Tuesday, January 29, 2019

Daily Coding Problem #69: A functional programming solution


- By Vasudev Ram - Online Python training / SQL training / Linux training




Stock reduction image attribution

Hi, readers,

I subscribed to the mailing list of the Daily Coding Problem site site a while ago. It's a useful site. Their modus operandi is to send you one programming problem per day, described in English. You try to solve them, in any programming language of your choice. (They say that some of the questions were asked by companies like Google, Facebook, Amazon, Microsoft, Netflix, etc.) Something like Rosetta Code.
The idea is that you can use this to practice and improve your programming and algorithm development skills.

I haven't been attempting to solve every problem I get in email from them, as of now. I just try one now and then. Hope to attempt more later.

Daily Coding Problem #69 is one that I tried, and solved, using a functional programming approach.

This is the problem statement (taken from the email I got from them):

Daily Coding Problem: Problem #69
To: vasudevram@gmail.com
Good morning! Here's your coding interview problem for today.

This problem was asked by Facebook.

Given a list of integers, return the largest product that can be made by multiplying any three integers.

For example, if the list is [-10, -10, 5, 2], we should return 500, since that's -10 * -10 * 5.

You can assume the list has at least three integers.

And here is my functional-style solution below (actually, two variants on a solution). For this post, I've used a slightly different format than what I usually use - instead of alternating code and (text) explanations, I've put all the explanations in the code, as comments - sort of like literate programming.
# daily_coding_problem_069.py
# Problem source: https://dailycodingproblem.com
# Solution created by Vasudev Ram
# Website: https://vasudevram.github.io
# Copyright 2019 Vasudev Ram
# Blog: https://jugad2.blogspot.com
# Python posts: https://jugad2.blogspot.com/search/label/python
# Product store: https://gumroad.com/vasudevram
# Twitter: https://mobile.twitter.com/vasudevram
# LinkedIn: https://linkedin.com/in.vasudevram

"""
Daily Coding Problem: Problem #69

This problem was asked by Facebook.

Given a list of integers, return the largest product that can be made 
by multiplying any three integers.

For example, if the list is [-10, -10, 5, 2], we should return 500, 
since that's -10 * -10 * 5.

You can assume the list has at least three integers.
"""

from __future__ import print_function

try:
    reduce
except NameError as ne:
    from functools import reduce

from itertools import combinations

# Create a list with a few numbers.
lis = range(1, 6)
print()
print("lis:", lis)

# First, print the combinations iterator object.
print("combinations(lis, 3):", combinations(lis, 3))
# Next, print the combinations themselves.
print("list(combinations(lis, 3)):\n" + \
    "\n".join(str(item) for item in list(combinations(lis, 3))))
print()

# Then define a function that takes an iterable and returns 
# the product of all the numbers in it.
def product(iterable):
    p = 1
    for i in iterable:
        p *= i
    return p

# Test the product function a few times:
print("product(range(10)):", product(range(10)))
print("product(range(1, 11)):", product(range(1, 11)))
print("product(range(1, 6, 2)):", product(range(1, 6, 2)))
print("product(range(1, 10, 2)):", product(range(1, 10, 2)))
print()

# Now use the product function with the combinations function 
# to solve Daily Coding Problem #69:
print("max(map(product, combinations(lis, 3)):", \
    max(map(product, combinations(lis, 3))))

# Now let's solve the same problem with reduce and operator.mul 
# instead of the product function above:

# Here is the docstring for reduce:
print("reduce.__doc__:", reduce.__doc__)
print

from operator import mul

# Here is the docstring for mul:
print("operator.mul.__doc__:", mul.__doc__)
print()

# Show how reduce works with mul with a few examples:
print("reduce(mul, range(1, 5)):", reduce(mul, range(1, 5)))
print("reduce(mul, range(3, 7)):", reduce(mul, range(3, 7)))
print()

# Use reduce-with-mul instead of product.
print("max(map(lambda s: reduce(mul, s), combinations(lis, 3))):", \
    max(map(lambda s: reduce(mul, s), combinations(lis, 3))))

# Here's the call using product again for comparison:
print("max(map(product, combinations(lis, 3))):", \
    max(map(product, combinations(lis, 3))))
print()

# A few more calls to the reduce-with-mul version:
lis4 = range(1, 5)
print("lis4:", lis4)
print("max(map(lambda s: reduce(mul, s), combinations(lis4, 3))):", \
    max(map(lambda s: reduce(mul, s), combinations(lis4, 3))))
print()

lis6 = range(1, 7)
print("lis6:", lis6)
print("max(map(lambda s: reduce(mul, s), combinations(lis6, 3))):", \
    max(map(lambda s: reduce(mul, s), combinations(lis6, 3))))
print()

lis7 = range(1, 8)
print("lis7:", lis7)
print("max(map(lambda s: reduce(mul, s), combinations(lis7, 3))):", \
    max(map(lambda s: reduce(mul, s), combinations(lis7, 3))))
print()

# And finally, here is the solution run again with the example 
# input given in the Facebook problem mentioned above:

lis_fb = [-10, -10, 5, 2]
print("lis_fb:", lis_fb)
print("max(map(lambda s: reduce(mul, s), combinations(lis_fb, 3))):", \
    max(map(lambda s: reduce(mul, s), combinations(lis_fb, 3))))
print()

# The result matches the given answer, 500.

# Now let's modify the Faceboook input and run the code again:
lis_fb2 = [-10, 8, -10, 9, 5, 7, 2]
# (Added values 8, 9 and 7 to the list.)
print("lis_fb2:", lis_fb2)
print("max(map(lambda s: reduce(mul, s), combinations(lis_fb2, 3))):", \
    max(map(lambda s: reduce(mul, s), combinations(lis_fb2, 3))))
print()

# The result is right again, since -10 * -10 * 9 = 900 is 
# the largest product.

Here is the output of a run of the program using Python 3:
lis: range(1, 6)
combinations(lis, 3): <itertools.combinations object at 0x0000000001DA9598>
list(combinations(lis, 3)):
(1, 2, 3)
(1, 2, 4)
(1, 2, 5)
(1, 3, 4)
(1, 3, 5)
(1, 4, 5)
(2, 3, 4)
(2, 3, 5)
(2, 4, 5)
(3, 4, 5)

product(range(10)): 0
product(range(1, 11)): 3628800
product(range(1, 6, 2)): 15
product(range(1, 10, 2)): 945

max(map(product, combinations(lis, 3)): 60
reduce.__doc__: reduce(function, sequence[, initial]) -> value

Apply a function of two arguments cumulatively to the items of a sequence,
from left to right, so as to reduce the sequence to a single value.
For example, reduce(lambda x, y: x+y, [1, 2, 3, 4, 5]) calculates
((((1+2)+3)+4)+5).  If initial is present, it is placed before the items
of the sequence in the calculation, and serves as a default when the
sequence is empty.
operator.mul.__doc__: Same as a * b.

reduce(mul, range(1, 5)): 24
reduce(mul, range(3, 7)): 360

max(map(lambda s: reduce(mul, s), combinations(lis, 3))): 60
max(map(product, combinations(lis, 3))): 60

lis4: range(1, 5)
max(map(lambda s: reduce(mul, s), combinations(lis4, 3))): 24

lis6: range(1, 7)
max(map(lambda s: reduce(mul, s), combinations(lis6, 3))): 120

lis7: range(1, 8)
max(map(lambda s: reduce(mul, s), combinations(lis7, 3))): 210

lis_fb: [-10, -10, 5, 2]
max(map(lambda s: reduce(mul, s), combinations(lis_fb, 3))): 500

lis_fb2: [-10, 8, -10, 9, 5, 7, 2]
max(map(lambda s: reduce(mul, s), combinations(lis_fb2, 3))): 900

I also tested it with Python 2 and it gave basically the same output, 
maybe with the exception of some minor message differences between 2 and 3.
So I'm not showing the 2 output here.

The image at the top of the post is of stock with bay leaf and thyme being reduced in a pan.
Here is the Wikipedia article about reduction in cooking.

The functional programming meaning of reduce sort of matches the cooking meaning, right? Heh.

Enjoy.


- Vasudev Ram - Online Python training and consulting

I conduct online courses on Python programming, Unix / Linux commands and shell scripting and SQL programming and database design, with course material and personal coaching sessions.

The course details and testimonials are here.

Contact me for details of course content, terms and schedule.

Try FreshBooks: Create and send professional looking invoices in less than 30 seconds.

Getting a new web site or blog, and want to help preserve the environment at the same time? Check out GreenGeeks.com web hosting.

Sell your digital products via DPD: Digital Publishing for Ebooks and Downloads.

Learning Linux? Hit the ground running with my vi quickstart tutorial. I wrote it at the request of two Windows system administrator friends who were given additional charge of some Unix systems. They later told me that it helped them to quickly start using vi to edit text files on Unix. Of course, vi/vim is one of the most ubiquitous text editors around, and works on most other common operating systems and on some uncommon ones too, so the knowledge of how to use it will carry over to those systems too.

Check out WP Engine, powerful WordPress hosting.

Sell More Digital Products With SendOwl.

Get a fast web site with A2 Hosting.

Creating online products for sale? Check out ConvertKit, email marketing for online creators.

Teachable: feature-packed course creation platform, with unlimited video, courses and students.

Posts about: Python * DLang * xtopdf

My ActiveState Code recipes

Follow me on:


No comments: