Counting Zeros

January 7, 2014

I’m not sure of the original source of today’s exercise; it feels like a Project Euler exercise — it’s mathy, it admits a simple but slow brute-force solution, and it also has a smart, fast solution — but I can’t find it there.

For a given n, count the total number of zeros in the decimal representation of the positive integers less than or equal to n. For instance, there are 11 zeros in the decimal representations of the numbers less than or equal to 100, in the numbers 10, 20, 30, 40, 50, 60, 70, 80, 90, and twice in the number 100. Expect n to be as large as 1010,000.

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

O Tannenbaum

December 24, 2013

Merry Christmas to all my readers.

Your task today is to write a program that draws a Christmas tree on the screen; it can be as simple or 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

Requiescat In Pace

December 20, 2013

My mother died on Tuesday, December 17th, aged eighty-eight years, after a brief illness.

Requiem aeternam dona ei, Domine, et lux perpetua luceat ei.

I’ll be taking a short break from writing exercises. The Christmas exercise for next Tuesday is already written and loaded and will appear on schedule. Then I’ll be back to the normal Tuesday/Friday schedule after the first of the year.

Remove Duplicates From A List

December 17, 2013

We have today another exercise from our infinite supply of interview questions:

Return a list containing only one copy of any duplicates in an input list, with items in the output in the same order as their first appearance in the input.

Your task is to answer the interview question given above; you must provide at least two different solutions. 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

Modular Factorial

December 13, 2013

This question appears from time to time as an interview question or on the coding-challenge web sites.

Write a function that calculates n! (mod p) when p is prime. Then extend the function to calculate n! (mod m) when m is not prime. Can you calculate the factorials using fewer than n−1 modular multiplications?

For instance, 1000000! (mod 1001001779) is 744950559.

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

Rock Paper Scissors

December 10, 2013

Today’s exercise is our five hundredth! It’s hard to believe. I remember writing the fiftieth exercise and thinking I would never get to a hundred. Even after all this practice it is hard to write two exercises every week, but your comments and private emails and referrals from other web sites sustain me. Many thanks to all my readers.

Our tradition for these milestone exercises is to have a party, which means we need a game: so we write one. Today’s exercise is to write an interactive rock-paper-scissors game: rock blunts scissors, paper wraps rock, scissors cut paper.

Your task is to write a program to play rock-paper-scissors with a human player, keeping score as you go. 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

Left-Handed Words

December 6, 2013

On a standard English keyboard, the letters that a touch-typist strikes with the fingers of the left hand are Q, W, E, R, T on the top row, A, S, D, F, G on the home row, and Z, X, C, V, B on the bottom row. For instance, words like FAST and ZEBRAS are left-handed words; PACKAGE and SOUTH are not.

Your task is to write a program that finds words that can be spelled using only letters that are struck with the fingers of the left hand; perhaps you are writing an exercise for a typing book. 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

Reversing Parts Of A List

December 3, 2013

This exercise is intended for beginning programmers who need to strengthen their understanding of linked lists. It comes in three parts:

First, write a function that reverses the elements of a linked list pairwise; for instance, given the list (1 2 3 4 5 6) the pairwise reversal is (2 1 4 3 6 5). If the list has an odd number of elements, keep the last element at the end of the list; for instance, given the list (1 2 3 4 5) the pairwise reversal is (2 1 4 3 5).

Second, write a function the reverses the elements of a linked list k-wise; for instance, given the list (1 2 3 4 5 6) the 3-wise reversal is (3 2 1 6 5 4) and the 4-wise reversal is (4 3 2 1 6 5).

Third, write a function that reverses the elements of a linked list by halves; for instance, given the list (1 2 3 4 5 6) the half-wise reversal is (3 2 1 6 5 4), with each half reversed independently. If the list has an odd number of elements, the middle element may be assigned to either half at the discretion of the programmer.

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

I Before E

November 29, 2013

School children learning to spell English words are taught a series of rules. One of them is:

I before E except after C, or when sounded as AY as in NEIGHBOR and WEIGH.

Your task is to write a program that finds exceptions to that rule; you may want to look at the pronouncing dictionary at http://svn.code.sf.net/p/cmusphinx/code/trunk/cmudict/cmudict.0.6d. 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

And The Winner Is …

November 26, 2013

In many voting systems, when there are more than two candidates and the rules require a majority of the votes to win, if no candidate receives a majority a runoff election is held between the two candidates who finished with the two highest vote totals. Some voting systems, instead of asking each voter to vote for a single candidate, instead ask voters to rank the candidates, which permits a runoff to be held instantly as follows: the votes are tallied, and a winner is declared if one of the candidates receives more than half the votes; otherwise, the candidate with the fewest votes is removed from all ballots and the votes are tallied again, the process repeating until some candidate has more than half the votes. This process is used in some political elections, and is often used in voting for awards such as the Hugo awards for science fiction writing and the Oscars for motion pictures.

Your task is to write a program that determines a winner in an instant-runoff voting system. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercises in the comments below.

Pages: 1 2

Follow

Get every new post delivered to your Inbox.

Join 574 other followers