Search

September 30, 2012

An Io Guessing Game

So when I get the chance I am working through Bruce Tate’s Seven Languages in Seven Weeks (it might end up being seven years in my case) and commenting on it when the mood strikes. I am currently working through the exercises for Io Day 2 and today I was contemplating the final exercise.

In this task, Tate asks us to write a program that will generate a random number between 1 and 100 and then prompt the user to guess it within ten guesses. The user is given feedback in the form of hotter or colder. The task itself was relatively straightforward after discovering how to read input from the console:

GuessMe := Object clone do(
    min ::= 1
    max ::= 100
    guessLimit ::= 10
    value ::= nil
    lastGuess ::= nil
    guessesLeft ::= 0

    start := method(
        reset
        value = Random value(min, max+1) floor
        guessesLeft = guessLimit
    )

    reset := method(
        value = nil
        lastGuess = nil
        guessesLeft = 0
    )

    guess := method(guess,
        guessesLeft = guessesLeft - 1
        oldGuess := lastGuess
        lastGuess = guess
        if (guess == value) then (return "Done")
        if (oldGuess == nil) then (return "Guess again")
        lastDelta := (value-oldGuess) abs
        delta := (value-guess) abs
        if (delta == lastDelta) then (
            return "Same temperature"
        ) elseif (delta < lastDelta) then (
            return "Hotter"
        ) else (
            return "Colder"
        )
    )

    interactive := method(
        if (value == nil) then (start)
        stdin := File standardInput
        while (guessesLeft > 0,
            in := stdin readLine asNumber
            result := guess(in)
            result println
            if (result == "Done") then (break)
        )
        if (guessesLeft <= 0) then (
            ("No more guesses, the value was " .. value) println
        )
        reset
    )
)

If you want to try it, save the above in GuessMe.io and then run the interpreter in the same directory and use the command GuessMe clone interactive.

So what really intrigued me about this assignment was not the exercise itself but the resulting game. It gets obvious pretty fast that the standard binary search solution for guessing games would not work; we need to tweak it somehow. (This is probably an elementary exercise in an algorithms course but it has been a while so it was a fun exercise for me.)

The solution comes from literally thinking outside the box. That is, you need to realize that you can guess numbers outside the range of possible values. So, let’s say that you start by guessing 1 and that’s not it. What should your next guess be? At this point you know the value is between 2 and 100 inclusive, i.e. [2,100]. You’d like to cut your range in half, that is, determine if the value is in the range [2,51] or the range [52,100]. What’s the proper guess?

We want to make our next guess further away from 51 than 1 is. At the same time, it should be closer to 52 than 1 is. In this case the guess is 102, since 51 - 1 = 50 = 102 - 52. Now if the result is hotter, the new range is [52,100]. If the result of the guess is colder, the new range is [2,51].

Now that we’ve seen how we can cut our options in half on every guess (following the first), we can start to create an algorithm. Suppose the range is [x,y] and the last guess is L. First, we find the bifurcation point a = floor((x+y)/2). So we will end up with either [x,a] or [a+1,y].

What should the guess g be? If L is less than a then g will be greater than a and we want g - (a+1) = a - L. This becomes g = 2a - L + 1. If L was greater than a then we want a - g = L - (a+1) which also reduces to g = 2a - L + 1.

Now we have enough to write a prototype to solve our game:

Guesser := Object clone do(
    min ::= 0
    max ::= 0
    guess ::= 0
    result ::= nil

    report := method(
        "Guessed #{guess}: #{result}; [#{min},#{max}]" interpolate println
    )

    guessIt := method(guessMe,
        guessMe start
        min = guessMe min
        max = guessMe max

        // Get through the first guess, it is special
        guess = min
        result = guessMe guess(guess)
        // Assume min wasn't it, no harm if it was
        last := min
        min = min + 1
        report

        while (result != "Done",
            if (guessMe guessesLeft <= 0) then (
                "No guesses left, the value was #{guessMe value}" interpolate println
                break
            )
            avg := ((min+max)/2) floor
            guess = if(min==max, min, 2*avg - last + 1)
            result = guessMe guess(guess)
            if (result == "Colder") then (
                if (guess < last) then (
                    min = avg + 1
                ) else ( // last < guess
                    max = avg
                )
            ) elseif (result == "Hotter") then (
                if (guess < last) then (
                    max = avg
                ) else ( // last < guess
                    min = avg + 1
                )
            ) elseif (result != "Done") then (
                "Did not understand result" println
                report
                break
            )
            report
            last = guess
        )
    )
)

Here’s the Guesser in action:

Io> gm := GuessMe clone
==>  GuessMe_0xa18e3b8:

Io> guesser := Guesser clone
==>  Guesser_0xa1756d8:

Io> guesser guessIt(gm)
Guessed 1: Guess again; [2,100]
Guessed 102: Colder; [2,51]
Guessed -49: Hotter; [2,26]
Guessed 78: Hotter; [15,26]
Guessed -37: Colder; [21,26]
Guessed 84: Hotter; [24,26]
Guessed -33: Hotter; [24,25]
Guessed 82: Colder; [24,24]
Guessed 24: Done; [24,24]
==> 24

If you enjoyed this post, here are some exercises you may want to think about:

  1. What happens if we start our algorithm with 50 instead of 1?
  2. Will the algorithm always be able to find the value within 10 guesses (when the range is [1,100]? What’s the largest range it can guarantee finding the answer over given 10 guesses? Given n guesses?
  3. Can the algorithm be improved upon?
  4. What if the game told you if you were hotter or colder than all of your previous guesses? How would you change the algorithm to use less guesses?

September 26, 2012

OS-specific ANT properties

The ANT build tool for Java does a pretty decent job of abstracting away OS concerns from your build script. E.g., file paths can always be represented using the / separator and there are tasks for all the typical file system and build operations.

However, once in while you may find yourself in a situation where you need ANT to behave differently based on the operating system. In my case, I needed to specify path to the dot executable within graphviz, a graph drawing tool used by the Hibernate tools ANT package. Rather than torture my environment, I figured I would set a property based on the OS:

<target name="schema-doc">
    <property name="hibernate.tool.dot.options"
              value="-Gsplines=true -Edecorate" />
    <condition property="hibernate.tool.dot.executable" value="/usr/bin/fdp">
        <os family="unix" />
    </condition>
    <condition property="hibernate.tool.dot.executable"
               value="C:/graphviz/bin/fdp.exe">
        <os family="windows" />
    </condition>
    <mkdir dir="${hibernate.tool.target.dir}/doc" />
    <delete>
        <fileset dir="${hibernate.tool.target.dir}/doc" />
    </delete>
    <hibernatetool destdir="${hibernate.tool.target.dir}/doc">
        <configuration configurationfile="${basedir}/hibernate-tool.cfg.xml">
            <fileset dir="${src}" includes="**/*.hbm.xml" />
        </configuration>
        <classpath refid="hibernate.classpath" />
        <hbm2doc>
            <property key="dot.executable"
                      value="${hibernate.tool.dot.executable} ${hibernate.tool.dot.options}" />
        </hbm2doc>
    </hibernatetool>
</target>

The key portion here occurs near the top, using the <condition> directive. Here I’ve placed in inside the <target>, but you can use it outside of a <target> as well. The <os> element within the <condition> allows you test based on properties of the underlying operating system. I’ve chosen to base the test on family, but there are also name, version and arch tests as well.

(As a bonus tip here, I’ve also shown you how to pass extra arguments to graphviz when running it within Hibernate Tools.)

Now this is all well and good for one property, which is the situation I was dealing with, but what if you have a whole mess of properties to deal with? Making multiple <condition> tags for each property and OS combination will get old real fast. In that case, we use the built-in properties ANT supplies:

<property file="build-${os.name}-${os.version}-${os.arch}.properties" />
<property file="build-${os.name}-${os.version}.properties" />
<property file="build-${os.name}.properties" />
<property file="build.properties" />

Note the order here. Recall that once a property is defined within ANT it cannot be changed. So put the defaults in build.properties and then override them in the more specific properties files that are loaded first. Of course, you may not need to go all the way to the OS architecture level, but now you know how.

September 22, 2012

Io Gotcha

As you are probably aware, I am working my way through Seven Languages in Seven Days by Bruce Tate. (And if you have ever googled basic questions on the Io language, you will know that I am not the first person to have this idea.) In any case, I am on Day of Io, but before I get to anything specific there, I wanted to share a gotcha of Io that I encountered.

Coming from an object-oriented background (like Java) you might find yourself writing code like the following:

Gotcha := Object clone do(
    conspirators ::= list()

    conspire := method(c,
        conspirators push(c)
        return self
    )
)

walter := Gotcha clone
walter conspire("jesse")
("walter: " .. walter conspirators) println

gus := Gotcha clone
gus conspire("mike")
gus conspire("victor")

("walter: " .. walter conspirators) println
("   gus: " .. gus conspirators) println

Everything seems fine, we initialize a list and then start adding elements to it. But here is the output:

walter: list(jesse)
walter: list(jesse, mike, victor)
   gus: list(jesse, mike, victor)

Somehow in the process of creating gus and adding his conspirators has caused the list of conspirators for walt to grow. What is happening here is that conspirators is a slot on Gotcha that is never overridden by the clones walt and gus. So they are all sharing the same conspirator list. (Fans of Breaking Bad will realize that this situation cannot be allowed!)

The solution (well, one solution, there are probably others) is to use the init method to set the conspirators slot:

Fixed := Object clone do(
    conspirators ::= nil

    init := method(
        setConspirators(list())
    )

    conspire := method(c,
        conspirators push(c)
        return self
    )
)

walter := Fixed clone
walter conspire("jesse")
("walter: " .. walter conspirators) println

gus := Fixed clone
gus conspire("mike")
gus conspire("victor")

("walter: " .. walter conspirators) println
("   gus: " .. gus conspirators) println

Now walt and gus maintain a separate list of conspirators (as Vince Gilligan intended):

walter: list(jesse)
walter: list(jesse)
   gus: list(mike, victor)

If you find yourself making these kinds of gaffes, re-read the Io style guide at http://en.wikibooks.org/wiki/Io_Programming/Io_Style_Guide.

September 16, 2012

Well I am back to reading Seven Languages in Seven Days by Bruce Tate and am taking on the chapter on Io. If you are not familiar, Io is a prototype-based language like JavaScript. Since I typically work on the server-side and only dabble in JavaScript and HTML, I am looking forward to seeing how learning Io can reflect on my knowledge of JavaScript.

The first thing to grab my attention is how slots on clones are handled. You’ll notice that the Car created from the Vehicle clone does not have a description slot listed when the slotNames message is sent to it. Also, Tate indicates that when you send the description message to Car, the message is forwarded to the prototype, Vehicle. Let’s see how that shakes out:

Io 20110905
Io> Vehicle := Object clone
==>  Vehicle_0x9be5758:
  type             = "Vehicle"

Io> Vehicle description := "Something to take you far away"
==> Something to take you far away
Io> Vehicle slotNames
==> list(description, type)
Io> Car := Vehicle clone
==>  Car_0x9c35590:
  type             = "Car"

Io> Car slotNames
==> list(type)
Io> Car description
==> Something to take you far away
Io> Vehicle description = "Something that can move you"
==> Something that can move you
Io> Car description
==> Something that can move you

Interesting, changing the description slot on Vehicle is reflected when the description message is sent to Car. But apparently it can be overridden:

Io> Car description = "Something else entirely"
==> Something else entirely
Io> Car description
==> Something else entirely
Io> Vehicle description
==> Something that can move you
Io>

Interestingly you can use the weaker = assignment even though in one sense the description slot had not been defined on Car.

Here’s another question: can we clone non-types and what is the behavior? In turns out the behavior is pretty much the same, except that the prototype is listed as the prototype of the cloned object:

Io> anotherFerrari := ferrari clone
==>  Car_0x9b61418:

Io> ferrari slotNames
==> list()
Io> ferrari color := "red"
==> red
Io> ferrari color
==> red
Io> anotherFerrari color
==> red
Io> Car color

  Exception: Car does not respond to 'color'
  ---------
  Car color                            Command Line 1

Io> anotherFerrari proto
==>  Car_0x9cb92d0:
  color            = "red"

Moving on to the exercises, most are straightforward. However, following my nose lead me to an interesting place when trying to execute the code in a slot given its name.

Io 20110905
Io> x := Object clone
==>  Object_0x9f878b0:

Io> x yzzy := method("plugh" println; return self)
==> method(
    "plugh" println; return self
)
Io> x yzzy
plugh
==>  Object_0x9f878b0:
  yzzy             = method(...)

Io> x getSlot("yzzy")
==> method(
    "plugh" println; return self
)
Io> x getSlot("yzzy") type
==> Block
Io> x getSlot("yzzy") call
plugh
==>  Object_0x9f13028:
  Lobby            = Object_0x9f13028
  Protos           = Object_0x9f12f58
  _                = Object_0x9f13028
  exit             = method(...)
  forward          = method(...)
  set_             = method(...)
  x                = Object_0x9f878b0

Io> x perform("yzzy")
plugh
==>  Object_0x9f878b0:
  yzzy             = method(...)

Initially I tried to get to the code via getSlot. While this worked, I ended up with a Block and then tried sending the call message to it. The code was executed, but the right thing was not returned. Somehow I ended up with the Lobby being returned instead of x. It turned out the better approach was to use the perform method on Object. Now the correct value is returned.

September 3, 2012

Absent Code

I recently hit an error I had never seen before:

Caused by: java.lang.ClassFormatError: Absent Code attribute in method that is
        not native or abstract in class file javax/servlet/http/HttpCookie

A little research and I discovered that some versions of the javaee.jar contain essentially just the method signatures without any bodies. This is fine for compiling against but can cause issues when running JUnit, i.e. unit tests.

The solution turned out to be to use a JEE jar from an application server. I use JBoss, but they seemed to have the jar scattered all over the place so I turned to GlassFish. GlassFish didn’t exactly give me one-stop shopping either but it was easier to put together the implementation jar than with JBoss.

If you don’t need the jar in any particular place you can just add it to your classpath. Otherwise if you are moving it, note that the jar itself contains nothing but a manifest pointing to other jars. Make sure you copy the other jars and preserve the directory structure.

Big hat tip to mkyong at http://www.mkyong.com/ who did the leg work for me on this one:

http://www.mkyong.com/hibernate/java-lang-classformaterror-absent-code-attribute-in-method-that-is-not-native-or-abstract-in-class-file/