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

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

Вы можете прочитать Часть I здесь: https://newtonmigosi.medium.com/an-additive-game-part-i-b8a6a2935ae3
И Часть II здесь: https://newtonmigosi.medium.com/ an-add-game-part-ii-2a6a590c3a13

Как и во всех задачах программирования, первое, что нужно сделать, - это определить наши типы данных. В этом упражнении основная структура данных, которую мы используем, называется списком . Это скромная структура данных, как раз и звучит. Экземпляры List - это такие вещи, как: [1,2,3], [4928347.3984, 32987423.423, 389742.23984], [😀, 🥺, 🤙]. По сути, это контейнер, который может содержать любое количество (, возможно, бесконечное) объектов, при условии, что они одного типа.

Наша первая задача - представить колоду карт, которую получает каждый игрок. Мы просто представим их числами от 1 до 13, исключая 12. Мы делаем это, записывая:

deck :: [Int]
deck = 13:[11,10..1]

Синтаксис здесь говорит, что deck - это Список из Int, где Int является сокращением от целого числа, и мы указываем, что список должен быть убывающим. начиная с 13, пропуская 12, затем переходя от 11 к 10 до 1. Наш компьютер достаточно умен, чтобы вычислить весь список, просто задав ему начальную схему.

Контрольный вопрос: как вы думаете, почему мы хотим, чтобы наш список располагался в порядке убывания? Почему это вообще должно быть устроено как-то с самого начала?

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

  • total: число, которое мы хотим, чтобы каждая сторона сумела получить
  • sides: количество сторон нашей сетки должно быть
  • dim: длина каждой стороны

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

Итак, как найти все способы сложить до 23? Или любое число в этом отношении? Хорошее место для начала, когда у вас есть пул чисел для выбора, - просто выбрать первое, затем проверить, не больше ли оно, а затем отложить его в сторону, чтобы сказать, что его можно использовать для суммирования до 23. Затем продолжение на следующее число в пуле и проверяя, дадут ли оно плюс предыдущее в сумме 23. Мы повторяем это до тех пор, пока не убедимся, что набрали достаточно чисел, а в нашем случае это четыре.

Кроме того, мы также можем провести некоторые проверки. Например, предположим, что мы хотим сложить до 23, и для нашей первой карты мы выбрали 13, тогда наш второй выбор был 11. Было бы бессмысленно проверять третью карту, поскольку мы уже знаем, что (13 + 11) больше чем 23.

Кроме того, мы не хотим генерировать все перестановки одного способа сложения до 23. Если мы просто выберем из пула, мы получим и [1,2,7,13], и [7,13,2,1], даже если они практически одно и то же. Простой способ избежать этого - ограничить порядок одного списка, чтобы он был строго убывающим или строго возрастающим. Таким образом, если мы найдем решение, которое нарушает это правило, мы будем знать, что его перестановка уже найдена. Бонусом является то, что у нас также гарантированно не будет дубликатов в нашем списке.

Контрольный вопрос: Можете ли вы придумать больше проверок, которые нужно выполнить при построении способа сложения числа?

С этими условиями мы можем реализовать функцию sumTo, которая будет использовать

  • target: число, которое мы хотим добавить до
  • counter: сколько чисел мы будем использовать, чтобы набрать target
  • pool: числа, из которых нам разрешено выбирать

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

Первая строка нашего цикла объявляет, какая информация нам понадобится внутри нашего цикла. В частности, в нем говорится, что нам нужно будет отслеживать counter, runningTotal и accumulator, в которых мы будем хранить наш результат.

Затем в строке 2 говорится: выберите номер из пула и назовите его current.

В строках с 4 по 6 убедитесь, что наш ответ строго по убыванию, поместив guard, который требует, чтобы current было меньше последнего числа, которое нужно выбрать для формирования нашего ответа.

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

Поскольку previous выбран из списка, есть вероятность, что его не существует! Скажем, например, если наш список пуст, а пустой список представлен как []. Для обработки этого сценария мы используем оператор case, который проверяет значение источника previous, которым в данном случае является accumulator. Стоит отметить, что guard True на самом деле ничего не делает, поэтому мы позволяем выбирать первое число, чтобы решение всегда было успешным.

Строка 8 говорит: убедитесь, что включение current в наш ответ не превышает цель.

Затем в последней строке говорится: повторите строки 2–8, но на этот раз обновите значения так, чтобы counter уменьшилось на 1, current добавляется к runningTotal, а current сохраняется в accumulator, где будет наш окончательный результат.

Если неясно, какое поведение вызовет последняя строка, может быть полезно представить (или даже сделать!) Буквально копирующую вставку строк со 2 по 8 столько раз, сколько мы хотим, чтобы наш цикл выполнялся. Это возможно, поскольку выражение формы x = 5 означает, что всякий раз, когда вы видите букву x, замените ее значением 5 перед продолжением вычислений. В некотором смысле x - не что иное, как синоним 5.

Таким же образом loop является просто синонимом строк со 2 по 10. Поэтому всякий раз, когда мы видим, что используется loop, мы можем скопировать и вставить их, со специальным предупреждением, что мы также должны различать имена, используемые каждой копией loop. Это означает, что поскольку каждая копия loop имеет собственное значение current, нам понадобится способ отличить их друг от друга. Например, позвонив им: current1, current2, current3 и так далее.

В нынешнем виде наш цикл работает вечно, потому что он не знает, когда остановиться. И когда это должно прекратиться? Легко, когда мы выбрали столько чисел, сколько хотели. Мы делаем это, начиная цикл с counter, равным количеству вариантов, которые мы хотим сделать. Затем на каждом шаге цикла мы уменьшаем counter. Таким образом, мы будем знать, что сделали достаточно шагов, когда counter равно 0. Это выглядит так:

Обратите внимание на небольшую разницу между этой первой строкой и первой строкой предыдущего блока. Для этого, вместо того, чтобы разрешать counter принимать какое-либо значение, мы установили его на 0. Если мы последуем нашей аналогии с копированием и вставкой, мы сможем заменить вхождение loop строками 2 и 3 только в том случае, если первое, что следует за этим, loop - это ноль.

Строка 2 говорит, что правильный ответ - это тот, у которого runningTotal в точности равно target. Сравните это с предыдущим блоком кода, где мы были удовлетворены, пока runningTotal было не более равным target. В последней строке говорится, что, поскольку мы выполнили все наши требования, все, что указано в accumulator, должно быть правильным ответом.

После завершения цикла мы можем определить sumTo как результат инициализации цикла следующим образом: loop dim 0 []. Таким образом, мы устанавливаем counter, чтобы иметь значение dim, runningTotal, чтобы иметь начальное значение 0 и accumulator, начиная с пустого списка, поскольку наш результат должен быть списком чисел в сумме до target.

И с этим у нас есть функция sumTo, которая предоставит нам все способы сложить до 23. Все, что осталось сейчас, это определить solutions, который затем будет выбирать из этого списка в соответствии с нашими правилами. К счастью, как я упоминал в начале этой статьи, он следует той же схеме, что и sumTo. Настолько, что было бы излишним писать это здесь.

Заинтересованный читатель должен попробовать. Но вкратце о том, что мы сделали:

  • Создайте loop, который на каждом шаге будет выбирать значение из pool. (Подсказка: pool для solutions на самом деле просто результат sumTo)
  • Поместите guard в это значение в соответствии с ограничениями задачи. (Подсказка: мы обсуждали наши ограничения в предыдущей статье)
  • Повторяйте эти шаги, пока не достигнете условия выхода. (Подсказка: для solutions условие выхода - это найти ровно четыре способа сложить до 23, которые соответствуют правилам)
  • Если да, выйдите из цикла и return значение. (Подсказка: не забудьте поместить самый сильный guard перед возвратом результата. Используйте более слабые guard, пока вы получаете ответ внутри основного цикла)

Для полноты, вот полная реализация sumTo:

Мою реализацию solutions также можно найти по этой ссылке: https://gist.github.com/newton-migosi/cfefc1a4af35edf401e126bc79ff790d

Приветствую вас за то, что вы дошли до этого момента. Я надеюсь, что эта серия была для вас полезна. На этом я прощаюсь с вами. До следующего раза!