THE PUZZLET PAGE

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

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 for i of 0 to 255, which correspond in binary to 00000000 to 11111111.  The denary value of i is passed to the function Binary() , along with the parameter 8.  This is instructing the function to return the binary representation of i , 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 variable bin$ .

Let's take a typical bin$ value returned, "00010011" corresponding to an i value of 19.  This is used by the subroutine MakeCheckString() now to convert our standard number 123456789.  Wherever it sees a 1 in bin$ 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 in check$ .

This value is now processed by the subroutine Totalise() , 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 called sign$, corresponding to the pattern of minuses and pluses in the little table on the right.  It uses our old friend Binary() to do this, passing in the current value of a local iterator for count and the variable count itself 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 of count will produce a sequence of alterations to check$, as shown inset.
 
The next bit is the last!  These strings are passed one at a time to the subroutine Evaluate() 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 of check$.


The binary() function works by using the schoolboy approach.
  1. Divide d by 2.
  2. If there’s a remainder, save it as “1”.
  3. If there’s no remainder, save it as “0”.
  4. If d equals zero, go to step 5, otherwise repeat steps 1 to 4 again.
  5. If the string of 1’s and 0’s is of lesser length than pad, add 0’s to make the lengths the same.
  6. Return the string thus formed – it’s the required  binary string.
bin$ will contain an 8-bit binary number.   The subroutine MakeCheckString() generates “123456789” and, after every integer generated, inserts a plus sign if the corresponding digit in bin$ 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  variable count is used to hold the number of pluses or minuses that will eventually be inserted into the “123456789”.  In the subroutine Totalise(), 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 subroutine Evaluate().

Evaluate() will set about  processing checks$ , which was punctuated by plus and minus signs in the subroutine Totalise() .  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. 

Puzzlet_002_screenshot


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 Ellis E-mail me!
Last Updated: January 22nd, 2010.