Added feature: scramble

5 files changed, 135 insertions, 16 deletions

diff --git a/src/main.c b/src/main.c
index 0a29d0e..125e4ec 100644
--- a/src/main.c
+++ b/src/main.c
@@ -1,6 +1,7 @@
 /* blabla */
 #include <stdio.h>
 #include <stdlib.h>
+#include <time.h>
 #include "utils.h"
 #include "coordinates.h"
 #include "io.h"
@@ -11,6 +12,8 @@
 char *commands[][10] = {
   {"help", "[COMMAND]",
    "Print this help, or a help page for COMMAND."},
+  {"scramble", "",
+   "Prints a random-state scramble"},
   {"save", "[MOVES|@ID|$ID]",
    "Save or copy a scramble."},
   {"change", "$ID1 [MOVES|$ID2|@ID2]",
@@ -141,6 +144,28 @@ void help_cmd(int n, char cmdtok[][100]) {
   }
 }
 
+void scramble_cmd(int n, char cmdtok[][100]) {
+  if (n > 1 || cmdtok[0][0] != 's') { /* Second case avoids warning */
+    printf("scramble: wrong syntax\n");
+    return;
+  }
+
+  srand(time(NULL));
+  int eofb = rand() % pow2to11;
+  int coud = rand() % pow3to7;
+  int ep   = rand() % factorial12;
+  int cp   = rand() % factorial8;
+  while (perm_sign_int(ep, 12) != perm_sign_int(cp, 8))
+    ep = (ep+1) % factorial12;
+
+  /* Debug */
+  /* printf("State: %d %d %d %d\n", eofb, coud, ep, cp); */
+
+  int scram[2][30];
+  reach_state(eofb, coud, ep, cp, scram);
+  print_results(1, scram);
+}
+
 void save_cmd(int n, char cmdtok[][100]) {
   int scram[255];
   if (n == 1) {
@@ -534,7 +559,7 @@ void dr_cmd(int n, char cmdtok[][100]) {
   int dr_list[m+5][30], ndr;
   if (from) {
     ndr = drfrom_scram_spam(scram_unnissed, dr_list, from, fb, rl, ud,
-                                m, b, niss, hide);
+                            m, b, niss, hide);
     if (ndr == -1) {
       printf("dr: from given, but EO not found (possibly other error).\n");
       return;
@@ -761,7 +786,7 @@ void exit_quit_cmd(int n, char cmdtok[][100]) {
 }
 
 void (*cmd_list[])(int n, char cmdtok[][100]) = {
-  help_cmd, save_cmd, change_cmd, print_cmd,
+  help_cmd, scramble_cmd, save_cmd, change_cmd, print_cmd,
   add_cmd, invert_cmd, unniss_cmd, pic_cmd,
   solve_cmd, replace_cmd,
   eo_cmd, dr_cmd, htr_cmd,
diff --git a/src/solver.c b/src/solver.c
index d918a54..c61aec4 100644
--- a/src/solver.c
+++ b/src/solver.c
@@ -463,11 +463,11 @@ int dr_scram_spam(int scram[], int dr_list[][30], int fb, int rl, int ud,
 /* DR finish */
 /*************/
 void dr_finish_dfs(int cp, int ep8, int ep4, int sol[][30], int *sol_count,
-                  int ep8_t_table[factorial8][19],
-                  int ep4_t_table[factorial4][19],
-                  int cp_p_table[factorial8],
-                  int ep8_p_table[factorial8],
-                  int mask, int last1, int last2, int moves, int m, int d) {
+                   int ep8_t_table[factorial8][19],
+                   int ep4_t_table[factorial4][19],
+                   int cp_p_table[factorial8],
+                   int ep8_p_table[factorial8],
+                   int mask, int last1, int last2, int moves, int m, int d) {
 
 
   if (*sol_count >= m || moves + cp_p_table[cp] > d ||
@@ -717,7 +717,7 @@ void small_optimal_dfs(int eofb, int eorl, int eoud, int ep,
   }
 }
 
-/* Solves directly using only medium tables. Suitable for short solutions. */
+/* Solves directly using only medium tables. Suitable for short solutions.
 void medium_optimal_dfs(int eofb, int eorl, int eoud,
                         int epose, int eposs, int eposm, int ep,
                         int coud, int cofb, int corl, int cp,
@@ -766,6 +766,7 @@ void medium_optimal_dfs(int eofb, int eorl, int eoud,
     }
   }
 }
+*/
       
 /* Uses huge tables */
 int optimal_dfs(int ep, int cp, int eo, int co, int emslices,
@@ -836,14 +837,6 @@ int solve_scram(int scram[], int sol[][30], int m, int b, int optimal) {
   if (n >= m || b <= 10)
     return n;
 
-  /* Then we try a slightly larger optimal solver */
-  /* 
-  int max_medium = 11;
-  init_directdr_pruning_tables();
-  for (int i = 0; i <= min(b, max_medium); i++)
-    medium_optimal_dfs(eofb, eorl, eoud, epose, eposs, eposm, ep,
-                       coud, cofb, corl, cp, sol, &n, 0, 0, 0, m, i);
-  */
 
   /* If we found at least a solution, we return */
   if (n > 0)
@@ -891,3 +884,82 @@ int solve_scram(int scram[], int sol[][30], int m, int b, int optimal) {
   }
   return best > b ? 0 : 1;
 }
+
+/* Given eofb, coud, ep and cp it finds a scramble that reaches that state.
+ * It uses a simple 3-step solver to find a preliminary "solution", and then
+ * gives this solutions as a scramble to a better solver (see above). */
+int reach_state(int eofb, int coud, int ep, int cp, int sol[][30]) {
+  
+  int fake_count = 0, fake_scram[30];
+  int eo_list[2][30], dr_list[2][30], finish_list[2][30];
+
+  /* Convert ep to array */
+  int ep_arr[12];
+  ep_int_to_array(ep, ep_arr);
+
+  /* Find EO */
+  init_small_pruning_tables();
+  for (int d = 0; d < 10; d++) {
+    niss_eo_dfs(eofb, fake_scram, eo_list, &fake_count, eofb_transition_table,
+                eofb_pruning_table, 0, 0, 0, 1, d, 0, 0, 0);
+    if (fake_count) {
+      fake_count = 0;
+      break;
+    }
+  }
+
+  /* Apply moves found, find epose */
+  for (int i = 0; eo_list[0][i]; i++) {
+    coud = coud_transition_table[coud][eo_list[0][i]];
+    cp   = cp_transition_table[cp][eo_list[0][i]];
+    apply_move_ep_array(eo_list[0][i], ep_arr);
+  }
+  int epose = epose_array_to_int(ep_arr);
+
+  /* Find DR */
+  init_drfromeo_pruning_tables();
+  for (int d = 0; d < 16; d++) {
+    niss_dr_from_eo_dfs(coud, epose, fake_scram, fake_scram, dr_list,
+                        &fake_count, coud_transition_table,
+                        epose_transition_table,
+                        coud_epose_from_eofb_pruning_table, move_mask_eofb,
+                        0, 0, 0, 0, 0, 1, d, 0, 0, 0);
+    if (fake_count) {
+      fake_count = 0;
+      break;
+    }
+  }
+
+  /* Apply moves found, find epud and epe */
+  for (int i = 0; dr_list[0][i]; i++) {
+    cp   = cp_transition_table[cp][dr_list[0][i]];
+    apply_move_ep_array(dr_list[0][i], ep_arr);
+  }
+  int epud = epud_array_to_int(ep_arr);
+  int epe  = epe_array_to_int(ep_arr);
+
+  /* Find finish */
+  init_small_pruning_tables();
+  for (int d = 0; d < 16; d++) {
+    dr_finish_dfs(cp, epud, epe, finish_list, &fake_count,
+                  epud_transition_table, epe_transition_table,
+                  cp_drud_pruning_table, epud_pruning_table, move_mask_drud,
+                  0, 0, 0, 1, d);
+    if (fake_count) {
+      fake_count = 0;
+      break;
+    }
+  }
+
+  int scram[50];
+
+  /* Debug */
+  /*print_moves(eo_list[0]); printf("\n");
+  print_moves(dr_list[0]); printf("\n");
+  print_moves(finish_list[0]); printf("\n");*/
+  
+  copy_moves(eo_list[0], scram);
+  append_moves(dr_list[0], scram);
+  append_moves(finish_list[0], scram);
+  return solve_scram(scram, sol, 1, 25, 0);
+}
diff --git a/src/solver.h b/src/solver.h
index 14997ed..d154c8f 100644
--- a/src/solver.h
+++ b/src/solver.h
@@ -11,3 +11,4 @@ int dr_corners_scram_spam(int scram[], int sol[][30], int from, int m, int b,
 int dr_finish_scram_spam(int scram[], int sol[][30], int from, int m, int b);
 int htr_finish_scram_spam(int scram[], int sol[][30], int m, int b);
 int solve_scram(int scram[], int sol[][30], int m, int b, int optimal);
+int reach_state(int eofb, int coud, int ep, int cp, int sol[][30]);
diff --git a/src/utils.c b/src/utils.c
index c672453..5b7df06 100644
--- a/src/utils.c
+++ b/src/utils.c
@@ -65,6 +65,23 @@ void index_to_perm(int p, int n, int *r) {
   }
 }
 
+
+int perm_sign_array(int a[], int n) {
+  int ret = 0;
+  for (int i = 0; i < n; i++)
+    for (int j = i+1; j < n; j++)
+      if (a[i]>a[j])
+        ret++;
+  return ret % 2;
+}
+
+int perm_sign_int(int p, int n) {
+  int a[n];
+  index_to_perm(p, n, a);
+  return perm_sign_array(a, n);
+}
+
+
 /* Converts a k-element subset of a set with an element from an array of n
  * elements, of which k are 1 (or just non-zero) and n-k are 0, to its index
  * in the sorted list of all such subsets.
diff --git a/src/utils.h b/src/utils.h
index b24ccb2..45a6302 100644
--- a/src/utils.h
+++ b/src/utils.h
@@ -36,6 +36,10 @@ int perm_to_index(int *a, int n);
  * (see perm_to_index) and saves the result to r. */
 void index_to_perm(int p, int n, int *r);
 
+/* Determine the sign of a permutation, either in integer or array format. */
+int perm_sign_array(int a[], int n);
+int perm_sign_int(int p, int n);
+
 /* Converts a k-element subset of a set with an element from an array of n
  * elements, of which k are 1 and n-k are 0, to its index in the sorted list
  * of all such subsets.