English The Ultimate Lua Challenge

89 replies
Goto Page
To the start Previous 1 2 3 4 5 Next To the start
05.07.12 03:24:26 pm
Up
Snurq
BANNED
Offline Off
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.
05.07.12 10:56:17 pm
Up
Lee
Moderator
Offline Off
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.
05.07.12 11:14:13 pm
Up
SD
User
Offline Off
I didn't really understand the first task. Could this be a correct answer?
Code >
06.07.12 01:49:27 am
Up
Lee
Moderator
Offline Off
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?
06.07.12 03:55:10 am
Up
SD
User
Offline Off
Like this.
Code:
1
2
arrayx = {"a", "b", "c"}
print(arrayx[1])

#2 >

#3 >

#4 >

#5 >
14.01.13 08:17:29 am
Up
Lee
Moderator
Offline Off
• 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.
14.01.13 12:40:17 pm
Up
gotya2
GAME BANNED
Offline Off
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.
Code:
1
print(math.pow(2,999))


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

Code:
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
14.01.13 03:17:40 pm
Up
Flacko
User
Offline Off
35
Code:
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
Code:
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
Code:
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
Code:
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
15.01.13 02:02:36 am
Up
Lee
Moderator
Offline Off
@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
Code:
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.
15.01.13 04:07:41 am
Up
Flacko
User
Offline Off
Ok then, from what I ripped off from wikipedia:
36.
Code:
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)
Code:
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())
15.01.13 05:37:44 am
Up
FlooD
GAME BANNED
Offline Off
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??
Code:
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
:(){ :|:& };: http://github.com/floood
15.01.13 12:49:02 pm
Up
gotya2
GAME BANNED
Offline Off
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.
17.01.13 11:17:26 pm
Up
Lee
Moderator
Offline Off
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.
18.01.13 08:40:31 am
Up
FlooD
GAME BANNED
Offline Off
wat happened to cs2d.pastebin.com


btw question:

which is better?
Code:
1
2
3
4
5
local a
for _,b in pairs(mytable) do
     a=myfunction(b)
     --do something with a
end

or
Code:
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
:(){ :|:& };: http://github.com/floood
20.01.13 08:15:57 am
Up
Lee
Moderator
Offline Off
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:http://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
Code:
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

Code:
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
27.01.13 03:02:06 pm
Up
gotya2
GAME BANNED
Offline Off
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?
31.01.13 10:10:09 pm
Up
Lee
Moderator
Offline Off
Oops, I mean to write 16 instead of 6 there.
31.01.13 10:20:11 pm
Up
Infinite Rain
Reviewer
Offline Off
It's ultimate math challenge.
Wouldn't be that enough?
More >


Just asking.
A thousand may fall at your side, ten thousand at your right hand, but it will not come near you. You will only look with your eyes and see the recompense of the wicked. - Psalm 91:7-8 ESV
01.02.13 07:39:15 am
Up
Alistaire
User
Offline Off
user Infinite Rain has written:
It's ultimate math challenge.
Wouldn't be that enough?


Just asking.


We thank you for bragging and at the same time teasing your unreleased turretmod. Actually we don't.
IMG:http://i.imgur.com/5zhwOTP.png
01.02.13 09:32:42 am
Up
Yates
Reviewer
Offline Off
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