Snack Break Problem #4

Followup on SB2 and SB3

Last week's problem were ones that involved math and could be a bit challenging, but were valuable examples of problem solving! I hope that all of you take a shot at the problems and think about how you would go about solving them; an important part of getting better at programming is the ability to come up with solutions and learning from the whole process.

Here is the solution to SB2 that was posted on github.

SB2 was on prime factorization, a process that breaks down a number into prime numbers that, when multiplied together, equal the original number. This problem emphasizes one of the most powerful tools you have at your disposable as a programmer: if you do not have to do a calculation, don't do it! Eliminating cases before doing the calculations is a great way to speed up your program and can end up simplifying your problem drastically.

Here is the solution to SB3 that was posted on github.

SB3 was on finding the direction that an angle needs to rotate in order to become another angle. This is particularly useful for programming problems involving rotational offsets over time, with behaviors similar to compasses! This sort of problem is seen frequently in manipulating rotations in 2D and 3D.

Explaining my solution to SB2

function primeFactorization(x)
    local factor    = 3
    local factors   = { }

    -- get all factors of 2
    while x%2 == 0 do
        factors[#factors + 1]   = 2
        x                       = 0.5*x
    end

    -- eliminate candidate factors that are too large
    while factor*factor <= x do
        while x%factor == 0 do
            factors[#factors + 1]   = factor
            x                       = x / factor
        end
        factor = factor + 2 -- only check odd factors
    end

    -- add the remainder into the factors
    -- also catch cases where x is originally prime to begin with
    if x > 1 then
        factors[#factors + 1] = x
        table.sort(factors)
    end

    return factors
end

Like I said above, this is a problem where you can eliminate a lot of cases.

Let's go over some properties of prime numbers! Here are some fundamental ones...

• Rule 1: The smallest prime number is 2.
• Rule 2: 2 is the only even prime number. All other prime numbers are odd.

... and here is the most powerful fact we can use at our disposal.

• Rule 3: If a number is prime then it can be split into the product of two numbers, which we will call a and b. If both a and b are greater than the square root of our number, then obviously a*b will be greater than our number (verify this)! So, to verify that the number is prime, we only have to check if there are any factors less than or equal to the square root of the original number.

With these facts, we can build our algorithm. It's a bit complicated, but it throws away a lot of cases that we really don't need to check!

1. Keep track of the current factor
2. Keep dividing the number by 2 until it is no longer even (Rule 1)
3. Set our current factor to 3, the next prime number after 2
4. A factor will only be valid if it is less than the square root of our number, so we will keep looping until we reach a factor that is greater than the square root of our number (Rule 3)
5. Keep dividing our number by the current factor until it is no longer divisible by our current factor
6. Since all prime numbers are odd, increment the current factor by 2 to keep it odd (Rule 2)
7. Any remainder we have left after the loop is a leftover prime factor

Explaining my solution to SB3

local pi    = math.pi
local tau   = 2*pi

function angularOffsetSign(startAngle, goalAngle)
    startAngle  = startAngle%tau
    goalAngle   = goalAngle%tau

    local sameDirection         = startAngle == goalAngle
    local oppositeDirection     = (startAngle + pi)%tau == goalAngle

    if sameDirection or oppositeDirection then
        return 0
    end

    local result = (startAngle - goalAngle)%tau
    return result < pi and -1 or 1
end

The first thing we want to do with this problem is to catch cases where the result of angularOffsetSign will be 0, which is "if the clockwise path is as long as the counterclockwise path".

That translates to if startAngle and goalAngle are the same or if startAngle and goalAngle are pointing in opposite directions.

We can do that easily!

The first thing we want to do is wrap startAngle and goalAngle around 2*math.pi, because a full circle is 2pi radians. This makes our problem simpler by making sure that the angles are only within a single rotation. We can achieve this with the % operator.

If startAngle and goalAngle are the same, then startAngle == goalAngle will be true. If startAngle and goalAngle are pointing in opposite directions, then (startAngle + math.pi)%(2*math.pi) == goalAngle because math.pi is half of a circle and therefore describes a rotation that points in the opposite direction.

Now, all that is left is determining if the offset is -1 or 1 in the case that it is not 0. If we take advantage of %, this becomes quite easy, but I'll leave that up to you to ponder (think about the properties of modular arithmetic)!

This week's problem

This week we will be taking a break from math. Instead, we will be looking at using the power of tables and other built-in Lua functions to our advantage.

Table to String is SB4. You will be taking all of the contents of a table and turning it to string format!

Visit the link above for more details.

I'll see you all next week!