Daily Archives: February 28, 2009

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 🙂

  • Pages

  • February 2009
    M T W T F S S
     1
    2345678
    9101112131415
    16171819202122
    232425262728  
  • RSS The Wayward Word Press

  • Recent Comments

    daveshields on SPITBOL for OSX is now av…
    Russ Urquhart on SPITBOL for OSX is now av…
    Sahana’s Respo… on A brief history of Sahana by S…
    Sahana’s Respo… on A brief history of Sahana by S…
    James Murray on On being the maintainer, sole…
  • Archives

  • Blog Stats

  • Top Posts

  • Top Rated

  • Recent Posts

  • Archives

  • Top Rated