Kemana ular itu pergi?

35

Tulis fungsi (menggunakan sesedikit mungkin byte) yang mengambil array dua dimensi dari sejumlah kolom dan baris di mana:

  • 0 mewakili blok kosong,
  • 1 mewakili blok ular.

Fungsi harus mengembalikan jumlah kemungkinan jalur yang dilalui ular.

Contoh 1:

Memasukkan:

[
  [1,1,1,1,1],
  [0,0,0,0,1],
  [0,0,0,0,1],
]

Keluaran: 2

Pada contoh di atas, fungsi akan kembali 2karena jawabannya adalah salah satu dari:

masukkan deskripsi gambar di sini

Contoh 2:

Memasukkan:

[
  [1,1,1,1],
  [0,0,1,1],
  [0,0,1,1],
]

Keluaran: 6

Dalam contoh ini fungsi akan kembali 6karena jawabannya adalah salah satu dari:

masukkan deskripsi gambar di sini

catatan:

Saat menilai input, Anda dapat mengasumsikan bahwa:

  • Array yang mewakili kolom akan selalu memiliki ukuran yang sama (sehingga array berbentuk persegi panjang);
  • Setidaknya ada 1 jalur yang valid;
  • Ular tidak dapat berjalan melalui tepian (seperti yang dapat terjadi pada beberapa versi ular);
  • Ular akan selalu memiliki setidaknya 2 blok;
  • Ular tidak bisa bergerak secara diagonal;
  • Jalan diarahkan. (jadi, dua jalur berakhir pada posisi yang berbeda tetapi sebaliknya tampak sama persis bukan jalan yang sama, itu akan menambah hingga total)
Adelin
sumber
13
Selamat datang di PPCG! Tantangan pertama yang bagus.
Laikoni
5
Catatan kecil: "Akan selalu ada setidaknya satu baris dan satu kolom" adalah berlebihan, mengingat bahwa ular akan selalu memiliki setidaknya 2 blok.
Stewie Griffin
2
Kasus uji yang disarankan: yang diberikan oleh @StewieGriffin dan [[0,0,1,1],[0,0,1,1],[0,0,1,1]]. Sebagian besar jawaban memberi 16, tetapi satu memberi 15.
Kevin Cruijssen
2
Sepertinya semua orang sejauh ini (termasuk saya) telah membuat asumsi bahwa 2 jalur berakhir pada posisi yang berbeda tetapi sebaliknya terlihat sama persis bukan jalan yang sama. Saya pikir ini perlu ditentukan secara eksplisit.
Arnauld
2
@Arnauld - benar. Dua jalur berakhir pada posisi yang berbeda tetapi sebaliknya tampak sama persis bukan jalur yang sama , itu akan menambah hingga total. Dalam contoh Anda, totalnya harus 16 jika saya tidak salah - saya tidak dapat menghitung secara akurat sekarang tetapi Anda mendapatkan intinya
Adelin

Jawaban:

11

Bahasa Wolfram (Mathematica) , 16 + 83 = 99 byte

Pernyataan impor perpustakaan (16 byte):

<<Combinatorica`

Badan fungsi aktual (83 byte):

Length@HamiltonianCycle[MakeGraph[#~Position~1~Join~{1>0},##||Norm[#-#2]==1&],All]&

Cobalah online!


Perhatikan bahwa pertanyaannya hanya menanyakan jumlah jalur Hamiltonian dalam grafik.

Namun, (untuk beberapa alasan) HamiltonianPathfungsi tidak benar-benar berfungsi dengan grafik berarah ( contoh ) Jadi, saya menggunakan solusi yang dijelaskan dalam pertanyaan Mathematica.SE ini :

  • Tambahkan simpul (disebut True) yang terhubung ke semua simpul lainnya.
  • Hitung jumlah siklus Hamiltonian pada grafik yang dihasilkan.

Grafik dikonstruksikan menggunakan MakeGraph(secara mengganggu tidak ada built-in yang setara langsung), menggunakan fungsi boolean ##||Norm[#-#2]==1&, yang mengembalikan Truejika dan hanya jika salah satu argumen adalah Trueatau jarak antara dua simpul tersebut 1.


Tr[1^x]tidak dapat digunakan sebagai gantinya Length@x, dan <2tidak dapat digunakan sebagai gantinya ==1.


HamiltonianPathdapat digunakan jika grafik tidak diarahkan, dengan fungsi tubuh membutuhkan 84 byte (lebih tepatnya 1 byte lebih dari pengiriman saat ini):

Length@HamiltonianPath[MakeGraph[#~Position~1,Norm[#-#2]==1&,Type->Undirected],All]&

Cobalah online!

pengguna202729
sumber
10

JavaScript (ES6), 154 134 byte

m=>m.map((r,Y)=>r.map(g=(_,x,y,r=m[y=1/y?y:Y])=>r&&r[x]&&[-1,0,1,2].map(d=>r[r[x]=0,/1/.test(m)?g(_,x+d%2,y+~-d%2):++n,x]=1)),n=0)|n/4

Cobalah online!

Bagaimana?

metode

Mulai dari setiap sel yang mungkin, kita mengisi matriks, membersihkan semua sel di jalan kita. Setiap kali matriks berisi tidak lebih dari 1 , kami menambah jumlah n dari jalur yang mungkin.

Setiap jalur yang valid dihitung 4 kali karena arah yang dipilih pada sel terakhir, yang sebenarnya tidak masalah. Karena itu, hasil akhirnya adalah n / 4 .

Fungsi rekursif

Alih-alih memanggil fungsi rekursif g () dari callback peta kedua () seperti ini ...

m=>m.map((r,y)=>r.map((_,x)=>(g=(x,y,r=m[y])=>...g(x+dx,y+dy)...)(x,y)))

... kita mendefinisikan rekursif fungsi g () secara langsung sebagai callback dari peta () :

m=>m.map((r,Y)=>r.map(g=(_,x,y,r=m[y=1/y?y:Y])=>...g(_,x+dx,y+dy)...))

Meskipun formula agak panjang y=1/y?y:Yyang diperlukan untuk mengatur nilai awal y , ini menghemat 2 byte secara keseluruhan.

Kode yang dikomentari

m =>                           // given the input matrix m[][]
  m.map((r, Y) =>              // for each row r[] at position Y in m[][]:
    r.map(g = (                //   for each entry in r[], use g() taking:
      _,                       //     - the value of the cell (ignored)
      x,                       //     - the x coord. of this cell
      y,                       //     - either the y coord. or an array (1st iteration),
                               //       in which case we'll set y to Y instead
      r = m[y = 1 / y ? y : Y] //     - r = the row we're currently located in
    ) =>                       //       (and update y if necessary)
      r && r[x] &&             //     do nothing if this cell doesn't exist or is 0
      [-1, 0, 1, 2].map(d =>   //     otherwise, for each direction d,
        r[                     //     with -1 = West, 0 = North, 1 = East, 2 = South:
          r[x] = 0,            //       clear the current cell
          /1/.test(m) ?        //       if the matrix still contains at least one '1':
            g(                 //         do a recursive call to g() with:
              _,               //           a dummy first parameter (ignored)
              x + d % 2,       //           the new value of x
              y + ~-d % 2      //           the new value of y
            )                  //         end of recursive call
          :                    //       else (we've found a valid path):
            ++n,               //         increment n
          x                    //       \_ either way,
        ] = 1                  //       /  do r[x] = 1 to restore the current cell to 1
      )                        //     end of map() over directions
    ),                         //   end of map() over the cells of the current row
    n = 0                      //   start with n = 0
  ) | n / 4                    // end of map() over the rows; return n / 4
Arnauld
sumber
10

Jelly , 12 11 byte

ŒṪŒ!ạƝ€§ÐṂL

Cobalah online!


Penjelasan.

ŒṪ               Positions of snake blocks.
  Œ!             All permutations.
                 For each permutation:
    ạƝ€             Calculate the absolute difference for each neighbor pair
       §            Vectorized sum.
                 Now we have a list of Manhattan distance between snake
                    blocks. Each one is at least 1.
        ÐṂL      Count the number of minimum values.
                    Because it's guaranteed that there exists a valid snake,
                    the minimum value is [1,1,1,...,1].
pengguna202729
sumber
Fitur-fitur baru terbukti sangat berguna.
user202729
Bagaimana kalau §ỊMLbukannya §ỊP€Smenyimpan byte - saya pikir itu harus bekerja?
Jonathan Allan
... atau §ÐṂLyang sedikit lebih cepat.
Jonathan Allan
@JonathanAllan Hanya berfungsi jika hasilnya bukan nol.
user202729
@ JonathanAllan Jadi akhirnya benar-benar berfungsi.
user202729
8

Python 2 , 257 246 241 234 233 227 214 210 byte

lambda b:sum(g(b,i,j)for j,l in e(b)for i,_ in e(l))
e=enumerate
def g(b,x,y):d=len(b[0])>x>-1<y<len(b);c=eval(`b`);c[d*y][d*x]=0;return d and b[y][x]and('1'not in`c`or sum(g(c,x+a,y)+g(c,x,y+a)for a in(1,-1)))

Cobalah online!


Disimpan

  • -8 byte, terima kasih kepada Kevin Cruijssen
  • -14 byte, terima kasih kepada user202729
TFeld
sumber
1
Bahasa yang tepat untuk pekerjaan itu?
Neil
5

Python 2, 158 byte

E=enumerate
g=lambda P,x,y:sum(g(P-{o},*o)for o in P if x<0 or abs(x-o[0])+abs(y-o[1])<2)+0**len(P)
lambda L:g({(x,y)for y,r in E(L)for x,e in E(r)if e},-1,0)

Cobalah online!

KSab
sumber
3

Haskell , 187 155 byte

r=filter
l=length
(a,b)?(x,y)=abs(a-x)+abs(b-y)==1
l#x=sum[p!r(/=p)l|p<-x]
p![]=1
p!l=l#r(p?)l
f x|l<-[(i,j)|i<-[0..l x-1],j<-[0..l(x!!0)-1],x!!i!!j>0]=l#l

Cobalah online!

pengguna28667
sumber