racket-nonogram can now show you any mistakes you’ve made, in case you can’t figure out what the issue was and don’t want to have to completely start over
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)
![[excerpt from the linked answer that starts partway through]
When this function is called, result_location will record the address of wherever result happens to be stored on the stack. Control then yields to the enclosing continuation prompt, and some time later, the continuation is restored. Unless the stack frame for foo happens to be restored to precisely the same location, the write to *result_location will fail to update the new location of result and will instead clobber whatever now happens to be at that address.
Given this fundamental issue, most programming language implementors consider implementing delimited continuations that capture the C stack to be a complete non-starter.
Doing it anyway
Fortunately, Daan Leijen is not most programming language implementors. His audaciously-named 2017 publication Implementing Algebraic Effects in C describes an implementation strategy for delimited continuations that really do capture and restore C stack frames.
How does he do it? By simply always restoring the continuation to exactly the place it was captured from, of course! In § 4.3 Resuming, Leijen describes his implementation strategy:](https://cdn.bsky.app/img/feed_thumbnail/plain/did:plc:fp4zjiflmhhaocasp4yblehe/bafkreidgzguyemf525vhz7efgbozyfegnyveufdqjanwuadms35ywhilei)
![Toolbox: Miscellaneous Utilities
This library provides a collection of miscellaneous Racket utilities that I use in my personal projects but I have not felt warrant being published as a separate package. Note that this library is intentionally not published on the Racket package server, as everything in this library should be considered unstable. In projects that use it, I include this repository as a Git submodule, pinning to a specific version.
[table of contents]](https://cdn.bsky.app/img/feed_thumbnail/plain/did:plc:fp4zjiflmhhaocasp4yblehe/bafkreiddt4asrpqzalltaolcv63xv5vq6h6tvbpezf25pg72mh64w3dl54)