yorool_gui: (лысый)
[personal profile] yorool_gui
Решил эту штуку (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 [livejournal.com profile] avva at четное дерево
https://www.hackerrank.com/challenges/even-tree

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

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

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

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

(чтобы проверить себя, я сел за эту задачу вчера, когда прочитал про нее. У меня был готова программа за 45 минут, включая проверку и отладку. Я пользовался https://repl.it/ для отладки, т.к. под рукой не было компилятора).
From:
Anonymous( )Anonymous This account has disabled anonymous posting.
OpenID( )OpenID You can comment on this post while signed in with an account from many other sites, once you have confirmed your email address. Sign in using OpenID.
User
Account name:
Password:
If you don't have an account you can create one now.
Subject:
HTML doesn't work in the subject.

Message:

 
Notice: This account is set to log the IP addresses of everyone who comments.
Links will be displayed as unclickable URLs to help prevent spam.

Profile

yorool_gui: (Default)
Michael Ilyin

April 2017

S M T W T F S
      1
2 345678
910 1112131415
16171819202122
23242526272829
30      

Most Popular Tags

Style Credit

Expand Cut Tags

No cut tags
Page generated Jul. 27th, 2017 02:43 am
Powered by Dreamwidth Studios