HW1 Solutions Page

[Hw1 Solution.py]

The grader used the test case off of the Homework description (weather.txt):

B317
53P7

as well as (weather1.txt)

B427
53P7

and ran the commands (which will find routes):

python plane_agent.py  weather.txt  manhattan 6 - gives output

python plane_agent.py  weather.txt  euclidean 7 - gives output

python plane_agent.py  weather1.txt  euclidean 8 - gives output

python plane_agent.py  weather1.txt  made_up 10 - gives output

and then ran command (which won't find routes):

python plane_agent.py  weather.txt  euclidean 5 -  no route exists 

python plane_agent.py  weather.txt  manhattan 4 -  no route exists 

python plane_agent.py  weather1.txt  made_up 7 -  no route exists 

python plane_agent.py  weather1.txt  manhattan  6 -  no route exists 

Here is a program to generate larger boards used for the contest:

import sys
import random
def windmap_maker(size, density):
    "Code to generate a windmaps for our CS156 Hw1 A* solvers"
    board = [];
    # first create a board with winds of value 1
    for i in xrange(0, size):
        row = [];
        for j in xrange(0, size):
            row.append('1');
        board.append(row);
    num_barriers = int(density * size * size + 0.5)
    # make density fraction of the squares with wind values maybe larger than 1
    for i in xrange(0, num_barriers):
        x = random.randint(0, size - 1)
        y = random.randint(0, size - 1)
        wind_value = random.randint(1, 9)
        board[x][y] = str(wind_value)
    # add the player to the top and add the airports
    board[0][0] = "A"
    num_airports = random.randint(1, 4)
    for i in xrange(0, num_airports):
        x = random.randint(0, size - 1)
        y = random.randint(0, size - 1)
        board[x][y] = "P"
    # print wind map
    for i in xrange(0, size):
        sys.stdout.write("".join(board[i]) + "\n");
if(len(sys.argv)) != 3:
   print "Please supply a map size and density"
   raise SystemExit(1)
random.seed(123456789)
program, size, density = sys.argv
windmap_maker(int(size), float(density))

The initial pool of programs for the contest consisted of those programs that score a 9 or better on the homework. I generated a sequence of progressively harder boards:

python windmap_generator.py 100 .5 > weather_test2.txt (tested on values 150 and 300 - 6 contestants passed)
python windmap_generator.py 300 .5 > weather_test3.txt (tested on values 150, 200, 10000 - 3 contestants passed)
python windmap_generator.py 1000 .5 > weather_test4.txt (tested on values 500, 1000 - 2 contestants passed)
python windmap_generator.py 2000 .7 > weather_test5.txt (tested on values 2000, 100000 - 0 contestants passed)

A contestant would be counted out if their program crashed or took longer than a minute. All programs were tested with the made-up heuristic. I gave the two last contestants the bonus point. Interesting, for one, the made up heuristic just returned 0, which is essentially just uniform cost search.

Return to homework page.