From 9ac266c76f39620d8343e46ca41cb09d1534384c Mon Sep 17 00:00:00 2001 From: Sebastiano Tronto Date: Sat, 7 Dec 2024 16:38:40 +0100 Subject: 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 Date: Sat Dec 7 16:06:48 2024 +0100 Fix indentation commit cc5d489a251812b6188c0ba264ac6cb2236f1afe Author: Sebastiano Tronto Date: Sat Dec 7 15:56:19 2024 +0100 Updated documentation commit a3f605dd628546e52564f82b139feb473b0725f3 Author: Sebastiano Tronto Date: Sat Dec 7 14:01:11 2024 +0100 use eoesep table as second fallback commit c75e43c9116c64f97e92b0fe038be8a032925a72 Author: Sebastiano Tronto Date: Fri Dec 6 16:13:23 2024 +0100 First commit for gendata_eoesep commit fea7688ab8bdc5ae0c3480622e2510a3bcd39248 Author: Sebastiano Tronto Date: Tue Dec 3 17:31:00 2024 +0100 Add scramble to tool commit 66866cb71dea4ca8278ecb9e90ff4295771feb42 Author: Sebastiano Tronto Date: Tue Dec 3 17:22:59 2024 +0100 Added tool to check multiple solutions commit ef65611c772c3996bddca8d181da3538e0af1674 Author: Sebastiano Tronto Date: Tue Dec 3 17:16:20 2024 +0100 Write all solutions for symmetric positions commit e3ded26db7d7d4ae7c0e2488151ed14f581f7b8e Author: Sebastiano Tronto Date: Tue Nov 26 09:14:54 2024 +0100 Added symmetry filter (TODO: print excluded solutions) commit 864c437a9751c58d58562650ca9eba4a9e6ad3eb Author: Sebastiano Tronto Date: Mon Nov 25 14:51:13 2024 +0100 Improved task split commit b88926d36d7ab0c64c5fe3bb954fd15d41267fba Author: Sebastiano Tronto Date: Fri Nov 22 19:06:41 2024 +0100 Reworked tasks for multi-threading in view of symmetry filter commit 26fa653f97df8cd601aecb80eaf89f0a00e9ba9f Author: Sebastiano Tronto Date: Thu Oct 31 15:37:43 2024 +0100 Added transform move commit 19f655ef94d658eaa2fefb5cea3c167a3ec58db6 Author: Sebastiano Tronto Date: Thu Oct 31 09:29:15 2024 +0100 Clarified doc commit 3b0fe1e5ef8b628854e30f0f0067300e2763c954 Author: Sebastiano Tronto Date: Thu Oct 31 08:36:58 2024 +0100 Handle solved cube correctly commit 57705cbc4982e3abe97a36ed64871738d4f721c0 Author: Sebastiano Tronto Date: Thu Oct 31 08:24:30 2024 +0100 Close file commit fc7d462b58bcf3d3a3fbf26c1f3bd04c640a4898 Author: Sebastiano Tronto Date: Tue Oct 29 15:05:48 2024 +0100 Removed stats tool commit 359bf7cb49ef405ee76ed662207d47cb2abcc5a9 Author: Sebastiano Tronto Date: Tue Oct 29 15:01:51 2024 +0100 Updated theory doc commit 39c315af562bc4ce896f41004388a4c34d475d37 Author: Sebastiano Tronto Date: Tue Oct 29 14:51:40 2024 +0100 Remove unused constants commit 57a5d24538aa59a4df9221dad2f99e9f0286bd9d Author: Sebastiano Tronto Date: Tue Oct 29 10:20:38 2024 +0100 Add tool to solve scrambles from file commit 07e2918c216636891b1fa6adecc9756086a901e9 Author: Sebastiano Tronto Date: Mon Oct 28 17:00:00 2024 +0100 Add make table to tool commit f5e5266c654eb027a5a35c57cc618555246f5e5e Author: Sebastiano Tronto Date: Mon Oct 28 09:35:49 2024 +0100 Remove old solver, other small things commit a1ec78025b7959dbb845213f7f4e6851ecebc204 Author: Sebastiano Tronto Date: Sun Oct 27 02:00:29 2024 +0200 Improvements commit 8eea23dbe888d923e662e24ae969130e2c67b999 Author: Sebastiano Tronto Date: Sat Oct 26 12:24:19 2024 +0200 Makefile fix commit 3fc3927beacc78971cefeb42da8d71fe6c015fc1 Author: Sebastiano Tronto Date: Fri Oct 25 18:25:09 2024 +0200 More performance gains commit 7b4efa1f9af9722de1ab9ccfc27899825a0d12c4 Author: Sebastiano Tronto Date: Fri Oct 25 15:53:20 2024 +0200 Alternative solver implementation, small performance gain --- test/130_allowednext_h48/00_empty_U.in | 3 -- test/130_allowednext_h48/00_empty_U.out | 1 - test/130_allowednext_h48/01_F.in | 4 --- test/130_allowednext_h48/01_F.out | 1 - test/130_allowednext_h48/02_U2.in | 3 -- test/130_allowednext_h48/02_U2.out | 1 - test/130_allowednext_h48/03_R_L.in | 5 --- test/130_allowednext_h48/03_R_L.out | 1 - test/130_allowednext_h48/04_D.in | 3 -- test/130_allowednext_h48/04_D.out | 1 - test/130_allowednext_h48/05_U_F_B2.in | 5 --- test/130_allowednext_h48/05_U_F_B2.out | 1 - test/130_allowednext_h48/06_empty_bound.in | 2 -- test/130_allowednext_h48/06_empty_bound.out | 1 - test/130_allowednext_h48/07_F_bound.in | 3 -- test/130_allowednext_h48/07_F_bound.out | 1 - test/130_allowednext_h48/08_U_D_bound_inverse.in | 4 --- test/130_allowednext_h48/08_U_D_bound_inverse.out | 1 - test/130_allowednext_h48/09_R_false_bound.in | 3 -- test/130_allowednext_h48/09_R_false_bound.out | 1 - test/130_allowednext_h48/allowednext_h48_tests.c | 38 ----------------------- 21 files changed, 83 deletions(-) delete mode 100644 test/130_allowednext_h48/00_empty_U.in delete mode 100644 test/130_allowednext_h48/00_empty_U.out delete mode 100644 test/130_allowednext_h48/01_F.in delete mode 100644 test/130_allowednext_h48/01_F.out delete mode 100644 test/130_allowednext_h48/02_U2.in delete mode 100644 test/130_allowednext_h48/02_U2.out delete mode 100644 test/130_allowednext_h48/03_R_L.in delete mode 100644 test/130_allowednext_h48/03_R_L.out delete mode 100644 test/130_allowednext_h48/04_D.in delete mode 100644 test/130_allowednext_h48/04_D.out delete mode 100644 test/130_allowednext_h48/05_U_F_B2.in delete mode 100644 test/130_allowednext_h48/05_U_F_B2.out delete mode 100644 test/130_allowednext_h48/06_empty_bound.in delete mode 100644 test/130_allowednext_h48/06_empty_bound.out delete mode 100644 test/130_allowednext_h48/07_F_bound.in delete mode 100644 test/130_allowednext_h48/07_F_bound.out delete mode 100644 test/130_allowednext_h48/08_U_D_bound_inverse.in delete mode 100644 test/130_allowednext_h48/08_U_D_bound_inverse.out delete mode 100644 test/130_allowednext_h48/09_R_false_bound.in delete mode 100644 test/130_allowednext_h48/09_R_false_bound.out delete mode 100644 test/130_allowednext_h48/allowednext_h48_tests.c (limited to 'test/130_allowednext_h48') diff --git a/test/130_allowednext_h48/00_empty_U.in b/test/130_allowednext_h48/00_empty_U.in deleted file mode 100644 index 28271a6..0000000 --- a/test/130_allowednext_h48/00_empty_U.in +++ /dev/null @@ -1,3 +0,0 @@ -0 -0 - diff --git a/test/130_allowednext_h48/00_empty_U.out b/test/130_allowednext_h48/00_empty_U.out deleted file mode 100644 index 8607955..0000000 --- a/test/130_allowednext_h48/00_empty_U.out +++ /dev/null @@ -1 +0,0 @@ -0x3FFFF diff --git a/test/130_allowednext_h48/01_F.in b/test/130_allowednext_h48/01_F.in deleted file mode 100644 index e7ae375..0000000 --- a/test/130_allowednext_h48/01_F.in +++ /dev/null @@ -1,4 +0,0 @@ -0 -1 -F - diff --git a/test/130_allowednext_h48/01_F.out b/test/130_allowednext_h48/01_F.out deleted file mode 100644 index 5d6f843..0000000 --- a/test/130_allowednext_h48/01_F.out +++ /dev/null @@ -1 +0,0 @@ -0x38FFF diff --git a/test/130_allowednext_h48/02_U2.in b/test/130_allowednext_h48/02_U2.in deleted file mode 100644 index 2c5ee5f..0000000 --- a/test/130_allowednext_h48/02_U2.in +++ /dev/null @@ -1,3 +0,0 @@ -0 -1 -U diff --git a/test/130_allowednext_h48/02_U2.out b/test/130_allowednext_h48/02_U2.out deleted file mode 100644 index a9a5adb..0000000 --- a/test/130_allowednext_h48/02_U2.out +++ /dev/null @@ -1 +0,0 @@ -0x3FFF8 diff --git a/test/130_allowednext_h48/03_R_L.in b/test/130_allowednext_h48/03_R_L.in deleted file mode 100644 index b6c0625..0000000 --- a/test/130_allowednext_h48/03_R_L.in +++ /dev/null @@ -1,5 +0,0 @@ -0 -2 -R -L' - diff --git a/test/130_allowednext_h48/03_R_L.out b/test/130_allowednext_h48/03_R_L.out deleted file mode 100644 index a4aa4b2..0000000 --- a/test/130_allowednext_h48/03_R_L.out +++ /dev/null @@ -1 +0,0 @@ -0x3F03F diff --git a/test/130_allowednext_h48/04_D.in b/test/130_allowednext_h48/04_D.in deleted file mode 100644 index 83da556..0000000 --- a/test/130_allowednext_h48/04_D.in +++ /dev/null @@ -1,3 +0,0 @@ -0 -1 -D diff --git a/test/130_allowednext_h48/04_D.out b/test/130_allowednext_h48/04_D.out deleted file mode 100644 index fe91843..0000000 --- a/test/130_allowednext_h48/04_D.out +++ /dev/null @@ -1 +0,0 @@ -0x3FFC0 diff --git a/test/130_allowednext_h48/05_U_F_B2.in b/test/130_allowednext_h48/05_U_F_B2.in deleted file mode 100644 index 67e090f..0000000 --- a/test/130_allowednext_h48/05_U_F_B2.in +++ /dev/null @@ -1,5 +0,0 @@ -0 -2 -U -F - diff --git a/test/130_allowednext_h48/05_U_F_B2.out b/test/130_allowednext_h48/05_U_F_B2.out deleted file mode 100644 index 5d6f843..0000000 --- a/test/130_allowednext_h48/05_U_F_B2.out +++ /dev/null @@ -1 +0,0 @@ -0x38FFF diff --git a/test/130_allowednext_h48/06_empty_bound.in b/test/130_allowednext_h48/06_empty_bound.in deleted file mode 100644 index 389e262..0000000 --- a/test/130_allowednext_h48/06_empty_bound.in +++ /dev/null @@ -1,2 +0,0 @@ -2 -0 diff --git a/test/130_allowednext_h48/06_empty_bound.out b/test/130_allowednext_h48/06_empty_bound.out deleted file mode 100644 index eb601fc..0000000 --- a/test/130_allowednext_h48/06_empty_bound.out +++ /dev/null @@ -1 +0,0 @@ -0x2DB6D diff --git a/test/130_allowednext_h48/07_F_bound.in b/test/130_allowednext_h48/07_F_bound.in deleted file mode 100644 index b3ae33d..0000000 --- a/test/130_allowednext_h48/07_F_bound.in +++ /dev/null @@ -1,3 +0,0 @@ -2 -1 -F diff --git a/test/130_allowednext_h48/07_F_bound.out b/test/130_allowednext_h48/07_F_bound.out deleted file mode 100644 index 0dc8997..0000000 --- a/test/130_allowednext_h48/07_F_bound.out +++ /dev/null @@ -1 +0,0 @@ -0x28B6D diff --git a/test/130_allowednext_h48/08_U_D_bound_inverse.in b/test/130_allowednext_h48/08_U_D_bound_inverse.in deleted file mode 100644 index 707f7e0..0000000 --- a/test/130_allowednext_h48/08_U_D_bound_inverse.in +++ /dev/null @@ -1,4 +0,0 @@ -3 -2 -U -D2 \ No newline at end of file diff --git a/test/130_allowednext_h48/08_U_D_bound_inverse.out b/test/130_allowednext_h48/08_U_D_bound_inverse.out deleted file mode 100644 index 6f47cf0..0000000 --- a/test/130_allowednext_h48/08_U_D_bound_inverse.out +++ /dev/null @@ -1 +0,0 @@ -0x2DB40 diff --git a/test/130_allowednext_h48/09_R_false_bound.in b/test/130_allowednext_h48/09_R_false_bound.in deleted file mode 100644 index 0b1d441..0000000 --- a/test/130_allowednext_h48/09_R_false_bound.in +++ /dev/null @@ -1,3 +0,0 @@ -1 -1 -R \ No newline at end of file diff --git a/test/130_allowednext_h48/09_R_false_bound.out b/test/130_allowednext_h48/09_R_false_bound.out deleted file mode 100644 index 121bfeb..0000000 --- a/test/130_allowednext_h48/09_R_false_bound.out +++ /dev/null @@ -1 +0,0 @@ -0x3FE3F diff --git a/test/130_allowednext_h48/allowednext_h48_tests.c b/test/130_allowednext_h48/allowednext_h48_tests.c deleted file mode 100644 index 64ded35..0000000 --- a/test/130_allowednext_h48/allowednext_h48_tests.c +++ /dev/null @@ -1,38 +0,0 @@ -#include "../test.h" - -uint32_t allowednextmove_h48(uint8_t *, uint8_t, uint32_t); - -static char *moves[] = { - "U", "U2", "U'", - "D", "D2", "D'", - "R", "R2", "R'", - "L", "L2", "L'", - "F", "F2", "F'", - "B", "B2", "B'", -}; - -void run(void) { - char movestr[STRLENMAX]; - uint8_t m[100]; - int n, i, j, bound; - - fgets(movestr, STRLENMAX, stdin); - bound = atoi(movestr); - - fgets(movestr, STRLENMAX, stdin); - n = atoi(movestr); - - for (i = 0; i < n; i++) { - fgets(movestr, STRLENMAX, stdin); - movestr[strcspn(movestr, "\n")] = 0; - for (j = 0; j < 18; j++) - if (!strcmp(movestr, moves[j])) - m[i] = j; - } - - fprintf(stderr, "Last two: %s, %s\n", - n > 1 ? moves[m[n-2]] : "-", - n > 0 ? moves[m[n-1]] : "-"); - uint32_t allowed = allowednextmove_h48(m, n, bound); - printf("0x%05X\n", allowed); -} -- cgit v1.3