Rush Hour

Rush Hour
Concurrency Opgave 3, Herfst 20141
Achtergrond
Rush Hour is een schuifpuzzel waarbij je door middel van het schuiven van andere auto’s op
het terrein je eigen auto moet proberen vrij te spelen. Je kunt op de website van ThinkFun
dit spel uitproberen. Als je het liever op je telefoon/tablet wilt uitproberen, kun je de app
”Unblock Me”(iOS/Android, gratis) downloaden die een heel vergelijkbare gameplay heeft
(maar niet van ThinkFun is).
Er staan horizontaal en vertikaal auto’s van verschillende lengtes op het spelbord. Je
kunt een horizontale auto alleen horizontaal, en een vertikale auto alleen vertikaal verplaatsen. Het doel is, om een gegeven auto naar het doelvakje te verplaatsen. Dit is alleen knap
lastig, omdat de andere auto’s in de weg staan. Zoek een zo kort mogelijke oplossing (zo
klein mogelijk aantal verschuivingen) om de auto naar zijn doel te brengen.
Opdracht
Voor deze opdracht moet je een parallelle Rush Hour solver maken. Je programma moet
niet alleen de standaard 6x6-configuratie aan kunnen, maar ook rechthoeken van andere
formaten. Bij het zoeken van een oplossing moet je bijhouden welke posities in de puzzel
je al hebt bezocht, om herhaling van zetten te voorkomen.
Uitvoer
Er zijn twee uitvoermodi:
• Telmodus: Geef het aantal stappen dat minimaal nodig is om de puzzel op te lossen.
Indien de puzzel niet oplosbaar is wordt -1 gegeven.
• Oplosmodus: Geef als antwoord een mogelijke kortste oplossing door middel van
een stap voor stap beschrijving. Elke stap wordt in de uitvoer gescheiden door een
komma en bestaat uit 3 karakters: (1) het karakter van de auto, (2) de richting van
de stap: u, d, l of r voor respectievelijk up, down, left en right, (3) het aantal vakjes
dat de auto verschuift in die richting. Als er geen oplossing voor de puzzel is wordt
“Geen oplossing gevonden” als uitvoer gegeven.
Een auto meer dan 1 hokje verplaatsen wordt ook gerekend als 1 stap. Let er op dat
je tijdens de Telmodus geen tijd en geheugen besteedt aan het onnodig bijhouden van de
bijbehorende oplossing.
1
Versie: 4 november 2014.
1
Het doel van het spel is om je eigen auto te bevrijden. Voor deze opdracht zal je eigen
auto altijd aangeduid worden met de letter x. Omdat we met variabele borden werken
wordt bij de invoer de targetspace gedefini¨eerd (zie Invoer). Dit zijn de coordinaten van
het vakje, geteld vanuit een 0-based grid, waar de linker bovenhoek van onze auto zich
moet bevinden om de puzzel als opgelost te beschouwen. Het targetvak ligt altijd binnen
het bord.
Invoer
De invoer begint met 4 regels met daarop:
• Een integer u, de uitvoermodus: 0 voor Telmodus, 1 voor Oplosmodus.
• Een integer w gevolgd door een spatie en een integer h, de breedte en hoogte van
het bord. Hierbij geldt dat zowel w als h positief en kleiner dan 120 zijn.
• Een integer x gevolgd door een spatie en een integer y, de coordinaten van het
targetvakje.
• Een integer s, die alleen wordt gebruikt indien je de optionele extra A* implementeert.
Anders kun je deze integer negeren. s geeft het gebruik van de heuristiek aan: 0
indien de heuristiek niet gebruikt mag worden, 1 indien wel.
Hierna volgen h regels van w karakters per stuk die de beginpositie van het bord
voorstellen. Een ’.’ geeft een leeg vakje aan, de ’x’ geeft de te bevrijden auto aan. De
overige auto’s worden voorgesteld met andere lowercase karakters. Alle auto’s zijn minstens
2 vakjes lang, zijn 1-dimensionaal (en staan dus altijd horizontaal of verticaal) en iedere
auto heeft een uniek karakter (er zijn dus nooit meer dan 26 auto’s).
Nog wat extra tips:
• De karakters zijn alleen ter identificatie van de auto’s en hebben (behalve ’x’) verder
geen betekenis.
• Ook je eigen auto kan groter zijn dan 2 vakjes.
• Je eigen auto kan ook verticaal staan.
Details
Gebruik van Threads/Tasks/etc...
Bij deze opdracht heb je iets meer vrijheid. Je mag alle2 ingebouwde functionaliteit
van C# gebruiken, dus ook alles uit bijvoorbeeld System.Collections.Concurrent en
2
met uizondering van System.Solvers.Concurrent.RushHour.
2
System.Threading.Parallel. Verras ons met hoe goed je de functionaliteit van C# in je
voordeel kan gebruiken!
In tegenstelling tot bij opdracht 1, is het aantal threads/tasks geen onderdeel van
de invoer! Het is de bedoeling dat je programma zelf besluit wat een redelijk aantal
is, bijvoorbeeld door te kijken naar Environment.ProcessorCount. Nog mooier3 is om
Parallel.For of Parallel.ForEach te gebruiken of een ThreadPool te gebruiken. Deze
methoden verdelen vanzelf het werk over een aantal threads, en het aantal threads wordt
door C# constant aangepast om zo goed mogelijke prestaties te behalen.
Representatie
Om je programma zo snel mogelijk te laten zoeken, moet je een goede representatie hebben
van posities. De manier waarop het in de invoer wordt gegeven (met strings) is voor intern
gebruik niet erg goed omdat het veel ruimte gebruikt en string-operaties erg langzaam zijn.
Een goede representatie is om een array te maken met integers4 , voor iedere auto in
het spelbord 1 integer. De integer geeft dan aan hoeveel posities de auto is verschoven ten
opzichte van de rand van het bord. Je hebt ook nog wat extra informatie nodig (zoals in
welke rij/kolom een auto staat, hoe lang hij is en of hij horizontaal/vertikaal is) maar dit
hoef je niet bij de representatie van de positie op te slaan (want het is altijd hetzelfde).
Oplossing opslaan In de oplosmodus is het nodig om de oplossing op te slaan. Je
kunt bij iedere positie een string bijhouden die de oplossing om bij die positie te komen
op slaat, maar dit is niet erg effici¨ent. Beter is het om een soort linked list te bouwen,
waarbij iedere positie een pointer heeft naar de positie die voor hem zit. Zo kun je door
vanaf de oplossingspositie deze pointers terug naar de beginpositie te volgen de oplossing
reconstrueren.
Algoritme
Een algoritme dat je kunt gebruiken om Rush Hour op te lossen, heet Breadth-First
Search. Het idee is, dat je begint met de beginpositie (diepte 0) en dat je vanuit hier
een lijst genereert van alle mogelijke volgende posities die je door het doen van 1 zet kunt
verkrijgen (diepte 1). Vanuit deze lijst bouw je weer een lijst op van alle mogelijke posities
die je in 2 zetten kunt bereiken (diepte 2). Herhaal dit proced´e totdat je de oplossing hebt
gevonden. Merk op dat het niet nodig is, om de lijsten met posities te behouden: je kunt
op diepte (n + 2) de lijst van diepte n weggooien om geheugen te besparen.
3
Dit levert dus ook meer punten op.
Tip: een integer kan 232 verschillende waarden opslaan, er zijn per auto maximaal 120 posities. Kies
voor maximale effici¨entie dus een ander numeriek datatype!
4
3
Taboo List
Breadth-First Search heeft een groot nadeel, het kan rondjes lopen: de beginpositie levert
een lijst op van posities op diepte 1, maar als je niet op let bevat de lijst van posities op
diepte 2 ook weer de beginpositie - en de lijst van posities op diepte 3 bevat ook weer alle
diepte 1-posities! Om dit te voorkomen moet je een Taboo List5 bouwen: een lijst van
posities die je al hebt gezien. Bij het ontdekken van een positie zet je deze in de taboo list,
en posities die al in de taboo list staan bekijk je niet nog eens.
Om dit snel genoeg te krijgen, kun je gebruik maken van de ConcurrentDictionaryklasse. Je moet dan wel een goede hashfunctie defini¨eren voor je posities. Je kunt extra
punten verdienen door niet de ConcurrentDictionary te gebruiken, maar zelf een datastructuur te implementeren.
Je kunt bijvoorbeeld met behulp van de CompareExchange-methode de wacht-vrije Trie
bouwen. Een Trie (wikipedia) is een speciale datastructuur die vooral voor strings wordt
gebruikt, maar ook zeer geschikt is om Rush Hour-posities op te slaan.
Een TrieNode-object is een object met daarin een array van (nog meer) TrieNodes. Als
de eerste auto op het bord (bijvoorbeeld) 6 mogelijke posities heeft, is de wortel van de
Trie een TrieNode-object met een array van 6 TrieNodes. Het eerste element van deze
array komt overeen met dat de eerste auto op positie 1 staat, en de tweede met positie 2,
etc... De TrieNode-objecten in de array van de wortel geven dan de positie van de tweede
auto weer, etc... Als ik dus een bord heb met auto 1 op positie 3, auto 2 op positie 4 en
auto 3 op positie 2, dan bekijk ik Trie[3][4][2].
Omdat er heel veel mogelijke posities zijn (en lang niet alle posities zijn bereikbaar) is
het niet haalbaar om de Trie in het begin helemaal op te bouwen. In het begin zijn alle
TrieNode-objecten null, en die worden opgevuld als posities worden ontdekt. Als je op het
pad in de Trie naar jouw positie een null tegenkomt, betekent dat dat die positie er nog
niet in staat.
Optioneel: A* met Heuristiek
A* is een ander zoek-algoritme. Je kunt dit algoritme een heuristiek meegeven. De heuristiek maakt een schatting van hoe veel stappen een bepaalde positie van de oplossing af
staat zodat je gerichter kunt zoeken. Hierdoor kun je veel ingewikkelder Rush Hour-puzzels
oplossen.
Als je A* implementeert moet het mogelijk zijn om de heuristiek uit te schakelen (zie
Invoer). Zonder heuristiek gedraagt A* zich hetzelfde als BFS. Je hoeft daarom naast A*
niet ook BFS te implementeren.
Lees voor meer informatie het wikipedia-artikel over A*. Bedenk zelf een goede heuristiek.
Zonder dit onderdeel kun je een 10 halen, met het implementeren van A* kun je bonuspunten verdienen en eventuele fouten in andere onderdelen compenseren.
5
NB: Dit heeft niks met Tabu Search te maken
4
Tip: om A* te implementeren heb je een priority queue nodig. Gebruik in geen geval
SortedList, dit is veel te langzaam. Je kunt bijvoorbeeld een array A van lijsten maken,
waarbij een positie met afstandschatting d in de lijst A[d] wordt opgeslagen.
Verslag
Schrijf een kort (5-10 regels) verslag over je programma. Noem hier in welke datastructuren
je hebt gebruikt, en of de operaties hierop locking zijn.
In een ideale wereld zou een programma dat op n cores draait, n keer zo snel moeten
werken. In de praktijk lukt dit nooit, omdat er door bijvoorbeeld locking en communicatie
bottlenecks ontstaan waardoor dingen niet parallel kunnen. Noem in je verslag wat de
bottlenecks in jouw programma zijn, en wat je hebt gedaan om bottlenecks te vermijden.
Beoordeling
Voor dit practicum is weer een testprogramma beschikbaar, TomJudge3.exe. Wij gebruiken
dit programma ook bij de beoordeling, dus het is heel verstandig om zelf je programma
door TomJudge te laten checken.
Zet het bestand TomJudge3.exe in dezelfde map als de *.cs-bestanden van je project.
TomJudge zoekt vervolgens automatisch in de ./bin/debug-map naar de debug-versie
van je executable. Het is belangrijk dat je voordat je test met TomJudge eerst zorgt
dat de debug-versie van je project up-to-date is (gebruik F5 of F6 in Visual Studio). Je
kunt eventueel ook de locatie van je executable doorgeven als argument, voer dan in de
opdrachtprompt in: TomJudge3 "C:/Concurrency/Programma.exe".
NB: TomJudge werkt alleen op Windows. Het daarom is niet verplicht om TomJudge
te gebruiken maar voor het nakijken is het handig als je het bestand report.csv dat
TomJudge aanmaakt ook inlevert. Let er ook op dat TomJudge op verschillende computers
andere beoordeingen kan geven, het is voor ons immers niet te doen om het op al jullie
computers uit te proberen. TomJudge geeft alleen een indicatie en is bedoeld om te helpen,
maar we gaan bij het nakijken er van uit hoe je programma op onze computer wordt
beoordeeld.
Extra informatie
Sommige van de testcases (met name hard-1,2,3 en 4) zijn erg lastig. Hard-1,2 en 3 kunnen
met BFS opgelost worden. Hard-4 zal je alleen lukken als je A* met een goede heuristiek
gebruikt. Het is niet erg als je hard-3 niet haalt. Het is mooi als dat wel lukt, maar het is
geen verplichting.
TomJudge test alleen of je programma correct werkt, maar kan niet zien hoe mooi het
is geschreven en welke datastructuren je gebruikt. TomJudge kan ook je verslag niet lezen.
Anders dan bij de eerste opdrachten zal de beoordeling iets meer naar de code kijken en
5
minder naar de testresultaten (alhoewel je als alle tests correct zijn nog steeds een mooi
cijfer kunt verwachten).
Voorbeelden
Hier volgen enkele voorbeelden van invoer en bijbehorende uitvoer. Je kunt ze vinden op
de praktikumpagina, waarbij voorbeeld VVV bestaat uit bestanden VVV.in en VVV.uit.
Voorbeeld st:
1
bd1, cl1, pu3, fr1, ku1, hr4, dd1, kd1,
6 6
fl1, pd1, cr1, el1, od3, bu1, xr3, ou3,
4 2
er1, du3, el1, od3, ar1, du1, xl3, ou1,
0
bd1, cl1, pu1, fr1, ku1, hl4, kd1, fl1,
aaobcc
pd3, cr1, bu1, od1, xr4
..ob..
xxo...
deeffp
d..k.p
hh.k.p
Voorbeeld drie: Deze kan in drie stappen.
1
ad3, bd2, xr4
6 6
4 2
0
......
..a...
xxa.b.
....b.
......
......
Voorbeeld vol: Oei die staat behoorlijk vol.
1
xl1, bd2, ar1, eu1, xl1, hu1, jl2, dd2,
6 6
cd2, fr2, ar2, hu2, xr1, gr1, ed4, xl1,
4 2
gl1, hd2, al2, du2, fl3, bu1, cu2, hu1,
0
gr4, jr2, bd2, hd2, fr2, xr2, eu4, iu3,
aaabcd
kl2, bd1, hd1, gl4, cd1, ar1, iu1, xl2,
effbcd
hu2, bu2, jl4, ll2, cd2, bd1, hd1, dd3,
e.xxcd
xr4
ggh...
.ih.jj
.ikkll
Voorbeeld fifty: Fifty shades of sweat.
6
1
6 6
4 2
0
..cddd
a.ce..
axxe..
bbryyi
.gruui
.gtt.i
Voorbeeld qwerty:
1
6 6
4 2
0
..qwwe
..qr.e
xxqr.e
tiii..
tuuop.
yy.op.
Voorbeeld rondje: Autodraaikolkje.
1
12 6
10 2
0
..cddd...q..
a.ce.....q..
axxe.....q..
bbryyi......
.gruui......
.gtt.i...zz.
Voorbeeld kannie: Deze kan echt niet.
1
12 2
10 0
0
.xx......q..
.........q..
au1,
yr1,
dl1,
dr1,
yl1,
cd1,
cu1,
xl1,
ed3,
iu1,
cu1,
id1,
dl1,
xr4
cd1,
yl2,
yr2,
xl3,
dr1,
iu1,
dl2,
id1,
br2,
cd2,
cu2,
yr1,
iu3,
dr2,
gu4,
dl1,
ru2,
ed3,
ur1,
cu1,
bl2,
iu1,
tl4,
yl2,
tr2,
xr3,
yl1,
yr1,
ul4,
id3,
rd1,
cd1,
id1,
eu3,
rd2,
dr1,
ed1,
ur3,
qd3,
ru1,
qd3,
il1,
wr1,
od2,
xr1,
ou2,
wl2,
ed3,
ru1,
rd1,
tu3,
ul4,
ru1,
xr1
pu3,
wl1,
xl1,
od2,
pu1,
yr1,
eu1,
qu3,
rd1,
xr3,
td1,
ir3,
il3,
wl1,
td1,
il1,
tu1,
ed1,
eu1,
wl1,
ou2,
yl1,
wr1,
ir3,
qu3,
zr1, qd3, dr6, eu1, xr9
Geen oplossing gevonden
7

Download Report