Forum

> > CS2D > Scripts > Help with some math please.
Forums overviewCS2D overview Scripts overviewLog in to reply

English Help with some math please.

8 replies
To the start Previous 1 Next To the start

old Help with some math please.

Blighted Song
User Off Offline

Quote
Heres how it goes, I need to find the lowest un-occupied number in an array that is higher than zero, example.
1
2
3
4
5
6
7
8
9
10
11
12
13
array1[1]=1
array1[2]=3
array1[3]=0
array1[4]=5
array1[5]=6
array1[6]=2
array1[7]=7
array1[9]=0
array1[10]=9
array1[11]=13
array1[12]=12
array1[13]=15
array1[14]=0
So with this the number I want to find is 4.

Not quite sure how to do this though, any help is appreciated.

old Re: Help with some math please.

Lee
Moderator Off Offline

Quote
As in finding the first 0 provided that its index is not 1? You need to formulate your question in a more concise form.

old Re: Help with some math please.

DannyDeth
User Off Offline

Quote
I'm guessing he means the lowest number that is not included in any of the elements of the array. I am not really sure how to do this, perhaps you could enlighten us both, Lee?

old Re: Help with some math please.

DC
Admin Off Offline

Quote
different attempts are possible here.

one primitive attempt would be to check for every number from 1 to n if it is in the array or not:
1
2
3
4
5
6
7
8
9
10
11
12
13
highestnumber=10000 -- highest possible number
for i=1,highestnumber
	occupied=false
	for j=1,#array1
		if array1[j]==i then
			occupied=true
			break
		end
	end
	if not occupied then
		return i
	end
end

another attempt would be to create a table with an index for each number to save if its occupied or not (less iteration but more memory usage):
1
2
3
4
5
6
7
8
9
10
11
12
13
highestnumber=10000 -- highest possible number
occupied = {}
for i=1,highestnumber do
	occupied[i] = false
end
for i=1,#array1
	occupied[array1[i]] = true
end
for i=1,highestnumber do
	if not occupied[i] then
		return i
	end
end

both not tested but I hope you get the idea..

another attempt would be to sort the stuff and find the first "gap" with an additional iteration after sorting.

old Re: Help with some math please.

Blighted Song
User Off Offline

Quote
I need to find the lowest number that isnt there, the index doesnt matter, for some context;

Im drawing an image onto the players screen when they die, and when they spawn I am removing it, but the image function indexes the images to the lowest index it can find, so to use the freeimage function I need to give it the index of the image the player has, so for example I have
1
2
3
4
5
6
7
8
9
10
11
12
addhook("die","addimage")
function addimage(id)
	ImageArray[id]=--lowest number that hasnt been taken
	image(...)
end

--then kill the image

addhook("spawn","deleteimage")
function deleteimage(id)
	freeimage(ImageArray[id]...)
end

EDIT:

Thanks guys, I have it working now.

old Re: Help with some math please.

DC
Admin Off Offline

Quote
oh.. what the! NO! WAIT!

did you know that the image function actually returns the ID of the image?

simply save that ID somewhere!

old Re: Help with some math please.

Lee
Moderator Off Offline

Quote
For cases in the future where someone may need a data structure that always returns some form of data in some sorted order, what you want is a priority queue. This may be unusually complicated for most purposes though...

So let's assume that we have a data structure with pop and push operation where pop returns the lowest value, then we can have a pre-initialized array of n numbers that forms a bank of ids that can be assigned to individual objects. In which case each pop is associated with one assignment and each push is associated with one clean up / deletion of the object.

In other words, each time we create an image, we borrow a number from this data structure and each time we're done with the image, we pay back the number and the data structure automatically puts it in the correct spot.

What we're looking for then is called a priority queue ( http://en.wikipedia.org/wiki/Priority_queue )

A naive implementation: (assuming that pops are made more often than pushes)
1
2
3
4
5
6
7
8
9
10
function new_pqueue(initial)
	return setmetatable({unpack(initial)}, {
		__index = {pop = function (self) 
			return table.remove(self, 1)
		end, push = function(self, v) 
			table.insert(self, v)
			table.sort(self)
		end}
	})
end

A much more efficient (if you really need it) implementation of the push and pop function are as follows:

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
__index = {push = function(self, v)
	table.insert(self, v)
	local next = #self
	local prev = math.floor(next/2)
	while next > 1 and self[next] < self[prev] do
		-- swap up
		self[next], self[prev] = self[prev], self[next]
		next = prev
		prev = math.floor(next/2)
	end
	self[next] = v
end, 
pop = function(self)
	local r = self[1]
	self[1] = table.remove(self)
	local root = 1
	if #self > 1 then
		local size = #self
		local v = self[root]
		while root < size do
			local child = 2*root
			if child < size then
				if child+1 < size and self[child+1] < self[child] then child = child + 1 end
				if self[child] < self[root] then
					-- swap down
					self[root], self[child] = self[child], self[root]
					root = child
				else
					self[root] = v
					break
				end
			else
				self[root] = v
				break
			end
		end
	end
	
	return r
end}

This uses the same scheme as http://en.wikipedia.org/wiki/Heap_(data_structure) so that the table is constantly kept in sorted order.

More >

old Re: Help with some math please.

FlooD
GAME BANNED Off Offline

Quote
lol lee seriously...

1
2
3
4
5
function lowest(t)
	for k, v in ipairs(t) do
		if tonumber(v) > 0 then return k end
	end
end
O(n) i believe, but n probably < 10 so who cares
To the start Previous 1 Next To the start
Log in to reply Scripts overviewCS2D overviewForums overview