/* 

  Bridge crossing in Picat.

  Inspired by http://stackoverflow.com/questions/1144207/bridge-crossing-puzzle
  using a DP approach.

  Note: This only calculates the optimal time, not the complete plan.


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

*/


% import util.
% import cp.


main => go.


go =>
  
  N = 4,
  Band = [1, 2, 5, 10].sort(),
  println("The total time taken to cross the bridge is:"),
  println(total_time(Band, N)),
 
  nl.


go2 =>
  
  N = 1000,
  _ = random2(),
  Band = [1+ random() mod N : _ in 1..N ].sort(),
  println(band=Band),
  println("The total time taken to cross the bridge is:"),
  println(total_time(Band, N)),
 
  nl.



total_time(Band, N) = Res =>
   println($total_time(Band, N)),
   
   if N < 3 then
      Res := Band[N]
   elseif N = 3 then
      Res := Band[1] + Band[2] + Band[3]
   else
      Temp1 = Band[N] + Band[1] + Band[N - 1] + Band[1],
      Temp2 = Band[2] + Band[1] + Band[N] + Band[2],
      if Temp1 < Temp2 then
         Res := Temp1 + total_time(Band, N - 1)
      elseif Temp2 < Temp1 then
         Res := Temp2 + total_time(Band, N - 1)
      else
         Res := Temp2 + total_time(Band, N - 1)
      end
    end.