Angel \”Java\” Lopez on Blog

May 10, 2013

TDD Kata (4): Lawnmover

Previous Post
Next Post

In the previous post, I commented about by experience at pre-round at Google Code Jam.

The exercise B was Lawnmover:

https://code.google.com/codejam/contest/2270488/dashboard#s=p1

Problem

Alice and Bob have a lawn in front of their house, shaped like an N metre by M metre rectangle. Each year, they try to cut the lawn in some interesting pattern. They used to do their cutting with shears, which was very time-consuming; but now they have a new automatic lawnmower with multiple settings, and they want to try it out.

The new lawnmower has a height setting – you can set it to any height h between 1 and 100 millimetres, and it will cut all the grass higher than h it encounters to height h. You run it by entering the lawn at any part of the edge of the lawn; then the lawnmower goes in a straight line, perpendicular to the edge of the lawn it entered, cutting grass in a swath 1m wide, until it exits the lawn on the other side. The lawnmower’s height can be set only when it is not on the lawn.

Alice and Bob have a number of various patterns of grass that they could have on their lawn. For each of those, they want to know whether it’s possible to cut the grass into this pattern with their new lawnmower. Each pattern is described by specifying the height of the grass on each 1m x 1m square of the lawn.

The grass is initially 100mm high on the whole lawn.

I solved it, see:

https://github.com/ajlopez/TddOnTheRocks/tree/master/Lawnmover

As usual, the commit history by test:

https://github.com/ajlopez/TddOnTheRocks/commits/master/Lawnmover

I could solve the first small set provided by Google. But I failed with the big set, because my algorithm was not efficient enough. The big set should be solved in 8 minutes, and if you cannot, there is no other chance. My initial algorithm (see comments) attacked the largest number in cells. My second algorithm switched to start with the minimal numbers (my first guess was that both algorithms had the same time, but I was wrong). I learnt: some problems in Google are hard to test by hand, we don’t have the use case (input and expected output), that is the main difficult.

More katas are comming.

Keep tuned!

Angel “Java” Lopez
http://www.ajlopez.com
http://twitter.com/ajlopez

7 Comments »

  1. […] Previous Post Next Post […]

    Pingback by TDD Kata (3): Tic-Tac-Toe-Tomek | Angel "Java" Lopez on Blog — May 10, 2013 @ 9:53 am

  2. […] TDD Kata (4): Lawnmover […]

    Pingback by TDD Kata (4): Lawnmover | MVPs de LATAM — May 16, 2013 @ 5:22 pm

  3. […] Previous Post […]

    Pingback by TDD Kata (5): Tree Search | Angel "Java" Lopez on Blog — June 30, 2013 @ 3:29 pm

  4. […] Previous Post […]

    Pingback by TDD Kata (5): Tree Search | MVPs de LATAM — July 2, 2013 @ 3:04 pm

  5. For all those in a position to buy your little league cleats remember to experience any bottom
    suitably sort of to offer absolute best compliment. It is
    having a huge variety of synthetic lawns to make your garden more lively, healthy as well as natural like a normal garden.
    The Rhinos, like the Shadow were, are the big fish in a small pond and
    that could once again be the case for men’s soccer in Spokane given the right operation.

    Comment by artifical grass — June 28, 2014 @ 10:53 pm

  6. The 2013 FINA World Aquatics Championships are helping Arena swimwear take its public relations strategy to the next level.
    If you have a small bust, choosing a suit with decoration or padding in the
    bust area will help balance your body. After a few years of
    the bikini as the fashionable swimsuit, one pieces are making a comeback.

    Comment by http://www.agdfh.com/archive/index.php?thread-19425.html — July 13, 2014 @ 11:11 am

  7. In my office, I try to help children take ownership of their
    feelings as well as their coping strategies, so that they in essence, become the
    captain of their own ship. Obsessive Compulsive Disorder (OCD) may take the form of excessive and intrusive obsessive thoughts, images or impulses that are almost impossible to ignore or
    stop, even if the individual understands that they are senseless or unfounded.

    He will never offer the solution to your problems, he’ll rather guide you to
    get to the conclusion on your own and make a decision yourself If he interprets
    a situation or gives his own opinion, he’ll point
    out loud and clear that it’s just his opinion, and that you can, but don’t have to, agree with it
    He leaves you a freedom of choice in every situation and respects your free will He
    doesn’t encourage an addictive relationship, and if that kind of relationship starts to
    emerge from side of the client, he’ll talk openly about that problem and act with a goal of his complete independency
    He won’t comment behaviours and personalities of other people involved in a problem witha goal to pander you
    and say you’re the one who’s right.

    Comment by www.youtube.com — July 24, 2014 @ 12:28 am


RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

The Shocking Blue Green Theme. Blog at WordPress.com.

Follow

Get every new post delivered to your Inbox.

Join 66 other followers

%d bloggers like this: