Can you make small changes in an unknown language?

If you’re tasked to make minor changes to an existing program in a programming language that you’ve never used before, can you do it? Consider the following fictitious interview question:

You’re writing code in a programming language that you’ve never used before. You have no documentation about the language except the other code. Complete the following function: …

Let’s make this easier. Can you do it if you’re only slightly unfamiliar with the programming language?

When I learned new programming languages, I looked for how to:

  • declare and initialise variables
  • do loops (such as for and while in the C family)
  • do conditionals (the if statement)
  • do multi-conditionals (switch for C#, select case for VB.NET) if available
  • take in input and print output
  • write and use functions

You might have a different list, and that’s ok. It’s how I look for patterns.

With that in mind, if you had sufficient lines of code, you should be able to figure out what the code did. Even if you’ve never seen the programming language before. Then you could make the minor changes you’re tasked with some level of confidence.

It’s not like you code in assembly, right? … Are you?

I don’t have a code sample to show you. Alright fine, I’m too lazy to think up one… Do you have something to show? Post in the comments, and I’ll rack my brains on it…

Puzzle of 7 points and 6 straight lines – 2nd solution

This is the second solution to this puzzle: Construct a geometric shape with 7 points such that there are 6 straight lines, and each line must pass through 3 points. The first solution was already discussed last week.

And here’s the construction:

2nd solution to 7 point and 6 line puzzle

The 7 points are labelled A to G. The 6 lines are ADB, AFC, AGE, DGF, DEC and FEB. No, I didn’t label the points so I’ll have AGE and the short forms of the months December and February. It just happened that way…

The construction starts with point A, and you draw two lines down to get points B and C. The lines AB and AC must be of the same length. Then from point B, draw a perpendicular line to meet line AC. That meeting point is F.

From this construction, angles AFB, AFE, CFB and CFE are right angles (90 degrees).

Do the same thing from point C and draw a perpendicular line to meet line AB, and you’ll get point D. Similarly, angles ADC, ADE, BDC and BDE are right angles.

The point E is formed from the cross point of lines DC and FB that was just formed.

Draw a line joining D and F. Draw another line joining A and E. The cross point of lines DF and AE is point G.

The first solution focused on getting the points right, and then forming lines to fit them. This solution focused on constructing the lines, and the required points magically appear.

On hindsight, we didn’t need the right angles to be there. As long as D and F meet the lines AB and AC respectively in the same ratio, the solution is still valid. There are 2 criteria to meet:

  • Lines AB and AC must be of the same length. This allows symmetry.
  • The length ratios AD:AB and AF:AC must be equal. This is dependent on the previous criteria.

[Update] Yes, that is one heck of a correction. 3 criteria:

  • Points B, A, and C don’t form a straight line (they’re not collinear)
  • D is somewhere on the line AB (and D not equal to A nor B)
  • F is somewhere on the line AC (and F not equal to A nor C)

Then follow similar construction steps for points E and G and as Eric puts it, the rest just happens. Thank you Eric for pointing this out.

Ok, 2 solutions were presented. I hope you had fun reading and thinking about the puzzle.

Response to Stack Overflow podcast 15

The recent Stack Overflow podcast is fantastic! Check it out here. Their fantasticness might have to do with Jeff and Joel answering listener questions more than directionless rambling. Some of the questions were interesting, and I want to add to their answers.

The one on time management

Like Jeff, I don’t really have a system. Like Joel, I got halfway through Getting Things Done and I decided the whole system is still too complex and I could have actually done something already. The concept of transferring tasks from your brain onto something, like paper (have a look at Todoodlist) or a PDA or a computer, is great though. I use my mobile phone to keep track of personal tasks, and the Outlook calendars and tasks to keep track of office work.

That said, my “system” if you want to call it that, is to keep people from annoying me.

Given similar levels of urgency, first do that task which has the most number of people irritating you.

It’s served me well so far.

The one on code review

I’ve never had a code review of my code. It’s not that I’m that good (it helped though), or I’m a pompous buffoon (I’m not). It’s that the people I’ve worked with, don’t care about code quality but more about whether the software worked. When the software failed, or was slow, then the code was checked.

The other reason is the small team I’m currently working in. There’s no one else available to check my code. My team leader trusts that I do my job and I’m grateful for that. The downside is, I don’t have anyone to talk to in my team. I’m the .NET guy! Or the front-end guy.

This is getting depressing. Moving on…

The one on interviews

I don’t know what it’s like in America, where the geographical context of Jeff and Joel’s conversation is. What I do know is, there was only one interview where I had to read and explain some code. It was something to do with string concatenation optimisation in Java. I believe it was an actual production issue, and the interviewers wanted to get a free answer from the interviewees.

Just go prepared. Read up on the company, prepare some questions of your own and revise some of the basic programming stuff. It might look bad if you asked for access to Google so you can find out the parameter signature of a basic function.

[Update] Joel also mentioned something about suits. If you’re not used to wearing office wear, and the company you’re interviewing for requires you to wear suits, well guess what? Practise wearing suits. My current job only required me to wear a long sleeved shirt, pants and (leather) shoes. And belts help too. Don’t you read fashion magazines? *smile* I remember squirming in that alien outfit for my first few interviews because I’m not used to wearing them… Don’t be like me.

I’ve heard of the puzzle questions in Microsoft and Google interviews. I’ve actually had one too. The puzzle had something to do with a cube.

The ones on managerial role and outsourcing

I’m linking them together because my answer is related to both: Offshoring. Occasionally, I’m in charge of a developer stationed in China. I had to write out instructions, program specifications, design layout and database table structures.

The only code reviews ever done was on the code of our Chinese colleagues. We’re (as in the Singapore team) supposed to be training them.

As I understand it, outsourcing means you delegate tasks to another company, usually in another country. Offshoring means you delegate tasks to another part of the mother company in another country.

Oh, you might want to read about my first outsourcing episode.

And that’s all from me. If you hadn’t done so, go listen to the podcast.

Featured demo – Inflorescence

Today’s featured demo is Inflorescence by mfx. Download it here. It’s about 4 minutes in length and 19.5 MB in size.

Since I’ve discovered Capped, I am happy to announce that you can now watch demos even if you have a sucky, I mean, graphics-card-challenged computer.

[Update: If the video doesn’t appear in your feed reader, please click through to the post or go direct to the source. If you know how to embed a video from Capped into an RSS feed so it shows up, let me know.]

My first impression? Very X-Files…

The demo makes heavy use of a technique called bump mapping. It allows you to create detailed surfaces with less polygons. For example, we have here a curved surface:

Surface without bump mapping

Perhaps we want it to be rougher in texture. Instead of pulling and pushing vertices out of alignment on the curved surface, we could use bump mapping. Tada!

Surface with bump mapping

Recalculating vertex normals so that light falls on the surface and create shadows correctly (due to physically shifting the vertices) is expensive. The cheaper way is to use the same 3D model, and add a processing step before the lighting calculations. Thus it looks like the vertices are physically changed, but aren’t.

I take psychic submissions too

I don’t know how to put this. Things have been a little … quiet around here. So I’ve decided to put my analytical and intuitive skills to the test, and hopefully gain some answers…

So, over the past one year or so of blogging, I collected what little information I had. Some emails, some comments, some Stumbles, and a delicious bookmark or Reddit or so.

You are probably from the United States. In fact, you are 41.54% likely to be from the United States (courtesy of Google Analytics). Or you’re 9.35% likely to hail from Harry Potter’s country (urgh… Dementors). Ok fine, I don’t really know anything. You could be from, let me see, Canada, India, Singapore (helllooo!), Australia or some other fine place on Earth.

And now, I’m going to reveal an embarrassing fact. My blog traffic is about 50 unique visitors per day, spiking up once in a while when a post gets Stumbled or Reddit. Page views are about 1900 to 2100 per month. Rest assured you’re more than a web site statistic. I love talking to you (even if you’re a bit shy talking back sometimes…). R.E.S.P.E.C.T.

Despite the low number of web visitors, I have about 35 RSS readers (thank you mem!) and a PageRank of 4. I’m not sure exactly what Google’s algorithm does, but I think 4 is a good value.

Now, the page views thing wouldn’t have been a big deal, until I read Daniel Scocco’s answer to a reader question

6000 page views per month means you are getting around 200 page views daily, right? Well, I think that is a pretty low number for a website that has been online for 3 months. I would aim for some 2,000 page views after 3 months.

Mother of all source code! I’ve been blogging for over a year, and have only about 2000 page views per month. And I’m supposed to have surpassed that after 3 months? Oh man, I so totally suck at this…

Yeah, it’s been a long lonely journey sometimes… Which is why this came in at the right time

Yes, I feel like giving up sometimes. But I know I won’t. And I hope you’ll stick it out too.

You thought I’d stop the math lessons, did you? *smile*

Where was I? Oh right, analysing data. I’ve had someone come through from Dream In Code, highly probably a student. He emailed and asked me a studently programming question and I gave him an answer and pointers. How do I know he’s a student? Because another person asked the same question in the forums. Probably not from the same professional programming team, so rival classmates?

The only thing I wanted to handle better was that I should not have given the answer in the forums too. He came all the way here to ask me something. I should’ve treated him better. So whoever you are, mysterious student, I’m sorry and I should have respected you more.

Speaking of students, my intuitive senses tell me that you are probably in your twenties, probably a student still in school. Yes, I’m guessing, but based on data from the few comments and emails I received (tonality, grammar, and gut feeling). Hah, that’s something Google Analytics don’t have!

Even if you do comment, you don’t put your web site down. You’ve also given me false emails. This is fine, it’s just an observation, and I’m just happy I got a human response. Do you know how deliriously happy I get when I see 3 emails in my blog inbox and I think “Ooh, someone commented/emailed/asked something!” and I expect to find 1 email from a human (because, you know, the other 2 are spam)? I dance around waving my hands in the air for about 10 seconds. I’m not kidding.

There’s this other observation. The no-web-site part. This tells me you are either really cautious, or you really don’t have a blog or web site. Which means I get less links, even if you like my posts (you do like my posts, right?), since you’ve got nowhere to link them from. Well, you could always share a post you like on a bookmarking site or email your friends. Yes I still respect you even if Google or some other web arachnid thinks my blog isn’t worth much.

Combating this undesirable serenity, in my free slots in the space-time continuum of weekends, I practised hard. I pored over ancient texts, meditated on the future of programming, and bent my body into all manner of uncomfortable positions. And I’ve finally achieved it.

Other than my current super power, I am now also psychic! I understand that clicking through from a feed reader to comment on something, or even using my contact form may be too much trouble for you. So I’ve come up with a solution. If it’s too much hassle to submit something to me, then think it to me.

Complementing the 24 by 7 nature of the web, I am now psychically receptive to thought submissions. Because of this new service, I have decided to give up sleeping, which I usually do around 12 midnight to 6 am (1600 – 2200 UTC). I am dedicating this sacred 6 hour period to be attuned to the thought waves travelling around the world to this blog.

No more filling out names, email addresses, web sites, your question/comment, credit card numbers, phone numbers, home addresses! Everything will be autopsychically filled for you! I may look like I’m just lying in bed, but I’m really maximising my psychic receptivity. No, that’s not me snoring.

You can still psychically submit stuff to me in the other 18 hours. I’m just totally devoted to receiving psychic messages from you in the designated time slot.

To encourage submission, I’ll tell you a bit more about myself, so you’ll have fodder for questions.

  • Worked at a startup company for exactly 6 weeks
  • Have more than 5 years of professional programming experience
  • Studied for 4 years in university, majored in Applied Mathematics and Computational Science
  • Worked at 3 distinct companies (I repeated working at one of them)
  • Speak 2 languages fluently (English/Chinese or C#/VB.NET. Take your pick)
  • … And a partridge in a pear tree *smile*

Since I’m new at this, I may not always get your message, or even get the correct message. Psychic receptivity isn’t an exact science, you know. Your best bet is still emailing me directly.

Hmm… and you picked the card Ace of Spades, right?

Puzzle of 7 points and 6 straight lines

My friend presented me with a puzzle: Construct a geometric shape with 7 points such that there are 6 straight lines, and each line must pass through 3 points.

My friend came up with a solution, but he wasn’t sure, so he consulted me. Actually there was a “model” answer, but he wanted to find another solution. So we had 2 solutions. I’ll present that model answer here so you can understand the puzzle better.

Equilateral triangle solution

Points A, B and C form an equilateral triangle. Points D, E and F are the midpoints of lines AB, AC and BC respectively. Point G is the centre of the triangle.

Note: 3 points are collinear if they lie on a straight line.

The 7 points are A to G. The 6 lines are formed by ADB, AEC, BFC, AGF, BGE and CGD.

[I’m not going to go too much into math theories and proofs. Besides, I’m not even sure if I can recall them after losing track for so long…]

The first three lines should be easy to understand. D is the midpoint of AB, so ADB is a straight line. So it is for AEC and BFC.

E is the midpoint of AC, and BE is the perpendicular bisector (remember ABC is an equilateral triangle). And G lies on the line BE, since G is the centre of the triangle. So BGE is a straight line.

Using this reasoning, AGF and CGD are also straight lines.

I know, the explanation I gave isn’t quite backed up with math proofs, more with intuitive reasoning. But I’m sure they are (I just don’t know exactly which theorems to cite…).

So I have 2 favours:

  • Send me a more proper explanation of the solution given above
  • Or send me another solution (remember I have another one?)

I know there are at least 2 solutions. Just wondering if there are more. I will post my other solution, together with any submissions from you next Monday. Or earlier, depending on the number of submissions. You’re welcome to do both. *smile*

Since this is a geometric construction, a picture together with some explanations is appreciated. You can host the image on a site like Flickr, then add a comment to this post with a link to that image and a brief explanation.

Or you can send me your solution via email to vincent at polymathprogrammer dot com. Let me know if you want to remain anonymous (why?), and I’ll just post your solution only.

Your construction doesn’t have to be exact in proportions. Meaning if there’s a right angle, it doesn’t have to be 90 degrees exactly, so long as it looks like it’s 90 degrees. Just add some explanation to supplement the drawing. Try Paint.NET if you don’t have any image editing software.

Have fun!

Multiplications, additions and bit shifts

In a previous article, I asked what this does

int foo(int para)
{
	int temp = para << 3;
	return temp + temp + temp;
}

The function basically returns a value of the parameter multiplied by 24 (thanks Mark!).

So why was it written that way? Speed.

From what I understand, in the olden days, multiplication was slower than addition and bit shift operations. I don't know how slow, but it was slow. It was so slow that programmers (particularly game programmers) started replacing multiplication operations with a combination of additions and bit shifts.

Our example above with 1 bit shift and 2 additions was faster than just 1 multiplication operation. Hmm... that example may not be the best to use... Let me give another one.

The idea is to split the multiplication into additions first. So
i * 80
becomes
i * (64 + 16)
which becomes
(i * 64) + (i * 16)
which becomes
(i << 6) + (i << 4) where we swap multiplications with powers of 2 to bit shifts. See, you do need some math in game programming.

Bit shifts are faster than additions, which are faster than multiplications. The speed difference obtained from rewriting the code was enough for some game programmers to adopt for use.

With modern computer chips, multiplications are just as fast as additions and bit shifts. So I did some comparison. Before I show you the code, there are 2 warnings:

  • The code segments aren't supposed to be tested on their own. The original speed improvements made sense when combined with their surrounding code.
  • Measuring something changes it, so you're not measuring the true value (some principle from physics. If you can find me a reference, I'd appreciate it).

I will present 4 different ways of multiplying by 24 using 4 functions. The first is the one posed in the previous post:

int foo(int para)
{
    int temp = para << 3;
    return temp + temp + temp;
}

The second function uses multiplication.

int goo(int para)
{
    int temp = para;
    return temp * 24;
}

I didn't really have to declare the variable temp. I did it so all 4 functions declare a variable. Even variable declaration takes time, minute as it is, so I had to take that into account and standardise it across the 4 functions. This is the part where "measuring something changes it"...

The third function uses 2 bit shifts and 1 addition.

int hoo(int para)
{
    int temp = para;
    return (temp << 4) + (temp << 3);
}

Convince yourself that the return value is a multiplication of the parameter by 24.

The fourth function is a modification of the first function.

int loo(int para)
{
    int temp = para << 3;
    return (temp << 1) + temp;
}

If bit shifts are faster than additions, temp << 1 is faster than temp + temp, right? The use of temporary variables to hold intermediate values for another calculation is another technique used in game programming. This sounds a little vague, so I'm publishing another article to explain this further.

And here's the timing code

const int cnMax = 500000000;
const int cnLoops = 20;
const int cnValue = 5;
DateTime dtStart = DateTime.Now;
DateTime dtEnd = DateTime.Now;
TimeSpan ts;
int i, j, temp = 0;

temp = 0;
dtStart = DateTime.Now;
for (i = 0; i < cnLoops; ++i)
{
    for (j = 0; j < cnMax; ++j)
    {
        temp = foo(cnValue);
    }
}
dtEnd = DateTime.Now;
ts = dtEnd - dtStart;
Console.WriteLine(ts.TotalSeconds);
Console.WriteLine(temp);

temp = 0;
dtStart = DateTime.Now;
for (i = 0; i < cnLoops; ++i)
{
    for (j = 0; j < cnMax; ++j)
    {
        temp = goo(cnValue);
    }
}
dtEnd = DateTime.Now;
ts = dtEnd - dtStart;
Console.WriteLine(ts.TotalSeconds);
Console.WriteLine(temp);

temp = 0;
dtStart = DateTime.Now;
for (i = 0; i < cnLoops; ++i)
{
    for (j = 0; j < cnMax; ++j)
    {
        temp = hoo(cnValue);
    }
}
dtEnd = DateTime.Now;
ts = dtEnd - dtStart;
Console.WriteLine(ts.TotalSeconds);
Console.WriteLine(temp);

temp = 0;
dtStart = DateTime.Now;
for (i = 0; i < cnLoops; ++i)
{
    for (j = 0; j < cnMax; ++j)
    {
        temp = loo(cnValue);
    }
}
dtEnd = DateTime.Now;
ts = dtEnd - dtStart;
Console.WriteLine(ts.TotalSeconds);
Console.WriteLine(temp);

I've initialised temp to 0 just before the test loops, and printed its value after the loops to check that the calculations give correct results. The loops are coded with a standard structure, and the only difference is the function used. All 4 functions are coded in as similar a structure as possible, to isolate only the method of calculation.

I've used nested for loops to increase the number of iterations. One loop can only go as high as 2^31 iterations (unless I use long). Nested loops increase this limit by doing a lower iteration limit multiple times.

And the conclusion? Multiplications are now just as fast. I didn't get consistent results to rank the methods in order of speed though. Generally speaking, the 2-shift-1-add method (3rd function) is faster than multiply-by-24 method (2nd function).

That's it. As an exercise, you might want to come up with better code to time them. Follow some simple rules:

  • The results must be repeatable
  • Tests must be standardised

A suggestion? Perhaps you can add more code to the loop structure (or the functions). So long as all 4 loops (or function code) are similar, you don't need a minimalistic approach. This allows you to increase the percentage of identical parts between the tests, and thus highlight the difference in only the calculation method (let me know if you're confused by this).

Have fun!

Translating database column names for globalisation

I was working at a software development house where one of those enterprisey .NET web applications was created for a large company. It was fairly standard. There were workflow processes, inventory tracking business logic, user management and the like.

The web application also had to display information in both English and Japanese (the customer was, you know, a Japanese company).

While the database column names were in English, there must be an option to display the Japanese equivalent. Suppose we had a table scripted like:

create table staff
(
STF_ID nchar(10) not null,
STF_NAME nvarchar(100) not null,
EFF_DT datetime not null
)

When I was creating datasets, I used Pascal case as recommended, and typed out words in full. So I had something like

ds.StaffID = "FIRSTID";
ds.StaffName = "Some name";
ds.EffectiveDate = DateTime.UtcNow;

The lead developer gently asked me why I coded that way. I explained the recommended practices for variable naming. I was actually quite puffed up with pride because of that knowledge.

The lead developer said he understood (though I didn’t think he did). Then he gave me an explanation why my method was a bad idea. He said translations for English and Japanese were based on resource files, and the contents of those files were based on the names used in the database tables.

So in the resource file, there would be an entry for STF_ID to be translated into “Staff ID” in English and “sutafu ID” in Japanese.

Staff ID translation (English and Japanese)

If I used “ds.StaffID”, it would be confusing for other programmers because I did some “translating” on my own. Someone else might translate differently and soon, the whole project would go up in flames. A standard way of referring to the database column name was established, and that was whatever the column name was originally. Even if it doesn’t look quite right in code.

So there would be

ds.STF_ID = "ID09183";
ds.STF_NAME = "another robot";
ds.EFF_DT = DateTime.UtcNow;

After some thinking, I had to concede. Using the database column name in code did make sense. There were full-time people hired to enter a code, word or phrase with the English and Japanese equivalent into the resource files. There were many developers working on that project. It’s just more efficient to use the column names as a standard.

That said, there’s much to be desired for the variable naming skills of the database administrators…

Please ConvertToEnglish()

So, I thought it would be interesting to do something different. How about deciphering code? The challenge is to explain a piece of code by giving a minimalist description in English. We’ll practise understanding code with no comments and only the surrounding context as clues.

Here’s the code

int foo(int para)
{
	int temp = para << 3;
	return temp + temp + temp;
}

Explain what the function is doing in the simplest possible way. Don't just tell me what it's doing line by line. Tell me what it finally does.

Post your answer in a comment. Bonus points if you can give a reason why it was coded that way (yes, it has a rational explanation). I'll post my answer in a few days time.

Are you a malleable code editor?

Let me explain malleability by telling you a short story. There was this guy, let’s call him Vincent, who was learning programming and the intricacies of using a Unix machine. The default editor software taught was the vi editor, and Vincent was having some trouble with it.

Copying and pasting was frustrating. Vincent had to remember vi had an edit mode and a command mode. He frequently typed in code and was surprised that a bunch of gobbledegook was on screen because he was in a different mode (the “u” undo command was extremely handy). Even moving up and down lines of code was a challenge (until he found he could still use the direction keys instead of h,j,k,l).

After a while, Vincent could use the vi editor fluently, editing his code with ease and thus able to focus on the logic and code. It’s not as easy as Notepad on Windows. It’s just a little different.

Then Vincent’s classmate and fellow student, let’s call him Paul, said he had a better way of writing code in Unix. “I’m using pico,” he said, as though that was the most sensible thing anyone could do, accompanied with an irritating smug on his face. It had a *gasp* white background with black text, and works similarly to Notepad.

Vincent was like, whatever. He had gotten used to the black background and light-coloured text on the Unix machines, and frankly, didn’t care that the vi editor had that colour palette. In fact, it helped Vincent in distinguishing the Unix and Windows editing environments, simply through a colour distinction.

Paul’s appalling passion for pico was palpably pedestrian. Vincent felt using vi on Unix, and Notepad on Windows was just fine. Of course, Vincent had enough sense to use Dev-C++ instead of Notepad…

Couldn’t let go, or couldn’t adapt?

I found the editing habit of one of my colleagues… intriguing. He’s an ASP.NET developer, or he compiles web applications targeting the .NET framework anyway.

When he needs to edit code, whether it’s the .aspx or the .vb code-behind file, he would open the code file in … Notepad. Or Notepad+. Or some other text editor meant for general use. I can’t remember which.

After he’s done, he would save the file, then switch to Visual Studio and compile the code. Basically, code was edited outside of Visual Studio, and the IDE was used only for compiling and debugging. I still can’t fathom the reasons behind this…

I had another colleague who had another intriguing habit. There were some C++ code files on our Unix machine, where the executable was to run in Unix too. Did he use the vi editor? Of course not.

He would transfer the code files to his computer via FTP. Then he would open them in Visual Studio, the only IDE capable of editing C++ code files on his computer (other than Notepad. We’ve been there. Moving on…). The editing was done in the IDE, never mind the limited Intellisense since the code file was the only file in a “project” as reference.

Since he can’t compile the code anyway (the code references Sybase libraries, which was on the Unix machine), he transferred the code files back into his directory on the Unix machine. Then he switched to the Unix environment and compiles the code.

Is there something wrong with the “indigenous” code editor for that code and environment?

I don’t see a noticeable enhancement for the change in editing tools. So I’m stumped. Perhaps you can provide an answer to the riddle.