Решение японских кроссвордов одним запросом SQL

[Radik_Wind]

Месье знает толк…

[Dialog]

Месье крут.

[deNULL]

Самый смешной и оригинальный комментарий, который только можно встретить в блоге «Ненормальное программирование».

Пусть уже НЛО его автоматически отправляет после каждого поста.

[ICELedyanoj]

Брутфорс японского кроссворда?

[maovrn]

Да. Только обычно при брутфорсе генерируется предположение, если не проходит проверку — отбрасывается, затем следующее. В итоге времени занимает много, памяти мало. А тут и времени, и памяти требуется сразу много.

[malan]

[PapaBubaDiop]

#1064 — You have an error in your SQL syntax; check the manual that corresponds to your MySQL server version for the right syntax to use near 'INPUT as

Хотите нас на Oracle подсадить?

Вопрос про возведение в степень двойки — оно работает натурально быстро в этой SQL?

[maovrn]

В большом количестве используются исключительно Oracle-фишки: аналитические функции, виртуальные таблицы, иерархические запросы. В других СУБД работать не будет, к сожалению. А возведение в степень далеко не самая тяжелая операция в этом запросе. Обработка регулярных выражений на миллионах строк куда весомей.

Для отладки использовал тот самый огрызок Oracle 11 XE на домашнем компьютере (далеко не сервер). Поле 3x3 обсчитывается за 1.5 секунды, 4x4 за 6.5 минут, 5x4 почти два часа, а 5x5 я уже не смог рассчитать.

[Optik]

На какой машине?

[maovrn]

Intel Core i5 2.8Ghz (XE использует только одно ядро из 4-х), про память вообще писать бессмысленно — XE использует только 1Gb, хотя в наличии все 8.

[FireSecure]

Судя по всему, наш клон слабее вашей машины раза в 3)

[igofed]

Это круто=)

[wrmax]

Новая задача на собеседование =)

[lolmaus]

На Хабре нельзя шутить на такие темы… :/ PS Плюсанул.

[wrmax]

Спасибо. В принципе у меня тоже были тяжёлые собеседования, но я отношусь к этому с юмором.

[achekalin]

Мне сразу вспомнилось из «Пароль Рыба-Меч»: «А теперь взломай 1024 шифр, и у тебя 40 секунд» )

st-im.kinopoisk.ru/im/kadr/1/5/0/kinopoisk.ru-Swordfish-15072.jpg

[Bulbulator]

у вас явно нехватает нагрузки на работе :)

[Geckelberryfinn]

Помнится, видел решение судоку на SQL.Ru, средствами DB2. Вот

[maovrn]

Автор этого решения вообще маньяк (в хорошем смысле)! Одна запись запроса весит 33 kb без комментариев, мне терпения не хватило разобрать его.

[modestguy]

Круто… плюс

[DenKrep]

Хм. Мсье действительно знает толк, но, учитывая, что мы говорим о oracle-sql, я бы напомнил, что даже в 10-ке есть итерации и я бы решал эту задачу посредством конструкции MODEL (если бы вообще решал её в SQL, конечно). Думаю что получилось бы эффективнее и не так нагруженно по использованию памяти. Конечно, model нельзя назвать совсем чистым sql-ем, но для этой задачи, на мой взгляд, очень даже подходит.

Но метод написанный автором красив.

PS: И, кстати, 12-ка не на подходе, она уже здесь, уже 2 месяца как.

[maovrn]

Спасибо за комплимент и интересный отзыв. Если я правильно понял, конструкция MODEL помогла бы более эффективно сгенерировать строки со значениями. На asktom приведен шикарный пример расчета чисел Фибоначчи. Но не избавила бы от необходимости перебирать все перестановки, чтобы потом отфильтровать только возможные. А именно огромное число перестановок — главный тормоз. Надо бы поразбираться, никогда не применял эту конструкцию на практике.

В Oracle 10 отсутствует функция listagg, которая склеивает строки по группе. Можно написать ее аналог на PL/SQL. Но это убивает весь спортивный интерес. А как иначе получить все значения строки или колонки в перестановке я не придумал.

О, 12-ка вышла! Что-то я отстал. Специально перерыл весь спам, который мне с oracle.com шлется — ничего. Неправильный спам какой-то.

[DenKrep]

model очень богат разнообразным функционалом. в том числе в нём конструкция iterate, которая позволила бы организовать цикл. Reference model я бы использовал чтобы задать исходные условия задачи, основную модель с dimension (x,y) measure (val) — дал бы на основное поле. Потом задаём набор правил по которым будем решать задачу и итерируем пока не закроем всё поле. Как ие правила зададите — зависит только от вас. Я бы не делал чистый перебор, ибо это неэффективно (то что ваш метод не решил поле большее чем 5*5 в разумные сроки на приемлимом компьютере это доказывает). Кстати, oracle xe использует только одно ядро (это тоже одно из ограничений лицензии).
listagg (или stragg, как её знают по Кайтовскому исполнению) можно было бы действительно сделать самостоятельно, неспортивности не вижу… но можно попробовать обойти и его отсутсвие другими методами.
В целом — было бы лишних пару часиков — попробовал бы реализовать на model и выдать ответ, но увы, сегодня этого времени нету, потому пока только дал наводку вам на ключевые слова. Вот ещё где можно подробнее почитать про то что оно такое, хотя, конечно линк не оригинален :)
docs.oracle.com/cd/B19306_01/server.102/b14223/sqlmodel.htm
Конечно, в любом случае будет перебор (даже когда вы сами решаете «аналитически» — это тоже в некоторой мере перебор). Просто не стоит делать чистый brute-force. Можно итеративно пробегать что можно заполнить хотя-бы на уровне каждой строки-колонки (учитывая задание и уже заполненные ячейки — как мы делаем при «аналитическом» поиске), а потом уже добить результат брут-форсом. Хотя, как я уже сказал, спортивный интерес это понизит, т.к. этот sql уже не настолько «sql» как в вашем решении.

А 12-ка, да. 29-го июня. С 30-го уже скачал и установил себе на виртуалку. Но писать статьи о новых фичах руки почти не доходят. Надеюсь что скоро исправлюсь.

[DenKrep]

oops, sorry, случайно в основной тред бросил. Это был ответ на Ваш комментарий habrahabr.ru/post/192752/#comment_6701608