Discussion:
Code Criticism
(too old to reply)
SJS
2008-01-08 02:02:48 UTC
Permalink
I as at a friend's place over the holidays, and I picked up a little
sliding-tile puzzle of a lizard. There were 8 pieces on a little 3x3
grid, and I futzed with it a bit and decided that I didn't even like
those sorts of puzzles when they were that small.

That night, the cat got up in my lap, arranged itself across my
forearms, so I decided to "solve" the 3x3 8-piece sliding tile puzzle.
Now, this would have been an ideal time to try out Ruby, but with a
purring cat trapping my arms, that wasn't really practical.

Same with perl or TCL... I'd need a reference book at hand, and that
wasn't going to happen unless I dumped the cat. And it's just wrong
to dump a purring cat, so I fell back on that old standby we call C.

Just for fun. It's just 'noodling'... futzing around, really, until
I got a reasonable answer. Then I went to bed.

The next day I looked at the code and cringed. There's lots of things
about this code that, frankly, suck. So I'll append it here for all
to pick at, criticize, and so forth. I'll also follow up this post
with _my_ initial reaction.

(The approach is simple -- a brute-force breadth-first search of all
the possible moves.)

There's lots of stuff to criticize. Have fun.

-----------------------------------------------------------------------------
/*
* $Id: sliding_nine.c,v 1.2 2007/12/24 19:55:58 stremler Exp $
*/

/*
* This program 'solves' the 3x3 sliding-puzzle problem.
* Not robustly, it was hacked together in an evening. No design,
* no testing, no good C programming habits.
*
* Author: Stewart Stremler
* License: public domain
*/

#include <stdlib.h>
#include <stdio.h>
#include <strings.h>

#ifndef FALSE
#define FALSE 0
#define TRUE 1
#endif

#define ERROR_EMPTY_ARG "Programmer error. Empty argument in %s at %d\n"
#define ERROR_MALLOC_FAIL "Failed to allocate memory. In %s at %d\n"
#define ERROR_BAD_BOARD "Bad board configuration: '%s' in %s at %d\n"
#define ERROR_SWITCH_BROKE "Unknown value in switch: %d in %s at %d\n"

/* change BLANK to use a different 'empty' character. '_' might be good. */
#define BLANK ' '

/* The fundamental board structure. We have nine puzzle slots, but
* we want to treat it as a string, so we need space for the terminating
* null. We want to eliminate repeats, so we keep track of the parent,
* which also offers a simple way to print out the final pieces in order.
*/
typedef struct {
char board[10];
void *moves[4];
void *prev;
} configuration;

/* We need a simple queue of arbitrary size, so we use a singly linked list.
*/
typedef struct {
configuration *data;
void *next;
} dequenode;

/* We push new items to the tail and pull them from the head for fast
* O(1) access.
* TODO - also keep a count of the # of elements in the queue?
*/
typedef struct {
dequenode *head;
dequenode *tail;
} deque;

/* ----------------------------------------------------------------- */

/* make_dequeue
* creates a new queue.
* exits on malloc failure.
*/
deque *make_deque() {
deque *p;
p = malloc( sizeof( deque ) );
if ( p == NULL ) {
fprintf( stderr, ERROR_MALLOC_FAIL, __FILE__, __LINE__ );
exit( EXIT_FAILURE );
}

p->head = NULL;
p->tail = NULL;
}

/* deque_insert
* inserts the current node into the queue.
* exits on malloc failure.
*/
void deque_insert( deque *d, configuration *current ) {
dequenode *n, *t;
n = malloc( sizeof( dequenode ) );
if ( n == NULL ) {
fprintf( stderr, ERROR_MALLOC_FAIL, __FILE__, __LINE__ );
exit( EXIT_FAILURE );
}

n->data = current;

if ( d->head == NULL ) {
d->head = n;
} else {
t = d->tail;
t->next = (struct dequenode *)n;
/*d->tail->next = n;*/
}
d->tail = n;
}

/* deque_remove
* removes the oldest node from the queue.
* do not call if queue is empty.
*/
configuration *deque_remove( deque *d ) {
configuration *p;
dequenode *q;

q = d->head;
p = q->data;

if ( d->head == d->tail ) {
d->head = NULL;
d->tail = NULL;
} else {
d->head = (dequenode *)d->head->next;
}

free( q );

return p;
}

/* deque_empty
* answers if the queue is empty.
*/
int deque_empty( deque *d ) {
return d->head == NULL;
}

/* deque_size
* answers the number of items in the queue.
* warning - very slow. Walks the linked list. See TODO for struct.
*/
int deque_size( deque *d ) {
int count = 0;
dequenode *p = d->head;
dequenode *end = d->tail;
while ( p != end ) { count++; p = p->next; }
return count;
}

/* ----------------------------------------------------------------- */

/* got_match
* Answers if the two configurations are equivalent.
* Exits on programmer error.
*/
int got_match( configuration *current, configuration *final ) {
if ( current == NULL ) {
return FALSE;
}
if ( final == NULL ) {
fprintf( stderr, ERROR_EMPTY_ARG, __FILE__, __LINE__ );
/*return FALSE;*/
exit( EXIT_FAILURE );
}

return ! (strncmp( current->board, final->board, 10 ));
}

/* got_repeat
* Walks the ancestor list looking for a configuration that is equivalent
* to the current node. This is an optimization step.
*/
int got_repeat( configuration *current ) {
configuration *p;
p = (configuration *)current->prev;
while ( p != NULL ) {
if ( got_match( p, current ) ) return TRUE;
p = (configuration *)p->prev;
}
return FALSE;
}

/* new
* Answers a clone of the the provided configuration. A NULL configuration
* will cause an uninitialized configuration to be created.
* TODO - how much of the brute-force initialization can we remove?
*/
configuration *new( configuration *current ) {
configuration *p;

p = malloc( sizeof( configuration ) );
if ( p == NULL ) {
fprintf( stderr, ERROR_MALLOC_FAIL, __FILE__, __LINE__);
exit( EXIT_FAILURE );
}
p->board[0] = '\0';
p->board[1] = '\0';
p->board[2] = '\0';
p->board[3] = '\0';
p->board[4] = '\0';
p->board[5] = '\0';
p->board[6] = '\0';
p->board[7] = '\0';
p->board[8] = '\0';
p->board[9] = '\0';
p->board[10] = '\0';
p->prev = NULL;
p->moves[0] = NULL;
p->moves[1] = NULL;
p->moves[2] = NULL;
p->moves[3] = NULL;

if ( current != NULL ) {
char *a, *b;
p->prev = (struct configuration *)current;
strncpy( p->board, current->board, 10 );
}

return p;
}

/* swap_tile
* Swaps the board elements at the specified location.
* Assumes arguments are valid and sensible.
*/
void swap_tile( configuration *current, int source, int dest ) {
char temp;
temp = current->board[dest];
current->board[dest] = current->board[source];
current->board[source] = temp;
}

/* make_child
* Creates a unique new child of the current configuration using the
* specified swap of tiles and adding to the specified move slot.
* If the child repeats an ancestor state, it is discarded.
*/
void make_child( configuration *current, int move, int dest, int source ) {
configuration *p;
p = new( current );
swap_tile( p, source, dest );
if ( ! got_repeat( p ) ) {
current->moves[move] = (struct configuration *)p;
} else {
free( p );
}
}

/* fill_children
* Creates all the possible children of the current configuration and
* adds them to the current configuration.
*/
void fill_children( configuration *current ) {
configuration *p;
char temp;
int i;
int blank = -1;

for ( i = 0; i < 9; i++ ) {
if ( current->board[i] == BLANK ) {
blank = i;
break;
}
}

if ( blank < 0 ) {
fprintf( stderr, ERROR_BAD_BOARD, current->board, __FILE__, __LINE__);
return;
}

/*
* 0 | 1 | 2
* -----+-----+-----
* 3 | 4 | 5
* -----+-----+-----
* 6 | 7 | 8
*
*/

switch ( blank ) {
case 0: /* 1->0, 3->0 */
make_child( current, 0, 0, 1 );
make_child( current, 1, 0, 3 );
break;
case 1: /* 0->1, 2->1, 4->1 */
make_child( current, 0, 1, 0 );
make_child( current, 1, 1, 2 );
make_child( current, 2, 1, 4 );
break;
case 2: /* 1->2, 5->2 */
make_child( current, 0, 2, 1 );
make_child( current, 1, 2, 5 );
break;
case 3: /* 0->3, 4->3, 6-> 3 */
make_child( current, 0, 3, 0 );
make_child( current, 1, 3, 4 );
make_child( current, 2, 3, 6 );
break;
case 4: /* 1->4, 3->4, 5->4, 7->4 */
make_child( current, 0, 4, 1 );
make_child( current, 1, 4, 3 );
make_child( current, 2, 4, 5 );
make_child( current, 3, 4, 7 );
break;
case 5: /* 2->5, 4->5, 8->5 */
make_child( current, 0, 5, 2 );
make_child( current, 1, 5, 4 );
make_child( current, 2, 5, 8 );
break;
case 6: /* 3->6, 7->6 */
make_child( current, 0, 6, 3 );
make_child( current, 1, 6, 7 );
break;
case 7: /* 6->7, 4->7, 8->7 */
make_child( current, 0, 7, 4 );
make_child( current, 1, 7, 6 );
make_child( current, 2, 7, 8 );
break;
case 8: /* 5->8, 7->8 */
make_child( current, 0, 8, 5 );
make_child( current, 1, 8, 7 );
break;
default:
fprintf( stderr, ERROR_SWITCH_BROKE, blank, __FILE__, __LINE__ );
}
}

/* walk_solutions
* Breadth-first walk of the solution tree and find the first solution.
*/
configuration *walk_solutions( configuration *initial, configuration *final ) {
configuration *current;
deque *queue;
int i;

queue = make_deque();
deque_insert( queue, initial );

while ( TRUE ) {
current = deque_remove( queue );
if ( got_match( current, final ) ) {
return current; /* leak memory like mad */
}

#ifdef MONITOR_PROGRESS
i = deque_size( queue );
if ( i % 100 == 0 ) {
if ( i < 1000 ) fprintf(stderr, ".");
else if ( i < 10000 ) fprintf(stderr, ":");
else if ( i < 100000 ) fprintf(stderr, "!");
else fprintf(stderr, "#");
}
#endif

fill_children( current );
for ( i = 0; i < 4; i++ ) {
if ( current->moves[i] != NULL ) {
deque_insert( queue, (configuration *)current->moves[i] );
}
}/* for */

}/* while */
}

/* print_solution_size
* Outputs the number of moves it took to solve the problem.
*/
void print_solution_size( configuration *end ) {
configuration *p;
int count;

count = 0;
p = end;
while ( p != NULL ) {
p = (configuration *)p->prev;
count++;
}

fprintf( stdout, "There are %d steps in the solution.\n", count);
}

/* print_solutions
* Print the solution-stack, in reasonable order.
* Recursive.
*/
void print_solutions( configuration *end ) {
if ( end->prev != NULL ) {
print_solutions( (configuration *)end->prev );
}
int row, col;
for ( row = 0; row < 3; row++ ) {
for ( col = 0; col < 3; col++ ) {
fprintf( stdout, " [%c] ", end->board[row * 3 + col] );
}
fprintf( stdout, "\n" );
}
fprintf( stdout, "\n" );
}

/* ----------------------------------------------------------------- */

/* usage
* Outputs how to use the program.
*/
void usage( char **argv ) {
fprintf( stderr, "Usage: %s start end\n", argv[0]);
fprintf( stderr, "\tstart = 9 character board configuration\n");
fprintf( stderr, "\tend = 9 character board configuration\n");
fprintf( stderr, "\t(Note that a blank is REQUIRED!)\n");
/* change this if change definition of BLANK define */
}

/* main
* program entry-point
*/
int main( int argc, char **argv ) {
configuration *start;
configuration *end;
configuration *solution;

if ( argc != 3 ) { usage( argv ); return EXIT_FAILURE; }

start = new( NULL );
end = new( NULL );

if ( strlen( argv[1] ) != 9 ) { usage( argv ); return EXIT_FAILURE; }
if ( strlen( argv[2] ) != 9 ) { usage( argv ); return EXIT_FAILURE; }

strncpy( start->board, argv[1], 10 );
strncpy( end->board, argv[2], 10 );

fprintf( stdout, "Starting with '%s' and trying for '%s'\n",
start->board, end->board );
fprintf( stdout, "start: %p \t end: %p\n", start, end );

solution = walk_solutions( start, end );

print_solution_size( solution );

print_solutions( solution );

return EXIT_SUCCESS;
}
-----------------------------------------------------------------------------
SJS
2008-01-08 02:08:44 UTC
Permalink
I skimmed thru the code and wrote down my initial reactions, and
then followed 'em up with the mitigation or rebuttal of the criticism.
Not much rebutting, and darn little mitigation going on here.

Most of it's pretty general, as I didn't have the patience to do a
line-referencing full on code review. I'd've ended up rewriting it.

-----------------------------------------------------------------------------
Comment #1
No overview-of-solution comment. Should at least point out that it
does a depth-first search by rearraning the strings.

Mitigation/Rebuttal
It's a very small program. Look at the code.

Comment #2
No makefile. All released C programs should presumably ship with
a makefile.

Mitigation/Rebuttal
It compiles with gcc and no options. It doesn't need a makefile.

Comment #3
All in one file. Should break it into at least four files (puzzle
and queue code, plus the associated .h files.)

Mitigation/Rebuttal
Yes. However, this fits all in one file, which means it can be
distributed without having to tar it up first.

Comment #4
BLANK is a define, not a variable; if I, the user, wanted to
use '_' instead of ' ' (so I wouldn't have to quote the arguments
on the command line, say), I have to recompile the code.

Mitigation/Rebuttal
It's not a lot of code to recompile.

Comment #5
Mixture of typedef, struct *, and void * types.

Mitigation/Rebuttal
That fell out of not having a C reference book on hand to remind me
about the details of using typedef in recursive data structures; I
changed my approach partway through, and again towards the end, and
then abandoned further cleanup.

Comment #6
Comments aren't very good. Improve comment quality.

Mitigation/Rebuttal
It's a scratch program. Didn't actually intend to release it.

Comment #7
Cryptic / poorly named variable and type names.

Mitigation/Rebuttal
It's a scratch program. Didn't actually intend to release it.

Comment #8
The deque_remove function does not check to see if the queue is empty.

Mitigation/Rebuttal
The code that uses this data structure always checks first.

Comment #9
Most functions do not sanity-check their arguments.

Mitigation/Rebuttal
It's a scratch program. Didn't actually intend to release it.

Comment #10
The function deque_size is really slow.

Mitigation/Rebuttal
There's a TODO in the struct that would improve performance, and this
function isn't called to do anything vital, and so it can be ignored.
(Can't use the "no premature optimization", as when this function is
used, it REALLY slows everything down.)

Comment #11
Error-reporting system is crude, requiring manual use of __FILE__ and of
__LINE__, something less inelegant could surely be devised.

Mitigation/Rebuttal
An elegant error-reporting system would most likely dwarf this little
program, and using someone else's would incur a needless dependency.

Comment #12
Board initialization is dumb. It assigns null values that get overwritten
anyway.

Mitigation/Rebuttal
That's the leftover changes that resulted from tracking down a
data-corrupting bug.

Comment #13
No unit tests.

Mitigation/Rebuttal
Scratch code, done for fun, all in one file. Not a lot of externally
verifiable behavior aside from computing actual solutions.

Comment #14
Harcoded to this particular problem. Board size need not be fixed, nor
does the board need to be square. The generalization to a board of m x n
is fairly basic and more useful.

Mitigation/Rebuttal
Scratch code, first attempt. Generalizing the algorithm to handle
arbitrarily-sized problems is a useful task for subsequent versions.

Comment #15
Shouldn't have to specify the move-slot.

Mitigation/Rebuttal
Yes, but it was easier to do so at the time.

Comment #16
Memory leaks.

Mitigation/Rebuttal
Scratch program, etc. The outstanding queue that is "just left in place"
will get cleaned up when at program exit. The big problem is the partial
branches (non-solution leaves), but it works regardless. This is where GC
would be handy.

Comment #17
Only first solution found.

Mitigation/Rebuttal
That was all that was being looked for. It satisfies the original requirement.

Comment #18
Input checking is minimal, and doesn't verify that there is indeed a
blank, or that the "final" string is a permutation of the "start" string,
which would send the algorithm off to never-never land.

Mitigation/Rebuttal
A missing blank in the start string should result in program exit when
the blank is searched for; an impossible solution due to mismatched
strings will not result in an infinite loop, as the search tree is self
limiting when we eliminate loops. (Despite the comment claiming it is
only an optimization step.)

Comment #19
Return codes are only success or failure, not something more useful.

Mitigation/Rebuttal
This program doesn't really do anything useful that checking the return
codes would be useful _for_. Error conditions emit output to stderr before
exiting with a failure takes place.

Comment #20
Code isn't very tight. Lots of extraneous statements, needless variable
assignments, etc.

Mitigation/Rebuttal
Yup. Scratch code, etc...

[]
-----------------------------------------------------------------------------
--
Sure, the code is ugly, fragile, and crude
It's basically a throwaway solution, dude.
Stewart Stremler
Chuck Esterbrook
2008-01-08 02:54:30 UTC
Permalink
Post by SJS
I skimmed thru the code and wrote down my initial reactions, and
then followed 'em up with the mitigation or rebuttal of the criticism.
Not much rebutting, and darn little mitigation going on here.
Most of it's pretty general, as I didn't have the patience to do a
line-referencing full on code review. I'd've ended up rewriting it.
-----------------------------------------------------------------------------
Comment #1
No overview-of-solution comment. Should at least point out that it
does a depth-first search by rearraning the strings.
Mitigation/Rebuttal
It's a very small program. Look at the code.
What code is this? Or where? I missed something.

-Chuck
Chuck Esterbrook
2008-01-08 03:16:40 UTC
Permalink
Post by Chuck Esterbrook
Post by SJS
I skimmed thru the code and wrote down my initial reactions, and
then followed 'em up with the mitigation or rebuttal of the criticism.
Not much rebutting, and darn little mitigation going on here.
Most of it's pretty general, as I didn't have the patience to do a
line-referencing full on code review. I'd've ended up rewriting it.
-----------------------------------------------------------------------------
Comment #1
No overview-of-solution comment. Should at least point out that it
does a depth-first search by rearraning the strings.
Mitigation/Rebuttal
It's a very small program. Look at the code.
What code is this? Or where? I missed something.
-Chuck
I see it now. gmail + kplug-lpsg has been acting weird on my lately. I
get messages out of order...

-Chuck
Carl Lowenstein
2008-01-08 15:11:51 UTC
Permalink
Post by SJS
I skimmed thru the code and wrote down my initial reactions, and
then followed 'em up with the mitigation or rebuttal of the criticism.
Not much rebutting, and darn little mitigation going on here.
Most of it's pretty general, as I didn't have the patience to do a
line-referencing full on code review. I'd've ended up rewriting it.
Looking at it from the puzzle point of view rather than programming,
there is one fatal flaw. A simple parity argument shows that 1/2 of
the plausible solutions can never be reached. Just swap two tiles in
the target and you can't get there from here.

Starting with '2468135 7' and trying for '12345687 '

After running for 60 seconds it has expanded to occupy 2 GB of RAM and
is still trying. I killed it.

This is of course a simplified version of the "Fifteen Puzzle",
attributed to Sam Loyd, circa 1890.

carl
--
carl lowenstein marine physical lab u.c. san diego
***@ucsd.edu
Andrew Lentvorski
2008-01-08 15:31:06 UTC
Permalink
Post by Carl Lowenstein
Looking at it from the puzzle point of view rather than programming,
there is one fatal flaw. A simple parity argument shows that 1/2 of
the plausible solutions can never be reached. Just swap two tiles in
the target and you can't get there from here.
Starting with '2468135 7' and trying for '12345687 '
After running for 60 seconds it has expanded to occupy 2 GB of RAM and
is still trying. I killed it.
Ayup. But that is a limitation of the puzzle, not the program.

However, I should have detected it as my system does eventually go to 0
in terms of untried solutions and gets stuck in an infinite loop. It
does quit growing, however.

It is interesting that out of all of my test cases, I never actually
managed to construct a parity-reversed problem.

I wonder why? Especially since I had pretty much a 50/50 chance every
time I created a test.

Hmmmmmm.

-a
Christopher Smith
2008-01-08 15:46:34 UTC
Permalink
Post by Carl Lowenstein
Post by SJS
I skimmed thru the code and wrote down my initial reactions, and
then followed 'em up with the mitigation or rebuttal of the criticism.
Not much rebutting, and darn little mitigation going on here.
Most of it's pretty general, as I didn't have the patience to do a
line-referencing full on code review. I'd've ended up rewriting it.
Looking at it from the puzzle point of view rather than programming,
there is one fatal flaw. A simple parity argument shows that 1/2 of
the plausible solutions can never be reached. Just swap two tiles in
the target and you can't get there from here.
Actually, IIRC, this is a property of this puzzle: depending on the
number of tiles, either all are reachable or only half are reachable.

--Chris
SJS
2008-01-08 15:57:08 UTC
Permalink
Post by Carl Lowenstein
Post by SJS
I skimmed thru the code and wrote down my initial reactions, and
then followed 'em up with the mitigation or rebuttal of the criticism.
Not much rebutting, and darn little mitigation going on here.
Most of it's pretty general, as I didn't have the patience to do a
line-referencing full on code review. I'd've ended up rewriting it.
Looking at it from the puzzle point of view rather than programming,
there is one fatal flaw. A simple parity argument shows that 1/2 of
the plausible solutions can never be reached. Just swap two tiles in
the target and you can't get there from here.
I believe you, but I'm afraid I'm not seeing it.
Post by Carl Lowenstein
Starting with '2468135 7' and trying for '12345687 '
After running for 60 seconds it has expanded to occupy 2 GB of RAM and
is still trying. I killed it.
Well, yah, it's going to brute-force all possible solutions if it can't
find the proper one. Starting with 'abcdefgh ' and looking for 'ABCDEFGH '
will cause all manner of fun.
Post by Carl Lowenstein
This is of course a simplified version of the "Fifteen Puzzle",
attributed to Sam Loyd, circa 1890.
Yup. It's not a new puzzle at all.
--
There are configurations you can arrange on a Rubick's cube
That can only be achieved with a screwdriver and graphite lube.
Stewart Stremler
Andrew Lentvorski
2008-01-08 16:16:46 UTC
Permalink
Post by SJS
I believe you, but I'm afraid I'm not seeing it.
Post by Carl Lowenstein
Starting with '2468135 7' and trying for '12345687 '
A more obvious example is:

Start with '12345678 ' and try for '12345687 '

No transformation cans swap the 7&8.

-a
Carl Lowenstein
2008-01-08 17:16:53 UTC
Permalink
Post by Andrew Lentvorski
Post by SJS
I believe you, but I'm afraid I'm not seeing it.
Post by Carl Lowenstein
Starting with '2468135 7' and trying for '12345687 '
Start with '12345678 ' and try for '12345687 '
No transformation cans swap the 7&8.
Yes, that occurred to me about 10 minutes too late.

carl
--
carl lowenstein marine physical lab u.c. san diego
***@ucsd.edu
Chuck Esterbrook
2008-01-08 03:18:30 UTC
Permalink
Post by SJS
I as at a friend's place over the holidays, and I picked up a little
sliding-tile puzzle of a lizard. There were 8 pieces on a little 3x3
grid, and I futzed with it a bit and decided that I didn't even like
those sorts of puzzles when they were that small.
...
Post by SJS
The next day I looked at the code and cringed. There's lots of things
about this code that, frankly, suck. So I'll append it here for all
to pick at, criticize, and so forth. I'll also follow up this post
with _my_ initial reaction.
(The approach is simple -- a brute-force breadth-first search of all
the possible moves.)
How about a Cobra version? :-)

-Chuck
Brad Beyenhof
2008-01-08 07:21:30 UTC
Permalink
Post by SJS
There's lots of stuff to criticize. Have fun.
From a functional standpoint, it runs and does what you built it to
do... whether or not it's "the most efficient way," I'm impressed.

The only problems I encountered (as a newbish C guy) were a few
compiling errors:
sliding_nine.c: In function 'new':
sliding_nine.c:208: warning: incompatible implicit declaration of
built-in function 'strncpy'
sliding_nine.c: In function 'main':
sliding_nine.c:418: warning: incompatible implicit declaration of
built-in function 'strlen'
sliding_nine.c:421: warning: incompatible implicit declaration of
built-in function 'strncpy'

Those didn't keep the program from running as long as I supplied
proper arguments, though.

This is with gcc version 4.1.3 20070929 on Ubuntu Server 7.10.
--
Brad Beyenhof
http://augmentedfourth.com
Silence will save me from being wrong (and foolish), but it will also
deprive me of the possibility of being right.
~ Igor Stravinsky
SJS
2008-01-08 12:09:21 UTC
Permalink
Post by SJS
Post by SJS
There's lots of stuff to criticize. Have fun.
From a functional standpoint, it runs and does what you built it to
do... whether or not it's "the most efficient way," I'm impressed.
The only problems I encountered (as a newbish C guy) were a few
Nothing in the code struck you as a problem?
Post by SJS
sliding_nine.c:208: warning: incompatible implicit declaration of
built-in function 'strncpy'
sliding_nine.c:418: warning: incompatible implicit declaration of
built-in function 'strlen'
sliding_nine.c:421: warning: incompatible implicit declaration of
built-in function 'strncpy'
Try changing #include <strings.h> to #include <string.h>.

I've seen both, but I don't remember which one is more standard.
Post by SJS
Those didn't keep the program from running as long as I supplied
proper arguments, though.
This is with gcc version 4.1.3 20070929 on Ubuntu Server 7.10.
I should check the GCC version I used to compile and run it. Good
idea.
--
They say that C is the portable assembler of tool code
For values of 'portable' that mean 'a moderate workload'
Stewart Stremler
David Brown
2008-01-08 13:17:19 UTC
Permalink
Post by SJS
Try changing #include <strings.h> to #include <string.h>.
I've seen both, but I don't remember which one is more standard.
<strings.h> seems to only define a handfull of Berkeley specific functions.
<string.h> has those in addition to the standard ones.

I think <string.h> is Posix, and <strings.h> is for the legacy bcopy() and
friends.

Dave
Barry Gershenfeld
2008-01-08 11:08:52 UTC
Permalink
Post by SJS
sliding-tile puzzle of a lizard. There were 8 pieces on a little 3x3
That night, the cat got up in my lap, arranged itself across my
forearms, so I decided to "solve" the 3x3 8-piece sliding tile puzzle.
Now, this would have been an ideal time to try out Ruby, but with a
purring cat trapping my arms, that wasn't really practical.
Just once, I wanna see c/cat/wife
Post by SJS
Same with perl or TCL... I'd need a reference book at hand, and that
wasn't going to happen unless I dumped the cat. And it's just wrong
to dump a purring cat, so I fell back on that old standby we call C.
So, you're still able to operate. Books aren't really required; with the
Web you have all the reference material available. Admittedly, some are
better than others. PHP shines here.
Post by SJS
Just for fun. It's just 'noodling'... futzing around, really, until
I got a reasonable answer. Then I went to bed.
Just as I expected. Stewart coughs, and out comes runnable code.
Post by SJS
There's lots of stuff to criticize. Have fun.
-----------------------------------------------------------------------------
* $Id: sliding_nine.c,v 1.2 2007/12/24 19:55:58 stremler Exp $
Aren't we supposed to embed this in the object somehow ( :) ...troll )

I let the machine do the criticizing. Who am I to judge?

$ gcc sliding_nine.c -o sli -Wall
sliding_nine.c: In function `make_deque':
sliding_nine.c:74: warning: control reaches end of non-void function
sliding_nine.c: In function `new':
sliding_nine.c:206: warning: unused variable `a'
sliding_nine.c:206: warning: unused variable `b'
sliding_nine.c: In function `fill_children':
sliding_nine.c:246: warning: unused variable `p'
sliding_nine.c:247: warning: unused variable `temp'

Okay, but the premise is that it /runs/

$ ./sli.exe
Usage: ./sli start end
start = 9 character board configuration
end = 9 character board configuration
(Note that a blank is REQUIRED!)

$ ./sli.exe 246813579 123456789
Starting with '246813579' and trying for '123456789'
start: 0x9700f8 end: 0x970120
Bad board configuration: '246813579' in sliding_nine.c at 259
Segmentation fault (core dumped)

Hmm...OK, there should only be 8 tiles of the 9. "Note that a blank is
REQUIRED!"

$ ./sli.exe 2468135 7 1234567 8
Usage: ./sli start end
start = 9 character board configuration
end = 9 character board configuration
(Note that a blank is REQUIRED!)

Umm...blank as delimiter, blank as...oh, I did learn something about shells:

$ ./sli.exe "2468135 7" "12345678 "
Starting with '2468135 7' and trying for '12345678 '
start: 0x9700f8 end: 0x970120

(now it's thinking)...

[2] [4] [6]
[8] [1] [3]
[5] [ ] [7]

[2] [4] [6]
[8] [ ] [3]
[5] [1] [7]

and so on, until

[1] [2] [3]
[4] [5] [6]
[7] [8] [ ]



Okay, I learned this, too:

$ time ./sli.exe "2468135 7" "12345678 " > sli.txp

real 0m37.930s
user 0m0.000s
sys 0m0.000s

...on a screamin' 533MHz Pentium, in cygwin, under Windows 98.
...uphill, both ways.

(Okay peanut gallery, this is where you post /your/ time...)

Barry
Brad Beyenhof
2008-01-08 11:25:22 UTC
Permalink
Post by Barry Gershenfeld
real 0m37.930s
user 0m0.000s
sys 0m0.000s
[snip]
Post by Barry Gershenfeld
(Okay peanut gallery, this is where you post /your/ time...)
I didn't use any gcc options when compiling, and it's running on my
Ubuntu 7.10 server (a Linode VPS). I changed my "blank" character in
the source code to an underscore so I wouldn't have to quote the
arguments:

$ time ./a.out 2468135_7 12345678_ > sli.txt

real 0m4.711s
user 0m3.070s
sys 0m0.190s
--
Brad Beyenhof
http://augmentedfourth.com
Silence will save me from being wrong (and foolish), but it will also
deprive me of the possibility of being right.
~ Igor Stravinsky
David Brown
2008-01-10 22:23:31 UTC
Permalink
Post by Brad Beyenhof
Post by Barry Gershenfeld
real 0m37.930s
user 0m0.000s
sys 0m0.000s
[snip]
Post by Barry Gershenfeld
(Okay peanut gallery, this is where you post /your/ time...)
I didn't use any gcc options when compiling, and it's running on my
Ubuntu 7.10 server (a Linode VPS). I changed my "blank" character in
the source code to an underscore so I wouldn't have to quote the
$ time ./a.out 2468135_7 12345678_ > sli.txt
real 0m4.711s
user 0m3.070s
sys 0m0.190s
Ok, my turn. The code, in Common Lisp, is attached below. Running this
interactively with SBCL on a 2.4Ghz Intel Core 2 DUO.

For the given example

(time (solve '(2 4 6 8 1 3 5 nil 7)))
Evaluation took:
0.628 seconds of real time
0.600038 seconds of user run time
0.028002 seconds of system run time
[Run times include 0.188 seconds GC run time.]
0 calls to %EVAL
0 page faults and
83,066,512 bytes consed.

I may have to look at the other solutions, since this thing is
significantly faster than either solution posted so far. I didn't try any
optimization.

I spent probably 8 hours last night learning enough common lisp (I know
scheme), and then about 5 hours this evening writing this.

Interestingly, the full space search

(time (solve '(1 2 3 4 5 6 8 7 nil)))

is 0.828 seconds. (It doesn't print anything if there is no solution).
It runs quite a bit slower if you print out the boards during the run, or
even time the printing of the solution.

To be honest, I'm completely surprised by these results. I give this
language and at least this implementation a lot of credit.

So, any ideas on what I should write next? This was a perfect problem for
learning this language.

Dave

----------------------------------------------------------------------
;;; Brute-force solution to the 9-square (or 15-square or whatever)
;;; problem.

;; Dimensions of board to solve.
(defconstant width 3 "Width of board in squares")
(defconstant height 3 "Height of board in squares")
(defconstant full-size (* width height) "Total number of board squares")

(defun valid-x-p (x)
(and (>= x 0)
(< x width)))
(defun valid-y-p (y)
(and (>= y 0)
(< y height)))

;; A given board is represented as a simple vector with the squares
;; given as integers starting at 1. The empty square has the value
;; NIL.

(defconstant solved-board
(let ((nums (loop for i from 1 to full-size
collect (and (< i full-size) i))))
(make-array full-size :initial-contents nums))
"The final solved board")

(defun show-board (board)
"Show the board in a readable format"
(loop for y from 0 to (1- height)
do (loop for x from 0 to (1- width)
for pos from (* width y)
do (format t " ~***@A" (or (elt board pos) "_")))
do (format t "~%")))

(defun nless (a b)
"Numeric sorting, except that 'nil' is larger than other numbers"
(< (or a full-size) (or b full-size)))

;; Given a board as a list, convert to vector format, and make sure it
;; is valid.
(defun make-board (items)
(let* ((board (make-array full-size :initial-contents items))
(sboard (copy-seq board)))
(unless (equalp (sort sboard #'nless) solved-board)
(error "Board does not have proper numbers"))
board))

;; Given a particular board, compute a unique bignum defining the
;; possible position. Treats the empty space as value full-size, and
;; simply computes the number base (1+ full-size).
(defun compute-cookie (board)
(loop for item across board
for power = 1 then (* power 10)
sum (* power (or item full-size))))

;; Pre-compute all possible moves from a given position.
(defun one-move (x y)
"Compute the valid moves from the given X and Y"
(loop for (dx dy) in '((-1 0) (1 0) (0 -1) (0 1))
nconc (let ((nx (+ x dx))
(ny (+ y dy)))
(and (valid-x-p nx) (valid-y-p ny)
(list (+ (* width ny) nx))))))
(defconstant all-moves-list
(loop for y from 0 to (1- height)
nconc (loop for x from 0 to (1- width)
for pos from (* width y)
collect (one-move x y)))
"All valid moves, as a single array")
(defconstant all-moves (make-array full-size :initial-contents all-moves-list))

;; Given a particular board, exchange the specified two pieces,
;; non-destructively (copies the board first).
(defun exchange (board a b)
(let ((board2 (copy-seq board)))
(setf (elt board2 a) (elt board b))
(setf (elt board2 b) (elt board a))
board2))

;; Given a particular board, return a list of the boards that are
;; reachable from this board.
(defun find-reachable (board)
(loop with my-pos = (position nil board)
for pos in (elt all-moves my-pos)
collect (exchange board my-pos pos)))

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;; A simple FIFO. New nodes are inserted at the tail, and removed
;;; from the head. The HEAD is the head of the list, and the TAIL is
;;; the cons cell of the last member of the list.
(defstruct fifo
(head nil)
(tail nil))

(defun fifo-empty-p (f)
(not (fifo-head f)))

(defun fifo-append (f item)
"Append the given ITEM to the end of the fifo F"
(let ((tmp (list item)))
(if (fifo-tail f)
(setf (rest (fifo-tail f)) tmp)
(setf (fifo-head f) tmp))
(setf (fifo-tail f) tmp))
f)

(defun fifo-append-many (f items)
"Append a list of ITEMS to the end of fifo F"
(loop for item in items
do (fifo-append f item))
f)

;; TODO: Return multiple values for more information.
(defun fifo-take (f)
"Remove an item from the fifo, returning NIL if empty."
(if (fifo-head f)
(let ((item (first (fifo-head f))))
(setf (fifo-head f) (rest (fifo-head f)))
(unless (fifo-head f)
(setf (fifo-tail f) nil))
item)))

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;; Wrap it all up, doing a breadth-first search for a solution.
;;; Takes INITIAL-ITEMS as a list of the initial board.
(defun solve (initial-items)
(do* ((start (make-board initial-items))
(todo (fifo-append (make-fifo) (list start (list start))))
(seen (let ((hash (make-hash-table :test 'equalp)))
(setf (gethash (compute-cookie start) hash) t)
hash)))
((fifo-empty-p todo) nil)

(let* ((entry (fifo-take todo))
(cur (first entry))
(seq (second entry)))
;(format t "Trying: ~A~%" seq)
;(show-board cur)
(when (equalp cur solved-board)
;(format t "Found solution!!!: ~A~%" seq)
(return-from solve (reverse seq)))
(loop for move in (find-reachable cur)
do (unless (gethash (compute-cookie move) seen)
(setf (gethash (compute-cookie move) seen) t)
(fifo-append todo (list move (cons move seq))))))))

(defun show-solve (initial-items)
(let*
((solution (time (solve initial-items))))
(when solution
(format t "Solution in ~A moves:~%" (1- (length solution)))
(loop for move in solution
for count from 0
do (format t "~%Move #~A:~%" count)
do (show-board move)))))

(defvar sample-board (make-board '(5 4 3 2 1 nil 8 6 7)))
Christopher Smith
2008-01-10 22:27:12 UTC
Permalink
Post by David Brown
Post by Brad Beyenhof
Post by Barry Gershenfeld
real 0m37.930s
user 0m0.000s
sys 0m0.000s
[snip]
Post by Barry Gershenfeld
(Okay peanut gallery, this is where you post /your/ time...)
I didn't use any gcc options when compiling, and it's running on my
Ubuntu 7.10 server (a Linode VPS). I changed my "blank" character in
the source code to an underscore so I wouldn't have to quote the
$ time ./a.out 2468135_7 12345678_ > sli.txt
real 0m4.711s
user 0m3.070s
sys 0m0.190s
Ok, my turn. The code, in Common Lisp, is attached below. Running this
interactively with SBCL on a 2.4Ghz Intel Core 2 DUO.
For the given example
(time (solve '(2 4 6 8 1 3 5 nil 7)))
0.628 seconds of real time
0.600038 seconds of user run time
0.028002 seconds of system run time
[Run times include 0.188 seconds GC run time.]
0 calls to %EVAL
0 page faults and
83,066,512 bytes consed.
I may have to look at the other solutions, since this thing is
significantly faster than either solution posted so far. I didn't try any
optimization.
I spent probably 8 hours last night learning enough common lisp (I know
scheme), and then about 5 hours this evening writing this.
Interestingly, the full space search
(time (solve '(1 2 3 4 5 6 8 7 nil)))
is 0.828 seconds. (It doesn't print anything if there is no solution).
It runs quite a bit slower if you print out the boards during the run, or
even time the printing of the solution.
I'm not surprised by this at all. Modern LISP implementations are quite
efficient, and this is a good problem for LISP. My solution does do a
full space search initially, and it does it in about the same amount of
time as yours. Mine also uses the Boost Graph stuff which actually slows
things down (I'm thinking of a more useful way to use the graph stuff as
I refactor the code) with tons of lookups that are slower than just
computing what possible moves one can do.
Post by David Brown
So, any ideas on what I should write next? This was a perfect problem for
learning this language.
Another good one for the language is a CLOS based equivalent to "find".

--Chris
SJS
2008-01-12 13:07:27 UTC
Permalink
[chop]
Post by David Brown
I may have to look at the other solutions, since this thing is
significantly faster than either solution posted so far. I didn't try any
optimization.
Equivalent features would be nice as well. Something that takes
two strings from the command line and prints out the result in an
easy-for-a-human-to-verify way would be very desirable.

Plus, we could all then time it the same way, using the same "time"
program, giving comparable results.

[snip]
Post by David Brown
To be honest, I'm completely surprised by these results. I give this
language and at least this implementation a lot of credit.
$ time ./a.out '12345678 ' '54321 867' > /dev/null
1.23u 0.05s 0:01.30 98.4%
$ time clisp puzzle
Real time: 36.646008 sec.
Run time: 36.644794 sec.
Space: 41246096 Bytes
GC: 37, GC time: 1.269448 sec.
36.41u 0.28s 0:36.71 99.9%
$

I'm thinking it's the implementation. :)
Post by David Brown
So, any ideas on what I should write next? This was a perfect problem for
learning this language.
Finding a good problem is a wonderful thing.

A suduko solver seems like a good fit for a lispy language. :)

Lemme check my assumptions...
Post by David Brown
----------------------------------------------------------------------
;;; Brute-force solution to the 9-square (or 15-square or whatever)
;;; problem.
[snip]
Post by David Brown
;; A given board is represented as a simple vector with the squares
;; given as integers starting at 1. The empty square has the value
;; NIL.
(defconstant solved-board
(let ((nums (loop for i from 1 to full-size
collect (and (< i full-size) i))))
(make-array full-size :initial-contents nums))
"The final solved board")
You don't take arbitrary strings, you take numbers, and the solutions
is always (1 2 3 4 5 6 7 8 nil) for a 3x3 board, yes?

[snip]
Post by David Brown
;; Given a particular board, compute a unique bignum defining the
;; possible position. Treats the empty space as value full-size, and
;; simply computes the number base (1+ full-size).
(defun compute-cookie (board)
(loop for item across board
for power = 1 then (* power 10)
sum (* power (or item full-size))))
At first I thought it was the guaranteed way to encode any number
sequence using powers and primes...

The loop with two fors is kind of odd; I think I see what it's doing.
My psuedocode interpretation of the above:

bignum compute-cookie( board ) {
sum = 0
power = 1
foreach item in board {
if ( item is nil ) {
sum = sum + (power * size(board))
} else {
sum = sum + (power * item)
}
power = power * 10
}
return sum
}

Close?

Also, it seems like there's going to be a potential problem when the board
size is > 3x3, as then you'll have items that are bigger than your power
increment.

[chop]
--
It takes a long time in lisp for me to think
Activation energy to get my brain to the brink.
Stewart Stremler
David Brown
2008-01-12 14:04:50 UTC
Permalink
Post by SJS
Equivalent features would be nice as well. Something that takes
two strings from the command line and prints out the result in an
easy-for-a-human-to-verify way would be very desirable.
Plus, we could all then time it the same way, using the same "time"
program, giving comparable results.
The results I gave were equivalent to that. In lisp, you generally use the
lisp interpreter as your shell and give your expressions there to evaluate.
I haven't even figured out yet how to make a standalone program (I did a
hello world), or parse arguments and such.

Lisp's time uses the same system call to get the time as time, so I would
expect the same results.
Post by SJS
A suduko solver seems like a good fit for a lispy language. :)
I've already moved on to directory parsing and tree walking...
Post by SJS
Lemme check my assumptions...
Post by SJS
----------------------------------------------------------------------
;;; Brute-force solution to the 9-square (or 15-square or whatever)
;;; problem.
[snip]
Post by SJS
;; A given board is represented as a simple vector with the squares
;; given as integers starting at 1. The empty square has the value
;; NIL.
(defconstant solved-board
(let ((nums (loop for i from 1 to full-size
collect (and (< i full-size) i))))
(make-array full-size :initial-contents nums))
"The final solved board")
You don't take arbitrary strings, you take numbers, and the solutions
is always (1 2 3 4 5 6 7 8 nil) for a 3x3 board, yes?
Yes. But, solved-board wouldn't have to be a constant.
Post by SJS
[snip]
Post by SJS
;; Given a particular board, compute a unique bignum defining the
;; possible position. Treats the empty space as value full-size, and
;; simply computes the number base (1+ full-size).
(defun compute-cookie (board)
(loop for item across board
for power = 1 then (* power 10)
sum (* power (or item full-size))))
At first I thought it was the guaranteed way to encode any number
sequence using powers and primes...
It would be, except for some strange bugs. It should be:
(defun compute-cookie (board)
(loop for item across board
for power = 1 then (* power full-size)
sum (* power (or item 0))))

The power needs to increase by the full-size, and the empty square counts
as zero. My old one works on the 3x3 board because the power is 1 too big,
so the empty square being 1 too big didn't hurt anything either. I put the
10 in there temporarily so I could see the result nicely in base-10, and
forgot to take it out.
Post by SJS
The loop with two fors is kind of odd; I think I see what it's doing.
bignum compute-cookie( board ) {
sum = 0
power = 1
foreach item in board {
if ( item is nil ) {
sum = sum + (power * size(board))
} else {
sum = sum + (power * item)
}
power = power * 10
}
return sum
}
Close?
Looks right, well at least in this case. A 'for' clause in the loop
describes what the variable does for each iteration through the loop.
'across' iterates through something, and also terminates the loop when the
sequence ends. A expr then expr2 evalues expr the first time, and then
expr2 each time after that.

You can also just use 'for name = expr' to compute something each
iteration.

I actually like LOOP in lisp. The following (using sbcl's posix library)
uses the posix opendir/readdir/closedir to read all of the names in a
directory.

(defun fake-dir-p (name)
(or (string-equal name ".")
(string-equal name "..")))

(defun list-directory (path)
(let ((dir (sb-posix:opendir path)))
(unwind-protect
(sort (loop for dirent = (sb-posix:readdir dir)
until (sb-alien:null-alien dirent)
for name = (sb-posix:dirent-name dirent)
while (stringp name)
unless (fake-dir-p name) collect name)
#'string<)
(sb-posix:closedir dir))))

It nicely handles the two different exit conditions (the dirent can either
be null, or the string inside of it invalid). It also handles the
conditional collection (to skip "." and ".."). Later in the code I collect
files and directories separately.
Post by SJS
Also, it seems like there's going to be a potential problem when the board
size is > 3x3, as then you'll have items that are bigger than your power
increment.
Yes, that's a bug. The 10 was just for debugging, and I forgot it.

Although there are far bigger problems with larger boards, such as utterly
rediculous amounts of memory needed.

For larger puzzles, a smarter algorithm is definitely needed. There are
actually fairly simple algorithms to always solve the puzzle, but they
won't necessarily have the smallest number of moves.

Dave
Andrew Lentvorski
2008-01-12 15:56:34 UTC
Permalink
Post by David Brown
Post by SJS
Equivalent features would be nice as well. Something that takes
two strings from the command line and prints out the result in an
easy-for-a-human-to-verify way would be very desirable.
Plus, we could all then time it the same way, using the same "time"
program, giving comparable results.
The results I gave were equivalent to that. In lisp, you generally use the
lisp interpreter as your shell and give your expressions there to evaluate.
I haven't even figured out yet how to make a standalone program (I did a
hello world), or parse arguments and such.
Lisp's time uses the same system call to get the time as time, so I would
expect the same results.
However, if you type it in from the repl, you've already sunk the
compilation time. Calling it from the command line forces you to add
the compilation time to the actual execution time.

-a
SJS
2008-01-12 18:16:48 UTC
Permalink
begin quoting Andrew Lentvorski as of Sat, Jan 12, 2008 at 03:56:32PM -0800:
[snip]
Post by Andrew Lentvorski
However, if you type it in from the repl, you've already sunk the
compilation time. Calling it from the command line forces you to add
the compilation time to the actual execution time.
I'm using clisp (on rohan) -- is there a way to compile it to something
that runs from the command-line?

Hm... I could count compiling the C code as part of the runtime.

Script started on Sat Jan 12 18:08:05 2008
rohan% tail -6 puzzle.cl

(defvar sample-board (make-board '(5 4 3 2 1 nil 8 6 7)))

;(time (solve '(1 2 3 4 5 6 7 8 nil )))
;(time (solve '(nil 1 2 3 4 5 6 8 7 )))
(time (solve sample-board) )
rohan% time clisp puzzle.cl
Real time: 36.984585 sec.
Run time: 36.98334 sec.
Space: 41246096 Bytes
GC: 37, GC time: 1.409856 sec.
36.67u 0.36s 0:37.05 99.9%
rohan% exit
exit

script done on Sat Jan 12 18:09:07 2008

versus

Script started on Sat Jan 12 18:13:58 2008
rohan% cat compile-and-run
#!/bin/csh -f
gcc sliding_nine.c >& /dev/null
# match solution: '(5 4 3 2 1 nil 8 6 7)))
./a.out '54321 867' '12345678 ' > /dev/null
rohan% time ./compile-and-run
1.35u 0.06s 0:01.48 95.2%
rohan% exit
exit

script done on Sat Jan 12 18:14:15 2008
--
It's hard enough making a comment pithy
Making it rhyme is hard so as to be mythy.
Stewart Stremler
David Brown
2008-01-12 22:05:54 UTC
Permalink
Post by Brad Beyenhof
[snip]
Post by Andrew Lentvorski
However, if you type it in from the repl, you've already sunk the
compilation time. Calling it from the command line forces you to add
the compilation time to the actual execution time.
I'm using clisp (on rohan) -- is there a way to compile it to something
that runs from the command-line?
clisp is about 40-times slower than sbcl on this problem. SBCL can also
cache it's compiled version, so the load time is probably fairly
insignificant.

Nonetheless, for SBCL, with your "command line version" (no compiler
caching).

SBCL:
0.243 seconds of real time
0.232014 seconds of user run time
0.012001 seconds of system run time
[Run times include 0.06 seconds GC run time.]
0 calls to %EVAL
0 page faults and
38,605,008 bytes consed.

Clisp:
Real time: 9.079655 sec.
Run time: 9.072568 sec.
Space: 41805808 Bytes
GC: 24, GC time: 0.36402 sec.

It doesn't run under GCL, which appears to be missing enough ANSI things.

Dave
SJS
2008-01-12 18:34:45 UTC
Permalink
Post by David Brown
Post by SJS
Equivalent features would be nice as well. Something that takes
two strings from the command line and prints out the result in an
easy-for-a-human-to-verify way would be very desirable.
Plus, we could all then time it the same way, using the same "time"
program, giving comparable results.
The results I gave were equivalent to that.
I want to use the same tool to approximately measure time, so that we're
actually measuring the same things in the same way.
Post by David Brown
In lisp, you generally use the
lisp interpreter as your shell and give your expressions there to evaluate.
That's not very user-friendly. I don't expect Java programs to be run
only from bsh, or sh scripts to require that I change my login shell just
to run a program.
Post by David Brown
I haven't even figured out yet how to make a standalone program (I did a
hello world), or parse arguments and such.
Important things for a language to be able to do, I should think.
Post by David Brown
Lisp's time uses the same system call to get the time as time, so I would
expect the same results.
I expect all sorts of things that the profiler and unit tests tell me
aren't true. I don't have that warm fuzzy from the version of lisp I
have available to me. :)
Post by David Brown
Post by SJS
A suduko solver seems like a good fit for a lispy language. :)
I've already moved on to directory parsing and tree walking...
Heh.
Post by David Brown
Post by SJS
Also, it seems like there's going to be a potential problem when the board
size is > 3x3, as then you'll have items that are bigger than your power
increment.
Yes, that's a bug. The 10 was just for debugging, and I forgot it.
Perhaps someone fluent in lisp could offer some constructive criticism.
Post by David Brown
Although there are far bigger problems with larger boards, such as utterly
rediculous amounts of memory needed.
Ah. Rouge-ish behavior, eh?
Post by David Brown
For larger puzzles, a smarter algorithm is definitely needed. There are
actually fairly simple algorithms to always solve the puzzle, but they
won't necessarily have the smallest number of moves.
I think they'd be harder to grok than the plain old search. What do they
do, have a series of "swap" operations that leave the other tiles unmoved?
--
I have come to distrust languages that are self-contained
To the point where the OS compatibility is at best feigned.
Stewart Stremler
David Brown
2008-01-12 22:13:24 UTC
Permalink
Post by SJS
Post by David Brown
For larger puzzles, a smarter algorithm is definitely needed. There are
actually fairly simple algorithms to always solve the puzzle, but they
won't necessarily have the smallest number of moves.
I think they'd be harder to grok than the plain old search. What do they
do, have a series of "swap" operations that leave the other tiles unmoved?
Just a couple of simple transforms:

- First, mutate the goal until the blank space is in the center (or as
close as it can be. Remember these moves.

- For n>3 solve the corners, then the edges. The rules aren't all that
complicated, with a few cases to move pairs in. When n=3, you can
brute force it, or there are a few simple rules to do it easily. When
n=2, it's just a rotation. n=1 is a completely empty board, so is
trivially.

- Now there is a solved ring around the edge. Ignore that, and treat it
as an n-2/n-2 board, and solve that.

- Once it's solved, reverse the moves you made on the goal to get the
true goal.

It's probably easier code, since it doesn't have to remember previous
positions. It still takes a long time for large boards, but it is on the
order of n^3 and needs reasonable memory (only enough for the board and a
few extra variables).

Dave
Andrew Lentvorski
2008-01-12 15:54:16 UTC
Permalink
Post by David Brown
(defconstant solved-board
(let ((nums (loop for i from 1 to full-size
collect (and (< i full-size) i))))
(make-array full-size :initial-contents nums))
"The final solved board")
While I have no problem with this, lisp-niks would not approve of your
use of loop.

-a
David Brown
2008-01-12 21:59:49 UTC
Permalink
Post by David Brown
(defconstant solved-board
(let ((nums (loop for i from 1 to full-size
collect (and (< i full-size) i))))
(make-array full-size :initial-contents nums))
"The final solved board")
While I have no problem with this, lisp-niks would not approve of your use
of loop.
Are any of these people still around? LOOP is an outstanding example of
how lisp macros can be used to improve the language.

I find I spend a whole lot less time thinking about how to write iterations
using LOOP than I ever did in Scheme, or OCaml, or Haskell.

I think the main argument with LOOP is that it isn't very lisp-like,
basically defining it's own domain-specific language. But, domain-specific
languages are common in lisp, so why complain when one is built-in.

Dave
Andrew Lentvorski
2008-01-12 16:03:31 UTC
Permalink
Post by SJS
Finding a good problem is a wonderful thing.
A suduko solver seems like a good fit for a lispy language. :)
I was less interested in the "learning the language" issue than
Stewart's "do it all without a reference".

To my mind, the second task was actually a good test of the language.
The fact that Python was good enough that I remembered 98% of it, had to
test about 1%, and had to run grep on the installed Python codebase for
the last 1% ("argv" is in "sys" ... ah, right) is a good stress test.

Besides, I'm not interested in problems that fit a language well. I'm
interested in problems that *don't* fit the language well. That's the
test. You don't always know the form of the solution to a problem a
priori.

-a
SJS
2008-01-12 17:52:54 UTC
Permalink
Post by Andrew Lentvorski
Post by SJS
Finding a good problem is a wonderful thing.
A suduko solver seems like a good fit for a lispy language. :)
I was less interested in the "learning the language" issue than
Stewart's "do it all without a reference".
To my mind, the second task was actually a good test of the language.
Ah!

Yes, I see. Especially a language that one hasn't used in awhile; had
I been using perl heavily in the previous week, it wouldn't have been
hard in perl... as I hadn't "used perl in anger" for quite some time,
it would be hopeless to attempt that program in perl.

It wouldn't have been any trouble in Java, but that's because I use
Java all the time. Wouldn't be a good test.
Post by Andrew Lentvorski
The fact that Python was good enough that I remembered 98% of it, had to
test about 1%, and had to run grep on the installed Python codebase for
the last 1% ("argv" is in "sys" ... ah, right) is a good stress test.
Non-trivial but simple program in a language you used extensively but
haven't touched in awhile, without significant reliance on references.

Hm. Say I were to do this in Smalltalk (gc, lots of built-in datatypes);
would it be fair (in terms of a 'stress test') to use the GUI development
environment?
Post by Andrew Lentvorski
Besides, I'm not interested in problems that fit a language well. I'm
interested in problems that *don't* fit the language well. That's the
test. You don't always know the form of the solution to a problem a
priori.
You can write a compiler in COBOL. Doesn't mean that one /should/; but
if it's the best tool around, it's better than nothing.
--
I should perhaps collect the comments and bugs
And fix the code up and polish it for you lugs.
Stewart Stremler
David Brown
2008-01-12 22:15:10 UTC
Permalink
Post by Andrew Lentvorski
Besides, I'm not interested in problems that fit a language well. I'm
interested in problems that *don't* fit the language well. That's the
test. You don't always know the form of the solution to a problem a
priori.
I seem to have a habit of doing this, such as trying to write backup
utilities in Lisp or weird things like that.

The main problem I'm having with lisp is that the implementations seem to
be fairly lazy about keeping bindings to C libraries working. Common lisp
defines a DIRECTORY function to iterate a directory, but it is required to
be worthless for what I want, since it has to resolve symlinks.

Dave
David Brown
2008-02-29 08:44:51 UTC
Permalink
Post by SJS
The loop with two fors is kind of odd; I think I see what it's doing.
I just discovered the Common Lisp "iterate" package
<http://common-lisp.net/project/iterate/>. It's basically an attempt to
get the usefulness of loop, but done in a more lisp-friendly syntax. Each
term is group as a separate list (with parens), and consists of a keyword
at the start followed by keyword value pairs. It also fixes the
ambiguities of 'loop' and defines a way to extend the syntax when needed.

As far as the multiple "for" keywords in a list moving parallel variables.
This can be done with C loops as well.

for (x = 0, y = 0;
x < 7;
x++, y += 7)
...

David

John H. Robinson, IV
2008-01-08 11:37:32 UTC
Permalink
Post by Barry Gershenfeld
real 0m37.930s
user 0m0.000s
sys 0m0.000s
...on a screamin' 533MHz Pentium, in cygwin, under Windows 98.
...uphill, both ways.
% time ./3x3 "2468135 7" "12345678 " > /dev/null
2008-01-08T11:32:17-0800
./3x3 "2468135 7" "12345678 " > /dev/null 3.17s user 0.20s system 99% cpu 3.379 total

(I have time aliased to: date -Isec; time)

% grep name /proc/cpuinfo
model name : Intel(R) Pentium(R) 4 CPU 3.40GHz
model name : Intel(R) Pentium(R) 4 CPU 3.40GHz
% free -m
total used free shared buffers cached
Mem: 2012 1689 323 0 0 1184
-/+ buffers/cache: 505 1507
Swap: 1906 0 1906

% uname -a; cat /etc/debian_version
Linux chao 2.6.18-5-amd64 #1 SMP Sat Dec 22 20:43:59 UTC 2007 x86_64 GNU/Linux
4.0

No comments on code, other than it works and few compiler warnings when
I typed ``make 3x3''.

-john

3x3.c: In function 'new':
3x3.c:208: warning: incompatible implicit declaration of built-in function 'strncpy'
3x3.c: In function 'main':
3x3.c:418: warning: incompatible implicit declaration of built-in function 'strlen'
3x3.c:421: warning: incompatible implicit declaration of built-in function 'strncpy'
SJS
2008-01-08 12:22:32 UTC
Permalink
Post by Barry Gershenfeld
Post by SJS
sliding-tile puzzle of a lizard. There were 8 pieces on a little 3x3
That night, the cat got up in my lap, arranged itself across my
forearms, so I decided to "solve" the 3x3 8-piece sliding tile puzzle.
Now, this would have been an ideal time to try out Ruby, but with a
purring cat trapping my arms, that wasn't really practical.
Just once, I wanna see c/cat/wife
Not much code gets written then.
Post by Barry Gershenfeld
Post by SJS
Same with perl or TCL... I'd need a reference book at hand, and that
wasn't going to happen unless I dumped the cat. And it's just wrong
to dump a purring cat, so I fell back on that old standby we call C.
So, you're still able to operate. Books aren't really required; with the
Web you have all the reference material available. Admittedly, some are
better than others. PHP shines here.
Of course, with the web, you need a mouse (not readily accessible)
or lynx (not always very good for reference material).

I had manpages near at hand.
Post by Barry Gershenfeld
Post by SJS
Just for fun. It's just 'noodling'... futzing around, really, until
I got a reasonable answer. Then I went to bed.
Just as I expected. Stewart coughs, and out comes runnable code.
Nah, I had a couple of boneheaded errors that resulted in memory
corruption and segfaults.
Post by Barry Gershenfeld
Post by SJS
There's lots of stuff to criticize. Have fun.
-----------------------------------------------------------------------------
* $Id: sliding_nine.c,v 1.2 2007/12/24 19:55:58 stremler Exp $
Aren't we supposed to embed this in the object somehow ( :) ...troll )
Actually, that's a good point.
Post by Barry Gershenfeld
I let the machine do the criticizing. Who am I to judge?
Who do you have to be?
Post by Barry Gershenfeld
$ gcc sliding_nine.c -o sli -Wall
Ah, "failed to compile with -Wall", another one.
Post by Barry Gershenfeld
sliding_nine.c:74: warning: control reaches end of non-void function
Yup, bug.
Post by Barry Gershenfeld
sliding_nine.c:206: warning: unused variable `a'
sliding_nine.c:206: warning: unused variable `b'
sliding_nine.c:246: warning: unused variable `p'
sliding_nine.c:247: warning: unused variable `temp'
Yup, code needs to be cleaned up.
Post by Barry Gershenfeld
Okay, but the premise is that it /runs/
$ ./sli.exe
Usage: ./sli start end
start = 9 character board configuration
end = 9 character board configuration
(Note that a blank is REQUIRED!)
$ ./sli.exe 246813579 123456789
Starting with '246813579' and trying for '123456789'
start: 0x9700f8 end: 0x970120
Bad board configuration: '246813579' in sliding_nine.c at 259
Segmentation fault (core dumped)
Hm. That should be an exit() as well.

So, -Wall is a big one. :)
Post by Barry Gershenfeld
Hmm...OK, there should only be 8 tiles of the 9. "Note that a blank is
REQUIRED!"
$ ./sli.exe 2468135 7 1234567 8
Usage: ./sli start end
start = 9 character board configuration
end = 9 character board configuration
(Note that a blank is REQUIRED!)
$ ./sli.exe "2468135 7" "12345678 "
Starting with '2468135 7' and trying for '12345678 '
start: 0x9700f8 end: 0x970120
(now it's thinking)...
[2] [4] [6]
[8] [1] [3]
[5] [ ] [7]
[2] [4] [6]
[8] [ ] [3]
[5] [1] [7]
and so on, until
[1] [2] [3]
[4] [5] [6]
[7] [8] [ ]
All correct, I presume?
Post by Barry Gershenfeld
$ time ./sli.exe "2468135 7" "12345678 " > sli.txp
real 0m37.930s
user 0m0.000s
sys 0m0.000s
...on a screamin' 533MHz Pentium, in cygwin, under Windows 98.
...uphill, both ways.
Shift! Shift!
Post by Barry Gershenfeld
(Okay peanut gallery, this is where you post /your/ time...)
What, it has bugs, and you want to test *performance*? :-P
--
Always remember to use dash Wall
To ensure cleanliness of you call
Stewart Stremler
Christopher Smith
2008-01-08 13:08:34 UTC
Permalink
Post by SJS
I as at a friend's place over the holidays, and I picked up a little
sliding-tile puzzle of a lizard. There were 8 pieces on a little 3x3
grid, and I futzed with it a bit and decided that I didn't even like
those sorts of puzzles when they were that small.
That night, the cat got up in my lap, arranged itself across my
forearms, so I decided to "solve" the 3x3 8-piece sliding tile puzzle.
Now, this would have been an ideal time to try out Ruby, but with a
purring cat trapping my arms, that wasn't really practical.
This seems like the kind of problem that just cries out for dynamic
programming, no?

--Chris
SJS
2008-01-08 13:15:19 UTC
Permalink
Post by Christopher Smith
Post by SJS
I as at a friend's place over the holidays, and I picked up a little
sliding-tile puzzle of a lizard. There were 8 pieces on a little 3x3
grid, and I futzed with it a bit and decided that I didn't even like
those sorts of puzzles when they were that small.
That night, the cat got up in my lap, arranged itself across my
forearms, so I decided to "solve" the 3x3 8-piece sliding tile puzzle.
Now, this would have been an ideal time to try out Ruby, but with a
purring cat trapping my arms, that wasn't really practical.
This seems like the kind of problem that just cries out for dynamic
programming, no?
The puzzle problem? Yes.

The cat, however is not a problem, merely a constraint.
--
Cats are God's gift to (and test of) man,
The goal is to make 'em purr as oft we can.
Stewart Stremler
John H. Robinson, IV
2008-01-08 13:14:34 UTC
Permalink
Post by SJS
/*
* $Id: sliding_nine.c,v 1.2 2007/12/24 19:55:58 stremler Exp $
*/
/*
* This program 'solves' the 3x3 sliding-puzzle problem.
* Not robustly, it was hacked together in an evening. No design,
* no testing, no good C programming habits.
*
* Author: Stewart Stremler
* License: public domain
*/
#include <stdlib.h>
#include <stdio.h>
#include <strings.h>
#ifndef FALSE
#define FALSE 0
#define TRUE 1
#endif
#define ERROR_EMPTY_ARG "Programmer error. Empty argument in %s at %d\n"
#define ERROR_MALLOC_FAIL "Failed to allocate memory. In %s at %d\n"
#define ERROR_BAD_BOARD "Bad board configuration: '%s' in %s at %d\n"
#define ERROR_SWITCH_BROKE "Unknown value in switch: %d in %s at %d\n"
/* change BLANK to use a different 'empty' character. '_' might be good. */
#define BLANK ' '
#define BLANK '.'
/* allows entry of board with 10-key */
Post by SJS
/* The fundamental board structure. We have nine puzzle slots, but
* we want to treat it as a string, so we need space for the terminating
* null. We want to eliminate repeats, so we keep track of the parent,
* which also offers a simple way to print out the final pieces in order.
*/
typedef struct {
char board[10];
void *moves[4];
void *prev;
} configuration;
/* We need a simple queue of arbitrary size, so we use a singly linked list.
*/
typedef struct {
configuration *data;
void *next;
} dequenode;
/* We push new items to the tail and pull them from the head for fast
* O(1) access.
* TODO - also keep a count of the # of elements in the queue?
*/
typedef struct {
dequenode *head;
dequenode *tail;
} deque;
/* ----------------------------------------------------------------- */
/* make_dequeue
* creates a new queue.
* exits on malloc failure.
*/
deque *make_deque() {
deque *p;
p = malloc( sizeof( deque ) );
if ( p == NULL ) {
fprintf( stderr, ERROR_MALLOC_FAIL, __FILE__, __LINE__ );
exit( EXIT_FAILURE );
}
p->head = NULL;
p->tail = NULL;
}
/* deque_insert
* inserts the current node into the queue.
* exits on malloc failure.
*/
void deque_insert( deque *d, configuration *current ) {
dequenode *n, *t;
n = malloc( sizeof( dequenode ) );
if ( n == NULL ) {
fprintf( stderr, ERROR_MALLOC_FAIL, __FILE__, __LINE__ );
exit( EXIT_FAILURE );
}
n->data = current;
if ( d->head == NULL ) {
d->head = n;
} else {
t = d->tail;
t->next = (struct dequenode *)n;
/*d->tail->next = n;*/
}
d->tail = n;
}
/* deque_remove
* removes the oldest node from the queue.
* do not call if queue is empty.
*/
configuration *deque_remove( deque *d ) {
configuration *p;
dequenode *q;
q = d->head;
p = q->data;
if ( d->head == d->tail ) {
d->head = NULL;
d->tail = NULL;
} else {
d->head = (dequenode *)d->head->next;
}
free( q );
return p;
}
/* deque_empty
* answers if the queue is empty.
*/
int deque_empty( deque *d ) {
return d->head == NULL;
}
/* deque_size
* answers the number of items in the queue.
* warning - very slow. Walks the linked list. See TODO for struct.
*/
int deque_size( deque *d ) {
int count = 0;
dequenode *p = d->head;
dequenode *end = d->tail;
while ( p != end ) { count++; p = p->next; }
return count;
}
/* ----------------------------------------------------------------- */
/* got_match
* Answers if the two configurations are equivalent.
* Exits on programmer error.
*/
int got_match( configuration *current, configuration *final ) {
if ( current == NULL ) {
return FALSE;
}
if ( final == NULL ) {
fprintf( stderr, ERROR_EMPTY_ARG, __FILE__, __LINE__ );
/*return FALSE;*/
exit( EXIT_FAILURE );
}
return ! (strncmp( current->board, final->board, 10 ));
}
/* got_repeat
* Walks the ancestor list looking for a configuration that is equivalent
* to the current node. This is an optimization step.
*/
int got_repeat( configuration *current ) {
configuration *p;
p = (configuration *)current->prev;
while ( p != NULL ) {
if ( got_match( p, current ) ) return TRUE;
p = (configuration *)p->prev;
}
return FALSE;
}
/* new
* Answers a clone of the the provided configuration. A NULL configuration
* will cause an uninitialized configuration to be created.
* TODO - how much of the brute-force initialization can we remove?
*/
configuration *new( configuration *current ) {
configuration *p;
p = malloc( sizeof( configuration ) );
if ( p == NULL ) {
fprintf( stderr, ERROR_MALLOC_FAIL, __FILE__, __LINE__);
exit( EXIT_FAILURE );
}
p->board[0] = '\0';
p->board[1] = '\0';
p->board[2] = '\0';
p->board[3] = '\0';
p->board[4] = '\0';
p->board[5] = '\0';
p->board[6] = '\0';
p->board[7] = '\0';
p->board[8] = '\0';
p->board[9] = '\0';
p->board[10] = '\0';
p->prev = NULL;
p->moves[0] = NULL;
p->moves[1] = NULL;
p->moves[2] = NULL;
p->moves[3] = NULL;
if ( current != NULL ) {
char *a, *b;
p->prev = (struct configuration *)current;
strncpy( p->board, current->board, 10 );
}
return p;
}
/* swap_tile
* Swaps the board elements at the specified location.
* Assumes arguments are valid and sensible.
*/
void swap_tile( configuration *current, int source, int dest ) {
char temp;
temp = current->board[dest];
current->board[dest] = current->board[source];
current->board[source] = temp;
}
/* make_child
* Creates a unique new child of the current configuration using the
* specified swap of tiles and adding to the specified move slot.
* If the child repeats an ancestor state, it is discarded.
*/
void make_child( configuration *current, int move, int dest, int source ) {
configuration *p;
p = new( current );
swap_tile( p, source, dest );
if ( ! got_repeat( p ) ) {
current->moves[move] = (struct configuration *)p;
} else {
free( p );
}
}
/* fill_children
* Creates all the possible children of the current configuration and
* adds them to the current configuration.
*/
void fill_children( configuration *current ) {
configuration *p;
char temp;
int i;
int blank = -1;
for ( i = 0; i < 9; i++ ) {
if ( current->board[i] == BLANK ) {
blank = i;
break;
}
}
if ( blank < 0 ) {
fprintf( stderr, ERROR_BAD_BOARD, current->board, __FILE__, __LINE__);
return;
}
/*
* 0 | 1 | 2
* -----+-----+-----
* 3 | 4 | 5
* -----+-----+-----
* 6 | 7 | 8
*
*/
switch ( blank ) {
case 0: /* 1->0, 3->0 */
make_child( current, 0, 0, 1 );
make_child( current, 1, 0, 3 );
break;
case 1: /* 0->1, 2->1, 4->1 */
make_child( current, 0, 1, 0 );
make_child( current, 1, 1, 2 );
make_child( current, 2, 1, 4 );
break;
case 2: /* 1->2, 5->2 */
make_child( current, 0, 2, 1 );
make_child( current, 1, 2, 5 );
break;
case 3: /* 0->3, 4->3, 6-> 3 */
make_child( current, 0, 3, 0 );
make_child( current, 1, 3, 4 );
make_child( current, 2, 3, 6 );
break;
case 4: /* 1->4, 3->4, 5->4, 7->4 */
make_child( current, 0, 4, 1 );
make_child( current, 1, 4, 3 );
make_child( current, 2, 4, 5 );
make_child( current, 3, 4, 7 );
break;
case 5: /* 2->5, 4->5, 8->5 */
make_child( current, 0, 5, 2 );
make_child( current, 1, 5, 4 );
make_child( current, 2, 5, 8 );
break;
case 6: /* 3->6, 7->6 */
make_child( current, 0, 6, 3 );
make_child( current, 1, 6, 7 );
break;
case 7: /* 6->7, 4->7, 8->7 */
make_child( current, 0, 7, 4 );
make_child( current, 1, 7, 6 );
make_child( current, 2, 7, 8 );
break;
case 8: /* 5->8, 7->8 */
make_child( current, 0, 8, 5 );
make_child( current, 1, 8, 7 );
break;
fprintf( stderr, ERROR_SWITCH_BROKE, blank, __FILE__, __LINE__ );
}
}
/* walk_solutions
* Breadth-first walk of the solution tree and find the first solution.
*/
configuration *walk_solutions( configuration *initial, configuration *final ) {
configuration *current;
deque *queue;
int i;
queue = make_deque();
deque_insert( queue, initial );
while ( TRUE ) {
current = deque_remove( queue );
if ( got_match( current, final ) ) {
return current; /* leak memory like mad */
}
#ifdef MONITOR_PROGRESS
i = deque_size( queue );
if ( i % 100 == 0 ) {
if ( i < 1000 ) fprintf(stderr, ".");
else if ( i < 10000 ) fprintf(stderr, ":");
else if ( i < 100000 ) fprintf(stderr, "!");
else fprintf(stderr, "#");
}
#endif
fill_children( current );
for ( i = 0; i < 4; i++ ) {
if ( current->moves[i] != NULL ) {
deque_insert( queue, (configuration *)current->moves[i] );
}
}/* for */
}/* while */
}
/* print_solution_size
* Outputs the number of moves it took to solve the problem.
*/
void print_solution_size( configuration *end ) {
configuration *p;
int count;
count = 0;
p = end;
while ( p != NULL ) {
p = (configuration *)p->prev;
count++;
}
fprintf( stdout, "There are %d steps in the solution.\n", count);
}
/* print_solutions
* Print the solution-stack, in reasonable order.
* Recursive.
*/
void print_solutions( configuration *end ) {
if ( end->prev != NULL ) {
print_solutions( (configuration *)end->prev );
}
int row, col;
for ( row = 0; row < 3; row++ ) {
for ( col = 0; col < 3; col++ ) {
fprintf( stdout, " [%c] ", end->board[row * 3 + col] );
}
fprintf( stdout, "\n" );
}
fprintf( stdout, "\n" );
}
/* ----------------------------------------------------------------- */
/* usage
* Outputs how to use the program.
*/
void usage( char **argv ) {
fprintf( stderr, "Usage: %s start end\n", argv[0]);
fprintf( stderr, "\tstart = 9 character board configuration\n");
fprintf( stderr, "\tend = 9 character board configuration\n");
fprintf( stderr, "\t(Note that a blank is REQUIRED!)\n");
/* change this if change definition of BLANK define */
}
/* main
* program entry-point
*/
int main( int argc, char **argv ) {
configuration *start;
configuration *end;
configuration *solution;
if ( argc != 3 ) { usage( argv ); return EXIT_FAILURE; }
start = new( NULL );
end = new( NULL );
if ( strlen( argv[1] ) != 9 ) { usage( argv ); return EXIT_FAILURE; }
if ( strlen( argv[2] ) != 9 ) { usage( argv ); return EXIT_FAILURE; }
strncpy( start->board, argv[1], 10 );
strncpy( end->board, argv[2], 10 );
fprintf( stdout, "Starting with '%s' and trying for '%s'\n",
start->board, end->board );
fprintf( stdout, "start: %p \t end: %p\n", start, end );
solution = walk_solutions( start, end );
print_solution_size( solution );
print_solutions( solution );
return EXIT_SUCCESS;
}
-----------------------------------------------------------------------------
--
http://www.kernel-panic.org/cgi-bin/mailman/listinfo/kplug-lpsg
Andrew Lentvorski
2008-01-08 13:55:03 UTC
Permalink
Post by SJS
I as at a friend's place over the holidays, and I picked up a little
sliding-tile puzzle of a lizard. There were 8 pieces on a little 3x3
grid, and I futzed with it a bit and decided that I didn't even like
those sorts of puzzles when they were that small.
That night, the cat got up in my lap, arranged itself across my
forearms, so I decided to "solve" the 3x3 8-piece sliding tile
puzzle. Now, this would have been an ideal time to try out Ruby, but
with a purring cat trapping my arms, that wasn't really practical.
Same with perl or TCL... I'd need a reference book at hand, and that
wasn't going to happen unless I dumped the cat. And it's just wrong
to dump a purring cat, so I fell back on that old standby we call C.
Funny. I wouldn't be able to pull that C out without grabbing at K&R.

However, my Python, even after not having written it for probably about
1 1/2 years is *still* just fine. I think you are far more clever than
I in choice of algorithm. I just used a simple recursive descent and
used a hash table to remember what states I already visited.

What is interesting to me is the difference in lines of code. Not
because Python is so much better, but simply because I could use vectors,
hash tables, strings, and sequences directly and Stewart had to reimplement
a data structure (deque).

And this matches my philosophy very well. I *HATE* reimplementing data
structures that already exist.

-a


After about 80 minutes of coding I have:

#!env python

import sys
import copy

availableDirs = [[(1, 0), (0, 1)], [(-1, 0), (0, 1), (1, 0)], [(-1, 0), (0, 1)],
[(0, -1), (1, 0), (0, 1)], [(-1, 0), (0, -1), (1, 0), (0, 1)], [(0, -1), (-1, 0), (0, 1)],
[(1, 0), (0, -1)], [(-1, 0), (0, -1), (1, 0)], [(-1, 0), (0, -1)]]

def swapSpace(puzzleState, direction):
spacePosition = puzzleState.find(" ")

spaceI = spacePosition % 3
spaceJ = spacePosition / 3

coordI = spaceI + direction[0]
coordJ = spaceJ + direction[1]

coordPosition = coordI + coordJ*3

newStateList = []
for ii in range(len(puzzleState)):
if ii == spacePosition:
newStateList.append(puzzleState[coordPosition])
elif ii == coordPosition:
# Redundant, should just use space
newStateList.append(puzzleState[spacePosition])
else:
newStateList.append(puzzleState[ii])

newState = "".join(newStateList)

return newState

def solveSingleStep(solutionState, targetState, visitedSolutions):
flgSolutionFound = False
nextSolutionState = []
solution = None

for (previousSteps, puzzleState) in solutionState:
nextDirs = availableDirs[puzzleState.find(" ")]

visitedSolutions[puzzleState] = True

for testDir in nextDirs:
newState = swapSpace(puzzleState, testDir)

newPreviousSteps = copy.copy(previousSteps)
newPreviousSteps.append(testDir)

if newState == targetState:
flgSolutionFound = True
solution = (newPreviousSteps, newState)
break
elif newState in visitedSolutions:
# New solution has already been visited ... ignore
pass
else:
nextSolutionState.append((newPreviousSteps, newState))

if flgSolutionFound:
break

if flgSolutionFound:
return (True, solution)
else:
return (False, nextSolutionState)

def boardPPrint(currentState):
ll = []
for ii in currentState:
ll.append(ii)
ll = tuple(ll)

print "[%s] [%s] [%s]\n[%s] [%s] [%s]\n[%s] [%s] [%s]\n\n" % ll

def main():
if len(sys.argv) != 3:
print "Wrong number of arguments"
exit()

startingState = sys.argv[1]
targetState = sys.argv[2]

flgSolved = False
solutionState = [([], startingState)]
visitedSolutions = {}

while(not flgSolved):
(flgSolved, newSolutionState) = solveSingleStep(solutionState, targetState, visitedSolutions)
solutionState = newSolutionState

print "NSS:", len(newSolutionState), len(visitedSolutions)


if flgSolved:
print "SOLVED in %d steps: %s" % (len(solutionState[0]), str(solutionState))

currentState = startingState
for ss in solutionState[0]:
boardPPrint(currentState)
currentState = swapSpace(currentState, ss)
boardPPrint(currentState)



if __name__ == "__main__":
main()



andrewl$ time python puzzle3.py "12345678 " " 87654321"
NSS: 2 1
NSS: 4 3
NSS: 8 7
NSS: 16 15
NSS: 20 31
NSS: 40 51
NSS: 66 90
NSS: 128 152
NSS: 164 268
NSS: 316 420
NSS: 456 706
NSS: 862 1102
NSS: 1206 1850
NSS: 2260 2874
NSS: 3162 4767
NSS: 5836 7279
NSS: 7760 11764
NSS: 13920 17402
NSS: 17344 26931
NSS: 29282 37809
NSS: 33280 54802
NSS: 51332 71912
NSS: 52140 95864
NSS: 71268 116088
NSS: 58492 140135
NSS: 65554 155713
NSS: 39710 170273
NSS: 2 171445
SOLVED in 28 steps: ([(-1, 0), (-1, 0), (0, -1), (0, -1), (1, 0), (1, 0), (0, 1), (0, 1), (-1, 0), (-1, 0), (0, -1), (0, -1), (1, 0), (1, 0), (0, 1), (0, 1), (-1, 0), (-1, 0), (0, -1), (0, -1), (1, 0), (1, 0), (0, 1), (0, 1), (-1, 0), (-1, 0), (0, -1), (0, -1)], ' 87654321')
[1] [2] [3]
[4] [5] [6]
[7] [8] [ ]


[1] [2] [3]
[4] [5] [6]
[7] [ ] [8]


[1] [2] [3]
[4] [5] [6]
[ ] [7] [8]


[1] [2] [3]
[ ] [5] [6]
[4] [7] [8]


[ ] [2] [3]
[1] [5] [6]
[4] [7] [8]


[2] [ ] [3]
[1] [5] [6]
[4] [7] [8]


[2] [3] [ ]
[1] [5] [6]
[4] [7] [8]


[2] [3] [6]
[1] [5] [ ]
[4] [7] [8]


[2] [3] [6]
[1] [5] [8]
[4] [7] [ ]


[2] [3] [6]
[1] [5] [8]
[4] [ ] [7]


[2] [3] [6]
[1] [5] [8]
[ ] [4] [7]


[2] [3] [6]
[ ] [5] [8]
[1] [4] [7]


[ ] [3] [6]
[2] [5] [8]
[1] [4] [7]


[3] [ ] [6]
[2] [5] [8]
[1] [4] [7]


[3] [6] [ ]
[2] [5] [8]
[1] [4] [7]


[3] [6] [8]
[2] [5] [ ]
[1] [4] [7]


[3] [6] [8]
[2] [5] [7]
[1] [4] [ ]


[3] [6] [8]
[2] [5] [7]
[1] [ ] [4]


[3] [6] [8]
[2] [5] [7]
[ ] [1] [4]


[3] [6] [8]
[ ] [5] [7]
[2] [1] [4]


[ ] [6] [8]
[3] [5] [7]
[2] [1] [4]


[6] [ ] [8]
[3] [5] [7]
[2] [1] [4]


[6] [8] [ ]
[3] [5] [7]
[2] [1] [4]


[6] [8] [7]
[3] [5] [ ]
[2] [1] [4]


[6] [8] [7]
[3] [5] [4]
[2] [1] [ ]


[6] [8] [7]
[3] [5] [4]
[2] [ ] [1]


[6] [8] [7]
[3] [5] [4]
[ ] [2] [1]


[6] [8] [7]
[ ] [5] [4]
[3] [2] [1]


[ ] [8] [7]
[6] [5] [4]
[3] [2] [1]



real 0m15.413s
user 0m15.181s
sys 0m0.160s

Time is in a 2.16GHz core 2 duo
SJS
2008-01-09 01:38:23 UTC
Permalink
[snip]
Post by Andrew Lentvorski
Post by SJS
Same with perl or TCL... I'd need a reference book at hand, and that
wasn't going to happen unless I dumped the cat. And it's just wrong
to dump a purring cat, so I fell back on that old standby we call C.
Funny. I wouldn't be able to pull that C out without grabbing at K&R.
My hardest problem with C syntax seems to be in getting the typedefs right.
Post by Andrew Lentvorski
However, my Python, even after not having written it for probably about
1 1/2 years is *still* just fine. I think you are far more clever than
I in choice of algorithm. I just used a simple recursive descent and
used a hash table to remember what states I already visited.
You have amazing powers of recollection; after a year and a half, I
think I'd need to crib quite a bit in *any* language I know.
Post by Andrew Lentvorski
What is interesting to me is the difference in lines of code. Not
because Python is so much better, but simply because I could use vectors,
hash tables, strings, and sequences directly and Stewart had to reimplement
a data structure (deque).
Yes. A language with a better set of tools on hand would have made
the writing of the code go a lot faster. I *thought* about reaching
for Java, but, well, where's the fun in that? I do that all the time.

I should've tried this with Smalltalk (as GST doesn't require the code
browser) and I could have looked at some of my sample code for reminders
about which classes to use. A queue is just a stream, after all, so the
same approach would have worked fine.
Post by Andrew Lentvorski
And this matches my philosophy very well. I *HATE* reimplementing data
structures that already exist.
As an exercise in entertainment, I don't mind so much. :)
A bit faster than me too. Using those high-level languages helps a lot,
doesn't it?

[chop]
--
I have no intention of starting a row
So peanuts I shall refrain to throw.
Stewart Stremler
Gabriel Sechan
2008-01-08 14:16:50 UTC
Permalink
Comments inline. For fun, I'm running this like I would a work code review- things I would want to see at least defended before allowing checkin. I'm not looking for better algorithms and I'm not looking for minor bugs, I'm just doing a style review.

----------------------------------------
Date: Tue, 8 Jan 2008 02:02:44 -0800
Subject: Code Criticism
#ifndef FALSE
#define FALSE 0
#define TRUE 1
#endif
C99 introduced a bool type, as well as false and true keywords. We shouldn't be using #defined true false anymore. Even without that, this should be an enum, not defines.
#define ERROR_EMPTY_ARG "Programmer error. Empty argument in %s at %d\n"
#define ERROR_MALLOC_FAIL "Failed to allocate memory. In %s at %d\n"
#define ERROR_BAD_BOARD "Bad board configuration: '%s' in %s at %d\n"
#define ERROR_SWITCH_BROKE "Unknown value in switch: %d in %s at %d\n"
/* change BLANK to use a different 'empty' character. '_' might be good. */
#define BLANK ' '
C99 also introduced const variables, just like C++. These have type checking, #defines do not. Use them instead.
/* The fundamental board structure. We have nine puzzle slots, but
* we want to treat it as a string, so we need space for the terminating
* null. We want to eliminate repeats, so we keep track of the parent,
* which also offers a simple way to print out the final pieces in order.
*/
typedef struct {
char board[10];
void *moves[4];
void *prev;
} configuration;
Bad mistake in using strncmp and strings. This isn't string data. Use the memcmp, memcpy, etc functions instead. That also means you only need char[9]. Unless you really only want to check up til the first null char, which seems a bit... odd




General comment- couldn't you have found a queue library prewritten?
/* We need a simple queue of arbitrary size, so we use a singly linked list.
*/
typedef struct {
configuration *data;
void *next;
} dequenode;
/* We push new items to the tail and pull them from the head for fast
* O(1) access.
* TODO - also keep a count of the # of elements in the queue?
*/
typedef struct {
dequenode *head;
dequenode *tail;
} deque;
/* ----------------------------------------------------------------- */
/* make_dequeue
* creates a new queue.
* exits on malloc failure.
*/
deque *make_deque() {
deque *p;
p = malloc( sizeof( deque ) );
if ( p == NULL ) {
fprintf( stderr, ERROR_MALLOC_FAIL, __FILE__, __LINE__ );
exit( EXIT_FAILURE );
}
p->head = NULL;
p->tail = NULL;
}
exiting like that is ok for such a minor program, but its a bad idea in anything bigger. If you wanted to reuse this code, return NULL on error instead and let the calling code exit.
/* deque_insert
* inserts the current node into the queue.
* exits on malloc failure.
*/
void deque_insert( deque *d, configuration *current ) {
dequenode *n, *t;
n = malloc( sizeof( dequenode ) );
if ( n == NULL ) {
fprintf( stderr, ERROR_MALLOC_FAIL, __FILE__, __LINE__ );
exit( EXIT_FAILURE );
}
n->data = current;
if ( d->head == NULL ) {
d->head = n;
} else {
t = d->tail;
t->next = (struct dequenode *)n;
/*d->tail->next = n;*/
}
d->tail = n;
}
Really bad variable names.
/* deque_remove
* removes the oldest node from the queue.
* do not call if queue is empty.
*/
configuration *deque_remove( deque *d ) {
configuration *p;
dequenode *q;
q = d->head;
p = q->data;
if ( d->head == d->tail ) {
d->head = NULL;
d->tail = NULL;
} else {
d->head = (dequenode *)d->head->next;
}
free( q );
return p;
}
/* deque_empty
* answers if the queue is empty.
*/
int deque_empty( deque *d ) {
return d->head == NULL;
}
/* deque_size
* answers the number of items in the queue.
* warning - very slow. Walks the linked list. See TODO for struct.
*/
int deque_size( deque *d ) {
int count = 0;
dequenode *p = d->head;
dequenode *end = d->tail;
while ( p != end ) { count++; p = p->next; }
return count;
}
If you expect to call size frequently, add a size member to the structure and increment/decrement it on insert/remove. Walking is expensive.
/* ----------------------------------------------------------------- */
/* got_match
* Answers if the two configurations are equivalent.
* Exits on programmer error.
*/
int got_match( configuration *current, configuration *final ) {
if ( current == NULL ) {
return FALSE;
}
if ( final == NULL ) {
fprintf( stderr, ERROR_EMPTY_ARG, __FILE__, __LINE__ );
/*return FALSE;*/
exit( EXIT_FAILURE );
}
return ! (strncmp( current->board, final->board, 10 ));
}
As previously said- use memcmp.
/* got_repeat
* Walks the ancestor list looking for a configuration that is equivalent
* to the current node. This is an optimization step.
*/
int got_repeat( configuration *current ) {
configuration *p;
p = (configuration *)current->prev;
while ( p != NULL ) {
if ( got_match( p, current ) ) return TRUE;
p = (configuration *)p->prev;
}
return FALSE;
}
Why do you have two list mechanisms? Why not use a dequeue inside the configuration?
/* new
* Answers a clone of the the provided configuration. A NULL configuration
* will cause an uninitialized configuration to be created.
* TODO - how much of the brute-force initialization can we remove?
*/
configuration *new( configuration *current ) {
configuration *p;
p = malloc( sizeof( configuration ) );
if ( p == NULL ) {
fprintf( stderr, ERROR_MALLOC_FAIL, __FILE__, __LINE__);
exit( EXIT_FAILURE );
}
p->board[0] = '\0';
p->board[1] = '\0';
p->board[2] = '\0';
p->board[3] = '\0';
p->board[4] = '\0';
p->board[5] = '\0';
p->board[6] = '\0';
p->board[7] = '\0';
p->board[8] = '\0';
p->board[9] = '\0';
p->board[10] = '\0';
p->prev = NULL;
p->moves[0] = NULL;
p->moves[1] = NULL;
p->moves[2] = NULL;
p->moves[3] = NULL;
if ( current != NULL ) {
char *a, *b;
p->prev = (struct configuration *)current;
strncpy( p->board, current->board, 10 );
}
return p;
}
Loops to initialize arrays. Don't initialize the board to nulls if you're just going to overwrite it if current!=NULL (in otherwise, put it in an else).
/* swap_tile
* Swaps the board elements at the specified location.
* Assumes arguments are valid and sensible.
*/
void swap_tile( configuration *current, int source, int dest ) {
char temp;
temp = current->board[dest];
current->board[dest] = current->board[source];
current->board[source] = temp;
}
/* make_child
* Creates a unique new child of the current configuration using the
* specified swap of tiles and adding to the specified move slot.
* If the child repeats an ancestor state, it is discarded.
*/
void make_child( configuration *current, int move, int dest, int source ) {
configuration *p;
p = new( current );
swap_tile( p, source, dest );
if ( ! got_repeat( p ) ) {
current->moves[move] = (struct configuration *)p;
} else {
free( p );
}
}
/* fill_children
* Creates all the possible children of the current configuration and
* adds them to the current configuration.
*/
void fill_children( configuration *current ) {
configuration *p;
char temp;
int i;
int blank = -1;
for ( i = 0; i < 9; i++ ) {
if ( current->board[i] == BLANK ) {
blank = i;
break;
}
}
if ( blank < 0 ) {
fprintf( stderr, ERROR_BAD_BOARD, current->board, __FILE__, __LINE__);
return;
}
/*
* 0 | 1 | 2
* -----+-----+-----
* 3 | 4 | 5
* -----+-----+-----
* 6 | 7 | 8
*
*/
switch ( blank ) {
case 0: /* 1->0, 3->0 */
make_child( current, 0, 0, 1 );
make_child( current, 1, 0, 3 );
break;
case 1: /* 0->1, 2->1, 4->1 */
make_child( current, 0, 1, 0 );
make_child( current, 1, 1, 2 );
make_child( current, 2, 1, 4 );
break;
case 2: /* 1->2, 5->2 */
make_child( current, 0, 2, 1 );
make_child( current, 1, 2, 5 );
break;
case 3: /* 0->3, 4->3, 6-> 3 */
make_child( current, 0, 3, 0 );
make_child( current, 1, 3, 4 );
make_child( current, 2, 3, 6 );
break;
case 4: /* 1->4, 3->4, 5->4, 7->4 */
make_child( current, 0, 4, 1 );
make_child( current, 1, 4, 3 );
make_child( current, 2, 4, 5 );
make_child( current, 3, 4, 7 );
break;
case 5: /* 2->5, 4->5, 8->5 */
make_child( current, 0, 5, 2 );
make_child( current, 1, 5, 4 );
make_child( current, 2, 5, 8 );
break;
case 6: /* 3->6, 7->6 */
make_child( current, 0, 6, 3 );
make_child( current, 1, 6, 7 );
break;
case 7: /* 6->7, 4->7, 8->7 */
make_child( current, 0, 7, 4 );
make_child( current, 1, 7, 6 );
make_child( current, 2, 7, 8 );
break;
case 8: /* 5->8, 7->8 */
make_child( current, 0, 8, 5 );
make_child( current, 1, 8, 7 );
break;
fprintf( stderr, ERROR_SWITCH_BROKE, blank, __FILE__, __LINE__ );
}
}
There has got to be a better solution than a giant switch. Plus if you can do it programatically, it expands to more than 3x3
/* walk_solutions
* Breadth-first walk of the solution tree and find the first solution.
*/
configuration *walk_solutions( configuration *initial, configuration *final ) {
configuration *current;
deque *queue;
int i;
queue = make_deque();
deque_insert( queue, initial );
while ( TRUE ) {
current = deque_remove( queue );
if ( got_match( current, final ) ) {
return current; /* leak memory like mad */
}
#ifdef MONITOR_PROGRESS
i = deque_size( queue );
if ( i % 100 == 0 ) {
if ( i < 1000 ) fprintf(stderr, ".");
else if ( i < 10000 ) fprintf(stderr, ":");
else if ( i < 100000 ) fprintf(stderr, "!");
else fprintf(stderr, "#");
}
#endif
fill_children( current );
for ( i = 0; i < 4; i++ ) {
if ( current->moves[i] != NULL ) {
deque_insert( queue, (configuration *)current->moves[i] );
}
}/* for */
}/* while */
}
/* print_solution_size
* Outputs the number of moves it took to solve the problem.
*/
void print_solution_size( configuration *end ) {
configuration *p;
int count;
count = 0;
p = end;
while ( p != NULL ) {
p = (configuration *)p->prev;
count++;
}
fprintf( stdout, "There are %d steps in the solution.\n", count);
}
/* print_solutions
* Print the solution-stack, in reasonable order.
* Recursive.
*/
void print_solutions( configuration *end ) {
if ( end->prev != NULL ) {
print_solutions( (configuration *)end->prev );
}
int row, col;
for ( row = 0; row < 3; row++ ) {
for ( col = 0; col < 3; col++ ) {
fprintf( stdout, " [%c] ", end->board[row * 3 + col] );
}
fprintf( stdout, "\n" );
}
fprintf( stdout, "\n" );
}
/* ----------------------------------------------------------------- */
/* usage
* Outputs how to use the program.
*/
void usage( char **argv ) {
fprintf( stderr, "Usage: %s start end\n", argv[0]);
fprintf( stderr, "\tstart = 9 character board configuration\n");
fprintf( stderr, "\tend = 9 character board configuration\n");
fprintf( stderr, "\t(Note that a blank is REQUIRED!)\n");
/* change this if change definition of BLANK define */
}
/* main
* program entry-point
*/
int main( int argc, char **argv ) {
configuration *start;
configuration *end;
configuration *solution;
if ( argc != 3 ) { usage( argv ); return EXIT_FAILURE; }
start = new( NULL );
end = new( NULL );
if ( strlen( argv[1] ) != 9 ) { usage( argv ); return EXIT_FAILURE; }
if ( strlen( argv[2] ) != 9 ) { usage( argv ); return EXIT_FAILURE; }
strncpy( start->board, argv[1], 10 );
strncpy( end->board, argv[2], 10 );
fprintf( stdout, "Starting with '%s' and trying for '%s'\n",
start->board, end->board );
fprintf( stdout, "start: %p \t end: %p\n", start, end );
solution = walk_solutions( start, end );
print_solution_size( solution );
print_solutions( solution );
return EXIT_SUCCESS;
}
-----------------------------------------------------------------------------
--
http://www.kernel-panic.org/cgi-bin/mailman/listinfo/kplug-lpsg
_________________________________________________________________
Make distant family not so distant with Windows Vista? + Windows Live?.
http://www.microsoft.com/windows/digitallife/keepintouch.mspx?ocid=TXT_TAGLM_CPC_VideoChat_distantfamily_012008
SJS
2008-01-08 15:26:23 UTC
Permalink
Post by Gabriel Sechan
Comments inline. For fun, I'm running this like I would a work code
review- things I would want to see at least defended before allowing
checkin. I'm not looking for better algorithms and I'm not looking
for minor bugs, I'm just doing a style review.
Excellent!
Post by Gabriel Sechan
----------------------------------------
Date: Tue, 8 Jan 2008 02:02:44 -0800
Subject: Code Criticism
#ifndef FALSE
#define FALSE 0
#define TRUE 1
#endif
C99 introduced a bool type, as well as false and true keywords. We
shouldn't be using #defined true false anymore. Even without that,
this should be an enum, not defines.
Assumed language is C89. Not entirely sure I have a C99 compiler on all
of my machines.
Post by Gabriel Sechan
#define ERROR_EMPTY_ARG "Programmer error. Empty argument in %s at %d\n"
#define ERROR_MALLOC_FAIL "Failed to allocate memory. In %s at %d\n"
#define ERROR_BAD_BOARD "Bad board configuration: '%s' in %s at %d\n"
#define ERROR_SWITCH_BROKE "Unknown value in switch: %d in %s at %d\n"
/* change BLANK to use a different 'empty' character. '_' might be good. */
#define BLANK ' '
C99 also introduced const variables, just like C++. These have type
checking, #defines do not. Use them instead.
BLANK should be a variable, but not const. I may want to let the user
change it.

I'm not a fan of 'const' anyway. It generally causes more problems than it
solves for me -- and it's sticky, like statics in Java -- it gets everywhere.
PITA.

Besides, improvements to the error code should involve an error
subsystem, using an array (okay, maybe that can be const) to store
the messages. Plus, that would allow for transparent localization.
Post by Gabriel Sechan
/* The fundamental board structure. We have nine puzzle slots, but
* we want to treat it as a string, so we need space for the terminating
* null. We want to eliminate repeats, so we keep track of the parent,
* which also offers a simple way to print out the final pieces in order.
*/
typedef struct {
char board[10];
void *moves[4];
void *prev;
} configuration;
Bad mistake in using strncmp and strings. This isn't string data.
Use the memcmp, memcpy, etc functions instead. That also means you
only need char[9]. Unless you really only want to check up til the
first null char, which seems a bit... odd
It lets me print out the current state when coding by dropping in fprintfs.
Post by Gabriel Sechan
General comment- couldn't you have found a queue library prewritten?
Maybe. It's doubtful I would have found a *small* library. I might
have been able to grab some "general purpose source code" from
somewhere, but then I'd need to worry about licensing issues, as I
don't have the right to release anyone else's code into the public
domain.

I *could* have extended my own general-purpose library and used that.
Arguably, I should do so anyway.
Post by Gabriel Sechan
/* We need a simple queue of arbitrary size, so we use a singly linked list.
*/
typedef struct {
configuration *data;
void *next;
} dequenode;
/* We push new items to the tail and pull them from the head for fast
* O(1) access.
* TODO - also keep a count of the # of elements in the queue?
*/
typedef struct {
dequenode *head;
dequenode *tail;
} deque;
/* ----------------------------------------------------------------- */
/* make_dequeue
* creates a new queue.
* exits on malloc failure.
*/
deque *make_deque() {
deque *p;
p = malloc( sizeof( deque ) );
if ( p == NULL ) {
fprintf( stderr, ERROR_MALLOC_FAIL, __FILE__, __LINE__ );
exit( EXIT_FAILURE );
}
p->head = NULL;
p->tail = NULL;
}
exiting like that is ok for such a minor program, but its a bad idea
in anything bigger. If you wanted to reuse this code, return NULL on
error instead and let the calling code exit.
Valid point. This data structure is not reusable, however.

Had I done the _right_ thing and added to my generic-data-structure
library, then having support code exit the program would be very bad
style indeed.
Post by Gabriel Sechan
/* deque_insert
* inserts the current node into the queue.
* exits on malloc failure.
*/
void deque_insert( deque *d, configuration *current ) {
dequenode *n, *t;
n = malloc( sizeof( dequenode ) );
if ( n == NULL ) {
fprintf( stderr, ERROR_MALLOC_FAIL, __FILE__, __LINE__ );
exit( EXIT_FAILURE );
}
n->data = current;
if ( d->head == NULL ) {
d->head = n;
} else {
t = d->tail;
t->next = (struct dequenode *)n;
/*d->tail->next = n;*/
}
d->tail = n;
}
Really bad variable names.
Heh. Yup.
Post by Gabriel Sechan
/* deque_remove
* removes the oldest node from the queue.
* do not call if queue is empty.
*/
configuration *deque_remove( deque *d ) {
configuration *p;
dequenode *q;
q = d->head;
p = q->data;
if ( d->head == d->tail ) {
d->head = NULL;
d->tail = NULL;
} else {
d->head = (dequenode *)d->head->next;
}
free( q );
return p;
}
/* deque_empty
* answers if the queue is empty.
*/
int deque_empty( deque *d ) {
return d->head == NULL;
}
/* deque_size
* answers the number of items in the queue.
* warning - very slow. Walks the linked list. See TODO for struct.
*/
int deque_size( deque *d ) {
int count = 0;
dequenode *p = d->head;
dequenode *end = d->tail;
while ( p != end ) { count++; p = p->next; }
return count;
}
If you expect to call size frequently, add a size member to the
structure and increment/decrement it on insert/remove. Walking is
expensive.
Yup. Noted in the TODOs.

Calling size _at all_ towards the middle and end of the run was very slow.
Post by Gabriel Sechan
/* ----------------------------------------------------------------- */
/* got_match
* Answers if the two configurations are equivalent.
* Exits on programmer error.
*/
int got_match( configuration *current, configuration *final ) {
if ( current == NULL ) {
return FALSE;
}
if ( final == NULL ) {
fprintf( stderr, ERROR_EMPTY_ARG, __FILE__, __LINE__ );
/*return FALSE;*/
exit( EXIT_FAILURE );
}
return ! (strncmp( current->board, final->board, 10 ));
}
As previously said- use memcmp.
That adds another parameter to screw up.

On the other hand, memcmp and memcpy would let me use character
sequences instead of just characters, allowing for mnemonic tile names.
Post by Gabriel Sechan
/* got_repeat
* Walks the ancestor list looking for a configuration that is equivalent
* to the current node. This is an optimization step.
*/
int got_repeat( configuration *current ) {
configuration *p;
p = (configuration *)current->prev;
while ( p != NULL ) {
if ( got_match( p, current ) ) return TRUE;
p = (configuration *)p->prev;
}
return FALSE;
}
Why do you have two list mechanisms? Why not use a dequeue inside the configuration?
Because a dequeue holds a configuration.

And this list -- a chain of parent nodes -- cannot and should not
change. We walk it repeatedly, and it encodes our final solution.
Post by Gabriel Sechan
/* new
* Answers a clone of the the provided configuration. A NULL configuration
* will cause an uninitialized configuration to be created.
* TODO - how much of the brute-force initialization can we remove?
*/
configuration *new( configuration *current ) {
configuration *p;
p = malloc( sizeof( configuration ) );
if ( p == NULL ) {
fprintf( stderr, ERROR_MALLOC_FAIL, __FILE__, __LINE__);
exit( EXIT_FAILURE );
}
p->board[0] = '\0';
p->board[1] = '\0';
p->board[2] = '\0';
p->board[3] = '\0';
p->board[4] = '\0';
p->board[5] = '\0';
p->board[6] = '\0';
p->board[7] = '\0';
p->board[8] = '\0';
p->board[9] = '\0';
p->board[10] = '\0';
p->prev = NULL;
p->moves[0] = NULL;
p->moves[1] = NULL;
p->moves[2] = NULL;
p->moves[3] = NULL;
if ( current != NULL ) {
char *a, *b;
p->prev = (struct configuration *)current;
strncpy( p->board, current->board, 10 );
}
return p;
}
Loops to initialize arrays. Don't initialize the board to nulls if
you're just going to overwrite it if current!=NULL (in otherwise, put
it in an else).
Yes, this is cruft leftover from tracking down a bug. It seriously
needs to be yanked out.
Post by Gabriel Sechan
/* swap_tile
* Swaps the board elements at the specified location.
* Assumes arguments are valid and sensible.
*/
void swap_tile( configuration *current, int source, int dest ) {
char temp;
temp = current->board[dest];
current->board[dest] = current->board[source];
current->board[source] = temp;
}
/* make_child
* Creates a unique new child of the current configuration using the
* specified swap of tiles and adding to the specified move slot.
* If the child repeats an ancestor state, it is discarded.
*/
void make_child( configuration *current, int move, int dest, int source ) {
configuration *p;
p = new( current );
swap_tile( p, source, dest );
if ( ! got_repeat( p ) ) {
current->moves[move] = (struct configuration *)p;
} else {
free( p );
}
}
/* fill_children
* Creates all the possible children of the current configuration and
* adds them to the current configuration.
*/
void fill_children( configuration *current ) {
configuration *p;
char temp;
int i;
int blank = -1;
for ( i = 0; i < 9; i++ ) {
if ( current->board[i] == BLANK ) {
blank = i;
break;
}
}
if ( blank < 0 ) {
fprintf( stderr, ERROR_BAD_BOARD, current->board, __FILE__, __LINE__);
return;
}
/*
* 0 | 1 | 2
* -----+-----+-----
* 3 | 4 | 5
* -----+-----+-----
* 6 | 7 | 8
*
*/
switch ( blank ) {
case 0: /* 1->0, 3->0 */
make_child( current, 0, 0, 1 );
make_child( current, 1, 0, 3 );
break;
case 1: /* 0->1, 2->1, 4->1 */
make_child( current, 0, 1, 0 );
make_child( current, 1, 1, 2 );
make_child( current, 2, 1, 4 );
break;
case 2: /* 1->2, 5->2 */
make_child( current, 0, 2, 1 );
make_child( current, 1, 2, 5 );
break;
case 3: /* 0->3, 4->3, 6-> 3 */
make_child( current, 0, 3, 0 );
make_child( current, 1, 3, 4 );
make_child( current, 2, 3, 6 );
break;
case 4: /* 1->4, 3->4, 5->4, 7->4 */
make_child( current, 0, 4, 1 );
make_child( current, 1, 4, 3 );
make_child( current, 2, 4, 5 );
make_child( current, 3, 4, 7 );
break;
case 5: /* 2->5, 4->5, 8->5 */
make_child( current, 0, 5, 2 );
make_child( current, 1, 5, 4 );
make_child( current, 2, 5, 8 );
break;
case 6: /* 3->6, 7->6 */
make_child( current, 0, 6, 3 );
make_child( current, 1, 6, 7 );
break;
case 7: /* 6->7, 4->7, 8->7 */
make_child( current, 0, 7, 4 );
make_child( current, 1, 7, 6 );
make_child( current, 2, 7, 8 );
break;
case 8: /* 5->8, 7->8 */
make_child( current, 0, 8, 5 );
make_child( current, 1, 8, 7 );
break;
fprintf( stderr, ERROR_SWITCH_BROKE, blank, __FILE__, __LINE__ );
}
}
There has got to be a better solution than a giant switch. Plus if
you can do it programatically, it expands to more than 3x3
There are always nine cases, even for more than a 3x3 grid.

Each corner (top left, top right, bottom left, bottom right), the
edges (top, left, right, bottom), and the middle.

The problem with the switch is that it's hard-coded to the 3x3 grid, but
not using a hard-coded lookup table. Worst of both worlds.
Post by Gabriel Sechan
/* walk_solutions
* Breadth-first walk of the solution tree and find the first solution.
*/
configuration *walk_solutions( configuration *initial, configuration *final ) {
configuration *current;
deque *queue;
int i;
queue = make_deque();
deque_insert( queue, initial );
while ( TRUE ) {
current = deque_remove( queue );
if ( got_match( current, final ) ) {
return current; /* leak memory like mad */
}
#ifdef MONITOR_PROGRESS
i = deque_size( queue );
if ( i % 100 == 0 ) {
if ( i < 1000 ) fprintf(stderr, ".");
else if ( i < 10000 ) fprintf(stderr, ":");
else if ( i < 100000 ) fprintf(stderr, "!");
else fprintf(stderr, "#");
}
#endif
fill_children( current );
for ( i = 0; i < 4; i++ ) {
if ( current->moves[i] != NULL ) {
deque_insert( queue, (configuration *)current->moves[i] );
}
}/* for */
}/* while */
}
/* print_solution_size
* Outputs the number of moves it took to solve the problem.
*/
void print_solution_size( configuration *end ) {
configuration *p;
int count;
count = 0;
p = end;
while ( p != NULL ) {
p = (configuration *)p->prev;
count++;
}
fprintf( stdout, "There are %d steps in the solution.\n", count);
}
/* print_solutions
* Print the solution-stack, in reasonable order.
* Recursive.
*/
void print_solutions( configuration *end ) {
if ( end->prev != NULL ) {
print_solutions( (configuration *)end->prev );
}
int row, col;
for ( row = 0; row < 3; row++ ) {
for ( col = 0; col < 3; col++ ) {
fprintf( stdout, " [%c] ", end->board[row * 3 + col] );
}
fprintf( stdout, "\n" );
}
fprintf( stdout, "\n" );
}
/* ----------------------------------------------------------------- */
/* usage
* Outputs how to use the program.
*/
void usage( char **argv ) {
fprintf( stderr, "Usage: %s start end\n", argv[0]);
fprintf( stderr, "\tstart = 9 character board configuration\n");
fprintf( stderr, "\tend = 9 character board configuration\n");
fprintf( stderr, "\t(Note that a blank is REQUIRED!)\n");
/* change this if change definition of BLANK define */
}
/* main
* program entry-point
*/
int main( int argc, char **argv ) {
configuration *start;
configuration *end;
configuration *solution;
if ( argc != 3 ) { usage( argv ); return EXIT_FAILURE; }
start = new( NULL );
end = new( NULL );
if ( strlen( argv[1] ) != 9 ) { usage( argv ); return EXIT_FAILURE; }
if ( strlen( argv[2] ) != 9 ) { usage( argv ); return EXIT_FAILURE; }
strncpy( start->board, argv[1], 10 );
strncpy( end->board, argv[2], 10 );
fprintf( stdout, "Starting with '%s' and trying for '%s'\n",
start->board, end->board );
fprintf( stdout, "start: %p \t end: %p\n", start, end );
solution = walk_solutions( start, end );
print_solution_size( solution );
print_solutions( solution );
return EXIT_SUCCESS;
}
---------------------------------------------------------------------------
There are two memory leaks. Only one of 'em is called out.

I didn't notice the second until I reviewed the code the first time.
--
I need a good C99 book
Then I could really cook!
Stewart Stremler
Christopher Smith
2008-01-08 20:45:27 UTC
Permalink
So, baited me successfully. I decided to give it a go with my own code.
This is more of a dynamic programming approach, and I wanted to use
Boost's Graph library, which wasn't strictly necessary but it let me
flex those otherwise atrophied muscles. The first little bit it spends
just building up the solution tables (if I persisted this information I
could speed startup a fair bit, although it is still pretty darn fast).
The code could definitely use a lot of cleanup (there is at least one
class that is basically screaming to be built), but it works and (given
enough memory) can even solve bigger grids. Here's a sample run:

$ ./solvepuzzle
Vertex size: 1
moves=edges(g)=(0,3)(0,1)(1,4)(1,2)(2,5)(3,6)(3,4)(4,7)(4,5)(5,8)(6,7)(7,8)
Total permutations:362880
Total reachable permutations:181440

Added: 2 new positions that require 1 to solve
Added: 4 new positions that require 2 to solve
Added: 8 new positions that require 3 to solve
Added: 16 new positions that require 4 to solve
Added: 20 new positions that require 5 to solve
Added: 39 new positions that require 6 to solve
Added: 62 new positions that require 7 to solve
Added: 116 new positions that require 8 to solve
Added: 152 new positions that require 9 to solve
Added: 286 new positions that require 10 to solve
Added: 396 new positions that require 11 to solve
Added: 748 new positions that require 12 to solve
Added: 1024 new positions that require 13 to solve
Added: 1893 new positions that require 14 to solve
Added: 2512 new positions that require 15 to solve
Added: 4485 new positions that require 16 to solve
Added: 5638 new positions that require 17 to solve
Added: 9529 new positions that require 18 to solve
Added: 10878 new positions that require 19 to solve
Added: 16993 new positions that require 20 to solve
Added: 17110 new positions that require 21 to solve
Added: 23952 new positions that require 22 to solve
Added: 20224 new positions that require 23 to solve
Added: 24047 new positions that require 24 to solve
Added: 15578 new positions that require 25 to solve
Added: 14560 new positions that require 26 to solve
Added: 6274 new positions that require 27 to solve
Added: 3910 new positions that require 28 to solve
Added: 760 new positions that require 29 to solve
Added: 221 new positions that require 30 to solve
Added: 2 new positions that require 31 to solve
Added: 0 new positions that require 32 to solve
Total positions: 181440
Most moves: 31
Please enter the configuration you'd like to solve, 0 is the space
4 1 2 8 5 3 0 6 7
Board layout: 4 1 2 8 5 3 0 6 7
Move: 3->6
Board layout: 4 1 2 0 5 3 8 6 7
Move: 0->3
Board layout: 0 1 2 4 5 3 8 6 7
Move: 1->0
Board layout: 1 0 2 4 5 3 8 6 7
Move: 2->1
Board layout: 1 2 0 4 5 3 8 6 7
Move: 5->2
Board layout: 1 2 3 4 5 0 8 6 7
Move: 8->5
Board layout: 1 2 3 4 5 7 8 6 0
Move: 7->8
Board layout: 1 2 3 4 5 7 8 0 6
Move: 6->7
Board layout: 1 2 3 4 5 7 0 8 6
Move: 3->6
Board layout: 1 2 3 0 5 7 4 8 6
Move: 4->3
Board layout: 1 2 3 5 0 7 4 8 6
Move: 5->4
Board layout: 1 2 3 5 7 0 4 8 6
Move: 8->5
Board layout: 1 2 3 5 7 6 4 8 0
Move: 7->8
Board layout: 1 2 3 5 7 6 4 0 8
Move: 4->7
Board layout: 1 2 3 5 0 6 4 7 8
Move: 3->4
Board layout: 1 2 3 0 5 6 4 7 8
Move: 6->3
Board layout: 1 2 3 4 5 6 0 7 8
Move: 7->6
Board layout: 1 2 3 4 5 6 7 0 8
Move: 8->7
Board layout: 1 2 3 4 5 6 7 8 0
Solved!!!

--Chris
Christopher Smith
2008-01-08 20:47:02 UTC
Permalink
Sigh... forgot to attach the code. How embarassing.

--Chris
David Brown
2008-01-08 23:01:27 UTC
Permalink
Post by Christopher Smith
Sigh... forgot to attach the code. How embarassing.
It still didn't make it through. The message was broken into two parts,
almost making it look like the mailing list removed the attachment or
something.

Dave
SJS
2008-01-09 01:16:10 UTC
Permalink
Post by David Brown
Post by Christopher Smith
Sigh... forgot to attach the code. How embarassing.
It still didn't make it through. The message was broken into two parts,
almost making it look like the mailing list removed the attachment or
something.
That's expected behavior.

It's code. It works as text. Just include it in the body.

A line of dashes works well as a separator.
--
Perhaps one of the great abominations of our time
Is that annoying extension to email called MIME.
Stewart Stremler
Christopher Smith
2008-01-09 09:48:13 UTC
Permalink
Post by SJS
Post by David Brown
Post by Christopher Smith
Sigh... forgot to attach the code. How embarassing.
It still didn't make it through. The message was broken into two parts,
almost making it look like the mailing list removed the attachment or
something.
That's expected behavior.
It's code. It works as text. Just include it in the body.
A line of dashes works well as a separator.
You mean like what happens automatically when you use MIME attachments? ;-)

In fairness, this is not the only list I use that has this feature, and
sometimes it is warranted, but this is a group where people explicitly
are supposed to share code. While you can encode snippets just fine
inline (arguably for small bits of code it is even more convenient), it
is kind of a mess to do that when multiple files are involved.

Sure, I could just copy and past from multiple files in to a single
message, put in dashes to separate files, and somehow encode file names
and any relevant permissions and such at the beginning of each file.
Then anyone who wanted to actually work with the code would then
essentially do the reverse of what I'd done to reconstitute the
structure of the work.

....or we could use standardized formats for doing such things. Then a
computer could automate the work in a fast and error free fashion. Your
mail client would understand the structure and perhaps choose not to
download the code at all. The only real downside of this is that some
old mail clients, all of which run on non-Linux platforms, have security
flaws in them that can be exploited through attachments without the
person reading the mail having a chance to avoid downloading the attachment.

What are the real odds here that someone reading this list is running
one of these old, unpatched clients with no anti-virus (or really old
anti-virus I guess) protecting them?

If we really think there is a risk, could we perhaps compromise by
having the kplug mailserver filter stuff through ClamAV instead of
throwing out the baby with the bath water?

- --Chris
Gus Wirth
2008-01-09 10:01:37 UTC
Permalink
Post by Christopher Smith
Post by SJS
Post by David Brown
Post by Christopher Smith
Sigh... forgot to attach the code. How embarassing.
It still didn't make it through. The message was broken into two parts,
almost making it look like the mailing list removed the attachment or
something.
That's expected behavior.
It's code. It works as text. Just include it in the body.
A line of dashes works well as a separator.
You mean like what happens automatically when you use MIME attachments? ;-)
In fairness, this is not the only list I use that has this feature, and
sometimes it is warranted, but this is a group where people explicitly
are supposed to share code. While you can encode snippets just fine
inline (arguably for small bits of code it is even more convenient), it
is kind of a mess to do that when multiple files are involved.
Sure, I could just copy and past from multiple files in to a single
message, put in dashes to separate files, and somehow encode file names
and any relevant permissions and such at the beginning of each file.
Then anyone who wanted to actually work with the code would then
essentially do the reverse of what I'd done to reconstitute the
structure of the work.
....or we could use standardized formats for doing such things. Then a
computer could automate the work in a fast and error free fashion. Your
mail client would understand the structure and perhaps choose not to
download the code at all. The only real downside of this is that some
old mail clients, all of which run on non-Linux platforms, have security
flaws in them that can be exploited through attachments without the
person reading the mail having a chance to avoid downloading the attachment.
What are the real odds here that someone reading this list is running
one of these old, unpatched clients with no anti-virus (or really old
anti-virus I guess) protecting them?
If we really think there is a risk, could we perhaps compromise by
having the kplug mailserver filter stuff through ClamAV instead of
throwing out the baby with the bath water?
Given the plethora of options available for posting files for download,
there is no need to support attachments to the mailing list. The
decision to ban attachments was made a long time ago by the Steering
Committee (of which I am a member) and still stands. We do not need to
revisit this argument.

Gus
Christopher Smith
2008-01-09 10:33:12 UTC
Permalink
Post by Gus Wirth
Given the plethora of options available for posting files for
download, there is no need to support attachments to the mailing list.
The decision to ban attachments was made a long time ago by the
Steering Committee (of which I am a member) and still stands. We do
not need to revisit this argument.
My hope was that the folks involved would recognize that with the
passage of time, the context for said decision had changed. Tracy
recently mentioned that he wished more people would post code to the
list.... well, making it easier (and yes, that includes providing more
ways to accomplish the same thing, particularly the ones that are most
established and standardized for e-mail) might help.

--Chris
John H. Robinson, IV
2008-01-09 10:47:07 UTC
Permalink
Post by Gus Wirth
Given the plethora of options available for posting files for download,
there is no need to support attachments to the mailing list. The
decision to ban attachments was made a long time ago by the Steering
Committee (of which I am a member) and still stands. We do not need to
revisit this argument.
WHy not? It was a poor decision then, and it remains a poor policy now.

Nothing wrong with text/plain attachments.

-john
Neil Schneider
2008-01-09 12:12:20 UTC
Permalink
Post by John H. Robinson, IV
Post by Gus Wirth
Given the plethora of options available for posting files for download,
there is no need to support attachments to the mailing list. The
decision to ban attachments was made a long time ago by the Steering
Committee (of which I am a member) and still stands. We do not need to
revisit this argument.
WHy not? It was a poor decision then, and it remains a poor policy now.
Nothing wrong with text/plain attachments.
Why is it a bad decision? It was done to keep bandwidth at a miminum. Someone
sending a 1Mb image attachment to the list consumes 1Mb*n bandwidth, where n
is the number of subscribers. Our bandwidth is donated and it is courtesy to
reduce the amount of bandwidth through policies that we can enforce. Source
code is plain text and as such fits fine inside of the body of email.

"Nothing wrong with text/plain attachments" except that AFAIK the options are
allow attachment or don't allow attachments. There is no option to allow plain
text attachments, don't allow jpeg attachments.

The decision stands, live with it.
--
Neil Schneider pacneil_at_linuxgeek_dot_net
http://www.paccomp.com
Key fingerprint = 67F0 E493 FCC0 0A8C 769B 8209 32D7 1DB1 8460 C47D

I help busy professionals diversify their self-directed IRAs and portfolios
with real estate they don't have to manage. Please let me know if you or
someone you know would like more information.
John H. Robinson, IV
2008-01-09 12:56:06 UTC
Permalink
Post by Neil Schneider
Post by John H. Robinson, IV
Nothing wrong with text/plain attachments.
Why is it a bad decision? It was done to keep bandwidth at a miminum.
Size limits are okay.
Post by Neil Schneider
"Nothing wrong with text/plain attachments" except that AFAIK the options are
allow attachment or don't allow attachments. There is no option to allow plain
text attachments, don't allow jpeg attachments.
I no longer do the admin of the lists, so I don't know. I would think
that MailMan could be configured to whitelist certain attachments, and
strip others. If not, I am positive Postfix can.
Post by Neil Schneider
The decision stands, live with it.
I found this to be *exceedingly* rude and _completely_ uncalled for.

-john
Tracy R Reed
2008-01-09 13:14:49 UTC
Permalink
Post by John H. Robinson, IV
Post by Neil Schneider
The decision stands, live with it.
I found this to be *exceedingly* rude and _completely_ uncalled for.
I don't think it was rude or uncalled for. We can't spend all day
bickering about issues which were settled ages ago. Lighten up.
Chuck Esterbrook
2008-01-09 13:49:14 UTC
Permalink
Post by Tracy R Reed
Post by John H. Robinson, IV
Post by Neil Schneider
The decision stands, live with it.
I found this to be *exceedingly* rude and _completely_ uncalled for.
I don't think it was rude or uncalled for. We can't spend all day
bickering about issues which were settled ages ago. Lighten up.
"Lighten up" could also be a valid response to "The decision stands,
live with it"

In other lists when I've brought up a "settled ages ago" issue, people
kindly pointed me to the previous thread from ages ago. On this list,
the response includes phrases like "live with it" and "spend all day
bickering".

"How nice."

-Chuck
SJS
2008-01-09 13:52:59 UTC
Permalink
Post by John H. Robinson, IV
Post by Neil Schneider
Post by John H. Robinson, IV
Nothing wrong with text/plain attachments.
Why is it a bad decision? It was done to keep bandwidth at a miminum.
Size limits are okay.
I propose 256 bytes.

Doubling that might be okay.

[snip]
Post by John H. Robinson, IV
Post by Neil Schneider
The decision stands, live with it.
I found this to be *exceedingly* rude and _completely_ uncalled for.
Perhaps it should be "Take policy discussions to -steer" ?

Now, working out the scripts needed to do the checking of such things
is an appropriate topic for -lpsg. And it might be amusing, even if
we never implement it for the list itself.
--
I see an immense need for kplug-test
But I guess I should give it a rest.
Stewart Stremler
Christopher Smith
2008-01-09 15:21:49 UTC
Permalink
Post by John H. Robinson, IV
Post by Neil Schneider
The decision stands, live with it.
I found this to be *exceedingly* rude and _completely_ uncalled for.
Meh. I dunnoh. Given that it was in response to: "Why not? It was a poor
decision then, and it remains a poor policy now.".... it doesn't seem at
all out of place.

In general though, such strong language should probably be kept to
discussions about C++, indenting, OOP, and Forth. ;-)

--Chris
Brad Beyenhof
2008-01-09 15:37:40 UTC
Permalink
Post by John H. Robinson, IV
Post by Neil Schneider
"Nothing wrong with text/plain attachments" except that AFAIK the options are
allow attachment or don't allow attachments. There is no option to allow plain
text attachments, don't allow jpeg attachments.
I no longer do the admin of the lists, so I don't know. I would think
that MailMan could be configured to whitelist certain attachments, and
strip others. If not, I am positive Postfix can.
I know for a fact (from adminning a mailman list) that specific MIME
types can be explicitly allowed if you have otherwise disallowed
attachments.

Not that I think they *should* be, as many people have pointed out the
myriad of other options for sharing code. If you don't have a
~/public_html somewhere, it shouldn't be too hard to find one (either
on your own box or somebody else's).
--
Brad Beyenhof
http://augmentedfourth.com
Silence will save me from being wrong (and foolish), but it will also
deprive me of the possibility of being right.
~ Igor Stravinsky
Neil Schneider
2008-01-09 17:00:29 UTC
Permalink
Post by Brad Beyenhof
Post by John H. Robinson, IV
Post by Neil Schneider
"Nothing wrong with text/plain attachments" except that AFAIK the options
are
Post by Neil Schneider
allow attachment or don't allow attachments. There is no option to allow
plain
Post by Neil Schneider
text attachments, don't allow jpeg attachments.
I no longer do the admin of the lists, so I don't know. I would think
that MailMan could be configured to whitelist certain attachments, and
strip others. If not, I am positive Postfix can.
I know for a fact (from adminning a mailman list) that specific MIME
types can be explicitly allowed if you have otherwise disallowed
attachments.
Not that I think they *should* be, as many people have pointed out the
myriad of other options for sharing code. If you don't have a
~/public_html somewhere, it shouldn't be too hard to find one (either
on your own box or somebody else's).
I checked the configuration for this list. The following mime types are
allowed. I didn't change this configuration is was already set. So if you
can't send code as an attachment then you are not mime encoding it right. I
think it should be coded as text/plain.

multipart/mixed
multipart/alternative
multipart/signed
text/plain
application/pgp-signature
message/rfc822
--
Neil Schneider pacneil_at_linuxgeek_dot_net
http://www.paccomp.com
Key fingerprint = 67F0 E493 FCC0 0A8C 769B 8209 32D7 1DB1 8460 C47D

I help busy professionals diversify their self-directed IRAs and portfolios
with real estate they don't have to manage. Please let me know if you or
someone you know would like more information.
Christopher Smith
2008-01-09 18:14:45 UTC
Permalink
Post by Neil Schneider
I checked the configuration for this list. The following mime types are
allowed. I didn't change this configuration is was already set. So if you
can't send code as an attachment then you are not mime encoding it right. I
think it should be coded as text/plain.
multipart/mixed
multipart/alternative
multipart/signed
text/plain
application/pgp-signature
message/rfc822
That was the crucial bit I was missing. Mine was compressed (an attempt
to shrink it down smaller, ironically), so it was sent as
"application/x-bzip".

Well thanks. At least I know how to send it through now.

--Chris
Andrew Lentvorski
2008-01-09 21:43:04 UTC
Permalink
Post by John H. Robinson, IV
Post by Neil Schneider
The decision stands, live with it.
I found this to be *exceedingly* rude and _completely_ uncalled for.
-john
WHy not? It was a poor decision then, and it remains a poor policy now.
Nothing wrong with text/plain attachments.
-john
First, you dismissed a policy which was well-considered with nothing
more than your opinion.

Second, you didn't even check, and it turned out that text/plain was
*not* disabled.

I would have been quite a bit ruder than Neil, and I would have felt
quite justified, thank you very much.

-a
Gregory K. Ruiz-Ade
2008-01-09 12:57:17 UTC
Permalink
Post by Neil Schneider
"Nothing wrong with text/plain attachments" except that AFAIK the options are
allow attachment or don't allow attachments. There is no option to allow plain
text attachments, don't allow jpeg attachments.
This is not entirely true, as the lists seem to allow OpenPGP
attachements (PGP/MIME detached signatures) perfectly fine. See also
Tracy's mail and my mail (with varying frequency.)

Gregory
--
Gregory K. Ruiz-Ade <***@unnerving.org>
OpenPGP Key ID: EAF4844B keyserver: pgpkeys.mit.edu


-------------- next part --------------
A non-text attachment was scrubbed...
Name: PGP.sig
Type: application/pgp-signature
Size: 186 bytes
Desc: This is a digitally signed message part
Url : http://www.kernel-panic.org/pipermail/kplug-lpsg/attachments/20080109/8a0379a1/PGP.pgp
Christopher Smith
2008-01-09 15:19:11 UTC
Permalink
Post by Neil Schneider
Why is it a bad decision? It was done to keep bandwidth at a miminum. Someone
sending a 1Mb image attachment to the list consumes 1Mb*n bandwidth, where n
is the number of subscribers. Our bandwidth is donated and it is courtesy to
reduce the amount of bandwidth through policies that we can enforce. Source
code is plain text and as such fits fine inside of the body of email.
I know for sure that Mailman has a "maximum message size" setting (as
does postfix/sendmail/qmail, for that matter). If managing bandwidth is
the concern.... isn't it more logical to manage it through that, rather
than through some kind of proxy, like attachments?

--Chris
SJS
2008-01-09 10:10:02 UTC
Permalink
[snip]
Post by Christopher Smith
Post by SJS
It's code. It works as text. Just include it in the body.
A line of dashes works well as a separator.
You mean like what happens automatically when you use MIME attachments? ;-)
Heh.

MIME does a lot more than a line of dashes.
Post by Christopher Smith
In fairness, this is not the only list I use that has this feature, and
sometimes it is warranted, but this is a group where people explicitly
are supposed to share code. While you can encode snippets just fine
inline (arguably for small bits of code it is even more convenient), it
is kind of a mess to do that when multiple files are involved.
That's what URLs are for.
Post by Christopher Smith
Sure, I could just copy and past from multiple files in to a single
:!r filename

(Or equivalent for your editor...)
Post by Christopher Smith
message, put in dashes to separate files, and somehow encode file names
and any relevant permissions and such at the beginning of each file.
Permissions aren't generally needed, unless you're playing games with
them; at that point, you're probably better off with "ls -l" in the
appropriate directory.
Post by Christopher Smith
Then anyone who wanted to actually work with the code would then
essentially do the reverse of what I'd done to reconstitute the
structure of the work.
Yup.

Plus, if someone wanted to comment on aspects of your layout and
design, it's right there, ready to be quoted.

(I was tempted to run the code thru 'nl' first, to aid in discussion.)
Post by Christopher Smith
....or we could use standardized formats for doing such things. Then a
computer could automate the work in a fast and error free fashion. Your
mail client would understand the structure and perhaps choose not to
download the code at all. The only real downside of this is that some
old mail clients, all of which run on non-Linux platforms, have security
flaws in them that can be exploited through attachments without the
person reading the mail having a chance to avoid downloading the attachment.
Or if it's really that complicated, you can provide a URL, and leave
the mailing list for discussion, and leave bulk file transfer out of
the discussion list.

What are the real odds here that someone reading this list is lacking
access to a web-server on which to put code archives?
Post by Christopher Smith
What are the real odds here that someone reading this list is running
one of these old, unpatched clients with no anti-virus (or really old
anti-virus I guess) protecting them?
At least one of us is using hotmail.
Post by Christopher Smith
If we really think there is a risk, could we perhaps compromise by
having the kplug mailserver filter stuff through ClamAV instead of
I am unimpressed with ClamAV thus far. Can't see *relying* on it for
much of anything.
Post by Christopher Smith
throwing out the baby with the bath water?
Perhaps not trying to bathe the baby in the soup would be a better start.
--
And they all sat around the pot, peering at the baby soup
Muttering under their breath: "It's just murky goop!"
Stewart Stremler
Christopher Smith
2008-01-09 10:28:33 UTC
Permalink
Post by Brad Beyenhof
[snip]
Post by Christopher Smith
Post by SJS
It's code. It works as text. Just include it in the body.
A line of dashes works well as a separator.
You mean like what happens automatically when you use MIME attachments? ;-)
Heh.
MIME does a lot more than a line of dashes.
For inline text it doesn't do much more.
Post by Brad Beyenhof
Post by Christopher Smith
In fairness, this is not the only list I use that has this feature, and
sometimes it is warranted, but this is a group where people explicitly
are supposed to share code. While you can encode snippets just fine
inline (arguably for small bits of code it is even more convenient), it
is kind of a mess to do that when multiple files are involved.
That's what URLs are for.
You mean like imaps://..... ? ;-)
Post by Brad Beyenhof
Post by Christopher Smith
message, put in dashes to separate files, and somehow encode file names
and any relevant permissions and such at the beginning of each file.
Permissions aren't generally needed, unless you're playing games with
them; at that point, you're probably better off with "ls -l" in the
appropriate directory.
Well, if you have shell scripts they are nice to have, but still, I
agree permissions aren't that important (and not actually encoded by
MIME, but they are by tar, which is the traditional tool for aggregating
a group of files).
Post by Brad Beyenhof
Plus, if someone wanted to comment on aspects of your layout and
design, it's right there, ready to be quoted.
Wait, your editor doesn't do mail?! ;-)
Post by Brad Beyenhof
Post by Christopher Smith
....or we could use standardized formats for doing such things. Then a
computer could automate the work in a fast and error free fashion. Your
mail client would understand the structure and perhaps choose not to
download the code at all. The only real downside of this is that some
old mail clients, all of which run on non-Linux platforms, have security
flaws in them that can be exploited through attachments without the
person reading the mail having a chance to avoid downloading the attachment.
Or if it's really that complicated, you can provide a URL, and leave
the mailing list for discussion, and leave bulk file transfer out of
the discussion list.
Yes, that is what I ended up doing, and it has its own advantages and
disadvantages.

I challenge the implied notion that allowing attachments suddenly allows
"bulk file transfer" out of the discussion list. My code was smaller
than your original posting, and because I was doing an attachment I took
the trouble to compress it (and as you can image it's compression ratio
was such that even with @#$$#@ base64 encoding this resulted in a
significant net win). Indeed, your original suggestion to me was to post
the code inline.

So, yes, using URL's would keep the file transfer off the discussion
list. Instead we'd be transferring URL's back and forth which would add
nothing to the discussion, while simultaneously remove what was being
discussed.
Post by Brad Beyenhof
What are the real odds here that someone reading this list is lacking
access to a web-server on which to put code archives?
I would argue that they are greater than someone being vulnerable to an
attachment exploit (which presumably was the motivation for this).
Post by Brad Beyenhof
Post by Christopher Smith
What are the real odds here that someone reading this list is running
one of these old, unpatched clients with no anti-virus (or really old
anti-virus I guess) protecting them?
At least one of us is using hotmail.
Hotmail is actually very well secured against attachments these days,
although still somewhat vulnerable to inline Javascript (we could start
stripping that I guess, but then it'd be even harder to share Javascript
code samples ;-), it's biggest exposure is actually from.... URL's
posted in messages. ;-)

--Chris
Gregory K. Ruiz-Ade
2008-01-09 12:07:52 UTC
Permalink
Post by Christopher Smith
In fairness, this is not the only list I use that has this feature, and
sometimes it is warranted, but this is a group where people explicitly
are supposed to share code. While you can encode snippets just fine
inline (arguably for small bits of code it is even more convenient), it
is kind of a mess to do that when multiple files are involved.
There's always things like pastebin.com.

Gregory
--
Gregory K. Ruiz-Ade <***@unnerving.org>
OpenPGP Key ID: EAF4844B keyserver: pgpkeys.mit.edu
Continue reading on narkive:
Loading...