/* 

  Who is the liar? (Number of liars) in Picat.

  https://puzzling.stackexchange.com/questions/109733/who-is-the-liar-number-of-liars/109734#109734
  """
  There are 5 people. Each one can be lying or telling the truth, and they can't 
  switch. Below, each person tells us how many liars exist in the group.

   1. There are at least 3 liars.
   2. There are at least 2 liars.
   3. There are at least 1 liars.
   4. There are at least 4 liars.
   5. There are at least 2 liars.

  How many liars exist and who they are? Can you give an answer for N people? 
  Explain your workflow.
  """

  people = [3,2,1,4,2]
  x = [1,0,0,1,0]
  liars = [2,3,5]
  numLiars = 3



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

*/

import cp.
import v3_utils.

main => go.

go ?=>
  People = [3,2,1,4,2],
  println(people=People),
  who_is_the_liar(People, X,Liars),
  println(x=X),
  println(liars=Liars),
  println(numLiars=Liars.len),
  fail,
  nl.
go => true.

/*
  The general case: 
  People say there are at least 0..N-1 liars
  * if N even: not possible
  * if N odd: the first 1..(N+1) div 2 persons are liars

n = 2
n = 3
x = [0,0,1]
liars = [1,2]
numLiars = 2

n = 4
n = 5
x = [0,0,0,1,1]
liars = [1,2,3]
numLiars = 3

n = 6
n = 7
x = [0,0,0,0,1,1,1]
liars = [1,2,3,4]
numLiars = 4

n = 8
n = 9
x = [0,0,0,0,0,1,1,1,1]
liars = [1,2,3,4,5]
numLiars = 5

n = 10
n = 11
x = [0,0,0,0,0,0,1,1,1,1,1]
liars = [1,2,3,4,5,6]
numLiars = 6


*/
go2 ?=>
  member(N,2..11),
  println(n=N),
  People = 0..N-1,
  println(people=People),
  if who_is_the_liar(People, X,Liars) then
    println(x=X),
    println(liars=Liars),
    println(numLiars=Liars.len)
  else
    println(no_solution)
  end,
  nl,
  fail,
  nl.
go2 => true.


% CP: Picat style
who_is_the_liar(People,X,Liars) =>
  N = People.len,

  % 
  X = new_list(N),
  X :: 0..1, % 0: liars, 1: truth sayer

  % X[P] is a liar if there ARE more than People[P] liars
  % in the group.
  foreach(P in 1..N)
    (X[P] #= 0) #<=> (sum([X[I] : I in 1..N]) #>= People[P])
  end,
  solve(X),
  Liars=[I : I in 1..N, X[I] == 0].