- 001
- 002
- 003
- 004
- 005
- 006
- 007
- 008
- 009
- 010
- 011
- 012
- 013
- 014
- 015
- 016
- 017
- 018
- 019
- 020
- 021
- 022
- 023
- 024
- 025
- 026
- 027
- 028
- 029
- 030
- 031
- 032
- 033
- 034
- 035
- 036
- 037
- 038
- 039
- 040
- 041
- 042
- 043
- 044
- 045
- 046
- 047
- 048
- 049
- 050
- 051
- 052
- 053
- 054
- 055
- 056
- 057
- 058
- 059
- 060
- 061
- 062
- 063
- 064
- 065
- 066
- 067
- 068
- 069
- 070
- 071
- 072
- 073
- 074
- 075
- 076
- 077
- 078
- 079
- 080
- 081
- 082
- 083
- 084
- 085
- 086
- 087
- 088
- 089
- 090
- 091
- 092
- 093
- 094
- 095
- 096
- 097
- 098
- 099
- 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
Follow us!
Жаль нет раздела для Хаскеля.
Как всегда подобные олимпиады проводим просто для отдыха.
Просто покажите код, который работает для заявленных режимов функционирования. Демонстрация в любом онлайн компиляторе (для тех кто не знает где его найти - спросите в теме). Желательно красивый и короткий код. Скорость не важна, но если кому интересно - можно позже её измерить. Язык любой. Алгоритм любой.
Задание:
Написать код поиска пути на двухмерной карте. Карту можно красиво представить в коде и\или сгенерировать. Карта состоит из пустот и стен.
Красиво показать карту и путь на ней.
Ходить можно по вертикали и горизонтали.
Если захочется, чтобы алгоритм умел прокладывать путь по диагонали, то путь не должен проходить через рядом стоящие стены, например ниже ошибка, тк между стенами прохода нет:
Если вы написали неточный алгоритм поиска пути, то не забудьте указать это. Впрочем желательно точный алгоритм использовать.
На тот случай, если кто-то хочет, чтобы его код мог учувствовать в измерении производительности, которая возможно состоится: картогенератор должен уметь генерировать карты произвольных размеров.
Выбрал алгоритм не очень подходящий для чистого кода. Код по большей части чист. В том числе сам алгоритм поиска пути. В коде много комментариев и код относительно не плохо декомпозирован. Конечно избавившись от этого - программу можно было бы значительно подсократить.
Алгоритм простейший и не оптимальный. Поиск в глубину, волновой алгоритм.
http://codepad.org/6lGy7TPX
http://ideone.com/mxbgNl
Не пользовался монадами кроме как для вывода результата.
Я тоже пытался использовать Data.Array.Unboxed, но по какой-то непонятной мне причине код с UArray не компилировался. Хотя если заменить его на на обычный чистый Array, то всё работало. Не знаете в чем может быть дело? Кстати разница между Array и UArray в том, что в Array лежат ссылки на элементы, а не сами элементы?
А зачем использовали unsafeFreeze unsafeThaw? Чтобы то что работает в монадах начало работать и в чистом коде и наоборот? unsafeFreeze unsafeThaw позволяют менять память массивов в чистом коде для оптимизации, чтобы каждый раз не происходило копирования?
Да, сами элементы.
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?
Но всплывают timeout-ы, хотя может проблемы codepad (у них вроде hugs).
1) лишь haskell-98
2) много ключевых библиотек прибито к ghc, сложно оценить какая часть пакетов с hackage заведется, но не думаю, что хотя бы половина
3) это _интерпретатор_
> не было System.Random
Есть еще fpcomplete.com , правда регистрация и больше месяца за денежку.
Берешь пример из wiki "Extensible records" и проверяешь: http://codepad.org/272qH9mG, в идеоне такое не заведется
У них админ кстати пассивный пидор (микаэл)- на ебале у него написано.
Тогда хоть подскажи годный форум или сайт для спаминга.
Кстати. Картинки с птицами можно распознавать с помощью GetPixel (не API, а функция из канвы TImage) в скрытом окне.
Это нужно для воспитания терпения участника.
>>Такого нет ни на одном сайте - неделю ждать возможности комментирования, две недели - возможности постинга
зато тут нет модераторов и админов- количество флуда регулируется не количеством разгаданных каптур (хотя и этим тоже) но в большей степени совестью флудера.
Я заметил в себе необычайное свойство - я медленно убиваю любой сайт, на котором задерживаюсь.
Но у меня есть иная трактовка: ты забредаешь на загнивающие сайты, и лишь способствуешь дальнейшей деструкции личности тамошних обитателей, что в конечном итоге неизбежно приводит к коллапсу.
Не обращай на него внимания, ни к чему эта агрессия. Если сильно достает - включи фильтр по никам, тут такой выкладывали.
А действительно - хуле я к тебе приебался?...
Расчешу ей шерстку гладко.
Чтобы её доставить радость.
Решил, раз сравниваю выразительность языков, то напишу ещё на каком-нибудь.
Хех, на крестах программа заработала с первого запуска, в отличии от хаскеля. Волновой алгоритм, поиск в ширину. Как и ожидалось кода немного побольше. Оптимальность должна быть повыше хаскелевой. Тесты не писал, ассерты тоже не вставлял. Алгоритм немного сложнее, но в хаскеле было не на много бы больше, чем есть сейчас. На пару строк побольше. Декомпозиция примерно на уровне хаскелевой проги. Даже названия функций схожи некоторых.
> #include <boost...
Господи, когда вижу это, хочется взять пистолет и таки поддаться на провокацию.
Пример тупой и неполный, но блджад, наглядно показывает что без буста головного мозга код чище, короче и незамусореннее.
http://ideone.com/hKsD6M