Moderators: jestingrabbit, Prelates, Moderators General
Now, there's still a shirt open for 'most elegant algorithm' -- I already have a conceptual approach that lets me generate the numbers. That's how I got the original list. What I'd like to see is a couple lines of code or a simple equation that takes in the argument, does a trick, and spits out the result. I feel like there should be a simple iterative solution with shuffling bits, but I don't have it.
N G(N) G(N) bin G(N) ^ G(N-1) F(N) ^ F(N-1)
0 0 00000000 0 0
1 1 00000001 1 1
2 3 00000011 2 2
3 2 00000010 1 1
4 7 00000111 5 10
5 6 00000110 1 2
6 4 00000100 2 1
7 5 00000101 1 2
8 15 00001111 10 5
9 14 00001110 1 2
10 12 00001100 2 1
11 13 00001101 1 2
12 8 00001000 5 10
13 9 00001001 1 1
14 11 00001011 2 2
15 10 00001010 1 1
16 31 00011111 21 21
17 30 00011110 1 2
18 28 00011100 2 1
19 29 00011101 1 2
20 24 00011000 5 5
21 25 00011001 1 1
22 27 00011011 2 2
23 26 00011010 1 1
24 16 00010000 10 10
25 17 00010001 1 1
26 19 00010011 2 2
27 18 00010010 1 1
28 23 00010111 5 5
29 22 00010110 1 2
30 20 00010100 2 1
31 21 00010101 1 2
32 63 00111111 42 42
33 62 00111110 1 2
34 60 00111100 2 5
35 61 00111101 1 2
BaldAdonis wrote: A) (1 --> 2--> 3), 0 fixed
-->If ((x_1=0, x_2 + x_3 is even) OR (x_1=1, 2, x_2 + x_3 is odd) apply A to x_0.
int N = 42;
int[][][] state =
{
{ {1,0,0}, {0,1,0}, {0,1,1}, {3,0,1} },
{ {0,0,0}, {1,0,1}, {1,1,1}, {2,1,0} },
{ {3,1,1}, {2,0,1}, {2,0,0}, {1,1,0} },
{ {2,1,1}, {3,1,0}, {3,0,0}, {0,0,1} }
};
int M = 15; //datatype has at least M*2 bits
int x = 0; //(x,y) coordinates in space, N units along space-filling curve
int y = 0;
int m = (1<<(M-1)); //current scale
int s = (M-1)%2==0 ? 0 : 1; //starting state
for (int i = M-1; i >= 0; i--) { //for each decreasing scale
int r = (N>>>(i*2))%4; //value of N at that place in base 4
x += state[s][r][1]*m; //add the offset (0 or 1) times the scale
y += state[s][r][2]*m;
s = state[s][r][0]; //transition to a new curve direction
m = m>>>1; //decrease scale
}
//convert (x,y) to F(N)
int f = 0; //start value at corner
m = 1; //current scale
while(x>0) { //each bit of x
f += (x%2)*m; //add the offset (0 or 1) times the scale
x = x>>>1; //delete lowest bit
m = m<<2; //increase scale
}
m = 2;
while(y>0) {
f += (y%2)*m;
y = y>>>1;
m = m<<2;
}
System.out.println(f);
to R
if :n = 0 [stop]
make "n :n - 1
rt 90 L F
lt 90 R F R
lt 90 F L rt 90
make "n :n + 1 ; restore :n to value before procedure was called
end
to L
if :n = 0 [stop]
make "n :n - 1
lt 90 R F
rt 90 L F L
rt 90 F R lt 90
make "n :n + 1
end
to F
if :count = 0 [
make "coord (map [abs round ? / :dist] list (first pos) + 250 (last pos) - 250)
ifelse :swap = 1 [print reverse :coord] [print :coord]
throw "hilbert.result
]
make "count :count - 1
FD :dist
end
to abs :n
ifelse :n < 0 [op 0 - :n] [op :n]
end
to HILBERT :n :count
hideturtle
fence
penup
setpos [-250 250]
setheading 180
clean
pendown
local "dist
make "dist 500 / (power 2 :n - 1 / power 2 :n)
catch "hilbert.result [L]
end
type "|Enter a number to calculate: |
make "num readword
make "degree ((int (ln :num + 1) / (ln 4)) + 1)
; if degree is even, we need to flip the coordinates from the output
; because every other degree is flipped
ifelse (modulo :degree 2) = 0 [make "swap 1] [make "swap 0]
HILBERT :degree :num
bye
GreedyAlgorithm wrote:I must admit I cannot rationalize F(34)=55 and F(35)=53. (...) For 0<=x<=33 and x=71, F'(x)=F(x), but F'(34)=51 and F'(35)=49.
/** An iterative solution to the puzzle
* Essentially loops through [0, 1, 3, 2] back and forth to get the answer
* @Author: Craig Gidney */
public class SolDigit {
private int val=0, //current value
inc=1, //direction
index=0, //digit position
count=0; //number of increments of this digit
private SolDigit next=null, prev=null; //for linking this list
/** When run, display output of F on [0, 35] U [71, 71] */
public static void main(String args[]) {
SolDigit d = new SolDigit();
int a;
//Print out 0-36
for (a = 0; a < 36; a++) {
System.out.println(d);
d.increment();
}
//Print out F(71)
for (; a < 71; a++)
d.increment();
System.out.println(d);
//Print out F(31337)
for (; a < 31337; a++)
d.increment();
System.out.println(d);
}
/** turns our values into the digits they actually represent (just swaps 2 and 3) */
private int digit() {
return (val == 2) ? 3 : (val == 3) ? 2 : val;
}
/** Increment to the next output of F */
public void increment() {
//increment
val = (val + inc + 4) % 4;
count++;
//switch directions at these values
if (count % 16 == 4 || count % 16 == 8 || count % 16 == 11 || count % 16 == 15)
inc *= -1;
//switch direction of previous digits at val == 2
if (val == 2)
for (SolDigit p = prev; p != null; p = p.prev)
p.inc *= -1;
//increment next digit when we roll over
if (count % 4 == 0) {
//create it if it doesn't exist
if (next == null) {
next = new SolDigit();
next.index = index + 1;
next.inc = (int)Math.pow(-1, next.index); //initial direction
next.prev = this;
}
next.increment();
}
}
/** Sum the digits' values */
public int actualVal() {
//Leftshift (base 4) next digit's value and add ours
return ((next != null) ? next.actualVal()*4 : 0) + digit();
}
public String toString() {
return "F(" + count + ") = " + actualVal();
}
}
F(0) = 0
F(1) = 1
F(2) = 3
F(3) = 2
F(4) = 8
F(5) = 10
F(6) = 11
F(7) = 9
F(8) = 12
F(9) = 14
F(10) = 15
F(11) = 13
F(12) = 7
F(13) = 6
F(14) = 4
F(15) = 5
F(16) = 16
F(17) = 18
F(18) = 19
F(19) = 17
F(20) = 20
F(21) = 21
F(22) = 23
F(23) = 22
F(24) = 28
F(25) = 29
F(26) = 31
F(27) = 30
F(28) = 27
F(29) = 25
F(30) = 24
F(31) = 26
F(32) = 48
F(33) = 50
F(34) = 51
F(35) = 49
F(71) = 134
F(31337) = 37757
xkcd wrote:BaldAdonis, your answer for F(31337) in your main post is off, but GreedyAlgorithm got it right.
sub fb($)
{
my @table=([0,1,2,3],[0,2,1,3],[3,2,1,0],[3,1,2,0]);
my $n=shift;
if($n==0) { return (0,0) }
elsif($n==1) { return (1,1) }
elsif($n==2) { return (3,1) }
elsif($n==3) { return (2,2) }
{
my ($b1,$trans1)=fb($n&3);
my ($b2,$trans2)=fb($n>>2);
return ((($b2<<3)&0xaaaaaaa8)|(($b2<<1)&0x55555554)|$table[$trans2][$b1],$trans1^$trans2);
}
}
N f(N) base2 f(N)^f(N-1) base2
1 1 000000000000000000001 1 000000000000000000001
2 3 000000000000000000011 2 000000000000000000010
4 8 000000000000000001000 10 000000000000000001010
8 12 000000000000000001100 5 000000000000000000101
16 16 000000000000000010000 21 000000000000000010101
32 48 000000000000000110000 42 000000000000000101010
64 128 000000000000010000000 170 000000000000010101010
128 192 000000000000011000000 85 000000000000001010101
256 256 000000000000100000000 341 000000000000101010101
512 768 000000000001100000000 682 000000000001010101010
1024 2048 000000000100000000000 2730 000000000101010101010
2048 3072 000000000110000000000 1365 000000000010101010101
4096 4096 000000001000000000000 5461 000000001010101010101
8192 12288 000000011000000000000 10922 000000010101010101010
16384 32768 000001000000000000000 43690 000001010101010101010
32768 49152 000001100000000000000 21845 000000101010101010101
65536 65536 000010000000000000000 87381 000010101010101010101
131072 196608 000110000000000000000 174762 000101010101010101010
262144 524288 010000000000000000000 699050 010101010101010101010
524288 786432 011000000000000000000 349525 001010101010101010101
1048576 1048576 100000000000000000000 1398101 101010101010101010101
/**
* Author: Luis Alejandro GonzÃ¡lez Miranda.
*
* Parameters:
* number - The number you want to lookup
* scale - The scale of the number, the total of elements in the curve. The number should be in the range [0 .. scale[
* cx, cy - The returned coordinates in terms of qs (see below)
*/
void hilpoint(long number, long scale, double *cx, double *cy)
{
/* This is a description of the shape of each fundamental pattern */
int patterns[4][4]={{0,1,3,2},{0,2,3,1},{3,1,0,2},{3,2,0,1}};
/* This is a description of what happens to each pattern the next iteration */
int transforms[4][4]={{1,0,2,0},{0,3,1,1},{2,2,0,3},{3,1,3,2}};
/* Quadrant coordinates in pixels; should be initialized to the width
* and height of your arena, which must be square.
* The coordinates will be expressed in numbers in the range [0..qs[
*/
double qs=1.0;
/* This variable should be initialized according to the scale of the
* numbers at the Hilbert curve. We will need to divide by this number,
* and the integer part of the result should be always between 0 and 3.
*
* For example, if you're making a map of Class A IP addresses, your
* range is [0..256[; therefore, the value of divisor is 256/4, or 64;
*/
long divisor=scale/4;
/* A copy of your number */
long tmp=number;
/* The start pattern. Don't modify */
long pattern=1;
(*cx)=(*cy)=0.0;
while(divisor>0) {
int cell;
long mantissa;
mantissa=tmp/divisor;
tmp=tmp%divisor;
divisor/=4;
cell=patterns[pattern][mantissa];
pattern=transforms[pattern][cell];
qs/=2.0;
if(cell & 1) (*cx)+=qs;
if(cell & 2) (*cy)+=qs;
}
}
Cosmologicon wrote:BaldAdonis, I'm trying to implement the algorithm in your post, but I don't understand what you mean by "apply A to x_0", for instance. Does that mean you change the value of y_0 or x_0 or both?
This changes everything! Alternating groups aren't needed, which means the entire half of the new algorithm (if x_2=2,3...) is unnecessary.xkcd wrote:
Boy, is there egg on my face. The last two numbers were indeed wrong (I did this by hand, but that should be no excuse). The last four should read:
32 48
33 50
34 51
35 49
#!/usr/bin/perl
use strict;
for(0..100,31337)
{
my ($bit)=fb($_);
my ($inv)=fbi($bit);
print "$_: $bit: $inv\n";
}
sub fb($)
{
my @table=([0,1,2,3],[0,2,1,3],[3,2,1,0],[3,1,2,0]);
my $n=shift;
if($n==0) { return (0,0) }
elsif($n==1) { return (1,1) }
elsif($n==2) { return (3,1) }
elsif($n==3) { return (2,2) }
else
{
my ($b1,$trans1)=fb($n&3);
my ($b2,$trans2)=fb($n>>2);
return ((($b2<<3)&0xaaaaaaa8)|(($b2<<1)&0x55555554)|$table[$trans2][$b1],$trans1^$trans2);
}
}
sub fbi($)
{
my @table=([0,1,2,3],[0,2,1,3],[3,2,1,0],[3,1,2,0]);
my $n=shift;
if($n==0) { return (0,0) }
elsif($n==1) { return (1,1) }
elsif($n==2) { return (3,2) }
elsif($n==3) { return (2,1) }
else
{
my ($b2,$trans2)=fbi( (($n&0xaaaaaaa8)>>3) | (($n&0x55555554)>>1) );
my ($b1,$trans1)=fbi($table[$trans2][$n&3]);
return (($b2<<2)|$b1,$trans1^$trans2);
}
}
#include <stdio.h>
void f(int n,int *xp,int *yp);
int fi(int x,int y);
int main(int argc,char **argv)
{
for(int i=0;i<102;i++)
{
int x,y;
if(i==101) i=31337;
f(i,&x,&y);
int il=0;
for(int j=0;j<16;j++) il|=( (x<<j)&(1<<(2*j)) )|( (y<<(j+1))&(1<<(2*j+1)) );
printf("%d: %d: %d %s\n",i,il,fi(x,y),i!=fi(x,y)?"!!!":"");
}
return 0;
}
static int transform_table[4][4]={{0,1,2,3},{0,2,1,3},{3,2,1,0},{3,1,2,0}};
static int locations[4]={0,1,3,2};
void f(int n,int *xp,int *yp)
{
static int transforms[4]={1,0,0,3};
int x=0,y=0;
int trans=0;
for(int i=30;i>=0;i-=2)
{
int m=(n>>i)&3;
int bits=transform_table[trans][locations[m]];
x=(x<<1)|((bits>>1)&1);
y=(y<<1)|(bits&1);
trans^=transforms[m];
}
*xp=x; *yp=y;
}
int fi(int x,int y)
{
static int transforms[4]={1,0,3,0};
int n=0;
int trans=0;
for(int i=15;i>=0;i--)
{
int m=transform_table[trans][((y>>i)&1)|(((x>>i)&1)<<1)];
int bits=locations[m];
n=(n<<2)|bits;
trans^=transforms[m];
}
return n;
}
unsigned F (const unsigned N) {
unsigned m = 1, n = N, r = 0, p, a = 0;
while (n >>= 2) ++m, a ^= 1;
while (m)
(r <<= 2) |= (p = ((n = N >> (--m << 1) & 3) > 1) ^ n) ^
3 * (a & p << 1 >> p ^ a >> 1),
a ^= n * (n & 1) ^ (n < 2);
return r;
}
Cosmologicon wrote:
- Code: Select all
unsigned F (const unsigned N) {
unsigned m = 1, n = N, r = 0, p, a = 0;
while (n >>= 2) ++m, a ^= 1;
while (m)
(r <<= 2) |= (p = ((n = N >> (--m << 1) & 3) > 1) ^ n) ^
3 * (a & p << 1 >> p ^ a >> 1),
a ^= n * (n & 1) ^ (n < 2);
return r;
}
unsigned F (const unsigned N) {
unsigned m = 1, n = N, r = 0, a = 0;
while (n>>=2) a=1&m++;
while (m--) r=r*4|(n=N>>m+m&3)^n>>1^3*(((a^=n<3?!n:3)+(n&1)&2)>>1);
return r;
}
unsigned F (const unsigned N) {
unsigned m = 1, n = N, r = 0, a = 0;
while (n >>= 2) ++m, a ^= 1;
while (m--) {
n = N >> (m << 1) & 3;
unsigned d = n ^ n >> 1; // lookup: (0,1,3,2)
if (a & n & 1 ^ a >> 1) d ^= 3;
r = r << 2 | d;
a ^= n * (n & 1) ^ (n < 2); // lookup: (1,0,0,3)
}
return r;
}
#include <stack>
unsigned F (const unsigned N) {
unsigned n = N, r = 0, a = 1;
std::stack<unsigned> s;
do { s.push(n & 3); a ^= 1; } while (n /= 4);
while (!s.empty()) {
n = s.top(); s.pop();
unsigned d = n & 2 ? n ^ 1 : n;
if (a & n & 1 ^ a >> 1) d ^= 3;
r = r * 4 + d;
a ^= n < 3 ? !n : 3;
}
return r;
}
def Hilbert(input, exp, list, result=0, start=0):
posit = [0, 1, 3, 2]
for i in range(len(list)):
if ((start+list[i]*(4**exp)) <= input) & ((start+(list[i]+1)*(4**exp)) > input):
start = start + list[i]*(4**exp)
result = result*4 + posit[i]
if list[i] == 3:
b = list[0]
list[0] = list[2]
list[2] = b
if list[i] == 0:
b = list[1]
list[1] = list[3]
list[3] = b
break
if exp>0:
Hilbert(input, exp-1, list, result, start)
else:
print result
def FindExp(input):
exp = 0
while(4**(exp+1))<=input:exp+=2
return exp
def Hilb(input):
Hilbert(input, FindExp(input), [0, 1, 2, 3])
print "Enter the number to be converted, q to quit, or l to loop"
while True:
i = raw_input("> ")
if i == "q":
break
elif i == "l":
print "Up to what?"
u = int(raw_input("> "))
for x in range(u):
Hilb(x)
else:
i = int(i)
Hilb(i)
Users browsing this forum: Black_Swan and 6 guests