Test_Runner

Untitled

Jan 22nd, 2021
825
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. # author: TestRunner
  2. # MIT License: Free use, do with it what you will etc
  3. #
  4. # Usage:
  5. #   first enter the number of "colors", which is the
  6. #   number of different types of items that can be offered.
  7. #   In each round ender in a 5 digit number representing
  8. #   the game's response. 0 = Red, 1 = Yellow, 2 = Green.
  9. #
  10. #   - For 5 or fewer colors, if you don't get an expected
  11. #     response of 50% in the first round, then you should
  12. #     just restart and try again.
  13. #   - For 6 colors, it will be hard to get good odds in 3
  14. #     rounds. But you can generally reset until you get
  15. #     a lucky first round that give 33% or better in 3 rounds.
  16. #   - For 7 colors, getting it done in 3 rounds is besically
  17. #     impossible, but can almost always get a 4 with 95%+.
  18. #     As before, reset until the 4th round can be done in high
  19. #     odds.
  20. #
  21. #  Note 1: this code is not efficient at all. When the odds
  22. #  is low, it may take a really long time to generate a result
  23. #  (especially on 7+ colors where the odds are poor). If the
  24. #  process is taking too long to run, you might want to just
  25. #  terminate it because the odds are likely so bad that it's
  26. #  not worth doing.
  27. #
  28. #  Note 2: The reported odds may not actually be correct, and
  29. #  it's possible that the suggested guess is not the best.
  30. #  However it typically quite and generally similar to the best.
  31.  
  32. import math
  33. import random
  34. import itertools
  35. import time
  36.  
  37. def partitions(n, depth=-1, I=1):
  38.     if depth != 0:
  39.         yield (n,)
  40.         for i in range(I, n//2 + 1):
  41.             for p in partitions(n-i, depth-1, i):
  42.                 yield p + (i,)
  43.  
  44.  
  45. def inits():
  46.     for p in partitions(holes, colors):
  47.         yield tuple(
  48.             i + 1
  49.             for i,c in enumerate(p)
  50.             for j in range(c)
  51.         )
  52.  
  53.  
  54. def space(holes, min, max):
  55.     return itertools.product(range(min,max+1), repeat=holes)
  56.  
  57.  
  58. def sub_game(game, response, guess, check_color):
  59.     if all(map(lambda hole: hole == 1, response)):
  60.         print('no changes in sub game')
  61.         return game
  62.     if all(map(lambda hole: hole == 2, response)):
  63.         print('empty sub game')
  64.         return set()
  65.  
  66.     if check_color:
  67.         dead_colors = set(
  68.             c
  69.             for i,c in enumerate(guess)
  70.             if response[i] == 0
  71.         )
  72.     else:
  73.         dead_colors = set()
  74.  
  75.     return set([
  76.         tuple(
  77.             p[i]
  78.             for i,hole in enumerate(response)
  79.             if hole != 2
  80.         )
  81.         for p in game
  82.         if not any(map(lambda h: h in dead_colors, p))
  83.     ])
  84.  
  85.  
  86. def get_guess(key, guess):
  87.     key = list(key)
  88.     guess = list(guess)
  89.     holes = len(key)
  90.     assert len(key) == len(guess)
  91.  
  92.     response = list(blank)
  93.  
  94.     reds = 0
  95.     for i in range(holes):
  96.         if key[i] == guess[i]:
  97.             response[i] = 2
  98.             key[i] = -1
  99.             guess[i] = -1
  100.  
  101.     whites = 0
  102.     for i in range(holes):
  103.         if guess[i] < 0:
  104.             continue
  105.         if guess[i] in key:
  106.             response[i] = 1
  107.  
  108.     return tuple(response)
  109.  
  110.  
  111. def enter_guess(guess, response, candidates):
  112.     new_candidates = []
  113.     for p in candidates:
  114.         if response == get_guess(p, guess):
  115.             new_candidates.append(p)
  116.     return new_candidates
  117.  
  118.  
  119. def filter_responses(response, responses):
  120.     for r in responses:
  121.         if all(map(lambda i: response[i[0]] != 2 or i[1] == 2, enumerate(r))):
  122.             yield r
  123.  
  124.  
  125. def elim_count(guess, response, candidates, sample):
  126.     elim = 0
  127.     for p in random.sample(candidates, min(sample, len(candidates))):
  128.         if response != get_guess(p, guess):
  129.             elim += 1
  130.     return elim
  131.  
  132.  
  133. def solve_game(key, init, guesses, candidates, responses, output):
  134.     guess = init
  135.     while guesses > 0:
  136.         guesses -= 1        
  137.         if output:
  138.             print(f'guess - {guess}')
  139.  
  140.         guess_r = get_guess(key, guess)
  141.         if guess_r == correct:
  142.             if output:
  143.                 print(f'Match found')
  144.             return (guesses, guess)
  145.  
  146.         candidates = enter_guess(guess, guess_r, candidates)
  147.         responses = list(filter_responses(guess_r, responses))
  148.  
  149.         guess = get_best_guess(candidates, responses)[0]
  150.  
  151.     if output:
  152.         print(f'Match not found')
  153.     return (-1, None)
  154.  
  155.  
  156. def get_best_guess(candidates, responses):
  157.     best = []
  158.     best_min = 0
  159.  
  160.     for p in random.sample(candidates, min(s_size, len(candidates))):
  161.         min_e = 100000
  162.         for r in random.sample(responses, min(s_size, len(responses))):
  163.             min_e = min(min_e, elim_count(p, r, candidates, s_size))
  164.  
  165.         if min_e == best_min:
  166.             best.append(p)
  167.         elif min_e > best_min:
  168.             best = [p]
  169.             best_min = min_e
  170.  
  171.     return sorted(best)
  172.  
  173.  
  174.  
  175.  
  176.  
  177. holes = 5
  178. colors = int(input("Enter Color Count: "))
  179.  
  180. if colors > 10:
  181.     raise Exception("color count invalid")
  182.  
  183. correct = tuple([2] * holes)
  184. blank = [0] * holes
  185. S = list(space(holes, 1, colors))
  186. R = list(space(holes, 0, 2))
  187. init_list = {
  188.     1 : (1,1,1,1,1),
  189.     2 : (1,1,1,1,1),
  190.     3 : (1,1,2,2,3),
  191.     4 : (1,1,2,3,4),
  192.     5 : (1,2,3,4,5),
  193.     6 : (1,2,3,4,5),
  194.     7 : (1,2,3,4,5),
  195. }
  196. init = init_list[colors]
  197.  
  198. k_size = 200
  199. s_size = 1000000
  200.  
  201. guess = init
  202. remaining_guesses = 4
  203. candidates = S
  204. responses = R
  205.  
  206.  
  207. print(f" * Suggested guess: {guess}")
  208. while True:
  209.     remaining_guesses -= 1
  210.     if remaining_guesses == 0:
  211.         print("Game finished.")
  212.         exit(0)
  213.  
  214.     while True:
  215.         try:
  216.             text = input("Enter response (x to quit): ").strip()
  217.             if text == 'x':
  218.                 exit(0)
  219.             response = tuple(map(int, [c for c in text]))
  220.             if len(response) != holes:
  221.                 raise Exception
  222.             break
  223.         except Exception as e:
  224.             print("Invalid input")
  225.  
  226.     print(f'Response {response}')
  227.  
  228.     print(f'candidates {len(candidates)}, responses {len(responses)}')
  229.  
  230.     candidates = enter_guess(guess, response, candidates)
  231.     responses = list(filter_responses(response, responses))
  232.  
  233.     print(f'candidates {len(candidates)}, responses {len(responses)}')
  234.  
  235.     guess_options = get_best_guess(candidates, responses)
  236.     guess = guess_options[0]
  237.     print(f' * Suggested guess {guess}')
  238.  
  239.     success_4 = 0
  240.     success_3 = 0
  241.     avg_guesses = 0
  242.     sample_size = min(k_size, len(candidates))
  243.     for key in random.sample(candidates, sample_size):
  244.         #print(f'key - {key}')
  245.         (guesses, final_guess) = solve_game(key, guess, remaining_guesses-1, candidates, responses, False)
  246.         if guesses >= 0:
  247.             success_3 += 1
  248.     for key in random.sample(candidates, sample_size):
  249.         #print(f'key - {key}')
  250.         (guesses, final_guess) = solve_game(key, guess, remaining_guesses, candidates, responses, False)
  251.         if guesses >= 0:
  252.             success_4 += 1
  253.             avg_guesses += guesses
  254.     print(f' - Success rate (3 turns): {(success_3 / sample_size) * 100}%')
  255.     print(f' - Success rate (4 turns): {(success_4 / sample_size) * 100}%')
  256.     print(f' - Expected remaining gueses: {(avg_guesses / sample_size)}')
  257.  
  258.  
  259.  
  260.  
  261.  
  262.  
  263. #for init in inits():
  264. print(f'init - {init}')
  265. print(f'depth 3')
  266. success = 0
  267. avg_guesses = 0
  268. for key in random.sample(S, k_size):
  269.     #print(f'key - {key}')
  270.     (guesses, final_guess) = solve_game(key, init, 3, S, R, False)
  271.     if guesses >= 0:
  272.         success += 1
  273.         avg_guesses += guesses
  274. print(f' - Success rate: {(success / k_size) * 100}%')
  275. print(f' - Expected gueses: {3 - (avg_guesses / k_size)}')
  276.  
  277. print(f'init - {init}')
  278. print(f'depth 4')
  279. success = 0
  280. avg_guesses = 0
  281. for key in random.sample(S, k_size):
  282.     #print(f'key - {key}')
  283.     (guesses, final_guess) = solve_game(key, init, 4, S, R, False)
  284.     if guesses >= 0:
  285.         success += 1
  286.         avg_guesses += guesses
  287. print(f' - Success rate: {(success / k_size) * 100}%')
  288. print(f' - Expected gueses: {3 - (avg_guesses / k_size)}')
  289.  
  290.  
  291. exit(0)
  292.  
  293.  
  294.  
  295.  
  296.  
  297.  
  298.  
  299. guesses = 0
  300.  
  301. #init = (1, 1, 1, 2, 2)
  302. #key = tuple(random.randint(1, colors) for i in range(holes))
  303.  
  304. min_init = []
  305. min_guesses = 1000000
  306.  
  307. count = len(S)
  308. c = 0
  309.  
  310. start = time.time()
  311. print(f'ETA: Unknown - {c}/{count}', end='\r')
  312.  
  313. for init in S:
  314.     c += 1
  315.  
  316.     guesses = 0
  317.     for key in S:
  318.         guesses_1 = solve_game(key, init)
  319.         guesses += guesses_1
  320.     guesses = guesses / count
  321.  
  322.     if guesses == min_guesses:
  323.         min_init.append(init)
  324.     elif guesses < min_guesses:
  325.         min_init = [init]
  326.         min_guesses = guesses
  327.  
  328.     elapsed = time.time() - start
  329.     if c == count:
  330.         ETA = 0
  331.     else:
  332.         ETA = ((count / c) - 1) * elapsed
  333.     ftime = time.strftime("%H:%M:%S", time.gmtime(ETA))
  334.     print(f'ETA: {ftime} - {c}/{count}', end='\r')
  335.  
  336.  
  337. print(f'done')
  338.  
  339. print(f'avg guess: {min_guesses}')
  340. for i in min_init:
  341.     print(f'init - {i}')
  342.  
RAW Paste Data