Problem:

知識の証明

あなたが住んでいる集合住宅の入口のドアには，パスワード式のロックがかけられている．このパスワードはちょうど 4 桁の 0 から 9 の範囲の数字で構成されており，あなたはいつも，集合住宅の管理人から伝えられたパスワード P を使って，このドアのロックを解除している．

ある日，あなたは集合住宅の住民全員が，自分と同じパスワード P を使っているのかどうか気になり，同じ集合住宅に住む友人に尋ねることにした．あなたとあなたの友人は，自分のパスワードを互いに伝えあうことで，同じパスワードを使っているのかどうか確かめ合うことができる．しかしながら，パスワードがそれぞれの住民に個別に割り当てられている可能性を考えると，この方法は好ましくない．自分のパスワードを知っているのは自分だけであるべきで，他人に伝えるべきではないからである．

この事態を防ぐために，あなたとあなたの友人は，自分のパスワードをハッシュ関数に入力し，得られたハッシュ値を互いに伝えあうことにした．ここで使用するハッシュ関数の計算式 S は小文字のアルファベット 'a', 'b', 'c', 'd' と記号 '[', ']', '+', '*', '^' からなり，以下のBNFで定義される <Hash> によって表される．

<Hash> ::= <Letter> | '['<Op><Hash><Hash>']'
<Op> ::= '+' | '*' | '^'
<Letter> ::= 'a' | 'b' | 'c' | 'd'

ここで 'a', 'b', 'c', 'd' はそれぞれ 4 桁のパスワードの先頭から 1 桁目，2 桁目，3 桁目，4 桁目の数字を表す．'+', '*', '^' は演算子であり，以下のような意味を表す．

'+' : 続く 2 つの <Hash> を二進数で表したときの論理和を取る

'*' : 続く 2 つの <Hash> を二進数で表したときの論理積を取る

'^' : 続く 2 つの <Hash> を二進数で表したときの排他的論理和を取る

ここで，論理和，論理積，排他的論理和の真理値表はそれぞれ以下のようになる．

A
B
[+AB]

0
0
0

1
0
1

0
1
1

1
1
1

A
B
[*AB]

0
0
0

1
0
0

0
1
0

1
1
1

A
B
[^AB]

0
0
0

1
0
1

0
1
1

1
1
0

例として，ハッシュ関数 [+c[+a[^bd]]] にパスワード 0404 を入力すると，ハッシュ値として 0 が得られる．同じハッシュ値が得られるパスワードとして 0000, 0101, 0202, 0303, 0505, 0606, 0707, 0808, 0909 がある．

あなたのパスワード P をハッシュ関数 S に入力した結果を出力せよ．また，ハッシュ値からパスワードを一意に特定可能なハッシュ関数の使用を防ぐため，あなたのパスワードと同じハッシュ値になるパスワードの数も出力せよ．

Input

入力は最大で 50 個のデータセットから構成される．各データセットは次の形式で表される．

S
P

各データセットの1行目は，ハッシュ関数の計算式 S である．各データセットの2行目は，4 桁の 0 から 9 の範囲の数字で構成されるパスワード P である．ハッシュ関数 S の長さは 80 以下であると仮定してよい．

入力の終了は '.' の1文字だけを含む行で表される．

Output

各データセットについて，P を S に入力して得られるハッシュ値と，P と同じハッシュ値が得られるパスワードの数を空白区切りで出力せよ．

Sample Input

[+c[+a[^bd]]]
0404
[*b[*[*cd]a]]
7777
[^[^ab][^cd]]
1295
a
9876
[^dd]
9090
.

Output for the Sample Input

0 10
7 1
15 544
9 1000
0 10000



Sample input:
[+c[+a[^bd]]]
0404
[*b[*[*cd]a]]
7777
[^[^ab][^cd]]
1295
a
9876
[^dd]
9090
.


Sample output:
0 10
7 1
15 544
9 1000
0 10000

Submission status: Wrong Answer

Solution code:
# AOJ 2883: Proof of Knowledge
# Python3 2018.7.11 bal4u

def calc(a, b, c, d, i):
    global S
    if S[i] == '[':
        op = S[i+1]
        if S[i+2] == '[': v1, i = calc(a, b, c, d, i+2)
        else:
            if S[i+2] == 'a': v1 = a
            elif S[i+2] == 'b': v1 = b
            elif S[i+2] == 'c': v1 = c
            else: v1 = d
            i += 3

        if S[i] == '[': v2, i = calc(a, b, c, d, i)
        else:
            if S[i] == 'a': v2 = a
            elif S[i] == 'b': v2 = b
            elif S[i] == 'c': v2 = c
            else: v2 = d
            i += 2
        if op == '+': ans = v1 | v2
        elif op == '*': ans = v1 & v2
        else: ans = v1 ^ v2
    else:
        if S[i] == 'a': ans = a
        elif S[i] == 'b': ans = b
        elif S[i] == 'c': ans = c
        else: ans = d
        i += 1
    return [ans, i]

while True:
    S = input()
    if S == '.': break
    P = input()
    a, b, c, d = map(int, list(P))
    val, cnt = calc(a, b, c, d, 0)[0], 0
    for a in range(0, 10):
        for b in range(0, 10):
            for c in range(0, 10):
                for d in range(0, 10):
                    if calc(a, b, c, d, 0)[0] == val: cnt += 1
    print(val, cnt)

Submission status: Accepted

Solution code:
# AOJ 2883: Proof of Knowledge
# Python3 2018.7.11 bal4u

def calc(a, b, c, d, i):
    global S
    if S[i] == '[':
        op = S[i+1]
        if S[i+2] == '[': v1, i = calc(a, b, c, d, i+2)
        else:
            if S[i+2] == 'a': v1 = a
            elif S[i+2] == 'b': v1 = b
            elif S[i+2] == 'c': v1 = c
            else: v1 = d
            i += 3

        if S[i] == '[': v2, i = calc(a, b, c, d, i)
        else:
            if S[i] == 'a': v2 = a
            elif S[i] == 'b': v2 = b
            elif S[i] == 'c': v2 = c
            else: v2 = d
            i += 2
        if op == '+': ans = v1 | v2
        elif op == '*': ans = v1 & v2
        else: ans = v1 ^ v2
    else:
        if S[i] == 'a': ans = a
        elif S[i] == 'b': ans = b
        elif S[i] == 'c': ans = c
        else: ans = d
        i += 1
    while i < len(S) and S[i] == ']': i += 1
    return [ans, i]

while True:
    S = input()
    if S == '.': break
    P = input()
    a, b, c, d = map(int, list(P))
    val, cnt = calc(a, b, c, d, 0)[0], 0
    for a in range(0, 10):
        for b in range(0, 10):
            for c in range(0, 10):
                for d in range(0, 10):
                    if calc(a, b, c, d, 0)[0] == val: cnt += 1
    print(val, cnt)

Submission status: Accepted

Solution code:
def solve(s,p):
    if s[0]!='[':
        return[p//1000,p//100%10,p//10%10,p%10][ord(s[0])-ord('a')]
    i=3
    cs=[0,1][s[2]=='[']
    ce=0
    while cs!=ce:
        if s[i]=='[':
            cs+=1
        elif s[i]==']':
            ce+=1
        i+=1
    j=i+1
    cs=[0,1][s[i]=='[']
    ce=0
    while cs!=ce:
        if s[j]=='[':
            cs+=1
        elif s[j]==']':
            ce+=1
        j+=1
    l=solve(s[2:i],p)
    r=solve(s[i:j],p)
    if s[1]=='+':
        return l|r
    elif s[1]=='*':
        return l&r
    else:
        return l^r
while True:
    s=input()
    if s=='.':break
    p=int(input())
    a=solve(s,p)
    c=0
    for i in range(10000):
        if solve(s,i)==a:
            c+=1
    print(a,c)

Submission status: Accepted

Solution code:
def solve(s,p):
    if s[0]!='[':
        return[p//1000,p//100%10,p//10%10,p%10][ord(s[0])-ord('a')]
    i=3
    cs=s[2]=='['
    ce=0
    while cs!=ce:
        if s[i]=='[':
            cs+=1
        elif s[i]==']':
            ce+=1
        i+=1
    j=i+1
    cs=s[i]=='['
    ce=0
    while cs!=ce:
        if s[j]=='[':
            cs+=1
        elif s[j]==']':
            ce+=1
        j+=1
    l=solve(s[2:i],p)
    r=solve(s[i:j],p)
    if s[1]=='+':
        return l|r
    elif s[1]=='*':
        return l&r
    else:
        return l^r
while True:
    s=input()
    if s=='.':break
    p=int(input())
    a=solve(s,p)
    c=0
    for i in range(10000):
        if solve(s,i)==a:
            c+=1
    print(a,c)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

def hash(a, b, c, d, f, start, end):
    i = start + 1
    while i < end:
        if f[i] in "+^*":
            i += 1
            if f[i] == "a":
                tmp1 = a
            elif f[i] == "b":
                tmp1 = b
            elif f[i] == "c":
                tmp1 = c
            elif f[i] == "d":
                tmp1 = d
            elif f[i] == "[":
                i, tmp1 = hash(a,b,c,d,f,i,end)
            i += 1
            if f[i] == "a":
                tmp2 = a
            elif f[i] == "b":
                tmp2 = b
            elif f[i] == "c":
                tmp2 = c
            elif f[i] == "d":
                tmp2 = d
            elif f[i] == "[":
                i, tmp2 = hash(a,b,c,d,f,i,end)
            if f[start+1] == "+":
                return i+1, tmp1 | tmp2
            elif f[start+1] == "^":
                return i+1, tmp1 ^ tmp2
            elif f[start+1] == "*":
                return i+1, tmp1 & tmp2


def main():
    while True:
        s = input().strip()
        if s[0] == ".":
            break
        p = input().strip()
        a = int(p[0])
        b = int(p[1])
        c = int(p[2])
        d = int(p[3])
        if s[0] in "abcd":
            if s[0] == 'a':
                print(a, 1000)
            elif s[0] == 'b':
                print(b, 1000)
            elif s[0] == 'c':
                print(c, 1000)
            elif s[0] == 'd':
                print(d, 1000)
            #print(int(p['s[0]' - 'a']), 1)
            continue
        _,ans1 = hash(a,b,c,d,s,0,len(s))
        count = 0
        for a in range(10):
            for b in range(10):
                for c in range(10):
                    for d in range(10):
                        _, x = hash(a,b,c,d,s,0,len(s))
                        if x == ans1:
                            count += 1
        print(ans1, count)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)
from operator import *

ops = {'+':lambda x1, x2: x1 | x2, '*': lambda x1, x2: x1 & x2, '^': lambda x1, x2: x1 ^ x2}

def f(op, s1, s2):
    return ops[op](s1, s2)

def toN(s, numbers):
    for abc, number in zip(letters, list(numbers)):
        s = s.replace(abc, number)
    return s

letters = list("abcd")
def solve(S, P):
    origin = S
    S = S.replace('[', 'f(')
    S = S.replace(']', '),')
    for k in ops.keys():
        S = S.replace(k, "'" + k + "',")
    for l in letters:
        S = S.replace(l, l + ",")
    transed = S

    # print(S)
    res = eval(toN(S, P))[0]
    print(res, end=' ')
    count = 0
    for i in range(10000):
        if res == eval(toN(S, "{:04d}".format(i)))[0]:
            count += 1
    
    print(count)

while True:
    S = input()
    if S == '.':
        break
    P = input()
    solve(S, P)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    def parse_hash(s,i):
        if s[i] == "[":
            i += 1
            op,i = parse_op(s,i)
            h1,i = parse_hash(s,i)
            h2,i = parse_hash(s,i)
            i += 1
            return calc(op,h1,h2),i
        else:
            return parse_letter(s,i)

    def parse_op(s,i):
        return s[i],i+1

    def parse_letter(s,i):
        return s[i],i+1

    def calc(op,h1,h2):
        if op == "+":
            return h1|h2
        elif op == "*":
            return h1&h2
        else:
            return h1^h2

    while 1:
        s = S()
        if s[0] == ".":
            break
        t = S()
        n = len(s)
        s0 = [s[i] for i in range(n)]
        for i in range(n):
            if s0[i] == "a":
                s0[i] = int(t[0])
            elif s0[i] == "b":
                s0[i] = int(t[1])
            elif s0[i] == "c":
                s0[i] = int(t[2])
            elif s0[i] == "d":
                s0[i] = int(t[3])
        p = parse_hash(s0,0)[0]
        ans = 0
        for a in range(10):
            for b in range(10):
                for c in range(10):
                    for d in range(10):
                        s0 = [s[i] for i in range(n)]
                        for i in range(n):
                            if s0[i] == "a":
                                s0[i] = a
                            elif s0[i] == "b":
                                s0[i] = b
                            elif s0[i] == "c":
                                s0[i] = c
                            elif s0[i] == "d":
                                s0[i] = d
                        p0 = parse_hash(s0,0)[0]
                        if p == p0:
                            ans += 1
        print(p,ans)

    return

#B
def B():
    return

#C
def C():
    return

#D
def D():
    return

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#I
def I_():
    return

#J
def J():
    return

#Solve
if __name__ == "__main__":
    A()

Submission status: Accepted

Solution code:
def parse_hash(s, pointer):
  head = s[pointer]
  if head == "[":
    pointer += 1
    op, pointer = parse_op(s, pointer)
    h1, pointer = parse_hash(s, pointer)
    h2, pointer = parse_hash(s, pointer)
    return calc(op, h1, h2), pointer + 1
  else:
    l, pointer = parse_letter(s, pointer)
    return l, pointer
 
def parse_op(s, pointer):
  return s[pointer], pointer + 1

def parse_letter(s, pointer):
  return int(s[pointer]), pointer + 1

def calc(op, h1, h2):
  if op == "+":
    return h1 | h2
  if op == "*":
    return h1 & h2
  if op == "^":
    return h1 ^ h2

from collections import defaultdict
from itertools import product
while True:
  s = input()
  if s == ".":break
  p = input()
  score = defaultdict(int)
  nums = [chr(i) for i in range(ord("0"), ord("9") + 1)]
  for a, b, c, d in product(nums, repeat=4):
    temp = s.replace("a", a)
    temp = temp.replace("b", b)
    temp = temp.replace("c", c)
    temp = temp.replace("d", d)
    score[parse_hash(temp, 0)[0]] += 1
  
  for i in range(4):
    s = s.replace(chr(ord("a") + i), p[i])
  hs = parse_hash(s, 0)
  print(hs[0], score[hs[0]])

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    rr = []

    def f(s):
        t = [int(c) for c in S()]
        a = [t[ord(c) - ord('a')] if c in 'abcd' else c for c in s]

        def ff(a):
            if len(a) == 1:
                return a[0]
            l = len(a)
            for i in range(l-4):
                if a[i] == '[' and a[i+4] == ']':
                    op = a[i+1]
                    b = a[i+2]
                    c = a[i+3]
                    t = -1
                    if op == '+':
                        t = b | c
                    elif op == '*':
                        t = b & c
                    elif op == '^':
                        t = b ^ c
                    return ff(a[:i] + [t] + a[i+5:])
            return -1

        r = ff(a)
        c = 0
        for k in range(10000):
            tt = [k//(10**i)%10 for i in range(4)]
            aa = [tt[ord(c) - ord('a')] if c in 'abcd' else c for c in s]
            kk = ff(aa)
            if kk == r:
                c += 1
        return '{} {}'.format(r,c)

    while 1:
        n = S()
        if n == '.':
            break
        rr.append(f(n))

    return '\n'.join(map(str, rr))


print(main())

Submission status: Accepted

Solution code:
import sys,functools
if sys.version_info[0]>=3:
	maketrans=str.maketrans
else:
	from string import maketrans

O=lambda a:lambda b:a|b
A=lambda a:lambda b:a&b
X=lambda a:lambda b:a^b
while True:
	s=sys.stdin.readline().rstrip().translate(maketrans('+*^[]','OAX()'))
	if s=='.': break
	for c in 'abcd': s=s.replace(c,'(%s)'%c)
	s=s[1:-1]
	n=int(sys.stdin.readline())
	r=eval(s.translate(maketrans('abcd','%04d'%n)))
	print('%d %d'%(r,sum(r==eval(s.translate(maketrans('abcd','%04d'%i))) for i in range(10000))))

Submission status: Runtime Error

Solution code:
def solve(s,p):
    if s[0]!='[':
        return[p//1000,p//100%10,p//10%10,p%10][ord(s[0])-ord('a')]
    i=3
    while s.count('[',2,i)!=s.count(']',2,i):
        i+=1
    j=i+1
    while s.count('[',i,j)!=s.count(']',i,j):
        j+=1
    l=solve(s[2:i])
    r=solve(s[i:j])
    if s[1]=='+':
        return l|r
    elif s[1]=='*':
        return l&r
    else:
        return l^r
while True:
    s=input()
    if s=='.':break
    p=int(input())
    a=solve(s,p)
    c=0
    for i in range(10000):
        if solve(s,i)==a:
            c+=1
    print(a,c)

Submission status: Runtime Error

Solution code:
def solve(s,p):
    if s[0]!='[':
        return[p//1000,p//100%10,p//10%10,p%10][ord(s[0])-ord('a')]
    i=3
    while s.count('[',2,i)!=s.count(']',2,i):
        i+=1
    j=i+1
    while s.count('[',i,j)!=s.count(']',i,j):
        j+=1
    l=solve(s[2:i],p)
    r=solve(s[i:j],p)
    if s[1]=='+':
        return l|r
    elif s[1]=='*':
        return l&r
    else:
        return l^r
while True:
    s=input()
    if s=='.':break
    p=int(input())
    a=solve(s,p)
    c=0
    for i in range(10000):
        if solve(s,i)==a:
            c+=1
    print(a,c)