Home
3
Coding Tutorial

Scrabble Score in Common-lisp: Complete Solution & Deep Dive Guide

a close up of a computer screen with code on it

The Complete Guide to Calculating Scrabble Score in Common Lisp

Calculating a Scrabble score in Common Lisp involves mapping each letter of a word to its point value and summing the results. This is elegantly achieved using a data structure like an association list for letter values and functional programming constructs like map and reduce for iteration and aggregation.

Have you ever been captivated by a classic word game and wondered about the logic that powers it? Translating the simple, static rules of a game like Scrabble into functional, efficient code is a fantastic exercise for any developer. It seems straightforward, but it forces you to make key decisions about data structures and algorithmic approaches that have real-world implications.

This challenge, drawn from the exclusive kodikra.com learning path, is more than just a game. It’s a practical lesson in text processing, data mapping, and the functional programming paradigm that makes Common Lisp so powerful. In this deep dive, we'll transform the rules of Scrabble into elegant Lisp code, exploring every decision from data storage to final calculation, and equip you with skills applicable to far more complex problems.

What is the Scrabble Score Challenge?

The core task is to write a function that computes the total score for a given word based on the official Scrabble letter values. Each letter in the alphabet has an assigned point value, and the score of a word is simply the sum of the values of its constituent letters. The calculation is case-insensitive, meaning 'a' and 'A' are worth the same.

This problem is a classic example of a "mapping and reducing" task. You map each character to a numerical value and then reduce the resulting collection of numbers into a single sum. It's a fundamental pattern in data processing and a perfect showcase for the functional capabilities of Common Lisp.

The Official Letter Values

For this challenge, we'll use the standard English Scrabble letter values. A clear way to represent this is with a table:

Letter(s) Value
A, E, I, O, U, L, N, R, S, T 1
D, G 2
B, C, M, P 3
F, H, V, W, Y 4
K 5
J, X 8
Q, Z 10

Our program must take a string as input (e.g., "cabbage") and return an integer representing its total score (e.g., 3 + 1 + 2 + 2 + 1 + 3 + 1 = 13).

Why Use Common Lisp for This Task?

Common Lisp, a dialect of the Lisp family of languages, is exceptionally well-suited for problems involving symbolic computation and data manipulation. Its strengths shine brightly in the Scrabble Score challenge for several key reasons:

  • Functional Programming Paradigm: Lisp is a multi-paradigm language, but its functional roots are deep. Functions are first-class citizens, which allows for elegant, chainable operations using higher-order functions like map and reduce. This often leads to more concise and readable code than imperative loops.
  • Powerful Data Structures: Lisp provides built-in, flexible data structures perfect for this task. The provided solution uses an association list (or alist), a simple list of key-value pairs, which is idiomatic Lisp for small, static lookups. We'll also explore the more performant hash table.
  • Interactive Development (REPL): Common Lisp's Read-Eval-Print Loop (REPL) allows you to build and test your code incrementally. You can define your data structures, test your letter-scoring function, and build up to the final word-scoring function, all within a live, interactive environment.
  • Expressiveness: Lisp syntax, known as S-expressions (or symbolic expressions), is highly regular. While it may look unusual at first, its "code-is-data" philosophy allows for powerful metaprogramming and a clear, unambiguous structure.

By solving this problem in Common Lisp, you're not just getting a score; you're learning a powerful way of thinking about data transformation that is applicable across countless domains. For more foundational concepts, check out our complete Common Lisp guide.

How to Structure the Solution: A Step-by-Step Code Walkthrough

Let's deconstruct the provided solution from the kodikra.com module. We'll analyze each part, from setting up the environment to the core scoring logic, to understand the "why" behind the code.

Step 1: Package and Environment Setup

Good Common Lisp code is organized into packages to avoid symbol conflicts. This is similar to namespaces in C++ or packages in Java.

(defpackage :scrabble-score
  (:use :cl)
  (:export :score-word))

(in-package :scrabble-score)
  • (defpackage :scrabble-score ...): This defines a new package named scrabble-score.
  • (:use :cl): This clause specifies that our new package should inherit all the standard symbols from the default COMMON-LISP package (aliased as :cl). This gives us access to functions like defun, defparameter, map, etc., without needing to prefix them (e.g., cl:defun).
  • (:export :score-word): This is crucial for modularity. It declares that the symbol score-word is part of the public API of this package. Any other package that wishes to use our scoring function can import this symbol.
  • (in-package :scrabble-score): This command switches the current working environment into our newly created package. All subsequent definitions will belong to scrabble-score.

Step 2: Storing the Letter Values

The first major decision is how to store the mapping from letters to scores. The solution uses an association list (alist), a traditional Lisp data structure.

(defparameter *letter-scores*
  '((#\A . 1) (#\B . 3) (#\C . 3) (#\D . 2) (#\E . 1) (#\F . 4)
    (#\G . 2) (#\H . 4) (#\I . 1) (#\J . 8) (#\K . 5) (#\L . 1)
    (#\M . 3) (#\N . 1) (#\O . 1) (#\P . 3) (#\Q . 10) (#\R . 1)
    (#\S . 1) (#\T . 1) (#\U . 1) (#\V . 4) (#\W . 4) (#\X . 8)
    (#\Y . 4) (#\Z . 10)))
  • defparameter: This defines a global, dynamically scoped variable. The asterisks (*...*) surrounding the name are a strong Lisp convention for naming such special variables.
  • '((#\A . 1) ...): This is the alist itself. It's a list of cons cells. Each cons cell is a pair, written as (key . value).
    • #\A: The #\ syntax denotes a character literal.
    • (#\A . 1): This is a pair where the key is the character #\A and the value is the integer 1.

An association list is simple and easy to read, making it a great choice for small, fixed datasets like the 26 letters of the alphabet.

Step 3: Creating a Function to Score a Single Letter

With our data structure in place, we need a helper function to look up the score for a single letter. This function encapsulates the logic of interacting with our *letter-scores* alist.

(defun score-letter (letter)
  "Returns the score for a single letter, or 0 if not a valid letter."
  (let ((pair (assoc letter *letter-scores*)))
    (if pair
        (cdr pair)
        0)))
  • (defun score-letter (letter)): Defines a function named score-letter that takes one argument, letter.
  • "...": This is a documentation string, or "docstring," which is a Lisp best practice. It describes what the function does.
  • (let ((pair (assoc letter *letter-scores*)))): This is the core lookup logic.
    • assoc: This is the standard Lisp function for searching an association list. It takes a key (letter) and the alist (*letter-scores*) and returns the first matching pair it finds. For example, (assoc #\A *letter-scores*) would return the pair (#\A . 1). If no match is found, it returns nil (Lisp's representation of false/null).
    • let: This creates a local variable binding. The result of the assoc call is stored in the local variable pair.
  • (if pair (cdr pair) 0): This conditional logic handles the result.
    • if pair: In Lisp, any non-nil value is treated as true. So, if assoc found a pair, this condition is met.
    • (cdr pair): If a pair was found (e.g., (#\A . 1)), cdr returns the second part of the pair—the value. In this case, 1.
    • 0: If pair is nil (the letter wasn't found), the function returns 0. This gracefully handles non-alphabetic characters like spaces or punctuation.

This function is a clean, reusable piece of logic. Now we can build upon it.

Step 4: The Main Function to Score an Entire Word

Finally, we combine everything into the main function, score-word. This function demonstrates the power of Lisp's functional programming tools.

(defun score-word (word)
  "Computes the Scrabble score for a word."
  (reduce #'+
          (map 'list #'score-letter (string-upcase word))))

This compact function packs a lot of power. Let's break it down from the inside out, which is how Lisp evaluates expressions.

    ● Input: "Lisp"
    │
    ▼
  ┌──────────────────────────┐
  │ 1. (string-upcase word)  │
  └────────────┬─────────────┘
               │
               ▼
           "LISP"
               │
    ┌──────────────────────────┐
    │ 2. (map ... #'score-letter ...) │
    └────────────┬─────────────┘
                 │
                 ▼
          (1 1 1 3)
                 │
    ┌──────────────────────────┐
    │ 3. (reduce #'+ ...)      │
    └────────────┬─────────────┘
                 │
                 ▼
             6
                 │
                 ▼
             ● Output
  1. (string-upcase word): The process starts here. This function takes the input word (e.g., "cabbage") and converts it to its uppercase equivalent ("CABBAGE"). This is crucial for ensuring our lookups in *letter-scores* are case-insensitive, as we only stored uppercase letters.
  2. (map 'list #'score-letter ...): This is the mapping step.
    • map is a higher-order function that applies another function to each element of a sequence.
    • 'list: The first argument specifies the type of sequence to return. Here, we want a list.
    • #'score-letter: The #' (sharp-quote) syntax is shorthand for (function score-letter). It passes our helper function as an argument to map.
    • The result of this expression is a new list containing the score for each letter. For "CABBAGE", it would produce the list (3 1 2 2 1 3 1).
  3. (reduce #'+ ...): This is the final reduction step.
    • reduce is another higher-order function that combines the elements of a sequence into a single value.
    • #'+: We pass the addition function (+) as the operator.
    • reduce takes the list of scores (3 1 2 2 1 3 1) and applies + cumulatively: ((((((3 + 1) + 2) + 2) + 1) + 3) + 1), resulting in the final score of 13.

This functional composition is a hallmark of idiomatic Lisp. It's declarative—we describe what we want to happen (uppercase, map scores, sum them) rather than how to do it with explicit loops and temporary variables.

When to Optimize: Association List vs. Hash Table

The provided solution using an association list is perfectly fine for this problem. The dataset is tiny (26 entries), and the linear search performed by assoc is instantaneous in practice. However, understanding the trade-offs is a critical skill for a developer.

For larger datasets, an association list becomes inefficient. The time complexity of an assoc lookup is O(n), meaning the time it takes to find an item grows linearly with the size of the list. A hash table, on the other hand, offers an average lookup time of O(1), or constant time, which is significantly faster for large n.

Pros & Cons for the Scrabble Problem

Data Structure Pros Cons
Association List
  • Very simple to write and read.
  • No overhead for creation.
  • Idiomatic for small, static Lisp configuration data.
  • O(n) lookup time (inefficient for large datasets).
  • Not suitable for data that changes frequently.
Hash Table
  • O(1) average lookup time (extremely fast).
  • The standard choice for key-value mapping in most languages.
  • Scales efficiently to millions of entries.
  • Slightly more verbose to create.
  • Minor memory and creation overhead.
  • Can feel like overkill for 26 fixed items.

An Optimized Solution Using a Hash Table

Let's see what an implementation using a hash table would look like. First, we need a function to create the hash table from our existing alist.

(defun make-letter-scores-hash ()
  "Creates a hash table from the letter-scores alist."
  (let ((table (make-hash-table)))
    (dolist (pair *letter-scores*)
      (setf (gethash (car pair) table) (cdr pair)))
    table))

(defparameter *letter-scores-hash* (make-letter-scores-hash))

Now, we create a new letter-scoring function that uses the hash table.

(defun score-letter-hash (letter)
  "Returns the score for a single letter using a hash table."
  (gethash letter *letter-scores-hash* 0))

This is much simpler! gethash takes the key, the hash table, and an optional default value to return if the key is not found. This single line replaces the let, assoc, and if logic from the alist version.

Finally, our main function can be updated to use this new helper:

(defun score-word-optimized (word)
  "Computes the Scrabble score using a hash table for faster lookups."
  (reduce #'+
          (map 'list #'score-letter-hash (string-upcase word))))

The overall structure remains the same, showcasing the power of abstraction. We swapped out the underlying implementation of the letter lookup without changing the high-level logic of the word-scoring function.

Here is an ASCII diagram illustrating the O(1) nature of a hash table lookup versus the O(n) of an alist.

   Association List Lookup (O(n))      Hash Table Lookup (O(1))
   ┌─────────────────────────┐       ┌──────────────────────────┐
   │ (assoc #\P alist)       │       │ (gethash #\P table)      │
   └──────────┬──────────────┘       └───────────┬──────────────┘
              │                                  │
              ▼                                  ▼
      Is car #\A? ── No ─┐             Hash(#\P) ───⟶ Index 15
              │           │                          │
             Yes          │                          ▼
              │           │                ┌──────────────────┐
              ▼           │                │ Bucket 15: (#\P.3)│
           Return       Next ── No ─┐      └─────────┬────────┘
                                │           │          │
                               Yes          │          ▼
                                │           │        Return 3
                                ▼           │
                             Return       Next ...

Running the Code in a REPL

One of the best ways to experience Common Lisp is through its REPL. Here’s how you could load and test this code. Assuming you have a Lisp implementation like SBCL (Steel Bank Common Lisp) installed and the code is saved in a file named scrabble.lisp:

1. Start the SBCL REPL from your terminal:

$ sbcl

2. You'll be greeted with a prompt, usually an asterisk (*). Load the file:

* (load "scrabble.lisp")

3. Now you can call the exported function. Note that you need to qualify it with the package name.

* (scrabble-score:score-word "kodikra")
; ==> 12
* (scrabble-score:score-word "LISP")
; ==> 6
* (scrabble-score:score-word "quiz")
; ==> 22
* (scrabble-score:score-word "")
; ==> 0

This interactive workflow allows for rapid testing and debugging, a key advantage of the Lisp development experience.

Frequently Asked Questions (FAQ)

Is Common Lisp case-sensitive in this solution?
By default, the Common Lisp reader downcases symbols, but character and string functions are case-sensitive. The character #\a is different from #\A. That's precisely why the (string-upcase word) step is critical to ensure that both "lisp" and "LISP" produce the same score by matching against the uppercase keys in our data store.
What exactly is an association list (alist)?
An alist is a list where each element is a cons cell representing a key-value pair, like (key . value). It's a fundamental Lisp data structure used for simple lookups. Functions like assoc perform a linear scan from the beginning of the list to find the first matching key.
Why use reduce instead of a traditional loop?
Using reduce promotes a functional programming style. It's more declarative, focusing on the "what" (summing a list) rather than the "how" (initializing a counter, iterating, updating the counter). This often leads to more concise, less error-prone, and more composable code. While a loop or dolist macro would also work, reduce is arguably more idiomatic for this kind of aggregation task.
How does the solution handle non-alphabetic characters or an empty string?
It handles them gracefully. The score-letter function returns 0 for any character not found in the *letter-scores* alist. So, a string like "hello world!" would be scored correctly, with the space and exclamation mark contributing 0 to the total. If an empty string "" is passed to score-word, map produces an empty list (), and (reduce #'+ '()) correctly returns 0.
What is the purpose of the #' syntax?
The #' (pronounced "sharp-quote") is a reader macro that is shorthand for the function special operator. #'foo is equivalent to (function foo). It tells the Lisp compiler that you are referring to the function binding of the symbol foo, not its value binding. This is necessary when passing functions as arguments to other functions, like map and reduce.
Could I have defined the letter scores directly inside the function?
Yes, you could have used let to define the alist inside score-word. However, defining it at the top level with defparameter is better practice. The letter scores are constant data; creating them every time the function is called is inefficient. A top-level definition creates the data structure once when the file is loaded.
What is the future of Common Lisp?
Common Lisp is one of the most stable and standardized languages in existence (ANSI Common Lisp). While not as mainstream as Python or JavaScript for web development, it remains a powerful force in specialized domains like artificial intelligence research, scheduling systems, and symbolic mathematics. Its powerful macro system and interactive development model are features that modern languages are still trying to replicate. The community is active, and modern implementations like SBCL are highly optimized and robust.

Conclusion: From Game Rules to Elegant Code

We've successfully translated a simple set of game rules into a robust and elegant Common Lisp program. This journey through the Scrabble Score problem has illuminated several core principles of effective software development in Lisp: the importance of choosing the right data structure, the power of functional composition with map and reduce, and the benefits of building modular code with helper functions and packages.

While the performance difference between an association list and a hash table was negligible for this specific problem, understanding the underlying algorithmic complexity is a vital skill that separates novice programmers from seasoned engineers. The patterns you've learned here—mapping data and reducing it to a result—are universal in programming and will serve you well in countless future projects.

This challenge is a stepping stone. The concepts of text manipulation, data mapping, and functional iteration are foundational to building more complex applications, from data analysis tools to the logic engines of sophisticated games.

Disclaimer: The code in this article is based on modern, stable features of ANSI Common Lisp. It is expected to be compatible with any conforming implementation, such as SBCL, CCL, or LispWorks, for the foreseeable future.

Ready to tackle the next challenge and deepen your Lisp expertise? Continue your journey on the kodikra.com Common Lisp learning path or dive deeper into the language with our comprehensive Common Lisp language guide.

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

Post a Comment