Thursday, January 29, 2015

WhatSort

Problem:

TopCoder Problem Statement - WhatSort
Single Round Match 164 Round 1 - Division I, Level Two
Single Round Match 164 Round 1 - Division II, Level Three

Overview:

Determine the sorting method used to arrange a group of people.

Java Source:
001: import java.util.Arrays;
002: import java.util.Comparator;
003: 
004: class Person {
005: 
006:     final int age;
007:     final int weight;
008:     final String name;
009: 
010:     Person(String name, int age, int weight) {
011:         this.name = name;
012:         this.age = age;
013:         this.weight = weight;
014:     }
015: }
016: 
017: class PersonComparator implements Comparator {
018: 
019:     final String type;
020: 
021:     PersonComparator(String type) {
022:         this.type = type;
023:     }
024: 
025:     @Override
026:     public int compare(Person p1, Person p2) {
027: 
028:         int x;
029: 
030:         switch (type) {
031:             case "NAW":
032:                 x = compareName(p1, p2);
033:                 if (x != 0) return x;
034:                 x = compareAge(p1, p2);
035:                 if (x != 0) return x;
036:                 return compareWeight(p1, p2);
037: 
038:             case "NWA":
039:                 x = compareName(p1, p2);
040:                 if (x != 0) return x;
041:                 x = compareWeight(p1, p2);
042:                 if (x != 0) return x;
043:                 return compareAge(p1, p2);
044: 
045:             case "ANW":
046:                 x = compareAge(p1, p2);
047:                 if (x != 0) return x;
048:                 x = compareName(p1, p2);
049:                 if (x != 0) return x;
050:                 return compareWeight(p1, p2);
051: 
052:             case "AWN":
053:                 x = compareAge(p1, p2);
054:                 if (x != 0) return x;
055:                 x = compareWeight(p1, p2);
056:                 if (x != 0) return x;
057:                 return compareName(p1, p2);
058: 
059:             case "WAN":
060:                 x = compareWeight(p1, p2);
061:                 if (x != 0) return x;
062:                 x = compareAge(p1, p2);
063:                 if (x != 0) return x;
064:                 return compareName(p1, p2);
065: 
066:             case "WNA":
067:                 x = compareWeight(p1, p2);
068:                 if (x != 0) return x;
069:                 x = compareName(p1, p2);
070:                 if (x != 0) return x;
071:                 return compareAge(p1, p2);
072: 
073:             default:
074:                 return 0;
075:         }
076: 
077:     }
078: 
079:     private int compareName(Person p1, Person p2) {
080:         return p1.name.compareTo(p2.name);
081:     }
082: 
083:     private int compareAge(Person p1, Person p2) {
084:         return new Integer(p1.age).compareTo(p2.age);
085:     }
086: 
087:     private int compareWeight(Person p1, Person p2) {
088:         return -1 * new Integer(p1.weight).compareTo(p2.weight);
089:     }
090: }
091: 
092: public class WhatSort {
093: 
094:     public String sortType(String[] name, int[] age, int[] wt) {
095: 
096:         Person[] inputList = new Person[name.length];
097: 
098:         for (int i = 0; i < name.length; i++) {
099:             Person p = new Person(name[i], age[i], wt[i]);
100:             inputList[i] = p;
101:         }
102: 
103:         String method = null;
104: 
105:         String[] sortingMethods = new String[]{"NAW", "NWA", "ANW",
106:                 "AWN", "WAN", "WNA"};
107: 
108:         for (String s : sortingMethods) {
109:             String result = testSortingMethod(inputList, s);
110:             if (result != null) {
111:                 if (method != null) {
112:                     return "IND";
113:                 } else {
114:                     method = result;
115:                 }
116:             }
117:         }
118: 
119:         return (method == null) ? "NOT" : method;
120:     }
121: 
122:     private String testSortingMethod(Person[] inputList, String method) {
123: 
124:         Person[] sortedList = new Person[inputList.length];
125: 
126:         System.arraycopy(inputList, 0, sortedList, 0, inputList.length);
127:         Arrays.sort(sortedList, new PersonComparator(method));
128: 
129:         return (Arrays.equals(inputList, sortedList)) ? method : null;
130:     }
131: 
132: }
Notes:

The approach is to sort the people using each of the six sorting methods described. If the sort matches the input, then that method may have been used. Just for check zero, or more than one possible solutions.

The Person class simply stores the age, weight, and name together; and allows us to create a Comparator to sort them.

The PersonComparator class provides the compare() method for comparing two Person objects. The PersonComparator constructor takes a String which determines the sorting method that it will use. This happens in the switch statement inside the compare() method. Each of the cases of the switch statement are the same, except that the order of the comparisons varies.

Be extra careful here to make sure that the items are getting sorted in the proper order. We can String.compare() and Integer.compare() for the name and age. However, since we want to sort weight in descending order, we need to multiple the result of the compare by -1 first before returning.

The sortType() method just creates an array of Person objects using the given input arrays, and then calls testSortingMethod() for each method, keep tracking of valid sorting methods along the way.

In the testSortingMethod() method, we make a copy of the original array, and then sort it using the given method. After it's sorted, we compare the copy to the original. Be sure to use Arrays.equals() to test to see if the two arrays contain the same elements in the same order. array1.equals(array2) will not work.

There was a lot of typing in this solution, but none of it was particularly hard. Just be careful in the compare() method and it'll work out.

PartySeats

Problem:

TopCoder Problem Statement - PartySeats
Single Round Match 164 Round 1 - Division II, Level Two

Overview:

Determine the arrangement of guests at a table for a dinner party.

Java Source:
01: import java.util.PriorityQueue;
02: import java.util.Queue;
03: 
04: public class PartySeats {
05: 
06:     public String[] seating(String[] attendees) {
07: 
08:         /*
09:         * Separate the boys from the girls.  By using a PriorityQueue, we
10:         * can easily pull out members in ascending order.
11:         */
12:         Queue boys = new PriorityQueue<>();
13:         Queue girls = new PriorityQueue<>();
14: 
15:         for (String s : attendees) {
16:             String[] attendee = s.split("\\s+");
17:             if ("boy".equals(attendee[1])) {
18:                 boys.add(attendee[0]);
19:             } else {
20:                 girls.add(attendee[0]);
21:             }
22:         }
23: 
24:         /*
25:         * Ensure the arrangement is possible.
26:         * The number of boys and girls must be equal, and both must be an
27:         * even number.
28:         */
29:         if ((boys.size() != girls.size()) || ((boys.size() % 2) != 0)) {
30:             return new String[0];
31:         }
32: 
33:         String[] result = new String[attendees.length + 2];
34:         result[0] = "HOST";
35:         boolean isBoyNext = false;
36: 
37:         for (int i = 1; i < result.length; i++) {
38: 
39:             // Seat the Hostess at the 1/2 way point.
40:             if (i == (result.length / 2)) {
41:                 result[i] = "HOSTESS";
42: 
43:             } else {
44:                 if (isBoyNext) {
45:                     result[i] = boys.poll();
46:                 } else {
47:                     result[i] = girls.poll();
48:                 }
49:             }
50: 
51:             isBoyNext = !isBoyNext;
52:         }
53: 
54:         return result;
55:     }
56: }
Notes:

We can create a legal arrangmenet if two conditions are met. First the number of boys must equals the number of girls. Second, the number of both must be divisible by two. Since we've already checked that they're equal, we only need to test one. These two conditions become pretty clear if you draw the solution out on a piece of paper.

We'll start by separating the boys from the girst. We can use Java's String.split() method to get the name and gender of each attendee. The espression split("\\s+") just splits on the next whitespace. Then we assign them to the correct Queue. A PriorityQueue was choosen it because it automatically keeps the entries in a sorted order. We'll get the names in the order we need them practically for free.

Next, we check to see that the two conditions are met. If so, we can proceed to building the result. The result String[] will have a length 2 larger than the input - in order to hold the HOST and HOSTESS. Position 0 gets the host, and length / 2 gets the HOSTESS. Then it's just a matter of alternating between pulling the next girl and then boy off their respective queues until the result array is full.

Justifier

Problem:

TopCoder Problem Statement - Justifier
Single Round Match 164 Round 1 - Division II, Level One

Overview:

Right justify a set of Strings so that their edges line up.

Java Source:
01: public class Justifier {
02: 
03:     public String[] justify(String[] textIn) {
04: 
05:         int longest = 0;
06: 
07:         // Find the longest string.
08:         for (int i = 0; i < textIn.length; i++)  {
09:             longest = Math.max(longest, textIn[i].length());
10:         }
11: 
12:         String[] result = new String[textIn.length];
13: 
14:         // Loop through each of the strings.
15:         for (int i = 0; i < textIn.length; i++)  {
16:             StringBuilder s = new StringBuilder(textIn[i]);
17: 
18:             // Insert spaces at the beginning until length == longest.
19:             while (s.length() < longest)  {
20:                 s.insert(0, " ");
21:             }
22: 
23:             result[i] = s.toString();
24:         }
25: 
26: 
27:         return result;
28:     }
29: 
30: }
Notes:

We can solve this easily in two steps. First, loop through all the Strings in textIn and make note of the longest. Then loop through each of the Strings again, and pad them with spaces at the beginning until their length matches the longest found in the first step.

Tuesday, January 27, 2015

Rochambo

Problem:

TopCoder Problem Statement - Rochambo
Single Round Match 163 Round 1 - Division I, Level One

Overview:

Determine how many rounds will be won in a Rochambo (rock, paper, scissors) match by following a given strategy.

Java Source:
01: public class Rochambo {
02: 
03:     public int wins(String opponent) {
04: 
05:         int numWins = 0;
06:         char previous2;
07:         char previous1;
08:         char current;
09: 
10:         for (int round = 0; round < opponent.length(); round++) {
11: 
12:             current = opponent.charAt(round);
13: 
14:             /*
15:             * First two moves are always Rock.  So if the opponent plays
16:             * Scissors, we win.
17:             */
18:             if (round < 2) {
19:                 if (current == 'S') numWins++;
20: 
21:             } else {
22: 
23:                 // Get opponents last 2 moves.
24:                 previous2 = opponent.charAt(round - 2);
25:                 previous1 = opponent.charAt(round - 1);
26: 
27:                 /*
28:                 * If the current move matches the last 2, we win by playing
29:                 * whatever would have beaten the last 2.
30:                 */
31:                 if ((previous2 == current) && (previous1 == current))  {
32:                     numWins++;
33: 
34:                     /*
35:                     * If the current and last 2 moves are all different, we
36:                     * win by playing what beats that which was not played in
37:                     * the previous 2 rounds.
38:                     */
39:                 } else if ((previous2 != previous1) &&
40:                         (current != previous1) &&
41:                         (current != previous2))  {
42:                     numWins++;
43:                 }
44:             }
45:         }
46: 
47:         return numWins;
48:     }
49: }
Notes:

Surprisingly easy for a Division 1 problem. All you need to do is look at the current, and previous 2 rounds played by your opponent.

If the current, 1st previous, and 2nd previous rounds all match then we'll win. We see the first two come in the same, and guess that the third will be the same, so we play whatever beats it.

If the current, 1st previous, and 2nd previous are all different, we will win here too. After seeing that the last two don't match, we'll play whatever beats the 3rd object.

In the first two rounds, we always play Rock. So if the opponent plays Scissors we win there too.

That's all there is to it.

Monday, January 26, 2015

Pool

Problem:

TopCoder Problem Statement - Pool
Single Round Match 163 Round 1 - Division I, Level Two
Single Round Match 163 Round 1 - Division II, Level Three

Overview:

Determine the fewest number of swaps necessary to re-order a set of billiard balls into a legal racking.

Java Source:
import java.util.PriorityQueue;

public class Pool {

    private enum BallType {SOLID, STRIPE, EIGHT}

    private static BallType[][] legalRacks = {{
            BallType.STRIPE,
            BallType.SOLID, BallType.SOLID,
            BallType.STRIPE, BallType.EIGHT, BallType.STRIPE,
            BallType.SOLID, BallType.STRIPE, BallType.SOLID, BallType.STRIPE,
            BallType.STRIPE, BallType.SOLID, BallType.STRIPE, BallType.SOLID,
            BallType.SOLID
    }, {
            BallType.SOLID,
            BallType.STRIPE, BallType.STRIPE,
            BallType.SOLID, BallType.EIGHT, BallType.SOLID,
            BallType.STRIPE, BallType.SOLID, BallType.STRIPE, BallType.SOLID,
            BallType.SOLID, BallType.STRIPE, BallType.SOLID, BallType.STRIPE,
            BallType.STRIPE
    }};

    /*
    * Represents a configuration of balls, and how many moves it took to
    * get there.  Includes some methods for swapping balls, and determining
    * how far away it is from a legal rack.
    */
    private class SearchNode implements Comparable {

        private BallType[] rack;
        private final int moves;
        private int numOutOfPlace = -1;

        SearchNode(BallType[] rack, int moves) {

            // Make a defensive copy of the rack that was passed in.
            this.rack = new BallType[rack.length];
            System.arraycopy(rack, 0, this.rack, 0, rack.length);

            this.moves = moves;
        }

        /*
        * Returns the number of balls that are out of place.  Since there
        * are more than one legal racks, it checks them all, and returns
        * the minimum.  Note, this calculation is only done once.
        */
        int getNumOutOfPlace() {

            if (numOutOfPlace >= 0)  {
                return numOutOfPlace;
            }

            numOutOfPlace = Integer.MAX_VALUE;

            // Check each legal configuration.
            for (int i = 0; i < legalRacks.length; i++) {

                int n = 0;

                for (int b = 0; b < rack.length; b++) {
                    if (rack[b] != legalRacks[i][b]) {
                        n++;
                    }
                }

                numOutOfPlace = Math.min(numOutOfPlace, n);
            }

            return numOutOfPlace;
        }

        /*
        * A heuristic representing how ideal this state is.  It is better
        * to have less balls out of place in a lower number of moves.
        */
        int getPriority() {
            return getNumOutOfPlace() + moves;
        }

        /*
        * Returns a new SearchNode with one pair of balls swapped.  Number
        * of moves is incremented by one.  If the 8 ball is out of position,
        * it will be swapped into the correct place first.
        */
        SearchNode swapBalls(BallType[] legalRack) {

            int ball1;
            int ball2;

            SearchNode newNode = new SearchNode(rack, moves + 1);

            // If the 8 ball is out of place, fix that first.
            if (rack[4] != BallType.EIGHT) {
                ball1 = 4;
                ball2 = 0;
                while (rack[ball2] != BallType.EIGHT) ball2++;  // Find the 8.
            } else {

                /*
                * ball1 is the first ball that is out of place - regardless
                * of it's type (solid / stripe).
                * ball2 is the first ball out of place of the type that
                * should be at the location of ball1.
                */
                ball1 = getFirstOutOfPlace(legalRack, null);
                ball2 = getFirstOutOfPlace(legalRack, legalRack[ball1]);
            }

            newNode.rack[ball1] = rack[ball2];
            newNode.rack[ball2] = rack[ball1];

            return newNode;
        }

        /*
        * Find the first ball that does not match the corresponding legal
        * rack.  If type is null, it can be either stripe or solid.  If
        * type is given, then the out of place ball must be of that type.
        */
        private int getFirstOutOfPlace(BallType[] legalRack, BallType type) {

            for (int i = 0; i < rack.length; i++) {
                if ((type == null) || (rack[i] == type)) {
                    if (rack[i] != legalRack[i]) {
                        return i;
                    }
                }
            }

            return -1;
        }

        // Sort SearchNodes based on their priority.
        public int compareTo(SearchNode o) {
            return Integer.compare(this.getPriority(), o.getPriority());
        }

    }

    public int rackMoves(int[] triangle) {

        /*
        * Using a PriorityQueue to process the possible solutions will allow
        * us to focus on the most promising paths first.  That is those closest
        * to a legal rack in the fewest number of moves.
        */
        PriorityQueue possibleSolutions = new PriorityQueue<>();

        /*
        * Convert the given input array into an array of BallType objects.
        * These will be easier to work with then constantly having to check
        * ranges to determine if the ball is a stripe or solid.
        */
        BallType[] rack = new BallType[triangle.length];
        for (int i = 0; i < triangle.length; i++) {
            if (triangle[i] < 8) rack[i] = BallType.SOLID;
            else if (triangle[i] > 8) rack[i] = BallType.STRIPE;
            else rack[i] = BallType.EIGHT;
        }

        // Put our starting position into the PriorityQueue
        SearchNode n = new SearchNode(rack, 0);
        possibleSolutions.add(n);

        // The fewest moves seen so far that leads to a legal rack.
        int minNumberOfMoves = Integer.MAX_VALUE;

        while (true) {

            if (possibleSolutions.isEmpty()) {
                return minNumberOfMoves;
            }

            // Get the most promising node.
            SearchNode s = possibleSolutions.poll();

            /*
            * If there are no balls out of place, check to see if this
            * is the best solution found so far.
            */
            if (s.getNumOutOfPlace() == 0) {
                minNumberOfMoves = Math.min(minNumberOfMoves, s.moves);

            } else {

                /*
                * Make sure the move that we're about to make keeps us below
                * the number of moves in the best solution.  Otherwise, there's
                * no point in trying it.
                */
                if ((s.moves + 1) < minNumberOfMoves) {
                    for (int i = 0; i < legalRacks.length; i++) {

                        /*
                        * Add to possible solutions swappings that will
                        * get us closer to each of the legal racks.
                        */
                        possibleSolutions.add(s.swapBalls(legalRacks[i]));
                    }
                }
            }

        }

    }
}

Notes:

The first thing I did was to create an enumerated type to represent the three types of billiard balls: Solid, Stripe, and 8-ball. It seemed easier to work with just these three and avoid having to deal with the individual values of the balls. With that, I created an array of legal rack configurations. Note that the legal racks are inverses of each other. Looking back, I probably could have made better use of that fact.

Next, I define an inner class called SearchNode. This holds a rack configuration, the number of moves required to reach this state, and some code to count the number of balls that are out of place, and to swap balls - leading to a new configuration. The method getPriority() gives us an idea of how good the current state is. The fewer balls out of place, and the less moves needed to reach this state, the better.

The swapBalls() method first looks to see if the 8 ball is in position 4. If it's not, then we'll swap the ball in position 4 with the 8 ball. Otherwise, we look for the first ball that is out of position (i.e. a Stripe where a Solid belongs). Then we look for an opposing ball to swap with that.

Finally, the SearchNode class provides a compareTo() method. The algorithm uses a priority queue to examine the SearchNode with the lowest priority. The compareTo() method allows SearchNodes to be sorted.

The heart of the algorithm is in the while loop of the rackMoves() method. It's based on the A* algorithm. We start by placing the initial state into the priority queue. Then we remove the lowest priority state from the queue and add two new states representing steps toward one of the two legal end states.

Once we've found a state that is legal, we update minNumberOfMoves. Any state that cannot reach the end state in less moves will not be added to the priority queue, and that line of progression will terminate.

Once the queue is empty, we'll have found our minimum possible number of moves.

This solution is probably overkill given the problem. With only 15 balls, and noting that each swap (not including the 8 ball) brings two more balls into alignment, it shouldn't be hard to write a brute-force approach. I like this solution becase it is more general. It can be expanded to take any starting condition and find the best sequence to get to any ending state. The same algorithm can be used to solve a rubik's cude, those sliding tile games, or a host of other problems.

Sunday, January 25, 2015

CalendarRecycle

Problem:

TopCoder Problem Statement - CalendarRecycle
Single Round Match 163 Round 1 - Division II, Level Two

Overview:

Determine the next year that shares a calendar with the given year. That is, all dates fall on the same day of the week.

Java Source:
01: import java.util.Calendar;
02: import java.util.GregorianCalendar;
03: 
04: public class CalendarRecycle {
05: 
06:  public int useAgain(int year) {
07: 
08:   boolean firstYearIsLeap = isLeapYear(year);
09: 
10:   int dayOfWeek = 0;
11: 
12:   while(true)  {
13: 
14:    // Determine which day the next year starts on.
15:    dayOfWeek += 365;
16:    if (isLeapYear(year)) dayOfWeek++;
17:    dayOfWeek %= 7;
18: 
19:    year++;
20: 
21:    /*
22:    * If the next year starts on the same day of the week, and they
23:    * have the same leap year status, then return.
24:    */
25:    if ((dayOfWeek == 0) && (firstYearIsLeap == isLeapYear(year)))  {
26:     return year;
27:    }
28:   }
29: 
30:  }
31: 
32:  private static boolean isLeapYear(int year)  {
33: 
34:   // If the year is divisible by 4
35:   if ((year % 4) == 0)  {
36: 
37:    // And not divisible by 100, unless also divisible by 400
38:    if ((year % 100 != 0) || ((year % 400) == 0))  {
39:     return true;
40:    }
41:   }
42: 
43:   return false;
44:  }
45: 
46: 
47: 
48:  /*
49:  * An alternate solution using Java's GregorianCalendar.
50:  */
51:  public int useAgain2(int year)  {
52: 
53:   GregorianCalendar c = new GregorianCalendar(year, Calendar.JANUARY, 1);
54:   int initialDayOfWeek = c.get(Calendar.DAY_OF_WEEK);
55: 
56:   while (true)  {
57:    c.add(Calendar.YEAR, 1);
58:    if ((c.get(Calendar.DAY_OF_WEEK) == initialDayOfWeek) &&
59:      (c.isLeapYear(c.get(Calendar.YEAR)) == c.isLeapYear(year))) {
60:     return c.get(Calendar.YEAR);
61:    }
62:   }
63:  }
64: }
Notes:

We say that two calendars are the same if the meet the following conditions:

  1. Any date falls on the same day of the week. (i.e. Jan 1 is a Sunday for both years). and
  2. Both years have the same leap year status. Either both are, or both aren't leap years.

The first thing useAgain() does is store the leap year status of the current year. We'll need this later to check that it matches the status of the candidate year.

Next, we set dayOfWeek to it's initial value. Note that we don't care what day this represents. It could be Sunday, Monday, etc. The only thing that matters is that we return to this value.

Finally, it's just a matter of adding 365 (+1 if it's a leap year), mod'ing that by 7 and seeing if we're back to the starting day. If so, and the leap year status matches, we've found our answer.

The logic for isLeapYear() is taken directly from the problem description. First check to see if the year is divisible by 4. If so, then check to see if it's not divisible by 100, unless it is also divisible by 400.

I've provided an alternate solution in useAgain1() that makes use of Java's GregorianCalendar.

Here, we create a new GregorianCalenar for January 1st of the given year (any date could have been chosen), and remember its day of the week. Then we keep adding a year and checking the day of the week and leap year status just as before.

An interesting note about GregorianCalendar - it provides an instance method isLeapYear(int year). A better way would be to create a static method GregorianCalendar.isLeapYear(int year) that could give the result for any year; and also provide an instnace method isLeapYear() with no parameters that gives the status of the current object. With the chosen implementation, you must create an instance of the GregorianCalendar to get the leap year status of some year that may be unrelated to that object. The second half of useAgain2()'s if statement could be much cleaner as:

GregorianCalendar.isLeapYear(year) == c.isLeapYear()

Wednesday, January 21, 2015

Inchworm

Problem:

TopCoder Problem Statement - Inchworm
Single Round Match 163 Round 1 - Division II, Level One

Overview:

Count the number of leaves an inchworm will stop at and eat before making it's way to the end of a branch.

Java Source:
01: public class Inchworm {
02: 
03:     public int lunchtime(int branch, int rest, int leaf) {
04: 
05:         int meals = 0;
06: 
07:         for (int p = 0; p <= branch; p += rest) {
08:             if ((p % leaf) == 0) meals++;
09:         }
10: 
11:         return meals;
12:     }
13: }
Notes:

This is a simple problem that can be solved in less time that it takes to read the description.

We'll use the variable p to keep track of the inchworm's current position. This starts at zero, and get incremented by rest until the inchworm goes beyond the end of the branch.

At each position, we'll check to see if there's a leaf there, and if so, increment the number of meals eaten. We can tell if there is a leaf at the current position by using the % operator. If position is evenly divided by leaf, then we've stopped on a leaf.

Once p is greater than branch we can return the value in meals.

Wednesday, January 14, 2015

Target

Problem:

TopCoder Problem Statement - Target
Single Round Match 633 Round 1 - Division II, Level One

Overview:

Draw a series of concentric squares.

Java Source:
01: public class Target {
02: 
03:     private static final char OFF = ' ';
04:     private static final char ON = '#';
05: 
06:     public String[] draw(int n) {
07: 
08:         // Create a char[][] and initialize it.
09:         char[][] target = new char[n][n];
10: 
11:         for (int y = 0; y < n; y++) {
12:             for (int x = 0; x < n; x++) {
13:                 target[y][x] = OFF;
14:             }
15:         }
16: 
17:         // Start the recursive calls.
18:         drawSquare(target, 0);
19: 
20:         // Convert the char[][] into a String[] and return it.
21:         String[] result = new String[n];
22: 
23:         for (int y = 0; y < n; y++) {
24:             result[y] = new String(target[y]);
25:         }
26: 
27:         return result;
28:     }
29: 
30:     private void drawSquare(char[][] target, int topOrLeft) {
31: 
32:         int bottomOrRight = target.length - topOrLeft - 1;
33: 
34:         if (topOrLeft < bottomOrRight) {
35:             drawSquare(target, topOrLeft + 2);
36:         }
37: 
38:         for (int i = topOrLeft; i <= bottomOrRight; i++) {
39:             target[topOrLeft][i] = ON;      // Top Row
40:             target[bottomOrRight][i] = ON;  // Bottom Row
41:             target[i][topOrLeft] = ON;      // Left Edge
42:             target[i][bottomOrRight] = ON;  // Right Edge
43:         }
44: 
45:     }
46: }
Notes:

The solution uses recursion to draw all of the inner squares, and then completes the outer square. The draw() method simply initializes a new 2-dimensional char array and then calls drawSquare(). When drawSquare() completes, it just converstion the char[][] back to a String[] and returns it. The call to drawSquare() passes the char[][] and the index 0, which indicates the top-left corner of the outermost square.

The drawSquare() method handles all the work on turning on the appropriate locations. It is passed the top-left corner of the current square, and uses that and the size of the char[][] to determine the location of the bottom-right corner. If these values are not the same, recursively call drawSquare moving the top-left corner in and down by 2.

As the recursion unwinds, we have a loop to draw each of the sides. Note the index representing the top edge will always equal the index of the left edge. So one variable (topOrLeft) will suffice. Similarly, the index for the bottom edge will be the same as the index of the right edge - thus bottomOrRight.

Tuesday, January 13, 2015

SmartElevator

Problem:

TopCoder Problem Statement - SmartElevator
Single Round Match 156 Round 1 - Division I, Level Two

Overview:

An elevator must pick up and drop off a number of people. Determine the earliest this can be completed.

Java Source:
01: import java.util.HashSet;
02: import java.util.Set;
03: 
04: public class SmartElevator {
05: 
06:     private int minFinishTime = Integer.MAX_VALUE;
07: 
08:     private int[] startingFloors;
09:     private int[] destinationFloors;
10:     private int[] arrivalTimes;
11: 
12:     public int timeWaiting(int[] arrivalTime, int[] startingFloor,
13:                            int[] destinationFloor) {
14: 
15:         // Make these accessible to other methods.
16:         this.startingFloors = startingFloor;
17:         this.destinationFloors = destinationFloor;
18:         this.arrivalTimes = arrivalTime;
19: 
20:         /*
21:         * Initialize the simulation.  Creates Sets representing people
22:         * waiting for the elevator (regardless of their arrival time) and
23:         * people currently on the elevator.
24:         */
25:         Set waiting = new HashSet<>();
26: 
27:         // Add everyone to the waiting Set.
28:         for (int i = 0; i < arrivalTime.length; i++) {
29:             waiting.add(i);
30:         }
31: 
32:         Set elevator = new HashSet<>();
33:         int floor = 1;
34:         int time = 0;
35: 
36:         moveElevator(waiting, elevator, floor, time);
37: 
38:         return minFinishTime;
39:     }
40: 
41:     private void moveElevator(Set waiting, Set elevator,
42:                               int floor, int time) {
43: 
44:         /*
45:         * If there is nobody waiting, and nobody in the elevator, then we're
46:         * done.  If time is smaller than anything previously seen, set it
47:         * to our time.
48:         */
49:         if (waiting.isEmpty() && elevator.isEmpty()) {
50:             minFinishTime = Math.min(minFinishTime, time);
51:         }
52: 
53:         /*
54:         * Picking up people.
55:         * Recursively call moveElevator().  We'll move one person in turn
56:         * from the waiting Set to the elevator set.
57:         */
58:         for (int i : waiting) {
59:             Set newWaiting = new HashSet<>(waiting);
60:             newWaiting.remove(i);
61: 
62:             Set newElevator = new HashSet<>(elevator);
63:             newElevator.add(i);
64: 
65:             int newFloor = startingFloors[i];
66:             int travelTime = Math.abs(floor - newFloor);
67: 
68:             // Max of when elevator gets there, and when person arrives.
69:             int newTime = Math.max((time + travelTime), arrivalTimes[i]);
70: 
71:             moveElevator(newWaiting, newElevator, newFloor, newTime);
72:         }
73: 
74:         /*
75:         * Dropping off people.
76:         * Recursively call moveElevator() removing one person from the
77:         * elevator Set.
78:         */
79:         for (int i : elevator) {
80:             Set newElevator = new HashSet<>(elevator);
81:             newElevator.remove(i);
82: 
83:             int newFloor = destinationFloors[i];
84:             int travelTime = Math.abs(floor - newFloor);
85:             int newTime = time + travelTime;
86: 
87:             moveElevator(waiting, newElevator, newFloor, newTime);
88:         }
89: 
90:     }
91: }
Notes:

The current state can be described fully with the following variables:

  • A set of passengers waiting to be picked up.
  • A set of passengers currently in the elevator.
  • The floor the elevator is currently on.
  • How much time has elapsed.

At any point, the elevator can either move to pick someone up, or move to drop them off. This solution uses recursion to try every possible combination.

The timeWaiting() method just initializes the simulations with an empty elevator, everyone in the waiting Set, and the elevator on floor 1 at time 0.

In moveElevator() we first check to see if we're done - that is, the elevator is empty and nobody is waiting to be picked up. If that's the case, then we'll update minFinishTime to the smaller of it's current value and our current time.

If we're not done, then we'll recursively call moveElevator with every possible combination of picking up or dropping off a passenger.

To simulate picking up a passenger, we create a newWaiting set that contains all the members of the current waiting set, except for the person that we're picking up. We then create a newElevator set using the contents of the current elevator set and add the new passenger. The travel time is calculated between floors, and our newTime becomes the greater of the time when the elevator arrives, and the arrival time for that person. moveElevator() is then recursively callled with the new parameters.

Similarly, to drop someone off, we create a newElevator set that contains everyone from the current elevator set except the person that we dropped off. There is no need to create a newWaiting set, since that will not have changed. Again, the times are calculated moveElevator() gets called recursively.

When all of the scenarios have completed, minFinishTime will contain the shortest time in which all passengers can be serviced, so we just return that.

Thursday, January 8, 2015

QuipuReader

Problem:

TopCoder Problem Statement - QuipuReader
Single Round Match 155 Round 1 - Division I, Level Two

Overview:

Determine values represented by a series of ropes and knots.

Java Source:
01: public class QuipuReader {
02: 
03:  private int ropeLength = 0;
04: 
05:  // The method called by TopCoder.
06:  public int[] readKnots(String[] knots) {
07: 
08:   int[] values = new int[knots.length];
09: 
10:   ropeLength = knots[0].length();
11: 
12:   int clusterStart = findClusterStart(knots, 0);
13: 
14:   while (clusterStart < ropeLength)  {
15: 
16:    int clusterEnd = findClusterEnd(knots, clusterStart);
17: 
18:    /*
19:    * We've found the start and end indexes for the current cluster.
20:    * Now count the number of knots that fall in that range for
21:    * each rope.
22:    */
23:    for (int q = 0; q < knots.length; q++)  {
24:     values[q] *= 10;
25:     values[q] += doCount(knots[q], clusterStart, clusterEnd);
26:    }
27: 
28:    clusterStart = findClusterStart(knots, clusterEnd);
29:   }
30: 
31:   return values;
32:  }
33: 
34:  /*
35:  * Returns the index of the next cluster which starts at or beyond p.
36:  * This will be the location of the first 'X' found among all ropes.
37:  */
38:  private int findClusterStart(String[] knots, int p)  {
39: 
40:   if (p >= ropeLength)  return ropeLength;
41: 
42:   int minStart = ropeLength;
43: 
44:   for (int q = 0; q < knots.length; q++)  {
45:    int i = p;
46: 
47:    while ((i < ropeLength) && knots[q].charAt(i) != 'X')  {
48:     i++;
49:    }
50: 
51:    // Note the earliest start position found.
52:    minStart = Math.min(minStart, i);
53:   }
54: 
55:   return minStart;
56:  }
57: 
58:  /*
59:  * Returns the index where the cluster starting at p ends.
60:  * This will be the position after the last 'X' of the longest continuous
61:  * string of 'X's starting at p among all the ropes.
62:  */
63:  private int findClusterEnd(String[] knots, int p)  {
64: 
65:   int maxEnd = p;
66: 
67:   for (int q = 0; q < knots.length; q++)  {
68:    int i = p;
69:    while ((i < ropeLength) && (knots[q].charAt(i) == 'X'))  {
70:     i++;
71:    }
72: 
73:    // Note the greatest ending position found.
74:    maxEnd = Math.max(maxEnd, i);
75:   }
76: 
77:   return maxEnd;
78:  }
79: 
80:  /*
81:  * Counts the number of knots located between clusterStart and clusterEnd
82:  * on the given rope.
83:  */
84:  private int doCount(String rope, int start, int end)  {
85: 
86:   int n = 0;
87: 
88:   for (int p = start; p < end; p++)  {
89:    if (rope.charAt(p) == 'X')  {
90:     n++;
91:    }
92:   }
93: 
94:   return n;
95:  }
96: }
Notes:

The tricky part of this problem is determining where each cluster starts and ends. I've created the methods findClusterStart() and findClusterEnd() to take care of that. With those indexes known, we simply count the number of knots between those points. The knots are read from left to right, and for each cluster, the current value is multiplied by 10, and the number of knots in the current cluster is added.

findClusterStart() returns the index of the first 'X' found at or after p among any of the knots given in the input array. The return value will be at most ropeLength.

findClusterEnd() is very similar to findClusterStart(). Here we're looking for the greatest index. It starts at position p, and increments the index so long as the current character is an 'X'. This is done for each knot in the knots array, and the greatest index is returned.

doCount() just returns the number of 'X's found in a string between the start and end indexes.

Saturday, January 3, 2015

QuiningTopCoder

Problem:

TopCoder Problem Statement - QuiningTopCoder
Single Round Match 152 Round 1 - Division I, Level Two

Overview:

Implement a small programming language, and determine if a program written in this language outputs itself.

Java Source:
001: import java.util.Stack;
002: 
003: public class QuiningTopCoder {
004: 
005:     private static final int MAX_CYCLES = 80000;
006:     private static final int MIN_STACK_VAL = -1000000000;
007:     private static final int MAX_STACK_VAL = 1000000000;
008: 
009:     /*
010:     * A custom version of the standard Stack.  This will return 0 if the user
011:     * attempts to pop a an empty stack (default behavior is to throw an
012:     * EmptyStackException).  Also checks the value being pushed to ensure
013:     * it is between MIN_STACK_VAL and MAX_STACK_VAL.  If not, it throws
014:     * an illegalArgumentException.
015:     */
016:     private class MyStack extends Stack {
017: 
018:         public Integer pop() {
019:             return (isEmpty()) ? 0 : super.pop();
020:         }
021: 
022:         public Integer push(Integer i) throws IllegalArgumentException {
023: 
024:             if ((i < MIN_STACK_VAL) || (i > MAX_STACK_VAL)) {
025:                 throw new IllegalArgumentException();
026:             }
027:             return super.push(i);
028:         }
029:     }
030: 
031: 
032:     // The function for updating the instruction pointer.
033:     private static int incIp(int n, int ip, int d) {
034:         return ((3 * n) + ip + d) % n;
035:     }
036: 
037:     // Method called by TopCoder.
038:     public String testCode(String source) {
039: 
040:         int ip = 0;
041:         int d = 1;
042:         int cycles = 0;
043:         int n = source.length();
044: 
045:         Stack stack = new MyStack();
046: 
047:         StringBuilder output = new StringBuilder();
048: 
049:         try {
050: 
051:             while (cycles <= MAX_CYCLES) {
052: 
053:                 char instruction = source.charAt(ip);
054: 
055:                 /*
056:                  * '0'-'9': pushes the number represented by that digit onto
057:                  * the stack.
058:                  */
059:                 if ((instruction >= '0') && (instruction <= '9')) {
060:                     stack.push(instruction - '0');
061:                     ip = incIp(n, ip, d);
062: 
063:                 } else {
064: 
065:                     int x, y;
066: 
067:                     switch (instruction) {
068: 
069:                         // '$' : pops a value off the stack, and discards it.
070:                         case '$':
071:                             stack.pop();
072:                             ip = incIp(n, ip, d);
073:                             break;
074: 
075:                         /*
076:                         * ':' : pops a value off the stack, then pushes that
077:                         * same value onto the stack twice.
078:                         */
079:                         case ':':
080:                             x = stack.pop();
081:                             stack.push(x);
082:                             stack.push(x);
083:                             ip = incIp(n, ip, d);
084:                             break;
085: 
086:                         /*
087:                         * 'W' : Pops a value A, then pops a value B, then
088:                         * pushes A, then pushes B.
089:                         */
090:                         case 'W':
091:                             x = stack.pop();
092:                             y = stack.pop();
093:                             stack.push(x);
094:                             stack.push(y);
095:                             ip = incIp(n, ip, d);
096:                             break;
097: 
098:                         /*
099:                         * ',' : pops a value X off of the stack, and prints the
100:                         * (absolute value of X)%Nth character in the source
101:                         * code.
102:                         */
103:                         case ',':
104:                             x = stack.pop();
105:                             x = Math.abs(x) % n;
106:                             output.append(source.charAt(x));
107: 
108:                             /*
109:                             * Whenever the output changes, check to see
110:                             * if we're done, or at least still on track.
111:                             * */
112:                             if (output.toString().equals(source)) {
113:                                 return "QUINES " + cycles;
114:                             }
115:                             if (!source.startsWith(output.toString())) {
116:                                 return "MISMATCH " + cycles;
117:                             }
118: 
119:                             ip = incIp(n, ip, d);
120:                             break;
121: 
122:                         /*
123:                         * '+' : pops two values, adds them, and pushes the
124:                         * result back onto the stack.
125:                         */
126:                         case '+':
127:                             x = stack.pop();
128:                             y = stack.pop();
129:                             stack.push(x + y);
130:                             ip = incIp(n, ip, d);
131:                             break;
132: 
133:                         /*
134:                         * '-' : pops two values, subtracts the second popped
135:                         * value from the first, and pushes the result back onto
136:                         * the stack.
137:                         */
138:                         case '-':
139:                             x = stack.pop();
140:                             y = stack.pop();
141:                             stack.push(x - y);
142:                             ip = incIp(n, ip, d);
143:                             break;
144: 
145:                         // '#' : multiplies D by 2 for this cycle only.
146:                         case '#':
147:                             ip = incIp(n, ip, (2 * d));
148:                             break;
149: 
150:                         // 'R' : multiplies D by -1.
151:                         case 'R':
152:                             d *= -1;
153:                             ip = incIp(n, ip, d);
154:                             break;
155: 
156:                         /*
157:                         * 'S' : pops a value, and if positive pushes a 1, else
158:                         * pushes a -1.
159:                         */
160:                         case 'S':
161:                             x = stack.pop();
162: 
163:                             // 0 is treated at not positive.
164:                             if (x > 0) {
165:                                 stack.push(1);
166:                             } else {
167:                                 stack.push(-1);
168:                             }
169: 
170:                             ip = incIp(n, ip, d);
171:                             break;
172: 
173:                         // '_' : pops a value X, and sets D to that value X%N.
174:                         case '_':
175:                             x = stack.pop();
176:                             d = x % n;
177:                             ip = incIp(n, ip, d);
178:                             break;
179: 
180:                         /*
181:                         * 'J' : pops a value X, and sets IP to the (absolute
182:                         * value of X)%N. (IP is not incremented after this step)
183:                         */
184:                         case 'J':
185:                             x = stack.pop();
186:                             ip = Math.abs(x) % n;
187:                             break;
188: 
189:                         /*
190:                         * '@' : stops the program
191:                         * It must be a BADEND here, because if the output
192:                         * had matched the source, then we would have caught it
193:                         * in the ',' command.
194:                         */
195:                         case '@':
196:                             return "BADEND " + cycles;
197: 
198:                         // Should not reach this so long as the input is valid.
199:                         default:
200:                             return "ERROR bad command: " + instruction;
201: 
202:                     }
203:                 }
204:                 cycles++;
205:             }
206: 
207:             // Exceeded MAX_CYCLES
208:             return "TIMEOUT";
209: 
210:         } catch (IllegalArgumentException e) {
211: 
212:             // A value outside of MIN_STACK_VAL | MAX_STACK_VAL was pushed.
213:             return "OVERFLOW " + cycles;
214:         }
215:     }
216: }
Notes:

This is a pretty straight forward problem. Just follow the instructions carefully, and you shouldn't run into any problems.

To implement the stack, I chose to extend java.util.Stack and override the pop() and push() methods. Although the problem doesn't explicitly state it, you can see from the first example that if pop() is called on an empty stack, it should return 0. The default behavior of java.util.Stack is to throw an EmptyStackException. I also modified push() to check that the value is between MIN_STACK_VAL (-1000000000) and MAX_STACK_VAL (1000000000) before pushing it. If the value is outside these bounds, it will throw an IllegalArgumentException.

When the ',' command is encountered, a value is popped from the stack and appended to output. This is the only time that output is modified. Whenever output changes, we check to see if it now equals source, or failing that, ensure source continues to begin with output.

Since output is only changed by the ',' command, if '@' is ever encountered, we return BADEND. At that point output cannot match the program since we would have caught it when processing the ',' command.

The while loop watches the value of cycles (which gets incremented after each command is processed), and terminates when it reaches MAX_CYCLES.

The only other exit point is when we catch an IllegalArgumentException from pushing a value outside the legal range onto the stack. This exception is caught and returns an OVERFLOW message.

The rest of the program simply implements the logic given in the problem statement. Again, be careful and you won't have any problems.

Friday, January 2, 2015

HappyLetterDiv2

Problem:

TopCoder Problem Statement - HappyLetterDiv2
Single Round Match 627 Round 1 - Division II, Level Two

Overview:

Eliminate non-matching letters until one remains. Determine what letters can possibly be left.

Java Source:
01: public class HappyLetterDiv2 {
02: 
03:     public char getHappyLetter(String letters) {
04: 
05:         // Loop through all letters in the input string.
06:         for (int i = 0; i < letters.length(); i++) {
07: 
08:             char currentChar = letters.charAt(i);
09: 
10:             // Count the characters that match the current char.
11:             int matchingChars = 0;
12: 
13:             for (int j = 0; j < letters.length(); j++) {
14:                 if (letters.charAt(j) == currentChar) {
15:                     matchingChars++;
16:                 }
17:             }
18: 
19:             /*
20:             * If the number of matching characters is greater than half the
21:             * length of the input string, then we have a happy letter.
22:             */
23:             if (matchingChars > (letters.length() / 2)) {
24:                 return currentChar;
25:             }
26: 
27:         }
28: 
29:         return '.';
30: 
31:     }
32: }
Notes:

In order to be a happy letter, more than half the letters in the string must be that character. If the frequency of a character is half (or less) the length of the input string, then other characters can be paired up with the current character until all instances of the current character are eliminated. Conversely, if the frequency is greater than half, then matching all other characters with the current character will be insufficient to eliminate all of the current character.

The solution then is just to loop through all the characters in the input string. For each letter, count the number of times it appears, and if that's greater than half the size of the input string, return it as the happy letter. If no character meets that criteria, return '.'

Note that only one character can be a happy letter, because more than half the input string must consist of that character. It's impossible for more than one character to take up more than half the string.