15 minute code challenge - for fun

General discussion about LÖVE, Lua, game development, puns, and unicorns.
User avatar
togFox
Party member
Posts: 770
Joined: Sat Jan 30, 2021 9:46 am
Location: Brisbane, Oztralia

Re: 15 minute code challenge - for fun

Post by 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'?
Current project:
https://togfox.itch.io/backyard-gridiron-manager
American football manager/sim game - build and manage a roster and win season after season
User avatar
darkfrei
Party member
Posts: 1169
Joined: Sat Feb 08, 2020 11:09 pm

Re: 15 minute code challenge - for fun

Post by darkfrei »

togFox wrote: Wed Jun 23, 2021 10:14 am 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
:awesome: in Lua we Löve
:awesome: Platformer Guide
:awesome: freebies
User avatar
pgimeno
Party member
Posts: 3544
Joined: Sun Oct 18, 2015 2:58 pm

Re: 15 minute code challenge - for fun

Post by pgimeno »

darkfrei wrote: Wed Jun 23, 2021 10:14 am 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.
User avatar
darkfrei
Party member
Posts: 1169
Joined: Sat Feb 08, 2020 11:09 pm

Re: 15 minute code challenge - for fun

Post by darkfrei »

pgimeno wrote: Wed Jun 23, 2021 11:48 am 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.
:awesome: in Lua we Löve
:awesome: Platformer Guide
:awesome: freebies
User avatar
pgimeno
Party member
Posts: 3544
Joined: Sun Oct 18, 2015 2:58 pm

Re: 15 minute code challenge - for fun

Post by pgimeno »

darkfrei wrote: Wed Jun 23, 2021 12:12 pm 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).
User avatar
Gunroar:Cannon()
Party member
Posts: 1085
Joined: Thu Dec 10, 2020 1:57 am

Re: 15 minute code challenge - for fun

Post by Gunroar:Cannon() »

pgimeno in his element :)
The risk I took was calculated,
but man, am I bad at math.

-How to be saved and born again :huh:
Post Reply

Who is online

Users browsing this forum: Google [Bot] and 44 guests