Kompresja różnicowa [zamknięta]

20

Aby sprostać temu wyzwaniu, musisz skompresować różnicę. Różnica to niektóre dane reprezentujące różnicę między dwoma łańcuchami. Aby sprostać temu wyzwaniu, musisz zapewnić jeden lub więcej programów, które mogą:

  1. Wejście Ai Bwyjście diff,C
  2. Wejście Ai C, i wyjścieB
  3. Wejście Bi C, i wyjścieA

Celem jest uczynienie różnicy Cmożliwie najmniejszą. Różnica może być dowolna: ciąg, liczba, kropla danych. Dbamy tylko o rozmiar (liczbę bajtów).

Mam 50 przypadków testowych, które można znaleźć na Github . Każdy przypadek testowy składa się z dwóch oddzielonych spacjami adresów URL, które wskazują na 2 pliki, które należy różnicować. (Te przypadki testowe pochodzą z profili Github członków PPCG. Dziękujemy wszystkim!)

Wszystkie trzy powyższe zadania powinny zająć mniej niż minutę, aby uruchomić się na komputerze o rozsądnej mocy (dla każdego przypadku testowego).

Twój wynik jest równy całkowitemu rozmiarowi (w bajtach) wszystkich 50 różnic, im niższy, tym lepszy. Twarde kodowanie różnic w twoim programie jest niedozwolone (zastrzegam sobie prawo do zmiany przypadków testowych, aby zapobiec twardemu kodowaniu). Wbudowane, które wytwarzają różnice (podobne diffutils) są niedozwolone.

code-challenge compression Nathan Merrill
źródło
4
Czym właściwie jest diff?
Conor O'Brien,
Naprawdę wszystko, co chcesz. Nieformalnie jest to ciąg znaków, który reprezentuje różnice między AiB
Nathan Merrill
1
Więcej linków: numerowanie par przypadków testowych według indeksu linii 1-bazowej; obie pary przypadków testowych 3, 13, 14, 15, 16, 17, 18, 19, 20, 21 mają wartość 404. Poza nimi udało mi się odzyskać co drugi przypadek.
H Walters,
3
Zamykam to pytanie, ponieważ jest w dużej mierze bez odpowiedzi i wiele starych linków, których użyłem jako przypadków testowych, już nie działa. Zaktualizuj pytanie i otwórz je ponownie, jeśli chcesz.
Nathan Merrill
1
Gotowy. GIST to gist.github.com/sethhillbrand/64066935e3f8c0fac75d75edd43c9ef8 Drugi plik to nieokreślone archiwum 40 pozostałych par przypadków testowych.
Seth

Odpowiedzi:

0

Czy moja odpowiedź jest ważna?

set f [open commits.txt]
while {![eof $f]} {scan [gets $f] %s\ %s a b; puts [string compare $a $b]}
close $f

testowany na: http://www.tutorialspoint.com/execute_tcl_online.php?PID=0Bw_CjBb95KQMNmd4QkxvQUFsTnM

sergiol
źródło
1
Musisz podać wiele programów (zarówno diffrównoważnych, jak i patchrównoważnych). Jeśli string comparediffs ciągi, narusza zasadę „brak wbudowanych”. Jeśli porównuje tylko ciągi znaków (jak sugeruje nazwa), nie pozostawia wystarczającej ilości informacji do odtworzenia łatki.
@ ais523: buildins Zrozumiałem to jako polecenia wiersza poleceń. Wiem, że string comparenie generuje informacji do utworzenia strony, ale nie ma miejsca w pytaniu o to.
sergiol
Z pytania „2. Wpisz A i C, a wyjdź B”. Jest to coś, czego twój program nie może zrobić, a tak naprawdę żaden program nie mógłby tego zrobić (ponieważ nie ma wystarczającej ilości informacji).
@ ais523: OK, źle zrozumiałem.
sergiol
@ ais523: Nie sądzę, aby twoje stwierdzenie było poprawne „w rzeczywistości żaden program nie mógłby tego zrobić”. Jeśli C jest różnicą między A i B, to biorąc pod uwagę C i A, B można obliczyć. Może brakowało mi twojego dokładnego punktu
Seth