Ярлыки доски минного тральщика (начальный уровень) - PullRequest
Новая
       27

Ярлыки доски минного тральщика (начальный уровень)

0 голосов
/ 11 ноября 2019

Нам дали домашнее задание, где мы получаем образец доски, похожей на тральщик, с пробелами вместо цифр (доска находится в форме [String]) и уже размещенными минами. Нам нужно создать функцию, которая заменяет все пробелы числами, которые равны числу примыкающих мин.

Я не смог добиться реального прогресса, кроме удаления всех пробелов с нулями, которыевероятно, даже не полезно в любом случае. У меня также была проблема с нулями типа Char, из-за чего я не мог добавить, например, +1 к нему. Было бы здорово, если бы это можно было решить без продвинутых функций, поэтому я могу понять это, но подойдет любое решение или хотя бы идея решения.

Вот как должно выглядеть начало кода. 

import Data.Char

type Result = [String]

pp :: Result -> IO ()
pp x = putStr (concat (map (++"\n") x)) --prints strings in a column.


sampleInput = ["       ",
               " *     ",
               "    *  ",
               "   *   ",
               "      *",
               "***    ",
               "* *    ",
               "***    "]

minesweeper :: Result -> Result

И результат должен быть таким 

Prelude>pp(minesweeper sampleInput)
1110000
1*11110
1122*10
001*221
233211*
***2011
*8*3000
***2000

Я невероятно рад любым указаниям, так как не могу добиться реального прогресса.

Обновление: сделалнемного другое, но похожее решение. Вы можете проверить связанный вопрос здесь

1 Ответ

3 голосов
/ 11 ноября 2019

То, что вам нужно здесь, называется "сверточная трафаретная печать" . Посмотрите на эту картинку: 

111
1x1
111

Это ваш трафарет. Выберите плитку на игровом поле и поместите трафарет поверх этой плитки. Сколько 1 s оверлейных мин, это число, которое мы должны отобразить в этой плитке. Например: 

       .....   .....
111    .*...   .....
1x1  + ..x*. = ..3..
111    ...*.   .....
       .....   .....

Как только мы применим эту операцию ко всей плате, мы в основном закончим.

Для этого есть продвинутые устройства, такие как comonads и arrays, но для этой целиВ этом посте я постараюсь все упростить, поэтому мы будем чертить все вручную, в самых простых видах. Я также собираюсь оставить некоторые пробелы в коде, чтобы читателю было скучнее. Если вы включите -fdefer-typed-holes, вы можете поместить такие элементы, как _wut вместо ..., и ghc скажет вам, как, по его мнению, должен быть тип отверстия.

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

    charsToInts :: [[Char]] -> [[Int]]
charsToInts = (fmap . fmap) charToInt
  where
    charToInt '*' = ...
    charToInt ... = ...

intsToChars :: [[Int]] -> [[Char]]
intsToChars = ...

  2. Вложенный список не очень удобен для работы. Мы определим некоторые вспомогательные функции, чтобы сделать это проще. Нам, безусловно, понадобится операция «индексация» , то есть доступ к элементу по его индексу - если он вообще там есть. 

    lookup2DMaybe :: [[a]] -> (Int, Int) -> Maybe a
lookup2DMaybe u (i, j) = do
    xs' <- lookupMaybe xs  i
    x   <- ...
    return x
  where
    lookupMaybe :: [a] -> Int -> Maybe a
    lookupMaybe xs i
        | 0 <= i && i < length xs = ...
        | ...                     = ...

  3. Теперь, к интересным вещам - трафаретное приложение. 

    applyStencil :: [[Int]] -> (Int, Int) -> Int
applyStencil u = sum . Data.Maybe.catMaybes . fmap (... u) . stencil
  where
    stencil :: (Int, Int) -> [(Int, Int)]
    stencil (i, j) = [ (i + di, ...) | di <- ..., dj <- ..., (di, dj) /= ... ]

    Это работает? 

    λ applyStencil (charsToInts sampleInput) (3, 5)
2
λ applyStencil (charsToInts sampleInput) (6, 1)
8

  4. Все, что осталось сделать, это "карта" трафарет вокруг минного поля. Для этого мы собираемся создать доску, на которой в каждой точке записаны ее координаты. Я надеюсь, что где-нибудь по пути вы поймете, почему. 

    indices :: [[a]] -> [[(Int, Int)]]
indices u = [ [ ... | ... ] | ... ]

    Идея в том, что мы даем ему доску из чего угодно, и она создает доску координат такого же размера.

  5. Рассмотрим тип, который у нас есть: 

    λ :type applyStencil (charsToInts sampleInput) 
applyStencil (charsToInts sampleInput) :: (Int, Int) -> Int

    Итак, эта функция преобразует координаты в число мин вокруг этих координат. Что произойдет, если мы отобразим это на доске координат? 

    fill :: [[Int]] -> [[Int]]
fill u = (fmap.fmap) (... u) (... u)

λ intsToChars (fill (charsToInts sampleInput))
["1110000","1011110","1122110","0011221","2332110","2422011","4843000","2422000"]

    Правильно, не правда ли?

  6. Осталось сделать только небольшие вещи: учитывая двадоски персонажей, накладывайте их. Это изложено в ответе на другой вопрос о списках списков. (В последнее время мы получаем много вопросов такого рода. Передайте привет вашему профессору из команды помощников преподавателя Stack Overflow Haskell!)

  7. Окончательное решение! 

    minesweeper x = overlay x (intsToChars . fill . charsToInts $ x)

    Совсем не сложно!

Есть несколько способов улучшить этот код:

  1. Создать специализированныйтип для доски, такой, что могут быть построены только правильные платы.
  2. Определите комонаду для этого типа.
  3. Сотрите тип целиком и обобщите код для комонады Store.
  4. Используйте эффективную обработку массива.

Но идеи, которые мы исследовали, существуют долго.

Некоторое дальнейшее чтение:

  1. Основытрафаретной свертки.
  2. Использование стандартных типов комонад.
  3. Усовершенствованная оптимизация трафаретной свертки.

Дайте мне знать, как это происходит!

...