Рассмотрим следующее «волшебное» трехугольное кольцо, заполненное числами от 1 до 6, и каждая строка добавляет до девяти.

Работая по часовой стрелке и начиная с группы из трех с наименьшим числовым внешним узлом (4,3,2 в этом примере), каждое решение можно описать уникальным образом. Например, приведенное выше решение можно описать набором: 4,3,2; 6,2,1; 5,1,3.

Можно завершить кольцо с четырьмя различными суммами: 9, 10, 11 и 12. Всего есть восемь решений.

Объединив каждую группу, можно сформировать строки из 9 цифр; максимальная строка для трехугольного кольца равна 432621513.

Используя числа от 1 до 10 и в зависимости от расстановки, можно сформировать строки из 16 и 17 цифр. Какова максимальная 16-значная строка для «волшебного» пятиугольного кольца?

Решение

(см. полное решение здесь)

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

Чтобы построить магический круг, будь то 3-х или 5-ти угольное кольцо, мы можем разбить числа на пары — например. А =› [1; 2], Б =› [3; 4], С =› [5; 6], Д =› [7; 8], Э =› [9; 10] — и проблема состоит в том, чтобы найти способы перестановки чисел таким образом, чтобы:

  1. a0 является наименьшим среди a0, b0, c0, d0 и e0
  2. суммы a0 + a1 + b1, b0 + b1 + c1, … одинаковы

Например:

Во-первых, мы найдем различные способы перестановки чисел от 1 до 10, и для каждой перестановки разобьем числа на пары:

(при этом используется функция permute, определенная в исходном файле Common.fs в решении).

Затем нам нужна функция для суммирования пары чисел с последним элементом в соседней паре — например. а0 + а1 + b1:

Для каждой перестановки нам нужно проверить:

  1. если a0 наименьший среди головных элементов
  2. если суммы групп из 3 — т. е. a0 + a1 + b1, b0 + b1 + c1 и т. д. — одинаковы

Эта предикатная функция позволяет нам находить схемы, соответствующие нашим критериям. Осталось только преобразовать группы из 15 чисел в строки из 16/17 цифр и найти максимум (см. полное решение ниже).

Вот полное решение:

Для выполнения этого решения на моей машине потребовалось 26 секунд.