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

I’ve been making notes when I have time, on the “17 x 17 challenge” posted a couple months back by Bill Gasarch. I’ve been sketching out algorithms for the problem and wanted to quickly produce some optimal rectangle free subsets to check my work and look at. So the code below answers the following question:

Imagine an n x n grid. You can color cells of the grid such that no rectangle overlayed on the grid will have all four corners colored. Find a grid with the maximum possible colored cells.

Read the rest of this article »

The function groupBy from haskell’s standard library is defined in terms of span, the effect being that the supplied predicate function is used to compare the first element of a group with successive elements.

This isn’t clear from the docs, and you might try to do this and wonder at the output you got:

*Main> groupBy (< =) [3,4,5,3,2,1,4,4,1,1,2,3,4,5,4,5,6,7]
[[3,4,5,3],[2],[1,4,4,1,1,2,3,4,5,4,5,6,7]]

Read the rest of this article »

I’ve been thinking quite a bit lately about a category of functions that are always a bit awkward to define: they involve cases where we would like to traverse a recursive data structure and do something with the data that we have passed over but which is “gone now”.
Read the rest of this article »