Re: rosettacode 500 milestone passed

new topic     » goto parent     » topic index » view thread      » older message » newer message
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() 
new topic     » goto parent     » topic index » view thread      » older message » newer message

Search



Quick Links

User menu

Not signed in.

Misc Menu