Recursion, Data Structures
We use recursion to print a square. If the square is simple, we can just print it.
Otherwise, we loop over the squares in the split square, and use our same function to print each of those.
def dump(s):
"""Print each square on a new line."""
# START SOLUTION
# Base case: it's a simple square
if s == 0 or s == 1:
print(s)
# Otherwise, recurse
else:
# Print each quadrant
for q in s:
dump(q)
This solution has the same general structure as dump. Our function will use a simple square as a base case (either returning True or False if it’s a valid simple square). For split squares, it checks each quadrant and returns True only if all four are valid.
def validate(s):
"""Validate that a given square is valid.."""
# START SOLUTION
# Base case: it's a simple square, so as long as it's either 0 or 1
# it's valid.
if type(s) == int:
return s == 0 or s == 1
# Base case: if not a list of 4, it's invalid
if type(s) != list or len(s) != 4:
return False
# It's a split square:
# Recurse intro quadrants and check each, "failing fast".
#
# Note: alternately, we could write the rest of this function in
# one pretty line by using the awesome `all(iterable)` function:
#
# return all(validate(q) for q in s)
for q in s:
if not validate(q):
return False
return True
This one is more tricky.
Our base case is still a simple square (we can’t simplify that any further!).
For split squares, we’ll first ask to recurse-simplify each of their component quadrants and then see if the resulting quadrants are the same and, if so, simplify those by returning a simple square.
def simplify(s):
"""Simplify a split square:"""
# START SOLUTION
# Base case: already a filled square, cannot be simplified
if type(s) == int:
return s
# It's a split square.
#
# Recursively simplify each square in split square.
# Recurse before simplify a split square, so that we can
# simplify things "coming up" --- this catches the case of
# ``[1, 1, 1, [1, 1, 1, 1]]`` => ``1``
# and other times when need to "simplify twice".
s = [simplify(s) for s in s]
# Simplify a split square if possible
if type(s[0]) == int and s[0] == s[1] == s[2] == s[3]:
return s[0]
else:
return s
If you got this, give yourself a big compliment. It’s a hard problem!
This one is also tricky, especially when the squares are unevenly nested.
It uses the same general base case as before: once we are trying to add two
simple squares, we can just add them together (in the main code example, we
use the uncommon-but-useful Python OR operator, |, but you could also
write this out as an if/else stanza).
If they are both split squares, it pairs up the quadrants and recursive-adds those pairs (recursive-add the top-left quadrants of both split squares, then the top-right, and so one, returning the list of those four adds).
The interesting (and hard!) part is handling the unevenly nested — where one square is split and one is simple. In this case, before the adding, it turns the simple square into a split square composed of four squares that are the same as the simple square. Then, it has “compatible split squares” and they can be added together. Neat!
def add(s1, s2):
"""Produce new split square adding two input squares."""
# START SOLUTION
# Base case: both are simple filled squares
if type(s1) == type(s2) == int:
# Return OR of squares: if either is filled in, it's filled in;
# otherwise, it's empty
#
# Instead of using | operator, could do this directly with:
# return 0 if (s1 == 0 and s2 == 0) else 1
return s1 | s2
# Otherwise, if one is filled square and not a divided square,
# make a divided square out of it
if type(s1) == int:
s1 = [s1, s1, s1, s1]
if type(s2) == int:
s2 = [s2, s2, s2, s2]
# Recursively find sum of four quadrants of both squares
#
# zip(s1, s2) is nice --- it takes s1=[1,1,1,1] and s1=[0,0,0,0] and
# returns list of pairings [(1,0), (1,0), (1,0), (1,0)].
# Alternatively, you could do this with
#
# return [add(s1[i], s2[i]) for i in [0, 1, 2, 3]]
return [add(q1, q2) for q1, q2 in zip(s1, s2)]
This is definitely hard. If you got this, you’re a recursion master!
If you got stuck, be kind to yourself — it’s definitely tricky. Go back and practice re-writing the earlier parts of the exercise to get a good feel for how recursion works through the parts of this problem.
A JavaScript version of this challenge is also provided:
"use strict";
/* splitsquare.js - Joel Burton <joel@joelburton.com> */
/* dump(s) - returns split square as string
(unlike Python version, which prints to console)
*/
function dump(s) {
if (s === 0 || s === 1) {
return s.toString();
} else {
// Array.map(fn) - return new array of [fn(item1), fn(item2), ...]
return s.map(dump).join(" ");
}
}
/* is_valid(s) - is this a valid split square? */
function is_valid(s) {
if (s === 0 || s === 1) {
return true;
}
if (Array.isArray(s) && s.length === 4) {
// Array.every(fn) = for every item in array, is fn(item) true?
return s.every(is_valid);
}
return false;
}
/* simplify(s) - simplify redundant splits in a split square */
function simplify(s) {
if (s === 0 || s === 1) {
return s;
}
var q1 = simplify(s[0]);
var q2 = simplify(s[1]);
var q3 = simplify(s[2]);
var q4 = simplify(s[3]);
if (Number.isInteger(q1) && (q1 === q2) && (q1 === q3) && (q1 === q4)) {
return q1;
}
return s;
}
/* add(s) - add two split squares */
function add(s1, s2) {
if (Number.isInteger(s1) && Number.isInteger(s2)) {
// Not || for "logical-or", but | for "bitwise-or"
// 0|0=0 0|1=1 1|0=1 1|1=1
return s1 | s2;
}
if (Array.isArray(s1) && !Array.isArray(s2)) {
s2 = [s2, s2, s2, s2];
}
if (Array.isArray(s2) && !Array.isArray(s1)) {
s1 = [s1, s1, s1, s1];
}
return [
add(s1[0], s2[0]),
add(s1[1], s2[1]),
add(s1[2], s2[2]),
add(s1[3], s2[3])
];
}
// allow testing from command line by exporting modules
if (typeof module === "object") {
module.exports = {dump, is_valid, simplify, add};
}
This has tests; you can see these tests run by opening js/test/splitsquare.test.html in a web browser.
"use strict";
/* Tests for splitsquare.js
*
* Joel Burton <joel@joelburton.com>
*
*/
if (typeof require === "function") {
var assert = require("chai").assert;
var {dump, is_valid, simplify, add} = require("../splitsquare");
}
suite("dump", function () {
test("should dump ints", function () {
assert.equal(dump(0), "0");
assert.equal(dump(1), "1");
});
test("should dump arrays", function () {
assert.equal(dump([0, 1, 0, 1]), "0 1 0 1");
});
test("should handle nesting", function () {
assert.equal(dump([0, 0, 0, [1, 1, [0, 0, 0, 0], 1]]), "0 0 0 1 1 0 0 0 0 1");
})
});
suite("is_valid", function () {
test("should allow correct ints", function () {
assert.isTrue(is_valid(0));
assert.isTrue(is_valid(1));
});
test("should reject wrong ints", function () {
assert.isFalse(is_valid(3));
});
test("should reject wrong types", function () {
assert.isFalse(is_valid({"hey": "there"}));
assert.isFalse(is_valid("yo"));
assert.isFalse(is_valid("1"));
});
test("should disallow wrong-length arrays", function () {
assert.isFalse(is_valid([0, 0, 0, 0, 0]));
});
test("should allow good arrays", function () {
assert.isTrue(is_valid([0, 0, 0, 0]));
});
test("should handle nesting properly", function () {
assert.isTrue(is_valid([0, 0, 0, [1, 1, 1, [0, 0, 0, 0]]]));
assert.isFalse(is_valid([0, 0, 0, [1, 1, 1, 1, [0, 0, 0, 0]]]));
});
});
suite("simplify", function () {
test("should be a no-op for ints", function () {
assert.equal(simplify(1), 1);
assert.equal(simplify(0), 0);
});
test("should not simplify non-matching arrays", function () {
assert.deepEqual(simplify([1, 0, 1, 0]), [1, 0, 1, 0]);
});
test("should simplify matching arrays", function () {
assert.equal(simplify([1, 1, 1, 1]), 1);
});
test("should handle nesting", function () {
assert.equal(simplify([0, 0, 0, [0, 0, 0, [0, 0, 0, 0]]]), 0);
});
});
suite("add", function () {
test("should add ints", function () {
assert.equal(add(0, 0), 0);
assert.equal(add(1, 1), 1);
assert.equal(add(1, 0), 1);
assert.equal(add(0, 1), 1);
});
test("should add arrays", function () {
// note: .toEqual, not .to.equal, since new list has different identity
assert.deepEqual(add([1, 0, 1, 0], [0, 0, 0, 1]), [1, 0, 1, 1]);
});
test("should handle nesting", function () {
assert.deepEqual(add(0, [1, 0, 1, 0]), [1, 0, 1, 0]);
assert.deepEqual(add(1, [1, 0, 1, 0]), [1, 1, 1, 1]);
});
});
Alternatively, tests have been provided in CoffeeScript, an alternate syntax for JavaScript which is particularly nice for running tests. You can see these tests running by opening js/test-coffee/splitsquare.test.html in a web browser.
# Tests for splitsquare.js
#
# Author: Joel Burton <joel@joelburton.com>
if require?
`chai = require("chai")`
`({dump, is_valid, simplify, add} = require("../splitsquare"))`
assert = chai.assert
suite "dump", =>
test "should dump ints", =>
assert.equal dump(0), "0"
assert.equal dump(1), "1"
test "should dump arrays", =>
assert.equal dump([0, 1, 0, 1]), "0 1 0 1"
test "should handle nesting", =>
assert.equal dump([0, 0, 0, [1, 1, [0, 0, 0, 0], 1]]), "0 0 0 1 1 0 0 0 0 1"
suite "is_valid", =>
test "should allow correct ints", =>
assert.isTrue is_valid 0
assert.isTrue is_valid 1
test 'should reject wrong ints', =>
assert.isFalse is_valid 3
test 'should reject wrong types', =>
assert.isFalse is_valid {hey: "there"}
assert.isFalse is_valid "yo"
assert.isFalse is_valid "1"
test "should disallow wrong-length arrays", =>
assert.isFalse is_valid [0, 0, 0, 0, 0]
test "should allow good arrays", =>
assert.isTrue is_valid [0, 0, 0, 0]
test "should handle nesting properly", =>
assert.isTrue is_valid [0, 0, 0, [1, 1, 1, [0, 0, 0, 0]]]
assert.isFalse is_valid [0, 0, 0, [1, 1, 1, 1, [0, 0, 0, 0]]]
suite "simplify", =>
test "should be a no-op for ints", =>
assert.equal simplify(0), 0
assert.equal simplify(1), 1
test "should not simplify non-matching arrays", =>
assert.deepEqual simplify([1, 0, 1, 0]), [1, 0, 1, 0]
test "should simplify matching arrays", =>
assert.equal simplify([1, 1, 1, 1]), 1
test "should handle nesting", =>
assert.equal simplify([0, 0, 0, [0, 0, 0, [0, 0, 0, 0]]]), 0
suite "add", =>
test "should add ints", =>
assert.equal add(0, 0,), 0
assert.equal add(1, 0,), 1
assert.equal add(0, 1,), 1
assert.equal add(1, 1,), 1
test "should add arrays", =>
assert.deepEqual add([1, 0, 1, 0], [0, 0, 0, 1]), [1, 0, 1, 1]
test "should handle nesting", =>
assert.deepEqual add(0, [1, 0, 1, 0]), [1, 0, 1, 0]
assert.deepEqual add(1, [1, 0, 1, 0]), [1, 1, 1, 1]