Rewritten from scratch. Welocme nissy 2.0!

1 files changed, 118 insertions, 31 deletions

diff --git a/README.md b/README.md
index 39d1857..fc71f2d 100644
--- a/README.md
+++ b/README.md
@@ -1,41 +1,128 @@
-# nissy
-A Rubik's cube solver and FMC assistant.
+# Nissy
 
-## Just another cube solver?
-Yes, pretty much. I wanted to write one and I started coding without any
-specific goal in mind. It is not more efficient than [CubeExplorer](http://kociemba.org/cube.htm), nor it is
-particularly user-friendly.
+A Rubik's cube solver and FMC assistant. For optimal HTM solving nissy is about as
+fast as Herbert Kociemba's [Cube Explorer](http://kociemba.org/cube.htm), and it
+uses the same method. Nissy can also solve many different substeps of
+Thistlethwaite's algorithm (DR/HTR), and can use NISS (Normal-Inverse Scramble Switch).
 
-## But does it do something unique?
-Yes, actually it does, but only for a very small niche of people. It allows to produce step-by-step solutions using DR
-([Thistlethwaite](/https://www.speedsolving.com/wiki/index.php/Thistlethwaite%27s_algorithm)/[Kociemba](https://www.speedsolving.com/wiki/index.php/Kociemba%27s_Algorithm) algorithm)
-combined with [NISS](https://www.speedsolving.com/wiki/index.php/Fewest_Moves_techniques). This makes it somewhat useful for [FMC](https://www.speedsolving.com/wiki/index.php/Fewest_Moves_Challenge) solvers who want to analyze a scramble and see if they missed something,
-or what was the optimal way to solve a certain substep at a given point, and so on.
+It can be useful to analyze your DR solves (and more, once I implement more features).
 
-## How to use it
-**Update:** the file nissy-win.exe should work as a Windows executable, but
-I have not tested it (I don't have a Windows machine).
+## Why should I use nissy?
 
-Check out the help pages in the docs folder. They are also available from
-within nissy with the command "help".
+You should use nissy if you:
+* Want to analyze your DR solutions or check for multiple optimal (or sub-optimal)
+solutions for EO/DR/HTR or similar substeps.
+* You just want a Rubik's cube solver and you like command line interfaces.
+* You want an alternative to Cube Explorer.
 
-I will add more examples and maybe screenshots when I feel like.
+## Requirements
+
+A full installation of nissy requires about 1.8Gb of space, of which 1.6Gb are
+occupied by the huge pruning table for optimal solving, and running it requires
+the same amount of RAM.
+One can choose to never use the optimal solver and not to install the relative
+pruning table. If so, about 200Mb should be enough.
 
 ## Installation
-For now you have to download all the files and compile the source 
-code yourself. Remember to tell your
-compiler to use the [C99 standard](https://en.wikipedia.org/wiki/C99). For
-example, on a Linux system with GCC installed:
 
-```
-cd path/to/nissy
-gcc -O2 -std=c99 -o nissy ./src/*.c
-./nissy
-```
+### On a UNIX system:
+
+You can download the source code for the latest version from git or simply clone
+the repo with `git clone https://github.com/sebastianotronto/nissy`.
+
+Edit the Makefile to match your local configuration (usually not necessary, but you
+may want to change the `PREFIX` variable) and run `make`, followed by `make install`.
+After that, you need to download some files and manually save them to your `NISSYDATA`
+folder (see manual page, ENVIRONMENT section). If you don't do it nissy can compute
+these files when needed and save them in the correct folders, but some of them
+take hours to generate even for a powerful computer (for reference, the huge pruning
+table takes about 20 hours on my laptop).
+
+Choose one of the following:
+
+| |.zip|.tar.gz|
+|-|-|-|
+|Full (~720Mb)|[full.zip](https://math.uni.lu/tronto/nissy/nissy-tables-full.zip)|[full.tar.gz](https://math.uni.lu/tronto/nissy/nissy-tables-full.tar.gz)|
+|No huge table (~90Mb)|[nohuge.zip](https://math.uni.lu/tronto/nissy/nissy-tables-nohuge.zip)|[nohuge.tar.gz](https://math.uni.lu/tronto/nissy/nissy-tables-nohuge.tar.gz)|
+
+extract the archive and copy the `tables` folder into `NISSIDATA` (paste there
+the whole folder, not the single files). The `nohuge` files are much smaller and
+do not contain the huge pruning table for the optimal solver.
+
+### On Windows
+
+Coming soon.
+
+## Structure of the code
+
+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.
+
+### Cube, moves and transformations
+
+There are many ways to represent a cube. In nissy I use two:
+* 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.
+
+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 huge pruning table, which
+results in around 1.6Gb instead of 24 or so.
+
+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 associate 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`)...
+
+There is one caveat: each coordinates also needs an inverse function that takes a
+coordinate value and returns a cube which has that coordinate. This is in general
+more complicated, but luckily the cube does not need to be fully built or consistent.
+This inverse-coordinate is used only in one specific step when building pruning tables
+to avoid using up hundreds of Gb of memory.
+
+Note: this part is different from what Cube Explorer does. Overall I think it is
+conceptually easier, although in practice it was still hard to implement.
+If anything it is more generalizable and one can use it to build any coordinate
+they might like.
+
+### Solving
 
-You can also use the script compile.sh, which executes that
-gcc line (with a few extra options).
+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.
 
-## Tips
-You can use a tool such as [rlwrap](https://github.com/hanslub42/rlwrap) to allow
-for infinte command history within nissy!