Coding Stories: Wrangling Representations
Before I can do much of anything such as cook a meal, calculate the forces on a projectile, or solve a math puzzle, I first need to get some aspects of the world around me into my brain. This process can be called representation because the ideas in my head represent what I perceive to be in the world. Once they are in my head I can use them in my thinking and actions.
When you doing something with a computer you also do this, but you additionally need to represent things in ways that are amenable to the structure of computers. Yet despite its importance Representation is not listed as one of the practices or concepts in the CSK12 standards. In this post I will be exploring just how important representation is in the process of creating code.
To help you understand where I am coming from I will share an illuminating journey that I undertook recently when I.came across an interesting puzzle on the blog of one of the amazing math teachers at my school. Here is my paraphrasing of the problem.
Say you want to store a collection of plastic bags from the grocery store all in a single bag so that they are tidy under your sink. How many different ways can you store these bags? He added this drawing to clarify the problem.
I always love a puzzle so I started working on figuring out the solutions for 4 bags. I quickly created the following diagram using similar notation but drawn in a more messy fashion on an iPad.
Then I started thinking more about the problem. To solve a puzzle like this you need to employ a few basic strategies. First you need to find a clever way to represent the problem. For this problem you could just represent it with real bags from under your sink. But that would not be ideal because it is hard to see how many bags are inside of a bag and you might lose track of the combinations that you tried (see below).
In other words using real bags is not a great representation system. A representation system should make the problem easier to explore. It can be useful when exploring objects that are too big or too small to work with. For example, a representation of atoms is better than real atoms unless you have an electron microscope and even then it is a challenge to manipulate atoms. Representation systems allow you to work with things that are inaccessible or even dangerous. They can also document your problem solving process. I think we sometimes take for granted the amazing power of pencil and paper. What an incredible system. You can draw or notate something multiple times, erase and store information. It is cheap and readily available. Also we have spent years of our lives learning how to use this system effectively. We have gained fine motor dexterity to wield a pen and have built up knowledge of graphical encoding systems such as the English language and mathematical notation. We also have the ability to create new notational systems and to document them with none other than a pencil and paper. Incredible!
Computers are just another representational system that offers its own advantages and limitations. We will get there soon, but let’s first take another look at the drawings shown above and how they let us explore all the combinations for one, two, three and four bags. We can identify patterns in the combinations, for example, you might notice that the first two combinations for four bags are the same as the two combinations for three bags with the outer bag removed. Patterns such as these are important in the process of developing a systematic solution.
All this to say that finding the right way to represent a problem is no small task in the problem solving process. Once you decide on a representation the next step is to come up with a method to generate solutions. In this case I tried all the ways of drawing four bags. But if you don’t have a systematic way of generating representations you might miss one. You also need a way to know when you are done exploring combinations. In this case there is an additional challenge because some combinations are equivalent. For example the following representations are equivalent because the order of the interior sets does not matter.
If you think about bags being placed in bags you can’t really be sure how they will be oriented inside. This is in fact a limitation of the representation system because it differentiates something that is not in reality differentiable. You need to be able to recognize issues such as this if you are going to accurately count your solution set.
A clever way to approach a problem like this is to think recursively about the solution. For example to get the solutions to four bags I can start with the two solutions to 3 bags and come up with all the ways of adding one bag to those solutions. In this way I can generate the next level of solutions to the current solution set. However there are actually 6 ways to add a bag to the two solutions, but some of the subsequent four bag solutions are equivalent and so only 4 unique solutions are generated.
This paper and pencil notation system is a good start to tackling this problem and is probably good enough to take me to 5, 6 and maybe even 7 bags. But there comes a point when it is challenging to work through all the combinations. When you hit a limitation like this you might try to develop a new way to think about the problem that makes it less tedious and cumbersome. Another approach is to harness the power of a computer. In fact that is what computers were invented for.
Computational thinking is a combination of the mathematical thinking I need to systematically analyze this problem and the computer based thinking I need to represent and solve the problem on a computer. By bringing these two aspects of thinking together you expand the range of problems you can explore and you end up deepening your thinking about them.
One way to think about the bags problem on a computer is to treat the bags as empty arrays. For example here are the two solutions for 3 bags using empty arrays.
1 [ [ [ ] ] ]
2 [ [ ] , [ ] ]A more clever way to store bag combinations utilizes a core concept of computing called a graph. A graph is simply a set of nodes (or dots) that are connected by lines called edges. In this case I need a very specific type of graph called a rooted tree because the outer bag always starts the tree.
Graphs can be represented visually with dots and lines as shown here
I have drawn the same solutions given at the start of this article using rooted trees. This is not necessarily a better representation than what we did above, but a lot of mathematical thinking has been documented for graphs and trees and so all of that knowledge can be leveraged in solving this problem. So a representation system is also powerful by giving you access to previous thinkers work on similar problems. For example rooted trees form the basis of many built-in data structures used in coding such as linked lists and heaps. Finally I think a rooted tree is a promising way to visualize this problem in p5.js.
So I decided to start building a visualization for rooted trees. I was inspired by the following website https://d3gt.com/unit.html?spanning-tree
First I defined a Node class so that I could easily create node objects to build my tree
let d = 50; // distance between nodesclass Node {
constructor(parent) {
if (parent) {
this.parent = parent;
this.pos = this.parent.pos.copy().add(createVector(0,d));
}
else {
this.pos = createVector(200,200);
}
}
show() {
if (this.parent) {
let p = this.parent;
line(this.pos.x,this.pos.y,p.x,p.y);
}
circle(this.pos.x,this.pos.y,40);
}
}
Each node has one and only one parent. Each tree has only one root. This is what defines the rooted tree.
Then I built a RTree class to keep track of all the nodes.
class RTRee {
constructor() {
this.nodes = [];
this.nodes[0] = new Node();
}
show() {
this.nodes.forEach((n)=>n.show());
}
}In order to visualize the tree I decided I would use a few ideas from Physics. The links to the parents could work like springs. The nodes could be pulled by gravity and experience an electrostatic repulsion from all the other nodes. When you make an animation it does not need to be physically accurate but sometimes it is more fun to make it that way. Here are the new methods I wrote for the Node class.
eForce(pos) {
let dist = this.pos.dist(pos)
let v = p5.Vector.sub(pos,this.pos);
return v.copy().normalize().mult((eConst) / (dist*dist));
}
move(nodes,g) {
this.vel.y+=g;
if (this.parent) {
let fApp = createVector(0,0);
fApp.add(this.pos.copy().sub(this.parent.pos));
let length = fApp.mag();
fApp.normalize().mult(k*(length-d*.6+this.depth*3));
}
for (let n of nodes) {
if (n!=this) {
fApp.add(this.eForce(n.pos));
}
}
this.vel.sub(fApp);
this.vel.mult(damp);
}
this.pos.add(this.vel);
}As I explored my computational rooted tree I lost track of the original problem and experimented with the aesthetics of the tree. I decided it would be pleasing to add nodes randomly. Then when the tree filled up I released its anchor and had it fade into the background. Meanwhile I instantiated a new rooted tree randomly on the screen. Here is my final version of the rooted tree animation. I really like the way it creates a sense of movement and beauty in the frame.
Now I could add in sliders and let you tinker with the aesthetics of the simulation but I will leave that to you. Instead you might just watch it for a while and enjoy.
Now you might accuse me of losing focus of the mathematics on this project. But I would argue that mathematics and creativity are well suited for each other. As I was playing with the animation I was thinking more deeply about rooted trees. How would I find all the possible configurations? Randomly creating trees is not the best way to create an exhaustive list.
As I started thinking more deeply about the problem I created a new notation system to help me think it through. While the visual of graphs are powerful I find linear written notation systems more accessible and familiar. So I created the following. Suppose each node in the tree is an integer in an array of integers. For example.
[3,2,0,0,1,0,0]
The first number refers to the number of children of the root node. The next three numbers refer to the number of children of those 3 child nodes. Subsequent integers represent each of the children in order on the new level. I could also represent this list with semi colons to disguise the the levels of the tree. But the semi-colons are not necessary.
3; 2,0,0; 1,0; 0 (drawing below shows the equivalent graph)
In order to avoid double counting I will keep the number of children reverse sorted on each level. Using this notation system I can document any rooted tree and therefore any combination solution to the bag problem. I went through the exercise of solving up to 5 bags by hand. Working through these examples I noticed that the number of edges in a rooted tree is equal to one less than the number of nodes. This makes sense since each node besides the root has one parent. I also noticed that the there was a pattern to the combinations on each level. At that point I realized I wanted to return to the computer to generate all the solutions. For generating algorithms such as these for some reason I find Python easier to work with. So I switched languages.
First I wrote a function that can generate all the possible combinations for a given level.
def levels(edges_left,slots_left,state=[]):
if slots_left == 0:
yield state
elif edges_left == 0:
yield state+[0]*slots_left
else:
start = edges_left if not state else min(state[-1],edges_left)
end = -1 if state else 0
for e in range(start,end,-1):
yield from levels(edges_left-e,slots_left-1,state+[e])For example if you run this code for 4 edges left and 2 slots left then it creates the following possible level options
4,0 / 3,1 / 3,0 / 2,2 / 2,1 / 2,0 / 1,1 / 1,0 Note how the edges are reverse sorted on the level and there needs to be at least one non-zero value to allow for another level. Then I wrote a function to generate all the trees made of multiple levels.
def trees(nodes,edges=None,state =[],slots=1):
if edges==None:
edges=nodes-1
if nodes==0: # and edges==0:
yield state
else:
for l in levels(edges,slots):
yield from trees(nodes-len(l),edges-sum(l),state+l,sum(l))I am pretty sure that this algorithm is correct though I encourage you to find if I made a mistake. For 20 bags I found 3,581,637 solutions. That seems pretty impressive. Even though it was easier for me to step through the solutions with this new notation it is not as satisfying as a visual approach. So I returned to p5, rewrote this same code in javascript and then generated rooted tree diagrams for a given configuration representation. That allowed me to make the following interactive app to show solutions for a chosen number of bags.
In this story I have explored representation in a number of different ways from how to think about a problem or idea, to the way to use computers to support that thinking. I also used representation to make my ideas and process visual and hopefully engaging. We need to put more thought into the role of representation when we are teaching computing. I also believe that the concept of representation can help us identify and highlight important connections between the STEM fields and the Arts.
