Menu
Topics Index
...
`

Weekend Hack - 16 Feb 2013 - Results

Thanks to Srihari Adelli, Raghu Ram Bharadwaj Diddigi, Tejaswini Rao, Deepika Koduri and Srinivas Rao Bolla for spending so much time, coming up with original and innovative answers and for submitting them. Thanks to many others who have tried to get the solution.
We have reviewed the solutions as per the criteria mentioned at Weekend Hack and included the comments below. Few minor comments found are included below in the order of the submission. These comments are not intended to point out the mistakes in the solutions but to learn from them.

The winner of the Weekend Hack 16 Feb 2013 - 1 is Srihari Adelli. He will get a recharge or gift voucher worth Rs. 125.
The winner of the Weekend Hack 16 Feb 2013 - 2 is Srinivas Rao Bolla. He will get a recharge or gift voucher worth Rs. 250. We will give the bonus amount of Rs. 100 to Tejaswini Rao Potlapally since her code is not way far off from the topper.

To parse the molecule and get the atoms count

Write a program to parse the molecule and get the atoms count.

Input (String) Output (Map)
C6H12OH {C=6, O=1, H=13}
Fe2Cl3 {Cl=3, Fe=2}
H2SO3 {S=1, O=3, H=2}
NH4OH {N=1, O=1, H=5}
NaOH {O=1, H=1, Na=1}

Solution 1 - Submitted on Sat Feb 16 13:27:56 2013

import java.util.HashMap;
import java.util.Map;

class ParseMolecule {

    public static void main(String s[]) {
        System.out.println("The atoms count in the molecule C6H12OH is :" + getElementsMap("C6H12OH"));
    }

    public static Map getElementsMap(String molecule) {
        HashMap map = new HashMap();
        int i = 0;
        int size = molecule.length();
        while (i < size) {
            String atomicsymbol = "";
            String numberOfAtoms = "1";
            boolean visit = true, visitedonce = false;
            while (i < molecule.length() && ((Character.isLetter(molecule.charAt(i)) && visit) || Character.isLowerCase(molecule.charAt(i)))) {
                if (Character.isLowerCase(molecule.charAt(i)))
                    atomicsymbol += molecule.charAt(i);
                else {
                    atomicsymbol = "" + molecule.charAt(i);
                    visit = false;
                }
                i++;
            }
            while (i < size && Character.isDigit(molecule.charAt(i))) {
                if (!visitedonce) {
                    numberOfAtoms = "" + molecule.charAt(i);
                    visitedonce = true;
                } else
                    numberOfAtoms += molecule.charAt(i);
                i++;
            }
            if (map.containsKey(atomicsymbol))
                map.put(atomicsymbol, Integer.parseInt(numberOfAtoms) + map.get(atomicsymbol));
            else
                map.put(atomicsymbol, Integer.parseInt(numberOfAtoms));
        }
        return map;
    }
}

Review Comments

  1. Correct usage of while loop for iterating until the characters end or the numbers end.
  2. Could have done with out the variables visit and visitedonce.
  3. Proper naming conventions followed and effective use of the methods like Character.isDigit, isLowerCase etc
  4. The code is easy to understand.

Solution 2 - Submitted on Sat Feb 16 14:08:04 2013

import java.util.HashMap;
import java.util.Map;

class ParseMolecule {

    public static void main(String s[]) {
        System.out.println("The atoms count in the molecule C6H12OH is :" + getElementsMap("C6H12OH"));
    }

    public static Map getElementsMap(String molecule) {
        HashMap hm = new HashMap();
        char[] c = molecule.toCharArray();
        int i = 0;
        String s;
        while (i < molecule.length()) {
            Integer res = 1;
            if (i + 1 < molecule.length() && molecule.codePointAt(i + 1) >= 97) {
                s = new String(c, i, 2);
                i = i + 2;
            } else {
                s = new String(c, i, 1);
                i = i + 1;
            }
            if (i < molecule.length() && molecule.codePointAt(i) < 60) {
                res = new Integer(new String(c, i, 1));
                if (i + 1 < molecule.length() && molecule.codePointAt(i + 1) < 60) {
                    Integer x = new Integer(new String(c, i + 1, 1));
                    res = res * 10 + x;
                    i = i + 2;
                } else
                    i = i + 1;
            }
            if (hm.get(s) != null) {
                int x = hm.get(s);
                res += x;
                hm.remove(s);
            }
            hm.put(s, res);
        }
        return hm;
    }
}

Review Comments

  1. The code is clear, but naming of variables like s, res and hm could have been better.
  2. We could have used Character.isUpperCase, isDigit to find the character details instead of comparison with 60, 97 etc.
  3. Will not work for formulas like C123H256OH, where the number of consecutive digits are more than 2.

Solution 3 - Submitted on Sat Feb 16 15:09:47 2013

import java.util.HashMap;
import java.util.Map;

class ParseMolecule {

    public static void main(String s[]) {
        System.out.println("The atoms count in the molecule C6H12OH is :" + getElementsMap("C6H12OH"));
    }

    public static Map getElementsMap(String molecule) {
        int size = molecule.length();
        String str[] = new String[size];
        int[] atoms = new int[size];
        int k = 0, j = 0;
        for (int i = 0; i < size; i++)/*code for finding individual molecules and corresponding atoms count*/
        {
            char ch = molecule.charAt(i);
            if (isUpper(ch)) {
                str[k++] = Character.toString(ch);
                atoms[j++] = 1;
            } else if (isLower(ch)) {
                String s = Character.toString(ch);
                str[k - 1] += s;
            } else {
                if (isNum(molecule.charAt(i - 1)))
                    atoms[j - 1] = atoms[j - 1] * 10 + (ch - '0');
                else {
                    atoms[--j] = ch - '0';
                    j++;
                }
            }
        }
        String[] str1 = new String[k]; /*code to remove duplicates*/
        int[] in1 = new int[k];
        int m = -1;
        for (int i = 0; i < k; i++) {
            if (!str[i].equals("0")) {
                str1[++m] = str[i];
                in1[m] = atoms[i];
            } else
                continue;
            for (int j1 = i + 1; j1 < k; j1++) {
                if (str[i].equals(str[j1])) {
                    str[j1] = "0";
                    in1[m] += atoms[j1];
                }
            }
        }
        Map map = new HashMap();
        for (int i = 0; i < m + 1; i++)
            map.put(str1[i], in1[i]);
        return map;
    }

    private static boolean isUpper(char ch) {
        if (ch >= 'A' && ch <= 'Z')
            return true;
        else
            return false;
    }

    private static boolean isLower(char ch) {
        if (ch >= 'a' && ch <= 'z')
            return true;
        else
            return false;
    }

    private static boolean isNum(char ch) {
        if (ch >= '0' && ch <= '9')
            return true;
        else
            return false;
    }
}

Review Comments

  1. The code is not very clear and a bit complex and it could have been better.
  2. Could have used methods like Character.isUpperCase, Character.isLowerCase, Character.isDigit instead isUpper, isLower, isNum
  3. In isUpper/isLower/isDigit method, we could have returned the condition itself, than checking the condition and then returning true or false.

Solution 4 - Submitted on Sun Feb 17 10:58:20 2013

import java.util.Map;

class ParseMolecule {

    public static void main(String s[]) {
        System.out.println("The atoms count in the molecule C6H12OH is :" + getElementsMap("C6H12OH"));
    }

    public static Map getElementsMap(String molecule) {
        Map out = new HashMap();
        int i = 0;
        while (i < molecule.length()) {
            String temp = Character.toString(molecule.charAt(i++));
            while (i < molecule.length() && !Character.isDigit(molecule.charAt(i)) && Character.isLowerCase(molecule.charAt(i)))
                temp += Character.toString(molecule.charAt(i++));
            String num = "";
            int n = 1;
            if (i < molecule.length() && Character.isDigit(molecule.charAt(i))) {
                while (i < molecule.length() && Character.isDigit(molecule.charAt(i)))
                    num += Character.toString(molecule.charAt(i++));
                if (out.containsKey(temp))
                    n = out.get(temp) + Integer.parseInt(num);
                else
                    n = Integer.parseInt(num);
                out.put(temp, n);
            } else {
                if (out.containsKey(temp))
                    n = out.get(temp) + 1;
                out.put(temp, n);
            }
        }
        return out;
    }
}

Review Comments

  1. Effective use of while loops for separating atoms and the count.
  2. The code is simple and easy to understand.
  3. Some duplicate code while checking and adding the count. We could have given better names for temp, n and num.
  4. Although, not necessary here, it is better to include the while loop body in flower brackets.

To find the path of non intersecting polygon which goes through all those points

Given the list of points, write a program to find the path of non intersecting polygon which goes through all those points. Non intersecting polygon is a polygon which does not intersect itself.
While returning the output, it is not necessary to exactly match the lines which are given in the requirements below. As long as they form a non intersecting polygon, it will be accepted.

Input (List of Points) Example Output (List of Lines)
[[3.0,3.0], [4.0,2.0], [1.0,1.0], [2.0,4.0], [5.0,5.0], [1.0,5.0], [2.0,7.0]] [[4.0,2.0]-[1.0,1.0], [1.0,1.0]-[1.0,5.0], [1.0,5.0]-[2.0,4.0], [2.0,4.0]-[3.0,3.0], [3.0,3.0]-[2.0,7.0], [2.0,7.0]-[5.0,5.0], [5.0,5.0]-[4.0,2.0]]
[[4.0,2.0], [1.0,1.0], [5.0,5.0], [1.0,5.0], [3.0,3.0], [2.0,7.0], [2.0,4.0]] [[4.0,2.0]-[1.0,1.0], [1.0,1.0]-[1.0,5.0], [1.0,5.0]-[2.0,7.0], [2.0,7.0]-[5.0,5.0], [5.0,5.0]-[2.0,4.0], [2.0,4.0]-[3.0,3.0], [3.0,3.0]-[4.0,2.0]]
[[2.0,2.0], [4.0,5.0], [3.0,1.0], [6.0,4.0]] [[2.0,2.0]-[4.0,5.0], [4.0,5.0]-[6.0,4.0], [6.0,4.0]-[3.0,1.0], [3.0,1.0]-[2.0,2.0]]
[[0.0,0.0], [3.0,0.0], [0.0,4.0]] [[0.0,0.0]-[3.0,0.0], [3.0,0.0]-[0.0,4.0], [0.0,4.0]-[0.0,0.0]]
[[2.0,2.0], [3.0,1.0], [5.0,1.0], [5.0,4.0]] [[2.0,2.0]-[3.0,1.0], [3.0,1.0]-[5.0,1.0], [5.0,1.0]-[5.0,4.0], [5.0,4.0]-[2.0,2.0]]
[[2.0,2.0], [3.0,4.0], [4.0,1.0], [8.0,5.0], [6.0,8.0]] [[2.0,2.0]-[3.0,4.0], [3.0,4.0]-[6.0,8.0], [6.0,8.0]-[8.0,5.0], [8.0,5.0]-[4.0,1.0], [4.0,1.0]-[2.0,2.0]]

Solution 1 - Submitted on Wed Feb 20 02:40:36 2013

import java.util.List;

class FindNonIntersectingPolygon {

    public static void main(String s[]) {
        List points = new ArrayList();
        points.add(new Point(3, 3));
        points.add(new Point(4, 2));
        points.add(new Point(1, 1));
        points.add(new Point(2, 4));
        points.add(new Point(5, 5));
        points.add(new Point(1, 5));
        points.add(new Point(2, 7));
        System.out.println("The path of the polygon : " + getPath(points));
    }

    public static List getPath(List points) {
        List result = new ArrayList();
        List SmallerX = new ArrayList();
        List GreaterX = new ArrayList();
        List point = new ArrayList();
        class sort_yDescending implements Comparator {

            public int compare(Object object1, Object object2) {
                Point s1 = (Point) object1;
                Point s2 = (Point) object2;
                if (s1.y == s2.y)
                    return 0;
                else if (s1.y > s2.y)
                    return -1;
                else
                    return 1;
            }
        }
        class sort_xAscending implements Comparator {

            public int compare(Object object1, Object object2) {
                Point s1 = (Point) object1;
                Point s2 = (Point) object2;
                if (s1.x == s2.x) {
                    if (s1.y == s2.y)
                        return 0;
                    else if (s1.y > s2.y)
                        return 1;
                    else if (s1.y < s2.y)
                        return -1;
                    return 0;
                } else if (s1.x > s2.x)
                    return 1;
                else
                    return -1;
            }
        }
        class sort_xDescending implements Comparator {

            public int compare(Object object1, Object object2) {
                Point s1 = (Point) object1;
                Point s2 = (Point) object2;
                if (s1.x == s2.x)
                    return 0;
                else if (s1.x > s2.x)
                    return -1;
                else
                    return 1;
            }
        }
        /*moving in the positive:x-axis,by sorting  the point.x in AscendingOrder and storing,except the firstone,since to move with respect to that point,*/
        point.addAll(points);
        Collections.sort(point, new sort_xAscending());
        int index1 = 0, index2 = 0;
        Point p3 = points.get(0);
        Point test = points.get(1);
        if (p3.equals(point.get(0)) && p3.x == test.x) {
            for (Point chosenpoint : point) {
                if (chosenpoint.x > p3.x) {
                    p3 = chosenpoint;
                    break;
                }
            }
        }
        Point p1 = p3;
        Point temporarypoint = new Point(0, 0);
        while (index2 < point.size()) {
            Point p2 = point.get(index2);
            temporarypoint = p1;
            if (p2.x >= p3.x && p2.y > p3.y && !p1.equals(p2)) {
                result.add(new Line(p1, p2));
                temporarypoint = p2;
                index1 = index2;
                p1 = point.get(index1);
                index2++;
            } else {
                if (!p1.equals(p2)) {
                    if (p2.x >= p3.x)
                        GreaterX.add(p2); /*The points,whose p.x is greater,but not p.y ,is stored.*/
                    else
                        SmallerX.add(p2); /*The points whose p.x is less than are stroed in this.*/
                }
                index2++;
            }
        }
        Collections.sort(GreaterX, new sort_xDescending());
        Collections.sort(SmallerX, new sort_yDescending());
        SmallerX.addAll(GreaterX);
        for (Point l : SmallerX) {
            result.add(new Line(temporarypoint, l));
            temporarypoint = l;
        }
        Line temp = result.get(0);
        result.add(new Line(temporarypoint, temp.p1)); /*The line consists of lastpoint and first.*/
        return result;
    }
}

class Point {

    double x;
    double y;

    Point(double x, double y) {
        this.x = x;
        this.y = y;
    }

    @Override
    public boolean equals(Object obj) {
        return Math.abs(x - ((Point) obj).x) < 0.00001 && Math.abs(y - ((Point) obj).y) < 0.00001;
    }

    @Override
    public String toString() {
        return "[" + x + "," + y + "]";
    }
}

class Line {

    Point p1;
    Point p2;

    public Line(Point p1, Point p2) {
        this.p1 = p1;
        this.p2 = p2;
    }

    @Override
    public String toString() {
        return p1.toString() + "-" + p2.toString();
    }
}

Review Comments

  1. The way comparators are used for sorting is good. In comparators we could have returned the difference of the values than checking for less than and greater than and return -1, 1
  2. Although the logic is simple to understand, it might not work for all the cases.
  3. Does not seem to work for points [[2.0,2.0], [3.0,3.0], [4.0,2.0], [6.0,2.0], [1.0,10.0], [5.0,5.0], [5.0,2.0], [1.0,5.0], [2.0,7.0]]
  4. Does not seem to work for points [[2.0,2.0], [3.0,3.0], [4.0,4.0], [1.0,1.0], [5.0,5.0], [5.0,2.0], [1.0,5.0], [2.0,7.0]]
  5. Does not seem to work for points [[1.0,1.0]-[3.0,2.0], [3.0,2.0]-[3.0,3.0], [3.0,3.0]-[4.0,4.0], [4.0,4.0]-[5.0,5.0], [5.0,5.0]-[1.0,1.0]]

Solution 2 - Submitted on Tue Feb 19 20:55:48 2013

import java.util.List;

class FindNonIntersectingPolygon {

    public static void main(String s[]) {
        List points = new ArrayList();
        points.add(new Point(3, 3));
        points.add(new Point(4, 2));
        points.add(new Point(1, 1));
        points.add(new Point(2, 4));
        points.add(new Point(5, 5));
        points.add(new Point(1, 5));
        points.add(new Point(2, 7));
        System.out.println("The path of the polygon : " + getPath(points));
    }

    public static List getPath(List points) {
        points = align(points);
        List polygon = new ArrayList();
        Point pivot = getpivot(points);
        points = sort(points, pivot);
        System.out.println(points);
        for (int i = 0; i < points.size() - 1; i++) {
            polygon.add(new Line(points.get(i), points.get(i + 1)));
        }
        return polygon;
    }

    public static List align(List points) {
        Point one, two;
        for (int i = 0; i < points.size() - 1; i++) {
            for (int j = i + 1; j < points.size(); j++) {
                one = points.get(i);
                two = points.get(j);
                if (Math.abs(one.x - two.x) == Math.abs(one.y - two.y) && one.x < two.x && one.y < two.y) {
                    points.set(i, two);
                    points.set(j, one);
                }
            }
        }
        return points;
    }

    /*Function to find lowest y coordinate*/
    public static Point getpivot(List points) {
        double x = points.get(0).x;
        double y = points.get(0).y;
        for (Point p : points) {
            if (y > p.y) {
                y = p.y;
                x = p.x;
            }
            if (y == p.y && x > p.x)
                x = p.x;
        }
        return new Point(x, y);
    }

    /*Function to sort in increasing order of angle made by line joining pivot and other points with positive x-axis*/
    public static List sort(List points, Point pivot) {
        int index = 0;
        final double constant = 361.0;
        List sorted = new ArrayList();
        double array[] = new double[points.size()];
        for (Point p : points) {
            double angle = Math.toDegrees(Math.atan2(p.y - pivot.y, p.x - pivot.x));
            if (angle >= 0)
                array[index++] = angle;
            else
                array[index++] = 360.0 - angle;
            if ((p.x == pivot.x) && (p.y == pivot.y)) {
                index--;
                array[index++] = -1.0;
            }
        }
        double min = constant;
        int ind = 0;
        for (int j = 0; j < array.length; j++) {
            for (int i = 0; i < array.length; i++) {
                if (min > array[i]) {
                    min = array[i];
                    ind = i;
                }
            }
            min = array[ind] = constant;
            sorted.add(points.get(ind));
        }
        sorted.add(pivot);
        return sorted;
    }
}

class Point {

    double x;
    double y;

    Point(double x, double y) {
        this.x = x;
        this.y = y;
    }

    @Override
    public boolean equals(Object obj) {
        return Math.abs(x - ((Point) obj).x) < 0.00001 && Math.abs(y - ((Point) obj).y) < 0.00001;
    }

    @Override
    public String toString() {
        return "[" + x + "," + y + "]";
    }
}

class Line {

    Point p1;
    Point p2;

    public Line(Point p1, Point p2) {
        this.p1 = p1;
        this.p2 = p2;
    }

    @Override
    public String toString() {
        return p1.toString() + "-" + p2.toString();
    }
}

Review Comments

  1. The code is well written and is easy to understand.
  2. The logic of getting the angles to create the polygon is good.
  3. For sorting by angles, it would have been easier if Comparator was used instead of the arrays.
  4. Naming conventions could be better and the name of the constants 361 and 360 could be clearer.
  5. Does not seem to work for points [[2.0,2.0], [3.0,3.0], [4.0,2.0], [6.0,2.0], [1.0,10.0], [5.0,5.0], [5.0,2.0], [1.0,5.0], [2.0,7.0]]

Solution 3 - Submitted on Wed Feb 20 01:04:00 2013

import java.util.Collections;
import java.util.Comparator;
import java.util.List;

class FindNonIntersectingPolygon {

    public static void main(String s[]) {
        List points = new ArrayList();
        points.add(new Point(3, 3));
        points.add(new Point(4, 2));
        points.add(new Point(1, 1));
        points.add(new Point(2, 4));
        points.add(new Point(5, 5));
        points.add(new Point(1, 5));
        points.add(new Point(2, 7));
        System.out.println("The path of the polygon : " + getPath(points));
    }

    public static List getPath(List points) {
        sort(points);
        System.out.println(points);
        List output = new ArrayList();
        int size = points.size();
        for (int i = 0; i < size - 1; i++)
            output.add(new Line(points.get(i), points.get(i + 1)));
        int line = intersectCondition(points.get(size - 1), points.get(0), output);
        System.out.println(line);
        if (line >= 0) {
            for (int i = output.size() - 1; i >= line; i--)
                output.remove(i);
            Collections.swap(points, line + 1, points.size() - 1);
            for (int i = line; i < size - 1; i++)
                output.add(new Line(points.get(i), points.get(i + 1)));
        }
        output.add(new Line(points.get(size - 1), points.get(0)));
        return output;
    }

    public static int intersectCondition(Point m1, Point m2, List output) {
        System.out.println(output.size());
        int count = 0;
        Point p1 = new Point(0, 0);
        Point p2 = new Point(0, 0);
        double first = output.get(0).p1.x;
        for (Line temp : output) {
            p1 = temp.p1;
            p2 = temp.p2;
            if (count != output.size() - 1 && count != 0 && m1.x != first) {
                double sign1 = (p2.x - p1.x) * (m1.y - p2.y) - (p2.y - p1.y) * (m1.x - p2.x);
                double sign2 = (p2.x - p1.x) * (m2.y - p2.y) - (p2.y - p1.y) * (m2.x - p2.x);
                System.out.println(sign1 + "  " + sign2);
                if (sign1 * sign2 > 0 || sign1 == 0 || sign2 == 0) {
                } else
                    break;
            }
            count++;
        }
        if (count == output.size())
            return -1;
        else
            return count;
    }

    public static void sort(List points) {
        Collections.sort(points, new Comparator() {

            @Override
            public int compare(Point o1, Point o2) {
                if (o1.y != o2.y)
                    return (int) (o1.y - o2.y);
                return (int) (o1.x - o2.x);
            }
        });
        double first = points.get(0).x;
        int index = 0;
        int array[] = new int[points.size()];
        int i = -1;
        List p = new ArrayList();
        for (Point temp : points) {
            if (temp.x <= first && index != 0) {
                p.add(new npoint(temp));
                i++;
                array[i] = index;
            }
            index++;
        }
        for (int k = 0; k <= i; k++) {
            points.remove(array[k]);
            array[k + 1]--;
        }
        Collections.sort(p, new Comparator() {

            public int compare(npoint o1, npoint o2) {
                if (o1.y != o2.y)
                    return (int) (o2.y - o1.y);
                return (int) (o2.x - o1.x);
            }
        });
        points.addAll(p);
        System.out.println(points);
    }
}

class npoint extends Point {

    npoint(Point next) {
        super(next.x, next.y);
    }
}

class Point {

    double x;
    double y;

    Point(double x, double y) {
        this.x = x;
        this.y = y;
    }

    @Override
    public boolean equals(Object obj) {
        return Math.abs(x - ((Point) obj).x) < 0.00001 && Math.abs(y - ((Point) obj).y) < 0.00001;
    }

    @Override
    public String toString() {
        return "[" + x + "," + y + "]";
    }
}

class Line {

    Point p1;
    Point p2;

    public Line(Point p1, Point p2) {
        this.p1 = p1;
        this.p2 = p2;
    }

    @Override
    public String toString() {
        return p1.toString() + "-" + p2.toString();
    }
}

Review Comments

  1. The way methods are created according to the fuctionality is good. Sort method could be made simpler.
  2. Not sure why we need the class npoint.
  3. The variables could be named better for clear understanding of the code.
  4. Does not seem to work for points [[2.0,2.0], [3.0,3.0], [4.0,2.0], [6.0,2.0], [1.0,10.0], [5.0,5.0], [5.0,2.0], [1.0,5.0], [2.0,7.0]]
  5. Does not seem to work for points [[3.0,1.0], [3.0,7.0], [3.0,3.0], [3.0,5.0], [4.0,4.0], [4.0,3.0], [4.0,2.0], [4.0,1.0], [6.0,2.0], [7.0,5.0], [8.0,1.0], [10.0,0.0]]

© meritcampus 2019

All Rights Reserved.