The recording of my talk from Software Should Work is now up. :) www.youtube.com/watch?v=0BXu...
youtube.com
The Unreasonable Effectiveness of Constructive Data Modeling - Alexis King | SSW 2026
YouTube video by Software Should Work
Alexis King
@lexi-lambda.bsky.social
1.7K followers 8 following 70 posts
computers can be understood • she/her, ⚢ • Chicago
![;; fill-forced-tiles-in-mega-span!
;; : mega-tiles/c mega-placement-bound? mega-placement-bound?
;; #:set-full! (-> mega-index? any)
;; -> (values natural? line-affinity? line-affinity?)
;;
;; Given two mega placement bounds, fills any tiles forced by crosses along the
;; path bridging the two bounds. For example, suppose we have the following row:
;; ☒☐☐☐☐☐☐☒☐■
;; ■☐☐☒☐☐☐☐☐☐
;; This function will fill any tiles that must be filled to connect the two
;; filled boxes:
;; ☒☐■■■☐☐☒☐■
;; ■■☐☒☐☐■■■☐
;;
;; Along the way, it also calculates and returns the minimum number of tiles
;; that must be filled within the span, taking existing filled tiles into
;; account. It also returns two line affinities that can be used to calculate
;; the minimum cost of extending a placement with the given bounds backwards or
;; forwards, respectively. For example, given the row
;; ☐☐■☐☒☐☐☐
;; ☐☐☐☐☐■☐☐
;; then the results of this function applied with bounds (mega-placement-bound 0 2)
;; and (mega-placement-bound 1 5) will be as follows:
;;
;; 1. The returned minimum size will be 5, as at least 5 tiles must be filled
;; to bridge the two bounds.
;;
;; 2. The first line affinity will be #f, as one possible way to bridge the
;; two bounds is
;; ☐☐■☐☒☐☐☐
;; ☐☐■■■■☐☐
;; which fills both tiles in the first column. Therefore, it is possible to
;; extend the filled region backwards to either line at equal cost.
;;
;; 3. The second line affinity will be 1, as filling the tile in the first
;; line above the end bound would require filling 6 tiles, not five.
;; Therefore, extending the filled region forwards is biased towards the
;; second line.
;;
;; Note that the way this function interprets bounds with line 'both or 'either
;; can be somewhat counterintuitive; see Note [Filling forced tiles between
;; placement bounds] for an explanation.](https://cdn.bsky.app/img/feed_thumbnail/plain/did:plc:fp4zjiflmhhaocasp4yblehe/bafkreiao5pacidkzzimcrpzuxxy3zki6hqltgxw2fyu2oelmsmkj4ytcmu)
![;; Note [Forced mega span endpoints]
;; ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
;; Endpoints of the span must be handled specially. Normally, we fill tiles
;; in one of the following shapes:
;; ■■■ ☐☒☐
;; ☐☒☐ ■■■
;; This corresponds to the span having to snake around a cross. However, at
;; consider the following row:
;; ☒☐☒☐☐☐☒
;; ☒☐☐☐☒☐☒
;; Suppose the span starts at the top left empty tile and ends at the bottom
;; right empty tile. If we only fill tiles in the above patterns, we’ll end up
;; with the following:
;; ☒☐☒■■■☒
;; ☒■■■☒☐☒
;; But this is missing the tiles at the ends! However, we don’t want to fill
;; the bounds unconditionally. Suppose instead we have the following row:
;; ☐☐☒☐☐☐☐
;; ☐☐☐☐☒☐☐
;; If the start and end locations are still the same, the tiles at the ends
;; are no longer forced. On the other hand, if we have the row
;; ☐☐☒☐☐☐☒
;; ☒☐☐☐☒☐☐
;; they *are* forced. Programmatically, the necessary conditions are:
;;
;; 1. The bound must cover 'both lines.
;; 2. The opposite tile must be bounded behind or afront.
;;
;; Somewhat counterintuitively, the second condition is all that matters, and
;; it holds regardless of whether the bound is the start bound or the end
;; bound. To illustrate, consider the following examples:
;; ☐☐▧☐☐ ☐☐▧☐☐
;; ☐☒☐☐☐ ☐☐☐☒☐
;; In both examples, ▧ represents a tile in one of the bound columns.
;; Regardless of whether we are filling from the left or the right, if the
;; bound’s line is 'both, the ▧ tile must be filled.](https://cdn.bsky.app/img/feed_thumbnail/plain/did:plc:fp4zjiflmhhaocasp4yblehe/bafkreiae7cifn5naof3apvipovukvlwjkynvmksd6avggssak6uxr5fc7y)
