4 grudnia 2017 r. Google Doodle była graficzną grą programistyczną z króliczkiem . Późniejsze poziomy były dość nietrywialne i wydawały się doskonałym kandydatem do gry w golfa atomowego .

Detale

Gra

• Dostępne są cztery ruchy: przeskocz do przodu, skręć w lewo, skręć w prawo i pętlę. Każdy z tych ruchów jest jednym żetonem , co odpowiada temu, że każdy z nich jest jednym kafelkiem w grze.
• Królik może zmierzyć się z czterema prostopadłymi kierunkami (tj. Północ, południe, wschód, zachód).
• Królik może wskoczyć do przodu (przesuń o jedno pole w kierunku, w którym jest skierowany) i skręć w lewo lub w prawo.
• Pętle mogą zawierać dowolną liczbę innych ruchów, w tym inne pętle, a ich liczba iteracji jest dowolną liczbą całkowitą dodatnią (chociaż gra technicznie pozwala na liczbę iteracji równą 0).
• Plansza to zestaw kwadratów wyrównanych do siatki, a króliczek może przeskakiwać między sąsiednimi kwadratami.
• Królik nie może wskoczyć w pustkę. Oznacza to, że próba zeskoczenia z planszy nic nie robi. (To było najwyraźniej niespodzianką dla niektórych osób i rozczarowaniem dla innych).
• Kwadraty są oznaczone lub niezaznaczone. Kiedy króliczek jest na kwadracie, zostaje oznaczony.
• Poziom jest ukończony, gdy wszystkie kwadraty są zaznaczone.
• Możesz założyć, że istnieje rozwiązanie.

Twój kod

• Cel: biorąc pod uwagę planszę, znajdź jedno lub więcej najkrótszych rozwiązań.
• Dane wejściowe to lista kwadratowych lokalizacji tworzących planszę (z wyróżnieniem zaznaczonych i nieoznaczonych kwadratów), a informacja wyjściowa to lista ruchów. Format wejściowy i wyjściowy w ogóle nie ma znaczenia, o ile są czytelne dla człowieka i zrozumiałe.
• Kryterium wygranej: suma ruchów najkrótszych rozwiązań znalezionych w ciągu jednej minuty dla każdej planszy. Jeśli twój program nie znajdzie rozwiązania dla żadnej konkretnej planszy, twój wynik dla tej planszy to (5 * liczba kwadratów).
• Nie należy w żaden sposób kodować rozwiązań. Twój kod powinien być w stanie przyjąć dowolną tablicę jako dane wejściowe, a nie tylko te podane jako przykłady poniżej.

Przykłady

Rozwiązania są ukryte w spoilerach, abyś mógł najpierw zagrać w grę i spróbować niektórych z nich samodzielnie. Ponadto dla każdego z nich podano tylko jedno rozwiązanie.

Sjest kwadratem początkowym króliczka (skierowanym na wschód), #jest kwadratem nieoznaczonym i Ojest kwadratem oznaczonym. W przypadku ruchów mój zapis to F= przeskocz do przodu, L= skręć w lewo, R= skręć w prawo i LOOP(<num>){<moves>}oznacza pętlę, która iteruje <num>razy i robi to za <moves>każdym razem. Jeśli pętla może działać dowolną liczbę razy powyżej pewnej minimalnej liczby, <num>można ją pominąć (tzn. Działa nieskończoność).

Poziom 1:

S##

FF

Poziom 2:

S##
  #
  #

PĘTLA (2) {FFR}

Poziom 3:

S##
# #
###

LOOP {FFR}

Poziom 4:

###
# #
##S##
  # #
  ###

LOOP {F LOOP (7) {FL}} (znaleziony przez DJMcMayhem)

Poziom 5:

#####
# # #
##S##
# # #
#####

LOOP (18) {LOOP (10) {FR} L}
Źródło: Reddit

Poziom 6:

 ###
#OOO#
#OSO#
#OOO#
 ###

LOOP {LOOP (3) {F} L}

Ogromne tablice: (najkrótsze obecnie nieznane rozwiązania)

12x12:

S###########
############
############
############
############
############
############
############
############
############
############
############

Poziom 5, ale znacznie większy:

#############
# # # # # # #
#############
# # # # # # #
#############
# # # # # # #
######S######
# # # # # # #
#############
# # # # # # #
#############
# # # # # # #
#############

Więcej dziurawych desek:

S##########
###########
## ## ## ##
###########
###########
## ## ## ##
###########
###########
## ## ## ##
###########
###########

i

S#########
##########
##  ##  ##
##  ##  ##
##########
##########
##  ##  ##
##  ##  ##
##########
##########

Wreszcie asymetria może być prawdziwym bólem w tyłku:

#######
# ##  #
#######
###S###
# ##  #
# ##  #
#######

i

#########
# ##  ###
###S  ###
# #######
###    ##
#####   #
####  ###
#########
#########

Python 3, 67 tokenów

import sys
import time

class Bunny():
    def __init__(self):
        self.direction = [0, 1]
        self.coords = [-1, -1]

    def setCoords(self, x, y):
        self.coords = [x, y]

    def rotate(self, dir):
        directions = [[1, 0], [0, 1], [-1, 0], [0, -1]]
        if dir == 'L':
            self.direction = directions[(directions.index(self.direction) + 1) % 4]
        if dir == 'R':
            self.direction = directions[(directions.index(self.direction) - 1) % 4]

    def hop(self):
        self.coords = self.nextTile()

    # Returns where the bunny is about to jump to
    def nextTile(self):
        return [self.coords[0] + self.direction[0], self.coords[1] + self.direction[1]]

class BoardState():
    def __init__(self, map):
        self.unvisited = 0
        self.map = []

        self.bunny = Bunny()
        self.hopsLeft = 0

        for x, row in enumerate(map):
            newRow = []
            for y, char in enumerate(row):
                if char == '#':
                    newRow.append(1)
                    self.unvisited += 1

                elif char == 'S':
                    newRow.append(2)

                    if -1 in self.bunny.coords:
                        self.bunny.setCoords(x, y)
                    else:
                        print("Multiple starting points found", file=sys.stderr)
                        sys.exit(1)

                elif char == ' ':
                    newRow.append(0)

                elif char == 'O':
                    newRow.append(2)

                else:
                    print("Invalid char in input", file=sys.stderr)
                    sys.exit(1)

            self.map.append(newRow)

        if -1 in self.bunny.coords:
            print("No starting point defined", file=sys.stderr)
            sys.exit(1)

    def finished(self):
        return self.unvisited == 0

    def validCoords(self, x, y):
        return -1 < x < len(self.map) and -1 < y < len(self.map[0])

    def runCom(self, com):
        if self.finished():
            return

        if self.hopsLeft < self.unvisited:
            return

        if com == 'F':
            x, y = self.bunny.nextTile()
            if self.validCoords(x, y) and self.map[x][y] != 0:
                self.bunny.hop()
                self.hopsLeft -= 1

                if (self.map[x][y] == 1):
                    self.unvisited -= 1
                self.map[x][y] = 2

        else:
            self.bunny.rotate(com)

class loop():
    def __init__(self, loops, commands):
        self.loops = loops
        self.commands = [*commands]

    def __str__(self):
        return "loop({}, {})".format(self.loops, list(self.commands))

    def __repr__(self):
        return str(self)


def rejectRedundantCode(code):
    if isSnippetRedundant(code):
        return False

    if type(code[-1]) is str:
        if code[-1] in "LR":
            return False
    else:
        if len(code[-1].commands) == 1:
            print(code)
            if code[-1].commands[-1] in "LR":
                return False

    return True


def isSnippetRedundant(code):
    joined = "".join(str(com) for com in code)

    if any(redCode in joined for redCode in ["FFF", "RL", "LR", "RRR", "LLL"]):
        return True

    for com in code:
        if type(com) is not str:
            if len(com.commands) == 1:
                if com.loops == 2:
                    return True

                if type(com.commands[0]) is not str:
                    return True

                if com.commands[0] in "LR":
                    return True

            if len(com.commands) > 1 and len(set(com.commands)) == 1:
                return True

            if isSnippetRedundant(com.commands):
                return True

    for i in range(len(code)):
        if type(code[i]) is not str and len(code[i].commands) == 1:
            if i > 0 and code[i].commands[0] == code[i-1]:
                return True
            if i < len(code) - 1 and code[i].commands[0] == code[i+1]:
                return True

        if type(code[i]) is not str:
            if i > 0 and type(code[i-1]) is not str and code[i].commands == code[i-1].commands:
                return True
            if i < len(code) - 1 and type(code[i+1]) is not str and code[i].commands == code[i+1].commands:
                return True

            if len(code[i].commands) > 3 and all(type(com) is str for com in code[i].commands):
                return True

    return False

def flatten(code):
    flat = ""
    for com in code:
        if type(com) is str:
            flat += com
        else:
            flat += flatten(com.commands) * com.loops

    return flat

def newGen(n, topLevel = True):
    maxLoops = 9
    minLoops = 2
    if n < 1:
        yield []

    if n == 1:
        yield from [["F"], ["L"], ["R"]]

    elif n == 2:
        yield from [["F", "F"], ["F", "L"], ["F", "R"], ["L", "F"], ["R", "F"]]

    elif n == 3:
        for innerCode in newGen(n - 1, False):
            for loops in range(minLoops, maxLoops):
                if len(innerCode) != 1 and 0 < innerCode.count('F') < 2:
                    yield [loop(loops, innerCode)]

        for com in "FLR":
            for suffix in newGen(n - 2, False):
                for loops in range(minLoops, maxLoops):
                    if com not in suffix:
                        yield [loop(loops, [com])] + suffix

    else:
        for innerCode in newGen(n - 1, False):
            if topLevel:
                yield [loop(17, innerCode)]
            else:
                for loops in range(minLoops, maxLoops):
                    if len(innerCode) > 1:
                        yield [loop(loops, innerCode)]

        for com in "FLR":
            for innerCode in newGen(n - 2, False):
                for loops in range(minLoops, maxLoops):
                    yield [loop(loops, innerCode)] + [com]
                    yield [com] + [loop(loops, innerCode)]

def codeLen(code):
    l = 0
    for com in code:
        l += 1
        if type(com) is not str:
            l += codeLen(com.commands)

    return l


def test(code, board):
    state = BoardState(board)
    state.hopsLeft = flatten(code).count('F')

    for com in code:
        state.runCom(com)


    return state.finished()

def testAll():
    score = 0
    for i, board in enumerate(boards):
        print("\n\nTesting board {}:".format(i + 1))
        #print('\n'.join(board),'\n')
        start = time.time()

        found = False
        tested = set()

        for maxLen in range(1, 12):
            lenCount = 0
            for code in filter(rejectRedundantCode, newGen(maxLen)):
                testCode = flatten(code)
                if testCode in tested:
                    continue

                tested.add(testCode)

                lenCount += 1
                if test(testCode, board):
                    found = True

                    stop = time.time()
                    print("{} token solution found in {} seconds".format(maxLen, stop - start))
                    print(code)
                    score += maxLen
                    break

            if found:
                break

    print("Final Score: {}".format(score))

def testOne(board):
    start = time.time()
    found = False
    tested = set()
    dupes = 0

    for maxLen in range(1, 12):
        lenCount = 0
        for code in filter(rejectRedundantCode, newGen(maxLen)):
            testCode = flatten(code)
            if testCode in tested:
                dupes += 1
                continue

            tested.add(testCode)

            lenCount += 1
            if test(testCode, board):
                found = True
                print(code)
                print("{} dupes found".format(dupes))
                break

        if found:
            break

        print("Length:\t{}\t\tCombinations:\t{}".format(maxLen, lenCount))

    stop = time.time()
    print(stop - start)

#testAll()
testOne(input().split('\n'))

Ten program przetestuje pojedynczą kartę wejściową, ale uważam, że ten sterownik testowy jest bardziej przydatny . Testuje każdą płytkę jednocześnie i drukuje, ile czasu zajęło znalezienie tego rozwiązania. Po uruchomieniu tego kodu na moim komputerze (czterordzeniowy procesor Intel i7-7700K @ 4,20 GHz, 16,0 GB pamięci RAM) otrzymuję następujące dane wyjściowe:

Testing board 1:
2 token solution found in 0.0 seconds
['F', 'F']


Testing board 2:
4 token solution found in 0.0025103092193603516 seconds
[loop(17, [loop(3, ['F']), 'R'])]


Testing board 3:
4 token solution found in 0.0010025501251220703 seconds
[loop(17, [loop(3, ['F']), 'L'])]


Testing board 4:
5 token solution found in 0.012532949447631836 seconds
[loop(17, ['F', loop(7, ['F', 'L'])])]


Testing board 5:
5 token solution found in 0.011022329330444336 seconds
[loop(17, ['F', loop(5, ['F', 'L'])])]


Testing board 6:
4 token solution found in 0.0015044212341308594 seconds
[loop(17, [loop(3, ['F']), 'L'])]


Testing board 7:
8 token solution found in 29.32585096359253 seconds
[loop(17, [loop(4, [loop(5, [loop(6, ['F']), 'L']), 'L']), 'F'])]


Testing board 8:
8 token solution found in 17.202533721923828 seconds
[loop(17, ['F', loop(7, [loop(5, [loop(4, ['F']), 'L']), 'F'])])]


Testing board 9:
6 token solution found in 0.10585856437683105 seconds
[loop(17, [loop(7, [loop(4, ['F']), 'L']), 'F'])]


Testing board 10:
6 token solution found in 0.12129759788513184 seconds
[loop(17, [loop(7, [loop(5, ['F']), 'L']), 'F'])]


Testing board 11:
7 token solution found in 4.331984758377075 seconds
[loop(17, [loop(8, ['F', loop(5, ['F', 'L'])]), 'L'])]


Testing board 12:
8 token solution found in 58.620323181152344 seconds
[loop(17, [loop(3, ['F', loop(4, [loop(3, ['F']), 'R'])]), 'L'])]

Final Score: 67

Ten ostatni test ledwo piszczy pod minimalnym ograniczeniem.

tło

To było jedno z najbardziej zabawnych wyzwań, na jakie kiedykolwiek odpowiedziałem! Miałem polowanie na wybuchy i szukałem heurystyki, aby ograniczyć rzeczy.

Ogólnie rzecz biorąc, tutaj na PPCG mam tendencję do odpowiadania na stosunkowo łatwe pytania. Szczególnie podoba mi się tag string, ponieważ ogólnie jest on całkiem odpowiedni dla moich języków. Pewnego dnia, jakieś dwa tygodnie temu, przeglądałem moje odznaki i zdałem sobie sprawę, że nigdy nie dostałem odznaki odrodzenia . Więc przejrzałem bez odpowiedzi, aby sprawdzić, czy coś przykuło moją uwagę, i znalazłem to pytanie. Postanowiłem odpowiedzieć bez względu na koszty. Skończyło się to trochę trudniej, niż się spodziewałem, ale w końcu dostałem brutalną siłę, z której mogę powiedzieć, że jestem dumny. Ale to wyzwanie jest dla mnie zupełnie nietypowe, ponieważ zwykle nie spędzam więcej niż godzinę na jednej odpowiedzi. Ta odpowiedź zajęła mi nieco ponad 2 tygodnie i co najmniej 10+ pracy, aby w końcu przejść do tego etapu, chociaż nie śledziłem uważnie.

Pierwsza iteracja była czystym rozwiązaniem brutalnej siły. Użyłem następującego kodu do wygenerowania wszystkich fragmentów o długości N :

def generateCodeLenN(n, maxLoopComs, maxLoops, allowRedundant = False):
    if n < 1:
        return []

    if n == 1:
        return [["F"], ["L"], ["R"]]

    results = []

    if 1:
        for com in "FLR":
            for suffix in generateCodeLenN(n - 1, maxLoopComs, maxLoops, allowRedundant):
                if allowRedundant or not isSnippetRedundant([com] + suffix):
                    results.append([com] + suffix)

    for loopCount in range(2, maxLoopComs):
        for loopComs in range(1, n):
            for innerCode in generateCodeLenN(loopComs, maxLoopComs, maxLoops - 1, allowRedundant):
                if not allowRedundant and isSnippetRedundant([loop(loopCount, innerCode)]):
                    continue

                for suffix in generateCodeLenN(n - loopComs - 1, maxLoopComs, maxLoops - 1, allowRedundant):
                    if not allowRedundant and isSnippetRedundant([loop(loopCount, innerCode)] + suffix):
                        continue

                    results.append([loop(loopCount, innerCode)] + suffix)

                if loopComs == n - 1:
                    results.append([loop(loopCount, innerCode)])

    return results

W tym momencie byłem pewien, że testowanie każdej możliwej odpowiedzi byłoby zbyt wolne, więc isSnippetRedundantfiltrowałem fragmenty, które można napisać krótszym fragmentem. Na przykład odmówiłbym wydania fragmentu, ["F", "F", "F"]ponieważ można uzyskać dokładnie takie same efekty [Loop(3, ["F"]), więc jeśli dojdziemy do punktu, w którym testujemy fragmenty długości 3, wiemy, że żaden fragment długości 3 nie mógłby rozwiązać obecnej płyty. Wykorzystało to wiele dobrych mnemoników, ale ostatecznie tak było waaaayza wolno. Testowanie 12 zajęło nieco ponad 3000 sekund przy użyciu tego podejścia. Jest to wyraźnie znacznie za wolne. Ale korzystając z tych informacji i kilku cykli komputerowych, by brutalnie wymusić krótkie rozwiązania każdej płyty, mogłem znaleźć nowy wzór. Zauważyłem, że prawie każde znalezione rozwiązanie ogólnie wygląda następująco:

[<com> loop(n, []) <com>]

zagnieżdżone w kilku warstwach, a pojedyncze coms z każdej strony są opcjonalne. Oznacza to, że rozwiązania takie jak:

["F", "F", "R", "F", "F", "L", "R", "F", "L"]

nigdy się nie pojawi. W rzeczywistości nigdy nie było sekwencji więcej niż 3 tokenów niepętlowych. Jednym ze sposobów wykorzystania tego byłoby odfiltrowanie ich wszystkich i nie zawracanie sobie głowy ich testowaniem. Ale generowanie ich wciąż zajmowało nie mniej ważny czas, a filtrowanie przez miliony takich fragmentów ledwo skróciło czas. Zamiast tego drastycznie przepisałem generator kodu, aby wygenerował tylko fragmenty zgodne z tym wzorcem. W pseudokodzie nowy generator stosuje się do tego ogólnego wzorca:

def codeGen(n):
    if n == 1:
        yield each [<com>]

    if n == 2:
        yield each [<com>, <com>]

    if n == 3:
        yield each [loop(n, <com length 2>]
        yield each [loop(n, <com>), <com>]

    else:
        yield each [loop(n, <com length n-1>)]
        yield each [loop(n, <com length n-2>), <com>]
        yield each [<com>, loop(n, <com length n-2>)]

        # Removed later
        # yield each [<com>, loop(n, <com length n-3>), <com>]
        # yield each [<com>, <com>, loop(n, <com length n-3>)]
        # yield each [loop(n, <com length n-3>), <com>, <com>]

To skróciło najdłuższy przypadek testowy do 140 sekund, co jest absurdalną poprawą. Ale odtąd wciąż było kilka rzeczy, które musiałem poprawić. Zacząłem bardziej agresywnie odfiltrowywać zbędny / bezwartościowy kod i sprawdzać, czy kod został wcześniej przetestowany. To jeszcze bardziej go zmniejszyło, ale to nie wystarczyło. Ostatnim brakującym elementem był licznik pętli. Poprzez mój bardzo zaawansowany algorytm (czytaj: losowa próba i błąd ) ustaliłem, że optymalny zakres pozwalający na uruchomienie pętli to [3-8]. Ale jest ogromna poprawa: jeśli wiemy, że [loop(8, [loop(8, ['F', loop(5, ['F', 'L'])]), 'L'])]nie możemy rozwiązać naszej rady, to absolutnie nie ma takiej możliwości[loop(3, [loop(8, ['F', loop(5, ['F', 'L'])]), 'L'])]lub dowolna liczba pętli od 3-7 może rozwiązać ten problem. Zamiast iterować wszystkie rozmiary pętli od 3-8, ustawiamy liczbę pętli w zewnętrznej pętli na maksimum. To powoduje zmniejszenie przestrzeni wyszukiwania o współczynnik maxLoop - minLoop, lub 6 w tym przypadku.

To bardzo pomogło, ale ostatecznie podniosło wynik. Niektóre rozwiązania, które znalazłem wcześniej przy użyciu brutalnej siły, wymagają uruchomienia większej liczby pętli (na przykład tablice 4 i 6). Zamiast ustawiać liczbę pętli zewnętrznych na 8, ustawiamy liczbę pętli zewnętrznych na 17, magiczną liczbę obliczoną również przez mój wysoce zaawansowany algorytm. Wiemy, że możemy to zrobić, ponieważ zwiększenie liczby pętli najbardziej zewnętrznej nie ma wpływu na ważność rozwiązania. Ten krok faktycznie obniżył nasz końcowy wynik o 13. Nie jest to więc trywialny krok.