Bob diculik dan terjebak dalam labirin. Tugas Anda adalah membantunya menemukan jalan keluar. Tapi karena ini adalah labirin yang sangat gelap dan menakutkan, dia tidak bisa melihat apa pun. Dia hanya bisa merasakan dinding ketika dia berlari ke sana, dan tahu kapan dia menemukan pintu keluar, tetapi tidak tahu apa-apa lagi.

Karena dia harus menjalankan program Anda dengan memori, itu harus sesingkat mungkin.

Catatan: Saya mengambil masalah ini dari http://acmgnyr.org/year2016/problems.shtml , tetapi mengadaptasinya sedikit, dan menulis sendiri program hakim / uji kasus.

Spesifikasi

• Ini adalah masalah interaktif, jadi program Anda akan menampilkan perpindahan ke stdout, dan menerima tanggapan dari stdin.
• Anda Program kaleng keluaran salah satu langkah right, left, down, up.
• Maka akan mendapatkan sebagai masukan salah satu dari berikut ini:
  • wall- ini berarti Bob telah menabrak tembok. Bob akan tinggal di tempat yang sama.
  • solved- Bob telah menemukan pintu keluar! Program Anda sekarang juga harus keluar tanpa mencetak apa pun.
  • ok - Bob bisa bergerak ke arah yang diberikan.
• Jika labirin tidak memiliki jalan keluar, program Anda harus no exitmemberi tahu Bob bahwa ia harus menyerah. Program Anda kemudian harus keluar tanpa mencetak apa pun.
• Karena Bob sedang terburu-buru untuk keluar, program Anda seharusnya tidak membuat gerakan asing. Dengan kata lain, program Anda tidak diperbolehkan bergerak ke arah yang sama dari kotak yang sama dua kali .
• Ini kode-golf , jadi program tersingkat menang!

Contohnya

Dalam contoh berikut, Sadalah kotak awal, Xadalah pintu keluar, #adalah dinding, dan spasi adalah kotak yang valid. Karena tidak ada jawaban tunggal yang benar, ini hanyalah contoh dari solusi. Perhatikan juga bahwa gambar-gambar labirin ada di sana untuk Anda lihat, dan program Anda tidak akan mendapatkannya sebagai masukan.

########
#S     #
###### #
     # #
     #X#

right
              ok
right
              ok
right
              ok
right
              ok
right
              ok
right
              wall
down
              ok
right
              wall
down
              ok
right
              wall
down
              solved

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

right
              ok
right
              wall
down
              wall
up
              wall
left
              ok
down
              wall
up
              wall
left
              ok
down
              wall
up
              wall
left
              wall
right
              ok
no exit
              solved

###############################
#S                            #
##############       ###      #
             #       #X#      #
             #                #
             ##################

right
              ok
right
              ok
right
              ok
right
              ok
right
              ok
right
              ok
right
              ok
right
              ok
right
              ok
right
              ok
right
              ok
right
              ok
right
              ok
right
              ok
right
              ok
right
              ok
right
              ok
right
              ok
right
              ok
right
              ok
right
              ok
right
              ok
right
              ok
right
              ok
right
              ok
right
              ok
right
              ok
right
              ok
right
              wall
down
              ok
right
              wall
down
              ok
right
              wall
down
              ok
right
              wall
down
              wall
left
              ok
down
              wall
up
              ok
up
              ok
left
              ok
down
              ok
down
              ok
down
              wall
left
              ok
down
              wall
up
              ok
up
              ok
left
              ok
down
              ok
down
              ok
down
              wall
left
              ok
down
              wall
up
              ok
up
              ok
left
              wall
down
              ok
left
              wall
down
              ok
left
              ok
down
              wall
up
              wall
left
              ok
down
              wall
up
              solved

Program Pemeriksa

• Saya telah menulis pemeriksa solusi dengan Python. Anda dapat menemukannya di https://gist.github.com/Maltysen/f0186019b3aa3812d812f8bb984fee19 .
• Jalankan seperti python mazechecker.py ./mazesolver.
• Ini akan menguji program Anda di semua labirin di folder bernama mazes.
• Labirin berada di file terpisah dalam format yang sama dari atas.
• Ia memeriksa semua kondisi yang tercantum di atas, dan memberi tahu Anda jika solusi Anda melanggar.
• Anda dapat memilikinya mencetak info diagnostik tambahan dengan python mazechecker.py -d ./mazesolver.
• Anda dapat menemukan mazesfolder zip di sini . Anda juga dapat menambahkan milik Anda sendiri jika mau.

JavaScript (ES6),  180  174 byte

Menggunakan prompt()untuk mengeluarkan arah dan mengambil hasilnya.

_=>(g=p=>[...'012301234'].some((d,i)=>g[p]>>d&1|i<4&g[P=[p[0]+(d-2)%2,p[1]+~-d%2]]>0?0:(r=prompt('up/left/down/right/no exit'.split`/`[g[p]|=1<<d,d]))<'s'?g(P):r<'t'))([0,0])

Cobalah online! (dengan I / O otomatis)

Cuplikan interaktif

PERINGATAN : kode ini akan menampilkan dialog prompt () sampai 'dipecahkan' dimasukkan atau fungsi menunjukkan bahwa tidak ada jalan keluar sama sekali.

(
_=>(g=p=>[...'012301234'].some((d,i)=>g[p]>>d&1|i<4&g[P=[p[0]+(d-2)%2,p[1]+~-d%2]]>0?0:(r=prompt('up/left/down/right/no exit'.split`/`[g[p]|=1<<d,d]))<'s'?g(P):r<'t'))([0,0])
)()

Berkomentar

_ => (                      // anonymous function taking no argument
  g = p =>                  // g = recursive function taking the current position p = [x, y]
    [ ...'0123',            // i<4  : try to move on squares that haven't been visited yet
      ...'0123',            // 3<i<8: try to go back to where we initially came from
      ...'4'                // i=8  : if everything failed, there must be no exit
    ].some((d, i) =>        // for each direction d at index i:
      g[p] >> d & 1         //   if this direction was already tried at this position
      | i < 4 &             //   or i is less than 4 and
      g[P = [               //   the square at the new position P = [X, Y] with:
        p[0] + (d - 2) % 2, //     X = x + dx[d]
        p[1] + ~-d % 2      //     Y = y + dy[d]
      ]] > 0 ?              //   was already visited:
        0                   //     abort
      : (                   //   else:
        r = prompt(         //     output the direction:
          [ 'up',           //       0 = up
            'left',         //       1 = left
            'down',         //       2 = down
            'right',        //       3 = right
            'no exit'       //       4 = no exit
          ][                //
            g[p] |= 1 << d, //       mark this direction as used
            d               //       d = actual index of the string to output
          ]                 //     r = result of prompt()
        )                   //
      ) < 's' ?             //     if r = 'ok':
        g(P)                //       do a recursive call at the new position
      :                     //     else:
        r < 't'             //       yield true if r = 'solved' or false if r = 'wall'
    )                       // end of some()
)([0, 0])                   // initial call to g at (0, 0)