Thoughts on software.

For too long I have been focused on dynamic programming, which I must admit is slightly on the harder side when it comes to recognizing and applying quickly. Its evil twin, greedy, is much more implementation friendly.

There is mention of matroid theory, an approach that can be used for theoretically proving if greedy approach is valid to a particular problem or not. But haven't come around to actually reading it.

For now, my personal rules for greedy: if it is an optimization problem, which seems like Dynamic programming, and if bigger problems seem to be a copy of smaller problems and optimal solution to a smaller problem is sure to be part of optimal solution to the bigger problem, then greed is good.

Here is a practice problem from a recent Topcoder SRM(530), solved of course in a leisurely non contest environment. Once it is clear that a greedy solution is possible, it's just implementation.

Notes to myself: Wasted some time when trying to position the cutter over the cake. Made a mistake when evaluating boundary conditions, using the sizes along x and y for both cutter and cake.

Another observation is that one should work with the data structure provided by the problem statement. Trying to convert the input data into a more understandable array of something, or some other custom data structure, is also a waste of time. Exception is when the original data needs to be preserved, in which case a copy may be made using arrayCopy.

public class GogoXCake
{
public String solve(String[] cake, String[] cutter) {
int cutterSizeX = cutter[0].length();
int cutterSizeY = cutter.length;
int cakeSizeX= cake[0].length();
int cakeSizeY=cake.length;
for(int i=0; i<cake.length;i++) {
for(int j=0;j<cake[i].length();j++) {
if(cutterSizeX<=cakeSizeX-j && cutterSizeY<=cakeSizeY-i && cake[i].charAt(j)=='.' ) { // if cake is empty, position cutter at this location.
for(int p=0;p<cutter.length;p++) {
for(int q=0;q<cutter[p].length();q++) {
if(cutter[p].charAt(q)=='.' && cake[i+p].charAt(j+q)=='.') {
cake[i+p]=cake[i+p].substring(0, j+q)+ 'X' + cake[i+p].substring(j+q+1);
}
}
}
}
}
}
// for(int i=0; i<cake.length;i++) {
// for(int j=0;j<cake[i].length();j++) {
// System.out.print(cake[i].charAt(j) + " ");
// }
// System.out.println();
// }

for(int i=0; i<cake.length;i++) {
for(int j=0;j<cake[i].length();j++) {
if(cake[i].charAt(j)=='.') { // if cake is empty, position cutter at this location.
return "NO";
}
}
}
return "YES";
}
}