mastermind.rb

require 'net/http'
require 'json'
require 'set'
require 'yaml'

REPEATS = true
LEVEL = 6

test_all = ARGV.delete('-a')

class Client
  def initialize(token)
    @uri = URI('https://mastermind.praetorian.com')
    @http = Net::HTTP.start(@uri.host, @uri.port, use_ssl: true)
    @token = token
  end

  def level(n)
    JSON.parse(@http.get("/level/#{n}/", 'Auth-Token' => @token).body)
  end

  def guess(n, g)
    JSON.parse(@http.post("/level/#{n}/", JSON.dump({'guess' => g.map { |x| x - 1 }}), 'Auth-Token' => @token, 'Content-Type' => 'application/json').body)
  end
end

class FakeClient
  def initialize(answer, level)
    @answer = answer.freeze
    @guesses = level.delete('numGuesses')
    @level = level.freeze
  end

  def level(_)
    @level
  end

  def guess(_, g)
    raise "nope, it was #{@answer}" if @guesses == 0
    @guesses -= 1
    {'response' => score(g, @answer)}
  end
end

class InteractiveClient
  def initialize(level)
    @guesses = level.delete('numGuesses')
    @level = level.freeze
  end

  def level(_)
    @level
  end

  COLOURS = [
    ['1;41', 'Red'],
    ['1;43', 'Yellow'],
    ['1;42', 'Green'],
    ['1;44', 'Blue'],
    ['48;5;172', 'Orange'],
    ['1;45', 'Purple'],
    ['48;5;94', 'Brown'],
    ['1;46', 'Cyan'],
  ]

  def guess(_, g)
    raise 'failed' if @guesses == 0
    @guesses -= 1
    puts "guess #{g.map { |v| "\e[#{COLOURS[v - 1][0] }m   \e[0m"}.join(' ')} (#{g.map { |v| COLOURS[v - 1][1] }.join(' ')})"
    puts "input two digits, black white:"
    input = STDIN.gets
    b, w = input.chomp.chars.map(&method(:Integer))
    {'response' => [b + w, b] }
  end
end

# 0: Number of guesses correct, regardless of position (white + black)
# 1: Number of guesses correct and in correct position (black)
# made this way because that's how praetorian did it
# conversion to/from black/white format should be trivial
def score(l1, l2)
  h1 = Hash.new(0)
  h2 = Hash.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 }, place]
end

# 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(length, choices, used, free, zero, repeats: false)
  # Don't need more frees than there are spots.
  frees_remaining = (choices - used.size).clamp(0, length)
  free_reps = (-frees_remaining..-1).to_a
  zero_rep = zero.empty? ? [] : [0]

  raw = (free_reps + zero_rep + used.to_a).repeated_permutation(length).select { |r|
    negs = r.select(&:negative?)
    # "For the first guess or exclusive free color codes, the order of all colors is also reorganized"
    if negs.size == length
      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
  }
  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 == length - zeroes.size
  } unless repeats
  # The free colours should come in order.
  free_canon = free.to_a.sort
  zero_canon = zero.to_a.sort
  raw.map { |r|
    zeroes_used = -1
    r.map { |x| x == 0 ? (zero_canon[repeats ? 0 : zeroes_used += 1]) : x > 0 ? x : free_canon[-x - 1] }
  }
end

if false
  ug = unique_guesses(4, 6, Set.new, (1..6).to_a, Set.new, repeats: REPEATS)
  puts "#{ug.size} uniques"
  ug.each { p _1 }
  exit 0
end

class FullTreeGame
  def initialize(length, choices, cache: true, repeats: false)
    @length = length
    @choices = choices
    @repeats = repeats
    @universe = (1..choices).to_a.send(repeats ? :repeated_permutation : :permutation, length).to_a
    if File.exist?(cache_file)
      @tree = YAML.load_file(cache_file)
    else
      used = Set.new
      free = (1..choices).to_set
      zero = Set.new
      @tree = make(used, free, zero, @universe)
      File.write(cache_file, YAML.dump(@tree))
    end

    @pointer = @tree
  end

  def guess
    @pointer[:guess]
  end

  def progress
    @pointer[:worst_case]
  end

  def record_response(_, r)
    @pointer = @pointer[:groups][r]
  rescue
    puts "FAIL!!! Tried #{r}, but I am #{@pointer}"
    raise
  end

  def cache_file
    "mastermind-cache-#{@length}-#{@choices}#{'-repeats' if @repeats}"
  end

  def make(used, free, zero, possible_answers)
    return {guess: possible_answers[0].freeze, worst_case: 1}.freeze if possible_answers.size == 1

    guesses = unique_guesses(@length, @choices, used, free, zero, repeats: @repeats).map { |guess|
      {
        guess: guess.freeze,
        groups: groups = possible_answers.group_by { |c| score(guess, c) },
        worst_case: max_size = groups.map { |_, v| v.size }.max,
        # 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]
        score: max_size * 2 + (possible_answers.include?(guess) ? 0 : 1),
      }
    }

    best_guess = guesses.min_by { _1[:score] }
    best_guess.delete(:score)
    best_guess[:groups] = best_guess[:groups].to_h { |score, possibilities|
      new_used = used | best_guess[:guess]
      new_free = free - best_guess[:guess]
      new_zero = zero.dup
      new_zero |= best_guess[:guess] if score[0] == 0
      # If number of pegs == number of spots, all colours NOT guessed are zeroes.
      new_zero |= ((1..@choices).to_a - best_guess[:guess]) if score[0] == @length

      [score, make(new_used.freeze, new_free.freeze, new_zero.freeze, possibilities)]
    }.freeze

    best_guess.freeze
  end
end

def universe_with(length, choices, repeats: false)
  choices.send(repeats ? :repeated_permutation : :permutation, length).to_set
end

class RandomGame
  def initialize(length, choices, repeats: false)
    @length = length
    @repeats = repeats
    @filter_choices = length * 2 < choices
    @universe = @filter_choices ? (1..choices).to_a.send(repeats ? :repeated_combination : :combination, length).to_a : universe_with(length, (1..choices).to_a, repeats: repeats)
  end

  def guess
    @universe.sample
  end

  def progress
    @universe.size
  end

  def record_response(g, r)
    if @filter_choices
      @universe.select! { |x| score(x, g)[0] == r[0] }
      # We could be more generous and flatten when we have, say, length * 2 choices in the universe.
      # But it takes too much to keep checking whether that's true.
      if @universe.size == 1
        @universe = universe_with(@length, @universe.flatten.uniq, repeats: @repeats)
        @filter_choices = false
      end
    else
      @universe.select! { |x| score(x, g) == r }
    end
  end
end

#Game = RandomGame
Game = FullTreeGame

#client = Client.new(File.read(__dir__ + '/secrets/praetorian-token').chomp)
#client = FakeClient.new([6, 5, 4, 3], 'numWeapons' => 6, 'numGladiators' => 4, 'numGuesses' => 8)
#client = FakeClient.new([6, 5, 4, 3, 7], 'numWeapons' => 10, 'numGladiators' => 5, 'numGuesses' => 10)
#client = FakeClient.new([6, 5, 4, 3], 'numWeapons' => 6, 'numGladiators' => 4, 'numGuesses' => 6)
#client = FakeClient.new([6, 5, 4, 3, 7, 21], 'numWeapons' => 25, 'numGladiators' => 6, 'numGuesses' => 18)
#client = FakeClient.new([6, 5, 4, 3], 'numWeapons' => 6, 'numGladiators' => 4, 'numGuesses' => 6, 'numRounds' => 25)
#client = FakeClient.new([6, 5, 4, 3, 7], 'numWeapons' => 10, 'numGladiators' => 5, 'numGuesses' => 7, 'numRounds' => 10)
# https://www.chiark.greenend.org.uk/~sgtatham/puzzles/js/guess.html "Standard"
client = InteractiveClient.new('numWeapons' => 6, 'numGladiators' => 4, 'numGuesses' => 10)
# https://www.chiark.greenend.org.uk/~sgtatham/puzzles/js/guess.html "Super"
#client = InteractiveClient.new('numWeapons' => 8, 'numGladiators' => 5, 'numGuesses' => 12)

level = client.level(LEVEL)
p level

def play(level, client)
  (level['numRounds'] || 1).times { |game_i|
    game = Game.new(level['numGladiators'], level['numWeapons'], repeats: REPEATS)
    1.step { |n|
      guess = game.guess
      response = client.guess(LEVEL, guess)
      puts "Game #{game_i + 1} Guess #{n}: #{guess}, got #{response}, progress #{game.progress}"

      break if response.has_key?('roundsLeft')

      # This only happens on FakeClient (too lazy to code the roundsLeft)
      return n if response['response'] == [level['numGladiators'], level['numGladiators']]

      return if response['message'] == 'Onto the next level'
      return if response.has_key?('hash')

      game.record_response(guess, response['response'])
    }
  }
end

# Test all
if test_all
  freq = Hash.new(0)
  failures = []
  too_long = []
  (1..6).to_a.repeated_permutation(4) { |ans|
    client = FakeClient.new(ans, 'numWeapons' => 6, 'numGladiators' => 4, 'numGuesses' => 10)
    begin
      guesses = play(level, client)
    rescue => e
      puts "FAIL!!! #{e}"
      guesses = :fail
      failures << ans.dup.freeze
    end
    if guesses > 5
      too_long << ans.dup.freeze
    end
    freq[guesses] += 1
    p freq
  }
  puts "Failures: #{failures}"
  puts "Too long: #{too_long}"
  exit 0
end

play(level, client)

# test a particularly troublesome one.
if false
  client = FakeClient.new([1, 4, 1, 5], 'numWeapons' => 6, 'numGladiators' => 4, 'numGuesses' => 10)
  guesses = play(level, client)
  puts "Took #{guesses} guesses"
  exit 0
end