Article 12747 of alt.sources:
Path: nntpd.lkg.dec.com!crl.dec.com!crl.dec.com!bloom-beacon.mit.edu!news.moneng.mei.com!howland.reston.ans.net!newsfeed.internetmci.com!uunet!in1.uu.net!news-1a.csn.net!teal.csn.net!not-for-mail
From: bediger@csn.net (Bruce Ediger)
Newsgroups: alt.sources
Subject: Meditations on 3-bit grey codes
Date: 25 Aug 1995 10:17:44 -0600
Organization: "READ WAY TOO MUCH INTO EVERYTHING" club
Lines: 816
Distribution: world
Message-ID: <41kt38$j6k@teal.csn.net>
NNTP-Posting-Host: 199.117.27.22
Summary: unit, 3-d cube generation of 3-bit grey codes

I got to thinking about grey codes (series of n-bit words where each
suceeding word differs from the last one by only 1 bit) the other 
day.  Here is the source to a few programs that generate grey codes
by walking the vertices of a unit, 3-dimensional cube.  There are
also programs to convert the output into PostScript or strings of 3 bits.

This is really sort of trivial, but I hope someone is amused by it.

#!/bin/sh
# This is a shell archive (produced by shar 3.49)
# To extract the files from this archive, save it to a file, remove
# everything above the "!/bin/sh" line above, and type "sh file_name".
#
# made 08/25/1995 16:12 UTC by bediger
# Source directory /home/tmp/src/csrc/grey_code2
#
# existing files will NOT be overwritten unless -c is specified
#
# This shar contains:
# length  mode       name
# ------ ---------- ------------------------------------------
#    867 -rw-rw-r-- makefile
#   2900 -rw-rw-r-- README
#   2157 -rw-rw-r-- cube1.c
#   2118 -rw-rw-r-- cube2.c
#   1133 -rw-rw-r-- out1.c
#   1224 -rw-rw-r-- out2.c
#   1287 -rw-rw-r-- out3.c
#    601 -rw-rw-r-- out4.c
#
# ============= makefile ==============
if test -f 'makefile' -a X"$1" != X"-c"; then
	echo 'x - skipping makefile (File already exists)'
else
echo 'x - extracting makefile (Text)'
sed 's/^X//' << 'SHAR_EOF' > 'makefile' &&
# gcc 2.5.8
#CC = gcc
#CFLAGS = -g -Wall -fno-common
X
# for lcc 3.3
CC = lcc
CFLAGS = -A -g
X
LIBS = -lsfio
X
all: out1 out2 out3 cube1 cube2
X
clean:
X	- rm out1 out2 out3 out4 cube1 cube2 *.bak *.BAK *.o core
X
shar:
X	shar makefile README cube1.c cube2.c out1.c out2.c out3.c out4.c > greycode.shar
X
# convert cube* output into postscript reps
out4: out4.c
X	$(CC) $(CFLAGS) -o out4 out4.c
X
# convert cube* output into numbered postscript reps
out3: out3.c
X	$(CC) $(CFLAGS) -o out3 out3.c $(LIBS)
X
# convert cube* output into postscript reps
out2: out2.c
X	$(CC) $(CFLAGS) -o out2 out2.c
X
# convert cube* output into postscript reps - sfio
out1: out1.c
X	$(CC) $(CFLAGS) -o out1 out1.c $(LIBS)
X
# vertex-number-path output - stdio
cube2: cube2.c
X	$(CC) $(CFLAGS) -o cube2 cube2.c
X
# vertex-number-path output - sfio
cube1: cube1.c
X	$(CC) $(CFLAGS) -o cube1 cube1.c $(LIBS)
SHAR_EOF
chmod 0664 makefile ||
echo 'restore of makefile failed'
Wc_c="`wc -c < 'makefile'`"
test 867 -eq "$Wc_c" ||
	echo 'makefile: original size 867, current size' "$Wc_c"
fi
# ============= README ==============
if test -f 'README' -a X"$1" != X"-c"; then
	echo 'x - skipping README (File already exists)'
else
echo 'x - extracting README (Text)'
sed 's/^X//' << 'SHAR_EOF' > 'README' &&
Thu Aug 24 22:02:08 MDT 1995
X
Meditations on Grey Codes.
X
X
BACKGROUND
X
3-bit grey codes can be generated by walking around the edges of a unit
3-dimensional cube, taking paths that never touch the same vertex twice.
X
Just for ease, I numbered the unit cube's vertices like this:
X   
X   z
X   |
X   |
X   
X   3--------2
X   |\      /|
X   | 7----6 |
X   | |    | |
X   | 4----5 |
X   |/      \|
X   0--------1  --- x
X
(highly distorted single-vanishing-point perspective - y axis is along 0 -> 4)
X
Vertices 0-1-2-3 on the face closest to viewer, 4-5-6-7 farthest away
X
vertex    x    y    z
X  0       0    0    0
X  1       1    0    0
X  2       1    0    1
X  3       0    0    1
X  4       0    1    0
X  5       1    1    0
X  6       1    1    1
X  7       0    1    1
X
X
SOURCE CODE
X
cube1.c and cube2.c recursively determine paths around the edges of the
unit cube.  Output is on stdout, in the form of a list of vertex numbers
in order of how the path goes, one path per line.  Output on stderr is
basically a "trace" of the recursion and how they check alternatives.
X
The difference between cube1.c and cube2.c is that cube1.c uses Bellcore's
"sfio" package for I/O, while cube2.c uses the old faithful "stdio" package.
Sfio is a lot easier to use.
X
X
cube1 and cube2 both find 18 different ways to make a 3-bit grey code,
each code starting at 000.
X
out1.c and out2.c generate PostScript drawings of the paths output by cube1
or cube2.  Again, the difference is mainly in the use of sfio in out1.c and
stdio in out2.c.  Sfio made the flow of control seem more natural, while
stdio seemed to mandate a few oddities.
X
out3.c is a mod of out1.c (sfio), generating PostScript drawings that
are numbered to show the order in which the cube* programs generate
the paths.  I was a bit confused at how I got 18 different paths,
and this numbering helped me see the pattern (3 groups of 6 paths).
X
out4.c, a mod of out2.c (stdio) generates the 18 3-bit grey codes
from the list of vertices output by the cube* programs.
X
X
COMPILATION
X
I'm reasonably certain these programs are portable to most (modern) unix boxes.
I did the work on a NeXT, but I also compiled and tested the programs under
SunOS and Solaris 2.3 using GCC 2.5.8, and lcc 3.3.  I think the program source
is ANSI C, so I didn't bother to try Sun's old PCC-based stock cc.
X
SFIO
X
You won't be able to compile cube1.c, out1.c, or out3.c without installing
Bellcore's Sfio "safe, fast string I/O" package.  I highly reccomend this
package as a subsitute for stdio, which is getting a bit long in the tooth.
X
I got Sfio from ftp://netlib.att.com/netlib/attgifts/sfio.shar.Z
X
FURTHER WORK
X
A few possible further explorations might be:
X
1. 2-vanishing-point perspective drawings of the 18 variations.
2. Using a 4-dimensional hypercube to get 4-bit grey codes.
3. Trying to figure out which of the 18 paths are the same under rotational
X   transformations.
SHAR_EOF
chmod 0664 README ||
echo 'restore of README failed'
Wc_c="`wc -c < 'README'`"
test 2900 -eq "$Wc_c" ||
	echo 'README: original size 2900, current size' "$Wc_c"
fi
# ============= cube1.c ==============
if test -f 'cube1.c' -a X"$1" != X"-c"; then
	echo 'x - skipping cube1.c (File already exists)'
else
echo 'x - extracting cube1.c (Text)'
sed 's/^X//' << 'SHAR_EOF' > 'cube1.c' &&
#include <sfio.h>
X
struct vertex {
X	int neighbor[3];
};
X
struct vertex ref_cube[8] = {
X	{{1,3,4}},
X	{{0,2,5}},
X	{{1,3,6}},
X	{{0,2,7}},
X	{{0,5,7}},
X	{{1,4,6}},
X	{{2,5,7}},
X	{{3,4,6}}
};
X
void visit_node(int visited[8], int visit_cnt, int path[8], int vertex);
void print_node(int visited[8], int visit_cnt, int path[8], int vertex);
void print_path(int path[8]);
X
int
main(int ac, char **av)
{
X	int path[8];
X	int visited[8];
X	int visit_cnt;
X	int i;
X
X	for (i = 0; i < 8; ++i)
X		visited[i] = 0;
X
X	path[0] = 0;
X	visit_cnt = 1;
X	visited[0] = 1;
X
X	for (i = 0; i < 3; ++i)
X	{
X		print_node(visited, visit_cnt, path, ref_cube[0].neighbor[i]);
X		visit_node(visited, visit_cnt, path, ref_cube[0].neighbor[i]);
X	}
X
X	path[0] = 0;
X	return 0;
}
X
void
visit_node(int visited[8], int visit_cnt, int path[8], int vertex)
{
X	int newpath[8];
X	int newvisited[8];
X	int i;
X
X	print_node(visited, visit_cnt, path, vertex);
X
X	for (i = 0; i < visit_cnt; ++i)
X		newpath[i] = path[i];
X
X	for (i = 0; i < 8; ++i)
X		newvisited[i] = visited[i];
X
X	newpath[visit_cnt++] = vertex;
X
X	sfputr(sfstderr, "\t currently visited: ", -1);
X	for (i = 0; i <= visit_cnt; ++i)
X		sfprintf(sfstderr, "%d", newvisited[i]);
X	sfputc(sfstderr, '\n');
X
X	newvisited[vertex] = 1;
X	
X	if (visit_cnt == 8)
X	{
X		print_path(newpath);
X		return;
X	}
X
X	for (i = 0; i < 3; ++i)
X	{
X		if (!newvisited[ref_cube[vertex].neighbor[i]])
X		{
X			sfprintf(sfstderr, "visiting %d\n",
X				ref_cube[vertex].neighbor[i]);
X			visit_node(newvisited, visit_cnt, newpath,
X				ref_cube[vertex].neighbor[i]);
X		} else {
X			sfprintf(sfstderr, "already visited %d\n",
X				ref_cube[vertex].neighbor[i]);
X		}
X	}
X
}
X
void
print_path(int path[8])
{
X	int i;
X
X	for (i = 0; i < 8; ++i)
X		sfprintf(sfstdout, "%d,", path[i]);
X	sfputc(sfstdout, '\n');
X
}
X
void
print_node(int visited[8], int visit_cnt, int path[8], int vertex)
{
X	int i;
X
X	sfprintf(sfstderr, "vertex %d, visit_cnt %d, visited ", vertex, visit_cnt);
X
X	for (i = 0; i < 7; ++i)
X		sfprintf(sfstderr, "%d", visited[i]);
X	sfprintf(sfstderr, "%d, path ", visited[7]);
X
X	for (i = 0; i < visit_cnt - 1; ++i)
X		sfprintf(sfstderr, "%d-", path[i]);
X	sfprintf(sfstderr, "%d\n", path[visit_cnt - 1]);
}
SHAR_EOF
chmod 0664 cube1.c ||
echo 'restore of cube1.c failed'
Wc_c="`wc -c < 'cube1.c'`"
test 2157 -eq "$Wc_c" ||
	echo 'cube1.c: original size 2157, current size' "$Wc_c"
fi
# ============= cube2.c ==============
if test -f 'cube2.c' -a X"$1" != X"-c"; then
	echo 'x - skipping cube2.c (File already exists)'
else
echo 'x - extracting cube2.c (Text)'
sed 's/^X//' << 'SHAR_EOF' > 'cube2.c' &&
#include <stdio.h>
X
struct vertex {
X	int neighbor[3];
};
X
struct vertex ref_cube[8] = {
X	{{1,3,4}},
X	{{0,2,5}},
X	{{1,3,6}},
X	{{0,2,7}},
X	{{0,5,7}},
X	{{1,4,6}},
X	{{2,5,7}},
X	{{3,4,6}}
};
X
void visit_node(int visited[8], int visit_cnt, int path[8], int vertex);
void print_node(int visited[8], int visit_cnt, int path[8], int vertex);
void print_path(int path[8]);
X
int
main(int ac, char **av)
{
X	int path[8];
X	int visited[8];
X	int visit_cnt;
X	int i;
X
X	for (i = 0; i < 8; ++i)
X		visited[i] = 0;
X
X	path[0] = 0;
X	visit_cnt = 1;
X	visited[0] = 1;
X
X	for (i = 0; i < 3; ++i)
X	{
X		print_node(visited, visit_cnt, path, ref_cube[0].neighbor[i]);
X		visit_node(visited, visit_cnt, path, ref_cube[0].neighbor[i]);
X	}
X
X	path[0] = 0;
X	return 0;
}
X
void
visit_node(int visited[8], int visit_cnt, int path[8], int vertex)
{
X	int newpath[8];
X	int newvisited[8];
X	int i;
X
X	print_node(visited, visit_cnt, path, vertex);
X
X	for (i = 0; i < visit_cnt; ++i)
X		newpath[i] = path[i];
X
X	for (i = 0; i < 8; ++i)
X		newvisited[i] = visited[i];
X
X	newpath[visit_cnt++] = vertex;
X
X	fputs("\t currently visited: ", stderr);
X	for (i = 0; i <= visit_cnt; ++i)
X		fprintf(stderr, "%d", newvisited[i]);
X	fputc('\n', stderr);
X
X	newvisited[vertex] = 1;
X	
X	if (visit_cnt == 8)
X	{
X		print_path(newpath);
X		return;
X	}
X
X	for (i = 0; i < 3; ++i)
X	{
X		if (!newvisited[ref_cube[vertex].neighbor[i]])
X		{
X			fprintf(stderr, "visiting %d\n",
X				ref_cube[vertex].neighbor[i]);
X			visit_node(newvisited, visit_cnt, newpath,
X				ref_cube[vertex].neighbor[i]);
X		} else {
X			fprintf(stderr, "already visited %d\n",
X				ref_cube[vertex].neighbor[i]);
X		}
X	}
X
}
X
void
print_path(int path[8])
{
X	int i;
X
X	for (i = 0; i < 8; ++i)
X		fprintf(stdout, "%d,", path[i]);
X	fputc('\n', stdout);
X
}
X
void
print_node(int visited[8], int visit_cnt, int path[8], int vertex)
{
X	int i;
X
X	fprintf(stderr, "vertex %d, visit_cnt %d, visited ", vertex, visit_cnt);
X
X	for (i = 0; i < 7; ++i)
X		fprintf(stderr, "%d", visited[i]);
X	fprintf(stderr, "%d, path ", visited[7]);
X
X	for (i = 0; i < visit_cnt - 1; ++i)
X		fprintf(stderr, "%d-", path[i]);
X	fprintf(stderr, "%d\n", path[visit_cnt - 1]);
}
SHAR_EOF
chmod 0664 cube2.c ||
echo 'restore of cube2.c failed'
Wc_c="`wc -c < 'cube2.c'`"
test 2118 -eq "$Wc_c" ||
	echo 'cube2.c: original size 2118, current size' "$Wc_c"
fi
# ============= out1.c ==============
if test -f 'out1.c' -a X"$1" != X"-c"; then
	echo 'x - skipping out1.c (File already exists)'
else
echo 'x - extracting out1.c (Text)'
sed 's/^X//' << 'SHAR_EOF' > 'out1.c' &&
#include <sfio.h>
#include <stdlib.h>
X
void new_diagram(void);
void poop_spot(int spot);
X
struct coords {
X	float x; float y;
};
X
struct coords ary[8] = {
X	{0.0, 0.0},
X	{3.0, 0.0},
X	{3.0, 3.0},
X	{0.0, 3.0},
X	{1.0, 1.0},
X	{2.0, 1.0},
X	{2.0, 2.0},
X	{1.0, 2.0}
};
X
float offset = 10.;
float xoff = 0.0, yoff = 0.0;
X
int
main(int ac, char **av)
{
X	char *bp;
X	int count = 0;
X	int spot;
X
X	sfprintf(
X		sfstdout,
X		"%%!\n 0.0 setlinewidth 10. 10. scale save %f %f translate newpath 0. 0. moveto\n",
X		offset + xoff, offset + yoff
X	);
X
X	while ((bp = sfgetr(sfstdin, ',', 1)) != NULL)
X	{
X		if (count == 8)
X		{
X			new_diagram();
X			count = 0;
X		}
X
X		spot = strtol(bp, NULL, 10);
X
X		poop_spot(spot);
X
X		++count;
X	}
X
X	sfputr(sfstdout, "stroke restore", '\n');
X
X	return 0;
}
X
void
new_diagram(void)
{
X	static int count = 0;
X
X	sfputr(sfstdout, "stroke restore", '\n');
X
X	++count;
X
X	if ((count % 5) == 4)
X	{
X		xoff = 0.;
X		yoff += 10.0;
X	} else
X		xoff += 10.0;
X
X
X	sfprintf(sfstdout, "save %f %f translate 0. 0. moveto\n", offset + xoff, offset + yoff);
}
X
void
poop_spot(int spot)
{
X	sfprintf(sfstdout, "%f %f lineto\n", ary[spot].x, ary[spot].y);
}
SHAR_EOF
chmod 0664 out1.c ||
echo 'restore of out1.c failed'
Wc_c="`wc -c < 'out1.c'`"
test 1133 -eq "$Wc_c" ||
	echo 'out1.c: original size 1133, current size' "$Wc_c"
fi
# ============= out2.c ==============
if test -f 'out2.c' -a X"$1" != X"-c"; then
	echo 'x - skipping out2.c (File already exists)'
else
echo 'x - extracting out2.c (Text)'
sed 's/^X//' << 'SHAR_EOF' > 'out2.c' &&
#include <stdio.h>
#include <stdlib.h>
X
void new_diagram(void);
void poop_spot(int spot);
X
struct coords {
X	float x; float y;
};
X
struct coords ary[8] = {
X	{0.0, 0.0},
X	{3.0, 0.0},
X	{3.0, 3.0},
X	{0.0, 3.0},
X	{1.0, 1.0},
X	{2.0, 1.0},
X	{2.0, 2.0},
X	{1.0, 2.0}
};
X
float offset = 10.;
float xoff = 0.0, yoff = 0.0;
X
int
main(int ac, char **av)
{
X	int count = 0;
X	int spot;
X
X	printf(
X		"%%!\n 0.0 setlinewidth 10. 10. scale save %f %f translate newpath 0. 0. moveto\n",
X		offset + xoff, offset + yoff
X	);
X
X	/* this is imperfect - stdio library is a bit lacking, so it doesn't
X	 * detect end-of-file until fscanf() actually fails to read a "%d,"
X	 */
X
X	while (!feof(stdin))
X	{
X		if (fscanf(stdin, "%d,", &spot) < 1)
X			break;  /* oh, ick */
X
X		poop_spot(spot);
X
X		++count;
X
X		if (count == 8)
X		{
X			new_diagram();
X			count = 0;
X		}
X
X	}
X
X	fputs("stroke restore\n", stdout);
X
X	return 0;
}
X
void
new_diagram(void)
{
X	static int count = 0;
X
X	fputs("stroke restore\n", stdout);
X
X	++count;
X
X	if ((count % 5) == 4)
X	{
X		xoff = 0.;
X		yoff += 10.0;
X	} else
X		xoff += 10.0;
X
X
X	printf("save %f %f translate 0. 0. moveto\n", offset + xoff, offset + yoff);
}
X
void
poop_spot(int spot)
{
X	printf("%f %f lineto\n", ary[spot].x, ary[spot].y);
}
SHAR_EOF
chmod 0664 out2.c ||
echo 'restore of out2.c failed'
Wc_c="`wc -c < 'out2.c'`"
test 1224 -eq "$Wc_c" ||
	echo 'out2.c: original size 1224, current size' "$Wc_c"
fi
# ============= out3.c ==============
if test -f 'out3.c' -a X"$1" != X"-c"; then
	echo 'x - skipping out3.c (File already exists)'
else
echo 'x - extracting out3.c (Text)'
sed 's/^X//' << 'SHAR_EOF' > 'out3.c' &&
#include <sfio.h>
#include <stdlib.h>
X
void new_diagram(void);
void poop_spot(int spot);
X
struct coords {
X	float x; float y;
};
X
struct coords ary[8] = {
X	{0.0, 0.0},
X	{3.0, 0.0},
X	{3.0, 3.0},
X	{0.0, 3.0},
X	{1.0, 1.0},
X	{2.0, 1.0},
X	{2.0, 2.0},
X	{1.0, 2.0}
};
X
int diagram_cnt = 1;
float offset = 10.;
float xoff = 0.0, yoff = 0.0;
X
int
main(int ac, char **av)
{
X	char *bp;
X	int count = 0;
X	int spot;
X
X	sfprintf(
X		sfstdout,
X		"%%!\n /Courier findfont 1.0 scalefont setfont 0.0 setlinewidth 10. 10. scale save %f %f translate newpath -1.0 -1.0 moveto (1) show 0. 0. moveto\n",
X		offset + xoff, offset + yoff
X	);
X
X	while ((bp = sfgetr(sfstdin, ',', 1)) != NULL)
X	{
X		if (count == 8)
X		{
X			new_diagram();
X			count = 0;
X		}
X
X		spot = strtol(bp, NULL, 10);
X
X		poop_spot(spot);
X
X		++count;
X	}
X
X	sfputr(sfstdout, "stroke restore", '\n');
X
X	return 0;
}
X
void
new_diagram(void)
{
X	static int count = 0;
X
X	sfputr(sfstdout, "stroke restore", '\n');
X
X	++count;
X
X	if ((count % 5) == 4)
X	{
X		xoff = 0.;
X		yoff += 10.0;
X	} else
X		xoff += 10.0;
X
X	++diagram_cnt;
X
X	sfprintf(
X		sfstdout,
X		"save %f %f translate -1. -1. moveto (%d) show 0. 0. moveto\n",
X		offset + xoff,
X		offset + yoff,
X		diagram_cnt
X	);
}
X
void
poop_spot(int spot)
{
X	sfprintf(sfstdout, "%f %f lineto\n", ary[spot].x, ary[spot].y);
}
SHAR_EOF
chmod 0664 out3.c ||
echo 'restore of out3.c failed'
Wc_c="`wc -c < 'out3.c'`"
test 1287 -eq "$Wc_c" ||
	echo 'out3.c: original size 1287, current size' "$Wc_c"
fi
# ============= out4.c ==============
if test -f 'out4.c' -a X"$1" != X"-c"; then
	echo 'x - skipping out4.c (File already exists)'
else
echo 'x - extracting out4.c (Text)'
sed 's/^X//' << 'SHAR_EOF' > 'out4.c' &&
#include <stdio.h>
#include <stdlib.h>
X
void new_diagram(void);
X
char *ary[8] = {
X	"000",
X	"100",
X	"101",
X	"001",
X	"010",
X	"110",
X	"111",
X	"011"
};
X
int
main(int ac, char **av)
{
X	int count = 0;
X	int spot;
X
X	/* this is imperfect - stdio library is a bit lacking, so it doesn't
X	 * detect end-of-file until fscanf() actually fails to read a "%d,"
X	 */
X
X	while (!feof(stdin))
X	{
X		if (fscanf(stdin, "%d,", &spot) < 1)
X			break;  /* oh, ick */
X
X		puts(ary[spot]);
X
X		++count;
X
X		if (count == 8)
X		{
X			new_diagram();
X			count = 0;
X		}
X
X	}
X
X	return 0;
}
X
void
new_diagram(void)
{
X	fputc('\n', stdout);
}
X
SHAR_EOF
chmod 0664 out4.c ||
echo 'restore of out4.c failed'
Wc_c="`wc -c < 'out4.c'`"
test 601 -eq "$Wc_c" ||
	echo 'out4.c: original size 601, current size' "$Wc_c"
fi
exit 0
-- 
I have killfilled all usenet articles from Prodigy.com due to the 
interminable phone sex spams and the "me too" posts.  I'm much happier now.


