2023/10/5 Minesweeper

https://gyazo.com/31635bc945f1f05e91a7671ab23781b8

例えばこんな入力が与えられる

code:_

·*·*·

··*··

··*··

·····

実際は空白文字

以下のような返却をする

code:_

1*3*1

13*31

·2*2·

·111·

0個のときは空白文字のままで良い

Exercismのサイト自体のバグなのか、テストコードのスタイルが終わっているので整形

code:hs

import Data.Foldable (for_)

import Test.Hspec (Spec, describe, it, shouldBe)

import Test.Hspec.Runner (configFailFast, defaultConfig, hspecWith)

import Minesweeper (annotate)

main :: IO ()

main = hspecWith defaultConfig {configFailFast = True} specs

specs :: Spec

specs = describe "annotate" $ for_ cases test

where

test (description, board) = it description assertion

where

clearBoard = map (map mineOrSpace)

mineOrSpace '*' = '*'

mineOrSpace _ = ' '

cases = [ ("no rows", [] )

, ("no mines", [ " "

, " "

, " " ] )

, ("board with only mines", [ "***"

, "***"

, "***" ] )

, ("mine surrounded by spaces", [ "111"

, "1*1"

, "111" ] )

, ("space surrounded by mines", [ "***"

, "*8*"

, "***" ] )

, ("vertical line", [ "1"

, "*"

, "2"

, "*"

, "1" ] )

, ("vertical line, mines at edges", [ "*"

, "1"

, " "

, "1"

, "*" ] )

, ("cross", [ " 2*2 "

, "25*52"

, "*****"

, "25*52"

, " 2*2 " ] )

, ("large board", [ "1*22*1"

, "12*322"

, " 123*2"

, "112*4*"

, "1*22*2"

, "111111" ] )

]

property-based testingしてるのか、良い

どういう方針で解けばよいのだろう

パーツの分類方針

パーツを分類するなら、

隅

隣接するものが3つ

辺

隣接するものが5つ

中心

隣接するものが8つ

という風には分けられる

パーツを分類しないなら、

いずれも周囲に8つあり、見えないものはすべて空白とみなす、

と捉えることもできそう

あるいは、実行前に、与えられた盤面に1周分自分で空白を与えてから始める、というアプローチもできそう

中心でないものはすべて無視するとかする

いくつかの方針

逐次的に上から順に計算していく方法

3*3のブロックをスライドさせていくとか

その仕組みさえあれば、リストモナドを使って、縦方向・横方向自動化できそう

各セルをオブジェクトとみなす方法

ボトムアップのイメージ

各セルに対するプログラムを書き、後は一周することで求まる

2次元であることうまく活かす方法

xy座標を持たせて計算するとか

1次元にする方法

2次元であるということを忘れて、1次元にした上で計算するとか

あまりうまく行かなそうな気がする

数学的にエクストリームに解決する方法

入力を行列か何かに見立てて、代数的にサッと答えを求めるみたいなアプローチありそう

リストで表現されていると、

横方向の隣接は簡単に計算できそうだけど、

縦方向の隣接の計算が難しそう

ここを何か良い仕組みでできると良さげ

横も縦も区別せずに扱えると良い

その一種の方法が、座標であろう

あとは座標だけを見て互いに計算する

リストのindexが隣り合っているかどうかは見ない

この問題における「haskell的なアプローチ」というのがいまいちイメージできてない

リストモナドを使う、遅延評価を上手く使う、とかはありそう

1つのセルとか、3*3のブロックを、一般的な構造に落とし込めたりしないだろうか？

舐める処理で言えば、Traversableとかあるわけで

1次元リストを舐めるのではなく、2次元図面を舐める処理を1個書けばあとは勝手に計算されないだろうか

入力と回答的に、構造は全く同じなので、盤面をFunctorとすることはできそう

FoldableとTraversableも簡単にできそうなイメージがある

その場合、座標変換とか特にしなくても、

Cell -> Intな関数を1つ定義できれば一瞬で終わりそうな気もする

その関数がむずいのだろうけど

座標に抽象化して扱う、というのがそもそも関数型っぽくない感じする

indexを見ながら操作するというこをしないので

一次元でできる抽象化をまず考えて、その後二次元に応用するとか出来んかな

1次元で考えると、今回の場合、自分と、その前後の要素が欲しい

その時、Index-1, Index+1というふうにアクセスするのではなく、

そもそも3つの要素ごとに舐めていく感じにするだろう

とりあえず1次元のものはスルッと書けた

次に行列に対して適用する、というのを考えてもいいが、

いったん、縦方向1次元、斜め方向1次元、も空想してみてもいいかもしれない

とは言え、縦方向1次元はマジで一瞬でできるはずなのでスルーして良さそう

1次元が書けたということは、それを少し拡張したものを複数回適用すれば解けるはず

つまり、3行を1つとみなして、それを1行ずつずらして最後まで繰り返す、みたいな

https://gyazo.com/0c6e7b364f53c122a0f4791d622d9e4b

いやあ、なんか結局、縦方向のものを取得するのにインデックスアクセスが必要になる？

ここの抽象化を上手くやってインデックスアクセスせずに実現できないだろうか

1次元→2次元の抽象化とか上手くやりたい

これで行ける！と思って実装を進めると、コーナーケースに対応できてないことに気づく

例えば、諦めてindex accessをする際に、1次元で相対的にアクセスできるのでは？と思い以下の様に書いてみた

全くきれいじゃないが

code:hs

where

self = store !? n

top1 = store !? (n-c-1)

top2 = store !? (n-c)

top3 = store !? (n-c+1)

mid1 = store !? (n-1)

mid2 = store !? (n+1)

bot1 = store !? (n+c-1)

bot2 = store !? (n+c)

bot3 = store !? (n+c+1)

(!?) xs i

| i < 0 = Safe

| otherwise = case drop i xs of

(y:ys) -> y

[] -> Safe

これは以下のようなケースに対応できない

code:hs

, ("vertical line", [ "1"

, "*" -- mid1, top2

, "2" -- ←これを処理してる時

, "*" -- mid2, bot2

, "1" ] )

1次元に変換して処理をすると情報が欠落してしまうので、やはり座標を使わないと無理そう

いくつかの方針でリファクタしたい

我ながら酷い

後から見れば、最初の方針のほうが正しかったが、書けなかったのでかなり具体的なコードにしてpassすることにしてしまった

リベンジしたい

リストを座標に変換する関数

あるあるなきがする

他の人の回答、5分の1の行数で解いてる人がいる..

恐らくスタート地点で違うのだろうなと思う

抽象化の方針の建て方がまず違うのだと思う

1個ずつ気になったやつを見ていく

どういうコードなのか、というよりどういう抽象化をしたのか？に着目する

まずこの部分

code:hs

annotate m = zipWith (zipWith toChar) mines adj

where

-- 同じ構造のまま、Boolに変換

mines = (map . map) (== '*') m

-- 同じ構造のまま、数値に変換

adj = smooth . (map . map $ fromEnum) $ mines

toChar True _ = '*'

toChar False 0 = ' '

toChar False n = intToDigit n

code:hs

たしかに、zipで十分かもね

tripsを一部改変

code:hs

trips f border = triples f . expand border

triples f l@(a:b:c:_) = f a b c : triples f (tail l)

triples _ _ = []

要は、まずリストの両端にborderを追加し、その後、goを適用している

tripsに関しては惜しいところまでは言ってた

ここを多層化たせることで、smoothに繋げられる

smoothを一部改変

この関数がまさに、1次元から2次元に抽象化して接続している箇所

code:hs

smooth = smoothCols . smoothRows

where

add3 a b c = a + b + c

smoothCols = map (trips add3 0)

smoothRows = trips (zipWith3 add3) (repeat 0)

別に逆でも良い

例えば、

code:こういう入力が

[

]

code:こうなっている

[

]

code:hs

smoothRows = transpose . smoothCols . transpose

あまり美しくはない

[0+1+4,0+2+5,0+3+6]

愚直だけど簡潔

code:hs

isMine b a]

index accessぽいことをするにしても、こういう書き方の方が洒落てる

その思考法みたいなのを体系化できないかな

経験則からのパターンマッチは微妙なんよな、受験数学みたいになる

抽象的な、いくつかのアイディアを適当に並べてみて、

徐々に具体化させていき、

どこがトレードオフや課題になるのかを見つけた上で、

それを解決しながら、その方針を進めるか、

ダメだと諦めて、別の方針でやっていくなり、新たな方針を見つけるか

まあ、プログラミングなんて、ぐちゃぐちゃを許容するならだいたいどんな方針でも解決できちゃうわけで

ここで目指したいのは、最も良さげな抽象化の方法は何か？を突き止めること

型的な考え方をするとやっぱ、登場人物の分類に目が行くなあ

ただ、分類しすぎると、それらを別概念として捉えてしまうことで、抽象化に失敗することも考えられる

あとで訂正すれば良いだけの話ではあるが

まず1次元に落として考えてみる、とかはありそう

その後、それを抽象化して2次元で同じことをする

いったん感想

最初、方針の建て方がかなり難しかった

1次元で解いた後に、3*3ブロックをスライドさせる方法

こっちは試してないが、まだギリ可能性はありそうな気がしてる

他の人の解法でも、パッと見た感じはなかった

objectっぽく扱う方法

結局これで解いたが、きれいじゃなくなった

進める中で、まず1次元で解いて、それを抽象化して2次元にすると良いのでは？というのを思った

後から見ればこれがかなり正しかった

が、その方針を満たすためのコードを書く力がなかった(?)

1行を書いた後に、1列を解くものだと思ってたが、無理だった

で、諦めてobjectっぽく扱う方法で進めた

1行を書いて、

1行まるごとに対して、列方向に対して書くといけるというのがわかった

なるほどなあ