amalloy-4clojure-solution124.clj

;; amalloy's solution to Analyze Reversi
;; https://4clojure.com/problem/124

(fn [board color]
  (let [;; we'll need to verify that we only "capture" enemy pieces
        enemy? #{('{b w, w b} color)}

        ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
        ;;; board/position related constants ;;;
        ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

        h (count board)
        w (count (first board))
        dims [h w]

        ;; all the [dy dx] pairs you could try "walking" to from a position
        neighbors (let [deltas [-1 0 1]]
                    ;; restricting the scope of deltas to where it is used
                    (for [y deltas, x deltas
                          :when (not= y x 0)]
                      [y x]))

        ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
        ;;; functions for getting board-based information from coordinates ;;;
        ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

        ;; is this position even on the board?
        valid? (fn [pos]
                 (every? true?
                         ;; here we make use of extra-arity map <
                         ;; map "expands" like (and (< -1 y h)
                         ;;                         (< -1 x w))
                         ;; with 3+ args, < tests "ascending", so we can pin
                         ;; y and x in the range of [0, max).
                         (map < [-1 -1] pos dims)))

        ;; who's at this location?
        piece #(get-in board %)
        ;; is this location empty?
        vacant? (comp #{'e} piece)

        ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
        ;;; Reversi-specific functions ;;;
        ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

        ;; given a position and a direction, "walk" in that direction until you
        ;; fall off the board, returning a seq of all the coordinates traversed
        pointer (fn [pos dir]
                  (->> pos
                       (iterate #(map + dir %))
                       (take-while valid?)))

        ;; Here is the heart of the algorithm. Given a position and a direction,
        ;; return a seq of all the positions that would be captured in that
        ;; direction by a play at the chosen position.
        ;; Inline comments would clutter things too much, but expect an
        ;; upcoming blog post breaking down what's going on.
        impacted (fn [pos dir]
                   (let [tokens (pointer pos dir)
                         [captured end] (split-with (comp not #{color} first)
                                                    (map (juxt piece identity)
                                                         (rest tokens)))]
                     (when (and (= color (ffirst end))
                                (every? (comp enemy? first) captured))
                       (map second captured))))]
    (into {}
          (for [;; find all the vacant positions on the board
                y (range h), x (range w), :let [pos [y x]]
                :when (vacant? pos)

                ;; for each one, check for captures in every direction
                :let [flipped (for [n neighbors]
                                (impacted pos n))]

                ;; if no direction has any captures, don't mention this position
                :when (some seq flipped)]
            ;; create a k/v pair of [position, (all-captured-pieces)]
            [pos (set (apply concat flipped))]))))