Автобусный билетик

Вводная


Тем из нас, кому приходится тратить полчаса-час на путешествие из Москвы в Москву, приходится искать, чем занять и разогреть ещё не до конца проснувшийся мозг. Кто-то читает, кто-то кидает птичек, кто-то решает математические головоломки. Например, классическая задачка: среди шести цифр автобусного билета расставить скобки и операторы так, чтобы получилось число 100. Бывает так, что ну никак не удаётся найти решение, и конкретная задачка не отпускает весь оставшийся день. Поневоле задумаешься над алгоритмом.
Решение «в лоб» подстановкой скобок и операторов и проверка на каком-нибудь математическом движке не устраивало, генетические алгоритмы, по которым я с ума схожу, не подходили из-за склонности скапливаться в локальных экстремумах. В итоге задача свелась к перебору всех возможных двоичных деревьев с заданным числом листьев (для шести их ровно 42).

Переходим к сути


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

Тем не менее, для шести цифр программа выполняется меньше, чем за секунду, имея таким образом право на жизнь.
Реализовывать будем на C++. Disclaimer: я ещё только учусь. Если вы видите откровенно плохой или просто неоптимальный код — сообщите, пожалуйста.
Пропуская достаточно тривиальный конструктор, рассмотрим создание следующего дерева. В узлах деревьев располагаются операторы, избавляя нас тем самым от возни со скобками и приоритетами. Операторов всего пять: конкатенация, сложение, вычитание, умножение и деление. Унарный минус не используем. Деревья перебираем по следующему принципу: для каждого правого поддерева делаем проход по всем левым поддеревьям. Повторяем для каждого оператора, то есть, пять раз. Внутри поддеревьев происходит ровным счётом то же самое.
Генерация дерева
void BinTree::buildNext()
{
  if (type == NUMBER)          // Просто лист,
      throw BinTreeLastTree(); // сделать с ним ничего нельзя.
  try
  {
    left->buildNext();
  }
  catch (BinTreeLastTree)
  {
    try
    {
      right->buildNext();
    }
    catch (BinTreeLastTree)
    {
      bool isLast = false;

      leftSize++;
      if (leftSize == size)
      {
        leftSize = 1;

        type = (Operation)(type + 1);
        if (type == NUMBER) // Если дошли до конца списка операций,
        {
          type = CONCAT; // то возвращаемся в начало
          isLast = true; // и ставим «зарубку».
        }
      }

      delete left;
      delete right;
      generateSubTrees();

      if (isLast)
        throw BinTreeLastTree(); // Исключения используем в качестве сигналов о том, что дерево совершило «полный круг».
    }
  }
}

За вычислением дело тоже не постоит, так что подробно останавливаться на нём не будем.
Главной проблемой были одинаковые решения: кремниевый друг уверял меня, что (1+(2+3)) и ((1+2)+3) — разные вещи. Чтобы объяснить ему обратное, применим «умную» расстановку скобок, а чтобы не тратить время на фильтрацию результата, препоручим это std::set.
Код расстановки скобок
std::string BinTree::toString(bool parentheses)
{
  switch (type)
  {
    case CONCAT:
      return left->toString() + right->toString();

    case ADD:
      {
        std::string leftStr = left->toString(!(left->getType() == ADD || left->getType() == SUB)),
                    rightStr = right->toString(!(right->getType() == ADD || right->getType() == SUB));

        return (parentheses?"(":"") + leftStr + operationSymbol[type] + rightStr + (parentheses?")":"");
      }

    case SUB:
      {
        std::string leftStr = left->toString(!(left->getType() == ADD || left->getType() == SUB));

        return (parentheses?"(":"") + leftStr + operationSymbol[type] + right->toString() + (parentheses?")":"");
      }

    case MUL:
      {
        std::string leftStr = left->toString(!(left->getType() == MUL || left->getType() == DIV)),
                    rightStr = right->toString(!(right->getType() == MUL || right->getType() == DIV));

        return (parentheses?"(":"") + leftStr + operationSymbol[type] + rightStr + (parentheses?")":"");
      }

    case DIV:
      return (parentheses?"(":"") + left->toString() + operationSymbol[type] + right->toString() + (parentheses?")":"");

    case NUMBER:
      {
        char str[2] = {(char)(digit[0]+'0'), '\0'};
        return str;
      }

    default:
      ;
  }
  throw BinTreeException();
}

Вуаля!
Код вызова
int main()
{
  std::string input;
  std::cin >> input;
  std::cout << busPuzzleSolve(input);
  return 0;
}
std::string busPuzzleSolve(std::string input)
{
  return BinTree(input.c_str()).solve();
}

Результат
123654

((((1*2)+3)*6)-5)*4
((1*(2+(3*6)))+5)*4
((1*(2+3)*6)-5)*4
((1*(2-3))+6)*5*4
((1*2)+(3*6)+5)*4
((1*2)-(3-6))*5*4
((1*2)-3+6)*5*4
((1/(2-3))+6)*5*4
((12*3)-(6+5))*4
((12*3)-6-5)*4
(1+23+6-5)*4
(1-((2*3)-(6*5)))*4
(1-(2*3)+(6*5))*4
(12+(3*6)-5)*4
1*(((2+3)*6)-5)*4
1*(2+(3*6)+5)*4
1*(2-(3-6))*5*4
1*(2-3+6)*5*4
1+((2+3+6)*(5+4))

Код на SkyDrive в архиве rar (+ файл проекта Code::Blocks) (~2.56 KiB).
Код на pastebin.
Share post

Similar posts

Comments 32

    +16
    Зачем у вас логика на исключениях?
      –11
      По-моему, это проще, чем возвращаемое значение, а заодно прерывает исполнение без моего вмешательства.
        +10
        Попробуй переписать на нормальных рекурсивных вызовах функций, позапускай оба варианта раз по 10К и узнай много нового о производительности исключений.
          +13
          Намёк понял, приму к сведению.
      +1
      1) унарный минус надо таки учитывать, например для решения 001101
      2) какой процент нерешаемых задач? А если разрешить степень и факториал?
        0
        1) В классическом варианте, вроде как, унарного минуса, степеней и факториалов нет. Как бы то ни было, если разрешить унарный минус, можно выбросить операцию вычитания.
        001101
        001101
        
        (0*0)-(1-101)
        (0*0)-1+101
        0+0-(1-101)
        0+0-1+101
        0-(0+1)+101
        0-(0+1-101)
        0-0-(1-101)
        0-0-1+101
        


        2) Понятия не имею, честно говоря. Код слишком медленный, чтобы пропустить его миллион раз. Я попробую его переписать без исключений в варианте «есть/нет решений» и отпишусь.
        С дополнительными операциями, скорее всего, решений будет больше, но всё равно не все комбинации будут решаемы.
          0
          Нерешаемых задач, если разрешить дробное деление, получилось 93901.
          Оптимизация ещё в процессе, сей подсчёт занял около 40 минут, что уже гораздо лучше прошлого раза (оставил на ночь, к утру так и не закончилось).
          Solved 906099 out of 1000000; 90.6099%
            0
            С дробями, но без унарного минуса у меня получилось всего 93265 плохих билетов. Вот их список (надеюсь, что он откроется). Есть ли какой-нибудь плохой номер, не попавший в него?
              0
              Похоже на то, что у меня просто баг. Собрал с флагом оптимизации, получил другой результат.
              Список я не составлял, к сожалению.
          0
          Особенно интересно было бы разрешить кратные факториалы. Типа 3!!-620+00 для 362000.
            +1
            Кратный факториал пишется как (3!)!. А 3!!=1*3=3 — немного другое выражение.

            3/6*200+0
            0
            Унарный минус (в арифметическом варианте) достаточно применять ко всему выражению, т.е. задача сводится к тому, чтобы получить 100 или --100.
            А кроме степени и факториала имеет смысл добавить квадратный корень (в более продвинутом варианте есть ещё десятичная точка и периодические дроби — но для 6-значных номеров это перебор). И получаются варианты вроде:

            4436: 100=sqrt(sqrt(sqrt(4^(4!))+36
            22838: 100=sqrt(2)*((sqrt(2)+sqrt(8))^3-8

            не так-то просто их искать автоматически.
              0
              1) 0*0-1+101
              2) Нерешаемых задач, по моим подсчётам, 101893 из миллиона, т.е. чуть больше 10%. На перебор миллиона номеров ушло примерно 170 секунд.
              0
              Интересно, что 101 из 6-значного номера получается уже только в 82% случаев. А получить 10000 из восьмизначного номера — довольно редкий вариант (особенно, если первая и последняя цифры нечётны). Правда, всех номеров я не перебирал.
              +1
              Бывает так, что ну никак не удаётся найти решение, и конкретная задачка не отпускает весь оставшийся день.

              Эта задача вообще выполнима для любого шестизначного числа?
                +1
                Нет. Самый простой пример — 000000. Программа утверждает, что комбинация 778451 тоже не имеет решений.
                0
                А как обрабатывается деление с остатком?
                  0
                  Никак. Разрешено только деление нацело.
                    0
                    Это слишком жестоко. Надо разрешить рациональные числа для промежуточных результатов.
                      0
                      Рациональные числа помогут в 8628 номерах (из миллиона). Менее 1% от общего количества.
                      Например:
                      617381
                      777700
                      995696

                        0
                        И, кстати, унарный минус поможет в 20539 случаях. И если совместить его с рациональными числами, плохих билетов останется 75413.
                  • UFO just landed and posted this here
                      +2
                      я реализовывал такую задачу с помощью обратной польской записи. хотя суть та же. только варианты перебираются с помощью добавление новых символов к строке.
                        0
                        А можно поподробнее?
                        Если я правильно помню, "(222-22)/2" в ОПЗ записывается как «222 22 — 2 /». Если просто добавлять символы в конец строки, такого не получить; если вставлять и в середину — плохо представляю себе реализацию.
                          +1
                          Составляется набор всех допустимых последовательностей операций. В последовательности 11=6+5 мест для операций, в каждом месте может стоять одна из 5 операций (4 арифметических+загрузка очередной цифры). Фактически набор операций — программа для стековой машины. Затем каждая программа прогоняется на интерпретаторе (тоже нужно написать) для данного набора цифр в билете.

                            0
                            Вставлять после каждого числа и знака. Было (2 + 3) * 4, в ОПЗ будет 23+4*. Хотим добавить все варианты деления на 5 — ставим 5/ после всех знаков и чисел. получаем следующее:
                            25/3+4* -> (2 / 5 + 3) * 4
                            25/3+4*
                            25/3+4*
                            25/3+4*
                              0
                              Вставлять после каждого числа и знака. Было (2 + 3) * 4, в ОПЗ будет 23+4*. Хотим добавить все варианты деления на 5 — ставим 5/ после всех знаков и чисел. получаем следующее:
                              25/3+4* -> (2 / 5 + 3) * 4
                              235/+4* -> (2 + 3 / 5) * 4
                              23+5/4* -> (2 + 3) / 5 * 4
                              23+45/* -> (2 + 3) * (4 / 5)
                              23+45*/ -> (2 + 3) / (4 * 5)
                                0
                                извиняюсь за то что так некрасиво получилось. да и последнюю строчку неправильно написал
                            0
                            Мсье, try-catch, ну как же так.
                              –3
                              Эта задача хорошо решается кодогенерацией.
                                0
                                Как один из вариантов, можно препроцессором генерировать все возможные варианты, компилятор сам порежет ненужные.

                              Only users with full accounts can post comments. Log in, please.