Mastodon

renephoenix.de

Kommentar von Arne

Komisch, wenn ich 10, 7, 4, 1, 8 und 1 addiere, komme ich auf 31 und nicht 33. 31 ist auch die Antwort meines Haskellprogrämmchens, zumindest ohne degenerierte Dreiecke, von denen es nach Zählweise meines Programms 23 gibt.

-- ANFANG
import Control.Monad (liftM2)

-- Teillisten einer Liste
-- Nicht in allen Haskell-Implementierungen vorhanden
subsequences :: [a] -> [[a]]
subsequences [] = [[]]
subsequences (x:l) =
  let s = subsequences l in map (x:) s ++ s

-- Knoten: 0 = links unten, dann gegen den Uhrzeigersinn bis 9. 10 = Mittelpunkt
vertices = [0..10]

-- Listen von jeweils mehr als 2 Punkten, die auf einer Geraden liegen
-- (Listen von je 2 Punkten würden nicht schaden, sind aber nicht notwendig)
colinear = [[0,1,2,3,4],[0,5,10],[0,7,8,9],[1,6,10],[2,7,10],[3,8,10],[4,5,6,7],[4,9,10]]

-- Alle Verbindungen zwischen je zwei Punkten, könnte man theoretisch auch aus \»colinear\« berechnen
edges = [(0,1),(0,2),(0,3),(0,4),(0,5),(0,7),(0,8),(0,9),(0,10),(1,2),(1,3),(1,4),(1,6),(1,10),(2,3),(2,4),(2,7),(2,10),(3,4),(3,8),(3,10),(4,5),(4,6),(4,7),(4,9),(4,10),(5,6),(5,7),(5,10),(6,7),(6,10),(7,8),(7,9),(7,10),(8,9),(8,10),(9,10)]

-- Kartesisches Produkt zweier Listen
cartesian :: [a] -> [b] -> [(a,b)]
cartesian = liftM2 (,)

-- Alle Dreiecke als aufsteigende Tripel, einschließlich degenerierter
-- Ein degeneriertes Dreieck ist eines mit Flächeninhalt 0, hier z.B. [0,2,4].
triangles_degen :: [(Int,Int,Int)]
triangles_degen =
  [ (a,b,c) | ((a,b),c) <- vertices `cartesian` vertices `cartesian` vertices,
              (a,b) `elem` edges, (b,c) `elem` edges, (a,c) `elem` edges ]

-- Alle nicht degenerierten Dreiecke
triangles =
  filter (\\(a,b,c) -> all (not . (\\l -> [a,b,c] `elem` subsequences l)) colinear)
         triangles_degen
-- ENDE

Ausgabe:
*Main> (length triangles, triangles)
(31,[(0,1,10),(0,2,7),(0,2,10),(0,3,8),(0,3,10),(0,4,5),(0,4,7),(0,4,9),(0,4,10),(0,5,7),(0,7,10),(0,8,10),(0,9,10),(1,2,10),(1,3,10),(1,4,6),(1,4,10),(2,3,10),(2,4,7),(2,4,10),(3,4,10),(4,5,10),(4,6,10),(4,7,9),(4,7,10),(5,6,10),(5,7,10),(6,7,10),(7,8,10),(7,9,10),(8,9,10)])