Beefy Boxes and Bandwidth Generously Provided by pair Networks
go ahead... be a heretic
 
PerlMonks  

Google Code Jam 2019 Round 1A Problem 1: Pylons

by choroba (Bishop)
on Apr 14, 2019 at 20:56 UTC ( #1232558=perlmeditation: 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]

Replies are listed 'Best First'.
Re: Google Code Jam 2019 Round 1A Problem 1: Pylons
by LanX (Archbishop) on Apr 16, 2019 at 00:05 UTC
    Annoying problem, the edge cases for small solutions are killing me.

    Anyway sufficiently big grids ( $R,$C >4 )are easily constructed

    In the following for simplicity we assume $R >= $C (otherwise just swap the result).

    First starting form 0/0 you do $R knight moves (+1,+2) module $C till each row was visited.

    It's obvious that successive moves can't collide here.

    - (5,4) -------------------- 1 0 0 0 0 0 2 0 3 0 0 0 0 0 4 0 5 0 0 0

    Now we have a pattern which can be moved horizontally by a value $shift.

    That is point p6 = (r6,c6) = (r1, c1 + $shift)

    For $shift= 1 this results in

    - (5,4) -------------------- 1 6' 11 16 12 17 2 7' 3 8' 13 18 14 19 4 9' 5 10' 15 20

    and it's obvious that a shifted group like p6..p10 can't collide because the original pattern in p1..p5 didn't.

    The only possible collision happen between the last element of a group and the first of the following, i.e p5 -> p6 are not allowed to be on the same column, to avoid vertical collision

    Diagonal and horizontal collision can't happen, since we supposed $R > $C, i.e the diagonals starting from the bottom row cant reach the top row.

    So in case p5 was blocking the spot right of p1, we could easily rotate all to the left by using $shift = -1.

    that's demonstrated in the following case

    - (9,5) -------------------- 1 0 0 0 0 0 0 2 0 0 0 0 0 0 3 0 4 0 0 0 0 0 0 5 0 6 0 0 0 0 0 0 7 0 0 0 0 0 0 8 0 9 0 0 0 - (9,5) -------------------- -1 shift to the left 1 37 28 19 10 20 11 2 38 29 39 30 21 12 3 13 4 40 31 22 32 23 14 5 41 6 42 33 24 15 25 16 7 43 34 44 35 26 17 8 18 9 45 36 27

    Now how about the other cases and does $shift always need to be 1 or -1?

    No, but 1 and -1 are easy since they obviously guaranty to fill the whole grid before returning to start.

    But so do all numbers which are prime to $C: In the case above shifts 2 = -3 and 3 =-2 modulo $C=5 would have worked too.

    But a shift 2 for $C=4 would create a loop (which is actually only complicating the solution to another shift)

    The remaining solvable edge cases for $R==$C with $C>4 are done by choosing $shift=1. The diagonals reach the top row, but never the spot to right of the start if $C>4.

    This is not the case for $R==$C==4 is quite special, exactly one diagonal collisions happens, between opposing corners.

    - (4,4) -------------------- 1 5 9 13* 10 14 2 6 3 7 11 15 12* 16 4 8

    This is easily fixed by renumbering the sequence and starting at the right upper corner. Hence 13 =>1 .. 16 =>4 , 1=>5 .. 12=>16 and no succeeding points can ever collide

    Possible solutions with $C <=4 requires swapping rows and columns and special shift values

    like

    - (2,5) -------------------- $shift = -1 1 0 0 0 0 0 0 2 0 0

    or

    - (3,5) -------------------- $shift = 3 1 0 0 0 0 0 0 2 0 0 0 0 0 0 3

    So how valuable are these results?
    • no random jumps needed
    • proven to work for all big grids
    • very fast
    • the remaining edge cases are very few
    • those can be either hard coded or brute forced.
    That's it, now I want my live back :)

    Cheers Rolf
    (addicted to the Perl Programming Language :)
    Wikisyntax for the Monastery FootballPerl is like chess, only without the dice

Re: Google Code Jam 2019 Round 1A Problem 1: Pylons
by tybalt89 (Vicar) on Apr 15, 2019 at 15:09 UTC

    Crummy problem :( ----- (because random)

    This is a permutation problem with a weak ordering requirement.

    "shuffle" the grid indexes, about half the time always taking the first non-conflict from the array of empty indexes gives a valid order, if not, reshuffle till it works.
    I am seeing on average slightly less than one reshuffle per grid solution over all the grids.

    Processes all 361 grids in under 2 seconds total typically.

    ( slight cheat: All IMPOSSIBLEs are hard coded (HINT: there are very few) :)

    It's not in final submit form because I wanted to test all grid sizes.

      > ( slight cheat: All IMPOSSIBLEs are hard coded (HINT: there are very few) :)

      Lemme guess, the remains were proven to be POSSIBLES by brute-force searching (N.B. only inside the max-boundaries) and not by applying mathematical reasoning?

      Cheers Rolf
      (addicted to the Perl Programming Language :)
      Wikisyntax for the Monastery FootballPerl is like chess, only without the dice

        It is a "code jam" and not a "math jam" :)

Re: Google Code Jam 2019 Round 1A Problem 1: Pylons
by LanX (Archbishop) on Apr 14, 2019 at 21:58 UTC
    I don't think you need rand, when dealing with bigger grids.

    Hint: do you know how the knight moves in chess? ;-)

    Smaller grids can be brute forced.

    Cheers Rolf
    (addicted to the Perl Programming Language :)
    Wikisyntax for the Monastery FootballPerl is like chess, only without the dice

      Feel free to solve the problem. Knight's moves aren't enough for some grid sizes.

      map{substr$_->[0],$_->[1]||0,1}[\*||{},3],[[]],[ref qr-1,-,-1],[{}],[sub{}^*ARGV,3]
        > Knight's moves aren't enough for some grid sizes.

        which sizes bigger 4x4?

        It's a bit more complicated, but since it's an open competition I don't wanna reveal too much.

        > Feel free to solve the problem.

        no time to code this at the moment.

        (you know mathematicians are like eunuchs ... ;)

        Cheers Rolf
        (addicted to the Perl Programming Language :)
        Wikisyntax for the Monastery FootballPerl is like chess, only without the dice

        update

        see here

Re: Google Code Jam 2019 Round 1A Problem 1: Pylons
by tybalt89 (Vicar) on Apr 15, 2019 at 14:14 UTC

    Is the round over, so it would be OK to post solutions?

      Yes, the part A is over. You can verify your solution in the "Archive" part of the Code Jam site and you can post it wherever else you like. The round isn't over, there'll be parts B and C running in different time slots so people from other time zones can participate easily. The following rounds will only have one part.

      map{substr$_->[0],$_->[1]||0,1}[\*||{},3],[[]],[ref qr-1,-,-1],[{}],[sub{}^*ARGV,3]
Re: Google Code Jam 2019 Round 1A Problem 1: Pylons
by QM (Parson) on Apr 18, 2019 at 10:26 UTC
    Your link to Pylons doesn't work, is it broken / stale?

    -QM
    --
    Quantum Mechanics: The dreams stuff is made of

      What do you mean by "doesn't work"? I see all the tasks, Pylons being one of them, even if not logged in.

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

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: perlmeditation [id://1232558]
Approved by marto
Front-paged by marto
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others chanting in the Monastery: (5)
As of 2019-04-20 10:54 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    I am most likely to install a new module from CPAN if:
















    Results (109 votes). Check out past polls.

    Notices?
    • (Sep 10, 2018 at 22:53 UTC) Welcome new users!