/* 

  Advent of Code 2024 in Picat.

  Problem 10
  https://adventofcode.com/2024/day/10

  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

  Benchmark 1: picat -g go 10.pi
    Time (mean ± σ):      55.0 ms ±   8.0 ms    [User: 39.2 ms, System: 15.7 ms]
    Range (min … max):    31.9 ms …  65.7 ms    40 runs

*/
go =>
  part1,
  part2.

/*
  Hyperfine

  Benchmark 1: picat -g part1 10.pi
    Time (mean ± σ):      46.3 ms ±   8.7 ms    [User: 29.8 ms, System: 16.5 ms]
    Range (min … max):    22.5 ms …  59.2 ms    53 runs

*/
part1 => 
  File = "10.txt",
  M = {Line.map(to_int): Line in read_file_lines(File)},
  N = M.len,
  Starts = [[I,J] : I in 1..N, J in 1..N, M[I,J] == 0],
  println([A.map(last).remove_dups.len : [I,J] in Starts, A=findall(P,P=p(M,N,I,J))].sum).

/*
  Hyperfine 

  Benchmark 1: picat -g part2 10.pi
    Time (mean ± σ):      45.4 ms ±   8.4 ms    [User: 27.5 ms, System: 17.8 ms]
    Range (min … max):    19.6 ms …  57.9 ms    76 runs

*/
part2 => 
  File = "10.txt",
  M = {Line.map(to_int): Line in read_file_lines(File)},  
  N = M.len,
  Starts = [[I,J] : I in 1..N, J in 1..N, M[I,J] == 0],
  println([findall(Path,Path=p(M,N,I,J)).len : [I,J] in Starts].sum),
  nl.


p(M,N,I,J) = Path =>
    Path = [],
    X = I, Y = J,  
    Val = 0,  
    while (Val < 9)
      Ns = neibs(M,N,N,X,Y,Val+1),
      member([X2,Y2],Ns),
      Path := Path ++ [[Val,X2,Y2]],
      X := X2,
      Y := Y2,
      Val := Val + 1
    end,
    Val == 9,    
    Path := Path ++ [[Val,X,Y]].

% Neibours of M[I,J] that have the value Next
neibs(M,Rows,Cols,I,J,Next) = [[I+A,J+B] : A in -1..1, B in -1..1,
                               abs(A+B) == 1, % just left/right/up/down
                               I+A >= 1, I+A <= Rows, J+B >= 1, J+B <= Cols,
                               M[I+A,J+B] == Next].