Algorithm

 Problem Statement for Algrid

Problem link- https://community.topcoder.com/stat?c=problem_statement&pm=11348&rd=14433

Problem Statement
     Algrid is a program that uses a single grid with cells colored white or black as input and returns a new one as output. The grid has H rows and W columns. The topmost row is row 0, the bottommost row is row H-1, the leftmost column is column 0 and the rightmost column is column W-1. The cell at row i, column j can be denoted as (i,j). The program works by evaluating pairs of contiguous cells and making decisions depending on their contents. The following pseudo-code describes how the program works:



For i = 0 to H-2:
    For j = 0 to W-2:
        //Get the current colors of cells (i,j) and (i,j+1)
        A = Color(i,j) , B = Color(i,j+1)

        If (A,B) == (White, White) Then:
             Do nothing.
        EndIf
        If (A,B) == (Black, White) Then: 
             Repaint cells (i+1,j) and (i+1,j+1) Black.
        EndIf
        If (A,B) == (White, Black) Then:
             Repaint cells (i+1,j) and (i+1,j+1) White.
        EndIf
        if (A,B) == (Black, Black) Then:
             Swap the colors in cells (i+1,j) and (i+1,j+1).
        EndIf
    EndFor
EndFor




You will be given a possible output for the program as a String[] output. The j-th character in the i-th element of output represents the color of cell (i,j) where 'W' represents white and 'B' represents black. Find an input grid that would yield output as a result. If there is more than one possible result, find the lexicographically smallest one. Return the found grid as a String[] following the same format as the input. If there are no grids that would generate the wanted output, return an empty String[] instead.
 

Definition
    
Class: Algrid
Method: makeProgram
Parameters: String[]
Returns: String[]
Method signature: String[] makeProgram(String[] output)
(be sure your method is public)
    
 
 

Notes
- To compare two String[]s A and B, find the smallest index i such that A[i] and B[i] differ. If A[i] is lexicographically smaller than B[i], we say that A is lexicographically smaller than B, and vice versa.
- To compare two Strings C and D, find the smallest index i such that the characters C[i] and D[i] differ. If C[i] is smaller in ASCII ordering than D[i], we say that C is lexicographically smaller than D, and vice versa.
 

Constraints
- output will contain between 2 and 16 elements, inclusive.
- Each element of output will contain between 2 and 16 characters, inclusive.
- All elements of output will have the same length.
- Each element of output will only contain 'W' or 'B' characters.
 

Examples
0)  
     
{"WWWWWWW",
 "WWWWWWB",
 "BBBBBWW"}
 
Returns: {"WWWWWWW", "WWWWWWB", "BBBBBBB" }
The following is another input grid that would yield the same output but is not the wanted result as it is not the lexicographically smallest: 
WWWWWWW
WWWWWWB
BBBBBWB
1)  
     
{"BBBBB",
 "WBWBW"}
 
Returns: {"BBBBB", "WWBWB" }
 
2)  
     
{"BBBB",
 "BBBB",
 "BBWB",
 "WWBB",
 "BWBB"}
 
Returns: { }
There is no possible input that would generate this output.
3)  
     
{"WWBBBBW",
 "BWBBWBB",
 "BWBBWBW",
 "BWWBWBB"}
 
Returns: {"WWBBBBW", "BBBBBWB", "BBBBBBB", "BBBWBBB" }

 

Code Examples

#1 Code Example with C++ Programming

Code - C++ Programming

#include <bits/stdc++.h>

using namespace std;

class Algrid {
public:
  vector<string> makeProgram(vector < string> output) {
    vector<string> ret;
    ret.resize(output.size());
    ret[0] = output[0];

    for(int i = 0; i < output.size() - 1; ++i) {
      for(int msk = (1 << output[i].length()) - 1; msk >= -1; --msk) {
        if(msk == -1) {
          vector<string> ret;
          return ret;
        }

        string s = "";
        for(int j = output[i].length() - 1; j >= 0; --j)
          s += ((msk >> j) & 1) ? 'B' : 'W';
        string ss = s;

        for(int j = 0; j < output[i].length() - 1; ++j) {
          if(output[i][j] == 'B' && output[i][j + 1] == 'W')
            s[j] = s[j + 1] = 'B';
          if(output[i][j] == 'W' && output[i][j + 1] == 'B')
            s[j] = s[j + 1] = 'W';
          if(output[i][j] == 'B' && output[i][j + 1] == 'B')
            swap(s[j], s[j + 1]);
        }

        if(s == output[i + 1]) {
          ret[i + 1] = ss;
          break;
        }
      }
    }

    return ret;
  }
};
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
{"WWWWWWW", "WWWWWWB", "BBBBBWW"}

Output

x
–
+
cmd
{"WWWWWWW", "WWWWWWB", "BBBBBBB" }
Advertisements

Demonstration

TopCoder Solution SRM504-D2-1000 Statement for Algrid C,C++, Java, Js and Python ,SRM504-D2-1000,TopCoder Solution