Nieczytelny , 2199 2145 2134 2104 2087 2084 bajtów
Obsługuje zarówno k/ jjak i ▲/▼ składnię.
Zgodnie z dobrą Nieczytelną tradycją program jest sformatowany czcionką proporcjonalną, aby zaciemnić różnicę między apostrofami a podwójnymi cudzysłowami:
„” „” „” „” „„ ”„ „” „„ ”„ ”„ ”„ ”„ „” „„ ”„ ”„ ”„ ”„ ”„ ”„ ” „” „” „” „” „” „” „„ ”„ ”„ ”„ ”„ „” „„ ”„ „” „” „” „” „” „” „” „” „” „” „” „” „” „” „„ ”„ ”„ ”„ ”„ „” „„ ”„ ”„ ”„ ”„ ”„ ”„ ”„” „„ ”„ ”„ „” „” „„ ”„ „” „” „” „” „„ ”„ „” „” „” „” „” „” „” „” „” „” „” „” „” „„ ”„ ”„ ”„ „” „„ ”„ „” „” „” „” „” „” „” „” „” „” „” „„ ”„ ”„ ”„ „” „” „” „” „„ ”„ ”„ ”„ ”„ ”„ ”„ ”„ ”„” „” „” „” „„ ”„ ”„ ”„ ”„ ”„ ”„ ”„ „” „„ ”„ ”„ ”„ ”„ ”„ ”„ ”„ ” „” „” „” „” „„ ”„ ”„ ”„ ”„ ”„ „” „” „” „„ ”„ ”„ ”„ ”„ ”„ ”„ ” „” „” „” „” „„ ”„ ”„ ”„ „” „” „” „” „„ ”„ „” „” „” „” „” „”„” „” „” „” „„ ”„ ”„ ”„ ”„ ”„ ”„ ”„ „” „„ ”„ ”„ ”„ „” „” „” „” „” „” „” „” „” „„ ”„ ”„ ”„ ”„ ”„ ”„ ”„ ”„ ”„ „” „” „” „” „” „” „” „” „” „” „” „„ ”„ ”„ ”„ ”„ ”„ ”„ ”„ „” „„ ”„ ”„ ”„ ”„ ”„ ”„” „” „” „” „” „” „” „” „” „” „” „„ ”„ „” „” „” „” „” „” „” „” „” „” „” „„ ”„ ”„ ”„ ”„ ”„ ”„ ”„ ”„ „” „„ ”„ ”„ ”„ ”„ ”„ ”„ ” „” „” „” „” „„ ”„ ”„ ”„ ”„ ”„ ”„ „” „„ ”„ „” „” „” „” „” „”„” „” „” „” „„ ”„ ”„ „” „„ ”„ ”„ ”„ „” „„ ”„ ”„ ”„ ”„ ”„ ”„ ” „” „” „” „” „” „„ ”„ ”„ ”„ ”„ ”„ ”„ „” „„ ”„ ”„ ”„ ”„ ”„ ”„ ” „” „” „” „” „„ ”„ ”„ ”„ „” „” „” „„ ”„ „” „„ ”„ ”„ ”„ ”„ ”„ ”„” „” „” „” „„ ”„ „” „” „” „” „” „„ ”„ „” „„ ”„ „” „” „” „” „” „” „” „” „„ ”„ ”„ ”„ ”„ ”„ ”„ „” „„ ”„ „” „” „” „” „” „” „” „” „” „” „” „„ ”„ ”„ „” „” „” „” „” „” „„ ”„ ”„ ”„ ”„ ”„ ”„ ”„” „” „” „” „” „” „„ ”„ ”„ ”„ ”„ ”„ „” „„ ”„ „” „” „” „” „” „” „” „” „” „„ ”„ ”„ „” „„ ”„ ”„ ”„ ”„ „” „„ ”„ „” „” „” „” „” „” „” „” „” „” „„ ”„ „” „” „” „” „„ ”„ „” „„ ”„ ”„ ”„ ”„ ”„ ”„ ”„” „” „” „” „„ ”„ ”„ „” „” „” „„ ”„ „” „„ ”„ ”„ ”„ ”„ ”„ ”„ ” „” „” „” „” „” „” „„ ”„ „” „” „” „” „„ ”„ „” „” „” „” „” „” „” „” „” „” „” „„ ”„ ”„ ”„ ”„ ”„ ”„ ”„ „” „„ ”„ „” „” „” „” „”„” „” „” „” „„ ”„ ”„ „” „” „” „„ ”„ „” „„ ”„ „” „„ ”„ ”„ ”„ ” „” „” „” „” „” „” „” „„ ”„ ”„ ”„ ”„ ”„ „” „” „” „” „” „” „” „” „” „” „” „” „” „” „” „„ ”„ ”„ ”„ ”„ „” „„ ”„ ”„ ”„ ”„ ”„ ”„” „” „” „” „” „” „„ ”„ ”„ ”„ ”„ ”„ ”„ „” „„ ”„ ”„ ”„ ”„ ”„ ”„ ” „” „” „” „” „„ ”„ ”„ ”„ ”„ ”„ ”„ ”„ „” „„ ”„ ”„ ”„ ”„ ”„ ”„ ”„ ” „” „” „” „” „„ ”„ „” „” „” „” „” „” „” „„ ”„ ”„ ”„ ”„ ”„ ”„” „” „” „” „” „” „„ ”„ „” „” „” „„ ”„ „” „” „” „” „” „” „” „” „” „” „” „” „” „” „„ ”„ ”„ ”„ „” „„ ”„ „” „„ ”„ „” „” „” „” „” „” „” „” „„ ”„ ”„ ”„ ”„ ”„ ”„ ”„ „” „„ ”„ ”„ ”„ „” „” „” „”„” „” „” „” „„ ”„ ”„ „” „” „” „„ ”„ ”„ „” „„ ”„ ”„ ”„ ”„ ”„ ”„ ” „” „” „” „” „„ ”„ ”„ „” „” „” „„ ”„ „” „„ ”„ ”„ ”„ ”„ ”„ ”„ ”„ ” „” „” „” „” „” „” „„ ”„ ”„ ”„ ”„ „” „„ ”„ „” „” „„ ”„ ”„ ”„ ”„” „” „” „” „” „” „” „„ ”„ ”„ ”„ „” „„ ”„ „” „„ ”„ ”„ ”„ ” „” „” „” „” „” „” „” „” „” „„ ”„ „” „„ ”„ „” „” „” „” „” „” „” „” „” „” „” „„ ”„ ”„ ”„ „” „” „” „” „” „„ ”„ ”„ ”„ ”„ ”„ ”„ ”„” „„ ”„ ”„ ”„ ”
To było niesamowite wyzwanie. Dziękujemy za wysłanie wiadomości!
Wyjaśnienie
Aby poczuć, co Nieczytelne może, a czego nie może zrobić, wyobraź sobie, że Brainfuck ma nieskończoną taśmę w obu kierunkach, ale zamiast wskaźnika pamięci przesuwającego się o jedną komórkę na raz, możesz uzyskać dostęp do dowolnej komórki pamięci, usuwając odwołanie ze wskaźnika. Jest to bardzo przydatne w tym rozwiązaniu, chociaż inne operacje arytmetyczne - w tym modulo - muszą być wykonywane ręcznie.
Oto program jako pseudokod z komentarzem reżysera:
// Initialize memory pointer. Why 5 will be explained at the very end!
ptr = 5
// FIRST PASS:
// Read all characters from stdin, store them in memory, and also keep track of the
// current line number at each character.
// We need the +1 here so that EOF, which is -1, ends the loop. We increment ptr by 2
// because we use two memory cells for each input character: one contains the actual
// character (which we store here); the other will contain the line number at which the
// character occurs (updated at the end of this loop body).
while ch = (*(ptr += 2) = read) + 1:
// At this point, ch will be one more than the actual value.
// However, the most code-economical way for the following loop is to
// decrement inside the while condition. This way we get one fewer
// iteration than the value of ch. Thus, the +1 comes in handy.
// We are now going to calculate modulo 4 and 5. Why? Because
// the mod 4 and 5 values of the desired input characters are:
//
// ch %5 %4
// ^ 1
// v 2
// k 3
// j 4
// ▲ 0 2
// ▼ 0 0
//
// As you can see, %5 allows us to differentiate all of them except ▲/▼,
// so we use %4 to differentiate between those two.
mod4 = 0 // read Update 2 to find out why mod5 = 0 is missing
while --ch:
mod5 = mod5 ? mod5 + 1 : -4
mod4 = mod4 ? mod4 + 1 : -3
// At the end of this loop, the value of mod5 is ch % 5, except that it
// uses negative numbers: -4 instead of 1, -3 instead of 2, etc. up to 0.
// Similarly, mod4 is ch % 4 with negative numbers.
// How many lines do we need to go up or down?
// We deliberately store a value 1 higher here, which serves two purposes.
// One, as already stated, while loops are shorter in code if the decrement
// happens inside the while condition. Secondly, the number 1 ('""") is
// much shorter than 0 ('""""""""'""").
up = (mod5 ? mod5+1 ? mod5+3 ? 1 : 3 : 2 : mod4 ? 3 : 1)
dn = (mod5 ? mod5+2 ? mod5+4 ? 1 : 3 : 2 : mod4 ? 1 : 3)
// As an aside, here’s the reason I made the modulos negative. The -1 instruction
// is much longer than the +1 instruction. In the above while loop, we only have
// two negative numbers (-3 and -4). If they were positive, then the conditions in
// the above ternaries, such as mod5+3, would have to be mod5-3 etc. instead. There
// are many more of those, so the code would be longer.
// Update the line numbers. The variables updated here are:
// curLine = current line number (initially 0)
// minLine = smallest linenum so far, relative to curLine (always non-positive)
// maxLine = highest linenum so far, relative to curLine (always non-negative)
// This way, we will know the vertical extent of our foray at the end.
while --up:
curLine--
minLine ? minLine++ : no-op
maxLine++
while --dn:
curLine++
minLine--
maxLine ? maxLine-- : no-op
// Store the current line number in memory, but +1 (for a later while loop)
*(ptr + 1) = curLine + 1
// At the end of this, minLine and maxLine are still relative to curLine.
// The real minimum line number is curLine + minLine.
// The real maximum line number is curLine + maxLine.
// The total number of lines to output is maxLine - minLine.
// Calculate the number of lines (into maxLine) and the real minimum
// line number (into curLine) in a single loop. Note that maxLine is
// now off by 1 because it started at 0 and thus the very line in which
// everything began was never counted.
while (++minLine) - 1:
curLine--
maxLine++
// Make all the row numbers in memory positive by adding curLine to all of them.
while (++curLine) - 1:
ptr2 = ptr + 1
while (ptr2 -= 2) - 2: // Why -2? Read until end!
*ptr2++
// Finally, output line by line. At each line, we go through the memory, output the
// characters whose the line number is 0, and decrement that line number. This way,
// characters “come into view” in each line by passing across the line number 0.
while (--maxLine) + 2: // +2 because maxLine is off by 1
ptr3 = 5
while (ptr -= 2) - 5:
print (*((ptr3 += 2) + 1) = *(ptr3 + 1) - 1) ? 32 : *ptr3 // 32 = space
ptr = ptr3 + 2
print 10 // newline
Tyle o logice programu. Teraz musimy przetłumaczyć to na Nieczytelne i zastosować kilka ciekawszych sztuczek golfowych.
Zmienne są zawsze dereferencyjne numerycznie w Nieczytelne (np. Stają a = 1się czymś podobnym *(1) = 1). Niektóre literalne liczby są dłuższe niż inne; najkrótsza to 1, następnie 2 itd. Aby pokazać, o ile dłuższe są liczby ujemne, oto liczby od -1 do 7:
-1 '""""""""'""""""""'""" 22
0 '""""""""'""" 13
1 '""" 4
2 '""'""" 7
3 '""'""'""" 10
4 '""'""'""'""" 13
5 '""'""'""'""'""" 16
6 '""'""'""'""'""'""" 19
7 '""'""'""'""'""'""'""" 22
Oczywiście chcemy przypisać zmienną nr 1 do tej, która występuje najczęściej w kodzie. W pierwszej pętli while jest to zdecydowanie mod5, co pojawia się 10 razy. Ale nie potrzebujemy mod5już po pierwszej pętli while, więc możemy ponownie przydzielić tę samą lokalizację pamięci do innych zmiennych, których będziemy używać później. To są ptr2i ptr3. Teraz zmienna odnosi się w sumie 21 razy. (Jeśli próbujesz samodzielnie policzyć liczbę wystąpień, pamiętaj o policzeniu czegoś takiego jak a++dwa razy, raz dla uzyskania wartości i raz dla jej ustawienia).
Jest tylko jedna zmienna, której możemy użyć ponownie; po obliczeniu wartości modulo chnie jest już potrzebne. upi dnpojawiają się tyle samo razy, więc albo jedno jest w porządku. Połączmy się chz up.
To pozostawia w sumie 8 unikalnych zmiennych. Możemy przypisać zmienne od 0 do 7, a następnie uruchomić blok pamięci (zawierający znaki i numery wierszy) na 8. Ale! Ponieważ 7 ma taką samą długość w kodzie jak -1, równie dobrze możemy użyć zmiennych od -1 do 6 i rozpocząć blok pamięci od 7. W ten sposób każde odniesienie do początkowej pozycji bloku pamięci jest nieco krótsze! To pozostawia nam następujące zadania:
-1 dn
0 ← ptr or minLine?
1 mod5, ptr2, ptr3
2 curLine
3 maxLine
4 ← ptr or minLine?
5 ch, up
6 mod4
7... [data block]
Teraz to wyjaśnia inicjalizacji na samej górze: to 5 bo to 7 (początek bloku pamięci) minus 2 (obowiązkowy przyrost pierwszy podczas stanu). To samo dotyczy pozostałych dwóch wystąpień 5 w ostatniej pętli.
Zauważ, że ponieważ 0 i 4 mają taką samą długość w kodzie ptri minLinemogą być przydzielane w obie strony. ... Czy mogliby?
Co powiesz na tajemniczą 2 w pętli while last-last? Czy nie powinno to być 6? Chcemy tylko zmniejszać liczby w bloku danych, prawda? Gdy osiągniemy 6, jesteśmy poza blokiem danych i powinniśmy przestać! Byłaby to luka bezpieczeństwa związana z błędem błędu przepełnienia bufora!
Zastanów się, co się stanie, jeśli nie przestaniemy. Zmniejszamy zmienne 6 i 4. Zmienna 6 to mod4. Jest to używane tylko w pierwszej pętli while i nie jest już tutaj potrzebne, więc nie wyrządzisz żadnej szkody. Co ze zmienną 4? Jak myślisz, ptrjaka powinna być zmienna 4, czy powinna być minLine? Zgadza się, minLinew tym momencie nie jest już używany! Zatem zmienna nr 4 jest minLinei możemy ją bezpiecznie zmniejszać i nie wyrządzać żadnych szkód!
AKTUALIZACJA 1! Golfed od 2199 do 2145 bajtów przez świadomość, że dnmogą również zostać połączone z mod5, choć mod5nadal jest używana do obliczania wartości dla dn! Nowe przypisanie zmiennych to teraz:
0 ptr
1 mod5, dn, ptr2, ptr3
2 curLine
3 maxLine
4 minLine
5 ch, up
6 mod4
7... [data block]
AKTUALIZACJA 2! Gra w golfa od 2145 do 2134 bajtów, zdając sobie sprawę, że ponieważ mod5jest teraz w tej samej zmiennej co dn, która jest liczona do 0 w pętli while, mod5nie musi już być jawnie inicjowana na 0.
AKTUALIZACJA 3! Grał w golfa od 2134 do 2104 bajtów, realizując dwie rzeczy. Po pierwsze, mimo że „negatywne modulo” Chodziło o to, warto na mod5, to samo rozumowanie nie dotyczy mod4, bo nigdy Test przeciwko mod4+2etc. Dlatego zmienia mod4 ? mod4+1 : -3się mod4 ? mod4-1 : 3przenosi nas do 2110 bajtów. Po drugie, ponieważ mod4zawsze wynosi 0 lub 2, możemy zainicjować mod4na 2 zamiast 0 i odwrócić dwie trójki ( mod4 ? 3 : 1zamiast mod4 ? 1 : 3).
AKTUALIZACJA 4! Gra w golfa od 2104 do 2087 bajtów, zdając sobie sprawę, że pętla while, która oblicza wartości modulo, zawsze działa co najmniej raz, aw takim przypadku Nieczytelny pozwala ponownie użyć wartości ostatniej instrukcji w innym wyrażeniu. Zatem zamiast tego while --ch: [...]; up = (mod5 ? mod5+1 ? [...]mamy teraz up = ((while --ch: [...]) ? mod5+1 ? [...](a wewnątrz tej pętli while obliczamy mod4najpierw, więc mod5jest to ostatnia instrukcja).
AKTUALIZACJA 5! Grał w golfa od 2087 do 2084 bajtów, zdając sobie sprawę, że zamiast zapisywać stałe 32i 10(spację i nową linię ), mogę zapisać liczbę 10 w (teraz nieużywanej) zmiennej nr 2 (nazwijmy to ten). Zamiast ptr3 = 5pisać ten = (ptr3 = 5) + 5, 32staje się ten+22i print 10staje print ten.