Fall 2010
Contact Information
Syllabus
Learning Outcomes
Prerequistites
Grading Criteria
References
Optional Textbooks
Web Resources
C++ Development
Misc. Programming Info
Getting Help
Tutoring
Advice from TAs
Calendar
Lecture notes
Lab materials
Homework
Test reviews
Schedule
Office Hours
Lab Times
Homework
Due Date and Time
Late Day Policy
Compilers
Electronic Submission
HW6 Maze Maker Contest
All Solutions:
| RCSID | puzzle0 | puzzle1 | puzzle2 | puzzle3 | puzzle4 | puzzle5 | puzzle6 | puzzle7 | puzzle8 | puzzle9 | puzzle10 | puzzle11 |
| chanb4 | incorrect | incorrect | incorrect | incorrect | incorrect | incorrect | incorrect | incorrect | incorrect | incorrect | incorrect | incorrect |
| cromak | 0:00.00 | 0:00.00 | 0:00.00 | 0:00.34 | segfault/>10m | 0:10.40 | 0:00.03 | 1:38.82 | 0:05.09 | 0:28.65 | segfault/>10m | segfault/>10m |
| cutler | 0:00.00 | 0:00.00 | 0:00.00 | 0:00.04 | 0:00.00 | 0:00.55 | 0:00.00 | 0:04.78 | 0:00.00 | 0:00.51 | 0:09.38 | 0:35.37 |
| erickj3 | incorrect | 0:00.00 | incorrect | incorrect | 0:00.00 | 0:00.05 | 0:00.02 | segfault/>10m | incorrect | segfault/>10m | incorrect | segfault/>10m |
| foleys3 | 0:00.00 | 0:00.00 | 0:00.00 | 0:00.45 | 0:00.00 | 0:19.42 | 0:00.06 | 2:59.04 | 0:11.79 | 0:45.32 | segfault/>10m | segfault/>10m |
| gerstr2 | 0:00.00 | 0:00.00 | 0:00.00 | 0:00.24 | 0:00.00 | 0:00.02 | 0:00.01 | 0:18.72 | 0:00.00 | 0:17.06 | 0:01.98 | 0:19.64 |
| grubej3 | 0:00.00 | segfault/>10m | 0:00.00 | segfault/>10m | 0:00.01 | segfault/>10m | segfault/>10m | segfault/>10m | 0:01.48 | segfault/>10m | segfault/>10m | segfault/>10m |
| hant2 | 0:00.00 | 0:00.00 | 0:00.00 | 0:00.04 | 0:00.00 | 0:00.01 | 0:00.00 | 0:01.73 | 0:00.00 | incorrect | incorrect | 0:02.36 |
| heyses | 0:00.02 | 0:00.00 | 0:00.00 | 0:00.21 | 0:00.01 | segfault/>10m | 0:00.27 | segfault/>10m | 0:00.16 | segfault/>10m | segfault/>10m | segfault/>10m |
| jonesj10 | 0:00.00 | 0:00.00 | 0:00.00 | 0:00.41 | 0:00.00 | 0:02.25 | 0:00.01 | 0:42.92 | 0:02.37 | 0:15.88 | segfault/>10m | segfault/>10m |
| lymank | 0:00.00 | incorrect | 0:00.00 | incorrect | 0:00.00 | incorrect | incorrect | incorrect | incorrect | incorrect | incorrect | incorrect |
| meltzg | 0:00.00 | 0:00.00 | 0:00.00 | segfault/>10m | 0:00.01 | 0:08.57 | 0:00.03 | segfault/>10m | 0:04.48 | segfault/>10m | segfault/>10m | segfault/>10m |
| michaj8 | 0:00.00 | incorrect | incorrect | incorrect | 0:00.00 | 0:25.74 | 0:00.08 | 4:18.98 | 0:10.25 | 3:02.91 | segfault/>10m | segfault/>10m |
| millea9 | 0:00.00 | incorrect | incorrect | incorrect | 0:00.01 | 0:00.04 | 0:00.01 | 0:24.52 | 0:00.00 | incorrect | incorrect | 0:27.62 |
| nistam | 0:00.02 | incorrect | 0:00.00 | incorrect | 0:00.00 | incorrect | incorrect | incorrect | 0:00.03 | incorrect | incorrect | incorrect |
| pomerm | 0:00.00 | 0:00.00 | 0:00.00 | 0:00.22 | 0:00.00 | 0:00.02 | 0:00.01 | 0:18.15 | 0:00.00 | 0:23.36 | 0:01.79 | 0:17.96 |
| ricec2 | segfault/>10m | segfault/>10m | segfault/>10m | segfault/>10m | segfault/>10m | segfault/>10m | segfault/>10m | segfault/>10m | segfault/>10m | segfault/>10m | segfault/>10m | segfault/>10m |
| sandes3 | 0:00.00 | 0:00.00 | incorrect | incorrect | 0:00.00 | 0:00.00 | 0:00.00 | 0:02.72 | 0:00.00 | 0:12.20 | 0:00.36 | 0:03.66 |
| santob2 | 0:00.00 | 0:00.00 | 0:00.00 | 0:01.89 | 0:00.00 | incorrect | incorrect | segfault/>10m | incorrect | segfault/>10m | incorrect | segfault/>10m |
| schmir5 | 0:00.00 | 0:00.00 | 0:00.00 | incorrect | 0:00.00 | 0:15.54 | 0:00.05 | incorrect | 0:07.34 | incorrect | segfault/>10m | segfault/>10m |
| steifc | 0:00.00 | 0:00.00 | 0:00.00 | 0:00.30 | 0:00.00 | 0:09.41 | 0:00.03 | 1:23.68 | 0:04.42 | 2:19.05 | segfault/>10m | segfault/>10m |
| steins3 | 0:00.00 | 0:00.00 | 0:00.00 | 1:04.45 | 0:00.01 | incorrect | incorrect | segfault/>10m | incorrect | segfault/>10m | segfault/>10m | segfault/>10m |
| tamham | 0:00.00 | 0:00.00 | 0:00.00 | 0:00.35 | 0:00.00 | 0:07.18 | 0:00.03 | 1:33.23 | incorrect | 3:12.15 | segfault/>10m | segfault/>10m |
| tebbug | 0:00.00 | 0:00.00 | 0:00.00 | segfault/>10m | 0:00.22 | 0:09.82 | 0:13.18 | segfault/>10m | 0:03.95 | segfault/>10m | segfault/>10m | segfault/>10m |
| torrez | incorrect | incorrect | incorrect | incorrect | incorrect | incorrect | incorrect | incorrect | incorrect | incorrect | segfault/>10m | segfault/>10m |
| wangz9 | 0:00.00 | 0:00.00 | 0:00.00 | segfault/>10m | 0:00.01 | 0:27.26 | 0:00.15 | segfault/>10m | 0:53.02 | segfault/>10m | segfault/>10m | segfault/>10m |
| wenslr | 0:00.00 | 0:00.00 | 0:00.00 | 0:00.26 | 0:00.00 | 0:04.68 | 0:00.02 | 0:35.05 | 0:00.00 | 0:31.57 | 7:50.91 | 5:10.16 |
| wrigha3 | 0:00.00 | 0:00.00 | 0:00.00 | 0:04.23 | 0:00.03 | 0:42.64 | 0:00.18 | segfault/>10m | 0:36.30 | segfault/>10m | segfault/>10m | segfault/>10m |
| zamana | 0:00.00 | 0:00.00 | 0:00.00 | 0:00.37 | 0:00.00 | 0:12.45 | 0:00.04 | 2:11.33 | 0:06.86 | 0:30.26 | segfault/>10m | segfault/>10m |
| zimmtn | 0:00.00 | 0:00.00 | 0:00.00 | 0:00.06 | 0:00.00 | 0:00.00 | 0:00.00 | 0:04.28 | 0:00.00 | 0:01.06 | 0:00.56 | 0:06.03 |
One Solution:
| RCSID | puzzle0 | puzzle1 | puzzle2 | puzzle3 | puzzle4 | puzzle5 | puzzle6 | puzzle7 | puzzle8 | puzzle9 | puzzle10 | puzzle11 |
| chanb4 | 0:00.00 | 0:00.00 | incorrect | incorrect | 0:00.00 | 0:00.00 | 0:00.00 | 0:01.27 | 0:00.00 | 0:10.75 | 0:00.27 | 0:02.17 |
| cromak | 0:00.00 | 0:00.00 | incorrect | incorrect | 0:00.00 | incorrect | incorrect | incorrect | incorrect | 0:24.82 | incorrect | incorrect |
| cutler | 0:00.00 | 0:00.00 | 0:00.00 | 0:00.00 | 0:00.00 | 0:00.04 | 0:00.00 | 0:00.64 | 0:00.00 | 0:00.02 | 0:00.66 | 0:33.50 |
| erickj3 | incorrect | 0:00.00 | 0:00.00 | 0:00.59 | 0:00.00 | 0:00.01 | 0:00.01 | segfault/>10m | 0:00.00 | 6:52.93 | incorrect | segfault/>10m |
| foleys3 | 0:00.00 | 0:00.00 | 0:00.00 | 0:00.01 | 0:00.00 | 0:00.02 | 0:00.04 | 0:03.88 | 0:03.43 | 0:41.44 | 4:07.17 | segfault/>10m |
| gerstr2 | 0:00.00 | 0:00.00 | 0:00.00 | 0:00.00 | 0:00.00 | 0:00.00 | 0:00.00 | 0:01.31 | 0:00.00 | 0:00.19 | 0:00.00 | 0:04.67 |
| grubej3 | incorrect | incorrect | incorrect | incorrect | incorrect | incorrect | incorrect | incorrect | incorrect | incorrect | incorrect | incorrect |
| hant2 | 0:00.00 | 0:00.00 | 0:00.00 | 0:00.00 | 0:00.00 | 0:00.00 | 0:00.00 | 0:00.30 | 0:00.00 | 0:00.00 | 0:00.15 | 0:00.41 |
| heyses | 0:00.00 | 0:00.00 | 0:00.00 | 0:00.02 | 0:00.00 | segfault/>10m | 0:00.25 | segfault/>10m | 0:00.15 | segfault/>10m | segfault/>10m | segfault/>10m |
| jonesj10 | 0:00.00 | 0:00.00 | 0:00.00 | 0:00.00 | 0:00.00 | 0:00.24 | 0:00.00 | 0:08.30 | 0:01.19 | 0:00.16 | segfault/>10m | segfault/>10m |
| lymank | 0:00.00 | incorrect | 0:00.00 | incorrect | 0:00.00 | incorrect | 0:00.00 | incorrect | 0:00.00 | incorrect | incorrect | 0:05.02 |
| meltzg | 0:00.00 | 0:00.00 | 0:00.00 | incorrect | 0:00.00 | 0:08.45 | 0:00.02 | incorrect | 0:04.45 | incorrect | segfault/>10m | incorrect |
| michaj8 | 0:00.00 | 0:00.00 | incorrect | incorrect | 0:00.00 | 0:25.51 | 0:00.07 | 4:19.79 | 0:10.75 | 3:03.25 | segfault/>10m | segfault/>10m |
| millea9 | exit(1) | incorrect | incorrect | incorrect | 0:00.01 | incorrect | incorrect | incorrect | incorrect | incorrect | incorrect | incorrect |
| nistam | 0:00.00 | 0:00.00 | 0:00.00 | 0:00.06 | 0:00.00 | 0:00.01 | 0:00.00 | 0:10.80 | 0:00.01 | 1:06.03 | 0:00.82 | 0:52.94 |
| pomerm | 0:00.00 | 0:00.00 | 0:00.00 | 0:00.00 | 0:00.00 | 0:00.00 | 0:00.00 | 0:00.49 | 0:00.00 | 0:00.25 | 0:00.00 | 0:02.68 |
| ricec2 | segfault/>10m | segfault/>10m | segfault/>10m | segfault/>10m | segfault/>10m | segfault/>10m | segfault/>10m | segfault/>10m | segfault/>10m | segfault/>10m | segfault/>10m | segfault/>10m |
| sandes3 | 0:00.00 | 0:00.00 | incorrect | incorrect | 0:00.00 | 0:00.00 | 0:00.00 | 0:00.05 | 0:00.00 | 0:00.15 | 0:00.00 | 0:00.91 |
| santob2 | 0:00.00 | 0:00.00 | 0:00.00 | 0:00.01 | 0:00.00 | incorrect | incorrect | incorrect | incorrect | segfault/>10m | incorrect | incorrect |
| schmir5 | 0:00.00 | 0:00.00 | 0:00.00 | 0:00.00 | 0:00.00 | 0:02.34 | 0:00.02 | 0:46.37 | 0:03.66 | 0:01.02 | segfault/>10m | segfault/>10m |
| steifc | exit(1) | exit(1) | exit(1) | exit(1) | incorrect | exit(1) | exit(1) | exit(1) | exit(1) | exit(1) | exit(1) | segfault/>10m |
| steins3 | 0:00.00 | 0:00.00 | 0:00.00 | 0:00.00 | 0:00.00 | incorrect | incorrect | 0:00.08 | incorrect | 0:00.08 | incorrect | 0:01.21 |
| tamham | 0:00.00 | 0:00.00 | 0:00.00 | 0:00.01 | 0:00.00 | 0:00.01 | 0:00.02 | 0:02.74 | 0:01.09 | 3:18.76 | 1:18.49 | segfault/>10m |
| tebbug | 0:00.00 | 0:00.00 | 0:00.00 | 0:00.00 | 0:00.01 | 0:00.00 | 0:00.00 | segfault/>10m | 0:00.00 | segfault/>10m | 0:01.12 | 5:14.13 |
| torrez | 0:00.00 | 0:00.00 | 0:00.00 | incorrect | 0:00.00 | 0:08.22 | 0:00.08 | 4:35.34 | incorrect | 0:03.71 | segfault/>10m | segfault/>10m |
| wangz9 | 0:00.00 | 0:00.00 | 0:00.00 | incorrect | 0:00.01 | 0:27.30 | 0:00.14 | incorrect | 0:52.43 | incorrect | incorrect | incorrect |
| wenslr | 0:00.00 | 0:00.00 | 0:00.00 | 0:00.01 | 0:00.00 | 0:00.00 | 0:00.01 | 0:02.70 | 0:00.00 | 0:27.16 | 0:00.33 | 4:49.26 |
| wrigha3 | 0:00.00 | 0:00.00 | 0:00.00 | 0:00.07 | 0:00.03 | 0:00.04 | 0:00.14 | 0:20.65 | 0:11.69 | 1:09.91 | segfault/>10m | segfault/>10m |
| zamana | 0:00.00 | 0:00.00 | 0:00.00 | 0:00.01 | 0:00.00 | 0:01.91 | 0:00.01 | 0:39.55 | 0:03.29 | 0:25.48 | segfault/>10m | segfault/>10m |
| zimmtn | 0:00.00 | 0:00.00 | 0:00.00 | 0:00.00 | 0:00.00 | 0:00.00 | 0:00.00 | 0:00.53 | 0:00.00 | 0:00.18 | 0:00.07 | 0:02.64 |
All times above are in m:ss.ss, compiled with g++ -O3 optimizations, on a 2.8 GHz Intel CPU running linux.
The orange highlighted squares are tied for the fastest times for each puzzle (within a tenth of a second).
The first 7 puzzles are on the calendar. 4 new puzzles were used for the contest:
puzzle8.txt,
puzzle9.txt,
puzzle10.txt, and
puzzle11.txt.
OPTIMIZATIONS
chanb4: rewrote class using lists and arrays (avoiding vectors)cromak: no optimizations for contest
cutler: switched board representation from vector of strings to string, sorted the blocks from largest to smallest before inserting, added check in shortest path to stop search if current path is longer than the desired path, commented out asserts in frequently used functions
erickj3: added more if statements to limit the number of times operations would be performed
foleys3: small edits in loops to reduce extra function calls
gerstr2: no optimizations for contest
grubej3: no optimizations for contests
hant2: global variables, array, convert to vertex & graph structure, & more (not described)
heyses: no optimizations for contest
jonesj10: stop after first solution
lymank: no optimizations for contest
meltzg: no optimizations for contest
michaj8: no optimizations for contest
millea9: no optimizations for contest
nistam: no optimizations for contest
pomerm: A* pathfinding for shortest path, stop after first solution
ricec2: optimized shortest path for cases where it is simply a line of sight
sandes3: iterative breadth first search, minimize number of duplicated block placement tests, avoid duplicating meta-data, unrolled board representation from vector of strings to a single string, rewrote print to eliminate calls to endl, reduced use of location class
santob2: no optimizations for contest
schmir5: shortest path always try to go towards the end point first before search other directions, checks best case path first
steifc: compare best case distance from current point to end point to the shortest path so far, exit after the first maze is found (one solution)
steins3: more if statements to reduce unnecessary looping
tamham: no optimizations for contest
tebbug: shortest path function tests to make sure it is almost always progressing towards the goal
torrez: no optimizations described
wangz9: no optimizations for contest
wenslr: doesn't try to place a block ontop of an already existing block, searches for first free space
wrigha3: removed all debugging cout statements
zamana: no optimizations for contest
zimmtn: switched vectors of strings to vector of char, used a 1D vector to represent the board, removed endl statements, tried breadth first seach & A* search
CONTEST WINNERS
- Fastest to find correct solutions (both ONE and ALL): Noah Zimmt
- Fastest to find ONE solution: Tianning Han
- Honorable Mentions: Michael Pomeranz, Ryan Gerstein, & Samuel Sandeen