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.
memoization Article's
30 articles in total
The intricacies of implementing memoization in Ruby
read article
Memorização em JavaScript
read article
When do (and don’t) children re-render in React?
read article
Memoization in React: When It Helps and When It Hurts
read article
Never call the same function twice (with memoization)
read article
Optimizing React Performance with Memoization and React.memo
read article
Optimizing React Component Performance with Memoization and React.memo
read article
Optimizing React Performance with memoization and React.memo
read article
Optimizing React Performance with Memoization and React.memo
read article
Optimizing React Component Performance with Memoization
read article
Кеширования в React - все ли так однозначно?
read article
Understanding and Implementing Memoization in React
read article
Caching & Memoization with state variables
read article
How to implement Memoization in your React projects
read article
Memoization in JavaScript
read article
Mastering React: A Deep Dive into Memoization and Component Optimization
read article
How to Use Memoization in React for Better Performance
read article
Deep Dive into Functional Programming in Javascript
read article
Demystifying React Memoization: Understanding React.memo() and the useMemo hook
read article
JavaScript Memoization
read article
Maximizing Performance: How to Memoize Async Functions in JavaScript
read article
Retos JS. Calculando factoriales muy grandes con JS.
read article
Memoizing DataFrame Functions: Using Hashable DataFrames and Message Digests to Optimize Repeated Calculations
read article
Memoize a React component
read article
Memoization in JavaScript and React
read article
Memoization in Ruby
read article
Advent of code Day 21
currently reading
Understanding Memoization in Javascript
read article
Reselect, but in OCaml
read article
Memoization in Javascript
read article
Featured ones: