OpenEuphoria

Re: Computer Language Shootout

• Posted by Jason Gade <jaygade at yahoo.com> Jul 13, 2005
• 576 views

Here is the entry for binary trees.  I pretty much copied the C/C#
implementation almost verbatim.  I don't know if I can make it any more
"Euphoria" though.

I also used Derek's ackermann.ex as a template.

The good news is it worked right the first time (pats self on back).

-- The Computer Language Shootout Benchmarks
--  http://shootout.alioth.debian.org/
-- 
--  by Jason Gade
--  run: exu binary-trees.ex N

include get.e 



constant LEFT =  1,
         RIGHT = 2,
         ITEM =  3
         
constant NULL = {} 



function ItemCheck(sequence tree)

    if equal(tree[LEFT], NULL) then 
        return tree[ITEM]
    else 
        return tree[ITEM] + ItemCheck(tree[LEFT]) - ItemCheck(tree[RIGHT])

    end if

end function -- ItemCheck



function BottomUpTree(atom item, integer depth)

    if depth > 0 then
        return {BottomUpTree(2 * item - 1, depth - 1), 
                BottomUpTree(2 * item, depth - 1),
                item}
    else
        return {NULL, NULL, item}
    
    end if
end function -- BottomUpTree



procedure main(sequence argv)

    atom iterations, check
    integer N, minDepth, maxDepth, stretchDepth
    sequence v, stretchTree, longLivedTree, tempTree

    if length(argv) > 2 then
        v = value(argv[3])
        N = v[2]
    else
        N = 0
    end if

    minDepth = 4

    if (minDepth + 2) > N then
        maxDepth = minDepth + 2
    else
        maxDepth = N
    end if

    stretchDepth = maxDepth + 1

    stretchTree = BottomUpTree(0, stretchDepth)
    printf(1, "stretch tree of depth %d\t  check: %d\n",
              {stretchDepth,
              ItemCheck(stretchTree)})

    stretchTree = {} 

    longLivedTree = BottomUpTree(0, maxDepth)

    for depth = minDepth to maxDepth by 2 do

       iterations = power(2, maxDepth - depth + minDepth)

       check = 0

       for i = 1 to iterations do

           tempTree = BottomUpTree(i, depth)
           check += ItemCheck(tempTree)
           tempTree = {}

           tempTree = BottomUpTree(-i, depth)
           check += ItemCheck(tempTree)
           tempTree = {}

       end for -- i

        printf(1, "%d\t  trees of depth %d\t  check: %d\n",
                  {iterations * 2, depth, check })

    end for -- depth

    printf(1, "long lived tree of depth %d\t  check: %d\n",
              {maxDepth, ItemCheck(longLivedTree)})

end procedure -- main



main(command_line())
-- end binary-trees.ex

The problem is sometimes I have a more difficult time understanding the
specification than I do the code.  Which is weird because I am not very good at
reading source code, especially that which is basically uncommented like the
shootout code is.

Are real-world specifications this vague?

I remember Derek's contest from last year, the specifications were very clear
with the exception of hashing (no pun) out some specifics on some details.

=====================================
Too many freaks, not enough circuses.

j.