Optimal full-align in a terminal (like emacs/vim)

A place to discuss the implementation and style of computer programs.

Moderators: phlip, Moderators General, Prelates

armedmonkey
Posts: 14
Joined: Sun Mar 14, 2010 4:36 pm UTC

Optimal full-align in a terminal (like emacs/vim)

Postby armedmonkey » Sat Mar 27, 2010 4:00 pm UTC

I'm trying to write a bit of code. The best way to describe it is, imagine writing a word processor for a console ui text editor like emacs/vim. Now imagine you needed to write a feature that full-justifies a bunch of text you typed.

Assumptions:
-arbitrary column number N
-monospace font
-cannot adjust spacING of words, just number of spaces between them.
-paragraph contains no line breaks (otherwise it's more than one paragraph)
-anything that's not a space is considered part of a word. for simplicity, let's say our charset is [a-z|\.| ] -- that's letters, period, space
-we want to use the minimal number of spaces possible and every subsequent space (in a row) is increasingly bad.
ie: the_cat___sat is worse than the__cat__sat.
we can express this by saying that the COST of some spaces after a word is (number_of_spaces-1)^k (where k>1). For simplicity, let's say 2.
so for the first example above... 0^2 + 3^2 = 9, and 1^2 + 2^2 = 5

What this means is, N, how do you add spaces and line breaks to a string of text such that the last character on each line is not a space.

I need my code to find the OPTIMAL (lowest overall cost) way to justify the paragraph.


Does anyone know of an algorithm that does this? Or know how to write one? I feel like I need to compute results on sub-paragraphs here, but i am not sure how to do it efficiently (ie not in exponential time).

You'd think there'd be plenty examples of this, but I can only find them where they adjust the spacing of words because they are using a rich text medium.

Unparallelogram
Posts: 336
Joined: Mon Jul 28, 2008 4:16 am UTC

Re: Optimal full-align in a terminal (like emacs/vim)

Postby Unparallelogram » Sat Mar 27, 2010 4:17 pm UTC

Dynamic programming. What you want is pretty similar to the usual line breaking problem, except you have a sort of different constraint about the end of lines being special. http://en.wikipedia.org/wiki/Word_wrap

armedmonkey
Posts: 14
Joined: Sun Mar 14, 2010 4:36 pm UTC

Re: Optimal full-align in a terminal (like emacs/vim)

Postby armedmonkey » Sat Mar 27, 2010 5:07 pm UTC

Yes, dynamic programming is the approach I'm trying to take right now. not having all that much luck just yet though.

User avatar
Xanthir
My HERO!!!
Posts: 5413
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: Optimal full-align in a terminal (like emacs/vim)

Postby Xanthir » Sat Mar 27, 2010 9:03 pm UTC

Knuth put together some wonderful algorithms for this when designing TeX. Check it out.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

Agent_Irons
Posts: 213
Joined: Wed Sep 10, 2008 3:54 am UTC

Re: Optimal full-align in a terminal (like emacs/vim)

Postby Agent_Irons » Thu Apr 01, 2010 8:21 am UTC

So many conversations on this board end "Go read Knuth". I should probably get the hint.

armedmonkey
Posts: 14
Joined: Sun Mar 14, 2010 4:36 pm UTC

Re: Optimal full-align in a terminal (like emacs/vim)

Postby armedmonkey » Thu Apr 01, 2010 12:29 pm UTC

As far as I have seen, Knuth's algorithms (and the nature of Tex itself) are exactly what I said I didn't want. Anyway, apologies for the late response, but the "Minimum Raggedness" section of that wiki was actually extremely helpful and was just what I needed.


Return to “Coding”

Who is online

Users browsing this forum: No registered users and 5 guests