Wprowadzenie

Arytmetyczny Gaol to specjalny obiekt, w którym uwięzione są liczby całkowite dodatnie. Jednak ostatnio dodatnie liczby całkowite próbują uciec. Dlatego strażnicy postanowili wyeliminować niektóre dodatnie liczby całkowite, aby wysłać wiadomość do innych liczb całkowitych. Zatrudnili inżyniera oprogramowania, aby napisał program, aby dowiedzieć się, które liczby całkowite wyeliminować w celu uzyskania maksymalnego efektu.

Opis wejścia

Dane wejściowe są podawane za pomocą STDIN, argumentów wiersza poleceń lub funkcji wprowadzania danych przez użytkownika (np. raw_input). Nie możesz mieć go jako argumentu funkcji lub wstępnie zainicjowanej zmiennej (np. Ten program oczekuje danych wejściowych w zmiennej x).

Pierwszy wiersz danych wejściowych zawiera jedną dodatnią liczbę całkowitą, ngdzie 8 >= n >= 3. Poniżej znajdują się nwiersze zawierające nznaki ze zbioru [1,2,3,4,5,6,7,8,9]. Oto przykładowe dane wejściowe:

5
22332
46351
65455
24463
65652

Opis wyjścia

Strażnicy chcieliby wyeliminować liczby, aby spełnione były następujące warunki:

• W każdym wierszu i kolumnie wynikowej siatki żadna liczba nie pojawi się dwukrotnie;
• Żadne dwie wyeliminowane liczby nie mogą przylegać poziomo ani pionowo;
• Liczby, które przeżyły, muszą tworzyć ortogonalnie ciągłą grupę - możliwe będzie podróżowanie z dowolnej liczby, która przeżyła, na dowolną inną liczbę, która przeżyje, poruszając się tylko poziomo i pionowo i nigdy nie przekraczając żadnej liczby wyeliminowanej.

Wyjście wejściowe (minus pierwszy wiersz), z wyeliminowanymi liczbami zastąpionymi przez #.

Może być więcej niż jedno rozwiązanie. W takim przypadku możesz wypisać dowolne rozwiązanie.

Może również nie być rozwiązania. W takim przypadku wypisz ciąg znaków no answer.

Oto możliwe dane wyjściowe dla przykładowego wejścia:

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

Przykładowe wejścia i wyjścia

Istnieje wiele wyjść dla każdego wejścia, więc są to tylko przykłady.

Wkład:

5
46551
51565
32654
14423
43244

Wydajność:

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

Wkład:

7
7183625
1681563
5238564
8786268
1545382
3814756
5325345

Wydajność:

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

Wkład:

8
21534768
75196287
68392184
96244853
44865912
76516647
89751326
43698979

Wydajność:

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

Wkład:

4
2222
2331
3112
1322

Wydajność:

no answer

Rubinowy, 346 344 329 316 bajtów, sl∞∞∞∞∞∞w

To jest golfowy kod, nie szybki kod, więc ...

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"

Używaj go jak:

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

Flaga -W0nie jest konieczna, ale sugeruję dodanie jej w celu wyłączenia ostrzeżeń lub przekierowanie stderr...

Powiedz mi, czy masz dość cierpliwości, aby uruchomić ją na przykładach dla n = 6,7,8

Dziennik zmian

• each⇨ mapdzięki @NotThatCharles
• sprawdź sąsiednie usunięcia i te same cyfry o dwa regexps, podobnie jak sugerował @NotThatCharles
• trochę zoptymalizowane odczyt
• mniejszy i wolniejszy

Ruby - 541 ..., 394

Podstawowym algorytmem jest rekurencyjne przeszukiwanie w pierwszej kolejności duplikatów w celu wybrania twierdzącego, przeglądanie wiersza 1, następnie kolumny 1, następnie wiersza 2 itd. I sprawdzanie, czy dwóch sąsiadów nie zostało zabitych i czy sieć jest podłączona (to jest break ifklauzula w tam i kawałek, który jest przed nim).

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"

Kilka ciekawych sztuczek:

if w[1]jest znacznie krótszy niż if !w.one?i jeśli wiesz, że jest co najmniej jeden członek, to ten sam wynik.

Podobnie [0]jest krótszy niż, any?jeśli nie ma bloku, i s[j]jest uroczym skrótem do j<s.size(technicznie bardziej przypomina j.abs<s.size)

I y%N+(y/N).ijest znacznie krótszy niżComplex(y%N,y/N)

Ponadto, gdy istnieją dwa skomplikowane warunki generowania ciągów, może to być krótsze [cond1?str1a:str1b,cond2?str2a:str2b]*''niż dodanie wszystkich parens lub #{}s.

Wykluczenie i objaśnienie:

(Jest to wersja 531 bajtów. Wprowadziłem zmiany. Co najważniejsze, od tego czasu wyeliminowałem wezwanie do produktu - po prostu rozwiązuj jedną cyfrę na wiersz / kolumnę na raz, a J jest teraz tylko tablicą indeksowaną według liczby całkowite. Wszystkie współrzędne są tylko liczbami całkowitymi.)

H oblicza sąsiadów

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 to rozmiar siatki

N = gets.to_i

K są kluczami do mapy (liczby zespolone)

# 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 to mapa wejściowa (więzienie)

# 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 są nie zabitymi kluczami

# starts as K

Q jest główną metodą rekurencyjną

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

Kod jest wykonywany za pomocą:

# run with whole board
Q[K]

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

Dziennik zmian

394 dodał poniżej sugestię @ blutorange i wyciągnął znacznie więcej manipulacji

408 raz jeszcze poprawiono wydajność. Użyj także .minzamiast, .inject(:+)ponieważ i tak biorę tylko jeden wiersz.

417 krótsze obliczenia wydajności

421 upuściło liczby zespolone. Po prostu użyj liczb całkowitych. Zapisz pakiet

450 więcej ulepszeń wejściowych

Ulepszenia wprowadzania 456

462 przyrostowe ulepszenia - szczególnie. find, nieselect

475 upuścił ui zmiażdżył konstruktora wierszy / kol. Dupe

503 rozwiązuje tylko jedną zduplikowaną cyfrę na wiersz / kolumnę na raz.

530 użyć map &:popzamiastvalues

531 wyciągnij lambda, która tworzy tablicę duplikatów

552 ups! brakowało wymagania

536 nieznacznie poprawiona populacja tablicy duplikatów (poprzednio d)

541 inicjał

HTML + JavaScript ( ES6 ) 459

Korzystanie z obszaru tekstowego HTML w celu uzyskania wprowadzania wielowierszowego.

Aby przetestować, uruchom fragment w przeglądarce Firefox. Jeśli chcesz, powiększ obszar tekstowy, wklej tekst wewnątrz obszaru tekstowego (uwaga: dokładne wprowadzanie, bez dodatkowych spacji w dowolnym wierszu) i tabulator. Wynik jest dołączany.

Metoda: rekursywna pierwsza głębokość Serarch. Znajduje nieoptymalne rozwiązania dla wszystkich przypadków testowych w kilka sekund (to gra w golfa, ale ważna odpowiedź powinna zakończyć się w przypadku typowych przypadków testowych)

<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>

Pierwsza próba

Metoda: Głębokie pierwsze Serarch, nierekurencyjne, przy użyciu stosu użytkowników.
Funkcja może być łatwo przekształcony w przeszukiwanie wszerz, chaging l.popsię l.shift, więc za pomocą kolejki zamiast stosu, ale to jest zbyt powolny i nie jestem pewien, może on znaleźć rozwiązanie optymalne i tak.

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>