6
\$\begingroup\$

Inspired by ecofont.

Given a string containing # and , output it more eco-friendly by cutting out circles, while keeping it "recognizable" (defined later, in the Circles section). # represents black, and represents white. This program is supposed to do something like this:

Input:

####################
####################
####################
####################
####################
####################
####################
####################
####################
####################
####################

Sample output (rather bad score):

####################
#### ###############
##     #############
##     #### ########
#       #     ######
##     ##     ######
##     #       #####
#### ####     ######
#########     ######
########### ########
####################

Circles

These are the only valid circles (#s indicating characters that would be cut out):

  #
 ###
#####
 ###
  #

   #
 #####
 #####
#######
 #####
 #####
   #

Every circle cut out must be of the same radius. By "recognizable", I mean that there must be a gap of at least one pixel / point between each circle, and each circle and the edge of the shape (outside of the # region):

Again, # indicates characters that would be cut out, not characters that would be left behind

   #      #
 #####  #####
 #####  #####
##############
 #####  #####
 #####  #####
   #      #

Is invalid, but:

   #
 #####
 #####
#######   #
 #####  #####
 #####  #####
   #   #######
        #####
        #####
          #

Is valid. Note that corners are considered touching. That is, in

#
 #

the two "pixels" are considered touching, thus circles cannot touch in that way.

Also, just to restate it, if we have a shape like:

########
########
########
########
########
########
########
########

Cutting circles like this is invalid (they both touch the edge of the figure):

####   #
###     
####   #
## ## ##
#   ####
     ###
#   ####
## #####

Scoring

Your score is the total number of #s left from the specified inputs. Lowest score wins.

Input #1:

##################################################
##################################################
##################################################
##################################################
##################################################
##################################################
##################################################
##################################################
##################################################
##################################################
##################################################
################################################# 
################################################# 
################################################# 
################################################# 
################################################  
################################################  
################################################  
###############################################   
###############################################   
##############################################    
##############################################    
##############################################    
#############################################     
############################################      
############################################      
###########################################       
###########################################       
##########################################        
#########################################         
#########################################         
########################################          
#######################################           
######################################            
######################################            
#####################################             
####################################              
###################################               
##################################                
################################                  
###############################                   
##############################                    
############################                      
###########################                       
#########################                         
#######################                           
######################                            
###################                               
#################                                 
##############                                    

Input #2:

                                         #####################                                      
                                        #######################                                     
                                        #######################                                     
                                       #########################                                    
                                       #########################                                    
                                      ###########################                                   
                                     ############################                                   
                                     #############################                                  
                                    ##############################                                  
                                    ###############################                                 
                                   ################################                                 
                                   #################################                                
                                  ##################################                                
                                 ####################################                               
                                 #################   ################                               
                                #################    #################                              
                                #################     ################                              
                               #################      #################                             
                               #################       ################                             
                              #################        #################                            
                              #################        #################                            
                             #################          #################                           
                            ##################          #################                           
                            #################            #################                          
                           #################             #################                          
                           #################              #################                         
                          #################               #################                         
                          #################                #################                        
                         #################                 #################                        
                        ##################                  #################                       
                        #################                   ##################                      
                       ##################                    #################                      
                       #################                     #################                      
                      ##################                      #################                     
                      #################                       #################                     
                     ##################                        #################                    
                     #################                         ##################                   
                    ##################                         ##################                   
                    #################                           #################                   
                   ###############################################################                  
                  ################################################################                  
                  #################################################################                 
                 ###################################################################                
                 ###################################################################                
                #####################################################################               
               ######################################################################               
               ######################################################################               
              ########################################################################              
              ########################################################################              
             ##########################################################################             
             ##################                                      ###################            
            ###################                                       ##################            
            ##################                                        ###################           
           ###################                                         ##################           
           ##################                                          ###################          
          ###################                                           ##################          
         ###################                                            ###################         
         ###################                                             ##################         
        ###################                                              ###################        
        ###################                                              ###################        
       ###################                                                ###################       
       ###################                                                 ##################       
      ###################                                                  ###################      
     ####################                                                  ###################      
     ###################                                                    ###################     
    ####################                                                    ###################     
    ###################                                                      ###################    
   ####################                                                      ###################    
   ###################                                                        ###################   
  ####################                                                        ###################   
  ###################                                                          ###################  
 ####################                                                          ###################  
####################                                                            ################### 
####################                                                            ################### 
###################                                                              ###################

Input #3:

              ##############            
          #####################         
        #########################       
      #############################     
    #################################   
   ###################################  
  ##################################### 
  ####################################  
 ##################################     
################################        
#############################           
##########################              
#######################                 
######################                  
##########################              
#############################           
###############################         
 ##################################     
  ####################################  
  ##################################### 
   ###################################  
    #################################   
      #############################     
        ##########################      
          #####################         
             ###############            

Note: Tailoring specifically to the samples is not allowed.

\$\endgroup\$
4
  • 1
    \$\begingroup\$ You either need to provide (examples of) correct output for the sample inputs, or explain the challenge in more detail, because as it stands I don't understand what the program is supposed to do, at all. \$\endgroup\$
    – breadbox
    Feb 11, 2014 at 6:34
  • \$\begingroup\$ @breadbox how is that? Also, note that since this is inspired by eco-font, that should help with understanding what this problem is. \$\endgroup\$
    – Justin
    Feb 11, 2014 at 6:41
  • 4
    \$\begingroup\$ "Inspired by ecofont": If we need to visit that site and read up on what it is and then get back to your question to figure out the exact challenge than all I see is an attempt to "spam" ecofont. Your challenge should be clearly described here, period. "defined later, in the Circles section": where? I don't see it. Tip: adding an image like this one will clarify a lot (something about a picture and 1000 words ;-) ) \$\endgroup\$
    – RobIII
    Feb 11, 2014 at 9:38
  • 2
    \$\begingroup\$ I went to ecofont.com and I still have no idea what this challenge is asking for. \$\endgroup\$
    – Paul R
    Feb 11, 2014 at 11:25

2 Answers 2

6
\$\begingroup\$

PHP

**WARNING : spaghetti english and spaghetti code ahead **

Okay, not sure I understood everything but here's my try. So what is done ?

  • Convert text input to an image. " " = white pixel, "#" = red pixel. Example : enter image description here
  • Draw holes inside image, cheking to not collide on a previous one. Example : enter image description here
  • Convert back image to text

(not sure about this red dot in the bottom right corner but, he, yolo)

<?php

    /* Check collision between white pixels in 2 images. */
    function checkCollision ($img1, $img2, $width, $height, $circle_x, $circle_y, $circle_size)
    {
        $start_x = $circle_x - round($circle_size / 2);
        if ($start_x < 0) return false;

        $stop_x = $circle_x + round($circle_size / 2);
        if ($stop_x > ($width - 1)) return false;

        $start_y = $circle_y - round($circle_size / 2);
        if ($start_y < 0) return false;

        $stop_y = $circle_y + round($circle_size / 2);
        if ($stop_y > ($height - 1)) return false;


        $color_white = array("red" => 255,
                "green" => 255,
                "blue" => 255,
                "alpha" => 0
                );

        for ($y = $start_y; $y < $stop_y - 1; $y++)
            for ($x = $start_x; $x < $stop_x - 1; $x++)
            {
                $pixel_img1 = imagecolorsforindex($img1, imagecolorat($img1, $x, $y));
                $pixel_img2 = imagecolorsforindex($img2, imagecolorat($img2, $x, $y));

                if ($pixel_img1 == $pixel_img2 
                    && $pixel_img1 == $color_white)
                        return false;                       
            }

        return true;
    }

    $input      = file_get_contents("input.txt");
    $lines      = explode("\n", $input);
    $image_width    = strlen($lines[0]);
    $image_height   = count($lines);
    $circle_size    = 5;

    /* Creating an image matching dimensions and some colors. */
    $img            = imagecreatetruecolor($image_width, $image_height);
    $color_red      = imagecolorallocate($img, 255, 0, 0);
    $color_white        = imagecolorallocate($img, 255, 255, 255);

    /* Filling the freshly created image. '#' is replaced by a red pixel, ' ' by a white one. */
    for ($y = 0; $y < $image_height; $y++)
    {
        $line = $lines[$y];
        for ($x = 0; $x < strlen($line); $x++)
            if ($line[$x] == '#')
                imagesetpixel($img, $x, $y, $color_red);
            else
                imagesetpixel($img, $x, $y, $color_white);
    }

    /*Try to draw a circle on any red pixel then check if 
    it not collides with any other white space before commiting */

    for ($y = 0; $y < $image_height; $y++)
        for ($x = 0; $x < $image_width; $x++)
        {
            $img_tmp = imagecreatetruecolor($image_width, $image_height);
            imagecopy($img_tmp, $img, 0, 0, 0, 0, $image_width, $image_height);

            imagefilledellipse($img_tmp, $x, $y, ($circle_size + 2), ($circle_size + 2), $color_white);

            if (checkCollision ($img, $img_tmp, $image_width, $image_height, $x, $y, ($circle_size + 2)))
                imagefilledellipse($img, $x, $y, $circle_size, $circle_size, $color_white);
        }

    /* Convert image to text */
    $output = "";
    $color_white = array("red" => 255,
            "green" => 255,
            "blue" => 255,
            "alpha" => 0
            );

    for ($y = 0; $y < $image_height; $y++)
    {
        for ($x = 0; $x < $image_width; $x++)
        {
            $pixel_img = imagecolorsforindex($img, imagecolorat($img, $x, $y));
            if ($pixel_img == $color_white)
                $output = $output . " ";
            else
                $output = $output . "#";
        }
        $output = $output . "\n";
    }

    file_put_contents("output.txt", $output)

?>

Spent a lot of time because I didn't know I could not just copy a GD ressource doing $a = $b.. (it creates a ref)

Example :

Input :

              ##############            
          #####################         
        #########################       
      #############################     
    #################################   
   ###################################  
  ##################################### 
  ####################################  
 ##################################     
################################        
#############################           
##########################              
#######################                 
######################                  
##########################              
#############################           
###############################         
 ##################################     
  ####################################  
  ##################################### 
   ###################################  
    #################################   
      #############################     
        ##########################      
          #####################         
             ###############            

Output :

              ##############             
          #####################          
        ########## ###### #######        
      ###########   ####   ########      
    ######## ###     ##     #########    
   ########   ###   ####   ###########   
  ########     ### ###### #############  
  ##### ###   ########################   
 #####   ### ######################      
#####     ######## #############         
######   ########   #########            
####### ########     #####               
############# ###   ###                  
############   ### ###                   
###### ####     ##########               
#####   ####   ##############            
####     #### ###### ##########          
 ####   ###########   #############      
  #### ###########     #### ##########   
  ########## ######   ####   ##########  
   ########   ###### ####     ########   
    ######     ###########   ########    
      #####   ############# #######      
        #### #####################       
          #####################          
             ###############             

I hope this hit the target. It's obvious that we can do it better and more properly but maybe it would help the others to understand what this code challenge is about.

Score

Input 1 :

Before : 2030 "#"
After : 1575 "#"
455 removed

Input 2 :

Before : 2955 "#"
After : 2370 "#"
585 removed

Input 3 :

Before : 748 "#"
After : 618 "#"
130 removed

Total :

"#" input : 5733
"#" left : 4563 (~80%)
"#" removed : 1170 (~20%)

FINAL SCORE : 4563

;_;

\$\endgroup\$
4
  • \$\begingroup\$ AFAIU, your "circles" can't touch the edges, so this doesn't qualify. \$\endgroup\$ Feb 11, 2014 at 20:23
  • \$\begingroup\$ Okay it's corrected. I did not noticed this. Does it qualify now ? \$\endgroup\$
    – user16229
    Feb 11, 2014 at 20:40
  • \$\begingroup\$ Looks good to me. +1 \$\endgroup\$ Feb 11, 2014 at 21:45
  • \$\begingroup\$ edited to add total score \$\endgroup\$
    – user16229
    Feb 12, 2014 at 9:16
3
\$\begingroup\$

Python 2.7

Expects the input file to be passed via the command line, e.g.

python thisscript.py input1.txt

I implemented 5 2 options to run:

  • Using the small shape
  • Using the large shape
  • Alternating between the small and large shape
  • Alternating between the small and large shape randomly
  • Completely random

I just scan the input starting from the top left and a shape is cut away as soon as possible.

The shapes themselves can be modified quite easily.

import sys,random,copy

def char2val(c):
    if (c=='#'):
        return 1 # this is the shape itself
    elif (c=='o'):
        return 2 # this is the boundary, for collision detection
    else:
        return 0
def val2char(v):
    if (v==0):
        return ' '
    else:
        return '#'
# convert string to array for processing
def str2arr(s):
    arr = []
    for line in s.split('\n'):
        arr.append( [ char2val(c) for c in line ] )
    return arr
# convert array to string for output purposes
def arr2str(arr):
    s=""
    for i in range(len(arr)):
        for j in range(len(arr[i])):
            s+=val2char(arr[i][j])
        s+="\n"
    return s
# check if a cut we want to make is a valid one
def validate_cut(arr,shape,r,c):
    valid = True
    for i in range(len(shape)):
        for j in range(len(shape[i])):
            if shape[i][j] == 1: #hard cut here
                valid = ( 0 < i+r < len(arr)-1 ) and ( 0 < j+c < len(arr[i+r])-1) # bounds check
                valid = valid and ( arr[i+r][j+c]==1) # site must be cut-able
            elif shape[i][j]==2: #edge of shape
                valid = ( 0 <= i+r <= len(arr)-1 ) and ( 0 <= j+c <= len(arr[i+r])-1) # bounds check, edge allowed to lie on border
                valid = valid and arr[i+r][j+c]!=0 # edge cannot go into cut/empty space
            if not valid:
                return False
    return valid

def cut(arr,shape,r,c): # cut shape from arr, @ position r,c
    for i in range(len(shape)):
        for j in range(len(shape[i])):
            if (shape[i][j] > 0):
                arr[i+r][j+c] -= shape[i][j]
def run(inarr,opt=0):
    arr = copy.deepcopy(inarr)
    for r in range(len(arr)):
        for c in range(len(arr[r])):
            if (opt==0):
                shape = c1arr
            elif (opt==1):
                shape = c2arr
            else:
                raise Exception("run option not supported!")
            if validate_cut(arr,shape,r,c):
                cut(arr,shape,r,c)
    return arr
# global variables for the shapes,...
# \# are the shapes themselves
# o is the boundary used for collision detection
c1 = \
"\
  ooo  \n\
 oo#oo \n\
oo###oo\n\
o#####o\n\
oo###oo\n\
 oo#oo \n\
  ooo  \
"
c2 = \
"\
   ooo   \n\
 ooo#ooo \n\
 o#####o \n\
oo#####oo\n\
o#######o\n\
oo#####oo\n\
 o#####o \n\
 ooo#ooo \n\
   ooo   \
"
c1arr = str2arr(c1)
c2arr = str2arr(c2)
def main():
    #input processing
    random.seed('117')
    f = file(sys.argv[1],"r")
    inp = f.read().rstrip('\n') #input string
    inarr = str2arr(inp)        #convert string to array
    #run the algorithm
    arr0 = run(inarr,opt=0)
    arr1 = run(inarr,opt=1)
    minarr = arr0 if arr2str(arr0).count('#') < arr2str(arr1).count('#') else arr1
    #output
    print arr2str(minarr)
    print " %d # of %d remaining " % (arr2str(minarr).count('#'),inp.count('#'))
main()

The results are

Input1

1102 # of 2030 remaining

Input2

1766 # of 2955 remaining

Input3

514 # of 748 remaining

Full output for input3:

              ##############            
          ##### ##### #########         
        ######   ###   #### #####       
      ### ###     #     ##   ######     
    ####   ###   ###   ##     #######   
   ####     ### ## ## ####   #########  
  ### ##   ######   #### ## ########### 
  ##   ## ## ###     ##   ############  
 ##     ###   ###   ##     ########     
####   ###     ### ####   ######        
##### ## ##   ## ####### ####           
#######   ## ##   ########              
### ##     ###     ####                 
##   ##   ## ##   ####                  
#     ## ##   ## ## ######              
##   #####     ###   ########           
### ## ####   ###     ## ######         
 ####   #### ## ##   ##   #########     
  ##     #####   ## ##     ## ########  
  ###   #####     #####   ##   ######## 
   ### #######   ## #### ##     ######  
    ########### ##   #######   ######   
      ###########     ####### #####     
        ##########   #############      
          ######### ###########         
             ###############  

Total score: 3382

\$\endgroup\$
4
  • \$\begingroup\$ Nice one. Total score is 3382 if we take the minimum for each input. \$\endgroup\$
    – user16229
    Feb 12, 2014 at 9:17
  • \$\begingroup\$ Three things: 1st, your program is supposed to decide which method to run. 2nd, the first two options are the only valid options. 3rd, can you show an output for one of the inputs? \$\endgroup\$
    – Justin
    Feb 12, 2014 at 18:53
  • \$\begingroup\$ Updated my post accordingly. \$\endgroup\$ Feb 13, 2014 at 10:18
  • \$\begingroup\$ @camelthemammel Don't forget the @ when responding to comments; I did not notice that you updated your post until now. \$\endgroup\$
    – Justin
    Feb 17, 2014 at 7:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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