/* 

  Sequence waiting times 1 in Picat.

  From  Gunnar Blom, Lars Holst, Dennis Sandell:
  "Problems and Snapshots from the World of Probability"
  Page 4ff, Problem 1.4 Patterns I, (Part Problem 1)

  Problem: Waiting time for a pattern (coin flipping)
   
  What is the waiting time for the patterns(0,1) in a coin 
  flipping sequence? For the pattern (1,1)?
  Answer: 
    * waiting time for (0,1) = 4
    * waiting time for (1,1) = 6


  Cf 
  - ppl_flipping_coins_until_pattern.pi
  - my Gamble model gamble_sequence_waiting_times_1.rkt

  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.

main => go.

/*

  pattern = [0,1]
  var : a
  Probabilities (truncated):
  [0,1]: 0.2466000000000000
  [0,0,1]: 0.1282000000000000
  [1,0,1]: 0.1253000000000000
  [1,1,0,1]: 0.0672000000000000
  .........
  [1,1,1,1,1,0,0,0,0,0,0,0,0,1]: 0.0001000000000000
  [1,1,0,0,0,0,0,0,0,0,0,0,0,1]: 0.0001000000000000
  [0,0,0,0,0,0,0,0,0,0,0,0,1]: 0.0001000000000000
  [0,0,0,0,0,0,0,0,0,0,0,0,0,1]: 0.0001000000000000
  Mean (truncated)
  mean = [[0,1] = 0.2466,[0,0,1] = 0.1282,[1,0,1] = 0.1253,[1,1,0,1] = 0.0672,[0,0,0,1] = 0.0669,[1,0,0,1] = 0.0581,[1,1,1,0,1] = 0.0336,[1,0,0,0,1] = 0.0322,[0,0,0,0,1] = 0.0322,[1,1,0,0,1] = 0.0305,[1,1,1,0,0,1] = 0.0157,[1,0,0,0,0,1] = 0.0153,[1,1,0,0,0,1] = 0.0147,[0,0,0,0,0,1] = 0.0144,[1,1,1,1,0,1] = 0.0139,[1,1,1,1,1,0,1] = 0.0081,[1,1,0,0,0,0,1] = 0.0076,[1,1,1,1,0,0,1] = 0.0074,[0,0,0,0,0,0,1] = 0.0072,[1,1,1,0,0,0,1] = 0.007]

  var : len
  Probabilities (truncated):
  3: 0.2535000000000000
  2: 0.2466000000000000
  4: 0.1922000000000000
  5: 0.1285000000000000
  .........
  13: 0.0017000000000000
  14: 0.0010000000000000
  15: 0.0004000000000000
  25: 0.0001000000000000
  mean = 3.9851


  pattern = [1,1]
  var : a
  Probabilities (truncated):
  [1,1]: 0.2522000000000000
  [0,1,1]: 0.1263000000000000
  [0,0,1,1]: 0.0639000000000000
  [1,0,1,1]: 0.0638000000000000
  .........
  [0,0,0,0,0,0,0,0,0,0,0,1,0,0,1,0,1,1]: 0.0001000000000000
  [0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,1,1]: 0.0001000000000000
  [0,0,0,0,0,0,0,0,0,0,0,0,0,1,1]: 0.0001000000000000
  [0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,1,1]: 0.0001000000000000
  Mean (truncated)
  mean = [[1,1] = 0.2522,[0,1,1] = 0.1263,[0,0,1,1] = 0.0639,[1,0,1,1] = 0.0638,[0,0,0,1,1] = 0.0311,[0,1,0,1,1] = 0.0294,[1,0,0,1,1] = 0.029,[1,0,1,0,1,1] = 0.0164,[1,0,0,0,1,1] = 0.0156,[0,0,0,0,1,1] = 0.0147,[0,1,0,0,1,1] = 0.0144,[0,0,1,0,1,1] = 0.0141,[0,0,1,0,0,1,1] = 0.0089,[1,0,0,0,0,1,1] = 0.0086,[0,0,0,0,0,1,1] = 0.0081,[1,0,1,0,0,1,1] = 0.0076,[1,0,0,1,0,1,1] = 0.0074,[0,0,0,1,0,1,1] = 0.0071,[0,1,0,0,0,1,1] = 0.0065,[0,1,0,1,0,1,1] = 0.0061]

  var : len
  Probabilities (truncated):
  2: 0.2522000000000000
  4: 0.1277000000000000
  3: 0.1263000000000000
  5: 0.0895000000000000
  .........
  36: 0.0002000000000000
  46: 0.0001000000000000
  37: 0.0001000000000000
  33: 0.0001000000000000
  mean = 6.0375


  pattern = [1,1,1]
  var : a
  Probabilities (truncated):
  [1,1,1]: 0.1206000000000000
  [0,1,1,1]: 0.0664000000000000
  [1,0,1,1,1]: 0.0328000000000000
  [0,0,1,1,1]: 0.0312000000000000
  .........
  [0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1]: 0.0001000000000000
  [0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,1,1,1]: 0.0001000000000000
  [0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1]: 0.0001000000000000
  [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,1,0,0,0,0,0,1,1,1]: 0.0001000000000000
  Mean (truncated)
  mean = [[1,1,1] = 0.1206,[0,1,1,1] = 0.0664,[1,0,1,1,1] = 0.0328,[0,0,1,1,1] = 0.0312,[0,0,0,1,1,1] = 0.018,[1,1,0,1,1,1] = 0.0176,[0,1,0,1,1,1] = 0.0155,[1,0,0,1,1,1] = 0.0148,[0,1,1,0,1,1,1] = 0.0096,[0,0,0,0,1,1,1] = 0.0093,[1,0,0,0,1,1,1] = 0.0084,[1,1,0,0,1,1,1] = 0.0078,[0,1,0,0,1,1,1] = 0.0072,[1,0,1,0,1,1,1] = 0.0067,[0,0,1,0,1,1,1] = 0.0064,[1,1,0,0,0,1,1,1] = 0.0045,[1,0,1,1,0,1,1,1] = 0.0045,[1,0,0,1,0,1,1,1] = 0.0044,[0,0,1,0,0,1,1,1] = 0.0044,[0,0,0,0,0,1,1,1] = 0.0043]

  var : len
  Probabilities (truncated):
  3: 0.1206000000000000
  4: 0.0664000000000000
  6: 0.0659000000000000
  5: 0.0640000000000000
  .........
  87: 0.0001000000000000
  85: 0.0001000000000000
  72: 0.0001000000000000
  69: 0.0001000000000000
  mean = 13.967


  pattern = [1,0,1]
  var : a
  Probabilities (truncated):
  [1,0,1]: 0.1226000000000000
  [0,1,0,1]: 0.0661000000000000
  [1,1,0,1]: 0.0615000000000000
  [0,0,1,0,1]: 0.0338000000000000
  .........
  [0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,0,0,1,0,0,1,1,1,0,1]: 0.0001000000000000
  [0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,1,0,1]: 0.0001000000000000
  [0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,1,0,1]: 0.0001000000000000
  [0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,1,1,0,1]: 0.0001000000000000
  Mean (truncated)
  mean = [[1,0,1] = 0.1226,[0,1,0,1] = 0.0661,[1,1,0,1] = 0.0615,[0,0,1,0,1] = 0.0338,[1,1,1,0,1] = 0.0311,[0,1,1,0,1] = 0.0307,[0,1,1,1,0,1] = 0.019,[1,1,1,1,0,1] = 0.0174,[0,0,1,1,0,1] = 0.0154,[1,0,0,1,0,1] = 0.0153,[0,0,0,1,0,1] = 0.0125,[1,0,0,0,1,0,1] = 0.0088,[1,1,1,1,1,0,1] = 0.0087,[1,0,0,1,1,0,1] = 0.0087,[0,0,0,1,1,0,1] = 0.0085,[0,0,0,0,1,0,1] = 0.008,[0,1,0,0,1,0,1] = 0.0072,[0,0,1,1,1,0,1] = 0.0069,[1,1,0,0,1,0,1] = 0.0068,[0,1,1,1,1,0,1] = 0.0066]

  var : len
  Probabilities (truncated):
  4: 0.1276000000000000
  3: 0.1226000000000000
  5: 0.0956000000000000
  6: 0.0796000000000000
  .........
  51: 0.0002000000000000
  56: 0.0001000000000000
  54: 0.0001000000000000
  53: 0.0001000000000000
  mean = 9.9916


  pattern = [1,1,0]
  var : a
  Probabilities (truncated):
  [1,1,0]: 0.1238000000000000
  [0,1,1,0]: 0.0624000000000000
  [1,1,1,0]: 0.0617000000000000
  [1,0,1,1,0]: 0.0339000000000000
  .........
  [0,0,0,0,0,0,0,0,0,0,0,1,0,1,1,0]: 0.0001000000000000
  [0,0,0,0,0,0,0,0,0,0,0,1,0,0,1,0,1,1,1,0]: 0.0001000000000000
  [0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,1,1,0]: 0.0001000000000000
  [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0]: 0.0001000000000000
  Mean (truncated)
  mean = [[1,1,0] = 0.1238,[0,1,1,0] = 0.0624,[1,1,1,0] = 0.0617,[1,0,1,1,0] = 0.0339,[1,1,1,1,0] = 0.0318,[0,0,1,1,0] = 0.0303,[0,1,1,1,0] = 0.0288,[1,0,1,1,1,0] = 0.0166,[0,1,0,1,1,0] = 0.0161,[0,1,1,1,1,0] = 0.016,[0,0,1,1,1,0] = 0.0158,[0,0,0,1,1,0] = 0.0152,[1,1,1,1,1,0] = 0.0146,[1,0,0,1,1,0] = 0.014,[0,0,1,0,1,1,0] = 0.0099,[1,0,0,0,1,1,0] = 0.009,[0,0,1,1,1,1,0] = 0.0087,[0,1,0,0,1,1,0] = 0.0082,[1,1,1,1,1,1,0] = 0.0081,[0,0,0,1,1,1,0] = 0.0079]

  var : len
  Probabilities (truncated):
  5: 0.1248000000000000
  4: 0.1241000000000000
  3: 0.1238000000000000
  6: 0.1083000000000000
  .........
  51: 0.0001000000000000
  50: 0.0001000000000000
  40: 0.0001000000000000
  39: 0.0001000000000000
  mean = 7.9633


  pattern = [0,1,1]
  var : a
  Probabilities (truncated):
  [0,1,1]: 0.1260000000000000
  [0,0,1,1]: 0.0653000000000000
  [1,0,1,1]: 0.0624000000000000
  [1,0,0,1,1]: 0.0310000000000000
  .........
  [0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,1,1]: 0.0001000000000000
  [0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1,0,1,1]: 0.0001000000000000
  [0,0,0,0,0,0,0,0,0,0,0,0,0,1,1]: 0.0001000000000000
  [0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,1,0,0,0,0,1,1]: 0.0001000000000000
  Mean (truncated)
  mean = [[0,1,1] = 0.126,[0,0,1,1] = 0.0653,[1,0,1,1] = 0.0624,[1,0,0,1,1] = 0.031,[0,1,0,1,1] = 0.0303,[0,0,0,1,1] = 0.029,[1,1,0,1,1] = 0.0289,[0,0,1,0,1,1] = 0.0168,[0,1,0,0,1,1] = 0.0165,[1,1,1,0,1,1] = 0.0164,[1,0,1,0,1,1] = 0.0161,[1,1,0,0,1,1] = 0.0159,[1,0,0,0,1,1] = 0.015,[0,0,0,0,1,1] = 0.0141,[1,1,0,0,0,1,1] = 0.0094,[1,0,0,0,0,1,1] = 0.0089,[0,0,0,0,0,1,1] = 0.0088,[0,0,1,0,0,1,1] = 0.0084,[1,1,1,0,0,1,1] = 0.0079,[1,1,1,1,0,1,1] = 0.0078]

  var : len
  Probabilities (truncated):
  4: 0.1277000000000000
  3: 0.1260000000000000
  5: 0.1192000000000000
  6: 0.1108000000000000
  .........
  42: 0.0001000000000000
  41: 0.0001000000000000
  35: 0.0001000000000000
  33: 0.0001000000000000
  mean = 7.9749


*/
go ?=>
  member(Pattern,[[0,1],[1,1],[1,1,1],[1,0,1],[1,1,0],[0,1,1]]),
  println(pattern=Pattern),
  reset_store,
  run_model(10_000,$model(Pattern),[show_probs_trunc,mean]),
  nl,
  % show_store_lengths,
  fail,
  nl.
go => true.
  

flip_sequence(A,Pattern) = Res =>
  Len = A.len,
  PatternLen = Pattern.len,
  if Len >= PatternLen, Pattern == A[Len-PatternLen+1..Len] then
    Res = A
  else
    Res = flip_sequence(A ++ [bern(1/2)],Pattern)
  end.
model(Pattern) =>
  A = flip_sequence([],Pattern),
  Len = A.len,
  add("a",A),
  add("len",Len).