Phil Trelford's Array
POKE 36879, 255

Code Golf

August 2, 2014 11:22 by phil

Last month Grant Crofton popped down from Leeds to the F#unctional Londoners meetup at Skills Matter to run a fun hands on code golf session. The idea of code golf is to implement a specific algorithm in the fewest possible characters. This is not the kind of thing you should be doing in enterprise code, but it is fun, and an interesting way of exploring features in a programming language.

On the night we attempted condensed versions of FizzBuzz and 99 bottles of beer, with Ross and I winning the first challenge and Simon & Adrian the second.

FizzBuzz Score99 Bottles Score

Thanks again to Grant for a really fun session.

F# FizzBuzz

A while back I strived to squeeze an F# implementation of FizzBuzz into a tweet, and with white space removed it weighs in at 104 characters (excluding line breaks):

for n=1 to 100 do 
 printfn"%s"
  (match n%3,n%5 with 0,0->"FizzBuzz"|0,_->"Fizz"|_,0->"Buzz"|_,_->string n)

The implementation, although quite clear, requires a fair number of characters for the pattern matching portion.

After some head scratching we came up with the idea of using a lookup to select the string to display:

N %3 N % 5 Index Output
0 0 0 N
>0 0 1 “Fizz”
0 >0 2 “Buzz”
>0 >0 3 “FizzBuzz”

This took the implementation down to 89 characters (without line breaks):

for i=1 to 100 do
 printfn"%s"["FizzBuzz";"Buzz";"Fizz";string i].[sign(i%5)*2+sign(i%3)]

Another trick is to abuse the sign function, to get 1 if the result of the modulus is above 0 and 0 otherwise.

The lookup trick can be used in other languages, and here’s a few examples, just for fun.

VB.Net FizzBuzz

VB.Net has a reputation for being a little verbose, but using the lookup trick it was possible to it get down to 96 characters (excluding line breaks):

For i=1 To 100:
Console.WriteLine({i,"Fizz","Buzz","FizzBuzz"}(-(i Mod 3=0)-(i Mod 5=0)*2))
:Next

In VB.Net true values translate to –1 and false to 0. This allowed me to simply negate the result of i % N = 0 to compute an index.

Python FizzBuzz

Using a similar trick in Python, where true translates to 1 and 0 to false, I was able to get to a very respectable 79 characters (excluding line breaks):

for x in range(1,101):
 print([x,"Fizz","Buzz","FizzBuzz"][(x%3==0)+2*(x%5==0)])

Python’s simple print function also helped to keep the character count down.

Amanda FizzBuzz

Amanda is a variant of David Turner’s quintessential functional programming language Miranda. Amanda runs on Windows, and is used for teaching FP at some universities.

Using a list comprehension it was possible to squeeze in to a mere 67 characters:

[["FizzBuzz","Buzz","Fizz",itoa x]!(min[1,x%3]+min[1,x%5]*2)|x<-[1..100]]

Note: this is cheating a little as we are not explicitly writing to the console.

APL FizzBuzz

APL is a very mature language, dating back to the 1960s, and is still used commercially today. It also wins hands down in code golf with just 54 characters:

⍪{'FizzBuzz' 'Buzz' 'Fizz'⍵[1+(2×1⌊5|⍵)+1⌊3|⍵]}¨⍳100

APL is particularly strong at matrix processing and provides single character representations for common operations:

Notation Name Meaning
B Index generator Creates a list from 1 to B
¨ Each for each loop
Table Produces a one column matrix
B Floor Greatest integer less than or equal to B

Try APL in your browser now.

Challenge

Can you beat the APL implementation of FizzBuzz?

Have fun!


Tags:
Categories: F# | Basic | Python | Haskell | APL
Actions: E-mail | Permalink | Comments (0) | Comment RSSRSS comment feed

Try 10 Programming Languages in 10 minutes

August 31, 2013 10:47 by phil

There are a lot of interesting programming languages out there, but downloading and setting up the environment can be very time consuming when you just want to try one out. The good news is that you can try out many languages in your browser straight away, often with tutorials which guide you through the basics.

Following the pattern of 7 languages in 7 weeks book, here’s a somewhat abridged version.

Dynamic Languages

Fed up of long compile times, want a lightweight environment for scripting? Dynamic languages could be your new friend.

Try Lua

Lua is a lightweight dynamic language with excellent coroutine support and a simple C API making it hugely popular in video gaming for scripting. Have fun with game engines like LÖVE and Marmalade Quick.

Try Clojure

Clojure is the brainchild of the hugely charismatic speaker Rich Hickey, it is a descendant of one of the earliest programming languages LISP. There’s a really rich community around Clojure, one of my favourite projects is Sam Aaron’s Overtone live coding audio environment.

Try R (quick registration required)

R is a free environment for statistical computing and graphics, with a huge range of user-submitted packages. Ever wondered how to draw an egg?

Functional Languages

Aspects of functional programming have permeated most mainstream languages from C++ to VB. However to really appreciate the expressiveness of the functional approach a functional-first language is required.

Try Erlang

Erlang is a really interesting language for building fault tolerant concurrent systems. It also has great pattern matching capabilities. It has many industrial applications and tools including the RabbitMQ messaging system and the distribute database Riak.

Try Haskell

Haskell is heavily based on the Miranda programming language which was taught in British universities in the 80s and 90s. Haskell added Monads and Type Classes, and is still taught in a few universities, it is also still quite popular in academic research.

Try OCaml

OCaml like Miranda is based on the ML programming language adding object-oriented constructs. F# is based on OCaml, there is even a compatibility mode. OCaml still has industrial application, for example at Jane Street Capital and XenSource.

Web Languages

There’s a plethora of languages that compile to JavaScript languages out there. Also worth a look are the new features in JavaScript itself, see Brendan Eich’s talk at Strangeloop last year on the The State of JavaScript. Here’s 3 *Script languages I find particularly interesting:

LiveScript

LiveScript is an indirect descendant of CoffeeScript with features to assist functional programming like pattern matching and function composition. Check out 10 LiveScript one liners to impress your friends.

Try Elm

Elm is a functional reactive language for creating highly interactive programs, including games. Reactive programming is an interesting direction and I think languages designed specifically for this are worth investigating.

PogoScript

Unfortunately there’s currently no online editor for this one, but there is a command line REPL. PogoScript is DSL friendly allowing white space in function names.

Esoteric Languages

Esoteric languages tend to be write-only, a bit like Perl but just for fun.

Try Brainfuck

Brainfuck is the Rubik’s cube of programming languages. I built the site last year with the interpreter written in plain old JavaScript, check out the fib sample.

Browser IDEs

With so many programming language experimentation environments available online, the next logical step is to host the IDE there. Imagine not having to wait 4 hours for Visual Studio to install.

Cloud 9 is an online environment for creating Node.js apps, pulling together sets of relevant packages. Tools like Sploder let you build games online.

The Try F# site offers arguably the most extensive online learning features of any language. Cloud Tsunami IDE also offers a rich online development experience for F#. In the near future CloudSharper will offer an online IDE experience for developing web applications with F# using WebSharper,

Scaling up

Once you’ve completed some basic tasks in a new language you’ll want to move on to slightly larger tasks. I like to use exercises from the coding Kata Catalogue like FizzBuzz, the Game of Life and Minesweeper.

Some people enjoy going through the Project Euler problems, others have their own hello world applications. For Martin Trojer it’s a Scheme interpreter and Luke Hoban often writes a Ray Tracer.

I’d also recommend joining a local meetup group. The London Scala meetup have a coding dojo every month and the F#unctional Londoners meetup have hands on session in the middle the month, the next one is on Machine Learning.

Programming language books that include questions at the end of sections are a good way to practice what you’ve learned but are few and far between. The recent Functional Programming with F# book is an excellent example of what can be done with questions at the end of each chapter.

While the basics of a language can be picked up in a few hours, expect it to take a few weeks before you’re productive and at least a few months before you start to gain mastery.

Want to write your own language? Pete Sestoft’s Programming Language Concepts book offers a good introduction to the subject.


Tags:
Categories: F# | Lua | JavaScript | Clojure | Erlang | Haskell | Scala
Actions: E-mail | Permalink | Comments (3) | Comment RSSRSS comment feed

Functional Fizz Buzz

March 25, 2012 10:23 by phil

Fizz-Buzz or Bizz Buzz is a word game, popularized by Jeff Atwood in the article:

Why Can’t Programmers… Program?

The game has been turned into a simple programming test:

Write a program that prints the numbers from 1 to 100. But for multiples of 3 print "Fizz" instead of the number and for the multiples of 5 print "Buzz". For numbers which are multiples of both 3 and 5 print "FizzBuzz".

If you’re involved in hiring programmers then the article is probably worth a read.

This kind of problem can be expressed very concisely in functional programming languages to the point where the code fits in a tweet.

Haskell

Last month Calvin Bottoms posted an article describing and implementation of Fizz-Buzz in Haskell expressed in a mere 78 characters:

[max(show x)(concat[n|(f,n)<-[(3,"Fizz"),(5,"Buzz")],mod x f==0])|x<-[1..100]]

Higher order functions and list comprehensions (a feature taken from Miranda) make this very terse, but also a little impenetrable.

F#

Rather more verbose (122 characters) but perhaps a little more readable:

for n in 1..100 do printfn "%s" <| match n%3, n%5 with 
0,0 -> "FizzBuzz" | 0,_ -> "Fizz" | _,0 -> "Buzz" | _,_ -> string n

Pattern matching makes the various states relatively obvious.

Clojure

Martin Trojer sent over this quite elegant Clojure implementation via Twitter:

(map #(cond (zero? (mod % 15)) "FizzBuzz" (zero? (mod % 3)) "Fizz" 
(zero? (mod % 5)) "Buzz" :else %) (range 1 101))

Testing for “FizzBuzz” using modulus 15 helps reduce the character count.

Erlang

I’ve been playing with Erlang recently and Fizz-Buzz is my new “Hello World” app. This was my first effort:

f(101)->ok;
f(X)->Y=case{X rem 3,X rem 5}of{0,0}->fizzbuzz;{0,_}->fizz;{_,0}->buzz;
{_,_}->X end,io:format("~w~n",[Y]),f(X+1). 

Erlang doesn’t have a for loop construct built-in so I resorted to recursion instead.

That said you can achieve the same thing using the lists module seq and foreach functions:

lists:foreach(fun(X)->io:format("~w~n",[case{X rem 3,X rem 5}of{0,0}->fizzbuzz;
{0,_}->fizz;{_,0}->buzz;{_,_}->X end])end,lists:seq(1,100)).

Next?

Is Fizz-Buzz the new “Hello World”?

I think it might be, despite Jeff’s protestations, take a peek at Fizz-Buzz on Rosetta Code.


Tags:
Categories: Twitter | Haskell | F# | Erlang | Clojure
Actions: E-mail | Permalink | Comments (15) | Comment RSSRSS comment feed