Friday, January 20, 2017

MatheMonsters

It’s Monday again. The weekly tests plague us...me. Not this time though; this time it’s the lovable creatures of Math. Everyone seems to think that they are monsters, but they are beautiful creatures. If you ask them they would tell you anything, but you have to understand their language to be able to ask them. Even our teacher thinks that this particular species of knowledge is a monster. Little does he know about the conversations I've had with them. My mother told me once that one should always try to understand. That the world is a knowable place and we must make an effort to understand it. These angels help me do that.
The invigilator hands out our papers. Sheets of wood beaten into submission so that we may give existence to what would otherwise only be in our minds. Human arrogance at display again. We would kill, only to make our thoughts known; for if you die without doing that, nobody would remember your memories. The first question asks me to define Pi.
I remember the class where our teacher told us that Pi is 22 parts divided into 7 pieces. Oh the confusion I had had that day! If that is all Pi is why does it have a name? What is so special about 22/7 that it deserves a symbol to name it? Where is the equality among those who belong to the species of mathematics? No! There must be something else about it, something which all the other mathemonsters have deemed worthy of their respect.
I asked mum about Pi. She does not usually now a lot about math but there is no other person who has taught me more about it than she has. She tells me that I was right; that Pi was a special bird. She does not remember what was special though. I take to the Internet. As long as I write well formed sentences and Google before I ask, I pass as a respectable adult here. My questions are taken seriously.
“Question 1. Define Pi. (2 marks)”
A statement so simple for those who do not understand. Oh what joy to be able to answer it! To simply write 22 / 7 or perhaps the circumference / diameter for those who pride themselves in going a step further than the rest. It would be lies of course. Pi herself is laughing at everyone present. They all take her for 22 / 7 and we both laugh at the private joke.
Pi is everything and nothing at the same time. I can only see her face which starts with 3.14.... and as I look lower I lose my ability to see her. I can look at parts of her but then the others disappear. I am thankful for even this. The Internet tells me that people like me, those who could see and communicate with the mathemonsters could not even see that earlier. They had to always start at the face and go down from there. Any second that you take your eyes off and she would disappear. It was some men who later discovered a way to look at any part of her without looking at her face to start with. This sight came at a cost obviously; we could not look at her as a whole.
Pi is an infinite being. She never ends. Starting with the face, as you get further and further away you would see more and more of her and yet never come across a part which seems familiar for she is a never ending and never repeating number. She is of the irrational clan. She mentioned e once but I haven’t met him yet.
If I was to manage to look at all of Pi at once. If I was to mark the even parts of her as 1 and the odd parts as 0, I might have something like a computer’s code. Pi however, because of her nature would have given me all the knowledge in the world. If you can look at Pi; you would have all the knowledge in the world.
The name of my great great grandfather. How did Bose die? Are we alone? When will I die? Who would be my friend? All of these Pi would tell you, you only have to look at her once. But these feeble eyes of mine don’t allow me to do that. This beautiful woman who promises me an understanding of everything, lets me have nothing as long as I cannot look at her. As long as I don’t understand all of her.
She is everything and nothing at the same time. She is all that I want to know, and yet I cannot. My future, my past, my love, my hate; all is known to Pi and she tells me nothing.
“Everything and nothing”
That’s how I managed to fail most of my tests. People kept telling my mum that she needed to put me into tuition, but both her and Pa knew that tuition would do me more harm than good. They would blind me and have me believe that the mathemonsters are nothing more than monsters. They would reduce pi to 22 /7 and e to a benign number. They would label the other numbers as complex and lend us faith in their non existence. They would never let me know about the family relations of the clan of irrationals and the complex. They would hide from me the love expressed within e^iπ = -1

Wednesday, December 28, 2016

Rain

As I walk out of my room, I am greeted by this winter rain. A soft spray of cold water caresses my jaw while I move along the balcony, as if to cajole me into joining it in it's emotion.

The wind whips up the beads of sweat born from seasons past into a frenzy so great they conceive ghosts of the land crashing against buildings as though to reclaim the earth which is now vertical against it's wishes. The forest in front of me is awash, blushing it's beauty with the rain washing away all that made it forget who it was.

A part of this torrent is caught in my neighbor's rooftop. The thousand droplet soldiers march to the steady drum of the drainpipe relieving itself on the tin sheet placed under it. The sky is painted blue with the deep color that only clouds with filled bellies can bring. A tinge of red peaks out behind the horizon as if to catch one last glimpse of this scene before going to bed.

Humans scurry about their shelters, filling up containers with what I have to spare. The smoke rises from their mounds and meets my gift halfway, mixing and mating with it until it falls back on land not gift and not smoke anymore. Humans. I've watched them since the beginning of time and as a people, they have watched me too. They have inspired in me emotion from time to time and so have I in them.

We are all prisoners, together in this walled reality of capability. What is, can. Thus the both of us trapped, beautiful things.

Thursday, December 8, 2016

Taking a Look at Competitive Programming

Introduction

Competitive programming is a lucrative business if you have the chops for it. It has however been subject to little analysis AFAIK. This has partially been because of the unavailability of consolidated data set to facilitate this. To resolve that I scraped together data from the Codechef website amounting to a little over 1 million programs submitted to the site. You can get the dataset on Kaggle (link to data).

The purpose of this work is to get started with the OpenAI special project which states
Build an agent to win online programming competitions. A program that can write other programs would be, for obvious reasons, very powerful.

To solve a problem, the first step is always to understand the problem and know it's quirks. This blog post is possibly the first of many exploring this dataset with the ultimate aim of being able to generate a solution program given the statement of the problem.

An Exploratory Data Analysis has been done by Swaraj Khadanga. You can see it at Simple EDA.

A brief description of the data

The dataset presents a table with columns as variables and rows as observations, making it tidy in the process. The columns we are interested in are:
  • QCode : The Question Code, denoting a unique question
  • Solution : The program written by the user
  • Status : Was it a correct attempt or not?
  • Language : The language that the code was written in.

Program Visualization

This visualization makes some assumptions, namely:
  • We consider only those programs which were written in C
  • We reduce each program to another string, keeping only keywords and special characters. The idea is to try and get an approximate representation of the Abstract Syntax Tree by obtaining an infix representation of the code.
  • With these program representations as representations of the programs, we calculate the Levenshtein distance between each pair of representations.
  • Using the above data we have a complete graph with each vertex representing a program and each edge being the Levenshtein distance between two programs.
  • Now, we place each vertex in a 2D plane at coordinates such that the difference between the distances between points on the plane and the Levenshtein distance between two points is minimal. This is similar to what has been done by Ben in his post on numerical optimization in the Last cities example.
We plot the points at the calculated coordinates and color them by the problem they were trying to solve. By doing this we arrive on a graph which is shown below.

All I can say at this point is that it's interesting. The X and Y represent nothing of significance. What is significant is the relative distances between the points. Most programs are of a similar structure with very few actually differing a lot from each other.
There will be more on this in later posts. The plot was created using this gist.