.. _calculator:
Calculator with Two Buttons
---------------------------
The following problem was posed as the `DMCommunity November 2020 challenge. `_
.. admonition:: Calculator with Two Buttons
A calculator, initially displaying 0, has only two buttons:
* "+" adds 1 to the number on the display;
* "x" multiplies the number on the display by 10.
What is the least number of button presses needed to show 5034?
This problem can easily be solved by hand, but it is always fun to create a cDMN specification for these types of problems.
As always, we start by creating a glossary.
We need a type to represent presses and the two types of buttons.
.. raw:: html
| Type |
| Press |
Int |
[0..20] |
| Button |
String |
add, mult |
For every press, we need to represent what button was pressed and what value the display showed beforehand.
To do this, we create two functions, `button of Press` and `value of Press`.
In this way, if `button of 5 = mult`, this would mean that the sixth button pressed (starting at zero) was a multiplication.
Similarly for `value of 5 = 4`, then the value before the sixth button was pressed is 4.
.. raw:: html
| Function |
| button of Press |
Button |
| value of Press |
Int |
To represent the number of presses needed to reach our goal of 5034, we introduce a constant called `NbPresses`.
.. raw:: html
With our glossary done, we can start constructing tables.
The first table we add is a constraint table in order to specify that our starting number is zero, by fixing the value of the first press.
.. raw:: html
| Starting value |
|
| E* |
value of 0 |
| 1 |
0 |
After doing so, we add the constraints stating how the value changes when a button is pressed.
The first rule of the below table states that when the `add` button is pressed, the next value is the previous value plus one.
The second rule states that when the `mult` button is pressed, the next value is the previous value times ten.
.. raw:: html
| Calculate next value |
|
| E* |
Press called p1 |
button of p1 |
Press called p2 |
value of p2 |
| 1 |
- |
add |
p1 + 1 |
value of p1 + 1 |
| 2 |
- |
mult |
p1 + 1 |
value of p1 * 10 |
Now we define that the value of `NbPresses` is the press when the value reached 5034.
.. raw:: html
| Define NbPress |
|
| U |
Press |
value of Press |
NbPresses |
| 1 |
- |
5034 |
Press |
Now that we have all the required logic in place, we simply need to tell the system that we want to minimize the number of presses via the ``Goal`` table.
.. raw:: html
We can now run our model using the cDMN solver.
This results in the following output:
.. code:: bash
Model 1
==========
button_of_Press := {0->add, 1->add, 2->add, 3->add, 4->add, 5->mult, 6->mult, 7->add, 8->add, 9->add, 10->mult, 11->add, 12->add, 13->add, 14->add, 15->add, 16->add, 17->add, 18->add, 19->add, 20->add}.
value_of_Press := {0->0, 1->1, 2->2, 3->3, 4->4, 5->5, 6->50, 7->500, 8->501, 9->502, 10->503, 11->5030, 12->5031, 13->5032, 14->5033, 15->5034, 16->5035, 17->5036, 18->5037, 19->5038, 20->5039}.
NbPresses := 15.
Elapsed Time:
0.2470
The number 5034 can be reached in 15 presses!