Решение японских кроссвордов на Haskell

[sidristij]

Хм… покажу статью бабушке…

[Turbo]

Если код небольшой было бы интересно как программа справится с закрытым набором данных:
www.spoj.pl/problems/JCROSS/

На HASKELL эту задачу ещё никто не решал, а в списке доступных исходников он есть (Haskell ghc 6.10.4)
www.spoj.pl/ranks/JCROSS/

[bodhisattva]

Спасибо за ссылку! Я так понял, там ограничение на один исходный файл? Переделка некоторое время займет, плюс все-таки день рабочий, но как сделаю — о результатах отпишусь.

[bodhisattva]

Нет, то ли не для того предназначен хаскель, то ли, что более вероятно, я не умею его готовить: несколько способов решения перепробовал, но от «time limit exceeded» уйти не могу =(

[Turbo]

Там есть сложные тесты, видимо надо ограничивать число попыток найти решение. Как вариант, решать только первый кроссворд, остальные не решать (там предусмотрена такая возможность), что бы получить хотя бы 1 accepted. Всего там около 250 тестов.

[bodhisattva]

Она успевает решить 3 *facepalm*
На самом деле должно бы побольше, но там нельзя вывести только первые решения (обязательно должны быть все, пусть неправильные), а у меня уже при создании поля производятся некоторые вычисления, что на большом количестве кроссвордов, видимо, занимает заметное время.
Можно, конечно, оптимизировать, но смысла особого не вижу: если уж биться за скорость, то надо просто то же самое на каком-нибудь Си переписать, тогда, думаю, скорость на порядок возрастет.

[powder96]

Кроссворд в начале топика, должно быть, неплохо заманивает читателей ;)

[bodhisattva]

Если честно, именно с этой целью он там и находится :)

[tranquil]

Непонятно почему, но вспомнилось про Nikki and Robots, которое на днях зарелизили joyridelabs.de/game/trailer/

[Akson87]

Начал читать и понял, что нет… Haskell не для чтения поздней ночью…

Спасибо за статью!

[bodhisattva]

Всегда пожалуйста)

[danmiru]

Совершенно немотивированно ожидал увидеть однострочник.

[zloool]

Дружбамагия

[bodhisattva]

Да вы автор доброй половины статей в этом блоге! Большая честь для меня :)

[6opoDuJIo]

Э, а мне вот что в голову пришло — как насчёт того, чтобы кодировать в японском кроссворде цветное изображение?

[6opoDuJIo]

В самом низу статьи на вики оказывается было.

[bodhisattva]

Сначала подумал, что под картинкой будет подпись «например такое».
А если по делу — программу несложно под них переделать, но как правило они весьма скучные.

[6opoDuJIo]

Это я к чему веду — если создать НЕЧТО для подобной кодировки RGBA-изображений, то можно будет неплохо сжать текстуру.

[bodhisattva]

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

[6opoDuJIo]

Разжимать можно и на GPU, а вот насчёт неоднозначности — можно модифицировать алгоритм, хотя как именно я пока хз.

[developerxyz]

Можно просто модифицировать текстуру, чтобы разжималось однозначно