Puzzle
7 minute read

Ponder This Challenge - March 2021 - Perseverance rover

While the real Perseverance rover is having fun on Mars, we imagine an alternative version that scouts out an NxN grid of Mars according to the following rules:

  1. Surveying a cell is possible only if all its upper neighbors were already explored. The upper neighbors of (a,b) are defined as (a-1,b-1), (a-1,b), (a-1,b+1). Cells that are not on the NxN grid do not need to be surveyed first.
  2. Each cell has a "score" between 0-255 points, indicating how valuable it is to explore it.
  3. Exploring a cell also requires rover maintenance, equivalent to a "cost" of 128 points.

The goal of the rover is to earn the maximum score possible from the grid. This means choosing which cells to explore that satisfy condition 1, such that the total score gained, considering 2 and 3, is the maximum score possible.

We represent the grid as an NxN array of numbers given in hexadecimal format.
As an example, consider the following 4x4 grid representation:

13 92 49 EC
BD 31 E8 FF
09 DD BE DE
C9 5A 1D 36

Which represents the following grid (the arrow A->B means "Exploring A is a prerequisite to exploring B"):

For example, the value -109 in cell (0,0) is obtained by converting 13 in hexadecimal notion to 16+3=19 and subtracting 128, obtaining -109.
Similarly, the value 18 in (0,1) is obtained by converting 92 to 9*16+2=146 and subtracting 128.

For the grid above, the optimal score is 424, and can be achieved via the following set:

[(0, 0), (0, 1), (0, 2), (0, 3), (1, 0), (1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3)]

Your goal: Find the maximum score and a set of cells achieving it for the following 20x20 grid:

BC E6 56 29 99 95 AE 27 9F 89 88 8F BC B4 2A 71 44 7F AF 96
72 57 13 DD 08 44 9E A0 13 09 3F D5 AA 06 5E DB E1 EF 14 0B
42 B8 F3 8E 58 F0 FA 7F 7C BD FF AF DB D9 13 3E 5D D4 30 FB
60 CA B4 A1 73 E4 31 B5 B3 0C 85 DD 27 42 4F D0 11 09 28 39
1B 40 7C B1 01 79 52 53 65 65 BE 0F 4A 43 CD D7 A6 FE 7F 51
25 AB CC 20 F9 CC 7F 3B 4F 22 9C 72 F5 FE F9 BF A5 58 1F C7
EA B2 E4 F8 72 7B 80 A2 D7 C1 4F 46 D1 5E FA AB 12 40 82 7E
52 BF 4D 37 C6 5F 3D EF 56 11 D2 69 A4 02 0D 58 11 A7 9E 06
F6 B2 60 AF 83 08 4E 11 71 27 60 6F 9E 0A D3 19 20 F6 A3 40
B7 26 1B 3A 18 FE E3 3C FB DA 7E 78 CA 49 F3 FE 14 86 53 E9
1A 19 54 BD 1A 55 20 3B 59 42 8C 07 BA C5 27 A6 31 87 2A E2
36 82 E0 14 B6 09 C9 F5 57 5B 16 1A FA 1C 8A B2 DB F2 41 52
87 AC 9F CC 65 0A 4C 6F 87 FD 30 7D B4 FA CB 6D 03 64 CD 19
DC 22 FB B1 32 98 75 62 EF 1A 14 DC 5E 0A A2 ED 12 B5 CA C0
05 BE F3 1F CB B7 8A 8F 62 BA 11 12 A0 F6 79 FC 4D 97 74 4A
3C B9 0A 92 5E 8A DD A6 09 FF 68 82 F2 EE 9F 17 D2 D5 5C 72
76 CD 8D 05 61 BB 41 94 F9 FD 5C 72 71 21 54 3F 3B 32 E6 8F
45 3F 00 43 BB 07 1D 85 FC E2 24 CE 76 2C 96 40 10 FB 64 88
FB 89 D1 E3 81 0C E1 4C 37 B2 1D 60 40 D1 A5 2D 3B E4 85 87
E5 D7 05 D7 7D 9C C9 F5 70 0B 17 7B EF 18 83 46 79 0D 49 59

Supply your solution as a number and a list of cells, given in the exact format above of a Python list of tuples (between the opening and closing brackets, each cell is listed as "(a,b)", with a,b as comma-separated integers).

A bonus '*' will be given for supplying a 5x5 grid, given in the same hexadecimal format as above, which maximizes the total number of distinct scores that can be obtained by sets of cells satisfying condition 1 (if a cell is present, so are its upper neighbors).

Solution

  • The optimal score is 1424, and can be achieved via the following set:
    [(0, 0), (0, 1), (0, 2), (0, 3), (0, 4), (0, 5), (0, 6), (0, 7), (0, 8), (0, 9), (0, 10), (0, 11), (0, 12), (0, 13), (0, 14), (0, 15), (0, 16), (0, 17), (0, 18), (0, 19), (1, 0), (1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (1, 7), (1, 8), (1, 9), (1, 10), (1, 11), (1, 12), (1, 13), (1, 14), (1, 15), (1, 16), (1, 17), (1, 18), (1, 19), (2, 0), (2, 1), (2, 2), (2, 3), (2, 4), (2, 5), (2, 6), (2, 7), (2, 8), (2, 9), (2, 10), (2, 11), (2, 12), (2, 13), (2, 14), (2, 15), (2, 16), (2, 17), (2, 18), (2, 19), (3, 0), (3, 1), (3, 2), (3, 3), (3, 4), (3, 5), (3, 6), (3, 7), (3, 8), (3, 9), (3, 10), (3, 11), (3, 12), (3, 13), (3, 14), (3, 15), (3, 16), (3, 17), (3, 18), (4, 0), (4, 1), (4, 2), (4, 3), (4, 4), (4, 5), (4, 6), (4, 7), (4, 8), (4, 9), (4, 10), (4, 11), (4, 12), (4, 13), (4, 14), (4, 15), (4, 16), (4, 17), (5, 0), (5, 1), (5, 2), (5, 3), (5, 4), (5, 5), (5, 6), (5, 7), (5, 8), (5, 9), (5, 10), (5, 11), (5, 12), (5, 13), (5, 14), (5, 15), (5, 16), (6, 0), (6, 1), (6, 2), (6, 3), (6, 4), (6, 5), (6, 6), (6, 7), (6, 8), (6, 9), (6, 12), (6, 14), (6, 15), (7, 0), (7, 1), (7, 2), (7, 4), (7, 7), (8, 0), (8, 1), (9, 0)]

    This is the so-called "Closure problem", which can be solved by using optimal flow algorithms; one can also use dynamic programming or SAT-solvers.

    For the "*" part, 340 distinct values can be achieved (this is equal to the number of distinct possible sets), for example using this board:

    FC 02 2B C5 3E
17 4B CE F9 A3
DD B8 84 AF 80
30 D5 B6 6C F5
E7 B2 EB EA 1E

Solvers

  • *Walter Sebastian Gisler (28/2/2021 5:43 PM IDT)
  • Rob Pratt (28/2/2021 6:25 PM IDT)
  • Guillaume Escamocher (28/2/2021 7:53 PM IDT)
  • *Uoti Urpala (28/2/2021 8:16 PM IDT)
  • Fei Xie (28/2/2021 8:41 PM IDT)
  • *Evert van Dijken (28/2/2021 10:12 PM IDT)
  • *Florian Fischer (1/3/2021 12:31 AM IDT)
  • *Alper Halbutogullari (1/3/2021 4:01 AM IDT)
  • *Joaquim Neves Carrapa (1/3/2021 10:35 AM IDT)
  • Ilya Tarygin (1/3/2021 11:42 AM IDT)
  • Christopher Marks (1/3/2021 2:33 PM IDT)
  • *Reda Kebbaj (1/3/2021 2:35 PM IDT)
  • *Michał Franczak (1/3/2021 3:08 PM IDT)
  • *Andreas Stiller (1/3/2021 7:19 PM IDT)
  • *Dominik Reichl (1/3/2021 8:09 PM IDT)
  • *Bert Dobbelaere (1/3/2021 9:16 PM IDT)
  • *Max Alekseyev (1/3/2021 10:48 PM IDT)
  • *Latchezar Christov (1/3/2021 11:47 PM IDT)
  • *Victor Chang (2/3/2021 5:18 AM IDT)
  • *Phil Proudman (2/3/2021 3:32 PM IDT)
  • Paul Shaw (2/3/2021 6:16 PM IDT)
  • *Giuliano Bertoletti ("*" only) (2/3/2021 6:34 PM IDT)
  • Yasodhar Patnaik (2/3/2021 11:56 PM IDT)
  • Florian Sikora (3/3/2021 1:36 AM IDT)
  • *Vladimir Volevich (3/3/2021 2:36 PM IDT)
  • Graham Hemsley (3/3/2021 4:24 PM IDT)
  • Benjamin Phillabaum (3/3/2021 10:28 PM IDT)
  • JJ Rabeyrin (4/3/2021 1:53 AM IDT)
  • *Chuck Carroll (4/3/2021 5:12 AM IDT)
  • Michael Liepelt (4/3/2021 9:36 AM IDT)
  • *Dan Dima (4/3/2021 11:42 AM IDT)
  • *Lazar Ilic (4/3/2021 6:24 PM IDT)
  • *Paul Revenant (4/3/2021 7:37 PM IDT)
  • *Keith Schneider (4/3/2021 8:13 PM IDT)
  • Gary M. Gerken (4/3/2021 9:43 PM IDT)
  • *Asaf Zimmerman (4/3/2021 10:54 PM IDT)
  • Willem Hendriks (4/3/2021 11:06 PM IDT)
  • Dieter Beckerle (5/3/2021 10:20 AM IDT)
  • John Tromp (5/3/2021 2:36 PM IDT)
  • Alex Fleischer (5/3/2021 5:56 PM IDT)
  • Daniel Chong Jyh Tar (5/3/2021 6:09 PM IDT)
  • *Daniel Bitin (5/3/2021 8:17 PM IDT)
  • Burak Boyaci (6/3/2021 12:53 AM IDT)
  • Soonho You (6/3/2021 12:41 PM IDT)
  • Lorenz Reichel (6/3/2021 1:36 PM IDT)
  • *Bertram Felgenhauer (6/3/2021 4:16 PM IDT)
  • Reiner Martin (7/3/2021 6:31 PM IDT)
  • *Amos Guler (7/3/2021 7:31 PM IDT)
  • *Simeon Krastnikov (7/3/2021 9:18 PM IDT)
  • *Chris Shannon (8/3/2021 6:43 AM IDT)
  • *David Greer (8/3/2021 4:39 PM IDT)
  • Liubing Yu (9/3/2021 10:29 AM IDT)
  • *Kamil Jarosz (9/3/2021 8:51 PM IDT)
  • Andrew Mullins (9/3/2021 9:18 PM IDT)
  • Arne Vik (10/3/2021 1:45 AM IDT)
  • Govind Jujare (10/3/2021 5:06 AM IDT)
  • David Keyes (10/3/2021 5:21 AM IDT)
  • Nir Drucker (10/3/2021 11:41 AM IDT)
  • *Andy Greig (11/3/2021 10:53 PM IDT)
  • Xavier Gandibleux (12/3/2021 11:26 AM IDT)
  • Albert Stadler (12/3/2021 1:29 PM IDT)
  • Andreas Knüpfer (12/3/2021 6:32 PM IDT)
  • Almog Yair (12/3/2021 6:55 PM IDT)
  • Jim Clare (13/3/2021 12:49 AM IDT)
  • Christoph Schmidt (13/3/2021 6:52 PM IDT)
  • Christian Pape (14/3/2021 12:25 PM IDT)
  • Clive Tong (14/3/2021 1:26 PM IDT)
  • Steven Langerwerf & Susan Brommer (14/3/2021 6:28 PM IDT)
  • Gundars Kokts (14/3/2021 8:45 PM IDT)
  • *Shouky Dan & Tamir Ganor (14/3/2021 9:06 PM IDT)
  • *Marco Bellocchi (15/3/2021 12:39 AM IDT)
  • *Govind Jujare (15/3/2021 1:56 AM IDT)
  • Michael Schuresko (15/3/2021 4:28 AM IDT)
  • Julius Barth (15/3/2021 9:08 AM IDT)
  • *Kai Guttmann (15/3/2021 9:41 PM IDT)
  • Dipto Thakurta (16/3/2021 4:54 AM IDT)
  • *Motty Porat (18/3/2021 1:50 AM IDT)
  • Hakan Summakoğlu (18/3/2021 11:40 PM IDT)
  • *James Muir (20/3/2021 4:07 PM IDT)
  • Nicolas Lopez (20/3/2021 7:03 PM IDT)
  • *Hansraj Nahata (21/3/2021 3:04 AM IDT)
  • Boris Silantev (22/3/2021 5:17 PM IDT)
  • *Nyles Heise (25/3/2021 4:46 AM IDT)
  • Hans Kodde (25/3/2021 7:12 PM IDT)
  • Xavier Nodet (26/3/2021 5:27 PM IDT)
  • Gil Citro (27/3/2021 3:22 PM IDT)
  • David F.H. Dunkley (29/3/2021 3:24 AM IDT)
  • *Eden Saig (29/3/2021 2:02 PM IDT)
  • Filippos Christou (30/3/2021 10:23 PM IDT)
  • Pieter Vandercammen (31/3/2021 1:01 AM IDT)
  • *Oscar Volpatti (31/3/2021 8:04 AM IDT)
  • Thomas Pircher (31/3/2021 10:33 AM IDT)
  • Radu-Alexandru Todor (1/4/2021 12:01 AM IDT)
  • Muralidhar Seshadri (1/4/2021 7:23 AM IDT)
  • Dimitri Lozeve (1/4/2021 6:08 PM IDT)
  • Todd Will (1/4/2021 9:40 PM IDT)
  • Markó Horváth (2/4/2021 10:05 AM IDT)
  • Fabio Filatrella (2/4/2021 11:13 AM IDT)
  • Li Li (4/4/2021 8:28 AM IDT)

Related posts