In a surprise move, N. Crocosia agreed to halt its nuclear program in return for 20 million iPods. According to the terms of the agreement, all iPods should come read-only, prerecorded with the same 10 tracks, 1 hour long each. The first half of each track is a speech by the country's leader followed by music in the second half without any pauses.

The Ministry of Songs provided 24 songs for the musical part, all with different durations in whole minutes. In addition, they requested that two of the leader's favorite songs, 10 and 12 min long, be together, as well as two others, respectively 4 and 13 min long.

Can these conditions be met?

There are 300 minutes to fill, which is also the sum of the first 24 whole numbers, so all the first 24 whole numbers are used. The 10 and 12 can be treated together as a second 22, and the 4 and the 13 together as a second 17.  The following program tries all possibilities but finds none.

DECLARE SUB fill (n!)

CLEAR , , 9999

OPEN "tuffnego.txt" FOR OUTPUT AS #2

DIM SHARED avail(24)
DIM SHARED track(10, 10), tot(10)
FOR i = 1 TO 24
 avail(i) = 1
NEXT
avail(4) = 0
avail(10) = 0
avail(12) = 0
avail(13) = 0
avail(22) = 2
avail(17) = 2

fill 1

CLOSE

SUB fill (n)
 r = 30 - tot(n)
 IF r > UBOUND(avail, 1) THEN l = UBOUND(avail, 1): ELSE l = r
 FOR i = track(n, track(n, 0)) TO l
   IF avail(i) THEN
     avail(i) = avail(i) - 1
     track(n, 0) = track(n, 0) + 1
     tot(n) = tot(n) + i
     track(n, track(n, 0)) = i
    
     IF n = 1 AND i = r THEN
      FOR j = 1 TO track(n, 0)
       PRINT #2, track(n, j);
      NEXT
      PRINT #2,
     END IF
     IF i = r THEN
       IF n = 10 THEN
         FOR j = 1 TO 10
           FOR k = 1 TO track(i, 0)
             PRINT track(i, k);
           NEXT
           PRINT
         NEXT
         PRINT
       ELSE
         fill n + 1
       END IF
     ELSE
         fill n
     END IF
   
     tot(n) = tot(n) - i
     track(n, 0) = track(n, 0) - 1
     avail(i) = avail(i) + 1
   END IF
 NEXT
END SUB

found no instances where all the 30-minute slots could be filled.

As a check on the program's thoroughness, the file produced shows all the possibilities gone through for the first track:

 1  2  3  5  8  11
 1  2  3  5  19
 1  2  3  6  7  11
 1  2  3  6  18
 1  2  3  7  8  9
 1  2  3  7  17
 1  2  3  8  16
 1  2  3  9  15
 1  2  3  24
 1  2  5  6  7  9
 1  2  5  6  16
 1  2  5  7  15
 1  2  5  8  14
 1  2  5  22
 1  2  6  7  14
 1  2  6  21
 1  2  7  9  11
 1  2  7  20
 1  2  8  19
 1  2  9  18
 1  2  11  16
 1  3  5  6  7  8
 1  3  5  6  15
 1  3  5  7  14
 1  3  5  21
 1  3  6  9  11
 1  3  6  20
 1  3  7  8  11
 1  3  7  19
 1  3  8  18
 1  3  9  17
 1  3  11  15
 1  5  6  7  11
 1  5  6  18
 1  5  7  8  9
 1  5  7  17
 1  5  8  16
 1  5  9  15
 1  5  24
 1  6  7  16
 1  6  8  15
 1  6  9  14
 1  6  23
 1  7  8  14
 1  7  22
 1  8  21
 1  9  20
 1  11  18
 1  14  15
 2  3  5  6  14
 2  3  5  9  11
 2  3  5  20
 2  3  6  8  11
 2  3  6  19
 2  3  7  18
 2  3  8  17
 2  3  9  16
 2  3  11  14
 2  5  6  8  9
 2  5  6  17
 2  5  7  16
 2  5  8  15
 2  5  9  14
 2  5  23
 2  6  7  15
 2  6  8  14
 2  6  22
 2  7  21
 2  8  9  11
 2  8  20
 2  9  19
 2  11  17
 3  5  6  7  9
 3  5  6  16
 3  5  7  15
 3  5  8  14
 3  5  22
 3  6  7  14
 3  6  21
 3  7  9  11
 3  7  20
 3  8  19
 3  9  18
 3  11  16
 5  6  8  11
 5  6  19
 5  7  18
 5  8  17
 5  9  16
 5  11  14
 6  7  8  9
 6  7  17
 6  8  16
 6  9  15
 6  24
 7  8  15
 7  9  14
 7  23
 8  22
 9  21
 11  19
 14  16

The recursion to n+1 similarly goes through all the possibilities for the remaining tracks, using the remaining song lengths for each possibility of track 1.

I realize I could have stopped the program when the first track passed having used the 1-minute song, as it could have been assumed that the first track would have the 1-minute song without loss of generality.

Posted by Charlie on 2007-02-27 10:52:17