CSCI 1200 Data Structures
Fall 2011
Home
  Contact Information

Announcements
  LMS

Syllabus
  Learning Outcomes
  Prerequistites
  Grading Criteria

References
  Optional Textbooks
  Web Resources
  C++ Development
  Memory Debugging
  Misc. Programming Info

Getting Help
  Tutoring
  Advice from TAs

Calendar
  Lecture notes
  Lab materials
  Homework
  Test reviews

Schedule
  Office Hours
  Lab Times

Academic Integrity

Homework
  Due Date and Time
  Late Day Policy
  Compilers
  Electronic Submission

Homework 6 Contest Results

Description of Optimizations

  • allmec :
  • barbia : sort pieces by area
  • berkln : minimize calls to add & remove block
  • bulged :
  • chens12 :
  • cookkc :
  • cropps : sort pieces by area, mirror/flip solutions (if not symmetric)
  • cutler : sort pieces, use an "unrolled" array, check for holes, if no holes, always try to "fill" the upper left-most hole, if no piece fits prune further search
  • derosa3 : 2 different methods of solving, chooses best based on puzzle data, stores next free position to avoid re-checking filled areas, sort pieces by area, allocation on stack
  • didycn : recursive vs iteration
  • dingf : added -no_print option
  • duncam2 :
  • ferres2 :
  • gamblc :
  • giacof : sort pieces by area, early exit in collision detection
  • goldbj5 : sort pieces by area
  • grubej2 :
  • hancom : sort pieces by area,
  • houc : assumes no holes
  • jacksj5 : faster overlap test,
  • janser :
  • jink2 :
  • kaiseb2 :
  • kaua : some piece placement rules to avoid putting pieces where they don't fit
  • kellet : mirroring of solutions
  • leblas :
  • lowens : sort pieces, avoid copying, check for out of bounds, store commonly used values
  • oconnk6 : w/ & w/o holes handled separately, sort pieces by area, eliminate some duplicate checks
  • pongb :
  • shasta : eliminated extra checks
  • songy4 :
  • spitzj3 : sort pieces, get rid of redundancy
  • stephr2 :
  • tenedt : sorted pieces by area
  • todds : sorted pieces by area, pass by reference, \n instead of endl, avoid checks outside of box
  • ulins :
  • weirc :
  • yongsn : all except squared square, does not solve hole cases
  • zhoup :

Results

  puzzle1 puzzle2 puzzle3 puzzle4 puzzle5 puzzle6 bcp_9_piece bcp_15_piece squared_square derosa3_3d_box derosa3_3x3_3x3_grid didycn ferres2_2 ferres2_3 ferres2_4 hancom todds (single)
puzzle5		 (single)
kellet		 (single)
lowens_1		 (single)
bcp_9_piece		 (single)
bcp_15_piece		 (single)
squared_square		 (w/rotation)
rotatable		 (w/rotation)
puzzle1		 (w/rotation)
puzzle3		 (w/rotation)
puzzle4		 (w/rotation)
puzzle6
allmec 0m0.001s 0m0.000s 0m0.005s 0m4.570s incorrect 0m0.001s incorrect     0m0.032s 3m28.100s 0m0.003s 0m1.075s 0m0.359s 0m0.000s 0m2.062s               0m0.000s incorrect incorrect   0m0.001s
barbia incorrect incorrect incorrect incorrect incorrect incorrect incorrect     incorrect incorrect incorrect incorrect incorrect incorrect incorrect incorrect                      
berkln incorrect 0m0.000s incorrect incorrect incorrect incorrect incorrect     incorrect incorrect incorrect incorrect 0m0.000s incorrect incorrect incorrect                      
bulged 0m0.001s 0m0.000s 0m0.001s 0m0.044s 0m0.127s 0m0.001s > 60m0.0s     0m0.003s 0m52.925s 0m0.010s incorrect 0m0.000s 0m0.000s 0m4.226s 0m7.315s incorrect incorrect incorrect incorrect incorrect incorrect          
chens12 0m0.001s 0m0.001s 0m0.002s 0m0.381s 0m0.310s 0m0.001s > 60m0.0s     0m0.292s 6m10.820s 0m0.002s 2m42.206s 0m0.000s 0m0.000s 0m1.883s 0m35.622s 0m0.001s 0m0.018s incorrect 1m0.205s              
cookkc incorrect incorrect incorrect incorrect incorrect incorrect incorrect     incorrect incorrect incorrect incorrect incorrect incorrect incorrect incorrect                      
cropps incorrect incorrect incorrect incorrect incorrect incorrect incorrect     incorrect incorrect incorrect incorrect incorrect incorrect incorrect incorrect                      
cutler 0m0.000s 0m0.000s 0m0.000s 0m0.002s 0m0.490s 0m0.000s 0m0.010s 0m0.953s 50m36.132s 0m0.001s 0m2.635s 0m0.001s 0m0.261s 0m0.000s 0m0.000s 0m1.022s 0m0.863s 0m0.000s 0m0.001s 0m0.000s 0m0.001s 0m0.003s 0m0.397s 0m0.000s 0m0.001s 0m0.001s 0m0.035s incorrect
derosa3 0m0.000s 0m0.000s 0m0.000s 0m0.001s 0m0.033s 0m0.000s 0m0.002s 0m0.079s 19m0.745s 0m0.001s 0m2.860s 0m0.002s 0m0.303s 0m0.000s 0m0.000s 0m0.890s 0m0.996s 0m0.000s 0m0.000s 0m0.000s 0m0.001s 0m0.002s 0m0.052s 0m0.000s 0m0.001s 0m0.001s 0m0.035s 0m0.001s
didycn 0m0.000s 0m0.000s 0m0.001s 0m0.071s incorrect 0m0.000s > 60m0.0s     0m0.001s 0m8.142s 0m0.001s 0m0.381s 0m0.000s 0m0.000s 0m0.937s incorrect             0m0.000s 0m0.001s 0m0.002s 0m2.313s 0m0.000s
dingf 0m0.000s 0m0.000s 0m0.001s 0m0.031s 0m0.076s 0m0.000s > 60m0.0s     0m0.002s 0m27.077s 0m0.004s 0m0.297s 0m0.000s 0m0.000s 0m1.309s 0m3.506s 0m0.060s incorrect incorrect 1m0.210s incorrect incorrect          
duncam2 incorrect incorrect incorrect incorrect incorrect incorrect incorrect     incorrect incorrect incorrect incorrect incorrect incorrect incorrect incorrect                      
ferres2 incorrect incorrect incorrect incorrect incorrect incorrect incorrect     incorrect incorrect incorrect incorrect incorrect incorrect incorrect incorrect                      
gamblc 0m0.000s 0m0.000s 0m0.001s 0m0.026s 0m0.063s 0m0.000s > 60m0.0s     0m0.002s 0m24.273s 0m0.004s 0m0.330s 0m0.000s 0m0.000s 0m1.126s 0m3.304s incorrect incorrect incorrect incorrect incorrect incorrect          
giacof incorrect incorrect incorrect incorrect incorrect incorrect incorrect     incorrect incorrect incorrect incorrect incorrect incorrect incorrect incorrect                      
goldbj5 0m0.000s 0m0.000s 0m0.000s 0m0.189s incorrect 0m0.000s > 60m0.0s     0m0.005s 0m7.718s 0m0.002s 0m0.365s incorrect 0m0.000s 0m1.087s 0m1.775s                      
grubej2 incorrect incorrect incorrect incorrect incorrect incorrect incorrect     incorrect incorrect incorrect incorrect incorrect incorrect incorrect incorrect                      
hancom 0m0.000s 0m0.000s 0m0.000s 0m0.006s 0m0.021s 0m0.000s > 60m0.0s     0m0.001s 0m6.718s 0m0.001s 0m0.133s 0m0.000s 0m0.000s 0m0.531s 0m0.993s incorrect incorrect incorrect incorrect incorrect incorrect          
houc 0m0.000s 0m0.000s 0m0.000s 0m0.018s 0m2.586s incorrect 0m0.016s 0m2.010s > 60m0.0s incorrect 0m1.557s 0m0.002s incorrect 0m0.000s 0m0.000s 0m0.616s 0m0.629s                      
jacksj5 0m0.001s 0m0.000s 0m0.001s 0m0.033s 0m0.202s 0m0.001s incorrect     0m0.002s incorrect 0m0.009s 0m0.625s incorrect 0m0.000s 0m5.846s incorrect incorrect incorrect incorrect incorrect incorrect incorrect incorrect incorrect incorrect incorrect incorrect
janser incorrect 0m0.000s incorrect 0m0.009s incorrect incorrect incorrect     incorrect incorrect incorrect incorrect 0m0.000s incorrect incorrect incorrect                      
jink2 0m0.001s 0m0.000s 0m0.001s 0m0.014s 0m0.058s 0m0.000s 0m33.156s     0m0.010s 0m5.912s 0m0.002s incorrect 0m0.000s 0m0.000s 0m1.661s 0m1.825s incorrect incorrect incorrect incorrect incorrect incorrect          
kaiseb2 incorrect incorrect incorrect incorrect incorrect incorrect incorrect     incorrect incorrect incorrect incorrect incorrect incorrect incorrect incorrect                      
kaua 0m0.001s 0m0.000s 0m0.001s 0m0.016s 0m0.076s 0m0.000s 1m1.362s     0m0.002s 0m4.297s 0m0.005s incorrect 0m0.000s 0m0.000s 0m1.529s 0m1.572s 0m0.000s 0m0.001s 0m0.000s 0m1.275s incorrect incorrect incorrect incorrect incorrect incorrect incorrect
kellet 0m0.004s 0m0.001s 0m0.011s 0m7.287s 0m2.998s 0m0.001s > 60m0.0s     0m0.103s > 10m0.0s 0m0.066s 1m45.444s incorrect 0m0.001s > 10m0.0s > 10m0.0s 0m0.005s 0m0.348s incorrect 1m0.200s incorrect incorrect          
leblas incorrect incorrect incorrect incorrect incorrect incorrect incorrect     incorrect incorrect incorrect incorrect incorrect incorrect incorrect incorrect                      
lowens 0m0.000s 0m0.000s 0m0.000s 0m0.005s 0m0.027s 0m0.000s > 60m0.0s     0m0.001s 0m6.304s 0m0.001s 0m0.214s 0m0.000s 0m0.000s 0m0.512s 0m1.270s incorrect incorrect incorrect incorrect incorrect incorrect          
oconnk6 0m0.001s 0m0.000s 0m0.001s 0m0.012s 0m5.405s 0m0.001s 0m0.011s 0m1.127s > 60m0.0s 0m0.359s 0m4.212s 0m0.002s incorrect 0m0.000s 0m0.000s 0m1.466s 0m1.401s incorrect incorrect incorrect incorrect incorrect incorrect          
pongb 0m0.001s 0m0.000s 0m0.001s 0m0.051s 0m0.089s 0m0.000s > 60m0.0s     0m0.005s 0m51.103s 0m0.002s 0m0.582s 0m0.000s 0m0.000s 0m1.162s 0m6.463s incorrect incorrect incorrect incorrect incorrect incorrect          
shasta 0m0.003s 0m0.003s 0m0.003s incorrect incorrect 0m0.117s > 60m0.0s     incorrect > 10m0.0s 0m0.109s > 10m0.0s incorrect 0m0.000s incorrect incorrect                      
songy4 0m0.000s 0m0.000s 0m0.000s 0m0.004s 0m0.032s 0m0.000s > 60m0.0s     0m0.001s 0m6.480s 0m0.001s 0m0.311s 0m0.000s 0m0.000s 0m0.766s 0m1.312s incorrect incorrect incorrect incorrect incorrect incorrect          
spitzj3 0m0.002s 0m0.001s 0m0.007s 0m6.570s 0m3.822s 0m0.001s > 60m0.0s     0m1.415s > 10m0.0s 0m0.018s 0m2.655s 0m0.009s 0m0.001s 0m6.713s incorrect incorrect incorrect incorrect incorrect incorrect incorrect          
stephr2 0m0.001s 0m0.000s 0m0.001s 0m0.077s 0m16.958s incorrect 0m0.046s     incorrect 0m5.098s 0m0.006s incorrect 0m0.000s 0m0.000s 0m1.864s 0m1.981s                      
tenedt 0m0.000s 0m0.000s 0m0.001s 0m0.013s 0m0.050s 0m0.000s > 60m0.0s     0m0.001s 0m19.989s 0m0.001s 0m0.216s 0m0.000s 0m0.000s 0m1.068s 0m2.475s incorrect incorrect incorrect incorrect incorrect incorrect          
todds 0m0.000s 0m0.000s 0m0.000s 0m0.009s 0m0.036s 0m0.000s > 60m0.0s     0m0.001s 0m10.055s 0m0.001s 0m0.360s 0m0.000s 0m0.000s 0m0.893s 0m2.130s incorrect incorrect incorrect incorrect incorrect incorrect          
ulins 0m0.001s 0m0.000s 0m0.006s 0m0.721s incorrect 0m0.001s > 60m0.0s     0m0.009s 1m10.833s 0m0.004s 0m0.959s 0m0.232s 0m0.000s 0m3.723s incorrect                      
weirc incorrect incorrect incorrect incorrect incorrect incorrect incorrect     incorrect incorrect incorrect incorrect incorrect incorrect incorrect incorrect                      
yongsn 0m0.001s 0m0.000s 0m0.001s 0m0.042s 0m16.036s incorrect 0m0.136s 0m40.488s > 60m0.0s incorrect 0m8.699s 0m0.002s incorrect 0m0.001s 0m0.000s 0m1.615s incorrect                      
zhoup 0m0.001s 0m0.001s 0m0.001s 0m2.401s incorrect incorrect 0m28.660s     incorrect 0m5.999s 0m0.002s incorrect 0m0.002s incorrect 0m1.657s incorrect                      

Additional Test Cases

  • derosa3_3d_box : 4 narrow pieces with a big hole in the center
  • derosa3_3x3_3x3_grid : 9 3x3 pieces in 9x9 board, 362880 solutions!
  • didycn : all permutations of 6 letters
  • ferrec : several different puzzles with 2-9 pieces, w/ & w/0 holes
  • hancom : 3x3 board, 9 1x1 pieces, 362880 solutions!
  • kellet : 15 pieces, 19x20 board
  • lowens : 4x3 grid, 12 1x1 pieces, 479001600 solutions! & another puzzle with 0 pieces
  • todds : 9 pieces, 12x12 board some duplicates
  • zhoup : 2 different small board, 4 piece puzzles
  • rotateable : 2 pieces, no holes, but rotation is necessary to fit

Prizes

HW6 Contest Winners

  • Overall Winner : Anthony DeRossi
  • Runners Up: Calvin Hou & Kevin O'Connor
  • Fast Single Solution :Alexander Kau
  • Best New Puzzle : Trevor Keller
  • Other Notable Submissions : Nutchanon Yongsatiancho & Seth Lowenstern