Inspiré par The Great API Easter Egg Hunt!

Résumé

Votre tâche consiste à rechercher un entier prédéterminé dans "l'espace Collatz" (pour être expliqué plus loin) en utilisant le moins d'étape possible.

introduction

Ce défi est basé sur la célèbre conjecture de Collatz dont tout le monde ici, espérons-le, a au moins entendu parler. Voici un récapitulatif tiré de Imprimer les numéros Super Collatz .

La séquence Collatz (également appelée problème 3x + 1) est l'endroit où vous commencez avec n'importe quel entier positif, pour cet exemple, nous utiliserons 10, et lui appliquerons cet ensemble d'étapes:

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

La distance Collatz C(m,n)entre les deux nombres met n, aux fins de ce défi, est la distance entre deux nombres dans le graphique Collatz (Crédits à @tsh pour me parler de ce concept), qui est défini comme suit: (en utilisant 21et 13comme exemples ):

Notez la séquence Collatz pour m(dans ce cas, 21):

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

Notez la séquence Collatz pour n(dans ce cas, 13):

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

Comptez maintenant le nombre de chiffres qui n'apparaissent que dans l'une des séquences. Ceci est défini comme la distance Collatz entre met n. Dans ce cas 8, à savoir,

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

Nous avons donc la distance Collatz entre 21et 13as C(21,13)=8.

C(m,n) ont les belles propriétés suivantes:

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

Espérons que la définition de C(m,n)est maintenant claire. Commençons à chasser les œufs dans l'espace Collatz!

Au début du jeu, un contrôleur décide de la position d'un œuf de Pâques, qui s'exprime par sa coordonnée unidimensionnelle: Un entier dans l'intervalle [p,q](en d'autres termes, un entier entre pet q, les deux extrémités inclus).

La position de l'œuf reste constante tout au long du jeu. Nous désignerons cette coordonnée comme r.

Vous pouvez maintenant faire une estimation initiale de ₀ et il sera enregistré par le contrôleur. Ceci est votre 0e round. Si vous êtes si chanceux que vous l'avez bien fait au début (c.-à-d. Un ₀ = r), le jeu se termine et votre score est 0(Plus le score est bas, mieux c'est). Sinon, vous entrez dans le 1er tour et vous faites une nouvelle estimation de ₁ , cela continue jusqu'à ce que vous ayez bien compris, c'est-à-dire a _n = r, et votre score sera n.

Pour chaque manche après le 0, le contrôleur vous donne l'une des rétroactions suivantes afin que vous puissiez faire une meilleure estimation en fonction des informations fournies. Supposons que vous êtes actuellement au ntroisième tour et donc votre supposition est un _n

• "Tu l'as trouvé!" si a _n = r, auquel cas le jeu se termine et vous marquez n.
• "Vous êtes plus proche :)" si C (a _n , r) <C (a _n-1 , r)
• "Vous tournez autour de l'œuf" si C (a _n , r) = C (a _n-1 , r)
• "Vous êtes plus loin :(" si C (a _n , r)> C (a _n-1 , r)

Pour économiser quelques octets, j'appellerai les réponses "Droite", "Plus proche", "Même", "Plus loin", dans l'ordre présenté ci-dessus.

Voici un exemple de jeu avec p=1,q=15.

• a ₀ = 10
• a ₁ = 11, réponse: "Closer"
• a ₂ = 13, réponse: "Plus loin"
• a ₃ = 4, réponse: "Plus loin"
• a ₄ = 3, réponse: "Closer"
• a ₅ = 5, réponse: "Identique"
• a ₆ = 7, réponse: "Droite"

Note: 6.

Défi

Concevez une stratégie déterministe pour jouer au jeu p=51, q=562avec le meilleur score.

Les réponses doivent décrire les algorithmes en détail. Vous pouvez attacher n'importe quel code qui aide à élucider l'algorithme. Ce n'est pas du codegolf, vous êtes donc encouragé à écrire du code lisible.

Les réponses doivent inclure le pire score qu'ils peuvent obtenir pour tous les cas possibles ret celui avec le score le plus faible l'emporte. En cas d'égalité, les algorithmes qui ont un meilleur score moyen pour tous les rs possibles (qui devraient également être inclus dans les réponses) l'emportent. Il n'y a plus de bris d'égalité et nous pouvons avoir plusieurs gagnants à la fin.

Spécifications

• Pour réitérer, rréside dans l'intervalle [51,562].
• Les failles par défaut s'appliquent.

Bounty (ajouté après la publication de la première réponse)

Je peux personnellement offrir une prime à une réponse où toutes les suppositions sont faites dans la plage [51,562]tout en ayant un pire score raisonnablement bas.

Rubis, 196

C'était beaucoup plus difficile que je pensais au départ. J'ai dû gérer beaucoup de cas obscurs et je me suis retrouvé avec beaucoup de code laid. Mais c'était très amusant! :)

Stratégie

Chaque séquence Collatz se termine par une séquence de pouvoirs de 2 (ex: [16, 8, 4, 2, 1]). Dès qu'une puissance de 2 est rencontrée, nous divisons par 2 jusqu'à ce que nous atteignions 1. Appelons la première puissance de 2 dans une séquence pow2 la plus proche (car c'est aussi la puissance la plus proche de 2 à notre nombre en utilisant Collatz Distance). Pour la plage donnée (51-562), tous les nombres pow2 les plus proches possibles sont: [16, 64, 128, 256, 512, 1024]

Version courte

L'algorithme effectue:

• une recherche binaire pour déterminer la puissance la plus proche de 2 au nombre actuel
• une recherche linéaire pour comprendre chaque élément précédent de la séquence jusqu'à ce que le nombre cible soit découvert.

Version détaillée

Étant donné un jeu avec le nombre cible r, la stratégie est la suivante:

1. Utilisez la recherche binaire pour déterminer la puissance de 2 la plus proche ren un minimum d'étapes.
2. Si la puissance la plus proche de 2 trouvée est la solution, arrêtez. Sinon, passez à 3.
3. Puisque la puissance de 2 qui a été trouvée est la première puissance de 2 apparaissant dans la séquence, il s'ensuit que cette valeur a été atteinte en effectuant une opération (* 3 + 1). (S'il venait après une opération / 2, alors le nombre précédent aurait également été une puissance de 2). Calculez le nombre précédent dans la séquence en effectuant l'opération inverse (-1 puis / 3)
4. Si ce nombre est la cible, arrêtez. Sinon, passez à 5.
5. Étant donné le nombre actuel connu de la séquence, il est nécessaire de revenir en arrière et de découvrir le numéro précédent de la séquence. On ne sait pas si le nombre actuel a été atteint par une opération (/ 2) ou (* 3 +1), donc l'algorithme les essaie tous les deux et voit lequel donne un nombre qui est plus proche (comme Collatz Distance) de la cible .
6. Si le nouveau numéro découvert est le bon, arrêtez.
7. En utilisant le numéro nouvellement découvert, revenez à l'étape 5.

Les resultats

L'exécution de l'algorithme pour tous les nombres compris entre 51 et 562 prend environ une seconde sur un PC normal et le score total est de 38665.

Le code

Essayez-le en ligne!

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

pire score: 11, score total: 3986

Toutes les suppositions sont à portée [51,562].

Mon algorithme:

1. Pour la première fois, devinez 512 et conservez un ensemble de résultats possibles vals. Initialement, l'ensemble contient tous les nombres dans la plage [51,562].

2. À chaque étape, procédez comme suit:

   1. Trouver la valeur de conjecture suivante guessdans la gamme de [51,562]telle sorte que, lorsque les valeurs vals(sauf guesslui - même) est divisé en 3 séries correspondant aux résultats possibles Closer, Sameet Farther, la taille maximale de ces 3 ensembles est minimum.
      S'il existe plusieurs valeurs possibles pour guesssatisfaire ce qui précède, choisissez la plus petite.
   2. Devinez la valeur guess.
   3. Si la réponse est "Droite", c'est fait (quittez le programme).
   4. Supprimez toutes les valeurs de l'ensemble de valssorte qu'elles ne puissent pas donner ce résultat.

Mon implémentation de référence écrite en C ++ et Bash s'exécute en environ 7,6 secondes sur ma machine et donne le pire score / score de somme comme décrit dans le titre.

Essayer toutes les valeurs de première estimation possibles prendra environ 1,5 heure sur ma machine. Je peux envisager de le faire.