Python3 ２重リスト 中身の重複

Question

目標)

初めてのおつかいを応援するアプリをつくりたい。

子どもに、今日作りたい料理のレシピの具材を買ってきてもらいます。
あなたの料理レシピには、1人前を調理するのに必要な食材とその量のみ載っています。

子どもが買ってきた食材とその量が与えられるので、今日作りたい料理のレシピが最大で何人前作れるかを求めてください。

入力される値
入力は以下のフォーマットで与えられます。

n　　　　　#レシピに書かれている食材の数を表す整数 n
a_1 b_1　　#レシピに書かれている食材の名前 a_1, 数 b_1
a_2 b_2　　#レシピに書かれている食材の名前 a_2, 数 b_2
...
a_n b_n　　#レシピに書かれている食材の名前 a_n, 数 b_n
m　　　　　#あなたが所持している食材の数を表す整数 m
c_1 d_1　　#所持している食材の名前 c_1, 数 d_1
c_2 d_2　　#所持している食材の名前 c_2, 数 d_2
...
c_m d_m　　#所持している食材の名前 c_m, 数 d_m
ここで、n はレシピに書かれている食材の数を表す整数
文字列 a_i と整数 b_i (1 ≦ i ≦ n) は、1人前あたりの食材 a_i が b_i だけ必要であることを表します。

同様に、m はあなたが所持している食材の数を表す整数
文字列 c_i と整数 d_i (1 ≦i ≦ m) は、食材 c_i を d_i だけ所持していることを表します。

それぞれの値は文字列で標準入力から渡されます。標準入力からの値取得方法はこちらをご確認ください
期待する出力
何人前作ることができるかを数字で一行に出力してください。

最後は改行し、余計な文字、空行を含んではいけません。
条件
すべてのテストケースで以下の条件を満たします。

・1 ≦ n ≦ 100
・0 ≦ m ≦ 100
・1 ≦ a_i の長さ, c_i の長さ ≦ 10
・1 ≦ b_i ≦ 100
・1 ≦ d_i ≦ 10,000
・i ≠ j のとき a_i ≠ a_j
・i ≠ j のとき c_i ≠ c_j

入力例1
4
supaisu 5
imo 2
niku 2
mizu 3
6
mizu 7
imo 4
ninjin 10
unagi 6
supaisu 20
niku 5

出力例1
2

入力例2
2
gohan 1
okazu 1
1

mizu 10000
出力例2
0

解釈)

まず、食材の名前と量を比較したい

絶対条件として、レシピの食材がすべてそろっていることが必要

次に、それぞれの食材の量比較

量の多さによって、１人前、２人前....をわけたい。

私のコード）

共通の食材をリストアップする

共通の食材の品目とレシピの食材の品目が一致すれば、絶対条件クリア

上記の二つの条件はコードかけた。

それぞれの食材の量を比較する以降がコードで書けない。

質問)

初心者のため、時間をかけてでも自力と解きたいと思っていますが、前に進めません。

ヒント等のお力添え頂ければ幸いです。

コード

N = int(input())
menu = [list(map(str,input().split())) for x in range(N)]
print(menu)    
print(len(menu))
    
M = int(input())
own = [list(map(str,input().split())) for _ in range(M)]
print(own)    

common_goods = []
for i in range(N):
    if menu[i][0] in own[i][0]:
        print(menu[i])
        common_goods.append(menu[i])
        if len(common_goods) == len(menu):
            print('OK')
        else:
            print('NG')

can110 さんの回答を受けての追記質問

以下のコードの☆の部分が質問内容です。

コード


recipe = {'apple': 2, 'bread': 1} 
stok = {'bread': 11, 'apple': 20, 'orange': 15} 

min_dish = 10000#最大所持量 / 最小レシピ量より

for food, amount in recipe.items():
    # 持っていない
    if food not in stok:
        min_dish = 0
        break
    # 何人前作れるか。ただし最小に制限される
    dish = int(stok[food] / amount)
    # dish = 10, 11
☆質問部分
　　if dish < min_dish:
        min_dish = dish
        # min_Dish = 10
    # ０人前ならこれ以上探しても意味がない
    if min_dish <= 0:
        break

print(min_dish)


出力値

10



質問内容

☆　dish=10,11

    どちらの数字も dish < min_dish(10000)に該当する
　　10,11では求めたい数字は最小の10

   10,11でもどちらでも成立してしまうのでは....

　　なぜ、min_dish = dish の式で
　　10,11　のふたつの内最小の数が最後に残るのかが理解できません。

 　dishのリストを作成し、min()最小値を求める方がより正確のではと思ったのですが、結果はどちらとも正常でした。

　　重ね重ね質問申し訳ありません。お時間がある時で構いませんのでお返事頂けたら幸いです。


# dish < min_dish の集めるリスト作成
ans = []

for food, amount in recipe.items():
    # 持っていない
    if food not in stok:
        min_dish = 0
        break
    # 何人前作れるか。ただし最小に制限される
    dish = (int(stok[food] / amount))
    ans.append(dish)
 #   print('dish is ', dish)
    if dish < min_dish:
        min_dish = min(ans)
 #       print('min_dish is ',min_dish)
    # ０人前ならこれ以上探しても意味がない
    if min_dish <= 0:
        break

print(min_dish)

Answer 1

・i ≠ j のとき a_i ≠ a_j

・i ≠ j のとき c_i ≠ c_j

より、レシピと所持分それぞれの中では、相異なる同じ食材が複数回登場することはないので
レシピの全食材について所持分の量 / レシピでの必要量(少数切り捨て) の最小を求めればよいのではないでしょうか？
ただし途中で１人前すら作れないことが分かれば探索終了できます。

recipe = {'supaisu':5, 'imo':2, 'niku':2, 'mizu':3}
stok = {'mizu':7,'imo':4,'ninjin':10,'unagi':6,'supaisu':20,'niku':5}

min_dish = 10000 #最大所持量 / 最小レシピ量より
for food, amount in recipe.items():
	# 持っていない
	if food not in stok:
		min_dish = 0
		break
	# 何人前作れるか。ただし最小に制限される
	dish = int(stok[food] / amount)
	if dish < min_dish:
		min_dish = dish
	# ０人前ならこれ以上探しても意味がない
	if min_dish <= 0:
		break

print(min_dish)

Comments

[python3_beginer]

お返事ありがとうございます。

数学的発想がとても勉強になりました。

コードに関して１点理解できないところがありまして、恐縮ですが追記で質問致しました。
重ね重ねすみません。

[can110]

min_dishの値は毎回if文ですでに保持している最小値と比較、更新していることに注目してください。
各材料で何人前できるかを[1,2]のようにあらわした場合、ループ毎のmin_dishの値の変化は
[11,10] なら (10000) -> 11 -> 10
[10,11] なら (10000) -> 10 -> 10(11は無視される)
となります。

[python3_beginer]

「毎回if文ですでに保持している最小値と比較、更新している」の考えが抜けておりました。
丁寧な説明ありがとうございます。初心者の私でも理解することができました。
ご指導ありがとうございました。

Answer 2

やはり辞書を使うのがよさそうですね。
pythonコードではありませんが、流れを記述してみましたので参考にしてください。
【訂正】よく考えたらロジックが間違っていたので修正しました。

recipe（レシピ）の入力（辞書として作成）

material（材料）の入力（辞書として作成）

recipeの入力データをチェック。不正ならエラー終了。

materialの入力データをチェック。不正ならエラー終了。

goods_counter = 0 # 作成数

while True: # ループ１

    材料を消費する（recipeのキーで回す。for recipe_key in recipe.keys()） # ループ２
        キー recipe_key が material に存在しなければ、調理できないのでループ１を脱出。
        個々の材料を消費する（recipe_keyキーのmaterialの値から、そのキーのrecipeの値を引く）
        （material[recipe_key] -= recipe[recipe_key]）

    調理可能の判断（material のキーで回す。for material_key in material.keys()）# ループ３
        キー material_key の材料の値がマイナスなら、調理できなかったのでループ１を脱出。

    作成数をカウントアップ

作成数を出力

Answer 3

例によって、とりあえず書いてみた。collections.defaultdictが活躍します。

from collections import defaultdict

#
n = int(input())
recipe = dict()

for _ in range(n):
    n, v = input().split()
    recipe[n] = int(v)

#
m = int(input())
ingredients = defaultdict(int)

for _ in range(m):
    n, v = input().split()
    ingredients[n] = int(v)

#
print(min(
    ingredients[n] // recipe[n] for n in recipe
))

Wandbox

ご提示のコードについて

まず気になったのは次の点です。

for i in range(N):
if menu[i][0] in own[i][0]:

menu[i]の食材とown[i]の食材がたまたま被ることに依存しています。
実現の仕方はいろいろあるとは思いますが、やはりこのようなデータは辞書で扱うのが自然かと。

ところで

いつも題材はどこから引っ張ってきているのでしょう？

Comments

[python3_beginer]

お返事ありがとうございます。
便利な処理があるのですね、勉強になりました！

海外のサイトの問題集や、勉強会で知り合った人に出された問題です。
英語なので私が和訳しています。
日本語が読みづらくてすみません。

[LouiS0616]

collectionsとitertoolsは一通り目を通す価値があるかと思います。
私も気が向いたときにしばしば眺めています。

---
なるほど。
どこかサイトの問題を利用する場合は、引用元のリンクを貼っておくとスムーズかと思います。