Видео

ありがとうごじゃります

似たご質問をされた方がいました。ですが、コピペするのも詰まらないのでお答えします。 おっしゃる通り、名前のついていないタイル "でも" 青の場合は閉じています。要するに「青ならば名前が付いていようが付いて無かろうが関係なく処理できる」ということです。 これを示唆するため、動画左上のルール項目には青のチェックが先に来るように書き、全てのルールにおいて「次へ」の命令としました。そして実際のプログラムでも上から順番に処理をするため（順次処理）、青は殆ど無視されて処理が経過します。 しかしながら、動画内にはゲームオーバーを決定するルール３をテキストとして載せていないため、かく余計な疑問を生む結果になりました。申し訳ありません。

(◎□ ◎ ; ) < 外側からの攻撃に脆い

見た感じBFSが分かってて隣接する2点の条件が定義できれば解けるから、ムズめのC問題くらいだと思う 350点とか

できそうですね… してみたくなりますね… いずれ作ったらご紹介したく思います。

これ4次元になると閉じた領域を検出するのむずく無いか。5次元は無理だよね(?)

多分出来ると思います　もしやったら動画にしたいですね

コメントありがとうございます。 このアルゴリズムの肝は『２つのリストを軸に簡単な３つのルールで構成される』という"考え方"であり、拙くはありますが何とかお伝え出来たかなと思っています。 しかしながら、この動画を制作する過程で完成品が「説明用に描いた画像」と「確認用に書いたソースコード」の２つに分裂し、それらが辿る道筋に食い違いが生じました。 本アルゴリズムの本質を伝えようという目的は達成しましたが、細かい部分で視聴者を惑わせてしまう結果になったことは後悔しています。申し訳ありません。

ご指摘ありがとうございます。 おっしゃる通りではありますが、動画内では簡略化、かつ便宜的に「最外周の赤いパネル」を「名前がついていないパネル」として呼称しました。 つまり、『allyリストに追加する際に名前が付いていないと、何を追加するのか分からないよね、そこで躓くよね』『青いパネルは結局無視するのだから、名前の有無も無視できるよね』ということを、まんじゅうも交えて表現したかったんですが、確かに説明不足でした。申し訳ありません。 コメントありがとうございます。精進します。

なるほど、つまり私はggrniksではありますが、既存の機能を持つアルゴリズムを発想する程度の能力は持ち合わせている と… (｀・ω・´) + ｷﾘｯ 自分の良さを再発見させて頂きました。情報のご提供、並びに丁寧なコメントに、心から感謝致します。

うまいこと実装すると、主さんのアルゴリズムのほうが最悪計算量がよいですよ～

でも、アルゴリズムに関するコメントなどには、勉強もふまえてお返事するかもです。よろしくお願いします。

とても勉強になります。ありがとうございます。 動画内のプログラムではcheckedをリストではなく１行の文字列として定義し、その中から座標を検索する方法をとっています。これも配列のアクセスよりコストがかかるものなのでしょうか？ 重ねて、詳細なコメントありがとうございます。

@@Takabayakinka 「リスト（のようなもの）」と謎の書き方をした部分は，「データを列状に並べた構造」というような意図でした． こういうものから特定の値を探すのは普通にやると最悪計算量が線形時間ですが，これにはリストだけでなく，文字列や（座標自体を並べた一次元の）配列も該当します． contains は魔法ではないので，内部的には「『この位置から始まる部分文字列は検索文字列に一致するか調べる』を開始位置毎にやる」必要が（少なくとも素朴に実装すれば）あるはずで， 検索文字列が先頭の方にあってくれないと遅いです． 毎回そんな幸運は起こらないので，ほとんどの場合で遅くなると思われます． 他方，checked を二次元配列にして， checked[y][x] := （元のプログラムで言うところの）checked に入っていれば True，そうでないなら False というような値を入れることにすれば（初期化時を除いて）常に定数時間で済みます．

横から失礼します。 補足として、アルゴリズムの計算量(処理時間)を把握するのにオーダー記法というものが使われ、こちらを理解するとより分かりやすいと思います。 結論から言うと、文字列の検索の方が一般的に遅くなってしまいます。 checked、もとい「データを列状に並べた構造」での検索をjavaのString(StringBuilder.toString())クラスのcontainsで実装されているようでしたので、こちらのオーダーを調べてみました。 オラクルのjava公式ドキュメントには特に書いてなさそうでしたが、英語圏の記事を見ていると複数の記事で一般的な検索実装方法である線型探索であることが書かれています。 (記事の例：Blocks Codee "How to check if a string contains a substring in Java?", Medium "Efficient Substring Search in Java: How to Check if a String Contains a Substring") 線型探索は単純に前から調べていき、検索文字列と部分文字列が一致するかどうかを調べていく方法です。 torus711さんのおっしゃる通り、最善であれば1回の処理で、最悪の場合は文字列長程度分、この処理を繰り返す必要があります。 このような場合、オーダーをO(n)と表し、一般の場合において処理がデータ数(文字列長)に比例して増えることを表します。 一方、同じサイズの2次元配列を用意してbooleanで表す場合、検索する際に配列の該当要素[y][x]だけを見る形になります。 これは内部的に、配列のメモリ番地を直接指定して値を見る形となるため、すべての場合において処理は1回のみになります。 このような場合、オーダーをO(1)と表し、データ数(2次元配列の大きさ)に関係ない処理時間であることを表します。 オーダーは適切な関数f(n)を用いて一般にO(f(n))で表されます。このf(n)を比較することで処理時間の優劣がある程度わかります。 他のアルゴリズムでもオーダーが知られているものがあるため、知っていて損はないかもしれません。 色々書きましたが、動画作成・プログラミング活動を応援しています！

@@torus711 うまく理解出来ました。丁寧なご説明に感謝いたします。

A*アルゴリズム、美しくてかつ機能的な、アルゴリズムの王様ですよね。あれ好きです。 ですが、果たして「外周をゴールとしたA*アルゴリズム」に名前が付いているのか？主はggrniksなので分かりかねます() コメントありがとうございます。

改善点が洗いざらい出てくるので助かりますヨ。 それに良かれ悪かれコメントして頂けるということは、人が集まっているということなので！ 賑やかでうれしいです。昔活動していた頃は１ケタ再生が並でしたから。

るーいさん大好きです。見てて飽きないですし分かりやすいですよね。 果たしてあなたが「ゲームを作りたい人など」に当てはまるかどうかわかりませんが、コメントありがとうございます。アルゴリズム主体の動画なので、そこの筋が通っていれば問題は無いと判断しました。

@@Takabayakinka視聴者が「ゲームを作りたい人など」に関わらず 一般の人にも知られないと「ゲームを作りたい人など」にも十分に届かないと思います。 でも説明が始まるととても聞きやすい説明になっているなとは思います。

ね！思ったw

そう思うのは自由だけど言い方をわかってない典型 そして他のチャンネルの名前出して批判するあたり消費豚の自覚がない豚なんだろうな

ありがとうございます。 まんじゅうの瞬きで繋げたつもりでしたが、間との兼ね合いが難しいですね。

@@Takabayakinka 瞬きの動きが小さくてほとんど見えないのが問題ですよね。