Egg hunting in Collatz style

Question

Inspired by The Great API Easter Egg Hunt!

Summary

Your task is to search for a predetermined integer in the "Collatz space" (to be explained later) using the fewest step possible.

Introduction

This challenge is based on the famous Collatz conjecture that hopefully everyone here at least heard of. Here is a recap taken from Print the Super Collatz numbers.

The Collatz Sequence (also called the 3x + 1 problem) is where you start with any positive integer, for this example we will use 10, and apply this set of steps to it:

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

The Collatz distance C(m,n) between the two numbers m and n, for the purpose of this challenge, is the distance between two numbers in the Collatz graph(Credits to @tsh for telling me about this concept), which is defined as follows: (using 21 and 13 as examples):

Write down the Collatz sequence for m (in this case, 21):

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

Write down the Collatz sequence for n(in this case, 13):

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

Now count how many numbers appear only in one of the sequences. This is defined as the Collatz distance between m and n. In this case, 8, namely,

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

So we have Collatz distance between 21 and 13 as C(21,13)=8.

C(m,n) have the following nice properties:

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

Hopefully the definition of C(m,n) is now clear. Let's start doing egg hunting in the Collatz space!

At the beginning of the game, a controller decides the position of an easter egg, which is expressed by its one-dimensional coordinate: An integer in the interval [p,q] (in other words, an integer between p and q, both ends inclusive).

The position of the egg remains constant throughout the game. We'll denote this coordinate as r.

You can now make an initial guess a₀, and it will be recorded by the controller. This is your 0th round. If you are so lucky that you got it right at the first place (i.e. a₀=r), the game ends, and your score is 0(The lower the score, the better). Otherwise, you enter the 1st round and you make a new guess a₁, this goes on until you got it right, i.e. a_n=r, and your score will be n.

For each round after the 0th, the controller gives you one of the following feedbacks so that you can make a better guess based on the information given. Lets assume you are currently at the nth round and hence your guess is a_n

• "You found it!" if a_n=r, in which case the game ends and you score n.
• "You are closer :)" if C(a_n,r)<C(a_n-1,r)
• "You are circling around the egg" if C(a_n,r)=C(a_n-1,r)
• "You are farther away :(" if C(a_n,r)>C(a_n-1,r)

To save some bytes, I will call the responses as "Right", "Closer", "Same", "Farther", in the order presented above.

Here is an example game with p=1,q=15.

• a₀=10
• a₁=11, response: "Closer"
• a₂=13, response: "Farther"
• a₃=4, response: "Farther"
• a₄=3, response: "Closer"
• a₅=5, response: "Same"
• a₆=7, response: "Right"

Score: 6.

Challenge

Design a deterministic strategy to play the game for p=51, q=562 with the best score.

Answers should describe the algorithms in detail. You can attach any code that helps to elucidate the algorithm. This is not codegolf so you are encouraged to write legible code.

Answers should include the worst score they may achieve for all possible cases of r, and the one with lowest worst score wins. In the case of tie, the algorithms that has a better average score for all possible rs (which should also be included in the answers) win. There are no further tie breakers and we may have multiple winners in the end.

Specs

• To reiterate, r lies in the interval [51,562].
• Default loopholes apply.

Bounty (Added after the first answer is posted)

I may personally offer a bounty to an answer where all the guesses are made within the range [51,562] while still having a reasonably low worst score.

Answer 1

Ruby, 196

This was way harder that I initially thought. I had to handle a lot of obscure cases and ended up with a lot of ugly code. But is was a lot of fun! :)

Strategy

Every Collatz Sequence ends up with a sequence of powers of 2 (ex: [16, 8, 4, 2, 1]). As soon as a power of 2 is encountered, we divide by 2 until we reach 1. Let's call the first power of 2 in a sequence closest pow2 (as this is also the closest power of 2 to our number using Collatz Distance). For the given range (51-562), all the possible closest pow2 numbers are: [16, 64, 128, 256, 512, 1024]

Short version

The algorithm performs:

• a binary search to figure out the closest power of 2 to the current number
• a linear search to figure out every previous element in the sequence until the target number is discovered.

Detailed version

Given a game with the target number r, the strategy is the following:

1. Use binary search to figure out the power of 2 that is closest to r in as few steps as possible.
2. If the closest power of 2 that was found is the solution, stop. Otherwise continue to 3.
3. Since the power of 2 that was found is the first power of 2 occurring in the sequence, if follows that that value was reached by doing a (* 3 + 1) operation. (If it came after a /2 operation, then the previous number would also have been a power of 2). Compute the previous number in the sequence by doing the reverse operation (-1 and then /3)
4. If that number is the target, stop. Otherwise continue to 5.
5. Given the current number known from the sequence, it is needed to go back and discover the previous number in the sequence. It is not known whether the current number was arrived at by a (/2) or (*3 +1) operation, so the algorithm tries them both and sees which one yields a number that is closer (as Collatz Distance) from the target.
6. If the newly discovered number is the right one, stop.
7. Using the newly discovered number, go back to step 5.

The results

Running the algorithm for all the numbers in the 51-562 range takes around a second on a normal PC and the total score is 38665.

The code

Try it online!

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}"

Answer 2

worst score: 11, sum score: 3986

All the guesses are in range [51,562].

My algorithm:

1. First time guess 512, and maintain a set of possible results vals, initially the set contains all numbers in range [51,562].

2. At each step, do the following:

   1. Find the value of next guess guess in range [51,562] such that, when the values in vals (excluding guess itself) is partitioned into 3 sets corresponding to the possible outcomes Closer, Same, and Farther, the maximum size of those 3 sets is minimum.
      If there are multiple possible values of guess satisfy the above, choose the smallest.
   2. Guess the value guess.
   3. If the answer is "Right", done (exit the program).
   4. Remove all values in the set vals such that they cannot possibly give that result.

My reference implementation written in C++ and Bash runs in about 7.6 seconds on my machine and give the worst score/sum score as described in the title.

Trying all possible first guess values will take about 1.5 hours on my machine. I may consider doing that.