Problem:


Problem H: Bug Hunt

In this problem, we consider a simple programming language that has only declarations of one-
dimensional integer arrays and assignment statements. The problem is to find a bug in the given
program.

The syntax of this language is given in BNF as follows:

where <new line> denotes a new line character (LF).

Characters used in a program are alphabetical letters, decimal digits, =, [, ] and new line characters. No other characters appear in a program.

A declaration declares an array and specifies its length. Valid indices of an array of length n are integers between 0 and n - 1, inclusive. Note that the array names are case sensitive, i.e.
array a and array A are different arrays. The initial value of each element in the declared array is undefined.

For example, array a of length 10 and array b of length 5 are declared respectively as follows.

a[10]
b[5]

An expression evaluates to a non-negative integer. A <number> is interpreted as a decimal
integer. An <array_name> [<expression>] evaluates to the value of the <expression> -th element of
the array. An assignment assigns the value denoted by the right hand side to the array element
specified by the left hand side.

Examples of assignments are as follows.

a[0]=3
a[1]=0
a[2]=a[a[1]]
a[a[0]]=a[1]

A program is executed from the first line, line by line. You can assume that an array is declared once and only once before any of its element is assigned or referred to.

Given a program, you are requested to find the following bugs.

   
 An index of an array is invalid.

   
 An array element that has not been assigned before is referred to in an assignment as an index of array or as the value to be assigned.

You can assume that other bugs, such as syntax errors, do not appear. You can also assume
that integers represented by <number>s are between 0 and 231 - 1 (= 2147483647), inclusive.

Input

The input consists of multiple datasets followed by a line which contains only a single '.' (period).
Each dataset consists of a program also followed by a line which contains only a single '.' (period).
A program does not exceed 1000 lines. Any line does not exceed 80 characters excluding a new
line character.

Output

For each program in the input, you should answer the line number of the assignment in which
the first bug appears. The line numbers start with 1 for each program. If the program does not
have a bug, you should answer zero. The output should not contain extra characters such as
spaces.

Sample Input

a[3]
a[0]=a[1]
.
x[1]
x[0]=x[0]
.
a[0]
a[0]=1
.
b[2]
b[0]=2
b[1]=b[b[0]]
b[0]=b[1]
.
g[2]
G[10]
g[0]=0
g[1]=G[0]
.
a[2147483647]
a[0]=1
B[2]
B[a[0]]=2
a[B[a[0]]]=3
a[2147483646]=a[2]
.
.

Output for the Sample Input

2
2
2
3
4
0



Sample input:
a[3]
a[0]=a[1]
.
x[1]
x[0]=x[0]
.
a[0]
a[0]=1
.
b[2]
b[0]=2
b[1]=b[b[0]]
b[0]=b[1]
.
g[2]
G[10]
g[0]=0
g[1]=G[0]
.
a[2147483647]
a[0]=1
B[2]
B[a[0]]=2
a[B[a[0]]]=3
a[2147483646]=a[2]
.
.


Sample output:
2
2
2
3
4
0

Submission status: Accepted

Solution code:
import re

def get_value(expr, array_size, array):
    seq = expr.replace(']', '').split('[')
    seq[-1] = int(seq[-1])
    while len(seq) > 1:
        ind = seq.pop()
        arr = seq.pop()
        if arr not in array or ind not in array[arr]:
            raise KeyError

        seq.append(array[arr][ind])

    return seq[0]

def testcase_ends():
    array_size = {}
    array = {}

    decl_prog = re.compile(r'(\w)\[(\d+)\]')

    line = input().strip()
    if line == '.':
        return True

    i = 1
    while True:
        if line == '.':
            print(0)
            return False

        if '=' in line:
            # assignment
            lhs, rhs = line.split('=')

            name = lhs[0]
            try:
                ind = get_value(lhs[2:-1], array_size, array)
                value = get_value(rhs, array_size, array)
                if name not in array or ind >= array_size[name]:
                    raise KeyError

                array[name][ind] = value
            except KeyError:
                print(i)
                break
        else:
            # declaration
            m = decl_prog.fullmatch(line)
            assert m is not None

            name = m.group(1)
            size = int(m.group(2))
            array_size[name] = size
            array[name] = {}

        line = input().strip()
        i += 1

    line = input().strip()
    while line != '.':
        line = input().strip()

    return False

while not testcase_ends():
    pass

Submission status: Accepted

Solution code:
import re
init = re.compile("([^[]+)\[([^=]+)\]$")
assign = re.compile("([^[]+)\[([^=]+)\]=(.+)$")
def evaluate(s):
    try:
        m = init.match(s)
        if m:
            name, expr = m.groups()
            return dic[name][evaluate(expr)]
        return eval(s)
    except:pass
    return -1
while 1:
    dic = {}
    sz = {}
    ans = 0
    idx = 0
    while 1:
        s = raw_input()
        if s == '.':
            break
        idx += 1
        m = init.match(s)
        if m:
            name, expr = m.groups()
            val = evaluate(expr)
            if val == -1:
                if ans == 0:
                    ans = idx
            else:
                dic[name] = {}
                sz[name] = val
        else:
            m = assign.match(s)
            name, expr, right = m.groups()
            i = evaluate(expr)
            val = evaluate(right)
            if i == -1 or val == -1 or name not in dic or sz[name]-1 < i:
                if ans == 0:
                    ans = idx
            else:
                dic[name][i] = val
    if not dic:
        break
    print ans

Submission status: Accepted

Solution code:
import re

def deref(d, expr):
  expr = expr.replace(']', '')
  symb = expr.split('[')
  symb[-1] = symb[-1]
  while len(symb) > 1:
    name, index = symb[-2:]
    if index not in d[name]:
      return None

    symb.pop()
    symb.pop()
    symb.append(d[name][index])

  return symb[0]


def check(s):
  d = {}
  dd = {}
  for i, stmt in enumerate(s, 1):
    if '=' not in stmt:
      name = stmt[0]
      index = stmt[2:-1]
      d[name] = {}
      dd[name] = int(index)
      continue

    lhs, rhs = stmt.split('=')
    
    name = lhs[0]
    index = lhs[2:-1]
    index = deref(d, index)
    value = deref(d, rhs)
    if index is None or value is None or int(index) >= dd[name]:
      print(i)
      return

    d[name][index] = value

  print(0)


def main():
  list_ = []
  with open(0) as fin:
    for line in fin:
      line = line.strip()
      if line == '.':
        if not list_: 
          return 0

        check(list_)
        list_ = []
        continue

      list_.append(line)

if __name__ == '__main__':
  main()

Submission status: Accepted

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

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

while True:
    lst = []
    S = raw_input()
    if S == '.':
        break
    lst.append(S)
    while True:
        S = raw_input()
        if S == '.':
            break
        lst.append(S)
    
    upper = []
    flag = False

    for i in range(len(lst)):
        S = lst[i]
        if '=' in S:
            try:
                exec(S)
            except:
                flag = True
            for elem in upper:
                for key in elem[0]:
                    if key >= elem[1]:
                        flag = True
                        break
            if flag:
                print i + 1
                break
        else:
            P = S.split('[')
            name = P[0]
            num = int(P[1][:-1])
            exec(name + ' = {}')
            upper.append((globals()[name], num))
    
    if not flag:
        print 0

Submission status: Accepted

Solution code:
while True:
    lst = []
    S = raw_input()
    if S == '.':
        break
    lst.append(S)
    while True:
        S = raw_input()
        if S == '.':
            break
        lst.append(S)
    
    upper = []
    flag = False

    for i in range(len(lst)):
        S = lst[i]
        if '=' in S:
            try:
                exec(S)
            except:
                flag = True
            for elem in upper:
                for key in elem[0]:
                    if key >= elem[1]:
                        flag = True
                        break
            if flag:
                print i + 1
                break
        else:
            P = S.split('[')
            name = P[0]
            num = int(P[1][:-1])
            exec(name + ' = {}')
            upper.append((globals()[name], num))
    
    if not flag:
        print 0

Submission status: Accepted

Solution code:
class CustomArray:
    def __init__(self, sz):
        self.sz = sz
        self.vals = {}

    def size(self):
        return self.sz

    def assign(self, idx, val):
        if idx == None or val == None:
            return False
        if idx >= self.sz:
            return False
        self.vals[idx] = val
        return True
    
    def get(self, idx):
        if idx == None:
            return None
        if idx >= self.sz:
            return None
        if idx not in self.vals:
            return None
        return self.vals[idx]

class Arrays:
    def __init__(self):
        self.arrays = {}

    def declare(self, arrName, sz):
        if sz == None:
            return False
        if arrName in self.arrays:
            return False
        self.arrays[arrName] = CustomArray(sz)
        return True

    def assign(self, arrName, idx, val):
        if arrName not in self.arrays:
            return False
        return self.arrays[arrName].assign(idx, val)

    def get(self, arrName, idx):
        if arrName not in self.arrays:
            return None
        return self.arrays[arrName].get(idx)
        
def resolve(expression):
    global arrays

    if "[" not in expression:
        return int(expression)

    arrName = expression[0]
    idx = resolve(expression[2:-1])

    return arrays.get(arrName, idx)

def processAssignment(command):
    global arrays

    equalIdx = command.find("=")
    leftStr = command[:equalIdx]
    rightStr = command[equalIdx + 1:]

    leftArrName = leftStr[0]
    leftIdx = resolve(leftStr[2:-1])
    rhs = resolve(rightStr)
    
    return arrays.assign(leftArrName, leftIdx, rhs)

def processDeclaration(arrStr):
    global arrays
    arrName = arrStr[0]
    sz = int(arrStr[2:-1])
    return arrays.declare(arrName, sz)

if __name__ == '__main__':
    while True:
        commands = []
        while True:
            line = input().strip()
            if line == '.':
                break
            commands.append(line)

        if len(commands) == 0:
            break

        errLine = 0
        arrays = Arrays()

        for i in range(len(commands)):
            command = commands[i]
            
            if "=" in command:
                result = processAssignment(command)
            else:
                result = processDeclaration(command)

            if not result:
                errLine = i + 1
                break

        print(errLine)

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+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(n):
        _a = [n]
        while 1:
            s = S()
            if s == '.':
                break
            _a.append(s)
        _ks = {}
        _d = {}
        for _i in range(len(_a)):
            _s = _a[_i]
            if '=' in _s:
                try:
                    exec(_s,_d)
                    for _k in _ks.keys():
                        # print('_k',_k)
                        _kl = _d[_k].keys()
                        # print('_kl',_kl)
                        if _kl and max(_kl) >= _ks[_k]:
                            # print('mk', _s, _k,_kl)
                            return _i + 1
                except:
                    # print('except', _s)
                    # print('_d',_d.keys(),_d['z'])
                    return _i + 1
            else:
                _k = _s.split('[')[0]
                _n = int(_s.split('[')[1].split(']')[0])
                _ks[_k] = _n
                # print('tg', _k + ' = {}', _n)
                if _n < 1:
                    continue
                exec(_k+"={}",_d)
        return 0

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

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


print(main())