جواب «Try It in Python: The Fewest Colours» چالش 7 از جلسهی 25
سؤال
«با پایتون امتحان کن» (اختیاری). یک گراف با n رأس (از ۱ تا ۶) داریم. کمترین تعدادِ رنگی را پیدا کن که بشود رأسها را طوری رنگ کرد که دو سرِ هیچ یالی همرنگ نباشند. خطِ اول n است، خطِ دوم تعدادِ یالها، و بعد هر یال در یک خط (دو شماره از ۱ تا n).
k را از ۱ بالا ببر و برای هر k همهی رنگآمیزیها را با product(range(k), repeat=n) امتحان کن.
برای یک مثلث (3، 3، 1 2، 2 3، 1 3) باید 3 چاپ شود.
راهنما
یک رنگآمیزی خوب است اگر all(colours[a] != colours[b] for a, b in edges). وقتی پیدا شد، found = True و break.
یک جواب درست
from itertools import product
n = int(input())
m = int(input())
edges = [tuple(int(x) - 1 for x in input().split()) for _ in range(m)]
k = 1
while True:
found = False
for colours in product(range(k), repeat=n):
if all(colours[a] != colours[b] for a, b in edges):
found = True
break
if found:
break
k += 1
print(k)
اول خودت امتحان کن؛ جوابهای دیگر هم قبول است. برگرد و خودت حلش کن