8th homework

Download hw_8.tar.gz and extract it. Then add your homework solutions to the directory. Rename the directory according to the rules in the syllabus before submitting it as compressed archive. Don't forget to add the correct subject to the email when submitting.

All of the tasks below need to

in order to receive (full) points.

You'll have to start by implementing a decent test-suite for each of the tasks. Only when you're done with your tests, implement the task itself. The grader will mainly use your own tests to determine your score. If the test-suite is comprehensive, the grader's score will be awarded fully. Otherwise, reasonable deductions will be made.

  1. Writing files (2 points)
    Write a function that takes a list of VRPTW customers (the data structure for representing the customers is up to you), the name of a file to store this list in and a string representing a key for sorting. The function should create a new file resembling the original input file (the same columns), but the customers should be sorted by the given key. The columns should be delimited with a comma (,). An example - sorted by demand - and saved as CSV is r101_by_demand.csv.
    To test your code, use the provided r101.txt file. For reading it, recycle the code you've written for past homeworks. A strategy for testing this is to create small input files and corresponding output file that are known to be correct. Your tests can then run your function on these input files and compare the resulting output files with the correct output files.
    Name the test module: test_vrptw_writer.py
    Test class: TestVrptwWriter
    Name the module: vrptw_writer.py
  2. List comprehension (2 points)
    Implement the functions below using list comprehensions. None of these functions requires more than one line in its body.
    1. Implement a function divisors(number) that takes a single positive integer and returns a list of its positive divisors.
    2. Implement a function filter_by_first_letter(strings, letter) that takes a list of strings and a single character and returns all elements starting with the given letter.
    3. Implement a function primes(number) that takes a single integer and returns a list of prime numbers smaller than or equal to that number.
    4. Implement a function roll_n_times(n) that takes a single integer and returns a list of n random integers between 1 and 6.
    Name the test module: test_comprehensions.py
    Test class: TestComprehensions
    Name the module: comprehensions.py
  3. Simulation (3 points)
    A local bike shop asks you to implement a small program that allows the company to easily simulate future demand.
    Drawing on your experience and past demand, you know that the demand for bikes during springtime is 8, 9, 10, 11 or 12 per day with probabilities of 0.10, 0.15, 0.25, 0.3 and 0.2. The distribution of values should be read from a file called distribution.txt. Given this distribution, generate random demands for the next 10 days. Also, add a command-line option --days d that allows to simulate the demand for any number of days. Make the program executable. When executed, the program should print the simulated total demand for the given number of days.
    The bike shop had already hired a seasoned Python coder to get the job done for them. That person started the program but unfortunately lacked the skills to implement a basic simulation. Feel free to use the code already written for this task.
    Name the test module: test_simulation.py
    Test class: TestSimulation
    Name the module: simulation.py
  4. Knapsack Problem (2 points)
    Imagine you'd have to pack everything you own into a single rucksack. As this is impossible, you'd likely want to pack the things most valuable to you. The problem of selecting the items that lead to the maximum total value is hard and constitutes one of the classical problems in combinatorial optimization. If needed, have a look on Wikipedia's article about knapsack problems.
    You are required to implement a simple recursive function calc_profit(goods, capacity) that returns the maximum profit of packing the rucksack with a subset of the given goods fulfilling the given capacity constraint. A recursive implementation of this function takes less than 10 lines of code. Note that you do not need to keep track which goods are selected and which aren't (this would make the problem a lot harder to implement).
    Name the test module: test_knapsack.py
    Test class: TestKnapsack
    Name the module: knapsack.py