|
|
import json
|
|
|
from igraph import Graph, plot
|
|
|
|
|
|
with open('data.json', 'r', encoding='utf-8') as file:
|
|
|
data_raw = json.load(file)
|
|
|
data = json.loads(json.dumps(data_raw))
|
|
|
#数据补充
|
|
|
for node_name in data_raw:
|
|
|
node_info_raw = data_raw[node_name]
|
|
|
node_info = data[node_name]
|
|
|
for path_to in node_info_raw['path_to']:
|
|
|
is_key_need = 'key_need' in path_to
|
|
|
key_need = path_to['key_need'] if is_key_need else ''
|
|
|
is_one_way_door = key_need == '单向门'
|
|
|
is_one_way = not is_one_way_door and 'is_one_way' in path_to
|
|
|
if is_one_way_door:
|
|
|
if not 'key_get' in node_info:
|
|
|
node_info['key_get'] = []
|
|
|
is_key_need = True
|
|
|
key_need = f'单向门-{node_name}-{path_to['name']}'
|
|
|
node_info['key_get'].append(key_need)
|
|
|
node_info['path_to']
|
|
|
if not is_one_way:
|
|
|
target_node_info = data[path_to['name']]
|
|
|
append_path = {'name':node_name}
|
|
|
if is_key_need:
|
|
|
append_path['key_need'] = key_need
|
|
|
target_node_info['path_to'].append(append_path)
|
|
|
#多余数据删除
|
|
|
for node_name in data:
|
|
|
node_info = data[node_name]
|
|
|
for path_to in node_info['path_to']:
|
|
|
is_key_need = 'key_need' in path_to
|
|
|
key_need = path_to['key_need'] if is_key_need else ''
|
|
|
is_one_way_door = key_need == '单向门'
|
|
|
is_one_way = not is_one_way_door and 'is_one_way' in path_to
|
|
|
if is_one_way_door:
|
|
|
key_need = f'单向门-{node_name}-{path_to['name']}'
|
|
|
path_to['key_need'] = key_need
|
|
|
path_to.pop('is_one_way', None)
|
|
|
|
|
|
#BFS
|
|
|
start_node_name = '破碎遗迹'
|
|
|
end_node_name = '战斗-魂魄妖忌'
|
|
|
start_node = (start_node_name,set(),set(),[start_node_name],'') #name，key_get, key_use，path，portal
|
|
|
stack = [start_node]
|
|
|
close_set = set()
|
|
|
|
|
|
useless_node_list = []
|
|
|
useless_key_list = []
|
|
|
|
|
|
while True:
|
|
|
if len(stack)==0:
|
|
|
break
|
|
|
current = stack.pop(0)
|
|
|
current_name = current[0]
|
|
|
current_key_get = current[1]
|
|
|
current_key_use = current[2]
|
|
|
current_path = current[3]
|
|
|
current_portal = current[4]
|
|
|
|
|
|
if current_name == '白玉楼' and current_portal == '':
|
|
|
current_portal = current_name
|
|
|
|
|
|
if current_name == end_node_name:
|
|
|
useless_node = []
|
|
|
useless_key = []
|
|
|
for node_name in data:
|
|
|
if not node_name in current_path:
|
|
|
useless_node.append(node_name)
|
|
|
if 'key_get' in data[node_name]:
|
|
|
for key_get in data[node_name]['key_get']:
|
|
|
if not key_get in current_key_use:
|
|
|
useless_key.append(key_get)
|
|
|
useless_node_list.append(useless_node)
|
|
|
useless_key_list.append(useless_key)
|
|
|
continue
|
|
|
|
|
|
if 'key_get' in data[current_name]:
|
|
|
for key_get in data[current_name]['key_get']:
|
|
|
if not key_get in current_key_get:
|
|
|
current_key_get.add(key_get)
|
|
|
current_path.append(f'获取({key_get})')
|
|
|
|
|
|
for path_to in data[current_name]['path_to']:
|
|
|
is_key_need = 'key_need' in path_to
|
|
|
if is_key_need and not path_to['key_need'] in current_key_get:
|
|
|
continue
|
|
|
next_name = path_to['name']
|
|
|
current_key_list = list(current_key_get)
|
|
|
current_key_list.sort()
|
|
|
next_name_with_key = next_name + ':' + ','.join(current_key_list)
|
|
|
if next_name_with_key in close_set:
|
|
|
continue
|
|
|
close_set.add(next_name_with_key)
|
|
|
next_path = current_path.copy()
|
|
|
next_path.append(next_name)
|
|
|
next_key_use = current_key_use.copy()
|
|
|
if is_key_need and path_to['key_need'] in current_key_get:
|
|
|
next_key_use.add(path_to['key_need'])
|
|
|
next_node = (next_name, current_key_get.copy(), next_key_use, next_path, current_portal)
|
|
|
stack.insert(-1,next_node)
|
|
|
#传送
|
|
|
if current_name == '白玉楼' and not current_portal == '':
|
|
|
next_name = current_portal
|
|
|
current_key_list = list(current_key_get)
|
|
|
current_key_list.sort()
|
|
|
next_name_with_key = next_name + ':' + ','.join(current_key_list)
|
|
|
if next_name_with_key in close_set:
|
|
|
continue
|
|
|
close_set.add(next_name_with_key)
|
|
|
next_path = current_path.copy()
|
|
|
next_path.append(f'传送({next_name})')
|
|
|
next_node = (next_name, current_key_get.copy(), current_key_use.copy(), next_path, current_portal)
|
|
|
stack.insert(-1,next_node)
|
|
|
|
|
|
if not current_name == '白玉楼' and not current_portal == '':
|
|
|
next_name = '白玉楼'
|
|
|
current_key_list = list(current_key_get)
|
|
|
current_key_list.sort()
|
|
|
next_name_with_key = next_name + ':' + ','.join(current_key_list)
|
|
|
if next_name_with_key in close_set:
|
|
|
continue
|
|
|
close_set.add(next_name_with_key)
|
|
|
next_path = current_path.copy()
|
|
|
next_path.append(f'传送({next_name})')
|
|
|
next_node = (next_name, current_key_get.copy(), current_key_use.copy(), next_path, current_name)
|
|
|
stack.insert(-1,next_node)
|
|
|
|
|
|
success_count = len(useless_node_list)
|
|
|
key_set = set()
|
|
|
useless_node_dict = {}
|
|
|
useless_key_dict = {}
|
|
|
for node_name in data:
|
|
|
useless_node_dict[node_name] = 0
|
|
|
if 'key_get' in data[node_name]:
|
|
|
for key_get in data[node_name]['key_get']:
|
|
|
if not key_get in key_set:
|
|
|
key_set.add(key_get)
|
|
|
useless_key_dict[key_get] = 0
|
|
|
node_max = len(data)
|
|
|
key_max = len(key_set)
|
|
|
|
|
|
for useless_node in useless_node_list:
|
|
|
for key in useless_node:
|
|
|
useless_node_dict[key] += 1
|
|
|
|
|
|
for useless_key in useless_key_list:
|
|
|
for key in useless_key:
|
|
|
useless_key_dict[key] += 1
|
|
|
|
|
|
useless_node_count_sum = sum(map(lambda x: len(x), useless_node_list))
|
|
|
print('success_count:', success_count)
|
|
|
print('useless_node_avg:', "{:.2f}%".format(useless_node_count_sum / success_count / node_max * 100))
|
|
|
|
|
|
for useless_node in useless_node_dict:
|
|
|
print("{} {:.2f}%".format(useless_node,useless_node_dict[useless_node] / success_count * 100))
|
|
|
|
|
|
print("-"*20)
|
|
|
for useless_key in useless_key_dict:
|
|
|
print("{} {:.2f}%".format(useless_key,useless_key_dict[useless_key] / success_count * 100))
|
|
|
|