Skip to main content

Project Euler problem 220 - Heighway Dragon

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.

Comments

Popular posts from this blog

Spring, Angular and other reasons I like and hate Bazel at the same time

For several weeks I've been trying to put together an Angular application served Java Spring MVC web server in Bazel. I've seen the Java, Angular combination works well in Google, and given the popularity of Java, I want get it to work with open source. How hard can it be to run arguably the best JS framework on a server in probably the most popular server-side language with  the mono-repo of planet-scale ? The rest of this post walks through the headaches and nightmares I had to get things to work but if you are just here to look for a working example, github/jiaqi/angular-on-java is all you need. https://github.com/jiaqi/angular-on-java Java web application with Appengine rule Surprisingly there isn't an official way of building Java web application in Bazel, the closest thing is the Appengine rule  and Spring MVC seems to work well with it. 3 Java classes, a JSP and an appengine.xml was all I need. At this point, the server starts well but I got "No

Wreck-it Ralph is from Chicago?

Hotel Felix in Chicago   The building of Fix-it Felix Jr.