Думаю всем с детства знакома задача о счастливом билете. Однако чаще всего поездка в автобусе занимает гораздо больше времени, чем время, потраченное на суммирование первых и последних трех цифр.И чтобы развлечь себя до конца поездки, я изобрел концепт «Несчастливого билета». Билета, у которого ни одно число из множества значений, полученного при помощи первых трех цифр, не совпадет ни с одним числом из множества значений, полученного при помощи последних трех цифр. Подробности в условии задачи.
Условие задачи
Найти все значения из 6 цифр, для которых ни одно из значений множества, полученного из первых трех цифр, не совпадет ни с одним значением множества из последних трех цифр.
Множество значений для каждой триады нужно получить:
- Применяя перестановку цифр в пределах триады
- Выполняя арифметические действия между цифрами: +, -, *, /
- Используя скобки.
- Применяя в качестве значений множества только целые числа
Множество значений триады: 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<Combination> combinations = new ArrayList<>(1000);
Set<String> 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));
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
Спасибо за внимание!
Комментарии (31)
SLASH_CyberPunk
17.10.2016 18:33По вашей логике:
9-8/3 = 6
Отбрасывать хорошо — округлять интереснее…
EvGenius1424
17.10.2016 18:47Может и интересно, но как-то нечестно. В глубине души я буду знать, что эти числа не равны. Зато я не запрещаю использовать нецелые числа в процессе вычисления. e.g. 2/8*4
AndrewN
17.10.2016 20:56Смысл есть в этом? Ведь можно переставить и не целых промежуточных уже не будет
koldyr
17.10.2016 18:45+5Расширте до игры Ландау.
SLASH_CyberPunk
17.10.2016 19:04Жаль не могу вам поставить плюс, но спасибо за подсказку отличной игры! ^_^
impwx
17.10.2016 18:48+1Жалко, что в приведенном решении перебор вариантов идет вручную. Самый сок задачи был бы в том, чтобы именно алгоритмически перебрать все возможные комбинации знаков и скобок.
P.S. Не нашел комбинацииa * (b - c).EvGenius1424
17.10.2016 18:54Спасибо. Добавил, но на результат не повлияло. Буду рад, если кто-нибудь откликнется и опубликует собственный вариант решения.
SLASH_CyberPunk
17.10.2016 19:01+1Деление лучше рассматривать в виде целой части и остатка от деления, это и алгоритм и момент из комментариев выше
koldyr
17.10.2016 19:16Перестановка и обратная польская запись позволяют перебрать все варианты, правда с избытком из-за коммутативности сложения и умножения.
phvoryh
17.10.2016 20:01+1Есть известная вариация: расставляя знаки арифметических действий и скобки, получить в результате 100. Знаки само собой не обязательно расставлять между всеми цифрами, то есть для билета 777777 допустимым решением является (777-77)/7. Решения есть для значительной доли билетов (если мне не изменяет память, по опыту выходило где-то треть или половина), но зачастую очень хитрые.
LynXzp
17.10.2016 22:02У меня получилось раз 10… из 10. Может повезло. Но использовал все (если сравнить с игрой Ландау то далеко не все).
phvoryh
18.10.2016 00:11Закодил перебор. Если нигде не ошибся, то счастливыми являются 906735 билетов. Так что результат 10 из 10 кажется не сильно удивительным. Но, если честно, я поражён, что у вас так легко получилось. Порой я убивал всю поездку, чтобы найти сотню. Поэтому попробовал специально поискать сложные билеты (сам билет в заголовке спойлера, ответ внутри):
101048(10+10/4)*8TheGodfather
18.10.2016 09:26У меня тоже получается почти в 100% случаев, когда часто ездил на автобусе, специально собирал билетики, для которых не получилось в уме составить. За год поездок штук 10 таких билетов накопилось, из них для 7 или 8 решения и вправду не существует (проверял самописной программкой)
ainu
18.10.2016 13:42422400. Годами думал, не решил
LynXzp
18.10.2016 17:254^(-log2(2))*400
ainu
18.10.2016 17:49Ну логарифм тоже не очень то вписывается, как и знак степени. Так то у меня была мысль:
(4^ — (2/2)) * 400
Для яваскрипта:
(4** — (2/2)) * 400
Но это выходит за рамки + — / * ( )LynXzp
18.10.2016 18:08Но если решений без степени и логарифма нет (phvoryh подтвердил), то почему бы не воспользоваться.
senya_z
17.10.2016 23:22+1Предложенный алгоритм обхода можно слегка улучшить. Первое, что бросается в глаза — много ненужных операций с листом тикетов — почти каждый кандидат добавляется в лист, и почти каждый потом из листа убирается. Немного переписав цикл, можно оставить только добавление, которое будет происходить после внутреннего for, с заменой break на continue на внешний цикл. Второе — можно сравнивать forward-only (комбинацию с самой собой сравнивать не имеет смысла, комбинацию BA рассматривать после того как раньше рассмотрели AB тоже не имеет смысла), добавляя сразу comb1 + comb2 и comb2 + comb1.
for (int comb1Index = 0; comb1Index < combinations.size(); comb1Index++)
{
nextPair: // labeling for early exit from nested loop
for (int comb2Index = comb1Index + 1; comb2Index < combinations.size(); comb2Index++)
{
Combination comb1 = combinations[comb1Index];
Combination comb2 = combinations[comb2Index];
for (Integer x: comb1.getValues())
{
if (comb2.getValues().contains(x))
{
continue nextPair;
}
}
tickets.add(comb1.toString() + comb2.toString());
tickets.add(comb2.toString() + comb1.toString());
}
}
P.S. Прошу прощение за корявые отступы. Не могу использовать тэги, а пробелы и табы почему-то игнорируются.
senya_z
17.10.2016 23:34Еще как вариант (если много свободной памяти) можно заранее посчитать мэп обратных зависимостей (в то же время, когда прямые считаются) — от арифметического результата к списку триад. По этим данным легко быстро построить лист билетов, не удовлетворяющим условию задачи. Можно для этого создать массив из миллиона булов, в который писать тру, на каждую такую найденную комбинацию. В конце пройти по массиву, выбрав те индексы, где значение false.
eversyt
18.10.2016 07:11Я в детстве еще факториал себе разрешал. И тогда несчастливых билетов не остается (это гипотеза :) )
В вашем случае 6 — 6/6 = 0! + 1 + 3
abyrkov
18.10.2016 07:11+1Вот я тут думал, что мне с MAC'ами и IP'ами из подсети моего провайдера делать.
Теперь знаю)
meft
18.10.2016 09:10А я просто пытаюсь собрать значение 100 из цифр билетика. Только перестановка запрещена, т.к. в некоторых случаях очень сильно облегчает задачу. А так, использую любые арифметические знаки.
Порой все легко, иногда очень сложно. Бывают случаи, когда невозможно (например, первые 95 билетов).
Другими словами, нужно расставить арифметические знаки так, чтобы при решении вышло 100.
Barafu
18.10.2016 11:51+1Попробовал найти "в лоб" все несчастливые билеты. Оказалось несложно, компьютер считал где-то 5 секунд. Всего нашлось 874 комбинации.
Код на Питонеopindex=["+","*","-","/"] partemplates=["%s%s%s%s%s","(%s%s%s)%s%s","%s%s(%s%s%s)"] def build(values,op1,op2,paren): textvalues=[str(a) for a in values] result=partemplates[paren] % (textvalues[0],opindex[op1],textvalues[1],opindex[op2],textvalues[2]) return result tickets=[] calcs=[] def all_tickets(): for d1 in range(0,10): for d2 in range(0,10): for d3 in range(0,10): calc_ticket((d1,d2,d3)) def calc_ticket(ticket): calc=set() for o1 in range(0,4): for o2 in range(0,4): for p in range(0,3): form=build(ticket,o1,o2,p) try: value=int(eval(form)) calc.add(value) except: pass tickets.append(ticket) calcs.append(calc) bad_tickets=[] def find_bad_tickets(): for i1 in range(0,len(calcs)): for i2 in range(0,len(calcs)): if calcs[i1].isdisjoint(calcs[i2]): bad_tickets.append((i1, i2)) all_tickets() find_bad_tickets() print(len(bad_tickets))
AndreyRubankov
> И чтобы развлечь себя до конца поездки, я изобрел концепт «Несчастливого билета».
Черт! А я книгу в телефоне читаю, чтобы скоротать время :-(