Don't push my buttons!

Jenny is the operator of a large garbage disposal machine. It is a fairly simple machine and constitutes of only three buttons: One green \color{#20A900} {\text{green}} button, one blue \color{#3D99F6} {\text{blue}} button and one red \color{#D61F06} {\text{red}} button.

Given that initially n n items are put in the machine, it will only destroy garbage in the three following ways:

  • The green \color{#20A900} {\text{green}} button, if pressed destroys 1 2 \frac{1}{2} of the items,leaving n 2 \frac{n}{2} of the items, but it only works if the number of items n n is divisible by 2. 2.
  • The blue \color{#3D99F6} {\text{blue}} button,if pressed destroys 2 3 \frac{2}{3} of the items,leaving n 3 \frac{n}{3} items, but it only works if the number of items n n is divisible by 3. 3.
  • The red \color{#D61F06} {\text{red}} button always works and destroys only 1 1 item leaving n 1 n-1 if pressed.

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 466559 466559 items?

Examples
As explicit examples for n = 10 n=10 items Jenny would have to do 4 4 button presses ( red \color{#D61F06} {\text{red}} , blue \color{#3D99F6} {\text{blue}} , blue \color{#3D99F6} {\text{blue}} , red \color{#D61F06} {\text{red}} ) to minimize the number of presses as shown below.
10 1 = 9 10-1=9 \longrightarrow 9 3 = 3 9\diagup 3=3 \longrightarrow 3 3 = 1 3\diagup3=1 \longrightarrow 1 1 = 0 1-1=0

For n = 6 n=6 items the optimal solution is 3 3 presses ( blue \color{#3D99F6} {\text{blue}} , green \color{#20A900} {\text{green}} , red \color{#D61F06} {\text{red}} ) or ( blue \color{#3D99F6} {\text{blue}} , red \color{#D61F06} {\text{red}} , red \color{#D61F06} {\text{red}} )
6 3 2 2 1 1 = 0 6\diagup 3 \longrightarrow 2 \diagup 2 \longrightarrow 1 - 1=0 or 6 3 2 1 1 1 = 0 6\diagup 3 \longrightarrow 2 - 1 \longrightarrow 1 - 1=0


The answer is 29.

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.

5 solutions

Discussions for this problem are now closed

Thaddeus Abiy
Apr 16, 2014

If M ( n ) M(n) returns the minimum number of times Jenny presses buttons for n n items. It can be defined recursively as:

M ( n ) = { m i n ( M ( n / 2 ) , M ( n 1 ) ) , if n is divisible by 2 m i n ( M ( n / 3 ) , M ( n 1 ) ) , if n is divisible by 3 m i n ( M ( n / 3 ) , M ( n 1 ) , M ( n / 2 ) ) , if n is divisible by both 2 and 3 M(n) = \begin{cases} min(M(n/2),M(n-1)), & \text{if }n\text{ is divisible by 2} \\ min(M(n/3),M(n-1)), & \text{if }n\text{ is divisible by 3}\\ min(M(n/3),M(n-1),M(n/2)), & \text{if }n\text{ is divisible by both 2 and 3} \end{cases}

Where the function m i n ( a 0 , a 1 , a 2 . . . , a i ) min(a_{0},a_{1},a_{2}...,a_{i}) returns the smallest a i a_{i} .

But since direct implementation of recursive functions are usually very slow,we change this into a Dynamic Programming solution where M ( n ) M(n) is computed from bottom up.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
M = {0:0} # Previous values of M(n) are stored
for N in range(1,466559 + 1):
    Possible = [] #A list of possible values for M(n)
    if N%2 == 0: 
        Possible.append(M[N/2])
    if N%3 == 0:
        Possible.append(M[N/3])
    Possible.append(M[N-1])
    M[N] = min(Possible) + 1

print M[466559]

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.

Lokesh Sharma - 7 years, 1 month ago

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.

Thaddeus Abiy - 7 years, 1 month ago

I've made some edits to the question. Can you review it for accuracy? Also changed the blue button to 2/3.

Calvin Lin Staff - 7 years, 1 month ago

Thank you and yes it is accurate.

Thaddeus Abiy - 7 years, 1 month ago
Lokesh Sharma
Apr 16, 2014

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
def pressMeNot(items, buttonsPressed = 0, best = None):
    '''
    Returns minimum no of buttons to
    be pressed to destory all items.
    '''
    if items == 0:
        return buttonsPressed
    buttonsPressed += 1
    for button in ['green', 'blue', 'red']:
        if best == None or buttonsPressed < best:
            if items%2 == 0 and button == 'green':
                best = pressMeNot(items/2, buttonsPressed, best)
            elif items%3 == 0 and button == 'blue':
                best = pressMeNot(items/3, buttonsPressed, best)
            elif button == 'red':
                best = pressMeNot(items-1, buttonsPressed, best)
    return best

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!

Lokesh Sharma - 7 years, 1 month ago

Nice,I will surely take a look at at that edx course!Also I think this could be faster with memoization .

Thaddeus Abiy - 7 years, 1 month ago

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
import sys
sys.setrecursionlimit(900000)

def pressMe2(n): # This is unmemoized
    if n == 0:
        return 0
    best = [1+pressMe2(n-1)] # Red button pressed
    if n%3 == 0:
        best.append(1+pressMe2(n/3)) # Green button pressed
    if n%2 == 0:
        best.append(1+pressMe2(n/2)) # Blue button pressed
    return min(best)


def pressMe3(n, memo = {}): # This is memoized
    if n == 0:
        return 0
    if n in memo:
        return memo[n]
    best = [1+pressMe2(n-1)] # Red button pressed
    if n%3 == 0:
        best.append(1+pressMe2(n/3)) # Green button pressed
    if n%2 == 0:
        best.append(1+pressMe2(n/2)) # Blue button pressed
    memo[n] = min(best)
    return memo[n]

Lokesh Sharma - 7 years, 1 month ago

@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
memo = {}
def pressMe3(n): # This is memoized
    if n == 0:
        return 0
    if n in memo:
        return memo[n]
    best = [1+pressMe3(n-1)] # Red button pressed
    if n%3 == 0:
        best.append(1+pressMe3(n/3)) # Green button pressed
    if n%2 == 0:
        best.append(1+pressMe3(n/2)) # Blue button pressed
    memo[n] = min(best)
    return memo[n]
for n in range(1,10001):
    pressMe3(n)
print memo[10000]

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 - 7 years, 1 month ago

@Thaddeus Abiy What's DP?

Lokesh Sharma - 7 years, 1 month ago

@Lokesh Sharma Dynamic Programming

Thaddeus Abiy - 7 years, 1 month ago

@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 - 7 years, 1 month ago

@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 - 7 years, 1 month ago

@Thaddeus Abiy Ok! Thanks man for all of this. I appreciate it.

Lokesh Sharma - 7 years, 1 month ago
Andrea Marino
Apr 25, 2014

<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?

Michael Lee
Apr 24, 2014

Using some Mathematica, I decided to fool around with cases to avoid a depth-first search.

1
2
3
4
pressred[i_] := (Print[Style[red, Red]]; n[i + 1] = n[i] - 1; Print[n[i + 1]]; Print["presses: ", i + 1])
pressblue[i_] := (Print[Style[blue, Blue]]; n[i + 1] = n[i]/3; Print[n[i + 1]]; Print["presses: ", i + 1])
pressgreen[i_] := (Print[Style[green, Green]]; n[i + 1] = n[i]/2; Print[n[i + 1]]; Print["presses: ", i + 1])
destroy[q_] := (n[0] = q; i = 0; While[n[i] > 0, If[Mod[n[i], 3] == 0, (pressblue[i]; i++), If[Mod[n[i], 3] == 1, (pressred[i]; i++; If[n[i] != 0, (pressblue[i]; i++)]), If[Mod[n[i], 2] == 0, (pressgreen[i]; i++), If[Mod[n[i], 2] == 1, (pressred[i]; i++; pressgreen[i]; i++)]]]]]) 

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

Bruno Osorio - 7 years, 1 month ago

Problem states 466559 and you did for 455669.

Akash Shah - 7 years, 1 month ago

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

Dushyant Janu - 7 years, 1 month ago

You used 466599, but the problem asked 466559

Silent Trailblazer - 7 years, 1 month ago

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]

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...