Vinnaren utsedd i Citerus programmeringsutmaning på Jfokus!

2011-02-16 — Tobias Hill — 43 kommentar(er)

Vi är glada över det översvallande intresset och härliga engagemanget som visats i vår programmeringstävling. Vi fick in totalt 109 enskilda bidrag i totalt 14 olika språk. Ungefär hälften av dessa passerade vår rättning som godkända bidrag.

Vissa bidrag var oerhört snabba, andra koncisa och alla unika på sitt sätt. Dels den stora mängden godkända bidrag men även varje enskilt bidrags snillrikhet har inte gjort juryns arbete lätt. Men det har varit värt varenda minut då det varit oerhört lärorikt.

Så, låt oss återvända till vad vi i uppgiftsformuleringen beskrev som goda egenskaper hos en lösning. Vi skrev:

Exempel på saker som vi på Citerus brukar uppskatta är "koncis kod som är lätt att läsa och förstå" samt "val av algoritmer och datastrukturer som ger rimlig prestanda för den uppgift som skall lösas".

I det extrema är oftast dessa egenskaper hos kod motstridiga. Exempelvis är det ofta svårt att göra en extremt snabb lösning som också är koncis och lätt att läsa. Så delvis kan man säga att den här tävlingen handlade om att balansera dessa egenskaper mot varandra. Mot bakgrund av det försökte juryn igår kväll ringa in vilken delmängd bidrag som vi tyckte både var tillräckligt koncisa och snabba men också lättlästa. Kvar blev ca 10 bidrag. Efter ytterligare mangling hade vi bara ett fåtal av dessa kvar och här började det bli riktigt svårt. Alla de kvarvarande bidragen hade en del mycket vackra egenskaper, men även små svagheter. Efter en slutlig omröstning stod det klart att vi alla var mest fascinerade av det bidrag som Carin Lidmar hade lämnat in. Algoritmiskt var Carins koncisa lösning ensam i sitt slag. Dessutom var det en av de snabbaste (men inte snabbast). Det som också gjorde oss både förundrade och väckte vårt intresse var att den varken använde sig av en memoizer eller någon form av pivotering men ändå lyckades vara riktigt snabb.

Så här ser Carins lösning ut:

public class CiterusChallenge {
  static String[] substrings = 
    {"TDD", "DDD", "DI", "DO", "OO", "UI", 
     "ANT", "CV", "IOC", "LOC", "SU", "VO"};

  public static void main(String[] args) {
    System.out.println(removeSubstringsToTheRight(
        "VOCDIITEIOCRUDOIANTOCSLOIOCVESTAIOCVOLIOCENTSU", 0));
  }

  public static String removeSubstringsToTheRight(String s, int start) {
    int minimum = s.length();
    String result = s;
    for (String substr : substrings) {
      int i = s.indexOf(substr);
      while (i >= 0) {
        if (i + substr.length() > start) {
          String newString = s.substring(0, i) + 
                s.substring(i + substr.length());
          newString = removeSubstringsToTheRight(newString, i);
          if (newString.length() < minimum) {
            minimum = newString.length();
            result = newString;
          }
        }
        i = s.indexOf(substr, i + 1);
      }
    }
    return result;
  }
}

Citerus kommer att återkomma inom kort med fler iakttagelser vi gjort under tävlingen.