1. Haskell / Говнокод #21424

    −20

    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
    30. 30
    31. 31
    32. 32
    -- GUESS THE NAME OF "algorithmX":
import qualified Data.List as DL
infinity = 1/0
adjacencyMatrix =
  [[0,3,1,6,0,0],
   [3,0,5,0,3,0],
   [1,5,0,5,6,4],
   [6,0,5,0,0,2],
   [0,3,6,0,0,6],
   [0,0,4,2,6,0]] :: [[Double]]

replaceZerosWithInfinity matrix =
  map (map (\e -> if e == 0 then infinity else e)) matrix

type Edge = (Int,Int,Double)

algorithmX adjacencyMatrix initialVertex = (minimumTotalCost,minimumEdges)
  where
    third (_,_,t) = t
    minimumTotalCost = sum $ map third minimumEdges
    (_,minimumEdges) = foldl iterate ([initialVertex],[]) [1..n-1]
    matrix = replaceZerosWithInfinity adjacencyMatrix
    n = length matrix
    getIndexes visited =
      filter (\(i,j) -> not $ elem j visited) [(i,j) | i <- visited, j <- [0..n-1]]
    iterate :: ([Int],[Edge]) -> Int -> ([Int],[Edge])
    iterate (visited,edges) iteration = (newVisited:visited,minimumEdge:edges)
      where
        (_,newVisited,_) = minimumEdge 
        minimumEdge = DL.minimumBy compareEdges $ map newEdge (getIndexes visited)
        newEdge (i,j) = (i,j,matrix !! i !! j)
        compareEdges e0 e1 = compare (third e0) (third e1)

    WARN: лаба с фейспука

    Запостил: roman-kashitsyn, 12 Октября 2016

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

    • ava kegdan 12.10.2016 15:25 # 0

      >> map (\e -> if e == 0 then infinity else e)
      удивило, что в прилюде из коробки нет replace
      Ответить

    • ava kegdan 12.10.2016 15:31 # +1

      ну и 16-строчная функция для хаски - содом и гоммора
      Ответить

    • ava kegdan 12.10.2016 15:53 # 0 

      >> getIndexes visited =
      filter (\(i,j) -> not $ elem j visited) [(i,j) | i <- visited, j <- [0..n-1]]

getIndexes = liftM2 (liftM2 (,)) id ([0..n-1]\\)
      Ответить

      • ava roman-kashitsyn 12.10.2016 15:58 # 0

        Алгоритм-то угадал?
        Ответить

        • ava kegdan 12.10.2016 16:19 # 0

          Неужели Дейкстра так распидорасило?
          Вникать лень
          Ответить

          • ava roman-kashitsyn 12.10.2016 16:22 # 0

            prim's mst
            Я предложил юзать kruskal's mst
            mst :: Graph -> [Edge]
mst g = foldEdges (ufEmpty, 0) $ sortBy (compare `on` edgeWeight) $ listEdges g
  where n = numVertices g
	foldEdges ( _, _) [] = []
	foldEdges state@(uf, numEdges) (e@(from, to, _):es) =
	  if numEdges == n - 1
	  then []
	  else if ufConnected uf from to
	       then foldEdges state es
	       else e : foldEdges (ufJoin uf from to, numEdges + 1) es
            Ответить

            • ava kegdan 12.10.2016 16:32 # 0

              действительно, остов находит

              А таки можно не предлагать таких больших функций?
              Ответить

            • ava kegdan 12.10.2016 16:35 # 0

              и огласите весь код, пожалуйста, с декларацией уфов
              Ответить

              • ava roman-kashitsyn 12.10.2016 16:40 # 0

                > огласите весь код

                Написано на скучном митинге, наверняка можно многое улучшить. Запилил свой UF и incidence list:
                https://gist.github.com/roman-kashitsyn/b2c8989c4d8c8a5a200537399d433412

                > А таки можно не предлагать таких больших функций?

                Сделай короче (не в ущерб понятности), жду пулл-реквест.
                Ответить

                • ava kegdan 12.10.2016 16:56 # −1

                  не сегодня, но на днях.

                  Эх, как же хорошо окунуться в хаскель после ебаного ксамарина...
                  Ответить

                • ava kegdan 12.10.2016 18:30 # 0

                  graph =: 1 2 4; 0 1 2 ; 1 2 8 ; 1 2 2
                  a=:(/:{:@>)graph
                  kruskal =: a#~>&0@+/"1@((3 2)&$)@(<#)@((i.&#@]i.~]#~#>])@]i.i.@#)@,(}:@>)a

                  но там где то что то по дороге наебнулось и кароч не работает
                  хер отдебажишь
                  Ответить

                  • ava kegdan 12.10.2016 18:39 # +2

                    graph =: 1 2 4; 0 1 2 ; 1 2 8 ; 1 2 2
                    a=:(/:{:@>)graph
                    kruskal=:a#~>&0@+/"1@($~(,&2)@-:@#)@(<#)@((i.&#@]i.~]#~#>])@]i.i.@#)@,(}:@>)a

                    таки отладил. Юледь, в 100раз проще, чем бороться с багами ксамарина
                    Ответить

                    • ava roman-kashitsyn 19.10.2016 20:24 # +1

                      Это какой-то неправильный haskell
                      Ответить

                      • ava barop 19.10.2016 21:51 # −15

                        показать все, что скрытоОбнаружен вирус!
                        Сканер памяти обнаружил вредоносную программу! Очень опасно работать на компьютере, в памяти которого активен вирус. Рекомендуется назначить загрузочное сканирование.
                        Ответить

                        • ava barop 20.10.2016 02:49 # −15

                          показать все, что скрытоО том, что останки Гигантов имеют Русскую ДНК, и поэтому скрываются и уничтожаются Западными неандертальцами от науки, Грэм Хэнкок даже и не догадывается. О том, что Гиганты никуда не исчезли, а просто постепенно стали меньше ростом, ему тоже не вдомёк. Как и то, что та глобальная война, которую он списывает на комету, была войной с применением гравитационного оружия (гравитационной бомбы). Странно слышать от Грэма Хэнкока слова о любви всех народов, тогда как его позиция в альтернативной археологии и есть основная движущая сила геноцида против Русов и страны Рош / Россия – против ПЛЕМЕНИ ОГНЕННОГО СОКОЛА РА / РАРОГА.

                          Поэтому намёки Грэма Хэнкока о том, что он передаёт нам наследие наших предков, – это издёвка. Почему Грэм Хэнкок не возмущается, что Сионо-Нацисты Украины сейчас утюжат Градами мегалитические пирамиды в Луганске?
                          Ответить

      • ava roman-kashitsyn 13.10.2016 13:08 # 0

        > getIndexes

        Вообще говоря, в этой функции как раз самое смешное. Причём даже не в реализации (твоя с liftM2 мне нравится ещё меньше, кстати), а в идее. Из-за того, что код перебирает O(n^2) ребёр на каждой из n-1 итераций, алгоритм становится O(n^3), хотя мог бы быть O(e * log n).

        Ну и самый цимус: если подать на вход несвязный граф, алгоритм зарепортит бесконечную стоимость и перечислит рёбра бесконечного веса.
        Ответить

        • ava kegdan 13.10.2016 13:55 # 0

          Ну сие понятно.

          А чем тебе лифт лифтов неугодил?
          Ответить

      • ava CHayT 13.10.2016 14:55 # +3

        > Indexes
        Indices!
        Ответить

        • ava inkanus-gray 13.10.2016 15:34 # +2

          Один мой препод ещё заменял “modules” на “moduli”. А некоторые ещё заменяют “formulas” на “formulae”, чтобы выпендриться знанием латыни.

          https://en.wiktionary.org/wiki/moduli
          https://en.wiktionary.org/wiki/formulae
          Ответить

    • ava kegdan 12.10.2016 16:07 # +3

      >> compare (third e0) (third e1)
      ну это уже блядство

      (compare `on` third) e0 e1
      Ответить

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