arnaud-m / cryptator Goto Github PK
View Code? Open in Web Editor NEWA constraint-based cryptarithm solver
License: BSD 3-Clause "New" or "Revised" License
A constraint-based cryptarithm solver
License: BSD 3-Clause "New" or "Revised" License
See here.
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.
Describe alternatives you've considered
Creating word lists, but it lacks flexibility.
Here is an example of cross number puzzles.
ABC * DE = CFGH
+ * -
JDHJ + DGC = JGKK
------------------
JEDK + EBAH = FAGH
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
.
The default code formatters of eclipse and intellij are different.
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.
Here are a few examples of new cryptarithms.
10 * A = BC
10 * A10 = 'ABCD'
10 * "10A" = "ABCD"
10 * '10A' = 'ABCD'
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
.
cryptator/src/main/java/cryptator/tree/CryptaLeaf.java
Lines 18 to 20 in 9bb4497
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).
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 relational operators with two letters (wikipedia).
The different constraints are separated by a semi-colon ;
.
It would allow to invent, solve, and generate cryptarithm variations.
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.
*=
for the long multiplication.Modelling Cross Number Puzzles is straightforward.
ABC * DE = CFGH
+ * -
JDHJ + DGC = JGKK
------------------
JEDK + EBAH = FAGH
cryptator/src/main/java/cryptator/tree/CryptaConstant.java
Lines 42 to 44 in 34eafc9
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
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 ?
The division operator /
computes the floor division (applying the floor function after division. So, for example, 5 / 2
is 2).
/
to //
for floor division./
for real division.The difficulty is that we are using integers for evaluation and integer variables for modeling.
Number of words, characters, operators, etc.
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.
Describe the bug
To Reproduce
Check the logs of the github action. For instance, this run should have failed.
Expected behavior
Describe the bug
The graphviz exports do not handle well the constants.
It displays their characters as symbols without values.
To Reproduce
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
The constraint is posted each time a symbol is the first letter of a word.
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.
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.
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 ?
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.
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 secondssixtytwo = 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
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.
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.
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.Is your feature request related to a problem? Please describe.
The syntax is misleading when the user wants to pass a partial assignment.
Describe the solution you'd like
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.
A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google ❤️ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.