Creating a Bitarray in python

Sunday, July 1, 2012

This code shows an implementation of bitarray in python using the bytearray built-in function, it can set/unset and fetch a bit from a given array index location, in the below example we create a bitarray of size 32k.

Listing 1: bitarray.py

"""
   Creating and accessing elements in a bitarray
   The bitarray is created from a bytearray
   
   Author: S.Prasanna
"""

class Bitarray:
    def __init__(self, size):
        """ Create a bit array of a specific size """
        self.size = size
        self.bitarray = bytearray(size/8)

    def set(self, n):
        """ Sets the nth element of the bitarray """

        index = n / 8
        position = n % 8
        self.bitarray[index] = self.bitarray[index] | 1 << (7 - position)

    def get(self, n):
        """ Gets the nth element of the bitarray """
        
        index = n / 8
        position = n % 8
        return (self.bitarray[index] & (1 << (7 - position))) > 0 

    def unset(self, n):
        """ Unsets the nth element of the bitarray """
        
        index = n / 8
        position = n % 8
        self.bitarray[index] = self.bitarray[index] & ((1 << (7 - position)) - 1)

if __name__ == "__main__":
    bitarray_obj = Bitarray(32000)
    for i in range(5):
        print "Setting index %d of bitarray .." % i
        bitarray_obj.set(i)
        print "bitarray[%d] = %d" % (i, bitarray_obj.get(i))
        print "Unset index %d of bitarray .." % i
        bitarray_obj.unset(i)
        print "bitarray[%d] = %d" % (i, bitarray_obj.get(i))
Syntax highlighter: Pygments

Sample Output:

>>>
Setting index 0 of bitarray ..
bitarray[0] = 1
Unset index 0 of bitarray ..
bitarray[0] = 0
Setting index 1 of bitarray ..
bitarray[1] = 1
Unset index 1 of bitarray ..
bitarray[1] = 0
Setting index 2 of bitarray ..
bitarray[2] = 1
Unset index 2 of bitarray ..
bitarray[2] = 0
Setting index 3 of bitarray ..
bitarray[3] = 1
Unset index 3 of bitarray ..
bitarray[3] = 0
Setting index 4 of bitarray ..
bitarray[4] = 1
Unset index 4 of bitarray ..
bitarray[4] = 0
>>>

A quick reference to HTML/URL escape/unescape methods in python

This code briefs about some of the escape/unescape methods in python available for HTML special characters and also ways to quote/unquote characters using urllib methods, though obvious, this is one of the common tasks involved when we generate/parse HTML/XML documents and process URLs.


"""
   Escape/unescape URL encode/unquote methods in python
   Shows the use of different methods available for these tasks
   
   Note: For detailed description of the differences between
   these methods, refer the respective python doc/wiki, the purpose
   of this code is to have a quick reference for these common
   repititive tasks
   
   Author: S.Prasanna
"""

import xml.sax.saxutils
import HTMLParser
import urllib2

# Escape <, > and &
char_list = ["<", ">", "&"]
html_char_list = ["&lt;", "&gt;", "&amp;"]

# Escape/unescape through xml.sax.saxutils escape/unescape methods
for item in char_list:
    print "escape(%s) = %s" % (item, xml.sax.saxutils.escape(item))

for item in html_char_list:
    print "unescape(%s) = %s" % (item, xml.sax.saxutils.unescape(item))

# Unescape through HTMLParser object's method
htmlparser_obj = HTMLParser.HTMLParser()
for item in html_char_list:
    print "unescape(%s) = %s" % (item, htmlparser_obj.unescape(item))

# URL encodings
url_char_list = [";", " ", "+", ","]

for item in url_char_list:
    print "quote(%s) = %s, unquote(%s) = %s" %\
          (item, urllib2.quote(item), urllib2.quote(item), urllib2.unquote(urllib2.quote(item)))
Syntax highlighter: Pygments

Sample Output:

>>>
escape(<) = &lt;
escape(>) = &gt;
escape(&) = &amp;
unescape(&lt;) = <
unescape(&gt;) = >
unescape(&amp;) = &
unescape(&lt;) = <
unescape(&gt;) = >
unescape(&amp;) = &
quote(;) = %3B, unquote(%3B) = ;
quote( ) = %20, unquote(%20) =
quote(+) = %2B, unquote(%2B) = +
quote(,) = %2C, unquote(%2C) = ,
>>>

Finding a missing number in an array using XOR logic

This python program illustrates the way to find a missing number in an array (list) using XOR logic.


"""
   Code to find the missing number using XOR gate
   Author: S.Prasanna
"""

def XOR(input_list):
    """ XOR all elements in a list """

    def recXOR(index):
        if index == 0:
            return input_list[0]
        else:
            return input_list[index] ^ recXOR(index - 1)

    return recXOR(len(input_list)- 1)

if __name__ == "__main__":
    input_list = [ -4, -2, 5, 6, 80 ]
    print "Input list =", input_list
    XOR1 = XOR(input_list)
    print "XOR of all elements in the list (XOR1) =", XOR1

    for index, value in enumerate(input_list):
        element = input_list.pop(index)
        print "Removed element %d from the list" % element
        XOR2 = XOR(input_list)
        print "New XOR of all items (XOR2) =", XOR2
        print "Missing element (XOR1 ^ XOR2) =", XOR1 ^ XOR2
        input_list.insert(index, element)
Syntax highlighter: Pygments

Sample Output:

>>>
Input list = [-4, -2, 5, 6, 80]
XOR of all elements in the list (XOR1) = 81
Removed element -4 from the list
New XOR of all items (XOR2) = -83
Missing element (XOR1 ^ XOR2) = -4
Removed element -2 from the list
New XOR of all items (XOR2) = -81
Missing element (XOR1 ^ XOR2) = -2
Removed element 5 from the list
New XOR of all items (XOR2) = 84
Missing element (XOR1 ^ XOR2) = 5
Removed element 6 from the list
New XOR of all items (XOR2) = 87
Missing element (XOR1 ^ XOR2) = 6
Removed element 80 from the list
New XOR of all items (XOR2) = 1
Missing element (XOR1 ^ XOR2) = 80
>>>

How to create a dictionary/list/tuple from a string in python

I often wondered about the easiest way to create a dictionary, tuple or a list from it's string representation in python, found out that the eval built-in function can be used to do the same, in the below example, we will see several different usages of eval command to convert a string into a dictionary, list and tuple.

Listing 1: eval.py

"""
   Create dictionaries, tuples, lists from string
   using eval built-in function
   
   Author: S.Prasanna
"""

dict_str = "{1:1, 2:2, 3:3, 4:4}"
tuple_str = "tuple(dict_obj)"
list_str = "list(dict_obj)"

print "dict_str = %s,type(dict_str) = %s" % (dict_str, type(dict_str))
print "tuple_str = %s,type(tuple_str) = %s" % (tuple_str, type(tuple_str))
print "list_str = %s, type(list(str) = %s" % (list_str, type(list_str))

dict_obj = eval(dict_str)
tuple_obj = eval(tuple_str)
list_obj = eval(list_str)

print "dict_obj = %s,type(dict_str) = %s" % (dict_obj, type(dict_obj))
print "tuple_obj = %s,type(tuple_str) = %s" % (tuple_obj, type(tuple_obj))
print "list_obj = %s, type(list(str) = %s" % (list_obj, type(list_obj))
Syntax highlighter: Pygments

Sample Output:

>>>
dict_str = {1:1, 2:2, 3:3, 4:4},type(dict_str) = <type 'str'>
tuple_str = tuple(dict_obj),type(tuple_str) = <type 'str'>
list_str = list(dict_obj), type(list(str) = <type 'str'>
dict_obj = {1: 1, 2: 2, 3: 3, 4: 4},type(dict_str) = <type 'dict'>
tuple_obj = (1, 2, 3, 4),type(tuple_str) = <type 'tuple'>
list_obj = [1, 2, 3, 4], type(list(str) = <type 'list'>
>>>

Towers of Hanoi explained in python

This code illustrates the Towers of Hanoi problem solution with it's simple logic - to move 'n' number of discs from source(A) to destination(B) using an intermediate rod (B), recursively move n-1 discs from A to B, move nth disc from A to C and then move the rest n-1 discs from B to C, can't get any simpler than python.

Listing 1: towers_of_hanoi.py

"""
    Recursive solution for the towers of hanoi problem
    Author: S.Prasanna
"""

import sys

TOTAL_MOVES = 0    

def move(n, src, middle, dst):
    global TOTAL_MOVES
    if n == 0:
        return
    else:
        move(n - 1, src, dst, middle)
        print "Move disk from %s to %s" % (src, dst)
        TOTAL_MOVES += 1
        move(n - 1, middle, src, dst)
        

n = int(raw_input("Enter the number of disks (n):"))
if n <= 0:
    print "Number of disks should be > 0."
    sys.exit(1)
else:
    move(n, "A", "B", "C")
    print "Total moves = %s" % TOTAL_MOVES
    
Syntax highlighter: Pygments

Sample Output:

>>>
Enter the number of disks (n):3
Move disk from A to C
Move disk from A to B
Move disk from C to B
Move disk from A to C
Move disk from B to A
Move disk from B to C
Move disk from A to C
Total moves = 7
>>>

MS&E 252 Decision Analysis I course in Stanford - an organized approach to decision analysis

An year before I took the MS&E 252 Decision Analysis course in Stanford, thought it would be worthwhile to share how important a formal decision analysis process is in making better decisions and how much difference a course on the same would make.

Well, the primary reason I took this course is mainly because the term 'Decision Analysis' appealed me to an extent and was I also keen to improve my decision making skills. Based on what I learnt, clearly this course impressed me.

The field decision analysis is coined by Prof Ronald A. Howard and it was a privilege to attend a class instructed by him. Decision analysis is all about dealing with uncertain events. The main takeaway from this course for me was, to make better decisions, you need to assign probabilities to different uncertain events based on your knowledge/belief about those events and apply some techniques based on those probabilities to arrive at a decision. The course also helped me to to greatly simplify probability problems through decision trees, something which has practical applications.

Never before I fully realized the power of probabilities in decision analysis till I took this course and after taking this course my approach towards decision analysis was much more organized, always taking into account the important decision analysis principles I learnt through this course. I still remember a situation where I got instant benefit from this course through the application of the sunk cost principle in one my decisions which I was delaying for a while and I am glad that I did apply that principle.

Finally coming to an important question: How much will a course help you make better decisions? Clearly depends on your willingness to go through a process for analyzing decisions, my belief is that if you go through that process, over a period of time your probabilities towards uncertain events will be more realistic and may result in better application of the decision analysis techniques to get close to best results.

Comparing the type of two objects in python

This code illustrates how to compare the type of any two objects in python with a simple example.

Listing 1: type_comparison.py

"""
   Code to check an object's type
   Author: S.Prasanna
"""

print "type(list) = %s" % list
print "type(dict) = %s" % dict
print "type(tuple) = %s" % tuple

list_obj = [1,2]
dict_obj = {1:1, 2:2}
tuple_obj = (1,2)

print "type(%s) == %s is %s" % (list_obj, list, (type(list_obj) == list))
print "type(%s) == %s is %s" % (dict_obj, dict, (type(dict_obj) == dict))
print "type(%s) == %s is %s" % (tuple_obj, dict, (type(tuple_obj) == tuple))
print "type(%s) == %s is %s" % (list_obj, tuple, (type(list_obj) == tuple))
Syntax highlighter: Pygments

Sample Output:

>>>
type(list) = <type 'list'>
type(dict) = <type 'dict'>
type(tuple) = <type 'tuple'>
type([1, 2]) == <type 'list'> is True
type({1: 1, 2: 2}) == <type 'dict'> is True
type((1, 2)) == <type 'dict'> is True
type([1, 2]) == <type 'tuple'> is False
>>>

An easy to understand solution to the eight queens problem in python

This is a simplified version of the famous eight queens problem, often I wondered on how I could I write recursive code for this which would exactly simulate the way one would place the queens on the board manually and remove them from a given position if it isn't the right position and once a solution is found, move on with the next till all solutions were found.

Accordingly this code models the board as a python list and add and remove methods simulate placing and removing a queen from a specific position in the board, hopefully this one will make the understanding part of it little easier and simpler.

Listing 1: eight_queens.py

""" A simple solution to 8 queens problem for easier
    understanding with the board modeled
    as a list and append/remove methods simulate
    placing/removing the queen from the board till
    one correct solution is reached and continues
    from there

    Author: S.Prasanna
    Copyright (C) 2011 by S.Prasanna.
"""

board = []
size = 8

def danger(row, col):
    """ Return if there is a danger by placing queen in
        a given row, col
    """
    for (i, j) in board:
        if row == i: return True
        if col == j: return True
        if abs(row - i) == abs(col - j): return True

    return False
    
def placequeen(row):
    if row > size:
        print board
    else:
        for col in range(1, size + 1):
            if not danger(row, col):
                board.append((row, col))
                placequeen(row + 1)
                board.remove((row,col))

if __name__ == "__main__":
    placequeen(1)
Syntax highlighter: Pygments

Sample Output:

For a board of size 4:

[(1, 2), (2, 4), (3, 1), (4, 3)]
[(1, 3), (2, 1), (3, 4), (4, 2)]

Textwrangler Connection unexpectedly lost error - Solution

When I was using TextWrangler text editor for MAC to connect to a remote Linux system to edit some text files there, once I got an error like the one shown below

"The server operation couldn't be completed because the connection was unexpectedly lost (application error code: 22807)"


Figure 1: TextWrangler connection unexpectedly lost error

Upon looking into the issue in-depth, found out that adding the following entry in /etc/ssh/sshd_config file on the remote Linux machine would fix the issue (you need root privileges for these commands).

1. Edit /etc/ssh/sshd_config, add the following line.

Subsystem sftp /usr/libexec/openssh/sftp-server

2. Restart ssh service

/etc/init.d/sshd stop
/etc/init.d/sshd start

This should fix the TextWrangler connection issue.

How to avoid automatic windows reboots after updates

Many a times it may be not be a pleasant experience when Windows 7 automatically reboots after installing updates without the user explicitly wanting to do it, to avoid automatic reboots after installing updates, change the following settings, the below steps apply to Windows 7 x64 version.

Under Control Panel -> System Security -> Windows Update, click Change Settings


Figure 1: Windows updates settings

Select one of the safer option below other than Install updates automatically (recommended setting) option.


Figure 2: Avoid automatic reboots after Windows updates


Copyright © 2016 Prasanna Seshadri, www.prasannatech.net, All Rights Reserved.
No part of the content or this site may be reproduced without prior written permission of the author.