Understanding sc2001.c

Sim Carol 2001, including this document, was written by Bill Godfrey.

Algorithm

SimCarol 2001 uses a brute force recursive descent algorithm. All possibilities are tried, inching towards one which matches the solution.

At each step, a list of available numbers are maintained. At the start, this list comes from the numbers given at the command line.

For each pairing of numbers, each of the four operators are applied.

In the case of subtraction and division, it is always the highest value (subtracted or divided by) the lower value. The rules do not allow a step to use negative or fractional values, and so the problem of "non-communative" operations do not apply, as there is only one valid way to apply any two numbers.

So for each triplet of two numbers and an operator, the result of this one calculation is found. If it matches the target, or gets closer than the previous near match, it is stored.

With the result of this one calculation, the pairing function is recursively called, this time with the two chosen numbers replaced by the one result of the previous calculation.

The recursion continues until the starting numbers have been reduced to one number. The recursion then backtracks to the caller and the next triplet of two numbers and an operator is attempted.

Similarly, when all triplets of two numbers and an operator have been exhasted, the recursion backracks to the caller.

When an exact match is found, the result is displayed. Any subsequent matches discovered are only displayed if the new result takes less steps than the previous discovery.

At the end, if no exact match is found, the nearest match is displayed.

Data types

term_t

A single number. Starting numbers, target, result of calculations. Valid values are 1 to (ULONG_MAX-1). 0 and ULONG_MAX have special meaning.

op_t

A single operator enumeration. Add, subtract, multiply, divide. Also a NULL value for use as array terminator.

step_t

A single calculation step. Consists of two numbers and an operator.

size_t

Array index type. Comes from <stdlib.h>.

int

Standard type. Used to step through argv and as a flag holder within the main function.

sol_t

A possible solution under development.

unused

Set of unused numbers, terminated with a zero.

steps

An array of steps undertaken to get from the starting numbers to the current set of unused numbers.

target

The ultimate target. Always the same from the command line.

result

Result obtained from the steps taken so far. (Or ULONG_MAX, the furthest from the target as is possible, so to have something to compare against.)

Code structure

Function main

Main's job is to parse the command line, validate and to start the recursion process.

Additionally, main will report the nearest match, if an exact match could not be found.

Function go_calc

This is the recursive core of the program. At the core are three nested for loops, generating triplets of two numbers and an operator.

Before it is processed, each triplet is validated.

• Subtracting two identical numbers leaves a zero, reject it.
• Dividing two numbers to leave a remainder is invalid, reject it.
• To multiply or divide by one is a wasted step, reject it.

A complete copy is made of the previous state, so that a recurrsive back track will be possible. This new copy will have the triplet applied, so that the two selected terms are replaced the one result of the calculation. (This update process is preformed by the update_unused function.)

This new possible solution is checked by the evaluate_sol function to see if it is a match, or a better match than the previous nearest find.

Finally, go_calc is recurrsively called, passing in the updated copy of the solution under development.

Utility functions

distance

Calculates absolute value difference between two term_t types. Simple subtraction is not used, lest 1 and (ULONG_MAX-1) are considered.
Used in considering if a new near miss match is better than the previous nearest.

count_unused
count_steps

Counts how many valid items are in an inparticular array.

do_step

Given the triplet of two numbers and an operator of the step_t type, the result is calculated and returned.

Macro LETNUM

Given a number, 0..25, returns the appropiate letter, for use in displaying a soluation.
Define the symbol USE_ASCII for an optimisation which only works when all 26 letters have continuous character values from 'A' with no gaps.

disp_sol

Displays a solution, step by step.

disp_unused

Used for debugging. Displays the unusued array, along with a prefix and suffix.

update_unused

Replaces two terms in an unused array with one, and closes up any gaps.

SimCarol 2001 was written by Bill Godfrey, with a bit of inspiration from Dave Jackson.