Mathematical puzzles that train the programmer's brain Q05 Still paying cash?

Problem summary

Exchange 1000 yen into a combination of 500 yen coins, 100 yen coins, 50 yen coins, and 10 yen coins. However, the total number of coins is 15 or less.

Code Solve without thinking

#Q05 Are you still paying in cash?

combinations = [] #List of combinations
for c500 in range(3):
    for c100 in range(11):
        for c50 in range(16):
            for c10 in range(16):
                if c500 + c100 + c50 + c10 <= 15:
                    if c500 * 500 + c100 * 100 + c50 * 50 + c10 *10 == 1000:
                        combinations.append((c500, c100, c50, c10))
                
print(combinations)
print(len(combinations))

Code 2

Write with as few repetitions of for statements as possible

import itertools
import numpy as np

combinations = []
for c in list(itertools.product(list(range(16)), repeat=4)):
    m = np.array(list(c)) * np.array([500, 100, 50, 10])
    if np.sum(c) <= 15 and np.sum(m) == 1000:
        combinations.append(c)
        
print(combinations)
print(len(combinations))

The code has become shorter, but I don't think the processing speed has increased, and the readability has decreased, so it's just for reference. .. ..

What I want to say is that when processing around an array,

If you fish around, you will find tools that are easier to implement.

The following is a supplement to the tools used this time.

itertools.product Find the direct product of the array. You can use the repeat option to find the direct product with yourself. Returns an itertools object, but can be cast to a list. The following usage example.

import itertools

x = ['a', 'b']
y = ['c', 'd']
z = list(range(3)) #[0, 1, 2]

print(list(itertools.product(x, y))) 
#[('a', 'c'), ('a', 'd'), ('b', 'c'), ('b', 'd')]

print(list(itertools.product(x, repeat=2)))
#[('a', 'a'), ('a', 'b'), ('b', 'a'), ('b', 'b')]

print(list(itertools.product(z, repeat=2)))
#[(0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (1, 2), (2, 0), (2, 1), (2, 2)]

Four arithmetic operations of list in numpy

In a normal list, the + sign represents a concatenation of the list. Other operation symbols are errors. In numpy, if you connect the list with an operation symbol, the list of the result of operating the elements at the same position is returned.

import numpy as np

x = [1, 3, 5]
y = [2, 4, 6]

print(x + y) #[1, 3, 5, 2, 4, 6]
print(x - y) #error
print(x * y) #error
print(x / y) #error

print(np.array(x) + np.array(y)) # [ 3  7 11]
print(np.array(x) - np.array(y)) # [-1 -1 -1]
print(np.array(x) * np.array(y)) # [ 2 12 30]
print(np.array(x) / np.array(y)) # [0.5 0.75 0.83333333]

Recommended Posts

Mathematical puzzles that train the programmer's brain Q05 Still paying cash?
Mathematical puzzles that train the programmer's brain Q08 Excellent cleaning robot
Mathematical puzzle to train the programmer's brain Q04 Carving a stick
Mathematical puzzle to train the programmer's brain Q01 "Palindrome in decimal"
Mathematical puzzle to train the programmer's brain Q03 Turn the card over
Mathematical puzzle to train the programmer's brain Q06 (modified version) Collatz's prediction