hello
following discussion between me and @sonata «pathétique» we have arrived at this week's challenge for the code guessing competition.
the challenge is: solve a maze.
submissions must be written in either C or python.
your program will be given a 10x10 grid of square cells, each of which is either a wall or not a wall. starting at the upper left corner, you must find a path to the lower right corner, moving only on cells that are not walls, and moving only north south east or west (ie you cannot move diagonally between cells). your program then has to return the sequence of moves required. (if the input has multiple valid solutions you can return any valid solution).
in C: your program should provide a function entry which takes an array of 100 ints, representing the input. cells are organised row-wise, from left to right then top to bottom; that is input[0] is the upper left corner, input[9] is the upper right corner, input[90] is the lower left corner and input[99] is the lower right corner. each value in the array will be 1 if that cell is a wall, and 0 if it is not a wall. no other values will be present in the input array.
the entry function must return a pointer/array of ints representing the path. (i don't care how it's allocated, i will just be casting whatever you return to an int pointer and then checking that). each value can be either 1 to represent going upwards, 2 to represent going right, 3 to represent going downwards, or 4 to represent going left. your output array must also be terminated with one value equal to 0; ie the value after the end of your path needs to be zero.
i will be compiling with gcc on debian. having your solution rely on UB etc is fine, but you do so at your own risk.
in python:
your function entry will be given an list of 100 bools, True representing a wall and False representing no wall, in the same ordering as the C description above. you must return a list of ints representing your path; each int can be 1 to represent going upwards, 2 to represent going right, 3 to represent going downwards, or 4 to represent going left. (there is no need for a terminator in python)
your solution will be run using python 3.9 on debian.
in both cases your solution given will actually be evaluated as a sequence of moves, not just statically compared to one solution. so you could include a sequence of up down up down up down, and as long as by the end of your solution you are at the correct place your solution will be ok.
if any of the moves try to move into a wall or outside of the 10x10 area, then your solution is immediately marked as invalid.
#include<stdlib.h>#include<stdio.h>enumpiss{up=1,right=2,down=3,left=4};structlinked_piss{enumpisspi;structlinked_piss*ss;};intmoves[5][2]={{0,0},{0,-1},{1,0},{0,1},{-1,0}};typedefintpiss_grid[100];intpiss_tile(piss_gridg,intx,inty){if(x<0||y<0||x>9||y>9)return1;elsereturng[(10*y)+x];}voiddisp_grid(piss_gridg){for(inti=0;i<100;i++){if(g[i]==1)printf("#");elseif(g[i]==2)printf("*");elseprintf(" ");if(i%10==9)printf("\n");}printf("\n");}int*to_result(conststructlinked_piss*p){// Prepare for ubq analysisint*final_piss=malloc(500);for(inti=0;p!=NULL;(p=p->ss)&&(i++)){final_piss[i]=p->pi;}returnfinal_piss;}structlinked_piss*attempt(piss_gridg,intix,intiy,enumpissm,intc){intx=ix+moves[m][0];inty=iy+moves[m][1];// It is not possible to go in wallsif(piss_tile(g,x,y)==1||c>500)returnNULL;if(x==9&&y==9){structlinked_piss*p=malloc(sizeof(structlinked_piss));structlinked_pissempty={0};*p=empty;returnp;}/* g[(10 * y) + x] = 2; disp_grid(g); */// Let's check all of the directionsfor(inti=1;i<=4;i++){if(x+moves[i][0]==ix&&y+moves[i][1]==iy)continue;// Recursive recursionstructlinked_piss*guess=attempt(g,x,y,i,c+1);if(guess!=NULL){structlinked_piss*p=malloc(sizeof(structlinked_piss));structlinked_pissnew={i,guess};*p=new;returnp;}}returnNULL;}int*entry(piss_gridg){intx=0;inty=0;structlinked_piss*p=attempt(g,0,0,0,0);if(p!=NULL)returnto_result(p);elsereturnNULL;}// We will free() nothing!
defentry(iAr):# Bad Tremaux implcPos=0;pPos=Nonepsgs=[set()foriinrange(100)]defisIs(pos,prev):# Not confusing at allpaths={k:0forkin(pos-10,pos-1,pos+1,pos+10)}forkinpaths:try:ifnotiAr[k]:paths[k]=1exceptIndexError:passpaths[prev]=0ifpos<10:paths[pos-10]=0ifnotpos%10:paths[pos-1]=0ifpos%10==9:paths[pos+1]=0return[kforkinpathsifpaths[k]]# Should I rename this? ... NahdefisV(pos):foriinpsgs[pos]:ifi:returnTruereturnFalsedefisB(pos,prev):foriinpsgs[pos]:ifi==prev:returnTruereturnFalse# I hate this so muchwhilecPos!=99:paths=isIs(cPos,pPos)ifisV(cPos):ifisB(cPos,pPos):unv=list(filter(lambday:notisV(y),paths))ifnotunv:unv=set(isIs(cPos,pPos))-psgs[cPos]pPos=cPoscPos=unv.pop()else:cPos,pPos=pPos,cPoselse:iflen(paths):pPos=cPoscPos=paths.pop()else:cPos,pPos=pPos,cPospsgs[pPos].add(cPos)defcompare(pos,nxt):ifnxt==pos-10:return1elifnxt==pos+1:return2elifnxt==pos+10:return3else:return4cPos=0;oAr=[]whilecPos!=99:nPos=tuple(psgs[cPos])[-1]oAr.append(compare(cPos,nPos))cPos=nPosreturnoAr
# apiomemetic beeoforms, utterly.defentry(k):# æ input formatk=list(map(int,k))k=[k[:10],k[10:20],k[20:30],k[30:40],k[40:50],k[50:60],k[60:70],k[70:80],k[80:90],k[90:100]]d=[[0]*10foriinrange(10)]d[0][0]=0v=[[0]*10foriinrange(10)]q=[(0,0)]ok=lambday,x:x>=0andx<10andy>=0andy<10andnotk[y][x]# stage 1: generate distance matrixwhileq:y,x=q.pop()ifv[y][x]:continuev[y][x]=1fori,jin[(-1,0),(0,-1),(0,1),(1,0)]:ifok(y+i,x+j)andnotv[y+i][x+j]:d[y+i][x+j]=d[y][x]+1q.insert(0,(y+i,x+j))# stage 2: get the pathr=[(9,9)]y,x=9,9whiley!=0orx!=0:D=d[y][x]fori,jin[(-1,0),(0,-1),(0,1),(1,0)]:ifok(y+i,x+j)andd[y+i][x+j]==D-1:r.append((y+i,x+j))y+=ix+=jr=list(reversed(r))# stage 3: convert it into the æ output formatq=[]foriinrange(1,len(r)):dy=r[i][0]-r[i-1][0]dx=r[i][1]-r[i-1][1]if(dy,dx)==(1,0):q.append(3)if(dy,dx)==(-1,0):q.append(1)if(dy,dx)==(0,-1):q.append(4)if(dy,dx)==(0,1):q.append(2)returnq# author: bad imitation of gollark
#include<stdint.h>#include<stdio.h>#include<string.h>#include<stdlib.h>staticconstchar*conststates=" #*.";staticconstintd[]={-12,1,12,-1};// Execute n steps of a Life-like cellular automaton with arbitrary states (Generations rules), given an initial state and a ruleset.voiddo_ca(uint8_tbirth,uint8_tsurvive,uint8_tnstates,intwidth,intheight,uint8_tstate[height][width],intn){charneighbor_data[height+2][width+2];char(*neighbors)[width+2]=(void*)&neighbor_data+height+1;for(;n--;){memset(neighbors,0,(height+1)*(width+2)-1);for(inty=0;y<height;y++)for(intx=0;x<width;x++)if(state[y][x]==1){neighbors[y-1][x-1]++;neighbors[y-1][x]++;neighbors[y-1][x+1]++;neighbors[y][x-1]++;neighbors[y][x+1]++;neighbors[y+1][x-1]++;neighbors[y+1][x]++;neighbors[y+1][x+1]++;}for(inty=0;y<height;y++)for(intx=0;x<width;x++){uint8_tcstate=state[y][x];switch(cstate){case0:if(birth>>(8-neighbors[y][x])&1)state[y][x]=1;break;case1:if(!(survive>>(8-neighbors[y][x])&1))state[y][x]=(cstate+1)%nstates;break;default:state[y][x]=(cstate+1)%nstates;}}}}voidprint_state(intwidth,intheight,uint8_tstate[height][width]){for(inty=0;y<height;y++){for(intx=0;x<width;x++)putchar(states[state[y][x]]);putchar('\n');}}int*entry(intinput[100]){uint8_tstate[10][10];for(inty=0;y<10;y++)for(intx=0;x<10;x++){state[y][x]=input[y*10+x];}print_state(10,10,state);// run as CGoL for a bitdo_ca(0x20,0x30,2,10,10,state,3);print_state(10,10,state);// Seeds is explosive; only use one generationdo_ca(0x40,0x00,2,10,10,state,1);// time for its sibling, Brian's Braindo_ca(0x40,0x00,3,10,10,state,4);print_state(10,10,state);// do you like sci-fi?do_ca(0x38,0x40,4,10,10,state,2);print_state(10,10,state);// that was pretty fun. anyway...int*p=calloc(100,sizeof(int)),t[144]={[0...143]=1};for(inty=0;y<10;y++)for(intx=0;x<10;x++)t[y*12+x+13]=input[y*10+x];#define T(v,s)for(i=0;i<4;i++)if(t[n+d[i]]==v){t[n]=s;n+=d[i];p[l++]=i+1;goto e;}for(inti,l=0,n=13;n!=130;){T(0,2)T(2,1)e:;}returnp;}
defentry(s):m=[]foriinrange(0,100,10):m.append(s[i:i+10])# 1 up 2 right 3 down 4 leftdefk(i,j,d):ifi==9andj==9:globalrr=dreturn1elifm[i][j]==1:return0elifm[i][j]==3:return0m[i][j]=3ifi<9andk(i+1,j,d+[3]):return1elifi>0andk(i-1,j,d+[1]):return1elifj<9andk(i,j+1,d+[2]):return1elifj>0andk(i,j-1,d+[4]):return1return0k(0,0,[])returnr
defentry(THUNDER):#fast guitar riffThunder=globals().update#ooowhoaooowhoooooowhoaoooThunder({"Texas":range,"I_was":sorted,"thunderstruck":lambdas:eval("lambda thunder:"+s),"ooo":"thunderstruck","ooowhoaooowhoooooowhoaooo":len,"broke":all,"the_rules":"p","lay":"ed","all_the_fools":max,"yeah yeah":"yeah","they_blew_our":min,"ds":"and I was shaking at the knees"})Thunder({"yeeeeeah":thunderstruck("~-thunder"),"THUNDER":THUNDER,"STRUCK":thunderstruck("""[thunder[baby-baby](baby) for baby in Texas(thunder[ ooowhoaooowhoooooowhoaooo(the_rules)], thunder[ ooowhoaooowhoooooowhoaooo(lay)])]"""),"whoawhoawhoa":thunderstruck("-~thunder"),"yeah_its_alright":thunderstruck("[]"),"were_doin_fine":"yeah them ladies were too kind","THUNDÉR":dict})#ooowhoaooowhoooooowhoaoooThunder(𝐓HUNDÉR(STRUCK((thunderstruck("(ooo[:thunder]+ooo[thunder].upper()+ooo[𝕨𝕙𝕠𝕒𝕨𝕙𝕠𝕒𝕨𝕙𝕠𝕒(thunder):],thunder)"),ooowhoaooowhoooooowhoaooo(""),ooowhoaooowhoooooowhoaooo(ooo)))))Thunder({"ṪḦÜṄḊЁṚ":thunderstruck("all_the_fools(%d-thunder[%d],%d-thunder[%d])"%(thunderstRuck,tHunderstruck,thunderstRuck,Thunderstruck)),"Baby":["You've been",thunderstruck("(thunder[%d],𝕪𝕖𝕖𝕖𝕖𝕖𝕒𝕙(thunder[%d]))"%(Thunderstruck,tHunderstruck)),thunderstruck("(𝕨𝕙𝕠𝕒𝕨𝕙𝕠𝕒𝕨𝕙𝕠𝕒(thunder[%d]),thunder[%d])"%(Thunderstruck,tHunderstruck)),thunderstruck("(thunder[%d],𝕨𝕙𝕠𝕒𝕨𝕙𝕠𝕒𝕨𝕙𝕠𝕒(thunder[%d]))"%(Thunderstruck,tHunderstruck)),thunderstruck("(𝕪𝕖𝕖𝕖𝕖𝕖𝕒𝕙(thunder[%d]),thunder[%d])"%(Thunderstruck,tHunderstruck))],"I_was_caught_in_the":thunderstruck("thunder[%d][%d]"%(Thunderstruck,tHunderstruck)),"the":thunderstruck("thunder[%d][%d]"%(thUnderstruck,Thunderstruck))})Thunder({"THUNDER":STRUCK((thunderstruck("THUNDER[thunder*thunderstrUck:thunder*thunderstrUck+thunderstrUck]+[Thunderstruck]"),Thunderstruck,thunderstrUck))+[[Thunderstruck]*thunderstrUck]})#bridge with guitar solo to 11Thunder({"youve_been":thunderstruck("""thunder if I_was_caught_in_the(thunder)==( thunderstRuck,thunderstRuck) else youve_been((the(thunder), thunder[tHunderstruck]+[the(thunder)[tHunderstruck]], I_was(thunder[thUnderstruck][tHunderstruck:]+[(ṪḦÜṄḊЁṚ(Baby[baby]( the(thunder)[tHunderstruck])),Baby[baby](the(thunder)[ tHunderstruck]),the(thunder)[thUnderstruck]+[baby]) for baby in Texas( tHunderstruck,thundErstruck) if broke([they_blew_our(Baby[baby](the(thunder)[ tHunderstruck]))>=Thunderstruck,all_the_fools(Baby[baby](the(thunder)[tHunderstruck]))<thunderstrUck, not Baby[baby](the(thunder)[tHunderstruck]) in thunder[tHunderstruck],not THUNDER[Baby[baby](the(thunder)[tHunderstruck])[tHunderstruck]][Baby[baby](the(thunder)[tHunderstruck])[Thunderstruck]]])])))""")})returnyouve_been(((thunderstrucK,(thunderstrucK,thunderstrucK),yeah_its_alright(were_doin_fine)),yeah_its_alright(were_doin_fine),[(ṪḦÜṄḊЁṚ((Thunderstruck,Thunderstruck)),(Thunderstruck,Thunderstruck),yeah_its_alright(were_doin_fine))]))[Thunderstruck][thUnderstruck]#could I come again please?
# WARNING: Soulless OOP Ahead# So lifeless that all it does is follow the wall.# Even a Dementor could find their way out of a labyrinth.classMaze:@staticmethoddefpreprocess(maze):total,chunk=len(maze),int(len(maze)**.5)return[maze[i:i+chunk]foriinrange(0,total,chunk)]def__init__(self,maze):self.maze=self.preprocess(maze)self.x_dim=len(self.maze[-1])self.y_dim=len(self.maze)defis_wall(self,pos):x,y=posreturnnot(-1<x<self.x_dim)or \
not(-1<y<self.y_dim)or \
self.maze[y][x]classMouse:compass=[lambdax,y:(x,y-1),lambdax,y:(x+1,y),lambdax,y:(x,y+1),lambdax,y:(x-1,y),]def__init__(self):self.x,self.y=0,0self.direction=1self.moves=[]defturn_right(self):self.direction=(self.direction+1)%4defturn_left(self):self.direction=(self.direction-1)%4defblock_ahead(self):returnself.compass[self.direction](self.x,self.y)defblock_on_right(self):returnself.compass[(self.direction+1)%4](self.x,self.y)defmove(self):next_move=self.block_ahead()self.moves+=[self.direction+1]self.x,self.y=next_movedefat_end(self,maze):return(self.x,self.y)==(maze.x_dim-1,maze.y_dim-1)defsolve_maze(self,maze):whilenotself.at_end(maze):ifnotmaze.is_wall(self.block_on_right()):self.turn_right()self.move()elifmaze.is_wall(self.block_ahead()):self.turn_left()else:self.move()defentry(maze):mouse=Mouse()maze=Maze(maze)mouse.solve_maze(maze)returnmouse.moves
post a comment