Pythagorean Triples

2012-10-27

When Programming Praxis mentioned that the newest challenge sounded like a Project Euler problem, they were’t wrong. Basically, the idea is to count the number of Pythagorean Triples with perimeters (sum of the three numbers) under a given value. The necessary code to brute force the problem is really straight forward, but then they asked for the count up to one million. With the brute force O(n^2) algorithm (and a relatively high constant), that’s not really feasible. So that’s when we have to get a bit more creative.

Prime Partitions II: The Listing

2012-10-22

As the continuation of Saturday’s post on counting the number of prime partitions of a number without actually determining what those partitions are, today we’re going to work out the actual list of partitions.

Prime Partitions

2012-10-20

Today we’re back into the mathy sort of problems from Programming Praxis, tasked with calculating the number of prime partitions for a given number–essentially, how many different lists of prime numbers are there that sum to the given number.

For example, working with 11, there are six prime partitions (I’ll show the code for this later):

> (prime-partitions 11)
'((2 2 2 2 3) (2 2 2 5) (2 2 7) (2 3 3 3) (3 3 5) (11))

Unfortunately, the number of prime partitions quickly gets ridiculous. Once you get to 1000, there are 48 quadrillion prime partitions… So generating all of them isn’t exactly feasible.

Memoization in Racket

2012-10-20

Memoization is awesome!

I’ve already written one post on the subject in Python, but this time we’ll do the same in Racket. It’s particularly timely as without it, today’s post on determining the number of prime partitions of a number would take longer to run than I care to wait.

The Evolution Of Flibs

2012-10-18

In the past, I absolutely loved messing around with genetic algorithms. The idea of bringing the power of natural selection to bear to solve all manner of problems just appeals to me for some reason. So when I came across a puzzle on on Programming Praxis called flibs source code The eventual goal will be–given a binary sequence–to evolve a finite state machine that will recognize the sequence and output the same, offset by one.

Rule 30 RNG

2012-10-17

Today we get away from the word games for a little while and get back to talking about random number generators (previous posts here and here). Or rather one random number generator in specific: a Rule 30 psuedo-random number generator (PRNG). (Here’s the motivating post from Programming Praxis.)

Remember the previous post I made about cellular automaton? The basic idea is to turn those into a random number generator. If you go back to the linked post in particular and give it Rule 30 with a random initial state, you can see how chaotic the rows seem to be. Perfect for a PRNG.

Chopping words

2012-10-15

One more challenge from Programming Praxis’ Word Games today (there are only a few left!). This time we have the challenge of cutting off bits of words, one letter at a time, such that each step is still a word.

The example given in their post is planet → plane → plan → pan → an → a, although surely many such examples exist.

Dodgson’s Doublets

2012-10-14

Today we have doublets source code, dictionary source code, queue source code. Using the same source code as the previous two posts (here and here, described originally here) for the dictionary, the code is a pretty straight forward case of using recursion to do backtracking. Basically, try all of the possible next words one letter different. Whenever you find a dead end, back up and try a different path. Something like this:

Word cubes

2012-10-13

Continuing in my recent set of word-cube source code. Like yesterday, it’s designed to work in Racket 5.3+.

Squaring the Bishop

2012-10-11

Okay, this one was just neat. Based on word-squares source. I’ve only tested it in Racket 5.3+, but newer versions should work as well. Racket 5.2 won’t work without some tweaking as (at the very least) it’s missing a definition for string-trim.