Created
January 29, 2017 19:32
-
-
Save jianminchen/117b8beda5b447729370b431ea8eb060 to your computer and use it in GitHub Desktop.
Hackerrank Queen attack II - second submission - score 24.51 ( maximum score), failed a few of test cases, bugs need to be fixed.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
using System; | |
using System.Collections.Generic; | |
using System.Linq; | |
using System.Text; | |
using System.Threading.Tasks; | |
namespace QueenAttack2 | |
{ | |
class QueenAttack2 | |
{ | |
internal class Directions | |
{ | |
public static int[] directions_row = new int[] { -1, -1, 0, 1, 1, 1, 0, -1 }; | |
public static int[] directions_col = new int[] { 0, -1, -1, -1, 0, 1, 1, 1 }; | |
public int rows; | |
public int[] minimumDistance; | |
public bool[] minimumDistanceExist; | |
public Tuple<int, int> queen {set; get;} | |
public Directions(int row, int col, int size) | |
{ | |
queen = new Tuple<int, int>(row, col); | |
minimumDistance = new int[8]; | |
minimumDistanceExist = new bool[8]; | |
rows = size; | |
} | |
/* | |
* left, right, up, down, or the four diagonals | |
* 8 directions - clockwise, starting from left. | |
*/ | |
public bool IsOneOfEightDirections( | |
int obstacle_row, | |
int obstacle_col) | |
{ | |
return (obstacle_col == queen.Item2 || | |
obstacle_row == queen.Item1 || | |
Math.Abs(obstacle_row - queen.Item1) == Math.Abs(obstacle_col - queen.Item2) | |
); | |
} | |
/* | |
* Go over 100000 obstacles, and find those 8 minimum one if there is. | |
* | |
*/ | |
public void Keep8MininumObstacles(Tuple<int,int>[] obstacles) | |
{ | |
for(int i = 0; i < obstacles.Length; i ++) | |
{ | |
Tuple<int, int> obstacle = obstacles[i]; | |
if(!IsOneOfEightDirections(obstacle.Item1, obstacle.Item2)) | |
{ | |
continue; | |
} | |
UpdateOneOfDirection(obstacle); | |
} | |
} | |
/* | |
* | |
*/ | |
private void UpdateOneOfDirection(Tuple<int, int> obstacle) | |
{ | |
bool isDirectionLeft = obstacle.Item1 == queen.Item1 && obstacle.Item2 < queen.Item2; | |
bool isDirectionRight = obstacle.Item1 == queen.Item1 && obstacle.Item2 > queen.Item2; | |
bool isDirectionUp = obstacle.Item1 > queen.Item1 && obstacle.Item2 == queen.Item2; | |
bool isDirectionDown = obstacle.Item1 < queen.Item1 && obstacle.Item2 == queen.Item2; | |
bool isDirectionUpLeft = obstacle.Item1 > queen.Item1 && obstacle.Item2 < queen.Item2; | |
bool isDirectionUpRight = obstacle.Item1 > queen.Item1 && obstacle.Item2 > queen.Item2; | |
bool isDirectionDownRight = obstacle.Item1 < queen.Item1 && obstacle.Item2 > queen.Item2; | |
bool isDirectionDownLeft = obstacle.Item1 < queen.Item1 && obstacle.Item2 < queen.Item2; | |
// direction left: | |
if (isDirectionLeft) | |
{ | |
int current = Math.Abs(queen.Item2 - obstacle.Item2); | |
UpdateMinimumDistanceInfo(0, current); | |
} | |
if (isDirectionUpLeft) | |
{ | |
int current = Math.Abs(queen.Item1 - obstacle.Item1); | |
UpdateMinimumDistanceInfo(1, current); | |
} | |
if (isDirectionUp) | |
{ | |
int current = Math.Abs(queen.Item1 - obstacle.Item1); | |
UpdateMinimumDistanceInfo(2, current); | |
} | |
if (isDirectionUpRight) | |
{ | |
int current = Math.Abs(queen.Item1 - obstacle.Item1); | |
UpdateMinimumDistanceInfo(3, current); | |
} | |
if (isDirectionRight) | |
{ | |
int current = Math.Abs(queen.Item2 - obstacle.Item2); | |
UpdateMinimumDistanceInfo(4, current); | |
} | |
if (isDirectionDownRight) | |
{ | |
int current = Math.Abs(queen.Item1 - obstacle.Item1); | |
UpdateMinimumDistanceInfo(5, current); | |
} | |
if (isDirectionDown) | |
{ | |
int current = Math.Abs(queen.Item1 - obstacle.Item1); | |
UpdateMinimumDistanceInfo(6, current); | |
} | |
if (isDirectionDownLeft) | |
{ | |
int current = Math.Abs(queen.Item1 - obstacle.Item1); | |
UpdateMinimumDistanceInfo(7, current); | |
} | |
} | |
/* | |
* 8 directions, use directions_row, directions_col as instruction | |
*/ | |
private void UpdateMinimumDistanceInfo(int direction, int current) | |
{ | |
if (!minimumDistanceExist[direction]) | |
{ | |
minimumDistanceExist[direction] = true; | |
minimumDistance[direction] = current; | |
} | |
else | |
{ | |
if (current < minimumDistance[direction]) | |
{ | |
minimumDistance[0] = current; | |
} | |
} | |
} | |
public int CalculateTotal() | |
{ | |
// public int[] minimumDistance; | |
// public bool[] minimumDistanceExist; | |
int total = 0; | |
for(int i = 0; i < 8; i++) | |
{ | |
if(minimumDistanceExist[i]) | |
{ | |
total += minimumDistance[i] - 1; | |
continue; | |
} | |
if(i == 0) | |
{ | |
// direction left | |
total += queen.Item2; | |
} | |
if(i == 1) | |
{ | |
// direction up-left | |
total += CalculateUpLeftCount(); | |
} | |
if(i == 2) | |
{ | |
// direction up | |
total += rows - queen.Item1 - 1; | |
} | |
if(i == 3) | |
{ | |
// direction up-right | |
total += CalculateUpRightCount(); | |
} | |
if(i == 4) | |
{ | |
// direction right | |
total += rows - queen.Item2 - 1; | |
} | |
if(i == 5 ) | |
{ | |
// direction down-right | |
total += CalculateDownRightCount(); | |
} | |
if(i == 6) | |
{ | |
// direction down | |
total += queen.Item1; | |
} | |
if(i == 7) | |
{ | |
// direction down-left | |
total += CalculateDownLeftCount(); | |
} | |
} | |
return total; | |
} | |
private int CalculateUpLeftCount() | |
{ | |
int row = queen.Item1; | |
int col = queen.Item2; | |
int count = 0; | |
while(row < rows -1 && col > 0) | |
{ | |
row++; | |
col--; | |
count++; | |
} | |
return count; | |
} | |
private int CalculateUpRightCount() | |
{ | |
int row = queen.Item1; | |
int col = queen.Item2; | |
int count = 0; | |
while(row < rows -1 && col < rows - 1) | |
{ | |
row++; | |
col++; | |
count++; | |
} | |
return count; | |
} | |
private int CalculateDownRightCount() | |
{ | |
int row = queen.Item1; | |
int col = queen.Item2; | |
int count = 0; | |
while(row > 0 && col < rows - 1) | |
{ | |
row--; | |
col++; | |
count++; | |
} | |
return count; | |
} | |
private int CalculateDownLeftCount() | |
{ | |
int row = queen.Item1; | |
int col = queen.Item2; | |
int count = 0; | |
while(row > 0 && col > 0) | |
{ | |
row--; | |
col--; | |
count++; | |
} | |
return count; | |
} | |
} | |
static void Main(string[] args) | |
{ | |
ProcessInput(); | |
//RunSampleTestcase(); | |
//RunSampleTestcase2(); | |
} | |
public static void RunSampleTestcase() | |
{ | |
Directions directions = new Directions(3, 3, 4); | |
var obstacles = new Tuple<int, int>[0]; | |
directions.Keep8MininumObstacles(obstacles); | |
Console.WriteLine(directions.CalculateTotal()); | |
} | |
/* | |
* 5 3 | |
* 4 3 | |
* 5 5 | |
* 4 2 | |
* 2 3 | |
* | |
*/ | |
public static void RunSampleTestcase2() | |
{ | |
Directions directions = new Directions(3, 2, 5); | |
var obstacles = new Tuple<int, int>[]{ | |
new Tuple<int,int>(4,4), | |
new Tuple<int,int>(3,1), | |
new Tuple<int,int>(1,2) | |
}; | |
directions.Keep8MininumObstacles(obstacles); | |
Console.WriteLine(directions.CalculateTotal()); | |
} | |
public static void ProcessInput() | |
{ | |
int[] data = Array.ConvertAll(Console.ReadLine().Split(' '), int.Parse); | |
int rows = data[0]; | |
int countObstacles = data[1]; | |
int[] queen = Array.ConvertAll(Console.ReadLine().Split(' '), int.Parse); | |
var obstacles = new Tuple<int, int>[countObstacles]; | |
for (int i = 0; i < countObstacles; i++) | |
{ | |
int[] obstacle = Array.ConvertAll(Console.ReadLine().Split(' '), int.Parse); | |
obstacles[i] = new Tuple<int, int>(obstacle[0]-1, obstacle[1]-1); | |
} | |
Directions directions = new Directions(queen[0] -1, queen[1] - 1, rows); | |
directions.Keep8MininumObstacles(obstacles); | |
Console.WriteLine(directions.CalculateTotal()); | |
} | |
/* | |
* Process all obstacles one by one, determined if the obstacle is on 8 direction. | |
* If it is 8 directions, then update minimum distance one. | |
* The total obstacles are up to 100000, we only need to keep up to 8 obstacles | |
*/ | |
public static IList<Tuple<int, int>> ProcessObstaclesKeep8withMinimuDistance(int n, int x, int y, Tuple<int,int>[] obstacles) | |
{ | |
IList<Tuple<int, int>> minimumOne = new List<Tuple<int, int>>(); | |
return minimumOne; | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment