/* 

  Lucky Number in Picat.

  https://www.codingame.com/ide/puzzle/the-lucky-number
  """
  A lucky number is a 10-based number, which has at least a "6" or an "8" in 
  its digits. However, if it has "6" and "8" at the same time, then the number 
  is NOT lucky. For example, "16", "38", "666" are lucky numbers, while "234" , 
  "687" are not.

  Now we want to know how many lucky numbers (without leading zeroes) are there 
  between L and R, inclusive?
  """

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

*/

import v3_utils.

main => go.

%
% 5.288s 
%
% CPU time 0.0 seconds.
%
% 10 = 2
%
% CPU time 0.001 seconds.
%
% 100 = 34
%
% CPU time 0.0 seconds.
%
% 1000 = 434
%
% CPU time 0.004 seconds.
%
% 10000 = 4930
%
% CPU time 0.042 seconds.
%
% 100000 = 52562
%
% CPU time 0.422 seconds.
%
% 1000000 = 538594
%
% CPU time 4.819 seconds.
%
% 10000000 = 5371634
%
% CPU time 5.288 seconds. Backtracks: 0
%
go ?=>
  L = 1,
  member(R,[10,100,1_000,10_000,100_000,1_000_000,10_000_000]),
  time(lucky_number_count1(L,R,Count)),
  println(R=Count),
  fail,
  nl.
go => true.

%
% The "Prolog way", 
% Slightly faster: 5.2s
%
% CPU time 0.0 seconds.
%
% 10 = 2
%
% CPU time 0.0 seconds.
%
% 100 = 34
%
% CPU time 0.001 seconds.
%
% 1000 = 434
%
% CPU time 0.005 seconds.
%
% 10000 = 4930
%
% CPU time 0.044 seconds.
%
% 100000 = 52562
%
% CPU time 0.434 seconds.
%
% 1000000 = 538594
%
% CPU time 4.716 seconds.
%
% 10000000 = 5371634
%
% CPU time 5.2 seconds. Backtracks: 0
%
go2 ?=>
  L = 1,
  member(R,[10,100,1_000,10_000,100_000,1_000_000,10_000_000]),
  time(lucky_number_count2(L,R,Count)),
  println(R=Count),
  fail,
  nl.
go2 => true.

%
% Slower: 5.373
%
% [l = 1,r = 10,2]
% [l = 1,r = 100,34]
% [l = 1,r = 1000,434]
% [l = 1,r = 10000,4930]
% [l = 1,r = 100000,52562]
% [l = 1,r = 1000000,538594]
% [l = 1,r = 10000000,5371634]
%
% CPU time 5.373 seconds. Backtracks: 0
%
%
go3 ?=>
  foreach(R in 1..7)
    println([l=1,r=10**R,[1 : N in 1..10**R, lucky_number4(N.to_string)].len])
  end,
  nl.
go3 => true.


%
% Some tests
% 
go4 ?=>

   Ns = ["16","38","666","234","687"],
   Preds = [lucky_number1,lucky_number2,lucky_number3,lucky_number4],

   foreach(Pred in Preds)
     println(pred=Pred),
     foreach(N in Ns) 
       if call(Pred,N) then
         println(N=lucky)
       else
         println(N=not_lucky)
       end
    end,
    nl
  end,

  nl.
go4 => true.

%
% Show the lucky numbers for R=[10,100,1000]
%
% 10 = [6,8]
% 100 = [6,8,16,18,26,28,36,38,46,48,56,58,60,61,62,63,64,65,66,67,69,76,78,80,81,82,83,84,85,87,88,89,96,98]
% 1000 = [6,8,16,18,26,28,36,38,46,48,56,58,60,61,62,63,64,65,66,67,69,76,78,80,81,82,83,84,85,87,88,89,96,98,106,108,116,118,126,128,136,138,146,148,156,158,160,161,162,163,164,165,166,167,169,176,178,180,181,182,183,184,185,187,188,189,196,198,206,208,216,218,226,228,236,238,246,248,256,258,260,261,262,263,264,265,266,267,269,276,278,280,281,282,283,284,285,287,288,289,296,298,306,308,316,318,326,328,336,338,346,348,356,358,360,361,362,363,364,365,366,367,369,376,378,380,381,382,383,384,385,387,388,389,396,398,406,408,416,418,426,428,436,438,446,448,456,458,460,461,462,463,464,465,466,467,469,476,478,480,481,482,483,484,485,487,488,489,496,498,506,508,516,518,526,528,536,538,546,548,556,558,560,561,562,563,564,565,566,567,569,576,578,580,581,582,583,584,585,587,588,589,596,598,600,601,602,603,604,605,606,607,609,610,611,612,613,614,615,616,617,619,620,621,622,623,624,625,626,627,629,630,631,632,633,634,635,636,637,639,640,641,642,643,644,645,646,647,649,650,651,652,653,654,655,656,657,659,660,661,662,663,664,665,666,667,669,670,671,672,673,674,675,676,677,679,690,691,692,693,694,695,696,697,699,706,708,716,718,726,728,736,738,746,748,756,758,760,761,762,763,764,765,766,767,769,776,778,780,781,782,783,784,785,787,788,789,796,798,800,801,802,803,804,805,807,808,809,810,811,812,813,814,815,817,818,819,820,821,822,823,824,825,827,828,829,830,831,832,833,834,835,837,838,839,840,841,842,843,844,845,847,848,849,850,851,852,853,854,855,857,858,859,870,871,872,873,874,875,877,878,879,880,881,882,883,884,885,887,888,889,890,891,892,893,894,895,897,898,899,906,908,916,918,926,928,936,938,946,948,956,958,960,961,962,963,964,965,966,967,969,976,978,980,981,982,983,984,985,987,988,989,996,998]
%
go5 ?=>
  foreach(R in 1..3)
    println((10**R)=[N : N in 1..10**R, lucky_number4(N.to_string)])
  end,
  nl.
go5 => true.

%
% It'a xor.
%
lucky_number1(N) =>
   Has6 = cond(membchk('6',N),1,0),
   Has8 = cond(membchk('8',N),1,0),
   Has6 ^ Has8 == 1.

lucky_number2(N) :-
  (membchk('6',N) ; membchk('8',N)),
  not (membchk('6',N), membchk('8',N)).

has6(N) => membchk('6',N).
has8(N) => membchk('8',N).
has6or8(N) => has6(N) ; has8(N).
has6and8(N) => has6(N),has8(N).

lucky_number3(N) =>
  % has6or8(N), not has6and8(N).
  (has6(N) ; has8(N)), not (has6(N),has8(N)).

lucky_number4(N) =>
   cond(membchk('6',N),1,0) ^ cond(membchk('8',N),1,0) == 1.


lucky_number_count1(L,R,Count) =>
  Count1 = 0,
  N = L,
  while (N <= R)
    if lucky_number4(N.to_string) then
      Count1 := Count1 + 1
    end,
    N := N+1
  end,
  Count = Count1.

%
% The Prolog way.
%
lucky_number_count2(L,R,Count) :-
  lucky_number_count2(L,R+1,1,0,Count).

lucky_number_count2(_L,R,R,Count,Count).
lucky_number_count2(L,R,N,Count0,Count) :-
  N <= R,
  % number_string(N,S), % much slower
  S = N.to_string,
  (lucky_number4(S) ->
    Count1 = Count0 + 1
  ;
    Count1 = Count0
  ),
  lucky_number_count2(L,R,N+1,Count1,Count).