python; checkio日記

checkioを中心にpythonプログラミングの記録

Elementary 問題 絶対値での並び替え

[-3, 2, 1, -8]なら[1, 2, -3, -8]と並び替える。 リストのindexを取り出してそれで並び替えるというようなことをしたいが、関数を知らないので力技で

def checkio(x):
    ans=[]
    order = sorted([abs(i) for i in x])
    for i in range(len(order)):
        for j in x:
            if abs(j)==order[i]:
                ans.append(j)
    ans
    return ans

Brute Force を使って、あらゆる並び替えを作って、

return x if x == sorted.array

みたいなのでシンプルにもできるかと考えたが並びかえの関数も知らないので、さっさと解いてしまって、他の人の答えで学ぶ。

sorted(x, key=abs)

sortedにkeyオプションがあるのですね 今回はabsをそのまま使えたが、ここを自作の関数にしたい場合は、下記のようにlambdaを使ってつなげればよいようです。

key=lambda x:abs(x)

Elementary 問題 Fizz Buzz

3で割り切れたらFizz、5で割り切れたらBuzz、15で割り切れたらFizz Buzzを、それ以外ではそのままの番号を(文字列で)返す問題

def checkio(x):
    ans = (x%3 == 0)*'Fizz' + (x%15 ==0)*' ' + (x%5 ==0)*'Buzz'
    if ans =='':
        return str(x)
    else:
        return ans

としていたが、他の人の答えをみて勉強。
空の文字列はFalse、そうでない文字列はTrueのようにif文の中で扱うことが出来るらしい。ということで、

def checkio(x):
    ans = (x%3 == 0)*'Fizz' + (x%15 ==0)*' ' + (x%5 ==0)*'Buzz'
    return ans if ans else str(x)

Lambdaで一行にかっこよくできたらすっきりするが。。

類似の一つ前の問題(最大の数と最小の数の差を求めるが、空の時は0を返す)は上記を利用して、すっきり

checkio =  lambda *x: max(x)-min(x) if x else 0

Elementary問題 辞書中で最大valueを持つkey

辞書中の最大の値を持つkeyを求める関数

def best_stock(data):
    return ''.join([i for (i, j) in data.items() if j==max(data.values())])

としたが、全くいけてない。
一番エレガントなのは

best_stock = lambda data: max(data, key=data.get)

このdata.getの使いについてはあんまり理解しがたいが、覚えておこう。
ただし、maxは一つしか値を返さないので、もし最大値が2つある場合には不適。

Elementary 問題 Correct sentence

英文の最初を大文字にして、最後にピリオドを打つ。もし正しく書いてあればそのままという関数

def correct_sentence(text: str) -> str:
    ans = text[0].upper()+text[1:]
    if text[-1] != '.':
        ans = ans + '.'
    return ans

下記には唸った。真偽判定を掛け算にすることでうまく一つにまとめている。

lambda t: t.capitalize() + "." * (t[-1]!=".")

これは使いたいテクニックです。 ところで、->strってなんなんだろう?

Electric Station 問題 Largest rectangular

今回も説明が難しいですが、一番大きな長方形の面積を返す問題。

  1. iterableにリストの数字を前から選ぶ (num)
  2. 選択された数字より大きな数字が右に何個連続しているか調べる (a)
  3. 反対方向にも調べる。(b)
  4. num*( a - b + 1)が面積

という方向性で考えました。
まずは覚えたてのRecursionを使って、

def largest_histogram(test):
    N = len(test)
    def index(x, dir, num):
        if 0<=x+dir< N and num <= test[x+dir]:
            return dir + index(x+dir, dir, num)
        else:
            return 0
    loc_val = []
    for i in range(N):
        start = index(i, -1, test[i])
        stop  = index(i,  1, test[i])
        loc_val.append( test[i]*(stop - start + 1)   )
    return max(loc_val)

でも、これ同じoperator (test[i])が何度も出てくるのであんまり効率が良くないなぁ。 Brute forceでやる場合は、前から順番にあらゆる組み合わせで数字を切っていって、その中で

  • 一番小さい数字*長さ

でやるやり方。シンプルに下記のように書けますが、O(CN)なので、時間はかかりますね。

def largest_histogram(test):
    return max([min(test[i:j])*(j-i) for i in range(len(test)) for j in range(i+1, len(test)+1)])

Electric Station 回文問題(The Longest Palindromic)

今回は与えられたテキスト内でもっとも長い回文を探します。

  • 前から一文字ずつ判定
  • 同じ文字で切れるところを探し
  • 反転しても一致するかを調べる

という方向性でやりました。

def longest_palindromic(test):
    ntest =  [(i,test[i]) for i in range(len(test))] # enumerate
    comb=[]
    for i in range(len(test)-1):  
        comb.extend([(test[i:(x+1)],x-i+1) for (x, y) in ntest[i+1:] \
            if (y == test[i] and test[i:(x+1)]==test[i:(x+1)][::-1])])
    if comb == []: # palidromic-negative
        return test[0]
    else:
        return sorted(comb, key=lambda x: x[1], reverse=True)[0][0]

ただ、2個目のステップで同じ文字を探さず、後ろから総当たりで探している人の方が多かった。 この場合、下記のようになる。

def longest_palindromic(test):
    N = len(test)
    for l1 in reversed(range(N)):
        for s1 in range(N - l1):
            text = test[s1:][:l1+1]
            if text == text[::-1]:
                return text

やっぱりこっちのほうがいいですね。。
なお、

test[s1:][:l1+1]

test[s1:s1+l1+1]

よりoperatorの重複を避けられるので好まれるとか。なるほど