Vorlesung 4 Lemke

Aus ProgrammingWiki

Archivierte Version vom 2021-04-17T17:34:04+00:00. Aktuelle Version

Kreativaufgabe S. 15

Aufzählfunktion für semi-entscheidbare Menge

import signal

from itertools import product
from math import sqrt

'''
A = {a, b, c}
M = words that begin with ab
'''

ALPHABET = 'abc'
a = 'ab'

def timeout(signum, frame):
	raise Exception('Stop waiting')

def semi_chi(word):
	if word[0:2] == 'ab':
		return True
	else:
		while True:
			pass
			
def generate_words_with_length(length):
	return ["".join(x) for x in product(ALPHABET, repeat=length)]
			
def generate_wordset():
	length = 0
	while True:
		for w in generate_words_with_length(length):
			yield w
		length += 1
		
def get_word_at(wordset, index):
	for i in range(index+1):
		w = next(wordset)
		if i == index:
			return w
			
def get_x_y_from_z(z):
	w = int((sqrt(8 * z + 1) -1) / 2)
	t = int((w * (w + 1)) / 2) # has to be typecast bc otherwise it will be .0 float
	y = z - t
	x = w - y
	return (x, y)
	
def generate_M(z):
	x, y = get_x_y_from_z(z)
	signal.signal(signal.SIGALRM, timeout)
	signal.alarm(y+1)
	try:
		word = get_word_at(generate_wordset(), x)
		if semi_chi(word):
			return word
	except Exception:
		return a

for z in range(20):
	print(generate_M(z))

Vorlesung 4 Lemke

Kreativaufgabe S. 15

Aufzählfunktion für semi-entscheidbare Menge

Suche