nissy

Where is nissy?
git clone https://git.tronto.net/nissy
Download | Log | Files | Refs | README

commit bf44088d4373a9520e860152c56a958332819c4b
parent 1a5bfe9b08707b0aef748d7921a419ba4a046fba
Author: Sebastiano Tronto <sebastiano@tronto.net>
Date:   Mon,  1 May 2023 16:33:51 +0200

Split nissy in other repos, see README.md

Diffstat:
D.gitignore | 5-----
DINSTALL | 81-------------------------------------------------------------------------------
DLICENSE | 636-------------------------------------------------------------------------------
DMakefile | 68--------------------------------------------------------------------
MREADME.md | 130+++++++++++++++++++++++--------------------------------------------------------
DTODO/2.1.md | 51---------------------------------------------------
DTODO/build-options.md | 33---------------------------------
DTODO/documentation.md | 41-----------------------------------------
DTODO/easy.md | 16----------------
DTODO/installation.md | 14--------------
DTODO/new-feature-ideas.md | 32--------------------------------
DTODO/parser.md | 13-------------
DTODO/refactoring.md | 28----------------------------
DTODO/testing.md | 6------
DTODO/webapp.md | 19-------------------
Ddoc/nissy.1 | 271-------------------------------------------------------------------------------
Dold/maybe-useful-coord.c | 181-------------------------------------------------------------------------------
Dold/maybe-useful-steps.c | 1111-------------------------------------------------------------------------------
Dold/solve_old.c | 447-------------------------------------------------------------------------------
Dold/solve_old.h | 9---------
Dsrc/alg.c | 459-------------------------------------------------------------------------------
Dsrc/alg.h | 35-----------------------------------
Dsrc/commands.c | 569-------------------------------------------------------------------------------
Dsrc/commands.h | 211-------------------------------------------------------------------------------
Dsrc/coord.c | 654-------------------------------------------------------------------------------
Dsrc/coord.h | 259-------------------------------------------------------------------------------
Dsrc/cube.c | 270-------------------------------------------------------------------------------
Dsrc/cube.h | 35-----------------------------------
Dsrc/cubetypes.h | 360-------------------------------------------------------------------------------
Dsrc/env.c | 60------------------------------------------------------------
Dsrc/env.h | 15---------------
Dsrc/fst.c | 401-------------------------------------------------------------------------------
Dsrc/fst.h | 13-------------
Dsrc/moves.c | 301-------------------------------------------------------------------------------
Dsrc/moves.h | 17-----------------
Dsrc/movesets.c | 194-------------------------------------------------------------------------------
Dsrc/movesets.h | 15---------------
Dsrc/pruning.c | 400-------------------------------------------------------------------------------
Dsrc/pruning.h | 16----------------
Dsrc/shell.c | 177-------------------------------------------------------------------------------
Dsrc/shell.h | 14--------------
Dsrc/solve.c | 122-------------------------------------------------------------------------------
Dsrc/solve.h | 54------------------------------------------------------
Dsrc/solver_step.c | 306-------------------------------------------------------------------------------
Dsrc/solver_step.h | 12------------
Dsrc/steps.c | 177-------------------------------------------------------------------------------
Dsrc/steps.h | 244-------------------------------------------------------------------------------
Dsrc/threader_eager.c | 163-------------------------------------------------------------------------------
Dsrc/threader_eager.h | 8--------
Dsrc/threader_single.c | 35-----------------------------------
Dsrc/threader_single.h | 8--------
Dsrc/trans.c | 190-------------------------------------------------------------------------------
Dsrc/trans.h | 32--------------------------------
Dsrc/utils.c | 290-------------------------------------------------------------------------------
Dsrc/utils.h | 43-------------------------------------------
Dtests/alg_tests.c | 266-------------------------------------------------------------------------------
Dtests/alg_tests.h | 21---------------------
Dtests/coord_tests.c | 50--------------------------------------------------
Dtests/coord_tests.h | 13-------------
Dtests/fst_tests.c | 184-------------------------------------------------------------------------------
Dtests/fst_tests.h | 19-------------------
Dtests/test.c | 85-------------------------------------------------------------------------------
Dtests/test_common.h | 41-----------------------------------------
Dwww/download/index.html | 217-------------------------------------------------------------------------------
Dwww/examples/index.html | 49-------------------------------------------------
Dwww/favicon.png | 0
Dwww/index.html | 93-------------------------------------------------------------------------------
Dwww/screenshot.png | 0
Dwww/style-3.css | 105-------------------------------------------------------------------------------
69 files changed, 38 insertions(+), 10456 deletions(-)

diff --git a/.gitignore b/.gitignore @@ -1,5 +0,0 @@ -doc/*.html -doc/*.pdf -nissy -nissy-* -test diff --git a/INSTALL b/INSTALL @@ -1,81 +0,0 @@ -# Website - -Nissy is available at https://nissy.tronto.net - -# Requirements - -A full installation of nissy requires about 3Gb of space, of which -2.3Gb are occupied by the huge pruning table for fast optimal solving, -and running it requires the same amount of RAM. One can choose to never -use this function and not to install the relative pruning table. There -is an alternative (slower) optimal solving function that uses about -500Mb of RAM. When generating the pruning tables automatically (see -the section Tables below), at least 5.3Gb or RAM are required. - -# Installation - -## On Windows - -Try downloading and executing in a terminal the file nissy.exe, then -follow the instructions in the Tables section below for installing the -pruning tables. If nissy.exe does not work, you can try following the -UNIX instructions in WSL (Windows Subsystem for Linux) or in a similar -environment. - -## On a UNIX system: - -Download the source archive (.tar.gz). Extract it with your favorite -archive program, for example with - - tar -xvzf nissy-VERSION.tar.gz - -Open a terminal in the directory just extracted. If you wish, edit the -Makefile to match your local configuration (this is usually not necessary, -but you may want to change the PREFIX variable to change the installation -path) and run - - make - -followed by - - make install - -Then follow the instructions below to install the pruning tables. - -## Tables - -Once you have installed nissy, run - - nissy gen - -to generate all the tables that Nissy will ever need. Running this -command requires around 5.3Gb of RAM, and it can take some time (about -40 minutes on my fairly old but decent laptop, with 8 CPU threads). - -Some unnecessary technical detail: by default this command is going to -use at most 64 threads. If you want you can choose to use more threads -(if your CPU is very powerful) or fewer threads (if you for example -want to run this command in the background while you do other stuff) -with the -t option, for example nissy gen -t 1. - -Alternatively, you can download all the tables (1.7Gb) and copy them -into the correct folder (see manual page, ENVIRONMENT section). On UNIX -operating systems this folder is either .nissy/tables in the user's -home directory or $XDG_DATA_HOME/nissy/tables if the XDG variable -is configured. On Windows it is the same directory as the nissy.exe -executable file. - -You can downloads all the tables from the following link: - - https://nissy.tronto.net/nissy-tables-2.0.2.zip - -# Upgrading - -If you already have nissy installed and you want to upgrade to a more -recent version, you can simply repeat the installation process: -* On Windows: simply replace nissy.exe with the new file with the same name. -* On UNIX systems: download the new version of the source code, extract it - in a new folder and run make and make install again. - -Between each version new table files might have been added, or old ones -may be not used anymore. Nissy will deal with this automatically. diff --git a/LICENSE b/LICENSE @@ -1,636 +0,0 @@ -The following license applies to every C source code and header file -distributed with this LICENSE file. - - Nissy - A Rubik's cube solver and FMC assistant - Copyright (C) 2020-2022 Sebastiano Tronto <sebastiano@tronto.net> - - This program is free software: you can redistribute it and/or modify - it under the terms of the GNU General Public License as published by - the Free Software Foundation, either version 3 of the License, or - (at your option) any later version. - - This program is distributed in the hope that it will be useful, - but WITHOUT ANY WARRANTY; without even the implied warranty of - MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - GNU General Public License for more details. - - - GNU GENERAL PUBLIC LICENSE - Version 3, 29 June 2007 - - Copyright (C) 2007 Free Software Foundation, Inc. <https://fsf.org/> - Everyone is permitted to copy and distribute verbatim copies - of this license document, but changing it is not allowed. - - Preamble - - The GNU General Public License is a free, copyleft license for -software and other kinds of works. - - The licenses for most software and other practical works are designed -to take away your freedom to share and change the works. By contrast, -the GNU General Public License is intended to guarantee your freedom to -share and change all versions of a program--to make sure it remains free -software for all its users. We, the Free Software Foundation, use the -GNU General Public License for most of our software; it applies also to -any other work released this way by its authors. You can apply it to -your programs, too. - - When we speak of free software, we are referring to freedom, not -price. Our General Public Licenses are designed to make sure that you -have the freedom to distribute copies of free software (and charge for -them if you wish), that you receive source code or can get it if you -want it, that you can change the software or use pieces of it in new -free programs, and that you know you can do these things. - - To protect your rights, we need to prevent others from denying you -these rights or asking you to surrender the rights. Therefore, you have -certain responsibilities if you distribute copies of the software, or if -you modify it: responsibilities to respect the freedom of others. - - For example, if you distribute copies of such a program, whether -gratis or for a fee, you must pass on to the recipients the same -freedoms that you received. You must make sure that they, too, receive -or can get the source code. And you must show them these terms so they -know their rights. - - Developers that use the GNU GPL protect your rights with two steps: -(1) assert copyright on the software, and (2) offer you this License -giving you legal permission to copy, distribute and/or modify it. - - For the developers' and authors' protection, the GPL clearly explains -that there is no warranty for this free software. For both users' and -authors' sake, the GPL requires that modified versions be marked as -changed, so that their problems will not be attributed erroneously to -authors of previous versions. - - Some devices are designed to deny users access to install or run -modified versions of the software inside them, although the manufacturer -can do so. This is fundamentally incompatible with the aim of -protecting users' freedom to change the software. The systematic -pattern of such abuse occurs in the area of products for individuals to -use, which is precisely where it is most unacceptable. Therefore, we -have designed this version of the GPL to prohibit the practice for those -products. If such problems arise substantially in other domains, we -stand ready to extend this provision to those domains in future versions -of the GPL, as needed to protect the freedom of users. - - Finally, every program is threatened constantly by software patents. -States should not allow patents to restrict development and use of -software on general-purpose computers, but in those that do, we wish to -avoid the special danger that patents applied to a free program could -make it effectively proprietary. To prevent this, the GPL assures that -patents cannot be used to render the program non-free. - - The precise terms and conditions for copying, distribution and -modification follow. - - TERMS AND CONDITIONS - - 0. Definitions. - - "This License" refers to version 3 of the GNU General Public License. - - "Copyright" also means copyright-like laws that apply to other kinds of -works, such as semiconductor masks. - - "The Program" refers to any copyrightable work licensed under this -License. Each licensee is addressed as "you". "Licensees" and -"recipients" may be individuals or organizations. - - To "modify" a work means to copy from or adapt all or part of the work -in a fashion requiring copyright permission, other than the making of an -exact copy. The resulting work is called a "modified version" of the -earlier work or a work "based on" the earlier work. - - A "covered work" means either the unmodified Program or a work based -on the Program. - - To "propagate" a work means to do anything with it that, without -permission, would make you directly or secondarily liable for -infringement under applicable copyright law, except executing it on a -computer or modifying a private copy. Propagation includes copying, -distribution (with or without modification), making available to the -public, and in some countries other activities as well. - - To "convey" a work means any kind of propagation that enables other -parties to make or receive copies. Mere interaction with a user through -a computer network, with no transfer of a copy, is not conveying. - - An interactive user interface displays "Appropriate Legal Notices" -to the extent that it includes a convenient and prominently visible -feature that (1) displays an appropriate copyright notice, and (2) -tells the user that there is no warranty for the work (except to the -extent that warranties are provided), that licensees may convey the -work under this License, and how to view a copy of this License. If -the interface presents a list of user commands or options, such as a -menu, a prominent item in the list meets this criterion. - - 1. Source Code. - - The "source code" for a work means the preferred form of the work -for making modifications to it. "Object code" means any non-source -form of a work. - - A "Standard Interface" means an interface that either is an official -standard defined by a recognized standards body, or, in the case of -interfaces specified for a particular programming language, one that -is widely used among developers working in that language. - - The "System Libraries" of an executable work include anything, other -than the work as a whole, that (a) is included in the normal form of -packaging a Major Component, but which is not part of that Major -Component, and (b) serves only to enable use of the work with that -Major Component, or to implement a Standard Interface for which an -implementation is available to the public in source code form. A -"Major Component", in this context, means a major essential component -(kernel, window system, and so on) of the specific operating system -(if any) on which the executable work runs, or a compiler used to -produce the work, or an object code interpreter used to run it. - - The "Corresponding Source" for a work in object code form means all -the source code needed to generate, install, and (for an executable -work) run the object code and to modify the work, including scripts to -control those activities. However, it does not include the work's -System Libraries, or general-purpose tools or generally available free -programs which are used unmodified in performing those activities but -which are not part of the work. For example, Corresponding Source -includes interface definition files associated with source files for -the work, and the source code for shared libraries and dynamically -linked subprograms that the work is specifically designed to require, -such as by intimate data communication or control flow between those -subprograms and other parts of the work. - - The Corresponding Source need not include anything that users -can regenerate automatically from other parts of the Corresponding -Source. - - The Corresponding Source for a work in source code form is that -same work. - - 2. Basic Permissions. - - All rights granted under this License are granted for the term of -copyright on the Program, and are irrevocable provided the stated -conditions are met. This License explicitly affirms your unlimited -permission to run the unmodified Program. The output from running a -covered work is covered by this License only if the output, given its -content, constitutes a covered work. This License acknowledges your -rights of fair use or other equivalent, as provided by copyright law. - - You may make, run and propagate covered works that you do not -convey, without conditions so long as your license otherwise remains -in force. You may convey covered works to others for the sole purpose -of having them make modifications exclusively for you, or provide you -with facilities for running those works, provided that you comply with -the terms of this License in conveying all material for which you do -not control copyright. Those thus making or running the covered works -for you must do so exclusively on your behalf, under your direction -and control, on terms that prohibit them from making any copies of -your copyrighted material outside their relationship with you. - - Conveying under any other circumstances is permitted solely under -the conditions stated below. Sublicensing is not allowed; section 10 -makes it unnecessary. - - 3. Protecting Users' Legal Rights From Anti-Circumvention Law. - - No covered work shall be deemed part of an effective technological -measure under any applicable law fulfilling obligations under article -11 of the WIPO copyright treaty adopted on 20 December 1996, or -similar laws prohibiting or restricting circumvention of such -measures. - - When you convey a covered work, you waive any legal power to forbid -circumvention of technological measures to the extent such circumvention -is effected by exercising rights under this License with respect to -the covered work, and you disclaim any intention to limit operation or -modification of the work as a means of enforcing, against the work's -users, your or third parties' legal rights to forbid circumvention of -technological measures. - - 4. Conveying Verbatim Copies. - - You may convey verbatim copies of the Program's source code as you -receive it, in any medium, provided that you conspicuously and -appropriately publish on each copy an appropriate copyright notice; -keep intact all notices stating that this License and any -non-permissive terms added in accord with section 7 apply to the code; -keep intact all notices of the absence of any warranty; and give all -recipients a copy of this License along with the Program. - - You may charge any price or no price for each copy that you convey, -and you may offer support or warranty protection for a fee. - - 5. Conveying Modified Source Versions. - - You may convey a work based on the Program, or the modifications to -produce it from the Program, in the form of source code under the -terms of section 4, provided that you also meet all of these conditions: - - a) The work must carry prominent notices stating that you modified - it, and giving a relevant date. - - b) The work must carry prominent notices stating that it is - released under this License and any conditions added under section - 7. This requirement modifies the requirement in section 4 to - "keep intact all notices". - - c) You must license the entire work, as a whole, under this - License to anyone who comes into possession of a copy. This - License will therefore apply, along with any applicable section 7 - additional terms, to the whole of the work, and all its parts, - regardless of how they are packaged. This License gives no - permission to license the work in any other way, but it does not - invalidate such permission if you have separately received it. - - d) If the work has interactive user interfaces, each must display - Appropriate Legal Notices; however, if the Program has interactive - interfaces that do not display Appropriate Legal Notices, your - work need not make them do so. - - A compilation of a covered work with other separate and independent -works, which are not by their nature extensions of the covered work, -and which are not combined with it such as to form a larger program, -in or on a volume of a storage or distribution medium, is called an -"aggregate" if the compilation and its resulting copyright are not -used to limit the access or legal rights of the compilation's users -beyond what the individual works permit. Inclusion of a covered work -in an aggregate does not cause this License to apply to the other -parts of the aggregate. - - 6. Conveying Non-Source Forms. - - You may convey a covered work in object code form under the terms -of sections 4 and 5, provided that you also convey the -machine-readable Corresponding Source under the terms of this License, -in one of these ways: - - a) Convey the object code in, or embodied in, a physical product - (including a physical distribution medium), accompanied by the - Corresponding Source fixed on a durable physical medium - customarily used for software interchange. - - b) Convey the object code in, or embodied in, a physical product - (including a physical distribution medium), accompanied by a - written offer, valid for at least three years and valid for as - long as you offer spare parts or customer support for that product - model, to give anyone who possesses the object code either (1) a - copy of the Corresponding Source for all the software in the - product that is covered by this License, on a durable physical - medium customarily used for software interchange, for a price no - more than your reasonable cost of physically performing this - conveying of source, or (2) access to copy the - Corresponding Source from a network server at no charge. - - c) Convey individual copies of the object code with a copy of the - written offer to provide the Corresponding Source. This - alternative is allowed only occasionally and noncommercially, and - only if you received the object code with such an offer, in accord - with subsection 6b. - - d) Convey the object code by offering access from a designated - place (gratis or for a charge), and offer equivalent access to the - Corresponding Source in the same way through the same place at no - further charge. You need not require recipients to copy the - Corresponding Source along with the object code. If the place to - copy the object code is a network server, the Corresponding Source - may be on a different server (operated by you or a third party) - that supports equivalent copying facilities, provided you maintain - clear directions next to the object code saying where to find the - Corresponding Source. Regardless of what server hosts the - Corresponding Source, you remain obligated to ensure that it is - available for as long as needed to satisfy these requirements. - - e) Convey the object code using peer-to-peer transmission, provided - you inform other peers where the object code and Corresponding - Source of the work are being offered to the general public at no - charge under subsection 6d. - - A separable portion of the object code, whose source code is excluded -from the Corresponding Source as a System Library, need not be -included in conveying the object code work. - - A "User Product" is either (1) a "consumer product", which means any -tangible personal property which is normally used for personal, family, -or household purposes, or (2) anything designed or sold for incorporation -into a dwelling. In determining whether a product is a consumer product, -doubtful cases shall be resolved in favor of coverage. For a particular -product received by a particular user, "normally used" refers to a -typical or common use of that class of product, regardless of the status -of the particular user or of the way in which the particular user -actually uses, or expects or is expected to use, the product. A product -is a consumer product regardless of whether the product has substantial -commercial, industrial or non-consumer uses, unless such uses represent -the only significant mode of use of the product. - - "Installation Information" for a User Product means any methods, -procedures, authorization keys, or other information required to install -and execute modified versions of a covered work in that User Product from -a modified version of its Corresponding Source. The information must -suffice to ensure that the continued functioning of the modified object -code is in no case prevented or interfered with solely because -modification has been made. - - If you convey an object code work under this section in, or with, or -specifically for use in, a User Product, and the conveying occurs as -part of a transaction in which the right of possession and use of the -User Product is transferred to the recipient in perpetuity or for a -fixed term (regardless of how the transaction is characterized), the -Corresponding Source conveyed under this section must be accompanied -by the Installation Information. But this requirement does not apply -if neither you nor any third party retains the ability to install -modified object code on the User Product (for example, the work has -been installed in ROM). - - The requirement to provide Installation Information does not include a -requirement to continue to provide support service, warranty, or updates -for a work that has been modified or installed by the recipient, or for -the User Product in which it has been modified or installed. Access to a -network may be denied when the modification itself materially and -adversely affects the operation of the network or violates the rules and -protocols for communication across the network. - - Corresponding Source conveyed, and Installation Information provided, -in accord with this section must be in a format that is publicly -documented (and with an implementation available to the public in -source code form), and must require no special password or key for -unpacking, reading or copying. - - 7. Additional Terms. - - "Additional permissions" are terms that supplement the terms of this -License by making exceptions from one or more of its conditions. -Additional permissions that are applicable to the entire Program shall -be treated as though they were included in this License, to the extent -that they are valid under applicable law. If additional permissions -apply only to part of the Program, that part may be used separately -under those permissions, but the entire Program remains governed by -this License without regard to the additional permissions. - - When you convey a copy of a covered work, you may at your option -remove any additional permissions from that copy, or from any part of -it. (Additional permissions may be written to require their own -removal in certain cases when you modify the work.) You may place -additional permissions on material, added by you to a covered work, -for which you have or can give appropriate copyright permission. - - Notwithstanding any other provision of this License, for material you -add to a covered work, you may (if authorized by the copyright holders of -that material) supplement the terms of this License with terms: - - a) Disclaiming warranty or limiting liability differently from the - terms of sections 15 and 16 of this License; or - - b) Requiring preservation of specified reasonable legal notices or - author attributions in that material or in the Appropriate Legal - Notices displayed by works containing it; or - - c) Prohibiting misrepresentation of the origin of that material, or - requiring that modified versions of such material be marked in - reasonable ways as different from the original version; or - - d) Limiting the use for publicity purposes of names of licensors or - authors of the material; or - - e) Declining to grant rights under trademark law for use of some - trade names, trademarks, or service marks; or - - f) Requiring indemnification of licensors and authors of that - material by anyone who conveys the material (or modified versions of - it) with contractual assumptions of liability to the recipient, for - any liability that these contractual assumptions directly impose on - those licensors and authors. - - All other non-permissive additional terms are considered "further -restrictions" within the meaning of section 10. If the Program as you -received it, or any part of it, contains a notice stating that it is -governed by this License along with a term that is a further -restriction, you may remove that term. If a license document contains -a further restriction but permits relicensing or conveying under this -License, you may add to a covered work material governed by the terms -of that license document, provided that the further restriction does -not survive such relicensing or conveying. - - If you add terms to a covered work in accord with this section, you -must place, in the relevant source files, a statement of the -additional terms that apply to those files, or a notice indicating -where to find the applicable terms. - - Additional terms, permissive or non-permissive, may be stated in the -form of a separately written license, or stated as exceptions; -the above requirements apply either way. - - 8. Termination. - - You may not propagate or modify a covered work except as expressly -provided under this License. Any attempt otherwise to propagate or -modify it is void, and will automatically terminate your rights under -this License (including any patent licenses granted under the third -paragraph of section 11). - - However, if you cease all violation of this License, then your -license from a particular copyright holder is reinstated (a) -provisionally, unless and until the copyright holder explicitly and -finally terminates your license, and (b) permanently, if the copyright -holder fails to notify you of the violation by some reasonable means -prior to 60 days after the cessation. - - Moreover, your license from a particular copyright holder is -reinstated permanently if the copyright holder notifies you of the -violation by some reasonable means, this is the first time you have -received notice of violation of this License (for any work) from that -copyright holder, and you cure the violation prior to 30 days after -your receipt of the notice. - - Termination of your rights under this section does not terminate the -licenses of parties who have received copies or rights from you under -this License. If your rights have been terminated and not permanently -reinstated, you do not qualify to receive new licenses for the same -material under section 10. - - 9. Acceptance Not Required for Having Copies. - - You are not required to accept this License in order to receive or -run a copy of the Program. Ancillary propagation of a covered work -occurring solely as a consequence of using peer-to-peer transmission -to receive a copy likewise does not require acceptance. However, -nothing other than this License grants you permission to propagate or -modify any covered work. These actions infringe copyright if you do -not accept this License. Therefore, by modifying or propagating a -covered work, you indicate your acceptance of this License to do so. - - 10. Automatic Licensing of Downstream Recipients. - - Each time you convey a covered work, the recipient automatically -receives a license from the original licensors, to run, modify and -propagate that work, subject to this License. You are not responsible -for enforcing compliance by third parties with this License. - - An "entity transaction" is a transaction transferring control of an -organization, or substantially all assets of one, or subdividing an -organization, or merging organizations. If propagation of a covered -work results from an entity transaction, each party to that -transaction who receives a copy of the work also receives whatever -licenses to the work the party's predecessor in interest had or could -give under the previous paragraph, plus a right to possession of the -Corresponding Source of the work from the predecessor in interest, if -the predecessor has it or can get it with reasonable efforts. - - You may not impose any further restrictions on the exercise of the -rights granted or affirmed under this License. For example, you may -not impose a license fee, royalty, or other charge for exercise of -rights granted under this License, and you may not initiate litigation -(including a cross-claim or counterclaim in a lawsuit) alleging that -any patent claim is infringed by making, using, selling, offering for -sale, or importing the Program or any portion of it. - - 11. Patents. - - A "contributor" is a copyright holder who authorizes use under this -License of the Program or a work on which the Program is based. The -work thus licensed is called the contributor's "contributor version". - - A contributor's "essential patent claims" are all patent claims -owned or controlled by the contributor, whether already acquired or -hereafter acquired, that would be infringed by some manner, permitted -by this License, of making, using, or selling its contributor version, -but do not include claims that would be infringed only as a -consequence of further modification of the contributor version. For -purposes of this definition, "control" includes the right to grant -patent sublicenses in a manner consistent with the requirements of -this License. - - Each contributor grants you a non-exclusive, worldwide, royalty-free -patent license under the contributor's essential patent claims, to -make, use, sell, offer for sale, import and otherwise run, modify and -propagate the contents of its contributor version. - - In the following three paragraphs, a "patent license" is any express -agreement or commitment, however denominated, not to enforce a patent -(such as an express permission to practice a patent or covenant not to -sue for patent infringement). To "grant" such a patent license to a -party means to make such an agreement or commitment not to enforce a -patent against the party. - - If you convey a covered work, knowingly relying on a patent license, -and the Corresponding Source of the work is not available for anyone -to copy, free of charge and under the terms of this License, through a -publicly available network server or other readily accessible means, -then you must either (1) cause the Corresponding Source to be so -available, or (2) arrange to deprive yourself of the benefit of the -patent license for this particular work, or (3) arrange, in a manner -consistent with the requirements of this License, to extend the patent -license to downstream recipients. "Knowingly relying" means you have -actual knowledge that, but for the patent license, your conveying the -covered work in a country, or your recipient's use of the covered work -in a country, would infringe one or more identifiable patents in that -country that you have reason to believe are valid. - - If, pursuant to or in connection with a single transaction or -arrangement, you convey, or propagate by procuring conveyance of, a -covered work, and grant a patent license to some of the parties -receiving the covered work authorizing them to use, propagate, modify -or convey a specific copy of the covered work, then the patent license -you grant is automatically extended to all recipients of the covered -work and works based on it. - - A patent license is "discriminatory" if it does not include within -the scope of its coverage, prohibits the exercise of, or is -conditioned on the non-exercise of one or more of the rights that are -specifically granted under this License. You may not convey a covered -work if you are a party to an arrangement with a third party that is -in the business of distributing software, under which you make payment -to the third party based on the extent of your activity of conveying -the work, and under which the third party grants, to any of the -parties who would receive the covered work from you, a discriminatory -patent license (a) in connection with copies of the covered work -conveyed by you (or copies made from those copies), or (b) primarily -for and in connection with specific products or compilations that -contain the covered work, unless you entered into that arrangement, -or that patent license was granted, prior to 28 March 2007. - - Nothing in this License shall be construed as excluding or limiting -any implied license or other defenses to infringement that may -otherwise be available to you under applicable patent law. - - 12. No Surrender of Others' Freedom. - - If conditions are imposed on you (whether by court order, agreement or -otherwise) that contradict the conditions of this License, they do not -excuse you from the conditions of this License. If you cannot convey a -covered work so as to satisfy simultaneously your obligations under this -License and any other pertinent obligations, then as a consequence you may -not convey it at all. For example, if you agree to terms that obligate you -to collect a royalty for further conveying from those to whom you convey -the Program, the only way you could satisfy both those terms and this -License would be to refrain entirely from conveying the Program. - - 13. Use with the GNU Affero General Public License. - - Notwithstanding any other provision of this License, you have -permission to link or combine any covered work with a work licensed -under version 3 of the GNU Affero General Public License into a single -combined work, and to convey the resulting work. The terms of this -License will continue to apply to the part which is the covered work, -but the special requirements of the GNU Affero General Public License, -section 13, concerning interaction through a network will apply to the -combination as such. - - 14. Revised Versions of this License. - - The Free Software Foundation may publish revised and/or new versions of -the GNU General Public License from time to time. Such new versions will -be similar in spirit to the present version, but may differ in detail to -address new problems or concerns. - - Each version is given a distinguishing version number. If the -Program specifies that a certain numbered version of the GNU General -Public License "or any later version" applies to it, you have the -option of following the terms and conditions either of that numbered -version or of any later version published by the Free Software -Foundation. If the Program does not specify a version number of the -GNU General Public License, you may choose any version ever published -by the Free Software Foundation. - - If the Program specifies that a proxy can decide which future -versions of the GNU General Public License can be used, that proxy's -public statement of acceptance of a version permanently authorizes you -to choose that version for the Program. - - Later license versions may give you additional or different -permissions. However, no additional obligations are imposed on any -author or copyright holder as a result of your choosing to follow a -later version. - - 15. Disclaimer of Warranty. - - THERE IS NO WARRANTY FOR THE PROGRAM, TO THE EXTENT PERMITTED BY -APPLICABLE LAW. EXCEPT WHEN OTHERWISE STATED IN WRITING THE COPYRIGHT -HOLDERS AND/OR OTHER PARTIES PROVIDE THE PROGRAM "AS IS" WITHOUT WARRANTY -OF ANY KIND, EITHER EXPRESSED OR IMPLIED, INCLUDING, BUT NOT LIMITED TO, -THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR -PURPOSE. THE ENTIRE RISK AS TO THE QUALITY AND PERFORMANCE OF THE PROGRAM -IS WITH YOU. SHOULD THE PROGRAM PROVE DEFECTIVE, YOU ASSUME THE COST OF -ALL NECESSARY SERVICING, REPAIR OR CORRECTION. - - 16. Limitation of Liability. - - IN NO EVENT UNLESS REQUIRED BY APPLICABLE LAW OR AGREED TO IN WRITING -WILL ANY COPYRIGHT HOLDER, OR ANY OTHER PARTY WHO MODIFIES AND/OR CONVEYS -THE PROGRAM AS PERMITTED ABOVE, BE LIABLE TO YOU FOR DAMAGES, INCLUDING ANY -GENERAL, SPECIAL, INCIDENTAL OR CONSEQUENTIAL DAMAGES ARISING OUT OF THE -USE OR INABILITY TO USE THE PROGRAM (INCLUDING BUT NOT LIMITED TO LOSS OF -DATA OR DATA BEING RENDERED INACCURATE OR LOSSES SUSTAINED BY YOU OR THIRD -PARTIES OR A FAILURE OF THE PROGRAM TO OPERATE WITH ANY OTHER PROGRAMS), -EVEN IF SUCH HOLDER OR OTHER PARTY HAS BEEN ADVISED OF THE POSSIBILITY OF -SUCH DAMAGES. - - 17. Interpretation of Sections 15 and 16. - - If the disclaimer of warranty and limitation of liability provided -above cannot be given local legal effect according to their terms, -reviewing courts shall apply local law that most closely approximates -an absolute waiver of all civil liability in connection with the -Program, unless a warranty or assumption of liability accompanies a -copy of the Program in return for a fee. diff --git a/Makefile b/Makefile @@ -1,68 +0,0 @@ -# See LICENSE file for copyright and license details. - -VERSION = post-2.0.2 - -PREFIX = /usr/local -MANPREFIX = ${PREFIX}/share/man - -CPPFLAGS = -DVERSION=\"${VERSION}\" -CFLAGS = -std=c99 -pthread -pedantic -Wall -Wextra \ - -Wno-unused-parameter -O3 ${CPPFLAGS} -DBGFLAGS = -std=c99 -pthread -pedantic -Wall -Wextra \ - -Wno-unused-parameter -g ${CPPFLAGS} - -CC = cc - -all: nissy - -nissy: clean - ${CC} ${CFLAGS} -o nissy src/*.c - -nissy.exe: - x86_64-w64-mingw32-gcc ${CFLAGS} -static -o nissy.exe src/*.c - -debug: - ${CC} ${DBGFLAGS} -o nissy src/*.c - -test: - ${CC} ${DBGFLAGS} -DTEST -o test src/*.c tests/*.c - -clean: - rm -rf nissy nissy*.exe nissy*.tar.gz doc/nissy.html doc/nissy.pdf - -dist: clean nissy.exe - mkdir -p nissy-${VERSION} - cp -R LICENSE Makefile INSTALL doc src nissy-${VERSION} - groff -Tpdf -mandoc doc/nissy.1 > doc/nissy.pdf - groff -Thtml -mandoc doc/nissy.1 > doc/nissy.html - cp doc/nissy.pdf nissy-${VERSION}/doc/nissy.pdf - cp doc/nissy.html nissy-${VERSION}/doc/nissy.html - tar -cf nissy-${VERSION}.tar nissy-${VERSION} - gzip nissy-${VERSION}.tar - rm -rf nissy-${VERSION} - mv nissy.exe nissy-${VERSION}.exe - -upload: dist - rsync -v --rsync-path=openrsync nissy-${VERSION}.exe \ - tronto.net:/var/www/htdocs/nissy.tronto.net/ - rsync -v --rsync-path=openrsync nissy-${VERSION}.tar.gz \ - tronto.net:/var/www/htdocs/nissy.tronto.net/ - -website: - rsync -rv --rsync-path=openrsync \ - www/ tronto.net:/var/www/htdocs/nissy.tronto.net - -install: nissy - mkdir -p ${DESTDIR}${PREFIX}/bin - cp -f nissy ${DESTDIR}${PREFIX}/bin/nissy - chmod 755 ${DESTDIR}${PREFIX}/bin/nissy - mkdir -p ${DESTDIR}${MANPREFIX}/man1 - sed "s/VERSION/${VERSION}/g" < doc/nissy.1 \ - > ${DESTDIR}${MANPREFIX}/man1/nissy.1 - chmod 644 ${DESTDIR}${MANPREFIX}/man1/nissy.1 - -uninstall: - rm -rf ${DESTDIR}${PREFIX}/bin/nissy ${DESTDIR}${MANPREFIX}/man1/nissy.1 - for s in ${SCRIPTS}; do rm -rf ${DESTDIR}${PREFIX}/bin/$$s; done - -.PHONY: all debug test clean dist install uninstall upload diff --git a/README.md b/README.md @@ -1,104 +1,50 @@ -# WARNING +# Where is nissy? -I am currently rewriting some important parts of the code -and the git version is not working. -You can download the last stable version from the -[download page](https://nissy.tronto.net/download). +In April 2023 I have decided to split nissy in 2 separate projects: an +optimal solver and an FMC assistant. These two projects are not usable +yet, so in the meantime I will keep a third branch where I update the +classic version of nissy with bugfixes and minor improvements. -# Nissy +You can find these three branches at the following pages (also +on github, links below are to my personal git instance): -A Rubik's cube solver and FMC assistant. -For optimal HTM solving Nissy uses techniques from Herbert Kociemba's -[Cube Explorer](http://kociemba.org/cube.htm) and Tomas Rokicki's -[nxopt](https://github.com/rokicki/cube20src/blob/master/nxopt.md). -With 4 cores at 2.5GHz and using about 3Gb of RAM, Nissy can find an -optimal solution in about a minute on average. +* [nissy-classic](https://git.tronto.net/nissy-classic): The stable + branch, will receive bugfixes and minor improvements but no big + change. Will eventually be replaced by the other two versions. +* [nissy-fmc](https://git.tronto.net/nissy-fmc): This will focus on + features useful for practicing FMC, for example finding EOs and + DRs (if you do not know what this means, there is a good chance + you don't care). I plan to make a graphical interface for it and + make it more usable. It will not be able to find an optimal + solution. *Not working at the moment.* +* [nissy-nx](https://git.tronto.net/nissy-nx): An optimal solver. + For now this is just my playground for implementing complex + optimizations, following the ideas of Tomas's Rokicki's + [nxopt](https://github.com/rokicki/cube20src/blob/master/nxopt.md). + Eventually it will become faster than nissy-classic at optimal + solving, but without all other features. *Not working at the moment.* -Nissy can also solve many different substeps of Thistlethwaite's algorithm -(DR/HTR), and can use NISS (Normal-Inverse Scramble Switch). -It can be useful to analyze your DR solves (and more, once I implement more features). +# I am a user of nissy, what should I do? -You can get Nissy from [nissy.tronto.net](https://nissy.tronto.net). -The download links and installation instructions can be found on the -[download page](https://nissy.tronto.net/download). +If you are happy with using nissy as it is, you can keep using it. -## Structure of the code +When nissy-fmc and nissy-classic are ready, you can chek them out too. -You can find all the source code in the `src` folder. -I strived to keep it legible but I did not write many comments (barely any at all). -I'll try to explain here the main parts of the program. +# But I liked that nissy can do both optimal solving! Why did you split it? -### Cube, moves and transformations +Then I encourage you to keep using nissy-classic :-) -There are many ways to represent a cube. In Nissy I use two: +See +[my blog post](https://sebastiano.tronto.net/blog/2023-04-10-the-big-rewrite/) +for some reasons behind this change. -* An array representation `CubeArray`: 3 arrays representing the permutation -of corners, edges and centers and 2 arrays for the orientation of corners and edges. -* An 11-integers representation `Cube`: 3 integers for edge orientation (with respect -to the three axes), 3 for corner orientation, and so on. Edge permutation is a bit -complicated because encoding 12 factorial as a single number is too large for some -practical reasons, so I use 3 integers for that. +# I just want to look at the code, where should I go? -Moves are easy to apply on the array form, but they are slow. So `moves.c` -contains the instructions to create all the transition tables necessary -to get the next position for the cube with just 11 lookup operations -(one for each of the 11 integers in the second representation). -These transition tables are saved in the `mtables` file in the -`tables` folder in binary format. - -The 11 integers are obviously redundant, but keeping all of them makes it easy -to apply transformations. A transformation is a rotation of the whole cube, possibly -combined with a mirror operation. Applying a transformation to a cube (say obtained -by applying a scramble to the solved cube) means applying the transformation to a -solved cube, then the scramble and then the inverse of the transformation -(i.e. conjugating by it). - -### Coordinates and pruning tables - -A *coordinate* consists of a function that takes a cube (in the 11-integer -representation) and return an (unsigned, 64-bit) integer. They are used -to "linearize" a cube and build pruning tables, which speed up significantly the -solving process. To be able to access the pruning table quickly, the function -needs to be very fast (e.g. it should not convert between the two representations -of the cube if not necessary). - -Some coordinates make use of symmetries to reduce the size of the resulting -pruning table. Unfortunately this complicates the code a lot, but it is a huge -advantage: it reduces by a factor of about 16 the pruning table size. - -Pruning tables are related to a specific step, a moveset and a coordinate. They -contain one value from 0 to 15 (4 bits) for each possible value for the coordinate, -which is less or equal than the minimum number of moves required to solve the -given step with the given moveset for a cube which has the given coordinate. For example, -say the coordinate `neo` gives the number of non-oriented edges (say with respect to -F/B). Then the possible values for the coordinate are 0,2,4,...,12. An associated -pruning table to solving EO with HTM moveset and this coordinate would have values 0 -(for `neo=0`), 3 (for `neo=2`), 1 (for `neo=4`)... - -The values for most pruning tables are memorized modulo 16, so they only occupy -4 bits per entry, and values larger than 15 are saved as 15. This is good enough -for most applications. -Some large tables are memorized in compact form using only 2 bits, similarly -to what [nxopt](https://github.com/rokicki/cube20src/blob/master/nxopt.md) does: -a base value `b` is picked and a value of `n` is saved as `MIN(3,MAX(0,n-b))`. -When a value of `v=1,2,3` is read it is simply returned as `v+b`, while if -`0` is a successive lookup to a fallback table is performed. The base value `b` -is picked to maximize the sum frequency of the values `1,2,3`. - -In order to generate the pruning tables, it is necessary to be able to move -a transform a coordinate; it is possible to do so without passing through a -complete cube representations, in a way similar to what Cube Explorer does. -This used to be different before version 2.1 (June 2022). - -More documentation on this and on the different types of coordinates (base -vs composed) is work in progress. - -### Solving - -Solving is implemented as a generic function that takes both a step and -a (scrambled) cube as input, as well as some extra parameters that say e.g. -how many solution one wants. A step consists, among other things, of -an estimator function that, given a cube, gives a lower bound for the number -of moves needed to complete the step. Many of these estimators simply -look up the corresponding values in the appropriate pruning table. +If you want to check out the git repository of the version you are +running, you probably want nissy-classic. The newer nissy-fmc will +eventually be nicer and easier to read, containing more or less +the same functionality (except for optimal solving). +If you want to follow my progress on an advanced optimal Rubik's +cube solver, you can check out nissy-nx - just remember that it +does not work yet! diff --git a/TODO/2.1.md b/TODO/2.1.md @@ -1,51 +0,0 @@ -# TODO-list for version 2.1 (or is it 3.0 at this point?) - -## Rework solver - -### 1. Implement minimum viable - -* Implement nxopt31 with fst_cube. Remember that the function - move_check_solved() should do one axis at the time, so that we don't move - everything before checking. -* test? - -### 2. Rework achitecture and file dependencies - -* solve.h depends only on moves(alg?) (dependency on step and trans is removed). -* Other modules have changed dependencies, might as well rework all. -* Make files smaller, do not include definition in .h, separate -data from abstract operations. -* remove cubetypes.h -* Create a module for multi-step (maybe wait?) -* Possible changes: in step solver, copy cube only if niss; add cleanup function -in solver (called by solve()) to free cube and perhaps pruning tables. -* see various TODO's in files - -### 4. More threading options - -* Lazy multithread: threads are as independent as possible and only -merged at the end. Ideal when all solutions of a certain length are requested. -* (Done) Eager multithread: current implementation, branches communicate the -number and list of solutions to stop as soon as possible. Good when only one -solution of a certain depth is required. - -## Simplify steps - -* Remove one type of rotation. -* Change steps to choicestep and stepalt to step (or was this already done?). - -## Add missing coordinates and steps - -* Check the old file for a list. Many are missing. -* Checkers in steps.c should use coordinates. - -## Missing and new commands - -* gen -* freemem -* twophase - -## Easy improvements - -* Solve should re-orient the cube if centers are off -* Solve: add options for -I (inverse only) and -L (linear = normal + inverse). diff --git a/TODO/build-options.md b/TODO/build-options.md @@ -1,33 +0,0 @@ -# Build options for memory and multithreading - -## Investigate - -* Check exactly how much memory is needed for everything. -* Take note of which parts use threading (solving, genptable, other?). - -## Prepare code - -* Use define / ifdef or similar to compile and build tables only for the - parts to be used. -* If threads = 1, use a much simpler version of the solve method. Remember - that checking if enough solutions have been found is the first thing to - do in singlethread (no locking). -* Do not include pthread if threads = 1. -* Only one optimal solver should be compiled. -* Some simple steps may also need alternatives with smaller tables - (e.g. for staying sub 1Gb). For example dr and drfin. -* If necessary, work out alternatives to "twophase" for low-resource versions. - -## Makefile - -* Figure out how to change these options via makefile. For example: one - variable for the maximum allowed ram and one for the number of threads. -* (Optional) use a configure script? -* (Optional) interactive installation script? - -## Automate - -* Scout for resources during installation and choose best configuration - automatically. -* How to do this in Linux / POSIX? -* How to do this in Windows? diff --git a/TODO/documentation.md b/TODO/documentation.md @@ -1,41 +0,0 @@ -# Documentation - -## Big documentation file on nissy's internals - -* Coordinates -* Symcoordinates -* Pruning tables -* Coordinate solving -* fst cube -* Optimized solver -* Multithreading -* Commands etc... -* Code architecture - -## examples.md - -* Example file for nissy's website and documentation folder -* With screenshots! - -## Random info - -Where to collect random information like this table? - -Table pt_nxopt31_HTM -Base value: 9 -0 1 -1 6 -2 29 -3 164 -4 1433 -5 16772 -6 205033 -7 2513871 -8 30329976 -9 342440769 -10 2815191126 -11 6147967200 -12 524918774 -13 3546 -14 0 -15 0 diff --git a/TODO/easy.md b/TODO/easy.md @@ -1,16 +0,0 @@ -# Easy things to improve or add - -## Improvements - -* Silent batch mode without >>> -* Solutions should be shown sorted: by length first, then by normal moves - (no niss) first, then it depends on the step (e.g. EO by axis). - -## Old commands and steps - -* drcorners (solve corners after DR) -* Search and improve suboptimal subsequences - -## New commands - -* notation: show valid moves diff --git a/TODO/installation.md b/TODO/installation.md @@ -1,14 +0,0 @@ -# Simplify and improve installation - -## Tables - -* Make install should generate tables, or add a "make tables" target to - generate tables. -* Make tables should also check for existing files and remove old ones - (maybe more for nissy's command than for makefile). - -## Correctness - -* Add checksum for all generated files. -* Hard-code results? Check for compatibility problems between different OSes - and filesystems - but there should not be any, since we use stdint.h. diff --git a/TODO/new-feature-ideas.md b/TODO/new-feature-ideas.md @@ -1,32 +0,0 @@ -# Possible new features and improvements - -This file contains non-refined ideas. Once an idea gets refined, it will -get its own file and more details. - -## Steps - -* QTM solver -* 5-side solver (for robots) -* Other steps (cross, blocks, LSE...) - -## UX features - -* Save algs as variables and edit them (like in old nissy) -* Use a logging system for previously run commands, info, results... - (e.g. when solving with -c solutions are not shown, they can be logged here) -* Configurability: add an "alias" command, run config file at startup -* Input cube state directly instead of moves (ugly from command line / file) - -## Improvements - -* Optimal solver: when asking only for one solution, scan for upper bound in - parallel using a non-optimal (but fast) solver (e.g. twophase). -* Optimal solver: up to a small bound, try with a small pruning table. -* Optimal solver: start at different depths in parallel -* Multi-step solver: make more general - -## New features - -* Allow user to specify moveset manually (see issue \#5 on github) -* EO analysis (and also DR and HTR analysis): group similar EOs (Jay) -* HTR "maze" analysis? diff --git a/TODO/parser.md b/TODO/parser.md @@ -1,13 +0,0 @@ -# Improve command parser - -First, expand this TODO file to be more precise. - -## Refactor - -* The syntax of a command's options should be described by data, not by a - parser function. -* A single parser function can then parse options for all commands. - -## Usability - -* Better error messages! diff --git a/TODO/refactoring.md b/TODO/refactoring.md @@ -1,28 +0,0 @@ -# Refactoring - -## Init functions - -* All .h files should have a single init function. -* This function should initialize everything that this module needs, including - calling the init functions of the modules it depends on. -* To avoid multiple initialization of the same module, each should have a - static bool initialized variable. -* Everything that a module needs should be initialized by init(), avoid - initializing stuff when solving. Exception: pruning tables, move tables. -* Most functions should generate some tables and save them to disk. -* Init functions should have a consistent structure (e.g. the way they check - if the tables are already generated should be the same). - -## Cube types - -* Get rid of cubetype.h, split type definitionss into the other modules. -* Every type definition should be in the most fundamental module that needs it. - -## Code style - -* Stop declaring all variables at the beginning of a function. -* Remove variable names from prototypes. -* Sort function implementations alphabetically, ignore static vs non static. -* Rename functions and variable to have a consistent naming scheme. -* Functions that copy data: swap src and dest, follow memcpy standard. -* Read style(9) and decide what to implement. diff --git a/TODO/testing.md b/TODO/testing.md @@ -1,6 +0,0 @@ -# Testing - -## Write tests - -* Write tests for each module. Some of might require refactoring (this is - a good thing!) diff --git a/TODO/webapp.md b/TODO/webapp.md @@ -1,19 +0,0 @@ -# Towards a nissy webapp - -## Architecture - -* Split in client / server. -* Server can load and keep in memory all the tables, client(s) send messages to - the server to run commands. -* Use UNIX sockets only first, maybe later try WinSock. - -## Simple webapp - -* Investigate how to use fastcgi, try simple program first. -* Decide what limits to put in terms of resources and write a "filter" script - to block big requests (maybe use a timeout). - -## Advanced webapp - -* Use cubing.js for nice graphics. -* Port it to a graphical desktop version too. diff --git a/doc/nissy.1 b/doc/nissy.1 @@ -1,271 +0,0 @@ -.Dd November 2021 -.Dt NISSY 1 -.Os -.Sh NAME -.Nm nissy -.Nd a Rubik's cube solver and FMC assistant -. -.Sh SYNOPSIS -.Nm -.Op Fl b -.Nm -.Ar command -.Op options... -. -.Sh DESCRIPTION -.Nm -is a Rubik's Cube solver. -It uses techniques from Herbert Kociemba's Cube Explorer and -Tomas Rokicki's nxopt. With 4 cores at 2.5GHz and using about 3Gb -of RAM, Nissy can find the optimal solution for a random Rubik's cube position -in about a minute on average. -Nissy can also solve different substeps of the Thistlethwaite's algorithm and more. -.Pp -When run without any argument an interactive shell is launched, otherwise -the provided -.Ar command -is executed and nissy terminates. If the option -.Fl b -is given, every argument after it is ignored and the shell is launched without -any prompt or welcome message. This can be used to run nissy in batch mode, -for example writing a list of commands in a -.Ar file -(one per line) and running -.Ar nissy -b < file -.Pp -The commands that can be run in the interactive shell are the same that can -be run non-interactively and are provided below. -. -.Sh COMMANDS -The available -.Ar commands -are the following: -. -.Bl -tag -width Ds -. -.It Nm cleanup Ar scramble -Rewrites the given scramble using only the 18 base (HTM) moves and at most two -rotations at the end. If -Ar scramble -uses NISS, all moves done on normal scramble are written first, followed by -all moves done on inverse. -. -.It Nm commands -List all available commands. -. -.It Nm freemem -Release some large tables from memory. You can use this command in case -you want to keep nissy open without using too much RAM. -. -.It Nm gen Op Fl t Ar N -Generate all tables used by nissy. Run this to complete your installation. -If -.Ar N -is specified, -.Ar N -CPU threads will be used (defaults to 64, use less only if you don't want -nissy to use all of your CPU resources). -. -.It Nm help Op Ar command -Display help. If no -.Ar command -is given, a generic help message is printed, otherwise a specific help -relative to -.Ar command -is returned. -. -.It Nm invert Ar scramble -Invert the given scramble. -. -.It Nm print Ar scramble -Display a text-only description of the cube obtained after applying -.Ar scramble . -. -.It Nm quit -Quit nissy. -. -.It Nm scramble Oo Fl n Ar N Oc Oo Ar type Oc -Print a randomly-generated (random position) scramble -. -If -.Ar N -is given, it produces -.Ar N -scrambles. -.Ar type -can be specified to be one of the following: -.Bl -tag -width Ds -.It Ar corners -Scramble with solved edges (only cornes are scrambled). -.It Ar dr -Scramble with solved DR on U/D. -.It Ar edges -Scramble with solved corners (only edges are scrambled). -.It Ar eo -Scramble with solved EO on F/B axis. -.It Ar fmc -Scramble the full cube and the resulting scramble starts and ends with -the moves R\(aq U\(aq F. -.It Ar htr -Scramble with HTR solved. -.El -. -.It Nm solve Ar step Oo Ar options Oc Ar scramble -Solve the given -.Ar step -on the given -.Ar scramble. -By default it finds only one (shortest) solution, without using niss, and it -displays the number of moves at the end of the line. -. -The options for the -.Ar solve -command are the following: -. -.Bl -tag -width Ds -. -.It Fl a -Print all solutions: some solutions are filtered out by default for some -steps, for examples EOs that finish with F\(aq, with this options they are not. -. -.It Fl c -Display only the number of solutions found, not the solutions themselves. -. -.It Fl m Ar min -Only look for solution that are at least -.Ar min -moves long. -. -.It Fl M Ar MAX -Only look for solution that are at most -.Ar MAX -moves long. -. -.It Fl n Ar N -Try to find -.Ar N -solutions. By default and unless the -.Fl M -or -.Fl o -options are used, at most one solution is returned. -If at least one of -.Fl M -and -.Fl o -is used, all the solutions found within the given bounds are returned. -The option -.Fl s -overwrites these default behaviors and at most -.Ar N -solutions are returned, still satisfiyng the other constraints. -. -.It Fl N -Allow use of NISS. -. -.It Fl o -Only find solutions that require the minimum number of moves. -. -.It Fl O Ar N -Only find solutions that require at most -.Ar N -moves more than the optimal solution. If -.Ar N -is 0, this is equivalent to -.Fl o -. -.It Fl p -Plain style: do not print the number of moves. -. -.It Fl t Ar N -Use -.Ar N -CPU threads. By default nissy uses only 1 thread. Using more than one -thread will improve performance, but the optimal number depends on your -machine and operating system. Generally, using one less than the number -of threads of your CPU works quite well. -. -.It Fl v -Verbose mode: print some information during the search and print each solution -as it is found instead of only printing them all together at the end. -. -. -.El -. -.It Nm steps -List all available -.Ar steps -for the -.Ar solve -command. -. -.It Nm twophase Ar scramble -Find a solution using a two-phase method. This does not guarantee -to return an optimal solution (and in fact most often it does not), -but it is very fast. -. -.It Nm unniss Ar scramble -Rewrite the scramble without using NISS. -. -.It Nm version -Display version information. -. -.El -. -.Sh SCRAMBLES -All the commands above that accept a scramble also accept a -.Fl Nm i -option with no arguments. -If this option is given, multiple scrambles are read from standard -input (one per line) until and EOF is found, at which point stdin is cleared. -. -.Sh ENVIRONMENT -Data is stored in the folder pointed to by -.Nm $NISSYDATA. -If that variable is unset the folder -.Nm $XDG_DATA_HOME/nissy -or -.Nm $HOME/.nissy -is used instead. If none of this environment variables is defined -(e.g. in a non-UNIX system), the current folder is used. -. -.Sh EXAMPLES -.Pp -The command: -.Dl nissy solve -v -O 1 \(dqR\(aqU\(aqFD2L2FR2U2R2BD2LB2D\(aqB2L\(aqR\(aqBD2BU2LU2R\(aqU\(aqF\(dq -Returns: -.Dl Searching depth 0 -.Dl Searching depth 1 -.Dl (some more lines) -.Dl Searching depth 16 -.Dl D2 F\(aq U2 D2 F\(aq L2 D R2 D F B2 R\(aq L2 F\(aq U\(aq D -.Dl Searching depth 17 -.Dl D2 F\(aq U2 D2 F\(aq L2 D R2 D F B2 R\(aq L2 F\(aq U\(aq D (16) -Notice that the solution is printed twice: the first time it is printed as soon -as it is found as requested by the -v option. -.Pp -The command: -.Dl nissy solve eofb -m 4 -M 5 -N -n 6 \(dqR\(aqU\(aqFD2L2 FR2 U2R2BD2 L B2 D\(aq B2 L\(aq R\(aq\(dq -Returns: -.Dl U B U\(aq B (4) -.Dl U (B R\(aq B) (4) -.Dl (U B R\(aq B) (4) -.Dl U2 F R2 F (4) -.Dl U2 B U2 B (4) -.Dl (U2 B R\(aq B) (4) -.Pp -On a UNIX shell, the composite command -.Dl nissy scramble -n 2 | nissy solve -i > file.txt -Generates two random scrambles, solves them and saves the result to file.txt. -The file will look something like this: -.Dl >>> Line: D U2 F D B\(aq F L2 D\(aq F2 R2 L B2 L\(aq U2 B2 R F2 L\(aq D2 -.Dl U2 R2 F2 L B2 D\(aq R2 D\(aq F U L2 B\(aq U\(aq R2 D2 R2 U (17) -.Dl >>> Line: D B R U\(aq B\(aq L2 U L U D2 R L B2 U2 L2 U2 R U2 B2 L F2 -.Dl D\(aq F R\(aq D B L2 B R2 L U L U2 B D\(aq U R U F2 (18) -. -.Sh AUTHORS -.An Sebastiano Tronto Aq Mt sebastiano@tronto.net -. -.Sh SOURCE CODE -Source code is available at -.Lk https://nissy.tronto.net diff --git a/old/maybe-useful-coord.c b/old/maybe-useful-coord.c @@ -1,181 +0,0 @@ -int -array_ep_to_epos(int *ep, int *ss) -{ - int epos[12] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}; - int eps[4]; - int i, j, is; - - for (i = 0, is = 0; i < 12; i++) { - for (j = 0; j < 4; j++) { - if (ep[i] == ss[j]) { - eps[is++] = j; - epos[i] = 1; - } - } - } - - for (i = 0; i < 4; i++) - swap(&epos[ss[i]], &epos[i+8]); - - return 24 * subset_to_index(epos, 12, 4) + perm_to_index(eps, 4); -} - -void -epos_to_compatible_ep(int epos, int *ep, int *ss) -{ - int i, j, k, other[8]; - bool flag; - - for (i = 0; i < 12; i++) - ep[i] = -1; - - epos_to_partial_ep(epos, ep, ss); - - for (i = 0, j = 0; i < 12; i++) { - flag = false; - for (k = 0; k < 4; k++) - flag = flag || (i == ss[k]); - if (!flag) - other[j++] = i; - } - - for (i = 0, j = 0; i < 12; i++) - if (ep[i] == -1) - ep[i] = other[j++]; -} - -void -epos_to_partial_ep(int epos, int *ep, int *ss) -{ - int i, is, eposs[12], eps[4]; - - index_to_perm(epos % FACTORIAL4, 4, eps); - index_to_subset(epos / FACTORIAL4, 12, 4, eposs); - - for (i = 0; i < 4; i++) - swap(&eposs[ss[i]], &eposs[i+8]); - - for (i = 0, is = 0; i < 12; i++) - if (eposs[i]) - ep[i] = ss[eps[is++]]; -} - -void -fix_eorleoud(CubeArray *arr) -{ - int i; - - for (i = 0; i < 12; i++) { - if ((edge_slice(i) == 0 && edge_slice(arr->ep[i]) != 0) || - (edge_slice(i) != 0 && edge_slice(arr->ep[i]) == 0)) { - arr->eorl[i] = 1 - arr->eofb[i]; - } else { - arr->eorl[i] = arr->eofb[i]; - } - - if ((edge_slice(i) == 2 && edge_slice(arr->ep[i]) != 2) || - (edge_slice(i) != 2 && edge_slice(arr->ep[i]) == 2)) { - arr->eoud[i] = 1 - arr->eofb[i]; - } else { - arr->eoud[i] = arr->eofb[i]; - } - } -} - -void -fix_cofbcorl(CubeArray *arr) -{ - int i; - - for (i = 0; i < 8; i++) { - if (i % 2 == arr->cp[i] % 2) { - arr->cofb[i] = arr->coud[i]; - arr->corl[i] = arr->coud[i]; - } else { - if (arr->cp[i] % 2 == 0) { - arr->cofb[i] = (arr->coud[i]+1)%3; - arr->corl[i] = (arr->coud[i]+2)%3; - } else { - arr->cofb[i] = (arr->coud[i]+2)%3; - arr->corl[i] = (arr->coud[i]+1)%3; - } - } - } -} - -Cube -admissible_ep(Cube cube, PieceFilter f) -{ - CubeArray *arr = new_cubearray(cube, f); - Cube ret; - bool used[12] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}; - int i, j; - - for (i = 0; i < 12; i++) - if (arr->ep[i] != -1) - used[arr->ep[i]] = true; - - for (i = 0, j = 0; i < 12; i++) { - for ( ; j < 11 && used[j]; j++); - if (arr->ep[i] == -1) - arr->ep[i] = j++; - } - - ret = arrays_to_cube(arr, pf_ep); - free_cubearray(arr, f); - - return ret; -} - -int -edge_slice(Edge e) { - if (e < 0 || e > 11) - return -1; - - if (e == FR || e == FL || e == BL || e == BR) - return 0; - if (e == UR || e == UL || e == DR || e == DL) - return 1; - - return 2; -} - -int -piece_orientation(Cube cube, int piece, char *orientation) -{ - int arr[12], n, b, x; - - if (!strcmp(orientation, "eofb")) { - x = cube.eofb; - n = 12; - b = 2; - } else if (!strcmp(orientation, "eorl")) { - x = cube.eorl; - n = 12; - b = 2; - } else if (!strcmp(orientation, "eoud")) { - x = cube.eoud; - n = 12; - b = 2; - } else if (!strcmp(orientation, "coud")) { - x = cube.coud; - n = 8; - b = 3; - } else if (!strcmp(orientation, "corl")) { - x = cube.corl; - n = 8; - b = 3; - } else if (!strcmp(orientation, "cofb")) { - x = cube.cofb; - n = 8; - b = 3; - } else { - return -1; - } - - int_to_sum_zero_array(x, b, n, arr); - if (piece < n) - return arr[piece]; - - return -1; -} diff --git a/old/maybe-useful-steps.c b/old/maybe-useful-steps.c @@ -1,1111 +0,0 @@ -#include "steps.h" - -#define UPDATECHECKSTOP(a, b, c) if ((a=(MAX((a),(b))))>(c)) return (a); - -static int estimate_stepalt(StepAlt *a, uint64_t *ind); - -/* Checkers and validators ***************************************************/ - -/* TODO: these should be with Cube *cube (and all need to change) */ -/* Maybe move them to cube.c */ -static bool check_centers(Cube cube); -static bool check_coud_HTM(Cube cube); -static bool check_coud_URF(Cube cube); -static bool check_corners_HTM(Cube cube); -static bool check_corners_URF(Cube cube); -static bool check_cornershtr(Cube cube); -static bool check_eofb(Cube cube); -static bool check_drud(Cube cube); -static bool check_htr(Cube cube); - -static bool always_valid(Alg *alg); -static bool validate_singlecw_ending(Alg *alg); - -/* Messages for when cube is not ready ***************************************/ - -static char check_centers_msg[100] = "cube must be oriented (centers solved)"; -static char check_eo_msg[100] = "EO must be solved on given axis"; -static char check_dr_msg[100] = "DR must be solved on given axis"; -static char check_htr_msg[100] = "HTR must be solved"; -static char check_drany_msg[100] = "DR must be solved on at least one axis"; - -/* Steps *********************************************************************/ - -/* Optimal solvers *******************/ - -Step -optimal_HTM = { - .shortname = "optimal", - .name = "Optimal solve (in HTM)", - - .final = true, - .is_done = is_solved, - .estimate = estimate_nxopt31_HTM, - .ready = check_centers, - .ready_msg = check_centers_msg, - .is_valid = always_valid, - .moveset = &moveset_HTM, - - .pre_trans = uf, - - .tables = {&pd_nxopt31_HTM, &pd_corners_HTM}, - .ntables = 2, -}; - -Step -optimal_light_HTM = { - .shortname = "light", - .name = "Optimal solve (in HTM), small table (500Mb RAM total)", - - .final = true, - .is_done = is_solved, - .estimate = estimate_light_HTM, - .ready = check_centers, - .ready_msg = check_centers_msg, - .is_valid = always_valid, - .moveset = &moveset_HTM, - - .pre_trans = uf, - - .tables = {&pd_drud_sym16_HTM, &pd_corners_HTM}, - .ntables = 2, -}; - -/* Optimal after EO ******************/ - -Step -eofin_eo = { - .shortname = "eofin", - .name = "Optimal solve after EO without breaking EO (detected)", - - .final = true, - .is_done = is_solved, - .estimate = estimate_nxopt31_HTM, - .ready = check_eofb, - .ready_msg = check_eo_msg, - .is_valid = always_valid, - .moveset = &moveset_eofb, - - .detect = detect_pretrans_eofb, - - .tables = {&pd_nxopt31_HTM, &pd_corners_HTM}, - .ntables = 2, -}; - -Step -eofbfin_eofb = { - .shortname = "eofbfin", - .name = "Optimal after EO on F/B without breaking EO", - - .final = true, - .is_done = is_solved, - .estimate = estimate_nxopt31_HTM, - .ready = check_eofb, - .ready_msg = check_eo_msg, - .is_valid = always_valid, - .moveset = &moveset_eofb, - - .pre_trans = uf, - - .tables = {&pd_nxopt31_HTM, &pd_corners_HTM}, - .ntables = 2, -}; - -Step -eorlfin_eorl = { - .shortname = "eorlfin", - .name = "Optimal after EO on R/L without breaking EO", - - .final = true, - .is_done = is_solved, - .estimate = estimate_nxopt31_HTM, - .ready = check_eofb, - .ready_msg = check_eo_msg, - .is_valid = always_valid, - .moveset = &moveset_eofb, - - .pre_trans = ur, - - .tables = {&pd_nxopt31_HTM, &pd_corners_HTM}, - .ntables = 2, -}; - -Step -eoudfin_eoud = { - .shortname = "eoudfin", - .name = "Optimal after EO on U/D without breaking EO", - - .final = true, - .is_done = is_solved, - .estimate = estimate_nxopt31_HTM, - .ready = check_eofb, - .ready_msg = check_eo_msg, - .is_valid = always_valid, - .moveset = &moveset_eofb, - - .pre_trans = fd, - - .tables = {&pd_nxopt31_HTM, &pd_corners_HTM}, - .ntables = 2, -}; - -/* EO steps **************************/ -Step -eoany_HTM = { - .shortname = "eo", - .name = "EO on any axis", - - .final = false, - .is_done = check_eofb, - .estimate = estimate_eofb_HTM, - .ready = check_centers, - .ready_msg = check_centers_msg, - .is_valid = validate_singlecw_ending, - .moveset = &moveset_HTM, - - .detect = detect_pretrans_void_3axis, - - .tables = {&pd_eofb_HTM}, - .ntables = 1, -}; - -Step -eofb_HTM = { - .shortname = "eofb", - .name = "EO on F/B", - - .final = false, - .is_done = check_eofb, - .estimate = estimate_eofb_HTM, - .ready = check_centers, - .ready_msg = check_centers_msg, - .is_valid = validate_singlecw_ending, - .moveset = &moveset_HTM, - - .pre_trans = uf, - - .tables = {&pd_eofb_HTM}, - .ntables = 1, -}; - -Step -eorl_HTM = { - .shortname = "eorl", - .name = "EO on R/L", - - .final = false, - .is_done = check_eofb, - .estimate = estimate_eofb_HTM, - .ready = check_centers, - .ready_msg = check_centers_msg, - .is_valid = validate_singlecw_ending, - .moveset = &moveset_HTM, - - .pre_trans = ur, - - .tables = {&pd_eofb_HTM}, - .ntables = 1, -}; - -Step -eoud_HTM = { - .shortname = "eoud", - .name = "EO on U/D", - - .final = false, - .is_done = check_eofb, - .estimate = estimate_eofb_HTM, - .ready = check_centers, - .ready_msg = check_centers_msg, - .is_valid = validate_singlecw_ending, - .moveset = &moveset_HTM, - - .pre_trans = fd, - - .tables = {&pd_eofb_HTM}, - .ntables = 1, -}; - -/* CO steps **************************/ -Step -coany_HTM = { - .shortname = "co", - .name = "CO on any axis", - - .final = false, - .is_done = check_coud_HTM, - .estimate = estimate_coud_HTM, - .ready = NULL, - .is_valid = validate_singlecw_ending, - .moveset = &moveset_HTM, - - .detect = detect_pretrans_void_3axis, - - .tables = {&pd_coud_HTM}, - .ntables = 1, -}; - -Step -coud_HTM = { - .shortname = "coud", - .name = "CO on U/D", - - .final = false, - .is_done = check_coud_HTM, - .estimate = estimate_coud_HTM, - .ready = NULL, - .is_valid = validate_singlecw_ending, - .moveset = &moveset_HTM, - - .pre_trans = uf, - - .tables = {&pd_coud_HTM}, - .ntables = 1, -}; - -Step -corl_HTM = { - .shortname = "corl", - .name = "CO on R/L", - - .final = false, - .is_done = check_coud_HTM, - .estimate = estimate_coud_HTM, - .ready = NULL, - .is_valid = validate_singlecw_ending, - .moveset = &moveset_HTM, - - .pre_trans = rf, - - .tables = {&pd_coud_HTM}, - .ntables = 1, -}; - -Step -cofb_HTM = { - .shortname = "cofb", - .name = "CO on F/B", - - .final = false, - .is_done = check_coud_HTM, - .estimate = estimate_coud_HTM, - .ready = NULL, - .is_valid = validate_singlecw_ending, - .moveset = &moveset_HTM, - - .pre_trans = fd, - - .tables = {&pd_coud_HTM}, - .ntables = 1, -}; - -Step -coany_URF = { - .shortname = "co-URF", - .name = "CO any axis (URF moveset)", - - .final = false, - .is_done = check_coud_URF, - .estimate = estimate_coud_URF, - .ready = NULL, - .is_valid = validate_singlecw_ending, - .moveset = &moveset_URF, - - .detect = detect_pretrans_void_3axis, - - .tables = {&pd_coud_HTM}, - .ntables = 1, -}; - -Step -coud_URF = { - .shortname = "coud-URF", - .name = "CO on U/D (URF moveset)", - - .final = false, - .is_done = check_coud_URF, - .estimate = estimate_coud_URF, - .ready = NULL, - .is_valid = validate_singlecw_ending, - .moveset = &moveset_URF, - - .pre_trans = uf, - - .tables = {&pd_coud_HTM}, - .ntables = 1, -}; - -Step -corl_URF = { - .shortname = "corl-URF", - .name = "CO on R/L (URF moveset)", - - .final = false, - .is_done = check_coud_URF, - .estimate = estimate_coud_URF, - .ready = NULL, - .is_valid = validate_singlecw_ending, - .moveset = &moveset_URF, - - .pre_trans = rf, - - .tables = {&pd_coud_HTM}, - .ntables = 1, -}; - -Step -cofb_URF = { - .shortname = "cofb-URF", - .name = "CO on F/B (URF moveset)", - - .final = false, - .is_done = check_coud_URF, - .estimate = estimate_coud_URF, - .ready = NULL, - .is_valid = validate_singlecw_ending, - .moveset = &moveset_URF, - - .pre_trans = fd, - - .tables = {&pd_coud_HTM}, - .ntables = 1, -}; - -/* Misc corner steps *****************/ -Step -cornershtr_HTM = { - .shortname = "chtr", - .name = "Solve corners to HTR state", - - .final = false, - .is_done = check_cornershtr, - .estimate = estimate_cornershtr_HTM, - .ready = NULL, - .is_valid = validate_singlecw_ending, - .moveset = &moveset_HTM, - - .pre_trans = uf, - - .tables = {&pd_cornershtr_HTM}, - .ntables = 1, -}; - -Step -cornershtr_URF = { - .shortname = "chtr-URF", - .name = "Solve corners to HTR state (URF moveset)", - - .final = false, - .is_done = check_cornershtr, - .estimate = estimate_cornershtr_URF, - .ready = NULL, - .is_valid = validate_singlecw_ending, - .moveset = &moveset_URF, - - .pre_trans = uf, - - .tables = {&pd_cornershtr_HTM}, - .ntables = 1, -}; - -Step -corners_HTM = { - .shortname = "corners", - .name = "Solve corners", - - .final = true, - .is_done = check_corners_HTM, - .estimate = estimate_corners_HTM, - .ready = NULL, - .is_valid = always_valid, - .moveset = &moveset_HTM, - - .pre_trans = uf, - - .tables = {&pd_corners_HTM}, - .ntables = 1, -}; - -Step -corners_URF = { - .shortname = "corners-URF", - .name = "Solve corners (URF moveset)", - - .final = true, /* TODO: check if this works with reorient */ - .is_done = check_corners_URF, - .estimate = estimate_corners_URF, - .ready = NULL, - .is_valid = always_valid, - .moveset = &moveset_URF, - - .pre_trans = uf, - - .tables = {&pd_corners_HTM}, - .ntables = 1, -}; - -/* DR steps **************************/ -Step -drany_HTM = { - .shortname = "dr", - .name = "DR on any axis", - - .final = false, - .is_done = check_drud, - .estimate = estimate_drud_HTM, - .ready = check_centers, - .ready_msg = check_centers_msg, - .is_valid = validate_singlecw_ending, - .moveset = &moveset_HTM, - - .detect = detect_pretrans_void_3axis, - - .tables = {&pd_drud_sym16_HTM}, - .ntables = 1, -}; - -Step -drud_HTM = { - .shortname = "drud", - .name = "DR on U/D", - - .final = false, - .is_done = check_drud, - .estimate = estimate_drud_HTM, - .ready = check_centers, - .ready_msg = check_centers_msg, - .is_valid = validate_singlecw_ending, - .moveset = &moveset_HTM, - - .pre_trans = uf, - - .tables = {&pd_drud_sym16_HTM}, - .ntables = 1, -}; - -Step -drrl_HTM = { - .shortname = "drrl", - .name = "DR on R/L", - - .final = false, - .is_done = check_drud, - .estimate = estimate_drud_HTM, - .ready = check_centers, - .ready_msg = check_centers_msg, - .is_valid = validate_singlecw_ending, - .moveset = &moveset_HTM, - - .pre_trans = rf, - - .tables = {&pd_drud_sym16_HTM}, - .ntables = 1, -}; - -Step -drfb_HTM = { - .shortname = "drfb", - .name = "DR on F/B", - - .final = false, - .is_done = check_drud, - .estimate = estimate_drud_HTM, - .ready = check_centers, - .ready_msg = check_centers_msg, - .is_valid = validate_singlecw_ending, - .moveset = &moveset_HTM, - - .pre_trans = fd, - - .tables = {&pd_drud_sym16_HTM}, - .ntables = 1, -}; - -/* DR from EO */ -Step -dr_eo = { - .shortname = "dr-eo", - .name = "DR without breaking EO (automatically detected)", - - .final = false, - .is_done = check_drud, - .estimate = estimate_dr_eofb, - .ready = check_eofb, - .ready_msg = check_eo_msg, - .is_valid = validate_singlecw_ending, - .moveset = &moveset_eofb, - - .detect = detect_pretrans_eofb, - - .tables = {&pd_drud_eofb}, - .ntables = 1, -}; - -Step -dr_eofb = { - .shortname = "dr-eofb", - .name = "DR on U/D or R/L without breaking EO on F/B", - - .final = false, - .is_done = check_drud, - .estimate = estimate_dr_eofb, - .ready = check_eofb, - .ready_msg = check_eo_msg, - .is_valid = validate_singlecw_ending, - .moveset = &moveset_eofb, - - .pre_trans = uf, - - .tables = {&pd_drud_eofb}, - .ntables = 1, -}; - -Step -dr_eorl = { - .shortname = "dr-eorl", - .name = "DR on U/D or F/B without breaking EO on R/L", - - .final = false, - .is_done = check_drud, - .estimate = estimate_dr_eofb, - .ready = check_eofb, - .ready_msg = check_eo_msg, - .is_valid = validate_singlecw_ending, - .moveset = &moveset_eofb, - - .pre_trans = ur, - - .tables = {&pd_drud_eofb}, - .ntables = 1, -}; - -Step -dr_eoud = { - .shortname = "dr-eoud", - .name = "DR on R/L or F/B without breaking EO on U/D", - - .final = false, - .is_done = check_drud, - .estimate = estimate_dr_eofb, - .ready = check_eofb, - .ready_msg = check_eo_msg, - .is_valid = validate_singlecw_ending, - .moveset = &moveset_eofb, - - .pre_trans = fd, - - .tables = {&pd_drud_eofb}, - .ntables = 1, -}; - -Step -drud_eofb = { - .shortname = "drud-eofb", - .name = "DR on U/D without breaking EO on F/B", - - .final = false, - .is_done = check_drud, - .estimate = estimate_drud_eofb, - .ready = check_eofb, - .ready_msg = check_eo_msg, - .is_valid = validate_singlecw_ending, - .moveset = &moveset_eofb, - - .pre_trans = uf, - - .tables = {&pd_drud_eofb}, - .ntables = 1, -}; - -Step -drrl_eofb = { - .shortname = "drrl-eofb", - .name = "DR on R/L without breaking EO on F/B", - - .final = false, - .is_done = check_drud, - .estimate = estimate_drud_eofb, - .ready = check_eofb, - .ready_msg = check_eo_msg, - .is_valid = validate_singlecw_ending, - .moveset = &moveset_eofb, - - .pre_trans = rf, - - .tables = {&pd_drud_eofb}, - .ntables = 1, -}; - -Step -drud_eorl = { - .shortname = "drud-eorl", - .name = "DR on U/D without breaking EO on R/L", - - .final = false, - .is_done = check_drud, - .estimate = estimate_drud_eofb, - .ready = check_eofb, - .ready_msg = check_eo_msg, - .is_valid = validate_singlecw_ending, - .moveset = &moveset_eofb, - - .pre_trans = ur, - - .tables = {&pd_drud_eofb}, - .ntables = 1, -}; - -Step -drfb_eorl = { - .shortname = "drfb-eorl", - .name = "DR on F/B without breaking EO on R/L", - - .final = false, - .is_done = check_drud, - .estimate = estimate_drud_eofb, - .ready = check_eofb, - .ready_msg = check_eo_msg, - .is_valid = validate_singlecw_ending, - .moveset = &moveset_eofb, - - .pre_trans = fr, - - .tables = {&pd_drud_eofb}, - .ntables = 1, -}; - -Step -drfb_eoud = { - .shortname = "drfb-eoud", - .name = "DR on F/B without breaking EO on U/D", - - .final = false, - .is_done = check_drud, - .estimate = estimate_drud_eofb, - .ready = check_eofb, - .ready_msg = check_eo_msg, - .is_valid = validate_singlecw_ending, - .moveset = &moveset_eofb, - - .pre_trans = fd, - - .tables = {&pd_drud_eofb}, - .ntables = 1, -}; - -Step -drrl_eoud = { - .shortname = "drrl-eoud", - .name = "DR on R/L without breaking EO on U/D", - - .final = false, - .is_done = check_drud, - .estimate = estimate_drud_eofb, - .ready = check_eofb, - .ready_msg = check_eo_msg, - .is_valid = validate_singlecw_ending, - .moveset = &moveset_eofb, - - .pre_trans = rd, - - .tables = {&pd_drud_eofb}, - .ntables = 1, -}; - -/* DR finish steps */ -Step -dranyfin_DR = { - .shortname = "drfin", - .name = "DR finish on any axis without breaking DR", - - .final = true, - .is_done = is_solved, - .estimate = estimate_drudfin_drud, - .ready = check_drud, - .ready_msg = check_drany_msg, - .is_valid = always_valid, - .moveset = &moveset_drud, - - .detect = detect_pretrans_drud, - - .tables = {&pd_drudfin_noE_sym16_drud}, - .ntables = 1, -}; - -Step -drudfin_drud = { - .shortname = "drudfin", - .name = "DR finish on U/D without breaking DR", - - .final = true, - .is_done = is_solved, - .estimate = estimate_drudfin_drud, - .ready = check_drud, - .ready_msg = check_dr_msg, - .is_valid = always_valid, - .moveset = &moveset_drud, - - .pre_trans = uf, - - .tables = {&pd_drudfin_noE_sym16_drud}, - .ntables = 1, -}; - -Step -drrlfin_drrl = { - .shortname = "drrlfin", - .name = "DR finish on R/L without breaking DR", - - .final = true, - .is_done = is_solved, - .estimate = estimate_drudfin_drud, - .ready = check_drud, - .ready_msg = check_dr_msg, - .is_valid = always_valid, - .moveset = &moveset_drud, - - .pre_trans = rf, - - .tables = {&pd_drudfin_noE_sym16_drud}, - .ntables = 1, -}; - -Step -drfbfin_drfb = { - .shortname = "drfbfin", - .name = "DR finish on F/B without breaking DR", - - .final = true, - .is_done = is_solved, - .estimate = estimate_drudfin_drud, - .ready = check_drud, - .ready_msg = check_dr_msg, - .is_valid = always_valid, - .moveset = &moveset_drud, - - .pre_trans = fd, - - .tables = {&pd_drudfin_noE_sym16_drud}, - .ntables = 1, -}; - -/* HTR from DR */ -Step -htr_any = { - .shortname = "htr", - .name = "HTR from DR", - - .final = false, - .is_done = check_htr, - .estimate = estimate_htr_drud, - .ready = check_drud, - .ready_msg = check_drany_msg, - .is_valid = validate_singlecw_ending, - .moveset = &moveset_drud, - - .detect = detect_pretrans_drud, - - .tables = {&pd_htr_drud}, - .ntables = 1, -}; - -Step -htr_drud = { - .shortname = "htr-drud", - .name = "HTR from DR on U/D", - - .final = false, - .is_done = check_htr, - .estimate = estimate_htr_drud, - .ready = check_drud, - .ready_msg = check_dr_msg, - .is_valid = validate_singlecw_ending, - .moveset = &moveset_drud, - - .pre_trans = uf, - - .tables = {&pd_htr_drud}, - .ntables = 1, -}; - -Step -htr_drrl = { - .shortname = "htr-drrl", - .name = "HTR from DR on R/L", - - .final = false, - .is_done = check_htr, - .estimate = estimate_htr_drud, - .ready = check_drud, - .ready_msg = check_dr_msg, - .is_valid = validate_singlecw_ending, - .moveset = &moveset_drud, - - .pre_trans = rf, - - .tables = {&pd_htr_drud}, - .ntables = 1, -}; - -Step -htr_drfb = { - .shortname = "htr-drfb", - .name = "HTR from DR on F/B", - - .final = false, - .is_done = check_htr, - .estimate = estimate_htr_drud, - .ready = check_drud, - .ready_msg = check_dr_msg, - .is_valid = validate_singlecw_ending, - .moveset = &moveset_drud, - - .pre_trans = fd, - - .tables = {&pd_htr_drud}, - .ntables = 1, -}; - -/* HTR finish */ -Step -htrfin_htr = { - .shortname = "htrfin", - .name = "HTR finish without breaking HTR", - - .final = true, - .is_done = is_solved, - .estimate = estimate_htrfin_htr, - .ready = check_htr, - .ready_msg = check_htr_msg, - .is_valid = always_valid, - .moveset = &moveset_htr, - - .pre_trans = uf, - - .tables = {&pd_htrfin_htr}, - .ntables = 1, -}; - -Step *steps[] = { - &optimal_HTM, /* first is default */ - &optimal_light_HTM, - - &eofin_eo, - &eofbfin_eofb, - &eorlfin_eorl, - &eoudfin_eoud, - - &eoany_HTM, - &eofb_HTM, - &eorl_HTM, - &eoud_HTM, - - &coany_HTM, - &coud_HTM, - &corl_HTM, - &cofb_HTM, - - &coany_URF, - &coud_URF, - &corl_URF, - &cofb_URF, - - &drany_HTM, - &drud_HTM, - &drrl_HTM, - &drfb_HTM, - - &dr_eo, - &dr_eofb, - &dr_eorl, - &dr_eoud, - &drud_eofb, - &drrl_eofb, - &drud_eorl, - &drfb_eorl, - &drfb_eoud, - &drrl_eoud, - - &dranyfin_DR, - &drudfin_drud, - &drrlfin_drrl, - &drfbfin_drfb, - - &htr_any, - &htr_drud, - &htr_drrl, - &htr_drfb, - - &htrfin_htr, - - &cornershtr_HTM, - &cornershtr_URF, - &corners_HTM, - &corners_URF, - - NULL -}; - -/* Checkers and validators ***************************************************/ - -static bool -check_centers(Cube cube) -{ - return cube.cpos == 0; -} - -static bool -check_coud_HTM(Cube cube) -{ - return cube.coud == 0; -} - -static bool -check_coud_URF(Cube cube) -{ - Cube c2, c3; - - c2 = apply_move(z, cube); - c3 = apply_move(x, cube); - - return cube.coud == 0 || c2.coud == 0 || c3.coud == 0; -} - -static bool -check_corners_URF(Cube cube) -{ - Cube c; - Trans i; - - for (i = 0; i < NROTATIONS; i++) { - c = apply_alg(rotation_alg(i), cube); - if (c.cp && c.coud) - return true; - } - - return false; -} - -static bool -check_corners_HTM(Cube cube) -{ - return cube.cp == 0 && cube.coud == 0; -} - -static bool -check_cornershtr(Cube cube) -{ - return coord_cornershtr.index(cube) == 0; -} - -static bool -check_eofb(Cube cube) -{ - return cube.eofb == 0; -} - -static bool -check_drud(Cube cube) -{ - return cube.eofb == 0 && cube.eorl == 0 && cube.coud == 0; -} - -static bool -check_htr(Cube cube) -{ - return check_drud(cube) && coord_htr_drud.index(cube) == 0; -} - -static bool -always_valid(Alg *alg) -{ - return true; -} - -static bool -validate_singlecw_ending(Alg *alg) -{ - int i; - bool nor, inv; - Move l2 = NULLMOVE, l1 = NULLMOVE, l2i = NULLMOVE, l1i = NULLMOVE; - - for (i = 0; i < alg->len; i++) { - if (alg->inv[i]) { - l2i = l1i; - l1i = alg->move[i]; - } else { - l2 = l1; - l1 = alg->move[i]; - } - } - - nor = l1 ==base_move(l1) && (!commute(l1, l2) ||l2 ==base_move(l2)); - inv = l1i==base_move(l1i) && (!commute(l1i,l2i)||l2i==base_move(l2i)); - - return nor && inv; -} - -/* Public functions **********************************************************/ - -void -compute_ind(StepAlt *a, Cube *cube, uint64_t *ind) -{ - -} - -int -estimate_stepalt(StepAlt *a, uint64_t *ind) -{ - int i, ret, est[a->n_coord]; - - for (i = 0; i < a->n_coord; i++) { - est[i] = ptableval(a->pd[i], ind[i]); - if (est[i] == 0 && a->compact_pd[i]) - est[i] = ptableval(a->fallback_pd, ind[i] / a->fbmod); - } - - for (i = 0; i < a->n_dbtrick; i++) - if (est[a->dbtrick[i][0]] == est[a->dbtrick[i][1]] && - est[a->dbtrick[i][0]] == est[a->dbtrick[i][2]]) - est[a->dbtrick[i][0]] += 1; - - for (i = 0, ret = -1; i < a->n_coord; i++) - ret = max(ret, est[i]); - - return ret; -} - -void -prepare_step(Step *step, SolveOptions *opts) -{ - int i, j; - PDGenData pdg; - StepAlt *a; - - init_moveset(step->moveset); - pdg.moveset = step->moveset; - - for (i = 0; step->alt[i] != NULL; i++) { - a = step->alt[i]; - for (j = 0; j < a->n_coord; j++) { - gen_coord(a->coord[j]); - - pdg.coord = a->coord[j]; - pdg.compact = a->compact[j]; - pdg.pd = NULL; - - a->pd[j] = genptable(&pdg, opts->nthreads); - - if (a->compact_pd[j]) { - gen_coord(a->fallback_coord[j]); - - pdg.coord = a->fallback_coord[j]; - pdg.compact = false; - pdg.pd = NULL; - - a->fallback_pd[j] = - step->genptable(&pdg, opts->nthreads); - } - } - } -} diff --git a/old/solve_old.c b/old/solve_old.c @@ -1,447 +0,0 @@ -#define SOLVE_C - -#include "solve.h" - -/* Local functions ***********************************************************/ - -static void copy_dfsarg(DfsArg *src, DfsArg *dst); -static void dfs(DfsArg *arg); -static void dfs_add_sol(DfsArg *arg); -static void dfs_niss(DfsArg *arg); -static bool dfs_move_checkstop(DfsArg *arg); -static void * instance_thread(void *arg); -static void multidfs(DfsArg *arg); -static bool niss_makes_sense(DfsArg *arg); -static bool solvestop(int d, int op, SolveOptions *opts, AlgList *sols); - -/* Local functions ***********************************************************/ - -static void -copy_dfsarg(DfsArg *src, DfsArg *dst) -{ - int i; - - dst->cube = src->cube; - dst->t = src->t; - dst->s = src->s; - dst->opts = src->opts; - dst->d = src->d; - dst->bound = src->bound; /* In theory not needed */ - dst->niss = src->niss; - dst->sols = src->sols; - dst->sols_mutex = src->sols_mutex; - dst->current_alg = src->current_alg; - - for (i = 0; i < src->s->n_coord; i++) { - dst->ind[i].val = src->ind[i].val; - dst->ind[i].t = src->ind[i].t; - } - - src->s->copy_extra(src, dst); -} - -static void -dfs(DfsArg *arg) -{ - int i; - Move m, l0, l1; - DfsArg newarg; - - if (dfs_move_checkstop(arg)) - return; - - if (arg->bound == 0) { - if (arg->current_alg->len == arg->d) - dfs_add_sol(arg); - return; - } - - for (i = 0; arg->s->moveset->sorted_moves[i] != NULLMOVE; i++) { - m = arg->s->moveset->sorted_moves[i]; - if (arg->s->moveset->can_append(arg->current_alg, m, arg->niss) - && compare_last(arg->current_alg, m, arg->niss) >= 0) { - copy_dfsarg(arg, &newarg); - append_move(arg->current_alg, m, newarg.niss); - dfs(&newarg); - remove_last_move(arg->current_alg); - } - } - - if (niss_makes_sense(arg)) - dfs_niss(arg); -} - -static void -dfs_add_sol(DfsArg *arg) -{ - bool valid, accepted, nisscanc; - - valid = arg->s->is_valid==NULL || arg->s->is_valid(arg->current_alg); - accepted = valid || arg->opts->all; - nisscanc = arg->s->final && - arg->s->moveset->cancel_niss(arg->current_alg); - - if (accepted && !nisscanc) { - pthread_mutex_lock(arg->sols_mutex); - - if (arg->sols->len < arg->opts->max_solutions) { - append_alg(arg->sols, arg->current_alg); - transform_alg( - inverse_trans(arg->t), arg->sols->last->alg); - if (arg->opts->verbose) - print_alg(arg->sols->last->alg, false); - } - - pthread_mutex_unlock(arg->sols_mutex); - } -} - -static void -dfs_niss(DfsArg *arg) -{ - DfsArg newarg; - Alg *inv; - Cube *c; - - copy_dfsarg(arg, &newarg); - - /* Invert current alg and scramble */ - newarg.cube = malloc(sizeof(Cube)); - inv = inverse_alg(arg->current_alg); - c = malloc(sizeof(Cube)); - make_solved(newarg.cube); - apply_alg(inv, newarg.cube); - copy_cube(arg->cube, c); - invert_cube(c); - compose(c, newarg.cube); - - /* New indexes */ - compute_ind(newarg.s, newarg.cube, newarg.ind); - - newarg.niss = !(arg->niss); - - dfs(&newarg); - - free_alg(inv); - free(c); - free(newarg.cube); -} - -static bool -dfs_move_checkstop(DfsArg *arg) -{ - int i, goal, nsols; - Move mm; - Trans tt = uf; /* Avoid uninitialized warning */ - - /* Moving and computing bound */ - arg->bound = 0; - goal = arg->d - arg->current_alg->len; - for (i = 0; i < arg->s->n_coord; i++) { - if (arg->last[0] != NULLMOVE) { - mm = transform_move(arg->ind[i].t, arg->last[0]); - arg->ind[i].val = move_coord(arg->s->coord[i], - mm, arg->ind[i].val, &tt); - arg->ind[i].t = transform_trans(tt, arg->ind[i].t); - } - - arg->bound = - MAX(arg->bound, ptableval(arg->s->pd[i], arg->ind[i].val)); - if (arg->opts->can_niss && !arg->niss) - arg->bound = MIN(1, arg->bound); - - if (arg->bound > goal) - return true; - } - - pthread_mutex_lock(arg->sols_mutex); - nsols = arg->sols->len; - pthread_mutex_unlock(arg->sols_mutex); - - return nsols >= arg->opts->max_solutions; -} - -static void * -instance_thread(void *arg) -{ - bool b, inv; - Cube c; - Move m; - ThreadDataSolve *td; - AlgListNode *node; - DfsArg darg; - - td = (ThreadDataSolve *)arg; - - while (1) { - b = false; - - pthread_mutex_lock(td->start_mutex); - if ((node = *(td->node)) == NULL) - b = true; - else - *(td->node) = (*(td->node))->next; - pthread_mutex_unlock(td->start_mutex); - - if (b) - break; - - inv = node->alg->inv[0]; - m = node->alg->move[0]; - - copy_cube(td->arg.cube, &c); - if (inv) - invert_cube(&c); - - copy_dfsarg(&td->arg, &darg); - compute_ind(td->arg.s, &c, darg.ind); - darg.cube = &c; - - darg.niss = inv; - darg.current_alg = new_alg(""); - append_move(darg.current_alg, m, inv); - - dfs(&darg); - - free_alg(darg.current_alg); - } - - return NULL; -} - -static void -multidfs(DfsArg *arg) -{ - int i; - Cube local_cube; - Alg *alg; - AlgList *start; - AlgListNode **node; - pthread_t t[arg->opts->nthreads]; - ThreadDataSolve td[arg->opts->nthreads]; - pthread_mutex_t *start_mutex, *sols_mutex; - - node = malloc(sizeof(AlgListNode *)); - start_mutex = malloc(sizeof(pthread_mutex_t)); - sols_mutex = malloc(sizeof(pthread_mutex_t)); - - start = new_alglist(); - pthread_mutex_init(start_mutex, NULL); - pthread_mutex_init(sols_mutex, NULL); - - for (i = 0; arg->s->moveset->sorted_moves[i] != NULLMOVE; i++) { - alg = new_alg(""); - append_move(alg, arg->s->moveset->sorted_moves[i], false); - append_alg(start, alg); - if (arg->opts->can_niss && !arg->s->final) { - alg->inv[0] = true; - append_alg(start, alg); - } - free_alg(alg); - } - *node = start->first; - - copy_cube(arg->cube, &local_cube); - - for (i = 0; i < arg->opts->nthreads; i++) { - copy_dfsarg(arg, &(td[i].arg)); - td[i].arg.cube = &local_cube; - td[i].arg.sols_mutex = sols_mutex; - - td[i].thid = i; - td[i].start = start; - td[i].node = node; - td[i].start_mutex = start_mutex; - - pthread_create(&t[i], NULL, instance_thread, &td[i]); - } - - for (i = 0; i < arg->opts->nthreads; i++) - pthread_join(t[i], NULL); - - free_alglist(start); - free(node); - free(start_mutex); - free(sols_mutex); -} - -static bool -niss_makes_sense(DfsArg *arg) -{ - Move m, mm; - uint64_t u; - int i; - - if (arg->s->final || arg->niss || !arg->opts->can_niss) - return false; - - if (arg->current_alg->len_normal == 0) - return true; - - m = inverse_move(arg->last[0]); - for (i = 0; i < arg->s->n_coord; i++) { - mm = transform_move(arg->ind[i].t, m); - u = move_coord(arg->s->coord[i], mm, 0, NULL); - if (ptableval(arg->s->pd[i], u) > 0) - return true; - } - - return false; -} - -static bool -solvestop(int d, int op, SolveOptions *opts, AlgList *sols) -{ - bool opt_done, max_moves_exceeded, max_sols_exceeded; - - opt_done = opts->optimal != -1 && op != -1 && d > opts->optimal + op; - max_moves_exceeded = d > opts->max_moves; - max_sols_exceeded = sols->len >= opts->max_solutions; - - return opt_done || max_moves_exceeded || max_sols_exceeded; -} - -/* Public functions **********************************************************/ - -AlgList * -solve(Cube *cube, ChoiceStep *cs, SolveOptions *opts) -{ - int i, j, d, op, est; - bool ready[99], one_ready, zerosol; - Movable ind[99][10]; - AlgList *s; - Cube *c[99]; - DfsArg arg[99]; - - prepare_cs(cs, opts); - s = new_alglist(); - - for (i = 0, one_ready = false; cs->step[i] != NULL; i++) { - c[i] = malloc(sizeof(Cube)); - copy_cube(cube, c[i]); - apply_trans(cs->t[i], c[i]); - - arg[i].cube = c[i]; - arg[i].t = cs->t[i]; - arg[i].s = cs->step[i]; - arg[i].opts = opts; - arg[i].sols = s; - - if ((ready[i] = cs->step[i]->ready(c[i]))) { - one_ready = true; - /* Only for local use for 0 moves solutions */ - compute_ind(cs->step[i], c[i], ind[i]); - } - } - if (!one_ready) { - fprintf(stderr, "Cube not ready for solving step: "); - fprintf(stderr, "%s\n", cs->ready_msg); - return s; - } - - /* If the empty moves sequence is a solution for one of the - * alternatives, all longer solutions will be discarded, so we may - * just set its ready[] value to false. If the solution is accepted - * we append it and start searching from d = 1. */ - for (i = 0, zerosol = false; cs->step[i] != NULL; i++) { - if (ready[i]) { - est = 0; - for (j = 0; j < cs->step[i]->n_coord; j++) - est = MAX(est, ptableval(cs->step[i]->pd[j], - ind[i][j].val)); - if (est == 0) { - ready[i] = false; - zerosol = true; - } - } - } - if (zerosol && opts->min_moves == 0) { - append_alg(s, new_alg("")); - opts->min_moves = 1; - if (opts->verbose) - printf("Step is already solved" - "(empty alg is a solution)\n"); - } - - for (d = opts->min_moves, op = -1; !solvestop(d, op, opts, s); d++) { - if (opts->verbose) - fprintf(stderr, "Searching depth %d\n", d); - - for (i=0; cs->step[i]!=NULL && !solvestop(d,op,opts,s); i++) { - if (!ready[i]) - continue; - - arg[i].d = d; - multidfs(&arg[i]); - - if (s->len > 0 && op == -1) - op = d; - } - } - - for (i = 0; cs->step[i] != NULL; i++) - free(c[i]); - - return s; -} - -/* TODO: make more general! */ -Alg * -solve_2phase(Cube *cube, int nthreads) -{ - int bestlen, newb; - Alg *bestalg, *ret; - AlgList *sols1, *sols2; - AlgListNode *i; - Cube c; - SolveOptions opts1, opts2; - - opts1.min_moves = 0; - opts1.max_moves = 13; - opts1.max_solutions = 20; - opts1.nthreads = nthreads; - opts1.optimal = 3; - opts1.can_niss = false; - opts1.verbose = false; - opts1.all = true; - - opts2.min_moves = 0; - opts2.max_moves = 19; - opts2.max_solutions = 1; - opts2.nthreads = nthreads; - opts2.can_niss = false; - opts2.verbose = false; - - /* We skip step1 if it is solved on U/D */ - if (check_drud(cube)) { - sols1 = new_alglist(); - append_alg(sols1, new_alg("")); - } else { - sols1 = solve(cube, &drud_HTM, &opts1); - } - bestalg = new_alg(""); - bestlen = 999; - for (i = sols1->first; i != NULL; i = i->next) { - copy_cube(cube, &c); - apply_alg(i->alg, &c); - sols2 = solve(&c, &dranyfin_DR, &opts2); - - if (sols2->len > 0) { - newb = i->alg->len + sols2->first->alg->len; - if (newb < bestlen) { - bestlen = newb; - copy_alg(i->alg, bestalg); - compose_alg(bestalg, sols2->first->alg); - } - } - - free_alglist(sols2); - } - - free_alglist(sols1); - - ret = cleanup(bestalg); - free_alg(bestalg); - - return ret; -} diff --git a/old/solve_old.h b/old/solve_old.h @@ -1,9 +0,0 @@ -#ifndef SOLVE_H -#define SOLVE_H - -#include "movesets.h" - -AlgList * solve(Cube *cube, ChoiceStep *cs, SolveOptions *opts); -Alg * solve_2phase(Cube *cube, int nthreads); - -#endif diff --git a/src/alg.c b/src/alg.c @@ -1,459 +0,0 @@ -#define ALG_C - -#include "alg.h" - -static int axis(Move m); -static void free_alglistnode(AlgListNode *aln); -static void realloc_alg(Alg *alg, int n); - -void -append_alg(AlgList *l, Alg *alg) -{ - AlgListNode *node = malloc(sizeof(AlgListNode)); - int i; - - node->alg = new_alg(""); - for (i = 0; i < alg->len; i++) - append_move(node->alg, alg->move[i], alg->inv[i]); - node->next = NULL; - - if (++l->len == 1) - l->first = node; - else - l->last->next = node; - l->last = node; -} - -void -append_move(Alg *alg, Move m, bool inverse) -{ - if (alg->len == alg->allocated) - realloc_alg(alg, 2*alg->len); - - alg->move[alg->len] = m; - alg->inv [alg->len] = inverse; - alg->len++; - - if (inverse) - alg->move_inverse[alg->len_inverse++] = m; - else - alg->move_normal[alg->len_normal++] = m; -} - -static int -axis(Move m) -{ - static int aux[] = { - [NULLMOVE] = 0, - - [U] = 1, [U2] = 1, [U3] = 1, - [D] = 1, [D2] = 1, [D3] = 1, - [Uw] = 1, [Uw2] = 1, [Uw3] = 1, - [Dw] = 1, [Dw2] = 1, [Dw3] = 1, - [E] = 1, [E2] = 1, [E3] = 1, - [y] = 1, [y2] = 1, [y3] = 1, - - [R] = 2, [R2] = 2, [R3] = 2, - [L] = 2, [L2] = 2, [L3] = 2, - [Rw] = 2, [Rw2] = 2, [Rw3] = 2, - [Lw] = 2, [Lw2] = 2, [Lw3] = 2, - [M] = 2, [M2] = 2, [M3] = 2, - [x] = 2, [x2] = 2, [x3] = 2, - - [F] = 3, [F2] = 3, [F3] = 3, - [B] = 3, [B2] = 3, [B3] = 3, - [Fw] = 3, [Fw2] = 3, [Fw3] = 3, - [Bw] = 3, [Bw2] = 3, [Bw3] = 3, - [S] = 3, [S2] = 3, [S3] = 3, - [z] = 3, [z2] = 3, [z3] = 3, - }; - - return aux[m]; -} - -Move -base_move(Move m) -{ - if (m == NULLMOVE) - return NULLMOVE; - else - return m - (m-1)%3; -} - -bool -commute(Move m1, Move m2) -{ - return axis(m1) == axis(m2); -} - -int -compare(Move m1, Move m2) -{ - if (!commute(m1, m2)) - return 0; - - return m1 < m2 ? 1 : -1; -} - -int -compare_last(Alg *alg, Move m, bool inverse) -{ - Move last; - int n; - - if (inverse) { - n = alg->len_inverse; - last = n > 0 ? alg->move_inverse[n-1] : NULLMOVE; - } else { - n = alg->len_normal; - last = n > 0 ? alg->move_normal[n-1] : NULLMOVE; - } - - return compare(last, m); -} - -void -compose_alg(Alg *alg1, Alg *alg2) -{ - int i; - - for (i = 0; i < alg2->len; i++) - append_move(alg1, alg2->move[i], alg2->inv[i]); -} - -void -copy_alg(Alg *src, Alg *dst) -{ - dst->len = dst->len_normal = dst->len_inverse = 0; - compose_alg(dst, src); -} - -void -free_alg(Alg *alg) -{ - free(alg->move); - free(alg->inv); - free(alg); -} - -void -free_alglist(AlgList *l) -{ - AlgListNode *aux, *i = l->first; - - while (i != NULL) { - aux = i->next; - free_alglistnode(i); - i = aux; - } - free(l); -} - -static void -free_alglistnode(AlgListNode *aln) -{ - free_alg(aln->alg); - free(aln); -} - -Alg * -inverse_alg(Alg *alg) -{ - Alg *ret = new_alg(""); - int i; - - for (i = alg->len-1; i >= 0; i--) - append_move(ret, inverse_move(alg->move[i]), alg->inv[i]); - - return ret; -} - -Move -inverse_move(Move m) -{ - return m == NULLMOVE ? NULLMOVE : m + 2 - 2*((m-1) % 3); -} - -char * -move_string(Move m) -{ - static char move_string_aux[NMOVES][7] = { - [NULLMOVE] = "-", - [U] = "U", [U2] = "U2", [U3] = "U\'", - [D] = "D", [D2] = "D2", [D3] = "D\'", - [R] = "R", [R2] = "R2", [R3] = "R\'", - [L] = "L", [L2] = "L2", [L3] = "L\'", - [F] = "F", [F2] = "F2", [F3] = "F\'", - [B] = "B", [B2] = "B2", [B3] = "B\'", - [Uw] = "Uw", [Uw2] = "Uw2", [Uw3] = "Uw\'", - [Dw] = "Dw", [Dw2] = "Dw2", [Dw3] = "Dw\'", - [Rw] = "Rw", [Rw2] = "Rw2", [Rw3] = "Rw\'", - [Lw] = "Lw", [Lw2] = "Lw2", [Lw3] = "Lw\'", - [Fw] = "Fw", [Fw2] = "Fw2", [Fw3] = "Fw\'", - [Bw] = "Bw", [Bw2] = "Bw2", [Bw3] = "Bw\'", - [M] = "M", [M2] = "M2", [M3] = "M\'", - [E] = "E", [E2] = "E2", [E3] = "E\'", - [S] = "S", [S2] = "S2", [S3] = "S\'", - [x] = "x", [x2] = "x2", [x3] = "x\'", - [y] = "y", [y2] = "y2", [y3] = "y\'", - [z] = "z", [z2] = "z2", [z3] = "z\'", - }; - - return move_string_aux[m]; -} - -Alg * -new_alg(char *str) -{ - Alg *alg; - int i; - bool niss, move_read; - Move j, m; - - alg = malloc(sizeof(Alg)); - alg->allocated = 30; - alg->move = malloc(alg->allocated * sizeof(Move)); - alg->inv = malloc(alg->allocated * sizeof(bool)); - alg->move_normal = malloc(alg->allocated * sizeof(Move)); - alg->move_inverse = malloc(alg->allocated * sizeof(Move)); - alg->len = 0; - alg->len_normal = 0; - alg->len_inverse = 0; - - niss = false; - for (i = 0; str[i]; i++) { - if (str[i] == ' ' || str[i] == '\t' || str[i] == '\n') - continue; - - if (str[i] == '(' && niss) { - fprintf(stderr, "Error reading moves: nested ( )\n"); - alg->len = alg->len_normal = alg->len_inverse = 0; - return alg; - } - - if (str[i] == ')' && !niss) { - fprintf(stderr, "Error reading moves: unmatched )\n"); - alg->len = alg->len_normal = alg->len_inverse = 0; - return alg; - } - - if (str[i] == '(' || str[i] == ')') { - niss = !niss; - continue; - } - - /* Single slash for comments */ - if (str[i] == '/') { - while (str[i] && str[i] != '\n') - i++; - - if (!str[i]) - i--; - - continue; - } - - move_read = false; - for (j = U; j < NMOVES; j++) { - if (str[i] == move_string(j)[0] || - (str[i] >= 'a' && str[i] <= 'z' && - str[i] == move_string(j)[0]-('A'-'a') && j<=B)) { - m = j; - if (str[i] >= 'a' && str[i] <= 'z' && j<=B) { - m += Uw - U; - } - if (m <= B && str[i+1]=='w') { - m += Uw - U; - i++; - } - if (str[i+1]=='2') { - m += 1; - i++; - } else if (str[i+1] == '\'' || - str[i+1] == '3' || - str[i+1] == '`' ) { - m += 2; - i++; - } else if ((int)str[i+1] == -62 && - (int)str[i+2] == -76) { - /* Weird apostrophe */ - m += 2; - i += 2; - } else if ((int)str[i+1] == -30 && - (int)str[i+2] == -128 && - (int)str[i+3] == -103) { - /* MacOS apostrophe */ - m += 2; - i += 3; - } - append_move(alg, m, niss); - move_read = true; - break; - } - } - - if (!move_read) { - free(alg); - return new_alg(""); - } - } - - if (niss) { - fprintf(stderr, "Error reading moves: unmatched (\n"); - alg->len = alg->len_normal = alg->len_inverse = 0; - } - - return alg; -} - -AlgList * -new_alglist() -{ - AlgList *ret = malloc(sizeof(AlgList)); - - ret->len = 0; - ret->first = NULL; - ret->last = NULL; - - return ret; -} - -Alg * -on_inverse(Alg *alg) -{ - Alg *ret = new_alg(""); - int i; - - for (i = 0; i < alg->len; i++) - append_move(ret, alg->move[i], !alg->inv[i]); - - return ret; -} - -void -print_alg(Alg *alg, bool l) -{ - char fill[4]; - int i; - bool niss = false; - - for (i = 0; i < alg->len; i++) { - if (!niss && alg->inv[i]) - strcpy(fill, i == 0 ? "(" : " ("); - if (niss && !alg->inv[i]) - strcpy(fill, ") "); - if (niss == alg->inv[i]) - strcpy(fill, i == 0 ? "" : " "); - - printf("%s%s", fill, move_string(alg->move[i])); - niss = alg->inv[i]; - } - - if (niss) - printf(")"); - if (l) - printf(" (%d)", alg->len); - - printf("\n"); -} - -void -print_alglist(AlgList *al, bool l) -{ - AlgListNode *i; - - for (i = al->first; i != NULL; i = i->next) - print_alg(i->alg, l); -} - -static void -realloc_alg(Alg *alg, int n) -{ - if (alg == NULL) { - fprintf(stderr, "Error: trying to reallocate NULL alg.\n"); - return; - } - - if (n < alg->len) { - fprintf(stderr, "Error: alg too long for reallocation "); - fprintf(stderr, "(%d vs %d)\n", alg->len, n); - return; - } - - if (n > 1000000) { - fprintf(stderr, "Warning: very long alg,"); - fprintf(stderr, "something might go wrong.\n"); - } - - alg->move = realloc(alg->move, n * sizeof(int)); - alg->inv = realloc(alg->inv, n * sizeof(int)); - alg->move_normal = realloc(alg->move_normal, n * sizeof(int)); - alg->move_inverse = realloc(alg->move_inverse, n * sizeof(int)); - alg->allocated = n; -} - -void -remove_last_move(Alg *a) -{ - a->len--; - - if (a->inv[a->len]) - a->len_inverse--; - else - a->len_normal--; -} - -void -swapmove(Move *m1, Move *m2) -{ - Move aux; - - aux = *m1; - *m1 = *m2; - *m2 = aux; -} - -char * -trans_string(Trans t) -{ - static char trans_string_aux[NTRANS][20] = { - [uf] = "uf", [ur] = "ur", [ub] = "ub", [ul] = "ul", - [df] = "df", [dr] = "dr", [db] = "db", [dl] = "dl", - [rf] = "rf", [rd] = "rd", [rb] = "rb", [ru] = "ru", - [lf] = "lf", [ld] = "ld", [lb] = "lb", [lu] = "lu", - [fu] = "fu", [fr] = "fr", [fd] = "fd", [fl] = "fl", - [bu] = "bu", [br] = "br", [bd] = "bd", [bl] = "bl", - - [uf_mirror] = "uf*", [ur_mirror] = "ur*", - [ub_mirror] = "ub*", [ul_mirror] = "ul*", - [df_mirror] = "df*", [dr_mirror] = "dr*", - [db_mirror] = "db*", [dl_mirror] = "dl*", - [rf_mirror] = "rf*", [rd_mirror] = "rd*", - [rb_mirror] = "rb*", [ru_mirror] = "ru*", - [lf_mirror] = "lf*", [ld_mirror] = "ld*", - [lb_mirror] = "lb*", [lu_mirror] = "lu*", - [fu_mirror] = "fu*", [fr_mirror] = "fr*", - [fd_mirror] = "fd*", [fl_mirror] = "fl*", - [bu_mirror] = "bu*", [br_mirror] = "br*", - [bd_mirror] = "bd*", [bl_mirror] = "bl*", - }; - - return trans_string_aux[t]; -} - -Alg * -unniss(Alg *alg) -{ - int i; - Alg *ret; - - ret = new_alg(""); - - for (i = 0; i < alg->len_normal; i++) - append_move(ret, alg->move_normal[i], false); - - for (i = 0; i < alg->len_inverse; i++) - append_move(ret, inverse_move(alg->move_inverse[i]), false); - - return ret; -} diff --git a/src/alg.h b/src/alg.h @@ -1,35 +0,0 @@ -#ifndef ALG_H -#define ALG_H - -#include <stdio.h> -#include <stdlib.h> -#include <string.h> - -#include "cubetypes.h" -#include "utils.h" - -void append_alg(AlgList *l, Alg *alg); -void append_move(Alg *alg, Move m, bool inverse); -Move base_move(Move m); -int compare(Move m1, Move m2); /* Return 1 (m1<m2), 0 or -1 (m1>m2) */ -int compare_last(Alg *alg, Move m, bool inverse); -void compose_alg(Alg *alg1, Alg *alg2); -bool commute(Move m1, Move m2); -void copy_alg(Alg *src, Alg *dst); -void free_alg(Alg *alg); -void free_alglist(AlgList *l); -Alg * inverse_alg(Alg *alg); -Move inverse_move(Move m); -char * move_string(Move m); -Alg * new_alg(char *str); -AlgList * new_alglist(); -Alg * on_inverse(Alg *alg); -void print_alg(Alg *alg, bool l); -void print_alglist(AlgList *al, bool l); -void remove_last_move(Alg *alg); -void swapmove(Move *m1, Move *m2); -char * trans_string(Trans t); /* Here because similar to move_string, move? */ -Alg * unniss(Alg *alg); - -#endif - diff --git a/src/commands.c b/src/commands.c @@ -1,569 +0,0 @@ -#define COMMANDS_C - -#include "commands.h" - -static bool read_cs(CommandArgs *args, char *str); -static bool read_scrtype(CommandArgs *args, char *str); -static bool read_scramble(int c, char **v, CommandArgs *args); - -/* Arg parsing functions implementation **************************************/ - -CommandArgs * -solve_parse_args(int c, char **v) -{ - int i; - bool infinitesols, fixedmsols; - long val; - - CommandArgs *a = new_args(); - - a->opts->min_moves = 0; - a->opts->max_moves = 20; - a->opts->max_solutions = 1; - a->opts->nthreads = 1; - a->opts->optimal = -1; - a->opts->can_niss = false; - a->opts->verbose = false; - a->opts->all = false; - a->opts->print_number = true; - a->opts->count_only = false; - - fixedmsols = false; - infinitesols = false; - - for (i = 0; i < c; i++) { - if (!strcmp(v[i], "-m") && i+1 < c) { - val = strtol(v[++i], NULL, 10); - if (val < 0 || val > 100) { - fprintf(stderr, - "Invalid min number of moves" - "(0 <= N <= 100).\n"); - return a; - } - a->opts->min_moves = val; - } else if (!strcmp(v[i], "-M") && i+1 < c) { - val = strtol(v[++i], NULL, 10); - if (val < 0 || val > 100) { - fprintf(stderr, - "Invalid max number of moves" - "(0 <= N <= 100).\n"); - return a; - } - a->opts->max_moves = val; - infinitesols = true; - } else if (!strcmp(v[i], "-t") && i+1 < c) { - val = strtol(v[++i], NULL, 10); - if (val < 1 || val > 64) { - fprintf(stderr, - "Invalid number of threads." - "1 <= t <= 64\n"); - return a; - } - a->opts->nthreads = val; - } else if (!strcmp(v[i], "-n") && i+1 < c) { - val = strtol(v[++i], NULL, 10); - if (val < 1 || val > 1000000) { - fprintf(stderr, - "Invalid number of solutions.\n"); - return a; - } - a->opts->max_solutions = val; - fixedmsols = true; - } else if (!strcmp(v[i], "-o")) { - a->opts->optimal = 0; - infinitesols = true; - } else if (!strcmp(v[i], "-O") && i+1 < c) { - val = strtol(v[++i], NULL, 10); - if (val < 0 || val > 100 || - (val == 0 && strcmp("0", v[i]))) { - fprintf(stderr, - "Invalid max number of moves" - " (0 <= N <= 100).\n"); - return a; - } - a->opts->optimal = val; - infinitesols = true; - } else if (!strcmp(v[i], "-N")) { - a->opts->can_niss = true; - } else if (!strcmp(v[i], "-i")) { - a->scrstdin = true; - } else if (!strcmp(v[i], "-v")) { - a->opts->verbose = true; - } else if (!strcmp(v[i], "-a")) { - a->opts->all = true; - } else if (!strcmp(v[i], "-p")) { - a->opts->print_number = false; - } else if (!strcmp(v[i], "-c")) { - a->opts->count_only = true; - } else if (!read_cs(a, v[i])) { - break; - } - } - - if (infinitesols && !fixedmsols) - a->opts->max_solutions = 1000000; /* 1M = +infty */ - - a->success = (a->scrstdin && i == c) || read_scramble(c-i, &v[i], a); - return a; -} - -CommandArgs * -scramble_parse_args(int c, char **v) -{ - int i; - long val; - - CommandArgs *a = new_args(); - - a->success = true; - a->n = 1; - - for (i = 0; i < c; i++) { - if (!strcmp(v[i], "-n") && i+1 < c) { - val = strtol(v[++i], NULL, 10); - if (val < 1 || val > 1000000) { - fprintf(stderr, - "Invalid number of scrambles.\n"); - a->success = false; - return a; - } - a->n = val; - } else if (!read_scrtype(a, v[i])) { - a->success = false; - return a; - } - } - - return a; -} - -CommandArgs * -gen_parse_args(int c, char **v) -{ - int val; - CommandArgs *a = new_args(); - - a->opts->nthreads = 64; - a->success = false; - - if (c == 0) { - a->success = true; - } else { - if (!strcmp(v[0], "-t") && c > 1) { - val = strtol(v[1], NULL, 10); - if (val < 1 || val > 64) { - fprintf(stderr, - "Invalid number of threads." - "1 <= t <= 64\n"); - return a; - } - a->opts->nthreads = val; - a->success = true; - } - } - - return a; -} - -CommandArgs * -help_parse_args(int c, char **v) -{ - int i; - CommandArgs *a = new_args(); - - if (c == 1) { - for (i = 0; commands[i] != NULL; i++) - if (!strcmp(v[0], commands[i]->name)) - a->command = commands[i]; - if (a->command == NULL) - fprintf(stderr, "%s: command not found\n", v[0]); - } - - a->success = c == 0 || (c == 1 && a->command != NULL); - return a; -} - -CommandArgs * -parse_only_scramble(int c, char **v) -{ - CommandArgs *a = new_args(); - - if (!strcmp(v[0], "-i")) { - a->scrstdin = true; - a->success = c == 1; - } else { - a->success = read_scramble(c, v, a); - } - - return a; -} - -CommandArgs * -parse_no_arg(int c, char **v) -{ - CommandArgs *a = new_args(); - - a->success = true; - - return a; -} - -/* Exec functions implementation *********************************************/ - -void -solve_exec(CommandArgs *args) -{ - Cube c; - AlgList *sols; - Solver *solver[99]; - Threader *threader; - - make_solved(&c); - apply_alg(args->scramble, &c); -/* TODO: adjust */ -/* threader = &threader_single;*/ - threader = &threader_eager; - -/* TODO: adjust */ - int i; - for (i = 0; args->cs->step[i] != NULL; i++) - solver[i] = new_stepsolver_lazy(args->cs->step[i]); - solver[i] = NULL; - sols = solve(&c, args->opts, solver, threader); - - if (args->opts->count_only) - printf("%d\n", sols->len); - else - print_alglist(sols, args->opts->print_number); - - free_alglist(sols); -} - -void -scramble_exec(CommandArgs *args) -{ - Cube cube; - Alg *scr, *ruf, *aux; - int i, j, eo, ep, co, cp; - uint64_t ui, uj, uk; - - srand(time(NULL)); - - for (i = 0; i < args->n; i++) { - - if (!strcmp(args->scrtype, "dr")) { - ui = rand() % FACTORIAL8; - uj = rand() % FACTORIAL8; - uk = rand() % FACTORIAL4; - - make_solved(&cube); - index_to_perm(ui, 8, cube.cp); - index_to_perm(uj, 8, cube.ep); - index_to_perm(uk, 4, cube.ep + 8); - for (j = 8; j < 12; j++) - cube.ep[j] += 8; - } else if (!strcmp(args->scrtype, "htr")) { - make_solved(&cube); - /* TODO */ - } else { - ep = rand() % FACTORIAL12; - cp = rand() % FACTORIAL8; - eo = rand() % POW2TO11; - co = rand() % POW3TO7; - - if (!strcmp(args->scrtype, "eo")) { - eo = 0; - } else if (!strcmp(args->scrtype, "corners")) { - eo = 0; - ep = 0; - } else if (!strcmp(args->scrtype, "edges")) { - co = 0; - cp = 0; - } - - make_solved(&cube); - index_to_perm(ep, 12, cube.ep); - index_to_perm(cp, 8, cube.cp); - int_to_sum_zero_array(eo, 2, 12, cube.eo); - int_to_sum_zero_array(co, 3, 8, cube.co); - } - - if (!is_admissible(&cube)) { - if (!strcmp(args->scrtype, "corners")) - swap(&cube.cp[UFR], &cube.cp[UFL]); - else - swap(&cube.ep[UF], &cube.ep[UB]); - } - - /* TODO: can be optimized for htr and dr using htrfin, drfin */ - /* - TODO: solve_2phase was removed - scr = solve_2phase(&cube, 1); - */ - - if (!strcmp(args->scrtype, "fmc")) { - aux = new_alg(""); - copy_alg(scr, aux); - /* Trick to rufify for free: rotate the scramble * - * so that it does not start with F or end with R */ - for (j = 0; j < NROTATIONS; j++) { - if (base_move(scr->move[0]) != F && - base_move(scr->move[0]) != B && - base_move(scr->move[scr->len-1]) != R && - base_move(scr->move[scr->len-1]) != L) - break; - copy_alg(aux, scr); - transform_alg(j, scr); - } - copy_alg(scr, aux); - ruf = new_alg("R' U' F"); - copy_alg(ruf, scr); - compose_alg(scr, aux); - compose_alg(scr, ruf); - free_alg(aux); - free_alg(ruf); - } - print_alg(scr, false); - free_alg(scr); - } -} - -void -gen_exec(CommandArgs *args) -{ -/* TODO: - int i; - - fprintf(stderr, "Generating coordinates...\n"); - fprintf(stderr, "Generating pruning tables...\n"); - for (i = 0; all_pd[i] != NULL; i++) - genptable(all_pd[i], args->opts->nthreads); -*/ - - fprintf(stderr, "Done!\n"); -} - -void -invert_exec(CommandArgs *args) -{ - Alg *inv; - - inv = inverse_alg(args->scramble); - print_alg(inv, false); - - free_alg(inv); -} - -void -steps_exec(CommandArgs *args) -{ - int i; - - for (i = 0; csteps[i] != NULL; i++) - printf("%-15s %s\n", csteps[i]->shortname, csteps[i]->name); -} - -void -commands_exec(CommandArgs *args) -{ - int i; - - for (i = 0; commands[i] != NULL; i++) - printf("%s\n", commands[i]->usage); - -} - -void -freemem_exec(CommandArgs *args) -{ -/* TODO: - int i; - - for (i = 0; all_pd[i] != NULL; i++) - free_pd(all_pd[i]); - - for (i = 0; all_sd[i] != NULL; i++) - free_sd(all_sd[i]); -*/ -} - -void -print_exec(CommandArgs *args) -{ - Cube c; - - make_solved(&c); - apply_alg(args->scramble, &c); - print_cube(&c); -} - -/* -void -twophase_exec(CommandArgs *args) -{ - Cube c; - Alg *sol; - - make_solved(&c); - apply_alg(args->scramble, &c); - sol = solve_2phase(&c, 1); - - print_alg(sol, false); - free_alg(sol); -} -*/ - -void -help_exec(CommandArgs *args) -{ - if (args->command == NULL) { - printf( - "Use the nissy command \"help COMMAND\" for a short " - "description of a specific command.\n" - "Use the nissy command \"commands\" for a list of " - "available commands.\n" - "See the manual page for more details. The manual" - " page is available with \"man nissy\" on a UNIX" - " system (such as Linux or MacOS) or in pdf and html" - " format in the docs folder.\n" - "Nissy is available for free at " - "https://nissy.tronto.net\n" - ); - } else { - printf("Command %s: %s\nusage: %s\n", args->command->name, - args->command->description, args->command->usage); - } -} - -void -quit_exec(CommandArgs *args) -{ - exit(0); -} - -void -cleanup_exec(CommandArgs *args) -{ - Alg *alg; - - alg = cleanup(args->scramble); - print_alg(alg, false); - - free_alg(alg); -} - -void -unniss_exec(CommandArgs *args) -{ - Alg *aux; - - aux = unniss(args->scramble); - print_alg(aux, false); - free(aux); -} - -void -version_exec(CommandArgs *args) -{ - printf(VERSION"\n"); -} - -/* Local functions implementation ********************************************/ - -static bool -read_scramble(int c, char **v, CommandArgs *args) -{ - int i, k, n; - unsigned int j; - char *algstr; - - if (c < 1) { - fprintf(stderr, "Error: no scramble given?\n"); - return false; - } - - for(n = 0, i = 0; i < c; i++) - n += strlen(v[i]); - - algstr = malloc((n + 1) * sizeof(char)); - k = 0; - for (i = 0; i < c; i++) - for (j = 0; j < strlen(v[i]); j++) - algstr[k++] = v[i][j]; - algstr[k] = 0; - - args->scramble = new_alg(algstr); - free(algstr); - - if (args->scramble->len == 0) - fprintf(stderr, "Error reading scramble\n"); - - return args->scramble->len > 0; -} - -static bool -read_scrtype(CommandArgs *args, char *str) -{ - int i; - static char *scrtypes[20] = - { "eo", "corners", "edges", "fmc", "dr", "htr", NULL }; - - for (i = 0; scrtypes[i] != NULL; i++) { - if (!strcmp(scrtypes[i], str)) { - strcpy(args->scrtype, scrtypes[i]); - return true; - } - } - - return false; -} - -static bool -read_cs(CommandArgs *args, char *str) -{ - int i; - - for (i = 0; csteps[i] != NULL; i++) { - if (!strcmp(csteps[i]->shortname, str)) { - args->cs = csteps[i]; - return true; - } - } - - return false; -} - -/* Public functions implementation *******************************************/ - -void -free_args(CommandArgs *args) -{ - if (args == NULL) - return; - - if (args->scramble != NULL) - free_alg(args->scramble); - if (args->opts != NULL) - free(args->opts); - - /* step and command must not be freed, they are static! */ - - free(args); -} - -CommandArgs * -new_args() -{ - CommandArgs *args = malloc(sizeof(CommandArgs)); - - args->success = false; - args->scrstdin = false; - args->scramble = NULL; /* initialized in read_scramble */ - args->opts = malloc(sizeof(SolveOptions)); - - /* step and command are static */ - args->cs = csteps[0]; /* default: first step in list */ - args->command = NULL; - - return args; -} diff --git a/src/commands.h b/src/commands.h @@ -1,211 +0,0 @@ -#ifndef COMMANDS_H -#define COMMANDS_H - -#include <time.h> - -#include "solve.h" -#include "steps.h" -#include "solver_step.h" -#include "threader_single.h" -#include "threader_eager.h" - -void free_args(CommandArgs *args); -CommandArgs * new_args(); - -/* Arg parsing functions *****************************************************/ - -CommandArgs * gen_parse_args(int c, char **v); -CommandArgs * help_parse_args(int c, char **v); -CommandArgs * parse_only_scramble(int c, char **v); -CommandArgs * parse_no_arg(int c, char **v); -CommandArgs * solve_parse_args(int c, char **v); -CommandArgs * scramble_parse_args(int c, char **v); - -/* Exec functions ************************************************************/ - -void gen_exec(CommandArgs *args); -void cleanup_exec(CommandArgs *args); -void invert_exec(CommandArgs *args); -void solve_exec(CommandArgs *args); -void scramble_exec(CommandArgs *args); -void steps_exec(CommandArgs *args); -void commands_exec(CommandArgs *args); -void freemem_exec(CommandArgs *args); -void print_exec(CommandArgs *args); -/*void twophase_exec(CommandArgs *args);*/ -void help_exec(CommandArgs *args); -void quit_exec(CommandArgs *args); -void unniss_exec(CommandArgs *args); -void version_exec(CommandArgs *args); - -/* Commands ******************************************************************/ - -#ifndef COMMANDS_C - -extern Command cleanup_cmd; -extern Command commands_cmd; -extern Command freemem_cmd; -extern Command gen_cmd; -extern Command help_cmd; -extern Command invert_cmd; -extern Command print_cmd; -extern Command quit_cmd; -extern Command scramble_cmd; -extern Command solve_cmd; -extern Command steps_cmd; -extern Command unniss_cmd; -extern Command version_cmd; - -extern Command *commands[]; - -#else - -Command -solve_cmd = { - .name = "solve", - .usage = "solve STEP [OPTIONS] SCRAMBLE", - .description = "Solve a step; see command steps for a list of steps", - .parse_args = solve_parse_args, - .exec = solve_exec -}; - -Command -scramble_cmd = { - .name = "scramble", - .usage = "scramble [TYPE] [-n N]", - .description = "Get a random-position scramble", - .parse_args = scramble_parse_args, - .exec = scramble_exec, -}; - -Command -gen_cmd = { - .name = "gen", - .usage = "gen [-t N]", - .description = "Generate all tables [using N threads]", - .parse_args = gen_parse_args, - .exec = gen_exec -}; - -Command -invert_cmd = { - .name = "invert", - .usage = "invert SCRAMBLE]", - .description = "Invert a scramble", - .parse_args = parse_only_scramble, - .exec = invert_exec, -}; - -Command -steps_cmd = { - .name = "steps", - .usage = "steps", - .description = "List available steps", - .parse_args = parse_no_arg, - .exec = steps_exec -}; - -Command -commands_cmd = { - .name = "commands", - .usage = "commands", - .description = "List available commands", - .parse_args = parse_no_arg, - .exec = commands_exec -}; - -Command -freemem_cmd = { - .name = "freemem", - .usage = "freemem", - .description = "free large tables from RAM", - .parse_args = parse_no_arg, - .exec = freemem_exec, -}; - -Command -print_cmd = { - .name = "print", - .usage = "print SCRAMBLE", - .description = "Print written description of the cube", - .parse_args = parse_only_scramble, - .exec = print_exec, -}; - -Command -help_cmd = { - .name = "help", - .usage = "help [COMMAND]", - .description = "Display nissy manual page or help on specific command", - .parse_args = help_parse_args, - .exec = help_exec, -}; - -/* -Command -twophase_cmd = { - .name = "twophase", - .usage = "twophase", - .description = "Find a solution quickly using a 2-phase method", - .parse_args = parse_only_scramble, - .exec = twophase_exec, -}; -*/ - -Command -quit_cmd = { - .name = "quit", - .usage = "quit", - .description = "Quit nissy", - .parse_args = parse_no_arg, - .exec = quit_exec, -}; - -Command -cleanup_cmd = { - .name = "cleanup", - .usage = "cleanup SCRAMBLE", - .description = "Rewrite a scramble using only standard moves (HTM)", - .parse_args = parse_only_scramble, - .exec = cleanup_exec, -}; - -Command -unniss_cmd = { - .name = "unniss", - .usage = "unniss SCRAMBLE", - .description = "Rewrite a scramble without NISS", - .parse_args = parse_only_scramble, - .exec = unniss_exec, -}; - -Command -version_cmd = { - .name = "version", - .usage = "version", - .description = "print nissy version", - .parse_args = parse_no_arg, - .exec = version_exec, -}; - -Command *commands[] = { - &commands_cmd, - &freemem_cmd, - &gen_cmd, - &help_cmd, - &invert_cmd, - &print_cmd, - &quit_cmd, - &solve_cmd, - &scramble_cmd, - &steps_cmd, -/* &twophase_cmd,*/ - &cleanup_cmd, - &unniss_cmd, - &version_cmd, - NULL -}; - -#endif - -#endif diff --git a/src/coord.c b/src/coord.c @@ -1,654 +0,0 @@ -#define COORD_C - -#include "coord.h" - -static void gen_coord_comp(Coordinate *coord); -static void gen_coord_sym(Coordinate *coord); -static bool read_coord_mtable(Coordinate *coord); -static bool read_coord_sd(Coordinate *coord); -static bool read_coord_ttable(Coordinate *coord); -static bool write_coord_mtable(Coordinate *coord); -static bool write_coord_sd(Coordinate *coord); -static bool write_coord_ttable(Coordinate *coord); - -/* Indexers ******************************************************************/ - -uint64_t -index_eofb(Cube *cube) -{ - return (uint64_t)digit_array_to_int(cube->eo, 11, 2); -} - -uint64_t -index_coud(Cube *cube) -{ - return (uint64_t)digit_array_to_int(cube->co, 7, 3); -} - -uint64_t -index_cp(Cube *cube) -{ - return (uint64_t)perm_to_index(cube->cp, 8); -} - -uint64_t -index_cpudsep(Cube *cube) -{ - int i, c[8]; - - for (i = 0; i < 8; i++) - c[i] = cube->cp[i] < 4 ? 0 : 1; - - return (uint64_t)subset_to_index(c, 8, 4); -} - -uint64_t -index_epe(Cube *cube) -{ - int i, e[4]; - - for (i = 0; i < 4; i++) - e[i] = cube->ep[i+8] - 8; - - return (uint64_t)perm_to_index(e, 4); -} - -uint64_t -index_epud(Cube *cube) -{ - return (uint64_t)perm_to_index(cube->ep, 8); -} - -uint64_t -index_epos(Cube *cube) -{ - int i, a[12]; - - for (i = 0; i < 12; i++) - a[i] = (cube->ep[i] < 8) ? 0 : 1; - - return (uint64_t)subset_to_index(a, 12, 4); -} - -uint64_t -index_eposepe(Cube *cube) -{ - int i, j, e[4]; - uint64_t epos, epe; - - epos = (uint64_t)index_epos(cube); - for (i = 0, j = 0; i < 12; i++) - if (cube->ep[i] >= 8) - e[j++] = cube->ep[i] - 8; - epe = (uint64_t)perm_to_index(e, 4); - - return epos * FACTORIAL4 + epe; -} - -/* Inverse indexers **********************************************************/ - -void -invindex_eofb(uint64_t ind, Cube *cube) -{ - int_to_sum_zero_array(ind, 2, 12, cube->eo); -} - -void -invindex_coud(uint64_t ind, Cube *cube) -{ - int_to_sum_zero_array(ind, 3, 8, cube->co); -} - -void -invindex_cp(uint64_t ind, Cube *cube) -{ - index_to_perm(ind, 8, cube->cp); -} - -void -invindex_cpudsep(uint64_t ind, Cube *cube) -{ - int i, j, k, c[8]; - - index_to_subset(ind, 8, 4, c); - for (i = 0, j = 0, k = 4; i < 8; i++) - cube->cp[i] = c[i] == 0 ? j++ : k++; -} - - -void -invindex_epe(uint64_t ind, Cube *cube) -{ - int i; - - index_to_perm(ind, 4, &cube->ep[8]); - for (i = 0; i < 4; i++) - cube->ep[i+8] += 8; -} - -void -invindex_epud(uint64_t ind, Cube *cube) -{ - index_to_perm(ind, 8, cube->ep); -} - -void -invindex_epos(uint64_t ind, Cube *cube) -{ - int i, j, k; - - index_to_subset(ind, 12, 4, cube->ep); - for (i = 0, j = 0, k = 8; i < 12; i++) - if (cube->ep[i] == 0) - cube->ep[i] = j++; - else - cube->ep[i] = k++; -} - -void -invindex_eposepe(uint64_t ind, Cube *cube) -{ - int i, j, k, e[4]; - uint64_t epos, epe; - - epos = ind / FACTORIAL4; - epe = ind % FACTORIAL4; - - index_to_subset(epos, 12, 4, cube->ep); - index_to_perm(epe, 4, e); - - for (i = 0, j = 0, k = 0; i < 12; i++) - if (cube->ep[i] == 0) - cube->ep[i] = j++; - else - cube->ep[i] = e[k++] + 8; -} - -/* Other local functions *****************************************************/ - -uint64_t -indexers_getmax(Indexer **is) -{ - int i; - uint64_t max = 1; - - for (i = 0; is[i] != NULL; i++) - max *= is[i]->n; - - return max; -} - -uint64_t -indexers_getind(Indexer **is, Cube *c) -{ - int i; - uint64_t max = 0; - - for (i = 0; is[i] != NULL; i++) { - max *= is[i]->n; - max += is[i]->index(c); - } - - return max; -} - -void -indexers_makecube(Indexer **is, uint64_t ind, Cube *c) -{ - /* Warning: anti-indexers are applied in the same order as indexers. */ - /* We assume order does not matter, but it would make more sense to */ - /* apply them in reverse. */ - - int i; - uint64_t m; - - make_solved(c); - m = indexers_getmax(is); - for (i = 0; is[i] != NULL; i++) { - m /= is[i]->n; - is[i]->to_cube(ind / m, c); - ind %= m; - } -} - -static void -gen_coord_comp(Coordinate *coord) -{ - uint64_t ui; - Cube c, mvd; - Move m; - Trans t; - - coord->max = indexers_getmax(coord->i); - - for (m = 0; m < NMOVES; m++) - coord->mtable[m] = malloc(coord->max * sizeof(uint64_t)); - - for (t = 0; t < NTRANS; t++) - coord->ttable[t] = malloc(coord->max * sizeof(uint64_t)); - - if (!read_coord_mtable(coord)) { - fprintf(stderr, "%s: generating mtable\n", coord->name); - - for (ui = 0; ui < coord->max; ui++) { - indexers_makecube(coord->i, ui, &c); - for (m = 0; m < NMOVES; m++) { - copy_cube(&c, &mvd); - apply_move(m, &mvd); - coord->mtable[m][ui] = - indexers_getind(coord->i, &mvd); - } - } - if (!write_coord_mtable(coord)) - fprintf(stderr, "%s: error writing mtable\n", - coord->name); - - fprintf(stderr, "%s: mtable generated\n", coord->name); - } - - if (!read_coord_ttable(coord)) { - fprintf(stderr, "%s: generating ttable\n", coord->name); - - for (ui = 0; ui < coord->max; ui++) { - indexers_makecube(coord->i, ui, &c); - for (t = 0; t < NTRANS; t++) { - copy_cube(&c, &mvd); - apply_trans(t, &mvd); - coord->ttable[t][ui] = - indexers_getind(coord->i, &mvd); - } - } - if (!write_coord_ttable(coord)) - fprintf(stderr, "%s: error writing ttable\n", - coord->name); - } -} - -static void -gen_coord_sym(Coordinate *coord) -{ - uint64_t i, in, ui, uj, uu, M, nr; - int j; - Move m; - Trans t; - - M = coord->base[0]->max; - coord->selfsim = malloc(M * sizeof(uint64_t)); - coord->symclass = malloc(M * sizeof(uint64_t)); - coord->symrep = malloc(M * sizeof(uint64_t)); - coord->transtorep = malloc(M * sizeof(Trans)); - - if (!read_coord_sd(coord)) { - fprintf(stderr, "%s: generating syms\n", coord->name); - - for (i = 0; i < M; i++) - coord->symclass[i] = M+1; - - for (i = 0, nr = 0; i < M; i++) { - if (coord->symclass[i] != M+1) - continue; - - coord->symrep[nr] = i; - coord->transtorep[i] = uf; - coord->selfsim[nr] = (uint64_t)0; - for (j = 0; j < coord->tgrp->n; j++) { - t = coord->tgrp->t[j]; - in = trans_coord(coord->base[0], t, i); - coord->symclass[in] = nr; - if (in == i) - coord->selfsim[nr] |= ((uint64_t)1<<t); - else - coord->transtorep[in] = - inverse_trans(t); - } - nr++; - } - - coord->max = nr; - - fprintf(stderr, "%s: found %" PRIu64 " classes\n", - coord->name, nr); - if (!write_coord_sd(coord)) - fprintf(stderr, "%s: error writing symdata\n", - coord->name); - } - - coord->symrep = realloc(coord->symrep, coord->max*sizeof(uint64_t)); - coord->selfsim = realloc(coord->selfsim, coord->max*sizeof(uint64_t)); - - for (m = 0; m < NMOVES; m++) { - coord->mtable[m] = malloc(coord->max*sizeof(uint64_t)); - coord->ttrep_move[m] = malloc(coord->max*sizeof(Trans)); - } - - if (!read_coord_mtable(coord)) { - for (ui = 0; ui < coord->max; ui++) { - uu = coord->symrep[ui]; - for (m = 0; m < NMOVES; m++) { - uj = move_coord(coord->base[0], m, uu, NULL); - coord->mtable[m][ui] = coord->symclass[uj]; - coord->ttrep_move[m][ui] = - coord->transtorep[uj]; - } - } - if (!write_coord_mtable(coord)) - fprintf(stderr, "%s: error writing mtable\n", - coord->name); - } -} - -static bool -read_coord_mtable(Coordinate *coord) -{ - FILE *f; - char fname[strlen(tabledir)+256]; - Move m; - uint64_t M; - bool r; - - strcpy(fname, tabledir); - strcat(fname, "/mt_"); - strcat(fname, coord->name); - - if ((f = fopen(fname, "rb")) == NULL) - return false; - - M = coord->max; - r = true; - for (m = 0; m < NMOVES; m++) - r = r && fread(coord->mtable[m], sizeof(uint64_t), M, f) == M; - - if (coord->type == SYM_COORD) - for (m = 0; m < NMOVES; m++) - r = r && fread(coord->ttrep_move[m], - sizeof(Trans), M, f) == M; - - fclose(f); - return r; -} - -static bool -read_coord_sd(Coordinate *coord) -{ - FILE *f; - char fname[strlen(tabledir)+256]; - uint64_t M, N; - bool r; - - strcpy(fname, tabledir); - strcat(fname, "/sd_"); - strcat(fname, coord->name); - - if ((f = fopen(fname, "rb")) == NULL) - return false; - - r = true; - r = r && fread(&coord->max, sizeof(uint64_t), 1, f) == 1; - M = coord->max; - N = coord->base[0]->max; - r = r && fread(coord->symrep, sizeof(uint64_t), M, f) == M; - r = r && fread(coord->selfsim, sizeof(uint64_t), M, f) == M; - r = r && fread(coord->symclass, sizeof(uint64_t), N, f) == N; - r = r && fread(coord->transtorep, sizeof(Trans), N, f) == N; - - fclose(f); - return r; -} - -static bool -read_coord_ttable(Coordinate *coord) -{ - FILE *f; - char fname[strlen(tabledir)+256]; - Trans t; - uint64_t M; - bool r; - - strcpy(fname, tabledir); - strcat(fname, "/tt_"); - strcat(fname, coord->name); - - if ((f = fopen(fname, "rb")) == NULL) - return false; - - M = coord->max; - r = true; - for (t = 0; t < NTRANS; t++) - r = r && fread(coord->ttable[t], sizeof(uint64_t), M, f) == M; - - fclose(f); - return r; -} - -static bool -write_coord_mtable(Coordinate *coord) -{ - FILE *f; - char fname[strlen(tabledir)+256]; - Move m; - uint64_t M; - bool r; - - strcpy(fname, tabledir); - strcat(fname, "/mt_"); - strcat(fname, coord->name); - - if ((f = fopen(fname, "wb")) == NULL) - return false; - - M = coord->max; - r = true; - for (m = 0; m < NMOVES; m++) - r = r && fwrite(coord->mtable[m], sizeof(uint64_t), M, f) == M; - - if (coord->type == SYM_COORD) - for (m = 0; m < NMOVES; m++) - r = r && fwrite(coord->ttrep_move[m], - sizeof(Trans), M, f) == M; - - fclose(f); - return r; -} - -static bool -write_coord_sd(Coordinate *coord) -{ - FILE *f; - char fname[strlen(tabledir)+256]; - uint64_t M, N; - bool r; - - strcpy(fname, tabledir); - strcat(fname, "/sd_"); - strcat(fname, coord->name); - - if ((f = fopen(fname, "wb")) == NULL) - return false; - - r = true; - M = coord->max; - N = coord->base[0]->max; - r = r && fwrite(&coord->max, sizeof(uint64_t), 1, f) == 1; - r = r && fwrite(coord->symrep, sizeof(uint64_t), M, f) == M; - r = r && fwrite(coord->selfsim, sizeof(uint64_t), M, f) == M; - r = r && fwrite(coord->symclass, sizeof(uint64_t), N, f) == N; - r = r && fwrite(coord->transtorep, sizeof(Trans), N, f) == N; - - fclose(f); - return r; -} - -static bool -write_coord_ttable(Coordinate *coord) -{ - FILE *f; - char fname[strlen(tabledir)+256]; - Trans t; - uint64_t M; - bool r; - - strcpy(fname, tabledir); - strcat(fname, "/tt_"); - strcat(fname, coord->name); - - if ((f = fopen(fname, "wb")) == NULL) - return false; - - M = coord->max; - r = true; - for (t = 0; t < NTRANS; t++) - r = r && fwrite(coord->ttable[t], sizeof(uint64_t), M, f) == M; - - fclose(f); - return r; -} - -/* Public functions **********************************************************/ - -void -gen_coord(Coordinate *coord) -{ - int i; - - if (coord == NULL || coord->generated) - return; - - for (i = 0; i < 2; i++) - gen_coord(coord->base[i]); - - switch (coord->type) { - case COMP_COORD: - if (coord->i[0] == NULL) - goto error_gc; - gen_coord_comp(coord); - break; - case SYM_COORD: - if (coord->base[0] == NULL || coord->tgrp == NULL) - goto error_gc; - gen_coord_sym(coord); - break; - case SYMCOMP_COORD: - if (coord->base[0] == NULL || coord->base[1] == NULL) - goto error_gc; - coord->max = coord->base[0]->max * coord->base[1]->max; - break; - default: - break; - } - - coord->generated = true; - return; - -error_gc: - fprintf(stderr, "Error generating coordinates.\n" - "This is a bug, pleae report.\n"); - exit(1); -} - -uint64_t -index_coord(Coordinate *coord, Cube *cube, Trans *offtrans) -{ - uint64_t c[2], cnosym; - Trans ttr; - - switch (coord->type) { - case COMP_COORD: - if (offtrans != NULL) - *offtrans = uf; - - return indexers_getind(coord->i, cube); - case SYM_COORD: - cnosym = index_coord(coord->base[0], cube, NULL); - ttr = coord->transtorep[cnosym]; - - if (offtrans != NULL) - *offtrans = ttr; - - return coord->symclass[cnosym]; - case SYMCOMP_COORD: - c[0] = index_coord(coord->base[0], cube, NULL); - cnosym = index_coord(coord->base[0]->base[0], cube, NULL); - ttr = coord->base[0]->transtorep[cnosym]; - c[1] = index_coord(coord->base[1], cube, NULL); - c[1] = trans_coord(coord->base[1], ttr, c[1]); - - if (offtrans != NULL) - *offtrans = ttr; - - return c[0] * coord->base[1]->max + c[1]; - default: - break; - } - - return coord->max; /* Only reached in case of error */ -} - -uint64_t -move_coord(Coordinate *coord, Move m, uint64_t ind, Trans *offtrans) -{ - uint64_t i[2], M; - Trans ttr; - - /* Some safety checks should be done here, but for performance * - * reasons we'd rather do them before calling this function. * - * We should check if coord is generated. */ - - switch (coord->type) { - case COMP_COORD: - if (offtrans != NULL) - *offtrans = uf; - - return coord->mtable[m][ind]; - case SYM_COORD: - ttr = coord->ttrep_move[m][ind]; - - if (offtrans != NULL) - *offtrans = ttr; - - return coord->mtable[m][ind]; - case SYMCOMP_COORD: - M = coord->base[1]->max; - i[0] = ind / M; - i[1] = ind % M; - ttr = coord->base[0]->ttrep_move[m][i[0]]; - i[0] = coord->base[0]->mtable[m][i[0]]; - i[1] = coord->base[1]->mtable[m][i[1]]; - i[1] = coord->base[1]->ttable[ttr][i[1]]; - - if (offtrans != NULL) - *offtrans = ttr; - - return i[0] * M + i[1]; - default: - break; - } - - return coord->max; /* Only reached in case of error */ -} - -uint64_t -trans_coord(Coordinate *coord, Trans t, uint64_t ind) -{ - uint64_t i[2], M; - - /* Some safety checks should be done here, but for performance * - * reasons we'd rather do them before calling this function. * - * We should check if coord is generated. */ - - switch (coord->type) { - case COMP_COORD: - return coord->ttable[t][ind]; - case SYM_COORD: - return ind; - case SYMCOMP_COORD: - M = coord->base[1]->max; - i[0] = ind / M; /* Always fixed */ - i[1] = ind % M; - i[1] = coord->base[1]->ttable[t][i[1]]; - return i[0] * M + i[1]; - default: - break; - } - - return coord->max; /* Only reached in case of error */ -} diff --git a/src/coord.h b/src/coord.h @@ -1,259 +0,0 @@ -#ifndef COORD_H -#define COORD_H - -#include "trans.h" - -void gen_coord(Coordinate *coord); -uint64_t index_coord(Coordinate *coord, Cube *cube, - Trans *offtrans); -uint64_t indexers_getind(Indexer **is, Cube *c); -void indexers_makecube(Indexer **is, uint64_t ind, Cube *c); -uint64_t move_coord(Coordinate *coord, Move m, - uint64_t ind, Trans *offtrans); -uint64_t trans_coord(Coordinate *coord, Trans t, uint64_t ind); - -/* Base coordinates and their index functions ********************************/ - -#ifndef COORD_C - -extern Coordinate coord_eofb; -extern Coordinate coord_coud; -extern Coordinate coord_cp; -extern Coordinate coord_cpudsep; -extern Coordinate coord_epos; -extern Coordinate coord_epe; -extern Coordinate coord_eposepe; -extern Coordinate coord_epud; -extern Coordinate coord_eofbepos; -extern Coordinate coord_coud_cpudsep; -extern Coordinate coord_eofbepos_sym16; -extern Coordinate coord_cp_sym16; -extern Coordinate coord_corners_sym16; -extern Coordinate coord_drud_sym16; -extern Coordinate coord_drudfin_noE_sym16; -extern Coordinate coord_nxopt31; - -extern Coordinate *all_coordinates[]; - -#else - -/* Indexers ******************************************************************/ - -uint64_t index_eofb(Cube *cube); -void invindex_eofb(uint64_t ind, Cube *ret); -Indexer -i_eofb = { - .n = POW2TO11, - .index = index_eofb, - .to_cube = invindex_eofb, -}; - -uint64_t index_coud(Cube *cube); -void invindex_coud(uint64_t ind, Cube *ret); -Indexer -i_coud = { - .n = POW3TO7, - .index = index_coud, - .to_cube = invindex_coud, -}; - -uint64_t index_cp(Cube *cube); -void invindex_cp(uint64_t ind, Cube *ret); -Indexer -i_cp = { - .n = FACTORIAL8, - .index = index_cp, - .to_cube = invindex_cp, -}; - -uint64_t index_cpudsep(Cube *cube); -void invindex_cpudsep(uint64_t ind, Cube *ret); -Indexer -i_cpudsep = { - .n = BINOM8ON4, - .index = index_cpudsep, - .to_cube = invindex_cpudsep, -}; - -uint64_t index_epos(Cube *cube); -void invindex_epos(uint64_t ind, Cube *ret); -Indexer -i_epos = { - .n = BINOM12ON4, - .index = index_epos, - .to_cube = invindex_epos, -}; - -uint64_t index_epe(Cube *cube); -void invindex_epe(uint64_t ind, Cube *ret); -Indexer -i_epe = { - .n = FACTORIAL4, - .index = index_epe, - .to_cube = invindex_epe, -}; - -uint64_t index_eposepe(Cube *cube); -void invindex_eposepe(uint64_t ind, Cube *ret); -Indexer -i_eposepe = { - .n = BINOM12ON4 * FACTORIAL4, - .index = index_eposepe, - .to_cube = invindex_eposepe, -}; - -uint64_t index_epud(Cube *cube); -void invindex_epud(uint64_t ind, Cube *ret); -Indexer -i_epud = { - .n = FACTORIAL8, - .index = index_epud, - .to_cube = invindex_epud, -}; - -/* Composite coordinates *****************************************************/ - -Coordinate -coord_eofb = { - .name = "eofb", - .type = COMP_COORD, - .i = {&i_eofb, NULL}, -}; - -Coordinate -coord_coud = { - .name = "coud", - .type = COMP_COORD, - .i = {&i_coud, NULL}, -}; - -Coordinate -coord_cp = { - .name = "cp", - .type = COMP_COORD, - .i = {&i_cp, NULL}, -}; - -Coordinate -coord_cpudsep = { - .name = "cpudsep", - .type = COMP_COORD, - .i = {&i_cpudsep, NULL}, -}; - -Coordinate -coord_epos = { - .name = "epos", - .type = COMP_COORD, - .i = {&i_epos, NULL}, -}; - -Coordinate -coord_epe = { - .name = "epe", - .type = COMP_COORD, - .i = {&i_epe, NULL}, -}; - -Coordinate -coord_eposepe = { /* Has to be done by hand, hard compose epos + epe */ - .name = "eposepe", - .type = COMP_COORD, - .i = {&i_eposepe, NULL}, -}; - -Coordinate -coord_epud = { - .name = "epud", - .type = COMP_COORD, - .i = {&i_epud, NULL}, -}; - -Coordinate -coord_eofbepos = { - .name = "eofbepos", - .type = COMP_COORD, - .i = {&i_epos, &i_eofb, NULL}, -}; - -Coordinate -coord_coud_cpudsep = { - .name = "coud_cpudsep", - .type = COMP_COORD, - .i = {&i_coud, &i_cpudsep, NULL}, -}; - -/* Symcoordinates ************************************************************/ - -Coordinate -coord_eofbepos_sym16 = { - .name = "eofbepos_sym16", - .type = SYM_COORD, - .base = {&coord_eofbepos, NULL}, - .tgrp = &tgrp_udfix, -}; - -Coordinate -coord_cp_sym16 = { - .name = "cp_sym16", - .type = SYM_COORD, - .base = {&coord_cp, NULL}, - .tgrp = &tgrp_udfix, -}; - -/* "Symcomp" coordinates *****************************************************/ - -Coordinate -coord_corners_sym16 = { - .name = "corners_sym16", - .type = SYMCOMP_COORD, - .base = {&coord_cp_sym16, &coord_coud}, -}; - -Coordinate -coord_drud_sym16 = { - .name = "drud_sym16", - .type = SYMCOMP_COORD, - .base = {&coord_eofbepos_sym16, &coord_coud}, -}; - -Coordinate -coord_drudfin_noE_sym16 = { - .name = "drudfin_noE_sym16", - .type = SYMCOMP_COORD, - .base = {&coord_cp_sym16, &coord_epud}, -}; - -Coordinate -coord_nxopt31 = { - .name = "nxopt31", - .type = SYMCOMP_COORD, - .base = {&coord_eofbepos_sym16, &coord_coud_cpudsep}, -}; - -/* All coordinates ***********************************************************/ - -Coordinate *all_coordinates[] = { - &coord_eofb, - &coord_coud, - &coord_cp, - &coord_cpudsep, - &coord_epos, - &coord_epe, - &coord_eposepe, - &coord_epud, - &coord_eofbepos, - &coord_coud_cpudsep, - &coord_eofbepos_sym16, - &coord_cp_sym16, - &coord_corners_sym16, - &coord_drud_sym16, - &coord_drudfin_noE_sym16, - &coord_nxopt31, - NULL -}; - -#endif - -#endif - diff --git a/src/cube.c b/src/cube.c @@ -1,270 +0,0 @@ -#define CUBE_C - -#include "cube.h" - -static int where_is_piece(int piece, int *arr, int n); - -void -compose_centers(Cube *c2, Cube *c1) -{ - apply_permutation(c2->xp, c1->xp, 6); -} - -void -compose_corners(Cube *c2, Cube *c1) -{ - apply_permutation(c2->cp, c1->cp, 8); - apply_permutation(c2->cp, c1->co, 8); - sum_arrays_mod(c2->co, c1->co, 8, 3); -} - -void -compose_edges(Cube *c2, Cube *c1) -{ - apply_permutation(c2->ep, c1->ep, 12); - apply_permutation(c2->ep, c1->eo, 12); - sum_arrays_mod(c2->eo, c1->eo, 12, 2); -} - -void -compose(Cube *c2, Cube *c1) -{ - compose_centers(c2, c1); - compose_corners(c2, c1); - compose_edges(c2, c1); -} - -void -copy_cube_centers(Cube *src, Cube *dst) -{ - memcpy(dst->xp, src->xp, 6 * sizeof(int)); -} - -void -copy_cube_corners(Cube *src, Cube *dst) -{ - memcpy(dst->cp, src->cp, 8 * sizeof(int)); - memcpy(dst->co, src->co, 8 * sizeof(int)); -} - -void -copy_cube_edges(Cube *src, Cube *dst) -{ - memcpy(dst->ep, src->ep, 12 * sizeof(int)); - memcpy(dst->eo, src->eo, 12 * sizeof(int)); -} - -void -copy_cube(Cube *src, Cube *dst) -{ - copy_cube_centers(src, dst); - copy_cube_corners(src, dst); - copy_cube_edges(src, dst); -} - -bool -equal(Cube *c1, Cube *c2) -{ - int i; - - for (i = 0; i < 12; i++) - if (c1->ep[i] != c2->ep[i] || c1->eo[i] != c2->eo[i]) - return false; - - for (i = 0; i < 8; i++) - if (c1->cp[i] != c2->cp[i] || c1->co[i] != c2->co[i]) - return false; - - for (i = 0; i < 6; i++) - if (c1->xp[i] != c2->xp[i]) - return false; - - return true; -} - -void -invert_cube_centers(Cube *cube) -{ - int i; - Cube aux; - - copy_cube_centers(cube, &aux); - - for (i = 0; i < 6; i++) - cube->xp[aux.xp[i]] = i; -} - -void -invert_cube_corners(Cube *cube) -{ - int i; - Cube aux; - - copy_cube_corners(cube, &aux); - - for (i = 0; i < 8; i++) { - cube->cp[aux.cp[i]] = i; - cube->co[aux.cp[i]] = (3 - aux.co[i]) % 3; - } -} - -void -invert_cube_edges(Cube *cube) -{ - int i; - Cube aux; - - copy_cube_edges(cube, &aux); - - for (i = 0; i < 12; i++) { - cube->ep[aux.ep[i]] = i; - cube->eo[aux.ep[i]] = aux.eo[i]; - } -} - -void -invert_cube(Cube *cube) -{ - invert_cube_centers(cube); - invert_cube_corners(cube); - invert_cube_edges(cube); -} - -bool -is_admissible(Cube *c) { - bool perm; - int sign, i; - int sum_e, sum_c; - - perm = is_perm(c->ep, 12) && is_perm(c->cp, 8) && is_perm(c->xp, 6); - - sign = perm_sign(c->ep,12) + perm_sign(c->cp,8) + perm_sign(c->xp,6); - - for (i = 0, sum_e = 0; i < 12; i++) - if (c->eo[i] > 1) - return false; - else - sum_e += c->eo[i]; - - for (i = 0, sum_c = 0; i < 8; i++) - if (c->co[i] > 2) - return false; - else - sum_c += c->co[i]; - - return (perm && sign % 2 == 0 && sum_e % 2 == 0 && sum_c % 2 == 0); -} - -bool -is_solved(Cube *cube) -{ - Cube solved_cube; - make_solved(&solved_cube); - - return equal(cube, &solved_cube); -} - -void -make_solved_centers(Cube *cube) -{ - static int sorted[6] = {0, 1, 2, 3, 4, 5}; - - memcpy(cube->xp, sorted, 6 * sizeof(int)); -} - -void -make_solved_corners(Cube *cube) -{ - static int sorted[8] = {0, 1, 2, 3, 4, 5, 6, 7}; - - memcpy(cube->cp, sorted, 8 * sizeof(int)); - memset(cube->co, 0, 8 * sizeof(int)); -} - -void -make_solved_edges(Cube *cube) -{ - static int sorted[12] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}; - - memcpy(cube->ep, sorted, 12 * sizeof(int)); - memset(cube->eo, 0, 12 * sizeof(int)); -} - -void -make_solved(Cube *cube) -{ - make_solved_centers(cube); - make_solved_corners(cube); - make_solved_edges(cube); -} - -void -print_cube(Cube *cube) -{ - static char edge_string[12][7] = { - [UF] = "UF", [UL] = "UL", [UB] = "UB", [UR] = "UR", - [DF] = "DF", [DL] = "DL", [DB] = "DB", [DR] = "DR", - [FR] = "FR", [FL] = "FL", [BL] = "BL", [BR] = "BR" - }; - - static char corner_string[8][7] = { - [UFR] = "UFR", [UFL] = "UFL", [UBL] = "UBL", [UBR] = "UBR", - [DFR] = "DFR", [DFL] = "DFL", [DBL] = "DBL", [DBR] = "DBR" - }; - - static char center_string[6][7] = { - [U_center] = "U", [D_center] = "D", - [R_center] = "R", [L_center] = "L", - [F_center] = "F", [B_center] = "B" - }; - - for (int i = 0; i < 12; i++) - printf(" %s ", edge_string[cube->ep[i]]); - printf("\n"); - - for (int i = 0; i < 12; i++) - printf(" %" PRIu8 " ", cube->eo[i]); - printf("\n"); - - for (int i = 0; i < 8; i++) - printf("%s ", corner_string[cube->cp[i]]); - printf("\n"); - - for (int i = 0; i < 8; i++) - printf(" %" PRIu8 " ", cube->co[i]); - printf("\n"); - - for (int i = 0; i < 6; i++) - printf(" %s ", center_string[cube->xp[i]]); - printf("\n"); -} - -int -where_is_center(Center x, Cube *c) -{ - return where_is_piece(x, c->xp, 6); -} - -int -where_is_corner(Corner k, Cube *c) -{ - return where_is_piece(k, c->cp, 8); -} - -int -where_is_edge(Edge e, Cube *c) -{ - return where_is_piece(e, c->ep, 12); -} - -static int -where_is_piece(int piece, int *arr, int n) -{ - int i; - - for (i = 0; i < n; i++) - if (arr[i] == piece) - return i; - - return -1; -} diff --git a/src/cube.h b/src/cube.h @@ -1,35 +0,0 @@ -#ifndef CUBE_H -#define CUBE_H - -#include <stdio.h> - -#include "cubetypes.h" -#include "env.h" -#include "utils.h" - -void compose(Cube *c2, Cube *c1); /* Use c2 as an alg on c1 */ -void compose_centers(Cube *c2, Cube *c1); -void compose_corners(Cube *c2, Cube *c1); -void compose_edges(Cube *c2, Cube *c1); -void copy_cube(Cube *src, Cube *dst); -void copy_cube_centers(Cube *src, Cube *dst); -void copy_cube_corners(Cube *src, Cube *dst); -void copy_cube_edges(Cube *src, Cube *dst); -bool equal(Cube *c1, Cube *c2); -void invert_cube(Cube *cube); -void invert_cube_centers(Cube *cube); -void invert_cube_corners(Cube *cube); -void invert_cube_edges(Cube *cube); -bool is_admissible(Cube *cube); -bool is_solved(Cube *cube); -void make_solved(Cube *cube); -void make_solved_centers(Cube *cube); -void make_solved_corners(Cube *cube); -void make_solved_edges(Cube *cube); -void print_cube(Cube *cube); -int where_is_center(Center x, Cube *c); -int where_is_corner(Corner k, Cube *c); -int where_is_edge(Edge e, Cube *c); - -#endif - diff --git a/src/cubetypes.h b/src/cubetypes.h @@ -1,360 +0,0 @@ -#ifndef CUBETYPES_H -#define CUBETYPES_H - -#include <stdbool.h> -#include <inttypes.h> -#include <pthread.h> - -#define NMOVES 55 /* Actually 54, but one is NULLMOVE */ -#define NTRANS 48 -#define NROTATIONS 24 -#define entry_group_t uint8_t /* For pruning tables */ - -#define MAX_N_COORD 6 - -/* Enums *********************************************************************/ - -typedef enum -center -{ - U_center, D_center, - R_center, L_center, - F_center, B_center -} Center; - -typedef enum -corner -{ - UFR, UFL, UBL, UBR, - DFR, DFL, DBL, DBR -} Corner; - -typedef enum -coordtype -{ - COMP_COORD, SYM_COORD, SYMCOMP_COORD -} CoordType; - -typedef enum -edge -{ - UF, UL, UB, UR, - DF, DL, DB, DR, - FR, FL, BL, BR -} Edge; - -typedef enum -move -{ - NULLMOVE, - U, U2, U3, D, D2, D3, - R, R2, R3, L, L2, L3, - F, F2, F3, B, B2, B3, - Uw, Uw2, Uw3, Dw, Dw2, Dw3, - Rw, Rw2, Rw3, Lw, Lw2, Lw3, - Fw, Fw2, Fw3, Bw, Bw2, Bw3, - M, M2, M3, - S, S2, S3, - E, E2, E3, - x, x2, x3, - y, y2, y3, - z, z2, z3, -} Move; - -typedef enum -trans -{ - uf, ur, ub, ul, - df, dr, db, dl, - rf, rd, rb, ru, - lf, ld, lb, lu, - fu, fr, fd, fl, - bu, br, bd, bl, - uf_mirror, ur_mirror, ub_mirror, ul_mirror, - df_mirror, dr_mirror, db_mirror, dl_mirror, - rf_mirror, rd_mirror, rb_mirror, ru_mirror, - lf_mirror, ld_mirror, lb_mirror, lu_mirror, - fu_mirror, fr_mirror, fd_mirror, fl_mirror, - bu_mirror, br_mirror, bd_mirror, bl_mirror, -} Trans; - - -/* Typedefs ******************************************************************/ - -typedef struct alg Alg; -typedef struct alglist AlgList; -typedef struct alglistnode AlgListNode; -typedef struct choicestep ChoiceStep; -typedef struct command Command; -typedef struct commandargs CommandArgs; -typedef struct coordinate Coordinate; -typedef struct cube Cube; -/*typedef struct dfsarg DfsArg;*/ -typedef struct fstcube FstCube; -typedef struct indexer Indexer; -typedef struct movable Movable; -typedef struct moveset Moveset; -typedef struct prunedata PruneData; -typedef struct solveoptions SolveOptions; -typedef struct step Step; -typedef struct symdata SymData; -typedef struct threaddatasolve ThreadDataSolve; -typedef struct threaddatagenpt ThreadDataGenpt; -typedef struct transgroup TransGroup; - -typedef bool (*Checker) (Cube *); -typedef bool (*CubeTester) (Cube *, Alg *); -/*typedef bool (*DfsMover) (DfsArg *);*/ -typedef void (*DfsExtraCopier) (void *, void *); -typedef Alg * (*Validator) (Alg *); -typedef void (*Exec) (CommandArgs *); -typedef CommandArgs * (*ArgParser) (int, char **); -typedef bool (*Tester) (void); -typedef int (*TransFinder) (uint64_t, Trans *); - - -/* Structs *******************************************************************/ - -struct -alg -{ - Move * move; - bool * inv; - int len; - int allocated; - Move * move_normal; - int len_normal; - Move * move_inverse; - int len_inverse; -}; - -struct -alglist -{ - AlgListNode * first; - AlgListNode * last; - int len; -}; - -struct -alglistnode -{ - Alg * alg; - AlgListNode * next; -}; - -struct -choicestep -{ - char * shortname; - char * name; - Step * step[99]; - Trans t[99]; - char * ready_msg; -}; - -struct -command -{ - char * name; - char * usage; - char * description; - ArgParser parse_args; - Exec exec; -}; - -struct -commandargs -{ - bool success; - Alg * scramble; - SolveOptions * opts; - ChoiceStep * cs; - Command * command; /* For help */ - int n; - char scrtype[20]; - bool scrstdin; - bool header; -}; - -struct -coordinate -{ - char * name; - CoordType type; - bool generated; - Indexer * i[99]; - uint64_t max; - uint64_t * mtable[NMOVES]; - uint64_t * ttable[NTRANS]; - TransGroup * tgrp; - Coordinate * base[2]; - uint64_t * symclass; - uint64_t * symrep; - Trans * transtorep; - Trans * ttrep_move[NMOVES]; - uint64_t * selfsim; -}; - -struct -cube -{ - int ep[12]; - int eo[12]; - int cp[8]; - int co[8]; - int xp[6]; -}; - -/* -struct -movable -{ - uint64_t val; - Trans t; -}; -*/ - -/* -struct -dfsarg -{ - Cube * cube; - Movable ind[MAX_N_COORD]; - Trans t; - Step * s; - SolveOptions * opts; - int d; - int bound; - bool niss; - AlgList * sols; - pthread_mutex_t * sols_mutex; - Alg * current_alg; - void * extra; -}; -*/ - -/* -struct -dfsarg -{ - void * cube_data; - SolveOptions * opts; - int d; - int bound; - bool niss; - AlgList * sols; - Alg * current_alg; - Solver * solver; - Threader * threader; -}; -*/ - -struct -fstcube -{ - uint16_t uf_eofb; - uint16_t uf_eposepe; - uint16_t uf_coud; - uint16_t uf_cp; - uint16_t fr_eofb; - uint16_t fr_eposepe; - uint16_t fr_coud; - uint16_t rd_eofb; - uint16_t rd_eposepe; - uint16_t rd_coud; -}; - -struct -indexer -{ - int n; - uint64_t (*index)(Cube *); - void (*to_cube)(uint64_t, Cube *); -}; - -struct -moveset -{ - char * name; - bool (*allowed)(Move); - bool (*can_append)(Alg *, Move, bool); - bool (*cancel_niss)(Alg *); - Move sorted_moves[NMOVES+1]; -}; - -struct -prunedata -{ - entry_group_t * ptable; - uint64_t n; - Coordinate * coord; - Moveset * moveset; - uint64_t count[16]; - bool compact; - int base; -}; - -struct -solveoptions -{ - int min_moves; - int max_moves; - int max_solutions; - int nthreads; - int optimal; - bool can_niss; - bool verbose; - bool all; - bool print_number; - bool count_only; -}; - -struct -step -{ - Checker ready; - bool final; - Moveset * moveset; - int n_coord; - Coordinate * coord[MAX_N_COORD]; - Trans coord_trans[MAX_N_COORD]; - PruneData * pd[MAX_N_COORD]; - bool pd_compact[MAX_N_COORD]; - Validator is_valid; - /*DfsMover custom_move_checkstop;*/ - DfsExtraCopier copy_extra; -}; - -/* -struct -threaddatasolve -{ - DfsArg arg; - int thid; - AlgList * start; - AlgListNode ** node; - pthread_mutex_t * start_mutex; -}; -*/ - -struct -threaddatagenpt -{ - int thid; - int nthreads; - PruneData * pd; - int d; - int nchunks; - pthread_mutex_t ** mutex; - pthread_mutex_t * upmutex; -}; - -struct -transgroup -{ - int n; - Trans t[NTRANS]; -}; - -#endif diff --git a/src/env.c b/src/env.c @@ -1,60 +0,0 @@ -#define ENV_C - -#include "env.h" - -bool initialized_env = false; -char *tabledir; - -void -mymkdir(char *d, int m) -{ -#ifdef _WIN32 - mkdir(d); -#else - mkdir(d, m); -#endif -} - -void -init_env() -{ - char *nissydata = getenv("NISSYDATA"); - char *localdata = getenv("XDG_DATA_HOME"); - char *home = getenv("HOME"); - bool read, write; - - if (initialized_env) - return; - - if (nissydata != NULL) { - tabledir = malloc((strlen(nissydata) + 20) * sizeof(char)); - strcpy(tabledir, nissydata); - } else if (localdata != NULL) { - tabledir = malloc((strlen(localdata) + 20) * sizeof(char)); - strcpy(tabledir, localdata); - strcat(tabledir, "/nissy"); - } else if (home != NULL) { - tabledir = malloc((strlen(home) + 20) * sizeof(char)); - strcpy(tabledir, home); - strcat(tabledir, "/.nissy"); - } else { - tabledir = malloc(20 * sizeof(char)); - strcpy(tabledir, "."); - } - - mymkdir(tabledir, 0777); - strcat(tabledir, "/tables"); - mymkdir(tabledir, 0777); - - read = !access(tabledir, R_OK); - write = !access(tabledir, W_OK); - - if (!read) { - fprintf(stderr, "Table files cannot be read.\n"); - } else if (!write) { - fprintf(stderr, "Data directory not writable: "); - fprintf(stderr, "tables can be loaded, but not saved.\n"); - } - - initialized_env = true; -} diff --git a/src/env.h b/src/env.h @@ -1,15 +0,0 @@ -#ifndef ENV_H -#define ENV_H - -#include <stdbool.h> -#include <stdio.h> -#include <stdlib.h> -#include <string.h> -#include <unistd.h> -#include <sys/stat.h> - -void init_env(); - -extern char *tabledir; - -#endif diff --git a/src/fst.c b/src/fst.c @@ -1,401 +0,0 @@ -#define FST_C - -#include "fst.h" - -static FstCube ep_to_fst_epos(int *ep); -static void init_fst_corner_invtables(); -static void init_fst_eo_invtables(); -static void init_fst_eo_update(uint64_t, uint64_t, int, Cube *); -static void init_fst_where_is_edge(); -static bool read_fst_tables_file(); -static bool write_fst_tables_file(); - -static int edge_slice[12] = {[FR] = 0, [FL] = 0, [BL] = 0, [BR] = 0, - [UL] = 1, [UR] = 1, [DR] = 1, [DL] = 1, - [UF] = 2, [UB] = 2, [DF] = 2, [DB] = 2}; - -static uint16_t inv_coud[FACTORIAL8][POW3TO7]; -static uint16_t inv_cp[FACTORIAL8]; -static uint16_t uf_cp_to_fr_cp[FACTORIAL8]; -static uint16_t uf_cp_to_rd_cp[FACTORIAL8]; -static uint16_t eo_invtable[3][POW2TO11][BINOM12ON4*FACTORIAL4]; -static uint16_t fst_where_is_edge_arr[3][12][BINOM12ON4*FACTORIAL4]; - -FstCube -cube_to_fst(Cube *cube) -{ - Cube c; - FstCube ret; - - copy_cube(cube, &c); - ret.uf_eofb = coord_eofb.i[0]->index(&c); - ret.uf_eposepe = coord_eposepe.i[0]->index(&c); - ret.uf_coud = coord_coud.i[0]->index(&c); - ret.uf_cp = coord_cp.i[0]->index(&c); - copy_cube(cube, &c); - apply_trans(fr, &c); - ret.fr_eofb = coord_eofb.i[0]->index(&c); - ret.fr_eposepe = coord_eposepe.i[0]->index(&c); - ret.fr_coud = coord_coud.i[0]->index(&c); - copy_cube(cube, &c); - apply_trans(rd, &c); - ret.rd_eofb = coord_eofb.i[0]->index(&c); - ret.rd_eposepe = coord_eposepe.i[0]->index(&c); - ret.rd_coud = coord_coud.i[0]->index(&c); - - return ret; -} - -static FstCube -ep_to_fst_epos(int *ep) -{ - static int eind[12] = { - [FR] = 0, [FL] = 1, [BL] = 2, [BR] = 3, - [UR] = 0, [DR] = 1, [DL] = 2, [UL] = 3, - [DB] = 0, [DF] = 1, [UF] = 2, [UB] = 3 - }; - static int eptrans_fr[12] = { - [FR] = UF, [DF] = UL, [FL] = UB, [UF] = UR, - [BR] = DF, [DB] = DL, [BL] = DB, [UB] = DR, - [UR] = FR, [DR] = FL, [DL] = BL, [UL] = BR - }; - static int eptrans_rd[12] = { - [DR] = UF, [FR] = UL, [UR] = UB, [BR] = UR, - [DL] = DF, [FL] = DL, [UL] = DB, [BL] = DR, - [DB] = FR, [DF] = FL, [UF] = BL, [UB] = BR - }; - - FstCube ret; - int i, ce, cs, cm; - int epe[4], eps[4], epm[4], epose[12], eposs[12], eposm[12]; - - memset(epose, 0, 12*sizeof(int)); - memset(eposs, 0, 12*sizeof(int)); - memset(eposm, 0, 12*sizeof(int)); - - for (i = 0, ce = 0; i < 12; i++) { - switch (edge_slice[ep[i]]) { - case 0: - epose[i] = 1; - epe[ce++] = eind[ep[i]]; - break; - case 1: - eposs[eptrans_fr[i]] = eind[ep[i]] + 1; - break; - default: - eposm[eptrans_rd[i]] = eind[ep[i]] + 1; - break; - } - } - - for (i = 0, cs = 0, cm = 0; i < 12; i++) { - if (eposs[i]) { - eps[cs++] = eposs[i] - 1; - eposs[i] = 1; - } - if (eposm[i]) { - epm[cm++] = eposm[i] - 1; - eposm[i] = 1; - } - } - - ret.uf_eposepe = subset_to_index(epose, 12, 4) * FACTORIAL4 + - perm_to_index(epe, 4); - ret.fr_eposepe = subset_to_index(eposs, 12, 4) * FACTORIAL4 + - perm_to_index(eps, 4); - ret.rd_eposepe = subset_to_index(eposm, 12, 4) * FACTORIAL4 + - perm_to_index(epm, 4); - - return ret; -} - -FstCube -fst_inverse(FstCube fst) -{ - FstCube ret; - int ep_inv[12]; - - ep_inv[FR] = fst_where_is_edge_arr[0][FR][fst.uf_eposepe]; - ep_inv[FL] = fst_where_is_edge_arr[0][FL][fst.uf_eposepe]; - ep_inv[BL] = fst_where_is_edge_arr[0][BL][fst.uf_eposepe]; - ep_inv[BR] = fst_where_is_edge_arr[0][BR][fst.uf_eposepe]; - - ep_inv[UR] = fst_where_is_edge_arr[1][UR][fst.fr_eposepe]; - ep_inv[UL] = fst_where_is_edge_arr[1][UL][fst.fr_eposepe]; - ep_inv[DR] = fst_where_is_edge_arr[1][DR][fst.fr_eposepe]; - ep_inv[DL] = fst_where_is_edge_arr[1][DL][fst.fr_eposepe]; - - ep_inv[UF] = fst_where_is_edge_arr[2][UF][fst.rd_eposepe]; - ep_inv[UB] = fst_where_is_edge_arr[2][UB][fst.rd_eposepe]; - ep_inv[DF] = fst_where_is_edge_arr[2][DF][fst.rd_eposepe]; - ep_inv[DB] = fst_where_is_edge_arr[2][DB][fst.rd_eposepe]; - - ret = ep_to_fst_epos(ep_inv); - - ret.uf_eofb = ((uint16_t)eo_invtable[0][fst.uf_eofb][fst.uf_eposepe]) | - ((uint16_t)eo_invtable[1][fst.uf_eofb][fst.fr_eposepe]) | - ((uint16_t)eo_invtable[2][fst.uf_eofb][fst.rd_eposepe]); - ret.fr_eofb = ((uint16_t)eo_invtable[0][fst.fr_eofb][fst.uf_eposepe]) | - ((uint16_t)eo_invtable[1][fst.fr_eofb][fst.fr_eposepe]) | - ((uint16_t)eo_invtable[2][fst.fr_eofb][fst.rd_eposepe]); - ret.rd_eofb = ((uint16_t)eo_invtable[0][fst.rd_eofb][fst.uf_eposepe]) | - ((uint16_t)eo_invtable[1][fst.rd_eofb][fst.fr_eposepe]) | - ((uint16_t)eo_invtable[2][fst.rd_eofb][fst.rd_eposepe]); - - ret.uf_cp = inv_cp[fst.uf_cp]; - - ret.uf_coud = inv_coud[fst.uf_cp][fst.uf_coud]; - ret.fr_coud = inv_coud[uf_cp_to_fr_cp[fst.uf_cp]][fst.fr_coud]; - ret.rd_coud = inv_coud[uf_cp_to_rd_cp[fst.uf_cp]][fst.rd_coud]; - - return ret; -} - -FstCube -fst_move(Move m, FstCube fst) -{ - FstCube ret; - Move m_fr, m_rd; - - m_fr = transform_move(fr, m); - m_rd = transform_move(rd, m); - - ret.uf_eofb = coord_eofb.mtable[m][fst.uf_eofb]; - ret.uf_eposepe = coord_eposepe.mtable[m][fst.uf_eposepe]; - ret.uf_coud = coord_coud.mtable[m][fst.uf_coud]; - ret.uf_cp = coord_cp.mtable[m][fst.uf_cp]; - - ret.fr_eofb = coord_eofb.mtable[m_fr][fst.fr_eofb]; - ret.fr_eposepe = coord_eposepe.mtable[m_fr][fst.fr_eposepe]; - ret.fr_coud = coord_coud.mtable[m_fr][fst.fr_coud]; - - ret.rd_eofb = coord_eofb.mtable[m_rd][fst.rd_eofb]; - ret.rd_eposepe = coord_eposepe.mtable[m_rd][fst.rd_eposepe]; - ret.rd_coud = coord_coud.mtable[m_rd][fst.rd_coud]; - - return ret; -} - -void -fst_to_cube(FstCube fst, Cube *cube) -{ - Cube e, s, m; - int i; - - coord_eposepe.i[0]->to_cube(fst.uf_eposepe, &e); - coord_eposepe.i[0]->to_cube(fst.fr_eposepe, &s); - apply_trans(inverse_trans(fr), &s); - coord_eposepe.i[0]->to_cube(fst.rd_eposepe, &m); - apply_trans(inverse_trans(rd), &m); - - for (i = 0; i < 12; i++) { - if (edge_slice[e.ep[i]] == 0) - cube->ep[i] = e.ep[i]; - if (edge_slice[s.ep[i]] == 1) - cube->ep[i] = s.ep[i]; - if (edge_slice[m.ep[i]] == 2) - cube->ep[i] = m.ep[i]; - } - - coord_eofb.i[0]->to_cube((uint64_t)fst.uf_eofb, cube); - coord_coud.i[0]->to_cube((uint64_t)fst.uf_coud, cube); - coord_cp.i[0]->to_cube((uint64_t)fst.uf_cp, cube); - - for (i = 0; i < 6; i++) - cube->xp[i] = i; -} - -void -init_fst() -{ - init_trans(); - gen_coord(&coord_eofb); - gen_coord(&coord_eposepe); - gen_coord(&coord_coud); - gen_coord(&coord_cp); - - if (!read_fst_tables_file()) { - fprintf(stderr, - "Could not load fst_tables, generating them\n"); - init_fst_corner_invtables(); - init_fst_eo_invtables(); - init_fst_where_is_edge(); - if (!write_fst_tables_file()) - fprintf(stderr, "fst_tables could not be written\b"); - } -} - -static void -init_fst_corner_invtables() -{ - Cube c, d; - uint64_t cp, coud; - - for (cp = 0; cp < FACTORIAL8; cp++) { - make_solved_corners(&c); - coord_cp.i[0]->to_cube(cp, &c); - - copy_cube_corners(&c, &d); - invert_cube_corners(&d); - inv_cp[cp] = coord_cp.i[0]->index(&d); - - for (coud = 0; coud < POW3TO7; coud++) { - copy_cube_corners(&c, &d); - coord_coud.i[0]->to_cube(coud, &d); - invert_cube_corners(&d); - inv_coud[cp][coud] = coord_coud.i[0]->index(&d); - } - - copy_cube_corners(&c, &d); - apply_trans(fr, &d); - uf_cp_to_fr_cp[cp] = coord_cp.i[0]->index(&d); - - copy_cube_corners(&c, &d); - apply_trans(rd, &d); - uf_cp_to_rd_cp[cp] = coord_cp.i[0]->index(&d); - } -} - -static void -init_fst_eo_invtables() -{ - uint64_t ep, eo; - Cube c, d; - - for (ep = 0; ep < BINOM12ON4 * FACTORIAL4; ep++) { - make_solved(&c); - coord_eposepe.i[0]->to_cube(ep, &c); - for (eo = 0; eo < POW2TO11; eo++) { - copy_cube_edges(&c, &d); - coord_eofb.i[0]->to_cube(eo, &d); - init_fst_eo_update(eo, ep, 0, &d); - - apply_trans(inverse_trans(fr), &d); - coord_eofb.i[0]->to_cube(eo, &d); - init_fst_eo_update(eo, ep, 1, &d); - - copy_cube_edges(&c, &d); - apply_trans(inverse_trans(rd), &d); - coord_eofb.i[0]->to_cube(eo, &d); - init_fst_eo_update(eo, ep, 2, &d); - } - } -} - -static void -init_fst_eo_update(uint64_t eo, uint64_t ep, int s, Cube *d) -{ - int i; - - for (i = 0; i < 12; i++) { - if (edge_slice[d->ep[i]] == s && d->eo[i] && d->ep[i] != 11) - eo_invtable[s][eo][ep] |= - ((uint16_t)1) << ((uint16_t)d->ep[i]); - } -} - -static void -init_fst_where_is_edge() -{ - Cube c, d; - uint64_t e; - - make_solved(&c); - for (e = 0; e < BINOM12ON4 * FACTORIAL4; e++) { - coord_eposepe.i[0]->to_cube(e, &c); - - copy_cube_edges(&c, &d); - fst_where_is_edge_arr[0][FR][e] = where_is_edge(FR, &d); - fst_where_is_edge_arr[0][FL][e] = where_is_edge(FL, &d); - fst_where_is_edge_arr[0][BL][e] = where_is_edge(BL, &d); - fst_where_is_edge_arr[0][BR][e] = where_is_edge(BR, &d); - - copy_cube_edges(&c, &d); - apply_trans(inverse_trans(fr), &d); - fst_where_is_edge_arr[1][UL][e] = where_is_edge(UL, &d); - fst_where_is_edge_arr[1][UR][e] = where_is_edge(UR, &d); - fst_where_is_edge_arr[1][DL][e] = where_is_edge(DL, &d); - fst_where_is_edge_arr[1][DR][e] = where_is_edge(DR, &d); - - copy_cube_edges(&c, &d); - apply_trans(inverse_trans(rd), &d); - fst_where_is_edge_arr[2][UF][e] = where_is_edge(UF, &d); - fst_where_is_edge_arr[2][UB][e] = where_is_edge(UB, &d); - fst_where_is_edge_arr[2][DF][e] = where_is_edge(DF, &d); - fst_where_is_edge_arr[2][DB][e] = where_is_edge(DB, &d); - } -} - -static bool -read_fst_tables_file() -{ - init_env(); - - FILE *f; - char fname[strlen(tabledir)+256]; - uint64_t i, j, r, total; - - strcpy(fname, tabledir); - strcat(fname, "/fst_tables"); - - if ((f = fopen(fname, "rb")) == NULL) - return false; - - r = 0; - total = FACTORIAL8*(POW3TO7+3) + 3*BINOM12ON4*FACTORIAL4*(12+POW2TO11); - - for (i = 0; i < FACTORIAL8; i++) - r += fread(inv_coud[i], sizeof(uint16_t), POW3TO7, f); - r += fread(inv_cp, sizeof(uint16_t), FACTORIAL8, f); - r += fread(uf_cp_to_fr_cp, sizeof(uint16_t), FACTORIAL8, f); - r += fread(uf_cp_to_rd_cp, sizeof(uint16_t), FACTORIAL8, f); - for (i = 0; i < 3; i++) - for (j = 0; j < POW2TO11; j++) - r += fread(eo_invtable[i][j], - sizeof(uint16_t), BINOM12ON4*FACTORIAL4, f); - for (i = 0; i < 3; i++) - for (j = 0; j < 12; j++) - r += fread(fst_where_is_edge_arr[i][j], - sizeof(uint16_t), BINOM12ON4*FACTORIAL4, f); - - fclose(f); - - return r == total; -} - -static bool -write_fst_tables_file() -{ - init_env(); - - FILE *f; - char fname[strlen(tabledir)+256]; - uint64_t i, j, w, total; - - strcpy(fname, tabledir); - strcat(fname, "/fst_tables"); - - if ((f = fopen(fname, "wb")) == NULL) - return false; - - w = 0; - total = FACTORIAL8*(POW3TO7+3) + 3*BINOM12ON4*FACTORIAL4*(12+POW2TO11); - - for (i = 0; i < FACTORIAL8; i++) - w += fwrite(inv_coud[i], sizeof(uint16_t), POW3TO7, f); - w += fwrite(inv_cp, sizeof(uint16_t), FACTORIAL8, f); - w += fwrite(uf_cp_to_fr_cp, sizeof(uint16_t), FACTORIAL8, f); - w += fwrite(uf_cp_to_rd_cp, sizeof(uint16_t), FACTORIAL8, f); - for (i = 0; i < 3; i++) - for (j = 0; j < POW2TO11; j++) - w += fwrite(eo_invtable[i][j], - sizeof(uint16_t), BINOM12ON4*FACTORIAL4, f); - for (i = 0; i < 3; i++) - for (j = 0; j < 12; j++) - w += fwrite(fst_where_is_edge_arr[i][j], - sizeof(uint16_t), BINOM12ON4*FACTORIAL4, f); - - fclose(f); - - return w == total; -} diff --git a/src/fst.h b/src/fst.h @@ -1,13 +0,0 @@ -#ifndef FST_H -#define FST_H - -#include "coord.h" - -FstCube cube_to_fst(Cube *cube); -FstCube fst_inverse(FstCube fst); -FstCube fst_move(Move m, FstCube fst); -void fst_to_cube(FstCube fst, Cube *cube); -void init_fst(); - -#endif - diff --git a/src/moves.c b/src/moves.c @@ -1,301 +0,0 @@ -#define MOVES_C - -#include "moves.h" - -/* Local functions ***********************************************************/ - -static void cleanup_aux(Alg *alg, Alg *ret, bool inv); - -/* Tables and other data *****************************************************/ - -/* Moves are represented as cubes and applied using compose(). Every move is * - * translated to a an <U, x, y> alg before filling the transition tables. * - * See init_moves(). */ - -static Cube move_array[NMOVES]; - -static char equiv_alg_string[100][NMOVES] = { - [NULLMOVE] = "", - - [U] = " U ", - [U2] = " UU ", - [U3] = " UUU ", - [D] = " xx U xx ", - [D2] = " xx UU xx ", - [D3] = " xx UUU xx ", - [R] = " yx U xxxyyy ", - [R2] = " yx UU xxxyyy ", - [R3] = " yx UUU xxxyyy ", - [L] = " yyyx U xxxy ", - [L2] = " yyyx UU xxxy ", - [L3] = " yyyx UUU xxxy ", - [F] = " x U xxx ", - [F2] = " x UU xxx ", - [F3] = " x UUU xxx ", - [B] = " xxx U x ", - [B2] = " xxx UU x ", - [B3] = " xxx UUU x ", - - [Uw] = " xx U xx y ", - [Uw2] = " xx UU xx yy ", - [Uw3] = " xx UUU xx yyy ", - [Dw] = " U yyy ", - [Dw2] = " UU yy ", - [Dw3] = " UUU y ", - [Rw] = " yyyx U xxxy x ", - [Rw2] = " yyyx UU xxxy xx ", - [Rw3] = " yyyx UUU xxxy xxx ", - [Lw] = " yx U xxxyyy xxx ", - [Lw2] = " yx UU xxxyyy xx ", - [Lw3] = " yx UUU xxxyyy x ", - [Fw] = " xxx U x yxxxyyy ", - [Fw2] = " xxx UU x yxxyyy ", - [Fw3] = " xxx UUU x yxyyy ", - [Bw] = " x U xxx yxyyy ", - [Bw2] = " x UU xxx yxxyyy ", - [Bw3] = " x UUU xxx yxxxyyy ", - - [M] = " yx U xx UUU yxyyy ", - [M2] = " yx UU xx UU xxxy ", - [M3] = " yx UUU xx U yxxxy ", - [S] = " x UUU xx U yyyx ", - [S2] = " x UU xx UU yyx ", - [S3] = " x U xx UUU yx ", - [E] = " U xx UUU xxyyy ", - [E2] = " UU xx UU xxyy ", - [E3] = " UUU xx U xxy ", - - [x] = " x ", - [x2] = " xx ", - [x3] = " xxx ", - [y] = " y ", - [y2] = " yy ", - [y3] = " yyy ", - [z] = " yyy x y ", - [z2] = " yy xx ", - [z3] = " y x yyy " -}; - - -/* Public functions **********************************************************/ - -void -apply_alg(Alg *alg, Cube *cube) -{ - Cube aux; - int i; - - copy_cube(cube, &aux); - make_solved(cube); - - for (i = 0; i < alg->len; i++) - if (alg->inv[i]) - apply_move(alg->move[i], cube); - - invert_cube(cube); - compose(&aux, cube); - - for (i = 0; i < alg->len; i++) - if (!alg->inv[i]) - apply_move(alg->move[i], cube); -} - -void -apply_move(Move m, Cube *cube) -{ - compose(&move_array[m], cube); -} - -void -apply_move_centers(Move m, Cube *cube) -{ - compose_centers(&move_array[m], cube); -} - -void -apply_move_corners(Move m, Cube *cube) -{ - compose_corners(&move_array[m], cube); -} - -void -apply_move_edges(Move m, Cube *cube) -{ - compose_edges(&move_array[m], cube); -} - -Alg * -cleanup(Alg *alg) -{ - int i, j, k, b[2], n, L; - Move bb, m; - Alg *ret; - - ret = new_alg(""); - cleanup_aux(alg, ret, false); - cleanup_aux(alg, ret, true); - - do { - for (i = 0, j = 0, n = 0; i < ret->len; i = j) { - if (ret->move[i] > B3) { - ret->move[n] = ret->move[i]; - ret->inv[n] = ret->inv[i]; - n++; - j++; - continue; - } - - bb = 1 + ((base_move(ret->move[i]) - 1)/6)*6; - while (j < ret->len && - ret->move[j] <= B3 && - ret->inv[j] == ret->inv[i] && - 1 + ((base_move(ret->move[j]) - 1)/6)*6 == bb) - j++; - - for (k = i, b[0] = 0, b[1] = 0; k < j; k++) { - m = ret->move[k]; - if (base_move(m) == bb) - b[0] = (b[0]+1+m-base_move(m)) % 4; - else - b[1] = (b[1]+1+m-base_move(m)) % 4; - } - - for (k = 0; k < 2; k++) { - if (b[k] != 0) { - ret->move[n] = bb + b[k] - 1 + 3*k; - ret->inv[n] = ret->inv[i]; - n++; - } - } - } - - L = ret->len; - ret->len = n; - } while (L != n); - - return ret; -} - -static void -cleanup_aux(Alg *alg, Alg *ret, bool inv) -{ - int i, j; - Cube c, d; - Move m; - Alg *equiv_alg; - - make_solved(&c); - for (i = 0; i < alg->len; i++) { - if (alg->inv[i] != inv) - continue; - - equiv_alg = new_alg(equiv_alg_string[alg->move[i]]); - - for (j = 0; j < equiv_alg->len; j++) - if (equiv_alg->move[j] == U) - append_move(ret, 3 * c.xp[U_center] + 1, inv); - else - apply_move(equiv_alg->move[j], &c); - - free_alg(equiv_alg); - } - - m = NULLMOVE; - switch (c.xp[F_center]) { - case U_center: - m = x3; - break; - case D_center: - m = x; - break; - case R_center: - m = y; - break; - case L_center: - m = y3; - break; - case B_center: - if (c.xp[U_center] == U_center) - m = y2; - else - m = x2; - break; - default: - break; - } - - make_solved(&d); - apply_move(m, &d); - if (m != NULLMOVE) - append_move(ret, m, inv); - - m = NULLMOVE; - if (c.xp[U_center] == d.xp[D_center]) { - m = z2; - } else if (c.xp[U_center] == d.xp[R_center]) { - m = z3; - } else if (c.xp[U_center] == d.xp[L_center]) { - m = z; - } - if (m != NULLMOVE) - append_move(ret, m, inv); -} - -void -init_moves() { - static bool initialized = false; - if (initialized) - return; - initialized = true; - - Move m; - Alg *equiv_alg[NMOVES]; - - static const Cube mcu = { - .ep = { UR, UF, UL, UB, DF, DL, DB, DR, FR, FL, BL, BR }, - .cp = { UBR, UFR, UFL, UBL, DFR, DFL, DBL, DBR }, - }; - static const Cube mcx = { - .ep = { DF, FL, UF, FR, DB, BL, UB, BR, DR, DL, UL, UR }, - .eo = { [UF] = 1, [UB] = 1, [DF] = 1, [DB] = 1 }, - .cp = { DFR, DFL, UFL, UFR, DBR, DBL, UBL, UBR }, - .co = { [UFR] = 2, [UBR] = 1, [UFL] = 1, [UBL] = 2, - [DBR] = 2, [DFR] = 1, [DBL] = 1, [DFL] = 2 }, - .xp = { F_center, B_center, R_center, - L_center, D_center, U_center }, - }; - static const Cube mcy = { - .ep = { UR, UF, UL, UB, DR, DF, DL, DB, BR, FR, FL, BL }, - .eo = { [FR] = 1, [FL] = 1, [BL] = 1, [BR] = 1 }, - .cp = { UBR, UFR, UFL, UBL, DBR, DFR, DFL, DBL }, - .xp = { U_center, D_center, B_center, - F_center, R_center, L_center }, - }; - - move_array[U] = mcu; - move_array[x] = mcx; - move_array[y] = mcy; - - for (m = 0; m < NMOVES; m++) - equiv_alg[m] = new_alg(equiv_alg_string[m]); - - for (m = 0; m < NMOVES; m++) { - switch (m) { - case NULLMOVE: - make_solved(&move_array[m]); - break; - case U: - case x: - case y: - break; - default: - make_solved(&move_array[m]); - apply_alg(equiv_alg[m], &move_array[m]); - break; - } - } - - for (m = 0; m < NMOVES; m++) - free_alg(equiv_alg[m]); -} - diff --git a/src/moves.h b/src/moves.h @@ -1,17 +0,0 @@ -#ifndef MOVES_H -#define MOVES_H - -#include "alg.h" -#include "cube.h" -#include "env.h" - -void apply_alg(Alg *alg, Cube *cube); -void apply_move(Move m, Cube *cube); -void apply_move_centers(Move m, Cube *cube); -void apply_move_corners(Move m, Cube *cube); -void apply_move_edges(Move m, Cube *cube); -Alg * cleanup(Alg *alg); - -void init_moves(); - -#endif diff --git a/src/movesets.c b/src/movesets.c @@ -1,194 +0,0 @@ -#define MOVESETS_C - -#include "movesets.h" - -static bool allowed_HTM(Move m); -static bool allowed_URF(Move m); -static bool allowed_eofb(Move m); -static bool allowed_drud(Move m); -static bool allowed_htr(Move m); -static bool can_append_HTM(Move l2, Move l1, Move m); -static bool can_append_HTM_cached(Alg *alg, Move m, bool inverse); -static bool cancel_niss_HTM_cached(Alg *alg); -static void init_can_append_HTM(); - -Moveset -moveset_HTM = { - .name = "HTM", - .allowed = allowed_HTM, - .can_append = can_append_HTM_cached, - .cancel_niss = cancel_niss_HTM_cached, -}; - -Moveset -moveset_URF = { - .name = "URF", - .allowed = allowed_URF, - .can_append = can_append_HTM_cached, - .cancel_niss = cancel_niss_HTM_cached, -}; - -Moveset -moveset_eofb = { - .name = "eofb", - .allowed = allowed_eofb, - .can_append = can_append_HTM_cached, - .cancel_niss = cancel_niss_HTM_cached, -}; - -Moveset -moveset_drud = { - .name = "drud", - .allowed = allowed_drud, - .can_append = can_append_HTM_cached, - .cancel_niss = cancel_niss_HTM_cached, -}; - -Moveset -moveset_htr = { - .name = "htr", - .allowed = allowed_htr, - .can_append = can_append_HTM_cached, - .cancel_niss = cancel_niss_HTM_cached, -}; - -Moveset * -all_movesets[] = { - &moveset_HTM, - &moveset_URF, - &moveset_eofb, - &moveset_drud, - &moveset_htr, - NULL -}; - -static uint64_t can_append_HTM_mask[NMOVES][NMOVES]; - -static bool -allowed_HTM(Move m) -{ - return m >= U && m <= B3; -} - -static bool -allowed_URF(Move m) -{ - Move b = base_move(m); - - return b == U || b == R || b == F; -} - -static bool -allowed_eofb(Move m) -{ - Move b = base_move(m); - - return b == U || b == D || b == R || b == L || - ((b == F || b == B) && m == b+1); -} - -static bool -allowed_drud(Move m) -{ - Move b = base_move(m); - - return b == U || b == D || - ((b == R || b == L || b == F || b == B) && m == b + 1); -} - -static bool -allowed_htr(Move m) -{ - Move b = base_move(m); - - return moveset_HTM.allowed(m) && m == b + 1; -} - -static bool -can_append_HTM(Move l2, Move l1, Move m) -{ - bool cancel, cancel_last, cancel_swap; - - cancel_last = l1 != NULLMOVE && base_move(l1) == base_move(m); - cancel_swap = l2 != NULLMOVE && base_move(l2) == base_move(m); - cancel = cancel_last || (commute(l1, l2) && cancel_swap); - - return !cancel; -} - -static bool -can_append_HTM_cached(Alg *alg, Move m, bool inverse) -{ - Move *moves, l1, l2; - uint64_t mbit; - int n; - - if (inverse) { - moves = alg->move_inverse; - n = alg->len_inverse; - } else { - moves = alg->move_normal; - n = alg->len_normal; - } - - l1 = n > 0 ? moves[n-1] : NULLMOVE; - l2 = n > 1 ? moves[n-2] : NULLMOVE; - - mbit = ((uint64_t)1) << m; - - return can_append_HTM_mask[l2][l1] & mbit; -} - -static bool -cancel_niss_HTM_cached(Alg *alg) -{ - Move i1, i2; - int n; - bool can_first, can_swap; - - n = alg->len_inverse; - i1 = n > 0 ? alg->move_inverse[n-1] : NULLMOVE; - i2 = n > 1 ? alg->move_inverse[n-2] : NULLMOVE; - - can_first = can_append_HTM_cached(alg, inverse_move(i1), false); - can_swap = can_append_HTM_cached(alg, inverse_move(i2), false); - - return can_first && (!commute(i1, i2) || can_swap); -} - -static void -init_can_append_HTM() -{ - Move l2, l1, m; - - for (l1 = 0; l1 < NMOVES; l1++) - for (l2 = 0; l2 < NMOVES; l2++) - for (m = 0; m < NMOVES; m++) - if (can_append_HTM(l2, l1, m)) - can_append_HTM_mask[l2][l1] - |= (((uint64_t)1) << m); -} - -void -init_moveset(Moveset *ms) -{ - int j; - Move m; - - for (j = 0, m = U; m < NMOVES; m++) - if (ms->allowed(m)) - ms->sorted_moves[j++] = m; - ms->sorted_moves[j] = NULLMOVE; - -/* TODO: should be here? maybe just init all movesets together anyway... */ - init_can_append_HTM(); -} - -void -init_movesets() -{ - int i; - - for (i = 0; all_movesets[i] != NULL; i++) - init_moveset(all_movesets[i]); -} diff --git a/src/movesets.h b/src/movesets.h @@ -1,15 +0,0 @@ -#ifndef MOVESETS_H -#define MOVESETS_H - -#include "alg.h" - -void init_moveset(Moveset *); -void init_movesets(); - -extern Moveset moveset_HTM; -extern Moveset moveset_URF; -extern Moveset moveset_eofb; -extern Moveset moveset_drud; -extern Moveset moveset_htr; - -#endif diff --git a/src/pruning.c b/src/pruning.c @@ -1,400 +0,0 @@ -#define PRUNING_C - -#include "pruning.h" - -#define ENTRIES_PER_GROUP (2*sizeof(entry_group_t)) -#define ENTRIES_PER_GROUP_COMPACT (4*sizeof(entry_group_t)) - -static int findchunk(PruneData *pd, int nchunks, uint64_t i); -static void genptable_bfs(PruneData *pd, int d, int nt, int nc); -static void genptable_fixnasty(PruneData *pd, int d, int nthreads); -static void * instance_bfs(void *arg); -static void * instance_fixnasty(void *arg); -static void ptable_update(PruneData *pd, uint64_t ind, int m); -static bool read_ptable_file(PruneData *pd); -static bool write_ptable_file(PruneData *pd); - -PruneData *active_pd[256]; - -int -findchunk(PruneData *pd, int nchunks, uint64_t i) -{ - uint64_t chunksize; - - chunksize = pd->coord->max / (uint64_t)nchunks; - chunksize += ENTRIES_PER_GROUP - (chunksize % ENTRIES_PER_GROUP); - - return MIN(nchunks-1, (int)(i / chunksize)); -} - -PruneData * -genptable(PruneData *pd, int nthreads) -{ - int d, nchunks, i, maxv; - uint64_t oldn; - - for (i = 0; active_pd[i] != NULL; i++) { - if (active_pd[i]->coord == pd->coord && - active_pd[i]->moveset == pd->moveset && - active_pd[i]->compact == pd->compact) - return active_pd[i]; - } - - init_moveset(pd->moveset); - gen_coord(pd->coord); - - pd->ptable = malloc(ptablesize(pd) * sizeof(entry_group_t)); - - if (read_ptable_file(pd)) - goto genptable_done; - - if (nthreads < 4) { - fprintf(stderr, - "--- Warning ---\n" - "You are using only %d threads to generate the pruning" - "tables. This can take a while.\n" - "Unless you did this intentionally, you should re-run" - "this command with `-t 4' or more.\n" - "---------------\n\n", nthreads - ); - } - - nchunks = MIN(ptablesize(pd), 100000); - fprintf(stderr, "Generating pt_%s_%s with %d threads\n", - pd->coord->name, pd->moveset->name, nthreads); - - memset(pd->ptable, ~(uint8_t)0, ptablesize(pd)*sizeof(entry_group_t)); - for (i = 0; i < 16; i++) - pd->count[i] = 0; - - ptable_update(pd, 0, 0); - pd->n = 1; - oldn = 0; - genptable_fixnasty(pd, 0, nthreads); - fprintf(stderr, "Depth %d done, generated %" - PRIu64 "\t(%" PRIu64 "/%" PRIu64 ")\n", - 0, pd->n - oldn, pd->n, pd->coord->max); - oldn = pd->n; - pd->count[0] = pd->n; - - maxv = pd->compact ? MIN(15, pd->base + 4) : 15; - for (d = 0; d < maxv && pd->n < pd->coord->max; d++) { - genptable_bfs(pd, d, nthreads, nchunks); - genptable_fixnasty(pd, d+1, nthreads); - fprintf(stderr, "Depth %d done, generated %" - PRIu64 "\t(%" PRIu64 "/%" PRIu64 ")\n", - d+1, pd->n - oldn, pd->n, pd->coord->max); - pd->count[d+1] = pd->n - oldn; - oldn = pd->n; - } - if (pd->compact) - fprintf(stderr, "Compact table, values above " - "%d are inaccurate.\n", maxv-1); - fprintf(stderr, "Pruning table generated!\n"); - - if (!write_ptable_file(pd)) - fprintf(stderr, "Error writing ptable file\n"); - -genptable_done: - for (i = 0; active_pd[i] != NULL; i++); - return active_pd[i] = pd; -} - -static void -genptable_bfs(PruneData *pd, int d, int nthreads, int nchunks) -{ - int i; - pthread_t t[nthreads]; - ThreadDataGenpt td[nthreads]; - pthread_mutex_t *mtx[nchunks], *upmtx; - - upmtx = malloc(sizeof(pthread_mutex_t)); - pthread_mutex_init(upmtx, NULL); - for (i = 0; i < nchunks; i++) { - mtx[i] = malloc(sizeof(pthread_mutex_t)); - pthread_mutex_init(mtx[i], NULL); - } - - for (i = 0; i < nthreads; i++) { - td[i].thid = i; - td[i].nthreads = nthreads; - td[i].pd = pd; - td[i].d = d; - td[i].nchunks = nchunks; - td[i].mutex = mtx; - td[i].upmutex = upmtx; - pthread_create(&t[i], NULL, instance_bfs, &td[i]); - } - - for (i = 0; i < nthreads; i++) - pthread_join(t[i], NULL); - - free(upmtx); - for (i = 0; i < nchunks; i++) - free(mtx[i]); -} - -static void -genptable_fixnasty(PruneData *pd, int d, int nthreads) -{ - int i; - pthread_t t[nthreads]; - ThreadDataGenpt td[nthreads]; - pthread_mutex_t *upmtx; - - if (pd->coord->type != SYMCOMP_COORD) - return; - - upmtx = malloc(sizeof(pthread_mutex_t)); - pthread_mutex_init(upmtx, NULL); - for (i = 0; i < nthreads; i++) { - td[i].thid = i; - td[i].nthreads = nthreads; - td[i].pd = pd; - td[i].d = d; - td[i].upmutex = upmtx; - pthread_create(&t[i], NULL, instance_fixnasty, &td[i]); - } - - for (i = 0; i < nthreads; i++) - pthread_join(t[i], NULL); - - free(upmtx); -} - -static void * -instance_bfs(void *arg) -{ - ThreadDataGenpt *td; - uint64_t i, ii, blocksize, rmin, rmax, updated; - int j, pval, ichunk, oldc, newc; - Move *ms; - - td = (ThreadDataGenpt *)arg; - ms = td->pd->moveset->sorted_moves; - blocksize = td->pd->coord->max / (uint64_t)td->nthreads; - rmin = ((uint64_t)td->thid) * blocksize; - rmax = td->thid == td->nthreads - 1 ? - td->pd->coord->max : - ((uint64_t)td->thid + 1) * blocksize; - - if (td->pd->compact) { - if (td->d <= td->pd->base) { - oldc = 1; - newc = 1; - } else { - oldc = td->d - td->pd->base; - newc = td->d - td->pd->base; - } - } else { - oldc = td->d; - newc = td->d + 1; - } - - updated = 0; - for (i = rmin; i < rmax; i++) { - ichunk = findchunk(td->pd, td->nchunks, i); - pthread_mutex_lock(td->mutex[ichunk]); - pval = ptableval(td->pd, i); - pthread_mutex_unlock(td->mutex[ichunk]); - if (pval == oldc) { - for (j = 0; ms[j] != NULLMOVE; j++) { - ii = move_coord(td->pd->coord, ms[j], i, NULL); - ichunk = findchunk(td->pd, td->nchunks, ii); - pthread_mutex_lock(td->mutex[ichunk]); - pval = ptableval(td->pd, ii); - if (pval > newc) { - ptable_update(td->pd, ii, newc); - updated++; - } - pthread_mutex_unlock(td->mutex[ichunk]); - } - if (td->pd->compact && td->d <= td->pd->base) { - ichunk = findchunk(td->pd, td->nchunks, i); - pthread_mutex_lock(td->mutex[ichunk]); - ptable_update(td->pd, i, 0); - pthread_mutex_unlock(td->mutex[ichunk]); - } - } - } - - pthread_mutex_lock(td->upmutex); - td->pd->n += updated; - pthread_mutex_unlock(td->upmutex); - - return NULL; -} - -static void * -instance_fixnasty(void *arg) -{ - ThreadDataGenpt *td; - uint64_t i, ii, blocksize, rmin, rmax, updated, ss, M; - int j, oldc; - Trans t; - - td = (ThreadDataGenpt *)arg; - - /* We know type = SYMCOMP_COORD */ - M = td->pd->coord->base[1]->max; - blocksize = (td->pd->coord->base[0]->max / td->nthreads) * M; - rmin = ((uint64_t)td->thid) * blocksize; - rmax = td->thid == td->nthreads - 1 ? - td->pd->coord->max : - ((uint64_t)td->thid + 1) * blocksize; - - if (td->pd->compact) { - if (td->d <= td->pd->base) - oldc = 1; - else - oldc = td->d - td->pd->base; - } else { - oldc = td->d; - } - - updated = 0; - for (i = rmin; i < rmax; i++) { - if (ptableval(td->pd, i) == oldc) { - ss = td->pd->coord->base[0]->selfsim[i/M]; - for (j = 0; j < td->pd->coord->base[0]->tgrp->n; j++) { - t = td->pd->coord->base[0]->tgrp->t[j]; - if (t == uf || !(ss & ((uint64_t)1<<t))) - continue; - ii = trans_coord(td->pd->coord, t, i); - if (ptableval(td->pd, ii) > oldc) { - ptable_update(td->pd, ii, oldc); - updated++; - } - } - } - } - - pthread_mutex_lock(td->upmutex); - td->pd->n += updated; - pthread_mutex_unlock(td->upmutex); - - return NULL; -} - -void -print_ptable(PruneData *pd) -{ - uint64_t i; - - printf("Table %s_%s\n", pd->coord->name, pd->moveset->name); - - if (pd->compact) { - printf("Compract table with base value: %d\n", pd->base); - printf("Values above %d are inaccurate.\n", pd->base + 3); - } - - for (i = 0; i < 16; i++) - printf("%2" PRIu64 "\t%10" PRIu64 "\n", i, pd->count[i]); -} - -uint64_t -ptablesize(PruneData *pd) -{ - uint64_t e; - - e = pd->compact ? ENTRIES_PER_GROUP_COMPACT : ENTRIES_PER_GROUP; - - return (pd->coord->max + e - 1) / e; -} - -static void -ptable_update(PruneData *pd, uint64_t ind, int n) -{ - int sh; - entry_group_t f, mask; - uint64_t i, e, b; - - e = pd->compact ? ENTRIES_PER_GROUP_COMPACT : ENTRIES_PER_GROUP; - b = pd->compact ? 2 : 4; - f = pd->compact ? 3 : 15; - - sh = b * (ind % e); - mask = f << sh; - i = ind / e; - - pd->ptable[i] &= ~mask; - pd->ptable[i] |= (((entry_group_t)n) & f) << sh; -} - -int -ptableval(PruneData *pd, uint64_t ind) -{ - int sh; - uint64_t e; - entry_group_t m; - - if (pd->compact) { - e = ENTRIES_PER_GROUP_COMPACT; - m = 3; - sh = (ind % e) * 2; - } else { - e = ENTRIES_PER_GROUP; - m = 15; - sh = (ind % e) * 4; - } - - return (pd->ptable[ind/e] & (m << sh)) >> sh; -} - -static bool -read_ptable_file(PruneData *pd) -{ - init_env(); - - FILE *f; - char fname[strlen(tabledir)+256]; - int i; - uint64_t r; - - strcpy(fname, tabledir); - strcat(fname, "/pt_"); - strcat(fname, pd->coord->name); - strcat(fname, "_"); - strcat(fname, pd->moveset->name); - - if ((f = fopen(fname, "rb")) == NULL) - return false; - - r = fread(&(pd->base), sizeof(int), 1, f); - for (i = 0; i < 16; i++) - r += fread(&(pd->count[i]), sizeof(uint64_t), 1, f); - r += fread(pd->ptable, sizeof(entry_group_t), ptablesize(pd), f); - - fclose(f); - - return r == 17 + ptablesize(pd); -} - -static bool -write_ptable_file(PruneData *pd) -{ - init_env(); - - FILE *f; - char fname[strlen(tabledir)+256]; - int i; - uint64_t w; - - strcpy(fname, tabledir); - strcat(fname, "/pt_"); - strcat(fname, pd->coord->name); - strcat(fname, "_"); - strcat(fname, pd->moveset->name); - - if ((f = fopen(fname, "wb")) == NULL) - return false; - - w = fwrite(&(pd->base), sizeof(int), 1, f); - for (i = 0; i < 16; i++) - w += fwrite(&(pd->count[i]), sizeof(uint64_t), 1, f); - w += fwrite(pd->ptable, sizeof(entry_group_t), ptablesize(pd), f); - fclose(f); - - return w == 17 + ptablesize(pd); -} - diff --git a/src/pruning.h b/src/pruning.h @@ -1,16 +0,0 @@ -#ifndef PRUNING_H -#define PRUNING_H - -#include "coord.h" -#include "movesets.h" - -void free_pd(PruneData *pd); -PruneData * genptable(PruneData *data, int nthreads); -void print_ptable(PruneData *pd); -uint64_t ptablesize(PruneData *pd); -int ptableval(PruneData *pd, uint64_t ind); - -extern PruneData *active_pd[256]; - -#endif - diff --git a/src/shell.c b/src/shell.c @@ -1,177 +0,0 @@ -#define SHELL_C - -#include "shell.h" - -static void cleanwhitespaces(char *line); -static int parseline(char *line, char **v); - -bool -checkfiles() -{ - /* TODO: add more checks (other files, use checksum...) */ - /* How to check for pruning tables with new method? */ - /* Solution: use list of steps */ - /* - char fname[strlen(tabledir)+100]; - int i; - - for (i = 0; all_pd[i] != NULL; i++) { - strcpy(fname, tabledir); - strcat(fname, "/"); - strcat(fname, all_pd[i]->filename); - if ((f = fopen(fname, "rb")) == NULL) - return false; - else - fclose(f); - } - */ - - return true; -} - -static void -cleanwhitespaces(char *line) -{ - char *i; - - for (i = line; *i != 0; i++) - if (*i == '\t' || *i == '\n') - *i = ' '; -} - -/* This function assumes that **v is large enough */ -static int -parseline(char *line, char **v) -{ - char *t; - int n = 0; - - cleanwhitespaces(line); - - for (t = strtok(line, " "); t != NULL; t = strtok(NULL, " ")) - strcpy(v[n++], t); - - return n; -} - -void -exec_args(int c, char **v) -{ - int i; - char line[MAXLINELEN]; - Command *cmd = NULL; - CommandArgs *args; - Alg *scramble; - - for (i = 0; commands[i] != NULL; i++) - if (!strcmp(v[0], commands[i]->name)) - cmd = commands[i]; - - if (cmd == NULL) { - fprintf(stderr, "%s: command not found\n", v[0]); - return; - } - - args = cmd->parse_args(c-1, &v[1]); - if (!args->success) { - fprintf(stderr, "usage: %s\n", cmd->usage); - return; - } - - if (args->scrstdin) { - while (true) { - if (fgets(line, MAXLINELEN, stdin) == NULL) { - clearerr(stdin); - break; - } - - scramble = new_alg(line); - - printf(">>> Line: %s", line); - - if (scramble != NULL && scramble->len > 0) { - args->scramble = scramble; - cmd->exec(args); - free_alg(scramble); - args->scramble = NULL; - } - } - } else { - cmd->exec(args); - } - free_args(args); -} - -void -launch(bool batchmode) -{ - int i, shell_argc; - char line[MAXLINELEN], **shell_argv; - - shell_argv = malloc(MAXNTOKENS * sizeof(char *)); - for (i = 0; i < MAXNTOKENS; i++) - shell_argv[i] = malloc((MAXTOKENLEN+1) * sizeof(char)); - - if (!batchmode) { - fprintf(stderr, "Welcome to Nissy "VERSION".\n" - "Type \"commands\" for a list of commands.\n"); - } - - while (true) { - if (!batchmode) { - fprintf(stdout, "nissy-# "); - } - - if (fgets(line, MAXLINELEN, stdin) == NULL) - break; - - if (batchmode) { - printf(">>>\n" - ">>> Executing command: %s" - ">>>\n", line); - } - - shell_argc = parseline(line, shell_argv); - - if (shell_argc > 0) - exec_args(shell_argc, shell_argv); - } - - for (i = 0; i < MAXNTOKENS; i++) - free(shell_argv[i]); - free(shell_argv); -} - -#ifndef TEST -int -main(int argc, char *argv[]) -{ - char *closing_cmd[1] = { "freemem" }; - - init_env(); - init_trans(); - - if (!checkfiles()) { - fprintf(stderr, - "--- Warning ---\n" - "Some pruning tables are missing or unreadable\n" - "You can generate them with `nissy gen'.\n" - "---------------\n\n" - ); - } - - if (argc > 1) { - if (!strcmp(argv[1], "-b")) { - launch(true); - } else { - exec_args(argc-1, &argv[1]); - } - } else { - launch(false); - } - - exec_args(1, closing_cmd); - - return 0; -} -#endif diff --git a/src/shell.h b/src/shell.h @@ -1,14 +0,0 @@ -#ifndef SHELL_H -#define SHELL_H - -#include "commands.h" - -#define MAXLINELEN 10000 -#define MAXTOKENLEN 255 -#define MAXNTOKENS 255 - -bool checkfiles(); -void exec_args(int c, char **v); -void launch(bool batchmode); - -#endif diff --git a/src/solve.c b/src/solve.c @@ -1,122 +0,0 @@ -#define SOLVE_C - -#include "solve.h" - -void -dfs(DfsArg *arg, Solver *solver, Threader *threader) -{ - int i; - DfsArg newarg; - Alg *sol; - Move m; - - if (arg->current_alg->len > arg->d) - return; - - if (solver->is_solved(solver->param, arg->cubedata)) { -/* TODO: the "all" option should be re-implemented as setting -validate to null */ - -/* TODO: we also have to check if cancel with NISS; -we can't because we have no access to the s->final field -this should be done by the step's validator? */ - sol = solver->validate_solution(solver->param,arg->current_alg); - bool accepted = sol != NULL; - bool too_short = arg->current_alg->len != arg->d; - - if (accepted && !too_short) { -/* TODO: arg->t got lost in refactoring */ -/* transform_alg(inverse_trans(arg->t), sol);*/ - if (arg->opts->verbose) - print_alg(sol, false); - threader->append_sol(sol, arg->threaddata); - } - return; - } - - if (arg->current_alg->len == arg->d) - return; - -/* TODO: do not alloc */ - newarg.cubedata = solver->alloc_cubedata(solver->param); - for (i = 0; solver->moveset->sorted_moves[i] != NULLMOVE; i++) { - m = solver->moveset->sorted_moves[i]; - if (solver->moveset->can_append(arg->current_alg, m, arg->niss) - && compare_last(arg->current_alg, m, arg->niss) >= 0) { - append_move(arg->current_alg, m, arg->niss); - - solver->copy_cubedata( - solver->param, arg->cubedata, newarg.cubedata); - newarg.threaddata = arg->threaddata; - newarg.opts = arg->opts; - newarg.d = arg->d; - newarg.niss = arg->niss; - newarg.current_alg = arg->current_alg; - if (!solver->move_check_stop( - solver->param, &newarg, threader)) - dfs(&newarg, solver, threader); - - remove_last_move(arg->current_alg); - } - } - solver->free_cubedata(solver->param, newarg.cubedata); - - if (arg->opts->can_niss && !arg->niss && - solver->niss_makes_sense( - solver->param, arg->cubedata, arg->current_alg)) { - solver->invert_cube(solver->param, arg->cubedata); - arg->niss = true; - dfs(arg, solver, threader); - } -} - -AlgList * -solve(Cube *cube, SolveOptions *opts, Solver **solver, Threader *threader) -{ - int i, d, optimal; - bool ready[MAX_SOLVERS], stop, one_ready; - DfsArg arg[MAX_SOLVERS]; - AlgList *sols; - - one_ready = false; - for (i = 0; solver[i] != NULL; i++) { - arg[i].cubedata = - solver[i]->prepare_cube(solver[i]->param, cube); - arg[i].opts = opts; - ready[i] = arg[i].cubedata != NULL; - one_ready = one_ready || ready[i]; - } - - sols = new_alglist(); - if (!one_ready) { - fprintf(stderr, "Cube not ready for solving\n"); - return sols; - } - - optimal = opts->max_moves; - stop = false; - for (d = opts->min_moves; d <= opts->max_moves && !stop; d++) { - if (opts->verbose) - fprintf(stderr, "Searching depth %d\n", d); - - for (i = 0; solver[i] != NULL && !stop; i++) { - if (!ready[i]) - continue; - - arg[i].d = d; - threader->dispatch(&arg[i], sols, solver[i], threader); - - if (sols->len > 0) - optimal = MIN(optimal, d); - - stop = sols->len >= opts->max_solutions; - } - stop = stop || - (opts->optimal != -1 && d >= opts->optimal + optimal); - } - -/* TODO: some cleanup (free cubedata) */ -/* TODO: actually, preparation should be done somewhere else */ - - return sols; -} diff --git a/src/solve.h b/src/solve.h @@ -1,54 +0,0 @@ -#ifndef SOLVE_H -#define SOLVE_H - -#include "moves.h" - -#define MAX_SOLVERS 99 - -typedef struct dfsarg DfsArg; -typedef struct threader Threader; -typedef struct solver Solver; - -/* TODO: add solver and threader in DfsData, remove from dispatch args and similar */ - -struct dfsarg { - void * cubedata; - void * threaddata; - SolveOptions * opts; - int d; - bool niss; - Alg * current_alg; -}; - -struct threader { - void (*append_sol)(Alg *, void *); - void (*dispatch)(DfsArg *, AlgList *, Solver *, Threader *); - int (*get_nsol)(void *); -/* TODO: threader should have param, like solver? */ -}; - -struct solver { - Moveset * moveset; - bool (*move_check_stop)(void *, DfsArg *, Threader *); - Alg * (*validate_solution)(void *, Alg *); - bool (*niss_makes_sense)(void *, void *, Alg *); -/* TODO: move param to somewhere where it makes more sense */ - void * param; -/* TODO: the following should be part of a generic cube description */ -/* TODO: remove alloc? */ -/* TODO: revisit apply_move, maybe apply_alg? or both? */ - void * (*alloc_cubedata)(void *); - void (*copy_cubedata)(void *, void *, void *); - void (*free_cubedata)(void *, void *); - void (*invert_cube)(void *, void *); - bool (*is_solved)(void *, void *); - void (*apply_move)(void *, void *, Move); -/* TODO: remove dependence on Cube, preparation should be done before */ - void * (*prepare_cube)(void *, Cube *); -}; - -void dfs(DfsArg *, Solver *, Threader *); -/* TODO: remove dependence on Cube, preparation should be done before */ -AlgList * solve(Cube *, SolveOptions *, Solver **, Threader *); - -#endif diff --git a/src/solver_step.c b/src/solver_step.c @@ -1,306 +0,0 @@ -#include "solver_step.h" - -typedef struct { - Cube * cube; - uint64_t * val; - Trans * t; -} CubeData; - -static void apply_move_cubedata(void *, void *, Move); -static void init_indexes(Step *, CubeData *); -static void * prepare_cube(void *, Cube *); -static bool move_check_stop_eager(void *, DfsArg *, Threader *); -static bool move_check_stop_lazy(void *, DfsArg *, Threader *); -static bool move_check_stop_nonsol(void *, DfsArg *, Threader *); -static bool is_solved_step(void *, void *); -static Alg * validate_solution(void *, Alg *); -static void * alloc_cubedata(void *); -static void copy_cubedata(void *, void *, void *); -static void free_cubedata(void *, void *); -static void invert_cubedata(void *, void *); -static bool niss_makes_sense(void *, void *, Alg *); -static Solver * new_stepsolver_nocheckstop(Step *step); - -static void -apply_move_cubedata(void *param, void *cubedata, Move m) -{ - Step *s = (Step *)param; - CubeData *data = (CubeData *)cubedata; - - Trans tt; - for (int i = 0; i < s->n_coord; i++) { - Move mm = transform_move(data->t[i], m); - data->val[i] = move_coord(s->coord[i], mm, data->val[i], &tt); - data->t[i] = transform_trans(tt, data->t[i]); - } -} - -static void -init_indexes(Step *step, CubeData *data) -{ - int i; - Cube moved; - Trans t, tt; - - for (i = 0; i < step->n_coord; i++) { - t = step->coord_trans[i]; - copy_cube(data->cube, &moved); - apply_trans(t, &moved); - data->val[i] = index_coord(step->coord[i], &moved, &tt); - data->t[i] = transform_trans(tt, t); - } -} - -static void * -prepare_cube(void *param, Cube *cube) -{ - int i; - Step *s; - CubeData *data; - - s = (Step *)param; - - for (i = 0; i < s->n_coord; i++) { - s->pd[i] = malloc(sizeof(PruneData)); - s->pd[i]->moveset = s->moveset; -/* TODO: check if moveset initialization works fine, - e.g. if there is a variable to save the initialized status - or if it gets initialized multiple times */ - init_moveset(s->moveset); - s->pd[i]->coord = s->coord[i]; - gen_coord(s->coord[i]); - s->pd[i]->compact = s->pd_compact[i]; - s->pd[i] = genptable(s->pd[i], 4); /* TODO: threads */ - } - - data = alloc_cubedata(param); - data->cube = malloc(sizeof(Cube)); - copy_cube(cube, data->cube); - init_indexes(s, data); - - return data; -} - -static bool -move_check_stop_eager(void *param, DfsArg *arg, Threader *threader) -{ - int nsol; - - if (move_check_stop_nonsol(param, arg, threader)) - return true; - - nsol = threader->get_nsol(arg->threaddata); - return nsol >= arg->opts->max_solutions; -} - -static bool -move_check_stop_lazy(void *param, DfsArg *arg, Threader *threader) -{ - int nsol; - - nsol = threader->get_nsol(arg->threaddata); - if (nsol >= arg->opts->max_solutions) - return true; - - return move_check_stop_nonsol(param, arg, threader); -} - -/* TODO: split in 2 (nissable / non-nissable) and only move cube - when nissable */ -static bool -move_check_stop_nonsol(void *param, DfsArg *arg, Threader *threader) -{ - int i, goal, bound; - Move mm, lastmove; - Trans tt = uf; - CubeData *data; - Step *s; - - s = (Step *)param; - data = (CubeData *)arg->cubedata; - - - bound = 0; - goal = arg->d - arg->current_alg->len; -/* TODO: check if len is 0 */ - lastmove = arg->current_alg->move[arg->current_alg->len-1]; - for (i = 0; i < s->n_coord; i++) { - mm = transform_move(data->t[i], lastmove); - data->val[i] = move_coord(s->coord[i], mm, data->val[i], &tt); - data->t[i] = transform_trans(tt, data->t[i]); - - bound = MAX(bound, ptableval(s->pd[i], data->val[i])); - if (arg->opts->can_niss && !arg->niss) - bound = MIN(1, bound); - - if (bound > goal) { - return true; - } - } - if (arg->opts->can_niss && !arg->niss) - apply_move(lastmove, data->cube); - - return false; -} - -static bool -is_solved_step(void *param, void *cubedata) -{ - int i; - Step *s; - CubeData *data; - - s = (Step *)param; - data = (CubeData *)cubedata; - - for (i = 0; i < s->n_coord; i++) - if (data->val[i] != 0) - return false; - - return true; -} - -static Alg * -validate_solution(void *param, Alg *alg) -{ - return ((Step *)param)->is_valid(alg); -} - -static void * -alloc_cubedata(void *param) -{ - Step *s; - CubeData *data; - - s = (Step *)param; - - data = malloc(sizeof(CubeData)); - /* We do not need to allocate a cube */ - data->val = malloc(s->n_coord * sizeof(uint64_t)); - data->t = malloc(s->n_coord * sizeof(Trans)); - - return data; -} - -static void -copy_cubedata(void *param, void *src, void *dst) -{ - int i; - Step *s; - CubeData *newdata, *olddata; - - s = (Step *)param; - olddata = (CubeData *)src; - newdata = (CubeData *)dst; - -/* TODO: do not copy if not nissable */ - newdata->cube = malloc(sizeof(Cube)); - copy_cube(olddata->cube, newdata->cube); - for (i = 0; i < s->n_coord; i++) { - newdata->val[i] = olddata->val[i]; - newdata->t[i] = olddata->t[i]; - } -} - -static void -free_cubedata(void *param, void *cubedata) -{ - CubeData *data; - - data = (CubeData *)cubedata; - - free(data->t); - free(data->val); - free(data->cube); - free(data); -} - -static void -invert_cubedata(void *param, void *cubedata) -{ - Step *s; - CubeData *data; - - s = (Step *)param; - data = (CubeData *)cubedata; - - invert_cube(data->cube); - init_indexes(s, data); -} - -static bool -niss_makes_sense(void *param, void *cubedata, Alg *alg) -{ - Step *s; - CubeData *data; - - s = (Step *)param; - data = (CubeData *)cubedata; - - if (s->final) - return false; - - if (alg->len_normal == 0) - return true; - - Move m = inverse_move(alg->move_normal[alg->len_normal-1]); - for (int i = 0; i < s->n_coord; i++) { - Move mm = transform_move(data->t[i], m); - uint64_t u = move_coord(s->coord[i], mm, 0, NULL); - if (ptableval(s->pd[i], u) > 0) - return true; - } - - return false; -} - -static Solver * -new_stepsolver_nocheckstop(Step *step) -{ - Solver *solver; - - solver = malloc(sizeof(Solver)); - - solver->moveset = step->moveset; - solver->param = step; - - solver->apply_move = apply_move_cubedata; - solver->prepare_cube = prepare_cube; - solver->is_solved = is_solved_step; - solver->validate_solution = validate_solution; - solver->alloc_cubedata = alloc_cubedata; - solver->copy_cubedata = copy_cubedata; - solver->free_cubedata = free_cubedata; - solver->invert_cube = invert_cubedata; - solver->niss_makes_sense = niss_makes_sense; - - return solver; -} - -Solver * -new_stepsolver_eager(Step *step) -{ - Solver *solver; - - solver = new_stepsolver_nocheckstop(step); - solver->move_check_stop = move_check_stop_eager; - - return solver; -} - -Solver * -new_stepsolver_lazy(Step *step) -{ - Solver *solver; - - solver = new_stepsolver_nocheckstop(step); - solver->move_check_stop = move_check_stop_lazy; - - return solver; -} - -void -free_stepsolver(Solver *solver) -{ - free(solver); -} diff --git a/src/solver_step.h b/src/solver_step.h @@ -1,12 +0,0 @@ -#ifndef SOLVER_STEP_H -#define SOLVER_STEP_H - -#include "cube.h" -#include "solve.h" -#include "steps.h" - -Solver *new_stepsolver_eager(Step *); -Solver *new_stepsolver_lazy(Step *); -void free_stepsolver(Solver *); - -#endif diff --git a/src/steps.c b/src/steps.c @@ -1,177 +0,0 @@ -#define STEPS_C - -#include "steps.h" - -/* TODO: change all checkers to use coordinates! */ - -bool -check_centers(Cube *cube) -{ - int i; - - for (i = 0; i < 6; i++) - if (cube->xp[i] != i) - return false; - - return true; -} - -bool -check_coud_HTM(Cube *cube) -{ - int i; - - for (i = 0; i < 8; i++) - if (cube->co[i] != 0) - return false; - - return true; -} - -bool -check_coud_URF(Cube *cube) -{ - Cube c2, c3; - - copy_cube(cube, &c2); - copy_cube(cube, &c3); - - apply_move(z, &c2); - apply_move(x, &c3); - - return check_coud_HTM(cube) || - check_coud_HTM(&c2) || - check_coud_HTM(&c3); -} - -bool -check_cp_HTM(Cube *cube) -{ - int i; - - for (i = 0; i < 8; i++) - if (cube->cp[i] != i) - return false; - - return true; -} - -bool -check_corners_HTM(Cube *cube) -{ - return check_coud_HTM(cube) && check_cp_HTM(cube); -} - -bool -check_corners_URF(Cube *cube) -{ - Cube c; - Trans i; - - for (i = 0; i < NROTATIONS; i++) { - copy_cube(cube, &c); - apply_alg(rotation_alg(i), &c); - if (check_corners_HTM(&c)) - return true; - } - - return false; -} - -bool -check_cornershtr(Cube *cube) -{ - /* TODO (use coord) */ - return true; -} - -bool -check_eofb(Cube *cube) -{ - /* TODO (use coord) */ - return true; -} - -bool -check_drud(Cube *cube) -{ - /* TODO (use coord) */ - return true; -} - -bool -check_htr(Cube *cube) -{ - /* TODO (check_drud(cube) and coord_htr_drud == 0) */ - return true; -} - -Alg * -validate_singlecw_ending(Alg *alg) -{ - int i; - bool nor, inv; - Alg *ret; - Move l2 = NULLMOVE, l1 = NULLMOVE, l2i = NULLMOVE, l1i = NULLMOVE; - - for (i = 0; i < alg->len; i++) { - if (alg->inv[i]) { - l2i = l1i; - l1i = alg->move[i]; - } else { - l2 = l1; - l1 = alg->move[i]; - } - } - - nor = l1 ==base_move(l1) && (!commute(l1, l2) ||l2 ==base_move(l2)); - inv = l1i==base_move(l1i) && (!commute(l1i,l2i)||l2i==base_move(l2i)); - - if (nor && inv) { - ret = new_alg(""); - copy_alg(alg, ret); - } else { - ret = NULL; - } - - return ret; -} - -/* Public functions **********************************************************/ - -/* -void -compute_ind(Step *s, Cube *cube, Movable *ind) -{ - int i; - Cube mvd; - Trans t, tt; - - for (i = 0; i < s->n_coord; i++) { - t = s->coord_trans[i]; - copy_cube(cube, &mvd); - apply_trans(t, &mvd); - - ind[i].val = index_coord(s->coord[i], &mvd, &tt); - ind[i].t = transform_trans(tt, t); - } -} -*/ - -void -prepare_cs(ChoiceStep *cs, SolveOptions *opts) -{ - int i, j; - Step *s; - - for (i = 0; cs->step[i] != NULL; i++) { - s = cs->step[i]; - for (j = 0; j < s->n_coord; j++) { - s->pd[j] = malloc(sizeof(PruneData)); - s->pd[j]->moveset = s->moveset; - s->pd[j]->coord = s->coord[j]; - s->pd[j]->compact = s->pd_compact[j]; - s->pd[j] = genptable(s->pd[j], opts->nthreads); - } - } -} diff --git a/src/steps.h b/src/steps.h @@ -1,244 +0,0 @@ -#ifndef STEPS_H -#define STEPS_H - -#include "pruning.h" -#include "movesets.h" - -bool check_centers(Cube *cube); -bool check_coud_HTM(Cube *cube); -bool check_coud_URF(Cube *cube); -bool check_cp_HTM(Cube *cube); -bool check_corners_HTM(Cube *cube); -bool check_corners_URF(Cube *cube); -bool check_cornershtr(Cube *cube); -bool check_eofb(Cube *cube); -bool check_drud(Cube *cube); -bool check_htr(Cube *cube); -/*void compute_ind(Step *a, Cube *cube, Movable *ind);*/ -void prepare_cs(ChoiceStep *cs, SolveOptions *opts); -bool always_valid(Alg *alg); -Alg * validate_singlecw_ending(Alg *alg); - -#ifndef STEPS_C - -extern char check_centers_msg[100]; -extern char check_eo_msg[100]; -extern char check_dr_msg[100]; -extern char check_htr_msg[100]; -extern char check_drany_msg[100]; - -extern Step step_eofb_HTM; -extern Step step_drud_HTM; -extern Step step_drfin_drud; - -extern ChoiceStep optimal_HTM; -extern ChoiceStep eoany_HTM; -extern ChoiceStep eofb_HTM; -extern ChoiceStep eorl_HTM; -extern ChoiceStep eoud_HTM; -extern ChoiceStep drany_HTM; -extern ChoiceStep drud_HTM; -extern ChoiceStep drrl_HTM; -extern ChoiceStep drfb_HTM; -extern ChoiceStep dranyfin_DR; -extern ChoiceStep drudfin_drud; -extern ChoiceStep drrlfin_drrl; -extern ChoiceStep drfbfin_drfb; - -extern ChoiceStep *csteps[]; - -#else - -char check_centers_msg[100] = "cube must be oriented (centers solved)"; -char check_eo_msg[100] = "EO must be solved on given axis"; -char check_dr_msg[100] = "DR must be solved on given axis"; -char check_htr_msg[100] = "HTR must be solved"; -char check_drany_msg[100] = "DR must be solved on at least one axis"; - -/* Optimal after EO ******************/ -/* TODO: eofin_eo (generic), eofbfin_eofb, eorlfin_eorl, eoudfin_eoud */ - -/* EO steps **************************/ -/* TODO: eoany_HTM (generic), eofb_HTM, eorl_HTM, eoud_HTM */ - -Step -step_eofb_HTM = { - .ready = check_centers, - .final = false, - .moveset = &moveset_HTM, - .n_coord = 1, - .coord = {&coord_eofb}, - .coord_trans = {uf}, - .is_valid = validate_singlecw_ending, -}; -ChoiceStep -eoany_HTM = { - .shortname = "eo", - .name = "EO on any axis", - .step = {&step_eofb_HTM, &step_eofb_HTM, &step_eofb_HTM, NULL}, - .t = {uf, ur, fd}, - .ready_msg = check_centers_msg, -}; -ChoiceStep -eofb_HTM = { - .shortname = "eofb", - .name = "EO on F/B", - .step = {&step_eofb_HTM, NULL}, - .t = {uf}, - .ready_msg = check_centers_msg, -}; -ChoiceStep -eorl_HTM = { - .shortname = "eorl", - .name = "EO on R/L", - .step = {&step_eofb_HTM, NULL}, - .t = {ur}, - .ready_msg = check_centers_msg, -}; -ChoiceStep -eoud_HTM = { - .shortname = "eoud", - .name = "EO on U/D", - .step = {&step_eofb_HTM, NULL}, - .t = {fd}, - .ready_msg = check_centers_msg, -}; - -/* CO steps **************************/ -/* TODO: coany_HTM (generic), cofb_HTM, corl_HTM, coud_HTM */ -/* TODO: coany_URF (generic), cofb_URF, corl_URF, coud_URF */ - -/* Misc corner steps *****************/ -/* TODO: cornershtr_HTM, cornershtr_URF, corners_HTM, corners_URF */ -/* TODO (new): corners_drud */ - -/* DR steps **************************/ -/* TODO: dr_eo (generic) */ -/* TODO: dr_eofb (generic), dr_eorl (generic), dr_eoud (generic) */ -/* TODO: drud_eofb, drrl_eofb, drud_eorl, drfb_eorl, drrl_eoud, drfb_eoud */ - -Step -step_drud_HTM = { - .ready = check_centers, - .final = false, - .moveset = &moveset_HTM, - .n_coord = 1, - .coord = {&coord_drud_sym16}, - .coord_trans = {uf}, - .is_valid = validate_singlecw_ending, -}; -ChoiceStep -drany_HTM = { - .shortname = "dr", - .name = "DR on any axis", - .step = {&step_drud_HTM, &step_drud_HTM, &step_drud_HTM, NULL}, - .t = {uf, rf, fd}, - .ready_msg = check_centers_msg, -}; -ChoiceStep -drud_HTM = { - .shortname = "drud", - .name = "DR on U/D", - .step = {&step_drud_HTM, NULL}, - .t = {uf}, - .ready_msg = check_centers_msg, -}; -ChoiceStep -drrl_HTM = { - .shortname = "drrl", - .name = "DR on R/L", - .step = {&step_drud_HTM, NULL}, - .t = {rf}, - .ready_msg = check_centers_msg, -}; -ChoiceStep -drfb_HTM = { - .shortname = "drfb", - .name = "DR on F/B", - .step = {&step_drud_HTM, NULL}, - .t = {fd}, - .ready_msg = check_centers_msg, -}; - -/* DR finish steps */ -Step -step_drfin_drud = { - .ready = check_drud, - .final = true, - .moveset = &moveset_drud, - .n_coord = 1, - .coord = {&coord_drudfin_noE_sym16}, /* TODO: maybe no noE */ - .coord_trans = {uf}, - .is_valid = NULL, -}; -ChoiceStep -dranyfin_DR = { - .shortname = "drfin", - .name = "DR finish on any axis without breaking DR", - .step = {&step_drfin_drud, &step_drfin_drud, - &step_drfin_drud, NULL}, - .t = {uf, rf, fd}, - .ready_msg = check_dr_msg, -}; -ChoiceStep -drudfin_drud = { - .shortname = "drudfin", - .name = "DR finis on U/D without breaking DR", - .step = {&step_drfin_drud, NULL}, - .t = {uf}, - .ready_msg = check_dr_msg, -}; -ChoiceStep -drrlfin_drrl = { - .shortname = "drrlfin", - .name = "DR finish on R/L without breaking DR", - .step = {&step_drfin_drud, NULL}, - .t = {rf}, - .ready_msg = check_dr_msg, -}; -ChoiceStep -drfbfin_drfb = { - .shortname = "drfbfin", - .name = "DR finish on F/B without breaking DR", - .step = {&step_drfin_drud, NULL}, - .t = {fd}, - .ready_msg = check_dr_msg, -}; - -/* HTR from DR */ -/* TODO: htr_any (generic), htr_drud, htr_drrl, htr_drfb */ - -/* HTR finish */ -/* TODO: htrfin_htr */ - -ChoiceStep *csteps[] = { -/* TODO: re-implement optimal - &optimal_HTM, -*/ - - &eoany_HTM, &eofb_HTM, &eorl_HTM, &eoud_HTM, - &drany_HTM, &drud_HTM, &drrl_HTM, &drfb_HTM, - &dranyfin_DR, &drudfin_drud, &drrlfin_drrl, &drfbfin_drfb, - -NULL -/* TODO: - &optimal_light_HTM, - - &eofin_eo, &eofbfin_eofb, &eorlfin_eorl, &eoudfin_eoud, - &coany_HTM, &coud_HTM, &corl_HTM, &cofb_HTM, - &coany_URF, &coud_URF, &corl_URF, &cofb_URF, - &dr_eo, &dr_eofb, &dr_eorl, &dr_eoud, - &drud_eofb, &drrl_eofb, - &drud_eorl, &drfb_eorl, - &drfb_eoud, &drrl_eoud, - &htr_any, &htr_drud, &htr_drrl, &htr_drfb, - &htrfin_htr, - &cornershtr_HTM, &cornershtr_URF, &corners_HTM, &corners_URF, - NULL -*/ - -}; - -#endif - -#endif diff --git a/src/threader_eager.c b/src/threader_eager.c @@ -1,163 +0,0 @@ -#include <pthread.h> -#include "threader_eager.h" - -typedef struct { - AlgList * sols; - pthread_mutex_t * sols_mutex; -} ThreadData; - -typedef struct { - DfsArg * arg; - Solver * solver; - Threader * threader; - AlgList * starts; - AlgListNode ** node; - pthread_mutex_t * start_mutex; -} ThreadInitData; - -static void append_sol(Alg *, void *); -static void * instance_thread(void *); -static void dispatch(DfsArg *, AlgList *, Solver *, Threader *); -static AlgList * possible_starts(DfsArg *, Solver *); -static int get_nsol(void *); - -Threader threader_eager = { - .append_sol = append_sol, - .dispatch = dispatch, - .get_nsol = get_nsol, -}; - -static void -append_sol(Alg *alg, void *threaddata) -{ - ThreadData *td = (ThreadData *)threaddata; - - pthread_mutex_lock(td->sols_mutex); - append_alg(td->sols, alg); - pthread_mutex_unlock(td->sols_mutex); -} - -static AlgList * -possible_starts(DfsArg *arg, Solver *solver) -{ - AlgList *ret = new_alglist(); - - if (solver->is_solved(solver->param, arg->cubedata)) { - if (arg->opts->min_moves == 0 && arg->d == 0) - append_sol(new_alg(""), arg->threaddata); - return ret; - } - - for (int i = 0; solver->moveset->sorted_moves[i] != NULLMOVE; i++) { - Move m = solver->moveset->sorted_moves[i]; - Alg *alg = new_alg(""); - append_move(alg, m, false); - append_alg(ret, alg); - free_alg(alg); - -/* TODO: check if step not final */ - if (arg->opts->can_niss) { - alg = new_alg(""); - append_move(alg, m, true); - append_alg(ret, alg); - free_alg(alg); - } - } - - return ret; -} - -static void * -instance_thread(void *arg) -{ - ThreadInitData *tid = (ThreadInitData *)arg; - - while (true) { - pthread_mutex_lock(tid->start_mutex); - AlgListNode *node = *(tid->node); - if (node == NULL) { - pthread_mutex_unlock(tid->start_mutex); - break; - } - *(tid->node) = (*(tid->node))->next; - pthread_mutex_unlock(tid->start_mutex); - -/* TODO: adjust for longer (arbitrarily long?) starting sequences */ - void *data = tid->solver->alloc_cubedata(tid->solver->param); - tid->solver->copy_cubedata( - tid->solver->param, tid->arg->cubedata, data); - bool inv = node->alg->inv[node->alg->len-1]; - if (inv) - tid->solver->invert_cube( - tid->solver->param, data); - tid->solver->apply_move( - tid->solver->param, data, node->alg->move[0]); - - DfsArg newarg; - newarg.cubedata = data; - newarg.threaddata = tid->arg->threaddata; - newarg.opts = tid->arg->opts; - newarg.d = tid->arg->d; - newarg.niss = inv; - newarg.current_alg = new_alg(""); - copy_alg(node->alg, newarg.current_alg); - - dfs(&newarg, tid->solver, tid->threader); - - tid->solver->free_cubedata(tid->solver->param, data); - free_alg(newarg.current_alg); - } - - return NULL; -} - -static void -dispatch(DfsArg *arg, AlgList *sols, Solver *solver, Threader *threader) -{ - int nthreads = arg->opts->nthreads; - ThreadInitData tid[nthreads]; - pthread_t t[nthreads]; - - pthread_mutex_t *sols_mutex = malloc(sizeof(pthread_mutex_t)); - pthread_mutex_init(sols_mutex, NULL); - - arg->threaddata = malloc(sizeof(ThreadData)); - ThreadData *td = (ThreadData *)arg->threaddata; - td->sols = sols; - td->sols_mutex = sols_mutex; - - AlgList *starts = possible_starts(arg, solver); - AlgListNode *node = starts->first; - pthread_mutex_t *start_mutex = malloc(sizeof(pthread_mutex_t)); - pthread_mutex_init(start_mutex, NULL); - for (int i = 0; i < nthreads; i++) { - tid[i].arg = arg; - tid[i].solver = solver; - tid[i].threader = threader; - tid[i].starts = starts; - tid[i].node = &node; - tid[i].start_mutex = start_mutex; - - pthread_create(&t[i], NULL, instance_thread, &tid[i]); - } - - for (int i = 0; i < nthreads; i++) - pthread_join(t[i], NULL); - - free(td); - free(sols_mutex); - free_alglist(starts); - free(start_mutex); -} - -static int -get_nsol(void *threaddata) -{ - ThreadData *td = (ThreadData *)threaddata; - - pthread_mutex_lock(td->sols_mutex); - int n = td->sols->len; - pthread_mutex_unlock(td->sols_mutex); - - return n; -} diff --git a/src/threader_eager.h b/src/threader_eager.h @@ -1,8 +0,0 @@ -#ifndef THREADER_EAGER_H -#define THREADER_EAGER_H - -#include "solve.h" - -extern Threader threader_eager; - -#endif diff --git a/src/threader_single.c b/src/threader_single.c @@ -1,35 +0,0 @@ -#include "threader_single.h" - -static void append_sol(Alg *, void *); -static void dispatch(DfsArg *, AlgList *, Solver *, Threader *); -static int get_nsol(void *); - -Threader threader_single = { - .append_sol = append_sol, - .dispatch = dispatch, - .get_nsol = get_nsol, -}; - -static void -append_sol(Alg *alg, void *threaddata) -{ - append_alg((AlgList *)threaddata, alg); -} - -static void -dispatch(DfsArg *arg, AlgList *sols, Solver *solver, Threader *threader) -{ - arg->threaddata = sols; - arg->niss = false; - arg->current_alg = new_alg(""); - - dfs(arg, solver, threader); - - free_alg(arg->current_alg); -} - -static int -get_nsol(void *threaddata) -{ - return ((AlgList *)threaddata)->len; -} diff --git a/src/threader_single.h b/src/threader_single.h @@ -1,8 +0,0 @@ -#ifndef THREADER_SINGLE_H -#define THREADER_SINGLE_H - -#include "solve.h" - -extern Threader threader_single; - -#endif diff --git a/src/trans.c b/src/trans.c @@ -1,190 +0,0 @@ -#define TRANS_C - -#include "trans.h" - -/* Local functions ***********************************************************/ - -/* Tables and other data *****************************************************/ - -static Cube mirror_cube = { -.ep = { [UF] = UF, [UL] = UR, [UB] = UB, [UR] = UL, - [DF] = DF, [DL] = DR, [DB] = DB, [DR] = DL, - [FR] = FL, [FL] = FR, [BL] = BR, [BR] = BL }, -.cp = { [UFR] = UFL, [UFL] = UFR, [UBL] = UBR, [UBR] = UBL, - [DFR] = DFL, [DFL] = DFR, [DBL] = DBR, [DBR] = DBL }, -.xp = { [U_center] = U_center, [D_center] = D_center, - [R_center] = L_center, [L_center] = R_center, - [F_center] = F_center, [B_center] = B_center } -}; - -static char rotation_alg_string[100][NROTATIONS] = { - [uf] = "", [ur] = "y", [ub] = "y2", [ul] = "y3", - [df] = "z2", [dr] = "y z2", [db] = "x2", [dl] = "y3 z2", - [rf] = "z3", [rd] = "z3 y", [rb] = "z3 y2", [ru] = "z3 y3", - [lf] = "z", [ld] = "z y3", [lb] = "z y2", [lu] = "z y", - [fu] = "x y2", [fr] = "x y", [fd] = "x", [fl] = "x y3", - [bu] = "x3", [br] = "x3 y", [bd] = "x3 y2", [bl] = "x3 y3", -}; - -Alg *rotation_alg_arr[NROTATIONS]; -Move moves_ttable[NTRANS][NMOVES]; -Trans trans_ttable[NTRANS][NTRANS]; -Trans trans_itable[NTRANS]; - -/* Public functions **********************************************************/ - -void -apply_trans(Trans t, Cube *cube) -{ - Cube aux; - Alg *inv; - int i; - - inv = inverse_alg(rotation_alg(t % NROTATIONS)); - copy_cube(cube, &aux); - make_solved(cube); - - if (t >= NROTATIONS) - compose(&mirror_cube, cube); - apply_alg(inv, cube); - compose(&aux, cube); - apply_alg(rotation_alg(t % NROTATIONS), cube); - if (t >= NROTATIONS) { - compose(&mirror_cube, cube); - for (i = 0; i < 8; i++) - cube->co[i] = (3 - cube->co[i]) % 3; - } - - free_alg(inv); -} - -/* -Trans -inverse_trans(Trans t) -{ - static Trans inverse_trans_aux[NTRANS] = { - [uf] = uf, [ur] = ul, [ul] = ur, [ub] = ub, - [df] = df, [dr] = dr, [dl] = dl, [db] = db, - [rf] = lf, [rd] = bl, [rb] = rb, [ru] = fr, - [lf] = rf, [ld] = br, [lb] = lb, [lu] = fl, - [fu] = fu, [fr] = ru, [fd] = bu, [fl] = lu, - [bu] = fd, [br] = ld, [bd] = bd, [bl] = rd, - - [uf_mirror] = uf_mirror, [ur_mirror] = ur_mirror, - [ul_mirror] = ul_mirror, [ub_mirror] = ub_mirror, - [df_mirror] = df_mirror, [dr_mirror] = dl_mirror, - [dl_mirror] = dr_mirror, [db_mirror] = db_mirror, - [rf_mirror] = rf_mirror, [rd_mirror] = br_mirror, - [rb_mirror] = lb_mirror, [ru_mirror] = fl_mirror, - [lf_mirror] = lf_mirror, [ld_mirror] = bl_mirror, - [lb_mirror] = rb_mirror, [lu_mirror] = fr_mirror, - [fu_mirror] = fu_mirror, [fr_mirror] = lu_mirror, - [fd_mirror] = bu_mirror, [fl_mirror] = ru_mirror, - [bu_mirror] = fd_mirror, [br_mirror] = rd_mirror, - [bd_mirror] = bd_mirror, [bl_mirror] = ld_mirror - }; - - return inverse_trans_aux[t]; -} -*/ - -Trans -inverse_trans(Trans t) -{ - return trans_itable[t]; -} - -Alg * -rotation_alg(Trans i) -{ - return rotation_alg_arr[i % NROTATIONS]; -} - -void -transform_alg(Trans t, Alg *alg) -{ - int i; - - for (i = 0; i < alg->len; i++) - alg->move[i] = transform_move(t, alg->move[i]); -} - -Move -transform_move(Trans t, Move m) -{ - return moves_ttable[t][m]; -} - -Trans -transform_trans(Trans t, Trans m) -{ - return trans_ttable[t][m]; -} - -void -init_trans() { - static bool initialized = false; - if (initialized) - return; - initialized = true; - - int i; - Alg *nonsym_alg, *nonsym_inv; - Cube aux, cube; - Move mi, move; - Trans t, u, v; - - init_moves(); - - for (i = 0; i < NROTATIONS; i++) - rotation_alg_arr[i] = new_alg(rotation_alg_string[i]); - - for (t = 0; t < NTRANS; t++) { - for (mi = 0; mi < NMOVES; mi++) { - make_solved(&aux); - apply_move(mi, &aux); - apply_trans(t, &aux); - for (move = 0; move < NMOVES; move++) { - copy_cube(&aux, &cube); - apply_move(inverse_move(move), &cube); - if (is_solved(&cube)) { - moves_ttable[t][mi] = move; - break; - } - } - } - } - - nonsym_alg = new_alg("R' U' F"); - nonsym_inv = inverse_alg(nonsym_alg); - - for (t = 0; t < NTRANS; t++) { - for (u = 0; u < NTRANS; u++) { - make_solved(&aux); - apply_alg(nonsym_alg, &aux); - apply_trans(u, &aux); - apply_trans(t, &aux); - for (v = 0; v < NTRANS; v++) { - copy_cube(&aux, &cube); - apply_trans(v, &cube); - apply_alg(nonsym_inv, &cube); - if (is_solved(&cube)) { - /* This is the inverse of the correct - value, it will be inverted later */ - trans_ttable[t][u] = v; - if (v == uf) - trans_itable[t] = u; - break; - } - } - } - } - for (t = 0; t < NTRANS; t++) - for (u = 0; u < NTRANS; u++) - trans_ttable[t][u] = trans_itable[trans_ttable[t][u]]; - - - free_alg(nonsym_alg); - free_alg(nonsym_inv); -} - diff --git a/src/trans.h b/src/trans.h @@ -1,32 +0,0 @@ -#ifndef TRANS_H -#define TRANS_H - -#include "moves.h" - -void apply_trans(Trans t, Cube *cube); -Trans inverse_trans(Trans t); -Alg * rotation_alg(Trans i); -void transform_alg(Trans t, Alg *alg); -Move transform_move(Trans t, Move m); -Trans transform_trans(Trans t, Trans m); - -void init_trans(); - -#ifndef TRANS_C - -extern TransGroup tgrp_udfix; - -#else - -TransGroup -tgrp_udfix = { - .n = 16, - .t = { uf, ur, ub, ul, - df, dr, db, dl, - uf_mirror, ur_mirror, ub_mirror, ul_mirror, - df_mirror, dr_mirror, db_mirror, dl_mirror }, -}; - -#endif - -#endif diff --git a/src/utils.c b/src/utils.c @@ -1,290 +0,0 @@ -#define UTILS_C - -#include "utils.h" - -void -apply_permutation(int *perm, int *set, int n) -{ - int *aux = malloc(n * sizeof(int)); - int i; - - if (!is_perm(perm, n)) - return; - - for (i = 0; i < n; i++) - aux[i] = set[perm[i]]; - - memcpy(set, aux, n * sizeof(int)); - free(aux); -} - -int -binomial(int n, int k) -{ - if (n < 0 || k < 0 || k > n) - return 0; - - return factorial(n) / (factorial(k) * factorial(n-k)); -} - -int -digit_array_to_int(int *a, int n, int b) -{ - int i, ret = 0, p = 1; - - for (i = 0; i < n; i++, p *= b) - ret += a[i] * p; - - return ret; -} - -int -factorial(int n) -{ - int i, ret = 1; - - if (n < 0) - return 0; - - for (i = 1; i <= n; i++) - ret *= i; - - return ret; -} - -void -index_to_perm(int p, int n, int *r) -{ - int *a = malloc(n * sizeof(int)); - int i, j, c; - - for (i = 0; i < n; i++) - a[i] = 0; - - if (p < 0 || p >= factorial(n)) - for (i = 0; i < n; i++) - r[i] = -1; - - for (i = 0; i < n; i++) { - c = 0; - j = 0; - while (c <= p / factorial(n-i-1)) - c += a[j++] ? 0 : 1; - r[i] = j-1; - a[j-1] = 1; - p %= factorial(n-i-1); - } - - free(a); -} - -void -index_to_subset(int s, int n, int k, int *r) -{ - int i, j, v; - - if (s < 0 || s >= binomial(n, k)) { - for (i = 0; i < n; i++) - r[i] = -1; - return; - } - - for (i = 0; i < n; i++) { - if (k == n-i) { - for (j = i; j < n; j++) - r[j] = 1; - return; - } - - if (k == 0) { - for (j = i; j < n; j++) - r[j] = 0; - return; - } - - v = binomial(n-i-1, k); - if (s >= v) { - r[i] = 1; - k--; - s -= v; - } else { - r[i] = 0; - } - } -} - -void -int_to_digit_array(int a, int b, int n, int *r) -{ - int i; - - if (b <= 1) - for (i = 0; i < n; i++) - r[i] = 0; - else - for (i = 0; i < n; i++, a /= b) - r[i] = a % b; -} - -void -int_to_sum_zero_array(int x, int b, int n, int *a) -{ - int i, s = 0; - - if (b <= 1) { - for (i = 0; i < n; i++) - a[i] = 0; - } else { - int_to_digit_array(x, b, n-1, a); - for (i = 0; i < n - 1; i++) - s = (s + a[i]) % b; - a[n-1] = (b - s) % b; - } -} - -int -invert_digits(int a, int b, int n) -{ - int i, ret, *r = malloc(n * sizeof(int)); - - int_to_digit_array(a, b, n, r); - for (i = 0; i < n; i++) - r[i] = (b-r[i]) % b; - - ret = digit_array_to_int(r, n, b); - free(r); - return ret; -} - -bool -is_perm(int *a, int n) -{ - int *aux = malloc(n * sizeof(int)); - int i; - bool ret = true; - - for (i = 0; i < n; i++) - aux[i] = 0; - - for (i = 0; i < n; i++) { - if (a[i] < 0 || a[i] >= n) - ret = false; - else - aux[a[i]] = 1; - } - - for (i = 0; i < n; i++) - if (!aux[i]) - ret = false; - - free(aux); - return ret; -} - -bool -is_subset(int *a, int n, int k) -{ - int i, sum = 0; - - for (i = 0; i < n; i++) - sum += a[i] ? 1 : 0; - - return sum == k; -} - -int -perm_sign(int *a, int n) -{ - int i, j, ret = 0; - - if (!is_perm(a, n)) - return -1; - - for (i = 0; i < n; i++) - for (j = i+1; j < n; j++) - ret += (a[i] > a[j]) ? 1 : 0; - - return ret % 2; -} - -int -perm_to_index(int *a, int n) -{ - int i, j, c, ret = 0; - - if (!is_perm(a, n)) - return factorial(n); - - for (i = 0; i < n; i++) { - c = 0; - for (j = i+1; j < n; j++) - c += (a[i] > a[j]) ? 1 : 0; - ret += factorial(n-i-1) * c; - } - - return ret; -} - -int -powint(int a, int b) -{ - if (b < 0) - return 0; - if (b == 0) - return 1; - - if (b % 2) - return a * powint(a, b-1); - else - return powint(a*a, b/2); -} - -int -subset_to_index(int *a, int n, int k) -{ - int i, ret = 0; - - if (!is_subset(a, n, k)) - return binomial(n, k); - - for (i = 0; i < n; i++) { - if (k == n-i) - return ret; - if (a[i]) { - ret += binomial(n-i-1, k); - k--; - } - } - - return ret; -} - -void -sum_arrays_mod(int *src, int *dst, int n, int m) -{ - int i; - - for (i = 0; i < n; i++) - dst[i] = (m <= 0) ? 0 : (src[i] + dst[i]) % m; -} - -void -swap(int *a, int *b) -{ - int aux; - - aux = *a; - *a = *b; - *b = aux; -} - -void -swapu64(uint64_t *a, uint64_t *b) -{ - uint64_t aux; - - aux = *a; - *a = *b; - *b = aux; -} - diff --git a/src/utils.h b/src/utils.h @@ -1,43 +0,0 @@ -#ifndef UTILS_H -#define UTILS_H - -#include <stdbool.h> -#include <stdint.h> -#include <stdlib.h> -#include <string.h> - -#define POW2TO6 64ULL -#define POW2TO11 2048ULL -#define POW2TO12 4096ULL -#define POW3TO7 2187ULL -#define POW3TO8 6561ULL -#define FACTORIAL4 24ULL -#define FACTORIAL6 720ULL -#define FACTORIAL7 5040ULL -#define FACTORIAL8 40320ULL -#define FACTORIAL12 479001600ULL -#define BINOM12ON4 495ULL -#define BINOM8ON4 70ULL -#define MIN(a,b) (((a) < (b)) ? (a) : (b)) -#define MAX(a,b) (((a) > (b)) ? (a) : (b)) - -void apply_permutation(int *perm, int *set, int n); -int binomial(int n, int k); -int digit_array_to_int(int *a, int n, int b); -int factorial(int n); -void index_to_perm(int p, int n, int *r); -void index_to_subset(int s, int n, int k, int *r); -void int_to_digit_array(int a, int b, int n, int *r); -void int_to_sum_zero_array(int x, int b, int n, int *a); -int invert_digits(int a, int b, int n); -bool is_perm(int *a, int n); -bool is_subset(int *a, int n, int k); -int perm_sign(int *a, int n); -int perm_to_index(int *a, int n); -int powint(int a, int b); -int subset_to_index(int *a, int n, int k); -void sum_arrays_mod(int *src, int *dst, int n, int m); -void swap(int *a, int *b); -void swapu64(uint64_t *a, uint64_t *b); - -#endif diff --git a/tests/alg_tests.c b/tests/alg_tests.c @@ -1,266 +0,0 @@ -#include "alg_tests.h" - -bool testmethod_append_move(void *); -bool testmethod_new_alg(void *); -/* -bool testmethod_compose_alg(void *); -bool testmethod_inverse_alg(void *); -bool testmethod_on_inverse(void *); -bool testmethod_unniss(void *); -*/ - -typedef struct { - Move *move; - bool *inv; - int len; - Move m; - bool inverse; -} append_move_t; - -Move m_app1[] = {F, x, D3}; -bool i_app1[] = {true, false, false}; -append_move_t append_move_case1 = { - .move = m_app1, - .inv = i_app1, - .len = 3, - .m = L3, - .inverse = false, -}; - -Move m_app2[] = {S, U, x2, M2}; -bool i_app2[] = {true, false, true, true}; -append_move_t append_move_case2 = { - .move = m_app2, - .inv = i_app2, - .len = 4, - .m = R, - .inverse = true, -}; - -Move m_app3[] = {U, U, U, U, U}; -bool i_app3[] = {false, false, false, false, false}; -append_move_t append_move_case3 = { - .move = m_app3, - .inv = i_app3, - .len = 5, - .m = U, - .inverse = false, -}; - -append_move_t *append_move_cases[] = { - &append_move_case1, - &append_move_case2, - &append_move_case3, -}; - -Test test_append_move = { - .name = "Appending a move to and alg", - .t = testmethod_append_move, - .cases = (void **)append_move_cases, -}; - -typedef struct { - char *str; - Move *move; - bool *inv; - int len; - Move *move_normal; - int len_normal; - Move *move_inverse; - int len_inverse; -} new_alg_t; - -/* Alg F U B' (L3 D) x M (S) y3 */ -Move m_new1[] = {F, U, B3, L3, D, x, M, S, y3}; -Move mn_new1[] = {F, U, B3, x, M, y3}; -Move mi_new1[] = {L3, D, S}; -bool i_new1[] = {false, false, false, true, true, false, false, true, false}; -new_alg_t new_alg_case1 = { - .str = "F U B' (L3 D) x M (S) y3", - .move = m_new1, - .inv = i_new1, - .len = 9, - .move_normal = mn_new1, - .len_normal = 6, - .move_inverse = mi_new1, - .len_inverse = 3, -}; -new_alg_t *new_alg_cases[] = {&new_alg_case1}; - -Test test_new_alg = { - .name = "Initializing an alg from a string", - .t = testmethod_new_alg, - .cases = (void **)new_alg_cases, -}; - -Test *alg_all_tests[] = { - &test_append_move, - &test_new_alg, -/* - &test_append_alg, - &test_compose_alg, - &test_inverse_alg, - &test_on_inverse, - &test_unniss, -*/ - NULL -}; -TestSuite alg_suite = { - .setup = NULL, - .tests = alg_all_tests, - .teardown = NULL, -}; - -TestSuite *alg_suites[] = { - &alg_suite, - NULL -}; - -bool -testmethod_append_move(void *a) -{ - append_move_t *b = (append_move_t *)a; - int li, ln; - Alg *alg; - - /* Small to test reallocation */ - alg = malloc(sizeof(Alg)); - alg->allocated = 5; - alg->move = malloc(alg->allocated * sizeof(Move)); - alg->inv = malloc(alg->allocated * sizeof(bool)); - alg->len = b->len; - memcpy(alg->move, b->move, alg->len * sizeof(Move)); - memcpy(alg->inv, b->inv, alg->len * sizeof(bool)); - alg->move_normal = malloc(alg->allocated * sizeof(Move)); - alg->move_inverse = malloc(alg->allocated * sizeof(Move)); - - li = ln = 0; - for (int i = 0; i < alg->len; i++) { - if (alg->inv[i]) - alg->move_inverse[li++] = alg->move[i]; - else - alg->move_normal[ln++] = alg->move[i]; - } - alg->len_inverse = li; - alg->len_normal = ln; - - append_move(alg, b->m, b->inverse); - - if (alg->len != b->len + 1) { - printf("Alg has wrong len (%d instead of %d)\n", - alg->len, b->len + 1); - goto append_move_fail; - } - if (alg->move[alg->len-1] != b->m) { - printf("Wrong last move (%s instead of %s)\n", - move_string(alg->move[alg->len-1]), - move_string(b->m)); - goto append_move_fail; - } - if (alg->inv[alg->len-1] != b->inverse) { - printf("Wrong inverse flag for last move " - "(%s instead of %s)\n", - b->inverse ? "normal" : "inverse", - b->inverse ? "inverse" : "normal"); - goto append_move_fail; - } - if (b->inverse) { - if (alg->len_inverse != li + 1 || - alg->len_normal != ln) { - printf("%d moves on normal (should be %d)" - " and %d on inverse (should be %d)\n", - alg->len_normal, ln, - alg->len_inverse, li + 1); - goto append_move_fail; - } - if (alg->move_inverse[alg->len_inverse-1] != b->m) { - printf("Wrong move on inverse (%s instead of %s)\n", - move_string(alg->move_inverse[alg->len-1]), - move_string(b->m)); - goto append_move_fail; - } - } else { - if (alg->len_inverse != li || - alg->len_normal != ln + 1) { - printf("%d moves on normal (should be %d)" - " and %d on inverse (should be %d)\n", - alg->len_normal, ln, - alg->len_inverse, li + 1); - goto append_move_fail; - } - if (alg->move_normal[alg->len_normal-1] != b->m) { - printf("Wrong move on normal (%s instead of %s)\n", - move_string(alg->move_normal[alg->len-1]), - move_string(b->m)); - goto append_move_fail; - } - } - - free(alg); - return true; - -append_move_fail: - free(alg); - return false; -} - -bool -testmethod_new_alg(void *a) -{ - new_alg_t *b = (new_alg_t *)a; - Alg *alg = new_alg(b->str); - - if (alg->len != b->len) { - printf("Algs have different length (%d instead of %d)\n", - alg->len, b->len); - goto new_alg_fail; - } - - for (int i = 0; i < alg->len; i++) { - if (alg->move[i] != b->move[i] || alg->inv[i] != b->inv[i]) { - printf("Algs differ on move %d\n", i); - printf("Expected: %s\nActual: ", b->str); - print_alg(alg, false); - goto new_alg_fail; - } - } - - if (alg->len_normal != b->len_normal) { - printf("Algs have different number of moves on normal" - " (%d instead of %d)\n", - alg->len_normal, b->len_normal); - goto new_alg_fail; - } - for (int i = 0; i < alg->len_normal; i++) { - if (alg->move_normal[i] != b->move_normal[i]) { - printf("Algs have different move %d on normal" - " (%s instead of %s)\n", i, - move_string(alg->move_normal[i]), - move_string(b->move_normal[i])); - goto new_alg_fail; - } - } - - if (alg->len_inverse != b->len_inverse) { - printf("Algs have different number of moves on inverse" - " (%d instead of %d)\n", - alg->len_inverse, b->len_inverse); - goto new_alg_fail; - } - for (int i = 0; i < alg->len_inverse; i++) { - if (alg->move_inverse[i] != b->move_inverse[i]) { - printf("Algs have different move %d on inverse:\n" - " (%s instead of %s)\n", i, - move_string(alg->move_inverse[i]), - move_string(b->move_inverse[i])); - goto new_alg_fail; - } - } - - free(alg); - return true; - -new_alg_fail: - free(alg); - return false; -} diff --git a/tests/alg_tests.h b/tests/alg_tests.h @@ -1,21 +0,0 @@ -#ifndef ALG_TESTS_H -#define ALG_TESTS_H - -#include "../src/alg.h" -#include "test_common.h" - -extern Test test_append_move; -extern Test test_new_alg; -/* -extern Test remove_last_move; -extern Test test_compose_alg; -extern Test test_inverse_alg; -extern Test test_on_inverse; -extern Test test_unniss; -*/ - -extern TestSuite alg_suite; - -extern TestSuite *alg_suites[]; - -#endif diff --git a/tests/coord_tests.c b/tests/coord_tests.c @@ -1,50 +0,0 @@ -#include "coord_tests.h" - -bool testmethod_indexes_consistent(void *); - -Test test_indexes_consistent = { - .name = "Consitency of index and anti-index", - .t = testmethod_indexes_consistent, - .cases = (void **)all_coordinates, -}; -Test *coord_pre_init[] = { - &test_indexes_consistent, - NULL -}; -TestSuite coord_pre_init_suite = { - .setup = NULL, - .tests = coord_pre_init, - .teardown = NULL, -}; - -TestSuite *coord_suites[] = { - &coord_pre_init_suite, - NULL -}; - -bool -testmethod_indexes_consistent(void *a) -{ - uint64_t ui, uj; - Cube c; - Coordinate *coord; - - coord = (Coordinate *)a; - - if (coord->type != COMP_COORD) - return true; /* Not applicable */ - - gen_coord(coord); - for (ui = 0; ui < coord->max; ui++) { - indexers_makecube(coord->i, ui, &c); - uj = indexers_getind(coord->i, &c); - if (ui != uj) { - fprintf(stderr, "Error with coordinate %s: " - "%" PRIu64 " != %" PRIu64 "\n", - coord->name, uj, ui); - return false; - } - } - - return true; -} diff --git a/tests/coord_tests.h b/tests/coord_tests.h @@ -1,13 +0,0 @@ -#ifndef COORD_TESTS_H -#define COORD_TESTS_H - -#include "../src/coord.h" -#include "test_common.h" - -extern Test test_indexes_consistent; - -extern TestSuite coord_pre_init_suite; - -extern TestSuite *coord_suites[]; - -#endif diff --git a/tests/fst_tests.c b/tests/fst_tests.c @@ -1,184 +0,0 @@ -#include "fst_tests.h" - -static bool testmethod_fst_is_consistent(void *); -static bool testmethod_cube_to_fst_to_cube(void *); -static bool testmethod_fst_move(void *); -static bool testmethod_fst_inverse(void *); -static bool check_equal_and_log(Cube *, Cube *); -static void void_to_cube(void *, Cube *); - -char *algs[] = { - "", - "U", "U2", "U'", "D", "D2", "D'", "R", "R2", "R'", - "L", "L2", "L'", "F", "F2", "F'", "B", "B2", "B'", - "U2 R2 U2 R2 U2", - "U2 F2 R2 B2 U2 D2 F2 L2 B2", - "RUR'URU2R'", - "L2 D R U2 B2 L", - "R'U'F", - "F2 U' R2 D' B2 D2 R2 D2 R2 U' F L' U' R B F2 R B' D2", - "D L2 F2 R2 D R2 U L2 U' B2 D L' F2 U2 B' L D' U' R' B2 F2", - "F' L2 F' D' R F2 L U L' D2 R2 F2 D2 R2 B' L2 B2 U2 F D2 B", - NULL, -}; - -Test test_fst_is_consistent = { - .name = "Consitency of FST (converted from cube)", - .t = testmethod_fst_is_consistent, - .cases = (void **)algs, -}; -Test test_cube_to_fst_to_cube = { - .name = "Cube to FST to cube", - .t = testmethod_cube_to_fst_to_cube, - .cases = (void **)algs, -}; -Test test_fst_move = { - .name = "FST move", - .t = testmethod_fst_move, - .cases = (void **)algs, -}; -Test test_fst_inverse = { - .name = "FST inverse", - .t = testmethod_fst_inverse, - .cases = (void **)algs, -}; - -Test *fst_pre_init[] = { - &test_fst_is_consistent, - &test_cube_to_fst_to_cube, - NULL -}; -TestSuite fst_pre_init_suite = { - .setup = NULL, - .tests = fst_pre_init, - .teardown = NULL, -}; - -Test *fst_post_init[] = { - &test_fst_move, - &test_fst_inverse, - NULL -}; -TestSuite fst_post_init_suite = { - .setup = init_fst, - .tests = fst_post_init, - .teardown = NULL, -}; - -TestSuite *fst_suites[] = { - &fst_pre_init_suite, - &fst_post_init_suite, - NULL -}; - -static bool -check_equal_and_log(Cube *c, Cube *d) -{ - bool ret = equal(c, d); - - if (!ret) { - printf("\n"); - printf("These cubes should be equal, but are not:\n\n"); - print_cube(c); - printf("\n"); - print_cube(d); - printf("\n"); - } - - return ret; -} - -static void -void_to_cube(void *a, Cube *c) -{ - char *algstr; - Alg *alg; - - algstr = (char *)a; - alg = new_alg(algstr); - make_solved(c); - apply_alg(alg, c); - free_alg(alg); -} - -bool -testmethod_fst_is_consistent(void *a) -{ - FstCube fst_uf, fst_fr, fst_rd; - Cube c, c_fr, c_rd; - bool consistent_fr, consistent_rd, result; - - void_to_cube(a, &c); - copy_cube(&c, &c_fr); - apply_trans(fr, &c_fr); - - copy_cube(&c, &c_rd); - apply_trans(rd, &c_rd); - - fst_uf = cube_to_fst(&c); - fst_fr = cube_to_fst(&c_fr); - fst_rd = cube_to_fst(&c_rd); - - consistent_fr = fst_uf.fr_eofb == fst_fr.uf_eofb && - fst_uf.fr_eposepe == fst_fr.uf_eposepe && - fst_uf.fr_coud == fst_fr.uf_coud; - - consistent_rd = fst_uf.rd_eofb == fst_rd.uf_eofb && - fst_uf.rd_eposepe == fst_rd.uf_eposepe && - fst_uf.rd_coud == fst_rd.uf_coud; - - result = consistent_fr && consistent_rd; - - if (!result) - printf("\nFailed with alg %s\n", (char *)a); - - return result; -} - -bool -testmethod_cube_to_fst_to_cube(void *a) -{ - Cube c, d; - FstCube fst; - - void_to_cube(a, &c); - fst = cube_to_fst(&c); - fst_to_cube(fst, &d); - - return check_equal_and_log(&c, &d);; -} - -bool -testmethod_fst_move(void *a) -{ - int i; - Alg *alg; - Cube c, d; - FstCube fst; - - void_to_cube(a, &c); - alg = new_alg((char *)a); - make_solved(&d); - fst = cube_to_fst(&d); - - for (i = 0; i < alg->len; i++) - fst = fst_move(alg->move[i], fst); - - fst_to_cube(fst, &d); - - free_alg(alg); - - return check_equal_and_log(&c, &d); -} - -bool -testmethod_fst_inverse(void *a) -{ - Cube c, d; - - void_to_cube(a, &c); - fst_to_cube(fst_inverse(cube_to_fst(&c)), &d); - invert_cube(&c); - - return check_equal_and_log(&c, &d); -} diff --git a/tests/fst_tests.h b/tests/fst_tests.h @@ -1,19 +0,0 @@ -#ifndef FST_TESTS_H -#define FST_TESTS_H - -#include "../src/fst.h" -#include "test_common.h" - -extern char *algs[]; - -extern Test test_fst_is_consistent; -extern Test test_cube_to_fst_to_cube; -extern Test test_fst_move; -extern Test test_fst_inverse; - -extern TestSuite fst_pre_init_suite; -extern TestSuite fst_post_init_suite; - -extern TestSuite *fst_suites[]; - -#endif diff --git a/tests/test.c b/tests/test.c @@ -1,85 +0,0 @@ -#include <stdio.h> - -#include "alg_tests.h" -#include "coord_tests.h" -#include "fst_tests.h" - -static bool run_test(Test *); -static bool run_suite(TestSuite *); - -static bool -run_test(Test *test) -{ - int i; - - printf("Running test %s...", test->name); - for (i = 0; test->cases[i] != NULL; i++) { - if (!test->t(test->cases[i])) { - printf("FAILED!\n"); - return false; - } - } - - printf("OK\n"); - return true; -} - -static bool -run_suite(TestSuite *suite) -{ - int i; - - if (suite->setup != NULL) - suite->setup(); - for (i = 0; suite->tests[i] != NULL; i++) - if(!run_test(suite->tests[i])) - return false; - if (suite->teardown != NULL) - suite->teardown(); - - return true; -} - -static bool -module_in_args(char *module, int argc, char *argv[]) -{ - for (int i = 0; i < argc; i++) - if (!strcmp(module, argv[i])) - return true; - return false; -} - -int main(int argc, char *argv[]) { - /* TODO: init should be in testsuites */ - init_env(); - init_trans(); - /**************************************/ - - TestModule alg = { .name = "alg", .suites = alg_suites }; - TestModule fst = { .name = "fst", .suites = fst_suites }; - TestModule coord = { .name = "coord", .suites = coord_suites }; - TestModule *modules[999] = { - &alg, - &fst, - &coord, - NULL - }; - - - bool all = argc == 1 || module_in_args("all", argc, argv); - int count = 0; - for (int i = 0; modules[i] != NULL; i++) { - if (all || module_in_args(modules[i]->name, argc, argv)) { - for (int j = 0; modules[i]->suites[j] != NULL; j++) { - if (!run_suite(modules[i]->suites[j])) { - return 1; - } else { - count++; - } - } - } - } - - printf("All tests passed (%d test suites).\n", count); - return 0; -} diff --git a/tests/test_common.h b/tests/test_common.h @@ -1,41 +0,0 @@ -#ifndef TEST_COMMON_H -#define TEST_COMMON_H - -/* - * Common utilities for testing. - * A VoidMethod can be used as a setup or teardown method for testing, see - * the TestSuite struct. A TestMethod takes a void pointer (usually cast - * to some data to be used for testing, but can also be ignored) and returns - * a bool: true for pass, false for fail. - * A Test consists of a name (string), a TestMethod and an array of void - * pointers that describe the test cases. Each element of this array is - * passed to the test method sequentially, and the test session stops on - * the first failure. - * A test suite is just a list of tests with a setup and a teardown method. - * The setup method is run once and for all before the first test, and the - * teardown is run at the end of the testsuite. - * Finally, a TestModule roughly corresponds to a test file. This type is - * only used in test.c to collect multiple test modules. - */ - -typedef void (*VoidMethod)(void); -typedef bool (*TestMethod)(void *); - -typedef struct { - char * name; - TestMethod t; - void ** cases; -} Test; - -typedef struct { - VoidMethod setup; - Test ** tests; - VoidMethod teardown; -} TestSuite; - -typedef struct { - char * name; - TestSuite ** suites; -} TestModule; - -#endif diff --git a/www/download/index.html b/www/download/index.html @@ -1,217 +0,0 @@ -<!doctype html> -<html lang="en"> -<head> - <title> Download | Nissy </title> -<meta name="viewport" content="width=device-width" /> <link rel="stylesheet" type="text/css" href="/style-3.css"> - <link rel="icon" href="/favicon.png"> - <meta charset="utf-8"> -</head> - -<body> - -<nav class="top"> - <table class="menu"> - <tr> - <td class="logo"> <a href="/"><img src="/favicon.png" alt="logo"></a> </td> - <td class="links"> - <a href="/download/">Download</a> | - <a href="/examples/">Examples</a> - </td> - </tr> - </table> -</nav> - -<hr class="line"> - - -<h1>Get Nissy</h1> - -<table class="dltable"> -<tr> - <td></td> - <td><strong>Source code</strong></td> - <td><strong>Windows executable</strong></td> -</tr> -<tr> - <td><strong>Latest version</strong></td> - <td><a href="/nissy-2.0.3.tar.gz">nissy-2.0.3.tar.gz (67Kb)</a></td> - <td><a href="/nissy-2.0.3.exe">nissy-2.0.3.exe (780Kb)</a></td> -</tr> -</table> - -<p> -In this page you can find download links (see above), -<a href="#Installation">installation instructions</a> and -<a href="#Upgrade">upgrade instructions</a> -for nissy. If instead you wish to clone the -<a href="https://git.tronto.net/nissy/">git repository</a>, -you can use git: -</p> - -<pre> -<code>git clone https://git.tronto.net/nissy</code> -</pre> - -<p> -For a summary of changes and a list of older versions see below. Some versions -(for example 1.0) are not available directly, but can be obtained from -the git repository. -</p> - -<h2 id="Installation">Installation</h2> - -<h3>System requirements</h3> - -<p> -A full installation of nissy requires about 3.1Gb of space, -of which 2.3Gb are occupied by the huge pruning table for fast optimal solving, -and running it requires the same amount of RAM. -One can choose to never use this function and not to install the relative -pruning table. There is an alternative (slower) -optimal solving function that uses about 500Mb of RAM. - -When generating the pruning tables automatically (see the section Tables below), -at least 5.3Gb or RAM are required. -</p> - -<h3>Windows</h3> - -<p> -Try downloading and executing in a terminal the file <code>nissy.exe</code>, -then follow the instructions in the <strong>Tables</strong> section below for -installing the pruning tables. -If <code>nissy.exe</code> does not work, you can try following the UNIX instructions -in WSL (Windows Subsystem for Linux) or in a similar environment. -</p> - -<h3>UNIX (Linux, MacOS, *BSD...)</h3> -<p> -Download the source archive (.tar.gz). Extract it -with your favorite archive program, for example with -</p> -<pre><code>tar -xvzf nissy-VERSION.tar.gz</code></pre> -<p> -Open a terminal in the directory just extracted. -If you wish, edit the <code>Makefile</code> to match your local configuration -(this is usually not necessary, but you may want to change the -<code>PREFIX</code> variable to change the installation path) and run -<pre><code>make</code></pre> -<p> -followed by -</p> -<pre><code>make install</code></pre> -<p> -Then follow the instructions below to install the pruning tables. -</p> - -<h3>Tables</h3> - -<p> -Once you have installed nissy, run -</p> - -<pre><code>nissy gen</code></pre> - -<p> -to generate all the tables that Nissy will ever need. -Running this command requires around 5.3Gb of RAM, and it can take some time -(about 40 minutes on my fairly old but decent laptop, with 8 CPU threads). -</p> - -<p> -Some unnecessary technical detail: by default this command is going to use -at most 64 threads. If you want you can choose to use more threads (if your CPU -is very powerful) or fewer threads (if you for example want to run this command -in the background while you do other stuff) with the <code>-t</code> option, for -example <code>nissy gen -t 1</code>. -</p> - -<p> -Alternatively, you can -<a href="/nissy-tables-2.0.2.zip">download all the tables (1.7Gb)</a> and -copy them into the correct folder (see manual page, <code>ENVIRONMENT</code> -section). On UNIX operating systems this folder is either -<code>.nissy/tables</code> in the user's home directory or -<code>$XDG_DATA_HOME/nissy/tables</code> if the XDG variable is configured. -On Windows it is the same directory as the <code>nissy.exe</code> executable -file. -</p> - -<h2 id="Upgrade">Upgrading</h2> -<p> -If you already have nissy installed and you want to upgrade to a more -recent version, you can simply repeat the installation process: -</p> -<ul> -<li> -On Windows: simply replace nissy.exe with the new file with the same name. -</li> -<li> -On UNIX systems: download the new version of the source code, extract it in -a new folder and run <code>make</code> and <code>make install</code> again. -</li> -</ul> -<p> -Between each version new table files might have been added, or old ones -may be not used anymore. Nissy will deal with this automatically. -</p> - -<h2>Version history</h2> - -<h3>Nissy v2</h3> - -<table class=dltable> -<tr> - <td><strong>Version</strong></td> - <td><strong>Date</strong></td> - <td><strong>Comment</strong></td> -</tr> -<tr> - <td><a href="/nissy-2.0.3.tar.gz">2.0.3</a></td> - <td>2022-09-10</td> - <td>Fixed bug in scramble dr</td> -</tr> -<tr> - <td><a href="/nissy-2.0.2.tar.gz">2.0.2</a></td> - <td>2022-06-01</td> - <td>Improved table generation speed</td> -</tr> -<tr> - <td><a href="/nissy-2.0.1.tar.gz">2.0.1</a></td> - <td>2022-02-22</td> - <td>Bugfix release</td> -</tr> -<tr> - <td>2.0</td> - <td>2021-12-29</td> - <td>Rewritten from scratch; much faster optimal solver</td> -</tr> -</table> - -<h3>Nissy v1</h3> - -<p> -Nissy v1 was released in 2020. It was slow, full of bugs and the code -was quite terrible. But in practice it got its job done most of the time. -</p> - - -<hr class="line"> - -<nav class="bottom"> - <table class="footer"> - <tr> - <td class="contact"> - <a href="https://sebastiano.tronto.net">sebastiano.tronto.net</a> - </td> - <td class="hosted"> - <a href="mailto:sebastiano@tronto.net"> - sebastiano@tronto.net - </a> - </td> - </tr> - </table> -</nav> - -</body> -</html> diff --git a/www/examples/index.html b/www/examples/index.html @@ -1,49 +0,0 @@ -<!doctype html> -<html lang="en"> -<head> - <title> Examples | Nissy </title> -<meta name="viewport" content="width=device-width" /> <link rel="stylesheet" type="text/css" href="/style-3.css"> - <link rel="icon" href="/favicon.png"> - <meta charset="utf-8"> -</head> - -<body> - -<nav class="top"> - <table class="menu"> - <tr> - <td class="logo"> <a href="/"><img src="/favicon.png" alt="logo"></a> </td> - <td class="links"> - <a href="/download/">Download</a> | - <a href="/examples/">Examples</a> - </td> - </tr> - </table> -</nav> - -<hr class="line"> - - -<h1>Examples</h1> - -(Coming soon...) - -<hr class="line"> - -<nav class="bottom"> - <table class="footer"> - <tr> - <td class="contact"> - <a href="https://sebastiano.tronto.net">sebastiano.tronto.net</a> - </td> - <td class="hosted"> - <a href="mailto:sebastiano@tronto.net"> - sebastiano@tronto.net - </a> - </td> - </tr> - </table> -</nav> - -</body> -</html> diff --git a/www/favicon.png b/www/favicon.png Binary files differ. diff --git a/www/index.html b/www/index.html @@ -1,93 +0,0 @@ -<!doctype html> -<html lang="en"> -<head> - <title> Nissy | Nissy </title> -<meta name="viewport" content="width=device-width" /> <link rel="stylesheet" type="text/css" href="/style-3.css"> - <link rel="icon" href="/favicon.png"> - <meta charset="utf-8"> -</head> - -<body> - -<nav class="top"> - <table class="menu"> - <tr> - <td class="logo"> <a href="/"><img src="/favicon.png" alt="logo"></a> </td> - <td class="links"> - <a href="/download/">Download</a> | - <a href="/examples/">Examples</a> - </td> - </tr> - </table> -</nav> - -<hr class="line"> - - -<h1>Nissy</h1> - -<p class=subtitle>A Rubik's cube solver and FMC assistant</p> - -<img src="/screenshot.png" alt="A screenshot of nissy running in a terminal emulator"> - -<p> -Nissy is a command-line Rubik's cube solver. It can find optimal solutions -for random positions using techniques from Herbert Kociemba's -<a href="http://kociemba.org/cube.htm">Cube Explorer</a> and -Tomas Rokicki's -<a href="https://github.com/rokici/cube20src/blob/master/nxopt.md">nxopt</a>. -With 4 cores at 2.5GHz and using about 3Gb of RAM, Nissy can find an optimal -solution in about a minute on average. -</p> - -<p> -Nissy aims at being a complete tool -for FMC (Fewest Moves Challenge) practice. It can solve different steps -of Thistlethwaite's algorithm (also know as DR/HTR) and cans use NISS -(Normal-Inverse Scramble Switch). -</p> - -<p> -You should use Nissy if: -</p> -<ul> -<li> -You want to analyze your DR solutions or check for multiple optimal -(or sub-optimal) solutions for EO/DR/HTR or similar steps. -</li> -<li> -You just want a Rubik's cube solver and you like command line interfaces. -</li> -<li> -You want an alternative to Cube Explorer. -</li> -</ul> - -<p> -To get started, head to the <a href="/download/">download</a> page. -</p> - -<p> -You can also see its source code by cloning the git repository -<a href="https://git.tronto.net/nissy/">git.tronto.net/nissy</a> -</p> - -<hr class="line"> - -<nav class="bottom"> - <table class="footer"> - <tr> - <td class="contact"> - <a href="https://sebastiano.tronto.net">sebastiano.tronto.net</a> - </td> - <td class="hosted"> - <a href="mailto:sebastiano@tronto.net"> - sebastiano@tronto.net - </a> - </td> - </tr> - </table> -</nav> - -</body> -</html> diff --git a/www/screenshot.png b/www/screenshot.png Binary files differ. diff --git a/www/style-3.css b/www/style-3.css @@ -1,105 +0,0 @@ -.menu { - width: 100%; -} - -.links { - text-align: right; - font-weight: bold; -} - -.logo img { - width: 50px; - height: 50px; -} - -.footer { - font-style: italic; - width: 100%; -} - -.hosted { - text-align: right; -} - -body { - margin: auto 8px 20px 8px; -} - -img { - display: block; - margin-left: auto; - margin-right: auto; - max-width: 100%; -} - -code { - background-color: #eeeeee; - padding: 2px; -} - -pre code { - padding: 0px; -} - -pre { - background-color: #eeeeee; - border: 2px solid; - padding: 6px; -} - -#blob { - background: #ffffff; - border: none; -} - -a { - color: #0f2899; - text-decoration: none; -} - -.links a { - font-weight: bold; - color: black; -} - -.hosted a, -.contact a { - font-weight: bold; -} - -a:hover { - text-decoration: underline; -} - -html { - margin: 1em auto; - max-width: 42em; -} - -h1 { - text-align: center; -} - -td h1 { - text-align: left; - font-size: 1.5em; -} - -table { - width: 100%; -} - -.url td { - font-family: monospace; -} - -.dltable th, .dltable td { - border: 1px solid black; - padding: 3px; -} - -.subtitle { - text-align: center; - font-weight: bold; - font-size: 1.1em; -}