Dalam permainan sudoku, banyak pemain suka "memasukkan" angka-angka yang mungkin ada di setiap kotak:
Baris di atas dapat direpresentasikan sebagai array:
[[1,2,9], [6], [5], [7], [1,2,9], [1,2,9], [3], [1,2,4], [8]]
Sekarang, perhatikan bahwa hanya ada 1 tempat di mana 4
bisa pergi. Ini secara efektif memungkinkan kita menyederhanakan daftar di atas menjadi:
[[1,2,9], [6], [5], [7], [1,2,9], [1,2,9], [3], [4], [8]]
Tujuan dari tantangan ini adalah untuk mengambil daftar nomor yang mungkin dalam permutasi, dan menyimpulkan kemungkinan yang dapat dihilangkan .
Sebagai contoh lain, katakanlah Anda memiliki berbagai kemungkinan berikut:
[[0,1,3], [0,2,3], [1,2], [1,2]]
Dua tempat terakhir harus diisi dengan 1 dan 2. Oleh karena itu, kita dapat menghapus kemungkinan itu dari dua elemen pertama dalam array:
[[0,3], [0,3], [1,2], [1,2]]
Sebagai contoh lain:
[[0,1,2,3], [0,2], [0,2], [0,2]]
Tidak mungkin untuk membangun permutasi dari kemungkinan di atas, karena hanya ada 1 lokasi untuk keduanya 1
dan 3
, dan Anda ingin mengembalikan array kosong.
Anda perlu memasukkan daftar kemungkinan dan menampilkan kemungkinan yang tersisa setelah jumlah maksimum kemungkinan telah dieliminasi.
- Jika array tertentu tidak mungkin, Anda harus mengembalikan array kosong, atau array di mana salah satu sub-array kosong.
- Anda dapat mengasumsikan bahwa array akan terbentuk dengan baik, dan memiliki setidaknya 1 elemen.
- Diberikan array ukuran
N
, Anda dapat menganggap angka-angka dalam subarray akan selalu berada dalam kisaran[0:N)
, dan ituN <= 10
- Anda tidak boleh berasumsi bahwa setiap nomor dari
0
hinggaN-1
akan ada - Anda dapat berasumsi bahwa angka-angka dalam satu subarray unik.
- Jika sebuah subarray hanya berisi satu kemungkinan, Anda bisa mewakili kemungkinan itu dalam sebuah array atau dengan sendirinya.
[[1],[2],[0]]
,[1,2,0]
,[[1,2],0,[1,2]]
Semuanya valid. - Anda dapat menerima array baik dalam format string yang masuk akal atau dalam format daftar / array.
- Subarrays bisa dalam urutan apa pun.
- Alih-alih berurusan dengan array kasar, Anda dapat mengisi tempat kosong dengan
-1
.
Uji kasus
[[0]] -> [[0]]
[[1],[0]] -> [[1],[0]]
[[1],[1]] -> []
[[1],[0,1]] -> [[1],[0]]
[[0,1,2],[1,2],[1,2]] -> [[0],[1,2],[1,2]]
[[0,1],[1,2],[0,2]] -> [[0,1],[1,2],[0,2]]
[[2,1],[1,2],[1,2]] -> []
[[0,3],[2,1],[3,0],[3,2]] -> [[0,3],[1],[0,3],[2]]
[[0,1],[0,1],[2,3],[2,3,0]] -> [[0,1],[0,1],[2,3],[2,3]]
[[0,1],[0,3],[3,2],[0]] -> [[1],[3],[2],[0]]
[[3,5,2],[0,2,4],[4,0],[0,1,3,5],[2,1],[2,4]] -> [[3,5],[0,2,4],[4,0],[3,5],[1],[2,4]]
[[6,9,8,4],[4,5],[5,3,6],[3,8,6,1,4],[3,1,9,6],[3,7,0,2,4,5],[9,5,6,8],[6,5,8,1,3,7],[8],[8,0,6,2,5,6,3]] -> [[6,9,4],[4,5],[5,3,6],[3,6,1,4],[3,1,9,6],[0,2],[9,5,6],[7],[8],[0,2]]
[[3,5,0],[5,7],[5,1,2],[1,3,0],[5,3],[5,0],[5,3,7,8,0,6],[7,5,0,1,8],[1,0,8],[0,6]] -> []
[[9,0,2,3,7],[0,7,6,5],[6,9,4,7],[9,1,2,3,0,5],[2,8,5,7,4,6],[6,5,7,1],[5,9,4],[5,9,3,8,1],[5,0,6,4],[0,7,2,1,3,4,8]] -> [[9,0,2,3,7],[0,7,6,5],[6,9,4,7],[9,1,2,3,0,5],[2,8,5,7,4,6],[6,5,7,1],[5,9,4],[5,9,3,8,1],[5,0,6,4],[0,7,2,1,3,4,8]]
[[2,6,0],[0,4,3],[0,6,2],[0,7],[0,9,2,3,6,1,4],[1,7,2],[2,7,8],[8,6,7],[6,5,2,8,0],[5,8,1,4]] -> [[2,6,0],[3],[0,6,2],[0,7],[9],[1],[2,7,8],[8,6,7],[5],[4]]
[[8],[8,0,6,5,7,2,4,1],[8,6,9,3,5,0,7],[3,9,1,0],[9],[9,2,6],[2,8,3],[3,1,6,8,2],[6],[6,4,5,3,0,7]] -> [[8],[5,7,4],[5,7],[0],[9],[2],[3],[1],[6],[4,5,7]]
[[8,1,0],[5,8,7,6,2,0],[6,8,2],[2,4,0,9],[4,1,7,3,6,8],[8,1],[8,0,3],[0,8,2],[0,8,3],[1,8,0]] -> []
Ini adalah kode-golf jadi buat jawaban Anda sesingkat mungkin!
sumber
Jawaban:
Brachylog , 21 byte
Cobalah online!
Cobalah online!
Predikat 0 (predikat utama)
Predikat 1 (predikat bantu 1)
Predikat 2 (predikat bantu 2)
sumber
Jelly , 10 byte
Cobalah online!
sumber
Pyth , 11 byte
Cobalah online!
sumber
Haskell, 100 byte
sumber
and.flip(zipWith elem)z
lebih pendekSebenarnya , 27 byte
Cobalah online!
sumber
Python 3,
10199 byteBerkat @TLW untuk -2 byte
Fungsi anonim yang mengambil input melalui argumen dari daftar daftar dan mengembalikan daftar set.
Bagaimana itu bekerja
Cobalah di Ideone
sumber
list(map(set,
lebih pendek, saya pikirMathematica, 46 byte
sumber
PHP,
245231 byte131117 untuk fungsi produk kartesius, 114 untuk hal-hal lainSaya mengalami masalah memori pada beberapa kasus uji, dengan fungsi rekursif untuk produk kartesius. Bekerja lebih baik dengan kelas generator ini dan
function c($a){$b=[];foreach($a as$i)$b[]=new \ArrayIterator($i);return new CartesianProductIterator($b);}
.Tetapi generator saya lebih pendek dan melakukan pekerjaan yang sama.
Contoh-contoh yang lebih besar, bagaimanapun, menghasilkan Kesalahan Server Internal (baik dengan iterator dan generator) setelah beberapa saat di mesin saya. Sayangnya, saat ini tidak ada waktu untuk memeriksa log server.
sumber