Coding Exercise – LUA Programming – SPOJ Online Judge – 17481. Fun with Sequences (Act 5)

The problem is from SPOJ Online Judge [problem description here]

The puzzle asks to you check if the given sequence of integers consists of strictly two parts: the first part descending and the second ascending. If the length of the given integers is 1, it is false. If it is two integers, we can either print true or false, both are correct.

Otherwise, we need to check first if sequence is descending (at least has a descending sub-sequence). And then we check if the sequence is ascending.

-- split a string into array
function split(s, delimiter)
    result = {}
    for match in (s..delimiter):gmatch("(.-)"..delimiter) do
        table.insert(result, match)
    end
    return result
end

n = tonumber(io.read())
arr = {}
for key, var in ipairs(split(io.read(), [[ ]])) do
	table.insert(arr, tonumber(var))  -- convert to numbers
end

function Check(s)
	local len = #s
	if len <= 2 then
		return true
	else
		local i = 1
		while (i < len) and (s[i] > s[i + 1]) do
			i = i + 1
		end
		if i == 1 then -- not descending
			return false
		end
		i = i + 1
		while (i < len) and (s[i] < s[i + 1]) do
			i = i + 1
		end
		return i == len -- has descending remainder
	end
end

if (Check(arr)) then
	print("Yes")
else
	print("No")
end

We use operator # (sharp) to get the length of a table/array. Also, the sub-strings split should be converted to numbers before comparison i.e. ‘-2′>’-1′ but -2<-1.

The keyword local is similar to the var in Javascript, where it tells the interpreter that the following variable has a limited local scope otherwise, it will be declared as a global variable.

Each statement can be optionally followed by a semicolon, which is similar in Javascript.

The overall algorithm complexity is O(n).

–EOF (The Ultimate Computing & Technology Blog) —