aboutsummaryrefslogtreecommitdiff
path: root/src/nissy.c
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 /src/nissy.c
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 '')
-rw-r--r--src/nissy.c80
1 files changed, 37 insertions, 43 deletions
diff --git a/src/nissy.c b/src/nissy.c
index c09c99e..f933cab 100644
--- a/src/nissy.c
+++ b/src/nissy.c
@@ -12,12 +12,15 @@
12#include "core/core.h" 12#include "core/core.h"
13#include "solvers/solvers.h" 13#include "solvers/solvers.h"
14 14
15int parse_h48_solver(const char *, uint8_t [static 1], uint8_t [static 1]); 15long long parse_h48_solver(
16 const char *, uint8_t [static 1], uint8_t [static 1]);
16STATIC bool checkdata(const char *, const tableinfo_t *); 17STATIC bool checkdata(const char *, const tableinfo_t *);
17STATIC bool distribution_equal(const uint64_t [static INFO_DISTRIBUTION_LEN], 18STATIC bool distribution_equal(const uint64_t [static INFO_DISTRIBUTION_LEN],
18 const uint64_t [static INFO_DISTRIBUTION_LEN], uint8_t); 19 const uint64_t [static INFO_DISTRIBUTION_LEN], uint8_t);
19STATIC long long write_result(cube_t, char [static NISSY_SIZE_B32]); 20STATIC long long write_result(cube_t, char [static NISSY_SIZE_B32]);
20STATIC size_t my_strnlen(const char *, size_t); 21STATIC size_t my_strnlen(const char *, size_t);
22STATIC long long nissy_gendata_unsafe(
23 const char *, unsigned long long, char *);
21 24
22#define GETCUBE_OPTIONS(S, F) { .option = S, .fix = F } 25#define GETCUBE_OPTIONS(S, F) { .option = S, .fix = F }
23struct { 26struct {
@@ -28,19 +31,13 @@ struct {
28 GETCUBE_OPTIONS(NULL, NULL) 31 GETCUBE_OPTIONS(NULL, NULL)
29}; 32};
30 33
31int 34long long
32parse_h48_solver(const char *buf, uint8_t h[static 1], uint8_t k[static 1]) 35parse_h48_solver(const char *buf, uint8_t h[static 1], uint8_t k[static 1])
33{ 36{
34 const char *fullbuf = buf; 37 const char *fullbuf = buf;
35 38
36 buf += 3; 39 buf += 3;
37 40
38 if (!strcmp(buf, "stats")) {
39 *h = 0;
40 *k = 4;
41 return 0;
42 }
43
44 if (*buf != 'h') 41 if (*buf != 'h')
45 goto parse_h48_solver_error; 42 goto parse_h48_solver_error;
46 buf++; 43 buf++;
@@ -62,9 +59,9 @@ parse_h48_solver(const char *buf, uint8_t h[static 1], uint8_t k[static 1])
62parse_h48_solver_error: 59parse_h48_solver_error:
63 *h = 0; 60 *h = 0;
64 *k = 0; 61 *k = 0;
65 LOG("Error parsing solver: must be in \"h48h*k*\" format" 62 LOG("Error parsing solver: must be in \"h48h*k*\" format,"
66 " or \"h48stats\", but got %s\n", fullbuf); 63 " but got %s\n", fullbuf);
67 return -1; 64 return NISSY_ERROR_INVALID_SOLVER;
68} 65}
69 66
70STATIC bool 67STATIC bool
@@ -360,20 +357,6 @@ nissy_getcube(
360} 357}
361 358
362long long 359long long
363nissy_datasize(
364 const char *solver
365)
366{
367 if (solver == NULL) {
368 LOG("Error: 'solver' argument is NULL\n");
369 return NISSY_ERROR_NULL_POINTER;
370 }
371
372 /* gendata() handles a NULL *data as a "dryrun" request */
373 return nissy_gendata(solver, 0, NULL);
374}
375
376long long
377nissy_datainfo( 360nissy_datainfo(
378 uint64_t data_size, 361 uint64_t data_size,
379 const char data[data_size], 362 const char data[data_size],
@@ -423,13 +406,32 @@ nissy_datainfo(
423} 406}
424 407
425long long 408long long
409nissy_datasize(
410 const char *solver
411)
412{
413 /* gendata() handles a NULL *data as a "dryrun" request */
414 return nissy_gendata_unsafe(solver, 0, NULL);
415}
416
417long long
426nissy_gendata( 418nissy_gendata(
427 const char *solver, 419 const char *solver,
428 unsigned long long data_size, 420 unsigned long long data_size,
429 char data[data_size] 421 char data[data_size]
430) 422)
431{ 423{
432 int p; 424 return nissy_gendata_unsafe(solver, data_size, data);
425}
426
427STATIC long long
428nissy_gendata_unsafe(
429 const char *solver,
430 unsigned long long data_size,
431 char *data
432)
433{
434 long long parse_ret;
433 gendata_h48_arg_t arg; 435 gendata_h48_arg_t arg;
434 436
435 if (solver == NULL) { 437 if (solver == NULL) {
@@ -440,10 +442,10 @@ nissy_gendata(
440 arg.buf_size = data_size; 442 arg.buf_size = data_size;
441 arg.buf = data; 443 arg.buf = data;
442 if (!strncmp(solver, "h48", 3)) { 444 if (!strncmp(solver, "h48", 3)) {
443 p = parse_h48_solver(solver, &arg.h, &arg.k); 445 parse_ret = parse_h48_solver(solver, &arg.h, &arg.k);
444 arg.maxdepth = 20; 446 arg.maxdepth = 20;
445 if (p != 0) 447 if (parse_ret != NISSY_OK)
446 return NISSY_ERROR_UNKNOWN; 448 return parse_ret;
447 return gendata_h48(&arg); 449 return gendata_h48(&arg);
448 } else { 450 } else {
449 LOG("gendata: unknown solver %s\n", solver); 451 LOG("gendata: unknown solver %s\n", solver);
@@ -495,7 +497,7 @@ nissy_solve(
495) 497)
496{ 498{
497 cube_t c; 499 cube_t c;
498 int p; 500 long long parse_ret;
499 uint8_t h, k; 501 uint8_t h, k;
500 502
501 if (solver == NULL) { 503 if (solver == NULL) {
@@ -521,20 +523,12 @@ nissy_solve(
521 } 523 }
522 524
523 if (!strncmp(solver, "h48", 3)) { 525 if (!strncmp(solver, "h48", 3)) {
524 if (!strcmp(solver, "h48stats")) 526 parse_ret = parse_h48_solver(solver, &h, &k);
525 return solve_h48stats(c, maxmoves, data, sols); 527 if (parse_ret == NISSY_OK)
526 528 return solve_h48(c, minmoves, maxmoves, maxsols,
527 p = parse_h48_solver(solver, &h, &k);
528 if (p != 0) {
529 LOG("solve: unknown solver %s\n", solver);
530 return NISSY_ERROR_INVALID_SOLVER;
531 } else {
532 return THREADS > 1 ?
533 solve_h48_multithread(c, minmoves, maxmoves,
534 maxsols, data_size, data, sols_size, sols, stats) :
535 solve_h48(c, minmoves, maxmoves, maxsols,
536 data_size, data, sols_size, sols, stats); 529 data_size, data, sols_size, sols, stats);
537 } 530 else
531 return parse_ret;
538 } else { 532 } else {
539 LOG("solve: unknown solver '%s'\n", solver); 533 LOG("solve: unknown solver '%s'\n", solver);
540 return NISSY_ERROR_INVALID_SOLVER; 534 return NISSY_ERROR_INVALID_SOLVER;

Generated with cgit - Back to sebastiano.tronto.net