Solving Some Project Euler Problems in Haskell

Here are a few solutions to Project Euler problems done in Haskell.  All of these were entered in gchi interactively.  As much as possible I try to keep them as one-liners.

The ">" indicates the beginning of a line at the ghci command line.

Starting with problem 7, this ideal could not be kept since it was becoming unmanageable.  With that problem I started to use modules.  The maintenance of that module is documented below.

One final note; this post is an experiment at producing fewer posts but keeping them alive with data and updates rather than flood with posts.  Quality over quantity seems to be my new mantra.  A good long post completed over the course of a few months.

Problem 1:

This problem was relatively straight-forward.  It's actually a nice one-liner!

> sum $ filter (\x -> x `mod` 3 == 0 || x `mod` 5 == 0) [1..999]

Problem 2:

First, create a fibonacci sequence list.  Make sure it is tail recursive for performance - hence why the first two elements are not included in the recursive list.  The filter and takeWhile should be interchangeable.

> let fib x y = (x+y):(fib y (x+y))> sum $ filter (\x -> x `mod` 2 == 0) $ takeWhile (<= 4000000) ([1,2] ++ fib 1 2)

Problem 3:

A much more interesting problem.  Note, the maximum value of your prime number will be the square root of the target number.

You do not need to enumerate all primes.  Actually, this would be slower as the sieve would take more time filtering numbers.  To crack the number, we first find all integers that divide it.  Then, of those integers, to determine which are prime, we see which divide each other.

To see why this works, consider an integer and all the integers that divide it.  If an integer were not prime, it could be decomposed into prime numbers.  Those prime numbers also divide the original number.

First identifying the dividing the integers being faster is only tractable for relatively small numbers.

"divs" finds all the integers that divide the given value.

"noDivs" is true if there is a value larger than "x" in "xs" which is divisible by "x".

"divs'" combines the previous two functions to find all the primes for the given value.

> let noDivs x xs = (length $ filter (\y -> (x `mod` y == 0) && (x > y)) xs) == 0> let divs x = filter (\y -> x `mod` y == 0) [2..(ceiling $ sqrt $ fromIntegral x)]> let divs' x = filter (\y -> noDivs y z) z where z = divs xmaximum $ divs' 600851475143

Problem 4:

Rather simple problem which can be solved in a single line.  Simply import Data.List:

> filter (\x -> reverse x == x) $ map show $ reverse $ sort $ concat $ map (\x -> map (*x) [1..x] ) [1..999]

Problem 5:

So, let's start with the wrong solution.  We could brute-force the problem as so:

> head $ filter snd $ map (\x -> (x,foldl (&&) True $ map (==0) $ map (\y -> x `mod` y) [2..20])) [100..]

We need a better solution.  Let's suppose we knew the prime factors of the numbers that we're dealing with.  Like so:

> let primesUntil p = filter (\x -> length (filter (\y -> x `mod` y == 0) $ [2..x-1]) == 0 ) [2..p]

Now, we can think of the solution as a permutation of the primes that arise from numbers 0...20.  Then, let us suppose we also had a function to enumerate all the possible permutations:

> let combos v n c = zipWith (\x y -> x + ((v `div` y) `mod` c)) (replicate n 1) $ map (\x -> c^x) [0..n-1]> let primeCombos p = take (3^(length z)) $ map (\x -> foldl (*) 1 $ zipWith (*) (combos x (length z) 3) z)[0..] where z = (primesUntil p)

Finally, we can combine everything together to get:

> minimum $ map fst $ filter snd $ map (\x -> (x,foldl (&&) True $ map (==0) $ map (\y -> x `mod` y) [2..20])) $ primeCombos 20

Not ideal as a solution though.  It takes quite a bit of time to run.  What would be ideal?  Proper analysis of the problems in terms of primes.  The smallest product is a product of the primes of 0...20.  Isolating the primes is a problem that would have added excess code though.

Problem 6:

Something that Haskell excels at, thankfully due to built-in big number support:

> let diffSq x = (foldl (+) 0 x)^2 - (foldl (\z y -> z + y*y) 0 x)> diffSq [1..100]

Problem 7:

For this problem, we will need a very fast function to calculate primes.  Very fast.  The naive solution though would be (assuming we have primesUntil from above):

> primesUntil 1000000000 !! 10000

Notice how the function doesn't return.  primesUntil breaks down when we wish to compute large primes since we test against all previous numbers and not just known primes.  A good prime function will use previous primes to find new primes.  It will also discard even numbers from the start.

Let me cook up a few little functions to help...

isDividedBy is the first.  It checks to see if any value divides any other value in a list.  It is intended to be written as: "10 isDividedBy [3, 4, 7]".  Note that foldr is more apt to lazy evaluation, which is exactly what we seek.

isDividedBy             :: Integer -> [Integer] -> Bool
isDividedBy x xs        =  foldr (\a b -> (x `mod` a == 0) || b) False xs

We desire a slightly more efficient way to enumerate primes.  Note that no prime will be even since they are all divisible by 2.  Also, primes become very sparse as we progress through the number line so discarding them quickly becomes kind of important.  The first primes will be multiples of a number more often than the latter primes.  Let us keep that in note and define a function to enumerate future primes:

nextPrime               :: Integer -> [Integer] -> Integer
nextPrime n xs          =  if (n `isDividedBy` xs)
                           then (nextPrime (n+2) xs)
                           else n

Good!  Let us suppose we had a way to perpetually enumerate future primes:

nextPrimes              :: Integer -> [Integer] -> [Integer]
nextPrimes x xs         =  np:(nextPrimes (x+2) pl)
                           where                              np = nextPrime x xs
                              pl = xs ++ [np]

Problem?  Still doesn't perform as well as needed.  How can we speed this code up?  There are primality tests which we can apply to filter numbers rather rapidly.  However, even with Fermat's Primality Test, we do not get much speed.

quickFermat             :: Integer -> Bool
quickFermat p           =  a^(p-1) `mod` p == 1                           where a = 2 -- p `div` 2
nextPrime               :: Integer -> [Integer] -> Integer
nextPrime n xs          =  if ((quickFermat n) || (n `isDividedBy` xs))
                           then (nextPrime (n+2) xs)
                           else n

Sounds like it's time to rethink our algorithm.  We know that division is expensive, so we should build a sieve.  Sieve of Atkin (according to Wikipedia) is the modern-day best-case.  In such a case, we wish to mark off numbers that we know to not be prime.

We can use Bertrand's Postulate and enumerate a set of values that we believe are prime between the intervals.  I would rather point out the idea of diminishing returns and mention that '2' cuts out half the numbers from primality testing.  '3' cuts out at most a quarter of the numbers.  '5' less, '7' even less, etc.  The problem is that we aren't testing just highly potential primes but the entire number line.

Let us try to enumerate all numbers that are multiples of the first few primes...  And Eureka!  A much better solution has emerged!  Unfortunately, it does not have the runtime that I'd desire.

The idea is simple, build a list of known composite numbers and flip it to get anything that is prime.  Yes - it is another implementation of the sieve of Eratosthenes.  Where it excels is at reducing the number of divisions.  There is a list being built that does not contain any prime.  By comparing it with a list of all numbers, we get a list of potential primes.  From that list, we can do simple primality tests.

Here is the code, in completion:

import Data.List
knownComposites         :: Integer -> Integer -> Integer -> [Integer]
knownComposites p s m   =  if ( m > 0 ) then p:(knownComposites (p+s) s (m-s))
                           else []
mergeLists              :: [Integer] -> [Integer] -> [Integer]
mergeLists [] []        = []
mergeLists [] b         =  b
mergeLists a []         =  a
mergeLists (a:aa) (b:bb)=  if (a == b) then a:(mergeLists aa bb)
                              else if (a<b) then a:(mergeLists aa (b:bb))
                                       else b:(mergeLists (a:aa) bb)
mergeComposites         :: [Integer] -> Integer -> [Integer]
mergeComposites [] _    = []
mergeComposites (p:pp)m = mergeLists (knownComposites p p m) (mergeComposites pp m)
compositesForPrimes     :: [Integer] -> [Integer]
compositesForPrimes p   =  mergeComposites p (foldr (*) 1 p)
missingFrom                :: [Integer] -> [Integer] -> [Integer]
missingFrom [] _           = []
missingFrom (a:aa) (b:bb)  = if (a > b) then b:(missingFrom (a:aa) bb)
                              else missingFrom aa bb
potentialPrimes         :: [Integer] -> [Integer]
potentialPrimes p       =  missingFrom (compositesForPrimes p) [2..]
quickFermat             :: Integer -> Bool
quickFermat p           =  a^(p-1) `mod` p == 1                           where a = 2 -- p `div` 2
isDividedBy             :: Integer -> [Integer] -> Bool
isDividedBy _ []        = False
isDividedBy x xs        =  foldr (\a b -> (x `mod` a == 0) || b) False xs
nextPrime               :: Integer -> [Integer] -> Integer
nextPrime n xs          =  if ((quickFermat n) || (n `isDividedBy` xs))
                           then (nextPrime (n+2) xs)
                           else n
nextPrimes              :: Integer -> [Integer] -> [Integer]
nextPrimes x xs         =  np:(nextPrimes (x+2) pl)
                           where                              np = nextPrime x xs
                              pl = xs ++ [np]
allPrimes               :: [Integer]
allPrimes               = 1:2:3:5:(nextPrimes 5 [2,3,5])
primeFilter'            :: [Integer] -> [Integer] -> [Integer]
primeFilter' p (m:mm)   =  if (m `isDividedBy` p)
                           then primeFilter' p mm
                           else m:(primeFilter' (p ++ [m]) mm)
allPrimes'              = (1:ip) ++ (primeFilter' [] $ potentialPrimes ip)
                        where ip = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233]

Just run the command "allPrimes' !! 10002" to get the answer.  I counted 1 as a prime.

Problem 8:

This one is a cute problem.  We'll solve it by first defining a variable called number by manually concatenating the given number together onto one line:

> let number = "7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450"

Good!  Good!  Now, let us split up this string into groups of 5 digits!

fives                   :: [x] -> [[x]]
fives v                 = if ((length v) < 5) then ([])
                        else ((take 5 v):(fives $ drop 1 v))

Wonderful!  Just one last part...

> import Data.Char
> maximum $ map (\x -> foldr (*) 1 $ map digitToInt x) $ fives number

What am I doing?  Taking the big string called "number" and splitting it into substrings of "5" in length (look at the definition of fives).  Then I'm mapping this lambda to each of the strings that multiplies the digits of the number together.

The "map digitToInt" will convert a string of character digits to a list of numbers.  "234" becomes [2,3,4].  The foldr multiplies it all together.  This is encapsulated in a map which applies the operation to the list from the fives function. 

Finally, maximum gives us our solution.

Problem 9:

Finally!  Another one-liner!

> map (\(x,y) -> x*y*(1000-x-y)) $ filter (\(x,y) -> x*x + y*y == (1000-x-y)*(1000-x-y) ) [(i,j) | i <- [1..1000], j <- [1..1000-i]]

There!  Now read it backwards!  We generate a tuple of numbers.  The last one must be chosen so that the sum is 1000.  Filter out any value that does not match the pythagorean inequality, and then map the remaining values to the product.  And voila!  Done!

Problem 10:

Ah!  Another problem involving prime numbers!  And we must enumerate an even greater set of primes than before!  As a hint, we wish to be able to write something as such into ghci and get a result:

> foldr (+) (-1) $ takeWhile (<2000000) allPrimes'

Until next time...

Problem 11:

(To do)

Problem 12:

First, let us define a function that computes the triangle 'n':

Prelude> let triangle x = if x > 0 then x + triangle (x - 1) else 0

Second, we wish to get a list of all triangles:

Prelude> let triangles x = (triangle x):(triangles (x + 1))

Good, with this list of triangles, we need to get all the factors.  The following returns 1 if divisible:

Prelude> let factors x y = if (y `mod` x == 0) then 1 else 0

Now

Problem n:

To be written.

Initial thoughts on video games and Wittgenstein

Overview

Indulging in both Wittgenstein's Tractatus and the new Legend of Zelda game have led to some mishmash of wires in my brain.  Foremost, the Tractatus, the more I read it, seems to describe a game engine of sorts and the limits it imposes upon the imagination.

Since this post is slightly longer than my regular posts, I have broken it down into a few sections.
- First: we will look at the mappings, how concepts from the Tractatus map flawlessly to the Legend of Zelda: a Link Between Worlds.
- Second: I shall muse on how it describes the world.
- Third: we shall consider what this means if we were an NPC (Non-Playable Character - an character inhabiting the digital world).

For convenience, I have highlighted any terms used by Wittgenstein in italics.

A little caveat - this writing is doubly to help me further my understanding of what I read by explaining my thoughts and as a reference for the future when I look upon the text again.

Mappings

Mappings are very relevant in the Zelda games.  Recall that the behaviours of objects are encoded within themselves.  Interestingly, the behaviour for interacting with a bomb is not encoded within a rock.  I've tried blowing up a rock repeatedly to no avail.  Recall that a rock can only be picked up and thrown.  There is no way to blow up a rock (except for a special type of rock with a crack in it).  Use a ton of dynamite and it will always remain.

A state of affairs is essentially the layout within a dungeon.  A level if you will.  Using an appropriate editor, many state of affairs can be brought to life.  All state of affairs are possible if imagined from objects.  It is the objects of the game world that limit the imagination.  Instead of composing complexes from atoms, the smallest building block is the size of a rock.

A picture is a design for a level.  It can relate an actual level, but doesn't have to.  It can be a subset of a level, a screen capture.  We can think of a level.

A picture, in this sense can also be thought of.  The thought encapsulates this toy world.

Game World

Interestingly, the thought process is further confined as we map the terms of the Tractatus to the toy world of a game.

These first few pages that build a model of the world so aptly describe the limits of our digital worlds.

I'm still working out the details of how they mesh - but there is something there.  Something describing the limits of what we can make, not just what we can think.

NPCs

There is also something interesting in regards to our own world.  Consider the rabbit that takes over Link's house and sets up shop - to sell all his possessions for a healthy profit to Link.  We obviously know that this character is following a simple script, but let us give him the benefit of the doubt and assign consciousness to this character.

Let's suppose one day he decides to question how his world works.  He would be able to analyze what is thinkable as Wittgenstein has done, eerily similar conclusions.  Except, the micro world would be completely different.

To feel the world around him would be to see himself from above, hear things.  He would see that he is made of pixels.  But that would be normal.  (I could have gone the route of seeing himself as a polygonal shape - conclusions would be similar).  As long as pixels looked right without any magnification, everything would be ok.

But let's say our NPC is a scientist and decides to zoom in.  Then what would be seen between the pixels?

Let's say we're dealing with an image encoded with the DCT (Discrete Cosine Transform).  Zoom in a lot!  As much as you wish!  Underneath there is a wave-like function that provides progressively blurrier visuals.  There is a point where the image is in focus.

I have deviated a bit, but this question has been in the back of my mind lately.  Is there an ideal zoom for our world, and any further magnification reveals the algorithm and not the substrate?  If I think of atoms as pixels (gross simplification, but hear me out), then as we zoom into atoms we are looking at a byproduct of the matter that holds the universe and not the actual matter.

Furthermore, are we at the intended zoom level, or are we just a happy accident that makes up the most basic of objects.

Wittgenstein must be rolling in his grave by now, by how I'm trying to subvert his work to apply to everyday toys.

First thoughts on Sprite Kit

Today,  I have decided to give Sprite Kit a try on iOS.  I have been disenchanted with the amount of setup needed for my little projects/prototypes and wanted something extremely simple to use.  Sprite Kit delivers.

First, Sprite Kit is a 2D scene graph.  You add nodes and transform them within a hierarchy.  There is a nice way to specify actions such as blinking lights or other little details atop a sprite.

My question was - how viable is this performance-wise.  After a few tests in displaying a large 512x512 tile map, here are my results:

1. Sprite Kit may be able to manage draw calls, but it works best when you manage the nodes.  For large enough levels, nodes will have to be swapped in and out.  Too many nodes and Sprite Kit will spend too much time processing them all.
2. Create a cache of nodes and recycle them -- the bottleneck was the allocation and deallocation. Even with a solid color SKSpriteNode, CPU usage would hit 90% when scrolling the map!

A few other notes after playing with Sprite Kit a bit more:

1. Render to texture effects are achieved through the core image filter system as far as I can tell.  This layout makes a feedback loop a bit challenging.  They are nodes in a tree, and previous results are not in the tree.
2. The particle system is easy to grow out of.  I tried to use it, but found that changing the velocity of all particles wasn't easy.  Rendering each particle as a sprite was surprisingly efficient.
3. Blend modes are particularly easy to set up.  They have similar names and behaviours to those in Photoshop - making for a nice way to quickly preview the result.  Note - much fewer blend modes in Sprite kit (normal, add, replace, screen)
4. Something that deserves more attention; the ability to effortlessly replace a solid colour box with an image should not be under-rated.  Why?  Have an idea for a sprite?  Give it the behaviour you want using solid colour boxes and see if it is fun before investing time making it look pretty.  This should push people to try out many behaviours before committing to anything.

There are a few caveats.  Oft when I think of some concept with a visual representation, Sprite Kit is incapable of doing what I wish (or would not do it efficiently), namely:

1. Complex / warping geometry would be beneficial.  If some instances, rather than encode a dozen images certain effects can be done through manipulation of geometry.  Suppose you had a circle and wanted it to grow spikes.  Suppose even a rope - you would be limited to build the rope out of rectangular segments.
2. Custom shaders can't be overlooked.  So many visual effects can be more readily achieved with them.  That, and multi pass techniques could add so much visually.  Worse, I do not see a clear step outside of the confines of Sprite Kit if ever these effects become desirable.  This may change in future iOS releases.  Hopefully it does.

I believe it is a great step forward in ease-of-creation for games and other multimedia apps.  Unfortunately, I wish I could use custom effects (shaders) to provide more interesting visuals.

After writing this, custom GLSL shaders are supported.  Still, I keep on being over-ambitious with the API.

I have subsequently written my thoughts on lighting and SpriteKit.

Effective Computation

One thing that strikes me is how much effort we humans put into writing highly precise rules for machines.  As I grow older, one thing that preoccupies my thoughts is how I can effectively reduce the verbiage that the machine needs.

Current programming methodologies require an army of programmers.  A ton of people to implement a solution to a problem.  And, if I were to trust my intuition, the reason everyone underestimates the time to make something arises from a natural high-level view rather than a fine-combed every-detail accounted for view.

What has happened, then, to give a high level view is a massive number of functions.  Really, a ton of functions.  Highly specialized functions.  Want to delete a file, there's a function.  Want to list all folders, another function, etc. etc.  there is little consistency amongst the APIs.

But, let's step back a bit.  What are we actually working with?  Linear algebra has this nice notion of a vector space.  As long as certain basic rules are obeyed, then a set is a vector space.  Then what is the verbiage that we see so often in programming languages?

First, the data.  It's all dictionaries.  An array is a dictionary with unsigned integer values as keys.  A set is a dictionary with just keys, nil values.  A queue is a dictionary with keys always increasing and the minimum key being removed...  File systems are dictionaries of dictionaries.  A 3D scene is a dictionary forming a tree of dictionaries.

We can even further simplify it to a tree.  A binary tree.  As a dictionary can be implemented using one...

If we can access all data uniformly, then what do we do with logic?  Bring the most common logic into the API.  Find through the file system is the same as find a node in a scene graph.  This essentially forces consistency across the entire API.

If we want to drop the learning curve and increase the speed of development, then it is this that we must consider.  Focus on what is peculiar to the software at hand, not get marred in the details that all software reinvents as a rite of passage.

The Lambda Calculus and Lazy Evaluation

For quite some time I've been looking into building a programming language that is both functional and supports lazy evaluation.  I may not have the energy to actually write the code, but I do keep thinking about it.

First thing I should have realized earlier: studying the theoretical foundations of functional languages (ie. The lambda calculus) would help me achieve my goals.

First, what is lazy evaluation?  Essentially, an expression is only evaluated as long as the calculations lead to the final result.  In a Haskell-like fictional language, I would say function "Pi" calculates Pi to an infinite number of digits.  Then "take 100 Pi" would take the first 100 digits of Pi and stop computing any further digits.

My initial mental model of this process was very convoluted.  Essentially, requiring back-tracking on the stack.  Now, looking at the lambda calculus, it makes a lot more sense.

Recall that the lambda calculus consists of a series of variables and production rules.  Rules are of the form: \xy.yx, where \ is a make-shift lambda, xy are the input, and yx the output.  Essentially flipping the values.

Execution in a functional language starts with a function.  Let's call it R.  Well, R does nothing on its own, so let's evaluate it.  We get T 3 P.  Yup, same as the pseudo-Haskell above, except 3 digits.  Let's try parsing this.

First, some syntax.  : means element in a list.  So x:P means x is the first element from P...

I expand it to something like:

(a:b:c.P)

At each step in T n, we take the head of the list from P and recursively call T (n-1).  In the end, we are matching a set of 3 elements to the infinite list P.  Notice that once P evaluates 3 elements, the matching is complete and any further evaluation of P is not needed.

This is what escaped me!  That means structured properly I could evaluate and match expressions and get lazy evaluation for free!  Or so I believe.  I'll keep on reflecting on the corner cases, but for now "early match and discard" seems to do the trick.

The Future Rants

Glimpses of a potential future have been assembled in the past two weeks thanks to leaks that media companies were happy to publish as infotainment.  Interests will wane, and like all other hot topics buried and people will omit what is happening from their collective consciousness unless people feed the fire by making more of a scene from the information.

Arguments for keeping track of everything seem to revolve around preventing people from doing bad things.  If the good guys of enforcement have access to all communications then they can prevent bad things from even landing on the radar.  Looking at patterns, anomalies can be spotted and investigated.  From the anomalies, bad people can be exposed.

Perfect people would manage this information tracking system so it would only be used for its intended purposes.  Perfect people would make the perfect hardware and software setup so it can't be hacked.  Perfect people would peruse the data looking for information without thinking of personal gain.  Perfect people would take utmost care of the data so no outside person sees it.  Perfect algorithms to sift through the data.  Perfect data to identify the right person.  Complete and utter perfection now and indefinitely into the future.

People aren't perfect.  The world isn't split into good and evil.  Good people win since the winners decide what is good -- play on history is written by the winners.

There's enough information floating on the Internet, that if someone were to capture it, for a single person they could determine income, circle of friends, health status/records, interests, means of expression, opinions, every purchase ever done, current location, affiliations, etc.  A complete profile, perfect for nefarious purposes.

Now I get off my soap box.  This is probably a repetition of what others said.  I just needed to collect my thoughts a bit and reflect.