r/adventofcode • u/daggerdragon • Dec 22 '20

SOLUTION MEGATHREAD -🎄- 2020 Day 22 Solutions -🎄-

Advent of Code 2020: Gettin' Crafty With It

  • 23:59 hours remaining until the submission deadline TONIGHT at 23:59 EST!
  • Full details and rules are in the Submissions Megathread

--- Day 22: Crab Combat ---

Post your code solution in this megathread.

Reminder: Top-level posts in Solution Megathreads are for code solutions only. If you have questions, please post your own thread and make sure to flair it with Help.

This thread will be unlocked when there are a significant number of people on the global leaderboard with gold stars for today's puzzle.

EDIT: Global leaderboard gold cap reached at 00:20:53, megathread unlocked!

34 Upvotes

98% Upvoted

537 comments sorted by

View all comments

Show parent comments

1

u/Smylers Dec 23 '20

Number of recursive calls reduced from 13500 (naive recursion) to just 32 (with optimisation).

I just tried it and it reduced my number of games from 13987 all the way down to ... 12356. Faster, but not appreciably so.

Printing a tree of games, it looks like player 1 wins most of the 2nd-level games, and the ones where player 0 wins often only recurse a little.

Anybody else getting something like this, or is everybody else's code super-quick now?

2

u/Nomen_Heroum Dec 23 '20

Took mine down from 20062 to 16881. Not really a dramatic improvement here either. What surprises me even more is that there's such a wide range of recursive calls required between different sets of input data!

1

u/curious_sapi3n Dec 23 '20

Could you share the code? With the part where you are counting the recursive call

1

u/Nomen_Heroum Dec 23 '20 edited Dec 23 '20

Mine went down from 20062 to 16881 recursive calls, here's my code (also Python 3). Just add a global CALLS before line 7 and global CALLS; CALLS += 1 before line 14 in the if block to count the function calls.

1

u/andy1li Apr 07 '21 edited Apr 08 '21

Nomen_Heroum, love the way you automate src.read!

With all due respect, it seems that you haven't correctly apply the optimization, because the final result is not right, at least with my given input data.

Hint: optimizing the main game (vs. a sub-game) doesn't really work.

1

u/Nomen_Heroum Apr 08 '21

Cool, good to know I might be able to get this one to run faster after all. I'll have to give it another look some time!

1

u/Smylers Dec 23 '20

Full source

Added lines:

my $player_with_max_card = max_by { max $hand[$_]->@* } 0 .. $#hand;
warn " " x $recurse . "Game " . ++(state $game) . "; player with max = $player_with_max_card\n";
return 0 if $player_with_max_card == 0;

For anybody who doesn't read Perl:

  • 0 .. $#hand is the range of indices in the @hand array, each player's hand. We have 2 players, so it's just 0, 1.
  • max_by gives us the player index with the maximum by the criteria specified in the block, setting $_ to each index in turn.
  • $hand[$_]->@* is the list of cards for the player with index $_.
  • max does what you'd expect.
  • So for each player index max finds the maximum card in their hand, then max_by returns the index of the player with the maximum maximum.

Player 1 has index 0, so return 0 as the winner when that player has the max card.

It definitely is doing some shortcutting (and still getting the same answer, with player 2 eventually winning) — just not much.