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 Re: The Ultimate Lua Challenge

Snurq
BANNED Off Offline

Quote
31:
Would take some time to do this in lua, so i did it by hand.
basically it came down to this in matrix notation:

f(n+2) = (4 12 1) * f(n+1)
f(n+1) = (1 0 0 ) * f(n)
f(n) = (0 1 0 ) * 5

> f(n+2) = 4 * f(n+1) + 12* f(n) + 5 √

diagonalize:
A = P * D * P^-1
Where D is the diagonal matrix with the eigen values,
P is the matrix with the eigenvectors as columns.
D^100 is easy to compute because diagonal.

A ^100 = P * D ^100 * P = Q

now Q * [1 0 5]' and u have the answer.

old Re: The Ultimate Lua Challenge

Lee
Moderator Off Offline

Quote
That's pretty much correct, however there's a small problem in the transformation matrix

http://mathbin.net/101651

• 34.

Find the last three digits of (25!)^2000 such that they are not all 0

• 34.b (Challenge)

As a corollary, show that for any n, the last three non-zero digits of (n!)^2000 can be expressed as 2^(2000*x) mod 1000 for some integer x < log_2(n!).

For example, for 25!, x = 16, and 2^(32000) mod 1000 = 376.

old Re: The Ultimate Lua Challenge

SD
User Off Offline

Quote
I didn't really understand the first task. Could this be a correct answer?
Code >

old Re: The Ultimate Lua Challenge

Lee
Moderator Off Offline

Quote
Not quite, it's actually simpler than what you are thinking. Essentially, if you have a table {"a", "b", "c", "d", ...}, the first element of that table is "a". How might you get the first element out of a table?

old Re: The Ultimate Lua Challenge

SD
User Off Offline

Quote
Like this.
1
2
arrayx = {"a", "b", "c"}
print(arrayx[1])
#2 >

#3 >

#4 >

#5 >

old Re: The Ultimate Lua Challenge

Lee
Moderator Off Offline

Quote
• 35. Suppose you are stacking a tower of boxes and each box has a weight that's equal to the capacity of weight it can support. For example, a box of weight 3 can support only up to 3 units of weight. What is the least weight of a 1000 box high tower?

• 36. Suppose that you are inside a grid and you can only walk either to the square below or to the right of you. How many paths are there between the origin and (x,y)?

• 37. Suppose that in 2020, UnrealSoftware users reorganized themselves into provinces and there are yearly elections for a moderator (out of two candidates). Suppose that there are 1000 provinces consisting of k_i users for each province i, and each province will put all of its votes into only one candidate. Given a randomly generated set of k_i, determine if it's possible for a tie to occur.

• 38. Suppose that China has recently decided to switch its language completely into pinyin (made up of the english alphabet), but are adamant about not putting spaces around words. For example, in english, the phrase "how are you doing" would become "howareyoudoing" if we're using the reformed chinese analogy. Suppose I give you an electronic dictionary of pinyin to chinese characters, write a program that can parse a stream of pinyin and output a character translation if one exists.

(Note: the obvious method for 38 may not work here; why?)

• 39. (Slightly challenging) Suppose that you live in a world where once a person makes a call, he cannot make another call for the rest of that minute. General Sherman was a general and had 10 officers that he can directly call, and those 10 officers each have some number of direct subordinates to whom they can call (think of this like a tree/hierarchy of command). Suppose the general wanted to everyone hi (i.e., each person is to utter the phrase "the general says hi, send it along" and hang up) which takes 0 seconds to do (assuming), then what is the least number of minutes it takes for everyone under Sherman's command to get the message if there are over 100 levels of command in this hypothetical world (generate a random test case)

For example, suppose that Sherman is in charge of Bob and Frank, Bob is not in charge of anyone else but Frank is in charge of Emily and Matt. If Sherman calls Bob first, then Frank, and Frank tells Emily and Matt, then it'll take a total of 4 minutes to finish the call. On the other hand, if Sherman calls Frank first, and while calling Bob next, Frank calls Emily, and finally Matt, then the whole process only takes 3 minutes. How do you compute the minimum time it takes? The brute force method will take too long when you have 100 levels of command.

old Re: The Ultimate Lua Challenge

gotya2
GAME BANNED Off Offline

Quote
Remember that this is the ultimate Lua challenge, and not the ultimate math challenge

ANyway for 35. I assume that the mimimum weight of a box is 1.

[1],
[1],
[2],
[4], this is what the top would look like
so the series of weight would look like

1 1 2^1 2^2 ... 2^(1000-2)
the sum of this is 2^(1000 - 1) = a huge number.
1
print(math.pow(2,999))

36.
combinational problem
http://en.wikipedia.org/wiki/Combination

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
fact = function(n)
	local sum = 1
	while( n > 0 ) do
		sum = sum * n
		n = n - 1
	end
	return sum

end

paths = function(o_x,o_y,x,y)
	if( x < o_x or y < o_y) then
		return 0
	else
		local dx,dy = x - o_x, y - o_y
		return fact(dx+dy) / (fact(dx) * fact(dy))
	end
end


print(paths(3,3,6,6))

38 This is a problem of lexical analysis
http://en.wikipedia.org/wiki/Lexical_analysis

The tokens would be {"how", "are", "you", "doing", ... }

the obvious problem is that in this sentence, howareyoudoing, also the words "war" and "do" appear, also part of the tokens. You would have to write a regular expression parser that only accepts the longest match. not "do" but "doing".
edited 1×, last 14.01.13 12:53:03 pm

old Re: The Ultimate Lua Challenge

Flacko
User Off Offline

Quote
35
1
2
3
4
5
6
7
8
9
function stackWeight(x,minw)
	local minw = minw or 1 --2^(x-1)
	for i=1, x-1 do
		minw = minw + minw
	end
	return minw
end
--output
print(stackWeight(1000))
36
1
2
3
4
5
6
7
8
9
function calcPaths(x,y) --assuming start tile is (0,0)
	local total = 0
	if x > 0 then total = total + calcPaths(x-1, y) end
	if y > 0 then total = total + calcPaths(x, y-1) end
	if x==0 and y==0 then return 1 end
	return total
end
--output
print(calcPaths(2,2))
37
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
k = {voters = 0}
for i=1, 1000 do
	local x = math.random(1,10)
	k[i] = x
	k.voters = k.voters + x
end
function isTiePossible()
	--assuming k[1 ... 500] will all vote candidate 1 while [500...1000] will vote 2
	local count = 0
	for i=1,500 do
		count = count + k[i]
	end
	return k.voters/count == 2
end
--output
print(tostring(isTiePossible()))
38
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
--english to spanish
dictionary = {
	{"war","guerra"},
	{"do","hacer"},
	{"how","como"},
	{"are","estas"},
	{"you","tu"},
	{"doing","haciendo"},
	{"other", "otro"},
	{"right", "correcto"},
	{"the", "lo"},
	{"thing", "cosa"},
}
table.sort(dictionary, function(a,b) return a[1]:len() > b[1]:len() end)
function translate(x,start)
	if not start then
		start = 1
		x = string.lower(x)
	end
	local m = {math.huge, math.huge, 0}
	for i=1,#dictionary do
		local s,e = x:find(dictionary[i][1], start, true)
		if s and e then
			if s < m[1] or (s == m[1] and e > m[2])then
				m = {s,e, i}
			end
		end
	end
	local str = ""
	if m[2] <= string.len(x) then 
		str = dictionary[m[3]][2] .. " " .. translate(x, m[2]+1)
	end
	return str
end
--output
print(translate("howareyoudoing"))
print(translate("dotherightthing"))
,
edited 1×, last 14.01.13 06:17:43 pm

old Re: The Ultimate Lua Challenge

Lee
Moderator Off Offline

Quote
@user gotya2: You know me :P, it's hard pressed for me to differentiate between the two

@user Flacko: • 36 is a bit intractable for large values, it's possible to bring the time complexity down to O(n^2) rather than EXP by memoization.

Another cool thing, as user gotya2 pointed out, this has a combinatorial form of either [(x+y) choose x] or [(x+y) choose y] because this has a natural reduction to a problem of shooting x balls into y baskets (can you see how to make this analogy)?

• 40 A (significantly) harder version of this problem with no known closed combinatorial form asks how many paths there are to a point (n,n) such that no points (x,y) whose x is perfectly square, y is perfectly square, and the sum x+y is also perfectly square (i.e. eliminating all pythagorean pairs).

Hint: inclusion/exclusion

For • 37, I'm not sure if this algorithm is correct for the general case. Supposing that all of the candidates are sorted in increasing order of their number of votes, then the following scenario [1,1,1,1,1,5] might constitute as a counterexample; in theory it could result in a tie if the first 5 candidates votes for 1 and the last candidate votes for two, but in which the sorted algorithm will return as being impossible to achieve.

For •38, both of you are slightly off (you are both seemingly trying to match the earliest and the longest matchable sequence first). Consider the following dictionary which consists of only three words, do, doing, and ingrid
1
2
3
dict.doing = "..."
dict.do = "..."
dict.ingrid = "..."

Suppose we have as an input the string "doingrid". The maximal munch technique will first match "doing" because that is the longest sequence, then it will have to match "rid", which has no known translation, and will then report that translation is not possible when it could be tokenized into "do" and "ingrid". Of course, as your dictionary becomes larger, such problems aren't as common and maximal much proves a good approximation. (Note that in general, this problem is NP-Hard, but it does not take an exponential number of operations to solve. The version which decides and translates the maximal subset of the string is both NP-Hard and take an exponential number of operations to solve; you can prove both by reduction from set cover and maximal set cover respectively)

Hint for • 39: you can solve this recursively and use a simple heuristic (just sort something in decreasing order) which turns out to be optimal. Ponder on the Sherman-Bob-Frank example and draw out the tree, you'll probably see the solution.

old Re: The Ultimate Lua Challenge

Flacko
User Off Offline

Quote
Ok then, from what I ripped off from wikipedia:
36.
1
2
3
4
5
6
7
8
9
10
11
12
13
function calcPaths(x,y) --assuming start tile is (0,0)
	local fz = 1
	for i=y+1, x+y do
		fz = fz*i
	end
	local fx = 1
	for i=1, x do
		fx = fx*i
	end
	return fz/fx
end
--output
print(calcPaths(3,3))

37. (ugly and inefficient, as I didn't understand wikipedia's subset sum article)
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
k = {voters = 0}
for i=1, 1000 do
	local x = math.random(1,5)
	k[#k+1] = x
	k.voters = k.voters + x
end
function isTiePossible()
	if k.voters % 2 ~= 0 then
		return false
	end
	local selections = {total=0}
	while selections.total ~= k.voters / 2 do
		if #k == 0 then return false end
		local lasti = 0
		for i=1,#k do --look for the biggest possible item to add
			if k[i]+selections.total <= k.voters/2 and k[i] > (k[lasti] or 0) then
				lasti = i
			end
		end
		if lasti == 0 then --couldn't fit a new item? discard the biggest element in our list
			local i = table.biggest(selections)
			selections.total = selections.total - selections[i]
			table.remove(selections,i)
		else --add new item to selections
			selections[#selections+1] = k[lasti]
			selections.total = selections.total + selections[#selections]
			table.remove(k,lasti)
		end
	end
	return selections
end
function table.biggest(t)
	local p = 1
	for i=2, #t do
		if t[i] > t[p] then p=i	end
	end
	return p
end
--output
print(isTiePossible())

old Re: The Ultimate Lua Challenge

FlooD
GAME BANNED Off Offline

Quote
wow
it's hard to remember the time when i wasn't so lazy and would actually try these


kkkk fine
didn't google or look at anyone's answer yet
35. trivial. 2^(1000-1)
36. trivial. x+y choose x
37. a bit nontrivial. coding on iphone sucks. one space indent, umad??
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
test={1,3,5,7,9,11}
function tie(t)
 local s=0
 for _,v in pairs(t) do s=s+v end
 if s%2==1 then return false end
 s=s/2 --problem?
 for _,v in pairs(t) do if v>s then return false end end
 return a(copy(t),s)
end
function copy(t)
 local tt={}
 for i,v in pairs(t) do tt[i]=v end
 return tt
end
function a(t,c)
 if c==0 then return true end
 local imax
 local max=0
 for i,v in pairs(t) do
  if v==c then return true
  elseif v>c then t[i]=0
  elseif v>max then imax,max=i,v
  end
 end
 if max==0 then return false end
 t[imax]=0
 return a(copy(t),c-max) or a(t,c)
end
inb4 stack overflow

38. just hire someone who reads pinyin...
39. tl;dr sorry
40. sentence fragment lol. sounds like boring problem so i'll pass

edit2: is flacko's 37 the same as mine? (while loop in place of crazy recursion)
edited 2×, last 15.01.13 10:00:08 am

old Re: The Ultimate Lua Challenge

gotya2
GAME BANNED Off Offline

Quote
user Lee has written
• 39. (Slightly challenging) Suppose that you live in a world where once a person makes a call, he cannot make another call for the rest of that minute. General Sherman was a general and had 10 officers that he can directly call, and those 10 officers each have some number of direct subordinates to whom they can call (think of this like a tree/hierarchy of command). Suppose the general wanted to everyone hi (i.e., each person is to utter the phrase "the general says hi, send it along" and hang up) which takes 0 seconds to do (assuming), then what is the least number of minutes it takes for everyone under Sherman's command to get the message if there are over 100 levels of command in this hypothetical world (generate a random test case)

For example, suppose that Sherman is in charge of Bob and Frank, Bob is not in charge of anyone else but Frank is in charge of Emily and Matt. If Sherman calls Bob first, then Frank, and Frank tells Emily and Matt, then it'll take a total of 4 minutes to finish the call. On the other hand, if Sherman calls Frank first, and while calling Bob next, Frank calls Emily, and finally Matt, then the whole process only takes 3 minutes. How do you compute the minimum time it takes? The brute force method will take too long when you have 100 levels of command.


The outcome you gave in the example is not correct..
1. Sherman calls bob at minute 0, frank at minute 1. Frank calls emily at minute 1, and matt at minute 2. Process takes 2 minutes.
2. Sherman calls frank at minute 0, frank calls emily at minute 0 and matt at minute 1, sherman calls bob at minute 1. Whole process takes 1 minute.
The rule was that you could only "make" a phonecall once a minute, but can you receive and then make a phonecall ?
i.e. the problem is not very clear to me.

old Re: The Ultimate Lua Challenge

Lee
Moderator Off Offline

Quote
I originally intended that a person can only make or receive one call per minute, but without loss of generality, if you are allowed to receive and then immediately make a call once a minute, then your optimal would be the optimal of the former minus the height of the chain or command hierarchy tree.

old Re: The Ultimate Lua Challenge

FlooD
GAME BANNED Off Offline

Quote
wat happened to cs2d.pastebin.com


btw question:

which is better?
1
2
3
4
5
local a
for _,b in pairs(mytable) do
	a=myfunction(b)
	--do something with a
end
or
1
2
3
4
for _,b in pairs(mytable) do
	local a=myfunction(b)
	--do something with a
end
i supposed the latter is better but idk
edited 1×, last 18.01.13 09:51:10 am

old Re: The Ultimate Lua Challenge

Lee
Moderator Off Offline

Quote
the latter is slightly faster, the former is an implicit table look up and the latter is stored directly onto one of the 255 registers allocated for you in Lua.

• 41. (Intermediate) A zig-zag permutation of order n is a permutation of the collection of numbers {1,2,...,n} such that within the zig-zag permutation, the first element is smaller than the second element, the second element is larger than the third element, the third element is smaller than the fourth, the fourth larger than the fifth, and so on, for n odd.

For example, one such permutation for n=9 is the following set: {4,8,6,7,5,9,1,3,2}
IMG:https://quicklatex.com/cache3/ql_8080fdda4f1b34cbcf423d093643f9a7_l3.png


Count the number of zig-zag permutations for all odd n less than 11. (Answer: {1,2,16,272,7936,353792})

• 42. (Trivial) If I give you an arbitrary n, construct one such valid zig-zag permutation. Hint: A particular path through a binary tree with the property that the root node is always larger than the two sub-child can generate this; can you find it?

• 43. (Extremely challenging) Desiree had a calculus problem: generate the taylor expansion of tan(x). He found a startling discovery
1
tan(x) = 1 (z/1!) + 2 (z^3/3!) + 16 (z^5/5!) + 272 (z^7/7!) + 7936 (z^9/9!) + 353792 (z^11/11!)

Suppose that we use the max-rooted binary tree encoding above, we can reduce the problem of counting all such permutations to finding all possible max-rooted binary trees with n nodes. One such combinatorial generator is specified by

1
Tree = Atom + (Tree, max, Tree)

This translates into a "generating function" y(x) = x + integral_0^z T(w)^2 dw. Use this to argue that tan(x) generates the zig-zag permutations and write a general function that approximates the number of zig-zag permutations for any arbitrary n.
edited 3×, last 31.01.13 10:10:40 pm

old Re: The Ultimate Lua Challenge

gotya2
GAME BANNED Off Offline

Quote
For 5 numbers, i count more than 6..
{3,5,2,4,1} {3,5,1,4,2} {3,4,1,5,2} {3,4,2,5,1} {2,5,1,4,3}
{2,5,3,4,1} {1,5,3,4,2} { 1,5,2,4,3} etc... what's up with that?

old Re: The Ultimate Lua Challenge

Infinite Rain
Reviewer Off Offline

Quote
It's ultimate math challenge.
Wouldn't be that enough?
More >


Just asking.

old Re: The Ultimate Lua Challenge

Yates
Reviewer Off Offline

Quote
I second that. You just spammed a thread for the most ridiculous reason ever. To brag about your code.

You know, good code is shown by what it does, and not what it is. And stop using semi-colons (;), it's completely useless as comma does the exact same thing (Apart from in other coding languages which you probably don't know anyway).

Thanks.
To the start Previous 1 2 3 4 5 Next To the start
Log in to reply Scripts overviewCS2D overviewForums overview