GCJ B - Cookie Clicker Alpha


Another problem from This year’s Google Code Jam.

The gist of the problem is to work out whether buying additional capacity for cookie production would result is reaching the quota faster than not buying additional capacity.

Haskell is suited to this for a couple of reasons. Firstly, its’ easy to work with infinite lists. so I can create list of the cumulative times for creating factories and reaching the target. And to calculate the cumulative target I’m using the scanl1 function to turn the infinite list of factory times into an infinite list of partial sums. I’m using scanl1 because it starts at 0, which is important as one of the gotcha’s with this is that it may be faster to just generate cookies rather than buying a factory in the first instance.

Secondly, pattern matching. With the infinite list I’m stopping when the time to reach the target starts growing again. Pattern matching makes this very easy to do.

module Main where

import Control.Monad
import Numeric

-- https://code.google.com/codejam/contest/dashboard?c=2974486#s=p1
-- Input and output with standard redirection operators

factoryTimes :: Double -> Double -> [Double]
factoryTimes c f = 0.0 : [ c / (2.0 + k * f) | k <- [0.0, 1.0 ..]]

productionTimes :: Double -> Double -> [Double]
productionTimes x f = [ x / (2.0 + k * f) | k <- [0.0, 1.0 ..]]

times :: Double -> Double -> Double -> [Double]
times c f x = zipWith (+) production factory
  where production = productionTimes x f
        factory = scanl1 (+) $ factoryTimes c f

firstMinimum :: [Double] -> Double
firstMinimum (x:y:ys) = if x < y
                        then x
                        else firstMinimum (y:ys)

solve :: Double -> Double -> Double -> Double
solve c f x = firstMinimum $ times c f x

main :: IO ()
main = do
  t <- getLine
  forM_ [1..read t :: Int] $ \i -> do
    [c, f, x] <- fmap (map read . words) getLine
    let result = solve c f x
    putStrLn $ concat ["Case #", show i, ": ", Numeric.showFFloat (Just 7) result ""]

GCJ A - Magic Trick


I got through the qualification round for Google Code Jam 2014. I usually manage to get through this stage; it’s the first round that I haven’t managed to get past yet.

The easiest question was A-Magic Trick. Nothing much to do here but count the number of similarities between two arrays, easily achieved with the interact method.

The only gotcha in this problem was that the index of the rows to check is 1-based, and most programming languages use 0-based indexing.

module Main where

import Control.Monad
import Data.List

-- https://code.google.com/codejam/contest/dashboard?c=2974486#s=p0
-- Input and output with standard redirection operators

solve :: [Int] -> [Int] -> String
solve a b
  | l == 1 = show $ head common
  | l > 1  = "Bad magician!"
  | otherwise = "Volunteer cheated!"
  where common = a `intersect` b
        l = length common

main :: IO ()
main = do
  t <- getLine
  forM_ [1..read t :: Int] $ \i -> do
    choice1 <- fmap read getLine
    initial <- replicateM 4 $ fmap (map read . words) getLine
    choice2 <- fmap read getLine
    final <- replicateM 4 $ fmap (map read . words) getLine
    let r1 = initial !! (choice1 - 1)
        r2 = final !! (choice2 - 1)
    putStrLn $ concat ["Case #", show i, ": ", solve r1 r2]

Hakyll New Post With Emacs


When this blog was created using Octopress, a new post could be created by simply running rake new_post in the Terminal. There is no such convenience in Hakyll, which is currently used as the generator. A small thing, but I wanted to fix it.

I could have created a similar Rake task, or shell script to do this, and there are even examples to be found on Hakyll’s site. But since I’m usually in Emacs when I want to write a new post, I thought it would be a good excuse to write a little lisp. And so, here is my first attempt.

(defun hakyll-site-location ()
  "Return the location of the Hakyll files."

(defun hakyll-new-post (title tags)
  "Create a new Hakyll post for today with TITLE and TAGS."
  (interactive "sTitle: \nsTags: ")
  (let ((file-name (hakyll-post-title title)))
    (set-buffer (get-buffer-create file-name))
     (format "---\ntitle: %s\ntags: %s\ndescription: \n---\n\n" title tags))
     (expand-file-name file-name (concat (hakyll-site-location) "posts")))
    (switch-to-buffer file-name)))

(defun hakyll-new-note (title)
  "Create a new Note with TITLE."
  (interactive "sTitle: ")
  (let ((file-name (hakyll-note-title title)))
    (set-buffer (get-buffer-create file-name))
    (insert (format "---\ntitle: %s\ndescription: \n---\n\n" title))
     (expand-file-name file-name (concat (hakyll-site-location) "notes")))
    (switch-to-buffer file-name)))

(defun hakyll-post-title (title)
  "Return a file name based on TITLE for the post."
   (format-time-string "%Y-%m-%d")
   (replace-regexp-in-string " " "-" (downcase title))

(defun hakyll-note-title (title)
  "Return a file name based on TITLE for the note."
   (replace-regexp-in-string " " "-" (downcase title))

I’m not much of a lisper, and it probably took me longer to write than the time it will save me, but that doesn’t matter. Firstly; it might be useful to somebody else, and so the cumulative time saved could be greater.

Secondly, my day job means I spend most of my coding time in Xcode, which can’t be customised as Emacs can be, and if I don’t spend time writing and learning lisp, I’ll have no chance of getting better at it.

So, I think it’s not bad as a first attempt, although it could obviously be refactored, and you can follow the history of it in my dotfiles repository if you want to see how it could be developed (or even, you know, help me out with it).

Hello Hakyll


This site is now being generated by Hakyll instead of Octopress

It’s something I’ve been planning on doing for a while, but feeling a bit burned out on Objective-C / Cocoa and facing a few days downtime over the seasonal holidays now was the time to actually do it.

Octopress is nice, and if you are just using the default theme, it’s easy to get up and running fairly quickly. But I found that updating the site for new versions of Octopress was fragile. I actually managed to break the installation, somehow, and that goes some way to explaining why there wasn’t much posted this year.

Hakyll is written in Haskell, and takes a little bit of work to get set up. Two things that make this a bit more difficult than normal. But, many people have made their site code public as examples, and this is very useful in getting started. I hope that my source shows up in that list in due course. (Update - it is now!).

Despite what some wags may have said on Twitter; it’s not actually that hip.

Twitter screenshot

Twitter screenshot

Git at London Web Standards


London Web Standards is focusing on Git for their meeting on 17th June. I’m going to be talking on the topic of “Git’s not what you think it is”.

You think you know Git? Really?

Are you using Git the same tired old way, checking in your changes and pulling from your colleagues? Do you get the sneaking feeling that others are having much more fun with it than you are?

Are you a refusenik, not tempted to use version control because its not for you?

I’m going to challenge some common ideas about Git; I hope to get current users to be more expansive in their use of it, and maybe to bring some new users into the fold.
The abstract

I’ve been talking about Git since 2009, which is when I became comfortable using it. I’ve heard some reasons for people not using it, or using it in its simplest form. My aim in this talk is to turn those statements on their head; maybe to get people to think about using git, not just as a set of task based recipes (which is a perfectly good way of working), but also to use the parts of it that seem too difficult, or poorly explained.