DEV Community

Marco Servetto
Marco Servetto

Posted on

Advent of code 6, still interesting!

Ok, Advent of code 6 is interesting:
first they describe you a very precise but inefficient algorithm, then they ask you to compute the result for a number that can not work with normal 32bit ints nor with their algorithm.
So, first I implemented it following their algorithm to the letter:

Day = {
  class method Void (mut I.List that) =
    for var i in that.#vals(0I to=that.size()) (
      if i!=0I (i-=1I)
      else (i:=6I, that.add(8I))
      )
  class method Void (mut I.List that, I rounds) =
    for i in Range(rounds) This(that)
  }
MainPart1=(
  fs = Fs.Real.#$of()
  input = fs.read(\"input")
  fishs = I.List()(for s in input.split(S",")
    \add(\(string=s.trim())))//last one ends with nl
  Debug(fishs.size())
  Day(fishs, rounds=80I)
  Debug(fishs.size())
  )
Enter fullscreen mode Exit fullscreen mode

There is something very interesting in my for loop:

for var i in that.#vals(0I to=that.size()) (
  ..i:=6I, that.add(8I).. )
Enter fullscreen mode Exit fullscreen mode

I both edit the number in place and I add to the end of the list.
But, we need not to give a round to those new fishes we just spawn. Thus, I'm using #vals, to limit the iteration to the number of fishes present at the START of the day.

Then, for part two:
Of course this algorithm is better done with a map.
Also, since those numbers grow quite a lot, we are going to use a map from I (indexes,32bit integers) to Num (arbitrary precision rationals)
that is, a fish age -> how many fishes at that age.
Since we just have a finite and small number of ages, we can make sure that there is an entry for all ages (may be with zero val)
and we can simply examine all ages case by case to move forward one day.
This mindset produces the following code:

Map = Collection.map(key=I,val=Num)
Day2={
  class method Void (mut Map that) = (
      (val0) = that.val(key=0I)
      (val1) = that.val(key=1I)
      (val2) = that.val(key=2I)
      (val3) = that.val(key=3I)
      (val4) = that.val(key=4I)
      (val5) = that.val(key=5I)
      (val6) = that.val(key=6I)
      (val7) = that.val(key=7I)
      (val8) = that.val(key=8I)
      that.put(key=8I, val=val0)
      that.put(key=7I, val=val8)
      that.put(key=6I, val=val7+val0)
      that.put(key=5I, val=val6)
      that.put(key=4I, val=val5)
      that.put(key=3I, val=val4)
      that.put(key=2I, val=val3)
      that.put(key=1I, val=val2)
      that.put(key=0I, val=val1)
      )
  class method Void (mut Map that, I rounds) =
    for i in Range(rounds) This(that)
  class method Num tot(mut Map that) = (
    var res=0Num
    for (val) in that ( res+=val )
    res
    )
  }
MainPart2=(
  fs = Fs.Real.#$of()
  input = fs.read(\"input")
  map=Map()((
    for i in Range(9I) ( \put(key=i,val=0Num) )
    for s in input.split(S",") (
      age = I(string=s.trim())
      (val) = \val(key=age)
      \put(key=age,val=val+1Num)
      )
    ))
  Debug(Day2.tot(map))
  Day2(map, rounds=256I)
  Debug(Day2.tot(map))//more then a trillion in my case
  )
Enter fullscreen mode Exit fullscreen mode

By declaring the 9 ages as 9 variables on the stack, I'm de facto unloading the map on the stack, and then I fill it up again.
This code is repetitive but I think it is the good kind of repetitive code: it is all tightly together, and can not possibly start deriving in different versions over space and time.

Also, note how I initialize the map in the main:
This is the more 42ish way to initialize a map, last time I have shown a more conventional one to be more understandable.

See you tomorrow for the next one!
If you like those posts, consider checking out the main 42 website
(https://L42.is) or the youtube channel (https://www.youtube.com/MarcoServetto)
By the way, new video out today :) (https://www.youtube.com/watch?v=47WdqInqKd0)

Discussion (0)