import os import random import sys MAX_DIM = 1000 MAX_INSTR = 10**5 CASE = 1 DEST = os.path.join(os.getcwd(), '../data/secret') def next_file(short_desc=None, long_desc=None): global CASE basename = os.path.join(DEST, '%02d' % CASE) CASE += 1 if short_desc is not None: basename += '-' + short_desc if long_desc is not None: with open(basename+'.desc', 'w') as desc_out: desc_out.write(long_desc) return open(basename+'.in', 'w') def save_case(grid, seq, short_desc=None, long_desc=None, shuffle_adj_list=True): (w, h) = (len(grid[0]), len(grid)) sys.stderr.write('save case sz %dx%d |I| = %d\n' % (w, h, len(seq))) f = next_file(short_desc, long_desc) f.write('%d %d\n' % (w, h)) for row in grid: f.write('%s\n' % ''.join(row)) f.write('%s\n' % seq) f.close() def random_new_dir(old_dir): return 'NWSE'[('NWSE'.index(old_dir) + random.randint(1, 3)) % 4] def perturb(seq, dir_gen): return ''.join(random_new_dir(x) for x in seq) def bfs(grid, sr, sc): (w, h) = (len(grid[0]), len(grid)) dist = [[-1]*w for _ in range(h)] dist[sr][sc] = 0 Q = [(sr, sc)] qhead = 0 while qhead < len(Q): (r, c) = Q[qhead] qhead += 1 for (nr, nc) in [(r-1, c), (r+1, c), (r, c-1), (r, c+1)]: if grid[nr][nc] != '#' and dist[nr][nc] == -1: dist[nr][nc] = dist[r][c] + 1 Q.append((nr, nc)) return dist def random_seq(dist, r, c): ans = [] while dist[r][c] > 0: poss = [(pr, pc, d) for (pr, pc, d) in [(r-1, c, 'S'), (r+1, c, 'N'), (r, c-1, 'E'), (r, c+1, 'W')] if dist[pr][pc] + 1 == dist[r][c]] (r, c, d) = random.choice(poss) ans.append(d) return ''.join(reversed(ans)) def random_goal(grid, sr, sc, dist_threshold = 0.1): (w, h) = (len(grid[0]), len(grid)) dist = bfs(grid, sr, sc) ends = [] max_dist = max(max(d) for d in dist) print('gen_goal, max_dist is %d' % max_dist) for r in range(h): for c in range(w): if dist[r][c] > dist_threshold*max_dist: ends.append((r, c)) if not ends: return None (gr, gc) = random.choice(ends) return random_seq(dist, gr, gc) def random_grid(w, h, obstacle_density): grid = [['.#'[random.random() < obstacle_density] for _ in range(w)] for _ in range(h)] for row in range(h): grid[row][0] = grid[row][-1] = '#' for col in range(w): grid[0][col] = grid[-1][col] = '#' srow = random.randint(1, h-2) scol = random.randint(1, w-2) grid[srow][scol] = 'S' return (grid, srow, scol) def gen_case_random(w, h, obstacle_density, goal_dist_threshold=1e-10, short_desc=None): good_seq = None while not good_seq: (grid, sr, sc) = random_grid(w, h, obstacle_density) good_seq = random_goal(grid, sr, sc, dist_threshold = goal_dist_threshold) bad_seq = perturb(good_seq, random_new_dir) if short_desc is None: short_desc='random_%dx%d' % (w, h) save_case(grid, bad_seq, short_desc=short_desc) def gen_spiral_case(dim, force_two_sols=False): w = h = dim grid = [['#' for _ in range(w)] for _ in range(h)] r = c = 1 dr = 1 dc = 0 pts = [] for i in range(w-2, 0, -1): grid[1][i] = '.' pts.append((1, i)) L = dim - 1 while L > 1: if dr: L -= 2 for _ in range(L): r += dr c += dc assert 1 <= r < h-1 assert 1 <= c < w-1 grid[r][c] = '.' pts.append((r, c)) (dr, dc) = (-dc, dr) start_idx = random.randint(1, len(pts)-2) (sr, sc) = pts[start_idx] grid[sr][sc] = 'S' L = min(start_idx, len(pts)-1 - start_idx, MAX_INSTR) if random.randint(0, 1): L = -L (gr, gc) = pts[start_idx - L] dist = bfs(grid, sr, sc) seq = random_seq(dist, gr, gc) assert(len(seq) == abs(L)) def rand_neither(x, y): while True: z = random.choice('NESW') if z != x and z != y: return z if force_two_sols: gr2, gc2 = pts[start_idx + L] seq2 = random_seq(dist, gr2, gc2) assert(len(seq2) == abs(L)) errseq = ''.join([rand_neither(seq[i], seq2[i]) for i in range(abs(L))]) else: errseq = perturb(seq, random_new_dir) save_case(grid, errseq, short_desc='spiral_%dx%d' % (w, h)) def room_grid(w, h): pass def gen_case_empty(w, h, sr, sc, gr, gc, flip_seq = False, sort_seq=False): grid = [['.' for _ in range(w)] for _ in range(h)] for row in range(h): grid[row][0] = grid[row][-1] = '#' for col in range(w): grid[0][col] = grid[-1][col] = '#' grid[sr][sc] = 'S' assert 1 <= sr < h-1 and 1 <= sc < w - 1 assert 1 <= gr < h-1 and 1 <= gc < w - 1 dist = bfs(grid, sr, sc) seq = random_seq(dist, gr, gc) if flip_seq: seq = perturb(seq, random_new_dir) if sort_seq: seq = ''.join(x for x in sorted(seq)) save_case(grid, seq, short_desc='empty_%dx%d' % (w, h)) def main(): random.seed(4711) gen_case_empty(4, 3, 1, 1, 1, 2, flip_seq = True) gen_case_empty(3, 4, 2, 1, 1, 1, flip_seq = True) for _ in range(5): w = random.randint(5, 10) h = random.randint(5, 10) dens = random.uniform(0.1, 0.4) thres = random.random() gen_case_random(w, h, dens, goal_dist_threshold=thres) # medium cases gen_case_empty(50, 50, 25, 25, 1, 25) gen_case_empty(50, 50, 25, 25, 1, 25, flip_seq = True) gen_case_empty(50, 50, 25, 25, 1, 25, flip_seq = True, sort_seq = True) gen_case_empty(50, 50, 48, 1, 25, 25) for _ in range(5): w = random.randint(25, 100) h = random.randint(25, 100) dens = random.uniform(0.1, 0.5) thres = random.random() gen_case_random(w, h, dens, goal_dist_threshold=thres) gen_spiral_case(75) gen_spiral_case(75, force_two_sols=True) # big cases gen_case_empty(1000, 1000, 500, 500, 998, 500) gen_case_empty(1000, 1000, 500, 500, 998, 500, flip_seq = True) gen_case_empty(1000, 1000, 998, 998, 500, 500) gen_spiral_case(1000) gen_spiral_case(1000, force_two_sols=True) gen_case_random(1000, 4, 0.001, goal_dist_threshold=0.5) gen_case_random(4, 1000, 0.001, goal_dist_threshold=0.5) gen_case_random(1000, 10, 0.1, goal_dist_threshold=0.5) gen_case_random(10, 1000, 0.1, goal_dist_threshold=0.5) gen_case_random(1000, 1000, 0.2, goal_dist_threshold=0.5) gen_case_random(1000, 1000, 0.3, goal_dist_threshold=0.5) gen_case_random(1000, 1000, 0.4, goal_dist_threshold=0.5) gen_case_random(1000, 1000, 0.45, goal_dist_threshold=0.5) if __name__=='__main__': main()