Check All - Scala
Estimated score: 2m^n
I start from each machine and iterate over all the tasks to create all permutations through the tasks with different machines that meet the deadlines. Meaning if everything is in time I would get 9 possible paths with 2 machines and 3 tasks. (m^n) Afterwards, I take the path with the lowest cost.
Input is structured like this (--> explains the parts and thus should not be entered):
M_1:5 3 5 4;M_2:4 2 7 5 --> time
M_1:5 4 2 6;M_2:3 7 3 3 --> cost
M_1:M_1}0 M_2}1;M_2:M_1}2 M_2}0 --> switch itme
M_1:M_1}0 M_2}2;M_2:M_1}1 M_2}0 --> switch cost
5 10 15 20 --> deadlines
And here is the code:
package Scheduling
import scala.io.StdIn.readLine
case class Cost(task: Map[String, List[Int]])
case class Switch(machine: Map[String, Map[String, Int]])
case class Path(time: Int, cost: Int, machine: List[String])
object Main {
def main(args: Array[String]) {
val (machines, cost_time, cost_money, switch_time, switch_money, deadlines) = getInput
val s = new Scheduler(machines, cost_time, cost_money, switch_time, switch_money, deadlines)
s.schedule
}
def getInput(): (List[String], Cost, Cost, Switch, Switch, List[Int]) = {
val cost_time = Cost(readLine("time to complete task").split(";").map{s =>
val parts = s.split(":")
(parts(0) -> parts(1).split(" ").map(_.toInt).toList)
}.toMap)
val cost_money = Cost(readLine("cost to complete task").split(";").map{s =>
val parts = s.split(":")
(parts(0) -> parts(1).split(" ").map(_.toInt).toList)
}.toMap)
val switch_time = Switch(readLine("time to switch").split(";").map{s =>
val parts = s.split(":")
(parts(0) -> parts(1).split(" ").map{t =>
val entries = t.split("}")
(entries(0) -> entries(1).toInt)
}.toMap)
}.toMap)
val switch_money = Switch(readLine("time to switch").split(";").map{s =>
val parts = s.split(":")
(parts(0) -> parts(1).split(" ").map{t =>
val entries = t.split("}")
(entries(0) -> entries(1).toInt)
}.toMap)
}.toMap)
val deadlines = readLine("deadlines").split(" ").map(_.toInt).toList
val machines = cost_time.task.keys.toList
(machines, cost_time, cost_money, switch_time, switch_money, deadlines)
}
}
class Scheduler(machines: List[String], cost_time: Cost, cost_money: Cost, switch_time: Switch, switch_money: Switch, deadlines: List[Int]) {
def schedule() {
var paths = List[Path]()
var alternatives = List[(Int, Path)]()
for (i <- machines) {
if (cost_time.task(i)(0) <= deadlines(0)) {
paths = paths ::: List(Path(cost_time.task(i)(0), cost_money.task(i)(0), List(i)))
}
}
val allPaths = deadlines.zipWithIndex.tail.foldLeft(paths)((paths, b) => paths.flatMap(x => calculatePath(x, b._1, b._2)))
if (allPaths.isEmpty) {
println("It is not possible")
} else {
println(allPaths.minBy(p=>p.cost).machine)
}
}
def calculatePath(prev: Path, deadline: Int, task: Int): List[Path] = {
val paths = machines.map(m => calculatePath(prev, task, m))
paths.filter(p => p.time <= deadline)
}
def calculatePath(prev: Path, task: Int, machine: String): Path = {
val time = prev.time + switch_time.machine(prev.machine.last)(machine) + cost_time.task(machine)(task)
val cost = prev.cost + switch_money.machine(prev.machine.last)(machine) + cost_money.task(machine)(task)
Path(time, cost, prev.machine :+ machine)
}
}
I also had an idea to start from the back. Since you can always choose a machine with the lowest cost if the time is smaller then the difference from the previous deadline to the new one. But that wouldn't decrease the maximal runtime if the task with the better cost takes longer then the last deadline is timed.
Update
======
Here is another set up.
time:
M_1 2 2 2 7
M_2 1 8 5 10
cost:
M_1 4 4 4 4
M_2 1 1 1 1
switch time:
M_1 M_2
M_1 0 2
M_2 6 0
switch cost:
M_1 M_2
M_1 0 2
M_2 2 0
deadlines:
5 10 15 20
As input into my program:
M_1:2 2 2 7;M_2:1 8 5 10
M_1:4 4 4 4;M_2:1 1 1 1
M_1:M_1}0 M_2}2;M_2:M_1}6 M_2}0
M_1:M_1}0 M_2}2;M_2:M_1}2 M_2}0
5 10 15 20
This one has two solutions:
time: 18, cost: 15, path: List(M_1, M_1, M_1, M_2)
time: 18, cost: 15, path: List(M_2, M_1, M_1, M_1)
Which raises the question how this should be handled. Should all be printed or just one? And what if the time would be different? Is one with the lowest cost and no missed deadline enough or should it also be the one with the lowest time?
"switching time from the row machine to the column machine" You mean the time cost to switch from M_1 to M_2? Also what's the difference between "switching cost" and "switching time". They typically mean the same thing in relation to describing scheduling algorithms. – Luminous – 2015-01-21T21:15:51.740
@Luminous Think of time in seconds and cost in dollars. They are different things in this question. The tables show the time (respectively cost) of changing machine to perform the next task. This could be from M_1 to M_2 or from M_2 to M_1. – None – 2015-01-21T21:27:54.007
Ok, that clarifies that. – Luminous – 2015-01-21T21:31:25.150
The short answer is that the complexity will be
O(m ^ n)
. No algorithm will be "faster" than that. Pruning based on a maximum required time or cost doesn't change the complexity of the algorithm, nor does having both a dollar cost and a time cost, henced
is not an element of the complexity. – Bob Dalgleish – 2015-01-22T13:43:14.8601@BobDalgleish That gives a score of 100 to the power of 100. I believe you can do a lot better. – None – 2015-01-22T14:10:20.817
Will the actual input have labels like
M_1
andT_1
? – KSFT – 2015-01-22T17:47:16.337@KSFT You can assume any sensible format for the input you like. I was assuming that each table would just be a list of tuples, each tuple representing a row of that table. – None – 2015-01-22T18:16:53.703
I'm not sure if I understand exactly how you're measuring time complexity. Do both answers currently have the same score? (If so, yay! The bounty would get me halfway to 1k rep!) – KSFT – 2015-01-28T14:32:51.550
@KSFT Assuming it is correct, O(2m^n) = O(m^n) which would give a score of 100^100. I am not yet sure if that 2 is really a constant or is secretly m. In this case it would be 100*100^100. – None – 2015-01-28T14:38:26.933
They both have complexity
O(m^n)
, as BobDalgleish pointed out. – KSFT – 2015-01-28T14:41:01.913The
2
is in the exponent. They both takeO(n*m^n)
time. – KSFT – 2015-01-28T15:05:44.183@KSFT Looks like you both have identical scores.. so you win :) I am bit sad no one tried dynamic programming which I think gives a much better score. – None – 2015-01-28T15:18:06.470
It looks like you never actually wrote in the question the secret information that times must be an integer between 0 and
d
, which made it impossible for anyone to use them n^2 d
solution. – feersum – 2015-01-28T17:30:24.333