Autor | Zpráva | ||
---|---|---|---|
RastyAmateur Profil |
#1 · Zasláno: 18. 11. 2017, 12:35:00
Zdravím, nevím, má-li někdo zkušenosti s AdventOfCode, ale zasekl jsem se na druhé části úlohy 2016#7. Zadání zní následovně:
An IP supports SSL if it has an Area-Broadcast Accessor, or ABA, anywhere in the supernet sequences (outside any square bracketed sections), and a corresponding Byte Allocation Block, or BAB, anywhere in the hypernet sequences. An ABA is any three-character sequence which consists of the same character twice with a different character between them, such as xyx or aba. A corresponding BAB is the same characters but in reversed positions: yxy and bab, respectively. For example: - aba[bab]xyz supports SSL (aba outside square brackets with corresponding bab within square brackets). - xyx[xyx]xyx does not support SSL (xyx, but no corresponding yxy). - aaa[kek]eke supports SSL (eke in supernet with corresponding kek in hypernet; the aaa sequence is not related, because the interior character must be different). - zazbz[bzb]cdb supports SSL (zaz has no corresponding aza, but zbz has a corresponding bzb, even though zaz and zbz overlap). How many IPs in your puzzle input support SSL? ... rhamaeovmbheijj[hkwbkqzlcscwjkyjulk]ajsxfuemamuqcjccbc gdlrknrmexvaypu[crqappbbcaplkkzb]vhvkjyadjsryysvj[nbvypeadikilcwg]jwxlimrgakadpxu[dgoanojvdvwfabtt]yqsalmulblolkgsheo dqpthtgufgzjojuvzvm[eejdhpcqyiydwod]iingwezvcbtowwzc[uzlxaqenhgsebqskn]wcucfmnlarrvdceuxqc[dkwcsxeitcobaylhbvc]klxammurpqgmpsxsr gmmfbtpprishiujnpdi[wedykxqyntvrkfdzom]uidgvubnregvorgnhm txxplravpgztjqcw[txgmmtlhmqpmmwp]bmhfgpmafxqwtrpr[inntmjmgqothdzfqgxq]cvtwvembpvdmcvk ... Na internetu jsem našel pár řešení, ovšem mě by zajímalo, proč nefunguje to mé. Moje idea byla taková, že pomocí regexu (\w)(\w)\1(.*?)\2\1\2 vyhledám potřebné dvojice trojic (je-li tomu rozumět, prostě aba...bab) a pak v té části (.*?) (v příkladu to jsou 3 tečky) spočtu, kolikrát se tam objevují hranaté závorky. Je-li to číslo liché, znamená to, že by teoreticky daná IP měla podporovat SSL.
Nenapadá někoho, kde má tu skulinku, kvůli které mi to stále nevychází? Děkuji, RA |
||
Keeehi Profil |
#2 · Zasláno: 18. 11. 2017, 14:35:19
1. Proč jsou v textu označené i tři znaky za závorkou?
2. Nemusí být ta sekvence hned v následující závorce. 3. Kontroluješ, zda se \1 a \2 liší? Tímhle si nejsem úplně jistý, ale když regulární něco matchne, nezačne prohledávat string až za koncem toho co matchnul? Pokud ano, tak v stringu abaxded[edexbab] najde aba ale přeskočí ded.
|
||
Tomáš K. Profil * |
#3 · Zasláno: 18. 11. 2017, 15:09:24
RastyAmateur:
Myslím že pokud v části před závorkou za sebou ABA a BAB, a poté BAB i v závorce, najde tvůj výraz jen tu část před závorkou a řekne, že SSL není podporováno. ababab[bab]xxx |
||
Keeehi Profil |
#4 · Zasláno: 18. 11. 2017, 15:56:47
Ono pokud to nemusí být hned v následující závorce, ale v jakékoli následující, tak bych na to šel asi jinak. Obyčejným cyklem bych prošel celé pole po třech znacích a vytahal si do dvou polí všechny trojice splňující formát aba. Jedno pole pro trojce mimo závorku, druhé pole pro trojice ze závorky. Ke každé takové trojici bych si pamatoval vzdálenost od začátku. Pak bych jen prošel první pole a v druhém hledal bab záznamy které mají od začátku větší vzdálenost než aktuálně hledaný záznam.
|
||
RastyAmateur Profil |
#5 · Zasláno: 18. 11. 2017, 16:16:44
Keeehi #2:
1) Nevím přesně, co myslíš? 2) Podle mě ne, nebo ano? Zadání pouze říká, že musí být v hypernet sequences... 3) Ano Jinak k té poznámce, také si tím nejsem úplně jistý, ale mám pocit, že to najde všechny možnosti. Během večera ještě otestuji Tomáš K. #3: Mám tam cyklus, projede to všechny shody nalezené daným patternem Keeehi #4: Rozumím tomu principu, ale nechápu, proč si ukládat vzdálenosti. Jako první může být i část bab, až po ní aba (viz aaa[kek]eke supports SSL (eke in supernet with corresponding kek in hypernet; the aaa sequence is not related, becaue... )
|
||
Tomáš K. Profil * |
#6 · Zasláno: 18. 11. 2017, 17:33:07
Keeehi:
Rozumím tomu tak, že dostane seznam řetězců (jeden na řádku), a o každém má prohlásit, jestli podporuje SSL nebo ne. V každém je právě jeden pár závorek. Tři znaky za závorkou jsou označené, protože ABA je mimo závorky, ale není řečeno, jeslti pře nebo za. RastyAmateur: Koukám, na ten můj příklad a je špatně, chytne se to na druhý výskyt aba. Lépe tedy takto: abaxbab[bab]xxx . Projet všechny výskyty nestačí, .*? je non-greedy, ne libovolně greedy. Vrátí nejkratší možný match (abaxbab , ne všechny (abaxbab , abaxbab[bab] ). Nepomůže ani udělat to jednou greedy a jednou non-greedy i na to by šel protipříklad.
|
||
Keeehi Profil |
Tomáš K.:
Díky za vysvětlení, oni ty označené části mají asi reprezentovat celý vstup. Já myslel, že to je jen označení důležité části ze vstupu a proto mi to bylo divné. RastyAmateur: „proč si ukládat vzdálenosti“ Protože jsem myslel, že záleží na pořadí. Na obrazovce mobilu to zadání nebylo nejlépe formátované a tak jsem to spíš prolétl. Myslím, že Tomáš K. na to přišel. Proto jsem vytvořil řetězec, který by měl projít, ale ten tvůj regulár ho nezvládne. abaxbab[bab]bab Tak jsem si to pro zábavu taky zkusil. <?php function doesSupportTLS($input) { $length = strlen($input); $inBrackets = false; $in = []; $out = []; $found = false; for ($i = 0 ; $i < $length - 3 ; $i++) { if ($input[$i] === '[' || $input[$i] === ']') { $inBrackets = !$inBrackets; } if($input[$i] === $input[$i+3] && $input[$i+1] === $input[$i+2] && $input[$i] !== $input[$i+1] && $input[$i] !== '[' && $input[$i] !== ']' && $input[$i+1] !== '[' && $input[$i+1] !== ']') { if ($inBrackets) { return false; } else { $found = true; } } } return $found; } function doesSupportSSL($input) { $length = strlen($input); $inBrackets = false; $in = []; $out = []; for ($i = 0 ; $i < $length - 2 ; $i++) { if ($input[$i] === '[' || $input[$i] === ']') { $inBrackets = !$inBrackets; } if($input[$i] === $input[$i+2] && $input[$i] !== $input[$i+1] && $input[$i] !== '[' && $input[$i] !== ']' && $input[$i+1] !== '[' && $input[$i+1] !== ']') { if ($inBrackets) { $in[] = $input[$i+1].$input[$i].$input[$i+1]; } else { $out[] = substr($input, $i, 3); } } } return count(array_intersect($in, $out)) > 0; } $data_raw = 'wysextplwqpv ... lonkut'; $data = explode("\n", $data_raw); $numberOfTLS = 0; $numberOfSSL = 0; foreach ($data as $input) { if (doesSupportTLS($input)) { $numberOfTLS++; } if (doesSupportSSL($input)) { $numberOfSSL++; } } echo "Number of TLS supporting IPs is $numberOfTLS.<br>\n"; echo "Number of SSL supporting IPs is $numberOfSSL.<br>\n"; Optimalizace by se dala provádět určitě na řádku 51, ale jelikož vstup je malý, tohle byla rychlá varianta. |
||
RastyAmateur Profil |
Aha, takže má domněnka, že následující script (java) projede všechny možné nalezené matche je nesprávný?
public class IP { private Pattern p4 = Pattern.compile("(\\w)(\\w)\\1(.*?)\\2\\1\\2"); public boolean supportsSSL() { Matcher m = p4.matcher(address); while (m.find()) { System.out.println(m.group(1) + m.group(2) + m.group(1)); if ((countStringsInString("[", m.group(3)) + countStringsInString("]", m.group(3))) % 2 == 1 && !m.group(1).equals(m.group(2))) { return true; } } return false; } } Teď tu na to koukám a ten cyklus opravdu neprojede vše. Tento kód jsem psal asi před třemi měsíci, teď jsem se k němu pouze vrátil. Nevím, z jakého důvodu jsem si myslel, že to projede všechny možné varianty... :/ |
||
Keeehi Profil |
Vyzkoušet to jde na stringu
abaxcdc[dcd]bab .
|
||
RastyAmateur Profil |
#10 · Zasláno: 18. 11. 2017, 23:28:59
Keeehi:
Tak to mi ale dost mrzí, že tudy cesta nevede. Konzultoval jsem to s kamarádem a pevně jsem mu tvrdil, jak to přes ty reguláry jednou zvládnu :D No nic, co se dá dělat, budu muset vymyslet něco jiného :) Samosebou oboum děkuji za pomoc, třeba jsem i Keeehiho přivedl k nějaké zajímavé "zábavě". Troufám si hádat, že toto nebyl jediný úkol, který jsi si vyzkoušel :D |
||
Tomáš K. Profil * |
#11 · Zasláno: 19. 11. 2017, 00:31:54
RastyAmateur:
Potřebuješ, aby mezi těmi trojicemi byla jedna hranatá závorka, to se v regulárním výrazu dá vyjádřit. |
||
Keeehi Profil |
#12 · Zasláno: 19. 11. 2017, 01:47:56
Tomáš K.:
Až na to, že je možnost, že je ten výraz nejdříve v závorce a pak až za závorkou. Tudíž druhá možnost je, že je tam jedna uzavírací závorka. A pak je tu taky možnost, že je až v druhé závorce. V takovém případě je tam otevírací, uzavírací a zase otevírací. Atd. Těch možností je spousta. No, ale dá se to popsat regulárním výrazem. Jen to není nic hezkého. ~(?:(\w)(\w)\1\w*(?:\[\w*\]\w*)*\[\w*\2\1\2)|(?:(\w)(\w)\3\w*\](?:\w*\[\w*\])*\w*\4\3\4)~U |
||
Časová prodleva: 6 let
|
0