online compiler and debugger for c/c++

code. compile. run. debug. share.
Source Code    Language
/* ============================================================================ Name : 2048.c Author : Maurits van der Schee Description : Console version of the game "2048" for GNU/Linux ============================================================================ */ #ifndef __NODE__ #define __NODE__ #ifndef __UTILS__ #define __UTILS__ #include <stdio.h> #include <stdlib.h> #include <string.h> #include <unistd.h> #include <termios.h> #include <stdbool.h> #include <stdint.h> #include <time.h> #include <signal.h> #define SIZE 4 #define _XOPEN_SOURCE 500 /** * Move type */ typedef enum moves{ left=0, right=1, up=2, down=3 } move_t; struct ai_s{ move_t move; int generated; int expanded; }; /** * Back Propagation type */ typedef enum propagation{ max=0, avg=1 } propagation_t; /** * Renders the board */ void drawBoard(uint8_t board[SIZE][SIZE], uint32_t score); /** * Updates the board with each action, and updates the score */ bool moveUp(uint8_t board[SIZE][SIZE], uint32_t* score); bool moveLeft(uint8_t board[SIZE][SIZE], uint32_t* score); bool moveDown(uint8_t board[SIZE][SIZE], uint32_t* score); bool moveRight(uint8_t board[SIZE][SIZE], uint32_t* score); /** * Checks if game has ended */ bool gameEnded(uint8_t board[SIZE][SIZE]); /** * Counts the number of empty cells */ uint8_t countEmpty(uint8_t board[SIZE][SIZE]); /** * Given an index, returns the tile value, i is row, j is column */ uint32_t getTile( uint8_t board[SIZE][SIZE], unsigned i, unsigned j); /** * initial random board, and a function to randmoly add a tile */ void initBoard(uint8_t board[SIZE][SIZE], uint32_t* score); void addRandom(uint8_t board[SIZE][SIZE]); /** * Executes an action, updates the board and the score, and return true if the board has changed, * and false otherwise */ bool execute_move_t( uint8_t board[SIZE][SIZE], uint32_t* score, move_t move); #endif /** * Data structure containing the node information */ struct node_s{ uint32_t priority; int depth; int num_childs; move_t move; uint8_t board[SIZE][SIZE]; struct node_s* parent; move_t firstMove; }; typedef struct node_s node_t; #endif #ifndef __AI__ #define __AI__ #include <stdint.h> #include <unistd.h> void initialize_ai(); struct ai_s get_next_move( uint8_t board[SIZE][SIZE], int max_depth, propagation_t propagation ); int get_max(int* scores); int propogateBackToFirstAction(node_t* node); bool board_different(node_t* node1, node_t* node2); void array_add(node_t* node, node_t** explored, int numNodes ); #endif #include "inttypes.h" /** * Setting up terminal to draw the game board */ void setBufferedInput(bool enable) { static bool enabled = true; static struct termios old; struct termios new; if (enable && !enabled) { // restore the former settings tcsetattr(STDIN_FILENO,TCSANOW,&old); // set the new state enabled = true; } else if (!enable && enabled) { // get the terminal settings for standard input tcgetattr(STDIN_FILENO,&new); // we want to keep the old setting to restore them at the end old = new; // disable canonical mode (buffered i/o) and local echo new.c_lflag &=(~ICANON & ~ECHO); // set the new settings immediately tcsetattr(STDIN_FILENO,TCSANOW,&new); // set the new state enabled = false; } } void signal_callback_handler(int signum) { printf(" TERMINATED \n"); setBufferedInput(true); printf("\033[?25h\033[m"); exit(signum); } /** * Valid keys for playing */ bool execute_keyboard( uint8_t board[SIZE][SIZE], uint32_t* score, char c){ bool success = false; switch(c) { case 97: // 'a' key case 104: // 'h' key case 68: // left arrow success = moveLeft(board, score); break; case 100: // 'd' key case 108: // 'l' key case 67: // right arrow success = moveRight(board, score); break; case 119: // 'w' key case 107: // 'k' key case 65: // up arrow success = moveUp(board, score); break; case 115: // 's' key case 106: // 'j' key case 66: // down arrow success = moveDown(board, score); break; default: success = false; } return success; } void print_usage(){ printf("To run the AI solver: \n"); printf("USAGE: ./2048 ai <max/avg> <max_depth> slow\n"); printf("or, to play with the keyboard: \n"); printf("USAGE: ./2048\n"); } int main(int argc, char *argv[]) { clock_t start=clock(),end; uint32_t score=0; uint8_t board[SIZE][SIZE]; int generated=0; int expanded=0; int i=0,j=0; uint32_t maxTile=0; int max_depth=0; char c; bool success; bool ai_run = false; propagation_t propagation=max; bool slow = false; struct ai_s selected_move; selected_move.move=0; selected_move.generated=0; selected_move.expanded=0; /** * Parsing command line options */ if( argc > 1 && argc < 4 ){ print_usage(); return 0; } if (argc > 1 ) { ai_run = true; initialize_ai(); if( strcmp(argv[2],"avg")==0 ){ propagation = avg; } else if( strcmp(argv[2],"max")==0 ){ propagation = max; } else{ print_usage(); return 0; } sscanf (argv[3],"%d",&max_depth); if(argc == 5 && strcmp(argv[4],"slow")==0 ) slow = true; } printf("\033[?25l\033[2J"); /** * register signal handler for when ctrl-c is pressed */ signal(SIGINT, signal_callback_handler); setBufferedInput(false); /** * Create initial state */ initBoard(board, &score); while (true) { /** * AI execution mode */ if(ai_run){ /** * ****** HERE IS WHERE YOUR SOLVER IS CALLED */ selected_move=(get_next_move( board, max_depth, propagation )); generated+= selected_move.generated; expanded += selected_move.expanded; /** * Execute the selected action */ success = execute_move_t( board, &score, selected_move.move); } else{ /** * Keyboard execution mode */ c=getchar(); success = execute_keyboard(board, &score, c); if (c=='q') { printf(" QUIT? (y/n) \n"); c=getchar(); if (c=='y') { break; } drawBoard(board,score); } if (c=='r') { printf(" RESTART? (y/n) \n"); c=getchar(); if (c=='y') { initBoard(board, &score); } drawBoard(board,score); } } /** * If selected action merges tiles, * then, add a random tile and redraw the board */ if (success) { drawBoard(board,score); if(slow) usleep(150000); //0.15 seconds addRandom(board); drawBoard(board,score); if (gameEnded(board)) { printf(" GAME OVER \n"); break; } } } setBufferedInput(true); printf("\033[?25h\033[m"); for(i=0;i<SIZE;i++){ for(j=0;j<SIZE;j++){ if(getTile(board,i,j) > maxTile){ maxTile = getTile(board,i,j); } } } end= clock(); printf("maxDepth = %i \n",max_depth); printf("Generated = %i\n",generated); printf("Expanded = %i\n",expanded); printf("Time = %f\n",(float)((end-start)/1000000.0)); printf("Expanded/Second = %i \n", (int)(expanded / (float)((end-start)/1000000.0))); printf("max_tile =" "%" PRIu32 "\n", maxTile ); printf("Score = %i\n",score ); return EXIT_SUCCESS; } /* Author: Eric Sciberras */ #include <time.h> #include <stdlib.h> #ifndef __PQ__ #define __PQ__ /** * NIR: Adapted from https://gist.github.com/aatishnn/8265656#file-binarymaxheap-c */ #include <stdio.h> #include <stdlib.h> /** * size is the allocated size, count is the number of elements in the queue */ struct heap { int size; int count; node_t** heaparr; }; int *heap, size, count; #define initial_size 4 void heap_init(struct heap* h); void max_heapify(node_t** data, int loc, int count); void heap_push(struct heap* h, node_t* value); void heap_display(struct heap* h); node_t* heap_delete(struct heap* h); void emptyPQ(struct heap* pq); #endif #include "math.h" #include "inttypes.h" #include <assert.h> struct heap h; void initialize_ai(){ heap_init(&h); } /** * Find best action by building all possible paths up to depth max_depth * and back propagate using either max or avg */ struct ai_s get_next_move( uint8_t board[SIZE][SIZE], int maxDepth, propagation_t propagation ){ int i=0,numNodes=0; struct ai_s aiOutput; aiOutput.generated=0; aiOutput.expanded=0; int scores[4]={0,0,0,0}; //this array holds the scores for each move choice and is used to decide how to play int exploredSize=1000; // keeps track of the size of our explored array move_t move=0; node_t* node=(node_t*)calloc(1,sizeof(node_t)); node_t* newNode=(node_t*)calloc(1,sizeof(node_t)); // node_t* tempNode=(node_t*)calloc(1,sizeof(node_t)); // temporary stores node when executing moves node_t** explored=(node_t**)calloc(exploredSize,sizeof(node_t)); // holds all the nodes we have looked at //just in case assert(node); assert(newNode); assert(tempNode); assert(explored); memcpy(node->board,board,sizeof(uint8_t) * SIZE * SIZE); // put board in node node->move=-1; //heap_init(&h); array_add(node,explored,numNodes); //heap_push(&h,explored[numNodes]); numNodes++; //frontier_add(node); while( (&h)->count != 0 ){ node=heap_delete(&h); aiOutput.expanded++; //array_add(node,explored,numNodes); //numNodes++; if(node->depth < maxDepth){ for(i=0;i<4;i++){ aiOutput.generated++; // This Block handles the assignment of the Newnode (new board) // and node (board before the move is made) memcpy(tempNode,node, sizeof(node_t)); execute_move_t( node->board, &(node->priority), i); memcpy(newNode,node,sizeof(node_t)); memcpy(node,tempNode,sizeof(node_t)); // if the new board is different then we will add it to the priority queue and // trace back the score to the first move made, then we will use this data to help // our propagation if( board_different(node,newNode) == true ){ newNode->move = i; newNode->depth = node->depth+1; newNode->parent = node; node->num_childs++; move=propogateBackToFirstAction(newNode); if( exploredSize <= numNodes){ explored=(node_t**)realloc(explored,2*exploredSize*sizeof(node_t)); assert(explored); exploredSize = 2*exploredSize; } array_add(newNode,explored,numNodes); numNodes++; if(propagation==max){ if( newNode->priority > scores[move]){ scores[move]=newNode->priority; } } else{ // Average propogation heuristics: very simple heuristic // prioritises the scores closer to the current board as they are // more liekly to be acheived due to the random tiles popping up after each turn scores[move]+= newNode->priority/ (float)(newNode->depth); } } } } } for(i=0;i<numNodes;i++){ free(explored[i]); } free(explored); free(newNode); free(tempNode); //free(node); // yes i know this 'should' be run but it seems to completely destroy my code aiOutput.move= get_max(scores); return (aiOutput); } void array_add(node_t* node, node_t** explored, int numNodes ){ node_t* tempNode=(node_t*)calloc(1,sizeof(node_t)); assert(tempNode); memcpy(tempNode,node, sizeof(node_t)); explored[numNodes] = tempNode; heap_push(&h,tempNode); } //board_different takes two nodes and compares them, it returns True if the boards are different // or false if otherwise bool board_different(node_t* node1, node_t* node2){ int i ,j; for(i=0;i<SIZE;i++){ for(j=0;j<SIZE;j++){ if(node1->board[i][j]!=node2->board[i][j] ){ return true; } } } return false; } // get_max takes an int array (4 elements) and find the index of the maximum value, // in the case of a tie a maximum random move is chosen int get_max(int* scores){ int i=0, max=0, matches=0; int duplicate_scores[4]={-1,-1,-1,-1}; // get the maximum element for (i=0;i<4;i++){ if (scores[i] >= max){ max = scores[i]; } } // look for duplicates for(i=0;i<4;i++){ if(max==scores[i]){ duplicate_scores[matches]=i; matches++; } } return(duplicate_scores[rand() % matches]); } // propogateBackToFirstAction takes a node and finds what original move led to it int propogateBackToFirstAction(node_t* node){ if(node->depth == 1){ return (node->move); } return(propogateBackToFirstAction(node->parent)); } void heap_init(struct heap* h) { int i; h->count = 0; h->size = initial_size; h->heaparr = (node_t **) malloc(sizeof(node_t*) * initial_size); for(i = 0; i < initial_size; i++) h->heaparr[i]=NULL; if(!h->heaparr) { printf("Error allocatinga memory...\n"); exit(-1); } } void max_heapify(node_t** data, int loc, int count) { int left, right, largest; node_t* temp; left = 2*(loc) + 1; right = left + 1; largest = loc; if (left <= count && data[left]->priority > data[largest]->priority) { largest = left; } if (right <= count && data[right]->priority > data[largest]->priority) { largest = right; } if(largest != loc) { temp = data[loc]; data[loc] = data[largest]; data[largest] = temp; max_heapify(data, largest, count); } } void heap_push(struct heap* h, node_t* value) { int index, parent; // Resize the heap if it is too small to hold all the data if (h->count == h->size) { h->size += 1; h->heaparr = realloc(h->heaparr, sizeof(node_t) * h->size); if (!h->heaparr) exit(-1); // Exit if the memory allocation fails } index = h->count++; // First insert at last of array // Find out where to put the element and put it for(;index; index = parent) { parent = (index - 1) / 2; if (h->heaparr[parent]->priority >= value->priority) break; h->heaparr[index] = h->heaparr[parent]; } h->heaparr[index] = value; } void heap_display(struct heap* h) { int i; for(i=0; i<h->count; ++i) { node_t* n = h->heaparr[i]; printf("priority = %d", n->priority); printf("\n"); drawBoard( n->board, 0 ); } } node_t* heap_delete(struct heap* h) { node_t* removed; node_t* temp = h->heaparr[--h->count]; if ((h->count <= (h->size + 2)) && (h->size > initial_size)) { h->size -= 1; h->heaparr = realloc(h->heaparr, sizeof(node_t) * h->size); if (!h->heaparr) exit(-1); // Exit if the memory allocation fails } removed = h->heaparr[0]; h->heaparr[0] = temp; if(temp == removed) h->heaparr[0] = NULL; max_heapify(h->heaparr, 0, h->count); return removed; } void emptyPQ(struct heap* pq) { while(pq->count != 0) { node_t* n = heap_delete(pq); free(n); //printf("<<%d", heap_delete(pq)); } } uint8_t scheme=0; // i = row, j = col uint32_t getTile( uint8_t board[SIZE][SIZE], unsigned i, unsigned j){ return (uint32_t)1<<board[j][i]; } void getColor(uint8_t value, char *color, size_t length) { uint8_t original[] = {8,255,1,255,2,255,3,255,4,255,5,255,6,255,7,255,9,0,10,0,11,0,12,0,13,0,14,0,255,0,255,0}; uint8_t blackwhite[] = {232,255,234,255,236,255,238,255,240,255,242,255,244,255,246,0,248,0,249,0,250,0,251,0,252,0,253,0,254,0,255,0}; uint8_t bluered[] = {235,255,63,255,57,255,93,255,129,255,165,255,201,255,200,255,199,255,198,255,197,255,196,255,196,255,196,255,196,255,196,255}; uint8_t *schemes[] = {original,blackwhite,bluered}; uint8_t *background = schemes[scheme]+0; uint8_t *foreground = schemes[scheme]+1; if (value > 0) while (value--) { if (background+2<schemes[scheme]+sizeof(original)) { background+=2; foreground+=2; } } snprintf(color,length,"\033[38;5;%d;48;5;%dm",*foreground,*background); } void drawBoard(uint8_t board[SIZE][SIZE], uint32_t score) { uint8_t x,y; char color[40], reset[] = "\033[m"; printf("\033[H"); printf("2048.c %17d pts\n\n",score); for (y=0;y<SIZE;y++) { for (x=0;x<SIZE;x++) { getColor(board[x][y],color,40); printf("%s",color); printf(" "); printf("%s",reset); } printf("\n"); for (x=0;x<SIZE;x++) { getColor(board[x][y],color,40); printf("%s",color); if (board[x][y]!=0) { char s[8]; snprintf(s,8,"%u",(uint32_t)1<<board[x][y]); uint8_t t = 7-strlen(s); printf("%*s%s%*s",t-t/2,"",s,t/2,""); } else { printf(" · "); } printf("%s",reset); } printf("\n"); for (x=0;x<SIZE;x++) { getColor(board[x][y],color,40); printf("%s",color); printf(" "); printf("%s",reset); } printf("\n"); } printf("\n"); printf(" ←,↑,→,↓ or q \n"); printf("\033[A"); // one line up } uint8_t findTarget(uint8_t array[SIZE],uint8_t x,uint8_t stop) { uint8_t t; // if the position is already on the first, don't evaluate if (x==0) { return x; } for(t=x-1;t>=0;t--) { if (array[t]!=0) { if (array[t]!=array[x]) { // merge is not possible, take next position return t+1; } return t; } else { // we should not slide further, return this one if (t==stop) { return t; } } } // we did not find a return x; } bool slideArray(uint8_t array[SIZE], uint32_t* score) { bool success = false; uint8_t x,t,stop=0; for (x=0;x<SIZE;x++) { if (array[x]!=0) { t = findTarget(array,x,stop); // if target is not original position, then move or merge if (t!=x) { // if target is zero, this is a move if (array[t]==0) { array[t]=array[x]; } else if (array[t]==array[x]) { // merge (increase power of two) array[t]++; // increase score (*score)+=(uint32_t)1<<array[t]; // set stop to avoid double merge stop = t+1; } array[x]=0; success = true; } } } return success; } void rotateBoard(uint8_t board[SIZE][SIZE]) { uint8_t i,j,n=SIZE; uint8_t tmp; for (i=0; i<n/2; i++) { for (j=i; j<n-i-1; j++) { tmp = board[i][j]; board[i][j] = board[j][n-i-1]; board[j][n-i-1] = board[n-i-1][n-j-1]; board[n-i-1][n-j-1] = board[n-j-1][i]; board[n-j-1][i] = tmp; } } } bool moveUp(uint8_t board[SIZE][SIZE], uint32_t* score) { bool success = false; uint8_t x; for (x=0;x<SIZE;x++) { success |= slideArray(board[x], score); } return success; } bool moveLeft(uint8_t board[SIZE][SIZE], uint32_t* score) { bool success; rotateBoard(board); success = moveUp(board, score); rotateBoard(board); rotateBoard(board); rotateBoard(board); return success; } bool moveDown(uint8_t board[SIZE][SIZE], uint32_t* score) { bool success; rotateBoard(board); rotateBoard(board); success = moveUp(board, score); rotateBoard(board); rotateBoard(board); return success; } bool moveRight(uint8_t board[SIZE][SIZE], uint32_t* score) { bool success; rotateBoard(board); rotateBoard(board); rotateBoard(board); success = moveUp(board, score); rotateBoard(board); return success; } uint8_t countEmpty(uint8_t board[SIZE][SIZE]) { uint8_t x,y; uint8_t count=0; for (x=0;x<SIZE;x++) { for (y=0;y<SIZE;y++) { if (board[x][y]==0) { count++; } } } return count; } bool findPairDown(uint8_t board[SIZE][SIZE]) { bool success = false; uint8_t x,y; for (x=0;x<SIZE;x++) { for (y=0;y<SIZE-1;y++) { if (board[x][y]==board[x][y+1]) return true; } } return success; } bool gameEnded(uint8_t board[SIZE][SIZE]) { bool ended = true; if (countEmpty(board)>0) return false; if (findPairDown(board)) return false; rotateBoard(board); if (findPairDown(board)) ended = false; rotateBoard(board); rotateBoard(board); rotateBoard(board); return ended; } void addRandom(uint8_t board[SIZE][SIZE]) { static bool initialized = false; uint8_t x,y; uint8_t r,len=0; uint8_t n,list[SIZE*SIZE][2]; if (!initialized) { srand(time(NULL)); initialized = true; } for (x=0;x<SIZE;x++) { for (y=0;y<SIZE;y++) { if (board[x][y]==0) { list[len][0]=x; list[len][1]=y; len++; } } } if (len>0) { r = rand()%len; x = list[r][0]; y = list[r][1]; n = (rand()%10)/9+1; board[x][y]=n; } } void initBoard(uint8_t board[SIZE][SIZE], uint32_t* score) { uint8_t x,y; for (x=0;x<SIZE;x++) { for (y=0;y<SIZE;y++) { board[x][y]=0; } } addRandom(board); addRandom(board); *score = 0; drawBoard(board,*score); } /** * Given a board configuration, apply action, and return the updated board and score */ bool execute_move_t( uint8_t board[SIZE][SIZE], uint32_t* score, move_t move){ bool success = false; switch(move) { case left: // left arrow success = moveLeft(board, score); break; case right: // right arrow success = moveRight(board, score); break; case up: // up arrow success = moveUp(board, score); break; case down: // down arrow success = moveDown(board, score); break; default: success = false; } return success; }
  • {user}

      {timestamp}

    {content}

    #FunctionFile:Line
    VariableValue
    ExpressionValue