First Day of 10.7

I decided it might be worth updating Mac OS to 10.7.  First, for anyone thinking of updating, double-check all of your apps.  I was surprised by the number of applications that I had that were PowerPC.  I think the machine was spending more time running Rosetta than x86 binaries...  The important apps I found newer versions and trudged forward.  My scanner will only be usable with an older Power Mac.

So.  How does the OS fare?  Here are the positive and negative features on a per-app/feature basis in my opinion.

Mail.app
Mail.app's interface update is great!  The application is now designed for wider screens.  On the far left is the side-bar as it was there before (hidden by default but click on "Afficher" -- I guess that's "Show" in English).  Organized like it is, stretch the application and there is plenty of room for the previews and other information.  The preferences allow for plenty of customization.

iCal
I like the way it looks.  Where Mail.app got a massive functionality upgrade, iCal seems to suffer.  The problem is that things normally aren't neatly split up between months.  So if I'm trying to schedule something it won't be for a specific day but some time-range.  So I want to quickly jump between weeks (if possible see multiple weeks) and not be stuck in groups a day/week/month/year.  (the option to scroll a day at a time is silly - it renders the velocity scrolling of the magic mouse useless)

For example, if in the week view it scrolled continuously and could display multiple weeks in it's columnar view I'd be very happy.  For the day view, for a sufficiently wide screen multiple months can be seen.  Even multiple days.  On a small 1024x768 screen the spacing is elegant, however I'd argue there is space for two more monthly calendars in day and week view.

Finder
Overall, it's as usable as ever.  I can't complain, it feels normal.  A few settings I had to re-enable, but it's as I expected.  The overall view of all my files is... pointless.  It seems to be randomly picking stuff I downloaded -- such as a picture generated by Doxygen.

I'm happy that the library is now hidden.  To many things could go wrong by having that exposed to the user.  Those of us that wish to muck with system stuff can hit Command-Shift-G.  The icons are much clearer.

Terminal
Works.  Happy.  Why can it go fullscreen?!

LaunchPad
I don't know what to make of this.  LaunchPad attempts to present a nicer view of the applications.  Sure, that's great!  The question that's running around my head is: why isn't LaunchPad's view synchronized with the Application folder?

For example, a folder in Applications becomes a folder in LaunchPad.  Of course there are issues with nesting folders but I don't see why folders nested more than one couldn't just be collapsed.  Certain applications would be dangerous to move (bad developers)...  However organizing my applications once is, in my opinion, preferable.

Actually, I would have loved LaunchPad if it just opened a fancy view of my Applications folder.

Apart from that, it's a great idea.  Only if I didn't use the dock to store often-used applications and Spotlight for everything else.  (StarCraft II?  Spotlight!)

Mission Control
A very good update to Exposé.  It unifies all the window management features into one nice spot.  One button to see all my windows from all the apps with all the desktops + fullscreen apps.  Then, windows from the same application are grouped.  It's very nice.

Fullscreen Apps
Really.  I wanted to love this.  I have a small-ish monitor on the side where I tend to throw documentation, iTunes, Mail, and the web browser.  The main monitor is reserved for work (XCode, iOS Simulator, etc.).  Never doubt having the documentation on a second monitor!

Fullscreen apps grey out the second monitor.  As in, they don't use it!  And I can't put floating windows on it if applications on the main monitor are full screen.  XCode, which I thought would actually use both monitors (put the Organizer on the second!) spawned the Organizer as a new full-screen window.

Use multiple monitors?  You'll go further running the applications in windows.

Safari
The download window is gone and replaced with a pop-up...  Thanks Apple!

Unfortunately flash videos skip now when the system is under load...

XCode
The documentation within the Organizer is still a mess.  It's more convenient browsing to Apple's site since the side-bar should be synchronized to the documentation (or a viewable side-bar should be there).

No, I don't want Quick Help.  Quick Help doesn't even pick up on the Doxygen comments littering my code.

Last Impressions
The Mac OS / iOS hybrid seems to be an odd beast.  The ability to quit and resume applications is wonderful.  But the addition of fullscreen applications and launchpad feel like kludges.  (LaunchPad especially feels like it's tacked on rather than integral).

The scroll-bars...  This is minor.  Use it for a day or two with the default settings.  Within a few minutes I was already used to the scrolling.  The elimination of scrollbars didn't affect me:  I never used them anyhow.  Give it a chance for at least a day.

Autocomplete -- it's annoying when it fails.

Those are my comments from one day with the system...

Software: From Simple to Complicated

A few years ago, I started a small software library.  A set of common routines.  Seeing how useful it was, I decided to expand it -- make it more general.  Apply good software development techniques so that it may prove to be more flexible.

For example, at the beginning I hardcoded the ability to use a single 1024x1024 texture for everything.  This meant I had no need to worry about which texture was currently bound (only one) and no need to manage memory (one fixed amount of memory used).  Then I expanded this system to load multiple textures using a plist for the parameters.

For the added flexibility, I was able to create textures and use them as objects.  Yet; as far as making prototypes go it didn't speed things up.  Memory became an issue to manage.  And now mipmapping and other little technological ideas for the sake of technology start to creep in when ideas should be driving the technology.

In the end; I should conclude the organization for generic code is only needed when called for.  If it works, and works well, why change it?

StarCraft II: Beating the AI on Hard

Watching others play StarCraft is the best way to learn.  And I have successfully beat the AI on hard using all of the races (1 vs 1).  And the pattern is actually quite simple (on Blizzard's maps at least).

First; we should realize the harvesting is the main bottleneck.  If you have to wait a second to build a unit (unless the game has just started) then something is wrong.

The other bottleneck is production speed.  If you have too many resources and can't spend them on units, something is wrong.

So; here's the overall build order:
1. Get up the 20 units harvesting the mineral fields provided at the beginning.
2. Zerg: get Zerglings (also, build a queen as soon as possible), Terrain: get marines (build two barracks), Protoss: Zealots (build two warp gates).
3. Set up a second base (no air units at this time).  Get 20 units harvesting the second mineral field (while producing a steady stream of offensive units -- your first test is surviving the first wave).
4.  For Zerg start focusing on roaches and move towards hydralisks (air defence) -- if all goes well you have so many minerals to waste that building a third or fourth hatchery for extra unit production is worth-while.  For terrain, build a factory for stronger units, however you should be able to afford 4-5 barracks producing a continual stream of marines.  Similarly, for protoss, 4-5 warp gates can produce plenty of units (but the zealots won't be enough, vary it a bit with them.)
5.  Send waves of units (if there are enough) into enemy territory (scouting may be needed).  I let them die off and focus on preparing the next wave.  If you have the talent, you might want to call back weak units.
6.  Prepare a final wave composed of tougher units (ultralisks, for example).

And victory should follow.  This just rushes the AI with too many units.  It can fail, but it tends to succeed.  If you aren't sure why things went wrong, look at the replays and see how the AI played.

Fast Integer Square Root

Here's my attempt at writing a fast square root function for integers.  It's not as fast as the built-in sqrtf function (even with type conversions) but it's decent.  In the worst case it was twice as slow -- but that would downplay the significance of the learning experience.

First, I try to estimate a point near the root.  Consider a number in binary, it's square root will be between two to the power of half of the length of the binary string rounded up and double that value.  The lower bound can be made more accurate, but this is sufficient.

Then, with the maximum and minimum, the midpoint should be a good starting point or guess that I feed into Newton's method.  Newton's method is used to increment or decrement the initial guess to something a bit saner.

More speed can be obtained by replacing some division by bit-shifting (but that's dangerous).  The fastest (and smartest) way would be to use the built-in SSE functions to do the square root and inverse square root (properly pipelined).

//! Same, but this time do Newton's method

int sqNewton(int in_val)

{

int c = in_val;

if (c <= 0) return 0;

int lower = 1;

if (c >= (1 << 16))

{

c >>= 16;

lower <<= 8;

}

if (c >= (1 << 8))

{

c >>= 8;

lower <<= 4;

}

if (c >= (1 << 4))

{

c >>= 4;

lower <<= 2;

}

if (c >= (1 << 2))

{

c >>= 2;

lower <<= 1;

}

//Hit mid-bound

lower = lower*3/2;

//printf("%li %li %li\n", lower, in_val, lower*lower-in_val);

int numerator = lower*lower + in_val;

int denominator = 2*lower;

return numerator/denominator;

}

Rant on P versus NP

The weekend spent on absorbing information relating to P's relation to NP, I shall now solidify my understandings through regurgitation of what I've understood.

First, the types of texts that I've found either went deep into the topic (from the theoretical perspective) or brushed lightly upon it (the way a book on programming treats mathematics).  I'll try to walk a fine line between both while maintaining clarity.  Hopefully it works.

What are P and NP?

These have to do with timing.  Not in seconds, but in 'effort'.  For example, consider sorting books in a book-shelf.  You could scan through the 'N' books to sort, find the smallest one (or whatever sorting criteria you want), and put it at the beginning of the shelf.  This operation could be repeated for the remaining books.  So, to sort 'N' books, you'd look at (on average) 'N/2' books to find the next one to place to the left of the shelf.  That involves looking at 'N^(N/2)' books.  In the big picture, we say 'N^N' (N to the N) operations will be needed.  As the number of books increase, this method of sorting will be excruciatingly slow.  It is left as an exercise to the reader to translate looking at book titles to actual time.

They also have something to do with 'polynomial time'.  That is, a number that can be expressed in the form of 'N^x' where 'N' is the number of elements to work on and 'x' is a constant.  Sorting books according to our previous example takes much longer than polynomial time (think of very large 'N').

P looks at problems that take polynomial time.  Specifically, deterministic problems.  Typically involving Turing machines (but I don't want to go into the details of tapes).  Essentially, any problem whose solution expressed as a series of unambiguous steps takes polynomial time is in P.

And NP also looks at problems that take polynomial time.  This time, problems whose solution is expressed non-deterministically.  Back to our book sorting problem, we looked at 'N/2' books (on average) to find the next book to place on the shelf.  But what if we just 'looked at all the books at once' and happened to pick the right one.  Something similar goes on with 'Oracle machines'.  However, NP is easier to understand as the time it takes to verify the problem.  In other words, our book sorting would take 'N' time in non-deterministic polynomial time (NP-time)

And why is P versus NP important?

The crux of the problem: are all the problems in NP also part of P?  Essentially, NP problems are easy to verify but can be hard to compute.  Like our sorting problem, we only need to inspect each book once to confirm that they are sorted.  Similar ideas are used in cryptography -- a very difficult problem must be solved by the person who attempts to intercept the message.

Problems in P are those that are practically solvable (well, practically this is debatable, theoretically this is true).  There are problems that are much more difficult.  Let's call these NP-Complete (ok, technically NP-Complete problems are a class of problems where if one is easily solved then all of them can be easily solved.  They are very difficult to solve though).  For example, given a series of numbers, find the subset whose sum is the greatest.  Short of attempting every possible combination of numbers, a solution is hard to find (programmers may chime in with 'dynamic programming' rolling off their tongue.  But, that just stores intermediate results, all potential combinations are still evaluated.).

Back to encryption, if P = NP then there is a way to easily decrypt data.  From what I read, a lot of things would become much easier.

But that is the essential nature of P = NP as far as I can tell for now.  I might change my mind as I become more informed.

Haskell to Solve Programming Challenges

There are times when I do silly things.  This is one of them.  Here are my solutions to the first 3 problems for the June 2011 Waterloo Local Contest (http://plg1.cs.uwaterloo.ca/~acm00/) -- not the most difficult, but good enough given my knowledge of Haskell.

So...  Let's start with the game of 31.  Just call the method `finishGame` with the input string.  It runs quite fast.


import List


-- Get the score from a list that is the game
scoreForGame :: (Integral a) => [a] -> a
scoreForGame x = foldl (+) 0 x


-- Change an int into a list
gameFromInt :: (Integral a) => a -> [a]
gameFromInt 0 = []
gameFromInt x = (x `mod` 10) : gameFromInt (x `div` 10)


-- Obtain the player for a game
data Player = A | B deriving (Show)


playerFromGame :: (Integral a) => [a] -> Player
playerFromGame x = if (even $ length x) then B else A




otherPlayer :: Player -> Player
otherPlayer B = A
otherPlayer A = B




-- Score a single move
scoreMove :: (Integral a) => a -> [a] -> a -> a
scoreMove score deck play
   | score + play > 31     = -1
   | otherwise             = if (elem 1 $ map (scoreMove (score+play) deckMinusPlay) (nub deckMinusPlay)) then -1 else 1
   where deckMinusPlay = delete play deck


-- Generate deck
deck :: (Integral a) => [a]
deck = [1..6] ++ [1..6] ++ [1..6] ++ [1..6]


-- Finish the game!
--    Takes the game and writes out the winner!
finishGame :: (Integral a) => a -> Player
finishGame a = if (r > 0) then p else otherPlayer p
   where
      d = deck \\ sort g
      g = gameFromInt a
      s = scoreForGame g
      p = playerFromGame g
      r = if (elem 1 $ map (scoreMove s d) (nub d) ) then -1 else 1

Ok.  That actually wasn't that bad.  And it worked.  Some people might complain that scoreMove returns 1 if the current player wins else -1 -- and keeps flipping the numbers between invocations.  Note that I check to see if the element is 1 rather than the more intuitive maximum as this allows Haskell to do lazy evaluation (on the first 1 found within the map over elements in deck stop processing since the player won!).

The \\ operator was a challenge to find.  It's great!  In `List', it subtracts the elements between lists.  Eg, [1,2,3,4,5] \\ [2,3] = [1,4,5].

On to problem 2.  Factoring large numbers.  Actually, using Haskell is probably cheating as you need to maintain a list of prime numbers to at least finish in 30 seconds (Haskell cached it for me)...  The code is quite simple:


import Control.Parallel


-- Generate an infinite list of primes?!


divides :: (Integral a) => a -> [a] -> Bool
divides _ []   =  False
divides n (x:xs)
   |  x*x <= n    = (n `mod` x == 0) || (divides n xs)
   |  otherwise   = False


firstPrime' :: (Integral a) => [a] -> a  -> a
firstPrime' (p:primes) value
   | (value `mod` p == 0)  = p
   | p*p > value           = value
   | otherwise             = firstPrime' primes value


firstPrime :: (Integral a) => a->a
firstPrime = firstPrime' primes


nextPrimes :: (Integral a) => a -> [a] -> [a]
nextPrimes trial primes
   |  (divides trial primes)  = nextPrimes (trial+2) primes
   |  otherwise               = trial:(nextPrimes (trial+2) (primes ++ [trial]))


primes :: (Integral a) => [a]
primes = 2:3:(nextPrimes 5 [3])


-- Return all the factors of a!
factor :: (Integral a) => a -> [a]
factor 1    = []
factor a    = p:(factor $ a `div` p)
   where p = firstPrime a


main :: IO ()
main = do
         print $ factor 90
         print $ factor 1234567891
         print $ factor 18991325453139
         print $ factor 18991325453143
         print $ factor 18991325453141
         print $ factor 12745267386521023


One comment I should make, lazy evaluation was essential!  Also, I am aware that (primes ++ [trial]) will do a complete list traversal of primes to append a single element.  Without that, the recursion was destroying the performance on the divides and firstPrime'.  In total, it's about 19 seconds to run.  Slower when more CPU is used...

Next off!  Computing the fibonacci sequence.  Once it hit me that I should try to avoid recursion (it's so natural) then I got this very nice and very fast solution:


import Control.Parallel


fib :: (Integral n) => n -> n
fib 1 = 1
fib 2 = 1
fib x = (fib $ x-1) + (fib $ x-2)


fibList' :: Integer -> Integer -> [Integer]
fibList' m1 m2 = m2:(fibList' (m2+m1) m1)


fibList :: [Integer]
fibList = (fibList' 1 1)


fib'' :: [Integer] -> Integer -> Integer
fib'' (x:xs) n
   | n <= 1    = x
   | otherwise = fib'' xs (n-1)


fib' :: Integer -> Integer
fib' = fib'' fibList


main :: IO ()
main = do
   print $ fib' 100
   print $ fib' 997
   print $ fib' 1000
   print $ fib' 1009
   print $ fib' 4500


I think for this 3rd problem, the challenge was to work with very large numbers efficiently.  Which Haskell does automagically.

Why infinite lists?  lazy evaluation is the answer!  I find it makes the algorithm cleaner even though a few things had to be shuffled around.  I did have fun typing fibList and seeing all the numbers in the fibonacci sequence appear.  And hopefully, written in this way it can cache intermediate results (but it runs so fast I don't think it even matters)!

Done a few programming challenges for the day!

Branding the Perfect Image

Perfection.  The opposite of being human.  How interesting.

We accept nothing but perfection from the leaders of the world.  Some brands attempt to portray themselves as perfect, hiding faults to promote products (unless legally obliged).  And now branding seems to be entering the world of social media, with people participating in campaigns for some reward (or without realizing it).

As people get brought into this mess of branding / advertising, their language must be monitored.  Bad things may not be said (in the past nor the future as everything is recorded for infinity - easily searched).  Even a minor mistake, redacted, can spread like wildfire as it gets cached (remembered) within various minds, machines, and search engines.  Who will control what this legion of unwashed masses does to help promote a brand?

Why do I bring this up?  Some people use social media to socialize, voice honest opinions.  Others use the media to present an image of themselves.  The latter is useful for brands as they play the game of perfection. The former can get the message across but will not let hesitate to post an honest idea.  SLAPPs are probably the best vehicle to keep everyone in line.

What makes the social media useful are the honest opinions.  Those that call out defects, problems, lemons if you will.  Attempting to use this word of mouth to spread a fixed message appears to be restricted to the set of people willing to appear perfect.

People aren't perfect.

In Search of Software Simplicity

15 years ago I was making small video-games as a hobbyist.  The games were simple, pushing QBasic to its limits.

Jump forward to today, 2011, and I'm still making video-games as a hobbyist.  The software development landscape has greatly changed.  Things look nicer, and the complexity of software development has jumped.  I try to keep up by abstracting away concepts.

The last concept I tried to abstract away was physics.  Of course there are plenty of physics engines out there, but I believe it is best that I understand how these work.  And more often than not, they are too powerful for what I wish to develop.

Even my simplistic set of objects are often times overkill for what I wish to do...

The last object I created, which I should have created a long time ago, is called "Angle".  It allows me to take and compare angles (even though they only exist between -PI and PI).  Something that makes my software more error prone and has greatly helped in reducing bugs.

Another object that I have is "Particle".  It's a point in space (2D or 3D) that has certain physical properties such as mass, velocity, etc.  A character is in essence a particle (it shares the same properties).  But, it can not go through anything.  So, should I infuse, within particle, all the potential logic to handle the case where it is within a bounding box that can collide with this specific world, or should I implement a custom type of object.

The arguments against the custom object are well known.  Code reuse.

But the arguments for creating a custom object are also strong:  Polluting a clean code-base for a one-time-use object is not worth it.  The particle object need not be that complex - leaving it simple means I can more easily reuse it when the time comes.

What if something else needs this code?  Then I'll worry about abstraction.  No use abstracting away something when I'm prototyping.  The goal isn't a library but something to test the feasibility.  The library is just a nice side-effect that happens when I try to keep track of the big picture.

Maybe code reuse is not the ultimate in software simplicity.

I'll leave this rant on one final note:  there once was an article (I believe the Daily WTF) which talked about the added efficiency of using the built-in functions to delete folders rather than recursively deleting folders.  Then it came to me, wouldn't it be more obvious if the right solution were to combine "fmap" with the "delete function" and a "file list"...

Complexity from combinations of simple elements, what a great thought!

My Latest Haskell Experiments

Many moons have risen in the night sky as I tried with great difficulty to become a Haskell master.  Lacking knowledge of category theory and Monads being this abstract notion with no concrete definition.  My infatuation with the language began with the desire to write a better programming language where I could express select computations and generate code to optimally handle a variety of data structures.  Haskell expressed purity in its functioning and strict type checking.  Winner it clearly was.

This year, marking at least the third, I have again revisited Haskell.  No language has managed to elude me before.  I will figure this one out.  This year, a book I have invested in.  A book I have read cover to cover. Another attempt at writing a code generator followed.

As I programmed Prolog, my mind always translated the code to it's sequential equivalent.  If this is done, then all possibilities are recursively enumerated until a solution is found.

Haskell, with Monads, is another story.  My problem was this silly attempt to maintain an imperative mindset rather than thinking functionally.  Hence, now I will document what I have discovered -- as many must have done before.  For someone wiser than I who can extrapolate the interesting portions and run forward -- someone who wishes to see how the thinking differs.  For tutorials, many have written much better texts than I could.

I'll start with the concept of laziness.  Haskell is lazy.  In an imperative language, suppose you had a for loop.  As long as it writes to a memory location (or potentially could write to a memory location) it will be run.  Haskell takes a goal and follows a chain of dependencies until it has finished the calculation at hand.  Back to our for loop, this means the compiler (or language) would need to provide a way to determine if a given write to a memory address will actually impact the resulting computation in the future.  This is possible for certain local computations on the stack, but anything dealing with shared objects is next to impossible.  Forget about static memory locations.

If we logically follow this path of thought, it means that Haskell has some restrictions on the language to allow it to do such reasoning.  Two things come to mind.  First global non-constant variables must go.  Suppose an object were to change a global variable, how would it know that no other object were to access that variable?  It becomes impossible with libraries unless everything must register for the data it will read from a-priori.

Actually, for the second thing, local variables as well should be constant.  Parameters passed to functions should be constant.  As should be the return values.  Essentially, all data becomes immutable.  Why do we want this?  All computations can now be represented as an acyclic graph.  You can start with a variable -- it is computed by calling a function, let's say.  That function's input is known, and the result is computed from information that is known.  So, let's say every computation that must be done for any value is known.  Then all that you need is to look at the graph of computations, only compute the nodes (that hold the operations) whose result benefits the desired computation at hand.

Some may wonder about determinism.  That is covered by the second thing.  If every variable is constant and can only change by creating a new constant whose value is computed by a series of predictable constant values then a function will always return the same output for a given input.

Implied by determinism and constant everything is the need for recursion.  Why recursion?  It creates more stack space to put constant values.  It also creates a framework to destroy values when they are no longer needed.

So that leads us to state...  how do we manage state?  Here, Haskell is very elegant.  Imagine you have an object that represents state.  Manipulating that object returns a new state object.  That old state object is discarded and the new one is used.  Haskell provides ways to automate this process.  This is the last piece of mind-bending...

Consider a multi-parameter function that returns a single value.  Suppose you gave a single parameter to the function and a new function was created with one-less parameter.  Let's call the first parameter the state and the return value is a combination of the state and some value (which we have yet to define).

Now, let's create functions that work on two inputs (the state and the data) and outputs two things (the state and the data).  The first function takes in a function, state, data, and outputs state and data.  Suppose the function to our function just manipulates data based on the current state.

A bit mind-bending, but now the state management is separated from the computations.  This doesn't always work, but when it does it's quite neat.  Error handling can be simplified in a similar way.  The error state can be a container that checks return values to make sure they are valid.  Push the idea further, since it's a function calling a function doing the actual work, the function that does the calling can first ensure that only non-error states can continue computations.  Want an exception state?  sure, have a function that takes two functions (the second only gets called on error).

Let's push this a bit further.  Our error functions last parameter is the data, but the first is the state.  Recall that we can assign values to the first parameters to create new functions?  Now, push this further and say assign a function with the promise to evaluate the results if successful.  In C this might look like: eval(func1, data1, eval(func2, data2, eval(func3, data3, ...)))...  Messy.   In Haskell: eval func1 data1 $ eval func2 data2 $ eval func3 data3.  Read it backwards...

Isn't that cleaner?  I'd need to get back to the book to give further insights as I'm too quickly jumping into Monads...  But, I think the point is made.

Haskell glues functions within functions (think containers) to abstract away computations.  Error handling can be seen as a series of functions.  As is state maintenance.  The typical machinery for this is a Monad.

Ok, quickly.  Monads.  Monads just say that a given object (some type of state) wraps another object (computation).  They define operators that must function for each Monad, and each Monad must conform to a set of rules so they behave as other programmers expect.

First, a Monad should be able to take a computation object and wrap it in a state object.  Second, given a function operating on the data, the Monad should be able to do the computations exactly as though they were done devoid of state.  Last, computations should give the same result no matter the order.  (a*b)*c = a*(b*c).

Well, something like that.  The concept, for a person used to the imperative style, should see a consistent use of the class adapter pattern.  The adaptee is the computation, the client is the state.