Groovy OLC #3 – Perfect numbers

At a time when new JVM based languages are mushrooming as fast as frameworks were being written a few years ago, it is interesting to reflect upon a few trends. About 6th century CE, there were already several languages in India and several grammar works were being written. But there is one work outstanding in its contribution to the world of linguistics. A linguist named Bhartruhari wrote vAkyapadIya (Book of sentences and words). Instead of grammar, he pondered on the Philosophy of Languages, where he traces formation of a sentence all the way back to the abstractness of sound. This sixth century work contains some very fine abstraction thinking, which has formed the basis of much of 20th century linguistics.

An analogy can be seen with programming languages too. The underlying “language” of ’em all is 1s and 0s, but the syntaxes and semantics vary vastly. With so many languages being created, one question to ask is the Philosophy of the Programming Language. Every language, every framework must have a philosophy, or in loose terms, the “why” behind it. Why did you select your syntax the way it is? Why did you name something this and not that? What can you solve with your language that the others cant?

The philosophy of Java is “Write once run anywhere. And screw the pointers”. The philosophy of C# is like “Something like Java, but sorry, no Js. And screw the conventions”. The philosophy of Groovy seems to be “You are a programmer, you know better. I will standby and hint functions, you do whatever you want with it. And screw the configurations”. The philosophy of TFS, the rich man’s poor version control, is like “I know everything. You programmers don’t know sh*t. Beg me to keep your source safe. And screw You”. In essence it is like “I dont like this feature in this language. So I am creating a new language without that feature”.

So on the lines of the philosophy of Groovy, in which simplicity and intuitiveness seem to be the gravest concern, there are three built-in closures, that I find extremely powerful – the find, collect and inject. If used correctly, they reduce some complex code to really trivial and make a mockery of standard loop syntaxes.

Perfect numbers are indeed a very fascinating math phenomenon. They are few and far between and whether there are infinite perfect numbers is a not yet solved mystery. I will spare writing about perfect numbers as there is an abundance of online literatue on them. Here’s a very simple Groovy OLC that finds perfect numbers upto a given number.

def find_perfect_numbers(def number) {
(2..number).findAll { x-> (1..(x/2)).findAll{ x % it == 0 }.sum() == x }
}

assertEquals(find_perfect_numbers(10000), [1,6,28,8128]

The internal closure finds all the factors of a give number, while the outside closure finds all those whose sum is equal to that number.

Groovy OLC #2 – Strand Puzzle 1914

I think it was the year 1986 when I participated in an interschool programming competition in Chennai. I wasn’t very good at math, but I did tag along with a couple of my friends who were darn good at it. There were three problems given that we have to solve using GW-BASIC in about 30 minutes. There were probably 100 participants. I did get a peep into a few poor guys inside the computer room who were typing our solutions into the computer blindly and see if they worked. I just remember only one of the problems. I didn’t get the correct solution, but one of my friends – Sowmy Srinivasan, did and win the competition.

Years later, I learned that this was a very interesting puzzle tackled by the genius Srinivasa Ramanujan. In the year 1914, PC Mahalanobis, a Kings college student in England, got hold of a puzzle from the Strand magazine.

“In a given street of houses with consecutive numbers between 50 and 500, find the house number, for which, the sum of numbers on the left is equal to the sum of numbers on the right”

In other words, given ‘n’ number of houses, find the house number ‘m’ that would sum(1..m-1) = sum(m+1..n).

Mahalanobis solved the problem by trial and error and went to Ramanujan to show it. Ramanujan was cooking some vegetables in the pan. The instant he heard the problem, Ramanujan, while still frying his veggies, not only gave the answer to the puzzle, but also provided the generic formula that would give infinite number of solutions. The problem belongs to the area called Continuous Fractions and is very fascinating. The problem can be reduced to x*x – Dy*y = ±1 and has been tackled by ~10th century Indian mathematician Brahmaguputa using a method called chakravala. I will probably write up on the “chakravala” method later. The Ramanujan anecdote is documented in several places on the net and a simple search will provide more interesting details.

So I was working on something in Groovy, I suddenly got reminded of this problem and was thinking if this can be solved as a Groovy OLC. I am going to use the brute-force method rather than solving via the quadratic equation, because it nicely demostrates the List capabilities of Groovy. It does run slow for large numbers, but speed or optimization is not the point here.

So here is Groovy OLC #2 – Ramanujan’s Continuous Fractions (via brute force method)

public test_ramanujan_continous_fraction() {
(1..100).each { n, houses = 1..n -> houses.eachWithIndex {m, i -> if (houses.subList(0,i).sum() == houses.subList(i+1,houses.size()).sum()) println "house# = $m, total_houses = $n" } }
}

Result:
house# = 1, total_houses = 1
house# = 6, total_houses = 8
house# = 35, total_houses = 49

Ignore the first one, as I am not bothered about boundary conditions, though its technically correct.

[6,8] = sum(1..5) = sum(7..8) = 15
[35,49] = sum(1..34) = sum(36..49) = 595

Lets retest it with the actual problem from the Strand magazine:

public test_ramanujan_continous_fraction() {
(50..500).each { n, houses = 1..n -> houses.eachWithIndex {m, i -> if (houses.subList(0,i).sum() == houses.subList(i+1,houses.size()).sum()) println "house# = $m, total_houses = $n" } }
}

Result:
house# = 204, total_houses = 288

This is the actual solution that Ramunjan gave instantly to the Strand’s puzzle.

From Groovy’s point of view, the most interesting thing is the second argument in the first closure – “houses” – is actually a variable defintion which is a function of the first argument, ie houses = f(n) !!!

Groovy OLC #1 – Prime Numbers

It is interesting how formatting conventions keep changing with the programming languages. I’m not talking about naming conventions, but just text formatting conventions aka code-layout conventions.

In Java, you dont commonly see beginning separate braces in a new line, although its okay for the ending braces. While in .NET, its a norm to have curly braces in separate lines. Inline code is also very rare in Java and .NET, except for get and set, but in Groovy/JavaScript, it seems to be a very common occurrence. Some of these conventions evolve as a tradition and some right from the invention. In Pascal, structured code was considered art. In Python block indentations are obligatory. Code format conventions, just like naming conventions are very subjective and sometimes personal and if a team cannot agree on one, its a rough road. Although some modern IDE-s have smartened up and present the personalized formatted code to the developer, while the source control would store a standard version. Some of the preferences are driven by language features too.

Closures, especially compact ones, are very intriguing when presented in a single line and some times very challenging. Solutions to puzzles and problems when rewritten in a single line look very catchy. Those who have coded in Prolog would perhaps realize what it means to say that a piece of code is work of art. You can do a regular findBy logic in Prolog, but doing it “Prolog”-way via predicates is certainly challenging.

So here is a One-Liner-Closure (OLC) that calculates the prime numbers > 2.

Given: a list of natural numbers
Find: all the prime numbers

void find_prime_numbers() {
def list = 1..100
println list.findAll { x -> (2..Math.sqrt(x)).every { x % it != 0 } }
}

Result:
[3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

Groovy #4 – A list of map of lists OLC

Find key by value in a map with a list of values

One of the greatest assets of Groovy syntax is how easy it makes to manipulate lists and maps. In fact, the second most clumsy part of Java syntax and implementation are the Collections. The Calendar takes the honors. Collections are functional, but very cumbersome and laborious to implement, ie when compared to Groovy. Even if one is hesitant to learn functional programming or succumbing to the Obsessive Closure Designer syndrome, it is illustrative to know how easy it is to manipulate collections in Groovy.

def mapOfListValues = [a:[1,2], b:[3,4], c:[5,6], d:[7,8]]

So find the key to which a given number belongs to and return a default value if not found.

def findKey = { value -> (mapOfListValues.find { value in it.value }?.key)?:'Not Found' }
assert findKey(3) == 'b'
assert findKey(10) == 'Not Found'

My friend says that I should also put equivalent Java code to lighten up readers’ minds :-). So here goes …

HashMap<String, List<Integer>> mapOfListValues = new HashMap<String,List<Integer>>() {
{
put("a", Arrays.asList(1,2));
put("b", Arrays.asList(3,4));
put("c", Arrays.asList(5,6));
put("d", Arrays.asList(7,8));
}
};

public String findKey(...) {
blah blah, iterator, find, check if rest of world is not null,  catch exceptions and then a lot of code goes here
}

Yawn… you get the point..