# Question
Title: Evaluate the number of possible strings a regex can match
In a chatroom with a few people, a topic came up between me and them about how many possible strings a regex could match.

Your task is to build a program that can answer that question.

Your program will accept, as input, any regular expression as defined in this document as an "extended regular expression", such as:

```
^[A-Za-z0-9]{8}$

```

and output the total number of possible strings that match that expression, outputting `infinity` if there are infinitely many:

```
218340105584896

```

Your program may also output `too many` if there are more than 263-1 possible strings that match the regex; however, it must not output `infinity` unless there are actually infinitely many strings.

The shortest program to do the above wins.

# Answer
> 33 votes
# Python 3370

I got this to be about as functional as I could, and even got alternation to work (with correct double-count checking!). As far as I know this works for everything except lookarounds (because that would be crazy).

For anyone writing their own solution feel free to use/improve my methods as much as you like.

Code:

```
R=range;L=len;E=enumerate;I=int;F="Infinity";S=sum;H=chr;D=ord;J=lambda l:''.join(l);U=lambda s:J([H(i)if H(i) not in s else''for i in R(1,128)]);s=' \n\t';c=J((H(i)if H(i)not in s else'')for i in R(1,32));d,l,u=[J(H(i)for i in R(*n))for n in [[48,59],[97,123],[65,91]]];p='`~!@#$%^&*()-_=+[{]}\\|;:\'",<.>/?';Y={'\\s':s,'\\S':c+s+p+u+l+d,'\\d':d,'\\D':U(d),'\\w':u+l+'_','\\W':U(u+l+'_'),'[:alnum:]':u+l+d,'[:alpha:]':u+l,'[:ascii:]':U(''),'[:blank:]':' \t','[:cntrl:]':c,'[:digit:]':d,'[:graph:]':p+d+l+u,'[:lower:]':l,'[:print:]':p+d+l+u+s,'[:punct:]':p,'[:space:]':s,'[:upper:]':u,'[:word:]':l+u+'_','[:xdigit:]':d+'ABCDEF'};C=lambda l,n:[d+[l[i]]for i in R(L(l))for d in C(l[i+1:],n-1)]if n>0 else[[]];O=lambda x:S([all((c in s)for s in [(e[1]if any(e[1] not in Y for e in x)else Y[e[1]])if e[0]=='e'else(e[1]if e[0]=='t'else((Y[e[1]]if e[1]in Y else B(e[1]))if e[0]=='['else''))for e in x])for c in Y['[:ascii:]']])
def X(r):
 x=[];l=0;c=''
 for h in r:
    l+=I(h in'([')-I(h in')]')
    if l<1 and'|'==h:x+=[c];c=''
    else:c+=h
 x+=[c]
 if L(x)>1:
    o=0;m=[];u=[]
    for e in x:
     p,b=X(e)
     if p==F:return F,[]
     o+=p;m+=[('(',b)];u+=[b]
    return o-S([(-1)**(i%2)*T(s) for i in R(2,L(u)+1)for s in C(u,i)]),[('|',m)]
 u=[];o=[];m=[];w=1
 while r!='':
    h=r[0];z=0
    if h in'([{':
     l=1;i=1
     while l>0:k=r[i];l+=(k==h)-(k=={'(':')','[':']','{':'}'}[h]);i+=1
     u+=[(h,r[1:i-1])];z=i
    elif h=='\\':u+=[('e','\\'+eval("'\\%s'"%r[1]))]if r[1]in'nt'else[('e','\\'+r[1])];z=2
    elif h in ['*','+','?']:u+=[('{',h)];z=1
    elif h in'^$':return 0
    elif h=='.':u+=[('[','[:ascii:]')];z=1
    else:u+=[('t',h)];z=1
    r=r[z:]
 for t,g in u:
    if t=='(':p,b=X(g);o+=[p];m+=[('(',b)]
    elif t=='e':o+=[L(Y[g])]if g in Y else[1]
    elif t=='[':o+=[N(g)]
    elif t=='{':
     n=o[-1]
     try:o[-1]=S([n**r for r in Q(g)])
     except:return F,[]
    elif t=='t':o+=[1]
    if t!='(':m+=[(t,g)]
 for c in o:
    if c==F:return F,[]
    w*=c
 return w,m
def N(s):
 if s in Y:return L(Y[s])
 if(s[0],s[-1])==('[',']'):return 1
 n=(s[0]=='^');a=0
 if n:s=s[1:]
 while s!='':
    if L(s)>=3 and s[1]=='-':a+=D(s[2])-D(s[0])+1;s=s[3:];continue
    a+=1;s=s[1:]
 return 256*n+(-1)**n*a
def Q(s):
 if s=='?':return[0,1]
 if s[0]in'*+':return None
 if ','in s:
    l,h=s.split(',')
    return None if h==''else R(I(l),I(h)+1)
 return[I(s)]
def B(s):
 n=(s[0]=='^')
 if n:s=s[1:]
 a='';w=''
 while s!='':
    h=s[0]
    if 3<=L(s)and'-'==s[1]:
     for i in R(D(s[0]),D(s[2])+1):a+=H(i)
     s=s[3:];continue
    a+=h;s=s[1:]
 return J([c*(c not in a)for c in Y['[:ascii:]']])if n else a
def T(x):
 if all(e==[] for e in x):return 1
 for i,e in E(x):
    if L(e)>=2 and e[1][0]=='{':return S([T([[e[0]]*n+e[2:]]+x[:i]+x[i+1:])for n in Q(e[1][1])])
    if L(e)>=1:
     if e[0][0] == '(':return T([e[0][1]+e[1:]]+x[:i]+x[i+1:])
     if e[0][0]== '|':
        t=S(T([[s]+e[1:]]+x[:i]+x[i+1:])for s in e[0][1])
        u=[[s]for s in e[0][1]]
        return t-S((-1)**(j%2)*T(b)for j in R(2,L(u)+1)for b in C(u,j))
 if any(e==[]for e in x):return 0
 return O([e[0]for e in x])*T([e[1:]for e in x])
r=raw_input();e=[];l=0;c=''
for h in r:
 l+=I(h in'([')-I(h in')]')
 if l<1 and'|'==h:e+=[c];c=''
 else:c+=h
e+=[c];o=[];x=[]
for f in e:
 if '^'!=f[0]or'$'!=f[-1]:print F;quit()
 n,m=X(f[1:-1])
 if n==F:print F;quit()
 o+=[n];x+=[m]
print S(o)-S([(-1)**(i%2)*T(s) for i in R(2,L(x)+1)for s in C(x,i)])

```

Ungolfed:

```
controlchars = ''
for i in range(1,32):
    if chr(i) not in '\t\n':
        controlchars += chr(i)

CLASSES={
'\\s':' \t\n',
'\\S':controlchars+'!"#$%&\'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\]^_`abcdefghijklmnopqrstuvwxyz{|}~',
'\\d':'0123456789',
'\\D':controlchars+'\n\t !"#$%&\'()*+,-./:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\]^_`abcdefghijklmnopqrstuvwxyz{|}~',
'\\w':'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789_',
'\\W':controlchars+'\n\t !"#$%&\'()*+,-./:;<=>?@[\\]^`{|}~',
'[:alnum:]':'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789',
'[:alpha:]':'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ',
'[:ascii:]':controlchars+'\n\t !"#$%&\'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\]^_`abcdefghijklmnopqrstuvwxyz{|}~',
'[:blank:]':' \t',
'[:cntrl:]':controlchars,
'[:digit:]':'0123456789',
'[:graph:]':'!"#$%&\'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\]^_`abcdefghijklmnopqrstuvwxyz{|}~',
'[:lower:]':'abcdefghijklmnopqrstuvwxyz',
'[:print:]':'\n\t !"#$%&\'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\]^_`abcdefghijklmnopqrstuvwxyz{|}~',
'[:punct:]':'`~!@#$%^&*()-_=+[{]}\\|;:\'",<.>/?',
'[:space:]':' \t\n',
'[:upper:]':'ABCDEFGHIJKLMNOPQRSTUVWXYZ',
'[:word:]':'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789_',
'[:xdigit:]':'0123456789ABCDEF'
}

DELIMIT = {
'(':')',
')':'(',
'[':']',
']':'[',
'{':'}',
'}':'{'
}

def combos(lst,num):
    if num == 0:
        return [[]]
    combs = []
    for i in range(len(lst)):
        for c in combos(lst[i+1:],num-1):
            combs.append([lst[i]]+c)
    return combs

def count_regex(regex):
    exprs = []
    level = 0
    current = ''
    for char in regex:
        if char in '([':
            level += 1
        if char in ')]':
            level -= 1
        if char == '|' and level == 0:
            exprs.append(current)
            current = ''
        else:
            current += char
    exprs.append(current)

    comps = []
    expanded = []
    for e in exprs:
        if (e[0] != '^' or e[-1] != '$'):
            return 'Infinity'
        num,member = count_expr(e[1:-1])
        if num == 'Infinity':
            return 'Infinity'
        comps.append(num)
        expanded.append(member)

    total = sum(comps)
    for i in range(2,len(expanded)+1):
        for subset in combos(expanded,i):
            if i % 2 == 0:
                total -= count_doubles(subset)
            else:
                total += count_doubles(subset)
    return total

def count_expr(expr):
    exprs = []
    level = 0
    current = ''
    for char in expr:
        if char in '([':
            level += 1
        if char in ')]':
            level -= 1
        if char == '|' and level == 0:
            exprs.append(current)
            current = ''
        else:
            current += char
    exprs.append(current)

    if len(exprs) != 1:
        comps = 0
        members = []
        sub = []
        for e in exprs:
            comp,memb = count_expr(e)
            if comp == 'Infinity':
                return 'Infinity',[]
            comps += comp
            members.append(('(',memb))
            sub.append(memb)

        for i in range(2,len(sub)+1):
            for subset in combos(sub,i):
                if i % 2 == 0:
                    comps -= count_doubles(subset)
                else:
                    comps += count_doubles(subset)

        return comps,[('|',members)]

    sub = []
    while expr != '':
        char = expr[0]
        if char in ['(','[','{']:
            level = 1
            i = 1
            while level > 0:
                nchar = expr[i]
                if nchar == char: level += 1
                if nchar == DELIMIT[char]: level -= 1
                i += 1
            sub.append((char,expr[1:i-1]))
            expr = expr[i:]
        elif char == '\\':
            if expr[1] == 'n':
                sub.append(('e','\\'+'\n'))
                expr = expr[2:]
            elif expr[1] == 't':
                sub.append(('e','\\'+'\t'))
                expr = expr[2:]
            else:
                sub.append(('e','\\'+expr[1]))
                expr = expr[2:]
        elif char in ['*','+','?']:
            sub.append(('{',char))
            expr = expr[1:]
        else:
            if char in '^$':
                return 0
            if char == '.':
                sub.append(('[','[:ascii:]'))
                expr = expr[1:]
            else:
                sub.append(('t',char))
                expr = expr[1:]

    components = []
    members = []
    for t,string in sub:
        if t == '(':
            comp,memb = count_expr(string)
            components.append(comp)
            members.append(('(',memb))
        elif t == 'e':
            if string in CLASSES:
                components.append(len(CLASSES[string]))
            else:
                components.append(1)
        elif t == '[':
            components.append(count_class(string))
        elif t == '{':
            num = components[-1]
            try:
                components[-1] = sum([num**r for r in count_quantifier(string)])
            except TypeError:
                return 'Infinity',[]
        elif t == 't':
            components.append(1)

        if t != '(':
            members.append((t,string))

    total = 1
    for c in components:
        if c == 'Infinity':
            return 'Infinity',[]
        total *= c
    return total,members

def count_class(string):
    if string in CLASSES:
        return len(CLASSES[string])
    if string[0] == '[' and string[-1] == ']':
        return 1
    negate = (string[0] == '^')
    if negate: string = string[1:]
    avail_count = 0
    while string != '':
        char = string[0]
        if len(string) >= 3:
            if string[1] == '-':
                first,last = string[0],string[2]
                avail_count += ord(last)-ord(first)+1
                string = string[3:]
                continue
        avail_count += 1
        string = string[1:]
    if negate:
        return 256-avail-count
    return avail_count

def count_quantifier(string):
    if string == '?':
        return [0,1]
    if string[0] in '*+':
        return None
    if ',' in string:
        low,high = string.split(',')
        if high == '':
            return None
        return range(int(low),int(high)+1)
    return [int(string)]

def bracket_string(string):
    negate = (string[0] == '^')
    if negate: string = string[1:]
    avail = ''
    while string != '':
        char = string[0]
        if len(string) >= 3:
            if string[1] == '-':
                first,last = string[0],string[2]
                for i in range(ord(first),ord(last)+1):
                    avail += chr(i)
                string = string[3:]
                continue
        avail += char
        string = string[1:]
    if negate:
        new = ''
        for c in CLASSES['[:ascii:]']:
            if c not in avail:
                new += c
        return new
    return avail

def overlap(es):
    chars=['' for i in range(len(es))]
    for i,e in enumerate(es):
        if e[0] == 'e':
            if any(e[1] not in CLASSES for e in es):
                chars[i] = e[1]
            else:
                chars[i] = CLASSES[e[1]]

    for i,e in enumerate(es):
        if e[0] == 't':
            chars[i] = e[1]

    for i,e in enumerate(es):
        if e[0] == '[':
            if e[1] in CLASSES:
                chars[i] = CLASSES[e[1]]
            else:
                chars[i] = bracket_string(e[1])

    total = 0
    for c in CLASSES['[:ascii:]']:
        has = True
        for chs in chars:
            if c not in chs:
                has = False
                break
        if has:
            total += 1
    return total

def count_doubles(exprs):
    if all(e==[] for e in exprs):
        return 1

    for i,expr in enumerate(exprs):
        if len(expr) >= 2 and expr[1][0] == '{':
            rng = count_quantifier(expr[1][1])
            total = 0
            for n in rng:
                total += count_doubles([ [expr[0]]*n+expr[2:] ] + exprs[:i] + exprs[i+1:])
            return total

    for i,expr in enumerate(exprs):
        if len(expr) >= 1 and expr[0][0] == '(':
            return count_doubles([ expr[0][1]+expr[1:] ] + exprs[:i] + exprs[i+1:] )

    if any(e==[] for e in exprs):
        return 0

    for i,expr in enumerate(exprs):
        if expr[0][0] == '|':
            total = 0
            subs = []
            for sub_expr in expr[0][1]:
                subs.append([sub_expr])
                total += count_doubles([ [sub_expr]+expr[1:] ] + exprs[:i] + exprs[i+1:])

            for j in range(2,len(subs)+1):
                for subset in combos(subs,j):
                    if j % 2 == 0:
                        total -= count_doubles(subset)
                    else:
                        total += count_doubles(subset)

            return total

    over = overlap([e[0] for e in exprs])
    if over == 0:
        return 0
    return  over * count_doubles([e[1:] for e in exprs])

reg = raw_input('Regex: ')
print count_regex(reg)

```

Here are some relevant test cases I have confirmed:

```
Regex: ^[A-Za-z0-9]{8}$
218340105584896

Regex: ^([a-b]*)$
Infinity

Regex: ^([0-9]|[a-e])([a-e]|[A-E])$|^[a-f]{2}$
161

Regex: ^[a-z]{2}$|^[0-9]?[a-z]{2,3}$|^a[a-z]?$
200773

Regex: ^([a-z]|[a-e]|[A-E]|[3-4]|[D-G])$
35

Regex: ^\(.)\(.)\2\1$
16129*

Regex: ^(a)\1?$
2

Regex: ^[[:space:]]$|^\t$
3

```

\*This is actually different in the golfed and ungolfed due to a one character difference in what is defined as valid ascii. I believe the golfed is the more correct one.

To confirm its accuracy further tests could be done, please let me know of any errors (I honestly would not be surprised if there were quite a few).

---
Tags: code-golf
---


title: Finish lazy parentheses

text:
# Question
Title: Finish lazy parentheses
The parentheses on my keyboard are all worn out, and I want to avoid using them as much as possible. Your challenge is to balance a line containing parentheses by adding them in before and after each line.

This is similar to TI-Basic's automatic parentheses and string closure (i.e. `Output(1, 1, "Hello, World!`). It also saves precious bytes from a program!

Example input:

```
This line has no parentheses
alert(Math.max(1, 2
1+1)*2).toString()
function() { alert('Hello, World!'); })(

```

Example (possible) output:

```
This line has no parentheses
alert(Math.max(1, 2))
((1+1)*2).toString()
(function() { alert('Hello, World!'); })()

```

Specification:

* For each line of input,

+ Add as many open parentheses to the beginning and close parentheses to the end of the line as needed to balance the parentheses in the line

    - The definition of "balance" is:

        * Same amount of `(` and `)` in the line
            * For every substring starting from the beginning of the string, this substring must not have more closing parentheses than opening parentheses

            + For example, `(foo))(bar` is not balanced because `(foo))` has more closing parentheses than opening parentheses
    + You may add extra unnecessary parentheses if you want to, if it makes your code shorter
    + You do not need to worry about string literals or anything like that, assume that all parentheses need balancing
* Output each line with parentheses balanced

This is , so the shortest code in bytes will win!

# Answer
# GolfScript, 23 bytes

```
n/{"()"1/{.2$\-,*}%*n}/

```

The loophole I'm exploiting is the ruling that:

> You may add extra unnecessary parentheses if you want to, if it makes your code shorter

Basically, for each line, this code counts the number of characters on the line that are *not* opening parentheses, and prepends that many extra opening parentheses to the line, and then does the same for closing parentheses. This is incredibly inefficient, but does ensure that all the parentheses on the output line are balanced.

For example, given the input:

```
This line has no parentheses
alert(Math.max(1, 2
1+1)*2).toString()
function() { alert('Hello, World!'); })(

```

this program will output:

```
((((((((((((((((((((((((((((This line has no parentheses))))))))))))))))))))))))))))
(((((((((((((((((alert(Math.max(1, 2)))))))))))))))))))
(((((((((((((((((1+1)*2).toString())))))))))))))))
(((((((((((((((((((((((((((((((((((((function() { alert('Hello, World!'); })()))))))))))))))))))))))))))))))))))))

```

Ps. You can also test this code online.
> 22 votes

# Answer
# Perl, 32 = 31 + 1 or 73 = 72 + 1 (minimized parentheses)

## 32 = 31 + 1: with extra unnecessary parentheses

**Edits:**

* Fix, parentheses now counted with `y///`.
* Unnecessary variable `$a` removed.

```
$_="("x y/)//.s|$|")"x y/(//|er

```

It is used with the run-time switch `-p` (+1 byte).

**Test file `input.txt`:**

```
This line has no parentheses
alert(Math.max(1, 2
1+1)*2).toString()
function() { alert('Hello, World!'); })(
(foo))(bar
)))(((
((
))

```

**Command line:**

```
perl -p script.pl <input.txt

```

or

```
perl -pe '$_="("x y/)//.s|$|")"x y/(//|er' <input.txt

```

**Result:**

```
This line has no parentheses
alert(Math.max(1, 2))
(((1+1)*2).toString())
(((function() { alert('Hello, World!'); })()))
(((foo))(bar))
((()))((()))
(())
(())

```

**Ungolfed:**

The algorithm is simple, just add the counterpart for each found parentheses.

```
$_ =                     # $_ is provided as input by switch `-p` and
                         # it is printed afterwards as output.
                         # y/X// is used to count the character 'X' in $_
    '(' x y/)//          # add opening parentheses for each closing parentheses
    . s|$|')' x y/(//|er # go right before the end of line and insert
                         # closing parentheses for each opening parentheses
                         # in the original string

```

## 73 = 72 + 1: adding *minimum* number of parentheses

This script only adds the *minimum* number of parentheses to get a balanced output.

```
$a=y/()//cdr;1while$a=~s/\(\)//g;$_=$a=~y/)(/(/dr.$_;s|$|$a=~y/()/)/dr|e

```

It is used with the run-time switch `-p` (+1 byte).

```
perl -pe "$a=y/()//cdr;1while$a=~s/\(\)//g;$_=$a=~y/)(/(/dr.$_;s|$|$a=~y/()/)/dr|e" <input.txt

```

**Result:**

```
This line has no parentheses
alert(Math.max(1, 2))
((1+1)*2).toString()
(function() { alert('Hello, World!'); })()
((foo))(bar)
((()))((()))
(())
(())

```

**Ungolfed:**

```
$a = y/()//cdr;            # filter parentheses and store in $a
1 while $a =~ s/\(\)//g;   # remove matching parentheses
$_ = $a =~ y/)(/(/dr . $_; # add missing opening parentheses at start of string
s|$|$a=~y/()/)/dr|e        # insert missing closing parentheses at end of string

```

## 81 = 80 + 1: adding *minimum* number of parentheses

This is an older method to add the minimum number of parentheses for a balanced output.

```
my($l,$r);s/[()]/($&eq")"&&($r&&$r--||++$l))||$r++/ger;$_="("x$l.$_;s/$/")"x$r/e

```

It uses Perl 5.14 (because of the non-destructive substitution modifier) and the run-time switch `-p` (+1 byte).

```
perl -p script.pl <input.txt

```

**Result:**

```
This line has no parentheses
alert(Math.max(1, 2))
((1+1)*2).toString()
(function() { alert('Hello, World!'); })()
((foo))(bar)
((()))((()))
(())
(())

```

**Ungolfed:**

```
# The while loop is added by option "-p".
LINE:
while (<>) {

    # $_ contains the current line
    my ($l, $r); # initializes $l and $r (to undef/kind of indirect 0)
    # Modifiers for the following substitution of $_:
    # /g: process all parentheses
    # /e: evaluate code
    # /r: does not change the original input string $_ (Perl 5.14)
    s/[()]/
        # $& contains the matched parentheses
        # $r is a balance level counter; at the end $r contains
        #    the number of needed closing parentheses
        # $l is the number of needed opening parentheses;
        #    if $r would go negative, then an opening parentheses
        #    is missing and $l is increases and $r remains zero.
        (
            $& eq ")" &&   # case ")"
            ($r && $r--    # close a parentheses group and update balance counter
                || ++$l)   # or update $l if an opening parentheses is needed
        )
        || $r++            # case "(": increase balance counter
    /ger;
    $_ = "(" x $l . $_;    # add opening parentheses at the begin of line
    s/$/")" x $r/e         # add closing parentheses before the line end

# the remainder is added by run-time switch "-p"
} continue {
    print or die "-p destination: $!\n";
}

```
> 7 votes

# Answer
# Python 2.7 3: 62 60 58 bytes

```
while 1:s=input();c=s.count;print('('*c(')')+s+')'*c('('))

```

Not super golfed, but you know. I might be able to squeeze some more bytes out if I really tried.

For each line, outputs `(`\*the number of `)` in the line, then the line, then `)`\*the number of `(` in the line. If I understand the rules correctly, this will always provide valid output.

Exits by throwing an exception, as a result of the way I did input. (Input is always a hard part of these problems.) If this isn't acceptable, it'll cost me a few bytes to fix, though I'm not yet sure how many.

Example output:

```
This line has no parentheses
alert(Math.max(1, 2))
(((1+1)*2).toString())
(((function() { alert('Hello, World!'); })()))

```
> 4 votes

# Answer
# Pure Bash, 72 bytes

Uses the same algorithm as @undergroundmonorail's answer:

```
while read a;do
o=${a//[!(]}
c=${a//[!)]}
echo ${c//)/(}$a${o//(/)}
done

```

Output:

```
$ ./lazyparens.sh < input.txt
This line has no parentheses
alert(Math.max(1, 2))
(((1+1)*2).toString())
(((function() { alert('Hello, World!'); })()))
$

```
> 1 votes

---
Tags: code-golf, balanced-string
---


title: Draw the Utah Teapot

text:
# Question
Title: Draw the Utah Teapot
The Utah teapot, originally created by Martin Newell, is a convenient object for testing 3D graphics programs.

The task is to create a wireframe image of the teapot in perspective projection. To encourage the idea of a *source-code application*, the viewing and camera control may be isolated and excluded from the count. This is so the parameters and input file may be modified and the code re-used to generate diverse images, but it is not necessary to create a full-fledged utility that accepts complicated command-line arguments or such. A "hackerly" balance is sought.

ref. StackOverflow: How do Bezier Patches work in the Utah Teapot?

So there are three subtasks here:

* read-in the teapot data in its original format.
* subdivide the patch data using deCasteljau splitting or other method. Other methods are using Bezier basis matrices and evaluating the polynomials (standard refs, like Foley and van Dam, Newmann and Sproull), or Bernstein basis methods (which are still beyond me).
* project the points to 2D (if the language does not support 3D natively) and draw the outline of each small patch as seen from an Eye point whose view is centered on a LookAt point and whose vertical axis is aligned with the vertical axis of the teapot (ie. draw it "upright" from a nice vantagepoint).

Assuming that reading line-oriented text data from a file is little trouble, this challenge is really about getting *hands-on* with Bi-Cubic Bezier patch data.

Since the simple normal test for backface culling is not sufficient (the patches are not all oriented outward), no hidden-line or -surface removal is necessary. As a wireframe, it should look just fine with the back visible. The appearance may be improved by adjusting the line-width depending upon the distance from the eye, but this is not strictly necessary (my own programs do not do this).

This is both and . Answers competing in the golf should include a count as normal. But submissions in unusual languages are very much encouraged, even if they're not particularly short.

For Kolmogorov-complexity enthusiasts, there is a more concise dataset where the full set may be reconstructed by adding rotations and mirroring of patches. And in Jim Blinn's *A Trip Down the Graphics Pipeline*, there is an even more concise method of generation by using the fact that the individual patches have rotational or other symmetries. The entire body (or lid) can be described by a single Bezier curve which is rotated around the y-axis. The spout and handles can be described by the two curves of their profile, and then selecting the intermediate control points to approximate a circular extrusion.

# Answer
# Processing (java), 314 (237 without camera control)

Not including the array definitions:

```
void setup(){size(640,480,P3D);}void draw(){background(0);noFill();stroke(255);translate(width/2,height/2,70);scale(30);rotateX(map(mouseX,0,width,0,TWO_PI));rotateY(map(mouseY,0,height,0,TWO_PI));for(int[] p:patches){beginShape();for(int pt:p){vertex(data[pt-1][0],data[pt-1][1],data[pt-1][2]);}endShape(CLOSE);}}

```

Data array definitions:

```
float [][] data = {{1.4,0.0,2.4},
{1.4,-0.784,2.4},
{0.784,-1.4,2.4},
{0.0,-1.4,2.4},
{1.3375,0.0,2.53125},
{1.3375,-0.749,2.53125},
{0.749,-1.3375,2.53125},
{0.0,-1.3375,2.53125},
{1.4375,0.0,2.53125},
{1.4375,-0.805,2.53125},
{0.805,-1.4375,2.53125},
{0.0,-1.4375,2.53125},
{1.5,0.0,2.4},
{1.5,-0.84,2.4},
{0.84,-1.5,2.4},
{0.0,-1.5,2.4},
{-0.784,-1.4,2.4},
{-1.4,-0.784,2.4},
{-1.4,0.0,2.4},
{-0.749,-1.3375,2.53125},
{-1.3375,-0.749,2.53125},
{-1.3375,0.0,2.53125},
{-0.805,-1.4375,2.53125},
{-1.4375,-0.805,2.53125},
{-1.4375,0.0,2.53125},
{-0.84,-1.5,2.4},
{-1.5,-0.84,2.4},
{-1.5,0.0,2.4},
{-1.4,0.784,2.4},
{-0.784,1.4,2.4},
{0.0,1.4,2.4},
{-1.3375,0.749,2.53125},
{-0.749,1.3375,2.53125},
{0.0,1.3375,2.53125},
{-1.4375,0.805,2.53125},
{-0.805,1.4375,2.53125},
{0.0,1.4375,2.53125},
{-1.5,0.84,2.4},
{-0.84,1.5,2.4},
{0.0,1.5,2.4},
{0.784,1.4,2.4},
{1.4,0.784,2.4},
{0.749,1.3375,2.53125},
{1.3375,0.749,2.53125},
{0.805,1.4375,2.53125},
{1.4375,0.805,2.53125},
{0.84,1.5,2.4},
{1.5,0.84,2.4},
{1.75,0.0,1.875},
{1.75,-0.98,1.875},
{0.98,-1.75,1.875},
{0.0,-1.75,1.875},
{2.0,0.0,1.35},
{2.0,-1.12,1.35},
{1.12,-2.0,1.35},
{0.0,-2.0,1.35},
{2.0,0.0,0.9},
{2.0,-1.12,0.9},
{1.12,-2.0,0.9},
{0.0,-2.0,0.9},
{-0.98,-1.75,1.875},
{-1.75,-0.98,1.875},
{-1.75,0.0,1.875},
{-1.12,-2.0,1.35},
{-2.0,-1.12,1.35},
{-2.0,0.0,1.35},
{-1.12,-2.0,0.9},
{-2.0,-1.12,0.9},
{-2.0,0.0,0.9},
{-1.75,0.98,1.875},
{-0.98,1.75,1.875},
{0.0,1.75,1.875},
{-2.0,1.12,1.35},
{-1.12,2.0,1.35},
{0.0,2.0,1.35},
{-2.0,1.12,0.9},
{-1.12,2.0,0.9},
{0.0,2.0,0.9},
{0.98,1.75,1.875},
{1.75,0.98,1.875},
{1.12,2.0,1.35},
{2.0,1.12,1.35},
{1.12,2.0,0.9},
{2.0,1.12,0.9},
{2.0,0.0,0.45},
{2.0,-1.12,0.45},
{1.12,-2.0,0.45},
{0.0,-2.0,0.45},
{1.5,0.0,0.225},
{1.5,-0.84,0.225},
{0.84,-1.5,0.225},
{0.0,-1.5,0.225},
{1.5,0.0,0.15},
{1.5,-0.84,0.15},
{0.84,-1.5,0.15},
{0.0,-1.5,0.15},
{-1.12,-2.0,0.45},
{-2.0,-1.12,0.45},
{-2.0,0.0,0.45},
{-0.84,-1.5,0.225},
{-1.5,-0.84,0.225},
{-1.5,0.0,0.225},
{-0.84,-1.5,0.15},
{-1.5,-0.84,0.15},
{-1.5,0.0,0.15},
{-2.0,1.12,0.45},
{-1.12,2.0,0.45},
{0.0,2.0,0.45},
{-1.5,0.84,0.225},
{-0.84,1.5,0.225},
{0.0,1.5,0.225},
{-1.5,0.84,0.15},
{-0.84,1.5,0.15},
{0.0,1.5,0.15},
{1.12,2.0,0.45},
{2.0,1.12,0.45},
{0.84,1.5,0.225},
{1.5,0.84,0.225},
{0.84,1.5,0.15},
{1.5,0.84,0.15},
{-1.6,0.0,2.025},
{-1.6,-0.3,2.025},
{-1.5,-0.3,2.25},
{-1.5,0.0,2.25},
{-2.3,0.0,2.025},
{-2.3,-0.3,2.025},
{-2.5,-0.3,2.25},
{-2.5,0.0,2.25},
{-2.7,0.0,2.025},
{-2.7,-0.3,2.025},
{-3.0,-0.3,2.25},
{-3.0,0.0,2.25},
{-2.7,0.0,1.8},
{-2.7,-0.3,1.8},
{-3.0,-0.3,1.8},
{-3.0,0.0,1.8},
{-1.5,0.3,2.25},
{-1.6,0.3,2.025},
{-2.5,0.3,2.25},
{-2.3,0.3,2.025},
{-3.0,0.3,2.25},
{-2.7,0.3,2.025},
{-3.0,0.3,1.8},
{-2.7,0.3,1.8},
{-2.7,0.0,1.575},
{-2.7,-0.3,1.575},
{-3.0,-0.3,1.35},
{-3.0,0.0,1.35},
{-2.5,0.0,1.125},
{-2.5,-0.3,1.125},
{-2.65,-0.3,0.9375},
{-2.65,0.0,0.9375},
{-2.0,-0.3,0.9},
{-1.9,-0.3,0.6},
{-1.9,0.0,0.6},
{-3.0,0.3,1.35},
{-2.7,0.3,1.575},
{-2.65,0.3,0.9375},
{-2.5,0.3,1.125},
{-1.9,0.3,0.6},
{-2.0,0.3,0.9},
{1.7,0.0,1.425},
{1.7,-0.66,1.425},
{1.7,-0.66,0.6},
{1.7,0.0,0.6},
{2.6,0.0,1.425},
{2.6,-0.66,1.425},
{3.1,-0.66,0.825},
{3.1,0.0,0.825},
{2.3,0.0,2.1},
{2.3,-0.25,2.1},
{2.4,-0.25,2.025},
{2.4,0.0,2.025},
{2.7,0.0,2.4},
{2.7,-0.25,2.4},
{3.3,-0.25,2.4},
{3.3,0.0,2.4},
{1.7,0.66,0.6},
{1.7,0.66,1.425},
{3.1,0.66,0.825},
{2.6,0.66,1.425},
{2.4,0.25,2.025},
{2.3,0.25,2.1},
{3.3,0.25,2.4},
{2.7,0.25,2.4},
{2.8,0.0,2.475},
{2.8,-0.25,2.475},
{3.525,-0.25,2.49375},
{3.525,0.0,2.49375},
{2.9,0.0,2.475},
{2.9,-0.15,2.475},
{3.45,-0.15,2.5125},
{3.45,0.0,2.5125},
{2.8,0.0,2.4},
{2.8,-0.15,2.4},
{3.2,-0.15,2.4},
{3.2,0.0,2.4},
{3.525,0.25,2.49375},
{2.8,0.25,2.475},
{3.45,0.15,2.5125},
{2.9,0.15,2.475},
{3.2,0.15,2.4},
{2.8,0.15,2.4},
{0.0,0.0,3.15},
{0.0,-0.002,3.15},
{0.002,0.0,3.15},
{0.8,0.0,3.15},
{0.8,-0.45,3.15},
{0.45,-0.8,3.15},
{0.0,-0.8,3.15},
{0.0,0.0,2.85},
{0.2,0.0,2.7},
{0.2,-0.112,2.7},
{0.112,-0.2,2.7},
{0.0,-0.2,2.7},
{-0.002,0.0,3.15},
{-0.45,-0.8,3.15},
{-0.8,-0.45,3.15},
{-0.8,0.0,3.15},
{-0.112,-0.2,2.7},
{-0.2,-0.112,2.7},
{-0.2,0.0,2.7},
{0.0,0.002,3.15},
{-0.8,0.45,3.15},
{-0.45,0.8,3.15},
{0.0,0.8,3.15},
{-0.2,0.112,2.7},
{-0.112,0.2,2.7},
{0.0,0.2,2.7},
{0.45,0.8,3.15},
{0.8,0.45,3.15},
{0.112,0.2,2.7},
{0.2,0.112,2.7},
{0.4,0.0,2.55},
{0.4,-0.224,2.55},
{0.224,-0.4,2.55},
{0.0,-0.4,2.55},
{1.3,0.0,2.55},
{1.3,-0.728,2.55},
{0.728,-1.3,2.55},
{0.0,-1.3,2.55},
{1.3,0.0,2.4},
{1.3,-0.728,2.4},
{0.728,-1.3,2.4},
{0.0,-1.3,2.4},
{-0.224,-0.4,2.55},
{-0.4,-0.224,2.55},
{-0.4,0.0,2.55},
{-0.728,-1.3,2.55},
{-1.3,-0.728,2.55},
{-1.3,0.0,2.55},
{-0.728,-1.3,2.4},
{-1.3,-0.728,2.4},
{-1.3,0.0,2.4},
{-0.4,0.224,2.55},
{-0.224,0.4,2.55},
{0.0,0.4,2.55},
{-1.3,0.728,2.55},
{-0.728,1.3,2.55},
{0.0,1.3,2.55},
{-1.3,0.728,2.4},
{-0.728,1.3,2.4},
{0.0,1.3,2.4},
{0.224,0.4,2.55},
{0.4,0.224,2.55},
{0.728,1.3,2.55},
{1.3,0.728,2.55},
{0.728,1.3,2.4},
{1.3,0.728,2.4},
{0.0,0.0,0.0},
{1.5,0.0,0.15},
{1.5,0.84,0.15},
{0.84,1.5,0.15},
{0.0,1.5,0.15},
{1.5,0.0,0.075},
{1.5,0.84,0.075},
{0.84,1.5,0.075},
{0.0,1.5,0.075},
{1.425,0.0,0.0},
{1.425,0.798,0.0},
{0.798,1.425,0.0},
{0.0,1.425,0.0},
{-0.84,1.5,0.15},
{-1.5,0.84,0.15},
{-1.5,0.0,0.15},
{-0.84,1.5,0.075},
{-1.5,0.84,0.075},
{-1.5,0.0,0.075},
{-0.798,1.425,0.0},
{-1.425,0.798,0.0},
{-1.425,0.0,0.0},
{-1.5,-0.84,0.15},
{-0.84,-1.5,0.15},
{0.0,-1.5,0.15},
{-1.5,-0.84,0.075},
{-0.84,-1.5,0.075},
{0.0,-1.5,0.075},
{-1.425,-0.798,0.0},
{-0.798,-1.425,0.0},
{0.0,-1.425,0.0},
{0.84,-1.5,0.15},
{1.5,-0.84,0.15},
{0.84,-1.5,0.075},
{1.5,-0.84,0.075},
{0.798,-1.425,0.0},
{1.425,-0.798,0.0}
};

int [][] patches = {
    {32},
{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16},
{4,17,18,19,8,20,21,22,12,23,24,25,16,26,27,28},
{19,29,30,31,22,32,33,34,25,35,36,37,28,38,39,40},
{31,41,42,1,34,43,44,5,37,45,46,9,40,47,48,13},
{13,14,15,16,49,50,51,52,53,54,55,56,57,58,59,60},
{16,26,27,28,52,61,62,63,56,64,65,66,60,67,68,69},
{28,38,39,40,63,70,71,72,66,73,74,75,69,76,77,78},
{40,47,48,13,72,79,80,49,75,81,82,53,78,83,84,57},
{57,58,59,60,85,86,87,88,89,90,91,92,93,94,95,96},
{60,67,68,69,88,97,98,99,92,100,101,102,96,103,104,105},
{69,76,77,78,99,106,107,108,102,109,110,111,105,112,113,114},
{78,83,84,57,108,115,116,85,111,117,118,89,114,119,120,93},
{121,122,123,124,125,126,127,128,129,130,131,132,133,134,135,136},
{124,137,138,121,128,139,140,125,132,141,142,129,136,143,144,133},
{133,134,135,136,145,146,147,148,149,150,151,152,69,153,154,155},
{136,143,144,133,148,156,157,145,152,158,159,149,155,160,161,69},
{162,163,164,165,166,167,168,169,170,171,172,173,174,175,176,177},
{165,178,179,162,169,180,181,166,173,182,183,170,177,184,185,174},
{174,175,176,177,186,187,188,189,190,191,192,193,194,195,196,197},
{177,184,185,174,189,198,199,186,193,200,201,190,197,202,203,194},
{204,204,204,204,207,208,209,210,211,211,211,211,212,213,214,215},
{204,204,204,204,210,217,218,219,211,211,211,211,215,220,221,222},
{204,204,204,204,219,224,225,226,211,211,211,211,222,227,228,229},
{204,204,204,204,226,230,231,207,211,211,211,211,229,232,233,212},
{212,213,214,215,234,235,236,237,238,239,240,241,242,243,244,245},
{215,220,221,222,237,246,247,248,241,249,250,251,245,252,253,254},
{222,227,228,229,248,255,256,257,251,258,259,260,254,261,262,263},
{229,232,233,212,257,264,265,234,260,266,267,238,263,268,269,242},
{270,270,270,270,279,280,281,282,275,276,277,278,271,272,273,274},
{270,270,270,270,282,289,290,291,278,286,287,288,274,283,284,285},
{270,270,270,270,291,298,299,300,288,295,296,297,285,292,293,294},
{270,270,270,270,300,305,306,279,297,303,304,275,294,301,302,271},
{306}
};

```

More readable version:

```
void setup() {
  size(640,480,P3D);
}

void draw() {
  background(0);
  noFill();
  stroke(255);
  translate(width/2,height/2,70);
  scale(30);
  rotateX(map(mouseX,0,width,0,TWO_PI));
  rotateY(map(mouseY,0,height,0,TWO_PI));
  for (int[] p:patches) {
    beginShape();
    for (int pt:p) {
      vertex(data[pt-1][0],data[pt-1][2],data[pt-1][2]);
    }
    endShape(CLOSE);
  }
}

```

And some pics:

Another version with some interesting effects:

```
void setup(){size(640,480,P3D);}
void draw(){
  background(0);noFill();stroke(255);
  translate(width/2,height/2,70);scale(30);
  rotateX(map(mouseX,0,width,0,TWO_PI));rotateY(map(mouseY,0,height,0,TWO_PI));
  for(int[] p:patches){
    //beginShape(QUADS);
    for(int pt:p){
      for(int pu:p){
        //vertex(data[pu-1][0],data[pu-1][4],data[pu-1][2]);
        line(data[pt-1][0],data[pt-1][5],data[pt-1][2],data[pu-1][0],data[pu-1][6],data[pu-1][2]);
    }}
    //endShape(CLOSE);
  }
}

```
> 10 votes

# Answer
## Postscript

Not fully golfed, but this illustrates a different approach than deCasteljau subdivision: evaluating the basis polynomial. Uses mat.ps.

```
(mat.ps)run[    % load matrix library, begin dictionary construction

/N 17
/C [ 0 7 4 ]   % Cam
/E [ 0 0 40 ] % Eye
/R 0 roty 120 rotx 90 rotz   % Rot: pan tilt twist
          matmul   matmul

/f(teapot)(r)file
/t{token pop exch pop}      % parse a number or other ps token
/s{(,){search not{t exit}if t 3 1 roll}loop}  % parse a comma-separated list
/r{token pop{[f 99 string readline pop s]}repeat}>>begin   % parse a count-prefixed paragraph of csv numbers
[/P[f r]/V[f r]/v{1 sub V exch get}        % Patches and Vertices and vert lookup shortcut
/B[[-1 3 -3 1][3 -6 3 0][-3 3 0 0][1 0 0 0]]              % Bezier basis matrix
/A{dup dup mul exch 2 copy mul 3 1 roll 1 4 array astore} % x->[x^3 x^2 x 1]
/M{[1 index 0 4 getinterval 2 index 4 4 getinterval       % flattened matrix->rowXcolumn matrix
3 index 8 4 getinterval 4 index 12 4 getinterval]exch pop}
/J{ C{sub}vop R matmul 0 get                              % perspective proJection  [x y z]->[X Y]
    aload pop E aload pop
    4 3 roll div exch neg
    4 3 roll add 1 index mul 4 1 roll
    3 1 roll sub mul}
>>begin

300 400 translate
1 14 dup dup scale div currentlinewidth mul setlinewidth  % global scale
/newline { /line {moveto /line {lineto} store} store } def
newline
P{
    8 dict begin
        [exch{v J 2 array astore}forall]/p exch def   % load patch vertices and project to 2D
        /X[p{0 get}forall] M B exch matmul B matmul def  % multiply control points by Bezier basis
        /Y[p{1 get}forall] M B exch matmul B matmul def

        0 1 N div 1 1 index .2 mul add{A/U exch def   % interpolate the polynomial over (u,v)/(N)
            /UX U X matmul def
            /UY U Y matmul def
            0 1 N div 1 1 index .2 mul add{A/V exch 1 array astore transpose def
                /UXV UX V matmul def
                /UYV UY V matmul def
                UXV 0 get 0 get
                UYV 0 get 0 get line
            }for
            newline
        }for

        0 1 N div 1 1 index .2 mul add{A/V exch def   % interpolate the polynomial over (u,v)/(N)
            /V [V] transpose def
            /XV X V matmul def
            /YV Y V matmul def
            0 1 N div 1 1 index .2 mul add{A/U exch 1 array astore transpose def
                /UXV U XV matmul def
                /UYV U YV matmul def
                UXV 0 get 0 get
                UYV 0 get 0 get line
            }for
            newline
        }for

    end

    %exit
}forall
stroke

```

## 1112

Stripping out the vertical lines, and discounting the parameters, yields this 1112 char version. Uses mat.ps.

```
(mat.ps)run[    % 12

/N 17
/C [ 0 7 4 ]   % Cam
/E [ 0 0 40 ] % Eye
/R 0 roty 120 rotx 90 rotz   % Rot: pan tilt twist
          matmul   matmul

/f(teapot)(r)file/t{token pop exch pop}/s{(,){search not{t exit}if t   % 1100
3 1 roll}loop}/r{token pop{[f 99 string readline pop
s]}repeat}>>begin[/P[f r]/V[f r]/v{1 sub
V exch get}/B[[-1 3 -3 1][3 -6 3 0][-3 3 0 0][1 0 0 0]]/A{dup dup mul exch
2 copy mul 3 1 roll 1 4 array astore}/M{[1 index 0 4 getinterval 2 index 4 4 getinterval
3 index 8 4 getinterval 4 index 12 4 getinterval]exch pop}/J{C{sub}vop R matmul 0 get
aload pop E aload pop 4 3 roll div exch neg 4 3 roll add 1 index mul 4 1 roll
3 1 roll sub mul}>>begin 300 400 translate
1 14 dup dup scale div currentlinewidth mul setlinewidth
/newline{/line{moveto/line{lineto}store}store}def newline
P{8 dict begin[exch{v J 2 array astore}forall]/p
exch def/X[p{0 get}forall] M B exch matmul B matmul
def/Y[p{1 get}forall] M B exch matmul B matmul def
0 1 N div 1 1 index .2 mul add{A/U exch def/UX U X matmul def/UY U Y matmul def
0 1 N div 1 1 index .2 mul add{A/V exch 1 array astore transpose
def/UXV UX V matmul def/UYV UY V matmul def UXV 0 get 0 get UYV 0 get 0 get line}for
newline}for end}forall stroke

```
> 12 votes

---
Tags: code-golf, graphical-output
---


title: One Letter Swap

text:
# Question
Title: One Letter Swap
The largest forum on the web, called postcount++ decided to make a new forum game. In this game, the goal is to post the word, but the word has to have one letter added, removed, or changed. Your boss wanted you to write a program which gets the word, and the UNIX dictionary, as you work for company who has more intelligent forum with more intelligent forum games, and wants to destroy the competition (hey, it's your boss, don't discuss with him, you get lots of cash from your job anyway).

Your program will get two arguments, the word, and the dictionary. Because the user managing the program (yes, an user, your company doesn't have resources to run bots) is not perfect, you should normalize the case in both. The words in dictionary may have ASCII letters (both upper-case and lower-case, but it should be ignored during comparison), dashes, apostrophes, and non-consecutive spaces in middle. They won't be longer than 78 characters. You have to output list of words that would be accepted in the game, to break the fun of people who think of words manually.

This is an example of your expected program, checking for similar words to `golf`.

```
> ./similar golf /usr/share/dict/words
Goff
Wolf
gold
golfs
goof
gulf
wolf

```

The `/usr/share/dict/words` is a list of words, with line break after each. You can easily read that with fgets(), for example.

The company you work in doesn't have much punch cards (yes, it's 2014, and they still use punch cards), so don't waste them. Write as short program as possible. Oh, and you were asked to not use built-in or external implementations of Levenshtein distance or any similar algorithm. Something about Not Invented Here or backdoors that apparently the vendor inserted into the language (you don't have proof of those, but don't discuss with your boss). So if you want distance, you will have to implement it yourself.

You are free to use any language. Even with punch cards, the company has the access to most modern of programming languages, such as ~~Cobol~~ Ruby or Haskell or whatever you want. They even have GolfScript, if you think it's good for string manipulation (I don't know, perhaps...).

The winner gets 15 reputation points from me, and probably lots of other points from the community. The other good answers will get 10 points, and points from community as well. You heard that points are worthless, but most likely that they will replace dolars in 2050. That wasn't confirmed however, but it's good idea to get points anyway.

# Answer
# GolfScript, 59 chars

```
{32|}%"*"%.|(:w;{:x,),{:^[x>.1>]{.[^w=]\+}%{^x<\+w=},},},n*

```

Sure, GolfScript is *great* for string manipulation!

What GolfScript is *not* so good at is handling file I/O or command-line arguments. Thus, this program expects to receive all its input via stdin: the first non-blank line is taken to be the target word, while the remaining lines should contain the dictionary. On a Unixish system, you can run this code e.g. with:

```
(echo golf; cat /usr/share/dict/words) | ruby golfscript.rb similar.gs

```

On my Ubuntu Linux box, the output of the above command is:

```
goff
wolf
gold
golfs
goof
gulf

```

Note that all the words are converted to lowercase, and any duplicates are eliminated; thus, unlike your sample output, mine does not list `Wolf` and `wolf` separately. Based on your challenge description, I assume this is acceptable.

Also, the code is really slow, since it uses a fairly brute force approach, and doesn't use even obvious optimizations like checking that the length of the candidate word matches that of the target word ± 1. Still, it does manage to go through the full, unfiltered `/usr/share/dict/words` list in... um... I'll let you know when it finishes, OK?

<sup>**Edit:** OK, it took about 25 minutes, but it did finish.</sup>
> 4 votes

# Answer
# Bash + coreutils, 99 bytes

Either I totally misunderstood the question (@lambruscoAcido's answer gives very different results), or this is a fairly straightforward regexp application:

```
for((i=0;i<${#1};i++)){
a=${1:0:i}
b=${1:i+1}
egrep -i "^($a$b|$a.$b|$a.${1:i}|$1.)$" $2
}|sort -u

```

Output:

```
$ ./similar.sh golf /usr/share/dict/words
Goff
gold
golf
golfs
goof
gulf
wolf
Wolf
$

```
> 6 votes

# Answer
# Python 3, 291 characters

Very straightforward, and thus not very clever. But with a big yummy generator tangle and optimized slowness. Because you don't want to leave your allocated computation time unused, do you?

```
from itertools import*
from sys import*
a=argv[1].lower()
r,l=range,len
n=l(a)
print('\n'.join((b for b in(s.strip()for s in open(argv[2]).readlines())if l(b)>n-2and b.lower()in(''.join(compress(a,(i!=j for j in r(n))))for i in r(n))or n==l(b)and sum(1for i in r(n)if a[i]!=b.lower()[i])<2)))

```
> 3 votes

# Answer
# Python, 174 chars:

Quick and to the point.

```
import re;from sys import*;w=argv[1]
print"\n".join(set(sum([re.findall(r"\b%s%s?[^'\n]?%s\b"%(w[:i],w[i],w[i+1:]),open(argv[2]).read(),re.I)for i in range(len(w))],[]))-{w})

```

Example:

```
python similar.py golf /usr/share/dict/words

```

Output:

```
goof
gola
gulf
gold
gol
gowf
goli
Golo
Gulf
goaf
Wolf
Goll
Rolf
wolf
goff
Gold

```

I suppose the OS X words file just has more entries.
> 2 votes

# Answer
# Scala - ~~403~~ 130

\[Updated\]: completely updated because former solution also allowed for permuted letters. Does not use regex or any builtin tools.

```
def f(x:String,d:List[String])={for{y<-d;c=(x zip y filter(t=>t._1!=t._2)length);n=y.length-x.length;if c<2&n==0|c==0&n==1}yield y

```

Ungolfed:

```
def f(x:String, d:List[String]) = {
  for {
    y <- d
    c = (x zip y filter (t=>t._1!=t._2) length)  // #letter changes.
    n = y.length-x.length                        // Difference in word length.
    if c<2 & n==0 | c==0 & n==1
  } yield y
}

```

Usage:

```
f("golf", io.Source.fromFile("/usr/share/dict/words").getLines.toList)

```
> 1 votes

# Answer
## Haskell - 219

```
import System.Environment
import Data.Char
u@(x:a)%w@(y:b)|x==y=a%b|1>0=1+minimum[a%w,u%b,a%b]
x%y=max(length x)$length y
main=do[w,d]<-getArgs;readFile d>>=mapM putStrLn.filter((==1).(%map toLower w).map toLower).words

```
> 0 votes

# Answer
# Rebol - 213

```
set[i d]split system/script/args" "r:[skip i | i skip]repeat n length? i[append r compose[|(poke s: split i 1 n 'skip s)|(head remove at copy i n)]]foreach w read/lines to-file d[if all[w != i parse w r][print w]]

```

Ungolfed (with some some comments):

```
set [i d] split system/script/args " "

; build parse rule
r: [skip i | i skip]       ; RULE - one letter added (prefix and postfix)

; sub-rule for each letter in word
repeat n length? i [
    append r compose [
        | (poke s: split i 1 n 'skip s)     ; RULE - letter changed
        | (head remove at copy i n)         ; RULE - letter removed
    ]
]

foreach w read/lines to-file d [
    if all [w != i parse w r] [print w]
]

```

Usage example (tested in Rebol 3 on OS X Lion):

```
$ rebol similar.reb golf /usr/share/dict/words
goaf
goff
gol
gola
Gold
gold
goli
Goll
Golo
goof
gowf
Gulf
gulf
Rolf
Wolf
wolf

```

Below is the `parse` rule created to match similar words to *golf*:

```
[
    skip "golf"
  | "golf" skip
  | skip "o" "l" "f"
  | "olf"
  | "g" skip "l" "f"
  | "glf"
  | "g" "o" skip "f"
  | "gof"
  | "g" "o" "l" skip
  | "gol"
]

```
> 0 votes

# Answer
# Python (103):

```
f=lambda x:[a for a in open('/usr/share/dict/words')if len(x)==len(a)&sum(b!=c for b,c in zip(a,x))==1]

```

Quite efficient, I think. Also, I like how well this golfed in Python.
> -1 votes

---
Tags: code-golf, string
---


# Question
Title: I challenge you to generate the following sequence
I challenge you to generate the following sequence till 100 terms through any programming language in shortest characters possible.
The sequence is like this :-

```
1 2 3 4 5 10 20 30 40 50 100 200 300 400 500 ........

```

The output needs to be like this (above) only, nothing extra.

Remember, You can use `+` and `-` **only** and for mathematical calculations **only** (`++` and `--` are also allowed) and no other mathematical function like `tan()`, `log()`, `pow()`, ......etc.

Also, You cannot use any character variables in your code.

# Answer
> 6 votes
## GolfScript (21 chars)

If

> You can use + and - only for mathematical calculations

means what it says then:

```
[6,1>~{4$10*}95*]' '*

```

If it is intended to say

> The only mathematical operators you can use are + and -

then the multiplications can be replaced with string manipulation at the same character count:

```
[6,1>~{4$0`+}95*]' '*

```

Dissection:

```
[         # Start gathering values into an array
  6,1>~   # Dump the numbers 1 to 5 onto the stack
  {       # Beginning of loop body
    4$    # Copy the 5th item on the stack

```

Here the variants differ

```
    10*   # Multiply it by 10

```

or

```
    0`+   # Postpend '0'

```

And then merge again

```
  }95*    # Loop 95 times, so we end up with 100 items on the stack
]         # Gather those 100 items into an array
' '*      # Space-separate them

```

# Answer
> 4 votes
## Perl, 38 bytes

Disclaimer: The restrictions of the changed question are not too clear to me.

```
for$i(0..19){print$_.0 x$i.$"for 1..5}

```

The code uses variables with integer values except for `$"` which is used for the separation space. It can be easily replaced by `' '` (+1 byte).

Mathematical operations are not used, the code only contains string concatenations and the repetition operator.

The result are 100 numbers:

```
1 2 3 4 5 10 20 30 40 50 100 200 300 400 500 1000 2000 3000 4000 5000 10000 20000 30000 40000 50000 100000 200000 300000 400000 500000 1000000 2000000 3000000 4000000 5000000 10000000 20000000 30000000 40000000 50000000 100000000 200000000 300000000 400000000 500000000 1000000000 2000000000 3000000000 4000000000 5000000000 10000000000 20000000000 30000000000 40000000000 50000000000 100000000000 200000000000 300000000000 400000000000 500000000000 1000000000000 2000000000000 3000000000000 4000000000000 5000000000000 10000000000000 20000000000000 30000000000000 40000000000000 50000000000000 100000000000000 200000000000000 300000000000000 400000000000000 500000000000000 1000000000000000 2000000000000000 3000000000000000 4000000000000000 5000000000000000 10000000000000000 20000000000000000 30000000000000000 40000000000000000 50000000000000000 100000000000000000 200000000000000000 300000000000000000 400000000000000000 500000000000000000 1000000000000000000 2000000000000000000 3000000000000000000 4000000000000000000 5000000000000000000 10000000000000000000 20000000000000000000 30000000000000000000 40000000000000000000 50000000000000000000

```

**Ungolfed:**

```
for $i (0..19) { # 20 * 5 = 100 numbers
    for $_ (1..5) {
        print $_     # first digit
            . 0 x $i # zeros
            . $"     # separator (space)
    }
}

```

# Answer
> 4 votes
## Python 60

```
r=range
for i in r(20):
 for j in r(1,6):print str(j)+'0'*i,

```

---

Thanks to @ace for pointing out that this was way too long.

## Python 113

```
from itertools import*
i=j=0
for x in cycle(range(1,6)):
 i+=1;print str(x)+'0'*j,
 if i%5==0:j+=1
 if i>99:break

```

# Answer
> 3 votes
# GolfScript, ~~30~~ 25 characters (~~26~~ 23 newline separated)

```
;6,1>{.{10*}%}20*][]*' '*

```

Commented:

```
;         # pop the input string (empty)
6,1>      # generate [1 2 3 4 5]
{.{10*}%} # duplicate the array and multiply everything by 10
20*       # do this 20 times (5 * 20 = 100)
]         # wrap the whole stack in an array
[]*       # flatten
' '*      # join by space

```

~~I really don't like the repetition at the end, but GS doesn't provide a `flat_map` or `flatten` of any sort.~~ Thanks @PeterTaylor for providing a way to flatten!

If we can separate by newlines instead of spaces, then **23 characters**:

```
;6,1>{.{10*}%}20*][]*n*

```

# Answer
> 3 votes
## APL (~~17~~ 24)

```
,⍉10⊥¨(⍳5)∘.{⍺,1↓⍵/0}⍳20

```

# Answer
> 2 votes
# C, 93

```
i;main(j,k){for(;++i;)for(j=0;++j<6;){for(putchar(48+j),k=0;++k<i;putchar(48));putchar(32);}}

```

// it draws nice patterns on the terminal...

# Answer
> 2 votes
# Java,185

```
class g {public static void main(String[] args){for(int x=0;x<20;x++){for(int i=1;i<6;i++){System.out.print(""+i); for(int j=0;j<x;j++){System.out.print("0");}System.out.print(" ");}}}}

```

# Answer
> 2 votes
# Julia - 38

```
[print(i,"0"^j," ") for i=1:5,j=0:19];

```

### Output:

```
1 2 3 4 5 10 20 30 40 50 100 200 300 400 500 1000 2000 3000 4000 5000 10000 20000 30000 40000 50000 100000 ...

```

# Answer
> 2 votes
# PHP - 61

```
for($i=0;$i++<21;)for($j=0;$j++<5;)echo str_pad($j,$i,0).' ';

```

---
Tags: code-golf, sequence, restricted-source
---


title: Is it a prime? w/o math

text:
# Question
Title: Is it a prime? w/o math
Write a program or function in any language that tells if the input is a prime number.

* The input is a **string** representing a natural number in base-10.
* The output is one of the two strings "Prime" or "Not!!" which correctly identifies the input.
* Arithmetic operators, bit-wise operators, numeric variables and constants, "math-stuff" in general, etc... are not allowed anywhere in your program. You should use **string operations** to do all necessary "calculations".
* You can compare string lengths (which are numbers) - but -10 to your score if you don't.
* Your program should work on any length input (given enough memory and time).
* Lowest byte count (UTF-8) wins.

# Answer
> 6 votes
## Ruby, 64 - 10 = 54

```
puts ('1
'..gets).map{?1}*''=~/^1?$|^(11+?)\1+$/?'Not!!': :Prime

```

This iterates from the string '1' (plus a newline) to the input string, using Ruby's built in string iteration method which looks an awful lot like adding 1, but which doesn't technically create a high-level numeric variable at any point. It uses the fact that there will be n iterations for an input of n to create an n-length string, then uses a regular expression to determine if that string can be grouped into identical substrings.

# Answer
> 15 votes
# Ruby: 52 - 10 = 42

Using a variation of that famous prime-matching regex.

```
puts ?_*gets.to_i=~/^(_|(__+?)\2+)$/?"Not!!":"Prime"

```

Just to be clear: `?_*gets.to_i` is a string operation that appends `"_"` to itself *n* times, where *n* is the input number. As I see it no string lengths are compared, so that should satisfiy the 10 character bonus criterium.

# Answer
> 3 votes
## Perl 52-10=42

**Implementation**

```
print((('-'x$ARGV[0])=~/^.$|^(..+?)\1+$/)?Not:Prime)

```

**Demo**

```
$ seq 1 10|xargs -I{} bash -c "echo -n '{} '  && perl Prime.pl {} && echo"
1 Not
2 Prime
3 Prime
4 Not
5 Prime
6 Not
7 Prime
8 Not
9 Not
10 Not

```

# Answer
> 1 votes
## ECMAScript 6, 159 - 10 = 149

Sounds like a task for regex. I/O with `prompt`/`alert` as usual.

```
for(s=prompt(u=""); /[^0]/.test(s); )
  s=s.replace(/(.)(0*)$/,(_,d,t)=>u+="x"," 012345678"[d]+t.replace(/0/g,"9"))
alert(/^((xx+)\2+|x?)$/.test(u)?"Not!!":"Prime")

```

The while loop decrements the decimal number by one each iteration purely by regex. The final regex matches a string consisting of a composite number of x's, by first matching one factor, then another by repeating the first factor one for the rest of the string.

# Answer
> 1 votes
# Javascript 266

```
function N(a){function b(a){return P.every(function(b){if(n=b,i=a.length,j=b.length,j>i) return;if(j==i) return 1;while(n.length<i)n+=b;return n.length!=i})}if(q=A,A!=a)for(;q.length.toString()!=a;)b(q)&&P.push(q),q+=A;console.log(b(q)?"Prime":"Not!!")}A="0",P=[A+A]

```

Creates a function called N which will print the desired result. The unminified version looks like this. I did a hand minify to clean up some variables and then ran that through uglify and then hand minified that again.

```
// A a string of "0" for using to generate long strings
// P is the store for all known primes
A="0", P=[A+A];
function N(val) {
  function _isPrime(str) {
    // go through all the known primes and return true
    // if we don't match on any of them
    return P.every(function(prime) {
      // prime is some known string whose length is a prime number
      tsr = prime, strlen = str.length, primelen = prime.length;
      // if the string we're checking has fewer chars than
      // this then it's not a prime
      if(strlen < primelen) return 0;
      // if the string we're checking has the same number of chars
      // as the the prime we're checking against then it is a prime
      if(primelen == strlen) return 1;
      // Keep incrementing our temporary string with the prime we're
      // checking. we'll break out of the loop once the temporary string
      // is greater than or equal to the string we're testing
      while(tsr.length < strlen) {
        tsr += prime;
      }
      return !(tsr.length == strlen)
    });
  }
  // start with a string of one unit
  nstr = A
  if(A!=val) {
    // keep incrementing the string so that we can compile a list
    // of known primes smaller than this value
    while(nstr.length.toString() !== val) {
      if(_isPrime(nstr)) {
        P.push(nstr);
      }
      nstr += A;
    }
  }
  console.log(_isPrime(nstr) ? "Prime" : "Not!!");
}

```

Tested it using this snippet:

```
for(var X=0;X<10;X++) {
  console.log('checking: ' + X);
  N(X.toString());
}

```

# Answer
> 0 votes
## Bash 66 - 10 = 56

**Implementation**

```
[[ -z `printf %$1s|grep -P "^(..+?)\1+$"` ]]&&echo Prime||echo Not

```

**Demo**

```
$ seq 1 10|xargs -I{} bash -c "echo -n '{} '  && ./Prime.sh {}"
1 Prime
2 Prime
3 Prime
4 Not
5 Prime
6 Not
7 Prime
8 Not
9 Not
10 Not

```

# Answer
> 0 votes
## Python 3, 109-10 = 89

```
print(['Not','Prime'][(lambda i:not any(' '*i==(' '*u)*v for u in range(i)for v in range(i)))(int(input()])

```

Not comparing string lengths, but string inclusion. Cross posted from duplicate Determine if a number is prime without using arithmetic

---
Tags: code-challenge, string, primes
---


title: Evolution of the 'x'

text:
# Question
Title: Evolution of the 'x'
Given is a board of variable size with a maximum size of 5 times 5 fields. Every field kann be filled with an 'x'. If it is not filled with an 'x', it is filled with an 'o'.

The starting state of every board is given (see below). With each board, 10 rounds have to be played (at max, conditions: see below) and the evolution of the x must be watched.

One round works the following way:

1. every 'x' spreads to orthogonally bordering fields, but dissapears itself
2. each time two 'x' are on one field, they neutralize each other

The evolution of all 'x' in each round has to happen simultaneously. Example:

```
    o o o            o x o
    o x o     ->     x o x
    o o o            o x o

```

With each round of evolution, you have to see if the board gets emptied of 'x'. Is it not empty, a repeating pattern could be present. If this is also not the case, we give up the analysis of the evolution. Additionally you have to print out the maximum percentage of x fields for every starting board (rounded down to whole numbers).

**Input:**

The input data can be found here (Pastebin) This data contains 100 starting states. As already mentioned, the boards vary in size. The number of rows is stated with number n from 1 to 5, followed by n rows that contain only 'x' and 'o', represent the starting pattern. Every row of a board has 1 to 5 fields.

**Output:**

The complete result must be printed out, one printed row for each starting board in the following form:

```
    Round {0-10}: {repetition/empty/giveup}, {0-100} percent maximum-fill

```

**Examples:**

Example 1:

```
    Input: 2       Starting state: x o x
           xox                     x x
           xx

                          Round 1: x x o
                                   o x

                          Round 2: x o x
                                   o x

                          Round 3: o x o
                                   o o

                          Round 4: x o x   -> The pattern repeats:
                                   o x        It is the same as in round 2,
                                              therefore we stop. Maximum fill was
                                              in the starting state with four times 'x'
                                              of 5 fields altogether,
                                              so we have 4/5 = 80 %.

    Output: Round 4: repetition, 80 percent maximum-fill

```

Example 2:

```
    Input: 1       Starting state: x x
           xx

                          Round 1: x x    ->  We already have a repetition, because
                                              the pattern is the same as in the starting
                                              state. The board is always filled 100 %.

    Output: Round 1: repetition, 100 percent maximum-fill

```

After eight dayst I will mark the working answer with the fewest characters as the winner. Additionally i will post the correct output for the 100 starting boards (input).

You can use your prefered (programming/scripting/whatever) language.

Have fun!

PS: If you have questions, feel free to ask.

PPS: In respect of the original creators: For people capable of speaking german, the question was taken from DO NOT CLICK IF YOU DO NOT WANT SPOILERS here. Since the official time for completing the challenge has ended, I wanted to see if someone could come up with a short and elegant solution.

**22.04.2014:**

**Challenge Done! Winner marked as accepted. Correct output:**

```
    Round 10: giveup, 50 percent maximum-fill
    Round 5: empty, 66 percent maximum-fill
    Round 1: repetition, 100 percent maximum-fill
    Round 1: empty, 100 percent maximum-fill
    Round 4: repetition, 100 percent maximum-fill
    Round 4: repetition, 70 percent maximum-fill
    Round 2: repetition, 60 percent maximum-fill
    Round 4: empty, 88 percent maximum-fill
    Round 10: giveup, 50 percent maximum-fill
    Round 5: repetition, 80 percent maximum-fill
    Round 10: repetition, 80 percent maximum-fill
    Round 1: empty, 80 percent maximum-fill
    Round 3: repetition, 60 percent maximum-fill
    Round 4: repetition, 48 percent maximum-fill
    Round 9: empty, 41 percent maximum-fill
    Round 10: giveup, 92 percent maximum-fill
    Round 10: giveup, 53 percent maximum-fill
    Round 10: giveup, 66 percent maximum-fill
    Round 6: repetition, 50 percent maximum-fill
    Round 10: giveup, 88 percent maximum-fill
    Round 10: giveup, 76 percent maximum-fill
    Round 10: giveup, 68 percent maximum-fill
    Round 10: giveup, 40 percent maximum-fill
    Round 10: giveup, 100 percent maximum-fill
    Round 10: giveup, 71 percent maximum-fill
    Round 2: empty, 81 percent maximum-fill
    Round 6: repetition, 36 percent maximum-fill
    Round 10: giveup, 61 percent maximum-fill
    Round 10: giveup, 60 percent maximum-fill
    Round 4: repetition, 66 percent maximum-fill
    Round 10: giveup, 72 percent maximum-fill
    Round 3: empty, 80 percent maximum-fill
    Round 10: giveup, 50 percent maximum-fill
    Round 10: giveup, 83 percent maximum-fill
    Round 7: repetition, 37 percent maximum-fill
    Round 9: repetition, 85 percent maximum-fill
    Round 5: repetition, 40 percent maximum-fill
    Round 5: repetition, 60 percent maximum-fill
    Round 4: empty, 80 percent maximum-fill
    Round 10: giveup, 60 percent maximum-fill
    Round 4: repetition, 46 percent maximum-fill
    Round 6: repetition, 42 percent maximum-fill
    Round 10: giveup, 72 percent maximum-fill
    Round 4: repetition, 70 percent maximum-fill
    Round 4: repetition, 80 percent maximum-fill
    Round 6: repetition, 50 percent maximum-fill
    Round 4: repetition, 56 percent maximum-fill
    Round 10: giveup, 60 percent maximum-fill
    Round 10: giveup, 54 percent maximum-fill
    Round 10: giveup, 66 percent maximum-fill
    Round 2: repetition, 40 percent maximum-fill
    Round 2: repetition, 40 percent maximum-fill
    Round 6: repetition, 75 percent maximum-fill
    Round 7: empty, 85 percent maximum-fill
    Round 10: giveup, 50 percent maximum-fill
    Round 6: repetition, 70 percent maximum-fill
    Round 2: empty, 66 percent maximum-fill
    Round 1: empty, 66 percent maximum-fill
    Round 3: empty, 100 percent maximum-fill
    Round 3: empty, 66 percent maximum-fill
    Round 8: repetition, 42 percent maximum-fill
    Round 1: empty, 60 percent maximum-fill
    Round 2: repetition, 100 percent maximum-fill
    Round 2: repetition, 83 percent maximum-fill
    Round 4: repetition, 66 percent maximum-fill
    Round 6: repetition, 75 percent maximum-fill
    Round 4: empty, 66 percent maximum-fill
    Round 10: giveup, 61 percent maximum-fill
    Round 10: giveup, 56 percent maximum-fill
    Round 4: empty, 66 percent maximum-fill
    Round 6: repetition, 33 percent maximum-fill
    Round 3: empty, 57 percent maximum-fill
    Round 3: repetition, 100 percent maximum-fill
    Round 6: repetition, 73 percent maximum-fill
    Round 10: giveup, 50 percent maximum-fill
    Round 6: repetition, 50 percent maximum-fill
    Round 10: giveup, 73 percent maximum-fill
    Round 5: empty, 80 percent maximum-fill
    Round 10: giveup, 61 percent maximum-fill
    Round 3: repetition, 53 percent maximum-fill
    Round 10: giveup, 33 percent maximum-fill
    Round 10: giveup, 80 percent maximum-fill
    Round 10: giveup, 63 percent maximum-fill
    Round 10: giveup, 70 percent maximum-fill
    Round 10: giveup, 84 percent maximum-fill
    Round 7: repetition, 70 percent maximum-fill
    Round 10: repetition, 57 percent maximum-fill
    Round 10: giveup, 55 percent maximum-fill
    Round 6: repetition, 36 percent maximum-fill
    Round 4: repetition, 75 percent maximum-fill
    Round 10: giveup, 72 percent maximum-fill
    Round 10: giveup, 64 percent maximum-fill
    Round 10: giveup, 84 percent maximum-fill
    Round 10: giveup, 58 percent maximum-fill
    Round 10: giveup, 60 percent maximum-fill
    Round 10: giveup, 53 percent maximum-fill
    Round 4: repetition, 40 percent maximum-fill
    Round 4: empty, 40 percent maximum-fill
    Round 10: giveup, 50 percent maximum-fill
    Round 10: giveup, 68 percent maximum-fill

```

# Answer
## Perl, ~~308, 304, 305, 293, 264~~, 262

**Edit:** A bug crept in after one of recent edits, causing wrong output for empty boards (test suite output was OK). Since `Round 0` in given output format can mean only that there can be empty boards in the input (though none is in test suite), the bug had to be fixed. Quick fix meant byte count increase (by 1, actually) - not an option, of course. Therefore, I had to golf it a little bit more.

Run with `-p` (+1 added to count), reads from STDIN. Requires 5.014 because of `r` substitution modifier.

```
(@a,%h,$m)=('',map<>=~y/ox\n/\0!/rd,1..$_);for$n(0..10){$_="Round $n: ".($h{$_="@a"}++?repetition:(($.=100*y/!///y/ //c)<$m?$.:$m=$.)?giveup:empty).", $m percent maximum-fill\n";@a=/g/?map{$_=$a[$i=$_];y//!/cr&(s/.//r.P^P.s/.$//r^$a[$i+1]^$a[$i-1])}0..$#a:last}

```

i.e.

```
# '-p' switch wraps code into the 'while(<>){....}continue{print}' loop,
# which reads a line from STDIN into $_, executes '....' and prints contents
# of $_. We use it to read board height and print current board's result.

# First line reads board's state into @a array, a line per element, at the same
# time replacing 'o' with 'x00', 'x' with '!' and chomping trailing newlines.
# '!' was chosen because it's just like 'x01' except 5th bit (which is not important)
# but saves several characters in source code.

# Note: array is prepended with an empty line, which automatically remains in this
# state during evolution, but saves us trouble of checking if actual (any non-empty)
# line has neighboring line below.

# %h hash and $m hold seen states and maximum fill percentage for current board,
# they are initialized to undef i.e empty and 0.

(@a,%h,$m)=('',map<>=~y/ox\n/\0!/rd,1..$_);

# /
# Then do required number of evolutions:

for$n(0..10){

# Stringify board state, i.e. concatenate lines with spaces ($") as separators.
# Calculate fill percentage - divide number of '!' by number of non-spaces.
# Note: using $. magick variable automatically takes care of rounding.
# Construct output string. It's not used if loop gets to next iteration.
# Check if current state was already seen (at the same time add it to %h)
# and if fill percentage is 0.

$_="Round $n: "
    .($h{$_="@a"}++?repetition:(($.=100*y/!///y/ //c)<$m?$.:$m=$.)?giveup:empty)
    .", $m percent maximum-fill\n";

# /
# Next is funny: if output string contains 'g' (of 'giveup' word), then evolve
# further, otherwise break-out of the loop.

    @a=/g/
        ?map{

# Do evolution round. Act of evolution for a given line is none other than
# XOR-ing 4 strings: itself shifted right, itself shifted left, line above, line
# below. Result of this operation is truncated to original length using bitwise '&'.
# Note, when shifting string right or left we prepend (append) not an ascii-0,
# but 'P' character. It's shorter, and 4th and 6th bits will be annihilated anyway.

            $_=$a[$i=$_];
            y//!/cr
            &(s/.//r.P
            ^P.s/.$//r
            ^$a[$i+1]
            ^$a[$i-1])
        }0..$#a
        :last
}

```
> 4 votes

# Answer
# **C# - 1164 chars**

This is my first participation in code-golf so please be indulgent ;-)

I know, I am far off the best results - really amazing by the way!

But I thought I'd share my solution in C# anyway.

```
using System;using System.Collections.Generic;using System.IO;using System.Linq;using System.Net;class Program{static void Main(string[] args){new WebClient().DownloadFile("http://mc.capgemini.de/challenge/in.txt",@"D:\in.txt");var a=File.ReadAllLines(@"D:\in.txt");int l=0;while(l<a.Length){int n=Int32.Parse(a[l]);var b=a.Skip(l+1).Take(n).ToArray();var f=new List<string[]>{b};var d=0;string g=null;while(d<10){var s=f.Last();if(s.All(e=>e.All(c=>c=='o'))){g="empty";break;}var h=new string[n];for(int r=0;r<n;r++){var k="";for(int c=0;c<b[r].Length;c++){int x=0;try{if(s[r][c-1]=='x')x++;}catch{}try{if(s[r][c+1]=='x')x++;}catch{}try{if(s[r-1][c]=='x')x++;}catch{}try{if(s[r+1][c]=='x')x++;}catch{}k+=((x%2)==1)?'x':'o';}h[r]=k;}d++;f.Add(h);var w=false;for(int i=0;i<f.Count-1;i++){var m=f[i];if (!h.Where((t,y)=>t!=m[y]).Any())w=true;}if(w){g="repetition";break;}}if(d==10&&g==null)g="giveup";File.AppendAllLines(@"D:\out.txt",new[]{string.Format("Round {0}: {1}, {2} percent maximum-fill",d,g,f.Select(z=>{int t=0;int x=0;foreach(var c in z.SelectMany(s=>s)){t++;if(c=='x')x++;}return(int)Math.Floor((double)x/t*100);}).Concat(new[]{0}).Max())});l=l+n+1;}}}

```

Solely the using directives already count 97 characters - so I think it is going to be quite hard to achieve the rest within less than 200 characters.

It is a fairly iterative approach, making use of LINQ in many places. I also included the downloading of the input file and writing of the output file into the code.

Here is one little more readable version:

```
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Net;

class Program
{
    static void Main(string[] args)
    {
        // Download the file
        new WebClient().DownloadFile("http://mc.capgemini.de/challenge/in.txt", @"D:\in.txt");
        // Read of lines of downloaded file
        var a = File.ReadAllLines(@"D:\in.txt");
        // Line index in input file
        int l = 0;
        while (l < a.Length)
        {
            // Parse number of rows to take
            int n = Int32.Parse(a[l]);

            // Take the n rows
            var b = a.Skip(l + 1).Take(n).ToArray();
            var f = new List<string[]> { b };
            var d = 0;
            string g = null;
            while (d < 10)
            {
                // Last state consists only of o's? ->
                var s = f.Last();
                if (s.All(e => e.All(c => c == 'o')))
                {
                    g = "empty";
                    break;
                }
                // In h we will build up the new state
                var h = new string[n];
                // Loop through all rows of initial state
                for (int r = 0; r < n; r++)
                {
                    // This is our new row we will build up for the current state
                    var k = "";
                    // Count number of orthogonal adjacent x's
                    // And catch potential OutOfRangeExceptions
                    for (int c = 0; c < b[r].Length; c++)
                    {
                        int x = 0;
                        try { if (s[r][c - 1] == 'x') x++; }
                        catch { }
                        try { if (s[r][c + 1] == 'x') x++; }
                        catch { }
                        try { if (s[r - 1][c] == 'x') x++; }
                        catch { }
                        try { if (s[r + 1][c] == 'x') x++; }
                        catch { }
                        // Is number of adjacent x's odd? -> character will be 'x'
                        // otherwise -> 'o'
                        k += ((x % 2) == 1) ? 'x' : 'o';
                    }
                    // Add the new row to the current state
                    h[r] = k;
                }
                // Increase round count
                d++;
                // Add the new state to our state collection
                f.Add(h);
                // Now check, whether it is a repetition by comparing the last state (h) with all other states
                bool w = false;
                for (int i = 0; i < f.Count - 1; i++)
                {
                    var m = f[i];
                    if (!h.Where((t, y) => t != m[y]).Any())
                        w = true;
                }
                if (w)
                {
                    g = "repetition";
                    break;
                }
            }
            // Check whether we reached maximum AND the last round wasn't a repetition
            if (d == 10 && g == null)
                g = "giveup";
            // Now we append the final output row to our text file
            File.AppendAllLines(@"D:\out.txt",
                new[]
                    {
                        string.Format("Round {0}: {1}, {2} percent maximum-fill",
                        d,
                        g,
                        // Here we select all rates of x's per state
                        // and then grab the maximum of those rates
                        f.Select(z =>
                            {
                                int t=0;
                                int x=0;
                                foreach (char c in z.SelectMany(s => s))
                                {
                                    t++;
                                    if(c=='x')
                                        x++;
                                }
                                return (int) Math.Floor((double) x / t *100);
                            }).Concat(new[] {0}).Max())
                    });
            // finally we shift our index to the next (expected) number n in the input file
            l = l + n + 1;
        }
    }
}

```
> 3 votes

# Answer
# J - 275 char

Oh, all these I/O specifications! Such a shamefully large score for J, in the end. Takes input on STDIN with a trailing newline, and assumes there aren't any carriage returns (`\r`) in the input. Here's the result of applying it to the sample input file in the question.

```
stdout;,&LF&.>}:(".@{~&0(('Round ',":@(#->/@t),': ',(empty`repetition`giveup{::~2<.#.@t=.11&=@#,0={:),', ',' percent maximum-fill',~0":>./)@(100*1&=%&(+/"1)_&~:)@,.@(a=:(a@,`[@.(e.~+.10<#@[)(_*_&=)+[:~:/((,-)(,:|.)0 1)|.!.0=&1){:)@,:@('ox'&i.^_:)@{.;$: ::]@}.)}.)];._2[1!:1]3

```

Ungolfed: (I may add a more thorough and J-newbie-friendly explanation later.)

```
input   =: ];._2 [ 1!:1]3
convert =: 'ox'&i. ^ _:               NB. 'x'=>1  'o'=>0  else=>infinity
spread  =: ((,-)(,:|.)0 1) |.!.0 =&1  NB. x spreading outwards
cover   =: (_*_&=) + [: ~:/ spread    NB. collecting x`s and removing tiles not on board
iterate =: (iterate@, ` [ @. (e.~ +. 10<#@[) cover) {:
percent =: 100 * 1&= %&(+/"1) _&~:    NB. percentage of x at each step
max     =: 0 ": >./
stat    =: 11&=@# , 0={:              NB. information about the simulation
ending  =: empty`repetition`giveup {::~ 2 <. #.@stat   NB. how simulation ended
round   =: ": @ (# - >/@stat)         NB. round number
format  =: 'Round ', round, ': ', ending, ', ', ' percent maximum-fill',~ max
evolvex =: format @ percent@,. @ iterate@,: @ convert
joinln  =: ,&LF &.>
nlines  =: ". @ {~&0
remain  =: }.
stdout ; joinln }: (nlines (evolvex@{. ; $: ::]@}.) remain) input

```

The `$:` part makes the main body recurse over the input (a terribly inconvenient form for J to parse), applying the `@` daisy-chain over each section. `nlines` finds the number of lines for the next board.

The action on each board (`evolvex`) is neat: `iterate` (called `a` in the golf) constructs a list of each iteration of the simulation until we hit either something seen before or too many steps. Then `percent@,.` calculates the percentage of filled square in each result, and `format` runs some statistics (`stat`, called `t` in the golf) to figure out how the simulation ended, which percentage was the greatest, and so on, before formatting all of that into a string.

Finally, `}:` takes care of some garbage before `; joinln` joins all of the individual board outputs into one newline-separated string.
> 2 votes

---
Tags: code-golf
---


title: Shortest code to sort walking points

text:
# Question
Title: Shortest code to sort walking points
The challenge is to, given a list of points, sort in a way that, when they are connected in this order, they never intersect.

Input format (read from stdin):

```
X Y
1 2
3 4
5 6
...

```

Output should be the same as input, but sorted.

Rules:

* You can start from any point.
* The last point must be same as first one, making a close circuit.
* It should be done considering the Cartesian grid.
* You may assume that the input points do not all lie on a single line.
* The endpoints of each line do not count as intersecting.

For further help:

# Answer
> 9 votes
## Mathematica - ~~20~~ 30 chars

Just the sorting part

```
SortBy[%, ArcTan @@ # &]

```

Whole testing code, that consists of generating 100 random points and plotting the line

```
RandomReal[{-10, 10}, {100, 2}];
SortBy[%, ArcTan @@ # &];
ListPlot@% /.
 Point[p_] :> {EdgeForm[Dashed], FaceForm[White], Polygon[p],
   PointSize -> Large, Point[p]}

```

# +26 chars

If you demand proper input/ouput, then

```
"0 0
 4 4
 0 4
 4 0";
Grid@SortBy[%~ImportString~"Table", ArcTan @@ # &]

```

# +2 chars

Just adding `N@`

```
Grid@SortBy[%~ImportString~"Table", ArcTan @@ N @ # &]

```

because above code works only on real numbers and not on integers due to Mathematica's weird behavior when sorting symbolic expressions

```
N@Sort[{ArcTan[1], ArcTan[-2]}]
Sort[N@{ArcTan[1], ArcTan[-2]}]

{0.785398, -1.10715}
{-1.10715, 0.785398}

```

**EDIT** I just realized if the points are not around the origin it won't work, so it also requires shift to the center of points

```
SortBy[%, ArcTan @@ N[# - Mean@%] &]

```

# Answer
> 5 votes
The question has changed, thus this answer contains different versions, with and without a closed path.

## Perl, open path, 69 bytes

```
print"@$_$/"for sort{$$a[0]<=>$$b[0]||$$a[1]<=>$$b[1]}map{[/\S+/g]}<>

```

Each point is expected in STDIN as line, with the coordinates separated by white space.

*Any* number format is supported that Perl interprets as number (including floating point numbers).

**Example:**

```
0 0
4 4
0 4
4 0
-2 1
2 -2
2 4
3.21 .56
.035e2 -7.8
0 2

```

**Output:**

```
-2 1
0 0
0 2
0 4
2 -2
2 4
3.21 .56
.035e2 -7.8
4 0
4 4

```

**Ungolfed:**

```
print "@$_$/" for            # print output line
    sort {                   # sort function for two points $a and $b
        $$a[0] <=> $$b[0]    # compare x part
        || $$a[1] <=> $$b[1] # compare y part, if x parts are identical
    }
    map { [/\S+/g] }         # convert input line to point as array reference
    <>                       # read input lines

```

# Circuit variants

In the first question version, there was a connection between the last and first point to make a circuit.

## Center is not existing point, 253 bytes

This variant can fail, if the center is one of the points, see example 3.

**Edits:**

* In his answer swish noticed, that the points should be centered around the origin to ensure a cross-free circuit:

+ Sorting needs transformed coordinates.
    + The original string representation of the numbers need to be kept for the output.
* Bug fix: the special case for the negative x-axis had included the positive x-axis.

```
print"$$_[2] $$_[3]$/"for sort{($X,$Y)=@$a;($x,$y)=@$b;(!$X&&!$Y?-1:0)||!$x&&!$y||!$Y&&!$y&&$X<0&&$x<0&&$X<=>$x||atan2($Y,$X)<=>atan2($y,$x)||$X**2+$Y**2<=>$x**2+$y**2}map{[$$_[0]-$M/$n,$$_[1]-$N/$n,@$_]}map{$n++;$M+=$$_[0];$N+=$$_[1];$_}map{[/\S+/g]}<>

```

**Example 1:**

```
4 4
-2 0
2 0
1 1
4 0
-2 -2
-3 -1
1 -2
3 0
2 -4
0 0
-1 -2
3 3
-3 0
2 3
-5 1
-6 -1

```

**Output 1:**

```
0 0
-6 -1
-3 -1
-2 -2
-1 -2
1 -2
2 -4
2 0
3 0
4 0
1 1
3 3
4 4
2 3
-5 1
-3 0
-2 0

```

**Example 2:**

Testing number representation and coordinate transformation.

```
.9e1 9
7 7.0
8.5 06
7.77 9.45

```

**Output 2:**

```
7 7.0
8.5 06
.9e1 9
7.77 9.45

```

**Ungolfed:**

```
print "$$_[2] $$_[3]$/" for sort { # print sorted points
    ($X, $Y) = @$a;                # ($X, $Y) is first point $a
    ($x, $y) = @$b;                # ($x, $y) is second point $b
    (!$X && !$Y ? -1 : 0) ||       # origin comes first, test for $a
    !$x && !$y ||                  # origin comes first, test for $b
    !$Y && !$y && $X < 0 && $x < 0 && $X <=> $x ||
        # points on the negative x-axis are sorted in reverse order
    atan2($Y, $X) <=> atan2($y, $x) ||
        # sort by angles; the slope y/x would be an alternative,
        # then the x-axis needs special treatment
    $X**2 + $Y**2 <=> $x**2 + $y**2
        # the (quadratic) length is the final sort criteria
}
map { [ # make tuple with transformed and original coordinates
        # the center ($M/$n, $N/$n) is the new origin
        $$_[0] - $M/$n,  # transformed x value
        $$_[1] - $N/$n,  # transformed y value
        @$_              # original coordinates
] }
map {
    $n++;                # $n is number of points
    $M += $$_[0];        # $M is sum of x values
    $N += $$_[1];        # $N is sum of y values
    $_                   # pass orignal coordinates through
}
map {                    # make tuple with point coordinates
    [ /\S+/g ]           # from non-whitespace in input line
}
<>                       # read input lines

```

## Without restriction, 325 bytes

```
print"$$_[2] $$_[3]$/"for sort{($X,$Y)=@$a;($x,$y)=@$b;atan2($Y,$X)<=>atan2($y,$x)||$X**2+$Y**2<=>$x**2+$y**2}map{[$$_[0]-$O/9,$$_[1]-$P/9,$$_[2],$$_[3]]}map{$O=$$_[0]if$$_[0]>0&&($O>$$_[0]||!$O);$P=$$_[1]if$$_[1]>0&&($P>$$_[1]||!$P);[@$_]}map{[$$_[0]-$M/$n,$$_[1]-$N/$n,@$_]}map{$n++;$M+=$$_[0];$N+=$$_[1];$_}map{[/\S+/g]}<>

```

In the previous version, the center is put at the begin and the last points on the negative axis are sorted in reverse order to get cross-free to the center again. However, this is not enough, because the last points could lie on a different line. Thus the following example 3 would fail.

This is fixed by moving the centered origin a little to the top and right. Because of centering, there must be at least one point with positive x value and a point with positive y value. Thus the minimums of the positive x and y values are taken and reduced to a ninth (a half or third could be enough). This point cannot be one of the existing points and is made the new origin.

The special treatments of the origin and the negative x-axis can be removed, because there is any point that lies on the new origin.

**Example 3:**

```
-2 -2
-1 -1
-2 2
-1 1
2 -2
1 -1
2 2
1 1
0 0

```

**Output 3:**

```
0 0
-1 -1
-2 -2
1 -1
2 -2
1 1
2 2
-2 2
-1 1

```

**Example 1** is now differently sorted:

**Ungolfed:**

```
print "$$_[2] $$_[3]$/" for sort { # print sorted points
    ($X, $Y) = @$a;                # ($X, $Y) is first point $a
    ($x, $y) = @$b;                # ($x, $y) is second point $b
    atan2($Y, $X) <=> atan2($y, $x) ||
        # sort by angles; the slope y/x would be an alternative,
        # then the x-axis needs special treatment
    $X**2 + $Y**2 <=> $x**2 + $y**2
        # the (quadratic) length is the final sort criteria
}
map { [ # make tuple with transformed coordinates
    $$_[0] - $O/9, $$_[1] - $P/9,  # new transformed coordinate
    $$_[2],  $$_[3]                # keep original coordinate
] }
map {
    # get the minimum positive x and y values
    $O = $$_[0] if $$_[0] > 0 && ($O > $$_[0] || !$O);
    $P = $$_[1] if $$_[1] > 0 && ($P > $$_[1] || !$P);
    [ @$_ ]               # pass tuple through
}
map { [ # make tuple with transformed and original coordinates
        # the center ($M/$n, $N/$n) is the new origin
        $$_[0] - $M/$n,  # transformed x value
        $$_[1] - $N/$n,  # transformed y value
        @$_              # original coordinates
] }
map {
    $n++;                # $n is number of points
    $M += $$_[0];        # $M is sum of x values
    $N += $$_[1];        # $N is sum of y values
    $_                   # pass orignal coordinates through
}
map {                    # make tuple with point coordinates
    [ /\S+/g ]           # from non-whitespace in input line
}
<>                       # read input lines

```

# Answer
> 3 votes
# GolfScript, 6 / 13 chars (open path; 49 chars for closed path)

> Note: This solution is for the current version of the challenge as edited by Rusher. It is *not* a valid solution to the original challenge, which required that the line from last point back to the first also should not intersect the other lines. The 49-char solution below is valid for the original challenge too.

```
~]2/$`

```

The code above assumes that the output can be in any reasonable format. If the output format has to match the input, the following 13-character version will do:

```
~]2/${" "*n}/

```

Explanation:

* `~` evaluates the input, turning it into a list of numbers; `]` gathers these numbers into an array, and `2/` splits this array into two-number blocks, each representing one point.
* `$` sorts the points in lexicographic order, i.e. first by the x-coordinate and then, if there are ties, by the y-coordinate. It is easy to show that this will guarantee that the lines drawn between the points do not intersect, *as long as* the path does not need to loop back to the beginning.
* In the 5-character version, ``` stringifies the sorted array, producing the native string representation of it (e.g. `[[0 0] [0 4] [4 0] [4 4]]`). In the longer version, `{" "*n}/` joins the coordinates of each point by a space, and appends a newline.

Online demo: short version / long version.

---

Ps. Here's a 49-char solution to the original problem, where the path is required to be closed:

```
~]2/$.0=~:y;:x;{~y-\x-.+.@9.?*@(/\.!@@]}${" "*n}/

```

It works in a similar manner as Heiko Oberdiek's Perl solution, except that, instead of using trig functions, this code sorts the points by the slope (*y**y*<sub>0</sub>) / (*x**x*<sub>0</sub>), where (*x*<sub>0</sub>, *y*<sub>0</sub>) is the point with the lowest *x*-coordinate (and lowest *y*-coordinate, if several points are tied for lowest *x*).

Since GolfScript doesn't support floating point, the slopes are multiplied by the fixed constant 9<sup>9</sup> = 387420489. (If that's not enough precision, you can replace the `9` with `99` to turn the multiplier into 99<sup>99</sup> ≈ 3.7 × 10<sup>197</sup>.) There's also some extra code to break ties (by the *x* coordinate) and to ensure that, as in Heiko's solution, points with *x* = *x*<sub>0</sub> are sorted last, in decreasing order by *y* coordinate.

Again, here's an online demo.

# Answer
> 1 votes
# Mathematica, 35

This works for ANY list of unique points.

```
s=StringSplit;Grid@Sort@s@s[%,"\n"]

```

You say "read from stdin", so for Mathematica, I'm assuming "read from last output".

## Input (last output):

```
"0 0
4 4
0 4
4 0"

```

## Output:

```
0 0
0 4
4 0
4 4

```

If input and output needn't be in the "newlines" format, this can shrink to **6** characters:

```
Sort@%

```

taking the last output as input, assuming the last output is a 2-dimensional array.

Input (last output):

```
{{0,0},{4,4},{0,4},{4,0}}

```

Ouput:

```
{{0,0},{0,4},{4,0},{4,4}}

```

# Answer
> 1 votes
# PHP (~~175~~ ~~109~~ 100 chars)

```
while(fscanf(STDIN,'%d%d',$a,$b))$r[]=sprintf('%1$04d %2$04d',$a,$b);sort($r);echo implode('
',$r);

```

OK, I admit, PHP isn't the best golfing language, but I gave it a try.

Here's some sample output:

```
0000 0000
0000 0004
0004 0000
0004 0004

```

What is does is it puts the information into a string formatted with previous zeroes.
Then it just sorts the points textually.
<sub>P.S. It fails on numbers above `9999`.</sub>

# Answer
> 0 votes
# Python 2.7, 42B

```
import sys
print''.join(sorted(sys.stdin))

```

Couldn't really be simpler; read STDIN, sort lines, print lines. NB I've respected the exact I/O requirements of the question, but if you're manually populating STDIN you need to press `CTRL+d` to end input.

---
Tags: code-golf, sorting
---


title: Gravity Controls

text:
# Question
Title: Gravity Controls
Your task is to find the total destination of objects that are falling to a planet, you will get inputs like this:

```
7
...#...
.......
#..O..#
.......
...#...
.......
.......

```

where O is the planet and # are the objects, note that the planet will attract objects from the for basic directions(NEWS). You should output:

```
    #
   #O#
    #

```

i.e the objects after reaching their destination.

The first number given as an input is the length of the grid(nxn), in the above example it is 7.

The object should always move in the shortest direction(note that the allowed directions are only horizontal and vertical; the object can't move diagonally)

If an object is equidistant from two directions it should go in a clock wise direction:

```
    ..#
    ...
    O..

```

Will reach this side:

```
    ...
    ...
    O#.

```

If an object collides with the planet, it will stop. If it collides with another object they become one object,

```
 4
 .#..
 #...
 ....
 .O..

```

would become:

```
  ....
  ....
  .#..
  .O..

```

One final example:

```
6
..#...
.#....
......
.#O...
....#.
......

```

Output:

```
......
......
..#...
.#O#..
......
......

```

**Note:** You should output the final shape, so all outputs are accepted as long as they show the final shape of the planet.

for example for this input:

```
...#
....
.O..
....

```

Should output:

```
O#

```

or

```
....
....
.O#.
....

```

Both of these are accepted.

This is so the shortest answer will win

**Note 2:**

As you may have noticed a `.` represents vaccum so the shortest path is the shortest number of dots.

For example:

```
.#.
...
.O.

```

Is not accepted to be

```
O#

```

since the shortest path is vertical. **Note3:**

The object should always move to be in the same line with the planet in one of the four directions(choosing the shortest)

```
     |<#
     |
     |
-----O------
     |

```

Restrictions:

2\<=n\<=100

# Answer
## Perl, ~~156 153~~ 148

```
$n=$_+1;
s/.+\n//;
$o=index$_,O;
$x=$o%$n-$-[0]%$n,
pos=$o+(($==($o-$-[0])/$n)&&$x/$=>-1&&$x/$=<=1?$=>0?-$n:$n:0<=>$x),
s/\G./x/ while s/#/./;
y/x/#/

```

Newlines for readability. Run with `-0777p` (5 added to count), input through STDIN.

More readable:

```
$n=$_+1;
s/.+\n//;
$o=index$_,O;
while(s/#/./){
    $x=$o%$n-$-[0]%$n;
    $==($o-$-[0])/$n;
    pos=$o+(
        $=
        &&$x/$=>-1
        &&$x/$=<=1
            ?$=>0
                ?-$n
                :$n
            :0<=>$x

    );
    s/\G./x/
}
y/x/#/

```
> 2 votes

# Answer
## Mathematica, 206 bytes

```
f=(m=Characters@StringSplit@#;o=#-Join@@m~(p=Position)~"O"&/@m~p~"#";h=If[MemberQ[#3/@o,{m_,n_}/;m#<0&&m#<=n#2<-m#],"#",e]&;{e=".",h[1,1,#&],e,n="\n",h[1,-1,r=Reverse],"O",h[-1,1,r],n,e,h[-1,-1,#&],e}<>"")&

```

Somewhat more readable:

```
f[input_] := (
  map = Characters @ StringSplit @ input;
  planet = Flatten[Position[map, "O"]];
  objects = Map[# - planet &, Position[map, "#"]];
  helper[pattern_] := If[
    Length[Position[objects, pattern]] > 0,
    "#",
    "."
  ];
  StringJoin[{
    ".", h[{m_, n_} /; m < 0 && m <= n < -m], ".", "\n",
    h[{m_, n_} /; n < 0 && n < m <= -n], "O", h[{m_, n_} /; n > 0 && -n <= m < n], "\n",
    ".", h[{m_, n_} /; m > 0 && -m < n <= m], "."
  }]
);

```

As you can see, I only take a single input which is the string containing the input map. This is because I wouldn't use the size integer anyway. If you insist on the input format, I can change the input string to the second argument for one more character.

As for the algorithm, I'm just collecting all the `{Δx, Δy}` pairs of the objects and look for one pair in each quadrant with the conditions passed to `h`. I suspect this is also the part that could be golfed down further.
> 6 votes

# Answer
# perl, 270 chars

3 steps: 1) find the planet and satellites in the input, 2) determine quadrant for each satellite, 3) output

```
sub _{"#"}$D=<>;$\=$/;for$L(1..$D){for$M(1..$D){$/=\1;$_=<>;$p=$M,$q=$L if/O/;push@s,[$M,$L] if/#/}$/=$\;<>}for(@s){$x=$_->[0]-$p,$y=$_->[1]-$q;($x<0&&$x<$y&&$y<=-$x?$l:$x>0&&-$x<=$y&&$y<$x?$r:$y<0&&$y<=$x&&$x<-$y?$u:$d)=_}$_=$l?" #":_;$u&&print;print $l."O$r";$d&&print

```

Less golfed:

```
sub _{"#"}
$D=<>;
$\=$/;
for$L(1..$D){
  $/=\1;
  for$M(1..$D){
    $_=<>;
    $p=$M,$q=$L if/O/;
    push@s,[$M,$L] if/#/;
  }
  $/=$\;
  <>
}

for(@s){
  $x=$_->[0]-$p,$y=$_->[1]-$q;

  ($x<0&&$x<$y&&$y<=-$x ? $l :
   $x>0&&-$x<=$y&&$y<$x ? $r :
   $y<0&&$y<=$x&&$x<-$y ? $u : $d)=_;
}

$_=$l?" #":_;
$u && print;
print$l."O$r";
$d && print;

```
> 5 votes

---
Tags: code-golf
---