solution.org 23 KB
#+TITLE: Solution to ProblemF
#+SUBTITLE: Machine scheduler
#+author: Edgar Rios
#+SETUPFILE: /home/edgar/Documentos/Research/Meniscus/Reports/setupfile.org
#+PROPERTY: header-args :exports results :eval no-export
#+PROPERTY: header-args:python :python python3 :eval no-export
* Executive summary
:LOGBOOK:
CLOCK: [2020-08-14 vie 20:43]--[2020-08-14 vie 20:48] => 0:05
CLOCK: [2020-08-14 vie 19:07]--[2020-08-14 vie 19:33] => 0:26
CLOCK: [2020-08-14 vie 15:07]--[2020-08-14 vie 15:37] => 0:30
:END:
This document presents the solution to a problem which is a preliminary step to apply to a position in Nexedi. The solution itself is shown next in table [[tbl-profit]].
#+NAME: tbl-profit
#+CAPTION: Results for the machine scheduler (see blk [[blk-main.py]])
#+RESULTS: blk-main.py
| Example Input | Example Output |
| 6 10 20 | Case 1: 258 |
| 0 11 30 | Case 2: 11 |
| 1 12 30 | Case 3: 12 |
| 1 10 2 | Case 4: 10 |
| 2 10 11 | Case 5: 57 |
The results shown in table [[tbl-profit]] show that for the *first case*, the maximum amount of money at the end of the restructuring period would be 258 dollars, for example (second line of table [[tbl-profit]]).
The *second case* does not have any machines, and the money would only be the initial funds available.
The *third* and *fourth* cases are more profitable by just keeping the initial money. For example, case 3 had only one machine which could be bought on the last day of the restructuring period, which would render it unproductive. The initial funds for that third case were 12 dollars, the price to buy and sell the machine were 10 and 5 dollars, respectively. This would represent a net loss of 5 dollars. The machine of case 4 would produce 1 dollar, but the expense of buying and selling it is greater than that. Thus, the best case is not to invest in those projects and keep the initial funds.
* Report
:LOGBOOK:
CLOCK: [2020-08-14 vie 15:22]--[2020-08-14 vie 18:59] => 3:37
CLOCK: [2020-08-14 vie 11:02]--[2020-08-14 vie 15:03] => 4:01
CLOCK: [2020-08-13 jue 23:44]--[2020-08-14 vie 01:03] => 1:19
CLOCK: [2020-08-13 jue 22:52]--[2020-08-13 jue 23:15] => 0:23
CLOCK: [2020-08-13 jue 21:08]--[2020-08-13 jue 22:20] => 1:12
CLOCK: [2020-08-13 jue 20:09]--[2020-08-13 jue 20:47] => 0:38
CLOCK: [2020-08-13 jue 17:45]--[2020-08-13 jue 20:03] => 2:18
CLOCK: [2020-08-12 mié 21:10]--[2020-08-12 mié 23:55] => 2:45
CLOCK: [2020-08-12 mié 20:05]--[2020-08-12 mié 21:05] => 1:00
CLOCK: [2020-08-12 mié 16:37]--[2020-08-12 mié 19:40] => 3:03
CLOCK: [2020-08-12 mié 15:57]--[2020-08-12 mié 16:12] => 0:15
CLOCK: [2020-08-12 mié 15:09]--[2020-08-12 mié 15:56] => 0:47
CLOCK: [2020-08-11 mar 22:45]--[2020-08-12 mié 00:01] => 1:16
CLOCK: [2020-08-11 mar 15:22]--[2020-08-11 mar 15:38] => 0:16
CLOCK: [2020-08-11 mar 15:05]--[2020-08-11 mar 15:21] => 0:16
CLOCK: [2020-08-11 mar 13:59]--[2020-08-11 mar 14:51] => 0:52
CLOCK: [2020-08-11 mar 13:15]--[2020-08-11 mar 13:33] => 0:01
CLOCK: [2020-08-11 mar 12:04]--[2020-08-11 mar 12:59] => 0:55
CLOCK: [2020-08-11 mar 11:48]--[2020-08-11 mar 12:00] => 0:12
CLOCK: [2020-08-11 mar 10:11]--[2020-08-11 mar 11:36] => 1:25
CLOCK: [2020-08-11 mar 10:00]--[2020-08-11 mar 10:01] => 0:01
CLOCK: [2020-08-10 lun 20:59]--[2020-08-10 lun 22:48] => 1:49
:END:
** Problem F
You are the director of Awesomely Complex Machines (or short: ACM), a company producing advanced machinery using even more advanced machinery. The old production machinery has broken down, so you need to buy new production machines for the company. Your goal is to make as much money as possible during the restructuring period. During this period you will be able to buy and sell machines and operate them for profit while ACM owns them. Due to space restrictions, ACM can own at most one machine at a time. During the restructuring period, there will be several machines for sale. Being an expert in the advanced machines market, you already know the price P_{i} and the availability day D_{i} for each machine M_{i}. Note if you do not buy machine M_{i} on day D_{i} then somebody else will buy it and it will not be available later. Needless to say, you cannot buy a machine if ACM has less money than the price of the machine. If you buy a machine M_{i} on day D_{i} then ACM can operate it starting on day D_{i} + 1. Each day that the machine operates, it produces a profit of G_{i} dollars for the company.
You may decide to sell a machine to reclaim a part of its purchase price any day after you’ve bought it. Each machine has a resale price R_{i} for which it may be resold to the market. You cannot operate a machine on the day that you sell it, but you may sell a machine and use the proceeds to buy a new machine on the same day. Once the restructuring period ends, ACM will sell any machine that it still owns. Your task is to maximize the amount of money that ACM makes during the restructuring.
** Input
The input consists of several test cases. Each test case starts with a line containing three positive integers N, C, and D. N is the number of machines for sale (N \le 10^{5}), C is the number of dollars with which the company begins the restructuring (C \le 10^{9}), and D is the number of days that the restructuring lasts (D \le 10^{9}).
Each of the next N lines describes a single machine for sale. Each line contains four integers D_{i}, P_{i}, R_{i} and G_{i} denoting (respectively) the day on which the machine is for sale, the dollar price for which it may be bought, the dollar price for which it may be resold and the daily profit generated by operating the machine. These numbers satisfy the following conditions:
| 1 \le D_{i} \le D |
| 1 \le R_{i} \lt P_{i} \le 10^{9} |
| 1 \le G_{i} \le 10^{9} |
The last test case is followed by a line containing three zeros.
** Output
For each test case, display its case number followed by the largest number of dollars that ACM can have at the end of day D + 1. Follow the format of the sample output.
| Example Input | Example Output |
| 6 10 20 | Case 1: 44 |
** Solution
*** Digest of the problem
- Your goal is to make as much money as possible during the restructuring period
- buy and sell is possible
- at most one machine at a time
- can only buy machines with available money
- profit starts on D_{i} + 1
- profit stops on sale day
- can buy new machine on sale day of old machine
- all machines are sold at the end
- cannot operate a machine on the day that you sell it
- P_{i} :: purchasing price
- M_{i} :: machine
- D_{i} :: day when you can buy machine
- G_{i} :: profit from machine for each day
- R_{i} :: resale price
- N :: number of machines for sale (N \le 10^{5})
- C :: starting money (N \le 10^{9})
- D_t :: total (D \le 10^{9})
#+name: blk-get-inputdata.py
#+caption: Read data file into a variable
#+begin_SRC python :exports none
# * Read the data
# Read the file and close it automatically
with open("input.txt") as fd:
# Read the values which are not "0 0 0" or empty (eol),
# and turn them into lists of integers (from strings)
inputdata = [[int(VAL) for VAL in LINE[:-1].split(" ")]
for LINE in filter(lambda l:
l[:5] != "0 0 0"
and len(l)>1,
fd.readlines())]
#+end_SRC
#+name: blk-show-inputdata.py
#+begin_SRC python :exports results :noweb yes :results output table
<>
print(inputdata)
#+end_SRC
#+name: tbl-input-data.txt
#+caption: Data provided as input
#+RESULTS: blk-show-inputdata.py
| 6 | 10 | 20 | |
| 6 | 12 | 1 | 3 |
| 1 | 9 | 1 | 2 |
| 3 | 2 | 1 | 2 |
| 8 | 20 | 5 | 4 |
| 4 | 11 | 7 | 4 |
| 2 | 10 | 9 | 1 |
| 0 | 11 | 30 | |
| 1 | 12 | 30 | |
| 30 | 10 | 5 | 3 |
| 1 | 10 | 2 | |
| 1 | 10 | 2 | 1 |
| 2 | 10 | 11 | |
| 1 | 10 | 4 | 3 |
| 1 | 10 | 9 | 3 |
*** Assumptions
- Restructuring period finishes by the end of the last day, and remaining machines will be sold after that (the next day).
#+begin_QUOTE
Once the restructuring period ends, ACM will sell any machine that it still owns.
#+end_QUOTE
In other words, a machine can produce on the last day (for as much as 1 day).
*** Extract data :noexport:
#+name: blk-inputdata2lst.py
#+caption: Get and structure data from =input.txt=
#+begin_SRC python :exports none
# * Extract the values for each case
# See where a case starts and ends
casemarks = [VAL for VAL in range(len(inputdata))
if len(inputdata[VAL])==3]
# Get the header of each case (case specs)
casehead = [inputdata[VAL] for VAL in casemarks]
# Get the variables' values
casevals = [inputdata[VAL+1:VAL + casehead[I][0] + 1]
for I, VAL in enumerate(casemarks)]
#+end_SRC
#+name: blk-print-casevals.py
#+HEADER: :var tabhead='(("Case" "Machine") ("" "(D_{i} P_{i} R_{i} G_{i})"))
#+begin_SRC python :noweb yes :results output table :var indexvarnom="casemarks" outvarnom="casevals"
<>
<>
outvar = eval(outvarnom)
indexvar = eval(indexvarnom)
out = [[] for i in range(len(indexvar))]
for I in range(len(indexvar) - 1):
out[I] = [I + 1] + outvar[I]
out[-1] = [I + 2] + outvar[-1]
print([*tabhead, None] + out)
#+end_SRC
The data for each machine and each case is presented on
#+caption: The values of each machine (D_{i} P_{i} R_{i} G_{i}) for each case
#+RESULTS: blk-print-casevals.py
| Case | Machine | | | | | |
| | | | | | | |
|------+-------------+------------+-----------+------------+------------+------------|
| 1 | (6 12 1 3) | (1 9 1 2) | (3 2 1 2) | (8 20 5 4) | (4 11 7 4) | (2 10 9 1) |
| 2 | | | | | | |
| 3 | (30 10 5 3) | | | | | |
| 4 | (1 10 2 1) | | | | | |
| 5 | (1 10 4 3) | (1 10 9 3) | | | | |
#+call: blk-print-casevals.py(tabhead='(("Case" "N (# machines)" "C ($)" "D_t (# days)")), outvarnom="casehead")
#+caption: The values for each case
#+RESULTS:
| Case | N (# machines) | C ($) | D_t (# days) |
|------+----------------+-------+--------------|
| 1 | 6 | 10 | 20 |
| 2 | 0 | 11 | 30 |
| 3 | 1 | 12 | 30 |
| 4 | 1 | 10 | 2 |
| 5 | 2 | 10 | 11 |
*** Mathematical model :noexport:
#+name: blk-machine-gain.py
#+caption: Calculate the nominal gain from a machine based on whether it is active and the number of days it runs
#+begin_SRC python :exports code
def machine_gain(P, R, G, D, de):
"""Calculate the nominal gain from a machine based on it is
active and the number of days it runs:
(G * (de - (D + 1)) + R - P)
Keyword Arguments:
P -- (int) Purchase cost
R -- (int) Amount returned after sale
G -- (int) Profit rate per day for working
D -- day on which the machine is purchased
de -- day on which the machine is sold
Returns:
(G * (de - (D + 1)) + Ri - Pi)
Example:
>>> machine_gain(4, 3, 10, 0, 2)
9
"""
return G * (de - (D + 1)) + R - P
#+end_SRC
*** Code
#+NAME: blk-itertools_import.py
#+CAPTION: Import itertools to do combinatorics quickly
#+BEGIN_SRC python :exports none
# Iteration tools
import itertools as itls
#+END_SRC
#+NAME: blk-enabled-machine-scen.py
#+caption: Get the cartesian product (combinations) for using (or not) every machine
#+begin_SRC python :exports none :var nmach=3
# Keep those machines which are considered for this
# scenario (scenari[-1][I]) and initial day is lower than
# last day (vals[I][0] < Dt)
# The machines which can be purchased on or after the last
# day are not profitable, because Ri < Pi and do not
# proudce because the initial day of production is Di + 1
if scencom.count(1) == 1:
# Find and get which scenario is active
actidx = scencom.index(1)
if vals[actidx][0] <= Dt:
scenmachs = [vals[actidx]]
else:
scenmachs = []
else:
scenmachs = [vals[I] for I in range(case[0])
if scencom[I] and vals[I][0] < Dt]
# Number of machines for this scenario
scenN = len(scenmachs)
if scenN > 0:
# Sort the machines according to the first possible day
# of use (first), and then profit rate (Gi)
# day column
dcol = 0
# Gi column
gcol = -1
# (https://stackoverflow.com/a/17109098
# to sort by two columns with descending order)
scenmachs = sorted(scenmachs,
key=lambda m: (m[dcol], -m[gcol]))
# Days when a machine can start and include total amount of
# days (last day)
scenD = [VAL[0] for VAL in scenmachs] + [Dt]
#+end_SRC
#+NAME: blk-last-day-combinations.py
#+CAPTION: Create all possible combinations of _(minimum and maximum) days to sell_ each machine
#+BEGIN_SRC python :exports none :results none :noweb yes
# Get the cartesian product (combinations) for choosing
# either min (0) and max (1).
# scenN - 1: because the last day of the last machine is
# always the last day of production
de_minmaxcom = list(itls.product(*[[0, 1]] * (scenN - 1)))
# Minimum allowable days of sale for each machine
# scenN - 1: the last day of the last machine is always
# the last day of production
desmin = [max(scenD[I] + 2, scenD[I + 1])
for I in range(scenN - 1)] + [Dt]
# Maximum allowable days of sale for each machine
desmax = [Dt + 1 for I in range(scenN)]
# This loop is reversed later (easier to see; remember that
# the first element is actually the last of the desmax)
for I in list(range(1, len(desmax))):
desmax[I] = desmax[I - 1] - 2
desmax.reverse()
# Pair min and max
desminmax = [[desmin[I], desmax[I]]
for I in range(scenN - 1)]
# Set all possible combinations of _minimum and maximum days
# to end using_ (sale day) each machine
des = [[desminmax[II][VAL[II]]
for II in range(scenN - 1)] + [Dt + 1]
for I, VAL in enumerate(de_minmaxcom)]
# Remove repeated and cases where an ending day is lower
# than or equal to the allowable purchase day
des = np.unique(
[des[I] for I, VAL in enumerate(
np.asarray(scenD[1:]) <= np.asarray(des))
if all(VAL)], axis=0).tolist()
# Correct those which are overlapping
# (it may not be needed, i.e. it is possible that they
# could be removed, but better be safe)
for VAL in des:
if not (sorted(VAL) == VAL and all(np.diff(VAL) > 1)):
I = 1
# for creates a temporary immutable variable, while
# works with the actual variable
while I < len(VAL[:-1]):
demin = VAL[I - 1] + 2
demax = VAL[I + 1] - 2
# If the current sale day is at least 2 days
# bigger than the previous machine (demin)
if VAL[I] < demin:
# if 2 days than the previous machine is
# lower or equal to maximum possible value
# of the machine, and viceversa
if demin <= desminmax[I][1]:
VAL[I] = demin
elif demax >= desminmax[I][0]:
VAL[I] = demin
I += 1
# Delete variable I (it is too precious; consider
# function)
del I, VAL
# Remove
# 1. cases which could not be ammended; those that still
# have machines which end within less than 2 days inbetween
# (avoid race conditions trying to do that in previous
# loop)
# 2. duplicates
des = np.unique([VAL for VAL in des
if sorted(VAL)==VAL], axis=0).tolist()
#+end_SRC
#+NAME: blk-ini-day-combinations.py
#+CAPTION: Calculate the initial days for each machine based on the sale days and the purchase day of the first machine
#+BEGIN_SRC python :exports none :results none
dis = [[scenD[0] + 1]
+ [VAL2 + 1 for VAL2 in VAL[:-1]] for VAL in des]
#+END_SRC
#+NAME: blk-scen-gains-from-machines.py
#+CAPTION: Calculate the actual profit produce by all machines for this scenario
#+BEGIN_SRC python :exports none :results none
# differences between last and first day for all machines
# (each row is a viable combination for the minimum and
# maximum days of sale, each column is a machine)
# [ de_1_max - di_1 de_2_max - di_2 ]
# [ de_1_min - di_1 de_2_max - di_2 ... n ]
# [ de_1_max - di_1 de_2_max - di_2 ]
# [ de_1_max - di_1 de_2_min - di_2 ]
scenDd = np.subtract(des, dis)
# Make sure that the last day is always bigger than the
# starting day
assert np.all(scenDd > 0)
# Create a matrix with the scenario values
scenmat = np.asmatrix(scenmachs)
# Get the product of the day differences and the production
# rate
# Gi = scenmat[:, 3]
mach_prod = np.asmatrix(scenDd).dot(scenmat[:, 3])
# Get the differences between return and purchase prices
# Ri = scenmat[:, 2], Pi = scenmat[:, 1]
mach_cost = (scenmat[:, 2] - scenmat[:, 1]).T
# Find the maximum profit
# C = case[1]
scenP = np.max(np.sum(mach_prod + mach_cost, axis=1))
#+END_SRC
#+NAME: def-scen_profit.py
#+CAPTION: Calculate the profit for a given scenario (a combination where some machines may be enabled or disabled) of a case
#+BEGIN_SRC python :exports none :results none :noweb yes
def scen_profit(case, vals, scencom):
"""Calculate the profit for a given scenario (a combination
where some machines may be enabled or disabled) of a case
Keyword Arguments:
<>
<>
<>
Returns:
scenP -- (int|float) the maximum profit for a given
scenario
Example:
>>> # N, C, D_t
>>> <>
>>> # Di, Pi, Ri, Gi
>>> <>
>>> <>
>>> scen_profit(case, vals, scencom)
143
"""
# Total number of days for the case
Dt = case[-1]
<>
# Cases which can be expedite
if len(scenmachs) == 1:
# If there is only one machine, the maximum profit is
# achieved when running it as long as possible
Di, Pi, Ri, Gi = scenmachs[0]
scenP = Gi * ((Dt + 1) - (Di + 1)) + Ri - Pi
return scenP
if scenN == 0:
# If there are no machines in the scenario, they cannot
# produce profit
scenP = 0
return scenP
<>
<>
<>
return scenP
#+END_SRC
#+NAME: def-case_profit.py
#+CAPTION: Calculate the maximum profit for a given case
#+BEGIN_SRC python :exports none :results none :noweb yes
def case_profit(case, vals):
"""Uses the values of =vals= to estimate the maximum profit
of a case (a combination of =vals= in conjunction with
=case=). It iterates over possible combinationss of last
days of use for each machine to set different viable
scenarios of profit.
Keyword Arguments:
<>
<>
Returns:
caseP -- (int|float) the maximum profit for a case
Example:
>>> # N, C, D_t
>>> <>
>>> # Di, Pi, Ri, Gi
>>> <>
>>> case_profit(case, vals)
155
"""
# Number of machines for this case
nmach = case[0]
nall = len(vals)
# Get the cartesian product (combinations) for using (or
# not) every machine
cartesian = itls.product(*[[0, 1]] * len(vals))
# Extract only the cases which have the number of machines
# specified by the case and remove the empty case
scenaricom = [I for I in cartesian
if I.count(1) == nmach and any(I)]
# Get the maximum profit for each scenario
# (a scenario is a single combination where a machine or
# several machines can be enabled)
scenariP = [scen_profit(case, vals, VAL)
for VAL in scenaricom] + [0]
# Get maximum profit for this case
caseP = case[1] + max(scenariP)
return caseP
#+END_SRC
#+NAME: blk-main.py
#+CAPTION: Main program to get the profit for all cases
#+BEGIN_SRC python :results output raw :noweb yes :exports both
# Headers ********
import numpy as np
<>
# Functions ********
<>
<>
<>
# Main program begins ********
<>
<>
# Get the initial funds if there are no machines for this
# case or calculate its maximum profit if there are
profits = [VAL[1] if VAL[0] < 1
else case_profit(VAL, casevals[I])
for I, VAL in enumerate(casehead)]
print("| Example Input | Example Output |")
for I, VAL in enumerate(casehead):
print("|", " ".join([str(VAL2) for VAL2 in VAL]),
"| Case {0}: {1} |".format(I + 1, profits[I]))
#+END_SRC
*** Snippets :noexport:
#+NAME: ex-case.py
#+CAPTION: Example for the value of a single case header. Its values are N, C and Dt (number of machines, intial funds and last day of production, respectively)
#+BEGIN_SRC python :results none
case = [5, 12, 15]
#+END_SRC
#+NAME: ex-vals.py
#+CAPTION: Example of the values that a case may have for each of its machines
#+begin_SRC python :results none
vals = [[1, 10, 4, 3], [1, 10, 9, 3], [7, 8, 3, 4],
[15, 10, 5, 4], [14, 10, 5, 4], [13, 10, 5, 4]]
#+end_SRC
#+NAME: ex-scencom.py
#+CAPTION: Example for the value of a single scenario (combination) with 5 machines. Each value can be =0= or =1= for /enabled/ or /disabled/, respectively.
#+BEGIN_SRC python :results none
scencom = (1, 1, 1, 0, 1)
#+END_SRC
#+NAME: desc-case.txt
#+CAPTION: Description of case
#+BEGIN_SRC fundamental :results none :noweb yes
case -- (list(N, C, Dt)) the header (main description) of the
case, where N is the number of machines in the case,
C is the initial funds and Dt is the last day of
production. Ex:
<>
#+END_SRC
#+NAME: desc-vals.txt
#+CAPTION: Description of values
#+BEGIN_SRC fundamental :results none :noweb yes
vals -- (list((Di, Pi, Ri, Gi))) the table of values for
each machine in this case. Ex:
<>
#+END_SRC
#+NAME: desc-scencom.txt
#+CAPTION:
#+BEGIN_SRC fundamental :results none :noweb yes
scencom -- (list(0|1)) which machines are enabled for
this scenario. Ex:
<>
#+END_SRC
#+caption: Dummy example with 5 machines
#+begin_SRC python
# FAKE CASE --------------------
# N, C, D_t
case = [5, 12, 15]
# Di, Pi, Ri, Gi
vals = [[1, 10, 4, 3], [1, 10, 9, 3], [15, 10, 5, 3]]
vals = [[1, 10, 4, 3], [1, 10, 9, 3], [7, 8, 3, 4],
[15, 10, 5, 4], [14, 10, 5, 4], [13, 10, 5, 4]]
# ------------------------------
#+end_SRC
** Time report
The amount of time consumed for this project is presented below, as requested
#+ATTR_LATEX: :booktabs t :environment longtabu
#+BEGIN: clocktable :maxlevel 1 :link nil
#+CAPTION: Amount of time consumed for this project (1d = 24 h)
| Headline | Time |
|-------------------+-----------|
| *Total time* | *1d 5:34* |
|-------------------+-----------|
| Executive summary | 0:56 |
| Report | 1d 4:38 |
#+END
* License
The code in this document is distributed as GPL v3.
The documentation (except for the Problem F, Input and Output sections) is distributed as FDL v1.6