Welcome to HBH! If you have tried to register and didn't get a verification email, please using the following link to resend the verification email.
Code Golf
I used to do something similar, maze solvers. I can't seem to dig up any of my own code, but I have a good friends work here:
http://www.societyofrobots.com/member_tutorials/node/94 that's a tutorial kind of. I haven't really looked through a lot of your code but it doesn't look in the least bit right. Here was my buddies winning code to solve a maze in the fewest keystrokes:
/*
Maze Programming Contest
(C) 2008 nulluser@gmail.com
*/
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
// Cell directions and flags
#define CELL_N 0x01 // North
#define CELL_S 0x02 // South
#define CELL_E 0x04 // East
#define CELL_W 0x08 // West
#define CELL_FLAG 0x10 // Marker for generation and path
const unsigned int step_mode = 0; // True for single step testing mode
const unsigned int maze_x_size = 25; // Size of maze
const unsigned int maze_y_size = 10;
const unsigned int num_tries = 1; // Number of random mazes to test
const unsigned long count_limit = maze_x_size * maze_y_size * 4;
/* User solution */
struct solution_type
{
char name[32]; // Name of solution
unsigned int (*func)(unsigned int doors); // User function
long int count; // Total steps
};
/* Core maze */
struct maze_type
{
unsigned char *cell_data; // Cell grid
unsigned long x_size, y_size; // Size of maze
};
/*
Submissions
*/
/* Right hand rule */
unsigned int rh_rule(unsigned int doors)
{
static unsigned int dir = CELL_E;
dir = dir == CELL_S ? CELL_W : // Rotate right
dir == CELL_E ? CELL_S :
dir == CELL_N ? CELL_E : CELL_N;
while(dir & doors) // While blocked rotate left
dir = dir == CELL_E ? CELL_N :
dir == CELL_N ? CELL_W :
dir == CELL_W ? CELL_S : CELL_E;
return(dir);
}
/* End of rh_rule */
/* Left hand rule */
unsigned int lh_rule(unsigned int doors)
{
static unsigned int dir = CELL_E;
dir = dir == CELL_E ? CELL_N : // Rotate left
dir == CELL_N ? CELL_W :
dir == CELL_W ? CELL_S : CELL_E;
while(dir & doors) // While blocked rotate right
dir = dir == CELL_S ? CELL_W :
dir == CELL_E ? CELL_S :
dir == CELL_N ? CELL_E : CELL_N;
return(dir);
}
/* End of lh_rule */
/*
End of Submissions
*/
/* Return maze cell data */
inline unsigned char get_data(struct maze_type *maze, int x, int y)
{
return(maze->cell_data[x + y * maze->x_size]);
}
/* End of get data */
/* Return true if the requested door is open */
unsigned int door_clear(struct maze_type *maze, int x, int y, unsigned int dir)
{
if (x < 0 || x >= maze->x_size || y < 0 || y >= maze->y_size ) return(0);
if ((dir == CELL_N && get_data(maze, x, y) & CELL_N) ||
(dir == CELL_S && get_data(maze, x, y+1) & CELL_N) ||
(dir == CELL_W && get_data(maze, x, y) & CELL_W) ||
(dir == CELL_E && get_data(maze, x+1, y) & CELL_W)) return(0);
return(1);
}
/* End of door clear */
/* Decode walls for corners */
unsigned char get_corner(struct maze_type *maze, int x, int y)
{
unsigned int bars = 0; // Blocked paths around intersection
// Check around the intersection to determine what is blocked
if (x < maze->x_size && !door_clear(maze, x, y, CELL_N)) bars |= 0x01; // E
if (y < maze->y_size && !door_clear(maze, x, y, CELL_W)) bars |= 0x02; // S
if (x > 0 && !door_clear(maze, x-1, y-1, CELL_S)) bars |= 0x04; // W
if (y > 0 && !door_clear(maze, x-1, y-1, CELL_E)) bars |= 0x08; // N
// ASCII Chars for the different maze intersections
unsigned char ascii_corner[] = {' ', 196, 179, 218, 196, 196, 191, 194,
179, 192, 179, 195, 217, 193, 180, 197};
return(ascii_corner[bars]);
}
/* End of get_corner */
/* Return true if a cell has been visited or is out of range */
unsigned int check_flag(struct maze_type *maze, int x, int y)
{
if (x < 0 || x >= maze->x_size || y < 0 || y >= maze->y_size) return(1);
if (get_data(maze, x, y) & CELL_FLAG) return(1);
return(0);
}
/* End of cell_visit */
/* Breaks down the barrier between cells */
// Only UP and LEFT are used for door markers
void open_door(struct maze_type *maze, int x, int y, unsigned int dir)
{
if (dir == CELL_W) maze->cell_data[x+y*maze->x_size] &= ~CELL_W;
if (dir == CELL_E) maze->cell_data[x+y*maze->x_size+1] &= ~CELL_W;
if (dir == CELL_N) maze->cell_data[x+y*maze->x_size] &= ~CELL_N;
if (dir == CELL_S) maze->cell_data[x+(y+1)*maze->x_size] &= ~CELL_N;
}
/* End of open door */
/* Process next cell for maze generation */
void next_cell(struct maze_type *maze, int x, int y)
{
// Mark cell as visited
maze->cell_data[x + y * maze->x_size] |= CELL_FLAG;
// Compute visited cells nearby
unsigned int open = !check_flag(maze, x, y - 1) * CELL_N |
!check_flag(maze, x, y + 1) * CELL_S |
!check_flag(maze, x - 1, y) * CELL_W |
!check_flag(maze, x + 1, y) * CELL_E;
if (open == 0) return; // Nowhere to go, back track
unsigned int dir = 0;
// Loop until we find an unvisited cell
while (!(open & dir)) dir = 1 << rand() % 4;
open_door(maze, x, y, dir);
next_cell(maze, x - (dir == CELL_W) + (dir == CELL_E),
y - (dir == CELL_N) + (dir == CELL_S));
// Branch if not at beginning, done otherwise
if (x + y != 0) next_cell(maze, x, y);
}
/* End of next_cell */
/* Create a random maze */
int make_maze(struct maze_type *maze, unsigned int x_size, unsigned int y_size)
{
maze->x_size = x_size;
maze->y_size = y_size;
// The extra right column and bottom row are used for barrires
maze->cell_data = (unsigned char *) malloc((x_size + 1) * (y_size + 1));
if (maze->cell_data == NULL)
{
printf("Unable to get maze memory\n");
return(1);
}
// Close all doors
for (int i = 0; i < (maze->x_size + 1) * (maze->y_size + 1); i++)
maze->cell_data[i] = CELL_N | CELL_W;
// Create the maze
next_cell(maze, 0, 0);
return(0);
}
/* End of make maze */
/* Display the maze */
void show_maze(struct maze_type *maze, int px, int py)
{
for (unsigned int y = 0; y < maze->y_size + 1; y++)
{
for (unsigned int x = 0; x < maze->x_size; x++)
{
if (!door_clear(maze, x, y, CELL_N))
printf("%c%c%c", get_corner(maze, x, y), 196, 196);
else
printf("%c ", get_corner(maze, x, y));
}
printf("%c\n", get_corner(maze,maze->x_size, y));
for (unsigned int x = 0; x < maze->x_size + 1 && y != maze->y_size; x++)
{
printf("%c", door_clear(maze, x, y, CELL_W) ? ' ' : 179);
if (x == px && y == py) printf("**"); else
if (get_data(maze, x, y) & CELL_FLAG && x != maze->x_size)
printf("%c%c", 222, 221);
else
printf(" ") ;
}
printf("\n");
}
}
/* End of show maze */
/* Clear travel path and reset to start */
void reset_maze( struct maze_type *maze)
{
for (int i = 0; i < (maze->x_size + 1) * (maze->y_size + 1); i++)
maze->cell_data[i] &= ~CELL_FLAG;
}
/* End of reset maze */
/* Test a solution */
int solve_maze(maze_type *maze, unsigned int next_move(unsigned int doors) )
{
int count = 0, x = 0, y = 0;
// Mark start
maze->cell_data[0] |= CELL_FLAG;
while(count < count_limit)
{
if (step_mode) printf("(%d, %d)\n", x, y);
// Compute closed doors
unsigned int doors = !door_clear(maze, x, y, CELL_N) * CELL_N |
!door_clear(maze, x, y, CELL_S) * CELL_S |
!door_clear(maze, x, y, CELL_W) * CELL_W |
!door_clear(maze, x, y, CELL_E) * CELL_E;
// Run user's code and filter agasint doors
unsigned int move = next_move(doors) & ~doors;
// Move in maze. Make sure only one move takes place
if (move == CELL_N) y--; else
if (move == CELL_S) y++; else
if (move == CELL_W) x--; else
if (move == CELL_E) x++;
count++;
// Mark current cell
maze->cell_data[x + y * maze->x_size] |= CELL_FLAG;
// Lower right corner, maze solved
if (x == maze->x_size-1 && y == maze->y_size-1) return(count);
// Display progress
if (step_mode)
{
show_maze(maze, x, y);
getchar();
}
}
return(0);
}
/* End of solve maze */
/* Driver */
int main( void )
{
// Solutions to test
struct solution_type solutions[] = {{"RH Rule", &rh_rule, 0},
{"LH Rule", &lh_rule, 0}};
unsigned int num_solutions = sizeof(solutions) / sizeof(solution_type);
srand(time(NULL));
maze_type maze;
// Try each solution with a number of different mazes
for (int i = 0; i < num_tries; i++)
{
if (make_maze(&maze, maze_x_size, maze_y_size))
{
printf("Unable to make maze\n");
return(1);
}
// Try the solutions
for (int j = 0; j < num_solutions; j++)
{
reset_maze(&maze);
printf("Testing %s: \n", solutions[j].name);
unsigned int steps = solve_maze(&maze, solutions[j].func);
// Unable to solve
if (steps == 0) solutions[j].count = -1;
// Add steps to solve
solutions[j].count += steps;
show_maze(&maze, -1, -1);
}
free(maze.cell_data);
}
printf("Name Score\n");
printf("-------------------------\n");
for (int i = 0; i < num_solutions; i++)
{
printf("%-16s ", solutions[i].name);
if (solutions[i].count != -1)
printf("%-4d\n", solutions[i].count / num_tries);
else
printf("DNF\n", solutions[i].name);
}
getchar();
return(0);
}
/* End of main */
I'll try and dig up my solution, it wasn't quite as complicated.
The last line threw me off a bit.. so I had to cheat on a few lines, and I am still very much a beginner in cpp so I don't know all the shortcuts :(
smufkin@emily:~$ wc -c golf.cpp 210 golf.cpp smufkin@emily:~$ cat golf.cpp #include <iostream> char a = 94; main(){ for (int c=4;c<13;c++){ a=a+3; if(c>6&&c<11){a++;} if(c==10){a++;} if(c==11){a++;} if(a>122){a=a-26;} std::cout << a << "\t"; if (c%3==0){std::cout << "\n";} } } smufkin@emily:~$ ./golf a d g k o s x b e
The Cheating Way:
smufkin@emily:~$ wc -c golf.pl 37 golf.pl smufkin@emily:~$ cat golf.pl print "a\td\tg\nk\to\ts\nx\tb\te\n"; smufkin@emily:~$ perl golf.pl a d g k o s x b e
japanesedude wrote: The last line threw me off a bit.. so I had to cheat on a few lines, and I am still very much a beginner in cpp so I don't know all the shortcuts :(
smufkin@emily:~$ wc -c golf.cpp 210 golf.cpp smufkin@emily:~$ cat golf.cpp #include <iostream> char a = 94; main(){ for (int c=4;c<13;c++){ a=a+3; if(c>6&&c<11){a++;} if(c==10){a++;} if(c==11){a++;} if(a>122){a=a-26;} std::cout << a << "\t"; if (c%3==0){std::cout << "\n";} } } smufkin@emily:~$ ./golf a d g k o s x b e
The Cheating Way:
smufkin@emily:~$ wc -c golf.pl 37 golf.pl smufkin@emily:~$ cat golf.pl print "a\td\tg\nk\to\ts\nx\tb\te\n"; smufkin@emily:~$ perl golf.pl a d g k o s x b e
lulz :)