Vorlesung 6 Nerlich

Aus ProgrammingWiki

Archivierte Version vom 2021-06-20T13:28:49+00:00. Aktuelle Version

S.11

v(x) = \begin{cases}0&x=0\\x-1&x>0\end{cases} h(x) = \begin{cases}x/2&2\text{ teilt }x\\0&\text{sonst}\end{cases} a(x) = \begin{cases}\perp&x=1234\vee x=7266281\\x&\text{sonst}\end{cases}

S.23

"""
    <Sprache>
    ________
  __\      /__
 |__   TM   __|
    /______\
    { True }
"""

"""
    <Sprache>
    ________
  __\      /__
 |__   TM   __|
    /______\
 { True, False }
"""

S.20

#!/usr/bin/env python3

from itertools import product

def nth(n: int, l: list):
	return map(lambda x: x[n-1], l)

def first(l: list):
	return nth(1, l)
def second(l: list):
	return nth(2, l)

def concatenation(l: list, idxs: list):
	l = list(l)
	return ''.join(map(lambda i: l[i], idxs))





def find_index_lists(pairs: list, search_all=False):
	length = 0
	while True:
		length += 1
		print("Searching for lists of length {}".format(length))
		l = find_index_lists_of_length(pairs, length, search_all=search_all)
		if l and not search_all:
				return l

def find_index_lists_of_length(pairs: list, length: int, search_all=False):
	for index_list in product(range(0,len(pairs)), repeat=length):
		concat = concatenation(first(pairs), index_list)
		if concat == concatenation(second(pairs), index_list):
			print("Found solution: {}  ({})".format(index_list, concat))
			if not search_all:
				return index_list

def inspect(pairs: list, idxs: list):
	one = concatenation(first(pairs), idxs)
	two = concatenation(second(pairs), idxs)
	if one == two:
		print("MATCH! {}  →  {}".format(idxs, one))
	else:
		print("no match. {}  ↓\n{}\n{}".format(idxs, one, two))


def parse_k(s: str):
	if s[0] == '[' or s[-1] == ']':
		return list(map(lambda x: tuple(x.split(',')), s[2:-2].split('),(')))
	elif s[0] == '(' or s[-1] == ')':
		return tuple(map(lambda x: tuple(x.split(',')), s[2:-2].split('),(')))
	else:
		raise ValueError("Invalid element for K: {}".format(s))

"""
if __name__ == '__main__':
	import sys
	
	if len(sys.argv) == 1:
		print("Usage:  {} K [TEST_LIST]\n        with K being a list like:  [(001,0),(01,011),(01,101),(10,001)]\n        and TEST_LIST being an index list like:  [0, 2, 1, 2]".format(sys.argv[0]))
	else:
		args = sys.argv[1:]
		args[0] = parse_k(args[0])

		if len(args) == 2:
			index_list = tuple(map(lambda s: int(s), args[1][1:-1].split(',')))
			inspect(args[0], index_list)
		else:
			find_index_lists(*args)
"""

find_index_lists([('1', '101'), ('10', '00'), ('011', '11')])

inspect([('001', '0'), ('01', '011'), ('01', '101'), ('10', '001')],
    (1, 3, 2, 3, 3, 1, 0, 1, 3, 2, 3, 2, 3, 3, 2, 3, 3, 1, 0, 3, 3, 1, 0, 2, 3, 0, 0, 2, 3, 3, 3, 1, 0, 1, 0, 0, 0, 2, 3, 2, 3, 0, 1, 0, 3, 3, 1, 0, 3, 0, 0, 2, 3, 0, 0, 2, 0, 0, 2, 0, 1, 0, 3, 0, 0, 2))

Vorlesung 6 Nerlich

S.11

S.23

S.20

Suche