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

    +126

    1. 001
    2. 002
    3. 003
    4. 004
    5. 005
    6. 006
    7. 007
    8. 008
    9. 009
    10. 010
    11. 011
    12. 012
    13. 013
    14. 014
    15. 015
    16. 016
    17. 017
    18. 018
    19. 019
    20. 020
    21. 021
    22. 022
    23. 023
    24. 024
    25. 025
    26. 026
    27. 027
    28. 028
    29. 029
    30. 030
    31. 031
    32. 032
    33. 033
    34. 034
    35. 035
    36. 036
    37. 037
    38. 038
    39. 039
    40. 040
    41. 041
    42. 042
    43. 043
    44. 044
    45. 045
    46. 046
    47. 047
    48. 048
    49. 049
    50. 050
    51. 051
    52. 052
    53. 053
    54. 054
    55. 055
    56. 056
    57. 057
    58. 058
    59. 059
    60. 060
    61. 061
    62. 062
    63. 063
    64. 064
    65. 065
    66. 066
    67. 067
    68. 068
    69. 069
    70. 070
    71. 071
    72. 072
    73. 073
    74. 074
    75. 075
    76. 076
    77. 077
    78. 078
    79. 079
    80. 080
    81. 081
    82. 082
    83. 083
    84. 084
    85. 085
    86. 086
    87. 087
    88. 088
    89. 089
    90. 090
    91. 091
    92. 092
    93. 093
    94. 094
    95. 095
    96. 096
    97. 097
    98. 098
    99. 099
    100. 100
    -- Подключим нужные библиотеки
    -- http://codepad.org/
    -- import Control.Exception
    import Data.Array
    import Data.Ord
    import Data.List
    import System.Random
    import Control.Arrow
    import Text.Printf
    
    --Тестовая карта. Можно менять.
    testMapList2D = [        
    		"        ",
    		" X X    ",
    		" X XX XX",
    		"XX X    ",
    		"   X X  ",
    		"  XX    ",
    		" X      ",
    		"   X    "]
    
    --Топографические знаки:
    void = ' '
    wall = 'X'
    step = '*'
    
    -- Не удобно без |> из F#. Няшная же функция. Чего её вдруг нет? Не выдержал, добавил.
    infixl 0 $>
    ($>) = flip ($)
    
    -- Получаем карту произвольного размера WxH. Генератор простейший, но впрочем не годен для генерации красивых лабиринтов.
    -- Можно использовать для измерения производительности.
    generateList2D wh wallFactor seed = 
    	(randomRs (0, 1000) (mkStdGen seed) ::[Float]) $>
    	map (\randNumber -> if randNumber/1000 > wallFactor then void else wall ) >>>
    	listToList2D wh
    
    -- Вспомогательные функции
    listToList2D (w, h) = 
    	take (w*h) >>>
    	iterate (drop w) >>>
    	take h >>>
    	map (take w)
    widthHeightOfList2D l = (length $ head l, length l)
    makeArray2D (w, h) values = listArray ((0,0), (h-1, w-1)) values
    list2DToArray2D l = makeArray2D (widthHeightOfList2D l) $ concat l
    widthHeightOfArray2D a = let (mx, my) = snd $ bounds a in (mx+1, my+1)
    putIntoArray2D valueForInsertion a positionsForInsertion = a // (zip positionsForInsertion $ repeat valueForInsertion)
    mapPathAdd map_ path = putIntoArray2D step map_ path
    generateMap wh wallFactor seed = list2DToArray2D $ generateList2D wh wallFactor seed
    outputArray2D a =
    	elems a $>
    	listToList2D (widthHeightOfArray2D a) >>>
    	mapM print -- В самом конце в последней строке функция outputArray2D стала грязной. Поплачем над её участью и идём дальше.
    
    -- Приступим к функции поиска пути findPath.
    -- UB findPath при использовании не прямоугольной карты. 
    -- UB findPath для карт меньше 2x2 точек (из-за реализации getNearestPoint) (из-за лени добавить одну короткую строчку с учетом того что карт таких не бывает обычно).
    -- Также использование неподходящих в карте топографичексих знаков не контролируется.
    -- Тесты не писал.
    {-
    	Я честно пытался использовать assert в чистом коде, но возможно из-за лени он работает через раз.
    	В коде выглдяит отвратительно.
    	Самое не приятное что он не сообщает ничего подробнее чем то, что произошл ассерт. Не номер строки, не описание ошибки, не выражение. Видимо чисто недоделанная стандартная библиотека.
    	Пытался написать свой ассерт, чтобы хоть какое-то сообщение выдавал. Ну видимо руки кривые сделали ещё ассерт хуже, тк вообще ни разу проверил. Видимо нужны всякие бенги секи и прочее для форсирования ленивых вычислений. Так что даже не стал пытаться.
    -}
    -- Функция findPath все ещё чиста как слеза младенца.
    
    findPath map_ (sx, sy) (dx, dy) = getPath $ waveField (-1) initialFieldAndYetNotFindedDestinationPoint (dx, dy)
    	where
    		wh = widthHeightOfArray2D map_
    		(w, h) = wh
    		fieldMax = w*h+1
    		initialField = makeArray2D wh $ repeat fieldMax
    		initialFieldAndYetNotFindedDestinationPoint = (initialField, False)
    		posibleSteps (cx, cy) = [(cx+1, cy), (cx-1, cy), (cx, cy+1), (cx, cy-1)]
    		isInMapRange (cx, cy) = cx>=0 && cy>=0 && cx<w && cy<h
    		getNearestPoint field = (minimumBy (comparing (field!))) . (filter isInMapRange) . posibleSteps
    		getPath (field, True) = (takeWhile (/=(dx,dy)) $ iterate (getNearestPoint field) (sx,sy)) ++ [(dx, dy)]
    		getPath (field, False) = []
    		waveField waveDistance waveFieldWithFindResult (cx, cy)
    			| not $ isInMapRange (cx, cy)                                = waveFieldWithFindResult
    			| map_!(cx, cy) == wall                                      = waveFieldWithFindResult
    			| ((fst waveFieldWithFindResult) ! (cx, cy)) <= waveDistance = waveFieldWithFindResult
    			| (cx, cy)==(sx, sy)                                         = ((fst waveFieldWithFindResult) // [((cx, cy), waveDistance+1)], True)
    			| otherwise                                                  =
    				let waveFieldWithFindResult1 = ((fst waveFieldWithFindResult) // [((cx, cy), waveDistance+1)], snd waveFieldWithFindResult) in
    				foldl (waveField (waveDistance+1)) waveFieldWithFindResult1 $ posibleSteps (cx, cy)
    
    -- Копипасте-бой
    pathView map_ mapName sourcePoint destinationPoint = do
    	let mapInfo = mapName ++ " with size " ++ (show $ widthHeightOfArray2D map_) ++ ":"
    	print mapInfo
    	let sd = (sourcePoint, destinationPoint)
    	printf "Path for %s: " (show sd)
    	let path = findPath map_ (fst sd) (snd sd)  
    	print path
    	let mapWithPath = mapPathAdd map_ path
    	print "Map with path: "
    	outputArray2D mapWithPath

    putStr "\n"

    -- Точка входа
    main = do
    let map1 = list2DToArray2D testMapList2D
    pathView map1 "MapFromCode" (0,0) (5,5)
    let mapGenerated1 = generateMap (4,4) 0.2 90
    pathView mapGenerated1 "MapGenerated1" (0,2) (3,3)
    let mapGenerated3 = generateMap (5,5) 0.1 15
    pathView mapGenerated3 "MapGenerated3" (0,0) (2,2)

    Запостил: laMer007, 11 Февраля 2014

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

    • Специальная олимпиада №1
      Жаль нет раздела для Хаскеля.
      Как всегда подобные олимпиады проводим просто для отдыха.
      Просто покажите код, который работает для заявленных режимов функционирования. Демонстрация в любом онлайн компиляторе (для тех кто не знает где его найти - спросите в теме). Желательно красивый и короткий код. Скорость не важна, но если кому интересно - можно позже её измерить. Язык любой. Алгоритм любой.

      Задание:
      Написать код поиска пути на двухмерной карте. Карту можно красиво представить в коде и\или сгенерировать. Карта состоит из пустот и стен.
      Красиво показать карту и путь на ней.
      Ходить можно по вертикали и горизонтали.
      Если захочется, чтобы алгоритм умел прокладывать путь по диагонали, то путь не должен проходить через рядом стоящие стены, например ниже ошибка, тк между стенами прохода нет:
      X*.
      *XX
      *..

      Если вы написали неточный алгоритм поиска пути, то не забудьте указать это. Впрочем желательно точный алгоритм использовать.
      На тот случай, если кто-то хочет, чтобы его код мог учувствовать в измерении производительности, которая возможно состоится: картогенератор должен уметь генерировать карты произвольных размеров.

      Выбрал алгоритм не очень подходящий для чистого кода. Код по большей части чист. В том числе сам алгоритм поиска пути. В коде много комментариев и код относительно не плохо декомпозирован. Конечно избавившись от этого - программу можно было бы значительно подсократить.
      Алгоритм простейший и не оптимальный. Поиск в глубину, волновой алгоритм.

      http://codepad.org/6lGy7TPX
      Ответить
      • Удалено администрацией.
        Ответить
      • в предположении, что вход корректен
        import Control.Monad
        import Control.Monad.ST (ST)
        import Data.Array.ST hiding (unsafeFreeze, unsafeThaw)
        import Data.Array.Unboxed
        import Data.Array.Unsafe
        import Data.Function (on)
        import Data.List
        
        
        getPath :: UArray (Int, Int) Char -> (Int, Int) -> (Int, Int) -> UArray (Int, Int) Char
        getPath laby xy_beg xy_end = runSTUArray $ do
          steps  <- newArray (bounds laby) 0 :: ST s (STUArray s (Int, Int) Int)
          search steps 1 [xy_beg]
          steps' <- unsafeFreeze steps
          laby'  <- unsafeThaw laby
          backtrack laby' (steps' :: UArray (Int, Int) Int) xy_end
          return laby'
        
          where
            search steps n xys = unless (null xys) $ do
              forM_ xys $ \xy -> writeArray steps xy n
              xys' <- filterM firstVisit . filter canPass $ concatMap moves xys
              search steps (n + 1) xys'
              where
                firstVisit = fmap (0 ==) . readArray steps
                canPass xy = laby ! xy == ' '
        
            backtrack laby' steps' xy = do
              writeArray laby' xy '*'
              unless (n == 1) $ backtrack laby' steps' xy'
              where
                n = steps' ! xy
                Just xy' = find ((n - 1 ==) . (steps' !)) $ moves xy
        
            -- @x@ for rows and @y@ for columns
            moves (x, y) = [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]
        
        
        fromList :: [[Char]] -> UArray (Int, Int) Char
        fromList laby = listArray ((0, 0), (height + 1, width + 1)) .
                            concatMap (\row -> "X" ++ row ++ "X") $
                                [border] ++ laby ++ [border]
          where
            width  = length $ head laby
            height = length laby
            border = replicate width 'X'
        
        
        labySimple :: [[Char]]
        labySimple =
            [ "        "
            , " X X    "
            , " X XX XX"
            , "XX X    "
            , "   X X  "
            , "  XX    "
            , " X      "
            , "   X    "
            ]
        
        main :: IO ()
        main = mapM_ (putStrLn . map snd) .
                   groupBy ((==) `on` (fst . fst)) .
                       assocs $ getPath (fromList labySimple) (1, 1) (6, 6)
        Ответить
        • Код работает. Получилось довольно кратко. Идея с расширением стен весьма красива. Спасибо.
          http://ideone.com/mxbgNl
          Не пользовался монадами кроме как для вывода результата.
          Я тоже пытался использовать Data.Array.Unboxed, но по какой-то непонятной мне причине код с UArray не компилировался. Хотя если заменить его на на обычный чистый Array, то всё работало. Не знаете в чем может быть дело? Кстати разница между Array и UArray в том, что в Array лежат ссылки на элементы, а не сами элементы?
          А зачем использовали unsafeFreeze unsafeThaw? Чтобы то что работает в монадах начало работать и в чистом коде и наоборот? unsafeFreeze unsafeThaw позволяют менять память массивов в чистом коде для оптимизации, чтобы каждый раз не происходило копирования?
          Ответить
          • С простым unbox не должно быть особых проблем, не видя код, могу лишь ванговать, что тип элемента был неограничен - Integer, например.
            Да, сами элементы.
            unsafeFreeze - чтобы не копировать steeps: дальше steps не используеется => безопасно.
            В частности: runST (... ; unsafeFreze arr) <=> runSTUArray (... ; return arr) всегда безопасн.
            unsafeThaw - то же для laby, здесь нюанс - дальше нельзя читать его элементы, но getPath (fromList ..) - очевидно безопасно, лучше было бы просто thaw или обозначить getPathUnsafe, либо получать аргумент [[Char]].
            Ответить
            • > не видя код
              Код выше, в начале топика. Заменить везде Array на UArray и получим ошибку компиляции. В чем дело - не понял. UArray использовался только для чаров и интов, так что проблем как я думаю быть не должно. Или все дело в том, что по умолчанию используется Integer (Неограниченный Integer) вместо короткого Int и потому это ссылочный тип и для него появляется ошибка? Как можно исправить? Везде вручную проставить Int вместо типа Integer или a?
              Ответить
              • В данном случае достаточно будет сигнатура makeArray2D: http://codepad.org/zEaQA7RC .
                Но всплывают timeout-ы, хотя может проблемы codepad (у них вроде hugs).
                Ответить
                • Просто вот это? Странно, вроде пытался делать...
                  import Data.Array.Unboxed
                  makeArray2D :: IArray UArray a => (Int, Int) -> [a] -> UArray (Int, Int) a
                  Ответить
                  • Значит, были отличия: например fieldMax был фиксирован (не связывался с w и h, не получал тип Int), или даже сигнатура была (Ix i, ...) -> (i,i) -> ... , но без (Num i, ...) и в hugs получалось ни рыба, ни мясо.
                    Ответить
                    • В целом Hugs хуже GHC? Например менее оптимизировнный? С Haskell Platform GHC идёт по дефолту? Я просто на кодепад пошел из-за того, что на других онлайнкомпиляторах не было System.Random. Но в целом заметил, что на кодепаде информация об ошибках компиляции менее информативная. Я подумал наверное там какой-то устаревший GHC стоит.
                      Ответить
                      • Hugs не применим для чего-то серьезного:
                        1) лишь haskell-98
                        2) много ключевых библиотек прибито к ghc, сложно оценить какая часть пакетов с hackage заведется, но не думаю, что хотя бы половина
                        3) это _интерпретатор_

                        > не было System.Random
                        Есть еще fpcomplete.com , правда регистрация и больше месяца за денежку.

                        Берешь пример из wiki "Extensible records" и проверяешь: http://codepad.org/272qH9mG, в идеоне такое не заведется
                        Ответить
              • Ну или отдельно для Int (в initialFields) и Char (list2DToArray2D) http://codepad.org/8WffhkKc
                Ответить
    • На раздевание, али на деньги?
      Ответить
    • показать все, что скрытоЯ НАДЕВАЮ БОБРА НА СВОЙ ФАЛЛОС.
      Ответить
    • Это ж задача с хакерранк, не? У меня где-то есть код на Лиспе, но влом искать + у них не установлен Квиклисп / АСДФ не доступен, а без этого влом что-то делать.
      Ответить
      • Ну тут можно на любом онлайн компиляторе. Ну или вообще без онлайн компилятора, если найти так сложно рабочий лисп. Хотя я думал он довольно популярен.
        Ответить
    • показать все, что скрытоЯ чувствую, как тёплый шерстяной бобёр СТОНЕТ, разрываемый моим РАДИОАКТИВНЫМ фаллосом.
      Ответить
    • показать все, что скрытоНе забываем анально минусовать "guest`a", пиздомужего выблядка...
      Ответить
    • показать все, что скрытоАдминистратор этого сайта - гандоноид, если до сих пор не может после веселухи 2011-го года разрешить постить коды сразу после регистрации. Хуле я должен ждать ещё неделю? Такого нет ни на одном сайте - неделю ждать возможности комментирования, две недели - возможности постинга.
      Ответить
      • показать все, что скрыто>>Хуле я должен ждать ещё неделю?
        Это нужно для воспитания терпения участника.

        >>Такого нет ни на одном сайте - неделю ждать возможности комментирования, две недели - возможности постинга
        зато тут нет модераторов и админов- количество флуда регулируется не количеством разгаданных каптур (хотя и этим тоже) но в большей степени совестью флудера.
        Ответить
        • показать все, что скрытоНа "Google ВиО" ещё недавно был самый цимес для флуда и троллинга. Но за четыре года этот сайт был мною опущен до уровня помойки, хотя оно ещё четыре года назад было салоном лучших умов Интернета.
          Я заметил в себе необычайное свойство - я медленно убиваю любой сайт, на котором задерживаюсь.
          Ответить
          • показать все, что скрытоДа, лишней скромностю ты не обременен, как я посмотрю.
            Но у меня есть иная трактовка: ты забредаешь на загнивающие сайты, и лишь способствуешь дальнейшей деструкции личности тамошних обитателей, что в конечном итоге неизбежно приводит к коллапсу.
            Ответить
            • Это явления осмоса.
              Ответить
            • Есть и еще одна трактовка - Google ВиО и прочие сайты не изменились, изменилось только отношение к ним конардо.
              Ответить
              • показать все, что скрытоНа хуй метнись.
                Ответить
                • питух - он и в африке питух
                  Ответить
                  • Как гласит народная мудрость: "не тронь говно, оно и вонять не будет".

                    Не обращай на него внимания, ни к чему эта агрессия. Если сильно достает - включи фильтр по никам, тут такой выкладывали.
                    Ответить
                    • да не, я просто афиширую, что я его по ip вычислил
                      Ответить
                    • >>>"не тронь говно, оно и вонять не будет"

                      А действительно - хуле я к тебе приебался?...
                      Ответить
                      • Плюсанул. Первый годный вброс от тебя. Продолжай в том же духе и через пару-тройку лет вырастешь в настоящего тролля ;)
                        Ответить
    • показать все, что скрытоИ как вы думаете - въебал ли я минус этому посту или нет?
      Ответить
    • let mapInfo = mapName ++ " with size " ++ (show $ widthHeightOfArray2D map_) ++ ":"
      print mapInfo
      Кстати, а почему бы это не записать как printf? Правда почему-то не компилируется.
      Ответить
    • //http://coliru.stacked-crooked.com/
      #include <iostream>
      #include <vector>
      #include <list>
      #include <algorithm>
      #include <functional>
      #include <random>
      #include <boost/range/algorithm.hpp>
      #include <boost/range/adaptors.hpp>
      #include <boost/range/algorithm_ext/insert.hpp>
      /*#include <boost/range/algorithm/transform.hpp>
      #include <boost/range/algorithm/copy.hpp>
      #include <boost/range/algorithm/generate.hpp>
      #include <boost/range/algorithm_ext/insert.hpp>
      #include <boost/range/algorithm/min_element.hpp> 
      #include <boost/range/adaptor/filtered.hpp>*/
      using namespace std;
      using namespace boost;
      typedef string CodeMapDimension;
      typedef vector<CodeMapDimension> CodeMap;
      CodeMap testMap_ = {
          "        ",
          " X X    ",
          " X XX XX",
          "XX X    ",
          "   X X  ",
          "  XX    ",
          " X      ",
          "   X    "};
      
      typedef vector<char> MapDimension;
      typedef vector<int> FieldDimension;
      typedef vector<MapDimension> Map;
      typedef vector<FieldDimension> Field;
      struct Point{
          int x, y;
          friend bool operator==(const Point& l, const Point& r){
              return l.x==r.x && l.y==r.y;
          }
          friend Point operator+(const Point& l, const Point& r){
              return {l.x+r.x, l.y+r.y};
          }
          friend ostream& operator<<(ostream& stream, const Point& point){
              stream<<"("<<point.x<<", "<<point.y<<")";
              return stream;
          }
          Point& operator=(const Point& p) = default;
      };
      typedef list<Point> Path;
      Ответить
      • const char wall  = 'X';
        const char void_ = ' ';
        const char step  = '*'; 
        
        //UB на не квадратных картах.
        Map toMap(const CodeMap& map){
            Map r(map.size());
            transform(map, r.begin(),
                [](const CodeMapDimension& line){
                    MapDimension r(line.size());
                    copy(line, r.begin());
                    return r;
                });
            return r;
            /* 
                    *vs* 
            Map ro(map.size());
            size_t i=0;//Можно чисто через итераторы, но длинее и я так всегда делаю, поэтому не интересно. 
            for(const CodeMapDimension& line: map)
            {
                MapDimension& r(ro[i++]);
                r.resize(line.size());
                size_t j=0;
                for(const char topographic: line)
                    r[j++]=topographic;
            }
            return ro;*/            
        }
        Ответить
        • Map generateMap(const int w, const int h, const double wallFactor, const int seed){
              default_random_engine engine_generator(seed);
              uniform_int_distribution<> distribution(0,1000);
              auto rand = bind(distribution, engine_generator);
              const auto generator = [&rand, wallFactor](){if(rand()/1000.0<wallFactor) return wall; else return void_;};
              Map r(h);
              return generate(r, [w, generator](){
                  MapDimension r(w);
                  return generate(r, generator);
              });
          }
          
          void outputMap(const Map& map){
              cout<<endl;
          	if(map.empty())
          	{
          		cout<<"o_O"<<endl;
          		return;
          	}	
              ostream_iterator<char> out(cout);
              ::std::fill_n(out, map[0].size()+2, '_');
              cout<<endl;
              for(const MapDimension& line: map){
                  cout<<"|";
                  copy(line, out);
                  cout<<"|"<<endl;
              };
              ::std::fill_n(out, map[0].size()+2, '-');
              cout<<endl;
          }
          
          Point mapSize(const Map& map)
          {
          	if(map.empty())
          		return {0, 0};
          	return {(int)map[0].size(), (int)map.size()};
          }
          
          template<class T>
          typename T::value_type::value_type& atPoint(T& twoDimensionContainer, const Point& point){
              return twoDimensionContainer[point.y][point.x];
          }
          
          template<class T>
          const typename T::value_type::value_type& atPoint(const T& twoDimensionContainer, const Point& point){
              return twoDimensionContainer[point.y][point.x];
          }
          Ответить
          • Map fillPathOnMap(const Map& map, const Path& path){
                Map r(map.size());
                copy(map, r.begin());
                for(const Point& point: path)
                    atPoint(r, point)=step;
                return r;
            }
            
            bool inMapRange(const Map& map, const Point& point){
                if(map.empty())
                    return false;
                return point.x>=0 && point.y>=0 && point.x<(int)map[0].size() && point.y<(int)map.size();
            }
            
            bool isPassably(const Map& map, const Point& point){
                return inMapRange(map, point) && atPoint(map, point)!=wall;
            }
            
            void outputPath(const Path& path){
                copy(path, ostream_iterator<Point>(cout));
            }
            
            Field fieldConstruct(const Map& map){
                const size_t
                        w = map[0].size(),
                        h = map.size(),
                        maxField = w*h+1;
                return Field(h, FieldDimension(w, maxField));
            }
            
            bool stepIsNotFolly(const Map& map, const Field& field, const int waveDistance, const Point& point){
                return isPassably(map, point) && waveDistance<atPoint(field, point);
            }
            
            Path nearPoints(const Point& point)
            {
                Path path = {point + Point({-1,0}), point + Point({1,0}), point + Point({0,-1}), point + Point({0,1})};
                return path;
            }
            
            Path nextPoints(const Map& map, const Field& field, const int waveDistance, const Point& point)
            {
                auto path = nearPoints(point);
                auto r = adaptors::filter(path, bind(stepIsNotFolly, map, field, waveDistance, placeholders::_1)); 
                return Path(r.begin(), r.end());
            }
            Ответить
            • Path nextPointsForPathTraversing(const Map& map, const Point& point)
              {
                  auto path = nearPoints(point);
                  auto r = adaptors::filter(path, bind(inMapRange, map, placeholders::_1)); 
                  return Path(r.begin(), r.end());
              }
              
              Path fillPath(const Map& map, const Field& field, const Point& source, const Point& destination)
              {
              	auto currentPoint = source;
              	Path path = {source};
              	while(!(currentPoint==destination))
                  {   
                      const auto nextPoints = nextPointsForPathTraversing(map, currentPoint);
              		path.push_back(currentPoint = *min_element(nextPoints, 
              			[&field](const Point& l, const Point& r){
              				return atPoint(field, l)<atPoint(field, r);
              			}));
                  }
              	return path;
              }
              
              Path pathFind(const Map& map, const Point& source, const Point& destination){
              	if(map.empty())
              		return Path();
                  if(!((inMapRange(map, source))&&(inMapRange(map, destination))))
                      return Path();
                  if(!isPassably(map, destination))
                      return Path();
                  Path waveFront = {destination};
              	auto field = fieldConstruct(map);
              	int waveDistance = 0;
              	const auto waveFrontEnd = waveFront.cend();
              	auto currentPoint = waveFront.begin();
              	while(currentPoint!=waveFrontEnd)
              	{
              		while(currentPoint!=waveFrontEnd)
              		{
              			atPoint(field, *currentPoint)=waveDistance;
              			if(source==*currentPoint)
              				return fillPath(map, field, source, destination);
              			insert(waveFront, currentPoint, nextPoints(map, field, waveDistance, *currentPoint));
              			waveFront.erase(currentPoint++);
              		}
              		currentPoint = waveFront.begin();
              		++waveDistance;
              	}
              	return Path();
              }
              Ответить
              • void viewPath(const Map& map, const string& mapName, const Point& source, const Point& destination)
                {
                	cout<<"Map "<<mapName<<" with size "<<mapSize(map)<<":";
                	outputMap(map);
                	cout<<"Path from "<<source<<" to "<<destination<<":"<<endl;
                	auto path = pathFind(map, source, destination);
                    outputPath(path);
                	cout<<endl<<"Map with path: ";
                	auto mapWithPath = fillPathOnMap(map, path);
                	outputMap(mapWithPath);
                	cout<<endl<<endl<<endl;
                }
                
                int main()
                {
                    const auto testMap = toMap(testMap_);
                    viewPath(testMap, "Code map", {0,0}, {5,5});
                    const auto map1 = generateMap(10,16, 0.2, 0);
                    viewPath(map1, "Generated map1", {2,2},{8,8});
                	const auto map2 = generateMap(16,10, 0.3, 50);
                    viewPath(map2, "Generated map2", {2,2},{14,8});
                }
                Ответить
                • http://coliru.stacked-crooked.com/a/e6cf41ee01c6c0d9
                  Решил, раз сравниваю выразительность языков, то напишу ещё на каком-нибудь.
                  Хех, на крестах программа заработала с первого запуска, в отличии от хаскеля. Волновой алгоритм, поиск в ширину. Как и ожидалось кода немного побольше. Оптимальность должна быть повыше хаскелевой. Тесты не писал, ассерты тоже не вставлял. Алгоритм немного сложнее, но в хаскеле было не на много бы больше, чем есть сейчас. На пару строк побольше. Декомпозиция примерно на уровне хаскелевой проги. Даже названия функций схожи некоторых.
                  Ответить
    • И так первый "оппонент":
      #include <climits>
      #include <string>
      #include <iostream>
      #include <vector>
      
      const int empty = 0;
      const int wall = -1;
      const int path = -2;
      
      class Map
      {
        std::vector<int> data;
      public:
        int width, height;
        int &at( int x, int y ) { return data[ height * x  + y ]; };
        int test( int x, int y )
        {
          if ( (x < 0) || (y < 0) || (x >= width) || (y >= height) )
            return INT_MAX;
          return at( x, y ) > 0 ? at( x, y ) : INT_MAX;
        };
        Map( int x, int y, int filler ): width( x ), height( y ), data( x * y, filler ) {};
        void show()
        {
          for ( int i = 0; i < width; i++ )
          {
            for ( int j = 0; j < width; j++ )
            {
              int v = at( i, j );
              char c = '.';
              if ( v == wall ) c = 'X';
              if ( v == path ) c = '*';
              std::cout << c;
            };
            std::cout << "\n";
          };
        };
      };
      
      const char *defmap =
          "        "
          " X X    "
          " X XX XX"
          "XX X    "
          "   X X  "
          "  XX    "
          " X      "
          "   X    ";
      Ответить
      • Map *createFromDefMap()
        {
           Map *ret = new Map( 8, 8, empty );
           const char *pos = defmap;
           for ( int i = 0; i < 8; i++ )
              for ( int j = 0; j < 8; j++ )
                 if ( *pos++ == 'X' )
                   ret->at( i, j ) = wall;
          return ret;
        };
        
        void findPath( Map *map, int dx, int dy, int sx, int sy )
        {
          map->at( sx, sy ) = 1; // start of wave
          bool not_done = true;
          while ( not_done )
          {
             not_done = false;
             for ( int i = 0; i < map->width; i++ )
               for ( int j = 0; j < map->height; j++ )
               {
                 int &v = map->at( i, j );
                 if ( v == empty )
                 {
                   int t = std::min( INT_MAX, map->test( i + 1, j ) );
                   t = std::min( t, map->test( i - 1, j ) );
                   t = std::min( t, map->test( i, j + 1 ) );
                   t = std::min( t, map->test( i, j - 1 ) );
                   if ( t != INT_MAX )
                   {
                      v = t + 1;
                      not_done = true;
                   };
                 };
               };
            if ( map->at( dx, dy ) != empty )
              break;
          };
          // mark path
          while ( true )
          {
            int v = map->at( dx, dy );
            if ( v <= 0 )
              break;
            map->at( dx, dy ) = path;
            if ( map->test( dx + 1, dy ) < v )
              dx = dx + 1;
            else if ( map->test( dx - 1, dy ) < v )
              dx = dx - 1;
            else if ( map->test( dx, dy + 1 ) < v )
              dy = dy + 1;
            else if ( map->test( dx, dy - 1 ) < v )
              dy = dy - 1;
            else
              break; // smth wrng
          };
        };
        
        int main()
        {
          Map *map = createFromDefMap();
          map->show();
          findPath( map, 0, 0, 5, 5 );
          map->show();
          delete map;
          
          return 0;
        };
        Ответить

        • > #include <boost...
          Господи, когда вижу это, хочется взять пистолет и таки поддаться на провокацию.
          Пример тупой и неполный, но блджад, наглядно показывает что без буста головного мозга код чище, короче и незамусореннее.

          http://ideone.com/hKsD6M
          Ответить

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