Go deh!

Mainly Tech projects on Python and Electronic Design Automation.

Saturday, September 23, 2017

Unit Conversions.

A little background

Stephan Fitzpatrick had a blog post entitled Recursion, what is it good for? this week where a friend introduced him to a problem and he decided to solve it in a tutorial style using recursion.
I liked the question and gave an iterative solution on reddit.
I had some time, and couldn't help myself from riffing on the question and expanded on the theme.
Later on, I started to get a niggle, and started to search Rosetta Code for that question, and sure enough, the task appears, from June 2015, where I had indeed posted two Python solutions!

The Original question

On RC it begins:
Write a function or program which:
  • takes a positive integer representing a duration in seconds as input (e.g., 100), and
  • returns a string which shows the same duration decomposed into weeks, days, hours, minutes, and seconds as detailed below (e.g., "1 min, 40 sec"). ...
Not knowing I had already solved it I posted this solution on reddit

Reddit solution

In [ ]:
def say_secs(seconds):
    names = 'sec min hour day week'.split()
    modulos = [60, 60, 24, 7]
    units, remainder = [], seconds
    for mod in modulos:
        remainder, unit = divmod(remainder, mod)
        units.append(unit)
    units.append(remainder)
    plurals = [('' if count == 1 else 's') for count in units]
    out = ' '.join(f'{count} {name}{p}'
                   for count, name, p 
                     in (zip(units[::-1], names[::-1], plurals[::-1]))
                   if count)
    return out or '0 secs'


if __name__ == '__main__':
    for s in [0, 100, 66400, 172801, 987987]:
        print(f'{s:6} seconds is: {say_secs(s)}')

What's it good for?

I looked at my reddit solution and thought "I could make that work for other units by modifying the modulos name appropriately".
A quick look on Wikipedia gave me info on Imperial units of measurement and I decided to add length in inches.

Refactorings to add units of length

I was going to need to change the names and modulos variables for another system of units, that was obvious. Looking at the new names I had though made me realise that plurals can't always be made by simply adding an "s". Inch becomes inches; foot becomes feet, so I had to pull namesmodulos, and pluralsout of the function above.
This stage of the code, supporting two units of measurement became:
In [ ]:
def say_secs(seconds):
    names = 'sec min hour day week'.split()
    plurals = [f'{n}s' for n in names]
    modulos = [60, 60, 24, 7]  # next unit is x times this  for unit in names
    return say_units(seconds, names, plurals, modulos)

def say_inches(inches, progression=False):
    names = 'inch foot yard chain furlong mile'.split()
    plurals = 'inches feet yards chains furlongs miles'.split()
    modulos = [12, 3, 22, 10, 8]
    return say_units(inches,  names, plurals, modulos)

def say_units(amount, names, plurals, modulos):
    units, remainder = [], amount
    for mod in modulos:
        remainder, unit = divmod(remainder, mod)
        units.append(unit)
    units.append(remainder)
    named = [(singular if count == 1 else plural) for 
             count, singular, plural in zip(units, names, plurals)]
    out = ' '.join(f'{count} {name}'
                   for count, name
                     in (zip(units[::-1], named[::-1]))
                   if count)
    return out or f'0 {plurals[0]}'


if __name__ == '__main__':
    print('\n###')
    for s in [0, 100, 66400, 172801, 987987]:
        print(f'{s:6} seconds is: {say_secs(s)}')
    print('\n###')
    say_inches(0, progression=True)
    for i in [0, 100, 66400, 172801, 987987]:
        print(f'{i:6} inches are: {say_inches(i)}')

Progressions

Too aid me I found I added the comment on the first assignment to modulos of
# next unit is x times this  for unit in names
The above was to remind me of how each measure relates to the next. Thinking about it, I thought it would make a nice printout too so added it requirements.

Adding Volumes

I wanted to add imperial units of volume, pints and what not. I found some reference material here.
Hmm, one, two, many - that's my mantra for checking if I need to maybe create a function and loop over something if I am repeating myself.
I now have three units of measurements which would have three pretty similar sections of code in the if __name__ == ... block.
With the additional requirement of wanting to print the progressions" of the units I decided to Use a class. One instantiaon per unit of measurement; make it callable for it's main action.

Result supporting three units of measurement and using classes

In [3]:
class Say_unit():
    def __init__(self, names, plurals, modulos):
        self.names = names
        self.plurals = plurals
        self.modulos = modulos
    
    def __call__(self, amount):
        return self.say_units(amount)
    
    def say_units(self, amount):
        names, plurals, modulos = self.names, self.plurals, self.modulos
        units, remainder = [], amount
        for mod in modulos:
            remainder, unit = divmod(remainder, mod)
            units.append(unit)
        units.append(remainder)
        named = [(singular if count == 1 else plural) for 
                 count, singular, plural in zip(units, names, plurals)]
        out = ' '.join(f'{count} {name}'
                       for count, name
                         in (zip(units[::-1], named[::-1]))
                       if count)
        return out or f'0 {plurals[0]}'

    def print_progression(self):
        for i, mod in enumerate(self.modulos):
            print('  '* i + f'{mod} {self.plurals[i]} in 1 {self.names[i+1]}')
        print()

def sample_unit_conversion(title, names, plurals, modulos):
    print(f'\n### {title}')
    unit_convertor = Say_unit(names, plurals, modulos)
    unit_convertor.print_progression()
    for units in [0, 100, 66400, 172801, 987987]:
        print(f'{units:6} {plurals[0]} is: {unit_convertor(units)}')
         
    

if __name__ == '__main__':
    title = 'Seconds of time'
    names = 'sec min hour day week'.split()
    plurals = [f'{n}s' for n in names]
    modulos = [60, 60, 24, 7]
    sample_unit_conversion(title, names, plurals, modulos)
 
    title = 'Inches of length'
    names = 'inch foot yard chain furlong mile'.split()
    plurals = 'inches feet yards chains furlongs miles'.split()
    modulos = [12, 3, 22, 10, 8]
    sample_unit_conversion(title, names, plurals, modulos)

    title = 'Fluid ounces of volume'
    names = 'fluid ounce, gill, cup, pint, quart, gallon, peck'.split(', ')
    plurals = [f'{n}s' for n in names]
    modulos = [5, 2, 2, 2, 4, 2]
    sample_unit_conversion(title, names, plurals, modulos)
    
    
### Seconds of time
60 secs in 1 min
  60 mins in 1 hour
    24 hours in 1 day
      7 days in 1 week

     0 secs is: 0 secs
   100 secs is: 1 min 40 secs
 66400 secs is: 18 hours 26 mins 40 secs
172801 secs is: 2 days 1 sec
987987 secs is: 1 week 4 days 10 hours 26 mins 27 secs

### Inches of length
12 inches in 1 foot
  3 feet in 1 yard
    22 yards in 1 chain
      10 chains in 1 furlong
        8 furlongs in 1 mile

     0 inches is: 0 inches
   100 inches is: 2 yards 2 feet 4 inches
 66400 inches is: 1 mile 3 chains 18 yards 1 foot 4 inches
172801 inches is: 2 miles 5 furlongs 8 chains 4 yards 1 inch
987987 inches is: 15 miles 4 furlongs 7 chains 10 yards 3 inches

### Fluid ounces of volume
5 fluid ounces in 1 gill
  2 gills in 1 cup
    2 cups in 1 pint
      2 pints in 1 quart
        4 quarts in 1 gallon
          2 gallons in 1 peck

     0 fluid ounces is: 0 fluid ounces
   100 fluid ounces is: 2 quarts 1 pint
 66400 fluid ounces is: 207 pecks 1 gallon
172801 fluid ounces is: 540 pecks 1 fluid ounce
987987 fluid ounces is: 3087 pecks 3 quarts 1 pint 1 gill 2 fluid ounces
We have a unit of volume that is two words fluid ounce so I had to make a slight change of its name string initial value and splitting. Say_unit.print_progression is new, and function sample_unit_conversion cuts down on the cut-n-paste coding.
END.
In [ ]:
 

Sunday, September 17, 2017

Pythons Positive Press Pumps Pandas

With the publishing of two Stack Overflow blog posts, this week has seen several articles feeding off them and cherry picking parts, as well as divorcing those quotes from context, but all in praise of Python.

That's got to be all good for Python, right?

Well this is hype. It can be riding the tigers tail were control is limited and we can end up in a local maxima that it is hard to escape from. Ruby had this kind of thing with Ruby on Rails, a successful application that ended up overshadowing the language - my search for Ruby on Rails for example had Google giving, under the "People also ask" banner: "Is Ruby and Ruby on Rails the same thing?".

Several of the articles referencing the SO originals latch on to SO 's belief that the Pandas library and therefore data science is the key to Pythons success. That is all well and good, but these articles, and the original SO ones, don't show that Pandas is one library amongst a broad area of computing were Python has a useful presence. It is often the breadth of Pythons influence that turn users to Python:

  • The statisticians who first learned R, Who still use R, but also use Python - Some switch wholly from a language designed for them to Python because when they want to do things with their stats then Python is more likely to support not just the stats, but their other field too.
  • Teaching. Prestigious Universities changing their computing course-ware language to Python because it is more relevant than Lisp/Scheme. If they want to ultimately control a robot, Python is more likely to have existing libraries for that.
  • Pythons ease of learning reputation "rubs-off" on libraries. Wrapping advanced GPU acceleration libraries, or machine learning libraries in Python; even though they are mainly written in other languages the Python integration gives those libraries an air of approach-ability. There is substance to this, as when well wrapped, these external libraries become Pythonic; aspects of their use just come for free from the users knowledge of existing Python as they conform to its idioms.
I would like to congratulate the Pandas team in their success, (Yay), but with current reporting, we need to remind those new to, and just looking at Python, that it is no one-trick Pony!

END.

Sunday, July 30, 2017

Egyptian division

Egyptian division

Egyptian division is a method of dividing integers using addition and doubling that is similar to the algorithm of Ethiopian multiplicaion

Algorithm:

Given two numbers where the dividend is to be divided by the divisor:
  1. Start the construction of a table of two columns: powers_of_2, and doublings; by a first row of a 1 (i.e. 2^0) in the first column and 1 times the divisor in the first row second column.
  2. Create the second row with columns of 2 (i.e 2^1), and 2 * divisor in order.
  3. Continue with successive i'th rows of 2^i and 2^i * divisor.
  4. Stop adding rows, and keep only those rows, where 2^i * divisor is less than or equal to the dividend.
  5. We now assemble two separate sums that both start as zero, called here answer and accumulator
  6. Consider each row of the table, in the reverse order of its construction.
  7. If the current value of the accumulator added to the doublings cell would be less than or equal to the dividend then add it to the accumulator, as well as adding the powers_of_2 cell value to the answer.
  8. When the first row has been considered as above, then the integer division of dividend by divisor is given by answer.
    (And the remainder is given by the absolute value of accumulator - dividend).

Example: 580 / 34

Table creation:

powers_of_2doublings
134
268
4136
8272
16544

Initialization of sums:

powers_of_2doublingsansweraccumulator
134
268
4136
8272
16544
00

Considering table rows, bottom-up:

When a row is considered it is shown crossed out if it is not accumulated, or bold if the row causes summations.
powers_of_2doublingsansweraccumulator
134
268
4136
8272
1654416544
powers_of_2doublingsansweraccumulator
134
268
4136
827216544
16544
powers_of_2doublingsansweraccumulator
134
268
413616544
8272
16544
powers_of_2doublingsansweraccumulator
134
26816544
4136
8272
16544
powers_of_2doublingsansweraccumulator
13417578
268
4136
8272
16544

Finally

So 580 divided by 34 using the Egyptian method is 17 remainder (578 - 580) or 2.

Rosetta Code

This blog post should be a Rosetta Code task, but at the time of writing the site has been down for maintenance for a week. I will still writethe task description and its first Python solution though.

Task

The task is to create a function that does Egyptian division. The function should closely follow the description above in using a list/array of powers of two, and another of doublings.
  • Functions should be clear interpretations of the algorithm.
  • Use the function to divide 580 by 34 and show the answer here, on this page.

Python Solution

In [2]:
def egyptian_divmod(dividend, divisor):
    assert divisor != 0
    pwrs, dbls = [1], [divisor]
    while dbls[-1] <= dividend:
        pwrs.append(pwrs[-1] * 2)
        dbls.append(pwrs[-1] * divisor)
    ans, accum = 0, 0
    for pwr, dbl in zip(pwrs[-2::-1], dbls[-2::-1]):
        if accum + dbl <= dividend:
            accum += dbl
            ans += pwr
    return ans, abs(accum - dividend)

# Test it gives the same results as the divmod built-in
from itertools import product
for i, j in product(range(13), range(1, 13)):
        assert egyptian_divmod(i, j) == divmod(i, j)

# Mandated result
i, j = 580, 34
print(f'{i} divided by {j} using the Egyption method is %i remainder %i'
      % egyptian_divmod(i, j))
580 divided by 34 using the Egyption method is 17 remainder 2

Extra

A quick note on hardware applications.
The astute may note that the doublings column entries are easily computed as successive shifts of the binary representation of the divisor; and that the result in binary can be read off by marking 1 if a table row is summed or 0 if it is not.

Followers

Subscribe Now: google

Add to Google Reader or Homepage

Go deh too!

whos.amung.us

Blog Archive