Уравнение года - 2022

В уравнении года - 2019 я использовал выражения без скобок и тот факт, что в системе счисления с основанием n очередное размещение с повторениями по k элементов из n соответствует очередному по порядку числу.

Намного ли усложняется задача, если разрешить в записи выражения ещё и круглые скобки? Вообще говоря, да. Несмотря на то, что само уравнение со скобками для чисел [10, 9, ..., 1] я нашёл:

10+(((9*8*7)-6+5)*(4+3-2-1)) = 2022

, хорошо бы ещё формализовать поиск.

С одной стороны, казалось бы, делов-то - написал скрипт, расставлющий всеми возможными способами пары скобок и четыре арифметических операции между числами (вот он):

<?php
 set_time_limit (0);

 function translate ($postfix) {
  $operators = ['+','-','/','*'];
  $expr = new SplStack();
  $sc = explode (' ',$postfix);
  for ($i = 0; $i < count($sc); $i++) {
   $t = $sc[$i];
   if (!in_array($t,$operators)) $expr->push($t);
   else $expr->push('('.$expr->pop().$t.$expr->pop().')');
  }
  return $expr->pop();
 }

 function brute($numbers, $stackHeight, $eq) {
  $operators = ['+','-','/','*'];
  if ($stackHeight >= 2) {
   foreach ($operators as $op) brute ($numbers, $stackHeight - 1, $eq . ' ' . $op);
  }
  $allUsedUp = true;
  for ($i = 0; $i < count($numbers); $i++) {
   if (isset($numbers[$i])) {
    $allUsedUp = false;
    $n = $numbers[$i];
    unset($numbers[$i]);
    brute ($numbers, $stackHeight + 1, $eq . ' ' . $n);  
    $numbers[$i] = $n;
   }
  }
  if ($allUsedUp and $stackHeight == 1) echo translate($eq).'<br>';
 }
 function expr ($numbers) {
  brute ($numbers, 0, '');
 }
 expr ([1,2,3,4]);
?>

- брутфорсом получаем нужные строки в RPN, методом translate добавляем скобки, выводим в браузер, (операнды-числа местами не переставляются), сбрасываем вывод скрипта в файл, например, с именем 2022.txt в текущей папке, и оцениваем себе выражения другим маленьким скриптом (кстати, там есть перехват деления на 0 для функции eval):

<?php
 set_time_limit (0);
 $file = file ('2022.txt') or die ('Read error!');
 foreach ($file as $line) {
  try {
   $res = eval('return '.$line.';');
  }
  catch (DivisionByZeroError $err) {
   $res = 'Div by 0';
  }
  echo $line.'='.$res.'<br>';
 }
?>

Увы, проблемы, как всегда, в размерностях. В общем случае, если у нас есть n+1 операнд и мы должны вставить n операторов, выбранных из k возможных, то имеем что-то вроде (оценка навскидку) (2n)! / n! * kn возможных выражений, и уже на шести элементах массива генерация формул будет работать довольно долго (более 170 тысяч вариантов) а на десяти числах просто рухнет вкладка.

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

Соответственно, два скрипта я просто соединил в один и добавил цикл:

<?php
 set_time_limit (0);

 function translate ($postfix) {
  $operators = ['+','-','/','*'];
  $expr = new SplStack();
  $sc = explode (' ',$postfix);
  for ($i = 0; $i < count($sc); $i++) {
   $t = $sc[$i];
   if (!in_array($t,$operators)) $expr->push($t);
   else $expr->push('('.$expr->pop().$t.$expr->pop().')');
  }
  return $expr->pop();
 }

 function brute($numbers, $stackHeight, $eq) {
  $operators = ['+','-','/','*'];
  if ($stackHeight >= 2) {
   foreach ($operators as $op) brute ($numbers, $stackHeight - 1, $eq . ' ' . $op);
  }
  $allUsedUp = true;
  for ($i = 0; $i < count($numbers); $i++) {
   if (isset($numbers[$i])) {
    $allUsedUp = false;
    $n = $numbers[$i];
    unset($numbers[$i]);
    brute ($numbers, $stackHeight + 1, $eq . ' ' . $n);  
    $numbers[$i] = $n;
   }
  }
  if ($allUsedUp and $stackHeight == 1) {
   $line = translate($eq);
   try {
    $res = eval('return '.$line.';');
   }
   catch (DivisionByZeroError $err) {
    $res = 'Div by 0';
   }
   if ($res == 2022) echo $line.'='.$res.'<br>';
  }
 }
 function expr ($numbers) {
  brute ($numbers, 0, '');
 }

 for ($n = 1; $n<100001; $n++) {
  $arr = [$n, $n + 1, $n + 2];
  expr ($arr);
 }
?>

Из найденного (а скрипт при поиске расстановок для 3 чисел выведет и расстановки для меньшего их количества) интересным оказалось только

673+674+675 = 2022

для границы поиска 100000.

Если искать для 4 натуральных чисел и границы поиска 10000, по видимости найдётся больше, но после исключения лишнего (отличающегося только порядком скобок), и тривиального, вроде (1009-(1010-(1011+1012)))=2022, получим лишь

504+505+506+507=2022

ну или

(507*506)-(505*504)=2022

Вот, пожалуй, и всё уравнение - 2022.

Скрипты выполнялись на локальном хосте XAMPP с PHP 8.

06.01.2022, 17:21 [622 просмотра]