J

Implementing flood fill or something like that would have been smart, so I didn’t do that. Instead I used a sparse-but-still-way-too-big-and-slow block matrix representation, which takes several minutes to compute the region partitions for the real problem. The rest is essentially simple, although counting edges has some picky details. The result is a lot of code though – way more than has been typical up to now.

data_file_name =: '12.data'
grid =: ,. > cutopen fread data_file_name
data =: , grid
'rsize csize' =: $ grid
size =: # data
inbounds =: monad : '(*/ y >: 0 0) * (*/ y < rsize, csize)'
coords =: ($ grid) & #:
uncoords =: ($ grid) & #.
neighbors =: monad : 'uncoords (#~ inbounds"1) (coords y) +"1 (4 2 $ 1 0 0 1 _1 0 0 _1)'
components =: 1 ((i.size) ,. i.size)} 1 $. (size, size); (0 1); 0
NB. fuse (m, n) fuses together the components of linear indices m and n onto the
NB. lesser of the two
fuse =: monad define
   fused_row =. >./ y { components
   NB. 4 $. is a version of 1 I. that works on sparse arrays: it gives us the index array,
   NB. but it's rows of index vectors so we have to transpose to get just the column indices
   fused_indices =. {. |: 4 $. fused_row
   components =: 1 (, fused_indices (< @: ,"0/) fused_indices)} components
)
NB. fuse_all fuses all adjacent pairs of cells according to the grid contents; this makes
NB. a "block diagonal" matrix of 1's where the block index groups are components
fuse_cols =: monad define
   for_r. i. rsize do.
      for_c. i. <: csize do.
         n =. uncoords (r, c)
         pair =. n, n + 1
         if. =/ (pair { data) do. fuse pair end.
      end.
   end.
   components
)
NB. To speed this up we only execute fusion once on each pair of adjacent contiguous groups,
NB. since each row has already had its columns fused.
fuse_rows =: monad define
   for_r. i. <: rsize do.
      cur_cell =. a:
      in_group =. 0
      for_c. i. csize do.
         n =. uncoords (r, c)
         if. cur_cell ~: n { data do.
            cur_cell =. n { data
            in_group =. 0
         end.
         pair =. n, n + csize
         if. =/ (pair { data) do.
            if. in_group = 1 do. continue.
            else.
               fuse pair
               in_group =. 1
            end.
         else. in_group =. 0 end.
      end.
   end.
   components
)
fuse_all =: fuse_rows @: fuse_cols
NB. count_edges n counts the number of fenced edges, which is 4 minus the number of neighbor
NB. cells in the same component
component_neighbors =: monad : '(#~ ((= & (y { data)) @: ({ & data))) neighbors y'
count_edges =: monad : '4 - # component_neighbors y'
NB. components component_index n gives the least cell index in n's component
component_index =: dyad : '<./ {. |: 4 $. y { x'
NB. distinct components gives the list of component indices
distinct_components =: monad : '~. 0 $. y component_index"_ 0 i.size'
NB. components component_cells m gives the cell list of component m
component_cells =: dyad : 'I. 0 $. y { x'"_ 0
NB. components area m gives the area of component m
area =: (# @: component_cells)"_ 0
NB. components perimeter m gives the perimeter of component m
perimeter =: (+/ @: (count_edges"0) @: component_cells)"_ 0
components =: fuse_all components
result1 =: +/ components (area * perimeter) distinct_components components

NB. cell edges are given coordinates as follows: horizontal edges are numbered according to the
NB. cell they are above, so [0..rsize] x [0..csize), and vertical edges are numbered according to
NB. the cell they are left of, so [0..rsize) x [0..csize]. Two adjacent (connected) cell edges
NB. belong to the same component edge if they have a component cell on the same side.
NB. cell_edges m gives the edge coordinates in the schema above of the cell with linear index m,
NB. as a boxed list horizontal_edges;vertical_edges.
cell_edges =: monad define
   'r c' =. coords y
   neighbors =. component_neighbors y
   horiz_edges =. (-. ((y - csize), y + csize) e. neighbors) # 2 2 $ r, c, (>: r), c
   vert_edges =. (-. ((<: y), >: y) e. neighbors) # 2 2 $ r, c, r, >: c
   horiz_edges ; vert_edges
)
NB. cells hconnected r c1 c2 if (r, c1) and (r, c2) are horizontally connected edges
hconnected =: dyad define
   'r c1 c2' =. y
   if. 1 < c2 - c1 do. 0 return. end.
   if. (0 = r) +. rsize = r do. 1 return. end.
   upper_neighbors =. (uncoords"1) 2 2 $ (<: r), c1, (<: r), c2
   lower_neighbors =. (uncoords"1) 2 2 $ r, c1, r, c2
   (*/ upper_neighbors e. x) +. (*/ lower_neighbors e. x)
)
NB. cells vconnected c r1 r2 if (r1, c) and (r2, c) are vertically connected edges
vconnected =: dyad define
   'c r1 r2' =. y
   if. 1 < r2 - r1 do. 0 return. end.
   if. (0 = c) +. csize = c do. 1 return. end.
   left_neighbors =. (uncoords"1) 2 2 $ r1, (<: c), r2, <: c
   right_neighbors =. (uncoords"1) 2 2 $ r1, c, r2, c
   (*/ left_neighbors e. x) +. (*/ right_neighbors e. x)
)
component_edges =: dyad define
   cells =. x component_cells y
   'raw_horiz raw_vert' =. (< @: ;)"1 |: cell_edges"0 cells
   edge_pairs_of_row =. ((> @: {.) (,"0 1) ((2 & (]\)) @: > @: {:))
   horiz_edge_groups =. ({. ;/.. {:) |: raw_horiz
   new_h_edges_per_row =. (-. @: (cells & hconnected)"1 &.>) (< @: edge_pairs_of_row)"1 horiz_edge_groups
   total_h_edges =. (# horiz_edge_groups) + +/ ; new_h_edges_per_row
   vert_edge_groups =. ({: ;/.. {.) |: raw_vert
   new_v_edges_per_row =. (-. @: (cells & vconnected)"1 &.>) (< @: edge_pairs_of_row)"1 vert_edge_groups
   total_v_edges =. (# vert_edge_groups) + +/ ; new_v_edges_per_row
   total_h_edges + total_v_edges
)
result2 =: +/ components (area * (component_edges"_ 0)) distinct_components components