Switch branches/tags
Nothing to show
Find file
Fetching contributors…
Cannot retrieve contributors at this time
115 lines (94 sloc) 5.47 KB
Author: Ricardo Garcia Gonzalez
License: Public domain code
This program solves the numeric exercises from the Spanish TV show "Cifras
y Letras". In the program, the contestants are given 6 random numbers from
the following set:
1 2 3 4 5 6 7 8 9 10 25 50 75 100
Then they are asked, by using only natural numbers and exact operations,
to combine them arithmetically in order to find another random number from
100 to 999. Only sums, substractions, multplications and divisions are
allowed. For example, they could be given numbers (5, 5, 6, 25, 9, 7) and
combine them to get number 881. One of the possible answers is ((5 * 25 *
7) + 6). As you can see, using all the basic numbers is not required. If
you prefer to put it step by step:
5 * 7 = 35
25 * 35 = 875
875 + 6 = 881
This problem has been generalized in the program. You can use at least 2
basic numbers but as many as you want, and the range is not limited, at least
in theory. In practice, the amount of basic numbers and range is limited,
but the limits "should be high enough for anybody".
The program is divided in 3 different parts: the Operation class, the Node
class and the MemoryManager class. I will explain them in that order.
The Operation class is quite easy to understand. It's an abstract class
that represents a binary operation. It stores a left and a right operand,
and has methods to check if the operation is valid and to get the result. The
operation may not be valid. For example, you cannot divide by zero and you
cannot divide if the result is not an exact natural number (i.e. you cannot
divide 3 by 2). This abstract class has 4 subclasses that represent the
basic operations allowed in the game.
This class is used by the Node class. The problem we are trying to solve
can be represented by a graph. If we have a list of numbers that we can
operate together, we can form pairs of those numbers and try the different
operations in that pair. For example, lets suppose we have the numbers (1,
2, 3). 3 pairs can be formed with these numbers:
(1, 2) leaving out the 3
(1, 3) leaving out the 2
(2, 3) leaving out the 1
The first pair can be used in the following valid operations:
2 + 1 (result: 3)
2 * 1 (result: 2)
2 - 1 (result: 1)
2 / 1 (result: 2)
As we left out the 3 in the that first pair, by combining the other two we
have a result that can be operated with the remaining 3. That is, after doing
each one of those operations, we would have the following "partial results":
2 + 1 = 3, partial result (3, 3)
2 * 1 = 2, partial result (3, 2)
2 - 1 = 1, partial result (3, 1)
2 / 1 = 2, partial result (3, 2)
In other words, we start with a so-called root node that has all the initial
numbers. This node is connected to many partial result nodes, by performing a
high number of operations with pairs of numbers. Each one of these, in turn,
is connected to a whole set of more partial result nodes, with as much deep
as needed to reach the target number, or until the partial result only has
one number remaining.
This graph is not a tree, as you can see in the example above. Both (2 * 1 =
2) and (2 / 1 = 2) allowed us to go from the node (1, 2, 3) to the node (2,
3). A node has three very important things: first, it has a list of operations
needed to reach it from the root node; second, each node introduces a new
number which is the result of operating a couple of numbers; third, it has a
list of remaining usable numbers to be combined to reach the result, and this
list includes the newly introduced number. When generating a new node, the
child node has a new list of operations, which is the same as in the parent
node plus one more operation, a new introduced number, which is the result
of the last operation, and a list of possible numbers to be combined, which
are the numbers not used in the operation, plus the result of the operation.
This allows us to recursively apply backtracking and explore the graph. If,
on top of that, we store the partial results we obtain, this can be done
efficiently. This means we wouldn't explore the node (2, 3) the second
time it appears. All this work is done in the Node constructor. The Node
constructor builds the full problem graph, because when building a node,
it builds all of its children.
One minor implementation detail is that the initial number list is sorted in
descending order, and when a new number is introduced, it's also inserted
preserving order. Order preservation allows us to form valid pairs quickly
and easily with the algorithm present in the node constructor, where each
number is paired with all of the numbers to its right. This way, we make sure
substractions always work, and divisions may work if the result is exact. We
don't need to try the other way around with these two non-commutative
operations, because we know we can't subtract B from A or divide A by B if
B is greater than A.
Finally, the MemoryManager class was designed to help track new nodes and
operations we need to create. It creates operations and nodes on the fly,
and stores all pointers it returns. This way, we can clean memory at any
point using the free() method. Currently, this is called at the end of the
program. This class is also designed using the Singleton design pattern. This
means the class has a static pointer to an object of the same class, and the
constructor is private. Te only way to get a MemoryManager instance is to call
the instance() static method, which always returns the same instance. This
guarantees there's only one MemoryManager object in the same program.