What is the level 2 Google Foobar challenge?

There are 2 challenges at this level. Still 7 days per challenge. It’s not that simple anymore. Much harder

readme.txt:

challenge I - Gearing Up for Destruction:

As Commander Lambda’s personal assistant, you’ve been assigned the task of configuring the LAMBCHOP doomsday device’s axial orientation gears. It should be pretty simple – just add gears to create the appropriate rotation ratio. But the problem is, due to the layout of the LAMBCHOP and the complicated system of beams and pipes supporting it, the pegs that will support the gears are fixed in place.

The LAMBCHOP’s engineers have given you lists identifying the placement of groups of pegs along various support beams. You need to place a gear on each peg (otherwise the gears will collide with unoccupied pegs). The engineers have plenty of gears in all different sizes stocked up, so you can choose gears of any size, from a radius of 1 on up. Your goal is to build a system where the last gear rotates at twice the rate (in revolutions per minute, or rpm) of the first gear, no matter the direction. Each gear (except the last) touches and turns the gear on the next peg to the right.

Given a list of distinct positive integers named pegs representing the location of each peg along the support beam, write a function solution(pegs) which, if there is a solution, returns a list of two positive integers a and b representing the numerator and denominator of the first gear’s radius in its simplest form in order to achieve the goal above, such that radius = a/b. The ratio a/b should be greater than or equal to 1. Not all support configurations will necessarily be capable of creating the proper rotation ratio, so if the task is impossible, the function solution(pegs) should return the list [-1, -1].

For example, if the pegs are placed at [4, 30, 50], then the first gear could have a radius of 12, the second gear could have a radius of 14, and the last one a radius of 6. Thus, the last gear would rotate twice as fast as the first one. In this case, pegs would be [4, 30, 50] and solution(pegs) should return [12, 1].

The list pegs will be given sorted in ascending order and will contain at least 2 and no more than 20 distinct positive integers, all between 1 and 10000 inclusive.

1
2
3
4
5

solution.solution([4, 30, 50])
12,1

solution.solution([4, 17, 50])
-1,-1

challenge II - Don’t Get Volunteered!:

As a henchman on Commander Lambda’s space station, you’re expected to be resourceful, smart, and a quick thinker. It’s not easy building a doomsday device and ordering the bunnies around at the same time, after all! In order to make sure that everyone is sufficiently quick-witted, Commander Lambda has installed new flooring outside the henchman dormitories. It looks like a chessboard, and every morning and evening you have to solve a new movement puzzle in order to cross the floor. That would be fine if you got to be the rook or the queen, but instead, you have to be the knight. Worse, if you take too much time solving the puzzle, you get “volunteered” as a test subject for the LAMBCHOP doomsday device!

To help yourself get to and from your bunk every day, write a function called solution(src, dest) which takes in two parameters: the source square, on which you start, and the destination square, which is where you need to land to solve the puzzle. The function should return an integer representing the smallest number of moves it will take for you to travel from the source square to the destination square using a chess knight’s moves (that is, two squares in any direction immediately followed by one square perpendicular to that direction, or vice versa, in an “L” shape). Both the source and destination squares will be an integer between 0 and 63, inclusive, and are numbered like the example chessboard below:

1
2
3
4
5

solution.solution(0, 1)
3

solution.solution(19, 36)
1

How did I solve the level 2 Google Foobar challenge?

challenge I - Gearing Up for Destruction:

Too lazy to do the math, I searched for the formula on Google instead. This source is a great answer to this challenge

So the formula is

1
2

r0(odd) = 2 * (-P(0) + 2*(P(1)-P(2)+P(3)+...+(sign)*P(n-2)) - P(n-1))
r0(even) = 2/3 * (-P(0) + 2*(P(1)-P(2)+P(3)+...+(sign)*P(n-2)) + P(n-1))

The rest is now simple, right? 😉

And additional information for you is that you may also face the Floating Point Limitations just like me. then I swapped the /3 to another position as Associative property of multiplication then It worked. Magic!!

so the final formula should be:

1
2

r0(odd) = 2 * (-P(0) + 2*(P(1)-P(2)+P(3)+...+(sign)*P(n-2)) - P(n-1))
r0(even) = 2 * (-P(0) + 2*(P(1)-P(2)+P(3)+...+(sign)*P(n-2)) + P(n-1)) / 3

But that’s still not enough yet! We need to do the validation step to make sure all gears >= 1 and the first gear >= 2 (r0=2*rn). If the result does not pass the validation. Then we return the [-1, -1]. This validation step is ugly and makes us lose confidence in the coverage of the formula. But if you can not find a better formula, you can use it, because it passed all the testcases 😎

challenge II - Don’t Get Volunteered!:

This one is easier than the first one. But I also had to find a solution before I did. This source was the inspiration for my solution.

The steps to solve this challenge are:

• Create the board object:
  • Start with (a source knight and a destination knight). Find a route to help source knight meet destination knight:
    • iterate over all possible locations in which a source knight can be located:
      • at each possible location, generate a child source knight with:
        • new coordinates
        • step_count = parent source knight’s step_count + 1
        • then check:
          • if it meets the destination knight, return step_count.
          • if it visits the old location, skip that route.
          • if it visits the very new location, recreate the child source knight.

solution.py:

challenge I - Gearing Up for Destruction:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

from fractions import Fraction


def find_first_gear(pegs):
    is_odd = len(pegs) % 2
    general_sum = 0
    for index, common_peg in enumerate(pegs[1:-1]):
        sign = 1 if index % 2 == 0 else -1
        general_sum += sign * common_peg
    if is_odd:
        all_sum = 2 * (-pegs[0] + 2 * general_sum - pegs[-1])
    else:
        all_sum = 2 * float(-pegs[0] + 2 * general_sum + pegs[-1]) / 3
    fraction = Fraction(all_sum).limit_denominator()
    return fraction


def check_gear_radius(pegs, first_gear):
    if first_gear < 2:
        return False
    radius = first_gear
    for peg_index in range(len(pegs) - 1):
        gap = pegs[peg_index + 1] - pegs[peg_index]
        next_radius = gap - radius
        if next_radius < 1:
            return False
        else:
            radius = next_radius
    return True


def solution(pegs):
    first_gear = find_first_gear(pegs)
    numerator = first_gear.numerator
    denominator = first_gear.denominator
    is_valid = check_gear_radius(pegs, first_gear)
    if is_valid:
        result = [numerator, denominator]
    else:
        result = [-1, -1]
    return result

challenge II - Don’t Get Volunteered!:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

BOARD_SIZE = 8
AVAILABLE_MOVES = [(1, 2), (1, -2), (-1, 2), (-1, -2), (2, 1), (2, -1), (-2, 1), (-2, -1)]


class Knight:
    def __init__(self, x=0, y=0, step_count=0, position=None):
        if position:
            x, y = self.position_to_coordinates(position)
        self.x = x
        self.y = y
        self.step_count = step_count

    @property
    def coordinates_to_position(self):
        return self.x + self.y * BOARD_SIZE

    @classmethod
    def position_to_coordinates(cls, position):
        x = position % BOARD_SIZE
        y = int(position / BOARD_SIZE)
        return x, y

    def __hash__(self):
        return self.coordinates_to_position

    def __eq__(self, node):
        return self.x == node.x and self.y == node.y


class Board:
    def __init__(self):
        self.size = BOARD_SIZE
        self.available_moves = AVAILABLE_MOVES

    @classmethod
    def validate_coordidates(cls, x, y):
        return (BOARD_SIZE > x >= 0) and (BOARD_SIZE > y >= 0)

    @classmethod
    def find_way(cls, start, end):
        steps = [start]
        visited = {}
        while steps:
            node = steps.pop(0)
            if node == end:
                return node.step_count
            elif not visited.get(node):
                visited[node] = True
                for offset in AVAILABLE_MOVES:
                    new_x, new_y = node.x + offset[0], node.y + offset[1]
                    if cls.validate_coordidates(new_x, new_y):
                        steps.append(Knight(new_x, new_y, node.step_count + 1))
        return BOARD_SIZE**2 + 1


def solution(src, dest):
    return Board.find_way(Knight(position=src), Knight(position=dest))