### Benjamin Kovach

#### Code Golf

I’ve always been interested in Code golf, which essentially boils down to creating the shortest possible program that completes some task. I finally got around to completing one of these challenges, and though I wasn’t really that close to winning, it was fun to mess around with it and it was one of the shorter Haskell solutions!

The challenge I attempted was Reddit’s Tiny Code Challenge #4, asking for the shortest program that finds the longest identical subsequence in a string. Directly from the challenge page, for example:

aaabbbbccc aabccdcdd ->  aab, bcc
abcdef ghijk -> nothing
abcdef fghijk -> f

So, here was my solution in Haskell:

import Data.List
import System.Environment
f=concat.r
r []=[[]]
r s=(scanr(:)[]s):(r$init s) g [a,b]=snd.maximum.map(\x->(length x,x))$intersect(f a)(f b)
main=getArgs>>= \z-> print.g$z  Let’s break this down into steps, since it probably looks like a bunch of mumbo-jumbo! import Data.List -- gets us the function "intersect" import System.Environment -- gets us the function "getArgs" f=concat.r -- calls "r" on some input and flattens the results (concat) {- The function "r" takes a list of elements and produces all of it's possible sublists. Base case: If the input list is empty, return an empty list containing a single empty list. -} r []=[[]] -- base case for "r" r s= (scanr(:)[]s) {- recursively build substrings from the list "s" and push them to an empty list -} : -- Append the list we just built to... (r$init s)     		-- "r" called on the first n-1 elements of of the current list "s"

g [a,b]=snd.maximum.		-- finds the maximum by the length of strings
map(\x->(length x, x))	-- groups lists into tuples of their lengths and the list
$intersect(f a)(f b) -- The intersection* of "f" called on a, and "f" called on b main= getArgs >>= -- get the command line arguments as a list ["firstString", "secondString"] \z-> print.g$z 		-- bind the argument list (z) to print "g" called on z

And there you have it! 193 characters of Haskell code got us a pretty cool program. Here’s a little bit of output:

>tc04.exe "aaabbbbccc" "aabccdcdd"
>"bcc"
>tc04.exe "abcdef" "ghijk"
>tc04.exe "abcdef" "fghijk"
>"f"
>tc04.exe "fhqwhgads" "where are all the dragons?"
>"wh"

Cool! :) -Ben