Post History

#6: Post edited by

jhnc‭ · 2026-03-20T23:14:44Z (6 months ago)
store grid redundantly as columns for ease of lookup

Copy Link

Raw

Markdown

# 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 1's~~
! 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
'
```
[Try it online!][TIO-mmzi6240]
[TIO-mmzi6240]: https://tio.run/##TZBBa8JAEIXv@ytGHRaDiZqCULuG5lRy9pKDiGzjWgOahN21bgjpT2@a3QiWubz5ZhjmvUrIy6q7KQHfq/nLKyPXeoqpj4kfSz/OPNap2ydsG4uNj7UXxQeWn6aETCagz7kCVReaG@BVJbhUoEsoSg3C5EpDXoC76pC6SQH3sygg13DnCvjxKI5kAstNhGaDKaVW1RtMiENAKbiBFW7kiFsglKLcYb3fodlH0dJrLmXGL//Y0GdWWxaF9u3RlxTVOMbDOPpZhOBq8bDa2DkaSke9zUbxul8DciplLFlvR7fbIYIg9JiVQWjzYLNZH1j/0juaN9s/try2bdkQZZ/ZB4tldOXVbrr0DKZ7P5zPMWFx9oTJAFO2xdSeToKw69ZrWJPfstJ5Wagu4H8 "Perl 5 – Try It Online"

# 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
'
```
[Try it online!][TIO-mmzi6240]
[TIO-mmzi6240]: https://tio.run/##TZBBa8JAEIXv@ytGHRaDiZqCULuG5lRy9pKDiGzjWgOahN21bgjpT2@a3QiWubz5ZhjmvUrIy6q7KQHfq/nLKyPXeoqpj4kfSz/OPNap2ydsG4uNj7UXxQeWn6aETCagz7kCVReaG@BVJbhUoEsoSg3C5EpDXoC76pC6SQH3sygg13DnCvjxKI5kAstNhGaDKaVW1RtMiENAKbiBFW7kiFsglKLcYb3fodlH0dJrLmXGL//Y0GdWWxaF9u3RlxTVOMbDOPpZhOBq8bDa2DkaSke9zUbxul8DciplLFlvR7fbIYIg9JiVQWjzYLNZH1j/0juaN9s/try2bdkQZZ/ZB4tldOXVbrr0DKZ7P5zPMWFx9oTJAFO2xdSeToKw69ZrWJPfstJ5Wagu4H8 "Perl 5 – Try It Online"

#5: Post edited by

jhnc‭ · 2026-03-20T23:02:39Z (6 months ago)
store grid redundantly as columns for ease of lookup

Copy Link

Raw

Markdown

~~# Perl, 278 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&&$g[$y][$x]==0){local$g[$y][$x]=1;if(!grep"@$_"=~/1 1 1 1/,@g,map{$a=$_;[map$g[$_][$a],0..$H-1]}0..$W-1){if(!$x&&!$y){say@$_~~
~~for@g;exit}R($x,$y-1);R($x-1,$y);++($W<$H?$x:$y);R($x,$y)}}}($W,$H)=@F;@g=map[(0)x$W],1..$H;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
~~$g[$y][$x]==0~~
) {
# mark current position
~~local $g[$y][$x] = 1;~~
if (
# no row or column has run of more than three 1's
~~! grep "@$_" =~ /1 1 1 1/,~~
~~# rows~~
~~@g,~~
~~# columns~~
~~map {~~
~~$a=$_;~~
~~[ map $g[$_][$a], 0..$H-1 ]~~
~~} 0..$W-1~~
) {
# reached second corner
if (!$x && !$y) {
~~say @$_ for @g;~~
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~~
~~@g = map [(0)x$W], 1..$H;~~
# generate path
R $W-1,$H-1
'
```
~~[Try it online!][TIO-mmyxy3k9]~~
[TIO-mmyxy3k9]: https://tio.run/##TVDPb4IwGL33r/imXxqJoLDEZK6ScVo8e@FACOlmRRIFQussIexPH2vrDksvr@/79d5rRXfZTDcp4Guzen5h5NovMPVx7yelxyZ5@4DDYDntY@/FScGq04KQ@RzUuZIg@1pxDbxtBe8kqAbqRoHQlVRQ1eBWOkreOgH3s6ihUnDnEvjxKI5kDuEuRr3DlFKL@h3uiaOAUnAFC1zJMa6BUIplhn2eoc7jOPSGS/PJL/@4yMp8KjvRzhIsZvH3OgL31saXf@XtgDzGgmUG2rHCjPHcD1cr3AdRPlqQBpE32DWoKX0y7gfJe7MNyKnpkpIZl2o8PJIxrczCILIxseXShGiUvqF@tf@/Lm8cR/aI10T5zpIyNvezRehpTHM/stfZwR72rYxp2m5hS36aVlVNLaeA/wI "Perl 5 – Try It Online"

# 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 1's
! 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
'
```
[Try it online!][TIO-mmzi6240]
[TIO-mmzi6240]: https://tio.run/##TZBBa8JAEIXv@ytGHRaDiZqCULuG5lRy9pKDiGzjWgOahN21bgjpT2@a3QiWubz5ZhjmvUrIy6q7KQHfq/nLKyPXeoqpj4kfSz/OPNap2ydsG4uNj7UXxQeWn6aETCagz7kCVReaG@BVJbhUoEsoSg3C5EpDXoC76pC6SQH3sygg13DnCvjxKI5kAstNhGaDKaVW1RtMiENAKbiBFW7kiFsglKLcYb3fodlH0dJrLmXGL//Y0GdWWxaF9u3RlxTVOMbDOPpZhOBq8bDa2DkaSke9zUbxul8DciplLFlvR7fbIYIg9JiVQWjzYLNZH1j/0juaN9s/try2bdkQZZ/ZB4tldOXVbrr0DKZ7P5zPMWFx9oTJAFO2xdSeToKw69ZrWJPfstJ5Wagu4H8 "Perl 5 – Try It Online"

#4: Post edited by

jhnc‭ · 2026-03-20T13:55:26Z (6 months ago)
spaces in regex are actually fewer bytes than the switch to elide them

Copy Link

Raw

Markdown

~~# Perl, 281 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&&$g[$y][$x]==0){local$g[$y][$x]=1;if(!grep"@$_"=~/1111/,@g,map{$a=$_;[map$g[$_][$a],0..$H-1]}0..$W-1){if(!$x&&!$y){say@$_~~
~~for@g;exit}R($x,$y-1);R($x-1,$y);++($W<$H?$x:$y);R($x,$y)}}}$"="";($W,$H)=@F;@g=map[(0)x$W],1..$H;R$W-1,$H-1'~~
```
A recursive backtracker.
~~Restricts choices slightly to reduce amount of backtracking. I had a shorter version but worst case runtime was horrible...~~
```
perl -aE'
sub R {
my ($x,$y) = @_;
if (
# within bounds
0<=$x<$W &&
0<=$y<$H &&
# not already visited
$g[$y][$x]==0
) {
# mark current position
local $g[$y][$x] = 1;
if (
# no row or column has run of more than three 1's
~~! grep "@$_" =~ /1111/,~~
# rows
@g,
# columns
map {
$a=$_;
[ map $g[$_][$a], 0..$H-1 ]
} 0..$W-1
) {
# reached second corner
if (!$x && !$y) {
say @$_ for @g;
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
~~# (choosing right backtracks excessively;~~
~~# would be correct if order was left,up)~~
++( $W<$H ? $x : $y ); R($x,$y)
}
}
}
~~# no spaces when interpolating arrays into strings~~
~~$"="";~~
# load dimensions
($W,$H) = @F;
# initialise grid
@g = map [(0)x$W], 1..$H;
# generate path
~~R$W-1,$H-1~~
'
```
~~[Try it online!][TIO-mmym5wpl]~~
[TIO-mmym5wpl]: https://tio.run/##TVBBboMwELz7FVuysoICCVSK1NSxyqnKORcOEUJu4xCkBBB2GiNEn15qkx7q03h2d3Z2Gtle1uNNSfhaL59fGLl2c0wD3AVJ4bNR3T5g3zvOBNj5PMlZeZoTMpuBPpcKVFdpYUA0jRStAl1DVWuQplQaygomyYlSt1bC/SwrKDXchQJxPMojmUG05Wi2mFLqULfFHZkooBSmggNTaWKmBkIpFgfssgOajPPI7y/1p7j842Jn86loZeMlmHv8exXbt7JHBVfR9Cg45uxgoZvJ7YzIgmi5xF0YZ4MDaRj7vdNAQ@mTPb1XorNSQE51mxTMnqiH/SMW28ocDGOXEVssbILW5huaV/f/6/KHYUCPex57BGzDfGdJwa2JwzzyDaZZEDsLbO@2B87LOG42sCE/daPLulJjKH4B "Perl 5 – Try It Online"

# Perl, 278 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&&$g[$y][$x]==0){local$g[$y][$x]=1;if(!grep"@$_"=~/1 1 1 1/,@g,map{$a=$_;[map$g[$_][$a],0..$H-1]}0..$W-1){if(!$x&&!$y){say@$_
for@g;exit}R($x,$y-1);R($x-1,$y);++($W<$H?$x:$y);R($x,$y)}}}($W,$H)=@F;@g=map[(0)x$W],1..$H;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
$g[$y][$x]==0
) {
# mark current position
local $g[$y][$x] = 1;
if (
# no row or column has run of more than three 1's
! grep "@$_" =~ /1 1 1 1/,
# rows
@g,
# columns
map {
$a=$_;
[ map $g[$_][$a], 0..$H-1 ]
} 0..$W-1
) {
# reached second corner
if (!$x && !$y) {
say @$_ for @g;
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
@g = map [(0)x$W], 1..$H;
# generate path
R $W-1,$H-1
'
```
[Try it online!][TIO-mmyxy3k9]
[TIO-mmyxy3k9]: https://tio.run/##TVDPb4IwGL33r/imXxqJoLDEZK6ScVo8e@FACOlmRRIFQussIexPH2vrDksvr@/79d5rRXfZTDcp4Guzen5h5NovMPVx7yelxyZ5@4DDYDntY@/FScGq04KQ@RzUuZIg@1pxDbxtBe8kqAbqRoHQlVRQ1eBWOkreOgH3s6ihUnDnEvjxKI5kDuEuRr3DlFKL@h3uiaOAUnAFC1zJMa6BUIplhn2eoc7jOPSGS/PJL/@4yMp8KjvRzhIsZvH3OgL31saXf@XtgDzGgmUG2rHCjPHcD1cr3AdRPlqQBpE32DWoKX0y7gfJe7MNyKnpkpIZl2o8PJIxrczCILIxseXShGiUvqF@tf@/Lm8cR/aI10T5zpIyNvezRehpTHM/stfZwR72rYxp2m5hS36aVlVNLaeA/wI "Perl 5 – Try It Online"

#3: Post edited by

jhnc‭ · 2026-03-20T08:10:24Z (6 months ago)
dead variables

Copy Link

Raw

Markdown

~~# Perl, 289 bytes~~
Takes two space-delimited numbers on stdin. Prints route on stdout.
```
~~perl -aE'sub R{my($x,$y,$w,$h)=@_;if(0<=$x<$W&&0<=$y<$H&&$g[$y][$x]==0){local$g[$y][$x]=1;if(!grep"@$_"=~/1111/,@g,map{$a=$_;[map$g[$_][$a],0..$H-1]}0..$W-1){if(!$x&&!$y){say@$_~~
~~for@g;exit}R($x,$y-1);R($x-1,$y);++($W<$H?$x:$y);R($x,$y)}}}$"="";($W,$H)=@F;@g=map[(0)x$W],1..$H;R($W-1,$H-1)'~~
```
A recursive backtracker.
Restricts choices slightly to reduce amount of backtracking. I had a shorter version but worst case runtime was horrible...
```
perl -aE'
sub R {
~~my ($x,$y,$w,$h) = @_;~~
if (
# within bounds
0<=$x<$W &&
0<=$y<$H &&
# not already visited
$g[$y][$x]==0
) {
# mark current position
~~local$g[$y][$x]=1;~~
if (
# no row or column has run of more than three 1's
~~! grep "@$_"=~/1111/,~~
# rows
@g,
# columns
map {
$a=$_;
[ map $g[$_][$a], 0..$H-1 ]
} 0..$W-1
) {
# reached second corner
if (!$x && !$y) {
say @$_ for @g;
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
# (choosing right backtracks excessively;
# would be correct if order was left,up)
~~++($W<$H?$x:$y); R($x,$y)~~
}
}
}
# no spaces when interpolating arrays into strings
$"="";
# load dimensions
($W,$H) = @F;
# initialise grid
@g = map [(0)x$W], 1..$H;
# generate path
~~R($W-1,$H-1)~~
'
```
~~[Try it online!][TIO-mmykqzzp]~~
[TIO-mmykqzzp]: https://tio.run/##TVBBboMwELzzii1ZWbFiklApUlPHKqeKcy4cEEJuQ4AqAYRJA0L06aW220N9mp2dXc9Ok7WX3XxTGXzu1o9P3LkOS4wY3hmGDAsW5AxLhh@Uz@r2BsfR9HuGg5UUVAQpL89Lx1ksoCtKBWqoOtmDbJpMtgq6Gqq6g6wvVQdlBfYTS6lbm8G9yCooO7hLBfJ0yk7OArYHgf0BI0IMGg4YOpYCQsA2DLAty1iBQwjmMQ5JjH0ixJaOl/pdXv5xvrH5kLdZ4waYuuJr4@u3MQdeZTOiFJjyWEMzk@oZmbDteo2h5yeTAZHn09HswJ6QBxzoqOSgV4Fzrtsg5/rEbjr@hqOl3EDP1wXlq5XOVNt8wf7Z1H8qOk0TusJ1uY081GG@8iAX2kS83NIeo4T5xoIZiMwubYbO834Pe@e7brqyrtTsyR8 "Perl 5 – Try It Online"

# Perl, 281 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&&$g[$y][$x]==0){local$g[$y][$x]=1;if(!grep"@$_"=~/1111/,@g,map{$a=$_;[map$g[$_][$a],0..$H-1]}0..$W-1){if(!$x&&!$y){say@$_
for@g;exit}R($x,$y-1);R($x-1,$y);++($W<$H?$x:$y);R($x,$y)}}}$"="";($W,$H)=@F;@g=map[(0)x$W],1..$H;R$W-1,$H-1'
```
A recursive backtracker.
Restricts choices slightly to reduce amount of backtracking. I had a shorter version but worst case runtime was horrible...
```
perl -aE'
sub R {
my ($x,$y) = @_;
if (
# within bounds
0<=$x<$W &&
0<=$y<$H &&
# not already visited
$g[$y][$x]==0
) {
# mark current position
local $g[$y][$x] = 1;
if (
# no row or column has run of more than three 1's
! grep "@$_" =~ /1111/,
# rows
@g,
# columns
map {
$a=$_;
[ map $g[$_][$a], 0..$H-1 ]
} 0..$W-1
) {
# reached second corner
if (!$x && !$y) {
say @$_ for @g;
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
# (choosing right backtracks excessively;
# would be correct if order was left,up)
++( $W<$H ? $x : $y ); R($x,$y)
}
}
}
# no spaces when interpolating arrays into strings
$"="";
# load dimensions
($W,$H) = @F;
# initialise grid
@g = map [(0)x$W], 1..$H;
# generate path
R$W-1,$H-1
'
```
[Try it online!][TIO-mmym5wpl]
[TIO-mmym5wpl]: https://tio.run/##TVBBboMwELz7FVuysoICCVSK1NSxyqnKORcOEUJu4xCkBBB2GiNEn15qkx7q03h2d3Z2Gtle1uNNSfhaL59fGLl2c0wD3AVJ4bNR3T5g3zvOBNj5PMlZeZoTMpuBPpcKVFdpYUA0jRStAl1DVWuQplQaygomyYlSt1bC/SwrKDXchQJxPMojmUG05Wi2mFLqULfFHZkooBSmggNTaWKmBkIpFgfssgOajPPI7y/1p7j842Jn86loZeMlmHv8exXbt7JHBVfR9Cg45uxgoZvJ7YzIgmi5xF0YZ4MDaRj7vdNAQ@mTPb1XorNSQE51mxTMnqiH/SMW28ocDGOXEVssbILW5huaV/f/6/KHYUCPex57BGzDfGdJwa2JwzzyDaZZEDsLbO@2B87LOG42sCE/daPLulJjKH4B "Perl 5 – Try It Online"

#2: Post edited by

jhnc‭ · 2026-03-20T07:51:17Z (6 months ago)
don't actually need sentinel border, can use string matching

Copy Link

Raw

Markdown

~~# Perl, 325 bytes~~
Takes two space-delimited numbers on stdin. Prints route on stdout.
```
perl -aE'sub R{my($x,$y,$h,$w)=@_;if(0<$x<=$W&&0<$y<=$H&&$g[$y][$x]==0){map{for($i=$x;$g[$y][$i+=$_]==1;){++$w}for($j=$y;$g[$j+=$_][$x]==1;){++$h}}-1,1;if($h<3&&$w<3){local$g[$y][$x]=1;if($x==$y==1){say@$_[1..$W]for@g[1..$H];exit}R($x,$y-1);R($x-1,$y);++($W<$H?$x:$y);R($x,$y)}}}($W,$H)=@F;@g=map[(0)x($W+2)],-1..$H;R($W,$H)'
```
First stab at a recursive backtracker.
~~Restricts choices slightly to reduce amount of backtracking required. I had a shorter version but worst case runtime seemed unpleasant...~~
```
perl -aE'
sub R {
~~my ($x,$y, $h,$w) = @_;~~
if (
# within bounds
~~0<$x<=$W &&~~
~~0<$y<=$H &&~~
# not already visited
$g[$y][$x]==0
){
# no bounds check here
~~# zero border on grid guarantees termination~~
~~map{~~
~~for ($i=$x; $g[$y][$i+=$_]==1; ){ ++$w }~~
~~for ($j=$y; $g[$j+=$_][$x]==1; ){ ++$h }~~
~~} -1,1;~~
# not too many in a row
~~if ($h<3 && $w<3) {~~
~~# mark current position~~
~~local $g[$y][$x] = 1;~~
~~# found solution~~
if ($x==$y==1) {
~~# remove the border before printing~~
~~say @$_[1..$W] fo r@g[1..$H];~~
exit
}
# test next positions
~~R($x,$y-1); # first up~~
~~R($x-1,$y); # then left~~
~~# only try one of right/down~~
~~++( $W<$H ? $x : $y );~~
~~R($x,$y)~~
}
}
}
~~# load values~~
($W,$H) = @F;
# initialise grid
~~# border added to reduce range checking~~
~~@g = map [ (0)x($W+2) ], -1..$H;~~
~~R($W,$H)~~
'
```
~~[Try it online!][TIO-mmy8hohl]~~
[TIO-mmy8hohl]: https://tio.run/##VVFdi@IwFH3Pr7jgRQyNYh2GGTYN26elz774IEUyY7QRbUtTtymlf327SXSG3bdzzzncj3Nr1Vxfp7tR8Pt1tXnn5NYvcMewY5gxLFh6ZqgZXiifzP0DtoPXLcPei9hRkR64Pi0Imc2gLbQB05ettCDrWsnGQFtBWbWgrDYt6BLCkECZe6OgK1QJuoVOGpDHozqSGawTtInAHcznHvcOZ8STnvhfCszDQOZzPO@xz/docyHWdLjJejhVzQK1QMu/RB0JPDhDzOkQRdiNwXIR2AfLJciPHk9LMY7LmMX@TCySFzenS17ocK0@5fWfkfF3DkbeFNRN9XFVNyhUo9xRaIUb4XoSj@LH4r4kdDCyT/Gwj1cr3OVunfQccJZzF1s7bh@BL2PKPXS7YE95FLk/JZj9RPvD108XHccxPDBzr/nF07NwMewXa2odG21ozpaht/cHF5mmtw28bcifqm51VZppKf8C "Perl 5 – Try It Online"

# Perl, 289 bytes
Takes two space-delimited numbers on stdin. Prints route on stdout.
```
perl -aE'sub R{my($x,$y,$w,$h)=@_;if(0<=$x<$W&&0<=$y<$H&&$g[$y][$x]==0){local$g[$y][$x]=1;if(!grep"@$_"=~/1111/,@g,map{$a=$_;[map$g[$_][$a],0..$H-1]}0..$W-1){if(!$x&&!$y){say@$_
for@g;exit}R($x,$y-1);R($x-1,$y);++($W<$H?$x:$y);R($x,$y)}}}$"="";($W,$H)=@F;@g=map[(0)x$W],1..$H;R($W-1,$H-1)'
```
A recursive backtracker.
Restricts choices slightly to reduce amount of backtracking. I had a shorter version but worst case runtime was horrible...
```
perl -aE'
sub R {
my ($x,$y,$w,$h) = @_;
if (
# within bounds
0<=$x<$W &&
0<=$y<$H &&
# not already visited
$g[$y][$x]==0
) {
# mark current position
local$g[$y][$x]=1;
if (
# no row or column has run of more than three 1's
! grep "@$_"=~/1111/,
# rows
@g,
# columns
map {
$a=$_;
[ map $g[$_][$a], 0..$H-1 ]
} 0..$W-1
) {
# reached second corner
if (!$x && !$y) {
say @$_ for @g;
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
# (choosing right backtracks excessively;
# would be correct if order was left,up)
++($W<$H?$x:$y); R($x,$y)
}
}
}
# no spaces when interpolating arrays into strings
$"="";
# load dimensions
($W,$H) = @F;
# initialise grid
@g = map [(0)x$W], 1..$H;
# generate path
R($W-1,$H-1)
'
```
[Try it online!][TIO-mmykqzzp]
[TIO-mmykqzzp]: https://tio.run/##TVBBboMwELzzii1ZWbFiklApUlPHKqeKcy4cEEJuQ4AqAYRJA0L06aW220N9mp2dXc9Ok7WX3XxTGXzu1o9P3LkOS4wY3hmGDAsW5AxLhh@Uz@r2BsfR9HuGg5UUVAQpL89Lx1ksoCtKBWqoOtmDbJpMtgq6Gqq6g6wvVQdlBfYTS6lbm8G9yCooO7hLBfJ0yk7OArYHgf0BI0IMGg4YOpYCQsA2DLAty1iBQwjmMQ5JjH0ixJaOl/pdXv5xvrH5kLdZ4waYuuJr4@u3MQdeZTOiFJjyWEMzk@oZmbDteo2h5yeTAZHn09HswJ6QBxzoqOSgV4Fzrtsg5/rEbjr@hqOl3EDP1wXlq5XOVNt8wf7Z1H8qOk0TusJ1uY081GG@8iAX2kS83NIeo4T5xoIZiMwubYbO834Pe@e7brqyrtTsyR8 "Perl 5 – Try It Online"

#1: Initial revision by

jhnc‭ · 2026-03-20T02:06:47Z (6 months ago)

Copy Link

Raw

Markdown

# Perl, 325 bytes

Takes two space-delimited numbers on stdin. Prints route on stdout.

```
perl -aE'sub R{my($x,$y,$h,$w)=@_;if(0<$x<=$W&&0<$y<=$H&&$g[$y][$x]==0){map{for($i=$x;$g[$y][$i+=$_]==1;){++$w}for($j=$y;$g[$j+=$_][$x]==1;){++$h}}-1,1;if($h<3&&$w<3){local$g[$y][$x]=1;if($x==$y==1){say@$_[1..$W]for@g[1..$H];exit}R($x,$y-1);R($x-1,$y);++($W<$H?$x:$y);R($x,$y)}}}($W,$H)=@F;@g=map[(0)x($W+2)],-1..$H;R($W,$H)'
```

First stab at a recursive backtracker.

Restricts choices slightly to reduce amount of backtracking required. I had a shorter version but worst case runtime seemed unpleasant...

```
perl -aE'
    sub R {
        my ($x,$y,  $h,$w) = @_;

        if (
            # within bounds
            0<$x<=$W &&
            0<$y<=$H &&

            # not already visited
            $g[$y][$x]==0
        ){
            # no bounds check here
            # zero border on grid guarantees termination
            map{
                for ($i=$x; $g[$y][$i+=$_]==1; ){ ++$w }
                for ($j=$y; $g[$j+=$_][$x]==1; ){ ++$h }
            } -1,1;

            # not too many in a row
            if ($h<3 && $w<3) {

                # mark current position
                local $g[$y][$x] = 1;

                # found solution
                if ($x==$y==1) {
                    # remove the border before printing
                    say @$_[1..$W] fo r@g[1..$H];
                    exit
                }

                # test next positions

                R($x,$y-1); # first up
                R($x-1,$y); # then left

                # only try one of right/down
                ++( $W<$H ? $x : $y );
                R($x,$y)
            }
        }
    }

    # load values
    ($W,$H) = @F;

    # initialise grid
    # border added to reduce range checking
    @g = map [ (0)x($W+2) ], -1..$H;

    R($W,$H)
'

```

[Try it online!][TIO-mmy8hohl]

[TIO-mmy8hohl]: https://tio.run/##VVFdi@IwFH3Pr7jgRQyNYh2GGTYN26elz774IEUyY7QRbUtTtymlf327SXSG3bdzzzncj3Nr1Vxfp7tR8Pt1tXnn5NYvcMewY5gxLFh6ZqgZXiifzP0DtoPXLcPei9hRkR64Pi0Imc2gLbQB05ettCDrWsnGQFtBWbWgrDYt6BLCkECZe6OgK1QJuoVOGpDHozqSGawTtInAHcznHvcOZ8STnvhfCszDQOZzPO@xz/docyHWdLjJejhVzQK1QMu/RB0JPDhDzOkQRdiNwXIR2AfLJciPHk9LMY7LmMX@TCySFzenS17ocK0@5fWfkfF3DkbeFNRN9XFVNyhUo9xRaIUb4XoSj@LH4r4kdDCyT/Gwj1cr3OVunfQccJZzF1s7bh@BL2PKPXS7YE95FLk/JZj9RPvD108XHccxPDBzr/nF07NwMewXa2odG21ozpaht/cHF5mmtw28bcifqm51VZppKf8C "Perl 5 – Try It Online"

Communities