graphs1030.md

https://gist.github.com/johntran - > graphs1030.md

Graphs 2018 Oct 30

Problem Set

Zombie Clusters

You have a matrix, full of 1 and zeros. Each {row,col} value represents the friendship status of two people/zombies. If they know each other the value is 1, else zero. How many clusters of zombies are there? A cluster is a group of zombies that directly and indirectly know each other.

Ex:

[ [1,1,0],
  [1,1,0],
  [0,0,1] ]

There are two zombie clusters, first cluster is in node[0][0], node[0][1], node[1][0], and node[1][1]. Second cluster is in node[2][2].

ex 2:

[ [1,0,0],
  [0,1,0],
  [0,0,1] ]

There are three zombie clusters. first is in node[0][0], second is in node[1][1], third is in node[2][2]

Snakes and Ladders Matrix

Given a snakes and ladders rectangular MxN board game, find the minimum number of dice throws required to reach the final cell from the first cell Snakes and Ladders rules:

• From square x, you throw a six-sided die which lands on result y, and you end up at square x + y
• If the square you land has a ladder, you go up the ladder
• If the square you land has a snake, you go down from the head to the tail.

In the board given below, it will take minimum 4 throws to get from 1 to 36. Sequence: [1,6,4,1] There may be more than one such sequence. [4,2,6,4]

function createBoard(numberOfCells, ladders, snakes) {
  // create a board of to cellNumber cells
  // move 0 is the start of the board
  const board = Array(numberOfCells).fill(-1);
  Object.keys(ladders).forEach(ladder => {
    // key is where the player has to be to take the ladder
    // value is where the player ends up after taking the ladder
    board[ladder] = ladders[ladder];
  });
  Object.keys(snakes).forEach(snake => {
    // key is where the player has to be to take the snake
    // value is where the player ends up after taking the snake
    board[snake] = snakes[snake];
  });
  return board;
}

function getMinThrows(board, numberOfCells) {
 // fill me
}

function snakesAndLadders(numberOfCells, ladders, snakes) {
  const board = createBoard(numberOfCells, ladders, snakes);
  return getMinThrows(board, numberOfCells);
}

snakesAndLadders(
  30,
  { 2: 21, 4: 7, 10: 25, 19: 28 },
  { 26: 0, 20: 8, 16: 3, 18: 6 },
);

// returns 3

snakesAndLadders(
  36,
 { 1: 14,  4:6,  8: 26 , 24: 34},
 { 33: 11 , 31: 29 ,  23: 15 ,  16:3 }
);

// returns 4

Board for above:

Given a sorted dictionary of an alien language, find order of characters

Input:  words[] = {"baa", "abcd", "abca", "cab", "cad"}
Output: Order of characters is 'b', 'd', 'a', 'c'
Note that words are sorted and in the given language "baa" 
comes before "abcd", therefore 'b' is before 'a' in output.
Similarly we can find other orders.

Input:  words[] = {"caa", "aaa", "aab"}
Output: Order of characters is 'c', 'a', 'b'