/* 

  Probability of missing values in Picat.

  From https://github.polettix.it/ETOOBUSY/2021/07/19/brute-force-puzzle/
  """
  Consider a display with N digits in base b

      A random value id shown on the display; each possible value is equiprobable. 
      What is the expected number of missing digit values?

  As an example, suppose that we consider base-4 digits (i.e. 0 to 3) and a display that 
  has 6 slots. An example value shown on the display would be 232133, which includes digits 1, 2, 
  and 3 but not digit 0. In this arrangement, digit 0 is considered missing. Similarly, in 
  arrangement 111111 there are three missing digits, namely 0, 2, and 3.

  ....

  (By hand and Brute force:)
  2916 / 4096 ≅ 0.711914  
  """
 

  Cf my Gamble model gamble_probability_of_missing_values.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.

/*
  The case in the description:

  [base = 4,size = 6]
  var : num_missing
  Probabilities:
  1: 0.5315000000000000
  0: 0.3784000000000000
  2: 0.0890500000000000
  3: 0.0010500000000000
  mean = 0.71275


  Some other cases:

  [base = 10,size = 5]
  var : num_missing
  Probabilities:
  6: 0.4970000000000000
  5: 0.3038000000000000
  7: 0.1857500000000000
  8: 0.0133000000000000
  9: 0.0001500000000000
  mean = 5.909


  [base = 2,size = 2]
  var : num_missing
  Probabilities:
  1: 0.5032500000000000
  0: 0.4967500000000000
  mean = 0.50325


  [base = 3,size = 3]
  var : num_missing
  Probabilities:
  1: 0.6624000000000000
  0: 0.2263000000000000
  2: 0.1113000000000000
  mean = 0.885


  [base = 4,size = 4]
  var : num_missing
  Probabilities:
  1: 0.5669000000000000
  2: 0.3251000000000000
  0: 0.0926000000000000
  3: 0.0154000000000000
  mean = 1.2633


  [base = 5,size = 5]
  var : num_missing
  Probabilities:
  2: 0.4833000000000000
  1: 0.3864500000000000
  3: 0.0944500000000000
  0: 0.0347500000000000
  4: 0.0010500000000000
  mean = 1.6406


  [base = 6,size = 6]
  var : num_missing
  Probabilities:
  2: 0.5004999999999999
  1: 0.2337000000000000
  3: 0.2308500000000000
  0: 0.0174500000000000
  4: 0.0173500000000000
  5: 0.0001500000000000
  mean = 1.9974


  [base = 10,size = 10]
  var : num_missing
  Probabilities:
  3: 0.3537000000000000
  4: 0.3472500000000000
  2: 0.1347500000000000
  5: 0.1293000000000000
  1: 0.0171500000000000
  6: 0.0168500000000000
  7: 0.0007500000000000
  0: 0.0002500000000000
  mean = 3.4896

*/
go ?=>
  member([Base,Size],[
                      [4,6],
                      [10,5],
                      [2,2],
                      [3,3],
                      [4,4],
                      [5,5],
                      [6,6],
                      [10,10]
                     ]),
  println([base=Base,size=Size]),
  reset_store,
  run_model(20_000,$model(Base,Size),[show_probs_trunc,mean]),
  nl,
  % show_store_lengths,
  fail,
  nl.
go => true.
  
  
model(Base,Size) =>

  % Each digit 0..Base-1
  Digits = random_integer_n(Base,Size),

  % Count the number of missing values
  NumMissing = [Missing : Val in 0..Base-1, Missing = cond(membchk(Val,Digits),0,1)].sum,

  % add("digits",Digits),
  add("num_missing",NumMissing).