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 ','.

Test your code

You can test your program against both the input provided in the test phase and the input provided in the submit phase. A nice output will tell you if your program got the right solution or not. You can try as many times as you want. Be careful with extra whitespace. The output should be exactly as described.

Test your program against the input provided in the test phase

Download test input

Program output:

Test your program against the input provided in the submit phase

Download input

Program output:

During the submit phase, in some problems, we might give your program harder inputs. As with the test token, a nice output will tell you if your program got the right solution or not. You can try as many times as you need.

In the actual contest you have to solve the test phase before you can submit your code. You must provide the source code used to solve the challenge and you can only make one submission. After your solution is submitted, you won't be able to modify it to fix issues or make it faster.

If you have any doubts, please see the info section.