Perl + Math :: {ModInt, Wielomian, Prime :: Util}, wynik ≤ 92819
$m=Math::Polynomial;sub l{($n,$b,$d)=@_;$n||$d||return;$n%$b,l($n/$b,$b,$d&&$d-1)}sub g{$p=$m->interpolate([grep ref$_[$_],0..$map{$p->evaluate($_)}0..$}sub p{prev_prime(128**$s)}sub e{($_,$r)=@_;length||return'';$s=$r+1;s/^[␀␁]/␁$&/;@l=map{mod($_,p$s)}l(Math::BigInt->from_bytes($_),p$s);$@l+$r>p($s)&&return e($_,$s);$a=0;join'',map{map{chr$_+$a}l($_->residue,128,$s,($a^=128))}g(@l)}sub d{@l=split/([␀-␡]+)/,$_[0];@l||return'';$s=vecmax map length,@l;@l=g map{length==$s&&mod($m->new(map{ord()%128}split//)->evaluate(128),p$s)}@l;$$_=$m->new(map{$_->residue}@l)->evaluate(p$s)->to_bytes;s/^␁//;$_}
Obrazy kontrolne są używane do reprezentowania odpowiedniego znaku kontrolnego (np. ␀Jest dosłowny znak NUL). Nie przejmuj się zbytnio próbą odczytania kodu; poniżej znajduje się bardziej czytelna wersja.
Uruchom z -Mbigint -MMath::ModInt=mod -MMath::Polynomial -MNtheory=:all. -MMath::Bigint=lib,GMPnie jest konieczne (i dlatego nie jest uwzględnione w partyturze), ale jeśli dodasz go przed innymi bibliotekami, spowoduje to, że program będzie działał nieco szybciej.
Obliczanie wyniku
Algorytm jest tutaj nieco poprawialny, ale trudniej go napisać (ponieważ Perl nie ma odpowiednich bibliotek). Z tego powodu dokonałem kilku kompromisów między rozmiarem a wydajnością w kodzie, na tej podstawie, że biorąc pod uwagę, że bajty można zapisać w kodowaniu, nie ma sensu próbować zgrywać każdego punktu z gry w golfa.
Program składa się z 600 bajtów kodu oraz 78 bajtów kar za opcje wiersza poleceń, co daje karę w wysokości 678 punktów. Resztę wyniku obliczono, uruchamiając program na łańcuchu najlepszych i najgorszych (pod względem długości wyjściowej) dla każdej długości od 0 do 99 i dla każdego poziomu promieniowania od 0 do 9; średni przypadek jest gdzieś pośrodku, a to wyznacza granice wyniku. (Nie warto próbować obliczyć dokładnej wartości, chyba że pojawi się inny wpis z podobnym wynikiem).
Oznacza to zatem, że wynik ze skuteczności kodowania mieści się w zakresie od 91100 do 92141 włącznie, więc wynik końcowy wynosi:
91100 + 600 + 78 = 91778 ≤ wynik ≤ 92819 = 92141 + 600 + 78
Wersja mniej golfowa, z komentarzami i kodem testowym
To jest oryginalny program + nowe linie, wcięcia i komentarze. (W rzeczywistości wersja w golfa została wyprodukowana przez usunięcie nowych linii / wcięć / komentarzy z tej wersji.)
use 5.010; # -M5.010; free
use Math::BigInt lib=>'GMP'; # not necessary, but makes things much faster
use bigint; # -Mbigint
use Math::ModInt 'mod'; # -MMath::ModInt=mod
use Math::Polynomial; # -MMath::Polynomial
use ntheory ':all'; # -Mntheory=:all
use warnings; # for testing; clearly not necessary
### Start of program
$m=Math::Polynomial; # store the module in a variable for golfiness
sub l{ # express a number $n in base $b with at least $d digits, LSdigit first
# Note: we can't use a builtin for this because the builtins I'm aware of
# assume that $b fits into an integer, which is not necessarily the case.
($n,$b,$d)=@_;
$n||$d||return;
$n%$b,l($n/$b,$b,$d&&$d-1)
}
sub g{ # replaces garbled blocks in the input with their actual values
# The basic idea here is to interpolate a polynomial through all the blocks,
# of the lowest possible degree. Unknown blocks then get the value that the
# polynomial evaluates to. (This is a special case of Reed-Solomon coding.)
# Clearly, if we have at least as many ungarbled blocks as we did original
# elements, we'll get the same polynomial, thus we can always reconstruct
# the input.
# Note (because it's confusing): @_ is the input, $_ is the current element
# in a loop, but @_ is written as $_ when using the [ or # operator (e.g.
# $_[0] is the first element of @_.
# We waste a few bytes of source for efficiency, storing the polynomial
# in a variable rather than recalculating it each time.
$p=$m->interpolate([grep ref$_[$_],0..$#_],[grep ref,@_]);
# Then we just evaluate the polynomial for each element of the input.
map{$p->evaluate($_)}0..$#_
}
sub p{ # determines maximum value of a block, given (radiation+1)
# We split the input up into blocks. Each block has a prime number of
# possibilities, and is stored using the top 7 bits of (radiation+1)
# consecutive bytes of the output. Work out the largest possible prime that
# satisfies this property.
prev_prime(128**$s)
}
sub e{ # encoder; arguments: input (bytestring), radiation (integer)
($_,$r)=@_; # Read the arguments into variables, $_ and $r respectively
length||return''; # special case for empty string
$s=$r+1; # Also store radiation+1; we use it a lot
# Ensure that the input doesn't start with NUL, via prepending SOH to it if
# it starts with NUL or SOH. This means that it can be converted to a number
# and back, roundtripping correctly.
s/^[␀␁]/␁$&/; #/# <- unconfuse Stack Exchange's syntax highlighting
# Convert the input to a bignum, then to digits in base p$s, to split it
# into blocks.
@l=map{mod($_,p$s)}l(Math::BigInt->from_bytes($_),p$s);
# Encoding can reuse code from decoding; we append $r "garbled blocks" to
# the blocks representing the input, and run the decoder, to figure out what
# values they should have.
$#l+=$r;
# Our degarbling algorithm can only handle at most p$s blocks in total. If
# that isn't the case, try a higher $r (which will cause a huge increase in
# $b and a reduction in @l).
@l+$r>p($s)&&return e($_,$s);
# Convert each block to a sequence of $s digits in base 128, adding 128 to
# alternating blocks; this way, deleting up to $r (i.e. less than $s) bytes
# will preserve the boundaries between each block; then convert that to a
# string
$a=0; # we must initialize $a to make this function deterministic
join'',map{map{chr$_+$a}l($_->residue,128,$s,($a^=128))}g(@l)
}
sub d{ # decoder: arguments; encdng (bytestring)
# Reconstruct the original blocks by looking at their top bits
@l=split/([␀-␡]+)/,$_[0];
@l||return''; # special case for empty string
# The length of the longest block is the radiation parameter plus 1 (i.e.
# $s). Use that to reconstruct the value of $s.
$s=vecmax map length,@l;
# Convert each block to a number, or to undef if it has the wrong length.
# Then work out the values for the undefs.
@l=g map{
# Convert blocks with the wrong length to undef.
length==$s&&
# Convert other blocks to numbers, via removing any +128 and then
# using Math::Polynomial to convert the digit list to a number.
mod($m->new(map{ord()%128}split// #/# <- fix syntax highlighting
)->evaluate(128),p$s)
}@l;
# Remove the redundant elements at the end; now that they've reconstructed
# the garbled elements they have no further use.
$#l-=$s-1;
# Convert @l to a single number (reversing the conversion into blocks.)
$_=$m->new(map{$_->residue}@l)->evaluate(p$s)
# Convert that number into a string.
->to_bytes;
# Delete a leading SOH.
s/^␁//; #/# <- unconfuse Stack Exchange's syntax highlighting
# Finally, return the string.
$_
}
### Testing code
use Encode qw/encode decode/;
# Express a string using control pictures + IBM437, to make binary strings
# easier for a human to parse
sub format_string {
($_)=@_;
$_ = decode("Latin-1", $_);
s/[\0-\x1f]/chr (0x2400 + ord $&)/eag;
s/\x7f/chr 0x2421/eag;
s/[ -~\x80-\xff]/decode("IBM437",$&)/eag;
encode("UTF-8","\x{ff62}$_\x{ff63}")
}
sub test {
my ($string, $radiation, $samples) = @_;
say "Input: ", format_string($string);
my $encoding = e($string, $radiation);
say "Encoding: ", format_string($encoding);
say "Input length ", length($string), ", encoding length ", length($encoding), ", radiation $radiation";
my $decoding = d($encoding);
$decoding eq $string or die "Mistake in output!";
say "Decoding: ", format_string($decoding), " from ",
format_string($encoding);
# Pseudo-randomly generate $samples radiation-damaged versions.
srand 1;
for my $i (1..$samples) {
my $encdng = $encoding;
for my $r (1..$radiation) {
substr $encdng, int(rand(length $encdng)), 1, "";
}
my $newdecoding = d($encdng);
say "Decoding: ", format_string($newdecoding), " from ",
format_string($encdng);
$newdecoding eq $string or die "Mistake in output!";
}
say "";
length $encoding;
}
test "abcdefghijklm", 1, 10;
test "abcdefghijklm", 2, 10;
test "abcdefghijklm", 5, 10;
test "abcdefghijklm", 10, 10;
test "\0\0\0\0\0", 1, 10;
test "\5\4\3\2\1", 2, 10;
test "a", 10, 10;
my %minlength = ();
my %maxlength = ();
for my $length (0..99) {
my ($min, $max) = ("", "");
$length and ($min, $max) =
("\2" . "\0" x ($length - 1), "\1" . "\377" x ($length - 1));
for my $radiation (0..9) {
$minlength{"$length-$radiation"} = test $min, $radiation, 1;
$maxlength{"$length-$radiation"} = test $max, $radiation, 1;
}
}
say "Minimum score: ", vecsum values %minlength;
say "Maximum score: ", vecsum values %maxlength;
Algorytm
Uproszczenie problemu
Podstawową ideą jest zredukowanie problemu „kodowania kasowania” (który nie jest szeroko badany) do problemu kodowania kasowania (obszernie zbadany obszar matematyki). Kodowanie wymazywania polega na tym, że przygotowujesz dane do wysłania przez „kanał kasowania”, kanał, który czasami zastępuje wysyłane przez siebie znaki znakiem „pomieszania”, który wskazuje znaną pozycję błędu. (Innymi słowy, zawsze jest jasne, gdzie nastąpiło uszkodzenie, chociaż pierwotna postać jest nadal nieznana). Idea tego jest dość prosta: dzielimy dane wejściowe na bloki długości ( promieniowanie+ 1) i użyj siedmiu z ośmiu bitów w każdym bloku na dane, podczas gdy pozostały bit (w tej konstrukcji MSB) na przemian jest ustawiony dla całego bloku, wyczyść dla całego następnego bloku, ustawiony dla bloku potem i tak dalej. Ponieważ bloki są dłuższe niż parametr promieniowania, co najmniej jeden znak z każdego bloku przetrwa na wyjściu; więc, biorąc ciąg znaków z tym samym MSB, możemy ustalić, do którego bloku należała każda postać. Liczba bloków jest również zawsze większa niż parametr promieniowania, więc zawsze mamy co najmniej jeden nieuszkodzony blok w encdng; wiemy zatem, że wszystkie najdłuższe bloki lub najdłuższe remisy są nieuszkodzone, co pozwala traktować wszelkie bloki krótsze jako uszkodzone (a więc pomyłkę). Możemy również wydedukować taki parametr promieniowania (
Usuń kod
Jeśli chodzi o część problemu polegającą na kodowaniu skasowania, wykorzystuje się prosty specjalny przypadek konstrukcji Reeda-Solomona. Jest to konstrukcja systematyczna: wynik (algorytmu kodowania kasowania) jest równy wejściowi plus pewna liczba dodatkowych bloków, równych parametrowi promieniowania. Możemy obliczyć wartości potrzebne dla tych bloków w prosty (i golfistyczny!) Sposób, traktując je jak elementy, a następnie uruchamiając na nich algorytm dekodujący w celu „odtworzenia” ich wartości.
Sam pomysł konstrukcji jest również bardzo prosty: dopasowujemy wielomian, w możliwie najmniejszym stopniu, do wszystkich bloków w kodowaniu (z interpolacjami interpolowanymi z innych elementów); jeśli wielomianem jest f , pierwszy blok to f (0), drugi to f (1) i tak dalej. Oczywiste jest, że stopień wielomianu będzie równy liczbie bloków wejściowych minus 1 (ponieważ najpierw dopasowujemy wielomian do tych bloków, a następnie wykorzystujemy go do budowy dodatkowych bloków „kontrolnych”); a ponieważ punkty d +1 jednoznacznie definiują wielomian stopnia d, wykasowanie dowolnej liczby bloków (do parametru promieniowania) pozostawi liczbę nieuszkodzonych bloków równą pierwotnemu wejściowi, co jest wystarczającą informacją do odtworzenia tego samego wielomianu. (Musimy wtedy tylko ocenić wielomian, aby odblokować blok.)
Konwersja bazy
Ostatnią kwestią pozostawioną tutaj jest faktyczne wartości przyjęte przez bloki; jeśli wykonamy interpolację wielomianową na liczbach całkowitych, wynikiem mogą być liczby wymierne (zamiast liczb całkowitych), znacznie większe niż wartości wejściowe lub w inny sposób niepożądane. Dlatego zamiast liczb całkowitych używamy pola skończonego; w tym programie zastosowanym polem skończonym jest pole liczb całkowitych modulo p , gdzie p jest największą liczbą pierwszą mniejszą niż 128 promieniowania +1(tj. największa liczba pierwsza, dla której możemy dopasować wiele odrębnych wartości równych tej liczbie pierwszej do części danych bloku). Dużą zaletą pól skończonych jest to, że podział (z wyjątkiem 0) jest jednoznacznie zdefiniowany i zawsze będzie generował wartość w tym polu; dlatego interpolowane wartości wielomianów zmieszczą się w bloku w taki sam sposób jak wartości wejściowe.
Aby przekonwertować dane wejściowe na szereg danych blokowych, musimy wykonać konwersję bazy: przekonwertować dane wejściowe z bazy 256 na liczbę, a następnie przekonwertować na bazę p (np. Dla parametru promieniowania 1 mamy p= 16381). Było to głównie powstrzymywane przez brak podstawowych procedur konwersji Perla (Math :: Prime :: Util ma kilka, ale nie działają one na bazy bignum, a niektóre liczby pierwsze, z którymi pracujemy, są niewiarygodnie duże). Ponieważ już używamy Math :: Polynomial do interpolacji wielomianowej, byłem w stanie użyć go ponownie jako funkcji „przekształć z sekwencji cyfr” (przeglądając cyfry jako współczynniki wielomianu i oceniając go), i to działa na bignum w porządku. Idąc w drugą stronę, musiałem sam napisać tę funkcję. Na szczęście pisanie nie jest zbyt trudne (lub pełne). Niestety ta podstawowa konwersja oznacza, że dane wejściowe są zwykle nieczytelne. Istnieje również problem z wiodącymi zerami;
Należy zauważyć, że nie możemy mieć więcej niż p bloków na wyjściu (w przeciwnym razie indeksy dwóch bloków stałyby się równe, a jednak prawdopodobnie musiałyby wytwarzać różne wyniki z wielomianu). Dzieje się tak tylko wtedy, gdy dane wejściowe są bardzo duże. Ten program rozwiązuje problem w bardzo prosty sposób: zwiększenie promieniowania (co sprawia, że bloki są większe, a p znacznie większe, co oznacza, że możemy zmieścić znacznie więcej danych i co wyraźnie prowadzi do prawidłowego wyniku).
Inną kwestią wartą uwagi jest to, że kodujemy łańcuch zerowy do siebie, ponieważ program tak jak napisałby zawiesiłby się na nim inaczej. Jest to oczywiście najlepsze możliwe kodowanie i działa bez względu na parametr promieniowania.
Potencjalne ulepszenia
Główną asymptotyczną nieefektywnością w tym programie jest wykorzystanie modulo-prime jako omawianych pól skończonych. Istnieją pola skończone o wielkości 2 n (dokładnie tego tutaj chcielibyśmy, ponieważ rozmiary bloków mają naturalnie potęgę 128). Niestety, są one bardziej złożone niż prosta konstrukcja modulo, co oznacza, że Math :: ModInt by tego nie wyciął (i nie mogłem znaleźć żadnych bibliotek na CPAN do obsługi skończonych pól o rozmiarach innych niż podstawowe); Musiałbym napisać całą klasę z przeciążoną arytmetyką dla Math :: Polynomial, aby móc sobie z tym poradzić, a w tym momencie koszt bajtu może potencjalnie przewyższyć (bardzo małą) stratę wynikającą z użycia np. 16381 zamiast 16384.
Kolejną zaletą korzystania z potęgi 2 rozmiarów jest to, że podstawowa konwersja stałaby się znacznie łatwiejsza. W obu przypadkach przydatna byłaby lepsza metoda reprezentowania długości danych wejściowych; metoda „przedkładaj 1 w niejednoznacznych przypadkach” jest prosta, ale marnotrawiona. Dwusuwowa konwersja bazy jest tutaj jednym z możliwych podejść (chodzi o to, że masz bazę jako cyfrę, a 0 jako nie cyfrę, tak aby każda liczba odpowiadała jednemu ciągowi znaków).
Chociaż asymptotyczna wydajność tego kodowania jest bardzo dobra (np. Dla wejścia o długości 99 i parametru promieniowania 3, kodowanie ma zawsze długość 128 bajtów, a nie ~ 400 bajtów, które uzyskałyby podejścia oparte na powtarzaniu), jego wydajność jest mniej dobry przy krótkich nakładach; długość kodowania jest zawsze co najmniej kwadratem (parametr promieniowania + 1). Tak więc dla bardzo krótkich sygnałów wejściowych (długość 1 do 8) przy promieniowaniu 9 długość wyjściowa wynosi jednak 100. (Przy długości 9 długość wyjściowa wynosi czasami 100, a czasem 110.) Podejścia oparte na powtarzaniu wyraźnie pokonują to wymazanie - podejście oparte na kodowaniu na bardzo małych nakładach; warto zmieniać różne algorytmy na podstawie wielkości danych wejściowych.
Wreszcie, tak naprawdę nie pojawia się w punktacji, ale przy bardzo wysokich parametrach promieniowania, użycie odrobiny każdego bajtu (⅛ wielkości wyjściowej) do rozgraniczenia bloków jest marnotrawstwem; taniej byłoby użyć zamiast tego ograniczników między blokami. Rekonstrukcja bloków z ograniczników jest raczej trudniejsza niż w przypadku metody naprzemiennego MSB, ale uważam, że jest to możliwe, przynajmniej jeśli dane są wystarczająco długie (przy krótkich danych może być trudno wydedukować parametr promieniowania z wyjścia) . Można by na to spojrzeć, jeśli dąży się do asymptotycznie idealnego podejścia niezależnie od parametrów.
(I oczywiście może istnieć zupełnie inny algorytm, który daje lepsze wyniki niż ten!)
