プログラミングのお題スレ Part22 (863ﾚｽ)
上下前次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) AAS
AA省
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) AAS
AA省
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
230(1): デフォルトの名無しさん [] 2024/02/10(土)22:10 ID:HaBtyH/G(1)
>>206
>>227をC++に移植
https://ideone.com/RgBBVA
231: デフォルトの名無しさん [sage] 2024/02/11(日)15:34 ID:3wEOIMb0(1)
>>206 octave
https://ideone.com/b2MsDk
>>206 octave
https://ideone.com/x6Lzmb
232: デフォルトの名無しさん [] 2024/02/11(日)20:38 ID:v64KP9lJ(1)
>>206
>>230をDで書くと
https://ideone.com/9oenyq
になるが、switch case 0, 1, 2の場合も3の場合と同じ処理にすると、効率は落ちるもののかなり短くできる。
https://ideone.com/ILLUdy
233: 223 [sage] 2024/02/12(月)23:45 ID:ix8w7wd+(1)
>>206 octave
https://ideone.com/VtqJcV
・組み合わせつくって集合のペアごとに調べることをやめた
・集合間で重複する要素に着目して集合を減らすようにした
>>223
g.(a).map {|set| set.map &h.invert.method(:[])}じゃなくて単に
g.(a).map {|set| h.keys.values_at *set}で良かった
上下前次1-新書関写板覧索設栞歴
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 1.361s*