Upgrade to Pro — share decks privately, control downloads, hide ads and more …

Solving problems using trees

Solving problems using trees

Tree is one of the most powerful data structures, and it is present in various kinds of problems. I want to show you how trees helped me design certain solutions so that you can do the same when the right time comes.

Tomasz Kowalczyk

April 03, 2017
Tweet

More Decks by Tomasz Kowalczyk

Other Decks in Programming

Transcript

  1. AST

  2. <?php declare(strict_types=1); final class AllowedYearsValidator { public function isYearAllowed(DateTimeImmutable $dt):

    bool { $currentYear = $dt->format('Y'); $isCurrentYear = '2017' === $currentYear; return $isCurrentYear && in_array($currentYear, ['2016', '2018']); } } $validator = new AllowedYearsValidator(); $dt = DateTimeImmutable::createFromFormat('Y', '2016'); assert(false === $validator->isYearAllowed($dt));
  3. <?php declare(strict_types=1); final class AllowedYearsValidator { public function isYearAllowed(DateTimeImmutable $dt):

    bool { $currentYear = $dt->format('Y'); $isCurrentYear = '2017' === $currentYear; return $isCurrentYear && in_array($currentYear, ['2016', '2018']); } } $validator = new AllowedYearsValidator(); $dt = DateTimeImmutable::createFromFormat('Y', '2016'); assert(false === $validator->isYearAllowed($dt));
  4. <?php declare(strict_types=1); final class c0 { public function m0(DateTimeImmutable $v0):

    bool { $v1 = $v0->format('Y'); $v2 = '2017' === $v1; return $v2 && in_array($v1, ['2016', '2018']); } } $v3 = new c0(); $v0 = DateTimeImmutable::createFromFormat('Y', '2016'); assert(false === $v3->m0($v0));
  5. <?php declare(strict_types=1); final class c0 { public function m0(DateTimeImmutable $v0):

    bool { $v1 = $v0->format('Y'); $v2 = '2017' === $v1; return $v2 && in_array($v1, ['2016', '2018']); }} $v3 = new c0(); $v0 = DateTimeImmutable::createFromFormat('Y', '2016'); assert(false === $v3->m0($v0));
  6. 0 0 4 6 0 6 4 0 2 1

    3 6 7 0 4 1 7 9 6 0 1 0 9 1 9 9 1 2 8 7 3 1 4 4 start end start end start end start end
  7. 0 0 4 6 0 6 4 0 2 1

    3 6 7 0 4 1 7 9 6 0 1 0 9 1 9 9 1 2 8 7 3 1 4 4 004651 213702 961446 962001 start end start end start end start end
  8. $handlers = new HandlerContainer(); $handlers->add('foo', function(ShortcodeInterface $s) { return '<foo>'.$s->getContent().'</foo>';

    }); $handlers->add('inner', function(ShortcodeInterface $s) { return date('Y.m.d'); }); $processor = new Processor(new RegularParser(), $handlers); $text = '[foo arg=val] data [inner=x /] code [/foo]'; $expected = '<foo> data 2017.04.03 code </foo>'; assert($expected === $processor->process($text));
  9. $schemaDir = __DIR__.'/xsd'; $targetDir = __DIR__.'/xml'; $log = new NullLogger();

    $ctr = new Counter(); $fs = new FilePutContentsFilesystem($targetDir); $ns = new CustomNamespaceResolver(); $analyzer = new XsdAnalyzer($log); $schemas = $analyzer->createFromDirectories([$schemaDir]); $generator = new PrimitivePhpGenerator($fs, $ns, $log, $ctr); $generator->generate($schemas);
  10. A B C D E A requires B and C

    B requires D and E E requires F and G ...but D and E can’t confirm before B, F and G must wait for E, so... Who can vote? Did vote pass? F G
  11. A B C D E Check B and C, when

    in B check D and E, when in E check F and G… and if something failed somewhere then return all the information down. F G failed
  12. A B C D E filter root nodes filter already

    decided nodes filter already notified nodes map to contact information F G failed