green button, one blue button and one red button.
Jenny is the operator of a large garbage disposal machine. It is a fairly simple machine and constitutes of only three buttons: OneGiven that initially n items are put in the machine, it will only destroy garbage in the three following ways:
Since Jenny is a lazy operator she wants to minimize the number of times she presses the buttons? What is the minimum number of times Jenny has to press the buttons in order to completely destroy 4 6 6 5 5 9 items?
Examples
As explicit examples for
n
=
1
0
items Jenny would have to do
4
button presses (
red
,
blue
,
blue
,
red
) to minimize the number of presses as shown below.
1
0
−
1
=
9
⟶
9
╱
3
=
3
⟶
3
╱
3
=
1
⟶
1
−
1
=
0
For
n
=
6
items the optimal solution is
3
presses (
blue
,
green
,
red
) or (
blue
,
red
,
red
)
6
╱
3
⟶
2
╱
2
⟶
1
−
1
=
0
or
6
╱
3
⟶
2
−
1
⟶
1
−
1
=
0
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
Heard a lot about dynamic programming and now I can see how powerful it is... I thought about learning it many a times but never tried it. This is a very nice problem emphasizing the usage of dynamic programming. Motivated by it I will be learning this tomorrow for sure.
Dynamic Programming is really nothing fancy but it is indeed powerful..It is very much like recursion(your solution) but it instead starts from the bottom up.
I've made some edits to the question. Can you review it for accuracy? Also changed the blue button to 2/3.
Thank you and yes it is accurate.
Here's my solution in Python:
The idea is to use decision trees where each node leads to its three children via 'blue' button, 'green' button and 'red' button respectively. A node represents the number of items left. Out goal is to find the shortest path leading to node representing 0 from the root node that represent all the items. Using this tree, Depth First Search can be used to find the shortest path possible to destroy all items or to reach node representing 0.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
|
This is a beautiful piece of code. It was only possible using Eric Grimson's code from 6.00x which is analogous to this one. Pay a visit to edx.org to learn this!
Nice,I will surely take a look at at that edx course!Also I think this could be faster with memoization .
I am learning about memoization. Here's I created a memoized version of my code but it always crashes with bigger numbers like 10000. Any guess why?
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 |
|
@Lokesh Sharma – It is probably because you are reaching too deep .if you build from the bottom up it will work
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
|
P.S-This is why DP is considered more superior. Here you always need smaller values to find a biggervalue. But there are many unnecessary smaller values you have to check. But if you use DP,a sort of inverted tree you build only from your essential smaller values to your required value.
@Thaddeus Abiy – What's DP?
@Lokesh Sharma – Dynamic Programming
@Thaddeus Abiy – This code with bottom to up works fine even for large inputs. Is that how DP is different from memoization? DP is bottom to top and memoization is up to bottom. Right?
@Lokesh Sharma – Yes that's the essence of it..but you dont need to call functions when you are doing DP,memoization opens the door for unnecessary function calls where as in DP the operaion is only done once..
@Thaddeus Abiy – Ok! Thanks man for all of this. I appreciate it.
<code> int min(int a, int b) {return (a<b)?a:b;}
int main() { int R[N]; R[0] = 0; int i,m,n; for (i=1; i<N; i++) { m = R[i-1]; if(i%2 == 0) m = min(m, R[i/2]); if(i%3 == 0) m = min(m, R[i/3]); R[i] = m+1; } cout << R[10]; return 0; } </code>
Hey guys, I can't give proper format to the code block! Can you help me?
Using some Mathematica, I decided to fool around with cases to avoid a depth-first search.
1 2 3 4 |
|
The results?
red
466558
presses: 1
green
233279
presses: 2
red
233278
presses: 3
green
116639
presses: 4
red
116638
presses: 5
green
58319
presses: 6
red
58318
presses: 7
green
29159
presses: 8
red
29158
presses: 9
green
14579
presses: 10
red
14578
presses: 11
green
7289
presses: 12
red
7288
presses: 13
green
3644
presses: 14
green
1822
presses: 15
red
1821
presses: 16
blue
607
presses: 17
red
606
presses: 18
blue
202
presses: 19
red
201
presses: 20
blue
67
presses: 21
red
66
presses: 22
blue
22
presses: 23
red
21
presses: 24
blue
7
presses: 25
red
6
presses: 26
blue
2
presses: 27
green
1
presses: 28
red
0
presses: 29
??? you can't assume that the operation that gives the lowest result is the best one... sometimes is best to subtract by 1 and then divide by 3 than directly divide by 2 for example. i could achieve the result with 21 steps, take a look at the iteration where there are 78 n left, it was best to divide by 2 and later divide by many 3s instead of dividing it by 3 and having to subtract by 1 many times later.
455669 - 1
455668 / 2
227834 / 2
113917 - 1
113916 / 3
37972 - 1
37971 / 3
12657 / 3
4219 - 1
4218 / 3
1406 / 2
703 - 1
702 / 3
234 / 3
78 / 2
39 / 3
13 - 1
12 / 3
4 - 1
3 / 3
1 - 1
0 done with 21 pushes
Problem states 466559 and you did for 455669.
I think the right answer is 27. 466599#466598#233279#233278#116639#116638#58319#58318#29159#29158#14579#14578#7289#7288#3644#1822#911#910#450#225#75#25#24#8#4#2#1#0
You used 466599, but the problem asked 466559
A breadth first search from 466559 till it finds 0
G = [[466559],0]
def new_layer(G):
gnew = []
for i in G[0]:
gnew.append(i-1)
if not i%2: gnew.append(i/2)
if not i%3: gnew.append(i/3)
return [gnew,G[1]+1]
while 0 not in G[0]:
G = new_layer(G)
print G[1]
Problem Loading...
Note Loading...
Set Loading...
If M ( n ) returns the minimum number of times Jenny presses buttons for n items. It can be defined recursively as:
M ( n ) = ⎩ ⎪ ⎨ ⎪ ⎧ m i n ( M ( n / 2 ) , M ( n − 1 ) ) , m i n ( M ( n / 3 ) , M ( n − 1 ) ) , m i n ( M ( n / 3 ) , M ( n − 1 ) , M ( n / 2 ) ) , if n is divisible by 2 if n is divisible by 3 if n is divisible by both 2 and 3
Where the function m i n ( a 0 , a 1 , a 2 . . . , a i ) returns the smallest a i .
But since direct implementation of recursive functions are usually very slow,we change this into a Dynamic Programming solution where M ( n ) is computed from bottom up.