Einfach wie ABC Solver

11

Easy As ABC, auch als "End View" bekannt, ist ein Puzzle, bei dem Sie ein leeres Gitter mit Buchstaben erhalten. Sie müssen das Raster teilweise ausfüllen, damit sich in jeder Zeile und Spalte genau einer von jedem Buchstaben befindet. Außerdem müssen Buchstaben am Ende einer Zeile (oder Spalte) der erste Buchstabe sein, der in dieser Zeile (oder Spalte) aus dieser Richtung sichtbar ist. Ihr Ziel bei diesem Code-Golf ist es, ein Easy As ABC-Puzzle zu lösen.

Hier ist zum Beispiel ein Easy As ABC-Puzzle von der diesjährigen MIT Mystery Hunt mit den Buchstaben MIC:

Puzzle

Die Lösung ist:

Lösung

(Entschuldigung für die Artefakte auf dem Cs; ich habe versucht, die irrelevanten Informationen aus dem Rest des Puzzles herauszuarbeiten.)

I / O.

Die Eingabe ist ein Array von Zeichenfolgen oder eine Zeichenfolge, möglicherweise mit Trennzeichen. Es beginnt in der oberen linken Ecke und geht im Uhrzeigersinn. Zum Beispiel könnte das obige Puzzle wie folgt eingegeben werden:

".CMM.M|....IM|.....I|C.ICI."

Die Ausgabe sollte das gelöste Raster mit oder ohne Rand sein. Es kann sich um ein Array von Zeichen, ein Array von Zeichenfolgen oder ein anderes geeignetes Format handeln. Das gleiche "leere" Zeichen muss als Eingabe akzeptiert und als Ausgabe angezeigt werden, aber dieses leere Zeichen kann alles sein. Wenn es sich um einzelne Zeichenfolgen handelt, müssen Eingabe und Ausgabe dasselbe Trennzeichen (zwischen den Seiten für die Eingabe und den Zeilen für die Ausgabe) oder überhaupt kein Trennzeichen haben.

Für unlösbare Rätsel müssen Sie etwas ausgeben, das nicht mit einer Lösung verwechselt werden kann. Sie können davon ausgehen, dass kein Puzzle mehr als eine Lösung hat.

Sie müssen eine beliebige Anzahl von Buchstaben und ein beliebiges Raster zulassen. Alle verwendeten Buchstaben werden am Rand des Rasters angezeigt.

Das ist : Wie immer gewinnt der kürzeste Code!

Testfälle

"T.AA..|.T.TSS|..TST.|A...SS"
"R.RU..|B.B..B|.UR.UB|UR..B."
"N...NK|E.NK.K|..KK..|....EK"
"CA..DBD|.B..CC.|.D.DEB.|DB.A..A"
"...DDEBE|DC..EBBD|BA..ABF.|E..FECDE"
Deusovi
quelle
2
um klar zu sein: das gesamte alphabet steht an der grenze? (dh wird kein Brief erscheinen, der nicht an der Grenze ist?)
Quintopia
@ Quintopia: Ja. Der Rand enthält jeden verwendeten Buchstaben.
Deusovi

Antworten:

1

PHP, 1111 Bytes

abzüglich der Bytes, die Zeilenumbrüche entfernen

Die Online-Version funktioniert nur mit den Testfällen mit einer Länge von 6

kurze Problemumgehung

mache alle Permutationen

Fülle 2 Arrays mit den Permutationen $ x $ y

Wechseln Sie zwischen zwei Funktionen, bis nur noch 1 Lösung in der x-Array-Zeile für jede Zeile vorhanden ist

Funktion i: Finden Sie Schnittpunkte im Raster und lassen Sie Permutationen fallen

Funktion c: Überprüfen Sie die Spalten in jedem Array eindeutiger Zeichen und entfernen Sie die Permutationen in den anderen Zeilen für das Array $ x und $ y

$p=[];p(array_pad(($s="str_split")(substr(count_chars($a=$argn,3),1,-1)),$l=(strlen($a)-3)/4," "));
$e=explode("|",$a);$e[3]=strrev($e[3]);$e[2]=strrev($e[2]);
$x=$y=array_fill(0,$l,$p);$g="preg_grep";$c="array_column";$o="join";
foreach($q=range(0,$l-1)as$i){
$e[0][$i]=="."?:$y[$i]=$g("#^\s*{$e[0][$i]}#",$y[$i]);
$e[2][$i]=="."?:$y[$i]=$g("#{$e[2][$i]}\s*$#",$y[$i]);
$e[3][$i]=="."?:$x[$i]=$g("#^\s*{$e[3][$i]}#",$x[$i]);
$e[1][$i]=="."?:$x[$i]=$g("#{$e[1][$i]}\s*$#",$x[$i]);}
for(;array_sum(($m="array_map")("count",$x))>$l;){
foreach($q as$i)foreach($q as$j){
$k=array_intersect($c($m($s,$x[$i]),$j),$c($m($s,$y[$j]),$i));
$y[$j]=$g("#^.{{$i}}(".$o("|",$k).")#",$y[$j]);
$x[$i]=$g("#^.{{$j}}(".$o("|",$k).")#",$x[$i]);
foreach(["x","y"]as$z){
$u=array_unique($c($m($s,${"$z"}[$i]),$j));
if(count($u)==1&&end($u)!=" "){$w=end($u);
foreach($q as$h){
if($i!=$h)${"$z"}[$h]=$g("#^.{{$j}}{$w}#",${"$z"}[$h],1);}}
}}}
echo$o("\n",$m($o,$x));
function p($c,$b=[]){global$p;
if(($c)){$n=[];while($c){
$e=array_pop($c);
p(($m="array_merge")($c,$n),$m($b,[$e]));
$n[]=$e;
}}else in_array($b=join($b),$p)?:$p[]=$b;}
Jörg Hülsermann
quelle