/* Lighting candles problem in Picat. From http://stackoverflow.com/questions/32644557/maximum-days-to-light-candles """ You are given heights of n candles. First day you lit one candle Second day you need to lit two candles Third day you need to lit three candles till possible. After lighting candles the height of candles deduced by 1 each day.You can also extinguish any candle you want but only at the end of day. So you need to tell the maximum number number of days , you can carry on lighting the candles. Example : there are three candles of heights {2 ,2 ,2 } Answer : 3 1.You light first candle on day one. heights -> {1,2,2} 2.You light second and third and extinguish first one . heights ->{1, 1,1} 3.You light all the candles. heights -{0,0,0} I found the solution on one blog as: Sort the array.Start from the maximum each day we add an element and subtract the number of candles needed. So for 2,2,2 Day 1: 2-1 = 1 Day 2: 1+2-2 = 1 Day 3: 1+2-3 = 0 Answer is: 3 But for 1,1,1 this algorithm will fail as answer should be 2. Please help me with this problem. """ Also see: https://www.hackerearth.com/problem/algorithm/afraid-of-darkness-2/ This Picat model was created by Hakan Kjellerstrand, hakank@gmail.com See also my Picat page: http://www.hakank.org/picat/ */ import planner. import cp. main => go. go => % Init = [2,2,2], Init = [4,4,4,4,5,10,20,10,5,5,7,10], % Init = [1], Day = 1, plan([Day|Init],Plan,Cost), println(plan=Plan), println(cost=Cost), nl. go2 => nolog, Test = [ [1], % 1 [10], % 1 [2, 2, 2], % 3 [1, 1, 1], % 2 [1, 2, 2], % 2 [1, 2, 3], % 3 [1, 2, 3, 4], % 4 [1, 2, 3, 3], % 3 [3, 3, 3, 3], % 4 [2, 3, 5, 3, 1, 1, 1] % 5 ], foreach(T in Test) println(t=T), Day = 1, plan([Day|T],T.len,Plan,Cost), println(plan=Plan), println(cost=Cost), nl end, nl. go3 => N = 8, % _ = random2(), % Init = [1+random() mod N : _ in 1..N], Init = [14,17,28,26,24,26,17,13,10,2,3,8,21,20,24,17,1,7,23,17,12,9,28,10,3,21,3,14,8,26], % Init = [2,2,2], println(init=Init), Day = 1, plan([Day|Init],Init.len,Plan,Cost),% not necessarily the longest path! % maxof(best_plan_nondet([Day|Init],Init.len,Plan,Cost),Cost), % best_plan([Day|Init],Plan,Cost), % max_plan([Day|Init],Plan,Cost), % very slow! println(plan=Plan), println(cost=Cost), nl, foreach([Day1,From1,Lit1,To1] in Plan) println(Day1), println(From1), println(Lit1), println(To1), nl end, nl. % cp go4 => Candles = [2,2,2], candles_cp(Candles, X,Lit,Len), println(x=X), println(lit=Lit), println(len=Len), nl. go5 => nolog, Test = [ [1], % 1 [10], % 1 [2, 2, 2], % 3 [1, 2, 2], % 2 [1, 2, 3], % 3 [1, 2, 3, 4], % 4 [1, 2, 3, 3], % 3 [3, 3, 3, 3], % 4 [2, 3, 5, 3, 1, 1, 1] % 5 ], foreach(T in Test) println(t=T), candles_cp(T,X,Lit,Len), println(x=X), println(lit=Lit), println(len=Len), nl end, nl. go6 => N = 20, _ = random2(), Candles = [1+random() mod N : _ in 1..N], % .sort_down(), % Candles = [14,17,28,26,24,26,17,13,10,2,3,8,21,20,24,17,1,7,23,17,12,9,28,10,3,21,3,14,8,26], println(candles=Candles), foreach(I in 1..N) println(I=[ 1 : C in Candles, C >= I].len) end, nl, candles_cp(Candles,X,Lit,Len), println(x=X), println(lit=Lit), println(len=Len), foreach(Day in 1..Len) println(day=Day), foreach(J in 1..Candles.len) printf("%2d ", X[Day,J]) end, nl, foreach(J in 1..Candles.len) printf("%2d ", Lit[Day,J]) end, nl,nl end, nl. go7 => N = 100, _ = random2(), Candles = [1+random() mod N : _ in 1..N].sort_down(), % Candles = [14,17,28,26,24,26,17,13,10,2,3,8,21,20,24,17,1,7,23,17,12,9,28,10,3,21,3,14,8,26], println(candles=Candles), T = [[ 1 : C in Candles, C >= I].len : I in 1..N], % println(t=T), println(numT=[1 : TT in T, TT > 0].len), candles2(Candles,X,Len), % println(x=X), println(len=Len), foreach(Day in 1..X.len) println(day=Day), foreach(J in 1..Candles.len) printf("%2d ", X[Day,J]) end, nl end, nl. % just the length go7b => N = 1000, % _ = random2(), % Candles = [1+random() mod N : _ in 1..N].sort_down(), Candles = [1+random() mod N : _ in 1..N].sort_down(), % Candles = [14,17,28,26,24,26,17,13,10,2,3,8,21,20,24,17,1,7,23,17,12,9,28,10,3,21,3,14,8,26], println(candles=Candles), T = [[ 1 : C in Candles, C >= I].len : I in 1..N], % println(t=T), println(numT=[1 : TT in T, TT > 0].len), candles2b(Candles,Len), println(len=Len), nl. go8 => Test = [ [1], % 1 [10], % 1 [2, 2, 2], % 3 [1, 2, 2], % 2 [1, 2, 3], % 3 [1, 2, 3, 4], % 4 [1, 2, 3, 3], % 3 [3, 3, 3, 3], % 4 [2, 3, 5, 3, 1, 1, 1] % 5 ], foreach(T in Test) println(t=T), candles2(T,X,Len), println(x=X), println(len=Len), nl end, nl. candles_cp(Candles,X,Lit,Len) => % maxof(candles_cp1(Candles, X, Lit, Len), Len). Found = true, FoundLen = 0, FoundX = _, FoundLit = _, foreach(Len1 in 1..Candles.len, Found = true) println(len1=Len1), if candles_cp1(Candles, X1, Lit1, Len1) then FoundLen := Len1, FoundX := X1, FoundLit := Lit1 else Found := false end end, Len = FoundLen, X = FoundX, Lit = FoundLit. candles_cp1(Candles, X, Lit, Len) => % println($candles_cp1(Candles, X, Lit, Len)), CLen = Candles.len, % Len :: 1..CLen, % indomain(Len), % member(Len,CLen..-1..1), Lit = new_array(Len,CLen), Lit :: 0..1, X = new_array(Len+1,CLen), X :: 0..max(Candles), foreach(J in 1..CLen) X[1,J] #= Candles[J], foreach(Day in 1..Len+1) X[Day,J] #<= Candles[J] end end, foreach(Day in 1..Len) sum([Lit[Day,J] : J in 1..CLen]) #= Day, foreach(J in 1..CLen) X[Day,J]-Lit[Day,J] #>= 0, X[Day+1,J] #= X[Day,J]-Lit[Day,J] % X[Day+1,J] #>= 0 end end, Vars = X.vars() ++ Lit.vars(), solve($[max,split],Vars). % % Very simple approach: % % Repeat for Day in 1..Candles.len % - sort candle list % - if there are enough to lit Day candles % - decrement the Day largest candles by 1 % - sort candle list % - else end loop % candles2(Candles,X,Len) => CLen = Candles.len, Candles2 = Candles.sort_down(), Y = [], Found = true, foreach(Day in 1..CLen, Found == true) Candles2 := Candles2.sort_down(), T = [Pos : Pos in 1..CLen, Candles2[Pos] > 0], if T.len >= Day then Y := Y ++ [copy_term(Candles2)], foreach(J in 1..Day) Candles2[T[J]] := Candles2[T[J]]-1 end else Found := false end end, X = Y, Len = X.len. % Just the length candles2b(Candles,Len) => CLen = Candles.len, Candles2 = Candles.sort_down(), Found = true, Len1 = 0, foreach(Day in 1..CLen, Found = true) T = [I : I in 1..CLen, Candles2[I] > 0], if T.len >= Day then foreach(J in 1..Day) Candles2[T[J]] := Candles2[T[J]]-1 % , end, Candles2 := Candles2.sort_down(), Len1 := Len1+1 else Found := false end end, Len = Len1. table(+,-,max) max_plan(S,Plan,Len), valid(S) => % println($max_plan2(S,Plan,Len)), action(Action,S,S1), max_plan(S1,Plan1,Len1), Plan = [Action|Plan1], Len = Len1+1. max_plan(S,Plan,Len) => % final(S) => % println($max_plan1(S,Plan,Len)), Plan=[], Len=0. % % A critera for a valid solution. % valid([Day|L]) => [1 : S in L, S > 0].len >= Day. % % Criteria for an invalid solution. % final([Day|L]) => T = [1 : S in L, S > 0], % T.len < Day. ((L.len > 1, T.len < Day-1) ; (L.len = 1, T.len < Day)). % % action/4: for planner % action([Day|From],To,Move,Cost) => % [1 : S in From, S > 0].len >= Day, Len = From.len, Lit = new_list(Len), % what candle to lit To1 = new_list(Len), foreach(I in 1..Len) % member(Lit[I],0..1), between(0,1,Lit[I]), From[I] - Lit[I] >= 0, To1[I] := From[I] - Lit[I] end, sum(Lit) = Day, Cost = 1, To = [Day+1|To1], Move = ['day '=Day,from=From,'lit '=Lit,'to '=To1]. % % action/3: for max_plan % action(Move,[Day|From],To) => % println($action(Move,[Day|From],Cost)), Len = From.len, Len >= Day, [1 : S in From, S > 0].len >= Day, % sum([1 : S in From, S > 0]) >= Day, Lit = new_list(Len), % what candle to lit To1 = new_list(Len), foreach(I in 1..Len) % member(Lit[I],0..1), between(0,1,Lit[I]), % faster From[I] - Lit[I] >= 0, To1[I] := From[I] - Lit[I] end, sum(Lit) = Day, % Cost = 1, To = [Day+1|To1], Move = ['day '=Day,from=From,'lit '=Lit,'to '=To1].