Re: rosettacode 500 milestone passed
- Posted by Spock Mar 16, 2017
- 1709 views
petelomax said...
I look forward to giving it a spin. Seems like you've got a bit of time to polish it though, rosettacode is down and the last time it was off for over a week.
Pete
Ok. It is in Orac form but the conversion is trivial to Euphoria:
~ means length()
. means []
The output is at the unit level since I couldn't be bothered subtotalling..
Spock
include sorting.e include seq.e seq good, bad int WEIGHT = 400 int compares = 0 int iter = 0 procedure init() compares = 0 iter = 0 -- the raw data seq s = -- {name, weight, value, pieces} { { "map", 9, 150, 1}, { "compass", 13, 35, 1}, { "sandwich", 50, 60, 2}, { "glucose", 15, 60, 2}, { "tin", 68, 45, 3}, { "banana", 27, 60, 3}, { "apple", 39, 40, 3}, { "cheese", 23, 30, 1}, { "beer", 52, 10, 3}, { "suntan cream", 11, 70, 1}, { "water", 153, 200, 2}, { "camera", 32, 30, 1}, { "T-shirt", 24, 15, 2}, { "trousers", 48, 10, 2}, { "umbrella", 73, 40, 1}, { "waterproof trousers", 42, 70, 1}, { "waterproof overclothes", 43, 75, 1}, { "note-case", 22, 80, 1}, { "sunglasses", 7, 20, 1}, { "towel", 18, 12, 2}, { "socks", 4, 50, 1}, { "book", 30, 10, 2} } -- reform seq t = {} for i = 1 to ~s do -- unpack seq q = s.i seq name = q.1 int w = q.2 int v = q.3 int n = q.4 -- set t &= repeat({name, w, v, w/v}, n) end for -- sort t = sort(t, 4) -- split good = {} bad = {} w = 0 for i = 1 to ~ t do w += t.i.2 if w > WEIGHT then good = t[1 to i-1] bad = t[i to $] ?{~good, ~bad} return end if end for -- special case all on good list good = t end procedure function spare() -- scan good list and work out how much spare space there is -- init int w = 0 -- loop for i = 1 to ~good do w += good.i.2 end for -- spare int spare = WEIGHT - w assert spare >= 0 -- exit return spare end function function can_swap(int a, int b, int g) -- init compares += 1 -- bad - 1 or 2 parameters int wbad = bad.a.2 int vbad = bad.a.3 if b then wbad += bad.b.2 vbad += bad.b.3 end if -- good int wgood = good.g.2 int vgood = good.g.3 -- compare return wbad <= wgood+spare() and vbad > vgood end function function swap_single() -- loop over BAD for i = 1 to ~bad do -- loop over GOOD for j = 1 to ~good do -- compare if can_swap(i, 0, j) then seq t = bad.i bad.i = good.j good.j = t return 1 end if end for end for return 0 end function function swap_double() -- loop over BAD for a = 1 to ~bad-1 do -- loop 2 over BAD for b = a+1 to ~bad do -- loop over GOOD for g = 1 to ~good do -- compare if can_swap(a, b, g) then seq t1 = bad.a seq t2 = bad.b bad = bad[1 to a-1] & bad[a+1 to b-1] & bad[b+1 to $] & {good.g} good = good[1 to g-1] & good[g+1 to $] & {t1, t2} return 1 end if end for end for end for return 0 end function procedure run() -- init init() -- perform algorithm atom t1 = time() while swap_single() or swap_double() do iter += 1 end while puts(1, "top-level iterations, element compares :") ? {iter, compares} ? time() - t1 -- show results int weight = 0, value = 0 for i = 1 to ~good do weight += good.i.2 value += good.i.3 seq name = good.i.1 printf(1, "%d %d %s\n", {weight, value,name} ) end for ? 9/0 end procedure run()