Rabbitgaming's code guessing stats

dir export

false.c ASCII text

/*
USAGE after compiling:
./false <filename> [input]
like ./false cat.false "Hello World"

Exit codes:
0 - success
1 - No file specified
2 - Memory error (Couldn't realloc(...))
3 - Unknown tokentype
4 - Invoked undefined behaviour
5 - Coudln't open specified file
*/

#include <stdio.h> 
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#include "tokenstack.h"
#include "stringlib.h"
#include "utils.h"
#include "token.h"

#define current_char checkChar(string_cstr(instructions)[current])

typedef struct program{
    stack_t* stck;
    token_t** variables;
    string_t* input;
    bool* initialized_vars;
} program_t;


char checkChar(char c){
    if(!((9 <= c && c <= 10) || (32 <= c && c <= 126))){
        printf("\nUNDEFINED BEHAVIOUR - char '%c' out of valid range", c);
        exit(4);
    }
    return c;
}

char eat_char_from_input(string_t* input){
    if(string_get_size(input) == 0){
        printf("\nUNDEFINED BEHAVIOUR - Trying to get char from input while being empty - Exiting...\n");
        exit(4);
    }
    const char inp = string_cstr(input)[0];
    string_erase(input, 0, 1);
    return checkChar(inp);
}

void run_quote(string_t* instructions, program_t* context){
    unsigned long long current = 0;
    const unsigned long long instructions_size = string_get_size(instructions);
    string_t* buffer = string_new();
    while(current < instructions_size){
        switch(current_char){
            case '{':
                {
                    char symbol = string_cstr(instructions)[current];
                    while(symbol != '}' && ++current < instructions_size){
                        symbol = current_char;
                    }
                    if(current==instructions_size){
                        printf("UNDEFINED BEHAVIOUR - Comment was never closed - Exiting...\n");
                        exit(4);
                    }
                    ++current;
                }
                break;

            case '0':
            case '1':
            case '2':
            case '3':
            case '4':
            case '5':
            case '6':
            case '7':
            case '8':
            case '9':
                {
                    char symbol = current_char;
                    do
                    {
                        string_append_char(buffer, symbol);
                        if(++current >= instructions_size){
                            break;
                        }
                        symbol = current_char;
                    } while ('0' <= symbol && symbol <= '9');
                    stack_push(context->stck, token_new_int(strtol(string_cstr(buffer), NULL, 10)));
                    string_clear(buffer);
                }
                break;

            case '\'':
                ++current;
                stack_push(context->stck, token_new_int(current_char));
                ++current;
                break;
            
            case '"':
                {
                    ++current;
                    if (current >= instructions_size){
                        printf("\nUNDEFINED BEHAVIOUR - String never closed - Exiting...\n");
                        exit(4);
                    }
                    
                    char symbol = current_char;
                    do{
                        string_append_char(buffer, symbol);
                        if (++current >= instructions_size){
                            printf("\nUNDEFINED BEHAVIOUR - Quote never closed - Exiting...\n");
                            exit(4);
                        }
                        symbol = current_char;
                    } while (symbol != '"');
                    printf("%s", string_cstr(buffer));
                    string_clear(buffer);
                    ++current;

                }
                break;

            case '[':
                {
                    ++current;
                    if (current >= instructions_size){
                        printf("\nUNDEFINED BEHAVIOUR - Quote never closed - Exiting...\n");
                        exit(4);
                    }
                    char symbol = current_char;
                    unsigned long long open_bracket_count = current_char != '[' ? 1 : 2;
                    do
                    {
                        string_append_char(buffer, symbol);
                        if (++current >= instructions_size){
                            printf("\nUNDEFINED BEHAVIOUR - Quote never closed - Exiting...\n");
                            exit(4);
                        }
                        symbol = current_char;
                        if(symbol == '['){
                            ++open_bracket_count;
                        }
                        else if(symbol == ']'){
                            --open_bracket_count;
                        }


                    } while (symbol != ']' || open_bracket_count > 0);
                    stack_push(context->stck, token_new_quote(string_copy(buffer)));
                    string_clear(buffer);
                    ++current;
                }
                break;
            
            case 'a':
            case 'b':
            case 'c':
            case 'd':
            case 'e':
            case 'f':
            case 'g':
            case 'h':
            case 'i':
            case 'j':
            case 'k':
            case 'l':
            case 'm':
            case 'n':
            case 'o':
            case 'p':
            case 'q':
            case 'r':
            case 's':
            case 't':
            case 'u':
            case 'v':
            case 'w':
            case 'x':
            case 'y':
            case 'z':
                stack_push(context->stck, token_new_reference(current_char));
                ++current;
                break;

            case ';':
                {
                    token_t* reference = stack_pop(context->stck);
                    if(reference->type != REFERENCE){
                        printf("\nUNDEFINED BEHAVIOUR - Pop'd object is not a Reference - Exiting...\n");
                        exit(4);
                    }
                    if(!context->initialized_vars[reference->value_r-'a']){
                        printf("\nUNDEFINED BEHAVIOUR - Reference '%c' is not initialized - Exiting...\n", reference->value_r);
                        exit(4);
                    }
                    token_t* new_tok = token_copy(context->variables[reference->value_r-'a']);
                    stack_push(context->stck, new_tok);
                    token_free(reference);
                    ++current;
                }
                break;

            case ':':
                {
                    token_t* reference = stack_pop(context->stck);
                    if(reference->type != REFERENCE){
                        printf("\nUNDEFINED BEHAVIOUR - Pop'd object is not a Reference - Exiting...\n");
                        exit(4);
                    }
                    if(context->initialized_vars[reference->value_r-'a']){
                        token_full_free(context->variables[reference->value_r-'a']);
                    }
                    context->variables[reference->value_r-'a'] = stack_pop(context->stck);
                    context->initialized_vars[reference->value_r-'a'] = true;
                    token_free(reference);
                    current++;
                }
                break;

            case '$':
                stack_push(context->stck, token_copy(stack_raccess(context->stck, 0)));
                ++current;
                break;

            case '%':
                token_full_free(stack_pop(context->stck));
                ++current;
                break;
            
            case '\\':
                {
                    token_t* first = stack_pop(context->stck);
                    token_t* second = stack_pop(context->stck);
                    stack_push(context->stck, first);
                    stack_push(context->stck, second);
                    ++current;
                }
                break;
            
            case '@':
                {
                    token_t* first = stack_pop(context->stck);
                    token_t* second = stack_pop(context->stck);
                    token_t* third = stack_pop(context->stck);
                    stack_push(context->stck, second);
                    stack_push(context->stck, first);
                    stack_push(context->stck, third);
                    ++current;
                }
                break;
            
            case 'O':
                {
                    token_t* index = stack_pop(context->stck);
                    if(index->type != INTEGER){
                        printf("\nUNDEFINED BEHAVIOUR - Pop'd object is not an Integer - Exiting...\n");
                        exit(4);
                    }
                    stack_push(context->stck, token_copy(stack_raccess(context->stck, index->value_i)));
                    token_free(index);
                    ++current;
                }
                break;
            
            case '+':
                {
                    token_t* first = stack_pop(context->stck);
                    if(first->type != INTEGER){
                        printf("\nUNDEFINED BEHAVIOUR - Pop'd object is not an Integer - Exiting...\n");
                        exit(4);
                    }
                    token_t* second = stack_pop(context->stck);
                    if(second->type != INTEGER){
                        printf("\nUNDEFINED BEHAVIOUR - Pop'd object is not an Integer - Exiting...\n");
                        exit(4);
                    }
                    stack_push(context->stck, token_new_int(first->value_i + second->value_i));
                    token_free(first);
                    token_free(second);
                    ++current;
                }
                break;
            
            case '-':
                {
                    token_t* subtrahend = stack_pop(context->stck);
                    if(subtrahend->type != INTEGER){
                        printf("\nUNDEFINED BEHAVIOUR - Pop'd object is not an Integer - Exiting...\n");
                        exit(4);
                    }
                    token_t* minuend = stack_pop(context->stck);
                    if(minuend->type != INTEGER){
                        printf("\nUNDEFINED BEHAVIOUR - Pop'd object is not an Integer - Exiting...\n");
                        exit(4);
                    }
                    stack_push(context->stck, token_new_int(minuend->value_i - subtrahend->value_i));
                    token_free(subtrahend);
                    token_free(minuend);
                    ++current;
                }
                break;

            case '*':
                {
                    token_t* first = stack_pop(context->stck);
                    if(first->type != INTEGER){
                        printf("\nUNDEFINED BEHAVIOUR - Pop'd object is not an Integer - Exiting...\n");
                        exit(4);
                    }
                    token_t* second = stack_pop(context->stck);
                    if(second->type != INTEGER){
                        printf("\nUNDEFINED BEHAVIOUR - Pop'd object is not an Integer - Exiting...\n");
                        exit(4);
                    }
                    stack_push(context->stck, token_new_int(first->value_i * second->value_i));
                    token_free(first);
                    token_free(second);
                    ++current;
                }
                break;
            
            case '/':
                {
                    token_t* divisor = stack_pop(context->stck);
                    if(divisor->type != INTEGER){
                        printf("\nUNDEFINED BEHAVIOUR - Pop'd object is not an Integer - Exiting...\n");
                        exit(4);
                    }
                    token_t* dividend = stack_pop(context->stck);
                    if(dividend->type != INTEGER){
                        printf("\nUNDEFINED BEHAVIOUR - Pop'd object is not an Integer - Exiting...\n");
                        exit(4);
                    }
                    stack_push(context->stck, token_new_int(dividend->value_i / divisor->value_i));
                    token_free(divisor);
                    token_free(dividend);
                    ++current;
                }
                break;
            
            case '_':
                {
                    token_t* value = stack_pop(context->stck);
                    if(value->type != INTEGER){
                        printf("\nUNDEFINED BEHAVIOUR - Pop'd object is not an Integer - Exiting...\n");
                        exit(4);
                    }
                    stack_push(context->stck, token_new_int(-(value->value_i)));
                    token_free(value);
                    ++current;
                }
                break;
            
            case '&':
                {
                    token_t* first = stack_pop(context->stck);
                    if(first->type != INTEGER){
                        printf("\nUNDEFINED BEHAVIOUR - Pop'd object is not an Integer - Exiting...\n");
                        exit(4);
                    }
                    token_t* second = stack_pop(context->stck);
                    if(second->type != INTEGER){
                        printf("\nUNDEFINED BEHAVIOUR - Pop'd object is not an Integer - Exiting...\n");
                        exit(4);
                    }
                    stack_push(context->stck, token_new_int(first->value_i & second->value_i));
                    token_free(first);
                    token_free(second);
                    ++current;
                }
                break;
            
            case '|':
                {
                    token_t* first = stack_pop(context->stck);
                    if(first->type != INTEGER){
                        printf("\nUNDEFINED BEHAVIOUR - Pop'd object is not an Integer - Exiting...\n");
                        exit(4);
                    }
                    token_t* second = stack_pop(context->stck);
                    if(second->type != INTEGER){
                        printf("\nUNDEFINED BEHAVIOUR - Pop'd object is not an Integer - Exiting...\n");
                        exit(4);
                    }
                    stack_push(context->stck, token_new_int(first->value_i | second->value_i));
                    token_free(first);
                    token_free(second);
                    ++current;
                }
                break;

            case '~':
                {
                    token_t* value = stack_pop(context->stck);
                    if(value->type != INTEGER){
                        printf("\nUNDEFINED BEHAVIOUR - Pop'd object is not an Integer - Exiting...\n");
                        exit(4);
                    }
                    stack_push(context->stck, token_new_int(~(value->value_i)));
                    token_free(value);
                    ++current;
                }
                break;

            case '=':
                {
                    token_t* first = stack_pop(context->stck);
                    if(first->type != INTEGER){
                        printf("\nUNDEFINED BEHAVIOUR - Pop'd object is not an Integer - Exiting...\n");
                        exit(4);
                    }
                    token_t* second = stack_pop(context->stck);
                    if(second->type != INTEGER){
                        printf("\nUNDEFINED BEHAVIOUR - Pop'd object is not an Integer - Exiting...\n");
                        exit(4);
                    }
                    stack_push(context->stck, token_new_int(first->value_i == second->value_i ? -1 : 0));
                    token_free(first);
                    token_free(second);
                    ++current;
                }
                break;
            
            case '>':
                {
                    token_t* first = stack_pop(context->stck);
                    if(first->type != INTEGER){
                        printf("\nUNDEFINED BEHAVIOUR - Pop'd object is not an Integer - Exiting...\n");
                        exit(4);
                    }
                    token_t* second = stack_pop(context->stck);
                    if(second->type != INTEGER){
                        printf("\nUNDEFINED BEHAVIOUR - Pop'd object is not an Integer - Exiting...\n");
                        exit(4);
                    }
                    stack_push(context->stck, token_new_int(second->value_i > first->value_i ? -1 : 0));
                    token_free(first);
                    token_free(second);
                    ++current;
                }
                break;

            case '!':
                {
                    token_t* quote = stack_pop(context->stck);
                    if(quote->type != QUOTE){
                        printf("\nUNDEFINED BEHAVIOUR - Pop'd object is not a Quote - Exiting...\n");
                        exit(4);
                    }
                    run_quote(quote->value_q, context);
                    token_full_free(quote);
                    ++current;
                }
                break;
            
            case '?':
                {
                    token_t* quote = stack_pop(context->stck);
                    if(quote->type != QUOTE){
                        printf("\nUNDEFINED BEHAVIOUR - Pop'd object is not a Quote - Exiting...\n");
                        exit(4);
                    }
                    token_t* condition = stack_pop(context->stck);
                    if(condition->type != INTEGER){
                        printf("\nUNDEFINED BEHAVIOUR - Pop'd object is not an Integer - Exiting...\n");
                        exit(4);
                    }
                    if(condition->value_i != 0){
                        run_quote(quote->value_q, context);
                    }
                    token_full_free(quote);
                    token_free(condition);
                    ++current;
                }
                break;
            
            case '#':
                {
                    token_t* body = stack_pop(context->stck);
                    if(body->type != QUOTE){
                        printf("\nUNDEFINED BEHAVIOUR - Pop'd object is not a Quote - Exiting...\n");
                        exit(4);
                    }
                    token_t* condition = stack_pop(context->stck);
                    if(condition->type != QUOTE){
                        printf("\nUNDEFINED BEHAVIOUR - Pop'd object is not a Quote - Exiting...\n");
                        exit(4);
                    }
                    while(true){
                        run_quote(condition->value_q, context);
                        token_t* evaluated_condition = stack_pop(context->stck);
                        if(evaluated_condition->type != INTEGER){
                            printf("\nUNDEFINED BEHAVIOUR - Pop'd object is not an Integer - Exiting...\n");
                            exit(4);
                        }
                        if(evaluated_condition->value_i == 0){
                            token_free(evaluated_condition);
                            break;
                        }
                        token_free(evaluated_condition);
                        run_quote(body->value_q, context);
                    }
                    token_full_free(body);
                    token_full_free(condition);

                    ++current;
                }
                break;
            
            case '^':
                if(string_get_size(context->input)==0){
                    stack_push(context->stck, token_new_int(-1));
                }
                else{
                    stack_push(context->stck, token_new_int(eat_char_from_input(context->input)));
                }
                ++current;
                break;
            
            case ',':
                {
                    token_t* c = stack_pop(context->stck);
                    if(c->type != INTEGER){
                        printf("\nUNDEFINED BEHAVIOUR - Pop'd object is not an Integer - Exiting...\n");
                        exit(4);
                    }
                    printf("%c", c->value_i);
                    token_free(c);
                    ++current;
                }
                break;

            case '.':
                {
                    token_t* c = stack_pop(context->stck);
                    if(c->type != INTEGER){
                        printf("\nUNDEFINED BEHAVIOUR - Pop'd object is not an Integer - Exiting...\n");
                        exit(4);
                    }
                    printf("%d", c->value_i);
                    token_free(c);
                    ++current;
                }
                break;

            case 'B':
                fflush(stdout);
                ++current;
                break;
            
            case '`':
                printf("\nUNDEFINED BEHAVIOUR - ` only does undefined behaviour - Exiting... \n");
                exit(4);
                break;

            default:
                switch(current_char){
                    case ' ':
                    case '\t':
                    case '\n':
                        ++current;
                        break;
                    default:
                        printf("\nUNDEFINED BEHAVIOUR - Unknown instruction '%c' - Exiting...\n", current_char);
                        exit(4);
                }
        }
    }
    string_free(buffer);
    return;
}

int main(int argc, char const *argv[])
{
    if(argc == 1){
        printf("No file specified\n");
        exit(1);
    }
    const char* filename = argv[1];    
    string_t* input = string_new();
    if(argc > 2){
        string_append_chars(input, argv[2]);
    }

    FILE* file = fopen(filename, "r");
    if(file == NULL){
        string_free(input);
        printf("Couldn't open file \"%s\"\n", filename);
        exit(5);
    }

    fseek(file, 0, SEEK_END);
    unsigned long long filesize = ftell(file);
    rewind(file);
    char* filecontent = malloc((filesize+1)*sizeof(char));
    fread(filecontent, filesize, 1, file); 
    filecontent[filesize] = '\0';
    string_t* instructions = string_from_chars(filecontent);
    free(filecontent);
    fclose(file);

    stack_t* stck = stack_new();
    token_t* variables[26];
    bool initialized_vars[26] = {0};
    
    program_t* context = malloc(sizeof(program_t));
    context->stck = stck;
    context->variables = variables;
    context->input = input;
    context->initialized_vars = initialized_vars;

    run_quote(instructions, context);

    string_free(instructions);
    stack_free(stck);
    string_free(input);
    for(int i = 0; i < 26; ++i){
        if(initialized_vars[i]){
            token_full_free(variables[i]);
        }
    }
    free(context);
}

stringlib.c ASCII text

#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#include <stdio.h>
#include "stringlib.h"
#include "utils.h"



typedef struct string{
    char* str;
    unsigned long long size;
    unsigned long long capacity;
} string_t;


string_t* string_new(){
    char* empty_string = (char*) malloc(MIN_STRING_CAPACITY*sizeof(char));
    string_t* new_str = malloc(sizeof(string_t));
    new_str->str = empty_string;
    new_str->size = 0;
    new_str->capacity = MIN_STRING_CAPACITY;
    return new_str;
}

string_t* string_from_chars(const char* str){
    const unsigned long long length = strlen(str);
    const unsigned long long capacity = umax(next_power_of_2(length), MIN_STRING_CAPACITY);
    char* new_chars = malloc(capacity*sizeof(char));
    strncpy(new_chars, str, capacity);
    string_t* new_str = malloc(sizeof(string_t));
    new_str->str = new_chars;
    new_str->size = length;
    new_str->capacity = capacity;
    return new_str;
}

char* string_cpy_to_chars(const string_t* str){
    char* new_chars = malloc(((str->size)+1)*sizeof(char));
    for(unsigned long long i = 0; i < str->size; ++i){
        new_chars[i] = str->str[i];
    }
    new_chars[str->size] = '\0';

    return new_chars;
}

string_t* string_copy(const string_t* str){
    string_t* new_str = string_new();
    char* chars = malloc((str->capacity)*sizeof(char));
    for(unsigned long long i = 0; i < str->size; ++i){
        chars[i] = str->str[i];
    }
    new_str->str = chars;
    new_str->capacity = str->capacity;
    new_str->size = str->size;
    return new_str;
}

const char* string_cstr(string_t* str){
    string_set_min_capacity(str, str->size+1);
    str->str[str->size] = '\0';
    return str->str;
}

unsigned long long string_get_size(const string_t* str){
    return str->size;
}

unsigned long long string_get_capacity(const string_t* str){
    return str->capacity;
}

void string_set_min_capacity(string_t* str, const unsigned long long size){
    if(size > str->capacity){
        char* new_str = realloc(str->str, size*sizeof(char));
        if(new_str==NULL){
            exit(2);
        }
        str->str = new_str;
        str->capacity = size;    
    }
    return;
}

void string_append(string_t* dest, const string_t* source){
    const unsigned long long dest_size = dest->size;
    const unsigned long long source_size = source->size;
    string_set_min_capacity(dest, umax(next_power_of_2(dest_size+source_size), MIN_STRING_CAPACITY));
    for(unsigned long long i = 0; i < source_size; ++i){
        dest->str[dest_size+i] = source->str[i];
    }
    dest->size = dest_size+source_size;
    return;
}

void string_append_char(string_t* dest, const char c){
    const unsigned long long size = dest->size;
    string_set_min_capacity(dest, umax(next_power_of_2(size+1), MIN_STRING_CAPACITY));
    dest->str[size] = c;
    dest->size = size+1;
    return;
}

void string_append_chars(string_t* dest, const char* source){
    string_t* temp = string_from_chars(source);
    string_append(dest, temp);
    string_free(temp);
    return;
}

void string_print(const string_t* str){
    for(unsigned long long i = 0; i < str->size; ++i){
        printf("%c", str->str[i]);
    }
    return;
}

string_t* string_substr(const string_t* str, const unsigned long long position, const unsigned long long length){
    string_t* new_str = string_new();
    if(position >= str->size){
        return new_str;
    }
    unsigned long long actual_size = min(length, str->size - position);
    string_set_min_capacity(new_str, umax(next_power_of_2(actual_size), MIN_STRING_CAPACITY));
    for(unsigned long long i = 0; i < actual_size; ++i){
        new_str->str[i] = str->str[position+i];
    }
    new_str->size = actual_size;
    return new_str;
}

void string_erase(string_t* str, const unsigned long long position, const unsigned long long length){
    if(position >= str->size){
        return;
    }
    unsigned long long actual_size = min(length, str->size - position);
    char* cpy = string_cpy_to_chars(str);

    for(unsigned long long i = 0; i < position; ++i){
        str->str[i] = cpy[i];
    }
    for(unsigned long long i = position + actual_size; i < str->size; ++i){
        str->str[i-actual_size] = cpy[i];
    }
    str->size -= actual_size;
    free(cpy);
    return;
}

void string_clear(string_t* str){
    str->size = 0;
}

void string_free(string_t* str){
    //According to valgrind strings made from string_copy aren't free'd correctly, but everything I tested seemed like it free'd correctly. Must be a valgrind bug...
    free(str->str);
    free(str);
    return;
}

stringlib.h ASCII text

#ifndef H_STRINGLIB

#define H_STRINGLIB

#define MIN_STRING_CAPACITY 64

typedef struct string string_t;

string_t* string_new();

string_t* string_from_chars(const char* str);

char* string_cpy_to_chars(const string_t* str);

string_t* string_copy(const string_t* str);

const char* string_cstr(string_t* str);

unsigned long long string_get_size(const string_t* str);

unsigned long long string_get_capacity(const string_t* str);

void string_set_min_capacity(string_t* str, const unsigned long long size);

void string_append(string_t* dest, const string_t* source);

void string_append_char(string_t* dest, const char c);

void string_append_chars(string_t* dest, const char* source);

void string_print(const string_t* str);

string_t* string_substr(const string_t* str, const unsigned long long position, const unsigned long long length);

void string_clear(string_t* str);

void string_erase(string_t* str, const unsigned long long position, const unsigned long long length);

void string_free(string_t* str);

#endif

token.c ASCII text

#include <stdlib.h>
#include <stdio.h>
#include "token.h"

token_t* token_new_int(int32_t value){
    token_t* new_token = malloc(sizeof(token_t));
    new_token->type = INTEGER;
    new_token->value_i = value;
    return new_token;
}

token_t* token_new_quote(string_t* value){
    token_t* new_token = malloc(sizeof(token_t));
    new_token->type = QUOTE;
    new_token->value_q = value;
    return new_token;
}

token_t* token_new_reference(char value){
    token_t* new_token = malloc(sizeof(token_t));
    new_token->type = REFERENCE;
    new_token->value_r = value;
    return new_token;
}

token_t* token_copy(token_t* tok){
    token_t* new_token = malloc(sizeof(token_t));
    int type = tok->type;
    new_token->type = type;
    switch(type){
        case INTEGER:
            new_token->value_i = tok->value_i;
            break;
        case REFERENCE:
            new_token->value_r = tok->value_r;
            break;
        case QUOTE:
            new_token->value_q = string_copy(tok->value_q);
            break;
        default:
            exit(3);
    }
    return new_token;
}

void token_print(const token_t* tok){
    switch(tok->type){
        case INTEGER:
            printf("INTEGER[%d]", tok->value_i);
            break;
        case QUOTE:
            printf("QUOTE[\"%s\"]", string_cstr(tok->value_q));
            break;
        case REFERENCE:
            printf("REFERENCE['%c']", tok->value_r);
            break;
        default:
            (void)0;
    }
    return;
}

void token_full_free(token_t* tok){
    if(tok->type == QUOTE){
        string_free(tok->value_q);
    }
    free(tok);
}

void token_free(token_t* tok){
    free(tok);
}

token.h ASCII text

#ifndef H_TOKEN

#define H_TOKEN
#include <stdint.h>
#include "stringlib.h"


#define INTEGER 0
#define QUOTE 1
#define REFERENCE 2

typedef struct token
{
    int type;
    union{
        int32_t value_i;
        string_t* value_q;
        char value_r;
    };
} token_t;

token_t* token_new_int(int32_t value);

token_t* token_new_quote(string_t* value);

token_t* token_new_reference(char value);

token_t* token_copy(token_t* tok);

void token_print(const token_t* tok);

void token_full_free(token_t* tok);

void token_free(token_t* tok);

#endif

tokenstack.c ASCII text

#include <stdlib.h>
#include <stdio.h>
#include "token.h"
#include "tokenstack.h"
#include "utils.h"

typedef struct stack{
    token_t** tokens;
    unsigned long long size;
    unsigned long long capacity;
} stack_t;

stack_t* stack_new(){
    stack_t* new_stack = malloc(sizeof(stack_t));
    new_stack->tokens = malloc(MIN_STACK_CAPACITY*sizeof(token_t));
    new_stack->size = 0;
    new_stack->capacity = MIN_STACK_CAPACITY;
    return new_stack;
}

token_t** stack_get_raw(const stack_t* stck){
    return stck->tokens;
}

unsigned long long stack_get_size(const stack_t* stck){
    return stck->size;
}

unsigned long long stack_get_capacity(const stack_t* stck){
    return stck->capacity;
}

void stack_set_min_capacity(stack_t* stck, const unsigned long long size){
    if(size > stck->capacity){
        token_t** new_tokens = realloc(stck->tokens, size*(sizeof(size_t*)));
        if(new_tokens==NULL){
            exit(2);
        }
        stck->tokens = new_tokens;
        stck->capacity = size;
    }
    return;
}

void stack_push(stack_t* stck, token_t* tok){
    const unsigned long long size = stck->size;
    stack_set_min_capacity(stck, umax(next_power_of_2(size+1), MIN_STACK_CAPACITY));
    stck->tokens[size] = tok;
    stck->size = size+1;
    return;
}

token_t* stack_pop(stack_t* stck){
    if(stck->size == 0){
        printf("\nUNDEFINED BEHAVIOUR - Stack has been pop'd while being empty - Exiting...\n");
        exit(4);
    }
    stck->size = stck->size-1;
    return stck->tokens[stck->size];
}

token_t* stack_access(stack_t* stck, const unsigned long long index){
    if(index >= stck->size){
        printf("\nUNDEFINED BEHAVIOUR - Stack access out of bounds (stacksize: %llu, index: %llu) - Exiting...\n", stck->size, index);
        exit(4);
    }
    return stck->tokens[index];
}

token_t* stack_raccess(stack_t* stck, const unsigned long long index){
    if(index >= stck->size){
        printf("\nUNDEFINED BEHAVIOUR - Stack raccess out of bounds (stacksize: %llu, index: %llu) - Exiting...\n", stck->size, index);
        exit(4);
    }
    return stck->tokens[stck->size - 1 - index];
}

void stack_print(const stack_t* stck){
    printf("[");
    for(unsigned long long i = 0; i < stck->size; ++i){
        token_print(stck->tokens[i]);
        printf(", ");
    }
    printf("]");
    return;
}

void stack_free(stack_t* stck){
    for(unsigned long long i = 0; i < stck->size; ++i){
        token_full_free(stck->tokens[i]);
    }
    free(stck->tokens);
    free(stck);
    return;
}

tokenstack.h ASCII text

#ifndef H_TOKENSTACK

#define H_TOKENSTACK

#include "token.h"
#define MIN_STACK_CAPACITY 64

typedef struct stack stack_t;

stack_t* stack_new();

token_t** stack_get_raw(const stack_t* stck);

unsigned long long stack_get_size(const stack_t* stck);

unsigned long long stack_get_capacity(const stack_t* stck);

void stack_set_min_capacity(stack_t* stck, const unsigned long long size);

void stack_push(stack_t* stck, token_t* tok);

token_t* stack_pop(stack_t* stck);

token_t* stack_access(stack_t* stck, const unsigned long long index);

token_t* stack_raccess(stack_t* stck, const unsigned long long index);

void stack_print(const stack_t* stck);

void stack_free(stack_t* stck);
#endif

utils.c ASCII text

#include <math.h>
#include "utils.h"

long long min(long long value1, long long value2){
    if(value2 >= value1){
        return value1;
    }
    else{
        return value2;
    }
}

unsigned long long umin(unsigned long long value1, unsigned long long value2){
    if(value2 >= value1){
        return value1;
    }
    else{
        return value2;
    }
}

long long max(long long value1, long long value2){
    if(value2 > value1){
        return value2;
    }
    else{
        return value1;
    }
}

unsigned long long umax(unsigned long long value1, unsigned long long value2){
    if(value2 > value1){
        return value2;
    }
    else{
        return value1;
    }
}

unsigned long long next_power_of_2(unsigned long long num){
    return powl(2, ceill(log2l(num)));
}

utils.h ASCII text

#ifndef H_UTILS
#define H_UTILS

long long min(long long value1, long long value2);
unsigned long long umin(unsigned long long value1, unsigned long long value2);

long long max(long long value1, long long value2);
unsigned long long umax(unsigned long long value1, unsigned long long value2);

unsigned long long next_power_of_2(unsigned long long num);

#endif

/*
****************************
*NOT A COPYRIGHT DISCLAIMER*
****************************
Soooooooo, you came here to look at my solver?
Well my solver, will not implement smart tactics, instead, it will use randomness and lots and lots of threads.
If you don't want Threads to run, comment following line: (or rather the line following the following line, because of the STAR SLASH)
*/
#define WITH_THREADS
/*
Don't worry, there's a maximum number of threads. First of all, my program analyses how "useful" new threads are,
and if a certain ratio is above a threshhold, it stops creating new threads. But how does it know when to stop creating threads?
Well in the below ThreadPool class, there's an static m_for_analysis array, which size is the maximum number of threads
and zero-initialized. Every newly created thread get's an id, which it can use to increment an entry of m_for_analysis like this:
++m_for_analysis[m_id]
The static array get's copied into the analyzing portion of solve() (yeah I know the source array get's modified while copying but idc),
The ratio is formed but dividing an older copy of m_for_analysis by the new m_for_analysis copy.
If the result is above a certein threshhold, it will stop creating new threads?
What is this magic ratio? it's this:
*/
constexpr long double RATIO_THRESHOLD = 5e-06;
/*
You can even change it if you wanna play around with the ratios.
There's also an absolute maxiumum of threads, even if the ratio threshold isn't reached yet.
My computer with a quad core 11th Gen Intel Core i5-1135G7 starts seriously lagging at 200 threads,
therefore I set the maximum number of threads to 200.
If you want to modify the max amount of threads, modify the line below:
*/
constexpr int MAX_THREADS = 200;
/*
Well, what's the API? It's-
Todays code has been sponsored by INCLUDE, you can include code like this with INCLUDE:
*/
#include <chrono>
#include <array>
#include <string>
#include <iostream>
#include <utility>
#include <set>
#include <vector>
#include <thread>
#include <cstdlib>
#include <mutex>
#include <random>
//The first 100 get a free
using namespace std::chrono_literals;
/*
Buy now. Sponsorship over.
Where was I? ah yes the API is
*/
std::string solve(std::array<std::array<int, 4>, 4>);
/*
Pretty selfexplainable, I hope. It accepts an array of arrays, and returns a std::string of char-sequences consisting of
U for MOVE UP
R for MOVE RIGHT
D for MOVE DOWN
and
L for MOVE LEFT
That's all, I kinda commented my code, I hope you figure the rest out, as long as you don't figure out who wrote this
(probably obvious for some of you)
Just remember, it uses randomness, so it will eventually solve it, but with many Moves required it probably won't finish
solving within the lifetime of the universe. bb
*/

//Utility function to print out an array
void print_array(std::array<int, 4> const& arr){
    std::cout << "arr[";
    for(int i = 0; i < 4; ++i){
        std::cout << arr[i] << ", ";
    }
    std::cout << "]\n";
}

namespace DIRECTIONS{
    enum Directions{
        UP,
        RIGHT,
        DOWN,
        LEFT
    };
}

void rotate(std::array<int, 4>& array, DIRECTIONS::Directions direction = DIRECTIONS::RIGHT, int amount = 1){
    amount = amount % 4;
    std::array<int, 4> buffer{0, 0, 0, 0};
    for(int repeat = 0; repeat < amount; ++repeat){
        switch(direction){
            case DIRECTIONS::RIGHT:
                buffer[0] = array[3];
                for(int i = 0; i < 3; ++i){
                    buffer[i+1] = array[i];
                }                
                array = buffer;
                break;
            case DIRECTIONS::LEFT:
                buffer[3] = array[0];
                for(int i = 1; i < 4; ++i){
                    buffer[i-1] = array[i];
                }
                array = buffer;
                break;
            default:
                throw std::runtime_error(std::string("Unknown Direction (") + std::to_string(direction) + ')' );
        }
    }
}


class Matrix{
private:
    std::array<std::array<int, 4>, 4> m_field;
    int m_empty;
    std::pair<int, int> m_empty_position;
public:

    //Creates the sorted field where 0 is the empty value and the field is laid out as following;
    //[
    //  [1 , 2 , 3 , 4 ],
    //  [5 , 6 , 7 , 8 ],
    //  [9 , 10, 11, 12],
    //  [13, 14, 15, 0 ],
    //]
    inline Matrix(): m_empty(0), m_empty_position(std::make_pair(3, 3)) {
        int num = 1;
        for(int i = 1; i <= 4; ++i){
            for(int j = 1; j <= 4; ++j){
                m_field[i-1][j-1] = num;
                ++num;
            }
        }
        m_field[3][3] = 0;
    }
    inline Matrix(std::array<std::array<int, 4>, 4> const& arr, int empty_value = 0){
        m_empty = empty_value;
        bool empty_found = false;
        for(int i = 0; i < 4; ++i){
            for(int j = 0; j < 4; ++j){
                m_field[i][j] = arr[i][j];
                if(arr[j][i] == empty_value){
                    if(!empty_found){
                        m_empty_position = std::make_pair(i, j);
                        empty_found = true;
                    }
                    else{
                        throw std::runtime_error(std::string("Empty value (") + std::to_string(empty_value) + ") found twice in matrix");
                    }
                }
            }
        }
        if(!empty_found){
            throw std::runtime_error(std::string("Empty value (") + std::to_string(empty_value) + ") not found in matrix");
        }
    }

    inline Matrix(Matrix const& field): m_empty(field.m_empty), m_empty_position(field.m_empty_position){
        for(int i = 0; i < 4; ++i){
            for(int j = 0; j < 4; ++j){
                m_field[i][j] = field.m_field[i][j];
            }
        }
    }
    inline Matrix(Matrix&& field): m_empty(std::move(field.m_empty)), m_empty_position(std::move(field.m_empty_position)){
        for(int i = 0; i < 4; ++i){
            for(int j = 0; j < 4; ++j){
                m_field[i][j] = std::move(field.m_field[i][j]);
            }
        }
    }
    Matrix& operator=(Matrix const& field){
        m_empty = field.m_empty;
        m_empty_position = field.m_empty_position;
        for(int i = 0; i < 4; ++i){
            for(int j = 0; j < 4; ++j){
                m_field[i][j] = field.m_field[i][j];
            }
        }
        return *this;
    }

    Matrix& operator=(Matrix&& field){
        m_empty_position = std::move(field.m_empty_position);
        m_empty = std::move(field.m_empty);
        for(int i = 0; i < 4; ++i){
            for(int j = 0; j < 4; ++j){
                m_field[i][j] = std::move(field.m_field[i][j]);
            }
        }
        return *this;
    }

    std::pair<int, int> find_empty_position() const{
        std::pair<int, int> result;
        for(int i = 0; i < 4; ++i){
            for(int j = 0; j < 4; ++j){
                if(m_field[i][j]==m_empty){
                    return {i, j};
                }
            }
        }
        throw std::runtime_error(std::string("empty value (") + std::to_string(m_empty) + ") not found in matrix");
    }

    void move(DIRECTIONS::Directions direction){
        int x = m_empty_position.first;
        int y = m_empty_position.second;
        int temp;
        switch(direction){
            case DIRECTIONS::UP:
                if(y == 0){
                    throw std::runtime_error("Can't move UP, empty field is already at y=0");
                }
                temp = m_field[y-1][x];
                m_field[y-1][x] = m_empty;
                m_field[y][x] = temp;
                m_empty_position.second = y-1;
                break;
            case DIRECTIONS::RIGHT:
                if(x == 3){
                    throw std::runtime_error("Can't move RIGHT, empty field is already at x=3");
                }
                temp = m_field[y][x+1];
                m_field[y][x+1] = m_empty;
                m_field[y][x] = temp;
                m_empty_position.first = x+1;
                break;
            case DIRECTIONS::DOWN:
                if(y == 3){
                    throw std::runtime_error("Can't move DOWN, empty field is already at y=3");
                }
                temp = m_field[y+1][x];
                m_field[y+1][x] = m_empty;
                m_field[y][x] = temp;
                m_empty_position.second = y+1;
                break;
            case DIRECTIONS::LEFT:
                if(x == 0){
                    throw std::runtime_error("Can't move LEFT, empty field is already at x=0");
                }
                temp = m_field[y][x-1];
                m_field[y][x-1] = m_empty;
                m_field[y][x] = temp;
                m_empty_position.first = x-1;
                break;
            default:
                (void)0;
        }

    }

    std::array<std::array<int, 4>, 4> get_field() const{
        return m_field;
    }

    int get_empty_value() const{
        return m_empty;
    }

    std::pair<int, int> get_empty_position(){
        return m_empty_position;
    }

    std::string to_string() const{
        std::string result = "[";
        for(std::array<int, 4> const& row: m_field){
            result += '[';
            for(int const col: row){
                result += std::to_string(col);
                result += ", ";
            }
            result.pop_back();
            result.pop_back();
            result += "], ";
        }
        result.pop_back();
        result.pop_back();
        result += ']';
        return result;
    }

    std::array<int, 4> at(unsigned int index){
        if(index >= 4){
            throw std::out_of_range(std::string("Index ") + std::to_string(index) + " is higher than 3");
        }
        else{
            return m_field[index];    
        }
    }

    std::array<int, 4> operator[](unsigned int index){
        return m_field[index];
    }


    friend bool operator==(Matrix const& field1, Matrix const& field2){
        if(field1.m_empty != field2.m_empty || field1.m_empty_position != field2.m_empty_position){
            return false;
        }
        for(int i = 0; i < 4; ++i){
            for(int j = 0; j < 4; ++j){
                if(field1.m_field[i][j] != field2.m_field[i][j]){
                    return false;
                }
            }
        }
        return true;
    }

    //Following methods should never be needed
    
    //Syncs the internal m_empty_position with the actual position of the empty cell
    bool sync(){
        std::pair<int, int> pos = find_empty_position();
        if(m_empty_position != pos){
            m_empty_position = pos;
            return true;
        }
        else{
            return false;
        }
    }

    //Checks if
    //a) Every value comes up exactly once
    //b) The empty value is there and comes up exactly once
    //Returns true if everything is fine,
    //if it isn't returns false. If you need more info about what is wrong, :-p
    bool check_integrity() const{
        std::set<int> set{};
        for(std::array<int, 4> const& row: m_field){
            for(int const col: row){
                if(set.count(col) != 0){
                    return false;
                }
                else{
                    set.insert(col);
                }
            }
        }
        if(set.count(m_empty) != 1 || find_empty_position() != m_empty_position){
            return false;
        }
        return true;
    }

};

Matrix const SOLVED_MATRIX = Matrix();

bool is_solved(Matrix const& field){
    return field == SOLVED_MATRIX;
}


class ThreadPool{
    static inline std::vector<std::thread> m_threads;                       //Place for the threads
    static inline int m_counter = 0;                                        //Counts how many threads there are, also used to assign ids
    static inline std::mutex m_lock{};                                      //For m_result access
    static inline bool m_running = true;                                    //If the threads should continue searching for solution, also an indicator for if a solution has been found
    static inline bool m_close_all_threads_registered = false;              //If the program gets ^C, makes sure ThreadPool::close_all_threads get's called exactly once
    static inline std::string m_result;                                     //Result
    static inline unsigned long long m_for_analysis[MAX_THREADS] = {0};     //For analysis if new threads are actually useful

    int m_id;
    std::thread m_thread;
public:
    inline ThreadPool(){
        m_id = m_counter;
        ++m_counter;
        if(!m_close_all_threads_registered){
            std::atexit(&close_all_threads);
            m_close_all_threads_registered = true;
        }
    }

    void start(Matrix field){
        m_threads.emplace_back(std::thread(&ThreadPool::solve_matrix, this, field));

    }

    void solve_matrix(Matrix field){
        std::random_device rd;
        std::mt19937 gen(rd());
        std::uniform_int_distribution<int> random_int(0, 3);
        std::string result;

        int random;

        while(m_running){
            if(is_solved(field)){
                std::lock_guard<std::mutex> guard(m_lock);
                m_running = false;
                m_result = result;
            }
            else{
                ++m_for_analysis[m_id];
                //creates a random move, starts over if the move is impossible
                start:
                random = random_int(gen);
                switch(random){
                    case 0: 
                        if(field.get_empty_position().second == 0){
                            goto start;
                        }
                        else{
                            field.move(DIRECTIONS::UP);
                            result += "U";
                        }
                        break;
                    case 1:
                        if(field.get_empty_position().first == 3){
                            goto start;
                        }
                        else{
                            field.move(DIRECTIONS::RIGHT);
                            result += "R";
                        }
                        break;
                    case 2:
                        if(field.get_empty_position().second == 3){
                            goto start;
                        }
                        else{
                            field.move(DIRECTIONS::DOWN);
                            result += "D";
                        }
                        break;
                    case 3:
                        if(field.get_empty_position().first == 0){
                            goto start;
                        }
                        else{
                            field.move(DIRECTIONS::LEFT);
                            result += "L";
                        }
                        break;
                    default:
                        (void)0;
                }
            }
        }
    }

    static void close_all_threads(){
        std::lock_guard<std::mutex> guard(m_lock);
        m_running = false;
        for(std::thread& thread: m_threads){
            thread.join();
        }
        m_threads.clear();
    }

    static std::string get_result(){
        return m_result;
    }

    static bool is_running(){
        return m_running;
    }

    static int get_counter(){
        return m_counter;
    }

    static unsigned long long* get_analysis(){
        return m_for_analysis;
    }

    static std::mutex& get_lock(){
        return m_lock;
    }
};


std::string solve(std::array<std::array<int, 4>, 4> input){
    Matrix field(input);
    ThreadPool first_thread;
    first_thread.start(field);
    #ifdef WITH_THREADS
    bool limit_reached = false;

    unsigned long long analysis_array1[MAX_THREADS] = {0};
    unsigned long long analysis_array2[MAX_THREADS] = {0};
    while(ThreadPool::is_running() && ThreadPool::get_counter() < MAX_THREADS && !limit_reached){
        std::this_thread::sleep_for(10ms);
        unsigned long long* temp = ThreadPool::get_analysis();
        for(int i = 0; i < MAX_THREADS; ++i){
            analysis_array1[i] = temp[i];
        }
        unsigned long long sum1;
        unsigned long long sum2;
        for(int i = 0; i < MAX_THREADS; ++i){
            sum1 += analysis_array1[i];
            sum2 += analysis_array2[i];
        }
        long double ratio = static_cast<long double>(sum2)/sum1;
        if(ratio > RATIO_THRESHOLD){
            limit_reached = true;
            break;
        }
        for(int i = 0; i < MAX_THREADS; ++i){
            analysis_array2[i] = analysis_array1[i];
        }
        ThreadPool thread = ThreadPool();
        thread.start(field);
    }
    std::cout << "STOPPED CREATING MORE THREADS OR SOLUTION FOUND; TOTAL THREADS (with main): " << ThreadPool::get_counter()+1 << '\n';
    #endif
    while(ThreadPool::is_running()){}
    ThreadPool::close_all_threads();
    return ThreadPool::get_result();
}

Rabbitgaming's stats

guessed the most

were guessed the most by

entries

round #41

post a comment

round #40

post a comment