Beefy Boxes and Bandwidth Generously Provided by pair Networks
more useful options
 
PerlMonks  

comment on

( [id://3333]=superdoc: print w/replies, xml ) Need Help??
The round 1A happened at unreasonable hours (around 3AM) for my timezone, so I skipped it. The next day, I checked the problems to see what I could expect in the 1B or 1C rounds. The first problem was called Pylons and it took me a whole day to solve.

It starts simply. We have a grid of a given size and we want to visit each cell in it exactly once. In each turn, we can move in any direction, we just can't stay in the same row, column, or diagonal.

I started with a brute force solution just to see what's possible. After several hours, I was able to guess whether any solution was possible for the given size of the grid, but I wasn't able to find a solution within the time limit for the larger grids.

In the end, I gave up and started to read the Analysis. When they mentioned "random solution should work", I stopped reading and returned to my code. In the brute force solution, I changed the loops

for my $row (1 .. $row_size) { for my $column (1 .. $column_size) { ... } }

into

use List::Util qw{ shuffle }; # ... for my $row (shuffle(1 .. $row_size)) { for my $column (shuffle(1 .. $column_size)) { ... } }

but my program was still timing out. I created a special input file to test all the possible inputs (the maximal size was 20×20) just to notice the program got stuck at a different size every time. I thought: "Maybe there's a random seed that would go through all the inputs smoothly." And I started testing srand $RAND for 0, 1, 2, 3, ... When $RAND was 48, my program solved the first 93 input lines before getting stuck!

And then I had another idea: maybe there's no universal random seed for all the inputs, but each input can have one good random seed. So I wrote a testing program that tried to find the solution for every given size with various random seeds. It set up an alarm timeout of 1 second before trying a solution and only continued in trying the following seed if it timed out.

#!/usr/bin/perl use warnings; use strict; use feature qw{ say }; local $SIG{ALRM} = sub { system killall => '1a1.pl'; die }; for my $r (2 .. 20) { SIZE: for my $c (2 .. 20) { open my $OUT, '>', 'x1' or die $!; say {$OUT} 1; say {$OUT} "$r $c"; close $OUT; for my $rand (1 .. 100) { print "$r $c $rand\n"; eval { alarm 1; 0 == system '1a1.pl', $rand, 'x1'; } and do { print "$r $c $rand\n"; next SIZE }; } say "NOT FOUND"; } }

To my surprise, most of the inputs performed well with the random seed 1. So I used it as the default and specified the exceptions in a hash:

my %srand = ('3 16' => 2, '4 10' => 2, '4 17' => 3, '4 19' => 3, '5 15' => 5, # ... );

I then just adjusted the srand before I started populating the grid.

srand ($srand{"$rows $columns"} || 1); $grid = solve($rows, $columns);

And this solution passed the tests.

map{substr$_->[0],$_->[1]||0,1}[\*||{},3],[[]],[ref qr-1,-,-1],[{}],[sub{}^*ARGV,3]

In reply to Google Code Jam 2019 Round 1A Problem 1: Pylons by choroba

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":



  • Are you posting in the right place? Check out Where do I post X? to know for sure.
  • Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:
    <code> <a> <b> <big> <blockquote> <br /> <dd> <dl> <dt> <em> <font> <h1> <h2> <h3> <h4> <h5> <h6> <hr /> <i> <li> <nbsp> <ol> <p> <small> <strike> <strong> <sub> <sup> <table> <td> <th> <tr> <tt> <u> <ul>
  • Snippets of code should be wrapped in <code> tags not <pre> tags. In fact, <pre> tags should generally be avoided. If they must be used, extreme care should be taken to ensure that their contents do not have long lines (<70 chars), in order to prevent horizontal scrolling (and possible janitor intervention).
  • Want more info? How to link or How to display code and escape characters are good places to start.
Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others taking refuge in the Monastery: (4)
As of 2024-03-29 10:10 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found