Two-Dimensional Lists

Please expand this article or section. You can help by adding more information if you are an editor. (July 2022)

Note:

Still in progress 30/8/2026

This tutorial explains how to make a two-dimensional list. A 2D list is a list whose contents are also lists. Those lists are said to be nested. Two-dimensional lists are not a feature included in Scratch, but it can be simulated with regular lists. Unlike a 2D array, 2D lists (specifically those nested) can be of different lengths.

3 List Method

This method uses the following three lists:

(elements::list) — stores all the items of the nested lists
(pointers::list) — stores where each nested list starts in the elements list
(lengths::list) — stores the length of each nested list, in parallel with the pointers list.

Because all items are stored in the (elements::list) list, inserting or deleting them will shift all items after. The (pointers::list) and (lengths::list) lists need to be updated to account for this.

This tutorial will implement lists that are indexed from 1, like Scratch's in-built lists.

Custom blocks will be used for readability and maintainability. Return values will be stored in a variable named (return). Arguments for the indices of the list and nested list will be called (index0) and (index1), respectively.

Adding a Nested List

These blocks add nested lists to the main two lists.

define add empty list
add ((length of [elements v]) + (1)) to [pointers v]
add [0] to [lengths v]

Get Length of Nested List

define get length of list (index0)
set [return v] to (item (index0) of [lengths v])

Get Item

define get item at  (index0) (index1)
if <(item (index0) of [lengths v]) and <<(index1) > [0]> and <not <(index1) > (item (index0) of [lengths v])>>>> then // check if indices are in bounds
  set [return v] to (item (((item (index0) of [pointers v]) + (index1)) - (1)) of [elements v])
else
  set [return v] to [] // out of bounds, return empty string
end

Replace Item

define replace item at (index0) (index1) with (value)
if <(item (index0) of [lengths v]) and <<(index1) > [0]> and <not <(index1) > (item (index0) of [lengths v])>>>> then // bounds check
  replace item (((item (index0) of [pointers v]) + (index1)) - (1)) of [elements v] with (value)
end

Add Item

define add (value) to list (index0)
if <(item (index0) of [pointers v]) and <(length of [elements v]::data) < [200000]>> then // bounds check
  insert (value) at ((item (index0) of [pointers v]) + (item (index0) of [lengths v])) of [elements v]
  replace item (index0) of [lengths v] with ((item (index0) of [lengths v]) + (1))
  set [list i v] to (index0)
  repeat ((length of [pointers v]::data) - (index0)) // update pointers
    change [i v] by (1)
    replace item (list i) of [pointers v] with ((item (list i) of [pointers v]) + (1)) // increase by 1 item
  end
end

The Canton Pairing Function

Though the Canton Pairing Function is not exactly a type of 2D list, it is able to organise integer cartesian coordinates into a 1D list.

Disclamer

The Canton Pairing Function is only able to handle rational numbers with a maximum of 'n' decimal places. Though it is made for integers, it is possible to times the coordinates by 10ⁿ , and then multiple the coordinates from the Inverse Canton Function by 10^-n.

Formula - Canton Pairing Function

The formula for the Canton function is as followed (the pi symbol is the function symbol, not the circle pi):

$π (x, y) = \frac{(x + y) (x + y + 1)}{2} + y$ ^[1], additional text.> , where x and y are positive integers (including 0). This formula give a unique positive integer index for each coordinate.

Formula - Inverse Canton Pairing Function

The Inverse Canton Pairing Function is the formula to convert the positive integer from the Canton Pairing Function, back into the original coordinates. The formula for the Inverse Canton Pairing Function is as followed:

$w = ⌊ \frac{\sqrt{8 z + 1} - 1}{2} ⌋$

$t = \frac{w^{2} + w}{2}$

$x = w - z + t$

$y = z - t$ , where x is the index given, and t and w are temparary variables^[2]

Code

The Canton Pairing Function and Inverse Canton Pairing Function are easily able to be created in scratch.

Canton Pairing Function

define Convert x:(x) y:(y) into index
set [idx v] to (((((x)+(y))*(((x)+(y))+(1)))/(2))+(y))

Inverse Canton Pairing Function

define Convert Index:(idx) to x, y
set [Temp v] to ([floor v] of ((([sqrt v] of (((8)*(idx))+(1)))-(1))/(2)))
set [y v] to ((idx)-((((Temp)*(Temp))+(Temp))/(2)))
set [x v] to ((Temp)-(y))

Function

This code converts 2 positive cartesian coordinates into a unique index, while also being able to reverse it. However, this only is able to utilise one quadrant out of four.

Extended Canton Pairing Function

To make this code able to work with any integer coordinate, it is necessary to be able to match all integers $[ℤ ∋ [. . . - 2, - 1, 0, 1, 2 . . .]]$ , to the Natural Numbers including 0, $[ℕ ∋ [0, 1, 2, 3, 4, . . .]]$ . One possible way to do this is to make negative numbers odd, and positive numbers evens. As a formula, this would be $f (x) = {\begin{cases} - 2 x - 1 & if x < 0 \\ 2 x & if x \geq 0 \end{cases}$

The inverse formula for this would be: $f (x) = {\begin{cases} \frac{x}{2} & if x \equiv 0 (\mod 2) \\ \frac{(x + 1)}{2} & if x \equiv 1 (\mod 2) \end{cases}$

Matching Code

This created in scratch blocks would be as followed:

Define Transform (n)
if <(n)<(0)> then
set [Temp v] to (((-2)*(n))-(1))
else
set [Temp v] to ((2)*(n))

The Inverse Matching Function would be as followed:

Define Untransform (n)
if <((n) mod (2))=(0)> then
set [Temp v] to ((n)/(2))
else
set [Temp v] to (((n)+(1))/(2))

Full Code

The matching code above, combined with the Canton Pairing Function, is all that is needed to make a Extended Canton Pairing Function to apply to all integers.

define Convert x:(x) y:(y) into index
Transform (x)::custom
set [x v] to (Temp)
Transform (y)::custom
set [y v] to (Temp)
set [idx v] to (((((x::variables)+(y::variables))*(((x::variables)+(y::variables))+(1)))/(2))+(y::variables))

define Convert Index:(idx) to x, y
set [Temp v] to ([floor v] of ((([sqrt v] of (((8)*(idx))+(1)))-(1))/(2)))
set [y v] to ((idx)-((((Temp)*(Temp))+(Temp))/(2)))
set [x v] to ((Temp)-(y))
Untransform (x)::custom
set [x v] to (Temp)
Untransform (y)::custom
set [y v] to (Temp)

String Encoding Method

This method uses data serialization to store the nested lists as strings, which are then placed in another list.

For this method, you will need the lists:

(Storage::list) — stores the strings of lists
(Compress::list) — helps compress and decompress the lists
(Names::list) — stores the names of the rows

You will also need the variables:

(Character)
(Index)
(Item)
(string)

To start, data serialization scripts will need to be made. We will need 2 define blocks:

define Compile (item)
...
define Decompile
...

A script to convert items into 1 string will also be necessary

define Compile (item)
set [Index v] to (1)
repeat (length of (item))
set [Character v] to (letter (Index) of (item))
if <[|~] contains(Character)?> then
set [String v] to (join (String) [~]
end
set [String v] to (join (String) (Character)
change [Index v] by (1)
end
set [String v] to (join (String) [|]

Next, a script to decompile the string into the items is needed to be made

define Decompile
set [Item v] to ()
forever
set [Character v] to (letter (Index) of (String)
change [Index v] by (1)
if <[|] contains (Character)?> then
stop [this script v]
end
if<[~] contains (Character)?> then
set [Character v] to (letter (Index) of (String))
change [Index v] by (1)
end
set [Item v] to (join (Item)(Character))

With the data serialization scripts completed, we will now need a way to read and write the compressed rows to turn them into lists.

define Read (row)//The input 'row' is to be the name of the row
delete all of [Compress v]
set [String v] to (item (item # of (row) in [Names v]) of [Store v])
set [Index v] to (1)
Decompile::custom
repeat until <(item) = ()>
add (item) to [Compress v]
Decompile::custom

define Write (row)//The input 'row' is to be the name of the row
set [string v] to ()
repeat (length of [Compress v])
Compile (item (1) of [Compress v])::custom
delete (1) of [Compress v]
end
replace item (item # of (row) in [Names v]) of [Store v] with (String)

With the data serialization, and read and write scripts done, we will now focus on initiating the 2D list. To start we will reset the lists:

when gf clicked
delete all of [Store v]
delete all of [Compress v]
delete all of [Names v]

The blocks below will edit the rows of the 2D list.

define Add row (name)
add (name) to [Names v]
add () to [Store v]

define Delete row (name)
delete (name) of [Names v]
delete (name) of [Store v]


define Insert row (name) at (position)
insert (name) at (position) of [Names v]
insert () at (position) of [Store v]

define Replace row (oldname) with row (name) and data (data)
replace item (item # of (oldname) in [Names v]) of [Names v] with (name)
replace item (item # of (name) in [Names v]) of [Store v] with (data)

The below blocks will edit the nested lists

define Add (item) to (name)
Read (name)::custom
add (item) to [Compress v]
Write (name)::custom

define Delete (item#) of (name)
Read (name)::custom
delete (position) of [Compress v]
Write (name)::custom

define Insert (item) at (position) of (name)
Read (name)::custom
insert (item) at (position) of [Compress v]
Write (name)::custom
define Replace item (position) of (name) with (item)
Read (name)::custom
replace item (position) of [Compress v] with (item)
Write (name)::custom

These custom blocks all act as list blocks. The following table will list the custom block, the function of the block, and the effect of the block. The effects will be based on the following 2D list:

Block	Role	Effect
Add row [Lizard]::custom define Add row (name) ...	This custom block adds a row to the end of the 2-Dimensional list
Delete row [Snakes]::custom define Delete row (name) ...	This custom block deletes a specified row
Insert row [Lizards] at [3]::custom define Insert row (name) at (position) ...	This custom block inserts a row at the specified position
	This custom block replaces a specified row and its data
Add [Goose] to [Birds]::custom define Add (item) to (name) ...	This custom block adds an item to the end of a specified row
Delete [2] of [Cats]::custom define Delete (position) of (name) ...	This custom block deletes an item specified by its position in a specified row
	This custom block inserts an item at a position in a specified row
	This custom block replaces an item in a specified row for another item