Go deh!

Mainly Tech projects on Python and Electronic Design Automation.

Sunday, July 27, 2014

Does the Californian dressing down, jeans-n-T-shirt attire of most software professionals hurt us?

Earlier generations have said  that "You are what you wear" but that doesn't seem to apply in the software industry wear billionaires are seen in the media with hardly a jacket, let alone a tailored suit and tie.

Everybody thinks that they too can be just as successful and, of course, you want to fit in with peers, so most dress down in comparison with other professions.

But what is the effect on the individual?  We can't all be Steve Jobs. Most of us will end up in the median of the profession. Could we  do better if we valued ourselves higher and signalled that to our employers by a mass change in our attire?

We have already seen that large tech companies have been found guilty of colluding to hold back our wages; and that Software outsourcing is not the panacea it was wished to be. Managers know that it can be difficult to recruit good developers too.

So, in this capitalist environment we find ourselves in, maybe we should follow the legal profession and recognise that, in some ways, we are what we wear, and to our employers - currently, they are happy for us to wear jeans.

Thursday, July 10, 2014

Unique numbers in multiplication tables

 I answered a Stack overflow question that asked for the number of unique numbers in an n-by-n multiplication table and got it horribly wrong.
I decided to look into the maths of it a little further last night and now know a bit more about the question but still have no formula for generating the number of distinct integers in an n-by-n multiplication table.

Table generator

In [1]:
def ptable(n):
    width = len(str(n*n))
    nrange = range(1, n+1)
    for i in nrange:
        print(' '.join('%*i' % (width, i * j) for j in nrange))

for n in range(1, 4):
    n2 = 2**n
    print('\n%i-by-%i times table' % (n2, n2))
    ptable(n2)

    
2-by-2 times table
1 2
2 4

4-by-4 times table
 1  2  3  4
 2  4  6  8
 3  6  9 12
 4  8 12 16

8-by-8 times table
 1  2  3  4  5  6  7  8
 2  4  6  8 10 12 14 16
 3  6  9 12 15 18 21 24
 4  8 12 16 20 24 28 32
 5 10 15 20 25 30 35 40
 6 12 18 24 30 36 42 48
 7 14 21 28 35 42 49 56
 8 16 24 32 40 48 56 64

Unique number counter

The only way i could think of counting the number of unique integers is to generate the table then get the size of the set of the tables numbers:
In [2]:
def mult_table_numbs(n):
    nrange = range(1, n+1)
    return len(set(n0 * n1 for n0 in nrange for n1 in nrange))

for n in range(1,11):
    print('%2i: %i' % (n, mult_table_numbs(n)))
 1: 1
 2: 3
 3: 6
 4: 9
 5: 14
 6: 18
 7: 25
 8: 30
 9: 36
10: 42

So for n of 4 there are 9 distinct numbers counted.
Stick the numbers 1,3,6,9,14,18,25,30,36,42 into OEIS and the integer sequence search engine indeed recognises it as A027424
I simplified. I actually first used Pythons itertools.product and reduce. for product I had to use product(range(1,n+1), repeat=2). The repeat=2 is because it is for a two-dimensional multiplication table.
That got me thinking and I quickly realised that I could create a k-dimensional multiplication table unique number counter by setting the repeat to a new argument k with default value 2.

The k-dimensional multiplication table unique number counter

In [3]:
from itertools import product
from functools import reduce

mul = int.__mul__

def mult_table_numbers(n, k=2):
    return len(set(reduce(mul, p, 1) 
                   for p in product(range(1,n+1), repeat=k)))

Dimension hopping

OEIS mentioned no formulae for generating the unique number counts except by direct counting so I thought "what if I explore the dimensions k as well as varying n"?
print('n,k=2.. matrix')

for n in range(2,13):

    print('%2i: %s' % (n, repr([mult_table_numbers(n, k)

                                for k in range(2,10)]).replace(' ','')))
The above takes several tens of minutes to run but finally gives the following results:
n,k=2.. matrix

 2: [3,4,5,6,7,8,9,10]

 3: [6,10,15,21,28,36,45,55]

 4: [9,16,25,36,49,64,81,100]

 5: [14,30,55,91,140,204,285,385]

 6: [18,40,75,126,196,288,405,550]

 7: [25,65,140,266,462,750,1155,1705]

 8: [30,80,175,336,588,960,1485,2200]

 9: [36,100,225,441,784,1296,2025,3025]

10: [42,120,275,546,980,1632,2565,3850]
The 2: [3,4,5,6,7,8,9,10] line reads that for n=2: a 2-dimensional multiplication table has 3 distinct numbers; a 3D table 4; a 5D table 6 distinct numbers, and so on...
Now each line with its series of distinct numbers for different k- dimensions is itself a sequence. The n=2 line is the sequence k+1 for example. I could look up the sequences in OEIS and extract the formulas for each row. If I could then link the formulas for different rows I might be able to finally generate a formula for the unique count, lets call it m(n, k) for dimension k=2.

OEIS extraction

Time on OEIS revealed the following information:
m(n,k)PolynomialOEIS Description
m(2,k)(k+1)Positive integers A000027
m(3,k)(k+1)*(k+2)/2Triangular numbers A000217
m(4,k)(k+1)*(k+1)Squares A000290
m(5,k)(k+1)(k+2)(2*(k+1)+1)/6Square pyramidal numbers A000330
m(6,k)(k+1)*2(k+2)/2Pentagonal pyramidal numbers A002411
m(7,k)(k+1)(2+k)(3+k)(1+3(k+1))/244-dimensional pyramidal numbers A001296
m(8,k)(k+1)^2(k+2)(k+3)/64-dimensional figurate numbers: A002417
m(9,k)((k+1)*(k+2)/2)^2Sum of first n cubes; or n-th triangular number squared A000537
m(10,k)(k+1)*2(k+2)(2k+3)/6A108678
Whilst playing around with the polynomials using SymPy Gamma and the Wolfram sites I rearranged them to help find patterns

Constant multipliers for the polynomials above (when expanded)

I could find no patterns in this:
nk**0k**1k**2k**3k**4
211---
313/21/2--
4121--
5113/63/21/3-
615/221/2-
7131/1219/811/121/8
8117/617/67/61/6
91313/43/21/4
10119/611/311/61/3


nrearranged polynomial for m(n,k)
1(1/(1)) * (1+0k)
2(1/(1)) * (1+k)
3(1/(1*2)) * (1+k)(2+k)
4(1/(1*1)) * (1+k)(1+k)
5(1/(1*2*3)) * (1+k)(2+k)(3+2k)
6(1/(1*2*1)) * (1+k)(2+k)(1+k)
7(1/(1*2*3*4)) * (1+k)(2+k)(3+k)(4+3k)
8(1/(1*2*1*3)) * (1+k)(2+k)(1+k)(3+k)
9(1/(1*2*1*2)) * (1+k)(2+k)(1+k)(2+k)
10(1/(1*2*1*3)) * (1+k)(2+k)(1+k)(3+2k)
There are some patterns in the above. the divisor is always all the constant terms (x+yk) of the polynomial multiplied together.
I then saw that some later polynomials were multiples of earlier ones so decided on using the shorthand @n for m(n,k) to produce the following:

shortformfactored polynomialAlternate factorisation
@1(1+0k)
@2(1+k)
@3@2*(2+k) / 2
@4@2*@2
@5@3*(3+2k) / 3
@6@2*@3
@7@3*(3+k)(4+3k) / 6
@8(@6 = @2*@3)*(3+k) / 3@4*(2+k)(3+k) / 6
@9(@6 = @2*@3)*(2+k) / 2@3*@3
@10(@6 = @2*@3)*(3+2k) / 3@2*@5

Unfortunately I can see no pervasive patterns here either.

Conclusion

I've looked. I've enjoyed the journey, but I've still to find what I'm looking for!

Monday, June 30, 2014

Why do static languages make it difficult to maintain small codebases?

Prompted by this post on Reddit

So many projects are abandoned after wasting millions often due to leaders believing that they can adequately sub-divide a problem to harness large development teams using the features of static languages to deliver huge requirements lists.

Dynamic languages make it plain that someone has to know what is going on  at all times in the software and have use features, such as modularisation and reuse - not just of what is written in one language, but often making it straightforward to integrate best-in-class libraries written in other languages - be they static or dynamic; together with the support of the language community in doing so.

Dynamic languages are excellent in supporting the Unix philosophy of  using small interconnected specialist programs to solve large problems without having to totally reinvent the wheel. Quick prototyping and duck typing often allow several solutions paths to be explored and so dead-ends avoided earlier rather than the usual static language approach which can often lead to inferior solutions having to be pursued due to the general increased time-to-prototype of static languages.

Tuesday, June 24, 2014

Indexing a sublist of a list the way you index a substring of a string


Following this question on reddit, I decided to create a script to index a sublist within a list similar to the way index works for Python strings.

Python Strings

Strings are a concatenation of characters, (although there is no separate character type in Python - a one element string suffices). You can find a substring of characters within a string using the str.index method and the substring can be more than one character. If the substring is not present then ValueError is raised.
In [21]:
help(str.index)
Help on method_descriptor:

index(...)
    S.index(sub [,start [,end]]) -> int
    
    Like S.find() but raise ValueError when the substring is not found.


In [22]:
s = 'abcabcd'
s.index('b')
Out[22]:
1
In [23]:
s.index('ca')
Out[23]:
2
In [24]:
s.index('x')
---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
{ipython-input-24-a677ba2c36a5} in ()
----> 1 s.index('x')

ValueError: substring not found

Python Lists

Single, individual values may be searched for within a list using the list.index method, but a sequence, or sublist of items cannot be searched for:
In [25]:
help(list.index)
Help on method_descriptor:

index(...)
    L.index(value, [start, [stop]]) -> integer -- return first index of value.
    Raises ValueError if the value is not present.


In [26]:
x = [1, 2, 3, 4, 5]
x.index(3)
Out[26]:
2
Try looking for value 3 followed by value 4
In [27]:
x.index([3, 4])
---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
{ipython-input-27-3cb52b6ef201} in ()
----> 1 x.index([3, 4])

ValueError: [3, 4] is not in list
But note:
In [28]:
y = [1, 2, [3, 4], 5]
y.index([3, 4])
Out[28]:
2
Note: the sublist [3,4] exists as a top-level element of y and so in index-able, but the value 3 is not
In [29]:
y.index(3)
---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
{ipython-input-29-f0b9f73a108f} in ()
----> 1 y.index(3)

ValueError: 3 is not in list

The index-ing function

In [30]:
def indexsublist(sub, lst):
    """
    Find a sublist in a list    
    """
    if type(sub) == list:
        sublen = len(sub)
        first = sub[0] if sub else []
    else:
        raise ValueError
    indx = -1
    while True:
        try:
            indx = lst.index(first, indx + 1)
        except ValueError:
            break
        if sub == lst[indx: indx + sublen]:
            return indx
    raise ValueError
Give the function a sub-list together with a list to find it in and for every occurrence of the first item of the sub-list in the list it checks to see if the next items of the list are also the same from that position of the first values match. The while loop tries all matches of the first value of the sub-list until they are all tried or a match is found.

Tests

In [31]:
for x in [[1, 2, 3, 4, [], [4], 3, 4, 5, [1, 2], 3, 5, [1, 2]], ]:
    for sublist in [[5, [1, 2]], [4, 5, [1, 2]], [3, 5, [1, 2]],
                    [[1, 2]], [[1, 2], 3], [[1, 2], 4], [], 4, [4], [[4]]]:
        try:
            ans = indexsublist(sublist, x)
        except ValueError:
            ans = '{ValueError}'
        print('%12s == indexsublist(%14s, %s)' % (ans, sublist, x))
           8 == indexsublist(   [5, [1, 2]], [1, 2, 3, 4, [], [4], 3, 4, 5, [1, 2], 3, 5, [1, 2]])
           7 == indexsublist([4, 5, [1, 2]], [1, 2, 3, 4, [], [4], 3, 4, 5, [1, 2], 3, 5, [1, 2]])
          10 == indexsublist([3, 5, [1, 2]], [1, 2, 3, 4, [], [4], 3, 4, 5, [1, 2], 3, 5, [1, 2]])
           9 == indexsublist(      [[1, 2]], [1, 2, 3, 4, [], [4], 3, 4, 5, [1, 2], 3, 5, [1, 2]])
           9 == indexsublist(   [[1, 2], 3], [1, 2, 3, 4, [], [4], 3, 4, 5, [1, 2], 3, 5, [1, 2]])
{ValueError} == indexsublist(   [[1, 2], 4], [1, 2, 3, 4, [], [4], 3, 4, 5, [1, 2], 3, 5, [1, 2]])
           4 == indexsublist(            [], [1, 2, 3, 4, [], [4], 3, 4, 5, [1, 2], 3, 5, [1, 2]])
{ValueError} == indexsublist(             4, [1, 2, 3, 4, [], [4], 3, 4, 5, [1, 2], 3, 5, [1, 2]])
           3 == indexsublist(           [4], [1, 2, 3, 4, [], [4], 3, 4, 5, [1, 2], 3, 5, [1, 2]])
           5 == indexsublist(         [[4]], [1, 2, 3, 4, [], [4], 3, 4, 5, [1, 2], 3, 5, [1, 2]])

A Find all indices function

There isn't a method on str to find all indices where a substring occurs in a string, but is is a part of the re.module and I decided to augment the above function to have that functionality for lists.
In [32]:
def findall(sub, lst, overlap=True):
    """
    Find all positions of sublist in a list    
    """
    if type(sub) == list:
        sublen = len(sub)
        first = sub[0] if sub else []
    else:
        raise ValueError
    indices, indx = [], -1
    while True:
        try:
            indx = lst.index(first, indx + 1)
        except ValueError:
            break
        if sub == lst[indx: indx + sublen]:
            indices.append(indx)
            if not overlap:
                indx += sublen - 1
    return indices
List indices in function findall just accumulates all the indices as it tries along the lst. Argument overlap chooses between overlapping and nonoverlapping searches. The difference is seen in the last two test outputs for searches for [4, 4].

Tests

In [33]:
for x in [[3, 4, [], [4], 3, 4, 5, [1, 2], 3, 5, [1, 2], 4, 4, 4, 4], ]:
    for sublist in [[5, [1, 2]], [4, 5, [1, 2]], [3, 5, [1, 2]],
                    [[1, 2]], [[1, 2], 3], [[1, 2], 4], [], 4, [[4]], [4, 4]]:
        try:
            ans = findall(sublist, x)
        except ValueError:
            ans = ''
        print('%12s == findall(%14s, %s)' % (ans, sublist, x))
for x in [[3, 4, [], [4], 3, 4, 5, [1, 2], 3, 5, [1, 2], 4, 4, 4, 4], ]:
    for sublist in [[4, 4], ]:
        try:
            ans = findall(sublist, x, overlap=False)
        except ValueError:
            ans = '{ValueError}'
        print('%12s == findall(%14s, %s, overlap=False)' % (ans, sublist, x))
      [6, 9] == findall(   [5, [1, 2]], [3, 4, [], [4], 3, 4, 5, [1, 2], 3, 5, [1, 2], 4, 4, 4, 4])
         [5] == findall([4, 5, [1, 2]], [3, 4, [], [4], 3, 4, 5, [1, 2], 3, 5, [1, 2], 4, 4, 4, 4])
         [8] == findall([3, 5, [1, 2]], [3, 4, [], [4], 3, 4, 5, [1, 2], 3, 5, [1, 2], 4, 4, 4, 4])
     [7, 10] == findall(      [[1, 2]], [3, 4, [], [4], 3, 4, 5, [1, 2], 3, 5, [1, 2], 4, 4, 4, 4])
         [7] == findall(   [[1, 2], 3], [3, 4, [], [4], 3, 4, 5, [1, 2], 3, 5, [1, 2], 4, 4, 4, 4])
        [10] == findall(   [[1, 2], 4], [3, 4, [], [4], 3, 4, 5, [1, 2], 3, 5, [1, 2], 4, 4, 4, 4])
         [2] == findall(            [], [3, 4, [], [4], 3, 4, 5, [1, 2], 3, 5, [1, 2], 4, 4, 4, 4])
{ValueError} == findall(             4, [3, 4, [], [4], 3, 4, 5, [1, 2], 3, 5, [1, 2], 4, 4, 4, 4])
         [3] == findall(         [[4]], [3, 4, [], [4], 3, 4, 5, [1, 2], 3, 5, [1, 2], 4, 4, 4, 4])
[11, 12, 13] == findall(        [4, 4], [3, 4, [], [4], 3, 4, 5, [1, 2], 3, 5, [1, 2], 4, 4, 4, 4])
    [11, 13] == findall(        [4, 4], [3, 4, [], [4], 3, 4, 5, [1, 2], 3, 5, [1, 2], 4, 4, 4, 4], overlap=False)

End.

Followers

Subscribe Now: google

Add to Google Reader or Homepage

Go deh too!

whos.amung.us