プログラミングのお題スレ Part15
■ このスレッドは過去ログ倉庫に格納されています
スタート地点に壁を作ってるみたい。アルゴリズムの詰めが甘いようだ。 >>160 表示の問題です。では済まないかい? 場所は保持してるよ? お題: 壁で囲まれた何もない有限の部屋(面積5m^3前後)の中に、四方向に距離センサーが付いた、丸い形のお掃除ロボット(直径20cm)がある。 各距離センサーは、ロボットからその方向にある障害物までの距離を常に教えてくれる。 ロボットはその場で右または左に5度単位で自転するか、もしくは前方向に5cm単位で前進できる。 部屋全体のおおよその形がわかるまで、ロボットを動かしなさい。 例) 正方形の部屋 例) 正三角形の部屋 例) 凹の形の部屋 直径20cmが入り込めない隙間は無視、もしくは壁と見なす。 スクリーンショットか動画を作れたら、30点加点する。 >>164 部屋の壁の構成が凹を基本としたヒルベルト曲線だったら「おおよその形」はそのロボットのAIは何と答えればいいの? ttps://cdn-ak.f.st-hatena.com/images/fotolife/o/obelisk2/20161224/20161224022849.png >>160 一晩かんがえてみたんだけどね、ゆる〜くね。 スタートに壁作るなとは書いてないよね?? 4個目のスタート地点の壁を許しても、3個目の答えが間違えてるやん? [-1,1]の壁を1回透過しないとゴールにたどり着けないやん? まあ [*いしのなかにいる*] は許されないと思うけどw >>171 あぁ、なるほど、先において起動させる前提なのか。 オレ、動的にターン制で考えてたわ。 動的ターン制って考えは思いつかんかった その考えなら>>155 でも問題ないな 部屋の形を表すビットマップ画像、もしくは一個以上の多角形でいいよ。 >>173 壁をいつ置くかの記述がなかった、設問の不備ということで、正解、にしときます。すみません。 >>32 perl5 http://ideone.com/1qwl1U ずいぶん前のお題だが面白い回答ができたので再提出 再帰する正規表現に perl-code 内蔵の正規表現 たぶんウルトラレア >>4 Java https://ideone.com/JHb8WE >>5-6 > T = std::max(T,UI(mt)); > if (T >= C) { Re++; } 保持してる最大値でもう一回振るかどうか決めちゃってないかい? >>182 振ったダイスが閾値超えてたら次の回を一回プラスしてる。 閾値C以上ならという判断。 >>4 https://ideone.com/1zA9kL C++。フォークして修正してみた。これでいいかなぁ。 俺のとあってるし多分いいんじゃね?わからんが でも>>5-6 の時点で出題者からの突っ込みがないのが気になる 出題者出てきてー https://ideone.com/XIuQ53 しつこいけど、変数名のかぶりが気持ち悪かったので書き直した。 それと、手元でデバッグ軽くやっておいた。 >>186 そりゃよかった。 出題者に宿題解かされたかな?? お題:値が変更不可能でインデックスだけ参照できるシャッフルされた配列を何らかの方法でソートする。その際配列や値のコピーは取れない。 C++でいう、constの配列をなんとか整列してみましょう。 自分の答え。:https://ideone.com/4S932i >>189 Perl5 use List::Util shuffle; @a = shuffle 1..10; @ix = 0..$#a; print "@a\n"; @iy = sort{$a[$a] <=> $a[$b]} @ix; print "@a[@iy]\n"; 実行例 ~ $ perl 15_189.pl 5 2 4 8 3 10 6 9 1 7 1 2 3 4 5 6 7 8 9 10 激お題:自動プログラミングプログラムを作るか日本語で説明せよ。方法は各自の言語にゆだねる。 https://ideone.com/2UWc8g 自分は上記のようなものを作った。 4kb位のプログラムができるのに多分数年かかる。 コンパイラの通ったかというのを取れれば文章的に正しいやつは何かを残していく。 でも、コンパイラに投げる動作はわからないので入れてない。 >>190 perlわからないけど、参加してくれてありがとう。 コードが短くて羨ましい。 >>191 ナンジャそれは、お題でもなんでもない。 まず日本語の勉強をして出直してこい。 お題も人に解る様に出せないような人間はプログラマの素質はない。 >>193 どこが解りにくかったですか? テストコードは、言語で使える英数記号類を全探索するモノです。 >>195 お題と余談が書いてあるだけだぞ。 とりあえず、刮目して自動プログラミングプログラムを作ってください。 作れなさそうなら、概要を日本語で説明してください。 まず自動プログラミングプログラムってなんだよ お前の造語なんか知らんわ >>189 Kotlin https://paiza.io/projects/hCnNPeSohDhcerAL2MMqag こんなので良いのかな? 厳密に言ったら最後の出力文字列を作る時の map で値が取り出されて新たなリスト作るからコピーされちゃってんだけどね。 「自動プログラミング」「プログラム」ですが何か。 DSLじゃないわ。 1文字ごとにカンマが入って空白or改行を使わないプログラミング言語ってなんだろう…? 4kb(この表記だとビットかバイトかわからん)が数年で行けるってどういう計算だろう…? >>199 暗黙変数があるとオレ、フリーズしちゃうなぁ。 やったことない言語だけど、結果はあってると思う。 >>201 文字の列挙のリストには抜けがあるかもしれない。 C++は改行しなくても空白さえあればかける気がするけど。 なお、字数が増えれば増えるほど遅くなる。 とりあえず、実行してみればわかるけど、検索文字を総当たりしてるだけだからね。 んで、コンパイラに投げて通るかどうかのチェック入れないといけないんだ。 >>201 あぁ、指摘には感謝しておく。 4kbは大体4千字くらいか。 字数が増えれば増えるほど遅くなる、の遅くなり具合がわかってない気がする 使用する文字の種類を60とした場合、総当たりで毎秒10億個生成できても19年で10文字くらいだよ >>205 うほ!そんな遅いんかいな。 オーダーよりパッションで作ったのでそこまで考えてない。 それが・・・現実・・・!!! >>206 そんなかんじだねぇ。 設問が悪い。 自動プログラミングプログラムの出力が不正でなければ良い→コンパイルエラーないしはランタイムエラーを出さない、で良いの? phpのソースを書き出せば問題ない。 ランダムな文字列を出力し続けても、文字空間が64文字であれば、5文字目以降、毎回1/1073741824で失敗するがそれ以外のケースで自分自身を表示する正しいプログラムになる。 >>200 自動プログラミングが何で数字の羅列なんだよ。 何処がプログラミングだよ。 こんな物どんなコンパイラを通したら意味を持ったプログラムになるんだよ。 >>209 エーっと、C/C++はポインタがあるので実行したマシン破壊する確率は高いな。 わざと文書的に正しければと書いてあるんだが、気づいてないな。 >>208 そうですなぁ。チェッカーがエラーを吐かないでよかった気がする。 とりあえず、絶不評なので>>191 は終了します。 お付き合いいただきありがとうございました。 ガチでやるなら遺伝的アルゴリズムで遊んだほうが面白そうな話題ではある。 総当たりは分が悪い。 ネットでプログラムとかコードとかの記事検索して予約語が含まれるセンテンスをコピペするプログラムとかどう?(゚∀゚)<これを自動プログラミングと呼べるかどうか知らんけど >>212 最後まで何をやらせたいのかわからなかった。 >>214 そいつは小学生じゃなくて わりと高齢の池沼だと思う お題: 入力として任意の長さのバイト列(半角アルファベット)が与えられる。入力を左から読み取っていくとき、 読み込まれるバイトの状態遷移を表すデータまたは画像を出力せよ。ただし、初期状態は'^'、終了状態は'$'で 表すものとし、状態遷移図のノードには重複がないものとする。 例) "AKDAK" → ^: A. A: K. K: D$. D: A. $: . mousukosikangaetekarasyutudasisiroyokusokotega >>219 > 読み込まれるバイトの状態遷移を表すデータまたは画像 とは何か? >>222 D$は、Dに遷移するか、または、$に遷移するって意味じゃないかな ちゃうやろJK edgeの終端が二股は有効グラフではNGやで お題 1億以下の同じ数字でできている数(1,22,777など)をすべて表示する >>228 自然数を対象とします。なので0は対象外。 >>228 Ruby p (1...9).flat_map{|i| (1..9).map{|j| j * (10**i - 1) / 9}} # => [1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 22, 33, 44, 55, 66, 77, 88, 99, 111, 222, 333, 444, 555, 666, 777, 888, 999, 1111, 2222, 3333, 4444, 5555, 6666, 7777, 8888, 9999, 11111, 22222, 33333, 44444, 55555, 66666, 77777, 88888, 99999, 111111, 222222, 333333, 444444, 555555, 666666, 777777, 888888, 999999, 1111111, 2222222, 3333333, 4444444, 5555555, 6666666, 7777777, 8888888, 9999999, 11111111, 22222222, 33333333, 44444444, 55555555, 66666666, 77777777, 88888888, 99999999] >>228 Google Sheets =ARRAYFORMULA(REPT(ROW(1:9), COLUMN(A:H))) https://i.imgur.com/pKQgzAG.png >>228 同じ数字でできている数って?どういう意味? >>228 Pharo/Squeak Smalltalk (1 to: 8) gather: [:n | (1 to: 9) collect: [:m | (Array new: n withAll: m) polynomialEval: 10]] #(1 2 3 4 5 6 7 8 9 11 22 33 44 55 66 77 88 99 111 222 333 444 555 666 777 888 999 1111 2222 3333 4444 5555 6666 7777 8888 9999 11111 22222 33333 44444 55555 66666 77777 88888 99999 111111 222222 333333 444444 555555 666666 777777 888888 999999 1111111 2222222 3333333 4444444 5555555 6666666 7777777 8888888 9999999 11111111 22222222 33333333 44444444 55555555 66666666 77777777 88888888 99999999) 遅いけど perl5 for (1..100_000_000) { print if s{\A (.) \1* \z}{$& }x } 1 2 3 4 5 6 7 8 9 11 22 33 44 55 66 77 88 99 111 222 333 444 555 666 777 888 999 1111 2222 3333 4444 5555 6666 7777 8888 9999 11111 22222 33333 44444 55555 66666 77777 88888 99999 111111 222222 333333 444444 555555 666666 777777 888888 999999 1111111 2222222 3333333 4444444 5555555 6666666 7777777 8888888 9999999 11111111 22222222 33333333 44444444 55555555 66666666 77777777 88888888 99999999 >>91 Haskell main = mapM_ (print.only) [ [1,1,1,1,2,2,2,3,3,4], [1,2,3,4,5,5,4,3,2,1], [3,1,4,1,5,9,2,6,5,3,5] ] only ns = f [xs | xs <- (group.sort) ns, length xs == 1] where f [] = -1 f ([x]:_) = x ワンライナーも出来るけど、何やってるか読み取り辛い。 only ns = if lst == [] then -1 else (head.head) lst where lst = [xs | xs <- (group.sort) ns, length xs == 1] >>228 Perl5 @s = map{$a=$_; map{$_ x $a} 1..9} 1..8; print "@s"; 実行; ~ $ perl 15_228.pl 1 2 3 4 5 6 7 8 9 11 22 33 44 55 66 77 88 99 111 222 333 444 555 666 777 888 999 1111 2222 3333 4444 5555 6666 7777 8888 9999 11111 22222 33333 44444 55555 66666 77777 88888 99999 111111 222222 333333 444444 555555 666666 777777 888888 999999 1111111 2222222 3333333 4444444 5555555 6666666 7777777 8888888 9999999 11111111 22222222 33333333 44444444 55555555 66666666 77777777 88888888 99999999 a = 0 for i = 1, 8 do a = a * 10 + 1 for j = a, a * 9, a do print(j) end end >>228 Lua >>228 Haskell import Data.List main = (print.sort.concat) [[(sum.take a) [x * 10 ^ y | y <- [0..9]] | x <- [1..9]]| a <- [1..8]] お題 >>228 を求めることができる 特に最適化を施さないナイーブな実装(例えば>>238 )を書いて その実行にかかる時間(ミリ秒、秒等)を計測し出力してください なお遅い言語処理系で1億以下が無理な場合は1千万以下でも構いません time perl -e 'for (1..100_000_000) { print if s{\A (.) \1* \z}{$& }x }' 1 2 3 4 5 6 7 8 9 11 22 33 44 55 66 77 88 99 111 222 333 444 555 666 777 888 999 1111 2222 3333 4444 5555 6666 7777 8888 9999 11111 22222 33333 44444 55555 66666 77777 88888 99999 111111 222222 333333 444444 555555 666666 777777 888888 999999 1111111 2222222 3333333 4444444 5555555 6666666 7777777 8888888 9999999 11111111 22222222 33333333 44444444 55555555 66666666 77777777 88888888 99999999 real 1m30.031s user 1m29.046s sys 0m0.093s >>245 Pharo/Squeak Smalltalk | time ans | time := [ans := (1 to: 100000000) select: [:n | n asString asSet size = 1]] timeToRun. ^{time. ans} "Core m3-8100Y => an Array(0:00:02:55.58 #(1 2 3 4 5 6 7 8 9 11 22 33 44 55 66 77 88 99 111 222 333 444 555 666 777 888 999 1111 2222 3333 4444 5555 6666 7777 8888 9999 11111 22222 33333 44444 55555 66666 77777 88888 99999 111111 222222 333333 444444 555555 666666 777777 888888 999999 1111111 2222222 3333333 4444444 5555555 6666666 7777777 8888888 9999999 11111111 22222222 33333333 44444444 55555555 66666666 77777777 88888888 99999999)) " >>245 Perl5、1千万以下、CPU: Core i5 M520@2.4GHz use Time::HiRes qw(gettimeofday tv_interval); $t0 = [gettimeofday]; for (1..1e8) { push @s, $_ if /^(.)\1*$/; } $elapse = tv_interval($t0, [gettimeofday]); printf "@s\n%.3f[s]\n", $elapse; 実行結果 ~ $ perl 15_245.pl 1 2 3 4 5 6 7 8 9 11 22 33 44 55 66 77 88 99 111 222 333 444 555 666 777 888 999 1111 2222 3333 4444 5555 6666 7777 8888 9999 11111 22222 33333 44444 55555 66666 77777 88888 99999 111111 222222 333333 444444 555555 666666 777777 888888 999999 1111111 2222222 3333333 4444444 5555555 6666666 7777777 8888888 9999999 49.732[s] >>245 Java https://ideone.com/0ddTLO Pentium G6950@2.8GHz 整数演算: 1,073ms 正規表現: 46,450ms Ideone 整数演算: 495ms 正規表現: 2,592ms (これだけ1千万以下で計測) >>120 Haskell main = map (\n -> f n 0) [15,93,77,123] f n a | n < 10 = (n,a) f n a = f (product [read [x] | x <- show n]) (a + 1) >>245 c99、 Core i5 M520@2.4GHz #include <time.h> #include <math.h> #include <stdio.h> int main() { int b = 1, n = 1; clock_t s = clock(); for (int e = 1; e <= 9; e++) { int j = pow(10, e) - pow(10, e - 1); for (int i = 1; i <= j; i++) { if (n == (n / b) * b) printf("%d ", n); n++; } b *= 10; b += 1; } clock_t e = clock(); printf("\n%.3f[s]\n", (double)(e - s)/1e6); } 実行結果 $ cc -std=c99 -O2 15_245.c -lm $ time ./a.out 1 2 3 4 5 6 7 8 9 11 22 33 44 55 66 77 88 99 111 222 333 444 555 666 777 888 999 1111 2222 3333 4444 5555 6666 7777 8888 9999 11111 22222 33333 44444 55555 66666 77777 88888 99999 111111 222222 333333 444444 555555 666666 777777 888888 999999 1111111 2222222 3333333 4444444 5555555 6666666 7777777 8888888 9999999 11111111 22222222 33333333 44444444 55555555 66666666 77777777 88888888 99999999 111111111 222222222 333333333 444444444 555555555 666666666 777777777 888888888 999999999 3.890[s] >>228 https://ideone.com/0Hy6a6 C++。いつもなら数え上げで書くところだが、今回は趣向を変えてみた。 >>252 >>231 > 自然数を対象とします。なので0は対象外。 すぺしゃらいずいらねw ぶー!!! ・・・これが・・・!!!・・・これこそが・・・!!! ・・・だ・・・!!!・・・だそく・・・!!!! >>245 Haskell ナイーブな方 Atomコア(Celeron N3050@1.6GHz) 1億以下で約31秒 main = print [x | x <- [1..100000000], let (s:ss) = show x, all (== s) ss] time ./zorome real 0m31.426s user 0m31.123s sys 0m0.248s ナイーブな方は探すアルゴリズムで、最適化の方(>>244 )は数列を作るアルゴリズム。 (1から99999999までの(1桁から8桁までの)ゾロ目を作る) [ [[1],[1,10],[1,10,100]...], [[2],[2,20],[2,20,200]...], ..., [[9],[9,90],[9,90,900]...]] ] って言う数列を生成して、合計出してフラットにしてソートしてるだけだよ。 (他の言語のも多少の手順の違い(フラット化とソートしないで「合計出した時点で表示」を縦方向に繰り返したり)はあるけど、基本のアルゴリズムとしては同じ) お題: nバイトのデータxをビット列にして出力しなさい ■ このスレッドは過去ログ倉庫に格納されています
read.cgi ver 07.5.5 2024/06/08 Walang Kapalit ★ | Donguri System Team 5ちゃんねる