Рубрики
Без рубрики

Google Foobar Challenge | Посмотрите, как я прошел уровень от 1 до 5 в режиме реального времени

Я только что пригласил выполнить вызов Google Foobar. В этой статье я хочу поделиться с вами, как я решил проблемы в режиме реального времени. Цель этой статьи – обучать вас — и повеселиться. Итак, вы готовы? Уровень 1: простые номера Первой целью было найти идентификатор для … Google Foobar Challenge | Посмотрите, как я прошел уровни от 1 до 5 в режиме реального времени Подробнее »

Автор оригинала: Chris.

Я только что пригласил выполнить вызов Google Foobar. В этой статье я хочу поделиться с вами, как я решил проблемы в режиме реального времени. Цель этой статьи – обучать вас – и повеселиться. Итак, вы готовы?

Уровень 1: простые номера

Первая цель состояла в том, чтобы найти идентификатор для нового сотрудника в компании «Миньоны».

Идентификатор выбран база на случайном номере I. Как мы пришли от случайного целого числа Я к идентификатору нового сотрудника миньона?

  • Создать последовательность простых чисел '23571113 ...' Отказ
  • Идентификатор является подпоследовательностью, начиная с индекса Я и заканчивая индекс Я + 4 (включая).
  • Ценность Я это целое число от 0 до 10000.

Вот решение, которое я реализовал в видео:

def solution(i):
    
    # Determine prime sequence
    primes = getPrimeNumbers()
    
    return primes[i:i+5]
    


def getPrimeNumbers():
    '''Returns the string of prime 
    numbers up to 10k+5 positions.'''
    
    s = ''
    prime = 2
    while len(s) < 10005:
        
        # Add new prime to s
        s += str(prime)
        
        # Calculate next prime
        prime += 1
        while not is_prime(prime):
            prime += 1
    
    return s
        

def is_prime(n):
    '''Tests if a number is prime. '''
    for i in range(2,n):
        if n % i == 0:
            return False
    return True

print(solution(0))
# 23571

print(solution(3))
# 71113

Вы хотите развивать навыки Хорошо округлый Python Professional То же оплачивается в процессе? Станьте питоном фрилансером и закажите свою книгу Оставляя крысиную гонку с Python На Amazon ( Kindle/Print )!

Уровень 2 Challenge 1: Sequence Sum

Вот проблема, представляемая Google:

Numbers Station Coded Messages
When you went undercover in Commander Lambda's 
organization, you set up a coded messaging system with 
Bunny Headquarters to allow them to send you important 
mission updates. Now that you're here and promoted to 
Henchman, you need to make sure you can receive those 
messages - but since you need to sneak them past 
Commander Lambda's spies, it won't be easy!

Bunny HQ has secretly taken control of two of the 
galaxy's more obscure numbers stations, and will use 
them to broadcast lists of numbers. They've given you a
 numerical key, and their messages will be encrypted 
within the first sequence of numbers that adds up to 
that key within any given list of numbers.

Given a non-empty list of positive integers l and a 
target positive integer t, write a function solution(l,
 t) which verifies if there is at least one consecutive
 sequence of positive integers within the list l (i.e. 
a contiguous sub-list) that can be summed up to the 
given target positive integer t (the key) and returns 
the lexicographically smallest list containing the 
smallest start and end indexes where this sequence can 
be found, or returns the array [-1, -1] in the case 
that there is no such sequence (to throw off Lambda's 
spies, not all number broadcasts will contain a coded 
message).

For example, given the broadcast list l as [4, 3, 5, 7, 
8] and the key t as 12, the function solution(l, t) 
would return the list [0, 2] because the list l 
contains the sub-list [4, 3, 5] starting at index 0 and
 ending at index 2, for which 4 + 3 + 5 = 12, even 
though there is a shorter sequence that happens later 
in the list (5 + 7). On the other hand, given the list 
l as [1, 2, 3, 4] and the key t as 15, the function 
solution(l, t) would return [-1, -1] because there is 
no sub-list of list l that can be summed up to the 
given target value t = 15.

To help you identify the coded broadcasts, Bunny HQ has 
agreed to the following standards:

- Each list l will contain at least 1 element but never 
more than 100.
- Each element of l will be between 1 and 100.
- t will be a positive integer, not exceeding 250.
- The first element of the list l has index 0.
- For the list returned by solution(l, t), the start 
index must be equal or smaller than the end index.

Remember, to throw off Lambda's spies, Bunny HQ might 
include more than one contiguous sublist of a number 
broadcast that can be summed up to the key. You know 
that the message will always be hidden in the first 
sublist that sums up to the key, so solution(l, t) 
should only return that sublist.

Languages
To provide a Python solution, edit solution.py
To provide a Java solution, edit Solution.java

Test cases
Your code should pass the following test cases.
Note that it may also be run against hidden test cases 
not shown here.

-- Python cases --
Input:
solution.solution([1, 2, 3, 4], 15)
Output:
-1,-1
Input:
solution.solution([4, 3, 10, 2, 8], 12)
Output:
2,3

-- Java cases --
Input:
Solution.solution({1, 2, 3, 4}, 15)
Output:
-1,-1
Input:
Solution.solution({4, 3, 10, 2, 8}, 12)
Output:
2,3

Use verify [file] to test your solution and see how it
 does. When you are finished editing your code, use 
submit [file] to submit your answer. If your solution 
passes the test cases, it will be removed from your 
home folder.

Вот первый код, который я пробовал:

def solution(l, t):
    
    start = 0
    
    while start < len(l):
        for stop in range(start, len(l)):
            s = sum(l[start:stop+1])
            if s == t:
                return [start, stop]
            elif s > t:
                break
        start += 1
    
    return [-1, -1]
    

Код решает проблему, но она принимает квадратичное время выполнения, поэтому я, хотя мы можем сделать лучше? Да мы можем! Существует линейное решение выполнения:

def solution(l, t):
    
    start = stop = 0
    
    while start <= stop and stop < len(l):
        s = sum(l[start:stop+1])
        if s == t:
            return [start, stop]
        elif s < t:
            stop += 1
        else:
            start += 1
            stop = max(start, stop)
    
    return [-1, -1]

Оба решения работа – но последний намного быстрее. Вот вывод и тестовые случаи:

print(solution([250,0,0], 250))
print(solution([1,2,3,4], 15))
print(solution([4, 3, 10, 2, 8], 12))
print(solution([4, 3, 5, 7, 8], 12))
print(solution([260], 260))

'''
[0, 0]
[-1, -1]
[2, 3]
[0, 2]
[0, 0]
'''

После отправки решения в моем оболочке браузера Google сообщает мне, что есть еще один вызов, чтобы добраться до следующего уровня:

Уровень 2 Challenge 2: Цифры и остатки классов

Вот проблема, представляемая Google:

Please Pass the Coded Messages
You need to pass a message to the bunny prisoners, but
to avoid detection, the code you agreed to use is… 
obscure, to say the least. The bunnies are given food 
on standard-issue prison plates that are stamped with 
the numbers 0-9 for easier sorting, and you need to 
combine sets of plates to create the numbers in the 
code. The signal that a number is part of the code is 
that it is divisible by 3. You can do smaller numbers 
like 15 and 45 easily, but bigger numbers like 144 and 
414 are a little trickier. 

Write a program to help yourself quickly create large 
numbers for use in the code, given a limited number of 
plates to work with.

You have L, a list containing some digits (0 to 9). 
Write a function solution(L) which finds the largest 
number that can be made from some or all of these 
digits and is divisible by 3. If it is not possible to 
make such a number, return 0 as the solution. L will 
contain anywhere from 1 to 9 digits. The same digit may 
appear multiple times in the list, but each element in 
the list may only be used once.

Languages
To provide a Java solution, edit Solution.java
To provide a Python solution, edit solution.py

Test cases
Your code should pass the following test cases.
Note that it may also be run against hidden test cases 
not shown here.

-- Java cases --
Input:
Solution.solution({3, 1, 4, 1})
Output:
4311
Input:
Solution.solution({3, 1, 4, 1, 5, 9})
Output:
94311

-- Python cases --
Input:
solution.solution([3, 1, 4, 1])
Output:
4311
Input:
solution.solution([3, 1, 4, 1, 5, 9])
Output:
94311

Сначала я продолжал развивать наивный раствор (без преждевременной оптимизации)!

def solution(l):
    x = find_largest_bucket(l)
    return find_max_number(x)
    

def find_largest_bucket(l):
    
    ''' Are the digits in the list divisible?'''
    if sum(int(digit) for digit in l)%3 == 0:
        return l
    
    ''' Find all smaller buckets recursively '''
    buckets = []  
    for digit in l:
        if digit not in {0, 3, 6, 9}:
            tmp = l[:]
            tmp.remove(digit)
            buckets.append(find_largest_bucket(tmp))
    
    largest_bucket = max(buckets, key=find_max_number)
    return largest_bucket


def find_max_number(l):
    '''Returns maximal number that can be generated from list.'''
    sorted_list = sorted(l)[::-1]
    number = ''.join(str(x) for x in sorted_list)
    return int(number)

print(solution([3, 1, 4, 1]))

print(solution([1 for i in range(1000000)]))

Хотя этот код решает проблему, это не оптимально. Это может быть болезненно медленным для больших списков из-за многих уровней рекурсии. Поэтому я вернулся и разработал новую версию на основе остальных классов:

Вот код новой идеи:

def solution(l):

    # Don't modify existing list object
    bucket = l[:]
    
    # Remainder Class:
    state = sum(bucket)%3 

    while state > 0 and bucket:

        # Transition between remainder classes by removing numbers
        if state == 1:
            to_remove = set(bucket) & {1, 4, 7}
            if not to_remove:
                to_remove = set(bucket) & {2, 5, 8}
        elif state == 2:
            to_remove = set(bucket) & {2, 5, 8}
            if not to_remove:
                to_remove = set(bucket) & {1, 4, 7}

        # Remove min and move to new remainder class
        bucket.remove(min(to_remove))
        state = sum(bucket) % 3
 
    # Calculate maximal number from bucket
    sorted_list = sorted(bucket)[::-1]
    number = ''.join(str(x) for x in sorted_list)
    return int(number) if number else 0

print(solution([3, 1, 4, 1]))
print(solution([3, 1, 4, 1, 5, 9]))
print(solution([]))
print(solution([9, 9, 9, 9]))

Выход правильный. После отправки решения Google сообщает мне, что мне удалось успешно пройти уровень! Ура!

Я даже добрался до друга …

Awesome! Commander Lambda was so impressed by your
efforts that she's made you her personal assistant.
You'll be helping her directly with her work, which 
means you'll have access to all of her files-including 
the ones on the LAMBCHOP doomsday device. This is the 
chance you've been waiting for. Can you use your new 
access to finally topple Commander Lambda's evil 
empire?

Уровень 3 Challenge 1:

Вот следующая задача:

foobar:~/prepare-the-bunnies-escape xcent.py$ cat readme.txt 
Prepare the Bunnies' Escape
===========================

You're awfully close to destroying the LAMBCHOP doomsday device and freeing Commander Lambda's bunny prisoners, but once they're free of the prison blocks, the bunnies are going to need to escape Lambda's space station via the escape pods as quickly as possible. Unfortunately, the halls of the space station are a maze of corridors and dead ends that will be a deathtrap for the escaping bunnies. Fortunately, Commander Lambda has put you in charge of a remodeling project that will give you the opportunity to make things a little easier for the bunnies. Unfortunately (again), you can't just remove all obstacles between the bunnies and the escape pods - at most you can remove one wall per escape pod path, both to maintain structural integrity of the station and to avoid arousing Commander Lambda's suspicions.

You have maps of parts of the space station, each starting at a prison exit and ending at the door to an escape pod. The map is represented as a matrix of 0s and 1s, where 0s are passable space and 1s are impassable walls. The door out of the prison is at the top left (0,0) and the door into an escape pod is at the bottom right (w-1,h-1).

Write a function solution(map) that generates the length of the shortest path from the prison door to the escape pod, where you are allowed to remove one wall as part of your remodeling plans. The path length is the total number of nodes you pass through, counting both the entrance and exit nodes. The starting and ending positions are always passable (0). The map will always be solvable, though you may or may not need to remove a wall. The height and width of the map can be from 2 to 20. Moves can only be made in cardinal directions; no diagonal moves are allowed.

Languages
=========

To provide a Python solution, edit solution.py
To provide a Java solution, edit Solution.java

Test cases
==========
Your code should pass the following test cases.
Note that it may also be run against hidden test cases not shown here.

-- Python cases --
Input:
solution.solution([[0, 1, 1, 0], [0, 0, 0, 1], [1, 1, 0, 0], [1, 1, 1, 0]])
Output:
    7

Input:
solution.solution([[0, 0, 0, 0, 0, 0], [1, 1, 1, 1, 1, 0], [0, 0, 0, 0, 0, 0], [0, 1, 1, 1, 1, 1], [0, 1, 1, 1, 1, 1], [0, 0, 0, 0, 0, 0]])
Output:
    11

-- Java cases --
Input:
Solution.solution({{0, 1, 1, 0}, {0, 0, 0, 1}, {1, 1, 0, 0}, {1, 1, 1, 0}})
Output:
    7

Input:
Solution.solution({{0, 0, 0, 0, 0, 0}, {1, 1, 1, 1, 1, 0}, {0, 0, 0, 0, 0, 0}, {0, 1, 1, 1, 1, 1}, {0, 1, 1, 1, 1, 1}, {0, 0, 0, 0, 0, 0}})
Output:
    11

Use verify [file] to test your solution and see how it does. When you are finished editing your code, use submit [file] to submit your answer. If your solution passes the test cases, it will be removed from your home folder.

И мое решение:

def solution(m):

    # Calculate map stats
    w, h = len(m[0]), len(m) # width and height
    
    # The current minimal solution
    s_min = 401

    # Iterate over all possible inputs (by replacing 1s with 0s).
    for m_0 in all_maps(m):
        
        # Find the minimal path length
        s_min = min(min_path(m_0, w, h), s_min)

        # Optimization: Minimal solution?
        if s_min == w + h - 1:
            return s_min
        
    return s_min


def min_path(m, w, h):
    '''Takes a map m and returns the minimal path
    from the start to the end node. Also pass width and height.
    '''
        
    # Initialize dictionary of path lengths
    # integer: {(i,j), ...} (Set of nodes (i,j) with this integer path length)
    d = {1: {(0,0)}}

    # Expand "fringe" successively
    path_length = 2
    while path_length < 401 and d[path_length-1]:

        # Fill fringe
        fringe = set()
        for x in d[path_length-1]:
            
            # Expand node x (all neighbors) and exclude already visited
            expand_x = {y for y in neighbors(x,m) if not any(y in visited for visited in d.values())}
            fringe = fringe | expand_x
            
        # Have we found min path of exit node?
        if (h-1, w-1) in fringe:
            return path_length
        
        # Store new fring of minimal-path nodes
        d[path_length] = fringe

        # Find nodes with next-higher path_length
        path_length += 1

    return 401 # Infinite path length  
        

def neighbors(x, m):
    '''Returns a set of nodes (as tuples) that are neighbors of node x in m.'''
    i, j = x
    w, h = len(m[0]), len(m)
    candidates = {(i-1,j), (i+1,j), (i,j-1), (i,j+1)}
    neighbors = set()
    for y in candidates:
        i, j = y
        if i>=0 and i=0 and j

Уровень 3 Challenge 2

Success! You've managed to infiltrate Commander Lambda's evil organization, and finally earned yourself an entry-level position as a Minion on her space station. From here, you just might be able to subvert her plans to use the LAMBCHOP doomsday device to destroy Bunny Planet. Problem is, Minions are the lowest of the low in the Lambda hierarchy. Better buck up and get working, or you'll never make it to the top…
Commander Lambda sure is a task-master, isn't she? You're being worked to the bone!
You survived a week in Commander Lambda's organization, and you even managed to get yourself promoted. Hooray! Henchmen still don't have the kind of security access you'll need to take down Commander Lambda, though, so you'd better keep working. Chop chop!
The latest gossip in the henchman breakroom is that "LAMBCHOP" stands for "Lambda's Anti-Matter Biofuel Collision Hadron Oxidating Potentiator". You're pretty sure it runs on diesel, not biofuel, but you can at least give the commander credit for trying.
You got the guards to teach you a card game today, it's called Fizzbin. It's kind of pointless, but they seem to like it and it helps you pass the time while you work your way up to Commander Lambda's inner circle.
Awesome! Commander Lambda was so impressed by your efforts that she's made you her personal assistant. You'll be helping her directly with her work, which means you'll have access to all of her files-including the ones on the LAMBCHOP doomsday device. This is the chance you've been waiting for. Can you use your new access to finally topple Commander Lambda's evil empire?
Who the heck puts clover and coffee creamer in their tea? Commander Lambda, apparently. When you signed up to infiltrate her organization, you didn't think you'd get such an up-close and personal look at her more… unusual tastes.

FOOBAR: ~/XCECT.PY $ Запросить запрос на запрос … Есть много сложных вещей о том, чтобы быть под прикрытием как личный помощник командира Лямбда, но вы должны сказать, личный спа-салон и частные горячие какао-бар довольно потрясающий. Новая задача «Совершенство впрыска топлива» добавлено в вашу домашнюю папку. Время решить: 96 часов.

Fuel Injection Perfection
Commander Lambda has asked for your help to refine the automatic quantum antimatter fuel injection system for her LAMBCHOP doomsday device. It's a great chance for you to get a closer look at the LAMBCHOP - and maybe sneak in a bit of sabotage while you're at it - so you took the job gladly.
Quantum antimatter fuel comes in small pellets, which is convenient since the many moving parts of the LAMBCHOP each need to be fed fuel one pellet at a time. However, minions dump pellets in bulk into the fuel intake. You need to figure out the most efficient way to sort and shift the pellets down to a single pellet at a time.
The fuel control mechanisms have three operations:
1) Add one fuel pellet
2) Remove one fuel pellet
3) Divide the entire group of fuel pellets by 2 (due to the destructive energy released when a quantum antimatter pellet is cut in half, the safety controls will only allow this to happen if there is an even number of pellets)
Write a function called solution(n) which takes a positive integer as a string and returns the minimum number of operations needed to transform the number of pellets to 1. The fuel intake control panel can only display a number up to 309 digits long, so there won't ever be more pellets than you can express in that many digits.
For example:
solution(4) returns 2: 4 -> 2 -> 1
solution(15) returns 5: 15 -> 16 -> 8 -> 4 -> 2 -> 1
Languages
To provide a Python solution, edit solution.py
To provide a Java solution, edit Solution.java
Test cases
Your code should pass the following test cases.
Note that it may also be run against hidden test cases not shown here.
-- Python cases --
Input:
solution.solution('15')
Output:
5
Input:
solution.solution('4')
Output:
2
-- Java cases --
Input:
Solution.solution('4')
Output:
2
Input:
Solution.solution('15')
Output:
5
Use verify [file] to test your solution and see how it does. When you are finished editing your code, use submit [file] to submit your answer. If your solution passes the test cases, it will be removed from your home folder.
def solution(n):
    x = int(n)
    c = 0
    
    while x > 1:
        if x & 1 == 1:
            # x is odd
            if x % 4 == 1 or x==3:
                x -= 1
            else:
                x += 1
        else:
            # x is even
            x = x >> 1
        c += 1
    return c

        


print(solution('4'))
# 2

print(solution('15'))
# 5

print(solution('16'))
# 4

print(solution('32'))
# 5

print(solution('33'))
# 6

print(solution('31'))
# 6

print(solution('124480579411363943422977485485450829978158403576349485507396127987323092328068524587695005561434534623452345436346456353425362283769712245781118297614280332424240701048410620648401132628401374562794562558123463462235342526466804149296501029546541499918765438784295157088047123009825235235168758962399'))
foobar:~/fuel-injection-perfection xcent.py$ verify solution.py
Verifying solution…
All test cases passed. Use submit solution.py to submit your solution
foobar:~/fuel-injection-perfection xcent.py$ submit solution.py
Are you sure you want to submit your solution?
[Y]es or [N]o: Y
Submitting solution…
Submission: SUCCESSFUL. Completed in: 2 hrs, 20 mins, 18 secs.
Current level: 3
Challenges left to complete level: 1
Level 1: 100% [==========================================]
Level 2: 100% [==========================================]
Level 3: 66% [===========================……………]
Level 4: 0% [……………………………………]
Level 5: 0% [……………………………………]
Type request to request a new challenge now, or come back later.

Уровень 3 Challenge 3 Baby Bomb

foobar:~/ xcent.py$ request
Requesting challenge…
There are a lot of difficult things about being undercover as Commander Lambda's personal assistant, but you have to say, the personal spa and private hot cocoa bar are pretty awesome.
New challenge "Bomb, Baby!" added to your home folder.
Time to solve: 96 hours.
foobar:~/ xcent.py$
foobar:~/ xcent.py$ cd bomb-baby/
foobar:~/bomb-baby xcent.py$ ls
Solution.java
constraints.txt
readme.txt
solution.py
foobar:~/bomb-baby xcent.py$ cat solution.py
def​ ​solution(x,​ ​y):
​ ​​ ​​ ​​ ​#​ ​Your​ ​code​ ​here
foobar:~/bomb-baby xcent.py$ cat readme.txt
Bomb, Baby!
You're so close to destroying the LAMBCHOP doomsday device you can taste it! But in order to do so, you need to deploy special self-replicating bombs designed for you by the brightest scientists on Bunny Planet. There are two types: Mach bombs (M) and Facula bombs (F). The bombs, once released into the LAMBCHOP's inner workings, will automatically deploy to all the strategic points you've identified and destroy them at the same time.
But there's a few catches. First, the bombs self-replicate via one of two distinct processes:
Every Mach bomb retrieves a sync unit from a Facula bomb; for every Mach bomb, a Facula bomb is created;
Every Facula bomb spontaneously creates a Mach bomb.
For example, if you had 3 Mach bombs and 2 Facula bombs, they could either produce 3 Mach bombs and 5 Facula bombs, or 5 Mach bombs and 2 Facula bombs. The replication process can be changed each cycle.
Second, you need to ensure that you have exactly the right number of Mach and Facula bombs to destroy the LAMBCHOP device. Too few, and the device might survive. Too many, and you might overload the mass capacitors and create a singularity at the heart of the space station - not good!
And finally, you were only able to smuggle one of each type of bomb - one Mach, one Facula - aboard the ship when you arrived, so that's all you have to start with. (Thus it may be impossible to deploy the bombs to destroy the LAMBCHOP, but that's not going to stop you from trying!)
You need to know how many replication cycles (generations) it will take to generate the correct amount of bombs to destroy the LAMBCHOP. Write a function solution(M, F) where M and F are the number of Mach and Facula bombs needed. Return the fewest number of generations (as a string) that need to pass before you'll have the exact number of bombs necessary to destroy the LAMBCHOP, or the string "impossible" if this can't be done! M and F will be string representations of positive integers no larger than 10^50. For example, if M = "2" and F = "1", one generation would need to pass, so the solution would be "1". However, if M = "2" and F = "4", it would not be possible.
Languages
To provide a Java solution, edit Solution.java
To provide a Python solution, edit solution.py
Test cases
Your code should pass the following test cases.
Note that it may also be run against hidden test cases not shown here.
-- Java cases --
Input:
Solution.solution('2', '1')
Output:
1
Input:
Solution.solution('4', '7')
Output:
4
-- Python cases --
Input:
solution.solution('4', '7')
Output:
4
Input:
solution.solution('2', '1')
Output:
1
Use verify [file] to test your solution and see how it does. When you are finished editing your code, use submit [file] to submit your answer. If your solution passes the test cases, it will be removed from your home folder.
foobar:~/bomb-baby xcent.py$
#######################
# FIRST SOLUTION
#######################



def solution(x, y):
    goal = (int(x), int(y))
    start = (1, 1)
    gen = [start]
    c = 0
    while gen:
        # Generate new states
        next_gen = []
        for M,F in gen:
            if (M,F) == goal:
                return str(c)

            # Ignore states that never lead to goal
            MF = M+F
            if MF <= goal[0]:
                next_gen.append((MF, F))
            if MF <= goal[1]:
                next_gen.append((M, MF))
        
        # Go to next generation
        gen = next_gen
        c += 1

    return 'impossible'


print(solution('4', '7'))
# 4

print(solution('2', '1'))
# 1

print(solution('2', '4'))
# impossible


#######################
# SECOND SOLUTION
#######################



def old_solution(x, y):
    goal = (int(x), int(y))
    start = (1, 1)
    gen = [start]
    c = 0
    while gen:
        # Generate new states
        next_gen = []
        for M,F in gen:
            if (M,F) == goal:
                return str(c)

            # Ignore states that never lead to goal
            MF = M+F
            if MF <= goal[0]:
                next_gen.append((MF, F))
            if MF <= goal[1]:
                next_gen.append((M, MF))
        
        # Go to next generation
        gen = next_gen
        c += 1

    return 'impossible'

seen = set()

def solution(x, y):
    goal = (int(x), int(y))
    start = (1, 1)
    gen = set([start])
    c = 0
    while gen:

        if goal in gen:
            return str(c)
            
        # Generate new states
        next_gen = set()
        for M,F in gen:
            # Ignore states that never lead to goal
            MF = M+F
            if MF <= goal[0]:
                state = (MF, F)
                if state not in seen:
                    next_gen.add(state)
                    seen.add(state)
            if MF <= goal[1]:
                state = (M, MF)
                if state not in seen:
                    next_gen.add(state)
                    seen.add(state)
        
        # Go to next generation
        gen = next_gen
        c += 1

    return 'impossible'

print('*****OLD*****')
print(old_solution('4', '7'))
print(old_solution('2', '1'))
print(old_solution('2', '4'))

import time
t0 = time.time()
print(old_solution(str(10**4), str(10**3)))
t1 = time.time()

print(t1-t0, 'seconds have passed')
# 3.7617175579071045  seconds have passed

print()
print('*****NEW*****')
print(solution('4', '7'))
print(solution('2', '1'))
print(solution('2', '4'))

import time
t0 = time.time()
print(solution(str(10**4), str(10**4)))
t1 = time.time()

print(t1-t0, 'seconds have passed')




##############
# THIRD SOLUTION
##############
def solution(M, F):
    goal = (int(M), int(F))
    x, y = goal
    c = 0

    while x!=y:

        if x > y:
            num_subs = (x-y)//y + ((x-y) % y > 0)
            c += num_subs
            x, y = x - num_subs * y, y
        elif y > x:
            num_subs = (y-x)//x + ((y-x) % x > 0)
            c += num_subs
            x, y = x, y - num_subs * x
        

    return str(c) if (x, y)==(1, 1) else 'impossible'
foobar:~/bomb-baby xcent.py$ verify solution.py
Verifying solution…
All test cases passed. Use submit solution.py to submit your solution
foobar:~/bomb-baby xcent.py$ submit solution.py
Are you sure you want to submit your solution?
[Y]es or [N]o: Y
Submitting solution…
Excellent! You've destroyed Commander Lambda's doomsday device and saved Bunny Planet! But there's one small problem: the LAMBCHOP was a wool-y important part of her space station, and when you blew it up, you triggered a chain reaction that's tearing the station apart. Can you rescue the imprisoned bunnies and escape before the entire thing explodes?
Submission: SUCCESSFUL. Completed in: 4 hrs, 35 mins, 50 secs.
Level 3 complete
You are now on level 4
Challenges left to complete level: 2
Level 1: 100% [==========================================]
Level 2: 100% [==========================================]
Level 3: 100% [==========================================]
Level 4: 0% [……………………………………]
Level 5: 0% [……………………………………]
Refer a friend: "https://foobar.withgoogle.com/?eid=ZYbpR" (Used)
Type request to request a new challenge now, or come back later.
The code is strong with this one…
You can now share your solutions with a Google recruiter!
If you opt in, Google staffing may reach out to you regarding career opportunities.
We will use your information in accordance with our Applicant and Candidate Privacy Policy.
[#1] [Yes [N]o [A]sk me later:]
[Y]es [N]o [A]sk me later: A
Response: contact postponed.
To share your progress at any time, use the recruitme command.

Работая в качестве исследователя в распределенных системах, доктор Кристиан Майер нашел свою любовь к учению студентов компьютерных наук.

Чтобы помочь студентам достичь более высоких уровней успеха Python, он основал сайт программирования образования Finxter.com Отказ Он автор популярной книги программирования Python одноклассники (Nostarch 2020), Coauthor of Кофе-брейк Python Серия самооставленных книг, энтузиаста компьютерных наук, Фрилансера и владелец одного из лучших 10 крупнейших Питон блоги по всему миру.

Его страсти пишут, чтение и кодирование. Но его величайшая страсть состоит в том, чтобы служить стремлению кодер через Finxter и помогать им повысить свои навыки. Вы можете присоединиться к его бесплатной академии электронной почты здесь.

Оригинал: “https://blog.finxter.com/googles-foobar/”