PSM

python する man

fontからbitmapを作成する

持っているfontから英文字とか数字とかのbitmapつくってくれるのが欲しいなあと思っていたのでつくりました.

欲しいもの

こんな感じのbitmap
この例は"A"

[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0]
[0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0]
[0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0]
[0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0]
[0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0]
[0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0]
[0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0]
[0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0]
[0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0]
[1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1]
[1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

f:id:muromura:20180407040329p:plainf:id:muromura:20180407040335p:plainf:id:muromura:20180407040341p:plain
見辛いですがこんな感じにpngでも描き出せます.

スクリプト

from PIL import Image, ImageDraw, ImageFont


class Letter2BitMap:
    def __init__(self, fontFile):
        self.fontFile = fontFile
        
    def makeBitMap(self, letter = " ", fontSize=32):
        self.letter = letter #欲しい文字
        self.fontSize = fontSize #欲しいフォントのサイズ
        self.font = ImageFont.truetype(fontFile, self.fontSize, encoding='utf-8') 
        self.w, self.h = self.font.getsize(chr(ord(letter)))
        
        self.image = Image.new('RGB', (self.w, self.fontSize), (255,255,255)) #背景を白色で描画
        self.draw = ImageDraw.Draw(self.image) 

        self.draw.text((0, 0), chr(ord(self.letter)), fill=(0,0,0), font=self.font) #文字を黒色で描画
        self.bitmap =[1-int(self.image.getpixel((i,j))[0]/255) for j in range(self.fontSize) for i in range(self.w)] #bitmap list
    
    def getBitMap(self): #bitmapを返す関数
        return self.bitmap
    
    def printBitMap(self): bitmapを標準出力する関数
        for i in range(self.fontSize):
            print([self.bitmap[j + i*self.w] for j in range(self.w)])
    
    def showBitMap(self): #bitmapを見せる
        self.image.show() 
        
    def saveBitMap(self, path): #pngで保存する
        self.saveFileName = path+str(ord(self.letter))+".png"
        self.image.save(self.saveFileName)
        

"""
使い方
初期化のときにfont fileの位置を与えてください.
makeBitMap()メソッドで引数のサイズ・文字のbitmapを作ります.
そのほかのメソッドでpng書き出したり出力したりできます.
"""
fontFile =  "/System/Library/Fonts/Courier.dfont" #font fileの場所

courier = Letter2BitMap(fontFile)
courier.makeBitMap("A" 32)
courier.printBitMap()

ProcessingでPythonを使ってみる(実践編2)

前回
muromura.hatenablog.com
の続きでいろいろ試してみる

マウスとインタラクティブ

Built with Processingを参考に,マウスを押している間だけ散らばり,マウスを離すと元の位置に戻る四角形の集合体を実装しました.
f:id:muromura:20180405204634g:plain

import Dot
#add_library('gifAnimation')

def setup():
    global speed, wNum, hNum, dots, gifMaker
    size(800, 800)

    wNum = 20
    hNum = 20

    dotSize = 10  # size of dot
    dotMargin = 2  # margin between each dot
    dotUnit = dotSize + dotMargin  # the unit size of dots

    dots = [None for i in range(wNum * hNum)]
    for i in range(hNum):
        for j in range(wNum):
            dots[i * wNum + j] = Dot.Dot(dotSize, dotSize, width / 2 + dotUnit * (
                i - hNum / 2), height / 2 + dotUnit * (j - wNum / 2), 50, i * wNum + j)
    """        
    gifMaker = GifMaker(this, "dots_p.gif")
    gifMaker.setRepeat(0)
    gifMaker.setDelay(10)
    """

def draw():
    background(50)

    pat = mousePressed

    for i in range(hNum * wNum):
        dots[i].display()
        dots[i].move(0.01, pat)  # need speed of dots
    """
    gifMaker.addFrame()
    if (frameCount > 100):
        gifMaker.finish()
        exit()
    """

コメントアウトしてある部分はgif作成用です.

また,Dot classの定義は

class Dot:

    def __init__(self, w, h, x, y, clr, cnt):
        self.rectW = w
        self.rectH = h
        self.xPos = x
        self.yPos = y
        self.iniXPos = x
        self.iniYPos = y
        self.c = clr
        self.dotNum = cnt
        self.pattern = 0
        self.c1 = color(255, 255, 255, 255)
        self.nextX = x
        self.nextY = y

    def display(self):
        fill(self.c1)
        stroke(self.c1)
        rectMode(CENTER)
        rect(self.xPos, self.yPos, self.rectW, self.rectH)

    def move(self, speed, pattern):
        self.speed = speed
        self.pattern = pattern

        if self.pattern == 0:
            self.speed *= 10
            self.nextX = self.iniXPos
            self.nextY = self.iniYPos
        else:
            self.nextX += random(-width / 8, width / 8)
            self.nextY += random(-height / 8, height / 8)

        self.xDiff = (self.xPos - self.nextX) * self.speed
        self.yDiff = (self.yPos - self.nextY) * self.speed

        self.xPos -= self.xDiff
        self.yPos -= self.yDiff

Tips
・クラス定義などは,New Tabで新しいタブを作ってそこに書いておくとコードが見やすい
f:id:muromura:20180405205227p:plain
・上記のNewTabの内容は,python modeではsketchと同じディレクトリ内に.pyファイルとして保存される

ProcessingでPythonを使ってみる(実践編1)

前回
muromura.hatenablog.com
の続き


[:contens]

Pvectorを使う

f:id:muromura:20180328160203p:plain

def setup():
    global v1, v2
    noLoop() #draw once
    size(400, 300) #size of window
    v1 = PVector(100, 40)
    v2 = PVector(80, 120)


def draw():
    ellipse(v1.x, v1.y, 12, 12) #draw cicle
    ellipse(v2.x, v2.y, 24, 24)
    v2.add(v1) #pvector can be added
    ellipse(v2.x, v2.y, 36, 36)
    
    save("pvector.png") # save file

tips
pythonで書きたいときはvoid→defのように書き換えたりと,pythonの記法に直す
・save("ファイル名.拡張子")で描画結果を保存できる
・pVectorを使って点を扱える
・pVector ではpVector.xのようにしてx成分を抜き出したり,.addなどでベクトル全体の演算ができる



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

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()

Tips
・global変数はsetup()の中でまとめて宣言すると見やすい

pythonでdelaunay図

pVectorを使ってdelaunay図の実装.
(計算量がo(N^4)だしpythonだしで,めちゃくちゃ遅いです)
f:id:muromura:20180329195100p:plain

N = 50

def setup():
    global pVec
    size(800, 600)
    pVec = [None for i in range(N)]
    for i in range(N):
        pVec[i] = PVector(random(width), random(height))
    smooth()
    noLoop()  # draw once


def draw():
    background(255)

    stroke(0)
    for i in range(N - 2):
        v1 = pVec[i]
        for j in range(i+1, N - 1, 1):
            v2 = pVec[j]
            for k in range(j+1,N,1):
                v3 = pVec[k]

                tmp = 2.0 * \
                    ((v2.x - v1.x) * (v3.y - v1.y) -
                     (v2.y - v1.y) * (v3.x - v1.x))
                
                center = PVector(
                    ((v3.y - v1.y) * (v2.x * v2.x - v1.x * v1.x + v2.y * v2.y - v1.y * v1.y) +
                     (v1.y - v2.y) * (v3.x * v3.x - v1.x * v1.x + v3.y * v3.y - v1.y * v1.y)) / tmp,
                    ((v1.x - v3.x) * (v2.x * v2.x - v1.x * v1.x + v2.y * v2.y - v1.y * v1.y) +
                        (v2.x - v1.x) * (v3.x * v3.x - v1.x * v1.x + v3.y * v3.y - v1.y * v1.y)) / tmp
                )
                r = PVector.dist(center, v1) - 0.01

                flg = False
                for l in range(N):
                    if (PVector.dist(center, pVec[l]) < r):
                        flg = True
                        break
                if (not(flg)):
                    line(v1.x, v1.y, v2.x, v2.y)
                    line(v2.x, v2.y, v3.x, v3.y)
                    line(v3.x, v3.y, v1.x, v1.y)

tips
 ・line(始点のx座標,始点のy座標 , 終点のx座標, 終点のy座標)で線が引ける
 ・pythonではbooleanの反転はnot()



迷路生成

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

f:id:muromura:20180211201854g:plain

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

Tips
・探索終了とgif作成の終わりを分岐にまとめておくとすっきりする

ProcessingでPythonを使ってみる(導入編)

pythonの描画環境ってmatplotlib一択というところがあると思うんですが,
久方ぶりにprocessingを触っていてたまたまpythonでも書けることに気がついたので試してみました.
(Javaの方が早いんだからええやんという話もありますが……)


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というパッケージをついでにインストールしておくと良いでしょう.



まとめ

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

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

次はいよいよ実践編へ
muromura.hatenablog.com

穴掘り法で迷路生成

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

pythonで競プロやるときのメモ

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

pythonって2だったり3だったり紛らわしいし,調べてみてもコピペで動いてくれるスクリプトが載っている記事を見つけられなかったので,自分の検索能力のなさを嘆きつつ苦しんだ結果をメモ書き程度に残しておきます.
(環境はpython3.6.0を想定しています)

入力

1行に1つの入力を受け取る

28

とか

test

とかを受け取りたい時です.
たぶんどの言語でもそうなんでしょうけど,pythonでも入力関数を一回呼び出すごとに1行分の入力を読み込んでくれるようです.
というわけで,

a = input()

とすればaに入力を代入できます.

ただしこれだとintだろうとfloatだろうとstrだろうと何でもstr型で読み込んでしまうので,型変換までついでにやっちゃうなら

a = int(input())

のように書けます.

1行に複数の入力を受け取る

a b c d e

1 2 3 4 5

とかを受け取りたい時です.

文字列で受け取るなら

a = input().split()

とすると,半角スペースのところで区切ってリストにして受け取ってくれます.

型を指定して読み込むときには,変数が1つのときの場合のようには書けず,map関数を使う必要があります.
intで受け取りたいなら

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

となります.
注意点としては,python3ではmap()を使って読み込むとmap objectというものになってしまうので,list()で変換する必要があります.

また,受け取りたい入力が数個程度で,その数がわかっているならこんな風にもできました
たとえば

3 4

に対して

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

とすればaに3が,bに4がint型で代入されます.


複数行に複数の入力を受け取る

3
1 2 3
4 5 6
7 8 9

競プロでよくある,みたいなのを受け取りたい時です.

input()を一回呼び出すごとに1行分の入力を受け取ってくれるので,for文などで行数分呼び出すか,whileなどを使えば良いようです.
というわけで,

n = int(input())
a = []
for i in range(n):
    a.append(list(map(int, input().split())))

最初に空のリストを用意して,appendでどんどん突っ込んでいくという方針です.
numpyを使うならここでついでにnp.arrayにしておいても良いかもしれません.


出力

基本

python3では標準出力printが関数となっていました(python2系との違い).

print("output")

のように書きます.
勘違いしていたのですが,ここではint型も勝手に型変換して出力してくれるようなので,例えば

print(1234)

とint型を直接書いても,勝手に変換して"1234"と出力してくれます.
複数の引数をとることもできて,

n = 2
print("春が",n, "階から降ってきた")

とすれば

春が 2 階から降ってきた

リストを空白などの文字区切りで出力する

join()を用いると,リストの要素を任意の文字を糊にしてくっつけた文字列に変換することができます.
["君","羊","青"]を"と"でくっつくて"君と羊と青"にするイメージです.

s = ["君","羊","青"]
joined_s = "と".join(map(str, s))
print(joined_s)

とすれば

君と羊と青

"と"の部分を半角スペース" "などにすれば半角スペース区切りで出力できます.


リスト操作

文字列を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]

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)

map関数とlambda式

map関数とは

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

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

とか書いたりしてますが,実はあまりよくわかっていませんでした.
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 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]

便利ですねえ.


リスト内包表記

任意長の配列

[0, 0, 0, 0, 0, 0, 0]

例えば 上のような長さ7のリストが欲しい時は,

[0]*7

と書けばよいですが,リスト内包表記という”[]の中にfor文を書く”やり方でも作ることができます.

 [0 for i in range(7)]

基本形

 [i for i in range(7)]

出力は

[0, 1, 2, 3, 4, 5, 6]

一番左のiがリストの要素となっています.
この場合では,右側のfor文でiが0から1つずつ増えていくと定義されていることになります.
よって例えば以下のように一番左のiを(i+1)に変えると,

 [(i+1) for i in range(7)]

出力は

[1, 2, 3, 4, 5, 6, 7]

となります.

if(後置)

要素をifで判定してリストに加えるかどうか決めることもできます.
この場合,for文のあとにif文を書きます.

 [i for i in range(7) if i<5]

5より小さいiのみが要素として追加され,

[0, 1, 2, 3, 4]

となります.

if else

if elseを使いたい時は最初にもってくる必要があります.

 [i if i<5 else 4 for i in range(7)]

iが5より小さい時はそのままiが要素となり,iが5以上のときは4が要素となります.

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

集計

リストなどで集計関数がそのまま使えます.例えば,

sum( [(i+1) for i in range(7)])

について,全要素の和となるので

28

が得られます.28は完全数ですね.

2重for

forを2回重ねることもできます.

[[i,j] for i in range(2) for j in range(5)]

この場合はiが2通り,jが5通り動くので,長さ10のリストができます.

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

Python3でグラフの実装

pythonでのグラフとその探索の実装の仕方が分からず,悲しい思いをしたのでまとめました.

グラフの入力

ノードとエッジに関する情報は,競技プログラミングでよくあるように以下の形式で与えられるとします.
ノード(頂点)数はNで,a_i番目のノードとb_i番目のノードをi番目のエッジが結んでいることを表しています.

N
a1 b1
・
・
・
aN bN

今回使う数値例はこちら.
ノード数7,エッジ数6のグラフを考えてみます.

7
3 6
1 2
3 1
7 4
5 7
1 4

図にするとこんな感じです.
f:id:muromura:20170716021330p:plain


このグラフの入力は,例えば以下のように書いて受け取ることができます.

n = int(input())
p = []
for i in range(n):
    p.append(list(map(int, input().split())))

さて,このようにして情報を受け取ったとすると,いま,情報を以下の形式で持っています.

n=7  #ノード数
p = [[3,6], [1,2], [3, 1], [7,4], [5,7], [1,4]] #エッジ

つぎに,このグラフをプログラミングでどう表現するのか見てみます.

グラフの表現

グラフの実装の仕方は隣接リストと隣接行列の2通りあります.
どちらも一長一短あり,隣接リストはメモリの消費量
が少ない,隣接行列は直観的に分かりやすいなどの特徴があります.

そんな隣接リストの実装は以下となります.

#隣接リスト
l = [[] for i in range(n)]
for pi in p:  #0-originedに注意
    l[pi[0]].append(pi[1])
    l[pi[1]].append(pi[0])
print(l)

pythonは0-originな言語なので,このような書き方をすれば当然,隣接リストの先頭要素は[]となってしまいます.
しかし,今回はそれで大丈夫です.
違和感はありますが,無理に詰めるより頂点iについての情報がそのままi番目に格納されてくれていた方が,なにかと考えやすくてコードを書く時に便利です.

重みありの場合は以下のように情報が与えられます.

n=7  #ノード数
p = [[3,6,1], [1,2,2], [3, 1,3], [7,4,4], [5,7,5], [1,4,6]]

ここで,各要素の3番目が重みを表しています.
図にするとこんな感じ.赤い数字が重みを表しています.
f:id:muromura:20170817181213p:plain


重みありの場合は,[繋がっている頂点, 重み]としたリストを各頂点に突っ込んで行きます.

lw = [[] for i in range(n+1)]
for path in p:
    lw[path[0]].append((path[1],path[2]))
    lw[path[1]].append((path[0],path[2]))
print(lw)

隣接行列についても重みありと重みなしでメモしておきます.
こちらは[i-1, j-1]要素をノードiとノードjの接続情報の格納場所とし,重みなしのときは「繋がっている/いない」で「0/1」の2値を,重みありのときは重みを代入するだけなので簡単です.

#重みなし
m =[ [0]*n for i in range(n)]
for path in p:
    m[path[0]-1][path[1]-1] = 1
print(m) 

#重みあり
mw =[ [0]*n for i in range(n)]
for path in p:
    mw[path[0]-1][path[1]-1] = path[2]
print(mw)