Mid-Contest Analysis: Gerrymander contest

Posted by Matthew Simoneau,

Mid-Contest Analysis: Gerrymander contest

By Lucio Cetto

In this analysis we briefly consider some of the entries submitted so far. We will visualize the results for a few small hand-crafted problems.

Four entries are shown here:

  • Ken Crounse’s “Mg3Si2O5(OH)4″, winner of the Darkness phase
  • Klaas Hartmann’s “Kristine”, winner of the Twilight phase
  • MR Keenan’s “Kopt Kristine 1″, winner of the Early Bird prize
  • Christian Ylamaki’s “yet another pattern 3a3b54 cy14″, winner of the Big Sunday Push.

 

Contents

Small problem with exact solution

When the size of the matrix is small, the snake algorithms do well. This is generally the case for all the small problems in the test suite.

load testsuite_sample

M=testsuite(3).map;
N=testsuite(3).n;
S = [3     3     3     4     4     1     1
     3     3     3     4     1     1     1
     3     3     4     4     1     1     1
     2     2     5     5     5     5     5
     2     2     5     5     5     5     5
     2     2     5     5     5     5     5];

mat3d(s16527(M,N),M,[0 0 200 200],0.8)
axis off; view([30 25]);
title({'''Mg3Si2O5(OH)4''';'by GreatRumpuscat'})

figure
mat3d(s16762(M,N),M,[0 0 200 200],0.8)
axis off; view([30 25]);
title('''Kristine'' by Klaas Hartmann')

figure
mat3d(s16762(M,N),M,[0 0 200 200],0.8)
axis off; view([30 25]);
title('''Kopt Kristine 1'' by MR Keenan')

figure
mat3d(s17321(M,N),M,[0 0 200 200],0.8)
axis off; view([30 25]);
title({'''yet another pattern 3a3b54 cy14''';'by christian ylamaki'})

Simple case not caught by any algorithm

This example has an exact solution that no algorithm (so far) detects.

S = [ 1 1 1 1 1 1 1 2 2 2 2 2 2
      1 1 1 1 1 1 1 2 2 2 2 2 2
      1 1 1 1 1 1 1 2 2 2 2 2 2
      1 1 1 1 1 1 1 2 2 2 2 2 2
      1 1 1 1 1 1 1 2 2 2 2 2 2
      3 3 3 3 4 4 4 2 2 2 2 2 2
      3 3 3 3 4 4 4 2 2 2 2 2 2
      3 3 3 3 4 4 4 2 2 2 2 2 2
      3 3 3 3 5 5 5 5 5 5 5 5 5
      3 3 3 3 5 5 5 5 5 5 5 5 5
      3 3 3 3 5 5 5 5 5 5 5 5 5
      3 3 3 3 5 5 5 5 5 5 5 5 5];
N = 5;
M = zeros(size(S));
for i=1:N,
    m= (S==i);
    M(m) = (pi^9)/sum(m(:));
end

figure
mat3d(S,M,[0 0 400 300],.9)
axis off; view([30 25]);
title({'Exact solution';...
    sprintf('Percentage pop misplaced: %0.5f ',grade(M,N,S))})

figure
S = s16527(M,N);
mat3d(S,M,[0 0 400 300],0.95)
axis off; view([30 25]);
title({'Mg3Si2O5(OH)4';'by GreatRumpuscat';...
    sprintf('Percentage pop misplaced: %0.5f ',grade(M,N,S))})

figure
S = s16762(M,N);
mat3d(S,M,[0 0 400 300],0.95)
axis off; view([30 25]);
title({'Kristine by Klaas Hartmann';...
    sprintf('Percentage pop misplaced: %0.5f ',grade(M,N,S))})

figure
S = s16762(M,N);
mat3d(S,M,[0 0 400 300],0.95)
axis off; view([30 25]);
title({'Kopt Kristine 1 by MR Keenan';...
    sprintf('Percentage pop misplaced: %0.5f ',grade(M,N,S))})

figure
S = s17321(M,N);
mat3d(S,M,[0 0 400 300],0.95)
axis off; view([30 25]);
title({'yet another pattern 3a3b54 cy14';'by christian ylamaki';...
    sprintf('Percentage pop misplaced: %0.5f ',grade(M,N,S))})
s =

  307.5542

Non-convex district areas

This is similar to the last example, but with non-convex districts. A growing algorithm may find this partition, whereas the snake approach never will.

S = [ 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2
      1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 4 4 4
      5 5 5 5 4 4 1 1 1 3 3 3 3 3 2 2 4 4 4
      5 5 5 5 4 4 1 1 1 3 3 3 3 3 2 2 4 4 4
      5 5 5 5 4 4 1 1 1 3 3 3 3 3 1 1 4 4 4
      5 5 4 4 4 4 1 1 1 3 3 3 3 3 1 1 4 6 6
      5 5 4 4 4 4 1 1 1 1 1 1 1 1 1 1 4 6 6
      5 5 5 5 4 4 4 4 4 4 4 4 4 4 4 4 4 6 6
      5 5 5 5 4 4 4 4 4 4 4 4 4 4 4 4 4 6 6];
N = 6;
M = zeros(size(S));
for i=1:N,
    m= (S==i);
    M(m) = 333/sum(m(:));
end

figure
mat3d(S,M,[0 0 400 300],.9)
axis off; view([30 25]);
title({'Exact solution';...
    sprintf('Percentage pop misplaced: %0.5f ',grade(M,N,S))})

figure
S = s16527(M,N);
mat3d(S,M,[0 0 400 300],0.95)
axis off; view([30 25]);
title({'Mg3Si2O5(OH)4';'by GreatRumpuscat';...
    sprintf('Percentage pop misplaced: %0.5f ',grade(M,N,S))})

figure
S = s16762(M,N);
mat3d(S,M,[0 0 400 300],0.95)
axis off; view([30 25]);
title({'Kristine by Klaas Hartmann';...
    sprintf('Percentage pop misplaced: %0.5f ',grade(M,N,S))})

figure
S = s16762(M,N);
mat3d(S,M,[0 0 400 300],0.95)
axis off; view([30 25]);
title({'Kopt Kristine 1 by MR Keenan';...
    sprintf('Percentage pop misplaced: %0.5f ',grade(M,N,S))})

figure
S = s17321(M,N);
mat3d(S,M,[0 0 400 300],0.95)
axis off; view([30 25]);
title({'yet another pattern 3a3b54 cy14';'by christian ylamaki';...
    sprintf('Percentage pop misplaced: %0.5f ',grade(M,N,S))})

Randomly created partition

We created an algorithm which creates random partitions. Then we populated each partition with exactly equal groups. Even though the regions are usually convex, the current algorithms have a hard time finding the optimal solution.

load example1

figure
mat3d(flipud(S),flipud(M),[0 0 400 300],.9)
axis off; view([30 25]);
title({'Exact solution';...
    sprintf('Percentage pop misplaced: %0.5f ',grade(M,N,S))})

figure
S = s16527(M,N);
mat3d(flipud(S),flipud(M),[0 0 400 300],0.98)
axis off; view([30 25]);
title({'Mg3Si2O5(OH)4';'by GreatRumpuscat';...
    sprintf('Percentage pop misplaced: %0.5f ',grade(M,N,S))})

figure
S = s16762(M,N);
mat3d(flipud(S),flipud(M),[0 0 400 300],0.98)
axis off; view([30 25]);
title({'Kristine by Klaas Hartmann';...
    sprintf('Percentage pop misplaced: %0.5f ',grade(M,N,S))})

figure
S = s16762(M,N);
mat3d(flipud(S),flipud(M),[0 0 400 300],0.98)
axis off; view([30 25]);
title({'Kopt Kristine 1 by MR Keenan';...
    sprintf('Percentage pop misplaced: %0.5f ',grade(M,N,S))})

figure
S = s17321(M,N);
mat3d(flipud(S),flipud(M),[0 0 400 300],0.98)
axis off; view([30 25]);
title({'yet another pattern 3a3b54 cy14';'by christian ylamaki';...
    sprintf('Percentage pop misplaced: %0.5f ',grade(M,N,S))})

Published with MATLAB® 7.0

Comments are closed.

These postings are the author's and don't necessarily represent the opinions of MathWorks.