PSM

Pプログラミング S初心者の Mメモ書き

processingで遊んでみた

この記事では基本的に,
Built with Processingという本で紹介されている内容を
Pythonに書き直しながら勉強しています.

マウスを四角がおっかける

f:id:muromura:20180219184239g:plain

add_library('gifAnimation')

def setup():
    global speed, xPos, yPos, gifMaker
    size(400, 400)
    speed = 0.05
    xPos = 0
    yPos = 0

    gifMaker = GifMaker(this, "maze.gif")
    gifMaker.setRepeat(0)
    gifMaker.setDelay(10)


def draw():
    global xPos, yPos
    background(100)
    c1 = color(255, 255, 255, 255)
    fill(c1)
    stroke(c1)
    rectMode(CENTER)
    xDiff = (xPos - mouseX) * speed
    yDiff = (yPos - mouseY) * speed

    xPos -= xDiff
    yPos -= yDiff
    rect(xPos, yPos, 10, 10)

    gifMaker.addFrame()
    if (frameCount > 100):
        gifMaker.finish()
        exit()

ProcessingでPythonを使って見た

pythonの描画環境ってmatplotlib一択というところがあると思うんですが,
久方ぶりにprocessingを触っていてたまたまpythonでも書けることに気がついたので試してみました.

Javaの方が早いんだからええやんという話もありますが,
私のようなPythonくらいしか触れないプログラミングニワカ勢が世の中には他にもいらっしゃると信じて……


Processingとは

基本的にJavaベースで,
ちょっとした物理演算をしたりアニメーションを作ったりということが
お手軽にできる環境のことです.

パラメトリックデザインやコンピューテーショナルなアートが試しやすく,
アーティスト向けであるとも言えるらしいとのことです.

Processingの導入

processingで検索して一番上のサイトに行き,Downloadsから,自分の環境にあったものを導入します.
Download \ Processing.org
windows / Linux / os xそれぞれ用意されています.

注意点として1系2系3系があり,使える関数やパッケージが微妙に違うことがあります.
今回は2.2.1を使用してます.


ProcessingでPythonを使う

Python Modeをインストールします.
Skethの右上のJava▽となっている部分をプルダウンして
Add More -> Mode Manager で[Python]と検索します.
インストールが済んだらJava▽となっている部分をプルダウンして▽Pythonに変更します.

これでProcessingでPythonを使う準備が整いました.

また,実行結果をgifアニメーションで保存するために
sketch -> Import Library -> Add Libraryから[gifAnimation]と検索して
gifAnimationというパッケージをついでにインストールしておくと良いでしょう.


迷路生成

いつかの穴掘り方による迷路作成をProcessingに移行して実装してみました.
muromura.hatenablog.com

結果はこんな感じ
f:id:muromura:20180211201854g:plain

まとめ

情報系でない人間にとってはPythonの記法が一番シンプルで見返しても分かりやすい気がします.

流行りのデータサイエンスばかりでなく,
デザインもPythonで簡単にできる環境が整ってきたらいいなあと思っています(人任せ)

コード

ちょっと全体的に見苦しい感じになっていますが,
基本的には開始点と探索方向をランダムにした穴掘り法で迷路を生成してます.
fill()の中が見苦しいのは,描画色を探索順に波打つように変化させたかったからなんです......

add_library('gifAnimation')
import random
import math


def setup():
    global h, w, maze, wl, stt, stt2, ps, dr, gifMaker

    frame.setTitle("Maze")
    h = 45
    w = 45

    maze = [[1 if 0 < i < w - 1 else 0 for i in range(w)] if 0 < j < h - 1 else [
        0 for i in range(w)] for j in range(h)]  # path:0 wall:1
    wl = [[2 * i + 2, 2 * j + 2]
          for i in range(int((w - 1) / 2) - 1) for j in range(int((h - 1) / 2) - 1)]  # prepare wall
    stt = wl.pop(random.randint(0, len(wl) - 1))  # start point
    stt2 = stt
    ps = [stt]  # paths
    maze[stt[1]][stt[0]] = 0  # change start point to 0
    dr = [[-1, 0], [1, 0], [0, -1], [0, 1]]  # direction list of search

    size(h * 10, w * 10)
    frameRate(4000)
    noStroke()
    background(10)

    gifMaker = GifMaker(this, "maze.gif")
    gifMaker.setRepeat(0)
    gifMaker.setDelay(10)


def draw():
    global h, w, maze, wl, stt, stt2, ps, dr, gifMaker

    fill(255, 0, 255)
    rect(stt2[0] * 10, stt2[1] * 10, 10, 10)

    random.shuffle(dr)  # random order of search direction

    for i in range(4):
        nxtx = stt[0] + dr[i][0] * 2
        nxty = stt[1] + dr[i][1] * 2
        nxtx2 = stt[0] + dr[i][0]
        nxty2 = stt[1] + dr[i][1]

        if maze[nxty][nxtx] == 1:
            wl.remove([nxtx, nxty])  # remove searched point
            ps.append([nxtx, nxty])  # append searched point

            maze[nxty][nxtx] = 0  # 2 block
            maze[nxty2][nxtx2] = 0  # middle block

            fill(255, maze[nxty2][nxtx2] * 255 +
                 math.sin(frameCount ** 1.2 / 500) * 255, 255)
            rect(nxtx2 * 10, nxty2 * 10, 10, 10)

            fill(255, maze[nxty][nxtx] * 255 +
                 math.sin(frameCount ** 1.2 / 500) * 255, 255)
            rect(nxtx * 10, nxty * 10, 10, 10)
            break

    if i == 3:  # end of direction
        ps.remove([stt[0], stt[1]])

    gifMaker.addFrame()
    if (len(ps) == 0):
        gifMaker.finish()
        exit()
    else:
        stt = ps[random.randint(0, len(ps) - 1)]  # next point

Python3で迷路生成

pythonで迷路生成を実装したのでメモしておきます.
今回は穴掘り方を使用しました.

前置き

穴掘り法については[迷路 穴掘り法]で検索していただくとして.

非常に眠いのであまり丁寧に説明できませんが,基本的に以下の点を工夫しています.
・外周を通路に設定して探索点の内外判定を省略
・[偶数,偶数]となる点群のみを探索候補としてもっておくことにより高速化

コード

import random

# 幅と奥行きの設定 (どちらも奇数である必要がある)
height = 25
width = 35
maze = [[1 if 0<i<width-1 else 0 for i in range(width)] if 0<j<height-1 else [0 for i in range(width)] for j in range(height)] #通路:0 壁:1


def mazeprint(maze):  #数字で表現された面を●や◯に変換する関数
    c_dict={0:"□",  1:"■"}
    c_maze = [[c_dict[maze[j][i]] for i in range(width)] for j in range(height)]
    for i in range(height):
            print("".join(c_maze[i]) )
    print("")

#開始点を定める
wl = [[2*i+2,2*j+2] for i in range(int((width-1)/2)-1) for j in range(int((height-1)/2)-1)] #未探索リスト
stt = wl.pop(random.randint(0, len(wl)-1)) #ランダムに開始点を定める
ps = [stt]  #探索済みリスト

print("start Point: ", stt)
maze[stt[1]][stt[0]] = 0  #壁(1)を通路(0)に書き換える
mazeprint(maze)  #迷路出力



#探索する
dr =[[-1,0], [1,0], [0,-1], [0,1]] #探索方向のリスト

while(len(wl)>0): 
    random.shuffle(dr)  #探索方向順をランダムに
    for i in range(4):  #このfor文内ではある座標sttの周辺4方向に対する探索のみ行う
        nxtx = stt[0]+dr[i][0]*2 #探索候補のx座標
        nxty = stt[1]+dr[i][1]*2 #探索候補のy座標
        if maze[nxty][nxtx]==1 :  #2マス先が通路でないとき
            wl.remove([nxtx,nxty])  #未探索リストから削除
            ps.append([nxtx,nxty])  #探索済みリストに追加
            maze[nxty][nxtx] = 0 #2マス先を通路に変更
            maze[nxty-dr[i][1]][nxtx-dr[i][0]] = 0 #1マス先を通路に変更
            break
            if i==3:
                ps.remove([nxtx,nxty])
        stt = ps[random.randint(0, len(ps)-1)]

#完成した迷路を出力
mazeprint(maze)

できた迷路

この方法だと迷路が開始点から放射状に広がることは避けられませんが,
このくらいのサイズならあまり気にならずに綺麗にできるようです.
f:id:muromura:20180201083729p:plain

collections.dequeについて

「え〜まだlistしか使い方わかんないの〜?」
「dequeくらい使えて当たり前だよね〜〜」
という啓示を得たのでメモします

listと比べて良いところ

listは,最後尾の要素をいじるappendとかの操作は早いんですが,先頭要素を加えたり削除したりしようとすると途端に遅くなります.
この点,dequeは双方向連結リストなので,先頭要素を操作するのも高速で行うことができるようになっています.

準備

collectionsをimportし,aという名前で dequeを準備します

import collections.deque
a = deque([1,2,3,4,5])

最後尾に要素を加えたい/削除したい

listと同じで,append/popを使います

#最後尾に要素を加える
a.append(0) #要素を加える
print(a)

#最後尾から要素を取り除く
print(a.pop()) #要素そのものも取り出せる
print(a) 

先頭に要素を加えたい/削除したい

pythonは左から右に流れる言語なので(逆は存在するのだろうか?)
先頭ということは即ち最も左側であるということになります.
よってappend/popにleft(左)を付け加えたappendleft/popleftを使います.

a.appendleft(9)
print(a)

print(a.popleft())
print(a)

まとめ

dequeを使ってLet's高速化

map関数とlambda式

python始めて1年くらい,map関数について復習するついでに,ようやくlambda式について勉強しました.

map関数

競技プログラミングをやっていて,標準入力を受け取るときに何も考えずに

a = list(map(int, input().split()))

とか書いたりしてますが,実はこのmapっていう関数は何?intとinput().split()って2つの引数あるけどこれ何?と実はあまり知らない状態が続いていました.

調べた結論から言うと,map()というのは1つ目の引数で指定した名前の関数を2つ目の引数で指定したリストの要素一つ一つに当てはめていってくれる関数のようです.
つまり,ここではinput().split()で受け取られた入力のリスト(str型)を,一つづつ全てint型に変換してくれるという処理を行なっているわけでした.

ここではintという関数を使っていますが,この部分には自分で定義した関数を用いることができます.
例えば引数の2乗を返す関数fを定義して,

def f(a):
    return a**2

list(map(f, [1,2,3,4]))

とすれば

[1, 4, 9, 16]

とやってくれます.便利ですね.
注意点ですが,map関数はそのままでは結果をmap objectという形式で返すようになっているため,printなどがしたい場合はlistをかませる必要があります.

lambda式

ところで,上の式では自作関数fをいちいち定義していましたが,これをもっとスマートにやる書き方があります.
それがlambda式です.

正確に言うとlambda式は,無名関数を定義する記法の1つであり,関数の定義文を式として扱うことができるのです.
...なんのこっちゃっていう話ですね.
調べたところによると,lambda式は

lambda 変数:返り値の定義

のように書くとのことです.実際に書いて動かしてみます.

lambda a: a>0

すると,

<function __main__.<lambda>>

なるほど,よくわかりませんが,ちゃんと関数として定義されているようです.

この関数に実際に変数を与えて処理を行わせるには,以下のように書きます.

(lambda a: a>0 )(1)

このように書けば,変数の1が0より大きいかどうかの判定が行われ,

True

と帰ってきます.

lambda式は式なので当然変数に与えることもできて,

f = lambda a: a>0 

と関数定義のように書くこともできます.この変数fは,map関数のときに普通に定義したfのように使うことができて

f(1)
True

となります.

さて,ここからがlambda式の便利なところです.
これを使えば,上のような0より大きいかどうかを判定する関数を,引数としてmap関数に直接与えることができます.
つまり,1行で書けます.

list(map(lambda a:a>0, [-1,0,1]))

結果は

[False, False, True]

便利ですねえ.

競プロ用メモ

python競技プログラミングの問題を解いていて,テクニックをまとめました.
ちょくちょく使うのに覚えてなくて,その度になんだっけって調べるやつです.

文字列を1文字ごとのリストに変換する

list()をかませるだけ

print(list("letters"))
['l', 'e', 't', 't', 'e', 'r', 's']

リストを1つの文字列に変換する

ほかのとこでも書いた気がする.joinを用いるのが定石.

l = ['l', 'e', 't', 't', 'e', 'r', 's']
print("".join(l))
letters

リスト内の要素の個数を数える

collectionsを使うのが早いし簡単らしい.

a = [1,2,3,5,2,1,3,4]
import collections
c = collections.Counter(a)

数えた結果は以下のように呼び出せる.

print(c)
print(c[2])
print(c.keys())
print(c.values())
Counter({1: 2, 2: 2, 3: 2, 5: 1, 4: 1})
2
dict_keys([1, 2, 3, 5, 4])
dict_values([2, 2, 2, 1, 1])

英小文字,英大文字のリストの作り方

アルファベットって何文字あるんだか,たまにわからなくなる.

lowl = [chr(i) for i in range(97, 97+26)]
uppl = [chr(i) for i in range(65, 65+26)]
['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z'] 
 ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z']

二次元リストをフラットにする

itertoolsを用いると早い.

l = [[1,2,3], [4,5,6]]
from itertools import chain
flatten_l = list(chain.from_iterable(l))
[1, 2, 3, 4, 5, 6]

初めてAtCoder Beginner Contestで全完した話

競技プログラミングというものを初めて1ヶ月経ちました.
情報系の専攻とかでは全くなく,最初は「プログラミング?よくわかんないけど頭めちゃくちゃ良くないとできなさそう……」とひたすらビビりまくっていましたが
,徐々にその面白さにハマりつつあります.

さて,そんな私ですが,今回は競プロサイトの1つであるAtCoderでほぼ毎週行われているAtCoder Beginner Contest (ABC)で初めて全完することができました.しかも全問1発AC!

正直に言ってめちゃくちゃ嬉しかったので,浮かれて攻略日記みたいなのを書くことにしました.
(たぶん今回はたまたま簡単な問題が多かったのだとは思いますが,それでも嬉しいものは嬉しいです.)
自分が実際に考えた内容なので模範回答ではないかもしれませんが,悪しからず.

A問題

東西n本,南北m本の街路に囲まれた街区の数を求める問題.

それぞれから1引いて掛けたのを出力するだけ.

# K-City
n,m = list(map(int, input().split()))

print((n-1)*(m-1))

B問題

与えられる1単語を所定のルールによって略す問題.

pythonのstr型はリストとして扱えることを知っていれば簡単.
リストの最後尾の要素はlist[-1]で呼び出せる.

# i18n
s = input()

print(s[0]+ str(len(s)-2) +s[-1] )

C問題

ある数列が与えられたとき,それを並び替えることでどの連続する二数の積も4の倍数となるような数列を作れるか判定する問題.

まず,4の倍数を●とそれ以外の数を○で表してみたとき,
○●○●・・・●○●○
のように交互に並べられるならば,その数列は条件を満たす.
さらに○のうち「2の倍数であって4の倍数でない数」を▲で表し,「2の倍数でも4の倍数でもない数」を△と表す.
(注意:全ての数字は●,△,▲に重複なく分類できる)

▲×△は2の倍数でしかないが,▲×▲は4の倍数になる.もちろん▲×●は4の倍数である.
▲が偶数個あるならちょうど2つずつ隣同士ペアを作ることができるので,残りの△と●が交互に並べられるかを考えれば良いし,▲が奇数個あるなら△が一つ増えたと考えて交互に並べられるか考えれば良い.

● : 4で割ったあまりが 0
△ : 4で割ったあまりが 1 or 3
▲ : 4で割ったあまりが 2
なので,与えられた数列を4で割ったあまりの数列に変換して考える.

# 4-adjacent
N = int(input())
a = list(map(int, input().split())) 

b = [a[i]%4 for i in range(N)] #4で割ったあまり
if ( b.count(2)%2 + b.count(1) + b.count(3) > 1 + b.count(0) ):
    print("No")
else:
    print("Yes")

D問題

長方形のマス目を塗り分ける問題.

問題をよく読んで,ぐねぐねと折り返しながら蛇のようにマス目を塗っていけば良い,ということに気がつけば簡単.
かかった時間の大半はpythonでどう実装するかググるのに費やした.
(調べた内容:リストを高速にflattenする方法,リストを逆順にする方法,リストの出力時に半角スペースを挟む方法)

# Grid Coloring
H,W = list(map(int, input().split()))
N = int(input())
a = list(map(int, input().split()))
 
from itertools import chain
b = list(chain.from_iterable([[i+1]*a[i] for i in range(N)]))  #指定された数だけ色iを並べたリストをつくる
c = [b[i*W:(i+1)*W] if i%2==0 else b[i*W:(i+1)*W][::-1] for i in range(H)]  #リストをHずつで切る.奇数列の時はlist[::-1]の表記を使ってリストを逆順にする
 
for i in range(H):
    print(' '.join(map(str, c[i])))  #半角スペースを間に挟みながら出力する

結果

A問題 01:51 (01:51)
B問題 03:51 (02:00)
C問題 13:06 (09:15)
D問題 36:13 (23:07)