Вдохновлен Великой API Охота за пасхальными яйцами!

Резюме

Ваша задача - найти заранее заданное целое число в «пространстве Коллатца» (будет объяснено позже), используя наименьший возможный шаг.

Вступление

Эта проблема основана на известной гипотезе Коллатца, о которой, надеюсь, все здесь хотя бы слышали. Вот резюме, взятое из Печать номеров Super Collatz .

Последовательность Коллатца (также называемая проблемой 3x + 1) - это место, где вы начинаете с любого положительного целого числа, в этом примере мы будем использовать 10 и применим к нему следующий набор шагов:

if n is even:
    Divide it by 2
if n is odd:
    Multiply it by 3 and add 1
repeat until n = 1

Расстояние Коллатца C(m,n)между двумя числами mи n, для целей этой задачи, представляет собой расстояние между двумя числами в графе Коллатца (Кредиты @tsh для рассказа об этой концепции), которое определяется следующим образом: (с использованием 21и в 13качестве примеров ):

Запишите последовательность Коллатца для m(в данном случае 21):

21, 64, 32, 16, 8, 4, 2, 1

Запишите последовательность Коллатца для n(в данном случае 13):

13, 40, 20, 10, 5, 16, 8, 4, 2, 1

Теперь посчитайте, сколько чисел появляется только в одной из последовательностей. Это определяется как расстояние Коллатца между mи n. В этом случае 8, а именно

21, 64, 32, 13, 40, 20, 10, 5

Таким образом, у нас есть Collatz расстояние между 21и 13как C(21,13)=8.

C(m,n) иметь следующие хорошие свойства:

C(m,n)=C(n,m)
C(m,n)=0 iff. m=n

Надеюсь, определение C(m,n)теперь ясно. Давайте начнем заниматься охотой на яйца в пространстве Collatz!

В начале игры контроллер решает положение пасхального яйца, которое выражается его одномерной координатой: целое число в интервале [p,q](другими словами, целое число между pи qоба конца включительно).

Положение яйца остается неизменным на протяжении всей игры. Мы будем обозначать эту координату как r.

Теперь вы можете сделать начальное предположение ₀ , и оно будет записано контроллером. Это твой 0-й раунд. Если вам так повезло, что вы поняли это правильно на первом месте (то есть ₀ = r), игра заканчивается, и ваш счет равен 0(Чем меньше счет, тем лучше). В противном случае, вы входите в 1-й раунд и делаете новое предположение ₁ , это продолжается до тех пор, пока вы не сделаете это правильно, то есть a _n = r, и ваш счет будет n.

Для каждого раунда после 0-го контроллер дает вам одну из следующих отзывов, чтобы вы могли сделать более правильное предположение на основе предоставленной информации. Давайте предположим , что вы в настоящее время в nм круге и , следовательно , ваше предположение является _п

• "Ты нашел это!" если a _n = r, в этом случае игра заканчивается, и вы забиваете n.
• «Вы ближе :)», если C (a _n , r) <C (a _n-1 , r)
• «Вы кружите вокруг яйца», если C (a _n , r) = C (a _n-1 , r)
• «Вы находитесь дальше :(», если C (a _n , r)> C (a _n-1 , r)

Чтобы сохранить некоторые байты, я буду называть ответы как «Право», «Ближе», «То же самое», «Дальше» в порядке, указанном выше.

Вот пример игры с p=1,q=15.

• ₀ = 10
• a ₁ = 11, ответ: «Ближе»
• а ₂ = 13, ответ: «Дальше»
• а ₃ = 4, ответ: «Дальше»
• а ₄ = 3, ответ: "Ближе"
• ₅ = 5, ответ: " То же"
• а ₆ = 7, ответ: «Верно»

Оценка: 6.

Вызов

Разработайте детерминированную стратегию, чтобы играть в игру p=51, q=562с лучшим счетом.

Ответы должны подробно описать алгоритмы. Вы можете прикрепить любой код, который поможет выяснить алгоритм. Это не Codegolf, поэтому вам предлагается написать разборчивый код.

Ответы должны включать наихудший балл, который они могут получить во всех возможных случаях r, и выигрывает тот, у кого наименьший наихудший балл. В случае ничьей выигрывают алгоритмы, которые имеют лучший средний балл для всех возможных rs (которые также должны быть включены в ответы). Дальнейших тай-брейков больше нет, и в итоге у нас может быть несколько победителей.

Спекуляции

• Повторюсь, rлежит в промежутке [51,562].
• Применяются лазейки по умолчанию .

Щедрость (добавляется после публикации первого ответа)

Я могу лично предложить вознаграждение за ответ, где все предположения сделаны в пределах диапазона, [51,562]при этом все еще имея достаточно низкий худший результат.

Рубин, 196

Это было намного сложнее, чем я изначально думал. Мне пришлось разобраться со многими непонятными случаями, и в результате я получил много уродливого кода. Но это было очень весело! :)

стратегия

Каждая последовательность Коллатца заканчивается последовательностью степеней 2 (например: [16, 8, 4, 2, 1]). Как только встречается степень 2, мы делим на 2, пока не достигнем 1. Давайте назовем первую степень 2 в последовательности, ближайшей к pow2 (так как это также ближайшая степень 2 к нашему числу, используя расстояние Коллатца). Для данного диапазона (51-562) все возможные ближайшие числа pow2 : [16, 64, 128, 256, 512, 1024]

Укороченная версия

Алгоритм выполняет:

• двоичный поиск, чтобы выяснить ближайшую степень 2 к текущему числу
• линейный поиск, чтобы выяснить каждый предыдущий элемент в последовательности, пока не будет обнаружено целевое число.

Подробная версия

Для игры с целевым номером rстратегия следующая:

1. Используйте бинарный поиск, чтобы выяснить степень 2, которая наиболее близка к rминимально возможному числу шагов.
2. Если ближайшая степень 2, которая была найдена, является решением, остановитесь. В противном случае перейдите к 3.
3. Поскольку найденная степень 2 является первой степенью 2, встречающейся в последовательности, если из этого следует, что это значение было достигнуто с помощью операции (* 3 + 1). (Если бы он пришел после операции / 2, то предыдущее число также было бы степенью 2). Вычислите предыдущее число в последовательности, выполнив обратную операцию (-1, а затем / 3)
4. Если это число является целью, остановитесь. В противном случае перейдите к 5.
5. Учитывая текущий номер, известный из последовательности, необходимо вернуться назад и обнаружить предыдущий номер в последовательности. Неизвестно, было ли получено текущее число операцией (/ 2) или (* 3 +1), поэтому алгоритм пробует их обоих и видит, какое из них дает число, которое ближе (как расстояние Коллатца) от цели ,
6. Если найденный номер правильный, остановитесь.
7. Используя недавно обнаруженный номер, вернитесь к шагу 5.

Результаты

Выполнение алгоритма для всех чисел в диапазоне 51-562 занимает около секунды на обычном ПК, и общая оценка составляет 38665.

Код

Попробуйте онлайн!

require 'set'

# Utility methods
def collatz(n)
  [].tap do |results|
    crt = n
    while true
      results << crt
      break if crt == 1
      crt = crt.even? ? crt / 2 : crt * 3 + 1
    end
  end
end

def collatz_dist(m, n)
  cm = collatz(m).reverse
  cn = collatz(n).reverse
  common_length = cm.zip(cn).count{ |x, y| x == y }
  cm.size + cn.size - common_length * 2
end



GuessResult = Struct.new :response, :score
# Class that can "play" a game, responding
# :right, :closer, :farther or :same when
# presented with a guess
class Game

  def initialize(target_value)
    @r = target_value
    @score = -1
    @dist = nil
    @won = false
  end
  attr_reader :score

  def guess(n)
    # just a logging decorator over the real method
    result = internal_guess(n)
    p [n, result] if LOGGING
    result
  end

  private

  def internal_guess(n)
    raise 'Game already won!' if @won
    @score += 1
    dist = collatz_dist(n, @r)
    if n == @r
      @won = true
      return GuessResult.new(:right, @score)
    end
    response = nil
    if @dist
      response = [:same, :closer, :farther][@dist <=> dist]
    end
    @dist = dist
    GuessResult.new(response)
  end

end

# Main solver code

def solve(game)
  pow2, won = find_closest_power_of_2(game)
  puts "Closest pow2: #{pow2}" if LOGGING

  return pow2 if won
  # Since this is the first power of 2 in the series, it follows that
  # this element must have been arrived at by doing *3+1...
  prev = (pow2 - 1) / 3
  guess = game.guess(prev)
  return prev if guess.response == :right

  solve_backward(game, prev, 300)
end

def solve_backward(game, n, left)
  return 0 if left == 0
  puts "***      Arrived at  ** #{n} **" if LOGGING
  # try to see whether this point was reached by dividing by 2
  double = n * 2
  guess = game.guess(double)
  return double if guess.response == :right

  if guess.response == :farther && (n - 1) % 3 == 0
    # try to see whether this point was reached by *3+1
    third = (n-1) / 3
    guess = game.guess(third)
    return third if guess.response == :right
    if guess.response == :closer
      return solve_backward(game, third, left-1)
    else
      game.guess(n) # reset to n...
    end
  end
  return solve_backward(game, double, left-1)
end


# Every Collatz Sequence ends with a sequence of powers of 2.
# Let's call the first occurring power of 2 in such a sequence
# POW2
#
# Let's iterate through the whole range and find the POW2_CANDIDATES
#
RANGE = [*51..562]
POWERS = Set.new([*0..15].map{ |n| 2 ** n })

POW2_CANDIDATES =
  RANGE.map{ |n| collatz(n).find{ |x| POWERS.include? x} }.uniq.sort
# Turns out that the candidates are [16, 64, 128, 256, 512, 1024]

def find_closest_power_of_2(game)
  min = old_guess = 0
  max = new_guess = POW2_CANDIDATES.size - 1
  guess = game.guess(POW2_CANDIDATES[old_guess])
  return POW2_CANDIDATES[old_guess], true if guess.response == :right
  guess = game.guess(POW2_CANDIDATES[new_guess])
  return POW2_CANDIDATES[new_guess], true if guess.response == :right
  pow2 = nil

  while pow2.nil?

    avg = (old_guess + new_guess) / 2.0

    case guess.response
    when :same
      # at equal distance from the two ends
      pow2 = POW2_CANDIDATES[avg.floor]
      # still need to test if this is correct
      guess = game.guess(pow2)
      return pow2, guess.response == :right
    when :closer
      if old_guess < new_guess
        min = avg.ceil
      else
        max = avg.floor
      end
    when :farther
      if old_guess < new_guess
        max = avg.floor
      else
        min = avg.ceil
      end
    end

    old_guess = new_guess
    new_guess = (min + max) / 2
    new_guess = new_guess + 1 if new_guess == old_guess
    # so we get next result relative to the closer one
    # game.guess(POW2_CANDIDATES[old_guess]) if guess.response == :farther
    guess = game.guess(POW2_CANDIDATES[new_guess])

    if guess.response == :right
      pow2 = POW2_CANDIDATES[new_guess]
      break
    end

    if min == max
      pow2 = POW2_CANDIDATES[min]
      break
    end

  end

  [pow2, guess.response == :right]

end



LOGGING = false

total_score = 0
51.upto(562) do |n|
  game = Game.new(n)
  result = solve(game)
  raise "Incorrect result for #{n} !!!" unless result == n
  total_score += game.score
end
puts "Total score: #{total_score}"

худший балл: 11, общий балл: 3986

Все догадки в диапазоне [51,562].

Мой алгоритм:

1. Сначала угадать 512 и сохранить набор возможных результатов vals, первоначально набор содержит все числа в диапазоне [51,562].

2. На каждом этапе сделайте следующее:

   1. Найти значение следующего предположения guessв диапазоне [51,562]таким образом , что , когда значения в vals( за исключением guessсамого себя) разбивается на 3 наборов соответствующих возможных результатов Closer, Sameи Farther, размер максимум из этих 3 -х наборов минимальна.
      Если существует несколько возможных значений, guessудовлетворяющих вышесказанному, выберите наименьшее.
   2. Угадайте значение guess.
   3. Если ответ «Верно», готово (выйдите из программы).
   4. Удалите все значения в наборе vals, чтобы они не могли дать такой результат.

Моя эталонная реализация, написанная на C ++ и Bash, работает на моей машине примерно за 7,6 секунды и дает худшую оценку / сумму, как описано в заголовке.

Испытание всех возможных значений первого предположения займет около 1,5 часов на моей машине. Я могу рассмотреть возможность сделать это.