Beefy Boxes and Bandwidth Generously Provided by pair Networks
Syntactic Confectionery Delight
 
PerlMonks  

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

by choroba (Bishop)
on Mar 28, 2015 at 08:15 UTC ( #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
Node Status?
node history
Node Type: note [id://1121627]
help
Chatterbox?
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others scrutinizing the Monastery: (4)
As of 2017-12-17 12:09 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    What programming language do you hate the most?




















    Results (464 votes). Check out past polls.

    Notices?