/* 

  Book sorting puzzle in Picat.

  From Rajul Saxena
  "The Library Book Sorting Puzzle"
  https://medium.com/puzzle-sphere/book-sorting-interview-puzzle-math-logic-google-amazon-microsoft-faang-quantitative-aptitude-probability-124b5917e059
  """
  Imagine you’re working at a library sorting books. You start with 32 fiction books 
  and 17 non-fiction books in a box. Each turn, you randomly pick two books from 
  the box and remove them.

  You do one more operation based on what books you picked.
  * If the books are of the same type (both fiction or both non-fiction), 
    you add a new fiction book to the box.

  * If the books are of different types (one fiction and one non-fiction), 
    you add a new non-fiction book to the box.

  * You have an unlimited supply of fiction and non-fiction books for this process.

  What will be the type of the last book remaining in the box?
  """

  Cf my Gamble model gamble_book_sorting_puzzle.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.
% import ordset.

main => go.

/*
  [num_fiction = 32,num_non_fiction = 17]
  var : res
  Probabilities:
  n: 1.0000000000000000


  [num_fiction = 32,num_non_fiction = 18]
  var : res
  Probabilities:
  f: 1.0000000000000000

  More generally: If the number of non-fiction books is odd then the 
  last book will be a non-fiction book. If the number of non-fiction 
  books is even, then it's a fiction book.

*/
go ?=>
  NumFiction = 32,
  member(NumNonFiction,17..18),
  println([num_fiction=NumFiction,num_non_fiction=NumNonFiction]),
  reset_store,
  run_model(10_000,$model(NumFiction,NumNonFiction),[show_probs]),
  nl,
  fail,
  nl.
go => true.
  

f(A) = Res =>
  if A.len <= 1 then
    Res = A
  else
    Pick = take(A,2),
    NewA = drop(A,2),
    if Pick.remove_dups.len == 1 then
      Res = f(NewA ++ [f]), % same book type: add fiction
    else
      Res = f(NewA ++ [n]), % different book type: add non fiction
    end
  end.

model(NumFiction,NumNonFiction) =>
  Init = shuffle(rep(NumFiction,f) ++ rep(NumNonFiction,n) ),
  Res = f(Init),

  add("res",Res).