下の20☓20の数字列からタテ・ヨコ・ナナメいずれかに4つ並んだ数字の積を取ったときの最大値を求める。
2020/04/11追記:
なんとData.Listに標準でtranspose関数があることが判明。しかもそちらの方が優秀で、それを使えばナナメ成分を拾うのが格段に簡単になる。いずれ修正しようと思う。
+++++++++
これは難しかった。まず、自分の中の勝手な縛りとして「座標は使わない」という変なルールを作ってしまったために、大変な苦労をすることになった。だって、座標を使ったらHaskellっぽくないんだもん。（誰？）
ということで、行列を転置する関数を作ったり、数字を右斜めに拾う関数を作ったり、それらを使いまわして左斜めに拾う関数を作ったり。こういう小さな部品を自作して、それを組み立てて大きなプログラムを作っていくのが、Haskellの醍醐味と言えば醍醐味ではある。
まずは問題の数字列をテキストとして読み込む関数gridsを準備する。
これは文字列['[String]]型のままでは今後不便なので、アレコレして['[Int]]型にしておく。
こんなにマップマップしていていいのだろうか？と不安になるが、とりあえず前に進む。
ヨコ方向に4つの数の積を取る操作は、行単位で行えば良いので、[Int]型に対して先頭から順に積を計算する関数take4Prodを準備する。ネーミングセンスには目を瞑って欲しい。
こうなると、この関数 take4Prod :: [Int] -> [Int] を可能な限り再利用したくなる。そこで数字をタテやナナメに4つ拾って積を求める関数を作る代わりに、与えられた20×20の数列を並び替えて、take4Prodだけでことを済ませることを考える。
まずはgridsを転置する関数。転置とは行列を対角線で入れ替える操作、つまり
[[x1,x2,x3],
[y1,y2,y3],
[z1,z2,z3]]'
を
[[x1,y1,z1],
[x2,y2,z2],
[x3,y3,z3]]'
にする操作である。 英語では転置をtransposeという。
ややこしいのでtransposeの働きを例で示す；
transpose [[x1,x2,x3],[y1,y2,y3],[z1,z2,z3]]
---> zipWith (:) [x1,x2,x3] (transpose [[y1,y2,y3],[z1,z2,z3]])
---> zipWith (:) [x1,x2,x3] (zipWith (:) [y1,y2,y3] (transpose [z1,z2,z3]))
---> zipWith (:) [x1,x2,x3] (zipWith (:) [y1,y2,y3] [[z1],[z2],[z3]])
---> zipWith (:) [x1,x2,x3] [[y1,z1],[y2,z2],[y3,z3]]
---> [[x1,y1,z1],[x2,y2,z2],[x3,y3,z3]]
この関数を作って何が嬉しいかというと、これでタテに4つ並んだ数の積もtake4Prodで処理することができるのだ。
すると次はナナメに並ぶ要素をリストにした「リストのリスト」を作る関数が欲しくなる。どいういうことかというと
[[x1,x2,x3],
[y1,y2,y3],
[z1,z2,z3]]
---> [[x1,y2,z3],[x2,y3],[x3],[y1,z2],[z1]]
と作用する['[Int]] -> ['[Int]]型の関数だ。これができれば、やはりtake4Prodで処理できる。
そのためには、行列の対角線を拾う関数diagと、それを使って上三角成分を拾う関数diagsRight'が必要。
なぜこれだけで良いかと言うと、もとの数字列 grids に対して diagsRight' . transpose で下三角成分を拾えるし、grids の要素を右斜め下に向かって数字を拾う関数ができれば、 grids の各行を reverse して同様の操作をすることで、左斜め下に向かって数字を拾う操作になるからである。
以上を踏まえて、全コードを下に示す。ハッキリ言って、座標を使えばもっと簡単にできたと思う。でも関数型っぽさにこだわりたかったのである。
お疲れさま…☆
