AdventCalendar

SRM 852 · 2024-01-23 · by misof

SRM 852 · 2024-01-23 · by misof · Brute Force, Simple Search, Iteration, String Parsing

Show categories

Class Name: AdventCalendar

Return Type: String[]

Method Name: eat

Arg Types: (vector<string>)

Problem Statement

An advent calendar is a box with 24 small windows, each containing a piece of chocolate. The windows are numbered from 1 to 24 in no particular order.

You have purchased an advent calendar from the discount bin in your store. You now plan to eat all the chocolate, but you want to still abide by the rules and open the windows in the proper order: 1, 2, 3, and so on.

Formally, a new advent calendar is a String[] in which each String contains only spaces and digits. Additionally, the digits form exactly the numbers from 1 to 24, each exactly once. Multiple numbers can appear within the same String. When they do, they have to be separated by one or more spaces.

E.g., there can be an element " 14 17 " but there cannot be an element " 1417 ". Hence, if you see the substring "14" somewhere, you can be sure that it's the actual number 14 and not the numbers 1 and 4 next to each other.

A partially opened advent calendar is a String[] obtained from a new advent calendar in the following way: for some K (between 0 and 23, inclusive), the K smallest numbers are replaced by the appropriate number of 'X' characters. These represent the K windows that have already been opened.

More precisely, whenever we open a window, each digit of its number is replaced by an 'X'. E.g., "7" becomes "X" and "12" becomes "XX".

You are given the String[] calendar containing a partially opened advent calendar. Find the next number that should be opened, open it by replacing it by the appropriate number of 'X' characters, and return the resulting String[].

Constraints

calendar will have between 1 and 50 elements, inclusive.
Each element of calendar will have between 1 and 50 characters, inclusive.
calendar will be a valid partially opened advent calendar, as described in the problem statement.

Examples

{"19     9        2   24  10 ",
 "  1       18     7 3       11",
 " 20   21 4    17       16    23",
 "  14         12      6    5      ",
 "      8    22     13        15"}
Returns: {"19     9        2   24  10 ", "  X       18     7 3       11", " 20   21 4    17       16    23", "  14         12      6    5      ", "      8    22     13        15" }

This is one example of a new advent calendar. Note that the elements may have different lengths and they may start or end with spaces. (K=0 being allowed in the definition of a partially opened advent calendar means that a new advent calendar also counts as a partially opened advent calendar.) For this calendar, the next window to open is window number 1. Note that all spaces have been preserved in the return value.

{"19     9        X   24  10 ",
 "  X       18     7 3       11",
 " 20   21 4    17       16    23",
 "  14         12      6    5      ",
 "      8    22     13        15"}
Returns: {"19     9        X   24  10 ", "  X       18     7 X       11", " 20   21 4    17       16    23", "  14         12      6    5      ", "      8    22     13        15" }

The calendar from the previous example after windows 1 and 2 have been opened. We open window 3 next.

{"X X X X X X X X X XX XX XX XX XX",
 "XX XX 17 18 19 20 21 22 23 24"}
Returns: {"X X X X X X X X X XX XX XX XX XX", "XX XX XX 18 19 20 21 22 23 24" }

This calendar was probably numbered sequentially. Windows 1-16 have been opened, window 17 is next.

{"  X X X X X X X X X XX XX XX XX XX  ",
 "  XX XX 24 XX XX XX XX XX XX XX  "}
Returns: {"  X X X X X X X X X XX XX XX XX XX  ", "  XX XX XX XX XX XX XX XX XX XX  " }

{"  7  X  19", "   6   12 4   20  16   17  ", "   8   22   X 13 9 18  ", " 5   11", " 21  3 24  10   23  15  14   "}
Returns: {"  7  X  19", "   6   12 4   20  16   17  ", "   8   22   X 13 9 18  ", " 5   11", " 21  X 24  10   23  15  14   " }

64)

{"X X X X X X X X X XX XX XX XX XX",
 "17 XX XX 18 19 20 21 22 23 24"}
Returns: {"X X X X X X X X X XX XX XX XX XX", "XX XX XX 18 19 20 21 22 23 24" }

Sometimes the numbers can appear on the beginning or end of line, too.

Submissions are judged against all 67 archived test cases, of which 6 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class AdventCalendar with a public method vector<string> eat(vector<string> calendar) · 67 test cases · 2 s / 256 MB per case