Implementation notes A mix of two themes. ---------------------------------------------------------------------- 0. Concept I was generating test data for Endoh-san's most explosive entry for IOCCC 2020, for which I thought a space filling curve would be most appropriate. After that I just got possessed by a strange mood to fill terminals with space filling curves. ---------------------------------------------------------------------- 1. Space filling curves with dynamic programming To fill an arbitrary rectangular area with space filling curves, we can try starting with predefined space filling curves that filled particular unit areas, add those curves to a table, and expand the table using existing table entries until it covers the area of interest. The most well known space-filling curves are probably Hilbert curve and Peano curve, both are generated in a fractal fashion that replace some subset of the curves following a fixed set of rules, and both fill up square areas. Since most terminals are not square, the first challenge would be to find some way to build rectangles out of these squares. Hilbert squares turned out to be more convenient for building rectangles, because the start and end of each curve lie on the same side of the square: +-----+ |.....| |. .| start -> |. .| -> end +-----+ If we just copy the same Hilbert curve to the right, the curves will still connect, and we end up with a rectangle with 2:1 aspect ratio: +-----+-----+ |.....|.....| |. .|. .| start -> |. .>. .| -> end +-----+-----+ If we add two rotated Hilbert curves below this rectangle, we would make a larger square that is 2x the size of the base square. Notice how this larger square is just the next generation of Hilbert curve: +-----+-----+ |.....|.....| |. .|. .| |. .>. .| +^----+----v+ |.....|.....| | .|. | start -> |.....|.....| -> end +-----+-----+ We can replace the top half of this large square with smaller squares to produce a rectangle with 4:3 aspect ratio: +--+--+--+--+ |..|..|..|..| +^-+--+--+-v+ |.....|.....| | .|. | start -> |.....|.....| -> end +-----+-----+ We can also replace the bottom right square with smaller squares to produce a slightly larger square that is 3x the size of the small squares: +--+--+--+ |..|..|..| +^-+--+-v+ |.....| .| | .+--+ start -> |.....| .| -> end +-----+--+ The common trick applied in all of the above is to take existing curves and place them adjacent to each other, making sure that the start and end of each curve are aligned at the right places. Essentially we are building a table of shapes that are reachable using existing space filling curves, and then joining those shapes to cover larger areas. Two optimizations are done to simplify organization of this table: - All shapes are rectangles. - All rectangles have their curves start in lower left corner and end in lower right corner. By duplicating and rotating rectangles of space filling curves, we can build up a table of space filling curves indexed by width and height. If the terminal size is just right, the final curve we want would be just a table lookup. ---------------------------------------------------------------------- 2. Space filling curves with divide and conquer Unfortunately, with the way we set our table up, the solution is not guaranteed to be reachable with a single table lookup. We to be a bit more flexible in how the table entries are applied to fill all possible areas. For example, we don't have a way of filling a rectangle of size (2,3) that starts in lower left corner and ends in lower right corner, although we can try this instead: 6--5--4 | 1--2--3 This would satisfy the orientation constraint if we transpose the rectangle: 3--4 | | 2 5 | | 1 6 The problem is that we will not arrive at this shape if we only follow basic rules for building Hilbert squares. A different construction might be something like this: 2--3 6 | | | 1 4--5 We can get there using a divide and conquer approach, where we first try to fill the left (2,2) area using Hilbert squares, and then recursively fill remaining (1,2) area to the right. This led to the following heuristic: - Orient input so that width >= height. - Find the largest rectangle in pre-built table that can cover the left side of this rectangle, and recursively fill the right side. Note that we don't need to maintain the constraint of having the curve end on the lower right corner, so the two rectangles might be joined like this: +------------+-------+ | |4 | | left | right | |1 2|3 | +------------+-------+ - If nothing fits, slice off the bottom edge with a rectangle of height 1 and retry. +------------+ +------------+ | | | 4| | top | | | |4 3| | top | +------------+ | | |1 bottom 2| | 3| +------------+ +------------+ |1 bottom 2| +------------+ The slice off by one step guarantees that all rectangles can be filled, because we could just fallback to filling it with a spiral pattern, although usually we would eventually hit a rectangle size that has the appropriate space filling curves in our table. ---------------------------------------------------------------------- 3. Space filling curves with eye Having found a satisfactory way fill the screen with space filling curves, I still wasn't quite satisfied with the result. But at this point I wasn't quite obsessed with space filling curves anymore. Instead, I was thinking about the ongoing manga series "Mieruko-chan", an interesting mix of horror and comedy. One of the logos that showed up from time to time in this series is an eye, the design of which is sufficiently simple to be described in a few curves, and scaling those few curves to fit any terminal was fairly straightforward. Well, there was a minor detail of having to scale an ellipse which involves finding the distance between a point and the ellipse, and turns out the best way to do that is just to test various points on that ellipse and find one that is closest. It's a kind of thing that is messy to describe but straightforward to implement, especially if you don't care about efficiency. I have decided to combine this image together with the space filling curve in what's basically an unusual kind of progressive image rendering, where the eye logo gets drawn while the space filling curve is being traced. The end effect worked out reasonably well. ---------------------------------------------------------------------- 4. Space filling curves with Ruby Because it involves filling terminals, I knew that it would be a Ruby program from the very beginning, due to its convenient "io/console" library. It was especially convenient that after I have golfed the code down to a reasonable size, I can just gzip+uuencode the thing and fit that output to a template. Ruby is totally a language designed for ASCII art, for those times when I too lazy to manually layout each character by hand. ---------------------------------------------------------------------- 5. Testing This program has been verified to work with these versions of Ruby: - ruby 2.7.1p83 (2020-03-31 revision a0c7c23c9c) [x86_64-linux-gnu] - ruby 2.6.4p104 (2019-08-28 revision 67798) [x86_64-cygwin] - ruby 2.3.1p112 (2016-04-26) [i386-linux-gnu] - ruby 2.1.5p273 (2014-11-13) [x86_64-linux-gnu] Also, because I only used the most basic ANSI colors, this program works even inside lesser terminals such as the Windows cmd.exe. ---------------------------------------------------------------------- 6. Finally... Some mixes just work out better than others. I didn't think horror comedy would be something I was enthusiastic about but "Mieruko-chan" has a good balance.