koldfront

Emarcheology #emacs #dynamic programming

๐Ÿ•“๏ธŽ - 2022-06-10

I randomly ended up reading the comments on this 6 year old blog post: export TERM=aaa-60 which sent me on to an archeology archive site of Emacs sources.

Paradoxically, or not, hosted on Microsoft GitHub.

Anyway, the blog comment referenced the top of the Gosling Emacs' display.c:


			 /-------------\
			/		\
		       /		 \
		      /			  \
		      |	  XXXX	   XXXX	  |
		      |	  XXXX	   XXXX	  |
		      |	  XXX	    XXX	  |
		      \		X	  /
		       --\     XXX     /--
			| |    XXX    | |
			| |	      | |
			| I I I I I I I |
			|  I I I I I I	|
			 \	       /
			  --	     --
			    \-------/
		    XXX			   XXX
		   XXXXX		  XXXXX
		   XXXXXXXXX	     XXXXXXXXXX
			  XXXXX	  XXXXX
			     XXXXXXX
			  XXXXX	  XXXXX
		   XXXXXXXXX	     XXXXXXXXXX
		   XXXXX		  XXXXX
		    XXX			   XXX

			  **************
			  *  BEWARE!!  *
			  **************

			All ye who enter here:
		    Most of the code in this module
		       is twisted beyond belief!

			   Tread carefully.

		    If you think you understand it,
			      You Don't,
			    So Look Again.

To optimize the number of changes done to update the screen a dynamic programming algorithm was used; here is another comment later in the file:

/*	1   2   3   4   ....	Each Mij represents the minumum cost of
      +---+---+---+---+-----	rearranging the first i lines to map onto
    1 |   |   |   |   |		the first j lines (the j direction
      +---+---+---+---+-----	represents the desired contents of a line,
    2 |   |  \| ^ |   |		i the current contents).  The algorithm
      +---+---\-|-+---+-----	used is a dynamic programming one, where
    3 |   | <-+Mij|   |		M[i,j] = min( M[i-1,j],
      +---+---+---+---+-----		      M[i,j-1]+redraw cost for j,2
    4 |   |   |   |   |			      M[i-1,j-1]+the cost of
      +---+---+---+---+-----			converting line i to line j);
    . |   |   |   |   |		Line i can be converted to line j by either
    .				just drawing j, or if they match, by moving
    .				line i to line j (with insert/delete line)
 */

Quite neat.

Add comment

To avoid spam many websites make you fill out a CAPTCHA, or log in via an account at a corporation such as Twitter, Facebook, Google or even Microsoft GitHub.

I have chosen to use a more old school method of spam prevention.

To post a comment here, you need to:

ยน Such as Thunderbird, Pan, slrn or Gnus (part of Emacs).

Or, you can fill in this form:

+=