Scala And Android Were Made For Each Other, Part 2

This is the second in a 2 part post.  To read the first post, Click Here.

Now that we've gone over the Service in our application, lets review the Activity.  Just in case you haven't read part 1, here's a 10 second recap:

We're building a countdown timer for the specific case of tracking a Pomodoro, a 25 minute block of time.  For more info, visit the Pomodoro Technique site, or maybe, order Pomodoro Technique Illustrated...

We've reviewed the Service and seen how the Scala language allows us to reduce a lot of boilerplate code.  Now lets look at the Activity:

1:  class ScalaDoro extends FragmentActivity with Actionable with MessageReceiver {  
2:   /** Messenger for communicating with service. */  
3:   var mService: Messenger = null  
4:   /** Flag indicating whether we have called bind on the service. */  
5:   var mIsBound: Boolean = false  
6:   var running = false  
7:   override def onCreate(savedInstanceState: Bundle) {  
8:    super.onCreate(savedInstanceState)  
9:    setContentView(R.layout.activity_main)  
10:    spawn {  
11:     startService(new Intent(ScalaDoro.this, classOf[BackgroundTimer]))  
12:    }  
13:    if (savedInstanceState != null) {  
14:     running = savedInstanceState.getBoolean("running", false)  
15:     val timerString = savedInstanceState.getString("timerText")  
16:     getSupportFragmentManager().findFragmentById(R.id.timer).asInstanceOf[CountdownTimerFragment].updateTime(if (timerString != null) timerString else "")  
17:    }  
18:    val button = findViewById(R.id.foo_button).asInstanceOf[Button]  
19:    //awesome lack of boilerplate code...  
20:    if (!running) {  
21:     button.setOnClickListener(toOnClickListener(startClickListener))  
22:     button.setText(R.string.start)  
23:    } else {  
24:     button.setOnClickListener(toOnClickListener(stopClickLister))  
25:     button.setText(R.string.stop)  
26:    }  
27:    val donate = findViewById(R.id.donate).asInstanceOf[TextView]  
28:    if(donate != null) {  
29:     donate.setText(Html.fromHtml("<a href='https://www.paypal.com/cgi-bin/webscr?cmd=_s-xclick&hosted_button_id=2RYS72VS6BJAA'>Is this useful to you? Donate via PayPal.</a>"));  
30:     donate.setMovementMethod(LinkMovementMethod.getInstance());  
31:    }  
32:   }  
33:   override def onSaveInstanceState(bundle: Bundle) = {  
34:    bundle.putBoolean("running", running)  
35:    bundle.putString("timerText", getSupportFragmentManager().findFragmentById(R.id.timer).asInstanceOf[CountdownTimerFragment].getTime.toString())  
36:   }  
37:   def onMessage(m: Message) = {  
38:    Log.i("BAA", "Message in Activity")  
39:    m.what match {  
40:     case BackgroundTimer.TICK =>  
41:      val textFragment = getSupportFragmentManager().findFragmentById(R.id.timer).asInstanceOf[CountdownTimerFragment]  
42:      if (textFragment != null) {  
43:       runOnUiThread {  
44:        textFragment.updateTime(m.obj.asInstanceOf[String])  
45:       }  
46:      }  
47:     case BackgroundTimer.STOPPED =>  
48:      val button = findViewById(R.id.foo_button).asInstanceOf[Button]  
49:      button.setOnClickListener(toOnClickListener(startClickListener))  
50:      button.setText(R.string.start)  
51:    }  
52:   }  
53:   def stopClickLister(v: View): Unit = {  
54:    val button = findViewById(R.id.foo_button).asInstanceOf[Button]  
55:    try {  
56:     running = false  
57:     // Give it some value as an example.  
58:     Log.i("BAA", "Sent message")  
59:     button.setOnClickListener(toOnClickListener(startClickListener))  
60:     val msg = Message.obtain(null, BackgroundTimer.STOP)  
61:     msg.replyTo = mMessenger  
62:     mService.send(msg);  
63:    } catch {  
64:     case ex: Exception => Log.i("BAA", ex.getMessage())  
65:    }  
66:    button.setText(R.string.start)  
67:   }  
68:   def startClickListener(v: View): Unit = {  
69:    val button = findViewById(R.id.foo_button).asInstanceOf[Button]  
70:    try {  
71:     // Give it some value as an example.  
72:     button.setOnClickListener(toOnClickListener(stopClickLister))  
73:     running = true  
74:     val msg = Message.obtain(null,  
75:      BackgroundTimer.START)  
76:     msg.replyTo = mMessenger  
77:     mService.send(msg);  
78:     Log.i("BAA", "Sent message")  
79:    } catch {  
80:     case ex: Exception => Log.i("BAA", ex.getMessage())  
81:    }  
82:    button.setText(R.string.stop)  
83:   }  
84:   //binding code..  
85:   val mConnection = new ServiceConnection() {  
86:    override def onServiceConnected(className: ComponentName, service: IBinder) = {  
87:     Log.i("BAA", "OnServiceConnected called")  
88:     // This is called when the connection with the service has been  
89:     // established, giving us the service object we can use to  
90:     // interact with the service. We are communicating with our  
91:     // service through an IDL interface, so get a client-side  
92:     // representation of that from the raw service object.  
93:     mService = new Messenger(service)  
94:     // We want to monitor the service for as long as we are  
95:     // connected to it.  
96:     try {  
97:      // Register to receive the notifications  
98:      val msg = Message.obtain(null,  
99:       BackgroundTimer.REGISTER)  
100:      msg.replyTo = mMessenger  
101:      mService.send(msg)  
102:      //Now get status  
103:      val status = Message.obtain(null, BackgroundTimer.STATUS)  
104:      status.replyTo = mMessenger  
105:      mService.send(status);  
106:      Log.i("BAA", "Sent message")  
107:     } catch {  
108:      case ex: Exception => Log.i("BAA", ex.getMessage())  
109:     }  
110:     mIsBound = true;  
111:    }  
112:    def onServiceDisconnected(className: ComponentName) = {  
113:     // This is called when the connection with the service has been  
114:     // unexpectedly disconnected -- that is, its process crashed.  
115:     mService = null;  
116:    }  
117:   }  
118:   override def onStart = {  
119:    super.onStart()  
120:    // Bind to the service  
121:    Log.i("BAA", "Binding")  
122:    bindService(new Intent(this, classOf[BackgroundTimer]), mConnection, Context.BIND_AUTO_CREATE);  
123:   }  
124:   @Override  
125:   override def onStop = {  
126:    super.onStop()  
127:    Log.i("BAA", "Unbinding")  
128:    // Unbind from the service  
129:    if (mIsBound) {  
130:     try {  
131:      // Give it some value as an example.  
132:      val msg = Message.obtain(null,  
133:       BackgroundTimer.UNREGISTER)  
134:      msg.replyTo = mMessenger  
135:      mService.send(msg)  
136:      Log.i("BAA", "Sent message")  
137:     } catch {  
138:      case ex: Exception => Log.i("BAA", ex.getMessage())  
139:     }  
140:     unbindService(mConnection)  
141:     mIsBound = false;  
142:    }  
143:   }  
144:  }  

The first thing to notice is that we are using 2 Traits.  Actionable and MessageReceiver.  You can see, even with this simple app, we're composing functionality from small pieces, and we're reusing code from the Service.  I've never NEEDED multiple inheritance, but in this case, it sure is nice.  We've already seen MessageReceiver, but lets take a look at Actionable:

1:  package com.example.scaladoro.activity  
2:  import android.view.View  
3:  trait Actionable {  
4:   implicit def toRunnable[F](f: => F): Runnable = new Runnable() { def run() = f }  
5:   implicit def toOnClickListener(f: View => Unit): View.OnClickListener = new View.OnClickListener() { def onClick(v: View) = f(v) }  
6:  }  

Actionable simply holds 2 implicit definitions.  These allow us to use functions in our Activity instead of having to constantly create new Abstract inner classes.  Now when I want to run something on the UI thread, I just use the syntax on line 43.  No 'new' keyword, no class definition, no methods to mark @Override.  Just the code that will be run.  All the cruft that obfuscates what we're trying to do is gone.

Notice I had to use additional syntax to set the click listeners (line 21).  I defined the click listener functions in the activity, and Scala's compiler didn't like them until I wrapped them in the implicit.  It doesn't add a ton of code and I find it to be a much cleaner implementation of the state/strategy pattern than creating abstract classes, so I'm willing to live with it.

Take another look at the code. Once again, there is is very little 'boilerplate' and nice cohesion.  Once you understand the Scala syntax, its also a lot easier to read and to reason about what is going on than the equivalent Java code.  At least, it is for me.

If you are interested in seeing the app run, go ahead and download it.  I've posted it to the Play store:

Want to try the app out?  Download Campari Pomodoro.

Scala And Android Were Made For Each Other

I've been experimenting with Scala for a while now, and the more I use it, the more I like it.  Scala isn't exactly what I would call an approachable language, but if you are familiar with Java or C# and you slowly work your way into it, Scala is really a joy to work in.

I also like to write apps for Android.  Since Scala runs on the JVM, it runs on Android, too.  Recently I've started to think that Google made a mistake using Java for Android.  It probably helped Android gain apps and popularity since thousands of developers could install the Eclipse Android Plugin and start coding, but that's the thing - Coding on Android is very different than coding, say, a Web app.  It's even quite different than coding a desktop app.  And it is because of the way that things should be written on Android that Java seems to be a poor fit.  All those thousands of programmers started writing apps - and did it wrong.

I know.  I made tons of mistakes.  As I read more about the platform and become more familiar with how things ran, it is clear that a lot of what I did often wasn't a best practice.  Some of what I did was just wrong.

This is where I get to the title of this post.  I recently experimented and wrote an application for Android using Scala.  I have to say, after writing the application this way, I don't ever want to go back. It is my sincere belief that Scala is a much better fit for writing applications on Android than Java.  To prove my point, I am going to go through the app I wrote and show you the Scala code. I am going to assume if you are reading this that you already have some familiarity with Android development so I will refrain from showing the Java alternative.

I'm also going to point out that I am in no way a functional programming expert.  As I said, I use Scala as a better Java.  My code continues to become 'more functional', but I'm sure this is not idiomatic Scala.  That's okay by be, though, because things are just easier.  To me, that's the best measure of how good the code is.

Background

We recently had half our staff move to an office in San Francisco.  Our company has always moved at a rapid pace, but with the additional overhead of working with a team 2 hours difference and across the US, I was feeling like I was getting distracted. I wanted to find a management technique that was simple and that would help me stay on track.  I picked the Pomodoro technique - it was simple. It suited me. It was invented by a programmer, and there were several apps in the Play store for me to use. Of course, I wanted to write my own anyway.

For the purpose of this app, all you need to know is that a Pomodoro is a 25 minute block of time where you concentrate on doing work. Since this is a pretty straight forward app to write, though, I thought I would implement it in Scala to see how it went.

If you want to know more about the Pomodoro Technique, you can visit the official Pomodoro Technique page or Buy the book on Amazon (convenient link on the left).

Application Definition

Here are the things I want the application to do:

• Allow me to start a Pomodoro (a 25 minute block of time)
• Play the ticker sound while in a Pomodoro (for some reason, hearing this helps me stay on track)
• Play a bell when the Pomodoro finishes
• Allow me to cancel a Pomodoro if I have to
• Keep the Pomodoro timer running, even if I close the application 

Here are the constituent parts of my application:

• Activity - Main activity, only Activity.  It has the text that shows you the time left and a button that changes states.  The button will either start or stop the timer.
• Service - A background service that will run the timer task - counting down 

If you've done any Android programming in the past, you realize that even these simple requirements will result in a slew of callbacks, threads, anonymous inner classes, binders, messengers...need I go on?  Okay, that was a bit of an exaggeration, but not as exaggerated as it seems.

Let's think about this for a moment. In order to prevent ANR warnings we need to keep things off the main thread, which, means any communication with our service should be run in separate threads.  Allowing the service to run separately from the Activity (and allow it to potentially be started and called from any activity, even someone else's) will require it to be started and bound so we'll need a Binder and then we'll need to implement its callbacks. Then communication should happen with Messages so we'll need a Messenger and we'll need to implement its callbacks. Oh, and if we want to update the UI so users know whats going on, we need to then run updates from background threads on the UI thread, which, requires a Runnable.

When you add all this up, it makes for lots of  boilerplate code.  Thankfully, the language features of Scala make this less verbose, easier to write,  more understandable, and ultimately easier to maintain.  It also makes it much easier to write code that will follow Android best practices.

Now that we know the what and the how, let's talk code.

The Code

We know we want a bound service that we can send messages to.  When you read the Android docs on it, you'll see that there is a abstract inner class that implements Handler and is passed to a Messenger that is returned in the Services onBind method.

Wow, that was a lot to say.  It is also a lot of boilerplate code.  I wanted to move this to a common class so it was out of my way.  In Java we might make an Abstract base class.  But wait, the Activity in our application also needs a Handler and a Messenger, and if we Make an AbstractService, we could not use that code in an Activity. If we make an AbstractActivity, we cannot use it for our Service.   Here is the first place where Scala is quite handy.  I was able to make a Trait.  Traits are very powerful and I'm using the one below as a 'better interface', which, might be under-utilizing this great feature.  It serves its purpose well, however.

1:  trait MessageReceiver {  
2:   implicit def toIncomingHandler(f: Message => Unit): Handler = new Handler() { override def handleMessage(message: Message) = f(message) }  
3:    
4:   val mMessenger = new Messenger({ m: Message => 
5:    onMessage(m)  
6:   })  
7:    
8:   def onMessage(m: Message)  
9:  }  

Notice that I also used an implicit to reduce the need to declare an abstract inner class to handle the message.  I probably didn't save any code, but I like the way this looks far better than the Java alternative.

Now that we have the MessageReceiver defined, let's define our Service.  Before I show you the code, here are some things I want you to notice about the class:

• We override onMessage and implement it.  This is the only code in this class that is related to receiving a message.  All the boilerplate has been moved to the Trait which can be used by both Activity and Service classes.
• The start method has an internal method called timer that is recursive. This also happens to be tail recursive, and Scala is smart enough to unwind this, so it won't grow my stack.  
• We run the timer in a background thread.  Notice that all we have to do is surround it with a spawn{} block.  (I omitted the imports, but you need to import scala.concurrent.ops._ to do this)

1:  case class BackgroundTimer extends Service with MessageReceiver {  
2:     
3:   var millis = 0L;  
4:   /** Keeps track of all current registered clients. */  
5:   var mClients = List[Messenger]()  
6:   var currentTime = "0:00"  
7:    
8:   val mediaPlayer = new SoundPool(2, AudioManager.STREAM_MUSIC, 0)  
9:    
10:   var tickId: Int = -1  
11:   var alarmId: Int = -1  
12:   var tickStreamId = -1  
13:     
14:   override def onMessage(m:Message) = {  
15:    m.what match {  
16:     case BackgroundTimer.REGISTER =>
18:       mClients ::= m.replyTo  
19:      }  
20:     case BackgroundTimer.UNREGISTER =>
21:      if (m.replyTo != null) {  
22:       mClients = mClients.remove(messenger =>
23:        if (messenger == m.replyTo) {  
24:         true  
25:        } else {  
26:         false  
27:        })  
28:      }  
29:     case BackgroundTimer.START >  
30:      start()  
31:     case BackgroundTimer.STOP =>
32:      //don't play the alarm bell  
33:      stop(true)  
34:    }  
35:   }  
36:    
37:   override def onStartCommand(intent: Intent, flags: Int, startId: Int): Int = {  
38:    Log.i("BAA", "Received start id " + startId + ": " + intent)  
39:    try {  
40:     tickId = mediaPlayer.load(this, R.raw.singletick, 1)  
41:     alarmId = mediaPlayer.load(this, R.raw.alarm, 1)  
42:    } catch {  
43:     case e: Exception => Log.d("BAA", e.getMessage())  
44:    }  
45:    Service.START_STICKY; // run until explicitly stopped.  
46:   }  
47:    
48:   /**  
49:    * Must override this to allow the service to bind to the Activity so we can start/stop timers  
50:    */  
51:   override def onBind(intent: Intent): IBinder = {  
52:    Log.i("BAA", "OnBind called")  
53:    return mMessenger.getBinder()  
54:   }  
55:    
56:   def start() = {  
57:    if (millis == 0) {  
58:     spawn {  
59:        
60:      var alarmStreamId = -1  
61:      try {  
62:       tickStreamId = mediaPlayer.play(tickId, 2.0f, 2.0f, 1, -1, 1.0f)  
63:      } catch {  
64:       case e: Exception => Log.d("BAA", e.getMessage())  
65:      }  
66:        
67:      def timer(millisLeft: Long): Unit = {  
68:       if (millis > 0) {  
69:        millis = millisLeft  
70:       }  
71:       val seconds = (millisLeft / 1000) % 60;  
72:       val minutes = ((millisLeft / (1000 * 60)) % 60);  
73:       currentTime = minutes + ":" + (if (seconds > 9) seconds else "0" + seconds)  
74:    
75:       if (millis > 0) {  
76:        mClients.foreach { messenger =>
77:         val response = Message.obtain(null, BackgroundTimer.TICK, 0, 0, currentTime)  
78:         messenger.send(response)  
79:        }  
80:        Thread.sleep(995);  
81:        timer(millisLeft - 995)  
82:       } else {  
83:        stop(false)  
84:          
85:       }  
86:      }  
87:      //now start it off...  
88:      millis = 1000 * 60 * 25  
89:      timer(millis)  
90:     }  
91:    }  
92:   }  
93:    
94:   def stop(forced:Boolean) = {  
95:    millis = 0  
96:    currentTime = "0:00"  
97:    mediaPlayer.stop(tickStreamId)  
98:    if(!forced)  
99:     mediaPlayer.play(alarmId, 0.2f, 0.2f, 1, 0, 1.0f)  
100:    mClients.foreach { messenger =>  
101:     val response = Message.obtain(null, BackgroundTimer.STOPPED, 0, 0, currentTime)  
102:     messenger.send(response)  
103:    }  
104:   }  
105:  }  
106:    
107:  /**  
108:   * Define an object to hold some statics  
109:   */  
110:  object BackgroundTimer {  
111:   val REGISTER = 1  
112:   val START = 2  
113:   val STOP = 3  
114:   val UNREGISTER = 4  
115:   val STARTED = 5  
116:   val STOPPED = 6  
117:   val TICK = 7  
118:  }   
119:    

I don't know about you, but this class looks very clean to me.  Almost all the code is directly related to what this class is intended to do with no messy boilerplate code for messaging or threading.  In fact, threading is now too easy -  just add a spawn block and done.  The 'business logic' is also very compact.  Since timer can be declared inside start, all the logic for actually running the timer is in one spot - no need to jump to a different section of code to see what's going on.

Want to try the app out?  Download Campari Pomodoro.

Next up, the Activity

Learn C Chapter 22 Flashcards

I'm currently slowly going through Zed Shaw's "Learn C The Hard Way".  In chapter 22, he instructs you to make flashcards of the C data types and flow control structures.  Seeing as how C syntax is really close in many ways to Java syntax, a lot of this stuff is pretty natural.  There are several functions,  macros and types, though, that are different and that I really should memorize.

As I just happen to work for a company that writes flashcard apps (StudyBlue.com), I figured I might as well create them on the site and share them for anyone else working through the book.  So, here are my, Learn C The Hard way - Ch 22 - data types and flow control in C flashcards.

Enjoy.

First TMX Map rendered with TMX-S-Parser

Well, I've been working in my infinite spare time on a parser that will allow you to easily use Scala to render maps in the TMX Map format.  The project started as a way for me to learn some more about Git and get more experience using Scala.  While the Euler problems were nice, I really wanted to do something non-trivial and non-academic in Scala.

This weekend I was finally able to make some headway on the project again and I was able to get my sample map rendered using Swing.  Here are the pictures:

Map as rendered by TMX-S-Parser in Swing

Map as rendered in Tiled (Objects hidden)

As you can see, the basic layer rendering seems to be working now.  I'm actually quite excited to start working on the other elements that can be in the map - objects, polygons and the like.  I also have some ideas for 'properties'.  If you'd like to see the code, check out the TMX-S-Parser project on Github.

Parsing TMX Maps using Scala

A co-worker and friend of mine was recently talking about how he wanted to make games on a phone.  He's a fan of turn-based style board games.  He was lamenting, though, at how much work it would take just to create things like maps and backgrounds, let alone characters and the like.  Of course, there are tools emerging to aid in the building of these things.  One of them is Tiled.  Tiled allows you to create maps from tile set image and store the resulting map definition in an XML file.  This format is called TMX Map Format.

I've recently been playing around with some Scala, and I figured since I liked Scala's XML support so much, I would create a little library that would parse a TMX file, represent the elements as Objects and allow you pretty easily render a Tiled map.

Who knows, maybe I will eventually turn it into a full-fledged Game framework.  For now, though, I'm concentrating on just the TMX parsing and utilities to allow you get the map info into your program.

The XML.

Since Scala's XML parsing is first-class, it was pretty easy to get started.  As I started looking through the documentation and writing tests, a few interesting portions of the code started to pop up.  First, it appears that there are several ways to express the ids of the tiles (each ID representing a 'tile' in the image it references).  The formats are: XML, csv, and Base64.

In addition to the different formats, the Base64 data could optionally be compressed using gzip or glib.  This presented me with the most interesting portions of the code.  First, the XML parser needed to be smart enough to create the Layers correctly depending on the formats.  Second, I needed to do some data manipulation to interpret the Base64 data the correct way.

Let's talk about the XML parsing depending on the different tags.  As it turns out, there was very little code for me to write to parse the XML, even with the variable data format.  What's interesting, is that I was able to make the parser return an immutable map object, creating each element and all sub-elements while constructing the hierarchy.  This is in keeping with my 'least mutable state' exercises I've been working on.  Here is a sample of the parsing code:



def loadMap(src: InputStream): TmxMap = {
    val xml = XML.load(src)
    new TmxMap((xml \ VERSION).text,
      (xml \ ORIENTATION).text,
      (xml \ WIDTH).text.toInt,
      (xml \ HEIGHT).text.toInt,
      (xml \ TILE_WIDTH).text.toInt,
      (xml \ TILE_HEIGHT).text.toInt,
      xml \ TILE_SET collect { case tileSet: Node => new TmxTileset((tileSet \ FIRST_GID).text, (tileSet \ NAME).text, getValue((tileSet \ TILE_WIDTH).text), getValue((tileSet \ TILE_HEIGHT).text), createImage((tileSet \ IMAGE).first)) },
      xml \ LAYER collect {
        case layer: Node =>


          if (!(layer \ DATA \ ENCODING).text.isEmpty()) {


            TmxLayer.fromData((layer \ NAME).text, getValue((layer \ WIDTH).text), getValue((layer \ HEIGHT).text), (layer \ DATA \ ENCODING).text, (layer \ DATA \ COMPRESSION).text, (layer \ DATA).text);
          } else {
            TmxLayer.fromTiles((layer \ NAME).text, getValue((layer \ WIDTH).text), getValue((layer \ HEIGHT).text),
              layer \ DATA \ TILE collect { case tile: Node => new TmxTile(getValue((tile \ GID).text)) })
          }
      },
      xml \ OBJECT_GROUP collect {
        case objectGroup: Node => new TmxObjectGroup((objectGroup \ NAME).text, getValue((objectGroup \ WIDTH).text), getValue((objectGroup \ HEIGHT).text),
          objectGroup \ OBJECT collect {
            case obj: Node => new TmxObject((obj \ NAME).text, getValue((obj \ X).text), getValue((obj \ Y).text), getValue((obj \ GID).text),
              obj \ POLYGON collect { case poly: Node => new PropertiesFactory[TmxPolygon].setProperties(poly \ PROPERTIES, new TmxPolygon(parsePoints((poly \ POINTS).text))) })
          })
      })
  }



What should pop out at you right away is that the loadMap function essentially has two statements.  One loads the XML, the other creates a new TmxMap.  There is a LOT going on here and I often consider breaking this up a little into smaller methods so its more readable and digestible, but its interesting to see how you can create compound statements in Scala.

The next most interesting thing is that if the data comes across as Base64, it is supposed to be interpreted as a byte array of unsigned little-endian integers.

Well, Java and Scala do not have unsigned types, so this required a little bit of conversion.  Interestingly, my first attempt used Sun's undocumented decoder.  I ran into an interesting issue with it.  It did not remove the carriage returns from my XML data before passing it to the decoder.  The decoder returned values, but they were wrong.  I re-implemented the function using the Apache Commons decoder, and it works just fine.  This leads me to wonder, though.  Which is more correct?  Should I remove all carriage returns from my data before parsing or should a decoder be able to recognize that?  I'm not sure which I would prefer.

I've created a project for this called, TMX-S-Parser on github and I intend to keep adding to it until I'm satisfied it is robust and complete.  Take a look at the code.  If you have the will, copy the repo, make some changes, recommend improvements, add utility.

Project Euler Problem 10 in Scala

This is 10 in a series. The previous post is at, Project Euler Problem 9 in Scala.


Problem 10 on project Euler is:

The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.
Find the sum of all the primes below two million.

Problem 10 posed an interesting issue for me.  I came up with a solution I thought would work well right away, but I couldn't seem to get the correct answer.  After poring over my code and playing around, I finally found my issue - my isPrime function had an error in it, causing me to be off by 2.  


What is interesting about this scenario is that I've been using that same function for lots of different problems, but since the function was only broken for the number 2, it didn't matter in those.  If I had some sort of test that say, verified the function against a random set of prime numbers, I would have found the issue much sooner. This speaks to how important it is to test even seemingly working things whenever you can.    


Another by product of the issue is that I did a little more research on calculating prime numbers.  Wikipedia had a nice article about the  Sieve of Eratosthenes.  This gave me a much better understanding of how it works.  While I am not changing my code (yet) to use a sieve, it was certainly valuable to learn more about how its done.  


Well, I did manage to finish it, and here is my solution.  Enjoy:


object Problem10 {
  def main(args: Array[String]): Unit = {
    var holder : BigDecimal = new BigDecimal(new java.math.BigDecimal("0"));
    (2 to 1999999).filter{next => val prime = isPrime(next);if(prime){holder = holder + new java.math.BigDecimal(new Integer(next).toString())};prime}
    println(holder)
  }
  
  /**
   * Brute force method.  Perhaps a better method 
   * can be implemented here?  
   */
  def isPrime(number: Long) : Boolean = {
    if(number == 2)
      return true
    if(number%2==0 || number % 3==0)
      return false;
    val sqrt:Int = Math ceil (Math sqrt number)  intValue;
    (true /: (3 to sqrt))((isPrime, next) => {
      if(number % next == 0) 
        return false 
      isPrime
    })
  }
}


Now that I've completed #10, I get a Euler award.  I have become a 'Decathlete' for finishing 10 problems in a row.  


And with that, I think I will finish blogging about my Euler solutions.  I still plan on working through the problems, but I think I've worn out my Euler solution posts and will move on to some other interesting topics.  

StudyBlue Flashcards nominated for Best App Ever Awards

I've been working for StudybBlue for about 9 months now.  If you don't know what StudyBlue is, it's a fantastic place for students to create online flashcards, study those flashcards, create quizzes from them, and track their progress.  In other words, its a product that makes students more efficient and effective.  


StudyBlue is more than a Web site, however.  It also produces native flashcard applications for iPhone and Android to allow students to study their cards on the go.  The goal for our company is to create a total user experience and we invest a lot of time, effort and energy into our application designs.  Apparently, that hard work is starting to payoff.  


We were recently notified that we were nominated for the the Best App Ever Awards.  While its not the biggest award or the best known, the interesting thing about it is that it is a user-driven award.  It means that one of our users nominated our app and other users will be voting on it.  In my mind this is one of the highest compliments StudyBlue could be paid.  After all, it doesn't really matter what anyone thinks but your users, and it seems that we're keeping at least some of ours pretty happy.  


If you are a student and use StudyBlue, please vote for our app.  There would be nothing more satisfying than knowing that our users think we're the Best App Ever.
Vote for STUDYBLUE Flashcards for Best High School Student App

Project Euler Problem 9 in Scala

This is 9 in a series.  The previous post is at, Project Euler Problem 8 in Scala. 


I've still been (slowly) working my way through the Project Euler Problems.  The next one is problem 9 which reads:

A Pythagorean triplet is a set of three natural numbers, a  b  c, for which,
a^2 + b^2 = c^2
For example, 3^2 + 4^2 = 9 + 16 = 25 = 5^2.
There exists exactly one Pythagorean triplet for which a + b + c = 1000. Find the product abc.

For this problem, I didn't use anything fancy.  Two for-comprehensions and basic math produced the solution in short order.  The only thing to mention about this solution is that it actually finds the solution twice since I'm iterating1 to 998 twice. I considered trying to optimize this, however, it runs plenty fast.  Since my goal in solving these isn't to come up with the fastest solution, but to come up with a solution that has no mutable state, I have met my goal.  Therefore, I present you the solution to problem 9:



object Problem9 {
  def main(args: Array[String]): Unit = {
    for (a <- 1 to 998) {
      for (b <- 1 to 998) {
        val c = 1000 - (a + b)
        if ((a * a) + (b * b) == (c * c)) {
          println("the triplet is " + a + " " + b + " " + c)
          println("the product is " + (a * b * c))
        }
      }
    }
  }
}


I think that's all for this one.  Problem 10 is in the hopper...

Project Euler Problem 8 in Scala

This is 8 in a series.  The previous post is at, Project Euler Problem 5 in Scala. 


So we saw problem 6 solved with a 'one-liner'.  Then we moved on to problem 7 and I had to have a while loop and control variables, which really disappointed me. Problem 8, however, was not only satisfying, but allowed me to explore even more features of Scala.  


Before I get into the actual problem, I want to comment on my language progress.  My 'native tongue' so-to-speak, is Java.  I use Java at work and have for 12 years. I expect it will be paying the bills for years to come.  We can debate the merits of Java as a language, and I'm sure every one reading this has an opinion about it, good or bad.  Regardless of opinion, I am most productive in Java.  Period.  Why?  Because I have used it so much, and am so familiar with the syntax and libraries that the language 'gets out of the way'.  I don't have to think about anything but what the code is intending to do.  This makes me very productive.  I'm finding that its taking a little longer to get to the point where I feel like the language has stepped back with Scala.  Part of it is the rather verbose API documentation, which, just seems to tell me too much and doesn't allow me to get right to 'how do I use this'.  Part of it is that Scala has a lot more power and expressiveness than Java, and that takes more time to learn.  At any rate, my Scala skills are slowing improving.  


Now, on to Problem 8:

Find the greatest product of five consecutive digits in the 1000-digit number.

 73167176531330624919225119674426574742355349194934
 96983520312774506326239578318016984801869478851843
 85861560789112949495459501737958331952853208805511
 12540698747158523863050715693290963295227443043557
 66896648950445244523161731856403098711121722383113
 62229893423380308135336276614282806444486645238749
 30358907296290491560440772390713810515859307960866
 70172427121883998797908792274921901699720888093776
 65727333001053367881220235421809751254540594752243
 52584907711670556013604839586446706324415722155397
 53697817977846174064955149290862569321978468622482
 83972241375657056057490261407972968652414535100474
 82166370484403199890008895243450658541227588666881
 16427171479924442928230863465674813919123162824586
 17866458359124566529476545682848912883142607690042
 24219022671055626321111109370544217506941658960408
 07198403850962455444362981230987879927244284909188
 84580156166097919133875499200524063689912560717606
 05886116467109405077541002256983155200055935729725
 71636269561882670428252483600823257530420752963450

 This problem is pretty straight forward.  Iterate the string literal and multiply sets of 5 numbers together.  Find the largest of those numbers and return it.  Now, in Java, this would take a couple of for loops, a String, possibly a string buffer, some variables to store the results, and an ugly System.out.println....

Not so in Scala.  The Collections facilities actually allowed me to solve this in one line, without any mutable state.  No, really, I mean it.  Check this out:

object Problem8 {
  def main(args: Array[String]): Unit = {
    val totalDigits = """[omitted the big string literal here, but you can add it back if you want to run the code...]"""
    println((for (i <- 5 to totalDigits.length()) yield totalDigits slice (i - 5, i)) collect {
      case i =>
        i.foldLeft(1)((product: Int, nextChar) => {
          (nextChar asDigit) * product
        })
    } max)
  }
}


Okay, its a 'one-liner' but there is a lot going on there.  Let's deconstruct the statement.  First, we see that everything is wrapped in a 'println', which is nice shorthand in Scala for System.out.println.  The second thing we see is that the result of the statement 'max' is what will be printed.  max is a collection function.  A couple of things to note.  Since max takes no arguments, we drop the '()'.  Since Scala can infer its a method call, we can even omit the '.'.  Now let's look at the rest of the code, shall we?


Let's go back to the beginning of the statement.  We are using the 'for' comprehension.  To be honest, the 'for' comprehension in Scala is much more powerful than the 'for' loop in other languages I've used.  You can see, we are going to iterate 5 to the length of the string.  For each iteration, we are going to yield the slice if i-5 and i.  slice is a nice string operator in Scala.  Essentially, we're getting 5 characters.  In turn we are going to collect the results of folding (There's that foldLeft again....) the 5 character Sequence.  The result of all of these will be a Sequence of Int values, on which we call 'max' function.


Boy, that was a mouthful.  It was cool, though, wasn't it?  It took a few minutes for me to weed through the API and figure out the syntax for this, but in the end, it is a succinct and stateless solution....


On to the next one...

Project Euler Problem 7 in Scala

This is 7 in a series.  The previous post is at, Project Euler Problem 6 in Scala.


After a very successful solution to problem 6, we get to problem 7.  I couldn't figure out how to remove all mutable state from this solution.  The issue is that we have to find the 10,001st number which means that we do not know how long we have to iterate.  I used a while loop here, and it seems to work fine.  Perhaps someone has a solution without a while loop?  


Here's Project Euler problem 7:

 By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.
 What is the 10,001st prime number?

object Problem7 {


  def main(args: Array[String]): Unit = {
var counter = 1L;
var number = new BigDecimal(new java.math.BigDecimal("0"));
var currentNum = 1l;

while(counter <= 10001) {
 if(isPrime(currentNum)) {
   number = new BigDecimal(new java.math.BigDecimal(currentNum));
   counter = counter + 1;
 }
 currentNum = currentNum + 1;
}
println("10001st prime " + number);
  }
    
  /**
   * Brute force method.  Perhaps a better method 
   * can be implemented here?  
   */
  def isPrime(number: Long) : Boolean = {
    if(number%2==0)
      return false;
    val sqrt:Int = Math ceil (Math sqrt number)  intValue;
    (true /: (3 to sqrt))((isPrime, next) => {
      if(number % next == 0) 
        return false 
      isPrime
    })
  }
} 


You should note that I've cleaned up my isPrime method.  I noticed that it wasn't very functionally written, so I changed it to use a fold left (By the way, foldLeft is turning out to be one of the handiest Scala constructs on the planet.)  I am now very comfortable with the isPrime method, at least as a brute force solution.