# Bachelor AI project 2009. Andreas van Cranenburgh 0440949.
from random import choice

#edit distance of two strings
def eddist(source, target):
	def substcost():
		if a == b: return 0
		else: return 2

	#initialize distance matrix
	distance = [[(0, ' ')for a in target+' '] for b in source+' ']
	for i, row in enumerate(distance): row[0] = (i, 'I')
	for j in range(len(distance[0])): distance[0][j] = (j, 'D')
	distance[0][0] = (0, 'S')

	#populate distance matrix
	for i, a in list(enumerate('#'+source))[1:]:
		for j, b in list(enumerate('#'+target))[1:]:
				insc = (distance[i-1][j][0] + 1, 'I')
				substc = (distance[i-1][j-1][0] + substcost(), 'S')
				delc = (distance[i][j-1][0] + 1, 'D')
				distance[i][j] = min((substc, insc, delc))
	return distance[-1][-1][0]

#reverse dictionary, ie. swap values and keys. 
#since a value may be occur with multiple keys, return a list of keys for each value
def revdict(d):
	return dict([(b, [c for c, e in d.items() if e == b ]) for a, b in d.items()])

def pred(token):
	if '(' in token: return token[:token.index('(')]
	else: return token

def arg(token):
	if '(' in token: return token[token.index('('):]
	else: return ''

#test whether meaning fits into partialmeanings, if so, unify 
#eg. "question: animal(bunny) do(X)" and "assertion: point(dog) animal(dog)" 
#will succeed, substituting "bunny" with "dog" because that's the first 
#predicate which overlaps
def unifiespartially(meaning, partialmeaning):
	#pm is wrapped in a list so that it can enjoy side-effects
	pm = partialmeaning[0]
	if pm == '':
		partialmeaning[0] = meaning
		return True

	for part in meaning.split():
		if pred(part) in pm:
			if arg(part):
				pr = pred(part)
				oldarg = pm[pm.index(pr+'(') + len(pr):pm.index(')', pm.index(pr+'(')) + 1]
				print "substituted", oldarg, "with", arg(part)
				partialmeaning[0] = pm.replace(oldarg, arg(part))
				return True
			return True
	#we failed:
	return False

#succeed if everything in "partialmeaning" is compatible with "meaning",
#substituting along the way
def unifiesfully(meaning, partialmeaning):
	#pm is wrapped in a list so that it can enjoy side-effects
	pm = partialmeaning[0]
	if pm == '':
		partialmeaning[0] = meaning
		return True

	for part in pm.split():
		if pred(part) not in meaning:
			return False
		elif part not in meaning and arg(part):
			pr = pred(part)
			newarg = meaning[meaning.index(pr+'(') + len(pr):meaning.index(')', meaning.index(pr+'(')) + 1]
			print "substituted", arg(part), "with", newarg
			partialmeaning[0] = pm = pm.replace(arg(part), newarg)
			#pm = partialmeaning[0]
	return True

#return semantic representation for linguistic utterance
def interpret(utterance, examplars):
	#exact match:
	if utterance in examplars:
		return examplars[utterance]

	#fuzzy match:
	#d = [(eddist(utterance, a), b) for a,b in examplars.items()]
	#if min(d)[0] < 5:
	#	return min(d)[1]

	#stitch together the best matching fragments:
	words, partialmeaning = utterance.split(), ['']
	l = len(words)
	while words:
		br = False
		for a in range(len(words), 0, -1):
			substring = " ".join(words[:a])
			for b in examplars:
				if substring in b and unifiespartially(examplars[b], partialmeaning):
					words = words[a:]
					br = True
					break
			if br: break
		#skip over words not in corpus
		if br == False:
			#return '' #partialmeaning[0]
			print "skipping", words[0]
			words = words[1:]

	return partialmeaning[0]

#transform a meaning into a response
def response(meaning, examplars):
	if 'imperative' in meaning:
		return 'confirmation'
	elif 'ynquestion' in meaning:
		return choice(('confirmation', 'denial', ''))
	elif 'question' in meaning:
		m = 'assertion: ' + meaning.split(':')[1]
		d = [(eddist(m, a), a) for a in examplars.values()]
		if min(d)[0] < len(meaning):
			r = choice([a for a in d if a[0] == min(d)[0]])[1]
			m = [m]
			if unifiesfully(r, m):
				return m[0]
		else:
			return ''
	#here we can decide to take spontaneous initiative (eg. "more juice!")
	elif 'assertion' in meaning:
		return 'acknowledgement'

	return ''

#transform a meaning into a two word utterance
def express(meaning, examplars):
	if meaning in examplars.values():
		return choice(revdict(examplars)[meaning])
	else:
		#find approximation
		d = [(eddist(meaning, a), b) for b, a in examplars.items()]
		if min(d)[0] < len(meaning):
			return choice([a for a in d if a[0] == min(d)[0]])[1]
		else:
			return '0'

def main():
	print "Child dialogue simulator. Enter parent utterance."
	print
	#read corpus
	examplars = {
		'uh': '',
		'eh': '',
		'ah': 'acknowledgement',
		'ok': 'confirmation',
		'yes': 'confirmation',
		'yeah': 'confirmation',
		'no': 'denial',
		'ball': 'assertion: point(ball) toy(ball)',
		'throw it to me': 'imperative: throw(X) toy(X)',
		'you kick the football !': 'imperative: kick(football) toy(football)',
		'what is this ?': 'question: point(ball) toy(ball)',
		'what does a bunny do ?': 'question: animal(bunny) do(X)',
		'who goes hop ?': 'question: animal(X) do(hop)',
		'bunny': 'assertion: animal(bunny) do(hop)',
		'hop': 'assertion: animal(bunny) do(hop)',
		'woof woof': 'assertion: animal(dog) do(woof)',
		'dog': 'assertion: point(dog) animal(dog)',
		'want some juice ?': 'ynquestion: want(juice) food(juice)',
		'chocolate': 'assertion: food(chocolate)'
		}
	print "Utterances in corpus: "
	print examplars.keys()
	print

	#main loop
	while 1:
		print "Parent: ",
		utt = raw_input()
		meaning = interpret(utt, examplars)
		print '	interpretation:', meaning
		reaction = response(meaning, examplars)
		print '	reaction:', reaction
		print "Child: ", express(reaction, examplars)

if __name__ == '__main__': main()