Re: [OT (though it might involve some Perl programming)] One for the weekend. (Updated: significant typo!)

in reply to [OT] One for the weekend. (Updated: Answer posted!)

Before I went to bed, I only had a guess. I started with a pen and paper, and some maths:

              w * h = (w - 2) * h + 10
w * h - (w - 2) - h = 10
    h * (w - w + 2) = 10
                 2h = 10
                  h = 5
[download]

Now, we need to find the width. To be able to step on every tile, it must be coprime with the height, and moreover, width - 2 must be coprime with the height as well. I drew the simplest cases and extrapolated the observation to the following sequence: 3, 9, 11, 13, 19, 21, 23...

And when I got up, I verifyied the results with a Perl program. Specify a true command line argument to see the paths:

#!/usr/bin/perl
use strict;
use warnings;

my $DEBUG = shift;

sub steps {
    my ($w, $h) = @_;
    print "$w x $h\n" if $DEBUG;
    my $steps = 1;
    my @dir = ( 1, 1 );
    my ($x, $y) = (1, 1);
    my @visited = ([], [ undef, '\\' ]);
    while () {
        $x += $dir[0];
        $y += $dir[1];
        $dir[0] = -1, $x -= 1 if $x > $w;
        $dir[1] = -1, $y -= 1 if $y > $h;
        $dir[0] = 1,  $x = 1  if $x < 1;
        $dir[1] = 1,  $y = 1  if $y < 1;
        ++$steps;
        return -1 if $steps > $w * $h or $visited[$x][$y];

        $visited[$x][$y] = $dir[0] != $dir[1] ? '/' : '\\';
        if ($DEBUG) {
            for my $x (1 .. $w) {
                for my $y (1 .. $h) {
                    print $visited[$x][$y] // ' ';
                }
                print "\n";
            }
            sleep 1;
            print "\n";
        }

        if ($x == $w and $y == $h) {
            last if $steps == $w * $h
                and '\\' eq $visited[$x][$y];

            return -1
        }
    }
    return $steps
}

my @steps;
my $width = 1;
until (0) {
    for my $height (1 .. $width) {
        $steps[$width][$height] = steps($width, $height);
        print "$width x $height = $steps[$width][$height]\n"
            if ($height > 2          and $steps[$width][$height - 2] =
+= $steps[$width][$height] - 10)
            or ($height < $width - 1 and $steps[$width - 2][$height] =
+= $steps[$width][$height] - 10)
    }
    ++$width;
}
[download]

Update: Spoiler tag removed.

لսႽ† ᥲᥒ⚪⟊Ⴙᘓᖇ Ꮅᘓᖇ⎱ Ⴙᥲ𝇋ƙᘓᖇ

Comment on Re: [OT (though it might involve some Perl programming)] One for the weekend. (Updated: significant typo!) Select or Download Code

In Section Seekers of Perl Wisdom