Monday, September 27, 2010

Recursion

Twisting. A new way to think and analyze algorithms. Its structure seems that can be exploitable with multicore systems, excepting of course the size of stacks... In essence, Recursion is a function that calls itself until certain condition is met. And this simple essence is still twisting...

You can define a function as:
function hola() { 
echo "hola!";
}
To make hola() recursive, we need to call hola() inside hola():
function hola() { 
echo "hola!";
hola();
}
But if we execute hola() right now, it will execute forever! We still need some condition that stops that infinite recursion:
function hola($n) {
if($n<=0) return;
echo "hola!";
hola($n-1);
}
And then, a recursive function was born. This is a completely too big jump away from sequential programming! Just try to solve factorial, fibonacci, quicksort and backtracking by using loops only, and compare them with their recursive counterparts... Twisting!

The 'Hello, World!' of recursion, Factorial:
function fact($n){
if($n<=1) return $n;
return $n * fact($n-1);
}
Right after factorial, the next example is Fibonacci:
function fibo($n){
if($n<1) return 0;
if($n==1) return 1;
return fibo($n-1) + fibo($n-2);
}
Fibonacci recursion still twists me, just like any QuickSort algorithm:
function qs($list){
if(count($list)<2) return $list;

$less=array();
$more=array()
$pivot=$list[(int) (count($list)/2)];

foreach($list as $e){
if($e<$pivot) $less[]=$e;
else $more[]=$e;
}
return array_merge( qs($less), qs($more) );
}
And, if that was not enough twist, there's also a Backtracking recursive algorithm! You can look an example of it at CodingBat, using Java. Backtracking is useful for solving problems similar to Knapsack and Eight Queens puzzles.
function backtracking($start, $charArray, $counter = ""){
if($start >= count($charArray)) return;
echo $counter, $charArray[$start], '<br />';
backtracking($start + 1, $charArray, $counter);
backtracking($start + 1, $charArray,
$counter . $charArray[$start]);
}
backtracking(0, array("A","B","C","D"));
I am starting to think that recursion (or at least my knowledge of recursion) is still in diapers.

-------

What follows now is a curiosity I found in Python.

I coded a solution for the previous backtrack recursion in CodingBat by using loops and binary numbers. That solution is good for an amount of elements less than 32 (int) or 64 (long) . Python has "unlimited" integers, so I tested if I can create an integer with a googol of bits and typed:

a = 1<<(10**100)
OverflowError: long int too large to convert to int

Experimenting with previous expression, I assume the limit is:

a = 1 << ((1 << 31) - 1)
print a

OverflowError: long is too large to format

This means 2,147,483,648 (more than two thousand millions) elements, an amount still lower than the amount of people in Earth; Although, in terms of integers, with 64 elements (bits), you can express a number like 9, 223,372, 036,854, 775,808 (more than nine trillions), a number good enough for some kind of accounting.

Python can't format and print (1 << ((1 << 31) - 1)), but at least we can know how many digits it has:

import math
math.log10(1 << ((1 << 31) - 1))

646456992.94488049

The number we can express in Python has 646,456,993 (more than six hundred millions) digits! But we can't print it. That number in ASCII string will weight 617MB. The same number in binary storage should weight 256MB, but it seems Python has something like Computational Notation to store binary strings (analogous to Scientific Notation), because it handles these calculations very well.

Bit: data? instruction? element? state? number? group?

Monday, September 20, 2010

The 'Undisputed' eager to fight

I learned and discovered this facet of myself with Nova, because he likes to joke with people too much:
  1. You don't like to be repeatedly touched on your body.
  2. Somebody knows you dislike to be touched.
  3. That person touches you a lot of times.
  4. Your anger rises to the point that you hit that person.
  5. That person uses that attack of yours as an excuse to fight against you.
  6. You show your strength, and that person sees you are strong enough.
  7. Then, that person says that he was simply touching you.
  8. That person also says that you are the crazy one.
  9. As you feel that hypocrisy, you say that person won't be a good friend of yours.
  10. That person sees how you ignore him, and then he wants to be your friend.
Now I understand, in Matrix Reloaded, what Seraph meant when he said: "You do not truly know someone until you fight them."
  • Carlos and Ivans, after our encounters
  • Sasuke and Naruto talk using fists
  • Boyka and Turbo in Undisputed III
  • And tons of stories about supposedly opposite extremes that get acquainted and sometimes they even identify a common enemy.
So, could that initial bothering of people we show be just a unconscious eagerness or impulse from ourselves to get acquainted with that person?

Wow, terrific! How many corners of our subconsciousness will we still keep unexplored?

Saturday, September 18, 2010

My praise for Python language

Disclaimer: PHP is my main scripting tool. I still prefer PHP for things related to HTML. Python threads looks like a total copy from Java's, but some concepts of Python have me dreaming too much...

I like when languages focus on both, problems and users. There are still many other common problems that bothers developers everyday, but I like like when solutions go towards freedom, instead of going towards constraints (although the world itself is a constraint).

Don't you find it rude to use Eclipse, NetBeans, VisualStudio or Zend Studio on EVERY computer you will ever use, only to check the a method's syntax? Programming environments should be cheaper and lighter... nevertheless, these comments looks contradictory...

When you unify several complex concepts into simple principles, you feel a surge of freedom in your brain, head, body, self, ... well, whatever you choose. Well, that's what I felt when I discovered that I can slice arrays the same way I slice strings.
  • If you have no text editor for coding, it brings Python GUI and a prompt to make tests.
  • It forces you to tabulate your code, which makes code looks nicer
  • Nested block delimiters reduced: neither {...} nor begin...end
  • help() and dir() functions: pass any object as a parameter and look.
  • The way you can access your own packages and modules
  • Built-in: highest integer number you can express is limited only by your computer
  • Built-in: complex number calculations (2+3i)
  • Its slicing system for arrays and string, for example: "python"[1:5:2]
  • dict.items() and enumerate(array)
  • Integer division for floating point numbers, without casting
  • You can use named parameters, for example: print my_page(head='Hello', foot='Bye');
Vaguely explored:
  • Its flexible object definitions. It looks more flexible than JavaScript definitions.
  • Lambda
  • Jython and binaries

Tuesday, September 14, 2010

Transforming If Conditions

I feel that breaking logic operations into several 'if' statements are easy to read and follow. But, from time to time I want to transpose them from single 'if' statement to multiple 'ifs' and vice versa. These are some patterns I use.

if(a==1) {
if(b==2{
f1();
}
}
/*AND*/ if (a==1 && b==2) { f1(); }

It looks a nice way to decompose a 'conjunction' (and); but it's not so well with 'disjunction' (or):

if(a==1) { f1(); }
if(b==2) { f1(); }
/*OR*/ if (a==1 || b==2) { f1(); }

But, if you have different conditions that execute the same statements, it's nice to know that you can join them with 'or'.

And now, there's one that annoyed me way too much, the empty 'if' block.

if(a==1) { /*nothing*/ }
else { f1(); }
/*NOT*/ if ( !(a==1) ) { f1(); }

I can remove that 'empty' block by negating the condition; but that extra parenthesis in NOT example looks odd. We can erase it by inverting that condition to:

if (a!=1) { f1(); }

And now, some other inversions of boolean operators:

if(a > b) ... if( !(a <= b) )
if(a >= b) ... if( !(a < b) )
if(a != b) ... if( !(a == b) )

It's fun to see that, if a number is not greater than another, it can, not be only lesser, but also equal; and that, if a number is neither less nor equal than another, then it's greater. Never forget the equal when inverting a less-than and greater-than operators.

Now I understand why the word NOT is never used in boolean variables. Which API method looks good: is_not_good() or !is_good()? Sorry for english language! ;-P

¿NOT is good? -vs- ¿NO está bien?

Sunday, September 12, 2010

Validation Overkill

"The price of reliability is the pursuit of the utmost simplicity. It is a price which the very rich find most hard to pay."
Sir Antony "Tony" Hoare, 1980

People keep inventing new ways of validation, and that's really good! The problem is when they want them all in the whole same form!

[This link] provides an example I have elaborated about what I have called "Validation Overkill."

I will list some overkill principles:
  • State validation constraints, before, while and after:
    before: by using a label, and description of the time of data and its formatting
    while: show errors while typing data, or when changing focus, with Javascript or AJAX
    after: it's normal that back-end rejects wrong data
  • Indicate validation errors. It's normally done by adding a red color to a data field
  • List a summary of errors with anchor links to data fields, normally at the top of the form.
  • Retell errors, just like the while part of validation constraints.
You are right! Of course these principles looks nice enough to take them into account, but there are some inconveniences:

Javascript problems: visibility, library size, duplication of validation code, excesive AJAX
  • Javascript code is visible
  • if libraries are big, they will take time to be downloaded
  • sometimes it's needed to validate twice: front-end and back-end
  • excessive ajax requests can kill bandwidth
User traffic and bandwidth: ajax
  • If your user base is big, it will be a load for your server
  • AJAX is a process running on back-end, not in the browser.
Processor power
  • You would like to squeeze the total capability of the machine, but
  • sometimes to pay for a CPU upgrade, or
  • to buy an extra CPU to use as replication could be a faster way to solve latency
And very important, amount of fields!!
  • because all these rules are present in every field of an input form,
  • and specially if those fields are required
But, as a friend of mine says: "That's what we are paid for!"

Friday, September 10, 2010

Unanimous Rule

"What you have to do, done; and what you have to ignore, ignored. and don't cry for what you will lose."

I was thinking about how could I spend more that RD$ 10MM. A friend of mine said that he would help some people if he receives a great amount of money. In my case, I thought about making contests. I would choose a group of different ethnical people, and choice of the winner must be their responsibility.

I thought it could be a referendum. 70% of participants must agree on the winner. Or maybe the choice must be unanimous, and if someone is in disagreement, that person *MUST* state his/her reasons, and we'll ponder it until everyone is agreed.

One possible problem is that even organizers could cheat! Somewhat, I must interview them in a private and protect them from evil supervisors by controlling the tide of the contest.

I was also starting my ethnical group by creating my "Email Web of Trust", just like when I talked about ToDao: to create a way in which people trust me enough to show me some of their contacts to show the world what an unified group can make. people add you, and give you emails, and trust you.

It could be a voting, or by amount of friends, or branches. But, again, there are people who will fake any of these systems and votes. I, sadly, would force people to write captchas and to write some thoughts that I will analyze. I could force them to provide a phone number, an email, or a scan or copy of their identification number. I could even set up a webcam meeting with them to check their validity.

Do you find all of this as madness? (300 anyone?) Then read some Albert Einstein quotes:
  • "The secret to creativity is knowing how to hide your sources."
  • "I want to know God's thoughts...the rest are details."
  • "There are only two ways to live your life. One is as though nothing is a miracle. The other is as though everything is a miracle.
Every idea is a miracle, and you should annotate all of them; although this method of thought promotes schizophrenia. (I think Einstein would have said it like that.)

Why do I like Einstein? Because he proved the Theory of Relativity on physics. Just as we, in real life and HHRR say that "everything depends on the way you look at things"...

... and, in the end, I still have difficulties to find motivation to work on my duties. I'm almost sure it's because of my daydreaming. I don't know why, but right now I recalled a Franco De Vita song called Louis...

Sacrifice, Weapon, Recovery

Today, in The Great Pawn Hunter's web page, I was reading Decoy: Chess with Style, and then all the Knights section in the Lessons page. I re-re-leaned the forgotten sacrifice-weapon-recovery principle I learned in 2002. I was re-dazzled again about how nice and beautiful some sacrifices can become... and also, in how similar they are to some aspects of life.

You must notice that whatever you sacrifice is not in vain. A plain sacrifice, because it has meaning, it has a purpose.

In Naruto Manga, Asuma explains what is his duty in the village (a sacrificial piece) and who is the most valuable piece in his game of life. Shikamaru got it wrong until Asuma finally explained his thoughts.

These children of the atom are making great philosophical stories since Tetsuwan Atomu (Mighty Atom). Mighty Atom was renamed to Astro Boy in United States. What do you think could be the reason behind that name change?

And still those powerful robots can't imagine a world without money and wars, because they want to be heads and managers of Earth by keeping poverty... As Maquiavelli said, "It is better to be feared than loved", right? I wouldn't like to be respected by fear, or to be so powerful that I fear of being alone, without enough reliable people near me.

There's no enough imagination. We humans are so crippled that we can only imagine that this is the only one way to live our lives. Respect, tolerance, acceptance and communication.
Now, each one have needs, and exchanges or sacrifices to make.

Understanding between everybody is better than any kind of money. if I could communicate with all animals and bugs, I probably would not need to kill them. But they can't imagine a new civilization. (a song about this line?)

I know the risk of losing all good things I have achieved and kept. It's just like when I don't want to lose rating on Free Internet Chess Server (FICS), but if I don't risk, I won't improve.

I know that we need to push people to work and do things, and that is not easy to change from one way to another. But also, Creativity doesn't light up too well under anxiety or pressure. Each idea should be stored and pondered from time to time when they appear on our heads.

I think I wrote about "storing all ideas of the world, even crazy ones" some time ago, but I can't remember when It was. And I'm not talking about "Web of Ideas", but something else.

Wednesday, September 8, 2010

Happy -vs- Sad

#6: yes, randomness, e+motion, sell, task, That's our task. That's what we get paid for. We do it, change it, and tweak it as you like, and receive the blame for it if it doesn't work as expected. And still we need to be happy. But how convenient that Einstein said that "There are only two ways to live your life. One is as though nothing is a miracle. The other is as though everything is a miracle." Thank your for the miracle of working that way...

Do you think we should simply ignore that bad side? Why don't we celebrate when somebody dies? or when diseased? or crippled? Or better: don't think about it at all! Show indifference to your friends' suffering, because it's bad and we should be in good mood forever, right? No! because they will reduce their estimation towards you. Challenges, Families, Relationship, Friends, ... the silly "That's another thing" answer. I hate it. I believe in Universal Law. Law should be applied to every[thing|one|where]. Then, What would my penalty be?

If you believe in God, then you believe in supernatural powers. If not, well, Malcolm X said that "a man who believes in nothing will fall for anything."