Легко, как ABC Solver

11

Easy As ABC, также известная как «End View», представляет собой головоломку, где вам дают пустую сетку с буквами вокруг нее; Вы должны частично заполнить сетку так, чтобы в каждой строке и столбце было ровно по одной букве; кроме того, буквы в конце строки (или столбца) должны быть первой буквой, видимой в этой строке (или столбце) с этого направления. Ваша цель в этом кодовом гольфе - решить головоломку Easy As ABC.

Например, вот загадка Easy As ABC из MIT Mystery Hunt этого года с использованием букв MIC:

головоломка

Решение:

решение

(Извините за артефакты на C; я пытался отредактировать не относящуюся к делу информацию из остальной части головоломки.)

I / O

Входные данные будут массивом строк или строк, возможно, с разделителями. Это начнется в верхнем левом углу и пойдет по часовой стрелке. Например, приведенная выше головоломка может быть введена так:

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

Выход должен быть решенной сеткой, с границей или без нее. Это может быть массив символов, массив строк или любой другой удобный формат. Тот же самый «пустой» символ должен быть принят как ввод и отображен как вывод, но этот пустой символ может быть чем угодно. Если они являются одиночными строками, то и вход, и выход должны иметь одинаковый разделитель (между сторонами для ввода и строки для вывода) или вообще не иметь разделителя.

Для неразрешимых головоломок вы должны вывести что-то, что не может быть ошибочно принято за решение. Вы можете предположить, что ни у одной головоломки нет более одного решения.

Вы должны разрешить любое количество букв и сетки любого размера; все используемые буквы появятся на границе сетки.

Это : как обычно, выигрывает самый короткий код!

Тестовые случаи

"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
источник
2
чтобы было понятно: весь алфавит дан на границе? (т.е. не появится письмо, которое не находится на границе?)
Quintopia
@ Quintopia: Да. Граница будет содержать каждое использованное письмо.
Деусови

Ответы:

1

PHP, 1111 байт

минус байты, удаляющие символы новой строки

Интернет - версия работает только с Testcases длиной 6

короткий обходной путь

сделать все перестановки

заполнить 2 массива перестановками $ x $ y

переключаться между двумя функциями до тех пор, пока существует только одно решение в каждой строке массива x

функция i: найти пересечения в сетке и переставить капли

функция c: проверяет столбцы в каждом массиве уникальных символов и удаляет перестановки в других строках для массива $ x и $ 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;}
Йорг Хюльсерманн
источник