Simple Program to Calculate Distance in 3 Dimensional Plane

In 2-space if two points are p1(x1, y1) and p2(x2, y2) then the distance between them is,

d = \sqrt[]{(x_2 - x_1)^2 + (y_2 - y_1)^2}

Similarly in 3-space distance between two points p1(x1, y1, z1) and p2(x2, y2, z2) is,

d = \sqrt[]{(x_2 - x_1)^2 + (y_2 - y_1)^2 + (z_2 - z_1)^2}

 

Example:

Distance between point (1, 1, 2) and point (3, -2, 4) is,

d = \sqrt[]{(x_2 - x_1)^2 + (y_2 - y_1)^2 + (z_2 - z_1)^2}
d = \sqrt[]{(3 - 1)^2 + (-2 - 1)^2 + (4 - 2)^2}
d = \sqrt[]{4 + 9 + 4}
d = 4.12


Code:

/**
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 */

#include<cstdio>
#include<cmath>
#include<algorithm>

struct point{
    float x, y, z;
};

// descending comparison x
bool point_sorter_x_desc(point const &p0, point const &p1){
    return p0.x > p1.x;
}

// ascending comparison x
bool point_sorter_x_asc(point const &p0, point const &p1){
    return p0.x < p1.x;
}

// descending comparison y
bool point_sorter_y(point const &p0, point const &p1){
    return p0.y > p1.y;
}

// descending comparison y
bool point_sorter_z(point const &p0, point const &p1){
    return p0.z > p1.z;
}

// descending comparison priority x then y then z
bool point_sorter_greatest(point const &p0, point const &p1){
    if(p0.x > p1.x)
        return p0.x > p1.x;
    if(p0.y > p1.y)
        return p0.y > p1.y;
    return p0.z > p1.z;
}

int main(){

    int N;
    printf("Enter number of points:\n");
    scanf("%d", &N);

    /*
     * Comment this section to hard code points
     * Uncomment to take user input
     */

    //struct point *p = new point[N];

    //for(int i = 0; i < N; ++i)
      //  scanf("%f %f %f", &p[i].x, &p[i].y, &p[i].z);

    /*
     * Comment this section to input points
     * Uncomment the struct memory allocation and scan above
     */
    struct point p[6] = {
        {1,1,2},
        {3,-2,4},
        {10,10,12},
        {6,2,7},
        {5,6,9},
        {8,1,1}
    };

    // Sort based on the point in x axis
    std::sort(p, p + N, &point_sorter_x_asc);

    // show the sorted points
    printf("\nSorted Points:\n\n");
    for(int i = 0; i < N; ++i)
        printf("P%d: (%.2f , %.2f, %.2f)\n", i, p[i].x, p[i].y, p[i].z);
    printf("\n\n");

    // Finding distance in 3-Dimensional Plane
    float total_distance = 0;
    for(int i = 1; i < N; ++i){
        float distance = sqrt( pow( p[i].x - p[i - 1].x, 2 ) + pow( p[i].y - p[i - 1].y, 2 ) + pow( p[i].z - p[i - 1].z, 2 ) );
        printf("\nDistance between points (%.2f,%.2f,%.2f) and (%.2f,%.2f,%.2f) is: %.2f\n", p[i - 1].x, p[i - 1].y, p[i - 1].z, p[i].x, p[i].y, p[i].z, distance);
        total_distance += distance;
    }

    printf("\n\n");
    printf("Total Distance: %.2f\n", total_distance);

	return 0;
}

Bits of Java Part 1

Introduction:

IDE(Integrated Development Environments):

For beginners there are many IDE’s but I’d recommend dr. java IDE. It is very light weight and easier to learn.
For advanced users there are IDE’s such as Eclipse, NetBeans, Android Studio, Intellijidea.

Installation:

Before installing the IDE make sure you have the latest JDK and JRE installed on your system. In windows system set path if it is not set automatically. JDK 7, 8, JRE 7, 8 can have co-existing installation without causing errors.


Java Bits:

Layout:

- Package Declaration
- Import Statements
- Class Declaration

Comments:

- Line Comments. 
  Ex: //

- Block Comments.
  Ex: /*
        Block Comment
       */

- Documentation Comment:
  Ex: /**
       * Documentation
       */

Class Members:

- Attributes / Instance Variables / Properties
- Methods / Functions

Package:

- A way of grouping or arranging files in folders.

Initializer Block:

- Executed before constructor
- When multiple constructors need to initialize the same instructions

Variable Declaration:

- Declare a data type

Variable Initialization:

- Assign values to variable

this Keyword:

- Access current class instance members

Access members of an object:

- objectname.attribute
- objectname.method()

Constructor Overloading:

- Constructors with same name but different types  parameter or different amount of parameters

Access Modifiers:

- Public: Can access from everywhere
- Private: Access only from same class
- Protected: Access from same class, sub / derived /child class, same package
- Default: Access from same class, same package

Primitive Wrapper Class:

- A class based on primitive data types

Inheritance:

- Inherit state, behavior from parent class

Encapsulation:

- A way of hiding, restricting access to class components

Polymorphism:

- Ability of object to take many forms
- Pass is-a test

Java Primitive Type Conversion Errors

Java Primitive Type Conversion Errors:

/*
 * This code won't compile
 */

public class TempError {
	public static void main(String[] args) {

		// can not implicitly cast double to integer
		int a = 3.4;

		// can not  implicitly cast integer to String
		string s = 3;

		// can not  implicitly cast integer to String
		string s1 = 4 + 5;

		// can not explicitly cast double to String
		string s2 = (String) 4.5;

		// can not explicitly cast integer to String
		string s3 = (String) 4;
	}
}

Java Primitive Type Conversions

Introduction:

These are few of the way to convert int, double, string to each other.

In Eclipse create a new project then create a class called temp in src directory. In case if you use another folder just include that package name.

For Dr. java users just paste code and save the file. In both case make sure class name matches the file name otherwise it will not compile.

The process should be same for other IDE’s.


Double to String Conversion:

public class Temp {
	public static void main(String[] args) {

		/*
		 * Double to String
		 */

		// Technique 1:
		double d0 = 4.0;
		String s0 = d0 + "";
		System.out.println(s0);

		// Technique 2:
		double d1 = 4.1;
		String s1 = String.valueOf(d1);
		System.out.println(s1);

		// Technique 3:
		double d2 = 4.2;
		String s2 = Double.toString(d2);
		System.out.println(s2);

		// Technique 4:
		double d3 = 4.3;
		StringBuilder s3 = new StringBuilder();
		s3.append(d3);
		System.out.println(s3);

		// Technique 5:
		double d4 = 4.4;
		StringBuffer s4 = new StringBuffer();
		s4.append(d4);
		System.out.println(s4);
	}
}

 

Integer to String:

public class Temp {
	public static void main(String[] args) {

		/*
		 * Integer to String
		 */

		// Technique 1:
		int i0 = 0;
		String m0 = Integer.toString(i0);
		System.out.println(m0); 

		// Technique 2:
		int i1 = 1;
		String m1 = "" + i1;
		System.out.println(m1); 

		// Technique 3:
		int i2 = 2;
		String m2 = String.valueOf(i2);
		System.out.println(m2); 

		// Technique 4:
		int i3 = 3;
		StringBuilder m3 = new StringBuilder();
		m3.append(i3);
		System.out.println(m3);

		// Technique 5:
		int i4 = 4;
		StringBuffer m4 = new StringBuffer();
		m4.append(i4);
		System.out.println(m4);
	}
}

 

String to Double:

public class Temp {
	public static void main(String[] args) {

		/*
		 * String to Double
		 */

		// Technique 1:
		String k0 = "20.22";
		double n0 = Double.parseDouble(k0);
		System.out.println(n0);

		// Technique 2:
		String k1 = "20.53";
		Double n1 = Double.valueOf(k1);
		System.out.println(n1);
	}
}

 

String to Integer:

public class Temp {
	public static void main(String[] args) {

		/*
		 * String to Integer
		 */

		// Technique 1:
		String p0 = "20";
		int u0 = Integer.parseInt(p0);
		System.out.println(u0);

		// Technique 2:
		String p1 = "203";
		Integer u1 = Integer.valueOf(p1);
		System.out.println(u1);
	}
}

UVA Problem 10696 – f91 Solution

UVA Problem 10696 – f91 Solution:


Click here to go to this problem in uva Online Judge.

Solving Technique:

This is a simple DP problem (OR, so it looks but there’s a better way). It can be solved both iteratively and recursively with or without memoization. Still it will get accepted. But still the runtime is slow due huge input. So using a faster io may help it get accepted with a better rank.

For the matter of practice i will show all four methods i know of to solve this problem. Codes are given in this order,

  1. dynamic programming solution.
  2. Recursive solution without Memoization.
  3. Recursive solution with Memoization.
  4. Shortcut Trickery.
  5. Maybe extend the shortcut Trickery with memoization or other technique by yourself ? try it !!
Before starting to look below take look at this codes ( Fibonacci DP, Memoization ) with explanation.

Solution explanation:

Here the formula is given, we just need rearrange it and get the recurrence relation,

If N ≤ 100, then f91(N) = f91(f91(N+11));
If N ≥ 101, then f91(N) = N-10.

So from the given statement generating recurrence relation will be,

f(n) = { f(f(n+11)), if n <= 100
       { n - 10,     if n >= 101

Here base case is for any n greater than or equal to 101 is return n – 10. No more recursive call on that.
This can be simplified but i won’t go into that. The codes below will give a better idea.

Now, just create a function named f and use if else or ternary to implement the given relation and it’ll work.

Memoization:

Since we’ve found out the recurrence relation it won’t be hard to memoize the code. We can use a memo array to store the already calculated results. We need not change much from the previous recursive solution to memoize it.

Add an if condition in the beginning if the value is already calculated and stored in memo array just return. Other wise when returning just store the return values in memo.

That’s it.

Dynamic Programming ( bottom up method ):

Our recurrence relation will never change. Since there is no other function needed we just calculate and store values in memo array. I started from 1,000,000 because the problem statement said an integer may be at most 1,000,000. Just loop through that many times and store results in memo array.

Last Solution Trick:

It come to me when i was testing my own inputs. Anything less or equal 100 result in 91. Any greater value results in that value minus 10. Take a look at the code below to get the idea.

Important:  Be sure to add or print a new line after each output unless otherwise specified. The outputs should match exactly because sometimes even a space character causes the answer to be marked as wrong answer. Please compile with c++ compiler as some of my codes are in c and some in c++.


Input:

500
91
1
5
190
100
101
0

 


Output:

490
91
91
91
180
91
91

Code Bottom Up (Iterative) Dynamic Programming:

/**
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 * Problem: UVA 10696 - f91
 * Type:    Bottom Up (Iterative) Dynamic Programming
 */

#include<cstdio>
#include<sstream>

using namespace std;

#define N 1000000

static int F[N];

int main(){
    int n, i;

    for(i = N; i >= 0; --i){
        if(i >= 101)
            F[i] = i - 10;
        else
            F[i] = F[F[i + 11]];
    }

    while(scanf("%d", &n) && n)
        printf("f91(%d) = %d\n", n, F[n]);

    return 0;
}

Code Top Down (Recursive) Without Memoization:

/**
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 * Problem: UVA 10696 - f91
 * Type:    Top Down (Recursive) without Memoization
 */

#include<stdio.h>

int f(int n){
    return (n >= 101) ? n - 10 : f(f(n + 11));
}

int main(){
    int n;

    while(scanf("%d",&n) && n)
        printf("f91(%d) = %d\n", n, f(n));

    return 0;
}

Code Top Down (Recursive) with Memoization:

/**
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 * Problem: UVA 10696 - f91
 * Type:    Top Down (Recursive) with Memoization
 */

#include<stdio.h>

static unsigned F[1000000];

unsigned f(unsigned n){
    if(F[n])
        return F[n];

    if(n >= 101)
        return F[n] = n - 10;
    else
        return F[n] = f(f(n+11));
}

int main(){
    unsigned n;

    while(scanf("%u",&n) && n)
        printf("f91(%u) = %u\n", n, f(n));

    return 0;
}

Shortcut Technique:

/**
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 * Problem: UVA 10696 - f91
 * Type:    shortcut technique
 */

#include<stdio.h>

int main(){
    unsigned n;

    while(scanf("%u", &n) && n){
        if(n <= 100)
            printf("f91(%d) = 91\n", n);
        else
            printf("f91(%d) = %d\n", n, n - 10);
    }

    return 0;
}

Ternary Heap Sort Code in C++ using Heap Data structure

Introduction:

This code is implementation of ternary heap sort. The code requires no input. Data inputs (integers) are generated randomly then sorted using heap sort.

Only change the define SIZE value to for sorting large or small amount of numbers.

Code for Binary Heap Sort here.

Ternary Heap Sort Code Cpp:

/**
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 * Problem: Ternary Heap Sort
 */

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<ctime>

#define SIZE 10
int A[SIZE], heapsize = SIZE;

void maxHeapify(int i){
    int largest;

    /**
     * Find right child index
     */
    int l = 3 * i + 1;

    /**
     * Compare left child against the current node
     */
    if(l < heapsize && A[l] > A[i])
        largest = l;
    else
        largest = i;

    /**
     * find mid child index
     */
    int m = 3 * i + 2;

    /**
     * Compare mid child against the calculated largest value node
     */
    if(m < heapsize && A[m] > A[largest])
        largest = m;

    /**
     * Find right child index
     */
    int r = 3 * i + 3;

    /**
     * Compare right child against the calculated largest value node
     */
    if(r < heapsize && A[r] > A[largest])
        largest = r;

    /*
     * If child nodes have larger value then current node
     */
    if(largest != i){
        /**
         * Swap the two values
         */
        std::swap(A[i], A[largest]);

        /**
         * Max heapify again rest of the heap
         */
        maxHeapify(largest);
    }
}

void buildMaxHeap(){
    int j;
    /**
     * operate on third of array
     */
    for(j = heapsize / 3 - 1; j >= 0; --j)
        maxHeapify(j);
}

void heapsort(){
    buildMaxHeap();

    int i;
    for(i = heapsize - 1; i > 0; --i){
        std::swap(A[0], A[i]);

        /**
         * Decrease the heap size as right of heap is already sorted
         */
        --heapsize;

        /**
         * Again max heapify the rest of the heap
         */
        maxHeapify(0);
    }
}

int main(){
    int i;

    clock_t begin, end;
    double time_elapsed;

    srand(time(NULL));
    for(i=0; i<SIZE; ++i){
        A[i] = rand() % SIZE;
        printf("%d ", A[i]);
    }
    printf("\n");

    printf("Sorting Now....\n");
    begin = clock();
    heapsort();
    end = clock();

    time_elapsed = (double)(end - begin) / CLOCKS_PER_SEC;

    for(i=0; i<SIZE; ++i)
        printf("%d ", A[i]);

    printf("\n\nTime elapsed: %lf\n", time_elapsed);

    return 0;
}

UVA Problem 12015 – Google is Feeling Lucky Solution

UVA Problem 12015 – Google is Feeling Lucky Solution:


Click here to go to this problem in uva Online Judge.

Solving Technique:

This is a sorting problem. In this problem we need to find biggest relevance number ( the second input / parameter). Then print the strings associated with that number. Multiple numbers can have equal relevance in which case print all the matching strings.

Ideas:

This can be solved efficiently by sorting inputs and based on that only print the strings / web addresses with biggest relevance number. Then if a lower relevance number is found stop processing. Since it was sorted ( ascending – start from last index, descending – start from index 0 )  if any lower value is found, further processing won’t yield any large relevance value.

Another method is using priority queue and store elements in key value pair. Then pop the biggest values and print their string.

Here my implementation is simple get the max value. Then brute force search all inputs for that value. If any value match the biggest relevance value print the string.

Important:  Be sure to add or print a new line after each output unless otherwise specified. The outputs should match exactly because sometimes even a space character causes the answer to be marked as wrong answer. Please compile with c++ compiler as some of my codes are in c and some in c++.


Input:

2
www.youtube.com 1
www.google.com 2
www.google.com.hk 3
www.alibaba.com 10
www.taobao.com 5
www.bad.com 10
www.good.com 7
www.fudan.edu.cn 8
www.university.edu.cn 9
acm.university.edu.cn 10
www.youtube.com 1
www.google.com 2
www.google.com.hk 3
www.alibaba.com 11
www.taobao.com 5
www.bad.com 10
www.good.com 7
www.fudan.edu.cn 8
acm.university.edu.cn 9
acm.university.edu.cn 10

 


Output:

Case #1:
www.alibaba.com
www.bad.com
acm.university.edu.cn
Case #2:
www.alibaba.com

Code:

/**
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 * Problem: UVA 12015 Google is feeling lucky
 */

#include<stdio.h>

static char s[10][100];
static unsigned r[10];

static unsigned c, n, max, i;

int main(){

    scanf("%u", &n);

    while(n--){
        scanf("%s %u", &s[0], &r[0]);
        max = r[0];

        for(i = 1; i < 10; ++i){
            scanf("%s %u", &s[i], &r[i]);
            if(r[i] > max)
                max = r[i];
        }

        printf("Case #%u:\n", ++c);
        for(i = 0; i < 10; ++i){
            if(r[i] == max)
                printf("%s\n", s[i]);
        }
    }
    return 0;
}

UVA Problem 12149 – Feynman Solution

UVA Problem 12149 – Feynman Solution:


Click here to go to this problem in uva Online Judge.

Solving Technique:

The problem asks given a number n how many squares are there in n by n grid. The relation can be found out by drawing n*n sqares and counting the squares. Since it will be very hard to draw and count more than 4 by 4 grid. We can try 1 by 1, 2 by 2, 3 by 3, 4 by 4 grid and count the number of squares. From there we can try to guess an equation.

For,
1*1 grid =   1 Square = 1
2*2 grid =   5 Square = 1 + 2^2
3*3 grid = 14 Square = 1 + 2^2 + 3^2
4*4 grid = 30 Square = 1 + 2^2 + 3^2 + 4^2

Here the series is,
1^2 + 2^2 + 3^2 + 4^2 + ….. n^2
Which is the sum of first n squares.

Instead of calculating with this formula a simpler formula exists.
1^2 + 2^2 + … + n^2 = n(n + 1)(2n + 1) / 6

The proof for this formula can be found here.

Important:  Be sure to add or print a new line after each output unless otherwise specified. The outputs should match exactly because sometimes even a space character causes the answer to be marked as wrong answer. Please compile with c++ compiler as some of my codes are in c and some in c++.


Input:

2
1
8
0

Output:

5
1
204

Code:

/**
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 * Problem: UVA 12149 Feynman
 * Type:    Mathematics ( 1^2 + 2^2 + .... + n^2 )
 */

#include<stdio.h>

int main(){
    static unsigned n;

    while(scanf("%u",&n) && n)
        printf("%u\n", n * (n + 1) * (2 * n + 1 ) / 6 );

    return 0;
}

UVA Problem 11727 – Cost Cutting Solution

UVA Problem 11727 – Cost Cutting Solution:


Click here to go to this problem in uva Online Judge.

Solving Technique:

Very easy problem. We are given 3 numbers in each test case. Among those three numbers we need to print the median value.

Two codes given below one solved with simple if else branching, another one is solved using STL sort algorithm. Can be solved also using stl nth_element  but it is too much for this problem. Use of nth_element shown in UVA Problem 10041 Vito’s Family.

Important:  Be sure to add or print a new line after each output unless otherwise specified. The outputs should match exactly because sometimes even a space character causes the answer to be marked as wrong answer. Please compile with c++ compiler as some of my codes are written in c and some in c++.


Input:

3
1000 2000 3000
3000 2500 1500
1500 1200 1800

 


Output:

Case 1: 2000
Case 2: 2500
Case 3: 1500

Code C:

/**
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 * Problem: UVA 11727 - Cost Cutting
 */

#include<stdio.h>

int main(){
    static unsigned i, n, a, b, c;
    scanf("%u", &n);

    for(i = 1; i <= n; ++i){
        scanf("%u%u%u",&a,&b,&c);

        if(a > b && a > c)
            printf("Case %u: %u\n", i, b > c ? b : c);
        else if(b > c)
            printf("Case %u: %u\n", i, c > a ? c : a);
        else
            printf("Case %u: %u\n", i, a > b ? a : b);
    }
    return 0;
}

Code STL Sort:

/**
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 * Problem: UVA 11727 - Cost Cutting
 */

#include<cstdio>
#include<algorithm>

static unsigned a[4];

int main(){
    static unsigned i, j, n;
    scanf("%u", &n);

    for(i = 1; i <= n; ++i){
        for(j = 0; j < 3; ++j)
            scanf("%u", &a[j]);

        std::sort(a, a + 3);
        printf("Case %u: %u\n", i, a[1]);
    }

    return 0;
}

UVA Problem 10684 – The jackpot Solution

UVA Problem 10684 – The jackpot Solution:


Click here to go to this problem in uva Online Judge.

Solving Technique:

This is an maximum sub array sum problem. Here we need find maximum subarray sum in 1D array. It can be solved easily with Kadane’s algorithm in O(n) time.

One thing to keep in mind the sample input isn’t properly aligned. So input format may be a bit confusing.

Explanation:

If the sum of array elements become 0 then we should set the sum to zero. Meaning we didn’t take any previous elements. Otherwise if we keep sum negative then we’ll never have the correct answer. Since we could get a bigger sum by discarding negative sum subset.

For example,

5
12  -4  -10  4  9

Here from first element to -10 we have a sum of -2. If we then add 4, 9 to the current sum -2 the max value is 11. But we could get a better result by discarding all previous sum since 12, -4, -10 produces a negative sum. There is no meaning taking a negative value. So discarding all previous sums till -10 then adding 4, 9 we get a max value of 13.

Important:  Be sure to add or print a new line after each output unless otherwise specified. The outputs should match exactly because sometimes even a space character causes the answer to be marked as wrong answer.


Input:

5
12  -4  -10  4  9
3
-2 -1 -2
0

 


Output:

The maximum winning streak is 13.
Losing streak.

Code:

/**
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 * Problem: UVA 10684 - The jackpot
 */

#include<stdio.h>

static int subset[10002];

int main(){
	static unsigned n, i;
	static int sum, max;

	while(scanf("%u", &n) && n){

        sum = max = i = 0;

        for(; i < n; ++i){
            scanf("%d", &subset[i]);
            sum += subset[i];

            if(sum < 0)
                sum = 0;

            if(sum > max)
                max = sum;
        }

        if(max > 0)
            printf("The maximum winning streak is %d.\n", max);
        else
            printf("Losing streak.\n");
	}
	return 0;
}