Project Euler #40: Champernowne's constant

This article is part of a series where I'll be diving head first into the Project Euler puzzles. I want to document the challenge of solving such a puzzle and how I got to the answer. I want to prefix this by stating that I can't cheat for any of these challenges; with that I mean I can't look up any other implementations online. After the implementation, I will validate the answer by using this document or a similar sheet.

In this article I'll be solving: Project Euler #40.

Introduction The puzzle starts by showing us an irrational decimal fraction which looks like this:

             |
             V
0.123456789101112131415161718192021...

The 12th digit in that decimal fraction is a 1. It took me a little while to figure out the pattern, but it is really simple:

0.1 2 3 4 5 6 7 8 9 10 11 12 13 14

Find d1 × d10 × d100 × d1000 × d10000 × d100000 × d1000000.

Champernowne’s method The first part is to make a method, which returns the Champernowne’s constant as a vector:

fn champernowne(max: u64) -> Vec<u8> {
    let mut s = String::from("");

    for n in 1..=max {
        s.push_str(&n.to_string());
    }

    s.chars()
        .map(|n| n.to_digit(10).unwrap() as u8)
        .collect()
}

#[test]
fn test_champernowne() {
    assert_eq!(champernowne(12), vec![1,2,3,4,5,6,7,8,9,1,0,1,1,1,2]);
}

Nothing too complex yet. The next trick is to make a vector of length 1.000.000. This is not the same as champernowne(1_000_000). We need to tweak our method a little, and check if the string s becomes over a million in length (or in our case: max).

fn champernowne(max: u64) -> Vec<u8> {
    let mut s = String::from("");

    for n in 1..=max {
        s.push_str(&n.to_string());

        if s.len() >= max as usize {
            break;
        }
    }

    s.chars()
        .map(|n| n.to_digit(10).unwrap() as u8)
        .collect()
}

#[test]
fn test_champernowne() {
    assert_eq!(champernowne(12), vec![1,2,3,4,5,6,7,8,9,1,0,1,1]);
    assert_eq!(champernowne(12).len(), 13);
}

The method produces a vector with some extra bits near the end, which is fine for what we’re trying to achieve. We do have to take into account that we don’t count the leading 0 in our solution, so all the indexes that are mentioned in the problem statement need to be reduced by 1. Being aware of that situation, the solution to problem_40() becomes 210.

fn problem_40() -> u64 {
    let c = champernowne(1_000_000);

    c[0] * c[9] * c[99] * c[999] * c[9999] * c[99_999] * c[999_999]
}

#[test]
fn test_problem_40() {
    assert_eq!(problem_40(), 210);
}

The full solution is available on GitHub.

55545352515049484746454443424140393837363534333231302928272625242322212019181716151413121110987654321