プログラミングのお題スレ Part22 (858ﾚｽ)
上下前次1-新
抽出解除 ﾚｽ栞
ﾘﾛｰﾄﾞ規制です｡10分ほどで解除するので､他のﾌﾞﾗｳｻﾞへ避難してください｡
208(2): デフォルトの名無しさん [sage] 2024/02/02(金) 10:53:02.58 ID:fEMhv+T7(2/2) AAS
>>207207(1): デフォルトの名無しさん [sage] 2024/02/02(金) 10:50:23.49 ID:fEMhv+T7(1/2) AAS
>>206
Rust
fn foo<'a, 'b>(input: &'b [&'a str]) -> Vec<Vec<&'a str>> {
struct Data<'a> { name: &'a str, rep: usize, coll: Option<Vec<usize }
let mut data = Vec::<Data>::new();
let mut map = HashMap::<&str, usize>::new();
for s in input {
let (index0, index1) = s.splitn(2, '=')
.map(|s| match map.get(s) {
Some(&index) => data[index].rep,
None => {
let index = data.len();
map.insert(s, index);
data.push(Data { name: s, rep: index, coll: Some(vec![index]), });
index
},
})
.sorted().tuple_windows().next().unwrap();
if index0 != index1 {
let coll0 = data[index0].coll.take().unwrap();
let coll1 = data[index1].coll.take().unwrap();
coll1.iter().for_each(|&index| data[index].rep = index0);
data[index0].coll = Some(itertools::merge(coll0, coll1).collect());
}
}
data.iter().map(|data| &data.coll).flatten()
.map(|coll| coll.iter().map(|&index| data[index].name).collect()).collect()
}
の動作確認用追加分
use std::collections::HashMap;
use itertools::Itertools;
fn main() {
let input = [
"a1=a2", "b1=b2", "b3=b2", "c1=c2", "e1=e2",
"a3=a4", "c3=c4", "e1=e3", "a2=a4", "c3=c1",
"b3=a4", "c2=d1", "a4=a5", "d2=c1", "b4=b3", "d3=c3"
];
let output = [
vec!["a1", "a2", "b1", "b2", "b3", "a3", "a4", "a5", "b4"],
vec!["c1", "c2", "c3", "c4", "d1", "d2", "d3"],
vec!["e1", "e2", "e3"]
];
assert_eq!(foo(&input), output);
}
216: 9 [sage] 2024/02/04(日) 16:39:59.23 ID:jTY6zdRX(1/2) AAS
>>208 Perl5
use feature qw{:5.16 signatures};
no warnings qw(experimental::signatures);
@s = qw[a1=a2 b1=b2 b3=b2 c1=c2 e1=e2 a3=a4 c3=c4 e1=e3 a2=a4 c3=c1 b3=a4 c2=d1 a4=a5 d2=c1 b4=b3 d3=c3];
for (map{[sort /(\w+)=(\w+)/]} @s) {
($l, $r) = @$_;
$g{$r} //= $g{$l} //= $g{$r} // $l;
$h{$g{$r}} = $g{$l} if $g{$l} ne $g{$r};
}
$h{$k} = sub($e){$h{$e} ? __SUB__->($h{$e}) : $e}->($v) while ($k, $v) = each %h;
$g{$_} = $h{$g{$_}} // $g{$_} for keys %g;
push @{$r{$v}}, $k while ($k, $v) = each %g;
say "@$_" for values %r;
※見易くするためインデントを全角スペースに置換してあります
実行結果
$ perl 22_206_grouping.pl
b3 a3 a5 b4 a4 a1 b1 a2 b2
c1 d1 d3 c3 c2 d2 c4
e3 e1 e2
217: 9 [sage] 2024/02/04(日) 18:22:17.66 ID:jTY6zdRX(2/2) AAS
>>208 宛てじゃなかった
>>206206(23): デフォルトの名無しさん [] 2024/02/02(金) 06:41:15.23 ID:CC6U77IS(1) AAS
お題
入力データをグループ分けして出力せよ
入力データの、= の左右は同じグループである。
出力する順番は、入力データの出現順とする
UnionFind を使えば良いかも
入力データ
["a1=a2", "b1=b2", "b3=b2", "c1=c2", "e1=e2",
"a3=a4", "c3=c4", "e1=e3", "a2=a4", "c3=c1",
"b3=a4", "c2=d1", "a4=a5", "d2=c1", "b4=b3", "d3=c3"]
出力
[["a1", "a2", "b1", "b2", "b3", "a3", "a4", "a5", "b4"],
["c1", "c2", "c3", "c4", "d1", "d2", "d3"],
["e1", "e2", "e3"]]
Ruby で、UnionFind を自作してみた。
下はユニットテストです
外部ﾘﾝｸ:paiza.io
外部ﾘﾝｸ:paiza.io
の回答だったわ… orz
上下前次1-新書関写板覧索設栞歴
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.053s