Google Code Jam 2011... lots of fun... so little time

I participated in the Qualifying Round of Code Jam 2011.
Knowing, that on a weekend the 4 Kids wouldn't leave me alone during the day, i waited for the start at 1am and solved Problem B until ~2.30am... small dataset was correct, so i figured the large one would be ok as well... turned out i was wrong ... more later.

During the day i kept thinking about Problem C and came up with a brute force solution... fine with max. 15 candies (small dataset)... but with 1000 it would take around 10^280 times the age of the universe (says Wofram Alpha)... just a tiny little bit too long for the 8 minutes i had for the large dataset...
With time running out (15 minutes to the deadline) i realized, that the solution was quite simple...
Patricks method of adding is simply an XOR, that was obvious...
I realized, that the nature of XOR is, that when summing two equal piles... the result must be 0!
In turn this means that removing any candy from the total pile that has a XOR sum of 0, results in the rest of the pile having a sum of the value of the candy just removed...
Its that easy ;)... just remove one candy with the lowest value, and Patrick is happy... and Sean has the maximum candies ;)
Coding that was quick and i submitted my solution 5 minutes before the deadline... for a total of 35 points and the qualification to Round 1 :-) (in 9007th place...)

In the meantime i also found out, why my solution to Problem B was incorrect... i implemented the lookup of combinations not via a HashMap or similar, but doing array accesses with the char value (this way i only needed to put the combination into the array once, since QA and AQ have the same sum... problem was, that it is also possible to combine the same element, i.e. QQ, and i did not check wether both elements were "base elements"... non-base elements had a value of zero... so looking up any base element and a non-base element could find a combination if the base-elements successor had a combination with itself. This is fixed in the github code for those interested...
So the correct solution for small dataset in Problem B was... well... pure luck :-D

All code can be found here: https://github.com/phueper/CodeJam2011
Much better explanations of the Problems an Solutions can be found here: Contest Analysis

That was a lot of fun... let's see wether i have time to compete in Round 1...

Patty

P.S. it amazes me, that the winners of the qualifying solved all 4 problems in ~40 minutes... that is really impressively fast... it took me somewhere around 3-4 hours thinking about and solving 2 problems... i guess i need to practice a little bit :-)

Scala Actors in Android

I experimented with scala Actors in android today.

It all works very nice, except that the actors classes are not in the scala-android library, but including the scala-library.jar and having proguard take care of removing unnecessary classes worked very well...

The actors work, only problem is that updates to Views should only be made from the main UI thread, so i added a function to allow to append Messages to TextViews by post()ing them...

Adding an click listener to a button:

// converter for anonymous func to OnClickListener
implicit def func2OnClickListener(func: (View)=>Unit):OnClickListener = {
new OnClickListener() {
def onClick(v:View) = func.apply(v)
}
}

button.setOnClickListener(
(v:View)=>{
textView.append("click from thread: " + Thread.currentThread().getId() + "\n");
buttonActor!"msg";
scrollViewUpdate(scrollView)
})

The ClickListener is outputting some code to the textView, and then sends "msg" to a actor... the Actor class and the messages used to post() functionality to the Views looks like this:

/* since views should only be accessed by the UI Thread, i use this method from ButtonActor to post the message to the TextView */
def textViewAppend(textView:TextView, msg:String) {
textView.post(()=>{
textView.append(msg)
() // must return Unit
})
}

def scrollViewUpdate(scrollView:ScrollView) {
/* post function for scrollView, after updates, we want to scroll to bottom... */
scrollView.post(()=>{
scrollView.fullScroll(View.FOCUS_DOWN)
() // must return Unit
})
}

class ButtonActor extends Actor {
private val textView:TextView = findViewById(R.id.TextView01)
private val scrollView:ScrollView = findViewById(R.id.ScrollView01)
private val spinner:Spinner = findViewById(R.id.Spinner01)
def act() {
loop {
receive {
case msg =>
val textMsg = "msg received: " + msg.toString() + " from thread: " + Thread.currentThread().getId() + "\n";
textViewAppend(textView, textMsg);scrollViewUpdate(scrollView);
}
}
}
}

See it all here:

http://github.com/phueper/AndroidScalaAntTest/

Cheers, Patty

Generics in implicit conversion functions

Playing with scala i started using implicit conversion classes... e.g. to use

findViewById

in the Android SDK:

val textView:TextView = findViewById(R.id.TextView01)

now findViewById returns a android.view.View (the base class of all views). In Java we would cast to a TextView, which can be done expicitly in scala using asInstanceOf[]. However, using implicit conversion functions is somewhat easier to read once understood...
So this is my first version of the conversion function:

implicit def textViewConverter(v:View):TextView =
   { v.asInstanceOf[TextView] }

If scala now finds a View being assigned to a TextView variable, it will try to find a conversion funtion, that converts from View to TextView and apply it "automagically".
Now this would mean writing one conversion function for every View type i am using... after having written the third conversion function i thought that there must be a better way... and there is! Using generics i can write the following conversion function:

implicit def viewConverter[T](v:View):T = {v.asInstanceOf[T] }

This will convert from View to any other type!

Now it would be neat if i could restrict T to be only of types inside android.widget... but i am not sure wether that can be done...

Cheers, Patty

First Steps with Android and Scala

I am trying to learn scala and i would like to write some apps for my Android phone...

So i thought i will combine the two.. i started to learn about writing an android app using scala...

I read some blogs on the web and pulling together ideas from different source (android.com / proguard.sf.net, http://chneukirchen.org/blog/archive/2009/04/programming-for-android-with-scala.html) i created my first Hello World Android App written in scala:

I published the git tree here:

http://github.com/phueper/AndroidScalaAntTest

It contains all steps from creating the Eclipse project, transferring it to an ant based project, adding scala and proguard to creating Hello World in scala...

Next steps:

- run the app on my G1, instead of the Android Emulator
- learn more about debugging...
- a real/useful Android application... i have some ideas of apps that i would like to use...

Cheers, Patty