Recursion, Data Structures
Note: This is a long code challenge in four parts — each part a little harder than the previous.
In this challenge, you’ll be writing code to handle squares and “split squares”.
A square can be a “simple square”, where it’s either empty or filled:
+----+ +----+
| | |####|
+----+ +----+
A square can be divided into a “split square” of four squares:
+---------+
| |####|
|----+----|
| | |
+---------+
Any or all of these can also be further split, so this is a legal square:
+-------------------+
| | |####|
| |----+----|
| |####|####|
|---------+---------|
| | |
| | |
| | |
+-------------------+
This splitting can be arbitrarily deep.
We need a Pythonic way to represent these squares.
We’ll represent a simple square with 1 (filled) or 0 (empty)
+----+ +----+
| | = 0 |####| = 1
+----+ +----+
A split square will be represented with a list of squares, with each item in the list being the (top-left, top-right, bottom-left, bottom-right) parts:
+---------+
| |####|
|----+----| = [0, 1, 0, 0]
| | |
+---------+
These lists can be nested as needed so we can represent further divided squares:
+-------------------+
| | |####|
| |----+----|
| |####|####|
|---------+---------| = [0, [0, 1, 1, 1], 0, 0]
| | |
| | |
| | |
+-------------------+
You could think of this structure as a kind of “recursive list” — any square can contain four squares, so any list item could be another list of four list items.
Make sure you understand this data structural representation before you move forward. You may find it helpful to draw a few squares and write down what the Python list-based representation would be, so that it’s clear in your head.
Squares can be “dumped”, which is when we want to see each square represented as
a 1 or 0 on a separate line.
For a simple square, this would just print 0 or 1.
For this split square:
+---------+
| |####|
|----+----|
| | |
+---------+
Its dump would be:
0
1
0
0
For this split square:
+-------------------+
| | |####|
| |----+----|
| |####|####|
|---------+---------|
| | |
| | |
| | |
+-------------------+
Its dump would be:
0
0
1
1
1
0
0
We want to write a function, dump(square), which will dump out a square.
For example, a simple square will only be one line:
>>> dump(0)
0
>>> dump(1)
1
A split square will use four lines:
>>> dump([0, 1, 0, 1])
0
1
0
1
A nested split square will use one line per square:
>>> dump([0, 0, 0, [1, 1, 1, 1]])
0
0
0
1
1
1
1
Of course, these can nested deeply and still work:
>>> dump([0, 0, 0, [1, 1, 1, [0, 0, 0, [1, 1, 1, 1]]]])
0
0
0
1
1
1
0
0
0
1
1
1
1
As a hint, you’ll want to use recursion here. This first task, of dumping things, will give you a good “skeleton” for the later tasks, as they’ll all need some of the same ideas of “navigating an arbitrarily nested data structure”.
Given our data structures, described above, write a function, validate(square), which takes a square/split square, and returns True if it is valid, and False if it is not.
For example, a simple square is valid:
>>> validate(0)
True
A split square of four simple filled squares is valid:
>>> validate([1, 1, 1, 1])
True
We can nest split and simple squares:
>>> validate([1, 0, [1, [0, 0, 0, 0], 1, [1, 1, 1, 1]], 1])
True
>>> validate([1, [1, 0, 1, [0, [0, 0, 0, 0], 1, 1]], [1, 0, 1, 0], 1])
True
Simple squares must be either 0 (empty) or 1 (filled):
>>> validate(2)
False
Split squares must contain exactly four parts:
>>> validate([1, 1, 1, 1, 1])
False
>>> validate([1, 0, [1, [0, 0, 0, 0, 1], 1, [1, 1, 1, 1]], 1])
False
>>> validate([1, [1, 0, 1, [0, [0, 0, 0], 1, 1]], [1, 0, 1, 0], 1])
False
As a hint, it might be useful to remember that you can test what type of something is in Python using the type function:
if type(s) == int:
print "an int"
elif type(s) == list:
print "a list"
A split square that has all the same squares can be “simplified” into a simple square.
For example, this split square contains four filled squares, so we could simplify the entire thing into one simple filled square:
+---------+ +---------+
|####|####| |#########|
|----+----| => |#########|
|####|####| |#########|
+---------+ +---------+
This works with nested split squares, too:
+-------------------+ +-------------------+
| |####|####| | |#########|
| |----+----| | |#########|
| |####|####| | |#########|
|---------+---------| => |---------+---------|
| | | | | |
| | | | | |
| | | | | |
+-------------------+ +-------------------+
If an inner simplification makes a simple square out of a split square, this could simplify an outer split square:
+-------------------+ +-------------------+
|#########|####|####| |###################|
|#########|----+----| |###################|
|#########|####|####| |###################|
|---------+---------| => |###################|
|#########|#########| |###################|
|#########|#########| |###################|
|#########|#########| |###################|
+-------------------+ +-------------------+
Write a function, simplify(square), that takes in a square and returns the maximally-simplified version of it.
For example, a simple square is already simplified:
>>> simplify(0)
0
A split square containing four simple filled squares can be simplified to a simple filled square:
>>> simplify([1, 1, 1, 1])
1
A split square containing four simple empty squares can be simplified to a simple empty square:
>>> simplify([0, 0, 0, 0])
0
A split square containing mixed squares cannot be simplified:
>>> simplify([1, 0, 1, 0])
[1, 0, 1, 0]
These can be simplified even when nested:
>>> simplify([1, 0, 1, [1, 1, 1, 1]])
[1, 0, 1, 1]
Simplification should nest, so if we can simplify one split square into a simple square and now an outer split square can be simplified, it should:
>>> simplify([1, 1, 1, [1, 1, 1, 1]])
1
>>> simplify([[1, 1, 1, 1], [1, 1, 1, 1], 1, 1])
1
>>> simplify([1, 0, [1, [0, 0, 0, 0], 1, [1, 1, 1, 1]], 1])
[1, 0, [1, 0, 1, 1], 1]
Squares can be added together, using the rule that if either square is filled, the result is filled:
+----+ +----+ +----+
| | + | | = | |
+----+ +----+ +----+
+----+ +----+ +----+
| | + |####| = |####|
+----+ +----+ +----+
+----+ +----+ +----+
|####| + | | = |####|
+----+ +----+ +----+
+----+ +----+ +----+
|####| + |####| = |####|
+----+ +----+ +----+
Split squares can be added with the same rules: for each part, if that part is filled, that part in the result is filled:
+---------+ +---------+ +---------+
| |####| |####| | |####|####|
|----+----| + |----+----| = |----+----|
| | | | | | | | |
+---------+ +---------+ +---------+
Even if one given square is more nested than another, the two squares can still be added. Any part of either square that is filled will be filled in the result square.
For example, if we add a simple empty square and a split square, we’ll get a split square with those same splits filled:
+---------+ +---------+ +---------+
| | |####| | |####| |
| | + |----+----| = |----+----|
| | | | | | | |
+---------+ +---------+ +---------+
Or, as a more complex version of that same idea:
+-------------------+ +-------------------+ +-------------------+
| | |####| | | | | | | | |####|
| |----+----| |----+----| | |----+----|----+----|
| | | | | |####| | | |####| | |
|---------+---------| + |---------+---------| = |---------+---------|
|####| | | |####| | | |####| | |
|----+----| | |----+----| | |----+----| |
| | | | | |####| | | |####| |
+-------------------+ +-------------------+ +-------------------+
Write a function, add(square, square), that adds together two squares.
For example, two simple squares can be added:
>>> s1 = 0
>>> s2 = 1
>>> add(s1, s2)
1
A simple square and a split square can be added:
>>> s1 = 0
>>> s2 = [1, 0, 1, 0]
>>> add(s1, s2)
[1, 0, 1, 0]
Two split squares can be added:
>>> s1 = [0, 0, 0, 1]
>>> s2 = [0, 1, 0, 1]
>>> add(s1, s2)
[0, 1, 0, 1]
Nested squares can be added:
>>> s1 = [0, [1, 1, 1, [0, 0, 0, 0]], [0, 0, 0, 0], 1]
>>> s2 = [1, [1, 0, 1, [0, 0, 1, 1]], [1, 0, 1, 0], 1]
>>> add(s1, s2)
[1, [1, 1, 1, [0, 0, 1, 1]], [1, 0, 1, 0], 1]
Unevenly-nested squares can be added:
>>> s1 = [0, [1, 1, 1, 0 ], [0, 0, 0, 0], 1]
>>> s2 = [1, [1, 0, 1, [0, 0, 1, 1]], [1, 0, 1, 0], 1]
>>> add(s1, s2)
[1, [1, 1, 1, [0, 0, 1, 1]], [1, 0, 1, 0], 1]
>>> s1 = [0, [1, 1, 1, 1 ], [0, 0, 0, 0], 1]
>>> s2 = [1, [1, 0, 1, [0, [0, 0, 0, 0], 1, 1]], [1, 0, 1, 0], 1]
>>> add(s1, s2)
[1, [1, 1, 1, [1, [1, 1, 1, 1], 1, 1]], [1, 0, 1, 0], 1]