Project Euler #56: Powerful digit sum

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 #56.

Introduction

“Considering natural numbers of the form, ab, where a, b < 100, what is the maximum digital sum?”

Part 1: sum_vec(), mul_vec() and to_digits()

I’ll be reusing the code originally started in “Power digit sum” to form the base of this puzzle. The next part is to take the power of a 100 of each digit and check which consecutive iteration of each vector contains the most digits (so: multiply by the same vector each time).

fn max_power_digit_sum(digit: u128) -> u64 {
    let mul_digits = digit.to_digits();
    let mut digits = digit.to_digits();
    let mut max = 0;

    for _ in 2..=100 {
        digits.mul_vec(&mul_digits);

        let sum = digits.iter().fold(0, |acc, &n| acc + n as u64);

        if sum > max {
            max = sum;
        }
    }

    max
}

#[test]
fn test_max_power_digit_sum() {
    assert_eq!(max_power_digit_sum(10), 1);
    assert_eq!(max_power_digit_sum(99), 972);
}

Part 2: Resolving problem 56

To resolve problem 56 do the following:

fn problem_56() -> u64 {
    let mut max = 0;
    let mut a = 99;

    while a > 2 {
        let pds = max_power_digit_sum(a);
        if pds > max {
            max = pds
        }
        a -= 1;
    }

    max
}

#[test]
fn test_problem_56() {
    assert_eq!(problem_56(), 972);
}

The code is not fast, but it results in the right answer. It resolves in 9.16s.

The full solution is available on GitHub.

5655545352515049484746454443424140393837363534333231302928272625242322212019181716151413121110987654321