Een algoritmepuzzel voor het weekend

 
19 maart 2010

Stel: je opdrachtgever heeft een apparaat dat filmpjes afspeelt. Je hebt ervoor gezorgd dat de filmpjes worden afgespeeld op volgorde van een XML, waarin staat welk filmpje er wanneer moet worden gestart:

<playlist>
 <item id="1">
  <start_time>2010-03-18 0900</start_time>
  <end_time></end_time>
 </item>
 <item id="2">
  <start_time>2010-03-19 0900</start_time>
  <end_time>2010-03-19 1000</end_time>
 </item>
 <item id="3">
  <start_time>2010-03-19 1015</start_time>
  <end_time>2010-03-19 1115</end_time>
 </item>
 <item id="4">
  <start_time>2010-03-19 1100</start_time>
  <end_time></end_time>
 </item>
</playlist>

Regels zijn hierbij: eindtijd (<end_time/>) geldt alleen als er niet een ander filmpje wordt gestart voor de betreffende eindtijd. Als er op het tijdstip van de eindtijd geen filmpjes meer zijn om te spelen, dan blijft het filmpje spelen totdat er (ooit) een ander filmpje wordt gestart. Een item hoeft geen eindtijd te hebben.

Volgens bovenstaande XML zal de speler op 18 maart om 9 uur beginnen met item 1. Op 19 maart om 9 uur start item 2. Om 10 uur wil item 2 stoppen, dus begint item 1 weer te spelen. Om 10:15 begint item 3. Alhoewel item 3 pas wil eindigen om 11:15, begint item 4 om 11 uur. Item 4 blijft vervolgens net zolang doorspelen totdat er een nieuw item wordt toegevoegd of de player crasht. Whichever comes first.

Maar nu het probleem.

De opdrachtgever wil graag per dag zien wat er te spelen valt. Het overzicht is simpel: toon alle items die vandaag starten. Denk je.

Maar de opdrachtgever wil ook weten welke items er op de gekozen dag spelen, die eerder waren gestart. Zelfs items die eerder zijn gestart, maar op de gekozen dag niet te zien zijn, maar mogelijk in de toekomst nog wel moeten worden getoond.

De opdracht voor deze puzzel luidt: schrijf een methode die een juist overzicht maakt op basis van de beschreven regels voor het afspelen en de wensen van de opdrachtgever. Het overzicht moet kloppen voor elke willekeurige (geldige) playlist die wordt aangedragen.

Goed weekend!

UPDATE: voorbeeld van een playlist


Werken met ?
Kijk dan bij onze mogelijkheden voor starters en/of ervaren IT'ers.


Categorieën: Development, Professionele vaardigheden, Overige talen en platformen

Tags: ,


Reacties (19)

  • Matthijs schreef:

    Oke na even denken zou dit hem dan moeten zijn:

    public LijstFilmpjes GetFilmpjesForDate(Filmpjes,Date)
    {
    LijstFilmpjes mogelijkeFilmpjes = new LijstFilmpjes();
    List starttijden = new List();
    List eindtijden = new List();

    //Eerst alle filmpjes die vandaag starten vinden
    //ook degene zonder eindtijd want ze zullen toch starten dus ook spelen.

    foreach(filmpje in filmpjes)
    {
    if(filmpje.Starttijd.Valtbinnen(Date))
    {
    mogelijkeFilmpjes.Add(filmpje);
    starttijden.Add(filmpje.Starttijd);
    }

    if(filmpje.Eindtijd.Valtbinnen(Date)
    && ! mogelijkeFilmpjes.Contains(filmpje))
    {
    //voeg filmpjes toe die we nog niet hebben
    //maar wiens eindtijd wel binnen de dag valt
    //(vorige dag gestart)
    eindtijden.Add(filmpje.Eindtijd);
    }
    }

    foreach(eindtijd in eindtijden)
    {
    foreach(starttijd in starttijden)
    {
    //Eindtijd valt binnen de dag en wordt overlapt
    //maar niet helemaal zodat een deel
    //nog afgespeeld moet worden
    if(starttijd Date.BeginVanDedag)
    {
    mogelijkeFilmpjes.
    Add(Filmpjes.First(f=>f.eindtijd == eindtijd));
    }
    }
    }

    //Al wat ons nu nog rest is het zoeken naar gaten
    //en die opvullen met het vroegste filmpje zonder eindttijd

    //Eerst kijken of we al filmpjes hebben zonder eindtijd.
    //Als we er een hebben zullen alle gaten in de toekemst
    //door dit filmpje opgevuld worden.
    Date grens = null;

    foreach(filmpje f in mogelijkeFilmpjes)
    {
    if(f.Eindtijd == null)
    {
    if(grens == null)
    {
    grens = f.Begintijd;
    }
    else if(grens > f.Begintijd)
    {
    //We hebben een vroeger filmpje gebruik deze
    grens = f.Begintijd;
    }
    }
    }

    //Sorteer alle filmpjes op begintijd
    Filmpjes.SortByBegintijd();
    bool gat = false;

    //reverse loop
    for(var i = Filmpjes.Count-1;i>-1;i–)
    {
    var filmpje = Filmpjes[i];
    if(filmpje.Eindtijd != null)
    {
    if(filmpje.Begintijd <grens && filmpje.Eindtijd f.Begintijd < Date.Beginvandedag
    && f.Eindtijd == null);
    filmpjesVanGister.SortByBegintijd();
    var hetLaatstefilmpje = filmpjesVanGister.LastOrDefault();

    if(hetLaatsteFilmpje != null
    {
    mogelijkeFilmpjes.Add();
    }
    }

    return mogelijkefilmpjes;

    //Yaay we hebben ze
    }

    Geplaatst op 09 juni 2010 om 15:30 Permalink

  • Matthijs schreef:

    Lol ook best veel voor 1 methode :P

    Geplaatst op 07 juni 2010 om 15:50 Permalink

  • Matthijs schreef:

    Als ik het goed begrijp haal je alle items op vanaf een bepaalde datum en ga je gaten in de playlist zoeken.
    Die gaten zijn eigelijk timespans en die ga je opvullen met het eerste filmpje zonder eindttijd die eerder (lees vroeger) in de xml staat.

    Geplaatst op 07 juni 2010 om 15:49 Permalink

    • Simon Klees schreef:

      Zo ongeveer inderdaad. Maar vind dat filmpje maar eens. Voor mensen makkelijk te doen, maar in een for-loop toch een stuk lastiger.

      Geplaatst op 07 juni 2010 om 15:52 Permalink

      • Matthijs schreef:

        misschien in een lijst opslaan op datum. De goede oplossing is hier natuurlijk ook niet 1 methode, wel een interessante uitdaging voor een forloop.

        Geplaatst op 08 juni 2010 om 9:34 Permalink

        • Simon Klees schreef:

          Het lastige is dat je begin- en eindtijd tegelijk nodig hebt. Daar valt niet op te sorteren…

          Geplaatst op 08 juni 2010 om 9:40 Permalink

  • Simon Klees schreef:

    (Ik wilde reageren op het bericht van Johan van 29 maart om 9:55, maar daar zit geen reageerknop meer onder…)

    Het moeilijke is nog om te achterhalen welke van de items in de toekomst nog gaat spelen. Je wilt namelijk niet de items laten zien die na de gekozen dag starten. Wel de items die eerder zijn gestart en ooit nog opduiken.
    Het Excelvoorbeeld laat zien dat je alleen de items 2, 3, 5 en 7 wil zien in het dagoverzicht. 5 eigenlijk zelfs niet, als 7 om 0:00 uur start op die dag. (Beetje ongelukkig gekozen in het voorbeeld.) Maar wel als item 7 om 0:01 of later start.

    Geplaatst op 29 maart 2010 om 10:03 Permalink

  • Johan Scholten schreef:

    Ik neem aan dat ze op starttijd gesorteerd zijn. Doordat het de laatste is weet je dat ze hun hele periode afgespeeld worden en onderbreken ze alleen eerder toegevoegde items. Ik ben wel afgestapt van m’n idee van een lijst van begin/eindtijden, maakt de code wat ingewikkelder.

    function getPlayList(xmlItems, requestedTime):
    for(item in xmlItems)
    if (item.endTime().after(requestedTime))
    result.addItem(item.copy(), requestedTime)
    return result

    result class:
    function addItem(toAdd, requestedTime):
    for (item in items)
    if(item.endTime.beforeOrEqual(toAdd.startTime))
    continue
    if (item.endTime.after(toAdd.endTime))
    items.add(new Item(item, toAdd.endTime, item.endTime)
    item.endTime = toAdd.startTime
    if (!item.endTime.after(requestedTime)
    remove(item)
    items.add(toAdd)

    Geplaatst op 28 maart 2010 om 22:38 Permalink

    • Simon Klees schreef:

      Als ik het goed lees maak je hier een playlist, net als Boris, die de player vertelt wanneer welk item moet worden gespeeld. Maar vergeet niet dat de gekozen dag niet een tijdstip is.
      Jullie zijn wel op de goede weg. Je moet inderdaad echt eerst een hele playlist maken.

      Toch niet zo simpel als het leek he? :-)

      Geplaatst op 29 maart 2010 om 8:08 Permalink

      • johan scholten schreef:

        Nou, ik vat ‘m denk ik net wat anders op.

        Je kiest een tijdstip en bouwt een playlist op op basis van dat tijdstip.
        Nu is het gekozen tijdstip blijkbaar middernacht op een gekozen dag. Dit zou in de toekomst natuurlijk nog kunnen veranderen, dus we implementeren het nu zo.

        Op basis van de lijst kun je weergeven wat weergegeven moet worden, eerste item is wat op dat moment aan het spelen was, en daarna komt wat later afgespeeld gaat worden. Als je echt verschil wilt maken tussen deze dag en volgende dagen kan dat nog toegevoegd worden. Maar ik zou eerlijk gezegd dit resultaat dan gewoon splitsen op datum (bijvoorbeeld met een extra methode op de result-klasse. De items in de result-klasse zou trouwens in het ideale geval altijd gesorteerd moeten zijn op starttijd).

        Geplaatst op 29 maart 2010 om 9:55 Permalink

  • Boris van Woerkom schreef:

    ok de parser heeft wat code ingeslikt, iemand een idee hoe ik code-format?

    Geplaatst op 27 maart 2010 om 22:05 Permalink

    • Simon Klees schreef:

      Sorry voor de late reactie, maar ik weet ook niet hoe dat moet. Ik gebruik ‘gewoon’ &nbsp; …

      Geplaatst op 08 juni 2010 om 9:39 Permalink

  • Boris van Woerkom schreef:

    Alhoewel de geneste foreach iteratie niet zo mooi is werkt het wel:

    string id = null;
    foreach (var moment in aanUitMomenten)
    {
    var onthoudId = id;
    DateTime onthoudStartMoment = DateTime.MinValue;
    foreach (var tijdsPeriode in aanUitPerioden)
    {
    if (moment.datumtijd >= tijdsPeriode.start && moment.datumtijd onthoudStartMoment)
    {
    onthoudStartMoment = tijdsPeriode.start;
    id = tijdsPeriode.id;
    }
    }
    if (id != onthoudId)
    {
    Console.WriteLine(“start ” + id + ” op ” + moment.datumtijd);
    }
    }

    Geplaatst op 27 maart 2010 om 3:09 Permalink

    • Simon Klees schreef:

      Dit lijkt een methode te zijn om een playlist aan te maken vanaf een opgegeven dag. Goed werk tot zover, maar wat de klant wil zien is welk item er op de datumwisseling tussen gisteren en vandaag aan het spelen was, welke items er vandaag zullen starten en de eerdere items die ooit nog zullen gaan spelen.
      (Of zie ik iets over het hoofd en heb je dit wel ingebouwd?)

      En code formatten is een drama! Steeds als ik iets wijzig in de post moet ik opnieuw &nbsp; ’s invullen om de code enigszins gestructureerd te kunnen plaatsen. Ga ik hier eens even over praten.

      Geplaatst op 29 maart 2010 om 8:02 Permalink

  • Johan Scholten schreef:

    I know, ik probeerde even te porren of dit de hele opdracht was, hij voelt niet volledig aan (maar het is beter met het voorbeeld erbij). De xml is dus altijd gesorteerd op begintijd, en een dubbele entry op een begintijd is dus onmogelijk?
    Hmm, ik kom nu uit op 2 fors en 5 ifs, maar wel pseudocode.

    Geplaatst op 19 maart 2010 om 16:54 Permalink

    • Simon Klees schreef:

      De XML mag je sorteren zoals je wilt. Maar het loopen is echt niet zo simpel als het lijkt. Post die pseudo eens, als je wilt?

      Geplaatst op 22 maart 2010 om 9:17 Permalink

  • Simon Klees schreef:

    Wat jij zegt, Johan, komt uiteindelijk neer op: “Je moet doen wat er in de opdracht staat”. Dit bedoel ik echt niet lullig.

    Het probleem is echter veel lastiger dan het lijkt.

    Geplaatst op 19 maart 2010 om 13:29 Permalink

  • Simon Klees schreef:

    JS: “Je loopt over alle xml-entries heen, controleert voor elke waarde of hij ertoe doet (actief kan worden op de gekozen dag)” en “Bij dat toevoegen controleer je ook of hij anderen wegduwt (een 2e oneindige zal ervoor zorgen dat de eerste oneindige nooit meer afgespeeld zal worden, bij andere items kan het dat begin/eindtijd beperkt zijn, of zelfs gesplitst wordt).”

    Die controles, daar gaat het precies om. Schrijf die maar eens uit.

    Geplaatst op 19 maart 2010 om 12:52 Permalink

  • Johan Scholten schreef:

    Iets te summier, wat is het grote probleem?
    Je loopt over alle xml-entries heen, controleert voor elke waarde of hij ertoe doet (actief kan worden op de gekozen dag), en voegt hem toe aan een lijst als dat nodig is, samen met de tijd dat hij actief kan worden (begin/eindtijd, ws. handigste als een lijst van begin/eindtijden).
    Bij dat toevoegen controleer je ook of hij anderen wegduwt (een 2e oneindige zal ervoor zorgen dat de eerste oneindige nooit meer afgespeeld zal worden, bij andere items kan het dat begin/eindtijd beperkt zijn, of zelfs gesplitst wordt). Uiteindelijk hou je een lijst over met starttijd, eindtijd en item.

    Dat ‘mogelijk in de toekomst nog wel’ is dan een kleine aanpassing, door in plaats van de gekozen dag vanaf de gekozen dag te kiezen als criterium. Ik weet niet zeker of items die later beginnen dan de gekozen datum ook op die lijst moeten, maar beide varianten zijn dan makkelijk te maken.

    Geplaatst op 19 maart 2010 om 12:48 Permalink