1. Куча / Говнокод #10022

    +103

    1. 01
    2. 02
    3. 03
    4. 04
    5. 05
    6. 06
    7. 07
    8. 08
    9. 09
    10. 10
    11. 11
    12. 12
    13. 13
    14. 14
    15. 15
    16. 16
    17. 17
    18. 18
    19. 19
    20. 20
    21. 21
    22. 22
    23. 23
    24. 24
    25. 25
    26. 26
    27. 27
    28. 28
    29. 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

    http://projecteuler.net/problem=55
    http://projecteuler.net/thread=55


    >i even haven't understood why it works :(

    Запостил: TheHamstertamer, 23 Апреля 2012

    Комментарии (48) RSS

    • Согласен, говнокод, нафиг не нужно разворачивать всю последовательность для того, чтобы убедиться в том, что это палиндром, достаточно только второй половины.
      Ответить
    • >
      g founded = f (x-1) [xs, ys, [x-1]] [] 0
       where x  = zs !! 0
             xs = founded !! 0
             ys = founded !! 1
             zs = founded !! 2
      Лень вникать в решение, но уже только за это стоит плюсовать. Где pattern-matching?
      g (xs : ys : (x:_) : _) = f (x - 1) [xs ys [x-1]] [] 0
      Обращения к спискам по индексу всюду! И вообще, обычно для решения задачи принято заводить отдельный тип. Первые строчки тоже доставляют. Разбираться в мясе посередине откровенно лень
      Ответить
      • Кстати, по поводу "лень вникать".
        А вот теперь сравните, любой код на Яве длиной 29 строчек с хорошим форматированием и короткими строчками. Кроме того, тут почти половина посвящается конкатенации строчек и их печатанию. При чем тут нету какого-то нагромождения редко используемых функций типа всяких операций с перемещением битов в байтах.
        Для того чтобы понять что код делает нужно не просто усилие приложить. Это пытка такое читать.
        Ответить
        • Смысл каждой строчки мне прекрасно понятен. мне лень вникать в "алгоритм". Java код читать для меня - бОльшая пытка, из-за громоздких конструкций понять общую идею гораздо сложнее.
          Ответить
          • Да ну не правда же. Алгоритм на самом деле простецкий. Только текст программы напоминает сочинения студенток русской литературы, в котором сказуемое в предложении на первом месте, потом десять деепричастных оборотов и в самом конце - подлежащее, когда уже и не помнишь с чего вообще начиналось. Ну и там со старославянскими афоризмами умело добавленными в ключевых местах.
            Ответить
            • > старославянскими афоризмами умело добавленными в ключевых местах
              это ви про founded?
              Ответить
              • http://3.bp.blogspot.com/_W7oqWQfFYLA/SVFrMcfePlI/AAAAAAAAELk/k_4UDiot3Zg/s1600/2.jpg
                Ответить
            • Читаемость кода зависит не столько от языка, сколько от кодера.
              Ответить
              • Еще больше зависит от читающего.
                Ответить
                • кстати, а ведь и правда, кодомакаки легко читают простыни, и орут, что "правильный" код (ООП,паттерны,слабая связность) им непонятен.
                  а "трушные", наоборот, понимают высокоабстрагированный код и ругают спагетти-код.
                  что это? ООП головного мозга и падение профессионализма с опытом?
                  Ответить
                  • с годами становимся умнее и ленивее движемся в сторону Haskell
                    Ответить
              • Естественно, зависит, только об этом никто не говорит. Если вы не знаете, как завести автомобиль, то вы сможете и на велосипеде быстрее уехать. Но есть объективные способы измерять понятность. Такие как, например, возможное количество интерпретатций одного и того же фрагмента кода, количество потенциальных ошибок вызваных незначительными отклонениями от канонической формы и т.д.
                Например, выражение 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 в этом смысле лучше.
                Ответить
                • Why so angry?
                  Всё гораздо лучше, чем вы описали. Язык прекрасен, основная проблема - отсутствие стабильной инфраструктуры. Попробуйте установить текстовый редактор Yi (не на винде, там он вообще не соберётся, на OpenSUSE или Fedora, к примеру), и вы поймёте, о чём я. Сравните с vim/emacs. Вот, что действительно демотивирует.
                  Ответить
                  • В смысле почему? Потому что есть тенденция отождествлять непонятное с умным / правильным. А Хаскелл непонятный изза того, что у него синтаксис уродский по своей природе. Это не связано с тем, что можно сделать с помощью языка, это касается исключительно синтаксиса. И, естественно, можно привести сто тысячь примеров, но человеку, которому достаточно веры это не поможет.
                    Первое и самое устойчивое сравнение которое возникает при виде программы на Хаскеле - клинопись (я, кстати могу читать некоторые древние симитские языки, не только иврит - так что знаю из первоисточника, на что это похоже). Только там это было объяснимо потому, что писать пупым гвоздем по камню - особо не разбежишься, а когда то же самое делают в 21м веке - это идиотизм.
                    Я пробовал leksah - Yi не пробовал, но не горю желанием. Разве что если я когда-нибудь возьмусь придумывать систему магии и алхимии для ролевых игр, и мне не будет хватать пиктрограм.
                    Ответить
                  • http://postimage.org/image/bs1gu20et/
                    PS. Вот, кстати, офигенная иллюстрация тому, как ИДЕ написаная на Хаскеле понимает синтаксис языка - не сложно догадаться, что лямбды там не было, это слеши которые нужны для того, чтобы записать многострочный строковый литерал - потому что кавычек явно не хватило...
                    Ответить
                    • Что вы хотите от поделки, сделанной горсткой активистов в свободное время. Говорю же, инфраструктуры нет.
                      От синтаксиса лично у меня никакого баттхёрта нет.
                      Ответить
    • Небыдлоговнокод?
      Ответить
    • Определенно гк... Можно было так (немного злоупотребляя point-free):

      import Data.List                        ( foldl1', unfoldr )
      import Data.Tuple                       ( swap )
      
      -- reversed
      digits :: Integer -> [Integer]
      digits = unfoldr digit where digit 0 = Nothing
                                   digit n = Just $ swap (n `divMod` 10)
      
      unDigits :: [Integer] -> Integer
      unDigits = foldl1' $ \ a b -> a * 10 + fromIntegral b
      
      isLycher :: Integer -> Bool
      isLycher = all (not . palindrom) . take 50 . drop 1 . iterate next . digits
          where palindrom ds = reverse ds == ds
                next ds = digits $ unDigits ds + unDigits (reverse ds)


      // к слову есть модуль с digits / unDigits, то запарка тут чуть ниже
      Ответить
      • // чорт, fromIntegral - лишняя, но не суть
        Ответить
      • вот, когда написано хорошо, тут и разбираться не в чем
        Ответить
      • Ага, и опять палиндром во всю длину сравниваем...

        Исключительно для примера (можно было оптимизировать, чтобы строку не создавать каждый раз, но это мелочи по сравнению с ненужной проверкой половины строки:
        (defun number-palindrom-p (n)
          (let* ((s (prin1-to-string n))
        	 (len (1- (length s))))
            (dotimes (i (ash (1+ len) -1) t)
              (when (not (char= (aref s i) (aref s (- len i))))
        	(return nil)))))
        
        (defun euler-55 ()
          (let ((tester 0) (lychrels 0))
            (dotimes (i 10000) (setf tester i)
              (dotimes (j 50)
        	(when (number-palindrom-p (+ tester tester))
        	  (return))
        	(incf tester tester)
        	(when (= j 49) (incf lychrels))))
            lychrels))
        
        (euler-55)


        ПС. И lychrels, а не lychers :).
        ППС. И структура такаяже черззаборногузадерическая - нужно угадывать что происходит после чего и где функция а где аргументы.
        Ответить
        • > Ага, и опять палиндром во всю длину сравниваем...
          Premature-optimisation ;). Здесь конкретная задача, а на списках так проще.

          > lychrels
          Ага, текст по ссылке по диагонали прочитал. Подхватил ошибку из приведенного кода.
          Ответить
        • Если уж так беспокоиться об оптимизации - лучше проверять всю цепочку (пока укладывается в 10000) сразу - и вычеркивать из проверяемых (аки решето эратосфена).
          Ответить
          • Из описания проблемы по ссылке:
            we shall assume that a number is Lychrel
            Где в конкретной задаче вообще говорится об использовании списков? Ну, если проще сделать хуже - то в чем собственно оправдание? Да, как правило проще сделать хуже.
            Про решето Эратосфена - имелось в виду не проверять суммы от уже проверенных слагаемых? Если да - то, вобщем, имеет смысл, но с другой стороны не-палиндромов не так-то и много, как оказалось (меньше 400), так что это как раз не принципиально (по сравнению с потенциальными ненужными 500000 проверками).
            Ответить
            • Данная реализация использует списки, посколько конкретную задачу она решает за приемлемое время - переписать оптимальнее можно, но на списках проще, поэтому считаю оптимизацию в этом случае излишней.

              Про цепочки: для каждого числа - проверяем 50 последующих, то есть для второго проверено 49, проверив ~64 вместо 50 можно снизить число операций (вроде раз в 10).

              // Проверьте, что-то ваш код много выдает, вроде 249 должно быть.
              Ответить
              • Впрочем про цепочки не уверен. Но думаю раза 2 (оверхэд палиндрома) может быть.
                Ответить
              • (defun number-palindrom-p (n)
                  (let* ((s (prin1-to-string n))
                	 (len (1- (length s))))
                    (dotimes (i (ash (1+ len) -1) t)
                      (when (not (char= (aref s i) (aref s (- len i))))
                	(return nil)))))
                
                (defun add-kyes (table start-from)
                  (when (< start-from 10000)
                      (setf (gethash start-from table) t)
                      (add-kyes table (+ start-from start-from))))
                
                (defun euler-55 ()
                  (let ((tester 0) (lychrels 0)
                	(verified (make-hash-table)))
                    (dotimes (i 10000)
                      (if (not (gethash i verified))
                	  (progn
                	    (setf tester i)
                	    (dotimes (j 50)
                	      (when (number-palindrom-p (+ tester tester))
                		(return))
                	      (incf tester tester)
                	      (when (= j 49)
                		(add-kyes verified i)
                		(incf lychrels))))
                      (incf lychrels)))
                    lychrels))
                
                (euler-55)

                Раз уж такое дело :)

                ЗЫ. Где и кто определил приемлимое время?
                Ответить
                • > Где и кто определил приемлимое время?
                  на 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:

                  (defn num-to-digits [num]
                    (map #(- (int %) (int \0)) (str num)))
                  
                  (defn digits-to-num [digits]
                    (reduce #(+ (* 10M %1) %2) digits))
                  
                  (defn reverse-and-add [seq]
                    (num-to-digits (+ (digits-to-num seq)
                                      (digits-to-num (reverse seq)))))
                  
                  (defn palindrom? [seq]
                    (= seq (reverse seq)))
                  
                  (defn lychrel? [num]
                    (not-any? palindrom?
                         (take 50 (drop 1 (iterate reverse-and-add
                                                   (num-to-digits num))))))
                  Результат выполнения:
                  user=> (time (println (count (filter lychrel? (take 10000 (iterate inc 1))))))
                  249
                  "Elapsed time: 626.558456 msecs"

                  т.е. даже при использовании языка с "динамической" типизацией на современной машине такое решение поставленной задачи требует около полусекунды (измерял несколько раз, было и 221.99 ms). Я считаю это вполне приемлимым.
                  Ответить
                  • А можно параметры машины? Потому-что мой вариант примерно в 2.5 раза быстрее (у меня, без оптимизаций, не скомпилированый, а запущеный через swank). А всякие фиты - конечно очень полезная вещь но они не дают полной информации о происходящем.
                    При всем желании, я не вижу смысла делать лишнюю по определению проверку, даже если бы это не занимало столько времени. Это просто глупо.
                    Ответить
                    • У меня мощная машина: 8GB RAM и Core i5.
                      но на ней крутится tomcat с нехилым приложением, запущено несколько проектов IntelliJ IDEA и браузер.
                      Давайте посмотрим в ideone, думаю, там примерно одинаковые машины выполняют код (хоть конкретных характеристик я и не нашёл):
                      http://ideone.com/OPRcm
                      http://ideone.com/0dBpU
                      Жаль, что у ребят стоит clisp, он вроде только интерпретирует код, не компилирует. Не знаю, почему ваш код возвращает 9648, я в него не вникал, просто скопировал и добавил format. К сожалению, вывести время непосредственного выполнения куска кода в CL не так просто, суммарное время на компиляцию и запуск у программ примерно одинаковое.
                      Ответить
                    • > делать лишнюю по определению проверку
                      > Это просто глупо
                      наличие этой "лишней" проверки существенно упрощает алгоритм, кроме того, оно гораздо лучше сочетается с функциональной парадигмой.

                      В индустрии ПО очень много "лишних" действий (разбиение приложение на слои, всякие там шаблоны вместо свитчей), но удобство и скорость разработки программ нынче гораздо важнее потерянных миллисекунд.
                      Ответить
                      • (progn
                          (defparameter *test* (get-internal-real-time))
                          (euler-55)
                          (princ (- (get-internal-real-time) *test*)))

                        Скомилировать можно, но там этого никто не даст сделать.
                        Я распечатал все найденые палиндромы и числа из которых они были получены, проверил - все сошлось 352. Не знаю как у вас получается что-то другое.
                        Ответить
                        • мой ответ (249) правильный, projecteuler.net его принял
                          Ответить
                          • #!/usr/bin/env bash
                            
                            error_exit() {
                                echo "Palindrome $1 cannot be computed from $2" 1>2
                                exit
                            }
                            
                            test_palindrome() {
                                a=$1
                                b=$2
                                echo "testing $a"
                                for i in {0..51}
                                do
                            	if [ $a -eq $b ]; then break; fi
                            	if [ $i -eq 50 ]; then error_exit $b $1; fi
                            	a=$((a+a))
                            	echo "$i $a $b"
                                done
                            }
                            
                            cat $1 | while read line
                            do
                                test_palindrome $line
                            done

                            Как проверял :)
                            Ответить
                            • > a=$((a+a))
                              кажется, здесь что-то не так: число нужно складывать с инверсией его самого:
                              > 47 + 74 = 121
                              Ответить
                  • (defun number-palindrome-p (n)
                      (let* ((s (prin1-to-string n))
                    	 (len (1- (length s))))
                        (dotimes (i (ash (1+ len) -1) t)
                          (when (not (char= (aref s i) (aref s (- len i))))
                    	(return nil)))))
                    
                    (defun reverse-int (n)
                      (labels
                          ((iterate-reversed (a b)
                    	 (if (zerop a) b
                    	     (iterate-reversed
                    	      (floor a 10) (+ (* b 10) (mod a 10))))))
                        (iterate-reversed n 0)))
                    
                    (defun add-keys (table start-from)
                      (when (< start-from 10000)
                          (setf (gethash start-from table) t)
                          (add-keys table (+ start-from (reverse-int start-from)))))
                    
                    (defun euler-55 ()
                      (let ((tester 0) (lychrels 0)
                    	(verified (make-hash-table)))
                        (dotimes (i 10000)
                          (if (not (gethash i verified))
                    	  (progn
                    	    (setf tester i)
                    	    (dotimes (j 50)
                    	      (when (number-palindrome-p
                    		     (+ tester (reverse-int tester)))
                    		(return))
                    	      (incf tester (reverse-int tester))
                    	      (when (= j 49)
                    		(add-keys verified  i)
                    		(incf lychrels))))
                          (incf lychrels)))
                        lychrels))
                    
                    (euler-55)

                    Около 90 миллисекунд.
                    Ответить
                    • После ознакомления с главой о ленивых последовательностях (streams) в SICP, я не могу уже думать как раньше. Сейчас идея породить бесконечную ленивую последовательность кандидатов/решений и взять нужную её часть выглядит для меня гораздо более изящной и естественной, чем циклы.

                      Жаль, в CL нет поддержки ленивых последовательностей из коробки, хоть при наличии макросов их и можно реализовать в виде библиотеки.

                      P.S. я бы на вашем месте не использовал конструкцию (if (cond) (progn ...)), ведь есть более короткий и удобочитаемый (when (cond) ...), который развернётся в ту же конструкцию
                      Ответить
                      • Про это писал еще Гаролд Абелсон в "Структуре и интерпретации компьютерных программ" - про fexp в смысле. И вкратце о том, почему их лучше не использовать.

                        ЗЫ. (when (cond ...)) совсем не то же самое что (if (cond) ...) уже хотя бы потому, что это тот же if, только с одной веткой, а в коде их две :S
                        Ответить
                        • > Гаролд Абелсон в "Структуре и интерпретации компьютерных программ"
                          >> SICP (Structure and Interpretation of Computer Programs)
                          > в коде их две
                          У вас форматирование поехало, incf на одном уровне с if, а скобочки я не считал. Извиняюсь.
                          Ответить
                          • Именно, и аргументировал это тем, что не возможно однозначно рассуждать о функциях не вычисляющих значения, которые они возвращают.
                            Ответить
                            • Не помню там особой критики с предложением лучше не использовать, помню лишь здравые размышления о том, что ленивые потоки не являются серебряной пулей для решения проблем состояния, ибо непонятно, как мёржить потоки друг с другом в мутабельном мире (http://tinyurl.com/3wtsrok конец).
                              Ответить
                              • А это я с Кентом Питманом перепутал, но суть аргумента та же - отсутствие гарантированой возможности оптимизации и анализа.
                                Ответить
                • > add-kyes
                  занятная очепятка add-xyes
                  Ответить
                  • transposed-letters priming effect только наоборот.
                    Ответить
              • > Проверьте, что-то ваш код много выдает, вроде 249 должно быть.
                Может зависеть от того, что подразумевается под палиндромом. Только wxxw или так же и wvxvw.
                Ответить
          • Упс, прошу прощения, наоборот, палиндромов всего около чуть меньше 400 :) Но даже при таком раскладе, лишних проверок на порядок больше изза того, что проверяется лишняя половина, чем изза того, что не проверяются уже проверенные сумы.
            Ответить

    Добавить комментарий