August 25, 2014

Knight's tour in 8086 assembly (MASM)

Almost 20 years ago I wrote an assembly code to solve Knight’s tour problem as my C solution was too slow. The code was lost on a backup disk and I’ve accidentally found it over the weekend. If you have MASM you can make a binary and test it.

.8086
.MODEL TINY

        CR      EQU     0dh
        LF      EQU     0ah
        SPACE   EQU     20H

.DATA?
        table           dw      81 DUP (?)      ; Worst case of 9x9 board.
        table_end       dw      ?               ; Offset of the last element in
                                                ; the table.
        jump            dw      8 DUP (?)

                        ;       (2*N+1)*2  - 0
                        ;       (N+2)*2    - 1      7 0      COLUMN 
                        ;       (-N+2)*2   - 2     6   1            R
                        ;       (-2*N+1)*2 - 3       x              O
                        ;       (-2*N-1)*2 - 4     5   2            W
                        ;       (-N-2)*2   - 5      4 3             
                        ;       (N-2)*2    - 6
                        ;       (2*N-1)*2  - 7
                        ; jump   --     Movement from the current position as
                        ;               a function of the move type.

        N               dw      ?       ; Table size.
        NN              dw      ?       ; N*N
        N2              dw      ?       ; 2*N
        N_char          db      ?       ; N as ASCII.

;       Register usage:
;       SI - current field.
;       DI - next field.
;       BX - movement type.
;       DX - info on the current field:
;               DH - allowed moves
;               DL - how many moves are tried from this field.
;       AX - info on the next field:
;               AH - allowed moves
;               AL - how many moves are tried from this field.


.DATA
                        db      'Author '
        author          db      'http://www.aleksa.org'
        table_size      db      CR, LF, 'Table size [3..9] > $'
        x_pos           db      CR, LF, 'row > $'
        y_pos           db      CR, LF, 'column  > $'
        analyzing_board db      CR, LF, 'Analyzing the board...',CR,LF,'$'
        nosolution      db      CR, LF, 'No solution.$'


.STACK 1024


.CODE
        .STARTUP
        mov     ah, 09h
        mov     dx, offset author
        int     21h             ; Display 'Table size [3..9] > '
        mov     ah, 01h
        int     21h             ; DOS call to read a char to AL.
        cmp     al, '3'
        jb      error           ; Exit if not in [3, 9] range.
        cmp     al, '9'
        jbe     ok_N
error:  jmp     finish
ok_N:   mov     N_char, al
        and     ax, 000fh       ; ASCII number -> bin number.
        mov     N, ax

        shl     ax, 1
        mov     N2, ax          ; N2 <- N*2
        mov     ax, N
        mul     al
        mov     NN, ax          ; NN <- N*N

        mov     table_end, offset table
        dec     ax              ; AX <- N*N-1
        shl     ax, 1           ; Every table element is 2 bytes.
        add     table_end, ax   ; table_end has the offset of the last element
                                ; in the table.

;---    Moves initialization.

        mov     di, offset jump

        mov     ax, N2
        inc     ax
        shl     ax, 1           ; (2*N+1)*2
        mov     [di], ax        ; Move 0.
        neg     ax
        mov     [di+8], ax      ; Move 4.
        add     di, 2           ; Point to the next element in the move list.

        mov     ax, N
        add     ax, 2
        shl     ax, 1           ; (N+2)*2
        mov     [di], ax        ; Move 1.
        neg     ax
        mov     [di+8], ax      ; Move 5.
        add     di, 2           ; Point to the next element in the move list.

        mov     ax, N
        neg     ax
        add     ax, 2
        shl     ax, 1           ; (-N+2)*2
        mov     [di], ax        ; Move 2.
        neg     ax
        mov     [di+8], ax      ; Move 6.
        add     di, 2           ; Point to the next element in the move list.

        mov     ax, N2
        neg     ax
        inc     ax
        shl     ax, 1           ; (-2*N+1)*2
        mov     [di], ax        ; Move 3.
        neg     ax
        mov     [di+8], ax      ; Move 7.

;---    Board initialization, mark illegal moves.

        mov     di, offset table; DI points to the table start.
        push    di
        xor     ax, ax
        mov     cx, NN
        cld
rep     stosw                   ; Fill the table with 0s.
        pop     di              ; Start from the beginning.
        mov     ax, 3c00h       ; Illegal moves 2,3,4 and 5 for the first
        mov     cx, N           ; column.
rep     stosw
        mov     ax, 1800h       ; Illegal moves 3 and 4 for the second column.
        mov     cx, N
rep     stosw
        mov     di, table_end
        mov     ax, 0c300h      ; Illegal moves 0,1,6 and 7 for the last
        mov     cx, N           ; row.
        std
rep     stosw
        mov     ax, 8100h       ; Illegal moves 0 and 7 for the next to last
        mov     cx, N           ; column.
rep     stosw
        mov     di, offset table
        mov     ax, 0f00h       ; Illegal moves 4, 5, 6 and 7 for the first
        mov     cx, N           ; row.
lab1:   or      [di], ax
        add     di, N2
        loop    lab1
        mov     di, offset table+2
        mov     ax, 0600h       ; Illegal moves 5 and 6 for the second row.
        mov     cx, N
lab2:   or      [di], ax
        add     di, N2
        loop    lab2
        mov     di, table_end
        mov     ax, 0f000h      ; Illegal moves 0,1,2 and 3 for the last row.
        mov     cx, N
lab3:   or      [di], ax
        sub     di, N2
        loop    lab3
        mov     di, table_end
        sub     di, 2
        mov     ax, 6000h       ; Illegal moves 1 and 2 for the last row.
        mov     cx, N
lab4:   or      [di], ax
        sub     di, N2
        loop    lab4

;---    Set starting position - first column, then row.

        mov     ah, 09h         ; DOS call to display the message.
        mov     dx, offset x_pos
        int     21h             ; 'column >'
        mov     ah, 01h         ; DOS call to read a character into AL.
        int     21h
        cmp     al, '1'
        jb      lab5            ; Exit if not within bounds.
        cmp     al, N_char      ; Exit if greater than table size.
        ja      lab5
        mov     cl, al
        mov     ah, 09h         ; DOS call to display the message.
        mov     dx, offset y_pos
        int     21h             ; 'row  >'
        mov     ah, 01h
        int     21h             ; DOS call to read a char to AL.
        cmp     al, '1'
        jb      lab5
        cmp     al, N_char      ; Exit if greater than table size.
        jbe     ok              ; Looks good.
lab5:   jmp     finish          ; As finish is more than 128 bytes away.
ok:     mov     ch, al          ; CH - row, CL - column.
        mov     ah, 09h
        mov     dx, offset analyzing_board
        int     21h             ; 'Analyzing the board...'
        and     cx, 0f0fh       ; Convert from ASCII to a number.
        dec     cl              ; Subtract 1 to mark the right field.
        dec     ch

;---    Set SI to point to the starting field.

        mov     ax, N
        mul     ch              ; AL <- row*N
        xor     ch, ch
        add     ax, cx          ; AL <- row*N + column
        shl     ax, 1           ; and multiply everything by 2.
        mov     si, offset table
        add     si, ax          ; SI - now pointing to the starting position.
        xor     bx, bx          ; BX <- 0
        mov     dx, [si]        ; Put the info on the current field.
        mov     dl, 1           ; Fields visited so far.

;---    Start filling the board.

        mov     cx, NN          ; !!!
search: rol     dh, 1           ; Rotate left, MSB is in CF.
        jc      nomove          ; Illegal move.
        mov     di, si
        add     di, jump[bx]    ; DI has the address of the next field.
        mov     ax, [di]        ; Load it.
        test    al, al          ; Is it taken?
        jnz     nomove          ; Yes.
        mov     [si], dx        ; No, store the old field,
        push    si              ; 
        push    bx              ; and what was the last move from that field.
        mov     si, di          ; Move the pointer to the new field.
        mov     dh, ah          ; Illegal moves go to DH.
        inc     dl              ; Increment the visited fields number.
        xor     bx, bx          ; Start with move 0.
        cmp     dl, cl          ; Did you fill the board?
        jne     search          ; No.
        jmp     short print     ; Yes, print it.
nomove: add     bx, 2           ; Try the next move.
        cmp     bx, 16          ; Have you tried all moves?
        jb      search          ; No.
        cmp     dl, 1           ; Are you back to the starting position?
        je      sorry           ; Yes, then there is no solution.
        xor     dl, dl
        mov     [si], dx        ; Unmark the field.
        pop     bx              ; What was the last move?
        pop     si              ; Go back by one field.
        mov     dx, [si]
        jmp     short nomove

;--- Print the solution, but convert to ASCII first.

print : mov     [si], dx
        mov     si, offset table
        ; CS already has N*N !!!
lab7:   mov     ax, [si]
        aam
        or      ax, 3030h       ; Convert to ASCII
        mov     [si], ax
        add     si, 2
        loop    lab7
        mov     ah, 02h
        mov     dl, CR
        int     21h
        mov     dl, LF
        int     21h
        mov     si, offset table
        mov     cx, N
crt:    mov     dl, [si+1]
        cmp     dl, '0'
        jne     good
        mov     dl, SPACE
good:   int     21h
        mov     dl, [si]
        int     21h
        mov     dl, SPACE
        int     21h
        add     si, 2
        loop    crt
        mov     dl, CR
        int     21h
        mov     dl, LF
        int     21h
        cmp     si, table_end
        jg      finish
        mov     cx, N
        jmp     short crt
sorry:  mov     ah, 09h         ; Print that there is no solution.
        mov     dx, offset nosolution
        int     21h
finish: .EXIT 0

END

August 10, 2014

GoPacker

A year ago I was working on a server in Go that I wanted to be easy to deploy and move around. Go is great for providing you with one statically linked binary, but I also had few files that needed to be bundled with the code (CSS, JavaScript, images).

At that time I couldn't find a solution that would fit my needs so I wrote one: GoPacker. Hope you find this script useful.

March 7, 2013

Configure git to use a different tool for diffing

I don't like default git diff output: I prefer vimdiff or tkdiff. Here is a recipe that explains how to set up external diff.
Your basic ~/.gitconfig should have [diff] section as in:
[user]
        name = <your name>
        email = <your@email>
[color]
        status = auto
        diff = auto
        branch = auto
        interactive = auto
[core]
        editor = vim
        pager = less -FRSX
[diff]
        external = /home/<username>/bin/gittkdiff.sh
[merge]
        tool = vimdiff
Create external gittkdiff.sh and make it executable (chmod +x):
#!/bin/sh

/usr/bin/tkdiff "$2" "$5" | cat
For vimdiff use:
#!/bin/sh

/usr/bin/vimdiff "$2" "$5" | cat



[Update - 08/10/2014]

Newer git can do this for you:
git config --global diff.tool tkdiff
git config --global merge.tool tkdiff
git config --global --add difftool.prompt false

March 4, 2013

Replacing Python's positional arguments with keyword arguments

I was renaming a positional function argument named id (which was masking Python's built in function id()), but that broke the rest of the third party code. I've just discovered a very nasty language feature.

A function in Python that takes only positional arguments:

def foo(x, y):
    print x ** y

should be called as:

foo(23)

But when calling a function it is possible to use keyword arguments in place of the given positional arguments:

foo(2, y=3)
foo(x=2, y=3)

Whoever wrote foo() counts it will always be called with positional arguments, but there is no way to prevent someone to use keyword calling style (foo(2, y=3)). If foo() arguments are renamed, e.g. to make it more readable:

def foo(base, exponent):
    print base ** exponent

the code using it will stop working:

>>> foo(x=2, y=3)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: foo() got an unexpected keyword argument 'x'

Positional function arguments should be and stay local, but that is not the case in Python. One could blame the programmer, but language should be able to prevent this problem. Never use keyword argument for a function that doesn't explicitly define one. This is a very nasty way to introduce bugs in otherwise very clean and safe code.

It goes the other way around: a function with keyword arguments can be called as if it was defined with positional arguments:

def hi(name="Nobody"):
    print "Hi {}!".format(name)

Usage:

>>> hi(name="Aleksa")
Hi Aleksa!
>>> hi("Aleksa")
Hi Aleksa!

I'd prefer to see an error here, but it "does the right thing" in a Perl like fashion. Keyword to positional argument replacement is going to make your code less readable, but will not break it as when replacing positional for named arguments.

Python 3 changed things a bit, but didn't fix the problem. Having * between positional and keyword arguments ensures that keyword arguments are properly used:

def foo(x, *, y=None):
    print("X: {}".format(x), end="\n")
    print("Y: {}".format(y), end="\n")
>>> foo(1, 2)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: foo() takes 1 positional argument but 2 were given
>>> foo(1, y=2)
X: 1
Y: 2

However, positional arguments can still be replaced with keyword arguments:

>>> foo(x=1, y=2)
X: 1
Y: 2

Every function argument in Python is a hybrid global variable!

March 2, 2013

Python friendly .vimrc

syn on
let python_highlight_builtins=1
au FileType python setlocal expandtab shiftwidth=4 softtabstop=4 colorcolumn=80 ai nu nowrap cul

let python_highlight_builtins=1 enables coloring of reserved and built in functions in Python. It is going to make you aware when a variable name overrides a built in function (e.g. id or type). For details on other specific parameters see Python's wiki page on vim and "Secrets of tabs in vim."

To enable folding add:

set foldmethod=indent

and you can open a fold with zo, close with zc, close all in the document with zM or open with zR.

To emulate PyCharm's variables highlighting under the cursor try this command:

:autocmd CursorMoved * exe printf('match Search /\V\<%s\>/'escape(expand('<cword>')'/\'))

March 1, 2013

Python resources

Useful material for mastering and using Python in the industry.

Books

Web Material

Development Tools

Videos

Useful Libraries

  • python-gflags — Google command line flag is intended to be used in situations where a project wants to mimic the command-line flag handling of a C++ app that uses google-gflags, or for a Python app that, via swig or some other means, is linked with a C++ app that uses google-gflags.

  • gevent for the Working Python Developer — The structure of this tutorial assumes an intermediate level knowledge of Python but not much else. No knowledge of concurrency is expected. The goal is to give you the tools you need to get going with gevent, help you tame your existing concurrency problems and start writing asynchronous applications today.

  • pymox — A mock object framework for Python. Mox is based on EasyMock, a Java mock object framework.

  • Django — A high-level Python Web framework that encourages rapid development and clean, pragmatic design.

  • matplotlib — A 2D plotting library which produces publication quality figures in a variety of hardcopy formats and interactive environments across platforms.

  • pydot — Allows to easily create both directed and non directed graphs from Python. You'd need to install GraphViz as well.

  • Gnuplot.py — A Python package that interfaces to gnuplot, the popular open-source plotting program. It allows you to use gnuplot from within Python to plot arrays of data from memory, data files, or mathematical functions.

  • SWIG — A software development tool that connects programs written in C and C++ with a variety of high-level programming languages. SWIG is used with different types of target languages including common scripting languages such as Perl, PHP, Python, Tcl and Ruby. Check out this tutorial that shows you how to interface with Python.

  • SciPy — An open-source software for mathematics, science, and engineering. The SciPy library depends on NumPy, which provides convenient and fast N-dimensional array manipulation.

Related Resources

  • HTTP status codes cheat sheet — You will need this for web programming.

  • Graphical vi-vim Cheat Sheet and Tutorial — I found vim to be good for editing Python, mainly because it can do copy-paste with proper indent adjustment (pasting with ]p instead of p).

  • git — Distributed version control system designed to handle everything from small to very large projects with speed and efficiency.