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
C++ IDEs
Other Information
Command Line Args
File I/O
Redirecting I/O
HW6 Inverse Word Search Contest
SOLVER STRATEGIES
- cohend4: looks for overlaps in given words, only fill blanks with letters not being excluded
- coxl2: checks for forbidden words before filling in blanks
- crownj: checks word length to be sure it will fit, checks for first letter of forbidden words
- cutler (instructor): sort words by length and insert longest words first, check for forbidden words after each word insertion
- fernap3: loop unrolling optimization, use addition instead of multipliation in array indexing, used iteration instead of recursion
- freidm: local (rather than global) check for forbidden words, use vector of references to boards to avoid cost of copying
- gastoj3: builds data structure of possible crossings between input words, calculates required "distance from furthest edge" for each letter in a word and compares to free space in the board, uses symmetry to find mirrors & rotations
- hebers: pass by reference (to avoid cost of copying), lots of helper functions
- henryb: used set to check for duplicates, avoided use of recursion, check for forbidden words before filling in blanks, checks word length to ensure it fits
- hunta3: check for forbidden words before filling in blanks
- johnsc12: only finds first solution
- krissj: check for forbidden words before filling in blanks
- meisse2: checks for forbidden words after each insertion
- millmm: sort words by length, insert longer words first, fewer empty spaces remain
- perrym5: lots of conditionals to reduce recursions
- portew: checks for forbidden words before filling in blanks
- schuln3: general coding efficiency
- skurkj: logic to short circuit testing when board is bad
- todisk: uses map to store solutions, checks for impossible puzzles (words can't fit)
- valerj3: larger words first, performs rotations & mirrors on the grids
- wakefp: first word will only appear in top left quarter (reduces search space by 75%)
- wellir (UTA): Uses Boost Libraries (supplement to STL)
- wongp3: check for forbidden words before filling in blanks
DATA
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | |
| cohend4 | 0.00 | 0.00 | 0.01 | 0.00 | 0.00 | 0.00 | 2.45 | 4.37 | > 8min | 31.33 | > 1hr |
| coxl2 | 0.00 | 0.00 | 8.12 | 0.00 | 0.00 | 0.00 | 5.75 | 0.42 | 212.00 | memory | memory |
| crownj | 0.00 | 0.00 | 90.03 | 0.02 | 0.04 | 0.00 | 28.37 | 16.10 | > 8min | 104.30 | > 1hr |
| cutler | 0.00 | 0.00 | 0.02 | 0.01 | 0.00 | 0.00 | 0.02 | 4.55 | 3.49 | 2.83 | > 1hr |
| czyzec | 0.00 | 0.00 | memory | memory | 0.00 | memory | memory | 0.00 | memory | memory | memory |
| fernap3 | 0.00 | 0.00 | 3.33 | 0.00 | 0.00 | 0.00 | 2.24 | 0.96 | > 8min | 14.94 | memory |
| freidm | 0.00 | 0.00 | 0.01 | 0.00 | 0.01 | 0.00 | 0.50 | 4.39 | > 8min | 38.30 | > 1hr |
| gastoj3 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.05 | 0.62 | 2.38 | 0.72 | 124.00 |
| hebers | incorrect | incorrect | incorrect | incorrect | incorrect | incorrect | incorrect | incorrect | incorrect | incorrect | incorrect |
| henryb | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.60 | 301.00 | 4.37 | > 1hr |
| hunta3 | 0.00 | 0.00 | 0.02 | 0.01 | 0.00 | 0.00 | 1.24 | 25.85 | > 8min | > 8min | > 1hr |
| johnsc12 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | incorrect | incorrect | incorrect |
| krissj | 0.00 | 0.00 | 0.03 | 0.00 | 0.01 | 0.00 | 0.07 | 2.00 | memory | memory | memory |
| langed2 | error | error | error | error | error | error | error | error | error | error | error |
| meisse2 | 0.00 | 0.00 | 0.00 | 0.11 | 0.00 | 0.05 | error | error | memory | memory | memory |
| millmm | 0.00 | 0.00 | 0.04 | 0.06 | 0.00 | 0.02 | 0.55 | 26.20 | 18.02 | 11.99 | > 1hr |
| papesm | > 1min | > 1min | > 1min | > 1min | > 1min | > 1min | > 1min | > 1min | > 8min | > 8min | > 1hr |
| perrym5 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 1.21 | > time | 7.13 | > 1hr |
| peryel | incorrect | incorrect | incorrect | incorrect | incorrect | incorrect | incorrect | incorrect | incorrect | incorrect | incorrect |
| portew | 0.00 | 0.00 | 0.01 | 0.00 | 0.01 | 0.00 | 143.00 | 0.70 | > 8min | > 8min | > 1hr |
| robers5 | error | error | error | error | error | error | error | error | error | error | error |
| schuln3 | 0.00 | 0.00 | 0.00 | 0.01 | 0.00 | 0.00 | 0.15 | 14.44 | > 8min | 80.17 | > 1hr |
| skurkj | 0.00 | 0.00 | memory | 1.58 | 0.01 | 17.30 | 0.26 | memory | memory | memory | memory |
| todisk | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.55 | 1.04 | > 8min | 5.92 | > 1hr |
| valerj3 | 0.00 | 0.00 | memory | memory | 0.00 | 0.21 | memory | memory | memory | memory | memory |
| wakefp | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.03 | 1.38 | > 8min | 20.55 | > 1hr |
| wangy14 | incorrect | incorrect | incorrect | incorrect | incorrect | incorrect | incorrect | incorrect | incorrect | incorrect | incorrect |
| wellir | 0.00 | 0.00 | 0.01 | 0.00 | 0.00 | 0.00 | 0.02 | 6.26 | > 8min | 43.18 | > 1hr |
| wildec2 | incorrect | incorrect | incorrect | incorrect | incorrect | incorrect | incorrect | incorrect | incorrect | incorrect | incorrect |
| wongp3 | 0.00 | 0.00 | 0.03 | 0.01 | 0.01 | 0.00 | 4.28 | 13.34 | > 8min | 49.25 | > 1hr |
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).
The first 8 puzzles are on the calendar. 3 new puzzles were used for the contest:
Puzzle 9,
Puzzle 10, and
Puzzle 11.
OVERALL CONTEST WINNER
- Jeff Gaston