- 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
laMer007 11.02.2014 21:13 # −1
Жаль нет раздела для Хаскеля.
Как всегда подобные олимпиады проводим просто для отдыха.
Просто покажите код, который работает для заявленных режимов функционирования. Демонстрация в любом онлайн компиляторе (для тех кто не знает где его найти - спросите в теме). Желательно красивый и короткий код. Скорость не важна, но если кому интересно - можно позже её измерить. Язык любой. Алгоритм любой.
Задание:
Написать код поиска пути на двухмерной карте. Карту можно красиво представить в коде и\или сгенерировать. Карта состоит из пустот и стен.
Красиво показать карту и путь на ней.
Ходить можно по вертикали и горизонтали.
Если захочется, чтобы алгоритм умел прокладывать путь по диагонали, то путь не должен проходить через рядом стоящие стены, например ниже ошибка, тк между стенами прохода нет:
Если вы написали неточный алгоритм поиска пути, то не забудьте указать это. Впрочем желательно точный алгоритм использовать.
На тот случай, если кто-то хочет, чтобы его код мог учувствовать в измерении производительности, которая возможно состоится: картогенератор должен уметь генерировать карты произвольных размеров.
Выбрал алгоритм не очень подходящий для чистого кода. Код по большей части чист. В том числе сам алгоритм поиска пути. В коде много комментариев и код относительно не плохо декомпозирован. Конечно избавившись от этого - программу можно было бы значительно подсократить.
Алгоритм простейший и не оптимальный. Поиск в глубину, волновой алгоритм.
http://codepad.org/6lGy7TPX
anonimb84a2f6fd141 13.02.2014 20:16 # −2
guest 14.02.2014 00:01 # 0
laMer007 14.02.2014 09:37 # 0
http://ideone.com/mxbgNl
Не пользовался монадами кроме как для вывода результата.
Я тоже пытался использовать Data.Array.Unboxed, но по какой-то непонятной мне причине код с UArray не компилировался. Хотя если заменить его на на обычный чистый Array, то всё работало. Не знаете в чем может быть дело? Кстати разница между Array и UArray в том, что в Array лежат ссылки на элементы, а не сами элементы?
А зачем использовали unsafeFreeze unsafeThaw? Чтобы то что работает в монадах начало работать и в чистом коде и наоборот? unsafeFreeze unsafeThaw позволяют менять память массивов в чистом коде для оптимизации, чтобы каждый раз не происходило копирования?
guest 14.02.2014 12:53 # 0
Да, сами элементы.
unsafeFreeze - чтобы не копировать steeps: дальше steps не используеется => безопасно.
В частности: runST (... ; unsafeFreze arr) <=> runSTUArray (... ; return arr) всегда безопасн.
unsafeThaw - то же для laby, здесь нюанс - дальше нельзя читать его элементы, но getPath (fromList ..) - очевидно безопасно, лучше было бы просто thaw или обозначить getPathUnsafe, либо получать аргумент [[Char]].
laMer007 14.02.2014 13:22 # 0
Код выше, в начале топика. Заменить везде Array на UArray и получим ошибку компиляции. В чем дело - не понял. UArray использовался только для чаров и интов, так что проблем как я думаю быть не должно. Или все дело в том, что по умолчанию используется Integer (Неограниченный Integer) вместо короткого Int и потому это ссылочный тип и для него появляется ошибка? Как можно исправить? Везде вручную проставить Int вместо типа Integer или a?
guest 14.02.2014 13:50 # 0
Но всплывают timeout-ы, хотя может проблемы codepad (у них вроде hugs).
laMer007 14.02.2014 13:59 # 0
guest 14.02.2014 14:22 # +1
laMer007 14.02.2014 14:53 # 0
guest 14.02.2014 18:23 # +2
1) лишь haskell-98
2) много ключевых библиотек прибито к ghc, сложно оценить какая часть пакетов с hackage заведется, но не думаю, что хотя бы половина
3) это _интерпретатор_
> не было System.Random
Есть еще fpcomplete.com , правда регистрация и больше месяца за денежку.
Берешь пример из wiki "Extensible records" и проверяешь: http://codepad.org/272qH9mG, в идеоне такое не заведется
guest 14.02.2014 13:56 # 0
Stertor 11.02.2014 21:27 # −4
Konardo 11.02.2014 21:41 # −11
Stertor 11.02.2014 21:50 # −4
Konardo 11.02.2014 22:00 # −14
guest 11.02.2014 22:01 # −6
Konardo 11.02.2014 22:03 # −14
guest 11.02.2014 22:04 # −6
guest 11.02.2014 22:09 # −6
Konardo 11.02.2014 22:12 # −14
wvxvw 11.02.2014 21:47 # 0
laMer007 12.02.2014 01:43 # 0
Konardo 11.02.2014 21:47 # −11
Stertor 11.02.2014 22:13 # −6
У них админ кстати пассивный пидор (микаэл)- на ебале у него написано.
Konardo 11.02.2014 22:14 # −13
Stertor 11.02.2014 22:17 # −5
Konardo 11.02.2014 22:18 # −5
Stertor 11.02.2014 22:23 # −5
Konardo 11.02.2014 22:28 # −5
Stertor 11.02.2014 22:30 # −5
Тогда хоть подскажи годный форум или сайт для спаминга.
Кстати. Картинки с птицами можно распознавать с помощью GetPixel (не API, а функция из канвы TImage) в скрытом окне.
Konardo 11.02.2014 22:59 # −6
Konardo 11.02.2014 22:25 # −13
Stertor 11.02.2014 22:28 # −6
Это нужно для воспитания терпения участника.
>>Такого нет ни на одном сайте - неделю ждать возможности комментирования, две недели - возможности постинга
зато тут нет модераторов и админов- количество флуда регулируется не количеством разгаданных каптур (хотя и этим тоже) но в большей степени совестью флудера.
Konardo 11.02.2014 22:33 # −6
Я заметил в себе необычайное свойство - я медленно убиваю любой сайт, на котором задерживаюсь.
Stertor 11.02.2014 22:36 # −6
Но у меня есть иная трактовка: ты забредаешь на загнивающие сайты, и лишь способствуешь дальнейшей деструкции личности тамошних обитателей, что в конечном итоге неизбежно приводит к коллапсу.
Abbath 11.02.2014 23:29 # −1
kipar 12.02.2014 16:31 # +2
Konardo 12.02.2014 16:34 # −6
Lure Of Chaos 12.02.2014 22:59 # −1
bormand 12.02.2014 23:07 # +1
Не обращай на него внимания, ни к чему эта агрессия. Если сильно достает - включи фильтр по никам, тут такой выкладывали.
Lure Of Chaos 12.02.2014 23:12 # +1
Konardo 12.02.2014 23:27 # −4
А действительно - хуле я к тебе приебался?...
bormand 12.02.2014 23:30 # −2
Lure Of Chaos 13.02.2014 06:28 # +2
Vindicar 13.02.2014 09:34 # 0
bormand 13.02.2014 09:40 # −2
Konardo 13.02.2014 10:21 # −7
bormand 13.02.2014 10:26 # −1
Расчешу ей шерстку гладко.
Konardo 13.02.2014 11:04 # −15
Чтобы её доставить радость.
Konardo 11.02.2014 22:26 # −14
Stertor 11.02.2014 22:29 # −5
laMer007 12.02.2014 01:40 # 0
laMer007 13.02.2014 15:34 # 0
laMer007 13.02.2014 15:34 # 0
laMer007 13.02.2014 15:35 # 0
laMer007 13.02.2014 15:36 # 0
laMer007 13.02.2014 15:36 # 0
laMer007 13.02.2014 15:36 # 0
laMer007 13.02.2014 15:37 # 0
Решил, раз сравниваю выразительность языков, то напишу ещё на каком-нибудь.
Хех, на крестах программа заработала с первого запуска, в отличии от хаскеля. Волновой алгоритм, поиск в ширину. Как и ожидалось кода немного побольше. Оптимальность должна быть повыше хаскелевой. Тесты не писал, ассерты тоже не вставлял. Алгоритм немного сложнее, но в хаскеле было не на много бы больше, чем есть сейчас. На пару строк побольше. Декомпозиция примерно на уровне хаскелевой проги. Даже названия функций схожи некоторых.
laMer007 13.02.2014 18:55 # 0
laMer007 13.02.2014 18:56 # 0
laMer007 13.02.2014 18:58 # +2
> #include <boost...
Господи, когда вижу это, хочется взять пистолет и таки поддаться на провокацию.
Пример тупой и неполный, но блджад, наглядно показывает что без буста головного мозга код чище, короче и незамусореннее.
http://ideone.com/hKsD6M