Trial Division

October 25, 2016

It was a gorgeous autumn weekend: brisk mornings, warm sunny afternoons, and absolutely no reason to sit at a computer screen indoors. And even though the programming on my big project at work is finished, there are still details to be looked after, so I had no time there, either. Thus, another recycled exercise today, another one that I’ve seen on the beginning-programmer message boards recently:

Write a program that determines the prime factors of a number n.

You should write at the level of a first-year programmer, nothing sophisticated. An appropriate algorithm is trial division.

Your task is to write a program to factor integers. 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

Checking Primality

October 21, 2016

[ I haven’t had time to prepare a new exercise because I’ve been busy finishing up a big project at work. So the bad news is we have a repeat exercise, but the good news is that my project is done! ]

We have today an exercise that has appeared on message boards at least a dozen times in the last few weeks; it must be that time in the semester when beginning programming students are working on their mid-term homework assignments.

Write a program that, given an integer, determines whether or not it is prime.

Your task is to write a program that determines if a given integer is prime, in the style of a beginning programmer who is less than confident of his knowledge of variable assignment and loops; do not use a complicated algorithm. When you are finished, you are welcome to read a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

Today’s exercise is an interview question from Amazon:

You are to write a program that reads a stream of characters from the input and returns a random character from the stream. Any character should have an equal probability of being returned. You may only use a single character of storage space; in particular, you may not save multiple characters from the input stream.

Your task is to write a program that solves the Amazon interview task. 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 three more list-manipulation exercises today, for those students midway through their beginning programming course who need practice with linked lists:

  1. Define a function that takes two lists, the second of which is a list of non-negative integers the same length as the first list, and returns a list of elements from the first list, in reverse order, each repeated a number of times as specified by the corresponding element of the second list.
  2. Rearrange the integers in a list so that all the odd numbers appear before all the even numbers, with both odd and even numbers in the same relative order in the output as they were in the input.
  3. Write a function that returns the nth item from the end of a list.

Your task is to write the three specified programs. 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 must be approaching the middle of the autumn academic term, because the beginning-programmer message boards are starting to fill up with linked-list exercises; one enterprising fellow even sent me an email asking for help on his homework. Here are three tasks that involve manipulating linked lists. We’ve probably done all three before, and they’re simple enough for many of the people that read and respond here, but learners seem to have trouble with them, so we’ll discuss them here:

  1. Write a function that takes a linked list of integers and returns a new linked list with all the odd integers removed.
  2. Write a function that removes every nth item from a linked list.
  3. Write a function that reverses the two halves of a list; if the number of items in the list is odd, the middle element should go with the second half of the list

Your task is to write the three functions 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

Sticks

October 7, 2016

We continue our occasional series of textbook exercises:

You are given a bunch of sticks, each of integer length. Two sticks can be combined into a single, larger stick by a process that costs the sum of the lengths of the two sticks. Your goal is to build a single stick combining all the original sticks, at minimal cost.

For example, suppose you initially have three sticks of lengths 1, 2, and 4. You could combine sticks 2 and 4 at a cost of 6, then combine that stick with stick 1 at a cost of 7, for a total cost of 13. But it is better to first combine sticks 1 and 2 at a cost of 3, then combine that stick with stick 4 at a cost of 7, for a total cost of 10.

Your task is to write a program that combines a bunch of sticks at minimal cost. 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

I’m Embarrassed!

October 4, 2016

Matthew Arcus pointed out a bug in my solution to the previous problem:

> (dollar 1234567.9999)
$1,234,567.100

I can’t remember a similarly bad bug in any previous Programming Praxis problem.

You get the day off today. There is no exercise for you to do. You are welcome to read or run my corrected solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

Dollar Format

September 30, 2016

We have a simple task today, a function that formats a number in dollar format. A number like 1234567.8912 should be rounded to two positions after the decimal point, have commas inserted every three positions before the decimal point, and have a dollar sign prepended; thus, the function should format 1234567.8912 as $1,234,567.89.

Your task is to write a function that returns numbers in dollar format; if your language provides such a facility natively, you are not permitted to use it. 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 Three

September 27, 2016

Today’s exercise comes from the end-of-chapter exercises in the sorting chapter of a programming textbook:

Write a program that finds the maximum product of three numbers in a given array of integers.

Your task is to write the desired program. 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

Water Jugs Puzzle

September 23, 2016

There are various puzzles in which water is poured from one jug to another to reach a desired amount of water. In the version we consider today, we have two jugs, an unlimited amount of water to fill them, and a drain into which we can pour an unlimited amount of water. The two jugs have known capacities, but it is not possible to accurately measure portions of a jug.

As an example, we wish to obtain four gallons of water, using jugs of capacities three and five gallons. Starting with two empty jugs, it is possible to obtain four gallons of water using the following six steps:

  1. Fill the five-gallon jug.
  2. Pour three gallons from the five-gallon jug to the three-gallon jug, leaving two gallons in the five-gallon jug.
  3. Empty the three-gallon jug.
  4. Pour two gallons from the five-gallon jug to the three-gallon jug, leaving the five-gallon jug empty and two gallons in the three-gallon jug.
  5. Fill the five-gallon jug.
  6. Pour one gallon from the five-gallon jug into the three-gallon jug, filling it, leaving the desired four gallons in the five-gallon jug.

Bruce Willis figured that out once; so too do thousands of school children every year.

Your task is to write a program that solves this kind of water-jug problem using the minimum number of steps (filling a jug, emptying a jug, or pouring one jug into the other). 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