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

1デフォルトの名無しさん2018/04/24(火) 20:45:14.49ID:ZY7R7Sru
プログラミングのお題スレです。

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

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

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

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

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

481デフォルトの名無しさん2018/05/19(土) 01:06:44.60ID:YJKUc9vG
>>478 です
とりあえずこれだけ出来ました
4770でシングルスレッドのC++で15分くらい
半径を倍にすると16倍くらいは時間がかかりそうなので
マルチスレッド&アセンブラ&AVXでガシガシに最適化したくらいじゃ
大して検索範囲は増えなそう
何かアイデアがないか考え中
----
3 : r=1.178511
4 : r=0.707107
5 : r=5.892557
6 : r=2.500000
7 : r=23.890677
8 : r=1.581139
9 : r=15.320647
10 : r=12.500000
11 : r=57.536370
12 : r=3.535534
13 : r=111.621856
14 : r=62.500000
15 : r=76.603235
16 : r=5.700877
18 : r=32.500000
20 : r=17.677670
24 : r=12.747549
28 : r=88.388348
32 : r=23.505319
36 : r=45.961941
40 : r=63.737744
48 : r=52.559490
64 : r=117.526593

482デフォルトの名無しさん2018/05/19(土) 01:35:39.77ID:/t1Y5z0r
ピタゴラス素数(4n+1型の素数、5、13など)は2乗和で表わせて。
逆に、2乗和(X^2+Y^2)は、2とピタゴラス素数の積の表わせる、もしくはこの問題を考える上でそれだけに限定していいとおもってる。

2^i * 5^j * 13^k * ・・・・をピタゴラス合成数と名付けると。
X^2 + Y^2 = ピタゴラス合成数、の解とその個数は比較的カンタンに求まる。

それを利用して、拡大(縮小)と並行させたやつで、最小半径を与えるのは全て表せるはず。

具体的には、上の解が求まっていれば、
(mx + a)^2 + (my +b)^2 = ピタゴラス合成数、の解と個数もそれなりの低コストでもとまる。
mの剰余を考えれば、解があるaとbの範囲も限定できる。

483デフォルトの名無しさん2018/05/19(土) 01:54:04.51ID:YJKUc9vG
ノーヒント、全て自力で求めようと思ってたんだけど
だから競争って

まあいいや
使えそうなら使わせていただきます

484デフォルトの名無しさん2018/05/19(土) 03:42:04.50ID:/t1Y5z0r
ピタゴラス素数は2乗和であらわせて。
(a^2 + b^2) (x^2 + y^2) = (ax + by)^2 + (bx - ay)^2 が常に成立するので、

ピタゴラス素数と 2 = 1^2 + 1^2 の積で、新たな2乗和の式が作り出せる。
この式から、解とその個数も求まるはず。

しかし、これがわかっても最小値を求めるのは簡単ではないとおもう。かなりの計算量がいるはず。

485デフォルトの名無しさん2018/05/19(土) 03:53:23.91ID:/t1Y5z0r
z = x + yiという複素数でいうと、このノルムは|

486デフォルトの名無しさん2018/05/19(土) 03:56:11.86ID:/t1Y5z0r
z = x + yiという複素数でいうと、ノルムは|z|^2 = x^2 + y^2 であって
|z||w| = |zw|を満たすので、
>>484の式は、新たな複素数 zwを作り出すことと一緒。

487デフォルトの名無しさん2018/05/19(土) 07:41:40.76ID:b7x1I7X/
お題

ケブンリッジジェネレータ

知らない人のために解説すると、人間の認識力の問題で単語の最初と最後が正しいと途中の文字順序が違っていても正しい単語と見間違えるというのがある。
例えば「よこうそ」は「ようこそ」と見間違える。「およはう」は「おはよう」と見間違える。(これは違うと分かっていても見えてしまうという、空耳アワーの歌みたいでもある)。

以前2chでこのことについてケブンリッジで発見されたというような内容の文章がコピペされて広まり一時期有名になりそれ用の変換をするケブンリッジジェネレータのページ(JavaScriptで作られてたと思う)が作られたりもしていた。
今はもうないようだが今回のお題はこれである。つまり、入力された単語の最初と最後はそのままで途中の文字順序をランダムに入れ替えた結果を出力する。
日本語の文章は普通は単語と単語の間にスペースがないが、これについては処理を簡単にするためにスペースありで入力された文章しか正常に処理しないということにして良い。

488デフォルトの名無しさん2018/05/19(土) 08:22:43.57ID:VUe7Kazw
>>487 Ruby
str = <<~EOT
Alice was beginning to get very tired of sitting by her sister on the bank,
and of having nothing to do: once or twice she had peeped into the book
her sister was reading, but it had no pictures or conversations in it,
'and what is the use of a book,' thought Alice 'without pictures or
conversations?'
EOT

puts str.gsub(/(?<=\b\w)\w*(?=\w\b)/){|m| m.chars.shuffle.join}
#=>
Aclie was bngneniig to get very terid of sntitig by her seistr on the bnak,
and of hnvaig nnthoig to do: ocne or twcie she had ppeeed into the book
her sitser was rniadeg, but it had no piteucrs or cinsoentravos in it,
'and waht is the use of a book,' tohught Aclie 'wtihuot pricetus or
coenrovanstis?'

489デフォルトの名無しさん2018/05/20(日) 12:39:54.67ID:fjnXxBFP
>>477
これってその条件内なら普通に最適解(圧縮度)出せる方法とか存在する?

490デフォルトの名無しさん2018/05/20(日) 12:52:52.72ID:+POqszb4
全通りやれば良い

491デフォルトの名無しさん2018/05/21(月) 12:42:55.71ID:DBB0b89i
>>487 Squeak/Pharo Smalltalk

| input nonLetters |

input := 'Alice was beginning to get very tired of sitting by her sister on the bank,
and of having nothing to do: once or twice she had peeped into the book
her sister was reading, but it had no pictures or conversations in it,
''and what is the use of a book,'' thought Alice ''without pictures or
conversations?'''.

nonLetters := input reject: #isLetter.
(input findTokens: nonLetters keep: nonLetters) inject: '' into: [:acc :token |
(token first isLetter and: [token size > 1])
ifTrue: [acc, (token first: 1), token allButFirst allButLast shuffled, (token last: 1)]
ifFalse: [acc, token]
]

"=> Ailce was beingnnig to get vrey tierd of sttinig by her seitsr on the bank,
and of hvanig nohintg to do: once or twice she had peeepd into the book
her seitsr was riaendg, but it had no piercuts or coitnevnarsos in it,
'and what is the use of a book,' thuoght Alice 'wtiohut ptriecus or
ctnaseinroovs?' "

492デフォルトの名無しさん2018/05/21(月) 18:51:56.06ID:VDVE1q4f
みんな日本語スルーしててワロタw

493デフォルトの名無しさん2018/05/21(月) 20:02:50.47ID:I0TPptnw
>>482
やってみたけど、
馬鹿正直に検索するのと大して変わらんね
半径1000以下を全て検索するのは厳しそう

円周を検索するする昔ながらのアルゴリズムは優秀だ

494デフォルトの名無しさん2018/05/21(月) 21:16:17.93ID:FH7zIseK
円周を検索するする昔ながらのアルゴリズムとは?

495デフォルトの名無しさん2018/05/21(月) 21:24:09.15ID:dve0ZlFL
>>487 Squeak/Pharo Smalltalk 日本語文章処理例

| input nonLetters |

input := '以前2ch で このこと に ついて ケブンリッジ で はっけん された と いうような ないよう の ぶんしょう が コピペ されて ひろまり
いちじき ゆうめい になり それよう の へんかん を する ケブンリッジ ジェネレータ の ページ(Java Script で つくられ てたと 思う)が つくられ たりも していた。
今 は もうない ようだが こんかい の お題 は これ である。つまり、にゅうりょく された 単語 の さいしょ と 最後 は そのまま で とちゅう の もじじゅんじょ を ランダム に いれかえ た 結果 を しゅつりょく する。
にほんご の ぶんしょう は 普通 は 単語 と 単語 の 間 に スペース が ないが、これ に ついては 処理 を かんたん に するため に スペース あり で にゅうりょく された ぶんしょう しか せいじょう に 処理 しない ということ に してよい。'.

nonLetters := input reject: #isLetter.
(input findTokens: nonLetters keep: nonLetters) inject: '' into: [:acc :token |
(token first isLetter and: [token size > 1])
ifTrue: [acc, (token first: 1), token allButFirst allButLast shuffled, (token last: 1)]
ifFalse: [acc, token]
]

"=> 以前2ch で このこと に ついて ケブリンッジ で はっけん された と いうような なよいう の ぶんょしう が コピペ されて ひろまり
いちじき ゆうめい になり そよれう の へかんん を する ケンブッリジ ジレェーネタ の ページ(Jvaa Spcirt で つくられ てたと 思う)が つくられ たりも しいてた。
今 は もうない ようだが こんかい の お題 は これ である。つまり、にりゅうょく された 単語 の さしいょ と 最後 は そのまま で とちゅう の もゅんじじじょ を ラダンム に いかれえ た 結果 を しょゅつりく する。
にほんご の ぶんしょう は 普通 は 単語 と 単語 の 間 に スペース が ないが、これ に ついては 処理 を かんたん に すたるめ に スーペス あり で にゅうりょく された ぶしんょう しか せょじいう に 処理 しない といこうと に してよい。"

496デフォルトの名無しさん2018/05/21(月) 21:36:05.44
>>495
ランダムに入れ替えるのはいいけど、元の単語と同じ並びは排除しないと期待外れの出力になるね

497デフォルトの名無しさん2018/05/21(月) 22:08:38.80ID:GTjH0Q6M
完全にランダムなんだから、結果が同じ並びでもそのまま出力するのが筋だろ
変更するなら日本語の文章の方だ

498デフォルトの名無しさん2018/05/21(月) 22:24:50.52ID:dve0ZlFL
>>487 Squeak/Pharo Smalltalk 同じ並びは排除

| input nonLetters |

input := '以前2ch で このこと に ついて ケブンリッジ で はっけん された と いうような ないよう の ぶんしょう が コピペ されて ひろまり
いちじき ゆうめい になり それよう の へんかん を する ケブンリッジ ジェネレータ の ページ(Java Script で つくられ てたと 思う)が つくられ たりも していた。
今 は もうない ようだが こんかい の お題 は これ である。つまり、にゅうりょく された 単語 の さいしょ と 最後 は そのまま で とちゅう の もじじゅんじょ を ランダム に いれかえ た 結果 を しゅつりょく する。
にほんご の ぶんしょう は 普通 は 単語 と 単語 の 間 に スペース が ないが、これ に ついては 処理 を かんたん に するため に スペース あり で にゅうりょく された ぶんしょう'.

nonLetters := input reject: #isLetter.
(input findTokens: nonLetters keep: nonLetters)
inject: ''
into: [:acc :token |
| middle |
(token first isLetter and: [token size > 3
and: [(middle := token copyFrom: 2 to: token size - 1) asSet size > 1]])
ifTrue: [
| shuffled |
[(shuffled := middle shuffled) = middle] whileTrue.
acc, (token first: 1), shuffled, (token last: 1)]
ifFalse: [acc, token]]

"=> 以前2ch で ここのと に ついて ケンブッリジ で はけっん された と いううよな なよいう の ぶしょんう が コピペ されて ひまろり
いじちき ゆめうい になり そよれう の へかんん を する ケリンッブジ ジネレェータ の ページ(Jvaa Srcpit で つらくれ てたと 思う)が つらくれ たりも しいてた。
今 は もなうい よだうが こかんい の お題 は これ である。つまり、にりょうゅく された 単語 の さしいょ と 最後 は そまのま で とゅちう の もじじんゅじょ を ラダンム に いかれえ た 結果 を しょつゅりく する。
にんほご の ぶしんょう は 普通 は 単語 と 単語 の 間 に スーペス が ないが、これ に つていは 処理 を かたんん に すたるめ に スーペス あり で にうりょゅく された ぶょんしう"

499デフォルトの名無しさん2018/05/21(月) 22:46:17.95ID:ivTUanMr
単語の最初と最後が正しいと途中の文字順序が違っていても正しい単語と見間違える
というのは無いこともないが、やっぱりおかしな単語はおかしく見えるな

500デフォルトの名無しさん2018/05/22(火) 02:04:34.13ID:IBCwJBRn
>>487
Kotlin
https://paiza.io/projects/vW2LiM_sGEYAb_l7QfaA_g

paiza.io の Kotlin はちょっとバージョンが古いようで shuffle() がなかったので自作した。

501デフォルトの名無しさん2018/05/23(水) 19:05:30.98ID:Au5e7VGg
僕の知り合いの知り合いができたパソコン一台でお金持ちになれるやり方
役に立つかもしれません
グーグルで検索するといいかも『ネットで稼ぐ方法 モニアレフヌノ』

AI2XF

502デフォルトの名無しさん2018/05/23(水) 22:43:13.42ID:0Sl9hrHV
僕の 知合いりの 知合りいが できた パコソン 一台で お持れちにな金る やり方
役立につ かまれもしせん
グルグーで 検るす索と いかいも 『 ネットぐ方稼で法 モヌレアフニノ 』

AXI2F

503デフォルトの名無しさん2018/05/24(木) 09:41:04.28ID:c64g4uzw
荒しだけの2連投か

504デフォルトの名無しさん2018/05/25(金) 03:35:14.49ID:thcmSanV
よく読み比べてみるとよい

505デフォルトの名無しさん2018/05/27(日) 20:01:12.45ID:zozk6gzj
荒らし業者の連投規制回避の小さな変更

さっさとアク禁になれ

506デフォルトの名無しさん2018/05/27(日) 20:37:36.93ID:Yc9D3hww
2個目はどう考えても業者じゃなくてスレ住人だろ…
業者はアク禁になってほしいのは同意

507デフォルトの名無しさん2018/05/27(日) 22:59:09.70ID:54akOR6H
>>506
お前のレスがあるまでケブンリッジジェネレータなのに気付かなかったわw

508デフォルトの名無しさん2018/05/28(月) 01:26:16.34ID:OHc1BnnP
いや、流石にそれは鈍すぎ

509デフォルトの名無しさん2018/05/28(月) 08:49:15.07ID:jUv7w+gM
まあ業者も日本語おかしいからね

510デフォルトの名無しさん2018/05/28(月) 09:38:09.76ID:KmDsu5r7
人間の認識力はそんなもんなんだろうな。ちょっと似てると同じと判断しまう。そうやって脳は省力化してエネルギーあまり使わないようにしてるのかも知れない。脳を動かすには糖分沢山必要だからな。

511デフォルトの名無しさん2018/05/28(月) 11:55:04.24
単なる老化

512デフォルトの名無しさん2018/05/28(月) 16:45:42.01ID:3CvuwD8l
逆に言えばいちいち全部の文字を正確に認識してたらちょっと誤字脱字や書き損じがあっただけで意味がわからなってしまうぞ

513デフォルトの名無しさん2018/05/28(月) 19:20:35.39ID:wGAafxHd
わからなって

514デフォルトの名無しさん2018/05/28(月) 21:12:41.80ID:NjmAPrvj
でもちゃんと読めちゃうってういね

515デフォルトの名無しさん2018/05/28(月) 21:24:04.06ID:GjCLG5ws
ういね

516デフォルトの名無しさん2018/05/28(月) 21:32:08.47ID:uFz834xt
くらだなといこに突っこんじんでゃねーよw

517デフォルトの名無しさん2018/05/28(月) 23:42:55.16ID:co2/BVdS
botの書き込みなんていちいち推敲モードで読まないからな

518デフォルトの名無しさん2018/05/28(月) 23:59:37.57ID:RI6Mq7Tq
推敲は読むときにするもんじゃないぞ書くときだぞw

519デフォルトの名無しさん2018/05/29(火) 00:08:28.36ID:ijkA2Dj3
>>518
あ、ホントだ、恥ずかしいww
校正というべきだったか

520デフォルトの名無しさん2018/05/29(火) 01:15:48.27ID:zVPinOAm
くらだなといこに

521デフォルトの名無しさん2018/05/31(木) 05:50:22.16ID:89+9cUdj

522デフォルトの名無しさん2018/06/03(日) 21:52:25.40ID:Six28wK2
お題:モリカケ問題を解くプログラム

523デフォルトの名無しさん2018/06/04(月) 21:24:56.45ID:XnHANXyJ
numpyのdotを再現せよ

524デフォルトの名無しさん2018/06/04(月) 21:32:40.88ID:i7Qhv+/y
お題: RFC 5321, 5322 に従ったメールアドレスの文字列をテキストファイルから抜き出すプログラム

参考
Javaで正規表現を使って抜き出すプログラム(最初に正規表現のパターンが出力される)
https://paiza.io/projects/Rc2wknAxofvjPfcs9MuYcQ

以下は日本語訳されたRFC
http://srgia.com/docs/rfc5321j.html
http://srgia.com/docs/rfc5322j.html

525デフォルトの名無しさん2018/06/04(月) 21:34:02.48ID:i7Qhv+/y
あ、ごめん。テキストファイルじゃなくて標準入力からでもいい。
何処から入力するかはたいした問題ではない。

526デフォルトの名無しさん2018/06/04(月) 21:55:13.33ID:J29vhHVp
http://www.din.or.jp/~ohzaki/mail_regex.htm
RFC通りのメールアドレス判定なんて不毛だってはっきりわかんだね

527デフォルトの名無しさん2018/06/04(月) 22:31:58.94ID:lBwALx1Z
>>526
わらたwwwww

528デフォルトの名無しさん2018/06/04(月) 23:19:04.56ID:hdRuAjud
昔仕事で MUA 作った時に >>526 にある
folding white space をぶち込んでくる送信元がいて苦労した記憶が…

529デフォルトの名無しさん2018/06/05(火) 00:27:36.36ID:xCctA/+R
>>526
ここはお題スレだから不毛で良いんだよ。パズルを解くようなもんなんだから。

530デフォルトの名無しさん2018/06/05(火) 00:33:47.39ID:ueqUCLW3
>>475に感化されて>>378の(1)(2)(3)を勉強しながら書いてみた
https://scalafiddle.io/sf/ZGr8M2X/1

531デフォルトの名無しさん2018/06/18(月) 23:54:29.00ID:2+ok0PtZ
お題: バイオリズム計算

計算結果の出力だけでも良いが、なんだったらアスキーアートやGUIで波形の絵を出したりしても良い。その辺は自由。

バイオリズムとは何かについては Wikipedia 参照。
https://ja.wikipedia.org/wiki/%E3%83%90%E3%82%A4%E3%82%AA%E3%83%AA%E3%82%BA%E3%83%A0

実際に計算して図を出すサイトもある。
https://keisan.casio.jp/exec/system/1231994137

新着レスの表示
レスを投稿する