АОС день 22: вирусов Sporifica Часть 1, Решение Новичок в Хаскелл


До недавнего времени, я была очень посвящена императивных языков программирования (в основном C++ и C, чтобы быть точным), когда я решил рисковать в неизвестных водах, подобрав новый, совершенно другой язык, который, оказалось, Хаскелл, решение, который, оказалось, повлияло то, что я владел копию "узнать Хаскелл за великое добро!", книга, которую я очень любил учиться.

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

Я обезжиренное через упражнения, ищу одну простую достаточно, чтобы преодолеть с моей еще очень неадекватные и шаткие навыки Хаскелл, и, наконец, выбрал задачу дня 22.

Описание Проблемы

Диагностика показывает, что местной сети вычислительного кластера был зараженной вирусом Sporifica. Сетки вычислительного кластера является казалось бы-бесконечной двумерной сетки узлов. Каждый узел либо чистая, либо заражены вирусом.

Для предотвращения перегрузки узлов (которые могли бы сделать их бесполезно вирус) или обнаружение системных администраторов, ровно один вирус перевозчик движется по сети, заражая или узлов очистки, как это движется. Носителем вируса всегда находится на одном узле сети (текущий узел) и отслеживает направление его сторону.

Чтобы избежать обнаружения, вирусоноситель работает прерывисто; в каждой серии, он просыпается, делает кое-какую работу, и идет обратно спать. Следующие действия выполняются в порядке один раз прорвало:

  • Если текущий узел заражен, он превращается в его право. В противном случае, это поворачивает ее влево. (Поворот производится на месте; текущего узла не изменится.)
  • Если текущий узел является чистым, он становится зараженным. В противном случае, оно будет чистить. (Это делается после того, как узел рассмотрела в целях изменения направления движения.)
  • Носителем вируса движется вперед одного узла в направлении он сталкивается. Диагностика также предоставил карту узла инфекционного статуса (входной головоломка).

Чистые узлы показаны .; зараженных узлов показаны в виде #. Эта карта показывает только в центре сетки; есть еще много узлов за пределы те, что показаны, но ни один из них в настоящее время заражены.

Носителем вируса начинается в середине карты вверх.

(Полный головоломка описание с примерами можно ознакомиться на официальном сайте Кро.)

Указанные головоломка состоит из файла, содержащего сетку . и #.

Мое Решение

import Data.List.Index
import qualified Data.Set as Set
import System.Environment
import System.IO
import qualified System.IO.Strict as IOS

type Position = (Int, Int)
type Dimensions = (Int, Int)
type NodeMap = Set.Set Position

data Rotation = Clockwise | Counterclockwise deriving (Eq, Show)
data Direction = North | East | South | West deriving (Eq, Show)


nextDirection :: Rotation -> Direction -> Direction
nextDirection rot dir
    | rot == Clockwise && dir == West         = North
    | rot == Clockwise && dir == East         = South
    | rot == Clockwise && dir == North        = East
    | rot == Clockwise && dir == South        = West
    | rot == Counterclockwise && dir == West  = South
    | rot == Counterclockwise && dir == East  = North
    | rot == Counterclockwise && dir == North = West
    | rot == Counterclockwise && dir == South = East

parseInput :: String -> (Dimensions, NodeMap)
parseInput s = ((length . head . lines $ s, length . lines $ s),
    foldl (\set (index, char) ->
        if char == '#'
            then Set.insert index set 
            else set)
    Set.empty
    . ifoldl (\ls index line ->
        ls ++ zipWith (\ix (i, char) -> 
            ((i, ix), char))
        (repeat index) (indexed line))
    []
    . lines $ s)

simulateNBurstsImpl :: Int -> (Int, Position, Direction, NodeMap)
    -> (Int, Position, Direction, NodeMap)
simulateNBurstsImpl 0 x = x
simulateNBurstsImpl i (count, pos, dir, map) = simulateNBurstsImpl
    (i - 1) transitionFunction 
    where
        step (a, b) dir
            | dir == West  = (a - 1, b)
            | dir == East  = (a + 1, b)
            | dir == North = (a, b - 1)
            | dir == South = (a, b + 1)
        transitionFunction 
            | Set.member pos map == True = let
                    nextDir = nextDirection Clockwise dir
                in (count, step pos nextDir, nextDir, Set.delete pos map)
            | Set.member pos map == False = let
                    nextDir = nextDirection Counterclockwise dir
                in (count + 1, step pos nextDir, nextDir, Set.insert pos map)

simulateNBursts :: Int -> Dimensions -> NodeMap -> Int
simulateNBursts i (width, height) map =
    first (simulateNBurstsImpl i (0, startingPos, North, map))
    where
        startingPos = (width `quot` 2, height `quot` 2)
        first (a, _, _, _) = a


main = getArgs >>= \(filename : _) ->
    withFile filename ReadMode IOS.hGetContents >>= \content ->
        let parsed = parseInput content in
        print . simulateNBursts 10000 (fst parsed) . snd $ parsed

Примечания:

  • Программа принимает один аргумент в командной строке; путь к файлу, содержащему стартовой решетке.
  • Я решил использовать набор в качестве базовой структуры данных, как это делает его легко работать с растущим сетям. Моя первая попытка использовать двумерную последовательность, но расширение сетки оказалось слишком много мороки, на мой вкус.
  • Код предполагает, что все данные верны, в том числе и тот факт, что параметр командной строки был принят и указывает на правильный файл.

Обзор Запросов

Пожалуйста, не стесняйтесь комментарий и все, что приходит на ум! Что сказал, У меня есть несколько конкретных вопросов:

  1. Имея simulateNBursts как приукрасить интерфейс simulateNBurstsImpl как-то некрасиво для меня. Есть ли способ, чтобы привести в порядок и объединить эти две функции? Или это общая картина?
  2. Как читается этот код? Как автору, мне трудно судить о том, насколько (не)приятный этот код в глаза третьего лица, тем более, что я не имеете никакого опыта в чтении и написании кода на Haskell. Что я могу сделать, чтобы улучшить читаемость?
  3. nextDirection кажется очень многословен для меня. Есть ли более лаконичный способ это реализовать?


129
2
задан 10 февраля 2018 в 10:02 Источник Поделиться
Комментарии
1 ответ

Вы можете рядный simulateNBurstsImpl Если избавиться от рекурсии:

simulateNBurstsImpl n = foldr (.) id $ replicate n transitionFunction

Сочетание zipWith С repeat - это дурацкая затея. (Я не знаю, где вы получаете ifoldl и indexedтак что я предполагаю, что они начинаются с 0).

parseInput :: String -> (Dimensions, NodeMap)
parseInput s = ((length . head $ lines s, length $ lines s), Set.fromList
[ (x, y)
| (y, line) <- zip [0..] $ lines s
, (x, char) <- zip [0..] line
, char == '#'
])

Direction и Rotation можно непосредственно представить как смещение и функции смещения.

import Data.NumInstances.Tuple

type Rotation = Direction -> Direction
type Direction = (Int, Int)

transitionFunction (count, pos, (dx,dy), map) = if Set.member pos map
then let nextdir = (-dy,dx)
in (count , pos + nextDir, nextDir, Set.delete pos map)
else let nextdir = (dy,-dx)
in (count + 1, pos + nextDir, nextDir, Set.insert pos map)

Дополнительно: lens и State специализируется в такой неудобный рода вещи.

data S = S
{ _count :: Int
, _pos :: Position
, _dir :: Int
, _map :: NodeMap
}

makeLenses ''S

simulateNBursts i (width, height) map =
(`evalState` (0, (width `quot` 2, height `quot` 2), (0,-1), map)) $ do
replicateM_ i $ do
hashtagged <- map . contains pos <<%= negate
nextDir <- dir <%= \(x,y) -> if hashtagged then (-y,x) else (y,-x)
pos += nextDir
unless hashtagged $ count += 1
use count

1
ответ дан 11 февраля 2018 в 04:02 Источник Поделиться