プログラミングのお題スレ Part22 (858ﾚｽ)
上下前次1-新
抽出解除 ﾚｽ栞
ﾘﾛｰﾄﾞ規制です｡10分ほどで解除するので､他のﾌﾞﾗｳｻﾞへ避難してください｡
206(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
207(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()
}
209: デフォルトの名無しさん [sage] 2024/02/02(金) 22:48:33.27 ID:UezRkqGy(1/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) << 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
}
213(1): デフォルトの名無しさん [] 2024/02/02(金) 23:58:11.98 ID:Uk0I9chw(1) AAS
>>206
R
外部ﾘﾝｸ:ideone.com
214: デフォルトの名無しさん [] 2024/02/03(土) 02:58:35.44 ID:bEsWZIv5(1) AAS
>>206
Java
外部ﾘﾝｸ:paiza.io
215(1): デフォルトの名無しさん [] 2024/02/03(土) 10:26:51.46 ID:kmOXhk/V(1) AAS
>>206 >>213
Rでもっと短く書けた。
外部ﾘﾝｸ:ideone.com
217: 9 [sage] 2024/02/04(日) 18:22:17.66 ID:jTY6zdRX(2/2) AAS
>>208208(2): デフォルトの名無しさん [sage] 2024/02/02(金) 10:53:02.58 ID:fEMhv+T7(2/2) AAS
>>207の動作確認用追加分
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);
}
宛てじゃなかった
>>206 の回答だったわ… orz
218(2): デフォルトの名無しさん [] 2024/02/04(日) 18:32:39.04 ID:fS5H2fbQ(1/2) AAS
>>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:39.57 ID:NiYs7EK6(1) AAS
>>206
C++
2chｽﾚ:tech
完全にやっつけ仕事、いろいろ課題がありますね
221(1): 211 [sage] 2024/02/04(日) 23:55:45.21 ID:ytAuzkvH(1) AAS
>>206 ruby
外部ﾘﾝｸ:ideone.com
・>>211から若干のアレンジ
・同一グループの収集にSortedSetを使用
222: 17 [] 2024/02/05(月) 02:54:15.12 ID:8tY/Vubv(1) AAS
>>206
Kotlin
入力データを標準入力から入力したり、クラス作ってその中でまとめる等、色々やって長くなった。
外部ﾘﾝｸ:paiza.io
223(2): 221 [sage] 2024/02/05(月) 20:08:21.07 ID:tt/WRhkt(1/2) AAS
>>206 ruby
外部ﾘﾝｸ:ideone.com
・>>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:45.85 ID:YjqgZClx(1) AAS
>>206
>>218-219をC#化
外部ﾘﾝｸ:ideone.com
225(1): 223 [sage] 2024/02/05(月) 23:51:15.55 ID:tt/WRhkt(2/2) AAS
>>206 rust
外部ﾘﾝｸ:ideone.com
・>>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:13.88 ID:6T/Xuns0(1) AAS
>>206 rust
外部ﾘﾝｸ:ideone.com
・>>225から若干の修正
・不必要なループ回数を訂正
・二重forを一重に（でもかえって煩雑に）
・まだまだ迷いアリ
.map(|k| *h.get(k).unwrap())は結局
.flat_map(|k| h.get(k)).cloned()に置き換え
こっちのほうが個人的にはスッキリ感アリ
>>206 rust
外部ﾘﾝｸ:ideone.com
・上記のmutナシ版
・パフォーマンス的な観点もナシ
227(2): デフォルトの名無しさん [] 2024/02/06(火) 22:17:05.66 ID:ICpsP2hv(1) AAS
>>206
C#で>>224とは別の解法
外部ﾘﾝｸ:ideone.com
228: デフォルトの名無しさん [] 2024/02/09(金) 20:11:03.28 ID:xlZlW34G(1) AAS
>>206
C#でHashSet型を使用。実効速度は>>224と>>227より遅い。
外部ﾘﾝｸ:ideone.com
230(1): デフォルトの名無しさん [] 2024/02/10(土) 22:10:46.31 ID:HaBtyH/G(1) AAS
>>206
>>227をC++に移植
外部ﾘﾝｸ:ideone.com
231: デフォルトの名無しさん [sage] 2024/02/11(日) 15:34:27.52 ID:3wEOIMb0(1) AAS
>>206 octave
外部ﾘﾝｸ:ideone.com
>>206 octave
外部ﾘﾝｸ:ideone.com
232: デフォルトの名無しさん [] 2024/02/11(日) 20:38:42.50 ID:v64KP9lJ(1) AAS
>>206
>>230をDで書くと
外部ﾘﾝｸ:ideone.com
になるが、switch case 0, 1, 2の場合も3の場合と同じ処理にすると、効率は落ちるもののかなり短くできる。
外部ﾘﾝｸ:ideone.com
233: 223 [sage] 2024/02/12(月) 23:45:12.86 ID:ix8w7wd+(1) AAS
>>206 octave
外部ﾘﾝｸ:ideone.com
・組み合わせつくって集合のペアごとに調べることをやめた
・集合間で重複する要素に着目して集合を減らすようにした
>>223
g.(a).map {|set| set.map &h.invert.method(:[])}じゃなくて単に
g.(a).map {|set| h.keys.values_at *set}で良かった
上下前次1-新書関写板覧索設栞歴
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.043s