Problem:


問題名 YAML

YAML (YAML Ain't Markup Language)とは、オブジェクトを文字列で表現する形式の一つです。

YAMLのサブセットで表されたオブジェクトと、プロパティを指定するクエリが与えられるので、指定されたプロパティの値を答えてください。

YAMLのサブセット

YAML のサブセットは、次のような拡張 BNF 記法で表される構文規則に従います。

yaml: mapping(0)
mapping(n): mapping-item(n) | mapping-item(n) mapping(n)
mapping-item(n): indent(n) key ':' ' ' string '\n'
                 | indent(n) key ':' '\n' mapping(m) (ただしm>n)
key: [a-z0-9]+ (※英字小文字または数字からなる1文字以上の文字列)
string: [a-z0-9 ]+ (※英字小文字または数字またはスペースからなる1文字以上の文字列)
indent(0): "" (※空文字列)
indent(n+1): ' ' indent(n) (※スペースをn+1個並べた文字列)

'\n'は改行文字を表します。

mapping(n) はオブジェクトを表し、mapping(n) に含まれる mapping-item(n) は、オブジェクトに含まれるプロパティを表します。

mapping-item(n): indent(n) key ':' ' ' string '\n' は、 key で表されるプロパティの値がstringで表される文字列であることを示します。

mapping-item(n): indent(n) key ':' '\n' mapping(m) は、key で表されるプロパティの値がmapping(m)で表されるオブジェクトであることを示します。

1つのオブジェクトに、2つ以上、同じ key を持つプロパティが含まれることはありません。

プロパティを指定するクエリの形式

プロパティを指定するクエリは、

.key_1.key_2(..省略..).key_n

のように、'.'と key が交互に現れる形で与えられ、これは「 yaml で与えられたオブジェクトの、key1 という key を持つプロパティの値であるオブジェクトの、 key2 という key を持つプロパティの値であるオブジェクトの、(..省略..) keyn という key を持つプロパティ」を表します。

なお、あるi(1 ≤ i ≤ n - 1)について、.key_1.key_2.(..省略..).key_iまでで表されるプロパティの値がオブジェクトでない、またはオブジェクトであるがkey_i+1というプロパティを含んでいない場合、.key_1.key_2(..省略..).key_n で表されるようなプロパティは存在しないとみなします。

Input

.key_1.key_2(...).key_n
yaml

1 ≤ n ≤ 20

入力全体に含まれる文字数 ≤ 50,000

Output

プロパティの値を 1 行で出力してください。

指定されたプロパティが存在しない場合は no such property, プロパティの値がオブジェクトの場合は object, プロパティの値が文字列の場合は string "<文字列の内容>" と出力してください。

Sample Input 1

.tweets.1
name: shimeji
id: shimejitan
tweets:
  1: shimejilove
  2: azupero

Output for the Sample Input 1

string "shimejilove"

Sample Input 2

.a
a: sample case

Output for the Sample Input 2

string "sample case"

Sample Input 3

.my.obj
my:
 str: string value
 obj:
    a: a
    b: b
    c: c

Output for the Sample Input 3

object

Sample Input 4

.str.inner
str: inner

Output for the Sample Input 4

no such property

Sample Input 5

.no.such.property
object:
    prop1: str
    prop2: str

Output for the Sample Input 5

no such property



Sample input:
.tweets.1
name: shimeji
id: shimejitan
tweets:
  1: shimejilove
  2: azupero


Sample output:
string "shimejilove"

Submission status: Wrong Answer

Solution code:
import sys
ipts = sys.stdin.readlines()
keys = ipts[0][1:-1].split('.')

node = root = {}
prev = 0
for cur in xrange(1, len(ipts)):
    line = ipts[cur]
    indent = 0
    while line[indent] == ' ':
        indent += 1
    m = line[indent:]
    key, value = m.split(':')
    if indent < prev:
        node = node[":"]
    if value == '\n':
        parent = node
        node[key] = node = {}
        node[":"] = parent
    else:
        node[key] = value[1:-1]
    prev = indent
node = root
for key in keys:
    if type(node) == dict and key in node:
        node = node[key]
    else:
        print "no such property"
        break
else:
    if type(node) == dict:
        print "object"
    else:
        print "string \"%s\"" % node

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python

def main():
    key = raw_input().split('.')[1:]
    indent = 0
    while True:
        try:
            s = raw_input()
        except EOFError:
            print 'EOFError'
            break

        # print '>>', '"'+' '*indent+key[indent/2]+':"'
        # print '<<', s
        if s.startswith(' '*indent+key[indent/2]+':'):
            indent += 2
            if len(key) == indent/2:
                t = s[len(key[indent/2-1])+indent:]
                if not t:
                    print 'object'
                else:
                    print 'string "'+t+'"'
                return

            t = s[len(key[indent/2-1])+indent:]
            # print t
            if t:
                break

        elif not s.startswith(' '*indent):
            break

    print 'no such property'

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python

import re

def main():
    key = raw_input().split('.')[1:]
    indent = 0
    level = 0
    while True:
        try:
            s = raw_input()
        except EOFError:
            break

        if re.match(' *'+' '*indent+key[level]+':', s):
            indent = len(re.match(' *', s).group())
            level += 1
            if len(key) == level:
                t = s[len(key[level-1])+indent+2:]
                if not t:
                    print 'object'
                else:
                    print 'string "'+t+'"'
                return

            t = s[len(key[level-1])+indent+2:]
            if t:
                break

        elif not s.startswith(' '*indent):
            break

        indent = len(re.match(' *', s).group())

    print 'no such property'

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python

import re

def main():
    key = raw_input().split('.')[1:]
    indent = 0
    level = 0
    while True:
        try:
            s = raw_input()
        except EOFError:
            break

        if re.match(' *'+' '*indent+key[level]+':', s):
            indent = len(re.match(' *', s).group())
            level += 1
            if len(key) == level:
                t = s[len(key[level-1])+indent+2:]
                if not t:
                    print 'object'
                else:
                    print 'string "'+t+'"'
                return

            t = s[len(key[level-1])+indent+2:]
            if t:
                break

        elif not s.startswith(' '*indent):
            break

        space = len(re.match(' *', s).group())
        if space < indent:
            break

    print 'no such property'

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python

import sys
import math
import itertools as it
from collections import deque

sys.setrecursionlimit(10000000)

Query = raw_input()
Query = Query.split('.')[1:]

lst = []
m = {}

for line in sys.stdin:
    key, value = line[:-1].split(":")
    rank = key.count(' ')
    key = key[rank:]
    index = len(lst)
    for i in range(len(lst)):
        if rank == lst[i][0]:
            index = i
            break
    lst = lst[:index]
    ms = m
    for p in lst:
        ms = ms[p[1]]
    if value == '':
        ms[key] = {}
    else:
        ms[key] = value
    lst.append((rank, key))

try:
    ms = m
    for key in Query:
        ms = ms[key]
    if type(ms) == type(''):
        print 'string "' + ms[1:] + '"'
    else:
        print 'object'
except:
    print 'no such property'

Submission status: Accepted

Solution code:
import sys
ipts = sys.stdin.readlines()
keys = ipts[0][1:-1].split('.')

node = root = {}
for cur in xrange(1, len(ipts)):
    line = ipts[cur]
    indent = 0
    while line[indent] == ' ':
        indent += 1
    m = line[indent:]
    key, value = m.split(':')
    if ":i" not in node:
        node[":i"] = indent
    while indent < node[":i"]:
        node = node[":p"]
    if value == '\n':
        parent = node
        node[key] = node = {}
        node[":p"] = parent
    else:
        node[key] = value[1:-1]
    prev = indent
node = root
for key in keys:
    if type(node) == dict and key in node:
        node = node[key]
    else:
        print "no such property"
        break
else:
    if type(node) == dict:
        print "object"
    else:
        print "string \"%s\"" % node

Submission status: Accepted

Solution code:
#!/usr/bin/python

import re

def main():
    key = raw_input().split('.')[1:]
    indent = 0
    level = 0
    need_update = False
    while True:
        try:
            s = raw_input()
        except EOFError:
            break

        space = len(re.match(' *', s).group())
        if need_update:
            indent = space
            need_update = False

        if re.match(' *'+' '*indent+key[level]+':', s):
            indent = len(re.match(' *', s).group())
            level += 1
            need_update = True
            if len(key) == level:
                t = s[len(key[level-1])+indent+2:]
                if not t:
                    print 'object'
                else:
                    print 'string "'+t+'"'
                return

            t = s[len(key[level-1])+indent+2:]
            if t:
                break

        elif not s.startswith(' '*indent):
            break

        if space < indent:
            break

    print 'no such property'

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict
d = defaultdict(lambda : "no such property")

check, *yaml = list(open(0))
before = []
beforei = []
ka = defaultdict(lambda :-1)
bv = -1
for y in yaml:
    y = y.split(":")
    vacant = y[0].count(" ")
    if bv >= vacant:
        for num,b in enumerate(beforei):
            if b == vacant:
                break
        before = before[:num]
        beforei = beforei[:num]
    bv = vacant
    before.append(y[0].strip(" "))
    beforei.append(bv)
    x = y[1][1:-1]
    d[tuple(before)] = "object" if x == "" else "string \""+x+"\""
ans = tuple(check.strip("\n").split(".")[1:])
print(d[ans])

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**13
mod = 10**9+9
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(ks):
        a = []
        while 1:
            try:
                s = S()
                if s == '':
                    break
                a.append(s)
            except:
                break
        y = {}
        keys = []
        for l in a:
            while 1:
                yi = y
                for k in keys:
                    yi = yi[k]
                ti = 0
                for c in l:
                    if c != ' ':
                        break
                    ti += 1
                if '_ind' not in yi:
                    yi['_ind'] = ti
                if yi['_ind'] != ti:
                    keys = keys[:-1]
                    continue
                k = l.split(':')[0].split(' ')[-1]
                if l[-1] == ':':
                    keys.append(k)
                    yi[k] = {}
                else:
                    yi[k] = l.split(':')[1][1:]
                break
        ka = ks.split('.')[1:]
        yi = y
        for k in ka:
            if isinstance(yi, str) or k not in yi:
                return 'no such property'
            yi = yi[k]
        if isinstance(yi, str):
            return 'string "{}"'.format(yi)
        return 'object'

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

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


print(main())

Submission status: Accepted

Solution code:
#! /usr/bin/env python3

import re

gkey = input()

yaml = {}
opening_key = ['']
opening_ind = [-1]
space_prog = re.compile(r' *')
key_prog = re.compile(r'[a-z\d]+')
while True:
    try:
        line = input()
    except EOFError:
        break

    indent = len(space_prog.match(line).group())
    while opening_ind[-1] >= indent:
        opening_ind.pop()
        opening_key.pop()

    key = key_prog.search(line).group()
    if not line.endswith(':'):
        yaml['.'.join(opening_key+[key])] = (
            'string "{}"'.format(line[line.index(':')+2:])
        )
        continue

    opening_key.append(key)
    opening_ind.append(indent)

    yaml['.'.join(opening_key)] = 'object'

print(yaml.get(gkey, 'no such property'))