Sunday, May 13, 2018

Declarative knitting

Hi folks!
There's a project I've made a start at a few times, but not entirely followed through, to make a kind of programmable knitting pattern generation toolkit.  The aim of this would be to make a kind of API for specifying knitting patterns programmatically - this would allow patterns to be generated based on data and computation, where this would be complex or laborious to do by hand, and to make the infrastructure behind it shared and re-usable.
My motivation for this comes from a few different projects I've done in the past to make mathematical shapes - I found that usually the computation part was quite straightforward, but outputting this as something I could knit took up most of the effort.  For example, calculating surfaces of revolution, or mapping images into polar coordinates.  At the same time, I design a lot of toys, and find that the bulk of this, especially the shaping, uses a pretty small number of concepts, which can easily by layered on top of each other.
The big idea behind how I'd like this to work is for the patterns to be expressed in a "declarative" style - a designer should be able to express "work in stocking stitch, increase evenly along the edges, for 10 rows", and leave the program to work out which specific stitches needs to do what.  The system should then be able to generate a fully detailed pattern, and express it in common formats - as text, charts, or others.  And of course this should be extensible, so that it's easy to add in new "rules" which can be used, particularly as there are so many styles of knitting that it would be impossible to express them all beforehand.
Then my big aim with all of this is that it would become possible to create "rules" based on complex computation too.  I'm working on a few of these initially - one which creates shadow knitting patterns based on images, one which creates lace patterns using edge detection, and one which will makes lace patterns from cellular automata.  Of course, these are only examples, but my hope is that I'll be able to take quirky ideas like these and make them accessible as a website where knitters can automatically generate patterns of their own.

The code for all this will be open source, and is on github:
The web services I'm hoping to get deployed on AWS in the next few weeks.

I'm pretty excited about it all!

Data Structures

Hi folks, I haven't posted any new projects for a while, and I've got a few waiting!
What I'd like to write about today, is my set of data structures.  The big idea here is that concepts are easier to explain and understand when you boil them down to their essence, and make them as concrete as possible - it forces you to think about what you really mean by them.  And because of that, it also makes it easier to explain to other people - so these are designed to be educational toys.
At the same time, data structures are a key part of computer science.  Writing good algorithms usually comes down to how you structure the data they need to work on, and good algorithms allow us to solve problems cleanly, elegantly, and fast.  They're a key enabler for how computers have changed the world, and they will only become more important over time.

The idea of the pieces is that each structure has a starting point (the purple ring), a number of arrows (which act as references), and a number of brown cups.  The "data" is represented by the plastic balls, which can be put in, taken out and moved around.  These are removable, which shows that the structure doesn't depend on the data objects themself, it just organises them.
So, the structures I've made, and what they tell us: 

Linked list

One thing you definitely need to do with a set of data is look through it.  Linked lists are very good if you just want to look through all the objects you've got in order.  You start at the initial point, and follow the arrows to look through the items.  This is great, and very flexible, and makes it easy to add new items to the list.  What it's very bad at is if you want to find a specific object - then you might need to look through the whole list to find it.
So this is good if you're going to need to add and remove objects a lot, and if you mostly care about looking through them in order.


So next up we have an array!  This time you have a rigid structure, with references at fixed intervals along it.  This means you can still look through the objects in order easily, but if you want to go to a specific entry (say the fourth), you know how far to go down the rod to find it (four steps), so you can go to that location in one step, without having to go through each of the other entries.  The down side is that if you want to add new entries, you might need to do a lot of work moving other entries around, and of course the array is a fixed size so if it's too short you'll just have to make a new one (and if it's too long, it's just wasted space.
So this is good if you've got a set of things which won't change much, and you want to pick out specific entries.

 Binary tree

But we can do better!  Suppose our data items come with some kind of order - here I've ordered the balls by colour, red to purple.  If we want to find a specific one now, we can start at the top and at each step ask, is the current one our item?  If not, is it further towards red than ours?  If so, go left.  Or is it further towards purple?  In that case, go right.  Clearly that's more complicated, but you can see that here we've got 8 objects and can find any of them in at most 3 steps.
I wanted to get across too that balance is difficult for binary trees.  Not all the branches have the same length, and you can see the one on the left only has one branch - this points to the problem you have with adding and removing entries in a tree, that you might have to do some extra work rebalancing the tree, or you might accept some inefficiency if you let it get out of hand.

(One structure I'd like to make in future is a red-black tree, to tell the next step in this story.  They're a wonderful concept, and already beautifully graphic!)

Hash table

The last of my data structures for now is a hash table - the idea now is that if you have a kind of summary of your data object (a hash function, here I'm using the colour of the ball), you can arrange it so that to find it, you just need to follow the arrow of that particular colour, and again this can be done without needing to look through all the entries.  But then we have an awkward question of what we do if two data items have the same colour (hash collisions!) - to be able to store both we need to fit both into a "hash bucket".  I'd hope this could lead to an interesting discussion of why a good hash function is important, and how using this structure efficiently can need us to think a bit about the distribution of our data.

So those are my data structures!  There's a couple more of these I'd like to do, and I am planning to write up a pattern for these.  I'm also interested in other data structures people would like to see - I've had requests for a 2D array, and for a ring buffer, which are both interesting challenges, so I'll have to see if I can come up with a way to represent them!

Happy knitting,

Saturday, April 15, 2017

Permutation cardi

There's some maths behind this one!  The idea here is that there are exactly 6 ways to permute 3 elements, and each of the cable represents one of these two permutations.

We can describe a permutation by writing down what it does to the elements 1, 2 and 3 - so the two cables on the front represent (1, 3, 2) and (2, 1, 3).

The ones on the back are slightly more complex - these ones represent (2, 3, 1) and (3, 1, 2), but in these cases you've got one element moving two places, which distorts the knitting a little more, so I've broken these into two steps each containing a single crossing.

The arms are the bit I'm most excited about - of the 6 possible permutations, there are two pairs which are mirror images (the ones we've seen), but the remaining two are their own mirror images, so they don't have a relationship - (3, 2, 1) and the trivial permutation (1, 2, 3), which leaves everything unchanged.  These give this nice asymmetry between the two arms.  (3, 2, 1) again has elements moving two places, but it's hard to break this up into two steps, so here I've added an extra chain stitch to extend the cables.

Also exciting, the length of the repeats varies between permutations -  this gives their order in the symmetry group: (1, 3, 2), (2, 1, 3) and (3, 2, 1) all have order 2, (2, 3, 1) and (3, 1, 2) are order 3, and (1, 2, 3) is order 1, so the lengths of their repeats is different.  It's cool too that these all divide 6, so if you could fit in exactly 6 repeats, all the cables would end up in the right place after the same number of rows.

You could go much further with this too!  These permutations are at the heart of bell-ringing, although taken much further - for example here.  I love the intricate patterns this gives, but I would be wary of doing this with intarsia cables - as much as I love the colours, this ends up with the yarn getting crossed and needing to be constantly untangled.  Still, imagine that beautiful scarf with rainbows weaving together!

Saturday, March 4, 2017

Foxtato pattern!

Also!  I should have mentioned here, I finally got around to posting my Foxtato pattern - you can see this on Ravelry here, and it's available for free download: Ravelry download

Looking forward to seeing other people's projects, and to see them Doing The Thing!


Data structures

Hi folks!  (I aten't dead)
I was thinking recently that I haven't made nearly enough things to do with computer science, the same way I did for maths, and it's time to fix that!
So this project is to knit a family of data structures.  The idea will be to take a bunch of plastic toy balls to represent data items, and knit wrapper cups, connected together in different ways, to represent the data structure itself.
I've got ideas for a few of these:

  • Linked list - each node has a link to the next node.
  • Doubly linked list - each node has forward and backward links.
  • Binary tree - each node has two children.  I'd like this to be unbalanced, so some of the branches will be longer than others.
  • Red-black tree - another binary tree, but with coloured nodes (and this one will be balanced).
  • Hash table - a single parent has a bunch of child nodes, each with a coloured rim to represent the hash value of the objects to place in it.  Some of the child nodes will also form (small) linked lists, of the same colour.
  • Array - a string of references, only some of which have a node attached.  (It might be more accurate if he nodes are all there, but only some of them are filled, but I think this would make it harder to distinguish from the linked list.
I'm planning to write up a pattern for this one - it should be pretty simple since the only components are the cups and the references.  But I'd love to see people knitting some other structures too, and maybe they'll be useful as teaching aids at some point?  The one drawback is this means I need to knit a *lot* of identical cups, I think the whole project will need about 40 of them.

Happy knitting,

Sunday, November 1, 2015


 The aim here was to make an ace-cephalopod, an asexual octopus, after seeing these awesome LGBT marine animals.

They're modelled on the giant pacific octopus, the main features are the head part, which leans backwards and has a slight fold where it attaches to the body.  There's then a bit of a waist, before it separates out into the arms.

The first one turned out a little more cute and cartoonish than I'd hoped - its body is too big and round, and the tentacles are too short.  I think the big problem though is that the eyes don't point outwards, so it's natural to see it as just having a big face, rather than seeing the eyes pointing sideway.  Regardless, it's pretty cute, and reminds me a lot of the dumbo octopus.  I really like how it stands up too - I'd consider adding a suction cup to the underside so it can be attached to things.

The second one I'm much happier with!  He has a real angry glare to him, and his features look great.  The main differences here are the tentacles are much longer, the head is a bit narrower and the waist more pronounced, and I've reworked the colours to give a bit more emphasis to the head.  And of course the eyes now come in little capsules so they protude and point outwards properly.

I had great fun wandering around out local docks taking pictures of them (and explaining to passersby what I was doing) - you can see the rest of them here:

Knitting these did make me realise quite how often the things I knit seem to end up having tentacles.  Going to try knitting a few more land-based things next!

Happy knitting,

Saturday, October 24, 2015

Getting ready for winter

 With winter coming, it's getting a little colder, and we're all keen to wrap up warm.  But among all the snug jumpers and mittens, let's not forget about our chlorophyll-bearing friends.
 (This comes from a suggestion from Facebook.  The hats are for the Innocent Smoothies campaign, and have been sitting in a box waiting to be sewn up for an embarrassingly long time.  No plants were harmed during the making of this.)