Pages

2012-09-05

Divisors.

I've been thinking about how to find divisors of an integer i (supposedly between 10 and 100 or so) manually and as effortlessly as possible.
I wrote the code below to check if the results are correct by comparison with a simple brute-force way.
In hand calculation, you have to find an integer a that satisfies the condition a 2 i < a + 1 2 instead of math.sqrt(i).

#!/usr/bin/env python
# -*- coding: utf-8 -*-
# divisors.py - returns list of divisors
import math, sys, traceback

def check1by1(int_num): # check all numbers from 1 to int_num.
    int_num = abs(int_num)
    if int_num == 0:
        return None
    else:
        div_list = []
        for i in range(1, int_num + 1):
            if int_num % i == 0:
                div_list.append(i)
        return div_list

def getdivisors(int_num): # avoid unnecessary calculation.
    """Return list of divisors of int_num. (None if int_num == 0.)"""
    int_num = abs(int_num)
    if int_num == 1:
        return [1]
    elif int_num == 0:
        return None
    else:
        div_list = [1, int_num]
        start = 2
        step = 1
        if int_num % 2 != 0: # if int_num is odd, even divisors are excluded.
            start = 3
            step = 2
        for i in range(start, int(math.sqrt(int_num)) + 1, step):
            if int_num % i == 0:
                div_list.append(i)
                if i != int_num / i:
                    div_list.append(int_num / i)
        return sorted(div_list)

if __name__ == '__main__':
    try:
        num = int(sys.argv[1])
    except IndexError:
        print('usage: python divisors.py integer')
        sys.exit(0)
    simple = check1by1(num)
    print('check1by1  ', num, simple)
    shortcut = getdivisors(num)
    print('getdivisors', num, shortcut)
    if simple != shortcut: # Error checking.
        print('Error.')

Update, September 7, 11:43 p.m. JST: xrange() instead of range(), benchmark().
#!/usr/bin/env python
# -*- coding: utf-8 -*-
# divisors.py - returns list of divisors
import math, sys, time

def benchmark(int_num, fn):
    start_time = time.clock()
    result = fn(int_num)
    elapsed_time = time.clock() - start_time
    return result, elapsed_time

def check1by1(int_num): # check all numbers from 1 to int_num.
    int_num = abs(int_num)
    if int_num == 0:
        return None
    else:
        div_list = []
        for i in xrange(1, int_num + 1):
            if int_num % i == 0:
                div_list.append(i)
        return div_list

def getdivisors(int_num): # avoid unnecessary calculation.
    """Return list of divisors of int_num. (None if int_num == 0.)"""
    int_num = abs(int_num)
    if int_num == 1:
        return [1]
    elif int_num == 0:
        return None
    else:
        div_list = [1, int_num]
        start = 2
        step = 1
        if int_num % 2 != 0: # if int_num is odd, even divisors are excluded.
            start = 3
            step = 2
        for i in xrange(start, int(math.sqrt(int_num)) + 1, step):
            if int_num % i == 0:
                div_list.append(i)
                div_result = int_num / i
                if i != div_result:
                    div_list.append(div_result)
        return sorted(div_list)

if __name__ == '__main__':
    try:
        num = int(sys.argv[1])
    except IndexError:
        print('usage: python divisors.py integer')
        sys.exit(0)
    simple = benchmark(num, check1by1)
    shortcut = benchmark(num, getdivisors)
    if simple[0] != shortcut[0]: # Error checking.
        print('Error.')
    print('check1by1  ', num, simple)
    print('getdivisors', num, shortcut)
    print('time difference: ' + str(simple[1] - shortcut[1]) + ' sec.')

2012-09-02

Python: Filtering Delicious bookmarks by tags

bmconv.py is required.
#!/usr/bin/env python
# -*- coding: utf-8 -*-
# bmfilter.py - Filter bookmarks by tags.
import bmconv

def tagfilter(tags_list):
    """Return a list of bookmark dictionaries."""
    return filter(lambda x: set(tags_list) <= set(x['tags']), bmconv.main())

if __name__ == '__main__':
    print(tagfilter(['book', 'history']))
The above example outputs only bookmarks that have both 'book' and 'history' tags.

Update, September 2, 8:41 p.m. JST: AND/OR filters.
#!/usr/bin/env python
# -*- coding: utf-8 -*-
# bmfilter.py - Filter bookmarks by tags.
import bmconv

def andfilter(tags_list):
    """Return a list of bookmarks that have all the tags in tags_list."""
    return filter(lambda x: set(tags_list) <= set(x['tags']), bmconv.main())

def orfilter(tags_list):
    """Return a list of bookmarks that have any of the tags in tags_list."""
    return filter(lambda x: len(set(tags_list).intersection(set(x['tags']))) > 0, bmconv.main())

if __name__ == '__main__':
#    print(andfilter(['book', 'history']))
    print(orfilter(['cd', 'dvd']))

Update, September 3, 6:59 p.m. JST: Changed function name and arguments. Added case sensitivity switch.
#!/usr/bin/env python
# -*- coding: utf-8 -*-
# bmfilter.py - Filter bookmarks by tags.
import bmconv

def tagfilter(tags_list, bookmarks_list, filter_type_and=True, ignore_case=True):
    """Return a list of dictionaries of bookmarks filtered from bookmarks_list by tags in tags_list."""
    
    def proc_case(str_list):
        if ignore_case:
            return map(lambda x: x.upper(), str_list)
        else: # case sensitive
            return str_list

    if filter_type_and: # AND
        return filter(lambda x: set(proc_case(tags_list)) <= set(proc_case(x['tags'])), bookmarks_list)
    else: # OR
        return filter(lambda x: len(set(proc_case(tags_list)).intersection(set(proc_case(x['tags'])))) > 0, bookmarks_list)

if __name__ == '__main__':
    print(tagfilter(['book', 'history'], bmconv.main()))
##      bookmarks that have both tags 'book' and 'history'
##      (case insensitive. also matches 'Book', 'History', etc.)
    print(tagfilter(['cd', 'dvd'], bmconv.main(), False))
##      bookmarks that have any of tags 'cd' and 'dvd'
##      (case insensitive. also matches 'CD', 'Cd', 'DVD', 'Dvd', etc.)
    print(tagfilter(['Apple'], bmconv.main(), True, False))
##      doesn't match 'apple'.

Python: Converting Delicious bookmarks.

#!/usr/bin/env python
# -*- coding: utf-8 -*-
# bmconv.py - Read Delicious.com bookmark file and convert it into a list of dictionaries.
import re

bookmark_file = 'delicious.html'

def main():
    """Return a list of dictionaries of bookmarks."""
    lines_list = []
    with open(bookmark_file, 'r') as f:
        lines_list = f.readlines()
    entries_list = []
    for idx, line in enumerate(lines_list):
        entry = {}
        if re.match(r'^<DT>', line):
            entry['url'] = re.match(r'^.*HREF=\"([^\"]+)\"', line).group(1)
            entry['add_date'] = re.match(r'^.*ADD_DATE=\"([^\"]+)\"', line).group(1)
            entry['private'] = re.match(r'^.*PRIVATE=\"([^\"]*)\"', line).group(1)
            entry['tags'] = re.match(r'^.*TAGS=\"([^\"]*)\"', line).group(1).split(',')
            entry['title'] = re.match(r'^.*<A [^>]+>(.*)</A>', line).group(1)
            if re.match(r'^<DD>', lines_list[idx + 1]):
                dd_tmp = []
                increment = 1
                try:
                    while True:
                        if re.match(r'^<DT>', lines_list[idx + increment]):
                            break
                        dd_tmp.append(re.match(r'^(<DD>)?(.*)$', lines_list[idx + increment]).group(2))
                        increment += 1
                except:
                    pass
                entry['description'] = '\n'.join(dd_tmp)
            entries_list.append(entry)
    return entries_list

if __name__ == '__main__':
    print(main())

Download bmconv.py from Google Drive