HomeRésuméOpen SourceWorkBlog

Project Euler in Rust, Part 2

Monday, 01 December 2025

Over the last few months (I started writing this blog post in September), I've continued to learn Rust by working through Project Euler problems. Since I will be giving a talk about Rust at ConFoo in February, learning Rust is no longer just for fun - I also need to make sure I don't make a fool of myself.

Below is an overview of some of the problems that I have solved in Rust and what I learned from each. Overall, I have definitely grown more comfortable with the syntax of Rust and its system of ownership, but there are certainly parts of Rust that I know I still need to explore.

Poker Hands

Project Euler problem 54 involves analyzing a set of one thousand hands of poker, and for each hand, determining whether Player 1 (the first five cards) would win in a head-to-head matchup against Player 2 (the remaining five cards). For this problem, I got my first taste of how to integrate custom types with Rust's default handling for comparisons, cloning, traits, and other built-in functionality.

In poker, some types of hands (like a straight or flush) are always better than other kinds (like a high card or pair) regardless of which specific cards are in the hand. But, when comparing hands of the same type (like a high card and another high card) the specific cards need to be compared.

To represent the type of hand, I used an enum:

enum HandRank {
	HighCard = 1,
	OnePair,
	TwoPair,
	ThreeOfAKind,
	Straight,
	Flush,
	FullHouse,
	FourOfAKind,
	StraightFlush,
	RoyalFlush,
}

By assigning HighCard = 1, I ensure that each subsequent rank is given a subsequent value. In C, for example, the enumeration case is essentially just a constant with the underlying value of the case, and thus can be treated as an integer for the purposes of comparison. In PHP, on the other hand, enums by default have no associated value, and when they do have a value (backed enums), comparing two cases of an enum requires accessing the backing values directly (for seeing which case has a greater value; equality checking can be done on the enum cases directly).

Rust, on the other hand, requires explicitly implementing the comparison operators that are used. Generally, this would be done with by implementing the PartialEq and PartialOrd traits for the desired type, in this case HandRank. However, Rust provides nice shortcuts for the reasonable case of comparing all of the fields: deriving from the generic trait.

In the case of the HandRank enum, adding #[derive(PartialEq)] results in an implementation of eq() where two ranks are considered equal if they have the same backing value, and unequal otherwise. Similarly, #[derive(PartialOrd)] results in ordering based on the order of cases. Which is exactly the behavior that we want!

I made use of the derive attribute while working on the sudoku solver, but not as much as I did for the poker analyzer. And, based on the derive documentation, it seems that it is possible for developers to add their own derive-able macros to provide shortcuts for implementing functions. Reading through the documentation, it seems that Rust's attribute system is significantly more powerful than PHP's attributes. I definitely need to spend some time looking into Rust's attributes.

That said, not everything can be derived, and sometimes a manual implementation of the method for a generic trait is needed. For example, when I wanted to be able to debug the program and print out a poker hand, I needed to manually implement the std::fmt::Display trait for formatting a card suit as a string:

impl std::fmt::Display for CardSuit {
	fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
		let rep: char = match self {
			CardSuit::Clubs => 'C',
			CardSuit::Diamonds => 'D',
			CardSuit::Hearts => 'H',
			CardSuit::Spades => 'S',
		};
		return write!(f, "{}", rep);
	}
}

I'm not entirely clear on how exactly std::fmt::Formatter works, but again, the Rust compiler gave me plenty of guidance and eventually I got there.

Coin Sums

I next worked on problem 31, asking for the number of ways to make a collection of coins add up to two pounds. This was the first Project Euler problem that I implemented in Rust that I hadn't already solved in another language. I figured that I couldn't really claim to be proficient in Rust if I was just converting code that I already knew worked from other languages.

My initial code was extremely inefficient: test every possible combination of coins of one pence, two pence, five pence, ten pence, twenty pence, fifty pence, one pound, and two pounds, as long as no individual denomination represented more than two pounds. In other words, I used a brute force approach. This worked, but was extremely inefficient.

My first optimization was to remove the two pound coin, and manually add that combination (a single two pound coin and no other coins). In any other combination with a two pound coin, the total would be over two pounds, and could just be skipped. At that point, the program took over 7 minutes to run, but it produced an answer. I submitted it to Project Euler, and it was correct!

I next started working on additional optimizations to avoid checking excessive combinations. The denomination with the most options to check is the one pence coin. But, for any combination of other coins, there is at most one quantity of one pence coins to bring the total sum of the coins to two pounds. In other words, we just need to check for combinations of the other coins, and any combination that totals to two pounds or less corresponds to a total that, when using some number of one-pence coins, would reach two pounds. With just this one additional optimization, the total execution time dropped to be just under two seconds. If the two pound coin was added back instead of being handled manually, execution would still only take roughly four seconds.

Project Euler problems are designed according to a "one-minute" rule, where efficiently powerful computers can, with the right algorithm, solve any problem in under a minute. Thus, only the one pence optimization was needed. And while further optimizations are definitely possible, in the interest of focusing on learning Rust I'm not going to invest more time in implementing those optimizations.

Amicable and Abundant Sums

Building off of my success with coin sums, I next tackled problem 95, which asks for an analysis of amicable chains. I won't go into the math involved here (see the Project Euler page for that), but when I successfully answered the problem I got a pleasant surprise: I advanced the "Level 2" on Project Euler. Each level represents 25 problems being solved; problem 95 was my 50th overall problem on Project Euler.

In the process of solving this problem, I also got more exposure to Rust's standard library, making use of both vectors (std::vec) and hash sets (std::collections::HashSet). I plan to try and make use of the standard library more as I continue my experimentation in Rust - now that I understand the basics, using existing implementations of generic data structures will allow me to focus more on trying to "think" in Rust when I am designing my solutions to other problems, rather than getting bogged-down in the details of various data structures.

I then reused my logic for determining the factors of a value to implement problem 23 (the problems do not need to be done in order). To be able to share code between files, I need to mark the function or trait as pub - Rust seems to base visibility around files, in contrast with some other languages that I've worked with.

Thinking in Rust

I spent a long time working on problem 102, which requires count the number of triangles provided that contain the origin (the point (0, 0)). But, my struggles were not with Rust, but rather with the algorithm for determining if a triangle contains the origin or not. Over the two weeks that I worked on this problem off and on, I rewrote the entire logic multiple times. Other than a few simple compilation issues that I immediately understood and was able to fix (e.g. not borrowing an argument), I was able to focus entirely on the logic and the problem, rather than how to implement my ideas in Rust. I'm definitely getting more comfortable with coding in Rust.

I then set myself a challenge - try to solve some problems without having internet access to be able to debug my understanding of Rust and to investigate what methods are available. In fact, I did these problems while on a flight, where I wouldn't be able to "cheat" if I got stuck. Unfortunately, I neglected to set up the Rust documentation locally before beginning, so the only thing I could refer back to was the code that I had written previously in Rust, and the guidance provided in error messages.

Before the flight, I downloaded the instructions for six different problems from Project Euler. I did not expect to complete all of them, but figured that if I got stuck on one problem I could just work on another. To my surprise, during the flight I was able to complete all six of the problems, and when I submitted my answers after landing, I got all six problems correct:

A number of these problems dealt with prime numbers, and I started writing some reusable logic for those problems and later ones. I dealt tangentially with prime numbers as part of problem 95 (discussed above), but not in a way that was easily reusable. The next step is probably to extract that code into a dedicated crate (Rust's version of a library package) locally. Doing so will also let me explore the crate system further - though organization of libraries is generally orthogonal to the language itself, in Rust the crate system seems intimately tied to the language structure, and is something that I will need to cover in my talk about Rust at ConFoo.

Footguns

While I am definitely getting more familiar with Rust, there are some places where a mistake leads to a logic error rather than a compilation error. In other words, instead of Rust telling me that I made a mistake when I try to compile the progrem, the program compiles and runs "correctly" (in terms of Rust semantics), but does something different from what I had intended.

Nowhere was such a mistake more painful (so far) than while working on problem 30, which dealt with exponentiation. From various math classes and the TeX markup language, I have grown used to '^' indicating exponentiation. However, in Rust (and many other languages) this indicates the "bitwise xor" operator. So, when I tried to use '^' to raise a digit to the power of five, the result was not what I expected. I'm not sure why I forgot that '^' generally indicates "bitwise xor" in software.

"Bitwise xor" takes two numbers, considers them as patterns of bits, and returns a number (as a pattern of bits) with a '1' where exactly one of the inputs had a '1', and a '0' otherwise. For example:

As a result of this confusion, despite getting the algorithm correct for problem 30 on my first try, I ended up spending a while debugging the algorithm before I realized my mistake.

Next Steps

Over the last few months, I've identified a few aspects of Rust that I have yet to explore but that definitely warrant attention. Even if I don't end up using them much myself, I need to understand the following topics enough to be able to discuss them at ConFoo:

Hopefully, I can look into some of these topics while working on Project Euler problems. If not, I'll need to find some other source of inspiration for what exactly my code should try to do.

Content is © 2025 Daniel Scherzer