Crypto: Heuristic Problem Solver

Weve managed to build an exhaustive crypto solver, but thats not exactly the way that a human would go about solving a crypto problem. A human may often apply several heuristics which have previously proven useful before they attempt to solve a problem in an exhaustive manner. Having defined some heuristics, seen their applicability, and determined how difficult they are for a human to execute, lets try to think of a way to make a solver actually apply heuristics when solving problems. Well start by thoroughly defining heuristics (keeping applicability and hexecutability in mind). Each definition will have a name, english description, pseudocode, and examples.

Defining the Heuristics

Heuristic 1 - Zeros

This heuristic is one that is quite simple, leaving it with a very high hexecutability, but reletively low applicability. Still, it is an important heuristic to have, as the principle it follows is used in other heuristics. The heuristic has you verify that you have a goal of zero, as well as a zero that is a part of your numbers. This requires very little effort, as does the solution that it requires: multiplying all of the numbers together.

1. Number/Name: H1/Zeros
2. English: If the goal is zero and zero is among the numbers, then multiply all of the numbers together.
3. Pseudocode: if ( the goal is zero ) and ( zero is among the numbers ) then [ multiply the numbers together ]
4. Examples:
   1. numbers = {5,4,0,8,9}, goal = 0
      • solution = (5 * (4 * (0 * (8 * 9))))
   2. numbers = {0,5,3,5,8}, goal = 0
      • solution = (0 * (5 * (3 * (5 * 8))))
   3. numbers = {7,6,7,1,0}, goal = 0
      • solution = (7 * (6 * (7 * (1 * 0))))

Demo

Heuristic 2 - Zero and Goal

This heuristic adds two additional predicates to the previous heuristic: that the goal is not zero, and that the goal is among the numbers. After those two cases are fulfilled, then all you have to do is apply the previous heuristic to the remaining numbers. That means that if there is a zero in the remaing numbers, you can use this heuristic. Because this heuristic adds to the previous, it will be slightly harder for a human to execute, but this addition makes it much more widly applicable. You can use this for any goal greater than zero, because all you do is add the product of the non-goal numbers to the goal.

1. Number/Name: H2/Zero and Goal
2. English: If the goal is nonzero and zero and the goal are among the numbers, then add the goal to the result of multiplying all of the remaining numbers together.
3. Pseudocode: if ( the goal is nonzero ) and ( zero is among the numbers ) and ( the goal is among the numbers ) then [ add the goal to the product of the remaining numbers ]
4. Examples:
   1. numbers = {7,0,9,2,6}, goal = 9
      • solution = (9 + (7 * (0 * (2 * 6))))
   2. numbers = {5,4,3,1,0}, goal = 4
      • solution = (4 + (5 * (3 * (1 * 0))))
   3. numbers = {0,2,3,5,3}, goal = 3
      • solution = (3 + (0 * (2 * (3 * 5))))

Demo

Heuristic 3 - Zero Goal and Pair

Like the previous heuristic, this one draws on the same concept as the first one. In this heuristic, you must find a pair while you have a goal of 0, with a solution that is the difference of the pair multiplied by the remaining numbers. If you take a look back at the first heuristic, youll see that this is almost identical to it. In fact, when you are soliving a problem with this heuristic, you get a problem of length four with a zero in the numbers and a goal of zero, since the difference of a pair is zero. That makes the hexecutability reletively high, while also retaining a higher applicability than the first heuristic.

1. Number/Name: H3/Zero Goal and Pair
2. English: If the goal is zero and a pair exists among the numbers, then multiply the difference between the pair of numbers by all of the remaining numbers.
3. Pseudocode: if ( the goal is zero ) and ( a pair exists among the numbers ) then [ multiply the difference between the pair of numbers by all of the remaining numbers ]
4. Examples:
   1. numbers = {4,5,6,4,9}, goal = 0
      • solution = ((4 - 4) * (5 * (6 * 9)))
   2. numbers = {5,0,6,0,7}, goal = 0
      • solution = ((0 - 0) * (5 * (6 * 7)))
   3. numbers = {1,0,1,2,3}, goal = 0
      • solution = ((1 - 1) * (0 * (2 * 3)))

Demo

Heuristic 4 - Pair and Goal

Following the theme of the heuristics so far, we will use a pair to create a zero value in order to add it to the goal. This is a combination of Heuristics 2 and 3, where the goal number is in the set of numbers, and there is a pair in the remaining numbers. The solution in this case is the goal value added to the difference of the pair multiplied by the other numbers. Much like Zero and Goal, after you find the pair, you end up with a problem of length four, where the goal number is in the set of numbers, as well as a zero, allowing you to apply This has the same level of hexecutability as Zero Goal and Pair, but a larger applicability, because it can be used for any goal number.

1. Number/Name: H4/Pair and Goal
2. English: If the goal is nonzero and a pair exists among the numbers and the goal exists among the remaining numbers, then add the difference between the pair of numbers multiplied by the product of the non-goal numbers to the goal number.
3. Pseudocode: if (the goal is nonzero ) and (a pair exists among the numbers ) then [ add the difference between the pair of numbers multiplied by the product of the non-goal numbers to the goal number ]
4. Examples:
   1. numbers = {7,7,6,5,3}, goal = 6
      • solution = (6 + ((7 - 7) * (5 * 3)))
   2. numbers = {2,2,1,5,9}, goal = 9
      • solution = (9 + ((2 - 2) * (1 * 5)))
   3. numbers = {3,2,2,1,1,}, goal = 3
      • solution = (3 + ((2 - 2) * (1 * 1)))

Demo

Heuristic 5 - Pair and GoalX

With this heuristic, we will get more complex. This means that the hexecutability of the heuristic will be a noticeably smaller, but this is to keep the applicability reasonably high. We are making a sacrifice in human executability for a more robust heuristic. This heuristic requires you to identify a pair in a problems numbers, and then see if you can make the goal with the remaining numbers. This expression will work in a similar way to how Zero and Goal works, but with the goal taking the form of the expression that the remaining numbers make up in order to create the goal number. We will add this to the difference of the pair (zero), in order to get the goal number.

1. Number/Name: H5/Pair and GoalX
2. English: If a pair exists among the numbers and the goal can be made from the remaining numbers, then add the expression that makes the goal to the difference of the pair.
3. Pseudocode: if (a pair exists among the numbers) and (the goal can be made from the remaining numbers) then [add the expression that makes the goal to the difference of the pair]
4. Examples:
   1. numbers = {5,4,1,2,5}, goal = 8
      • solution = ((5 - 5) + (4 * (2 * 1)))
   2. numbers = {3,3,8,9,0}, goal = 1
      • solution = ((3 - 3) + (0 + (9 - 8)))
   3. numbers = {1,2,3,4,4}, goal = 9
      • solution = ((4 - 4) + ((1 + 2) * 3))

Demo

Heuristic 6 - Two and Double Goal

This heuristic requires you to find a two, and evaluate if you can create twice the goal number with the remaining numbers. Going through this process is a little bit more complicated than the previous heuristics, which means the hexecutability is lower than all the others, but it isnt so difficult that it is impossible to use, and the applicability is reasonably high as well.

1. Number/Name: H6/Two and Double Goal
2. English: If a two exists among the numbers and twice the goal can be made with the remaining numbers, then divide the expression evaluating to twice the goal by two.
3. Pseudocode: if (a two exists among the numbers) and (twice the goal can be made with the remaining numbers) then [divide the expression evaluating to twice the goal by two]
4. Examples:
   1. numbers = {5,5,7,2,2}, goal = 6
      • solution = (((5 * 2) + (7 - 5)) / 2)
   2. numbers = {6,4,8,2,3}, goal = 5
      • solution = ((8 + (4 / (6 / 3))) / 2)
   3. numbers = {3,9,5,2,8}, goal = 4
      • solution = ((8 * ((9 - 3) - 5)) / 2)

Demo

Heuristic 7 - Two Ones and Half Goal

This heuristic is similar to Two and Double Goal, except you must use four numbers to create two ones, and the remaing number must be half the goal number. This leaves you with a much higher hexecutability, but a much lower applicability, as you must have two sets of numbers that evaluate to one, so you can add them together and multiply the remaining number by the sum.

1. Number/Name: H7/Two Ones and Half Goal
2. English: If one half the goal is among the numbers and a pair of numbers evaluates to one and the remaining two numbers can evaluate to one, then multiply the one half by the sum of the expressions that evaluate to one.
3. Pseudocode: if (one half the goal is among the numbers) and (a pair of numbers evaluates to one) and (the remaining two numbers can evaluate to one) then [multiply the one half by the sum of the expressions that evaluate to one]
4. Examples:
   1. numbers = {8,8,2,6,6}, goal = 4
      • solution = (2 * ((8 / 8) + (6 / 6)))
   2. numbers = {6,2,3,3,5}, goal = 6
      • solution = (3 * ((3 - 2) + (6 - 5)))
   3. numbers = {4,9,8,5,5}, goal = 8
      • solution = (4 * ((9 - 8) + (5 / 5)))

Demo

Heuristic 8 - One More Than Goal

This heuristic is a bit simpler than the previous heuristic, it requires you to identify a one, a number that is one more than the goal, and find an expression that evaluates to zero using the remaining numbers. If the criteria are fulfilled, then all you have to do is add the zero expression to the number larger than the goal minus one The hexecutability for this heuristic is much better, as there are just two trivial verifications/validations, and then you need to do two small computations in order to see if the remaining numbers can evaluate to zero. Once again, this comes at the cost of applicability, but it is high enough for us to justify using.

1. Number/Name: H8/One More Than Goal
2. English: If the number that is one more than the goal is among the numbers and one is among the numbers and the remaing numbers can make zero, then add the zero expression to one more than the goal minus one.
3. Pseudocode: if (the number that is one more than the goal is among the numbers) and (one is among the numbers) and (the remaing numbers can make zero) then [add the zero expression to one more than the goal minus one]
4. Examples:
   1. numbers = {1,0,8,3,4}, goal = 3
      • solution = ((4 - 1) + (0 * (3 * 8)))
   2. numbers = {5,3,2,1,5}, goal = 4
      • solution = ((5 - 1) + ((3 - 2) - 1))
   3. numbers = {7,1,2,3,5}, goal = 6
      • solution = ((7 - 1) + ((3 - 2) - 1))

Demo