プログラミングのお題スレ Part22 (854ﾚｽ)
上下前次1-新
抽出解除 ﾚｽ栞
ﾘﾛｰﾄﾞ規制です｡10分ほどで解除するので､他のﾌﾞﾗｳｻﾞへ避難してください｡
133(1): デフォルトの名無しさん [sage] 2023/10/17(火) 07:02:57.86 ID:InaHR8fg(1) AAS
>>132132(1): デフォルトの名無しさん [] 2023/10/16(月) 08:51:26.93 ID:kgcCjrnK(1) AAS
1)
BY
RG
2)
RG
BY
3)
GR
YB
1-3を回転対称で同じとみなせるグループと線対称で同じとみなせるグループに分類せよ
4色を2x2の升にランダムに一つづつ配置して4x3x2通りのパターンを作成し
それぞれを上の基準でグループ分けせよ
Ruby
外部ﾘﾝｸ:ideone.com
212: デフォルトの名無しさん [sage] 2024/02/02(金) 23:24:45.86 ID:UezRkqGy(4/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
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
}
233: 223 [sage] 2024/02/12(月) 23:45:12.86 ID:ix8w7wd+(1) AAS
>>206 octave
外部ﾘﾝｸ:ideone.com
・組み合わせつくって集合のペアごとに調べることをやめた
・集合間で重複する要素に着目して集合を減らすようにした
>>223223(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(:[])}
}
g.(a).map {|set| set.map &h.invert.method(:[])}じゃなくて単に
g.(a).map {|set| h.keys.values_at *set}で良かった
517(1): デフォルトの名無しさん [sage] 2025/01/31(金) 21:55:55.86 ID:mLWOFznj(1/2) AAS
>>514514(2): デフォルトの名無しさん [] 2025/01/31(金) 13:46:22.55 ID:+tPQNmsr(1) AAS
このスレでいいのかわからんのだけど
Rust勉強中なんだがメモリ安全性の恩恵を受けやすいなんかしらかのプログラムを書こうと思ってるんだがなにかいいお題はあるか？
言語処理系は大体作ってるのでそれ以外で頼む
Rustはメモリのデータ競合もデータ参照競合も全てコンパイルエラーにしてくれるから間違えようがないね
他の普通の言語だと実行して問題発生に気付いて調査して頑張ってようやく競合が原因だと判明して間違えていたことがわかるから開発効率の悪さとして差が現れるけど
Rustは実行前にその種のミスのデバッグまで全て終えてしまう感じ
527: デフォルトの名無しさん [sage] 2025/02/01(土) 23:00:12.86 ID:FwGLv5NU(2/2) AAS
Rustのメモリ安全性を確認するためにプログラム書きたいんでしょ、だったら循環リストをフルスクラッチするしかないよね
556: 警備員[Lv.19] [] 2025/02/10(月) 13:21:24.86 ID:g+w4FSG9(1) AAS
>>510510(21): デフォルトの名無しさん [] 2025/01/30(木) 21:27:24.39 ID:te1+SH0T(1) AAS
お題
ソース文字列と検索文字列が入力されます
検索文字列の文字をすべて含むソース文字列の部分文字列のうち
一番短い部分文字列を出力してください
DHBICEJAFG EIC → ICE
FDGJHCBIEA EIC → CBIE
FBHDCIJGEA EIC → CIJGE
JDIBGHCEAF EIC → IBGHCE
JBCIAGDHEF EIC → CIAGDHE
EJFBCAGIHD EIC → EJFBCAGI
IADCGJFBEH EIC → IADCGJFBE
IDFHBJGAEC EIC → IDFHBJGAEC
Kotlin
出来たことは出来たが、もっと簡単に出来そうな気がしてきた。
外部ﾘﾝｸ:paiza.io
707: デフォルトの名無しさん [] 2025/03/25(火) 23:43:24.86 ID:V/NXIH+S(1) AAS
>>704>>699699(2): デフォルトの名無しさん [] 2025/03/21(金) 20:49:29.98 ID:uwhksDTb(1) AAS
>>697-698
Rustはよく知らないが、mainのforループ内をprintln!("{}", a);に置き換えれば解が表示されるんだよね?
実行結果を>>685で述べたC++プログラムのものと照合したら167個の解すべてが一致した。見事正解!
実行時間はC++プログラムの数倍かかるようだが、ideoneでの実行時間も見たいので載せて下さい。
では最適化オプションを付けてrustc -O a.rsでコンパイルした。最適化なしでは
ありの4.6倍くらい掛かった。もしやと思ってコンパイラをアップデートしてみたら、
実行時間は約3分の1に激減し、>>700700(4): デフォルトの名無しさん [] 2025/03/23(日) 23:00:51.13 ID:pi1bImlR(1) AAS
>>680から1週間経ったので解答例を掲載
>>685を書いたときに作ってあった2つのC++プログラム
外部ﾘﾝｸ:ideone.com
外部ﾘﾝｸ:ideone.com
1番目ではsolve関数の再帰呼び出しの対象とするx[p]の下限と上限を線形探索するが、
2番目では二分探索する。要素数10では二分探索の効果は薄いと思いきや、大分速くなった。
2番目を読み返していたらバグを発見してしまった。i = N - 1のとき63行目のa[i + 1]はa[N]となり
配列の添字範囲外アクセス。0との比較だけだし、if文の評価がどっちでも以降の処理は結局同じだから、
実害も解への影響もないが、厳格さが必要ならif ((i + 1 < N ? a[i + 1] : 0) >= 0) {と書き換えるべきだな。
実行時間への影響は無視できる。
それぞれのPowerShellへの移植版
外部ﾘﾝｸ:ideone.com
外部ﾘﾝｸ:ideone.com
完全な逐語訳ではなく、PowerShellで書くと遅くなったり煩雑になったりする箇所は適宜改変した。
15桁以下の場合は64ビット整数でも桁溢れしないので、BigIntの代わりにInt64を使えば少し速くなる。
の1番目と大差ない1.3倍ほどに収まった。
Rustの古いコンパイラ（5年前のもの）がこんなに低性能だったとは…
773: デフォルトの名無しさん [sage] 2025/07/25(金) 21:30:28.86 ID:Z69qH9vG(1) AAS
>>771771(22): デフォルトの名無しさん [sage] 2025/07/25(金) 12:30:11.02 ID:CjDQVF2B(1) AAS
【問題】
整数のリストが与えられたとき、そのリストを昇順に安定ソートした時の各要素のインデクス（0開始）を対応させたリストを作成せよ
【例】
入力： 1 100 10 10000 1000
出力： 0 2 1 4 3
入力： 3 1 4 1 5 9 2
出力： 3 0 4 1 5 6 2
入力： 0 1 0 1 0 1 0 1
出力： 0 4 1 5 2 6 3 7
実際に必要になって実装したけどスマートな方法があったら知りたい
C++ 特にひねりは無い
外部ﾘﾝｸ:ideone.com
787: デフォルトの名無しさん [] 2025/07/31(木) 18:54:11.86 ID:cLL+G38O(2/2) AAS
ち、勘が鈍った。＞＞もつけ間違えるし、sage忘れるし。
上下前次1-新書関写板覧索設栞歴
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.036s