Home
4
Coding Tutorial

Twelve Days in Common-lisp: Complete Solution & Deep Dive Guide

man wearing black shirt

The Complete Guide to String Manipulation in Common Lisp: Solving The Twelve Days of Christmas

This guide provides a comprehensive solution for generating the "Twelve Days of Christmas" song lyrics using Common Lisp. We'll explore list processing, string formatting, and functional programming techniques by breaking down the problem, building an elegant solution, and analyzing the underlying Lisp concepts involved in this classic challenge.

Have you ever faced a programming problem that seemed simple on the surface but quickly spiraled into a messy web of conditionals and loops? Generating repetitive, yet slightly different, text patterns is a perfect example. You might start with a simple loop, but then you're bogged down by edge cases: the first verse is different, the list of items grows, and the punctuation needs to be perfect. It’s a common frustration that can make elegant code feel out of reach.

But what if this very challenge could unlock a deeper understanding of a language's core strengths? In this guide, we'll tackle the "Twelve Days of Christmas" song problem, a task perfectly suited to Common Lisp's powerful list manipulation and string formatting capabilities. We will transform this seemingly tedious task into a practical masterclass, showing you how to think in Lisp, structure data effectively, and write code that is not only correct but also concise and expressive. Prepare to move beyond basic loops and embrace the functional elegance of Lisp.

What is The "Twelve Days of Christmas" Challenge?

The core task, part of the exclusive kodikra.com curriculum, is to programmatically generate the complete lyrics for the English Christmas carol, "The Twelve Days of Christmas." The song has a unique cumulative structure: each verse repeats the gifts from all the previous verses.

For example, the third verse includes the gifts from the second and first verses. This cumulative pattern is the central challenge. The output must be a single string containing all twelve verses, formatted precisely as shown in the traditional lyrics.

The Complete Song Lyrics

Your code must produce the following text exactly, including all punctuation and line breaks.

On the first day of Christmas my true love gave to me: a Partridge in a Pear Tree.

On the second day of Christmas my true love gave to me: two Turtle Doves, and a Partridge in a Pear Tree.

On the third day of Christmas my true love gave to me: three French Hens, two Turtle Doves, and a Partridge in a Pear Tree.

On the fourth day of Christmas my true love gave to me: four Calling Birds, three French Hens, two Turtle Doves, and a Partridge in a Pear Tree.

On the fifth day of Christmas my true love gave to me: five Gold Rings, four Calling Birds, three French Hens, two Turtle Doves, and a Partridge in a Pear Tree.

On the sixth day of Christmas my true love gave to me: six Geese-a-Laying, five Gold Rings, four Calling Birds, three French Hens, two Turtle Doves, and a Partridge in a Pear Tree.

On the seventh day of Christmas my true love gave to me: seven Swans-a-Swimming, six Geese-a-Laying, five Gold Rings, four Calling Birds, three French Hens, two Turtle Doves, and a Partridge in a Pear Tree.

On the eighth day of Christmas my true love gave to me: eight Maids-a-Milking, seven Swans-a-Swimming, six Geese-a-Laying, five Gold Rings, four Calling Birds, three French Hens, two Turtle Doves, and a Partridge in a Pear Tree.

On the ninth day of Christmas my true love gave to me: nine Ladies Dancing, eight Maids-a-Milking, seven Swans-a-Swimming, six Geese-a-Laying, five Gold Rings, four Calling Birds, three French Hens, two Turtle Doves, and a Partridge in a Pear Tree.

On the tenth day of Christmas my true love gave to me: ten Lords-a-Leaping, nine Ladies Dancing, eight Maids-a-Milking, seven Swans-a-Swimming, six Geese-a-Laying, five Gold Rings, four Calling Birds, three French Hens, two Turtle Doves, and a Partridge in a Pear Tree.

On the eleventh day of Christmas my true love gave to me: eleven Pipers Piping, ten Lords-a-Leaping, nine Ladies Dancing, eight Maids-a-Milking, seven Swans-a-Swimming, six Geese-a-Laying, five Gold Rings, four Calling Birds, three French Hens, two Turtle Doves, and a Partridge in a Pear Tree.

On the twelfth day of Christmas my true love gave to me: twelve Drummers Drumming, eleven Pipers Piping, ten Lords-a-Leaping, nine Ladies Dancing, eight Maids-a-Milking, seven Swans-a-Swimming, six Geese-a-Laying, five Gold Rings, four Calling Birds, three French Hens, two Turtle Doves, and a Partridge in a Pear Tree.

Why Common Lisp is Perfect for This Problem

Common Lisp, with its "code-is-data" philosophy (homoiconicity) and powerful standard library, is exceptionally well-suited for tasks involving data transformation and generation. This problem isn't just about looping; it's about building and formatting lists of strings, a domain where Lisp has historically excelled.

  • List Processing: The core of the problem is managing a growing list of gifts. Lisp's built-in functions like subseq, reverse, cons, and mapcar make manipulating these lists trivial and expressive.
  • Powerful String Formatting: The FORMAT function in Common Lisp is a mini-language in itself. It can handle iteration, conditionals, and complex string interpolation directly within the format string, allowing for incredibly concise code that would require complex concatenation and logic in other languages.
  • Functional Paradigm: We can solve this problem by composing small, pure functions. One function can be responsible for getting the gifts for a day, another for formatting them, and a third for assembling a verse. This approach leads to code that is easier to test, debug, and understand.
  • REPL-Driven Development: The interactive nature of the Lisp REPL (Read-Eval-Print Loop) allows you to build and test each function incrementally. You can define your data, test your gift-formatting function, and build up the solution piece by piece, ensuring each component works perfectly before combining them.

Instead of fighting with string concatenation and off-by-one errors in loops, we can leverage these features to describe *what* we want the result to be, letting Lisp handle the *how*. Master Common Lisp with our complete guide to learn more about these foundational concepts.

How to Structure the Data and Logic

Before writing a single line of code, a good programmer thinks about the data. The song's structure is highly regular, which is a clear signal that we should store the repeating parts in data structures—specifically, lists.

Step 1: Define the Core Data

We need three pieces of information for each verse:

  1. The day number as an ordinal word (e.g., "first", "second").
  2. The quantity and name of the gift for that day (e.g., "a Partridge in a Pear Tree", "two Turtle Doves").

We can store these in two distinct lists. We'll use defparameter to define these as global constants. The indices of these lists will correspond to the day (minus one, as lists are zero-indexed).

(defparameter *ordinals*
  '("first" "second" "third" "fourth" "fifth" "sixth"
    "seventh" "eighth" "ninth" "tenth" "eleventh" "twelfth"))

(defparameter *gifts*
  '("a Partridge in a Pear Tree" "two Turtle Doves" "three French Hens"
    "four Calling Birds" "five Gold Rings" "six Geese-a-Laying"
    "seven Swans-a-Swimming" "eight Maids-a-Milking" "nine Ladies Dancing"
    "ten Lords-a-Leaping" "eleven Pipers Piping" "twelve Drummers Drumming"))

Step 2: Visualize the Logic Flow

The overall process for generating the full song can be broken down into a clear pipeline. For each day from 1 to 12, we need to assemble a single verse. Then, we combine all the verses.

Here's a high-level flow of the logic for generating the entire song:

    ● Start Song Generation
    │
    ▼
  ┌───────────────────┐
  │  Loop from Day 1  │
  │     to Day 12     │
  └─────────┬─────────┘
            │ For each Day `n`...
            ▼
  ┌───────────────────┐
  │ Generate Verse(n) │
  └─────────┬─────────┘
            │
            ▼
  ┌───────────────────┐
  │ Collect Verse(n)  │
  │   into a list     │
  └─────────┬─────────┘
            │
            ▼
  ┌───────────────────┐
  │   Join all verses │
  │ with double newline │
  └─────────┬─────────┘
            │
            ▼
    ● End: Final Song String

Now, let's zoom in on the most critical part: `Generate Verse(n)`. This itself is a multi-step process.

Step 3: Deconstruct Verse Generation

Generating a single verse requires a few distinct steps:

  1. Get the correct ordinal string (e.g., "third" for day 3).
  2. Get the cumulative list of gifts for that day. For day 3, this would be ["three French Hens", "two Turtle Doves", "a Partridge in a Pear Tree"].
  3. Format this list of gifts into a single string, handling the comma and the "and" correctly.
  4. Combine the ordinal and the formatted gift list into the final verse string.

This breakdown is crucial. It allows us to create small, focused helper functions, which is a hallmark of good functional programming style.

Here is the logic flow for creating a single verse:

    ● Start Verse Generation (for Day `n`)
    │
    ▼
  ┌──────────────────┐
  │ Get Ordinal(n-1) │ e.g., "third"
  └────────┬─────────┘
           │
           ▼
  ┌──────────────────┐
  │ Get Gifts(0..n-1)│ e.g., ("a P...", "two T...", "three F...")
  └────────┬─────────┘
           │
           ▼
  ┌──────────────────┐
  │  Reverse the list│ e.g., ("three F...", "two T...", "a P...")
  └────────┬─────────┘
           │
           ▼
  ┌──────────────────┐
  │ Format gift list │ Add commas and "and"
  └────────┬─────────┘
           │
           ▼
  ┌──────────────────┐
  │ Combine into the │ "On the third day..."
  │ final verse string │
  └────────┬─────────┘
           │
           ▼
    ● End: Single Verse String

This structured thinking, moving from high-level data definition to a detailed logical flow, sets us up perfectly to write clean and effective Common Lisp code.

The Complete Common Lisp Solution

Here is a complete, well-commented solution from the kodikra learning path. It follows the logical structure we designed above, using helper functions to maintain clarity and compose the final result.

We'll place our code within a package to avoid symbol conflicts, which is standard practice for any non-trivial Lisp project.

(defpackage :twelve-days
  (:use :cl)
  (:export :recite))

(in-package :twelve-days)

;;; Data Definitions
;;; We store the unique parts of the song in lists.
;;; The index corresponds to the day (0 for day 1, 1 for day 2, etc.).

(defparameter *ordinals*
  '("first" "second" "third" "fourth" "fifth" "sixth"
    "seventh" "eighth" "ninth" "tenth" "eleventh" "twelfth")
  "A list of ordinal strings for each day.")

(defparameter *gifts*
  '("a Partridge in a Pear Tree." "two Turtle Doves," "three French Hens,"
    "four Calling Birds," "five Gold Rings," "six Geese-a-Laying,"
    "seven Swans-a-Swimming," "eight Maids-a-Milking," "nine Ladies Dancing,"
    "ten Lords-a-Leaping," "eleven Pipers Piping," "twelve Drummers Drumming,")
  "A list of gift strings for each day.")

;;; Helper Functions

(defun get-gifts-for-day (day-number)
  "Returns the cumulative, reversed list of gifts for a given day number (1-12)."
  (let ((day-index (1- day-number)))
    ;; Take a subsequence of the gifts from the beginning up to the current day.
    ;; Reverse it to get the correct lyrical order (e.g., day 3 starts with "three French Hens").
    (reverse (subseq *gifts* 0 (1+ day-index)))))

(defun format-gifts (gifts)
  "Formats a list of gift strings into a single, grammatically correct string.
   Handles the special case for one gift and adds 'and' for multiple gifts."
  (if (= 1 (length gifts))
      ;; If there's only one gift, just return it.
      (first gifts)
      ;; Otherwise, join all but the last gift with spaces, then add 'and',
      ;; then add the last gift.
      (format nil "~{~a ~}and ~a" (butlast gifts) (first (last gifts)))))

(defun verse (day-number)
  "Generates the full verse string for a given day number (1-12)."
  (let ((ordinal (nth (1- day-number) *ordinals*))
        (gifts-list (get-gifts-for-day day-number)))
    ;; Use FORMAT's powerful directives to construct the verse string.
    ;; ~a is an aesthetic directive, consuming an argument and printing it.
    (format nil "On the ~a day of Christmas my true love gave to me: ~a"
            ordinal
            (format-gifts gifts-list))))

;;; Main Function

(defun recite ()
  "Generates the complete lyrics for 'The Twelve Days of Christmas'."
  ;; Use the LOOP macro for a clear and readable iteration from 1 to 12.
  (loop for day from 1 to 12
        ;; For each day, generate the verse.
        collect (verse day)
        ;; After the loop, join the collected verses with two newlines.
        ;; The ~{~a~^...~} directive is perfect for this.
        ;; ~% is a newline character.
        into verses
        finally (return (format nil "~{~a~^~%~%~}" verses))))

Running the Code

You can run this code in any Common Lisp implementation with a REPL, such as SBCL (Steel Bank Common Lisp).

  1. Save the code above as a file, for example, twelve-days.lisp.
  2. Start your Lisp REPL.
  3. Load the file into your Lisp image.

# In your terminal, start SBCL
$ sbcl

# In the SBCL REPL
* (load "twelve-days.lisp")
T
* (twelve-days:recite)
"On the first day of Christmas my true love gave to me: a Partridge in a Pear Tree.

On the second day of Christmas my true love gave to me: two Turtle Doves, and a Partridge in a Pear Tree.
... (and so on) ..."

Detailed Code Walkthrough

Let's dissect the solution to understand the role of each component and the Lisp concepts at play.

The Data: *ordinals* and *gifts*

We use defparameter to define our two lists. The asterisks (earmuffs) around the names, like *ordinals*, are a strong convention in Lisp for naming global or special variables. This makes it immediately clear that they have a wider scope.

An important detail is the punctuation. We pre-emptively add commas and the final period to the gift strings. This simplifies the formatting logic later, as we only need to worry about adding spaces and the word "and". This is a common strategy: bake static parts of the format into the data itself to reduce code complexity.

Helper Function: get-gifts-for-day

This function is the heart of the cumulative logic. Given a day-number (e.g., 3), it does two things:

  1. (subseq *gifts* 0 (1+ day-index)): subseq extracts a portion of a sequence. Since our lists are 0-indexed, we use (1- day-number) to get the index. We want all gifts from index 0 up to and including the current day's index, so the end of the subsequence is (1+ day-index). For day 3 (index 2), this extracts the first three elements.
  2. (reverse ...): The song lists gifts in descending order of day. Day 3's verse starts with "three French Hens," not "a Partridge." Reversing the sub-list achieves this correct lyrical order.

Helper Function: format-gifts

This function tackles the tricky grammar of listing items. It takes a list like ("two Turtle Doves," "a Partridge in a Pear Tree.") and turns it into a string like "two Turtle Doves, and a Partridge in a Pear Tree.".

  • Base Case: (if (= 1 (length gifts))) checks if there is only one gift. If so, it simply returns that gift string. This handles "a Partridge in a Pear Tree." on the first day.
  • General Case: For multiple gifts, we use format.
    • (butlast gifts): Returns a new list containing all elements except the last one.
    • (first (last gifts)): A robust way to get the very last element of a list.
    • "~{~a ~}and ~a": This is a powerful format directive.
      • ~{ ... ~} is the iteration directive. It loops over a list argument.
      • Inside, ~a ~ tells it to print each element (~a) followed by a space.
      • This is applied to (butlast gifts), so for day 3 it produces "three French Hens, two Turtle Doves, ".
      • After the iteration, the string "and " is added literally, followed by the final ~a which prints the last gift.

The Verse Builder: verse

This function assembles a single, complete verse. It's a straightforward composition of our helper functions.

  • (nth (1- day-number) *ordinals*): nth retrieves an element from a list by its index. We get the correct ordinal string (e.g., "third").
  • (get-gifts-for-day day-number): Calls our helper to get the reversed list of gifts.
  • (format-gifts gifts-list): Calls our other helper to create the formatted gift string.
  • Finally, another format call pieces everything together into the "On the... day of Christmas..." template. The nil as the first argument to format tells it to return the formatted text as a new string instead of printing it to the console.

The Main Function: recite

This is the public-facing function that generates the whole song. It uses the powerful loop macro, one of Common Lisp's most flexible and readable iteration constructs.

  • (loop for day from 1 to 12 ...): Sets up a simple numeric loop.
  • collect (verse day) into verses: For each day, it calls our verse function and collects the resulting string into a list that will be named verses.
  • finally (return (format nil "~{~a~^~%~%~}" verses)): The finally clause executes after the loop finishes. It takes the collected list of verse strings and joins them.
    • ~{ ... ~} iterates over the verses list.
    • ~a prints each verse.
    • ~^ is the "separator" directive. It tells format to insert the following text (~%~%, two newlines) *between* elements, but not after the last one. This is perfect for joining lines and avoids a trailing newline at the end of the song.

Alternative Approaches and Considerations

While the provided solution is idiomatic and clear, Common Lisp often provides multiple ways to solve a problem. Let's explore some alternatives.

A Purely Recursive Approach

One could write a recursive function that builds the song verse by verse. This can be elegant but may be less intuitive for developers from an imperative background.


(defun recite-recursive (day)
  (if (> day 12)
      ""
      (let ((current-verse (verse day))
            (rest-of-song (recite-recursive (1+ day))))
        (if (string= rest-of-song "")
            current-verse
            (format nil "~a~%~%~a" current-verse rest-of-song)))))

;; Initial call would be (recite-recursive 1)

This approach builds the song from the last day backwards (due to the recursive stack). It's a classic functional pattern but can be less efficient and risks stack overflow on very large inputs (not an issue for 12 verses).

Using mapcar instead of loop

For Lispers who prefer a more functional style, mapcar can replace the loop macro.


(defun recite-mapcar ()
  (let ((days (loop for i from 1 to 12 collect i)))
    (let ((verses (mapcar #'verse days)))
      (format nil "~{~a~^~%~%~}" verses))))

This achieves the same result. The choice between loop and mapcar is often a matter of style. loop can be more readable for complex iterations, while mapcar is arguably more "functionally pure."

Pros and Cons of Different Methods

Approach Pros Cons
Iterative (loop) Highly readable and explicit. Efficient, no risk of stack overflow. Very idiomatic in modern Common Lisp. Can be seen as more "imperative" and less purely functional.
Functional (mapcar) Clear separation of data generation and transformation. Elegant and concise for simple mappings. Requires creating an intermediate list of numbers (days), which can be slightly less memory-efficient.
Recursive Mathematically elegant. A good demonstration of core functional principles. Can be harder to reason about. Prone to stack overflow for large N. Potentially less performant due to function call overhead.

For this specific problem from the kodikra Common Lisp Learning Path, the loop-based solution strikes the best balance of readability, efficiency, and idiomatic style.

Frequently Asked Questions (FAQ)

Why use format instead of simple string concatenation?

Common Lisp's format is vastly more powerful than functions like concatenate. It's a domain-specific language for text formatting. For tasks like joining list elements with a specific separator (~{~a~^, ~}) or padding strings, format is far more concise and readable than building the string manually with loops and concatenation calls.

What is the difference between defparameter and defvar?

Both define global variables. The key difference is that defparameter *always* assigns the value, even if the variable already exists. defvar only assigns the value if the variable is not already defined. For defining constants or configuration that should be reloadable, defparameter is generally preferred. For variables that should be initialized only once, defvar is appropriate.

In format-gifts, why use (first (last gifts)) instead of (nth... )?

While (nth (1- (length gifts)) gifts) would also work, it's less efficient for lists. nth may have to traverse the list from the beginning (O(n) complexity). last returns a cons cell pointing to the last element, and first (or car) retrieves it, which is generally more direct and idiomatic for getting the final element of a list.

Could this entire problem be solved in a single, massive loop?

Yes, absolutely. The loop macro is powerful enough to handle nested iterations and complex string accumulation within its clauses. However, doing so would likely result in a single, monolithic function that is much harder to read, test, and debug. Breaking the problem down into smaller helper functions (get-gifts-for-day, format-gifts, verse) is a superior software engineering practice.

Why are lists zero-indexed but we talk about days 1-12?

This is a common impedance mismatch between human-centric problem descriptions (days 1 to 12) and computer science data structures (zero-indexed arrays/lists). The code handles this by consistently subtracting 1 from the day number to get the correct list index (e.g., (1- day-number)). This is a crucial detail to manage correctly to avoid off-by-one errors.

Is recursion a bad practice in Common Lisp?

Not at all! Recursion is a fundamental concept in Lisp. However, for simple linear iterations, high-level constructs like loop, mapcar, or dotimes are often more idiomatic and efficient. Most Common Lisp compilers perform tail-call optimization, which can turn certain recursive patterns into efficient loops, but it's not guaranteed in all cases. For clarity and performance in this scenario, an iterative approach is often preferred.

How does this problem relate to real-world programming?

This exercise is a microcosm of many real-world tasks: report generation, data serialization (like converting data to JSON or XML), and building complex UI components. The core skills—structuring data, transforming it through a pipeline of functions, and formatting it into a final string representation—are directly applicable to countless programming challenges.

Conclusion: The Lisp Philosophy in Action

Successfully solving the "Twelve Days of Christmas" challenge is more than just a string manipulation exercise; it's a practical demonstration of the Lisp philosophy. We began not by writing loops, but by structuring our data into lists. We then built a series of small, composable functions, each with a single responsibility. Finally, we used high-level, declarative tools like loop and format to assemble the final output.

This approach—data-driven design, functional composition, and leveraging powerful built-in abstractions—is what gives Common Lisp its enduring power. The skills you've applied here in list processing and string formatting are foundational and will serve you well across a wide array of more complex problems. This kodikra module shows that even a simple holiday carol can be a gateway to mastering elegant and powerful programming paradigms.

Disclaimer: The code in this article is written for modern Common Lisp implementations (like SBCL 2.4+). The core language is standardized and stable, but best practices and library availability evolve. The concepts presented are timeless.

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

Post a Comment