Instantly share code, notes, and snippets.

# ericnormand/00 Dueling Knights.md

Last active Oct 6, 2021

Dueling Knights

A chess board has nothing but knights ♞ and empty spaces. In this setup, the color of the knights doesn't matter. Each knight could potentially capture any other. Your job is to write a function to figure out which knights can capture each other, if any.

A board is represented as a vector of vectors, each 8 elements long. A `0` represents an empty square. A `1` represents a knight. Your function should return a collection of pairs. The pairs represent the positions of the two knights that can capture each other.

For reference, see this site for understanding how knights move and capture.

Examples

```(captures [[0 0 0 1 0 0 0 0]
[0 0 0 0 0 0 0 0]
[0 1 0 0 0 1 0 0]
[0 0 0 0 1 0 1 0]
[0 1 0 0 0 1 0 0]
[0 0 0 0 0 0 0 0]
[0 1 0 0 0 0 0 1]
[0 0 0 0 1 0 0 0]]) ;=> [] ;; no captures

(captures [[0 0 0 1 0 0 0 0]
[0 0 0 0 0 0 0 0]
[0 0 0 0 1 0 0 0]
[0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0]]) ;=> [#{[0 3] [2 4]}] ;; one capture

(captures [[0 0 0 1 0 0 0 0]
[0 0 0 0 0 0 0 0]
[0 0 0 0 1 0 0 0]
[0 0 1 0 0 0 0 0]
[0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0]]) ;=> [#{[0 3] [2 4]} #{[2 4] [3 2]}] ;; two capture```

Thanks to this site for the problem idea, where it is rated Very Hard in PHP. The problem has been modified.

### mchampine commented Oct 6, 2021 • edited

```(defn movesfornight [kpos]
(letfn [(padd [[a1 a2] [b1 b2]] [(+ a1 b1) (+ a2 b2)])]  ;; pairwise add
(map #(padd kpos %) [[1 -2] [1 2] [2 -1] [2 1]])))

(defn captures [brd]
(letfn [(isknight? [[x y]] (= (get (get brd x) y) 1))
(kck [kpos] (seq (map hash-set (repeat kpos)
(filter isknight? (movesfornight kpos)))))]
(let [npos (filter isknight? (for [x (range 8) y (range 8)] [x y]))]
(into [] (distinct (apply concat (mapv kck npos)))))))```

### KingCode commented Oct 6, 2021 • edited

Added captures for other pieces as well:

```(defn abs [x]
(if (neg? x) (- x) x))

(defn dueling-pred [row+col-diffs]
(fn [[r1 c1] [r2 c2]]
(some (fn [[dr dc]]
(and (= dr (abs (- r2 r1)))
(= dc (abs (- c2 c1)))))
row+col-diffs)))

(defn captures
([board] ;; knight captures by default
(captures board (dueling-pred [[1 2] [2 1]])))
([board dueling?]
(let [rowsiz (count board)
colsiz (count (first board))]
(for [i (range rowsiz)
j (range colsiz)
:when (pos? (get-in board [i j]))
i' (range i rowsiz)
j' (range colsiz)
:let [base [i j] other [i' j']]
:when (and (if (= i i') (< j j') true)
(pos? (get-in board other))
(dueling? base other))]
#{base other}))))

(defn diagonal-diffs [board]
(map vector (range 1 (count board)) (range 1 (count (first board)))))

(defn grid-diffs [board]
(concat (map vector (repeat 0) (range 1 (count board)))
(map vector (range 1 (count (first board))) (repeat 0))))

(defn line-diffs [board]
(concat (diagonal-diffs board) (grid-diffs board)))

(defn captures-bishops [board]
(captures board (dueling-pred (diagonal-diffs board))))

(defn captures-rooks [board]
(captures board (dueling-pred (grid-diffs board))))

(defn captures-queens [board]
(captures board (dueling-pred (line-diffs board))))

(def mixed-board [[0 0 0 1 0 0 0 0]
[0 0 0 0 0 0 0 0]
[0 0 0 0 1 0 0 0]
[0 0 1 0 0 0 1 0]
[0 0 0 0 0 0 0 0]
[0 0 0 0 1 0 0 0]
[0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0]])

(captures mixed-board) ;=> (#{[0 3][2 4]} #{[2 4][3 2]} #{[2 4][3 6]}])
(captures-bishops mixed-board) ;=> (#{[0 3][3 6]} #{[3 2][5 4]} #{[3 6][5 4]}])
(captures-rooks mixed-board) ;=>(#{[2 4][5 4]} {[3 2][3 6]})
(= (into #{} (concat (captures-bishops mixed-board)
(captures-rooks mixed-board)))
(set (captures-queens mixed-board))) ;;=> true```