/* Find the missing number in Picat. Using this simple approach: - the missing number must be of the same length as the difference between the length of the string of all digits and the length of the problem instance - the missing number must have the same digit sum as the difference between the digit sum of all digits and the digit sum of the problem instance - the digits of the missing number is the digits that has the difference number of occurrences of all digits and the problem instance - after all this one search if there is a number matching all the above criteria that is not in the instance string. Note: This step seems to be redundant. Analysis: This algorithm is exact, in the sense that the only time this approach will correctly identify the missing number if there is no reverse of the number (in the allowed range) or if the missing number is a palindrom - which makes the number it's own reversal. This means that in the problem range is 1..20, this approach will find all instances (100%). However, the hit percentage drops quite fast: N %hits ----------- 20 100% 25 91.92% 50 76.03% 100 28.06% 250 23.39% 200 18.9% 500 11.23% 999 4.47% This Picat model was created by Hakan Kjellerstrand, hakank@gmail.com See also my Picat page: http://www.hakank.org/picat/ */ import util. import cp. main => go. /* N=20 10_000 rounds num found: 10000 (of 10000) = 100.00% 1: found: 499 not found: 0 always found 2: found: 501 not found: 0 3: found: 531 not found: 0 4: found: 481 not found: 0 5: found: 538 not found: 0 6: found: 502 not found: 0 7: found: 491 not found: 0 8: found: 506 not found: 0 9: found: 487 not found: 0 10: found: 474 not found: 0 11: found: 521 not found: 0 12: found: 516 not found: 0 13: found: 520 not found: 0 14: found: 458 not found: 0 15: found: 464 not found: 0 16: found: 493 not found: 0 17: found: 519 not found: 0 18: found: 551 not found: 0 19: found: 496 not found: 0 20: found: 452 not found: 0 N=25 100_000 rounds num found: 91924 (of 100000) = 91.92% 1: found: 3950 not found: 0 2: found: 4049 not found: 0 3: found: 3946 not found: 0 4: found: 3970 not found: 0 5: found: 3964 not found: 0 6: found: 3968 not found: 0 7: found: 3975 not found: 0 8: found: 4055 not found: 0 9: found: 4049 not found: 0 10: found: 3966 not found: 0 11: found: 4077 not found: 0 12: found: 0 not found: 4071 never found since 21 is in the range 13: found: 4062 not found: 0 14: found: 3977 not found: 0 15: found: 3976 not found: 0 16: found: 3938 not found: 0 17: found: 3975 not found: 0 18: found: 4092 not found: 0 19: found: 3929 not found: 0 20: found: 3900 not found: 0 21: found: 0 not found: 4005 never found since 12 is in the range 22: found: 4023 not found: 0 23: found: 4136 not found: 0 24: found: 3981 not found: 0 25: found: 3966 not found: 0 N=50 10000 rounds num found: 76032 (of 100000) = 76.03% 1: found: 1967 not found: 0 always found: palindrom 2: found: 2026 not found: 0 3: found: 1957 not found: 0 4: found: 1913 not found: 0 5: found: 1939 not found: 0 6: found: 1994 not found: 0 7: found: 1958 not found: 0 8: found: 1935 not found: 0 9: found: 1995 not found: 0 10: found: 1991 not found: 0 11: found: 2070 not found: 0 12: found: 0 not found: 1954 never found: reverse exists 13: found: 0 not found: 2010 never found: reverse exists 14: found: 0 not found: 2029 never found: reverse exists 15: found: 2004 not found: 0 always found: reverse don't exist 16: found: 2029 not found: 0 17: found: 2010 not found: 0 18: found: 1935 not found: 0 19: found: 2016 not found: 0 20: found: 2027 not found: 0 21: found: 0 not found: 2022 never found: reverse exists 22: found: 2016 not found: 0 23: found: 0 not found: 2017 never found: reverse exists 24: found: 0 not found: 1988 never found: reverse exists 25: found: 2022 not found: 0 26: found: 2064 not found: 0 27: found: 1951 not found: 0 28: found: 2037 not found: 0 29: found: 1959 not found: 0 30: found: 1981 not found: 0 31: found: 0 not found: 1932 never found: reverse exists 32: found: 0 not found: 2037 never found: reverse exists 33: found: 1962 not found: 0 34: found: 0 not found: 1986 never found: reverse exists 35: found: 2017 not found: 0 36: found: 1967 not found: 0 37: found: 2045 not found: 0 38: found: 1992 not found: 0 39: found: 1973 not found: 0 40: found: 2028 not found: 0 41: found: 0 not found: 1954 never found: reverse exists 42: found: 0 not found: 2016 never found: reverse exists 43: found: 0 not found: 2023 never found: reverse exists 44: found: 1980 not found: 0 45: found: 2031 not found: 0 46: found: 2046 not found: 0 47: found: 2020 not found: 0 48: found: 2047 not found: 0 49: found: 2078 not found: 0 50: found: 2050 not found: 0 N=100 10000 rounds num found: 28063 (of 100000) = 28.06% 1: found: 996 not found: 0 2: found: 965 not found: 0 3: found: 943 not found: 0 4: found: 1002 not found: 0 5: found: 974 not found: 0 6: found: 1014 not found: 0 7: found: 1024 not found: 0 8: found: 1014 not found: 0 9: found: 996 not found: 0 10: found: 1025 not found: 0 11: found: 1021 not found: 0 12: found: 0 not found: 957 never found: reverse exists (8) 13: found: 0 not found: 978 14: found: 0 not found: 997 15: found: 0 not found: 1000 16: found: 0 not found: 1004 17: found: 0 not found: 993 18: found: 0 not found: 993 19: found: 0 not found: 980 20: found: 1036 not found: 0 21: found: 0 not found: 973 never found: reverse exists (1) 22: found: 975 not found: 0 23: found: 0 not found: 1033 never found: reverse exists (7) 24: found: 0 not found: 974 25: found: 0 not found: 1007 26: found: 0 not found: 992 27: found: 0 not found: 1026 28: found: 0 not found: 972 29: found: 0 not found: 1019 30: found: 1032 not found: 0 always found: reverse don't exist (1) 31: found: 0 not found: 999 32: found: 0 not found: 1026 33: found: 1002 not found: 0 34: found: 0 not found: 955 35: found: 0 not found: 969 36: found: 0 not found: 1021 37: found: 0 not found: 1032 38: found: 0 not found: 1002 39: found: 0 not found: 989 40: found: 1002 not found: 0 41: found: 0 not found: 1018 42: found: 0 not found: 972 43: found: 0 not found: 994 44: found: 1002 not found: 0 45: found: 0 not found: 914 46: found: 0 not found: 1002 47: found: 0 not found: 1002 48: found: 0 not found: 1000 49: found: 0 not found: 1002 50: found: 983 not found: 0 51: found: 0 not found: 1002 52: found: 0 not found: 1006 53: found: 0 not found: 1046 54: found: 0 not found: 990 55: found: 1012 not found: 0 always 56: found: 0 not found: 1040 57: found: 0 not found: 977 58: found: 0 not found: 1009 59: found: 0 not found: 1035 60: found: 999 not found: 0 61: found: 0 not found: 1059 62: found: 0 not found: 986 63: found: 0 not found: 993 64: found: 0 not found: 996 65: found: 0 not found: 952 66: found: 978 not found: 0 always found, no reverse 67: found: 0 not found: 1014 68: found: 0 not found: 995 69: found: 0 not found: 1049 70: found: 1008 not found: 0 71: found: 0 not found: 973 72: found: 0 not found: 958 73: found: 0 not found: 1029 74: found: 0 not found: 963 75: found: 0 not found: 1036 76: found: 0 not found: 985 77: found: 967 not found: 0 78: found: 0 not found: 1004 79: found: 0 not found: 993 80: found: 979 not found: 0 81: found: 0 not found: 985 82: found: 0 not found: 955 83: found: 0 not found: 1061 84: found: 0 not found: 1047 85: found: 0 not found: 997 86: found: 0 not found: 1044 87: found: 0 not found: 1002 88: found: 1081 not found: 0 89: found: 0 not found: 1007 90: found: 1012 not found: 0 91: found: 0 not found: 922 92: found: 0 not found: 1041 93: found: 0 not found: 942 94: found: 0 not found: 1013 95: found: 0 not found: 1025 96: found: 0 not found: 993 97: found: 0 not found: 1037 98: found: 0 not found: 981 99: found: 1006 not found: 0 100: found: 1015 not found: 0 N=200 num found: 19042 (of 100000) = 19.04% num found: 1890 (of 10000) = 18.90% N=250 10000 rounds num found: 23391 (of 100000) = 23.39% 1: found: 403 not found: 0 2: found: 391 not found: 0 3: found: 376 not found: 0 4: found: 403 not found: 0 5: found: 417 not found: 0 6: found: 394 not found: 0 7: found: 389 not found: 0 8: found: 369 not found: 0 9: found: 411 not found: 0 10: found: 409 not found: 0 11: found: 385 not found: 0 12: found: 0 not found: 388 13: found: 0 not found: 417 14: found: 0 not found: 366 15: found: 0 not found: 395 16: found: 0 not found: 397 17: found: 0 not found: 388 18: found: 0 not found: 371 19: found: 0 not found: 359 20: found: 385 not found: 0 21: found: 0 not found: 423 22: found: 399 not found: 0 23: found: 0 not found: 438 24: found: 0 not found: 409 25: found: 0 not found: 380 26: found: 0 not found: 373 27: found: 0 not found: 465 28: found: 0 not found: 411 29: found: 0 not found: 376 30: found: 402 not found: 0 31: found: 0 not found: 352 32: found: 0 not found: 378 33: found: 413 not found: 0 34: found: 0 not found: 402 35: found: 0 not found: 411 36: found: 0 not found: 427 37: found: 0 not found: 433 38: found: 0 not found: 383 39: found: 0 not found: 446 40: found: 380 not found: 0 41: found: 0 not found: 390 42: found: 0 not found: 377 43: found: 0 not found: 404 44: found: 404 not found: 0 45: found: 0 not found: 397 46: found: 0 not found: 428 47: found: 0 not found: 403 48: found: 0 not found: 396 49: found: 0 not found: 407 50: found: 388 not found: 0 51: found: 0 not found: 432 52: found: 0 not found: 406 53: found: 0 not found: 419 54: found: 0 not found: 396 55: found: 403 not found: 0 56: found: 0 not found: 418 57: found: 0 not found: 412 58: found: 0 not found: 441 59: found: 0 not found: 401 60: found: 375 not found: 0 61: found: 0 not found: 432 62: found: 0 not found: 398 63: found: 0 not found: 402 64: found: 0 not found: 394 65: found: 0 not found: 406 66: found: 397 not found: 0 67: found: 0 not found: 391 68: found: 0 not found: 420 69: found: 0 not found: 398 70: found: 366 not found: 0 71: found: 0 not found: 397 72: found: 0 not found: 400 73: found: 0 not found: 401 74: found: 0 not found: 368 75: found: 0 not found: 422 76: found: 0 not found: 397 77: found: 413 not found: 0 78: found: 0 not found: 403 79: found: 0 not found: 399 80: found: 393 not found: 0 81: found: 0 not found: 385 82: found: 0 not found: 361 83: found: 0 not found: 417 84: found: 0 not found: 410 85: found: 0 not found: 395 86: found: 0 not found: 429 87: found: 0 not found: 400 88: found: 399 not found: 0 89: found: 0 not found: 414 90: found: 366 not found: 0 91: found: 0 not found: 393 92: found: 0 not found: 416 93: found: 0 not found: 401 94: found: 0 not found: 410 95: found: 0 not found: 387 96: found: 0 not found: 400 97: found: 0 not found: 391 98: found: 0 not found: 385 99: found: 421 not found: 0 100: found: 366 not found: 0 101: found: 0 not found: 418 102: found: 0 not found: 378 103: found: 0 not found: 387 104: found: 0 not found: 394 105: found: 0 not found: 379 106: found: 0 not found: 402 107: found: 0 not found: 393 108: found: 0 not found: 380 109: found: 0 not found: 409 110: found: 0 not found: 396 111: found: 419 not found: 0 112: found: 0 not found: 378 113: found: 0 not found: 409 114: found: 0 not found: 430 115: found: 0 not found: 378 116: found: 0 not found: 450 117: found: 0 not found: 422 118: found: 0 not found: 410 119: found: 0 not found: 424 120: found: 0 not found: 432 121: found: 0 not found: 401 122: found: 0 not found: 433 123: found: 0 not found: 378 124: found: 0 not found: 373 125: found: 0 not found: 419 126: found: 0 not found: 404 127: found: 0 not found: 413 128: found: 0 not found: 421 129: found: 0 not found: 408 130: found: 0 not found: 383 131: found: 0 not found: 399 132: found: 0 not found: 395 133: found: 382 not found: 0 134: found: 0 not found: 405 135: found: 0 not found: 372 136: found: 0 not found: 391 137: found: 0 not found: 390 138: found: 0 not found: 404 139: found: 0 not found: 437 140: found: 0 not found: 405 141: found: 0 not found: 385 142: found: 0 not found: 407 143: found: 0 not found: 416 144: found: 412 not found: 0 145: found: 0 not found: 390 146: found: 0 not found: 403 147: found: 0 not found: 439 148: found: 0 not found: 390 149: found: 0 not found: 387 150: found: 0 not found: 407 151: found: 0 not found: 419 152: found: 0 not found: 389 153: found: 0 not found: 426 154: found: 0 not found: 417 155: found: 409 not found: 0 156: found: 0 not found: 394 157: found: 0 not found: 384 158: found: 0 not found: 407 159: found: 0 not found: 412 160: found: 0 not found: 373 161: found: 0 not found: 411 162: found: 0 not found: 413 163: found: 0 not found: 426 164: found: 0 not found: 410 165: found: 0 not found: 425 166: found: 439 not found: 0 167: found: 0 not found: 430 168: found: 0 not found: 374 169: found: 0 not found: 372 170: found: 0 not found: 422 171: found: 0 not found: 395 172: found: 0 not found: 406 173: found: 0 not found: 409 174: found: 0 not found: 400 175: found: 0 not found: 401 176: found: 0 not found: 421 177: found: 395 not found: 0 178: found: 0 not found: 405 179: found: 0 not found: 381 180: found: 0 not found: 379 181: found: 0 not found: 409 182: found: 0 not found: 390 183: found: 0 not found: 386 184: found: 0 not found: 430 185: found: 0 not found: 403 186: found: 0 not found: 401 187: found: 0 not found: 409 188: found: 376 not found: 0 189: found: 0 not found: 375 190: found: 0 not found: 414 191: found: 0 not found: 387 192: found: 0 not found: 397 193: found: 0 not found: 412 194: found: 0 not found: 394 195: found: 0 not found: 389 196: found: 0 not found: 393 197: found: 0 not found: 419 198: found: 0 not found: 421 199: found: 414 not found: 0 200: found: 400 not found: 0 201: found: 0 not found: 375 202: found: 0 not found: 389 203: found: 0 not found: 386 204: found: 0 not found: 375 205: found: 0 not found: 410 206: found: 378 not found: 0 207: found: 385 not found: 0 208: found: 402 not found: 0 209: found: 429 not found: 0 210: found: 0 not found: 415 211: found: 0 not found: 396 212: found: 0 not found: 400 213: found: 0 not found: 382 214: found: 0 not found: 412 215: found: 0 not found: 405 216: found: 0 not found: 378 217: found: 0 not found: 389 218: found: 0 not found: 375 219: found: 0 not found: 424 220: found: 0 not found: 449 221: found: 0 not found: 398 222: found: 447 not found: 0 223: found: 0 not found: 366 224: found: 0 not found: 427 225: found: 403 not found: 0 226: found: 359 not found: 0 227: found: 396 not found: 0 228: found: 378 not found: 0 229: found: 420 not found: 0 230: found: 0 not found: 373 231: found: 0 not found: 382 232: found: 0 not found: 409 233: found: 382 not found: 0 234: found: 0 not found: 367 235: found: 384 not found: 0 236: found: 372 not found: 0 237: found: 420 not found: 0 238: found: 377 not found: 0 239: found: 400 not found: 0 240: found: 0 not found: 379 241: found: 0 not found: 385 242: found: 0 not found: 388 243: found: 0 not found: 417 244: found: 385 not found: 0 245: found: 386 not found: 0 246: found: 399 not found: 0 247: found: 437 not found: 0 248: found: 350 not found: 0 249: found: 439 not found: 0 250: found: 0 not found: 367 N=500 100_000 rounds num found: 11233 (of 100000) = 11.23% N=999 100_000 rounds num found: 4469 (of 100000) = 4.47% N=2000 num found: 259 (of 10000) = 2.59% */ go => % get the hit rate of the numbers from 1..1000 Rounds = 10_000, foreach(N in 1..1000) garbage_collect(300_000_000), [NumFound,Pct] = test(N,Rounds), printf("%d num_found: %d pct: %2.2f%%\n",N,NumFound, Pct) end, nl. go1 => N = 2000, FoundMap = new_map(), NotFoundMap = new_map(), NumFound = 0, Rounds = 10_000, foreach(T in 1..Rounds) if T mod 1000 == 0 then println(test=T) end, % [MissingNumber,Found] = check_simple2(N), generate_problem(N,MissingNumber,SortedDigits,MissingNumbers,MissingDigits), [MissingNumber,Found] = check_simple2(N,MissingNumber,SortedDigits,MissingNumbers,MissingDigits), if Found.len == 1, Found.first()=MissingNumber then FoundMap.put(MissingNumber,FoundMap.get(MissingNumber,0)+1), NumFound := NumFound + 1 else NotFoundMap.put(MissingNumber,NotFoundMap.get(MissingNumber,0)+1) end end, printf("N = %d num found: %d (of %d) = %2.2f%%\n", N, NumFound, Rounds, 100*NumFound / Rounds), foreach(I in 1..N) printf("%3d: found: %5d not found: %5d\n", I, FoundMap.get(I,0), NotFoundMap.get(I,0)) end, nl. % calculate the maximal probability of a hit % Note: This is not the complete algorithm, just the upper limit of % what we can expect of number/pct of hits. go2 => N = 1000, Pcts = [], foreach(I in 1..N) [Hits,Misses] = check_hit(I), Pct = 100*Hits/I, printf("%d hits:%3d misses:%d %2.2f%%\n", I, Hits, Misses, Pct), Pcts := Pcts ++ [Pct] end, % println(Pcts), nl. % generate and test a single instance go3 => N=250, generate_problem(N,MissingNumber,SortedDigits,MissingNumbers,MissingDigits), [MiniZinc,Filename] = minizinc(N,MissingNumber,SortedDigits,MissingNumbers,MissingDigits), println(missingNumber=MissingNumber), println(missingNumbers=MissingNumbers), println(missingDigits=MissingDigits), [MissingNumber2,Found] = check_simple2(N,MissingNumber,SortedDigits,MissingNumbers,MissingDigits), printf("N = %d MissingNumber: %w found: %w\n", N, MissingNumber, Found), Status = not_found, if Found.len == 1, Found.first()=MissingNumber then Status := found end, println(picat_status=Status), run_minizinc(MiniZinc,Filename), println(picat_status=Status), nl. check_hit(N) = [Hits,Misses] => L = [I.to_string() : I in 1..N], Hits = 0, Misses = 0, foreach(I in 1..N) S = I.to_string(), R = reverse(S), if is_palindrom(S) ; not membchk(R,L) then Hits := Hits + 1 else Misses := Misses + 1 end end. is_palindrom(S) => S == reverse(S). test(N,Rounds) = [NumFound,Pct] => FoundMap = new_map(), NotFoundMap = new_map(), NumFound = 0, foreach(T in 1..Rounds) % if T mod 1000 == 0 then println(test=T) end, generate_problem(N,MissingNumber,SortedDigits,MissingNumbers,MissingDigits), [MissingNumber,Found] = check_simple2(N,MissingNumber,SortedDigits,MissingNumbers,MissingDigits), if Found.len == 1, Found.first()=MissingNumber then FoundMap.put(MissingNumber,FoundMap.get(MissingNumber,0)+1), NumFound := NumFound + 1 else NotFoundMap.put(MissingNumber,NotFoundMap.get(MissingNumber,0)+1) end end, Pct = 100*NumFound / Rounds. % printf("N = %d num found: %d (of %d) = %2.2f%%\n", N, NumFound, Rounds, 100*NumFound / Rounds), % foreach(I in 1..N) % printf("%3d: found: %5d not found: %5d\n", I, FoundMap.get(I,0), NotFoundMap.get(I,0)) % end, % nl. % % Generate a problem of N size and Check for the missing number. % check_simple2(N,MissingNumber,SortedDigits,MissingNumbers,MissingDigits) = [MissingNumber,Found] => % generate_problem(N,MissingNumber,SortedDigits,MissingNumbers,MissingDigits), [MiniZinc,Filename] = minizinc(N,MissingNumber,SortedDigits,MissingNumbers,MissingDigits), % Len = SortedDigits.len, MissingDigitsLen = MissingDigits.len, SumMissingNumbers = sum_numbers(MissingDigits), SumNumbers = sum_numbers(SortedDigits), DiffSum = SumNumbers - SumMissingNumbers, LenDiff = SortedDigits.len - MissingDigits.len, % Count the number of digits in the complete string MapAllDigits = new_map(), foreach(I in SortedDigits) S = I.to_string(), MapAllDigits.put(S,MapAllDigits.get(S,0)+1) end, % Count the number of digits in the instance string MapMissingDigits = new_map(), foreach(I in MissingDigits) S = I.to_string(), MapMissingDigits.put(S,MapMissingDigits.get(S,0)+1) end, % Which digits are in the missing number? MissingContains = [], foreach(I in 0..9) S = I.to_string(), if MapMissingDigits.get(S,0) != MapAllDigits.get(S,0) then MissingContains := MissingContains ++ S end end, % check if this number might be the missing number Found1 = [], foreach(I in 1..N) S = I.to_string(), SLen = S.len, if SLen == LenDiff then C = [H : H in S, membchk(H, MissingContains)], if C.sort() == S.sort(), SLen == LenDiff, sum_numbers(S) == DiffSum then % if not find(MissingNumbers,S,From,To) then Found1 := Found1 ++ [I] % end end end end, Found = Found1. sum_numbers(S) = sum([I.to_int() : I in S]). random_perm(L,N) = Perm => Perm = L, Len = L.length, _ = random2(), foreach(_I in 1..N) R1 = 1+(random() mod Len), R2 = 1+(random() mod Len), T = Perm[R1], Perm[R1] := Perm[R2], Perm[R2] := T end. generate_problem(N,MissingNumber, SortedDigits,MissingNumbersPlain,MissingDigits) => % All numbers 1..N AllNumbersOrdered = [I.to_string() : I in 1..N].join(''), % we don't know the complete string SortedDigits = [I.to_int() : I in AllNumbersOrdered], Random = random_perm(1..N,N*2), % AllNumbers = [I.to_string() : I in Random].join(''), % missing if var(MissingNumber) then MissingNumber = 1+random2() mod N end, MissingNumbersPlain = [I : I in Random, I != MissingNumber].flatten(), MissingNumbers = [I.to_string() : I in MissingNumbersPlain].join(''), MissingNumbersInt = [I.to_int() : I in MissingNumbers], MissingDigits = MissingNumbersInt. minizinc(N,MissingNumber,SortedDigits,MissingNumbers,MissingDigits) = [Out2,Filename] => Out = "", Out := Out ++ to_fstring("n=%d;\n", N), Out := Out ++ to_fstring("max_len=%w;\n", N.to_string().len), Out := Out ++ to_fstring("digits_all=%w;\n", SortedDigits), Out := Out ++ to_fstring("num_digits_all=%w;\n", SortedDigits.len), Out := Out ++ to_fstring("%% missing number: %d\n", MissingNumber), Out := Out ++ to_fstring("%% missing_numbers = %w\n", MissingNumbers), Out := Out ++ to_fstring("digits_missing=%w;\n", MissingDigits), Out := Out ++ to_fstring("num_digits_missing=%w;\n", MissingDigits.len), Filename = to_fstring("find_missing_number_%d_%d.dzn", N, MissingNumber), Out := Out ++ to_fstring("%% Save as %w\n", Filename), Out2 = Out. run_minizinc(MiniZinc,Filename) => println(filename=Filename), FD = open(Filename,write), println(FD,MiniZinc), close(FD), println("\n\nMiniZinc model:"), Mzn = to_fstring("/home/hakank/bin/mzx2.pl /home/hakank/g12/me/find_missing_number.mzn %w", Filename), _ = command(Mzn), nl. number_len(N) = ceiling(log10(N+1)).