Practice Problem 1 - List Compression

Loyola College > Department of Computer Science > Dr. James Glenn > HS Programming Contest > Practice Problem 1

Practice

This is a reworked version of one of the practice problems from last year's contest. About half of the teams got this one correct. It represents about the middle of the difficulty of the problems in the 2005-06 contest. The problem has been reworked to reflect how the majority of the problems for this year's contest will be set up. Teams will add methods to existing classes; those new methods will have to use either the existing methods or the fields of the objects in order to perform their tasks. Teams will not have to worry about reading input as the inputs will be hard-coded in the provided mains. The provided test inputs will not be comprehensive; the judging inputs, however, will be comprehensive, so teams should add test cases to ensure that their solutions are 100% correct.

Introduction

Sorted lists of numbers will often be written in a compact form when the list contains several consecutive numbers. The consecutive numbers can be given as a range, for example 1,3-7,9 would represent the list 1, 3, 4, 5, 6, 7, 9. (Note that in the specification of the problem below, ranges are to be output using a colon instead of a dash in order to avoid confusion with negative numbers).

Problem

The given IntegerList class has methods that allow you to iterate through the numbers in the list in sorted order. These methods are nextNumber, which returns the next number in the list (the first invocation returns the first number), hasNextNumber which returns true if nextNumber has something to return, and reset to move back to the beginning of the list.

For example, if l is an integer list object representing the list 1, 5, 6, 7, 10, 11 then the first invocation l.nextNumber() returns 1, the next invocation returns 5, and so on. After 6 invocations of l.nextNumber(), l.hasNextNumber() would return false and l.nextNumber() would throw an exception if it were invoked for the seventh time unless l.reset() were invoked first. Add a method called printList to IntegerList. The output of printList must consist of a comma-separated list of individual numbers and ranges in strictly increasing order. The first and last numbers in a range should be separated by a colon (':'). Ranges should only be used for runs of three or more consecutive numbers. If a number is present in the input then it must either be present in the output explictly as an individual number or endpoint of a range, or implicitly by being between the endpoints of a range. No other numbers should be listed in the output either explicitly or implicitly. The list should be the only line of output from the method.

For example, if l is the list given in the introduction, then l.printList() should print 1,3:7,9.

Assumptions

Code