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
)
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.
Top comments (0)