1. if (found[LEFT] && found[RIGHT]) {
2. // There's no point to initialize result here (see Line 6)
3. // initResult(result);
4. for (int iIndex : iIndices) {
5. // But here!
6. initResult(result);
7. for (int jIndex = iIndex + 1; jIndex < size; jIndex++) {
8. char nextChar = characters[jIndex];
9. checkFor(nextChar, TARGET[MIDDLE], result);
10. int kIndex = jIndex + 1;
11. if (result.match && rightHash.containsKey(kIndex)) {
12. found[MIDDLE] = true;
13. System
<http://www.google.com/search?hl=en&q=allinurl%3Adocs.oracle.com+javase+docs+api+system>
.out.println("0 -(I)-> " + iIndex + " " + (iIndex + 1) + " -(J)-> " +
jIndex + " "
14. + kIndex + " -(K)->" + size);
15. break;
16. }
17. }
18. }
19. }
On Tue, Apr 14, 2015 at 2:22 PM vthai <[email protected]> wrote:
> Thanks for reviewing Halim, here goes the code, NOTE: if I uncomment the
> JUSTIFICATION part, the result would be the same as the solution, but I am
> suspecting that is not the correct answer
>
> import java.io.BufferedReader;
> import java.io.File;
> import java.io.FileReader;
> import java.io.IOException;
> import java.util.ArrayList;
> import java.util.HashMap;
> import java.util.List;
> import java.util.Map;
>
>
> public class Dijkstra2 {
> public static final char[] TARGET = {'i', 'j', 'k'};
>
> public static final int LEFT = 0;
> public static final int RIGHT = 2;
> public static final int MIDDLE = 1;
>
> Map<Key, char[]> quaternion = new HashMap<Key, char[]>();
> Map<String, String> buffer = new HashMap<>();
>
> public static void main(String[] args) throws IOException {
> Dijkstra2 dijkstra = new Dijkstra2();
> dijkstra.init();
> dijkstra.run(args[0]);
> }
>
> private void initResult(Result result) {
> result.previousResult = new char[]{'+','1'};
> result.match = false;
> }
>
> public void init() {
> quaternion.put(new Key('1', 'i'), new char[]{'+','i'});
> quaternion.put(new Key('1', 'j'), new char[]{'+','j'});
> quaternion.put(new Key('1', 'k'), new char[]{'+','k'});
>
> quaternion.put(new Key('i', 'i'), new char[]{'-','1'});
> quaternion.put(new Key('i', 'j'), new char[]{'+', 'k'});
> quaternion.put(new Key('i', 'k'), new char[]{'-', 'j'});
>
> quaternion.put(new Key('j', 'j'), new char[]{'-', '1'});
> quaternion.put(new Key('j', 'i'), new char[]{'-', 'k'});
> quaternion.put(new Key('j', 'k'), new char[]{'+','i'});
>
> quaternion.put(new Key('k', 'k'), new char[]{'-', '1'});
> quaternion.put(new Key('k', 'j'), new char[]{'-', 'i'});
> quaternion.put(new Key('k', 'i'), new char[]{'+','j'});
> }
>
> private void run(String filename) throws IOException {
> BufferedReader fileReader = new BufferedReader(new FileReader(new
> File(filename)));
> int numberOfCase = Integer.valueOf(fileReader.readLine());
> Result result = new Result();
> Result reverseResult = new Result();
>
> for (int i = 0; i < numberOfCase; i++) {
> System.out.print("Case #" + (i+1) + ": ");
> String[] data = fileReader.readLine().split(" ");
> int numberOfChars = Integer.valueOf(data[0]);
> int repeatTime = Integer.valueOf(data[1]);
> //System.out.println(numberOfChars + "-" + repeatTime);
> int size = numberOfChars * repeatTime;
> char[] characters = new char[size];
>
> String rawData = fileReader.readLine();
> char[] originalChars = rawData.toCharArray();
> for (int time = 0; time < repeatTime; time++) {
> System.arraycopy(originalChars, 0, characters,
> originalChars.length * time, originalChars.length);
> }
>
> List<Integer> iIndices = new ArrayList<>();
> boolean[] found = new boolean[3];
> Map<Integer, Integer> rightHash = new HashMap<>();
>
> initResult(result);
> initResult(reverseResult);
> int reverseIndex;
>
> for (int index = 0; index < size; index++) {
> char nextChar = characters[index];
> checkFor(nextChar, TARGET[LEFT], result);
> if (result.match) {
> found[LEFT] = true;
> iIndices.add(index);
> }
>
> reverseIndex = size - index - 1;
> nextChar = characters[reverseIndex];
> checkForReverse(nextChar, TARGET[RIGHT], reverseResult);
> if (reverseResult.match) {
> found[RIGHT] = true;
> rightHash.put(reverseIndex, reverseIndex);
> }
>
> // JUSTIFICATION: Add in this condition break and my
> result is
> // identical to the solution, BUT this is not correct,
> right?
> // we cannot conclude that the combination does
> // not exist only base on one case of reduction
> //if (found[LEFT] && found[RIGHT])
> // break;
> }
> //System.out.println("\nI found " + iIndices.size() + " K
> found " + rightHash.size());
> if (found[LEFT] && found[RIGHT]) {
> initResult(result);
> for (int iIndex : iIndices) {
> for (int jIndex = iIndex + 1; jIndex < size; jIndex++)
> {
> char nextChar = characters[jIndex];
> checkFor(nextChar, TARGET[MIDDLE], result);
> int kIndex = jIndex + 1;
> if (result.match && rightHash.containsKey(kIndex))
> {
> found[MIDDLE] = true;
> //System.out.println("0 -(I)-> " + iIndex + "
> " + (iIndex + 1) + " -(J)-> " + jIndex + " "
> // + kIndex + " -(K)->" + size);
> break;
> }
> }
> }
> }
>
> if (found[LEFT] && found[MIDDLE] && found[RIGHT]) {
> System.out.println("YES");
> } else {
> System.out.println("NO");
> }
> }
> fileReader.close();
> }
>
> Key key = new Key(' ', ' ');
> public void checkFor(char nextChar, char target, Result result) {
> key.key[0] = result.previousResult[1];
> key.key[1] = nextChar;
> char[] returnValue = quaternion.get(key);
> int previousSign = result.previousResult[0];
> System.arraycopy(returnValue, 0, result.previousResult, 0, 2);
>
> if (previousSign == '-' && returnValue[0] == '-') {
> result.previousResult[0] = '+';
> }
>
> if (previousSign == '-' && returnValue[0] == '+') {
> result.previousResult[0] = '-';
> }
>
> if (previousSign == '+' && returnValue[0] == '+') {
> result.previousResult[0] = '+';
> }
>
> if (previousSign == '+' && returnValue[0] == '-') {
> result.previousResult[0] = '-';
> }
>
> boolean match = result.previousResult[0] == '+' &&
> result.previousResult[1] == target;
> result.match = match;
> }
>
> public void checkForReverse(char nextChar, char target, Result
> rresult) {
> if (rresult.previousResult[1] == '1') {
> key.key[0] = rresult.previousResult[1];
> key.key[1] = nextChar;
> } else {
> key.key[1] = rresult.previousResult[1];
> key.key[0] = nextChar;
> }
> char[] returnValue = quaternion.get(key);
> int previousSign = rresult.previousResult[0];
> System.arraycopy(returnValue, 0, rresult.previousResult, 0, 2);
>
> if (previousSign == '-' && returnValue[0] == '-') {
> rresult.previousResult[0] = '+';
> }
>
> if (previousSign == '-' && returnValue[0] == '+') {
> rresult.previousResult[0] = '-';
> }
>
> if (previousSign == '+' && returnValue[0] == '+') {
> rresult.previousResult[0] = '+';
> }
>
> if (previousSign == '+' && returnValue[0] == '-') {
> rresult.previousResult[0] = '-';
> }
> boolean match = rresult.previousResult[0] == '+' &&
> rresult.previousResult[1] == target;
> rresult.match = match;
> }
>
> public class Key {
> public Key(char o, char t) {
> key[0] = o;
> key[1] = t;
> }
> char[] key = new char[2];
>
> @Override
> public int hashCode() {
> return Integer.valueOf(key[0])*13 + Integer.valueOf(key[1])*7;
> }
>
> @Override
> public boolean equals(Object o) {
> Key k = (Key) o;
> return this.key[0] == k.key[0] && this.key[1] == k.key[1];
> }
> }
>
> public class Result {
>
> boolean match;
>
> char[] previousResult;
> }
> }
>
> --
> You received this message because you are subscribed to the Google Groups
> "Google Code Jam" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to [email protected].
> To post to this group, send email to [email protected].
> To view this discussion on the web visit
> https://groups.google.com/d/msgid/google-code/f3c18d8b-7110-4c0c-9107-4d25cc2da380%40googlegroups.com
> .
> For more options, visit https://groups.google.com/d/optout.
>
--
You received this message because you are subscribed to the Google Groups
"Google Code Jam" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
To view this discussion on the web visit
https://groups.google.com/d/msgid/google-code/CAGDEU-%2BNcxfT1eZsgHdfMrXGwDQLWnYoZvPrHOM%2BX%2BAXQn0wWQ%40mail.gmail.com.
For more options, visit https://groups.google.com/d/optout.
