use core::panic;
use std::alloc::{alloc, dealloc, handle_alloc_error, Layout};
use std::io::stdin;
use std::ptr::null_mut;
#[derive(PartialEq, Eq)]
enum Room {
Empty,
HasCoin,
}
pub struct LinkedListNode<T> {
pub next: *mut LinkedListNode<T>,
pub prev: *mut LinkedListNode<T>,
pub data: T,
}
impl<T> LinkedListNode<T> {
pub fn for_each<F: FnMut(&LinkedListNode<T>)>(&self, mut f: F) {
let mut coin_iter = self as *const LinkedListNode<T>;
while !coin_iter.is_null() {
f(unsafe { &*coin_iter });
coin_iter = unsafe { (*coin_iter).next };
}
}
/// Removes the element the iterator is currently pointing at, and advances the iterator
/// forward to point to the next element instead
pub fn remove_this_element(&mut self) {
unsafe {
if !self.prev.is_null() {
(*self.prev).next = self.next;
}
if !self.next.is_null() {
(*self.next).prev = self.prev;
}
dealloc(
self as *mut LinkedListNode<T> as *mut u8,
Layout::new::<*mut LinkedListNode<T>>(),
);
}
}
}
pub struct LinkedListIter<T> {
address: *mut LinkedListNode<T>,
first_node: *mut LinkedListNode<T>,
}
impl<T> Iterator for LinkedListIter<T> {
type Item = *mut LinkedListNode<T>;
fn next(&mut self) -> Option<Self::Item> {
if self.address.is_null() {
self.address = self.first_node;
None
} else {
let v = Some(self.address);
self.address = unsafe { (*self.address).next };
v
}
}
}
impl<T> LinkedListIter<T> {
pub fn new(first_node: *mut LinkedListNode<T>) -> LinkedListIter<T> {
LinkedListIter {
address: first_node,
first_node,
}
}
pub fn new_with_node_address(
first_node: *mut LinkedListNode<T>,
address: *mut LinkedListNode<T>,
) -> LinkedListIter<T> {
LinkedListIter {
address,
first_node,
}
}
pub fn go_to_address(&mut self, address: *mut LinkedListNode<T>) {
self.address = address;
}
}
fn main() {
let mut n = String::new();
stdin().read_line(&mut n).unwrap();
let _room_count = n.trim().parse::<i32>().unwrap();
let mut room_map = String::new();
stdin().read_line(&mut room_map).unwrap();
let mut robot_position: isize = -1;
let rooms = room_map
.trim()
.chars()
.enumerate()
.map(|(index, room_desc)| match room_desc {
'*' => Room::HasCoin,
'.' => Room::Empty,
'R' => {
robot_position = index as isize;
Room::Empty
}
_ => panic!(),
});
let mut coins = Vec::new();
for (index, room) in rooms.enumerate() {
if room == Room::HasCoin {
coins.push(index as isize);
}
}
coins.sort_unstable();
let mut first_coin: *mut LinkedListNode<isize> = null_mut();
let mut current_coin: *mut LinkedListNode<isize> = null_mut();
let mut prev_coin: *mut LinkedListNode<isize> = null_mut();
let mut is_first_coin = true;
for coin in coins {
current_coin =
unsafe { alloc(Layout::new::<LinkedListNode<isize>>()) } as *mut LinkedListNode<isize>;
if current_coin.is_null() {
handle_alloc_error(Layout::new::<LinkedListNode<isize>>());
}
if is_first_coin {
first_coin = current_coin;
unsafe {
(*first_coin).prev = null_mut() as *mut LinkedListNode<isize>;
}
is_first_coin = false;
} else {
unsafe {
(*prev_coin).next = current_coin;
(*current_coin).prev = prev_coin;
}
}
unsafe {
(*current_coin).data = coin;
(*current_coin).next = null_mut();
}
prev_coin = current_coin;
}
if robot_position == -1 {
panic!()
}
let mut num_coins_collected = 0;
let mut num_steps_taken = 0;
let mut coin_iter = LinkedListIter::new(first_coin);
for coin in &mut coin_iter {
if unsafe { (*coin).data } >= robot_position {
if unsafe { (*coin).prev }.is_null() {
coin_iter.go_to_address(coin);
} else {
coin_iter.go_to_address(unsafe { (*coin).prev });
}
break;
}
}
// There is no coin at a position more right than the robot
if coin_iter.address == first_coin {
coin_iter.go_to_address(current_coin);
}
loop {
let (closest_coin, closest_coin_dis);
let prev_coin = match coin_iter.next() {
None => break,
Some(c) => unsafe { &mut *c },
};
let disp = robot_position.abs_diff(prev_coin.data);
match coin_iter.next() {
None => {
closest_coin = prev_coin;
closest_coin_dis = disp;
}
Some(c) => {
let c = unsafe { &mut *c };
let disc = robot_position.abs_diff(c.data);
if disc < disp {
closest_coin = c;
closest_coin_dis = disc;
} else if disc > disp {
closest_coin = prev_coin;
closest_coin_dis = disp;
} else {
break;
}
}
}
robot_position = closest_coin.data;
if closest_coin.prev.is_null() {
coin_iter.go_to_address(closest_coin.next);
} else {
coin_iter.go_to_address(closest_coin.prev);
}
closest_coin.remove_this_element();
num_coins_collected += 1;
num_steps_taken += closest_coin_dis;
}
println!("{} {}", num_steps_taken, num_coins_collected);
}
