Pegman

pegman.md

Problem

While using Google Street View, you may have picked up and dropped the character Pegman before. Today, a mischievous user is going to place Pegman in some cell of a rectangular grid of unit cells with R rows and C columns. Each of the cells in this grid might be blank, or it might be labeled with an arrow pointing in one of four possible directions: up, right, down, or left.

When Pegman is placed on a grid cell, if that cell is blank, Pegman stands still forever. However, if that cell has an arrow, Pegman starts to walk in that direction. As he walks, whenever he encounters a blank cell, he just keeps walking in his current direction, but whenever he encounters another arrow, he changes to the direction of that arrow and then keeps walking.

You know that it is possible that Pegman might keep happily walking around and around the grid forever, but it is also possible that Pegman's walk will take him over the edge of the grid! You may be able to prevent this and save him by changing the direction of one or more arrows. (Each arrow's direction can only be changed to one of the other three possible directions; arrows can only be changed, not added or removed.)

What is the smallest number of arrows you will need to change to ensure that Pegman will not walk off the edge, no matter where on the grid he is initially placed?

Input

The first line of the input gives the number of test cases, T. T test cases follow. Each begins with one line with two space-separated integers R, C. This line is followed by R lines, each of which has C characters, each of which describes a grid cell and is one of the following:

. period = no arrow
^ caret = up arrow
> greater than = right arrow
v lowercase v = down arrow
< less than = left arrow

Output

For each test case, output one line containing "Case #x: y", where x is the test case number (starting from 1) and y is the minimum number of arrows that must be changed to ensure that Pegman will not leave the grid no matter where he is initially placed, or the text IMPOSSIBLE if it is not possible to ensure this, no matter how many arrows you change.

Limits

1 ≤ T ≤ 100. Small dataset

1 ≤ R, C ≤ 4. Large dataset

1 ≤ R, C ≤ 100.

Sample

(See image below)

In Case #1, Pegman is guaranteed to walk off the top edge of the grid, no matter where he is placed. You can prevent that by changing the topmost arrow to point down, which will cause him to walk back and forth between those two arrows forever.

In Case #2, no matter where Pegman is placed, he will walk around and around the board clockwise in a circle. No arrows need to be changed.

In Case #3, the mischievous user might place Pegman on the up arrow in the middle of the grid, in which case he will start walking and then walk off the top edge of the grid. Changing the direction of this arrow won't help: it would just make him walk off a different edge.

In Case #4, the only possible starting cell is blank, so Pegman will stand still forever and is in no danger.

Verify solution

https://code.google.com/codejam/contest/8234486/dashboard

Sample

My solution in Scala

import scala.collection.mutable
import scala.collection.mutable.ListBuffer

case class Cell(label: Char, x: Int, y: Int)

object Pegman {
  def solution(input: String): String = {
    val (height, length, grid) = ("""(\d+)\s(\d)((\n|.)*)""".r.findAllIn(input).matchData map {
      m => (m.group(1).toInt, m.group(2).toInt, m.group(3).replace("\n", "").toCharArray)
    }).next()

    val cellsByRow = new mutable.HashMap[Int, mutable.Set[Cell]] with mutable.MultiMap[Int, Cell]
    val cellsByCol = new mutable.HashMap[Int, mutable.Set[Cell]] with mutable.MultiMap[Int, Cell]
    val unprocessedCells = new ListBuffer[Cell]()

    var counter = 0
    for (row <- 0 until height) {
      for (col <- 0 until length) {
        val currentCell = new Cell(grid(counter), col, row)
        print(currentCell.label)
        if ("^v<>".contains(currentCell.label)) {
          cellsByCol.addBinding(col, currentCell)
          cellsByRow.addBinding(row, currentCell)
          unprocessedCells += currentCell
        }
        counter += 1
      }
      println("")
    }

    def pointsUpToCell(col: Int, row: Int): Boolean = cellsByCol.get(col).get.exists(_.y < row)

    def pointsDownToCell(col: Int, row: Int): Boolean = cellsByCol.get(col).get.exists(_.y > row)

    def pointsRighToCell(col: Int, row: Int): Boolean = cellsByRow.get(row).get.exists(_.x > col)

    def pointsLeftToCell(col: Int, row: Int): Boolean = cellsByRow.get(row).get.exists(_.x < col)

    def canPointToOther(x: Int, y: Int): Boolean =
      pointsUpToCell(x, y) || pointsDownToCell(x, y) || pointsRighToCell(x, y) || pointsLeftToCell(x, y)

    def searchPosibleChanges(x: Int, y: Int): Int =
      if (canPointToOther(x, y))
        1
      else
        throw new scala.Exception("Can't be changed, Pegman dies")

    try {
      val minMov = unprocessedCells.map({
        case Cell('^', x, y) if pointsUpToCell(x, y) => 0
        case Cell('v', x, y) if pointsDownToCell(x, y) => 0
        case Cell('>', x, y) if pointsRighToCell(x, y) => 0
        case Cell('<', x, y) if pointsLeftToCell(x, y) => 0
        case Cell(_, x, y) => searchPosibleChanges(x, y)
      }).sum

      s"${minMov}"
    } catch {
      case e: Exception => "IMPOSSIBRU!!"
    }
  }

  def main(args: Array[String]): Unit = {
    println("Case 1: " + solution(
      """2 1
        |^
        |^
      """.stripMargin))
    println("Case 2: " + solution(
      """2 2
        |>v
        |^<
      """.stripMargin))
    println("Case 3: " + solution(
      """3 3
        |...
        |.^.
        |...
      """.stripMargin))
    println("Case 4: " + solution(
      """1 1
        |.
      """.stripMargin))
    println("Case 5: " + solution(
      """1 2
        |<>
      """.stripMargin))
    println("Case 6: " + solution(
      """2 2
        |^>
        |<v
      """.stripMargin))
  }
}

Output:

^
^
Case 1: 1
>v
^<
Case 2: 0
...
.^.
...
Case 3: IMPOSSIBRU!!
.
Case 4: 0
<>
Case 5: 2
^>
<v
Case 6: 4

My go solution
https://github.com/bubuntux/sport-programming/blob/Nearsoft-pegman/main.go

public class Pegman {
    private static final String INPUT_FILE = "A-small-practice.in";
    private static final String OUTPUT_FILE = "output.out";

    public static void main(String[] args) throws IOException {
        try (Scanner scanner = new Scanner(new File(INPUT_FILE)); FileWriter fw = new FileWriter(new File(OUTPUT_FILE))) {
            StringBuilder stringBuilder = new StringBuilder();
            int t = scanner.nextInt();
            for (int i = 1; i <= t; i++) {
                int r = scanner.nextInt();
                int c = scanner.nextInt();
                char[][] grid = new char[r][c];
                for (int j = 0; j < r; j++) {
                    grid[j] = scanner.next().toCharArray();
                }
                stringBuilder.append(String.format("Case #%d: %s\n", i, minimumMoves(grid)));
            }
            fw.write(stringBuilder.toString());
        }
    }

    private static String minimumMoves(char[][] grid) {
        Cell[][] cellGrid = buildCellGrid(grid);
        for (int i = 0; i < grid[0].length; i++) {
            Character firstArrow = null;
            int rowIndexLastArrow = -1;
            for (int j = 0; j < grid.length; j++) {
                if (grid[j][i] != '.') {
                    if (firstArrow == null) {
                        firstArrow = grid[j][i];
                        cellGrid[j][i].markAsFirstArrowFromColumn();
                    }
                    rowIndexLastArrow = j;
                }
            }
            if(rowIndexLastArrow >= 0) {
                cellGrid[rowIndexLastArrow][i].markAsLastArrowFromColumn();
            }
        }
        for (int i = 0; i < grid.length; i++) {
            Character firstArrow = null;
            int columnIndexLastArrow = -1;
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] != '.') {
                    if (firstArrow == null) {
                        firstArrow = grid[i][j];
                        cellGrid[i][j].markAsFirstArrowFromRow();
                    }
                    columnIndexLastArrow = j;
                }
            }
            if(columnIndexLastArrow >= 0) {
                cellGrid[i][columnIndexLastArrow].markAsLastArrowFromRow();
            }
        }
        int minimumMoves = 0;
        for (Cell[] cellRow : cellGrid) {
            for(Cell cell : cellRow) {
                if(cell.isImpossibleToChange()) {
                    return "IMPOSSIBLE";
                }
                if(cell.shouldArrowShouldBeChanged()) {
                    minimumMoves++;
                }
            }
        }
        return Integer.toString(minimumMoves);
    }

    private static Cell[][] buildCellGrid(char[][] grid) {
        Cell[][] cellGrid = new Cell[grid.length][grid[0].length];
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                cellGrid[i][j] = new Cell(grid[i][j]);
            }
        }
        return cellGrid;
    }

    private static class Cell {
        private char _arrow;
        private boolean _isFirstArrowFromColumn;
        private boolean _isLastArrowFromColumn;
        private boolean _isFirstArrowFromRow;
        private boolean _isLastArrowFromRow;

        Cell(char arrow) {
            _arrow = arrow;
        }

        void markAsFirstArrowFromColumn() {
            _isFirstArrowFromColumn = true;
        }

        void markAsLastArrowFromColumn() {
            _isLastArrowFromColumn = true;
        }

        void markAsFirstArrowFromRow() {
            _isFirstArrowFromRow = true;
        }

        void markAsLastArrowFromRow() {
            _isLastArrowFromRow = true;
        }

        boolean isImpossibleToChange() {
            return _isFirstArrowFromColumn && _isLastArrowFromColumn && _isFirstArrowFromRow && _isLastArrowFromRow;
        }

        boolean shouldArrowShouldBeChanged() {
            return (_isFirstArrowFromColumn && _arrow == '^') ||
                    (_isLastArrowFromColumn && _arrow == 'v') ||
                    (_isFirstArrowFromRow && _arrow == '<') ||
                    (_isLastArrowFromRow && _arrow == '>');
        }
    }
}

public class Pegman {

public static int minimumNumberOfArrowsToChange(final String[][] grid){
    int arrowsToChange = 0;
    for (int row = 0; row<grid.length; row++){
        for (int column = 0; column < grid[row].length; column++){
            String currentDirection = grid[row][column];

            if (!currentDirection.equals(".") && !areMoreArrowsInRow(grid, row) &&  !areMoreArrowsInColumn(grid, column)){
                return -1;
            }

            switch(currentDirection){
                case "ˆ":
                    if (!areMoreArrowsUp(grid, row, column) &&
                        (row == 0 ||
                                areMoreArrowsRight(grid, row, column) ||
                                areMoreArrowsDown(grid, row, column) ||
                                areMoreArrowsLeft(grid, row, column))) {

                        arrowsToChange++;
                    }
                    break;

                case ">":
                    if (!areMoreArrowsRight(grid, row, column) &&
                            (column == grid[row].length ||
                                    areMoreArrowsDown(grid, row, column) ||
                                    areMoreArrowsLeft(grid, row, column)||
                                    areMoreArrowsUp(grid, row, column))) {

                        arrowsToChange++;
                    }

                    break;

                case "v":
                    if (!areMoreArrowsDown(grid, row, column) &&
                            (row == grid.length ||
                                    areMoreArrowsRight(grid, row, column) ||
                                    areMoreArrowsLeft(grid, row, column) ||
                                    areMoreArrowsUp(grid, row, column))) {

                        arrowsToChange++;
                    }
                    break;

                case "<":
                    if (!areMoreArrowsLeft(grid, row, column) &&
                            (row == grid.length ||
                                    areMoreArrowsUp(grid, row, column) ||
                                    areMoreArrowsRight(grid, row, column) ||
                                    areMoreArrowsDown(grid, row, column))) {

                        arrowsToChange++;
                    }
                    break;
            }
        }
    }
    return arrowsToChange;
}

private static boolean areMoreArrowsUp(final String[][] grid, final int currentRow, final int currentColumn){
    for (int row = currentRow-1; row>=0; row--){
        if (!grid[row][currentColumn].equals("."))
            return true;
    }
    return false;
}

private static boolean areMoreArrowsDown(final String[][] grid, final int currentRow, final int currentColumn){
    for (int row = currentRow+1; row<grid.length; row++){
        if (!grid[row][currentColumn].equals("."))
            return true;
    }
    return false;
}

private static boolean areMoreArrowsRight(final String[][] grid, final int currentRow, final int currentColumn){
    for (int column=currentColumn+1; column<grid[currentRow].length; column++){
        if (!grid[currentColumn][column].equals("."))
            return true;
    }
    return false;
}

private static boolean areMoreArrowsLeft(final String[][] grid, final int currentRow, final int currentColumn){
    for (int column=currentColumn-1; column>=0; column--){
        if (!grid[currentColumn][column].equals("."))
            return true;
    }
    return false;
}

private static boolean areMoreArrowsInRow(final String[][] grid, final int currentRow){
    int numOfArrows = 0;
    for (int column = 0; column<grid[currentRow].length; column++){
        if (!grid[currentRow][column].equals("."))
            numOfArrows++;
    }
    return numOfArrows >=2;
}

private static boolean areMoreArrowsInColumn(final String[][] grid, final int currentColumn){
    int numOfArrows = 0;
    for (int row = 0; row<grid.length; row++){
        if (!grid[row][currentColumn].equals("."))
            numOfArrows++;
    }
    return numOfArrows >=2;
}

public static void scanGrids(final String[][][] grids){
    for (int currentCase =0; currentCase< grids.length; currentCase++){
        String result = minimumNumberOfArrowsToChange(grids[currentCase]) +"";
        if (result.equals("-1"))
            result = "IMPOSSIBLE";
        System.out.println("Case #" + currentCase+": " + result );
    }

}

}