プログラミングのお題スレ Part10

**デフォルトの名無しさん** · 2018/01/01(月) 11:15:04.40

プログラミングのお題スレです。

前スレ
プログラミングのお題スレ Part9
https://mevius.5ch.net/test/read.cgi/tech/1480579110/

【出題と回答例】
1 名前：デフォルトの名無しさん
　　お題：お題本文

2 名前：デフォルトの名無しさん
　　>>1 使用言語
　　回答本文

【ソースコードが長くなったら】 (オンラインでコードを実行できる)
http://ideone.com/
http://codepad.org/
http://compileonline.com/
http://rextester.com/runcode
http://runnable.com/
http://code.hackerearth.com/
http://melpon.org/wandbox
https://paiza.io/

宿題は宿題スレがあるのでそちらへ。

**123 今北産業** · 2018/01/28(日) 18:49:59.25

>>131、ｽﾏｿ誤記があった
誤 java
正 C++

◆QZaw55cn4c · 2018/01/28(日) 19:09:24.53

>>131
了解

>>131
＞長いな
うん、ライブラリを知らずいちいち書いてるから長くなるのも止むを得ない

◆QZaw55cn4c · 2018/01/28(日) 19:13:55.34

>>128
出題者は私じゃありません

**愛知人** · 2018/01/28(日) 19:15:15.98

ここまでに出てるやつって>>130のアルゴリズム使ってるやつある？

**123 今北産業** · 2018/01/28(日) 19:24:07.36

>>133
"ABCDEFG", "Hello, World!" は、藻前さんのエンコード結果であってるとおもうよ

**111** · 2018/01/28(日) 20:43:46.22

>>135
最初それで作ろうかと思ったが複雑になりそうだったので止めた。
結局レジスタ代わりの変数に8bitシフトして6ビット取り出すとか、
6ビットシフトして8ビット超えたら取り出すという方式にした。

>>127
読み取れなかった? C言語でも作ってるので気長に待ってて。
多分そちらはなんとなく分かるだろうと思う。

**124** · 2018/01/28(日) 21:00:32.08

>>111 rust
https://ideone.com/sxPlp1
・ちょっと部分的に整理
・>>127で指摘してもらって気付いたバグを修正

◆QZaw55cn4c · 2018/01/28(日) 22:03:30.34

お題：>>111 の系
1) base64 を実装せよ
2) base64 は 6 ビットごとに一文字を当てるが、これを①5ビットごとに、あるいは②3ビットごとに割り当てるように変更せよ
変換表は base64 の部分とせよ
base64 の実装コードから最小元の変更で済むように構成せよ
※デコード時の '=' の出力仕様は実装しなくともよい

**デフォルトの名無しさん** · 2018/01/28(日) 23:14:42.76

>>139 rust
https://ideone.com/LEjBFW

**デフォルトの名無しさん** · 2018/01/28(日) 23:19:10.39

>>139
なんでコンピュータで奇数扱おうとするんですか～。
個人的にはだけど、すごい気持ち悪い。
ぴったりはまらないから何個も変数マタグし。

**デフォルトの名無しさん** · 2018/01/28(日) 23:22:37.93

>>137
>>122は、3バイトを4分割してるよ。逆変換もしてるよ。
6bit*4で24ビットなのでちょうど3バイトだよ。
まぁ、エラー処理あってるかよくわかってないけど。

**140** · 2018/01/29(月) 00:30:27.71

>>139
https://ideone.com/MOd0La
・'='追加のバグ修正

**今北産業** · 2018/01/29(月) 01:26:52.75

>>139 Perl5
https://ideone.com/82DbUR

幅が5や3のときに=を何個補完すべきか明確じゃなくなるので
=の追加は省いています。

**今北産業** · 2018/01/29(月) 01:52:00.25

>>144　バグってた。orz
6行目の$W-2は$W-1でなければならない。
この間違いにより幅5のときのABCDEFGのエンコード結果の末尾が1カラム欠ける。

修正版
>>139 Perl5
https://ideone.com/KNxABI

**愛知人** · 2018/01/29(月) 01:53:47.97

ideoneは後から編集できるんだしコッソリ書き換えとけばよくね

**デフォルトの名無しさん** · 2018/01/29(月) 01:59:30.35

お題。
暇な人向け。
ボゴソートを実装し、処理が終わるか確認せよ。
https://ja.wikipedia.org/wiki/ボゴソート
発展お題として大体どれくらいの要素数までが現実的か確認せよ。

サンプル：https://ideone.com/Fb8x80

◆QZaw55cn4c · 2018/01/29(月) 12:23:05.32

>>147
https://ideone.com/WGZ2WG
12文字が限界でしたか…

**愛知人** · 2018/01/29(月) 15:58:00.28

>>111
今更だけど
C言語
https://ideone.com/80cjOY

**デフォルトの名無しさん** · 2018/01/30(火) 00:03:42.09

>>148
参加してくれてありがとう。
俺のお題は不人気なんだよね。
どうでもいいお題ばかりだからだけど。

◆QZaw55cn4c · 2018/01/30(火) 00:11:56.31

>>150
いえいえ、一度やってみたかったのです、みてのとおり手数はわずかですみました
コードを書くのは楽しいのに、そのネタがみつからず状況で渡りに船でした
それに私のお題も不人気で、それは過去ログが示しています

**111** · 2018/01/30(火) 00:35:59.04

>>111をC言語で作ってみたものの、open_memstream()が使えるサイトが見つからず、
結局似たような機能ものを自作してしまいかなり長くなってしまった。orz
https://paiza.io/projects/9mjG00te6x5pMJTZzPF3Dw

直接 FILE * から一文字つづ読みながら変換した方が小さくなるな。

**愛知人** · 2018/01/30(火) 00:49:23.55

>>147
C言語
https://ideone.com/02P7xy

11個でした。

**デフォルトの名無しさん** · 2018/01/30(火) 00:58:03.51

>>153
thank you for playing!
まぁ、乱数の質とかが問題になるような気がするのでその分布だときつそうだ。

**111** · 2018/01/30(火) 01:05:16.85

>>139
ほんのちょっと変更したらできた。ビット数変更は最初の B64BIT の定義を変えるだけ。今は3ビットになってる。
https://paiza.io/projects/aGQZdP5PKfNESdBXh3tHyw

**今北産業** · 2018/01/30(火) 01:49:35.30

>>149
こういう実装は個人的に好みだな。
ｵﾚがCで書くならこれに近いイメージ。
encodeMap decodeMapはまったくの静的定数テーブルでもいいけど、
初期化コードで設定すればステートメントが減って見た目もすっきりする
かもね…

**愛知人** · 2018/01/30(火) 02:17:30.68

無駄な動作が一切ないもんな（多分）

**111** · 2018/01/30(火) 12:37:43.63

メモリを多く使って高速化するか、それとも使わずに普通に動かすかといった違いかな。
この程度のメモリは今時の普通のPCだと全く問題にならないが、組み込みでメモリがちょっとしか使えないとか、環境に応じて使い分ける必要がある。

**愛知人** · 2018/01/30(火) 13:14:13.97

定数配列はフラッシュメモリに置いたままにできるからメモリ関係ないぞ

**デフォルトの名無しさん** · 2018/01/30(火) 13:16:52.58

これやってる人いる? N=41とか難しいやつだったような。

自然数Nに対して、平面上の円でその円周上の整数点がちょうどN個となる円の最小半径を求めよ。

**111** · 2018/01/30(火) 13:56:11.56

>>160
問題の意味がわからない。

**デフォルトの名無しさん** · 2018/01/30(火) 14:25:08.29

XY平面上に適当なサイズの円をおいたとき、
その円周上でX座標、Y座標もともに整数となる点の個数が定まる。
たとえば、中心(0,0)で半径1の円ならば、整数点は4のはず。(1,0) (-1,0) (0,1) (0-,1)

**デフォルトの名無しさん** · 2018/01/30(火) 14:43:14.34

しかし、x^2 + y^2 = 1
が4点の最小半径ではなく、

(x-0.5)^2 + (y-0.5)^2 = 0.5　
は、(0,0) (1,0) (0,1) (1,1)で成り立つのでこっちのほうが小さい半径。

**デフォルトの名無しさん** · 2018/01/30(火) 17:06:36.99

その条件だとN=1の時の正しい答えが分からないので俺には無理だ

**デフォルトの名無しさん** · 2018/01/30(火) 18:24:23.70

1はさすがに除外だろ
適当な3点で円作って、交点の座標調べていくくらいしか思いつかんわ

**愛知人** · 2018/01/30(火) 18:40:10.88

お題:IPアドレスのリスト(改行区切り)をホスト名のリストに変換せよ

**愛知人** · 2018/01/30(火) 19:02:43.92

ネットつながるのパいざだけでワロタ

**111** · 2018/01/31(水) 01:37:53.83

>>166
Java
https://paiza.io/projects/gmdnr--vMsOdJg4mgYPVWg

**デフォルトの名無しさん** · 2018/01/31(水) 02:49:17.63

>>166
Perl
https://paiza.io/projects/i-FzOG_EexLNXTX2_QYEpA

**デフォルトの名無しさん** · 2018/01/31(水) 03:29:20.85

C++

**デフォルトの名無しさん** · 2018/01/31(水) 03:30:11.21

う。C++には標準ネットワークライブラリが無いので環境依存になる。
そして俺はLINUXしらない。

**デフォルトの名無しさん** · 2018/01/31(水) 04:17:16.49

nodejs
var odai = `
216.58.197.14
98.139.180.180
`;
var out = [];
odai.trim().split`\n`.forEach(ip => dns.reverse(ip, (err, hostnames) => {
out.push(hostnames[0]);
}));
out.join`\n`;

**デフォルトの名無しさん** · 2018/01/31(水) 13:04:01.66

名前の解決には DNS NIS WINS hostsファイルの4種類で行うこと
という条件付けたらどの言語使うのが簡単なんだろう

**デフォルトの名無しさん** · 2018/01/31(水) 14:12:55.10

>>160
昔やってた（コード貼らずに計算結果だけスレに貼ってた）よ。
2年半くらい前の書き散らしたコード、見てもよーわからんくなってる。

**デフォルトの名無しさん** · 2018/02/02(金) 00:14:41.12

>>147
Rubyで。
N=11が限界みたいだ。

N = 11
org_ary = (1..N).to_a
wrk_ary = org_ary.dup

cnt = 0
while (wrk_ary = wrk_ary.shuffle) != org_ary
cnt += 1
end
p cnt

# 実行結果
# ruby odai-10-147.rb 17.10s user 0.15s system 96% cpu 17.906 total
# 22093802
# ruby odai-10-147.rb 35.19s user 0.27s system 98% cpu 35.950 total
# 6677838
# ruby odai-10-147.rb 10.64s user 0.11s system 96% cpu 11.170 total
# 26014838

**デフォルトの名無しさん** · 2018/02/02(金) 07:34:54.92

>>147 ruby
1分以内ならN=12が限度かと

N=ARGV.first.to_i
m=(1..N).reduce(:*)
p (1..1.0/0).each{|i|rand(m).zero?&&(break i)}

**デフォルトの名無しさん** · 2018/02/02(金) 11:55:37.20

>>175-176
どちら様も参加してくれてありがとう。サンキュー。

>>175 の試行回数は参考になるな。
N=12位が現実的か。ふーん。
ベンチマーク的に言って結構できるなーって感想だけど、実用には程遠いな。
コンピュータもまだまだやな。

面白いね。

**111** · 2018/02/06(火) 18:09:43.58

お題：数独を解くプログラム

問題の入力は凝ってもいいけどテキストをファイルや標準入力から読んでもよい。
テキストファイルで数が分かっている所はその数字、分かっていない所は*にして9桁9行で入れとくとかね。

これもほんのちょっと難しいだけの初心者向けお題かな。

**デフォルトの名無しさん** · 2018/02/06(火) 19:36:44.66

ＮＰ完全問題って回答が似たり寄ったりになるよね

**デフォルトの名無しさん** · 2018/02/06(火) 19:38:56.97

うーん、SMTソルバ！w

**デフォルトの名無しさん** · 2018/02/06(火) 23:49:05.88

>>178
過去ログに俺の書いたやつあるよ。

**デフォルトの名無しさん** · 2018/02/07(水) 10:41:58.75

数独は、各マスに候補となる数字のテーブル作って、縦横に重複してる数字を消して行き、残った一つを確定するって作業を繰り返すだけの処理で完成さ。

**デフォルトの名無しさん** · 2018/02/07(水) 11:03:49.05

>>182
それで済むのは初級問題だけ

**デフォルトの名無しさん** · 2018/02/07(水) 11:12:34.29

https://ideone.com/mtcLac
昔書いたやつ。発掘してきた。もう覚えてないからバグあっても治せん。

**デフォルトの名無しさん** · 2018/02/07(水) 17:52:17.81

>>178 Ruby
https://ideone.com/YRslIS

**デフォルトの名無しさん** · 2018/02/07(水) 21:06:46.20

>>185ってめっちゃ短いけどどういうアルゴリズムなん？

**デフォルトの名無しさん** · 2018/02/07(水) 21:08:13.86

buruto fosu

**デフォルトの名無しさん** · 2018/02/07(水) 22:16:04.98

>>183
上級問題対応するなら、仮盤面作って総当たり戦で解が出るまで繰り返してあげればいいんじゃね？
当然、あるマス目に入る数字は幾つかに絞られてるから無駄にはならない。

**デフォルトの名無しさん** · 2018/02/07(水) 22:19:58.39

>>186
3×3のマス目には1から9の値は一つしか入らないからってのと、
縦横全体も数字は重複しないってルールだけでぶん回してる感じ？

**111** · 2018/02/08(木) 03:00:07.95

>>178
自分で作ってみた。Kotlin。
https://paiza.io/projects/xnR6_Wgd7gKcC1jW__QBxw
やり方は同じだな。再帰で総当たりしてるだけ。

というか、これに関して他にもっと良い方法あるのかな?

**111** · 2018/02/08(木) 03:10:18.15

編集ミスして消し忘れた部分を修正したりほんのちょっと記述を変えて無駄をなくした。

**デフォルトの名無しさん** · 2018/02/08(木) 12:00:24.59

>>186
すでに指摘されてるけど、縦横3*3で重複無しルールにのみ基づき全探索
ttps://gigazine.net/news/20100822_hardest_sudoku/
上にある世界一難しい(らしい)数独も3秒くらいで解けるし余計な枝刈りは不要かなと

**デフォルトの名無しさん** · 2018/02/08(木) 14:18:21.56

>>184 つかって　>>192　解いてみた。
i6700のスカイレークでリリースビルドで2秒くらいやった。
解法がバックトラックで十分だからバリエーションでないね。

**デフォルトの名無しさん** · 2018/02/09(金) 12:41:19.10

find!!
145327698
839654127
672918543
496185372
218473956
753296481
367542819
984761235
521839764

答えこれのやつでしょ？

core2のノートで>>184の使って0.154秒だったけど
6年前に自分が書いたやつでもやってみたら0.011秒だった
それ遅すぎるような気がするけどこっちが何か間違ってるのかな

**デフォルトの名無しさん** · 2018/02/09(金) 16:11:55.97

>>194
さぁ、>>184が色々余計なことしてる可能性はなくもない。
答え出ればいいだけだだから余計な枝狩りやってるかも。

**デフォルトの名無しさん** · 2018/02/09(金) 16:15:21.82

あ、ちがうわ。

>>194
VS上でやってるから余計なプロセス動いてたかも。ファントム関係ってことはないと思うけど。

**デフォルトの名無しさん** · 2018/02/09(金) 16:29:04.59

https://ideone.com/NqxATw
これ見る限りうちがおかしいな。なんでだろ。

**111** · 2018/02/09(金) 21:22:00.28

やっぱ数独はここの常連には簡単すぎたかな。
じゃあ枢動の問題作るプログラムはどうかな？
もちろんちゃんと解ける問題じゃないとだめだよw

**デフォルトの名無しさん** · 2018/02/09(金) 21:23:02.19

ごめん。変換ミス。数独の問題な。

**デフォルトの名無しさん** · 2018/02/09(金) 21:24:13.83

>>198
適当に数字置いてソルバーに解かせて歯抜けにすればいい。

**111** · 2018/02/09(金) 21:29:08.23

>>200
まあそうなんだよな

**デフォルトの名無しさん** · 2018/02/09(金) 21:42:40.35

解が複数あるかどうかまで調べなあかんやろ？

**デフォルトの名無しさん** · 2018/02/09(金) 21:47:43.12

>>202
自分のソルバーは重解対応。

**デフォルトの名無しさん** · 2018/02/09(金) 23:29:19.09

理詰めで解ける難易度の高い問題を作るのは難しいんじゃないかな？

**デフォルトの名無しさん** · 2018/02/09(金) 23:34:37.03

理詰めっていってもよくある解放は特殊な場合の背理法に過ぎないからなぁ
背理法アリなら何でも解けちゃうしね

**デフォルトの名無しさん** · 2018/02/10(土) 01:03:55.15

https://ideone.com/4gJj7c
C++。やっつけで作ってみた。
ソルバー指向の出題システム。答え合わせ付き。
なんか若干バグってる気がする。
ユニークしてないのになんか答えの数が合わない。

**デフォルトの名無しさん** · 2018/02/10(土) 01:14:04.93

あ、修正した。

**デフォルトの名無しさん** · 2018/02/10(土) 01:15:50.01

あれ？二度手間してるか？

**デフォルトの名無しさん** · 2018/02/10(土) 01:26:03.91

バージョンアップ。これで完成。

**デフォルトの名無しさん** · 2018/02/10(土) 01:51:14.02

https://ideone.com/A2t0QO
C++。出題部を複雑化したバージョン。
もう手を入れるところないやろ。

**デフォルトの名無しさん** · 2018/02/10(土) 02:20:45.32

長くなっちゃった。。。そーりー。

**デフォルトの名無しさん** · 2018/02/10(土) 17:24:55.37

>>198
>>210 みたいなのはおｋなの？
反応なくて寂しい・・・。

**デフォルトの名無しさん** · 2018/02/10(土) 17:53:13.03

難易度とか、手で解いたときの楽しさみたいな設定

**デフォルトの名無しさん** · 2018/02/10(土) 17:54:30.37

>>213
それは、俺自力で数独解いたことないから手加減がわからない。

**デフォルトの名無しさん** · 2018/02/10(土) 18:15:22.72

っていうかさ、評価聞きたいのにさらに欲求出されたらやる気なくなる。
守銭奴か。

**デフォルトの名無しさん** · 2018/02/10(土) 18:52:43.33

つ強リンク弱リンク

**デフォルトの名無しさん** · 2018/02/10(土) 19:09:24.36

ん？

**デフォルトの名無しさん** · 2018/02/10(土) 19:12:44.97

難易度で言うなら、数字消すときに何個消すかで対応できると思う。
初心者用に5個消すとか。楽しさとかは俺が理解してない。

**デフォルトの名無しさん** · 2018/02/10(土) 19:17:06.37

守銭奴の意味くらい調べて使えよ
あと、解いたこともないパズルを作るときに難易度とかなんの疑問もわかなかったのか

**デフォルトの名無しさん** · 2018/02/10(土) 19:18:52.78

あと評価は、難易度設定機能がないから低評価だ

**デフォルトの名無しさん** · 2018/02/10(土) 19:21:18.78

>>220
そこまで言うなら見本見せて。
おれはプログラムのお題を解いただけだからな。

**デフォルトの名無しさん** · 2018/02/10(土) 19:33:36.98

もしくは難易度というものを俺がわかるように説明して。

**デフォルトの名無しさん** · 2018/02/10(土) 20:31:11.58

遅い。待ちくたびれた。待ちくたびれた。

**111** · 2018/02/10(土) 20:44:37.27

>>212
え？いいんじゃないの？ていうか、これといった制限もないし、基本的に自分でこれで良いと思えばそれで良い。
自分で気に入らないならまた作り直せば良いじゃない。誰かに依頼されてやてる仕事じゃないんだし誰かと競っているわけでもないし。
自己満足を徹底的に追及すれば良い。

**デフォルトの名無しさん** · 2018/02/10(土) 20:48:42.43

>>224
ほい。了解。サンキュー。

**デフォルトの名無しさん** · 2018/02/10(土) 20:52:13.46

後は、>>220が自己評価マックスの製品を見せてくれるだけだな！

**デフォルトの名無しさん** · 2018/02/10(土) 21:04:40.26

難度設定するとなると一般的な解法を実装して逆算的に作っていくしかないのかな
構成的に問題作るのは無理だと思うので

**デフォルトの名無しさん** · 2018/02/10(土) 21:28:50.36

>>227
難易度とは何ぞやってところがまず曖昧だからね。
自分のソルバーはまず正解を作って数字を消してるんだけど、消す数を調整しても難易度には寄与するし。

**デフォルトの名無しさん** · 2018/02/10(土) 21:31:17.41

40個くらい消したあたりが一番やりがいあるとおもう。

恥人 · 2018/02/10(土) 21:52:20.78

顔真っ赤ｗ

**111** · 2018/02/10(土) 22:09:29.40

よくわからんのだが数独の初期配置の最小個数は17個と書いてある。
https://ja.wikipedia.org/wiki/%E6%95%B0%E7%8B%AC#%E6%9C%80%E5%B0%91%E5%80%8B%E6%95%B0
ということで17個残したやつは難易度が最も高いってことにしていいんじゃないかな。