Dette indlæg er alene udtryk for skribentens egen holdning.

GOTO - programming with the stars (F#)

23. maj 2012 kl. 16:2813
Artiklen er ældre end 30 dage
Manglende links i teksten kan sandsynligvis findes i bunden af artiklen.

Anden session i dag under parolen "Programming with the stars" var F# og Mark Seesmann. Det viste sig, at "programming with the stars" var et spor, hvor "the stars" skulle løse det samme problem allesammen - hver med deres favoritsprog. Opgaven var i al sin enkelthed at tage et input til Minesweeper-programmet med placering af bomber i et 4x4 grid og give som output værdierne for de enkelte celler afhængigt af bombernes placering.

Input:

  1. . * . .
  2. * . . .
  3. . . . .
  4. . . * .

Output:

  1. 2 * 1 0
  2. * 2 1 0
  3. 1 2 1 1
  4. 0 1 * 1

Dette var dermed også opgaven for den tidligere session med Java.

Artiklen fortsætter efter annoncen

Mark startede med at spørge om, hvor mange der kendte til F#. Et par tøvende hænder viste sig rundt omkring i lokalet. Derfor spurgte han hvor mange, der var kommet for at få en introduktion af sproget og lære mere om det. Stort set samtlige rakte hånden op. Desværre blev dette ikke ført til dørs, for niveauet var i hvert fald for mig alt for højt til at jeg kunne lære noget - udover at få inspiration til at kigge nærmere på det. Marks "sidekick" var nemlig ikke en "menig" tilhører i lokalet - det var søreme en F#-ekspert, der i øvrigt stod for en F#-usergroup i London. Det skal siges at Mark forsøgte bravt at holde partneren i ørene og løbende forklare de syrede constructs han brugte - men det var lidt svært for ham.

Anyways.

Jeg skal huske at sige, at Mark og partner havde snydt lidt og forberedt noget hjemmefra, men når det så er sagt, så blev jeg nærmest bjergtaget over forskellene i løsningerne. Nu er der jo mange måder at løse problemet på, men det var mit klare indtryk, at grunden til forskellene i løsningerne for det imperative sprog og for det funktionelle sprog skyldtes netop forskellene i sprog og ikke så meget forskellene i de personer, der kodede skidtet. Jeg skal være den første til at erkende, at den imperative løsning nok havde bevæget sig ud af en uheldig, kompleks tangent, men det var tydeligt for mig, at dette spor skulle illustrere tankerne om "right tool for the job". For hvis det eneste værktøj man har i kassen er et imperativt, OO-sprog, så bliver måske løsningerne også derefter. Den imperative løsning endte hurtigt med et sandt virvar af klasser, enums og lignende, hvorimod den funktionsorienterede løsning fokuserede på data og udregningerne af det og ikke meget mere. Den samlede funktionsorientede løsning var vel på 20 liniers kode, hvorimod den imperative brugte mindst det samme alene på klasseerklæringer og lignende.

Som sagt var det for mig en inspiration til at kigge meget nærmere på F#, også er det jo heldigt, at Marks sidekick fortalte os om et website han havde lavet, der hedder www.tryfsharp.org . Denne URI er hermed poppet op på toppen af min "Read it later"-kø .

Artiklen fortsætter efter annoncen

Opdateret: Marks kode findes nu på https://gist.github.com/2776707

  1. let input = "**..
  2. ....
  3. .*..
  4. ...."
  5.  
  6. let compute (board : string) =
  7. let board = board.Split([| "\n" |], System.StringSplitOptions.RemoveEmptyEntries)
  8. let count (x, y) =
  9.  
  10. [-1, -1; 0, -1; 1, -1;
  11. -1, 0; 1, 0;
  12. -1, 1; 0, 1; 1, 1]
  13. |> List.map (fun (x', y') -> x + x', y + y')
  14. |> List.filter (fun (x, y) -> x >= 0 && x < board.[0].Length && y >= 0 && y < board.Length)
  15. |> List.sumBy (fun (x, y) ->
  16. if board.[y].[x] = '*'
  17. then 1
  18. else 0
  19. )
  20.  
  21. board
  22. |> Array.mapi (fun y line ->
  23. line.ToCharArray() |> Array.mapi (fun x c ->
  24. match c with
  25. | '*' -> '*'
  26. | '.' -> '0' + char (count(x, y))
  27. | _ -> invalidArg "c" "Boo hiss!"
  28. )
  29. )
  30. |> Array.map (fun chars -> System.String(chars))
  31. |> Array.reduce (sprintf "%s\n%s")
13 kommentarer.  Hop til debatten
Denne artikel er gratis...

...men det er dyrt at lave god journalistik. Derfor beder vi dig overveje at tegne abonnement på Version2.

Digitaliseringen buldrer derudaf, og it-folkene tegner fremtidens Danmark. Derfor er det vigtigere end nogensinde med et kvalificeret bud på, hvordan it bedst kan være med til at udvikle det danske samfund og erhvervsliv.

Og der har aldrig været mere akut brug for en kritisk vagthund, der råber op, når der tages forkerte it-beslutninger.

Den rolle har Version2 indtaget siden 2006 - og det bliver vi ved med.

Debatten
Log ind eller opret en bruger for at deltage i debatten.
settingsDebatindstillinger
13
29. maj 2012 kl. 11:28

Min søn Vitus lavede som 10-årig denne implementering i Phrogram..(højreklik, gem & installér.) Jeg skal forsøge at hive kildekoden ud af ham og lægge den op senere.

Mvh Morten, Version2.

11
26. maj 2012 kl. 10:34

  1. #include <stdio.h>
  2. #define L 4
  3.  
  4. char braet[L+2][L+2] = /* fylder 0'er omkring <em>/
  5. { /</em> meget nemmere at taelle <em>/
  6. {0,0,0,0,0,0},
  7. {0,0,1,0,0,0},
  8. {0,1,0,0,0,0},
  9. {0,0,0,0,0,0},
  10. {0,0,0,1,0,0},
  11. {0,0,0,0,0,0}
  12. };
  13.  
  14. char count(int x,int y)
  15. {
  16. int i,j,c=0;
  17.   if (braet[x+1][y+1])
  18.   return '</em>';
  19. for (i=-1;i<=1;i++)
  20.   for (j=-1;j<=1;j++)
  21.   c +=braet[x+i+1][y+j+1];
  22. return c +'0';
  23. }
  24.  
  25. int main(void)
  26. {
  27. int i,j;
  28.   for (i=0;i<L;i++)
  29.   {
  30.   for (j=0;j<L;j++)
  31.   printf("%c ",count(i,j));
  32.   printf("\n");
  33.   }
  34. }

12
27. maj 2012 kl. 11:50

C programmet snyder :-). Du skal starte fra char* braet = "**..\n....\n.*..\n...."; ligesom de andre programmer og den der define er også lidt snyd.

Jeg har altid fundet strengbehandling i C meget klodset og besværligt.

10
24. maj 2012 kl. 17:43

Det fylder som et ondt år, men til gengæld tror jeg, at jeg hurtigt kan forstå den, hvis jeg skulle kigge på den igen om et halvt år. :)

  1. object MineSweeper {
  2. def main(args: Array[String]) {
  3. val input =
  4. """. * . .
  5. |* . . .
  6. |. . . .
  7. |. . * .""".stripMargin
  8.  
  9. val grid = fromInput(input)
  10. println(toOutput(grid.head.size, calculate(grid)))
  11. }
  12.  
  13. def fromInput(input: String) =
  14. input.split("\n") map {<em>.split(" ")}
  15.  
  16. def calculate(grid: Array[Array[String]]) = {
  17. val squaresWithPos = indexed(grid)
  18. val mines = minePositions(squaresWithPos)
  19.  
  20. squaresWithPos map {
  21. case ("<em>", _) => "</em>"
  22. case (".", pos) =>
  23. numberOfAdjacentMines(pos, mines).toString
  24. }
  25. }
  26.  
  27. def indexed(grid: Array[Array[String]]) = for {
  28. (row, i) <- (grid map {</em>.zipWithIndex}).zipWithIndex
  29. (square, j) <- row
  30. } yield (square, (i, j))
  31.  
  32. def minePositions(squaresWithPos: Array[(String, (Int, Int))]) =
  33. squaresWithPos collect {case ("*", pos) => pos}
  34.  
  35. def numberOfAdjacentMines(position: (Int, Int),
  36. mines: Array[(Int, Int)]) = {
  37. val adjacents = for {
  38. i <- -1 to 1
  39. j <- -1 to 1
  40. if (i, j) !=(0, 0)
  41. } yield (i + position._1, j + position.<em>2)
  42. (adjacents intersect mines).size
  43. }
  44.  
  45. def toOutput(squaresPerLine: Int, arr: Array[String]) =
  46. (arr.grouped(squaresPerLine) map {</em>.mkString(" ")}).mkString("\n")
  47. }

7
24. maj 2012 kl. 13:33

Min Scala udgave:

  1. case object Bombe
  2. case class Tom(bomber: Int)
  3. val input = for(linje <- io.Source.stdin.getLines.toArray) yield linje.collect {
  4. case '.' => Tom(0)
  5. case '<em>' => Bombe
  6. }.toArray
  7. val resultat = for((linje,y) <- input.zipWithIndex) yield
  8. for ((plads,x) <- linje.zipWithIndex) yield plads match {
  9. case Bombe => Bombe
  10. case Tom(<em>) =>
  11. val bomber = for(i <- x-1 to x+1; j <- y-1 to y+1;
  12. række <- input.lift(j)) yield række.lift(i)
  13. Tom(bomber.count(</em> == Some(Bombe)))
  14. }
  15. println(resultat.map(_.map{case Bombe => "</em>"; case Tom(n) => n.toString}.
  16. mkString(" ")).mkString("\n"))

9
24. maj 2012 kl. 15:09

En udgave der er lidt mere ækvivalent med de andre:

  1. val input = "**..\n....\n.<em>..\n....".split("\n")
  2. val res = for(y <- 0 to input.length-1; linje=input(y)) yield
  3. for (x <- 0 to linje.length-1) yield linje(x) match {
  4. case '</em>' => "<em>"
  5. case _ =>
  6. val bomber = for(i <- x-1 to x+1; j <- y-1 to y+1;
  7. række <- input.lift(j)) yield række.lift(i)
  8. bomber.count(_ == Some('</em>'))
  9. }
  10. println(res.map(_.mkString(" ")).mkString("\n"))

Nu har jeg ikke set Java versionen, men jeg sider lidt med en forestilling om at man har lavet en vild version med mangle klasser med mere, selvom man også i Java vil kunne implementere en algoritme i stil med ovenstående.

5
24. maj 2012 kl. 13:25

Det er et oplagt problem til enten J eller APL hvor ovenstående formentlig er en one-liner på en 4-5 tastetryk :)

4
24. maj 2012 kl. 12:49

Nu kender jeg ikke noget til F# (endnu), men som jeg læser det, så er det ikke en matricen som sådan, men blot et array/liste (med længden 8) af par. Disse par er xy-koordinater på nabofelterne ift. parametrene x og y. Dvs. (-1, -1), (0, -1) ...

3
24. maj 2012 kl. 12:27

Jeg har puttet Marks F#-kode ind til sidst i eksemplet.

:o)

PS: Hvis nogen kan forklare mig idéen med den "magiske matrix" i linie 10-12, så vil det være ganske velkomment.

8
24. maj 2012 kl. 13:38

Hvis nogen kan forklare mig idéen med den "magiske matrix" i linie 10-12, så vil det være ganske velkomment.

Den indeholder offsets til nabofelter. Det er ikke egentlig en matrice, blot en lineær liste af koordinater, der er vist i 2D, for at anskueliggøre retningerne.

Jeg synes i øvrigt ikke, at løsningen er specielt elegant. Herunder er kode i SML (som ligner F#) for samme problem.

  1. val input = "**..\n....\n.<em>..\n...."
  2.  
  3. val lines = String.tokens Char.isSpace
  4. ("....\n"^input^"\n....")
  5.  
  6. val chars = map (fn s=>explode ("."^s^".")) lines
  7.  
  8. fun neighbours (a::(l as (b::c::<em>))) =
  9. neighbours1 a b c :: neighbours l
  10. | neighbours _ = []
  11.  
  12. and neighbours1 (a1 :: (l1 as (b1::c1::</em>)))
  13. (a2 :: (l2 as (b2::c2::<em>)))
  14. (a3 :: (l3 as (b3::c3::</em>))) =
  15. (if b2 = #"</em>" then #"<em>"
  16. else chr (ord #"0" +
  17. length
  18. (List.filter (fn c=> c = #"</em>")
  19. [a1,b1,c1,a2,c2,a3,b3,c3])))
  20. :: neighbours1 l1 l2 l3
  21. | neighbours1 _ _ _ = []
  22.  
  23. val solution =
  24. String.concat
  25. (map (fn l => (String.implode l)^"\n")
  26. (neighbours chars))

6
24. maj 2012 kl. 13:30

PS: Hvis nogen kan forklare mig idéen med den "magiske matrix" i linie 10-12, så vil det være ganske velkomment.

Koordinater. Ordinataksen er vendt.

1
24. maj 2012 kl. 11:20

Det burde ganske rigtigt ikke kræve mere end en snes linjer i et fornuftigt sprog. Men man kan ikke bruge problemet til at sammenligne sprog på andre kriterer end "løsning af små puslespilsagtige opgaver". For dette problem kræver ikke avancerede datastrukturer, modularisering, abstraktion, generisk programmering osv, som er vigtige for løsning af større programmeringsopgaver.

Dog kan simple problemer afsløre, om et sprog kræver urimeligt meget boiler plate for at løse små problemer. Noget kunne tyde på, at dette er tilfældet for Java.