Skip to content

Instantly share code, notes, and snippets.

@jianminchen
Created January 29, 2017 19:32
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save jianminchen/117b8beda5b447729370b431ea8eb060 to your computer and use it in GitHub Desktop.
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.
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