CSCI 1200 Data Structures
Fall 2010
Home
  Contact Information

Announcements
  LMS

Syllabus
  Learning Outcomes
  Prerequistites
  Grading Criteria

References
  Optional Textbooks
  Web Resources
  C++ Development
  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

HW8 City Chase Contest

CONTEST DETAILS

  • 67 evaders
  • 76 pursuers
  • 5 test graphs (3 simple, 2 student submissions)
  • 20 trials
  • up to 100 clock ticks per trial
  • Each table below shows the top 20 evaders (survived the longest), and
    the top 20 pursuers (caught the evader in fewest moves) on a particular graph.
    Each cell in the table is the average number of ticks until the evader is caught.
  • A 999.0 in a cell denotes either a seg fault, failure to compile, or program running too long
    This counts as a 100 for the pursuer and a 1 for the evader.

 

TWO CITIES: 1 cities, 1 link, 1 pursuer, 1 evader

Pursuersmillea9yaunegduffynkaplae2lbassbeojwaiteb3roberj13truhlbwillis4curram2wangz9steifcschled3heysesmorang2sterlameltzgfasanazamana
Evaders18.518.618.718.718.818.818.819.819.819.920.020.020.120.120.120.420.620.721.331.0
hant2100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0
pomerm100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0
nistam64.61.01.01.01.01.01.01.0100.0100.080.2100.0100.0100.0100.0100.0100.0100.0100.0100.01.0
tamham60.01.02.01.02.01.92.01.02.02.06.01.01.02.04.04.04.01.06.02.0100.0
tebbug49.72.01.01.01.01.01.01.02.02.03.01.01.03.01.01.02.09.01.022.01.0
millea949.74.02.01.02.03.02.01.01.01.01.01.01.01.03.02.05.02.09.012.01.0
dimioe49.61.01.02.02.01.02.03.01.01.04.01.01.01.03.01.01.014.03.09.01.0
schled349.64.01.03.03.01.02.02.02.01.06.01.03.01.02.01.01.01.04.012.01.0
foleys349.62.01.07.02.02.02.01.02.01.02.03.01.02.01.01.02.06.05.56.01.0
torrez49.62.03.01.02.01.06.04.02.01.01.02.04.03.01.01.04.01.07.02.01.0
rodrie749.62.01.02.01.09.04.01.02.03.01.02.01.02.02.04.02.04.01.02.01.0
milits249.62.01.03.01.02.01.01.02.02.03.02.04.01.04.01.01.01.03.011.01.0
warsae49.51.01.01.01.07.01.01.02.63.01.05.05.01.02.02.01.01.03.05.01.0
ricec249.51.02.01.01.01.01.01.01.01.02.02.01.05.01.06.01.01.02.013.01.0
cromak49.54.04.01.01.45.01.01.01.02.03.01.02.02.03.02.01.03.03.03.01.0
steifc49.53.01.03.01.01.05.04.01.01.05.06.01.01.61.01.01.01.01.04.01.0
zimmtn49.51.01.04.01.01.03.01.02.02.01.01.05.01.01.02.01.02.03.09.01.0
willis449.52.02.01.01.06.01.02.01.02.02.02.04.01.04.01.04.01.01.04.01.0
fasana49.53.02.01.01.01.03.01.01.02.03.01.02.02.01.08.05.01.01.01.01.0
oneilm649.51.01.02.04.01.01.03.05.01.01.52.02.02.01.02.01.02.06.01.31.0

 

CIRCLE: 6 cities, 5 links, 1 pursuer, 1 evader

Pursuerssterlamorang2lbassbtruhlbschled3millea9curram2willis4kaplae2heyseswaiteb3meltzgfasanaroberj13duffynzamanaeojsteifcpoiricchanb4
Evaders44.446.547.848.548.548.748.748.849.450.051.151.251.452.252.252.652.853.754.555.3
pomerm100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0
hant2100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0
schmir581.8100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0
foleys381.8100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0
cromak80.5100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0
sandes380.5100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0
fitchj80.5100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0
francr380.5100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0
wenslr80.5100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0
lynchj580.5100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0
fasana80.5100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0
xiaoz480.5100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0
curram280.5100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0
lbassb80.5100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0
tebbug80.5100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0
morang280.5100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0
bakera480.5100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0
poiric80.5100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0
milits280.5100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0
nistam70.33.04.0100.0100.0100.03.0100.02.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0

 

LINE: 5 cities, 4 link, 1 pursuer, 1 evaders

Pursuersroberj13curram2steifcwillis4truhlbmillea9schled3yaunegmorang2sterladuffynhowarc2lbassbpoiricnistamsandes3kaplae2heysesmeltzgfasana
Evaders20.721.421.521.521.722.626.627.627.828.029.629.830.330.631.932.032.533.233.233.6
hant2100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0
pomerm100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0
wenslr58.516.08.04.04.010.011.048.04.081.0100.068.09.09.04.04.04.053.011.037.07.0
sandes358.04.013.013.04.015.08.05.03.08.048.070.06.028.04.04.04.067.062.076.03.0
fasana57.83.013.022.027.08.03.011.011.046.063.010.015.573.03.03.03.044.038.04.021.0
cromak57.33.03.08.08.018.03.010.033.018.066.027.07.7100.03.03.03.031.07.0100.042.0
lynchj556.34.04.58.04.025.017.025.037.010.0100.014.08.018.04.04.04.04.042.036.015.0
foleys356.08.013.013.018.03.019.08.011.033.0100.022.012.08.03.03.03.029.031.520.043.0
willis455.73.03.03.04.04.03.04.04.09.06.017.04.013.03.03.03.015.026.05.017.0
hungw254.95.04.09.05.05.019.08.05.010.04.027.06.021.04.04.04.09.026.024.07.0
oneilm654.76.03.03.05.08.09.04.09.07.04.04.05.07.04.04.04.051.04.08.0100.0
truhlb54.02.09.03.07.03.026.020.06.020.09.012.04.03.04.02.04.042.05.030.59.0
weitht53.93.09.04.03.04.025.07.07.015.04.06.010.012.04.04.04.033.012.09.03.0
erickj353.43.03.02.02.02.04.04.011.04.93.06.05.03.02.02.02.08.026.013.04.0
dobbie53.33.03.05.02.02.04.011.05.04.03.06.06.06.02.02.02.05.014.016.02.0
roberj1353.22.02.04.02.02.03.05.03.07.04.04.05.02.02.02.02.03.05.051.03.0
lymank52.92.03.03.02.02.02.03.06.05.04.010.03.07.02.02.02.09.04.02.06.0
torrez52.73.02.04.02.02.03.05.05.04.03.02.06.58.02.02.02.05.07.04.02.0
wongw451.73.03.04.03.02.02.017.02.03.03.05.05.02.02.02.02.07.04.08.08.0
tamham49.73.03.04.03.03.03.03.018.03.026.02.07.04.0100.0100.0100.04.03.08.09.0

 

FRANCR3, 25 cities, 60 links, 5 pursuers, 5 evaders (after 33 ticks some cities removed, after 66 ticks more cities/links removed)

From francr3's README:
Here's a a crude diagram of it, arranged in a 5x5 grid with lines representing links

     ______  ______
/ \/ \
A1--A2 A3 A4--A5
/| \/ \/ | \
/ | /\ /\ | \
| B1 B2--B3--B4 B5 |
\ \/| \ | /| \/ /
\ /\| \| / | /\ /
C1 C2--C3--C4 C5
/ \/| /| \ | \/ \
/ /\| / | \| /\ \
| D1 D2--D3--D4 D5 |
\ | \/ \/ | /
\| /\ /\ | /
E1--E2 E3 E4--E5
\______/\______/

Pursuerswillis4foleys3curram2lbassbsteifcduffyntruhlbmorang2sterlalynchj5schled3honigaroberj13tebbugheyseswaiteb3eojchanb4zamanakaplae2
Evaders28.629.731.632.732.733.233.833.833.834.634.735.035.337.337.938.339.041.041.141.3
sandes361.913.035.046.224.069.1100.089.771.046.930.0100.0100.0100.088.047.057.0100.067.067.079.0
tebbug52.216.039.037.037.018.410.052.032.038.011.029.934.071.054.033.769.021.074.050.082.5
lynchj550.615.04.066.018.028.95.0100.020.0100.021.012.086.0100.023.029.054.013.013.06.0100.0
sterla49.112.016.053.817.812.728.054.164.155.040.052.028.054.060.831.049.032.034.039.614.0
tamham46.814.044.015.06.015.718.048.022.321.06.017.08.033.051.014.09.012.0100.032.311.0
steifc44.45.014.065.34.030.412.066.04.032.038.08.032.033.028.24.079.07.018.044.047.0
foleys343.48.033.05.025.025.424.042.018.0100.018.033.038.036.043.026.030.914.034.513.050.0
millea939.44.04.04.09.04.012.05.08.04.040.04.04.04.04.029.233.036.018.016.044.0
morang237.919.032.026.039.826.915.052.068.026.023.825.028.540.075.0100.049.096.012.035.615.0
fasana37.319.34.011.017.925.17.027.044.033.037.06.015.033.015.023.027.069.419.012.018.0
ricec237.24.04.04.012.04.013.04.04.06.010.010.04.04.04.08.058.04.029.06.029.0
zimmtn35.16.05.05.05.04.05.06.06.05.06.07.03.05.03.411.013.05.03.067.06.0
dimioe34.85.94.04.05.070.013.04.05.03.44.010.04.070.04.010.410.05.03.014.07.4
gerstr234.210.011.09.016.014.411.011.09.04.07.028.010.029.039.028.015.028.0100.0100.08.0
nistam33.510.04.03.03.010.04.04.1100.04.034.035.04.06.02.0100.038.035.410.713.0100.0
poiric33.317.012.066.047.845.338.04.022.04.032.027.017.019.044.073.049.054.030.036.067.0
wisec233.04.04.04.07.04.08.04.85.04.016.06.04.04.04.08.020.011.024.013.08.0
willis432.95.04.027.08.02.011.04.07.08.07.024.069.92.033.029.032.039.010.014.021.0
bakera432.65.04.04.033.018.239.711.019.532.021.510.011.011.025.04.013.755.040.06.026.0
hant232.633.033.033.033.033.033.033.033.033.033.033.033.033.033.033.033.033.033.033.033.0

 

WENSLR, flat dodecahedron 20 cities, 63 link, 5 pursuer, 5 evaders

Pursuerswillis4lbassbmorang2duffynsteifcschled3waiteb3eojmeltzgheysessterlahonigacromakjuffrrcurram2kaplae2roberj13tebbugwenslrtruhlb
Evaders28.332.834.935.238.038.138.840.242.142.242.943.244.344.644.745.045.446.347.548.1
pomerm100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0
hant2100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0
sandes375.158.0100.0100.041.0100.0100.0100.065.031.0100.0100.0100.0100.0100.0100.027.0100.0100.0100.0100.0
morang271.125.029.082.8100.068.444.0100.0100.086.0100.0100.046.040.7100.0100.0100.0100.076.0100.0100.0
poiric70.650.072.044.037.0100.046.034.0100.0100.053.0100.019.027.9100.0100.089.0100.043.0100.0100.0
tebbug65.36.081.029.052.022.0100.044.0100.075.419.053.0100.021.342.075.4100.0100.0100.098.4100.0
fasana65.047.017.023.026.0100.029.055.034.9100.032.0100.0100.0999.025.0100.0100.0100.0100.0100.0100.0
foleys364.530.034.018.0100.0100.021.09.0100.0100.079.0100.0100.0999.059.06.095.8100.0100.0100.0100.0
wenslr63.843.124.918.253.895.132.836.888.474.541.4100.019.226.360.9100.064.0100.026.5999.0100.0
weitht63.718.466.041.031.0100.07.0100.044.014.067.0100.026.023.015.0100.079.0100.027.0100.0100.0
fitchj63.28.014.06.08.025.010.042.012.091.035.0100.0100.0100.09.0100.044.0100.0100.0100.0100.0
bakera462.530.010.010.029.0100.024.858.020.017.041.09.0100.0999.019.0100.067.0100.0100.0100.0100.0
lynchj562.09.019.926.038.086.829.037.033.0100.065.1100.0100.0999.0100.0100.0100.0100.0100.0100.0100.0
steifc60.16.06.017.020.035.815.010.012.0100.031.0100.0100.012.6100.0100.0100.0100.0100.0100.0100.0
sterla58.226.074.030.026.055.033.823.022.024.038.038.816.029.454.4100.072.0100.025.025.9100.0
xiaoz456.914.08.033.09.014.011.035.026.067.013.013.0100.022.083.0100.022.0100.0100.0100.06.0
duffyn56.617.05.09.012.029.014.06.04.054.031.0100.0100.08.010.0100.054.0100.0100.0100.0100.0
francr356.122.023.236.020.259.524.022.062.358.628.0100.037.03.041.0100.035.04.05.0100.0100.0
lbassb56.010.046.024.021.013.015.043.023.017.091.0100.027.014.035.3100.019.0100.09.015.0100.0
willis454.516.013.012.044.013.015.011.032.061.011.011.0100.08.0100.0100.033.02.0100.0100.0100.0

 

SUMMARY: TOP EVADERS

trial_two_citiestrial_circletrial_linetrial_francr3trial_wenslrAverage Rankstrategy
pomerm1112015 hacks the pursuer code so the pursuer never moves
hant21112015 don't go to cities where pursuers stay
foleys3827776 evaluates "safety" of each city
fasana16341068 picks the city that the fewest tas can reach in one tick
lynchj523363129 find a city with fewest pursuer and most connecting cities
sandes343331210 moves randomly away from TAs and towards cities with neighbors
tebbug43352510 rating cities for safety based on number of pursuers surrounding city
tamham381952111 runs the pursuer strategy to figure out where the TAs are going
steifc1462061312 find cities pursuers can't get to in one tick
willis41558181913 looks for city with neighbors with no pursuers
nistam2422152714 move to a random city with no pursuers
oneilm6171410252017 move to a city that no TA can reach in one tick
weitht2791231918 scores each city by how many pursuers could move there
fitchj41324211020 check if the target move location doesn't have TAs and the neighbors don't have TAs
morang2563299320 look for safe neighbors
poiric5132816420 look for guaranteed safe neighbors, else move randomly
duffyn21736221620 look for guaranteed safe neighbors
truhlb291011242620 waits until pursuers get to neighboring city, then moves away
wenslr303260821 looks for viable escape strategies
roberj13201315273221 if the pursuer is in the neighbor, move to the neighbor assuming the pursuer will move too

 

SUMMARY: TOP PURSUERS

trial_two_citiestrial_circletrial_linetrial_francr3trial_wenslrAverage Rankstrategy
lbassb5313425 if student is in neighboring city, randomly decides to stay in place or move to that city
willis41084115 if two pursuers are in the same city, tries to work together
duffyn31511648 tries to avoid other pursuers to spread out
morang21629838 try to spread the pursuers out, choose randomly to move to the evader city if a neighbor
curram211723158 if an evader is in a neighbor, choose randomly to mve there
steifc13183559 calculate the shortest path to an evader who hasn't submitted homework, make sure pursuers don't go to the same city
truhlb9457209 searches for evader in a 2-city radius
schled314571169 if a student is in a neighboring city, choose randomly to move there
sterla1711091110 calculate "threat level" from evaders, how many evaders might move to each city
roberj138141131711 move closer to an evader, move randomly when in a neighboring city
kaplae24917201613 move randomly
millea9166282213 move to the city with the evader that has the fewest links
waiteb37112216713 move randomly, but follow the student if close
heyses151018151014 move randomly
eoj6172117814 move randomly
meltzg18121925917 move randomly but avoid evader dodge
yauneg2248243418 no readme
zamana201623192320 don't move if the student is nearby, move randomly otherwise
poiric241914212521 randomly decide to move to the city if it contains an evader
chanb4232024182422 moves randomly

PRIZES

  • Best (legal) Evader: Sam Foley
  • Best Pursuers (tie): Benjamin L'Bassi & Sarah Williams
  • Best Graph: Ryland France