A fun little function

Working through the backlog of potentially interesting bits I've been meaning to post about, I came across this one. Suppose you're given an unknown function, call it foo, and asked to figure out what it does. The function takes as parameters four ints and returns a string. Experimenting a bit, you figure out that if the ints are small and non-negative, the function returns nice ASCII art:

> print(foo(4, 12, 4, 10))

        +---+        
        |   |        
+-------+   +-------+
|                   |
+---+               |
    |               |
+---+           +---+
|               |    
+-------+   +---+    
        |   |        
        +---+        

> print(foo(24, 5, 24, 11))

+-------+            
|       |            
|       +-------+    
|               |    
+---+           +---+
    |               |
+---+           +---+
|               |    
+-----------+   +---+
            |       |
            +-------+

Question 1: what does the function foo do?

The input ints are interpreted as the edges of a puzzle piece, which is then printed out. Viewing the ints in their binary form, it's easy to see that the orientation of the edges is clockwise, north-east-south-west:

      -->
   +-------+            
   | 1   1 | 0   0   0  
   |       +-------+       |
   | 1   1   1   1 | 0     |
   +---+           +---+   v
^    0 | 1   1   1   1 |
|  +---+           +---+
|  | 1   1   1   1 | 0  
   +-----------+   +---+
     0   0   0 | 1   1 |
               +-------+
                <--

Here of course 24 = 11000, 5 = 00101, 24 = 11000 again and 11 = 01011. The ordering is a bit arbitrary and there's an overlap between the first and last bits of each int, but that's all fine.

Question 2: how would you implement the function foo?

A simple scanline algorithm should be good for this. First convert the given ints, interpreted as 5-bit numbers, into a 5x5 boolean matrix for simplicity. (Note that the center 3x3 of each puzzle piece is always filled, so it's just the given 4 edges that make this interesting.) After this start at, say, the upper left corner, and going through each row in the matrix left to right, check the values for this cell and the relevant neighbours and draw accordingly. (Define the cells outside the matrix to have the value 0.)

Now since you're processing the cells in order, top-to-bottom and left-to-right, it's sufficient at each cell to just consider the upper, upper-left and left neighbours. This gives you in theory 16 different cases. Sketching them out you'll find 5 distinct cases (or 4, depending on how you look at it); or you could just notice that there are 4 main cases depending on whether you've just crossed a horizontal edge, vertical edge, both or neither, and then one more case depending on whether you've just ended or started a both-horizontal-and-vertical cross point.

Instead of going through the algorithm in more detail, here's the link to an implementation on Github. I wrote the refactored version in slightly scruffy C for some reason, after noticing that the first implementation I had done a while back was amusingly bad. To test it out, simply say "make" and for some examples, see the "test" script. (No unit tests this time, sorry.)