/* 

  Subset plus 2 problem in Picat.

  From God plays dice:
  "Bitwise set trickery"
  http://gottwurfelt.wordpress.com/2012/07/13/bitwise-set-trickery/
  """
  James Tanton asked last week on Twitter: How many subsets S of {1, 2,... 10} 
  have the property that S and S+2 cover all the numbers from 1 to 12?
  
  (I’ve taken the liberty of expanding some abbreviations here because my 
  blog, unlike Twitter, doesn’t have a 140-character limit.  Also, Tanton 
  gave a hint which I’m omitting; you can click through to the link if you 
  want it.)
  
  In case you don’t know the notation, S + 2 means the set that we get from 
  S by adding 2 to each element. So, for example, if S = {3, 5, 9} then 
  S + 2 = {5, 7, 11}.
  """

  And this model (with low=1, high=10, and add=2) gives the expected 25 
  solutions.

  Testing with different values of high (low = 1 and add = 2).
    high #solutions
    ---------------
    1    0
    2    1
    3    1
    4    1
    5    2
    6    4
    7    6
    8    9
    9   15
   10   25
   11   40
   12   64
   13  104
   14  169
   15  273
   16  441
   17  714
   18 1156
   19 1870
   20 3025
  
  OK, time for OEIS:
  0,1,1,1,2,4,6,9,15,25,40,64,104,169,273,441,714,1156,1870,3025
  
  This is http://oeis.org/A074677
  "a(n)=Sum((-1)^(i+Floor(n/2))F(2i+e),(i=0,..,Floor(n/2))), where F(n) = Fibonacci numbers and e=(1/2)(1-(-1)^n)."
  
  With the first 0 removed it's
  http://oeis.org/A006498
  A006498: a(n) = a(n-1)+a(n-3)+a(n-4).
  Number of compositions of n into 1's, 3's and 4's. (+ other variants)


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

*/

import cp.

main => go.

go =>

  High = 10,
  Add = 2,
  subsets_plus_n(High, Add, S1,S2),

  println(s1=[I : I in 1..High, S1[I] == 1]),
  println(s2=[I : I in Add..High+Add, S2[I] == 1]),
  nl,
  fail,
  
  nl.

/*
  Count the number of solutions High = 2..20
*/
go2 =>
  Add = 2,
  foreach(High in 1..20)
    Count=count_all(subsets_plus_n(High, Add, _S1,_S2)),
    printf("%2d:%10d\n",High,Count)
  end,
  nl.

subsets_plus_n(High,Add, S1,S2) =>
  High > 1,
  S1 = new_list(High+Add),
  S1 :: 0..1,
  S2 = new_list(High+Add),
  S2 :: 0..1,

  foreach(I in 1..Add)
    S1[I+Add] #= 0,
    S2[I] #= 0
  end,

  foreach(I in 1..High+Add)
    S1[I] + S2[I] #>= 1
  end,

  foreach(I in 1..High)
    S1[I] #= 1 #<=> S2[I+Add] #= 1
  end,

  solve(S1++S2).