Coding Challenge #3: Continuous Subarrays

[starmaq]

Coding Challenge #3

Welcome back, to another coding challenge! I hope you have fun with today’s. I think it’s much simpler and shorter, and just requires some amount of creativity. Credit belongs to @Fifkee for sharing this challenge with me!

As usual, same requirements:

• Has to be written in Lua 5.1 (the version roblox uses)
• The program has to be compatible with Roblox Studio, meaning you can’t use features vanilla Lua has but rbxlua disabled
• You can’t use httpservice to cheat the challenge

---

Let’s say we have an array A.

We define S to be a subarray of A if contains some elements that also exist in A.

We define S to be a continuous subarray of A, if it is a subarray of A, and staisfies the condition: S[1] , S[2] , ... , S[n] = A[i] , A[i + 1] , ... , A[i + n - 1] for some index i. An array has multiple continuous arrays.

For this challenge, you need to create a function subarrays, which takes an array as input, and return a table containing all of the array’s continuous subarrays.

Wait… What? Well the first part is simple, but what about the continuous subarray? I think giving an example is the best way to explain it.

Let A be {1, 2, 3}, the continuous subarrays of A would be {}, {1}, {2} , {3} , {1, 2} , {2, 3} and {1, 2, 3}.

Let A be {1, 2, 3, 4}, the continuous subarrays of A would be {}, {1}, {2} , {3} , {4}, {1, 2} , {2, 3}, {3, 4}, {1, 2, 3}, {2, 3, 4} and {1, 2, 3}.

Basically, you need to make all possible subarrays using initial array A’s elements that have a length of 1, and all subarrays that have a length of 2, where the elements of each subarray are next to each other (e.g {1, 3} isn’t correct, because 1 and 3 aren’t next to each other) ect.

Anywho, this is it again! I hope you have fun with this one! You can find a list of all the challenges here or a github version here.

The answer is here, don't spoil yourself!

Basically, the way this will work is, we will loop through the array, and for each element, using the fact that unpack(table, from, to) has two optional argument; from where to start and stop unpacking, we loop from that element to the next element, inserting those two into a subarray, then loop from the same element to the next next element ect. until the there are no elements, and we move to the second element, and do the same stuff.

local function subarrays(array) --array is the inputted array
    local subarrays = {{}} --this is the returned table, {} is considered a subarray as well
    for x, _ in pairs(array) do --loop through all elements
        for i = x, #array do --loop from the element's index, to the end of the list, i would be the current next element
            table.insert(subarrays, {unpack(array, x, i)}) --basically insert an array in the returned table of elements starting from the element and the current next element
       end
    end
    return subarrays --return
end

local A = {1,2,3,4,5} --an example

for i, v in pairs(subarrays(A)) do  
    print(string.format("{ %s }", table.concat(v, ", "))) --just a way to print the subarrays
end

Result:

Note that order isn’t needed.

[Fifkee (Noire)]

Still forgetting subarray {}, Starma.

imeanitismycodesotechnicallyiforgotitbutstill

[rogchamp (pasta)]

I got confused and thought that you only wanted consecutive elements that were consecutive. (For example, {1, 2, 4, 3, 5} would have {1, 2} as the longest since 3 doesn’t come after 4 and 5 doesn’t come right after 3.) Since your examples were all 1, 2, 3, 4 and stuff like that, it was hard to tell that’s not what you were asking for. Here’s my code anyways:

code

local function findSubsection(array, start, stop)
	-- note: doesn't deep copy (as u can see lol)
	local final, j = {}, 1
	
	for i = start, stop do
		final[j] = array[i]
		j = j + 1
	end
	
	return final
end

return function(array)
	local last = {};
	local subarrays = {{},} -- haha unlike Fifkee i did not forget the empty table
	
	for _, value in ipairs(array) do
		subarrays[#subarrays + 1] = {value} -- insert the 1 element subarray
		print(value, repr(last))
		
		if last[#last] == value - 1 then -- if it's sequential with the last 
			local subsection 
			-- probably an awful method (should really be local to scope of 2nd `for`
			-- but i want the last subsection to become the new `last`
			
			for i = 1, #last do
				subsection = findSubsection(last, i, #last)
				subsection[#subsection + 1] = value
								
				subarrays[#subarrays + 1] = subsection
			end
			
			last = subsection
		else
			last = {value}
		end
	end
	
	return subarrays
end

Ozzypig’s Repr made this super easy to test.

Here’s my reworked code now that I actually understand what you’re asking for. I found this out after looking at (and testing) your solution, so it’ll probably be pretty similar. (I hadn’t wrote mine yet at the time of writing this.)

reworked code

local function findSubsection(array, start, stop)
	-- note: doesn't deep copy (as u can see lol)
	local final, j = {}, 1
	
	for i = start, stop do
		final[j] = array[i]
		j = j + 1
	end
	
	return final
end

return function(array)
	local last = {};
	local subarrays = {{},} -- haha unlike Fifkee i did not forget the empty table
	
	for start = 1, #array do
		for stop = start, #array do
			subarrays[#subarrays + 1] = findSubsection(array, start, stop)
		end
	end
	
	table.sort(subarrays, function(subtable1, subtable2) -- bonus! since i already saw solution
		local length1, length2 = #subtable1, #subtable2
		
		if length1 ~= length2 then
			return length1 < length2
		else
			return subtable1[1] < subtable2[1]
		end
	end)
	
	return subarrays
end

[starmaq]

Very great! As usual!

From the looks of it, it seems to work.

Also I assume it’s a module script? Because you’re returning the function.

I really like how yor attempt is different then the one in the challenge (which is @Fifkee’s btw).

[rogchamp (pasta)]

@starmaq

Also I assume it’s a module script? Because you’re returning the function.

Yeah, I forgot to mention that. They’re both ModuleScripts.

[starmaq]

Submitted by @Abandion!

arr = {1,2,3,4,5,6,7,8,9}

function gensubarrays(array)
	ret = {}
	length = #array

	for i = 2, length do
		for h = 1, (length - (i-1)) do
			to = {}
			for j = 1, i do
				table.insert(to, array[h + (j-1)])
			end
			table.insert(ret, to)
		end
	end

	return ret
end

for i, v in pairs(gensubarrays(arr)) do
	a = ""
	for i, v in pairs(v) do a = a..v end
	print(a)
end

[LegitimatlyMe]

i made this challenge heres my sol (solution btw)

local function generateSubarrays(arr)
    local subarrays = {{}}

    for size = 1, #arr do
        for start = 1, #arr - size + 1 do
            local fin = start + size - 1

            table.insert(
                subarrays,
                { unpack(arr, start, fin) }
            )
        end
    end

    return subarrays
end

[FieryEvent]

local function subarrays(array)
	local length = #array
	local s = table.create(length*(length+1)/2 - 1, {})
	local i = 1
	for n=1, length - 1 do
		for j=1, length - n + 1 do
			s[i] = table.move(array, j, j + n - 1, 1, table.create(n, 0))
			i = i + 1
		end
	end
	return s
end

{ 1 }
{ 2 }
{ 3 }
{ 4 }
{ 5 }
{ 1, 2 }
{ 2, 3 }
{ 3, 4 }
{ 4, 5 }
{ 1, 2, 3 }
{ 2, 3, 4 }
{ 3, 4, 5 }
{ 1, 2, 3, 4 }
{ 2, 3, 4, 5 }

[sircfenner]

A solution using recursion:

local function q(a, o, i, j)
	o = o or {{}}
	i = i or 1
	j = j or 1
	if j > #a then
		return o
	elseif i > j then
		return q(a, o, 1, j + 1)
	end
	o[#o + 1] = {unpack(a, i, j)}
	return q(a, o, i + 1, j)
end

{  }
{ 1 }
{ 1, 2 }
{ 2 }
{ 1, 2, 3 }
{ 2, 3 }
{ 3 }
{ 1, 2, 3, 4 }
{ 2, 3, 4 }
{ 3, 4 }
{ 4 }
{ 1, 2, 3, 4, 5 }
{ 2, 3, 4, 5 }
{ 3, 4, 5 }
{ 4, 5 }
{ 5 }

[starmaq]

@FieryEvent

table.create(n, 0)

Good idea using table.create for allocating since we know the size of the array. It seems to be faster than mine!

local start1 = tick()
for i = 1, 100 do
	local random = table.create(math.random(1, 10), 5) --array of random size
	local a = subarrays(random)--my algorithm
end
print(tick()-start1)

local start2 = tick()
for i = 1, 100 do
	local random = table.create(math.random(1, 10), 5) --array of random size
	local a = subarrays2(random) --your algorithm
end
print(tick()-start2)

[starmaq]

Your solution is very interesting!
It seems to be faster as well

[JayO_X (fakefriends)]

Are subarrays like multidimensional arrays?

[starmaq]

A subarray is simply a part of an array. If you have an array of size #t, a subarray is any array {unpack(t, i, j)} such as 0 < i <= j <= #t, including the empty array {}.

Or simply, if you have the array {1, 2, 3, 4}, {1, 2} is a subarray, {2, 3} is a subarray, {2, 3, 4} is a subarray, {1} is a subarray etc. even {1, 2, 3, 4} is a subarray of itself. So really you pick a starting index, and choose an end index within the bounds of the array, that’s a subarray. The only special case is {} which is a subarray of all arrays. The challenge is to return all the subarrays of a given array.

[aren1709user (ireng)]

so far from challenge 1 till this one, i have been just opening the answer because i couldnt figure it out (even with the answer i still have no idea what im doing, im pretty sure this is easier than the second one.)