wow, jestem pod dużym wrażeniem :) pisałeś to w takiej formie czy obfuskowałeś na koniec?
Muszę przyznać że spodziewałem się że pojawi się choć jedno podobne rozwiązanie i obstawiałem na pythona, ale myślałem że ogółem zaproponowane rozwiązania będą wyglądać... trochę inaczej ;)
Chętnie podałbym cały tok rozwiązywania/zmieniania zadania, ale niestety - został w pracy (No co, piątek. Niektórzy przeglądają kwejka, ja pół godziny pisałem kółko i krzyżyk). W sumie zrobiłem też czysto funkcyjne rozwiązanie dla @shaloma, ale zapomniałem wrzucić.
wow, jestem pod dużym wrażeniem :) pisałeś to w takiej formie czy obfuskowałeś na koniec?
Muszę przyznać że spodziewałem się że pojawi się choć jedno podobne rozwiązanie i obstawiałem na pythona, ale myślałem że ogółem zaproponowane rozwiązania będą wyglądać... trochę inaczej ;)
Jeszcze bonusowa wersja dla @shaloma - same funkcje, żadnych mutowalnych zmiennych:
def beta(alpha):
return (((((((((((((((((delta(alpha,0,0)*256+32)*256+delta(alpha,1,0))*256+32)*256+delta(alpha,
2,0))*256+10)*256+delta(alpha,0,1))*256+32)*256+delta(alpha,1,1))*256+32)*256+delta(alpha,2,1))*
256+10)*256+delta(alpha,0,2))*256+32)*256+delta(alpha,1,2))*256+32)*256+delta(alpha,2,2))*256+10)+0
def gamma(a,b,c): return (1-iota(a-b))*(1-iota(b-c))
def delta(alpha,x,y): return theta(epsilon(alpha,x,y))
def epsilon(alpha,x,y): return (alpha/(10**(x*3+y)))%10
def zeta(alpha, x, y, v): return (alpha-epsilon(alpha,x,y)*(10**(x*3+y)))+v*(10**(x*3+y))
def theta(x): return -12*x*x+45*x+46
def iota(x): return ((x>0)-(x<0))*((x>0)-(x<0))
def xi(x, a, b): return x*a+(1-x)*b
def xx(omega,alpha,nxt,rho):
ox(xi(omega,0,alpha), xi(omega,1,nxt), xi(omega,xi(omega,rho*79228162514264337593543950336+
(563906476998359738053408*256*256+theta(omega)*256+10),rho)*22300745198530623141535718272648361505980416+
xi(omega,beta(xi(omega,0,alpha)),beta(xi(omega,0,alpha))),xi(omega,rho*79228162514264337593543950336+
(563906476998359738053408*256*256+theta(omega)*256+10),rho)))
def xo(x, alpha, nxt, rho):
xx(iota(xi(gamma(epsilon(alpha,0,2),epsilon(alpha,1,1),epsilon(alpha,2,0)),epsilon(
alpha,1,1),xi(gamma(epsilon(alpha,0,0),epsilon(alpha,1,1),epsilon(alpha,2,2)),
epsilon(alpha,1,1),xi(gamma(epsilon(alpha,2,0),epsilon(alpha,2,1),epsilon(alpha,2,2)
),epsilon(alpha,2,0),xi(gamma(epsilon(alpha,1,0),epsilon(alpha,1,1),epsilon(alpha,1,
2)),epsilon(alpha,1,0),xi(gamma(epsilon(alpha,0,0),epsilon(alpha,0,1),epsilon(alpha,
0,2)),epsilon(alpha,0,0),xi(gamma(epsilon(alpha,0,2),epsilon(alpha,1,2),epsilon(
alpha,2,2)),epsilon(alpha,0,2),xi(gamma(epsilon(alpha,0,1),epsilon(alpha,1,1),epsilon
(alpha,2,1)),epsilon(alpha,0,1),xi(gamma(epsilon(alpha,0,0),epsilon(alpha,1,0),
epsilon(alpha,2,0)),epsilon(alpha,0,0),0))))))))),alpha,nxt,rho)
def ox(alpha, nxt, rho):
print format(rho,'x').decode('hex')
x=input()
xo(x, xi(iota(epsilon(alpha,x[0],x[1])),alpha,zeta(alpha,x[0],x[1],xi(iota(epsilon(alpha,
x[0],x[1])),nxt,(nxt+1)%2)+1)), xi(iota(epsilon(alpha,x[0],x[1])),nxt,(nxt+1)%2),
xi(iota(epsilon(alpha,x[0],x[1])),7597139782223356938,0)*22300745198530623141535718272648361505980416
+beta(xi(iota(epsilon(alpha,x[0],x[1])),alpha,zeta(alpha,x[0],x[1],xi(iota(epsilon(alpha,x[0],x[1]))
,nxt,(nxt+1)%2)+1))))
ox(0, 1, beta(0))
A odnośnie tego jak to pisałem - miałem gdzieś zapisywane krok po kroku transformacje (właśnie jakby trzeba było się pochwalić "jak to było zrobione", ale niestety nie na tym komputerze, więc postaram się odtworzyć.
Ogólnie cały kod "oblicza" wyjście jako liczbę, a następnie wypisuje ją jako napis.
- Zacząłem od napisania klasycznego kółka i krzyżyka.
1.5) Zmieniłem reprezentacje planszy tak, żeby '0' oznaczało puste pole, '1' oznaczało kółko, a '2' oznaczało krzyżyk - taka liczbowa reprezentacja okazała się najlepsza.
- Przepisałem wszystkie printy w ten sposób, żeby został tylko jeden print na końcu. Czyli zamiast:
print 'a'
...
print 'b'
zrobiło się
to_print = 'a'
...
to_print = to_print + 'b'
- pierwsza trudniejsza część - przepisałem wszystkie ify itp na wyrażenia warunkowe. Czyli zamiast:
winner = get_winner(board)
if winner != 0:
to_print = to_print + 'winner is ' + get_symbol(winner)
board = [[0,0,0],[0,0,0],[0,0,0]
next_player = 1
robi się:
winner = get_winner(board)
to_print = to_print + 'winner is ' + get_symbol(winner) if winner != 0 else to_print
board = [[0,0,0],[0,0,0],[0,0,0] if winner != 0 else board
next_player = 1 if winner != 0 else next_player
etc
Jest problem, bo używamy napisów oraz list. Niezdyt dobrze się one komponują z operacjami matematycznymi, a takich zamierzamy używać (for fun and profit). Więc zaczynamy od zmiany napisów na liczby - np. zamiast
print' 'winner_is '
byłoby
print format(563906476998359738053408, 'x').decode('hex')
Ale w praktyce nie wypisywałem nigdzie stringów a je łączyłem (jak w punkcie 2 napisane), więc trzeba było wymyśleć sposób na połączenie dwóch "liczbowych" napisów. To tak naprawdę dość prostę - jeśli mamy liczby reprezentujące napisy "A" i "B", to żeby uzyskać napis "AB" musimy obliczyć A * 256^(długość_napisu_b) + B.
Pozamieniałem w ten sposób wszystkie literały napisowe (wszystkie napisy mają stałą długość na szczęście) w kodzie.
- Drugi problem, plansza jest listą. Ale jako że ta lista może przechowywac tylko liczby 0-2, możemy przechowywać cały stan planszy w jednej wielkiej liczbie. Np. weźmy planszę (1-kółko, 2-krzyżyk):
102
201
101
Możemy ją potraktować jako liczbę dziesiętną (albo trójkową, albo szesnastkową, albo dziewiątkową) równą 102201101. Wtedy zamiast
x = board[0][1]
board[1][2] = 2
Trzeba pisać:
x = get(board, 0, 1)
board = set(board, 1, 2, 2)
Gdzie:
# epsilon = get
def epsilon(alpha,x,y): return (alpha/(10**(x*3+y)))%10
# zeta = set
def zeta(alpha, x, y, v): return (alpha-epsilon(alpha,x,y)*(10**(x*3+y)))+v*(10**(x*3+y))
Ale warto, bo teraz w kodzie operujemy na stamych liczbach.
- Skoro już mamy same liczby, to wypada zacząć redukować ify (bo na razie je tylko przesywaliśmy z miejsca w miejsce).
Po pierwsze - mały "matematyczny" hack na ifa (ale to nie jest żaden if oczywiście, tylko prosta funkcja liniowa):
# xi == if
def xi(x, a, b): return x*a+(1-x)*b
# xi(0, a, b) === b
# xi(1, a, b) === a
Niestety nie działa to tak jak chcemy jeśli x jest liczbą spoza zbioru {0, 1} - ale można zrobić funkcję "to_bool" która zamienia dowolną liczbę nierówną 0 na 1, a 0 zostawia w spokoju.
Jedną z prostych definicji takiej funkcji jest:
def to_bool(x):
return sgn(x)*sgn(x) # sgn(x)**2, wartość bezwzględna znaku liczby
# gdzie sgn to
def sgn(x):
return (x>0)-(x<0)
W podanym kodzie:
def iota(x): return ((x>0)-(x<0))*((x>0)-(x<0))
Przy okazji, negacja boola 'x' to oczywiście 1-x.
A sprawdzenie równości liczb x i y, zamiast używać operatora ==, można zrealizować jako 1-to_bool(x - y). (Wiem, w pythonie wystarczy x == y, bo boole można traktować jak liczby. Powiedzmy że miałem zaćmienie i niepotrzebnie skomplikowałem kod.)
- skoro mamy już takiego pseudo-ifa, czas go wykorzystać. Weźmy poprzedni kod:
winner = get_winner(board)
to_print = XYZ if winner != 0 else to_print
board = UVW if winner != 0 else board
next_player = 1 if winner != 0 else next_player
Możemy przepisać to na:
winner = to_bool(get_winner(board))
to_print = xi(winner, XYZ, to_print)
board = xi(winner, UVW, board)
next_player = xi(winner, 1, next_player)
No i to w sumie wszystko, jedne rzeczy bylo prościej podmienić inne trudniej. Z ciekawostek, była taka funkcja:
def getsymbol(x):
if x == 0:
return ord('.') # ord, bo wszędzie w ostatecznej wersji korzystamy z liczb
elif x == 1:
return ord('O')
elif x == 2:
return ord('X')
I trzeba było usunąć z niej ify. Najpierw, co dokładnie zwracamy:
>>> ord('.')
46
>>> ord('O')
79
>>> ord('X')
88
Więc chcemy funkcję spełniającą własność:
f(0) = 46
f(1) = 79
f(2) = 88
Najprościej wykorzystać wielomian axx + b*x + c:
a*0*0 + b*0 + c = 46
a*1*1 + b*1 + c = 79
a*2*2 + b*2 + c = 88
Kilkanaście lat edukacji nie poszło na marne, i szybko znajdujemy współczynniki:
def theta(x):
return -12*x*x+45*x+46
(@niezdecydowany - i widzisz jaka matematyka jest przydatna w życiu)
edit:
Druga sprawa:
mov is Turing-complete
Poszukałem w guglu, G podał mi https://www.cl.cam.ac.uk/~sd601/papers/mov.pdf a tam jest takie stwierdzenie:
To prawda, podzbiór pythona który wykorzystałem (brak żadnych operacji warunkowych) nie jest kompletny w sensie maszyny turinga.
Na pewno ma co najmniej moc maszyny turinga liniowo ograniczonej, ale być może jest troche silniejszy (musiałbym dokładniej przeanalizować).
edit2: post pisany podczas jazdy trzęsącym się busem, więc wszelkie literówki/błedy niezamierzone.