Moleskine notes for July 2008
Java left fold
Using Functional Java
public static <A, B> A fold(F<A, F<B, A>> f, A z, Iterable<B> xs) {
A p = z;
for (B x : xs) {
p = f.f(p).f(x);
}
return p;
}
A Regex
Match username (min 3, max 16, aAzZ_09) /^[a-zA-Z0-9_]{3,16}$/
Langs
- D
- OCaml
- Ruby
- Scheme (on tap)
- Corba
- Haskell
- ML
Popes scare me worse than clowns.
Broccoli
- Predicate functions end in ?
- underscore is a scope var lookup
- Function overloading
- Varargs
- OO is message based
Conventions
ClassNamemethod_name_scalar_variable__collection_variablepredicate?!undefineCONSTANT- Block-level elements (e.g. fundef, flow ctrl) enclosed in curly brackets
{} - Fact base views (e.g. rule LHS, bulk facts) enclosed in square brackets
[] - Function calls enclosed in parens
()
Some of the conventions are enforced by the language, others are merely standards.
Tech Books
- The Pencil: A History of Design and Circumstance
- The Design of Everyday Things
- The Codebreakers: The Story of Secret Writing
- Longitude: The True Story of a Lone Genius Who Solved the Greatest Scientific Problem of His Time
- The Making of the Atomic Bomb
Charles H. Moore
Yes indeed, I write Forth code every day. It is a joy to write a few simple words and solve a problem. As brain exercise it far surpasses cards, crosswords or Sudoku; and is useful.
Prolog/Lisp/Prolog/Lisp Insanity
Using GNU Prolog
eval(X,O) :- defined(X,A), eval(A,O).
eval([X|T],O) :- defined(X,A), eval([A|T],O).
eval(X,X) :- number(X); X = t ; X = [].
eval([quote,X],X).
eval([lambda|X],[lambda|X]).
eval([define,X,Y],t) :- \+ defined(X,_), asserta(defined(X,Y)).
eval([cond],_) :- !, fail.
eval([cond,[H,A]|_],Z) :- eval(H,O), \+ O = [],!, eval(A,Z).
eval([cond,_|T],Z) :- eval([cond|T],Z),!.
eval([F|A],X) :- eval_list(A,Ae), apply(F,Ae,X),!.
eval_list([],[]).
eval_list([H|T],[Ho|To]) :- eval(H,Ho), eval_list(T,To).
apply(add,[X,Y],Z) :- Z is X + Y.
apply(add,[X,Y|T],Z) :- I is X + Y, apply(add,[I|T],Z).
apply(mul,[X,Y],Z) :- Z is X * Y.
apply(mul,[X,Y|T],Z) :- I is X * Y, apply(mul,[I|T],Z).
apply(sub,[X,Y],Z) :- Z is X - Y.
apply(div,[X,Y],Z) :- Z is X / Y.
apply(mod,[X,Y],Z) :- Z is X mod Y.
apply(pow,[X,Y],Z) :- Z is X ** Y.
apply(eq,[X,Y],t) :- X = Y.
apply(eq,[X,Y],[]) :- \+ X = Y.
apply(atom,[X],t) :- number(X);atom(X); X = [].
apply(atom,[[_|_]],[]).
apply(cons,[X|[Y]],[X|Y]).
apply(car,[[X|_]],X).
apply(cdr,[[_|T]],T).
apply([lambda,[],E],[],O) :- eval(E,O).
apply([lambda,[A|Ta],E],[L|Tl],O) :- subst(A,[quote,L],E,E2), apply([lambda,Ta,E2],Tl,O).
subst(_,_,[],[]).
subst(A,B,[A|T],[B|L]) :- subst(A,B,T,L).
subst(A,B,[H|T],[H2|L]) :- subst(A,B,H,H2),subst(A,B,T,L).
subst(A,B,A,B).
subst(_,_,X,X).
% gprolog
:- predicate_property(defined,dynamic).
% swi prolog
:- dynamic defined/2.
defined(_,[]) :- !,fail.
lisp([
[define,null,[lambda,[x],[eq,x,[quote,[]]]]],
[define,and,[lambda,[x,y],[cond,[x,[cond,[y,t],[t,[quote,[]]]]],[t,[quote,[]]]]]],
[define,not,[lambda,[x],[cond,[x,[quote,[]]],[t,t]]]],
[define,append,[lambda,[x,y],[cond,[[null,x],y],[t,[cons,[car,x],[append,[cdr,x],y]]]]]],
[define,list,[lambda,[x,y],[cons,x,[cons,y,[quote,[]]]]]],
[define,pair,[lambda,[x,y],[cond,[[and,[null,x],[null,y]],[quote,[]]],[[and,[not,[atom,x]],[not,[ato
m,y]]],[cons,[list,[car,x],[car,y]],[pair,[cdr,x],[cdr,y]]]]]]],
[define,assoc,[lambda,[x,y],[cond,[[eq,x,[car,[car,y]]],[car,[cdr,[car,y]]]],[t,[assoc,x,[cdr,y]]]]]
],
[define,evcon,[lambda,[c,a],[
cond,[[eval,[caar,c],a],[eval,[cadar,c],a]],[t,[evcon,[cdr,c],a]]
]]],
[define,eval,[lambda,[e,a],[
cond,
[[atom,e],[assoc,e,a]],
[[atom,[car,e]],[cond,
[[eq,[car,e],[quote,quote]],[cadr,e]],
[[eq,[car,e],[quote,atom]],[atom,[eval,[cadr,e],a]]],
[[eq,[car,e],[quote,eq]],[eq,[eval,[cadr,e],a],[eval,[caddr,e],a]]],
[[eq,[car,e],[quote,car]],[car,[eval,[cadr,e],a]]],
[[eq,[car,e],[quote,cdr]],[cdr,[eval,[cadr,e],a]]],
[[eq,[car,e],[quote,cons]],[cons,[eval,[cadr,e],a],[eval,[caddr,e],a]]],
[[eq,[car,e],[quote,cond]],[evcon,[cdr,e],a]],
[t,[eval,[cons,[assoc,[car,e],a],[cdr,e]],a]]
]],
[[eq,[caar,e],[quote,label]],
[eval,[cons,[caddar,e],[cdr,e]],[cons,[list,[cadar,e],[car,e]],a]]
],
[[eq,[caar,e],[quote,lambda]],
[append,[pair,[cadar,e],[evlis,[cdr,e],a]],a]
]]]],
[define,evlis,[lambda,[m,a],[
cond,[[null,m],[quote,[]]],[t,[cons,[eval,[car,m],a],[evlis,[cdr,m],a]]]
]]],
[define,cadr,[lambda,[x],[car,[cdr,x]]]],
[define,caddr,[lambda,[x],[car,[cdr,[cdr,x]]]]],
[define,cadar,[lambda,[x],[car,[cdr,[car,x]]]]],
[define,caddar,[lambda,[x],[car,[cdr,[cdr,[car,x]]]]]]
]).
load :- lisp(X), eval_list(X,_)
paren("(").
paren(")").
digit("0") --> "0".
digit("1") --> "1".
digit("2") --> "2".
digit("3") --> "3".
digit("4") --> "4".
digit("5") --> "5".
digit("6") --> "6".
digit("7") --> "7".
digit("8") --> "8".
digit("9") --> "9".
space(" ") --> " ".
space("\t") --> "\t".
space("\n") --> "\n".
identifier_char(X) :-
\+ space(X, _, _),
\+ paren(X),
\+ digit(X, _, _).
ws --> space(_).
ws --> space(_), ws.
ows --> space(_), ows.
ows --> [].
program([H|T]) --> sexp(H), ows, program(T).
program([H]) --> sexp(H).
sexp(L) --> "(", ows, sexp_list(L), ows, ")".
sexp([]) --> "(", ows, ")".
sexp_list([H|T]) --> (sexp(H); atom(H)), ws, sexp_list(T).
sexp_list([H]) --> sexp(H); atom(H).
atom(A) --> identifier(A) ; number(A).
identifier(I) --> [A], { identifier_char([A]) }, id_list(L), { atom_codes(I, [A|L]) }.
id_list([H|T]) --> [H], { identifier_char([H]) }, id_list(T).
id_list([]) --> [].
number(N) --> n_list(L), { number_codes(N, L) }.
n_list([H|T]) --> digit([H]), n_list(T).
n_list([H]) --> digit([H]).
Dyna-fgets
/*
* rfgets.c
* dynamically allocating fgets
* daniel.fischer at iitb.fraunhofer.de
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
enum { RFGETS_CHUNK_SIZE = 32 };
static char *rfg(FILE *f, size_t n)
{
char b[RFGETS_CHUNK_SIZE + 1], *const e = b + sizeof b - 2, *p;
size_t x;
/* store '\0' in the second-to-last character of b */
*e = '\0';
/* read into b */
if (!fgets(b, sizeof b, f))
return 0;
/* check for an incomplete line */
if (*e != '\0' && *e != '\n' && (p = rfg(f, n + (x = sizeof b - 1))))
return memcpy(p - x, b, x);
/* this is the end of the line (or EOF); allocate a buffer for the line */
else if ((p = malloc(n + (x = strlen(b) + 1))))
return memcpy(p + n, b, x);
else
return 0;
}
char *rfgets(FILE *f)
{
return rfg(f, 0);
}
int main(void)
{
char *line;
for (; line = rfgets(stdin); free(line))
printf(">>%s<<\n", line);
if (!feof(stdin))
puts("Error?");
return 0;
}
Low-power PC
- AMD Geode LX 800 Nano ITX Motherboard/CPU Combo $154
- 512MB 200-pin SO-DIMM DDR-400 $20
- 4GB compact flash card $14
- 12vdc AC/DC external wall wart $18
Broccoli Adoption
Preal(success) = F(perceived crisis / perceived pain of adoption)
Music to Investigate
- 1950s Jazz
- Ellington
- Monk
- Mingus
- Davis
- Dolphy
- Jean Luc Ponty
- Igor Stravinsky
- Purcell (English Aristocracy numbers)
- Chopin
- Mahler
Mephistophelean Maze
/* McCaughan's maximally marvellous moby maze making machine
* (c) 1995 Gareth McCaughan
*
* Usage: make-maze <x> <y> [<seed>]
*
* Make mazes using Olin Shivers's method (actually he didn't invent it):
* start with our set of cells; randomly knock down walls unless
* doing so introduces a cycle into the connectivity graph of our
* cells.
* Like Shivers, I'll do hexagonal mazes: it's more fun that way.
*
* If you are compiling under SunOS 4, put -DSUN on the command line.
* If you're compiling on some other platform, and any changes are
* needed to the program to make it compile correctly, please let
* me know and I'll create a Makefile and maybe even a configure script.
*/
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#ifdef SUN
# include <memory.h>
# include <sys/timeb.h>
# define Random random
# define SRandom srandom
# define CLOCKS_PER_SEC 1000000
# define difftime(x,y) (((double)x)-(double)y)
#else
# include <string.h>
# define Random rand /* Beware bad random number generators! */
# define SRandom srand
#endif
/* The cells are represented by an array pointed to by |cells|.
* A negative entry -N means "This cell is in a component of size N".
* A non-negative entry M means "This cell is in a component whose
* description you can find by looking in cell number M, which is
* another thing in the same component".
* If two cells are in the same component, then repeated chaining
* will lead you to the same final cell. Otherwise it won't. We
* avoid having to do too much chaining because every time we
* do any we go back and snap all the pointers so that they point
* straight at the final cell, IYSWIM. This trick is due to
* Tarjan.
*/
static int *cells;
/* If |x| is a cell, then |base(x)| is the cell one reaches by
* chaining along those pointers from |x|.
*/
static int base(int x) {
int y=cells[x],z=x;
while (y>=0) { z=y; y=cells[y]; }
/* Now we could just return |z|, but we snap pointers first. */
y=x; while (cells[y]>=0) { x=cells[y]; cells[y]=z; y=x; }
return z;
}
/* If |x| and |y| are base cells (i.e., |cells[x]<0| and |cells[y]<0|)
* then |unify(x,y)| puts |x| and |y| in the same component.
*/
static void unify(int x, int y) {
int sx=cells[x],sy=cells[y];
if (sx<sy) { /* X larger than Y */
cells[y]=x;
cells[x]=sx+sy;
}
else {
cells[x]=y;
cells[y]=sx+sy;
}
}
/* After making the maze, we need to convert it into a slightly
* more helpful format. To do this, we need another array of
* information about cells. Here's the information we need
* about each cell:
*/
typedef struct node {
int exits; /* bitmap representing exits -- see later */
int n_kids; /* number of descendants in tree */
struct node *kids[6]; /* and which ones they are */
/* The use of the following will become clear when you look
* at |analyse_tree|.
*/
struct node *first,*second,*furthest;
int length,distance;
} node;
/* And here's the array.
*/
node *nodes;
/* Exits from a cell are recorded in a bitmap. It only needs 8 bits,
* even allowing a little spare space. Thus:
*/
enum {
Up=1, Down=2, /* (k,l) -> (k,l+-1) delta=+-1 */
LDown=4, RDown=8, /* (k,l) -> (k+-1,l-1) delta=+-n_rows -1 */
LEq=16, REq=32, /* (k,l) -> (k+-1,l) delta=+-n_rows */
LUp=64, RUp=128 /* (k,l) -> (k+-1,l+1) delta=+-n_rows +1 */
};
/* Set up the |cells| array to contain |n| cells, each in its own
* component. Also set up the |nodes| array to contain |n| nodes,
* none of them with any children or any walls.
*/
static void init_cells(int n) {
cells=malloc(n*sizeof(int));
if (!cells) {
fprintf(stderr,"! I couldn't get enough memory for |cells|.\n");
exit(1);
}
memset(cells,-1,n*sizeof(int)); /* strictly, this isn't portable... */
nodes=calloc(n,sizeof(node));
if (!nodes) {
fprintf(stderr,"! I couldn't get enough memory for |nodes|.\n");
exit(1);
}
}
/* We need to go through the walls between the cells in a random order.
* To do this, we produce an array of structures representing walls,
* and sort it into random order.
*/
typedef struct wall {
struct wall *next; /* next wall after this one */
int lower; /* one neighbouring cell */
int higher; /* the other neighbouring cell */
} wall;
/* The array of walls is pointed to by |walls|. Amazing.
*/
static wall *walls;
/* And the first wall to be dealt with is pointed to by |first_wall|.
* (The last one is indicated by having a null pointer in its |next|
* field, of course.)
*/
static wall *first_wall;
/* More than one bit of the program needs to know how big the
* maze is. Here are the dimensions:
*/
static int n_columns;
static int n_rows;
/* Set up the |walls| array to represent the walls in an |m| by |n|
* hexagonal array of cells, and link them all together with their
* |next| fields.
* Now is a good time to think about how to describe our cells.
* I adopt Shivers's terminology: columns are numbered left to right,
* 0..m-1, and each column contains n cells 0..n-1. Columns 0,2,...
* are half a cell "lower" than columns 1,3,... .
* Thus, cell (k,l) is adjacent to cells (k,l+-1) above and below;
* and to cells (k+-1,l) and (k+-1,l-1) if k is even,
* or to cells (k+-1,l) and (k+-1,l+1) if k is odd.
* Except for the walls, of course: if any of those numbers are
* outside their ranges then the relevant cells just aren't there.
* The total number of walls is (m-1)*(2n-1) horizontally, plus
* m*(n-1) vertically: that comes to 2mn-m-2n+1+mn-m = 3mn-2m-2n+1.
* Cell (i,j) is number |n*i+j| in the |cells| array: so we go
* up the columns first, as it were.
* This is not efficient code, by the way; but it's not radically
* inefficient, and I don't think this is where the program spends
* most of its time.
*/
static void init_walls(int m, int n) {
int i,j;
int this;
wall *e;
walls=malloc((3*m*n-m-m-n-n+1)*sizeof(wall));
if (!walls) {
fprintf(stderr,"! I couldn't get enough memory for |walls|.\n");
exit(1);
}
e=walls;this=0;
for (i=0;i<m;++i) {
for (j=0;j<n;++j) {
/* Cell (i,j). */
if (i>0 && (j<n-1 || !(i&1))) { /* Northwest: */
e->next=e+1;
e->lower=this;
e->higher=this-n+(i&1);
++e;
}
if (j<n-1) { /* North: */
e->next=e+1;
e->lower=this;
e->higher=this+1;
++e;
}
if (i<m-1 && (j<n-1 || !(i&1))) { /* Northeast: */
e->next=e+1;
e->lower=this;
e->higher=this+n+(i&1);
++e;
}
++this;
}
}
if (e!=walls+3*m*n-m-m-n-n+1) {
fprintf(stderr,"! Gareth screwed up (%d != %d).\n",e-walls,3*m*n-m-m-n-n+1);
exit(1);
}
(e-1)->next=0; /* terminate list */
}
/* If this isn't going to give the exact same maze every time we run it,
* we'd better start up the random number generator in some way that
* actually depends on a few things.
* |init_rand()| does this: it should be called before |init_walls|.
* If |seed| is non-zero, we use that directly as our seed.
*/
static int seed;
static void init_rand(void) {
#ifdef SUN
struct timeb t;
int pid;
if (!seed) {
ftime(&t);
pid=getpid();
seed=(t.time<<8) + (t.millitm) + (pid<<16);
}
#else
seed=clock()+time(0);
#endif
seed=seed&0x7FFFFFFF;
SRandom(seed);
}
/* To sort the walls into order, we do three passes of 1024-way radix sort,
* putting things into random bins. This is equivalent to giving
* each wall a random 30-bit key and sorting into order, but doesn't
* require us to waste space storing keys we don't really want.
* So, here are the list heads for the sublists:
*/
static wall *head1[1024]; /* initialised to 0, say ANSI */
static wall *head2[1024]; /* ditto */
/* "Sort" the walls into random order.
*/
static void shuffle_walls(void) {
wall *p,*q;
int i,k;
/* First pass, into head1[]. */
p=walls; while (p) {
k=Random()&1023;
q=p->next;
p->next=head1[k]; head1[k]=p;
p=q;
}
/* Second pass, from head1[] into head2[]. */
for (i=0;i<1024;++i) {
p=head1[i]; head1[i]=0; while (p) {
k=Random()&1023;
q=p->next;
p->next=head2[k]; head2[k]=p;
p=q;
}
}
/* Third pass, from head2[] into head1[]. */
for (i=0;i<1024;++i) {
p=head2[i]; head2[i]=0; while (p) {
k=Random()&1023;
q=p->next;
p->next=head1[k]; head1[k]=p;
p=q;
}
}
/* Finally, link them all together again. */
q=0;
for (i=0;i<1024;++i) {
p=head1[i];
if (!p) continue;
if (q) { q->next=p; } else first_wall=p;
while (p) { q=p; p=p->next; }
}
/* We're done. */
}
/* Create the maze: for each wall, see whether its neighbours are
* already in the same component. If so, do nothing (removing this
* wall would mean that there were two paths between some pair of
* points). If not, remove the wall (by unlinking it from the list)
* and unify the components of the cells on either side.
* When we remove a wall, we also put an entry in the |exits| field
* of each corresponding |node|.
*/
static void create_maze(void) {
wall *p=first_wall;
wall *q=0; /* if |q!=0| then |q->next| is waiting to be filled in */
int x,y;
int delta;
while (p) {
x=base(p->lower); y=base(p->higher);
if (x!=y) {
unify(x,y); /* not connected: connect them */
/* Also, add exits. */
#define Add_exits(dh,dl) { \
nodes[p->higher].exits|=dh; nodes[p->lower].exits|=dl; }
delta=p->higher-p->lower;
if (delta==1) Add_exits(Down,Up)
else if (delta>0) switch(delta-n_rows) {
case -1: Add_exits(LUp,RDown); break;
case 0: Add_exits(LEq,REq); break;
case 1: Add_exits(LDown,RUp); }
else /* delta<0 */ switch(delta+n_rows) {
case -1: Add_exits(RUp,LDown); break;
case 0: Add_exits(REq,LEq); break;
case 1: Add_exits(RDown,LUp);
}
}
else { if (q) q->next=p; else first_wall=p; q=p; }/* connected: refrain from deleting wall */
p=p->next;
}
q->next=0; /* terminate list */
}
/* Build a subtree, starting at node |n| and including as much of the
* full tree as is possible without including anything already visited.
* Return 0 if this node has in fact already been visited; otherwise 1.
* Calling this for the first time builds an entire tree, with root at
* node |n|.
*/
static int build_tree(node *n) {
int exits=n->exits;
int nk=0;
if (exits&0x80000000) return 0; /* already visited? */
n->exits|=0x80000000; /* mark as visited */
/* Visit all neighbours: */
if (exits&LDown) if (build_tree(n-n_rows-1)) n->kids[nk++]=n-n_rows-1;
if (exits&LEq) if (build_tree(n-n_rows)) n->kids[nk++]=n-n_rows;
if (exits&LUp) if (build_tree(n-n_rows+1)) n->kids[nk++]=n-n_rows+1;
if (exits&Down) if (build_tree(n-1)) n->kids[nk++]=n-1;
if (exits&Up) if (build_tree(n+1)) n->kids[nk++]=n+1;
if (exits&RDown) if (build_tree(n+n_rows-1)) n->kids[nk++]=n+n_rows-1;
if (exits&REq) if (build_tree(n+n_rows)) n->kids[nk++]=n+n_rows;
if (exits&RUp) if (build_tree(n+n_rows+1)) n->kids[nk++]=n+n_rows+1;
n->n_kids=nk;
return 1;
}
/* Fill in some fields of the |node|s of the subtree at |n|.
* |first|,|second| are the ends of the longest path in this
* subtree; |length| is its length. |furthest| is the most
* distant (from |n|) single node, and |distance| is its
* distance from |n|.
* The points are that (1) we can compute all this stuff
* recursively, and (2) when we've done so for the entire
* tree, we know what the two maximally-distant nodes are.
* This algorithm was suggested to me by Colin Bell, but
* it's obvious enough that it's probably been thought of
* before.
* We actually use a strange metric: paths with lots of branches
* count for more than paths with few branches. This probably
* makes for a harder maze.
*/
void analyse_tree(node *n) {
int i=n->n_kids;
node *m;
int d1=0,d2=0; /* biggest & next-biggest distance to leaves */
int l1=0; /* longest path among subtrees */
node *dn1=0,*dn2=0; /* nodes achieving d1,d2 */
node *ln1=0; /* node achieving l1 */
/* First off, deal with leaf nodes */
if (!i) {
n->first=n->second=n->furthest=n;
n->length=n->distance=0;
return;
}
/* The general case: */
while (--i>=0) {
m=n->kids[i];
analyse_tree(m);
if (m->length>=l1) { l1=m->length; ln1=m; }
if (m->distance>=d1) { d2=d1; dn2=dn1; d1=m->distance; dn1=m; }
else if (m->distance>=d2) { d2=m->distance; dn2=m; }
}
d1+=n->n_kids; d2+=n->n_kids;
n->distance=d1; n->furthest=dn1->furthest;
if (d1+d2>l1) {
n->length=d1+d2;
n->first=dn1->furthest;
n->second=dn2 ? dn2->furthest : n; /* this deals with case n_kids==1 */
}
else {
n->length=l1;
n->first=ln1->first;
n->second=ln1->second;
}
}
/* Print out the maze.
* |start| and |end| are the starting and ending points of the maze,
* of course; they're integers using the same correspondence as
* everywhere else in the program.
* We produce PostScript; we define three operators:
* N draws the north wall of a given cell, NE,NW draw the NE,NW walls.
* Cells are given as <place in column> <column number>.
*/
#define Check { if ((nn+=10)>=70) { printf("\n"); nn=0; } else printf(" "); }
#define Check1 { if ((nn+=2)>=70) { printf("\n"); nn=0; } else printf(" "); }
static void print_maze(int start, int end) {
wall *p=first_wall;
double xs=500/((n_columns+1)*1.36602540378444);
double ys=700/((n_rows+1)*1.73205080756888);
double scale = (xs<ys) ? xs : ys;
int i,j,x;
int nn=0; /* number of walls on current line */
printf("%%!PS\n");
printf("/Times-Roman findfont 10 scalefont setfont\n");
printf("30 770 moveto (Maze produced by ) show\n");
printf("/Times-Italic findfont 10 scalefont setfont\n");
printf("(make-maze ) show\n");
printf("/Times-Roman findfont 10 scalefont setfont\n");
printf("30 755 moveto (Parameters: %dx%d, seed=%d) show\n",
n_columns,n_rows,seed);
printf("\n30 40 translate\n");
printf("%lg %lg scale\n",scale,scale);
printf("1 1 translate\n");
printf("\n");
printf("/M { dup 1 and 0 ne { exch .5 add exch } if\n");
printf(" 1.5 mul exch\n");
printf(" 1.73205080756888 mul\n");
printf(" newpath moveto } bind def\n");
printf("/N { gsave -.6 0.866025403784439 rmoveto\n");
printf(" .15 .0866025403784439 rlineto\n");
printf(" .9 0 rlineto\n");
printf(" .15 -.0866025403784439 rlineto\n");
printf(" -.15 -.0866025403784439 rlineto\n");
printf(" -.9 0 rlineto\n");
printf(" closepath fill grestore } bind def\n");
printf("/NW{ gsave -.45 .952627944162883 rmoveto\n");
printf(" 0 -.173205080756888 rlineto\n");
printf(" -.45 -.779422863405995 rlineto\n");
printf(" -.15 -.0866025403784439 rlineto\n");
printf(" 0 .173205080756888 rlineto\n");
printf(" .45 .779422863405995 rlineto\n");
printf(" closepath fill grestore } bind def\n");
printf("/NE{ gsave .45 .952627944162883 rmoveto\n");
printf(" 0 -.173205080756888 rlineto\n");
printf(" .45 -.779422863405995 rlineto\n");
printf(" .15 -.0866025403784439 rlineto\n");
printf(" 0 .173205080756888 rlineto\n");
printf(" -.45 .779422863405995 rlineto\n");
printf(" closepath fill grestore } bind def\n");
printf("/A { 0 1.73205080756888 rmoveto\n");
printf(" currentpoint newpath moveto } bind def\n");
printf("/B { N A } bind def\n");
printf("/C { NW A } bind def\n");
printf("/D { NW N A } bind def\n");
printf("/E { NE A } bind def\n");
printf("/F { N NE A } bind def\n");
printf("/G { NW NE A } bind def\n");
printf("/H { NW N NE A } bind def\n");
/* Outer walls: */
printf("\n%% Outer walls:\n");
printf("-1 -1 M NE"); Check;
for (i=1;i<n_rows;++i) { printf("A NE"); Check; }
printf("0 0 M NW"); Check;
for (i=1;i<n_rows;++i) { printf("A NW"); Check; }
printf("0 %d M NE",n_columns-1); Check;
for (i=1;i<n_rows;++i) { printf("A NE"); Check; }
printf("%d %d M NW",-(n_columns&1),n_columns); Check;
for (i=1;i<n_rows;++i) { printf("A NW"); Check; }
for (i=0;i<n_columns;++i) {
printf("-1 %d M N",i); Check;
printf("%d %d M N",n_rows-1,i); Check;
if (i&1) {
printf("-1 %d M NW",i); Check;
if (i<n_columns-1) { printf("-1 %d M NE",i); Check; }
printf("%d %d M NW",n_rows-1,i); Check;
printf("%d %d M NE",n_rows-1,i); Check;
}
}
if (nn) printf("\n");
/* Inner walls: */
printf("\n%% Inner walls:\n");
for (i=0;i<n_columns;++i) {
printf("0 %d M",i); Check;
for (j=0;j<n_rows;++j) {
x=nodes[i*n_rows+j].exits;
if (i&1) x = ((x&Up) ? 0 : 1) | ((x&LUp) ? 0 : 2) | ((x&RUp) ? 0 : 4);
else x = ((x&Up) ? 0 : 1) | ((x&LEq) ? 0 : 2) | ((x&REq) ? 0 : 4);
printf("%c",65+x); Check1;
}
}
#if 0
while (p) {
printf("%d %d ",p->lower%n_rows,p->lower/n_rows);
if (p->higher-p->lower==1) printf("N");
else if (p->higher>p->lower) printf("NE");
else printf("NW");
Check;
p=p->next;
}
#endif
if (nn) printf("\n");
/* Start and end points: */
printf("\n%% Start and end of path:\n");
printf("%d %d M currentpoint 0.3 0 360 arc fill\n",start%n_rows,start/n_rows);
printf("%d %d M currentpoint 0.3 0 360 arc fill\n",end%n_rows,end/n_rows);
printf("\nshowpage\n");
}
/* It's nice to have some idea of how long all this is taking.
* So we keep track of the elapsed time and CPU time.
*/
static double cpu0,cpu1; /* initial & most recent */
static time_t real0,real1; /* initial & most recent */
/* Display the CPU time and real time so far.
*/
static void show_time(void) {
clock_t cpu=clock();
time_t real=time(0);
if (cpu!=(clock_t)-1)
fprintf(stderr,"cpu=%5.03lf (total %5.03lf) ",
((double)cpu-cpu1)/CLOCKS_PER_SEC,
((double)cpu-cpu0)/CLOCKS_PER_SEC);
if (real!=(time_t)-1)
fprintf(stderr,"real=%lg (total %lg)",
difftime(real,real1),
difftime(real,real0));
fprintf(stderr,"\n");
cpu1=cpu; real1=real;
}
/* Before we use |show_time| we need to set up those variables.
*/
static void init_time(void) {
cpu0=cpu1=(double)clock();
real0=real1=time(0);
}
/* Now everything's trivial!
*/
int main(int argc, char *argv[]) {
if (argc!=3 && argc!=4) {
fprintf(stderr,"Usage: %s <columns> <rows> [<seed>]\n",argv[0]);
return 0;
}
n_columns=atoi(argv[1]);
n_rows=atoi(argv[2]);
if (n_columns<2 || n_rows<2 || n_columns>1000 || n_rows>1000) {
fprintf(stderr,"Both dimensions must be in the range 2..1000.\n");
return 1;
}
if (argc==4) seed=atoi(argv[3]);
fprintf(stderr,"Initialising everything... ");
init_time();
init_rand();
init_cells(n_rows*n_columns);
init_walls(n_columns,n_rows);
show_time();
fprintf(stderr,"Shuffling walls... ");
shuffle_walls();
show_time();
fprintf(stderr,"Creating maze... ");
create_maze();
show_time();
fprintf(stderr,"Building tree... ");
build_tree(nodes);
show_time();
fprintf(stderr,"Analysing tree... ");
analyse_tree(nodes);
show_time();
fprintf(stderr,"Printing maze... ");
print_maze(nodes->first-nodes,nodes->second-nodes);
show_time();
fprintf(stderr,"Done.\n");
return 0;
}
-m
One Comment, Comment or Ping
lena
my only comment: jesus h. christ. i never did figure out what the h. stood for.
Aug 13th, 2008
Reply to “Moleskine notes for July 2008”