Prosty problem jako zadanie z programowania

Każdy pomysł na fajne zadanie z programowania jest bardzo cenny. Dobre zadanie dla studentów powinno być ciekawe i powiązane z jakimś życiowym problemem, tak aby łatwiej było się skupić na samej istocie programowania a nie na samym problemie. Sam chodziłem kiedyś na zajęcia, gdzie prowadzący wymyślał abstrakcyjne problemy, które łatwo było oprogramować, ale bardzo trudno było zrozumieć o co chodzi i po co to wszystko. Wczoraj otworzyłem nowy wielopak zapałek i okazały się to być te z klasyczną łamigłówką z przekładaniem jednej zapałki:

img_1110

Pomyślałem, że mogło by to być fajne zadanie dla studentów I roku. Ja zazwyczaj uczę Pythona, więc podjąłem próbę napisania programu. W pierwszej wersji zadaniem programu jest po prostu znalezienie rozwiązania (lub rozwiązań) pojedynczego problemu:


plus = dict()
plus[0] = [8]
plus[1] = [7]
plus[2] = []
plus[3] = [9]
plus[4] = []
plus[5] = [9]
plus[6] = [8]
plus[7] = []
plus[8] = []
plus[9] = [8]

minus = dict()
minus[0] = []
minus[1] = []
minus[2] = []
minus[3] = []
minus[4] = []
minus[5] = []
minus[6] = []
minus[7] = [1]
minus[8] = [0, 6, 9]
minus[9] = [3, 5]

swap = dict()
swap[0] = [6, 9]
swap[1] = []
swap[2] = [3]
swap[3] = [2, 5]
swap[4] = []
swap[5] = [3]
swap[6] = [0, 9]
swap[7] = []
swap[8] = []
swap[9] = [0, 6]


def test_single(a, o1, b, o2, c):
	if o2 == "=":
		if o1 == "+":
			return a+b==c
		elif o1 == "-":
			return a-b==c
		else:
			print('ERROR')
	elif o1 == "=":
		if o2 == "+":
			return a+b==c
		elif o2 == "-":
			return a-b==c
		else:
			print('ERROR')
	else:
		print('ERROR')
def print_result(a, o1, b, o2, c,debug):
	print("{5}: {0}{1}{2}{3}{4}:".format(a,o1,b,o2,c,debug), test_single(a, o1, b, o2, c));


def all_comb(a, o1, b, o2, c):
	#print("SWAPY")
	for a1 in swap[a]:
		print_result(a1, o1, b, o2, c,1)
	for b1 in swap[b]:
		print_result(a, o1, b1, o2, c,2)
	for c1 in swap[c]:
		print_result(a, o1, b, o2, c1,3)
	if o1 == '-':
		print_result(a, "=", b, "-", c,4)
	#print("A minus")
	for a1 in minus[a]:
		for b1 in plus[b]:
			print_result(a1, o1, b1, o2, c,5)
		for c1 in plus[c]:
			print_result(a1, o1, b, o2, c1,6)
		if o1 == "-":
			print_result(a1, "+", b, o2, c,7)
		if o2 == "-":
			print_result(a1, o1, b, "+", c,8)
	#print("B minus")
	for b1 in minus[b]:
		for a1 in plus[a]:
			print_result(a1, o1, b1, o2, c,9)
		for c1 in plus[c]:
			print_result(a, o1, b1, o2, c1,10)
		if o1 == "-":
			print_result(a, "+", b1, o2, c,11)
		if o2 == "-":
			print_result(a, o1, b1, "+", c,12)
	#print("C minus")
	for c1 in minus[c]:
		for b1 in plus[b]:
			print_result(a, o1, b1, o2, c1,13)
		for a1 in plus[a]:
			print_result(a1, o1, b, o2, c1,14)
		if o1 == "-":
			print_result(a, "+", b, o2, c1,15)
		if o2 == "-":
			print_result(a, o1, b, "+", c1,16)

	#print("+ minus")
	if o1 == "+":
		for a1 in plus[a]:
			print_result(a1, "-", b, o2, c,17)
		for b1 in plus[b]:
			print_result(a, "-", b1, o2, c,18)
		for c1 in plus[c]:
			print_result(a, "-", b, o2, c1,19)


all_comb(1,"+",2,"=",8)

Nie jest to rozwiązanie w żaden sposób zoptymalizowane. Byłbym zadowolony, gdyby na zajęciach udało się dojść do takiego rozwiązania. Dla równania 1+2=8 program zwraca taki wynik:

screenshot_43

Działanie programu opiera się po pierwsze na 3 zdefiniowanych słownikach, które określają na jaką cyfrę można zmienić daną cyfrę po odjęciu, dodaniu i przełożeniu jednej zapałki. Po drugie program przewiduje wszystkie przypadki zamian: np. odjęcie zapałki z pierwszej cyfry i dodanie do cyfry drugiej lub trzeciej. W sumie przewidziane jest 19 przypadków (może da się to zoptymalizować?).

Drugą, równie ciekawą wersją programu jest wygenerowanie wszystkich możliwych łamigłówek. Tu należy zdecydować, czy rozważamy te równania, które są poprawne na wejściu. Ja zdecydowałem ich nie pomijać, bo wymagamy poprawności po przełożeniu jednej zapałki. Kod wygląda tak:


plus = dict()
plus[0] = [8]
plus[1] = [7]
plus[2] = []
plus[3] = [9]
plus[4] = []
plus[5] = [9]
plus[6] = [8]
plus[7] = []
plus[8] = []
plus[9] = [8]

minus = dict()
minus[0] = []
minus[1] = []
minus[2] = []
minus[3] = []
minus[4] = []
minus[5] = []
minus[6] = []
minus[7] = [1]
minus[8] = [0, 6, 9]
minus[9] = [3, 5]

swap = dict()
swap[0] = [6, 9]
swap[1] = []
swap[2] = [3]
swap[3] = [2, 5]
swap[4] = []
swap[5] = [3]
swap[6] = [0, 9]
swap[7] = []
swap[8] = []
swap[9] = [0, 6]


def test_single(a, o1, b, o2, c):
	if o2 == "=":
		if o1 == "+":
			return a+b==c
		elif o1 == "-":
			return a-b==c
		else:
			print('ERROR')
	elif o1 == "=":
		if o2 == "+":
			return a+b==c
		elif o2 == "-":
			return a-b==c
		else:
			print('ERROR')
	else:
		print('ERROR')
def print_result(wa,wo1,wb,wo2,wc,a, o1, b, o2, c):
	if test_single(a, o1, b, o2, c):
		print("{0}{1}{2}{3}{4} -> {5}{6}{7}{8}{9}".format(wa,wo1,wb,wo2,wc,a,o1,b,o2,c))
		return 1
	else:
		return 0;


def all_comb(a, o1, b, o2, c):
	count = 0
	for a1 in swap[a]:
		count = count + print_result(a,o1,b,o2,c,a1, o1, b, o2, c)
	for b1 in swap[b]:
		count = count + print_result(a,o1,b,o2,c,a, o1, b1, o2, c)
	for c1 in swap[c]:
		count = count + print_result(a,o1,b,o2,c,a, o1, b, o2, c1)
	if o1 == '-':
		count = count + print_result(a,o1,b,o2,c,a, "=", b, "-", c)
	for a1 in minus[a]:
		for b1 in plus[b]:
			count = count + print_result(a,o1,b,o2,c,a1, o1, b1, o2, c)
		for c1 in plus[c]:
			count = count + print_result(a,o1,b,o2,c,a1, o1, b, o2, c1)
		if o1 == "-":
			count = count + print_result(a,o1,b,o2,c,a1, "+", b, o2, c)
		if o2 == "-":
			count = count + print_result(a,o1,b,o2,c,a1, o1, b, "+", c)
	for b1 in minus[b]:
		for a1 in plus[a]:
			count = count + print_result(a,o1,b,o2,c,a1, o1, b1, o2, c)
		for c1 in plus[c]:
			count = count + print_result(a,o1,b,o2,c,a, o1, b1, o2, c1)
		if o1 == "-":
			count = count + print_result(a,o1,b,o2,c,a, "+", b1, o2, c)
		if o2 == "-":
			count = count + print_result(a,o1,b,o2,c,a, o1, b1, "+", c)
	for c1 in minus[c]:
		for b1 in plus[b]:
			count = count + print_result(a,o1,b,o2,c,a, o1, b1, o2, c1)
		for a1 in plus[a]:
			count = count + print_result(a,o1,b,o2,c,a1, o1, b, o2, c1)
		if o1 == "-":
			count = count + print_result(a,o1,b,o2,c,a, "+", b, o2, c1)
		if o2 == "-":
			count = count + print_result(a,o1,b,o2,c,a, o1, b, "+", c1)
	if o1 == "+":
		for a1 in plus[a]:
			count = count + print_result(a,o1,b,o2,c,a1, "-", b, o2, c)
		for b1 in plus[b]:
			count = count + print_result(a,o1,b,o2,c,a, "-", b1, o2, c)
		for c1 in plus[c]:
			count = count + print_result(a,o1,b,o2,c,a, "-", b, o2, c1)
	return count

for to1 in ["+", "-"]:
	for ta in range(10):
		for tb in range(10):
			for tc in range(10):
				tcount = all_comb(ta,to1,tb,"=",tc)
				#if tcount > 2:
				#	print("{0}{1}{2}{3}{4}".format(ta,to1,tb,"=",tc), tcount)

Wynik jest obliczany w mgnieniu oka. Dla rozwiązania dla łamigłówek z obrazka są następujące:

screenshot_44

Lista wszystkich kombinacji dla potomnych:

0+0=6 -> 6+0=6
0+0=6 -> 0+6=6
0+0=6 -> 0+0=0
0+0=8 -> 8-0=8
0+0=9 -> 9+0=9
0+0=9 -> 0+9=9
0+0=9 -> 0+0=0
0+1=7 -> 6+1=7
0+1=7 -> 8-1=7
0+1=8 -> 8+1=9
0+2=3 -> 0+3=3
0+2=3 -> 0+2=2
0+2=6 -> 8-2=6
0+2=8 -> 6+2=8
0+3=2 -> 0+2=2
0+3=2 -> 0+3=3
0+3=5 -> 0+5=5
0+3=5 -> 0+3=3
0+3=5 -> 8-3=5
0+3=8 -> 0+9=9
0+3=9 -> 6+3=9
0+4=4 -> 8-4=4
0+5=3 -> 0+3=3
0+5=3 -> 0+5=5
0+5=3 -> 8-5=3
0+5=8 -> 0+9=9
0+6=0 -> 0+0=0
0+6=0 -> 0+6=6
0+6=2 -> 8-6=2
0+6=9 -> 0+9=9
0+6=9 -> 0+6=6
0+7=1 -> 8-7=1
0+7=9 -> 8+1=9
0+8=0 -> 8-8=0
0+8=3 -> 0+9=9
0+8=5 -> 0+9=9
0+8=8 -> 8+0=8
0+9=0 -> 0+0=0
0+9=0 -> 0+9=9
0+9=6 -> 0+6=6
0+9=6 -> 0+9=9
1+0=7 -> 1+6=7
1+0=7 -> 7-0=7
1+0=8 -> 1+8=9
1+1=3 -> 1+1=2
1+1=6 -> 7-1=6
1+2=2 -> 1+2=3
1+2=4 -> 1+3=4
1+2=5 -> 1+2=3
1+2=5 -> 7-2=5
1+2=8 -> 7+2=9
1+3=3 -> 1+2=3
1+3=4 -> 7-3=4
1+3=6 -> 1+5=6
1+4=3 -> 1+4=5
1+4=3 -> 7-4=3
1+5=0 -> 1+5=6
1+5=2 -> 7-5=2
1+5=4 -> 1+3=4
1+5=9 -> 1+5=6
1+6=1 -> 1+0=1
1+6=1 -> 7-6=1
1+6=8 -> 1+8=9
1+7=0 -> 7-7=0
1+7=8 -> 7+1=8
1+8=0 -> 1+8=9
1+8=1 -> 1+6=7
1+8=6 -> 1+8=9
1+8=7 -> 7+0=7
1+9=1 -> 1+0=1
1+9=7 -> 1+6=7
1+9=8 -> 1+8=9
2+0=3 -> 3+0=3
2+0=3 -> 2+0=2
2+0=8 -> 2+6=8
2+1=2 -> 2+1=3
2+1=4 -> 3+1=4
2+1=5 -> 2+1=3
2+1=8 -> 2+7=9
2+2=5 -> 3+2=5
2+2=5 -> 2+3=5
2+3=3 -> 2+3=5
2+3=4 -> 2+2=4
2+3=6 -> 3+3=6
2+3=7 -> 2+5=7
2+4=0 -> 2+4=6
2+4=7 -> 3+4=7
2+4=9 -> 2+4=6
2+5=5 -> 2+3=5
2+5=8 -> 3+5=8
2+6=2 -> 2+0=2
2+6=9 -> 3+6=9
2+7=0 -> 2+7=9
2+7=6 -> 2+7=9
2+8=0 -> 2+6=8
2+8=6 -> 2+6=8
2+8=9 -> 2+6=8
2+9=1 -> 2+5=7
2+9=2 -> 2+0=2
2+9=8 -> 2+6=8
3+0=2 -> 2+0=2
3+0=2 -> 3+0=3
3+0=5 -> 5+0=5
3+0=5 -> 3+0=3
3+0=8 -> 9+0=9
3+0=9 -> 3+6=9
3+0=9 -> 9-0=9
3+1=3 -> 2+1=3
3+1=6 -> 5+1=6
3+1=8 -> 9-1=8
3+2=3 -> 3+2=5
3+2=4 -> 2+2=4
3+2=6 -> 3+3=6
3+2=7 -> 5+2=7
3+2=7 -> 9-2=7
3+3=0 -> 3+3=6
3+3=5 -> 2+3=5
3+3=5 -> 3+2=5
3+3=6 -> 9-3=6
3+3=8 -> 5+3=8
3+3=8 -> 3+5=8
3+3=9 -> 3+3=6
3+4=5 -> 9-4=5
3+4=6 -> 2+4=6
3+4=9 -> 5+4=9
3+5=4 -> 9-5=4
3+5=6 -> 3+3=6
3+5=7 -> 2+5=7
3+6=0 -> 3+6=9
3+6=3 -> 3+0=3
3+6=3 -> 9-6=3
3+6=6 -> 3+6=9
3+6=8 -> 2+6=8
3+7=2 -> 9-7=2
3+7=9 -> 2+7=9
3+8=1 -> 9-8=1
3+8=3 -> 3+6=9
3+8=5 -> 3+6=9
3+8=9 -> 9+0=9
3+9=0 -> 3+5=8
3+9=0 -> 9-9=0
3+9=3 -> 3+0=3
3+9=6 -> 3+5=8
3+9=9 -> 3+6=9
3+9=9 -> 3+5=8
4+1=3 -> 4+1=5
4+2=0 -> 4+2=6
4+2=7 -> 4+3=7
4+2=9 -> 4+2=6
4+3=6 -> 4+2=6
4+3=9 -> 4+5=9
4+5=0 -> 4+5=9
4+5=6 -> 4+5=9
4+5=7 -> 4+3=7
4+6=4 -> 4+0=4
4+9=1 -> 4+3=7
4+9=3 -> 4+5=9
4+9=4 -> 4+0=4
4+9=5 -> 4+5=9
5+0=3 -> 3+0=3
5+0=3 -> 5+0=5
5+0=8 -> 9+0=9
5+0=9 -> 9-0=9
5+1=0 -> 5+1=6
5+1=4 -> 3+1=4
5+1=8 -> 9-1=8
5+1=9 -> 5+1=6
5+2=5 -> 3+2=5
5+2=7 -> 9-2=7
5+2=8 -> 5+3=8
5+3=6 -> 3+3=6
5+3=6 -> 9-3=6
5+3=7 -> 5+2=7
5+4=0 -> 5+4=9
5+4=5 -> 9-4=5
5+4=6 -> 5+4=9
5+4=7 -> 3+4=7
5+5=4 -> 9-5=4
5+5=8 -> 3+5=8
5+5=8 -> 5+3=8
5+6=3 -> 9-6=3
5+6=5 -> 5+0=5
5+6=9 -> 3+6=9
5+7=2 -> 9-7=2
5+8=1 -> 9-8=1
5+8=9 -> 9+0=9
5+9=0 -> 5+3=8
5+9=0 -> 9-9=0
5+9=5 -> 5+0=5
5+9=6 -> 5+3=8
5+9=9 -> 5+3=8
6+0=0 -> 0+0=0
6+0=0 -> 6+0=6
6+0=8 -> 8-0=8
6+0=9 -> 9+0=9
6+0=9 -> 6+0=6
6+1=1 -> 0+1=1
6+1=7 -> 8-1=7
6+1=8 -> 8+1=9
6+2=2 -> 0+2=2
6+2=6 -> 8-2=6
6+2=9 -> 6+3=9
6+3=0 -> 6+3=9
6+3=3 -> 0+3=3
6+3=5 -> 8-3=5
6+3=6 -> 6+3=9
6+3=8 -> 6+2=8
6+4=4 -> 0+4=4
6+4=4 -> 8-4=4
6+5=3 -> 8-5=3
6+5=5 -> 0+5=5
6+5=9 -> 6+3=9
6+6=2 -> 8-6=2
6+6=6 -> 0+6=6
6+6=6 -> 6+0=6
6+7=1 -> 6+1=7
6+7=1 -> 8-7=1
6+7=7 -> 0+7=7
6+7=9 -> 8+1=9
6+8=0 -> 8-8=0
6+8=8 -> 0+8=8
6+8=8 -> 8+0=8
6+9=3 -> 6+3=9
6+9=5 -> 6+3=9
6+9=6 -> 6+0=6
6+9=9 -> 0+9=9
7+0=1 -> 7-0=7
7+0=9 -> 1+8=9
7+1=0 -> 7-7=0
7+1=8 -> 1+7=8
7+2=0 -> 7+2=9
7+2=6 -> 7+2=9
7+3=9 -> 7+2=9
7+6=1 -> 1+6=7
7+6=7 -> 7+0=7
7+6=9 -> 1+8=9
7+7=0 -> 1+7=8
7+7=0 -> 7+1=8
7+7=6 -> 1+7=8
7+7=6 -> 7+1=8
7+7=9 -> 1+7=8
7+7=9 -> 7+1=8
7+8=1 -> 7+0=7
7+8=3 -> 1+8=9
7+8=5 -> 1+8=9
7+9=7 -> 7+0=7
7+9=9 -> 1+8=9
8+0=0 -> 8-8=0
8+0=0 -> 8-0=8
8+0=3 -> 9+0=9
8+0=5 -> 9+0=9
8+0=6 -> 8-0=8
8+0=8 -> 0+8=8
8+0=9 -> 8-0=8
8+1=0 -> 8+1=9
8+1=1 -> 6+1=7
8+1=1 -> 8-7=1
8+1=1 -> 8-1=7
8+1=6 -> 8+1=9
8+1=7 -> 0+7=7
8+2=0 -> 6+2=8
8+2=6 -> 6+2=8
8+2=9 -> 6+2=8
8+3=3 -> 6+3=9
8+3=5 -> 6+3=9
8+3=9 -> 0+9=9
8+5=9 -> 0+9=9
8+6=0 -> 8-8=0
8+6=8 -> 8+0=8
8+6=8 -> 0+8=8
8+7=1 -> 0+7=7
8+7=3 -> 8+1=9
8+7=5 -> 8+1=9
8+8=0 -> 0+8=8
8+8=0 -> 8+0=8
8+8=6 -> 0+8=8
8+8=6 -> 8+0=8
8+8=9 -> 0+8=8
8+8=9 -> 8+0=8
8+9=0 -> 8-8=0
8+9=3 -> 0+9=9
8+9=5 -> 0+9=9
8+9=8 -> 8+0=8
8+9=8 -> 0+8=8
9+0=0 -> 0+0=0
9+0=0 -> 9+0=9
9+0=1 -> 9-8=1
9+0=3 -> 9-0=9
9+0=5 -> 9-0=9
9+0=6 -> 6+0=6
9+0=6 -> 9+0=9
9+0=8 -> 8-0=8
9+1=0 -> 9-1=8
9+1=1 -> 0+1=1
9+1=2 -> 9-7=2
9+1=6 -> 9-1=8
9+1=7 -> 6+1=7
9+1=7 -> 8-1=7
9+1=8 -> 8+1=9
9+1=9 -> 9-1=8
9+2=1 -> 5+2=7
9+2=1 -> 9-2=7
9+2=2 -> 0+2=2
9+2=6 -> 8-2=6
9+2=8 -> 6+2=8
9+3=0 -> 5+3=8
9+3=0 -> 9-9=0
9+3=3 -> 0+3=3
9+3=5 -> 8-3=5
9+3=6 -> 5+3=8
9+3=9 -> 6+3=9
9+3=9 -> 5+3=8
9+4=1 -> 3+4=7
9+4=3 -> 5+4=9
9+4=4 -> 0+4=4
9+4=4 -> 8-4=4
9+4=5 -> 5+4=9
9+5=0 -> 3+5=8
9+5=0 -> 9-9=0
9+5=3 -> 8-5=3
9+5=5 -> 0+5=5
9+5=6 -> 3+5=8
9+5=9 -> 3+5=8
9+6=1 -> 9-8=1
9+6=2 -> 8-6=2
9+6=3 -> 3+6=9
9+6=5 -> 3+6=9
9+6=6 -> 0+6=6
9+6=9 -> 9+0=9
9+7=1 -> 8-7=1
9+7=7 -> 0+7=7
9+7=9 -> 8+1=9
9+8=0 -> 8-8=0
9+8=3 -> 9+0=9
9+8=5 -> 9+0=9
9+8=8 -> 0+8=8
9+8=8 -> 8+0=8
9+9=1 -> 9-8=1
9+9=9 -> 0+9=9
9+9=9 -> 9+0=9
0-0=0 -> 0=0-0
0-0=6 -> 6-0=6
0-0=6 -> 0-0=0
0-0=8 -> 0+0=0
0-0=9 -> 9-0=9
0-0=9 -> 0-0=0
0-1=5 -> 6-1=5
0-1=7 -> 0+1=1
0-1=8 -> 9-1=8
0-2=4 -> 6-2=4
0-2=7 -> 9-2=7
0-2=8 -> 8-2=6
0-3=3 -> 6-3=3
0-3=6 -> 9-3=6
0-3=9 -> 0+3=3
0-3=9 -> 8-3=5
0-4=2 -> 6-4=2
0-4=5 -> 9-4=5
0-5=1 -> 6-5=1
0-5=4 -> 9-5=4
0-5=9 -> 8-5=3
0-5=9 -> 0+5=5
0-6=0 -> 6-6=0
0-6=0 -> 0-0=0
0-6=3 -> 9-6=3
0-6=8 -> 0+6=6
0-7=1 -> 0+1=1
0-7=2 -> 9-7=2
0-7=7 -> 8-1=7
0-7=7 -> 8-7=1
0-8=0 -> 0+0=0
0-8=1 -> 9-8=1
0-8=2 -> 8-6=2
0-8=6 -> 0+6=6
0-8=8 -> 8-0=8
0-8=8 -> 8-8=0
0-8=9 -> 0+9=9
0-9=0 -> 9-9=0
0-9=0 -> 0-0=0
0-9=3 -> 0+3=3
0-9=3 -> 8-5=3
0-9=5 -> 8-3=5
0-9=5 -> 0+5=5
0-9=8 -> 0+9=9
1-0=1 -> 1=0-1
1-0=7 -> 1+0=1
1-1=0 -> 1=1-0
1-1=6 -> 1-1=0
1-1=8 -> 7-1=6
1-1=9 -> 1-1=0
1-2=9 -> 1+2=3
1-2=9 -> 7-2=5
1-4=9 -> 7-4=3
1-4=9 -> 1+4=5
1-5=8 -> 1+5=6
1-6=1 -> 1-0=1
1-6=7 -> 7-6=1
1-7=2 -> 1+1=2
1-7=6 -> 7-1=6
1-7=8 -> 7-7=0
1-8=1 -> 1+0=1
1-8=1 -> 7-6=1
1-8=7 -> 7-0=7
1-8=7 -> 1+6=7
1-8=8 -> 1+8=9
1-9=1 -> 1-0=1
1-9=2 -> 7-5=2
1-9=4 -> 7-3=4
1-9=4 -> 1+3=4
1-9=6 -> 1+5=6
2-0=2 -> 2=0-2
2-0=3 -> 3-0=3
2-0=3 -> 2-0=2
2-1=1 -> 2=1-1
2-1=2 -> 3-1=2
2-1=9 -> 2+1=3
2-2=0 -> 2=2-0
2-2=1 -> 3-2=1
2-2=6 -> 2-2=0
2-2=9 -> 2-2=0
2-3=0 -> 3-3=0
2-3=0 -> 2-2=0
2-3=9 -> 2+3=5
2-4=8 -> 2+4=6
2-6=2 -> 2-0=2
2-7=3 -> 2+1=3
2-7=8 -> 2+7=9
2-8=2 -> 2+0=2
2-8=8 -> 2+6=8
2-9=2 -> 2-0=2
2-9=5 -> 2+3=5
2-9=7 -> 2+5=7
3-0=2 -> 2-0=2
3-0=2 -> 3-0=3
3-0=3 -> 3=0-3
3-0=5 -> 5-0=5
3-0=5 -> 3-0=3
3-0=8 -> 9-0=9
3-0=9 -> 3+0=3
3-1=1 -> 2-1=1
3-1=2 -> 3=1-2
3-1=3 -> 3-1=2
3-1=4 -> 5-1=4
3-2=0 -> 2-2=0
3-2=0 -> 3-3=0
3-2=1 -> 3=2-1
3-2=3 -> 5-2=3
3-2=9 -> 3+2=5
3-3=0 -> 3=3-0
3-3=1 -> 3-2=1
3-3=2 -> 5-3=2
3-3=6 -> 3-3=0
3-3=8 -> 9-3=6
3-3=8 -> 3+3=6
3-3=9 -> 3-3=0
3-4=1 -> 5-4=1
3-4=9 -> 9-4=5
3-5=0 -> 5-5=0
3-5=0 -> 3-3=0
3-6=3 -> 3-0=3
3-6=8 -> 3+6=9
3-6=9 -> 9-6=3
3-7=4 -> 3+1=4
3-7=8 -> 9-1=8
3-8=0 -> 9-9=0
3-8=3 -> 3+0=3
3-8=3 -> 9-6=3
3-8=7 -> 9-8=1
3-8=9 -> 9-0=9
3-8=9 -> 3+6=9
3-9=3 -> 3-0=3
3-9=4 -> 9-5=4
3-9=6 -> 9-3=6
3-9=6 -> 3+3=6
3-9=8 -> 3+5=8
3-9=8 -> 9-9=0
4-0=4 -> 4=0-4
4-1=2 -> 4-1=3
4-1=3 -> 4=1-3
4-1=5 -> 4-1=3
4-1=9 -> 4+1=5
4-2=1 -> 4-3=1
4-2=2 -> 4=2-2
4-2=3 -> 4-2=2
4-2=8 -> 4+2=6
4-3=1 -> 4=3-1
4-3=2 -> 4-2=2
4-4=0 -> 4=4-0
4-4=6 -> 4-4=0
4-4=9 -> 4-4=0
4-5=1 -> 4-3=1
4-5=8 -> 4+5=9
4-6=4 -> 4-0=4
4-7=5 -> 4+1=5
4-8=4 -> 4+0=4
4-9=4 -> 4-0=4
4-9=7 -> 4+3=7
4-9=9 -> 4+5=9
5-0=3 -> 3-0=3
5-0=3 -> 5-0=5
5-0=5 -> 5=0-5
5-0=8 -> 9-0=9
5-0=9 -> 5+0=5
5-1=2 -> 3-1=2
5-1=4 -> 5=1-4
5-1=8 -> 5+1=6
5-2=1 -> 3-2=1
5-2=2 -> 5-3=2
5-2=2 -> 5-2=3
5-2=3 -> 5=2-3
5-2=5 -> 5-2=3
5-3=0 -> 3-3=0
5-3=0 -> 5-5=0
5-3=2 -> 5=3-2
5-3=3 -> 5-2=3
5-3=3 -> 5-3=2
5-3=8 -> 9-3=6
5-4=1 -> 5=4-1
5-4=8 -> 5+4=9
5-4=9 -> 9-4=5
5-5=0 -> 5=5-0
5-5=2 -> 5-3=2
5-5=6 -> 5-5=0
5-5=9 -> 5-5=0
5-6=5 -> 5-0=5
5-6=9 -> 9-6=3
5-7=6 -> 5+1=6
5-7=8 -> 9-1=8
5-8=0 -> 9-9=0
5-8=3 -> 9-6=3
5-8=5 -> 5+0=5
5-8=7 -> 9-8=1
5-8=9 -> 9-0=9
5-9=4 -> 9-5=4
5-9=5 -> 5-0=5
5-9=6 -> 9-3=6
5-9=8 -> 5+3=8
5-9=8 -> 9-9=0
6-0=0 -> 0-0=0
6-0=0 -> 6-6=0
6-0=0 -> 6-0=6
6-0=6 -> 6=0-6
6-0=8 -> 6+0=6
6-0=9 -> 9-0=9
6-0=9 -> 6-0=6
6-1=3 -> 6-1=5
6-1=5 -> 6=1-5
6-1=8 -> 9-1=8
6-2=3 -> 6-3=3
6-2=4 -> 6=2-4
6-2=7 -> 9-2=7
6-2=8 -> 8-2=6
6-3=1 -> 6-5=1
6-3=2 -> 6-3=3
6-3=3 -> 6=3-3
6-3=4 -> 6-2=4
6-3=5 -> 6-3=3
6-3=6 -> 9-3=6
6-3=8 -> 6+3=9
6-3=9 -> 8-3=5
6-4=2 -> 6=4-2
6-4=3 -> 6-4=2
6-4=5 -> 9-4=5
6-5=1 -> 6=5-1
6-5=3 -> 6-3=3
6-5=4 -> 9-5=4
6-5=9 -> 8-5=3
6-6=0 -> 6=6-0
6-6=3 -> 9-6=3
6-6=6 -> 6-0=6
6-6=6 -> 6-6=0
6-6=9 -> 6-6=0
6-7=2 -> 9-7=2
6-7=7 -> 8-1=7
6-7=7 -> 6+1=7
6-7=7 -> 8-7=1
6-8=1 -> 9-8=1
6-8=2 -> 8-6=2
6-8=6 -> 6+0=6
6-8=8 -> 8-0=8
6-8=8 -> 8-8=0
6-9=0 -> 9-9=0
6-9=0 -> 6-6=0
6-9=3 -> 8-5=3
6-9=5 -> 8-3=5
6-9=6 -> 6-0=6
6-9=9 -> 6+3=9
7-0=1 -> 7-6=1
7-0=1 -> 1+0=1
7-0=7 -> 7=0-7
7-1=0 -> 7-1=6
7-1=2 -> 1+1=2
7-1=6 -> 7=1-6
7-1=8 -> 7-7=0
7-1=9 -> 7-1=6
7-2=3 -> 7-2=5
7-2=3 -> 1+2=3
7-2=4 -> 7-3=4
7-2=5 -> 7=2-5
7-2=8 -> 7+2=9
7-3=2 -> 7-5=2
7-3=4 -> 7=3-4
7-3=4 -> 1+3=4
7-3=5 -> 7-2=5
7-4=2 -> 7-4=3
7-4=3 -> 7=4-3
7-4=5 -> 7-4=3
7-4=5 -> 1+4=5
7-5=2 -> 7=5-2
7-5=3 -> 7-5=2
7-5=4 -> 7-3=4
7-5=6 -> 1+5=6
7-6=1 -> 7=6-1
7-6=7 -> 7-0=7
7-6=7 -> 1+6=7
7-7=0 -> 7=7-0
7-7=6 -> 7-7=0
7-7=8 -> 1+7=8
7-7=8 -> 7+1=8
7-7=9 -> 7-7=0
7-8=1 -> 7-0=7
7-8=7 -> 7+0=7
7-8=9 -> 1+8=9
7-9=1 -> 7-6=1
7-9=7 -> 7-0=7
8-0=0 -> 0+0=0
8-0=1 -> 9-8=1
8-0=2 -> 8-6=2
8-0=3 -> 9-0=9
8-0=5 -> 9-0=9
8-0=6 -> 6+0=6
8-0=8 -> 8=0-8
8-0=8 -> 8-8=0
8-0=9 -> 9+0=9
8-1=0 -> 9-1=8
8-1=1 -> 0+1=1
8-1=2 -> 9-7=2
8-1=6 -> 9-1=8
8-1=7 -> 8=1-7
8-1=7 -> 6+1=7
8-1=7 -> 8-7=1
8-1=8 -> 8+1=9
8-1=9 -> 9-1=8
8-2=0 -> 8-2=6
8-2=1 -> 9-2=7
8-2=2 -> 0+2=2
8-2=5 -> 8-3=5
8-2=6 -> 8=2-6
8-2=8 -> 6+2=8
8-2=9 -> 8-2=6
8-3=0 -> 9-9=0
8-3=3 -> 8-5=3
8-3=3 -> 8-3=5
8-3=3 -> 0+3=3
8-3=5 -> 8=3-5
8-3=6 -> 8-2=6
8-3=9 -> 6+3=9
8-4=4 -> 8=4-4
8-4=4 -> 0+4=4
8-5=0 -> 9-9=0
8-5=2 -> 8-5=3
8-5=3 -> 8=5-3
8-5=5 -> 8-3=5
8-5=5 -> 8-5=3
8-5=5 -> 0+5=5
8-6=1 -> 9-8=1
8-6=2 -> 8=6-2
8-6=3 -> 8-6=2
8-6=6 -> 0+6=6
8-6=8 -> 8-0=8
8-6=8 -> 8-8=0
8-7=1 -> 8=7-1
8-7=1 -> 8-1=7
8-7=7 -> 0+7=7
8-7=9 -> 8+1=9
8-8=0 -> 8=8-0
8-8=0 -> 8-0=8
8-8=6 -> 8-8=0
8-8=6 -> 8-0=8
8-8=8 -> 0+8=8
8-8=8 -> 8+0=8
8-8=9 -> 8-8=0
8-8=9 -> 8-0=8
8-9=1 -> 9-8=1
8-9=2 -> 8-6=2
8-9=8 -> 8-0=8
8-9=8 -> 8-8=0
8-9=9 -> 0+9=9
9-0=0 -> 0-0=0
9-0=0 -> 9-9=0
9-0=0 -> 9-0=9
9-0=3 -> 9-6=3
9-0=3 -> 3+0=3
9-0=5 -> 5+0=5
9-0=6 -> 6-0=6
9-0=6 -> 9-0=9
9-0=7 -> 9-8=1
9-0=8 -> 9+0=9
9-0=9 -> 9=0-9
9-1=4 -> 3+1=4
9-1=5 -> 6-1=5
9-1=6 -> 5+1=6
9-1=8 -> 9=1-8
9-2=4 -> 6-2=4
9-2=5 -> 3+2=5
9-2=6 -> 9-3=6
9-2=7 -> 9=2-7
9-2=7 -> 5+2=7
9-2=8 -> 8-2=6
9-3=0 -> 9-3=6
9-3=3 -> 6-3=3
9-3=4 -> 9-5=4
9-3=6 -> 9=3-6
9-3=6 -> 3+3=6
9-3=7 -> 9-2=7
9-3=8 -> 5+3=8
9-3=8 -> 9-9=0
9-3=9 -> 9-3=6
9-3=9 -> 8-3=5
9-4=2 -> 6-4=2
9-4=3 -> 9-4=5
9-4=5 -> 9=4-5
9-4=7 -> 3+4=7
9-4=9 -> 5+4=9
9-5=1 -> 6-5=1
9-5=4 -> 9=5-4
9-5=6 -> 9-3=6
9-5=8 -> 3+5=8
9-5=8 -> 9-9=0
9-5=9 -> 8-5=3
9-6=0 -> 6-6=0
9-6=0 -> 9-9=0
9-6=2 -> 9-6=3
9-6=3 -> 9=6-3
9-6=5 -> 9-6=3
9-6=7 -> 9-8=1
9-6=9 -> 9-0=9
9-6=9 -> 3+6=9
9-7=0 -> 9-1=8
9-7=2 -> 9=7-2
9-7=3 -> 9-7=2
9-7=6 -> 9-1=8
9-7=7 -> 8-1=7
9-7=7 -> 8-7=1
9-7=9 -> 9-1=8
9-8=1 -> 9=8-1
9-8=2 -> 8-6=2
9-8=3 -> 9-0=9
9-8=5 -> 9-0=9
9-8=8 -> 8-0=8
9-8=8 -> 8-8=0
9-8=9 -> 9+0=9
9-9=0 -> 9=9-0
9-9=3 -> 9-6=3
9-9=3 -> 8-5=3
9-9=5 -> 8-3=5
9-9=6 -> 9-9=0
9-9=7 -> 9-8=1
9-9=9 -> 9-0=9
9-9=9 -> 9-9=0

Mam nadzieję, że nie ma jakich drastycznych błędów w rozwiązaniu?

W ramach ćwiczeń polecam każdemu chętnemu rozwiązanie tego problemu w Waszym ulubionym języku programowania. Jeżeli twierdzicie, że da się prościej to zapewne macie racje, ale zawsze miło mi zobaczyć Wasz kod.

| Komentarze

Zdjęcia z kilku ostatnich lotów dronem

Drony pozwalają na spojrzenie na świat dookoła nas z innej perspektywy. W przeciągu ostatnich tygodni latałem kilkanaście razy i chciałem podzielić się z Wami zdjęciami, które udało mi się zrobić. Znad Wisły w okolicy mostu Świętokrzyskiego zrobiłem kila ujęć obydwu stron Warszawy:

dji_0010-hdrdji_0015-hdrdji_0069-hdr

Wyjątkowo ładny efekt udało mi się osiągnąć poprzez połączenie 5 ujęć (wszystkie HDR) w panoramę:

dji_0039-hdr-pano

Niewiele dalej na północ, przy moście Gdańskim zrobiłem kilka ujęć Warszawy w nocy:

dji_0005dji_0021dji_0049

Jeden dzień był wyjątkowo pochmurny, ale okazało się, że całkiem blisko świeci słońce:

dji_0195-hdrdji_0219-hdrdji_0226-hdr

Z lotu w chmury mam również film:

Jeżeli podobają się Wam moje zdjęcia i filmy to obserwujcie mnie na Instagramie (https://www.instagram.com/m.polkowski/) i subskrybujcie na YouTube (https://www.youtube.com/channel/UC0rcoI-FVLZjhIgTgfQpl9Q). Zapraszam!

| Komentarze

GMT – piękne mapy w kilku krokach

GMT (Generic Mapping Toolbox) to zestaw narzędzi do pracy z danymi geograficznymi (i nie tylko) opracowany na uniwersytecie na Hawajach (o mało co nie przyjęli mnie tam do pracy nad tym projektem… ehhh…), o którym mało kto pewnie słyszał. Podstawowym zastosowaniem GMT jest tworzenie różnego rodzaju map. Na stronie domowej projektu opisana jest instalacja (Windows, Mac OS X, Linux) oraz udostępniona jest obszerna dokumentacja, więc nie będę tych rzeczy tutaj powtarzał. Chciałem Was zachęcić kilkoma prostymi przykładami do zapoznania się z tym pakietem. Uwaga: to nie jest pełny tutorial, to tylko zachęta!

Przykład 1: Mapa bazowa Europy. GMT jest oczywiście pakietem bez interfejsu graficznego, więc wszystko odbywa się z wiersza poleceń:

gmt psbasemap -R-15/35/30/72 -Jl9/11/45/70/1:40000000 -B5g2:."Europa": -K -P -Y10 > Europa.ps
gmt pscoast -R -Di -Ia/0.03p,black -J -N1/0.5p,- -G#dde6d5 -S#a5bfdd -A0/0/4 -W0.5p,black -O -P >> Europa.ps
convert -geometry 2048x2048 -density 300 -trim Europa.ps Europa.png


Pierwszą komendą tworzymy mapę bazową o podanym wymiarze (-R), w projekcji azymutalnej równopowierzchniowej Lamberta (-Jl). GMT wynik (w postaci języka post script) wypisuje na standardowe wyjście. Drugą komendą rysujemy na mapie linię brzegową i granice państw. Opcja -D odpowiada za dokładność granic, -I za rysowanie rzek, -G i -S za kolory morza i lądów itd. (wszystko dokładnie opisane w dokumentacji). Trzecią komendą konwertujemy ps na png. Oto wynik:

europa

Przykład 2: Mapa bazowa Europy z naniesionymi punktami. Sama mapa bazowa jest ładna, ale mało użyteczna. Często chcemy na mapie pokazać jakieś lokalizacje. Na przykład lotniska. Ze strony http://openflights.org/data.html#airport pobrałem plik z listą lotnisk na świecie i przygotowałem mapę:

awk -F, '{print $8 "\t" $7}' airports.dat > airports.txt
gmt psbasemap -R-15/35/30/72 -Jl9/11/45/70/1:40000000 -B5g2:."Airports in Europe": -K -P -Y10 > Europa_air.ps
gmt pscoast -R -Di -J -N1/0.5p,- -G#dde6d5 -S#a5bfdd -A0/0/1 -W0.5p,black -O -P -K >> Europa_air.ps
gmt psxy airports.txt -Jl -O -R -Sc0.1c -W -G255/0/0 -K >> Europa_air.ps
convert -geometry 2048x2048 -density 300 -trim Europa_air.ps Europa_air.png


W pierwszej linii konwertują plik z danymi lotnisk na listę współrzędnych geograficznych. Drugą i trzecią linię już znamy. W czwartej linii rysuję na mapie czerwone kółeczka w każdej z zapisanych lokalizacji. Oto wynik:

europa_air

Przykład 3: Mapa topograficzna Polski. Jako przykład prezentacji rozkładu przestrzennego zmiennej wybrałem wysokość terenu nad poziomem morza. Miałem przygotowany wcześniej plik tekstowy zawierający informacje o wysokości n.p.m.:

screenshot_42

Teraz wystarczy tylko przeliczyć te dane na siatkę geograficzną i nanieść na mapę:

gmt surface DEM.xyz -R13.8/24.5/48.7/55 -I0.02/0.01 -GDEM.grd -T0.5 -C0.01
gmt psbasemap -R13.8/24.5/48.7/55 -Jl19.20/19.30/52/60/1:5000000 -B2g2:."Polska - Mapa Topo": -K -P -Y10 > PL.ps
gmt makecpt -CDEM_PL_wiki.cpt -T-10/2500/1 > tmp.cpt
gmt psscale -D3.1i/-.5i/7.0i/0.5ih -Ctmp.cpt -B250::/:m: -O -K -P >> PL.ps
gmt grdimage -Bg DEM.grd -R -J -O -Q -K -nn+a -Ctmp.cpt >> PL.ps
gmt pscoast -R  -Ia -Df -J -N1/0.5p,- -S#a5bfdd -A0/0/4 -W0.25p,black -K -O -P -L23.7/49.1/54/100+u -T14.2/54.5/1.5:: >> PL.ps
convert -geometry 2048x2048 -density 300 -trim PL.ps PL.png

W pierwszej linii przeliczamy dane w punktach na powierzchnię w siatce geograficznej i zapisujemy do pliku grd. W drugiej linii tworzymy mapę bazową dla Polski. Trzecia linia to przygotowanie skali kolorów na podstawie wzorca (DEM_PL_wiki.cpt, dużo wzorców tutaj). Czwarta linia to dodanie do mapy skali kolorów. Piąta linia to naniesienie na mapę naszej powierzchni w kolorach zgodnych ze skalą. Szósta linia to nałożenie na wszystko granic i zamalowanie wody na niebiesko. Oto efekt:

pl

GMT ma duże możliwości, niestety kosztem łatwości obsługi. Ważną zaletą jest tworzenie map w postaci wektorowej. GMT polecałbym szczególnie w dwóch przypadkach: po pierwsze gdy potrzebujemy bardzo wysokiej jakości np. do publikacji i po drugie w przypadku, gdy chcemy proces automatyzować np. generując indywidualne mapy dla użytkowników itp.

Gdybyście mieli jakieś pytania, piszcie – używam GMT od 5 lat więc może będę mógł pomóc.

| Komentarze

Sprytne omijanie limitu zapytań z adresu IP

Dawno dawno temu podjąłem się parsowania danych z pewnej strony www, na której obowiązywał limit ilości zapytań z jednego adresu IP. Działało to mniej więcej tak, że po kilku zapytaniach dany adres IP był blokowany na kilka minut. Ponieważ do pobrania było bardzo dużo rekordów, filtr ten skutecznie mnie blokował. Zacząłem szukać rozwiązania i po kilku iteracjach doszedłem do prostego i relatywnie taniego sposobu.

Na rynku istnieje wielu dostawców usługi zwanej Hosting SEO (do pozycjonowania) – od zwykłego hostingu różni się możliwością wykorzystania wielu adresów IP w ramach jednego konta. Adresy IP są stosunkowo drogie (jeśli potrzebujemy kilkadziesiąt), ale w hostingu SEO ta sama pula adresów dostępna jest dla wielu kont klientów. Za konto z pulą 32 adresów IP zapłacimy rzędu 20-30 zł za miesiąc. Po wykupieniu usługi i zalogowaniu się do panelu admina powinniśmy mieć dostęp do listy “naszych” adresów ip.

Zanim przejdziemy do rozwiązania, zróbmy prosty test. Spróbujmy z poziomu serwera sprawdzić adres IP. Zrobimy to za pomocą prostego skryptu php:

<?php
	$ch = curl_init('http://whatismyip.org/');
	curl_setopt($ch,CURLOPT_RETURNTRANSFER,TRUE);
	$myIp = curl_exec($ch);
	preg_match_all('/\d{1,3}\.\d{1,3}\.\d{1,3}\.\d{1,3}/',$myIp, $out);
	print_r($out);
?>

Skrypt uruchamiamy przez przeglądarkę (tani serwer raczej nie oferuje dostępu przez ssh). Wynik powinien wyglądać mniej więcej tak:

Array
(
    [0] => Array
        (
            [0] => 212.59.244.5
        )

)

Adres IP, który się wyświetli jest najprawdopodobniej przypisany domyślnie do naszego konta. Możemy przez panel administratora go zmienić i spróbować ponownie. Niestety takie rozwiązanie nie pomoże nam w szybkim zmienianiu adresów. Okazuje się, że wystarczy przy wywoływaniu CURL dodać informację, z którego interfejsu sieciowego serwera chcemy skorzystać. Na liście dostępnych dla mojego konta adresów IP były 32 pozycje:

ip

Użyjmy pierwszego adresu z listy:

<?php
	$ch = curl_init('http://whatismyip.org/');
	curl_setopt($ch,CURLOPT_RETURNTRANSFER,TRUE);
	curl_setopt($ch,CURLOPT_INTERFACE,"31.6.69.41");
	$myIp = curl_exec($ch);
	preg_match_all('/\d{1,3}\.\d{1,3}\.\d{1,3}\.\d{1,3}/',$myIp, $out);
	print_r($out);
?>

Otrzymujemy wynik:

Array
(
    [0] => Array
        (
            [0] => 31.6.69.41
        )

)

Działa! Za pomocą CURL możemy zdziałać cuda. Wystarczy tylko dopisać logikę, która losowo będzie przy każdym zapytaniu zmieniała adresy IP.

Jeśli ktoś jest dociekliwy to może odkryć jeszcze jedną rzecz. Wykupując najtańsze konto (z najmniejszą liczbą adresów IP) będziemy działali prawdopodobnie na tej samej maszynie co właściciele droższych pakietów. Możemy więc korzystać z całej puli adresów IP przypisanych do tego serwera, nawet jeśli nie są dla nas dostępne w panelu. U mnie działały np. takie adresy spoza listy: 31.6.69.42, 31.6.69.43, 31.6.69.45, 31.6.69.47 (więcej nie próbowałem). Użycie adresu nie przypisanego do danej maszyny spowoduje zwrócenie pustego stringa – nasze dane nie wiedziały jak wrócić.

Trzeba pamiętać jeszcze o małej małych zasobach serwera dla takiego konta hostingowego – jeśli zaczniemy generować za duże obciążenie prędzej czy później odezwie się admin z pretensjami.

Może komuś z Was się takie coś kiedyś przyda.

| Komentarze

Reprezentacja czasu w komputerze

Czas jest jednym z podstawowych “parametrów” świata, który na co dzień wielokrotnie zapisujemy (zapamiętujemy) i przeliczamy. Obecnie oznacza to, że jest przetwarzany przez komputery. Mogło by się wydawać, że sprawa jest prosta, ale od razu widać całą masę kłopotów. Pomysł na ten wpis wynika z bezsensownej zmiany czasu na zimowy w minioną niedzielę.

Po pierwsze strefy czasowe. Dopóki znajdujemy się w jednej strefie czasowej wszystko jest ok, potrafimy bez problemu obliczyć różnicę czasu pomiędzy dwiema datami. Do czasu: mamy przecież w Polsce dwie strefy czasowe – letnią i zimową. Jeżeli interesuje nas dokładne obliczenie czasu to musimy te informacje uwzględniać. Rozwiązaniem tego problemu może być zapamiętywanie i obliczanie dat i czasów w UTC (Universal Time Coordinated). Wiedzę na temat aktualnej w danym momencie i miejscu strefie czasowej najlepiej pobierać z systemu operacyjnego, który powinien to “ogarniać”. Nie warto tego rozgryzać samemu, bo ilość wyjątków jest powalająca. W tym miejscu polecam film The Problem with Time & Timezones.

Do tej pory pamiętam kartkówkę z geografii w liceum na której liczyliśmy czas podróży samolotem z San Francisco to Tokio (i z powrotem) na podstawie godzin przylotów i odlotów. Jedynym rozwiązaniem gwarantującym dobry wynik było przejście do czasu UTC.

Po drugie format zapisu danych. Komputer operuje na liczbach a ludzie na ciągach znaków. Istnieje wiele formatów zapisu daty i czasu w formie ciągu znaków, ale to jest tylko reprezentacja “dla ludzi”. W pamięci data i czas mogą być zapisane na wiele sposobów, z których trzy są moim zdaniem najważniejsze:

  • Możemy pamiętać oddzielnie jako liczby całkowite rok, miesiąc, dzień, godzinę, minutę, sekundę i milisekundę (albo nanosekundę itp.) + dodatkowo kod strefy czasowej (zapisany np. w postaci liczby minut w stosunku do UTC). Taki sposób jest dokładny i uniwersalny, ale mało wydajny i pamięciożerny. Ktoś jeszcze pamięta problem roku 2000?
  • Drugim sposobem jest zapisywanie epoki unix, czyli ilości sekund od 01-01-1970. Tu problemy są dwa: stosując int32 mamy bardzo ograniczony zakres dat i dokładność na poziomie sekundy.
  • Trzecim sposobem, z którym spotykam się na co dzień jest zapisywanie liczby zmiennoprzecinkowej określającej dni od roku 0. Z tej metody korzysta Matlab. Zdecydowaną zaletą jest możliwość opisania dowolnej daty w historii i przyszłości wszechświata oraz możliwość uwzględniania dokładności sub-sekundowej. Wada tego zapisu wynika ze zmiennej dokładności zapisu zmiennoprzecinkowego w zależności od wartości – pisałem o tym kilka tygodni temu.

Zdecydowanie trzeci sposób zapisu daty jest moim ulubionym – pozwala na bardzo szybkie operowanie na datach, bez utraty precyzji. Operacje na liczbach zmiennoprzecinkowych są całkowicie rutynowe, więc ciężko będzie znaleźć coś wydajniejszego.

Bardzo wiele zależy od języka programowania, w każdym jest inne podejście. Szczególnie w Pythonie widać ogrom komplikacji. Jakie są Wasze doświadczenia? Z którego formatu korzystacie najczęściej?

Jako bonus chciałbym Wam pokazać 3 animacje mojego autorstwa. Pierwsza jest dość przewidywalna bo pokazuje czas trwania dnia w zależności od dnia roku:

Dwie kolejne są już dużo ciekawsze, ponieważ pokazują czas wschodu i zachodu słońca w lokalnej strefie czasowej.

Widać wyraźnie zmianę czasu letniego na zimowy (w różnym czasie zależnie od regionu) i słabe dopasowanie strefy czasowej w niektórych regionach.

| Komentarze

Czy Python może być 876 razy szybszy?

Pythona zacząłem używać jakieś 5 lat temu. Na początku nie byłem przekonany, ale nie miałem wyboru. Z czasem się przekonałem i zrobiłem kilka projektów małych i dużych. Dodatkowo uczyłem podstaw programowania w pythonie przez 4 lata – do tej pory nie jestem przekonany czy jest to dobry język na początek (trochę za dużo wybacza), ale nie była to moja decyzja.

Wracając do tematu: python ma jedną poważną wadę – jest strasznie wolny. Dziś chcę wam pokazać na przykładzie, jak w prosty sposób można użyć funkcji napisanych w C/C++ do przeprowadzania obliczeń w programie w napisanym w pythonie. Python jest rewelacyjny jeśli chodzi o wczytywanie, zapisywanie i wizualizację danych, z kolei C/C++ jest bardzo wydajny. Połączenie wydaję się idealne i okazuje się całkiem proste.

Dla przykładu weźmy proste zadanie: generujemy listę N liczb losowych z zakresu od 0 do 1. Chcemy obliczyć wszystkie możliwe sumy 3 liczb z tej listy bez powtórzeń i policzyć ile z nich wynosi 1 z pewną ustaloną dokładnością. Oczywiście można ten problem optymalizować, ale dziś nie o tym. Chcemy porównać wydajność czystego pythona i pythona wspieranego przez C++.

W pierwszej kolejności napiszmy sobie funkcję w C++ (plik CALC.cpp):

#include "CALC.h"
#include 
#include 
#include 

void _CALC(double *DATA, int *RESULT, int N,  double treshold)
{
	printf("C++ start\n");

	RESULT[0] = 0;
	for (int a = 0; a < N; a++)
	{
		for (int b = a+1; b < N; b++)
		{
			for (int c = b+1; c < N; c++)
			{
				if (fabs(DATA[a] + DATA[b] + DATA[c] - 1) < treshold)
				{
					RESULT[0]++;
				}
			}
		}
	}

	printf("C++ finish\n");
}

W parze mamy plik nagłówkowy (CALC.h):

void _CALC(double *DATA, int *RESULT, int N, double treshold);

Powyższa funkcja robi dokładnie to co założyliśmy - zlicza ile kombinacji bez powtórzeń daje sumę 1 z dokładnością "treshold". Za chwilę powinno być jasne, czym są argumenty tej funkcji.

Naszym celem jest możliwość wywołania tej funkcji z poziomu pythona w taki sposób (program.py):

import numpy
import CALC
import time
start_time = time.time()

N = 1000
treshold = 1e-7

DATA = numpy.random.uniform(0, 1, size=N)
RESULT = numpy.zeros((1,), dtype=numpy.int)

start_time = time.time()
CALC.CALC(DATA, RESULT, N, treshold)
t1 = (time.time() - start_time)
print("C++:", RESULT[0], t1)


start_time = time.time()
count = 0;
for a in range(0,N):
	for b in range(a+1,N):
		for c in range(b+1,N):
			if abs(DATA[a]+DATA[b]+DATA[c]-1) < treshold:
				count =count + 1
t2 = (time.time() - start_time)
print("Python:", count, t2)

print("Speed:", t2/t1)

Dokładnie chodzi o linię

CALC.CALC(DATA, RESULT, N, treshold)

Potrzebujemy powiązania (interfejsu) pomiędzy pythonem i C++ (CALCmodule.cpp). Jest to kawałek kody, który z naszej funkcji C++ pozwala zrobić moduł dla pythona. Nie pisałem tego sam, złożyłem z kilku tutoriali. Najważniejsza jest funkcja CALC, gdzie definiujemy nasze zmienne i wywołujemy funkcję liczącą:

#include 
#define NPY_NO_DEPRECATED_API NPY_1_10_API_VERSION
#include 
#include "CALC.h"



struct module_state {
    PyObject *error;
};

#define GETSTATE(m) ((struct module_state*)PyModule_GetState(m))

static PyObject* CALC(PyObject* self, PyObject* args)
{
	PyArrayObject *data_obj;
	PyArrayObject *result_obj;
	double treshold;
	int N;

	if (!PyArg_ParseTuple(args, "OOid", &data_obj, &result_obj, &N, &treshold))
	{
		Py_INCREF(Py_None);
		return Py_None;
	}

	double *DATA = static_cast(PyArray_DATA(data_obj));
	int *RESULT = static_cast(PyArray_DATA(result_obj));

	_CALC(DATA, RESULT, N, treshold);

	Py_INCREF(Py_None);
	return Py_None;
}

static PyMethodDef CALCMethods[] = {
    {"CALC", CALC, METH_VARARGS, "..."},
    {NULL, NULL, 0, NULL}
};

static int CALC_traverse(PyObject *m, visitproc visit, void *arg) {
    Py_VISIT(GETSTATE(m)->error);
    return 0;
}

static int CALC_clear(PyObject *m) {
    Py_CLEAR(GETSTATE(m)->error);
    return 0;
}


static struct PyModuleDef moduledef = {
        PyModuleDef_HEAD_INIT,
        "CALC",
        NULL,
        sizeof(struct module_state),
        CALCMethods,
        NULL,
        CALC_traverse,
        CALC_clear,
        NULL
};

extern "C" PyObject * PyInit_CALC(void)
{
	PyObject *module = PyModule_Create(&moduledef);
	if (module == NULL)
        return NULL;
    struct module_state *st = GETSTATE(module);

    st->error = PyErr_NewException("CALC.Error", NULL, NULL);
    if (st->error == NULL) 
    {
        Py_DECREF(module);
        return NULL;
    }
	import_array();
	Py_INCREF(module);
    return module;

}

Na stronie https://docs.python.org/2/c-api/arg.html znajdują się dokładnie opisy typów danych które możemy przekazywać z pythona do C++ i z powrotem. W powyższym przykładzie "OOid" oznacza dwa obiekty, liczbę całkowitą i zmiennoprzecinkową (double). Obiektem może być lista, z której możemy czytać i do której pisać. Nazwa naszego modułu pojawia się w tym kodzie wielokrotnie - zmieniając trzeba pamiętać o wszystkich miejscach.

Ostatnim krokiem jest kompilacja modułu. Potrzebujemy skryptu do kompilacji (setup.py):

from distutils.core import setup, Extension
import numpy.distutils.misc_util
import os

os.environ["CC"] = "g++"
os.environ["CXX"] = "g++"

module1 = Extension('CALC', sources = ['CALCmodule.cpp', 'CALC.cpp'])

setup (name = 'CALC',
       version = '1.0',
       description = 'Package for calculating number sums',
       ext_modules = [module1],
	   include_dirs=numpy.distutils.misc_util.get_numpy_include_dirs())

Teraz możemy kompilować i uruchamiać:

screenshot_35

Funkcja w C++ potrzebowała 0.12 sekundy na policzenie, że jest 19 trójek, które z dokładnością 0.0000001 dają sumę 1. Python potrzebował na analogiczne liczenie 108.42 sekund: 876 razy dłużej! Oczywiście można by ten kod zoptymalizować, ale porównujemy dwa identyczne rozwiązania. Różnica w czasie jest kolosalna. W mojej pracy często spotykam się z obliczeniami numerycznymi, dlatego w pierwszej kolejności przygotowuję prototyp w pythonie i fragment obliczeniowy przepisuję na C++.

Nie chcę wnikać w teorię budowania modułów dla pythona bo się na tym nie znam. Sam najlepiej uczę się na przykładach, więc mam nadzieję, że ten Wam się przyda.

Dajcie znać, czy kiedyś używaliście takich rozwiązań, albo czy przydadzą Wam się w przyszłości.

| Komentarze (2)

Wykład “Badania sejsmiczne Polski w 3D”

Jeszcze przed obroną doktoratu zostałem poproszony o wygłoszenie wykładu o tematyce mojej pracy doktorskiej w ramach studenckiego koła geofizyki na wydziale fizyki uniwersytetu warszawskiego.

Było to dla mnie ważne z dwóch powodów. Po pierwsze był to pierwszy wykład w ramach koła w tym roku akademickim, a po drugie było to moje pierwsze wystąpienie jako doktora. OK, nie czepiajmy się szczegółów, doktorem zostanę po uchwale rady wydziału, ale to tylko kwestia formalna.

Wszystkich zainteresowanych zapraszam do oglądania. Niestety kamera sportowa zawiodła mnie po raz kolejny – tym razem jasność nie pozwala na odczytanie niczego ze slajdów, więc znów dodałem je w montażu. Druga kamera również mnie zawiodła przerywając nagrywanie po 30 minutach. Mam nadzieję, że kiedyś nauczę się jak porządnie nagrywać.

| Komentarze

Jak w poniedziałek zostałem doktorem

W poniedziałek 17 października broniłem na Wydziale Fizyki Uniwersytetu Warszawskiego swoją pracę doktorską zatytułowaną „Lokalizacja ognisk trzęsień ziemi metodą propagacji wstecznej z wykorzystaniem implementacji metody fast marching w modelu 3D obszaru Polski”.

img_2278

Praca doktorska była podsumowaniem 4-letnich studiów doktoranckich, podczas których realizowałem cały temat. Oczywiście najważniejszym celem studiów doktoranckich jest zdobycie stopnia naukowego doktora, ale równie ważne jest wykorzystanie tego czasu na wyrabianie sobie “naukowej marki”. Dowodem wyników pracy w nauce są publikacje w czasopismach naukowych (recenzowanych czasopismach z tak zwanej listy filadelfijskiej). W 4 lata zostałem współautorem 8 takich publikacji.

Drugą połowę czwartego roku studiów doktoranckich poświęciłem na zebranie wszystkich zagadnień, nad którymi wcześniej pracowałem w spójną całość – 180 stron pracy doktorskiej. Moją pracę doktorską możecie pobrać z mojej prywatnej strony: http://marcinpolkowski.com/en/ (po prawej stronie w boksie “Education”).

Należy też zaznaczyć, że jednym z ważnych elementów studiów doktoranckich jest dydaktyka – ja uczyłem głównie programowania w pythonie i C++.

Samo przygotowanie dysertacji (wiki) to dopiero początek drogi do uzyskania stopnia doktora. Trzeba otworzyć przewód doktorski, powołać komisje na dwa (lub trzy jak ktoś nie ma certyfikatu z angielskiego) egzaminy, wyznaczyć dwóch recenzentów i powołać komisję, która przyjmie obronę pracy. Każdy z tych elementów przechodzi przez Radę Wydziału. Gotowa praca trafia najpierw do recenzentów, którzy ją opiniują i dopuszczają do dalszego postępowania – mają na to dwa miesiące (recenzje mojej pracy: recenzja prof. Pietsch, recenzja prof. Guterch). Po otrzymaniu recenzji komisja ds. obrony sprawdza wszystkie dokumenty i wyznacza termin obrony. Moja obrona miała miejsce 17 października 2016.

W celach głównie pamiątkowych postanowiłem dyskretnie zarejestrować całe wydarzenie. Małą kamerę sportową schowałem w piórniku koło komputera, żeby nikogo nie kuła w oczy. Całoś trwała równo dwie godziny. Myślę, że możecie być ciekawi jak taka obrona wygląda (moja prezentacja startuje około 8-9 minuty):

Gdybyście mieli pytania o studia doktorancie, proces uzyskiwania stopnia czy samą moją pracę to chętnie będę odpowiadał – komentujcie poniżej!

Nie zapomnijcie subskrybować mojego kanału na YouTube:

| Komentarze (3)

Czego nie wiemy o liczbach zmiennoprzecinkowych

Przez ostatnie 4 lata prowadziłem na Wydziale Fizyki ćwiczenie do kilku kursów programowania w pythonie i c++. Kilka razy spotkałem się z pytaniem o liczby zmiennoprzecinkowe. Poruszamy na zajęciach kwestię zapisu binarnego liczb całkowitych i wtedy pojawia się pytanie o liczby rzeczywiste. Do tej pory odpowiadałem bardzo skrótowo, że “jest to skomplakowne”, bardzo sprytne, ale nie pozbawione wad. W przypadku liczb całkowitych sprawa jest prosta. W danej ilości bitów możemy przechować dany zakres liczb całkowitych. Z liczbami zmiennoprzecinkowymi problem polega na tym, że w każdym przedziale jest ich nieskończenie wiele, a my mamy tylko 32 albo 64 bity. Więc jak to właściwie jest? O samej formie zapisu można oczywiście przeczytać wszystko w Wikipedii – ja chcę zrobić eksperyment. Na pierwszy ogień liczby typu float, czyli 32 bitowe (1 bit na znak, 8 bitów na wykładnik i 23 na mantysę). 32 bity daje jakieś 4 294 967 296 kombinacji – to na tyle mało, że mogę sprawdzić wszystkie. W ramach testu sprawdzam ile liczb mieści się w 4 przedziałach: 0-1, 1-2, 1000-1001 i 1000000-1000001:

int main()
{
	float f;
	uint i;	 
	std::vector range = {0, 1, 1000, 1000000};
	std::vector count = {0, 0, 0, 0};
	for(i = 0; i=range[a] && f < range[a]+1)
				count[a]++;
		}
	}
	for(int a = 0; a < range.size(); a++)
	{
		std::cout << range[a] << "-" << range[a]+1 << ":\t" << count[a] << std::endl;
	}
}

Wynik mamy po niecałych 2 minutach. Policzone ilości liczb są bardzo ciekawe:

screenshot_33

Od razu widać kilka zależności. W zakresie od 1 do 2 jest dokładnie 2^23 liczb - tak jakby były to wszystkie "mantysy" dla jednego wykładnika. W zakresie od 0 do 1 jest dokładnie 2^23*(2^7-1)-1 - czyli wszystkie mantysy dla połowy wykładników (bez jednego). Im większa liczba tym mniejsza dokładność - mamy do dyspozycji 2^31 a musimy móc pokazać zarówno bardzo małe liczby i te gigantyczne.

Z liczbami w pojedynczej precyzji sprawa była prosta - udało się sprawdzić wszystkie kombinacje w niecałe 2 minuty. Przy podwójnej precyzji mamy 64 bity, więc sprawdzenie wszystkich zajęłoby 16000 lat. Szkoda czasu. Możemy natomiast pobawić się takim kodem:

int main()
{
	union
	{
		uint64_t input;
		uint64_t   output;
	} data;

	uint64_t x = 5;
	data.input = x;
	std::bitset   bits(data.output);

	for(uint64_t a = 0; a<=2048; a++)
	{
		for(uint64_t b = 0; b<=pow(2,52)-1; b+=pow(2,52)-1)
		{
			x = b+(a<<52);
			data.input = x;
			bits = data.output;
			double f;
			memcpy(&f, &x, sizeof(f));
			std::cout << std::setw(4)<< a<< '\t'<< std::setw(16)<<  b << '\t'<< std::setw(12) << f << '\t' << bits  << std::endl;
		}
		std::cout << std::endl;
	}
}

Powyższy kod wypisze zakres liczb dla każdego z 2^11 wykładników. Mantysa ma 52 bity (~4.5*10^15), więc od 1 do 2 mamy właśnie 2^52 liczb, Tyle samo od 2 do 4, 4 do 8 itd:

screenshot_34

Na powyższym przykładzie pierwsza kolumna to wykładnik, druga to mantysa, trzecia to wartość liczby, a czwarta to reprezentacja binarna.

Nie chcę tutaj wnikać w szczegóły samego formatu. Zależy mi na pokazaniu specyfiki takiego pamiętania liczb. Możecie modyfikować i uruchamiać powyższe kody, a dowiecie się więcej o liczbach zmiennoprzecinkowych. Dodatkowo powyższe przykłady powinny dobrze obrazować kolosalną różnicę pomiędzy pojedynczą i podwójną precyzją.

Musimy pamiętać, że operując na bardzo dużych liczbach, gdzie dokładność zapisu zmiennoprzecinkowego jest mała, możemy wprowadzać błędy numeryczne - w szczególności gdy łączymy wielkie i małe liczby.

Kto dowiedział się czegoś nowego klika łapkę w górę!

| Komentarze

Karta dźwiękowa jako przetwornik A/D dla sejsmografu

Dostałem dziś mailem pytanie dotyczące wcześniejszych wpisów dotyczących budowy prostego czujnika sejsmicznego (Sejsmograf domowej roboty – pierwsza przymiarka oraz Sejsmograf domowej roboty – krok drugi):

Dzień dobry,

Jestem studentem geofizyki na AGH i instruktorem harcerskim w ZHP. Przygotowuję zajęcia dla młodzieży popularyzujące sejsmologię. Chcieliśmy na nich zbudować sejsmograf według Pańskiego pomysłu, jednak jedna rzecz jest dla mnie niejasna – jak dokładnie należy podłączyć cewkę do karty dźwiękowej w komputerze? Niestety, nie znalazłem odpowiedzi na to pytanie w artykule. Będę bardzo wdzięczy za odpowiedź.

Z wyrazami szacunku,
Marek Ziobro

Każdy taki mail jest dla mnie bardzo ważny, bo oznacza, że treść, którą tworzę jest wartościowa. Dziś postanowiłem odpowiedzieć publicznie na blogu – myślę, że odpowiedź może się komuś jeszcze przydać.

Cewka zastosowana w sejsmometrze to zwykły zwój drutu mający dwa końce. W wyniku zmiany pola magnetycznego spowodowanej ruchem magnesu w cewce indukuje się napięcie, czyli różnica potencjału pomiędzy obydwoma końcami drutu. Wartość tego napięcia jest proporcjonalna do tego, jak szybko zmienia się pole magnetyczne – im szybciej rusza się magnes tym większe napięcie. Do pomiaru stałego napięcia można oczywiście użyć multimetru, natomiast w naszym przypadku zależy nam na pomiarze zmian napięcia w czasie. Pomiaru napięcia w funkcji czasu możemy dokonać za pomocą oscyloskopu. W przypadku, gdy nie mamy pod ręką oscyloskopu można ratować się kartą dźwiękową komputera z wejściem mikrofonowym. Sygnał z mikrofonu jest napięciem zmiennym w czasie dokładnie tak jak w przypadku czujnika sejsmicznego. Niektóre karty dźwiękowe w komputerach stacjonarnych mają również wejścia zwane line-in, które działają bardzo podobnie.

Oczywiście karta dźwiękowa nie będzie doskonałym oscyloskopem (i tym bardziej rejestratorem sejsmicznym) ponieważ:

  1. Ma ograniczony zakres napięć wejściowych – to bardzo ważne, bo przekroczenie maksymalnego dopuszczalnego napięcia może kartę uszkodzić. Dokładne wartości należy sprawdzić w dokumentacji danego modelu karty.
  2. Pracuje w domyślnym dla dźwięku próbowaniu (44.1, 48kHz) jest to zdecydowanie za dużo, ale lepiej za dużo niż za mało.
  3. Ma spore szumy, co jest istotne przy rejestracji słabych sygnałów.
  4. Ma zazwyczaj niską rodzielczość.

Do samego podłączenia będziemy potrzebowali wtyk jack 3.5mm (mono lub stereo). Do masy podpinamy jeden koniec drutu cewki, a do plusa (w przypadku wtyku stereo do kanału L lub P) drugi. Zamiany miejscami kabli od cewki będzie miała wpływ na kierunek pomiaru: dodatnie napięcie przy ruch w górę lub w dół – na początek zabawy nie ma to żadnego znaczenia, przy głębszej interpretacji warto to wiedzieć i kontrolować. Czasami łatwiej będzie kupić kabel zakończony złączem jack (np. przedłużacz do słuchawek, lub kabel do podłączania odtwarzacza do radia), przeciąć i połączyć kabelki. W przypadku kabla stereo trzeba uważać, żeby nie połączyć cewki do kanałów L i P, bo wtedy nie zadziała – jeden koniec musi być do masy. Ja stosowałem właśnie taki przerobiony kabel:

Na komputrze można użyć dowolnego oprogramowania do rejestracji dźwięku lub specjalnego programu udającego oscyloskop: Zelscope lub Soundcard Oscilloscope. Drugi z nich widać na moich starych zdjęciach (to zdjęcie jest 2006, dlatego w warsztacie miałem monitor CRT):

Pozdrawiam i jak zawsze czekam na Wasze maile!

Zapraszam w środę o 20 na nowy wpis – w tym tygodniu będzie o liczbach zmiennoprzecinkowych.

| Komentarze

Starsze wpisy »