Forum

> > CS2D > Scripts > The Ultimate Lua Challenge
Forums overviewCS2D overview Scripts overviewLog in to reply

English The Ultimate Lua Challenge

89 replies
Page
To the start Previous 1 2 3 4 5 Next To the start

old important The Ultimate Lua Challenge

Lee
Moderator Off Offline

Quote
Work through these problem sets and you will earn your title as a Lua Programmer. Post your scripts to http://cs2d.pastebin.com/ and then post the links here once you're through. Please include your name in your submission.

There will be 100 or more problems in total.

∗ First 10 problems:
More >


∗ Problems 11 - 20: Number Theory

• 11. Determine if a number is a prime. (Floor floats into integers if necessary).

• 12. Determine the greatest common divisor of two positive integer numbers.

• 13. Determine whether two positive integer numbers are coprime.

• 14. Calculate Euler's totient function phi(m) such that phi(m) returns the number of integers less than m that are coprime to m. (IE: phi(a prime number) will intuitively be m-1 as only 1 is both not coprime to m and less than m. http://en.wikipedia.org/wiki/Totient_function

• 15. Determine the prime factors of a given positive integer. (Such that all elements of this list are primes and their product is the said integer, prime_factors(12) = 2,2,3)

• 16. Find the unique prime factors of a given positive integer as well as the number of duplicates (see 15 and 10)

• 17. Calculate phi(10090), aka rewrite the euler totient function so that it's time complexity is polynomial
hint: use 16 and IMG:https://upload.wikimedia.org/math/3/3/4/3341e604a3ee2420a86af3a98f113510.png

where p[i] are the prime factors and k[i] are the number of duplicates (or multiplicity)

• 18. Construct a list of all prime numbers below a certain limit n. For example, gen(10) = 2,3,5,7

• 19. Prove Goldbach's Conjecture up to 1000.
http://en.wikipedia.org/wiki/Goldbach%27s_conjecture

• 20. Challenge Problem: Create a program that translates numbers/integers into English words. For example, pronounce(10) = "ten", 103 = one hundred and three, 103450 = one hundred three thousand four hundred and fifty (no and in the 103 thousand part), 34 = thirty-four. See http://en.wikipedia.org/wiki/English_numerals

∗ Problems 21 - 30: Even more Number Theory

• 21. Assuming that you have the solution to problem 12, compute 6^6002 mod 77 using Euler's Theorem, namely that given a^n mod m, if a is coprime to m (or gcd(a, m) = 1), then it is suffice to compute only a^(n mod phi(m)) mod m, where phi is the euler totient function.

• 22. Write a fast modular exponentiation function to calculate 3^222 mod 15 (note that 3 and 15 are no longer coprime, so you cannot use the technique from 21.)

• 23. Looking at the list of numbers generated by 3^i mod 15 for i <= 20, write a function that specifically calculates 3^i mod 15 in O(1) (constant) time.
Bonus points if you can write this in just one line (minus the function header and the end statement) with no semicolons

• 24. Compute the number of permutations of a set of n elements.

• 25. Compute the number of k-permutations of a set of n elements. (IE,how many choices of k elements are there in a total set of n elements) see the second definition under combinatorics in http://en.wikipedia.org/wiki/Permutation

• 26. Same as 25, but disregarding the ordering (also known as combination)

• 27. Find all possible permutations (24. type of definition) of a table. (IE: perm{1,2,3} = {1,2,3},{1,3,2},{2,1,3},{2,3,1},{3,1,2},{3,2,1})

• 28. Somewhat challenging: How many ways are there to put n balls into k baskets? Write a function that given 2 parameters n and k, computes the number of choices you have to put n balls into k baskets. (It's okay to google this, it was an open problem for quite a while at the time of its proposition)

• 29. In a certain programming language, valid identifiers must start with a letter or $, then they can be composed of underscores, hyphens, letters, or numbers. Write a lua pattern that when plugged into str:find(pattern), can determine whether str is a valid identifier in this language.

• 30. Challenge Problem: Given a number in the English language, determine its numerical value (complement of 20)
edited 3×, last 16.07.11 07:51:34 pm

old Re: The Ultimate Lua Challenge

FlooD
GAME BANNED Off Offline

Quote
asdf kk i'm really bored
typing this as fast as possible so these aren't optimal functions. just whatever comes off the top of my head
1.
function kth(table, i)
     return table[i]
end
2.
function last(table)
     return kth(#table)
end
3.
function second_last(table)
     return kth(#table-1)
end
4.
function flat(table)
function number(table)
     return #table
end
5.
function reverse(table)
     local a = #table
     local t = {}
     for i,v in ipairs(table) do
          t[1+a-i] = v
     end
end
6.
function p(table)
     local t = reverse(table)
     for i,v in ipairs(table) do
          if table[i] ~= t[i] then
               return false
          end
     end
     return true
end
7.
eww recursion
function flat(table)
     local t = {}
     for i,v in ipairs(table) do
          if type

TBC
8.
extremely inefficient method
function unique(table)
     local t = {}
     for i,v in ipairs(table) do
          for ii,vv in ipairs(table) do
               if i ~= i and v~= vv then
                    t:insert(v)
               end
          end
     end
end
9.
function group(table)
     local t = unique(table)
TBC
edited 1×, last 29.12.10 07:13:29 am

old Re: The Ultimate Lua Challenge

FlooD
GAME BANNED Off Offline

Quote
sdffkfkjrkf sry im too lazy to post on pastebin cuz im on itouch
7. function asdf(table)
local t={}
for i,v in ipairs(table) do
if type(v)~="table" then
t:insert(v)
else
for z,x in ipairs(asdf(v)) do
t:insert(x)
end
end
end
return t
end
9.
function duudjdc(table)
local last
for i,v in ipairs(table) do
if v==last then
if type(table[i-1])~="table" then table[i-1]={table[i-1]} end
table[i-1]:insert(last)
table:remove(i)
else
last=v
end
end
return table
end
10.
function sjfufi(table)
t=duudjdc(table)
for i,v in ipairs(t) do
if type(v)="table" then
t[i]={v[1],#v}
end
end
return t
end

old Re: The Ultimate Lua Challenge

SQ
Moderator Off Offline

Quote
@FlooD,
You're careless.
First, you should post scripts in cs2d.Pastebin.com
Second, put tabs on.
Third, careless scripting....
I suggest going on PC, though.

old Re: The Ultimate Lua Challenge

FlooD
GAME BANNED Off Offline

Quote
sorry bro im on my itouch
idk how to indent in it lmao

ill post a "clean" version of my answers on pastebin tomorrow

old Re: The Ultimate Lua Challenge

Lee
Moderator Off Offline

Quote
@Flacko
√ 1,2,3,4,5,6,7,9,10
× 8 fails on {1,2,3,4,5,4} (the duplicates do not necessarily have to be consecutive)

@flood
√ 1,2,3,4(meh, the logic is right),5,6,8
× cba to read 7, 9, and 10, we gotta have a talk about drinking and coding man

@Blazing
√ 1,2,3,4,5,6,7,8,9,10 congrats

old Re: The Ultimate Lua Challenge

Flacko
User Off Offline

Quote
Lee has written
@Flacko
√ 1,2,3,4,5,6,7,9,10
× 8 fails on {1,2,3,4,5,4} (the duplicates do not necessarily have to be consecutive)


Oh, I see, then this should work:
1
2
3
4
5
6
7
8
9
10
11
12
13
function unique(t)
	local r = {}
	local i = {}
	for k,v in pairs(t) do
		if not i[v] then
			r[#r+1] = v
			i[v] = 1
		end
	end
	return r
end
a = unique({1,4,5,2,2,3,4})
for k,v in pairs(a) do print(v) end

old Re: The Ultimate Lua Challenge

NKN
User Off Offline

Quote
Flacko has written
Lee has written
@Flacko
√ 1,2,3,4,5,6,7,9,10
× 8 fails on {1,2,3,4,5,4} (the duplicates do not necessarily have to be consecutive)


Oh, I see, then this should work:
1
2
3
4
5
6
7
8
9
10
11
12
13
function unique(t)
	local r = {}
	local i = {}
	for k,v in pairs(t) do
		if not i[v] then
			r[#r+1] = v
			i[v] = 1
		end
	end
	return r
end
a = unique({1,4,5,2,2,3,4})
for k,v in pairs(a) do print(v) end

Thats chinese for me.

old Re: The Ultimate Lua Challenge

Flacko
User Off Offline

Quote
This is the fastest table.reverse function I could come up with:
1
2
3
4
5
6
function table.reverse(t)
	local len = #t+1
	for i=1, (len-1)/2 do
		t[i], t[len-i] = t[len-i], t[i]
	end
end

Can somebody make a faster one?
(Yes, this is a challenge too)

old Re: The Ultimate Lua Challenge

archmage
User Off Offline

Quote
I think this is slightly faster. I ran 10 tests on each I have these results:
Mine has written
9 results where 1 ms
1 result was less than 1 ms (idk what it was Lua just printed 0)


Flacko's has written
9 results where 1 ms
1 result was 2 ms


1
2
3
4
5
6
7
8
9
function table.reverse(t)
	local len = #t;
	local ret = {};
	for i = len, 1, -1 do
		ret[len-i+1] = t[i];
	end

	return ret;
end

old Re: The Ultimate Lua Challenge

Flacko
User Off Offline

Quote
On the test I ran, my function runs a little faster:
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
function table.dbreverse(t)
	local len = #t;
	local ret = {};
	for i = len, 1, -1 do
		ret[len-i+1] = t[i];
	end
	return ret;
end

function table.reverse(t)
	local len = #t+1
	for i=1, (len-1)/2 do
		t[i], t[len-i] = t[len-i], t[i]
	end
end

local tbl = {}
for i=1,9999 do
	tbl[i] = i
end
local start
local finish

start = os.clock()
for i=1,2500 do
	--Since your function creates a new table, I think we will need to reassign the reversed table
	tbl = table.dbreverse(tbl)
end
finish = os.clock()
print("DB: "..finish-start)

start = os.clock()
for i=1,2500 do
	table.reverse(tbl)
end
finish = os.clock()
print("Flacko:"..finish-start)

Output:
DB: ~3.4
Flacko: ~2.77

However, by applying a small tweak to your function, I got to make it slightly faster:
1
2
3
4
5
6
7
8
function table.dbreverse(t)
	local len = #t+1; --here
	local ret = {};
	for i = len-1, 1, -1 do --and here
		ret[len-i] = t[i]; --and here
	end
	return ret;
end
Output:
DB: ~3.228
Flacko: ~2.772

I don't think I can make it any faster, though.
I've also tried with tables smaller than 9999, but the difference just got bigger. I think it's because your script creates a new table while mine just uses the table supplied as a parameter directly

old Re: The Ultimate Lua Challenge

Lee
Moderator Off Offline

Quote
You can also use the time command, which profiles your code with millisecond granularity


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
#include <lua.h>
#include <lauxlib.h>
#include <lualib.h>

int reverse(lua_State* l){
	if (!lua_getttop(l) || !lua_istable(l,1)){
		lua_pushstring(l, "reverse() needs to take a table parameter");
		lua_error(l);
	}
	
	// Stack: i -> t[n-i+1] -> n-i+1 -> t[i] / settable pops off 2 at a time
	int i, n=lua_objlen(l,1);
	for (i=1; i<=n/2; i++){
		lua_pushinteger(l, i);
		lua_pushinteger(l, n+1-i);
		lua_gettable(l, 1);
		lua_pushinteger(l, n+1-i);
		lua_pushinteger(l, i);
		lua_gettable(l, 1);
		lua_settable(l, 1);
		lua_settable(l, 1);
	}
	
	lua_pushvalue(l, 1); // return the table passed in
	return 1;
}

gcc -shared -oreverse.so -llua reverse.c

1
reverse = package.loadlib("reverse", "reverse")

This is equivalent to yours, except without the bytecode parsing overhead, so it should theoretically be faster by a few milliseconds (note, untested)
To the start Previous 1 2 3 4 5 Next To the start
Log in to reply Scripts overviewCS2D overviewForums overview