15 minute code challenge - for fun

[togFox]

Hmmm. Has more utility. How would you make ws and wd optional so if those parameters were not provided they would default to '1'?

[darkfrei]

Hmmm. Has more utility. How would you make ws and wd optional so if those parameters were not provided they would default to '1'?

Code: Select all

function somefunction (ws, wd)
	ws = ws or 1
	wd = wd or 1 -- if wd is not false (nil is false too) then it's wd, otherwise wd is 1
	return ws, wd
end

Code: Select all

function otherfunction (tabl)
	local ws = tabl.ws or 1
	local wd = tabl.wd or 1 -- if tabl.wd is not false (nil is false too) then wd is tabl.wd, otherwise wd is 1
	return ws, wd
end

ws, wd = otherfunction {ws = 10} -- wd is nil

It's very useful for maps:

Code: Select all

map = {}
for y = 1, 10 do
	for x = 1, 10 do
		map[x] = map[x] or {} -- new table map[x] if map[x] not exists
		map[x][y] = math.random()
	end
end

[pgimeno]

The next one: ws = 3, but wd = 1: the diagonal movement is cheaper and it has higher priority for movement.

Hm, tricky. You have to consider map dimensions. You only need to go straight if, when colouring the map with chequered (alternating black and white) colours, you need to change colours; otherwise you do bishop movements. You need to change colours if (1) one of the map dimensions is 1 (then you need to change colours at every step) or (2) the start and end are in different colours (then you have to do it just once).

Code: Select all

local function shortestDistance(x1, y1, x2, y2, ws, wd)
  local dx = math.abs(x1 - x2)
  local dy = math.abs(y1 - y2)
  if map.sizeX == 1 or map.sizeY == 1 then
    return (dx + dy) * ws -- edited - forgot *ws
  end
  local straight = (dx + dy) % 2 -- number of steps necessary in a straight direction
  return straight * ws + (math.max(dx, dy) - straight) * wd
end

Finding the threshold for ws >> wd and joining both functions so that the result is always correct regardless of weights, is left as an exercise to the reader

(edit: oops, the threshold is 1, my bad)

By the way, wd=17 and ws=12 are much closer than 14 and 10 to the euclidean path length.

[darkfrei]

By the way, 17 and 12 are much closer than 14 and 10 to the euclidean path length.

You are right:

Code: Select all

local t, d, s, e = math.sqrt(2), 1, 1, 1

function check_solution (d, s, t)
	if math.abs (d/s-t) < e then
		e = math.abs (d/s-t)
		print ('better solution: d=' .. d .. ' s=' .. s .. ' error:' .. e ..  ' 1/'.. math.floor(1/e+0.5))
	end
end

for i = 1, 100000 do
	check_solution (d, s, t)
	if d/s > t then s = s + 1 else d = d + 1 end
end

Result:

better solution: d=1 s=1 error:0.4142135623731 1/2
better solution: d=3 s=2 error:0.085786437626905 1/12
better solution: d=4 s=3 error:0.080880229039762 1/12
better solution: d=7 s=5 error:0.014213562373095 1/70
better solution: d=17 s=12 error:0.0024531042935716 1/408
better solution: d=24 s=17 error:0.0024488564907421 1/408
better solution: d=41 s=29 error:0.00042045892481934 1/2378
better solution: d=99 s=70 error:7.2151912619223e-005 1/13860
better solution: d=140 s=99 error:7.2148231681002e-005 1/13860
better solution: d=239 s=169 error:1.2378941142588e-005 1/80782
better solution: d=577 s=408 error:2.1239014147412e-006 1/470832
better solution: d=816 s=577 error:2.1238982250704e-006 1/470832
better solution: d=1393 s=985 error:3.6440355200007e-007 1/2744210
better solution: d=3363 s=2378 error:6.252177442434e-008 1/15994428
better solution: d=4756 s=3363 error:6.2521771981849e-008 1/15994428
better solution: d=8119 s=5741 error:1.0727040367087e-008 1/93222358
better solution: d=19601 s=13860 error:1.8404691104479e-009 1/543339736
better solution: d=47321 s=33461 error:3.157747396898e-010 1/3166814423

It's interesting, that 3, 17, 99, 577, 3363 are in d and s for the next best solution, but not much better solution.

[pgimeno]

It's interesting, that 3, 17, 99, 577, 3363 are in d and s for the next best solution, but not much better solution.

There are mathematical reasons Notice that in all cases where that happens, the next d is twice the previous s.

If d/s is an approximation to the square root of 2, then 2s/d is another approximation of the same order, because 2s/d can be rewritten as 2/(d/s), and since 2/sqrt(2) = sqrt(2), if e is an approximation to sqrt(2), 2/e is approximately equal to e.

In the cases where the rule you've found fails, 2s/d is still very close to d/s, just with a slightly bigger error and therefore a worse approximation. For example, 41/29 = sqrt(2) - 0.0004204589... and 58/41 = sqrt(2) + 0.000420583968...; the error is only slightly bigger in this case (and in all cases, the opposite sign).

[Gunroar:Cannon()]

pgimeno in his element