Python sudoku

# Lars.Rasmusson@gmail.com 2011-12-18
class sudoku(dict):
    def __init__(self,game):
        game = [g for g in game if g in ".123456789"]
        for r in range(1,10):
            for c in range(1,10):
                self[(r,c)] = set(range(1,10)) if game[0] == '.' \
                              else set([int(game[0])])
                game = game[1:]
    def row(self, r): return [(r,c) for c in range(1,10)]
    def col(self, c): return [(r,c) for r in range(1,10)]
    def field(self, f):
        fs = []
        for x in range(1,10):
            r = (x - 1) // 3 + 3 * ((f - 1) // 3) + 1
            c = (x - 1) % 3 + 3 * ((f - 1) % 3) + 1
            fs.append((r,c))
        return fs
    def different(self, vars, n):
        from itertools import combinations
        modified = False
        for vs in combinations(vars, n):
            u = set().union(*[self[x] for x in vs])
            o = set().union(*[self[x] for x in vars if not x in vs])
            if len(u) == n and o.intersection(u) != set():
                for v in set(vars)-set(vs):
                    if self[v].intersection(u):
                        self[v] -= u
                modified = True
        return modified
    def solve(self):
        n = 1
        while n < 9:
            mod = False
            for i in range(1,10):
                mod |= self.different(self.row(i),n)
                mod |= self.different(self.col(i),n)
                mod |= self.different(self.field(i),n)
            n = 1 if mod else n + 1
    def write(self):
        for r in range(1,10):
            for c in range(1,10):
                v = self[(r,c)]
                print '.' if len(v) > 1 else list(v)[0],
            print
    def backtrack(self):
        from copy import deepcopy
        self.solve()
        choices = [len(self[var]) for var in self]
        if min(choices) < 1: return None
        if max(choices) == 1: return self
        var = [var for var in self if len(self[var]) > 1][0]
        for val in self[var]:
            s = deepcopy(self)
            s[var] = set([val])
            s = s.backtrack()
            if s != None: return s
        return None
    def check(self):
        for i in range(1,10):
            s1 = set().union(*[self[v] for v in self.row(i)])
            s2 = set().union(*[self[v] for v in self.col(i)])
            s3 = set().union(*[self[v] for v in self.field(i)])
            if not s1 == s2 == s3 == set(range(1,10)):
                return False
        return True

games = ["""
798 ... 2..
... 69. .73
.6. 27. 1..

6.. 94. .81
4.5 .61 .2.
9.2 8.. .3.

2.7 ... 4..
1.. 4.3 76.
..6 .19 .5.
"""
,
"""
... .4. ...
..5 ... .46
..7 ... ..5
.5. 3.. 2..
23. ... 97.
7.. 8.. ...
.9. .8. 3..
... .24 ...
12. .3. .8.
"""
,

"""
5.. 17. .39
..7 9.. ...
.1. ... 4..

... 8.2 7..
3.8 ... 6.2
..5 4.6 ...

..2 ... .5.
... ..5 9..
15. .29 ..7
"""
,
"""
.2. ..6 ..3
.7. 95. ...
..8 ... ...

..5 ... ...
... 248 .1.
.6. ..3 ..2

39. ... ...
... 1.. 79.
... ... 1..

"""
,
"""
... 76. .5.
..2 ... .9.
... .5. 7..

..4 ..1 ...
.3. ..8 57.
... 2.. 6..

42. .3. ...
7.. 8.. ...
... ... ..1

"""
,
"""
.6. .4. ...
8.. ... ..9
..7 ... 15.

... ..8 ...
..3 .9. 7.4
... ... .6.

.1. 6.. ..3
9.. 1.. 8..
62. ..5 ...
"""
,
"""
5.1 ..8 ...
... .4. .3.
... ... 15.

.6. 49. ...
... 6.. 9.7
..3 1.. ...

... ... .42
.4. 8.7 ...
.27 ... .6.
"""

,
"""

. . 2 | 4 . . | . 8 9
. 4 . | . . 8 | 2 7 .
. . . | . . 6 | . . 4
------|-------|------
. 7 . | 9 . . | . . .
. . . | . . . | . . .
3 . 8 | 5 . . | . . .
------|-------|------
. 9 7 | 3 . 1 | . 6 5
. 8 . | 7 2 . | . . .
4 . . | . . . | . . 8
""",

"""
. 4 3 | 9 8 . | 2 5 . 
6 . . | 4 2 5 | . . . 
2 . . | . . 1 | . 9 4 
------|--------|------ 
9 . . | . . 4 | . 7 . 
3 . . | 6 . 8 | . . . 
4 1 . | 2 . 9 | . . 3 
------|--------|------ 
8 2 . | 5 . . | . . . 
. . . | . 4 . | . . 5 
5 3 4 | 8 9 . | 7 1 . 
"""
,
"""
1..4....8
...89.5..
.2...5...
..8....37
.9..5..2.
36....1..
...1...7.
..6.48...
9....3..4
"""
,
"""
.6. .4. ...
8.. ... ..9
..7 ... 15.

... ..8 ...
..3 .9. 7.4
... ... .6.

.1. 6.. ..3
9.. 1.. 8..
62. ..5 ...
"""
]

if __name__ == "__main__":
    for game in games:
        s = sudoku(game)
        s.write()
        # s.solve()
        s = s.backtrack()
        if s:
            if s.check():
                s.write()
            else:
                print "FAILED CHECK!"
        else:
            print None
        print

Verisign S/MIME certificate for Mac

I ordered a certificate from verisign
"Digital ID for Secure Email"

I did it via Firefox

I filled in name and credit card info
and clicked accept.

A popup asked which key to use and I chose "Software device"
or something like that. I clicked a couple of times.

Then I got an email from verisign telling me
how to retrieve the certificate.

When I retrieved it, I got a webpage called sophia.exe
which contained some certificate and some HTML.
I stripped out the certificate and tried to import it
into Apples "Keychain Access", but I don't think it worked.

Eventually I went back to the Verisign site and went to
Support, and then to "Digital IDs for Secure Email Support"

Then I clicked on Retrieve to try to get the certificate
again. It said I had to use the same browser as before,
which I did, and this time it said everything went ok.

I went into Preferences, Advanced, Encryption, View Certificates,
clicked on my certificate and made a "backup" of it.
That created a pkcs12 file (.p12) which I was able to
import into Keychain Access.

Set ipv6 default route

I have a box that sends out radvd announcements on a lan, but something on the lan makes the other machines forget the advertisement about the default gateway after a while. They remember their ipv6 address, but cannot connect outside the lan anymore.

Before I used to log in to the machine with radvd and restart it so that it sends out fresh advertisements, but I'm now trying to explicitly add the default route with

read -p host: m;
ssh -t ${m:?} sudo ip -6 route add default via fe80::2b0:d0ff:febe:5fd7 dev eth0

Let's see how that goes...

Building bochs

The required libraries must be installed somewhere,
I let MacPorts build and install bochs to get
the libraries installed into /opt/local

Download bochs from svn in SRC, configure and make:

cd $SRC

CFLAGS="-I/opt/local/include -arch i386" \
CXXFLAGS="-L/opt/local/lib -arch i386" \
LDFLAGS="-L/opt/local/lib -arch i386" \
./configure \
--exec-prefix=/opt/local \
--bindir=/opt/local/bin \
--mandir=/opt/local/share/man \
--enable-all-optimizations \
--enable-cdrom \
--with-vbe \
--without-x \
--with-sdl

make -j8

Make a HD image

./bximage -q -hd -mode=sparse -size=1024 $SRC/c.img

./bochs

Configure hard disks, cdrom, bios files and boot order to boot from cdrom.
Use these files

$SRC/c.img
~/Downloads/ubuntu-10.04.2-server-i386.iso

$SRC/bios/BIOS-bochs-latest
$SRC/bios/VGABIOS-lgpl-latest


To make it faster, change the default ips from 50000000 to 4000000
cpu: count=1, ips=4000000, ....

Using a pure python disassembler for x86_64 machine code

Get some machine code, for instance with otool -t /bin/ls | head

$ otool -t /bin/ls | head
/bin/ls:
(__TEXT,__text) section
0000000100001478 6a 00 48 89 e5 48 83 e4 f0 48 8b 7d 08 48 8d 75 
0000000100001488 10 89 fa 83 c2 01 c1 e2 03 48 01 f2 48 89 d1 eb 
0000000100001498 04 48 83 c1 08 48 83 39 00 75 f6 48 83 c1 08 e8 
00000001000014a8 58 0f 00 00 89 c7 e8 1b 39 00 00 f4 55 48 89 e5 
00000001000014b8 48 8d 47 68 48 8d 7e 68 48 89 c6 c9 e9 01 3a 00 
00000001000014c8 00 55 48 89 e5 48 83 c6 68 48 83 c7 68 c9 e9 ef 
00000001000014d8 39 00 00 55 48 89 e5 53 48 89 f1 48 8b 56 60 48 
00000001000014e8 8b 47 60 48 8b 58 30 48 39 5a 30 7f 1d 7c 22 48

Get pymsasid from http://code.google.com/p/pymsasid/

$ wget http://pymsasid.googlecode.com/files/pymsasid-0.31.zip
$ unzip pymsasid-0.31.zip
$ cd pymsasid-0.3

Run it

$ python

import pymsasid
code = "6a 00 48 89 e5 48 83 e4 f0 48 8b 7d 08 48 8d 75 10"
p=pymsasid.Pymsasid(source=code,hook=pymsasid.HexstringHook,vendor=pymsasid.VENDOR_AMD)
p.dis_mode = 64
p.pc = 0x0000000100001478
for i in range(5): print p.decode()

will print

push 0x0 
mov rbp rsp 
and rsp 0xf0 
mov rdi [rbp+0x8] 
lea rsi [rbp+0x10]

IEEE Explore and KTH

To access IEEE Explore, etc., from my laptop:

* Connect to KTH OPEN on the wireless network, then,
change to use the KTH OPEN router to access the KTH Library


    # route change lib.kth.se 130.229.128.1
    # route change focus.lib.kth.se 130.229.128.1


Then go to lib.kth.se and look for IEEE Explore
or just go to http://focus.lib.kth.se

PYPI

I couldn't resist the title of this post :-)

def pi(digits=100):
    pi_digits=""
    SCALE = 10000
    ARRINIT = 2000
    carry = 0
    arr = [ARRINIT]*(digits+1)
    for i in range(digits, 0, -14):
        sum = 0
        for j in range(i-1,0,-1):
            sum = sum * j + SCALE * arr[j]
            arr[j] = sum % (j * 2 - 1)
            sum = sum / (j * 2 - 1)
        pi_digits += "%04d" % (carry + sum / SCALE)
        carry = sum % SCALE
    return pi_digits

bind9 dnssec

Example:

To configure bind9 so that you can sign the zone with
rndc sign sics6.se; rndc freeze; rndc unfreeze;


in /etc/bind/named.conf.options:


options {
directory "/var/cache/bind";
key-directory "/etc/bind/dnssec";

...

};

in /etc/bind/named.conf.local:


include "/etc/bind/keys.conf";
include "/etc/bind/rndc.key";



controls {
      inet 127.0.0.1 port 953
              allow { 127.0.0.1; } keys { "rndc-key"; };
};



...



zone "sics6.se." IN {
        type master;
        file "/etc/bind/zones/sics6.se..signed";
        allow-update { key lra.sics.se.; };
        auto-dnssec allow;
};

Python virtualenv

Virtualenv http://pypi.python.org/pypi/virtualenv is very useful.  It creates a new file environment into which you can install python software without screwing up your already installed system python.

To create a virtual environment, if you already have  virtualenv installed, do

• python -m virtualenv myEnv

otherwise,

• download virtualenv-1.5.1.tar.gz
• unpack it: tar xfz virtualenv-*-gz
• create the environment:  python virtualenv-1.5.1/virtualenv.py myEnv
• once the environment (myEnv) has been created,  you can remove the virtualenv-1.5.1 directory.

Example:

curl -s http://pypi.python.org/packages/source/v/virtualenv/virtualenv-1.5.1.tar.gz | tar zxvf -

python virtualenv-1.5.1/virtualenv.py myEnv

Now you can use myEnv/bin/python or myEnv/bin/pip to install packages

(pip can download and install python packages very neatly).

wget and ssl certificates

To use certificates with wget, first get the root cerificate for the site.

1. Just have one certificate

You can either go to the site with Firefox, click on the little lock in
the status bar, in the Security tab click View certificate, click on Details,
click on the topmost certificate in the “Certificate Hierarchy”, click on
“Export…” and save as “.pem”.

Now you can use ssl with wget like this:

wget --ca-certificate={the_cert_file}  https://www.google.com

2. A directory full of certificates

Or you can have an entire directory full of certificates that wget
can choose from. Useful if you want to use all the certificates
from the KeyChain.app.

If you export all the certificates from KeyChain.app in one go
(you can select multiple and export all at once), then you must
split up the file into individual files for each certificate, and
name the certificates by their hash and a “.0” at the end.

If the certificates from KeyChain.app are saved into the file
Certificates.pem, then this splits these commands splits the
files and renames them.

mkdir certdir
cd certdir

n=0 ; cat ../Certificates.pem | while read x; do if [ "$x" == "-----BEGIN CERTIFICATE-----" ]; then n=$((n+1)); fi; echo >>cert-$n.pem $x ; done

for f in cert-*; do n=$(openssl x509 -hash -in $f -noout); mv $f $n.0; done

cd ..

Now you can use ssl with wget like this:

wget --ca-directory=certdir  https://www.google.com

If you want to, you can put the certdir in your ~/.wgetrc file so you

won't have to specify it all the time.  Just put the line

ca_directory = {full path to certdir}
and you're done.

Actually, you also need some way to handle revocation of certificates.
But that's for another day.

Building WiiMC on a Mac OS X

WiiMC is a homebrew program for Wii.
These are my bash notes on how to downloads a devkitPPC environment, install some libraries needed, and to show where to patch a file to make it compile.

Here are the bash commands...   Use them with care...  :-)

 
export WIIROOT=$(pwd)
 
svn checkout http://wiimc.googlecode.com/svn/trunk/ wiimc-read-only
svn checkout http://libext2fs-wii.googlecode.com/svn/trunk/ libext2fs-wii-read-only
svn checkout http://grrlib.googlecode.com/svn/trunk/GRRLIB/lib/zlib
 
export WIIMCSRC=$WIIROOT/wiimc-read-only
 
 
mkdir -p $WIIROOT/devkitpro
export DEVKITPRO=$WIIROOT/devkitpro
 
echo THIS IS IMPORTANT
echo export DEVKITPPC=$DEVKITPRO/devkitPPC
echo export PATH=$DEVKITPPC/bin:$PATH
 
export DEVKITPPC=$DEVKITPRO/devkitPPC
export PATH=$DEVKITPPC/bin:$PATH
 
 
mkdir -p $WIIROOT/download
cd $WIIROOT/download
 
DEVKITURL=http://sourceforge.net/projects/devkitpro/files
 
(
wget -c ${DEVKITURL}/devkitPPC/devkitPPC_r22-osx.tar.bz2 &
wget -c ${DEVKITURL}/libogc/libogc-1.8.6.tar.bz2 &
wget -c ${DEVKITURL}/examples/wii/wii-examples-20100930.tar.bz2 &
wget -c ${DEVKITURL}/examples/gamecube/gamecube-examples-20100930.tar.bz2 &
wget -c ${DEVKITURL}/libfat/libfat-ogc-1.0.8.tar.bz2 &
 
# wget -c ${DEVKITURL}/portlibs/zlib-1.2.4-ppc.tar.bz2 &
wget -c ${DEVKITURL}/portlibs/mxml-2.6-ppc.tar.bz2 &
wget -c ${DEVKITURL}/portlibs/libpng-1.4.1-ppc.tar.bz2 &
wget -c ${DEVKITURL}/portlibs/jpeg8a-ppc.tar.bz2 &
wget -c ${DEVKITURL}/portlibs/freetype-2.4.2-ppc.tar.bz2 &
wait
)
 
diff <(md5 *bz2) <(cat << EOF
MD5 (devkitPPC_r22-osx.tar.bz2) = 385300a31c4c2cc6890adfb8f220674c
MD5 (freetype-2.4.2-ppc.tar.bz2) = 0e91ad37ead10137cc9f8d2f3454a245
MD5 (gamecube-examples-20100930.tar.bz2) = e9ef264a5c7acd6ef6144b676527bacd
MD5 (jpeg8a-ppc.tar.bz2) = ef4c03019ade885dbba05982e777ea2b
MD5 (libfat-ogc-1.0.8.tar.bz2) = 495cb164afa9ca420fd21d4c78c0723f
MD5 (libogc-1.8.6.tar.bz2) = 5be16c7c972e8c92e637220adb123be1
MD5 (libpng-1.4.1-ppc.tar.bz2) = 29a9a6c754d32990f542990d3d38e715
MD5 (mxml-2.6-ppc.tar.bz2) = b196036aa9f0b310efb6bdc4b02614dc
MD5 (wii-examples-20100930.tar.bz2) = 5a37fb6cc1704f43cb3813ddbb964a24
EOF) 
 
#MD5 (zlib-1.2.4-ppc.tar.bz2) = c952918d7fb3e52e8fa66fa09f2edf87
 
 
if [ ! $? ] ; then
    echo The checksums on the downloaded files were wrong.
    exit 1
fi
 
cd $WIIROOT/download
 
tar -C $DEVKITPRO -xjf devkitPPC_r22-osx.tar.bz2
 
mkdir $DEVKITPRO/libogc
tar -C $DEVKITPRO/libogc -xjf libogc-1.8.6.tar.bz2
tar -C $DEVKITPRO/libogc -xjf libfat-ogc-1.0.8.tar.bz2
 
mkdir -p $DEVKITPRO/examples/{wii,gamecube}
tar -C $DEVKITPRO/examples/wii  -jxf wii-examples-20100930.tar.bz2
tar -C $DEVKITPRO/examples/gamecube  -jxf gamecube-examples-20100930.tar.bz2
 
mkdir -p $DEVKITPRO/portlibs/ppc
#tar -C $DEVKITPRO/portlibs/ppc -xjf zlib-1.2.4-ppc.tar.bz2
tar -C $DEVKITPRO/portlibs/ppc -xjf mxml-2.6-ppc.tar.bz2
tar -C $DEVKITPRO/portlibs/ppc -xjf libpng-1.4.1-ppc.tar.bz2
tar -C $DEVKITPRO/portlibs/ppc -xjf jpeg8a-ppc.tar.bz2
tar -C $DEVKITPRO/portlibs/ppc -xjf freetype-2.4.2-ppc.tar.bz2
 
 
############################################
 
 
cd $WIIMCSRC/libs/libntfs
make
make install
 
# remember: the powerpc-eabi commands must be in the path 
# so that 'configure' can find them)
 
for lib in fribidi libexif pcre libiconv ; do
  echo Building $lib.  Press RETURN to start
  read
  cd $WIIMCSRC/libs/$lib
  ./configure --host=powerpc-eabi --prefix="${DEVKITPRO}/portlibs/ppc" --libdir="${DEVKITPRO}/portlibs/ppc/lib" --disable-shared
  make
  make install
done
 
cd $WIIROOT/libext2fs-wii-read-only
make
make install
 
 
#install zlib 1.2.5 instead of 1.2.4 which is what we got from the devkitpro site
cd $WIIROOT/zlib
make
make install
cp $DEVKITPRO/libogc/include/{zconf,zlib}.h $DEVKITPRO/portlibs/ppc/include
cp $DEVKITPRO/libogc/lib/wii/libz.a $DEVKITPRO/portlibs/ppc/lib/libz.a 
#sed -i -e 's/1\.2\.4/1\.2\.5/' $DEVKITPRO/portlibs/ppc/lib/pkgconfig/zlib.pc
 
 
# fix missing include file in wiimc.cpp
 
===================================================================
--- source/wiimc.cpp    (revision 802)
+++ source/wiimc.cpp    (working copy)
@@ -14,6 +14,7 @@
 #include <dirent.h>
 #include <wiiuse/wpad.h>
 #include <di/di.h>
+#include <sys/iosupport.h>
 
 #include "utils/FreeTypeGX.h"
 #include "utils/gettext.h"
 
 
 
cd $WIIMCSRC
make