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.