# Help with algorithm: calculate max possible score of DigitParty game

**URL:** <https://discourse.julialang.org/t/help-with-algorithm-calculate-max-possible-score-of-digitparty-game/98843>\
**Category:** General Usage\
**Tags:** question\
**Created:** [May 14, 2023, 5:53pm UTC](https://discourse.julialang.org/t/help-with-algorithm-calculate-max-possible-score-of-digitparty-game/98843 "2023-05-14T17:53:25Z")\
**Posts on this page:** 11\
**Page:** 1

<div class="post-metadata">

**Author:** ![natemcintosh](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/natemcintosh/32/9021_2.png) [@natemcintosh](https://discourse.julialang.org/u/natemcintosh)\
**Post date:** [May 14, 2023, 5:53pm UTC](https://discourse.julialang.org/t/help-with-algorithm-calculate-max-possible-score-of-digitparty-game/98843/1 "2023-05-14T17:53:25Z")

</div>

I created a [package](https://github.com/natemcintosh/DigitParty) that provides a programmatically playable copy of [Digit Party](https://digit.party/). The game itself is pretty simple, but has a good depth of strategy; I highly recommend playing a few games.

I need help with one part though: **calculating the maximum possible score**. Currently I just calculate the maximum possible score assuming that each instance of a given number can be connected to every other instance of that number. This is obviously not correct. Does anyone have any ideas of how to calculate this?

Also, feel free to create your own engine and see how it does!

---

<div class="post-metadata">

**Author:** ![gdalle](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/gdalle/32/27854_2.png) [@gdalle](https://discourse.julialang.org/u/gdalle)\
**Post date:** [May 14, 2023, 6:05pm UTC](https://discourse.julialang.org/t/help-with-algorithm-calculate-max-possible-score-of-digitparty-game/98843/2 "2023-05-14T18:05:23Z")

</div>

If you know all the digits in advance, which is the case when you design the instance, you can formulate it as an integer program and solve it with eg. [https://jump.dev/](https://jump.dev/)

---

<div class="post-metadata">

**Author:** ![natemcintosh](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/natemcintosh/32/9021_2.png) [@natemcintosh](https://discourse.julialang.org/u/natemcintosh)\
**Post date:** [May 14, 2023, 6:12pm UTC](https://discourse.julialang.org/t/help-with-algorithm-calculate-max-possible-score-of-digitparty-game/98843/3 "2023-05-14T18:12:01Z")

</div>

That sounds really neat! However I know almost nothing about optimization (or jump). Do you have any suggestions?

---

<div class="post-metadata">

**Author:** ![gdalle](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/gdalle/32/27854_2.png) [@gdalle](https://discourse.julialang.org/u/gdalle)\
**Post date:** [May 14, 2023, 6:50pm UTC](https://discourse.julialang.org/t/help-with-algorithm-calculate-max-possible-score-of-digitparty-game/98843/4 "2023-05-14T18:50:24Z")

</div>

JuMP’s documentation is really well-done if you only need practical knowledge: [Introduction · JuMP](https://jump.dev/JuMP.jl/stable/)  
For more theoretical aspects, I have listed some references here: [IntroJulia - LP](https://gdalle.github.io/IntroJulia/linear_programming.html)  
In particular, I think your problem is close to Sudoku, so you could use their formulation to get started: [Sudoku · JuMP](https://jump.dev/JuMP.jl/stable/tutorials/linear/sudoku/)

---

<div class="post-metadata">

**Author:** ![natemcintosh](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/natemcintosh/32/9021_2.png) [@natemcintosh](https://discourse.julialang.org/u/natemcintosh)\
**Post date:** [May 16, 2023, 1:59am UTC](https://discourse.julialang.org/t/help-with-algorithm-calculate-max-possible-score-of-digitparty-game/98843/5 "2023-05-16T01:59:58Z")

</div>

I’ve made an attempt. I believe it correctly establishes all of the constraints. However, I’m struggling with the `@objective`.

```julia
using StaticArrays
using JuMP
using HiGHS

# How the game is defined
mutable struct Game
    board :: MMatrix{5,5,Int8}
    up_next :: MVector{2,Int8}
end

function get_max_score(g::Game)
    game_is_over(g) || error("Cannot get max score before game is over")

    # Create an array that acts like a dictionary. The index is the number and the value
    # is how many times that number appeared on the board
    counts = @MVector zeros(Int, 9)
    for val in g.board
        counts[val] += 1
    end

    model = Model(HiGHS.Optimizer)
    # Create a 7x7 matrix, where the outer rows and columns are all zeros. Makes getting
    # neighbors easier
    @variable(model, x[1:7, 1:7], Int)

    # All boundaries have to be 0
    @constraint(model, bz1, x[:, 1] .== 0)
    @constraint(model, bz2, x[:, end] .== 0)
    @constraint(model, bz3, x[1, :] .== 0)
    @constraint(model, bz4, x[end, :] .== 0)

    # Need the correct number of instances of each number
    @constraints(
        model,
        begin
            correct_numbers[i = eachindex(counts)], count(==(i), x[2:6, 2:6]) == counts[i]
        end
    )

    # Hoping to use 
    # when `x[idx+dir] >= 1`, we add `x[idx]`, otherwise add 0
    # DIRS = CartesianIndex.([(1, 1), (1, 0), (1, -1), (0, 1), (0, -1), (-1, 1), (-1, 0), (-1, -1)])
    @objective(
        model,
        Max,
        sum(
            x[idx] * (1 - min(x[idx+dir], 1)) for
            idx in eachindex(IndexCartesian(), x[2:6, 2:6]) for dir in DIRS
        )
    )

    optimize!(model)
    @show termination_status(model)
    @show x
end

```

Any thoughts on how to write the objective?

---

<div class="post-metadata">

**Author:** ![natemcintosh](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/natemcintosh/32/9021_2.png) [@natemcintosh](https://discourse.julialang.org/u/natemcintosh)\
**Post date:** [May 16, 2023, 2:05am UTC](https://discourse.julialang.org/t/help-with-algorithm-calculate-max-possible-score-of-digitparty-game/98843/6 "2023-05-16T02:05:22Z")

</div>

It looks like the creators of the game [don’t yet have a great way to solve it themselves](https://twitter.com/VinceVatter/status/1658081389449756674?cxt=HHwWhIC2raSP2IIuAAAA). I asked for clarification on how they calculate the score on the site.

---

<div class="post-metadata">

**Author:** ![natemcintosh](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/natemcintosh/32/9021_2.png) [@natemcintosh](https://discourse.julialang.org/u/natemcintosh)\
**Post date:** [May 16, 2023, 2:18am UTC](https://discourse.julialang.org/t/help-with-algorithm-calculate-max-possible-score-of-digitparty-game/98843/7 "2023-05-16T02:18:25Z")

</div>

[They say](https://twitter.com/VinceVatter/status/1658293431955775490?s=20)

> We assume you can get the maximum score for every digit, and we know those. We’re well aware that this isn’t always possible, and people have shared screenshots where it doesn’t work, we just haven’t come up with a better way yet.

---

<div class="post-metadata">

**Author:** ![gdalle](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/gdalle/32/27854_2.png) [@gdalle](https://discourse.julialang.org/u/gdalle)\
**Post date:** [May 16, 2023, 6:08am UTC](https://discourse.julialang.org/t/help-with-algorithm-calculate-max-possible-score-of-digitparty-game/98843/8 "2023-05-16T06:08:37Z")

</div>

Here’s how I would write it, using the package GridGraphs.jl that I developed (be sure to install the latest version 0.9.1):

```julia
using Graphs
using GridGraphs: GridGraph, QUEEN_DIRECTIONS, index_to_coord
using HiGHS
using JuMP

d = 4 # size of the grid, vertices are named u or v
n = 9 # maximum number, numbers are named k

grid = GridGraph(ones(Int, d, d); directions=QUEEN_DIRECTIONS);
numbers = rand(1:n, d^2); # sequence of numbers (order unimportant)
numbers_count = [count(==(k), numbers) for k in 1:n];

model = Model(HiGHS.Optimizer)

# Variables: x[v, k] = 1 <-> number k on vertex v
@variable(model, x[v=1:d^2, k=1:n], Bin);
# Auxiliary variables: y[u, v, k] = x[u, k] x[v, k]
@variable(model, y[u=1:d^2, v=1:d^2, k=1:n; has_edge(grid, u, v)], Bin);

# Constraint 1: one number per vertex
@constraint(model, [v = 1:d^2], sum(x[v, :]) == 1);

# Constraint 2: as many k's as needed
@constraint(model, [k = 1:n], sum(x[:, k]) == numbers_count[k]);

# Linearization constraints: coherence between y and x
@constraint(model, [u = 1:d^2, v = 1:d^2, k = 1:n; has_edge(grid, u, v)], y[u, v, k] <= x[u, k]);
@constraint(model, [u = 1:d^2, v = 1:d^2, k = 1:n; has_edge(grid, u, v)], y[u, v, k] <= x[v, k]);
@constraint(model, [u = 1:d^2, v = 1:d^2, k = 1:n; has_edge(grid, u, v)], y[u, v, k] >= x[u, k] + x[v, k] - 1);

# Objective: sum of k xᵤₖ xᵥₖ over all k's and all edges (u, v)
@objective(model, Max, sum(k * y[src(e), dst(e), k] for k in 1:n, e in edges(grid)));

optimize!(model)

x_sol = round.(Int, value.(x))

solution = zeros(Int, d, d)
for v in vertices(grid)
    (i, j) = index_to_coord(grid, v)
    solution[i, j] = argmax(x_sol[v, :])
end

```

Here’s what we get at the end for one random instance:

```julia
julia> 1:n .=> numbers_count
9-element Vector{Pair{Int64, Int64}}:
 1 => 0
 2 => 2
 3 => 1
 4 => 2
 5 => 4
 6 => 0
 7 => 3
 8 => 3
 9 => 1

julia> solution
4×4 Matrix{Int64}:
 4 4 3 9
 8 8 5 5
 7 8 5 5
 7 7 2 2

```

It takes a VERY long time to solve for `d=5` so maybe there is a better formulation though

---

<div class="post-metadata">

**Author:** ![gdalle](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/gdalle/32/27854_2.png) [@gdalle](https://discourse.julialang.org/u/gdalle)\
**Post date:** [May 16, 2023, 6:10am UTC](https://discourse.julialang.org/t/help-with-algorithm-calculate-max-possible-score-of-digitparty-game/98843/9 "2023-05-16T06:10:15Z")

</div>

This might typically be an instance where constraint programming would work faster

---

<div class="post-metadata">

**Author:** ![gdalle](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/gdalle/32/27854_2.png) [@gdalle](https://discourse.julialang.org/u/gdalle)\
**Post date:** [May 16, 2023, 1:14pm UTC](https://discourse.julialang.org/t/help-with-algorithm-calculate-max-possible-score-of-digitparty-game/98843/10 "2023-05-16T13:14:44Z")

</div>

Also, looking at the solution, I think we can somehow relate it to bin-packing or other classical problems. A faster approach might explicitly enumerate connected regions where one can put several numbers at once.  
Here’s an example of an alternative formulation which has an exponential number of variables but should be solvable with branch & price:

\max\_{x \in \{0,1\}^{KR}} \, \sum\_k \sum\_r k |E(r)| x\_{k,r} \quad \text{s.t.} \quad \left\vert \begin{aligned} \sum\_r |V(r)| x\_{k,r} & = N\_k & \forall k \\ \sum\_k x\_{k,r} & \leq 1 & \forall r \\ \sum\_k (x\_{k,r\_1} + x\_{k,r\_2}) & \leq 1 & \forall r\_1 \cap r\_2 \end{aligned} \right.

- The index k denotes numbers from 1 to 9, while r denotes connected regions of the grid (with V(r) vertices and E(r) internal edges).
- The binary variable x\_{k,r} is equal to 1 if region r is filled with number k
- The first constraint imposes that we insert exaclty N(k) times the number k
- The second constraint ensures that a region r is occupied by at most one number k
- The third constraint enforces that two intersecting regions r\_1 and r\_2 cannot be occupied at the same time

---

<div class="post-metadata">

**Author:** ![BatyLeo](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/batyleo/32/35017_2.png) [@BatyLeo](https://discourse.julialang.org/u/BatyLeo)\
**Post date:** [May 17, 2023, 2:26pm UTC](https://discourse.julialang.org/t/help-with-algorithm-calculate-max-possible-score-of-digitparty-game/98843/11 "2023-05-17T14:26:41Z")

</div>

By using `Gurobi` instead oh `HiGHS`, your code solves the 5x5 grids in a few seconds instead of a few minutes. It also becomes slow on 6x6 grids and larger though.