УДАР+УДАР=ДРАКА

[fregimus]

Вопрос навеян последней записью с числовыми ребусами И. Весеннего. Что вы знаете об алгоримизации решения таких ребусов? Если есть ссылки на статьи, было бы здорово. Ну, или просто идеями поделитесь.

З. Ы. ЖЖ опять тормозит несколько дней. Это у всех так, или только в гадюкинских краях?

Comments

[potan.livejournal.com]

Перебор с возвратом.
Ввиде программы на Prolog :-).
Кстати, в книжках про Mozart/Oz решение ребусов часто приводят как пример программирования в ограничениях.

[fregimus.livejournal.com]

Это-то само собой. Мне бы побыстрее.

[potan.livejournal.com]

Сомневаюсь, что в общем виде это возможно. Система нелинейных уравнений по модулю 10. Скорость определяется правильным порядком перебора и применением эвристик.

Одна тонкость

[my-tribune.livejournal.com]

В данной постановке, надо решать уравнения не по модулю 10 ;)

[slobin.livejournal.com]

В Mozart/Oz заметно быстрее, чем на Прологе. Если я правильно понял эти книжки (на практике не проверял), там какие-то зашитые в язык эвристики сужают потенциальный перебор с сотен миллионов (если загадка восьмизначная) до просто сотен, а потом уже эти сотни действительно тупо перебирают. Там вроде бы даже есть визуализатор графа тех вариантов, которые остались для перебора после первоначального отсечения лишнего. Но это так, как я понял при чтении по диагонали, мог и с прямым углом спутать.

... Intrat et exit ut nil supra ...

[fregimus.livejournal.com]

Посмотрю, спасибо.

[timur0.livejournal.com]

была когда-то статья в "Кванте", не помню года (не позже 93). идея была в ограничениях - в заголовочном примере очевидно, что Д = 1, У >= 5. а потом перебор по жадному алгоритму - если мы определились со старшими разрядами, то на долю младших остается мало вариантов.

[fregimus.livejournal.com]

Угу. Мне вот алгоритмы извлечения этих «очевидностей» как раз и интересны.

[timur0.livejournal.com]

алгоритм извлечения неравенств вполне очевиден:
УДАР * 2 <= 9876 * 2 = 19752 => Д = 1
УДАР * 2 > 10000, перебор по У с максимизацией остальных разрядов дает У >= 5
эту эвристику формализовать легко. другое дело, что она не всегда продуктивна: СУК * СУК = БАРСУК - этот пример надо решать с младших разрядов. хотя здесь, в примерах на умножение, тоже внятная эвристика - таблица умножения по модулю 10, длины чисел сокращаются не со старших, а с младших разрядов.
самое крутое - это задачи не с буквами, а со звездочками. если не забуду, вечером найду крутейшую задачу, решением которой горжусь :-)

[fregimus.livejournal.com]

Да, не забудьте, пожалуйста!

[timur0.livejournal.com]

вот: http://timur0.livejournal.com/130515.html

[fregimus.livejournal.com]

Ого!

[akalenuk.livejournal.com]

10! вариантов в худшем случае вполне себе перебираются.

[fregimus.livejournal.com]

Мне интересно, как эта задача обобщается. В системе счисления по основанию 100 все уже не так радужно.

[akalenuk.livejournal.com]

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

То есть вопрос о решении подобных задач все равно упирается в некоторый объем вычислений.

А 10! и даже 100! - это немного по нашим временам. Недавно в ru_pythonе предлагалась задачка: посчитать 1 000 000! Подразумевалось, что это возможно сделать за вменяемое время. Ну, на нетбуке это время немножко невменяемое, а вот 100 000! за 30 секунд считается. Брутфорсом, без факторизации.

Тут же объем задачи просто провоцирует решить ее перебором.

[fregimus.livejournal.com]

А вы не поддавайтесь на эти провокации!

[janatem.livejournal.com]

Так ведь посчитать n! и перебрать n! вариантов, пусть даже тривиальных, -- радикально разной сложности задачи.

[akalenuk.livejournal.com]

А, ну вообще да.

[fdo-eq.livejournal.com]

Ну и какого черта! (извините за резкость формулировки)
http://fdo-eq.livejournal.com/247147.html

[fregimus.livejournal.com]

Тут Вам И. В. отвечает: http://fregimus.livejournal.com/121056.html?thread=2901472#t2901472

Н-да, промазал

[my-tribune.livejournal.com]

Не туда написал :(

Коротко суть:
fdo-eq, если Вы автор задачи, то приношу извинения за отсутствие указания на Ваше авторство рядом с условием.
Сообщите, пожалуйста, на какой из Ваших сайтов/ЖЖ следует поставить ссылку рядом с условием этой задачи (если её вообще можно публиковать).

Re: Н-да, промазал

[fdo-eq.livejournal.com]

Это действительно моя задача. Проще всего поставить ссылку на запись в ЖЖ (еще раз: http://fdo-eq.livejournal.com/247147.html) - искать по архивам фидошной эхи RU_GOLOVOLOMKA (а еще раньше - по архивам конференции relcom.rec.puzzles) долго, да и ни к чему. Еще раз прошу прощения, если был излишне резок.

Ссылку поставил

[my-tribune.livejournal.com]

Спасибо за разъяснения и интересную задачку!

[yarikas.livejournal.com]

Нашёл давешнее обсуждение.

ЖЖ уж не от рекламы ли со звездой тормозит?

[fregimus.livejournal.com]

Я никогда не подписывался на кириличные (хосподи, слово-то какое!) услуги.

Задача на умножение

[pingback-bot.livejournal.com]

User timur0 referenced to your post from Задача на умножение (http://timur0.livejournal.com/130515.html) saying: [...] (вспомнилось по прочтении этого: http://fregimus.livejournal.com/121056.html [...]

Программистский brainfuck

[pingback-bot.livejournal.com]

User plakhov referenced to your post from Программистский brainfuck (http://plakhov.livejournal.com/143872.html) saying: [...] ПИСАТЬ О вставьте название дисциплины, которая кажется им скучной". По мотивам записей 'а и (1 [...]

[avkh.livejournal.com]

-- TSQL

create table #Digits (d int)

insert into #Digits (d) values (0)
insert into #Digits (d) values (1)
insert into #Digits (d) values (2)
insert into #Digits (d) values (3)
insert into #Digits (d) values (4)
insert into #Digits (d) values (5)
insert into #Digits (d) values (6)
insert into #Digits (d) values (7)
insert into #Digits (d) values (8)
insert into #Digits (d) values (9)

select
*
from
#Digits U
cross join #Digits D
cross join #Digits A
cross join #Digits R
cross join #Digits K
where
U.d<>D.d and U.d <> A.d and U.d <> R.d and U.d <> K.d
and D.d <> A.d and D.d <> R.d and D.d <> K.d
and A.d <> R.d and A.d <> K.d
and R.d <> K.d
and (1000*U.d+100*D.d+10*A.d+R.d) + (1000*U.d+100*D.d+10*A.d+R.d) = (10000*D.d+1000*R.d+100*A.d+10*K.d+A.d)

drop table #Digits

--------------
-- 8 1 2 6 5
-- 0 секунд

[fregimus.livejournal.com]

Это нечестно: это ж не вы сами решаете. На прологе вообще три строчки, а умельцы, поди, в одну запишут. Да, оптимизатор SQL как раз и есть решатель таких задач. Кстати, 0 секунд — непонятно, быстро или медленно.

Вспомнил об одном из возможных методов решения таких задач: О-алгебры (буква О латинская, не ноль). Вам, как специалисту по БД, это навевает какие-нибудь ассоциации?

[avkh.livejournal.com]

нет, про О-алгебры не слышал, тёмный
полез в вики - нашёл только O*-algebra, но кажется это не то

[avkh.livejournal.com]

0 секунд - это столько сколько должно быть.
Видимо он этот селект решает закручивая 5 вложенных циклов от 0 до 9, т.е. всего 100 тыс., это мгновенно при любом подходе.
И, если умный, то глядя на условие, ещё часть внутренних циклов пропускает.

[avkh.livejournal.com]

на самом деле всё ещё более нечестно - скрипт я сёдня не сочинял, а только подправил условие в старом, который был написан давно для проверки бумажного решеия задачки http://avkh.livejournal.com/5461.html

[avkh.livejournal.com]

а блин, там с разными системами надо пробовать !
ну, это мне лень , но там просто
цикл закрутить и умножаит не на 10^k а на N^k