Busy Beaver

June 24, 2014

Yesterday was Alan Turing’s birthday, so today we will write a program for a turing machine.

The Busy Beaver is a turing machine that performs the maximum work for a given configuration of machine; the concept was invented by Tibor Radó in his 1962 paper On Non-Computable Functions. We won’t look at the underlying theory, although it is fascinating if you have the time. Instead, we’ll be content to implement the first few busy beavers. Here are the two-symbol busy beavers for one, two, three and four states, from Wikipedia; the two symbols are 0 and 1, the states are letters A through D plus the halting state H, and the moves L and R are left and right:

  A
0 1RH
1 unused
  A B
0 1RB 1LA
1 1LB 1RH
  A B C
0 1RB 0RC 1LC
1 1RH 1RB 1LA
  A B C D
0 1RB 1LA 1RH 1RD
1 1LB 0RC 1LD 0RA

Your task is to implement the four busy beavers. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

Birthday Paradox

June 20, 2014

The birthday paradox, which we studied in a previous exercise, states that in any group of 23 people there is a 50% chance that two of them share a birthday. The BBC recently published an article that shows 16 of the 32 World Cup teams, each consisting of 23 players, have shared birthdays, thus demonstrating the paradox precisely. Today’s exercise asks you to recreate their calculation.

You can obtain the same listing of player birthdays that the BBC used from FIFA. Another source is the player rosters at WikiPedia.

Your task is to demonstrate that the 2014 World Cup rosters honor the birthday paradox. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

Collinearity

June 17, 2014

Beware: today’s exercise sounds simple but is actually quite complex if you don’t look at it properly.

Your task is to write a function that takes three points in the x,y plane and determines if they are collinear; be sure to handle vertical lines and horizontal lines properly. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

Over at /r/math, Darksteve writes of “A problem I came up with, and haven’t been able to solve for many years:”

I would like to present a mathematical problem that I came up with some years ago, and haven’t yet found a solution for:

If you take all the numbers that contain the digits 1 to 9 exactly once, and you write down the prime factorization of all those numbers, which one has the smallest biggest prime factor?

To illustrate what I mean, the number 879456123 contains the prime factors 3 7 13 and 491; making 491 this numbers biggest prime factor.

The number 213456789 contains 3 7 13 and 197 as factors, making 197 the biggest prime factor. Out of all the numbers I’ve tried, 213456789 has the smallest biggest prime factor.

Many other number have much bigger biggest prime factors, like 576492813 which contains 3 13 19 and 13649.

But I have not found a way to actually solve this problem, as I am lacking the programming skills, or the algebraic knowledge required. I would therefore greatly appreciate anyone capable of solving this.

Your task is to solve Darksteve’s problem. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

Balanced Delimiters

June 10, 2014

I heard today’s exercise as an interview question — you have five minutes to solve this task, while I watch — but it could equally be a homework problem:

Write a function to return true/false after looking at a string. Examples of strings that pass:

{}, [], (), a(b)c, abc[d], a(b)c{d[e]}

Examples of strings that don’t pass:

{], (], a(b]c, abc[d}, a(b)c{d[e}]

Your task is to write the function described above. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below:

Pages: 1 2

Remove Singleton

June 6, 2014

I’m not sure if this is a homework exercise or an interview questions, but it’s a fun little exercise to get your creative juices flowing on a Friday morning:

Given a string and a character, remove from the string all single occurrences of the character, while retaining all multiple consecutive instances of the character. For instance, given string “XabXXcdX”, removing singleton Xs leaves the string “abXXcd”.

Your task is to write the program given above; be sure to properly test your work. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

We studied the problem of converting between integers and roman numerals in a previous exercise. We’ll do it again today because it’s a fun exercise, it appears frequently in lists of interview questions, we have an improved algorithm, and it lets us highlight a useful piece of the Standard Prelude.

Your task is to write functions that convert an integer to its equivalent in roman numerals and vice versa. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

In the previous exercise we implemented the subset sum algorithms of CLRS 35.5. In today’s exercise we solve exercise 35.5-5, which asks us to return the subsets as well as their sums. The algorithm is exactly the same. The difference is that set members are stored along with their partial sums.

Your task is to write a program that solves the subset sum problem as described above. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

We studied the subset sum problem — find the subset of a set of integers that sum to a given target — in two previous exercises; in both cases, we produced an exact answer, but took exponential time to do so. In today’s exercise, we will study a variant of the subset sum problem — find the subset of a set of integers that have the largest sum not exceeding a given target — that admits both exact and approximate answers; the exact answer runs in exponential time, though it is typically quite fast, but the approximate answer runs in linear time in the number of integers in the input set. Our solution is given by CLRS 35.5.

The exact solution uses two auxiliary functions. The function denoted by L + x adds x to each element of a list L. The function merge-lists takes two sorted input lists and returns the merge of the two lists with duplicates removed. Then CLRS gives the algorithm as follows, where S is a sorted list of integers and t is the target:

EXACT-SUBSET-SUM(S,t)
1  n = |S|
2  L0 = ‹0›
3  for i = 1 to n
4      Li = MERGE-LISTS(Li−1, Li−1 + x)
5      remove from Li every element that is greater than t
6  return the largest element in Ln

The approximation algorithm adds a trimming step to the exact algorithm. The trimming step removes from the accumulating L list partial sums that are within a factor of 0 < δ < 1 such that any partial sum that is less than 1 + δ times its predecessor is removed. For instance, given L = ‹10, 11, 12, 15, 20, 21, 22, 23, 24, 29› and δ = 0.1, the trimmed L‘ = ‹10, 12, 15, 20, 23, 24›, where 11 is removed because it is within 10% of 10 and 21 and 22 are removed because they are within 10% of 20; trim assumes that L = ‹y1, y2,… ym› is sorted:

TRIM(L,δ)
1  let m be the length of L
2  L‘ = ‹y1
3  last = y1
4  for i = 2 2 m
5      if yi > last · (1 + δ) // yilast because L is sorted
6           append yi onto the end of L
7          last = yi
8  return L

Then the approx-subset-sum algorithm is the same as the exact-subset-sum algorithm except that step Li = TRIM(Li, ε/2n) is inserted between steps 4 and 5, where the solution is within 0 < ε < 1 percent of the desired target.

Your task is to implement the two algorithms given above. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

Aliquot Sequences

May 23, 2014

We studied amicable chains in the previous exercise. Today we look at aliquot sequences, which are closely related to amicable chains. The aliquot sequence of n is the sequence that starts with n as its zero’th element and s(k−1) as its k‘th element, where s is the sum-of-divisors function of the previous exercise. For instance, the aliquot sequence of 10 is 10, 8, 7, 1, 0 because s(10) = 1 + 2 + 5 = 8, s(8) = 1 + 2 + 4 = 7, s(7) = 1, and s(1) = 0.

In 1888 Eugène Charles Catalan conjectured that all aliquot sequences end either at a prime number (the aliquot sequence for 10 shown above is usually considered to end at the prime 7, since once a member of an aliquot sequence is prime, the next two steps are 1 and 0) or at an amicable chain (either a perfect number which is an amicable chain of length 1, or an amicable pair which is an amicable chain of length 2, or a longer amicable chain). For instance, the aliquot sequence for 95 is 95, 25, 6, 6, …, where 6 is a perfect number. All numbers for which the entire aliquot sequence has been determined fit the conjecture, but there are many numbers for which the entire aliquot sequence is not known, of which the smallest is 276.

Your task is to write a function that computes aliquot sequences; it should return either the prime number or the amicable chain (smallest number first) that terminates the sequence. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2 3

Follow

Get every new post delivered to your Inbox.

Join 628 other followers