Katakanlah Anda melihat teman Anda memasukkan kata sandi ke ponsel Android mereka. Anda tidak ingat bagaimana mereka membuat pola tetapi Anda ingat seperti apa pola itu. Menjadi teman yang peduli bahwa Anda adalah Anda ingin tahu seberapa aman kata sandi mereka. Tugas Anda adalah menghitung semua cara pola tertentu dapat dibuat.

Bagaimana pola kerja Android

Pola digambar pada kisi node 3x3. Dalam pola, seseorang mengunjungi serangkaian node tanpa pernah mengangkat jari mereka dari layar. Setiap node yang mereka kunjungi terhubung ke node sebelumnya dengan sebuah edge. Ada dua aturan yang perlu diingat.

• Anda tidak boleh mengunjungi satu simpul pun lebih dari sekali

• Edge mungkin tidak melewati simpul yang belum dikunjungi

Perhatikan bahwa, meskipun biasanya sangat sulit untuk dilakukan dan karenanya tidak terlalu umum dalam kombinasi kunci android asli, adalah mungkin untuk bergerak seperti Knight . Artinya, dimungkinkan untuk bergerak dari satu sisi ke sudut yang tidak berbatasan atau sebaliknya. Berikut adalah dua contoh pola yang menerapkan langkah tersebut:

Berikut adalah Gif animasi yang sedang dilakukan.

Memecahkan suatu pola

Pola khas mungkin terlihat seperti ini:

Dengan pola sederhana seperti ini ada dua cara dua menggambar pola. Anda dapat mulai dari salah satu dari dua ujung yang longgar dan bepergian melalui node yang disorot ke yang lain. Walaupun ini berlaku untuk banyak pola terutama yang biasanya digunakan manusia, ini tidak berlaku untuk semua pola.

Pertimbangkan pola berikut:

Ada dua solusi yang langsung dapat dikenali. Satu mulai di kiri atas:

Dan satu dimulai di tengah bawah:

Namun karena garis diizinkan melewati titik setelah telah dipilih ada pola tambahan yang dimulai di tengah atas:

Pola khusus ini memiliki 3 solusi tetapi pola dapat memiliki antara 1 dan 4 solusi ^[rujukan?] .

Berikut ini beberapa contoh masing-masing:

1.

2.

3.

4.

I / O

Suatu simpul dapat direpresentasikan sebagai bilangan bulat dari nol hingga sembilan inklusif, ekuivalen stringnya atau karakter dari a ke i (atau A ke I). Setiap node harus memiliki representasi unik dari salah satu set ini.

Suatu solusi akan diwakili oleh suatu wadah yang dipesan yang mengandung representasi simpul. Node harus dipesan dalam urutan yang sama dengan yang dilewati.

Suatu pola akan diwakili oleh suatu wadah pasangan node yang tidak berurutan. Setiap pasangan mewakili sisi mulai menghubungkan dua titik dalam pasangan. Representasi pola tidak unik.

Anda akan mengambil representasi pola sebagai input melalui metode input standar dan mengeluarkan semua solusi yang memungkinkan yang membuat pola yang sama melalui metode output standar.

Anda dapat mengasumsikan setiap input akan memiliki setidaknya satu solusi dan akan menghubungkan setidaknya 4 node.

Anda dapat memilih untuk menggunakan wadah yang dipesan sebagai pengganti wadah yang tidak dipesan, jika Anda menginginkannya atau dipaksa oleh pemilihan bahasa.

Uji Kasus

Dengan simpul yang diatur dalam pola berikut:

0 1 2
3 4 5
6 7 8

Membiarkan {...}menjadi wadah yang tidak teratur, [...]menjadi wadah yang teratur, dan (...)menjadi pasangan.

Input dan output berikut harus sesuai

{(1,4),(3,5),(5,8)} -> {[1,4,3,5,8]}
{(1,4),(3,4),(5,4),(8,5)} -> {[1,4,3,5,8]}
{(0,4),(4,5),(5,8),(7,8)} -> {[0,4,5,8,7],[7,8,5,4,0]}
{(0,2),(2,4),(4,7)} -> {[0,1,2,4,7],[1,0,2,4,7],[7,4,2,1,0]}
{(0,2),(2,6),(6,8)} -> {[0,1,2,4,6,7,8],[1,0,2,4,6,7,8],[8,7,6,4,2,1,0],[7,8,6,4,2,1,0]}
{(2,3),(3,7),(7,8)} -> {[2,3,7,8],[8,7,3,2]}
{(0,7),(1,2),(1,4),(2,7)} -> {[0,7,2,1,4],[4,1,2,7,0]}
{(0,4),(0,7),(1,3),(2,6),(2,8),(3,4),(5,7)} -> {[1,3,4,0,7,5,8,2,6]}
{(1,3),(5,8)} -> {}

Album imgur dari semua kasus uji sebagai gambar dapat ditemukan di sini . Pola ada dalam solusi biru berwarna merah.

Mencetak gol

Ini kode golf. Bytes paling sedikit menang.

Python 2.7, 493 430 byte

exec("L=['012','345','678','036','147','258','048','246'];L+=[i[::-1]IL];S=sorted;F=lambda t:''.join(str(i)It)\ndef N(x):\n s=' '.join(F(S(i))Ix)\nIL:s=s.replace(i[::2],i[:2]+' '+i[1:])\n return S(set(s.split()))\ndef P(s):\n e=0\nIL:e|=-1<s.find(i[::2])<s.find(i[1])\n return[zip(s[:-1],s[1:]),L][e]\nx=N(input());print[F(i)I__import__('itertools').permutations({iI`x`if i.isdigit()})if x==N(P(F(i)))]".replace('I',' for i in '))

Versi baris tunggal membungkus program dengan exec("...".replace('I',' for i in '))sehingga semua for-loop dan generator dapat disingkat dengan satu Idan menyimpan 15 byte dari versi yang lebih mudah dibaca ini:

L=['012','345','678','036','147','258','048','246'];L+=[i[::-1]for i in L]
S=sorted;F=lambda t:''.join(str(i)for i in t)
def N(x):
 s=' '.join(F(S(i))for i in x)
 for i in L:s=s.replace(i[::2],i[:2]+' '+i[1:])
 return S(set(s.split()))
def P(s):
 e=0
 for i in L:e|=-1<s.find(i[::2])<s.find(i[1])
 return[zip(s[:-1],s[1:]),L][e]
x=N(input())
print[F(i)for i in __import__('itertools').permutations({i for i in`x`if i.isdigit()})if x==N(P(F(i)))]

Program mengambil input dengan cara yang ditunjukkan (misalnya {(1,4),(3,4),(5,4),(8,5)}) atau sebagai daftar string (misalnya ['14','34','54','85']) (atau dalam format ramah python lainnya) dan mengembalikan output sebagai daftar string. Jadi kami secara teknis memiliki wadah yang dipesan dari wadah yang dipesan.

Fungsi Nmenormalkan suatu pola sehingga dua pola dapat dengan mudah dibandingkan. Normalisasi mengurutkan pasangan yang menunjukkan tepi (jadi '02'alih-alih '20'), gunakan penggantian string untuk memperluas tepi ganda (misalnya '02'menjadi '01 12'), membagi tepi menjadi satu set untuk menghapus duplikat, dan mengurutkan hasilnya.

Fungsi ini Fmeratakan tupel int / string ke string, sehingga kita dapat menormalkan jalur yang dihasilkan dengan berbagai cara.

Daftar ini Lberisi semua baris di layar.

Kami kemudian mengambil setiap permutasi dari semua digit dalam pola yang dinormalisasi dan menghitung jalur yang valid atau Ljika tidak valid (yang tidak pernah dinormalisasi ke daftar pasangan seperti jalur nyata akan), atau daftar pasangan yang menunjukkan node pesanan dikunjungi jika valid. Jika ini dinormalkan dengan pola yang sama maka kami memiliki solusi yang valid dan memasukkannya dalam daftar akhir.

Pemeriksaan utama yang diperlukan untuk memvalidasi permutasi sebagai string sadalah -1<s.find(i[::2])<s.find(i[1]), yang mendeteksi kesalahan dengan garis i. Misalnya dengan baris '210'kode mendeteksi kesalahan jika '20'terjadi (yaitu indeksnya lebih besar dari -1) dan '1'terjadi setelahnya. Kita tidak perlu khawatir tentang 1 tidak terjadi karena 1 akan muncul dalam pola normal ketika itu tidak ada dalam input.

CATATAN: Saya tahu mengganti str(i)for i in t dengan map(str,t) dan {i for i in`x`if i.isdigit()} dengan set('012345678')&set(`x`) akan membuat kode asli lebih pendek, tapi ini masih sedikit lebih lama daripada yang menggantikan I .