Bangun pemecah freecell dengan gerakan paling sedikit

54

Dalam permainan Freecell, Anda ditugasi membangun empat tiang pondasi yang sesuai dari kartu as ke raja, pada tata letak tempat Anda membangun ke bawah dengan warna bergantian. Namun, Anda hanya dapat membuat satu kartu pada satu waktu, sehingga Anda diberikan empat "sel bebas" yang masing-masing dapat berisi satu kartu untuk membantu Anda memindahkan seluruh urutan. Idenya adalah Anda menenun kartu individual masuk dan keluar dari sel gratis seperti yang diperlukan untuk membantu Anda memecahkan permainan.

Tugas Anda adalah membangun program yang akan menyelesaikan permainan ini dalam gerakan sesedikit mungkin.

Program Anda akan mengambil sebagai input urutan 52 kartu, dalam format berikut:

2S 9H 10C 6H 4H 7S 2D QD KD QC 10S AC ...

Yang akan dibahas dalam tata letak awal dalam urutan ini:

01 02 03 04 05 06 07 08
09 10 11 12 13 14 15 16
17 18 19 20 21 22 23 24
25 26 27 28 29 30 31 32
33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48
49 50 51 52

Dan kembalikan daftar langkah untuk menyelesaikan permainan. Setiap langkah akan berada dalam format ini:

  • Nomor yang mewakili nomor tumpukan ( 1melalui 8), atau sel bebas ( Ake D), mewakili tumpukan sumber.
  • Nomor atau surat lain yang mewakili tumpukan tujuan atau sel bebas, atau Funtuk fondasi setelan itu.

Outputnya akan terlihat seperti ini:

18 28 3A 8B 8C 85 B5 35 4F etc.

Setelah kartu dimasukkan ke dalam fondasi, itu tidak dapat dihapus. Karena hanya satu kartu yang dipindahkan pada satu waktu, memindahkan urutan 3 kartu membutuhkan 5 gerakan, dan urutan 5 kartu membutuhkan 9 gerakan.

Jika sebuah game tidak dapat dipecahkan, program Anda harus menunjukkannya. Namun, program Anda harus dapat menyelesaikan permainan yang dapat dipecahkan.

Program Anda akan dinilai berdasarkan 32.768 penawaran yang ditemukan dalam program Microsoft FreeCell asli. Agar valid, program Anda harus berhasil menyelesaikan setiap transaksi kecuali kesepakatan # 11.982 , yang tidak dapat dipecahkan. Skor Anda akan menjadi jumlah total gerakan yang diperlukan untuk menyelesaikan 32.767 kesepakatan ini, dengan kode yang lebih pendek menjadi tie-breaker.


File dengan semua deck dalam format yang diperlukan oleh spesifikasi di atas tersedia untuk diunduh di sini (file 5,00 MB): https://github.com/joezeng/pcg-se-files/raw/master/freecell_decks

Joe Z.
sumber
1
Sekarang saya hanya perlu menangkap generator angka acak yang mereka gunakan untuk menghasilkan 32.768 game tersebut. : S
Joe Z.
3
Generator ada di sini: rosettacode.org/wiki/Deal_cards_for_FreeCell
nutki
1
Itu poin yang bagus. Bagaimana Anda menangani kasus di mana, katakanlah, dua kartu dengan warna dan nomor yang sama (seperti 7C dan 7S) keduanya dalam sel bebas? Kemudian jika Anda pindah dari "C" ke kartu hitam 8, itu bisa salah satu dari dua kartu itu.
Joe Z.
2
Anda mungkin bisa mendapatkan beberapa jawaban dengan menghapus batasan bahwa semua transaksi yang harus diselesaikan harus diselesaikan dengan pengiriman. Kemudian, skor berdasarkan jumlah kesepakatan diselesaikan, kemudian dengan langkah paling sedikit.
mbomb007
1
dapatkah kartu diindeks 0?
tuskiomi

Jawaban:

22

C 64.643 byte, Skor: ~ 6,5 juta

Cuplikan Stack berikut (milik Mego) menampilkan semua kode sebagai file C tunggal yang berdiri sendiri:

Unduh sumber aslinya di sini . Gunakan GCC dan jalankan makekemudian gunakan pedoman di readme.

Pemformatan saya buruk (semua file berbeda berada dalam satu blok kode) dan ini bisa di-golf lebih banyak (12k byte tho). Bantuan apa pun akan dicintai!

Beberapa kode bukan milik saya. Saya menggunakannya dari sumber yang tidak dilindungi hak cipta. Namun saya tetap metode input / output berada dalam tantangan (tugas panjang karena saya mengerikan di C (jam 5ish)). Saya juga harus menulis ulang banyak kode dan men-debug semuanya. Terima kasih banyak kepada Ayah saya karena telah membantu dan menjadi bebek karet (dan menunjukkan kesalahan manajemen ingatan saya) dan untuk semua orang di TNB yang berurusan dengan kemarahan saya tentang segfaults dan C.

Christopher
sumber
Anda mungkin dapat menggunakan ini untuk mengatasi batasan panjang jawaban dan memiliki semua kode Anda dalam jawaban, daripada perlu mengunduh eksternal.
Mego
@Mego maksudku ya tetapi dalam beberapa file
Christopher
Sangat mudah untuk menggabungkan beberapa file C menjadi satu.
Mego
Berikut ini cuplikan tumpukan yang menunjukkan kode yang digabungkan menjadi satu file.
Mego
@ego, bisakah Anda mengeditnya? Di ponsel
Christopher