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

■ このスレッドは過去ログ倉庫に格納されています
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/

宿題は宿題スレがあるのでそちらへ。
234デフォルトの名無しさん
垢版 |
2018/05/03(木) 01:32:09.14
>>233
無為に捨てられる何千もの’Hello, World!’がかわいそうすぎね?(´;ω;`)
2018/05/03(木) 01:32:43.19ID:rKkc5eBg
>>211 Perl5
https://ideone.com/cMJGDR

自力で動的計画法による解法を考えようとしていたけど、
>>227で紹介されたWEBの解法に勝る見込みが無さそうなので
思考を停止してWEBの解法を愚直に実装したものです
2018/05/03(木) 09:34:11.17ID:dYPbvGoR
【お題】
与えられた整数のリストで、
2つの要素の和が100になるすべての組を列挙せよ。

例:
[1, 99, 20]
-> [[1, 99]]

[62, 116, 181, 86, 60, 98, -16, 73, 131, 16, 80, -81, 40]
-> [[40, 60], [-16, 116], [-81, 181]]

[100, 0, 100, 0]
-> [[0, 100], [0, 100], [0, 100], [0, 100]]
237デフォルトの名無しさん
垢版 |
2018/05/03(木) 10:12:06.60ID:6SfrUic2
>>236 Rust
https://play.rust-lang.org/?gist=29b80b217f269f6ad43a712d52fd595e
2018/05/03(木) 10:13:33.58ID:ngB6qDho
>>236 ruby
https://ideone.com/Noq7GJ
239デフォルトの名無しさん
垢版 |
2018/05/03(木) 10:19:06.64ID:m6mdbiEz
>>236
Ruby。
ary.combination(2).select{|x|x.inject(:+)==100}
2018/05/03(木) 10:45:51.16ID:uFV+Z8SY
>>236 Squeak/Pharo Smalltalk

| fn |
fn := [:arr |
| bag |
bag := Bag new.
arr combinations: 2 atATimeDo: [:comb |
comb sum = 100 ifTrue: [bag add: comb sorted]].
bag asArray
].

fn value: #(1 99 20).
"=> #((1 99)) "
fn value: #(62 116 181 86 60 98 -16 73 131 16 80 -81 40).
"=> #((-81 181) (-16 116) (40 60)) "
fn value: #(100 0 100 0).
"=> #((0 100) (0 100) (0 100) (0 100)} "
241デフォルトの名無しさん
垢版 |
2018/05/03(木) 11:34:54.61
>>236
C言語
https://ideone.com/Ohue7U
2018/05/03(木) 13:12:32.47ID:N6jONgbj
>>236 Perl5
use Data::Dump 'dump';
for ([1, 99, 20],
[62, 116, 181, 86, 60, 98, -16, 73, 131, 16, 80, -81, 40],
[100, 0, 100, 0]) {
sub c {my $d = shift;
my @l = c(@_) if 1 < @_;
@l, map{[$d, $_]} @_};
@s = grep{100 == $$_[0]+$$_[1]} c @$_;
print dump($_)."\n->".dump(\@s)."\n";
}


実行結果
$ perl 11_236.pl
[1, 99, 20]
->[[1, 99]]
[62, 116, 181, 86, 60, 98, -16, 73, 131, 16, 80, -81, 40]
->[[60, 40], [181, -81], [116, -16]]
[100, 0, 100, 0]
->[[100, 0], [0, 100], [100, 0], [100, 0]]

※実行にはperlのData::Dumpモジュールが必要ですが、
 Ideoneのperl 24にはインストールされてないようでした
2018/05/03(木) 13:15:16.16ID:ngB6qDho
>>236 c
https://ideone.com/c5I9TG
2018/05/03(木) 14:31:25.30ID:M52LYEAa
>>236 javascript

var f = l => {
console.log(
l.reduce((acc, m, i, ary) =>
[
...acc,
...ary.slice(i+1)
.filter(n => m + n == 100)
.map(n => [m, n])
],
[]
)
)
}

f([1, 99, 20])
//=> [[1, 99]]
f([62, 116, 181, 86, 60, 98, -16, 73, 131, 16, 80, -81, 40])
//=> [[116, -16], [181, -81], [60, 40]]
f([100, 0, 100, 0])
//=> [[100, 0], [100, 0], [0, 100], [100, 0]]
2018/05/03(木) 14:55:50.12ID:cjR1ezGU
Smalltalk のメソッドの充実っぷりには毎回感心
2018/05/03(木) 18:28:55.09ID:qi+bYfi0
それなりの規模の処理系(GUI付きOSモドキ)をセルフホスティングで構築・維持していると
イディオムがイディオムとして認識・共有されやすく、さらにメソッドとしてまとめられやすいのかも

たとえばスクリプト言語処理系でしかないGNU Smalltalkはあまり便利メソッドが増える感じがしないので
247デフォルトの名無しさん
垢版 |
2018/05/04(金) 19:54:42.66ID:4Zt1BODM
お題
10,000個の単純変数に1から10,000の整数を代入する
2018/05/04(金) 20:34:39.46ID:6j9W/G+p
>>247 Ruby
(1..10000).each{|i|instance_variable_set("@v#{i}", i}
249デフォルトの名無しさん
垢版 |
2018/05/04(金) 20:41:53.19ID:LfImqqRO
>>247 Common Lisp
https://ideone.com/tM8Nve
250デフォルトの名無しさん
垢版 |
2018/05/04(金) 20:52:57.61ID:LfImqqRO
>>247 Bash
ideone だと駄目だった
https://ideone.com/FTnIoN
251デフォルトの名無しさん
垢版 |
2018/05/04(金) 21:16:29.34ID:sij7cbOA
>>247
Perl

for(1..10000){eval”\$a$_=$_”}

こんなんでいいのか?
252デフォルトの名無しさん
垢版 |
2018/05/04(金) 21:23:10.57ID:sij7cbOA
>>250
シェルもperlみたいにeval使えば簡単だと思うよ。その他の言語も同様。

てかこれ、インタープリタの言語にはできてもコンパイルする言語の場合は普通の方法ではできないんじゃないかな。
トリッキーな方法使ってようやっとできるかも知れないって感じじゃないだろうか。
253デフォルトの名無しさん
垢版 |
2018/05/04(金) 21:49:18.32
Cプリプロセッサでもやろうと思えばできるけど面倒だからやらない
2018/05/04(金) 21:57:55.58ID:mhxe2Hc6
お題:パイ生地を折り畳め
ただし要素数は二個以上で偶数とする
気が向いた人は逆の操作も実装せよ
https://ideone.com/W9woGu
255デフォルトの名無しさん
垢版 |
2018/05/04(金) 22:02:19.57ID:sij7cbOA
>>254
問題の意味がわからん
256デフォルトの名無しさん
垢版 |
2018/05/04(金) 23:16:59.35
>>255
分からないときは好きに解釈していいのがこのスレのルール
2018/05/05(土) 00:33:22.15ID:1BpKS+ks
>>254 Perl5
sub f {pop, shift, @_ ? f(@_) : ()}
sub g {@_ ? do{my $a = shift; shift, g(@_), $a} : ()}
use feature 'say';
sub pai {
say "@pai";
@pai = f(@pai); say "@pai";
@pai = g(@pai); say "@pai";
}
@pai = qw{1 2 3 4 5 6}; &pai;
@pai = qw{a b c d e f}; &pai;

実行結果
$ perl 11_254_1.pl
1 2 3 4 5 6
6 1 5 2 4 3
1 2 3 4 5 6
a b c d e f
f a e b d c
a b c d e f
258デフォルトの名無しさん
垢版 |
2018/05/05(土) 01:53:30.67ID:ia6t0Ogc
f, g のような変換関数を作ること自体は簡単な感じがするが、それと「パイ生地の折り畳み」がどう関係するのかがわからんな。
単にここでは折り畳んだらそういう並びになるというルールなだけ?
259デフォルトの名無しさん
垢版 |
2018/05/05(土) 01:54:26.33ID:0a7ZDXtf
>>254 Common Lisp
https://ideone.com/cabI9c
2018/05/05(土) 02:02:07.19ID:1dAfhim4
半分に折る->後半部を逆順に
折重ねたまま元の大きさまで伸ばす->前半部に合成

パイ生地の作り方からの連想だとは思う
2018/05/05(土) 02:08:07.54ID:j/DSqy58
>>247 javascript
eval('var ' + [...Array(10000)].map((_, i) => `a${i+1}=${i+1}`).join())
>>252の通りやった
2018/05/05(土) 02:13:33.62ID:1BpKS+ks
>>258 分からないと言うことをいろいろ言うつもりは無いけどm
>>254 のレスの内容とoctaveのコードから考えて
1 2 3 5 6
をパイ生地のように二つに折り畳んだ
1 2 3
6 5 4
を(下を先に選択して)リストで表すと
6 1 5 2 4 3
だということは想像に難くないので、そう解釈して解答を考えた。
gはその逆。誤解はあるかもしれない。

講釈がコードより長くなったけど、
「だけ?」って一体どういういみだよ?
263デフォルトの名無しさん
垢版 |
2018/05/05(土) 02:43:53.26ID:ia6t0Ogc
>>262
「パイ生地の折り畳み」という言葉に他の意味がないかってこと。
2018/05/05(土) 07:20:49.47ID:lTVCLXC3
>>254
J
l =: -: * -.@(2&|)
r =: (# - -:@>:) * 2&|
p_fold =: {~((l+r)@i.@#)

折りたたみちょっと面白いね
何度か繰り返し適用すると元に戻る
例えば4つだと p_fold^:3 (1 2 3 4) => 1 2 3 4
と3回適用すると元に戻る
(^:n ってのはn回適用するJの仕組み)

同様に
p_fold^:5 (1 2 3 4 5 6) =>1 2 3 4 5 6
p_fold^:4 (1 2 3 4 5 6 7 8) => 1 2 3 4 5 6 7 8
p_fold^:9 (1 2 3 4 5 6 7 8 9 10) => 1 2 3 4 5 6 7 8 9 10
2018/05/05(土) 10:31:30.99ID:5+ZWBL/x
>>254 Ruby 条件分岐を使わずにindexのみから求めてみた

f=->a{a.size.times.map{|i|a[(i&1)*i-i/2-1]}}
g=->a{(s=a.size).times.map{|i|a[~(4*i-2*s+3).abs/2]}}
p f[[*1..6]] #=> [6, 1, 5, 2, 4, 3]
p g[f[[*1..6]]] #=> [1, 2, 3, 4, 5, 6]
266デフォルトの名無しさん
垢版 |
2018/05/05(土) 11:51:20.86
>>254
C言語
https://ideone.com/frCiwG
2018/05/05(土) 14:19:41.02ID:E0VTmDdu
>>254 Squeak/Pharo Smalltalk

| f g pie |

f := [:arr |
((1 to: arr size)
collect: [:idx | arr perform: (#(atLast: at:) atWrap: idx) with: (idx / 2) ceiling]
) as: arr species
].

g := [:arr |
(((1 to: arr size) select: #even), ((1 to: arr size) select: #odd) reversed
collect: [:idx | arr at: idx]
) as: arr species
].

pie := 'abcdefg'.
pie := f value: pie. "=> 'gafbecd' "
g value: pie. "=> 'abcdefg' "

pie := (1 to: 7).
pie := f value: pie. "=> #(7 1 6 2 5 3 4) "
g value: pie. "=> #(1 2 3 4 5 6 7) "
2018/05/05(土) 16:41:53.04ID:YacZpoVZ
>>254 Squeak/Pharo Smalltalk >>265っぽい方針も入れて書き直し

| f g pie |

f := [:arr |
((1 to: arr size)
collect: [:m | arr atWrap: m * m even asBit - (m // 2)]
) as: arr species
].

g := [:arr |
((2 to: arr size by: 2), (1 to: arr size by: 2) reversed
collect: [:idx | arr at: idx]
) as: arr species
].

pie := 'abcdefg'.
pie := f value: pie. "=> 'gafbecd' "
g value: pie. "=> 'abcdefg' "

pie := (1 to: 7).
pie := f value: pie. "=> #(7 1 6 2 5 3 4) "
g value: pie. "=> #(1 2 3 4 5 6 7) "
2018/05/05(土) 17:07:44.87ID:ZO4AhgIr
>>265ってどういう計算してんの?
2018/05/05(土) 17:25:53.15ID:Js8QmTUw
お題
N×Mのフィールドが与えられる。各マスの意味は以下の通りとする。
'S':始点
'G':終点
'.':通行可
'#':通行不可

連続して同じ方向に進むことができないという制約下で、
始点から終点までの最短距離を求めよ。

[example 1]
S....
#....
..#..
....G
=> 9

[example 2]
S.....G
.......
=> 12
2018/05/05(土) 17:33:36.44ID:5+ZWBL/x
>>269
配列の長さを L とすると、
f(パイをたたむ)は;
i(0 <= i < L)番目の要素を元の配列の (~...~[i / 2]) % L 番目から持ってくればよい
(~...~はビット反転を i 回繰り返したもの)
g(パイを開く)は;
i(0 <= i < L)番目の要素を元の配列の (- 0.5 - |2 * i - L + 1.5|) % L 番目から持ってくればよい
2018/05/05(土) 18:32:03.46ID:sJdk0i7H
[][][] [[[ ] X_[[[ [] ][ [] ][][[[]
2018/05/05(土) 18:51:54.01ID:c0K4Xq7n
今抱えてる課題
1から100までインクリメントする変数iを用いて
300から1までの実数を100個出力せよ

i=1の時は300
i=100の時は1
となる式を考えてちょ(人・ω・)☆
2018/05/05(土) 19:03:50.73ID:1st6shTW
>>273
300 - (299.0 / 99.0) * (i - 1)
2018/05/05(土) 19:06:07.33ID:j/DSqy58
お題:文字駒を滑らせろ
四方を囲いで被われ駒がこぼれる心配のないM×Nマスのボードがある。
ここに英小文字が印字された正方形の駒が適当に配置されている。(駒のないマスは.(ドット)で表す)
与えられる、ボードを傾ける指示を完遂したときの最終盤面を表示せよ。
指示の方向はU(向かい方向)、D(手前方向)、L(左方向)、R(右方向)の四種類。

例1)
solve([
'...',
'.a.',
'...',
], 'UR')
// ↓
// [
// '..a',
// '...',
// '...',
// ]
https://jsfiddle.net/en6rd3vk/
※盤面は文字列の配列にしているが文字の配列の配列など言語で扱いやすいよう好きにしてよい

例2)
solve(
[".....", ".d.i.", "kmegk", "..tu."],
"LRRLLUDRRLRLRRURRRRLLLRULDUDULDLLRDULURULUDLDLUDDL"
)
//=> [".....", "gk...", "km...", "dietu"]

暇な人は300×300、指示数50くらいでやってみてください。最適化しないと結構時間かかっちゃうと思いますが。
2018/05/05(土) 19:17:21.84ID:c0K4Xq7n
>>274
ありがとうございます(^○^)
範囲を等分してiと合わせるだけだったんですね
これを思いつかないとは・・・寝てきます(・_・;)
277デフォルトの名無しさん
垢版 |
2018/05/05(土) 19:38:36.14ID:ia6t0Ogc
>>254
色々な言語で書いてみたが、やってることはほとんど同じ。
それぞれの言語の特徴をあまり生かせてない感じがする。

C
https://paiza.io/projects/zsjD__CUc4kIlaDd-nYgQQ
Kotlin
https://paiza.io/projects/ncCwkTCvQ0IsNcZGbpy_vw
Perl
https://paiza.io/projects/C9lzimZEAZzk25gjn4NGfw
2018/05/05(土) 20:28:32.99ID:MmzVJzsz
>>270 Ruby 愚直に

https://ideone.com/SYfrSu
2018/05/05(土) 20:59:38.12ID:a4pX7/xy
>>270 Squeak/Pharo Smalltalk

https://ideone.com/ACAeKW
2018/05/05(土) 22:20:56.64ID:MmzVJzsz
>>275 Ruby 傾ける順番だけ最適化

https://ideone.com/4iIY9g
2018/05/05(土) 22:58:44.12ID:Js8QmTUw
お題
Y円を支払うとき、同種の通貨の枚数を最小化する。

Y=500
=> 1 (500*1, 同種の通貨は最大1枚)

Y=300
=> 2 (2*100+2*50, 同種の通貨は最大2枚)

Y=40
=> 3

Y=60
=> 1
2018/05/05(土) 23:08:19.67ID:MmzVJzsz
>>281
通貨の種類は 1, 5, 10, 50, 100, 500, 1000, 2000, 5000, 10000?
2018/05/05(土) 23:19:24.99ID:Js8QmTUw
>>282 それでいいです。任意の種類に対応できたら尚良し
2018/05/05(土) 23:53:24.33ID:gS+4uwRv
>>281
=> 0 (カード決済または電子マネー決済)
285デフォルトの名無しさん
垢版 |
2018/05/06(日) 00:22:26.26
>>270
C言語
https://ideone.com/YLAnLJ
286デフォルトの名無しさん
垢版 |
2018/05/06(日) 01:34:21.80
>>281
C言語
https://ideone.com/RVA3Mk
287デフォルトの名無しさん
垢版 |
2018/05/06(日) 01:45:52.35ID:Bse1bLkg
>>275
Kotlin
https://paiza.io/projects/gVAA38huK6qosFkqbihPTg
ボードの内容と傾ける指示は全て標準入力から入力するようにした。
2018/05/06(日) 06:45:27.16ID:lHf8cLJR
>>281 Ruby ぴったり払えない時は No Solutions と出力

currency = [1, 5, 10, 50, 100, 500, 1000, 2000, 5000, 10000]
sums = currency.size.times.map { |i| currency[0..i].sum }

[74664, 55998, 37332, 500, 340, 300, 197, 161, 157, 60, 40].each { |yen|
print '%d => ' % yen
min = currency.zip(sums).reverse_each.map { |c, s|
yen -= c * x = [yen/c, -(-yen/s)].min
x
}.max
puts yen.zero? ? min : 'No Solutions'
}
#=>
74664 => 4
55998 => 3
37332 => 2
500 => 1
340 => 3
300 => 2
197 => 3
161 => 1
157 => 2
60 => 1
40 => 3
2018/05/06(日) 08:03:16.30ID:939GOaZM
>>275
一度でも水平垂直の両方に傾けると
座標じゃなくて単に駒の二次元リストでいけると思うから
指示の短縮と合わせて早くできると思うけど
どう書けばいいか悩んでる・・・
2018/05/06(日) 08:16:38.56ID:xMaBOakW
>>281 Ruby >>288を修正
currency = [1, 5, 10, 50, 100, 500, 1000, 2000, 5000, 10000]
samples = [74664, 55998, 37332, 500, 340, 300, 197, 161, 157, 60, 40]
cands = currency.zip(currency.reduce([]){|s, e| s << s.last.to_i + e}).reverse_each
breakdown = lambda do |yen|
  x = cands.map{|c, s| yen -= c * x = [yen/c, -(-yen/s)].min; x}.max
  yen > 0 ? 'No Solution' : x
end

samples.each{|yen| puts '%d => %s' % [yen, breakdown[yen]]}
#=>
74664 => 4
55998 => 3
37332 => 2
500 => 1
340 => 3
300 => 2
197 => 3
161 => 1
157 => 2
60 => 1
40 => 3
2018/05/06(日) 19:32:00.34ID:9CUhRDV/
}]] [[《_["[[]]" 〈[]》》 [][][]0,1》》〈〉 [] } } "B,V,0%%%,*1BVLO,SASA1`}}//%\\0,1\"VL"\
2018/05/08(火) 21:21:59.59ID:qF4LguOP
お題:九九の各段の値を合計せよ
https://ideone.com/T3TrFG
2018/05/08(火) 21:45:36.53ID:XzXTdruW
>>292

@9`*45
294デフォルトの名無しさん
垢版 |
2018/05/08(火) 21:54:00.37ID:rppAglGz
はっ。それはもしや45の倍数・・・

おや?こんな夜中に誰だ?
2018/05/08(火) 22:14:46.30ID:8rfWV9vw
>>289
それって例えば初期配置が以下のとき(■が駒)
□■■□□■
□□■□■□
■■□■□■
□□■■□□
□■□■□□
■□■□□■
最初に例えばULが来ると以下のようになって…
■■■■■■
■■■■■□
■■■■□□
■□□□□□
□□□□□□
□□□□□□
□だけの行、□だけの列はこれからハブいてループ回せるじゃんってことだよね。この例だと下二行。
なるほど命令の最適化ばっかり考えてて全然気づかなかった。
2018/05/08(火) 23:30:03.25ID:y0JbAqkN
>>292 Squeak/Pharo Smalltalk

(1 to: 9) sum * (1 to: 9) "=> #(45 90 135 180 225 270 315 360 405) "

((1 to: 9) * (Array new: 9 withAll: (1 to: 9))) sum. "=> #(45 90 135 180 225 270 315 360 405) "


ついでに全段の合計も

((1 to: 9) sum * (1 to: 9)) sum. "=> 2025 "

((1 to: 9) * (Array new: 9 withAll: (1 to: 9))) sum sum. "=> 2025 "

(Matrix rows: 9 columns: 9 tabulate: [:x :y | x * y]) sum. "=> 2025 "

((1 to: 9) asArray +* (Matrix rows:1 columns: 9 contents: (1 to: 9))) sum. "=> 2025 "
2018/05/08(火) 23:50:03.66ID:XzXTdruW
>>275
これの最適化したいんだけど誰か大きいボードのサンプルくれないかなあ
2018/05/09(水) 00:00:50.01ID:yM0yjk1d
激問って未だに更新されてるんだね
2018/05/09(水) 00:58:06.52ID:NS139TvC
>>296
Smalltalk なのに普通だ…いやtabulateが便利そう

J
格段の和
+/(*/[)>:i.9
45 90 135 180 225 270 315 360 405

さらに足すと
+/+/(*/[)>:i.9
2025

先に,で1次元化してから足せば1文字短く
+/,(*/[)>:i.9
2025
2018/05/09(水) 01:51:50.10ID:bn/AH8fd
>>297
すごくでかくなったので分けた。ごめんよjsfiddle...
board(1980x1080, 文字列の配列形式)
https://jsfiddle.net/eqyuvgm9/

actions(256)
https://jsfiddle.net/2j2817rc/

result(1980x1080, 文字列の配列形式)
https://jsfiddle.net/uyboko52/

このサンプルでchromeのコンソールで試した結果、
最適化なしでは47.4秒
命令の最適化だけで1.8秒になった
>>289も試してみようと思う
301デフォルトの名無しさん
垢版 |
2018/05/09(水) 01:56:38.20ID:qkLXPpHd
>>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
302デフォルトの名無しさん
垢版 |
2018/05/09(水) 03:24:50.65
>>292
C言語
https://ideone.com/nGbT40
2018/05/09(水) 04:36:36.06ID:uBL8ccTk
>>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.32ID:LEGAA83e
>>300
命令はもう LDRULDRU... で与えた方がいいかもね
この256文字?命令も URDLURDLU まで最適化できちゃうわけだし
2018/05/09(水) 14:54:31.24ID:LEGAA83e
>>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.92ID:FhlfzW8k
>>295
マス単位で省けると思う
[a....,bcd..,efghi]を[a,bcd,efghi]って表現して
これを上に傾けて[acdhi,bfg,e]にする操作はこんなコードで出来る
https://ideone.com/i7EmbB
他の方向へは対称性を利用すれば書けるから
今は左下に寄ってるみたいな情報を持ってればいいし
その情報で行列表現にも戻せる
まあ駒の数が多い場合は大して速くならないけど
2018/05/09(水) 15:13:44.30ID:LEGAA83e
あとは2回目以降どうやって傾けても駒の配置は合同(かその反転)になるから
2回傾けた結果を使って4回目を求めて……ってやればO((駒の数)*log(最適化された命令の長さ))で済みそうだよね
308デフォルトの名無しさん
垢版 |
2018/05/09(水) 15:37:49.24ID:FhlfzW8k
>>305
面倒なループ書かなくても反転でいけたのか・・・
数学力が足りなかった
2018/05/09(水) 18:01:06.55ID:tbbSaefy
>>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.67ID:tbbSaefy
補足
256回というのは>>300にある256アクションをそのまま行うということ
2018/05/09(水) 19:18:52.31ID:tbbSaefy
目先を変えて 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.08ID:28IRmfG3
やっぱはえ〜w
2018/05/09(水) 21:40:14.20ID:7NiN2gcq
(そして今試してわかったが dispatch_group は
>>311のように使いまわさず wait 後破棄してまた create する方が高速、と)
2018/05/09(水) 21:57:48.63ID:bn/AH8fd
スクリプト言語のわりには速いと言われるjsだけど当たり前なのかもしれないが桁違いにぜんぜん敵わんくて糞ワロタww
2018/05/09(水) 22:18:37.30ID:7NiN2gcq
JS のは配列の初期化や文字列操作関数とかが足引っ張ってるんじゃないだろうか。
毎回メモリアロケートするからキャッシュも効きにくそうだし。
2次元配列に初期値セットしてからコードで操作した方が速い気がする。
2018/05/09(水) 22:24:38.34ID:7NiN2gcq
PCの速度差がかなりあるだけかも知れんし後でjs版も計測してみる
317デフォルトの名無しさん
垢版 |
2018/05/10(木) 08:16:30.90
各コマの最大可動範囲は最初に定まるし
ターンが進むにつれ狭まりもするから
それで最適化できん?

知らんけど
2018/05/10(木) 14:34:27.76ID:qHVZoDSH
>>305のやり方だと二回傾けて以降は駒の入れ替えだけでいいから
numpyでboard[board!='.']=np.fliplr(board)[np.fliplr(board)!='.']とかやれば速いかな
インデックスは毎回計算しなくてもいいけど
2018/05/10(木) 16:30:45.02ID:qHVZoDSH
>>318で書いてみたけど
傾きの処理自体はC並みに速い
https://ideone.com/NWCyYW
2018/05/10(木) 16:47:50.18ID:Ulb5C2sT
そりゃあ
numpyの本体はC言語だしなぁ・・・
2018/05/10(木) 17:33:52.68ID:qHVZoDSH
本当は数値計算みたいにもっと速い命令を使ってくれるかなと期待してたんだけど
そういう上手くはいかなかった
322デフォルトの名無しさん
垢版 |
2018/05/10(木) 17:50:15.92ID:I+4Qxgba
>>281
Kotlin
https://paiza.io/projects/wLuen-HE27TC3lZo8QclPw
何を何枚使用するかの内訳も出るようにした。
323316
垢版 |
2018/05/10(木) 18:04:31.86ID:CLWEept/
>>275のコードで>>300のデータを
C版を計測したMacのChromeで計測してみた
結果は>>300と似たような数字で性能差はあまりなさそう

actions(256個)そのまま
37.972秒

最適化した URDLURDLU を使用
1.861秒
2018/05/10(木) 18:30:24.64ID:O+ANAa9X
じゃあArray版作るか…
思ったんだけどこれWebGLでGPU計算出来るかな?いやGPGPU向きの問題かどうかすら分かんないんだけど詳しい人いるかと思って。
2018/05/10(木) 20:41:39.42ID:CLWEept/
>>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.89ID:0yLDhGJt
Jが…Jがちゃんとプログラミング言語しとるw
2018/05/10(木) 21:44:01.34ID:CLWEept/
先頭2行のJらしい部分の解説

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

直感的で 読 み や す い
2018/05/10(木) 21:52:47.05ID:O+ANAa9X
えー直感ってなんだっけ…
2018/05/11(金) 02:07:15.57ID:9bxegKCD
第六感的に読みやすいな
330デフォルトの名無しさん
垢版 |
2018/05/12(土) 10:11:54.49ID:bX5i+Zj+
2つの普通のサイコロを
面と面をくっつけて直方体を作る
何種類の異なる直方体ができるか?
回転して同じものは同じ種類とする
2018/05/12(土) 10:31:53.41ID:Hl4HQ1Ge
>>330 PHP
84
2018/05/12(土) 10:56:43.70ID:pDgCeBjY
共同ツール 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.65ID:R/twbybb
>>332
アフィ
■ このスレッドは過去ログ倉庫に格納されています
5ちゃんねるの広告が気に入らない場合は、こちらをクリックしてください。

ニューススポーツなんでも実況