Forum

> > Off Topic > Lua Challenges
Forums overviewOff Topic overviewLog in to reply

English Lua Challenges

28 replies
Page
To the start Previous 1 2 Next To the start

old Lua Challenges

Lee
Moderator Off Offline

Quote
This is not a formal Lua thread, rather, it's a collection of programming challenges to help create better scripters. This first challenge will be an extremely difficult one, so please bear with me if you will.

Note: Solutions must be PURELY Lua. There are no other restrictions.

Challenge 1: Write a function that can determine the number of parameters that a function will take. (There are two types of solutions: one that's clever but useless, another that's useful but rather dull)

Test Cases:
1
2
3
4
5
6
7
8
9
10
function num_args(func)
	...
end

--Such that

num_args(function(a,b,c) end) -- Returns 3
num_args(function() end) -- Returns 0
num_args(function(...) end) -- Returns 0+
num_args(function(a,b,c,...) end) -- Returns 3+
edited 1×, last 26.05.10 07:26:01 am

old Re: Lua Challenges

SQ
Moderator Off Offline

Quote
Great, I haven't scripted for months...

I didn't get it right.
My guess was wrong because it should get function(func) arguments.
edited 3×, last 26.05.10 02:22:14 pm

old Re: Lua Challenges

Flacko
User Off Offline

Quote
Wow, this chunkspy library is really big o.o
Edit: I got it, you have to pass a dumped string function to ChunkSpy so you can get the debugged info, even with the parameter's names, I'll do that tomorrow, too tired right now.
edited 1×, last 27.05.10 12:56:56 am

old Re: Lua Challenges

Lee
Moderator Off Offline

Quote
not chunkspy, but yes, the parameter information are in the string dump of the function It should be relatively easy to implement.

old Re: Lua Challenges

YellowBanana
BANNED Off Offline

Quote
In the spoiler lies the answer. Don't click it if you don't have the answer yet

Spoiler >



output:
3+
3

if the function is empty, it somehow doesn't work with me.

Also, using string.dump() is REALLY boring!!
edited 4×, last 27.05.10 03:09:24 pm

old Re: Lua Challenges

Flacko
User Off Offline

Quote
Here I've uploaded a preconfigured version of ChunkSpy:
http://www.mediafire.com/?lgmfmamemvj

And this would be my script:
1
2
3
4
5
6
7
8
9
10
require "chunkspy"

function getLocals(fn)
	local pars = ChunkSpy("",string.dump(fn)).func.locvars
	local rt = #pars
	if pars[#pars].varname == "arg" then -- ...
		rt = (rt-1).."+"
	end
	return rt.."" --Return a string
end

old Re: Lua Challenges

Flacko
User Off Offline

Quote
I guess he hasn't got enough time to come and check, his latest visit was 2 days ago.

old Re: Lua Challenges

Lee
Moderator Off Offline

Quote
Sorry guys, I'm net-locked in China right now so I haven't gotten many chances to get on. I've reviewed all of your solutions and they're all correct

@Yellow: Nice use of a coroutine to wrap around the target function so that the scoping level is propagated, I tried to look for a solution like that at first and gave up after a while T_T. Even though the function must be executed first for the parameters to be determined, it works perfectly for this challenge

@Flacko: Well, I didn't mean using ChunkSpy literally... can't believe that you actually went through the entire library

Here's my solution, it's in the same ballpark as that of Flacko's and about a hundred times less elegant :P, enjoy the mess

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
local function ReadInt(str)
	local t = {}
	for w in str:gmatch(".") do table.insert(t, w:byte()) end
	return t[1]+t[2]*256+t[3]*256*256+t[4]*256*256*256
end

local function num_args(func)
	local ok = pcall(function() string.dump(func) end)
	if not ok then return "?" end
	local dump = string.dump(func)
	--Set up the cursor
	local cursor = 1
	--Skip Header Stuff
	cursor = cursor + 12
	--Skip Source Name
	local offset = ReadInt(dump:sub(cursor, cursor + 4))
	cursor = cursor + 4 + offset + 9
	--Get the Parameters
	local numParams = dump:sub(cursor, cursor + 1):byte()
	cursor = cursor + 1
	--Get the Variable-Args flag (whether there's a ... in the param)
	local varFlag = dump:sub(cursor, cursor + 1):byte()
	cursor = cursor + 1

	local ret = tostring(numParams)
	if varFlag > 1 then ret = ret .. "+" end

	return ret
end

Bonus Challenge: Write a function that returns a list of parameters of a given function.

Challenge #2
Write a function (at.exit) that let's you detect the termination of the Lua runtime (IE: End of execution) such that:

1
2
3
4
5
at.exit(function()
	print "Bob")
end)

print "Hello"

Outputs:
1
2
Hello
Bob

old Re: Lua Challenges

Crazyx
User Off Offline

Quote
YellowBanana pwns and will probably win the challenge. I'm counting on you.

old Re: Lua Challenges

YellowBanana
BANNED Off Offline

Quote
Second challenge:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
at = {}

co = nil

at.exit =   function(func)
				test = newproxy(true)
				test_mt = getmetatable(test)
				test_mt.__gc = function(self)
					coroutine.resume(co)
				end
				co = coroutine.create(func)
			end

at.exit(function() print "Bob" end)

print "hello"
Explanation: garbage-collector metamethod gets called when an userdata object gets destroyed. It is destroyed at the end of lua runtime. So the coroutine is resumed.

Bonus question:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
function hello(a,b,c,...)
     d = 2*2
end

function num_args(funct)
     local co = coroutine.create(funct)
	 local args = {}
     debug.sethook(co,function()
          local i,k = 1, debug.getlocal(co,2,1)
          while k do
               if(k~= "(*temporary)") then
                    if(k~="arg") then
                         table.insert(args,k)
                    else
                         table.insert(args,"...")
                    end
               end
               i = i +1
               k = debug.getlocal(co,2,i)
          end
     end,"c")
     coroutine.resume(co)

	return args
end


for _k,_v in pairs(num_args(hello)) do
	print(_k,_v)
end

edit:
// Lee, are you ever going to post your solutions?
edited 2×, last 19.06.10 08:08:43 pm

old Re: Lua Challenges

Lee
Moderator Off Offline

Quote
oops, I completely forgot to post my solutions, but before I do, since Yellow got the correct solution to the last challenge, I'll post #3 (I know, the paces are a bit slow, blame my being stuck without internet)

Challenge #3: (Easy)
Write an algorithm to remove duplicates from a continuous array (IE: a table with indices 1, 2, 3, 4, ... n)

Challenge #4: (Medium)
Write an algorithm inside a function combinate(len, bins) so that the function will generate every possible unique combination of bins positive integers that add up to len.

IE:
combinate(7, 3) returns {{1, 1, 5}, {1, 2, 4}, {1, 3, 3}, {2, 2, 3}}
combinate(7, 2) returns {{1, 6}, {2, 5}, {3, 4}}

*Note that order does not matter.

Solution to challenges 1 and 2

Common to 1:
1
2
3
4
5
local function ReadInt(str)
	local t = {}
	for w in str:gmatch(".") do table.insert(t, w:byte()) end
	return t[1]+t[2]*256+t[3]*256*256+t[4]*256*256*256
end

1.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
local function num_args(func)
	local ok = pcall(function() string.dump(func) end)
	if not ok then return "?" end
	local dump = string.dump(func)
	--Set up the cursor
	local cursor = 1
	--Skip Header Stuff
	cursor = cursor + 12
	--Skip Source Name
	local offset = ReadInt(dump:sub(cursor, cursor + 4))
	cursor = cursor + 4
	local sourceName = dump:sub(cursor, cursor+offset)
	cursor = cursor + offset
	--Skip Line Defined
	cursor = cursor + 4
	--Skip Last Line Defined
	cursor = cursor + 4
	--Get the Upvalues
	local numUpvalues = dump:sub(cursor, cursor + 1):byte()
	cursor = cursor + 1
	--Get the Parameters
	local numParams = dump:sub(cursor, cursor + 1):byte()
	cursor = cursor + 1
	--Get the Variable-Args flag (whether there's a ... in the param)
	local varFlag = dump:sub(cursor, cursor + 1):byte()
	cursor = cursor + 1

	local ret = tostring(numParams)
	if varFlag > 1 then ret = ret .. "s" end

	return ret
end

1.b
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
local function get_args(func)
	local function _get_args(dump, cursor)
		--Set up the cursor
		if not cursor then
			cursor = 1
			--Skip Header Stuff
			cursor = cursor + 12
		end
		--Skip Source Name
		local offset = ReadInt(dump:sub(cursor, cursor + 4))
		cursor = cursor + 4
		local sourceName = dump:sub(cursor, cursor+offset)
		cursor = cursor + offset
		--Skip Line Defined
		cursor = cursor + 4
		--Skip Last Line Defined
		cursor = cursor + 4
		--Get the Upvalues
		local numUpvalues = dump:sub(cursor, cursor + 1):byte()
		cursor = cursor + 1
		--Get the Parameters
		local numParams = dump:sub(cursor, cursor + 1):byte()
		cursor = cursor + 1
		--Get the Variable-Args flag (whether there's a ... in the param)
		local varFlag = dump:sub(cursor, cursor + 1):byte()
		cursor = cursor + 1
		--Skip the Stacksizes
		cursor = cursor + 1
		--CODE:
		--~Skip the entire code...
		local offset = ReadInt(dump:sub(cursor, cursor + 4))
		cursor = cursor + 4
		cursor = cursor + offset*4
		--CONSTANTS:
		--~Skip the entire constant section...
		local offset = ReadInt(dump:sub(cursor, cursor + 4))
		cursor = cursor + 4
		for i=1,offset do
			local tp = dump:sub(cursor, cursor):byte()
			cursor = cursor + 1
			if tp == 1 then
				--Boolean
				local off = t(dump:sub(cursor, cursor):byte()
				cursor = cursor + 1
			elseif tp == 3 then
				--Number
				local off = ReadInt(dump:sub(cursor, cursor + 8))
				cursor = cursor + 8
			elseif tp == 4 then
				--String
				local off = ReadInt(dump:sub(cursor, cursor + 4))
				cursor = cursor + 4
				--print(dump:sub(cursor, cursor+off))
				cursor = cursor + off
			else
				-- Pass on nil
			end
		end
		--FUNCTIONS:
		--Reget...
		local offset = ReadInt(dump:sub(cursor, cursor + 4))

		cursor = cursor + 4
		for i=1, offset do
			local _
			_, cursor = _get_args(dump, cursor)
		end
		--LINES:
		--~Skip the entire Line section...
		local offset = ReadInt(dump:sub(cursor, cursor + 4))
		cursor = cursor + 4
		cursor = cursor + offset*4
		--LOCALS:
		--~Get Locals
		local offset = ReadInt(dump:sub(cursor, cursor + 4))
		cursor = cursor + 4
		local locals = {}
		local params = {}
		for i=1,offset do
			local off = ReadInt(dump:sub(cursor, cursor + 4))
			cursor = cursor + 4
			local varname = dump:sub(cursor, cursor+off)
			table.insert(locals,varname)
			if i <= numParams then table.insert(params,varname) end
			cursor = cursor + off
			cursor = cursor + 4
			cursor = cursor + 4
		end
		if varFlag > 1 then
			--table.insert(params, "...")
			params['...'] = true
		end
		--UPVALUES:
		--~Get Upvalues
		local offset = ReadInt(dump:sub(cursor, cursor + 4))
		cursor = cursor + 4
		for i=1,offset do
			local off = ReadInt(dump:sub(cursor, cursor + 4))
			cursor = cursor + 4
			cursor = cursor + off
		end
		return params, cursor
	end
	local ok = pcall(function() string.dump(func) end)
	if not ok then return {"..."} end
	local dump = string.dump(func)
	local ret = {_get_args(dump)}
	return ret[1]
end

Which pretty much partially emulates the lua runtime engine... in fact, it's just a few more steps from there to a lua in lua implementation T_T

2.
1
2
3
4
5
6
7
at = {}
function at.exit(fn)
	getmetatable(newproxy(true)).__gc = fn
end

at.exit(function() print "Bob" end)
print "Hello"

the existence of the at.exit function hold partial reference to the anonymous proxy that only terminates when execution terminates.

old Re: Lua Challenges

YellowBanana
BANNED Off Offline

Quote
My solution to 3..
I bet there are faster ways, but this one works.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
values = {1,2,3,3,4,5,5,6,1,2,3,9,5,2,8,3,9,12,15,1,4,5}


function unduplicate(tb)
	table.sort(tb)
	i = 1
	while(i < #tb) do
		if(tb[i+1] == tb[i]) then
			table.remove(tb,i+1)
		else
			i = i + 1
		end
	end
	return tb
end

for i,v in ipairs(unduplicate(values)) do
	print(i,v)
end

4 is pretty hard in my opinion..
I have it in my head how to do it, probably best to use recursion.
edited 1×, last 28.06.10 03:20:36 pm

old Re: Lua Challenges

Lee
Moderator Off Offline

Quote
You got #3, here's my solution:
1
2
3
4
5
function unique(list)
	local set, seen = {},{}
	for i,v in ipairs(list) do table.insert(set, (seen[v] or v) and (not seen[v] or nil) and v);seen[v] = v end
	return set
end

Here is the outstanding challenge

Challenge #4: (Medium)
Write an algorithm inside a function combinate(len, bins) so that the function will generate every possible unique combination of bins positive integers that add up to len.

old Re: Lua Challenges

YellowBanana
BANNED Off Offline

Quote
Here's my solution for #4 with 3 bins.. I'm working on a better one tho

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
function combinate(len,bins)
	local solutions= {}
	for i = len - bins+1,math.ceil(len/3),-1 do
		for j = len - i,1,-1 do
			for k = len - i - j, 1,-1 do
				local sol = {i,j,k}
				if(i+j+k == len and i>=j and j>=k) then
					table.insert(solutions,sol)
				end
			end
		end
	end

	for _,t in ipairs(solutions) do
		print("{"..t[1]..", "..t[2].." ,"..t[3].."}")
	end
end

combinate(17,3)

Anyway, is your #3 solution the same as this?

1
2
3
4
5
6
7
8
9
10
11
function unique2(list)
	local set,seen = {},{}

	for i,v in ipairs(list) do
		if seen[v] == nil then
			table.insert(set,v)		
			seen[v] = v
		end
	end
	return set
end
edited 2×, last 30.06.10 02:11:36 pm

old Re: Lua Challenges

Lee
Moderator Off Offline

Quote
The problem with using this general form of loop is that it cannot dynamically allocate for larger bins without you having to write more for loops.

There's a way to do this directly with a single for-loop and a little bit of modulus math and a recursive form that's a lot more straight forward.

Bonus to #4: Write this algorithm in both recursive and closed form.

Hint 1: Think about a tree with three levels

Hint 2: Write function f(i, n) -> {a,b,c,..n} where f(i,10) returns every digit of i (You might want to google for a binary dissector)

@#3: Delete the else keyword and it is

old Re: Lua Challenges

YellowBanana
BANNED Off Offline

Quote
anyway, this is 1 solution..
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
function combinate(len,bins)
	solutions = {}
	max = len-bins+2
	local sol = initArray(bins,1)
	while(sol[bins]~=max) do
		sol[1] = sol[1] + 1
		for i=1,bins-1 do
			if(sol[i]==max) then
				sol[i+1] = sol[i+1] + 1
				sol[i] = 1
			end
		end

		local sum = 0
		for v = 1, bins do
			if(v == bins) then
				sum = sum + sol[v]
				if(sum == len) then
					table.insert(solutions,table.copy(sol))
				end
			elseif(sol[v] < sol[v+1]) then
				break
			else
				sum = sum + sol[v]
			end
		end

	end

	return solutions
end

Don't quite understand what you mean with the hints though.. The second hint f(337,10) would return {3,3,7} ?

and f(337,2) would return {1,0,1,0,1,0,0,0,1} ?

old Re: Lua Challenges

Lee
Moderator Off Offline

Quote
That's good, here are my iterative solutions:

Commons
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
function table.find(t, o)
	for k, v in pairs(t) do if v == o then return k end end
end

function log(x, b)
	return math.log(x)/math.log(b)
end

function f(x,n)
	local digits = {}
	for i=math.floor(log(x,n)), 0, -1 do
		table.insert(digits, math.floor(x/math.pow(n, i)))
		x=x%math.pow(n,i)
	end
	return digits
end

function uniquep(list)
	local set, seen, s = {},{}, ""
	for i,v in ipairs(list) do
		if type(v) == "table" then table.sort(v);s=table.concat(v) end
		table.insert(set, (seen[s] or v) and (not seen[s] or nil) and v)
		seen[s] = v
	end
	return set
end

local function sum(list)
	local s = 0
	for _,v in ipairs(list) do s=s+v end
	return s
end

Standard
1
2
3
4
5
6
7
8
9
10
11
12
function combinate1(len, bins)
	local stack = {}
	for i=math.pow(len, bins-1),math.pow(len,bins)-1 do
		local this = f(i,len)
		if sum(this) == len then
			if not table.find(this, 0) then
				table.insert(stack, this)
			end
		end
	end
	return uniquep(stack)
end

Optimized
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
function combinate2(len, bins)
	local first
	local cursor = math.pow(len,bins-1)
	while not first do
		local this = f(cursor, len)
		cursor = cursor + 1
		if sum(this) == len then
			first = cursor-1
		end
	end
	local stack = {}
	for i = first, math.pow(len,bins)-1, len-1 do
		local this = f(i,len)
		if sum(this) == len and not table.find(this, 0) then
			table.insert(stack, this)
		end
	end
	return uniquep(stack)
end

Function f is basically one that can create a base n representation from a base 10 number which we can poll from a range of index to generate every possible permutations of bins numbers.

Outstanding Challenges:
Bonus Challenge #4: (Medium)
Write a recursive algorithm inside a function combinate(len, bins) so that the function will generate every possible unique combination of bins positive integers that add up to len.

New Challenges
Challenge #5: (Easy)
Write a function sigmam(n,b) that returns the sum of all multiples of b less than or equal to n so that sigmam(10,2) = 2+4+6+8+10 = 30

Challenge #5.b: (Medium)
Rewrite the algorithm in challenge #5 to one without any iterations nor recursive calls (IE: as a flat polynomial)
edited 1×, last 01.07.10 01:29:01 pm

old Re: Lua Challenges

YellowBanana
BANNED Off Offline

Quote
#5a

1
2
3
4
5
function sigmam(n,b)
	local sum=0
	for i =b,n,b do sum = sum +i end
	return sum
end

#5b

1
2
3
function sigmam2(n,b)
	return 0.5*b*math.pow((math.floor(n/b) +1),2) - 0.5*b*(math.floor(n/b) +1)
end


and a fast approximation:
1
2
3
function sigmam(n,b)
	return 0.5*math.floor(n/b)*(n+b)
end
edited 4×, last 01.07.10 03:15:59 pm
To the start Previous 1 2 Next To the start
Log in to replyOff Topic overviewForums overview