8085 Assembler program in C++

In my Compiler Design lab, there was an assignment on making a 2 pass assembler for 8085 Micro processor. This assembler takes a 8085 assembly program (in mnemonics like MOV A, B) and outputs the corresponding Machine code in hexadecimal characters.
NOTE - This is just a lab work for demonstrating how a assembler works. It is not a real assembler for producing binaries.

First Download the 8085 zip

Files present in archieve-
1. assembler.cpp
2. assembler.h
3. test_assembler.cpp
4. symbols8085.txt
5. sample.asm
6. sample2.asm
7. README

Currently there are 208 commands for 8085 which can be processed. You can modify/add commands by editing "symbols.txt".

Instructions for Linux

1. First extract the contents of archieve in some folder. Lets call this folder WORK
2. Open terminal and change directory to WORK. To do this, run "cd WORK"
3. Now compile the files using "g++ -o 8085assembler test_assembler.cpp"
4. Test the sample file (sample.asm) using "./8085assembler sample.asm". You should get a string consisting of hexadecimal characters on a single line. For output to be displayed on seperate lines (for each instruction) use "./8085assembler sample.asm -n"

You can create your own 8085 input files. Just pass them as an argument to ./8085assembler
For any query, just post a comment.

Reasons for preferring C++ over Java in Coding competitions

Some time back, a question was asked on Codechef that "Why majority of programmers use C++ and not Java for submitting solutions". I posted an answer which was well received, here is my blog version of the answer.

Lets first understand the question-

It is a known fact that C++, C and Java dominate the domain of systems programming. And they are quite close in terms of popularity, in terms of usage. But the scene on programming competition sites like TopCoder, Codechef, SPOJ etc. is rather lopsided. Majority of programmers use C or C++. In fact for a typical problem C/C++ submissions are as high as 85%. Java getting second position at some ~10%, and rest is C#, python, pascal etc. You can research on your own, by going through All Submissions of Codechef.

So here are my reasons in point form-

1. Main reason is definitely the speed of execution. C or C++ is far ahead of Java in this. I won't elaborate as to why C++ is faster here.
2. Also in C++ you can get away with procedural style of programming, but Java forces you to write OO program. Which is unnecessary burden for programming on codechef.
3. No pointers? No pass by reference? Seriously this is a put off.
4. Top programmers are wicked! And C++ allows you to do wicked things. For example macros. Can you do this in Java?
5. C++ has STL, which is awesome. So argument "Java definitely has more inbuilt functionality than c++" is invalid. Whenever I see C++ beating C, I immediately understand that it has got to do with STL.
6. Taste. Yes a language is supposed to be tasty. Java syntax is rather mundane. C++ packs a lot of spicy operators.
7. Generics are not as powerful as templates. I don't know whether people use either of them on codechef, but it is a fact. With C++ templates, you can do a lot of work at compile time.
8. Also it is possible that C++ is taught before Java (as in my case). Which I think is again for a good reason.

I have omitted many points of difference between C++ and Java, because they are not relevant in Codechef programs are quite small. But 80% of time, Java losses. Which is yet another reason for programming in C++ on Codechef.
Note 1 - I am not suggesting that Java programmers should become C++ programmer. Code in the language, you are comfortable in. And both languages are good enough for all sorts of programming. This answer is merely an answer to the question.
Note 2 - Feel free to correct me, if I said anything wrong.

In addition, there is a saying "Rich gets richer, poor gets poorer", which I think is valid in this context. The problem setters and testers most of the time, test the solutions in C or C++. So the Time Limit for slower languages like Python, or the esoteric ones like Prolog, maybe unjust (even after giving them 2x to 6x time compared to C).

This post is not supposed to bash Java language, its just my true observations regarding C++ and Java.

Greatest Common Divisor (GCD) C++ Program

One of the most useful math function is Greatest Common Divisor (GCD), also known as Highest Common Factor (HCF). It takes 2 (or more) integers (positive or negative, but not zero) and returns the largest positive integer which divides the input integers without leaving remainder.

Examples-
* GCD(2, 4) = 2 because 2 divides both 2 and 4, and there is no other integer bigger than 2 which can do this.
* GCD(16, 24) = 8
* GCD(5, 6) = 1
* GCD(-2, 6) = 2

There are several ways to compute GCD as given on Wikipedia page, but we will use Euclid's algorithm, which is well suited for programming.

Note - Take care that the arguments are positive integers only. You can call GCD(abs(a), abs(b)) to ensure the negative integers are converted to positive.
The recursive version of Euclid's GCD function in C/C++

int gcd(int a, int b)
{
    if (b == 0) {
        return a;
    }
    else {
        return gcd(b, a % b);
    }
}

The non-recursive version of Euclid's GCD function in C/C++

int gcd(int a, int b)
{
    int c;
    while (b != 0)
    {
        c = a % b;
        a = b;
        b = c;
    }
    return a;
}

Let's trace GCD(18, 88) to see how code works for recursive version-

GCD(18, 88) => GCD(88, 18) => GCD(18, 16) => GCD(16, 2) => GCD(2, 0) => 2

Project Euler problem 15 : code and explanation

The problem is simply stated as -

Starting in the top left corner in a 20 by 20 grid, how many routes are there to the bottom right corner?

Note, we can not move up, or left at any point.
For input 2, there are 6 ways, as shown-

Solution 1- There is a combinatorics solution, which reduces the problem to a simple expression, in terms of 'N', but I solved it using Dynamic Programming, which is solution 2. If you want the expression, just ask :)

Solution 2 - There is a common problem in programming, where we need to find the sum of elements in a NxN matrix, moving from top left to bottom right, in same fashion. So I just use the strategy, but instead of summing the elements, I counted the number of paths. Also for a input N, the DP solution of mine needs a matrix of size (N+1)x(N+1). Try visualizing the above image imposed on a 3x3 matrix.

Python code-

#Problem 15

import numpy

table = numpy.zeros((21, 21), dtype=numpy.int64)

def rec(r, c):
    if table[r, c] != 0:
        return table[r, c]
    if r == 0 and c == 0:
        return 1
    rsum = 0
    csum = 0
    if r != 0:
        rsum = rec(r-1, c)
    if c != 0:
        csum = rec(r, c-1)
    table[r, c] = rsum + csum
    return rsum + csum

if __name__ == "__main__":
    n = int(raw_input("Enter n : "))
    print rec(n, n)

If I remove the memoization, the input number '20' will take forever to come with solution.

Redirecting standard input and standard output

Redirecting input to stdin from a file -
./a.out < in.txt

Redirecting input from stdout to a file -
./a.out > out.txt

Combining both -
./a.out < in.txt > out.txt

Sum of digits of factorial of a number

This is another projecteuler.net problem. This is again, very simple and gives programmers a chance to practice any new language they are learning. I wrote it in Python :)

#Problem 20
#Sum of digits in factorial

def fact(n):
    m = int(n/5)
    r = n - (m*5)
    i = 1
    f = 1
    while m > 0:
        m = m - 1
        f = f * i
        i = i + 1
        f = f * i
        i = i + 1
        f = f * i
        i = i + 1
        f = f * i
        i = i + 1
        f = f * i
        i = i + 1
        f = f / 10
    while r > 0:
        r = r - 1
        f = f * i
        i = i + 1
    return f

def digsum(n):
    s = 0
    while n > 0:
        s = s + (n%10)
        n = n/10
    return s

if __name__ == "__main__":
    n = int(raw_input("Enter n : "))
    f = fact(n)
    s = digsum(f)
    print f, s

Read the code carefully, while it is not perfect (100% correct though), there are many things to learn for newbie.

Python program to find the largest prime factor of the number

Recently I started learning Python. Having programmed in C, C++ and Java up to now, I found it rather different, but easy :). Here is my small and first ("Hello World" is too boring now!) program in Python-

#Computes the largest prime factor for the number
#Solution for Problem 3 on Project Euler.net

import math

x = int(raw_input('Enter Number : '))
max_factor = 2

i = (x+1)/2

while i > 1:
    if x % i == 0:
        j = 2
        while j <= int(math.sqrt(i)):
            if i % j == 0:
                break
            j = j + 1
        else:
            max_factor = i
            break
    i = i - 1

print max_factor

To find all the prime factors just use a list instead of max_factor, and keep appending "i" to it. Also remove the 'break' statement in 'else:'.

Reverse a linked list in group of k

This is one of a candidate interview question. I don't see any practical application of this-

Given a linked list, reverse the list in groups of size k. 

I am sure it is not clear to you, so here is a example-
Input -    1=>2=>3=>4=>5=>6=>7=>8
Output -  3=>2=>1=>6=>5=>4=>8=>7

Try solving it yourself before going through the code.

#include <stdio.h>
#include <stdlib.h>

typedef struct node 
{
 int v;
 struct node *next;
} node;

node * revk(node *head, int k)
{
 int i = 1;
 node *p, *b, *s1, *s2, *t;
 p = head;
 b = NULL;
 s1 = NULL;
 s2 = head;

 while (p)
 {
  t = p;
  p = p->next;
  if (t)
   t->next = b;
  b = t;

  if (i == k)
  {
   if (s1)
    s1->next = b;
   else
    head = b;
   s1 = s2;
   s2 = p;
   i = 0;
  }
  i++;
 }
 s1->next = b;
 s2->next = NULL;
 return head;
}

void print(node *head)
{
 node *p = head;
 while (p)
 {
  printf("%d -> ", p->v);
  p = p->next;
 }
 printf("$\n");
}

void insert(node **t, int v)
{
 node *p = malloc(sizeof(node));
 p->v = v;
 p->next = NULL;
 (*t)->next = p;
 *t = p;
}

int main(int argc, char *argv[])
{
 node *head, *tail = NULL;
 head = malloc(sizeof(node));
 head->next = NULL;
 head->v = 1;
 tail = head;
 insert(&tail, 2); 
 insert(&tail, 3); 
 insert(&tail, 4); 
 insert(&tail, 5); 
 insert(&tail, 6); 
 insert(&tail, 7); 
 insert(&tail, 8);

 print(head);

 head = revk(head, 3);

 print(head);

 tail = head;

 while (tail)
 {
  head = tail;
  tail = tail->next;
  free(head);
 }

 printf("\n");
 return 0;
}

C Program : Rank of a word

Rank of a word is the position of the word when all the permutations of the letters in the word are listed in dictionary order. So for example "cat" is the word, then, various permutations in dictionary order are-

1. act
2. atc
3. cat
4. cta
5. tac
6. tca

Hence the rank of "cat" is 3.
Here is the logic in short-

Sort the word, find number of permutations that can be formed with letters which come before i^th letter in original word.

So for i = 0, i^th letter is 'c' and the sorted word is "act", so we need to find all permutations starting with 'a' and so on.

Below is the program that takes care of duplicates as well.

#include <stdio.h>
#include <string.h>

long fact(int n)
{
 long f = 1;
 while (n > 0)
 {
  f *= n;
  n--;
 }
 return f;
}

int find_rank(char s[], int len)
{
 long rank = 1;
 int i, j, k, l, fr[26], f; //fr is frequency
 char sorted[100], cur, t, pre;

 for (i = 0; i < len -1 ; ++i)
 {
  cur = s[i];
  strcpy(sorted, s + i);
  l = len - i;
  memset(fr, 0, sizeof(fr));
  fr[sorted[0] - 'a']++;
  for (j = 1; j < l; ++j)
  {
   t = sorted[j];
   fr[t-'a']++;
   for (k = j-1; k >=0 && sorted[k] > t; --k)
    sorted[k+1] = sorted[k];
   sorted[k+1] = t;
  }
  pre = 1;
  for (k = 0; sorted[k] != cur ;++k)
  {
   if (sorted[k] == pre)
    continue;
   pre = sorted[k];

   f = fact(l - 1);
   fr[pre - 'a']--;
   for (j = 0; j < 26; ++j)
    if (fr[j])
     f /= fact(fr[j]);
   rank += f;
   fr[pre - 'a']++;
  }
 }
 return rank;
}

int main()
{
 char s[100];
 
 scanf("%s", s);
 printf("%d", find_rank(s, strlen(s)));
 return 0;
}

C++ Program - Finding the kth element in a dynamic sorted list

A common programming problem goes something like -

To find the k^th minimum(/maximum) element in a dynamic list, which is kept sorted.

The catch here is that, the list is dynamic, i.e. the list is increasing in size (due to insertion of element), and at any instant, you may be asked to report the k^th minimum element.

There are in general 3 approaches (considering we have 'n' elements at any instant)-

1. To have O(1) insertion, i.e insert at the end of the list. And O(n log n) search, i.e when asked to give k^th element, sort the list and output the element at k^th offset. As is evident, if the queries are frequent this approach is not going to be efficient.
2. To have O(n) insertion, i.e insert the new element at its correct position in sorted list by shifting all elements from  k^th to  n^th offset by 1. And to have O(1) output. Again this is not very efficient as it is O(n²) overall.
3. To have O(log n) insertion and O(1) output time. Now this seems rather efficient! This is overall O(n log n). This is the method I am discussing below.

The difference in second and third approach is that we use a array in former and 2 heaps in later.

Using 2 heaps-

If we need the  k^th minimum element, we will need 2 heaps. One is a MIN heap other is a MAX heap. And at any time we need to ensure that MAX heap has exactly 'k' elements and MIN heap has the rest (N-K). Then the  k^th element is at the top of MAX heap at any time. Let me illustrate with an example, followed by a C++ program.

Consider a stream of insertion and queries (?), for k = 4 - 

9 5 4 7 ? 6 2 ? 1 ? 2 ?

Stream	MIN heap	MAX heap	Output
9		9
5		9 5
4		9 5 4
7		9 7 5 4
?		9 7 5 4	9
6	9	7 6 5 4
2	7 9	6 5 4 2
?	7 9	6 5 4 2	6
1	6 7 9	5 4 2 1
?	6 7 9	5 4 2 1	5
2	5 6 7 9	4 2 2 1
?	5 6 7 9	4 2 2 1	4

Now there are several points to be noted -

• For first k insertions, we are not able to maintain the size of MAX heap as k. But we insert all of the first k elements in MAX heap.
• After k elements are inserted, and we have new element "x", then we compare x with MAX heap's top "t". If x > t, we insert x in MIN heap, else we delete t from MAX heap, and put it in MIN heap, and then insert x in MAX heap.
• Do we really need MIN heap? This is a question that should come in your mind. Answer is No! Just throw the numbers being inserted in MIN heap. This method is so general that it can be easily adapted for problems in which k is not a number but a fraction. Like to output the 1/3th element. In that case just maintain size of MAX heap to 1/3 of total. In this you may have to transfer elements from MIN heap to MAX heap as well.
• C++ does not have Heap data structure, at least not with the name "heap". Either you can create your own, or use Priority Queue in STL. 

So here is the program-

#include <iostream>
#include <queue>

using namespace std;

class Rlong //Reverse Long
{
 long m_l;
public:
 Rlong(long l) : m_l(l)
 { }
 operator long const &() const
 { return m_l; }
 bool operator<(Rlong const &right) const
 { return m_l > right.m_l; }
};

int main()
{
 long n, k, x, y, i;

 priority_queue<Rlong> minpq;
 priority_queue<long>  maxpq;

 cin >> n >> k;

 for (i = 0; i < k; ++i)
 {
  cin >> x;
  maxpq.push(x);
 }
 for (; i < n; ++i)
 {
  cin >> x ;
  if (x != -1) // assuming -1 as '?'
  {
   if (x < maxpq.top())
   {
    y = maxpq.top();
    maxpq.pop();
    maxpq.push(x);
    minpq.push(y);
   }
   else
   {
    minpq.push(x);
   }
  }
  else
  {
   x = maxpq.top();
   cout << x;
  }
 }
 return 0;
}

Eliminate duplicates and sort the list

Recently I received a List of zipcodes from a carrier. The zipcodes were duplicated and were not sorted. So I just wrote a small C++ code to sort and eliminate the duplicates from the list of zipcodes.

The program simply uses the set container in C++ STL, for the task. The set has the property that, it doesn't store duplicates. So, all we need to do is, insert all the elements (from the input file), into the set. And since set is also ordered in nature (implemented as a Red Black Tree), we can iterate over it to yield a sorted list. Below is the code-

#include <fstream>
#include <sstream>
#include <string>
#include <set>

using namespace std;

inline int convert(string &s)
{
 int out;
 istringstream ss(s);
 ss >> out;
 return out;
}

int main()
{
 ifstream infile("input.txt");
 ofstream outfile("output.txt");

 string line;
 int zipcode;  //zipcode is just a integer

 set<int> zipcodes;

 while (getline(infile, line))
 {
  zipcode = convert(line);
  zipcodes.insert(zipcode);
 }

 for (auto i = zipcodes.begin(); i != zipcodes.end(); i++)
  outfile << *i << '\n';

 infile.close();
 outfile.close();

 return 0;
}

To some, one keyword might have confused, that is "auto", in the for loop as -

auto i = zipcodes.begin() ;

Well, it was introduced in C++11 standard, to let the programmer omit typing the type of variable. The compiler well deduce the type by looking at the type of RHS. And I believe it is rather nice introduction, seeing how it can save you from rather ugly expressions. If you are using gcc with version prior to 4.7, you need to add a flag -std=c++0x while compiling in terminal or enable this flag in your IDE (if it is not already).

The stack that could give minimum in O(1)

This is one of my favorite interview question-

You have to create a stack which gives the smallest element in constant (or O(1)) time. 

You can be asked for the largest element instead of smallest also.

Take some time to think. Or read the grayed hint below, followed by the solution and explanation-

You can use linear amount of (extra) memory.

Ok now the solution. You take a separate stack, call it min-stack. The other stack is the main-stack. 

When you push a element in main-stack, compare the new element with top (using peek, not pop) of min-stack. Following cases are possible-

1. The min-stack is empty => simply push the new element in min-stack as well.
2. The min-stack top is smaller => do nothing.
3. The min-stack top is larger => push the new element in min-stack as well.
4. The min-stack top is equal => push the new element in min-stack as well. 

When you pop the element from the main-stack, again compare the popped element with the min-stack top. There are only 2 cases now-

1. The min-stack top is equal => pop from min-stack as well.
2. The min-stack top is not equal => do nothing

When the time comes for get minimum, just return the top of min-stack (taking care of underflow).

For completeness, here is the C++ code

void stack::push(int a)
{ 
    main_stack.push(a);   

    if (min_stack.is_empty())
        min_stack.push(a); 
    else if (a <= min_stack.top()) 
        min_stack.push(a);
}

int stack::pop()
{
    //take care of underflow here

    int e = main_stack.top();     
    if (min_stack.top() == e)
        min_stack.pop();

    return e;
}

int stack::minimum()
{
    //take care of underflow here

    return min_stack.top();
} 

C++ - Convert list of numbers to list of ranges

I recently needed to convert a list of zip codes to a list of ranges of zip codes. Example below (the numbers are only for illustration, real zip-code are 6 or 7 digit)-
Input: {1, 2, 3, 4, 6, 8, 9}

Output: {(1,4), (6,6), (8, 9)}

What is the use?
I needed to enter it in a database table like:
+----+-------+-----+
| id | start | end |
+----+-------+-----+
|  1 |     1 |   4 |
|  2 |     6 |   6 |
|  3 |     8 |   9 |
+----+-------+-----+
for looking up if a input zip-code falls in any range (zip code where our carrier accepts shipments).

This is my small program in C++ to do this (Download)-

#include <iostream>
#include <fstream>
#include <sstream>
#include <string>

using namespace std;

template <typename T>
inline T convert(string &s)
{
 T out;
 istringstream ss(s);
 ss >> out;
 return out;
}

int main()
{
 ifstream infile("input.txt");
 ofstream outfile("output.txt");

 string cur_line, last_line;
 int cur, last;

 if (infile.good()) {
  getline(infile, cur_line);
  cur = convert<int>(cur_line);
  outfile << cur_line << ',';
  last = cur;
 }

 while(getline(infile, cur_line))
 {
  cur = convert<int>(cur_line);
  
  if (cur != last + 1) {
   outfile << last_line << '\n';
   outfile << cur_line << ',';
  }
  
  last = cur;
  last_line = cur_line;
 }

 outfile << last_line;

 infile.close();
 outfile.close();

 return 0;
}

I hope you find good use for this program.