Five programming problems every Software Engineer should be able to solve in less than 1 hour

[Mark Waddingham]

> In any case, I thought they were interesting so I gave it a shot. I
> finished in something like 40 minutes, but I think some of my solutions 
> are
> more expedient than I would like.

Indeed - the problems themselves are quite interesting - here are my 
solutions:

---- PROBLEM 1

function problem1_for pList
    local tIndex
    get 0
    repeat with tIndex = 1 to the number of items in pList
       add item tIndex of pList to it
    end repeat
    return it
end problem1_for

function problem1_while pList
    local tIndex
    put 1 into tIndex
    get 0
    repeat while tIndex <= the number of items in pList
       add item tIndex of pList to it
       add 1 to tIndex
    end repeat
    return it
end problem1_while

function problem1_recurse pList
    if the number of items in pList is 1 then
       return item 1 of pList
    end if
    return item 1 of pList + problem1_recurse(item 2 to -1 of pList)
end problem1_recurse

---- PROBLEM 2

function problem2 pListA, pListB
    get empty
    repeat while pListA is not empty or pListB is not empty
       if pListA is not empty then
          put item 1 of pListA & comma after it
          delete item 1 of pListA
       end if
       if pListB is not empty then
          put item 1 of pListB & comma after it
          delete item 1 of pListB
       end if
    end repeat
    delete the last char of it
    return it
end problem2

---- PROBLEM 3
----   This would be trivial with arbitrary precision integers but
----   a simple 'high-school addition' function takes care of that.

function problem3
    get 0 & return & 1 & return
    repeat until the number of lines in it is 100
       put largeAdd(line -2 of it, line -1 of it) & return after it
    end repeat
    delete the last char of it
    return it
end problem3

function largeAdd pLeft, pRight
    local tLength
    put max(the number of chars in pLeft, the number of chars in pRight) 
into tLength
    put format("%0*s", tLength, pLeft) into pLeft
    put format("%0*s", tLength, pRight) into pRight

    local tIndex, tCarry, tResult
    put 0 into tCarry
    put empty into tResult
    repeat with tIndex = tLength down to 1
       get char tIndex of pLeft + char tIndex of pRight + tCarry
       put it div 10 into tCarry
       put it mod 10 before tResult
    end repeat
    if tCarry is not 0 then
       put tCarry before tResult
    end if

    return tResult
end largeAdd

---- PROBLEM 4
----   I must confess I found this one trickier than Problem 5. The
----   tricky case reduces to sets of integers with a common prefix
----   and sorting those into the right order. My solution pads with
----   the leading digit, then sorts preferring originally shorter
----   before longer (it relies on the fact 'sort' is stable in LC).

function problem4_pad pItem, pLength
    repeat until the length of pItem is pLength
       put char 1 of pItem after pItem
    end repeat
    return pItem
end problem4_pad

function problem4 pList
    local tLength
    put 0 into tLength
    repeat for each item tItem in pList
       put max(the number of chars in tItem, tLength) into tLength
    end repeat
    sort items of pList ascending numeric by the number of chars in each
    sort items of pList descending text by problem4_pad(each, tLength)
    replace comma with empty in pList
    return pList
end problem4

---- PROBLEM 5
----   At first sight this one seems 'scary' but in actual fact the
----   number of combinations is actually quite small (3^8) and you
----   can get them by counting from 0 to 3^8 in ternery and padding
----   the result to 8 digits. I then use 0 for no sign, 1 for + and
----   2 for -. Having 'value' makes checking the sums trivial.

function problem5
    local tResults
    repeat with i = 0 to 3^8
       local tScheme, tSum
       put empty into tSum
       put format("%08s", baseConvert(i, 10, 3)) into tScheme
       repeat with j = 1 to 8
          put j after tSum
          switch char j of tScheme
             case "0"
                break
             case "1"
                put "+" after tSum
                break
             case "2"
                put "-" after tSum
                break
          end switch
       end repeat
       put "9" after tSum
       if value(tSum) is 100 then
          put tSum & return after tResults
       end if
    end repeat
    return tResults
end problem5

-- 
Mark Waddingham ~ mark at livecode.com ~ http://www.livecode.com/
LiveCode: Everyone can create apps