11
\$\begingroup\$

Easy As ABC, also known as "End View", is a puzzle where you are given an empty grid with letters around it; you must partially fill in the grid so that exactly one of each letter is in every row and column; in addition, letters at the end of a row (or column) must be the first letter visible in that row (or column) from that direction. Your goal in this code golf will be to solve an Easy As ABC puzzle.

For example, here is an Easy As ABC puzzle from this year's MIT Mystery Hunt using the letters MIC:

puzzle

The solution is:

solution

(Sorry about the artifacts on the Cs; I tried to edit out the irrelevant information from the rest of the puzzle.)

I/O

Input will be an array of strings or a string possibly with delimiters. It will start in the top left corner and go clockwise. For instance, the above puzzle could be input like this:

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

Output should be the solved grid, with or without the border. It can be as an array of chars, array of strings, or any other convenient format. The same "blank" character must be accepted as input and displayed as output, but that blank character may be anything. If they are single strings, both input and output must have the same separator (between sides for input and rows for output) or no separator at all.

For unsolvable puzzles, you must output something that is not mistakable for a solution. You may assume that no puzzle has more than one solution.

You must allow any number of letters and any size grid; all used letters will appear in the border of the grid.

This is : as usual, shortest code wins!

Test Cases

"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"
\$\endgroup\$
  • 2
    \$\begingroup\$ to be clear: the entire alphabet is given on the border? (i.e. no letter will appear that is not on the border?) \$\endgroup\$ – quintopia Jan 28 '16 at 5:39
  • \$\begingroup\$ @quintopia: Yes. The border will contain every used letter. \$\endgroup\$ – Deusovi Jan 28 '16 at 5:40
  • \$\begingroup\$ Similar yet quite different puzzle \$\endgroup\$ – Sp3000 Jan 28 '16 at 11:53
1
\$\begingroup\$

PHP, 1111 Bytes

minus the Bytes removing newlines

The Online version works only with the Testcases with a length of 6

short workaround

make all permutations

fill 2 arrays with the permutations $x $y

change between two functions so long till only 1 solution in the x array foreach line exists

function i:find intersections in the grid and drop permutations

function c:check the colums in each array of unique charcters and remove permutations in the other lines for array $x and $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;}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.