import itertools
import random
from timeit import default_timer as timer

def dreieckszahl(n):
	return n*(n+1) // 2

def index(i, j):
	return dreieckszahl(i) + j

def dreiecksumme(liste, n):
	summe = 0;
	for i in range(1, n):
		for j in range(1, 1 + i):
			zahl1 = liste[index(i, j)]
			zahl2 = liste[index(i, j-1)]
			zahl3 = liste[index(i-1, j-1)]
			diff = abs(zahl1-zahl2) + abs(zahl2-zahl3) + abs(zahl3-zahl1)
			summe += diff
	return summe

def ausgabe(liste, n):
	for i in range(n):
		zeile = ''
		for j in range(1 + i):
			zeile += str(liste[index(i, j)]) + ' ' 
		print(zeile)
	print(f'DSDSmax={dreiecksumme(liste, n)}')

def solve(n):
	anzahl = dreieckszahl(n)
	zahlen = [i for i in range(anzahl)]
	beste_liste = zahlen
	DSDSmax = 0

	for p in itertools.permutations(zahlen):
		liste = list(p) 
		ds = dreiecksumme(liste, n)
		if ds > DSDSmax:
			DSDSmax = ds
			beste_liste = liste
	ausgabe(beste_liste, n)

def solve_rnd(n):
	anzahl = dreieckszahl(n)
	liste = [i for i in range(anzahl)]
	beste_liste = [e for e in liste]
	DSDSmax = 0
	zufallsversuche = 1000000
	print(f'Untersuche {zufallsversuche} Belegungen')
	for zaehler in range(zufallsversuche):
		random.shuffle(liste)
		ds = dreiecksumme(liste, n)
		if ds > DSDSmax:
			DSDSmax = ds
			beste_liste = [e for e in liste]
			print(f'{1+zaehler}\t{DSDSmax}') 
	ausgabe(beste_liste, n)

def main():
	for n in range(8):
		start = timer()
		solve_rnd(n)
		end = timer()
		print(f'{n}\t{end-start:.4} s')

if __name__ == '__main__':
	main()