Problem:


パズル

1 〜 9 の数字を 14 個組み合わせて完成させるパズルがあります。与えられた 13 個の数字にもうひとつ数字を付け加えて完成させます。

パズルの完成条件は

同じ数字を２つ組み合わせたものが必ずひとつ必要です。

残りの12 個の数字は、３個の数字の組み合わせ４つです。

３個の数字の組み合わせ方は、同じ数字を３つ組み合わせたものか、または３つの連続する数字を組み合わせたものです。ただし、9 1 2 のような並びは連続する数字とは認められません。

同じ数字は4 回まで使えます。

13 個の数字からなる文字列を読み込んで、パズルを完成することができる数字を昇順に全て出力するプログラムを作成してください。なお、1〜9 のどの数字を付け加えてもパズルを完成させることができないときは 0 を出力してください。

例えば与えられた文字列が 3456666777999 の場合

「2」があれば、　234 567 666 77 999

「3」があれば、　33 456 666 777 999

「5」があれば、　345 567 666 77 999

「8」があれば、　345 666 678 77 999

というふうに、2 3 5 8 のいずれかの数字が付け加えられるとパズルは完成します。「6」でも整いますが、5 回目の使用になるので、この例では使えないことに注意してください。

Input

入力は複数のデータセットからなります。各データセットとして、13 個の数字が１行に与えられます。データセットの数は 50 を超えません。

Output

データセットごとに、パズルを完成させることができる数字を昇順に空白区切りで１行に出力します。

Sample Input

3649596966777
6358665788577
9118992346175
9643871425498
7755542764533
1133557799246

Output for the Sample Input

2 3 5 8
3 4
1 2 3 4 5 6 7 8 9
7 8 9
1 2 3 4 6 7 8
0



Sample input:
3649596966777
6358665788577
9118992346175
9643871425498
7755542764533
1133557799246


Sample output:
2 3 5 8
3 4
1 2 3 4 5 6 7 8 9
7 8 9
1 2 3 4 6 7 8
0

Submission status: Runtime Error

Solution code:

def dfs(hands, pair):
    hands.sort()

    if not hands:
        return True
    target = hands[0]
    # sequence
    if all(map(lambda x: x in hands, range(target, target + 3))):
        for i in range(target, target + 3):
            hands.remove(i)
        if dfs(hands, pair):
            return True
        for i in range(target, target + 3):
            hands.append(i)
    # triple
    if hands.count(target) >= 3:
        for i in range(3):
            hands.remove(target)
        if dfs(hands, pair):
            return True
        for i in range(3):
            hands.append(target)
    # pair
    if not pair and hands.count(target) >= 2:
        for i in range(2):
            hands.remove(target)
        if dfs(hands, True):
            return True
        for i in range(2):
            hands.append(target)
    return False

for line in filter(lambda line: line.strip(), open("input.txt").readlines()):
    result = []
    data = [int(ch) for ch in line.strip()]
    for num in filter(lambda x: data.count(x) < 4, range(1, 10)):
        data_cp = list(data)
        data_cp.append(num)
        data_cp.sort()
        if dfs(data_cp, False):
            result.append(num)
    print result

Submission status: Runtime Error

Solution code:

def dfs(hands, pair):
    hands.sort()

    if not hands:
        return True
    target = hands[0]
    # sequence
    if all(map(lambda x: x in hands, range(target, target + 3))):
        for i in range(target, target + 3):
            hands.remove(i)
        if dfs(hands, pair):
            return True
        for i in range(target, target + 3):
            hands.append(i)
    # triple
    if hands.count(target) >= 3:
        for i in range(3):
            hands.remove(target)
        if dfs(hands, pair):
            return True
        for i in range(3):
            hands.append(target)
    # pair
    if not pair and hands.count(target) >= 2:
        for i in range(2):
            hands.remove(target)
        if dfs(hands, True):
            return True
        for i in range(2):
            hands.append(target)
    return False

for line in filter(lambda line: line.strip(), stdin.readlines()):
    result = []
    data = [int(ch) for ch in line.strip()]
    for num in filter(lambda x: data.count(x) < 4, range(1, 10)):
        data_cp = list(data)
        data_cp.append(num)
        data_cp.sort()
        if dfs(data_cp, False):
            result.append(num)
    print " ".join(result)

Submission status: WA: Presentation Error

Solution code:
import sys
def check(x,j=1):
    if sum(x)==0: return 1
    i = j
    while x[i]==0: i+=1
    y = x[:]
    if y[i]>=3:
        y[i] -= 3
        if check(y,i): return 1
    y = x[:]
    if i<8 and y[i]>0 and y[i+1]>0 and y[i+2]>0:
        y[i] -= 1
        y[i+1] -= 1
        y[i+2] -= 1
        if check(y,i): return 1
    return 0
 
for s in sys.stdin:
    c = [0]*10
    for e in map(int,s[:-1]): c[e] += 1
 
    f = 0
    R = range(1,10)
    for i in R:
        c1=c[:]
        if c1[i]>=4:continue
        c1[i]+=1
        for j in R:
            if c1[j]<2:continue
            c1[j]-=2
            if check(c1):
                f = 1
                print i,
                break
            c1[j]+=2
    print[0,""][f]

Submission status: WA: Presentation Error

Solution code:
import sys
def check(x,j=1):
    if sum(x)==0: return 1
    i = j
    while x[i]==0: i+=1
    y = x[:]
    if y[i]>=3:
        y[i] -= 3
        if check(y,i): return 1
    y = x[:]
    if i<8 and y[i]>0 and y[i+1]>0 and y[i+2]>0:
        y[i] -= 1
        y[i+1] -= 1
        y[i+2] -= 1
        if check(y,i): return 1
    return 0
 
for s in sys.stdin:
    c = [0]*10
    for e in map(int,s[:-1]): c[e] += 1
 
    f = 0
    R = range(1,10)
    for i in R:
        c1=c[:]
        if c1[i]>=4:continue
        c1[i]+=1
        for j in R:
            if c1[j]<2:continue
            c1[j]-=2
            if check(c1):
                f = 1
                print i,
                break
            c1[j]+=2
    print[0,"\n"][f]

Submission status: WA: Presentation Error

Solution code:
import sys
def check(x,j=1):
    if sum(x)==0: return 1
    i = j
    while x[i]==0: i+=1
    y = x[:]
    if y[i]>=3:
        y[i] -= 3
        if check(y,i): return 1
    y = x[:]
    if i<8 and y[i]>0 and y[i+1]>0 and y[i+2]>0:
        y[i] -= 1
        y[i+1] -= 1
        y[i+2] -= 1
        if check(y,i): return 1
    return 0
 
for s in sys.stdin:
    c = [0]*10
    for e in map(int,s[:-1]): c[e] += 1
 
    f = 0
    R = range(1,10)
    for i in R:
        c1=c[:]
        if c1[i]>=4:continue
        c1[i]+=1
        for j in R:
            if c1[j]<2:continue
            c1[j]-=2
            if check(c1):
                f = 1
                print i,
                break
            c1[j]+=2
    print["0\n","\n"][f],