dev-resources.site
for different kinds of informations.
Advent of code Day 21
Published at
12/21/2021
Categories
adventofcode
adventofcode2021
caching
memoization
Author
marcoservetto
Author
13 person written this
marcoservetto
open
The two parts for the problem of today are well divided, so I will present them one at a time.
Or, if you prefer, you can just look to my comments on you tube:
(https://www.youtube.com/watch?v=61v1SNA79V0)
Part 1 is really trivial.
Note the trick with the modulo arithmetic, where we store a position that is 1 less than the intended position of the player.
D100 = Data:{
var I rolled = 0I
var I seed = 0I
mut method I roll()=(
\rolled(\rolled+1I)
\seed((if \seed>=100I 0I else \seed)+1I)
\seed
)
}
Player = Data:{
var I pos
var I points = 0I
mut method Void turn(mut D100 that) =(
tot = that.roll()+that.roll()+that.roll()
\pos((\pos+tot).mod(10I)) //pos from 0--10, real pos is +1
\points(\points+\pos+1I)
)
read method Bool won() = \points>=1000I
}
Main=(
p1 = Player(pos=0I) //1-1
p2 = Player(pos=2I) //3-1
dice = D100()
while !p1.won() && !p2.won() (
p1.turn(dice)
if !p1.won() (p2.turn(dice))
)
if p1.won() (
Debug(S"p2 loses for %p2.points(), %dice.rolled(), %(p2.points()*dice.rolled())")
)
if p2.won() (
Debug(S"p1 loses for %p1.points(), %dice.rolled(), %(p1.points()*dice.rolled())")
)
//p1 loses for 671, 1338, 897798
)
Part 2 is much more interesting, and it was feasible thanks to @Cache.Lazy; in this way our 'recursive' call may simply return a pre-computed value.
Report = Data:{
Num p1Wins
Num p2Wins
method Bool open() = \p1Wins+\p2Wins==0Num
method This +(This that) = This(
p1Wins=this.p1Wins()+that.p1Wins(),
p2Wins=this.p2Wins()+that.p2Wins()
)
}
State = Data:{
I p1Pos
I p2Pos
I p1Score = 0I
I p2Score = 0I
method This turn(I p1Roll) = (
(p1Pos0,p2Pos0,p1Score0,p2Score0) = this
p1Pos = (p1Pos0+p1Roll).mod(10I) //from 0--10, real pos is +1
p1Score = p1Score0+p1Pos+1I
This(p1Pos=p1Pos,p2Pos=p2Pos0,
p1Score=p1Score,p2Score=p2Score0)
)
method This turn(I p2Roll) = (
(p1Pos0,p2Pos0,p1Score0,p2Score0) = this
p2Pos = (p2Pos0+p2Roll).mod(10I) //from 0--10, real pos is +1
p2Score = p2Score0+p2Pos+1I
This(p1Pos=p1Pos0,p2Pos=p2Pos,
p1Score=p1Score0,p2Score=p2Score)
)
method Report directWin() = {
(p1Pos,p2Pos,p1Score,p2Score) = this
X[p1Score<21I || p2Score<21I]
if p1Score>=21I return \(p1Wins=1\ p2Wins=0\)
if p2Score>=21I return \(p1Wins=0\ p2Wins=1\)
return \(p1Wins=0\ p2Wins=0\)
}
@Cache.Lazy method Report wins() = {
Debug(this)
var res = this.directWin()
if !res.open() return res
r = Range(1I to=4I)
for a1 in r,for a2 in r,for a3 in r {
stateA = this.turn(p1Roll=a1+a2+a3)
resA = stateA.directWin()
if !resA.open() return res+=resA
return for b1 in r,for b2 in r,for b3 in r {
stateB = stateA.turn(p2Roll=b1+b2+b3)
resB = stateB.directWin()
if !resB.open() return res+=resB
return res+=stateB.wins()
}
}
return res
}
}
Main = (
s = State(p1Pos=0I,p2Pos=2I)
Debug(s.wins())
//Report(p1Wins=48868319769358,p2Wins=22432440913119)
)
}
What do you think? with minor modifications I could combine automatic parallelism and automatic caching for an even faster version.
adventofcode2021 Article's
13 articles in total
Advent of code Day 20
read article
Advent of code Day 11
read article
Advent of code Day 18
read article
Advent of code, last puzzle
read article
Advent of code Day 17
read article
Advent of code day 16
read article
Advent of code Day 21
currently reading
Advent of code Day 9
read article
Advent of code Day 15
read article
Advent of code day 14: A puzzle too good for me.
read article
Advent of code Day 13
read article
Advent of code day 12
read article
Advent of code, Day 10
read article
Featured ones: