I wanted to learn a new language (Rust), and a common, fun way of learning a new language is to solve problems on Project Euler. These are math problems ranging in difficulty from 5% (easiest) to 100% (hardest), typically drawn from number theory, set theory, combinatorics, and various other topics. Each solution is a unique numeric value, and while there are often multiple ways of solving a given problem, we must consider the algorithmic complexity. The goal is a program which can find the solution in under 1 minute, but I personally feel better if it finishes in under 1 second 😀 A naive solution can take days, months, or years, even on a very fast computer!

A recent problem I encountered was to solve Sudoku puzzles, another problem involved scoring poker hands. These have been quite a bit of fun, not only learning new math concepts, but expanding my knowledge of algorithms, data structures, and problem-solving techniques. I find they push me to the limits, out of my comfort zone, and besides that, they are a great demonstration of why algorithm design, CS theory and math theory are important in software development.

**NOTE:** I’m going to follow the rules and not publish my solutions, as it spoils the challenge for others. However, if anyone happens to be working on a problem and wants to discuss it, I would be happy to! 🙂

## Concepts

Useful concepts to know

**Algorithm and data structure analysis:**it’s*extremely*helpful to quickly estimate the scale of the problem, and eliminate solutions that require too many resources.**Polygonal / figurate numbers:**numbers that can be arranged into polygonal shapes.**Integer and prime factorization methods:**the faster, the better!**Mixed radix numbers:**some problems can be interpreted as mixed radix systems.**Combinations:**“n choose k”, how many ways can we take k things from a set of n things? Order doesn’t matter: {A,B,C} is the same as {C,B,A}. Also, know combinations*with*repetition (multicombinations, multisubsets).**Permutations:**arrange a set of n things into a unique order.**Binomial coefficients:**useful to find the number of combinations of a set.**Gray codes:**binary counting where only a single bit changes/flips: 1101 => 1111 => 1110.**Integer partitioning:**how many distinct ways can we add smaller integers to equal n? (e.g. 4 = 3 + 1 = 2 + 2 = 2 + 1 + 1 = 1 + 1+ 1+ 1)**Integer composition:**like partitioning, only order matters (3 + 1 and 1 + 3 are distinct).**Sets:**all of the above (combinations, permutations, partitions)**Multisets:**all of the above (combinations, permutations, partitions)**Tree and graph construction and traversal:**some problems can be expressed as a tree or graph structure, and there are well-known, efficient algorithms for manipulating them.**Recursion:**some problems are naturally recursive, but it’s not always the most efficient solution! (e.g. compare calculating binomial coefficients recursively for large n,k vs. using multiplication)

## References

Some handy references for solving these types of problems.

- “The Art of Computer Programming” by Donald E. Knuth. Embarrassingly, I had never read this book until I started working on PE problems. It’s an invaluable reference, especially Volume 4 which deals extensively with combinatorial algorithms. You can get the uncorrected pre-fascicles for free: http://www.cs.utsa.edu/~wagner/knuth/
- “Combinatorial Generation” by Frank Ruskey. Another solid reference for combinatorial problems
- The Online Encyclopedia of Integer Sequences (OEIS). A great resource for discovering well-known sequences of integers