プログラミングのお題スレ Part22 (854ﾚｽ)
上下前次1-新
抽出解除 必死ﾁｪｯｶｰ(本家) (べ) 自ID ﾚｽ栞 あぼーん
ﾘﾛｰﾄﾞ規制です｡10分ほどで解除するので､他のﾌﾞﾗｳｻﾞへ避難してください｡
209: デフォルトの名無しさん [sage] 2024/02/02(金) 22:48:33.27 ID:UezRkqGy(1/4) AAS
>>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
ruby
外部ﾘﾝｸ:ideone.com
f = -> a {
w = a.map {|s| s.split('=')}.flatten.uniq.map.with_index.to_h
a.each_with_object([]) {|s, acc|
x, xa, y, ya = s.split('=').map {|k| [k, acc.find {|b| b.include? k}]}.flatten(1)
if xa && ya then xa.concat (acc.delete ya) << x << y
elsif xa then xa << x << y
elsif ya then ya << x << y
else acc << [x, y]
end
}.map {|a| a.uniq.sort_by {|s| w[s]}}.sort_by {|a| w[a[0]]}
}
210: デフォルトの名無しさん [sage] 2024/02/02(金) 22:51:42.74 ID:UezRkqGy(2/4) AAS
>>206 rust
外部ﾘﾝｸ:ideone.com
fn f<'a>(a: &[&'a str]) -> Vec<Vec<&'a str>> { // '
let h = a.iter().map(|&s| s.split('=')).flatten().rev().enumerate().map(|(p, s)| (s, p)).collect::<HashMap<_, _>>();
let mut acc = Vec::<Vec<&str>>::new();
for xy in a.iter().map(|s| s.split('=').collect::<Vec<_>>()) {
match (acc.iter().position(|b| b.contains(&xy[0])), acc.iter().position(|b| b.contains(&xy[1]))) {
(Some(xi), Some(yi)) => {
let ys = acc[yi].clone();
acc[xi].extend(ys);
acc[xi].extend(xy);
acc.remove(yi);
},
(Some(xi), None) => acc[xi].extend(xy),
(None, Some(yi)) => acc[yi].extend(xy),
_ => acc.push(xy),
}
}
for b in acc.iter_mut() {
b.sort_by(|c, d| h.get(d).cmp(&h.get(c)));
b.dedup();
}
acc.sort_by(|c, d| h.get(d[0]).cmp(&h.get(c[0])));
acc
}
211(1): デフォルトの名無しさん [sage] 2024/02/02(金) 23:24:19.60 ID:UezRkqGy(3/4) AAS
>>206 ruby
外部ﾘﾝｸ:ideone.com
・若干の修正
f = -> a {
w = a.map {|s| s.split('=')}.flatten.uniq.map.with_index.to_h
a.each_with_object([]) {|s, acc|
x, xa, y, ya = s.split('=').map {|k| [k, acc.find {|b| b.include? k}]}.flatten(1)
if xa && ya then xa.concat (acc.delete ya)
elsif xa then xa << y
elsif ya then ya << x
else acc << [x, y]
end
}.map {|a| a.sort_by {|s| w[s]}}.sort_by {|a| w[a[0]]}
}
212: デフォルトの名無しさん [sage] 2024/02/02(金) 23:24:45.86 ID:UezRkqGy(4/4) AAS
>>206 rust
外部ﾘﾝｸ:ideone.com
・若干の修正
fn f<'a>(a: &[&'a str]) -> Vec<Vec<&'a str>> { // '
let h = a.iter().map(|&s| s.split('=')).flatten().rev().enumerate().map(|(p, s)| (s, p)).collect::<HashMap<_, _>>();
let mut acc = Vec::<Vec<&str>>::new();
for xy in a.iter().map(|s| s.split('=').collect::<Vec<_>>()) {
match (acc.iter().position(|b| b.contains(&xy[0])), acc.iter().position(|b| b.contains(&xy[1]))) {
(Some(xi), Some(yi)) => {
let ys = acc[yi].clone();
acc[xi].extend(ys);
acc.remove(yi);
},
(Some(xi), None) => acc[xi].push(xy[1]),
(None, Some(yi)) => acc[yi].push(xy[0]),
_ => acc.push(xy),
}
}
acc.iter_mut().for_each(|b| b.sort_by(|c, d| h.get(d).cmp(&h.get(c))));
acc.sort_by(|c, d| h.get(d[0]).cmp(&h.get(c[0])));
acc
}
上下前次1-新書関写板覧索設栞歴
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.048s