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

**デフォルトの名無しさん** · 2018/04/24(火) 20:45:14.49

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

前スレ
プログラミングのお題スレ 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/

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

**デフォルトの名無しさん** · 2018/05/09(水) 01:56:38.20

>>292
Kotlin

(1..9).forEach { a -> println((1..9).map { it * a }.sum()) }

この1行をファイルに入れて kotlinc -script でファイルを指定するとスクリプトとして実行されて計算結果が出力される。

45
90
135
180
225
270
315
360
405

**デフォルトの名無しさん** · 2018/05/09(水) 03:24:50.65

>>292
C言語
https://ideone.com/nGbT40

**デフォルトの名無しさん** · 2018/05/09(水) 04:36:36.06

>>292 Nim

import math
const s1 = (sum[int]([1,2,3,4,5,6,7,8,9]))
var s=0; for i in 1..9: s+=s1; echo s

**デフォルトの名無しさん** · 2018/05/09(水) 07:39:32.32

>>300
命令はもう LDRULDRU... で与えた方がいいかもね
この256文字?命令も URDLURDLU まで最適化できちゃうわけだし

**デフォルトの名無しさん** · 2018/05/09(水) 14:54:31.24

>>300 Ruby
>>289を意識して最適化してみた
https://ideone.com/zwyM7p

2回動かした後、適切に反転させて右下が開くようにしておけば、
abc-
ed--
f---
----

LとRは、
cba-
de--
f---
----

UとDは、
fdc-
eb--
a---
----

と垂直、鉛直方向にそれぞれ反転するだけでいい
最適化された命令は時計回りか反時計回りに回すことになるけど、((駒の数)! + 1)回以内には必ずでループするのでそれも考慮
が、1980x1080には4秒要する模様

**デフォルトの名無しさん** · 2018/05/09(水) 15:06:55.92

>>295
マス単位で省けると思う
[a....,bcd..,efghi]を[a,bcd,efghi]って表現して
これを上に傾けて[acdhi,bfg,e]にする操作はこんなコードで出来る
https://ideone.com/i7EmbB
他の方向へは対称性を利用すれば書けるから
今は左下に寄ってるみたいな情報を持ってればいいし
その情報で行列表現にも戻せる
まあ駒の数が多い場合は大して速くならないけど

**デフォルトの名無しさん** · 2018/05/09(水) 15:13:44.30

あとは2回目以降どうやって傾けても駒の配置は合同(かその反転)になるから
2回傾けた結果を使って4回目を求めて……ってやればO((駒の数)*log(最適化された命令の長さ))で済みそうだよね

**デフォルトの名無しさん** · 2018/05/09(水) 15:37:49.24

>>305
面倒なループ書かなくても反転でいけたのか・・・
数学力が足りなかった

**デフォルトの名無しさん** · 2018/05/09(水) 18:01:06.55

>>275を>>300のボードで

こういう処理はCが速かろうということで何の工夫もないコードを書いてみた
アクションの最適化なしで256回動かした場合

MacBook-Pro:tmp$ time ./a.out <data.raw > r.raw

real 0m0.638s
user 0m0.625s
sys 0m0.009s
638ミリ秒

アクションの最適化だけ実装すると
MacBook-Pro:tmp$ time ./a.out <data.raw > r.raw

real 0m0.045s
user 0m0.037s
sys 0m0.006s
45ミリ秒

https://ideone.com/bZmXpg

**デフォルトの名無しさん** · 2018/05/09(水) 18:02:18.67

補足
256回というのは>>300にある256アクションをそのまま行うということ

**デフォルトの名無しさん** · 2018/05/09(水) 19:18:52.31

目先を変えて Apple の GCD を使って8スレッド並列にしてみた
4コアのPCで3倍くらいになった

アクションの最適化なし
MacBook-Pro:tmp$ time ./c.out <data.raw > rc.raw

real 0m0.218s
user 0m1.190s
sys 0m0.027s
218ミリ秒

アクションの最適化あり
MacBook-Pro:tmp$ time ./c.out <data.raw > rc.raw

real 0m0.023s
user 0m0.058s
sys 0m0.008s
23ミリ秒

100回繰り返すと1回あたり18msec程度になる模様
MacBook-Pro:tmp$ time for i in `seq 1 100` ; do ./c.out <data.raw >rc.raw ; done

real 0m1.814s
user 0m6.659s
sys 0m0.589s

https://ideone.com/ULrjTi

**デフォルトの名無しさん** · 2018/05/09(水) 21:01:50.08

やっぱはえ～ｗ

**デフォルトの名無しさん** · 2018/05/09(水) 21:40:14.20

(そして今試してわかったが dispatch_group は
>>311のように使いまわさず wait 後破棄してまた create する方が高速、と)

**デフォルトの名無しさん** · 2018/05/09(水) 21:57:48.63

スクリプト言語のわりには速いと言われるjsだけど当たり前なのかもしれないが桁違いにぜんぜん敵わんくて糞ワロタｗｗ

**デフォルトの名無しさん** · 2018/05/09(水) 22:18:37.30

JS のは配列の初期化や文字列操作関数とかが足引っ張ってるんじゃないだろうか。
毎回メモリアロケートするからキャッシュも効きにくそうだし。
2次元配列に初期値セットしてからコードで操作した方が速い気がする。

**デフォルトの名無しさん** · 2018/05/09(水) 22:24:38.34

PCの速度差がかなりあるだけかも知れんし後でjs版も計測してみる

**デフォルトの名無しさん** · 2018/05/10(木) 08:16:30.90

各コマの最大可動範囲は最初に定まるし
ターンが進むにつれ狭まりもするから
それで最適化できん？

知らんけど

**デフォルトの名無しさん** · 2018/05/10(木) 14:34:27.76

>>305のやり方だと二回傾けて以降は駒の入れ替えだけでいいから
numpyでboard[board!='.']=np.fliplr(board)[np.fliplr(board)!='.']とかやれば速いかな
インデックスは毎回計算しなくてもいいけど

**デフォルトの名無しさん** · 2018/05/10(木) 16:30:45.02

>>318で書いてみたけど
傾きの処理自体はC並みに速い
https://ideone.com/NWCyYW

**デフォルトの名無しさん** · 2018/05/10(木) 16:47:50.18

そりゃあ
numpyの本体はC言語だしなぁ・・・

**デフォルトの名無しさん** · 2018/05/10(木) 17:33:52.68

本当は数値計算みたいにもっと速い命令を使ってくれるかなと期待してたんだけど
そういう上手くはいかなかった

**デフォルトの名無しさん** · 2018/05/10(木) 17:50:15.92

>>281
Kotlin
https://paiza.io/projects/wLuen-HE27TC3lZo8QclPw
何を何枚使用するかの内訳も出るようにした。

**316** · 2018/05/10(木) 18:04:31.86

>>275のコードで>>300のデータを
C版を計測したMacのChromeで計測してみた
結果は>>300と似たような数字で性能差はあまりなさそう

actions(256個)そのまま
37.972秒

最適化した URDLURDLU を使用
1.861秒

**デフォルトの名無しさん** · 2018/05/10(木) 18:30:24.64

じゃあArray版作るか…
思ったんだけどこれWebGLでGPU計算出来るかな？いやGPGPU向きの問題かどうかすら分かんないんだけど詳しい人いるかと思って。

**デフォルトの名無しさん** · 2018/05/10(木) 20:41:39.42

>>275
J

left =: (((#~-.),(#~))'.'&=)"1
right =: (((#~),(#~-.))'.'&=)"1
solve =: 3 : 0
:
if. (#x) = 0 do. y return. end.
action =. {. x
actions_left =. }. x
if. action = 'U' do. board =. |: left |: y
elseif. action = 'D' do. board =. |: right |: y
elseif. action = 'L' do. board =. left y
elseif. action = 'R' do. board =. right y
end.
actions_left solve board
)

Cシングルスレッド版の3.5～6.6倍遅い
アクション(256個)そのまま
4.242秒
最適化した URDLURDLU を使用
0.161秒

https://%62it.ly/2rybKgZ

**デフォルトの名無しさん** · 2018/05/10(木) 21:02:14.89

Jが…Jがちゃんとプログラミング言語しとるｗ

**デフォルトの名無しさん** · 2018/05/10(木) 21:44:01.34

先頭2行のJらしい部分の解説

文字列を.と等しいか('.'&=)でマスク(#~)
(#~'.'&=) '..a.b' => '...'
その論理否定(-.)でマスク
((#~-.)'.'&=) '..a.b' => 'ab'
,で繋げる
(((#~),(#~-.))'.'&=) '..a.b' => '...ab'
これで右寄せ。反対に繋げれば左寄せ。

直感的で読みやすい

**デフォルトの名無しさん** · 2018/05/10(木) 21:52:47.05

えー直感ってなんだっけ…

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

第六感的に読みやすいな

**デフォルトの名無しさん** · 2018/05/12(土) 10:11:54.49

2つの普通のサイコロを
面と面をくっつけて直方体を作る
何種類の異なる直方体ができるか?
回転して同じものは同じ種類とする

**デフォルトの名無しさん** · 2018/05/12(土) 10:31:53.41

>>330　PHP
84

**デフォルトの名無しさん** · 2018/05/12(土) 10:56:43.70

共同ツール 1
https://seleck.cc/685

https://trello.com/
ボードのメニュー → Power-Upsから拡張可能 Slack DropBoxなど
Trello Chrome拡張機能　elegant
ttp://www.kikakulabo.com/service-eft/
trelloのオープンソースあり

共同ツール 2
https://www.google.com/intl/ja_jp/sheets/about/

共同ツール 3
https://slack.com/intl/ja-jp
https://www.dropbox.com/ja/
https://bitbucket.org/
https://ja.atlassian.com/software/sourcetree
https://sketchapp.com/extensions/plugins/
ttp://photoshopvip.net/103903

ttps://goodpatch.com/blog/sketch-plugins/

**デフォルトの名無しさん** · 2018/05/12(土) 11:33:58.65

>>332
アフィ

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

>>330
無限

**デフォルトの名無しさん** · 2018/05/12(土) 13:04:25.66

>>330
C言語
#include <stdio.h>
int main(){ printf("%d¥n", (6+5+4+3+2+1)*4); return 0; }

**デフォルトの名無しさん** · 2018/05/12(土) 13:50:20.72

>>330
直方体そのものは1つなのでは？各面に打ってある点の数は違うけど同じ直方体であることには変わりないよね。

などと言ってしまったら問題にならなくて全然面白くないので後で考えてみるよ。w

**デフォルトの名無しさん** · 2018/05/12(土) 15:39:30.07

まず数学的に考えると、6面の内の一面がくっつくのでこれで6種で、更にくっ付けられる面が6面なので6倍。そして4回回転できるので更に4倍。しかし同じ値の面がくっついた時はお互いに回転させても同じのができるのでこれを引く。
とすると6*6*4-6*4=6*4*(6-1)=6*4*5=120でいいのかな。

**デフォルトの名無しさん** · 2018/05/12(土) 15:42:14.83

ま、しかし、数学的に答え出しちゃったらプログラム作る意味なくなるような気がするので全パターン作って確かめるようなの作るか。

**デフォルトの名無しさん** · 2018/05/12(土) 15:53:15.44

>>337
なんか違う

**デフォルトの名無しさん** · 2018/05/12(土) 15:57:15.26

プログラム的な最適解って難しい

**デフォルトの名無しさん** · 2018/05/12(土) 16:11:04.18

プログラムでやる意味がまったくないな

**デフォルトの名無しさん** · 2018/05/12(土) 17:25:20.83

>>337
1-1
1-2 2-2
1-3 2-3 3-3
1-4 2-4 3-4 4-4
1-5 2-5 3-5 4-5 5-5
1-6 2-6 3-6 4-6 5-6 6-6
すなわち (6+5+4+3+2+1)×4面

**KAC** · 2018/05/12(土) 17:50:27.68

>>335
改行書くことすら惜しむくらいなら、「return 0;」省略すればいいのに・・・

>>338
そういうときはn面体に対するものにするとか、
m個くっつける場合のものにするとか、どこかの値を可変にすればいい。

**デフォルトの名無しさん** · 2018/05/12(土) 18:04:42.08

>>339
そうか。何が違うのか今のところ俺にはわからない。

>>342
その説明の意味がわからない。何を表しているのか？

**デフォルトの名無しさん** · 2018/05/12(土) 18:38:44.14

>>344
くっついている面の組み合わせ（サイコロを2つ振って出る目と同じ）×4回転

**デフォルトの名無しさん** · 2018/05/12(土) 18:57:16.30

>>345
あ、そうか。例えば1、6は6、1と同じか。

**デフォルトの名無しさん** · 2018/05/12(土) 19:09:45.48

6*7/2*4=6*7*2=84てことだな。

じゃ、あとは無理矢理全パターン出して全件チェックするブルートフォースなプログラムでもゆっくり作るとするか。

**347** · 2018/05/13(日) 03:37:21.95

散々考えて作ったプログラムで 96 と結果が出てしまい、何がどう間違ってるのか探すの面倒なのでとりあえず休止。
またその内気が向いたらやってみよう。

**デフォルトの名無しさん** · 2018/05/13(日) 17:57:36.41

よくある総当たり戦の試合数を求める問題の変形だろ
いくらなんでも算数レベルはさすがに・・・

**デフォルトの名無しさん** · 2018/05/13(日) 19:10:48.15

算数レベルだと不満があるみたいなので類題を
正五胞体の各面に1～10の番号が振られたサイコロが2つある
2つの正五胞体の面を合わせて新たな多胞体を作るとき、
面の模様の組み合わせ合わせてを合わせて何通り作ることができるか求めよ

**デフォルトの名無しさん** · 2018/05/13(日) 20:08:59.23

面を合わせる操作で胞はどうなるんだろう
模範解答が欲しいな

**デフォルトの名無しさん** · 2018/05/13(日) 20:10:50.40

O(1)でない問題に挑みたい

**デフォルトの名無しさん** · 2018/05/13(日) 20:28:41.70

無理だろ
問題のクラスがどこに属するかを確かめてから……ってのは

**デフォルトの名無しさん** · 2018/05/13(日) 20:48:58.34

出題者がわからなくてどうする

**デフォルトの名無しさん** · 2018/05/13(日) 22:02:39.26

出題者は学校の宿題をコピペしてるだけなんだからそんなの分かるわけないだろｗ

**デフォルトの名無しさん** · 2018/05/13(日) 23:15:41.18

円周上の格子点を求めるプログラムをしこしこ作ってるが、
マルチスレッドで動かしたらPentium G6950とAtom x5-Z8350タブレットでほとんど変わらなくて(´・ω・`)

**デフォルトの名無しさん** · 2018/05/13(日) 23:18:59.24

どのお題？

**デフォルトの名無しさん** · 2018/05/13(日) 23:27:47.10

これか

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

例)
x^2 + y^2 = 1の整数点は4つだがN=4の最小半径ではない。

(x-0.5)^2 + (y-0.5)^2 = 0.5の方が小さい。　4点は(0,0) (1,0) (0,1) (1,1)

**デフォルトの名無しさん** · 2018/05/13(日) 23:55:53.09

ああ、自称数学が出来る人がアホな事を言ってたヤツだな

最小値は存在しないとか
最小値が存在する証明は簡単だとか言いつつまったく出来てなかったり

**デフォルトの名無しさん** · 2018/05/13(日) 23:57:36.72

全く解いてないけど
力業しか方法は無いのかな？

AVX512とかGPUとか使えたりする？

**KAC** · 2018/05/13(日) 23:59:19.53

>>359
複数解があれば、その中で一番小さい物が最小値
という当たり前の定義に何か疑問でも？

**デフォルトの名無しさん** · 2018/05/14(月) 00:04:15.31

まだ続けるのその話題？

**デフォルトの名無しさん** · 2018/05/14(月) 00:07:14.94

>>361
最小値が存在するためにはいくつかの条件があって
その条件を全く考慮しないで「証明」と言い張ってたアホがいたと
まさか君じゃないよね？

◆QZaw55cn4c · 2018/05/14(月) 00:12:43.39

それより数学のセンセが複素指数関数をなんだか誤解しているのを何とか説き伏せたいのだけれども…

**デフォルトの名無しさん** · 2018/05/14(月) 02:08:50.73

>>364
多値関数のことを周期関数とか見当違いのことを言っていたあなたが何か言えることなんてあるんですか？
でこの話題まだ続けたいの？

**デフォルトの名無しさん** · 2018/05/14(月) 03:17:23.56

>>364
やるならよそで個人的にやってくれ

**デフォルトの名無しさん** · 2018/05/14(月) 07:14:36.98

なんか最小値とかでよほど辛い目にあったんだろうなw

◆QZaw55cn4c · 2018/05/14(月) 16:57:02.04

>>365
続けます、今必死に
http://www.eng.niigata-u.ac.jp/~nomoto/2.html
を理解しようとしています、とてもつらいです、涙が知らず知らず頬を伝っているありさまです…

**デフォルトの名無しさん** · 2018/05/14(月) 17:12:13.58

せんせーともども数学板へどうぞ。
こいつら異世界転生もののアニメ見てそうだなワラ

**デフォルトの名無しさん** · 2018/05/14(月) 21:15:20.93

数学の専門家が高見の見物

**デフォルトの名無しさん** · 2018/05/14(月) 21:29:45.96

仲間内じゃうだつが上がらないのかな、誉められたくてこんなとこまで来てチンコしごいてんのか気持ち悪い。
リアルで軽んじられてる理由が透けて見えるよ。ほんと迷惑な話。

**デフォルトの名無しさん** · 2018/05/14(月) 21:36:42.92

>>369みたいなアニオタは巣から出てくるな　不快な上に真面目に気持ち悪いわ

**デフォルトの名無しさん** · 2018/05/14(月) 23:27:31.52

お題
辺の長さと面の面積と体積の全てが整数である4面体を求める

**デフォルトの名無しさん** · 2018/05/14(月) 23:35:45.52

>>368
もしかしてリーマン面とかも知らずに留数定理がどうのこうの言ってたのか？
厚顔無恥ってこのことだぜ

**デフォルトの名無しさん** · 2018/05/15(火) 00:31:02.93

>>374
素人が素人を笑う
目糞鼻糞

**デフォルトの名無しさん** · 2018/05/15(火) 00:50:44.33

>>375
言ってる事がよくわからないんだが？
もしかしてくやしいの？

**デフォルトの名無しさん** · 2018/05/15(火) 01:12:11.74

数学コンプがプログラミングに逃げたが
やっぱり数学からは逃れられなかっただけ

**デフォルトの名無しさん** · 2018/05/15(火) 02:50:42.43

お題
(1) 入力された英数字([A-Z0-9])をモールス信号を表す文字列に変換する。大文字小文字は区別しない。
　記号は変換出来なくても良い。また数字の略体は不要。短点と長点には何の文字を使っても良いが、
　なるべく分かり易くするために「・」、「－」等にすること。

(2) (1)で作ったモールス信号を表す文字列の逆変換。

(3) 和文版の(1)と(2)

欧文、和文モールス符号については下記ページ参照
https://ja.wikipedia.org/wiki/%E3%83%A2%E3%83%BC%E3%83%AB%E3%82%B9%E7%AC%A6%E5%8F%B7

**デフォルトの名無しさん** · 2018/05/15(火) 03:49:05.69

>>350
問題そのものとは関係ないかもしれんが正五胞体の面同士を重ねても通常の多胞体にはならないんじゃ
次元をひとつ下げればふたつの正四面体の辺同士を重ねる操作にあたるよね

**デフォルトの名無しさん** · 2018/05/15(火) 06:03:50.51

>>378 Ruby
(1) を wavで出力
https://ideone.com/uw0YFZ

**デフォルトの名無しさん** · 2018/05/15(火) 07:41:42.24

>>376
おれは数学の専門家だって
>>368と>>374の低レベルなバトル楽しみにしてるよ

**デフォルトの名無しさん** · 2018/05/15(火) 09:34:19.74

その自称数学の専門家がなんでまたこんな場違いな板のスレに粘着してんの？
お前も実は数学コンプなんだろ

**デフォルトの名無しさん** · 2018/05/15(火) 09:38:30.52

もう数学問題に特化したお題スレ作った方が良いのでは？

**デフォルトの名無しさん** · 2018/05/15(火) 09:53:16.24

>>373
無い

**デフォルトの名無しさん** · 2018/05/15(火) 11:30:36.04

>>382
趣味のプログラマーだから
数学的に面白いネタ探し

>>384
プログラムで書きなさい

printf("ない??n");

**デフォルトの名無しさん** · 2018/05/15(火) 11:38:20.20

プログラム板で文字化けさせてる人って

**デフォルトの名無しさん** · 2018/05/15(火) 11:53:09.77

>>385
いちいちID変えてる時点でこいつが誰なのかすぐに分かってしまいますね

**デフォルトの名無しさん** · 2018/05/15(火) 11:53:29.05

全角の「ない」は化けていないのに不思議？不思議？

**デフォルトの名無しさん** · 2018/05/15(火) 12:43:26.80

円マークかな？Unicodeだとバックスラッシュとはコードが違うよね。

**デフォルトの名無しさん** · 2018/05/15(火) 12:45:53.43

前にLinuxの端末でバックスラッシュと円マークの両方が半角で普通に両方入力できて驚いたことがある。やっとまともになったのかとw

**デフォルトの名無しさん** · 2018/05/15(火) 13:01:00.15

??
\
￥

**デフォルトの名無しさん** · 2018/05/15(火) 13:02:18.78

なぜ化ける

**デフォルトの名無しさん** · 2018/05/15(火) 13:04:01.28

>>387
おれは誰なんだ？
ごくたまにしか書き込んで無いけど

**デフォルトの名無しさん** · 2018/05/15(火) 13:05:37.32

datをバイナリエディタで見たら化けてる所は 0xfc 0xfc になってるが、なぜそれになるのかは知らん。

**デフォルトの名無しさん** · 2018/05/15(火) 13:26:15.15

ていうかC言語等の文字のエスケープに使う文字は本来であればバックスラッシュだ。
円マークになってる入門書等が多い理由は歴史的な理由による。
どういう歴史的理由かは長くなるので省略。

**デフォルトの名無しさん** · 2018/05/15(火) 13:58:57.23

中途半端な知識で語りたがりが多いな
数学といい文字コードといい

**デフォルトの名無しさん** · 2018/05/15(火) 14:59:41.39

ま、これでも読め。
https://anopara.net/2016/03/06/%e5%86%86%e3%83%9e%e3%83%bc%e3%82%af%e3%81%a8%e3%83%90%e3%83%83%e3%82%af%e3%82%b9%e3%83%a9%e3%83%83%e3%82%b7%e3%83%a5/

**デフォルトの名無しさん** · 2018/05/15(火) 15:00:25.50

5chなんだから
じゃんじゃん語るべき

**デフォルトの名無しさん** · 2018/05/15(火) 15:13:17.78

"\" 円(U+00A5)
"\" バックスラッシュ(U+005C)

**デフォルトの名無しさん** · 2018/05/15(火) 15:14:24.36

両方U+005Cにされたｗ