A bit of fun. A programming puzzle to be done in C.

R

Rick Dearman

A_________B
|\ \
| \ |\
| \ | \
| C\________\D
| | | |
| | | |
|___|_____| |
E\ | H\ |
\ | \|
\|________|
F G


Given the above cube, write a program that will start at the point A
on the cube and traverse each leg of the cube without going back over
a leg more than once. Then print the path to standard output in the
form of:

A->C
C->D
D->G
....


Hope nobody minds me posing a little puzzle for the great unwashed
(and washed too for that matter)

:)

Rick
 
K

Keith Thompson

Rick Dearman said:
A_________B
|\ \
| \ |\
| \ | \
| C\________\D
| | | |
| | | |
|___|_____| |
E\ | H\ |
\ | \|
\|________|
F G


Given the above cube, write a program that will start at the point A
on the cube and traverse each leg of the cube without going back over
a leg more than once.
[snip]

(Please avoid tab characters.)

Not possible. There are three edges leading to vertex A. A traversal
can pass through A once, but it must also either start or end at A.
The same applies to all 8 vertices. Since a traversal can only start
at one vertex and end at one vertex (either the same one or a
different one), a full traversal is possible only if at most two
vertices connect to an odd number of edges. See the Konigsberg Bridge
Problem.

If a full traversal were possible (as it is on a 4-dimensional
hypercube, or more generally any hypercube with an even number of
dimensions), the simplest way to print it in a C program would be to
print the string literals representing the path. If you want a more
general solution, you'll have to restate the problem.
 
R

Richard

Keith Thompson said:
Rick Dearman said:
A_________B
|\ \
| \ |\
| \ | \
| C\________\D
| | | |
| | | |
|___|_____| |
E\ | H\ |
\ | \|
\|________|
F G


Given the above cube, write a program that will start at the point A
on the cube and traverse each leg of the cube without going back over
a leg more than once.
[snip]

(Please avoid tab characters.)

Not possible. There are three edges leading to vertex A. A traversal

Of course it's possible.

He said "leg". Not edge.

A-E-F-C-D-G-H-B

Done.
 
B

Bartc

Rick Dearman said:
A_________B
|\ \
| \ |\
| \ | \
| C\________\D
| | | |
| | | |
|___|_____| |
E\ | H\ |
\ | \|
\|________|
F G


Given the above cube, write a program that will start at the point A
on the cube and traverse each leg of the cube without going back over
a leg more than once. Then print the path to standard output in the
form of:

A->C
C->D
D->G
...

Your rules are unclear. Are you saying I can traverse AB then later BA, but
not AB then AB again?

Assuming I can do AB and AB, my 'program' came up with this (hijacking
Richard's cube because that's what I used but it seems to be a little
different from yours):

a---------b
|\ /|
| e-----f |
| | | |
| g-----h |
|/ \|
c---------d

A->B
B->D
D->C
C->A
A->E
E->F
F->B
B->D
D->H
H->F
F->H
H->G
G->E
E->G
G->C

And optionally C->A to end up at the start point.
 
K

Keith Thompson

Richard Heathfield said:
Keith Thompson said: [...]
There are three edges leading to vertex A. A
traversal can pass through A once, but it must also either start
or end at A.

I think you missed the significance of the phrase "without BACK over
a leg more than once".

I didn't read carefully enough; I thought the problem was to avoid
visiting any vertex more than once.

Never mind.
 
E

Eric Sosman

Rick said:
[...]
Given the above cube, write a program that will start at the point A
on the cube and traverse each leg of the cube without going back over
a leg more than once. [...]

If you succeed, be sure to gloat at your triumph over
Leonhard Euler. And stay away from Königsberg, where the
locals may hold a grudge against you.
 
E

Eric Sosman

Eric said:
Rick said:
[...]
Given the above cube, write a program that will start at the point A
on the cube and traverse each leg of the cube without going back over
a leg more than once. [...]

If you succeed, be sure to gloat at your triumph over
Leonhard Euler. And stay away from Königsberg, where the
locals may hold a grudge against you.

Oh, damn. Never mind; reading speed greater than
comprehension speed. Again.
 
C

CBFalconer

Keith said:
Rick Dearman said:
A_________B
|\ \
| \ |\
| \ | \
| C\________\D
| | | |
| | | |
|___|_____| |
E\ | H\ |
\ | \|
\|________|
F G


Given the above cube, write a program that will start at the point
A on the cube and traverse each leg of the cube without going back
over a leg more than once.
[snip]

(Please avoid tab characters.)

Not possible. There are three edges leading to vertex A. A traversal

As stated, there is no problem. We only need to go back over legs
once. To make it impossible he needed to specify "never going back
over a leg".
 
R

Richard

CBFalconer said:
Keith said:
Rick Dearman said:
A_________B
|\ \
| \ |\
| \ | \
| C\________\D
| | | |
| | | |
|___|_____| |
E\ | H\ |
\ | \|
\|________|
F G


Given the above cube, write a program that will start at the point
A on the cube and traverse each leg of the cube without going back
over a leg more than once.
[snip]

(Please avoid tab characters.)

Not possible. There are three edges leading to vertex A. A traversal

As stated, there is no problem. We only need to go back over legs
once. To make it impossible he needed to specify "never going back
over a leg".

Off Topic. Can't talk about it here. Blah Blah Blah. It seems once again
you break your own rules. Take it to comp.programming ....
 
R

Rick Dearman

LOL.

All good replies, but I wanted to see your C code! And yes Richard I
am very familar with the thread back in the dark ages when I was a
regular comp.lang.c poster.

It is a good puzzle to get people to use regression in their
programming.

If we don't have any C code to look at it isn't really topical.

Rick
 
J

James Kuyper

Rick said:
LOL.

All good replies, but I wanted to see your C code!

You specified the problem poorly enough that your challenge can be met
by code which does nothing but call printf() to print out the answer.
The simplest way to force the use of non-trivial code would be to
require the program to produce correct answers for a large set of
closely related problems, with the particular problem to be solved being
determined by the inputs to the program.

....
If we don't have any C code to look at it isn't really topical.

That I can agree with.
 
R

Rick Dearman

Jeez! Has anyone noticed that in all the replies not one person
bothered to attempt to complete the puzzle only to spend their time
being critical of the "specification".

Fair enough. It would seem that there are no longer any programmers
here in comp.lang.c only a bunch of pedantic nit-pickers, more
concerned with telling people to go to another newsgroup for the
answer to the problem.

I would have been happy just to see the "printf" only solution
mentioned, at least that would have mean someone actually attempted it
and compiled it.

This problem can be solved using only ANSI C and you don't even have
to have a C99 compliant compiler to do it.

So lets see some C!!

Here is my "printf" only solution. How about a recursive solution? Or
anything? I think my answer might be wrong. Perhaps someone else has a
more elegant solution?

#include <stdio.h>

int main ()
{
char *answer = "A->B->C->D->E->F->G->H->A";
printf("%s",answer);
return 0;
}
 
B

Bartc

Rick Dearman said:
Jeez! Has anyone noticed that in all the replies not one person
bothered to attempt to complete the puzzle only to spend their time
being critical of the "specification".

Fair enough. It would seem that there are no longer any programmers
here in comp.lang.c only a bunch of pedantic nit-pickers, more
concerned with telling people to go to another newsgroup for the
answer to the problem.

I would have been happy just to see the "printf" only solution
mentioned, at least that would have mean someone actually attempted it
and compiled it.

This problem can be solved using only ANSI C and you don't even have
to have a C99 compliant compiler to do it.

So lets see some C!!

My effort uses totally random attempts until it finds a solution by
accident. So it may not complete on your machine.

By redefining nedges and edges variables, I think you can define any sort of
network, but I haven't tried it.

Arrays here tend to be 1-based.


/* Solve cube puzzle */
#include <stdio.h>
#include <stdlib.h>

void movenext(void);
int finished(void);

#define nedges 12
char edges[nedges+1][2] ={{0,0},{'A','B'},{'B','C'},{'C','D'},{'D','A'},
{'E','F'},{'F','G'},{'G','H'},{'H','E'},
{'A','F'},{'B','G'},{'C','H'},{'D','E'}};

char cv; /* current vertex, eg. 'A' */
char cvhistory[1000];
int ncv; /* number of vertices in cvhistory */
char visited[nedges+1]; /* Number of visits along each edge */


int main (void) {
int i,j,k;

restart:
while (1) { /* Start new traversal */

cv='A'; /* Always start at A */

cvhistory[1]=cv; /* Reset vertex history */
ncv=1;
for (i=1; i<=nedges; ++i) /* Reset visited flags */
visited=0;

while (1) { /* Start traversing edges */
movenext(); /* Step CV to new vertex */

j=finished();
if (j==1) exit(0); /* Finished */
if (j==2) goto restart; /* Error so start again. Can prob avoid
using goto but not at 2am... */

} /* End inner while */
} /* End outer while */

}

int finished(void) {
/* Return:
0: not yet finished (some edges not visited)
1: finished: path used is displayed here
2: error: one edge traversed too many times
*/
int i;

for (i=1; i<=nedges; ++i) {
if (!visited) return 0; /* Edge not visited */
if (visited>2) return 2; /* Error */
}

/* Finished, so show path */

puts("Solved:");
for (i=1; i<ncv; ++i) {
printf(" %c -> %c\n",cvhistory,cvhistory[i+1]);
}
return 1;
}

void movenext(void) {
/* Work out where to go next from vertex cv */

int i,j,n,r;

n=0; /* Count edges that involve cv */

for (i=1; i<=nedges; ++i) {
if (cv==edges[0] || cv==edges[1])
++n;
}

/* Get a vaguely random number 1..n */

r=(rand()%n)+1;

/* Now choose the r'th edge that involves cv */
i=1;
j=0;

while (1) {
if (cv==edges[0] || cv==edges[1]) {
++j;
if (j==r) { /* Use this edge */
if (cv==edges[0]) /* Use opposite vertex */
cv=edges[1];
else
cv=edges[0];
cvhistory[++ncv]=cv; /* Remember new vertex */
++visited; /* And this visit to edge */
return;
}
}
++i;
if (i>nedges) i=1; /* Wrap (may be needed when r too high?) */
}

}
 
J

James Kuyper

Rick said:
Jeez! Has anyone noticed that in all the replies not one person
bothered to attempt to complete the puzzle only to spend their time
being critical of the "specification".

I'm not that interested in the puzzle, and am worried about the
possibility that it's a homework assignment.
I would have been happy just to see the "printf" only solution
mentioned, at least that would have mean someone actually attempted it
and compiled it.

I considered it doing so, but lost interest when I noticed "without
going back over a leg more than once." The "more than once" clause
changed it from an impossible problem (with some interesting history
behind the proof that it's impossible), to a problem so easily solved
that it's not interesting to solve it.
Here is my "printf" only solution. How about a recursive solution? Or
anything? I think my answer might be wrong. Perhaps someone else has a
more elegant solution?

#include <stdio.h>

int main ()
{
char *answer = "A->B->C->D->E->F->G->H->A";
printf("%s",answer);
return 0;
}

If the move from B->C is allowed, the problem is even easier to solve
than I thought.
 
G

Guest

James Kuyper said:


It isn't. Rick Dearman may (or may not!) be many things, but he's no
spring chicken. I guarantee it. I'm afraid his homework days are
perhaps rather farther behind him than he'd care to remember!

No, I don't know Rick Dearman personally, but he and a third party
had business dealings in which I very nearly got involved. I
probably should say no more than that, since it's really his
business, not mine - but, even though I am no betting man, I would
not hesitate to give you 100-1 against this being his homework
assignment.

I'd always taken "homework" to mean any problem that is solved
for pedagogical purposes rather than for the utility of the
problem. I'd never taken "homework" on clc to only mean "problems
set as part of a formal instruction program". By my definition
we all do homework from time to time no matter how autumnal fowl
we may be.

I can't believe anyone *really* needs to solve this rather odd
cube traversal (the vertices seem rather oddly labelled).
 
R

Richard

I'd always taken "homework" to mean any problem that is solved
for pedagogical purposes rather than for the utility of the
problem. I'd never taken "homework" on clc to only mean "problems
set as part of a formal instruction program". By my definition
we all do homework from time to time no matter how autumnal fowl
we may be.

Wow. You've taken to talking like Heathfield. I ad to read that 3
times. "Homework" has one widely understood meaning and you know it. It
means tasks given to a student to complete as part of a course.
I can't believe anyone *really* needs to solve this rather odd
cube traversal (the vertices seem rather oddly labelled).

No one *really* needs to do anything. It was a puzzle he would like to
see "solved" in C. Nothing more. Nothing less.
 
A

Antoninus Twink

It would seem that there are no longer any programmers here in
comp.lang.c only a bunch of pedantic nit-pickers, more concerned with
telling people to go to another newsgroup for the answer to the
problem.

Sad to say, you've got the measure of this group exactly right.

However, it's not universal - there are still a few people here who try
to give useful answers. A good rule of thumb: if you ever see a post
from CBF saying "X is a pure troll, best *plonked*", that's a good
indication that X posts correct answers to technical questions about
real-world C.
 
G

Guest

Wow. You've taken to talking like Heathfield.

it's unlike you to be so nice to people!

I ad to read that 3
times. "Homework" has one widely understood meaning and you know it.

well, as I outlined above, no

It
means tasks given to a student to complete as part of a course.




No one *really* needs to do anything.

some people get paid to write software. In a sense they have problems
they "need" to solve.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,744
Messages
2,569,482
Members
44,901
Latest member
Noble71S45

Latest Threads

Top