Contents
Case: Urban Planning
- Straten leggen door een grid, waarbij de interconnectedness tussen alle grid points minimaal is (?)
Case: #Wares&Winkels
- Flink pak orders van 5 items or less
- Warehouse met stellages (grid)
- 1. Find de kortste route voor je robot pickers
- 2. size van de items?
- 3. Items opnieuw inrichten in stellages
- 4. stellages opnieuw plaatsen
Case: #onDroneDemand
Naar een idee van Jelle van Assema.
Drone delivery! De concurrentie is bij webwinkels en warenhuizen om te snijden, en om je als winkel een beetje te onderscheiden willen we razendsnelle bezorging. Dus laten we drones inzetten zoals Amazon dat hoopt te doen.De vraag is dan, hoe krijgen we zo snel mogelijk de bestellingen bij klanten d.m.v. onze drones?
Het idee voor de case is als volgt. Klanten plaatsten bestellingen. Alle bestellingen zijn dus bekend voor het roosteren begint. Een bestelling is een verzameling van één of meer pakketten die allemaal geleverd moeten worden voordat de bestelling voltooid is. Pakketten bevinden zich in warenhuizen. Warenhuizen zijn daarmee verzamelingen van pakketten, maar let op de voorraad kan ook opraken of niet aanwezig zijn. Drones kunnen één pakket tegelijk ophalen in een warenhuis en dit pakket vervolgens afleveren bij de klant. Dit alles vindt plaats op een grid van x bij y, met w warenhuizen, k klanten en o orders. Op elk plekje van het grid kan zich een klant bevinden of een warenhuis. Maarja, drones kunnen vliegen dus die doen niet aan Manhattan distance. Drones vliegen met de snelheid van één vakje per tijdseenheid, en dan is de tijd van x1,y1 naar x2,y2 gelijk aan ceil(((x1 - x2)**2 + (y1 - y2)**2)**(1/2)). Ofwel, Pythagoras naar boven afgerond. Het laden en ontladen van een drone kost geen tijd. Als de batterij op is, vervangen we deze door een reserve. Een drone kan altijd vliegen.
Nu is de taak, hoe krijgen we bestellingen zo snel mogelijk afgerond. Wat dit precies betekent is nog open. Zijn we geïnteresseerd in de laatste bestelling (zwakste schakel bepaalt score), of is elke afgeronde bestelling punten waard t.o.v. de tijd dat deze is afgerond?
Dan zijn alle parameters nog te bepalen: Hoeveel klanten met hoeveel bestellingen en waar? Hoeveel drones hebben we? Hoeveel warenhuizen met hoeveel pakketten en waar?
Hoe kunnen we het in deze case nou lastig, makkelijk of onmogelijk maken om een goede score te scoren? Terwijl we het toch toegankelijk houden voor de studenten.
ps. Dit naar aanleiding van Google HashCode 2015
Case: #JijTube
Google HashCode 2017
Case: smart grid
Deze case is inmiddels gerealiseerd. Zie SmartGrid.
Case: pathfinding in adventure games (pittig!)
Gegeven kaarten 20x20, 30x30 (je kunt 3 watertjes wegtoveren), 40x40 (je kunt 5 tiles modifyen, er zijn teleports op de map.
1) Maak een algoritme dat een pad vindt tussen een ingegeven x en y op kaart 1
2) Maak een algoritme dat een pad vindt tussen een ingegeven x en y op kaart 2
3) Maak een algoritme dat een pad vindt tussen een ingegeven x en y op kaart 3
4) Iets met verschillende units hebben verschillende snelheid op verschillend terrein? Ruiters gaan snel, maar niet in de bergen of zo? Warmachines kunnen niet door de swamps?
5) Avoiding monsters?
6) Run-time? vijandige heroes moven randomly rond?
Case: RadioIostopen
Nog heel prematuur.