in reply to Google Code Jam 2019 Round 1A Problem 1: Pylons

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.

<Reveal this spoiler or all in this thread>

Replies are listed 'Best First'.
Re^2: Google Code Jam 2019 Round 1A Problem 1: Pylons
by LanX (Saint) on Apr 15, 2019 at 17:01 UTC
    > ( 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

[reply]

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

[reply]
        "JAM" it certainly is. ;)

        But my point is a bit different, I once participated at a golfing competition where the winner had impossibly short code.

        Turned out he just hardcoded the desired result into a print.

        Precomputing all results for a finite input set indeed looks like ... jam.

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

[reply]

In Section Meditations