commit a2a7678518ec1db608f37f0521a3f8b61e97f868
parent 96ffb29a550451152b125f353a2107141610bc27
Author: Sebastiano Tronto <sebastiano.tronto@gmail.com>
Date: Tue, 22 Sep 2020 00:04:49 +0200
Added CO first command
Diffstat:
7 files changed, 323 insertions(+), 73 deletions(-)
diff --git a/README.md b/README.md
@@ -26,7 +26,7 @@ example, on a Linux system with GCC installed:
```
cd path/to/nissy
-gcc -O3 -std=c99 -o nissy ./src/*.c
+gcc -O2 -std=c99 -o nissy ./src/*.c
./nissy
```
diff --git a/docs/co.txt b/docs/co.txt
@@ -0,0 +1,39 @@
+
+HELP PAGE FOR COMMAND co
+
+SYNTAX
+co [OPTIONS] [MOVES|$ID|@ID]
+
+DESCRIPTION
+Solves CO for a given scramble. A scramble can be given as last argument of the
+command, or an ID of a saved scramble can be provided. If none of the two is
+given, a prompt will ask the user to input a new scramble.
+
+OPTIONS
+axis={fb,rl,ud} Specify the axis for the CO. One to three axes can be given,
+ comma separated, no spaces.
+ Default: CO on any of the three axis (omitting the option is
+ the same as specifying axis=fb,rl,ud).
+b=N Specify a bound for the number of moves. N must be a number.
+ Default value: 20.
+h Show hidden COs.
+ Default, if an CO ending in e.g. F is shown, the equivalent
+ one ending in F' is hidden.
+i Ignore centers. By default the CO is aligned with centers.
+niss Use NISS.
+ Default: does not use NISS.
+n=N Specify a maximum number of COs to be output. N must be a
+ number.
+ Default value: 1.
+
+EXAMPLES
+co axis=fb $1
+ Finds one optimal CO on fb for the first saved scramble.
+
+co n=5 b=4 U R F
+ Finds up to 5 COs of length at most 4 for scramble U R F.
+
+co n=100 b=5 niss axis=fb,ud h R' U' F L R'U'F
+ Finds up to 100 COs of lenth at most 4, possibly using NISS, including
+ "hidden" COs, excluding the rl axis.
+
diff --git a/nissy b/nissy
Binary files differ.
diff --git a/src/helppages.h b/src/helppages.h
@@ -1,6 +1,6 @@
/* To generate this help page, use the script makedoc.sh */
-int Npages = 21;
+int Npages = 22;
char *helppages[][10] = {
@@ -67,6 +67,50 @@ Resets all saved scrambles and output sequences.\n\
"
},
+{ "co",
+"\
+\n\
+HELP PAGE FOR COMMAND co\n\
+\n\
+SYNTAX\n\
+co [OPTIONS] [MOVES|$ID|@ID]\n\
+\n\
+DESCRIPTION\n\
+Solves CO for a given scramble. A scramble can be given as last argument of the\n\
+command, or an ID of a saved scramble can be provided. If none of the two is\n\
+given, a prompt will ask the user to input a new scramble.\n\
+\n\
+OPTIONS\n\
+axis={fb,rl,ud} Specify the axis for the CO. One to three axes can be given,\n\
+ comma separated, no spaces.\n\
+ Default: CO on any of the three axis (omitting the option is\n\
+ the same as specifying axis=fb,rl,ud).\n\
+b=N Specify a bound for the number of moves. N must be a number.\n\
+ Default value: 20.\n\
+h Show hidden COs.\n\
+ Default, if an CO ending in e.g. F is shown, the equivalent\n\
+ one ending in F' is hidden.\n\
+i Ignore centers. By default the CO is aligned with centers.\n\
+niss Use NISS.\n\
+ Default: does not use NISS.\n\
+n=N Specify a maximum number of COs to be output. N must be a\n\
+ number.\n\
+ Default value: 1.\n\
+\n\
+EXAMPLES\n\
+co axis=fb $1\n\
+ Finds one optimal CO on fb for the first saved scramble.\n\
+\n\
+co n=5 b=4 U R F \n\
+ Finds up to 5 COs of length at most 4 for scramble U R F.\n\
+\n\
+co n=100 b=5 niss axis=fb,ud h R' U' F L R'U'F\n\
+ Finds up to 100 COs of lenth at most 4, possibly using NISS, including\n\
+ \"hidden\" COs, excluding the rl axis.\n\
+\n\
+"
+},
+
{ "dr",
"\
\n\
diff --git a/src/main.c b/src/main.c
@@ -8,51 +8,6 @@
#include "solver.h"
#include "string.h"
#include "helppages.h"
-
-char *commands[][10] = {
- {"help", "[COMMAND]",
- "Print this help, or a help page for COMMAND."},
- {"scramble", "[OPTIONS]",
- "Prints a random-state scramble."},
- {"save", "[MOVES|@ID|$ID]",
- "Save or copy a scramble."},
- {"change", "$ID1 [MOVES|$ID2|@ID2]",
- "Change a memorized scramble."},
- {"print", "[$ID|@ID]",
- "Print memorized sequences."},
- {"add", "[MOVES|$ID1|@ID1] $ID2",
- "Add moves at the end of a memorized scramble."},
- {"invert", "[MOVES|$ID|@ID]",
- "Inverts the given sequence of moves."},
- {"unniss", "[MOVES|$ID|@ID]}",
- "Removes NISS: A (B) -> B\' A."},
- {"pic", "[MOVES|$ID|@ID]",
- "Show a text description of the scrambled cube."},
- {"solve", "[MOVES|$ID|@ID]",
- "Solves a scramble."},
- {"replace", "[MOVES|$ID|@ID]",
- "Find non-optimal subsequences."},
- {"clear", "",
- "Delete saved scrambles and output sequences."},
- {"eo", "[MOVES|$ID|@ID]",
- "Solves EO."},
- {"dr", "[MOVES|$ID|@ID]",
- "Solves DR, either directly or from eo."},
- {"htr", "[MOVES|$ID|@ID]",
- "Solves HTR from DR."},
- {"drfinish", "[MOVES|$ID|@ID]",
- "Solves the cube after DR."},
- {"htrfinish", "[MOVES|$ID|@ID]",
- "Solves the cube using only half turns."},
- {"drcorners", "[MOVES|$ID|@ID]",
- "Solves corners after DR."},
- {"exit", "",
- "Exit nissy."},
- {"quit", "",
- "Exit nissy."},
- {"", "", ""}
-};
-
/* Saved sequences of moves */
int scr_count=1, tmp_count=1, max_tmp=999;
int scrambles[255][255], tmp[1000][255];
@@ -122,28 +77,6 @@ int parsecmd(char *cmd, char cmdtok[][100]) {
return n;
}
-void help_cmd(int n, char cmdtok[][100]) {
- if (n == 1) {
- printf("\n");
- for (int i = 0; commands[i][0][0]; i++)
- printf("%-10s%-25s%s\n", commands[i][0], commands[i][1], commands[i][2]);
- printf("\n");
- printf("Type \'help\' followed by a command for a detailed help page.\n");
- printf("Type \'help nissy\' for a general user guide.\n");
- } else if (n == 2) {
- for (int i = 0; i < Npages; i++) {
- if (!strcmp(helppages[i][0], cmdtok[1])) {
- printf("%s", helppages[i][1]);
- return;
- }
- }
- printf("No help page for %s.\n", cmdtok[1]);
- return;
- } else {
- printf("help: wrong syntax.\n");
- }
-}
-
void scramble_cmd(int n, char cmdtok[][100]) {
int c = 0, e = 0, dr = 0;
@@ -528,6 +461,69 @@ void eo_cmd(int n, char cmdtok[][100]) {
print_results(neo, eo_list);
}
+void co_cmd(int n, char cmdtok[][100]) {
+
+ /* Default values */
+ int m = 1, b = 20, ignore = 0;
+ int niss = 0, hide = 1;
+ int fb = 1, rl = 1, ud = 1;
+ int scram[255] = {[0] = 0};
+ int scram_unnissed[255];
+
+ /* Parse options */
+ for (int i = 1; i < n && scram[0] == 0; i++) {
+ if (!strcmp(cmdtok[i], "h")) {
+ hide = 0;
+ } else if (!strcmp(cmdtok[i], "niss")) {
+ niss = 1;
+ } else if (!strcmp(cmdtok[i], "i")) {
+ ignore = 1;
+ } else if (!strncmp(cmdtok[i], "axis=", 5)) {
+ fb = rl = ud = 0;
+ if (strstr(cmdtok[i], "fb") != NULL)
+ fb = 1;
+ if (strstr(cmdtok[i], "rl") != NULL)
+ rl = 1;
+ if (strstr(cmdtok[i], "ud") != NULL)
+ ud = 1;
+ if (fb + rl + ud == 0) {
+ printf("co: bad axis option.\n");
+ return;
+ }
+ } else if (!strncmp(cmdtok[i], "n=", 2)) {
+ m = atoi(cmdtok[i]+2);
+ if (m <= 0) {
+ printf("co: bad option n.\n");
+ return;
+ }
+ } else if (!strncmp(cmdtok[i], "b=", 2)) {
+ b = atoi(cmdtok[i]+2);
+ if (b <= 0) {
+ printf("co: bad option b.\n");
+ return;
+ }
+ } else if (read_moves_from_argument(n-i, cmdtok+i, scram) == -1) {
+ printf("co: error reading moves or ID.\n");
+ return;
+ }
+ }
+
+ if (scram[0] == 0) {
+ if (read_moves_from_prompt(scram) == -1) {
+ printf("co: error reading moves.\n");
+ return;
+ }
+ }
+
+ unniss(scram, scram_unnissed);
+
+ /* Call solver and print results */
+ int co_list[m+5][30];
+ int nco = co_scram_spam(scram_unnissed, co_list, fb, rl, ud, m, b, niss,
+ hide, ignore);
+ print_results(nco, co_list);
+}
+
void dr_cmd(int n, char cmdtok[][100]) {
/* Default values */
@@ -763,7 +759,7 @@ void htrfinish_cmd(int n, char cmdtok[][100]) {
void drcorners_cmd(int n, char cmdtok[][100]) {
/* Default values */
- int m = 1, b = 20, ignore=0;
+ int m = 1, b = 20, ignore = 0;
int from = 0; /* 0: unspecified; {1,2,3}: from {ud,fb,rl} */
int scram[255] = {[0] = 0};
int scram_unnissed[255];
@@ -823,15 +819,89 @@ void exit_quit_cmd(int n, char cmdtok[][100]) {
printf("%s: wrong synstax.\n", cmdtok[0]);
}
+/***************************************************************/
+/* List of all commands */
+/* Important: they must be in the same order in the two arrays */
+/***************************************************************/
+
+char *commands[][10] = {
+ {"help", "[COMMAND]",
+ "Print this help, or a help page for COMMAND."},
+ {"scramble", "[OPTIONS]",
+ "Prints a random-state scramble."},
+ {"save", "[MOVES|@ID|$ID]",
+ "Save or copy a scramble."},
+ {"change", "$ID1 [MOVES|$ID2|@ID2]",
+ "Change a memorized scramble."},
+ {"print", "[$ID|@ID]",
+ "Print memorized sequences."},
+ {"add", "[MOVES|$ID1|@ID1] $ID2",
+ "Add moves at the end of a memorized scramble."},
+ {"invert", "[MOVES|$ID|@ID]",
+ "Inverts the given sequence of moves."},
+ {"unniss", "[MOVES|$ID|@ID]}",
+ "Removes NISS: A (B) -> B\' A."},
+ {"pic", "[MOVES|$ID|@ID]",
+ "Show a text description of the scrambled cube."},
+ {"solve", "[MOVES|$ID|@ID]",
+ "Solves a scramble."},
+ {"replace", "[MOVES|$ID|@ID]",
+ "Find non-optimal subsequences."},
+ {"clear", "",
+ "Delete saved scrambles and output sequences."},
+ {"eo", "[MOVES|$ID|@ID]",
+ "Solves EO."},
+ {"co", "[MOVES|$ID|@ID]",
+ "Solves CO."},
+ {"dr", "[MOVES|$ID|@ID]",
+ "Solves DR, either directly or from eo."},
+ {"htr", "[MOVES|$ID|@ID]",
+ "Solves HTR from DR."},
+ {"drfinish", "[MOVES|$ID|@ID]",
+ "Solves the cube after DR."},
+ {"htrfinish", "[MOVES|$ID|@ID]",
+ "Solves the cube using only half turns."},
+ {"drcorners", "[MOVES|$ID|@ID]",
+ "Solves corners after DR."},
+ {"exit", "",
+ "Exit nissy."},
+ {"quit", "",
+ "Exit nissy."},
+ {"", "", ""}
+};
+
+void help_cmd(int n, char cmdtok[][100]) {
+ if (n == 1) {
+ printf("\n");
+ for (int i = 0; commands[i][0][0]; i++)
+ printf("%-10s%-25s%s\n", commands[i][0], commands[i][1], commands[i][2]);
+ printf("\n");
+ printf("Type \'help\' followed by a command for a detailed help page.\n");
+ printf("Type \'help nissy\' for a general user guide.\n");
+ } else if (n == 2) {
+ for (int i = 0; i < Npages; i++) {
+ if (!strcmp(helppages[i][0], cmdtok[1])) {
+ printf("%s", helppages[i][1]);
+ return;
+ }
+ }
+ printf("No help page for %s.\n", cmdtok[1]);
+ return;
+ } else {
+ printf("help: wrong syntax.\n");
+ }
+}
+
void (*cmd_list[])(int n, char cmdtok[][100]) = {
help_cmd, scramble_cmd, save_cmd, change_cmd, print_cmd,
add_cmd, invert_cmd, unniss_cmd, pic_cmd,
solve_cmd, replace_cmd, clear_cmd,
- eo_cmd, dr_cmd, htr_cmd,
+ eo_cmd, co_cmd, dr_cmd, htr_cmd,
drfinish_cmd, htrfinish_cmd, drcorners_cmd,
exit_quit_cmd, exit_quit_cmd, NULL
};
+
void execcmd(int n, char cmdtok[][100]) {
int i = 0;
while (strcmp(commands[i][0], cmdtok[0]) && strcmp(commands[i][0], ""))
@@ -842,6 +912,9 @@ void execcmd(int n, char cmdtok[][100]) {
printf("%s: not a command.\n", cmdtok[0]);
}
+
+/* Main loop */
+
int main() {
init_transition_table();
init_possible_next();
diff --git a/src/solver.c b/src/solver.c
@@ -107,6 +107,88 @@ int eo_scram_spam(int scram[], int eo_list[][30], int fb, int rl, int ud,
}
+/******/
+/* CO */
+/******/
+void niss_co_dfs(int co, int scramble[], int co_list[][30], int *co_count,
+ int t_table[pow3to7][19], int p_table[pow3to7],
+ int last1, int last2, int moves, int m, int d, int niss,
+ int can_use_niss, int hide, int ignore) {
+
+
+ if (*co_count >= m || moves > d ||
+ ((!can_use_niss || niss) && ((!ignore && moves + p_table[co] > d) ||
+ ( ignore && moves + p_table[co] - 2 > d))))
+ return;
+
+ co_list[*co_count][moves] = 0;
+
+ if (co == 0 || (ignore && ( t_table[t_table[co][F]][B] == 0 ||
+ t_table[t_table[co][R]][L] == 0 ||
+ t_table[t_table[co][U]][D] == 0 ))) {
+ /* If an early CO is found, or if "case F2 B", or if hide is on. */
+ if (moves != d || (parallel(last1, last2) && last2 % 3 == 2) ||
+ (hide && moves > 0 &&
+ (last1 % 3 == 0 || (parallel(last1, last2) && last2 % 3 == 0))))
+ return;
+ /* Copy moves for the next solution */
+ if (*co_count < m - 1)
+ copy_moves(co_list[*co_count], co_list[(*co_count)+1]);
+ (*co_count)++;
+ return;
+ }
+
+ for (int i = 1; i < 19; i++) {
+ if (possible_next[last1][last2] & (1 << i)) {
+ co_list[*co_count][moves] = niss ? -i : i;
+ niss_co_dfs(t_table[co][i], scramble, co_list, co_count, t_table,
+ p_table, i, last1, moves+1, m, d, niss,
+ can_use_niss, hide, ignore);
+ }
+ }
+
+ if (*co_count >= m)
+ return;
+ co_list[*co_count][moves] = 0;
+
+ /* If not nissing already and we either have not done any move yet or
+ * the last move was F/F' etc, and if I am allowed to niss, try niss! */
+ if (!niss && (last1 == 0 || t_table[0][last1] != 0) && can_use_niss &&
+ !(hide && moves > 0 &&
+ (last1 % 3 == 0 || (parallel(last1, last2) && last2 % 3 == 0)))) {
+ int aux[] = {0,0};
+ niss_co_dfs(premoves_inverse(co_list[*co_count], scramble, aux, t_table),
+ scramble, co_list, co_count, t_table, p_table,
+ 0, 0, moves, m, d, 1, can_use_niss, hide, ignore);
+ }
+}
+
+int co_scram_spam(int scram[], int co_list[][30], int fb, int rl, int ud,
+ int m, int b, int niss, int h, int ignore) {
+
+ init_small_pruning_tables();
+
+ int n = 0, cofb = 0, corl = 0, coud = 0;
+ for (int i = 0; scram[i]; i++) {
+ cofb = cofb_transition_table[cofb][scram[i]];
+ corl = corl_transition_table[corl][scram[i]];
+ coud = coud_transition_table[coud][scram[i]];
+ }
+ for (int i = 0; i <= b; i++) {
+ if (fb)
+ niss_co_dfs(cofb, scram, co_list, &n, cofb_transition_table,
+ cofb_pruning_table, 0, 0, 0, m, i, 0, niss, h, ignore);
+ if (rl)
+ niss_co_dfs(corl, scram, co_list, &n, corl_transition_table,
+ corl_pruning_table, 0, 0, 0, m, i, 0, niss, h, ignore);
+ if (ud)
+ niss_co_dfs(coud, scram, co_list, &n, coud_transition_table,
+ coud_pruning_table, 0, 0, 0, m, i, 0, niss, h, ignore);
+ }
+ return n;
+}
+
+
/**************/
/* DR from EO */
/**************/
@@ -600,10 +682,20 @@ void dr_corners_dfs(int cp, int sol[][30], int *sol_count,
sol[*sol_count][moves] = 0;
- if (cp == 0 || (ignore &&
+ if (cp == 0 ||
+ (ignore && mask == move_mask_drud &&
(cp_transition_table[cp_transition_table[cp][U]][D3] == 0 ||
cp_transition_table[cp_transition_table[cp][U2]][D2] == 0 ||
- cp_transition_table[cp_transition_table[cp][U3]][D] == 0 ))) {
+ cp_transition_table[cp_transition_table[cp][U3]][D] == 0 )) ||
+ (ignore && mask == move_mask_drfb &&
+ (cp_transition_table[cp_transition_table[cp][F]][B3] == 0 ||
+ cp_transition_table[cp_transition_table[cp][F2]][B2] == 0 ||
+ cp_transition_table[cp_transition_table[cp][F3]][B] == 0 )) ||
+ (ignore && mask == move_mask_drrl &&
+ (cp_transition_table[cp_transition_table[cp][R]][L3] == 0 ||
+ cp_transition_table[cp_transition_table[cp][R2]][L2] == 0 ||
+ cp_transition_table[cp_transition_table[cp][R3]][L] == 0 ))
+ ) {
if (moves != d)
return;
/* Copy moves for the next solution */
diff --git a/src/solver.h b/src/solver.h
@@ -1,5 +1,7 @@
int eo_scram_spam(int scram[], int eo_list[][30], int fb, int rl, int ud,
int m, int b, int niss, int h);
+int co_scram_spam(int scram[], int co_list[][30], int fb, int rl, int ud,
+ int m, int b, int niss, int h, int i);
int dr_scram_spam(int scram[], int dr_list[][30], int fb, int rl, int ud,
int m, int b, int h);
int drfrom_scram_spam(int scram[], int dr_list[][30], int from, int fb,
