Posts Tagged ‘square’

Programming Praxis – An Odd Way To Square

February 26, 2013

In today’s Programming Praxis exercise, our goal is to implement an algorithm to square a number using only addition and subtraction. Let’s get started, shall we?

import Data.Bits
import Data.List

First, the trivial O(n) algorithm. n^2 = n * n = sum (n times n)

square :: Integer -> Integer
square n = sum $ genericReplicate n n

Next, an O(log n) algorithm. Create a sequence in which each element consists of the following values: an incrementing integer i, 2^i and n*2^i. Filter out all elements for which the ith bit of n is 0. Sum the n*2^i terms.

square2 :: Integer -> Integer
square2 n = sum [a | (i,a) <- unfoldr (\(i,p,a) -> if p <= n then
    Just ((i,a), (i+1,p+p,a+a)) else Nothing) (0,1,n), testBit n i]

Some tests to see if everything is working properly:

main :: IO ()
main = do print $ map square  [0..10] == map (^2) [0..10]
          print $ map square2 [0..10] == map (^2) [0..10]
          print $ square (2^20) == 2^40
          print $ square2 (2^1000) == 2^2000

Programming Praxis – Four Points Determine A Square

January 2, 2013

In today’s Programming Praxis exercise, our goal is to determine whether four given points in a 2D plane make up a square. Let’s get started, shall we?

AnĀ  import:

import Data.List

The provided solution calculates the squares distances between the first and the three other points and considers the points a square when the smallest two are equal and the largest is the sum of the two smallest, i.e. a2 + b2 = c2. This solution is incorrect, however. If we take the points (0, 0), (1, 0), (0, 1) and (-1, -1), both conditions are satisfied despite the fact that the four points do not form a square. To handle this case correctly, we can use the same basic approach, albeit expanded a bit. Instead of just three distances, we calculate the distances between all six pairs. Of these six, the four smallest ones should be equal, as should the two larger ones. Pythagoras’ theorem can remain the same.

isSquare :: (Num a, Ord a) => (a, a) -> (a, a) -> (a, a) -> (a, a) -> Bool
isSquare p q r s = and [a == b, b == c, c == d, e == f, a + b == e] where
    [a,b,c,d,e,f] = sort [l | (h:t) <- tails [p,q,r,s], l <- map (dist h) t]
    dist (x1,y1) (x2,y2) = (x2-x1)^2 + (y2-y1)^2

Testing reveals that this version handles the old test cases correctly, as well as the example described above.

main :: IO ()
main = do print $ isSquare (0,0) (0,1) (1,1) (1,0)
          print $ isSquare (0,0) (2,1) (3,-1) (1, -2)
          print $ isSquare (0,0) (1,1) (0,1) (1,0)
          print . not $ isSquare (0,0) (0,2) (3,2) (3,0)
          print . not $ isSquare (0,0) (3,4) (8,4) (5,0)
          print . not $ isSquare (0,0) (0,0) (1,1) (0,0)
          print . not $ isSquare (0,0) (0,0) (1,0) (0,1)
          print . not $ isSquare (0,0) (1,0) (0,1) (-1,-1)

Programming Praxis – Squaring The Bishop

May 3, 2011

In today’s Programming Praxis exercise, our goal is to write a program that can create word squares. Let’s get started, shall we?

Some imports:

import qualified Data.ByteString.Char8 as B
import qualified Data.List.Key as K
import qualified Data.Map as M
import qualified Data.Trie as T

First we need to load the words into a practical data structure. The obvious one here is a trie. Rather than one big trie for the whole dictionary, we make group the words by length, making a trie for each different length.

loadWords :: IO (M.Map Int (T.Trie Int))
loadWords = fmap (M.fromList . map (\(w:ws) -> (snd w, T.fromList (w:ws))) .
                  K.group snd . K.sort snd . map (\w -> (w, B.length w)) .
                  B.words) $ B.readFile "words.txt"

Next, we need a function to find all the possible words of the correct length given a prefix.

findWords :: Int -> String -> M.Map Int (T.Trie a) -> [B.ByteString]
findWords l prefix = T.keys . T.submap (B.pack prefix) . (M.! l)

Finally, constructing the square is a matter recursively finding all the possible next words and keeping only the combinations that result in a full square.

square :: String -> M.Map Int (T.Trie a) -> [[B.ByteString]]
square word ds = f 1 [B.pack word] where
    f n ws = if n == length word then [ws] else 
             (\w -> f (n + 1) (ws ++ [w])) =<<
             findWords (length word) (map (`B.index` n) ws) ds

Some tests to see if everything is working properly:

main :: IO ()
main = do print . square "bonsai" =<< loadWords
          print . (== 122) . length . square "bishop" =<< loadWords

Looks like it. Interestingly, the word bonsai only has a single word square:

bonsai
osiers
nitril
serosa
arisen
island