19
\$\begingroup\$

You are given an \$ 25 \times 25 \$ square lattice graph. You are to remove certain nodes from the graph as to minimize your score, based on the following scoring system:

Your score will be the \$ \text{number of nodes removed} \$ \$ + \$ the \$ \text{size of the largest connected component} \$. In the smaller \$ 4 \times 4 \$ example below, exactly \$ 5 \$ nodes have been crossed out (removed), and the size of the largest connected component is \$ 4 \$ (top and left components). Therefore the total score is \$ 9 \$.

Square lattice graph

Notes

  • You should give your score alongside a list of crossed out nodes
  • If a program was written to solve this problem, please include it in your answer if possible
  • Here is a program to check your score

This is , so the minimum score wins!

\$\endgroup\$
  • 1
    \$\begingroup\$ Out of curiosity, as someone not well versed in graph theory, is this equivalent to saying "Divide a 25x25 grid by placing obstacles in cells. Your score is the size of the largest contiguous area free of obstacles, plus the number of obstacles you placed"? \$\endgroup\$ – Steve Bennett May 7 at 2:15
  • \$\begingroup\$ @SteveBennett Yes, that is certainly another way to put it :) \$\endgroup\$ – dingledooper May 7 at 2:40
  • \$\begingroup\$ I sense an OEIS entry in this - Calculate the minimum scores for any NxN grid size. Proving optimality would be pretty challenging at higher N's though. \$\endgroup\$ – Darrel Hoffman May 7 at 19:11
13
\$\begingroup\$

92+41=133

.......X.........X.......
........X.......X........
.......X.........X.......
......X.X.......X.X......
.....X...X.....X...X.....
....X.....X...X.....X....
...X.......X.X.......X...
X.X.........X.........X.X
.X.X.......X.X.......X.X.
....X.....X...X.....X....
.....X...X.....X...X.....
......X.X.......X.X......
.......X.........X.......
......X.X.......X.X......
.....X...X.....X...X.....
....X.....X...X.....X....
.X.X.......X.X.......X.X.
X.X.........X.........X.X
...X.......X.X.......X...
....X.....X...X.....X....
.....X...X.....X...X.....
......X.X.......X.X......
.......X.........X.......
........X.......X........
.......X.........X.......

Now with 13 regions, all of 41.

Previous version 93+46=139

X...........X...........X
.X..........X..........X.
..X.........X.........X..
...X.......X.X.......X...
....X.....X...X.....X....
.....X...X.....X...X.....
......X.X.......X.X......
.......X.........X.......
......X.X.......X.X......
.....X...X.....X...X.....
....X.....X...X.....X....
...X.......X.X.......X...
XXX.........X.........XXX
...X.......X.X.......X...
....X.....X...X.....X....
.....X...X.....X...X.....
......X.X.......X.X......
.......X.........X.......
......X.X.......X.X......
.....X...X.....X...X.....
....X.....X...X.....X....
...X.......X.X.......X...
..X.........X.........X..
.X..........X..........X.
X...........X...........X

8 regions of 46, 4 regions of 41.

| improve this answer | |
\$\endgroup\$
  • 7
    \$\begingroup\$ This looks like a spider web. I guess a spider is actually minimizing the size of the holes while using as little silk as possible. \$\endgroup\$ – Arnauld May 5 at 17:00
  • 1
    \$\begingroup\$ Why do I get 185 on this? \$\endgroup\$ – the default. May 5 at 17:02
  • 1
    \$\begingroup\$ @mypronounismonicareinstate I don't know. I count 46 for the largest region (there are 8 of them) and 93 X's, total 139. \$\endgroup\$ – Level River St May 5 at 17:07
  • \$\begingroup\$ After a long examination, I found the problem: there's a cleverly hidden lowercase X. \$\endgroup\$ – the default. May 5 at 17:16
  • \$\begingroup\$ @mypronounismonicareinstate Edited. Thanks \$\endgroup\$ – Level River St May 5 at 17:18
8
\$\begingroup\$

Lower bound: 114

Notation: Add 25 points to each side of the grid to produce a 27-by-27 grid with corners missing. Call these additional 100 points \$\mathcal{E}\$. Let \$\mathcal{X}\$ denote the set of deleted points. Say the \$i\$th component has \$c_i\$ points and is bounded by \$x_i\$ members of \$\mathcal{X}\$ and by \$e_i\$ members of \$\mathcal{E}\$.

Constraints: First, components that border \$\mathcal{E}\$ border disjoint subsets of \$\mathcal{E}\$, and so

$$\sum_i e_i \leq 100.$$

Next, consider the simple polygon with vertices/perimeter at the members of \$\mathcal{X}\$ and \$\mathcal{E}\$ that border the \$i\$th component. By Pick's theorem, the area of this polygon is

$$A_i=c_i + \frac{x_i + e_i}{2} - 1.$$

Meanwhile, the octagon with \$\mathcal{E}\$ as vertices/perimeter has area 674. As such,

$$\sum_i c_i + \sum_i\Big( \frac{ x_i + e_i }{2} - 1 \Big) = \sum_i A_i \leq 674.$$

Furthermore, it is conjectured (!) that

$$\frac{ x_i + e_i }{2} - 1 \geq \frac{1}{2}\Big\lceil \sqrt{8c_i-4}\Big\rceil.$$

Optimization: In our notation, we seek to minimize \$|\mathcal{X}|+\max_i c_i\$. It is convenient to write

$$|\mathcal{X}| = 625 - \sum_i c_i.$$

We may relax our optimization to only consider the above constraints:

$$\text{minimize} \quad 625 - \sum_i c_i + \max_i c_i$$ $$\text{subject to} \quad \sum_i e_i \leq 100, \quad \sum_i c_i + \sum_i\Big( \frac{ x_i + e_i }{2} - 1 \Big) \leq 674, $$ $$\frac{ x_i + e_i }{2} - 1 \geq \frac{1}{2}\Big\lceil \sqrt{8c_i-4}\Big\rceil, \quad x,c,e \geq 0.$$

The square root makes this optimization a pain, so we further relax to a sequence of linear programs. To accomplish this, we take

$$X_k := \sum_{i:c_i=k} x_i, \quad E_k := \sum_{i:c_i=k} e_i, \quad z_k := |\{i:c_i = k\}|, \quad C := \max_i c_i.$$

Then for each \$C\in\{1,\ldots,133\}\$, we solve the linear program

$$\text{minimize} \quad 625 - \sum_k kz_k + C$$ $$\text{subject to} \quad \sum_k E_k \leq 100, \quad \sum_k kz_k + \sum_k\Big( \frac{ X_k + E_k }{2} - z_k \Big) \leq 674, $$ $$\frac{ X_k + E_k }{2} - z_k \geq \frac{1}{2}\Big\lceil \sqrt{8k-4}\Big\rceil\cdot z_k, \quad X,E,z \geq 0.$$

Indeed, we only need to consider \$C\leq 133\$ thanks to the best known solution. Here's an implementation in MATLAB using CVX:

vals=[];
for C=1:133;
    [C min(vals)]
    w = ceil(sqrt(8*(1:C)-4))/2;
    cvx_begin quiet
        variable X(C) 
        variable E(C) 
        variable z(C) 
        minimize( 625 - (1:C)*z + C )
        subject to
            sum(E) <= 100
            (1:C)*z + sum( (X+E)/2-z ) <= 674
            for ii=1:C
                (X(ii)+E(ii))/2-z(ii) >= w(ii)*z(ii)
            end
            X >= 0
            E >= 0
            z >= 0
        cvx_end
    vals(end+1)=cvx_optval;
end

The minimum value of 113.32 occurs when \$C=41\$. (Curiously, this is the size of the components in the best known solution.) Here's a plot of how the minimum varies with \$C\$:

| improve this answer | |
\$\endgroup\$
5
\$\begingroup\$

C++, score 147

Adding simulated annealing has changed the results very significantly. They are now extremely worrying.

The code:

//#define _GLIBCXX_DEBUG
#include <x86intrin.h>
#include <iostream>
#include <streambuf>
#include <bitset>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>
#include <climits>
#include <random>
#include <set>
#include <list>
#include <map>
#include <unordered_map>
#include <deque>
#include <stack>
#include <queue>
#include <string>
#include <iomanip>
#include <unordered_set>
#include <thread>

std::mt19937_64 mt;
int N = 25;
std::vector<char> cuts(N*N);
std::vector<char> marks;
int dfs(int at)
{
    char x = at % N, y = at / N;
    marks[at] = true;
    int sz = 1;
    static const char ddx[4] {1, -1, 0, 0};
    static const char ddy[4] {0, 0, 1, -1};
    for(int d = 0; d < 4; d++)
    {
        int dx = ddx[d], dy = ddy[d];
        int nx = x + dx, ny = y + dy;
        if(nx < 0 || ny < 0 || ny >= N || nx >= N) continue;
        if(marks[ny * N + nx]) continue;
        sz += dfs(ny * N + nx);
    }
    return sz;
}
bool connected(int at)
{
    char x = at % N, y = at / N;
    static const char ddx[4] {1, -1, 0, 0};
    static const char ddy[4] {0, 0, 1, -1};
    for(int d = 0; d < 4; d++)
    {
        int dx = ddx[d], dy = ddy[d];
        int nx = x + dx, ny = y + dy;
        if(nx < 0 || ny < 0 || ny >= N || nx >= N) continue;
        if(cuts[ny * N + nx]) return true;
    }
    return false;
}
int score()
{
    marks = cuts; //true -> pretend it's already cut
    int ans1 = 0, ans2 = 0;
    for(char el : cuts) ans2 += el == true;
    for(int i = 0; i < N*N; i++)
    {
        if(marks[i]) continue;
        ans1 = std::max(ans1, dfs(i));
    }
    return ans1 + ans2;
}
int main()//int64_t argc, char*argv[])
{
    int gs = 8;
    for(int y = 0; y < N; y++)
    for(int x = 0; x < N; x += gs)
        cuts[y*N+x] ^= true;
    for(int y = 0; y < N; y += gs)
    for(int x = 0; x < N; x++)
        cuts[y*N+x] ^= true;
    for(int x = 0; x < N; x++)
        cuts[x] ^= true,
        cuts[N*x] ^= true,
        cuts[N*(N-1)+x] ^= true,
        cuts[N*x+N-1] ^= true;
    //do random changes, minimizing score
    printf("%d\n", score());
    int its = 1e6;
    float temp = 1;
    for(int y = 0; y < N; y++)
    {
        for(int x = 0; x < N; x++) printf("%c", cuts[y*N+x] ? '#' : '.');
        printf("\n");
    }
    while(its --> 0)
    {
        if(its % 1000 == 0) printf("i: %d\n", its);
        temp -= 2e-6;
        int i = 0;
        do { i = mt() % (N*N); }
        while(!cuts[i] && !connected(i));
        //fun fact: do..while loops don't actually need braces
        int sb = score();
        cuts[i] ^= 1;
        int sa = score();
        int delta = sb - sa; //positive -> good
        //printf("%d\n", delta);
        if(delta <= 0 && (temp <= 0 || ldexpf(std::exp(delta / temp), 60) < mt()))
            cuts[i] ^= 1;
        else printf("%d\n", sa);
    }
    for(int y = 0; y < N; y++)
    {
        for(int x = 0; x < N; x++) printf("%c", cuts[y*N+x] ? '#' : '.');
        printf("\n");
    }
}

The output, with the starting condition being a 3x3 grid:

........#........#.......
.........#......#........
........#.......#........
.......#.......#.........
........#.......#........
........#........#.......
.......#........#........
.#....#.#......#.#...#.##
#.#.##...#...##...#.#.#..
...#......#.#....#.#.....
...........#.....#.......
..........#......#.......
.........#.......#.......
#......##........#.......
.#....#.......###........
..##.#.......#..#........
....#......##....#....#.#
.....#....#......#...#.#.
......#.##........###....
.......#.........#.......
.......#........#........
........#......#.........
.......#......#..........
.......#......#..........
.......#.....#...........
```
| improve this answer | |
\$\endgroup\$
5
\$\begingroup\$

Score 80 + 61 = 141

........X...........X....
.......X.............X...
........X...........X....
.X.......X.........X.....
X.X.......X.......X......
...X.......X.....X.......
....X.......X...X........
.....X.....X.X.X.......X.
......X...X...X.......X.X
.......X.X.....X.....X...
........X.......X...X....
.......X.........X.X.....
......X...........X......
.....X.X.........X.......
....X...X.......X........
...X.....X.....X.X.......
X.X.......X...X...X......
.X.......X.X.X.....X.....
........X...X.......X....
.......X.....X.......X...
......X.......X.......X.X
.....X.........X.......X.
....X...........X........
...X.............X.......
....X...........X........

Found with the help of this program which tells you the number of Xs and the size of each area of .s.

Previous score 89 + 54 = 143

....X...............X....
.....X.............X.....
......X...........X......
.......X.........X.......
........X...X...X........
.........XXX.XXX.........
........X.......X........
.......X.........X.......
XXXXXXX...........XXXXXXX
.......X.........X.......
.......X.........X.......
........X.......X........
.........XXXXXXX.........
........X.......X........
.......X.........X.......
.......X.........X.......
XXXXXXX...........XXXXXXX
.......X.........X.......
........X.......X........
.........XXX.XXX.........
........X...X...X........
.......X.........X.......
......X...........X......
.....X.............X.....
....X...............X....
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ It's pretty. :) \$\endgroup\$ – Steve Bennett May 7 at 2:12
4
\$\begingroup\$

Score: 158 145 141

-4 thanks to @LevelRiverSt !

.....X.............X.....
.....X.............X.....
......X...........X......
.......X.........X.......
........X.......X........
XX.......X.....X.......XX
..X.......X.X.X.......X..
...X.......X.X.......X...
....X.....X...X.....X....
.....X...X.....X...X.....
......X.X.......X.X......
.......X.........X.......
......X...........X......
.......X.........X.......
......X.X.......X.X......
.....X...X.....X...X.....
....X.....X...X.....X....
...X.......X.X.......X...
..X.......X.X.X.......X..
XX.......X.....X.......XX
........X.......X........
.......X.........X.......
......X...........X......
.....X.............X.....
.....X.............X.....

Try it online!

Number of X: 80
Largest component: 61

Divide the grid into 9 rougly equal areas of size ~60.

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ There is a way to get 80+61 by revising the spokes (more or less a rotation by 1/16 turn.) Do 2 rows of .....X.............X..... at the top then go diagonally in toward the central diamond. \$\endgroup\$ – Level River St May 6 at 23:52
  • \$\begingroup\$ @LevelRiverSt thanks! \$\endgroup\$ – Surculose Sputum May 7 at 3:47
3
\$\begingroup\$

92 + 45 = 137

......X.........X........
.......X........X........
........X........X.......
.......X.X.......X.......
......X..X......X.X......
.....X....X....X...X.....
....X......X..X.....X...X
X..X.......X.X.......X.X.
.XX.........X.........X..
...X.......X.X.......X...
....X.....X...X.....X....
.....X...X.....X...X.....
......X.X.....X.X.X......
.......X.....X...X.......
......X.....X.....X......
.....X......X......X.....
....X......X........X....
....X.....X.X........XXX.
XXXX.X...X...X......X...X
......X.X.....X....X.....
.......X.......X..X......
.......X........XX.......
........X.......X........
........X.......X........
........X.......X........

Try it online!

I started with a program, then I took the best output and hand-modified it to get this. Next I'm going to try restricting the program to only place Xs on one color of squares - that seems like it might work better. The program is written in rust. The key idea was to seed the map with a Vornoi diagram before running a simplified simulating annealing:

use rand::prelude::*;

use std::collections::{HashMap, HashSet};

fn make_neighbors(point: (usize, usize), size: usize) -> Vec<(usize, usize)> {
    let (r, c) = point;
    let mut neighbors = vec![];
    if r > 0 {
        neighbors.push((r - 1, c));
    }
    if c > 0 {
        neighbors.push((r, c - 1));
    }
    if r < size - 1 {
        neighbors.push((r + 1, c));
    }
    if c < size - 1 {
        neighbors.push((r, c + 1));
    }
    neighbors
}

fn value_board(board: &Vec<Vec<bool>>) -> usize {
    let size = board.len();
    let mut color_counts = vec![];
    let mut removed_count = 0;
    let mut seen = HashSet::new();
    for r in 0..size {
        for c in 0..size {
            if board[r][c] {
                removed_count += 1;
            } else {
                let mut color_count = 0;
                let mut flood_stack = vec![(r, c)];
                while !flood_stack.is_empty() {
                    let point = flood_stack.pop().unwrap();
                    if !board[point.0][point.1] &&!seen.contains(&point) {
                        seen.insert(point);
                        color_count += 1;
                        let neighbors = make_neighbors(point, size);
                        flood_stack.extend(neighbors);
                    }
                }
                color_counts.push(color_count);
            }
        }
    }
    let max_color_count = color_counts.into_iter().max().unwrap_or(0);
    removed_count + max_color_count
}

// TODO: make removed, neighbor_removed into VecSets.
fn simulated_annealing(input_board: &Vec<Vec<bool>>, max_steps: usize) -> Vec<Vec<bool>> {
    let size = input_board.len();
    let mut coloring: HashMap<(usize, usize), usize> = HashMap::new();
    let mut max_color = 0;
    let mut color_counts = vec![];
    let mut removed: Vec<(usize, usize)> = vec![];
    let mut neighbor_removed: Vec<(usize, usize)> = vec![];
    let mut board = input_board.clone();
    for r in 0..size {
        for c in 0..size {
            if board[r][c] {
                removed.push((r, c));
                let neighbors = make_neighbors((r, c), size);
                for point in neighbors {
                    if !board[point.0][point.1] && !neighbor_removed.contains(&point) {
                        neighbor_removed.push(point);
                    }
                }
            } else {
                if !coloring.contains_key(&(r, c)) {
                    let color = max_color;
                    max_color += 1;
                    color_counts.push(0);
                    let mut flood_stack = vec![(r, c)];
                    while !flood_stack.is_empty() {
                        let point = flood_stack.pop().unwrap();
                        if !board[point.0][point.1] && !coloring.contains_key(&point) {
                            coloring.insert(point, color);
                            color_counts[color] += 1;
                            let neighbors = make_neighbors(point, size);
                            flood_stack.extend(neighbors);
                        }
                    }
                }
            }
        }
    }
    let mut rng = thread_rng();
    for step in 0..max_steps {
        //dbg!(&removed, &neighbor_removed, &coloring, &board);
        assert_eq!(removed.len() + coloring.len(), size.pow(2));
        if rng.gen::<f64>() < 0.5  && !removed.is_empty() {
            let index = rng.gen_range(0, removed.len());
            let &(r, c) = &removed[index];
            assert!(removed.contains(&(r, c)));
            assert!(!neighbor_removed.contains(&(r, c)));
            assert!(!coloring.contains_key(&(r, c)));
            assert!(board[r][c]);
            let neighbors = make_neighbors((r, c), size);
            let neighbor_colors: HashSet<usize> = neighbors
                .iter()
                .filter_map(|n| coloring.get(n))
                .cloned()
                .collect();
            // Remove if only 1 color.
            // This will always be a neutral or improving step
            // Never remove otherwise
            if neighbor_colors.len() <= 1 {
                board[r][c] = false;
                removed.swap_remove(index);
                let neighbors = make_neighbors((r, c), size);
                for neighbor in neighbors {
                    if board[neighbor.0][neighbor.1] {
                        neighbor_removed.push((r, c));
                        break;
                    }
                }
                let new_color = if neighbor_colors.len() == 1 {
                    neighbor_colors.into_iter().next().unwrap()
                } else {
                    let new_color = max_color;
                    max_color += 1;
                    color_counts.push(0);
                    new_color
                };
                coloring.insert((r, c), new_color);
                color_counts[new_color] += 1;
            }
        } else if !neighbor_removed.is_empty() {
            let index = rng.gen_range(0, neighbor_removed.len());
            let (r, c) = neighbor_removed[index];
            let my_color = *coloring.get(&(r, c)).unwrap();
            let is_max_color = color_counts.iter().enumerate().all(|(i, &color_count)| {
                i == my_color || color_count < color_counts[my_color]
            });
            // Flip if either is a max color, in which case it's free,
            // or temp is high enough and get lucky.
            let take_action = is_max_color || {
                step < max_steps / 2 && rng.gen::<f64>() < 0.1
            };
            if take_action {
                board[r][c] = true;
                neighbor_removed.swap_remove(index);
                removed.push((r, c));
                coloring.remove(&(r, c));
                color_counts[my_color] -= 1;
                let neighbors = make_neighbors((r, c), size);
                for neighbor in neighbors {
                    if !board[neighbor.0][neighbor.1] && !neighbor_removed.contains(&neighbor) {
                        neighbor_removed.push(neighbor)
                    }
                }
            }
        }
    }
    board
}
// Given starting points and a board size, make a vornoi diagram
fn vornoi(points: &Vec<(usize, usize)>, size: usize) -> Vec<Vec<bool>> {
    let mut time_board: Vec<Vec<Option<usize>>> = vec![vec![None; size]; size];
    let mut board = vec![vec![false; size]; size];
    for (i, point) in points.iter().enumerate() {
        time_board[point.0][point.1] = Some(i);
    }
    for _ in 0..size {
        let mut new_board = time_board.clone();
        for r in 0..size {
            for c in 0..size {
                if let Some(i) = time_board[r][c] {
                    let neighbors = make_neighbors((r, c), size);
                    for (nr, nc) in neighbors {
                        if let Some(j) = new_board[nr][nc] {
                            if i != j {
                                board[r][c] = true;
                            }
                        } else {
                            new_board[nr][nc] = Some(i);
                        }
                    }
                }
            }
        }
        time_board = new_board
    }
    board
}

fn random_vornoi(num_points: usize, size: usize) -> Vec<Vec<bool>> {
    let mut points = vec![];
    let mut rng = thread_rng();
    while points.len() < num_points {
        let r = rng.gen_range(0, size);
        let c = rng.gen_range(0, size);
        if !points.contains(&(r, c)) {
            points.push((r, c))
        }
    }
    vornoi(&points, size)
}
fn print_board(board: &Vec<Vec<bool>>) {
    let string_board = board
        .iter()
        .map(|row| {
            row.iter()
                .map(|&c| if c { 'X' } else { '.' })
                .collect::<String>()
        })
        .collect::<Vec<String>>()
        .join("\n");
    println!("{}", string_board);
}
fn main() {
    let size: usize = 25;
    let reps = 100;
    let steps = 30000000;
    let mut best_points = 0;
    let mut best_board = None;
    let mut best_value = size.pow(2);
    for num_points in 8..17 {
        let mut best_board_points = None;
        let mut best_value_points = size.pow(2);
        for _ in 0..reps {
            let board = random_vornoi(num_points, size);
            let better_board = simulated_annealing(&board, steps);
            let value = value_board(&better_board);
            if value < best_value {
                best_board = Some(better_board.clone());
                best_value = value;
                best_points = num_points;
            }
            if value < best_value_points {
                best_board_points = Some(better_board);
                best_value_points = value;
            }
        }
        println!("{} {}", num_points, best_value_points);
        print_board(&best_board_points.unwrap());
        println!();
    }
    println!("{} {}", best_points, best_value);
    print_board(&best_board.unwrap());
    println!();
}

To run the program, put the above file in src/main.rs and put rand = "*" in your Cargo.toml.

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

Score: 314 313

-1 thanks to @Level River St

.X.X.X.X.X.X.X.X.X.X.X.X.
X.X.X.X.X.X.X.X.X.X.X.X.X
.X.X.X.X.X.X.X.X.X.X.X.X.
X.X.X.X.X.X.X.X.X.X.X.X.X
.X.X.X.X.X.X.X.X.X.X.X.X.
X.X.X.X.X.X.X.X.X.X.X.X.X
.X.X.X.X.X.X.X.X.X.X.X.X.
X.X.X.X.X.X.X.X.X.X.X.X.X
.X.X.X.X.X.X.X.X.X.X.X.X.
X.X.X.X.X.X.X.X.X.X.X.X.X
.X.X.X.X.X.X.X.X.X.X.X.X.
X.X.X.X.X.X.X.X.X.X.X.X.X
.X.X.X.X.X.X.X.X.X.X.X.X.
X.X.X.X.X.X.X.X.X.X.X.X.X
.X.X.X.X.X.X.X.X.X.X.X.X.
X.X.X.X.X.X.X.X.X.X.X.X.X
.X.X.X.X.X.X.X.X.X.X.X.X.
X.X.X.X.X.X.X.X.X.X.X.X.X
.X.X.X.X.X.X.X.X.X.X.X.X.
X.X.X.X.X.X.X.X.X.X.X.X.X
.X.X.X.X.X.X.X.X.X.X.X.X.
X.X.X.X.X.X.X.X.X.X.X.X.X
.X.X.X.X.X.X.X.X.X.X.X.X.
X.X.X.X.X.X.X.X.X.X.X.X.X
.X.X.X.X.X.X.X.X.X.X.X.X.

The largest connected component is of size 1.

Verify the score here: Try it online!

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ I make your score 313. 625/2 rounded up. Or alternatively add each pair of rows and you get 12*25 with an additional 13 for the odd row at the bottom. \$\endgroup\$ – Level River St May 5 at 16:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.