## Three More Homework Problems

### September 22, 2015

I can tell from my statistics that people like the homework problem exercises, I suppose because they are short and provide simple drill. I can also tell, from reading some of the beginning-programmer message boards, that students seem to be quicker that they used to be to post their homework problems on-line rather than figuring out the solutions themselves, either because they are lazy or because their teachers aren’t providing sufficient help. So today we have three more homework problems:

1) Given a list of integers, return a list in which all the duplicates have been removed. For instance, given the input list [3, 2, 4, 2, 7, 3, 5, 1, 3] return the output list [3, 2, 4, 7, 5, 1].

2) Given two lists of integers, each sorted in ascending order, return a list of the integers common to the two lists; the output list must also be in ascending order. For instance, give the input lists [2, 3, 5, 5, 6, 7, 8, 9] and [1, 2, 4, 5, 5, 7] return the output list [2, 5, 5, 7].

3) Given a positive integer, determine if it is a perfect cube. For instance, the integer 125 is a perfect cube, 5*5*5, but the integer 121 is not.

Your task is to write programs that solve the three homework problems. 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

## Three Homework Problems

### September 18, 2015

We have three simple exercises today to help beginning programmers with their homework; all three exercises have appeared on beginning-programmer forums in the last week:

1) Write a recursive function to find the sum of the first n odd integers. For instance, if n = 2, the first two odd integers are 1 and 3, and their sum is 4.

2) Write a function to count the frequence of characters in a string. For instance, given the string “hello” the function should return counts of 1, 1, 2 and 1 for h, e, l and o.

3) Write functions that encrypt and decrypt messages in a Caesar cipher. Input consists of upper-case letters and spaces; the “key” is an integer giving the number of letters to shift. For instance, the message ATTACK AT DAWN with a shift of 5 is enciphered as FYYFHP FY IFBS.

Your task is to solve the three homework exercises 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

## Time Arithmetic

### September 15, 2015

The Standard Prelude provides functions `julian` and `gregorian` for performing date arithmetic. In today’s exercise we will extend those functions to provide arithmetic on times as well. The parameters provided to `julian` will be year, month, day, hour, minute, and second, and the same parameters will be returned by `gregorian`.

Your task is to write the new `julian` and `gregorian` functions. 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

## Finding The Median

### September 11, 2015

The median of an array is the value in the middle if the array was sorted; if the array has an odd number of items n, the median is the (n+1)/2’th largest item in the array (which is also the (n+1)/2’th smallest item in the array), and if the array has an even number of items n, the median is the arithmetic average of the n/2’th smallest item in the array and the n/2’th largest item in the array. For instance, the median of the array [2,4,5,7,3,6,1] is 4 and the median of the array [5,2,1,6,3,4] is 3.5.

Your task is to write a program that takes an array of 8-bit integers (possibly but not necessarily in sort) and finds the median value in the array; you should find an algorithm that takes linear time and constant space. 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

## Fermat’s Divisors Challenges

### September 8, 2015

Pierre de Fermat issued these two challenges in 1657: First, find a cube that, when increased by the sum of its aliquot divisors, becomes a square; for instance, 73 + (1 + 7 + 72) = 203. Second, find a square that, when increased by the sum of its aliquot divisors, becomes a cube. I would guess that Fermat knew the answer to the first challenge but not the second.

In the days before computers, challenges such as this were frequently issued by one mathematician or group of mathematicians to their competing colleagues; for instance, the French mathematicians might challenge the German mathematicians. Once the challenge was met, the solving group would issue a new challenge to the original challengers. It was considered un-gentlemanly to issue a challenge to which you did not have a solution, though Fermat was probably respected enough to get away with it. Times have changed.

Your task is to write programs that find solutions to the two challenges. 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

## Reversing Digits

### September 4, 2015

After Tuesday’s exercise on Lychrel numbers, I answered a question about Lychrel numbers over at Stack Overflow, using a recursive function to extract and reverse the digits one-by-one. I was challenged by a reader who claimed “using `int("".join(reversed(str(n))))` has got to be far more efficient than using your recursive function. Your function is clever, but clever isn’t always best.” He was wrong, of course: arithmetic on numbers is better than converting a number to a string, creating a generator to reverse the individual characters of the string, appending them one-by-one to a new string, and converting the new string back to a number, which I demonstrated to him in a timing experiment.

Your task is to find the best way to reverse the digits of a positive integer, in the language of your choice. 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

## Lychrel Numbers

### September 1, 2015

Let `r`(n) be the function that reverses the digits of the number n, and let `s`(n) = n + `r`(n); for instance, `r`(281) = 182 and `s`(281) = 281 + 182 = 463. Repeatedly applying `s` to the result of `s`(n) frequently leads to a palindrome; for instance, starting with n = 281, `s`(281) = 463, `s`(463) = 827, `s`(827) = 1555, `s`(1555) = 7106, `s`(7106) = 13123, and `s`(13123) = 45254, which is a palindrome. There are some numbers, such as 196, that apparently don’t lead to palindromes; these numbers are called Lychrel numbers (A023108), and we say apparently because no one knows if there might be a palindrome if the computation is continued sufficiently far. It is conjectured that there are an infinite number of Lychrel numbers.

Your task is to write a function that determines if a number appears to be a Lychrel number and, if not, returns the chain of numbers that shows it is not. 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

## Maximum Product Of Two Primes Less Than N

### August 28, 2015

Today we have a fun little exercise based on prime numbers.

Given an integer n > 4, find the maximum product of two prime numbers such that the product is less than n. For instance, when n = 27, the maximum is 2 * 13 = 26, and when n = 50, the maximum is 7 * 7 = 49.

Your task is to write a program to find the maximum product of two primes less than n. 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

## Collect Sets Of Ranges

### August 25, 2015

A frequent idiom in data processing is the control-break idiom, where some processing must be done every time there is a change in some value. A simple example comes from collecting ranges, for instance, converting the sequence 0, 1, 2, 7, 21, 22, 108, 109 to the ranges 0-2, 7, 21-22, 108-109, where a break occurs whenever two numbers aren’t consecutive.

Writing control-break programs can be difficult, for two reasons. First, you don’t know there is a break until you see the next record after the break, so you either need to look ahead in the input or keep track of what you have seen. Second, there is an implied break at the end of the input, which occurs when there is no record at all. Depending on the situation, either or both of those can be tricky.

Your task is to write a program that converts a sequence to a set of ranges, as shown 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

## Two Homework Problems

### August 21, 2015

I can see from my statistics that the new academic year is beginning. Again, as in a previous exercise, in the spirit of helping programming students who are just starting a new school year, we have two typical homework problems:

1. Given an array of positive integers, find the inflection point where the total of the integers before the inflection point and the total of the integers after the inflection point are least different. For instance, given the array [3, 7, 9, 8, 2, 5, 6], the inflection point is between the 9 and 8, which leaves a total of 19 before the inflection point and 21 after, a difference of 2.

2. Write a program that reads a file from disk and writes the last n lines of the file, where n is an input parameter.

Your task is to write programs to solve these problems. 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