CSCI 1200 - Fall 2009
Data Structures
Home
  Contact Information

Announcements

Syllabus
  Learning Outcomes
  Prerequistites

Textbooks
  Web Resources
  Additional Tutoring
  LMS

Grading

Calendar
  Lecture notes
  Lab materials
  Homework
  Test reviews

Schedule
  Lab Times
  Office Hours

Academic Integrity

Homework
  Due Date and Time
  Late Day Policy
  Compilers
  Electronic Submission

Programming Tips

C++ Development
  Cygwin
  Emacs
  C++ IDEs

Other Information
  Command Line Args
  File I/O
  Redirecting I/O

HW6 Inverse Word Search Contest

DATA

 1 all2 all3 all4 all5 all6 all7 all8 all9 onesol9 all10 onesol10 all11 onesol11 all12 onesol
aldorm0m0.040s0m0.020s0m0.030s0m0.040s0m0.040s0m0.090s0m0.100s0m4.706s0m1.197s0m1.221s0m0.598s0m0.900s14m54.017s14m55.063s>5m
barrem40m0.040s0m0.040s0m0.210s0m0.100s0m0.090s0m0.080s0m30.664s0m15.912s0m0.906s0m4.627s0m0.031s0m4.324s14m22.120s74m5.395s0m0.591s
bishob20m0.030s0m0.020s0m2.143s0m0.230s0m0.050s0m0.410s0m0.811s4m43.527s>1m>9m0m12.384sincorrect >1hr0m4.397s
chalda0m0.020s0m0.020s0m0.100s0m0.030s0m0.040s0m0.060s0m1.912s0m8.612s>1m>9m>20s0m24.836s >1hrcrashed
cryerjNo outputNo outputNo outputNo outputNo outputNo outputNo outputNo outputNo outputNo outputNo outputNo output   
cutler0m0.030s0m0.030s0m1.351s0m0.971s0m0.070s0m0.350s0m0.831s6m31.162s0m6.023s1m0.635s0m0.487s0m44.455s>16m>30m0m0.271s
delgoc0m0.030s0m0.060s0m11.997s0m2.022s0m6.970sincorrect>1m>1m>1m>9m>1m>9m  >5m
felizd0m0.030s0m0.050s0m0.060s0m0.050s0m0.040sincorrectincorrect0m33.257s>1m>9m>1mincorrect  >5m
grubbm2>1m>1m>1m>1m>1m>1m>1m>1m>1m>9m>1m>9m  >5m
horowm0m0.030s0m0.020s0m0.190s0m0.160s0m0.080s0m0.140s0m0.160s>1m>1m>9m>1m>9m  >5m
iaconn0m0.030s0m0.030s0m0.080s0m0.130s0m0.050s0m0.140s0m0.160s0m53.567s0m0.363s0m10.494s0m0.138s0m15.123s>16m>30m0m1.925s
interj20m0.020s0m0.030s0m0.060s0m0.050s0m0.040s>1m0m8.782s0m17.435s0m36.103s>9m0m0.490s0m35.475s>16m 0m0.190s
kellem40m0.020s0m0.020s>1m0m0.310s0m0.731s0m0.160s0m7.050s>1m>1m>9m0m2.152sincorrect>16m 0m0.671s
keohaa0m0.020s0m0.030s0m0.040s0m0.030s0m0.030s0m0.040s0m31.935s0m1.882s0m52.007s>9m0m0.353s0m15.827s8m44.725s>70m0m0.430s
kueblc0m0.020s0m0.020s>1m0m0.320s0m0.170s0m0.110s>1m>1m>1m>9m0m3.515s>9m   
lipsct0m0.010s0m0.009s0m1.208s0m0.340s0m0.156s0m0.173s0m6.721s> 1min>1m>9m>1m>9m   
matthj50m0.040sincorrectincorrectincorrect>1mincorrect>1mincorrectincorrectincorrectincorrectincorrect   
mcguia0m0.030s0m0.030s0m1.612s0m1.452s0m0.670sincorrectincorrect>1m0m0.040sincorrect0m0.030sincorrect   
milant0m0.030s0m0.030s0m1.331s>1mincorrectincorrectincorrect>1m       
sankan0m0.040s0m0.020s0m0.240s0m0.310s0m0.080s0m0.180s0m48.910s>1m>1m>9m>1m>9m   
shermj40m0.030s0m0.030sincorrectincorrectincorrectincorrectincorrect>1m>1m>9m>1mincorrect   
staufb0m0.030s0m0.040s0m5.007s0m3.114s0m0.660s0m0.841s0m6.869s>1m0m1.340s>9m>1m>9m   
usherm0m0.030s0m0.020s0m0.060s0m0.030s0m0.040s0m0.040s1m56.647s0m6.609s>1m>9m0m0.496s0m21.255s>16m 0m12.608s
vanclj0m0.030s0m0.030s0m2.834s0m1.692s0m0.711s0m0.380sincorrect>1m>1m>9m>1m>9m   

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, Puzzle 11, and Puzzle 12.

OPTIMIZATIONS

  • aldorm:   sorts required & banned word lists, inserts rotations & reflections of each found solutions, first word only inserted in upper left of board, single characters do not need to be oriented
  • barrem4:   reduces permutations necessary to fill in blanks, improved test for duplicate solutions, uses pass by reference
  • bishob2:   special algorithm for diagonally asymmetrical boards
  • cutler:   used a 1D unrolled array rather than an array of arrays, reduced copying of data structures, inserts rotations & reflections of each found solutions, first word only inserted in upper left of board, sorted words by length, check for forbidden words frequently
  • felizd:   reduces number of recursive calls, checks if words are substrings of other words
  • horowm:   uses inline functions
  • iaconn:   reduced calls to size(), checks word length before inserting word, sorts words by length, first word only inserted in upper left of board, uses integers rather than class objects, uses pass by reference when possible
  • interj2:   inserts rotations & reflections of each found solutions
  • kellem4:   checks word length before inserting word
  • keohaa:   check for illegal words before filling blank spaces, reduces checking & looping
  • lipsct:   reduces calls to the letter filling code
  • mcguia:   sorts words by length, checks for forbidden words after every insertion
  • sankan:   checks word length before inserting word
  • shermj4:   inserts rotations & reflections(?)
  • staufb:   checks for restricted words after each inserted letter
  • usherm:   loop unrolling, checks word length before inserting word

CONTEST WINNERS

  • Fastest to find ALL solutions: Marc Aldorasi
  • Fastest to find ONE solutions: Andrew Keohane
  • Honorable Mentions: Max Barrett-Lhu, Nicholas Iaconis, Joseph Internicola, Matthew Keller