Connect the corners without 4 in a row
Connect opposite corners of a rectangle of characters without putting 4 characters in a row.
Input
- Two numbers, W and H, representing the width and height of the rectangle
- Each number will be in the range 2 to 70
Output
- A rectangular grid of characters, of width W and height H
- You may choose any 2 distinct characters to represent path and background
- The output must contain 2 connected path characters in diagonally opposite corners of the grid
- Connected means there is a path from one to the other moving only between adjacent path characters
- Adjacent means 1 character away horizontally or vertically (but not both - diagonal adjacency does not count as connection for this challenge)
- The output must not contain 4 adjacent path characters in a line horizontally or vertically
- There is no limit to how many of the characters may be path characters, provided there are never 4 in a row.
- There may be redundant sections connected to the path
- There may be disconnected sections of path provided the main path meets the requirements
Examples
These examples use # for a path character and . for the background.
Valid examples for input 4, 3
##..
.##.
..##
.###
.#..
##..
#...
##..
.###
##.#
.###
##.#
Invalid examples for input 4, 3
4 in a line horizontally:
#...
####
...#
Depends on diagonal adjacency, which does not count as connection:
#...
.#..
..##
Does not connect diagonally opposite corners:
###.
..##
###.
Valid examples for input 7, 5
###....
..#....
..###..
....#..
....###
##.....
.##....
..##...
...##..
....###
#......
#......
##.###.
.#.#.##
.###..#
###....
..###..
###.###
#...#.#
###...#
Invalid examples for input 7, 5
Does not connect two diagonally opposite corners:
###....
..###..
....###
...##..
...#...
Has 4 in a row horizontally:
####...
...#...
...###.
.....#.
.....##
Has 4 in a row vertically:
###....
..#....
..#.###
..###.#
......#
Depends on diagonal adjacency, which does not count as connection:
##.....
..##...
....##.
......#
......#
Validator
You can check a specific output using this path validator, which will give a reason for any failed validations.
Explanations are optional, but I'm more likely to upvote answers that have one.
2 answers
Haskell + hgl, 134 bytes
k=cy"X.XX"
x#1=[4,0,9,9]!x
2#y=8
3#y=[8,9,4,4]!y
x#3=[0,3]!x
_#_=0
x?y|(n,j)<-fvD 4$x%4#(y%4)=tk y$dr j$tk x<dr n<cy[dr2 k,k,cy".X",k]
I first set up a pretty dense background pattern which doesn't break any rules:
XXX.XXX.XXX.XXX.XXX.
X.XXX.XXX.XXX.XXX.XX
.X.X.X.X.X.X.X.X.X.X
X.XXX.XXX.XXX.XXX.XX
XXX.XXX.XXX.XXX.XXX.
X.XXX.XXX.XXX.XXX.XX
.X.X.X.X.X.X.X.X.X.X
X.XXX.XXX.XXX.XXX.XX
XXX.XXX.XXX.XXX.XXX.
X.XXX.XXX.XXX.XXX.XX
.X.X.X.X.X.X.X.X.X.X
X.XXX.XXX.XXX.XXX.XX
XXX.XXX.XXX.XXX.XXX.
X.XXX.XXX.XXX.XXX.XX
.X.X.X.X.X.X.X.X.X.X
X.XXX.XXX.XXX.XXX.XX
XXX.XXX.XXX.XXX.XXX.
X.XXX.XXX.XXX.XXX.XX
.X.X.X.X.X.X.X.X.X.X
X.XXX.XXX.XXX.XXX.XX
All we have to do is make sure the pattern is aligned so there's always a path. I wish I had some clever way of doing this, but I just use a bunch of magic numbers I calculated by trial and error.
Since the pattern repeats with period 4, I just tried every pair of numbers on the range 1-4 and found a shifting that lined up. I encoded these in base 4 and that's what the program uses.
There might be an opportunity to optimize this by finding better numbers.
Perl, 276 bytes
Takes two space-delimited numbers on stdin. Prints route on stdout.
perl -aE'sub R{my($x,$y)=@_;if(0<=$x<$W&&0<=$y<$H&&$r[$y][$x]==0){local$r[$y][$x]=local$c[$x][$y]=1;if(!grep"@$_"=~/1 1 1 1/,@r,@c){if(!$x&&!$y){say@$_
for@r;exit}R($x,$y-1);R($x-1,$y);++($W<$H?$x:$y);R($x,$y)}}}($W,$H)=@F;@r=map[(0)x$W],1..$H;@c=map[(0)x$H],1..$W;R$W-1,$H-1'
A recursive backtracker.
Restricts choices slightly to reduce amount of backtracking.
perl -aE'
sub R {
my ($x,$y) = @_;
if (
# within bounds
0<=$x<$W &&
0<=$y<$H &&
# not already visited
$r[$y][$x]==0
) {
# mark current position
local $r[$y][$x] = local $c[$x][$y] = 1;
if (
# no row or column has run of more than three 1s
! grep "@$_" =~ /1 1 1 1/, @r, @c
) {
# reached second corner
if (!$x && !$y) {
say @$_ for @r;
exit
}
# extend path
R($x,$y-1); # first try up
R($x-1,$y); # then try left
# then
# if tall+narrow, try right
# if wide+short, try down
# if square, also try down
# (going right backtracks excessively in some
# cases (eg. 40 40); but I think would be
# correct if order was left,up)
++( $W<$H ? $x : $y ); R($x,$y)
}
}
}
# load dimensions
($W,$H) = @F;
# initialise grid, store twice for ease of lookup
@r = map [(0)x$W], 1..$H; # list of rows
@c = map [(0)x$H], 1..$W; # list of columns
# generate path
R $W-1,$H-1
'
0 comment threads