Eco-ize data for printing
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 :
- Draw holes inside image, cheking to not collide on a previous one. Example :
- 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
;_;
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 shapeAlternating between the small and large shape randomlyCompletely 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:
##############
##### ##### #########
###### ### #### #####
### ### # ## ######
#### ### ### ## #######
#### ### ## ## #### #########
### ## ###### #### ## ###########
## ## ## ### ## ############
## ### ### ## ########
#### ### ### #### ######
##### ## ## ## ####### ####
####### ## ## ########
### ## ### ####
## ## ## ## ####
# ## ## ## ## ######
## ##### ### ########
### ## #### ### ## ######
#### #### ## ## ## #########
## ##### ## ## ## ########
### ##### ##### ## ########
### ####### ## #### ## ######
########### ## ####### ######
########### ####### #####
########## #############
######### ###########
###############