136 competition/games/set.p
Description
This article is from the Puzzles FAQ, by Chris Cole chris@questrel.questrel.com and Matthew Daly mwdaly@pobox.com with numerous contributions by others.
136 competition/games/set.p
What is the size of the largest collection of cards from which NO "set"
can be selected ?
competition/games/set.s
I can get 20:
1ROL
1GDL
1GDM
1GOM
1GSL
1PDH
1PDM
1POL
1POM
2RSL
2PDM
3ROL
3ROM
3RSL
3RSH
3GDM
3GOL
3GSL
3GSM
3POM
This collection of 20 is a local maximum.
The small C progam shown below was used to check for all possible
extensions to a collection of 21.
Of course this leaves open the question whether there exists a completely
different collection of 21 from which no "set" can be selected.
-- Gene Miller
------- C Program enclosed -------
#define N 21
static int data[N][4]= {
1, 1, 2, 1, /* 00 */
1, 2, 1, 1, /* 01 */
1, 2, 1, 2, /* 02 */
1, 2, 2, 2, /* 03 */
1, 2, 3, 1, /* 04 */
1, 3, 1, 3, /* 05 */
1, 3, 1, 2, /* 06 */
1, 3, 2, 1, /* 07 */
1, 3, 2, 2, /* 08 */
2, 1, 3, 1, /* 09 */
2, 3, 1, 2, /* 10 */
3, 1, 2, 1, /* 11 */
3, 1, 2, 2, /* 12 */
3, 1, 3, 1, /* 13 */
3, 1, 3, 3, /* 14 */
3, 2, 1, 2, /* 15 */
3, 2, 2, 1, /* 16 */
3, 2, 3, 1, /* 17 */
3, 2, 3, 2, /* 18 */
3, 3, 2, 2, /* 19 */
0, 0, 0, 0 /* 20 */ /* leave space for Nth combo */
};
main()
{
int x, y, z, w;
for (x=1; x<=3; x++) /* check all combos */
for (y=1; y<=3; y++)
for (z=1; z<=3; z++)
for (w=1; w<=3; w++)
printf ("%d %d %d %d -> sets=%d\n", x, y, z, w,
check (x, y, z, w));
}
int check(x,y,z,w)
int x, y, z, w;
{
int i,j,k,m;
int errors, sets;
for (i=0; i<N; i++) /* check for pre-existing combos */
if (x==data[i][0] &&
y==data[i][1] &&
z==data[i][2] &&
w==data[i][3] ) {
return -1; /* discard pre-existing*/
}
data[N-1][0] = x; /* make this the Nth combo */
data[N-1][1] = y;
data[N-1][2] = z;
data[N-1][3] = w;
sets = 0; /* start counting sets */
for (i=0; i<N; i++) /* look for sets */
for (j=i+1; j<N; j++)
for (k=j+1; k<N; k++) {
errors = 0;
for (m=0; m<4; m++) {
if (data[i][m] == data[j][m]) {
if (data[k][m] != data[i][m]) errors++;
if (data[k][m] != data[j][m]) errors++;
}
else {
if (data[k][m] == data[i][m]) errors++;
if (data[k][m] == data[j][m]) errors++;
}
}
if (errors == 0) /* no errors means is a set */
sets++; /* increment number of sets */
}
return sets;
}
--
I did some more experimenting. With the enclosed C program, I looked at many
randomly generated collections. In an earlier version of this program I
got one collection of 20 from a series of 100 trials. The rest were collections
ranging in size from 16 to 19. Unfortunately, in an attempt to make this
program more readable and more general, I changed the algorithm slightly and
I haven't been able to achieve 20 since then. I can't remember enough about
my changes to be able to get back to the previous version. In the most recent
1000 trials all of the maximaml collections range in size from 16 to 18.
I think that this experiment has shed very little light on what is the
global maximum, since the search space is many orders of magnitude larger
than what can be tried in a reasonable amount of time through random
searching.
I assume that Mr. Ring found his collection of 20 by hand. This indicates
that an intelligent search may be more fruitful than a purely random one.
------------------ Program enclosed -------------
int n;
int data[81][4];
main()
{
int i;
for (i=0; i<1000; i++) { /* Do 1000 independent trials */
printf ("Trial %d:\n", i);
try();
}
}
try()
{
int i;
int x, y, z, w;
n = 0; /* set collection size to zero */
for (i=0; i<100; i++) { /* try 100 random combos */
x = 1 + rand()%3;
y = 1 + rand()%3;
z = 1 + rand()%3;
w = 1 + rand()%3;
check (x, y, z, w);
}
for (x=1; x<=3; x++) /* check all combos */
for (y=1; y<=3; y++)
for (z=1; z<=3; z++)
for (w=1; w<=3; w++)
check (x, y, z, w);
printf (" collection size=%d\n", n);
}
int check(x, y, z, w) /* check whether a new combo can be added */
int x, y, z, w;
{
int i,j,k,m;
int errors, sets;
for (i=0; i<n; i++) /* check for pre-existing combos */
if (x==data[i][0] &&
y==data[i][1] &&
z==data[i][2] &&
w==data[i][3] ) {
return -1; /* discard pre-existing*/
}
data[n][0] = x; /* make this the nth combo */
data[n][1] = y;
data[n][2] = z;
data[n][3] = w;
sets = 0; /* start counting sets */
for (i=0; i<=n; i++) /* look for sets */
for (j=i+1; j<=n; j++)
for (k=j+1; k<=n; k++) {
errors = 0;
for (m=0; m<4; m++) {
if (data[i][m] == data[j][m]) {
if (data[k][m] != data[i][m]) errors++;
if (data[k][m] != data[j][m]) errors++;
}
else {
if (data[k][m] == data[i][m]) errors++;
if (data[k][m] == data[j][m]) errors++;
}
}
if (errors == 0) /* no errors means is a set */
sets++; /* increment number of sets */
}
if (sets == 0) {
n++; /* increment collection size */
printf ("%d %d %d %d\n", x, y, z, w);
}
return sets;
}
------------------ end of enclosed program -------------
-- Gene
--
Gene Miller Multimedia Communications
NYNEX Science & Technology Phone: 914 644 2834
500 Westchester Avenue Fax: 914 997 2997, 914 644 2260
White Plains, NY 10604 Email: gene@nynexst.com
Continue to:
My Books
