Organize Halloween Candy - Hole #4

Question

See Hole #1 if you are confused.

What does every kid do after he/she collects buckets of candy over Halloween?

Sort it by type and size, of course¹!

The Challenge

Given a dumped-out bag of candy of varying shapes and sizes, sort the candy from left to right based on:

• First: The amount of candy (so 5 of one will be more left than 4 of another)
• Second (if there are any ties after the first): If the amount is the same, the candy with more internal area (based on number of characters) will rank higher.

If after the second sort there is still a tie, then you may choose either to be first.

Input

You will be given the candy through stdin; strewn about. See examples below.

Output

Output the candy ordered in the correct order. Note, candy should always be placed in very neat columns to appease your OCD fish². The candy of the same type should be placed directly under one another. See examples below.

What do you mean by "interior area"?

• The interior area of a piece of candy is measured by the total characters making up the candy as a whole.

• Any whitespace within a "border" is considered part of the area of the candy.

• A border is any connected loop of characters, each character diagonal or next to it's neighbor.

For example,

+--------+
|        |
|        |
|        |
|        |
+--------+

has more area than

XXXXXXXX
XXXXXXXX
XXXXXXXX
XXXXXXXX

even though is has less characters overall.

Examples

input:

                       _           \|            |/                                     _    
    _               lllllll        -*------------*-            -\       /-           lllllll 
 lllllll           lllllllll        |  /\  /\  / |             +|\ooooo/|+          lllllllll
lllllllll          llll+llll        | /  \/  \/  |             ||o     o||          llll+llll
llll+llll          lllllllll       -*------------*-            ||o     o||          lllllllll
lllllllll           lllllll        /|            |\            +|/ooooo\|+           lllllll 
 lllllll               |                                       -/       \-              |    
    |                  |                _                                               |    
    |   -\       /-    |             lllllll                                            |    
    |   +|\ooooo/|+    |            lllllllll                                           |    
    |   ||o     o||    |            llll+llll                                           |    
    |   ||o     o||    +            lllllllll                              rrr--rrr     +    
    +   +|/ooooo\|+                  lllllll                                rr||rr           
        -/       \-                     |                                   | || |           
                                        |                                   | || |           
                                        |                                   | || |           
                                        |                                   | || |           
                                        |            \|            |/       | || |           
                                        +            -*------------*-       | || |           
                                                      |  /\  /\  / |        | || |           
                        -\       /-                   | /  \/  \/  |        | || |           
                        +|\ooooo/|+                  -*------------*-       rr||rr           
                        ||o     o||                  /|            |\      rrr--rrr          
                        ||o     o||                                                          
                        +|/ooooo\|+                                                          
                        -/       \-                                                          

Would become

    _     \|            |/ -\       /- rrr--rrr
 lllllll  -*------------*- +|\ooooo/|+  rr||rr 
lllllllll  |  /\  /\  / |  ||o     o||  | || | 
llll+llll  | /  \/  \/  |  ||o     o||  | || | 
lllllllll -*------------*- +|/ooooo\|+  | || | 
 lllllll  /|            |\ -/       \-  | || | 
    |                                   | || | 
    |     \|            |/ -\       /-  | || | 
    |     -*------------*- +|\ooooo/|+  | || | 
    |      |  /\  /\  / |  ||o     o||  | || | 
    |      | /  \/  \/  |  ||o     o||  rr||rr 
    +     -*------------*- +|/ooooo\|+ rrr--rrr
          /|            |\ -/       \-         
    _                                          
 lllllll  \|            |/ -\       /-         
lllllllll -*------------*- +|\ooooo/|+         
llll+llll  |  /\  /\  / |  ||o     o||         
lllllllll  | /  \/  \/  |  ||o     o||         
 lllllll  -*------------*- +|/ooooo\|+         
    |     /|            |\ -/       \-         
    |                                          
    |                                          
    |                                          
    |                                          
    +                                          

    _                                          
 lllllll                                       
lllllllll                                      
llll+llll                                      
lllllllll                                      
 lllllll                                       
    |                                          
    |                                          
    |                                          
    |                                          
    |                                          
    +                                          

    _                                          
 lllllll                                       
lllllllll                                      
llll+llll                                      
lllllllll                                      
 lllllll                                       
    |                                          
    |                                          
    |                                          
    |                                          
    |                                          
    +                                          

A second example:

                   qq                                                                 \/     
                   qq                 qq      qq                                    +-----+  
                                      qq      qq         qq                       +       |  
 jjjjjjjj                                                qq         qq            |       |  
  jjjjjj             \/                                             qq      qq    |       |  
   jjjj            +-----+ <---notice that the left side is not connected   qq    +-------+  
  jj  jj         +       |       <-->       <-->                                             
 j      j        |       |                                                                   
jj  <>  jj       |       |       <-->                                 qq            jjjjjjjj 
 jj    jj        +-------+                                            qq             jjjjjj  
   jjjj                                 qq           qq                               jjjj   
                                        qq           qq                              jj  jj  
                                                                                    j      j 
                      +---------------------------------------------------------+  jj  <>  jj
      ooooo           +---------------------------------------------------------+   jj    jj 
     o     yyyyyy                                                                     jjjj   
     o           ww - notice diagonal border, allowed                                        
     o           ww                                                 jjjjjjjj                 
     o     yyyyyy          ooooo                ooooo                jjjjjj                  
      ooooo               o     yyyyyy         o     yyyyyy           jjjj                   
                          o           ww       o           ww        jj  jj                  
                          o           ww       o           ww       j      j                 
                          o     yyyyyy         o     yyyyyy        jj  <>  jj                
                           ooooo                ooooo               jj    jj                 
                                                                      jjjj                   

Solution:

qq  ooooo          jjjjjjjj  <-->     \/    +---------------------------------------------------------+
qq o     yyyyyy     jjjjjj          +-----+ +---------------------------------------------------------+
   o           ww    jjjj    <--> +       |                                                            
qq o           ww   jj  jj        |       |                                                            
qq o     yyyyyy    j      j  <--> |       |                                                            
    ooooo         jj  <>  jj      +-------+                                                            
qq                 jj    jj                                                                            
qq  ooooo            jjjj             \/                                                               
   o     yyyyyy                     +-----+                                                            
qq o           ww  jjjjjjjj       +       |                                                            
qq o           ww   jjjjjj        |       |                                                            
   o     yyyyyy      jjjj         |       |                                                            
qq  ooooo           jj  jj        +-------+                                                            
qq                 j      j                                                                            
    ooooo         jj  <>  jj                                                                           
qq o     yyyyyy    jj    jj                                                                            
qq o           ww    jjjj                                                                              
   o           ww                                                                                      
qq o     yyyyyy    jjjjjjjj                                                                            
qq  ooooo           jjjjjj                                                                             
                     jjjj                                                                              
qq                  jj  jj                                                                             
qq                 j      j                                                                            
                  jj  <>  jj                                                                           
qq                 jj    jj                                                                            
qq                   jjjj                                                                              

Note that columns have 1 character of spacing between them, and are aligned horizontally at the top. Also note that each candy is in an exact columns, each candy with 1 character of spacing in between.

Scoring

This is code-golf, so shortest program (in bytes) wins.

¹ What else would you do? Obviously you want to display your awesome might and power in the amount of candy you collected, right?

² I know what you're thinking! A fish has to look through a curved bowl at your candy, so therefore it would be distorted anyway! Well, my fish lived (before it died) in a rectangular aquarium.

Answer 1

Ruby, 928 characters

Whew, this one was fun!

w=[];b=' ';u=$<.read.split'
';k=->l,z,t,p{loop{y=!!1;z.each{|c|t.each{|o|v=[c[0]+o[0],c[1]+o[1]]
y=!(z+=[v])if v[0]>=0&&v[1]>=0&&v[0]<l.size&&v[1]<l[0].size&&p[l[v[0]][v[1]]]&&!z.index(v)}}
break if y};z};(y=y;z=k[u,[[u.index{|p|y=p.index /\S/},y]],([-1,0,1].product([-1,0,1])-[0,0]),->x{x!=b}]
n=z.min_by{|c|c[0]}[0];m=z.min_by{|c|c[1]}[1];q=Array.new(z.max_by{|c|c[0]}[0]-n+1){b*(z.max_by{|c|c[1]}[1]-m+1)}
z.each{|c|q[c[0]-n][c[1]-m]=u[c[0]][c[1]];u[c[0]][c[1]]=b};w+=[q])while u*''=~/\S/;o=Hash.new 0;w.each{|c|o[c]+=1}
p=->q{e=k[q,((0...q.size).flat_map{|x|[[x,0],[x,q[0].size-1]]}+(1...q[0].size-1).flat_map{|y|[[0,y],[q.size-1,y]]}).select{|c|q[c[0]][c[1]]==b},[[0,1],[0,-1],[1,0],[-1,0]],->x{x==b}]
(q.size*q[0].size)-e.size};r=o.sort_by{|k,v|v+(p[k]/1e3)}.reverse.map{|k,v|(k+[b*k[0].size])*v}
r.map!{|k|k+([b*k[0].size]*(r.max_by(&:size).size-k.size))};puts ([b]*r.max_by(&:size).size).zip(*r).map{|r|r.join(b)[2..-1]}

You can give the input on STDIN, or you can pass an input file as an argument (like ruby organize.rb candy.txt) and it will treat the file as STDIN automatically.

All semicolons can be replaced with newlines; I just glued some lines together to reduce vertical space.

Ungolfed (2367 chars):

#!/usr/bin/ruby
input = $<.read.split("\n")
candies = []

# utility method
flood = -> arr, coords, offsets, cond {
    loop {
        changed = false
        coords.each{|c|
            offsets.each{|o|
                nc = [c[0]+o[0], c[1]+o[1]]
                if nc[0] >= 0 && nc[1] >= 0 && nc[0] < arr.length && nc[1] < arr[0].length &&
                    cond[arr[nc[0]][nc[1]]] && !coords.index(nc)
                    coords.push nc
                    changed = true
                end
            }
        }
        break if !changed
    }
    coords
}

# while there are non-whitespace characters in the pile
while input.join =~ /\S/
    # get coordinates of the first character to flood-fill on
    y = nil
    x = input.index{|row| y = row.index /\S/ }

    # flood-fill on that character
    coords = flood[input, [[x, y]], ([-1,0,1].product([-1,0,1]) - [0, 0]), ->x{x != ' '}]

    # x = max, n = min
    xx = coords.max_by{|c| c[0] }[0]
    nx = coords.min_by{|c| c[0] }[0]
    xy = coords.max_by{|c| c[1] }[1]
    ny = coords.min_by{|c| c[1] }[1]

    # create a properly sized thingy for this one candy
    candy = Array.new(xx - nx + 1) {
        ' ' * (xy - ny + 1)
    }

    # fill the thingy, while also removing it from the pile
    coords.each{|c|
        candy[c[0] - nx][c[1] - ny] = input[c[0]][c[1]]
        input[c[0]][c[1]] = ' '
    }

    candies.push candy
end

# group by same candies
candytypes = Hash.new 0
candies.each{|c| candytypes[c] += 1 }

area = -> candy {
    # we want to eliminate surrounding spaces
    # so flood-fill all spaces that touch the edges
    surround = (0...candy.length).flat_map{|x| [[x, 0], [x, candy[0].length-1]] } +
        (1...candy[0].length-1).flat_map{|y| [[0, y], [candy.length-1, y]] }
    surround.select! {|c| candy[c[0]][c[1]] == ' ' }
    surround = flood[candy, surround, [[0,1],[0,-1],[1,0],[-1,0]], ->x{x == ' '}]

    # now just subtract amount of surrounding spaces from total amount of chars
    (candy.length * candy[0].length) - surround.length
}
columns = candytypes.sort_by {|k, v|
    # this is a pretty ugly hack
    v + (area[k] / 1000.0)
}.reverse.map{|k, v| (k + [' ' * k[0].length]) * v }
columns.map!{|k| k + ([' ' * k[0].length] * (columns.max_by(&:length).length - k.length)) }

puts ([' '] * columns.max_by(&:length).length).zip(*columns).map{|r| r.join(' ')[2..-1] }