## danklang (re, 100p)
> if you see this task while scroling>> you have been visited by the reversing task of the 9447 ctf> good flags and points will come to you>> but only if you submit '9447{`dankcode main.dc`}' to this task. >> [main.dc](main.dc)
###PL[ENG](#eng-version)
Przepełnione memami zadanie (co widać nawet po wstępie).
Dostajemy [długi kod w nieistniejącym języku](main.dc).
Ciężko go czytać, więc zaczynamy od przepisania go literalnie do pythona: [main1.py](main1.py).
Widać że jest niesamowicie nieoptymalny - więc po prostu uruchomienie kodu main1.py prawdopodobnienie skończyłoby się za naszego życia (a na pewno nie w trakcie trwania CTFa)
Rozpoczynamy rozpoznawanie funkcji które można zoptymalizować:
Na przykład to nic innego niż fibonacci(memes) % 987654321
```pythondef brotherman(memes):    hues = 0    if memes != 0:        if memes < 3:            return 1        else:            wew = brotherman(memes - 1)            hues = wew            wew = brotherman(memes - 2)            hues += wew    return hues % 987654321```
Jako że maksymalna wartość memes nie jest olbrzymia, możemy po prostu obliczyć wcześniej wszystkie wartości (precomputing):
```pythondef precompute_fibonacci_mod_987654321():    table = []    N = 13379447+1    result = [0] * N    result[1] = 1    for i in xrange(2, N):        result[i] = (result[i-2] + result[i-1]) % 987654321    return result
precomputed_fibonacci = precompute_fibonacci_mod_987654321()
def fibonacci_mod_987654321(number):    return precomputed_fibonacci[number]```
Za to tutaj rozpoznajemy funkcję sprawdzającą czy liczba jest pierwsza:```pythondef fail(memes, calcium):    dank = True    if calcium < memes:        if memes % calcium == 0:            dank = False        else:            wew = fail(memes, calcium + 1)            dank = wew    return dank```
I przepisujemy ją do takiej postaci:
```pythondef is_prime(number):    if number % 2 == 0:        return False    else:        for divisor in range(3, int(sqrt(number)) + 1, 2):            if number % divisor == 0:                return False    return True```
Dochodzimy do takiego stanu: [main2.py](main2.py)
W tym momencie kończą się oczywiste pomysły na optymalizację, a wykonanie dalej jest bardzo powolne. Decydujemy się więcna więcej precomputingu, i obliczać z góry wszystko co się da.
Przepisujemy więc sprawdzanie pierwszych:
```pythondef precompute_primes():    limit = 13379447 + 1    a = [True] * limit    for i in xrange(2, len(a)):        isprime = a[i]        if isprime:            for n in xrange(i*i, limit, i):                a[n] = False    return a
primes = precompute_primes()
def is_prime(number):    return primes[number]```
funkcję dootdoot (nie rozpoznaliśmy jej, a wygląda na jakąś znaną funkcję z prostym wzorem matematycznym):
```pythondef dootdoot(memes, seals):    if seals <= memes:        if seals == 0:            return 1        else:            if seals == memes:                return 1            else:                return dootdoot(memes - 1, seals - 1) + dootdoot(memes - 1, seals)```
Na taką formę:
```pythondef precompute_dootdoot():    table = []    MAXH, MAXW = 6, 13379447+1    for i in range(MAXH):        table.append([0] * MAXW)    for i in range(0, MAXH):        for j in xrange(0, MAXW):            if i > j:                table[i][j] = 0            elif i == 0:                table[i][j] = 1            elif i == j:                table[i][j] = 1            else:                table[i][j] = table[i][j-1] + table[i-1][j-1]    return table
dootdoot_table = precompute_dootdoot()def dootdoot(memes, seals):    return dootdoot_table[seals][memes] ```
Na końcu trzy powiązane funkcje - such, epicfail i bills:
```pythondef epicfail(memes):    if memes > 1:        if dank(memes, 2):            return 1 + bill(memes - 1)        else:            return such(memes - 1)    return 0
def such(memes):    wow = dootdoot(memes, 5)    if wow % 7 == 0:        wew = bill(memes - 1)        wow += 1    else:        wew = epicfail(memes - 1)    wow += wew    return wow
def bill(memes):    wow = fibonacci_mod_987654321(memes)    if wow % 3 == 0:        wew = such(memes - 1)        wow += 1    else:        wew = epicfail(memes - 1)    wow += wew    return wow```
Do takiej postaci:
```pythondef bill(memes):    wow = fibonacci_mod_987654321(memes)    if wow % 3 == 0:        wew = suchs[memes - 1]        wow += 1    else:        wew = epicfails[memes - 1]    wow += wew    return wow
def such(memes):    wow = dootdoot(memes, 5)    if wow % 7 == 0:        wew = bills[memes - 1]        wow += 1    else:        wew = epicfails[memes - 1]    wow += wew    return wow
def epicfail(i):    if i > 1:        if is_prime(i):            return 1 + bill(i - 1)        else:            return such(i - 1)    return 0
epicfails = [0] * (13379447 + 1)suchs = [0] * (13379447 + 1)bills = [0] * (13379447 + 1)
def upcompute_epicfails():    for i in xrange(1, 13379447+1):        if i % 10000 == 0:            print i        epicfails[i] = epicfail(i)        suchs[i] = such(i)        bills[i] = bill(i)
upcompute_epicfails()```
W tym momencie rozwiązanie zadania staje sie trywialne - skoro mamy już wszystkie wartości wyliczone, starczy pobrać wynik z tablicy:
```pythondef me():    memes = 13379447    wew = epicfails[memes]    print(wew)```
Przepisywanie tego zajęło dość dużo czasu, ale ostatecznie doszliśmy do takiej formy jak [main3.py](main3.py).Uruchomiony kod wykonywał się dość długo, ale ostatecznie dostaliśmy wynik: `2992959519895850201020616334426464120987`
Po dodaniu stałych części:
    9447{2992959519895850201020616334426464120987}
Zdobywamy punkty
### ENG version
Task full of memes (which you can see even from the task description).
We get a [long code in a made-up language](main.dc).
It's difficult to read so we rewrite it to python:  [main1.py](main1.py).
It is clear that it's not optimal and execution of main1.py would not finish before we die (and for sure not before CTF ends).
We start with trying to recognize some function we could optimize:
For example this function is fibonacci(memes) % 987654321:
```pythondef brotherman(memes):    hues = 0    if memes != 0:        if memes < 3:            return 1        else:            wew = brotherman(memes - 1)            hues = wew            wew = brotherman(memes - 2)            hues += wew    return hues % 987654321```
And since the memes variable is not so big, we can simply calculate all values before (precomputing):
```pythondef precompute_fibonacci_mod_987654321():    table = []    N = 13379447+1    result = [0] * N    result[1] = 1    for i in xrange(2, N):        result[i] = (result[i-2] + result[i-1]) % 987654321    return result
precomputed_fibonacci = precompute_fibonacci_mod_987654321()
def fibonacci_mod_987654321(number):    return precomputed_fibonacci[number]```
Here we recognize primarity test:
```pythondef fail(memes, calcium):    dank = True    if calcium < memes:        if memes % calcium == 0:            dank = False        else:            wew = fail(memes, calcium + 1)            dank = wew    return dank```
And change it for a faster one:
```pythondef is_prime(number):    if number % 2 == 0:        return False    else:        for divisor in range(3, int(sqrt(number)) + 1, 2):            if number % divisor == 0:                return False    return True```
We end up with a new version: [main2.py](main2.py)
At this point we run out of obvious ideas to optimize the code, and the execution time is still too long. We decide to do even more precomputing and just calculate all possible values.
We precompute primarity check:
```pythondef precompute_primes():    limit = 13379447 + 1    a = [True] * limit    for i in xrange(2, len(a)):        isprime = a[i]        if isprime:            for n in xrange(i*i, limit, i):                a[n] = False    return a
primes = precompute_primes()
def is_prime(number):    return primes[number]```
Function dootdoot (we didn't recognize it at the time, but it is just number of combinations):
```pythondef dootdoot(memes, seals):    if seals <= memes:        if seals == 0:            return 1        else:            if seals == memes:                return 1            else:                return dootdoot(memes - 1, seals - 1) + dootdoot(memes - 1, seals)```
We change into:
```pythondef precompute_dootdoot():    table = []    MAXH, MAXW = 6, 13379447+1    for i in range(MAXH):        table.append([0] * MAXW)    for i in range(0, MAXH):        for j in xrange(0, MAXW):            if i > j:                table[i][j] = 0            elif i == 0:                table[i][j] = 1            elif i == j:                table[i][j] = 1            else:                table[i][j] = table[i][j-1] + table[i-1][j-1]    return table
dootdoot_table = precompute_dootdoot()def dootdoot(memes, seals):    return dootdoot_table[seals][memes] ```
And finally three connected function - such, epicfail i bills:
```pythondef epicfail(memes):    if memes > 1:        if dank(memes, 2):            return 1 + bill(memes - 1)        else:            return such(memes - 1)    return 0
def such(memes):    wow = dootdoot(memes, 5)    if wow % 7 == 0:        wew = bill(memes - 1)        wow += 1    else:        wew = epicfail(memes - 1)    wow += wew    return wow
def bill(memes):    wow = fibonacci_mod_987654321(memes)    if wow % 3 == 0:        wew = such(memes - 1)        wow += 1    else:        wew = epicfail(memes - 1)    wow += wew    return wow```
Are changed into:
```pythondef bill(memes):    wow = fibonacci_mod_987654321(memes)    if wow % 3 == 0:        wew = suchs[memes - 1]        wow += 1    else:        wew = epicfails[memes - 1]    wow += wew    return wow
def such(memes):    wow = dootdoot(memes, 5)    if wow % 7 == 0:        wew = bills[memes - 1]        wow += 1    else:        wew = epicfails[memes - 1]    wow += wew    return wow
def epicfail(i):    if i > 1:        if is_prime(i):            return 1 + bill(i - 1)        else:            return such(i - 1)    return 0
epicfails = [0] * (13379447 + 1)suchs = [0] * (13379447 + 1)bills = [0] * (13379447 + 1)
def upcompute_epicfails():    for i in xrange(1, 13379447+1):        if i % 10000 == 0:            print i        epicfails[i] = epicfail(i)        suchs[i] = such(i)        bills[i] = bill(i)
upcompute_epicfails()```
And now solving the task is trivial - we have all values calculated so we simply need to read the result from the array:
```pythondef me():    memes = 13379447    wew = epicfails[memes]    print(wew)```
It took us a while to rewrite this but we finally got [main3.py](main3.py).The code was still running for quite a while but finally we got the result: `2992959519895850201020616334426464120987` which resulted in flag:
    9447{2992959519895850201020616334426464120987}