"""
input: 5, 6, 7, 1, 2, 8
output: 5, 6, 7, 8

solution: dynamic
"""

def LongestUpSeq(A):
    dp = [1] * len(A)
    for i in range(1, len(A)):
        dp[i] = max(dp[i], dp[i], *(dp[j] + 1 for j in range(i) if A[j] < A[i]))
    return max(dp)

def main():
    A = [5, 6, 7, 1, 2, 8]
    print(LongestUpSeq(A))

if __name__ == "__main__":
    main()

"""
input: 1, 3, 4, 5, 5; 2, 4, 5, 5, 7, 6
output: 4, 5, 5

solution: dynamic
"""

def LongestSubSeq(s1, s2):
    dp = [[0] * len(s2) for _ in range(len(s1))]
    maxSeq, maxI, maxJ = 0, 0, 0
    for i, a in enumerate(s1):
        for j, b in enumerate(s2):
            if a == b:
                dp[i][j] = dp[i-1][j-1] + 1
                if dp[i][j] > maxSeq:
                    maxSeq = dp[i][j]
                    maxI, maxJ = i, j
            else:
                dp[i][j] = 0
    return s1[maxI-maxSeq+1:maxI+1], s2[maxJ-maxSeq+1:maxJ+1]

def main():
    s1, s2 = [1, 3, 4, 5, 5], [2, 4, 5, 5, 7, 6]
    print(LongestSubSeq(s1, s2))

if __name__ == "__main__":
    main()
    

"""
input: sequence
output: num of subseq 

solution: dynamic
"""


def countSubSeq(A):
    dp = [2] * len(A)
    d = {A[0]: 0}
    for i, a in enumerate(A[1:]):
        dp[i+1] = dp[i] * 2
        if a in d:
            dp[i+1] -= dp[d[a]]
        d[a] = i + 1
    return dp[-1] - 1


def main():
    A = [4, 13, 14, 1, 4, 2, 3]
    print(countSubSeq(A))


if __name__ == "__main__":
    main()

"""
input: aabcc, dbbca -> aadbbcbcac
output: true

solution: dynamic
"""


def IsInterleave(s1, s2, s3):
    if len(s1) + len(s2) != len(s3):
        return False
    dp = [[False] * (len(s2) + 1) for _ in range(len(s1)+1)]
    dp[0][0] = True
    for i in range(len(s1) + 1):
        for j in range(len(s2) + 1):
            if (i - 1 >= 0 and dp[i-1][j] and s1[i-1] == s3[i+j-1]) or \
                    (j - 1 >= 0 and dp[i][j-1] and s2[j-1] == s3[i+j-1]):
                dp[i][j] = True
    return dp[len(s1)][len(s2)]

def main():
    s1, s2, s3 = "aabcc", "dbbca", "aadbbcbcac"
    if IsInterleave(s1, s2, s3):
        print("s1, s2, s3 is right")
    if not IsInterleave(s1.replace("a", "c"), s2, s3):
        print("ok")

if __name__ == "__main__":
    main()

# -*- coding: utf-8 -*-
"""
学習2日目のメモ。

前回移行に得た知識。
スキーマとプリムの違い。
スキーマクラスとはMayaのMFnMeshみたいなもの。
UsdGeomMeshは IsA(～は～である)スキーマで、継承関係の型用。

移動したりするにはUsdGeom.XformableのAddTranslateOp等を使うのが一般的。
XformCommonAPIはあまり一般的ではない（用途が別）

VSCode+Jupyterでやると色々幸せ。
"""

# %%

import os.path
from pxr import Usd, UsdGeom, Sdf, Gf

# %%
# ファイルではなくメモリにシーンを作る
stage = Usd.Stage.CreateInMemory()
# シーンに対してPrimを追加する。
xf = UsdGeom.Xform.Define(stage, "/hello")
cam = UsdGeom.Camera.Define(stage, '/hello/camera')
# スキーマオブジェクトを指定のStageから取得したい場合は↓
UsdGeom.Xform.Get(stage, '/hello')
# Transに値を入れる
xf.AddTranslateOp().Set((1, 2, 3))
# 結果を表示
print(stage.ExportToString())

# %%
# アトリビュートを追加するためにスキーマオブジェクトからPrimを取得
prim = cam.GetPrim()
attrMat4d = prim.CreateAttribute('myMatrix', Sdf.ValueTypeNames.Matrix4d)
attrMat4d.Set(Gf.Matrix4d(1))
print(stage.ExportToString())

"""
input: Julytype, Jultypt
output: 3

solution: dynamic
"""


def editDistance(s1, s2):
    d = [[0] * len(s2) for _ in range(len(s1))]
    for i in range(len(s1)):
        d[i][0] = i + 1
    for j in range(len(s2)):
        d[0][j] = j + 1
    for i in range(len(s1)):
        for j in range(len(s2)):
            if s1[i] == s2[j]:
                d[i][j] = d[i-1][j-1]
            else:
                d[i][j] = 1 + min(d[i][j-1], d[i-1][j])
    return d[len(s1)-1][len(s2)-1]


def main():
    s1 = "Julytype"
    s2 = "Jultypt"
    print(editDistance(s1, s2))


if __name__ == "__main__":
    main()

"""
input: Julytype, Jultypt
output: 2

solution: dynamic
"""


def editDistance(s1, s2):
    d = [[0] * len(s2) for _ in range(len(s1))]
    for i in range(len(s1)):
        d[i][0] = i + 1
    for j in range(len(s2)):
        d[0][j] = j + 1
    for i in range(len(s1)):
        for j in range(len(s2)):
            if s1[i] == s2[j]:
                d[i][j] = d[i-1][j-1]
            else:
                d[i][j] = 1 + min(d[i][j-1], d[i-1][j], d[i-1][j-1])
    return d[len(s1)-1][len(s2)-1]


def main():
    s1 = "Julytype"
    s2 = "Jultypt"
    print(editDistance(s1, s2))


if __name__ == "__main__":
    main()

"""
input: [3, -4, 2, 4, -3, -1, 7, -6, 5]
output: 30240

description: don't use divide, biggest (n - 1) multiplies 

solution: dynamic
"""


def maxMultiply(A):
    s1, s2 = [1] * len(A), [1] * len(A)
    for i in range(1, len(A)):
        s1[i] *= s1[i-1] * A[i-1]
    for i in range(len(A)-2, -1, -1):
        s2[i] *= s2[i+1] * A[i+1]
    for i in range(len(s1)):
        s1[i] *= s2[i]
    return max(s1)


def main():
    A = [3, -4, 2, 4, -3, -1, 7, -6, 5]
    # from functools import reduce
    # print(reduce(lambda x, y: x * y, A))
    print(maxMultiply(A))


if __name__ == "__main__":
    main()

"""
input: [-2.5, 4, 0, 3, 0.5, 8, -1]
output: 3 * 0.5 * 8

solution: dynamic
"""


def MaxProductSubArray(A):
    Min, Max = A[0], A[0]
    maxResult = A[0]
    for a in A[1:]:
        end1, end2 = Min * a, Max * a
        Max = max(max(end1, end2), a)
        Min = min(min(end1, end2), a)
        maxResult = max(maxResult, Max)
    return maxResult


def main():
    A = [-2.5, 4, 0, 3, 0.5, 8, -1]
    print(MaxProductSubArray(A))


if __name__ == "__main__":
    main()

"""
input: sorted Matrix, key
output: key in Matrix ?

solution: search from right-up position
"""

def find(Matrix, key) -> bool:
    width, height = len(Matrix[0]), len(Matrix)
    startX = 0
    startY = width - 1
    while 0 <= startX < height and 0 <= startY < width and Matrix[startX][startY] != key:
        if Matrix[startX][startY] > key:
            startY -= 1
        else:
            startX += 1
    if not (0 <= startX < height and 0 <= startY < width):
        return False
    return True

def main():
    matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
    if find(matrix, 7):
        print("7 is in matrix")
    if not find(matrix, 10):
        print("10 is not in matrix")

if __name__ == "__main__":
    main()