Coin Change, Part 3
May 24, 2013
Our exercise today is similar to the two previous exercises on the coin change problem, but doesn’t directly involve coins. But we’ll still call it a coin change problem because I can’t think of a better name.
As in the coin change problems, we are given a target to which a set of coins is intended to sum. But instead of a list of coins, we are given a number n and assume that we have one of each denomination of coin from 1 through n. Unlike the coin change problems, we have only one of each coin, not an infinite number of them.
The problem is to figure out all the ways to combine coins to reach the desired sum. For instance, if the sum s is 10 and n is 10, the ways to combine the coins are (10), (9 1), (8 2), (7 3), (7 2 1), (6 4), (6 3 1), (5 4 1), (5 3 2), and (4 3 2 1). Note that a set like (6 2 2) is not possible because only one 2-coin is available. As in the two previous exercises, we are interested in both a function to make a list of all the solutions and a separate function that simply counts them.
Your task is to write the two programs 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.
Coin Change, Part 2
May 21, 2013
In the previous exercise we studied the classic coin change problem to find all the ways to make a given amount of change using a given set of coins. Sometimes the problem in a different way: find the minimum set of coins needed to make a given amount of change. As with the prior exercise, sometimes the task is to find just the count and sometimes the task is to find the actual set of coins.
Your task is to write the two programs 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.
Coin Change, Part 1
May 17, 2013
It is a classic problem from computer science to determine the number of ways in which coins can be combined to form a particular target; as an example, there are 31 ways to form 40 cents from an unlimited supply of pennies (1 cent), nickels (5 cents), dimes (10 cents) and quarters (25 cents), ranging from the 3-coin set (5 10 25) to the 40-coin set consisting only of pennies.
The solution is usually stated in recursive form: if c is the first coin in the set of coins cs and n is the target, the solution is the number of ways to reach the target after removing c from cs plus the number of ways to reach n − c using all the coins in cs. The algorithm to make a list of the coins, instead of the count, is the same, but keeping track of the list of coins instead of the count.
Your task is to write two functions, one to determine the count and one to determine the list of coins. 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.
Optimal Alphabetical Order
May 14, 2013
Today’s exercise comes from the book Making the Alphabet Dance: Recreational Wordplay by Ross Eckler, but I found it at http://www.math.cmu.edu/~bkell/alpha-order/:
Assume we have a list of all the words in the English language. Under the normal ordering of the alphabet in English (A, B, C, …, Z), some number of these words have all their letters in alphabetical order (for example, DEEP, FLUX, and CHIMPS). However, if we change the ordering of the alphabet, we will change the number of words having their letters in “alphabetical” order. What arrangement of the letters of the alphabet maximizes this number?
Your task is to write a program to find such an arrangement. 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.
MindCipher
May 10, 2013
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.
Three List Exercises
May 7, 2013
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.
Pairing Students
May 3, 2013
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.
First Unrepeated Character In A String
April 30, 2013
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.
Correct Horse Battery Staple, Improved
April 26, 2013
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.
Correct Horse Battery Staple
April 23, 2013
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.
Programming Praxis 