fluffychaos fluffychaos - 3 months ago 35
Java Question

Find if there exists a circle given moves

I was asked a question similar to this one on HackerRank: Check If there exists a Circle

The difference was that F was replaced with G (i.e. G means go forward one step).

I implemented an algorithm like the one described in the accepted answer, but I failed one test case. Could someone please find the bug for me?

static String checkIfCircleExists(String s) {
int x = 0;
int y = 0;
int dir = 0;

for (char c : s.toCharArray()) {
switch (c) {
case 'G':
switch (dir) {
case 0:
y++;
break;
case 1:
x++;
break;
case 2:
y--;
break;
case 3:
x--;
break;
}
break;
case 'L':
dir = Math.abs((dir - 1) % 4);
break;
case 'R':
dir = Math.abs((dir + 1) % 4);
break;
}
}

if (x == 0 && y == 0) {
return "YES";
}
return "NO";
}


Edit

This is a helper method. The input to this helper method is the original input string concatenated with three copies of the original input string. For example, for input "G", "GGGG" will be passed in this helper.

MBo MBo
Answer

Does code (dir - 1) % 4 work as intended in your language?

If not, replace it with (dir + 3) % 4

not actual after question editing, but might be useful to reduce run time:

Note that moving is limited in two cases:

  1. Final displacement is zero (your solution checks for this case)
  2. Final direction differs from initial one (in this case object returns in the initial position after two or four rounds)

Seems you dismissed the second one.

Comments