36461


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

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

[code]

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

となっています。

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

[code]

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

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

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

        [".",".",".",".",".","."],
        [".",".",".",".",".","."],
        [".",".",".",".",".","."],
        [".",".",".",".",".","."],
        ["#",".",".",".",".","."]
    ]
    
[/code]

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

[code]     array=[

        [".",".",".",".",".","."],
        [".",".",".",".",".","."],
        [".",".",".",".",".","."],
        [".",".",".",".",".","."],
        ["#",".","#","#","#","."]
    ]
    
[/code]

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

        [".",".",".",".",".","."],
        [".","#","#","#",".","."],
        [".","#","#","#",".","."],
        [".","#","#","#",".","."],
        ["#",".","#","#","#","."]
    ]
    
[/code]

と array を書き換えます。

最終的に、

[code]

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

を出力させたいです。

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

今の断片コードですが、

[code]

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

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


CC BY-SA 3.0
2017-07-17T12:06:21.073
36451
2017-07-18T06:17:51.463
2017-07-17T23:55:10.863
19110
24451
question
python アルゴリズム
指定した通りに配列の要素を書き換えたい


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

[code]

    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
    =>    
    [['.', '.', '.', '.', '.', '#'],
     ['.', '#', '#', '#', '.', '#'],
     ['.', '#', '#', '#', '.', '#'],
     ['.', '#', '#', '#', '.', '#'],
     ['#', '.', '#', '#', '#', '#']]
    
[/code]

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

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

  * `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`
なので、

[code]

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

をチェックする事になります。これ以降(例えば `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+1` と `r+1` はどういう意味なのでしょうか？

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


CC BY-SA 3.0
2017-07-18T03:39:38.277
36461
2017-07-18T06:17:51.463
2017-07-18T06:17:51.463
36451
answer