Diagonal read the matrix array - C++

 

Introduction

After a long time, here comes a post on parsing a NxN matrix. Our main intension here is to take the sum of the diagonals and take a absolute difference between them. At first, I simply forgot the C++ way to initialize an NxN array. Whoof!!

Let’s first understand what a double pointer is. It’s just a pointer to an array of pointers!!

That is,

What we do with a integer pointer *A? . Allocate an array of integers

Then what to do when u need a list of integer pointers **A ?  Allocate an array of integer pointers

How its done?

Now below is the code to allocate the double pointer

int N=10;

int **A = new int*[N]; // get array of N integer pointers

for(int i = 0; i < N; i++)

    A[i] = new int[N]  // now allocate to each pointer an array of N

// finally A[i][j] gets you into NxN!!

Next confusion comes with reading this array diagonally. Until we understand how coordinates of an diagonal behave, it’s tough to understand that clearly.

 

 If you see the left diagram, you can guess the paper work done for it.

 

From left->right, you can notice that always you get two indices, (i == j) equal. So you got this diagonal for all NxN.

 

From right –> left, what is the pattern ? It has to be the combination of i and j. If you see closely, i increases and j decreases as we move. i always increases in our loop, we just need to take care of making j to decrease.. or equating like this as well  i+j = N+1 works!!

 

 

#include <cmath>

#include <cstdio>

#include <vector>

#include <iostream>

#include <algorithm>

using namespace std;

int main() {

    int N=1;

    cin>>N;

    int **A = new int*[N];

    for(int i = 0; i < N; ++i)

    {

        A[i] = new int[N];

        for(int j = 0; j < N; ++j)

        {

            cin>>A[i][j];

        }

    }

    int sumDiag1 = 0;

    int sumDiag2 = 0;

    for(int i = 0; i < N; ++i)

    {

        for(int j = 0; j < N; ++j)

        {

            if(i == j)

            {

               sumDiag1 += A[i][j];    

            }

            if(j + i == N-1)

            {

               sumDiag2 += A[i][j]; 

            }

        }

    }

    cout<<abs(sumDiag1 - sumDiag2);

    return 0;

}

DISCLAIMER: There are better ways to do this on internet without O(N^2) loop. You can do this in a single loop as well.

Create a binary tree using an array

 

Introduction

  Its a reiterate of the same concept of mapping an array to a binary tree. We use this helper routine for creating binary trees used in our problems. So thought about showcasing the code to do that.

Solution

if you have an array like,

arr[] = { 2,3,6,1,8,2,3}

Total: 7 elements. To form a balanced binary tree out of the above array, we have to follow the below index to node mapping for the tree!!

root = i

left = 2i+1

right = 2i+2

(Assuming starting index of array is 0)

For creating the above balanced tree, you need to do a level order traversal.

We already have some examples (See references). But lets think simple way.

Algorithm:

- queue the first node

- loop

- de-queue from the vector, create a new node + left and right with data.

- push left & right of current node into the queue

- exit when array length is exceeded!!

struct BinTree

{

    int data;

    BinTree *left;

    BinTree *right;

    BinTree(int data) {

        this->data = data;

        this->left = NULL;

        this->right = NULL;

    }

};

BinTree* createBNode(int data)

{

    return new BinTree(data);

}

BinTree* arr_to_tree(int *arr, int size)

{

    BinTree *newTree, *root;

    vector<BinTree*> node_list;

    int i=0;

    root = createBNode(arr[0]);

    node_list.push_back(root);

    while(!node_list.empty())

    {

        newTree = node_list.front();

        node_list.erase(node_list.begin());

        if(2*i + 1 >= size)

            break;

        newTree->left = createBNode(arr[2*i+1]);

        node_list.push_back(newTree->left);

        if(2*i+2 >= size)

            break;

        newTree->right = createBNode(arr[2*i+2]);

        node_list.push_back(newTree->right);

        i+=1;

    }

    return root;

}

void main()

{

    BinTree *tree;

    int arr[] = { 2,3,4,6};

    tree = arr_to_tree(arr,4);

}

 

Reference

http://analgorithmaday.blogspot.in/2011/06/level-order-insert-in-binary-tree.html

Find the maximum product in an array (in all directions)

 

Question

  Really an interesting question again on Project Euler site. Problem #11.

http://projecteuler.net/index.php?section=problems&id=11

Its a 20x20 matrix in which you need to find the maximum product of 4 numbers in all the possible directions you can traverse the array. :) But thank god, the traversal is in straight line. Not zig-zag or random.. :)

Brain storm

  I started solving the problem. Initially thought it in very complex way possible as i always do. But its really simple. It’s no optimization problem, sorting problem, anything of that sort. :)

You need to find the adjacent elements of size 4 in up, down, left, right, diagonal directions in an array which when multiplied gives you a max. Even though the question looks complex, it will look like solvable.

Just do the brute force way. You need to first check horizontal 4-by-4 elements. vertical same 4-by-4 elements and then the diagonal.

I got the horizontal and vertical somehow as we take 4 elements on hand and multiply and still move the loop from 0->20.

But for diagonal what is the pattern ?

simple.. diagonal is 2 ways

• from left top to bottom right, move a line
• from right top to bottom left, move a line

But even when you move diagonal, you need to consider 4 elements?.. How, simple..

the pattern is,

(i,j) (i+1, j+1) (i+2, j+2) (i+3,j+3)

for all i,j. Note that we end by 17 itself. :)

the above one is for right top to bottom left

for, left top to bottom right, since we need to ignore elements, we start after 3.

Code

using namespace std;

void main()

{

    char line[10];

    double arr[20][20];

    ifstream myfile ("C:\\Works\\cppassignments\\algorithms\\algorithms\\euler-input.txt");

    for(int i =0 ; i<20; i++) {

        for(int j=0; j<20; j++) {

            myfile.getline(line, 10, ' ');

            arr[i][j] = atof(line);

            cout<<arr[i][j]<<" ";

        }

        cout<<endl;

    }

    double max=1;

    double prod;

    // rows

    for(int i=0;i<20; i++) {

        for(int j=0; j<17; j++) {

            prod = arr[i][j] * arr[i][j+1] * arr[i][j+2] * arr[i][j+3];

            if(max < prod) {

                max = prod;

            }

        }

    }

    // column

    for(int j =0; j<20;j++) {

        for(int i=0;i<17; i++) {

            prod = arr[i][j] * arr[i+1][j] * arr[i+2][j] * arr[i+3][j];

            if(max < prod) {

                max = prod;

            }

        }

    }

    // diagonal right top to bottom left

    // exclude 3 from 20 as it never can make it to 4 elements

    for(int i=0; i< 17;i++) {

        for(int j=0; j<17;j++) {

            prod = arr[i][j]*arr[i+1][j+1]*arr[i+2][j+2]*arr[i+3][j+3];

            if(max < prod)

                max = prod;

        }

    }

    // diagonal left top to right bottom

    for(int i=3; i< 20;i++) {

        for(int j=0; j<17;j++) {

            prod = arr[i][j]*arr[i-1][j+1]*arr[i-2][j+2]*arr[i-3][j+3];

            if(max < prod)

                max = prod;

        }

    }

}

• You cannot end by 20. :) be careful even some runtime won’t warn about array overrun, calculation will happen with garbage, your basic type will overflow and you will wrong value. Even for horizontal & vertical we do +3, so must run loop perfectly from 0 to 16
• For math contests like this, always try to use the maximum sized type as possible. :) But do that only if memory of the program is not the winning criteria.. :P
• Thanks to http://duncan99.wordpress.com/2008/10/29/project-euler-problem-11/ for enlightening me about the diagonal flow.

Alternative partition method

 

See also

http://analgorithmaday.blogspot.com/2011/02/partitioning-algorithmin-place.html

Introduction

  Quick sort partition algorithm is sometimes taught differently. :) So, thought of covering that too. There is no difference in performance or space usage. Only advantage is, this method is little bit straight forward.

Concept

  Instead of taking the pivot and incrementing 2 counts: i and j both starting from the left, we can maintain left & right with left starting from the start and right starting from the end.

  As we know that, left needs to have lesser items and right needs to have greater items. until we have appropriate items, we can simply skip it. This is little bit clearer since the skip we do is not so clear in old partition approach.

  After we skip perfectly “ok” left and right, what we have will be swappable items. We continue this until we meet the condition left > right.

  After we do all the swaps and ready with left & right lists smaller & greater. We can simply swap the element in the location where right is.

Code

int qpartition( int *a, int low, int high )

{

    int left, right;

    int pivot_item;

    pivot_item = a[low];

    left = low;

    right = high;

    while ( left < right ) {

        /* Move left while item < pivot */

        while( a[left] <= pivot_item ) left++;

        /* Move right while item > pivot */

        while( a[right] > pivot_item ) right--;

        if ( left < right ) swap(a[left],a[right]);

    }

    /* right is final position for the pivot */

    a[low] = a[right];

    a[right] = pivot_item;

    return right;

}

void main()

{

    int A[] = {9,5,7,1,10,2,3};

    int loc = qpartition(A, 0,6);

}

• I felt this approach, little bit confusing.. :) If you are not used to lots of counters.. be with the old approach
• The above code taken from: http://www.cs.auckland.ac.nz/~jmor159/PLDS210/qsort1a.html
• Even though a[low] is the pivot, we include that as well in the comparison. This is also another difference in this algorithm.

Randomized Quick sort

“Randomized quick sort uses random partition method we discussed. We just select a random pivot in an array. The advantage we get is that we can reduce the worst case performance of quick sort!! But still, this optimization is expected!!”

Introduction

   As we have seen a lot about this already, we can directly jump into Randomized quick sort

Concept

  Just select a random pivot element in the partition algorithm.

Code

int random_partition(int* arr, int start, int end)

{

    srand(time(NULL));

    int pivotIdx = start + rand() % (end-start+1);

    int pivot = arr[pivotIdx];

    swap(arr[pivotIdx], arr[end]); // move pivot element to the end

    pivotIdx = end;

    int i = start -1;

    for(int j=start; j<=end-1; j++)

    {

        if(arr[j] <= pivot)

        {

            i = i+1;

            swap(arr[i], arr[j]);

        }

    }

    swap(arr[i+1], arr[pivotIdx]);

    return i+1;

}

void random_quick_sort(int* arr, int start, int end)

{

    if(start < end) {

        int mid = random_partition(arr, start, end);

        random_quick_sort(arr, start, mid-1);

        random_quick_sort(arr, mid+1, end);

    }

}

void main()

{

    int A[] = {2,5,7,1,10,8,9};

    random_quick_sort(A, 0,6);

}

• pivot Index must be start + rand() %(end-start+1).. We do a recursive algorithm with different start and end.. :) so be careful about the formula for pivotIndex
• We need to add start to the rand() % end because we need to get near the size of the array
• start->mid-1 and mid+1->end.. is enough for quick sort.. NOTE: we always get the pivot element in right position at every iteration
• There is an alternate way of partitioning given at many other places.. Not a CLRS way!! :) We will see that as well in the next article..!! :D