Stacks¶
0. Introduction¶
What to do¶
unzip exercises in a folder, you should get something like this:
stacks
stacks.ipynb
capped_stack.py
capped_stack_sol.py
capped_stack_test.py
...
jupman.py
sciprog.py
open the editor of your choice (for example Visual Studio Code, Spyder or PyCharme), you will edit the files ending in
.py
filesGo on reading this notebook, and follow instuctions inside
1. CappedStack¶
You will try to implement a so called capped stack, which has a limit called cap over which elements are discarded.
Your internal implementation will use python lists
Please name internal variables that you don’t want to expose to class users by prepending them with one underscore
'_'
, like_elements
or_cap
The underscore is just a convention, class users will still be able to get internal variables by accessing them with field accessors like
mystack._elements
If users manipulate private fields and complain something is not working, you can tell them it’s their fault!
try to write robust code. In general, when implementing code in the real world you might need to think more about boundary cases. In this case, we add the additional constraint that if you pass to the stack a negative or zero cap, your class initalization is expected to fail and raise a
ValueError
.For easier inspection of the stack, implement also an
__str__
method so that calls toprint
show text likeCappedStack: cap=4 elements=['a', 'b']
IMPORTANT: you can exploit any Python feature you deem correct to implement the data structure. For example, internally you could represent the elements as a list , and use its own methods to grow it.
QUESTION: If we already have Python lists that can more or less do the job of the stack, why do we need to wrap them inside a Stack? Can’t we just give our users a Python list?
QUESTION: When would you not use a Python list to hold the data in the stack?
Notice that:
We tried to use pythonic names for methods, so for example
isEmpty
was renamed tois_empty
In this case, when this stack is required to
pop
orpeek
but it is found to be empty, anIndexError
is raised
CappedStack Examples¶
To get an idea of the class to be made, in the terminal you may run the python interpreter and load the solution module like we are doing here:
[2]:
from capped_stack_sol import *
[3]:
s = CappedStack(2)
[4]:
print(s)
CappedStack: cap=2 elements=[]
[5]:
s.push('a')
[6]:
print(s)
CappedStack: cap=2 elements=['a']
[7]:
s.peek()
[7]:
'a'
[8]:
s.push('b')
[9]:
s.peek()
[9]:
'b'
[10]:
print(s)
CappedStack: cap=2 elements=['a', 'b']
[11]:
s.peek()
[11]:
'b'
[12]:
s.push('c') # exceeds cap, gets silently discarded
[13]:
print(s) # no c here ...
CappedStack: cap=2 elements=['a', 'b']
[14]:
s.pop()
[14]:
'b'
[15]:
print(s)
CappedStack: cap=2 elements=['a']
[16]:
s.pop()
[16]:
'a'
s.pop() # can't pop empty stack
---------------------------------------------------------------------------
IndexError Traceback (most recent call last)
<ipython-input-41-c88c8c48122b> in <module>()
----> 1 s.pop()
~/Da/prj/sciprog-ds/prj/stacks/capped_stack_sol.py in pop(self)
63 #jupman-raise
64 if len(self._elements) == 0:
---> 65 raise IndexError("Empty stack !")
66 else:
67 return self._elements.pop()
IndexError: Empty stack !
s.peek() # can't peek empty stack
---------------------------------------------------------------------------
IndexError Traceback (most recent call last)
<ipython-input-18-f056e7e54f5d> in <module>()
----> 1 s.peek()
~/Da/prj/sciprog-ds/prj/stacks/capped_stack_sol.py in peek(self)
77 #jupman-raise
78 if len(self._elements) == 0:
---> 79 raise IndexError("Empty stack !")
80
81 return self._elements[-1]
IndexError: Empty stack !
Capped Stack basic methods¶
Now open capped_stack.py
and start implementing the methods in the order you find them.
All basic methods are grouped within the CappedStackTest class: to execute single tests you can put the test method name after the test class name, see examples below.
1.1 __init__
¶
Test: python3 -m unittest capped_stack_test.CappedStackTest.test_01_init
1.2 cap¶
Test: python3 -m unittest capped_stack_test.CappedStackTest.test_02_cap
1.3 size¶
Test: python3 -m unittest capped_stack_test.CappedStackTest.test_03_size
1.4 __str__
¶
Test: python3 -m unittest capped_stack_test.CappedStackTest.test_04_str
1.5 is_empty¶
Test: python3 -m unittest capped_stack_test.CappedStackTest.test_05_is_empty
1.6 push¶
Test: python3 -m unittest capped_stack_test.CappedStackTest.test_06_push
1.7 peek¶
Test: python3 -m unittest capped_stack_test.CappedStackTest.test_07_peek
1.8 pop¶
Test: python3 -m unittest capped_stack_test.CappedStackTest.test_08_pop
1.9 peekn¶
Implement the peekn
method:
def peekn(self, n):
"""
RETURN a list with the n top elements, in the order in which they
were pushed. For example, if the stack is the following:
e
d
c
b
a
peekn(3) will return the list ['c','d','e']
- If there aren't enough element to peek, raises IndexError
- If n is negative, raises an IndexError
"""
raise Exception("TODO IMPLEMENT ME!")
Test: python3 -m unittest capped_stack_test.PeeknTest
1.10 popn¶
Implement the popn
method:
def popn(self, n):
""" Pops the top n elements, and RETURN them as a list, in the order in
which they where pushed. For example, with the following stack:
e
d
c
b
a
popn(3)
will give back ['c','d','e'], and stack will become:
b
a
- If there aren't enough element to pop, raises an IndexError
- If n is negative, raises an IndexError
"""
Test: python3 -m unittest capped_stack_test.PopnTest
1.11 set_cap¶
Implement the set_cap
method:
def set_cap(self, cap):
""" MODIFIES the cap, setting its value to the provided cap.
If the cap is less then the stack size, all the elements above
the cap are removed from the stack.
If cap < 1, raises an IndexError
Does *not* return anything!
For example, with the following stack, and cap at position 7:
cap -> 7
6
5 e
4 d
3 c
2 b
1 a
calling method set_cap(3) will change the stack to this:
cap -> 3 c
2 b
1 a
"""
Test: python3 -m unittest capped_stack_test.SetCapTest
2. SortedStack¶
You are given a class SortedStack
that models a simple stack. This stack is similar to the CappedStack
you already saw, the differences being:
it can only contain integers, trying to put other type of values will raise a
ValueError
integers must be inserted sorted in the stack, either ascending or descending
there is no cap
Example:
Ascending: Descending
8 3
5 5
3 8
[17]:
from sorted_stack_sol import *
To create a SortedStack
sorted in ascending order, just call it passing True
:
[18]:
s = SortedStack(True)
print(s)
SortedStack (ascending): elements=[]
[19]:
s.push(5)
print(s)
SortedStack (ascending): elements=[5]
[20]:
s.push(7)
print(s)
SortedStack (ascending): elements=[5, 7]
[21]:
print(s.pop())
7
[22]:
print(s)
SortedStack (ascending): elements=[5]
[23]:
print(s.pop())
5
[24]:
print(s)
SortedStack (ascending): elements=[]
For descending order, pass False
when you create it:
[25]:
sd = SortedStack(False)
sd.push(7)
sd.push(5)
sd.push(4)
print(sd)
SortedStack (descending): elements=[7, 5, 4]
2.1 transfer¶
Now implement the transfer
function.
NOTE: function is external to class SortedStack
, so you must NOT access fields which begin with underscore (like _elements
), which are meant to be private !!
def transfer(s):
""" Takes as input a SortedStack s (either ascending or descending) and
returns a new SortedStack with the same elements of s, but in reverse order.
At the end of the call s will be empty.
Example:
s result
2 5
3 3
5 2
"""
raise Exception("TODO IMPLEMENT ME !!")
Testing
Once done, running this will run only the tests in TransferTest
class and hopefully they will pass.
**Notice that exercise1
is followed by a dot and test class name .TransferTest
: **
python -m unittest sorted_stack_test.TransferTest
2.2 merge¶
Implement following merge
function. NOTE: function is external to class SortedStack
.
def merge(s1,s2):
""" Takes as input two SortedStacks having both ascending order,
and returns a new SortedStack sorted in descending order, which will be the sorted merge
of the two input stacks. MUST run in O(n1 + n2) time, where n1 and n2 are s1 and s2 sizes.
If input stacks are not both ascending, raises ValueError.
At the end of the call the input stacks will be empty.
Example:
s1 (asc) s2 (asc) result (desc)
5 7 2
4 3 3
2 4
5
7
"""
raise Exception("TODO IMPLEMENT ME !")
Testing: python -m unittest sorted_stack_test.MergeTest
3. WStack¶
Using a text editor, open file wstack.py
. You will find a WStack
class skeleton which represents a simple stack that can only contain integers.
3.1 implement class WStack¶
Fill in missing methods in class WStack
in the order they are presented so to have a .weight()
method that returns the total sum of integers in the stack in O(1)
time.
Example:
[26]:
from wstack_sol import *
[27]:
s = WStack()
[28]:
print(s)
WStack: weight=0 elements=[]
[29]:
s.push(7)
[30]:
print(s)
WStack: weight=7 elements=[7]
[31]:
s.push(4)
[32]:
print(s)
WStack: weight=11 elements=[7, 4]
[33]:
s.push(2)
[34]:
s.pop()
[34]:
2
[35]:
print(s)
WStack: weight=11 elements=[7, 4]
3.2 accumulate¶
Implement function accumulate
:
def accumulate(stack1, stack2, min_amount):
""" Pushes on stack2 elements taken from stack1 until the weight of
stack2 is equal or exceeds the given min_amount
- if the given min_amount cannot possibly be reached because
stack1 has not enough weight, raises early ValueError without
changing stack1.
- DO NOT access internal fields of stacks, only use class methods.
- MUST perform in O(n) where n is the size of stack1
- NOTE: this function is defined *outside* the class !
"""
Testing: python -m unittest wstack_test.AccumulateTest
Example:
[36]:
s1 = WStack()
print(s1)
WStack: weight=0 elements=[]
[37]:
s1.push(2)
s1.push(9)
s1.push(5)
s1.push(3)
[38]:
print(s1)
WStack: weight=19 elements=[2, 9, 5, 3]
[39]:
s2 = WStack()
print(s2)
WStack: weight=0 elements=[]
[40]:
s2.push(1)
s2.push(7)
s2.push(4)
[41]:
print(s2)
WStack: weight=12 elements=[1, 7, 4]
[42]:
# attempts to reach in s2 a weight of at least 17
[43]:
accumulate(s1,s2,17)
[44]:
print(s1)
WStack: weight=11 elements=[2, 9]
Two top elements were taken from s1 and now s2 has a weight of 20, which is >= 17
4. Backpack¶
Open a text editor and edit file backpack_sol.py
We can model a backpack as stack of elements, each being a tuple with a name and a weight.
A sensible strategy to fill a backpack is to place heaviest elements to the bottom, so our backback will allow pushing an element only if that element weight is equal or lesser than current topmost element weight.
The backpack has also a maximum weight: you can put any number of items you want, as long as its maximum weight is not exceeded.
Example
[45]:
from backpack_sol import *
bp = Backpack(30) # max_weight = 30
bp.push('a',10) # item 'a' with weight 10
DEBUG: Pushing (a,10)
[46]:
print(bp)
Backpack: weight=10 max_weight=30
elements=[('a', 10)]
[47]:
bp.push('b',8)
DEBUG: Pushing (b,8)
[48]:
print(bp)
Backpack: weight=18 max_weight=30
elements=[('a', 10), ('b', 8)]
>>> bp.push('c', 11)
DEBUG: Pushing (c,11)
ValueError: ('Pushing weight greater than top element weight! %s > %s', (11, 8))
[49]:
bp.push('c', 7)
DEBUG: Pushing (c,7)
[50]:
print(bp)
Backpack: weight=25 max_weight=30
elements=[('a', 10), ('b', 8), ('c', 7)]
>>> bp.push('d', 6)
DEBUG: Pushing (d,6)
ValueError: Can't exceed max_weight ! (31 > 30)
4.1 class¶
✪✪ Implement methods in the class Backpack
, in the order they are shown. If you want, you can add debug prints by calling the debug
function
IMPORTANT: the data structure should provide the total current weight in O(1), so make sure to add and update an appropriate field to meet this constraint.
Testing: python3 -m unittest backpack_test.BackpackTest
4.2 remove¶
✪✪ Implement function remove
:
# NOTE: this function is implemented *outside* the class !
def remove(backpack, el):
"""
Remove topmost occurrence of el found in the backpack,
and RETURN it (as a tuple name, weight)
- if el is not found, raises ValueError
- DO *NOT* ACCESS DIRECTLY FIELDS OF BACKPACK !!!
Instead, just call methods of the class!
- MUST perform in O(n), where n is the backpack size
- HINT: To remove el, you need to call Backpack.pop() until
the top element is what you are looking for. You need
to save somewhere the popped items except the one to
remove, and then push them back again.
"""
Testing: python3 -m unittest backpack_test.RemoveTest
Example:
[51]:
bp = Backpack(50)
bp.push('a',9)
bp.push('b',8)
bp.push('c',8)
bp.push('b',8)
bp.push('d',7)
bp.push('e',5)
bp.push('f',2)
DEBUG: Pushing (a,9)
DEBUG: Pushing (b,8)
DEBUG: Pushing (c,8)
DEBUG: Pushing (b,8)
DEBUG: Pushing (d,7)
DEBUG: Pushing (e,5)
DEBUG: Pushing (f,2)
[52]:
print(bp)
Backpack: weight=47 max_weight=50
elements=[('a', 9), ('b', 8), ('c', 8), ('b', 8), ('d', 7), ('e', 5), ('f', 2)]
[53]:
remove(bp, 'b')
DEBUG: Popping ('f', 2)
DEBUG: Popping ('e', 5)
DEBUG: Popping ('d', 7)
DEBUG: Popping ('b', 8)
DEBUG: Pushing (d,7)
DEBUG: Pushing (e,5)
DEBUG: Pushing (f,2)
[53]:
('b', 8)
[54]:
print(bp)
Backpack: weight=39 max_weight=50
elements=[('a', 9), ('b', 8), ('c', 8), ('d', 7), ('e', 5), ('f', 2)]
[55]:
print(s2)
WStack: weight=20 elements=[1, 7, 4, 3, 5]
5. Tasks¶
Very often, you begin to do a task just to discover it requires doing 3 other tasks, so you start carrying them out one at a time and discover one of them actually requires to do yet another two other subtasks….
To represent the fact a task may have subtasks, we will use a dictionary mapping a task label to a list of subtasks, each represented as a label. For example:
[56]:
subtasks = {
'a':['b','g'],
'b':['c','d','e'],
'c':['f'],
'd':['g'],
'e':[],
'f':[],
'g':[]
}
Task a
requires subtasks b
andg
to be carried out (in this order), but task b
requires subtasks c
, d
and e
to be done. c
requires f
to be done, and d
requires g
.
You will have to implement a function called do
and use a Stack data structure, which is already provided and you don’t need to implement. Let’s see an example of execution.
IMPORTANT: In the execution example, there are many prints just to help you understand what’s going on, but the only thing we actually care about is the final list returned by the function!
IMPORTANT: notice subtasks are scheduled in reversed order, so the item on top of the stack will be the first to get executed !
[57]:
from tasks_sol import *
do('a', subtasks)
DEBUG: Stack: elements=['a']
DEBUG: Doing task a, scheduling subtasks ['b', 'g']
DEBUG: Stack: elements=['g', 'b']
DEBUG: Doing task b, scheduling subtasks ['c', 'd', 'e']
DEBUG: Stack: elements=['g', 'e', 'd', 'c']
DEBUG: Doing task c, scheduling subtasks ['f']
DEBUG: Stack: elements=['g', 'e', 'd', 'f']
DEBUG: Doing task f, scheduling subtasks []
DEBUG: Nothing else to do!
DEBUG: Stack: elements=['g', 'e', 'd']
DEBUG: Doing task d, scheduling subtasks ['g']
DEBUG: Stack: elements=['g', 'e', 'g']
DEBUG: Doing task g, scheduling subtasks []
DEBUG: Nothing else to do!
DEBUG: Stack: elements=['g', 'e']
DEBUG: Doing task e, scheduling subtasks []
DEBUG: Nothing else to do!
DEBUG: Stack: elements=['g']
DEBUG: Doing task g, scheduling subtasks []
DEBUG: Nothing else to do!
DEBUG: Stack: elements=[]
[57]:
['a', 'b', 'c', 'f', 'd', 'g', 'e', 'g']
The Stack
you must use is simple and supports push
, pop
, and is_empty
operations:
[58]:
s = Stack()
[59]:
print(s)
Stack: elements=[]
[60]:
s.is_empty()
[60]:
True
[61]:
s.push('a')
[62]:
print(s)
Stack: elements=['a']
[63]:
s.push('b')
[64]:
print(s)
Stack: elements=['a', 'b']
[65]:
s.pop()
[65]:
'b'
[66]:
print(s)
Stack: elements=['a']
5.1 do¶
Now open tasks.py
and implement function do
:
def do(task, subtasks):
""" Takes a task to perform and a dictionary of subtasks,
and RETURN a list of performed tasks
- To implement it, inside create a Stack instance and a while cycle.
- DO *NOT* use a recursive function
- Inside the function, you can use a print like "I'm doing task a',
but that is only to help yourself in debugging, only the
list returned by the function will be considered in the evaluation!
"""
Testing: python3 -m unittest tasks_test.DoTest
5.2 do_level¶
In this exercise, you are asked to implement a slightly more complex version of the previous function where on the Stack
you push two-valued tuples, containing the task label and the associated level. The first task has level 0, the immediate subtask has level 1, the subtask of the subtask has level 2 and so on and so forth. In the list returned by the function, you will put such tuples.
One possibile use is to display the executed tasks as an indented tree, where the indentation is determined by the level. Here we see an example:
IMPORTANT: Again, the prints are only to let you understand what’s going on, and you are not required to code them. The only thing that really matters is the list the function must return !
[67]:
subtasks = {
'a':['b','g'],
'b':['c','d','e'],
'c':['f'],
'd':['g'],
'e':[],
'f':[],
'g':[]
}
do_level('a', subtasks)
DEBUG: Stack: elements=[('a', 0)]
DEBUG: I'm doing a level=0 Stack: elements=[('g', 1), ('b', 1)]
DEBUG: I'm doing b level=1 Stack: elements=[('g', 1), ('e', 2), ('d', 2), ('c', 2)]
DEBUG: I'm doing c level=2 Stack: elements=[('g', 1), ('e', 2), ('d', 2), ('f', 3)]
DEBUG: I'm doing f level=3 Stack: elements=[('g', 1), ('e', 2), ('d', 2)]
DEBUG: I'm doing d level=2 Stack: elements=[('g', 1), ('e', 2), ('g', 3)]
DEBUG: I'm doing g level=3 Stack: elements=[('g', 1), ('e', 2)]
DEBUG: I'm doing e level=2 Stack: elements=[('g', 1)]
DEBUG: I'm doing g level=1 Stack: elements=[]
[67]:
[('a', 0),
('b', 1),
('c', 2),
('f', 3),
('d', 2),
('g', 3),
('e', 2),
('g', 1)]
Now implement the function:
def do_level(task, subtasks):
""" Takes a task to perform and a dictionary of subtasks,
and RETURN a list of performed tasks, as tuples (task label, level)
- To implement it, use a Stack and a while cycle
- DO *NOT* use a recursive function
- Inside the function, you can use a print like "I'm doing task a',
but that is only to help yourself in debugging, only the
list returned by the function will be considered in the evaluation
"""
Testing: python3 -m unittest tasks_test.DoLevelTest
6. Stacktris¶
Open a text editor and edit file stacktris.py
A Stacktris
is a data structure that operates like the famous game Tetris, with some restrictions:
Falling pieces can be either of length 1 or 2. We call them
1-block
and2-block
respectivelyThe pit has a fixed width of 3 columns
2-block
s can only be in horizontal
We print a Stacktris
like this:
\ j 012
i
4 | 11| # two 1-block
3 | 22| # one 2-block
2 | 1 | # one 1-block
1 |22 | # one 2-block
0 |1 1| # on the ground there are two 1-block
In Python, we model the Stacktris
as a class holding in the variable _stack
a list of lists of integers, which models the pit:
class Stacktris:
def __init__(self):
""" Creates a Stacktris
"""
self._stack = []
So in the situation above the _stack
variable would look like this (notice row order is inverted with respect to the print)
[
[1,0,1],
[2,2,0],
[0,1,0],
[0,2,2],
[0,1,1],
]
The class has three methods of interest which you will implement, drop1(j)
, drop2h(j)
and _shorten
Example
Let’s see an example:
[68]:
from stacktris_sol import *
st = Stacktris()
At the beginning the pit is empty:
[69]:
st
[69]:
Stacktris:
EMPTY
We can start by dropping from the ceiling a block of dimension 1 into the last column at index j=2
. By doing so, a new row will be created, and will be a list containing the numbers [0,0,1]
IMPORTANT: zeroes are not displayed
[70]:
st.drop1(2)
DEBUG: Stacktris:
| 1|
[70]:
[]
Now we drop an horizontal block of dimension 2 (a 2-block
) having the leftmost block at column j=1
. Since below in the pit there is already the 1
block we previosly put, the new block will fall and stay upon it. Internally, we will add a new row as a python list containing the numbers [0,2,2]
[71]:
st.drop2h(1)
DEBUG: Stacktris:
| 22|
| 1|
[71]:
[]
We see the zeroth column is empty, so if we drop there a 1-block
it will fall to the ground. Internally, the zeroth list will become [1,0,1]
:
[72]:
st.drop1(0)
DEBUG: Stacktris:
| 22|
|1 1|
[72]:
[]
Now we drop again a 2-block
at column j=2
, on top of the previously laid one. This will add a new row as list [0,2,2]
.
[73]:
st.drop2h(1)
DEBUG: Stacktris:
| 22|
| 22|
|1 1|
[73]:
[]
In the game Tetris, when a row becomes completely filled it disappears. So if we drop a 1-block
to the leftmost column, the mid line should be removed.
NOTE: The messages on the console are just debug print, the function drop1
only returns the extracted line [1,2,2]
:
[74]:
st.drop1(0)
DEBUG: Stacktris:
| 22|
|122|
|1 1|
DEBUG: POPPING [1, 2, 2]
DEBUG: Stacktris:
| 22|
|1 1|
[74]:
[1, 2, 2]
Now we insert another 2-block
starting at j=0
. It will fall upon the previously laid one:
[75]:
st.drop2h(0)
DEBUG: Stacktris:
|22 |
| 22|
|1 1|
[75]:
[]
We can complete teh topmost row by dropping a 1-block
to the rightmost column. As a result, the row will be removed from the stack and the row will be returned by the call to drop1
:
[76]:
st.drop1(2)
DEBUG: Stacktris:
|221|
| 22|
|1 1|
DEBUG: POPPING [2, 2, 1]
DEBUG: Stacktris:
| 22|
|1 1|
[76]:
[2, 2, 1]
Another line completion with a drop1
at column j=0
:
[77]:
st.drop1(0)
DEBUG: Stacktris:
|122|
|1 1|
DEBUG: POPPING [1, 2, 2]
DEBUG: Stacktris:
|1 1|
[77]:
[1, 2, 2]
We can finally empty the Stacktris by dropping a 1-block
in the mod column:
[78]:
st.drop1(1)
DEBUG: Stacktris:
|111|
DEBUG: POPPING [1, 1, 1]
DEBUG: Stacktris:
EMPTY
[78]:
[1, 1, 1]
6.1 _shorten¶
Start by implementing this private method:
def _shorten(self):
""" Scans the Stacktris from top to bottom searching for a completely filled line:
- if found, remove it from the Stacktris and return it as a list.
- if not found, return an empty list.
"""
If you wish, you can add debug prints but they are not mandatory
Testing: python3 -m unittest stacktris_test.ShortenTest
6.2 drop1¶
Once you are done with the previous function, implement drop1
method:
NOTE: In the implementation, feel free to call the previously implemented _shorten
method.
def drop1(self, j):
""" Drops a 1-block on column j.
- If another block is found, place the 1-block on top of that block,
otherwise place it on the ground.
- If, after the 1-block is placed, a row results completely filled, removes
the row and RETURN it. Otherwise, RETURN an empty list.
- if index `j` is outside bounds, raises ValueError
"""
Testing: python3 -m unittest stacktris_test.Drop1Test
6.3 drop2h¶
Once you are done with the previous function, implement drop2
method:
def drop2h(self, j):
""" Drops a 2-block horizontally with left block on column j,
- If another block is found, place the 2-block on top of that block,
otherwise place it on the ground.
- If, after the 2-block is placed, a row results completely filled,
removes the row and RETURN it. Otherwise, RETURN an empty list.
- if index `j` is outside bounds, raises ValueError
"""
Testing: python3 -m unittest stacktris_test.Drop2hTest
[ ]: