PreemptiveChannelSelection | Topcoder Archive

Problem Statement

Tired of treasure hunting, Robert has decided to relax in front of his brand new TV set.

The TV can receive up to 999 channels, each of which is assigned a number between 1 and 999. Normally, Robert punches the 3-digit channel code into the remote to have it switch to a channel. For one and two-digit channels, he prepends the channel number with leading zeros. For example, to switch to channel 123, he'll press the buttons 1, 2, and 3. To switch to channel 25, he'll press the buttons 0, 2 and 5. To switch to channel 6, he'll press 0, 0, 6.

Robert doesn't get that many channels so most of these numbers will be unoccupied. The TV set comes with a new feature, called preemptive channel selection:

Whenever a user starts entering a number and there is exactly one channel matching the digits entered so far, the TV will immediately switch to that channel, without waiting for the user to enter the remaining digit or digits. For example, suppose the TV has channels 12, 456, and 478. If the user starts pressing 456, the TV will switch to that channel after the digits 4 and 5 are entered, because there is no other channel starting with the digits 45.
Similarly, when a user enters a sequence which cannot match any channels, the TV will reject it and allow the user to enter a new number. In the above example, if the user entered 49, the TV would recognize it as a mistake and allow the user to start over (after the 9 was entered).

The TV displays the digits entered so far, so that it is easier for the user to track what is happening. Missing digits are displayed as underscores ('_'). When the TV switches to a channel, the entire number is displayed. Here's an example of how the display can change if the channels are 12, 456 and 478:

                   display
Robert enters 4      4__
Robert enters 5      456 (TV switched to channel 456)
Robert enters 0      012 (TV switched to channel 12)
Robert enters 4      4__
Robert enters 9      ___ (no channels start with 49)

Given a int[] channels, the numbers on the TV which are occupied by channels, and a int[] buttonsPressed, the buttons that Robert presses (in order), return a String[] containing the state of the display after each button that Robert presses.

Definition

Class:: PreemptiveChannelSelection
Method:: selectedChannels
Parameters:: int[], int[]
Returns:: String[]
Method signature:: String[] selectedChannels(int[] channels, int[] buttonsPressed)
(be sure your method is public)

Constraints

channels will contain between 1 and 50 elements, inclusive.
Each element of channels will be between 1 and 999, inclusive.
channels will not contain duplicates.
buttonsPressed will contain between 1 and 50 elements, inclusive.
Each element of buttonsPressed will be between 0 and 9, inclusive.

Examples

```
{12, 456, 478}
```
```
{4, 5, 0, 4, 9}
```
```
Returns: {"4__", "456", "012", "4__", "___" }
```
This is the example from the problem statement. After entering 4 and 5, the TV recognizes that Robert wants to switch to channel 456. After pressing 0, it switches to channel 12, since it's the only channel that would start with a zero. The TV considers the final 49 as a mistake and clears the display.

{12, 13}

{1, 2, 0, 1, 2}

Returns: {"___", "___", "0__", "01_", "012" }

{1, 12, 123}

{0, 0, 0, 1, 1, 2, 3}

Returns: {"0__", "001", "0__", "012", "123", "___", "___" }

{1, 12, 123, 9, 19, 129}

{0, 0, 1, 0, 1, 2, 1, 2, 3}

Returns: {"0__", "00_", "001", "0__", "01_", "012", "1__", "12_", "123" }

No shortcuts here.

{444, 555, 666}

{2, 3, 7, 8, 9, 0, 0, 0, 1}

Returns: {"___", "___", "___", "___", "___", "___", "___", "___", "___" }

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.