/* 

  Advent of Code 2023 Day 21 in Picat.

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

  Part 1

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

*/

import util.

main => go.

/*
  Part 1: 
  $ hyperfine 'picat 21.pi'
  Benchmark 1: picat 21.pi
    Time (mean ± σ):     138.4 ms ±   9.2 ms    [User: 119.4 ms, System: 19.0 ms]
    Range (min … max):   129.7 ms … 160.9 ms    17 runs

*/
go =>
  part1,
  nl.

part1 => 

  File = "21.txt",

  M = read_file_lines(File),
  Rows = M.len,
  Cols = M[1].len,

  Start = _,
  foreach(I in 1..Rows, J in 1..Cols, break(nonvar(Start)), M[I,J] == 'S' )
    Start := [I,J]
  end,

  NumSteps = cond(Rows < 20, 6, 64),
  Found = [Start],
  Step = 0,
  NumCovered = 0,  
  while (Step < NumSteps)
    Found := find_new(M,Rows,Cols,Found),
    NumCovered := Found.len,
    Step := Step + 1
  end,
  println(NumCovered).


find_new(M,Rows,Cols,Found) = NewFound =>
  NewFound = [],
  Seen = new_set(),
  ds(Ds),
  foreach([PI,PJ] in Found)
    foreach([DI,DJ] in Ds,
                     NewI = PI + DI, NewI >= 1, NewI <= Rows,
                     NewJ = PJ + DJ, NewJ >= 1, NewJ <= Cols,
                     not Seen.has_key([NewI,NewJ]), M[NewI,NewJ] != '#')
       NewFound := [[NewI,NewJ]|NewFound],
       Seen.put([NewI,NewJ])
     end
  end.
  
ds([[-1,0],[1,0],[0,-1],[0,1]]).