https://adventofcode.com/2021/day/21
For day 21, we played a "dice game" with two chess pawns.
The game was a two player game, with a track with 10 positions,
labeled 1 through 10, and the data for the puzzle was the player's
starting positions.
example=:{{)n
Player 1 starting position: 4
Player 2 starting position: 8
}}
Rather than write a parser for this, I used the starting positions
directly -- for this example: 4 8.
The game itself was to roll a die three times, move that many
positions forward and then add the resulting position to the player's
score (which starts at 0). The first player to reach 1000 wins.
Anyways, for part A of the puzzle, our "die" was a "deterministic 100
sided die". This die first rolls a 1 and then rolls a 2 and then a 3
and... so on up to 100 after which the next roll is 1. And our answer
for part A was the loser's score multiplied by the number of times the
die was rolled.
My implementation for this was brute force and uninspired:
NB. deterministic die
det=: 100 NB. value before start
k=: 0 NB. count of times rolled
roll=: {{
k=: k+1
det=: 1+100|det
}}
NB. roll die 3 times
d3=: {{
+/roll"0 i.3
}}
NB. move
m10=: {{
1+10|y-1
}}
a21=:{{
p=: y
s=: 0 0
while. 1 do.
assert. k < 10000 NB. avoid infinite loops
if. 1000<:>./s=: s+ 1 0 *p=:m10 p+1 0 * d3'' do. done p return.end.
if. 1000<:>./s=: s+ 0 1 *p=:m10 p+0 1 * d3'' do. done p return.end.
end.
}}
NB. calculate puzzle value
done=: {{
k*<./s
}}
Thinking about this, I could have instead done something like
play=: * (=i.2) $~ #
A21=: {{
die=: 1+100|i.6e3
rolls=: _3 +/\ die
positions=: 11 |&.<: y+"1 play+/\play rolls
scores=:+/\play positions
limit=: 1 i.~1000 <: >./"1 scores
(3*1+limit)*<./limit{scores
}}
Is that more comprehensible though? I am not sure...
For part B, instead of a 100 sided deterministic die, we had a 3 sided
"dirac die". Every time we "roll" this die, the universe splits into
three copies, with the die having value 1, 2 or 3 in those three
universes. And, for part B, the puzzle was: count the number of
universes won by the player who wins the most times in these
universes.
Also, to keep this game "simple" a win was a score of 21 instead of a
score of 1000.
So, for this game, we needed to track the count of universes in each
"has not yet won" state. That's a score of 0 .. 20 and a board
position of 1..10. We do not care about the history of a universe
prior to reaching that state except in the sense that we are counting
those universes. We can also ignore universes after we have counted
their wins.
I approached that this way:
NB. we only care about the counts of "universes"
NB. each player's position and score marks a universe
NB. multiple copies of "identical" universe occur because
NB. of differing histories of die rolls reaching that state
map=:{{
dirac=. ,1 2 3 +/1 2 3+/1 2 3
c=. #/.~ dirac
i=. ~.dirac
'sc in' =.|:21 10 #:i.210 NB. sc: score, in: index into 1+i.10
'SC CN IN'=. 0 1 |: ((sc,"0/c),"1 0]_1)+"1(1+10|in+/i)*"0 1]1 0 1
NB. score before: 0..20, each move adds a number in range 1..10 to score
|:CN {{x y}310$0}}"1 IN+10*SC
}}''
So, basically, each row of this matrix represents a track position and
a score, and each column represents the next track position and score,
and the values are the number of transitions between that row and that
column. It's mostly zeros, but if we summarize the dice (how much they
add to the track position and the count for that change), the counts
we see here are the values which go into the non-zero parts of the
transition map:
(~.,.#/.~),1 2 3 +/1 2 3+/1 2 3
3 1
4 3
5 6
6 7
7 6
8 3
9 1
With that map from one collection of universes to the next, I could
write a step function representing a player taking their turn:
NB. y is universe counts
NB. leading dimension of y represents current player
NB. scores over 20 end the game and get counted
NB. x is the player id for this move
adv=: {{
next=. map +/ .*y
wins=:((x{wins)+x:+/,210}. next) x} wins
210{. next
}}
And, my puzzle solution starts with a single universe (based on the
starting position and a score of zero), and runs until every universe
has won, then reports on the largest number of wins for any player:
b21=:{{
wins=: 0 0x
uni=. 1 (<<:y)} 210 210$0
while. 0 < >./,uni do.
uni=. |: 1 adv |: 0 adv uni
end.
>./wins
}}
With the example data:
b21 4 8
444356092776315
Possibly the only remaining tricky thing in b21 itself was that I'm
using position indices (0 .. 9) rather than position labels (1 .. 10)
to indicate the position of pawns on the circular track.
Anyways, I hope this made sense.
Thanks,
--
Raul
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
