Programming Praxis

According to their masthead, the MindCipher website is “a social repository of the world’s greatest brain teasers, logic puzzles and mental challenges.” Some of the problems lend themselves to brute force computation, others are better solved with pencil-and-paper or solely with mental effort. We look at three MindCipher exercises today.

1: Coin Flip: On Monday, you flip a coin all day. You start flipping it until you see the pattern Head, Tail, Head. You record the number of flips required to reach this pattern, and start flipping again (and counting up from 1 again) until you see that pattern again, you record the second number, and start again. At the end of the day you average all of the numbers you’ve recorded. On Tuesday you do the EXACT same thing except you flip until you see the pattern Head, Tail, Tail.

Will Monday’s number be higher than Tuesday’s, equal to Tuesday’s, or lower than Tuesday’s?

2: 1978: The year 1978 is such that the sum of the first two digits and the latter two digits is equal to the middle two digits, i.e. 19 + 78 = 97. What is the next year (after 1978) for which this is true?

3: Sum of Two Prime Numbers: If p, q > 2 are consecutive in set of primes. Since p,q can only be odd number, (p+q) is an even number.

Can (p+q)/2 be prime?

Your task is to solve the three problems given above; write a computer program to help you if you wish. 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

Today’s exercise provides three little exercises on linked lists, designed to help beginning programmers learn more about how lists work; there is also a special invitation for more experienced programmers.

1. Write a function that takes an input list and an interval n and returns a new list with all the elements of the original list, in order, except that every nth item has been removed. For instance, given the input list (1 2 3 4 5 6 7 8 9 10) and n = 4, the function should return the list (1 2 3 5 6 7 9 10).

2. Write a function that takes an input list and returns a new list with all the elements of the original list, in order, except that in the case of duplicate elements all of the duplicates except the first has been removed. For instance, all of the following lists should be transformed into the list (1 2 3 4 5): (1 2 3 4 5), (1 1 2 3 4 5), (1 2 1 3 1 4 1 5 1), and (1 2 2 3 3 3 4 4 4 4 5 5 5 5 5).

3. Write a function that takes an input list and splits the list in half; for instance, given the input list (1 2 3 4 5) the two outputs are the lists (1 2) and (3 4 5). If the list has odd length the middle element can be placed in either half, at your option, so the lists (1 2 3) and (4 5) are an alternate acceptable solution for the example problem.

Your task is to write the three indicated functions. If you find that to be too simple, write one or more exercises for your student friends. 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

A teacher wants to create several sets of pairs of her students to work together on class projects; over the several sets, each student should be paired with each other student only once. For instance, with four students, there are three sets of pairings:

{Anne, Beth}, {Chet, Dirk}
{Anne, Chet}, {Beth, Dirk}
{Anne, Dirk}, {Beth, Chet}

Your task is to write a program that, given a list of students, produces a list of all possible sets of pairings, without duplicates. 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 have today another exercise from our never-ending supply of interview questions:

Given a string, find the first character that appears only once in the string. For instance, given the string “aabbcddd”, the first character that appears only once is the “c” found at the 4th character in the string, counting from 0. Be sure that your program properly handles the case that all characters appear more than once.

Your task is to write a program that finds the first unrepeated character in a string, and its index in the string. 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

My solution to the previous exercise has a horrible performance bug. Because of its use of shuffle, the function takes time proportional to the length of the dictionary instead of the length of the passphrase. For a four-word passphrase and the 3097-word dictionary used in the solution, that’s a three-order-of-magnitude performance bug. Ouch!

Your task is to fix your solution if you got it wrong like I did. 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 his 936th xkcd comic strip, Randall Munro described what is wrong with common passwords and suggested a method of passphrase generation that is simpler to use and provides greater security. Unfortunately, I know of no popular websites that permit xkcd-style passphrases. I do still recall, however, the xkcd-style passphrase that CompuServe assigned me about twenty-five years ago (does anyone else remember upgrading from a 1200 baud modem to 9600 baud?)

Your task is to write an xkcd-style passphrase generator. 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 filled in a missing piece of the Standard Prelude in the previous exercise. In today’s exercise we fill in another missing piece, the integer root function: iroot(k, n) returns the largest integer x such that x^k does not exceed n, assuming k and n are both positive integers. For example, iroot(3, 125) equals 5, because 5³ equals 125; likewise, iroot(3, 126) equals 5, but iroot(3, 124) is 4, because 5³ is greater than 124.

Your task is to write the integer root function. 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 many programming languages, dates have a kind of “second class” relationship to data types such as integers, characters, strings and arrays; functions related to dates, such as finding the number of days between two dates, may be relegated to libraries or omitted entirely. Our Standard Prelude provides a few simple date functions, but missing is a function to neatly format a date.

Your task is to write a function that takes a date and returns a neatly-formatted string representing the input date; your function may be as simple or as elaborate as you wish. 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

One of the pleasures of writing a blog like mine is that I get to learn from my readers just as they learn from me. In a comment on the previous exercise on cyclic equality, reader Maurits pointed to Booth’s algorithm, which I had never previously heard of. Note that Booth’s algorithm is somewhat different than the one we gave in the previous exercise, since Booth’s algorithm relies on an ordering predicate between elements of the cycle while our algorithm relies only on an equality predicate.

Booth’s algorithm creates a canonical rotation of a cycle by putting it in the least possible lexicographic order out of all possible rotations. This is done by a variant of the Knuth-Morris-Pratt string search algorithm. We won’t give the algorithm here, as Wikipedia does a fine job; Booth’s original paper, referenced at Wikipedia, is behind a paywall. Here is Wikipedia’s explanation:

The algorithm uses a modified preprocessing function from the Knuth-Morris-Pratt string search algorithm. The failure function for the string is computed as normal, but the string is rotated during the computation so some indices must be computed more than once as they wrap around. Once all indices of the failure function have been successfully computed without the string rotating again, the minimal lexicographical rotation is known to be found and its starting index is returned. The correctness of the algorithm is somewhat difficult to understand, but it is easy to implement.

Your task is to implement the cyclic equality test of the prior exercise using Booth’s linear-time algorithm. 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

Two cyclic lists are equal if they have the same number of elements in the same order. For instance, the cyclic lists (1 2 3 4 5) and (3 4 5 1 2) are equal. So are the cyclic lists (1 1 2 2) and (2 1 1 2), and also the cyclic lists (1 1 1 1) and (1 1 1 1). The two cyclic lists (1 2 3 4) and (1 2 3 5) are not equal because they have different elements, and the cyclic lists (1 1 1) and (1 1 1 1) are not equal because they have different lengths.

Your task is to write a function that takes two cyclic lists and determines if they are equal. 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