IBM Ponder This March 2021 Challenge

grid.txt

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

rover.jl

# https://www.research.ibm.com/haifa/ponderthis/challenges/March2021.html

using DelimitedFiles
using JuMP, GLPK

function readgrid(filename)
    open(filename) do f
        parse.(Int, readdlm(f, String); base=16) .- 128
    end
end

function optimalset(grid)
    n = size(grid, 1)
    model = Model(GLPK.Optimizer)
    @variable(model, x[1:n, 1:n], Bin)
    for i = 2:n, j = 1:n
        if j > 1
            @constraint(model, x[i, j] <= x[i-1, j-1])
        end
        @constraint(model, x[i, j] <= x[i-1, j])
        if j < n
            @constraint(model, x[i, j] <= x[i-1, j+1])
        end
    end
    @objective(model, Max, sum(grid[i, j] * x[i, j] for i = 1:n, j = 1:n))

    optimize!(model)
    obj = Int(objective_value(model))
    indices = Tuple.(findall(value.(x) .> 0))
    indices = sort([(a-1, b-1) for (a, b) = indices])
    obj, indices
end

for filename = ["test.txt", "grid.txt"]
    grid = readgrid(filename)
    obj, indices = optimalset(grid)
    println(obj)
    println(indices)
end

test.txt

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