Program Robot Penumpukan Piala

36

Saya yakin semua orang telah melihat sebelumnya bahwa cangkir dapat ditumpuk menjadi piramida (dan bentuk lainnya):

           A    
        A A A   
 A     A A A A  
A A A A A A A A

Ya, Ajelas merupakan karakter yang memadai untuk mewakili piala.

Cangkir baru dapat ditambahkan baik di tanah, di sebelah kanan struktur, atau di atas dua cangkir yang berdekatan. Berikut adalah struktur di atas lagi, tetapi semua tempat yang tersedia untuk cangkir baru ditandai dengan _:

         _ A         
        A A A        
 A _ _ A A A A       
A A A A A A A A _ _ _

Katakanlah kita ingin membuat robot yang dapat merakit tumpukan piala ini. Robot akan memahami dua instruksi sederhana untuk memanipulasi struktur seperti itu:

  • a: Tambahkan cangkir baru di tempat pertama yang tersedia dalam urutan membaca kiri-ke-kanan (yaitu, memindai baris dari atas ke bawah, kiri ke kanan hingga Anda menemukan tempat yang tersedia, lalu tempatkan cangkir di sana). Contoh di atas akan menjadi:

             A A   
        A A A  
 A     A A A A 
A A A A A A A A

  • r: Lepaskan cangkir pertama dalam urutan membaca kiri-ke-kanan. Contoh di atas akan menjadi:

            A A A  
 A     A A A A 
A A A A A A A A

Ternyata setiap struktur dapat dibangun dari awal hanya dengan menggunakan dua operasi ini. Misalnya

      A
 A   A A
A A A A A

Dapat dibangun dengan urutan instruksi

aaaaaaaaaaaarrrrraa

Contoh yang lebih besar di atas dapat dibangun menggunakan

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaarrrrrrrrrrrrrrrrrraaaaaaarr

Inilah yang lebih besar:

    A
   A A                   A
  A A A     A   A       A A
 A A A A   A A A A     A A A A
A A A A A A A A A A   A A A A A

yang dapat dibangun dengan

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaarrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrraaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaarrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrraaaaaaaaaaaaaaaaaaarrrrrrrrrrrrrrraaaaaaaaaaaaaarrrrrrrrrrraaaaaaaa

Catatan: Jika bintik-bintik di tanah dilepaskan oleh instruksi pelepasan, mereka akan digunakan kembali sebelum menempatkan cangkir di sebelah kanan semua cangkir yang ada. Misalnya

aaaarrra

akan menghasilkan

A   A

tidak

    A A

Anda dapat menganggap tanah berada di atas deretan gelas semi tak terbatas.

Tantangan

Diberikan struktur gelas bertumpuk, kembalikan urutan yang mewakili instruksi untuk membangun struktur ini. Skor utama Anda adalah jumlah dari jumlah instruksi untuk kasus uji yang disediakan di bagian bawah. Dalam hal terjadi seri (yang kemungkinan besar, karena saya yakin bahwa solusi optimal yang efisien dimungkinkan), solusi terpendek akan menang.

Berikut ini beberapa detail tentang aturan:

  • Anda mungkin berasumsi bahwa tidak ada spasi di baris paling bawah dari input, sehingga titik tanah paling kiri untuk cawan selalu digunakan.
  • Anda dapat mengasumsikan jumlah ruang trailing yang masuk akal (tidak ada ruang, satu ruang, empuk ke persegi panjang, empuk ke persegi panjang dengan ruang trailing tunggal).
  • Anda dapat secara opsional mengharapkan input berakhir dalam satu baris baru.
  • Anda dapat memilih dua karakter ASCII yang dapat dicetak yang berbeda (0x20 hingga 0x7E, inklusif) dan bukan Aspasi (aturan tentang spasi lalu transfer ke karakter yang Anda pilih).
  • Keluaran Anda harus mengandung hanya dua karakter berbeda yang mewakili operasi (Anda dapat memilih karakter selain adan r). Anda dapat secara opsional mencetak satu baris baru.
  • Kode Anda harus dapat menyelesaikan semua kasus uji di bawah ini dalam waktu kurang dari satu menit pada PC desktop yang wajar (jika saya membutuhkan dua menit, saya akan memberi Anda manfaat keraguan, tetapi jika butuh sepuluh, saya menang 't - Saya percaya algoritma optimal dimungkinkan yang memecahkan salah satu dari mereka dalam waktu kurang dari satu detik).
  • Anda tidak boleh mengoptimalkan kode Anda terhadap setiap kasus uji (mis. Dengan meng-hardcodenya). Jika saya curiga ada yang melakukannya, saya berhak mengubah kasus uji.

Anda dapat menggunakan skrip CJam ini untuk operasi terbalik: ini akan mengambil serangkaian instruksi pembuatan dan mencetak tumpukan cangkir yang dihasilkan. (Terima kasih kepada Dennis karena menulis ulang cuplikan dan mempercepatnya secara signifikan.)

Sp3000 juga menyediakan skrip Python alternatif ini untuk tujuan yang sama.

Uji Kasus

Setelah setiap kasus uji, ada angka yang menunjukkan jumlah instruksi optimal sesuai jawaban Ell.

                                       A
                                      A A
                                     A A A
                                    A A A A
                                   A A A A A
                                  A A A A A A
                                 A A A A A A A
                                A A A A A A A A
                               A A A A A A A A A
                              A A A A A A A A A A
                             A A A A A A A A A A A
                            A A A A A A A A A A A A
                           A A A A A A A A A A A A A
                          A A A A A A A A A A A A A A
                         A A A A A A A A A A A A A A A
                        A A A A A A A A A A A A A A A A
                       A A A A A A A A A A A A A A A A A
                      A A A A A A A A A A A A A A A A A A
                     A A A A A A A A A A A A A A A A A A A
                    A A A A A A A A A A A A A A A A A A A A
                   A A A A A A A A A A A A A A A A A A A A A
                  A A A A A A A A A A A A A A A A A A A A A A
                 A A A A A A A A A A A A A A A A A A A A A A A
                A A A A A A A A A A A A A A A A A A A A A A A A
               A A A A A A A A A A A A A A A A A A A A A A A A A
              A A A A A A A A A A A A A A A A A A A A A A A A A A
             A A A A A A A A A A A A A A A A A A A A A A A A A A A
            A A A A A A A A A A A A A A A A A A A A A A A A A A A A
           A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
          A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
         A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
        A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
       A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
      A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
     A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
    A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
   A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
  A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
 A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A

820
                                             A
                                            A A
                                           A A A
                                          A A A A
                                         A A A A A
                                        A A A A A A
                                       A A A A A A A
                                      A A A A A A A A
                     A               A A A A A A A A A
                    A A             A A A A A A A A A A
                   A A A           A A A A A A A A A A A
                  A A A A         A A A A A A A A A A A A
         A       A A A A A       A A A A A A A A A A A A A
        A A     A A A A A A     A A A A A A A A A A A A A A
   A   A A A   A A A A A A A   A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A

1946

               A
              A A
             A A A
            A A A A
           A A A A A
          A A A A A A
         A A A A A A A
        A A A A A A A A
       A A A A A A A A A               A
      A A A A A A A A A A             A A
     A A A A A A A A A A A           A A A
    A A A A A A A A A A A A         A A A A
   A A A A A A A A A A A A A       A A A A A       A
  A A A A A A A A A A A A A A     A A A A A A     A A
 A A A A A A A A A A A A A A A   A A A A A A A   A A A   A
A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A

2252

                                                         A A
                                                      A A A A
                                                   A A A A A A
                                                A A A A A A A A
                                             A A A A A A A A A A
                                          A A A A A A A A A A A A
                                       A A A A A A A A A A A A A A
                                    A A A A A A A A A A A A A A A A
                                 A A A A A A A A A A A A A A A A A A
                              A A A A A A A A A A A A A A A A A A A A
                           A A A A A A A A A A A A A A A A A A A A A A
                        A A A A A A A A A A A A A A A A A A A A A A A A
                     A A A A A A A A A A A A A A A A A A A A A A A A A A
                  A A A A A A A A A A A A A A A A A A A A A A A A A A A A
               A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
            A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
         A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
      A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
   A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A

9958

                   A A
                  A A A A
                 A A A A A A
                A A A A A A A A
               A A A A A A A A A A
              A A A A A A A A A A A A
             A A A A A A A A A A A A A A
            A A A A A A A A A A A A A A A A
           A A A A A A A A A A A A A A A A A A
          A A A A A A A A A A A A A A A A A A A A
         A A A A A A A A A A A A A A A A A A A A A A
        A A A A A A A A A A A A A A A A A A A A A A A A
       A A A A A A A A A A A A A A A A A A A A A A A A A A
      A A A A A A A A A A A A A A A A A A A A A A A A A A A A
     A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
    A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
   A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
  A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
 A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A

5540

A   A   A   A   A   A   A   A   A   A   A   A   A   A   A   A   A   A   A   A

10280

 A   A   A   A   A   A   A   A   A   A   A   A   A   A   A   A   A   A   A   A
A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A

10320

   A       A       A       A       A       A       A       A       A       A
  A A     A A     A A     A A     A A     A A     A A     A A     A A     A A
 A A A   A A A   A A A   A A A   A A A   A A A   A A A   A A A   A A A   A A A
A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A

5794

              A
             A A
            A A A
           A A A A                                               A
          A A A A A                                             A A
         A A A A A A A                                         A A A
        A A A A A A A A               A                       A A A A
       A A A A A A A A A             A A             A       A A A A A   A
      A A A A A A A A A A           A A A           A A     A A A A A A A A
     A A A A A A A A A A A         A A A A         A A A   A A A A A A A A A
    A A A A A A A A A A A A       A A A A A       A A A A A A A A A A A A A A
 A A A A A A A A A A A A A A     A A A A A A     A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A   A A A A A A A   A A A A A A A A A A A A A A A A

3297

                                                   A A
                                                  A A A
                                                 A A A A
                                                A A A A A
                                               A A A A A A
                                              A A A A A A A
                                             A A A A A A A A
                                            A A A A A A A A A
                                           A A A A A A A A A A     A
                                          A A A A A A A A A A A   A A
                                       A A A A A A A A A A A A A A A A
                                      A A A A A A A A A A A A A A A A A
                                     A A A A A A A A A A A A A A A A A A
      A                             A A A A A A A A A A A A A A A A A A A
     A A                           A A A A A A A A A A A A A A A A A A A A
    A A A             A A         A A A A A A A A A A A A A A A A A A A A A
   A A A A           A A A       A A A A A A A A A A A A A A A A A A A A A A
  A A A A A         A A A A     A A A A A A A A A A A A A A A A A A A A A A A
 A A A A A A     A A A A A A   A A A A A A A A A A A A A A A A A A A A A A A A
A A A A A A A   A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A

4081

                      A
                     A A       A                     A
                    A A A     A A                   A A A                 A
             A     A A A A   A A A A               A A A A     A         A A
  A         A A   A A A A A A A A A A         A   A A A A A   A A       A A A
 A A       A A A A A A A A A A A A A A       A A A A A A A A A A A     A A A A
A A A   A A A A A A A A A A A A A A A A     A A A A A A A A A A A A   A A A A A

4475

                                                             A              
      A           A                       A                 A A A   A       A
     A A         A A   A         A A     A A A   A         A A A A A A     A A
A   A A A A A   A A A A A   A   A A A   A A A A A A   A   A A A A A A A   A A A

5752

Itu artinya, skor terbaik adalah 64.515 instruksi.

metagolf hexagonal-grid Martin Ender
sumber

Jawaban:

32

Python 2, 64.515

import sys

input = map(str.rstrip, sys.stdin.readlines())
width = (len(input[-1]) + 1) / 2
for i in range(len(input)):
    indent = len(input) - i - 1
    input[i] = [c != " " for c in input[i][indent::2]]
    input[i] += [False] * (width - indent - len(input[i]))
input = [[False] * n for n in range(width - len(input) + 1)] + input
working_area = [[False] * n for n in range(width + 1)]

def add():
    sys.stdout.write("a")
    for row in range(width + 1):
        for i in range(row):
            if not working_area[row][i] and (
                row == width or
                (working_area[row + 1][i] and working_area[row + 1][i + 1])
            ):
                working_area[row][i] = True
                return
def remove():
    sys.stdout.write("r")
    for row in range(width + 1):
        if True in working_area[row]:
            working_area[row][working_area[row].index(True)] = False
            return

for row in range(width, -1, -1):
    r = input[row]; R = working_area[row]
    for i in range(len(r) - 1, -1, -1):
        if r[i]:
            while not R[i]: add()
        else:
            while R[i]: remove()

Hasil

Tes 1 # 1 - 820   # 2 - 1.946 # 3 - 2.252 # 4 - 9.958 # 5 - 5.540 # 6 - 10.280 # 7 - 10.320 # 8 - 5.794 # 9 - 3.297 # 10 - 4.081 # 11 - 4.475 # 12 - 5.752Tes 2   Tes 3
Tes 4   Tes 5   Tes 6
Tes 7   Tes 8   Tes 9
Tes 10   Tes 11   Tes 1 2

Total 64.515

Penjelasan

Kita mulai dengan "area kerja" kosong. Kami memindai input dalam urutan pembacaan terbalik , yaitu kanan-ke-kiri dan bawah-ke-atas. Jika ada ketidaksesuaian antara input dan area kerja di lokasi saat ini (yaitu, ada cangkir di input tetapi tidak di area kerja, atau sebaliknya,) kami menambahkan, atau menghapus, cangkir ke area kerja, sesuai untuk aturan, sampai ketidakcocokan diselesaikan, pada titik mana kami melanjutkan ke lokasi berikutnya.

Kebenaran

Untuk menunjukkan bahwa metode ini benar, yaitu, bahwa urutan yang dihasilkan menghasilkan struktur input, cukup untuk menunjukkan bahwa kami tidak pernah memodifikasi (yaitu, menambah atau menghapus cangkir di) lokasi yang telah kami kunjungi (karena, di setiap lokasi yang kami kunjungi , kami memastikan bahwa area kerja cocok dengan input.) Ini adalah konsekuensi mudah dari kenyataan bahwa kami bekerja dalam urutan terbalik di mana cangkir ditambahkan dan dilepas:

  • Gelas di lokasi l akan selalu dilepas sebelum gelas di lokasi yang berhasil l dalam urutan membaca, dan karena itu, yang mendahului l dalam urutan pemindaian, maka tidak ada bahaya menghapus cawan yang telah kita kunjungi.
  • Demikian pula, cangkir di lokasi l akan selalu ditambahkan sebelum cangkir yang mendahuluinya dalam urutan pemindaian, mengingat sudah ada dua cangkir di bawahnya (atau bahwa itu di bagian bawah); namun, karena kita akan sudah mengunjungi lokasi-lokasi ini, dan karenanya menambahkan cangkir yang diperlukan, dan karena, sebagaimana disebutkan di atas, tidak ada bahaya nanti setelah melepas cangkir itu, kondisi ini terpenuhi, dan dengan demikian tidak ada bahaya menambahkan cangkir di lokasi yang sudah kami kunjungi.

Optimalitas

Perhatikan bahwa efek menambahkan, atau menghapus, cawan dari suatu struktur tidak tergantung pada urutan operasi yang digunakan untuk menghasilkan struktur, hanya pada konfigurasi saat ini. Sebagai hasilnya, diberi urutan optimal S n = { s 1 , ..., s n } operasi yang menghasilkan struktur tertentu, setiap segmen awal S n , yaitu, setiap urutan S m = { s 1 , .. ., s m }, di mana m ≤ n , juga merupakan urutan optimal, untuk struktur yang dihasilkannya, atau akan ada urutan yang lebih pendek dari S n, menghasilkan struktur yang sama.

Kami dapat menunjukkan bahwa metode kami optimal dengan induksi pada panjang urutan pembangkitan optimal: Metode kami jelas menghasilkan urutan optimal untuk setiap struktur yang urutan pembangkit optimalnya kosong (hanya ada satu struktur seperti itu — struktur kosong.) Misalkan kita Metode menghasilkan urutan optimal untuk semua struktur yang urutan optimal (atau urutan) adalah panjang n , dan mempertimbangkan struktur yang dihasilkan oleh urutan optimal S n +1 . Kami ingin menunjukkan bahwa, mengingat struktur yang dihasilkan oleh S n +1 sebagai input, metode kami menghasilkan urutan yang sama (atau, setidaknya, urutan dengan panjang yang sama.)

Seperti disebutkan di atas, S n juga merupakan urutan optimal, dan dengan demikian, dengan hipotesis, metode kami menghasilkan urutan optimal mengingat struktur yang dihasilkan oleh S n sebagai input. Misalkan, tanpa kehilangan keumuman, bahwa S n adalah urutan yang dihasilkan oleh metode kami (jika tidak, kami selalu dapat mengganti elemen n pertama dari S n +1 dengan urutan tersebut, dan mendapatkan urutan panjang n + 1 yang menghasilkan struktur yang sama.) Biarkan l menjadi lokasi yang diubah oleh operasi terakhir di S n +1 (yaitu, s n +1 ), dan biarkanS m menjadi segmen awal S n , yang akan diproduksi program kami setelah mencapai l (tetapi sebelum memproses l ). Perhatikan bahwa, karena struktur yang dihasilkan oleh S n dan S n +1 setuju di semua lokasi yang mengikuti l , dalam urutan pembacaan, S m adalah sama dengan struktur yang diberikan sebagai input.

Jika s n +1 adalah a(yaitu, penambahan cawan), maka tidak boleh ada lokasi sebelumnya l , dalam urutan pembacaan, di mana cawan dapat ditambahkan ke struktur yang dihasilkan oleh S n . Akibatnya, urutan S n mengikuti S m harus semuanya a(karena rakan menyiratkan bahwa ada ruang kosong sebelum l , atau bahwa S n tidak optimal.) Ketika kita datang ke proses l , kita perlu tambahkan persis n - m gelas sebelum kita dapat menambahkan cangkir di l , maka urutan yang dihasilkan adalah Sm , diikuti oleh n - m + 1aelemen, yang sama dengan S n +1 (tidak akan ada ketidakcocokan setelah titik ini, maka ini adalah urutan lengkap yang dihasilkan.)

Demikian juga, jika s n +1 adalah r, maka tidak boleh ada cangkir di lokasi sebelumnya l , dalam urutan membaca, dalam struktur yang dihasilkan oleh S n . Akibatnya, urutan S n setelah S m harus semuanya r. Ketika kita sampai pada proses l , kita harus menghapus persis n - m gelas sebelum kita dapat menghapus cangkir di l , maka urutan yang dihasilkan adalah S m , diikuti oleh n - m + 1 relemen, yang lagi sama dengan S n +1 .

Dengan kata lain, metode kami menghasilkan urutan optimal untuk struktur input tersebut, dan oleh karena itu, dengan induksi, untuk setiap struktur input.

Perhatikan bahwa ini tidak berarti bahwa implementasi ini adalah yang paling efisien. Misalnya, sangat mungkin untuk menghitung jumlah cangkir yang harus ditambahkan, atau dihilangkan, pada setiap titik secara langsung, daripada benar-benar melakukan operasi ini.

Keunikan

Kita dapat menggunakan optimalitas metode kita untuk menunjukkan bahwa urutan optimal, pada kenyataannya, unik (yaitu, bahwa tidak ada dua urutan optimal berbeda menghasilkan struktur yang sama.) Kami menggunakan, sekali lagi, induksi pada ukuran urutan pembangkit optimal: Urutan kosong jelas merupakan urutan pembangkitan optimal unik dari struktur kosong. Misalkan semua urutan pembangkitan optimal panjang n adalah unik, dan pertimbangkan struktur, Σ, yang dihasilkan oleh dua urutan optimal S n +1 dan T n +1 .

Ingat bahwa S n dan T n sendiri optimal, dan oleh karena itu, dengan hipotesis, unik. Karena metode kami menghasilkan urutan optimal, S n dan T n dapat dianggap sebagai dihasilkan oleh metode kami. Misalkan l S dan l T adalah lokasi yang dimodifikasi oleh operasi terakhir di S n +1 dan T n +1 , masing-masing, dan anggaplah, tanpa kehilangan generalitas, bahwa l S mengikuti, atau sama dengan, l T dalam urutan pembacaan. Karena struktur yang dihasilkan oleh S ndan T n setuju di semua lokasi berikut l S , dalam urutan pembacaan, urutan yang dihasilkan oleh metode kami, diberikan salah satu struktur sebagai input, setelah mencapai l S (tetapi sebelum memprosesnya), adalah sama untuk keduanya; sebut urutan ini U .

Karena aksi terakhir S n +1 memodifikasi l S , jika Σ memiliki piala di l S maka tidak boleh ada lowongan sebelum l S , dan jika Σ tidak memiliki piala di l S maka tidak boleh ada cangkir sebelum l S , dalam urutan membaca. Oleh karena itu, sisa rangkaian urutan Σ, mengikuti U , harus terdiri dari aplikasi berulang dari instruksi yang sama, yang ditentukan oleh ada atau tidak adanya cangkir pada l S (atau kalau tidak itu tidak akan optimal). Dengan kata lain, S n +1 dan T n +1adalah sama (keduanya dimulai dengan U , dan diakhiri dengan urutan kata dari instruksi yang diulang,) yaitu, urutan pembangkitan optimal Σ adalah unik, dan dengan induksi, semua urutan pembangkitan optimal adalah unik.

Elo
sumber