Code Golf: Connecting the dots

Commodore 64 BASIC - 313 chars

EDIT: See below for the golfed version

A little trip down the memory lane with PET graphics, POKEs and PEEKs and everything :)

The program operates directly in the screen memory, so you just go ahead, clear the screen, place your dots, and type RUN:

You have to wait a minute or so while it finds the dots and then it starts to draw. It isn't fast - you can actually see the lines being drawn, but that's the coolest part :)

Golfed version:

Commodore BASIC seems like a great language for golfing, because it doesn't require whitespace :) You can also shorten most of the commands by entering an unshifted first letter followed by a shifted second letter. For example, POKE can be typed as P[SHIFT+O], which appears as P┌ on the screen:

Perl, 222 char (211)

Perl, 384 365 276 273 253 225 222 218 211 chars (222 when contest ended). Newlines are for "readability" only and are not included in the character count.

Last edit: no longer overwriting $", and printing @S directly

    $_=join'',@S=map{$n=s/$/$"x97/e;(/./g)[0..95],$/}<>;
    while(/\b$n /){$S[$q=$-[0]]='+';($P,$Q)=sort{$a-$b}$q,$p||$q;
    for(qw'\98 |97 /96 -1'){/\D/;$S[$P]=$&until($Q-$P)%$'||$Q<=($P+=$')}
    $n++;$p=$q}s/\d/ /,print for@S

Explanation:

$_=join'',@S=map{$n=s/$/$"x97/e;(/./g)[0..95],$/}<>;

This task will be easier if all the lines are the same length (say, 97 characters). This statement takes each line of input, replaces the end-of-line character with 96 spaces, then pushes the first 96 characters plus a newline into the array @S. Note we are also setting $n=1, as 1 is the first number we'll look for in the input. The join statement creates a single string from the array @S. It is more convenient to use the scalar variable $_ for pattern matching, and more convenient to use the array @S for making updates to the picture.

while(/\b$n /){

Search for the number $n in the variable $_. Evaluating regular expressions in Perl has several side-effects. One is to set the special variable $-[0] with the position of the start of the matched pattern within the matched string. This gives us the position of the number $n in the string $_ and also the array @S.

Of course, the loop will end when $n is high enough that we can't find it in the input.

    $S[$q=$-[0]]='+';

Let $q be the position of the number $n in the string $_ and the array @S, and assign the character '+' at that position.

        $P=($p||=$q)+$q-($Q=$q>$p?$q:$p)
        ($P,$Q)=sort{$a-$b}$p||$q,$q;

The first time through the loop, set $p to $q. After the first time, $p will hold the previous value of $q (which will refer to the position in the input of the previous number). Assign $P and $Q such that $P=min($p,$q), $Q=max($p,$q)

    for(qw'\98 |97 /96 -1'){

By construction, consecutive numbers are either

• connected by a vertical line. Since the input is constructed to have 97 characters on each line, this case means that $p-$q is divisible by 97.

• "aligned to the slope of a backslash", which would make $p-$q divisible by 98

• "aligned to the slope of a forward slash", which would make $p-$q divisible by 96

• on the same horizontal line

The elements of this list encode the possible number of positions between line segments, and the character to encode that segment.

        /\D/;

Another trivial regex evaluation. As a side-effect, it sets the special variable $& (the MATCH variable) to the line segment character (\ | / or -) and $' (the POSTMATCH variable) to the number (98 97 96 or 1) encoded in the list element.

        $S[$P]=$&until($Q-$P)%$'||$Q<=($P+=$')

This statement draws the line segment between two numbers. If $Q-$P is divisible by $', then keep incrementing $P by $' and assigning the character $& to $S[$P] until $P reaches $Q. More concretely, for example if $Q-$P is divisible by 97, then increment $P by 97 and set $S[$P]='|'. Repeat until $P>=$Q.

    $n++;$p=$q

Prepare for the next iteration of the loop. Increment $n to the next number to search for in the input, and let $p hold the position of the previous number.

s/\d/ /,print for@S

Output the array, converting any leftover digits (from double digit identifiers in the input where we only overwrote the first digit with a '+') to spaces as we go.