Anagram in Common-lisp: Complete Solution & Deep Dive Guide

a close up of a computer screen with code on it

From Zero to Hero: Master Anagram Detection in Common Lisp

To find anagrams in Common Lisp, the most effective strategy is to create a canonical representation for each word. This is achieved by sorting the characters of the word alphabetically. If two words, after being lowercased and sorted, are identical (and are not the original word), they are anagrams.

You’ve stumbled upon a classic word puzzle, a challenge that has intrigued minds for centuries. You have a target word, say "listen," and a list of candidates. Your mission is to programmatically sift through the list and pull out every word that is a perfect scramble of "listen," like "silent" or "enlist." It sounds simple, but how do you teach a computer to see this relationship? The logic feels elusive, a pattern just out of reach.

This is a common hurdle for developers diving into algorithmic thinking. You know the goal, but the path to a clean, efficient, and elegant solution isn't always clear. This guide is your map. We will break down the anagram problem from its core principles, translating abstract logic into powerful, idiomatic Common Lisp code. You will not only solve the problem but also understand the deep-seated computer science concepts that make the solution work, turning a frustrating puzzle into a showcase of your new skills.

What Exactly Is an Anagram?

An anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once. The essence of an anagram lies in character frequency: two words are anagrams if and only if they are composed of the exact same letters with the exact same counts.

For example, the word "snow" can be rearranged to form "owns". Both words use one 's', one 'n', one 'o', and one 'w'. This makes them perfect anagrams. In our context, based on the problem from the exclusive kodikra.com curriculum, we have two critical constraints:

Case-Insensitivity: The comparison must ignore case. This means "Listen" and "silent" should be considered anagrams. Our logic must treat 'L' and 'l' as the same character.
Identity Exclusion: A word is never its own anagram. So, given the target word "stop", the candidate "stop" should be rejected, even though it meets the character frequency criteria.

Understanding these rules is the first step toward building a robust solution. We're not just matching characters; we're implementing a specific set of logical rules in code.

Why Anagram Detection is a Foundational Coding Challenge

The anagram problem appears deceptively simple, which is precisely why it's a staple in technical interviews and coding challenges. It's a fantastic tool for evaluating a developer's fundamental skills. Solving it effectively demonstrates a solid grasp of several key areas:

String Manipulation: At its heart, this is a problem about taking strings apart, analyzing their components, and comparing them in a non-obvious way.
Algorithmic Thinking: There isn't a built-in is_anagram() function. You must devise an algorithm. The most common approach involves creating a "canonical representation"—a standardized form—for each string to make comparison trivial.
Data Structures: While our first solution won't explicitly use complex data structures, understanding the problem opens the door to more optimized solutions using hash maps (or hash tables in Lisp) to count character frequencies.
Attention to Detail: Handling edge cases like case-insensitivity and the self-exclusion rule separates a partial solution from a complete one.

By mastering this challenge from the kodikra learning path, you're not just learning to find jumbled words; you're honing the core competencies that apply to a vast range of programming problems.

How to Identify Anagrams: The Canonical Representation Strategy

The most elegant and intuitive way to solve the anagram problem is to establish a "canonical form" or a "signature" for each word. If two words share the same signature, they must be anagrams.

What is the perfect signature for an anagram? A sorted version of the word. If you take any two anagrams, lowercase them, and then sort their characters alphabetically, the results will be identical.

Let's walk through an example:

Target Word: "Stale"
Candidate Word: "Least"

Now, let's apply the canonicalization process:

Lowercase both words:
- "Stale" becomes "stale"
- "Least" becomes "least"
Sort the characters of each lowercased word:
- "stale" -> s, t, a, l, e -> sorted -> "aelst"
- "least" -> l, e, a, s, t -> sorted -> "aelst"
Compare the results:
- The signature for "Stale" is "aelst".
- The signature for "Least" is "aelst".
- Since "aelst" is equal to "aelst", the words are anagrams.

This method is powerful because it transforms a complex comparison problem into a simple equality check. The entire logic hinges on this transformation.

Anagram Detection Flow (Sorting Method)

    ● Start with Subject & Candidate Word
    │
    ▼
  ┌──────────────────┐
  │ Lowercase Both   │
  │ e.g., "Listen" → "listen"
  │       "silent" → "silent"
  └─────────┬────────┘
            │
            ▼
  ┌──────────────────┐
  │ Sort Characters  │
  │ "listen" → "eilnst"
  │ "silent" → "eilnst"
  └─────────┬────────┘
            │
            ▼
  ◆ Are sorted strings equal?
  │   ("eilnst" == "eilnst")
  │
 ├───────────────┐
 Yes             No
 │               │
 ▼               ▼
 ◆ Are original strings different?
 │   ("Listen" != "silent")
 │               │
 ├──────┐        │
 Yes    No       │
 │      │        │
 ▼      ▼        ▼
[ANAGRAM] [NOT]  [NOT ANAGRAM]
 │      │        │
 └──────┴────────┘
        │
        ▼
     ● End

Where the Magic Happens: A Deep Dive into the Common Lisp Solution

Now, let's translate our strategy into idiomatic Common Lisp code. We'll analyze the solution provided in the kodikra.com module, breaking it down piece by piece to understand not just what it does, but why it's written that way.

The Full Code Snippet

(defpackage :anagram
  (:use :common-lisp)
  (:export :anagrams-for))

(in-package :anagram)

(defun anagram-equal (a b)
  (and (string-equal (sort (copy-seq a) #'char-lessp)
                     (sort (copy-seq b) #'char-lessp))
       (string-not-equal a b)))

(defun anagrams-for (subject candidates)
  (remove-if-not #'(lambda (w) (anagram-equal w subject))
                 candidates))

Code Walkthrough

Part 1: Setting up the Package

(defpackage :anagram
  (:use :common-lisp)
  (:export :anagrams-for))

(in-package :anagram)

(defpackage :anagram ...): This defines a new package named anagram. In Common Lisp, packages are namespaces that prevent symbol collisions. It's like creating a module or a library in other languages.
(:use :common-lisp): This tells our new package to inherit all the standard symbols (functions, macros, variables) from the core common-lisp package. This gives us access to functions like sort, and, defun, etc.
(:export :anagrams-for): This is crucial. It declares which symbols from our package should be "public." Only exported symbols can be easily accessed by other packages. Here, we are making our main function, anagrams-for, available for external use.
(in-package :anagram): This command switches the current working namespace to our newly defined anagram package. All subsequent definitions will belong to this package.

Part 2: The Core Comparison Logic: `anagram-equal`

(defun anagram-equal (a b)
  (and (string-equal (sort (copy-seq a) #'char-lessp)
                     (sort (copy-seq b) #'char-lessp))
       (string-not-equal a b)))

This helper function is the heart of our solution. It takes two strings, a and b, and returns T (true) if they are anagrams of each other, and NIL (false) otherwise.

(defun anagram-equal (a b) ...): Defines a function named anagram-equal that accepts two arguments, a and b.
(and ...): The and macro evaluates its arguments from left to right. It returns NIL as soon as any argument evaluates to NIL. If all arguments are true, it returns the value of the last argument. This is perfect for checking multiple conditions.
First Condition: The Canonical Comparison
- (copy-seq a): This is a critical step. The sort function in Common Lisp is destructive; it modifies the sequence it operates on. To avoid altering our original input strings, we first create a mutable copy of the string a using copy-seq.
- (sort ... #'char-lessp): This sorts the copied sequence. The #'char-lessp is the predicate function used for comparison. It tells sort to order characters based on their character codes in a case-sensitive manner.
- (string-equal ...): This function compares the two sorted strings. Crucially, string-equal performs a case-insensitive comparison. This elegantly handles the requirement that "Listen" and "silent" should match. Even though char-lessp is case-sensitive, the final comparison with string-equal smooths this out, making the entire process effectively case-insensitive.
Second Condition: The Identity Check
- (string-not-equal a b): This implements our second rule: a word cannot be its own anagram. It performs a case-insensitive check to see if the original strings a and b are different.

The function only returns T if both the canonical forms match AND the original words are different.

Part 3: The Main Function: `anagrams-for`

(defun anagrams-for (subject candidates)
  (remove-if-not #'(lambda (w) (anagram-equal w subject))
                 candidates))

This is our public-facing function. It orchestrates the whole process, filtering a list of candidates against a subject word.

(defun anagrams-for (subject candidates) ...): Defines the main function that takes a subject string and a list of candidates strings.
(remove-if-not ...): This is a powerful higher-order function from the Lisp family. It iterates through a list (candidates in this case) and keeps only the elements for which a given predicate function returns true.
#'(lambda (w) (anagram-equal w subject)): This is the predicate. Let's break it down:
- lambda: Defines an anonymous function—a function without a name. This is common in functional programming for creating small, single-use functions.
- (w): This lambda function takes one argument, which we'll call w. As remove-if-not iterates through the candidates list, w will be each candidate word in turn.
- (anagram-equal w subject): The body of the lambda. For each candidate w, it calls our helper function anagram-equal to compare it against the original subject.
- #': This is shorthand for (function ...). It tells Lisp that we are referring to the function object itself, not trying to call it.

In plain English, this function says: "For every word in the candidates list, check if it's an anagram of the subject. Give me back a new list containing only the words for which that check was true."

When to Optimize: A More Performant Approach with Frequency Counting

The sorting-based solution is elegant and easy to understand. However, its performance depends on the efficiency of the sorting algorithm. Sorting a string of length N typically takes O(N log N) time. If we have M candidate words, the total complexity is roughly O(M * N log N).

For most cases, this is perfectly fine. But what if we were dealing with millions of candidates or very long words? We can do better. An alternative strategy is frequency counting.

The logic is simple: two words are anagrams if they have the exact same count of each character. We can implement this by creating a frequency map (a hash table in Common Lisp) for the subject word and then comparing it to the frequency map of each candidate.

Frequency Counting Flow (Hash Table Method)

    ● Start with Subject & Candidate Word
    │
    ▼
  ┌───────────────────────┐
  │ Lowercase Both Words  │
  └──────────┬────────────┘
             │
             ▼
  ┌───────────────────────┐
  │ Build Frequency Map   │
  │ for Subject Word      │
  │ "listen" → {l:1, i:1, s:1, t:1, e:1, n:1}
  └──────────┬────────────┘
             │
             ▼
  ┌───────────────────────┐
  │ Build Frequency Map   │
  │ for Candidate Word    │
  │ "silent" → {s:1, i:1, l:1, e:1, n:1, t:1}
  └──────────┬────────────┘
             │
             ▼
  ◆ Are the two maps identical?
  │   (Check keys & values)
  │
 ├──────────────────┐
 Yes                No
 │                  │
 ▼                  ▼
 ◆ Are original strings different?
 │                  │
 ├──────┐           │
 Yes    No          │
 │      │           │
 ▼      ▼           ▼
[ANAGRAM] [NOT]   [NOT ANAGRAM]
 │      │           │
 └──────┴───────────┘
         │
         ▼
      ● End

Creating a frequency map for a word of length N takes O(N) time. Comparing two maps also takes, on average, O(N) time. This brings the total complexity down to O(M * N), which is a significant improvement for long strings.

Optimized Code using Hash Tables

(defun char-counts (word)
  "Creates a hash table counting character frequencies in a word."
  (let ((counts (make-hash-table :test 'equal)))
    (loop for char across (string-downcase word)
          do (incf (gethash char counts 0)))
    counts))

(defun hash-tables-equal (ht1 ht2)
  "Checks if two hash tables are equivalent (same keys with same values)."
  (and (= (hash-table-count ht1) (hash-table-count ht2))
       (loop for key being the hash-keys of ht1
             using (hash-value value1)
             always (= value1 (gethash key ht2)))))

(defun anagrams-for-optimized (subject candidates)
  "Finds anagrams using a frequency counting (hash table) approach."
  (let ((subject-lower (string-downcase subject))
        (subject-counts (char-counts subject)))
    (loop for candidate in candidates
          when (and (not (string-equal subject-lower candidate))
                    (= (length subject-lower) (length candidate)) ; Quick check
                    (hash-tables-equal subject-counts (char-counts candidate)))
          collect candidate)))

This version is more verbose but can be much faster. It first pre-calculates the frequency map of the subject word. Then, for each candidate, it does a quick length check (a cheap way to discard obvious non-anagrams) before building and comparing the frequency maps.

Pros & Cons: Sorting vs. Frequency Counting

Aspect	Sorting Method	Frequency Counting (Hash Table) Method
Time Complexity	O(M * N log N)	O(M * N)
Readability	Very high. The logic is concise and easy to follow.	Lower. Requires understanding hash tables and more helper functions.
Memory Usage	Low. Requires temporary copies of strings for sorting.	Higher. Requires creating a hash table for the subject and each candidate.
Best For	Short strings, smaller datasets, and situations where code clarity is paramount.	Very long strings, large datasets, and performance-critical applications.

Frequently Asked Questions (FAQ)

Why is `copy-seq` necessary before sorting in the first solution?: In Common Lisp, the sort function is "destructive," meaning it modifies the sequence you pass to it directly. If we passed the original candidate string to sort, it would be permanently altered. Using (copy-seq a) creates a fresh copy, ensuring that the original input data remains untouched, which is a fundamental principle of good functional programming style (avoiding side effects).
What does the `#'` (hash-quote or sharp-quote) syntax mean in Common Lisp?: The #' syntax is a reader macro, and it's shorthand for the function special operator. For example, #'char-lessp is equivalent to (function char-lessp). It tells the Lisp compiler that you are referring to the function object itself, rather than trying to call the function. This is necessary when passing a function as an argument to another function, like passing char-lessp to sort or a lambda to remove-if-not.
How would you modify the code to handle words with hyphens or spaces?: The current solution would treat hyphens and spaces as characters to be included in the sort. To ignore them, you would need to add a preprocessing step that filters out non-alphabetic characters before creating the canonical form. You could create a helper function that removes unwanted characters from a string before it's passed to the sorting or frequency counting logic.
Is the frequency counting method always better than sorting?: Not always. While it has a better time complexity in theory (O(N) vs O(N log N)), creating hash tables has a higher constant overhead. For very short strings, the simplicity and lower overhead of the sorting method might actually make it faster in practice. The performance benefits of frequency counting become significant as the length of the strings increases.
What is the difference between `string-equal` and `string=`?: string= performs a case-sensitive comparison, meaning "Word" and "word" are considered different. string-equal performs a case-insensitive comparison, treating "Word" and "word" as the same. For the anagram problem, where case should be ignored, string-equal is the correct choice.
How does Common Lisp's functional approach benefit this solution?: The solution heavily leverages functional programming concepts. Using higher-order functions like remove-if-not with a lambda allows for expressive and concise code. Instead of writing a manual loop with conditional checks, we can describe the filtering logic at a higher level of abstraction, leading to more readable and maintainable code.

Conclusion: From Jumbled Letters to Elegant Logic

We've journeyed from a simple word puzzle to a deep exploration of algorithmic strategy in Common Lisp. You've learned that the key to solving the anagram problem lies in creating a canonical representation—a consistent "signature"—for each word. By transforming words into their sorted-character form, we turned a complex comparison into a simple check for equality.

We dissected a concise, functional solution using sort and remove-if-not, highlighting the power of higher-order functions. We also explored a more performant alternative using hash tables for frequency counting, understanding the trade-offs between readability and raw speed. This journey through the kodikra.com module has equipped you with not just an answer, but a versatile problem-solving pattern that you can apply to countless other challenges.

Disclaimer: The code and concepts discussed are based on standard Common Lisp implementations. Behavior may vary slightly between different implementations like SBCL, CLISP, or CCL. The provided solutions are tested and conform to the ANSI Common Lisp standard.

Ready to apply these concepts to new challenges? Explore the full Common Lisp learning path on kodikra.com to continue your journey. For a broader understanding of the language, don't miss our complete Common Lisp guide.

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

kodikra

Search this blog