Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- OBSTACLE = "+"
- EMPTY = "."
- MINE = "M"
- BEACON = "B"
- raw_board="""\
- ++++++++++++++++++++
- +++++++..+++++++++++
- +++++++...++++.+++++
- ++++++.+..+++.....++
- ++++++.....+......++
- +++++++..++.......++
- ++....+..+++.+.+..++
- ++........+........+
- ++..........++.+++++
- ++..........++.+++++
- +++++..+..........++
- ++++++++++++...++.++
- ++++++++++++......++
- +.++++...+++......++
- +..+++...+++++++++++
- ++++++...+++++++++++
- ++++++++++++++++++++"""
- #all functions assume that: a board's outermost rows/columns are entirely obstacles
- def copy(board):
- #could just use deepcopy, but meh
- return [row[:] for row in board]
- def iter_neighbors(board, x,y):
- """yield the tile type of every adjacent tile"""
- #todo: make this work for border tiles
- assert 0 < y < len(board) - 1
- assert 0 < x < len(board[0]) - 1
- for dx in (-1,0,1):
- for dy in (-1, 0, 1):
- if dx == dy == 0: continue
- yield board[dy+y][dx+x]
- def calculate_score(board):
- """Returns the total score of the board."""
- def _score(x,y):
- """the score of this one tile."""
- if board[y][x] == MINE:
- return 100 + sum(40 for tile in iter_neighbors(board, x, y) if tile == BEACON)
- else:
- return 0
- return sum(_score(x,y) for y, row in enumerate(board) for x, _ in enumerate(row))
- def display(board):
- """print the board."""
- print("\n".join("".join(row) for row in board))
- #example optimizers. Each one may mutate board in-place in an attempt to improve its score.
- def literally_nothing(board):
- pass
- def fill_empty_with_mines(board):
- for y, row in enumerate(board):
- for x, tile in enumerate(row):
- if board[y][x] == EMPTY:
- board[y][x] = MINE
- def optimize_with_hill_climb(board):
- """Make only simple strict improvements. Very likely to get stuck in local optima."""
- #pass 1: fill up empty tiles
- fill_empty_with_mines(board)
- #pass 2: replace a mine with a beacon iff doing so increases score
- cur_score = calculate_score(board)
- for y, row in enumerate(board):
- for x, tile in enumerate(row):
- if board[y][x] == MINE:
- board[y][x] = BEACON
- new_score = calculate_score(board)
- if new_score > cur_score:
- #keep change
- cur_score = new_score
- else:
- #revert
- board[y][x] = MINE
- def sample_showcase():
- """showcase the performance of the sample optimizers."""
- starting_board = [list(row) for row in raw_board.strip().split("\n")]
- optimizers = [literally_nothing, fill_empty_with_mines, optimize_with_hill_climb]
- print("Starting board:")
- display(starting_board)
- print("\n")
- for i, optimize_func in enumerate(optimizers, 1):
- board = copy(starting_board)
- print(f"Candidate #{i}: {optimize_func.__name__}")
- optimize_func(board)
- display(board)
- print("Score:", calculate_score(board))
- print(f"End of report for candidate #{i}.\n\n")
- if __name__ == "__main__":
- sample_showcase()
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement