- 01
- 02
- 03
- 04
- 05
- 06
- 07
- 08
- 09
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
digits n = reverse $ map (`mod` 10) (takeWhile (/= 0) (iterate (`div` 10) n))
fromDigits l = sum $ zipWith (*) (reverse l) (map (10^) [0..])
isPalindromic x = digits x == (reverse $ digits x)
f :: Integer -> [[Integer]] -> [Integer] -> Int -> [[Integer]]
f x founded lookedup niter
| niter > 50 = [notlychers, [x] ++ lychers ++ lookedup, zs]
| nextX `elem` notlychers = [[x] ++ notlychers ++ lookedup, lychers, zs]
| nextX `elem` lychers = [notlychers, [x] ++ lychers ++ lookedup, zs]
| isPalindromic nextX = [[x] ++ notlychers ++ lookedup, lychers, zs]
| otherwise = f nextX founded (x : lookedup) (niter+1)
where nextX = x + fromDigits (reverse $ digits x)
notlychers = founded !! 0
lychers = founded !! 1
zs = founded !! 2
g :: [[Integer]] -> [[Integer]]
g founded = f (x-1) [xs, ys, [x-1]] [] 0
where x = zs !! 0
xs = founded !! 0
ys = founded !! 1
zs = founded !! 2
gg n = g [[],[],[n+1]]
isLycher n = null $ (gg n) !! 0
Follow us!
А вот теперь сравните, любой код на Яве длиной 29 строчек с хорошим форматированием и короткими строчками. Кроме того, тут почти половина посвящается конкатенации строчек и их печатанию. При чем тут нету какого-то нагромождения редко используемых функций типа всяких операций с перемещением битов в байтах.
Для того чтобы понять что код делает нужно не просто усилие приложить. Это пытка такое читать.
это ви про founded?
а "трушные", наоборот, понимают высокоабстрагированный код и ругают спагетти-код.
что это? ООП головного мозга и падение профессионализма с опытом?
Например, выражение a b c d e может быть валидной программой в Хаскелле, Си, Лиспе и Баше, но когда Си-программист увидит такую программу, он будет с утюгом бегать за мудаком, который придумал такой шаблон. Примерно то же самое будет делать лиспер в поисках того, кто придумал такой ридер макрос. На Баше - это норма жизни, потому что интерпретация однозначная - a(b, c, d, e) - т.е. вызывается функция a с параметрами b, c, d, e. В Хаскелле - это тоже, по-своему, норма жизни, единственное, интерпретаций есть несколько: a(b(c, d, e)), a(b(c), d(e))... и т.д.
Т.е. идиотское желание убрать скобки делает язык похожим на то, как говорит Ёда.
Но если вам кажется, что это не достаточно убедительный аргумент - сравните, например: практически любой другой язык возможно автоматически отформатировать - Хаскелл в принципе не возможно. Автокомплит? - размечтались... Компьютер на уровне исходного кода вообще не понимает, что происходит в программе пока она не написана и не работает правильно. Сообщения об ошибках - как правило не то, что не указывают на строку с ошибкой, они вообще функцию правильно угадать не могут. Даже PHP в этом смысле лучше.
Всё гораздо лучше, чем вы описали. Язык прекрасен, основная проблема - отсутствие стабильной инфраструктуры. Попробуйте установить текстовый редактор Yi (не на винде, там он вообще не соберётся, на OpenSUSE или Fedora, к примеру), и вы поймёте, о чём я. Сравните с vim/emacs. Вот, что действительно демотивирует.
Первое и самое устойчивое сравнение которое возникает при виде программы на Хаскеле - клинопись (я, кстати могу читать некоторые древние симитские языки, не только иврит - так что знаю из первоисточника, на что это похоже). Только там это было объяснимо потому, что писать пупым гвоздем по камню - особо не разбежишься, а когда то же самое делают в 21м веке - это идиотизм.
Я пробовал leksah - Yi не пробовал, но не горю желанием. Разве что если я когда-нибудь возьмусь придумывать систему магии и алхимии для ролевых игр, и мне не будет хватать пиктрограм.
PS. Вот, кстати, офигенная иллюстрация тому, как ИДЕ написаная на Хаскеле понимает синтаксис языка - не сложно догадаться, что лямбды там не было, это слеши которые нужны для того, чтобы записать многострочный строковый литерал - потому что кавычек явно не хватило...
От синтаксиса лично у меня никакого баттхёрта нет.
// к слову есть модуль с digits / unDigits, то запарка тут чуть ниже
Исключительно для примера (можно было оптимизировать, чтобы строку не создавать каждый раз, но это мелочи по сравнению с ненужной проверкой половины строки:
ПС. И lychrels, а не lychers :).
ППС. И структура такаяже черззаборногузадерическая - нужно угадывать что происходит после чего и где функция а где аргументы.
Premature-optimisation ;). Здесь конкретная задача, а на списках так проще.
> lychrels
Ага, текст по ссылке по диагонали прочитал. Подхватил ошибку из приведенного кода.
we shall assume that a number is Lychrel
Где в конкретной задаче вообще говорится об использовании списков? Ну, если проще сделать хуже - то в чем собственно оправдание? Да, как правило проще сделать хуже.
Про решето Эратосфена - имелось в виду не проверять суммы от уже проверенных слагаемых? Если да - то, вобщем, имеет смысл, но с другой стороны не-палиндромов не так-то и много, как оказалось (меньше 400), так что это как раз не принципиально (по сравнению с потенциальными ненужными 500000 проверками).
Про цепочки: для каждого числа - проверяем 50 последующих, то есть для второго проверено 49, проверив ~64 вместо 50 можно снизить число операций (вроде раз в 10).
// Проверьте, что-то ваш код много выдает, вроде 249 должно быть.
Раз уж такое дело :)
ЗЫ. Где и кто определил приемлимое время?
на projecteuler.net и определено:
Each problem has been designed according to a "one-minute rule", which means that although it may take several hours to design a successful algorithm with more difficult problems, an efficient implementation will allow a solution to be obtained on a modestly powered computer in less than one minute.
Мне экономия на стравнении полиномов не кажется хорошей стратегией оптимизации, поскольку она не даёт ни выигрыша в порядке роста, ни даже особого выигрыша в константе (в два раза точно быстрее не заработает, тут полно более затратных операций).
я бы решил задачу в точности так же, как guest:
Результат выполнения:
т.е. даже при использовании языка с "динамической" типизацией на современной машине такое решение поставленной задачи требует около полусекунды (измерял несколько раз, было и 221.99 ms). Я считаю это вполне приемлимым.
При всем желании, я не вижу смысла делать лишнюю по определению проверку, даже если бы это не занимало столько времени. Это просто глупо.
но на ней крутится tomcat с нехилым приложением, запущено несколько проектов IntelliJ IDEA и браузер.
Давайте посмотрим в ideone, думаю, там примерно одинаковые машины выполняют код (хоть конкретных характеристик я и не нашёл): Жаль, что у ребят стоит clisp, он вроде только интерпретирует код, не компилирует. Не знаю, почему ваш код возвращает 9648, я в него не вникал, просто скопировал и добавил format. К сожалению, вывести время непосредственного выполнения куска кода в CL не так просто, суммарное время на компиляцию и запуск у программ примерно одинаковое.
> Это просто глупо
наличие этой "лишней" проверки существенно упрощает алгоритм, кроме того, оно гораздо лучше сочетается с функциональной парадигмой.
В индустрии ПО очень много "лишних" действий (разбиение приложение на слои, всякие там шаблоны вместо свитчей), но удобство и скорость разработки программ нынче гораздо важнее потерянных миллисекунд.
Скомилировать можно, но там этого никто не даст сделать.
Я распечатал все найденые палиндромы и числа из которых они были получены, проверил - все сошлось 352. Не знаю как у вас получается что-то другое.
Как проверял :)
кажется, здесь что-то не так: число нужно складывать с инверсией его самого:
> 47 + 74 = 121
Около 90 миллисекунд.
Жаль, в CL нет поддержки ленивых последовательностей из коробки, хоть при наличии макросов их и можно реализовать в виде библиотеки.
P.S. я бы на вашем месте не использовал конструкцию (if (cond) (progn ...)), ведь есть более короткий и удобочитаемый (when (cond) ...), который развернётся в ту же конструкцию
ЗЫ. (when (cond ...)) совсем не то же самое что (if (cond) ...) уже хотя бы потому, что это тот же if, только с одной веткой, а в коде их две :S
>> SICP (Structure and Interpretation of Computer Programs)
> в коде их две
У вас форматирование поехало, incf на одном уровне с if, а скобочки я не считал. Извиняюсь.
занятная очепятка add-xyes
Может зависеть от того, что подразумевается под палиндромом. Только wxxw или так же и wvxvw.