new programming challenge

Toggle sidebar Toggle sidebar
B

Burner

Member
Oct 25, 1999
85
0
0
I enjoyed doing the battleship, although I never really finished it.
Anyway here is a new game.

Write a program that will solve this game for levels 1, 2, 3, 5, 21, 23, 24 (all of these have normal mirrors and prisms)
for a slight extra challenge: 7,9,11,13,15,16,20,22 (these also include double mirrors)
if you can actually get these two, the extreme challenge is: all the other levels (includes splitters)

note you actually have to play through the game to see all the levels, but if you want a pass to get to a higher level feel free to pm me.

I think I wrote one that runs in O((l*w)^(m))
l=length
w=width
m=total number of mirrors

which well sucks (I also don't know if works)
 
D

Descartes

Lifer
Oct 10, 1999
13,968
2
0
1) What are you defining as "length"
2) What are you defining as "width"
3) Are these not the same thing?
4) How are you plotting the coordinates of the mirrors et. al? Are you transposing the levels to some data structure?
5) How do you know it runs in O((i*w)^(m)) if you don't know whether or not it works?

I'm mostly interested in how you've transposed those levels to something you can program against...
 
0

0x7a69

Junior Member
Oct 7, 2001
19
0
0
this is off topic, but i was at barnes & noble about a month ago and picked up a book some of you may enjoy. it's called Games and Decisions by R. Duncan Luce and Howard Raiffa. it's an overview of game theory that is aimed at non-mathematicians. (as a warning, you do need to be fairly decent with math to follow it despite its aim). i've been reading it out of order but have really enjoyed what i have read so far. enjoy
 
M

Mucman

Diamond Member
Oct 10, 1999
7,246
1
0
Holy this is soo much fun :) Reminds me of The Incredible Machine sort of
 
B

Burner

Member
Oct 25, 1999
85
0
0
doh I meant width and height
I'll attempt to post my code, but I think that it won't work properly.
maybe someone will have a different method of doing this, I'm sure that mine is not optimal, but I'm also sure that it is less then 140^mirrors running time

I think I probably could get better time by only checking for a solution after all the mirrors have been place.

The code should just look at cells that the laser beam passes through for putting mirrors in. It should reset the beam to as if it was coming off of the current mirror for each iteration.

It should do a depth first search.

It shouldn't get into a loop of mirrors so that the beam propogates infinitely (which unfortuneately can happen)

I primarilly did level 3 and level 23 (3 for testing, level 23 because I can't solve it)

3 should work, 23 takes quite a while, I think I've been running for 24 hours on a celeron@550 and I haven't made any noticeable progress.


<<
#include <stdio.h>

//row,column
int board[10][14];
int board2[10][14];
int counter=0;

class Beam {
private:
//must have a node that doesn't have any attachments or they will be lost
void AddTail(Beam *b) {
head->last->next=b;
head->last=b;
b->head=head;
b->last=NULL;
b->next=NULL;
};
public:
Beam() {head=this; next=NULL; last=this; r=0; c=0; d=0; printf("bad\n");}
Beam(int row, int col, int dir) {
r=row;
c=col;
d=dir;
head=this;
next=NULL;
last=this;
};
void AddTail(int row, int col, int dir) {
Beam *b=new Beam(row,col,dir);
AddTail(b);
};
~Beam() {
if(head!=this) delete head;
else if(next!=NULL) {
next->head=next;
next->last=last;
delete next;
}

};
void Print() {
if(head!=this) head->Print();
else {
Beam *b=this;
if(b==NULL) {
printf("Empty Beam\n");
return;
}
while(b!=NULL) {
printf("r=%d c=%d dir=%d\n",b->r,b->c,b->d);
b=b->next;
}
}
}

Beam * head;
Beam * last;
Beam * next;
int r,c,d;

};


#define BLANK 0
#define TARGET 1
#define BOMB 2
#define WALL 3
#define GUN_UP 4
#define GUN_UP_RIGHT 5
#define GUN_RIGHT 6
#define GUN_DOWN_RIGHT 7
#define GUN_DOWN 8
#define GUN_DOWN_LEFT 9
#define GUN_LEFT 10
#define GUN_UP_LEFT 11
#define ONEWAY_UP 12
#define ONEWAY_UP_RIGHT 13
#define ONEWAY_RIGHT 14
#define ONEWAY_DOWN_RIGHT 15
#define ONEWAY_DOWN 16
#define ONEWAY_DOWN_LEFT 17
#define ONEWAY_LEFT 18
#define ONEWAY_UP_LEFT 19
#define MIRROR_UP 20 //ie mirror opens facing up
#define MIRROR_UP_RIGHT 21
#define MIRROR_RIGHT 22
#define MIRROR_DOWN_RIGHT 23
#define MIRROR_DOWN 24
#define MIRROR_DOWN_LEFT 25
#define MIRROR_LEFT 26
#define MIRROR_UP_LEFT 27
#define PRISM_H_RIGHTUP 28 // _/
#define PRISM_H_LEFTUP 29 // \_
// \ _
#define PRISM_V_UPLEFT 30 // |
// /
#define PRISM_V_UPRIGHT 31 // |
#define BEAM 32

void printBoard()
{
for( int i=0; i<10; i++) {
for( int j=0; j<14; j++) {
switch(board[j]) {
case BLANK:
printf(" "); break;
case TARGET:
printf("?"); break;
case WALL:
printf("x"); break;
case BOMB:
printf("@"); break;
case GUN_UP: case GUN_UP_RIGHT: case GUN_RIGHT:
case GUN_DOWN_RIGHT: case GUN_DOWN: case GUN_DOWN_LEFT:
case GUN_LEFT: case GUN_UP_LEFT:
printf("G"); break;
case MIRROR_UP: case MIRROR_UP_RIGHT: case MIRROR_RIGHT:
case MIRROR_DOWN_RIGHT: case MIRROR_DOWN: case MIRROR_DOWN_LEFT:
case MIRROR_LEFT: case MIRROR_UP_LEFT:
printf("M"); break;
case ONEWAY_UP: case ONEWAY_UP_RIGHT: case ONEWAY_RIGHT:
case ONEWAY_DOWN_RIGHT: case ONEWAY_DOWN: case ONEWAY_DOWN_LEFT:
case ONEWAY_LEFT: case ONEWAY_UP_LEFT:
printf("A"); break;
case PRISM_H_RIGHTUP: case PRISM_H_LEFTUP:
case PRISM_V_UPLEFT: case PRISM_V_UPRIGHT:
printf("P"); break;

case BEAM:
printf("*");
}
}
printf("\n");
}
}
void printBoard2()
{
for( int i=0; i<10; i++) {
for( int j=0; j<14; j++) {
switch(board2[j]) {
case BLANK:
printf(" "); break;
case TARGET:
printf("?"); break;
case WALL:
printf("x"); break;
case BOMB:
printf("@"); break;
case GUN_UP: case GUN_UP_RIGHT: case GUN_RIGHT:
case GUN_DOWN_RIGHT: case GUN_DOWN: case GUN_DOWN_LEFT:
case GUN_LEFT: case GUN_UP_LEFT:
printf("G"); break;
case MIRROR_UP: case MIRROR_UP_RIGHT: case MIRROR_RIGHT:
case MIRROR_DOWN_RIGHT: case MIRROR_DOWN: case MIRROR_DOWN_LEFT:
case MIRROR_LEFT: case MIRROR_UP_LEFT:
printf("M"); break;
case ONEWAY_UP: case ONEWAY_UP_RIGHT: case ONEWAY_RIGHT:
case ONEWAY_DOWN_RIGHT: case ONEWAY_DOWN: case ONEWAY_DOWN_LEFT:
case ONEWAY_LEFT: case ONEWAY_UP_LEFT:
printf("A"); break;
case PRISM_H_RIGHTUP: case PRISM_H_LEFTUP:
case PRISM_V_UPLEFT: case PRISM_V_UPRIGHT:
printf("P"); break;

case BEAM:
printf("*");
}
}
printf("\n");
}
}

//returns direction that it leaves a cell
int test(int r, int c, int dir) {
//printf("in test\n");
int object=board[r][c];
if(object==0 || object==1)
return dir;
//passes a one way thingy
if(object>11 && object<20 && (object-dir)==12)
return dir;

switch(object) {
case MIRROR_UP:
if(dir==3) return 1;
if(dir==5) return 7;
break;
case MIRROR_UP_RIGHT:
if(dir==4) return 2;
if(dir==6) return 0;
break;
case MIRROR_RIGHT:
if(dir==5) return 3;
if(dir==7) return 1;
break;
case MIRROR_DOWN_RIGHT:
if(dir==6) return 4;
if(dir==0) return 2;
break;
case MIRROR_DOWN:
if(dir==7) return 5;
if(dir==1) return 3;
break;
case MIRROR_DOWN_LEFT:
if(dir==0) return 6;
if(dir==2) return 4;
break;
case MIRROR_LEFT:
if(dir==1) return 7;
if(dir==3) return 5;
break;
case MIRROR_UP_LEFT:
if(dir==2) return 0;
if(dir==4) return 6;
break;
case PRISM_H_RIGHTUP:
if(dir==2) return 1;
if(dir==6) return 5;
if(dir==5) return 6;
if(dir==1) return 2;
break;
case PRISM_H_LEFTUP:
if(dir==2) return 3;
if(dir==6) return 7;
if(dir==7) return 6;
if(dir==3) return 2;
break;
case PRISM_V_UPLEFT:
if(dir==0) return 7;
if(dir==4) return 3;
if(dir==7) return 0;
if(dir==3) return 4;
break;
case PRISM_V_UPRIGHT:
if(dir==0) return 1;
if(dir==4) return 5;
if(dir==5) return 4;
if(dir==1) return 0;
break;
default:
break;
}
//beam is stopped by something
return -1;
}
#define PRISM_H_RIGHTUP 28 // _/
#define PRISM_H_LEFTUP 29 // \_
// \ _
#define PRISM_V_UPLEFT 30 // |
// /
#define PRISM_V_UPRIGHT 31 // |
void initboard(int problem, int &r, int &c, int &d)
{
for( int i=0; i<10; i++) {
for ( int j=0; j<14; j++) {
board[j]=0;
}
}
if(problem==23) {


board[0][2]=ONEWAY_LEFT;
board[0][4]=BOMB;
board[0][5]=BOMB;
board[0][6]=WALL;
board[0][7]=BOMB;
board[0][10]=TARGET;
board[0][11]=BOMB;
board[1][4]=ONEWAY_DOWN_LEFT;
board[1][6]=WALL;
board[1][10]=ONEWAY_RIGHT;
board[2][3]=ONEWAY_LEFT;
board[2][6]=WALL;
board[2][7]=ONEWAY_UP;
board[2][9]=ONEWAY_DOWN_LEFT;
board[2][12]=TARGET;
board[3][1]=TARGET;
board[3][2]=ONEWAY_LEFT;
board[3][6]=WALL;
board[3][9]=BOMB;
board[3][11]=ONEWAY_UP_RIGHT;
board[4][1]=GUN_RIGHT;
board[4][6]=TARGET;
board[4][10]=TARGET;
board[5][1]=ONEWAY_DOWN_RIGHT;
board[5][6]=WALL;
board[5][8]=BOMB;
board[5][11]=ONEWAY_DOWN_RIGHT;
board[6][0]=ONEWAY_UP;
board[6][3]=ONEWAY_UP;
board[6][4]=ONEWAY_DOWN_LEFT;
board[6][5]=ONEWAY_UP;
board[6][6]=WALL;
board[7][3]=TARGET;
board[7][6]=WALL;
board[7][10]=BOMB;
board[8][3]=ONEWAY_UP;
board[8][8]=BOMB;
board[9][2]=BOMB;
board[9][6]=WALL;
board[9][8]=TARGET;
board[9][10]=WALL;
board[9][11]=BOMB;

r=4;
c=1;
d=2;
}
if (problem==3) {
board[2][7]=TARGET;
board[3][6]=TARGET;
board[3][8]=TARGET;
board[4][0]=TARGET;
board[4][7]=TARGET;
board[9][6]=GUN_UP;
r=9;
c=6;
d=0;
}
for( int i=0; i<10; i++) {
for ( int j=0; j<14; j++) {
board2[j]=board[j];
}
}

}

bool CheckDuplicate(int r,int c, int dir,Beam *b)
{
Beam *beam=b->head;
for(Beam *tmp=beam; tmp->next!=NULL; tmp=tmp->next){
if(tmp->r==r && tmp->c==c && tmp->d==dir)
return true;
}
return false;
}

//assumes the beam is coming from the r,c cell pointing in dir direction
//0=up, 2=right, 4=down, 6=left
Beam* createBeam(int r, int c, int dir)
{
Beam *b=NULL;

int newdir=0;
while(newdir!=-1) {
newdir=-1;
switch (dir) {
case 0: //up
if(r>0) {
newdir=test(r-1,c,dir);
if(newdir!=-1) {
r=r-1;
dir=newdir;
}
}
break;
case 1: //up-right
if(r>0 && c<13) {
newdir=test(r-1,c+1,dir);
if(newdir!=-1) {
c=c-1;
r=r+1;
dir=newdir;
}
}
break;
case 2: //right
if(c<13) {
newdir=test(r,c+1,dir);
if(newdir!=-1) {
c=c+1;
dir=newdir;
}
}
break;
case 3: //down-right
if(c<13 && r<9) {
newdir=test(r+1,c+1,dir);
if(newdir!=-1) {
c=c+1;
r=r+1;
dir=newdir;
}
}
break;
case 4: //down
if(r<9) {
newdir=test(r+1,c,dir);
if(newdir!=-1) {
r=r+1;
dir=newdir;
}
}
break;
case 5: //down-left
if(c>0 && r<9) {
newdir=test(r+1,c-1,dir);
if(newdir!=-1) {
c=c-1;
r=r+1;
dir=newdir;
}
}
break;
case 6: //left
if(c>0) {
newdir=test(r,c-1,dir);
if(newdir!=-1) {
c=c-1;
dir=newdir;
}
}
break;
case 7: //left-up
if(c>0 && r>0) {
newdir=test(r-1,c-1,dir);
if(newdir!=-1) {
c=c-1;
r=r-1;
dir=newdir;
}
}
break;
default:
printf("Error in direction\n");
break;
}
if(newdir!=-1) {
if(b==NULL) {
b=new Beam(r,c,dir);
} else {
if(CheckDuplicate(r,c,dir,b))
return b;
b->AddTail(r,c,dir);
}
} else {
//printf("no new direction\n");
}

// printf("next is %d %d %d %d\n",r,c,dir,newdir);
}
return b;
}

bool Solved(int startrow, int startcol, int startdir)
{
// printf("in solved \n");
Beam* currentBeam=createBeam(startrow,startcol,startdir);
//if(currentBeam!=NULL)
//currentBeam->Print();
for( Beam* b=currentBeam; b!=NULL; b=b->next) {
board2[b->r][b->c]=BEAM;
}
// printBoard2();
//for 3

/* if( board2[2][7]==BEAM &&
board2[3][6]==BEAM &&
board2[3][8]==BEAM &&
board2[4][0]==BEAM &&
board2[4][7]==BEAM ) {*/
//for 23

if (board2[0][10]==BEAM &&
board2[2][12]==BEAM &&
board2[3][1]==BEAM &&
board2[4][6]==BEAM &&
board2[4][10]==BEAM &&
board2[7][3]==BEAM &&
board2[9][8]==BEAM) {
delete currentBeam;
return true;
}
for( Beam* b=currentBeam; b!=NULL; b=b->next) {
board2[b->r][b->c]=board[b->r][b->c];
}
delete currentBeam;
return false;
}
bool FindSolutionRR(int numMirrors, int numPrisms, int startrow,
int startcol, int startdir)
{
// printf("in find solution\n");
if(numMirrors==0 && numPrisms==0) return false;
//printf("mirrors %d prisms %d \n",numMirrors, numPrisms);
//counter++;
Beam* currentBeam=createBeam(startrow,startcol,startdir);
for( Beam* b=currentBeam; b!=NULL; b=b->next) {
//for each thing the beam goes through
if(board[b->r][b->c]==BLANK) {
if(numMirrors>0) {
//add a mirror here
for( int i=MIRROR_UP; i<=MIRROR_UP_LEFT; i++) {
board[b->r][b->c]=i;
if(Solved(startrow,startcol,startdir) ||
FindSolutionRR(numMirrors-1, numPrisms, startrow, startcol,
startdir)){
printf("mirror %d %d %d\n",b->r,b->c,i-MIRROR_UP);
delete currentBeam;
return true;
}
}
}
if(numPrisms>0) {
//add a prism here
for( int i=PRISM_H_RIGHTUP; i<=PRISM_V_UPRIGHT; i++) {
board[b->r][b->c]=i;
if(Solved(startrow,startcol,startdir) ||
FindSolutionRR(numMirrors, numPrisms-1, startrow, startcol,
startdir)){
printf("prism %d %d %d\n",b->r,b->c,i-PRISM_H_RIGHTUP);
delete currentBeam;
return true;
}
}
}
board[b->r][b->c]=BLANK;
}
}
//counter--;
//printf("counter %d\n",counter);
delete currentBeam;
return false;
}

bool FindSolutionR(int numMirrors, int numPrisms, int startrow,
int startcol, int startdir)
{
// printf("in find solution\n");
if(numMirrors==0 && numPrisms==0) return false;
//printf("mirrors %d prisms %d \n",numMirrors, numPrisms);
//counter++;
Beam* currentBeam=createBeam(startrow,startcol,startdir);
for( Beam* b=currentBeam; b!=NULL; b=b->next) {
//for each thing the beam goes through
if(board[b->r][b->c]==BLANK) {
if(numMirrors>0) {
//add a mirror here
for( int i=MIRROR_UP; i<=MIRROR_UP_LEFT; i++) {
board[b->r][b->c]=i;
printf("Level 2 Mirror %d\n",i-MIRROR_UP);
if(Solved(startrow,startcol,startdir) ||
FindSolutionRR(numMirrors-1, numPrisms, startrow, startcol,
startdir)){
printf("mirror %d %d %d\n",b->r,b->c,i-MIRROR_UP);
delete currentBeam;
return true;
}
}
}
if(numPrisms>0) {
//add a prism here
for( int i=PRISM_H_RIGHTUP; i<=PRISM_V_UPRIGHT; i++) {
board[b->r][b->c]=i;
printf("Level 2 Prism %d\n",i-MIRROR_UP);
if(Solved(startrow,startcol,startdir) ||
FindSolutionRR(numMirrors, numPrisms-1, startrow, startcol,
startdir)){
printf("prism %d %d %d\n",b->r,b->c,i-PRISM_H_RIGHTUP);
delete currentBeam;
return true;
}
}
}
board[b->r][b->c]=BLANK;
}
}
//counter--;
//printf("counter %d\n",counter);
delete currentBeam;
return false;
}

bool FindSolution(int numMirrors, int numPrisms, int startrow,
int startcol, int startdir)
{
int counter=0;
// printf("in find solution\n");
if(numMirrors==0 && numPrisms==0) return false;
//printf("mirrors %d prisms %d \n",numMirrors, numPrisms);
//counter++;
Beam* currentBeam=createBeam(startrow,startcol,startdir);
for( Beam* b=currentBeam; b!=NULL; b=b->next) {
//for each thing the beam goes through
printf("counter is %d\n",counter);
counter++;
if(board[b->r][b->c]==BLANK) {
if(numMirrors>0) {
//add a mirror here
for( int i=MIRROR_UP; i<=MIRROR_UP_LEFT; i++) {
printf("Level 1 Mirror %d\n",i-MIRROR_UP);
board[b->r][b->c]=i;
if(Solved(startrow,startcol,startdir) ||
FindSolutionR(numMirrors-1, numPrisms, startrow, startcol,
startdir)){
printf("mirror %d %d %d\n",b->r,b->c,i-MIRROR_UP);
delete currentBeam;
return true;
}
}
}
if(numPrisms>0) {
//add a prism here
for( int i=PRISM_H_RIGHTUP; i<=PRISM_V_UPRIGHT; i++) {
printf("Prism %d\n",i);
board[b->r][b->c]=i;
if(Solved(startrow,startcol,startdir) ||
FindSolutionR(numMirrors, numPrisms-1, startrow, startcol,
startdir)){
printf("Level 1 prism %d %d %d\n",b->r,b->c,i-PRISM_H_RIGHTUP);
delete currentBeam;
return true;
}
}
}
board[b->r][b->c]=BLANK;
}
}
//counter--;
//printf("counter %d\n",counter);
delete currentBeam;
return false;
}

int main( int argv, char** argc)
{
int startrow, startcol,startdir;
//Beam *currentBeam;
//init board
initboard(23, startrow, startcol,startdir);
//done with init
printf("starting at r=%d c=%d d=%d\n",startrow, startcol,startdir);

// currentBeam=createBeam(startrow,startcol,startdir);
//printf("done creating starting beam\n");
//if(currentBeam!=NULL)
//currentBeam->Print();
printBoard();
printf("starting\n");
// currentBeam->Print();
//for 23
bool solution=FindSolution(7,4,startrow, startcol, startdir);
// for 3
//bool solution=FindSolution(3,0,startrow,startcol,startdir);
printf("there is a solution? %d\n",solution);
return 0;
}
 >>



edit fixed some bugs, enhanced printing somewhat
 
B

Burner

Member
Oct 25, 1999
85
0
0
I was hoping quote wouldn't kill spacing and stuff but I guess I was wrong

also I'm not sure if the prism code works or not as I never made a good test for it. (or even the mirrors...)
 
S

Shalmanese

Platinum Member
Sep 29, 2000
2,157
0
0
You know you did something wrong with the coding if you can figure out how to make take less time after its started running :)
 
You must log in or register to reply here.

TRENDING THREADS

COMPANY
RESOURCES
FOLLOW
Top Bottom