pengantar

Gaith Arithmetic adalah fasilitas khusus yang memenjarakan bilangan bulat positif. Namun, baru-baru ini, bilangan bulat positif telah mencoba melarikan diri. Oleh karena itu sipir telah memutuskan untuk, um, menghilangkan beberapa bilangan bulat positif untuk mengirim pesan ke bilangan bulat lainnya. Mereka telah menyewa seorang insinyur perangkat lunak untuk menulis sebuah program untuk mencari tahu bilangan bulat mana yang harus dihilangkan untuk efek maksimum.

Deskripsi Input

Input diberikan melalui STDIN, argumen baris perintah, atau fungsi input pengguna (seperti raw_input). Anda tidak dapat memilikinya sebagai argumen fungsi atau variabel yang sudah diinisialisasi (mis. Program ini mengharapkan input dalam variabel x).

Baris input pertama berisi bilangan bulat positif tunggal di nmana 8 >= n >= 3. Berikut ini adalah nbaris yang berisi nkarakter dari set [1,2,3,4,5,6,7,8,9]. Berikut ini contoh input:

5
22332
46351
65455
24463
65652

Deskripsi Output

Sipir ingin menghilangkan angka sehingga kondisi berikut terpenuhi:

• Di setiap baris dan kolom dari kisi yang dihasilkan, tidak ada angka yang akan muncul dua kali;
• Tidak ada dua angka yang dihilangkan yang dapat berdekatan secara horizontal atau vertikal;
• Angka yang masih hidup harus membentuk kelompok yang berdekatan secara ortogonal - akan memungkinkan untuk melakukan perjalanan dari nomor yang masih hidup ke nomor yang masih hidup lainnya yang hanya bergerak secara horizontal dan vertikal dan tidak pernah melewati angka yang dihilangkan.

Keluarkan input (minus baris pertama), dengan angka yang dihilangkan diganti dengan #.

Mungkin ada lebih dari satu solusi. Jika itu masalahnya, Anda dapat mengeluarkan solusi apa pun.

Mungkin juga tidak ada solusi. Jika itu masalahnya, keluarkan string no answer.

Berikut ini adalah kemungkinan output untuk input contoh:

#2#3#
46351
6#4#5
24#63
#56#2

Contoh Input dan Output

Ada beberapa output untuk setiap input, jadi output ini hanyalah contoh.

Memasukkan:

5
46551
51565
32654
14423
43244

Keluaran:

46#51
#156#
326#4
1#423
#324#

Memasukkan:

7
7183625
1681563
5238564
8786268
1545382
3814756
5325345

Keluaran:

71#362#
#6815#3
5238#64
#7#62#8
154#382
3814756
#325#4#

Memasukkan:

8
21534768
75196287
68392184
96244853
44865912
76516647
89751326
43698979

Keluaran:

21#34768
#5196287
683#21#4
9#24#853
#4865912
7#51#64#
89751326
436#8#7#

Memasukkan:

4
2222
2331
3112
1322

Keluaran:

no answer

Ruby, 346 344 329 316 bytes, sl∞∞∞∞∞∞w

Ini kode-golf, bukan kode-cepat, jadi ...

N=/!/=~G=$*[1..-1]*?!
M=N*N
g=->i{(!G[i]||G[i]<?*||i<0||A[i])&&break
A[i]=0
[1,N+1,-1,-1-N].map{|a|g[i+a]}}
f=->w,a{A=[];g[/\d/=~G=a];/#.{#{N}}?#/!~G&&/(\d)([^!]*|.{#{N}}.{#{O=N+1}}*)\1/!~G&&A.count(0)+w==M&&N.times.map{|m|puts G[m*(1+N),N]}&&exit
(w...M).map{|j|b=a+'';b[j]=?#
w<M&&f[w+1,b]}}
f[0,G]
$><<"no answer"

Gunakan seperti:

mad_gaksha@madlab ~/Applications/Tools $ ruby -W0 c50442.rb 3 323 312 231
#23
312
231

Bendera -W0tidak diperlukan, tetapi saya sarankan Anda menambahkannya untuk menonaktifkan peringatan atau mengalihkan stderr...

Katakan jika Anda memiliki cukup kesabaran untuk menjalankannya pada contoh untuk n = 6,7,8

Changelog

• each⇨ map, terima kasih kepada @NotThatCharles
• periksa penghapusan yang berdekatan dan digit yang sama dengan dua regexps, mirip dengan apa yang disarankan @NotThatCharles
• input bacaan yang dioptimalkan sedikit
• lebih kecil & lebih lambat

Ruby - 541 ..., 394

Algoritma dasar adalah pencarian duplikat kedalaman-pertama rekursif untuk memilih, melihat melalui baris 1, kemudian kolom 1, kemudian baris 2, dll, dan memeriksa bahwa dua tetangga tidak terbunuh dan bahwa grid terhubung (itulah break ifklausa dalam di sana, dan bit yang datang sebelumnya).

K=(0...(N=gets.to_i)*N).to_a
J=gets(p).split*''
H=->m{K&[m+1,m-1,m+N,m-N]}
Q=->k{s=[k[j=0]]
(j=s.size
s.map{|x|(s+=H[x]&k).uniq!})while s[j]
break if(K-k).any?{|m|(H[m]-k)[0]}||k!=k&s
$><<K.map{|m|[k.index(m)?J[m]:?#,m%N>N-2?"
":p]}*''|exit if !g=((0...N*2).map{|x|(k.select{|m|m.divmod(N)[x/N]==x%N}.group_by{|m|J[m]}.find{|l,c|c[1]}||[])[1]}-[p]).min
g.map{|d|Q[k-g<<d]}}
Q[K]
puts"no answer"

Beberapa trik rapi:

if w[1]jauh lebih pendek daripada if !w.one?dan jika Anda tahu setidaknya ada satu anggota, itu adalah hasil yang sama.

Demikian pula, [0]lebih pendek daripada any?jika tidak ada blok, dan s[j]merupakan jalan pintas yang lucu untuk j<s.size(secara teknis, ini lebih seperti j.abs<s.size)

Dan y%N+(y/N).ijauh lebih pendek dariComplex(y%N,y/N)

Juga, ketika ada dua persyaratan rumit untuk menghasilkan string, mungkin lebih pendek untuk dilakukan [cond1?str1a:str1b,cond2?str2a:str2b]*''daripada menambahkan semua parens atau #{}s.

Tidak ada komentar dan penjelasan:

(Ini dari versi 531 byte. Saya telah membuat perubahan. Terutama, sejak itu saya menghilangkan panggilan ke produk - hanya menyelesaikan satu digit per baris / kolom pada suatu waktu, dan J sekarang hanya sebuah array, diindeks oleh bilangan bulat. Semua koordinat hanyalah bilangan bulat.)

H menghitung tetangga

def H m 
  # m, like all indices, is a complex number 
  #    where the real part is x and the imaginary is y
  # so neighbors are just +/-i and +/-1

  i='i'.to_c
  neighborhood = [m+1, m-1, m+i, m-i]

  # and let's just make sure to eliminate out-of-bounds cells
  K & neighborhood
end

N adalah ukuran grid

N = gets.to_i

K adalah kunci untuk peta (bilangan kompleks)

# pretty self-explanatory
# a range of, e.g., if N=3, (0..8)
# mapped to (0+0i),(1+0i),(2+0i),(0+1i),(1+1i),(2+1i),...
K = (0..N**2-1).map{|y| (y%N) +(y/N).i }

J adalah peta input (penjara)

# so J is [[0+0,"2"],[0+1i,"3"],....].to_h
J=K.zip($<.flat_map {|s|
  # take each input line, and...
  # remove the "\n" and then turn it into an array of chars 
  s.chomp.chars
}).to_h

k adalah kunci yang tidak terbunuh

# starts as K

Q adalah metode rekursif utama

def Q k
  j=0 # j is the size of mass
  # the connected mass starts arbitrarily wherever k starts
  mass=[k[0]]
  while j < s.size # while s hasn't grown
    j = mass.size   
    mass.each{|cell|
      # add all neighbors that are in k
      (mass+=H[cell] & k).uniq!
    }
  end
  # if mass != k, it's not all orthogonally connected
  is_all_connected = k!=k&mass

  # (K-k) are the killed cells 
  two_neighbors_killed = (K-k).any?{|m|
    # if any neighbors of killed cells aren't in k,
    # it means it was killed, too 
    (H[m]-k)[0]
  }
  # fail fast
  return if two_neighbors_killed || is_all_connected

  def u x
    x.group_by{|m|J[m]}.select{|l,c|c[1]}
  end

  rows_with_dupes = Array.new(N){|r|u[k.select{|m|m.imag==r}]}

  cols_with_dupes = Array.new(N){|r|u[k.select{|m|m.real==r}]}

  # dupes is an array of hashes
  # each hash represents one row or column.  E.g.,
  #   {
  #     "3"=>[(0+0i),(1+0i),(3+0i)],
  #     "2"=>[(2+0i),(4+0i)]
  #   }
  # means that the 0th, 1st and 3rd cells in row 0
  # all are "3", and 2nd and 4th are "2".
  # Any digits without a duplicate are rejected.
  # Any row/col without any dupes is removed here.
  dupes = (rows_with_dupes+cols_with_dupes-[{}])

  # we solve one row at a time
  first_row = dupes[0]

  if !first_row
    # no dupes => success!
    J.map{|m,v|k.member?(m)?v:?#}.each_slice(N){|s|puts s*''}
    exit
  else
    # the digit doesn't really matter
    t=first_row.values

    # cross-multiply all arrays in the row to get a
    # small search space. We choose one cell from each
    # digit grouping and drop the rest.
    t.inject(:product).map{ |*e|
      # Technically, we drop all cells, and add back the
      # chosen cells, but it's all the same.
      new_k = k-t.flatten+e.flatten

      # and then search that space, recursively
      Q[new_k]
    }
  end
end

Kode dijalankan dengan:

# run with whole board
Q[K]

# if we get here, we didn't hit an exit, so we fail
puts"no answer"

Changelog

394 menambahkan saran @ blutorange di bawah ini, dan memotong lebih banyak manipulasi

408 hasil revisi sekali lagi. Juga gunakan .mindaripada .inject(:+)karena saya hanya mengambil satu baris saja.

417 perhitungan output lebih pendek

421 menjatuhkan bilangan kompleks. Cukup gunakan bilangan bulat. Simpan bundel

450 lebih banyak masukan perbaikan

456 peningkatan input

462 peningkatan tambahan - esp. findtidakselect

475 menjatuhkan udan menghancurkan pembangun baris / col dupe

503 hanya menyelesaikan satu digit duplikat per baris / kolom pada suatu waktu.

530 digunakan map &:popsebagai gantinyavalues

531 mengeluarkan lambda yang membuat array dupes

552 oops! melewatkan persyaratan

536 populasi yang sedikit meningkat dari array dupes (apa yang sebelumnya d)

541 awal

HTML + JavaScript ( ES6 ) 459

Menggunakan textarea HTML untuk mendapatkan input multiline.

Untuk mengujinya, jalankan snippet di Firefox. Perbesar textarea jika Anda suka, rekatkan input di dalam textarea (waspadalah: input tepat, tidak ada spasi tambahan pada baris apa pun), dan tab menjauh. Hasilnya ditambahkan.

Metode: seorang Depth First Serarch yang rekursif. Ia menemukan solusi yang tidak optimal untuk semua kasus uji dalam hitungan detik (itu golf golf, tetapi jawaban yang valid harus diakhiri untuk kasus uji umum)

<textarea onchange="s=this.value,
  z=s[0],o=-~z,k=[],X='no answer',f='#',
  (R=(s,t,h={},r=[],d=0)=>(
    s.map((v,i)=>v>0&&[i%o,~(i/o)].map(p=>h[p+=v]=[...h[p]||[],i])),
    [h[i][1]&&h[i].map(p=>r[d=p]=p)for(i in h)],
    d?r.some(p=>(
      (s[p+o]!=f&s[p-o]!=f&s[p-1]!=f&s[p+1]!=f)&&
      (
        g=[...s],g[p]=f,e=[...g],n=0,
        (F=p=>e[p]>0&&[1,-1,o,-o].map(d=>F(p+d),e[p]=--n))(p<o?p+o:p-o),
        t+n==0&&!k[g]&&(k[g]=1,R(g,t-1))
      )
    )):X=s.join('')
  ))([...s.slice(2)],z*z-1),this.value+=`

`+X"></textarea>

Percobaan pertama

Metode: Server Kedalaman Pertama, non-rekursif, menggunakan tumpukan pengguna.
Fungsi dapat dengan mudah diubah dalam Breadth First Search, chaging l.popuntuk l.shift, sehingga menggunakan antrian bukannya tumpukan, tapi itu terlalu lambat dan aku tidak yakin ia dapat menemukan solusi yang optimal pula.

S=s=>{
  z=s[0],o=-~z,s=[...s.slice(2)];
  k=[];
  l=[[z*z,s]];

  for(d=1;d&&(t=l.pop());)
  {
    [t,s]=t,--t,

    s.map((v,i)=>v>0&&[i%o,~(i/o)].map(p=>h[p+=v]=[...h[p]||[],i]),h={},r=[])

    d=0
    for(i in h)h[i][1]&&h[i].map(p=>r[d=p]=p)

    r.map(p=>
      (s[p+o]!='#'&s[p-o]!='#'&s[p-1]!='#'&s[p+1]!='#')&&
      (
        g=[...s],g[p]='#',
        f=[...g],n=0,
        (F=p=>f[p]>0&&[1,-1,o,-o].map(d=>F(p+d),f[p]=--n))(p<o?p+o:p-o),
        t+n||k[g]||(k[g]=l.push([t,g]))
      )
    )
  }
  return d?'no answer':s.join('')
}

// TEST
cases=[
 ['5\n22332\n46351\n65455\n24463\n65652','#2#3#\n46351\n6#4#5\n24#63\n#56#2']
,['5\n46551\n51565\n32654\n14423\n43244','46#51\n#156#\n326#4\n1#423\n#324#']
,['7\n7183625\n1681563\n5238564\n8786268\n1545382\n3814756\n5325345'
 ,'71#362#\n#6815#3\n5238#64\n#7#62#8\n154#382\n3814756\n#325#4#']
,['8\n21534768\n75196287\n68392184\n96244853\n44865912\n76516647\n89751326\n43698979'
 ,'21#34768\n#5196287\n683#21#4\n9#24#853\n#4865912\n7#51#64#\n89751326\n436#8#7#']  
,['4\n2222\n2331\n3112\n1322','no answer']
]

  var out = ''
  var nt=0
  var exec =_=>{ 
    var t=cases[nt++];
    if (t) {
      var r = S(t[0]).replace(/#/g,'<b>#</b>');
      var k = t[1].replace(/#/g,'<b>#</b>');
      out += '<tr><th>Input<th>Result<th>Expected</tr>'+
      '<tr><td>'+t[0]+'</td><td>'+r+'</td><td>'+k+'</td></tr>';
      T.innerHTML = out + 'test ' + nt + ' done';
      setTimeout(exec, 100);
    }
    else
    {
      T.innerHTML = out;
    }
  }
  T.innerHTML = "...wait ..."
  setTimeout(exec, 100);  

table {
  font-size: 12px;
}
td {
  font-family: monospace;
  white-space: pre;
  vertical-align: bottom;
  margin: 2x 4px;
}

b {
  color: #ccc;  
}

<table id=T>
</table>