forked from tothmate/puzzles
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathtsp.html
106 lines (83 loc) · 3.79 KB
/
tsp.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
<!doctype html>
<html>
<head>
<title>Zillabyte Travelling Salesman</title>
<link href="tsp.css" rel="stylesheet" type="text/css">
<!-- Vendor JS Files -->
<script src="vendor/jquery.min.js"></script>
<script src="vendor/d3.v2.js"></script>
<script src="vendor/underscore.js"></script>
<script src="vendor/heap.js"></script>
<!-- Stuff to get the TSP working -->
<script src="harness.js"></script>
<script src="random_graph_builder.js"></script>
<script src="renderer.js"></script>
<!-- Algorithms -->
<script src="greedy_salesman.js"></script>
<script src="sequential_salesman.js"></script>
<script src="jch_salesman.js"></script>
</head>
<body>
<!--
Welcome, fellow hacker. You may git-clone this puzzle from: http://github.com/zillabyte/puzzles
Happy coding, and may the odds be ever in your favor.
-->
<div id="graph"></div>
<div id="info">
<h1>Zillabyte</h1>
<p>
The Travelling Salesman Problem (TSP) tries to find the shortest path through a given graph, touching every point and returning to the starting position.
<br/>
<br/>
This is an NP-hard problem, and finding the best solution efficiently is one of the great challenges of Computer Science.
<br/>
<br/>
At Zillabyte, we like hard problems. We also like helping sales people. Can you implement a better solution to the TSP than we have here? If so, email your implementation (or a link) to <a href="mailto:[email protected]">[email protected]</a>
<br><br>
<a href='http://www.zillabyte.com/jobs'>zillabyte.com/jobs</a>
</p>
</div>
<script>
// Initialize
var renderer = new Renderer("#graph");
var graph_builder = new RandomGraphBuilder();
var graph = graph_builder.build_graph();
var harness = new Harness();
var start_point_id = "pt_0";
var bad_score;
var your_score;
var greedy_score;
// Render the graph
renderer.set_graph(graph);
// Our baseline implementation
var greedy_salesman = new GreedySalesman()
var greedy_plan = harness.run_algorithm(graph, start_point_id, greedy_salesman);
var greedy_score = harness.compute_plan_cost(graph, greedy_plan);
window.setTimeout(function() {renderer.start_plan(greedy_plan, "player_one");}, 2500)
console.log("*** Greedy Algorithm Total Distance: " + String(greedy_score));
// Your implementation. Uncomment to see a demonstration:
var your_salesman = new JCHSalesman(); // <-- REPLACE ME
var your_plan = harness.run_algorithm(graph, start_point_id, your_salesman);
your_score = harness.compute_plan_cost(graph, your_plan);
window.setTimeout(function() {renderer.start_plan(your_plan, "player_two");}, 2500)
console.log("*** YOUR Algorithm Total Distance: " + String(your_score));
// Their bad implementation. Uncomment to see a demonstration:
var bad_salesman = new SequentialSalesman(); // <-- REPLACE ME
var bad_plan = harness.run_algorithm(graph, start_point_id, bad_salesman);
bad_score = harness.compute_plan_cost(graph, bad_plan);
// window.setTimeout(function() {renderer.start_plan(bad_plan, "player_three");}, 2500)
console.log("*** BAD Algorithm Total Distance: " + String(bad_score));
// Congrats?
if( bad_score < greedy_score ) {
console.log("!!! There is nothing wrong with me... Something is wrong with the universe!");
}
if (your_score < greedy_score) {
console.log("*** BOOM! Nice job. You defeated our implementation. You should email [email protected] RIGHT NOW. A world of glory awaits you.");
} else if (your_score < bad_score) {
console.log("*** Consolation prize--you aren't worse than bad.");
} else {
console.log("*** Don't quit your day job.");
}
</script>
</body>
</html>