This content is organized almost like a story. Start to finish it demonstrates a bunch of related concepts in Python programming. For later reference, these bookmarks jump to specific sections:
map(), reduce(), and lambdamap() and lambda from map() solutionreduce() solutionThis problem was inspired by www.hackerrank.com. The original problem was to take any number N (input by the user), and output a "123...N" result without using any strings to do it. The most elegant solution accepted on www.hackerrank.com is to utilize Python 3 print() function syntax in a single statement that prints range(N) by unpacking it first with an asterick: *.
In [88]:
from __future__ import print_function
# only need this line for Python 2.7 ... by importing print() we also get support for unpacking within print
# * for unpacking is not recognized in this context in Python 2.7 normally
# arguments on print and behavior of print in this example is also Python 3.x which "from _future__" is importing
# assume input of 9:
N = 9
print(*range(N+1), sep='', end='')
In [476]:
# this larger number test is just for comparison with what follows in the attempt to do this mathematically
N = 113
print(*range(N+1), sep='', end='')
As a point of curiosity though ... how would we do it using math instead of relying on print tricks which probably convert the numbers to strings under the covers anyway? The basics of the solution is that the code needs to add zeroes to each number in the sequence in the right amount so that added together, they become the "string" of numbers:
3 1001
20 10000000
+ 100 99900000000
====== ===============
123 99910001001
In [477]:
'''Initial experiment: use powers of 10, but start from the end so that we get: 1 * 10**N + 2 * 10**N-1 + ...
This idea fails however as soon as numbers get bigger than 9
This example outputs the source list generated by range() ahead of the answer just to show it. '''
def num_to_seqStr(N, showList = True):
lst = range(1,N+1)
answer = sum([i*10**(N-i) for i in lst])
if showList == True:
print(lst)
return answer
for i in range(11):
print("Answer: %s" %num_to_seqStr(i))
Note: At 10, it all goes wrong and the number ends in 7900 instead of 78910. This is because the earlier numbers were not multiplied by sufficient powers of 10 so the numbers will sum together correctly into the final answer.
There are better ways to do all of this, but using loops and incrementers to get the right amount of zeroes for each power of ten encountered establishes a simple baseline for what the program internally needs to do.
In [49]:
def findTens(N): # find the powers of 10 inside a number
incrementer = 1
while True:
if N - 10**incrementer < 0:
break
else:
incrementer += 1
if incrementer == 100:
break # debugging condition
return incrementer - 1
In [50]:
findTensTests = [findTens(0),
findTens(7),
findTens(112),
findTens(13),
findTens(1009)]
findTensTests
Out[50]:
In [410]:
def create_seqNum(N, reverse=False, showWork=False, returnDescr=False, divLength=100):
'''create_seqNum() --> iput N, and get back a number built from the sequence of 1234...N
Arguments: reverse=True to get the sequence in revers, showWork=True to see numbers that add up to final,
returnDescr=True to print the answer in a sentence as well as returning it as a number.'''
num = 0
tensIncr = 0
answer = 0
Ntens = findTens(N)
modifier = 0 # modifies counter when increment of 10 occurs
if reverse == True: # create range() inputs
rstart = 1
rend = N+1
rinc = 1
else:
rstart = N
rend = 0
rinc = -1
for i in range(rstart, rend, rinc):
itens = findTens(i)
num = i * 10**tensIncr # how many zeroes do we need on the end of each num?
tensIncr += 1 + itens
pad = (Ntens - itens)
if showWork == True:
print(("For %d" + " "*pad + " Add: %d") %(i, num))
answer += num
if showWork == True:
print("#"*divLength)
if showWork == True or returnDescr == True:
print("Answer: %d" %answer)
print("#"*divLength)
return answer
In [412]:
print(create_seqNum.__doc__)
In [415]:
for i in [1, 5, 9, 10, 11, 13, 98, 99, 100, 101, 102, 107, 1012]:
create_seqNum(i, reverse=True, returnDescr=True)
create_seqNum(i, returnDescr=True)
In [421]:
create_seqNum(102, showWork=True)
Out[421]:
As suggested on Stack Overflow by userID: eruciform, taking the base-10 logarithm of a number should replace the loop logic used in the earlier "findTens()" function. This helps us calculate the powers of 10 in a number to use to help calculate how many zeroes will be needed on each term. This allows the terms to add together into a final that displays them all.
In [51]:
import math # needed for log functions
def powOfTens(N): # find the powers of 10 inside a number
return int(math.log10(N)) # converts decimal to whole integer
# int() rounds down no matter how big the decimal
# note: math.log(x, 10) produces floating point rounding errors
In [52]:
# output is of form: (oritinalNumber, powersOfTens)
countTensTest = [(1, powOfTens(1)),
(7, powOfTens(7)),
(112, powOfTens(112)),
(13, powOfTens(13)),
(1009, powOfTens(1009))]
countTensTest
Out[52]:
In [53]:
listofints = [1,2,3,9,10,11,12,19,99,100,101,102, 999, 1000, 1001, 50102030]
In [54]:
for i in listofints:
print(i, powOfTens(i), math.log10(i)) # show what we are really calculating:
# (original, function result, un-modified log)
This code addresses the underlying calculations. It initially tests the code using a number sequence that is not the full 123... range progression of the original problem, but we can tells from the tests that these approaches work. This code is also designed to quickly solve the problem in as few lines as possible (unlike the loop which was also designed to give options on how to show its inner workings).
In [55]:
# source: eruciform on StackOverflow
# note: powOfTens(x) is just int(math.log10(x))
import math # to get math.log
listofints = [1,2,3,9,10,11,12,19,99,100,101,102, 999, 1000, 1001, 50102030]
n = reduce(lambda x,y:[x[0]*(10**(y[1]+1))+y[0],0],map(lambda x:[x,powOfTens(x)], listofints))[0]
# to do this in one line with no external functions, replace powOfTens(x) w/:
# int(math.log10(x))
print(n)
In [58]:
# source: eruciform on StackOverflow
# we can also more simply crack this problem with just reduce()
n = reduce(lambda x,y:x*(10**(powOfTens(y)+1))+y,listofints)
# to do this in one line with no external functions, replace powOfTens(x) w/:
# int(math.log10(y))
print(n)
Deconstructing the code from the inside out, this is what it is doing.
Starting with the first more complex example using map(), lambda creates an anonymous function that "maps" to all the elements in the list, in this case listofints. The anonymous lambda function applies int(math.log10(x)) to a single x, and then map() "maps" each x in listofints to the lambda function.
In [61]:
listofints = [1,2,3,9,10,11,12,19,99,100,101,102, 999, 1000, 1001, 50102030]
map(lambda x:[x,int(math.log10(x))], listofints)
Out[61]:
Each sublist now contains [original_number, number_of_tens_in_number]. reduce() "reduces" the list to a single number by applying the lambda function fed into it. It takes each term in the list as function(n1 , n2), then the result goes back into the function as function(result, n3), then function(result2, n4) ... and so on until the entire list is consumed and one answer is spit back.
In [74]:
reduce(lambda x,y:[x[0]*(10**(y[1]+1))+y[0],0],map(lambda x:[x,int(math.log10(x))], listofints))
Out[74]:
The lambda function being used to reduce it, grabs the first term of of each sublist and multiplies by 10 to the power of the second term of the next sublist + 1 + the next term. The original format of the sublist is preserved by wrapping the whole thing in [] to make it a list that is then used to replace the original [term, number_powers_of_tens] sublist in listofints. This test function can better show what is happening:
In [69]:
# asume this is a subset from a list like this [ ... 999, 1001, 1002, ...]
# after mapping it with powOfTens() or int(math.log10(x)), the first two terms in the sample would look like this:
testVal = [[999, 2], [1001, 3]] # and it would continue with more terms
testFun = lambda x,y:[x[0]*(10**(y[1]+1))+y[0],0]
testFun(testVal[0], testVal[1])
Out[69]:
In [191]:
# then, as reduce works its way up the list, the answer and the next term feed in like this:
testVal = [[9991001, 2], [1002, 3]]
testFun(testVal[0], testVal[1])
Out[191]:
Extracting just the first term is why the whole thing ended with [0] in the original code:
n = reduce(lambda x,y:[x[0]*(10**(y[1]+1))+y[0],0],map(lambda x:[x,int(math.log(x,10))], listofints))[0]
The original code:
In [79]:
listofints = [1,2,3,9,10,11,12,19,99,100,101,102, 999, 1000, 1001, 50102030]
n = reduce(lambda x,y:x*(10**(int(math.log10(y))+1))+y,listofints)
print(n)
When the code is simplified to just use use reduce(), now only one lambda function is able to set up the power-of-tens calculation for each number and merge it all into terms needed for reduce(). Picking it apart from the inside, just the lambda logic is demonstrated here:
In [77]:
# for comparison, here is the lambda logic split in two functions from the earlier example
testFun_r = lambda x,y:[x[0]*(10**(y[1]+1))+y[0],0] # used in outer () to feed into reduce()
testFun_m = lambda x:[x,int(math.log10(x))] # used in inner () to feed into map()
# for this idea, only one lambda does it all, feeding directly into reduce():
testFun2 = lambda x,y:x*(10**(int(math.log10(y))+1))+y
# test it:
testVal = [999, 1001]
testFun2(testVal[0], testVal[1])
Out[77]:
In [81]:
# now reduce() applies it across the whole original list: function(n1, n2) = result1, function(result1, n3) = result2 ...
# until it produces a final answer to return ("reducing the list down to one number").
listofints = [1,2,3,10,12,19,99,100,101,50102030]
n = reduce(lambda x,y:x*(10**(int(math.log10(y))+1))+y,listofints)
print(n)
In [110]:
1*10**(int(math.log10(2))+1)+2
Out[110]:
After exploring different options, if we are to preserve all the functionality but lose the loops, a solution is chosen that combines reduce() with list comprehensions. Some notes on this solution:
listofints used in the quick solutions aboveshowWork now shows what reduce is fusing together to form the final outputN or listofints it tests the input argument for type. This is not considered good practice, but is kept here to illustrate how to do it. Coding sites generally recommend code be refactored to avoid using type testing within its operation.
In [263]:
# this function presented and tested in earlier sections
# repeated here (unchanged) for conveninece:
import math # needed for log functions
def powOfTens(N): # find the powers of 10 inside a number
if N < 1:
N = 1 # less than 1 would throw an error, this is a work-around based on
# how this function is used in the code
return int(math.log10(N)) # converts decimal to whole integer
# int() rounds down no matter how big the decimal
# note: math.log(x, 10) produces floating point rounding errors
In [269]:
from __future__ import print_function
def create_seqNumber(N, reverse=False, showWork=False, returnDescr=False, divLength=100):
'''create_seqNumber() --> iput N, and get back a number built from the sequence of 1234...N
Arguments: reverse=True to get the sequence in revers, showWork=True to see numbers that add up to final,
returnDescr=True to print the answer in a sentence as well as returning it as a number.'''
num = 0
tensIncr = 0
answer = 0
if isinstance(N, list):
if reverse == False:
listofints = N
else:
listofints = N[::-1]
elif isinstance(N, int):
Ntens = powOfTens(N)
if reverse == False: # create range builder inputs
rstart = 1
rend = N+1
rinc = 1
else:
rstart = N
rend = 0
rinc = -1
listofints = range(rstart, rend, rinc)
else:
print(type(N))
raise TypeError("Error: for create_seqNumber(N), N must be a list or an integer.")
answer = reduce(lambda x,y:x*(10**(powOfTens(y)+1))+y,listofints)
if showWork == True:
print("Show Work:")
print("#"*divLength)
worklist = [reduce(lambda x,y:x*(10**(powOfTens(y)+1))+y, listofints[0:2])]
worklist.append([reduce(lambda a,b:a*(10**(powOfTens(b)+1))+b, [worklist[-1], x])
for ind, x in enumerate(listofints[2:])])
worklist = [worklist[0]] + worklist[1]
# print("worklist: %s" %worklist)
# print("worklist[-1]", worklist[-1])
NpOfT = powOfTens(worklist[-1])
NpOfT2 = powOfTens(len(worklist)-1)
[(x, print(("%d)" + " "*(NpOfT2 - powOfTens(ind)) + " "*(NpOfT - powOfTens(x) + 1) + "%s") %(ind, x)))[0]
for ind, x in enumerate(worklist)]
print("#"*divLength)
if showWork == True or returnDescr == True:
print("Answer: %d" %answer)
print("#"*divLength)
return answer
In [279]:
create_seqNumber(15, showWork=False, returnDescr=True)
Out[279]:
In [214]:
create_seqNumber(15, reverse=True, showWork=False, returnDescr=True)
Out[214]:
In [215]:
create_seqNumber(102, reverse=False, showWork=False, returnDescr=True)
Out[215]:
In [216]:
for i in [1, 5, 9, 10, 11, 13, 98, 99, 100, 101, 102, 107, 1012]: # returnDescr = False by default
print("F: %s" %(create_seqNumber(i, reverse=False)))
print("-----"*25)
print("R: %s" %(create_seqNumber(i, reverse=True)))
print("#####"*25)
In [217]:
tstLst = [1,2,3,9,10,11,12,59,99,100,101,50102030]
print("F: %s" %(create_seqNumber(tstLst, reverse=False)))
print("-----"*25)
print("R: %s" %(create_seqNumber(tstLst, reverse=True)))
print("#####"*25)
In [277]:
create_seqNumber(3, reverse=False, showWork=True, returnDescr=True)
Out[277]:
In [278]:
create_seqNumber(13, reverse=True, showWork=True, returnDescr=True)
Out[278]:
In [276]:
tstLst = [1,2,3,9,10,11,12,59,99,100,101,50102030]
create_seqNumber(tstLst, reverse=False, showWork=True, returnDescr=True)
Out[276]:
In [272]:
create_seqNumber(1003, reverse=False, showWork=True, returnDescr=True)
Out[272]:
In [280]:
create_seqNumber('15', showWork=False, returnDescr=True) # demo of TypeError the code raises for wrong input
For more information on the python functions explored here:
In [ ]:
In [ ]: