Thursday, 2021-01-14

719: Number splitting

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.

Tuesday, 2018-10-16

351: Hexagonal orchards

Reused code from 577 to bruteforce a sequence that I could search for in Sloane.

Monday, 2018-10-15

407: Idempotents

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.

Sunday, 2018-10-14

323: Bitwise-OR operations on random integers

I suck at probalities so had to google for an answer.

Friday, 2018-10-12

297: Zeckendorf Representation

I learned some extra stuff about Fibonacci numbers, that’s always fun.

Thursday, 2018-10-11

577: Counting hexagons

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.

Sunday, 2018-10-07

138: Special isosceles triangles

Generating the first few terms in the sought sequence with brute force leads to integers that can be searched for in OEIS.

Saturday, 2018-10-06

587: Concave triangle

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.

Friday, 2018-10-05

549: Divisibility of factorials

Another old problem that I took a new look at!

226: A scoop of blancmange

Yet another old problem I started working on in 2012.

It’s straightforward numerical integration but I was tripped up by the error threshold.

Wednesday, 2018-10-03

504: Square on the inside

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.

Monday, 2018-10-01

622: Riffle Shuffles

This is a fun problem!

Thursday, 2018-09-27

500: Problem 500!!!

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.

Tuesday, 2018-09-25

381: (prime-k) factorial

Returning to a problem after 3 years. This is slightly optimized brute-force and can be much quicker.

Friday, 2018-09-21

346: Strong repunits

Easing back into PE again. I’m picking off problems in ascending difficulty order.

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 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

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.

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.

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.