CoCalc Public FilesPackets of buttons.ipynbOpen with one click!
Author: Julia Burnside
Views : 46
Compute Environment: Ubuntu 20.04 (Default)

Packets of Buttons

The function buttonsbuttons has 88 base cases which are the minimum number of packets to purchase for nn buttons where 0n70\leqslant{n}\leqslant{7}.

L(0)=0L(0) = 0

L(1)=1L(1) = 1

L(2)=2L(2) = 2

L(3)=3L(3) = 3

L(4)=1L(4) = 1

L(5)=2L(5) = 2

L(6)=3L(6) = 3

L(7)=1L(7) = 1

For a number of buttons n>7n>7, the vector LL is appended with the minimum value of the base cases LL after having subtracted the packet sizes 1, 4,& 71,\ 4,\&\ 7 from nn, incrementing the total number of packets ii but 11 in each iteration with the condition that ini\leqslant{n}.

It then returns the final value of the vector LL.

In [53]:
def buttons(n): L = [0, 1, 2, 3, 1, 2, 3, 1] if n > 7: i = 8 while i <= n: L.append(min(L[i-7],L[i-4],L[i-1])+1) i += 1 return L[-1] print('Minimum Packets: ', buttons(20))
Minimum Packets: 5

The Greedy Method

Alternatively, a greedy algorithm does actually works for n=20n=20 buttons although it will not work for all values of nn. The function greedyButtonsgreedyButtons calculates the minimum number of packets required to purchase for nn buttons with 33 base cases:

n>=7n>=7

n>=4n>=4

n>=1n>=1

The function returns a vector with the required number of each sized packet. The sum of this vector is the total minimum number of packets required to purchase to have 2020 buttons.

In [54]:
def greedyButtons(n): B=[0, 0, 0] while n>=7: n=n-7 B[0]+=1 while n>=4: n=n-4 B[1]+=1 while n>=1: n=n-1 B[2]+=1 return B P=greedyButtons(20) print('Packets of 7: ', P[0], '\nPackets of 4: ', P[1], '\nPackets of 1: ', P[2], '\nMinimum Packets: ', sum(P))
Packets of 7: 2 Packets of 4: 1 Packets of 1: 2 Minimum Packets: 5