Login
curiouser

curiouser / cakeThief.js

Last active 3 days ago

Like 0

A solution to this code challenge: https://www.interviewcake.com/question/javascript/cake-thief

curiouser revised this gist 10 years ago · 5044cb2

1 file changed, 1 insertion, 1 deletion

cakeThief.js
@@ -41,7 +41,7 @@ function maxDuffelBagValue (cakeTypes, capacity) {
41 41 smallestCake = getSmallestCakeType(validCakeTypes);
42 42
43 43 // until we don't have enough weight left, find the most valuable cake
44 - for (capacityLeft = capacity; capacityLeft >= smallestCake.weight; capacityLeft = bag.getCapacityRemaining()) {
44 + for (var capacityLeft = capacity; capacityLeft >= smallestCake.weight; capacityLeft = bag.getCapacityRemaining()) {
45 45 // reduce our cakeTypes to the index of the highest value density that can fit
46 46 let bestCake = validCakeTypes.reduce((prev, next) => {
47 47 // make sure this next cake will fit

curiouser revised this gist 10 years ago · 84dffe7

1 file changed, 1 insertion, 5 deletions

cakeThief.js
@@ -35,14 +35,13 @@ let cakeTypes = [
35 35
36 36 function maxDuffelBagValue (cakeTypes, capacity) {
37 37 let bag = new Bag(capacity),
38 - capacityLeft = capacity,
39 38 // clean our cake types to cover out of bounds values
40 39 validCakeTypes = cleanCakeTypes(cakeTypes),
41 40 // figure out what the smallest cake is
42 41 smallestCake = getSmallestCakeType(validCakeTypes);
43 42
44 43 // until we don't have enough weight left, find the most valuable cake
45 - while (capacityLeft >= smallestCake.weight) {
44 + for (capacityLeft = capacity; capacityLeft >= smallestCake.weight; capacityLeft = bag.getCapacityRemaining()) {
46 45 // reduce our cakeTypes to the index of the highest value density that can fit
47 46 let bestCake = validCakeTypes.reduce((prev, next) => {
48 47 // make sure this next cake will fit
@@ -56,9 +55,6 @@ function maxDuffelBagValue (cakeTypes, capacity) {
56 55
57 56 // add the cake to our bag (adding to its weight and value)
58 57 bag.addCake(bestCake);
59 -
60 - // re-calculate our remaining cake capacity
61 - capacityLeft = bag.getCapacityRemaining();
62 58 }
63 59
64 60 return bag.getValue();

curiouser revised this gist 10 years ago · 5b3ca42

1 file changed, 84 insertions

cakeThief.js (file created)
@@ -0,0 +1,84 @@
1 + class Bag {
2 + constructor (capacity) {
3 + this.capacity = capacity;
4 + this.cakes = [];
5 + this.weight = 0;
6 + this.value = 0;
7 + }
8 +
9 + addCake (cake) {
10 + this.cakes.push(cake);
11 + this.value += cake.value;
12 + this.weight += cake.weight;
13 + }
14 +
15 + getCapacityRemaining () {
16 + return this.capacity - this.getWeight();
17 + }
18 +
19 + getValue () {
20 + return this.value;
21 + }
22 +
23 + getWeight () {
24 + return this.weight;
25 + }
26 + }
27 +
28 + let cakeTypes = [
29 + {weight: 7, value: 160},
30 + {weight: 3, value: 90},
31 + {weight: 1, value: 15}
32 + ];
33 +
34 + // maxDuffelBagValue(cakeTypes, 20);
35 +
36 + function maxDuffelBagValue (cakeTypes, capacity) {
37 + let bag = new Bag(capacity),
38 + capacityLeft = capacity,
39 + // clean our cake types to cover out of bounds values
40 + validCakeTypes = cleanCakeTypes(cakeTypes),
41 + // figure out what the smallest cake is
42 + smallestCake = getSmallestCakeType(validCakeTypes);
43 +
44 + // until we don't have enough weight left, find the most valuable cake
45 + while (capacityLeft >= smallestCake.weight) {
46 + // reduce our cakeTypes to the index of the highest value density that can fit
47 + let bestCake = validCakeTypes.reduce((prev, next) => {
48 + // make sure this next cake will fit
49 + if (next.weight <= capacityLeft) {
50 + // decide which is higher value-weight ratio
51 + return prev.value / prev.weight > next.value / next.weight ? prev : next;
52 + }
53 + // this next cake doesn't fit, keep the previous
54 + else return prev;
55 + }, {value: 0, weight: 1});
56 +
57 + // add the cake to our bag (adding to its weight and value)
58 + bag.addCake(bestCake);
59 +
60 + // re-calculate our remaining cake capacity
61 + capacityLeft = bag.getCapacityRemaining();
62 + }
63 +
64 + return bag.getValue();
65 + }
66 +
67 + /**
68 + * reduce our cakeType collection down to one with the lowest weight
69 + * @param {array} cakeTypes - collection of cakeType object {weight, value}
70 + * @return {object} cakeType
71 + */
72 + function getSmallestCakeType (cakeTypes) {
73 + return cakeTypes.reduce((prev, next) => prev.weight < next.weight ? prev : next);
74 + }
75 +
76 + /**
77 + * cleanCakeTypes - filters out invalid cakeTypes
78 + * @param {array} cakeTypes - collection of cakeType object {weight, value}
79 + * @return {array} filtered collection of cakeType objects
80 + */
81 + function cleanCakeTypes (cakeTypes) {
82 + // filter out any cake types with weight or value of 0, that's unreal!
83 + return cakeTypes.filter((type) => type.weight > 0 && type.value > 0);
84 + }