You know we’ve come a long way when it is more expedient to explain to children that a byte is a quantity corresponding to roughly a billionth of another unit far more fundamental to them in their daily lives: the gigabyte. A hundred bytes is an atomic-level scale to the newest generation.  In the spirit of Robby Boey’s Commodore 64 sprite art with his daughters, I wanted to show mine that a small, quickly written program could be quite usable in solving her favorite word game from the daily newspaper.

A crytpoquip is a letter-substitution cipher (a cryptogram) that always reveals some witty observation or pun once every letter has been substituted for another, with never any mapping onto the same letter and not necessarily any reciprocal mappings. These constraints, together with context clues and the somewhat limited set of two- and three- letter words, allows the enthusiast to gradually crack the substitution code, which changes from one cryptoquip to another.  A hint is often given to get started, for example “S equals E.”

Besides the newspaper, it is possible to find solvable cryptograms on the web.  And whether as an algorithms demonstration or targeted at the impatient puzzler, there exist various automated solver programs on the web that utilize a standard (or selectable) language dictionary to remove all subtle insights from the path toward the solution.

Of course my homebrew version is in assembly language, both to get the size down (the hex codes for the loop itself fit on one 40×25 screen) and to illustrate that a  carefully programmed text-based 6502 platform can be at least as responsive as a comparable app running on a smartphone taking up 100,000 times the memory footprint.  In my interface, any character typed on the keyboard appears in the upper left corner of the screen.  The first character pressed shows up there in reverse video, with all instances of it in the cipher (as determined by a nonprinting character in the row below them) also highlighted in reverse.  Here is a screenshot from a puzzle with only one clue, the letter B, remaining:

puzzle1

The answer is obviously that the letter B in this cipher maps onto the letter H in the solution.  Pressing a second key when letters are highlighted equates (by way of printing it in normal video in the row superior) all the instances to that solution letter.  As the final step the comma is mapped onto itself, since punctuation and digits do not typically get mapped as part of the puzzle:puzzle2

Below is loader code that runs on the Commodore 16 series.  It uses the TED-series trick of allocating and then de-allocating a graphics screen to open up 12K of memory underneath BASIC without interrupting the program being run:crypto1-20

To achieve the compact size of 146 bytes, it is necessary to input the puzzle on a blank screen using the Commodore screen editor or as part of the BASIC loader: crypto30-230

Substitution continues in a loop even after all cipher characters have been mapped, since no such check is performed.  Here is the assembly code in crasm’s format.  With limited tweaks it should run under any Commodore BASIC, since it makes use of the standard Kernal routines for screen I/O and the character codes that use bit 7 as a reverse-video flag.  The equivalent C code appears in the comment at the end of the lines:

cpu	6502
page	0,132

	;; start of character codes (screen memory directly manipulated)
	TEDSCR = $0c00		; const TEDSCR = 0x0c00;
	TEDPAG = TEDSCR>>8	; const TEDPAG = TEDSCR>>8;

	;; space character (both ROM table index and ASCII)
	spc = $20		; const char spc = ' ';

	;; KERNAL jump vectors
	GETIN = $ffe4		; extern char GETIN(void);
	CHOUT = $ffd2		; extern void CHOUT(char);
	PLOT = $fff0		; extern void PLOT(boolean, short&, short&);

	;; 2-byte pointer to "answer" letter and "crypto" letter below it
	leta = $da		; char* leta;
	letc = $dc		; char* letc;

	code			; char cryp(short, short, short);

				; void shll(void) {
shll	lda	#$80		;  unsigned short stack = 0x80;
	pha			;  do {
shl1	clc			;   char a;
	ldx	#$00		;   short x = 0;
	ldy	#$00		;   short y = 0;
	jsr	PLOT		;   PLOT(0,x,y);
shl2	jsr	GETIN		;   do a = GETIN();
	beq	shl2		;   while (a == 0);
	jsr	CHOUT		;   CHOUT(a);
	pla			;
	and	#$80		;   stack &= 0x80; /* get char at (x,y) */
	eor	#$80		;   stack ^= 0x80; /* flip state bit */
	ldx	#$00		;
	ldy	#$00		;
	jsr	cryp		;
	pha			;   stack = cryp(stack, x, y);
	and	#$7f		;
	bne	shl1		;  } while (stack & 0x7f);
	pla			;
	rts			;  return;
				; }

;;; user must pass in pointer (X row>=0, Y col>=0) to set search start location,
;;; with character passed in A, whose MSB indicates whether this character
;;; is for highlighting "crypto" letters (clear) or substituting them (set)

				; short cryp(short a, short x, short y) {
cryp	sta	letc+1		;

	sty	leta		;
	ldy	#$28		;
	lda	#TEDPAG		;
	sta	leta+1		;

	;; add 1 row for each count of x
	clc			; 
xrow	tya			;
	adc	leta		;
	dex			;
	bmi	xro2		;
	bcc	xro1		;
	inc	leta+1		;
xro1	sta	leta		;
	clc			;
	bcc	xrow		;  leta = TEDSCR + x*40 + y;

	;; A and C conveniently tell us the value to go into higher-pointer LSB
xro2	sta	letc		;
	lda	leta+1		;
	adc	#$00		;
	ldy	letc+1		;
	sta	letc+1		;  letc = leta + 40;

	;; if Y (and thus the initial A) was zero, we use character at this pos
	ldx	#$00		;
	tya			;
	and	#$7f		;
	bne	test		;  if ((a & 0x7f) == 0)
	tya			;
	and	#$80		;
	ora	(leta,x)	;
	tay			;   a = (a & 0x80) | *leta;

test	tya			;  for (--letc; ++letc < TEDSCR + 1024; ++leta)
	bmi	tes2		;   if (a >= 0) { /* highlight crypto letters */

tes1	cmp	(leta,x)	;
	bne	tes3		;
	lda	#spc		;
	cmp	(letc,x)	;
	bne	tes3		;    if ((*leta == a) && (*letc == spc)) {
	cmp	(leta,x)	;     if (*leta == spc)
	beq	done		;      break;
	tya			;
	ora	#$80		;
	sta	(leta,x)	;     *leta |= 0x80; /* reverse video */
	bmi	tes3		;    }

tes2	lda	(letc,x)	;
	bpl	tes3		;   } else if (*letc == a) { /* show answers */
	and	#$7f		;
	sta	(letc,x)	;    *letc &= 0x80; /* normal video */
	tya			;
	and	#$7f		;
	sta	(leta,x)	;    *leta = *letc & 0x7f;

tes3	inc	letc		;   }
	bne	tes4		;
	inc	letc+1		;
	lda	letc+1		;
	cmp	#TEDPAG+4	;
	bpl	done		;
tes4	inc	leta		;
	bne	test		;
	inc	leta+1		;
	bne	test		;

done	tya			;
	rts			;  return a;
				; }

 

Advertisements