{-# LANGUAGE FlexibleContexts #-} {-# LANGUAGE MultiParamTypeClasses #-} ----------------------------------------------------------------------------- -- | -- Module : Diagrams.TwoD.Factorization -- Copyright : (c) 2012 Brent Yorgey -- License : BSD-style (see LICENSE) -- Maintainer : byorgey@cis.upenn.edu -- -- Factorization diagrams, as seen at -- <http://mathlesstraveled.com/2012/10/05/factorization-diagrams/> -- and -- <http://mathlesstraveled.com/2012/11/05/more-factorization-diagrams/> -- and on the cover of Hacker Monthly -- (<http://hackermonthly.com/issue-31.html>): visually represent the -- prime factorization of n by drawing n dots recursively grouped -- according to the factors. -- -- <<diagrams/src_Diagrams_TwoD_Factorization_grid100Big.svg#diagram=grid100Big&width=600>> -- ----------------------------------------------------------------------------- module Diagrams.TwoD.Factorization where import Data.Char (digitToInt) import Data.List.Split (chunksOf) import Data.Maybe (listToMaybe) import Diagrams.Prelude -- | @primeLayout@ takes a positive integer p (the idea is for it to -- be prime, though it doesn't really matter) and a diagram, and lays -- out p rotated copies of the diagram in a circular pattern. -- -- There is a special case for @p = 2@: if the given diagram is taller -- than it is wide, then the two copies will be placed beside each -- other; if wider then tall, they will be placed one above the -- other. -- -- The regular @p@-gon connecting the centers of the laid-out -- diagrams is also filled in with vertical bars of color -- representing the number @p@. In particular, there is one color -- for each decimal digit (the provided list should have length 10 -- and represents the digits 0-9), and the colors, read left to -- right, give the decimal expansion of @p@. -- -- > import Diagrams.TwoD.Factorization -- > plExample -- > = pad 1.1 . centerXY -- > . hsep 0.5 -- > . map (sized (mkWidth 1)) -- > $ [ primeLayout defaultColors 5 (circle 1 # fc black) -- > , primeLayout defaultColors 103 (square 1 # fc green # lw none) -- > , primeLayout (repeat white) 13 (circle 1 # lc orange) -- > ] -- -- <<diagrams/src_Diagrams_TwoD_Factorization_plExample.svg#diagram=plExample&width=400>> primeLayout :: (Renderable (Path V2 n) b, TypeableFloat n) => [Colour Double] -> Integer -> QDiagram b V2 n Any -> QDiagram b V2 n Any primeLayout _ 2 d | width d >= height d = (d === strutY (height d / 3) === d # reflectY) # centerY | otherwise = (d ||| strutX (width d / 3) ||| d) # centerX primeLayout colors p d = (mconcat $ map (\n -> d # translateY r # rotateBy (fromIntegral n/fromIntegral p)) [0..p-1] ) <> colorBars colors p poly where poly = polygon (with & polyType .~ PolyRegular (fromIntegral p) r & polyOrient .~ OrientH ) w = max (width d) (height d) r = w * c / sin (tau / (2 * fromIntegral p)) c = 0.75 -- | Draw vertical bars of color inside a polygon which represent the -- decimal expansion of @p@, using the provided list of colors to -- represent the digits 0-9. -- -- > import Diagrams.TwoD.Factorization -- > colorBarsEx = colorBars defaultColors 3526 (square 1) -- -- <<diagrams/src_Diagrams_TwoD_Factorization_colorBarsEx.svg#diagram=colorBarsEx&width=200>> colorBars :: (Renderable (Path V2 n) b, TypeableFloat n) => [Colour Double] -> Integer -> Path V2 n -> QDiagram b V2 n Any colorBars colors p poly | p <= 11 = stroke poly # fc (colors!!(fromIntegral p `mod` 10)) # lw none colorBars colors p poly = bars # clipBy poly where barColors = map ((colors!!) . digitToInt) (show p) barW = width poly / fromIntegral (length barColors) barH = height poly bars = (hcat $ map (\c -> rect barW barH # fc c # lc c) barColors) # centerX -- | A default set of digit colors, based very loosely on the color -- code for resistors (<http://en.wikipedia.org/wiki/Electronic_color_code>), -- lightened up a bit by blending with white. -- -- <<diagrams/src_Diagrams_TwoD_Factorization_showDefaultColors.svg#diagram=showDefaultColors&height=50>> defaultColors :: [Colour Double] defaultColors = map (blend 0.1 white) [black,red,orange,yellow,green,blue,gray,purple,white,brown] -- > import Diagrams.TwoD.Factorization -- > showDefaultColors = hcat $ zipWith showColor defaultColors [0..] -- > where -- > showColor c d = text (show d) <> square 1 # fc c # lw none -- | Create a centered factorization diagram from the given list of -- factors (intended to be primes, but again, any positive integers -- will do; note how the below example uses 6), by recursively -- folding according to 'primeLayout', with the 'defaultColors' and -- a base case of a black circle. -- -- > import Diagrams.TwoD.Factorization -- > factorDiagram'Ex = factorDiagram' [2,5,6] -- -- <<diagrams/src_Diagrams_TwoD_Factorization_factorDiagram'Ex.svg#diagram=factorDiagram'Ex&height=200>> factorDiagram' :: (Renderable (Path V2 n) b, TypeableFloat n) => [Integer] -> QDiagram b V2 n Any factorDiagram' = centerXY . foldr (primeLayout defaultColors) (circle 1 # fc black # lw none) -- | Create a default factorization diagram for the given integer, by -- factoring it and calling 'factorDiagram'' on its prime -- factorization (with the factors ordered from smallest to -- biggest). -- -- > import Diagrams.TwoD.Factorization -- > factorDiagramEx = factorDiagram 700 -- -- <<diagrams/src_Diagrams_TwoD_Factorization_factorDiagramEx.svg#diagram=factorDiagramEx&width=400>> factorDiagram :: (Renderable (Path V2 n) b, TypeableFloat n) => Integer -> QDiagram b V2 n Any factorDiagram = factorDiagram' . factors factors :: Integer -> [Integer] factors 1 = [] factors n = maybe [n] (\a -> a : factors (n `div` a)) mf where mf = listToMaybe $ filter (\x -> (n `mod` x) == 0) [2 .. n - 1] -- only need to go to @intSqrt n@ really -- | Place a diagram inside a square with the given side length, -- centering and scaling it to fit with a bit of padding. -- -- > import Diagrams.TwoD.Factorization -- > ensquareEx = ensquare 1 (circle 25) ||| ensquare 1 (factorDiagram 30) -- -- <<diagrams/src_Diagrams_TwoD_Factorization_ensquareEx.svg#diagram=ensquareEx&width=200>> ensquare :: (Renderable (Path V2 n) b, TypeableFloat n) => n -> QDiagram b V2 n Any -> QDiagram b V2 n Any ensquare n d = d # centerXY # sized (dims2D (0.8*n) (0.8*n)) <> square n -- | @fdGrid n@ creates a grid of factorization diagrams, given a list -- of lists of integers: the inner lists represent L-R rows, which -- are laid out from top to bottom. -- -- > import Diagrams.TwoD.Factorization -- > fdGridEx = fdGrid [[7,6,5],[4,19,200],[1,10,50]] -- -- <<diagrams/src_Diagrams_TwoD_Factorization_fdGridEx.svg#diagram=fdGridEx&width=200>> fdGrid :: (Renderable (Path V2 n) b, TypeableFloat n) => [[Integer]] -> QDiagram b V2 n Any fdGrid = vcat . map hcat . (map . map) (ensquare 1 . factorDiagram) -- | @fdGridList n@ creates a grid containing the factorization -- diagrams of all the numbers from @1@ to @n^2@, ordered left to -- right, top to bottom (like the grid seen on the cover of Hacker -- Monthly, <http://hackermonthly.com/issue-31.html>). -- -- > import Diagrams.TwoD.Factorization -- > grid100 = fdGridList 10 -- > grid100Big = grid100 -- -- <<diagrams/src_Diagrams_TwoD_Factorization_grid100.svg#diagram=grid100&width=400>> fdGridList :: (Renderable (Path V2 n) b, TypeableFloat n) => Integer -> QDiagram b V2 n Any fdGridList n = fdGrid . chunksOf (fromIntegral n) $ [1..n*n] -- | @fdTable n@ creates a \"multiplication table\" of factorization -- diagrams, with the diagrams for @1@ to @n@ along both the top row -- and left column, and the diagram for @m*n@ in row @m@ and column -- @n@. -- -- > import Diagrams.TwoD.Factorization -- > fdMultTableEx = fdMultTable 13 -- -- <<diagrams/src_Diagrams_TwoD_Factorization_fdMultTableEx.svg#diagram=fdMultTableEx&width=600>> fdMultTable :: (Renderable (Path V2 n) b, TypeableFloat n) => Integer -> QDiagram b V2 n Any fdMultTable n = fdGrid [ [r*c | c <- [1 .. n]] | r <- [1 .. n] ]