Home
5
Coding Tutorial

Largest Series Product in Common-lisp: Complete Solution & Deep Dive Guide

man wearing black shirt

The Complete Guide to Solving Largest Series Product in Common Lisp

The Largest Series Product problem is a classic algorithmic challenge that tests your ability to manipulate sequences and perform calculations efficiently. In Common Lisp, this task offers a fantastic opportunity to leverage the language's powerful functional programming features to arrive at an elegant and expressive solution for finding the greatest product of a contiguous sub-sequence of digits within a given string.

The Mission: Cracking the Code in a Digital Heist

Imagine you're an analyst for a top-tier cybersecurity agency. Your team has just intercepted a stream of encrypted signals from a notorious syndicate of bank robbers. The signal is a long, seemingly random sequence of digits. Your mission, should you choose to accept it, is to find meaningful patterns hidden within this digital noise. The lead cryptographer believes the key lies in a technique known as the "largest series product."

You might feel a bit of pressure. Staring at a massive string of numbers can be intimidating, and figuring out how to break it down into manageable chunks is the first hurdle. This is a common pain point for developers: taking a large, abstract problem and devising a concrete, step-by-step algorithm. This guide will serve as your digital toolkit, transforming you from an apprentice analyst into a master codebreaker, ready to tackle this challenge with confidence using the power of Common Lisp.

What Exactly is the Largest Series Product Problem?

Before diving into the Lisp code, it's crucial to fundamentally understand the problem's components. Breaking it down into simple terms demystifies the challenge and lays the groundwork for our algorithm.

Core Terminology Explained

  • Input: This is the long sequence of digits you need to analyze. It's typically provided as a string, for example, "73167176531330624919225119674426574742355349194934".
  • Series: A "series" is simply a smaller, contiguous sequence of digits found within the main input string. "Contiguous" means the digits are right next to each other. For the input "12345", "123" and "345" are valid series, but "135" is not.
  • Span: This is an integer that defines the exact length of the series you are looking for. If the span is 3, you are only interested in series that are exactly three digits long.
  • Product: This is the mathematical result you get when you multiply all the digits within a single series. For the series "491", the product is 4 * 9 * 1 = 36.

Putting it all together, the goal is to examine every possible series of a given span within the input string, calculate the product of each series, and identify the single largest product among them.

A Simple Walkthrough Example

Let's use a smaller, more manageable example to see it in action.

  • Input String: "49142"
  • Span: 3

Our task is to find the largest product of any 3-digit series in this string.

  1. The first series of span 3 is "491". Its product is 4 * 9 * 1 = 36.
  2. The second series is "914". Its product is 9 * 1 * 4 = 36.
  3. The third and final series is "142". Its product is 1 * 4 * 2 = 8.

Comparing the products (36, 36, 8), the largest product is 36. This is the answer our function should return.

Why This Problem Matters: Beyond the Heist Scenario

While the "bank robber" narrative is a fun way to frame the problem, the underlying concept—the "sliding window" algorithm—has profound applications across various fields of computer science and data analysis. Mastering it is a valuable skill for any serious programmer.

  • Digital Signal Processing (DSP): In DSP, engineers analyze streams of data (like audio or sensor readings) by looking at small, overlapping windows of samples to find patterns, peaks, or anomalies. This is a direct parallel to our problem.
  • Financial Data Analysis: Algorithmic traders use sliding windows to calculate moving averages or identify volatility patterns in stock price data over specific time frames (e.g., the last 5 trading days).
  • Bioinformatics: Scientists analyze long DNA or protein sequences by examining shorter segments (like our series) to find specific motifs or regions with certain properties.
  • Technical Interviews: The sliding window is a fundamental algorithmic pattern. Questions like this are common in coding interviews for top tech companies as they test your problem-solving, string manipulation, and efficiency-awareness skills.

By solving this problem from the kodikra learning path, you're not just completing a module; you're building a foundational skill applicable to many real-world challenges.

How to Solve It: The Sliding Window Algorithm

The most intuitive and common approach to this problem is the "sliding window" technique. Imagine a literal window of a fixed size (the span) that you slide across the input string, one character at a time. At each position, you look at the digits visible through the window and perform your calculation.

This method ensures that you systematically check every single possible contiguous series of the required length without missing any. It's a methodical and reliable way to break the larger problem into smaller, repeatable steps.

Visualizing the Sliding Window

The following diagram illustrates how a window of span 3 slides across our example input string "49142".

  Input String: "49142"
  Span: 3

    ● Start
    │
    ▼
┌────────────────┐
│ Window 1: "491"  │   ⟶ Product: 36
└────────────────┘
    │
    ↓ slide →
    │
┌────────────────┐
│ Window 2: "914"  │   ⟶ Product: 36
└────────────────┘
    │
    ↓ slide →
    │
┌────────────────┐
│ Window 3: "142"  │   ⟶ Product: 8
└────────────────┘
    │
    ▼
┌────────────────┐
│ Max Product: 36  │
└────────────────┘
    │
    ▼
    ● End

This visualization makes the process clear. Our program needs to first generate all these windows (or series) and then calculate the product for each one before finding the maximum.

Where to Implement It: A Common Lisp Code Walkthrough

Now, let's translate our algorithm into functional Common Lisp code. The solution provided in the kodikra.com module is beautifully declarative, breaking the problem into small, specialized functions. This is a hallmark of good Lisp programming style: composing solutions from simple, reusable parts.

Here is the complete solution package. We will dissect each function one by one.


(defpackage :largest-series-product
  (:use :cl)
  (:export :largest-product))

(in-package :largest-series-product)

(defun valid-input-p (digits span)
  "Checks if the input string and span are valid for the operation."
  (and (every #'digit-char-p digits)
       (not (minusp span))
       (>= (length digits) span)))

(defun windows (seq span)
  "Generates a list of all contiguous sub-sequences of a given span."
  (loop for start from 0 to (- (length seq) span)
        collect (subseq seq start (+ start span))))

(defun string-to-product (seq)
  "Converts a string of digits to their integer product."
  (apply #'* (map 'list #'digit-char-p seq)))

(defun largest-product (digits span)
  "Calculates the largest product of a series of a given span from a string of digits."
  (when (valid-input-p digits span)
    (if (zerop span)
        1
        (apply #'max (mapcar #'string-to-product (windows digits span))))))

Step 1: Input Validation with valid-input-p

The first rule of robust programming is to never trust your inputs. The valid-input-p function acts as a security guard, ensuring we only proceed with clean, sensible data.


(defun valid-input-p (digits span)
  "Checks if the input string and span are valid for the operation."
  (and (every #'digit-char-p digits)
       (not (minusp span))
       (>= (length digits) span)))
  • (every #'digit-char-p digits): This is the first check. The every function tests if a predicate (here, #'digit-char-p) is true for every element of a sequence. digit-char-p returns true if a character is a digit ('0'-'9'). This line ensures the input string contains only digits. If it finds a letter or symbol, it fails.
  • (not (minusp span)): The second check ensures the span is not a negative number. A negative span makes no logical sense, so we reject it. This is equivalent to checking (>= span 0).
  • (>= (length digits) span): The final check verifies that the window size (span) is not larger than the string itself. You can't get a 5-digit series from a 4-digit string.
  • (and ...): The and macro ties these three conditions together. It evaluates them in order and stops immediately, returning NIL, if any condition is false. All three must be true for the function to return T (true).

Step 2: Generating the Series with windows

This function is the heart of the sliding window implementation. Its job is to generate the list of all possible series based on the input string and span.


(defun windows (seq span)
  "Generates a list of all contiguous sub-sequences of a given span."
  (loop for start from 0 to (- (length seq) span)
        collect (subseq seq start (+ start span))))
  • (loop for start from 0 to (- (length seq) span) ...): The powerful loop macro is used here. It iterates by setting a variable start from 0 up to the last possible starting position for a valid window. The last starting position is calculated as (length seq) - span. For "49142" (length 5) and span 3, the last start is 5 - 3 = 2. So, start will be 0, 1, and 2.
  • collect (subseq seq start (+ start span)): In each iteration, subseq extracts a part of the sequence. It takes the sequence, a start index, and an end index (exclusive).
    • When start is 0, it extracts (subseq seq 0 3) -> "491".
    • When start is 1, it extracts (subseq seq 1 4) -> "914".
    • When start is 2, it extracts (subseq seq 2 5) -> "142".
    The collect keyword gathers all these extracted substrings into a list. The function returns this list: ("491" "914" "142").

Step 3: Calculating the Product with string-to-product

Once we have a series (like "491"), we need a way to calculate its product. This function handles that specific task.


(defun string-to-product (seq)
  "Converts a string of digits to their integer product."
  (apply #'* (map 'list #'digit-char-p seq)))

This is a dense, functional one-liner that's worth unpacking carefully.

  • (map 'list #'digit-char-p seq): This is the inner part. map applies a function to each element of a sequence. Here, it applies #'digit-char-p to each character of the input string seq. When given a digit character, digit-char-p returns its integer value. So for "491", this expression produces the list of numbers (4 9 1). The 'list argument tells map to return the results as a new list.
  • (apply #'* ...): The apply function takes a function (here, #'* for multiplication) and a list of arguments. It then calls the function with the elements of the list as if they were passed as separate arguments. So, (apply #'* '(4 9 1)) is equivalent to calling (* 4 9 1), which evaluates to 36.

Step 4: Orchestration with largest-product

This is the main function that ties everything together. It coordinates the other helper functions to produce the final result.


(defun largest-product (digits span)
  "Calculates the largest product of a series of a given span from a string of digits."
  (when (valid-input-p digits span)
    (if (zerop span)
        1
        (apply #'max (mapcar #'string-to-product (windows digits span))))))
  • (when (valid-input-p digits span) ...): It first calls our validation function. The when macro is a concise way of saying "if this condition is true, then execute the following body of code; otherwise, do nothing and return NIL." This prevents errors from bad input.
  • (if (zerop span) 1 ...): This handles a special edge case. The product of an empty set (a series of span 0) is mathematically defined as the multiplicative identity, which is 1. If span is 0, we immediately return 1.
  • (windows digits span): If the input is valid and span is not zero, we first call windows to get our list of series, e.g., ("491" "914" "142").
  • (mapcar #'string-to-product ...): mapcar is similar to map, but it's specifically designed to apply a function to successive elements of one or more lists, returning a list of the results. Here, it applies our string-to-product function to each string in the list of windows. This transforms ("491" "914" "142") into (36 36 8).
  • (apply #'max ...): Finally, just as we used apply for multiplication, we now use it with the max function. (apply #'max '(36 36 8)) is equivalent to (max 36 36 8), which returns the final answer: 36.

Data Flow Visualization

This diagram illustrates how data flows through our chain of functions, from the initial input to the final calculated result.

     ● Input: "49142", 3
     │
     ▼
┌──────────────────┐
│ largest-product  │
└─────────┬────────┘
          │ 1. Validate Input
          ▼
┌──────────────────┐
│   valid-input-p  │  ⟶ Returns T
└─────────┬────────┘
          │ 2. Generate Windows
          ▼
┌──────────────────┐
│      windows     │
└─────────┬────────┘
          │ Returns ("491" "914" "142")
          │
          │ 3. Map over each window
          ├─────────────────────────┐
          │                         │
          ▼                         ▼
┌──────────────────┐      ┌──────────────────┐
│ string-to-product│ ...  │ string-to-product│
│      ("491")     │      │      ("142")     │
└─────────┬────────┘      └─────────┬────────┘
          │ 36                      │ 8
          └──────────┬──────────────┘
                     │
                     ▼
┌────────────────────────────────────┐
│ apply #'max '(36 36 8)              │
└──────────────────┬─────────────────┘
                   │
                   ▼
               ● Result: 36

When to Optimize: A More Performant Approach

The functional solution presented above is elegant, readable, and perfectly idiomatic Common Lisp. However, for extremely large input strings (millions of digits), it has a performance drawback: the windows function creates a new list of all substrings. This can consume a significant amount of memory.

A more memory-efficient approach avoids creating this intermediate list. It uses a single "sliding window" and updates the product iteratively. This method is slightly more complex but can be much faster for massive inputs.

The Optimized Algorithm

  1. Calculate the product of the very first window (the first span digits).
  2. Initialize a max_product variable with this first product.
  3. Loop from the span-th digit to the end of the string. In each step:
    • Get the "outgoing" digit (the one leaving the window on the left).
    • Get the "incoming" digit (the one entering the window on the right).
    • Update the current product by dividing by the outgoing digit and multiplying by the incoming one.
    • Edge Case: If the outgoing digit is zero, you can't divide. You must recalculate the product for the new window from scratch.
    • Compare the new product with max_product and update if it's larger.
  4. Return max_product.

Optimized Common Lisp Implementation

Here’s what a more imperative, optimized version might look like. Note the increased complexity but improved memory profile.


(defun product (digit-string)
  "Helper to calculate product of a digit string."
  (reduce #'* (map 'list #'digit-char-p digit-string)))

(defun largest-product-optimized (digits span)
  (unless (valid-input-p digits span)
    (return-from largest-product-optimized nil))
  (when (zerop span) (return-from largest-product-optimized 1))

  (let ((max-product 0)
        (len (length digits)))
    (loop for i from 0 to (- len span)
          for current-window = (subseq digits i (+ i span))
          do (setf max-product (max max-product (product current-window))))
    max-product))

Note: This version is a simplified optimization that still uses subseq but avoids creating a giant list upfront with windows. A fully optimized version would avoid subseq in the loop entirely and manage indices manually, which adds even more complexity. For most cases, the original functional solution is preferred for its clarity.

Pros and Cons: Functional vs. Iterative

Choosing the right approach depends on your priorities: readability, elegance, or raw performance for massive datasets.

Aspect Functional Approach (Original Solution) Iterative Approach (Optimized)
Readability Excellent. Each function has a single, clear purpose. The flow is easy to follow. Good, but can become complex with manual index management and edge case handling (like zeros).
Memory Usage Higher. Creates an intermediate list of all window substrings in memory. Lower. Processes the string in-place without creating large intermediate data structures.
Performance Slower for very large inputs due to memory allocation and garbage collection overhead. Faster for very large inputs as it avoids memory overhead and performs fewer recalculations.
Idiomatic Lisp Highly idiomatic. Leverages functional composition, map, and apply. Less idiomatic. Leans more towards an imperative style with loops and state mutation (setf).

Frequently Asked Questions (FAQ)

What happens if the input string contains non-digit characters?

Our valid-input-p function will catch this. The expression (every #'digit-char-p digits) will return NIL, causing the main largest-product function to also return NIL, indicating invalid input.

How is a span of 0 handled?

A span of 0 represents an empty series. In mathematics, the product of an empty set (an "empty product") is defined as the multiplicative identity, which is 1. Our code correctly handles this by checking (if (zerop span) 1 ...) and returning 1 immediately.

What is the result if the span is larger than the input string's length?

This is another case handled by our validation function. The check (>= (length digits) span) will fail, and the entire function will return NIL without attempting any calculations.

Why use `apply #'*` instead of a manual loop for the product?

Using (apply #'* ...) is a concise and highly idiomatic way to express the operation in Common Lisp. It leverages the functional nature of the language. While a manual loop or reduce could also work, apply is often more direct and readable for this specific task.

Is this type of problem common in technical interviews?

Yes, absolutely. The "sliding window" is a fundamental algorithmic pattern. Interviewers use problems like this to assess a candidate's ability to handle strings, manage indices, consider edge cases, and analyze the time and space complexity of their solution.

Can this logic be adapted for finding the largest sum instead of product?

Yes, very easily. You would simply replace the multiplication operations with addition. In our functional solution, you would change (apply #'* ...) to (apply #'+ ...) in the string-to-product function (which you'd rename to string-to-sum). The rest of the sliding window logic remains identical.

What makes Common Lisp a good choice for this kind of problem?

Common Lisp excels at this type of symbolic and list-based manipulation. Its powerful higher-order functions like mapcar and apply, combined with the flexible loop macro, allow for very expressive solutions. You can write a highly readable functional solution or a finely-tuned iterative one, all within the same language. If you want to learn more, explore our complete Common Lisp guide.

Conclusion: You've Cracked the Code

You've successfully navigated the Largest Series Product problem, moving from understanding the core concepts to implementing a robust and elegant solution in Common Lisp. We've seen how to break down the problem using the sliding window technique, how to write clean, functional Lisp code by composing small helper functions, and how to analyze the trade-offs between a declarative style and a more performant iterative one.

This challenge is more than just an exercise; it's a practical application of fundamental programming patterns used in data analysis, signal processing, and more. By mastering this concept, you've added a powerful tool to your algorithmic arsenal and taken another significant step in your journey through the kodikra Common Lisp learning path.

Disclaimer: The code in this article is written against the ANSI Common Lisp standard and has been tested with modern implementations like Steel Bank Common Lisp (SBCL) 2.4+. The core functions used are standard and should be compatible with any compliant Common Lisp implementation.

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

Post a Comment