?

Log in

Yorool-GUI's blog
четное дерево 
20th-Dec-2016 12:49 pm
лысый
Решил эту штуку (https://www.hackerrank.com/challenges/even-tree, см репост ниже) на Rust-е, ушло около получаса на думание и часа 4 на программирование - правда заметную часть времени читал доки и боролся с borrow checker-ом.
Кстати, borrow checker действительно помогает. Обратите внимание на split_at_mut в calc_weights. Rust мне не позволил получить доступ на запись к элементам массива i и j вот таким образом:

let from = &mut v[i];
let to = &mut v[j];

что логично - это я про себя думаю, что это разные элементы массива. Но ведь возможно, что i == j и компилятор мне об этом напомнил. Пришлось сначала получить раздельный доступ к двум половинкам массива, гарантировав, что v[i] и v[j] различны

под катом решение

use std::io;
use std::io::prelude::*;
use std::str::FromStr;

#[derive(Clone)]
struct Vertex {
  weight: i32,
  links: Vec<usize>,
  followed_links: Vec<usize>
}

impl Vertex {
  fn new() -> Vertex { Vertex { weight: 1, links: Vec::new(), followed_links: Vec::new() } }
}

fn edge(v: &mut Vec<Vertex>, i: usize, j: usize) {
  v[i].links.push(j);
  v[j].links.push(i);
}

fn follow_link(from: &mut Vertex, i: usize, to: &mut Vertex, j: usize)
{
  let l_from = from.links.iter().position(|&n| n==j).unwrap();
  let l_to = to.links.iter().position(|&n| n==i).unwrap();
  from.followed_links.push(from.links.swap_remove(l_from));
  to.followed_links.push(to.links.swap_remove(l_to));
  to.weight += from.weight;
}

fn calc_weights(v: &mut Vec<Vertex>) {
  let mut processed = true;
  while processed {
    processed = false;
    for i in 1..v.len() {
      if v[i].links.len() == 1 {
        processed = true;
        let j = v[i].links[0];
        if i < j {
          let (left, right) = v.split_at_mut(j);
          follow_link(&mut left[i], i, &mut right[0], j);
        } else if i > j {
          let (left, right) = v.split_at_mut(i);
          follow_link(&mut right[0], i, &mut left[j], j);
        } else {
          panic!("Circular link to itself");
        }
      }
    }
    //dump(v);
  }
}

#[allow(dead_code)]
fn dump(v : &Vec<Vertex>) {
    println!("---");
    let mut n = 0;
    for vertex in v {
      if n > 0 {
        print!("{} ({}) : (", n, vertex.weight ); 
        for link in &vertex.links {
          print!("{},",link); 
        }
        print!(") ("); 
        for link in &vertex.followed_links {
          print!("{},",link); 
        }
        println!(")");
      }
      n += 1;
    }
}

fn main() {
    
    let stdin = io::stdin();
    let mut lines = stdin.lock().lines();
    let line1 = lines.next().unwrap().unwrap();
    let mut values1 = line1.split(" ");
    let vertices_count = usize::from_str(values1.next().unwrap()).unwrap();
    //let edges_count = usize::from_str(values1.next().unwrap()).unwrap();
    // println!("vertices = {} edges = {}", vertices_count, edges_count);

    let mut vertices : Vec<Vertex> = vec![Vertex::new(); vertices_count + 1];

    for line in lines {
      let s = line.unwrap(); 
      let mut values = s.split(" ");
      if values.clone().count() == 2 {
        let from = usize::from_str(values.next().unwrap()).unwrap();
        let to = usize::from_str(values.next().unwrap()).unwrap();
        edge(&mut vertices, from, to);
        //println!("{} {}", from, to);
      }
    }

    //dump(&vertices);
    calc_weights(&mut vertices);

    let result = vertices.iter().fold(0, |count, ref vertex| count + if vertex.weight % 2 == 0 { 1 } else { 0 });
    println!("{}", result - 1);

}



update: почитал другие решения - ну да, нет у меня опыта работы с графами, можно было куда лаконичнее сделать. Ну и ладно, и так неплохо получилось

Originally posted by avva at четное дерево
https://www.hackerrank.com/challenges/even-tree

По-русски: написать программу, которая получает с стандартного входа описание дерева, и печатает максимальное количество ребер, которые можно убрать так, чтобы дерево превратилось в лес, в котором в каждой компоненте связности четное число вершин. Пример и точное описание входа/выхода по ссылке.

По-моему, неплохой пример задачи для программистов, которая где-то на уровне интервью в Гугле. Мне сразу несколько вещей в ней нравится:

- надо знать/помнить что-то из теории (граф, дерево, компонента связности), но не глубокие вещи и не сложные алгоритмы, а достаточно для того, чтобы могло включиться алгоритмическое мышление
- надо сначала подумать, как собственно найти искомое, подход "прямиком" слишком трудоемкий
- сам выбираешь структуры данных, нет очевидно верного выбора, можно по-разному
- нужно сесть и написать с нуля работающий код, проверка проблемы "не знаю, как начать"

Я думаю, что если кто-то садится за эту проблему и меньше чем за час у него есть работающий код, то этот человек находится в хорошей форме в плане идти на технические интервью в Гугл/Фейсбук/Амазон итд. Все равно стоит готовиться, плюс еще есть интервью по system design, но для алго/кодинг это неплохие шансы, мне кажется. Конечно, люди, которые занимаются программистскими соревнованиями, щелкают такие задачки за 5-10 минут без проблем, но это другой случай, они натасканы на это. Я говорю про "просто программиста", который сомневается, идти ли на интервью и что там будет.

(чтобы проверить себя, я сел за эту задачу вчера, когда прочитал про нее. У меня был готова программа за 45 минут, включая проверку и отладку. Я пользовался https://repl.it/ для отладки, т.к. под рукой не было компилятора).
Comments 
20th-Dec-2016 11:46 am (UTC)
В предложенном решении
- не делается диагностика несвязности входного графа (зато делается диагностика его цикличности)
- не обрабатывается случай, когда решения не существует (а эта проверка вообще мгновенная)
20th-Dec-2016 01:39 pm (UTC)
Задания на проверку несвязности не было, так что я не парился. Цикличность я кстати тоже не детектирую - если будет цикл, у меня программа тупо зависнет.
Основное, из-за чего так длинно получилось - я не подумал, что дерево можно же от любого узла начать разматывать. А я зачем-то пытаюсь решить, какие узлы являются листьями и иду от них к центру - делаю лишнюю работу
This page was loaded Feb 21st 2017, 9:40 am GMT.