Peg Game: лучшее место для размещения мяча таким образом, чтобы он попадал в целевую клетку

Question

Источник: Facebook Hacker Cup Квалификационный раунд 2011

В аркаде вы можете сыграть в простую игру, где мяч попадает в верхнюю часть игры.с позиции по вашему выбору.Есть несколько колышков, от которых будет отскакивать мяч, когда он падает в игре.Всякий раз, когда мяч попадает в колышек, он отскакивает влево с вероятностью 0,5 и вправо с вероятностью 0,5.Единственным исключением является случай, когда он ударяет колышком в крайнюю левую или правую сторону, и в этом случае он всегда отскакивает к середине.

Когда игра была сделана впервые, колышки были расположены в регулярной сетке,Тем не менее, это старая игра, и теперь некоторые колышки отсутствуют.Ваша цель в игре - заставить мяч выпасть из нижней части игры в определенном месте.Учитывая расположение игры, как мы можем определить оптимальное место для падения мяча, чтобы вероятность его попадания в это конкретное место была максимально увеличена?

На рисунке ниже показан пример игры с пятьюряды из пяти столбцов.Обратите внимание, что в верхнем ряду пять колышков, в следующем ряду четыре колышка, следующие пять и т. Д.С пятью столбцами, есть четыре варианта, в которые нужно бросить мяч (проиндексировано от 0).Обратите внимание, что в этом примере отсутствуют три колышка.Верхняя строка - это строка 0, а самый левый колышек - это столбец 0, поэтому координаты отсутствующих колышков - (1,1), (2,1) и (3,2).В этом примере лучшее место для падения мяча - крайний левый столбец 0, что дает 50% -ную вероятность того, что он закончится в воротах.

x.x.x.x.x
 x...x.x
x...x.x.x
 x.x...x
x.x.x.x.x
 G

x указывает на колышек, . обозначает пустое место.

Answer 1

Начните снизу и назначьте вероятность 1 для цели и 0 для других слотов.Затем для следующего ряда вверх назначьте вероятности следующим образом:

1) if there is no peg, use the probability directly below.
2) for a peg, use the average of the probabilities in the adjacent columns one row down.

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

Answer 2

Мы можем решить эту проблему, используя теорию вероятностей. Мы опускаем шар в позицию и рекурсивно разделяем траекторию мяча в одном (на боковой стенке) или двух возможных направлениях. На первом шаге мы с вероятностью 1 узнаем положение мяча (в конце концов, мы его опускаем!). При каждом последующем разделении на два направления вероятность уменьшается вдвое. Если мы окажемся в нижней строке целевого местоположения, мы добавим вероятность пройденного пути к нашему итогу. Повторите этот процесс для всех стартовых позиций и возьмите наибольшую вероятность достижения цели.

Мы можем улучшить этот алгоритм, удалив рекурсию и построчную обработку с помощью динамического программирования. Начните с первой строки, установленной на все 0, кроме начальной позиции, которую мы установили на 1. Затем вычислим вероятности достижения каждой ячейки в следующей строке, начиная с массива 0 и. Для каждой ячейки в нашей текущей строке добавьте половину ее вероятности к ячейке слева от нее в следующей строке и половину справа от нее, если только она не относится к боковой стенке, и в этом случае мы добавляем полную вероятность к отдельной ячейке. Продолжайте делать это для каждого ряда, пока не достигнете последнего ряда.

Пока мы пренебрегли отсутствующими колышками. Мы можем принять их во внимание, имея три вероятности для каждой ячейки: по одной для каждого направления, в котором движется мяч. В итоге мы подводим итоги, так как направление не имеет значения.

Answer 3

O(R*C) решение

dp[i][j] дает вероятность того, что мяч достигнет прорези ворот, если он в данный момент находится в ряду i и в прорези j.

Базовый случай имеет dp[R-1][goal] = 1.0 и все другие слоты в строке R-1 до 0,0

Повторение тогда составляет

dp[i][j] = dp[i + 2][j] if the peg below is missing 
dp[i][j] = dp[i + 1][left] if the peg is on the right wall 
dp[i][j] = dp[i + 1][right] if the peg is on the left wall 
dp[i][j] = (dp[i + 1][left] + dp[i + 1][right]) / 2 otherwise 

Answer 4

Наблюдения:

1. Для данной исходной позиции в каждой строке имеется распределение вероятностей
2. От одной полной строки к следующей,Распределение будет просто размытым, за исключением краев.
3. Там, где есть отверстия, мы увидим предсказуемое отклонение от размытия в (2)
4. Мы могли бы выделить эти отклонения, так как шары выпадают по одному за раз, поэтому вероятности подчиняютсяпринцип суперпозиции (квантовые компьютеры были бы идеальными здесь).
5. Разделяя отклонения, мы можем видеть, что действительно существует множество отверстий, наложенных на сетку колышков, поэтому мы можем вычислить распределение по полномусначала установите набор колышков (легко), а затем просмотрите колышки по отдельности, чтобы увидеть их эффект - это предполагает, что колышков больше, чем отверстий!
6. Ребро действительно является зеркалом - мы можем рассчитать для бесконечного множестваэти зеркальные виртуальные доски вместо того, чтобы использовать условия условия для границ.

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

В идеале я бы начал с полного (fibonacci) дерева, и для каждого отсутствующего колышка в строке добавьтев результате их пропажи.

Answer 5

Этот вопрос был в Facebook Hacker Cup 2011.

Решение Marcog кажется правильным, но я решил немного по-другому.Я решил так:

1. Настройка платы: чтение ввода, настройка платы NxM, считывание недостающих колышков и вставка отверстий в плату.

2. Для каждого возможного начального отверстия, выполните BFS следующим образом:

   • Дроп-дыра имеет начальную вероятность 1,0.
   • Из текущего состояния вы можете перейти вниз, влево, вправо, влево и вправо.
   • Если вы можете только идти вниз, влево или вправо, суммируйте текущую вероятность состояния и добавьте ее в очередь, если ее еще нет в очереди.Например: если вы находитесь в точке (1, 2) с вероятностью 0,5 и можете только понизиться, то суммируйте 0,5 до состояния (2,2) и добавьте его в очередь, если его еще нет в очереди.
   • Если вы можете идти влево и вправо, суммируйте половину вероятности текущего состояния для каждого возможного следующего состояния и добавляйте их в очередь, если их там еще нет.Например: если вы находитесь в точке (3, 3) с вероятностью 0,5 и можете идти влево и вправо, добавьте 0,25 к (4, 2) и 0,25 к (4, 4) и их в очередь, если их еще нет,
3. Обновление текущего лучшего
4. Печать глобального лучшего.

Мое решение (не самый чистый код) в cpp можно загрузить с: https://github.com/piva/Programming-Challenges/blob/master/peggame.cpp

Надеюсь, это помогло ...