Category Archives: UVA Online Judge

UVA 10196 – Check The Check

This was a fun problem. This is a really good example of a problem where functions make your code extremely easy to read and write. I did a bit of trickery so that I could use the same functions for both white and black kings.

import java.awt.Point;
import java.io.PrintWriter;
import java.util.Scanner;

/**
 * 
 * @author Sanchit M. Bhatnagar
 * @see http://uhunt.felix-halim.net/id/74004
 * 
 */
public class P10196 {

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    PrintWriter out = new PrintWriter(System.out);

    int count = 1;
    while (sc.hasNext()) {
      char[][] grid = new char[8][8];
      Point blackKing = null;
      Point whiteKing = null;
      for (int i = 0; i < 8; i++) {
        char[] tmp = sc.next().trim().toCharArray();
        for (int j = 0; j < 8; j++) {
          grid[i][j] = tmp[j];
          if (tmp[j] == 'k') {
            blackKing = new Point(i, j);
          } else if (tmp[j] == 'K') {
            whiteKing = new Point(i, j);
          }
        }
      }
      if (blackKing == null || whiteKing == null)
        break;
      if (inCheck(blackKing, grid)) {
        out.println("Game #" + count + ": black king is in check.");
      } else if (inCheck(whiteKing, grid)) {
        out.println("Game #" + count + ": white king is in check.");
      } else {
        out.println("Game #" + count + ": no king is in check.");
      }
      count++;
    }

    out.close();
    sc.close();
  }

  private static boolean inCheck(Point king, char[][] grid) {
    // Death by queen has been incorporated into deathByRook and deathByBishop
    if (deathByPawn(king, grid) || deathByKnight(king, grid) || deathByRook(king, grid) || deathByBishop(king, grid))
      return true;
    return false;
  }

  private static boolean deathByBishop(Point king, char[][] grid) {
    int i = king.x;
    int j = king.y;
    char thing = '\u000F';
    char thing2 = '\u000F';
    if (Character.isLowerCase(grid[i][j])) {
      // Black King
      thing = 'B';
      thing2 = 'Q';
    } else {
      // White King
      thing = 'b';
      thing2 = 'q';
    }

    // NW
    int idx = i - 1;
    int idx2 = j - 1;
    while (idx >= 0 && idx < 8 && idx2 >= 0 && idx2 < 8 && grid[idx][idx2] == '.') {
      idx--;
      idx2--;
    }
    if (idx >= 0 && idx < 8 && idx2 >= 0 && idx2 < 8 && (grid[idx][idx2] == thing || grid[idx][idx2] == thing2))
      return true;

    // NE
    idx = i - 1;
    idx2 = j + 1;
    while (idx >= 0 && idx < 8 && idx2 >= 0 && idx2 < 8 && grid[idx][idx2] == '.') {
      idx--;
      idx2++;
    }
    if (idx >= 0 && idx < 8 && idx2 >= 0 && idx2 < 8 && (grid[idx][idx2] == thing || grid[idx][idx2] == thing2))
      return true;

    // SW
    idx = i + 1;
    idx2 = j - 1;
    while (idx >= 0 && idx < 8 && idx2 >= 0 && idx2 < 8 && grid[idx][idx2] == '.') {
      idx++;
      idx2--;
    }
    if (idx >= 0 && idx < 8 && idx2 >= 0 && idx2 < 8 && (grid[idx][idx2] == thing || grid[idx][idx2] == thing2))
      return true;

    // RIGHT
    idx = i + 1;
    idx2 = j + 1;
    while (idx >= 0 && idx < 8 && idx2 >= 0 && idx2 < 8 && grid[idx][idx2] == '.') {
      idx++;
      idx2++;
    }
    if (idx >= 0 && idx < 8 && idx2 >= 0 && idx2 < 8 && (grid[idx][idx2] == thing || grid[idx][idx2] == thing2))
      return true;

    return false;
  }

  private static boolean deathByRook(Point king, char[][] grid) {
    int i = king.x;
    int j = king.y;
    char thing = '\u000F';
    char thing2 = '\u000F';
    if (Character.isLowerCase(grid[i][j])) {
      // Black King
      thing = 'R';
      thing2 = 'Q';
    } else {
      // White King
      thing = 'r';
      thing2 = 'q';
    }

    // UP
    int idx = i - 1;
    while (idx >= 0 && grid[idx][j] == '.') {
      idx--;
    }
    if (idx >= 0 && idx < 8 && (grid[idx][j] == thing || grid[idx][j] == thing2))
      return true;

    // DOWN
    idx = i + 1;
    while (idx < 8 && grid[idx][j] == '.') {
      idx++;
    }
    if (idx >= 0 && idx < 8 && (grid[idx][j] == thing || grid[idx][j] == thing2))
      return true;

    // LEFT
    idx = j - 1;
    while (idx >= 0 && grid[i][idx] == '.') {
      idx--;
    }
    if (idx >= 0 && idx < 8 && (grid[i][idx] == thing || grid[i][idx] == thing2))
      return true;

    // RIGHT
    idx = j + 1;
    while (idx < 8 && grid[i][idx] == '.') {
      idx++;
    }
    if (idx >= 0 && idx < 8 && (grid[i][idx] == thing || grid[i][idx] == thing2))
      return true;

    return false;
  }

  private static boolean deathByKnight(Point king, char[][] grid) {
    int i = king.x;
    int j = king.y;
    char thing = '\u000F';
    if (Character.isLowerCase(grid[i][j])) {
      // Black King
      thing = 'N';
    } else {
      // White King
      thing = 'n';
    }
    if (i + 2 < 8) {
      if (j - 1 >= 0 && grid[i + 2][j - 1] == thing)
        return true;
      if (j + 1 < 8 && grid[i + 2][j + 1] == thing)
        return true;
    }
    if (i - 2 >= 0) {
      if (j - 1 >= 0 && grid[i - 2][j - 1] == thing)
        return true;
      if (j + 1 < 8 && grid[i - 2][j + 1] == thing)
        return true;
    }
    if (j + 2 < 8) {
      if (i - 1 >= 0 && grid[i - 1][j + 2] == thing)
        return true;
      if (i + 1 < 8 && grid[i + 1][j + 2] == thing)
        return true;
    }
    if (j - 2 >= 0) {
      if (i - 1 >= 0 && grid[i - 1][j - 2] == thing)
        return true;
      if (i + 1 < 8 && grid[i + 1][j - 2] == thing)
        return true;
    }

    return false;
  }

  private static boolean deathByPawn(Point king, char[][] grid) {
    int i = king.x;
    int j = king.y;
    char thing = '\u000F';
    if (Character.isLowerCase(grid[i][j])) {
      // Black King
      i++;
      thing = 'P';
    } else {
      // White King
      i--;
      thing = 'p';
    }
    if (i >= 0 && i < 8) {
      if (j - 1 >= 0 && grid[i][j - 1] == thing)
        return true;
      if (j + 1 < 8 && grid[i][j + 1] == thing)
        return true;
    }
    return false;
  }
}

UVA 462 – Bridge Hand Evaluator

Just an implementation problem. Pretty lengthy though.

import java.io.PrintWriter;
import java.util.Scanner;
import java.util.StringTokenizer;

/**
 * 
 * @author Sanchit M. Bhatnagar
 * @see http://uhunt.felix-halim.net/id/74004
 * 
 */
public class P462 {

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    PrintWriter out = new PrintWriter(System.out);

    while (sc.hasNextLine()) {
      String line = sc.nextLine();
      if (line == null)
        break;
      if (line.equals(""))
        continue;

      StringTokenizer st = new StringTokenizer(line);

      int sum = 0;
      Card[] hand = new Card[13];
      // Step 1
      for (int i = 0; i < 13; i++) {
        hand[i] = new Card(st.nextToken());
        sum += gameCardValue(hand[i]);
      }

      // Step 2
      for (int i = 0; i < 13; i++) {
        if (hand[i].isFaceCard() && hand[i].card.charAt(0) == 'K') {
          char suite = hand[i].card.charAt(1);
          boolean found = false;
          for (int j = 0; j < 13; j++) {
            if (j == i)
              continue;
            if (hand[j].card.charAt(1) == suite) {
              found = true;
              break;
            }
          }
          if (!found)
            sum--;
        }
      }

      // Step 3
      for (int i = 0; i < 13; i++) {
        if (hand[i].isFaceCard() && hand[i].card.charAt(0) == 'Q') {
          char suite = hand[i].card.charAt(1);
          int count = 0;
          for (int j = 0; j < 13; j++) {
            if (j == i)
              continue;
            if (hand[j].card.charAt(1) == suite) {
              count++;
            }
          }
          if (count < 2)
            sum--;
        }
      }

      // Step 4
      for (int i = 0; i < 13; i++) {
        if (hand[i].isFaceCard() && hand[i].card.charAt(0) == 'J') {
          char suite = hand[i].card.charAt(1);
          int count = 0;
          for (int j = 0; j < 13; j++) {
            if (j == i)
              continue;
            if (hand[j].card.charAt(1) == suite) {
              count++;
            }
          }
          if (count < 3)
            sum--;
        }
      }

      // Step 5, 6, 7
      int sum567 = 0;
      int[] suiteCount = new int[4];
      for (int i = 0; i < 13; i++) {
        char suite = hand[i].card.charAt(1);
        switch (suite) {
          case 'S':
            suiteCount[0]++;
            break;
          case 'H':
            suiteCount[1]++;
            break;
          case 'D':
            suiteCount[2]++;
            break;
          case 'C':
            suiteCount[3]++;
            break;
        }
      }
      for (int i = 0; i < 4; i++) {
        if (suiteCount[i] == 2) {
          sum567++;
        } else if (suiteCount[i] == 1) {
          sum567 += 2;
        } else if (suiteCount[i] == 0) {
          sum567 += 2;
        }
      }

      // IsStopped
      boolean[] isStopped = new boolean[4];
      boolean[][] specialCards = new boolean[4][3];
      for (int i = 0; i < 13; i++) {
        char suite = hand[i].card.charAt(1);
        switch (suite) {
          case 'S':
            if (hand[i].card.charAt(0) == 'A') {
              specialCards[0][0] = true;
              isStopped[0] = true;
            } else if (hand[i].card.charAt(0) == 'K') {
              specialCards[0][1] = true;
              if (suiteCount[0] > 1)
                isStopped[0] = true;
            } else if (hand[i].card.charAt(0) == 'Q') {
              if (suiteCount[0] > 2)
                isStopped[0] = true;
              specialCards[0][2] = true;
            }
            break;
          case 'H':
            if (hand[i].card.charAt(0) == 'A') {
              specialCards[1][0] = true;
              isStopped[1] = true;
            } else if (hand[i].card.charAt(0) == 'K') {
              specialCards[1][1] = true;
              if (suiteCount[1] > 1)
                isStopped[1] = true;
            } else if (hand[i].card.charAt(0) == 'Q') {
              if (suiteCount[1] > 2)
                isStopped[1] = true;
              specialCards[1][2] = true;
            }
            break;
          case 'D':
            if (hand[i].card.charAt(0) == 'A') {
              specialCards[2][0] = true;
              isStopped[2] = true;
            } else if (hand[i].card.charAt(0) == 'K') {
              specialCards[2][1] = true;
              if (suiteCount[2] > 1)
                isStopped[2] = true;
            } else if (hand[i].card.charAt(0) == 'Q') {
              specialCards[2][2] = true;
              if (suiteCount[2] > 2)
                isStopped[2] = true;
            }
            break;
          case 'C':
            if (hand[i].card.charAt(0) == 'A') {
              specialCards[3][0] = true;
              isStopped[3] = true;
            } else if (hand[i].card.charAt(0) == 'K') {
              specialCards[3][1] = true;
              if (suiteCount[3] > 1)
                isStopped[3] = true;
            } else if (hand[i].card.charAt(0) == 'Q') {
              specialCards[3][2] = true;
              if (suiteCount[3] > 2)
                isStopped[3] = true;
            }
            break;
        }
      }

      if (sum + sum567 < 14) {
        out.println("PASS");
      } else if (sum + sum567 > 13) {
        if (sum > 15 && isStopped[0] && isStopped[1] && isStopped[2] && isStopped[3]) {
          out.println("BID NO-TRUMP");
        } else {
          int max = -1;
          int maxIndex = -1;
          for (int i = 0; i < 4; i++) {
            if (suiteCount[i] > max) {
              max = suiteCount[i];
              maxIndex = i;
            }
          }
          out.print("BID ");
          switch (maxIndex) {
            case 0:
              out.println("S");
              break;
            case 1:
              out.println("H");
              break;
            case 2:
              out.println("D");
              break;
            case 3:
              out.println("C");
              break;
          }
        }
      }

    }

    out.close();
    sc.close();
  }

  private static int gameCardValue(Card c) {
    if (c.getCardValue() == 1)
      return 4;
    else if (c.getCardValue() == 13)
      return 3;
    else if (c.getCardValue() == 12)
      return 2;
    else if (c.getCardValue() == 11)
      return 1;
    else
      return 0;
  }

  private static class Card {
    String card;

    public Card(String card) {
      int test1 = getSuitIdx(card.charAt(1));
      if (test1 == -1)
        return;
      int test2 = getNumIdx(card.charAt(0));
      if (test2 == -1)
        return;
      this.card = card;
    }

    public boolean isFaceCard() {
      return getSuitIdx(card.charAt(1)) != -1;
    }

    public int getCardValue() {
      return getNumIdx(card.charAt(0));
    }

    private int getSuitIdx(char suit) {
      switch (suit) {
        case 'H':
          return 0;
        case 'S':
          return 1;
        case 'D':
          return 2;
        case 'C':
          return 3;
      }
      return -1;
    }

    private int getNumIdx(char num) {
      switch (num) {
        case 'A':
          return 1;
        case 'T':
          return 10;
        case 'J':
          return 11;
        case 'Q':
          return 12;
        case 'K':
          return 13;
        default:
          try {
            int val = Integer.parseInt(num + "");
            if (val > 1 && val < 10)
              return val;
            return -1;
          } catch (Exception e) {
            return -1;
          }
      }
    }
  }
}

UVA 696 – How Many Knights

This is extremely similar to UVA 278 – Chess but the tricky case is when min = 2. If you write it out on paper you will figure out the optimal placing for the knights.

import java.io.PrintWriter;
import java.util.Scanner;

/**
 *
 * @author Sanchit M. Bhatnagar
 * @see http://uhunt.felix-halim.net/id/74004
 *
 */
public class P696 {

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    PrintWriter out = new PrintWriter(System.out);

    while (sc.hasNext()) {
      int R = sc.nextInt();
      int C = sc.nextInt();
      if (R == 0 && C == 0) {
        break;
      }
      int max = Math.max(R, C);
      int min = Math.min(R, C);
      if (min == 1) {
        out.print(max);
      } else if (min == 2) {
        if (max < 3) {
          out.print(min * max);
        } else if (max == 3) {
          out.print(4);
        } else {
          int tmp = max / 4;
          int rem = max % 4;
          out.print(tmp * min * 2 + Math.min(rem, 2) * 2);
        }
      } else {
        int a = max / 2;
        int b = (max - a);
        int c = min / 2;
        int d = (min - c);
        out.print(Math.max(a * c + b * d, a * d + b * c));
      }
      out.println(" knights may be placed on a " + R + " row " + C + " column board.");
    }

    out.close();
    sc.close();
  }
}

UVA 278 – Chess

Pretty easy problem. Kings, Queens and Rooks are easy; with Knights you need to realize that knigns basically attack boxes of the opposite color. Once you figure that out, you are golden.

import java.io.PrintWriter;
import java.util.Scanner;

/**
 * 
 * @author Sanchit M. Bhatnagar
 * @see http://uhunt.felix-halim.net/id/74004
 * 
 */
public class P278 {

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    PrintWriter out = new PrintWriter(System.out);

    int N = sc.nextInt();
    for (int zz = 0; zz &lt; N; zz++) {
      String type = sc.next();
      int R = sc.nextInt();
      int C = sc.nextInt();
      int min = Math.min(R, C);
      int max = Math.max(R, C);
      if (type.equals(&quot;r&quot;) || type.equals(&quot;Q&quot;)) {
        out.println(min);
      } else if (type.equals(&quot;k&quot;)) {
        int a = max / 2;
        int b = (max - a);
        int c = min / 2;
        int d = (min - c);
        out.println(Math.max(a * c + b * d, a * d + b * c));
      } else if (type.equals(&quot;K&quot;)) {
        out.println(((max + 1) / 2) * ((min + 1) / 2));
      }
    }

    out.close();
    sc.close();
  }
}

UVA 12247 – Jollo

I lazily figured out weather a given nubmer was good enough or not by trying all combinations. I’m sure there’s a better (greedy) way to do this that involves less work. Greedy doesn’t always work, but though so be careful! I messed up twice by trying a greedy strategy and gave up when I got tired of finding something that has no counterexamples.

import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Scanner;

/**
 * 
 * @author Sanchit M. Bhatnagar
 * @see http://uhunt.felix-halim.net/id/74004
 * 
 */
public class P12247 {

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    PrintWriter out = new PrintWriter(System.out);

    while (sc.hasNext()) {
      int[] princess = new int[] { sc.nextInt(), sc.nextInt(), sc.nextInt() };
      if (princess[0] == 0)
        break;
      int[] prince = new int[] { -1, sc.nextInt(), sc.nextInt() };
      out.println(check(princess, prince));
    }

    out.close();
    sc.close();
  }

  // Cheating
  private static int[][] perm = { new int[] { 0, 1, 2 }, new int[] { 0, 2, 1 }, new int[] { 1, 0, 2 }, new int[] { 1, 2, 0 }, new int[] { 2, 0, 1 }, new int[] { 2, 1, 0 } };

  private static int check(int[] princess, int[] prince) {
    int[] tmpPrincess = Arrays.copyOf(princess, princess.length);
    int[] tmpPrince = null;
    int min = 1;
    boolean found = false;
    for (int i = min; !found && i <= 52; i++) {
      tmpPrince = Arrays.copyOf(prince, prince.length);
      tmpPrince[0] = i;
      if (i != tmpPrincess[0] && i != tmpPrincess[1] && i != tmpPrincess[2] && i != tmpPrince[1] && i != tmpPrince[2]) {
        min = i;
        // Try to lose
        int count = 0;
        for (int j = 0; count == 0 && j < perm.length; j++) {
          int subCount = 0;
          for (int k = 0; k < 3; k++) {
            if (tmpPrince[perm[j][k]] > tmpPrincess[k]) {
              subCount++;
            }
          }
          if (subCount < 2)
            count++;
        }
        if (count == 0)
          found = true;
      }
    }
    if (!found) {
      return -1;
    } else {
      return min;
    }
  }
}

UVA 10646 – What is the Card?

Pretty straightforward. Don’t even need to use this Card class that I have been using for the past few questions!

import java.io.PrintWriter;
import java.util.Scanner;

/**
 * 
 * @author Sanchit M. Bhatnagar
 * @see http://uhunt.felix-halim.net/id/74004
 * 
 */
public class P10646 {

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    PrintWriter out = new PrintWriter(System.out);

    int N = sc.nextInt();
    for (int zz = 1; zz <= N; zz++) {
      String[] deck = new String[52];
      for (int i = 0; i < 52; i++) {
        deck[i] = sc.next();
      }
      int Y = 0;
      int last = -1;
      int count = 0;
      for (int i = 25; i >= 0 && count < 3; i--) {
        int val = getVal(deck[i]);
        Y += val;
        i -= (10 - val);
        count++;
        last = i;
      }

      if (Y <= last) {
        out.println("Case " + zz + ": " + deck[Y - 1]);
      } else {
        out.println("Case " + zz + ": " + deck[26 + (Y - last) - 1]);
      }
    }
    sc.close();
    out.close();
  }

  private static int getVal(String card) {
    char c = card.charAt(0);
    if (c >= '2' && c <= '9') {
      return Integer.parseInt(c + "");
    }
    return 10;
  }
}

UVA 10205 – Stack ’em Up

Pretty much just an implementation problem.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;

/**
 * 
 * @author Sanchit M. Bhatnagar
 * @see http://uhunt.felix-halim.net/id/74004
 * 
 */
public class P10205 {

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    PrintWriter out = new PrintWriter(System.out);
    String line = null;
    StringTokenizer st = null;

    int cases = Integer.parseInt(br.readLine());
    br.readLine(); // Read blank line.

    for (int zz = 0; zz < cases; zz++) {
      if (zz != 0)
        out.println();

      int shuffles = Integer.parseInt(br.readLine());
      int[][] caesar = new int[shuffles][52];
      for (int i = 0; i < shuffles; i++) {
        int count = 0;
        while (count < 52) {
          st = new StringTokenizer(br.readLine());
          while (st.hasMoreTokens()) {
            caesar[i][count] = Integer.parseInt(st.nextToken()) - 1;
            count++;
          }
        }
      }

      Card[] newDeck = new Card[52];
      init(newDeck);
      while ((line = br.readLine()) != null) {
        if (line.trim().equals(""))
          break;
        int move = Integer.parseInt(line) - 1;
        Card[] tmp = new Card[52];
        for (int i = 0; i < 52; i++) {
          tmp[i] = newDeck[caesar[move][i]];
        }
        newDeck = tmp;
      }
      for (int i = 0; i < 52; i++) {
        out.println(newDeck[i]);
      }
    }

    out.close();
    br.close();
  }

  private static void init(Card[] newDeck) {
    String[] suitOrder = new String[] { "Clubs", "Diamonds", "Hearts", "Spades" };
    String[] order = { "2", "3", "4", "5", "6", "7", "8", "9", "10", "Jack", "Queen", "King", "Ace" };
    for (int j = 0; j < 4; j++) {
      for (int i = 0; i < 13; i++) {
        newDeck[i + 13 * j] = new Card(order[i], suitOrder[j]);
      }
    }
  }

  @SuppressWarnings("unused")
  private static class Card {
    String card;
    String card2;
    String num;
    String suit;

    public Card(String num, String suit) {
      card2 = num + " of " + suit;
      this.num = num;
      this.suit = suit;
      if (this.num == "10") {
        card = "T" + suit.charAt(0);
      } else {
        card = num.charAt(0) + "" + suit.charAt(0);
      }
    }

    public String toString() {
      return this.card2;
    }
  }
}

UVA 162 – Beggar My Neighbour

This was a pain to debug but I finally got it right. There’s a little bit of trickery with outputting the result as well so watch out for that!

import java.io.PrintWriter;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Scanner;
import java.util.StringTokenizer;

/**
 * 
 * @author Sanchit M. Bhatnagar
 * @see http://uhunt.felix-halim.net/id/74004
 * 
 */
public class P162 {

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    PrintWriter out = new PrintWriter(System.out);

    while (sc.hasNextLine()) {
      String line = sc.nextLine().trim();
      while (line.equals(""))
        line = sc.nextLine();
      if (line.equals("#"))
        break;

      gameOver = false;
      Player[] players = new Player[2];
      for (int i = 0; i < players.length; i++) {
        players[i] = new Player();
      }
      Card[] deck = new Card[52];
      StringTokenizer st = new StringTokenizer(line);
      for (int i = 0; i < 13; i++) {
        deck[i] = new Card(st.nextToken());
      }
      for (int i = 13; i < 52; i++) {
        deck[i] = new Card(sc.next());
      }

      for (int j = 0; j < players.length; j++) {
        for (int i = 0; i < 26; i++) {
          players[j].deck.add(deck[i * 2 + j]);
        }
        Collections.reverse(players[j].deck);
      }

      // players[0] = non-dealer
      // players[1] = dealer

      int idx = 0;
      LinkedList<Card> stack = new LinkedList<>();
      while ((players[0].deck.size() > 0 || players[1].deck.size() > 0) && !gameOver) {
        Card played = players[idx].deck.poll();
        if (played == null)
          break;
        stack.add(played);
        if (played.isFaceCard()) {
          idx = doThing(stack, players, idx);
        }
        idx = 1 - idx;
      }
      if (players[0].deck.isEmpty()) {
        out.println("1 " + String.format("%2d", players[1].deck.size()));
      } else {
        out.println("2 " + String.format("%2d", players[0].deck.size()));
      }

    }
    out.close();
    sc.close();
  }

  private static boolean gameOver = false;

  private static int doThing(LinkedList<Card> stack, Player[] players, int idx) {
    boolean good = true;
    idx = 1 - idx;
    int val = getGameCardVal(stack.peekLast());
    for (int i = 0; i < val; i++) {
      Card played = players[idx].deck.poll();
      if (played == null) {
        gameOver = true;
        good = false;
        break;
      } else {
        stack.add(played);
        if (played.isFaceCard()) {
          return doThing(stack, players, idx);
        }
      }
    }
    if (good)
      while (!stack.isEmpty()) {
        players[1 - idx].deck.add(stack.poll());
      }
    return idx;
  }

  private static int getGameCardVal(Card c) {
    switch (c.card.charAt(1)) {
      case 'A':
        return 4;
      case 'K':
        return 3;
      case 'Q':
        return 2;
      case 'J':
        return 1;
    }
    return 0;
  }

  private static class Card {
    String card;

    public Card(String card) {
      int test1 = getSuitIdx(card.charAt(0));
      if (test1 == -1)
        return;
      int test2 = getNumIdx(card.charAt(1));
      if (test2 == -1)
        return;
      this.card = card;
    }

    public boolean isFaceCard() {
      int val = getCardValue();
      return (val == 1 || val == 11 || val == 12 || val == 13);
    }

    public int getCardValue() {
      return getNumIdx(card.charAt(1));
    }

    private int getSuitIdx(char suit) {
      switch (suit) {
        case 'H':
          return 0;
        case 'S':
          return 1;
        case 'D':
          return 2;
        case 'C':
          return 3;
      }
      return -1;
    }

    private int getNumIdx(char num) {
      switch (num) {
        case 'A':
          return 1;
        case 'T':
          return 10;
        case 'J':
          return 11;
        case 'Q':
          return 12;
        case 'K':
          return 13;
        default:
          try {
            int val = Integer.parseInt(num + "");
            if (val > 1 && val < 10)
              return val;
            return -1;
          } catch (Exception e) {
            return -1;
          }
      }
    }

    @Override
    public String toString() {
      return this.card;
    }

  }

  private static class Player {
    private LinkedList<Card> deck;

    public Player() {
      deck = new LinkedList<>();
    }

    @Override
    public String toString() {
      return this.deck.toString();
    }
  }

}

UVA 12478 – Hardest Problem Ever (Easy)

So this was an interesting problem. You could have technically solved it manually but that would have taken too much time. If you didn’t mind at most 7 WA’s you could have just tried all 8 solutions one at a time and gotten it correct. I did it the long way; making my program solve it for me.

I used this string normalization technique I was ‘taught’ in college. It’s a neat little trick that I seem to use every chance I get. Pretty easy solution once you know you can map all permutations of a string to just one string!

import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Scanner;

/**
 * 
 * @author Sanchit M. Bhatnagar
 * @see http://uhunt.felix-halim.net/id/74004
 * 
 */
public class P12478 {

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    PrintWriter out = new PrintWriter(System.out);

    String[] grid = new String[] { "OBIDAIBKR", "RKAULHISP", "SADIYANNO", "HEISAWHIA", "IRAKIBULS", "MFBINTRNO", "UTOYZIFAH", "LEBSYNUNE", "EMOTIONNAL" };

    String[] originalNames = new String[] { "RAKIBUL", "ANINDYA", "MOSHIUR", "SHIPLU", "KABIR", "SUNNY", "OBAIDA", "WASI" };

    String[] names = new String[originalNames.length];
    int[] count = new int[names.length];

    for (int i = 0; i &lt; names.length; i++) {
      names[i] = normalize(originalNames[i]);
    }

    // Check Horizontally
    for (int zz = 0; zz &lt; 9; zz++) {
      for (int i = 0; i &lt; 9; i++) {
        for (int j = i + 4; j &lt;= 9; j++) { //Shortest name is 4 characters so we are checking for sub-strings of at least that length. We could also have capped the sub-string to at most 7 characters based on the names provided.
          String substring = normalize(grid[zz].substring(i, j));
          for (int k = 0; k &lt; names.length; k++) {
            if (substring.equals(names[k])) {
              count[k]++;
            }
          }
        }
      }
    }

    // Check Vertically
    String[] grid2 = new String[grid.length];
    for (int j = 0; j &lt; 9; j++) {
      char[] tmp = new char[9];
      for (int i = 0; i &lt; 9; i++) {
        tmp[i] = grid[i].charAt(j);
      }
      grid2[j] = new String(tmp);
    }

    for (int zz = 0; zz &lt; 9; zz++) {
      for (int i = 0; i &lt; 9; i++) {
        for (int j = i + 4; j &lt;= 9; j++) {
          String substring = normalize(grid2[zz].substring(i, j));
          for (int k = 0; k &lt; names.length; k++) {
            if (substring.equals(names[k])) {
              count[k]++;
            }
          }
        }
      }
    }

    for (int i = 0; i &lt; count.length; i++) {
      if (count[i] == 2) {
        out.println(originalNames[i]);
      }
    }

    out.close();
    sc.close();
  }

  // Normalizes all strings
  private static String normalize(String word) {
    char[] list = word.toCharArray();
    Arrays.sort(list);
    return new String(list);
  }
}

Edit: Further explanation. I’ve also updated the code to avoid the IndexOutOfBounds exception I was strangely using a try-catch for.

Firstly let us cover the normalize function. As you can tell by the code, it takes a word, splits it into a character array, sorts the character array and then converts it back into a string. Let us take some examples so that this is clear.

Take a word, let’s say: apple once you run it through the normalize function it will become aelpp. The same will happen for all permutations of apple (I won’t list them all) for example aplpe, ppael, leapp, etc. This allows us to quickly check if a particular permutation of a word is in the grid.

If this part is clear then we can just move on to the checking part.

We will go through the grid one row at a time (the code with the comment stating horizontal). Find all substrings within that line, normalize them and then compare them with the names array. If they are in the array then we increment a counter (named count). We do the same thing for the grid vertically.

UVA 11956 – Brainfuck

So this problem wont work on uva however I am pretty sure that my implementation is correct. Really simple problem.

import java.io.PrintWriter;
import java.util.Scanner;

/**
*
* @author Sanchit M. Bhatnagar
* @see http://uhunt.felix-halim.net/id/74004
*
*/
public class P11956 {

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
PrintWriter out = new PrintWriter(System.out);

int T = Integer.parseInt(sc.nextLine());
for (int zz = 1; zz <= T; zz++) { int idx = 0; int[] byteArray = new int[100]; char[] input = sc.nextLine().trim().toCharArray(); for (int i = 0; i < input.length; i++) {         switch (input[i]) {           case '>‘:
idx++;
break;
case ‘<': idx--; break; case '+': byteArray[idx]++; break; case '-': byteArray[idx]--; break; } idx = (idx + byteArray.length) % byteArray.length; byteArray[idx] = (byteArray[idx] + 256) % 256; } out.print("Case " + zz + ":"); for (int i = 0; i < byteArray.length; i++) { String print = String.format("%02x", byteArray[i]).toUpperCase(); out.print(" " + print); } out.println(); } out.close(); sc.close(); } } [/java]