Spiral Matrix in Common-lisp: Complete Solution & Deep Dive Guide

a close up of a computer screen with code on it

The Complete Guide to Building a Spiral Matrix in Common Lisp

Generating a spiral matrix is a classic algorithmic puzzle that elegantly tests your understanding of array manipulation, state management, and boundary detection. This guide provides a comprehensive walkthrough in Common Lisp, showing how to create a square matrix filled with numbers in a clockwise, inward spiral, starting from 1 in the top-left corner.

The Treasure Map in the Code

Imagine you're an explorer named Elara. You've just found an ancient document describing the path to a hidden treasure. The instructions aren't a simple "X marks the spot." Instead, they describe a peculiar, winding path: "Start at the northernmost edge, walk east until you can go no further. Then, turn south until you must stop. Turn west, then north, and continue this inward spiral until you reach the center."

You realize this isn't just a path; it's an algorithm. The forest is a grid, and the instructions are a set of rules for navigating it. This is precisely the challenge developers face with the spiral matrix problem. It feels abstract, but at its core, it's about translating a set of movement rules into a concrete, data-filled structure. If you've ever felt stuck trying to visualize how to command a program to "turn" at a "wall," this guide is the map you've been looking for. We'll turn that confusing spiral into a clear, logical path, one line of Common Lisp at a time.

What Exactly is a Spiral Matrix?

A spiral matrix is a square (N x N) 2D array, or grid, filled with sequential numbers from 1 to N². The numbers are arranged in a clockwise spiral pattern that starts from the top-left corner and coils inwards towards the center of the matrix.

It's a fantastic exercise for practicing array traversal and algorithmic thinking. The core challenge lies not in placing the numbers themselves, but in programmatically controlling the direction of placement.

For a clear visual, consider these examples:

Example: Spiral Matrix of Size 3

Example: Spiral Matrix of Size 4


 1 →  2 →  3 → 4
             ↓
12 → 13 → 14   5
 ↑         ↓   ↓
11   16 ← 15   6
 ↑             ↓
10 ←  9 ←  8 ← 7

The pattern is consistent: move right, then down, then left, then up, shortening the path length after each turn until the matrix is completely filled.

Why is this Algorithm a Cornerstone of Programming?

While you might not be asked to generate a spiral matrix in your day-to-day work, mastering the underlying concepts is incredibly valuable. This problem is a microcosm of more complex challenges found in various domains:

Technical Interviews: It's a favorite at top tech companies because it effectively assesses a candidate's ability to handle coordinates, state changes, edge cases, and 2D data structures.
Game Development: Algorithms for procedural generation, pathfinding (like A*), and character movement often involve similar grid traversal and boundary detection logic.
Image and Data Processing: Certain image filtering or data scanning algorithms might process pixels or data points in a non-linear, spiral pattern to analyze local neighborhoods of data.
Robotics and Pathing: A robot cleaning a room or a CNC machine cutting a pattern might use a spiral path for maximum coverage and efficiency.

By solving this, you're not just filling a grid with numbers; you're building a mental model for navigating any 2D space algorithmically. For those on the path to master the fundamentals of Common Lisp, this module from the kodikra.com curriculum is a perfect practical test.

How to Construct the Spiral: The Core Logic

Before diving into code, let's conceptualize the solution. The most intuitive way to solve this is to simulate the process of "drawing" the spiral. Imagine a pen (or a cursor) moving across a grid, leaving a trail of increasing numbers.

This "simulation" approach requires us to track three key pieces of state at all times:

Current Position: The (row, col) coordinates of our cursor.
Current Direction: The direction we are currently moving (e.g., Right, Down, Left, or Up).
The Grid Itself: The matrix we are filling, which also helps us know where we've already been.

The algorithm then becomes a simple loop that runs N² times (once for each number):

Place the current number at the current (row, col) position.
Determine the next position by moving one step in the current direction.
Check if a turn is needed: A turn is required if the next position is either outside the grid boundaries OR lands on a cell that has already been filled.
If a turn is needed, update the current direction (e.g., from Right to Down).
Update the current position to the new location.
Increment the number and repeat.

Visualizing the Simulation Flow

Here is a minimalist flow diagram illustrating the decision-making process inside the main loop for each number we place in the matrix.

    ● Start Loop (for number `i`)
    │
    ▼
  ┌──────────────────────────┐
  │ Place `i` at current pos │
  └────────────┬─────────────┘
               │
               ▼
  ┌──────────────────────────┐
  │ Calculate next potential │
  │ position based on        │
  │ current direction        │
  └────────────┬─────────────┘
               │
               ▼
    ◆ Is a turn needed?
   ╱  (Out of bounds OR cell filled)
  Yes ╲
  │    No
  │     │
  ▼     │
┌──────────────┐
│ Update       │
│ direction to │
│ next in cycle│
│ (e.g. R → D) │
└──────┬───────┘
       │
       └───────────┐
                   │
                   ▼
  ┌──────────────────────────┐
  │ Update current position  │
  │ to the next valid spot   │
  └────────────┬─────────────┘
               │
               ▼
    ● End Loop Iteration

Where the Magic Happens: The Common Lisp Implementation

Now, let's translate this logic into idiomatic Common Lisp. The solution from the kodikra.com learning path is particularly elegant, using a circular list to manage directions and higher-order functions to handle coordinates.

The Complete Code

Here is the full solution. We will break it down piece by piece right after.


(defpackage :spiral-matrix
  (:use :cl)
  (:export :spiral-matrix))

(in-package :spiral-matrix)

(defun turnp (matrix index delta size)
  "Predicate to check if a turn is needed.
   Checks for out-of-bounds or if the next cell is already filled."
  (let ((look-ahead (mapcar #'+ index delta)))
    (or (< (first look-ahead) 0)      ; Row is out of bounds (top)
        (< (second look-ahead) 0)     ; Col is out of bounds (left)
        (= size (first look-ahead))   ; Row is out of bounds (bottom)
        (= size (second look-ahead))  ; Col is out of bounds (right)
        (apply #'aref matrix look-ahead)))) ; Cell is already filled

(defun spiral-matrix (size)
  "Generates a square spiral matrix of a given size."
  (when (plusp size)
    (let ((cycler '#0=((0 1) (1 0) (0 -1) (-1 0) . #0#)) ; Right, Down, Left, Up
          (matrix (make-array (list size size) :initial-element nil))
          (index '(0 0))
          (delta '(0 1))) ; Start by moving right
      (loop for i from 1 to (* size size)
            do (setf (apply #'aref matrix index) i)
               (when (turnp matrix index delta size)
                 (setf cycler (cdr cycler)
                       delta (car cycler)))
               (setf index (mapcar #'+ index delta)))
      matrix)))

Code Walkthrough: `spiral-matrix` Main Function

This function orchestrates the entire process. Let's dissect its components.

(when (plusp size) ...)

This is a guard clause. If the requested size is zero or negative, it does nothing and returns NIL, which is a sensible default for an empty matrix.

(let (...) ...)

This sets up our local state variables for the simulation.

(cycler '#0=((0 1) (1 0) (0 -1) (-1 0) . #0#))

This is the most clever part of the solution. It defines a circular list named cycler. The #0=(... . #0#) syntax creates a data structure where the `cdr` (the rest of the list) of the last element points back to the beginning of the list itself. This creates an infinite cycle of directions.

(0 1): Move Right (Row doesn't change, Column increases by 1).
(1 0): Move Down (Row increases by 1, Column doesn't change).
(0 -1): Move Left (Row doesn't change, Column decreases by 1).
(-1 0): Move Up (Row decreases by 1, Column doesn't change).

By simply taking the cdr of this list, we effectively "rotate" to the next direction in the sequence.

(matrix (make-array (list size size) :initial-element nil))

This creates our N x N grid. make-array is the standard way to create arrays in Common Lisp. We initialize every cell with nil. This is crucial because nil evaluates to false in Lisp, which our turnp function will use to check if a cell is empty.

(index '(0 0)) and (delta '(0 1))

These initialize our starting state. The index is our cursor, starting at the top-left (0, 0). The delta is our initial direction vector, set to (0 1), which corresponds to moving Right.

(loop for i from 1 to (* size size) ...)

This is the main engine. The loop iterates from 1 up to N*N, which is the total number of cells in the matrix.

do (setf (apply #'aref matrix index) i)

This is where we place the number. aref is used to access an element of an array. Since aref expects separate arguments for each dimension (e.g., (aref matrix row col)), but our index is a list like '(0 0), we use apply to unpack the list into arguments for the function. This line effectively says: "Set the value at `matrix[row][col]` to `i`."

(when (turnp matrix index delta size) ...)

Here, we check if we need to turn *before* the next move. We pass the current state to our helper function turnp.

(setf cycler (cdr cycler) delta (car cycler))

If turnp returns true, we execute this block. (setf cycler (cdr cycler)) moves our pointer to the next element in the circular list. Then, (setf delta (car cycler)) updates our direction vector delta to this new direction. For instance, if we were moving Right, the cycler advances, and the new `delta` becomes (1 0), for Down.

(setf index (mapcar #'+ index delta))

Finally, we update our position. mapcar applies the + function element-wise to our two lists, index and delta. For example, if index is `(0 2)` and `delta` is `(1 0)` (Down), the new index becomes `(0+1, 2+0)`, which is `(1 2)`. This elegantly calculates the next coordinate.

matrix

After the loop completes, the let block's last expression is the populated matrix, which is implicitly returned by the function.

Code Walkthrough: `turnp` Helper Function

The `turnp` (turn predicate) function is a boolean helper that answers one question: "If I continue in my current direction, will I hit a wall or a path I've already taken?"

(let ((look-ahead (mapcar #'+ index delta))) ...)

First, it calculates the coordinates of the very next cell by adding the current index and delta, just as we do in the main loop. This is our "look-ahead" position.

(or ...)

The or macro checks a series of conditions and stops, returning true, as soon as it finds one that is true. This is efficient short-circuiting.

(< (first look-ahead) 0): Is the next row less than 0? (Top boundary).
(< (second look-ahead) 0): Is the next column less than 0? (Left boundary).
(= size (first look-ahead)): Is the next row equal to `size`? (Bottom boundary, since indices are 0 to `size-1`).
(= size (second look-ahead)): Is the next column equal to `size`? (Right boundary).
(apply #'aref matrix look-ahead): If none of the boundary checks are true, we check the cell itself. We access the value at the `look-ahead` position. If the cell has a number in it (anything other than our initial `nil`), this expression is truthy, and the or returns true. If the cell is still `nil`, this is falsey, and the check fails.

This function is a robust and concise way to handle all the conditions that necessitate a change in direction.

Visualizing the Data Flow

This diagram shows the conceptual flow of how the state (position, direction) is updated within the loop to populate the matrix.

    ● Start with `i = 1`, pos = (0,0), dir = Right
    │
    ▼
  ┌──────────────────┐
  │ Loop (i → N*N)   │
  └────────┬─────────┘
           │
           ├─ 1. Write `i` to matrix at `pos`
           │
           ├─ 2. Check `turnp(pos, dir)`
           │    │
           │    ├─ Yes? ⟶ Update `dir` using `cycler`
           │    │
           │    └─ No?  ⟶ Keep same `dir`
           │
           ├─ 3. Update `pos` using new/current `dir`
           │
           └─ 4. Increment `i` ⟶ Repeat
               │
               ▼
    ● Final Matrix

Algorithm Performance and Considerations

Understanding the efficiency of your code is crucial. For the spiral matrix algorithm, the analysis is straightforward.

Time Complexity: O(N²) - We must visit every single cell in the N x N grid exactly once to place a number. The main loop runs N² times, and the operations inside the loop (arithmetic, array access, function call) are all constant time operations, O(1). Therefore, the total time complexity is directly proportional to the number of cells.
Space Complexity: O(N²) - We need to create and store an N x N matrix in memory to hold the results. The space required grows quadratically with the input size `N`. This is unavoidable as the output itself is an N² element structure.

Pros and Cons of this Simulation Approach

Pros	Cons
Intuitive Logic: The code directly models the physical act of drawing a spiral, making it easier to reason about and debug.	State Management: Requires careful management of multiple state variables (index, delta, matrix, cycler), which can be complex.
Single Pass: The algorithm fills the matrix in a single pass without needing to revisit cells, making it highly efficient.	Not Easily Parallelizable: The calculation for each cell depends on the state of the previous one, making it an inherently sequential process.
Elegant in Lisp: Features like circular lists and `mapcar` allow for a very concise and expressive implementation in Common Lisp.	Less Obvious for Rectangles: Adapting this exact logic for a non-square (M x N) matrix requires more complex boundary checks.

This problem is a fantastic part of the Common Lisp Learning Roadmap on kodikra.com, as it perfectly blends algorithmic theory with practical, language-specific features.

Frequently Asked Questions (FAQ)

What is the time complexity of the spiral matrix algorithm?: The time complexity is O(N²), where N is the size of the matrix. This is because the algorithm must touch every one of the N² cells once to fill it with a number. It's considered an optimal solution as you cannot generate the output without visiting each cell.
Can this algorithm be adapted for a rectangular matrix?: Yes, it can, but the boundary conditions in the turnp function become more complex. Instead of a single size variable, you would need to track rows and cols. The turn logic would need to check against the specific boundary for the current direction of travel (e.g., check against cols when moving horizontally, and rows when moving vertically).
How does the circular list #0=(... . #0#) work in Common Lisp?: This is read-time syntax for creating circular data structures. #0= assigns a label (in this case, 0) to the list that follows. The . #0# at the end of the list's definition creates a `cons` cell where the `cdr` (the "rest" of the list) points back to the object labeled 0, which is the start of the list itself. This creates an infinite loop, perfect for cycling through a fixed set of states like directions.
Are there other ways to solve the spiral matrix problem?: Absolutely. Another common approach is the "layer-by-layer" method. You fill the outermost layer (top row, right column, bottom row, left column), then move inwards and fill the next layer, and so on, until you reach the center. This often involves four separate loops for each layer, nested inside a main loop that shrinks the boundaries.
Why is Common Lisp a good language for this kind of algorithmic problem?: Common Lisp excels at symbolic manipulation and handling complex data structures. Features like the powerful loop macro, higher-order functions (mapcar, apply), and the ability to easily create structures like circular lists allow for solutions that are both concise and highly expressive, often mirroring the abstract logic of the algorithm very closely.
What happens if the input size is 0 or 1?: The provided code handles these edge cases gracefully. If size is 0, (plusp size) is false, and the function returns NIL. If size is 1, the loop runs once for i = 1, places 1 at (0,0), and returns the 1x1 matrix, which is correct.
How can I visualize the matrix generation process for debugging?: To debug, you can add a print statement inside the main loop. After setting the value in the matrix, you could print the current number i, the index, the delta, and even the entire matrix state. This will give you a step-by-step trace of how the spiral is being constructed, making it easy to spot where the logic might be going wrong.

Conclusion: From Spiral Path to Clear Solution

The spiral matrix problem is more than just an academic exercise; it's a practical workout for the skills every developer needs: breaking down a complex problem, managing state, handling edge cases, and translating logic into clean code. By simulating the path of a cursor, we transformed an abstract requirement into a tangible, step-by-step process.

We saw how Common Lisp, with its powerful features like circular lists and functional constructs, provides an exceptionally elegant toolkit for this task. The final solution is not just correct; it's a testament to how choosing the right data structures can simplify your code and make the underlying logic shine through.

Whether you're preparing for a technical interview or simply honing your problem-solving skills, mastering this algorithm will undoubtedly make you a more confident and capable programmer.

Disclaimer: The code in this article is written for modern ANSI Common Lisp implementations. The logic and functions used are standard and should be portable across systems like SBCL, CCL, and others.

Published by Kodikra — Your trusted Common-lisp learning resource.

kodikra

Search this blog