drawsomething

CS106XHandout20

Summer2006July14,2006

Assignment3:TheDraw

ThisassignmentwaswrittenbyJerry.

EverwonderwhatsortofmagictheHousingOfficeustoassignstudentstohousing

comespring?Metoo!SoIdecidedtofindout!

Due:Friday,July21stat9:30a.m.

Thisweek'sassignmentisafull-fledgedC++toolthattakescareofeverylastdetail

ofyouunfamiliarwith

theStanfordHousingLottery,thisistheprocesswhichdetermineswholiveswhere.

Fraughtwithtensionandhope,theenjoyment(ortorture)ofthefollowingyearhangs

histhefactthatstudentsmayenterthe

housinglotteryingroupsofuptotwelve,andthepotentialforcomplexityisgreat.

Eachdrawsubmitsitshousingchoicestothehousingoffice,theneachgroupisgivena

uniquebutotherwirandomnumberbetween1andthetotalnumberofgroups.

Whenallgroupshaveentered,groupsareassignedtohousindrawnumberorder,

lowernumbersfirst,onaspace-availablebasis.

Note:youmayulatedaysifyouwantto,butumorethanonelatedayandyou’re

odethisassignmentup,andyou

codeitupwell,thenIguaranteeyouyou’signment

looksmuchmoreintimidatingthanitreallyis,butitreallyworksvirtuallyeveryaspect

ofC++thatwe’velearnedtodate.

2

TheDataStructures

Thefourdatastructuresyou'llbeusingtocompletetheassignmenthavealreadybeen

ethefirsttwo:

#defineMaxStudentsPerGroup12

#defineMaxPreferenceListLength8

enumgender{

Male,Female,NumGenders

};

structstudentRec{

stringstudentName;

stringsuidNumber;

genderstudentGender;

structdormRec*assignedDorm;

};

structdormRec{

stringhouName;

inthouID;

intmaxNumAssigned[NumGenders];

studentRec**assignedResidents;

intactualNumAssigned[NumGenders];

inthighestDrawNumber[NumGenders];

};

AstudentRecisarecordthatbundlesalltheinformationaboutoneStanford

student–includingname,SUID(whichIconstraintobeastring),

ec

maintainsinformationaboutasingleStanfordresidence–attributessuchasdormname,

housingIDnumber(asudbytheStanfordhousingoffice),andmaximumoccupancy

ecalsocontainsinformationrelevanttothehousinglottery,such

astheactualnumberofstudentsassignedbygender,thehighestdrawnumberoftho

studentsassignedtothedormbygender,andthenfinally,adynamicallyallocatedarray

ofstudentRec*swhichcontainspointerstothestudentRecrecordsofthestudents

rayneedstobedynamicallyallocated,becauthe

maximumnumberofstudentsthatcanbehoudinanyparticulardormitoryvaries

greatlyanddependsonthedormitory(compareXanadutoRoble,forexample.)

Theothertwodatastructuresaredefinedasfollows:

structdrawGroupRec{

studentRec*students[MaxStudentsPerGroup];

intnumStudents;

dormRec*dormPreferences[MaxPreferenceListLength];

intnumPreferences;

intdrawNumber;

boolassignAnywhere;

};

3

structstanfordHousingDBRec{

studentRec*stanfordStudents;

intnumStudents;

dormRec*stanfordDorms;

intnumDorms;

drawGroupRec*drawGroups;

intnumDrawGroups;

};

AdrawG

maintainsalistofitsmembers,thenumberofmembers,theresidencesontheir

preferenceslist,thenumberofhousintheirpreferencelists,theirdrawnumberinthe

lottery,andaboolwhichindicateswhetherornottheyarewillingtobeassigned

anywhereoncampusiftheycan’tbeaccommodatedinoneoftheirpreferreddorms.

scribedinmoredetailbelow.

Threeofeightfunctionsyou'llbewritingaredesignedtoinitializethesingleinstanceof

astanfordHousingDBRec.

Themainfunction

warethat

youhaveamidtermnextTuesdaynight,I'vedecidedtostructureanddecompoyour

’llfinishitoffbywritingeighthelperfunctionstoreadindata

files,assignrandomdrawnumbers,assigndrawgroupstohous,anddumptheresults

ofthehousinglotterytoabunchofoutputfiles—oneforeachofthefifty-nine

dormitorieswhichhousupperclassmen.

ThemainfunctionIgiveyouisawelldecompodoutlineofthestepsthatneedtobe

takentoreadinalldata,assigndrawgroupstodormitories,andthenwritetheresultof

nfunctionthatI'vealreadywritten

foryoulookslikeso:

intmain()

{

InitHousingGraphics();

stanfordHousingDBRecstanford;

ReadInStudentData(stanford);

ReadInHousingData(stanford);

ReadInPreferences(stanford);

AssignDrawNumbers(stanford);

SortByDrawNumber(stanford);

AssignToDorms(stanford);

GenerateAssignmentFiles(stanford);

FreeStanford(stanford);

return0;

}

4

AsinglestanfordHousingDBRec(DBstandsfordataba)isneededtostoreallofthe

studentandhousingdatathatwillbeudtoassignthestudentswhoenterthedraw.

Someimportantfeaturesworthnoting:

•stanfordisdeclaredtobeastanfordHousingRecandnotapointer-to-

ingapointerallocatexactly4bytes–justenoughto

storeapointerandthat'aringabonafidestanfordHousingRec,weget

alloftheassociatedmemorywhenweenterthemainfunction,andallofthevarious

fieldsoftherecordcanbeupdatedbytheeighthelperfunctionsifwetakecareto

ingstanfordbyreference,mainsharesits

variablespacewithallofthehelperfunctions,therebyallowingeachtoinitializeor

otherwimanipulateitscontents.

•onemightbetemptedtodynamicallyallocatethespacefortherecordinsteadof

declaringitonthestack,ousinglotteryusone

andexactlyonestanfordHousingRec,andbecauweknowthisbeforeweeven

compile,weshoulddeclareallthespaceweneedfortheentirerecordinonetinyline

ydynamicallyallocatememorywheneverdecisionsaboutsizecan

'exactlyoneeverytime.

•phicelementtothisassignmentis

prettycontrived,’sherefornootherreasonthattoputaprettyface

ontheapplicationandtoanimatetheprogressoftheapplicationasdrawgroupsare

’tneedtobotherwiththegraphicsifyoudon’t

ou’dliketoimitatethesampleapplicationasmuchaspossible,then

facefiletogetwordonwhat

’shardlyrocketscience,soI’llleaveittoyouto

figureitout.

Task1:WritingReadInStudentData

stanfordisconstructedinveralstages,thefirstthreeofwhichinvolvetheprocessing

oflargedatafilesofstudentsprofiles,housingoccupancystatistics,anddrawgroup

StudentData'sprimaryresponsibilityistoparaninputfilethat

edoesn'tcontainany

housingpreferencesforthestudents;rather,itcontainsinformationthatmightbe

availablefromtheRegistrar'sOffice–fullname,SUIDnumber,hree

piecesofinformationareparticularlyimportanttothorunningthehousinglottery,

becauSUIDnumbersmightbeudtopostresultswithoutidentifyingstudentsby

name,andgenderinformationiscrucialbecaualmostalluniversitydormitoriesmake

theefforttohaveascloa50/50female-to-malepopulationaspossible.

Theinformationstoredinthestudentdatafileisudtoinitializethefirsttwofieldsof

main'sstanfordHousingDBRec.

5

structstanfordHousingDBRec{

studentRec*stanfordStudents;

intnumStudents;

dormRec*stanfordDorms;

intnumDorms;

drawGroupRec*drawGroups;

intnumDrawGroups;

};

BecauthestanfordStudentsfieldisastudentRec*,nomemorybeyondthe

pointergetsallocatedonthestack—youonlygetspaceforthepointer!Unlikethe

situationwiththestanfordHousingDBRecinmain,wepreferapointertoarecord

here,becauweonlylearnhowmanystudentrecordsareneededafterweopenand

partiallyprocessthestudentdatafile.

Hereistheformatofatypicalstudentdatafile:

2659<-numberoflineswhichfollowthisone

Aaron,Jessica:F3997080<-:

Aaslid,IveElisabeth:M4011835<-:

Abbruzze,ThomasAnthony:M4413843<-:

Abdullah,MohdAzhar:F4024164<-:

Abdullah,SharifahSahar:M4099207<-:

//etc..moredatafilesfollow

//........

Zweifach,Adam:F4230173<-:

Allstudentdatafilescontainastheirveryfirstlinethenumberofstudentsforwhich

xamplefileabove,theveryfirstlinecontaininga2659isa

dtoreadin

thisnumber(itwon'tnecessarilybe2659,itmaybesomethingdifferent)andthen

dynamicallyallocateanarrayofstudentRecsthat'sjustbigenoughtoholdthismany

inethatfollowsisformattedtocontainthenameofonestudent,that

student'sgender,andthatstudent’sSUIDnumber.(Ofcour,ImakeuptheSUID

numberstolooklikerealSUIDnumbers.)Eachstudentrecordneedstobestoredin

ertocache

thesizeofthearrayyoujustallocatedintothenumStudentsfieldsoyou'llknowhow

largethestanfordStudentsarrayislateronintheprogram!

Somehelpfulhints:

•llcomeinhandy

reyouprerve

thisorderasyoutransferthestudentinformationfromthedatafileintoyourdata

'oreeverything

asonelargestring.

•Thegenderinformationiscompletelymadeup!Whilegatheringthisinformation,I

wasn’tabletofindanyinformationabouttruegender,soIflippedagendercoinfor

orget

this,lestyou’llthinkthere’reproblemswithyourparsingroutine.

6

•YoushouldalsoinitializetheassignedDormfieldofallnewstudentRecstobe

NULL–that'llreprentthefactthatthestudenthasyetassignedtoadormitoryyet.

Don'tforgettodothis.

•Youcanassumethatthefileisproperlyformattedandthatyouneedn'terrorcheck

utmyhandoutOpenDataFileroutine,whichrepeatedlypromptsthe

urforafilenameuntilheorshetypesonein(oracceptsadefaultfilename)

Task2:WritingReadInHousingData

YournextjobistoimplementafunctioncalledReadInHousingData,whichtakesa

stanfordHousingDBRecreferenceandinitializesthethirdandfourthfieldsofthemaster

recordtocontainmeaningfuldata.

structstanfordHousingDBRec{

studentRec*stanfordStudents;

intnumStudents;

dormRec*stanfordDorms;

intnumDorms;

drawGroupRec*drawGroups;

intnumDrawGroups;

};

Inmanyways,theimplementationofReadInHousingDataisjustlikethatof

dtoopenanewdatafile,scaninthefirstlinetoehow

manylineswillfollowandhowlargeanarrayyouneedtostorealloftheinformation,

andthenreadineachlineonebyone,eachtimeinitializingexactlyoneofthedormRecs

singData

fileisformattedasfollows:

59<-numberoflineswhichfollow:

Cardenal:062Male:20Female:20x:6.97y:4.13<-informationforfirstdorm

Faisan:063Male:15Female:20x:6.97y:4.58<-informationforconddorm

Loro:065Male:23Female:22x:7.56y:4.58<-informationforthirddorm

Mirlo:066Male:25Female:25x:7.56y:4.13<-informationforfourthdorm

........

:Male:Female:x:y:

........

ZAP:994Male:18Female:17x:0.26y:4.84<-informationfor59thdorm

Thefirstlineofthehousingdatafilecontainsthenumberofdormsforwhich

informationismaintained(notnecessarily59.)AswithReadInStudentData,you

shoulduthisnumbertodynamicallyallocateanarrayofdormRecsjustlargeenough

toholdalloftheinformationmaintainedbythehousingfile.

Eachlinethatfollowscontainsthenameofadorm,itsidnumberasudbythehousing

office,thenumberofupperclassmenandwomenthatcanbehoudthere,andthex

andycoordinatesofthedormitoryonthemapdrawnbyInitHousingGraphics.

RecallthattheassignedResidentsfieldofthedormRecisdeclaredtobea

studentRec**.TheimplicationisthatassignedResidentswilleventuallybea

dynamicarrayofstudentRec*s,eachofwhichpointstosomestudentRecofthe

7

icular,apointertoastudentRecisstoredina

dorm'

readinginthemaximumnumberofmenandwomenthatcanbehoudinaparticular

dorm,youareabletodynamicallyallocateitsarrayofstudentRec*stobejustlarge

enoughtoholdthemaximumnumberofmenandwomenthatmightlaterbeassigned

uldn'tworryaboutinitializingtheindividualpointersinthearrayjust

yet;you'lltakecareofthatwhenweactuallyrunthelotteryanddotheassignments.

Justtakethetimenowtoallocatespaceforthepointersandthat'sit.

Afewtips:

•MakesuretoupdatethehighestDrawNumberandactualNumAssignedarraysto

containallzeroes.

•ThousinggHousingDrawshouldbesuretocallDrawHouToMapeverytimeyou

uToMapisafunctionexportedbythe

housingDrawInterfacemodule,andwillbringupacounteronthemap

wheneveryoucallitandspecifyadormname(asastring)andanxandy

hexandyvaluesarebeingreadinwiththerestofthedormitory

information,you'llwanttocallDrawHouToMapassoonaspossibleandthenforget

aboutthexandyvalues,sinceyou'untingonthe

graphicscanjustdiscardthexandyvalues(thoughyoustillneedtoparover

them!)

Task3:WrintingReadInPreferences

ThenextphainvolvestheimplementationofafunctioncalledReadInPreferences,

whichthefifthandsixthfields.

structstanfordHousingDBRec{

studentRec*stanfordStudents;

intnumStudents;

dormRec*stanfordDorms;

intnumDorms;

drawGroupRec*drawGroups;

intnumDrawGroups;

};

ReadInPreferencesiswrittentoparafilecontaininginformationaboutdraw

gledrawgroupcanhaveuptoamaximum

oftwelvestudents(althoughtheremaybeless),andeachcanlistuptoeightdormsinits

preferencelist(althoughtheremaybelessthaneightlisted).Housingpreferencefiles

areformattedasfollows:

8

7<-numdrawgroups

Mitchell,WilliamByrd:Y051<-group1endshere

Schwerer,ElizabethCarol:Y993987959<-group2endshere

Velamoor,GautamRangaraj:

Lin,PaulI-Lung:

King,AbbyC:

Kernal,HadynKendell:N966993964735<-group3endshere

Gerlach,Sharon:

Qi,Xiaoning:Y<-group4endshere

Galambos,LudwigL:

Wong,SuzanneShu-shan:

Burns,KristinR:Y996420965995<-group5endshere

Shirk,GrantAndrew:Y736051055<-group6endshere

Thefirstlinecontainsthenumberofdrawgroupsandpreferencelistsstoredinthat

tsofasingledrawgrouparelistedonelineafteranother(acolon

alwaysfollowsthestudentname),butthelastlineforanyonedrawgroupcontainsthe

preferencelist.

Intheabovefile,Mitchellishisowndrawgroup,Schwererisherowndrawgroup,and

Velamoor,Lin,King,isthelastmemberof

hisdrawgroup,becauheshareshislinewithhisgroup’spreferencelist.

Thepreferencelisthasitsownformat:ThefirstcharacterisalwaysaYoranN;Ymeans

thatgroupiswillingtobehoudanywhereoncampusiftheycan'tbeassignedtoany

tofthelinegoesontolistthehouIDoftheir

firstchoiceresidence,thentheircondchoice,etcetera,uptoamaximumofeight

ethenumberofpreferencesmayvaryfromdrawgrouptodrawgroup,

you’llwanttoenlistthervicesoftheistringstreamclass,whichallowingyourto

’llneedto#includeto

importthefulldefinition.

Task4:WritingAssignDrawNumbers

’tjustcallRandomInteger

andexpectadifferentnumbereverytime,

bottomlineisthatyouneedtoassignauniquebutotherwirandomnumbertoeach

showtogeneratearandompermutationofnumbers

between1and,oh,say…n?Checkthisout:

intnumbers[n];

for(inti=0;i

for(intlh=0;lh

intrh=RandomInteger(lh,n-1);

swap(numbers[lh],numbers[rh]);

}

cout<<"Anyoneofthen!Permutationsiquallylikely!"<

Nowwhydoesthiswork?

9

Task5:WritingSortByDrawNumber

Atthispoint,you'llwanttosortthedrawGroupsarrayofthestanfordHousingDBRec

sothatdrawGroupswithlowerdrawnumbersappearatlowerindicesthandraw

owillallowyoutotraverthedraw

groupsfromhigherprioritytolowerpriorityandassignalldrawgroupswithlower

drawnumbersfirst.

oughthe

implementationssortintegerarrays,thesamebasicalgorithmapplieswhetheryouare

sortingintegerarrays,stringarrays,ysubtlety:

ThemodifiedalgorithmshouldcomparethedrawNumberfieldsoftwo

drawGroupRecs,'tmakethe

mistakeofjustexchangingthedrawnumbers—doingsomightdevastatethowho

drewalownumberbuthappenedtobeinitiallystoredneartheendofthedrawGroups

ou'vetakencareofthisfunction,you'rereadytogoonandbegin

assigningstudentstohous.

Task6:WritingAssignToDorms

Nowcomesthetimewe'thoftheeightfunctionssimply

stepsthroughthesorteddrawGroupsarrayinyourstanfordHousingDBRec,

examinesthestoredpreferencelistsandattemptstoassignallthostudentsinthedraw

ofthehousontheirlistcanaccommodate

thefulldrawgroup,butthedrawgroupiswillingtoliveanywhereoncampus,then

raw

groupwouldprefertoremainunassigned,orifnodormsoncampuscanaccommodate

theentiregroup,thenthedrawgroupshouldjustremainunassigned.

Someimportantnotes:

•hestudentsinaparticulardraw

grou

noneoftheirchoiceshaveenoughspaceleftfortheentiregroup,butthegroupis

willingtoliveanywhereoncampus,thenthefullgroupshouldbeplacedinthefirst

ca,youwouldsimply

performalineararchofthestanfordDormsarraytofindthefirstresidencethat

canhoueverysinglestudentofthedrawgroup.

•Onceyoufindadormitorythatcanhouthem,youshouldstepthroughthe

studentsarrayofthedrawgroup,andupdatetheassignedDormfieldtopointto

allocatememoryforanewdormRec;juststoreapointertotheonewedgedinside

lalsowanttoupdatethedorm'sassignedResidents

arraytoincludepointerstotherecentlyassignedstudents,updatethe

actualNumAssignedarraytoreflectthatfactthatmoremenand/orwomenhave

beenassignedtothedorm,andupdatethedorm'shighestDrawNumberarrayeach

timeadrawgroupgetsassignedthere.

10

•Ifthedrawgroupremainsunassigned,thenyoushouldjustleavethe

whatitshouldhavebeent

toduringReadInStudentData.

•utthe

gHousingDrawinterfaceforthedetails.

•Itisso

astudentisn’tpartofsomedrawgroup,thenyoushouldjustignorehim/her.

Task7:WritingGenerateAssignmentFiles

Congratulations!!!You'vecompletedthefirstsixtasks,andthemostdifficultpartofthe

esthetimewhenyoumakeonefinalpassthrough

thestanfordDormsarray,andforeachdorminthearray,printtoafilevarious

statisticsaboutthathou(name,numberofassignedstudents,highestdrawnumberof

assignedmaleandfemaleresidents)andthengoontolisttheSUIDnumbersandnames

ofalloftheassignedstudents.

GenerateAssignmentFileswillgenerateafileforeachdorm,sothatthenumberof

outputfileswillalwaysbeequaltothenumberofdormsyoureadinduringTask2.

Youshouldjustuthenamesofthedormsforthenamesoftheoutputfile,andyou

arefreetoformatyourfilesinanyreasonablyreadablemanner,provideditcontainsthe

ple

applicationgeneratesoutputfilesthatlooklikethis:

Kimball:Assignmentbyname

NumberMalesAssigned:52

NumberFemalesAssigned:39

MaleCutoff:261

FemaleCutoff:101

4087381Alfano,ChristineLynn

4168405Martinn,Julia

......

......

4015588Clebsch,William

4007456Takara,NatashaYooko

4310755Li,HowardYeong-rung

4304407Lansden,Pamela

4210977Hackerman,ClaytonDavid

Somehelpfulhints:

•traver

theassignedResidentsarrayandprintoutthestudentinformationintheorder

'relookingforsomeextrawork,youmaywanttosort

theassignedResidentsarray(swappingpointers,notactualstudentRecs)

'snotrequiredthough.

•IfyouwanttoplacetheoutputfilesinsidethefoldernamedAssignments,asthe

sampleapplicationdoes,thenyoucandothatbyappendingthenameofthedorm

(whichwillrveasthefilename)to":Assignments:"(or"/Assignments/"for

11

thePC)Ratherthancreatingthenewfilesinthesamedirectoryastheprojectfile,

theapplicationwillplacethenewfilesinsidetheAssignmentsfolderifthereisan

dtomanually

createanAssignmentsfolderifthereisn'tonealreadythere.

•Whileitmayemreallyintimidatingtowriteafunctionwhichgeneratesbunches

andbunchesofnewfiles,youreallyonlyneedtoprovidearoutinethatgenerates

onenewoutputfile,andthencallitmultipletimes,oneforeachdorminthe

standfordDormsarray.

Task8:WritingFreeStanford

Iwantyoutotakeastabatfreeingallofthedynamicallyallocatedmemoryenlistedby

reyouonlyfreememoryallocated

ontheheap,neverfreethesameheapaddresstwice.

Accessingfiles

AwholebunchofmaterialshavebeenplacedintheAssignment3HousingDrawfolder.

Readthesuppliedinterfacesfirst.

interfaceforthegraphicalurinterfaceabstraction.

implementationofthegraphicalurinterface

llyshouldn’tlookatthiscode,

becauImadeverylittleefforttomakeitbeautiful.

rtialprogramwhichcontainsallofthedatastructure

definitionsandhelperfunctionsIwroteforyoutoassist

'satonofcode

inherealready,butbesureyouatleastunderstandthe

datastructuresandtheprototypesofthevenfunctions

you'llbeimplementing.

allerdatafilecontainingstudentnames,genders,

andidnumbers.

allerdatafilecontaininghounames,idnumbers,

maximumcapacities,andmapcoordinates.

allerdatafilecontainingdrawgroups,housing

preferencelists,andtheirwillingnesstoliveanywhere

oncampusifdormsontheirpreferencelistarealreadyat

capacity.

rylargedatafilecontainingstudentnames,genders,

andidnumbers.

tafilecontaininghounames,idnumbers,

maximumcapacities,andmapcoordinates(confession:

it'sidenticaltosmallHousingData)

preferencesData[1234].txtFourhugedatafilesofstudentpreferenceswhichshould

onlybeudafteryou'vefullytestedyourprogram

usingthesmallertestfiles.