Namaran

Code daily. Without assist.

2026-11-07

Knights.hs

import Data.Array

main :: IO ()
main = print (sum [grid ! q | p <- indices grid, q <- jumps p, inRange (bounds grid) q])
 where
  grid = listArray ((1, 1), (20, 30)) (repeat 1) :: Array (Int, Int) Int
  jumps (i, j) = [(i + di, j + dj) | (di, dj) <- moves]
  moves = [(a, b) | a <- [-2, -1, 1, 2], b <- [-2, -1, 1, 2], abs a /= abs b]

これは何を出力するでしょうか?

Answer

Output

4216

grid は添字が (1, 1) から (20, 30) までの600マスで、どのマスにも1が入っています。moves は、縦と横のずれの大きさが1と2、または2と1になる8通りで、チェスのナイトの動きです。内包表記は、マス p と跳び先 q の組のうち、inRange (bounds grid) q で盤の中に収まるものだけについて grid ! q の1を足すので、出力は盤の中に収まる跳び方の数です。(!) は添字が範囲の外なら実行時エラーにするので、この条件が無ければ盤の端で止まります。

マスごとに跳び先を数えると、端からの距離によって2、3、4、6、8通りと場合が細かく分かれます。足す順序を入れ替え、跳び方ごとに「その跳び方で盤の中に着地できるマスの数」を数えると簡単になります。縦に1、横に2ずれる跳び方なら、出発できる行は20行のうち19行、列は30列のうち28列で、向きによらず 19 × 28 = 532 マスです。縦に2、横に1ずれる跳び方は 18 × 29 = 522 マスです。それぞれ向きが4通りずつあるので、合計は 4 × 532 + 4 × 522 = 2128 + 2088 = 4216 です。

条件を読み飛ばして全マスから8方向とすると 600 × 8 = 4800 になり、盤の外に出る584通りを数えすぎます。跳び方ごとの数がマスの数の掛け算で求まるのは、添字の組 (i, j) に対する inRange が、i と j がそれぞれ自分の範囲に入っているかを別々に調べるからです。縦のずれで残る行の数と、横のずれで残る列の数を掛ければ、着地できるマスの数になります。