[Из песочницы] Занимательная задачка «Несчастливый билет»17.10.2016 18:48

image Думаю всем с детства знакома задача о счастливом билете. Однако чаще всего поездка в автобусе занимает гораздо больше времени, чем время, потраченное на суммирование первых и последних трех цифр.

И чтобы развлечь себя до конца поездки, я изобрел концепт «Несчастливого билета». Билета, у которого ни одно число из множества значений, полученного при помощи первых трех цифр, не совпадет ни с одним числом из множества значений, полученного при помощи последних трех цифр. Подробности в условии задачи.

Условие задачи

Найти все значения из 6 цифр, для которых ни одно из значений множества, полученного из первых трех цифр, не совпадет ни с одним значением множества из последних трех цифр.

Множество значений для каждой триады нужно получить:

  • Применяя перестановку цифр в пределах триады
  • Выполняя арифметические действия между цифрами: +, -, *, /
  • Используя скобки.
  • Применяя в качестве значений множества только целые числа

Пример
Билет: 983060

Множество значений триады: 983 [96, 33, 2, 3, 35, 99, 4, 69, 5, 75, 11, 45, 14, 15, 48, 51, 19, 20, 216, 24]
Множество значений триады: 060 [0, 6]

Общего значения нет — это несчастливый билет.

P.S. Опускаю отрицательные значения, так как для каждого отрицательного значения найдется такое же положительное


Таким образом, если вы до конца поездки не смогли найти общее число для первых и последних трех цифр, используя действия из условия, значит вам попался несчастливый билет! Или у вас не очень с математикой.
Мой вариант решения задачи
Выкладывать весь код не вижу смысла, постараюсь объяснить главное.

Список всех комбинаций из трех цифр — 1000 штук. Набор, в который будут складываться найденные билеты.

   List combinations = new ArrayList<>(1000);
   Set tickets = new HashSet<>();

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

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

for (Combination comb1 : combinations)
        {
            for (Combination comb2 : combinations)
            {
                for (Integer x : comb1.getValues())
                {
                    if (comb2.getValues().contains(x))
                    {
                        tickets.remove(comb1.toString() + comb2.toString());
                        break;
                    }
                    else
                    {
                        tickets.add(comb1.toString() + comb2.toString());
                    }
                }
            }
        }

Привожу метод, вычисляющий множество значений для каждой комбинации:
(Метод выполняется для каждой перестановки 3 цифр комбинации) 
 private void countValues(int a, int b, int c)
    {
        //Sum
        addValue(a + b + c);
        addValue(a + b - c);
        addValue(a + b * c);
        addValue((a + b) * c);

        if (c != 0 && b % c == 0) {addValue(a + b / c);}
        if (c != 0 && (a + b) % c == 0) { addValue((a + b) / c); }

        //Subtraction
        addValue(a - b + c);
        addValue(a - b - c);
        addValue(a - b * c);
        addValue((a - b) * c);

        if (c != 0 && b % c == 0) {addValue(a - b / c);}
        if (c != 0 && (a - b) % c == 0) {addValue((a - b) / c);}

        //Multiplication
        addValue(a * b + c);
        addValue(a * b - c);
        addValue(a * b * c);

        if (c != 0)
        {
            double x = (double)a * (double)b / (double)c;

            if (isInteger(x)) { addValue((int)x); }
        }

        if (c != 0)
        {
            double x = (double)a * (double)b / (double)c;

            if (isInteger(x)) { addValue((int)x); }
        }

        //Division

        if (b != 0 && a % b == 0) { addValue(a / b + c); }
        if (b + c != 0 && a % (b + c) == 0) { addValue(a / (b + c)); }

        if (b != 0 && a % b == 0) { addValue(a / b - c); }
        if (b - c != 0 && a % (b - c) == 0) { addValue(a / (b - c)); }

        if (b != 0)
        {
            double x = (double)a / (double)b * (double)c;

            if (isInteger(x)) { addValue((int)x); }
        }

        if (b != 0 && c != 0)
        {
            double x = (double)a / (double)b / (double)c;

            if (isInteger(x)) { addValue((int)x); }
        }
    }

Итого: 23088 билетов.

Счастливый билет: каждый 18
Несчастливый билет: каждый 43


Спасибо за внимание!

Комментарии (4)

  • 17 октября 2016 в 18:32

    0

    ↑

    ↓

    > И чтобы развлечь себя до конца поездки, я изобрел концепт «Несчастливого билета».

    Черт! А я книгу в телефоне читаю, чтобы скоротать время :-(

  • 17 октября 2016 в 18:33

    0

    ↑

    ↓

    По вашей логике:
    9–8/3 = 6
    Отбрасывать хорошо — округлять интереснее…

    • 17 октября 2016 в 18:47 (комментарий был изменён)

      0

      ↑

      ↓

      Может и интересно, но как-то нечестно. В глубине души я буду знать, что эти числа не равны. Зато я не запрещаю использовать нецелые числа в процессе вычисления. e.g. 2/8×5

  • 17 октября 2016 в 18:45

    0

    ↑

    ↓

    Расширте до игры Ландау.

© Habrahabr.ru