The Hilbert curves are a class of space-filling fractal curves where every bend in the path is at a right angle and the curve as a whole fills up a square, with the property that sequences of consecutive segments are always displayed as contiguous blocks.
Traditionally, the curve is drawn as a series of very squiggly lines inside a square such that each segment becomes smaller and smaller until they fill up the whole square. However, like the Walsh matrix, it is also possible to represent the limit curve as a sequence of line segments connecting lattice points that grows infinitely until it fills up an entire quadrant of lattice points on the Cartesian plane.
Suppose we define such a curve as the integral Hilbert curve, as follows:
Start at the origin.
Move one unit right (
R
), one unit up (U
), and one unit left (L
). Down will be notated asD
.Let
RUL
beH_1
. Then defineH_2
asH_1 U I_1 R I_1 D J_1
where:I_1
isH_1
rotated 90 degrees counterclockwise and flipped horizontally.J_1
isH_1
rotated 180 degrees.
Perform the steps of
H_2
afterH_1
to completeH_2
.Define
H_3
asH_2 R I_2 U I_2 L J_2
, where:I_2
isH_2
rotated 90 degrees clockwise and flipped vertically.J_2
isH_2
rotated 180 degrees.
Perform the steps of
H_3
afterH_2
to completeH_3
.Define
H_4
and otherH_n
for evenn
the same way asH_2
, but relative toH_{n-1}
.Define
H_5
and otherH_n
for oddn
the same way asH_3
, but relative toH_{n-1}
.The integral Hilbert curve is
H_infinity
.
We get a function f(n) = (a, b)
in this way, where (a, b)
is the position of a point moving n
units along the integral Hilbert curve starting from the origin. You may notice that if we draw this curve 2^{2n}-1
units long we get the n
th iteration of the unit-square Hilbert curve magnified 2^n
times.
Your task is to implement f(n)
. The shortest code to do so in any language wins.
Example inputs and outputs:
> 0
(0, 0)
> 1
(1, 0)
> 9
(2, 3)
> 17
(4, 1)
> 27
(6, 3)
> 41
(7, 6)
> 228
(9, 3)
> 325
(24, 3)
Note that your solution's algorithm must work in general; if you choose to implement your algorithm in a language where integers are of bounded size, that bound must not be a factor in your program's code.