Forum

Off Topic

Lua Challenges

Forums overview Off Topic overview Log in to reply

Lua Challenges

28 replies

1 2

Re: Lua Challenges

Lee
Moderator Off

Offline

02.07.10 07:17:03 am

You got them both correct. Basically we refactor the algorithm into one with the minimum number of iterations

b * sigma to floor(n/b)

so that the expression:

4 + 8 + 12 + 16 + ... 100
becomes 4(1 + 2 + 3 + 4 + ... 25)

Note that arithmetic sum can be re-expressed as n(n+1)/2

1
2
3
4

function sigmam(n, b)
	local function sigma(n) return n*(n+1)/2 end
	return b*sigma(math.floor(n/b))
end

New Challenges:

Challenge 6: (Easy-Medium)
Write a function sigmams(n,ms) that returns the sum of all multiples of at least one number in the table ms so that:

sigmams(10,{2,3}) = 2 + 3 + 4 + 6 + 8 + 9 + 10

Hint: Exclude 6 in the above case

Challenge 7: (Easy-Medium)
Assume that we have a recursive function k(n) that generates a set of numbers with the following rule:

k(1) = 1
k(n) = n, k(n/2) if n is even
k(n) = n, k(3n+1) if n is odd

so that the first 5 terms of the k-series is as follows:

k(1) = 1
k(2) = 2 1
k(3) = 3 10 5 16 8 4 2 1
k(4) = 4 2 1
k(5) = 5 16 8 4 2 1

Assume that for every n in the set of positive integers, k(n) returns a finite set that terminates with 1, write a function maxCycle(a,b) that finds the index n between a and b (a<=n<=b) for which k(n) contains the greatest number of elements (the longest cycle)

Challenge #8: (Easy)
Write a function Windows() that returns true if the OS is not a *nix derivative (Linux, Symbian, iOS, Mac, Debian, etc) and false if it is.

edited 1×, last 02.07.10 07:30:25 am

Re: Lua Challenges

archmage
User Off

Offline

02.07.10 07:41:08 am

Challenge #8

1
2
3
4
5
6
7

function isWindows ()
	if ( os.getenv("OS") == "Windows_NT" ) then
		return true
	else
		return false
	end
end

Re: Lua Challenges

Lee
Moderator Off

Offline

02.07.10 08:48:35 am

@Dark Byte:
You're almost correct, however the code will fail on a pure DOS environment (Non windows and non *nix), but for the record, your isWindows would be the best way to check if the running thread is hosted inside a Win OS.

Re: Lua Challenges

Flacko
User Off

Offline

02.07.10 09:16:59 am

#6:
I think this is what you want

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

function sigmams(n,ms)

	local t = {}
	
	local function find(v)
		for i=1, #t do
			if(t[i] == v) then return true end
		end
		return false
	end
	
	for i=1, #ms do
		local mult = 1
		while(true) do
			if(ms[i] <= n) then
			
				if(ms[i]*mult > n) then	break end
			
				if find(ms[i]*mult) == false then
					table.insert(t,ms[i]*mult)
				end
				mult = mult+1
			end
		end
	end
	
	local sum = 0
	for i=1, #t do
		sum = sum+t[i]
	end
	
	return sum
end

Re: Lua Challenges

YellowBanana
BANNED Off

Offline

18.07.10 01:57:11 am

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

function sigmam(n,b)
	local numbers = {}
	local sum = 0

	local 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

	if type(b) == "table" then
		for i,v in ipairs(b) do
			for _i = v,n,v do
				table.insert(numbers,_i)
			end
		end
	end

	for i,v in ipairs(unique(numbers)) do
		sum = sum + v
	end

	return sum
end

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

tabs = {}
function k(n)

	table.insert(tabs,n)
	if(n == 1) then
		return tabs
	elseif(isEven(n)) then
		return k(n/2)
	else
		return k(3*n+1)
	end

end

--table.foreach(k(3),print)

function maxCycle(a,b)

	local function findMax(a)
		local mi = 1			--index of max value
		local m = a[mi]			--max value
		for i, val in ipairs(a) do      --can use pairs() as well, ipairs() indicates an array-like table
			if val > m then
				mi = i
				m = val
			end
		end
		return m, mi	--neat feature of lua, can return multiple values
	end

	local vals = {}

	for i=a,b do
		tabs = {}
		local nums = #k(i)
		vals[i] = nums
	end

	numElem,maxNum = findMax(vals)

	return maxNum
end

print(maxCycle(1,5))

function isWindows() return not not os.execute("ls") end

I have a Lua challenge for everyone.
Check if a number is a palindromic number.
Examples of palindromic numbers are 353, 91219, 36963, 999999.
Write a function isPalindromic(number) that returns true when it is palindromic, and false when it's not.

edited 3×, last 02.08.10 04:51:21 pm

Re: Lua Challenges

Flacko
User Off

Offline

02.08.10 05:19:52 pm

You can tostring() the number and check for the first and last characters but I'm doing it the hard way:

1
2
3
4
5
6
7
8
9

function ispal(n)
	local last = math.floor(n%10)
	local first
	while n>9 do
		n = math.floor(n/10)
	end
	first = n
	return first==last
end

Re: Lua Challenges

Lee
Moderator Off

Offline

02.08.10 07:03:04 pm

Numerically, the following is the most asymptotically optimized version that I've been able to create with running time T(n) = THETA(log(n)log(log(n))) and with a bit more hassle, it can be abstracted down to merely THETA(log(n)). Note that this is probably not the fastest implementation absolutely as it requires a lot of numerical computation, but since these are constant time, the growth rate of the function is low with regards to the size of the input.

1
2
3
4
5
6
7
8
9
10
11

function isPalindromic(k)
	if k < 10 then return true end
	local n = math.floor(math.log(k)/math.log(10))+1;local h = math.floor(n/2)
	local a,b = math.floor(k/10^(h+n%2)),k%10^h
	if a%10 == math.floor(b/10^(h-1)) then 
		a, b, n = math.floor(a/10), b%10^(h-1), n-2
		return isPalindromic((a*10^math.floor(n/2))+b)
	else
		return false
	end
end

Sadly, floating precision is lost when the input size is above 1000000001000000001 thus the result will be inaccurate. This ironically cancels out any advantages that it may have held from a lower rate of growth.

Re: Lua Challenges

YellowBanana
BANNED Off

Offline

03.08.10 06:45:34 pm

I had two solutions:

function isPalindromic(k) return tostring(k) == tostring(k):reverse() end

Which i doubt is very fast because of the == operator on strings, and the tostring function.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

function isPalindromic(k)	
	local function numberToTable(num)
		local i = 0
		local factors = {}

		while(num >0) do
			i = i +1
			local fac = num % 10
			num = math.floor(num / 10)
			table.insert(factors,fac)
		end

		return factors
	end
	
	nums = numberToTable(k)

	for i=1,math.floor(#nums / 2) do
		if(nums[i] ~= nums[#nums - i +1]) then
			return false
		end
	end
	return true
end

Second one, probably faster.

Anyway, i was wondering if there is a way to make the increment operators in C work in Lua, in a non-hackish way.

d++ would mean d = d + 1
d+=5 would mean d = d + 5 in lua.

edited 1×, last 03.08.10 10:42:12 pm

Re: Lua Challenges

Flacko
User Off

Offline

03.08.10 09:15:02 pm

Oh, in that case mine is probably wrong because I just checked the first and last numbers Dx. Since I'm not in my PC this is my second attempt:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

function isPal(n)
	local t = {}
	local a = n

	while a>0 do
		table.insert(t,a%10)
		a = math.floor(a/10)
	end

	local offset = math.ceil(#t/2)

	for a=1, math.floor(#t/2) do
		if t[i] ~=  t[i+b] then
			return false
		end
	end
	return true
end

But I think the way that will require less processing will be the first one you posted, since all you need to turn a number into a string is to add it 48 to get the ASCII code and a simple loop comparing each character is a lot faster than dividing (which is a loop of substracions, just like multiplication is a loop of additions in 32-bit machines), adding stuff to a table, etc.

1 2