Calculator with Two Buttons

The following problem was posed as the DMCommunity November 2020 challenge.

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, the two types of buttons and the value of the number.

Type
Name Type Values
Press Int [0..20]
Button String add, mult
Value Int [0..6000]

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.

Function
Name Type
button of Press Button
value of Press Value

To represent the number of presses needed to reach our goal of 5034, we introduce a constant called NbPresses.

Constant
Name Type
NbPresses Press

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.

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.

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 what that the value of NbPresses is the press when the value is 5034.

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.

Goal
Minimize NbPresses

We can now run our model using the cDMN solver. This results in the following output:

Number of models: 1
Model 1
=======
structure  : V {
  Button = { 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 }
  NbPresses = 15
  Value = { 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 }
}

Elapsed Time:
0.312465

The number 5034 can be reached in 15 presses!