De AIVD te slim af (nou ja, hun kerstpuzzel dan...) (BitFactory meetup November 2024)

Transcript

1. De AIVD te slim af Arnout Boks - BitFactory Meetup - 21 november 2024
2. De AIVD te slim af Nou ja, hun kerstpuzzel dan… Arnout Boks - BitFactory Meetup - 21 november 2024
3. AIVD kerstpuzzel
4. AIVD kerstpuzzel
5. AIVD kerstpuzzel
6. Een case study
7. Spoiler alert!
8. AIVD kerstpuzzel 2022 - opgave 15
9. Aanpak • Implementatie in PHP • Modellering • Check van mogelijke (deel-)oplossingen • Bruteforce • …?
10. Modellering - kleuren enum Color { case GREY; case YELLOW; case LIGHT_GREEN; case LIGHT_BLUE; case PURPLE; case ORANGE; case DARK_GREEN; case RED; case DARK_BLUE; case BLACK; }
11. Modellering - tegel & rotatie class Tile { public function __construct( public readonly Color $color, public readonly array $letters, public bool $hand_top, public bool $hand_right, public bool $hand_bottom, public bool $hand_left, ) {} public function rotatedCW(): self { $rotated_letters = [ $this->letters[1], $this->letters[2], $this->letters[3], $this->letters[0] ]; return new self( $this->color, $rotated_letters, $this->hand_left, $this->hand_top, $this->hand_right, $this->hand_bottom ); } public function isValidRotation(): bool { return $this->letters[0] !== null; } public function getLetter(): string { return $this->letters[0]; } }
12. Modellering - bord class Board { /** @param Tile[][] $tiles */ private function __construct ( private readonly array $tiles, ) {} public static function createEmpty (): self { $empty_board_tiles = array_fill(0, 7, array_fill(0, 4, null)); return new self ($empty_board_tiles ); } public function withTileAt(Tile $tile, int $x, int $y): self { $tiles_copy = $this->tiles; $tiles_copy [$x][$y] = $tile; return new self ($tiles_copy ); } }
13. Modellering - convenience DSL H H . H HH.H =
14. Modellering - convenience DSL M . W E M.WE =
15. Modellering - convenience DSL $tiles = [ tile("..HH", "D...", Color::GREY), tile("HH..", "EM.W", Color::YELLOW), tile("HH.H", "M.WE", Color::LIGHT_GREEN), tile(".H..", "ZNZN", Color::LIGHT_BLUE), tile("HH..", "IHIH", Color::GREY), tile("HHH.", "OOOO", Color::PURPLE), tile("H.HH", ".G..", Color::YELLOW), // ... ];
16. Check van mogelijke (deel-)oplossingen public function verify(): bool { for ($x = 0; $x < 7; $x++) { for ($y = 0; $y < 4; $y++) { if (isset($this->tiles[$x][$y])) { // Check valid rotation $tile = $this->tiles[$x][$y]; if (!$tile->isValidRotation ()) { return false ; } // Check color foreach ($this->yieldValidPositionsWithinDistanceOf ($x, $y) as [ $other_x, $other_y ]) { if (isset($this->tiles[$other_x][$other_y]) && $this->tiles[$other_x][$other_y]->color === $tile->color) { return false ; } } // ... } } } }
17. Check - anderhalve meter afstand e e e e e e e e d c b c d e e c a a a c e e b a a b e e c a a a c e e d c b c d e e e e e e e e 1.1 m 1.1 m 1.1√2 m > 1.5 m
18. Check van mogelijke (deel-)oplossingen private function yieldValidPositionsWithinDistanceOf (int $orig_x, int $orig_y): iterable { foreach ($this->yieldAllPositionsWithinDistanceOf ($orig_x, $orig_y) as [ $x, $y ]) { if ($x >= 0 && $x <= 6 && $y >= 0 && $y <= 3) { yield [ $x, $y ]; } } } private function yieldAllPositionsWithinDistanceOf (int $x, int $y): iterable { // Straight 1-distance yield [ $x - 1, $y ]; yield [ $x + 1, $y ]; yield [ $x, $y - 1 ]; yield [ $x, $y + 1 ]; // Diagonal 1-distance yield [ $x - 1, $y - 1 ]; yield [ $x + 1, $y - 1 ]; yield [ $x - 1, $y + 1 ]; yield [ $x + 1, $y + 1 ]; // ...
19. Check van mogelijke (deel-)oplossingen public function verify(): bool { for ($x = 0; $x < 7; $x++) { for ($y = 0; $y < 4; $y++) { if (isset($this->tiles[$x][$y])) { $tile = $this->tiles[$x][$y]; // ... // Check hands if ($tile->hand_left && $x > 0 && isset($this->tiles[$x - 1][$y]) && $this->tiles[$x - 1][$y]->hand_right) { return false ; } if ($tile->hand_right && $x < 6 && isset($this->tiles[$x + 1][$y]) && $this->tiles[$x + 1][$y]->hand_left) { return false ; } if ($tile->hand_top && $y > 0 && isset($this->tiles[$x][$y - 1]) && $this->tiles[$x][$y - 1]->hand_bottom) { return false ; } if ($tile->hand_bottom && $y < 3 && isset($this->tiles[$x][$y + 1]) && $this->tiles[$x][$y + 1]->hand_top) { return false ; }
20. Debugging public function dump(): string { $line_dumps = []; for ($y = 0; $y < 4; $y++) { $tile_dumps = []; for ($x = 0; $x < 7; $x++) { if (isset($this->tiles[$x][$y])) { $tile_dumps[] = $this->tiles[$x][$y]->dump(); } else { $tile_dumps[] = " "; } } $line_dumps[] = implode("", $tile_dumps); } return implode("\n", $line_dumps); }
21. Bruteforce - setup $board = Board::createEmpty(); $positions_to_fill = []; for ($y = 0; $y < 4; $y++) { for ($x = 0; $x < 7; $x++) { $positions_to_fill [] = [$x, $y]; } } bruteforce($board, $tiles, $positions_to_fill );
22. Bruteforce - rotaties van tegels function generate_rotations(Tile $tile): iterable { if ($tile->isValidRotation()) { yield $tile; } $tile1 = $tile->rotatedCW(); if ($tile1->isValidRotation() && !$tile1->equals($tile)) { yield $tile1; } $tile2 = $tile1->rotatedCW(); if ($tile2->isValidRotation() && !$tile2->equals($tile) && !$tile2->equals($tile1)) { yield $tile2; } $tile3 = $tile2->rotatedCW(); if ($tile3->isValidRotation() && !$tile3->equals($tile) && !$tile3->equals($tile1) && !$tile3->equals($tile2)) { yield $tile3; } }
23. Bruteforce - recursie function bruteforce(Board $current_board , array $remaining_tiles , array $remaining_positions ): void { [$x, $y] = array_shift($remaining_positions ); foreach ($remaining_tiles as $key => $try_tile) { $next_remaining_tiles = $remaining_tiles ; unset($next_remaining_tiles [$key]); foreach (generate_rotations ($try_tile) as $rotated_try_tile ) { $next_board = $current_board ->withTileAt($rotated_try_tile , $x, $y); if ($next_board->verify()) { if (count($remaining_positions ) === 0) { print $next_board->dump(); exit(); } else { bruteforce($next_board, $next_remaining_tiles , $remaining_positions ); } } } } }
24. Succes?
25. Succes? Het probleem Naïeve bruteforce is (zoals verwacht) véél te langzaam. De oplossing? Toevoegen van kennis om deeloplossingen eerder af te kunnen keren
26. Kennis toevoegen - locaties per kleur Geel 6 Lichtblauw 4 Paars 4 Oranje 4 Grijs 2 Lichtgroen 2 Rood 2 Donkerblauw 2 Donkergroen 1 Zwart 1
27. Kennis toevoegen - locaties per kleur Geel 6 Lichtblauw 4 Paars 4 Oranje 4 Grijs 2 Lichtgroen 2 Rood 2 Donkerblauw 2 Donkergroen 1 Zwart 1
28. Kennis toevoegen - locaties per kleur Geel 6 Lichtblauw 4 Paars 4 Oranje 4 Grijs 2 Lichtgroen 2 Rood 2 Donkerblauw 2 Donkergroen 1 Zwart 1
29. Kennis toevoegen - locaties per kleur Geel 6 Lichtblauw 4 Paars 4 Oranje 4 Grijs 2 Lichtgroen 2 Rood 2 Donkerblauw 2 Donkergroen 1 Zwart 1
30. Kan een oplossing met deze tegels beginnen? Kennis toevoegen - tekstanalyse
31. Kennis toevoegen - tekstanalyse Oplossingsrichting • Controle of de eerste reeks tegels in leesvolgorde wel een Nederlandse tekst kan zijn • Woordenlijst van OnzeTaal Dilemma • Steeds gehele woordenlijst doorlopen kost teveel tijd • Alle mogelijke prefixes van lengte X vooraf genereren kost teveel geheugen
32. Kennis toevoegen - tekstanalyse
33. Boomstructuur als index
34. Boomstructuur als index E N G ENG
35. Boomstructuur als index E N G ENG ENKEL KOE K E L K O E
36. Boomstructuur als index E N G ENG ENKEL KOE EN ENGEL ENGE K E L K O E E L
37. Boomstructuur als index E N G K E L K O E E L Kan een oplossing beginnen met ‘ENGKO’? En met ‘ENGOE’?
38. Succes?
39. Kennis toevoegen: handen vs. plaatsen Horizontaal: 5 x 7 = 35 plaatsen Verticaal: 8 x 4 = 32 plaatsen Totaal: 67 plaatsen Totaal handen: 66 handen
40. Kennis toevoegen: handen vs. plaatsen Kan een oplossing met deze tegels beginnen?
41. Kennis toevoegen: handen vs. plaatsen Kan een oplossing met deze tegels beginnen?
42. Succes?
43. Succes!
44. Wat kon er fraaier? • Tegel-prototype en geroteerde tegel van elkaar scheiden • Verificatie-code buiten de Board-klasse • Eerder handjes tellen! Hoe ‘krap’ is de puzzel eigenlijk? • Misschien wel met de hand?
45. Iteratieve aanpak werkt!
46. Netjes modelleren voorkomt fouten
47. Efficiënte algoritmen en datastructuren voor tekstanalyse
48. Help de computer met zo veel mogelijk ‘menselijke’ kennis
49. Bedankt! - Vragen? Arnout Boks @aboks@phpc.social @arnoutboks https://aboks.github.io https://www.moxio.com We’re hiring!