|
Chris Pollett >
Old Classses > |
HW1 Solutions PageFor this homework, I had the grader recommend some of the better assignments and I chose from them one to use as the homework solution. The student that had their homework chosen received 1 bonus point after curving for having their homework selected. If you were chosen and would rather your homework not be used as the solution let me know and I will choose someone else's homework and they will receive the bonus point instead. The only changes I made were to convert the names listed in the homework files to SJSU student. Here are the test cases the grader used: Competition.The competition was conducted by generating boards of size 20x20, 50x50, 100x100, and 500x500. The initial pool were programs which had received a score of 10 out of 10. I let programs run for 20 seconds on my 2009 MacBook Pro. Four programs were able to find a solution to the 100x100 board, but only one of these (which by chance also happened to be the chosen solution) was also able to solve the 500x500 board. To generate the board I used the following code and chose density values between .1 and .2
import sys
import random
def board_maker(size, density):
"Code to generate a maze for our CS156 Hw1 A* solvers"
board = [];
# first create a blank board
for i in xrange(0, size):
row = [];
for j in xrange(0, size):
row.append('.');
board.append(row);
num_walls = int(density * size * size + 0.5)
# make density fraction of the squares walls
for i in xrange(0, num_walls):
x = random.randint(0, size - 1)
y = random.randint(0, size - 1)
board[x][y] = "#"
# add the player and the food
board[0][0] = "@"
board[size - 1][size - 1] = "%"
# print board
for i in xrange(0, size):
sys.stdout.write("".join(board[i]) + "\n");
if(len(sys.argv)) != 3:
print "Please supply a board size and density"
raise SystemExit(1)
random.seed(123456789)
program, size, density = sys.argv
board_maker(int(size), float(density))
|