Tags: Uncategorized, django, graph theory, linkedin, mathematics, python, Site updates, Techiness, webdevelopment, Yarning
My knitting colleague E. made the (arguably) goofy decision to refresh her crocheting skills by taking on a granny squares blanket.
It’s a great idea for using up a ton of scrap yarn.
It’s not a great idea if you enjoyed the level of sanity you had when you started.
She quickly ran into the classic self-randomizing problem: given 20 different colored yarns of different weights, how do you put 3 different ones in each square while trying to keep the colors as random as possible? Sounds easy enough, but after 15 or so squares, it gets tricky. If you’re aiming for randomization, the last thing you want is a big diagonal of purple in your blanket when you’re done.
So E. appealed to me and asked me to write her a “script” to randomize her colors. I was on board, look forward to some Python/Django fun before I realized that what I’d been handed was a graph coloring problem with some fun restraints. (Turns out it was easy, but fun to think through.)
Given a set of yarn colors each with one of three richnesses (light, medium, and dark) and one of three yarn weights/thicknesses (light, medium, heavy) generate a blanket x squares wide by y squares tall using n colors per square.
The optimal solution will have one of each richness per square and one of each yarn weight per square. In addition, no two adjacent yarns in different squares will be the same color, richness, or thickness. (That is, the yarn at depth 2 of square one should be different in color, richness, and thickness from the yarn at depth 2 of square two.)
If there aren’t enough different richnesses or thicknesses provided for one per square (e.g. a square that is four colors deep must have a duplicate richness and thickness), the generated blanket should try to ensure that no two adjacent yarns have the same thickness.
If not enough colors are provided for a single square (e.g. three colors for a four-deep square), the blanket should create a random pattern and apply it repetitively to the blanket. (In other words, “screw that mess.”)
I found that–surprisingly–given the other slowness inherent in a web app (network latency, apparently page load times, etc.) and the small sizes I’d be dealing with (10×10 squares and 3-4 colors deep are common) that a brute-force color search worked well enough. (Averaging less than 35 ms for up to 8 colors per square and less than 20 ms for 4 or fewer colors.) For each color in each square, I start from the set of all colors, reduce it down by eliminating colors based on the above constraints, and pick randomly. If there aren’t any viable colors, then I pick a random color that isn’t one already in the square.
Not that these aren’t “will do’s”. They just haven’t been done yet.
The fallback for missing viable colors should be more graceful. If there are no optimal colors, then I should try to find one with a different richness. If there are none of those, then one with a different thickness. Then I should fall back to the random color that isn’t already in the square.
Second is the presentation. Some tiny CSS tweaks to make errors more noticeable and the current field highlight, etc. I also toyed around with the idea of making the color entry tabular, but stuck with the currently more expanded form for accessibility. I still want to find a good way to make that work.
Lastly, I’ve never learned graph theory well, and this project could be an awesome way to rectify that. The target users of this probably won’t give a damn, but it’d be fun to pigeonhole this into an established graph coloring problem and work up a faster algorithm.