Mord selektiv positive ganze Zahlen

21

Einführung

Arithmetisches Gefängnis ist eine spezielle Einrichtung, die positive ganze Zahlen einkerkert. In letzter Zeit haben die positiven ganzen Zahlen jedoch versucht, zu entkommen. Aus diesem Grund haben die Wächter beschlossen, einige der positiven Ganzzahlen zu eliminieren , um eine Nachricht an die anderen Ganzzahlen zu senden. Sie haben einen Softwareentwickler beauftragt, ein Programm zu schreiben, um herauszufinden, welche ganzen Zahlen für eine maximale Wirkung zu eliminieren sind.

Eingabebeschreibung

Die Eingabe erfolgt über STDIN, Befehlszeilenargumente oder eine Benutzereingabefunktion (z. B. raw_input). Sie können es nicht als Funktionsargument oder vorinitialisierte Variable haben (z. B. erwartet dieses Programm die Eingabe in eine Variable x).

Die erste Eingabezeile enthält eine einzelne positive Ganzzahl, nwobei 8 >= n >= 3. Daran schließen sich nZeilen mit nZeichen aus der Menge an [1,2,3,4,5,6,7,8,9]. Hier ist eine Beispieleingabe:

5
22332
46351
65455
24463
65652

Ausgabebeschreibung

Die Wärter möchten Zahlen streichen, damit die folgenden Bedingungen erfüllt sind:

  • In jeder Zeile und Spalte des resultierenden Gitters wird keine Nummer zweimal angezeigt.
  • Es dürfen keine zwei eliminierten Zahlen horizontal oder vertikal benachbart sein.
  • Die überlebenden Zahlen müssen eine orthogonal zusammenhängende Gruppe bilden - es wird möglich sein, von jeder überlebenden Zahl zu jeder anderen überlebenden Zahl zu gelangen, die sich nur horizontal und vertikal bewegt und niemals eine eliminierte Zahl kreuzt.

Geben Sie die Eingabe aus (minus der ersten Zeile), wobei die eliminierten Zahlen durch ersetzt werden #.

Es kann mehr als eine Lösung geben. In diesem Fall können Sie eine beliebige Lösung ausgeben.

Möglicherweise gibt es auch keine Lösung. Wenn dies der Fall ist, geben Sie die Zeichenfolge aus no answer.

Hier ist eine mögliche Ausgabe für die Beispieleingabe:

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

Beispiel Ein- und Ausgänge

Für jeden Eingang gibt es mehrere Ausgänge. Diese Ausgänge sind also nur Beispiele.

Eingang:

5
46551
51565
32654
14423
43244

Ausgabe:

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

Eingang:

7
7183625
1681563
5238564
8786268
1545382
3814756
5325345

Ausgabe:

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

Eingang:

8
21534768
75196287
68392184
96244853
44865912
76516647
89751326
43698979

Ausgabe:

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

Eingang:

4
2222
2331
3112
1322

Ausgabe:

no answer
code-golf grid Absinth
quelle
4
(Auch als Singles bekannt .)
Türknauf
Dieses Puzzle ist hervorragend. Vielen Dank. Arbeiten an einer Lösung
Nicht dass Charles
1
Ich mag dieses Rätsel, aber es kann nicht "so wie es ist" mit JavaScript in einem Browser beantwortet werden, da die einzige Benutzereingabemethode promptkeine mehrzeilige Eingabe zulässt.
edc65

Antworten:

0

Ruby, 346 344 329 316 Bytes, sltesw

Das ist Code-Golf, nicht Code-schnell, also ...

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"

Verwenden Sie es wie folgt:

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

Das Flag -W0ist nicht notwendig, aber ich schlage vor, dass Sie es entweder hinzufügen, um Warnungen zu deaktivieren oder umzuleiten stderr...

Sagen Sie mir, ob Sie genug Geduld hatten, um es an den Beispielen für n = 6,7,8 auszuführen

Änderungsprotokoll

  • each⇨ mapDank an @NotThatCharles
  • Überprüfen Sie regexp, ähnlich wie bei @NotThatCharles, ob nebeneinander liegende Löschungen und identische Ziffern mit zwei Sekunden angegeben sind
  • Leseeingabe etwas optimiert
  • kleiner und langsamer
blutorange
quelle
ein paar inkrementelle Verbesserungen in der Größe: \dist kürzer als [^#]in der vorletzten Zeile; M.times.to_aist länger als(0..M-1).to_a
Nicht, dass Charles
@NotThatCharles Danke für die Tipps! Ist M.times.to_aaber 1 Byte kürzer als (0..M-1).to_a;) (0...M).to_afunktioniert auch und ist gleich lang.
blutorange
... Zählen ist schwer
Nicht, dass Charles
ist es tatsächlich abgeschlossen, wenn n = 8?
Nicht dass Charles
@NotthatCharles Wenn Sie zu lange warten oder einen superschnellen PC verwenden, sollte dies der Fall sein. Dies ist ein
blutorange
5

Ruby - 541 ..., 394

Der grundlegende Algorithmus ist eine rekursive Tiefensuche nach Duplikaten, um sie zu bestätigen, indem Sie Zeile 1, dann Spalte 1, dann Zeile 2 usw. durchsehen und überprüfen, ob zwei Nachbarn nicht getötet wurden und das Gitter verbunden ist (das ist die break ifKlausel in dort und das bisschen, das davor kommt).

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"

Einige nette Tricks:

if w[1]ist viel kürzer als if !w.one?und wenn Sie wissen, dass es mindestens ein Mitglied gibt, ist es das gleiche Ergebnis.

Ebenso [0]ist kürzer als any?wenn es keinen Block gibt, und s[j]ist eine nette Abkürzung für j<s.size(technisch ist es eher wie j.abs<s.size)

Und y%N+(y/N).iist viel kürzer alsComplex(y%N,y/N)

Wenn es zwei komplizierte Bedingungen gibt, um Zeichenfolgen zu generieren, kann es auch kürzer sein, [cond1?str1a:str1b,cond2?str2a:str2b]*''als alle Parens oder #{}s in hinzuzufügen .

Ungolfing und Erklärung:

(Dies ist aus der 531-Byte-Version. Ich habe Änderungen vorgenommen. Vor allem habe ich seitdem den Aufruf zum Produkt beseitigt - löse jeweils nur eine Ziffer pro Zeile / Spalte, und J ist jetzt nur ein Array, indiziert durch Ganzzahlen Alle Koordinaten sind nur Ganzzahlen.)

H berechnet Nachbarn

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 ist die Größe des Rasters

N = gets.to_i

K sind die Schlüssel zur Karte (komplexe Zahlen)

# 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 ist die Eingabekarte (Gefängnis)

# 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 sind die nicht getöteten Schlüssel

# starts as K

Q ist die hauptsächliche rekursive Methode

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

Der Code wird ausgeführt mit:

# run with whole board
Q[K]

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

Änderungsprotokoll

394 haben @ blutoranges Vorschlag unten hinzugefügt und viel mehr Manipulation herausgenommen

408 Ausgabe nochmals überarbeitet. Verwenden Sie auch .minstatt, .inject(:+)da ich sowieso nur eine Zeile nehme.

417 kürzere Ausgangsberechnung

421 ließen komplexe Zahlen fallen. Verwenden Sie einfach ganze Zahlen. Speichern Sie ein Bundle

450 weitere Eingabeverbesserungen

456 Eingabeverbesserungen

462 inkrementelle Verbesserungen - esp. findnichtselect

475 ließ uden Row / Col Dupe Builder fallen und zerquetschte ihn

503 lösen Sie jeweils nur eine doppelte Ziffer pro Zeile / Spalte.

530 verwenden map &:popstattvalues

531 Ziehe das Lambda heraus, aus dem das Dupes-Array besteht

552 oops! eine Anforderung verpasst

536 geringfügig verbesserte Population von Dupes Array (was früher war d)

541 initial

Nicht dieser Charles
quelle
Innerhalb von Lambdas, breakdie anstelle von verwendet werden können return, wird möglicherweise ein weiteres Byte gespeichert. Ich mag diesen, viele Tricks und viel schneller.
blutorange
@blutorange Danke! Angewandt. Wir haben aber noch einen weiten Weg vor uns, um 344 zu treffen.
Nicht dass Charles
Ein bisschen länger, ja, aber sonst sieht es gut aus. Eine weitere Sache, die ich gesehen habe: In der zweiten Zeile, da die Variable anur einmal verwendet wird, könnte man das machen J=gets(p).split*''. Haben Sie CLI-Argumente ausprobiert, siehe meine Antwort?
blutorange
3

HTML + JavaScript ( ES6 ) 459

Verwenden eines HTML-Textbereichs, um mehrzeilige Eingaben zu erhalten.

Führen Sie zum Testen das Snippet in Firefox aus. Vergrößern Sie den Textbereich, wenn Sie möchten, fügen Sie die Eingabe in den Textbereich ein (Achtung: exakte Eingabe, keine zusätzlichen Leerzeichen in einer Zeile), und klicken Sie auf die Tabulatortaste. Das Ergebnis wird angehängt.

Methode: Ein rekursiver Tiefenserarch. Es findet nicht optimale Lösungen für alle Testfälle in Sekunden (es ist Gode Golf, aber eine gültige Antwort sollte für häufige Testfälle enden)

<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>
Erweitern Sie das Snippet

Erster Versuch

Methode: Ein Depth First Serarch, nicht rekursiv, unter Verwendung eines Benutzerstapels.
Die Funktion könnte leicht in einer Breitensuche umgewandelt werden, chaging l.popzu l.shift, so eine Warteschlange statt einen Stapel verwendet wird , aber es ist zu langsam , und ich bin nicht sicher , kann es eine optimale Lösung trotzdem finden.

Code-Snippet anzeigen

edc65
quelle