DEV Community

Marco Servetto
Marco Servetto

Posted on

Advent of code day 12

Here we are again.
Doing this every day is staring to get tiresome, we do not even get a weekend break! :-P

Anyway, today code is fully relying on immutable data structures.
If there is something I've learnt in those years of programming, is that recursive searches + mutability = bugs.

The key idea for part 2 is to define a 'Forbidden' type,
that is a structured datatype keeping track of the more complex condition to keep visiting.
If I tried to encode the new condition on a simple list of visited, I would still be coding.

The idea is that you can 'push' the new visited node on the forbidden instance, and check if we have got in a 'wrong' state.
Alternatively, I could have thrown an error.

For the fine details, yes, the code after 'next=' should probably go in a separate function to be more elegant.

reuse [L42.is/AdamsTowel]
Fs = Load:{reuse[L42.is/FileSystem]}
Big ={class method Bool(S that) = that.toStartUp()==that}
Edges = Collection.map(key=S,val=S.List)
Paths = Data.AddList:Data:{S name, This.List next List={}}
Forbidden = Data:{
  S.List visited=\[S"start"]
  Bool bonus=\.false()
  Bool wrong=\.false()
  method This push(S that) = 
    if Big(that) this 
    else \pushSmall(that)
  method This pushSmall(S that) = {
    X[!this.wrong()]
    limit = that==S"start" || that==S"end"
    visited = that in \visited
    if limit && visited return \with(wrong=Bool.true()) 
    if visited && \bonus return \with(wrong=Bool.true())
    if visited return \with(bonus=Bool.true())
    return \with(visited=\visited.withAlso(right=that))
    }
  }
Count = {class method I (Paths that)={
    if that.name()==S"end" && that.next().isEmpty() return 1I
    return 0I.acc()(for p in that.next() \add(This(p)))
    }}
Visit = {
  class method Paths(S that, Edges e, Forbidden forbidden) =   
    Paths(name=that,
      next= if that==S"end" \() else Paths.List()(
        for ni in e.val(key=that).val() {
          f = forbidden.push(ni)
          if f.wrong() return void
          return \add(This(ni,e=e,forbidden=f))
          }
        )
  )}
Main=(
  input = Fs.Real.#$of().read(\"input")
  imm edges = Edges()(
    for line in input.split(S.nl()) (
      s = line.split(S"-")
      s1 = s()
      s2 = s()
      on1 =\val(key=s1)
      on2 =\val(key=s2)
      v1 = ( if on1 on1.val() else S.List[] ).withAlso(right=s2)
      v2 = ( if on2 on2.val() else S.List[] ).withAlso(right=s1)
      \put(key=s1 val=v1)
      \put(key=s2 val=v2)
    ))
  res=Visit(S"start",e=edges,forbidden=\())
  Debug(Count(res))//3497 and 93686
  )
Enter fullscreen mode Exit fullscreen mode

Finally, not that the problem can only be well posed if there are never two large caves in direct contact, otherwise we could loop forever.

Latest comments (0)