Programmeringsglädje!

Programmeringsglädje!
juli 7, 2012 erik.lupander@squeed.com

Så här i semestertider kanske man borde koppla bort allt vad datorer, mjukvara och projekt heter och ägna sig åt annat. Men regniga dagar kommer ändå skaparlusten fram i mig. Då jag inte har särskilt mycket Ernst i mig vänder jag mig istället till den digitala domänen.

Härom kvällen lade svägerskan några olika patienser och frågade om jag kunde någon. Den enda jag kom att tänka på lärde jag mig redan som barn av min mor – livslång patiensentusiast – och det speciella med den patiensen är att den skall vara i stort sett omöjlig att få att gå ut. Jag vet inte vad den heter, men ska förklara de enkla reglerna nedan. Jag och svägerskan lade den några gånger var – och mycket riktigt var vi inte ens nära att få den att gå ut en endaste gång.

Patiensens regler är som sagt enkla. 52 kort och målet är att få samtliga kort i en enda hög. Man tar ett kort och lägger ut. Sedan drar man nästa kort och lägger till höger om det första., Om det är av samma färg eller siffra som kortet direkt till vänster, eller tre kort till vänster, får man lägga kortet på den högen. Om det inte matchar drar man ett nytt och lägger till höger osv. När man flyttar en hög så får man givetvis försöka matcha vidare eftersom den flyttade  högens översta kort kanske matchar något i sin nya position.

I brist på soligt väder gav jag det hela en bit tankeverksamhet och bestämde mig för att ta reda på hur många försök man egentligen behöver för att få patiensen att gå ut med hjälp av lite Javakodning på semesterdatorn med den konstiga tangentbordslayouten. Lyckligtvis fanns Eclipse i gammal version redan installerad, så förstärkt av en stor kopp kaffe och ett par timmar barnfritt skred jag till verket.

Uppgiften i sig är ganska banal för en utvecklare över nybörjarnivå och jag tror faktiskt uppgiften hade passat alldeles utmärkt som en introduktionsuppgift i en programmeringskurs. Men låt mig ändå redogöra för lösningen och utfallet i stora drag. WordPress är inte riktigt med mig så mina generics verkar försvinna och någon vettig kod-vy får jag heller inte till, så jag beklagar den bristande läsbarheten.

1. Representera kortleken och spelbrädet

Kortleken är en ArrayList<Card> där Card har en färgenum och en siffra 1-13. 52 kort skapas i en for-sats och blandas med Collections.shuffle(..)

for(int a = 0; a < 13; a++) {
    deck.add(new Card(CardType.CLUBS, a));
    deck.add(new Card(CardType.HEARTS, a));
    deck.add(new Card(CardType.SPADES, a));
    deck.add(new Card(CardType.DIAMONDS, a));
}

// Shuffle
Collections.shuffle(deck);

Spelbrädet är en Listdär Stack enbart innehåller en List. Man hade således kunnat skriva den som List>, vad som är tydligast kan säkert någon clean-code guru tala om för mig.

List deck = new ArrayList();
List stacks = new ArrayList();

2. Dra kort

Plocka översta kortet i leken genom deck.remove(0); och placera kortet i en ny CardStack.

Card card = deck.remove(0);
// Put card in new stack at the bottom
stacks.add(new Stack(card));

3. Försök lägga korten i högar enligt spelreglerna
Jag tittar efter varje förändring av spelbrädet (nytt kort eller flyttad hög) efter möjlighet att stapla högarna.

private void tryToStackCards() {
  for(int a = stacks.size() - 1; a > 0; a--){

    Card card1 = stacks.get(a).getCards().get(0);
    if(a-1 >= 0) {
      Card adjacent = stacks.get(a-1).getCards().get(0);
      if(canStack(card1, adjacent)) {
         // stack and recurse
         stack(a, a-1);
         tryToStackCards();
         break;
      }
   }
  if(a-3 >= 0) {
     Card twoAway = stacks.get(a-3).getCards().get(0);
     if(canStack(card1, twoAway)) {
        // stack and recurse
        stack(a, a-3);
        tryToStackCards();
        break;
     }
   }
}

4. Själva stackningen – att flytta över en hög till en annan är enkla operationer mha Collection API:t.

Stack from = stacks.get(fromIndex);
Stack to = stacks.get(toIndex);

to.getCards().addAll(0, from.getCards());
from.getCards().clear();
stacks.remove(fromIndex);

5. Kör programmet tills dess att patiensen ”går ut”

private void startRound() {
// Setup deck
setupDeck();

// Start drawing cards
drawCardFromDeck();

if(stacks.size() > 1) {
  tries++;
  resetGame();
  startRound();
} else {
  System.out.println("Succeeded after " + ++tries + " tries!");
  System.out.println("Average num of stacks: " + ((float) totalStacks/tries));
}

}

Utfall
Syftet med denna lilla semesterprogrammering var att ta reda på hur många gånger man egentligen behöver lägga denna oidentifierade patiens innan den går ut. Innan jag redovisar utfallet skall dock nämnas att mitt program inte har någon form av artificiell intelligens som försöker avgöra vilket stackningsalternativ som är det bästa i de fall man har valet att flytta antingen från flera ställen eller till flera ställen. (1 eller 3 steg åt vänster och/eller att man genom att flytta A->B får möjlighet att i nästa steg kanske flytta B->C). Kan mycket väl bli en utmaning att ta sig an en annan regnig semesterdag.

Utfallet då? Jag körde programmet 1000 ggr i rad och i genomsnitt behövde datorn lägga patiensen 1353 gånger med minimiantalet 8 gånger och maximiantalet 8865 gånger. Jag antar att utfallet är tämligen normalfördelat. Att lägga ca 1.353 miljoner omgångar tar ungefär 45 sekunder på den här datorn (MacBook Pro Core2Duo 2.4ghz).

Framtida utmaningar
* Förbättra prestandan genom flertrådning, något actor-ramverk etc.
* Förbättra prestandan genom effektivare kod, renare datastrukturer, bättre algoritmer.
* Förbättra utfallet genom mer avancerad ”AI” som likt en schackdator testar olika utfall innan den väljer vilken kortflytt som skall utföras när flera alternativ finns. Man kan också låta programmet känna till vilka kort som redan ligger på bordet och fatta beslut utifrån sannolikhet att en viss färg/siffra är på nästa kort.
* Implementera i annat programmeringsspråk. Kanske en ursäkt för att lära mig Scala, Groovy eller varför inte JRuby?

3 Kommentarer

  1. Fredrik Wendt 6 år sedan

    En tanke som slår mig är att man inte behöver hålla koll på vilka kort som ligger på bordet, förutom de översta. Istället för två dimensioner blir det bara en – hur många kort(högar) finns det och vilket kort ligger där/överst. Det blir mycket färre kort att flytta runt och hantera iaf.

    • Författare
      erik.lupander@squeed.com 6 år sedan

      Bra idé!

Pingbacks

  1. […] Post navigation ← Previous […]

Lämna ett svar

E-postadressen publiceras inte. Obligatoriska fält är märkta *

*

Denna webbplats använder Akismet för att minska skräppost. Lär dig hur din kommentardata bearbetas.