The shortest oneline brainf*ck interpreter in python (558 characters)

Hi, it is Dr. NISHIO Hirokazu. This code was written in 2006-09 but I didn't have publish yet in English.

get from here: http://gist.github.com/476940. It takes a filename as an argument and exec it as Brainf*ck code. All illegal characters are ignored.

exec(reduce(lambda x,y:x.replace(y[0],y[1:]),'Iz"d",|Jz"t",|K1),"|L.read(|Mimport |O,lambda|Psys.std|Q",0);z"|R"Yzp,|S}.get(code[|T)or |U"YZor z"p",p|Vifilter(bool,(|W)%256)or Z,"|X)for x in count())).next()|Y:lambda:|Zz"c",c+1)|q(globals().get(p,0)|zglobals().__setitem__('.split('|'),'Msys;from itertools Mcount,ifilter;z"cQpQj"O kYq==0)^(k==-1)and(Jc+kTI1TVId+{"]":-1,"[":1St],0)*kTd==0 or Jt+kXand z"c",t+1T1TZ);z"code",file(sys.argv[1])L));Vc==len(code)or({">U+K<U-K+Rq+1W-Rq+255W."YPout.write(chrq)TZ,",Rord(PinL1)W[":j(K]":j(-1),Sc]O:Z)()and NoneX'))

See this charm point!

>U+K<U-K+Rq+1W-Rq+255W

It's a definition of >, <, + and - !

What happen if you put both str and unicode key on a dict in Python?

In [1]: {u"a": 1, "a": 2}
Out[1]: {u'a': 2}

Yas, it is because:

In [2]: u"a" == "a"
Out[2]: True

Python2.* think u"a" and "a" are EQUAL. of course:

In [3]: u"a" is "a"
Out[3]: False

they are not IDENTITY. If Guido designed to use IDENTITY to check whether they are SAME key, it causes:

In [4]: (1, 2) is (1, 2)
Out[4]: False

that uncomfortable behavior. We don't want to distinguish EQUAL tuples. It is a difficult question on designing new languages. Those behavior was changed from Python3.0. On it, bytes(byte sequence) and text(unicode char sequence) are not compatible. No automatic conversion between them.

>>> b"a" == "a"
False
>>> {b"a": 1, "a": 2}
{b'a': 1, 'a': 2}

Re: Python vs Clojure

Hi, it is NISHIO Hirokazu, a Python hacker.

In Python vs Clojure – Evolving « Best in Class I found a code:



What a mess!

Why you need icross. In Clojure it was written as (for [x (range 100 1000) y (range 100 1000)] (* x y)). It can be written (x * y for x in range(100, 1000) for y in range(100, 1000)) in Python too!

Why you need digits_from_num. In Clojure it was written as (= (seq s) (reverse s)). It can be written list(s) == list(reversed(s)) in Python too!!

And Why you need mul. In Clojure it was (* x y). Why you need new multiply function which takes arbitrary number of arguments?? Why didn't you write just (x * y)?

Finally, I concluded the messy python code is equivalent to the below:

print max(s for s in (x * y 
                      for x in range(111, 1000) 
                      for y in range(y, 1000))
          if list(str(s)) == list(reversed(str(s))))

It is shorter than Clojure.

---

P.S. matz reported the original version of Python code takes 12.2 seconds, my version takes 4.9 seconds (both on Python2.6). And his ruby code (see first post) takes only 2.8 seconds on Ruby1.8.7 and 0.9 seconds on Ruby1.9.

http://twitter.com/yukihiro_matz/status/4901341641
http://twitter.com/yukihiro_matz/status/4901791131
http://twitter.com/yukihiro_matz/status/4901849726

How to calculate Bezier curves' bounding box

Hi, it is NISHIO Hirokazu. Today I wanted to make a lot of Bezier curves same size. And I got it.

Here is what I want to draw:


To calculate bounding box of cubic Bezier seems easy, especially you know its parametric form. See Bézier curve - Wikipedia, the free encyclopedia

However, there are some pitfall. The derivative of Bezier equation is usually quadratic equation but not always. Solutions of the derivative may out of range, etc.

I publish following source code under MIT License. Feel free to use it.

def calc_box(start, curves):
    P0 = start
    bounds = [[P0[0]], [P0[1]]]

    for c in curves:
        P1, P2, P3 = (
            (c[0], c[1]), 
            (c[2], c[3]), 
            (c[4], c[5]))

        bounds[0].append(P3[0])
        bounds[1].append(P3[1])

        for i in [0, 1]:
            f = lambda t: (
                (1-t)**3 * P0[i] 
                + 3 * (1-t)**2 * t * P1[i] 
                + 3 * (1-t) * t**2 * P2[i]
                + t**3 * P3[i])

            b = 6 * P0[i] - 12 * P1[i] + 6 * P2[i]
            a = -3 * P0[i] + 9 * P1[i] - 9 * P2[i] + 3 * P3[i]
            c = 3 * P1[i] - 3 * P0[i]

            if a == 0:
                if b == 0:
                    continue
                t = -c / b
                if 0 < t < 1: 
                    bounds[i].append(f(t))
                continue

            b2ac = b ** 2 - 4 * c * a
            if b2ac < 0: 
                continue
            t1 = (-b + sqrt(b2ac))/(2 * a)
            if 0 < t1 < 1: bounds[i].append(f(t1))
            t2 = (-b - sqrt(b2ac))/(2 * a)
            if 0 < t2 < 1: bounds[i].append(f(t2))

        P0 = P3

    x = min(bounds[0])
    w = max(bounds[0]) - x
    y = min(bounds[1])
    h = max(bounds[1]) - y
    return (x, y, w, h)

---

Blaze Boy asked me about the structure, thank you. for each c in curves is 6-tuples: P1, P2, P3 = ((c[0], c[1]), (c[2], c[3]), (c[4], c[5])) P0 and P3 are terminal points of each bezier curves.

Ruby's Struct v.s. Python's namedtuple

Hi, it is NISHIO Hirokazu. 9 years ago I met to Ruby's Struct. It is nice.

irb(main):018:0> FooBar = Struct.new(:foo, :bar)
=> FooBar
irb(main):019:0> FooBar.new(1, 2)
=> #<struct FooBar foo=1, bar=2>
irb(main):020:0> _.foo
=> 1

So I wrote its Python version.

>>> def Struct(*keys):
 class _Struct(object):
     def __init__(self, *values):
  self.__dict__.update(zip(keys, values))
 return _Struct

 
>>> Struct("foo", "bar")
<class '__main__._Struct'>
>>> FooBar = Struct("foo", "bar")
>>> FooBar(1, 2)
<__main__._Struct object at 0x01494E90>
>>> _.foo
1

Today I regret to inform the code is obsolete. In python2.6 we can use collections.namedtuple:

>>> from collections import namedtuple
>>> namedtuple("MyClass", "foo bar")
<class '__main__.MyClass'>
>>> _(1, 2)
MyClass(foo=1, bar=2)
>>> _.foo
1

[Python] To raise exception doesn't take extra overhead on call

Hi, it is NISHIO Hirokazu. Today I'll write about Python tips. My friend said "Does a function which raise exceptions take extra overhead on call?" on Twitter. I don't think so, but I wrote a code:

import timeit

print timeit.Timer("foo(1)", setup="""
def foo(x):
    if x:
        return None
    else:
        return x
""").repeat()

print timeit.Timer("bar(1)", setup="""
def bar(x):
    if x:
        return None
    else:
        raise NotImplementedError
""").repeat()

The formar function doesn't raise any exceptions. The latter does. The timeit module measures time to run given code 1000000 times, and repeat it 3 times. The result is below:

[0.24111700057983398, 0.22863888740539551, 0.22955012321472168]
[0.23151803016662598, 0.23359298706054688, 0.2297508716583252]

I concluded there is no extra overhead between them.

[Python]Draw a fractal pattern(Julia set)

I wrote a program to draw a fractal pattern.
Julia set - Wikipedia, the free encyclopedia.
I found it is very easy to implement; it took much time to check the mathematical definition of Julia set than to implement. If you already know Python and don't know Python Imaging Library (PIL) yet, I strongly recommend to learn it!



Using PIL you can generate images like above from very simple code:

import Image
import ImageDraw

SIZE = 128
image = Image.new("L", (SIZE, SIZE))
d = ImageDraw.Draw(image)

c = 0.5 + 0.2j
for x in range(SIZE):
    for y in range(SIZE):
        re = (x * 2.0 / SIZE) - 1.0
        im = (y * 2.0 / SIZE) - 1.0

        z=re+im*1j
        for i in range(128):
            if abs(z) > 2.0: break
            z = z * z + c
        d.point((x, y), i * 2)

image.save(r"c:\julia.png", "PNG")

Here is a movie(2MB, c = -0.78 + i * 0.002 + 0.23j (i < 40), center = -0.5 + 0.2j, scale = 1.0). I think this type of movie isn't suitable for MPEG compression, it is raw avi.

[Python]Eliminate assignment before conditional statement

Python doesn't allow to write a statement in a condition clause.
The limitation keeps beginners away from the well-known bug;
using an assignment while thay want to evaluate equality of two values.
However, it is a little pain to be forced an assignment before a conditional statement for me as below.

import re

data = "aaaabbbbaaaa"

m = re.search("b+", data)
if m:
    print "'b+' is found at", m.start()

One possible solution is introducing a stack.
By using my 'bigstack' library you can write as below.

import re
import bigstack

data = "aaaabbbbaaaa"

if push(re.search("b+", data)):
    print "'b+' is found at", pop().start()

The library introduces two function 'push' and 'pop' to the built-in namespace. You may easily imagine how it works. And the temporary variable 'm' is no longer needed.

The source code of the 'bigstack' library is as below. It is very simple.
I doesn't think it is the perfect solution, but it could make your code more pretty especially in a 'while' statement.

"""bigstack.py: singleton stack to eliminate temporary variables"""

import __builtin__

BIG_STACK = []

def push(x):
    BIG_STACK.append(x)
    return x

def pop():
    return BIG_STACK.pop()

__builtin__.__dict__.update(
    push=push,
    pop=pop
)

-----
p.s.
I'm sorry. It requires extra "else" clause to pop the value. worthless...

[Python]Simple Impl. of Bloom Filter

Bloom filter is a data structure to tell whether an object is in given list or not. Of cource, if you hold the given list you can do it. The merit of bloom filter is it doesn't need to hold the original list. As a result you can save a memory space. However, it lost an accuracy of result as the price of space-efficiency. It is possible to answer 'yes' while a query is not in the list in a probability. Because you can estimate the probability, bloom filter remains useful.

The following source is a simple implementation of a bloom filter to learn algorithm.

SIZE = 1987
def hashes(s):
    xs = [0, 0, 0]
    for c in s:
        o = ord(c)
        xs[0] = xs[0] * 137 + o
        xs[1] = xs[1] * 69 + o
        xs[2] = xs[2] * 545 + o

    return [x % SIZE for x in xs]

class BloomFilter(object):
    def __init__(self):
        self.bitarray = [0] * SIZE

    def add(self, s):
        for x in hashes(s):
            self.bitarray[x] = 1

    def query(self, s):
        return all(
            self.bitarray[x] == 1
            for x in hashes(s))

The function 'hashes' calculates three hash value using three different hash function. Class 'BloomFilter' has a bit-array. For simple implementation, I use a list as a substitute for a bit array. It decleases the bloom filter's merit much so you shouldn't use the code in practical use.

The following list is the result of interactive execution on a python's shell.

>>> bf = BloomFilter()
>>> bf.add("hoge")
>>> bf.query("hoge")
True
>>> bf.query("hoga")
False
>>> bf.add("foo")
>>> bf.add("bar")
>>> bf.add("baz")
>>> bf.query("hoga")
False
>>> bf.query("foo")
True

When a string added, the bloom filter write '1' on the position of bit array corresponds to each hash value. When a string queried, the bloom filter checks each position and if and only if all of them are '1' it says 'True'. You can imagine more strings are added, the bit array has more '1', and bloom filter more possibly says 'True'. The probability can easily estimate. Given m is the size of bit array, k is the number of hash functions and n is the number of strings you added, the probability is (1 - exp(-float(k * n) / m)) ** k. In this case, m equals 1987 and k equals 3, so when n is 100 the prob. is 0.003 and when n is 1000 the prob. is 0.47. You have to increase the size of bit array if you want to add 1000 strings to a bloom filter.

Get values from Wii Remote (through IronPython and WiimoteLib.dll)

This entry is translation of my entry in Japanese. http://d.hatena.ne.jp/nishiohirokazu/20071227/1198746597

To get values from Wii Remote through IronPython is very easy.
At first you need to get WiimoteLi.dll from
Managed Library for Nintendo's Wiimote - Release: WiimoteLib v1.2.
Its document is nice.

And then save a following script as name "setup_wii.py"

import clr
clr.AddReferenceToFile("wiimotelib.dll")

from WiimoteLib import *

wii = Wiimote()
def get_value(sender, args):
   global a
   a = args

wii.WiimoteChanged += WiimoteChangedEventHandler(get_value)

wii.Connect()
wii.SetReportType(wii.InputReport.IRAccel, True) 

In the script, at first I get a namespace "WiimoteLib" from wiimotelib.dll and import all objects in it.
Secondly I make an instance of "Wiimote" class. Its "WiimoteChanged" field is "event" and "+=" means "add event listener". I set a minimal event listener.
Finally I call connect its instance and tell it should return IR-Camera data and accelation data. You should read WiimoteLib.dll's document and choice the correct report type.

Let's use the script in interactive console.

>>> import setup_wii
>>> setup_wii.a
<WiimoteChangedEventArgs object at 0x000000000000002B>

OK, I got the argument of the event listener.
To know what fields the object have, you should read WiimoteLib.dll's document. It is very comprehensive. Today I want to get the result of IR-Camera, so I did like below.

>>> setup_wii.a.WiimoteState
<WiimoteState object at 0x000000000000002C>
>>> setup_wii.a.WiimoteState.IRState
<WiimoteLib.IRState object at 0x000000000000002D [WiimoteLib.IRState]>
>>> setup_wii.a.WiimoteState.IRState.X1
0.379091

I got it! It is very easy!

Reference:
Coding4Fun : Managed Library for Nintendo's Wiimote

Acknowledge:
The reference to my Japanese entry in IronPython URL's: Using the Wiimote from IronPython motivated me to write blog in English. Thanks!