Jiaqi's Blog

Problem 359, Hilbert's new Hotel Had no idea where to start at all, the only thing I could was to write a small program to print out first hundred numbers in naive way. [ 1 , 3, 6, 10, 15, 21, 28, 36, 45, 55, 66, 78, 91] [ 2 , 7, 9, 16, 20, 29, 35, 46, 54, 67, 77, 92] [ 4 , 5, 11, 14, 22, 27, 37, 44, 56, 65, 79, 90] [ 8 , 17, 19, 30, 34, 47, 53, 68, 76, 93] [ 12 , 13, 23, 26, 38, 43, 57, 64, 80, 89] [ 18 , 31, 33, 48, 52, 69, 75, 94] [ 24 , 25, 39, 42, 58, 63, 81, 88] [ 32 , 49, 51, 70, 74, 95] [ 40 , 41, 59, 62, 82, 87] [ 50 , 71, 73, 96, 100] [ 60 , 61, 83, 86] [ 72 , 97, 99] [ 84 , 85] [ 98 ] As you may see, the result is very interesting. The numbers on the first column seems to be ( row + 1 ) / 2 * ( row / 2 ) * 2. Note that row/2*2 != row since all operations are integer operations. If we calculate the delta values between consecutive numbers in each row, we got 2, 3, 4, 5, 6, 7, 8, 9,10, 11, 12, 13, 5 , 2 , 7, 4 , 9, 6 ,11, 8 ,13, 10 , 15, ...

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; ca...