two_array_problem.rs

//! This is a solution to the HackerRank problem, Two Array Problem.
//!
//!     https://www.hackerrank.com/challenges/weird-queries/problem
//!
//! The array manipulation operations aren't too difficult. I wouldn't even 
//! classify them as tedious. The challenge is to find a way to get the bounding
//! circle of the points.
//!
//! The bounding circle can be found with Welzl's Algorithm. There are a number 
//! of example implementations of the algorithm that can be gleaned from.
//!
//!     https://en.wikipedia.org/wiki/Smallest-circle_problem#Welzl's_algorithm
//!     https://www.geeksforgeeks.org/minimum-enclosing-circle-set-1/
//!
//! The random number generator at the bottom of this file was included because
//! Rust relies on 3rd party libraries for this, which I wasn't sure would be 
//! provided in the HR execution environment. They're easy to implement anyway. 
//! The Welzl algorithm relies to a small degree on randomization.

use std::convert::TryFrom;
use std::convert::TryInto;
use std::error::Error;
use std::fmt::Debug;
use std::io::{BufRead, stdin};
use std::time::SystemTime;

// Operations
const REVERSE: usize = 1;
const SWAP   : usize = 2;
const XSWAP  : usize = 3;
const RADIUS : usize = 4;


fn main() -> Result<(), Box<dyn Error>> {
    let data = stdin().lock().lines().skip(1)
                      .collect::<Result<Vec<_>, _>>()?;
                      
    let mut data = data.into_iter()
                       .map(|l| l.split_whitespace().map(|w| w.parse())
                                  .collect::<Result<Vec<usize>, _>>());
                                 
    let mut a0 = data.next().ok_or("Incomplete data.")??;
    let mut a1 = data.next().ok_or("Incomplete data.")??;
    
    seed(); // Seed the RNG.
    
    for query in data {
        let query = query?;
        
        match query[0] {
            REVERSE => {
                let [id, l, r]: [_; 3] = query[1..=3].try_into()?;
                
                let v = if id == 0 { &mut a0 } else { &mut a1 };
                
                v[l - 1..r].reverse();
            },
            SWAP => {
                let [id, l1, r1, l2, r2]: [_; 5] = query[1..=5].try_into()?;
                
                let     a = if id == 0 { &mut a0 } else { &mut a1 };
                let mut v = Vec::with_capacity(r2 - l1 + 1);
                
                v.extend_from_slice(&a[l2 - 1..r2    ]);
                v.extend_from_slice(&a[r1    ..l2 - 1]);
                v.extend_from_slice(&a[l1 - 1..r1    ]);
                a[l1 - 1..r2].copy_from_slice(&v);
            },
            XSWAP => {
                let [l, r]: [_; 2] = query[1..=2].try_into()?;
                
                a0[l - 1..r].swap_with_slice(&mut a1[l - 1..r]);
            },
            RADIUS => {
                let [l, r]: [_; 2] = query[1..=2].try_into()?;
                
                let x = &a0[l - 1..r];
                let y = &a1[l - 1..r];

                let p = x.iter().zip(y.iter())
                         .map(|(&x, &y)| Point::new(x as f64, y as f64))
                         .collect::<Vec<_>>();
                             
                let c = Circle::from_points(p);
                let r = c.radius();
                
                println!("{:.2}", r);
            },
            _ => Err("Invalid operation.")?,
        }
    }    
    Ok(())
}

/// Object representing a circle and providing methods to calculate the minimum
/// enclosing circle of a collection of points.
///
#[derive(Clone, Copy)]
pub struct Circle {
    center: Point,
    radius: f64,
}

impl Circle {
    /// Produce a new circle object with center point and given radius.
    ///
    pub fn new(center: Point, radius: f64) -> Self {
        Self { center, radius }
    }

    /// Returns the radius of the enclosing circle.
    ///
    pub fn radius(&self) -> f64 {
        self.radius
    }
    
    /// Finds the minimum sized circle that can enclose all points. The 
    /// time-complexity should work out to `O(n)`.
    ///
    pub fn from_points(points: Vec<Point>)  -> Self {
        enum Stage { 
            First  (Vec<Point>, usize), 
            Second (Vec<Point>, usize, Point),
        }
        use  Stage::*;
        
        let mut p       = points;
        let mut stages  = vec![First(Vec::new(), p.len())];
        let mut results = vec![];

        while let Some(stage) = stages.pop() {
            match stage {
                First(r, n) => {
                    if n == 0 || r.len() == 3 {
                        let c1 = match r.len() {
                            3 => Self::from_3_points(&r[0], &r[1], &r[2]),
                            2 => Self::from_2_points(&r[0], &r[1]),
                            1 => Self::new(r[0], 0.),
                            0 => Self::new(Point { x: 0., y: 0. }, 0.),
                            _ => panic!("Too many `r` points."),
                        };
                        results.push(c1);
                    } else {
                        let idx = random(n);
                        let p1  = p[idx];
                        p.swap(idx, n - 1);

                        stages.push(Second(r.clone(), n, p1));
                        stages.push(First(r, n - 1));
                    }
                },
                Second(mut r, n, p1) => {
                    let c1 = results.pop().unwrap();

                    if c1.contains_point(&p1) {
                        results.push(c1);
                    } else {
                        r.push(p1);
                        stages.push(First(r, n - 1));
                    }
                }
            }
        }
        results.pop().unwrap()
    }
    
    /// Create circle that intersects the 3 points.
    ///
    fn from_3_points(p1: &Point, p2: &Point, p3: &Point) -> Self {
        let p12 = Point::new(p2.x - p1.x, p2.y - p1.y);
        let p13 = Point::new(p3.x - p1.x, p3.y - p1.y);
        
        let c12  = p12.x * p12.x + p12.y * p12.y;
        let c13  = p13.x * p13.x + p13.y * p13.y;
        let c123 = p12.x * p13.y - p12.y * p13.x;
        
        let cx = (p13.y * c12 - p12.y * c13) / (2. * c123);
        let cy = (p12.x * c13 - p13.x * c12) / (2. * c123);
        
        let center = Point::new(cx + p1.x, cy + p1.y);
        
        Self::new(center, center.distance(p1))
    }
    
    /// Creates circle that intersects the two points.
    ///
    fn from_2_points(p1: &Point, p2: &Point) -> Self {
        let center = Point::new((p1.x + p2.x) / 2., 
                                (p1.y + p2.y) / 2.);
        Self::new(center, p1.distance(p2) / 2.)
    }
    
    /// Returns true if the circile contains the point.
    ///
    fn contains_point(&self, point: &Point) -> bool {
        self.center.distance(point) <= self.radius
    }
       
}

/// Represents a point on a 2D plane.
///
#[derive(Clone, Copy)]
pub struct Point {
    x: f64,
    y: f64,
}

impl Point {
    pub fn new(x: f64, y: f64) -> Self {
        Self { x, y }
    }
    /// Returns the distance between `self` and `other`.
    ///
    pub fn distance(&self, other: &Point) -> f64 {
        ((other.x - self.x).powf(2.) + 
         (other.y - self.y).powf(2.)).sqrt()
    }    
}

/// The static RNG instance.
///
static mut LCG_RAND_GEN: LcgRandGen = LcgRandGen { 
    seed: 748392749010,
    incr: 1442695040888963407,
    mult: 6364136223846793005 
};

/// Seeds the RNG off the system clock.
///
pub fn seed()
{
    let ns = SystemTime::now().elapsed().unwrap().as_nanos() as u64;
    unsafe { 
        LCG_RAND_GEN.seed = LCG_RAND_GEN.seed.wrapping_add(ns); 
    }
}

/// Returns a randum number in the range `[0..modulus)`.
///
pub fn random<T>(modulus: T) -> T
where
    T: TryInto<u64> + TryFrom<u64>,
    <T as TryInto<u64>>::Error: Debug,
    <T as TryFrom<u64>>::Error: Debug,
{
    let m = modulus.try_into().unwrap();
    let v = unsafe { LCG_RAND_GEN.next().unwrap() };
    (v % m).try_into().unwrap()
}

/// An iterator that produces pseudo-random numbers.
///
pub struct LcgRandGen {
    seed    : u64,
    incr    : u64,
    mult    : u64,
}

impl Iterator for LcgRandGen {
    type Item = u64;
    
    /// Produces the next random value.
    ///
    fn next(&mut self) -> Option<Self::Item> {
        self.seed = self.mult.wrapping_mul(self.seed)
                             .wrapping_add(self.incr);
        Some(self.seed)
    }
}