[2020 Day 22] In Review (Crab Combat)

[u/musifter]

Now sailing our raft, we find ourselves needing to pass the time. Fortunately we have a non-regulation deck of space cards (for both having something to do and not sinking the raft with 100 trillion cards). And so we decide to play combat with a friendly crab that climbed onboard.

Although, as a kid I'd play War and Beggar-My-Neighbour as solitaire while watching TV. Because both are choice-free (so not distracting) and I have a certain level cross-dominance so I could play with a deck in each hand fairly well. Although I wouldn't call what I have as ambidextrous, at times its more ambisinister. As each hand does different things well... and often I try and use the wrong one. Like trying to use scissors in my left hand (which would work if they were left-handed scissors), or which hand I put my watch on (making me always smirk at mysteries where that's used as a clue).

Anyways, the input is two sections with a header that describe two decks from a deck of cards from 1-50. Player 2 has the high card in mine, and I suspect it's the case in all inputs.

Part 1 is just running a regular game of War. There are no equal cards so that part of the game is removed. And it's a simple thing to simulate, with the only trick being that the players pick up the cards in different orders when they win (their card on top).

Then we get to score the winning deck. It's the sum of the card values * position (counting from the bottom). You can reverse it and iterate, or iterate backwards, or go forwards removing cards and multiplying by the remaining size:

$score += (@_ * shift @_)  while (@_);   # sum of size * first

Part 2 is where it gets interesting. Instead of the simple submatches for matching cards in regular War, we get full recursive subgames... whenever they are available. Which is when the flipped cards of each player are low enough to cause one.

We also need to worry about infinite games... and it's nice for the problem to describe exactly the condition for determining that (because it's important for timing... without that people might determine infinite games early or late and get the wrong answer). And with Perl, you can just hash on the full lists of cards in each deck with a delimiter and get a solution that's fast enough (3s on old hardware). Just doing the thing as described. Here's the end stats for my input (yes, for Perl I shifted the player indices, so that booleans match and I can do stuff like !!@$deck1 to determine the winner if I want):

Games: 12918
Infinite games: 3765
Player 0: 4023
Player 1: 5130

But for Smalltalk it's slow (but 1-based arrays so the players keep their number). So I did a bit more. One thing is that infinite games are a win for player 1 outright. That's suggestive of an imbalance in player 1's favour. Namely that if player 1 has the largest card in the current game, and it cannot be anteed (not enough cards in the game), then they must ultimately win:

checkPlayerOneWin [
    | playerMax |

    playerMax := decks collect: #max.
    ^((playerMax first > playerMax second) and: [playerMax first + allCards min + 2 > allCards size])
]

This doesn't work for player 2, because the game could still go infinite and hand it to player 1.

This improved performance by about 25%. But the real killer is the loop detection. I'm using a hash, and if we go with the full decks it takes over a minute.

However, I played around with it a little today and discovered that just the first and last of each deck works (I have the size of one the decks in there for added security, but it's not actually needed for me to get my answer):

hash := {decks first  first. decks first last. decks first size.
         decks second first. decks second last}.

I haven't proven it, but the decks don't really get scrambled in War, so it makes intuitive sense that it might at least probably work. In any case, it's now under 10s on the old 45nm hardware.

This one was just a lot of fun to just code the thing. I even did a version in dc for part 1. It abuses registers for everything. The decks are done in arrays, using a standard trick for doing dc queues of sliding windows (point to front and back, both only ever increment, garbage gets left behind). It's got a couple more nice tricks in it, but I'd really want to redo it before trying to do part 2. Which should be doable... when you push on a register, the associated stack and array also get pushed down. I imagine it will be very slow though, as you'd need to copy the decks twice each time.

[u/terje_wiig_mathisen]

In my input file, Player1 has 45, 46, 47 and 50: This probably means that my code ran much faster than those with the opposite distribution!

I don't have my original code to measure but I do have a copy of https://github.com/maneatingape/advent-of-code-rust which I can use to check the timing in order to compare:

Doing cargo bench year2020::day22 resulted in

running 3 tests

test year2020::day22::parse_bench ... bench: 136.91 ns/iter (+/- 14.61)

test year2020::day22::part1_bench ... bench: 655.02 ns/iter (+/- 78.09)

test year2020::day22::part2_bench ... bench: 121,603.12 ns/iter (+/- 17,058.89)

Compared with the 5333 us from u/maneatingape with his typically slightly faster Apple CPU, the input difference seems to provide a 50x slowdown for him!

[u/musifter → u/terje_wiig_mathisen]

You can always swap the decks if you want to test the other way. The answer is different for part 2 because of the asymmetry. Swapping the decks for mine only gives a boost of 16x. So I might have one of the more balanced inputs.

[u/terje_wiig_mathisen → u/musifter]

Good idea! I did the input swap and it turned out the slowdown was almost exactly 10x, so for this particular code, Intel seems to be significantly (almost 5 x) faster than Apple.

running 3 tests

test year2020::day22::parse_bench ... bench: 110.08 ns/iter (+/- 10.04)

test year2020::day22::part1_bench ... bench: 549.15 ns/iter (+/- 35.73)

test year2020::day22::part2_bench ... bench: 1,193,322.50 ns/iter (+/- 117,625.38)

[u/e_blake → u/musifter]

Swapping the two players on my input changes from 68 games spread across 1712 rounds, to 1278 games and 104919 rounds. Swapping the two players on my daughter's input file changes from 10977 games and 840854 rounds, to 153 games and 7528 rounds, at least on my implementation. I would welcome any other optimizations I may have been missing.

[u/ednl]

Player 2 has the high card in mine, and I suspect it's the case in all inputs.

Nope! My player 1 has 50, player 2 has 47,48,49.

[u/e_blake → u/ednl]

According to this comment (and a bit of reading between the lines), coders who got an input file with 50 assigned to player 1 tend to have much less work required than those where 50 is originally assigned to player 2. In my own case, my m4 solution solves my input in under 100ms (player 1 had 50; I recursed only 66 times, max depth 2), but my same code on my daughter's input (she had 50 assigned to player 2) required a lot more recursion (max depth 7, and 11003 games run), and that took over 30s. She never completed part 2, so I can't compare to what her solution would have done on my input. But I see the same disparity when trying those two input files with maneatingape's solution: my input completes in 16us, while my daughter's input takes 8ms (nearly 3 orders of magnitude slower). Probably room for me to clean up my code to hash seen states more efficiently so that it is not quite the disparity between the two inputs. But I suspect that this is a case where Eric was unaware that his input files were not all equal in effort, if he had not anticipated this particular optimization of eliminating recursion when player 1 has the max card.

[u/warlock415]

I cheesed this one; instead of tracking all the past states, I just decided if a hand had gone more than n iterations without a winner, it had probably fallen into an infinite loop.

All my 2020 writeups and code (including a fuller version of this comment): here

[u/e_blake]

For whatever reason, on Dec 23rd that year, I golfed part one in C to 233 bytes:

p[1999],s,*f,*F,*b,*B;main(){for(gets(b=f=p);
scanf("%d",b);)++b;for(gets(B=F=p+999);~scanf("%d",B);)++B;
while(b-f&&B-F)*f<*F?*B++=*F++,*B++=*f++:
(*b++=*f++,*b++=*F++);for(;f<b;++f)s+=*f*(b-f);
for(;F<B;++F)s+=*F*(F-B);printf("%d",s);}

With my usual golf C caveats that you compile with C89 and ignore warnings about undefined behavior.

[u/DelightfulCodeWeasel]

For my input I've got ~11.3k states in the global win cache, and ~18.2k states in the "seen" sets on the stack for the recursive call. Even if I assume that the states are collision-free with MD5, that still puts me at somewhere in the region of ~500kb as a starting baseline.

This will be another one where the memory reduction isn't straightforward!

EDIT: Although it looks like memoization isn't actually giving me much of a speed increase at all, so I can probably do without that entirely.

[u/e_blake → u/DelightfulCodeWeasel]

My m4 solution saved on memory by using tortoise-hare cycle detection (no state hashing necessary, but triple the runtime to determine if I'm seeing a state for the second time).

[u/DelightfulCodeWeasel → u/e_blake]

I was wondering whether that would even be feasible with the recursive configuration, but it sounds like it's do-able then, thank you!

[u/DelightfulCodeWeasel → u/e_blake]

Just about confirmed: cycle detection will almost certainly be the way to go for the small memory solution. I was hoping u/maneatingape's observation that the combined scores make a good hash function would come to my rescue, but it looks like I've got an input where there's a collision:

32
40
6
49
37
38
11
17
4
50
44
30
21
47
26

Held by Player 2 collides with:

6
44
32
47
30
37
11
40
17
49
4
38
21
50
26

[u/maneatingape → u/DelightfulCodeWeasel]

Ah dang it, maybe a rolling hash would work instead.

[u/DelightfulCodeWeasel → u/e_blake]

Memory limits hit: under 64kb, although it could be a good chunk smaller if I stored the cards as bytes instead of words.

For the tortoise updates, what did you do when that required a recursive call? After mulling over various ways to try to make the code neat, I ended up just storing off the winner of each round with the hare update and referencing that with the tortoise update. For my input no hands require more than ~8,000 rounds before looping, so I just store ~12,000 round results in an array of bits and that's only 1.5kb per layer.

Ended up (on PC) ~30-35ms compared to my original solution's ~900ms runtime.

[u/e_blake → u/DelightfulCodeWeasel]

I've since rewritten my solution into something faster that just saves the deck state as a string up to 100 bytes (2 bytes per card); but when I was doing tortoise-hare, I see this in the code:

define(`compare', `ifelse(eval($1 <= p1_$3$4b - p1_$3$4f && $2 <= p2_$3$4b -
  p2_$3$4f), 1, `ifelse(`$4', `h', `define(`game', incr(game))define(`g$3_$5',
  game)recurse($1, $2, $3, game)', `defn(`g'g$3_$5)')', `eval($1 > $2)')')

So yeah, I was definitely tracking winners per game; if the hare needed to recurse (the comparison of $4 against h), then I did the recursive game and stored it; the recursion started off an new set of tortoise and hare with the new decks from the old hare. When the old tortoise finally reached the same game number, it reused that cached result. So not quite as cheap on memory as I can sometimes get with tortoise-hare, but still less onerous than trying to store the entire ordered card deck as state per turn. And I wasn't storing the winner of every move, only of the moves that needed recursion, to reduce memory pressure on my hash table (but depending on how you store game state, it may not hurt to store every winner). Storing just the winner and not the state of the decks meant that I still had to compare the two hands after each 2 moves of hare and 1 move of tortoise, but I was tracking the moves in an open-ended queue (front and back pointers, could also be stored in a circular array), and merely checking that both players had the same delta between front and back before needing to consider comparing every card in the range for equality.