Programming Praxis

Today’s exercise comes from our file of interview questions:

Given a list, return the first half of the list as one list and the second half of the list as a second list. For instance, given the input list {1 2 3 4}, output the two lists {1 2} and {3 4}. If the input list has an odd number of items, the middle item can go to either list, so that the input list {1 2 3 4 5} can result in the output lists {1 2} and {3 4 5} or the output lists {1 2 3} and {4 5}.

Your task is to write the function that splits a list in two halves. 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 a tradition here at Programming Praxis of celebrating milestones by having a party, and parties require games. Today, for our three-hundredth exercise we will write a cheating version of the hangman from a previous exercise.

The idea is simple. Instead of choosing a single answer at the beginning of the game, choose a length, and make a list of all possible answers. Each time the player guesses a letter, delete as few words from the possible-answer list as possible consistent with the guesses the player has made; most of the time another body part will be added to the gibbet.

Your task is to write a referee for the game of cheating hangman. 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

It’s Christmas time, and that means winter, and that means snow (sometimes, but probably not this year), so today’s exercise is to draw Koch’s Snowflake. This famous fractal is built from an equilateral triangle, as shown upper left. At each step each side is modified by removing its center third and replacing it with two legs of another equilateral triangle. Thus, at upper right, each of the three legs has been replaced four line segments that form a new shape. Carrying on, the fractal becomes more and more detailed at the edges of the triangle; eventually, the perimeter of the triangle is infinite, though its area is 8/5 the area of the original triangle. Mathematically, the Koch Snowflake can be encoded as a Lindenmayer system with initial string F++F++F, rewriting rule F → F-F++F-F, and angle 60 degrees (in the Lindenmayer notation, F means move forward, + is a right turn and - is a left turn).

Your task is to write a program to draw the Koch Snowflake. 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 today’s exercise we implement the classic Unix V7 game hangman for guessing words. The player is given a series of blanks, one per letter of a word to be guessed. At each turn the player guesses a letter; if it is in the word, all occurrences of the letter are filled in the appropriate blank, but if the guess is wrong, another body part — traditionally, the head, torso, two arms and two legs, for a total of six — is added to the gibbet. The player wins by guessing all the letters of the word before the hangman adds all the pieces of his body.

Your task is to implement the interactive game of hangman. 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 an election, the winner is required to have the majority of the votes. For instance, with the set of votes {A A A C C B B C C C B C C}, the winner is C with 7 of 13 votes. Some elections have no winner; with the set of votes {A B C A B C A}, A gets a plurality of the votes but not a majority, so there is no winner. You can think of voting as a political election, or as redundant hardware in a critical system where a failure of one component must not lead to failure of the overall system.

Your task is to write a function that determines the winner of a vote, or indicates that no candidate reached a majority. 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

When I was a kid, telephones had rotary dials, not push buttons, and exchanges had names; my grandmother was in the Underhill 8 exchange. If you were calling someone in the same exchange as you were, you only had to dial the last four digits of the number. Long distance calling generally involved a human operator.

Modern American telephone numbers have ten digits, segmented as a three-digit area code, a three-digit exchange code, and a four-digit number. Within an area code, you need only dial (the verb hasn’t changed, even though telephones no longer have a dial) the seven-digit exchange code and number; otherwise, you must dial the complete ten-digit number, often with a prefix.

Our exercise today asks you to validate a telephone number, as if written on an input form. Telephone numbers can be written as ten digits, or with dashes, spaces, or dots between the three segments, or with the area code parenthesized; both the area code and any white space between segments are optional. Thus, all of the following are valid telephone numbers: 1234567890, 123-456-7890, 123.456.7890, (123)456-7890, (123) 456-7890 (note the white space following the area code), and 456-7890. The following are not valid telephone numbers: 123-45-6789, 123:4567890, and 123/456-7890.

Your task is to write a phone number validator that follows the rules given above; your function should either return a valid telephone number or an indication that the input is invalid. Be sure to write a proper test suite. 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

At McDonalds’ Restaurants, the Chicken McNugget meals are available in sizes of 6 McNuggets, 9 McNuggets, or 20 McNuggets. A number is a McNugget number if it can be the sum of the number of McNuggets purchased in an order (before eating any of them). Henri Picciotto devised the math of McNugget numbers in the 1980s while dining with his son at McDonald’s, working the problem out on a napkin.

Your task is to determine all numbers that are not McNugget numbers. 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 1653 Blaise Pascal published his treatise Traité du triangle arithmétique describing his triangle computing the binomial coefficients, which are used in the study of probability; Pascal gets credit for the name even though both the coefficients and their arrangement in a triangle were known before him.

To compute the triangle, start with a row containing only 1. Then each succeeding row is built by adding the two numbers triangularly above the current number, assuming a temporary 0 at each end of the prior row.

Your task is to write a program to neatly display Pascal’s Triangle. 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 classic problem in computing is the Knight’s Tour, in which a knight visits every square on a chessboard; the objective is to list the knight’s moves in order. There are two types of tours: cyclic (or closed), in which the final square is a knight’s jump away from the starting square, and acyclic (or open), where the final square is unconstrained. Knight’s tours are often given for generalized chessboards, such as 5-by-5 or 10-by-12, in addition to the standard 8-by-8 chessboard.

The simple solution is via backtracking: Make any valid move. Then make another move. And so on, until you have completed the tour. If at any point there are no valid moves, backtrack and choose an alternate move. The diagram below shows a sample 8-by-8 cyclic tour, and the list below the board shows the list of squares using row and column coordinates in the order they are visited:

01 16 51 34 03 18 21 36
50 33 02 17 52 35 04 19
15 64 49 56 45 20 37 22
32 55 44 63 48 53 42 05
61 14 57 54 43 46 23 38
28 31 62 47 58 41 06 09
13 60 29 26 11 08 39 24
30 27 12 59 40 25 10 07

0/0 1/2 0/4 1/6 3/7 5/6 7/7 6/5
5/7 7/6 6/4 7/2 6/0 4/1 2/0 0/1
1/3 0/5 1/7 2/5 0/6 2/7 4/6 6/7
7/5 6/3 7/1 5/0 6/2 7/0 5/1 3/0
1/1 0/3 1/5 0/7 2/6 4/7 6/6 7/4
5/5 3/6 4/4 3/2 2/4 4/5 5/3 3/4
2/2 1/0 0/2 1/4 3/5 4/3 3/1 2/3
4/2 5/4 7/3 6/1 4/0 5/2 3/3 2/1

Since the number of possible tours is very large, the simple solution will likely take a long time. In 1823, H. C. von Warnsdorff proposed the following heuristic: sort the valid moves according to the number of their successor moves, choosing first the move that has the least number of successors (choose randomly in the event of a tie). On small chessboards, say less than 10-by-10, Warnsdorff’s heuristic frequently eliminates backtracking entirely.

Your task is to write a program that finds a single Knight’s Tour on an n-by-n chessboard. 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