깃헙갤 과제 풀이들

hs01.hs

{- https://gall.dcinside.com/mgallery/board/view/?id=github&no=14646 -}
{-# LANGUAGE GeneralizedNewtypeDeriving #-}
module Main where

import Data.Char
import System.Random
import Test.QuickCheck hiding ((.&.))

newtype BigChar
    = Big Char
    deriving (Eq, Show, Random)

instance Arbitrary BigChar where
    arbitrary = choose (Big '0', Big '\x10FFFF')
    shrink (Big c) = map Big (shrinkChar c)

shrinkChar :: Char -> [Char]
shrinkChar = map (toEnum . fromEnum) . flip map [0, 1 .. ] . go . toEnum . fromEnum where
    pow :: Double -> Int -> Double
    pow x n
        | n == 0 = 1
        | n `rem` 2 == 0 = y * y
        | n > 0 = y * y * x
        | n < 0 = y * y / x
        where
            y :: Double
            y = pow x (n `quot` 2)
    go :: Double -> Int -> Double
    go c n = c - c * 0.5 `pow` n

main :: IO ()
main = print $ map fromEnum $ take 10 $ shrinkChar 'a'

py01.py

# https://gall.dcinside.com/mgallery/board/view/?id=github&no=13601

def fast(n, s, sz):
    # 1st case: n = 6, s = "(()())", sz = 3.
    # 2nd case: n = 6, s = "(())()", sz = 1.
    # 3rd case: n = 6, s = "((()))", sz = 2.
    def v(i):
        nonlocal s
        if s[i] == '(':
            return 1
        else:
            return -1
    def bad(val):
        nonlocal sz
        return val < 0 or val > sz
    def get_solution():
        nonlocal n, s, sz
        # ==============================================
        # | cases                 | sequences          |
        # ==============================================
        # | 1st case              |  1  2  3  4  5  6  |
        # |-----------------------|--------------------|
        # | 1st string = ")(()()" | -1  0  1  0  1  0  |
        # | 2nd string = "()()()" |  1  0  1  0  1  0  |
        # | 3rd string = "(())()" |  1  2  1  0  1  0  |
        # | 4th string = "(())()" |  1  2  1  0  1  0  |
        # | 5th string = "(()())" |  1  2  1  2  1  0  |
        # | 6th string = "(()())" |  1  2  1  2  1  0  |
        # ==============================================
        # | 2nd case              |  1  2  3  4  5  6  |
        # |-----------------------|--------------------|
        # | 1st string = ")(())(" | -1  0  1  0 -1  0  |
        # | 2nd string = "()())(" |  1  0  1  0 -1  0  |
        # | 3rd string = "(()))(" |  1  2  1  0 -1  0  |
        # | 4th string = "(()))(" |  1  2  1  0 -1  0  |
        # | 5th string = "(()))(" |  1  2  1  0 -1  0  |
        # | 6th string = "(())()" |  1  2  1  0  1  0  |
        # ==============================================
        # | 3rd case              |  1  2  3  4  5  6  |
        # |-----------------------|--------------------|
        # | 1st string = ")((())" | -1  0  1  2  1  0  |
        # | 2nd string = "()(())" |  1  0  1  2  1  0  |
        # | 3rd string = "(()())" |  1  2  1  2  1  0  |
        # | 4th string = "((()))" |  1  2  3  2  1  0  |
        # | 5th string = "((()))" |  1  2  3  2  1  0  |
        # | 6th string = "((()))" |  1  2  3  2  1  0  |
        # ==============================================
        # Observing the above table, we can infer that:
        # (1) the i-th values of (1 ~ i)-th strings are same; and
        # (2) the i-th values of (i + 1 ~ n)-th strings are same;
        # where i is an arbitrary integer such that 1 =< i =< n.
        before = v(n - 1)
        after = v(0)
        left_idx = 1 # i >= left_idx if i-th string is valid
        right_idx = n # i <= right_idx if i-th string is valid
        for i in range(1, n + 1):
            # before = i-th value of (i - 1)-th string
            # after = i-th value of i-th string
            if bad(before): # bad(before) is true if and only if (1 ~ i)-th strings are invalid
                left_idx = max(i + 1, left_idx)
            if bad(after): # bad(after) is true if and only if (i + 1 ~ n)-th strings are invalid
                right_idx = min(i, right_idx)
            if i >= n:
                break
            else:
                before += v(i - 1)
                after += v(i)
        return max(right_idx - left_idx + 1, 0)
    return get_solution()

def slow(n, s, sz):
    def v(i):
        nonlocal s
        if s[i] == '(':
            return 1
        else:
            return -1
    def bad(x):
        nonlocal sz
        return x < 0 or x > sz    
    def valid():
        nonlocal n, s, sz
        cnt = 0
        for j in range(0, i):
            if bad(cnt):
                return False
            cnt += v(j)
        if bad(cnt):
            return False
        cnt += v(n - 1)
        for j in range(i, n - 1):
            if bad(cnt):
                return False
            cnt += v(j)
        return True
    res = 0
    for i in range(0, n):
        if valid():
            res += 1
    return res

if __name__ == '__main__':
    test_cases = [(6, "(()())", 3), (6, "(())()", 1), (6, "((()))", 2), (6, "()()()", 2), (8, "((())))(", 3)]
    for i in range(0, len(test_cases)):
        print("#", i + 1)
        n, s, sz = test_cases[i]
        fast_res = fast(n, s, sz)
        slow_res = slow(n, s, sz)
        if fast_res == slow_res:
            print(">>> Passed")
        else:
            print("--> fast_res =", fast_res)
            print("--> slow_res =", slow_res)
            print(">>> Failed")