Go Counting in Clojure: Complete Solution & Deep Dive Guide
Mastering Graph Traversal: The Complete Guide to Go Board Counting in Clojure
This guide provides a comprehensive solution for calculating territory on a Go board using Clojure. We'll explore how to model the board, implement a Breadth-First Search (BFS) algorithm to identify contiguous empty regions, and determine ownership based on surrounding stones, turning a classic game problem into a practical lesson in graph theory.
You’ve stared at the seemingly simple grid of a Go board, a canvas of black and white stones. The rules are elegant, yet determining the final score—calculating the territory captured by each player—presents a surprisingly complex computational challenge. This isn't just about a game; it's a problem that mirrors real-world scenarios like flood fill in image editing software, analyzing network connectivity, or even mapping contagious disease spread.
Many developers might reach for imperative loops and mutable state, but this often leads to complex, error-prone code. What if there was a more elegant, robust way? This is where Clojure shines. In this deep dive, we will dissect this fascinating problem and build a solution from the ground up, leveraging Clojure's functional paradigm, immutable data structures, and powerful abstractions to write code that is not only correct but also clear and concise.
What is the Go Territory Counting Problem?
At its core, the Go counting problem is an exercise in computational geometry and graph traversal. The goal is to analyze a snapshot of a Go board at the end of a game and assign ownership to empty intersections, which form the "territory" that ultimately determines the winner.
The Core Objective
The problem, as presented in the kodikra Clojure 9 learning path, asks us to perform two main tasks:
- Calculate Territories: Identify all distinct, contiguous groups of empty intersections on the board. For each group, determine if it is exclusively surrounded by one player's stones. If so, that group becomes that player's territory.
- Determine Specific Territory: Given a specific coordinate on the board, identify which territory (if any) it belongs to.
We operate under a key assumption: all "dead" stones (those stranded in enemy territory) have already been removed. This simplifies the problem significantly, allowing us to focus purely on the ownership of empty spaces.
Input and Output
The input is typically a representation of the board, such as a list of strings, where each character represents the state of an intersection:
'B'for a Black stone'W'for a White stone' '(space) for an empty intersection
The desired output is a data structure, like a Clojure map, that associates each player (e.g., :black, :white) with a set of coordinates representing their captured territory. Neutral, unowned territories (known as "dame") should also be accounted for.
; Example Input Board (5x5)
(def board-strings
[" B W "
"B W W"
"B W"
" W B "
" B "])
; Desired Output
'{:black #{[0 0] [1 3] [2 1] [2 2] [3 0] [3 2] [4 0] [4 3] [4 4]}
:white #{[0 2] [0 4] [1 1] [3 4]}
:none #{[0 3] [2 3] [4 1]}}
The fundamental challenge is to programmatically define what "contiguous" and "surrounded" mean. This is where algorithms designed for graphs and grids become indispensable.
Why Clojure is a Perfect Fit for Grid and Graph Problems
While you could solve this problem in any language, Clojure's design philosophy offers distinct advantages that lead to a more elegant and robust solution. Its functional, data-oriented approach naturally aligns with the logic of traversing and analyzing a static board state.
Immutability by Default
The state of the Go board at the end of the game is fixed. Clojure’s immutable data structures ensure that once we parse the board into a map or vector, it cannot be accidentally changed. When we explore the board, we don't modify the board itself; instead, we build up new data structures (like a set of visited coordinates) to track our progress. This eliminates a whole class of bugs related to state management and makes the logic easier to reason about.
Powerful Data Structures and Abstractions
Clojure provides a rich set of core data structures that are perfectly suited for this task. We can model the board as a map where keys are [x y] coordinate vectors and values are keywords like :B, :W, or :E (Empty). This is far more flexible than a 2D array.
Furthermore, functions like map, filter, reduce, and for allow us to express complex transformations and queries on these data structures concisely. For instance, getting all empty coordinates is a simple one-liner, not a nested loop.
Functional Approach to Traversal
Graph traversal algorithms like Breadth-First Search (BFS) or Depth-First Search (DFS) can be implemented beautifully using functional constructs. A recursive function or a loop/recur structure can manage the traversal state (like the queue of nodes to visit and the set of already visited nodes) without any mutable variables. Each step of the traversal produces a new state, passing it to the next iteration, which is a core tenet of functional programming.
How to Implement the Territory Calculation Algorithm
Our strategy will be to treat the grid of empty intersections as a graph. Each empty point is a node, and an edge exists between two nodes if they are adjacent (horizontally or vertically). We will explore each connected component (a territory) of this graph, identify its boundaries, and determine its owner.
We'll use a Breadth-First Search (BFS) algorithm, which is an excellent choice for exploring all reachable nodes from a starting point level by level.
The High-Level Plan
Our algorithm can be broken down into a clear sequence of steps. This workflow ensures we systematically analyze every part of the board without missing any territories or double-counting intersections.
● Start
│
▼
┌───────────────────────────┐
│ 1. Parse Input to Board Map │
│ (e.g., `{[x y] :stone}`) │
└────────────┬──────────────┘
│
▼
┌───────────────────────────┐
│ 2. Find All Empty Coords │
│ And Initialize State │
│ (visited set, results map)│
└────────────┬──────────────┘
│
▼
◆ Loop: Any unvisited empty coords remain?
╱ ╲
Yes No
│ │
▼ ▼
┌────────────────────────┐ ┌────────────────┐
│ 3. Pick an Unvisited │ │ 5. Return Final│
│ Empty Coord as Start│ │ Territories │
└────────────┬───────────┘ └────────┬───────┘
│ │
▼ ● End
┌────────────────────────┐
│ 4. Run BFS from Start │
│ - Find all connected│
│ empty coords │
│ - Find all bordering│
│ stone colors │
│ - Update visited set│
│ - Determine owner │
│ - Store territory │
└────────────┬───────────┘
│
└─────────────> Back to Loop
Step 1: Modeling the Board
First, we need to transform the input strings into a more useful data structure. A map from coordinates [x y] to keywords :B, :W, or :E is ideal. This allows for constant-time lookup of any intersection's state.
(defn parse-board [board-strings]
(into {}
(for [y (range (count board-strings))
x (range (count (first board-strings)))
:let [stone (get-in board-strings [y x])]]
{[x y] (case stone
\B :B
\W :W
\space :E)})))
Step 2: The Breadth-First Search (BFS) Core
This is the heart of our solution. For a given starting empty coordinate, the BFS will explore outwards to find all connected empty coordinates and simultaneously record the colors of any stones it bumps into along the boundary.
The BFS needs three key pieces of state to manage its exploration:
- A queue of coordinates to visit next. We start with just our initial coordinate.
- A set of visited coordinates to avoid infinite loops and redundant work.
- A structure to accumulate results: the set of coordinates in the current territory and the set of unique stone colors bordering it.
We'll use Clojure's loop/recur to implement the BFS iteratively without mutable state. In each step, we'll dequeue a coordinate, examine its neighbors, and update our state for the next iteration.
Step 3: Determining Ownership
Once the BFS for a territory is complete, it will return the set of coordinates in that territory and the set of unique bordering stone colors (e.g., #{:B}, #{:W}, or #{:B :W}).
The ownership logic is simple:
- If the bordering set contains only
:B, the territory belongs to Black. - If it contains only
:W, the territory belongs to White. - If it contains both
:Band:W(or is empty, for a territory filling the whole board), it is neutral ("dame").
Step 4: Orchestrating the Full Scan
The final piece is a main function that iterates through all coordinates on the board. If it finds an empty coordinate that we haven't visited yet, it kicks off the BFS from that point. The results from each BFS run (each territory) are collected, and the `visited` set is updated to ensure we don't re-scan the same territory.
The Complete Clojure Solution and Code Walkthrough
Now, let's assemble these concepts into a complete, working Clojure solution. The code is structured into small, focused helper functions that compose together to solve the larger problem.
The Full Code
(ns go-counting
(:require [clojure.set :as set]))
(defn- parse-board
"Converts a vector of board strings into a map of {[x y] -> :B, :W, or :E}."
[board-strings]
(when (and (seq board-strings) (seq (first board-strings)))
(into {}
(for [y (range (count board-strings))
x (range (count (first board-strings)))]
{[x y] (case (get-in board-strings [y x])
\B :B
\W :W
\space :E)}))))
(defn- neighbors
"Returns the four cardinal neighbors of a given coordinate [x y]."
[[x y]]
[[(dec x) y] [(inc x) y] [x (dec y)] [x (inc y)]])
(defn- bfs-explore-territory
"Performs a Breadth-First Search from a start coordinate to find a
contiguous territory and its bordering stone owners."
[board start-coord]
(loop [queue (conj clojure.lang.PersistentQueue/EMPTY start-coord) ; Use a proper queue
visited #{start-coord}
territory #{start-coord}
owners #{}]
(if-let [current (peek queue)]
(let [new-neighbors (->> (neighbors current)
(remove visited))]
(let [exploration-results (reduce
(fn [acc neighbor-coord]
(if-let [stone-type (get board neighbor-coord)]
(case stone-type
:E (-> acc
(update :queue conj neighbor-coord)
(update :visited conj neighbor-coord)
(update :territory conj neighbor-coord))
; It's a stone, so it's an owner
(update acc :owners conj stone-type))
acc)) ; Ignore off-board neighbors
{:queue (pop queue)
:visited visited
:territory territory
:owners owners}
new-neighbors)]
(recur (:queue exploration-results)
(:visited exploration-results)
(:territory exploration-results)
(:owners exploration-results))))
;; Queue is empty, traversal is complete
{:territory territory, :owners owners})))
(defn- determine-owner
"Determines the owner keyword based on a set of bordering stones."
[owners]
(cond
(= owners #{:B}) :black
(= owners #{:W}) :white
:else :none))
;; Public API Functions
(defn territory
"Calculates the territory for a specific coordinate."
[board-strings [x y :as coord]]
(let [board (parse-board board-strings)]
(when (nil? (get board coord))
(throw (Exception. "Invalid coordinate")))
(if (= :E (get board coord))
(let [{:keys [territory owners]} (bfs-explore-territory board coord)]
{:owner (determine-owner owners)
:stones territory})
{:owner nil, :stones #{}})))
(defn territories
"Calculates all territories on the board."
[board-strings]
(let [board (parse-board board-strings)]
(if-not board
{:black #{}, :white #{}, :none #{}}
(loop [coords (keys board)
visited #{}
results {:black #{}, :white #{}, :none #{}}]
(if-let [coord (first coords)]
(if (or (visited coord) (not= :E (get board coord)))
(recur (rest coords) visited results)
(let [{:keys [territory owners]} (bfs-explore-territory board coord)
owner (determine-owner owners)]
(recur (rest coords)
(set/union visited territory)
(update results owner set/union territory))))
results)))))
Detailed Walkthrough
1. `parse-board`
This function is our entry point for data transformation. It takes the raw `board-strings` and uses a `for` comprehension to iterate over every `x` and `y` index. The `get-in` function safely retrieves the character at `[y x]`. A `case` statement then cleanly maps the characters `\B`, `\W`, and ` ` to the more descriptive keywords :B, :W, and :E. The result is a single map representing the entire board state, which is efficient for lookups.
2. `neighbors`
A simple but crucial helper. Given a coordinate like `[5 5]`, it returns its four direct neighbors: `[4 5]`, `[6 5]`, `[5 4]`, and `[5 6]`. It doesn't perform any bounds checking; that responsibility is left to the caller, who can simply check if a neighbor exists as a key in our `board` map.
3. `bfs-explore-territory` (The Core Engine)
This function is where the magic happens. Let's visualize its flow.
● Start bfs-explore-territory(board, start-coord)
│
▼
┌─────────────────────────────────────────────────────────┐
│ Initialize State: │
│ - queue: [start-coord] │
│ - visited: #{start-coord} │
│ - territory: #{start-coord} │
│ - owners: #{} │
└──────────────────────┬──────────────────────────────────┘
│
▼
◆ Loop: Is queue empty?
╱ ╲
No Yes
│ │
▼ ▼
┌──────────────────┐ ┌──────────────────────────────────┐
│ Dequeue `current`│ │ Traversal complete. │
└────────┬─────────┘ │ Return {:territory, :owners} │
│ └──────────────────┬───────────────┘
▼ ● End
┌──────────────────────────────────┐
│ For each valid, unvisited │
│ `neighbor` of `current`: │
└────────────────┬─────────────────┘
│
▼
◆ What is neighbor's type?
├───────────┬───────────┐
▼ ▼ ▼
Empty(:E) Stone(:B/:W) Off-board
│ │ │
┌───────┴───────┐ ┌─┴──────────┐│
│ - Enqueue it │ │ - Add its ││
│ - Add to │ │ color to ││
│ `visited` │ │ `owners` ││
│ - Add to │ │ set ││
│ `territory` │ │ ││
└───────────────┘ └────────────┘│
│ │ │
└───────────┼───────────┘
▼
┌──────────────────────────────────┐
│ Recur with updated state │
│ (new queue, visited, etc.) │
└──────────────────────────────────┘
The loop/recur construct is Clojure's idiomatic way to perform iteration or recursion without consuming stack space. We start with a queue containing only the `start-coord`. In each iteration, we take an item off the queue (`peek` and `pop`). We then find its unvisited neighbors. For each neighbor, we check its status on the `board` map:
- If it's empty (
:E), we add it to our `queue` to visit later, to our `visited` set so we never process it again, and to our `territory` set. - If it's a stone (
:Bor:W), we don't traverse it, but we add its color to our `owners` set. This is how we find the boundary. - If it's `nil` (off the board), we ignore it.
4. `territories` (The Orchestrator)
This function drives the entire process. It initializes an empty `results` map and an empty `visited` set. It then loops through all coordinates of the board. For each coordinate, it checks three things:
- Have we already visited this coordinate as part of a previous territory scan?
- Is this coordinate an empty space?
If the coordinate is an unvisited empty space, it means we've found a new, unexplored territory. We then call `bfs-explore-territory` to map it out completely. The result (the territory and its owners) is used to update our main `results` map, and all coordinates of the newly found territory are added to the `visited` set. The loop continues until all coordinates have been considered.
Alternative Approaches and Considerations
While BFS is a solid and intuitive choice, it's not the only way to solve this problem. Understanding the alternatives helps in building a more robust mental model of graph algorithms.
Depth-First Search (DFS)
Depth-First Search is the sibling algorithm to BFS. Instead of exploring level by level, DFS goes as deep as possible down one path before backtracking.
Implementation Change: The only practical change in our code would be to treat our "queue" as a "stack". Instead of adding new items to the back (enqueue) and taking from the front (dequeue), we would add to the front (push) and take from the front (pop). In Clojure, using a vector with `conj` (add to end) and `peek`/`pop` (take from end) effectively makes it a stack.
Pros and Cons: BFS vs. DFS for Go Counting
| Aspect | Breadth-First Search (BFS) | Depth-First Search (DFS) |
|---|---|---|
| Algorithm | Explores neighbors level by level. Uses a queue. | Explores as far as possible along each branch before backtracking. Uses a stack. |
| Memory Usage | Can use more memory for "wide" territories, as the queue can grow large. | Can use more memory for "deep" or "long" territories, as the recursion/stack depth can grow. Generally more memory-efficient for this problem. |
| Pathfinding | Guaranteed to find the shortest path (in terms of edges) from the start node. Not relevant for our problem. | Does not guarantee the shortest path. Path can be long and meandering. |
| Complexity | For this problem, the implementation complexity is virtually identical to DFS. | Can be slightly more intuitive to implement recursively, but the `loop/recur` approach is similar for both. |
| Verdict for Go Counting | Excellent choice. Its systematic, level-by-level exploration is easy to visualize and debug. | Equally valid choice. The order of exploration doesn't change the final result (the set of all connected nodes). |
For this specific problem, since we need to explore the *entire* connected component, both algorithms will visit the exact same set of nodes and produce the identical result. The choice between them is largely a matter of style or minor performance trade-offs in specific edge cases.
Frequently Asked Questions (FAQ)
- Why use a graph traversal algorithm like BFS/DFS instead of just iterating with loops?
-
Simple nested loops can only check immediate neighbors. They can't determine if two empty points on opposite sides of a region are part of the same "contiguous" territory. Graph traversal algorithms are specifically designed to answer this connectivity question by systematically exploring all reachable nodes from a starting point.
- How does this solution handle "dame" (neutral points)?
-
The ownership logic naturally handles this. A territory is considered "dame" or neutral if its boundary contains stones of both Black and White players. Our
bfs-explore-territoryfunction collects all unique bordering stone colors. Thedetermine-ownerfunction checks this set. If the set is#{:B :W}, it correctly assigns the owner as:none. - Is this algorithm efficient enough for a full-size 19x19 Go board?
-
Yes, absolutely. The time complexity of this approach is O(N), where N is the number of intersections on the board (e.g., 19x19 = 361). Each intersection is visited a constant number of times throughout the entire process. This is highly efficient and will run virtually instantaneously even on large boards.
- What are the benefits of using an immutable map for the board state?
-
Immutability prevents accidental modification of the board state during traversal, which is a common source of bugs in imperative solutions. It makes the code easier to reason about, test, and even parallelize, as there are no shared mutable states to worry about.
- How do you handle coordinates that are off the board?
-
Our `bfs-explore-territory` function handles this gracefully. When checking neighbors, it uses `(get board neighbor-coord)`. If `neighbor-coord` is outside the board's boundaries, it won't be a key in the `board` map, and `get` will return `nil`. The logic then simply ignores this `nil` result and moves on, effectively treating the board's edge as a boundary.
- Can this logic be adapted for other grid-based problems?
-
Definitely. This BFS/DFS on a grid pattern is a fundamental technique. It can be used for solving mazes, "bucket fill" tools in paint programs, finding connected components in any grid, pathfinding for games (like in Pac-Man), and many other problems in computer graphics and logistical analysis.
Conclusion: From Game Logic to Core Concepts
We've successfully journeyed from the abstract rules of a Go game to a concrete, efficient, and elegant implementation in Clojure. By modeling the board as a map and treating empty intersections as nodes in a graph, we transformed the problem into a classic traversal task. The use of Breadth-First Search, managed with Clojure's immutable data structures and functional `loop/recur` construct, provided a solution that is both robust and easy to understand.
This module from the kodikra learning curriculum is more than just a coding exercise; it's a practical application of fundamental computer science principles. The skills you've honed here—graph traversal, state management with immutability, and functional problem-solving—are universally applicable and highly valuable in modern software development.
As you continue your journey, you'll find this pattern of thinking—breaking down a problem into data transformations and pure functions—to be one of the most powerful tools in your arsenal. To further solidify your understanding, dive deeper into Clojure with our other guides and see how these concepts apply to an even wider range of challenges.
Disclaimer: The solution provided is based on Clojure 1.11+. While the core logic is stable, specific function availability and performance characteristics may vary slightly between language versions.
Published by Kodikra — Your trusted Clojure learning resource.
Post a Comment