My first real code golf program!

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 it was one of the shorter Haskell solutions!

So, 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
adeaabbbbccc aabccdedcdd -> 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

view raw tc04.hs hosted with ❤ by GitHub

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

view raw tc04Comments.hs hosted with ❤ by GitHub

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