プログラミングのお題スレ Part22 (862ﾚｽ)
上下前次1-新
抽出解除 ﾚｽ栞
206(23): デフォルトの名無しさん [] 2024/02/02(金)06:41 ID:CC6U77IS(1)
お題
入力データをグループ分けして出力せよ
入力データの、= の左右は同じグループである。
出力する順番は、入力データの出現順とする
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 を自作してみた。
下はユニットテストです
https://paiza.io/projects/e6nk1EOu3utyWpV3iuWAFQ?language=ruby
https://paiza.io/projects/kjeVtTKeDwEnWVrBU5_nbg?language=ruby
207(1): デフォルトの名無しさん [sage] 2024/02/02(金)10:50 ID:fEMhv+T7(1/2)
>>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()
}
209: デフォルトの名無しさん [sage] 2024/02/02(金)22:48 ID:UezRkqGy(1/4)
>>206 ruby
https://ideone.com/eF5lww
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 ID:UezRkqGy(2/4)
>>206 rust
https://ideone.com/MEZMPO
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 ID:UezRkqGy(3/4)
>>206 ruby
https://ideone.com/daI0QL
・若干の修正
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 ID:UezRkqGy(4/4)
>>206 rust
https://ideone.com/dO4xea
・若干の修正
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
}
213(1): デフォルトの名無しさん [] 2024/02/02(金)23:58 ID:Uk0I9chw(1)
>>206
R
https://ideone.com/FOwwk2
214: デフォルトの名無しさん [] 2024/02/03(土)02:58 ID:bEsWZIv5(1)
>>206
Java
https://paiza.io/projects/TzHsf-cnqzdxSASpwlgg_w
215(1): デフォルトの名無しさん [] 2024/02/03(土)10:26 ID:kmOXhk/V(1)
>>206 >>213
Rでもっと短く書けた。
https://ideone.com/vmtYAJ
217: 9 [sage] 2024/02/04(日)18:22 ID:jTY6zdRX(2/2)
>>208 宛てじゃなかった
>>206 の回答だったわ… orz
218(2): デフォルトの名無しさん [] 2024/02/04(日)18:32 ID:fS5H2fbQ(1/2)
>>206
>>215をPowerShellに移植
$in =
"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"
$in -split "=" |% {$h = @{}; $n = 0} {if (!$h[$_]) {$h[$_] = $n++}}
$eq = $in |% {, $h[$_ -split "="]}
$g = 1..$n
do {
$changed = $false
$eq |% {
$i, $j = $_
switch ($g[$i] - $g[$j]) {
{$_ -gt 0} {$g[$i] = $g[$j]; $changed = $true}
{$_ -lt 0} {$g[$j] = $g[$i]; $changed = $true}
}
}
} while ($changed)
$h.keys | sort {$h[$_]} | group {$g[$h[$_]]} |% {"[$($_.group -join ", ")]"}
-- 実行結果 --
[a1, a2, b1, b2, b3, a3, a4, a5, b4]
[c1, c2, c3, c4, d1, d2, d3]
[e1, e2, e3]
220: デフォルトの名無しさん [] 2024/02/04(日)19:43 ID:NiYs7EK6(1)
>>206
C++
2chｽﾚ:tech
完全にやっつけ仕事、いろいろ課題がありますね
221(1): 211 [sage] 2024/02/04(日)23:55 ID:ytAuzkvH(1)
>>206 ruby
https://ideone.com/2UiT8U
・>>211から若干のアレンジ
・同一グループの収集にSortedSetを使用
222: 17 [] 2024/02/05(月)02:54 ID:8tY/Vubv(1)
>>206
Kotlin
入力データを標準入力から入力したり、クラス作ってその中でまとめる等、色々やって長くなった。
https://paiza.io/projects/zdysD5ygRDFVbY2gAGCwOw
223(2): 221 [sage] 2024/02/05(月)20:08 ID:tt/WRhkt(1/2)
>>206 ruby
https://ideone.com/j2xPyB
・>>221から若干のアレンジ
・SortedSet単位でのみいじるようにした
f = -> a {
g = -> a {a.combination(2) {|x, y| break g.(a.tap {x.merge y; a.delete y}) if x.intersect? y}}
h = a.map {|s| s.split('=')}.flatten.uniq.map.with_index.to_h
a = a.map {|s| s.split('=').map {|k| h[k]}.to_set SortedSet}
g.(a).map {|set| set.map &h.invert.method(:[])}
}
224(2): デフォルトの名無しさん [] 2024/02/05(月)23:26 ID:YjqgZClx(1)
>>206
>>218-219をC#化
https://ideone.com/qWA5TB
225(1): 223 [sage] 2024/02/05(月)23:51 ID:tt/WRhkt(2/2)
>>206 rust
https://ideone.com/Ma1WGV
・>>223の移植
・色々迷いアリ
.map(|k| *h.get(k).unwrap())のところは当初
.map(|k| h.get(k).map(|&i| i)).flatten()などとしていたが
正解がわからないので迷った挙げ句に短く書けるほうを採用
・これに限らずrustは不慣れなので色々珍妙なことをしている可能性アリ
226(1): 225 [sage] 2024/02/06(火)22:07 ID:6T/Xuns0(1)
>>206 rust
https://ideone.com/m5INyJ
・>>225から若干の修正
・不必要なループ回数を訂正
・二重forを一重に（でもかえって煩雑に）
・まだまだ迷いアリ
.map(|k| *h.get(k).unwrap())は結局
.flat_map(|k| h.get(k)).cloned()に置き換え
こっちのほうが個人的にはスッキリ感アリ
>>206 rust
https://ideone.com/hT5zGF
・上記のmutナシ版
・パフォーマンス的な観点もナシ
227(2): デフォルトの名無しさん [] 2024/02/06(火)22:17 ID:ICpsP2hv(1)
>>206
C#で>>224とは別の解法
https://ideone.com/fvtgZa
228: デフォルトの名無しさん [] 2024/02/09(金)20:11 ID:xlZlW34G(1)
>>206
C#でHashSet型を使用。実効速度は>>224と>>227より遅い。
https://ideone.com/cPsAYu
上下前次1-新書関写板覧索設栞歴
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.030s