Path: utzoo!attcan!utgpu!cs.utexas.edu!usc!wuarchive!uunet!mcsun!ukc!axion!tharr!gombo
From: gombo@tharr.UUCP (Alun Jones)
Newsgroups: alt.sources.d
Subject: Re: Maze generation
Keywords: how-to maze generate program wanted
Message-ID: <1522@tharr.UUCP>
Date: 19 Dec 90 13:05:27 GMT
References: <1215@syacus.acus.oz> <1990Dec13.190759.9297@craycos.com> <1990Dec14.001604.20990@informix.com> <1990Dec17.142513@avahi.inria.fr> <A=J^{4+@rpi.edu>
Reply-To: gombo@tharr.UUCP (Alun Jones)
Organization: Power Microsystems Ltd
Lines: 53

Someone recently put up the obfuscated c code maze generator.
(Or rather, they put up a clear version of it.)
I'm going to respond with a program that takes the output from that maze 
generator, and solves the maze.
In fact, if you feed it ANY SIZE maze - even MULTIPLY CONNECTED, it will find
a best route through it. (In this context, through means from the hole in top
left, to the hole in bottom right.)
I think it's quite cute, but it's not really good enough for the obfuscated
c code contest - unless there's a category for 'Best program using output
from a previous winner'.

Oh, and one more thing - there doesn't yet exist a clear version of this
program - I debug it in this state.  You're welcome to distribute it - I'm
not proud. :-)  Call it pd, call it whatever you will - just don't call it
copyright.
---------------------------Code begins after this line.---------------
#define _ define
#_ B switch(getchar()){D
#_ D case
#_ E >>1
#_ F(x)free((char *)x)
#_ H ;for(
#_ I (e&2?-1:1)
#_ J e&1?0:
#_ K (P("\n"),
#_ P(a)j=write(1,a,1)
#_ Q(a,b,c)P(a+((b)>>4&1)+((c)&2))
#_ S struct
#_ V =p->p
#_ W while(
#_ X(a)(S a *)malloc(sizeof(S a))
#_ Y (Q("## .",Z
#_ Z M[g
char *malloc();void free();
main(){int M[5000],C=0,R=0,g,e,j;S d{int p;S d*l;}*p,*n;S q{S d*g;S q*n;}*q,*o,
*r H;getchar()!='\n';C++)H e=(C>>=1);e--;)M[e]=!(M[e+C]=13);M[!(Z=C]=15)]=8;W!R
){B-1:R=g-1;break;D'|':Z-1]&=~1;Z]&=~4;}B'_':Z]&=~8;D' ':Z+C]=13|(Z]>>2);g++;}}
o=q=X(q);(p=X(d))->p=0;W(g V)!=R){Z]|=32 H e=~0;++e<4;)if(1<<e&Z])if(
M[(n=X(d))->p V+(J I)+C*(~J-I)]&32)F(n);else{n->l=p;o->g=n;o=o->n=X(q);}p=
(r=q)->g;q=q->n;F(r);}Z V]|=16;W g)Z=(p=p->l)->p]|=16;M[R+C]=16 H g=e=0;e<R;
e+=C){H;!e||Y]&Z-1],Z]E)),(g++<e+C||K 0));(Q(" .",Z-1],0)))H g=e;Y],(Z]&Z+C]&
(Z]&Z-1])E)E),(g++<e+C||K g--,0)));Y-1]&Z+C-1],Z-1]>>2)));}return j;}
------------------------------Code ends above this line.-----------------
Oh, one thing - it doubles the width and height (in characters) it gets,
and uses # to mark the walls, . to mark the path from entry to exit.
There is another version for lineprinters that overprints on the original maze
but I shan't post that.
-- 
Alun Jones - Unix Development Engineer - Welcom Software Technology Int'l.
My views are nothing whatsoever to do with the company I work for.
(That may be boring, but I feel safer for it.)

<-- tharr *free* public access to Usenet in the UK 0234 261804 -->