HackerRank King Richard’s Knights Solution
In this post, we will solve HackerRank King Richard’s Knights Problem Solution. King Richard is leading a troop of N power 2 knights into battle! Being very organized, he labels his knights K0, K1,…, K N power 2 – 1 and arranges them in an N x N square formation, demonstrated
Before the battle begins, he wants to test how well his knights follow instructions. He issues S drill commands, where each command follows the format a; b; d; and is executed like so:
- All knights in the square having the top-left corner at location (a, b) and the bottom-right corner at location (ai +di,bi + di) rotate 90° in the clockwise direction. Recall that some location (r, c) denotes the cell located at the intersection of row r and column c.
You must follow the commands sequentially. The square for each command is completely contained within the square for the previous command. Assume all knights follow the commands perfectly.
After performing all S drill commands, it’s time for battle! King Richard chooses knights Kw₁, Kw2,…, KwL for his first wave of attack; however, because the knights were reordered by the drill commands, he’s not sure where his chosen knights are! As his second-in-command, you must find the locations of the knights. For each knight Kw₁ Kw2,…,KwL, print the knight’s row and column locations as two space-separated values on a new line.
Input Format
This is broken down into three parts:
- The first line contains a single integer, N.
- The second line contains a single integer, S.
- Each line i of the S subsequent lines describes a command in the form of three space- separated integers corresponding to a, b, and di, respectively.
Output Format
Print L lines of output, where each line j contains two space-separated integers describing the respective row and column values where knight Kwj, is located.
Sample Input
7
4
1 2 4
2 3 3
3 4 1
3 4 0
7
0
6
9
11
24
25
48
Sample Output
1 1
1 7
4 6
3 4
2 5
2 4
7 7
In the final configuration:
- Knight Ko is at location (1, 1)
- Knight K6 is at location (1,7)
- Knight Kg is at location (4, 6)
- Knight K11 is at location (3, 4)
- Knight K24 is at location (2,5)
- Knight K25 is at location (2, 4)
- Knight K48 is at location (7,7)
King Richard’s Knights C Solution
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <inttypes.h>
#include <string.h>
int main()
{
int64_t N, S, L;
int64_t * command, *initialArea, *searchArea;
scanf ( "%lld", &N );
scanf ( "%lld", &S );
command = ( int64_t * ) malloc ( 3 * S * sizeof ( int64_t ) );
initialArea = ( int64_t * ) malloc ( 3 * S * sizeof ( int64_t ) );
searchArea = ( int64_t * ) malloc ( 4 * S * sizeof ( int64_t ) );
for ( int64_t i = 0; i < S; i++ )
{
scanf ( "%lld%lld%lld", command + i * 3, command + i * 3 + 1, command + i * 3 + 2 );
command[3 * i + 0]--;
command[3 * i + 1]--;
}
initialArea[0] = command[0];
initialArea[1] = command[1];
initialArea[2] = command[2];
searchArea[4 * 0 + 0] = initialArea[3 * 0 + 0];
searchArea[4 * 0 + 1] = initialArea[3 * 0 + 0] + initialArea[3 * 0 + 2];
searchArea[4 * 0 + 2] = initialArea[3 * 0 + 1];
searchArea[4 * 0 + 3] = initialArea[3 * 0 + 1] + initialArea[3 * 0 + 2];
for ( int64_t i = 1; i < S; i++ )
{
int64_t di = command[3 * i + 0] - command[3 * ( i - 1 ) + 0];
int64_t dj = command[3 * i + 1] - command[3 * ( i - 1 ) + 1];
initialArea[3 * i + 2] = command[3 * i + 2];
switch ( i % 4 )
{
case 0:
initialArea[3 * i + 0] = initialArea[3 * ( i - 1 ) + 0] + di;
initialArea[3 * i + 1] = initialArea[3 * ( i - 1 ) + 1] + dj;
break;
case 1:
initialArea[3 * i + 0] = initialArea[3 * ( i - 1 ) + 0] - dj + initialArea[3 * ( i - 1 ) + 2] - initialArea[3 * i + 2];
initialArea[3 * i + 1] = initialArea[3 * ( i - 1 ) + 1] + di;
break;
case 2:
initialArea[3 * i + 0] = initialArea[3 * ( i - 1 ) + 0] - di + initialArea[3 * ( i - 1 ) + 2] - initialArea[3 * i + 2];
initialArea[3 * i + 1] = initialArea[3 * ( i - 1 ) + 1] - dj + initialArea[3 * ( i - 1 ) + 2] - initialArea[3 * i + 2];
break;
case 3:
initialArea[3 * i + 0] = initialArea[3 * ( i - 1 ) + 0] + dj;
initialArea[3 * i + 1] = initialArea[3 * ( i - 1 ) + 1] - di + initialArea[3 * ( i - 1 ) + 2] - initialArea[3 * i + 2];
break;
}
searchArea[4 * i + 0] = initialArea[3 * i + 0];
searchArea[4 * i + 1] = initialArea[3 * i + 0] + initialArea[3 * i + 2];
searchArea[4 * i + 2] = initialArea[3 * i + 1];
searchArea[4 * i + 3] = initialArea[3 * i + 1] + initialArea[3 * i + 2];
}
// for ( int64_t i = 0; i < S; i++ )
// {
// printf ( "(%d, %d, %d) (%d, %d, %d)\n", command[3 * i + 0], command[3 * i + 1], command[3 * i + 2], initialArea[3 * i + 0], initialArea[3 * i + 1], initialArea[3 * i + 2]);
// }
scanf ( "%lld", &L );
while ( L-- > 0 )
{
int64_t w;
scanf ( "%lld", &w );
int64_t i = w / N, j = w % N;
int64_t max = S - 1, min = -1, last = max / 2;
while ( max > min )
{
if ( i >= searchArea[4 * last + 0] &&
i <= searchArea[4 * last + 1] &&
j >= searchArea[4 * last + 2] &&
j <= searchArea[4 * last + 3] )
{
min = last;
int64_t temp = min + max;
if ( temp % 2 == 1 )
{
last = temp / 2 + 1;
}
else
{
last = temp / 2;
}
}
else
{
max = last - 1;
last = ( min + max ) / 2;
}
}
// printf("last = %lld\n", last);
int64_t di = i - initialArea[3 * last + 0];
int64_t dj = j - initialArea[3 * last + 1];
if ( last >= 0 )
{
switch ( ( last + 1 ) % 4 )
{
case 0:
i = di + command[3 * last + 0];
j = dj + command[3 * last + 1];
break;
case 1:
i = dj + command[3 * last + 0];
j = command[3 * last + 1] + command[3 * last + 2] - di;
break;
case 2:
i = command[3 * last + 0] + command[3 * last + 2] - di;
j = command[3 * last + 1] + command[3 * last + 2] - dj;
break;
case 3:
i = command[3 * last + 0] + command[3 * last + 2] - dj;
j = di + command[3 * last + 1];
break;
}
}
printf ( "%lld %lld\n", i + 1, j + 1 );
}
return 0;
}
King Richard’s Knights C++ Solution
#include <bits/stdc++.h>
using namespace std;
int S,N,L;
typedef complex<int> pt;
struct state {
pt orig;
pt now;
int d,idx;
pt get_at(int x,int y) {
x-=real(now);
y-=imag(now);
int rots=idx%4;
swap(x,y);
for(;rots--;) {
int tmp=x;
x=y;
y=d-tmp;
}
swap(x,y);
return pt(real(orig)+x,imag(orig)+y);
}
bool has(int x,int y) {
return x>=real(orig) && y>=imag(orig) && x<=real(orig)+d && y<=imag(orig)+d;
}
pt rlook(int x,int y) {
swap(orig,now);
idx = 4-(idx%4);
pt ans=get_at(x,y);
idx=4-(idx%4);
swap(orig,now);
return ans;
}
};
vector<state> vs;
int main() {
cin>>N>>S;
vs.push_back({pt(1,1),pt(1,1),N-1,0});
for(int i=1;i<=S;i++) {
int a,b,d; cin>>a>>b>>d;
pt ul=vs.back().get_at(a,b);
pt dr=vs.back().get_at(a+d,b+d);
pt neworig={min(real(ul),real(dr)), min(imag(ul),imag(dr))};
pt newnow={a,b};
vs.push_back({neworig,newnow,d,i});
}
for(auto &st : vs) {
// cout<<st.orig<<" "<<st.now<<" "<<st.d<<" "<<st.idx<<endl;
}
cin>>L;
for(;L--;) {
long long w; cin>>w;
int x=w/N+1;
int y=w%N+1;
int lb=0,rb=S;
for(;lb<rb;) {
int mb=(lb+rb+1)/2;
if(vs[mb].has(x,y)) lb=mb;
else rb=mb-1;
}
pt p=vs[lb].rlook(x,y);
cout<<real(p)<<" "<<imag(p)<<endl;
}
}
King Richard’s Knights C Sharp Solution
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
class Solution {
public class Linear
{
public long A { get; }
public long B { get; }
public Linear(long a, long b)
{
A = a;
B = b;
}
public long ValueAt(long x)
{
return A * x + B;
}
public long InverseValue(long y)
{
return (y - B) / A;
}
public Linear Chain(Linear inner)
{
return new Linear(A*inner.A, A*inner.B + B );
}
}
public class Square
{
public readonly Point Orig;
public readonly long D;
private Linear _transformX;
private Linear _transformY;
private bool _swapCoords;
public Square(Point orig, long d)
{
Orig = orig;
D = d;
_transformY = new Linear(1L, -Orig.X + Orig.Y);
_transformX = new Linear(-1L, D + Orig.X + Orig.Y);
_swapCoords = true;
}
public bool Contains(Point p)
{
return Orig.X <= p.X && p.X <= Orig.X + D &&
Orig.Y <= p.Y && p.Y <= Orig.Y + D;
}
public bool Contains(Square sq)
{
Point[] pts = new Point[]
{
sq.Orig,
new Point(sq.Orig.Y + sq.D, sq.Orig.X),
new Point(sq.Orig.Y, sq.Orig.X + sq.D),
new Point(sq.Orig.Y + sq.D, sq.Orig.X + sq.D)
};
return pts.All(_ => Contains(_));
}
// Find inverse, for sqare sq contained in this sqare.
public Square Inverse(Square sq)
{
Point[] pts = new Point[]
{
sq.Orig,
new Point(sq.Orig.Y + sq.D, sq.Orig.X),
new Point(sq.Orig.Y, sq.Orig.X + sq.D),
new Point(sq.Orig.Y + sq.D, sq.Orig.X + sq.D)
};
var invertedPts = pts.Select(_ => Inverse(_));
return new Square(FindOrigin(invertedPts), sq.D)
{
_transformY = sq._transformY,
_transformX = sq._transformX,
_swapCoords = sq._swapCoords
};
}
public void Chain(Square sq, bool swapCoords)
{
if (!sq.Contains(this))
throw new ArgumentException();
_swapCoords = swapCoords;
_transformX = _transformX.Chain(sq._transformY);
_transformY = _transformY.Chain(sq._transformX);
}
public Point Transform(Point p)
{
if (_swapCoords)
return new Point(_transformY.ValueAt(p.X), _transformX.ValueAt(p.Y));
return new Point(_transformY.ValueAt(p.Y), _transformX.ValueAt(p.X));
}
// Find inverse, for point p contained in this sqare.
private Point Inverse(Point p)
{
if (!Contains(p))
throw new ArgumentOutOfRangeException();
if (_swapCoords)
return new Point(_transformX.InverseValue(p.X), _transformY.InverseValue(p.Y));
return new Point(_transformY.InverseValue(p.Y), _transformX.InverseValue(p.X));
}
private Point FindOrigin(IEnumerable<Point> pts)
{
Point origin = pts.First();
foreach (var pt in pts)
if (origin.X >= pt.X && origin.Y >= pt.Y)
origin = pt;
return origin;
}
}
public class Point
{
public long X { get; }
public long Y { get; }
public Point(long y, long x)
{
Y = y;
X = x;
}
}
public class Solver
{
private readonly Square[] _invertedSquares;
public Solver(int[][] commands)
{
var sqares = commands
.Where(_ => _[2] > 0)
.Select(_ => new Square(new Point(_[0], _[1]), _[2]))
.ToArray();
for (int i = 1; i < sqares.Length; i++)
sqares[i].Chain(sqares[i-1], (i + 1) % 2 == 1);
_invertedSquares = new Square[sqares.Length];
_invertedSquares[0] = sqares[0];
for (int i = 1; i < sqares.Length; i++)
_invertedSquares[i] = sqares[i-1].Inverse(sqares[i]);
}
public Square FindMinContainingSqare(Point p)
{
Square lastFound = null;
int l = 0;
int r = _invertedSquares.Length - 1;
while (l <= r)
{
int mid = ((r - l) / 2) + l;
if (_invertedSquares[mid].Contains(p))
{
lastFound = _invertedSquares[mid];
l = mid + 1;
}
else
r = mid - 1;
}
return lastFound;
}
public Point Solve(Point p)
{
var square = FindMinContainingSqare(p);
if (square == null)
return p;
return square.Transform(p);
}
}
/*
* Complete the kingRichardKnights function below.
*/
static long[][] kingRichardKnights(int n, int[][] commands, long[] knights)
{
var solver = new Solver(commands);
long[][] result = new long[knights.Length][];
int idx = 0;
foreach (long k in knights)
{
long y = (k / n) + 1;
long x = (k % n) + 1;
var p = solver.Solve(new Point(y, x));
result[idx++] = new long[] {p.Y, p.X};
}
return result;
}
static void Main(string[] args) {
TextWriter textWriter = new StreamWriter(@System.Environment.GetEnvironmentVariable("OUTPUT_PATH"), true);
int n = Convert.ToInt32(Console.ReadLine());
int s = Convert.ToInt32(Console.ReadLine());
int[][] commands = new int[s][];
for (int commandsRowItr = 0; commandsRowItr < s; commandsRowItr++) {
commands[commandsRowItr] = Array.ConvertAll(Console.ReadLine().Split(' '), commandsTemp => Convert.ToInt32(commandsTemp));
}
int k = Convert.ToInt32(Console.ReadLine());
long[] knights = new long[k];
for (int i = 0; i < k; i++)
knights[i] = Convert.ToInt64(Console.ReadLine());
long[][] result = kingRichardKnights(n, commands, knights);
//int[][] result = kingRichardKnights(n, s, knights);
textWriter.WriteLine(String.Join("\n", result.Select(x => String.Join(" ", x))));
textWriter.Flush();
textWriter.Close();
}
}
King Richard’s Knights Java Solution
import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
public class Solution {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int s = sc.nextInt();
long[] a = new long[s+1];
long[] b = new long[s+1];
long[] d = new long[s+1];
long[] tln = new long[s+1];
a[0] = 1;
b[0] = 1;
d[0] = n-1;
for (int i = 1; i <= s; i++) {
a[i] = sc.nextInt();
b[i] = sc.nextInt();
d[i] = sc.nextInt();
if (i%4==1) {
tln[i] = tln[i-1]+(a[i]-a[i-1])*n+(b[i]-b[i-1]);
} else if (i%4==2) {
tln[i] = tln[i-1]+((b[i-1]+d[i-1])-(b[i]+d[i]))*n+(a[i]-a[i-1]);
} else if (i%4==3) {
tln[i] = tln[i-1]+((a[i-1]+d[i-1])-(a[i]+d[i]))*n+((b[i-1]+d[i-1])-(b[i]+d[i]));
} else if (i%4==0) {
tln[i] = tln[i-1]+(b[i]-b[i-1])*n+((a[i-1]+d[i-1])-(a[i]+d[i]));
}
}
int l = sc.nextInt();
long[] w = new long[l];
for (int i = 0; i < l; i++) {
w[i] = sc.nextLong();
int low = 0;
int high = s;
while (low != high) {
int mid = (low+high+1)/2;
if (w[i] >= tln[mid] && w[i] < tln[mid]+(d[mid]+1)*n && w[i]%n >= tln[mid]%n && w[i]%n <= (tln[mid]%n)+d[mid])
low = mid;
else
high = mid-1;
}
long off1 = (w[i]-tln[low])/n;
long off2 = (w[i]-tln[low])%n;
if (low%4==0) {
System.out.println((a[low]+off1)+" "+(b[low]+off2));
} else if (low%4==1) {
System.out.println((a[low]+off2)+" "+(b[low]+d[low]-off1));
} else if (low%4==2) {
System.out.println((a[low]+d[low]-off1)+" "+(b[low]+d[low]-off2));
} else if (low%4==3) {
System.out.println((a[low]+d[low]-off2)+" "+(b[low]+off1));
}
}
}
}
King Richard’s Knights JavaScript Solution
'use strict';
const fs = require('fs');
process.stdin.resume();
process.stdin.setEncoding('utf-8');
let inputString = '';
let currentLine = 0;
process.stdin.on('data', inputStdin => {
inputString += inputStdin;
});
process.stdin.on('end', _ => {
inputString = inputString.trim().split('\n').map(str => str.trim());
main();
});
function readLine() {
return inputString[currentLine++];
}
class Command{
constructor(original,newCoord,dimension,iters){
this.original = original;
this.newCoord = newCoord;
this.dimension = dimension;
this.iters = iters;
}
get(x,y){
x -= this.newCoord[0];
y -= this.newCoord[1];
let rotations = this.iters % 4;
[x,y] = [y,x];
while(rotations != 0){
let temp = x;
x = y;
y = this.dimension - temp;
rotations--;
}
[x,y] = [y,x];
return [this.original[0]+x,this.original[1]+y];
}
has(x,y){
return (x >= this.original[0] && y>= this.original[1] && x <= this.original[0]+this.dimension && y<= this.original[1]+this.dimension);
}
check(x,y){
[this.original,this.newCoord] = [this.newCoord,this.original];
this.iters = 4 - (this.iters%4);
let result = this.get(x,y);
this.iters = 4 - (this.iters%4);
[this.original,this.newCoord] = [this.newCoord,this.original];
return result;
}
}
function kingRichardKnights(n,s,commands,knights){
var commandData = [];
commandData.push(new Command([1,1],[1,1],(n-1),0));
for(let i = 0;i < s;i++){
let a = commands[i][0];
let b = commands[i][1];
let d = commands[i][2]
let startCoord = commandData[commandData.length - 1].get(a,b);
let endCoord = commandData[commandData.length - 1].get(a+d,b+d);
let original = [];
original[0] = Math.min(startCoord[0],endCoord[0]);
original[1] = Math.min(startCoord[1],endCoord[1]);
commandData.push(new Command(original,[a,b],d,i+1));
}
var points = [];
for(let j = 0;j<knights.length;j++){
let x = Math.floor(knights[j]/n)+1;
let y = knights[j]%n+1;
let lowerBound = 0;
let upperBound = s;
while(lowerBound<upperBound){
let mid = Math.floor((lowerBound+upperBound+1)/2);
if(commandData[mid].has(x,y)){
lowerBound = mid;
} else {
upperBound = mid - 1;
}
}
let requiredPoint = commandData[lowerBound].check(x,y);
points.push(requiredPoint);
}
return points;
}
function main() {
const ws = fs.createWriteStream(process.env.OUTPUT_PATH);
const n = parseInt(readLine(), 10);
const s = parseInt(readLine(), 10);
let commands = Array(s);
for (let commandsRowItr = 0; commandsRowItr < s; commandsRowItr++) {
commands[commandsRowItr] = readLine().split(' ').map(commandsTemp => parseInt(commandsTemp, 10));
}
const noOfKnights = parseInt(readLine(),10);
let knights = Array(noOfKnights);
for(let i = 0;i < noOfKnights;i++){
knights[i] = parseInt(readLine(), 10);;
}
let result = kingRichardKnights(n, s, commands,knights);
ws.write(result.map(x => x.join(' ')).join("\n") + "\n");
ws.end();
}
King Richard’s Knights Python Solution
#!/bin/python3
import os
import sys
def identity():
return [
[1, 0, 0],
[0, 1, 0],
[0, 0, 1],
]
def cw(x, y, k):
return [
[1, x - y, k + x + y],
[0, 0, -1],
[0, 1, 0],
]
def ccw(x, y, k):
return [
[1, k + x + y, -x + y],
[0, 0, 1],
[0, -1, 0],
]
# from profiler import line_profile
def multiply(a, b):
c = [
[0] * len(b[0])
for _ in range(len(a))
]
for i in range(len(a)):
for j in range(len(b[0])):
for k in range(len(a[0])):
c[i][j] += a[i][k] * b[k][j]
return c
# return [
# a[0][0]*b[0][0] + a[0][1]*b[1][0] + a[0][2] * b[2][0]
# ]
def multiply_ccw(x, y, k, a):
return [[
a[0][i] + (k + x + y) * a[1][i] + (-x + y) * a[2][i]
for i in range(3)
], [
a[2][i]
for i in range(3)
], [
-a[1][i]
for i in range(3)
]]
def multiply_cw(x, y, k, a):
return [[
a[0][i] + (x - y) * a[1][i] + (k + x + y) * a[2][i]
for i in range(3)
], [
-a[2][i]
for i in range(3)
], [
a[1][i]
for i in range(3)
]]
#
# Complete the kingRichardKnights function below.
#
# from profiler import line_profile
#
# @line_profile()
def kingRichardKnights(n, commands, knights):
new_commands = []
t = identity()
for ind, c in enumerate(commands):
m = multiply([[1, c[0], c[1]]], t)
new_command = [m[0][1], m[0][2], c[2]]
if (ind % 4) == 1:
new_command[0] -= c[2]
elif (ind % 4) == 2:
new_command[0] -= c[2]
new_command[1] -= c[2]
elif (ind % 4) == 3:
new_command[1] -= c[2]
new_commands.append(new_command)
# t = multiply(ccw(c[0], c[1], c[2]), t)
t = multiply_ccw(c[0], c[1], c[2], t)
to_process = {}
for k in knights:
i, j = (k // n) + 1, (k % n) + 1
l = -1
r = len(new_commands)
while r - l > 1:
s = (l + r) // 2
x, y, k = new_commands[s]
if (x <= i <= x + k and
y <= j <= y + k):
l = s
else:
r = s
to_process.setdefault(l, [])
to_process[l].append((i, j))
ans = {
k: k
for k in to_process.get(-1, [])
}
t = identity()
for ind, c in enumerate(new_commands):
# t = multiply(cw(c[0], c[1], c[2]), t)
t = multiply_cw(c[0], c[1], c[2], t)
for k in to_process.get(ind, []):
m = multiply([[1, k[0], k[1]]], t)
ans[k] = [m[0][1], m[0][2]]
result = []
for k in knights:
result.append(ans[(k // n) + 1, (k % n) + 1])
return result
if __name__ == '__main__':
fptr = open(os.environ['OUTPUT_PATH'], 'w')
# import sys
# sys.stdin = open('input', 'r')
n = int(input())
s = int(input())
commands = []
for _ in range(s):
commands.append(list(map(int, input().rstrip().split())))
kn = int(input())
knights = []
for _ in range(kn):
knights.append(int(input().strip()))
result = kingRichardKnights(n, commands, knights)
fptr.write('\n'.join([' '.join(map(str, x)) for x in result]))
fptr.write('\n')
fptr.close()