Pengujian Primality di Manufactoria

13

Latar Belakang

Manufactoria adalah game tentang pemrograman. Pemain harus menggunakan bentuk bahasa pemrograman dua dimensi untuk menyelesaikan tugas. Jika Anda belum pernah mendengarnya, cara termudah untuk belajar adalah mencoba beberapa level pertama dalam permainan.

Tantangan

Tantangan Anda adalah membuat program yang menguji keutamaan angka.

Input akan berupa serangkaian penanda biru N dalam antrian. Jika N adalah prima, maka program Anda harus menerimanya (pindahkan robot ke garis finish). Jika N adalah komposit, maka program Anda harus menolaknya (letakkan di lantai di suatu tempat).

Opsi Pengiriman

Karena ini adalah tantangan yang lebih kompleks daripada tantangan Manufactoria biasa, saya telah memutuskan untuk mengizinkan lebih banyak cara untuk mengirimkan jawaban Anda.

Vanila

Saya telah membuat tingkat kustom 13x13 untuk membuat dan menguji pengiriman. Level pengujian khusus adalah sebagai berikut.

Tingkat kustom 13x13

Gim ini hanya memungkinkan 8 kasus uji pada tingkat khusus, tetapi kreasi Anda harus secara teoritis dapat menangani bilangan asli N, yang hanya dibatasi oleh memori yang tersedia. Untuk tujuan informasi, kasus uji yang disediakan di tingkat khusus adalah sebagai berikut:

1 -> reject
2 -> accept
4 -> reject
5 -> accept
7 -> accept
9 -> reject
11-> accept
15-> reject

Kotak yang Diperluas

Beberapa pengguna mungkin menginginkan lebih banyak ruang daripada kisi 13x13. Berikut ini tautan ke tingkat kustom dalam game 15x15, yang dibuat dengan mengubah angka di URL:

Tingkat kustom 15x15

Sayangnya, tingkat kustom yang lebih besar tidak berfungsi, karena sel-sel tambahan tidak dapat diakses.

The Manufactoria Esolang

Telah ada adaptasi Manufactoria ke dalam bahasa berbasis ASCII. Jika Anda ingin cara berbeda untuk merancang / menguji kreasi Anda, atau jika Anda tidak dapat memasukkan solusi akhir Anda ke papan permainan, Anda dapat menggunakan esolang ini. Anda dapat menemukan informasi tentang esolang ini di sini:

Manufactoria esolang

Ada beberapa perbedaan antara esolang dan gim yang sebenarnya. Misalnya, penyeberangan konveyor ditangani secara berbeda. Cobalah untuk menghindari mengambil keuntungan dari perbedaan ini.

Cara yang Lebih Cepat untuk Menguji

Gim ini sangat lambat ketika menyangkut program yang membutuhkan beberapa ribu langkah untuk diselesaikan. Solusi proof-of-concept saya mengambil 28042 langkah untuk menolak 15. Bahkan pada 50x speedup dalam game, itu hanya memakan waktu terlalu lama.

Saya menemukan situs web ini sangat membantu . Cukup salin dan tempel tautan ke jawaban Anda, dan Anda dapat menguji jawaban Anda dengan input spesifik. Proses 28042 langkah membutuhkan waktu satu detik.

Satu hal yang perlu diperhatikan adalah sering mengatakan sesuatu seperti "diterima dengan tidak benar" walaupun mesin Anda bekerja dengan baik. Ini karena laman web hanya mengetahui kasus uji. Misalnya, itu akan mengatakan bahwa solusi saya "salah menerima" nomor 3, meskipun mesin saya sebenarnya benar.

Bagaimana cara Menang

Kriteria penilaian adalah jumlah bagian (sel yang ditempati). Ini kode golf, jadi pengiriman dengan bagian paling sedikit menang.

Bagi mereka yang tertarik, solusi benchmark saya memiliki 96 bagian dan pas di grid 13x13. Menemukan algoritma yang lebih baik dapat mengarah pada peningkatan kolosal, karena saya tahu saya menggunakan algoritma sub-optimal.

PhiNotPi
sumber

Jawaban:

10

53 bagian - kotak 11x11

Saya baru belajar bermain Manufactoria 2 hari yang lalu, jadi mungkin ini bukan golf-dioptimalkan, tapi setidaknya itu memecahkan masalah. Ini mengimplementasikan pembagian percobaan tentu saja, melalui pengurangan berulang. Semua pembagi dari 2 hingga N-1 diperiksa. Kompleksitas waktu harus O (N ^ 3), saya percaya.

Solusi 53-potong

Tautan Solusi

Saya sangat kecewa harus menggunakan ban berjalan :)

feersum
sumber