rq02+@andrew.cmu.edu (Richard Quadrel) (03/04/91)
Not that I don't have better things to do, but... For anyone who's stuck with 3 in Three, the puzzle "Outside In", you will be horrified to learn that there are 479,001,600 possible combinations of button presses that can be attempted to close the "security doors." Below is a program that will generate all of these combinations and print feasible solutions (i.e., combinations that successfully close all of the doors) to a file called "solutions." OK, so I'm nerd. The good news is that there appear to be many thousands of combinations that work. The bad news is that with 12 levels of recursion, this program takes about 48 hours to run to completion on a Sun3/60. So, for whatever its worth... If you can't wait that long, send me some mail, and I'll be happy to tell you a combination that does work. If you have any comments about the code, especially how to make it faster, I'd be happy to hear that too. Have fun! Rich Quadrel rquadrel@cs.cmu.edu
rq02+@andrew.cmu.edu (Richard Quadrel) (03/04/91)
#include <stdio.h>
#include <time.h>
/*-------------------------------------------------------------------*
state of the 24 "security doors," which are numbered from 0 to 23
starting at the upper left corner and going across
*-------------------------------------------------------------------*/
int state[24];
FILE* fp;
void wig();
int *shiftx();
void display();
void test();
void alterstate();
void main()
{
/*-------------------------------------------------------------------*
array x is the array with the values of the available "buttons"
*-------------------------------------------------------------------*/
int x[12];
x[0]=7; x[1]=8; x[2]=9; x[3]=10;
x[4]=13; x[5]=14; x[6]=15; x[7]=16;
x[8]=19; x[9]=20; x[10]=21; x[11]=22;
fp = fopen("solutions", "w");
fprintf(fp, "%d\n", time(0));
fflush(fp);
wig(12,x);
fclose(fp);
}
/*-------------------------------------------------------------------*
wig is a recursive function that generates all possible orderings
of a sequence of numbers. Why "wig?"... well when it worked, it
flipped mine.
*-------------------------------------------------------------------*/
void wig(int col, int *x)
{
int i;
int *save;
for (i=0; i<col; i++) {
save = shiftx(col, x, i);
if (col==2) test(save);
else wig(col-1, save);
}
}
/*-------------------------------------------------------------------*
shiftx "cycles" a subset of cells in the array. "col" defines
what the subset is, "shift" determines how many positions the
array should be cycled.
*-------------------------------------------------------------------*/
int *shiftx(int col, int *x, int shift)
{
int i,j,temp;
for (i=0; i<shift; i++) {
temp=x[0];
for (j=1; j<col; j++) x[j-1] =x[j];
x[col-1]=temp;
}
return x;
}
/*-------------------------------------------------------------------*
write the sequence of button presses to the file "solutions"
*-------------------------------------------------------------------*/
void display(int *x)
{
int i;
fprintf(fp, "%d ", time(0));
for (i=0; i<12; i++) fprintf(fp, "%d ", x[i]);
fprintf(fp, "\n");
fflush(fp);
return;
}
/*-------------------------------------------------------------------*
test the sequence of button presses in array x to see if it will
close all the "security doors."
*-------------------------------------------------------------------*/
void test(int *x)
{
int i;
static long count=0;
count++;
for (i=0; i<24; i++) state[i]=1;
if (count%50000 == 0) printf("testing sequence %d\n", count);
for (i=0; i<12; i++) alterstate(x[i]);
for (i=0; i<24; i++) if (state[i]) return;
display(x);
return;
}
/*-------------------------------------------------------------------*
given a press of button 'b', how will that change the state of
the security doors? The case statements reflect what happens to
the other doors depending on whether the button 'b' is on or off.
*-------------------------------------------------------------------*/
void alterstate(int b)
{
switch (b) {
case 7:
if (state[7]) {
state[14]=state[14] ? 0 : 1;
state[19]=state[19] ? 0 : 1;
}
else {
state[0]=state[0] ? 0 : 1;
state[16]=state[16] ? 0 : 1;
state[21]=state[21] ? 0 : 1;
}
state[7]=state[7] ? 0 : 1;
break;
case 8:
if (state[8]) {
state[16]=state[16] ? 0 : 1;
state[20]=state[20] ? 0 : 1;
}
else {
state[11]=state[11] ? 0 : 1;
state[14]=state[14] ? 0 : 1;
state[19]=state[19] ? 0 : 1;
}
state[8]=state[8] ? 0 : 1;
break;
case 9:
if (state[9]) {
state[3]=state[3] ? 0 : 1;
state[13]=state[13] ? 0 : 1;
state[22]=state[22] ? 0 : 1;
}
else {
state[16]=state[16] ? 0 : 1;
state[20]=state[20] ? 0 : 1;
}
state[9]=state[9] ? 0 : 1;
break;
case 10:
if (state[10]) {
state[14]=state[14] ? 0 : 1;
state[18]=state[18] ? 0 : 1;
state[21]=state[21] ? 0 : 1;
}
else {
state[15]=state[15] ? 0 : 1;
state[20]=state[20] ? 0 : 1;
}
state[10]=state[10] ? 0 : 1;
break;
case 13:
if (state[13]) {
state[9]=state[9] ? 0 : 1;
state[20]=state[20] ? 0 : 1;
}
else {
state[4]=state[4] ? 0 : 1;
state[8]=state[8] ? 0 : 1;
state[22]=state[22] ? 0 : 1;
}
state[13]=state[13] ? 0 : 1;
break;
case 14:
if (state[14]) {
state[9]=state[9] ? 0 : 1;
state[22]=state[22] ? 0 : 1;
}
else {
state[7]=state[7] ? 0 : 1;
state[12]=state[12] ? 0 : 1;
state[19]=state[19] ? 0 : 1;
}
state[14]=state[14] ? 0 : 1;
break;
case 15:
if (state[15]) {
state[7]=state[7] ? 0 : 1;
state[22]=state[22] ? 0 : 1;
}
else {
state[13]=state[13] ? 0 : 1;
state[17]=state[17] ? 0 : 1;
state[20]=state[20] ? 0 : 1;
}
state[15]=state[15] ? 0 : 1;
break;
case 16:
if (state[16]) {
state[1]=state[1] ? 0 : 1;
state[9]=state[9] ? 0 : 1;
state[20]=state[20] ? 0 : 1;
}
else {
state[21]=state[21] ? 0 : 1;
state[22]=state[22] ? 0 : 1;
}
state[16]=state[16] ? 0 : 1;
break;
case 19:
if (state[19]) {
state[8]=state[8] ? 0 : 1;
state[15]=state[15] ? 0 : 1;
state[23]=state[23] ? 0 : 1;
}
else {
state[10]=state[10] ? 0 : 1;
state[14]=state[14] ? 0 : 1;
}
state[19]=state[19] ? 0 : 1;
break;
case 20:
if (state[20]) {
state[15]=state[15] ? 0 : 1;
state[22]=state[22] ? 0 : 1;
}
else {
state[2]=state[2] ? 0 : 1;
state[7]=state[7] ? 0 : 1;
state[9]=state[9] ? 0 : 1;
}
state[20]=state[20] ? 0 : 1;
break;
case 21:
if (state[21]) {
state[7]=state[7] ? 0 : 1;
state[14]=state[14] ? 0 : 1;
}
else {
state[6]=state[6] ? 0 : 1;
state[8]=state[8] ? 0 : 1;
state[16]=state[16] ? 0 : 1;
}
state[21]=state[21] ? 0 : 1;
break;
case 22:
if (state[22]) {
state[5]=state[5] ? 0 : 1;
state[8]=state[8] ? 0 : 1;
state[15]=state[15] ? 0 : 1;
}
else {
state[9]=state[9] ? 0 : 1;
state[19]=state[19] ? 0 : 1;
}
state[22]=state[22] ? 0 : 1;
break;
default:
printf("error, unknown value: %d", b);
}
}conrad@brahms.udel.edu (Jon Conrad) (03/04/91)
I'm in awe of the effort it took to write your program, but...
It isn't at all necessary. This is in many ways the EASIEST of the
"door" puzzles. You're using an atomic bomb to crack a walnut.
Note (if you want an alternative solution):
1. There are 12 doors you can click on, and 12 perimeter doors.
2. You are allowed 12 moves.
3. Each perimeter door will flip when exactly ONE clickable door
is clicked, in either open or closed position.
4. Therefore, these are the 12 moves you need.
5. List the doors you need to click when open, and the doors you need
to click when closed.
6. Make the moves you have listed. Order doesn't matter too much,
except that you mustn't cut yourself off from remaining moves.
I've solved this 3 times. Each order of moves was a little different;
in no case did I need to calculate all possible moves.
Logic is a time- and labor-saving alternative to brute force!!
Jon Alan Conrad