The voice of a wizard hacking away

My pals at Sandy Pug Games have opened up preorders for WIZARDPUNK, a zine of various wizard stories and whatnot. It’s full of brilliant work, and I highly recommend checking it out! I have a little epistolary slice-of-life piece in it, which I’m honestly pretty proud of. In addition to this, I was asked if something rather curious was possible, if there was any way some audio-producing computer code could be squished down to a reasonable size such that someone could theoretically type it in.

Solving puzzles using Sentient Lang

I’ve been playing a mobile room-escaping-themed puzzle game (I believe the title is simply Can You Escape 50 Rooms) with a friend, and there was a certain puzzle that we got stuck on. By stuck, I mean that we certainly would’ve figured it out eventually, but it was more frustrating than fun, and it consumed enough time that I thought up a fun way to cheat. I am not against cheating at puzzles that are failing to provide me with joy, or that I’m simply unable to complete, but I have a sort of personal principle that if I’m going to cheat, I’m going to attempt to learn or develop something in the process.

MINOL and the languages of the early micros

This post was updated in May 2020 with an explanatory footnote sent in by a reader.

When I started playing with VTL-2, another small and obscure language was included in the same download: MINOL. Inspired by BASIC syntax and written by a high-schooler in 1976, it “has a string-handling capability, but only single-byte, integer arithmetic and left-to-right expression evaluation.” What I am assuming is the official spec PDF was seemingly submitted over several letters to and subsequently published by the magazine, “Dr. Dobb’s Journal of Computer Calesthenics and Orthodontia.” This article described the purpose and syntax of the language, as well as the code for the Altair interpreter.

MINOL has 12 statements: LET, PR(int), IN(put), GOTO, IF, CALL, END, NEW, RUN, CLEAR, LIST, and OS (to exit the interpreter).As quoted above, there is integer arithmetic (+-*/), and there are three relational operators, =, <, and the inexplicably-designated #1 for not equal. Line numbers are single-byte, with a maximum of 254 lines. Statements can be separated with a colon. Exclamation points are random numbers. If (immediately) running a line without a line number, GOTO calls its line number 0. Rudimentary string-handling seems to be the big sell. This basically entails automatically separating a string into individual code points and popping them into memory locations, as well as some means of inverting this process. An included sample program inputs two strings and counts the number of instances of the second string in the first; being a bunch of code points contiguous in memory, it is certainly functional.

Is MINOL interesting, as a hobbyist/golf language? I may very well try one or two string-based challenges with it. Its limitations are quirky and could make for a fun challenge. I think more than anything, however, I’m just fascinated by this scenario that the Altair and similar early micros presented. Later micros like the Commodore PET booted right into whatever version of BASIC the company had written or licensed for the machine, but these early micros were very barebones. Working within the system restrictions, making small interpreters, and designing them around specific uses was a very real thing. It’s hard to imagine languages like MINOL or VTL-2 with their terse, obscure, limited syntaxes emerging in a world where every machine boots instantly into Microsoft BASIC.

Once again, I don’t know how much value there is in preserving these homebrew languages of yore, but as I mentioned when discussing VTL-2, folks nowadays generate esoteric languages just to mimic Arnold Schwarzenegger’s speaking mannerisms. Given that climate, I think there’s a pretty strong case to keep these things alive, at least in a hobbyist capacity. And given the needs of early micro hobbyists, I find the design of these languages absolutely fascinating. I’m hopeful that I can dig up others.


VTL-2: golfing and preservation

I’ve been playing with Gary Shannon and Frank McCoy’s minimalist programming language from the ‘70s, VTL-2 PDF as of late. Written for the Altair 8800 and 680 machines, it was designed around being very small – the interpreter takes 768 bytes in ROM. It has quite a few tricks for staying lean: it assumes the programmer knows what they’re doing and therefore offers no errors, it uses system variables in lieu of many standard commands, and it requires that the results of expressions be assigned to variables. It is in some ways terse, and its quirks evoke a lot of the fun of the constrained languages of yore. So, I’ve been playing with it to come up with some solutions for challenges on Programming Puzzles and Code Golf Stack Exchange (PPCG)1.

I mentioned that it is in some ways terse, and this is a sticking point for code golf. VTL-2 is a line-numbered language, and lines are rather expensive in terms of byte count. Without factoring in any commands, any given line requires 4 bytes: (always) two for the line number, a mandatory space after the line number, and a mandatory CR at the end of the line. So, at a minimum, a line takes 5 bytes. This became obvious when golfing a recent challenge:

3 B=('/A)*0+%+1

saved a byte over

3 B='/A
4 B=%+1

These almost certainly look nonsensical, and that is largely because of two of the things I mentioned above: the result of an expression always needs to be assigned to a variable, and a lot of things are handled via system variables instead of commands. For example, ' in the code above is a system variable containing a random number. There is no modulo nor remainder command, rather % is a system variable containing the remainder of the last division operation. Thus originally, I thought I had to do a division and then grab that variable on the next line. As long as the division is performed, however, I can just destroy the result (*0) and add the mod variable, making it a single shot. It’s a waste of our poor Altair’s CPU cycles, but I’m simulating that on modern x64 hardware anyway. And despite the extra characters, it still saves a byte2.

Other notable system variables include ? for input and output:

1 A=?
2 ?="Hello, world! You typed "
3 ?=A

Line 1 takes input – it assigns variable A to the I/O variable, ?. Line 2 prints “Hello, world! You typed &rquo;, and then line 3 prints the contents of variable A. Lines 2 and 3 assign values to the I/O variable. The system variable # handles line numbers. When assigned to another variable (I=#), it simply returns the current line number. When given an assignment (#=20), it’s akin to a GOTO. The former behavior seems like it could come in handy for golf: if you need to assign an initial value to a variable anyway, you’re going to be spending 4 bytes on the line for it. Therefore, it may come in handy to, say, initialize a counter by using its line number: 32 I=#.

Evaluation happens left-to-right, with functional parentheses. Conditionals always evaluate to a 1 for true and a 0 for false. Assigning the line number variable to a 0 in this way is ignored. With that in mind, we can say IF A==25 GOTO 100 with the assignment #=A=25*100. A=25 is evaluated to a 1 or a 0 first, and this is multiplied by 100 and # is assigned accordingly. ! contains the last line that executed a #= plus 1, and therefore #=! is effectively a RETURN.

There’s obviously more to the language, which I may get into in a future post3. Outside of the syntactical quirks which make it interesting for hobbyist coding, the matter of running the thing makes it less than ideal for programming challenges. Generally speaking, challenges on PPCG only require that a valid interpreter exists, not that one exists in an online interpreter environment such as Try It Online (TIO). In order to futz around in VTL-2, I’m running a MITS Altair 8800 emulator and loading the VTL-2 ROM. TIO, notably, doesn’t include emulation of a machine from the ‘70s with a bundle of obscure programming language ROMs on the side.

This brings me to my final point: how much effort is being put into preserving the lesser-known programming languages of yore, and how much should be? I personally think there’s a lot of value in it. I’ve become so smitten with VTL-2 because it is a beautiful piece of art and a brilliant piece of engineering. Many languages of that era were, by the necessity of balancing ROM/RAM limitations with functionality and ease of use. Yet, there’s no practical reason to run VTL-2 today. It’s hard to even justify the practicality of programming in dc, despite its continued existence and its inclusion a requirement for POSIX-compliance. New esoteric languages pop up all the time, often for golfing or for sheer novelty, yet little to no effort seems to be out there to preserve the experimental languages of yesteryear. We’re seeing discussions on how streaming gaming platforms will affect preservation, we have archive.org hosting a ton of web-based emulators and ROMs, we have hardware like Applesauce allowing for absolutely precise copies to be made of Apple II diskettes. Yet we’re simply letting retro languages… languish.

To be clear, I don’t think that this sort of preservation is akin to protecting dying human languages. But I do think these forgotten relics are worth saving. Is “Hello, world!” enough? An archive of documentation? An interpreter that runs on an emulator of a machine from 1975? I don’t know. I don’t feel like I have the authority to make that call. But I do think we’re losing a lot of history, and we don’t even know it.


On Twine (and my first Twine project)

Twine is, by its own definition, “an open-source tool for telling interactive, nonlinear stories”. I, personally, would call it a templating language for HTML-based interactive fiction. I have finally gotten around to experimenting with it, and… I find it to be missing the mark in the way that many templating systems tend to, and the way that many ‘friendly’ languages tend to.

Before I dive into my struggles with Twine, I’d just like to drop a link to the result of this experiment: yum yum you are a bread, which I guess I’ll just call a bread simulator? I don’t know. It’s silly, it’s fun, it’s bread. Also, minor spoilers in the rest of the post.


"I don't know what to say" (external)

I’m behind on posting about this, but given my potential audience, I wouldn’t be doing so as a warning anyway but rather a curiosity. A couple of weeks ago, malicious code was discovered in an npm package called flatmap-stream placed as a dependency inside event-stream. Publish rights to event-stream were apparently handed off to the bad actor, a user with no history whatsoever, because according to the original author:

he emailed me and said he wanted to maintain the module, so I gave it to him. I don’t get any thing from maintaining this module, and I don’t even use it anymore, and havn’t for years.

The attack was quite targeted – a payload was encrypted using the description of another package, the code would only be executed if this package was present. It appears that the end goal was getting bitcoin wallet access, as this targeted package was directly related to the Copay wallet. I don’t have much experience with npm, but I’ve gathered that its approach to dependencies is decentralized ownership/maintenance with centralized package lists/names/etc. It also seemingly pushes minor updates (as declared by the author) automatically, but not major ones. The vector of attack here was quite fascinating then: find a package that doesn’t appear to have been maintained for a while and that is often used alongside a well-maintained package that you want to infiltrate; ask to maintain the first package; push malicious code as a minor update and remove it immediately in a major update; sit back as it makes its way through projects everywhere.

Title link goes to the event-stream issue thread, which is well worth reading for information on the discovery, the forensics process, and a bit of back-and-forth about maintainer responsibility in the open source world. Additionally, in a gist, the original author responded to these issues of responsibility. Finally, if you don’t want to piece it together via the thread, Zach Schneider has an excellent explanation of the attack.


Dotfile highlights: .vimrc

I use zsh, and portability across Darwin, Ubuntu, Red Hat, cygwin, WSL, various gvims, etc. means I may have pasted something in that’s system-specific by accident.

New series time, I guess! I thought for the benefit of my future self, as well as anyone who might wander through these parts, there might be value in documenting some of the more interesting bits of my various dotfiles (or other config files). First up is .vimrc, and while I have plenty of important yet trivial things set in there (like set shell=zsh and mitigating a security risk with set modelines=0), I don’t intend to go into anything that’s that straightforward. But things like:

"uncomment this on a terminal that supports italic ctrl codes
"but doesn't have a termcap file that reports them
"set t_ZH=^[[3m
"set t_ZR=^[[23m

…are a bit more interesting. I do attempt to maintain fairly portable dotfiles, which means occasionally some of the more meaningful bits start their lives commented out.

Generally speaking, I leave word wrapping on, and I don’t hard wrap anything1. I genuinely do not understand the continuing practice of hard wrapping in 2018. Even notepad.exe soft wraps. I like my indicator to be an ellipsis, and I need to set some other things related to tab handling:

"wrap lines, wrap them at logical breaks, adjust the indicator
set wrap
if has("linebreak")
	set linebreak
	set showbreak=…\ \ 
	set breakindentopt=shift:1,sbr
endif

Note that there are two escaped spaces after the ellipsis in showbreak. I can easily see this trailing space because of set listchars=eol:↲,tab:→\ ,nbsp:·,trail:·,extends:…,precedes:…. I use a bent arrow in lieu of an actual LFCR symbol for the sake of portability. I use ellipses again for the ‘more stuff this way’ indicators on the rare occasions I turn wrapping off (set sidescroll=1 sidescrolloff=1 for basic unwrapped sanity). I use middots for both trailing and non-breaking spaces, either one shows me there’s something space-related happening. I also only set list if &t_Co==256, because that would get distracting quickly on a 16 color terminal.

Mouse handling isn’t necessarily a given:

if has("mouse") && (&ttymouse=="xterm" || &ttymouse=="xterm2")
	set mouse=a "all mouse reporting.
endif

I’m not entirely sure why I check for xterm/2. I would think it would be enough to check that it isn’t null. I may need to look into this. At any rate, the variable doesn’t exist if not compiled with +mouse, and compiling with +mouse obviously doesn’t guarantee the termcap is there, so two separate checks are necessary.

I like my cursors to be different in normal and insert modes, which doesn’t happen by default on cygwin/mintty. So,

"test for cygwin; not sure if we can test for mintty specifically
"set up block/i cursor
if has("win32unix")
	let &t_ti.="\e[1 q"
	let &t_SI.="\e[5 q"
	let &t_EI.="\e[1 q"
	let &t_te.="\e[0 q"
endif

Trivial, but very important to me:

"make ctrl-l & ctrl-z work in insert mode; these are crucial
imap <C-L> <C-O><C-L>
imap <C-Z> <C-O><C-Z>

I multitask w/ Unix job control constantly, and hugo server’s verbosity upon file write means I’m refreshing the display fairly often. Whacking Ctrlo before Ctrll or Ctrlz is easy enough, but I do it enough that I’d prefer to simplify.

I have some stuff in for handling menus on the CLI, but I realize I basically never use it… So while it may be interesting, it’s probably not useful. Learning how to do things in vim the vim way is generally preferable. So, finally, here we have my status line:

if has("statusline")
	set laststatus=2
	set statusline=%{winnr()}%<:%f\ %h%m%r%=%y%{\"[\".(&fenc==\"\"?&enc:&fenc).((exists(\"+bomb\")\ &&\ &bomb)?\",B\":\"\").\"]\ \"}%k\ %-14.(%l,%c%V%)\ %P
endif

I don’t like my status line to be too fancy, or rely on anything nonstandard. But there are a few things here which are quite important to me. First, I start with the window number. This means when I have a bunch of splits, I can easily identify which I want to switch to with (say) 2Ctrlww. I forget what is shown by default, but toward my right side I show edited/not, detected filetype, file encoding, and presence or lack thereof of BOM. Here’s a sample:

2<hfl.com/content/post/2018-02/vimrc.md [+][markdown][utf-8]  65,6           Bot

That’s about everything notable from my .vimrc. Obviously, I set my colorscheme, I set up some defaults for printing, I set a few system-dependent things, I set some things to pretty up folds. I set spell; display=lastline,uhex; syntax on; filetype on; undofile; backspace=indent,eol,start; confirm; timeoutlen=300. I would hesitantly recommend new users investigate Tim Pope’s sensible.vim, though I fundamentally disagree with some of his ideas on sensibility (incsearch?2 autoread? Madness).


Interpreting 69lang (a ;# dialect) in dc

PPCG user caird coinheringaahing came up with a language, ;#, and a code golf challenge to implement an interpreter thereof. The language has two commands: ; adds one to the accumulator, # mods the accumulator 127, outputs its ASCII counterpart, and resets the accumulator. It is, quite clearly, a language that only exists for the sake of this challenge. I mostly do challenges that I can do in dc, which this challenge is not (dc simply cannot do anything with strings).

What I can do is establish a dialect of ;# wherein the commands are transliterated to digits1. I’ve opted for 6 and 9, because I am a mature adult. So, assuming the input is a gigantic number, the challenge is fairly trivial in dc: 0sa[10~rdZ1<P]dsPx[6=Ala127%P0sa]sR[la1+saq]sA[lRxz0<M]dsMx

0sa initializes our accumulator, a, to zero. Our first macro, [10~rdZ1<P]dsPx breaks a (presumably very large) number into a ton of single-digit entries on the stack. ~ yields mod and remainder, which makes the task quite simple – we keep doing ~10, reversing the top-of-stack, and checking the length of our number. Once it’s down to a single digit, our stack is populated with commands.

The main macro, [lRxz0<M]dsMx runs macro R, makes sure there are still commands left on the stack, and loops until that is no longer true. R, that is, [6=Ala127%P0sa]sR tests if our command is a 6 (nee ;), and runs A if so. A has a q command in it that exits a calling macro, which means everything else in R is essentially an else statement. So, if the command is a 9 (or, frankly, anything but a 6), it does the mod 127, Print ASCII, and reset a to zero stuff. All we have left is [la1+saq]sA, which is macro A, doing nothing but incrementing a.

66666666666666666666666666666666666666666666666666666666666666666666666696666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666696666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666669666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666966666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666696666666666666666666666666666666666666666666696666666666666666666666666666666696666666666666666666666666666666666666666666666666666666666666666666666666666666666666669666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666966666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666696666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666669666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666696666666666666666666666666666666669
0sa[10~rdZ1<P]dsPx[6=Ala127%P0sa]sR[la1+saq]sA[lRxz0<M]dsMx

Hello, World!

SVGs

For someone rooted in graphic design and illustration, I typically hate running across visuals on the internet. Aside from being numbed by ads, the fact of the matter is that a large percentage of the graphical presentation on the web is just bandwidth-stealing window dressing with little impact on the surrounding content. Part of my plan with this blog was to avoid graphics almost entirely, and yet over the past month or so, I have littered this space with a handful of SVGs. I think, for the most part, they have added meaningful visual aids to the surrounding content, but I still don’t want to make too much of a habit of it.

I’m far more comfortable with SVGs (or, vector graphics in general) because I find it easier to have them settle onto the page naturally without becoming jarring. I could obviously restrict the palette of a raster image to the palette of my site, and render a high resolution PNG with manageable file size, but scaling will still come into play, type may be mismatched… aside from being accessibility issues, these things have subtle effects on visual flow. I’m thankful that SVG has been adopted as well as it has, and that it’s relatively simple to write or manipulate by hand. Following is the process I go through to make my graphics as seamless as possible.

Generally speaking, the first step is going to be to get my graphic into Illustrator. Inside Illustrator, I have a palette corresponding to my site’s colors. Making CSS classes for primary, secondary, tertiary colors is in my to-do list, but I need to ensure nothing will break with a class defining both color and fill. Groups and layers (mostly) carry over when Illustrator renders out an SVG, so I make a point of going through the layer tree to organize content. Appearances applied to groups cascade down in the output process, so (as far as SVG output is concerned) there’s no point in, say, applying a fill to a group – each individual item will get that fill in the end anyway. I use Gentium for all of the type, as that is ideally how it will be rendered in the end, though it’s worth quickly checking how it all looks in Times New Roman as well.

Once I get things colored and grouped as I need them, I crop the artboard to the artwork boundaries. This directly affects the SVG viewbox, and unless I need extra whitespace for the sake of visually centering a graphic, I can rely instead on padding or the like for spacing.

Once in the SVG Save dialog, I ensure that ‘Type’ is set to ‘SVG’. I don’t want anything converted to an outline, because I want the type to visually fall back with the rest of my page. I never actually save an SVG file from Illustrator, I just go to ‘SVG Code…’ from the Save dialog, and copypaste it elsewhere for further massaging. This involves:

Illustrator seemingly outputs SVG with the intent being structural accuracy if the file is read back in for editing, which is often counterproductive for web use, which would prioritize small filesize without a sacrifice in selection ordering or visual accuracy. To be fair, I just installed 2018 and haven’t tested its SVG waters yet, so we’ll see how Adobe managed to mess that up handle that.

Finally, it’s worth mentioning SVGO (and the web-based SVGOMG). Very customizable optimization, definitely more useful once one starts dealing with more intricate, complicated SVGs. I’m happy to optimize mine down by hand, and stop there – but I’m keeping them to a handful of kilobytes anyway.


Aztec diamonds: Testing the reversed Aztec numbers

My initial test of x=ceil(sqrt(2y)/2) to determine the size of a square given a value in A046092 corresponding to how many line segments would remain if the grid formed internally at every unit of height and width of the square was broken at every intersection was tested and shown to be valid for the first 1000 numbers in the sequence. I did this haphazardly in Excel, just to make sure it wasn’t going to fail quickly.

I have since scripted a test in python, which has thus far shown my method viable up to a 50907428697×50907428697 square. The script is called by passing it an argument containing the initial integer for the square’s size (default 2), and it loops infinitely until it either fails or is halted with SIGINT. Upon halting, it returns something like Last success: Square 39033633; azNum 3047249088424644; urNum 39033633.0, where Square is the height/width of the square being tested, azNum is the number of line segments (or squares in the equivalent Aztec diamond), and urNum is the calculation which (hopefully) is equal to Square. Revealing the last success in this way tells me where to start next time. The code:

import signal
import sys
from math import ceil,sqrt
def sigintHdl(signal,f):
    print "Last success: Square %s; azNum %s; urNum %s" % (tNum-1,azNum,urNum)
    sys.exit(0)
signal.signal(signal.SIGINT,sigintHdl)
tNum = 2 if len(sys.argv)<2 or int(sys.argv[1])<2 else int(sys.argv[1])
result=0
while result==0:
    azNum=tNum**2+tNum*(tNum-2)
    urNum=ceil(((2*azNum)**.5)/2)
    result=urNum-tNum
    tNum+=1
print "FAILURE: Square %s; azNum %s; urNum %s" % (tNum-1,azNum,urNum)

There’s another way of looking at this whole thing. If we consider an isosceles right triangle with hypotenuse h, we know the length of either of the legs is equal to sqrt(h^2/2). Interestingly enough, if we work with a hypotenuse of one unit larger (which should never exist as a halved Aztec diamond), h^2/2 is equal to our A046092 value +0.5.

Adding one unit to our central line yields seven units; squaring seven and then halving the result yields 24.5. 7

Ultimately, the problem seems to be one of dealing with a not-quite-proper triangle. It’s easy to imagine additional nodes that make the triangle more… triangular. Doing so leads to more funny math, but it all sort of, kind of makes sense. I guarantee there’s an off-the-shelf solution out there, and it’s likely quite straightforward and, in hindsight, obvious. But this sort of math isn’t necessarily my forté, so I’ll just fidget around until I come up with something conclusive. At this point, it’s all for fun – I have far more known-valid values than I could ever imagine needing. My little python test snippet will easily be reused for other things as well, so I’ll call that a win.


Golfing in Eukleides

Eukleides is decidedly not a golfing language, but when a geometry-related question came up on PPCG, I had to give it a shot. Eukleides can be quite rigid; for starters it is very strongly typed. Functions are declared by what they intend to return, so while set would be the shortest way to declare a function, it can’t really be exploited (unless returning a set is, in fact, desired). Speaking of sets, one thing that is potentially golfable is ‘casting’ a point to a set. Given a point, p, attempting a setwise operation on p will fail because a point does not automatically cast to a set (strict typing). p=set(p) will overwrite point p with a single-item set containing the point that was p. If, however, it is okay to have two copies of the point in the set, p=p.p is three bytes shorter.

If user input is required, the command number("prompt") reads a number from STDIN. The string for the prompt is required, though it can be empty (""). Thus, if more than four such inputs (or empty strings for other purposes) are required, it saves bytes to assign a variable with a one-letter name to an empty string.

Whitespace is generally unavoidable, but I did come to realize that boolean operators do not need to be preceded by whitespace if preceded by a number. So, if a==7or a==6 is perfectly valid. aor a, 7ora, 7 or6 are all invalid, however. This may be an interpreter bug, but for the time being it is an exploitable byte.

Finally, loci. Loci are akin to for-loops that automagically make sets. Unfortunately, they don’t seem to care much for referencing themselves mid-loop, which meant that I couldn’t exploit how short of a construction they are compared to manually creating a set in a for-loop.

This was a fun exercise, and just goes to show that if you poke around at any language enough, you’ll find various quirks that may prove useful given some ridiculous situation or another.


Tetris has been implemented in Conway's Game of Life (external)

Over four years ago, a challenge was posed on the Programming Puzzles & Code Golf Stack Exchange: Build a working game of Tetris in Conway’s Game of Life (GoL). Yesterday, an incredibly dedicated team of seven posted a working solution that is just fantastic to read about. I am flabbergasted by the work that went into this, and what these folks achieved. Starting with the concept of a metapixel – essentially a giant block of GoL tiles that can be programmed to behave like a single GoL cell, but with any ruleset – they developed wiring, logic gates, an ALU, a RISC architecture, an assembly language, a higher-level language, and finally (for now) a working game of Tetris. Not the first example of advanced computation in GoL (Wireworld is well known), but almost certainly the largest in scope and likely the best-documented as well. I linked to the Stack Exchange page, and if you have any knowledge of GoL, logic gates, or low-level computing, the multiple write-ups are incredibly clear and fascinating.


Eukleides

Despite having failed out of geometry in my younger days, it has become my favorite sort of recreational math. I think, back in elhi geometry, too much emphasis was placed on potential practical applications instead of just distilling it down to the reality that this was what math was before there was any sort of formal mathematical system. Geometry is hands-on, it’s playful, and as such I have come to really enjoy playing with it. As much as I enjoy doing constructions with a straightedge and compass, I occasionally poke around to see what tools exist on the computer as well. Recently, I stumbled across a very neat thing: Eukleides.

I’m drawn to Eukleides because it is a language for geometry, and not a mouse-flinging WYSIWYG virtual compass. This seems contradictory given my gushing about geometry being hands-on, and don’t get me wrong – I love a hands-on GUI circle-canvas too1. But sometimes (often times) my brain is in code-mode and it’s easier to express what I’m trying to do in words than to fiddle around with a mouse. And a task like ‘intersecting a couple of circles’ is far more conducive to writing out than, say, laying down an SVG illustration from scratch.

a b c d e bi

There you have one of the first constructions learned by anyone studying geometry – bisecting an angle with three arcs (or, full-blown circles in this case). Angle ∠abc is bisected by segment bbi. Here’s the code:

% Percent signs are comments
a=point(7,0); b=point(0,0) % Semicolons and newlines separate commands
a b c triangle 5,-40°
g=circle(b,3)
d=intersection(g,a.b); e=intersection(g,b.c)
d=d[0]; e=e[0] % Intersections return sets (arrays), extract the points
h=circle(d,3); i=circle(e,3)
bi=intersection(h,i)
bi=bi[1]
label
  a 0°; b 180°; c 40° % Label the points
  d -40° gray; e 90° gray
  bi 20°
  a,b,bi; bi,b,c 1.5 % Make the angle markers
end
draw
  c.b.a
  g lightgray; h gray
  i gray
  bi
  b.bi
end

Note that the code originally used shades of grey, I shifted these around to match my site’s colors when I converted the resulting EPS file to SVG. The code is pretty straightforward: define some points, make an angle of them, draw a circle, intersect segments ab and bc, make some more circles, intersect where the circles meet, and boom – a bisected angle. The language reminds me a bit of GraphViz/DOT – purpose-built for naturally expressing how things will be drawn.

We can actually prove that the construction works without even generating an image file. Removing the draw and label sections, and replacing them with some print (to stdout) statements calling angle measurement functions:

a=point(7,0); b=point(0,0)
a b c triangle 5,-40°
g=circle(b,3)
d=intersection(g,a.b); e=intersection(g,b.c)
d=d[0];e=e[0]
h=circle(d,3); i=circle(e,3)
bi=intersection(h,i)
bi=bi[1]
%%%%%%%% New content starts here:
print angle(a,b,c)
print angle(a,b,c)/2
print angle(a,b,bi)
print angle(bi,b,c)

We get ∠abc, ∠abc/2, ∠abbi, and ∠bcbi. The last three of these should be equal, and:

40
20
20
20

…they are! We can also do fun things like dividing the circumference of a circle by its diameter:

print (perimeter(circle(point(0,0),4))/8)

…to get 3.14159. Very cool. There are a few improvements I would like to see. Notably, while you can label points etc. with their names, I can’t find a way to add arbitrary labels, or even labels based on functions. So you can’t (seemingly) label a line segment with its length, or an angle with its measure. Also, the interpreter wants ISO 8859-1 encoding, and it uses the degree symbol2 (°) to represent angle measures. This gets all flippy-floppy when moving to UTF-8, and in fact if I forget to convert a file to ISO 8859-1, I’ll get syntax errors if I use degree symbols. Finally, it only outputs to EPS; native SVG would be incredibly welcome.

Eukleides is a lot of fun to play with, and it’s worth mentioning that it has looping and conditionals and the like, so it is programmable and not just computational or presentational. Presumably some pretty interesting opportunities are thus opened up.


Nth-order Fibonacci sequence in dc

After working on the nearest Fibonacci number problem in dc, I got to thinking about how one might implement other generalized Fibonacci sequences in the language. Nth-order sequences seemed like a fun little challenge, and since I was simply doing it for my own pleasure I went ahead and gave it prompts and user input:

% dc -e '[_nacci? ]n?1-sg[terms? ]n?2-snlgsi[0lid1-si1<Z]dsZx1[dls+ssli:flid1+silg>G]sG[li;flid1-si0<R]sRlgsz[0si0sslGxlgsilRxlslzd1+szln>M]dsMxf'
_nacci? 4
terms? 20
20569
10671
5536
2872
1490
773
401
208
108
56
29
15
8
4
2
1
1
0
0
0

…gives us the first 20 terms of the tetranacci sequence. This interested me because unlike a simple Fibonacci iteration that can be handled on the stack with only rudimentary stack manipulation (dsf+lfr), higher order ‘naccis need summation of more terms. For a defined number, I could simply use registers, but dc does support arrays, so setting the order at runtime is plausible. There’s a bit going on here, so I’m going to start by rattling off all of the registers I use:

g:
The order (so, a g-nacci sequence)
n:
Number of terms to run through
s:
Sum
i:
General counter
f:
Array used to temporarily hold the last sequence as it’s being summed
G:
Generalized Fibonacci generating macro
R:
Macro to retrieve previous sequence from f
Z:
Zero-seed macro
z:
Counter for iterations (compares to n)
M:
Main macro

Now to break down what’s going on. [_nacci? ]n?1-sg[terms? ]n?2-sn just prompts the user and inputs g and n. We reduce each of these in the process to appease the loops. After doing this, we need to seed the sequence with g-1 zeroes, and one one. lgsi sets counter i to g, and then the macro Z, does nothing but put a zero on the stack and loop: [0lid1-si1<Z]1. dsZx stores the macro and executes it; then 1 pushes the necessary one onto the stack such that we can begin.

[dls+ss]sS is our macro, S, which is a simple summer for register s. It duplicates the top of stack, recalls s, adds the two together, and then writes that back to s. The stack is returned to its original state.

Our next macro, G, has a bit more going on: [dls+ssli:flid1+silg>G]sG. It starts with a simple summer for register s, dls+ss. This duplicates the stack, recalls s, adds them and then overwrites s with the new sum. The stack returns to its original state. The next thing we need to do is move the top of the stack into our holding array, f. We’ll use our counter i as an index, so we load i and then do the array operation, li:f. Every time we do these two things, our summation (the next number in the sequence) nears its next value, and our stack shrinks. The rest of the macro, lid1+sig>G just handles incrementing i and comparing it to our order, g, determining whether or not to continue the loop.

Macro R, [li;flid1-si0<R]sR repopulates the stack from array f. Before calling R, i is set to g, and we use that as our array index to pull from, thus treating the array as a LIFO2. li;f does this, and then the rest of the macro is (surprise, surprise) counter/loop handling.

Before we run macro M, which is our main macro essentially, we set counter z to our order number g, which accounts for the fact that we already have our first few terms in assorted zeroes and a one. M, [0si0sslGxlgsilRxlslzd1+szln>M]dsMx, starts out by resetting counter i and the sum register s to zero: 0si0ss. lGx runs macro G, lgsi sets counter i to our order g, and then lRx runs macro R. ls puts our sum (the new Fibonacci value) at the top of the stack, and then the rest of the thing is counter/loop handling. dsMx saves the macro as M and also sets it running, while our last command, f prints the entire stack.


Finding the greatest Yahtzee score

A little over a year after writing this post, I decided to make a code golf challenge of it. Not too many people submitted answers, but there was a wild one in MS-DOS Batch, as well as some interesting tricks I hadn’t thought of.

I’ve been meaning to implement a way to incorporate style or script requirements into my posts using Hugo frontmatter. I’m not there yet, and before I get there, I need a test post that requires one or the other. I thought a little toy that lets one play a turn (three rolls) of Yahtzee, and then returns the highest possible score of the roll would be a fun and simple demonstration. Aside from small straights wigging me out a little (and I still have a nagging feeling this can be optimized), it was indeed simple1 to come up with an optimal score search. Fortunately, for a single-turn score, we don’t need to worry about a few scoring rules: bonus (joker) Yahtzees, the upper row bonus, nor chance. We could implement chance easily, but it really doesn’t make sense for single-turn scoring.


dc Syntax for Vim

This is an old post from an old blog; assets may be missing, links may be broken, and my opinions may differ considerably by this point…

I use dc as my primary calculator for day-to-day needs. I use other calculators as well, but I try to largely stick to dc for two reasons - I was raised on postfix (HP 41CX, to be exact) and I'm pretty much guaranteed to find dc on any *nix machine I happen to come across. Recently, however, I've been expanding my horizons, experimenting with dc as a programming environment, something safe and comfortable to use as a mental exercise. All of that is another post for another day, however - right now I want to discuss writing a dc syntax definition for vim.