Connection Status:
Competition Arena > Amoebae

Amoebae

SRM 172 · 2003-11-20 · by lbackstrom

SRM 172 · 2003-11-20 · by lbackstrom · String Manipulation, String Parsing
Class Name: Amoebae
Return Type: int
Method Name: cultureX
Arg Types: (vector<string>, vector<string>)
Problem Statement

Problem Statement

Your boss, the absent-minded biologist, has gone too far. It's one thing if he chills his lemonade in the lab refrigerator, but this morning he inadvertently rearranged the petri dishes. Now the old bird is calling for Culture X. You've found a dish of amoebae that looks like it might be Culture X, and you even have a photograph of Culture X taken yesterday, but these critters move around freely. They spin and glide through the dish and even flip over, making it hard to tell whether you're still looking at the same culture.

You are given a String[] describing a known state of Culture X. Consider it as a rectangular grid of squares, each of which is marked either '.' or 'X'. An amoeba is a component formed of directly adjacent 'X' squares. If an amoeba is composed of more than one 'X' square, then each of its 'X' squares shares an edge with at least one other 'X' square in the same amoeba. No two 'X' squares belonging to different amoebae may share an edge, but they are permitted to neighbor each other diagonally. An amoeba may contain holes. For example, the dish below contains five amoebae. Observe that one of them comprises exactly two squares, while another consists of a single square. 


          ...XXXXXXX.......
          ....X.X.X........
          ...XXXXXX........
          ...............XX
          ......X.....XX..X
          .XXXXX........X.X
          .X.XXX.......XXXX

Given a second String[] with the same dimensions, decide whether it depicts the same collection of amoebae. Amoebae are considered identical under rotation (at right angles), reflection (in the horizontal or vertical axis), and translation (to any extent, as long as the amoeba remains wholly within the petri dish). Return 0 if both dishes contain the same amoebae. Otherwise, return the sum of these two figures: (a) the number of amoebae in Culture X that are not present in the candidate dish and (b) the number of amoebae in the candidate dish that are not present in Culture X.

Constraints

  • known and candidate have the same number of elements
  • known and candidate each have between 1 and 50 elements, inclusive
  • all elements of known and candidate are equally long
  • elements of known and candidate are each between 1 and 50 characters long, inclusive
  • all characters in known and candidate must be either '.' or 'X'
Examples
0)
{"...XXXXXXX.......",
 "....X.X.X........",
 "...XXXXXX........",
 "...............XX",
 "......X.....XX..X",
 ".XXXXX........X.X",
 ".X.XXX.......XXXX"}
{"X.X..........XXXX",
 "XXX...XX......X.X",
 "X.X...XX........X",
 "XXX...XX.......XX",
 "X.X....X.X.......",
 "XXX...XX.X.......",
 "X.......X........"}
Returns: 0

You've found Culture X! All the amoebae have been translated since yesterday. The one that was in the lower right corner has also been reflected in the horizontal axis. The one at lower left has been reflected and rotated, as has the big ugly one with two holes. The amoeba formed of two squares has been rotated.

1)
{"...XXXXXXX.......",
 "....X.X.X........",
 "...XXXXXX........",
 "...............XX",
 "......X.....XX..X",
 ".XXXXX........X.X",
 ".X.XXX.......XXXX"}
{"X.X..........XXXX",
 "XXX...XX......X.X",
 "X.X...XX........X",
 "......XX.......XX",
 "X.X....X.X.......",
 "XXX...XX.X.......",
 "X.......X........"}
Returns: 3

Four amoebae from Culture X are present in the candidate petri dish, but the big ugly one with two holes is missing. Furthermore, the candidate dish has two amoebae that were not present in Culture X. In total, this makes a difference of 1+2=3.

2)
{"......................",
 "....XXX...............",
 "..X...X......XX.XX....",
 "..XX.........XX.XX....",
 "...XX.................",
 "..........X...X..XXXX.",
 "..XXX.....XX.XX.XX..XX",
 "..X........X.X..X....X",
 ".....XX....XXX..X....X",
 ".....XX.....X...XX..XX",
 "............X....XXXX."}
{"....X......XX.XX.XX...",
 "....XXX....XX.XX.XX...",
 ".........XX...........",
 ".........XX...........",
 "......................",
 "..X....XXXX....X......",
 "..X...XX..XX...X......",
 ".XXX..X....X..XXX.....",
 ".X.X..X....X..X.X.....",
 "XX.XX.XX..XX.XX.XX....",
 "X...X..XXXX..X...X...."}
Returns: 4

Compared to Culture X, the candidate dish has an extra Y-shaped amoeba and an extra two-by-two amoeba, but it's missing a small L-shaped amoeba, and it doesn't have the squiggly one at all. That makes a symmetric difference of 4.

3)
{".XXXX.X...X...XXXX..", 
"X..XXXXXXX.X.....XX.", 
".X.X.XX....X..XXX..X", 
"..XXX.X.X....X......", 
".XXXXX...X.....XXXX.", 
"..X.XXX..XX....XXX.X", 
".......XXX..X.X...XX", 
"XX....X.....X...X.X.", 
".....X.....XX..XXX.X", 
"X...XX.X.X..X....X.X", 
".X........X.........", 
".X..X.........X.....", 
"..X.X..X..........XX", 
"........X.X...X.XX..", 
"....X.......X.X..X.X", 
"....XX..X..X.X.X...X", 
"X.....X.........X.X.", 
"X.X...X.............", 
"..XXX.X...X..X..XX..", 
"X.......XX...X......"}
{".X.....X.X......XX.X", 
"X.X.X..X..XX........", 
"X..XXX......X....XX.", 
"XXXXX.............X.", 
"XX.XXX...X.XX.XX..X.", 
".XX.XX..XX.....X....", 
"XXXX.X.X........XXX.", 
".X....X..X..X.......", 
".X.X..X......X.X...X", 
".X..XXX..X.........X", 
"X....X....X..X....X.", 
".XX.....X......X....", 
"......XXXX....X.....", 
"...X...........X..XX", 
"X.X...X....X.XX.....", 
"X.X.XX..X......X....", 
"X.X.XX.XX....X..X.X.", 
"XX..XX..XX...XX...X.", 
".X..X.XX....X...X...", 
"..X..XX.XX..X.XX...."}
Returns: 0
4)
{".....XXX...X.....XX.....XX.XX..XX..", 
"..X.XX.XX.X....XXX....X......X.....", 
".....XX...X....X.X....X.X.X........", 
"X.....X.......XXX.X....X..XX.X.....", 
".X.X....X.X........X..........XX...", 
"........XX........X.....X..X.X.....", 
".X..X...X...XX.X..X.....X..........", 
"..............X......X...X....X..X.", 
"XX..X.....XX..X...X...X.X..X....X..", 
".X....XX..X...............X.X.XXXX.", 
"...XXXXX.....X...X....X.XX..XXX..X.", 
".........X..XX....X.X......XXXX....", 
"..XXXX.X..XXX.X...........X..X.XX..", 
"X...X...........X..X.X..X.XX..X.X..", 
"..X....X.....X..X.X....X..X.X..XXXX", 
"X..XXX..X..XX.XX.X..X...X...X..X.XX", 
"....X....X.X...X..X..X..XXX...XXXX.", 
".X..XX.XX.....X..XX..............XX", 
"X..........X..X......XXXX.....X..X.", 
".X.XXX...X..X..XX.X.X.X.X..X.......", 
"X....X.........X....XXXX..X....X..X", 
"..X.XX...X......X.X.......XX....X..", 
"X.XXXX....X.XXX..XX..XXXX.X.XX.....", 
"XXX.X........X.X..X..X....X..X.....", 
"......X..X..XX..X.....XX........X..", 
"...X.....XX..X..X..X.X......XX..X.X", 
"..X..X.......XX......X......X...XX.", 
"..X.XX......XX.X..X.....X...X.X..X.", 
".X.X.XX.XXX.X..X.X.................", 
".......X.XX..X..X..X.....X.X..XX..X", 
"X...XX.......X...X...X.X....X......", 
"X.......X.X......X.X.X......X.....X", 
"....X.X.X.X....XXX..XX.....XX.X..X.", 
"...X..X.X.XX......X.....XX.XXXX....", 
"..X......X...X.X...X...X.X.XXXX...X"}
{"..XX......X..XX.X....X..X.XX..X....", 
"...X.X.X.......X..X....X...........", 
".XXX.X.XXX.....X.X.X..XX.XX.X.XX.XX", 
"X...X......X.X........X...X.X.....X", 
"X.....X....X...XX....X.X........XX.", 
"..XXX...XXX............X.XX..XX..XX", 
"....X.X..X..X.X...X.X....X.XX...X..", 
".XX..X........XX..X......XX..X....X", 
"...X......X...X..X...XX...XXX..X.X.", 
"..XX...X..X...X...X.XX.....X.....X.", 
".XX.X........X..X..X......XX.X.XX..", 
".X.X..XX..X.XX......X....X.........", 
"X..X.X..X........X.....X..X..XX...X", 
"X.X.........X.XXX..XX..X.........X.", 
".........X......XX.....X.....X..X.X", 
"X..X.X.XXX.X.....X...X...X...X..X.X", 
"X......X..X.XX.X......X....XX.....X", 
"X.X...................X...X..X..XX.", 
".........X........X..XX..X......X.X", 
".X....X.X.X.......X..XX..XX.XXX...X", 
".................XXX...XX...X..X...", 
"..X...X...XX.....X.....X..XX....XX.", 
".......XXX.XX....X...XX..XXX.X....X", 
"........X...XXXX..X..........X.....", 
"..........XX.X.XX.X.........XX....X", 
"...X.....X.X.................X....X", 
"...XX.X.....X.....XXXX...X...X.X...", 
".............X.....X..X..X.X.X..X..", 
"...............X....X....X..X.X.X.X", 
".XX..XX........X.....X.XX....X....X", 
"...X....X..X...XXX..X........X.....", 
"X.XXX.XX..X......XX.X......X.X.X...", 
".XX.X....X..X..X.X.................", 
"....XXX.X.X......XX.....XX...X.XX..", 
"......X....XX..X.....X...XX.X.....X"}
Returns: 64

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

Coding Area

Language: C++17 · define a public class Amoebae with a public method int cultureX(vector<string> known, vector<string> candidate) · 43 test cases · 2 s / 256 MB per case

Submitting as anonymous