Week 2
这周我们 ed 系统上有1个 Quiz 和5个 Challenges。
[TOC]
Quiz 2
这个 Quiz 依旧写好了输入输出的代码。
题目要求
See pdf and stub.
1.5 mark for cycles
1 mark for reversed dictionary
依旧，pdf 文档中给出了 test cases 和希望的输出结果。详情请见 Quiz 2 要求 -- OneDrive 分享 。
在 shell 中输入：
$ python3 quiz_2.py
Enter two integers: 20 11
期望得到的输出：
The generated mapping is:
{2: 4, 3: 9, 4: 4, 5: 8, 6: 2, 7: 5, 8: 11, 9: 1, 10: 10, 11: 5}
The keys are, from smallest to largest:
[2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
Properly ordered, the cycles given by the mapping are:
[[4], [5, 8, 11], [10]]
The (triply ordered) reversed dictionary per lengths is:
{1: {1: [9], 2: [6], 8: [5], 9: [3], 10: [10], 11: [8]},
2: {4: [2, 4], 5: [7, 11]}}
你需要做
- 寻找所有所谓的 Cycle
- Cycle 指的是，从字典中某一个 item 开始，将前一个 item 的 value 作为下一个 item 的 key，如此接龙之后可以最终回到第一个 item。
- 如果一个 item 的 value 等于其 key，那么这就是最小的一个 Cycle。
- 如果在寻找的过程中某一个 value，在字典中找不到与之相等的 key，那么显然就没法继续找下去了。
- 如果发现进入了一个 Cycle，但这个 Cycle 的起始不是我当前的起始值，并且绕不出来了，那么这个时候应当属于找错了循环。这时候应该输出的仅仅只有这个小的循环。
- 首先将字典倒序，也就是说，新的 key 为之前的 value，新的 value 为之前的 key。
- 这时候，有可能出现多个原来的 key(现在的value) 对映一个原来的 value(现在的key) 的情况，那么相当于在同一个新的 key 之下有多个新的 value。
- 将这个字典每个 key，按照对映了多少个 value，也就是所谓的 length 进行排序。
- 将结果整理输出。
代码实现
(by Harriet and Eric Martin, All Right Reserved)
Anyone who is plagiarisming, which include copying, Inappropriate paraphrasing, Collusion, Inappropriate citation, Self-plagiarism will undermine academic integrity and is not tolerated at UNSW.
# Written by Harriet and Eric Martin for COMP9021
import sys
from random import seed, randrange
from pprint import pprint
try:
arg_for_seed, upper_bound = (abs(int(x)) + 1 for x in input('Enter two integers: ').split())
except ValueError:
print('Incorrect input, giving up.')
sys.exit()
seed(arg_for_seed)
mapping = {}
for i in range(1, upper_bound):
r = randrange(-upper_bound // 8, upper_bound)
if r > 0:
mapping[i] = r
print('\nThe generated mapping is:')
print(' ', mapping)
# sorted() can take as argument a list, a dictionary, a set...
keys = sorted(mapping.keys())
print('\nThe keys are, from smallest to largest: ')
print(' ', keys)
cycles = []
reversed_dict_per_length = {}
# INSERT YOUR CODE HERE
#############################################################################
# Section 1
# This section is for cycles
#############################################################################
used_in_cycle = []
# Loop and try all elements in `mapping`
for i in keys:
tracking = i
used = []
flag = 0
used.append(i)
# If is a same cycle listed before, then jump to next `i`
# If not, do other things.
if i in used_in_cycle:
continue
else:
# Loop for cycles
while 1:
# If tracking can not move to next loop,
# this is not a cycle
# Record this in `flag` as wrong and break the while loop
if mapping[tracking] not in mapping:
flag = 0
break
# Move to next tracking
tracking = mapping[tracking]
# Getting into a wrong cycle
# Record this in `flag` as wrong and break while loop
if (tracking in used) and (tracking != i):
flag = 0
break
# If tracking equals to the original number `i`,
# this is a cycle.
# Record this in `flag` and break while loop
if tracking == i:
flag = 1
break
# If not correct and not recorded in used
# Record this `used` and continue finding
used.append(tracking)
# Check if this i is a correct valur for cycle
# If true, then append this in cycle
if flag:
cycles.append(used)
# And record all elements in this cycle
# into `used_in_cycle`.
# This is for avoiding outputing a same cycle
# for multiplied times.
for j in used:
if j not in used_in_cycle:
used_in_cycle.append(j)
else:
continue
#############################################################################
# Section 2
# This section is for reversed dictionary.
#############################################################################
value_key = {}
value_count = {}
# Take out the `keys` and `values` in original `mapping`.
# Then put `values:keys` into value_key
# also do counting for each `value` in original `mapping`.
for j, i in mapping.items():
# If this is a key-value pair in mapping
if mapping[j] == i:
# Also, if this value is a new value
if i not in value_key.keys():
value_key[i] = []
value_key[i].append(j)
value_count[i] = []
value_count[i] = 1
# if this value has appeared as `value_key.keys()`
else:
value_key[i].append(j)
value_count[i] += 1
# Collect all `values:keys` with same `value_count`
# into a same `value_count:{values:keys}`
# List all counting values in sorted way.
counting_used = sorted(value_count.values())
# Take out all values and its countings
for i, j in value_count.items():
# If this counting has not been appeared in `reversed_dict_per_length`
# Then we should add a new element.
if (value_count[i] == j) and (j not in reversed_dict_per_length.keys()):
reversed_dict_per_length[j] = {}
# In final result `reversed_dict_per_length`, for counting `j`,
# The `i`th subelement should be `value_key[i]`
reversed_dict_per_length[j][i] = value_key[i]
print('\nProperly ordered, the cycles given by the mapping are: ')
print(' ', cycles)
print('\nThe (triply ordered) reversed dictionary per lengths is: ')
pprint(reversed_dict_per_length)
