Pada 4 Desember 2017, Google Doodle adalah game pemrograman grafis yang menampilkan kelinci . Level-level selanjutnya baik non-sepele dan mereka tampak seperti kandidat yang hebat untuk atom-golf tantangan .

Detail

Permainan

• Ada empat gerakan yang tersedia: melompat maju, belok kiri, belok kanan, dan putaran. Masing-masing gerakan ini adalah satu token , sesuai dengan fakta bahwa mereka masing-masing ubin dalam permainan.
• Kelinci dapat menghadapi empat arah ortogonal (yaitu utara, selatan, timur, barat).
• Kelinci bisa melompat ke depan (bergerak satu kotak ke arah yang dihadapinya) dan belok kiri atau kanan.
• Loop mungkin memiliki sejumlah gerakan lain di dalamnya, termasuk loop lain, dan jumlah iterasi mereka adalah bilangan bulat positif (meskipun game secara teknis memungkinkan jumlah iterasi 0).
• Papan adalah seperangkat kotak yang disejajarkan dengan kotak dan kelinci dapat melompat di antara kotak yang berdekatan.
• Kelinci tidak bisa melompat ke dalam kehampaan. Artinya, upaya untuk melompat dari papan tidak melakukan apa-apa. (Ini tampaknya mengejutkan bagi sebagian orang dan mengecewakan bagi yang lain.)
• Kotak ditandai atau tidak ditandai. Saat kelinci berada di kotak, itu menjadi ditandai.
• Level selesai ketika semua kotak ditandai.
• Anda mungkin menganggap ada solusi.

Kode Anda

• Tujuan: diberi papan, temukan satu atau lebih solusi terpendek.
• Input adalah daftar lokasi kuadrat yang membentuk papan (membedakan kotak bertanda dan tidak bertanda) dan output adalah daftar gerakan. Format input dan output tidak masalah sama sekali, selama mereka dapat dibaca dan dipahami manusia.
• Kriteria kemenangan: jumlah jumlah gerakan dari solusi terpendek yang ditemukan dalam satu menit untuk setiap papan. Jika program Anda tidak menemukan solusi untuk papan tertentu, skor Anda untuk papan itu adalah (5 * jumlah kotak).
• Tolong jangan solusi hardcode dengan cara apa pun. Kode Anda harus dapat mengambil papan apa pun sebagai input, bukan hanya yang diberikan sebagai contoh di bawah ini.

Contohnya

Solusi disembunyikan di spoiler untuk memberi Anda kesempatan untuk bermain game terlebih dahulu dan mencoba beberapa di antaranya sendiri. Juga, hanya satu solusi yang disediakan di bawah ini untuk masing-masing.

Sadalah bujur sangkar kelinci (menghadap ke timur), #adalah bujur sangkar tanpa tanda, dan Omerupakan bujur sangkar yang ditandai. Untuk gerakan, notasi saya adalah F= maju terus, L= belok kiri, R= belok kanan, dan LOOP(<num>){<moves>}menunjukkan loop yang mengulangi <num>kali dan melakukan <moves>setiap kali. Jika loop dapat berjalan beberapa kali di luar beberapa angka minimum, <num>dapat dihilangkan (yaitu infinity berfungsi).

Tingkat 1:

S##

FF

Level 2:

S##
  #
  #

LOOP (2) {FFR}

Tingkat 3:

S##
# #
###

LOOP {FFR}

Tingkat 4:

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

LOOP {F LOOP (7) {FL}} (ditemukan oleh DJMcMayhem)

Level 5:

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

LOOP (18) {LOOP (10) {FR} L}
Sumber: Reddit

Tingkat 6:

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

LOOP {LOOP (3) {F} L}

Papan besar: (solusi terpendek saat ini tidak diketahui)

12x12:

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

Level 5 tetapi jauh lebih besar:

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

Papan berlubang lainnya:

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

dan

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

Akhirnya, asimetri bisa sangat menyakitkan di pantat:

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

dan

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

Python 3, 67 token

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'))

Program ini akan menguji papan input tunggal, tetapi saya menemukan driver tes ini lebih bermanfaat . Ini akan menguji setiap papan sekaligus dan mencetak berapa lama untuk menemukan solusi itu. Ketika saya menjalankan kode itu di komputer saya (Intel i7-7700K quad core CPU @ 4.20 GHz, RAM 16.0 GB), saya mendapatkan output sebagai berikut:

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

Tes terakhir ini hanya nyaris mencicit di bawah pembatasan menit.

Latar Belakang

Ini adalah salah satu tantangan paling menyenangkan yang pernah saya jawab! Saya memiliki pola ledakan berburu dan mencari heuristik untuk mengurangi hal-hal.

Secara umum, di sini di PPCG saya cenderung menjawab pertanyaan yang relatif mudah. Saya terutama menyukai tag string karena umumnya cukup cocok untuk bahasa saya. Suatu hari, sekitar dua minggu yang lalu, saya melihat-lihat lencana saya dan saya menyadari bahwa saya belum pernah mendapatkan lencana kebangunan rohani . Jadi saya melihat-lihat yang belum terjawab tab untuk melihat apakah ada sesuatu yang menarik perhatian saya, dan saya menemukan pertanyaan ini. Saya memutuskan untuk menjawabnya terlepas dari biaya. Itu akhirnya menjadi sedikit lebih sulit daripada yang saya pikirkan, tetapi saya akhirnya mendapat jawaban kasar yang bisa saya katakan saya bangga. Tetapi tantangan ini sama sekali di luar normal bagi saya karena saya biasanya tidak menghabiskan lebih dari satu jam pada satu jawaban. Jawaban ini butuh saya sedikit lebih dari 2 minggu dan setidaknya 10+ pekerjaan untuk akhirnya sampai ke tahap ini, meskipun saya tidak melacak dengan cermat.

Iterasi pertama adalah solusi brute force murni. Saya menggunakan kode berikut untuk menghasilkan semua potongan hingga panjang 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

Pada titik ini, saya yakin bahwa menguji setiap jawaban yang mungkin akan terlalu lambat, jadi saya biasa isSnippetRedundantmemfilter cuplikan yang dapat ditulis dengan cuplikan yang lebih pendek. Sebagai contoh, saya akan menolak untuk menghasilkan cuplikan ["F", "F", "F"]karena efek yang sama persis dapat dicapai [Loop(3, ["F"]), jadi jika kita sampai pada titik di mana kita menguji cuplikan panjang-3, kita tahu bahwa tidak ada cuplikan panjang-3 yang dapat menyelesaikan papan saat ini. Ini menggunakan banyak mnemonik yang baik, tetapi akhirnya adalah waaaayterlalu lambat. Testcase 12 mengambil lebih dari 3.000 detik menggunakan pendekatan ini. Ini jelas terlalu lambat. Tetapi dengan menggunakan informasi ini dan banyak siklus komputer untuk memaksa solusi pendek untuk setiap papan, saya dapat menemukan pola baru. Saya perhatikan bahwa hampir setiap solusi yang ditemukan umumnya akan terlihat seperti sesuatu seperti berikut:

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

bersarang beberapa lapisan, dengan com tunggal di setiap sisi menjadi opsional. Ini berarti bahwa solusi seperti:

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

tidak akan pernah muncul. Bahkan, tidak pernah ada urutan lebih dari 3 token non-loop. Salah satu cara untuk memanfaatkan ini adalah dengan menyaring semua ini dan tidak repot untuk mengujinya. Tetapi menghasilkan mereka masih membutuhkan waktu yang tidak dapat diabaikan, dan menyaring jutaan snippet seperti ini hampir tidak akan memotong waktu. Sebaliknya saya secara drastis menulis ulang generator kode untuk hanya menghasilkan snippet mengikuti pola ini. Dalam kode semu, generator baru mengikuti pola umum ini:

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>]

Ini memotong test case terpanjang hingga 140 detik, yang merupakan peningkatan konyol. Tetapi dari sini, masih ada beberapa hal yang perlu saya perbaiki. Saya mulai lebih agresif menyaring kode redundan / tidak berharga dan memeriksa untuk melihat apakah kode telah diuji sebelumnya. Ini mengurangi lebih jauh, tetapi itu tidak cukup. Pada akhirnya, bagian terakhir yang hilang adalah loop counter. Melalui algoritma saya yang sangat canggih (baca: trial and error acak ) saya menentukan bahwa rentang optimal untuk memungkinkan loop dijalankan adalah [3-8]. Tapi ada peningkatan besar di sana: Jika kita tahu itu [loop(8, [loop(8, ['F', loop(5, ['F', 'L'])]), 'L'])]tidak bisa menyelesaikan papan kita, maka sama sekali tidak mungkin[loop(3, [loop(8, ['F', loop(5, ['F', 'L'])]), 'L'])]atau hitungan loop apa pun dari 3-7 bisa menyelesaikannya. Jadi daripada mengulangi semua ukuran loop dari 3-8, kami mengatur jumlah loop pada loop luar ke max. Ini pada akhirnya memotong ruang pencarian turun dengan faktor maxLoop - minLoop, atau 6 dalam hal ini.

Ini banyak membantu, tetapi akhirnya menggembungkan skor. Solusi tertentu yang saya temukan sebelumnya dengan brute force membutuhkan jumlah loop yang lebih besar untuk dijalankan (misalnya, papan 4 dan 6). Jadi daripada mengatur jumlah loop luar menjadi 8, kami menetapkan jumlah loop luar menjadi 17, angka ajaib juga dihitung oleh algoritma saya yang sangat canggih. Kami tahu kami bisa melakukan ini karena meningkatkan jumlah loop dari loop terluar tidak berpengaruh pada validitas solusi. Langkah ini sebenarnya mengurangi skor akhir kita menjadi 13. Jadi bukan langkah sepele.