/*
* A160808.c
* Calculates the entries of Sloane's A160808
*
* Created by Nathaniel Johnston (nathaniel@nathanieljohnston.com)
* March 30, 2011
*/

#include <math.h>
#include <stdio.h>


unsigned int prevPts = 2, numPts = 2, pt[268435455];
FILE *file;

unsigned int getCoord (unsigned int pt, unsigned short coord)
{
    unsigned short shift = 14*(coord-1);
    return (pt & (16383*(1 << shift))) >> shift;
}

unsigned char getOrien (unsigned int pt)
{
    return (pt & (1 << 28)) >> 28;
}

unsigned int getPt (unsigned short x, unsigned short y, unsigned short orien)
{
    return x | (y << 14) | (orien << 28);
}

unsigned char addOrien (unsigned short x, unsigned short y, unsigned short orien)
{
    unsigned int j, nn = 0;
    unsigned short px, py, po;
    for(j=0;j<prevPts;j++)
    {
        px = getCoord(pt[j],1);
        py = getCoord(pt[j],2);
        po = getOrien(pt[j]);

        if(po == 1 && ((px == x && py == y+1) || (px == x && py == y-1))){
            if(orien == 1)return 0;nn++;
        }
        else if(po == 0 && ((px == x-1 && py == y) || (px == x+1 && py == y))){
            if(orien == 0)return 0;nn++;
        }
    }
    return (nn == 1);
}

unsigned char isOccupied (unsigned short x, unsigned short y)
{
    unsigned int j;
    for(j=0;j<prevPts;j++)
    {
        if(x == getCoord(pt[j],1) && y == getCoord(pt[j],2))return 1;
    }
    return 0;
}

unsigned int makeSpiral (unsigned short numGens)
{
    unsigned int j, k, f1 = 2, f2 = 2, f3, nfp = 2;
    int lcx = 1, lcy = 1, lco = 1, lcd = 1;
    int totSpir = (int)(3*log(numGens));

    for(j=0;j<totSpir;j++){
        f3 = f1 + f2;
        f1 = f2;f2 = f3;
        for(k=0;k<f1;k++){
            if(lco==0)pt[nfp++] = getPt(8192+lcx + 2*lcd*k,8192+lcy,lco);
            else pt[nfp++] = getPt(8192+lcx,8192+lcy + 2*lcd*k,lco);
            numPts++;
            prevPts++;
        }

        if(lco==0){
            lcx = lcx + lcd*(2*f1-1);
            lcy += lcd;
        }else{
            lcx -= lcd;
            lcy = lcy + lcd*(2*f1-1);
        }
        if(lco==1)lcd*=-1;
        lco = (lco+1) % 2;
    }

    return nfp;
}

int main ()
{
    unsigned short xi, yi, oi, tOr, gen, maxGens;
    unsigned int negPts;
    pt[0] = getPt(8190,8192,0);
    pt[1] = getPt(8192,8192,0);

    printf("This tool will calculate the entries of Sloane's A160808.\nPlease enter the number of terms to compute (an integer from 1 to 8191). Smaller numbers will accelerate even the early computations: ");
    scanf("%d",&maxGens);
    negPts = makeSpiral(maxGens);

    file = fopen("b160808.txt","w");
    fprintf(file,"0 0\n");
    fclose(file);
    printf("0 0\n");

    for(gen=1;gen<=maxGens;gen++){
        for(xi=8189-(int)(gen/2);xi<=8189+(int)(gen/2);xi++){
            for(yi=8192-(int)((gen+1)/2);yi<=8192+(int)((gen+1)/2);yi++){
                tOr = isOccupied(xi,yi);
                for(oi=0;oi<2;oi++){
                    if(!tOr && addOrien(xi,yi,oi))pt[numPts++]=getPt(xi,yi,oi);
                }
            }
        }
        file = fopen("b160808.txt","a");
        fprintf(file,"%d %d\n",gen,numPts-negPts);
        fclose(file);
        printf("%d %d\n",gen,numPts-negPts);
        prevPts = numPts;
    }

    printf("Done!");
    getchar();
    return 0;
}