Beefy Boxes and Bandwidth Generously Provided by pair Networks
P is for Practical
 
PerlMonks  

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

by choroba (Cardinal)
on Mar 28, 2015 at 08:15 UTC ( [id://1121627]=note: print w/replies, xml ) Need Help??


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

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; }
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

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://1121627]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others meditating upon the Monastery: (4)
As of 2025-05-22 22:28 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found

    Notices?
    erzuuliAnonymous Monks are no longer allowed to use Super Search, due to an excessive use of this resource by robots.