Skip to content

Commit 1b7112d

Browse files
bradhansonbradhanson
committed
Added hard/city_traffic
1 parent 9b0f102 commit 1b7112d

File tree

2 files changed

+260
-0
lines changed

2 files changed

+260
-0
lines changed

‎hard/city_traffic.js

Lines changed: 166 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,166 @@
1+
/**
2+
* Using the JavaScript language, have the function cityTraffic(strArr) read
3+
* strArr which will be a representation of an undirected graph in a form
4+
* similar to an adjacency list. Each element in the input will contain an
5+
* integer which will represent the population for that city, and then that will
6+
* be followed by a comma separated list of its neighboring cities and their
7+
* populations (these will be separated by a colon). For example: strArr may be
8+
*
9+
* ["1:[5]", "4:[5]", "3:[5]", "5:[1,4,3,2]", "2:[5,15,7]", "7:[2,8]",
10+
* "8:[7,38]", "15:[2]", "38:[8]"]. This graph then looks like the following
11+
* picture:
12+
*
13+
* [Image of cities graph](https://i.imgur.com/5xbQDUY.jpg)
14+
*
15+
* Each node represents the population of that city and each edge represents a
16+
* road to that city. Your goal is to determine the maximum traffic that would
17+
* occur via a single road if everyone decided to go to that city. For example:
18+
* if every single person in all the cities decided to go to city 7, then via
19+
* the upper road the number of people coming in would be (8 + 38) = 46. If all
20+
* the cities beneath city 7 decided to go to it via the lower road, the number
21+
* of people coming in would be (2 + 15 + 1 + 3 + 4 + 5) = 30. So the maximum
22+
* traffic coming into the city 7 would be 46 because the maximum value of (30,
23+
* 46) = 46.
24+
*
25+
* Your program should determine the maximum traffic for every single city and
26+
* return the answers in a comma separated string in the format:
27+
* city:max_traffic,city:max_traffic,... The cities should be outputted in
28+
* sorted order by the city number. For the above example, the output would
29+
* therefore be: 1:82,2:53,3:80,4:79,5:70,7:46,8:38,15:68,38:45. The cities will
30+
* all be unique positive integers and there will not be any cycles in the
31+
* graph. There will always be at least 2 cities in the graph.
32+
*
33+
* https://www.coderbyte.com/results/bhanson:City%20Traffic:JavaScript
34+
*
35+
* @param {array} strArr
36+
* @return {string}
37+
*/
38+
function cityTraffic(strArr) {
39+
'use strict';
40+
41+
const graph = new Cities();
42+
43+
// Populate graph with nodes and connections
44+
const reverseConnections = [];
45+
strArr.forEach(city => {
46+
let [namePopulation, edges] = city.split(':');
47+
namePopulation = Number(namePopulation);
48+
edges = JSON.parse(edges);
49+
50+
const cityNode = graph.addNode(namePopulation);
51+
52+
edges.forEach(edge => {
53+
cityNode.addEdge(edge);
54+
// Cannot add bidirectional connections yet because not all nodes
55+
// are created at this time
56+
reverseConnections.push([edge, namePopulation]);
57+
});
58+
});
59+
60+
// Add bidirectional connections
61+
reverseConnections.forEach(connection => {
62+
const [nodeA, nodeB] = connection;
63+
graph.node(nodeA).addEdge(nodeB);
64+
});
65+
66+
const trafficData = [];
67+
68+
// Get max traffic of each city
69+
for (const city of graph) {
70+
const [namePopulation, cityNode] = city;
71+
const maxTraffic = graph.maxTrafficFromOneRoad(namePopulation);
72+
trafficData.push({ namePopulation, maxTraffic });
73+
}
74+
75+
trafficData.sort((a, b) => {
76+
return a.namePopulation - b.namePopulation;
77+
});
78+
79+
const trafficDataString = trafficData
80+
.map(city => `${city.namePopulation}:${city.maxTraffic}`)
81+
.join(',');
82+
83+
return trafficDataString;
84+
}
85+
86+
class Node {
87+
constructor(key) {
88+
this.key = key;
89+
this.edges = new Map();
90+
}
91+
92+
addEdge(key, weight = 1) {
93+
this.edges.set(key, weight);
94+
}
95+
96+
hasEdge(key) {
97+
return this.edges.has(key);
98+
}
99+
}
100+
101+
class Graph {
102+
constructor() {
103+
this.nodes = new Map();
104+
}
105+
106+
*[Symbol.iterator]() {
107+
const nodeItr = this.nodes[Symbol.iterator]();
108+
for (const node of nodeItr) {
109+
yield node;
110+
}
111+
}
112+
113+
addNode(key) {
114+
this.nodes.set(key, new Node(key));
115+
return this.node(key);
116+
}
117+
118+
node(key) {
119+
return this.nodes.get(key);
120+
}
121+
}
122+
123+
class Cities extends Graph {
124+
constructor() {
125+
super();
126+
}
127+
128+
maxTrafficFromOneRoad(key) {
129+
const city = this.node(key);
130+
131+
let edgeTraffic = [];
132+
city.edges.forEach((_, edgeKey) => {
133+
edgeTraffic.push(this.sumTrafficFromAllRoads(edgeKey, [key]));
134+
});
135+
136+
if (edgeTraffic.length === 0) {
137+
return 0;
138+
}
139+
140+
return Math.max(...edgeTraffic);
141+
}
142+
143+
sumTrafficFromAllRoads(key, visited = []) {
144+
const city = this.node(key);
145+
146+
visited = visited.slice();
147+
visited.push(key);
148+
149+
let edgeTraffic = [];
150+
city.edges.forEach((weight, edgeKey) => {
151+
if (!visited.includes(edgeKey)) {
152+
edgeTraffic.push(this.sumTrafficFromAllRoads(edgeKey, visited));
153+
}
154+
});
155+
156+
if (edgeTraffic.length === 0) {
157+
return key;
158+
}
159+
160+
const edgeSum = edgeTraffic.reduce((sum, val) => (sum += val), 0);
161+
162+
return edgeSum + key;
163+
}
164+
}
165+
166+
module.exports = cityTraffic;

‎hard/city_traffic.test.js

Lines changed: 94 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,94 @@
1+
const cityTraffic = require('./city_traffic');
2+
3+
describe('cityTraffic()', () => {
4+
test('passes Coderbyte.com tests', () => {
5+
expect(
6+
cityTraffic([
7+
'1:[5]',
8+
'4:[5]',
9+
'3:[5]',
10+
'5:[1,4,3,2]',
11+
'2:[5,15,7]',
12+
'7:[2,8]',
13+
'8:[7,38]',
14+
'15:[2]',
15+
'38:[8]'
16+
])
17+
).toBe('1:82,2:53,3:80,4:79,5:70,7:46,8:38,15:68,38:45');
18+
19+
expect(
20+
cityTraffic(['1:[5]', '2:[5]', '3:[5]', '4:[5]', '5:[1,2,3,4]'])
21+
).toBe('1:14,2:13,3:12,4:11,5:4');
22+
23+
expect(
24+
cityTraffic([
25+
'1:[5]',
26+
'2:[5,18]',
27+
'3:[5,12]',
28+
'4:[5]',
29+
'5:[1,2,3,4]',
30+
'18:[2]',
31+
'12:[3]'
32+
])
33+
).toBe('1:44,2:25,3:30,4:41,5:20,12:33,18:27');
34+
35+
expect(cityTraffic(['1:[12]', '12:[1]'])).toBe('1:12,12:1');
36+
37+
expect(
38+
cityTraffic(['4:[100]', '100:[4,67]', '67:[100,12]', '12:[67]'])
39+
).toBe('4:179,12:171,67:104,100:79');
40+
41+
expect(
42+
cityTraffic([
43+
'4:[100]',
44+
'100:[4,67]',
45+
'67:[100,12,89]',
46+
'12:[67]',
47+
'89:[67]'
48+
])
49+
).toBe('4:268,12:260,67:104,89:183,100:168');
50+
51+
expect(
52+
cityTraffic([
53+
'12:[4]',
54+
'82:[4]',
55+
'4:[12,82,90]',
56+
'90:[4,105]',
57+
'105:[90]'
58+
])
59+
).toBe('4:195,12:281,82:211,90:105,105:188');
60+
61+
expect(
62+
cityTraffic([
63+
'1:[2]',
64+
'3:[2]',
65+
'4:[2]',
66+
'2:[1,3,4,8]',
67+
'8:[2,67,14]',
68+
'67:[8]',
69+
'14:[8]'
70+
])
71+
).toBe('1:98,2:89,3:96,4:95,8:67,14:85,67:32');
72+
73+
expect(
74+
cityTraffic([
75+
'1:[5]',
76+
'4:[5]',
77+
'3:[5]',
78+
'5:[1,4,3,2]',
79+
'2:[5,15,7]',
80+
'7:[2,8]',
81+
'8:[7,38]',
82+
'15:[2]',
83+
'38:[8,104]',
84+
'104:[38]'
85+
])
86+
).toBe(
87+
'1:186,2:157,3:184,4:183,5:174,7:150,8:142,15:172,38:104,104:83'
88+
);
89+
90+
expect(cityTraffic(['56:[2]', '2:[56,12]', '3:[12]', '12:[2,3]'])).toBe(
91+
'2:56,3:70,12:58,56:17'
92+
);
93+
});
94+
});

0 commit comments

Comments
 (0)