OpenEuphoria

Re: Goto (Was Re: Open Source)

• Posted by Pete Lomax <petelomax at blu?y?nder.co.uk> Oct 25, 2007
• 874 views

Juergen Luethje wrote:
> > If I didn't make a mistake, this translates to the following Eu program:
<snip>
> I actually would prefer to write the code this way:
<snip>
> Now this is short and pretty clear. Without using GOTO, the structure of
> the program (2 nested loops) is directly visible. So the "nature" of the
> program can be understood immediately and intuitively.
No arguments here, but you did need two attempts even on such a trivial piece of
code 

> Sorry, I do not know anything about COBOL.
Try this then:

-- optimised best-fit algorithm
include sort.e

integer required
	required = 2482
-- expected results with first sizes set:
--Exact 2482:  12 505, 10 425, 7 396, 6 391, 5 388, 1 377
-- expected results with second sizes set:
--Lower 2324: 6 798, 5 734, 3 410, 2 382
--Higher 2520: 5 734, 4 650, 3 410, 2 382, 1 344
	required = 1659
-- expected results with first sizes set:
--Exact 1659: 11 488, 7 396, 6 391, 3 384
-- expected results with second sizes set:
--Lower 1590: 6 798, 3 410, 2 382
--Higher 1728: 5 734, 4 650, 1 344

sequence sizes
--	 sizes = {377,378,384,387,388,391,396,422,424,425,488,505}
	 sizes = {798,344,650,410,382,734}

sequence incset

integer lowbest, lowlevel, highbest, highlevel, worktot, level, item
sequence lowset, highset

procedure display(integer tot, integer level, sequence incset)
integer item
    printf(1,"%d ",tot)
    for i = 1 to level do
	item = incset[i]
	printf(1,"%d %d ",{item,sizes[item]})
    end for
    puts(1,"       key <cr>")
    if getc(0) then end if
    puts(1,"\n")
end procedure
 
function find_combination(integer jumpToDa200)
--
-- this section tries to find a set of sizes which add up to the
-- required amount exactly.
--
    if jumpToDa200 then goto da200 end if
    level = 1
    lowbest = 0
    highbest = 999999999
    item = length(sizes)
    incset=repeat(0,item)
    worktot=0
da100::
    incset[level] = item
    worktot += sizes[item]
    if worktot = required then return 0 end if	      -- found exact fit
    if worktot > required then goto da200 end if	    -- too big
--
-- this set is smaller than required - save it if it is best so far
--
    if worktot > lowbest then
	lowbest = worktot
	lowlevel = level
	lowset = incset
    end if
    if item > 1 then	    -- more to be tested
	item -= 1
	level += 1	    -- leave item in table;
	goto da100
    end if
    goto da300
da200::
--
-- this set is larger than required - save it if it is best so far
--
    if worktot < highbest then
	highbest = worktot
	highlevel = level
	highset = incset
    end if
da300::
--
-- now we need to backtrack;  remove item from running total and look
-- at the next instead.
--
    worktot -= sizes[item]
    if item > 1 then	-- more to be tested
	item -= 1	-- look at next (overwrite item in table)
	goto da100
    end if
--
-- we have exhausted all possibilities at this level; backtrack to
-- a previous level.
--
    incset[level] = 0
    level -= 1
    if level = 0 then return 1 end if		-- all done
    item = incset[level]
    goto da300
 
end function

procedure main()
    sizes=sort(sizes)
    if not find_combination(0) then
	while 1 do
	    display(worktot,level,incset)
--	    if da200() then exit end if
	    if find_combination(1) then exit end if
	end while
    end if
    puts(1,"lower figure ")
    display(lowbest,lowlevel,lowset)
    puts(1,"higher figure ")
    display(highbest,highlevel,highset)
end procedure
main()

I wasn't really keeping track but I think it just took me a shade under an hour
to hack that into something working, then again I know how it works and I've
managed that trick once before, and that I tried and failed many moons ago when I
was still an Eu novice. While messing about I trigered two fatal crashes in Edita
(in re-indent and CtrlBracket) which I fixed (as part of that hour), so at least
it was not a complete and utter waste of time 

One thing I would like to say is that the original of that code was used as part
of the compilation process in a team of ten programmers for many years, so any
restructuring or rewrite would, I felt, carry a strong chance of (re-)introducing
bugs that had been ironed out long ago. OTOH if you translate some code from
language A to language B then a) that is a big enough upheaval anyway, and b) if
you don't test it thoroughly then you know what to expect.

The point that this is the only real nasty I have encountered in 5+ years with
Eu is not a small point either.

Regards,
Pete