Tuesday, 2018-01-09

607: Marsh crossing

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.

Thursday, 2018-01-04

301: Nim

Problem description.

Brute-forcing for 5 minutes gave the correct answer, and access to the forum and an even faster solution…

Wednesday, 2018-01-03

118: Pandigital prime sets

Problem description.

Pretty happy with this solution!

Tuesday, 2018-01-02

111: Primes with runs

Project description.

Algo adopted from this solution.

349: Langton’s Ant

Problem description.

I had to write some code for AoC 2017 day 22 which matched up with this pretty nicely.

Friday, 2017-01-13

493: Under The Rainbow

Project description

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.

Thursday, 2017-01-12

214: Totient Chains

Problem description.

Another Math::Prime::Util example.

211: Divisor Square Sum

Problem description.

Another Math::Prime::Util example.

131: Prime cube partnership

Problem description.

Scrounged around in the documentation to Math::Prime::Util and found this under the examples section.

Tuesday, 2017-01-10

105: Special subset sums: testing

Problem description.

The idea to use a bitmask to represent the sets is from this page, as is the clever way to test rule 2.

Thursday, 2017-01-05

Wednesday, 2016-12-28

Project Euler cleanup

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.

Tuesday, 2015-11-17

315: Digital root clocks

Problem description.

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.

Saturday, 2015-11-14

387: Harshad numbers

Problem description.

Another one off the list of unsolved problems in ascending difficulty. Perl string manipulation makes this one easy.

Wednesday, 2015-09-09

357: Prime generating integers

Problem description.

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.

Saturday, 2012-11-17

90: Cube digit pairs

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.

Tuesday, 2012-10-16

188: Tetration

The hyperexponentiation of a number.

You get to the start of the trail by reading the Wikipedia article on tetration.

Monday, 2012-10-15

110: Diophantine reciprocals II

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.

Thursday, 2012-10-11

148: Exploring Pascal’s triangle

Problem link.

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.

Wednesday, 2012-10-03

204: Generalised Hamming Numbers

Problem description.

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.

Tuesday, 2012-10-02

121: Disc game prize fund

Investigate the game of chance involving coloured discs.

I suck at probabilities and had to google for hints for this one.

Monday, 2012-10-01

144: Investigating multiple reflections of a laser beam

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.

Thursday, 2012-09-13

93: Arithmetic expressions

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.

Wednesday, 2012-09-12

174: Counting hollow square laminae

Counting the number of “hollow” square laminae that can form one, two, three, … distinct arrangements.

This was basically the same as 173, my code needed changes to 3 lines and some hash counting code.

Tuesday, 2012-09-11

173: Hollow Square Laminae

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.

101: Optimum polynomial

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.

94: Almost equilateral triangles

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.

Monday, 2012-09-10

88: Product-sum numbers

Fell for the spoiler urge, not proud of it.

Friday, 2012-09-07

84: Monopoly odds

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.

Thursday, 2011-11-03

193: Squarefree numbers

Problem description.

Found searching for “project euler” in OEIS.

Saturday, 2011-10-29

Friday, 2011-10-28

187: Semiprimes

Problem description.

Easily done if you have a few million primes on hand.

There’s a sequence in Sloane that gives the answer directly, too!

Thursday, 2011-10-27

100: Arranged probability

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.

Wednesday, 2011-10-26

203: Squarefree Binomial Coefficients

Problem description.

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.

119: Digit power sum

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.

Thursday, 2010-03-25

Notes on Project Euler

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.