Being the thoughts and writings of one Gustaf Erikson; father, amateur photographer, technologist.
More stuff can be found at gerikson.tumblr.com and Flickr.
I tweet at @gerikson.
Follow my bookmarks at Pinboard.
I’m a bit fired up after Advent of Code, so thought I’d start by picking off some “easy” recent PE problems.
My first brute-force attempt found a solution after 4.5 hours, but access to the forum showed much smarter solutions so that’s what I’ve added to the repo.
Reused code from 577 to bruteforce a sequence that I could search for in Sloane.
Got a good way just by observing patterns. Could have used Sloane to find a sequence but forgot about it. Resolved to be more thorough in the future.
I suck at probalities so had to google for an answer.
I learned some extra stuff about Fibonacci numbers, that’s always fun.
I enjoyed this one. As before I confirmed the sequence using brute force and geometry, then tried to search OEIS (Sloane) for sequences.
The geometry was tricky, so I was glad to finally pull it off.
Generating the first few terms in the sought sequence with brute force leads to integers that can be searched for in OEIS.
Quite easy as befits its difficulty ranking of 20%.
I recycled my code for finding a root via bisection from the Blancmange problem.
I looked up efficient numerical integration methods and found a Perl implementation of Romberg’s method. I didn’t quite trust it so installed a Perl module for it instead. It turns out the first one was sufficient so it’s in the code now. I don’t want too many weird modules as dependencies.
Another old problem that I took a new look at!
Yet another old problem I started working on in 2012.
It’s straightforward numerical integration but I was tripped up by the error threshold.
Revisiting an old problem. I was messing around with symmetries etc but it turns out you don’t really need it.
3 minute runtime isn’t ideal though.
This is a fun problem!
After some attempts at a solution at the limit I went back to the Wikipedia page on the divisor function.
Implemented a priority queue for the first time, unfortunately the plethora of modules implementing this in Perl made it hard to choose. Finally went for the POE framework.
Returning to a problem after 3 years. This is slightly optimized brute-force and can be much quicker.
Easing back into PE again. I’m picking off problems in ascending difficulty order.
A fun problem!
My initial idea was to utilize Snell’s law, which was indeed the right idea, but I didn’t have the right constraints.
After a while I rethought the problem to minimize a multi-variable function using the “downhill simplex” algorithm.
Brute-forcing for 5 minutes gave the correct answer, and access to the forum and an even faster solution…
Pretty happy with this solution!
Algo adopted from this solution.
I had to write some code for AoC 2017 day 22 which matched up with this pretty nicely.
Based on the difficulty raiting of this problem I guessed it had an analytical solution, and indeed the answer can be easily expressed in binomial terms.
Another Math::Prime::Util example.
Another Math::Prime::Util example.
Scrounged around in the documentation to Math::Prime::Util and found this under the examples section.
The idea to use a bitmask to represent the sets is from this page, as is the clever way to test rule 2.
This is the Hungarian algorithm.
Fresh from Advent of Code 2016 I thought it would be nice if I organized my Project Euler solutions and cleaned them up a bit.
They’re being added to my Github repo as I go through them, verify they are working on newer Perls, and generally try to streamline the code.
I’ve found a few “solved” problems that don’t actually have any solutions, but where I do have access to the answer forums. I’ve used solutions there for some problems, and credited the source in the comments.
This was a fiddly one. But once you get the actual state changes correct it’s simply a matter of extracting the values that will be displayed and calculate how much it’ll “cost” to display them.
Another one off the list of unsolved problems in ascending difficulty. Perl string manipulation makes this one easy.
I had to try to solve this without access to my previous favorite Perl module: Math::Pari, and it took almost an hour to run.
An unexpected way of using two cubes to make a square.
The key to this is to handle the fact that 6 and 9 are equivalent. Once I’d handled that I had to eliminate duplicates. Otherwise it’s pretty straightforward.
The hyperexponentiation of a number.
You get to the start of the trail by reading the Wikipedia article on tetration.
Find an efficient algorithm to analyse the number of solutions of the equation 1/x + 1/y = 1/n.
We know from problem 108 how the answer is formed. The trick is to generate a number of integers from the prime factors, to find which combination has the most divisors.
This was a fun one, I did try a 2nd-order brute force approach after some research and realized it would break the 1-minute rule but let it run anyway for about 10 minutes and got the answer.
Did quite some research on this but in the end extended a “classic” Hamming number generator (for 5-smooth numbers) that I found on Rosettacode.com. Bit of a cheat and runs in 2 minutes instead of the required 1.
Investigate the game of chance involving coloured discs.
I suck at probabilities and had to google for hints for this one.
Investigating multiple reflections of a laser beam.
This was fun, once I figured out the geometry. Another thing to watch out for is comparing 2 floats for equality.
Using four distinct digits and the rules of arithmetic, find the longest sequence of target numbers.
Straightforward brute force, helped by the Perl Algorithm::Combinatorics module to find different permutations and so on.
Runs in about 36s with some debugging info.
This was basically the same as 173, my code needed changes to 3 lines and some hash counting code.
Investigate the optimum polynomial function to model the first k terms of a given sequence.
o/~ All by myself…
Pretty proud of this one. Used linear algebra to solve for the coefficients in each successive polynomial. Unfortunately the Perl Math::Matrix package didn’t let me easily extract the values so I had to copy-paste into a separate script to check against the correct values.
Using up to one million tiles how many different “hollow” square laminae can be formed?
On a roll today!
This wasn’t too hard once I sorted out all the fencepost errors.
Investigating almost equilateral triangles with integral sides and area.
The hinge for this is discovering that the solution can be expressed as a Pell’s equation, this puzzle is helpful.
Fell for the spoiler urge, not proud of it.
In the game, Monopoly, find the three most popular squares when using two 4-sided dice.
This marks my return(?) to Eulering. I did a lot of research for this a long time ago, and was planning on implementing a Markov chain approach based on the results from this page but after falling for the trap of googling for solutions I found that most people simply simulate the dice rolls, counting the number of times the dice hits each cell.
I simulated 1 million throws and got a result in about 5 seconds.
Found searching for “project euler” in OEIS.
These all flow from 114, and the secret there is to use recursion to try to fill the space to the right. Don’t forget to memoize the recursion function.
Easily done if you have a few million primes on hand.
There’s a sequence in Sloane that gives the answer directly, too!
Finding the number of blue discs for which there is 50% chance of taking two blue.
I started researching the hypergeometric distribution and thought about comparing it to a binomial distribution at large numbers before twigging that if you expand the problem it’s a quadratic Diophantine equation. There’s an online solver that provides factors for these equations and after that it was simply a matter of plugging them in.
I had in mind optimisations in only calculating half the triangle, but in the end it didn’t signify. I used the Pari issquarefree() function.
Biggest issue was forgetting telling Perl to use arbitrary precision integers.
Investigating the numbers which are equal to sum of their digits raised to some power.
I turned this over in my mind trying to find some limit so I didn’t have such an enormous search space. Then I found A023106 in Sloane which gives all but the last few terms, and then it was really fast to brute force.
To be quite honest this was a bit easy for this level.
Project Euler “is a series of challenging mathematical/computer programming problems that will require more than just mathematical insights to solve.” In other words, you need to get down and program to solve the problem[1].
I’ve recently reached Level 3 (solved over 100 problems) and thought I’d share some notes on what I’ve learned.
PE programming is “pure” programming, as in you’re working with algorithms and not systems. There’s rarely anything more complicated than file access needed. In fact, I’d say you need an aptitude for problem solving rather than programming, and the skills needed to solve PE problems are probably not really translatable to real work out in the real world, where you’re dealing with real people and real hardware and networks. To be sure, nowhere on PE do they say that this is programming in the wider sense, as opposed to Computer Science, but you’d be surprised how many CS grads think it does (I’m mocking you, Haskell nerds!).
The typical PE problem looks amenable to brute force, but it pays to research before jumping in. Wikipedia and Mathworld are great resources for a lot of the problems, often explaining the math behind them and sometimes having the algorithms you need.
Spoilers. I find it pretty hard to concentrate on a problem and not want to know the solution, especially when I’m into “grind” mode and just want to level up (this happens a lot with me and puzzle games too). There are plenty of spoilers around for the early problems (the ones that most people manage to solve) but as you move up they get sparser and sparser, and are usually in languages other than your chosen one. Often it’s enough for me to just get a hint. After you’ve solved a problem, you get access to a forum where others discuss their solutions. This can be an eye opener, but there’s no need to share your crappy solution if you don’t want to.
I use Perl. I thought of using PE to learn another language (Python), but finally I felt it was more fun to explore something I’m pretty proficient in than to learn something else. Perl has all the things you need for these problems (so far), especially as there are tons of libraries for specific applications. One of the more useful is Math::Pari, an interface to the Pari suite of numerical algorithms.
Perl is really nice for stuff like string manipulation and set operations. It’s also really easy to build ad-hoc data structures, although the syntax grows hairy really fast.
Python seems very popular among PE participants. Another popular language among the people who bother to post to answer threads is J), and of course Haskell has some vocal devotees.
I find it challenging and fun to work on these problems, and I encourage you to do the same!
[1] although there are some wizards who manage with pencil and paper, at least for the earlier problems.