You've been hired by a company that creates hymn boards - a plaque that goes on the wall of a church showing which songs are to be sung during a church service:
Your task is to create an algorithm to determine the minimum number of each digit card (the little cards with a single digit, 0-9, on them) to include with each hymn board. You are given the number of songs in the songbook, and the maximum number of songs that can be sung during a service. A song is never repeated during a service.
For example, if there are 10 songs in the book, and two songs can be sung during a service, then you need exactly two 1s, and one of everything else (two 1s in case the two songs are 1 and 10). That one is easy enough to do by hand, but most books will have a few hundred songs, and at least three songs are sung at most services. Your algorithm should be universal.
Here's your skeleton code:
-
type THymnBoard = record
-
N0, N1, N2, N3, N4, N5, N6, N7, N8, N9: Integer;
-
end;
-
-
function GetDigitCounts(SongsInBook, SongsInService: Integer): THymnBoard;
-
begin
-
//You fill in here
-
end;
3 Comments
Ok, this must be the weirdest code I’ve ever written… For Each “Song” number I calculate the digits needed to display it and store all the results in an array.
Next, I loop through the array and locate the maximum for each digit, and repeat this process SongsInService times. I add up the count and display the result.
Check out the code here: http://users.otenet.gr/~zkeramid/misc/HymnBoard.dpr
Should there be any consideration of 6’s and 9’s? They’re really the same card.
For example, if SongsInService is 2 and SongsInBook is 100, a naive algorithm would determine that you need three 6’s and three 9’s in case a service called for songs 16 and 66 or 90 and 99. But you’d be including two more cards than you needed with the board because any 6 card can be turned upside-down to be used as a 9. Instead of six cards, just include four — the worst case is when a service calls for songs 66 and 99.
Rob: Excellent question about 6’s and 9’s. Based on the picture included with the puzzle, I’d say they’re interchangeable :). Good thinking.
Post a Comment