Integers to intervals (Haskell solution)

This is the known task ("problem" from Clojure problems list): to convert integers list to intervals by merging they... See:

[1,2,3,5,7,6,10] -> [<1,3>,<5,7>,10]

First, I create type El which is input list element and can be point or already interval (with simple factory iv). Relation Rel is needed to determine relative location of point and interval. Join of point to interval is based on this result. joinToIv joins point to interval and returns possible new one. Function joinToIvs joins point to one of intervals but if it is not possible then returns original intervals with new one added. Main algorithm is a left folding of joinToIvs.

Code is very dirty and sure may be more short :-)

-- Dirty code of turn integers to intervals
module Intervals where

-- element is interval Iv of 2 integers or point of 1 integer
data El = Iv Integer Integer|Pt Integer
instance Show El where
  show (Iv n m)|n == m = show n
               |otherwise = "<" ++ show n ++ "," ++ show m ++ ">"
  show (Pt n) = show n

-- constructor for intervals from 2 integers
iv :: Integer -> Integer -> El
iv n m|n < m     = Iv n m
      |otherwise = Iv m n

-- relation pt/interval: L (left), LS (left-side), IN (included), RS (right-side), R (right)
data Rel = L|LS|IN|RS|R deriving Show

-- relation
rel :: El -> El -> Rel
rel (Iv a b) (Pt n)  |a - n == 1  = LS
                     |a - n > 1   = L
                     |b - n >= 0  = IN
                     |b - n == -1 = RS
                     |otherwise   = R
rel (Iv a b) (Iv c d)|c - b == 1 = RS
                     |otherwise  = R

-- join integer to element (which is expected to be interval)
-- joinToIv :: El -> Integer -> [El]
joinToIv :: El -> Integer -> Maybe El
joinToIv e@(Iv a b) n = let p = Pt n in
  case rel e p of
    LS -> Just $ iv n b
    IN -> Just e
    RS -> Just $ iv a n
    otherwise -> Nothing

-- join integer to list of intervals by extend some or add new one to the end
joinToIvs :: [El] -> Integer -> [El]
joinToIvs [] n = [iv n n]
joinToIvs (e:es) n =
  maybe ([e] ++ joinToIvs es n) (\e' -> _add e' es) (joinToIv e n) where
  _add (Iv a b) ((Iv c d):es1)|abs (c-b) == 1 = [Iv a d] ++ es1
  _add e1 es1 = [e1] ++ es1

-- Turn integers to intervals
toIv :: [Integer] -> [El]
toIv [] = []
toIv (n:ns) =
  foldl (joinToIvs) [iv n n] ns

--------------------------------------------------
main :: IO ()
main = print l >> print (toIv l) where
  l = [1,2,3,5,6,4,0,10,11,9,12,100,-1,80,99,101,98,8,7]

AWK Literate Programming Personal Tool

LAWK is the simple literate programming tool for personal usage (no collaboration features). For collaboration nanolp can be used see.

Input files are markdown, output - any one. Supports non-ASCII, Windows. Does not support spaces and other special chars in paths. Source is here.

Good feautures are:

• very clean syntax of definition, pasting, writing named chunks
• simple dependencies (awk, mkdir, rm, make) - available for Windows too
• no installation (only copy source somewhere)
• markdown input format
• no special syntax for code chunks
• ctags tag file generation (unsorted)

Fossil: remote clone on Windows from Linux

There is interesting DSCS - Fossil, written by SQLite3 author. When I tried to use it on remote Windows machines, I hit several problems: no local ssh.exe, problems with GSSAPI, authorization...

But these problems are solvable with SSH tunnel. Let's look at picture:

We can create SSH tunnel with Putty (SSH alternative for Windows, and not only) and connect with fossil HTTP server via it. One machine will keep fossil repo. First, we create it (I called it x):

fossil init x
fossil open x
fossil add somefile
fossil ci -m "init"
fossil ui

When fossil's UI will be opened, I add some user, for example, user and grant them permissions AND password. Then kill fossil with ^C and start it in serv mode (actually ui/serv mode lokks like the same). It will be bound to default port 8080 (you can see this on fig).

On remote machine we start Putty, create some session and in SSH tunnel section creates tunnel (in "destination" input box) with local port 7777, IP of fossile machine and fossil port 8080, result should be:

L7777 fossil_IP:8080

Also we set "Local", "Auto" (or "Dynamic" - works too).

In session section we set host to fossil IP (where we created repo!), auto-login with name of fossil machine user. Now save session and open it. We are see console window, enter password and don't close it (another way is to use Putty agent). Open new console and enter there:

fossil clone http://fossil-user@localhost:7777//path-to-x x
fossil open x

where path-to-x is the path to repo on fossil machine.

Now you have x repo locally. Works with them, commit, then push changes:

fossil push

If it ask password, enter it (this is the password of early created fossil user).

Parse hex chars string to bytes

Very simple task as for interview: to parse hex chars into bytes. Example: "123Ad" -> "\x12\x3A\x0D". This procedure can be helpfull if you want to transmit some encoding string (in UTF8, UTF16, mbcs, etc) between different processes/OS and it's probably to get broken bytes, so best solution will be to use such hex chars (it's ASCII [0-9a-fA-F] only).

Implementation in C may use sscanf() which will be slow or does not. Here is an example without sscanf:

#include <stdio.h>
#include "algutils.h"

int parse_hex_str(const char *s, int slen, char *out) {
#define __ord(c) \
    ((c) >= '0' && (c) <= '9'? (c) - '0' : \
     (c) >= 'a' && (c) <= 'f'? (c) - 'a' + 10 : \
     (c) >= 'A' && (c) <= 'F'? (c) - 'A' + 10 : -1)

    register int b, t, i;
    for (i=0; i<slen; i++) {
        t = __ord(s[i]);
        if (-1 == t) return (1);
        if (i%2) out[i/2] = (b << 4) | t;
        else     b = t;
    }
    if (i%2) out[i/2] = b;
    return (0);

#undef __ord
}

/*************************************************************/
int main() {
    unsigned char ins[] = "1230aAF0D";
    unsigned char out[20] = {0};
    int res = parse_hex_str(ins, sizeof(ins) - 1, out);
    printf("input = %s\n", ins);
    printf("res=%d\n", res);
    PRINTARRX(out, 10, "%02X");
    return (0);
}

Compilation:

gcc -ggdb -std=c99 -o hex.exe hex.c

Output:

input = 1230aAF0D
res=0
{ 12 30 AA F0 0D 00 00 00 00 00 }