Skip to content

Instantly share code, notes, and snippets.

@mhoehle

mhoehle/cxx

Last active June 16, 2023 23:46
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save mhoehle/e5cd120376c68b5e189bb458bb44580f to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save mhoehle/e5cd120376c68b5e189bb458bb44580f to your computer and use it in GitHub Desktop.
Download ZIP
Check that 17 repeats of Lw' Uw' Lw Uw in a 3x3 Rubik's cube take you back to the starting configuration.
Raw
cxx
// hoehle 2023-06-17: Downloaded as "subgroup.tar.gz" from
// http://www.geometer.org/rubik/index.html
// in order to check that 17 repeats are needed
// for the move sequence described in
// https://twitter.com/Rainmaker1973/status/1669664486855176192?s=20
// (the sequence is Lw' Uw' Lw Uw)
// or in the notation of the program (line 92):
// char *grouplist[] = {"l*Ru*DL*LU*U", 0};
// Compile with g++ subgroup.cxx -o subgroup -Wc++11-compat-deprecated-writable-strings
// Copyright 2003 Thomas R. Davis
//
// This file is part of Rubik.
//
//
// Rubik is free software; you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation; either version 2 of the License, or
// (at your option) any later version.
//
// Rubik is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with Rubik; if not, write to the Free Software Foundation,
// Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
// cube configuration:
// 0 1 2
// 3 4 5
// 6 7 8
//
// 9 10 11 18 19 20 27 28 29 36 37 38
// 12 13 14 21 22 23 30 31 32 39 40 41
// 15 16 17 24 25 26 33 34 35 42 43 44
//
// 45 46 47
// 48 49 50
// 51 52 53
// Cube faces:
//
// U
// L F R B
// D
// Moves: F, R, ... front, right, ... clockwise
// Moves: f, r, ... front, right, ... counter-clockwise
// >F whole cube clockwise
// *F front slice clockwise
// Fill in array grouplist with the generaters. For example:
// char *grouplist[] = {"FF", ">F", "D", 0}; counts all positions
// you can get to from FF, >F, or D in any order.
// define CORNERS or EDGES to get just corner or edge permutations.
#include <stdlib.h>
#include <stdio.h>
#define HASHSIZE 65536*2
#define CHUNKSIZE 20000
#define MAXGROUP 20000000
#ifdef CORNERS
#define COUNT 7
unsigned char cubefaces[7] = {0, 2, 6, 8, 15, 17, 33};
#endif
#ifdef EDGES
#define COUNT 11
unsigned char cubefaces[11] = {1, 3, 5, 7, 12, 14, 23, 32, 16, 25, 34};
#endif
#if !defined(EDGES) && !defined(CORNERS)
#define COUNT 20
unsigned char cubefaces[20] = {1, 3, 5, 7, 12, 14, 23, 32, 16, 25, 34,
0, 2, 6, 8, 15, 17, 33, 4, 22};
#endif
extern void moveface(int);
extern void movecube(int);
//char *grouplist[] = {"UUdd", "LLrr", "FFbb", 0};
//char *grouplist[] = {"rUUBlFuBDFUdLDDfRbDfubdU", "RF", 0};
//char *grouplist[] = {"UR", 0};
//char *grouplist[] = {"RUru", 0};
//https://twitter.com/Rainmaker1973/status/1669664486855176192?s=20
//char *grouplist[] = {"*l*u*L*U", 0};
char *grouplist[] = {"l*Ru*DL*LU*U", 0};
static int totalpositions = 0;
int maxdepth = 0;
struct hashrec {
char cube[COUNT];
struct hashrec *next;
int depth;
};
static struct hashrec *table[HASHSIZE];
static struct hashrec *group[MAXGROUP];
static struct hashrec *freelist = 0;
static struct hashrec *curhash = 0;
int currecord = 0;
int moves[6][54];
int movec[3][54];
#define moveit(a, b, c, d) moves[j][d]=a;moves[j][c]=d;moves[j][b]=c;moves[j][a]=b;
#define movex(a, b, c, d) movec[j][d]=a;movec[j][c]=d;movec[j][b]=c;movec[j][a]=b;
void hashstats()
{
int i, total;
int len[10000];
struct hashrec *h;
for (i = 0; i < 10000; i++) len[i] = 0;
for (i = 0; i < HASHSIZE; i++) {
total = 0;
h = table[i];
while (h) { total++; h = h->next; }
len[total]++;
}
for (i = 0; i < 10000; i++)
if (len[i] > 0) printf("[%d:%d]", i, len[i]);
printf("\n");
}
static void loadmovearray()
{
int i, j, tmp;
for (i = 0; i < 6; i++)
for (j = 0; j < 54; j++)
moves[i][j] = j;
j = 0;
moveit(0, 2, 8, 6);
moveit(1, 5, 7, 3);
moveit(9, 36, 27, 18);
moveit(10, 37, 28, 19);
moveit(11, 38, 29, 20);
j = 1;
moveit(9, 11, 17, 15);
moveit(10, 14, 16, 12);
moveit(0, 18, 45, 44);
moveit(3, 21, 48, 41);
moveit(6, 24, 51, 38);
j = 2;
moveit(18, 20, 26, 24);
moveit(19, 23, 25, 21);
moveit(6, 27, 47, 17);
moveit(7, 30, 46, 14);
moveit(8, 33, 45, 11);
j = 3;
moveit(27, 29, 35, 33);
moveit(28, 32, 34, 30);
moveit(8, 36, 53, 26);
moveit(5, 39, 50, 23);
moveit(2, 42, 47, 20);
j = 4;
moveit(36, 38, 44, 42);
moveit(37, 41, 43, 39);
moveit(2, 9, 51, 35);
moveit(1, 12, 52, 32);
moveit(0, 15, 53, 29);
j = 5;
moveit(45, 47, 53, 51);
moveit(46, 50, 52, 48);
moveit(24, 33, 42, 15);
moveit(25, 34, 43, 16);
moveit(26, 35, 44, 17);
for (i = 0; i < 3; i++)
for (j = 0; j < 54; j++)
movec[i][j] = j;
j = 0;
movex(0, 2, 8, 6);
movex(1, 5, 7, 3);
movex(45, 51, 53, 47);
movex(46, 48, 52, 50);
movex(9, 36, 27, 18);
movex(10, 37, 28, 19);
movex(11, 38, 29, 20);
movex(12, 39, 30, 21);
movex(13, 40, 31, 22);
movex(14, 41, 32, 23);
movex(15, 42, 33, 24);
movex(16, 43, 34, 25);
movex(17, 44, 35, 26);
j = 1;
movex(9, 11, 17, 15);
movex(10, 14, 16, 12);
movex(27, 33, 35, 29);
movex(28, 30, 34, 32);
movex(0, 18, 45, 44);
movex(3, 21, 48, 41);
movex(6, 24, 51, 38);
movex(1, 19, 46, 43);
movex(4, 22, 49, 40);
movex(7, 25, 52, 37);
movex(2, 20, 47, 42);
movex(5, 23, 50, 39);
movex(8, 26, 53, 36);
j = 2;
movex(18, 20, 26, 24);
movex(19, 23, 25, 21);
movex(36, 42, 44, 38);
movex(37, 39, 43, 41);
movex(6, 27, 47, 17);
movex(7, 30, 46, 14);
movex(8, 33, 45, 11);
movex(3, 28, 50, 16);
movex(4, 31, 49, 13);
movex(5, 34, 48, 10);
movex(0, 29, 53, 15);
movex(1, 32, 52, 12);
movex(2, 35, 51, 9);
}
static void inithash()
{
struct hashrec *tmp;
int i;
while (freelist) {
tmp = freelist;
freelist = freelist->next;
free(tmp);
}
for (i = 0; i < HASHSIZE; i++)
table[i] = 0;
totalpositions = 0;
curhash = 0;
currecord = 0;
maxdepth = 0;
loadmovearray();
}
int hashpos()
{
int i;
int hash = 0;
#ifdef CORNERS
for (i = 0; i < COUNT; i++) {
hash <<= 3;
hash ^= cubefaces[i];
}
#else
#ifdef EDGES
for (i = 0; i < COUNT; i++) {
hash <<= 2;
hash ^= cubefaces[i];
}
#else
for (i = 0; i < COUNT; i++) {
hash <<= 1;
hash ^= cubefaces[i];
}
#endif
#endif
return hash %(HASHSIZE-1);
}
static int samepos(struct hashrec *h)
{
int i;
for (i = 0; i < COUNT; i++)
if (h->cube[i] != cubefaces[i]) return 0;
return 1;
}
static struct hashrec *newrecord()
{
struct hashrec *newr;
if (currecord == 0) {
curhash = (struct hashrec *)malloc(CHUNKSIZE*sizeof(struct hashrec));
curhash->next = freelist;
freelist = curhash;
currecord = 1;
}
newr = curhash + currecord++;
if (currecord == CHUNKSIZE) currecord = 0;
//printf("%d\n", newr);
return newr;
}
void printcube()
{
int i;
for (i = 0; i < COUNT; i++)
printf("%2d ", cubefaces[i]);
printf("\n");
}
int addrec(int depth)
{
int h = hashpos();
int i;
struct hashrec *hnew, *hrec = table[h];
//printcube();
//printf(" %d\n", h);
if (hrec == 0) {
hnew = newrecord();
for (i = 0; i < COUNT; i++) hnew->cube[i] = cubefaces[i];
hnew->next = 0;
hnew->depth = depth;
if (depth > maxdepth) maxdepth = depth;
table[h] = hnew;
group[totalpositions] = hnew;
totalpositions++;
return 1;
}
while (hrec) {
if (samepos(hrec)) return 0;
if (hrec->next == 0) {
hnew = newrecord();
for (i = 0; i < COUNT; i++) hnew->cube[i] = cubefaces[i];
hnew->next = 0;
hnew->depth = depth;
if (depth > maxdepth) maxdepth = depth;
hrec->next = hnew;
group[totalpositions] = hnew;
totalpositions++;
return 1;
}
hrec = hrec->next;
}
return 0;
}
int grouppos = 0;
int listcount;
void makemove(char *s)
{
while (*s)
switch (*s++) {
case 'u': moveface(0); moveface(0);
case 'U': moveface(0); break;
case 'l': moveface(1); moveface(1);
case 'L': moveface(1); break;
case 'f': moveface(2); moveface(2);
case 'F': moveface(2); break;
case 'r': moveface(3); moveface(3);
case 'R': moveface(3); break;
case 'b': moveface(4); moveface(4);
case 'B': moveface(4); break;
case 'd': moveface(5); moveface(5);
case 'D': moveface(5); break;
case '>': // whole cube move
switch (*s++) {
case 'U': movecube(0); break;
case 'L': movecube(1); break;
case 'F': movecube(2); break;
case 'R': movecube(3); break;
case 'B': movecube(4); break;
case 'D': movecube(5); break;
}
break;
case '*': // slice move
switch (*s++) {
case 'U':
moveface(0);
moveface(0);
moveface(0);
moveface(5);
movecube(0);
break;
case 'L':
moveface(1);
moveface(1);
moveface(1);
moveface(3);
movecube(1);
break;
case 'F':
moveface(2);
moveface(2);
moveface(2);
moveface(4);
movecube(2);
break;
case 'R':
moveface(3);
moveface(3);
moveface(3);
moveface(1);
movecube(3);
break;
case 'B':
moveface(4);
moveface(4);
moveface(4);
moveface(2);
movecube(4);
break;
case 'D':
moveface(5);
moveface(5);
moveface(5);
moveface(0);
movecube(5);
break;
}
break;
}
}
int main()
{
int i, j, depth;
inithash();
addrec(0);
listcount = 0;
while (grouplist[listcount]) listcount++;
while (grouppos < totalpositions) {
for (i = 0; i < listcount; i++) {
for (j = 0; j < COUNT; j++) cubefaces[j] = group[grouppos]->cube[j];
depth = group[grouppos]->depth;
//printcube();
makemove(grouplist[i]);
addrec(depth+1);
if (totalpositions == MAXGROUP) {
printf("\nMore than %d group members\n", totalpositions);
return 0;
}
}
grouppos++;
if (grouppos % 100000 == 0) {
printf("[%d:%d]\n", grouppos, totalpositions);
//hashstats();
}
}
printf("\ntotal count = %d\nmaxdepth = %d\n", totalpositions, maxdepth);
return 0;
}
void moveface(int j)
{
unsigned char x[COUNT];
int i;
for (i = 0; i < COUNT; i++) x[i] = moves[j][cubefaces[i]];
for (i = 0; i < COUNT; i++) cubefaces[i] = x[i];
}
void movecube(int j)
{
unsigned char x[COUNT];
int i;
if (j < 3) {
for (i = 0; i < COUNT; i++) x[i] = movec[j][cubefaces[i]];
for (i = 0; i < COUNT; i++) cubefaces[i] = x[i];
} else switch (j) {
case 3:
movecube(1);
movecube(1);
movecube(1);
break;
case 4:
movecube(2);
movecube(2);
movecube(2);
break;
case 5:
movecube(0);
movecube(0);
movecube(0);
break;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment