Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

Background

ASCII art is the practice of creating images by using ASCII text to form shapes.

Aliasing is the effect created by the large "pixels" of ASCII art, which are the size of characters. The image becomes blocky and hard to see. Anti-aliasing removes this effect by creating a gradient and by softening the hard edges of the ASCII art.

The Challenge

Your challenge is to write the shortest program possible that will take a piece of ASCII art and will output a version that has been anti-aliased.

What sort of anti-aliasing?

All of the ASCII art will consist of two types of symbols: Spaces and non-whitespace. For each non-whitespace character, your program must determine whether it is in a position where it need to be anti-aliased. If it is, then you need to replace it with the correct character. If it isn't, then the character stays the same.

How do you know if a character needs to be anti-aliased? The answer depends on the characters that are immediately above, below, left, and right of the character (not the diagonals). Here is a chart of when anti-aliasing is required, where ? and x can stand for any non-whitespace character.

 x? ->  d?
 ?      ? 


?x  -> ?b 
 ?      ? 

 ?      ? 
?x  -> ?F 


 ?      ? 
 x? ->  Y?



 x  ->  ;   Note: This character has been changed from _ to ;
 ?      ? 

 ?      ? 
 x  ->  V 



?x  -> ?> 



 x? ->  <?



 x  ->  @ 

Input (and example pre-anti-aliasing ASCII art)

First, there will be two lines of input (to STDIN), a number H followed by a number W. There will then be H lines of exactly W characters each (excluding the newline). These following lines will be the ASCII art that needs to be anti-aliased. Here is an example input (not beautiful, but a test):

7
9
  888888 
 888888  
999 98  7
 666666  
  666666 
   6666  
    6    

Output (and example anti-aliased art)

Your program should output to STDOUT the ASCII art (of the same dimensions), which has been anti-aliased. Here is the output for the above input. Notice how the the border characters are treated as bordering whitespace.

  d8888> 
 d8888F  
<99 98  @
 Y6666b  
  Y6666> 
   Y66F  
    V    

This might not look that good (due to the space between lines in the code block), it looks better with larger ASCII art, and the quality depends on the exact font used.

Another Example

Input

12
18
   xx  xxx  xxx   
  xxxx  xxx  xxx  
 xxxxxx  xxx  xxx 
xxx  xxx  xxx  xxx
xxxx xxx  xxx  xxx
 xxxxxx  xxx  xxx 
  xxxx  xxx  xxx  
x  xx  xxx  xxx  x
xx    xxx  xxx  xx
xxx  xxx  xxx  xxx
xxxx  xxx  xxx  xx
xxxxx  xxx  xxx  x

Output

   db  <xb  <xb   
  dxxb  Yxb  Yxb  
 dxxxxb  Yxb  Yxb 
dxx  xxb  xxb  xxb
Yxxb xxF  xxF  xxF
 YxxxxF  dxF  dxF 
  YxxF  dxF  dxF  
;  YF  dxF  dxF  ;
xb    dxF  dxF  dx
xxb  <xF  <xF  <xx
xxxb  Yxb  Yxb  Yx
Yxxx>  Yx>  Yx>  V

Rules, Restrictions, and Notes

Your program should be written in printable ASCII characters only, so that we can make art out of the programs. Other than that, the standard code-golf rules apply.

share|improve this question
    
Since there are no answers yet, I have changed one character in the anti-aliasing chart. _ has become ; because it works better. –  PhiNotPi Apr 11 '12 at 15:15
    
This might be my favorite code golf question of all time. Working on like 4 different awesome solutions. –  CMP Apr 12 '12 at 1:46
    
Although I am confused. You say diagonals don't count, but your diagrams all show question marks filling out the diagonals. From what I see in the examples, it may be safe to only look to the sides, but I get confused? Do diagonals ever matter? –  CMP Apr 12 '12 at 3:17
    
No, the diagonals never matter. It will probably be more clear if I removed the diagonals from the chart. –  PhiNotPi Apr 12 '12 at 3:23
    
I think there might be a typo in your example; I believe the right-hand column should have Ys on the inside edge. Enjoyed coming up with the answer to this one though, good question :D –  Ed Woodcock Apr 12 '12 at 19:16

7 Answers 7

Ruby, 180 168 characters

gets
w=1+gets.to_i
f=*(readlines*"").chars
f.zip(f[1..-1]+s=[" "],s+f,s*w+f,f[w..-1]+s*w){|a,*b|$><<"@;V#{a}>bF#{a}<dY#{a*5}"[a>" "?(b.map{|y|y>" "?1:0}*"").to_i(2):3]}

Another Ruby implementation which takes a zip approach. You can see the second example running online.

Edit: Using readlines saves 12 characters.

share|improve this answer

Ruby 275 265 263 261 258 254 244 243 214 212 207

H=0...gets.to_i
W=0...gets.to_i
G=readlines
z=->x,y{(H===y&&W===x&&' '!=G[y][x])?1:0}
H.map{|j|W.map{|i|l=G[j][i]
G[j][i]="@V;#{l}>Fb#{l}<Yd#{l*5}"[z[i+1,j]*8+z[i-1,j]*4+z[i,j+1]*2+z[i,j-1]]if' '!=l}}
puts G

Sample 1: http://ideone.com/PfNMA

Sample 2: http://ideone.com/sWijD

share|improve this answer
    
1) Parenthesis around the range definition are not necessary. 2) 0..h-1 can be written as 0...h. 3) G=[];h.times{G<<gets} can be written as G=readlines, similarly as in your C# code. 4) After step 3. variable h becomes useless, h and w's values are used only once, so h=gets.to_i;w=gets.to_i;H=(0..h-1);W=(0..w-1) can be written as H=0...gets.to_i;W=0...gets.to_i. 5) In this case and can be written as &&, which not needs the spaces around. 6) You have an extra ; and you counted the newline at the end of file, which are not necessary. This mean 214 chars: ideone.com/CiW0l –  manatwork Jun 2 '12 at 11:08
    
Wow, thanks! I knew there were improvements to be made, but never thought there were that many. I had tried H=0..gets.to_i when I wrote the code, but it didn't seem to work (obviously it must've been for other reasons). –  w0lf Jun 2 '12 at 11:52
1  
Still two points where you can reduce by at least 7 chars: 1) You can use map instead of each 2) z=->... instead of def z...end. –  Howard Jun 4 '12 at 11:31
    
@Howard Thanks, I've applied the map instead of each change. For the lambda syntax, however, I think that would require the usages of z to be of the form z.call(args) instead of z(args), thus adding a bit to the character count. Please let me know if I'm missing something. –  w0lf Jun 4 '12 at 12:35
    
@Howard Nevermind, I just found out what I was missing. I'll update to use the lambda [] usage. –  w0lf Jun 4 '12 at 12:37

Javascript, 410 characters:

function(t){m={"10110":"b","11100":"d","01101":"Y","00111":"F","10100":";","00101":"V","00110":">","01100":"<","00100":"@"},d="join",l="length",t=t.split('\n').splice(2),t=t.map(function(x)x.split('')),f=function(i,j)t[i]?(t[i][j]||' ')==' '?0:1:0;for(o=t[l];o--;){for(p=t[o][l];p--;){y=[f(o+1,p),f(o,p+1),f(o,p),f(o,p-1),f(o-1,p)],t[o][p]=m[y[d]('')]||t[o][p]}}t=t.map(function(x)x[d](''))[d]('\n');return t;}

ungolfed:

function(t){
    m={
        "10110":"b",
        "11100":"d",
        "01101":"Y",
        "00111":"F",
        "10100":";",
        "00101":"V",
        "00110":">",
        "01100":"<",
        "00100":"@"
    },
    d="join",
    l="length",
    t=t.split('\n').splice(2),
    t=t.map(function(x) x.split('')),
    f=function(i,j) t[i]?(t[i][j]||' ')==' '?0:1:0;

    for(o=t[l];o--;){
        for(p=t[o][l];p--;){
            y=[f(o+1,p),f(o,p+1),f(o,p),f(o,p-1),f(o-1,p)],

            t[o][p]=m[y[d]('')]||t[o][p]
        }
    }
    t=t.map(function(x)x[d](''))[d]('\n');
    return t;
}

Original, 440 characters:

function (t){m={"10110":"b","11100":"d","01101":"Y","00111":"F","10100":";","00101":"V","00110":">","01100":"<","00100":"@"},s="split",d="join",l="length",t=t[s]('\n').splice(2),t=t.map(function(x) x[s]('')),f=function(i,j)i<0||i>=t[l]?0:(j<0||j>=t[i][l]?0:t[i][j]==' '?0:1);for(o=t[l];o--;){for(p=t[o][l];p--;){y=[f(o+1,p),f(o,p+1),f(o,p),f(o,p-1),f(o-1,p)],h=m[y[d]('')];if(h){t[o][p]=h}}}t=t.map(function(x) x[d](''))[d]('\n');return t;}

N.B. I've assumed that the first two input lines are actually irrelevant and the size of the following lines are a correct. I'm also reckoning I might be able to chop a few more chars off this when I get a chance!

share|improve this answer
1  
Replace the declaration of m to m={22:"b",28:"d",13:"Y",7:"F",20:";",5:"V",6:">",12:"<",4:"@"} then convert m's subscript with parseInt(): m[parseInt(y[d](''),2)]. This reduces the size to 373 characters. –  manatwork Jun 2 '12 at 16:29

Python, 259 chars

H=input()
W=input()+1
I=' '.join(raw_input()for i in' '*H)
for i in range(H):print''.join(map(lambda(s,a,b,c,d):(s*5+'dY<'+s+'bF>'+s+';V@'+' '*16)[16*(s==' ')+8*(a==' ')+4*(b==' ')+2*(c==' ')+(d==' ')],zip(I,I[1:]+' ',' '+I,I[W:]+' '*W,' '*W+I))[i*W:i*W+W-1])

The program reads the input into a single string I (with spaces separating the lines), zips up a list of 5-tuples containing the character and its four surrounding characters, then looks up the result character using string indexing.

share|improve this answer

PHP - 359 330 282 268 257 characters

<?php
$i=fgets(STDIN)+0;$w=fgets(STDIN)+1;$s='';$m='@<;d>0b0VY00F000';
for(;$i--;)$s.=fgets(STDIN);
for(;++$i<strlen($s);){
$b=trim($s[$i])?0:15;
foreach(array($i+1,$i+$w,$i-1,$i-$w)as$k=>$x)
$b|=pow(2,$k)*(isset($s[$x])&&trim($s[$x]));
echo $m[$b]?$m[$b]:$s[$i];}
share|improve this answer
    
@PhiNotPi It wasn't working because my locally saved test files had windows-style EOL \r\n. I updated my code to work with unix style EOL \n. –  Rusty Fausak Apr 12 '12 at 22:40
    
Ok, it seems to be working now. –  PhiNotPi Apr 12 '12 at 22:47

Python, 246 241

H=input();W=1+input()
S=' '
o=W*S
F=o+'\n'.join((raw_input()+o)[:W-1]for k in range(H))+o
print ''.join((16*x+'@;<d>b'+2*x+'V'+x+'Y'+x+'F'+3*x)[
16*(x>S)|8*(a>S)|4*(l>S)|2*(r>S)|(b>S)]for
x,a,l,r,b in zip(F[W:-W],F,F[W-1:],F[W+1:],F[2*W:]))

WC and test on sample 2, diffed with the output of the Ruby solution at the top:

t:~$ wc trans.py && python trans.py < lala2 > o && diff -q o ruby_out2_sample
  2 11 241 trans.py
t:~$
share|improve this answer

C# 591 563

string A(string t){var s=new StringReader(t);var h=int.Parse(s.ReadLine());var w=int.Parse(s.ReadLine());var lines=s.ReadToEnd().Split(new[]{"\r\n"},StringSplitOptions.None).Select(x=>x.ToCharArray()).ToArray();for(var i=0;i<h;i++)for(var j=0;j<w;j++){var c=lines[i][j];if(c==' ')continue;var n=(i>0?(lines[i-1][j]!=' '?1:0):0)+(i<h-1?(lines[i+1][j]!=' '?2:0):0)+(j>0?(lines[i][j-1]!=' '?4:0):0)+(j<w-1?(lines[i][j+1]!=' '?8:0):0);lines[i][j]=new[]{'@','V',';',c,'>','F','b',c,'<','Y','d',c,c,c,c,c}[n];}return string.Join("\r\n",lines.Select(l=>new string(l)));}
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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