/* Smallest missing positive number in Picat. From https://gist.github.com/adamcrussell/e18f081d711be5a49aea6e6665463d73 """ You are given an unsorted list of integers @N. Write a script to find out the smallest positive number missing. """ Via Adam Russell https://twitter.com/adamcrussell/status/1313153770843525127 The problem is from: https://perlweeklychallenge.org/blog/perl-weekly-challenge-080/#TASK1 """ You are given unsorted list of integers @N. Write a script to find out the smallest positive number missing. Example 1: Input: @N = (5, 2, -2, 0) Output: 1 Example 2: Input: @N = (1, 8, -1) Output: 2 Example 3: Input: @N = (2, 0, -1) Output: 1 """ Here are some different implementations with the times for some instances (using go2/0): - first_missing/1 Picat approach using list comprehension, sort/1, membchk/2, and first/1 * 20_000: 0.456s * 50_000: 2.844s * 100_000: 11.727s * 1_000_000: - * 10_000_000: - * 100_000_000: - The slowest. - first_missing2/1 Picat approach using list comprehension, sort/1, membchk/2, and first/1 * 20_000: 0.421s * 50_000: 2.659s * 100_000: 10.777s * 1_000_000: - * 10_000_000: - * 100_000_000: - Also very slow. - first_missing3/2 Prolog style using membchk and recursion * 20_000: 0.0s * 50_000: 0.0s * 100_000: 0.0s * 1_000_000: 0.004s * 10_000_000: 0.021s * 100_000_000: 0.212s One of the fastest. - first_missing4/2 Prolog style using sort, membchk and recursion but with Picat flavours * 20_000: 0.0s * 50_000: 0.006s * 100_000: 0.012s * 1_000_000: 0.125s * 10_000_000: 1.707s * 100_000_000: - - first_missing4Prolog/2 Prolog style using sort, membchk and recursion. "Plain" Prolog. Slower than first_missing4/2. * 20_000: 0.0s * 50_000: 0.007s * 100_000: 0.014s * 1_000_000: 0.178s * 10_000_000: 10.719s * 100_000_000: - - first_missing5/1 Imperative Picat style using while loop, membchk, and reassigment * 20_000: 0.0s * 50_000: 0.0s * 100_000: 0.001s * 1_000000: 0.005s * 10_000_000: 0.021s * 100_000_000: 0.212s Also one of the fastest. - first_missing6/1 Using ordset, subtract, and first * 20_000: 0.002s * 50_000: 0.01s * 100_000: 0.005s * 1_000_000: 0.203s * 10_000_000: 2.319s * 100_000_000: 699.347s - first_missing7/1 Using foreach and membchk * 20_000: 0.001s * 50_000: 0.003s * 100_000: 0.005s * 1_000_000: 0.052s * 10_000_000: 0.474s * 100_000_000: 4.735s - first_missing8/1 Using membchk/2 twice. * 20_000: 0.001s * 50_000: 0.003s * 100_000: 0.006s * 1_000_000: 0.053s * 10_000_000: 0.513s * 100_000_000: 10.147s first_missing3/2 and first_missing5/2 are the fastest. first_missing7/2 and first_missing8/2 are also quite fast. first_missing/2 and first_missing2/2 are by far the slowest. This Picat model was created by Hakan Kjellerstrand, hakank@gmail.com See also my Picat page: http://www.hakank.org/picat/ */ import ordset. main => go. go ?=> Ls = [ [5, 2, -2, 0], % 1 [1, 8, -1], % 2 [2, 0, -1], % 1 [-2,-1,0,1,2,3,4,5], % hakank: added this case: Should be 6 [3,15,0,-7,1,-6,19,2,20,17], % should be 4 [-7,-1,-10,-5,-8,-2], % all non positives: should be 1 [-8,-4,1,1,2,5,11,13,15,18], % duplicates: should be 3 [-8,9,-2,8,-8,5,-9,-2,6,2] % shoud be 1 ], foreach(L in Ls) println(l=L), first_missing(L,Missing1), println('first_missing '=Missing1), first_missing2(L,Missing2), println(first_missing2=Missing2), first_missing3(L,Missing3), println(first_missing3=Missing3), first_missing4(L,Missing4), println(first_missing4=Missing4), first_missing4_prolog(L,Missing4Prolog), println(first_missing4Prolog=Missing4Prolog), first_missing5(L,Missing5), println(first_missing5=Missing5), first_missing6(L,Missing6), println(first_missing6=Missing6), first_missing7(L,Missing7), println(first_missing7=Missing7), first_missing8(L,Missing8), println(first_missing8=Missing8), nl end, nl. go => true. % % Random with timing % go2 ?=> _ = random2(), garbage_collect(300_000_000), % N = 20_000, % N = 50_000, % N = 100_000, % N = 1_000_000, % N = 10_000_000, N = 100_000_000, % N = 1_000_000_000, println(n=N), L = [random(-10,N) : _ in 1..N], % .remove_dups, % println(l=L), % println(sorted=L.sort()), if N < 1_000_000 then println("\nrun first_missing/2"), time(first_missing(L,Missing1)), % too slow println('first_missing '=Missing1), println("\nrun first_missing2/2"), time(first_missing2(L,Missing2)), % too slow println(first_missing2=Missing2) end, println("\nrun first_missing3/2"), time(first_missing3(L,Missing3)), println(first_missing3=Missing3), if N < 100_000_000 then println("\nrun first_missing4/2"), time(first_missing4(L,Missing4)), println(first_missing4=Missing4) end, if N < 100_000_000 then println("\nrun first_missing4Prolog/2"), time(first_missing4_prolog(L,Missing4Prolog)), % a little too slow forlarger instances println(first_missing4Prolog=Missing4Prolog) end, println("\nrun first_missing5/2"), time(first_missing5(L,Missing5)), println(first_missing5=Missing5), if N < 100_000_000 then println("\nrun first_missing6/2"), time(first_missing6(L,Missing6)), println(first_missing6=Missing6) end, println("\nrun first_missing7/2"), time(first_missing7(L,Missing7)), println(first_missing7=Missing7), println("\nrun first_missing8/2"), time(first_missing8(L,Missing8)), println(first_missing8=Missing8), nl. go2 => true. % % Checking solutions for different approaches. % go3 ?=> _ = random2(), Found = false, M = 100000, foreach(_I in 1..M, Found == false) N = 10, L = [random(-10,N) : _ in 1..N], % .remove_dups, first_missing3(L,Missing3), first_missing4(L,Missing4), if Missing3 != Missing4 then println(l=L), println(sort=L.sort), println(first_missing3=Missing3), println(first_missing4=Missing4), Found := true end end, nl. go3 => true. % % First approach: Slowest % first_missing(L,First) => Pos = [I : I in L.sort, I> 0], First = cond(Pos != [], first([I : I in 1..L.max()+1, not membchk(I,Pos)]),1). % % Simpler, but still very slow. % first_missing2(L,Missing) => Missing = cond(max(L)>1,first([I : I in 1..L.max()+1, not membchk(I,L)]),1). % % Prolog style % first_missing3(L,Missing) :- first_missing3(L,1,Missing). % Found it first_missing3(L,N,N) :- % \+ member(N,L),!. \+ membchk(N,L), !. % faster % Continue first_missing3(L,N,Missing) :- N1 is N+1, first_missing3(L,N1,Missing). % first_missing3(L,N+1,Missing). % Picat version % % Prolog style, with sort. % first_missing4_prolog(L,Missing) :- bp.sort(L,Sorted), remove_non_positive(Sorted,Pos), (Pos == [] -> Missing = 1 ; list_max(L,Max1), Max = Max1 + 1, first_missing4(Pos,1,Max,Missing) ). % It's much faster with some Picat flavour but still quite slow % for larger instances: 10_000_000: 45.2439s first_missing4(L,Missing) :- Pos = [E : E in L.sort_remove_dups, E > 0], % Picat (Pos == [] -> Missing = 1 ; Max = max(L)+1, % Picat first_missing4(Pos,1,Max,Missing) ). % Found it first_missing4([H|_T],N,_Max,N) :- H != N. % Nope, continue first_missing4([_H|T],N,Max,Missing) :- N1 is N+1, first_missing4(T,N1,Max,Missing). % Last: Aha, then it's the +1 value! first_missing4([],_N,Max,Max). % % Imperative style % first_missing5(L,Missing) => I = 1, Missing1 = _, while (var(Missing1)) if not membchk(I,L) then Missing1 := I end, I := I+1 end, Missing = Missing1. % % Using ordset % Fast: 0.0s on 20000 instance % first_missing6(L,Missing) => Missing = cond(max(L)>0,first(subtract(1..L.max+1, new_ordset(L))),1). % % Imperative, foreach and member % first_missing7(L,Missing) => Missing1 = _, (max(L) < 1 -> Missing1 = 1 ; foreach(I in 1..max(L)+1,var(Missing1)) if not membchk(I,L) then Missing1 := I end end ), Missing = Missing1. % % Just using member/2 % first_missing8(L,Missing) => if max(L) < 1 then Missing = 1 else membchk(I,1..L.max+1), % between(1,L.max+1,I), (not membchk(I, L) -> !,Missing = I ; fail ) end. % Remove all non positive values remove_non_positive(L,Pos) :- remove_non_positive(L,[],Pos). remove_non_positive([],Pos,Pos). remove_non_positive([H|T],Pos1,[H|Pos]) :- H > 0, remove_non_positive(T,Pos1,Pos). remove_non_positive([_H|T],Pos1,Pos) :- remove_non_positive(T,Pos1,Pos). list_max([H|T],Max) :- list_max(T,H,Max). list_max([],Max,Max). list_max([H|T],Max1,Max) :- H > Max1 -> list_max(T,H,Max) ; list_max(T,Max1,Max).