Matchstick task is much more complex than we initially thought. Examples can be made easily, but unfortunately testing for solutions is not so simple as one can easily overlook a couple of them. A matchstick equation resolver program (in the text: program) has to be written to help us overcome these issues and produce good matchstick-equation test cases, for which we are aware of all solutions.
(a) The main purpose of our program will be to calculate all possible solutions for a given matchstick equation under different number of allowed moves.
(b) The secondary purpose is to build such equations under different requirements that can later be used in the group tasks.
Program building steps in order:
Understanding the problem space
Program firstly needs to be able to understand which matchstick-built symbols, that build up equation, and equations are valid. Understanding all elements at play is the prerequisite that will enable it to work with our matchstick equations.
All allowed mathematic symbols have to be identified. Currently they are separated into 3 categories: Numerals (1, 2, 3, 4, 5, 6, 7, 8, 9, 0), Operators ( + [addition], - [subtraction], * [multiplication], / [division] ) and Comparators ( = [equality], ≠ or ! [non-equality], < [smaller], > [bigger] ). At this point it is still uncertain if inequality comparators will be allowed, so the implementation will take this into account and make them loose-coupled with the program implementation. Each of these categories has an underlying background-framework, that basically specifies where the matches can be placed and in turn how symbols can be manipulated to create other symbols. Necessary restrictions have to be asserted to prevent undesired symbol manipulation (eg. number one can be written as a "vertical stick" (using 2 matchsticks) or with additional diagonal line at the top and bottom, like this: 1 (using up to 4 matchsticks). The allowed symbols have to be agreed upon and presented to subject-solver at the beginning of the task. These specified symbols need to be specially marked with final and thus not allowed to be messed with in any way.
The actual matchstick elements need to be modifiable and not necessary valid at every step. They however need to have an isValid() method that will ensure that the element is one of the specified symbols at the beginning and at the end of a task. Unlike allowed symbols, mentioned in above paragraph, these elements do have a matchstick setup, but do not have a representable mathematic symbol. They can easily be understood as "a work-in-progress pile of matches", that may or may not resemble any allowed mathematic symbol.
A series of ordered valid matchstick elements is known as a matchstick equation. Elements are ordered in our standard convention, from left to right, and this element order in the equation must always be preserved through equation manipulation. Elements in the equation can be subjected to manipulation by actions, which can change the shape of none or multiple elements. There are currently no actions that can change the order of elements in equation sequence. After each series of executed actions, the equation must remain valid.
There are a few rules to which each equation must adhere in order to be considered valid: (0) Each element in the equation must be valid by itself, (1) Exactly one comparator element must be present in each equation, (2) Each operator and comparator must be preceded and succeeded (in the present element order) by a numeral element and (3) Only numerals are allowed to be multiple in sequence. These rules are based upon standard infix notation and will ensure that equations are considered valid even to the less trained eye. Thus 4+15=3 is a valid equation, while 4+/6= is not. Be advised that this rules forbid using minus symbol for negation, making -5=8-3 invalid.
Equation is considered correct if (0) it is valid and (1) calculating results on each side of the comparator element yields the values on each side of the comparator element, that are in accordance with its comparing rules. Calculating refers to extraction of values according to values of numerals and rules of operators in-between. When multiple numerals are in sequence, their value is combined according to the rules of decimal notation form. Each operator has a priority and rule and acts upon neighboring numerals. Operators with highest priority (multiplication and division have priority of 2 and subtraction and addition have priority of 1) have to be resolved before operators with lower priority. In case more operators with the same priority are present, the operator on the left has to be resolved first. Each operation has a rule on which values of neighboring numerals are combined. We will not discuss these operation in detail here, but their descriptions can be found here: ( + ) addition, ( - ) subtraction, ( * ) multiplication and ( / ) division. No other actions are allowed to be preformed. Once both of the sides are calculated, they are compared according to the comparator that lies between them. The equation is marked as correct if and only if one of the following is true: (1) When the presented comparator is <, the left value must be lower then the right, (2) When the presented comparator is <, the left value must be greater then the right, (3) When the presented comparator is =, the left and right values must be the same and (4) When the presented comparator is ≠, the left and right value must not be the same. This concludes the calculation of equation correctness.
We are going to introduce two new terms: action and subaction. An action is executed on the whole valid equation and must produce another valid equation. There is no rule that produced equation must differ from original one, but it is strongly desired and such actions will be later automatically dismissed (they do not make any progress to make a correct equation from an incorrect one and thus cannot compete with the actions that do - this may be changed in the future). Action is split into subactions that work on a single symbol. Each subaction must produce another valid symbol - again there are no rules that prohibit creation of the same symbol, but the above rules still apply. All subactions together must form an action.
Subaction is defined on a starting symbol by the amount of matches that can be added and the amount of matches that can be removed - eg. (2, -1) this subaction can add one match to the symbol and move one match inside the symbol (remove one and put it back in), totaling in 2 added and 1 removed match. The order of executing addition and removal of matches does not influence the final created symbol. A subaction can produce none or multiple valid symbols. An action is a collection of subactions on a single equation and is again determined by the amount of added and removed matches. The total added matched must match the sum of added matches in all subactions and the total removed matches must match the sum of removed matches in all subactions. Eg. an action (1, -1) can be split into two subactions (1, 0), (0, -1), where one removes a match from a symbol and the other one adds a match to a different symbol, or it can also be made into just a single subaction which removes and adds a match to the same symbol. Observe that moving a match is in our description nothing more than removing a match from one symbol and adding a match to another (or same) symbol.
A subaction can produce none or just a couple of different symbols. But for an action, all possible combinations of subactions on all symbols have to be considered, in order to obtain all produced valid and correct equations. The complexity of a single action is therefore determined by numbers of added and removed matches and number of symbols in the equation. Every valid produced equation must afterwards be tested for correctness.
In order to make a list of all starting equations for each group, we must first find valid equations that will suffice for each group's requirements. This is much easier said than done. One heuristic that comes to mind is to take a correct equation and execute one action on it - thus we get a valid new equation, for which we are sure that is solvable with a single action. We don't however know anything else about this new equation: is it correct? is it solvable in any other way? This strategy is reasonably good, but we are not going to use it. Rather, we are going to produce all random valid equations (of a predetermined element-type sequence) in a specific order and test them for all possible solutions. This way we get the surety that no equation will be attempted to be solved more than once and that all possible equations will be tested - such surety is not available when using previous strategy without a complex cache of previously tested equations.
The program described above is very simple by its nature, mainly due to its heavy reliance on recursive functions. In theory this is not a problem, however, when we attempt to run such a program on a less capable computer, troubles soon arise. Recursion consumes a lot of memory space as it tries to solve a problem in one go and sometimes, in case of large problems, this is just too much. Most of the recursive functions will, therefore, have to be replaced with their iterative counterparts. The latter are able to select and tackle one part of the problem at a time and thus free memory space for other calculations. This ability will also enable us to pause the program execution and easily resume it later without having to redo all already done work. On the negative side, iterative execution is much harder to implement and much more prone to errors. However, the benefits are so great, that we will stick with it and try to remove as many deep recursions as possible.
Checking validity of constructed symbols and validity and correctness of equations can be quite repetitive task. Performing such tasks consumes way too much computational power that could easily be avoided. In order to remedy the situation, we will introduce cache for commonly occurring operations. In this construct, the real calculation will only be performed once and saved to memory for easy access. For all following calculations with the same input, the correct answer will just be read from memory.
Caution is advised as caches can easily overwhelm the memory and often clean-up methods have to remove some of the less used calculation-answers to free some of the used memory.
The program has run successfully and produced the following results. However, this was just a trial run and much more has to be debated over, to determine which equations may be used for our experiment.
File containing solutions for a single match move
https://drive.google.com/file/d/0B3mDFo2JJraHY1k3dFVBZXlCU00/view?usp=sharing
File containing solutions for a single and double match move
https://drive.google.com/file/d/0B3mDFo2JJraHM1VQVlJDRURVVTA/view?usp=sharing
The solutions for already correct starting equations have been removed. And also keep in mind that in many equations, where a solution can be achieved in one matchstick move, the same solution can be achieved in two matchstick moves, where the second move just removes a random match and puts it back on the same place. This is an undesirable way to tackle the given task, but the solution is still valid. In the future such solutions will be filtered out of the list.
Data in the files has to be read as follows:
Example:
| Original equation |
Action (short) |
Action overview |
Resulting equation |
||
| 9-9*9=9 |
-- |
(+1, -1) |
(+ , - , wO) |
-> |
9/9*9=9 |
| -- |
(+1, -1) |
(+ , - , wN) |
-> |
9-0*9=9 |
|
| -- |
(+1, -1) |
(+N, -O, w ) |
-> |
9-9/9=8 |
The action (+1, -1) marks that one match was added (+1) to the original equation and one match was removed (-1). This action results in a classical move of a matchstick.
Action overview marks where the match was added ( + ), removed ( - ) or moved within( w ). Character "O" marks the change with an operator element and character "N" within a numeral element. There exists also the change with a comparator element, marked with "C", but these have been removed from the given list. Overview "wO" marks a move of a matchstick within one operator element: '-' -> '/'. Overview "wN" marks a move of a matchstick within one numeral element: '9' -> '0'. And lastly "+N, -O" marks move of a match from a numeral to an operator element: '*' and '9' -> '/' and '8'.
We can take advantage of these features.
There are quite a few changes expected to be made, most of them after a prolonged discussion. But for now it is planned to sort these equations and their solutions in appropriate files, each of them containing equation/solution pairs with certain properties, regarding finding solutions. One file will contain equations that can only be solved by moving matches between operators, the other equations that can only be solved by moving matches between numerals and the third file collection of equations that can be solved by both such match moves. This is just an example and we will fully define these equation collections later. But for now let it show the work that still lies in front of us.