commit e1ebff51092baf5581b728baec05c52c4bb3445e
parent 0fe7c8b43c50ae5701463acbb186a6fe0f53a773
Author: Sebastiano Tronto <sebastiano.tronto@gmail.com>
Date: Sun, 12 Jul 2020 20:44:09 +0200
Added feature: scramble
Diffstat:
6 files changed, 135 insertions(+), 16 deletions(-)
diff --git a/nissy b/nissy
Binary files differ.
diff --git 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
@@ -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
@@ -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
@@ -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
@@ -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.
