kq
2018-12-01 15:05

Dziś o 6 rano ruszyła nowa edycja Advent of Code

Zapraszamy do wspólnej zabawy. Forumowy leaderboard: 205905-acd3f4e2

Jeśli wrzucacie gdzieś swoje rozwiązania to się pochwalcie, to wspaniała okazja zobaczyć jak można te same zadania rozwiązać w innym języku lub za pomocą innego algorytmu. Zacznę od siebie: https://github.com/KrzaQ/AdventOfCode2018

#adventofcode

katelx

ja po raz kolejny robie w haskellu + planuje w pythonie jak mi sie nie znudzi (bo potem dluzsze zadania sa) https://github.com/katelx/aoc/tree/master/2018

daniel1302

@katelx: :D Widzialem Twojego jednoliniowca w pythonie :D https://github.com/katelx/aoc[...]er/2018/day01/solution.py#L12

Najs ale przez takie jednoliniowce perl przyjął miano write only / not readable

WeiXiao

@katelx: Da radę zrobić task1 part2 jednym linq chainem?

katelx

@WeiXiao: bez oszukiwania to nie mam pomyslu, albo framework, albo moja jego znajomosc jest uboga (no chyba ze sobie zdefiniujesz proste extension method Cycle do IEnumerable generujacy input w nieskonczonosc, ale wtedy problem staje sie trywialny :)), z oszukiwaniem to cos w stylu: Enumerable.Repeat(0, 1).Select(_ => { int result = 0; /* tu wlasciwy algorytm */ return result; }).ToList().ForEach(Console.WriteLine);, tzn po prostu sobie robisz jednoelementowa liste i potem w select wlasciwa implementacje krok po kroku ;)

przemyslowiec

Dołaczyłem, głównie zamierzam rozwiązywać je w pythonie, ale też zastanawiam się na sporóbowaniem w Go

Kalrais

Pytanie do tych co uczestniczyli w poprzednich latach, czy większość zadań sprowadza się do map/filter/reduce tak jak te pierwsze 4? Bo jeśli tak to trochę szkoda mi czasu na to.

kq

Nie, możesz zresztą zobaczyć zadania z poprzednich lat :​) Trudność zadań rośnie wraz z dniami

kq

C++ jest średnim rozwiązaniem dla tego formatu, gdzie liczy się szybkość naklepania zadanka. No i w Rubym mogę klepać magiczne onelinery :​D Ale pewnie jakieś zadanko dodam w C++, ale nie będę się spinał, wolę potraktować AoC jako powód do podszlifowania Rusta

Shalom

@szarotka: wiesz ze jest coś takiego jak Set? :)

szarotka

Oj tam oj tam. Miło, że mnie podglądasz, aż się zarumieniłam :)

wiciu

Fajna zabawa. Też rozwiązałem te zadania z pierwszej części. :-)

Afish

@Kalrais: Robiłem w poprzednich latach i niestety na cały sezon trafiały się może ze 3 dni, gdy trzeba było coś ciekawszego, niż pałowanie map/reduce lub BFS generujący wszystkie stany.

katelx

@Afish ale to nie jest jeden chain

Vincent_zyx

czy tylko w javie robienie tych zadan mija sie z celem?:/
zrobilem pierwsze dwa dni, tyle ze w 100% imperatywnie na petlach.
czy ktos rozwiazywal, albo moglby dac sample jak rozwiazuje day1/part2 lub day2 na streamach, etc?

edit*: tym co mnie blokuje w tym zeby skrocic zapis w streamach/lambdach, jest to ze nie moge w nich modyfikowac zmiennych lokalnych

baant

nigdzie w zasadach nie ma, że ma być funkcyjnie, na streamach, etc :P

Shalom

@Vincent_zyx: A czemu niby nie możesz modyfikować zmiennych? o_O Oczywiście że możesz. Wystarczy ze masz jakiś wrapper w stylu AtomicLong choćby. Zresztą popatrz na kod od @Afish kilka komentarzy wyżej, to samo możesz zrobić w Javie jeśli chcesz. To nie Java jest probleme, tylko to że nie umiesz pisać funkcyjnego kodu ;)

superdurszlak

@baant: nigdzie nie ma, ale programowanie funkcyjne jest teraz na topie :P także tfu-tfu imperatywne rozwiązania są chyba mocno passe

superdurszlak

znaczy nie mówię, collection.filter { /* blah blah blah */ }.doCośtam { /* pleh pleh pleh */ } jest dużo bardziej czytelne od jakiejś pętlozo-ifozy i nawet fajnie się tak pisze np. w Kotlinie, ale w takim Pythonie jakoś nie umiem się przestawić

baant

oczywiście, że tak. Ale to nie znaczy, że robienie imperatywnie mija się z celem. Lepiej poćwiczyć jakkolwiek niż nie poćwiczyć w ogóle, bo nie zna się streamów xd Zawsze można znaleźć odpowiedź imperatywnie, a potem przepisać na streamy

nalik

Skoro liczy się czas rozwiązania, to lepiej zrobić jak się umie, a potem przepisać na coś co wygląda dobrze.

kq

Ja tak właśnie robię

paulonio

Prośba o podpowiedż: https://4programmers.net/Pastebin/10118 Dlaczego to zwraca błędne wynik dla pierwszej części day2?

kq

Początkową wartością którą ustawiasz powinno chyba być 1

nalik

@paulonio Ile razy chciałbyś policzyć linię, która zawiera więcej niż jeden podwójny czy potrójny znak?

paulonio

@nalik dzięki, dopiero teraz doczytałem dokładnie ostatni przykład ;)

WeiXiao

@Afish: a bez hacka .Range(0, int.MaxValue) dałoby radę? że serio nie wiesz kiedy to wypadnie. :P

Afish

Tak, o ile zrobisz odczyt pliku wielokrotnie.

WeiXiao

@Afish: nie no, plik chcemy czytać raz, a w nums trzymać tylko tyle, ile trzeba :P

Afish

A to nie wiem. W LINQ brakuje sporo fajnych metod, więc nie zdziwi mnie, jeżeli nie da się tego zrobić.

WeiXiao

claims = length . filter (> 1) . map length . group . sort . (>>= claim) where claim [_, x, y, h, v] = (,) <$> [x .. x + h - 1] <*> [y .. y + v - 1] ???

katelx

@WeiXiao: o co chodzi? to akurat dosc latwo mozna przepisac na jeden ladny linq chain

WeiXiao

@katelx: jakieś _, (,) .. <$> :D ciekawie się bawicie w tym .hs Możesz pokazać ten chain :P

kq

Widzę, że znów spędzę kilka godzin nad zrozumieniem Twoich rozwiązań @katelx :​)

katelx

@WeiXiao poszukaj sobie rozwiazan w k, tam sa fajne magiczne, jednoznakowe funkcje @kq ja mam odwrotny problem, nie wazne jak szybko rozwiazuje to nie jestem w stanie cie wyprzedzic, chyba czas na jakies dopalacze ;)

mariusz345

jest okej, podoba mi się ta inicjatywa

nalik

To o której wy wstajecie? :)

Kalrais

@WeiXiao: Ta linijka jest akurat prosta: w where definiujesz funkcje pomocniczą która bierze prostokąt i generuje wszystkie punkty na gridzie które się w nim zawierają. Później idąc od prawej strony (urok notacji prefiksowej) robisz map z claim (tutaj to jest akurat bind bo bawimy się listą jako monadą), czyli generujesz wszystkie punkty dla każdego prostokąta, póżniej grupujesz wszystkie tak wygenerowane punkty, zliczasz w grupach, filtrujesz, i zliczasz wszystkie.

WeiXiao

Ja po prostu zbierałem wszystkie (x,y) i liczyłem ich występowanie :P a claim, którego wszystkie (x,y) mają ilość wystąpień 1 = wynik

Kalrais

Mi się zupełnie nie chciało bawić i spałowałem na macierzy. ;)

M = np.zeros((1000, 1000))
for (_,x,y, w, h) in xs:
    M[x:x+w, y:y+h] += 1
print(np.sum(M > 1))
Kalrais

BTW: @katelx dość oryginalny sposób robienia produktu kartezjańskiego ja to robię tak - [(x,y) | x <- xs, y <- ys] , ale twój rzeczywiście wymaga mnie znaków. :)

superdurszlak

chyba pora uczyć się FP, żeby być w stanie się porozumieć.. :v

katelx

@Kalrais: w list comprehension nie podoba mi sie to ze wprowadza niepotrzebne zmienne, dlatego imo ladniej operatorami lub liftM2 (,) xs ys @KrzaQ miales racje, zaspales czy ruby byl za wolny? ;) @WeiXiao chaina napisze przy okazji

kq

Zaspany byłem i źle się zabrałem, na siłę chciałem function chain wsadzić. No i niestety do tego zadania Ruby jest do d**y, moje pierwsze rozwiązanie jechało ~12sekund na reakcję (więc part2 kilka minut). Po optymalizacjach zszedłem do 5 sekund i dalej nie umiem.

Shalom

Imperatywnie lvl 5 prosty (chamskim iterator.remove() :D) ale chwile mi zajęło żeby zrobić to collapse funkcyjnie:

private fun collapseFunctional(list: List<Byte>, start: Int = 0): List<Byte> {
    return IntStream.range(start, list.size - 1)
            .filter { index -> pairConverges(list[index].toChar(), list[index + 1].toChar()) }
            .mapToObj { x -> x }
            .findAny()
            .map { removalIndex ->
                collapseFunctional(IntStream.range(0, list.size)
                        .filter { index -> index != removalIndex && index != removalIndex + 1 }
                        .mapToObj { index -> list[index] }
                        .asSequence()
                        .toList(), if (removalIndex > 0) removalIndex - 1 else 0)
            }
            .orElse(list)
}

Różnica w czasie wykonania oczywiście też kolosalna, ale to było spodziewane ;]

kq

Ja planuję zrobić day 5 Manacherem i zobaczyć jak (czy) to śmiga.

Kalrais

@Shalom: Muszę powiedzieć że na pierwszy rzut oka nie rozumiem twojego rozwiązania. A samo zadanko do zrobienia funkcyjnie jest przecież proste: zaczynasz ze streamem znaków i pustym stosem, i robisz reduce na streamie na zasadzie jak current jest przeciwinieństwem top na stosie to robisz pop() jak nie jest to robisz push(). Nie ma tu nic nie funkcyjnego i działa w O(n)

Kalrais

1 linijka w haskellu

main = (-2+) . length . (foldl (\(x:xs) y -> if x /= y && (toLower x) == (toLower y) then xs else (y:x:xs)) ['-']) <$> (readFile "2018/day05/in.txt")
Shalom

@Kalrais: ten kod wyżej jest raczej dość prosty -> znajdujemy pierwszą parę do usunięcia i aplikujemy funkcje rekurencyjnie na liście z usuniętą parą. Jeśli takiej pary nie znaleźliśmy to zwracamy aktualną listę.

paulonio

Ktoś ma jakieś szybsze/ ładniejsze rozwiązanie w Pythonie? https://4programmers.net/Pastebin/10158 Bo jak widzę te wasze rozwiązania w haskellu, to wydaje mi się jakbym jakieś dłuższe i trudniejsze zadanie rozwiązywał ;)

Kalrais

@paulonio: Z tego co widzę napisałeś mniej więcej to co Shalom. Szybsze powinno być rozwiązanie, które opisałem wyżej. Na pythona tłumaczy się jakoś tak - https://4programmers.net/Pastebin/10159

Shalom

No gdzie tam, on robi replace regexpami w pętli aż się przestanie coś zmieniać, niewiele to ma wspólnego z moim rozwiązaniem :P

Kalrais

Obaj usuwacie >0 w jednej iteracji do osiągnięcia punktu stałego. Jak dla mnie podobne. :P

kq

@katelx: I znów wygrało dobro (@kq) ;​)

katelx

@kq w pracy jestem, to dlatego ;) a tak serio to zamotalam sie z wykrywaniem nieskonczonosci :(

WeiXiao

ja*****. Miałem przerwę ze 2 dni, zacząłem zadanko 4.1 - test przechodzi, a normalny data set nie. Po pół h debugu z jakimś gotowym kodem i zauważyłem, że nie umiem czytać i o 1 zbyt długo brałem kiedy są asleep :P Enumerable.Range(start, end - start+1) => Enumerable.Range(start, end - start)

katelx

@kq :D no ale sobota rano, wybaczam @WeiXiao lepiej by bylo przepisac od nowa w te pol h ;)

kq

@katelx: Miałem problemy techniczne i mi ST usunął plik z rozwiązaniem w trakcie działania :​( 8 00:10:07 228 0 00:33:30 648 0

WeiXiao

@katelx: Wiesz... jeżeli piszesz kod i twój algorytm wydaje Ci się flawless, to tak niechętnie jest pisać od nowa :/ zresztą nie wiem czy miałbym inny pomysł :P

kq

@katelx: wrzucaj rozwiązania, ciekaw jestem jak w haskellu zrobiłaś d13 :​P

katelx

@kq niestety rozwiazuje na pc w pracy i nie moge kodu nigdzie wrzucic bo mnie posadza o wykradanie danych. przepisze w weekend :) btw to mi sie zdawalo ze dzis nadzwyczaj szybko zrobilam ale rzut oka na leaderboard pozbawil mnie zludzen ;(

katelx

@kq widzialam, graty! :) ja powoli trace nadzieje ze choc raz sie wbije do 100 w tym roku. ale dzis bylam blisko

kq

Dziś nawet top 50 weszło w p2.

katelx

noooooo! ;) a ja przez || zamiast && stracilam z 10 minut :(

kq

Nie, kompletnie się zakopałem :​/

kq

No dziś to jakaś mega porażka...

katelx

moje rozwiazanie sie obliczylo po ponad godzinie :(

kq

Ja pierwszą część zrobiłem jak kompletny kretyn (bawiłem się w RE zamiast wyprintować output na pałę), ale przy drugim już użyłem mózgu. 21 00:50:46 312 0 00:59:40 96 5

kq

W Rubym mi długo liczy, ale C++ migiem (modern C++ ;​D)

katelx

no, widzialam ten c++, calkiem ladny jak na codegen, ja gdyby nie powolny kod to bym byla w top 50 :( 21 00:34:17 189 0 01:37:12 263 0

kq

Ja się zastanawiam jak by mi poszło gdybym włączył mózg, bo dziś zadanie idealne żeby punktów nałapać :​/ A Part2 szybko zrobiłem. No cóż, jeszcze 3.5 dnia, może coś się uda. Teraz najważniejsze to nie stracić leadów :​D

WeiXiao

@katelx: moje rozwiazanie sie obliczylo po ponad godzinie :o

katelx

@kq niestety nie zaczelam nawet bo prawie caly dzien poza domem :( + pakuje sie na wczasy, takze aoc dokoncze pewnie w styczniu. fajnie w tym roku bylo, gratuluje ci wygranej i nie ma mowy ze za rok bede nizej niz na 1 miejscu ;);)

kq

Na wczasach też możesz kampić w kiblu z laptopem! Ale dzięki.

WeiXiao

kurde, fajnie ten haskell wygląda.