arnaud-m / cryptator Goto Github PK

• Refactor, clarify, and document code to prepare #32
• Improve the constraint that bounds the number of digits required for the results of a sum.

Here is an example of cross number puzzles.

ABC   *  DE = CFGH
  +      *      -
JDHJ +  DGC = JGKK
------------------
JEDK + EBAH = FAGH

• Add junit tests for valid equations
• Add junit tests for invalid equations.
• Add help/error messages for invalid equations.
• Use English for naming and commenting
• Enforce that the comparator is the root of the equation tree

See Using non-ASCII characters in token rules.

Is your feature request related to a problem? Please describe.
It seems that the status badge is only triggered by the main branch.
See here.

Describe the solution you'd like
I would prefer that the status badge is triggered by the current branch.

Provide usage examples
See commit 058d7aa that has a failing status.

The division operator / computes the floor division (applying the floor function after division. So, for example, 5 / 2 is 2).

• Change / to // for floor division.
• Use / for real division.

The difficulty is that we are using integers for evaluation and integer variables for modeling.

Is your feature request related to a problem? Please describe.

• a+b=c ; a = b is accepted by the parser.
• a+b=c && a = b is rejected by the parser.

The first syntax is natural for writing a cryptarithm, but not always for display.

Describe the solution you'd like
Allow both syntaxes.

Provide usage examples
Here is below an example using graphiz.

Is your feature request related to a problem? Please describe.
The parser uses a special empty word leaf that represents 0 when parsing -a as 0-a.

Describe the solution you'd like
Use a constant node and parse -a as '0'-a.

Describe alternatives you've considered
Keep it as it is, but it allows to simplify the code of several consumers (features, exports, etc).

The constraint is posted each time a symbol is the first letter of a word.

At this moment the classic solver does not accept words with leading zeroes.
However, it could be interesting to make a cryptarithm of type -a=a where a must equal zero.

Another case where a single-letter word should be zero is when we force a letter to be zero.
For example in send+more=money we are able to add the constraint m=1 and have send+more=money; m=1.
Similary it would be usefull to be able to declare o=0 in a similar situation send+more=money; o=0.

Is your feature request related to a problem? Please describe.
The default search is pretty efficient, but sometimes trashes.

• sixtyone + one = sixtytwo is solved within seconds
• sixtytwo = sixtyone + one is not solved within minutes.

It happens because the solver starts branching on the sixtytwo variable that has a huge domain !
It does not happen for the bignum model that does not define any variable representing the entire word.

Describe the solution you'd like
One must evaluate and select the searches of choco.
A minimum requirement is to declare the decision variables.

Describe alternatives you've considered
TINA

Use relational operators with two letters (wikipedia).

Liste de mots français Gutenberg

• Do we protect the main branch ?
• Which rules do we enable ?

Is your feature request related to a problem? Please describe.
We have retrieved a number of thematic word lists, but we would like to generate new cryptarithms.

Describe the solution you'd like
Add new word lists gathered from the internet.

The different constraints are separated by a semi-colon ;.

It would allow to invent, solve, and generate cryptarithm variations.

Long Multiplication

               S E E
                  S O
             ---------
              E M O O
            M E S S
           -----------
            M I M E O

A long multiplication is stated by multiple constraints :

• SEE * SO = MIMEO
• MIMEO = EMOO + 10*MESS
• SEE * O = EMOO
• SEE * S = MESS

Note that the second constraint can not be stated yet.

• Modify the parser so that 10 is read as a number rather than a word.
• Or, define a special operator *= for the long multiplication.

Cross Number Puzzles

Modelling Cross Number Puzzles is straightforward.

ABC   *  DE = CFGH
  +      *      -
JDHJ +  DGC = JGKK
------------------
JEDK + EBAH = FAGH

Describe the bug

• The github action only executes the extended test suite, but does not execute the normal test suite.
• The dependencies are not in the cache.

To Reproduce
Check the logs of the github action. For instance, this run should have failed.

Expected behavior

• Execute both the normal and extended test suite.
• Cache the repo to speed up builds (see here)

Describe the bug
The graphviz exports do not handle well the constants.
It displays their characters as symbols without values.

To Reproduce

1. Go to project root.
2. Type the command below.
3. Open the generated SVG file.

 java  -cp target/cryptator-0.5.0-SNAPSHOT-with-dependencies.jar cryptator.Cryptator -g TRUE "send + more = money + '0'"

Expected behavior
The question marks should always be removed for constants.

Screenshots

Number of words, characters, operators, etc.

• Each generate-and-test solvers must implement the ICryptaSolver Interface.
• It throws an exception if it cannot handle the configuration.
• Ideally, there would be only 2 such solvers: a naive solver and a more advanced one.

See here.

• The checker is not taken into account when activated.
• The exit code of the program is not set

Is your feature request related to a problem? Please describe.

• m= '1' is accepted by the parser.
• m= "1" is rejected by the parser.

Describe the solution you'd like
Allow both delimiters which is convenient for writing shell command.

A leaf with symbol 0 is inserted instead of a Null/Zero leaf !

To reproduce the problem, execute the cryptator command with the following cryptarithms

• send + more = money returns a single solution (that is correct).
• (- send) +(-more) = - money fails to find any solution.
• (- send) -more = - money returns two solutions where the symbol 0.

At this time, a sequence of digits is always parsed as a word.

The grammar must be extended so that a sequence of numbers can also be parsed as a number.

• Use ticks as optional delimiter for words.
• A word must be enclosed by ticks if its first letter is a digit.
• A sequence of digits not enclosed by ticks is a number.

Here are a few examples of new cryptarithms.

10 * A = BC
10 * A10 = 'ABCD'
10 * "10A" = "ABCD"
10 * '10A' = 'ABCD'

For now, we can export the cryptarithm, partial solution, or solution to graphviz text format.
We want to directly generate the image, for instance SVG.

• use graphviz with pure java graphviz-java.
• or use other graph libraries : graphstream; jgrapht.

Is your feature request related to a problem? Please describe.
Generate geographical cryptarithms.

Describe the solution you'd like
Create the word list by executing a request on a geographical API chosen among 11 Popular Cities APIs.

• GeoDB Cities API, or
• Spott API ?

Describe alternatives you've considered
Creating word lists, but it lacks flexibility.

Describe the bug

The syntax is misleading when the user wants to pass a partial assignment.

• send+more=money; m = '1' has solution.
• send+more=money; o = '0' hasn't a solution.

Indeed, the model enforces that the variable 'o' is non zero, because it is the first letter of a word.
So, it is not possible to assign a letter to 0.

To Reproduce

1. Go to the project root.
2. Type the command below.

java -cp target/cryptator-*-with-dependencies.jar cryptator.Cryptator -g TRUE "send+more=money; o = '0'"

Expected behavior

This is the unfortunately the expected behaviour.
Define a special operator, for instance := for passing a partial assignment ?

Is your feature request related to a problem? Please describe.
Update choco to benefit from the latest enhancements and to seek support more easily.

Describe the solution you'd like
Update to the latest choco release.

Additional context
A first attempt has shown that the expression handling has changed : some tests will fail.
We must determine if the tests fails because of a regression.
It requires to isolate the failing tests, hard-code the models and post issues in the choco project if needed.

Is your feature request related to a problem? Please describe.
The syntax is misleading when the user wants to pass a partial assignment.

• #52
• #39

Describe the solution you'd like

• Add a new option to the command line for passing a partial assignment to the solver.
• A data structure already exists for partial/total solution, and it would be used to state constraints.

Describe alternatives you've considered
Extend the grammar with a new assignment operator :=.
But, it is a bad architecture because the input and output of the problem are mixed.

Provide usage examples

• -s 'o=0' -v TRUE' 'send+more=money'
• -s 'o=0 m=1' 'send+more=money' 'donald+gerald=robert'

Note that the partial assignment is applied to all cryptarithms of the command.

• www.objectdb.com
• www.dizitart.org

• Getting started with Github Actions: Run JUnit 5 tests in a Java project with Maven
  
• Github tutorial for java

Is your feature request related to a problem? Please describe.
We need to compare the different models for solving the cryptarithms.

Describe the solution you'd like
We need to define benchmark instances for the following decision problem.
Is the input equation a cryptarithm with a unique solution ?

• The benchmarks instances are divided into thematic datasets.
• The instances are the most difficult. Easy instances are discarded.
• Each dataset is a single file with an instance per line.
• Datasets are generated thanks to the generation model.

Describe alternatives you've considered
Generate the datasets instances on the fly, but it is slower and less reproducible.
Indeed, the candidate set can change depending on the generation model.

The default code formatters of eclipse and intellij are different.

• Is there a common predefined style?
• Use the intellij adapter?