PUZZLET 002 - THE SOLUTION

This is the old solution to Puzzlet 002, using iBasic. There is a later version using BB4W (BBC Basic for Windows) available which is faster and simpler than the old one. Click here to see it.I pointed out in the introduction to this Puzzlet that my solution contains something no previous published version, to the best of my knowledge, does. All published material that I've seen contains only eleven solutions. The iBasic program below will find a twelfth. Here's the code:

' Puzzlet #002.

' Take the digits 1 to 9 in order, to give 123456789.

' Insert "+" and "-" signs anywhere such that the

' resultant sum is exactly 100.

' Example: 123 + 45 - 67 + 8 - 9 = 100.

' By Dave Ellis.

' Declarations

declare Binary(b: int , pad: int )

declare MakeCheckString()

declare Totalise()

declare Evaluate()

def i: int

def bin$: string

' Screen SetUp

color 11, 0

openconsole

print "Searching ... ": print

color 14, 0: print

for i = 0 to 255

bin$ = Binary(i, 8)

check$ = MakeCheckString()

Totalise()

next i

' Finished

print "That's all, folks! ",

print "Press any key ..."

do : until inkey$ <>""

closeconsole

end

' +++ Functions and Subroutines +++

sub Binary(b, pad)

' converts denary integer b into a binary

' number. Returns a string padded with

' zeros on the left to make length = pad.

' By Dave Ellis

def d: int

def binary$, temp$: string

binary$ = ""

d = b

do

if d % 2 = 0

temp$ = "0"

else

temp$ = "1"

endif

binary$ = temp$ + binary$

d = int(d /2)

until d = 0

temp$ = string$ (pad- len (binary$), "0")

binary$ = temp$ + binary$

return binary$

sub MakeCheckString

' Takes global variable bin$ as input.

' Generates string "123456789" and in-

' serts + between digits in line with

' 1's contained in bin$. Returns mod-

' ified string.

' By Dave Ellis

def i: int

def temp$: string

temp$ = "+1"

for i = 1 to 8

if mid$ (bin$,i,1) = "1"

temp$ = temp$ + "+"

endif

temp$ = temp$ + ltrim$( str$ (i+1))

next i

return temp$

sub Totalise

' Runs as many times as there are binary

' combinations of the number of +'s in

' check$. For each combination, inserts

' a pattern of +'s and -'s accordingly.

' Passes resultant string each time to

' subroutine evaluate().

' By Dave Ellis

def sign$: string

def partCheck$: string

def count, i, j, k, Lsign: int

count = len (check$) - 9

for i = 1 to count - 2

sign$ = Binary(i, count)

Lsign = len(sign$)

j = 1

k = 1

do

partCheck$ = mid$ (check$, k ,1)

if (partCheck$ = "+") | (partCheck$ = "-")

select mid$ (sign$, j, 1)

case "0"

replace$(check$, k, 1, "-")

case "1"

replace$(check$, k, 1, "+")

endselect

j = j + 1

endif

k = k + 1

until j > Lsign

Evaluate()

next i

return

sub Evaluate

' Takes global variable check$ as input.

' Makes arithmetical evaluation of check$

' to produce an arithmetic value.

' If the value = 100, prints it out.

' By Dave Ellis

def flag, i, L, op, tot: int

def sum$, temp$, value$: string

L = len (check$)

tot = 0

i = 1

do

value$ = mid$(check$, i, 1)

select value$

case "+"

op = 1

case "-"

op = -1

default

flag = 0

sum$ = ""

do

temp$ = mid$ (check$, i, 1)

if (temp$ <> "+") & (temp$ <> "-")sum$ = sum$ + temp$

else

tot = tot + op * val(sum$)

flag = -1

i = i - 2

endif

if i = L

tot = tot + op * val(sum$)

endif

i = i + 1

until flag = -1 | i > L

endselect

i = i + 1

until i > L

if tot = 100

if left$ (check$, 1) = "+"

temp$ = " " + right$ (check$, (len (check$) - 1))

print temp$,

else

print check$,

endif

print " = 100"

endif

return

Program Notes

I started with the idea that the digits 1 to 9 inclusive can be expressed as 123456789 or 1 2 3 4 5 6 7 8 9. That is, there can be a maximum of 8 spaces between the digits, and a minimum of zero spaces. This prompts the thought that if the spaces are made to correspond to logic 1 and the lack of a space corresponds to logic 0, it is possible to express every single combination of spaces by simply running through the binary count 00000000 to 11111111 and at each count inserting logic 1 as a space and ignoring logic 0.

The following code, which forms the main routine in the program, does that:

for i = 0 to 255

bin$ = Binary(i, 8)

check$ = MakeCheckString()

Totalise()

next i

It runs through values foriof 0 to 255, which correspond in binary to 00000000 to 11111111. The denary value ofiis passed to the functionBinary(), along with the parameter 8. This is instructing the function to return the binary representation ofi, padded out to 8 characters. This padding is necessary as leading digits would be lost, and that is also why it's returned as a string and placed into the variablebin$.

Let's take a typical bin$ value returned, "00010011" corresponding to anivalue of 19. This is used by the subroutineMakeCheckString()now to convert our standard number 123456789. Wherever it sees a 1 inbin$it needs to insert a space, making 1234 567 8 9. In practice, those spaces will be either a minus sign or a plus.makeCheckString()takes the initiative and inserts a plus to get the process started, and returns "1234+567+8+9" to be stored incheck$.

This value is now processed by the subroutineTotalise(), whose task is to work out the literal arithmetic value of the string. However, it has to cope with the fact that the plus signs can also be minus signs.

The variable,count, is used to generate a series of strings calledsign$, corresponding to the pattern of minuses and pluses in the little table on the right. It uses our old friendBinary()to do this, passing in the current value of a local iterator forcountand the variablecountitself as a padding value.

0 0 0

0 0 1

0 1 0

0 1 1

1 0 0

1 0 1

1 1 0

1 1 1

The 8 iterations ofcountwill produce a sequence of alterations tocheck$, as shown inset.

The next bit is the last! These strings are passed one at a time to the subroutineEvaluate()whose task is to produce an arithmetic result.

Once it has a value, it compares it with the desired result, denary 100. If it matches,check$is printed out and the program goes on to the next possible value ofcheck$.

Thebinary()function works by using the schoolboy approach.

Divide d by 2.If there’s a remainder, save it as “1”.If there’s no remainder, save it as “0”.If d equals zero, go to step 5, otherwise repeat steps 1 to 4 again.If the string of 1’s and 0’s is of lesser length than pad, add 0’s to make the lengths the same.Return the string thus formed – it’s the required binary string.bin$will contain an 8-bit binary number. The subroutineMakeCheckString()generates “123456789” and, after every integer generated, inserts a plus sign if the corresponding digit inbin$is a “1”, otherwise no insertion is made. The purpose here is simply to put in a marker for later use which effectively says “Some punctuation is needed here. I’ll decide later whether it’s to stay as a Plus or be turned into a minus.”

As explained above, the variablecountis used to hold the number of pluses or minuses that will eventually be inserted into the “123456789”. In the subroutineTotalise(), iterator i loops through all combinations of inserted plus and minus signs except all pluses or all minuses. For example, if there are 3 spaces to use, the possible values would 000, 001, 010, 011, 100, 101, 110, 111. Of these, 000 and 111 are redundant as they would signify all minuses or all pluses.Neither of these punctuations can ever result in a sum of one hundred as required. This explains the line “for i = 1 to count – 2”.

The rest of the subroutine is an assortment of string slicing to put every possible combination of pluses and minuses in the current string. Each time another valid combination is ready, it’s evaluated by the subroutineEvaluate().

Evaluate()will set about processingchecks$, which was punctuated by plus and minus signs in the subroutineTotalise(). String slicing is again used extensively here. Where several digits appear without punctuation, they have to be enumerated according to length. For example, 123 is completely different from 12+3.

When you run the program, the output screen looks like this:

What's special about these solutions? The penultimate line starts with a -1. I've never seen it in any published solutions before.

I believe the answer is legitimate within the terms of reference of the problem.

The Outlet offering was written in Qbasic, and used a less sophisticated algorithm. It also ran very much slower. If you want to take a look at the Outlet material, you can find a link on my Useful Links page.

MAIN MENU

DOWNLOAD CODE

ARCHIVES

Site design/maintenance: Dave EllisE-mail me!

Last Updated: January 22nd, 2010.