aboutsummaryrefslogtreecommitdiff
path: root/tools
diff options
context:
space:
mode:
authorSebastiano Tronto <sebastiano@tronto.net>2024-12-07 16:38:40 +0100
committerSebastiano Tronto <sebastiano@tronto.net>2024-12-07 16:38:40 +0100
commit9ac266c76f39620d8343e46ca41cb09d1534384c (patch)
tree823bd419d99fe0f00e6b5b713237a73b4ec7ffca /tools
parentea25a7ccad625c4e664dfd114147971b8a2677f3 (diff)
downloadnissy-core-9ac266c76f39620d8343e46ca41cb09d1534384c.tar.gz
nissy-core-9ac266c76f39620d8343e46ca41cb09d1534384c.zip
Merge the "solver-experiments" branch that I have been working on for
a few weeks. This include mainly three things: 1. Various tweaks for a total performance gain of around 30%. 2. Take into account symmetries and avoid repeated work. This required a re-work of the splitting into tasks before the solve. 3. Add a second fallback table (eoesep). This gives huge performance gains for particular scrambles (e.g. superflip). After merging this commit, remove and re-generate all pruning tables. Squashed commit of the following: commit 60f0705d2d69050e6a30581a2810f686d6f69b80 Author: Sebastiano Tronto <sebastiano@tronto.net> Date: Sat Dec 7 16:06:48 2024 +0100 Fix indentation commit cc5d489a251812b6188c0ba264ac6cb2236f1afe Author: Sebastiano Tronto <sebastiano@tronto.net> Date: Sat Dec 7 15:56:19 2024 +0100 Updated documentation commit a3f605dd628546e52564f82b139feb473b0725f3 Author: Sebastiano Tronto <sebastiano@tronto.net> Date: Sat Dec 7 14:01:11 2024 +0100 use eoesep table as second fallback commit c75e43c9116c64f97e92b0fe038be8a032925a72 Author: Sebastiano Tronto <sebastiano@tronto.net> Date: Fri Dec 6 16:13:23 2024 +0100 First commit for gendata_eoesep commit fea7688ab8bdc5ae0c3480622e2510a3bcd39248 Author: Sebastiano Tronto <sebastiano@tronto.net> Date: Tue Dec 3 17:31:00 2024 +0100 Add scramble to tool commit 66866cb71dea4ca8278ecb9e90ff4295771feb42 Author: Sebastiano Tronto <sebastiano@tronto.net> Date: Tue Dec 3 17:22:59 2024 +0100 Added tool to check multiple solutions commit ef65611c772c3996bddca8d181da3538e0af1674 Author: Sebastiano Tronto <sebastiano@tronto.net> Date: Tue Dec 3 17:16:20 2024 +0100 Write all solutions for symmetric positions commit e3ded26db7d7d4ae7c0e2488151ed14f581f7b8e Author: Sebastiano Tronto <sebastiano@tronto.net> Date: Tue Nov 26 09:14:54 2024 +0100 Added symmetry filter (TODO: print excluded solutions) commit 864c437a9751c58d58562650ca9eba4a9e6ad3eb Author: Sebastiano Tronto <sebastiano@tronto.net> Date: Mon Nov 25 14:51:13 2024 +0100 Improved task split commit b88926d36d7ab0c64c5fe3bb954fd15d41267fba Author: Sebastiano Tronto <sebastiano@tronto.net> Date: Fri Nov 22 19:06:41 2024 +0100 Reworked tasks for multi-threading in view of symmetry filter commit 26fa653f97df8cd601aecb80eaf89f0a00e9ba9f Author: Sebastiano Tronto <sebastiano@tronto.net> Date: Thu Oct 31 15:37:43 2024 +0100 Added transform move commit 19f655ef94d658eaa2fefb5cea3c167a3ec58db6 Author: Sebastiano Tronto <sebastiano@tronto.net> Date: Thu Oct 31 09:29:15 2024 +0100 Clarified doc commit 3b0fe1e5ef8b628854e30f0f0067300e2763c954 Author: Sebastiano Tronto <sebastiano@tronto.net> Date: Thu Oct 31 08:36:58 2024 +0100 Handle solved cube correctly commit 57705cbc4982e3abe97a36ed64871738d4f721c0 Author: Sebastiano Tronto <sebastiano@tronto.net> Date: Thu Oct 31 08:24:30 2024 +0100 Close file commit fc7d462b58bcf3d3a3fbf26c1f3bd04c640a4898 Author: Sebastiano Tronto <sebastiano@tronto.net> Date: Tue Oct 29 15:05:48 2024 +0100 Removed stats tool commit 359bf7cb49ef405ee76ed662207d47cb2abcc5a9 Author: Sebastiano Tronto <sebastiano@tronto.net> Date: Tue Oct 29 15:01:51 2024 +0100 Updated theory doc commit 39c315af562bc4ce896f41004388a4c34d475d37 Author: Sebastiano Tronto <sebastiano@tronto.net> Date: Tue Oct 29 14:51:40 2024 +0100 Remove unused constants commit 57a5d24538aa59a4df9221dad2f99e9f0286bd9d Author: Sebastiano Tronto <sebastiano@tronto.net> Date: Tue Oct 29 10:20:38 2024 +0100 Add tool to solve scrambles from file commit 07e2918c216636891b1fa6adecc9756086a901e9 Author: Sebastiano Tronto <sebastiano@tronto.net> Date: Mon Oct 28 17:00:00 2024 +0100 Add make table to tool commit f5e5266c654eb027a5a35c57cc618555246f5e5e Author: Sebastiano Tronto <sebastiano@tronto.net> Date: Mon Oct 28 09:35:49 2024 +0100 Remove old solver, other small things commit a1ec78025b7959dbb845213f7f4e6851ecebc204 Author: Sebastiano Tronto <sebastiano@tronto.net> Date: Sun Oct 27 02:00:29 2024 +0200 Improvements commit 8eea23dbe888d923e662e24ae969130e2c67b999 Author: Sebastiano Tronto <sebastiano@tronto.net> Date: Sat Oct 26 12:24:19 2024 +0200 Makefile fix commit 3fc3927beacc78971cefeb42da8d71fe6c015fc1 Author: Sebastiano Tronto <sebastiano@tronto.net> Date: Fri Oct 25 18:25:09 2024 +0200 More performance gains commit 7b4efa1f9af9722de1ab9ccfc27899825a0d12c4 Author: Sebastiano Tronto <sebastiano@tronto.net> Date: Fri Oct 25 15:53:20 2024 +0200 Alternative solver implementation, small performance gain
Diffstat (limited to 'tools')
-rw-r--r--tools/200_stats_tables_h48/stats_tables_h48.c117
-rw-r--r--tools/301_solve_file/solve_file.c71
-rw-r--r--tools/302_solve_multisol/solve_multisol.c66
3 files changed, 137 insertions, 117 deletions
diff --git a/tools/200_stats_tables_h48/stats_tables_h48.c b/tools/200_stats_tables_h48/stats_tables_h48.c
deleted file mode 100644
index bdf6329..0000000
--- a/tools/200_stats_tables_h48/stats_tables_h48.c
+++ /dev/null
@@ -1,117 +0,0 @@
1#include <pthread.h>
2
3#include "../tool.h"
4
5#define MAXMOVES 20
6#define LOG_EVERY (NCUBES_PER_THREAD / 10)
7
8int NCUBES_PER_THREAD;
9int64_t size = 0;
10const char *solver = "h48stats";
11const char *filename = "tables/h48h0k4";
12char *buf;
13
14typedef struct {
15 int n;
16 int thread_id;
17 int64_t v[12][100];
18} thread_arg_t;
19
20uint64_t randll(void) {
21 long long int i, ret;
22
23 for (i = 0, ret = 0; i < 64; i++)
24 ret |= (long long int)(rand() % 2) << i;
25
26 return ret;
27}
28
29static void *
30run_thread(void *arg)
31{
32 char s[12], cube[22];
33 long long int ep, eo, cp, co, stats[NISSY_SIZE_SOLVE_STATS];
34 int i, j;
35
36 thread_arg_t *a = (thread_arg_t *)arg;
37
38 for (i = 0; i < a->n; i++) {
39 ep = randll();
40 eo = randll();
41 cp = randll();
42 co = randll();
43 nissy_getcube(ep, eo, cp, co, "fix", cube);
44 nissy_solve(cube, "h48stats", NISSY_NISSFLAG_NORMAL,
45 0, MAXMOVES, 1, -1, size, buf, 12, s, stats);
46 for (j = 0; j < 12; j++)
47 a->v[j][(int)s[j]]++;
48 if ((i+1) % LOG_EVERY == 0)
49 printf("[thread %d] %d cubes solved...\n",
50 a->thread_id, i+1);
51 }
52
53 return NULL;
54}
55
56void run(void) {
57 int64_t i, j, k, tot;
58 double avg;
59 pthread_t thread[THREADS];
60 thread_arg_t arg[THREADS];
61
62 size = nissy_datasize(solver);
63
64 for (i = 0; i < THREADS; i++) {
65 arg[i] = (thread_arg_t) {
66 .thread_id = i,
67 .n = NCUBES_PER_THREAD,
68 .v = {{0}}
69 };
70 pthread_create(&thread[i], NULL, run_thread, &arg[i]);
71 }
72
73 for (i = 0; i < THREADS; i++)
74 pthread_join(thread[i], NULL);
75
76 for (j = 0; j < 12; j++) {
77 printf("Data for h=%" PRId64 "\n", j);
78 for (k = 0, avg = 0.0; k < 16; k++) {
79 for (i = 0, tot = 0; i < THREADS; i++)
80 tot += arg[i].v[j][k];
81 printf("%" PRId64 "\t%" PRId64 "\n", k, tot);
82 avg += tot * k;
83 }
84 avg /= (double)(NCUBES_PER_THREAD * THREADS);
85 printf("Average: %.4lf\n", avg);
86 printf("\n");
87 }
88}
89
90int main(int argc, char **argv) {
91 srand(time(NULL));
92 nissy_setlogger(log_stderr);
93
94 if (argc < 2) {
95 printf("Error: not enough arguments. "
96 "Number of cubes per thread must be provided.\n");
97 return 1;
98 }
99
100 NCUBES_PER_THREAD = atoi(argv[1]);
101
102 if (NCUBES_PER_THREAD < 1 || NCUBES_PER_THREAD > 1000000) {
103 printf("Invalid number of cubes: must be > 0 and "
104 "< 1000000, but %d was given.\n", NCUBES_PER_THREAD);
105 return 1;
106 }
107
108 printf("Using %d cubes per thread (%d total)\n",
109 NCUBES_PER_THREAD, NCUBES_PER_THREAD * THREADS);
110 if (getdata(solver, &buf, filename) != 0)
111 return 1;
112
113 timerun(run);
114
115 free(buf);
116 return 0;
117}
diff --git a/tools/301_solve_file/solve_file.c b/tools/301_solve_file/solve_file.c
new file mode 100644
index 0000000..aa45df0
--- /dev/null
+++ b/tools/301_solve_file/solve_file.c
@@ -0,0 +1,71 @@
1#include "../tool.h"
2
3#define SOL_BUFFER_LEN 1000
4#define MAX_SCR 10000
5#define MAX_SCR_LEN 250
6
7char *solver;
8int64_t size = 0, N = 0;
9char *buf;
10char scrambles[MAX_SCR][MAX_SCR_LEN];
11
12void run(void) {
13 int64_t i, nsols;
14 long long stats[NISSY_SIZE_SOLVE_STATS];
15 char sol[SOL_BUFFER_LEN], cube[22];
16
17 printf("Solved the following scrambles:\n\n");
18 for (i = 0; i < N; i++) {
19 printf("%" PRId64 ". %s\n", i+1, scrambles[i]);
20 printf("Solving scramble %s\n", scrambles[i]);
21 if (nissy_applymoves(NISSY_SOLVED_CUBE, scrambles[i], cube)
22 == -1) {
23 printf("Invalid scramble\n");
24 continue;
25 }
26 nsols = nissy_solve(cube, solver, NISSY_NISSFLAG_NORMAL,
27 0, 20, 1, -1, size, buf, SOL_BUFFER_LEN, sol, stats);
28 if (nsols == 0)
29 printf("No solution found\n");
30 else
31 printf("Solutions:\n%s\n", sol);
32 }
33}
34
35int main(int argc, char **argv) {
36 char filename[255], *scrfilename;
37 FILE *scrfile;
38
39 if (argc < 3) {
40 printf("Error: not enough arguments. "
41 "A solver and a scramble file must be given.\n");
42 return 1;
43 }
44
45 solver = argv[1];
46 scrfilename = argv[2];
47
48 srand(time(NULL));
49 nissy_setlogger(log_stderr);
50
51 sprintf(filename, "tables/%s", solver);
52 if (getdata(solver, &buf, filename) != 0)
53 return 1;
54
55 size = nissy_datasize(solver);
56
57 if ((scrfile = fopen(scrfilename, "r")) == NULL) {
58 printf("Error: could not read given file '%s'.\n",
59 scrfilename);
60 return 1;
61 }
62
63 printf("Reading scrambles from file '%s'.\n", scrfilename);
64 for (N = 0; fgets(scrambles[N], MAX_SCR_LEN, scrfile) != NULL; N++) ;
65 fclose(scrfile);
66
67 timerun(run);
68
69 free(buf);
70 return 0;
71}
diff --git a/tools/302_solve_multisol/solve_multisol.c b/tools/302_solve_multisol/solve_multisol.c
new file mode 100644
index 0000000..739ccbd
--- /dev/null
+++ b/tools/302_solve_multisol/solve_multisol.c
@@ -0,0 +1,66 @@
1#include "../tool.h"
2
3#define SOL_BUFFER_LEN 10000
4
5int nsol;
6char *solver;
7int64_t size = 0;
8char *buf;
9
10char *scrambles[] = {
11 "U2 D2 F2 B2 L2 R2",
12 "R' D R U R' D' R U'", /* Pure 8-move comm */
13 "R D' R2 D R U2 R' D' R U2 R D R'", /* 12 mover with sym */
14 NULL
15};
16
17void run(void) {
18 int i;
19 int64_t n;
20 long long stats[NISSY_SIZE_SOLVE_STATS];
21 char sol[SOL_BUFFER_LEN], cube[22];
22
23 printf("Solved the following scrambles:\n\n");
24 for (i = 0; scrambles[i] != NULL; i++) {
25 printf("%d. %s\n", i+1, scrambles[i]);
26 printf("Solving scramble %s\n", scrambles[i]);
27 if (nissy_applymoves(NISSY_SOLVED_CUBE, scrambles[i], cube)
28 == -1) {
29 printf("Invalid scramble\n");
30 continue;
31 }
32 n = nissy_solve(cube, solver, NISSY_NISSFLAG_NORMAL,
33 0, 20, nsol, -1, size, buf, SOL_BUFFER_LEN, sol, stats);
34 if (n == 0)
35 printf("No solution found\n");
36 else
37 printf("Solutions:\n%s\n", sol);
38 }
39}
40
41int main(int argc, char **argv) {
42 char filename[255];
43
44 if (argc < 3) {
45 printf("Error: not enough arguments. "
46 "A solver and a number of solutions must be given.\n");
47 return 1;
48 }
49
50 solver = argv[1];
51 nsol = atoi(argv[2]);
52 srand(time(NULL));
53 nissy_setlogger(log_stderr);
54
55
56 sprintf(filename, "tables/%s", solver);
57 if (getdata(solver, &buf, filename) != 0)
58 return 1;
59
60 size = nissy_datasize(solver);
61
62 timerun(run);
63
64 free(buf);
65 return 0;
66}

Generated with cgit - Back to sebastiano.tronto.net