On Sat, Dec 5, 2020 at 3:00 PM Xmilia Hermit wrote:
[ … a faster solution … ]
Congratulations!
Your solution is the fastest.
$ time lua student3.lua 20
real 0m0.294s
$ time lua pierre.lua 20
real 0m0.158s
$ time lua student4.lua 20
real 0m0.140s
$ time lua xmilia.lua 20
real 0m0.127s
How about this:
function fastnil_table()
local data = "" class=""> local my_nil = {}
return setmetatable({
move = function(a1, ...)
table.move(data, ...)
end
}, {
__index = function(t, k)
if data[k] ~= my_nil then
return data[k]
end
end,
__newindex = function(t, k, v)
if v == nil then
v = my_nil
end
data[k] = v
end
})
end
local function create(level, t, idx)
if level == 0 then
idx = idx + 1
t[idx] = "Lua"
else
idx = create(level - 1, t, idx)
t:move(1, idx, idx + level)
idx = (2 * idx) + level - 1
for i = 1,level do
t[idx + i] = nil
end
end
return idx
end
function solution4(level)
local t = fastnil_table()
local last_index = create(level, t, 0)
return t, last_index
end
local level = tonumber(arg[1])
local t, last_index = solution4(level)
┌ chris@chriss-mbp-2 ~/src/tmp/lua
└ 11:03:01 $ /usr/bin/time -p lua student1.lua 20
real 0.25
user 0.23
sys 0.01
┌ chris@chriss-mbp-2 ~/src/tmp/lua
└ 11:06:50 $ /usr/bin/time -p lua student3.lua 20
real 0.18
user 0.16
sys 0.01
┌ chris@chriss-mbp-2 ~/src/tmp/lua
└ 11:06:55 $ /usr/bin/time -p lua xmilia.lua 20
real 0.11
user 0.10
sys 0.01
┌ chris@chriss-mbp-2 ~/src/tmp/lua
└ 11:07:04 $ /usr/bin/time -p lua chris.lua 20
real 0.06
user 0.04
sys 0.01
Regards,
Chris