Mastermind

mastermind.cr

alias Elt = Int32
alias Count = Int32

SPOTS = 4
COLOURS = 6
REPEATS = true
OPT = true

INTERACTIVE = ARGV.includes?("-i") || ARGV.includes?("--interactive")

# Two-tuple:
# First element: # of guesses in correct position (black peg)
# Second element: # of guesses of correct colour but incorrect position (white peg)
def score(l1 : Array(Elt), l2 : Array(Elt)) : Tuple(Count, Count)
  h1 = Hash(Elt, Count).new(0)
  h2 = Hash(Elt, Count).new(0)

  place = 0

  l1.zip(l2) { |v1, v2|
    if v1 == v2
      place += 1
    else
      h1[v1] += 1
      h2[v2] += 1
    end
  }

  {place, h1.reduce(0) { |acc, (k, v)| acc + {v, h2[k]}.min }}
end

puts "#{Time.utc}: M(#{SPOTS},#{COLOURS}) with#{REPEATS ? "" : "OUT"} repeats"

# Filter by free/zero signature
# An Optimal Mastermind (4,7) Strategy and More Results in the Expected Case
# Ville, Greoffrey
# 2013 March
# https://arxiv.org/pdf/1305.1010.pdf
def unique_guesses(used : Set(Elt), free : Set(Elt), zero : Set(Elt))
  # Don't need more frees than there are spots.
  frees_remaining = {SPOTS, {COLOURS - used.size, 0}.max}.min
  free_reps = (-frees_remaining..-1).to_a
  zero_rep = zero.empty? ? [] of Elt : [0]

  raw = (free_reps + zero_rep + used.to_a).repeated_permutations(SPOTS)
  raw.select! { |x|
    zeroes, nonzeroes = x.partition { |y| y == 0 }
    # No repeats means:
    # Each zero in guess needs a representative zero colour.
    # No repeats in nonzeroes.
    zeroes.size <= zero.size && nonzeroes.uniq.size == SPOTS - zeroes.size
  } unless REPEATS
  raw.select! { |r|
    negs = r.select { |x| x < 0 }
    # "For the first guess or exclusive free color codes, the order of all colors is also reorganized"
    if negs.size == SPOTS
      next false if negs.sort != negs
      # make 1123 and 1223 and 1233 equivalent, by enforcing increasing group size
      by_freq = negs.group_by(&.itself).values.map(&.size)
      next false if by_freq.sort != by_freq
    end
    # Prevent gaps in frees, like -1 and -3 (in which case -negs.min is 3 and uniq is 2)
    negs.empty? || negs.uniq.size == -negs.min && negs.uniq.sort == negs.uniq
  }
  free_canon = free.to_a.sort
  # Don't need to canonicalize zeroes, so just leave them as zeroes here.
  raw.map { |r|
    r.map { |x| x >= 0 ? x : free_canon[-x - 1] }
  }
end

free = (1..COLOURS).to_set
used = Set(Elt).new
zero = Set(Elt).new

ug = unique_guesses(used, free, zero)
puts "#{ug.size} unique guesses:"
ug.each { |x| p x }

initial_choices = (1..COLOURS).to_a.repeated_permutations(SPOTS)
initial_choices.select! { |x| x.uniq.size == SPOTS } unless REPEATS
puts "#{Time.utc}: #{initial_choices.size} generated"

choices = initial_choices

0.step { |n|
  guess = (OPT ? unique_guesses(used, free, zero) : initial_choices).min_by { |possible_guess|
    groups = choices.group_by { |c| score(possible_guess, c) }
    # If tied between multiple best guesses, choose one that's possible over one that's not
    # see [1, 4, 1, 5] where this matters, guess 3 should be [5, 1, 1, 4] not [5, 1, 2, 3]
    groups.map { |_, v| v.size }.max * 2 + (choices.includes?(possible_guess) ? 0 : 1)
  }

  groups = choices.group_by { |c| score(guess, c) }
  largest_group = groups.max_by { |_, v| v.size }

  puts "#{Time.utc}: Guess #{n + 1}: #{guess}. Worst case: #{largest_group[0]} has #{largest_group[1].size} cases"

  if INTERACTIVE
    puts "Input two digits, black white:"
    break unless (a = STDIN.gets)
    resp = a.chars.map(&.to_i)
    raise "bad response #{resp}" unless resp.size == 2
    response = {resp[0], resp[1]}
    choices = groups[response]
  else
    response, choices = largest_group
  end

  used |= guess.to_set
  free -= guess
  zero |= guess.to_set if response == {0, 0}
  # If number of pegs == number of spots, all colours NOT guessed are zeroes.
  zero |= ((1..COLOURS).to_a - guess).to_set if response[0] + response[1] == SPOTS

  if choices.size == 1
    puts "Win on guess #{n + 2}; groups are #{groups}"
    break
  end
}