Mushroom Monster: 3-Line Solution in Julia

The first question in Round 1A of the 2015 Google Code Jam is a great example of a problem that can be solved very easily in just a few lines of Julia.

The question goes like this:

Kaylin loves mushrooms. Put them on her plate and she'll eat them up! In this problem she's eating a plate of mushrooms, and Bartholomew is putting more pieces on her plate.

In this problem, we'll look at how many pieces of mushroom are on her plate at 10-second intervals. Bartholomew could put any non-negative integer number of mushroom pieces down at any time, and the only way they can leave the plate is by being eaten.

Figure out the minimum number of mushrooms that Kaylin could have eaten using two different methods of computation:

1) Assume Kaylin could eat any number of mushroom pieces at any time.

2) Assume that, starting with the first time we look at the plate, Kaylin eats mushrooms at a constant rate whenever there are mushrooms on her plate.

For example, if the input is 10 5 15 5: With the first method, Kaylin must have eaten at least 15 mushroom pieces: first she eats 5, then 10 more are put on her plate, then she eats another 10. There's no way she could have eaten fewer pieces. With the second method, Kaylin must have eaten at least 25 mushroom pieces. We can determine that she must eat mushrooms at a rate of at least 1 piece per second. She starts with 10 pieces on her plate. In the first 10 seconds, she eats 10 pieces, and 5 more are put on her plate. In the next 5 seconds, she eats 5 pieces, then her plate stays empty for 5 seconds, and then Bartholomew puts 15 more pieces on her plate. Then she eats 10 pieces in the last 10 seconds.

The key observations are that for the first method, the solution is simply the sum of the negative differences across Kaylin's plate between each time step. For the second method, you need to determine the time step that has the greatest decrease, and then let Kaylin eat either that number of mushrooms or the number of mushrooms on her plate, whichever is fewer.

A solution in a traditional programming language like C++ or Java takes 10-20 messy lines of for loops. You can download such implementations from the contest scoreboard. However, I present a 3-line solution using Julia (14 lines if you include my comments and I/O).

# Read input
T = int(readline(STDIN))
for t=1:T
    N = int(readline(STDIN))
    M = int(split(readline(STDIN)))

    # Compute solution
    deltas = M[2:end] - M[1:end-1]
    n1 = -sum(deltas[deltas .< 0])
    n2 = sum(min(-minimum(deltas), M[1:end-1]))

    # Print result
    println("Case #$t: $n1 $n2")
end

The implementation can be run from the command line as julia mushroom.jl < mushroom.in where mushroom.in is your input file.

For those who don't know, Julia is a new programming language, originally designed for scientific computing. Its syntax is similar to MATLAB/Octave, but under the hood it uses strong typing to speed up execution and give more flexibility for fast scripting. Like Romeo, I've fallen in love with Julia and don't expect to be switching to a different language any time soon. :)

Installing Cilk Plus on OS X

Cilk Plus is a language extension to C++ that gives convenient parallel programming constructs, like spawn and sync. Installing it on OS X is fairly simple.

These instructions are very similar to those found on the official web site.

Prerequisites

You need to have the Xcode Command Line Tools installed before you can continue. Follow steps 1-3 of this tutorial for more information.

Building

First, I recommend making a clean directory to save your Cilk Plus source, build files, and binaries.

$ cd ~
$ mkdir cilkplus
$ cd cilkplus
$ mkdir build
$ mkdir install

Next, we download the source code. I was not having luck downloading the SVN and Git repos for the Cilk Plus extension. However, downloading a snapshot worked on the first try.

Once you download, you need to extract the tarball. My ref was named gcc-6bca773, but yours might be something slightly different.

$ cd ~/cilkplus
$ tar -zxf gcc-6bca773.tar.gz
$ mv gcc-6bca773 source
$ cd source
$ ./contrib/download_prerequisites

Now you can start the build process. Warning: This involves building the whole freaking GNU C Compiler. It can take several hours.

$ cd ../build
$ ../source/configure --prefix=/absolute/path/to/cilkplus/install --enable-languages="c,c++"
$ make
$ make install

Download Cilk Plus Tools

If you need to use the cilkview and cilkscreen commands, download them from here and save them in your cilkplus directory.

$ cd ~/cilkplus
$ tar -zxf cilktools-mac-004277.tgz
$ mv cilktools-mac-004277 tools

Creating a Cilk Plus Environment

Once the build process is complete, you will have a GCC binary with support for the Cilk Plus extension. However, you probably don't want to use this binary as your default GCC. You can therefore create a custom Bash environment to only use Cilk Plus when you need it.

First, create a file ~/.bashrc.cilk and save it with this contents.

# Use the Cilk Plus gcc binaries
export PATH=/path/to/cilkplus/install/bin:$PATH

# Cilk Tools
export PATH=$PATH:/path/to/cilkplus/tools/bin

# Customize prompt
export PS1="\h:cilk\$ "

You can add the following alias to your ~/.bash_profile file.

alias cilk="bash --rcfile ~/.bashrc.cilk"

Using Cilk Plus

You can now use Cilk Plus.

$ gcc --version
i686-apple-darwin11-llvm-gcc-4.2 (GCC) 4.2.1 (Based on Apple Inc. build 5658) (LLVM build 2336.11.00)
$ cilk
cilk$ gcc --version
gcc (GCC) 4.9.0 20130520 (experimental)

Did this help? Let me know by commenting below.

Pro Tip: Verbose Logging in PhoneGap for iOS

I stumbled upon this tip while browsing the source code of Cordova (aka PhoneGap) when trying to hunt down a bug. There are many log calls scattered throughout the Cordova source code, but they are disabled by default.

  1. Open the following file in your PhoneGap project: platforms/ios/CordovaLib/Classes/CDVAvailability.h
  2. Find the following line. In PhoneGap 3.3 it's at line 88: #define CDV_ENABLE_EXEC_LOGGING 0
  3. Change the 0 to a 1.
  4. Build and run the project. ViolĂ : more details in the device logs!

One particularly useful construct for debugging are lines where it says "Exec: evalling" in the code. Sometimes these calls raise JavaScript errors, but there is no way that I know of to see them (if there is, let me know in the comments). However, if you have weinre installed in your project, you can copy the JavaScript snippet from the PhoneGap log into weinre's JavaScript console and run it to see the error that was raised.

If this helped you, let me know by commenting below!

GitHub – vote539

vote539