Bits of Learning

Learning sometimes happens in big jumps, but mostly in little tiny steps. I share my baby steps of learning here, mostly on topics around programming, programming languages, software engineering, and computing in general. But occasionally, even on other disciplines of engineering or even science. I mostly learn through examples and doing. And this place is a logbook of my experiences in learning something. You may find several things interesting here: little cute snippets of (hopefully useful) code, a bit of backing theory, and a lot of gyan on how learning can be so much fun.

Wednesday, September 24, 2008

Alien Number System

Here's something about the C++ program I wrote for implementing the alien number system which has an arbitrary set of characters as its digits. Seems to work for all test cases I tried. See Google Codejam sample problems for details:

A number system is represented by a sequence of characters which represent its digits. For example, the decimal number system (also called the base-10 number system) has the characters '0', '1', '2', '3', '4', '5', '6', '7', '8' and '9' as its digits. Representing the number system in this sequence also means the following:

  • The first digit (for decimal system, it's '0') is the additive idempotent number. In other words, the effect of adding it to any other number is the same number. In more worldly language, it represents the smallest natural number, or simply, the zero.
  • The first number is the multiplicative idempotent number. Which means that by multiplying it to any number, you get back the same number. Also, the difference between any two successive numbers in this number system is this number. In simplest possible terms, its value is one.
  • Definition of one gives the definition of the successor function. succ(x) = x + one.
  • Addition is repetitive application of the succ function. For instance, in decimal system:
add(3, 4) = succ (succ (succ (succ (3)))) = succ(succ(succ(4))) = succ(succ(5)) = succ(6) = 7.
  • Multiplication is a repetitive application of addition function between the number and itself.
multiply(3, 4) = add(3, add(3, add(3, 3))) = add(3, add(6))) = add(3, 9) = 12.

The above phenomena underlie the design of a basic number system. And that's what is done in the code below. Apart from the above, we use some optimisation by implementing the add and multiply functions to simulate the algorithms generally used in manual calculations.

Interface:


#ifndef NUMBERSYSTEM_H

#define NUMBERSYSTEM_H



#include <vector>

#include <map>

#include <string>



using namespace std;





class NumberSystem

{

private:

string m_Digits;

map< pair <char, char>, string> m_AddMap;

map< pair <char, char>, string> m_MultiplyMap;

public:

NumberSystem (string);

string add (string, string);

string add (char, char);

string add (string, char);

string multiply (char, char);

string multiply (string, string);



string succ (string);

string prev (string);



string getDigits ();

string getZero ();

char operator[] (unsigned int);

unsigned int size ();

};



string reverse (string);



#endif

Implementation

#include "NumberSystem.h"



NumberSystem::NumberSystem (string aDigits)

: m_Digits (aDigits)

{

// set up a lookup table to to speeden up the addition of two

// single digit numbers. Currently not used anywhere.

for (unsigned int i = 0; i < m_Digits.size (); i++)

{

for (unsigned int j = 0; j < m_Digits.size (); j++)

{

char a = m_Digits[i];

char b = m_Digits[j];



string sum = add (a, b);

pair <char, char> p = pair <char, char>(a, b);

m_AddMap[p] = sum;

}

}

// set up a lookup table to to speeden up the multiplication of two

// single digit numbers. Currently not used anywhere.

for (unsigned int i = 0; i < m_Digits.size (); i++)

{

for (unsigned int j = 0; j < m_Digits.size (); j++)

{

char a = m_Digits[i];

char b = m_Digits[j];



string product = multiply (a, b);

pair <char, char> p = pair <char, char>(a, b);

m_MultiplyMap[p] = product;

}

}

}





// Adds two single digit numbers.

string

NumberSystem::add (char a, char b)

{

string sum(" ");

sum[0] = a;

sum[1] = m_Digits[0];



int j = m_Digits.find (b);

for (unsigned int k = 1; k <= j; k++)

{

sum = succ (sum);

}

return sum;

}



// adds two numbers, one single digit, and another non-single digit.

string

NumberSystem::add (string a, char b)

{

string sum = a;



unsigned int j = m_Digits.find (b);

for (unsigned int k = 1; k <= j; k++)

{

sum = succ (sum);

}

return sum;

}



// adds two non-single digit numbers.

string

NumberSystem::add (string n1, string n2)

{



string a;

string b;

if (n1.size () >= n2.size ())

{

a = n1;

b = n2;

}

else

{

a = n2;

b = n1;

}



string sum;

char carry = m_Digits[0];

for (unsigned int i = 0; i < b.size (); i++)

{

string digitSum = add (a[i], b[i]);

digitSum = add (digitSum, carry);

sum = sum + digitSum[0];

if (digitSum.size () == 2)

{

carry = digitSum[1];

}

else

{

carry = m_Digits[0];

}

}

for (unsigned int i = b.size (); i < a.size (); i++)

{

string digitSum = add (add (a[i], m_Digits[0]), carry);

sum = sum + digitSum[0];

if (digitSum.size () == 2)

{

carry = digitSum[1];

}

else

{

carry = m_Digits[0];

}

}

if (carry != m_Digits[0])

{

sum = sum + carry;

}

return sum;

}



// given any number, it returns the successor of it.

string

NumberSystem::succ (string aNum)

{

if (aNum[0] == m_Digits[m_Digits.size () - 1])

{

aNum[0] = m_Digits[0];

}

else

{

aNum[0] = m_Digits[m_Digits.find (aNum[0]) + 1];

return aNum;

}

for (unsigned int i = 1; i < aNum.size (); i++)

{

if (aNum[i - 1] == m_Digits[0])

{

if (aNum[i] == m_Digits[m_Digits.size () - 1])

{

aNum[i] = m_Digits[0];

}

else

{

aNum[i] = m_Digits[m_Digits.find (aNum[i]) + 1];

return aNum;

}

}

}

if (aNum[aNum.size () - 1] == m_Digits[0])

{

aNum = aNum + m_Digits[1];

}

return aNum;

}



// given any number, this function returns a previous number. Not implemented

// as yet.

string

NumberSystem::prev (string aNum)

{

return aNum;

}



// multiplies two single-digit numbers.

string

NumberSystem::multiply (char aa, char bb)

{

string product (1, m_Digits[0]);

for (string counter (1, m_Digits[0]); counter != string (1, aa); counter = succ (counter))

{

product = add (product, bb);

}

return product;

}



//multiplies two non-single digit numbers.

string

NumberSystem::multiply (string a, string b)

{

vector <string> Products;

for (unsigned int i = 0; i < a.size (); i++)

{

char carry = m_Digits[0];

string product1;

for (unsigned int j = 0; j < i; j++)

{

product1 = product1 + (m_Digits[0]);

}

for (unsigned int j = 0; j < b.size (); j++)

{

string digitProduct = multiply (a[i], b[j]);

digitProduct = add (digitProduct, carry);

product1 = product1 + digitProduct[0];

if (digitProduct.size () == 2)

{

carry = digitProduct[1];

}

else if (digitProduct.size () == 1)

{

carry = m_Digits[0];

}

else

{

exit (1);

}

}

if (carry != m_Digits[0])

{

product1 = product1 + carry;

}

Products.push_back (product1);

}

string product (1, m_Digits[0]);

for (unsigned int i = 0; i < Products.size (); i++)

{

product = add (product, Products[i]);

}

return product;

}



// returns the digits of the number system.

string

NumberSystem::getDigits ()

{

return m_Digits;

}



// returns the zero value of the number system.

string

NumberSystem::getZero ()

{

return string (1, m_Digits[0]);

}



// returns the apos-th digit of the number system

char

NumberSystem::operator [] (unsigned int apos)

{

return m_Digits[apos];

}



// returns the number of digits in the number system.

unsigned int

NumberSystem::size ()

{

return m_Digits.size ();

}



// reverses a string. Used for user-interface purposes.

string reverse (const string s)

{

string o;

if (s.size ())

{

for (unsigned int i = 0; i < s.size (); i++)

{

o = o + s[s.size () - i - 1];

}

}

return o;

}



That's it!

Tuesday, September 23, 2008

Alien Number System

Here's the C++ program I wrote for implementing the alien number system which has an arbitrary set of characters as its digits. Seems to work for all test cases I tried. See Google Codejam sample problems for details:

#include
#include
#include

#include
#include <map>

using namespace std;

string reverse (string);

class NumberSystem
{
private:
string m_Digits;
map char, char, string> m_AddMap;
map char, char>, string> m_MultiplyMap;

public:
NumberSystem (string);
string add (string, string);
string add (
char, char);
string add (string,
char);
string multiply (
char, char);
string multiply (string, string);
string multiply1 (string, string);

string succ (string);
string prev (string);

string getDigits ();
string getZero ();
char operator[] (unsigned int);
unsigned int size ();
};

NumberSystem::NumberSystem (string aDigits)
: m_Digits (aDigits)
{
for (
unsigned int i = 0; i < m_Digits.size (); i++)
{
for (
unsigned int j = 0; j < m_Digits.size (); j++)
{
char a = m_Digits[i];
char b = m_Digits[j];

string sum = add (a, b);
pair
char, char> p = pair <char, char>(a, b);
m_AddMap[p] = sum;
}
}
for (
unsigned int i = 0; i < m_Digits.size (); i++)
{
for (
unsigned int j = 0; j < m_Digits.size (); j++)
{
char a = m_Digits[i];
char b = m_Digits[j];

string product = multiply (a, b);
pair <
char, char> p = pair <char, char>(a, b);
m_MultiplyMap[p] = product;
}
}
}

string
NumberSystem::add (
char a, char b)
{
string sum(
" ");
sum[
0] = a;
sum[
1] = m_Digits[0];

int j = m_Digits.find (b);
for (
unsigned int k = 1; k <= j; k++)
{
sum = succ (sum);
}
return sum;
}

string
NumberSystem::add (string a,
char b)
{
string sum = a;

unsigned int j = m_Digits.find (b);
for (
unsigned int k = 1; k <= j; k++)
{
sum = succ (sum);
}
return sum;
}

string
NumberSystem::add (string n1, string n2)
{

string a;
string b;
if (n1.size () >= n2.size ())
{
a = n1;
b = n2;
}
else

{
a = n2;
b = n1;
}

string sum;
char carry = m_Digits[0];
for (
unsigned int i = 0; i < b.size (); i++)
{
string digitSum = add (a[i], b[i]);
digitSum = add (digitSum, carry);
sum = sum + digitSum[
0];
if (digitSum.size () ==
2)
{
carry = digitSum[
1];
}
else

{
carry = m_Digits[
0];
}
}
for (
unsigned int i = b.size (); i < a.size (); i++)
{
string digitSum = add (add (a[i], m_Digits[
0]), carry);
sum = sum + digitSum[
0];
if (digitSum.size () ==
2)
{
carry = digitSum[
1];
}
else

{
carry = m_Digits[
0];
}
}
if (carry != m_Digits[
0])
{
sum = sum + carry;
}
return sum;
}

string
NumberSystem::succ (string aNum)
{
if (aNum[
0] == m_Digits[m_Digits.size () - 1])
{
aNum[
0] = m_Digits[0];
}
else

{
aNum[
0] = m_Digits[m_Digits.find (aNum[0]) + 1];
return aNum;
}
for (
unsigned int i = 1; i < aNum.size (); i++)
{
if (aNum[i -
1] == m_Digits[0])
{
if (aNum[i] == m_Digits[m_Digits.size () -
1])
{
aNum[i] = m_Digits[
0];
}
else

{
aNum[i] = m_Digits[m_Digits.find (aNum[i]) +
1];
return aNum;
}
}
}
if (aNum[aNum.size () -
1] == m_Digits[0])
{
aNum = aNum + m_Digits[
1];
}
return aNum;
}

string
NumberSystem::prev (string aNum)
{
return aNum;
}

string
NumberSystem::multiply (string a, string b)
{
string counter (
1, m_Digits[0]);
string product (
1, m_Digits[0]);

for (; counter != b; counter = succ (counter))
{
product = add (product, a);
}
return product;
}

string
NumberSystem::multiply (
char aa, char bb)
{
string product (
1, m_Digits[0]);
for (string counter (
1, m_Digits[0]); counter != string (1, aa); counter = succ (counter))
{
product = add (product, bb);
}
return product;
}

string
NumberSystem::multiply1 (string a, string b)
{
vector Products;
for (
unsigned int i = 0; i < a.size (); i++)
{
char carry = m_Digits[0];
string product1;
for (
unsigned int j = 0; j < i; j++)
{
product1 = product1 + (m_Digits[
0]);
}
for (
unsigned int j = 0; j < b.size (); j++)
{
string digitProduct = multiply (a[i], b[j]);
digitProduct = add (digitProduct, carry);
product1 = product1 + digitProduct[
0];
if (digitProduct.size () ==
2)
{
carry = digitProduct[
1];
}
else if (digitProduct.size () ==
1)
{
carry = m_Digits[
0];
}
else

{
exit (
1);
}
}
if (carry != m_Digits[
0])
{
product1 = product1 + carry;
}
Products.push_back (product1);
}
string product (
1, m_Digits[0]);
for (
unsigned int i = 0; i < Products.size (); i++)
{
product = add (product, Products[i]);
}
return product;
}

string
NumberSystem::getDigits ()
{
return m_Digits;
}

string
NumberSystem::getZero ()
{
return string (
1, m_Digits[0]);
}


char
NumberSystem::operator [] (unsigned int apos)
{
return m_Digits[apos];
}

unsigned int
NumberSystem::size ()
{
return m_Digits.size ();
}

string reverse (string s)
{
string o;
if (s.size ())
{
for (
unsigned int i = 0; i < s.size (); i++)
{
o = o + s[s.size () - i -
1];
}
}
return o;
}


class Converter
{
private:
string m_Input;
NumberSystem m_Source;
NumberSystem m_Target;
string m_Output;

map string, string> m_Map;
public:
Converter (string, NumberSystem, NumberSystem);
string getOutput ();
string convert ();
void makeMap ();
};

Converter::Converter (string aN, NumberSystem aS, NumberSystem aT)
: m_Input (aN)
, m_Source (aS)
, m_Target (aT)
{
makeMap ();
}

void
Converter::makeMap ()
{
if (m_Source.size () >= m_Target.size ())
{
string cOut = m_Target.getZero ();
for (
unsigned int i = 0; i < m_Source.size (); i++)
{
char c[2];
c[
0] = m_Source[i];
c[
1] = '\0';
m_Map[c] = cOut;
cOut = m_Target.succ (cOut);
}
}
else

{
string cIn = m_Source.getZero ();
for (
unsigned int i = 0; i < m_Target.size (); i++)
{
char c[2];
c[
0] = m_Target[i];
c[
1] = '\0';
m_Map[cIn] = c;
cIn = m_Source.succ (cIn);
}
}

// cout << "*******************************" << endl;
// for (map::iterator I = m_Map.begin (); I != m_Map.end (); I++)
// {
// cout << "Map[" << reverse ((*I).first) << "] = " << reverse ((*I).second) << endl;
// }
// cout << "*******************************" << endl;

}

string
Converter::getOutput ()
{
return m_Output;
}

string
Converter::convert ()
{
string output = m_Target.getZero ();
string nine (
1, m_Source[m_Source.size () - 1]);
string ten = m_Target.succ (m_Map[nine]);

for (
unsigned int i = 0; i < m_Input.size (); i++)
{
string product = m_Map[string (
1, m_Input[i])];
for (
unsigned int j = 0; j < i; j++)
{
product = m_Target.multiply (product, ten);
}
output = m_Target.add (output, product);
}
return output;
}

vector ;

getInput (istream & fin)
{
unsigned int n;
vector v;
fin >> n;
for (
unsigned int i = 0; i < n; i++)
{
string num;
string s;
string t;
fin >> num;
fin >> s;
fin >> t;

Converter c (reverse (num), s, t);
v.push_back (c);
}
return v;
}


int main (int argc, char ** argv)
{
/*
vector v;
if (argc < 2)
{
cout << "argc = " << argc << endl;
cout << "argv[0] = " << argv[0] << endl;
getInput (cin);

}
else
{
ifstream fin (argv[1]);
v = getInput (fin);
fin.close ();
}

for (unsigned int i = 0; i < v.size (); i++)
{
cout << "output = " << reverse (v[i].convert ()) << endl;
}
*/

/*
Counter c ("01");
for (unsigned int i = 0; i < 100; i++)
{
++c;
cout << reverse (c.getCurrentCount ()) << endl;
}
NumberSystem ns1 ("0123456789");
cout << "45 + 50 = " << reverse (ns1.add (reverse ("45"), reverse ("50"))) << endl;
cout << "4512222 * 50345 = " << reverse (ns1.multiply (reverse ("4512222"), reverse ("50345"))) << endl;
NumberSystem ns2 ("01");
*/

NumberSystem ns1 ("0123456789");
cout <<
"45113435 * 503112 = " <<>"45113435"), reverse ("503112"))) << endl;
getchar ();
cout <<
"45113435 * 503112 = " <<>"45113435"), reverse ("503112"))) << endl;

return
0;
}