praxent pather

path-problem.sh

#!/bin/sh
cat <<PROB
Given that the text file 'input.txt' contains a rectangular block of dot
characters ('.') and two or more hash characters ('#'), write a program 'pather'
which writes out to 'output.txt' the same data with the two '#' characters
joined by asterisks ('*'). The command will be invoked like this:

  pather input.txt output.txt

Your job is to implement 'pather' in this directory. This script will run it
for you and test the accuracy of the output. The file 'pather' will need to
be executable (chmod +x pather). It maybe written in any language.

The rules for the path:

* No diagonals.
* Only change direction once per pair of hashes. 
* Start with a vertical line and then complete with a horizontal line.

Please feel free to write further tests if you believe the program can be
improved upon. Have fun with it.

PROB

cat <<INPUT >input.txt
........................
........................
....#...................
........................
........................
........................
........................
..................#.....
........................
........................
........................
........................
INPUT

cat <<EXPECTED >expected.txt
........................
........................
....#...................
....*...................
....*...................
....*...................
....*...................
....**************#.....
........................
........................
........................
........................
EXPECTED

cat <<EXPLAIN

Input:

`cat input.txt`

Expected Output:

`cat expected.txt`
EXPLAIN

if [ -x pather ]; then
  ./pather input.txt output.txt
else
  echo "PROBLEM: 'pather' does not exist in this directory or is not executable"
fi

cat <<CONCLUSION

Output:

`cat output.txt`

Diff:

`diff -u expected.txt output.txt`

CONCLUSION

cat <<INPUT >input-2.txt
........................
........................
....#.............#.....
........................
........................
........................
........................
........................
........................
........................
........................
........................
INPUT

cat <<EXPECTED >expected-2.txt
........................
........................
....#*************#.....
........................
........................
........................
........................
........................
........................
........................
........................
........................
EXPECTED

cat <<EXPLAIN

Input:

`cat input-2.txt`

Expected Output:

`cat expected-2.txt`
EXPLAIN

if [ -x pather ]; then
  ./pather input-2.txt output-2.txt
else
  echo "PROBLEM: 'pather' does not exist in this directory or is not executable"
fi

cat <<CONCLUSION

Output:

`cat output-2.txt`

Diff:

`diff -u expected-2.txt output-2.txt`

CONCLUSION

cat <<INPUT >input-3.txt
........................
........................
....#.............#.....
........................
........................
........................
........................
........................
............#...........
........................
........................
........................
INPUT

cat <<EXPECTED >expected-3.txt
........................
........................
....#*************#.....
..................*.....
..................*.....
..................*.....
..................*.....
..................*.....
............#******.....
........................
........................
........................
EXPECTED

cat <<EXPLAIN

Input:

`cat input-3.txt`

Expected Output:

`cat expected-3.txt`
EXPLAIN

if [ -x pather ]; then
  ./pather input-3.txt output-3.txt
else
  echo "PROBLEM: 'pather' does not exist in this directory or is not executable"
fi

cat <<CONCLUSION

Output:

`cat output-3.txt`

Diff:

`diff -u expected-3.txt output-3.txt`

CONCLUSION

cat <<INPUT >input-4.txt
........................
........................
....#.............#.....
........................
........................
........................
........................
........................
.#..........#...........
........................
........................
........................
....#.........#.........
........................
........................
.......#.............#..
........................
..#.....................
........................
INPUT

cat <<EXPECTED >expected-4.txt
........................
........................
....#*************#.....
..................*.....
..................*.....
..................*.....
..................*.....
..................*.....
.#**********#******.....
.*......................
.*......................
.*......................
.***#*********#.........
..............*.........
..............*.........
.......#*************#..
.....................*..
..#*******************..
........................
EXPECTED

cat <<EXPLAIN

Input:

`cat input-4.txt`

Expected Output:

`cat expected-4.txt`
EXPLAIN

if [ -x pather ]; then
  ./pather input-4.txt output-4.txt
else
  echo "PROBLEM: 'pather' does not exist in this directory or is not executable"
fi

cat <<CONCLUSION

Output:

`cat output-4.txt`

Diff:

`diff -u expected-4.txt output-4.txt`

CONCLUSION

pather

#!/usr/bin/env node
 
var fs = require('fs'),
    readline = require('readline');
 
// Stack is used to write lines of output hat may or may not
// contain a vertical path
function Stack(output, bgChar, pathChar, newline) {
    var a = [];
    // push adds a line with a vertical path char to the stack
    // index is where the path char will be written, and
    // length is the length of the line with no newline at the end
    this.push = function(index, length) {
        a.push([index, length]);
    };
    // write all the lines in the stack to output
    // if path is not true then we do not need to print the path chars
    // a newline will be appended to each line of output
    this.write = function(path) {
        var buf, el;
        for (el = a.pop(); el; el = a.pop()) {
            buf = new Buffer(el[1] + 1);
            buf.fill(bgChar);
            if (path === true) {
                buf[el[0]] = pathChar.charCodeAt(0);
            }
            buf[el[1]] = newline.charCodeAt(0);
            output.write(buf);
        }
    };
}
 
// return a boolean indicating if val is a number >= 0
function isIndex(val) {
    return typeof val === 'number' && val >= 0;
}
 
// print a usage message to a WritableStream
function usage(writer) {
    writer.write('Usage: ' + process.argv[1] + ' input.txt [output.txt]\n');
}
 
function main() {
    if (process.argv.length < 3) {
        usage(process.stderr);
        process.exit(1);
    }
 
    var stack,
        verticalIndex = -1, // position of vertical path char
        bgChar = '.',
        vertexChar = '#',
        pathChar = '*',
        newline = '\n',
        instream = fs.createReadStream(process.argv[2]),
        input = readline.createInterface({ input: instream }),
        output;
 
    if (process.argv.length === 3) {
        output = process.stdout;
    } else {
        output = fs.createWriteStream(process.argv[3]);
    }
 
    // whenever there might be a need to write lines with
    // a vertical path char we push them onto a stack because
    // we won't know whether we need to print the path chars
    // or not until we see a line with a vertex character
    stack = new Stack(output, bgChar, pathChar, newline);
 
    input.on('line', function(line) {
        var i, start, end,
            f = line.indexOf(vertexChar),
            l = line.lastIndexOf(vertexChar),
            buf = new Buffer(line + newline); // add the missing newline
 
        if (f >= 0) {
            // at least one vertex char
            // write the stack with path chars
            stack.write(true);
 
            if (isIndex(verticalIndex)) {
                // there is a vertical path leading to this line
                if (verticalIndex <= f) {
                    // verticalIndex is to the left of the first vertex
                    start = verticalIndex;
                    end = l;
                    // new vertical path will start from the last vertex
                    verticalIndex = l;
                } else if (verticalIndex < l) {
                    // verticalIndex falls between the first and last vertex
                    start = f;
                    end = l;
                    // new vertical path will start from the last vertex
                    verticalIndex = l;
                } else {
                    // verticalIndex is to the right of the last vertex
                    start = f;
                    end = verticalIndex + 1;
                    // new vertical path will start from the first vertex
                    verticalIndex = f;
                }
            } else {
                // go from first vertex char to last vertex char
                start = f;
                end = l;
                // new vertical path will start from the last vertex
                verticalIndex = l;
            }
            // write paths
            for (i = start; i < end; i++) {
                if (buf[i] === bgChar.charCodeAt(0)) {
                    buf[i] = pathChar.charCodeAt(0);
                }
            }
            output.write(buf);
            return;
        }
 
        // no vertex char, just push to the stack and return
        if (isIndex(verticalIndex)) {
            stack.push(verticalIndex, line.length);
            return;
        }
 
        // echo the line to output
        output.write(buf);
    });
 
    // write the stack without the path chars when there is no more input data
    instream.on('end', function() {
        stack.write(false);
    });
}
 
main();