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

Investment Science: A list of useful excel sheets for computations

Tuesday, March 27, 2012


Has been planning to do this for sometime, but here is a list of excel sheet computations which I developed during my Investment Science course in Stanford, these may help you understand some investment related calculations (like mortgages, Net Present Value, Internal rate of return and so on), the one which may be of frequent use is the mortgage/loan payment schedule given the interest rate and the number of years, personally was of good use to me.

Note: Most of them may be in openoffice format, you may download openoffice software to use these.

1. Spreadsheet:Compound interest calculation

2. Spreadsheet:Calculating Net Present Value (NPV) and Internal rate of return (IRR)

Investment Science for Beginners

Monday, March 26, 2012

A couple of years back I took MS&E 242S - Investment Science course from Stanford where I got a chance to learn several concepts in investment science, some important ones I published as articles, listing a reference to all of them here so that this page serves as a definitive reference for some of the fundamental and important concepts in Investment Science.

Note: For some of the posts, you may need to refer Investment Science by Luenberger for problem statements, but they are also mentioned in the respective entries, also a few articles are meant to familiarize yourself with the basics of working with a financial calculator used to solve some of the problems in Investment science, the one I used being the Texas Instruments BA II Plus Financial Calculator, also familiarity with excel/openoffice spreadsheets may help as some of the problems were solved using spreadsheet/excel computations.

1.   Investment Science: Yearly, monthly and Continuous compounding

2.   Using math symbols in openoffice

3.   Investment Science: Effective and Nominal interest rates

4.   Investment Science: Present Value and Future Value of an investment

5.   Investment Science: Cash flow streams and their present and future values

6.   Investment Science: Present value analysis of cash flow streams - Problem 2.7 Luenberger

7.   Investment Science: Computing Net Present Value of a cash flow stream using a financial calculator

8.   Investment Science: Internal rate of return of a cash flow stream

9.  Investment Science: Computing the Internal rate of return of a cash flow stream using a financial calculator

10. Investment Science: Net Present Value and Internal rate of return calculations in spreadsheet (OpenOffice)

11. Investment Science: Net Present Value vs Internal rate of return analysis in investment decisions - Problem 2.11 Luenberger

12. Investment Science: Incremental internal rate of return for analyzing alternate investment options - Problem 2.8 Luenberger

13. Investment Science: Perpetual Annuity - How to compute your monthly loan payment

14. Investment Science - Understanding the mathematics of Mortgage payments - 1 - Problem 3.6 Luenberger


15. Investment Science: Amortization schedule of a Mortgage/loan payment

16. Investment Science: Variable rate Mortgage - Problem 3.8 Luenberger

17. Investment Science: The price of a bond and it's yield - Problem 3.9 Luenberger

18. Investment Science: Sum of a Geometric series and applications in computing Net Present Value

19. Investment Science: Duration of a bond - Problem 3.10 Luenberger

20. Investment Science: The price of a bond and it's relationship to the Present Value formula

21. Investment Science: Bond Portfolio Immunization

22. Investment Science: Bond Price Sensitivity

23. Investment Science: The Price of a bond and it's duration using excel/spreadsheet - Problem 3.10 Luenberger

24. Investment Science - Bond Portfolio Immunization Example - Problem 3.12 Luenberger


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.