#!/usr/bin/env python3 # # Testing tool for the "Dungeon Dawdler" problem from NCPC 2019. # # Usage: # # python testing_tool.py [-f map_file] # # If the -f parameter is not specified, the map from Sample # Interaction 1 will be used. Otherwise, map_file should be a file # containing a map in the same format as the problem output format. # # For example, if you have a Java solution that you would run using # "java MyClass", you could invoke the testing tool with: # # python testing_tool.py java MyClass # # Note that this tool does not make a complete check that the map you # provide it with is valid (for instance it does not check that the # map is connected without dead ends). # # The tool is provided as-is, and you should feel free to make # whatever alterations or augmentations you like to it. # import argparse import subprocess import sys MAX_STEPS = 10**5 DEFAULT_MAP = ''' ####### #b.SAB# #####a# ####### '''.split() DIRECTIONS = {'N': (-1, 0), 'E': (0, 1), 'S': (1, 0), 'W': (0, -1)} def error(msg): print('ERROR: %s' % msg) sys.exit(1) def get_surroundings(MAP, r, c): return ''.join('#' if MAP[nr][nc] == '#' else '.' for (nr, nc) in [(r-1, c), (r, c+1), (r+1, c), (r, c-1)]) def check_map(MAP): flatmap = ''.join(MAP) if flatmap.count('S') != 1: error('map must have exactly one "S"') if flatmap.count('A') > 1: error('map must have at most one "A"') if flatmap.count('a') != flatmap.count('A'): error('map must have same number of "a" as "A"') if flatmap.count('B') > 1: error('map must have at most one "B"') if flatmap.count('b') != flatmap.count('B'): error('map must have same number of "b" as "B"') # TODO, this function could check some more things, e.g.: # - that the boundary of the map consists of walls # - that the map is connected without dead ends # - etc. # Implementing such checks is left as an exercise to the contestants. def maps_equal(map1, map2): h1 = len(map1) w1 = len(map1[0]) h2 = len(map2) w2 = len(map2[0]) if (h1, w1) != (h2, w2): return False AB_swaps = 0 ab_swaps = 0 for r in range(h1): for c in range(w1): if map1[r][c] in 'AB' and map2[r][c] in 'AB': AB_swaps += map1[r][c] != map2[r][c] elif map1[r][c] in 'ab' and map2[r][c] in 'ab': ab_swaps += map1[r][c] != map2[r][c] elif map1[r][c] != map2[r][c]: return False return AB_swaps == ab_swaps def read_map(f): line = f.readline().strip().decode('utf-8') print(' %s' % line) try: (H, W) = map(int, line.split()) except: error('expected a line with the dimensions of the map but instead got "%s"' % line) if W <= 0 or H <= 0: error('map dimensions given as %d x %d, but they must be positive' % (H, W)) if W*H > 100000: error('too large map (%d x %d = %d cells large)' % (H, W, H*W)) result = [] for i in range(H): try: line = f.readline().strip().decode('utf-8') print(' %s' % line) except: error('map dimensions given as %d x %d but I failed to read %d\'th line of the map' % (H, W, i+1)) result.append(line) for i in range(H): if len(result[i]) != W: error('map dimensions given as %d x %d but %d\'th line of the map has wrong length %d' % (H, W, i+1, len(line))) for j in range(W): if result[i][j] not in '#AaBbS.': error('row %d column %d of map contains invalid character %c' % (i+1, j+1, result[i][j])) check_map(result) return result def main(): parser = argparse.ArgumentParser(description='''Testing tool for the "Dungeon Dawdler" problem from NCPC 2019. See source code for further info.''') parser.add_argument('-f', '--file', type=argparse.FileType('rb'), help='Use map contained in this file instead of map from Sample Interaction 1. The file must contain a map in the same format as the output format of the problem.') parser.add_argument('program', nargs='+', help='Command to execute your solution program, for instance "./a.out" or "java MySolution"') args = parser.parse_args() if args.file: print('[*] Loading map from %s:' % args.file.name) MAP = read_map(args.file) args.file.close() else: print('[*] Using default map') MAP = DEFAULT_MAP check_map(MAP) height = len(MAP) width = len(MAP[0]) cur_row = cur_col = None endpoints = {} for i in range(height): for j in range(width): if MAP[i][j] == 'S': (cur_row, cur_col) = (i, j) elif MAP[i][j] in 'ab': endpoints[MAP[i][j]] = (i, j) process = subprocess.Popen(args.program, stdin=subprocess.PIPE, stdout=subprocess.PIPE) steps_taken = 0 while True: # Send information to solution about surroundings message = [] message.append(get_surroundings(MAP, cur_row, cur_col)) if MAP[cur_row][cur_col] in 'AB': message.append('trap') (cur_row, cur_col) = endpoints[chr(ord(MAP[cur_row][cur_col])+32)] message.append(get_surroundings(MAP, cur_row, cur_col)) else: message.append('ok') message = ' '.join(message) print('[*] Round %3d: At (%d,%d), message is "%s"' % (steps_taken+1, cur_row, cur_col, message)) process.stdin.write(('%s\n' % message).encode()) process.stdin.flush() # Get and execute action from solution action = process.stdout.readline().strip().decode('utf-8') if action == 'done': break if action not in DIRECTIONS: error('solution sent invalid action "%s"' % action) steps_taken += 1 if steps_taken > MAX_STEPS: error('Exceeded maximum number of steps (%d)' % (MAX_STEPS)) (dr, dc) = DIRECTIONS[action] cur_row += dr cur_col += dc print('[*] Action \'%s\', walk to (%d,%d)' % (action, cur_row, cur_col)) if MAP[cur_row][cur_col] == '#': error('solution walked into a wall at position (%d,%d)' % (cur_row, cur_col)) print('[*] Solution reported done, reading map:') # Get and check solution output output = read_map(process.stdout) if not maps_equal(MAP, output): print('[*] Correct map:') print(' %d %d' % (len(MAP), len(MAP[0]))) for row in MAP: print(' %s' % row) error('solution gave wrong map') else: print('[*] OK, solution correct!') if __name__=='__main__': main()