Computer Science II
Contact Information
Prerequisites
Course Overview
Textbooks
Web Resources
Additional Tutoring
Calendar
Lecture notes
Lab materials
Homework
Test reviews
Schedule
Lab Times
Office Hours
Homework
Due Date and Time
Late Day Policy
Compilers
Electronic Submission
C++ Development
Cygwin
Emacs
Dev C++
MinGW
Other Information
Command Line Args
File I/O
Redirecting I/O
HW6 Sliding Block Recursion Contest
SOLVER STRATEGIES
- cutler: recursion, history unsorted list, heuristic based on min possible moves to solve
- dawkim: recursive, 2 solvers (1 square, 1 non-rect), map for history, early exits
- devars2: no undo, pass by reference or const refence
- hutcha2: got rid of all bugs, uses lists for efficient erase
- kasia: greedy, with heuristic based on similarity to solution
- kramet: no info on optimizations
- peacha: no info on optimizations
- pedrok: breadth first search, scratch grid, uses a map for fast searching
- radoca: depth first with increasing max depths, hashing for history
- rakese: looks for all possible board positions
- saulnk: no info on optimizations
- sberard: bi-directional a* search, (preallocated) hash table of visited states
- scourj: fast possible possible moves checker
- vandes4: breadth first search, tree of pointers to moves
- wellir: iterative, minimizes memory, hashes board
- woodg: looks for pieces next to blanks to move
Source code for cutler's & sberard's solutions are posted on the calendar.
DATA
| Puzzle 1 | Puzzle 2 | Puzzle 3 | Puzzle 4 | Puzzle 5 | Puzzle 6 | Puzzle 7 | Puzzle 8 | Puzzle 9 | Puzzle 10 | Puzzle 11 | Puzzle 12 | Puzzle 13 | Puzzle 14 | Puzzle 15 | Puzzle 16 | Puzzle 17 | |
| grid | 2x2 | 4x3 | 2x2 | 3x2 | 3x2 | 3x2 | 3x3 | 4x3 | 4x4 | 3x3 | 3x3 | 3x3 | 4x5 | 4x4 | 4x4 | 9x5 | 9x5 |
| #pieces | 3 | 2 | 3 | 5 | 5 | 5 | 2 | 2 | 2 | 8 | 8 | 8 | 4 | 15 | 15 | 8 | 8 |
| shape | square | non-rect | square | square | square | square | rect | non-rect | non-rect | square | square | square | non-rect | square | square | non-rect | non-rect |
| #moves | 4 | impossible | 4 | 6 | impossible | 18 | 4 | 7 | 7 | 8 | 30 | impossible | 6 | 36 | possible | 78 | 112 |
| cutler | 0 | 0 | 0 | 0 | 37 | 7 | 0 | 0 | 0 | 0 | > 1hr | seg fault | 0 | > 1hr | seg fault | > 1hr | > 1hr |
| dawkim | 0 | 0.01 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0.07 | 0.81 | 712 | 0 | memory | memory | > 1hr | > 1hr |
| devars2 | 0.01 | 0.22 | 0 | 0.03 | 1.96 | 0.18 | 0 | 0 | 0 | 9.59 | > 1hr | > 1hr | 0 | > 1hr | > 1hr | > 1hr | > 1hr |
| hutcha2 | 0 | 0.01 | 0 | 0.1 | > 1hr | 1.2 | 0.03 | 0.02 | 0.15 | memory | memory | memory | 0.01 | memory | memory | > 1hr | > 1hr |
| kasia | 0.01 | 0 | 0 | 0 | 0.05 | 0 (48) | 0 (6) | 0 | 0 (9) | 0 | 0.03 (226) | seg fault | 0 | 34 (6364) | seg fault | > 1hr | > 1hr |
| kramet | 0 | 0 | 0 | > 1hr | > 1hr | > 1hr | > 1hr | 18 | > 1hr | memory | memory | memory | 10 | memory | memory | incorrect | > 1hr |
| peacha | 0 | incorrect | 0 | 0 | > 1hr | incorrect | incorrect | incorrect | > 1hr | incorrect | incorrect | > 1hr | > 1hr | > 1hr | > 1hr | > 1hr | > 1hr |
| pedrok | 0 | 0 | 0 | 0 | 0.02 | 0.01 | 0 | 0 | 0 | 0.01 | memory | memory | 93 | memory | memory | memory | memory |
| radoca | 0.02 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0.02 | 0 | 2.48 | 3.38 | 0 | memory | memory | > 1hr | > 1hr |
| rakese | 0 | 0 | 0 | 0 | 0.01 | 0.01 | 0 | 0 | 0 | 0 | > 1hr | > 1hr | 0 | memory | memory | > 1hr | > 1hr |
| saulnk | 0 | 0 | 0 | 0.02 (16) | 0.34 | 0.32 (118) | 0 (6) | 0 | 0 (15) | memory | memory | memory | 7 (10) | memory | memory | memory | memory |
| sberard | 0.3 | 0.25 | 0.3 | 0.3 | 0.25 | 0.29 | 0.3 | 0.29 | 0.3 | 0.29 | 0.44 (32) | 2107 | 0.29 | 79 | > 1hr | 1.07 | 11.4 |
| scourj | 0 | 0 | 0 (8) | 0 (152) | 0.02 | 0 (74) | 0 (6) | 0 | 0 (19) | seg fault | 31 (6124) | seg fault | incorrect | seg fault | seg fault | seg fault | seg fault |
| vandes4 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | > 1hr | > 1hr | 0 | > 1hr | > 1hr | > 1hr | > 1hr |
| wellir | 0 | 0 | 0 | 0 | memory | 37 | 0 | 0 | 0 | 0 | memory | memory | 0 | memory | memory | memory | memory |
| woodg | 0 | 0.13 | 0 | 0 | seg fault | 0.09 | incorrect | incorrect | incorrect | seg fault | seg fault | seg fault | seg fault | seg fault | seg fault | incorrect | incorrect |
All times above are in seconds.
The orange highlighted squares are tied for the fastest times for each
puzzle (within a tenth of a second).
A number in parentheses after
the time indicates the length of the non-optimal path that was output.
SUMMARY
| incorrect | too long | seg fault | memory | > 1hr | finished | fastest | sloccount | |
| cutler | 2 | 4 | 11 | 9 | 307 | |||
| dawkim | 2 | 2 | 13 | 12 | 630 | |||
| devars2 | 6 | 11 | 8 | 323 | ||||
| hutcha2 | 5 | 3 | 9 | 6 | 449 | |||
| kasia | 5 | 2 | 2 | 8 | 8 | 342 | ||
| kramet | 1 | 5 | 6 | 5 | 3 | 437 | ||
| peacha | 6 | 8 | 3 | 4 | 257 | |||
| pedrok | 6 | 11 | 10 | 444 | ||||
| radoca | 2 | 2 | 13 | 12 | 307 | |||
| rakese | 2 | 4 | 11 | 11 | 437 | |||
| saulnk | 5 | 7 | 5 | 4 | 355 | |||
| sberard | 1 | 1 | 15 | 4 | 530 | |||
| scourj | 1 | 6 | 6 | 4 | 4 | 372 | ||
| vandes4 | 6 | 11 | 12 | 334 | ||||
| wellir | 7 | 10 | 9 | 774 | ||||
| woodg | 5 | 7 | 5 | 4 | 212 |
"incorrect" means that the output was incorrect (e.g., illegal moves).
"too long" means that the path output was non optimal.
"seg fault" means the program terminated with an error.
"memory" means ran out of memory.
"> 1hr" means the solver was still running after an hour.
"finished" is the number of correctly solved puzzles.
"fastest" is the number of puzzles for which the submission was one of the fastest.
"sloccount" is the a count of the (non comment) lines of source code.
BEST STUDENT SUBMISSIONS
- Matthew Dawkins
- Alex Radocea
HONORABLE MENTIONS
- hutcha: fastest consumption of entire RAM
- kasia: longest (incorrect) solution
- wellir: most lines of code