The fastest, smallest Ubuntu Linux antivirus scanner

When I temporarily needed a laptop recently, my daughter kindly lent me an old laptop that she had replaced. It had Windows XP on it.

When I powered it up, I soon noticed that an antivirus scan was running since the machine hadn’t been used for months.

That scan ran … and ran .. and ran.

Whilst it was running, I realized that it was possible to write a very fast and very small Unbuntu antivirus scanner.

Not only is this scanner small and fast, it is also very portable. It runs on every version of Linux.

Here’s the code to create it and to demonstrate how to run it:

$ cat  < /dev/null > antivirus  # enter the code (none is needed)
$ chmod +x anitivirus  # make the program executable
$ ./antivirus  # run a complete system scan on EVERY disk

This scanner is zero bytes long. No other scanner can run faster, and none is more effective.

That’s because you don’t need an antivirus scanner with Linux.

All the necessary scanning was done by the eyeballs of the programmers who wrote Linux.

Isn’t it nice they saved we Linux users from having to wait … and wait … and wait.

Kenken Solver in Python

On February 13, 2009, the New York Times began publishing two kenken puzzles every weekday. See KENKEN® Puzzles , and A New Puzzle Challenges Math Skills.

I solved the first puzzle in short order, and found it fun.

Even more fun was the realization that writing a solver for kenken in Python would also be fun, and once I had done that I concluded that this could serve as a starting program for a new project of mine, how to teach programming in Python to students in k12. I’ll be writing about that project in a forthcoming post.

Puzzles are described in a simple text format. You can read the code to figure out the encoding. Here is the first 4×4 puzzle published in the New York Times:

first 4x4 puzzle from NY Times, published on Friday 02/13/09
4
8 * 0 0 rr
1 - 0 3 d
3 - 1 0 d
3 = 1 1
7 + 1 2 dl
2 / 2 3 d
1 - 3 0 r
1 = 3 2

Below you can find a simple kenken solver written in python. It reads the puzzle definition from standard input:

# Copyright (C) 2009, David Shields
# Licensed under "License Dave Shields for Software" available at https://daveshields.wordpress.com/about/#license
#

# v1 is with puzzle definition in the program
# v2 is with puzzle definition read from standard input, with cage as list of cells
# v3 is with puzzle read from standard input, with each cage represented by line and set of moves
# v4 fixes a bug in multiply()
# v5 uses prettyprint to format output
# v5 adds special handling for triples

# A puzzle is represented by a list [title-string, puzzle-size, cage-list]
# where
#   title-string is a string identifying the puzzle
#   puzzle-size is an integer giving the number of rows (and also columns)
#   cage-list is a list of cages

# A cage is a list (result-value, operator, cell-list)
# where
#   result-value is the value of the operator applied to the values in the cells in the cell-list
#   operator is a string, one of '+', '-', '*', '/' and '='
#   cell-list is a list of cells

# A cell is a list (row, column)
#   By convention, the first cell in the cell-list is the topmost, leftmost cell, but this is not required.
#
# An assignment is a list of cages and assignments of values for the cells in each cage: [cage, values]
#

# A solution is a list of assignments to cages that satisfies the non-duplication requirement

import copy
import pprint
import string
import sys

def add(size, cage):
    # ways to get result res with puzzle size size and length length
    # if length is two and since must add at least one, then just look at values less than result
    result, operator, cells = cage
    length = len(cells)
    r = []
    if result == 0:
        return r
    if length < 2:
        return r
    if length == 2:
        for i in range(size):
            n = i+1
            if result - n <= size:
                r.append(&#91;n, result - n&#93;)
#                if result -n != n: # append complentary choice if it is different
#                    r.append(&#91;result - n, n&#93;)
    else:
        # try all the possibilities for first cell, and then look for alternatives in the remaining cells
        for i in range(size-1):
            n = i+1
            tail = &#91;result - n, '+', cells&#91;1:&#93;&#93;
            others = add(size, tail)
            t = &#91;n&#93;
            for o in others:
                 r.append(&#91;n&#93; + o)
    if length == 3: # remove obvious incorrect possibilities
        trim3(cage, r)
    return r

def adjacent(cell0, cell1):
    r0, c0 = cell0
    r1, c1 = cell1
    if r0 == r1 or c0 == c1: return True
    return False
    
def choices(puzzle):
    title,size,cages = puzzle
    res = &#91;&#93;
    for cage in cages:
        result, operator, cells = cage
        length = len(cells)
        if operator == '=':
            possible = &#91;&#91;result&#93;&#93;
        elif operator == '+':
            possible = add(size, cage)
        elif operator == '-':
            possible = subtract(size, cage)
        elif operator == '*':
            possible = multiply(size, cage)
        elif operator == '/':
            possible = divide(size, cage)
        else:
            print "error, unknown operator",operator
        if possible == None or len(possible) == 0:
            print "no solution for cage ", result, operator, cells
            print " ", 1 / 0
        res.append(possible)
    return res


def classify(cells): #classify triple, returning center
    if len(cells) != 3: return None
    cell0, cell1, cell2 = cells
    if adjacent(cell0, cell1) and adjacent(cell0, cell2): return 0
    if adjacent(cell1, cell0) and adjacent(cell1, cell2): return 1
    if adjacent(cell2, cell0) and adjacent(cell2, cell1): return 2
    return &#91;&#93;
    
def divide(size, cage):
    result = cage&#91;0&#93;
    r = &#91;&#93;
    if result > size:
        print "error, impossible division", result,size
    else:

        for i in range(size):
            n = i + 1
            if n * result <= size:
                r.append(&#91;n, n*result&#93;)
                r.append(&#91;n*result, n&#93;)
    return r
    
def multiply(size, cage):
#   ways to get -result- by multiplying -length- numbers for puzzle of given -size-
    r = &#91;&#93;
    result, operator, cells = cage
    length = len(cells)
    if result == 1:
        # here if want result of 1, so add appropriate number of 1's
        t = &#91;&#93;
        for i in range(length):
            t.append(1)
        r.append(t)
        return r
    if length == 2:
        for i in range(size):
            n = i + 1 # trial divisor
            (quot, rem) =  divmod(result, n)
            if rem == 0:
                if quot <= size:
                    r.append(&#91;quot, result // quot&#93;)
        return r;
    # here if more than two numbers
    for i in range(result):
        n = i+1
        if n == 1: continue # have already dealt with this case
        if n > size: break # if too big
        (quot,rem) = divmod(result, n)
        if rem: continue # not a divisor
        # have possible choice for first
        now = [quot, size, cage[1:]]
        others = multiply(size, now)
        for o in others:
            t = [n]
            t.extend(o)
            r.append(t)
    if len == 3: # remove obvious incorrect possibilities
        trim3(cage, r)
    return r

def printsolution(puzzle, solution): #choices, guess):
# solution is list of form [row,col, value]
    title, size, cages = puzzle
    cells = [0] * (size * size)

    for s in range(len(solution)):
        row, col, value  = solution[s]
        cells[col*size + row] = value
    for row in range(size):
        for col in range(size):
            print " ", cells[col*size + row], " ",
        print ""
        
def readpuzzle():
# read puzzle from standard input
    text  = ""
    lines =  sys.stdin.readlines()
    cages = []
    nlines = 0
    for line in lines:
        words = line.split() # break line into words separated by whitespace
        if len(words) == 0:
            continue # ignore blank line
        nlines += 1
        cage =  []
#        print "nlines, line", nlines, line
        if nlines==1:
            title =  line
        elif nlines == 2:
            size = string.atoi(line)
        else:
            # new cage
            result = string.atoi(words[0])
            operator = words[1]
            row = string.atoi(words[2])
            col =  string.atoi(words[3])
            cells = [[row,col]]
            if len(words) > 4: # if have more than one cell
                moves = words[4]
                for m in moves:
                    if m == 'r':
                        col += 1
                    elif m == 'l':
                        col -= 1
                    elif m == 'd':
                        row += 1
                    elif m == 'u':
                        row -= 1
                    if [row,col] not in cells: # if new cell
                        cells = cells + [[row,col]]
            cages.append([result, operator, cells])
    return [title, size, cages]

def subtract(size, cage):
    result, operator, cells = cage
    r = []
    if result > size:
        pass
        # no, just look at multiples that match ...
    else:
        for i in range(size):
            v = i + 1
            if (v + result) <= size:
                r.append(&#91;v,v + result&#93;)
                r.append(&#91;v+result,v&#93;)
    return r

        
def solve(puzzle,choices):
    title, size,cages = puzzle
    ncages = len(cages)
    c = choices
    trials = 1
    trialset = &#91;&#93;
    for trial in range(len(c)):
        trialset.append(len(c&#91;trial&#93;))
        trials *= len(c&#91;trial&#93;)
    print "trials is", trials, " trial set", trialset
    # trials may be long so ...
    trial = 0
    while 1:
#    for trial in xrange(trials):
        if trial >= trials:
            break
        trial += 1
        t = trial
        if t % 10000 == 0:
            print t
        if t // 100000000:
            print "too many tries", t,
            break;
        solution = []
        guess = []
        nfound = 0
        for i in range(ncages):
            (t,g) = divmod(t, len(c[i]))
            guess.append(g)
        # now fill out solution for this guess
        solution = []
        # This is exhaustive search,
        # it would be better to check for duplicates on the fly
        for i in range(ncages):
            gi = guess[i]
            choicelist = c[i]
            choice = choicelist[gi]
            cage = cages[i]
            cells = cage[2]
            for ci in range(len(cells)):
                row,col = cells[ci]
                if ci<0 or ci >= len(choice):
                    print "choice index error", ci, trial
                try:
                    solution.append([row,col, choice[ci]])
                    nfound += 1
                except IndexError:
                    print "error ", row, col, ci, choice
                    raise ValueError
        if nfound != (size * size):
                    print "sizezzzz", nfound, size
        if verify(puzzle, solution):
            print "success:", guess
            print "took ", trial, " trials"
            printsolution(puzzle, solution)
            return guess
    print "no solution"

def trim3(cage, possibles):
    result, operator, cells = cage
    pivot = classify(cells)
    pi = 0
    for pin in possibles:
        p = copy.copy(pin)
        pvalue = p[pivot]
        del p[pivot]
        other1,other2 = p
        if pivot == other1 or pivot == other2: # if cannot be solution
            del possibles[pi]
        pi += 1
    
        
def verify(puzzle, solution): #choices, guess):
# solution is list of form [row,col, value]
    title,size, cages = puzzle
    if len(solution) != (size * size):
        print "solution,len error", len(solution), size
    cells = [0] * (size * size)

    rows = [[]] * size
    cols = [[]] * size
    for s in range(len(solution)):
        row, col, v  = solution[s]
        if row in rows[v-1]:
            return 0; # value already used, so cannot verify
        if col in cols[v-1]:
            return 0; # value already used, so cannot verify
        rows[v-1] = rows[v-1] + [row]
        cols[v-1] = cols[v-1] + [col]

    return 1 # found match!
                # set up possible assignments


puzzle = readpuzzle()
pprint.pprint(puzzle)
c =  choices(puzzle)
print "choices"
pprint.pprint(c)
solve(puzzle, c)

Happy hacking 🙂

On “Farewell World” and Programming

I have written several posts about the most ubiquitous of computer programs, “Hello World.” See “Hello World” through the ages, “Hello World” and programming, “Hello World” and Twit-messaging, and Dave Shields HELLO Tom Friedman.

As you will learn in my next post, today is a day both of farewell and of starting a new phase in my life, which got me to thinking if there was such a thing as a “Farewell World” program.

One obvious instance is the Blue Screen of Death, familiar to countless users of Windows. It’s the signal that Windows has wandered into a rathole of Microsoft’s own devising, and has found no way to escape.

Though it doesn’t involve a Blue Screen, I heard of another example of “Farewell World” from Microsoft last week. I was on a call with a colleague, and he said he was going to tie into another colleague so we could have a conference call. He came back a few minutes later saying that he been unable to reach the other person. When I spoke with the missing party later that day I learned that he had just bought a new cell phone. Though he had thought of getting one that ran Linux (that they exist is an example of Linux’s every growing march into the embedded space) he wound up buying one from Sprint since it didn’t cost that much, even though it ran Windows Mobile Edition.

He said his phone had rung earlier in the day, and knew the call came from our colleague, but that when he tried to answer the call the cell phone hung!

I can think of two “Fareworld World” programs from the land of Unix and Linux.

Back in the early 80’s, during my years on the SETL Project, we had the pleasure of the company of Lambert Meetens. He had been an active colleague of Robert B. K. Dewar back in the days of Algol 68, and Robert invited Lambert to spend a year with us at the Courant Institute at NYU.

Though I know it was great to have him around, and I know he did good work, I recall only two specific things about his visit.

First, Lambert had his own “Farewell World” experience. I learned from a colleague that Lambert had spent several months doing all his work on a Unix box. Realizing that the machine might crash and his work might be lost, he decided to save all his files on tape use the Unix “tar” (tape archive) program.

So he mounted the tape, planning to type the command “tar cfv …” to create the archive.

Thing is, if you look at your keyboard you will see that the “c” that stands for “create” is right next to the “x” that represents the “extract” option of tar, the inverse of save. His finger landed on the wrong key and thus his directory was over-written with the files on the tape. Six month’s of work lost.

This is an example of hideous design, using two adjacent keys to represent such opposed function.

The greatest impact of his visit came on his return to CWI in Amsterdam, where he and some colleagues created a programming language to teach basic programming principles. They called it ABC. The wikipedia entry says in part” ABC also had a major influence on the design of the Python programming language; Guido van Rossum, who developed Python, previously worked for several years on the ABC system in the early 1980s.”

Though SETL never wide achieved wide usage, it’s spirit has lived on in Python, which is why Python is my favorite programming language.

A second example of “Farewell World” is the Morris Worm, in which a small program meant to “gauge the size of the internet” happened to have a bug that brought the Internet to its knees.

Happy Birthday to The Wayward Word Press

I posted the first entry in this blog exactly three years ago today: Letter to Robert J Stevens, CEO, Lockheed Martin.

I resumed active blogging in September 2006, and especially in the last months of 2007. A list can be found at My Posts.

Aside from my delicious links, my last entry before this one was in January 2008: On the death of the client/server computer model.

And somehow, for reasons that I don’t really know, or worry about, I lost the yen to blog. It wasn’t that anything had gone wrong. It’s just that I lost the inclination. It wasn’t fun any more.

My guiding rule in open-source work is simple: If you aren’t having fun doing open-source then something is wrong. Stop and fix it before continuing.

So I stopped. I didn’t know how long it would last. I did know I would just wait until it came time to resume.

And so it has …

Hello again,world!

Blogger Dave is back.