sharper_99
2019-12-01 09:06

Jakby ktoś zapomniał edycja 2019 Adventa wystartowała https://adventofcode.com/
Ktoś będzie próbował w tym roku ?

iddqd

No ba! Pierwszy dzień zaliczony. :)

katelx

w tym roku raczej z czasem kiepsko, ale bede sie starac byc na biezaco, ewentualnie t+1 :( https://github.com/katelx/aoc/tree/master/2019

vpiotr

Ja miałem próbować kolejny raz z rzędu, ale znowu mi się nie chciało. :)

Freesher

Pierwszy dzień zrobiony. Zostało już tylko 24.

superdurszlak

Ostatnio coś się nie mogę zebrać do pisania kodu po godzinach :/

Kalrais

Byłoby ciekawiej, jakby w tym pierwszym zadanku użyli Collatza zwłaszcza w kontekście niedawnego dowodu Tao ;) . I to jest właśnie mój główny zarzut z poprzedniego roku do AoC. Te zadanka są nudne...

Maciej Cąderek

Zobaczymy ile wytrwam: https://github.com/caderek/aoc2019 :P Leaderboard (by @hauleth): 205905-acd3f4e2

katelx

@Kalrais: to wspaniale ze sie podzieliles tym spostrzezeniem z ludzmi ktorzy to lubia. czaimy - jestes na to za dobry. jeszcze jakis glebszy cel w tej jakze merytorycznej krytyce? po prostu idz na projecteuler.net malkontencie.

Kalrais

@katelx: Podzieliłem się swoimi wrażeniami z poprzedniego roku, gdzie jeśli dobrze pamiętam to 2 pierwsze tygodnie to były prawie same map/reduce'y. Wystarczy mi, że w pracy to ciągle klepie, no ileż można. :P Jak kogoś kręci sama rywalizacja to pewnie może być to fajna zabawa (zwłaszcza jak się jest w strefie czasowej, w której zadanka nie pojawiają się o 6:00 rano).

Clarc

Powodzenia dla wszystkich biorących udział i wytrwałości. Mnie przy drugiej części dzisiejszego zadania odciągnęły telefony i spotkania na 4 godziny. Jeśli zostanę dla zabawy to chyba z poślizgiem 12 godzinnym bo inaczej się nie uda tego ogarnąć :/

AreQrm

No pewnie! Jak co roku - nie chce mi się.

Sunnydev

yup. ale jak zwykle zaspałem z zadaniami :D

Maciej Cąderek

Jak ktoś używa JSa/TSa to zapraszam do skorzystania: TS starter | JS starter

lambdadziara

od tego dnia naiwne brute-force'owanie przestaje sie oplacac, probuje wziac intersekcje wszystkich punktow wire1 i wire2 aby otrzymac wszystkie punkty w ktore linie sie przecinaja, co dla >149000 punktow (a dokladnie to 149000 list 2 elementowych) zajmuje kilkanascie minut xD ale co zrobic innego jak sie nie zna odpowiedniego algorytmu

lion137

"intersekcję" wszystkich punktów!!! Ru crazy?:) Wystarczy startując od zera, aktualizować pozycje, sprawdzić czy się przecinają, zaktualizować minimum i na końcu je zwrócić.

lambdadziara

jak sprawdzic czy sie przecinają?

Shalom

Ja po prostu wygenerowałem sobie listę punktów na wire1, listę punktów na wire2, zrobiłem z tego dwa sety, przeciąłem te sety i voila, masz wszystkie punkty gdzie oba się stykają i robi się to momentalnie :)

lion137

Albo tak, złożonośc powinna być taka sama.

lambdadziara

@Shalom czyli jesli mamy liste punktow w1 i liste punktow w2, to najpierw robisz w1=set(w1), w2=set(w2) i potem dopiero liczysz ich intersekcje? Czy to mozliwe ze dlatego moj program jest taki wolny? Dla porownania jaka jest wielkosc listy punktow w wire przed jego przekonwertowanie na zbior a jaka po?

iddqd

@lambdadziara: Ja zrobiłem tak, że zrobiłem listę wszystkich punktów dla w1 i w2, potem część wspólną, dla każdej odległość i tyle. Do tego mam x,y, dystans, więc od razu wyciągam ile każdy przewód ma długości, dodaje i koniec. Chociaż ja jestem w algorytmy cienki jak barszcz, więc moje rozwiązanie pewnie jest brzydkie i kijowe. Mi jedzie niecałe dwie minuty na i5 3.4GHz, 4 core.

BTW jest lista dla 4programmers ale nie znam kodu zaproszenia: https://adventofcode.com/2019/leaderboard/private/view/205905

lambdadziara

no nie wiem, to jest moje rozwiazanie, zwraca dobry wynik ale gdzies po kilkunastu minutach, tez biore czesc wspolna https://pastebin.com/9jHjy5UR

Shalom

@lambdadziara: masz bana na standardowe api pythona? :D set(wire1).intersection(set(wire2)) i voila, liczy się momentalnie. Tak samo można użyć min(), nie trzeba go implementować od zera...

lambdadziara

dla "list of list" nie działa. Ja mam wspolrzedne punktorw wire1 i wire2 w takiej formie: 1,2],[3,3, gdzie pierwszy index to x a drugi y. A ty jak masz?

Shalom

@lambdadziara to weź jak człowiek zrób z tego krotki ;] nowalista = map(tuple, tatwojalista) i potem już spokojnie zadziała set(nowalista). Bo teraz szukasz tych przecięć w O(n*m) a przecięcie hashsetów to O(n), więc wielokrotnie szybciej.

Maciej Cąderek

@lambdadziara: Heh, moje pierwsze podejście było podobnie tępe, na szczęście w Node to ~2.5min. Po zaminaie tablicy na Map (Set akurat mi nie pasował) niecałe 0.5sec :D

lambdadziara

@Shalom z tymi krotkami to magia, program zwraca odpowiedz po paru sekundach :)

Shalom

@lambdadziara: to nie kwestia krotek tylko setów ;) A krotka, w przecieństwie do listy jest hashowalna (bo krotka jest immutable, a do listy można zawsze cośtam dodać) i da się ją włożyć do hashseta.

lambdadziara

teraz mam problem z czescia druga, dla testowych przykladach dostaje wynik za maly o 21 i 22 wiec gdzies robie za malo krokow ale nie wiem gdzie https://pastebin.com/KLiMEPgT

lambdadziara

chyba ze po prostu zmodyfikuje pierwszy program, zeby zwracal indeks, jesli indeks wskazuje na intersekcje i ten indeks+1 to bedzie liczba krokow do danej intersekcji

Shalom

@lambdadziara o_O brak mi słów. Przecież skoro masz listę krotek z których składa sie wire, to co za problem zrobić lista.index(punkt_przeciecia) które zwróci ci dokładnie liczbę kroków dla tego wire. Uważaj tylko przy tworzeniu tejże listy żeby nie brać wielokrotnie tego samego punktu niepotrzebnie, tzn jednocześnie jako "końca" danego fragmentu jak i "początku" nowego. Sugeruje odliczać od 1 a nie od 0 jak dodajesz nowy fragment. Więc zamiast twojego range(self.x, self.x+delta) powinno być range(self.x+1, self.x+delta) bo self.x juz jest uwzgędnione.

lambdadziara

@Shalom czekaj, czekaj. Czyli range(self.x+1, self.x+delta) w goRight i range(self.y+1, self.y+delta) w goDown ale nadal mam wtedy blad off by 8 i off by 4. 618 i 406 zamiast 610 i 410. Mam problem ze zwizualizowaniem sobie, gdzie jest ten blad

Shalom

Ech no bo robisz to w mocno zrypany sposób i jakoś kombinujesz niepotrzebnie. Ten range mógłby zawsze wyglądać tak samo, tylko dalej byłoby np. (x+i,y) jeśli idziesz w prawo albo (x, y+i) jak w górę itd. Wtedy nie trzeba by sie zastanawiać czy ten range ma mieć +1 czy -1, ale generalnie musi być albo jedno albo drugie. Bo zauważ że jak masz range(self.x, self.x+delta) to zaczynasz od pola self.x na ktrym właśnie stoisz i ono JUŻ JEST w liscie. Nie potrzeba dodawać go drugi raz (i potem mieć tam dwóch kroków zamiast jednego).

lambdadziara

hmm, sprobuje jeszcze usunac punkty z listy jesli, lst[i]==lst[i+1] to powinno rozwiazac problem dodawania punktu na ktorym wlasnie stoje, tylko bedzie to znowu dlugo trwalo

lambdadziara

no albo po prostu nie wrzucac punktu do listy jesli jest taki sam jak ostatni element

Maciej Cąderek

Udało się komuś napisać regexa dla par w Day 4 part 2?

Tyle udało mi się wymyśleć (z dodatkowym some):

(pass.match(/(.)\1+/g) || []).some(x => x.length === 2)

Całość: https://github.com/caderek/ao[...]blob/master/src/day4/index.ts

lambdadziara

subseqs=[item[0] for item in re.findall(r"((.)\2*)", s)] wszystkie podciagi z tym samymi znakami. Ale nie trzeba uzywac regexa do tej czesci btw mozna zrobic cos w tym stylu

for i in range(10):
  count=0
  for c in code:
    if c==str(i): count+=1
  if count==2: return True
return False
Maciej Cąderek

@lambdadziara: ((.)\2*) przecież ten regex to prawie to samo co (.) (wszystko pasuje). Chyba, że czegoś nie czaję. Że bez regexa można zrobić to wiadomo ;)