Tuenti Challenge 10

Challenge 18 - Matters with Formatters

We've finished building our platform, but there is a problem. We have a service that sends data to multiple endpoints. But because of a lack of coordination between the development teams, some of the endpoints accept data in a different format!

Since we're in a hurry, we need to make as few changes as possible to the original string to make it valid in both of the accepted formats. Bear in mind at least one format is already valid. A change consists of changing the character at one position. It's OK to change the structure/contents of the data, so I'll only describe what the data needs to contain for it to be parseable in each format:

  • ESC (Elements Separated by Commas): Each line contains at least two elements separated by commas. An element can be an empty string.
    • Example 1 (one line with only two elements):
      foo,bar
    • Example 2 (one line with three empty elements):
      ,,
    • Example 3 (multiple lines, each with a different number of elements):
      alfa,beta,gamma
      foo,bar
      test,a[5],asdf
  • LOLMAO (List-Oriented Language with Multiple Advanced Options): Each element is either a literal or a list:
    • Literals can have any character except '[', ']', ',' or they can have no characters, in which case, the literal would be an empty string.
    • Each list starts with a '[' and ends with a ']', and can contain zero, one or multiple elements separated by commas. The elements can be empty literals, lists of literals or lists at the same time!
    • The entire data is either a literal or a list.
    • Example 1 (a literal):
      foo
    • Example 2 (an empty list. Empty lists can also be seen as a list with one empty literal. But in order to remove the ambiguity, empty literals must be followed by a ','):
      []
    • Example 3 (a list with one literal):
      [foo]
    • Example 4 (a complex list):
      [[],foo,[[[,],[1,2],5,,],some0literal
      with3multiple
      lines]]

Input

The first line has an integer C, which is the number of cases for the problem, and C cases follow. Each case starts with a line with an integer L, which is the number of lines data. The next L lines are the original data D, including the line breaks.

Output

For each case, there should be a line starting with "Case #X: " followed by the minimum number of changes you need to do to the original data to make it valid in both of the accepted formats (ESC and LOLMAO), or "IMPOSSIBLE" if it's not possible.

Limits

  • 1 ≤ C ≤ 200
  • 1 ≤ L
  • 1 ≤ length(D) ≤ 400 if the original format is ESC
  • 1 ≤ length(D) ≤ 4000 if the original format is LOLMAO
  • D only includes letters, digits, line breaks (\n), ',', '[' and ']'

Sample Input

4
1
[foo,bar]
2
[foo,
bar,[
1
fb
2
[[],[]
,[]]

Sample Output

Case #1: 0
Case #2: 1
Case #3: IMPOSSIBLE
Case #4: 1

In the first case, the original string is already valid in both formats so no changes are needed.
In the second case, we replace the last '[' with a ']'.
In the third case, the string cannot be made valid in both formats at the same time.
In the last case, we can replace the line break with a ','.

Problem stats

Completion time: min: 1:57:55 h
10th percentile: 2:36:30 h
90th percentile: 47:19:12 h
max: 54:17:43 h
Test phase time: 10th percentile: 2:33:37 h
90th percentile: 30:20:38 h
Submit phase time: 10th percentile: 0:01:16 h
90th percentile: 15:55:04 h
# of completions:24