/* 

  Advent of Code 2023 Day 8 in Picat.

  https://adventofcode.com/2023/day/7

  This program was created by Hakan Kjellerstrand, hakank@gmail.com
  See also my Picat page: http://www.hakank.org/picat/

*/

import util.

main => go.

/*
  $ hyperfine 'picat 8.pi'   
  Benchmark 1: picat 8.pi
    Time (mean ± σ):      96.9 ms ±  10.8 ms    [User: 84.1 ms, System: 12.7 ms]
    Range (min … max):    76.2 ms … 112.9 ms    27 run
*/
go =>
  part1,
  part2,
  nl.

/*
  Part 1:
  Benchmark 1: picat -g part1 8.pi
    Time (mean ± σ):      46.4 ms ±   7.3 ms    [User: 31.2 ms, System: 15.0 ms]
    Range (min … max):    28.2 ms …  65.4 ms    40 runs

*/
part1 =>
  File = "8.txt",
  Lines = read_file_lines(File),
  RL = Lines[1],
  Map = new_map([Ns.first=Ns.tail : Line in Lines[3..Lines.len], Ns = Line.split("= (),")]),
  [Node,Ix,RLLen,C] = ["AAA",1,RL.len,0],
  while (Node != "ZZZ")
    N = Map.get(Node),
    Node := cond(RL[Ix] == 'R', N[2], N[1]),
    Ix := 1 + (Ix mod RLLen),
    C := C + 1
  end,
  println(C).

/*
  This was quite harder.
  Benchmark 1: picat -g part2 8.pi
    Time (mean ± σ):     100.4 ms ±   8.2 ms    [User: 84.9 ms, System: 15.4 ms]
    Range (min … max):    85.8 ms … 116.9 ms    26 runs

*/
part2 =>
  File = "8.txt",
  Lines = read_file_lines(File),
  RL = Lines[1],
  RLLen = RL.len,
  Map = new_map(),
  Dests = new_set(), % Destinations
  foreach(Line in Lines[3..Lines.len])
    Ns = Line.split("= (),"),
    [N,Dest] = [Ns.first,Ns.tail],  
    Map.put(N,Dest),
    Dests.put(Dest[1]), Dests.put(Dest[2])
  end,

  % Detect the cycle lengths
  Cycles = [],
  foreach(Node1 in Map.keys, not Dests.has_key(Node1))
     Node = copy_term(Node1),
     [Ix,Found,Count] = [1,false,0],
     New = _,
     while (Found == false, (var(New) ; New != Node1))
       N = Map.get(Node),
       New := cond(RL[Ix] == 'R', N[2], N[1]),       
       if New.last == 'Z' then Found := true end,
       Node := New,
       Count := Count + 1,
       Ix := 1 + (Ix mod RLLen)
     end,
     Cycles := Cycles ++ [Count]
  end,
  % println(cycles=Cycles=Cycles.len),
  println(lcm(Cycles)).

lcm(X,Y)= abs(X*Y)//gcd(X,Y).
lcm(X,Y,LCM) => LCM = abs(X*Y)//gcd(X,Y).

lcm(List) = fold(lcm,1,List).