/* 

  Can you hop to the lily pad? in Picat.

  From Can you hop to the lily pad?
  https://laurentlessard.com/bookproofs/can-you-hop-to-the-lily-pad/
  """
  You are a frog in a pond with an infinite number of lily pads in a 
  line, marked "1," "2," "3," etc. You are currently on pad 2, and 
  your goal is to make it to pad 1. From any given pad, there are 
  specific probabilities that you’ll jump to another pad: Whenever you 
  are on pad k, you will hop to pad k-1 with probability 1/k, and you 
  will hop to pad k+1 with probability (k-1)/k.

  What is the probability that you will ultimately make it to pad 1? 
  """

  (Via Pascal Bercker).

  Cf my Gamble model gamble_hop_the_lily_pad.rkt
  My (exact but with a limit of 25) Gamble model gives p=0.6321039908078091,
  which is suspiciously near 1-1/exp(1) (~0.63212055882855767840).
  The difference is 0.00001656802074857840.


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

*/

import ppl_distributions, ppl_utils.
import util.
% import ordset.

main => go.

/*
  * Limit = 20

  var : last pad
  Probabilities:
  1: 0.6356000000000001
  19: 0.0875500000000000
  21: 0.0872000000000000
  17: 0.0663500000000000
  23: 0.0432000000000000
  15: 0.0399000000000000
  13: 0.0203000000000000
  11: 0.0118500000000000
  9: 0.0051000000000000
  7: 0.0018000000000000
  5: 0.0007000000000000
  3: 0.0004500000000000
  mean = 7.3079

  var : len
  Probabilities:
  1: 0.5028000000000000
  21: 0.3644500000000000
  3: 0.0837000000000000
  5: 0.0272000000000000
  7: 0.0117000000000000
  9: 0.0054500000000000
  11: 0.0025500000000000
  13: 0.0011000000000000
  15: 0.0007500000000000
  17: 0.0002000000000000
  19: 0.0001000000000000
  mean = 8.7332

  var : p
  Probabilities:
  true: 0.6356000000000001
  false: 0.3644000000000000
  mean = 0.6356


  * Limit = 100

  var : last pad
  Probabilities:
  1: 0.6311000000000000
  97: 0.0660500000000000
  95: 0.0622500000000000
  99: 0.0537500000000000
  93: 0.0522500000000000
  91: 0.0375500000000000
  101: 0.0323000000000000
  89: 0.0232500000000000
  87: 0.0142000000000000
  103: 0.0103000000000000
  85: 0.0075500000000000
  83: 0.0051500000000000
  81: 0.0019000000000000
  79: 0.0009000000000000
  77: 0.0005000000000000
  73: 0.0004000000000000
  75: 0.0002500000000000
  71: 0.0002500000000000
  69: 0.0000500000000000
  63: 0.0000500000000000
  mean = 35.5821

  var : len
  Probabilities:
  1: 0.5024500000000000
  101: 0.3689000000000000
  3: 0.0800500000000000
  5: 0.0280500000000000
  7: 0.0108500000000000
  9: 0.0049500000000000
  11: 0.0027000000000000
  13: 0.0011500000000000
  17: 0.0003500000000000
  15: 0.0003500000000000
  19: 0.0001500000000000
  23: 0.0000500000000000
  mean = 38.3221

  var : p
  Probabilities:
  true: 0.6311000000000000
  false: 0.3689000000000000
  mean = 0.6311


*/
go ?=>
  reset_store,
  run_model(20_000,$model,[show_probs,mean]),
  nl,
  % show_store_lengths,nl,
  % fail,
  nl.
go => true.
  
hop(K,N,Target,Limit) = Res =>
  if K == Target ; N > Limit then
    Res = [K,N]
  else
    H = categorical([1/K,(K-1)/K],[K-1,K+1]),
    Res = hop(H,N+1,Target,Limit)
  end.
  
model() =>
  Start = 2,
  Target = 1,
  Limit = 100,

  [LastPad,Len] = hop(Start,0,Target,Limit),
  P = check(LastPad == 1),
  
  add("last pad",LastPad),
  add("len",Len),
  add("p",P).