Generating non-repeating strings

2012-12-12

Based on this post from Programming Praxis, today’s goal is to write an algorithm that, given a number N and an alphabet A, will generate all strings of length N made of letters from A with no adjacent substrings that repeat.

So for example, given N = 5 and A = {a, b, c} the string abcba will be allowed, but none of abcbc, ababc, nor even aabcb will be allowed (the bc, ab, and a repeat).

It’s a little more general even than the version Programming Praxis specifies (they limit the alphabet to exactly *A = {1, 2, 3} *and more more general still than their original source which requires only one possible string, but I think it’s worth the extra complications.

Numbers of Wirth

2012-12-10

Niklaus Wirth gave the following problem back in 1973:

Develop a program that generates in ascending order the least 100 numbers of the set M, where M is defined as follows:

a) The number 1 is in M.

b) If x is in M, then y = 2 * x + 1 and z = 3 * x + 1 are also in M.

c) No other numbers are in M.

(via Programming Praxis)

It’s an interesting enough problem, so let’s work out a few different ways of doing it.

One Billion Primes - Segmented Sieve

2012-11-29

After a sum of the first billion primes post (originally from Programming Praxis), I decided to finally write a segmented version of the Sieve of Eratosthenes.

List algorithms and efficiency

2012-11-21

Programming Praxis’ new challenge(s) are to write three different list algorithms three times, each with a different runtime complexity. From their first post last week we have list intersection and union and from a newer post yesterday we have the difference of two lists. For each of those, we want to be able to write an algorithm that runs in O(n²) time, one that runs in O(n log n), and finally one that runs in O(n). It turns out that it’s more of an exercise in data structures than anything (although they’re all still technically ’list’ algorithms), but it’s still interesting to see how you can achieve the same goal in different ways that may be far more efficient.

Project Euler 9

2012-11-15

A Pythagorean triplet is a set of three natural numbers, a b c, for which,

a² + b² = c²

For example, 3² + 4² = 9 + 16 = 25 = 5².

There exists exactly one Pythagorean triplet for which a + b + c = 1000.

Find the product abc. – PROJECT EULER #9

Project Euler 8

2012-11-14

Find the greatest product of five consecutive digits in the 1000-digit number. – PROJECT EULER #8

Project Euler 7

2012-11-12

By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.

What is the 10 001st prime number? – PROJECT EULER #7

Project Euler 6

2012-11-11

The sum of the squares of the first ten natural numbers is,

1² + 2² + … + 10² = 385

The square of the sum of the first ten natural numbers is,

(1 + 2 + … + 10)² = 55² = 3025

Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is 3025 - 385 = 2640.

Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum. – PROJECT EULER #6

Taxicab numbers

2012-11-10

Yesterday had another programming puzzle by Programming Praxis. This time, we are looking for a very special sort of number, a Taxicab number. According to Wikipedia:

In mathematics, the nth taxicab number, typically denoted Ta(n) or Taxicab(n), is defined as the smallest number that can be expressed as a sum of two positive algebraic cubes in n distinct ways. – Wikipedia: Taxicab Number

Project Euler 5

2012-11-08

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20? – PROJECT EULER #5