Solution: HackerRank Sherlock and Moving Tiles in Ruby

Author: telwell
Date: July 6, 2016
Categories: Coding, Solutions

This one was pretty fun! To be honest, I found it a little tricky at first but once I got the hang of it the math was pretty easy. The key is understanding that the velocity of each square is how much they each move on the line y = x every interval. NOT how much to increment each (x,y) coordinate every interval as I naively thought.

So, first of all, let’s check out the question prompt and get a solid grasp of the question. Then let’s do some math to solve for t, which is the amount of time needed for square q to be the proper area.

    \begin{document}t = time \\ v_1 = velocity \ of \ \square_1 \\ v_2 = velocity \ of \ \square_2 \\ l_q = length \ of \ side \ \square_q \\ x = side \ of \ the \ right \ \triangle \ with \ bottom-left \ corner \ of \ \square_1 \ and \ \square_2 \ as \ vertices \\ \\ \begin{equation*} Diagonal \ between \ \square_1 \ and \ \square_2 \\ &= t \cdot v_2 - t \cdot v_1 \\ &= t(v_2 - v_1) \vspace{5mm} \\ \end{equation*} Pythagorean \ Theorem \ gives \ us: \\ \begin{equation*} [t(v_2 - v_1)]^2 = 2 \cdot x^2 \\ \end{equation*} \begin{equation*} x &= \frac {t \cdot (v_2 - v_1)} {\sqrt{2}} \end{equation} \vspace{5mm} To find l_q: \\ \begin{equation*} l_q = l - x = l - \frac {t \cdot (v_2 - v_1)} {\sqrt{2}} \\ l_q - l = - \frac {t \cdot (v_2 - v_1)} {\sqrt{2}} \\ l - l_q = \frac {t \cdot (v_2 - v_1)} {\sqrt{2}} \\ \sqrt{2} \cdot (l - l_q) &= t \cdot (v_2 - v_1) \\ t &= \frac {\sqrt{2} \cdot (l - l_q)} {(v_2 - v_1)} \end{equation} \end{document}

Apologies for the LaTeX with the poor formatting, I’m not entirely used to it yet. Perhaps with a few more of these problems I will be!

Anyway, when we solve for time we’re basically looking for when one side of square q will be the square root of the sought-after area. In order to implement this in Ruby I built a simple PORO that just implements the equation from above in Ruby.

Remember, though, that the velocity of square 1 could be larger than the velocity of square 2. The equation above was built with the velocity of square 2 being greater than the velocity of square 1. There are a couple ways to account for this, but I simply just took the absolute value of the result to achieve the correct answer.

# Sherlock and Moving Tiles
# https://www.hackerrank.com/challenges/sherlock-and-moving-tiles

class System
	
	
	def initialize
		@s = get_square_info
		@q = get_q_info
		@q.each do |q|
			puts get_t_from_q(q)
		end
	end
	
	
	def get_t_from_q(q)
		lq = Math.sqrt(q)
		# This is a little hairy, but once you draw it out you can find that
		# the equation for t is: 
		# sqrt(2) * (lq - l)
		# ------------------
		# (s2 - s1)
		# where lq is the length of a side of square q, is is the length of a main square
		# s2 and s1 are the velocities of square 2 and 1 respectively 
		((Math.sqrt(2) * (@s[:l] - lq) / (@s[:s1] - @s[:s2]))).abs
	end
	
	def get_square_info
		s_info = {}
		line = gets.split.map(&:to_f)
		s_info[:l] = line[0]
		s_info[:s1] = line[1]
		s_info[:s2] = line[2]
		s_info
	end


	def get_q_info
		q = []
		count = gets.to_i
		count.times do |i|
			q << gets.to_f
		end
		q
	end
	
	
end


s = System.new

This worked for every test case. Were you able to solve this problem? What strategies did you use to do so?

«
»