Zainspirowany The Great API Easter Egg Hunt!

streszczenie

Twoim zadaniem jest poszukiwanie z góry określonej liczby całkowitej w „przestrzeni Collatz” (wyjaśnione później) przy użyciu jak najmniejszej liczby kroków.

Wprowadzenie

Wyzwanie to opiera się na słynnej hipotezie Collatz, o której, przynajmniej mam nadzieję, wszyscy tu słyszeli. Oto podsumowanie zaczerpnięte z Print the Super Collatz numbers .

Collatz Sequence (zwany również problem 3x + 1) jest tam, gdzie zaczynają się każdej liczby całkowitej dodatniej, w tym przykładzie użyjemy 10, i zastosować zestaw kroków do niego:

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

Odległość Collatz C(m,n)między dwiema liczbami mi n, na potrzeby tego wyzwania, jest odległością między dwiema liczbami na wykresie Collatz (Podziękowania dla @tsh za poinformowanie mnie o tej koncepcji), która jest zdefiniowana następująco: (za pomocą 21i 13jako przykłady ):

Zapisz sekwencję Collatz dla m(w tym przypadku 21):

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

Zapisz sekwencję Collatz dla n(w tym przypadku 13):

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

Teraz policz, ile liczb pojawia się tylko w jednej sekwencji. Jest to zdefiniowane jako odległość Collatz między mi n. W tym przypadku 8, a mianowicie

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

Mamy więc odległość Collatz między 21i 13jak C(21,13)=8.

C(m,n) mają następujące miłe właściwości:

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

Mam nadzieję, że definicja C(m,n)jest teraz jasna. Zacznijmy polować na jajka w przestrzeni Collatz!

Na początku gry kontroler decyduje o położeniu jajka wielkanocnego, które wyraża się w jego jednowymiarowej współrzędnej: Liczba całkowita w przedziale [p,q](innymi słowy liczba całkowita między pi q, włącznie z obydwoma końcami).

Pozycja jajka pozostaje stała podczas gry. Będziemy oznaczać tę współrzędną jako r.

Możesz teraz początkowo zgadnąć ₀ , a to zostanie zarejestrowane przez kontroler. To twoja 0 runda. Jeśli masz tyle szczęścia, że ​​udało Ci się to zrobić na pierwszym miejscu (tj. ₀ = r), gra się kończy, a twój wynik to 0(Im niższy wynik, tym lepiej). W przeciwnym razie wchodzisz do pierwszej rundy i zgadujesz ₁ , to trwa do momentu, aż wszystko będzie dobrze, tj. _N = r, a twój wynik będzie n.

Dla każdej rundy po 0 kontroler podaje jedną z następujących informacji zwrotnych, dzięki czemu można lepiej zgadywać na podstawie podanych informacji. Załóżmy, że aktualnie jesteś w ntrzeciej rundzie, więc zgadujesz, że to _n

• "Znalazłeś to!" jeśli a _n = r, w takim przypadku gra się kończy i zdobywasz punkty n.
• „Jesteś bliżej :)” jeśli C (a _n , r) <C (a _n-1 , r)
• „Krążysz wokół jajka”, jeśli C (a _n , r) = C (a _n-1 , r)
• „Jesteś dalej :(” jeśli C (a _n , r)> C (a _n-1 , r)

Aby zapisać niektóre bajty, wywołam odpowiedzi jako „w prawo”, „bliżej”, „sam”, „dalej”, w kolejności przedstawionej powyżej.

Oto przykładowa gra z p=1,q=15.

• ₀ = 10
• ₁ = 11, odpowiedź „bliżej”
• ₂ = 13, odpowiedź: "dalej"
• ₃ = 4, reakcji: "dalej"
• ₄ = 3, reakcji „bliżej”
• ₅ = 5, odpowiedź: "to samo"
• ₆ = 7, odpowiedź: "W prawo"

Wynik: 6.

Wyzwanie

Zaprojektuj deterministyczną strategię gry p=51, q=562z najlepszym wynikiem.

Odpowiedzi powinny szczegółowo opisywać algorytmy. Możesz dołączyć dowolny kod, który pomoże wyjaśnić algorytm. To nie jest kodegolf, więc zachęcamy do napisania czytelnego kodu.

Odpowiedzi powinny zawierać najgorszy wynik, jaki mogą osiągnąć we wszystkich możliwych przypadkach r, a ten z najniższym wynikiem najgorszym wygrywa. W przypadku remisu wygrywają algorytmy, które mają lepszy średni wynik dla wszystkich możliwych rs (co powinno być również zawarte w odpowiedziach). Nie ma już żadnych przerywników remisów i na końcu możemy mieć wielu zwycięzców.

Okular

• Powtarzam, rleży w przedziale [51,562].
• Obowiązują domyślne luki .

Nagroda (dodana po opublikowaniu pierwszej odpowiedzi)

Mogę osobiście zaoferować nagrodę za odpowiedź, w której wszystkie domysły są w zasięgu, [51,562]ale wciąż mają stosunkowo niski wynik najgorszy.

Ruby, 196

To było o wiele trudniejsze, niż początkowo myślałem. Musiałem poradzić sobie z wieloma niejasnymi sprawami i skończyło się to brzydkim kodem. Ale było dużo zabawy! :)

Strategia

Każda sekwencja Collatz kończy się sekwencją potęg 2 (np .: [16, 8, 4, 2, 1]). Gdy tylko napotkamy potęgę 2, dzielimy przez 2, aż osiągniemy 1. Nazwijmy pierwszą potęgę 2 w sekwencji najbliższej pow2 (ponieważ jest to również najbliższa potęga 2 do naszej liczby za pomocą Collatz Distance). Dla danego zakresu (51-562) wszystkie możliwe najbliższe liczby pow2 to: [16, 64, 128, 256, 512, 1024]

Krótka wersja

Algorytm wykonuje:

• wyszukiwanie binarne w celu ustalenia najbliższej potęgi 2 do bieżącej liczby
• liniowe wyszukiwanie, aby ustalić każdy poprzedni element w sekwencji, dopóki nie zostanie wykryta liczba docelowa.

Szczegółowa wersja

Biorąc pod uwagę grę z numerem docelowym r, strategia jest następująca:

1. Użyj wyszukiwania binarnego, aby obliczyć potęgę 2, która jest najbliższa, rw jak najmniejszej liczbie kroków.
2. Jeśli najbliższą znalezioną siłą 2 jest rozwiązanie, zatrzymaj się. W przeciwnym razie przejdź do 3.
3. Ponieważ znaleziona moc 2 jest pierwszą potęgą 2 występującą w sekwencji, jeśli wynika z tego, że wartość ta została osiągnięta poprzez wykonanie operacji (* 3 + 1). (Gdyby przyszedł po operacji / 2, to poprzednia liczba byłaby również potęgą 2). Oblicz poprzedni numer w sekwencji, wykonując operację odwrotną (-1, a następnie / 3)
4. Jeśli ta liczba jest celem, przestań. W przeciwnym razie przejdź do 5.
5. Biorąc pod uwagę bieżącą liczbę znaną z sekwencji, należy cofnąć się i odkryć poprzedni numer w sekwencji. Nie wiadomo, czy bieżąca liczba została uzyskana przez operację (/ 2) czy (* 3 +1), więc algorytm wypróbowuje je obie i widzi, która z nich daje liczbę bliższą (jako odległość Collatza) od celu .
6. Jeśli nowo odkryty numer jest właściwy, przestań.
7. Korzystając z nowo odkrytego numeru, wróć do kroku 5.

Wyniki

Uruchomienie algorytmu dla wszystkich liczb z zakresu 51-562 zajmuje około sekundy na normalnym komputerze, a łączny wynik to 38665.

Kod

Wypróbuj 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}"

najgorszy wynik: 11, łączny wynik: 3986

Wszystkie domysły są w zasięgu [51,562] .

Mój algorytm:

1. Po raz pierwszy zgadnij 512 i zachowaj zestaw możliwych wyników vals, początkowo zestaw zawiera wszystkie liczby w zakresie[51,562] .

2. Na każdym kroku wykonaj następujące czynności:

   1. Znaleźć wartość następnego odgadnięcia guessw zakresie [51,562]takim, że gdy wartości w vals(bez guesssiebie) dzieli się 3 zestawy odpowiadające możliwych efektów Closer, Samei Fartherwielkość maksymalną z tych 3 zestawów jest minimalna.
      Jeśli istnieje wiele możliwych wartości guessspełniających powyższe kryteria, wybierz najmniejszą.
   2. Odgadnij wartość guess.
   3. Jeśli odpowiedź brzmi „Dobrze”, gotowe (zamknij program).
   4. Usuń wszystkie wartości z zestawu vals, aby nie mogły dać tego wyniku.

Moja referencyjna implementacja napisana w C ++ i Bash działa na moim komputerze w około 7,6 sekundy i daje najgorszy wynik / sumę punktów, jak opisano w tytule.

Wypróbowanie wszystkich możliwych wartości domyślnych zajmie na moim komputerze około 1,5 godziny. Mogę to rozważyć.