swap them like a sir

some days ago, during a quite pleasant job interview, I was asked for the third time an interesting (and simple) brain puzzle. having successfully solved it before (the last time about 1 year ago), I was confident I would eventually come to the solution quickly. actually that didn't happen and after struggling with the question for some time, one of the interviewers kindly put an end to my efforts (even though I felt I was almost getting it - or was I?) and offered the right (and simple) solution.

this episode made me realize how ephemeral (my) knowledge is. there I was, in a privileged position, having already answered the question, knowing the basics of how two possible methods would solve the problem, and yet that previous experience was of no use to my performance. could it even have been self detrimental in a way that I was trying to recall previous memories and that "past-event familiarity feeling" instead of actually trying to solve the puzzle? this obviously upset me and I spent the most part of the day feeling dumb for missing something that I was so clearly supposed to know. eventually I began to question why did this happen and what other examples of supposedly acquired knowledge could (momentarily?) be just "phantom memories"?

first of all, I guess the context of a job interview and the 2-hour sleep the night before didn't really help me in this situation. still, I don't think that was sufficient to justify my major fail on that problem as I was able to correctly answer several other questions during the 1.5 hours of interview. there had to be more than that to it.

the subject of human memory, how it works and what influences the creation and recall of memories is still only vaguely understood. numerous factors influence our ability to encode, store and recall memories. for instance, walking into another room can easily constitute an "event boundary" that diminishes your ability to recall memories from the previous room.

in my case, I think the problem occurred during the encoding process. my previous solutions to this problem were reached without caring too much about the method used. I just saw it as an interesting riddle, and solved it while multitasking and without paying too much attention to how my thought was being organized. I also failed to integrate the solution with previous knowledge which may have hindered my ability to migrate the solution to long-term memory (which usually occurs during sleep).

ergo, trying to avoid doing the same mistake for the third time, I am writing this article as an experiment and expecting to be able to finally organize and move this little bits of information into long term and easily recalled memory. let's see how it goes.


the problem: given 2 variables: x = a and y = b, swap their values without recurring to any other variable.



first solution - XOR swap algorithm

starting with the end, here is the solution:

x_1 = x \oplus y = a \oplus b


y_1 = x_1 \oplus y = (a \oplus b) \oplus b


x_2 = x_1 \oplus y_1 = (a \oplus b) \oplus ((a \oplus b) \oplus b)

it works. you can try it. but more interesting than that is understanding how it works.
the "exclusive or" \oplus is a logical operation which returns true if the operands are different, and false otherwise.

in order to better understand the process let us make a and b store just one bit. in this case x_1 = x \oplus y = a \oplus b would produce the following true table:

a\b 0 1
0 0 1
1 1 0

this stores the meaning of the XOR (\oplus) operand, "whether a is different than b", in x_1. the second operation, y_1 = x_1 \oplus y = (a \oplus b) \oplus b gives us this second table:

a\b 0 1
0 0 1
1 0 1

as you can see, whatever the value of a, (a \oplus b) \oplus b will always give the value of b. take a moment to think about what does this conclusion really mean.

if a is different than b, a \oplus b = 1, and y_1 = 1 \oplus b, which is actually equivalent to the result of the english expression "is b different than true(1)", or simply, "is b not true", i.e. the negation of b. hence, because a is different than b (a \oplus b = 1) and we are working with single-bit variables, the negation of b is actually a.

if a is equal to b, a \oplus b = 0, and y_1 = 0 \oplus b. this time the expression is equivalent to the result of "is b different than false(0)", or simply, "is b true", i.e. the same logical value as b. knowing that a is equal to b (a \oplus b = 0), we can keep b's value during the swap to a.

applying this same technique to a multi-bit number makes up for the first value swap. y_1 = x_1 \oplus y = (a \oplus b) \oplus b ends up attributing a to y_1.

if we look at the third instruction in our algorithm x_2 = x_1 \oplus y_1 = (a \oplus b) \oplus ((a \oplus b) \oplus b), and knowing, from the previous step, that y_1 = (a \oplus b) \oplus b = a, we can see that this is basically the same as the previous instruction, with the only difference that in this case we have a instead of b as the right operand of the XOR expression. therefore, we can conclude that the result will be the negation of a, if a is different than b, or a, if a equals b. thus, at the end of the instruction, x_2 will always store the value of b, completing our value swap.



second solution - arithmetic
this was the solution that I had explored previously and failed to remember during the interview. I rushed to an empiric, exploratory, try-and-error approach trying to recall my memories, without stopping to think what actually would make sense. after the interview, this is what made sense to me and made the problem absolutely trivial: "distances"!

diagram

by thinking about a and b as two points on a line, and adding a third conceptual variable to the problem representing the "distance" between those points (b-a), we created all the mental tools needed to perform the given task.

we start by storing this "distance" in one of the variables:

x_1 = y - x = b - a

then, we use this variable to change the value of y from b to a by subtracting the difference stored in x_1 from b.

y_1 = y - x_1 = b - (b - a) = a

after this step, we still have the "distance" from a to b in our x_1 variable, so we just need to use it in order to obtain b from a (now stored in y_1).

x_2 = y_1 + x_1 = a + (b - a) = b

and it's done. so easy that it makes me want to forget how I ridiculously failed to solve it. the most probable however is that, because of the role emotion plays in this process, I will more easily remember my bad performance on the interview question, than the solutions above.

... I hope not!

Posted: February 10th, 2013
Comments: No Comments.

multiple Firefox profiles

having multiple profiles on your browser can be useful for many purposes. last week I have created a new profile in order to experiment some add-ons development, but you can also use this feature to debug possible problems with your current Firefox profile. on the other hand, if you are simply the type of person that (like me) can easily clutter the browser with lots of extensions and are an adept of extreme tab browsing, then a clean slate profile may as well come in handy and let you savor a long time forgotten fresh taste of speed.

enough with the talking, here is how it is done:

open Firefox with the -p switch to open up the Profile Manager.

on Windows you can just press Windows+R and then:

there you can create a new profile and afterwards, if you want to have multiple Firefox windows opened at the same time with different profiles use:

to open your second window.

more Firefox command line arguments here

Posted: February 4th, 2013
Comments: No Comments.

dreams are made to be done

after sometime neglecting an egocentric need to set up my own domain on this big thing called Internet, and eventually share my passion for the Montenegrin ISO 3166 code, I finally succumbed to the obvious. after all it might make sense to do so even if you are not quite fond of solipsism (but hey, nobody could refuted it till now!).

so folks, feel free to click on things here. it is probably safe. there is not much to see yet, but I want to keep this a little bit interesting (not too much though). for now you can just see how beautiful my CV/resumé became after a nice face lift kindly performed on a late night with the cool modernCV package (yeah it's LaTeX!), and some old content from my MSc thesis (it's in Portuguese though). unfortunately the entire report is still a matter of national security and Ian Fleming won't let me release it for the next 1.5 years.

that's about it for now. I hope you find the time to make this your favorite website ever (yes, the one you check daily on your smarphone even before getting out of bed) and see more posts of me linking to stuff.

welcome to my blog.

André.

Posted: January 12th, 2013
Comments: No Comments.