fragmentary ideas ䷿ intellectual what-nots ䷷ and haskell programming ䷴

Computer science is a fascinating and maddening thing. Even the most seemingly-esoteric topics turn out to be fundamental. Go out to the fringes of CS and you find yourself smack in the middle of Philosophy. You try to understand a single point and you suddenly find yourself embracing everything.

So this post comes from that infinitely-recursive rabbit hole of wikipedia topics I’ve been falling down for the last few weeks, and you can probably expect a few more like this one; I’ll try to keep focused.

We begin (as do All Good Things) with the Untyped Lambda Calculus:

» read more…

Note: this is part of a series of posts is related to the “17×17 Challenge” posted by Bill Gasarch. The goal is to color cells of a 17 by 17 grid, using only four colors, such that no rectangle is formed from four cells of the same color.

This is something I’ve been wanting to play with for months now, but haven’t made the time to implement: I wondered if simulated annealing techniques could be effective in finding a complete grid covering.

We would simply start with four copies of the 74-color grid and swap their rows and columns around, within each color set, trying to cover all of the cells by the union of the four subsets. So all of the sets of cells of a single color are fundamentally simply different permutations of the same 74-cell rectangle-free Graph.

Here is an illustration of the concept. Our algorithm starts with all four colored sets of cell overlapping (the red cells are on top, covering the other three colors):

…then we swap two rows or two columns from a colored subset of cells, until the four colored subsets spread out covering as much of the grid as possible. Here we cover all but 21 cells:

» read more…

Note: this is part of a series of posts is related to the “17×17 Challenge” posted by Bill Gasarch. The goal is to color cells of a 17 by 17 grid, using only four colors, such that no rectangle is formed from four cells of the same color.

An almost silly amount of time passes between my new ideas on this problem and investigating/coding those ideas, but I’m trying to be better about helping my thoughts see the light of day before I get entirely bored of them.

So in that spirit, here are a few more thoughts on the 17×17 Problem investigated.

Will Graph Layout Algorithms show Symmetry?

Force-based algorithms tend to be good at creating symmetrical layouts of graphs. The idea is to translate a Graph into a system of springs (edges) and charged particles (nodes). You then run a simulation of this 2-dimensional sytem and the graph eventually should work itself out into some equilibrium state.

At that point hopefully you get a layout which is more clear and perhaps makes clear some important relationships of the Graph.

I used the graphviz software suite to do the force-directed layouts and wrote some ugly code to coax some rectangle-free single-colorings into the graphviz file format. I hoped that some of the single- and double-symmetrical relationships that I noticed would emerge in the process.

» read more…