Euler Project Problems 1-3 in Scala

As with when I learned Ruby, I find Project Euler to be an extremely useful way both to learn a language and its idioms and also flex my math muscles every once in a while. Since I’m starting to learn Scala, I decided to start answering the problems there again (the last time I got to 33) and thought I’d share what I came up with here.

Problem #1

object problem1 {
  def run(number: Int): Int = {
    sum(number - 1)
  }

  def sum(number: Int): Int = {
    number match {
      case 0 => 0
      case n => (if(n % 3 == 0 || n % 5 == 0) n else 0) + problem1.sum(n - 1)
    }
  }
}

I had wanted to use PartialFunction‘s functionality for the sake of some mental gymnastics (and the fact that filtering doesn’t occur until the inside of the case in the previous solution), so here’s another solution:

def problem1Runner(x: Int): Int = {
  val zeroCase: PartialFunction[Int, Int] = { case 0 => 0 }
  val otherNumbers: PartialFunction[Int, Int] = { case n => p1(n) }

  val runner = zeroCase orElse new Problem1PF orElse otherNumbers

  runner(x)
}

def p1(x: Int) = problem1Runner(x - 1)

class Problem1PF extends PartialFunction[Int, Int] {
  def isDefinedAt(n: Int): Boolean = {
    (n % 3 == 0 || n % 5 == 0)
  }

  def apply(n: Int): Int = {
    n + p1(n)
  }
}

println(p1(1000))

Obviously, this is the less readable solution, but it taught me more to try and code it.

Problem #2

def fibSum(): Int = fibSum(1, 2)

def fibSum(a: Int, b: Int): Int = {
  var sum = 0
  var x = a
  var y = b

  while (x <= 4000000) {
    if (x % 2 == 0) sum += x

    val z = x
    x = y
    y += z
  }

  sum
}

println(fibSum())

I tried to create an obvious recursive solution, but I quickly understood how it would overflow.

Problem #3

Here I tried the obvious solution first, but it had horrible complexity, so I went and implemented the (unreadable) Shanks’ square forms factorization algorithm (and used Euclid’s greatest common divisor algorithm as part of it).

import collection.mutable.ListBuffer

object problem3 {
  def apply(n: Long): Long = {
    var num = n
    val factors = ListBuffer[Long](problem3.findFactor(num))

    while (factors.last != 1) {
      num /= factors.last
      factors.append(problem3.findFactor(num))
    }

    factors.max
  }

  private def findFactor(n: Long): Long = {
    // initialize
    val k = 1
    var p: ListBuffer[Long] = ListBuffer(math.floor(math.sqrt(k * n)).asInstanceOf[Long])
    var q: ListBuffer[Long] = ListBuffer(1, (k * n - math.pow(p.head, 2.0)).asInstanceOf[Long])
    var b: Long = 0L

    // repeat
    var i = 1

    do {
      b = math.floor((math.floor(math.sqrt(k * n)) + p(i-1)) / q(i)).asInstanceOf[Long]
      p.append(b * q(i) - p(i-1))
      q.append(q(i-1) + b * (p(i-1) - p(i)))
      i += 1
    } while (!isPerfectSquare(q.last))

    // initialize
    b = math.floor((math.floor(math.sqrt(k * n)) - p(i-1)) / math.sqrt(q(i))).asInstanceOf[Long]
    p = ListBuffer((b * math.sqrt(q(i)) + p(i - 1)).asInstanceOf[Long])
    q = ListBuffer(math.sqrt(q(i)).asInstanceOf[Long], ((k * n - math.pow(p(0), 2.0)) / math.sqrt(q(i))).asInstanceOf[Long])

    // repeat
    i = 0

    do {
      i += 1
      b = math.floor((math.floor(math.sqrt(k * n)) + p(i-1)) / q(i)).asInstanceOf[Long]
      p.append(b * q(i) - p(i-1))
      q.append(q(i-1) + b * (p(i-1) - p(i)))
    } while (p(i-1) != p(i))

    gcd(n, p(i))
  }

  private def isPerfectSquare(n: Long): Boolean = {
    val root: Long = math.floor(math.sqrt(n)).asInstanceOf[Long]

    root * root == n
  }

  private def gcd(a: Long, b: Long): Long = {
    // Euclid's algorithm
    b match {
      case 0 => a
      case _ => gcd(b, a - b * math.floor(1.0 * a / b).asInstanceOf[Long])
    }
  }
}

println(problem3(600851475143L))

Notes:

  1. ListBuffers are better than Lists for appending items.
  2. Turns out you can’t do for on a range longer than Int.MAX_VALUE.
  3. The number of non-textual operators in Scala is insane!
Advertisements

A Fresh Start

Since January 2010, I’ve been working at LivePerson, as a Senior Java Developer and ScrumMaster. It’s now time to move on – I will be joining newBrandAnalytics starting November 1st, 2011 and have decided it’s time to bring my professional blog back to life.

As I have not focused on .NET in the past two years and the fact that I’ll be working in Scala at nBA, I’ve decided to move the blog from the old ASP.NET Community Server 2007 installation that has been my home for years to WordPress. The blog will no longer focus on any one thing, so if you’ve come here expecting .NET content, I apologize, but hope you’ll stay and keep reading.

Here’s to new beginnings and fresh starts! :)

The Anti-Social Network

(I’ve returned from my trip a few months ago, but didn’t have enough to blog about; hopefully, this is my returning to a semi-regular posting schedule; also, I’ve decided to veer off .NET in some of my posts, focusing on more issues that I like to talk about and offer my opinions on)

(Update: This article is now featured in Hebrew in Gal Mor’s blog “Holes in the Net”)

CC-BY-NC, Min Jung Kim Social networks have been flourishing in the past few years, and have let us reach more people than we could before them. I, personally, use both Facebook and Twitter on a daily basis. The trend of ‘socialized’ applications is steadily marching on. A simple example of that is e-commerce sites looking to increase their conversion rate with you using recommendations from your friends.

However, there is yet another trend coming up that we should worry about, which is users trying to force anti-social behavior. Here are a couple of examples:

  1. Facebook introduced the ‘Like’ feature in February 2009, making it easier for users to say that they like a certain something: a post, a picture, a link, etc. This feature was immediately put to good use, with people ‘liking’ things, instead of creating long comment chains. ‘Liking’ something was much easier, too, being a single-click action, and increased the amount of participation. The Like feature was a good thing.

    Lately, voices have come up in favor of creating a ‘Dislike’ button. Users feel that since they have an easy way to notify their friend that they like his or her post, that they should equally be able to notify them of not liking it, discouraging the person from continuing this kind of activity.
    To use the ‘Dislike’ feature would be like saying to someone’s face that their joke was not funny or that they are ugly. Face to face, you might only do that to your closest friends and family and even then in jest, but online it’s much easier to be anti-social. The socially acceptable alternative to the ‘Dislike’ button would be to ‘Hide’ that friend’s updates, which unlike ignoring someone in the real world, is something the friend will never know about and will therefore never get offended by.
  2. The way to use Twitter is not something users can agree on. One thing that is widely agreed upon, though, is that following someone means you care what they say. That leads most people to the mistaken belief that the more followers you acquire, the more people will believe you are important and influential.One of the ways in which users are attempting to inflate their follower count is the contemptible habit of expecting auto-follow-back. This means that the user follows you, waits for you to follow them back and then un-follows you if you haven’t. This widely embraced practice causes unsuspecting users to be barraged with a very large number of follow notifications from people, brands and companies they have no interest in.This is downright adamant to spam, which we can all agree is one of the least socially acceptable activities you can partake in online.

These examples just go to show the trend of users wanting to add anti-social behavior to a social platform.

Social networks, on their part, should never allow themselves to be catalysts for anti-social behavior. Anti-social activities, such as hiding users or reporting them or their actions should remain hidden from all other users and must remain in confidence between the user and the platform. The real world parallel to this would be ‘telling on’ someone, which is frowned upon.
Facebook tries to avoid that by making all positive social activities more open, while keeping the anti-social activities on a one-on-one basis between the user and the platform. Unfavorable comments are still prevalent, but are unavoidable.
Twitter is, on the other hand, lagging far behind by keeping their network very much bare of personal filters (no way to hide unwanted tweets) and allowing users to easily find out who un-followed them, to name just a few issues.

The rule-of-thumb I present here does not stop with social networks, but continues to other socially-influenced platforms. Socially-enabled games follow this rule too: FarmVille, which at the time of writing of this post is the most popular and fastest growing game of all time on Facebook, does the same.
Players have a multitude of socially-positive activities to choose from, such as sending each other gifts, taking in animals their friends put up for adoption, helping out on friends’ farms and even racing each other to the top of their local hall of fame in the long run. On the other hand, there are no socially-negative activities in the game: players can not steal crops or animals from friends, mess up their farms, etc.

Social platforms should make it easy to broadcast socially-positive activities and hard to broadcast the negative ones. Once they follow this simple frame of mind, they will reap the psychological and sociological benefits.

Hiatus

In 15 days’ time, I’ll be taking off on a four months long trip around the world. I’ll be hiking and travelling my way through Japan (March-May), the United States of America (May-July) and the Netherlands (July). I’ve been planning this trip for a long time now, since I came back from Japan for the first time in August 2007 (the photo on the right was taken near the Tsurugaoka Hachiman-gu Shrine in Kamakura), and have taken a long leave from work to accomplish it. What this means is that from March 10th you can expect a long pause in my semi-regular updates.

I am not dead :)

If you’re a reader who lives along my path and want to meet up for a beer and a lively chat, ping me via the contact form. I’ll be reading my emails every once in a while, so don’t worry if you only get an answer after a few days.

If you want to read about my trip, I’ll be posting regular updates to my new travel blog.

Circumventing the KB957543 .NET 3.5 SP1 Regression Bug

A couple of days ago I hit a regression bug in .NET 3.5 SP1, in which when you have a generic class that implements ISerializable and has static variables – you can not serialize it using a BinaryFormatter without your application either hanging (x86) or raising an exception (x64 – a TargetInvocationException containing an OutOfMemoryException). This only happens if you use a reference type as a generic argument.

It’s already well known, but I have yet to find a workaround documented anywhere. You could simply install the hotfix, but well, I wouldn’t if I were you – it hasn’t been thoroughly tested yet. Moreover, you might not even be able to do so due to either internal politics, strict IT rules or the fact that you simply do not have control over the hosting server.

Let’s take the simplest class that causes the issue:

[Serializable]
public class MyClass<T> : ISerializable
{
private static int list = 0;
public MyClass()
{
}
protected MyClass(SerializationInfo info, StreamingContext context)
{
}
void ISerializable.GetObjectData(SerializationInfo info, StreamingContext context)
{
}
}

When using the class as such:

using (MemoryStream stream = new MemoryStream())
{
BinaryFormatter formatter = new BinaryFormatter();
formatter.Serialize(stream, new MyClass<string>());
stream.Position = 0;
MyClass<string> item = (MyClass<string>)formatter.Deserialize(stream);
}

The last line will hit the bug.

To work around this issue, simply move your static variables into a new subclass:

[Serializable]
public class MyClass<T> : ISerializable
{
private static class KB957543
{
public static int list = 0;
}
public MyClass()
{
}
protected MyClass(SerializationInfo info, StreamingContext context)
{
}
void ISerializable.GetObjectData(SerializationInfo info, StreamingContext context)
{
}
}

You can still access all of your static variables and you don’t hit the bug.

Note that when you use anonymous methods or lambdas, they are cached as static variables of the type, meaning that you will have to manually type all of your lambdas.

Here’s an example of such a type that is prone to the bug:

[Serializable]
public class MyClass<T> : ISerializable
{
public MyClass()
{
}
public static string Concat(IEnumerable<int> numbers)
{
return string.Join(", ", numbers.Select(i => i.ToString()).ToArray());
}
protected MyClass(SerializationInfo info, StreamingContext context)
{
}
void ISerializable.GetObjectData(SerializationInfo info, StreamingContext context)
{
}
}

If we look through Reflector, we can see that there is a cached delegate in our type:

Since this is a static member, it makes the type susceptible to the bug and we now need to manually create the cached member ourselves:

[Serializable]
public class MyClass<T> : ISerializable
{
private static class KB957543
{
public static readonly Func<int, string> ToString = i => i.ToString();
}
public MyClass()
{
}
public static string Concat(IEnumerable<int> numbers)
{
return string.Join(", ", numbers.Select(KB957543.ToString).ToArray());
}
protected MyClass(SerializationInfo info, StreamingContext context)
{
}
void ISerializable.GetObjectData(SerializationInfo info, StreamingContext context)
{
}
}

Let SQL Server Tell You Which Indexes to Rebuild

When index fragmentation becomes too high, indexes will be very inefficient. Other than planning a good index design, you should rebuild / reorganize your indexes every once in a while.

SELECT 'ALTER INDEX [' + ix.name + '] ON [' + s.name + '].[' + t.name + '] ' +
CASE WHEN ps.avg_fragmentation_in_percent > 40 THEN 'REBUILD' ELSE 'REORGANIZE' END +
CASE WHEN pc.partition_count > 1 THEN ' PARTITION = ' + cast(ps.partition_number as nvarchar(max)) ELSE '' END
FROM   sys.indexes AS ix INNER JOIN sys.tables t
ON t.object_id = ix.object_id
INNER JOIN sys.schemas s
ON t.schema_id = s.schema_id
INNER JOIN (SELECT object_id, index_id, avg_fragmentation_in_percent, partition_number
FROM sys.dm_db_index_physical_stats (DB_ID(), NULL, NULL, NULL, NULL)) ps
ON t.object_id = ps.object_id AND ix.index_id = ps.index_id
INNER JOIN (SELECT object_id, index_id, COUNT(DISTINCT partition_number) AS partition_count
FROM sys.partitions
GROUP BY object_id, index_id) pc
ON t.object_id = pc.object_id AND ix.index_id = pc.index_id
WHERE  ps.avg_fragmentation_in_percent > 10 AND
ix.name IS NOT NULL

The above query will give you a list of recommended index rebuild / reorganize statements for your database, according Pinal Dave’s 10-40 rule, although you are welcome to tweak it to your liking. It supports non-partitioned as well as partitioned indexes. If you want a more intense check for fragmentation, change the last NULL in the dm_db_index_physical_stats call to ‘SAMPLED’ or even ‘DETAILED’ (include quotes).

It’s a handy little tool for database administrators and saves a lot of the hassle of monitoring index fragmentation.

Update: Added multi-schema support as suggested by MJ12 and another check for null index names.

SQL Server Management Studio 2008 IntelliSense Doesn’t Recognize Special Characters

ssms

I just filed a new bug with Microsoft Connect. I certainly hope this one doesn’t get shrugged off like many of my other bugs did.

Want to reproduce it yourselves? Just create a table with a character that can only be valid inside the context of brackets (like a comma or braces) and then try to select from it. Don’t keep the CREATE clauses in the same query window or it might just work. See the screenshot below.

This is very frustrating because this means that not only is there no IntelliSense for these objects, but IntelliSense now gets in the way of actual querying as it will autocomplete incorrect names.