Python Exercises: Solutions

#!/usr/bin/python3

print('ciao!')

#!/usr/bin/python3
#
# This program reads a sequence of numbers from the standard input,
# with one or more numbers per line, and prints the minimum and the
# maximum values in the list.
# 
import sys

A = []
for line in sys.stdin:
    for a in line.split():
        A.append(int(a))

minimum = None
maximum = None
for a in A:
    if minimum == None or minimum > a:
        minimum = a
    if maximum == None or maximum < a:
        maximum = a

print('min =',minimum)
print('max =',maximum)

#!/usr/bin/python3
#
# This program reads a line from the standard input, and outputs that
# line flipped right-to-left.
#
l = input()
i = len(l)
while i > 0:
    i = i - 1
    print(l[i], end='')
print()

#!/usr/bin/python3
#
# A program that takes an integer N > 0 as a command-line parameter,
# and prints the values of \pi(i) for all i <= N, where \pi(k) is the
# number of prime numbers between 1 and k
#
import sys

def pi(n):
    # we implement the sieve of Eratosthenes
    #
    S = [True]*(n + 1)
    S[0] = False
    S[1] = False
    p = 2
    while p * p <= n:
        if S[p]:
            i = p * p
            while i <= n:
                S[i] = False
                i = i + p
        p = p + 1

    count = 0
    i = 1
    while i <= n:
        if S[i]:
            count = count + 1
        print (i, count)
        i = i + 1

try:
    pi(int(sys.argv[1]))
except:
    print('usage:', sys.argv[0], '<n>')

#!/usr/bin/python3
#
# This program reads a list of numbers from the standard input, with
# one number per line, and prints a histogram corresponding to those
# numbers.  In this histogram, each number N is represented by a
# line of N characters "#"
# 
import sys

if len(sys.argv) > 1:
    file = open(sys.argv[1], 'r')
else:
    file = sys.stdin

for line in file:
    for i in range(int(line)):
        sys.stdout.write('#')
    sys.stdout.write('\n')

#!/usr/bin/python3
#
# This program reads a list of numbers from the standard input, with
# one or more numbers per line, and prints a vertical histogram
# corresponding to those numbers.  In this histogram, each number N is
# represented by a column of N characters "#" starting from a
# base-line of N dash characters "-" representing value 0.  Positive
# numbers are represented by a column above zero while negative
# numbers are represented with a column below zero.
# 
def v_histogram(A):
    top = 0
    bottom = 0
    for a in A:
        if a > top:
            top = a
        elif a < bottom:
            bottom = a

    i = top
    while i > 0:
        for a in A:
            if a >= i:
                print('#',end='')
            else:
                print(' ',end='')
        print()
        i = i - 1

    for a in A:
        print('-',end='')
    print()
    while i > bottom:
        i = i - 1
        for a in A:
            if a <= i:
                print('#',end='')
            else:
                print(' ',end='')
        print()

import sys
X = []
f = open(sys.argv[1])
for l in f:
    for n in l.split():
        X.append(int(n))

v_histogram(X)

# The general idea is to scan the given sequence $A$ looking for
# subsequences of identical consecutive elements.  If the subsequence
# consists of one or two elements, then we simply print those element
# one by one, otherwise we print the element followed by the count.  We
# can do this with a linear scan of $A$.

# Tactically, we can proceed in a number of ways.  One simple and quite
# elegant way of doing that is to use two position indexes, $i$ and $j$,
# with $i<j$, where position $i$ indicates the /first/ element of the
# sequence, and $j$ indicates the last element.  In fact, it is even
# more convenient to use $j$ to indicate the the first element /past/
# the sequence, meaning the first element that differs from the elements
# of the sequence and therefore that terminates the sequence.

# Notice that $j$ can be the position of an element, or it can be the
# first position past the last element of the whole sequence.

def compress(A):
    i = 0
    while i < len(A):
        j = i + 1
        while j < len(A) and A[j] == A[i]:
            j = j + 1
        if j - i <= 2:
            for _ in range(j - i):
                print(A[i])
        else:
            print(A[i],'*',j - i)
        i = j

import sys
A = []
for l in sys.stdin:
    for a in l.strip().split():
        A.append(a)

compress(A)

#!/usr/bin/python3

import sys

A = []
for l in sys.stdin:
    for a in l.split():
        A.append(int(a))

if len(A) >= 1:
    i = 0
    j = 1
    best = A[0]
    best_len = 1
    while j < len(A):
        if A[i] != A[j]:
            i = j            
        j = j + 1
        if j - i > best_len:
            best = A[i]
            best_len = j - i

    print(best)

#!/usr/bin/python3
#
#  This program reads a text file from the standard input, and prints
#  the most common word in the input.  The words in the input are the
#  maximal-length sequences of alphabetic characters (e.g., a-z).  So,
#  a word does not include spaces or punctuation characters.
#
import sys

def line_to_words(line):
    words = []
    w = ''

    for c in line:
        if c.isalpha():
            w += c
        else:
            if not w == '':
                words.append(w)
                w = ''
    if not w == '':
        words.append(w)

    return words

D = {}

for l in sys.stdin:
    for w in line_to_words(l):
        if w in D:
            D[w] += 1
        else:
            D[w] = 1

most_common = None
max_freq = 0
for w in D:
    if D[w] > max_freq:
        most_common = w
        max_freq = D[w]

print(most_common)

#!/usr/bin/python3
#
# This program reads a text file from the standard input, and prints
# the list of all characters present in the input followed by the
# number of times the character appears in the input.
#
import sys

freq = {}
for line in sys.stdin:
    for c in line:
        if c in freq:
            freq[c] = freq[c] + 1
        else:
            freq[c] = 1

for c, f in freq.items():
    print(c, f)

#!/usr/bin/python3
#
# This program reads a text file from the standard input, and prints
# the list of all characters present in the input followed by the
# number of times the character appears in the input.  The output is
# sorted in reverse order of frequency, from the highest to the lowest
# frequency count.
#
import sys

freq = {}
for line in sys.stdin:
    for c in line:
        if c in freq:
            freq[c] = freq[c] + 1
        else:
            freq[c] = 1

sorted_freq = list(freq.items())
for i in range(1,len(sorted_freq)):
    j = i
    while j > 0 and sorted_freq[j][1] > sorted_freq[j-1][1]:
        sorted_freq[j], sorted_freq[j-1] = sorted_freq[j-1], sorted_freq[j]
        j = j - 1

for c, f in sorted_freq:
    print(c, f)

#!/usr/bin/python3
#
# This program reads a text file from the standard input and prints
# the list of all the words in the text file, each followed by the
# number of times the word occurs in the text.  Words in the input are
# the maximal-length sequences of alphabetic characters (e.g., a-z).
# So, a word does not include spaces or punctuation characters.
#
import sys
import string

def line_to_words(line):
    words = []
    w = ''

    for c in line:
        if c.isalpha():
            w += c
        else:
            if not w == '':
                words.append(w)
                w = ''
    if not w == '':
        words.append(w)

    return words

freqs = {}
for line in sys.stdin:
    for word in line_to_words(line):
        if word in freqs:
            freqs[word] = freqs[word] + 1
        else:
            freqs[word] = 1

for c, f in freqs.items():
    print(c, f)

#!/usr/bin/python3
#
# A program that reads a list of words from the standard input, with
# one word per line, and prints any one of the shortest words that
# appear least often.
#
import sys

D = {}

for w in sys.stdin:
    w = w.strip()
    if w in D:
        D[w] += 1
    else:
        D[w] = 1

min_v = None
min_len_w = None
for k,v in D.items():
    if min_v == None:
        min_v = v
        min_len_w = k
    elif v < min_v:
        min_v = v
        min_len_w = k
    elif v == min_v and len(k) < len(min_len_w):
        min_len_w = k

print(min_len_w)

#!/usr/bin/python3
#
# this program reads a list of numbers from the standard input, with
# one or more numbers per line separated by spaces on each line, and
# prints the largest cluster of extension D.  The parameter D is a
# number that may be given as the first command-line argument.  If the
# parameter is not specified, the default value is D=10.  A cluster of
# extension D is a list of all the elements taken from the input list
# that are within a distance of at most D from each other.  For
# example, if the input sequence is 12, 2, 34, 7, 21, 24, 50, 45, -9,
# 7, 45, and if D=10, then the output should contain the numbers 12,
# 2, 7, 7 because those numbers form a cluster of extension 10, and no
# other cluster of extension 10 contains more than 4 elements.
# 
import sys

A = []
for l in sys.stdin:
    for n in l.split(' '):
        A.append(int(n.strip()))

try:
    D = int(sys.argv[1])
except:
    D = 10

max_c = []
for a in A:
    c = []
    for b in A:
        if b >= a and b - a <= D:
            c.append(b)
    if len(c) > len(max_c):
        max_c = c

for x in max_c:
    print(x, end=' ')
print()

#!/usr/bin/python3 
#
# 
import sys

def count_inversions_trivial(A):
    x = 0
    for i in range(1,len(A)):
        for j in range(i):
            if A[j] > A[i]:
                x += 1
    return x

def count_inversions(A):
    if len(A) < 2:
        return 0

    m = len(A)//2
    Aleft = A[:m]               # O(n)
    Aright = A[m:]              # O(n)
    count = count_inversions(Aleft) + count_inversions(Aright)
    i = 0
    j = 0
    k = 0
    while i < len(Aleft) or j < len(Aright):
        if i >= len(Aleft) or (j < len(Aright) and Aright[j] < Aleft[i]):
            A[k] = Aright[j]
            j += 1
            k += 1
            count += len(Aleft)-i
        else:
            A[k] = Aleft[i]
            i += 1
            k += 1

    return count

A = []
for l in sys.stdin:
    for n in l.split():
        A.append(int(n))

print(count_inversions(A))

#!/usr/bin/python3
#
# This program that takes a number N (a positive integer) in decimal
# notation from the console, and prints its value as a roman numeral.
#
ten_zero = ['', 'I', 'II', 'III', 'IV', 'V', 'VI', 'VII', 'VIII', 'IX']
ten_one = ['', 'X', 'XX', 'XXX', 'XL', 'L', 'LX', 'LXX', 'LXXX', 'XC']
ten_two = ['', 'C', 'CC', 'CCC', 'CD', 'D', 'DC', 'DCC', 'DCCC', 'CM']

n = int(input('input a number: '))

r = ''
while n >= 1000:
    r = r + 'M'
    n = n - 1000

c = n // 100
r = r + ten_two[c]
n = n - c*100

d = n // 10
r = r + ten_one[d]
n = n - d*10

r = r + ten_zero[n]

print(r)

#!/usr/bin/python3

import sys

if len(sys.argv) > 1:
    n = int(sys.argv[1])
else:
    n = int(input('give me a number: '))

i = 2
while i * i <= n:
    if n % i == 0:
        c = 1
        n = n // i
        while n % i == 0:
            c += 1
            n = n // i
        if c > 1:
            sys.stdout.write(str(i) + '^' + str(c) + ' ')
        else:
            sys.stdout.write(str(i) + ' ')
    i += 1

if n > 1:
    sys.stdout.write(str(n))
sys.stdout.write('\n')

#!/usr/bin/python3
#
import sys

# checks whether V contains a permutation of the integers between 1
# and 9.  For example, V = [ 3, 2, 1, 4, 5, 6, 9, 8, 7 ] => True but
# V = [ 3, 2, 1, 4, 5, 6, 9, 2, 7 ] => False
def perm9(V):
    F = [ 0, 0, 0, 0, 0, 0, 0, 0, 0 ]
    for x in V:
        if x < 1 or x > 9 or F[x-1] != 0:
            return False
        else:
            F[x-1] = 1

    for x in F:
        if x == 0:
            return False

    return True

# returns a list of the elements of the 3-by-3 submatrix of S whose
# upper-left corner is at position (x,y) within S 
def submatrix(S, x, y):
    return S[x][y:y+3] + S[x+1][y:y+3] + S[x+2][y:y+3]

# returns the column at position X within S 
def column(S, x):
    c = []
    for row in S:
        c.append(row[x])
    return c

def row(S, x):
    return S[x]

S = []
for line in sys.stdin:
    l = []
    for x in line.split():
        l.append(int(x))
    S.append(l)

for i in range(9):
    if not perm9(row(S,i)):
        print("Wrong")
        print("row", i)
        sys.exit(1)

for i in range(9):
    if not perm9(column(S,i)):
        print("Wrong")
        print("column", i)
        sys.exit(1)

for i in range(0,9,3):
    for j in range(0,9,3):
        if not perm9(submatrix(S,i,j)):
            print("Wrong")
            print("submatrix", i, j)
            sys.exit(1)

print("Correct")

#!/usr/bin/python3

# this program takes a number N as a command-line parameter and 
# prints all the *partitions* of N
#
# a partition of a positive number N is a set of positive numbers that
# add up to N.  For example, { 3, 2, 2 } is a partition of 7.
# Also, for example, all the partitions of N=4 are:
#
# 4
# 3 1
# 2 2
# 2 1 1
# 1 1 1 1

#
# P contains a lists of numbers and represents a previously computed
# partition, say of a number X. n is the value of which we want to
# find all partitions.  For each one of these partitions Q, the
# function partition() adds Q to P and prints the list, that is, a
# partition of n+X.
#
# The key idea to partition n is to compose a non-increasing list of
# numbers, which is intended to avoid repeating the same partition.
#
# Thus partition(n, limit, P) partitions n in parts that are not
# greater than limit.
#
def partition(n, limit, P):
    # ASSERT(n >= limit)
    while limit > 0:
        P.append(limit)
        remainder = n - limit
        if remainder > limit:
            partition(remainder, limit, P)
        else:
            if remainder == 0:
                for n in P:
                    print(n,end=' ')
                print()
            else:
                partition(remainder, remainder, P)
        del P[-1]
        limit -= 1

import sys

if len(sys.argv) != 2:
    sys.stderr.write('usage: ' + sys.argv[0] + ' <num>\n')
    exit(1)

N = int(sys.argv[1])

partition(N, N, [])

#!/usr/bin/python3

import random

initial_position =  [ ' 1', ' 2', ' 3', ' 4',
                      ' 5', ' 6', ' 7', ' 8',
                      ' 9', '10', '11', '12', 
                      '13', '14', '15', '  ' ]

def display(cells):
    for i in range(0,16):
        if i % 4 == 0:
            print('+--+--+--+--+')
            print('|' + cells[i] + '|' + cells[i+1] + '|' + cells[i+2] + '|' + cells[i+3] + '|')
    print('+--+--+--+--+')

def find(cells, s):
    for i in range(0, 16):
        if cells[i].strip() == s.strip():
            return i
    return -1

def nsew_pos(pos):
    res = []
    x = pos % 4
    y = pos // 4
    if x > 0:
        res.append(pos - 1)
    if x < 3:
        res.append(pos + 1)
    if y > 0:
        res.append(pos - 4)
    if y < 3:
        res.append(pos + 4)
    return res

def equal_to_initial_position(cells):
    for i in range(0, 16):
        if cells[i] != initial_position[i]:
            return False
    return True

def switch(cells, pos):
    x = find(cells,pos)
    if x < 0:
        print('invalid cell')
    else:
        y = find(cells,'  ')
        if y in nsew_pos(x):
            cells[x], cells[y] = cells[y], cells[x]

cells = []                      # initialize the state of the game
cells += initial_position
random.shuffle(cells)           # shuffle
while not equal_to_initial_position(cells):
    display(cells)
    pos = input('switch? ')
    switch(cells,pos)

#!/usr/bin/python3

import sys
import random

RootPrefix="•"
Vertical="│"
LeafWithOther="├"
SingleLeaf="└"
WithChildren="┬"
WithoutChildren="─"

class Node:
    def __init__(self, name):
        self.name = name
        self.parent = None
        self.children = set()

    def set_parent(self, parent):
        if self.parent != None:
            self.parent.children.remove(self)
        self.parent = parent
        self.parent.children.add(self)

    def print_indentation(self, prefix):
        sys.stdout.write(prefix + self.name + '\n')
        for c in self.children:
            c.print_indentation(prefix + '  ')

    def print_simple(self, prefix):
        sys.stdout.write(prefix[0:-1] + '+-' + self.name + '\n')
        l = list(self.children)
        for i in range(0, len(l)):
            if i < len(l) - 1:
                l[i].print_simple(prefix + ' |')
            else:
                l[i].print_simple(prefix + '  ')

    def print_pretty(self, prefix, prefix2):
        l = list(self.children)
        if len(l) == 0:
            sys.stdout.write(prefix + prefix2 + WithoutChildren + self.name + '\n')
        else:
            sys.stdout.write(prefix + prefix2 + WithChildren + self.name + '\n')

        if prefix2 == LeafWithOther:
            new_prefix = prefix + Vertical 
        else:
            new_prefix = prefix + ' '
        for i in range(0, len(l)-1):
            l[i].print_pretty(new_prefix, LeafWithOther)
        if (len(l) > 0):
            l[-1].print_pretty(new_prefix, SingleLeaf)

    def print_tree(self, format):
        if format == 'indentation':
            self.print_indentation('')
        elif format == 'simple':
            self.print_simple('')
        else:
            self.print_pretty('', RootPrefix)

def read_tree_from_child_parent_list():
    nodes = {}
    roots = Node("")
    for line in sys.stdin:
        child_name, parent_name = line.split()
        if parent_name not in nodes:
            parent = Node(parent_name)
            nodes[parent_name] = parent
            parent.set_parent(roots)
        else:
            parent = nodes[parent_name]

        if child_name not in nodes:
            child = Node(child_name)
            nodes[child_name] = child
        else:
            child = nodes[child_name]

        child.set_parent(parent)
    return roots

def read_file_system_tree():
    nodes = {}
    roots = Node("")
    for child_name in sys.stdin:
        child_name = child_name.rstrip('\n')
        parent_name, separator, basename = child_name.rpartition('/')

#        print(child_name + '(' + basename + ') -> ' + parent_name)

        if parent_name not in nodes:
            parent_basename = parent_name.rpartition('/')[2]
            parent = Node(parent_basename)
            nodes[parent_name] = parent
            parent.set_parent(roots)
        else:
            parent = nodes[parent_name]

        if child_name not in nodes:
            child = Node(basename)
            nodes[child_name] = child
        else:
            child = nodes[line]

        child.set_parent(parent)
    return roots

# R = read_tree_from_child_parent_list()
R = read_file_system_tree()

formats = sys.argv[1:]
if formats == []:
    formats = [ 'indentation', 'simple', 'pretty' ]

for f in formats:
    for r in R.children:
        r.print_tree(f)

#!/usr/bin/python3

import sys

M = []
maxlen = 0

for l in sys.stdin:
    if len(l) > maxlen:
        maxlen = len(l)
        M = [ l ]
    elif len(l) == maxlen:
        M.append(l)

for l in M:
    sys.stdout.write(l)

#!/usr/bin/python3

import sys

P = []

for l in sys.stdin:
    point_str = l.split(' ')
    x = int(point_str[0])
    y = int(point_str[1])
    P.append((x, y))

def points_lt(p,q):
    return (p[0] < q[0] or (p[0] == q[0] and p[1] < q[1]))

def points_le(p,q):
    return (p[0] < q[0] or (p[0] == q[0] and p[1] <= q[1]))

def partition(A, begin, end):
    pivot = A[end - 1]
    q = begin
    for i in range(begin+1, end-1):
        if points_le(A[i], pivot):
            A[i], A[q] = A[q], A[i]
            q += 1
    A[end-1], A[q] = A[q], A[end-1]
    return q

def quick_sort_r(A, begin, end):
    if (end > begin + 1):       # if we are looking at more than one element
        q = partition(A, begin, end)
        quick_sort_r(A, begin, q)
        quick_sort_r(A, q+1, end)

def quick_sort(A):
    quick_sort_r(A, 0, len(A))

def binary_search(A, k, begin, end):
    while begin < end:
        middle = (end + begin - 1) // 2
        if A[middle] == k:
            return True
        elif points_lt(A[middle], k):
            begin = middle + 1
        else:
            end = middle
    return False

quick_sort(P)

def vec_diff(x,y):
    return (x[0]-y[0], x[1]-y[1])

def vec_rot_90(x):
    return (x[1],-x[0])

N = len(P)
for i in range(1,N):
    for j in range(i):
        p = P[i]
        q = P[j]
        pq = vec_diff(q,p)
        if pq[0] < 0 and pq[1] >= 0 or pq[0] >= 0 and pq[1] < 0:
            continue
        if pq[0] < 0 and pq[1] < 0:
            p, q = q, p
            pq = vec_diff(q,p)
        # must be pq[0] >= 0 and pq[1] >= 0
        ort = vec_rot_90(pq)
        r = vec_diff(p, ort)
        s = vec_diff(q, ort)
        if binary_search(P, r, 0, N) and binary_search(P, s, 0, N):
            print(p, q, r, s)

#!/usr/bin/python3

#
# this program reads a set of words from the standard input, then it
# inserts them into a ternary search trie (TST) and then prints the
# TST
#
# For example, with this input:
# 
# lugano
# ciao
# lunatic
# cappero
# algorithms
# algo
# altro
# altrove
# allegro
# ciaa
# math
# matrix
# 
# the output should be:
# 
#    /a=l=g=o*r=i=t=h=m=s*
#    /     \ /l=e=g=r=o*
#    /     \t=r=o*v=e*
#    / /a=p=p=e=r=o*
#    / /   /a*
#  /c=i=a=o*
# l=u=g=a=n=o*
#  \   \n=a=t=i=c*
#  \m=a=t=h*
#          \r=i=x*
# 
import sys

class TSTNode:
    """represents a node in a ternary search trie"""
    def __init__(self,c):
        self.c = c
        self.is_key = False
        self.equal = None
        self.left = None
        self.right = None

def tst_chain(k, pos):
    prev = None
    res = None
    for i in range(pos, len(k)):
        n = TSTNode(k[i])
        if prev != None:
            prev.equal = n
        prev = n
        if res == None:
            res = n
    n.is_key = True
    return res

def tst_insert(t,k):
    if t == None:
        return tst_chain(k,0)
    root = t
    i = 0
    while True:
        if k[i] > t.c:
            if t.right == None:
                t.right = tst_chain(k,i)
                return root
            else:
                t = t.right
        elif k[i] < t.c:
            if t.left == None:
                t.left = tst_chain(k,i)
                return root
            else:
                t = t.left
        else:
            if i >= len(k)-1:
                t.is_key = True
                return root
            if t.equal == None:
                t.equal = tst_chain(k,i+1)
                return root
            else:
                i = i + 1
                t = t.equal

def tst_add_from_file(t,f):
    for l in f:
        k = l.strip()
        if k != '':
            t = tst_insert(t, k)
    return t

def tst_print_left(prefix,t):
    if t == None:
        return

    if t.left != None:
        prefix = prefix + ' /'
        tst_print(prefix, t.left)
    else:
        prefix = prefix + '  '

    if t.equal != None:
        tst_print_left(prefix, t.equal)


def tst_print_equal_right(prefix,t):
    if t == None:
        return

    sys.stdout.write(t.c)
    if (t.is_key):
        sys.stdout.write('*')
    else:
        sys.stdout.write('=')
    if t.right != None:
        prefix = prefix + ' \\'
    else:
        prefix = prefix + '  '

    if t.equal != None:
        tst_print_equal_right(prefix, t.equal)
    else:
        sys.stdout.write('\n')

    if t.right != None:
        tst_print(prefix, t.right)

def tst_print(prefix, t):
    if t == None:
        return

    if len(prefix) > 1 and prefix[-1:] == '/':
        tst_print_left(prefix[:-1]+' ',t)
    else:
        tst_print_left(prefix,t)

    sys.stdout.write(prefix)
    if len(prefix) > 1 and prefix[-1:] == '\\':
        tst_print_equal_right(prefix[:-1]+' ',t)
    else:
        tst_print_equal_right(prefix,t)

T = None
T = tst_add_from_file(T, sys.stdin)

tst_print('',T)

#!/usr/bin/python3
#
# This program reads a string of digits S as a command-line argument,
# and inserts plus (+) and minus signs (-) in the sequence of digits
# so as to create an expression that evaluates to zero. The program
# should output a resulting expression, if one such expression exists,
# or "None" if no such expression exists.
# 
# For example, if S is "201015900001", then the program could output
# "+2+0+10+1-5-9+0+0+0+0+1". Instead, if S is "200015800001", then the
# program should output "None".
#
# This program tends to produce long expressions (with many operands).
# 
import sys

def solve_puzzle(s, n):
    v = int(s)
    if v == n:
        return '+' + s

    if v == -n:
        return '-' + s

    if v < abs(n):
        return None

    for i in range(1,len(s)):
        front = s[0:i]
        back = s[i:]
        target = int(front)
        back_solution = solve_puzzle(back,n-target)
        if back_solution != None:
            return '+' + front + back_solution
        back_solution = solve_puzzle(back,n+target)
        if back_solution != None:
            return '-' + front + back_solution

    return None

print(solve_puzzle(sys.argv[1],0))