Autor Zpráva
RastyAmateur
Profil
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?
Poté dostanu dloooouhatánský seznam stringů:
...
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
...
A otázka zní vcelku jasně...

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
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 *
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
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
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 *
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
Buď toho sežere málo nebo toho sežere moc.


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
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 *
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
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
Všechny hvězdičky jsou ungreedy. Může za to ten modifikátor U. Jen jsem byl líný psát za každou otazník. Teda možná by fungovala i greedy varianta, na pár příkladech co jsem zkoušel fungovala i ta. Jen bývá náročnější pro program a přímo jsem nezkoumal, zda bude správně ve všech variantách.

Vaše odpověď


Prosím používejte diakritiku a interpunkci.

Ochrana proti spamu. Napište prosím číslo dvě-sta čtyřicet-sedm: