Same GNOME
Problem: Given a string S, find the shortest string obtained by repeatedly removing any series of identical characters of length at least 2. Find the shortest transcipt?
In 2d, we generalize it as follows. We have an n X n gird in which each cell is labeled one of the 4 colors R,G,B,Y. Find the smallest object by repeatedly dropping any contiguous portion of identical colors (colors pack the empty cells if any to the bottom and left). Reminds one of the Same GNOME game (not quite interesting as a game?). Any formal analysis out there?
In 2d, we generalize it as follows. We have an n X n gird in which each cell is labeled one of the 4 colors R,G,B,Y. Find the smallest object by repeatedly dropping any contiguous portion of identical colors (colors pack the empty cells if any to the bottom and left). Reminds one of the Same GNOME game (not quite interesting as a game?). Any formal analysis out there?
posted by metoo at 7:41 PM
0 Comments:
Post a Comment
<< Home