Map 2D array to a 1D array.

BlitzMax Forums/BlitzMax Beginners Area/Map 2D array to a 1D array.

Shortwind

(Posted 2010) [#1]

Ok, I have this code:

c=(((a+b)^2) + (3*a) + b)/2

Simple code to demostrate:

Strict 

Local a:Int=0
Local b:Int=0
Local c:Int=0

For a=0 To 9
	For b=0 To 9
		c=(((a+b)^2) + (3*a) + b)/2
		Print "("+a+","+b+")="+c
	Next
Next

I've used this code in the past to convert a two dimensional array into a one dimensional array. I need to go back the other way, from this setup. In otherwords, I need to map the one dimensional array back into the original two dimensional array.

Um, I can't find the code that goes the other way. LOL I've got it here somewhere, but I'll be buggered if I can find it. I've been using this on and off since the days of the old C64, but my brain doesn't seem to be working to reverse the situation. It's so simple too, that's so embarrassing.

Anyone know of the reverse to this code, off hand?

Floyd

(Posted 2010) [#2]

All variables are integers. c originally came from non-negative a,b.

s = Floor( Sqr( 1 + 8*c ) )
s = ( s - 1 ) / 2
a = c - s*(s+1)/2
b = s - a

I just realized this is a BlitzMax forum. In that case the Floor is superfluous. But it is needed in earlier Blitz's, which converted float to integer by rounding.

Shortwind

(Posted 2010) [#3]

Floyd thanks. This routine works well.

Warpy

(Posted 2010) [#4]

I'm sure there doesn't need to be a square term in the 2d-1d function.

Suppose you've got an MxN array.
Reading from left to right and top to bottom in the array, if you're on column I and row J, then you've already passed J*M+I cells, so that number should be the position in the 1d array where you store the cell [I,J]. To work out I and J from a position C in the 1d array, notice that I = C Mod M, and then J=(C-I)/M.

Here's some code

SuperStrict

Local m:Int=2, n:Int=3
Local arr2d:Int[m,n]

Local show$=""
Local i:Int,j:Int
Print "arr2d~n====="
For j=0 To n-1
For i=0 To m-1
	arr2d[i,j] = Rand(1,10)
	show:+String(arr2d[i,j])+" "
Next
show:+"~n"
Next
Print show

Local arr1d:Int[] = twoToOne(arr2d)

show=""
Local c:Int
For c=0 To Len(arr1d)-1
	i=c Mod m
	j=(c-i)/m
	show:+arr1d[c]+" "
	If i=m-1 Then show:+"~n"
Next
Print show


Function twoToOne:Int[](arr2d:Int[,])
	'converts 2d array into 1d array
	Local m:Int=arr2d.dimensions()[0]
	Local n:Int=arr2d.dimensions()[1]
	
	Local arr1d:Int[m*n]
	
	Local i:Int,j:Int,c:Int
	For i=0 To m-1
	For j=0 To n-1
		arr1d[j*m+i]=arr2d[i,j]
	Next
	Next
	Return arr1d
End Function

Shortwind

(Posted 2010) [#5]

Warpy, very nice. :)

Floyd

(Posted 2010) [#6]

I'm sure there doesn't need to be a square term in the 2d-1d function.

I would consider j*m to be a square term.

The original version is based on triangles. The s*(s+1) are called the triangular numbers.

Inverting this scheme ( c back to a,b ) is more complicated. The benefit is that you don't need to know M,N.

' s represents the sum a+b, where a,b are non-negative integers.
' c was originally calculated from a,b as  c = s*(s+1)/2 + b
'
' This shows how to recover a,b from c.

Local a:Int, b:Int, c:Int, s:Int

For c = 0 To 14
	s = Sqr( 1 + 8*c )    ' NOTE: BlitzMax chops floating point values to integer.
	s = ( s - 1 ) / 2     ' s is a+b
	a = c - s*(s+1)/2
	b = s - a
	
	If a = 0 Then Print ; Write  s + ":  "
	Write String(a) + String(b) + " "
Next

Print

Function Write( str$="" )                   ' Like the old Blitz Write
	StandardIOStream.WriteString str
End Function

Warpy

(Posted 2010) [#7]

I knew I should have thought about that code for a while before pooh-poohing it!