جواب «Try It in Python: Count the Groups» چالش 7 از جلسهی 36
سؤال
«با پایتون امتحان کن» (اختیاری). خطِ اول n است و خطِ دوم line (شهرهای ۱ تا n پشتِ سرِ هم در یک خط) یا star (شهرِ ۱ به همهی شهرها جاده دارد). با امتحانِ همهی گروهها بشمار چند گروهِ بههمپیوسته هست و چاپ کن.
تابعِ connected(group) آماده است؛ تو فقط همهی گروهها را بساز. راه: عددهای 1 تا 2 ** n - 1 را بشمار؛ بیتِ k اُمِ عدد یعنی شهرِ k + 1 در گروه هست.
با 4 و line باید 10 چاپ شود.
راهنما
for mask in range(1, 2 ** n): و داخلش group = {k + 1 for k in range(n) if mask >> k & 1}.
یک جواب درست
n = int(input())
shape = input()
if shape == "line":
roads = [(k, k + 1) for k in range(1, n)]
else:
roads = [(1, k) for k in range(2, n + 1)]
def connected(group):
start = min(group)
seen = {start}
stack = [start]
while stack:
v = stack.pop()
for a, b in roads:
for x, y in ((a, b), (b, a)):
if x == v and y in group and y not in seen:
seen.add(y)
stack.append(y)
return seen == group
count = 0
for mask in range(1, 2 ** n):
group = {k + 1 for k in range(n) if mask >> k & 1}
if connected(group):
count += 1
print(count)
اول خودت امتحان کن؛ جوابهای دیگر هم قبول است. برگرد و خودت حلش کن