The results of a certain very popular examination has just been released. The system for allowing candidates to access the

]]>The results of a certain very popular examination has just been released. The system for allowing candidates to access the results online is curiously hosted on a free instance over at Heroku. Everyone who took the exam is curious to know how they stack up against their peers and everyone in the general public wants to know how someone they know performed. Unfortunately, the results interface requires knowing the roll number of the candidate whose result you wish to view. This is problematic, so we wish to scrape the results website and create a list that allows people to view the result by name as opposed to by roll number.

The range of valid roll numbers is from 2 to 9999. While this range is small enough that building a distributed web crawler would be massive overkill, the range of roll numbers in real world applications is going to be large enough that any other method would take way too long to finish crawling.

In StormyCloud, you break up your problems into 4 different parts: `split`

, `map`

, `reduce`

and `finally`

.

`split`

breaks your problem into a number of smaller sub-problems that can be executed in parallel. `map`

will execute a single sub-problem. As the result of each computation comes in, `reduce`

is run with the task and the result — this is a good place to save results however you like. Once the job is complete, the optional `finally`

code is called.

```
require 'stormy-cloud'
StormyCloud.new("square_summation", "10.6.2.213") do |c|
c.split { (1..1000).to_a }
c.map do |t|
sleep 2 # do some work
t ** 2
end
c.reduce do |t, r|
@sum ||= 0
@sum += r
end
c.finally do
p @sum
end
end
```

Let’s go through this example step-by-step. We specify (on line 3) a string that describes the job and the IP address of the central server. The `split`

block specifies how to break the problem into a number of sub-problems — in this case it returns an array consisting of the numbers 1 to 1000.

The `map`

block accepts a single task, does whatever work needs to be done and returns the result. In this case, it sleeps for 2 seconds to simulate doing work and returns the square of the number.

The `reduce`

block is called with a task and its result the moment the central server recieves the result of the computation from a node. Instance variables will persist between calls of the `reduce`

block — in this case we set up an instance variable called `@sum`

. (For those of you who are not familiar with Ruby, instance variables are the ones which start with an `@`

sign, and `@sum ||= 0`

basically means “if the variable `@sum`

has not been set, initialize it to 0”.)

The `finally`

block is called after all the central server has recieved the solution to all of the sub-tasks. It is not *mandatory* to specify the `finally`

block, but it is a good idea to do so because the value returned by this block is considered the result of the computation and will be displayed in the dashboard.

StormyCloud is packaged as a Ruby gem. First, make sure that all machines involved have a recent version of Ruby installed (I’ve only tested 1.9.3).

You need to install the Sinatra and MessagePack gems in addition to StormyCloud, so run something like

```
$ gem install sinatra msgpack stormy-cloud
```

Depending on your setup you might have to prefix a `sudo`

or `rvm all do`

to that command.

Save the following code as `square_summation.rb`

.

```
require 'stormy-cloud'
StormyCloud.new("square_summation", "localhost") do |c|
c.config :debug, true
c.split { (1..1000).to_a }
c.map do |t|
t ** 2
end
c.reduce do |t, r|
@sum ||= 0
@sum += r
end
c.finally do
p @sum
end
end
```

This the exact same example from before, except that the sleep has been removed, the address of the central server has been changed to “localhost” and the code has been configured to run in debug mode. Now, in your terminal, run:

```
$ ruby square_summation.rb
```

After a short time, you will see the result 333833500. In debug mode, the code is run sequentially on a single machine. It is useful to run a subset of the problem in debug mode to test your code.

Now, let’s run it in distributed mode. Remove the line `c.config :debug, true`

, save the file and run:

```
$ ruby square_summation.rb server
> My identifier is e774c67612a5e4fce61c96897960f83f.
> Running in server mode.
>
>>> Starting dashboard.
== Sinatra/1.3.2 has taken the stage on 4567 for development with backup from Thin
>> Thin web server (v1.4.1 codename Chromeo)
>> Maximum connections set to 1024
>> Listening on 0.0.0.0:4567, CTRL+C to stop
```

You can now navigate to the dashboard to check out the progress of the job.

Spawn a few nodes on your computer by running the following command a few times:

```
$ ruby square_summation.rb node
```

Let’s get back to the original problem, scraping results.

Luckily, a web scraper fits into the StormyCloud paradigm with a lot of ease. We “split” the problem into a task for each roll number. We “map” over each task, returning an array of the candidate’s name and result. We “reduce” these results by writing them to text file, and omit the finally block.

The only work left to do at this point is to actually get the result for a given roll number; we do this using Net::HTTP. We drop down to `irb`

to play around a bit.

```
1.9.3-p194 :001 > require 'net/http'
=> true
1.9.3-p194 :002 > uri = URI('http://results.herokuapp.com/result')
=> #<URI::HTTP:0x007f8b238a97a0 URL:http://results.herokuapp.com/result>
1.9.3-p194 :003 > res = Net::HTTP.post_form(uri, 'rno' => '4')
=> #<Net::HTTPOK 200 OK readbody=true>
1.9.3-p194 :004 > p res.body
"<h1>Result</h1>\n <p>The name is <strong>bitobi</strong>.</p>\n <p>The result is <strong>13862</strong>.</p>\n <a href='/'>Back</a>"
=> "<h1>Result</h1>\n <p>The name is <strong>bitobi</strong>.</p>\n <p>The result is <strong>13862</strong>.</p>\n <a href='/'>Back</a>"
1.9.3-p194 :005 > res.body.split('</strong>')
=> ["<h1>Result</h1>\n <p>The name is <strong>bitobi", ".</p>\n <p>The result is <strong>13862", ".</p>\n <a href='/'>Back</a>"]
1.9.3-p194 :006 > res.body.split('</strong>')[1..2]
=> [".</p>\n <p>The result is <strong>13862", ".</p>\n <a href='/'>Back</a>"]
1.9.3-p194 :007 > res.body.split('</strong>')[0..1]
=> ["<h1>Result</h1>\n <p>The name is <strong>bitobi", ".</p>\n <p>The result is <strong>13862"]
1.9.3-p194 :008 > res.body.split('</strong>')[0..1].map {|x| x.split('<strong>')[1] }
=> ["bitobi", "13862"]
```

This leads to the following code. We initially scrape the results for only a subset of the roll numbers in debug mode to make sure everything works alright.

```
require 'stormy-cloud'
require 'net/http'
StormyCloud.new("web_scraper", "localhost") do |c|
c.config :debug, true
c.split { (2..5).to_a }
c.map do |roll_number|
uri = URI('http://results.herokuapp.com/result')
res = Net::HTTP.post_form(uri, 'rno' => roll_number.to_s)
res.body.split('</strong>')[0..1].map {|x| x.split('<strong>')[1] }
end
c.reduce do |roll_number, result|
File.open('result', 'a') do |f|
f.puts "#{roll_number} #{result * ' '}"
end
end
end
```

Note that we don’t need to manually handling locking the `result`

file in the `reduce`

block, because StormyCloud does that for you using a Mutex. Running the code, we can see that it works correctly.

```
$ ruby web_scraper.rb
$ cat result
2 bekube 6931
3 bihewo 10986
4 bitobi 13862
5 bofuzu 16094
```

Since we can see that the code works correctly, we can now set up the code to run in parallel. To do so, we only need to change “localhost” to the correct IP address of the central server and update the `split`

block to cover the entire range of roll numbers. After this all that is left to do is to copy `web_scraper.rb`

to each of the workers and spawn a node after starting the central server.

Go ahead and try it out! :)

]]>In this post I will assume

]]>Animus is an AI programming contest I organized during Exodia 2012, along the lines of the Google AI challenge. This post will get you started with the contest Animus. The goal is to write a bot that will play the game “Dots and Boxes”.

In this post I will assume that you understand the game. If you don’t, please read this page and come back.

From here on, the term “size of the board” will always mean the number of dots along each edge, not the number of boxes. The game board will always be a square.

Each dot is assigned a single number. The top-left dot is assigned 1, and the number is incremented by one as we move to the right (like the periodic table).

The image below shows a 4×4 board, along with the labels assigned to points.

Your submission must include a function `move`

which accepts a single parameter `board`

. `board`

is an object that contains 3 members: `size`

is a single integer that denotes the size of the board, `connections`

is an array that consists of moves that have been performed so far (this is described below), and `valid_moves`

is an array of moves that your bot can legally perform at this point.

Your function must return a single “move”, which is basically an array of two integers which correspond to the dots you wish to connect. For example, `[1, 2]`

will connect the top left dot and the one immediately to its right. `board['valid_moves']`

and `board['connections']`

are arrays of moves of this sort.

Here are two sample bots: one which will perform the first valid move it is provided, and another which will perform a random move.

```
function random_element(myArray) {
return myArray[Math.floor(Math.random() * myArray.length)];
}
function move(board) {
return random_element(board.valid_moves);
}
```

```
function move(board) {
return board['valid_moves'][0];
}
```

This package will allow you to test variations of your bot locally. The tool requires that Java is installed on your computer. It has been tested on OS X (Lion), Linux (Ubuntu and Arch) and Windows (Vista). It should be able to work on any other platform as well, if you are having trouble please leave a comment below.

The package contains a JAR file and a directory. The JAR file should be run using the command:

```
java -Djruby.compat.version=1.9 -jar local_tournament.jar [size]
```

You should replace `[size]`

with the size of the map you wish to use. You should probably run it using a size of 10, because that is the map size the tournament will be using. Do not omit the argument, doing so will result in the map size being set to 0, which is quite useless.

Name | Score |
---|---|

egreavette | 18 |

a_iitmandi | 17 |

ignite | 16 |

rohanag | 16 |

abracadabra | 8 |

animator | 8 |

aounon | 8 |

saikiran | 8 |

saint3k | 8 |

shalmezad | 8 |

shapeshifter | 8 |

vesper_sword | 8 |

123 | 4 |

maggot092 | 4 |

randombot | 4 |

rohitgupta_hpf | 4 |

sukrit | 3 |

chamun | 2 |

gopi | 2 |

shubham929 | 2 |

Replays from the tournament can be downloaded from here or here. Note that the replays might not work display directly in the newest browsers, you will need to replace `history`

with `history_`

first.

You are working on a new “RPG Hero Name Generator” application. In order to generate the names, rather than going for a

]]>Obfuscation is a contest in which the goal is to solve a given problem with the smallest amount of C code possible. Congratulations to the winners!

You are working on a new “RPG Hero Name Generator” application. In order to generate the names, rather than going for a dictionary approach you decide to explore something more along the lines of Markov-chain text generation. Since you are generating character names rather than paragraphs, you treat each character as a state, and in order to simplify matters you make the assumption that each letter is independent of all of the letters coming before it except for its immediate predecessor.

The input consists of two lines. The first character of the first line is the character to be considered. The rest of the line will consist of an arbitrary number of characters, this is the sample of text to be considered. Ignore the content of the second line. You are to output a single character, the one which occurs most frequently after the given character in the sample.

The number of characters is small enough that you need not worry about exceeding the limits of int. The character string will consist of only uppercase or lowercase alphabets, you will not encounter any other characters.

Despite the amount of jargon present, this is a fairly simple problem. The first paragraph only provides some context, and can be ignored for the sake of solving the problem. All that needs to be done in this problem is to count the frequencies of letter when they occur after a certain given character, and output the character that occurs most frequently.

```
main() {
char c = getchar(), t, p = -1;
int freq[128] = {0};
while ( (t = getchar()) != '\n' ) {
if (p == c)
freq[t] ++;
p = t;
}
for (t=0; t<127; t++)
if (freq[t] > freq[c])
c = t;
putchar(c);
return 0;
}
```

The winning solution by M. is only 101 characters; can you bring this down to that?

You are working on a spam classification system using a new machine learning algorithm that you devised yourself. Surprised by its abysmal performance, you start to investigate how to improve its accuracy. You decide to run a genetic algorithm to pick the best among various variants of your algorithm. You have picked F1-score as the evaluation metric, and need an efficient implementation that will compute the F1-score.

The first line of input to your program will be a single integer m (<= 100) that represents the size of your cross-validation set. This is followed by m lines, each containing two characters. Each character will be either a ‘+’ or a ‘-’. The first character represents the correct classification of an item in the cross-validation set, and the second character represents the output of your algorithm. As you might guess, ‘+’ corresponds to a positive classification and ‘-’ is a negative classification.

Your program is to output the F1-score with respect to the cross-validation set, with two digits after the decimal point. The following formulae might help:

`precision = true positives / (true positives + false positives)`

`recall = true positives / (true positives + false negatives)`

`F1 score = 2 * precision * recall / (precision + recall)`

**Definitions:**

- A true positive is an example that was correctly classified by your algorithm as positive.
- A true negative is an example that was correctly classified as negative.
- A false positive is an example that is actually negative, but which was classified as positive.
- A false negative is a positive example that was incorrectly classified as negative.

This was by far the easiest problem, it got the most submissions by a pretty large margin. The naive solution is shown below.

```
#define eq(X, a) ((X[0] == a[0]) && (X[1] == a[1]))
main() {
int t;
float tp, tn, fp, fn, p, r;
tp = tn = fp = fn = 0;
char c[3];
scanf("%d\n", &t);
while (t--) {
gets(c);
if (eq(c, "++")) tp++;
if (eq(c, "+-")) fn++;
if (eq(c, "-+")) fp++;
if (eq(c, "--")) tn++;
}
p = tp / (tp + fp);
r = tp / (tp + fn);
printf("%.2f", 2*p*r / (p+r));
return 0;
}
```

The size of this solution can be brought down by taking into account, for one, the fact that “true negatives” are never used anywhere. Another thing to do would be to get rid of the intermediate precision and recall computations, and to compute the F1 score directly.

The best solution by Ankit Gupta at 133 characters is truly a work of art. M.‘s solution is also quite amazing, but the second optimization was not used; this increased the size of M.’s submission.

Despite your best efforts, your classification algorithm doesn’t work out as well as you had hoped. Not one to be fazed by failure, you decide to go for a more standard algorithm this time, and after spending a short amount on Wikipedia you pick the k-Nearest Neighbors algorithm because of how easy it would be to implement.

In order to further reduce complications, you decide that you don’t want to deal with implementing kNN in a feature-space with a large number of dimensions, and so you apply Principle Component Analysis to reduce the number of features to one and hope for the best. To simplify the problem even further, you decide to set k=1.

The first line of input consists of a single integer n (< 100), the number of examples. This is followed by n lines each consisting of a single real number and a character (‘+’ or ‘-’) separated by a single space. The integer represents the value of the feature, and ‘+’ or ‘-’ represents the correct classification of the item that corresponds to the feature value.

This is followed by a line containing a single integer m (<= 100), the number of queries. After this there will be m lines each containing a single integer, which is the value of the feature for the item you must classify. For each query output the classification of the example whose feature value is closest to the given integer.

To summarize the problem, you will be given a set of integer-character pairs, and you need to output the character for which the lvalue (the integer which corresponds to the character) is closest to a given integer.

```
main() {
int n, m, k, t=0, i;
scanf("%d\n", &n);
int s[n][2];
for (i=0; i<n; i++)
scanf("%d %c\n", &s[i][0], &s[i][1]);
scanf("%d\n", &m);
while (m--) {
scanf("%d\n", &k);
for (i=0; i<n; i++) {
if ( abs(k - s[t][0]) > abs(k - s[i][0]) )
t = i;
}
putchar(s[t][1]);
}
return 0;
}
```

The best solution was submitted by Abhay Prakarsh, and has 157 characters.

Surprisingly even the nearest neighbor approach didn’t work well. Your faculty advisor says that it is because of your abuse of Principle Component Analysis, but you think it is more due to the fact that kNN is a high variance algorithm, and your dataset is too noisy for it to work well. After some more research, you stumble upon an algorithm called Logistic Regression (a.k.a a single layer perceptron).

The Logistic Regression algorithm basically involves fitting a given dataset to the function `f(z) = 1/(1+exp(-z))`

, where z is the dot product of two vectors: a vector containing the “intercept” and “regression coefficients” and another containing the features. The dimensionality of the first vector is one larger than the dimensionality of the feature space, this is because of the intercept term. There are two ways to treat the bias term: one is to neglect it while performing the dot product and to add it to the result, the other is to add in an extra “1” at the front of the feature vector, which ends up having the same effect as the first method because the intercept is the first term of the first vector, and 1 becomes the first term of the second.

Since this algorithm is to be used for classification, a threshold value T is used: if the output of linear regression is greater than or equal to T the example is classified as positive, otherwise it is classified as negative. You make an arbitrary choice and pick T=0.5.

You have already created the portion of the system that handles learning from the dataset, all that is left is to write the part that makes predictions on new items. The first line of input will contain two space-separated integers: the dimensionality of the feature space (d) and the number of items to be classified (q). This is followed by a line containing (d+1) integers which correspond to the vector with the intercept and regression coefficient. After this there will be q lines, each with d integers that correspond to the feature vector. For each of these q lines you are to output a single character, ‘+’ or ‘-’ depending on whether the input is classified as positive or negative. Both q and d are less than 50.

```
#define classify(x) (((x) >= 0.5) ? '+' : '-')
float sigmoid(float x) {
return 1 / (1 + exp((double) -x));
}
main() {
int d, q, i, a, t;
scanf("%d %d\n", &d, &q);
int beta[d+1];
for (i=0; i<d; i++)
scanf("%d ", &beta[i]);
scanf("%d\n", &beta[i]);
while (q--) {
a = beta[0];
for (i=1; d>i; i++) {
scanf("%d ", &t);
a += beta[i] * t;
}
scanf("%d\n", &t);
a += beta[i] * t;
putchar(classify(sigmoid(a)));
}
return 0;
}
```

Note that is is possible to completely skip computing the sigmoid function, whenever z ≥ 0 the classification would be positive, and when z < 0 the classification would be negative. The best solution by Piyush Kapoor comes in at 166 characters.

Roger challenges Dave to play a game involving coins. In the game, a fair coin is tossed n times. If, during the coin tosses, heads occurs two or more times in a row, Roger would win; otherwise Dave would win.

Dave disagrees with Roger, because as n grows, so does Roger’s chances of winning. Eventually, both of them agree to arrange the bet amounts in such a way that both players end up with an equal expected gain. For this purpose, they need your help. You need to write a program that, for a given value of n, will output the probability of Dave winning the game.

The first line of input will be a number t, the number of testcases. This will be followed by t lines, each containing a positive integer less than or equal to 20. For each integer, output the probability of Dave winning the game. Include 6 digits after the decimal point in your answer.

I am going to omit the derivation, but it can be shown that the probability is F(n+2) / 2^{n}, where F(n) is the n^{th} Fibonacci number.

```
int fib(n) {
return n < 2 ? n : fib(n-1) + fib(n-2);
}
int main() {
int t, n;
scanf("%d\n", &t);
while (t--) {
scanf("%d\n", &n);
printf("%f\n", fib(n+2) / pow(2, n));
}
return 0;
}
```

The best solution by Piyush Kapoor comes in at 136 characters. His solution computes the relevant Fibonacci number using an inline iterative method, and uses bit shifting to avoid calling `pow()`

.

Dennis is programming a robot that is supposed to paint a horizontal line. Not being one to care much about efficiency, Dennis programs the robot to move in an

]]>Dennis is programming a robot that is supposed to paint a horizontal line. Not being one to care much about efficiency, Dennis programs the robot to move in an anti-clockwise spiral as shown below.

The robot starts at position zero, then moves to position 1, then position 2 and so on. Dennis wants all of the tiles to the right of 0 to be painted black. (These tiles are represented as bold numbers in the figure above.)

Your task is to help Dennis by telling him which is the n^{th} tile that must be painted black, with the zeroth tile being zero.

The spiral in this problem is constructed in the same way as Ulam’s Spiral. With a little bit of derivation, you can see that the n^{th} spiral number is given by 4n^{2}–3n.

```
gets.to_i.times do
n = gets.to_i
puts 4*n*n - 3*n
end
```

Galileo’s latest project involves determining the density of stars in certain regions of the sky. For this purpose he started looking for datasets online, and discovered a dataset on Newton’s blog. Newton had decomposed the night sky into a Voronoi tessellation with the generators arranged in a grid. He has stored the number of stars in a Voronoi cell at a position in a matrix that corresponds to the position of the generator in the grid.

This dataset does not directly help Galileo, because he needs to be able to query the number of stars in a rectangular portion of the sky. Galileo tried to write a program that does this on his own, but it turned out to be too slow. Can you help him?

This problem would have been far more interesting with a stricter time limit. As it is now, even solutions that take the naive approach of looping over the relevant section each time would be accepted. A more efficient way of solving this problem (given that there would be a large number of queries for a single dataset) would be to construct a “dominance matrix”, in which each element of the matrix `D[x][y]`

is the sum of all elements of the dataset `A[i][j]`

with `i ≤ x`

and `j ≤ y`

. Using this approach, the doubly nested loop in the naive approach can be replaced with four array lookups.

```
a, b = gets.split.map {|x| x.to_i }
data = []
a.times do
data << gets.split.map {|x| x.to_i }
end
gets.to_i.times do
px, py, qx, qy = gets.split.map {|x| x.to_i }
sum = 0
for x in (px-1)..(qx-1)
for y in (py-1)..(qy-1)
sum += data[x][y]
end
end
puts sum
end
```

Useless Fencing Inc. has recently scored a contract to create a fence around a bunch of sheep in light of recent wolf attacks. As implied by their name, Useless Fencing tries to use as little fencing material as possible.

In order to determine the location of each of the sheep, Useless Fencing has deployed a system consisting of laser range-finders. This has given them the location of each of the sheep, however because of errors inherent in the system, they only know that each of the sheep is inside a square of side 2 units. (Note that the orientation of all of these squares is identical, and the coordinate system has been selected so that each of the sides are parallel to one of the axes.)

The sheep are rather lazy (they never move), but none of them should be left outside the fence. Your task is to determine the minimum possible length of the fence.

This problem boils down to finding the Convex Hull. Finding the convex hull of a set of points in a plane can be thought of as stretching a rubber band so that it covers all of the points, and then releasing it so that it becomes taut. This image will probably be helpful in understanding the rubber band analogy.

There is a slight twist, however, the set of points to be considered is not the set of sheep coordinates, rather it is the set of all of the vertices of the squares that contain the sheep. In other words, each of the given center coordinates of the sheep would be transformed into four different points as illustrated by the image below, and this transformation should be applied to each one of the sheep coordinates. We would then find the length of the convex hull of the resulting set of coordinates, which would contain 4 times as many points as the original set of coordinates.

Jarvis’s march will suffice for solving this problem, but you may also consider more sophisticated algorithms like the Graham’s Scan. Jarvis’s march is much simpler to implement, and choosing it over Graham’s Scan means that precious time is saved.

Gray codes were invented to prevent spurious output from electromagnetic switches. Consider the number 3 in ordinary binary encoding: when incremented from 011 to 100 it is unlikely that all of the switches will change states at the same time, so there is a possibility of reading the state of the variable while it is in between a transition (i.e., when some of the bits have flipped to the correct value but others haven’t).

To solve this problem, Frank Gray introduced a new number system in which successive numbers differ by only a single bit.

You are working on a legacy system that uses Gray codes, but are having difficulty fixing a bug related to multiplication of numbers. For the purpose of debugging, you wish to convert a number’s Gray encoding into the corresponding decimal representation.

This page has a number of interesting applications of Gray Codes. I think Karnaugh maps are the most interesting, they are used to solve boolean minimization (the problem of minimizing logical circuitry).

```
#include <stdio.h>
int gray_decode(int n) {
int p = n;
while (n >>= 1) p ^= n;
return p;
}
int main() {
int t, c;
scanf("%d\n", &t);
while (t--) {
scanf("%d\n", &c);
printf("%d\n", gray_decode(c));
}
return 0;
}
```

To test a new cloud computing service, you decide to write a program that generates the Pascal Triangle in a distributed fashion.

You wish to estimate the amount of network traffic that would be expected between nodes. Since the nodes exchange the computed values in base 10, you want to know the number of digits in the base-10 representation of nth row and rth column of Pascal’s triangle. Since your program internally represents these in base-2, you also wish to know the number of digits in the base-2 representation to get an idea of the memory usage involved.

The name of this problem is a play on the term Software as a Service. The number of digits a number n has in base b is floor(log_{b}(n))+1.

```
def ncr(n, r)
a, b = r, n-r
a, b = b, a if a < b # a is the larger
numer = (a+1..n).inject(1) { |t,v| t*v } # n!/r!
denom = (2..b).inject(1) { |t,v| t*v } # (n-r)!
numer / denom
end
def ncrdigs_naive(n, r, base)
ncr(n, r).to_s(base).length
end
gets.to_i.times do
n, r = gets.split.map {|x| x.to_i }
puts "#{ncrdigs_naive(n,r,10)} #{ncrdigs_naive(n,r,2)}"
end
```

A balanced prime is one which is the average of the previous and the next prime number. Your task in this problem is to write a program that can calculate the n^{th} balanced prime.

This is the sort of problem that looks like it was meant to be solved in Haskell.

```
minus (x:xs) (y:ys) = case (compare x y) of
LT -> x : minus xs (y:ys)
EQ -> minus xs ys
GT -> minus (x:xs) ys
minus xs _ = xs
primesPE = 2 : primes'
where
primes' = sieve [3,5..] 9 primes'
sieve (x:xs) q ps@ ~(p:t)
| x < q = x : sieve xs q ps
| otherwise = sieve (xs `minus` [q, q+2*p..]) (head t^2) t
primes_triplet = map f [1..]
where f x = (primesPE !! (x - 1), primesPE !! x, primesPE !! (x + 1))
balanced_primes = map g $ filter f primes_triplet
where f (a,b,c) = 2 * b == a + c
g (a,b,c) = b
main = interact g
where g x = unlines $ map show $ map nbp $ drop 1 $ lines x
nbp x = balanced_primes !! ((read x) - 1)
```

The first two definitions (`minus`

and `primesPE`

) are taken verbatim from this page. There are far more efficient implementations on that page that can be dropped in, and doing so will make the program run faster, because generation of primes is the bottleneck. `primesPE`

is an infinite list of primes. `primes_triplet`

uses `primesPE`

to create another list that contains triplets of prime numbers. `balanced_primes`

applies a filter to this list of triplets, selecting only those for which twice the middle element is the sum of the extreme elements, and then selecting only the middle elements of those triplets. The final definition, `main`

, handles IO and can be ignored.

The infinite lists take care of memoization, so that values will not be unnecessarily recomputed. The Haskell code sample above feels almost like *declarative* programming, in which you specify what you want computed rather than how to compute it.