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 leftmost 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 rechecking 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 29 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
