Added CO first command

7 files changed, 323 insertions, 73 deletions

diff --git a/README.md b/README.md
index 1278b31..25ba2d4 100644
--- 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
new file mode 100644
index 0000000..27c0b43
--- /dev/null
+++ 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
index 76442d5..0f435d3 100755
--- a/nissy
+++ b/nissy
diff --git a/src/helppages.h b/src/helppages.h
index 5ee0e4a..178de37 100644
--- 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
index 5bed343..a14e365 100644
--- 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
index 82abd85..48e845f 100644
--- 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
index d154c8f..abb55d3 100644
--- 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,