指定した通りに配列の要素を書き換えたい – python アルゴリズム

質問:


二次元配列の要素を、別の配列のデータに従って入れ替えたいです。

今、1つの配列に縦5横6の二次元配列があり、配列(array)の中身は全て “.” で埋まっています。つまりarrayは

array = [
  [".",".",".",".",".","."],
  [".",".",".",".",".","."],
  [".",".",".",".",".","."],
  [".",".",".",".",".","."],
  [".",".",".",".",".","."]  # ←①
]

となっています。

この “.” を str_array 配列の数字に従って書き換えたいです。たとえば str_array

str_array = [[1, 1, 0], [1, 3, 2], [3, 3, 1]]

のときを考えます。この str_array は要素を3つもっています。

  • 最初の [1, 1, 0] はarrayの最後のブロック(①で示したもの)を書き変えます。
    • [1, 1, 0] の 0 は [".",".",".",".",".","."] の左から0番目の場所を表し、1, 1 は縦横1つずつの “.” を書き換えることを示します。
    • これによって、最後のブロックが ["#",".",".",".",".","."] になるということです。
  • 次の [1, 3, 2] は左から2番目の “.” を書き換えます。今 array は

    array=[
        [".",".",".",".",".","."],
        [".",".",".",".",".","."],
        [".",".",".",".",".","."],
        [".",".",".",".",".","."],
        ["#",".",".",".",".","."]
    ]
    

    という状態であり、一番下のブロックの左から2番目が空いているので、縦1横3で “#” を敷き詰め、下のように書き換わります。

    array=[
        [".",".",".",".",".","."],
        [".",".",".",".",".","."],
        [".",".",".",".",".","."],
        [".",".",".",".",".","."],
        ["#",".","#","#","#","."]
    ]
    
  • 最後の [3, 3, 1] は左から1番目の “.” を書き換えますが、一番下のブロックには縦横3つをもう入れ替えられないので、

    array=[
        [".",".",".",".",".","."],
        [".","#","#","#",".","."],
        [".","#","#","#",".","."],
        [".","#","#","#",".","."],
        ["#",".","#","#","#","."]
    ]
    

    と array を書き換えます。

最終的に、

array=[
    [".",".",".",".",".","."],
    [".","#","#","#",".","."],
    [".","#","#","#",".","."],
    [".","#","#","#",".","."],
    ["#",".","#","#","#","."]
]

を出力させたいです。

これを行えるようなアルゴリズムとしてfor文をまず思いつきました。次にスタート “.” を入れ替えられるように 4 * 6 + 1 という風に (縦幅-1) * 横幅 + スタートの順番 という式を使うのではと思いましたが、これらをどう組み合わせればいいのかわかりません。特に “.” が既に埋まっていて “#” になっている時とそうでない時で処理が違います。このプログラムはどのように書けますか?

今の断片コードですが、

for i in range(len(str_array))
    str_array[0][i] * str_array[1][i] + x

(xはスタートの順番)と書きました。

質問者: mikimiki

metropolis

ごく簡単に説明すると、str_array で指定された矩形領域を走査して、領域内の要素が全て '.' の場合は '#' に置き替えています。
以下の実行例では str_array[5, 1, 5] を追加しています。なお、エラーチェック(array の range check)はしていないので、str_array の内容によってはエラーが発生します。

str_array = [[1, 1, 0], [1, 3, 2], [3, 3, 1], [5, 1, 5]]

l = len(array) - 1
for str in str_array:
  h, w, s = str  # height, width, start
  for r in range(l, h-2, -1):
    if all(map(all, [[i == '.' for i in array[y][s:s+w]] for y in range(r, r-h, -1)])):
      for y in range(r-h+1, r+1):
        array[y][s:s+w] = ['#'] * w
      break
=>    
[['.', '.', '.', '.', '.', '#'],
 ['.', '#', '#', '#', '.', '#'],
 ['.', '#', '#', '#', '.', '#'],
 ['.', '#', '#', '#', '.', '#'],
 ['#', '.', '#', '#', '#', '#']]

# テトリスを想い起こしました

コメント欄の質問に対する回答

  • l = len(array) - 1 はどういう意味があるのでしょうか?

array の内容を調べ始める位置(インデックス)です。この場合、array の最後の要素からチェックする必要があるので、そのインデックス番号を取り出しています。ループ内不変定数になるので、予め変数 l に代入していますけれども、for r in range(len(array)-1, h-2, -1): としても実際には Python インタープリタで最適化されるのではないかと思います。

  • for r in range(l, h-2, -1): で h-2, -1 としているのはなぜでしょうか?

実際に調べる範囲は array[l] から array[h-1] で十分だからです。例えば [3, 3, 1] の場合、「高さ」が 3 なので、

- array[4], array[3], array[2] 
- array[3], array[2], array[1] 
- array[2], array[1], array[0] 

をチェックする事になります。これ以降(例えば array[1], ...)は array の領域から外れる(はみ出る)事になります。

  • [[i == '.' for i in array[y][s:s+w]] for y in range(r, r-h, -1)] の部分は何をしているのでしょうか?

all() で判定するため、'.' との比較結果(True or False)のリストを作っています。矩形領域内の全ての要素が '.' であれば、'#' に置き換える事ができるわけです。

  • for y in range(r-h+1, r+1):r-h+1r+1 はどういう意味なのでしょうか?

これは range(r, r-h, -1) と同値です。方向が逆になっているだけで、入れ替えても結果は同じになります。

出典

Related Posts:

NameErrorが出る – python
質問: 以下のコードを実行したいのですがエラーが出てしまいます。 解決方法を教えていただけると幸いです。 元のコードはdata-science-from-scratch/nearest_neighbors.pyにあります。 現在Pythonを学び始めたばかりなのですが、したいこととしてはk近傍方でk=1,3,5,7でどのような結果になるのか示したいと認識しています。 import math def knn_classify(k, labeled_points, new_point): """each labeled point should be a pair (point, label)""" # order the labeled ...
バイトニックソートとマージソートの違いを教えて [クローズ済み] – アルゴリズム
質問: 動画を見たり画像見たけど違いわからなかったよ 同じ間隔離れたものを入れ替えるって共通する点じゃないか ほら、全く違いが見えない 質問者: 溢れだすクズ マージソートは他のソートアルゴリズム(バイトニックソートを含む)と比べて、メモリには全体を格納できないほど数の多いデータを、ディスクのようなシーケンシャルアクセスが主体の外部記憶装置に格納しつつソートするのに有用です。 出典
お釣りの札と硬貨の枚数をもとめたい – ruby アルゴリズム
質問: お釣りの札と硬貨の枚数をもとめたいです。Rubyで解きたいのですがやり方がわかりません。 468円の買い物をして1万円札を出したときの実行結果は以下の通りになります。 五千円札の枚数 = 1 千円札の枚数 = 4 五百円玉の枚数 = 1 百円玉の枚数 = 0 五十円玉の枚数 = ...
【Python3】Beautiful Soupについての質問 – python
質問: Beautiful Soupで <div class="hoge1"> <div class="hoge2"> <p>hogehoge</p> </div> </div> といったHTMLコードから<p>の部分を取得するにはどのようにしたら良いのでしょうか?   質問者: creamroid 下記ではいかがでしょうか。 from bs4 import BeautifulSoup html = """ <div class="hoge1"> ...
tensor flowのバージョンアップを行った結果、checkpointファイルのフォーマットが変更されている – python tensorflow
質問: tensorflowの学習モデルの出力フォーマットが以前のものとは変更されており、 model.ckptだけであったのが model.ckpt-1111.data-00000-of-000001, model.ckpt-1111.index, model.ckpt-1111.meta といった具合に3ファイルに変更されており対処に困っています。 どのckptファイルを参照するのか、またコード例が知りたいです。 ~~~下記は自分が使っているコードの一部です~~~ images_placeholder = tf.placeholder("float", shape=(None, IMG_PIXELS)) keep_prob = tf.placeholder("float") logits = inference(images_placeholder, keep_prob) sess = tf.InteractiveSession() saver = tf.train.Saver() sess.run(tf.global_variables_initializer()) saver.restore(sess, "model.ckpt") 質問者: nyannyan tensorflow r12よりcheckpointファイルのフォーマットが変更されております。 とりあえず過去フォーマットでsaveしたいのならば import tensorflow as tf from ...
jsonのtrueをTrueにしたい [クローズ済み] – python
質問: json = {"Hi":true} このHiのtrueをTrueにして論理演算できるようにしたいです。 質問者: たかなし json.dumps を使ってPythonのオブジェクトに変換できます。 >>> import json >>> d = json.loads('{"Hi":true}') >>> d {'Hi': True} 出典
tkinter の bad geometry specifier “200*100” というエラーの意味がよくわからない – python python3 tkinter
質問: このプログラムを実行しようとすると というメッセージが表示されます。 何が悪いのかよくわからないので一度Pythonをアンインストールして最新のPythonを再インストールしたのですが結果は変わりませんでした。 インストールする前のPathのチェック欄にはチェックを入れました。 すごく初歩的なことで恐縮ですが、お願いします。 質問者: 岸本真人 Kohei TAMURA 200*100ではなく、200x100ではないですかね。 tkinter の使い方は独特な所があり、色々とつまずくかも知れません。 使い方が解らないメソッドなどは help 関数などで説明を読むことができます。今回ですと、Pythonコード内で help(root.geometry) とすると、 Help on method wm_geometry in module tkinter: wm_geometry(newGeometry=None) method of ...
pythonからツイートの保存について – python twitter
質問: 下記のツイートを保存したいのですが上手くいきません。実行中でpython intento.py >> result.dat を書きました。 #-*- coding: utf-8 -*- from tweepy.streaming import StreamListener from tweepy import OAuthHandler from tweepy import Stream import json # Variables that contains the user credentials to ...
pythonパラメータエラーに関して(スクレイピング) – python
質問: いつもお世話になっております。 再度みなさまの知見をお借りしたく質問させていただきます。 ただいま、pyrhonでスクレイピングに挑戦をしていました。 実践しようとしているのはJRAのページの馬柱をスクレイピングしようとしていました。 url ='http://www.jra.go.jp/JRADB/accessD.html' fetched_dataframes = pandas.io.html.read_html(url) ...
スロットマシンのフロー図 [クローズ済み] – アルゴリズム
質問: スロットマシンのフロー図を作りたいのですが、 スタートボタンを押すと3つのマスがそれぞれピロピロする。 それぞれのマスには、1~9の数字が1つづつ存在。 ストップボタンは3つあり、それぞれのマスをストップする。 3つの数字が揃えば、アタリと表示する。 3つの数字が揃わないとき、ハズレと表示する。 (ストップボタンをおさないと、10秒で自動停止する。) この仕様だとどうやって作っていきますか? また、繰り返し処理はいらないですよね? 質問者: user10383 おそらく。繰り返し処理=ある条件を満たしてなければ、もう一度繰り返す処理を指していると思いますので、 ストップボタンを押さないと10秒で停止する、をより正確に条件を書くと、おそらくスロットマシンの動きですので、 "すべての"ストップボタンが押されているか 開始してから10秒間経過した このどちらかを満たすまで、スロットマシンは動き続ける、つまり動くことを繰り返します。 では「具体的に何を繰り返す」のかを考えてみましょう。実は既に答えは書いています。 1または2の条件を満たしてスロットマシンの数字は停止します。 停止したときに3つの数字が全て同じであるかを判定しましょう。 文字だけで書くとわからないこともありますので、フロー図なので図示されると良いでしょう。 環境が書いてないのですが、ロジックだけをフローに落とすのでしょうか? >繰り返し処理はいらないですよね? なぜそう思ったのでしょう? 数字の表示にしても、10秒間ボタン押下を待つにしても、 (イベント処理でもしない限り)繰り返しがないと何も出来ないと思いますが? 出典
異なるwebページからの情報取得を一本化したい – python
質問: 現在、Pythonを学習しています。 Google検索APIで「東京都 会社概要」と検索し、検索結果の各webページのURLを取得し、 それらのURL先をスクレイピングして会社概要を取得しようと考えています。 当たり前のことですが、各webページのhtmlの書き方が異なっていて、tableタグだったり、liタグだったりで上手く求めている情報を抽出できません。 何かアイデアがあれば教えて頂きたいです。 # コード1.googleAPI検索し、結果をjsonファイルに出力 import json import urllib.request import urllib.parse from urllib.request import urlopen QUERY = u'会社概要+東京都' key = 'KEY' cx = 'CX' NUM = 3 cseurl = 'https://www.googleapis.com/customsearch/v1?' params = ...
tensor flow をjupyter notebookで使っているんですがtensor boardが使えません。 – python tensorflow
質問: 初心者です。 tensor flow をjupyter notebookで使っているんですがtensor boardが使えません。 下記のプログラムをjupyter notebook上で打ち込んでtensorboad --logdir=/path/to/log をターミナルで打ち込みましたがうまくいきません。 教えてもらえると有難いです。 import tensorflow as tf import numpy as np import os LOG_DIR = os.path.join(os.path.dirname("__file__"), 'log') if os.path.exists(LOG_DIR) is False: os.mkdir(LOG_DIR) w ...
サイトが表示されません。 – python linux ubuntu
質問: https://github.com/blobmon/simplechan 上の掲示板をネット上に設置したのですが、ホーム画面は表示されるのですが、そこからクリックをして入ったら本来表示されるべきものが表示されません。クリックしたらこんなものが出てきます。 psycopg2.OperationalError OperationalError: FATAL: Peer authentication failed for user "simplech_role" Traceback (most recent call last) File "/root/simplechan/venv/lib/python2.7/site-packages/flask/app.py", line 2309, in __call__ return self.wsgi_app(environ, start_response) File "/root/simplechan/venv/lib/python2.7/site-packages/flask/app.py", line 2295, in ...
python3のエラー “TypeError: Tensors … that don’t all match” がわからない – python python3 tensorflow
質問: Traceback (most recent call last): File "/Users/oshikawaakinobu/anaconda3/lib/python3.6/site-packages/tensorflow/python/framework/op_def_library.py", line 458, in _apply_op_helper raise TypeError() # All types should match. TypeError During handling ...
pip installコマンドでCould not open requirements file: [Errno 2] No such file or directory:というエラーが出る – python
質問: Colaというプログラムを使って、Weiboの投稿を取得したいです。pip install colaまではうまくいきますが 下記のコマンドを打つとエラーが表示されます。 エラーがなぜ起きるかわかる方がいれば教えてください。 # pip install -r/path/to/cola/app/weibo/requirements.txt Could not open requirements file: No such file or directory: '/path/to/cola/app/weibo/requirements.txt' 質問者: ...

You Might Also Like

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です