This document goes through a Java solution for Project Euler problem 220. If you want to achieve the pleasure of solving the unfamiliarity and you don't have a solution yet, PLEASE STOP READING UNTIL YOU FIND A SOLUTION.

Problem 220 is to tell the coordinate after a given large number of steps in a Dragon Curve. The first thing came to my mind, is to DFS traverse a 50 level tree by 10^12 steps, during which it keeps track of a direction and a coordinate. Roughly estimate, this solution takes a 50 level recursion, which isn't horrible, and 10^12 switch/case calls. Written by a lazy and irresponsible Java engineer, this solution vaguely looks like:

Traveler traveler = new Traveler(new Coordinate(0, 0), Direction.UP);
void main() {
  try {
    traverse("Fa", 0);
  } 
  catch (TerminationSignal signal) {
    print signal;
  }
}

void traverse(String plan, int level) {
  foreach(char c:plan) {
    switch(c) {
      case 'F': traveler.stepForward(); break;
      case 'L': traveler.turnLeft(); break;
      case 'R': traveler.turnRight(); break;
      case 'a':
        if(level < 50) {
          traverse("aRbFR", level+1);
        }
        break;
      case 'b':
        if(level < 50) {
          traverse("LFaLb", level+1);
        }
        break;
    };
    if(traveler.steps == 10^12) {
      throw new TerminationSignal("Coordinate after 10^12 steps is "
              + traveler.coordinate);
    }
  }
}

I was quite satisfied with this approach, I thought it was neat, efficient and simple until I ran it. It ran out of all my 20 minutes of patience before I killed the process. It took 10 seconds to calculate for 10^9 steps, it'd take 3 hours for 10^12 steps.

Since I only care the coordinate after 10^12 steps, the solution doesn't have to traverse to the end one step after another if it can predict the coordinate delta after a series of steps. Particularly, since we know "FaRbFR" takes 2 steps and changes direction backwards, we don't have to really go through all 5 characters in "FaRbFR" to know the result. Similarly, we know the coordinate delta brought by FaRbFRRLFaLbFR, or letter 'a' and 'b' in any level. Therefore when the code expand 'a' to "FaRbFR" and traverse it, it can also remember what has been done so that next time it doesn't have to expand it again.

...
Map cachedPaths = new HashMap();
void traverse(String plan, int level) {
  foreach(char c:plan) {
    switch(c) {
      case 'F': traveler.stepForward(); break;
      case 'L': traveler.turnLeft(); break;
      case 'R': traveler.turnRight(); break;
      case 'a':
      case 'b':
        expandSubstitution(c, level);
        break;
    };
    if(traveler.steps == 10^12) {
      throw new TerminationSignal("Coordinate after 10^12 steps is "
              + traveler.coordinate);
    }
  }
}
void expandSubstitution(char c, int level) {
  if(level >= 50) { return; }
  String pathKey = c + "-" + level;
  Path path = cachedPaths.get(pathKey);
  if(path != null && path.steps + traveler.steps < 10^12) {
    traveler.walk(path);
    return;
  }
  Traveler begin = traveler.snapshot();
  if(c == 'a') {
    traverse("aRbFR", level+1);
  } else {
    traverse("LFaLb", level+1);
  }
  path = traveler.pathFrom(begin);
  cachedPaths.put(pathKey, path);
}

This solution takes 50 * 5 * 2 switch/case calls to figure out 100 paths for 'a' and 'b' in 50 levels, at most. With 100 known paths, rest of work is to call walk() for log2(10^12) times. This solution only took 4 milliseconds to finish on my computer (Intel(R) Core(TM)2 CPU 6600 @2.40GHz).

jiaqi@rattlesnake:~/workspace/eulerer$ mvn exec:java
[INFO] Scanning for projects...
...
>>>>>> Runnining solution of problem 220
Coordinate after 10^12 steps is ####76,####04
<<<<<< Solution 220 took 4.089997 ms

For obvious reason, I masked the final result in the output above. If you are not bored enough and wonder what the exact Java code looks like, the source code is hosted in subverion under cyclops-group project in SourceForge.net.

Labels: euler, java

Reflection invocation is a little bit more expensive comparing to the direct call, but it wasn't very slow and it's not slow at all now in JDK 6. It is looking up by name that takes long time.

Operation	2000/11 (probably jdk 1.3.1)	2003/1 (probably jdk 1.3.1)	2004/10 (jdk1.4.2_03)	2007/2 (jdk1.6.0_b105)
100,000 regular calls	2664ms	281ms	203ms	78ms
100,000 reflection calls without lookup	4216ms	297ms	250ms	78ms
100,000 reflection calls with lookup	45505ms	938ms	562ms	203ms
1,000,000 regular calls	27840ms	2578ms	1828ms	594ms
1,000,000 reflection calls without lookup	43863ms	2782ms	2485ms	641ms
1,000,000 reflection calls with lookup	47097ms	5453ms	9343ms	1984ms
10,000,000 regular calls	-	25906ms	17766ms	5063ms
10,000,000 reflection calls without lookup	-	27891ms	24813ms	6141ms
10,000,000 reflection calls with lookup	-	54843ms	93611ms	20093ms

Link: What are the performance costs involved in Java reflection? E.g., looking up a method by name and then invoking it.

Labels: java

Parsing CSV file is easy, it's nothing but splitting string with comma delimiter, which can be easily done in Java... The first thing came to my mind when I'm about to parse CSV file in Java is just like that. Now, reality is that following examples are all possible valid lines in a CSV file

• 1,Bender
• 2,"Bender"
• 3,"Bender, Bending"
• 4,"Ben""d""er"
• 5, Ben"der
• 6, Ben""der

Line 7 might be arguable but anyway, two basic rules are

• If there's comma in field, use double quot to wrap field, otherwise double quot wrapper isn't required.
• Inside double quot, double quot is used to escape double quot.

Suddenly the problem is complicated to something more than string splitting, however it can be simplified into a finite state machine with 4 states.

States:

• 1. Ready for new field (initial state)
• 2. Field without double quot
• 3. Field with double quot
• 4. Escaping or end of double quot

Transitions

*Direction*|*Condition*|*Action*
1->2       |not(" or ,)|Append character to buffer
1->3       |"          |Nothing
2->2       |not ,      |append character to field
1|2|4->1   |,          |Output complete field and create buffer for next field
3->3       |not "      |Append character to buffer
3->4       |"          |Nothing

Labels: java