Easy As ABC, znany również jako „End View”, to układanka, w której otrzymujesz pustą siatkę z literami wokół niej; musisz częściowo wypełnić siatkę, aby dokładnie jedna litera znajdowała się w każdym wierszu i kolumnie; ponadto litery na końcu wiersza (lub kolumny) muszą być pierwszą literą widoczną w tym wierszu (lub kolumnie) z tego kierunku. Twoim celem w tym golfie kodowym będzie rozwiązanie zagadki Easy As ABC.

Na przykład, oto łamigłówka Easy As ABC z tegorocznego MIT Mystery Hunt z użyciem liter MIC:

Rozwiązaniem jest:

(Przepraszam za artefakty na Cs; Próbowałem wyedytować nieistotne informacje z reszty układanki.)

I / O

Dane wejściowe będą tablicą ciągów lub łańcuchem, ewentualnie z ogranicznikami. Rozpocznie się w lewym górnym rogu i pójdzie w prawo. Na przykład powyższą łamigłówkę można wprowadzić w następujący sposób:

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

Wyjściem powinna być rozwiązana siatka z ramką lub bez. Może być tablicą znaków, tablicą ciągów znaków lub dowolnym innym wygodnym formatem. Ten sam „pusty” znak musi zostać zaakceptowany jako wejście i wyświetlony jako wynik, ale ten pusty znak może być dowolny. Jeśli są to pojedyncze ciągi, zarówno wejście, jak i wyjście muszą mieć ten sam separator (między bokami dla danych wejściowych i wierszami dla danych wyjściowych) lub w ogóle nie mogą zawierać separatora.

W przypadku zagadek nierozwiązywalnych musisz wydać coś, co nie jest błędne dla rozwiązania. Możesz założyć, że żadna łamigłówka nie ma więcej niż jednego rozwiązania.

Musisz zezwolić na dowolną liczbę liter i dowolną wielkość siatki; wszystkie użyte litery pojawią się na granicy siatki.

To jest golf golfowy : jak zwykle najkrótszy kod wygrywa!

Przypadki testowe

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

PHP, 1111 bajtów

minus bajty usuwające nowe linie

Wersja online działa tylko z Testcases o długości 6

krótkie obejście

dokonać wszystkich permutacji

wypełnij 2 tablice permutacjami $ x $ y

przełączaj się między dwiema funkcjami tak długo, aż istnieje tylko jedno rozwiązanie w linii foreach tablicy x

funkcja i: znajdź przecięcia w siatce i upuść permutacje

funkcja c: sprawdź kolumny w każdej tablicy unikalnych znaków i usuń permutacje w innych wierszach dla tablic $ x i $ 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;}