# Project Euler

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.