Project Euler #38: Pandigital multiples
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 #38.
Introduction
“What is the largest 1 to 9 pandigital 9-digit number that can be formed as the concatenated product of an integer with (1,2, … , n) where n > 1?”
Multiply concat
Step 1 of this problem is taking an integer and multiplying it by 1,2,3 etc. and concatenating the answer to a total as a String.
fn multiply_concatenate(mut n: u64) -> String {
let mut multiplier = 1;
let mut total = String::from("");
while multiplier > 0 {
n *= multiplier;
total.push_str(&format!("{}", n));
multiplier += 1;
break
}
total
}
#[test]
fn test_multiply_concatenate() {
assert_eq!(multiply_concatenate(192), String::from("192384576"))
}
Duplicate or pandigital
Obviously the test fails at this point, and it returns “192”. The trick right now is to check if each digit is unique (and remains unique), and if it becomes pandigital at one point. If both conditions are met, you can stop the while loop. In the case of a duplicate digit entering the total String, we should return a special type of String or a None. Using Some and None we get this function:
fn multiply_concatenate(n: u64) -> Option<String> {
let mut multiplier = 1;
let mut total = String::from("");
let pandigital = vec!['1', '2', '3', '4', '5', '6', '7', '8', '9'];
loop {
total.push_str(&format!("{}", n * multiplier));
let mut chars = total.chars().collect::<Vec<char>>();
let duplicates = pandigital
.iter()
.any(|d1| {
chars
.iter()
.filter(|d2| *d2 == d1)
.count() > 1
});
if duplicates {
break None
}
chars.sort();
if chars == pandigital {
break Some(total)
}
multiplier += 1;
}
}
#[test]
fn test_multiply_concatenate() {
assert_eq!(
multiply_concatenate(192),
Some(String::from("192384576"))
);
assert_eq!(multiply_concatenate(1), Some(String::from("123456789")));
assert_eq!(multiply_concatenate(2), None)
}
Solution
The next step is to tackle the actual puzzle. The puzzle asks for the largest possible number (meaning length in digits, in this particular case), implying there’s no reasonable upper bound (I’m noticing a trend here). Considering the result of each product is concatenated to the total, the amount of digits duplicates (at least) very quickly after at least 2 cycles. So a reasonable upper bound would be to check until 99.999 (the highest number with 5 digits). The puzzle clearly isn’t assuming 123.456.789 as a candidate. To get to the solution I did this:
fn problem_38() -> String {
let mut max = 1;
let mut result = String::from("");
for n in 1..=99_999 {
match multiply_concatenate(n) {
Some(t) => {
if n > max {
result = t;
max = n;
}
},
None => {}
}
}
result
}
#[test]
fn test_problem_38() {
assert_eq!(problem_38(), String::from("932718654"));
}
Voila! The answer is “932718654”.
Improvements
A thing I don’t really like about Rust is empty match-branches; so let’s get rid of those! The first step is to simply return a String for multiply_concatenate. In the None-case, return an empty string instead. After changing that, we can reduce problem_38() down to this:
fn problem_38() -> String {
let mut result = String::from("");
for n in 1..=99_999 {
let t = multiply_concatenate(n);
if !t.is_empty() {
result = t;
}
}
result
}
#[test]
fn test_problem_38() {
assert_eq!(problem_38(), String::from("932718654"));
}
That’s elegant enough for me!
The full solution is available on GitHub.
