Solutions


Below are all the solutions for the coding competition!

Java Solutions


package solution;

import java.util.Collections;
import java.util.ArrayList;

public class Solution {

    // REQUIRES: int numRows
    // MODIFIES: N/A
    // EFFECTS:  Returns a ArrayList of ArrayLists of Pascal's triangle
    //           e.g. where numRows = 4
    //           [
    //		    [1],
    //		    [1, 1],
    //		    [1, 2, 1],
    //		    [1, 3, 3, 1]
    //		 ]
    public static ArrayList<ArrayList<Integer>> genPascalTriangleSol(int numRows) {
        // increment elts in each col by 2 when inner col ArrayList exceeds capacity
        ArrayList<ArrayList<Integer>> r = new ArrayList<ArrayList<Integer>>(numRows);
        for (int i = 0; i < numRows; ++i) {
            // create a new inner col ArrayList with capacity i + 1, add it for each row
            r.add(i, new ArrayList<Integer>(i + 1));
            // set size of inner ArrayList as i + 1
            for (int k = 0; k < i + 1; ++k) {
                r.get(i).add(0);
            }
            r.get(i).set(0, 1);
            r.get(i).set(i, 1);
            for (int j = 1; j < i; j++) {
                r.get(i).set(j, r.get(i - 1).get(j - 1) + r.get(i - 1).get(j));
            }
        }
        return r;
    }

    // REQUIRES: ArrayList<int> tasks
    // EFFECTS:  Returns the missing int where ArrayList<int> is size
    //           N containing the integers 1 to N except a missing one
    //           e.g. task = [ 4, 1, 2 ] returns 3
    public static int missingTaskSol(ArrayList<Integer> tasks) {
        if (tasks.isEmpty()) {
            return 1;
        }
        Collections.sort(tasks);
        int i = 0;
        for (; i < tasks.size(); ++i)
            if (tasks.get(i) != i + 1)
                break;
        return i + 1;
    }

    // REQUIRES: string romanNumerals
    // EFFECTS:  Returns the integer equivalent of the roman numerals
    //           e.g. romanNumerals = "MDCCXLII" returns 1742
    public static int romanTranslationSol(String romanNumerals) {
	if (romanNumerals.length() == 0) return 0;
        else if (romanNumerals.equals("I"))
            return 1;
        else if (romanNumerals.equals("V"))
            return 5;
        else if (romanNumerals.equals("X"))
            return 10;
        else if (romanNumerals.equals("L"))
            return 50;
        else if (romanNumerals.equals("C"))
            return 100;
        else if (romanNumerals.equals("D"))
            return 500;
        else if (romanNumerals.equals("M"))
            return 1000;

        int curr_idx = 0;
        int curr_dist = 0;
        String ref_arr = "IVXLCDM";
        for (int i = 0; i < romanNumerals.length(); ++i){
            // get index of this alphabet wrt to ref_arr = distance from 0 to this index
            int loop_dist = ref_arr.indexOf(romanNumerals.charAt(i));
            if (loop_dist > curr_dist) {
                curr_idx = i;
                curr_dist = loop_dist;
            }
        }
        int num = romanTranslationSol(
                romanNumerals.substring(curr_idx, curr_idx + 1));
        int left = romanTranslationSol(
                romanNumerals.substring(0, curr_idx));
        int right = romanTranslationSol(
                romanNumerals.substring(curr_idx + 1));
        return  num + right - left;
    }

    // REQUIRES: string militaryTime
    // EFFECTS:  Returns the corresponding military time from the
    //           given standard time (both represented as strings)
    //           in the format: "HR:MI:SE[AM/PM]" where the AM/PM
    //           is omitted for the returned military time.
    //           e.g. standardTime = "07:05:45PM" returns "19:05:45"
    public static String timeConversionSol(String standardTime) {
        if (standardTime.substring(0, 2).equals("12")) {
            if (standardTime.substring(8).equals("AM")) {
                return "00".concat(standardTime.substring(2, 8));
            } else {
                return "12".concat(standardTime.substring(2, 8));
            }
        }
        if (standardTime.substring(8).equals("AM")) return standardTime.substring(0, 8);
        int curr_hours = Integer.parseInt(standardTime.substring(0, 2)) + 12;
        return Integer.toString(curr_hours).concat(standardTime.substring(2, 8));
    }

    // REQUIRES: ArrayList<int> games
    // EFFECTS:  Returns the number of times that the least points
    //           record is broken assuming the initial record is set
    //           by the first element of ArrayList<int> games
    //           e.g. games = [ 6, 4, 5, 4, 3 ] returns 2
    public static int breakingWorstSol(ArrayList<Integer> games) {
        if (games.isEmpty()) return 0;
        int count = 0;
        int worst = games.get(0);
        for (int game: games) {
            if (game < worst) {
                ++count;
                worst = game;
            }
        }
        return count;
    }

    // REQUIRES: ArrayList<int> games
    // EFFECTS:  Returns the number of times that the most points
    //           record is broken assuming the initial record is set
    //           by the first element of ArrayList<int> games
    //           e.g. games = [ 2, 1, 2, 3, 2, 5 ] returns 2
    public static int breakingBestSol(ArrayList<Integer> games) {
        if (games.isEmpty()) return 0;
        int count = 0;
        int best = games.get(0);
        for (int game: games) {
            if (game > best) {
                ++count;
                best = game;
            }
        }
        return count;
    }

    // REQUIRES: ArrayList<int> houses
    // EFFECTS:  Given the house robber game described in the packet,
    //           returns the most optimal amount the player can rob
    //           e.g. houses = [ 2, 10, 3, 3, 30 ] returns 40
    public static int houseRobberSol(ArrayList<Integer> houses) {
        if (houses.isEmpty()) return 0;
        int val1 = houses.get(0);
        if (houses.size() == 1) return val1;
        int val2 = Math.max(houses.get(0), houses.get(1));
        if (houses.size() == 2) return val2;
        int maxval = 0;
        for (int i = 2; i < houses.size(); ++i) {
            maxval = Math.max(houses.get(i) + val1, val2);
            val1 = val2;
            val2 = maxval;
        }
        return maxval;
    }

    // REQUIRES: string ransomNote (letters in ransom note)
    //           string magazine   (letters in the magazine)
    // EFFECTS:  Returns whether the the following ransom note
    //           characters can be formed by the magazine charcters
    //           e.g. ransomNote="a" and magazine="b" returns false
    //           e.g. ransomNote="aa" and magazine="ab" returns false
    //           e.g. ransomNote="aa" and magazine="aab" returns true
    public static boolean ransomNoteSol(String ransomNote, String magazine) {
        for (int i = 0; i < ransomNote.length(); ++i) {
            char c = ransomNote.charAt(i);
            boolean exists = false;
            for (int j = 0; j < magazine.length(); ++j) {
                if (c == magazine.charAt(j)) {
                    exists = true;
                    magazine = magazine.substring(0, j).concat(magazine.substring(j + 1));
                    break;
                }
            }
            if (!exists) return false;
        }
        return true;
    }
}

						

package solution;

import java.util.Scanner;

public class TicTacToeSol {
    char square[] = { 'o','1','2','3','4','5','6','7','8','9' };
    Scanner scanner = new Scanner(System.in);

    public void run() throws Exception {
	int player = 1, i, choice;

	char mark;
	do {
	    board();
	    player = (player % 2) == 1 ? 1 : 2;

	    System.out.println("Player " + player + ", enter a number: ");
	    choice = scanner.nextInt();

	    mark = (player == 1) ? 'X' : 'O';

	    if (choice == 1 && square[1] == '1')
	        square[1] = mark;
	    else if (choice == 2 && square[2] == '2')
	        square[2] = mark;
	    else if (choice == 3 && square[3] == '3')
	        square[3] = mark;
	    else if (choice == 4 && square[4] == '4')
	        square[4] = mark;
	    else if (choice == 5 && square[5] == '5')
	        square[5] = mark;
	    else if (choice == 6 && square[6] == '6')
	        square[6] = mark;
	    else if (choice == 7 && square[7] == '7')
	        square[7] = mark;
	    else if (choice == 8 && square[8] == '8')
	        square[8] = mark;
	    else if (choice == 9 && square[9] == '9')
	        square[9] = mark;
	    else {
	        System.out.println("Invalid move");
	        player--;
	        scanner.nextLine();
	    }

	    i = checkwin(square);
	    player++;
	} while(i == -1);

	board();
	if(i == 1)
	    System.out.print("==>\0007Player " + --player + " win ");
	else
	    System.out.print("==>\0007Game draw");

	scanner.nextLine();
    }

    /*********************************************
     * FUNCTION TO RETURN GAME STATUS
     * 1 FOR GAME IS OVER WITH RESULT
     * -1 FOR GAME IS IN PROGRESS
     *  O GAME IS OVER AND NO RESULT
     ***********************************************/

    public static int checkwin(char board[]) throws Exception {
	if (board[1] == board[2] && board[2] == board[3])
	    return 1;
	else if (board[4] == board[5] && board[5] == board[6])
	    return 1;
	else if (board[7] == board[8] && board[8] == board[9])
	    return 1;
	else if (board[1] == board[4] && board[4] == board[7])
	    return 1;
	else if (board[2] == board[5] && board[5] == board[8])
	    return 1;
	else if (board[3] == board[6] && board[6] == board[9])
	    return 1;
	else if (board[1] == board[5] && board[5] == board[9])
	    return 1;
	else if (board[3] == board[5] && board[5] == board[7])
	    return 1;
	else if (board[1] != '1' && board[2] != '2' && board[3] != '3'
                && board[4] != '4' && board[5] != '5' && board[6] != '6'
	             && board[7] != '7' && board[8] != '8' && board[9] != '9')
	    return 0;
	else
	    return -1;
    }


    /*******************************************************************
     * FUNCTION TO DRAW BOARD OF TIC TAC TOE WITH PLAYERS MARK
     *********************************************************************/


    public void board() {
	System.out.print("\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n");
	System.out.print("\n\n\tTic Tac Toe\n\n");

	System.out.println("Player 1 (X)  -  Player 2 (O)\n\n");

	System.out.println("     |     |     ");
	System.out.println("  " + square[1] + "  |  " + square[2]
                + "  |  " + square[3]);

	System.out.println("_____|_____|_____");
	System.out.println("     |     |     ");

	System.out.println("  " + square[4] + "  |  " + square[5]
                + "  |  " + square[6]);

	System.out.println("_____|_____|_____");
	System.out.println("     |     |     ");

	System.out.println("  " + square[7] + "  |  " + square[8]
                + "  |  " + square[9]);

	System.out.println("     |     |     \n");
    }

    /**********************************************
     * GAME OVER
     ************************************************/
}
						

C++ Solutions


#include <algorithm>
#include "solution.h"

using namespace std;

const vector<char> order = { 'I', 'V', 'X', 'L', 'C', 'D', 'M' };

// REQUIRES: int numRows
// MODIFIES: N/A
// EFFECTS:  Returns a vector of vectors of Pascal's triangle
//           e.g. where numRows = 4
//           [
//				[1],
//			    [1, 1],
//				[1, 2, 1],
//				[1, 3, 3, 1]
//			 ]
vector<vector<int>> genPascalTriangleSol(int numRows) {
	vector<vector<int>> r((unsigned) numRows);
	for (int i = 0; i < numRows; ++i) {
		r[i].resize((unsigned) i + 1);
		r[i][0] = r[i][i] = 1;
		for (int j = 1; j < i; j++) {
			r[i][j] = r[i - 1][j - 1] + r[i - 1][j];
		}
	}
	return r;
}

// REQUIRES: vector<int> tasks
// EFFECTS:  Returns the missing int where vector<int> is size
//           N containing the integers 1 to N except a missing one
//           e.g. task = [ 4, 1, 2 ] returns 3
int missingTaskSol(vector<int> tasks) {
    if (tasks.empty())
        return 1;
    sort(tasks.begin(), tasks.end());
    int i = 0;
    for (; (unsigned) i < tasks.size(); ++i)
        if (tasks[i] != i + 1)
            break;
    return i + 1;
}

// REQUIRES: string romanNumerals
// EFFECTS:  Returns the integer equivalent of the roman numerals
//           e.g. romanNumerals = "MDCCXLII" returns 1742
int romanTranslationSol(string romanNumerals) {
    if (romanNumerals.empty())
        return 0;
    else if (romanNumerals == "I")
        return 1;
    else if (romanNumerals == "V")
        return 5;
    else if (romanNumerals == "X")
        return 10;
    else if (romanNumerals == "L")
        return 50;
    else if (romanNumerals == "C")
        return 100;
    else if (romanNumerals == "D")
        return 500;
    else if (romanNumerals == "M")
        return 1000;
    unsigned int curr_idx = 0;
    long curr_dist = 0;
    for (unsigned int i = 0; i < romanNumerals.size(); ++i) {
        long dist = distance(order.begin(), find(
                order.begin(), order.end(), romanNumerals[i]));
        if (dist > curr_dist) {
            curr_idx = i;
            curr_dist = dist;
        }
    }
    int num = romanTranslationSol(
            romanNumerals.substr(curr_idx, 1));
    int left = romanTranslationSol(
            romanNumerals.substr(0, curr_idx));
    int right = romanTranslationSol(
            romanNumerals.substr(curr_idx + 1,
                romanNumerals.size() - 1 - curr_idx));
    return num + right - left;
}

// REQUIRES: string militaryTime
// EFFECTS:  Returns the corresponding military time from the
//           given standard time (both represented as strings)
//           in the format: "HR:MI:SE[AM/PM]" where the AM/PM
//           is omitted for the returned military time.
//           e.g. standardTime = "07:05:45PM" returns "19:05:45"
string timeConversionSol(string standardTime) {
    if (standardTime.substr(0, 2) == "12")
        return ((standardTime.substr(8, 2) == "AM") ? "00" : "12")
            + standardTime.substr(2, 6);
    else if (standardTime.substr(8, 2) == "AM")
        return standardTime.substr(0, 8);
    int curr_hours = stoi(standardTime.substr(0, 2)) + 12;
    return to_string(curr_hours) + standardTime.substr(2, 6);
}

// REQUIRES: vector<int> games
// EFFECTS:  Returns the number of times that the least points
//           record is broken assuming the initial record is set
//           by the first element of vector<int> games
//           e.g. games = [ 6, 4, 5, 4, 3 ] returns 2
int breakingWorstSol(vector<int> games) {
    if (games.empty())
        return 0;
    int count = 0;
    int worst = games[0];
    for (int game : games) {
        if (game < worst) {
            ++count;
            worst = game;
        }
    }
    return count;
}

// REQUIRES: vector<int> games
// EFFECTS:  Returns the number of times that the most points
//           record is broken assuming the initial record is set
//           by the first element of vector<int> games
//           e.g. games = [ 2, 1, 2, 3, 2, 5 ] returns 2
int breakingBestSol(vector<int> games) {
    if (games.empty())
        return 0;
    int count = 0;
    int best = games[0];
    for (int game : games) {
        if (game > best) {
            ++count;
            best = game;
        }
    }
    return count;
}

// REQUIRES: vector<int> houses
// EFFECTS:  Given the house robber game described in the packet,
//           returns the most optimal amount the player can rob
//           e.g. houses = [ 2, 10, 3, 3, 30 ] returns 40
int houseRobberSol(vector<int> houses) {
    if (houses.empty())
        return 0;
    int val1 = houses[0];
    if (houses.size() == 1)
        return val1;
    int val2 = max(houses[0], houses[1]);
    if (houses.size() == 2)
        return val2;
    int maxval = 0;
    for (int i = 2; (unsigned) i < houses.size(); ++i) {
        maxval = max(houses[i] + val1, val2);
        val1 = val2;
        val2 = maxval;
    }
    return maxval;
}

// REQUIRES: string ransomNote (letters in ransom note)
//           string magazine   (letters in the magazine)
// EFFECTS:  Returns whether the the following ransom note
//           characters can be formed by the magazine charcters
//           e.g. ransomNote="a" and magazine="b" returns false
//           e.g. ransomNote="aa" and magazine="ab" returns false
//           e.g. ransomNote="aa" and magazine="aab" returns true
bool ransomNoteSol(string ransomNote, string magazine) {
    for (char c : ransomNote) {
        bool exists = false;
        for (unsigned int j = 0; j < magazine.length(); ++j) {
            if (c == magazine[j]) {
                exists = true;
                magazine = magazine.substr(0, j) + magazine.substr(
                        j + 1, magazine.size() - 1 - j);
                break;
            }
        }
        if (!exists)
            return false;
    }
    return true;
}
						

#include <iostream>
using namespace std;

char square[10] = { 'o','1','2','3','4','5','6','7','8','9' };

int checkwin(char *board);
void board();

void run() {
    int player = 1, i, choice;

    char mark;
    do {
        board();
        player = (player % 2) ? 1 : 2;

        cout << "Player " << player << ", enter a number:  ";
        cin >> choice;

        mark = (player == 1) ? 'X' : 'O';

        if (choice == 1 && square[1] == '1')
            square[1] = mark;
        else if (choice == 2 && square[2] == '2')
            square[2] = mark;
        else if (choice == 3 && square[3] == '3')
            square[3] = mark;
        else if (choice == 4 && square[4] == '4')
            square[4] = mark;
        else if (choice == 5 && square[5] == '5')
            square[5] = mark;
        else if (choice == 6 && square[6] == '6')
            square[6] = mark;
        else if (choice == 7 && square[7] == '7')
            square[7] = mark;
        else if (choice == 8 && square[8] == '8')
            square[8] = mark;
        else if (choice == 9 && square[9] == '9')
            square[9] = mark;
        else {
            cout << "Invalid move";
            player--;
            cin.ignore();
            cin.get();
        }

        i = checkwin(square);
        player++;
    } while(i == -1);

    board();
    if(i == 1)
        cout << "==>\aPlayer " << --player << " win ";
    else
        cout << "==>\aGame draw";

    cin.ignore();
    cin.get();
}

/*********************************************
	    FUNCTION TO RETURN GAME STATUS
	    1 FOR GAME IS OVER WITH RESULT
	    -1 FOR GAME IS IN PROGRESS
	    O GAME IS OVER AND NO RESULT
**********************************************/

int checkwin(char *board) {
    if (board[1] == board[2] && board[2] == board[3])
        return 1;
    else if (board[4] == board[5] && board[5] == board[6])
        return 1;
    else if (board[7] == board[8] && board[8] == board[9])
        return 1;
    else if (board[1] == board[4] && board[4] == board[7])
        return 1;
    else if (board[2] == board[5] && board[5] == board[8])
        return 1;
    else if (board[3] == board[6] && board[6] == board[9])
        return 1;
    else if (board[1] == board[5] && board[5] == board[9])
        return 1;
    else if (board[3] == board[5] && board[5] == board[7])
        return 1;
    else if (board[1] != '1' && board[2] != '2' && board[3] != '3'
             && board[4] != '4' && board[5] != '5' && board[6] != '6'
             && board[7] != '7' && board[8] != '8' && board[9] != '9')
        return 0;
    else
        return -1;
}


/*******************************************************************
     FUNCTION TO DRAW BOARD OF TIC TAC TOE WITH PLAYERS MARK
********************************************************************/


void board() {
    cout << "\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n";
    cout << "\n\n\tTic Tac Toe\n\n";

    cout << "Player 1 (X)  -  Player 2 (O)" << endl << endl;
    cout << endl;

    cout << "     |     |     " << endl;
    cout << "  " << square[1] << "  |  " << square[2]
         << "  |  " << square[3] << endl;

    cout << "_____|_____|_____" << endl;
    cout << "     |     |     " << endl;

    cout << "  " << square[4] << "  |  " << square[5]
         << "  |  " << square[6] << endl;

    cout << "_____|_____|_____" << endl;
    cout << "     |     |     " << endl;

    cout << "  " << square[7] << "  |  " << square[8]
         << "  |  " << square[9] << endl;

    cout << "     |     |     " << endl << endl;
}

/**********************************************
				  GAME OVER
***********************************************/