m1o2 - Permutation - Project Euler 24 projecteuler24

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include <string.h>

#define WaitForResponse { fprintf(stdout,"\n\n Press any key to continue..."); flushall(); getch(); }
#define ErrorMsg( msg ) { fprintf(stderr,"\n\n Error: %s\n",(msg)); fflush(stdout); }
#define PointerAssert( pointer ) { if( (pointer)==NULL){ ErrorMsg("Insufficient Memory"); WaitForResponse; exit(1); }  }
#define IntAtIndex( arr, index ) *((int*)(arr)+(index) )

typedef unsigned long long int Gigantic;
typedef enum { False, True } Bool;
typedef enum { Reverse = -1, Normal = 1 } IteratorMode;

typedef struct Arr{
    void* arr;
    Gigantic length;
    Gigantic top;
}Arr,*Array;

Array newArray(void* arr, Gigantic length, Gigantic top);
Array permutation_n(Array arr, Gigantic n);
void print_array_int(Array arr);
void print_all_permutations(Array arr);
Gigantic factorial( Gigantic n );
Gigantic next_index( Array arr, Gigantic n, IteratorMode mode );
Array reverse_int( Array arr, Array indexer );
void copy_array_int( void* dest, void* source );


int main(){


    int a[] = {0,1,2,3,4,5,6,7,8,9};
    Array arr = newArray(a,10,9);

    //Array p = permutation_n(arr, 1000000 );

    //print_array_int( p );

    //print_all_permutations( arr );
    Array p = permutation_n(arr, 123456 );
    print_array_int( p );

    free( p->arr);
    free( p );

free( arr );

WaitForResponse;
return 0;
}



Array permutation_n(Array arr, Gigantic n){

    Array temp = newArray(calloc(arr->top+1,sizeof(int)),arr->top+1,arr->top);
    Array permutation = newArray(calloc(arr->top+1,sizeof(int)),arr->length,arr->top);
    Gigantic index;

    PointerAssert( temp->arr );

    for( index = 1; n >= 1 ; ++index ){

        Gigantic fact = factorial(arr->top-(index-1));
        Gigantic div;
        Gigantic mod;

        div = n / fact;
        mod = n % fact;

        if( mod == 0 ){
            Gigantic tempIndex = next_index(temp,div,Normal);
            Array reversed;

            IntAtIndex(permutation->arr,index-1) = IntAtIndex(arr->arr, tempIndex );
            IntAtIndex(temp->arr,tempIndex) = 1;

            reversed = reverse_int(arr,temp);
            copy_array_int((((int*)permutation->arr)+index),reversed->arr,reversed->length);

            free( reversed );

            return permutation;
        }
        else if( fact == 1 ){

            Gigantic nextIndex = next_index(temp, 1, Normal ),test1;

            test1 = IntAtIndex(arr->arr,nextIndex);
            IntAtIndex(permutation->arr,index-1) = IntAtIndex(arr->arr,nextIndex);
            IntAtIndex(temp->arr,nextIndex) = 1;

            nextIndex = next_index(temp, 1, Normal );
            test1 = IntAtIndex(arr->arr,nextIndex);
            IntAtIndex(permutation->arr, index-1) = IntAtIndex(arr->arr, nextIndex);
            IntAtIndex(temp->arr,nextIndex) = 1;



            return permutation;
        }
        else{
            Gigantic tempIndex = next_index(temp, div+1, Normal );
            n = mod;

            IntAtIndex(permutation->arr,index-1) = IntAtIndex(arr->arr, tempIndex);

            IntAtIndex(temp->arr, tempIndex) = 1;

        }
    }

    free( temp->arr );
    free( temp );

    return permutation;
}

Gigantic next_index( Array arr, Gigantic n, IteratorMode mode ){    ///
    Gigantic index = (( mode == Normal )?(0):(arr->top)),counter = 0;
    Gigantic till = 0;

    for( ; till <= arr->top && counter < n; index += mode , ++till )
        if( IntAtIndex( arr->arr, index ) == 0 && ++counter == n )
            return index;

    return -1;
}

Array reverse_int( Array arr, Array indexer ){ //

    Gigantic count, index,temp;
    Array newArr;

    for(index = count = 0; index <= arr->top; ++index)
        if( IntAtIndex(indexer->arr, index ) == 0 )
            ++count;

    newArr = newArray(malloc(sizeof(count)),count,count-1);

    for( index = temp = 0; temp < count; ++index )
        if( IntAtIndex(indexer->arr, arr->top-index) == 0 ){
            IntAtIndex(newArr->arr,temp) = IntAtIndex(arr->arr, arr->top-index);
            ++temp;
        }

    return newArr;
}

void copy_array_int( void* dest, void* source,  Gigantic length){  //

    while( length-- > 0 )
        IntAtIndex( dest,length ) = IntAtIndex( source, length );

}

Array newArray(void* arr, Gigantic length, Gigantic top){ //

    Array newArr = (Array)malloc(sizeof(Arr));
    PointerAssert( newArray );

    newArr->arr = (int*)arr;
    newArr->length = length;
    newArr->top = top;

    return newArr;
}


void print_array_int(Array arr){  //

    Gigantic index;

    for( index = 0; index <= arr->top; ++index)
        fprintf(stdout,"%d",IntAtIndex(arr->arr,index) );

}

void print_all_permutations(Array arr){
    Gigantic index,fact = factorial(arr->top+1);

    for( index = 1; index <= fact; ++index){
        Array temp = permutation_n(arr,index);
        print_array_int( temp );
        putchar('\n');
        free( temp );
    }
}

Gigantic factorial( Gigantic n ){  //
    Gigantic result = 1,index=0;

    for( ; n > 1; ++index)
        result *= n--;

    return result;
}