Recursion and working with files

Date: 25/11/2020
Time: 09:30-11:30

Recursion

What is it about?
  • The process of defining something in terms of itself
  • In python this happens when a function calls itself

    • Why do we need it?
  • The code look clean and elegant
  • A complex task is broken down into simpler sub-problems
  • Some data structures like trees are easier to explore using recursion
    • # Example: recursive function for calculating n! (factorial)
    def factorial_recursive(n):
        #Base case
        if n == 1:
            return 1
        #Recursive case: n * (n-1)!
        else:
            return n * factorial_recursive(n-1)
    print(factorial_recursive(5))
    #OUTPUT: 120

    Reading and writing files

  • In python, we can read external files and create/write new files with content inside
  • We need to provide the location of the file inside our system: path to the file. If the path is in the current working directory, you can just provide the filename myfile.txt. If not then you have to provide the path of the file DIRECTORY_NAME/myfile.txt. We have two types of paths
  • Absolute file path: are notated by a leading forward slash or drive label. The path starts from the root of the file system. E.g. /DIRECTORY_1/MY_PROJ_DIRECTORY/MY_PROJ_FILES/myfile.txt
  • Relative file path: are notated by a lack of a leading forward slash. It is interpreted from the perspective of your current working directory. MY_PROJ_FILES/myfile.txt

  • /DIRECTORY_1/MY_PROJ_DIRECTORY/MY_PROJ_FILES/myfile.txt
  • MY_PROJ_FILES/myfile.txt
    • Reading a file:
    # First approach
    my_file=open("files/freetext.txt","r")
    for line in my_file:
        print(line)
    my_file.close()
    # Second approach
    with open("files/freetext.txt","r") as my_file:
        for line in my_file:
            print(line)
    Writing a file:
    # First approach
    my_file=open("files/new_freetext.txt","w")
    my_file.write("the file content!")
    my_file.close()
    # Second approach
    with open("files/new_freetext.txt","w") as my_file:
        my_file.write("the file content!")

    CSV and JSON files

  • A CSV (Comma Separated Values): file is a form of plain text document which uses a particular format to organize tabular information. CSV file format is a bounded text document that uses a comma to distinguish the values
    • Reading a CSV file:
    import csv
    with open('files/csv_example.csv', mode='r') as file:
        csvFile = csv.reader(file)
        for line in csvFile:
            print(line)
    Writing a CSV file:
    import csv
    with open('files/new_csv_example.csv', mode='w') as csvfile:
        csvwriter = csv.writer(csvfile)
        # fields is a list values
        csvwriter.writerow(fields)
        # rows is a list of lists
        csvwriter.writerows(rows)
  • A JSON: used to transmit data objects consisting of attribute–value pairs and array data types
    • Reading a JSON file:
    import json
    with open('files/json_example.json', mode='r') as jsonfile:
        json_object = json.load(jsonfile)
    Writing a JSON file:
    import json
    a_dict = {"Federico":35,"Stefano":22,"Sandro":31}
    with open('files/new_json_example.json', mode='w') as jsonfile:
        json.dump(a_dict, jsonfile)

    Exercises

    (check the exercises on the github repository)

    1st Exercise

    Giving a collection of pokemon cards (i.e. a list) we want to adapt it following the pokemon evolution rules, such that if we have two cards representing the same pokemon we must replace them with one card representing the evolved version of that particular pokemon following the mapping rules defined in the below dictionary:

    evolution_map = {
        "Poliwag": "Poliwhirl",
        "Bulbasaur": "Ivysaur",
        "Charmander": "Charmeleon",
        "Pidgey": "Pidgeotto",
        "Psyduck": "Golduck",
        "Abra": "Kadabra"
    }

    For instance:

    l_cards = ["Poliwag", "Pidgey", "Abra", "Pidgey", "Charmander", "Bulbasaur", "Charmander", "Psyduck", "Poliwag","Goldeen"]
    # The new list should be:
    # ['Poliwhirl', 'Charmeleon', 'Bulbasaur', 'Psyduck', 'Pidgeotto', 'Goldeen', 'Abra']

    Define a recursive function called pokemon_cards() which takes a list of pokemon cards and returns a new list of pokemon cards following the pokemon evolution rules just described.

    Mark the box to see the solution
    cards_set = set()
    def pokemon_cards(l_pokemons):
        len_list = len(l_pokemons)
        if len_list == 1:
            pokemon_name = l_pokemons[0]
            if pokemon_name not in cards_set:
                cards_set.add(pokemon_name)
            else:
                cards_set.remove(pokemon_name)
                level2_pokemon = evolution_map[pokemon_name]
                cards_set.add(level2_pokemon)
        else:
            mid = len_list // 2
            pokemon_cards(l_pokemons[:mid])
            pokemon_cards(l_pokemons[mid:])
            return list(cards_set)

    2nd Exercise

    We want to define a recursive function that simulates a pokemon tournament. The number of pokemons participating in the tournament is 8. Each pokemon is defined using 3 values: (1)name, (2)attack-points, and (3) defense-points. A pokemon could be therefore characterized using a tuple of 3 elements, e.g. ("Poliwag",10,5). The tournament could be defined as a list of 8 pokemons (i.e. tuple). For instance:

    pokemon_tournament = [("Poliwag",10,5),("Charmander",15,2),("Abra",8,7),("Pidgey",4,5),("Goldeen",6,8),("Bulbasaur",12,10),("Charmeleon",18,8),("Psyduck",3,4)]

    To determine the champion of the tournament 2 nearby pokemons (according to their order in the list) compete. The pokemon on the left uses the attack-points (second value of the tuple), while the right one uses the defense-points (third value of the tuple), if the attack-points are higher than the defense-points then the pokemon on the left side goes to the next round, otherwise, the pokemon on the right side does that. The same process will be repeated in the second round too. The tournament ends when we have 1 final winner. For example the winner of the tournament pokemon_tournament is:

    # ("Poliwag",10,5)vs("Charmander",15,2) | ("Abra",8,7)vs("Pidgey",4,5) | ("Goldeen",6,8)vs("Bulbasaur",12,10) | ("Charmeleon",18,8)vs("Psyduck",3,4)
    # ("Poliwag",10,5)vs("Abra",8,7) | ("Bulbasaur",12,10)vs("Charmeleon",18,8)
    # ("Poliwag",10,5)vs("Bulbasaur",12,10)
    # ("Bulbasaur",12,10)

    Define a recursive function called pokemon_champion() which takes a tournament (i.e. a list of pokemons) and returns a list containing only the champion of the tournament. For instance pokemon_champion(pokemon_tournament) returns the list [ ("Bulbasaur",12,10) ]

    Mark the box to see the solution
    def pokemon_champion(l_table):
        len_list = len(l_table)
        if len_list == 1:
            return [l_table[0]]
        elif len_list == 2:
            p_attack = l_table[0][1]
            p_defend = l_table[1][2]
            if p_attack > p_defend:
                return [l_table[0]]
            else:
                return [l_table[1]]
        else:
            mid = len_list // 2
            return pokemon_champion(pokemon_champion(l_table[:mid]) + pokemon_champion(l_table[mid:]))