In [1]:
# you can mix text and code in one place and
# run code from a Web browser
All you need to know about Python is here:
You don't need to specify type of a variable
In [2]:
a = 10
In [3]:
a
Out[3]:
You can assign several variables at once:
In [4]:
a, b = 1, 2
a, b
Out[4]:
In [5]:
b, a = a, b
a, b
Out[5]:
There is no "begin-end"! You use indentation to specify blocks. Here is simple IF statement:
In [6]:
if a > b:
print("A is greater than B")
else:
print("B is greater than A")
In [7]:
# Integer
a = 1
print(a)
# Float
b = 1.0
print(b)
# String
c = "Hello world"
print(c)
# Unicode
d = u"Привет, мир!"
print(d)
# List (array)
e = [1, 2, 3]
print(e[2]) # 3
# Tuple (constant array)
f = (1, 2, 3)
print(f[0]) # 1
# Set
g = {1, 1, 1, 2}
print(g)
# Dictionary (hash table, hash map)
g = {1: 'One', 2: 'Two', 3: 'Three'}
print(g[1]) # 'One'
In [8]:
for i in range(10):
print(i)
In [9]:
i = 0
while i < 10:
print(i)
i += 1
In [10]:
items = ['apple', 'banana', 'stawberry', 'watermelon']
for item in items:
print(item)
In [11]:
for i, item in enumerate(items):
print(i, item)
In [12]:
# Variable name
my_variable = 1
# Class method and function names
def my_function():
pass
# Constants
MY_CONSTANT = 1
# Class name
class MyClass(object):
# 'private' variable - use underscore before a name
_my_variable = 1
# 'protected' variable - use two underscores before a name
__my_variable = 1
# magic methods
def __init__(self):
self._another_my_variable = 1
PEP 8 quote:
In Python, single-quoted strings and double-quoted strings are the same. PEP 8 does not make a recommendation for this. Pick a rule and stick to it. When a string contains single or double quote characters, however, use the other one to avoid backslashes in the string. It improves readability.
For triple-quoted strings, always use double quote characters to be consistent with the docstring convention in PEP 257.
My rule for single-quoted and double-quoted strings is:
In [13]:
'string'
"another string"
"""Multiline
string"""
'''
Another
multiline
string
'''
Out[13]:
Sum all elements in an array is straightforward:
In [14]:
sum([1,2,3,4,5])
Out[14]:
However, there is no built-in function for multiplication:
In [15]:
mult([1,2,3,4,5])
, so we have to write our solution. Let's start with straightforward one:
In [16]:
def mult(array):
result = 1
for item in array:
result *= item
return result
In [17]:
mult([1,2,3,4,5])
Out[17]:
There is another way to implement it. It is to write it in a functional-programming style:
In [18]:
from functools import reduce
def mult_functional(array):
return reduce(lambda prev_result, current_item: prev_result * current_item, array, 1)
In [19]:
mult_functional([1,2,3,4,5])
Out[19]:
In [20]:
%timeit mult(range(1, 1000))
%timeit mult_functional(range(1, 1000))
Let's look at a simple problem (https://projecteuler.net/problem=5):
2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.
What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?
In [21]:
def get_smallest_divisor_in_range(N):
"""
Brute force all numbers from 2 to 1*2*3*4*5*6*...*N
until we get a number, which divides by all numbers
in a range of [1, N].
Example:
>>> get_smallest_devisor_in_range(10)
2520
"""
range_multiplied = mult(range(2, N+1))
for x in range(2, range_multiplied, 2):
for divisor in range(3, N+1):
if x % divisor:
break
else:
break
return x
In [22]:
%time print(get_smallest_divisor_in_range(10))
%time print(get_smallest_divisor_in_range(20))
It is to count LCM (Least common multiple) of all numbers in a range of [1, N]:
$[a,b]=p_1^{\max(d_1,e_1)}\cdot\dots\cdot p_k^{\max(d_k,e_k)}.$
For example:
$8\; \, \; \,= 2^3 \cdot 3^0 \cdot 5^0 \cdot 7^0 \,\!$
$9\; \, \; \,= 2^0 \cdot 3^2 \cdot 5^0 \cdot 7^0 \,\!$
$21\; \,= 2^0 \cdot 3^1 \cdot 5^0 \cdot 7^1. \,\!$
$\operatorname{lcm}(8,9,21) = 2^3 \cdot 3^2 \cdot 5^0 \cdot 7^1 = 8 \cdot 9 \cdot 1 \cdot 7 = 504. \,\!$
In [23]:
def get_smallest_divisor_in_range_fast(N):
"""
Optimal solution for the problem is to count
LCM (Least common multiple) of all numbers in
a range of [1, N].
"""
prime_divisors = {}
# Loop from 2 to N.
for x in range(2, N+1):
# Find and save all prime divisors of `x`.
for divisor in range(2, int(x**0.5) + 1):
power = 0
# Find the power of the `divisor` in `x`.
while x % divisor == 0:
x /= divisor
power += 1
if power > 0:
# Save the `divisor` with the greatest power into our `prime_divisors` dict (hash-map).
if divisor in prime_divisors:
if prime_divisors[divisor] < power:
prime_divisors[divisor] = power
else:
prime_divisors[divisor] = power
# Stop searching more divisors if `x` is already equals to `1` (all divisors are already found).
if x == 1:
break
else:
# If `x` is prime, we won't find any divisors and
# the above `for` loop will be over without hitting `break`,
# thus we just need to save `x` as prime_divisor in power of 1.
prime_divisors[x] = 1
# Having all prime divisors in their lowest powers we multiply all of them to get the answer.
least_common_multiple = 1
for divisor, power in prime_divisors.items():
least_common_multiple *= divisor ** power
return least_common_multiple
In [24]:
%time print(get_smallest_divisor_in_range_fast(10))
%time print(get_smallest_divisor_in_range_fast(20))
In [25]:
%time print(get_smallest_divisor_in_range_fast(10000))
In [26]:
try:
from math import gcd
except ImportError: # Python 2.x has `gcd` in `fractions` module instead of `math`
from fractions import gcd
def get_smallest_divisor_in_range_fastest(N):
least_common_multiple = 1
for x in range(2, N + 1):
least_common_multiple = (least_common_multiple * x) // gcd(least_common_multiple, x)
return least_common_multiple
In [27]:
%time print(get_smallest_divisor_in_range_fastest(10))
%time print(get_smallest_divisor_in_range_fastest(20))
In [28]:
%time print(get_smallest_divisor_in_range_fastest(10000))
In [ ]:
import math
math?