Как рассчитать все возможные пути на сетке

Question

Я недавно видел картинку с вызовом в Instagram-аккаунте brillant.org:

Инструкции: робот делает 4 случайных шага (может 't go диагональ).

В каком районе он с наибольшей вероятностью приземлится?

Очевидно, есть 4 ⁴ = 256 возможных путей для робота. Я пытался написать программу (Javascript) для решения этой проблемы, но мои подходы не сработали. На самом деле у меня нет полезного кода для показа здесь, потому что я застрял довольно рано.

Поэтому мой вопрос: как бы вы написали программу, которая:

1. Проверяет все 256 возможных путей и

2. Сообщает мне, сколько (%) приземлилось в какой области

Answer 1

Это очень крутой вопрос! И спасибо, что позволили мне открыть Instagram-аккаунт brillant.org. Итак, я бы поступил следующим образом:

1. Напишите функцию для вычисления всех возможных перестановок с повторением (n ^ k)
2. Создайте карту, где выполнить все возможные ходы, рассчитанные в шаг 1
3. Проверьте область, на которой робот приземлится, на последнем шаге и сохраните его
4. Рассчитайте процент на основе подсчета на шаге 3

Первый шаг - это проблема сама по себе, и она не является частью этой области. Вы можете использовать или адаптировать код здесь: https://rosettacode.org/wiki/Permutations_with_repetitions

Затем, чтобы сгенерировать карту, я просто использовал массив:

const map = [
  0, 0, 0, 0, 1, 0, 0, 0, 0,
  0, 0, 0, 1, 1, 1, 0, 0, 0,
  0, 0, 1, 1, 2, 1, 1, 0, 0,
  0, 1, 1, 2, 2, 2, 1, 1, 0,
  1, 1, 3, 3, 2, 3, 3, 1, 1,
  0, 1, 1, 3, 3, 3, 1, 1, 0,
  0, 0, 1, 1, 3, 1, 1, 0, 0,
  0, 0, 0, 1, 1, 1, 0, 0, 0,
  0, 0, 0, 0, 1, 0, 0, 0, 0,
];

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

На этом этапе я определил массив из 4 возможных ходов:

const moves = [
  -1,  // left 
   1,  // right,
  -9,  // top
   9,  // bottom
];

Значения указывают на смещение, необходимое для перемещения в направлении, указанном в комментарии: я думаю, левый и правый говорят сами за себя. Для верха и низа, поскольку мы используем массив в качестве «матрицы», нам, в основном, нужно преобразовать значение y в значение индекса в массиве. Формула проста: index = x + y * width, поэтому это означает, что если вы хотите указать y для перемещения up на одну ячейку, у вас есть -1 * 9, а для перемещения down - это 1 * 9.

По той же причине начальная позиция робота (в центре карты) рассчитывается следующим образом: 4 + 4 * 9.

Теперь я вычисляю все возможные комбинации ходов с функцией перестановки:

const allmoves = permutationsWithRepetition(4, moves);

И создать массив для хранения результатов:

let results = [0, 0, 0, 0];

После этого я просто перебираю все возможные массивы ходов и вычисляю позицию в конце ходов:

for (let j = 0; j < allmoves.length; j++) {
  // set the robot's initial position at the center
  // before executing any moves' list
  let pos = 4 + 4 * 9;

  // calculate the new position using the current moves
  for (let i = 0; i < moves.length; i++) {
    let move = allmoves[j][i];
    pos += move;
  }

  // now `map[pos]` points to a number between 1 and 3
  // that identify the area where the robot is.
  // we use that number as index of the results
  // to increment its value.
  // Notice that it's impossible land to any 0 area
  // if we start from the center and we can only perform
  // 4 moves.
  // We use that number as `index` for our `results`
  results[map[pos]]++;
}

Теперь в results вы будете знать, сколько раз робот оказывался в какой области:

console.log(results); // [0, 60, 100, 96]

Как уже упоминалось, это невозможно, учитывая начальную позицию и количество ходов, которые робот может выполнить. земля в любой области 0, поэтому первый индекс будет иметь значение 0. Вы можете видеть, что он приземлился в области 1 (оранжевая) 60 раз, в области 2 100 раз (самая маленькая область, зеленая / зеленая) и в области 3 96 раз (синий / фиолетовый). ).

На данный момент вы можете рассчитать процент (times / total * 100) и отобразить его с правильным форматированием:

// we skip the first element of results since
// it's not an area (and we'll be always 0)
for (let k = 1; k < results.length; k++) {
  console.log(k, `${(results[k] /  allmoves.length * 100).toFixed(2)}%`)
}

И вы получите:

1 "23.44%"
2 "39.06%"
3 "37.50%"

Вы также можете сделать проверку empiri c, и фактически генерировать десять тысяч ходов случайным образом, и заставить программу применять их вместо allmoves, и вы увидите, что вы всегда заканчиваете одинаковым числом (очевидно, но это также забавная часть математики, убедитесь, что это именно то, что вы ожидаете!).

Вот рабочий код, который также реализует код перестановки , упомянутый в начале, из rosettacode. org, и код, объясненный в этом посте: https://codepen.io/zer0/pen/RwWPZmE

(Вам нужно открыть консоль, чтобы увидеть результаты)

Answer 2

Я бы создал различные объекты, представляющие различные возможности, как показано ниже:

function Path(x, y, movesLeft) {

    this.x = x;
    this.y = y;
    this.movesLeft = movesLeft;

    this.paths = [];
    if (movesLeft > 0) {
        this.paths.push(new Path(x - 1, y, movesLeft - 1));
        this.paths.push(new Path(x + 1, y, movesLeft - 1));
        this.paths.push(new Path(x, y - 1, movesLeft - 1));
        this.paths.push(new Path(x, y + 1, movesLeft - 1));
    }

    this.getArray = function() {
        if (this.movesLeft > 0) {
            var output = [];
            for (var i = 0; i < this.paths.length; i++) {
                output = output.concat(this.paths[i].getArray());
            }
            return output;
        }
        return [this];
    }

}

Теперь вы можете создать объект и проверить результаты:

var endPosArray = new Path(0, 0, 4).getArray();

Все, что вам нужно сделать l oop через массив и рассчитать шансы.