### forum-msg-id-130855-edit

Original date:2017-03-16 20:56:00 Edited by: Spock Subject: Re: rosettacode 500 milestone passed

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 []

Spock

```include sorting.e
include seq.e

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 = {}
w = 0
for i = 1 to ~ t do
w += t.i.2
if w > WEIGHT then
good = t[1 to i-1]
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
if b then
end if

-- good
int wgood = good.g.2
int vgood = good.g.3

-- compare

end function

function swap_single()

for i = 1 to ~bad do

-- loop over GOOD
for j = 1 to ~good do

-- compare
if can_swap(i, 0, j) then
good.j = t
return 1
end if

end for

end for

return 0

end function

function swap_double()

for a = 1 to ~bad-1 do

for b = a+1 to ~bad do

-- loop over GOOD
for g = 1 to ~good do

-- compare
if can_swap(a, b, g) then
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()
```