12
\$\begingroup\$

Programmer's Garden

Being a professional software developer, you cannot risk exposing yourself to the harsh non-artificial light of the sun, but you also have a soft spot for flowers, and want to keep your garden in good shape all year round.

To this end, a gardener is hired each month to tidy up the flowerbed at the foot of your house. However you need to make sure the gardener is doing his job properly, and work out a suitable payment for the hard working fellow. Naturally a software solution is best.

Input

Your program will be fed input describing the flowerbed as it appears current, and details of items that need to be removed. The program must output the garden devoid of the clutter, and print out a breakdown of the gardeners pay. The input can be either be from STDIN, or as a single command line argument.

The first line of input is of the format

width height unwanted_item_type_count

where width is the width of the flowerbed, height is the height of the flowerbed (both in ASCII characters), and unwanted_item_type_count tells you how many lines will following containing a description of a type of item to be removed from the garden.

Each line for each unwanted type of item is of the format

width height string_representation name fee_per_item

where width is the width of the item, height is the height of the item (both in ASCII characters), string_representation is the string representation of the item without line breaks, name is an identifier for the type of item (spaces will be replaced with underscores), and fee_per_item is how much the gardener must be paid for the removal of each type of item.

For example

3 2 .R.\|/ rouge_flower 3

Represents an item type of name rouge_flower, which costs 3 to remove, and looks like this:

.R.
\|/

The items will not contain spaces, and no item may have a border consisting entirely of dots, and the string representation will also be the exact size described. Thusly, all of the following are invalid inputs:

3 1 ( ) space 0
1 1 . dot 0
2 1 .! bang 0
3 2 .@.\|/. plant 0

Note that 0 is however a valid fee (fees will always be integers greater than -1).

Note also that the flowerbed is predominately made up of dots (.) rather than spaces, and you can safely use whitespace as delimitation for all the inputs. The flowerbed is always bounded by dots itself.

After the unwanted item types are listed, then comes the ASCII representation of the flowerbed of given width and height.

Output

Output should be to STDOUT, or suitable alternative if your language doesn't support it.

The output starts with a print-out of the flowerbed, but with all unwanted items removed (replaced with dots), so you can see how it should appear and check the gardener has done his job. Each item in the flowerbed will be surrounded by a rectangle of dots, and will be one-contiguous item (i.e. there will be no separating dots inside the item). For example

.....
.#.#.
.....

shows 2 separate items

.....
.\@/.
.....

shows 1 item

......
.#....
....|.
....|.
.o--/.
......

is invalid, as while the stone (#) can be matched, the snake (you couldn't tell it was a snake?) cannot because the stone interferes with the required surrounding of dots.

...
\@.
...

This is also invalid, as the snail is on the edge of the flowerbed, and the edge must always be bounded by dots in a valid input.

After this, there should be a listing of each type of unwanted item, giving the count, the cost per item, and costs for all the items (count * cost per item), in the format:

<count> <name> at <cost_per_item> costs <cost>

After this, there should be a single line yielding the total cost (the sum of the costs for unwanted items):

total cost <total_cost>

Example

For this given input

25 18 3
4 2 .\/.\\// weeds 5
2 1 \@ snails 2
1 1 # stones 1
.........................
.\@/.................\@..
............\/...........
......O....\\//..^|^.....
.#...\|/.........^|^.....
..................|......
.................\|/.....
..\@.....\/...........#..
........\\//....#........
....*....................
...\|/......\/......\@/..
...........\\//..........
..................*......
.......\@/.......\|/.....
...O.....................
..\|/.......*............
.......#...\|/....\@.....
.........................

The program should produce this output

.........................
.\@/.....................
.........................
......O..........^|^.....
.....\|/.........^|^.....
..................|......
.................\|/.....
.........................
.........................
....*....................
...\|/..............\@/..
.........................
..................*......
.......\@/.......\|/.....
...O.....................
..\|/.......*............
...........\|/...........
.........................
3 weeds at 5 costs 15
3 snails at 2 costs 6
4 stones at 1 costs 4
total cost 25

The output must be terminated by a line-break.

This is code-golf, may the shortest code win.

Additional test case

Edit: this used to contain Unicode, which isn't allowed in the flowerbed, far too modern. This has been rectified, sorry about that.

25 15 5
5 3 ..@..\\|//.\|/. overgrown_plants 3
5 3 @-o....|...\|/. semi-articulated_plant 4
3 2 .|.\@/ mutant_plants 5
1 1 $ dollars 0
1 1 # stones 1
.........................
........@................
....$..\|/...........@...
............|.......\|/..
...#.......\@/...........
.........................
.........................
......@.......@......@...
.....\|/....\\|//...\|/..
.............\|/.........
.#....................#..
.........$.......|.......
...\/.......\/..\@/..\/..
..\\//.....\\//.....\\//.
.........................

Expected Output:

.........................
........@................
.......\|/...........@...
....................\|/..
.........................
.........................
.........................
......@..............@...
.....\|/............\|/..
.........................
.........................
.........................
...\/.......\/.......\/..
..\\//.....\\//.....\\//.
.........................
1 overgrown_plants at 3 costs 3
0 semi-articulated_plants at 4 costs 0
2 mutant_plants at 5 costs 10
2 dollars at 0 costs 0
3 stones at 1 costs 3
total cost 16
\$\endgroup\$
  • \$\begingroup\$ May we assume the bounding box of each unwanted item is exact? That is, no border in the item's description is fully dots? \$\endgroup\$ – John Dvorak Sep 16 '14 at 10:00
  • \$\begingroup\$ @JanDvorak yes, that seems a reasonable enough constraint. I'll add that to the question, and I'll borrow your wording on the presumption that you won't mind my doing so. \$\endgroup\$ – VisualMelon Sep 16 '14 at 10:15
  • \$\begingroup\$ Will the snail be crawling to different direction as well? \@ and @/ for example.. Or are they bound to point eternally to west? \$\endgroup\$ – Han Soalone Sep 17 '14 at 9:28
  • \$\begingroup\$ @SickDimension the unwanted items should only be matched precisely as they are described, distinct rotations and flips should not be matched. This does not preclude the possibility that a snail will crawl in the other direction, but no one is being paid to remove them in the example. \$\endgroup\$ – VisualMelon Sep 17 '14 at 10:08
3
\$\begingroup\$

Perl - 636

There is definitely some more golfing that can be done. And probably better ways to do it too.

<>;while(<>){if(/ /){chomp;push@v,$_}else{$t.=$_}}for(@v){r(split/ /)}say$t.$y."total cost $u";sub r{my($e,$w,$c,$h,$z)=@_;($i,$f,$q,$d)=(1,0,0,"."x$e);@m=($c=~/($d)/g);@l=split/\n/,$t;while($i>0){($g,$j)=(1,0);for(0..$#l){if($j==0&&$l[$_]=~/^(.*?)\.\Q$m[$j]\E\./){$j++;$l="."x length$1}elsif($j<@m&&$l[$_]=~/^$l\.\Q$m[$j]\E\./){$j++}elsif($j>0){$l[$_-1]=~s!.\Q$m[$j-1]\E.!" ".$m[$j-1]=~s/\./ /gr." "!e;($j,$g)=(0,0)}if($j==@m){$k=$j;for($f=$_;$f>$_-$j;$f--){$k--;$o="."x length$m[$k];$l[$f]=~s/^($l)\.\Q$m[$k]\E\./$1.$o./}($g,$j)=(0,0);$q++}}if($g){$i--}}$t=join("\n",@l)."\n";$t=~s/ /./g;$p=$z*$q;$u+=$p;$y.="$q $h at $z costs $p\n"}

635 characters + 1 for -C flag to handle the euros.

If you have the input stored in input.txt you can run it with:

cat input.txt | perl -C -E'<>;while(<>){if(/ /){chomp;push@v,$_}else{$t.=$_}}for(@v){r(split/ /)}say$t.$y."total cost $u";sub r{my($e,$w,$c,$h,$z)=@_;($i,$f,$q,$d)=(1,0,0,"."x$e);@m=($c=~/($d)/g);@l=split/\n/,$t;while($i>0){($g,$j)=(1,0);for(0..$#l){if($j==0&&$l[$_]=~/^(.*?)\.\Q$m[$j]\E\./){$j++;$l="."x length$1}elsif($j<@m&&$l[$_]=~/^$l\.\Q$m[$j]\E\./){$j++}elsif($j>0){$l[$_-1]=~s!\Q$m[$j-1]\E!$m[$j-1]=~s/\./ /gr!e;($j,$g)=(0,0)}if($j==@m){$k=$j;for($f=$_;$f>$_-$j;$f--){$k--;$o="."x length$m[$k];$l[$f]=~s/^($l)\.\Q$m[$k]\E\./$1.$o./}($g,$j)=(0,0);$q++}}if($g){$i--}}$t=join("\n",@l)."\n";$t=~s/ /./g;$p=$z*$q;$u+=$p;$y.="$q $h at $z costs $p\n"}'

Here is the deparsed version. I went through and added some comments to help explain things. Maybe I'll go make the variable names more readable sometime. There may be some edge cases this doesn't work with but it works with the examples at least.

BEGIN { # These are the features we get with -C and -E flags
    $^H{'feature_unicode'} = q(1); # -C gives us unicode
    $^H{'feature_say'} = q(1); # -E gives us say to save 1 character from print
    $^H{'feature_state'} = q(1);
    $^H{'feature_switch'} = q(1);
}
<ARGV>; # throw away the first line
while (defined($_ = <ARGV>)) { # read the rest line by line
    if (/ /) { # if we found a space (the garden doesn't have spaces in it)
        chomp $_; # remove the newline
        push @v, $_; # add to our array
    }
    else { # else, we construct the garden
        $t .= $_;
    }
}
foreach $_ (@v) { # call the subroutine r by splitting our input lines into arguments
    r(split(/ /, $_, 0)); # the arguments would be like r(3,2,".R.\|/","rouge_flower",3)
}
say $t . $y . "total cost $u"; # print the cost at the end

# this subroutine removes weeds from the garden and counts them
sub r {
    BEGIN {
        $^H{'feature_unicode'} = q(1);
        $^H{'feature_say'} = q(1);
        $^H{'feature_state'} = q(1);
        $^H{'feature_switch'} = q(1);
    }
    my($e, $w, $c, $h, $z) = @_; # get our arguments
    ($i, $f, $q, $d) = (1, 0, 0, '.' x $e); # initialize some variables
    @m = $c =~ /($d)/g; # split a string like this .R.\|/ into .R. and \|/
    @l = split(?\n?, $t, 0); # split the garden into lines to process line by line
    while ($i > 0) {
        ($g, $j) = (1, 0);
        foreach $_ (0 .. $#l) { # go through the garden
            if ($j == 0 and $l[$_] =~ /^(.*?)\.\Q$m[$j]\E\./) { # this matches the top part of the weed. \Q and \E make it so the weed isn't intepreted as a regex. Capture the number of dots in front of it so we know where it is
                ++$j;
                $l = '.' x length($1); # this is how many dots we have
            }
            elsif ($j < @m and $l[$_] =~ /^$l\.\Q$m[$j]\E\./) { # capture the next line
                ++$j;
            }
            elsif ($j > 0) { # if we didn't match we have to reset
                $l[$_ - 1] =~ s[.\Q$m[$j - 1]\E.][' ' . $m[$j - 1] =~ s/\./ /rg . ' ';]e; # this line replaces the dots next to the weed and in the weed with spaces
                # to mark it since it didn't work but the top part matches
                # that way when we repeat we go to the next weed
                ($j, $g) = (0, 0);
            }
            if ($j == @m) { # the whole weed has been matched
                $k = $j;
                for ($f = $_; $f > $_ - $j; --$f) { # remove the weed backwards line by line
                    --$k;
                    $o = '.' x length($m[$k]);
                    $l[$f] =~ s/^($l)\.\Q$m[$k]\E\./$1.$o./; 
                }
                ($g, $j) = (0, 0);
                ++$q;
            }
        }
        if ($g) {
            --$i; # all the weeds of this type are gone
        }
    }
    $t = join("\n", @l) . "\n"; # join the garden lines back together
    $t =~ s/ /./g; # changes spaces to dots 
    $p = $z * $q; # calculate cost
    $u += $p; # add to sum
    $y .= "$q $h at $z costs $p\n"; #get message
}

Feel free to suggest improvements!

\$\endgroup\$
  • \$\begingroup\$ Nice work, and I'm afraid I have sinned, I did specify that the flowerbed would be ASCII, and then got all excited and put Unicode in the example - I will change the example so that it's just ASCII, sorry for making work for you. \$\endgroup\$ – VisualMelon Sep 17 '14 at 9:00
  • 1
    \$\begingroup\$ @VisualMelon it was interesting to learn how to get a one-liner to work with unicode. I didn't know about the -C flag before this. I'll leave it in there to be compatible anyway since it is only a 1 character difference. \$\endgroup\$ – chilemagic Sep 17 '14 at 13:47
0
\$\begingroup\$

Python 3, 459 bytes

    from re import*
E=input()
W,H,C=map(int,E[0].split())
B,T,O='\n'.join(E[~H:]),0,''
for L in E[1:~H]:
 w,h,s,n,c=L.split();w,h,c=map(int,(w,h,c));r,t='.'*(w+2),0;a=[r]+['.%s.'%s[i:i+w]for i in range(0,w*h,w)]+[r]
 for L in['(%s)'%'\\n'.join('.{%d})%s(.*'%(i,escape(b))for b in a)for i in range(W)]:t+=len(findall(L,B));B=sub(L,r.join('\\%d'%b for b in range(1,h+4)),B,MULTILINE)
 O+='%d %s at %d costs %d\n'%(t,n,c,t*c);T+=t*c
print(B+O+'total cost',T)

Assumes the input will be given as a list of strings.

\$\endgroup\$
  • \$\begingroup\$ I like the ~H trick; I can't test this now, but I'll try to do so later today. \$\endgroup\$ – VisualMelon Aug 16 at 10:49
  • \$\begingroup\$ I can't seem to get this to run correctly (ValueError: not enough values to unpack (expected 3, got 1), python 3.6.6); can you provide a TIO link or some description on how to run it. I think it might be bending the rules by assuming the input is all on one line, but I wasn't entirely clear about that in the question so I won't complain. \$\endgroup\$ – VisualMelon Aug 16 at 18:12
  • \$\begingroup\$ @VisualMelon - bah, I've probably copy/pasta'd something incorrectly. I can't get to TIO at work, so I'll check my work and post a link later today. \$\endgroup\$ – Triggernometry Aug 16 at 18:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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