title: Draw an Apollonian Gasket

text:
# Question
Title: Draw an Apollonian Gasket
Given three mutually tangent circles, we can always find two more circles which are tangent to all three of those. These two are called *Apollonian circles*. Note that one of the Apollonian circles might actually be *around* the three initial circles.

Starting from three tangent circles, we can create a fractal called an Apollonian gasket, by the following process:

1. Call the initial 3 circles the *parent circles*
2. Find the parent circles' two Apollonian circles
3. For each Apollonian circle:
    4. For each pair of the three pairs of parent circles:
        5. Call the Apollonian circle and the two parent circles the new set of parent circles and start over from step 2.

E.g. starting with circles of equal size, we get:

Image found on Wikipedia

There's one more bit of notation we need. If we have a circle of radius *r* with centre *(x, y)*, we can define it's curvature as *k = ±1/r*. Usually *k* will be positive, but we can use negative *k* to denote the circle that encloses all the other circles in the gasket (i.e. all tangents touch that circle from the inside). Then we can specify a circle with a triplet of numbers: ***(k, x\*k, y\*k)***.

For the purpose of this question, we will assume positive integer *k* and rational *x* and *y*.

Further examples for such circles can be found in the Wikipedia article.

There's also some interesting stuff about integral gaskets in this article (among other fun things with circles).

## The Challenge

You will be given **4** circle specifications, each of which will look like `(14, 28/35, -112/105)`. You can use any list format and division operator that is convenient, such that you can simply `eval` the input if you wish to. You may assume that the 4 circles are indeed tangent to each other, and that the first of them has negative curvature. That means you are already given the surrounding Apollonian circle of the other three. For a list of valid example inputs, see the bottom of the challenge.

Write a program or function which, given this input, draws an Apollonian gasket.

You may take input via function argument, ARGV or STDIN and either render the fractal on screen or write it to an image file in a format of your choice.

If the resulting image is rasterised, it must be at least 400 pixels on each side, with less than 20% padding around the largest circle. You may stop recursing when you reach circles whose radius is less than a 400th of the largest input circle, or circles which are smaller than a pixel, whichever happens first.

You must draw only circle outlines, not full discs, but the colours of background and lines are your choice. The outlines must not be wider than a 200th of the outer circles diameter.

This is code golf, so the shortest answer (in bytes) wins.

## Example Inputs

Here are all integral gaskets from the Wikipedia article converted to the prescribed input format:

```
[[-1, 0, 0], [2, 1, 0], [2, -1, 0], [3, 0, 2]]
[[-2, 0, 0], [3, 1/2, 0], [6, -2, 0], [7, -3/2, 2]]
[[-3, 0, 0], [4, 1/3, 0], [12, -3, 0], [13, -8/3, 2]]
[[-3, 0, 0], [5, 2/3, 0], [8, -4/3, -1], [8, -4/3, 1]]
[[-4, 0, 0], [5, 1/4, 0], [20, -4, 0], [21, -15/4, 2]]
[[-4, 0, 0], [8, 1, 0], [9, -3/4, -1], [9, -3/4, 1]]
[[-5, 0, 0], [6, 1/5, 0], [30, -5, 0], [31, -24/5, 2]]
[[-5, 0, 0], [7, 2/5, 0], [18, -12/5, -1], [18, -12/5, 1]]
[[-6, 0, 0], [7, 1/6, 0], [42, -6, 0], [43, -35/6, 2]]
[[-6, 0, 0], [10, 2/3, 0], [15, -3/2, 0], [19, -5/6, 2]]
[[-6, 0, 0], [11, 5/6, 0], [14, -16/15, -4/5], [15, -9/10, 6/5]]
[[-7, 0, 0], [8, 1/7, 0], [56, -7, 0], [57, -48/7, 2]]
[[-7, 0, 0], [9, 2/7, 0], [32, -24/7, -1], [32, -24/7, 1]]
[[-7, 0, 0], [12, 5/7, 0], [17, -48/35, -2/5], [20, -33/35, 8/5]]
[[-8, 0, 0], [9, 1/8, 0], [72, -8, 0], [73, -63/8, 2]]
[[-8, 0, 0], [12, 1/2, 0], [25, -15/8, -1], [25, -15/8, 1]]
[[-8, 0, 0], [13, 5/8, 0], [21, -63/40, -2/5], [24, -6/5, 8/5]]
[[-9, 0, 0], [10, 1/9, 0], [90, -9, 0], [91, -80/9, 2]]
[[-9, 0, 0], [11, 2/9, 0], [50, -40/9, -1], [50, -40/9, 1]]
[[-9, 0, 0], [14, 5/9, 0], [26, -77/45, -4/5], [27, -8/5, 6/5]]
[[-9, 0, 0], [18, 1, 0], [19, -8/9, -2/3], [22, -5/9, 4/3]]
[[-10, 0, 0], [11, 1/10, 0], [110, -10, 0], [111, -99/10, 2]]
[[-10, 0, 0], [14, 2/5, 0], [35, -5/2, 0], [39, -21/10, 2]]
[[-10, 0, 0], [18, 4/5, 0], [23, -6/5, -1/2], [27, -4/5, 3/2]]
[[-11, 0, 0], [12, 1/11, 0], [132, -11, 0], [133, -120/11, 2]]
[[-11, 0, 0], [13, 2/11, 0], [72, -60/11, -1], [72, -60/11, 1]]
[[-11, 0, 0], [16, 5/11, 0], [36, -117/55, -4/5], [37, -112/55, 6/5]]
[[-11, 0, 0], [21, 10/11, 0], [24, -56/55, -3/5], [28, -36/55, 7/5]]
[[-12, 0, 0], [13, 1/12, 0], [156, -12, 0], [157, -143/12, 2]]
[[-12, 0, 0], [16, 1/3, 0], [49, -35/12, -1], [49, -35/12, 1]]
[[-12, 0, 0], [17, 5/12, 0], [41, -143/60, -2/5], [44, -32/15, 8/5]]
[[-12, 0, 0], [21, 3/4, 0], [28, -4/3, 0], [37, -7/12, 2]]
[[-12, 0, 0], [21, 3/4, 0], [29, -5/4, -2/3], [32, -1, 4/3]]
[[-12, 0, 0], [25, 13/12, 0], [25, -119/156, -10/13], [28, -20/39, 16/13]]
[[-13, 0, 0], [14, 1/13, 0], [182, -13, 0], [183, -168/13, 2]]
[[-13, 0, 0], [15, 2/13, 0], [98, -84/13, -1], [98, -84/13, 1]]
[[-13, 0, 0], [18, 5/13, 0], [47, -168/65, -2/5], [50, -153/65, 8/5]]
[[-13, 0, 0], [23, 10/13, 0], [30, -84/65, -1/5], [38, -44/65, 9/5]]
[[-14, 0, 0], [15, 1/14, 0], [210, -14, 0], [211, -195/14, 2]]
[[-14, 0, 0], [18, 2/7, 0], [63, -7/2, 0], [67, -45/14, 2]]
[[-14, 0, 0], [19, 5/14, 0], [54, -96/35, -4/5], [55, -187/70, 6/5]]
[[-14, 0, 0], [22, 4/7, 0], [39, -12/7, -1/2], [43, -10/7, 3/2]]
[[-14, 0, 0], [27, 13/14, 0], [31, -171/182, -10/13], [34, -66/91, 16/13]]
[[-15, 0, 0], [16, 1/15, 0], [240, -15, 0], [241, -224/15, 2]]
[[-15, 0, 0], [17, 2/15, 0], [128, -112/15, -1], [128, -112/15, 1]]
[[-15, 0, 0], [24, 3/5, 0], [40, -5/3, 0], [49, -16/15, 2]]
[[-15, 0, 0], [24, 3/5, 0], [41, -8/5, -2/3], [44, -7/5, 4/3]]
[[-15, 0, 0], [28, 13/15, 0], [33, -72/65, -6/13], [40, -25/39, 20/13]]
[[-15, 0, 0], [32, 17/15, 0], [32, -161/255, -16/17], [33, -48/85, 18/17]]

```

# Answer
## GolfScript (289 bytes vector / 237 bytes raster)

At 289 bytes and executing in a reasonable time:

```
'/'/n*','/']['*0,`1/*~1.$[]*(~-400*:&;{1+1=*}/:D;{{1+2<~D@*\/}%}%'<svg><g fill="none" stroke="red">'puts.{[[~@:b[D&*\abs]{@&*[b]+}2*]{'.0/'*'"#{
}"'n/*~}%'<circle r="
" cx="
" cy="
" />'n/\]zip puts}:|/[{.([.;]+}3*]{(:?zip{)\~++2*\-}%:c.|0=D&*<{?);[c]+[{([.;]+.}3*;]+}*.}do'</g></svg>'

```

This takes input on stdin and generates an SVG file to stdout. Unfortunately it takes a bit too long for an online demo, but a tweaked version which aborts early can give you an idea.

Given input `[[-2, 0, 0], [3, 1/2, 0], [6, -2, 0], [7, -3/2, 2]]` the output (converted to PNG with InkScape) is

---

At 237 bytes and taking far too long (I extrapolate that it would take just over a week to produce similar output to the above, although in one-bit black and white):

```
'/'/n*','/']['*0,`1/*~1.$[]*(~-400*:&;{1+1=*}/:D;{{1+2<~D@*\/}%}%.[{.([.;]+}3*]{(:?[zip{)\~++2*\-}%:c]@+\0c=D&*<{?);[c]+[{([.;]+.}3*;]+}*.}do;:C;'P1 ''801 '2*.~:B*,{:P;C{:?[0=2/.D&*-.*\D&*+.*]{2,{P{B/}2$*B%400-?0=*\)?=&*-.*}/+<},,1=},!}/

```

Output is NetPBM format without newlines, so possibly doesn't strictly follow the spec, although the GIMP will still load it. If strict conformance is required, insert an `n` after the last `!`.

The rasterisation is by testing each pixel against each circle, so the time taken is pretty much linear in the number of pixels times the number of circles. By downscaling everything by a factor of 10,

```
'/'/n*','/']['*0,`1/*~1.$[]*(~-40*:&;{1+1=*}/:D;{{1+2<~D@*\/}%}%.[{.([.;]+}3*]{(:?[zip{)\~++2*\-}%:c]@+\0c=D&*<{?);[c]+[{([.;]+.}3*;]+}*.}do;:C;'P1 ''81 '2*.~:B*,{:P;C{:?[0=2/.D&*-.*\D&*+.*]{2,{P{B/}2$*B%40-?0=*\)?=&*-.*}/+<},,1=},!}/

```

will run in 10 minutes and produce

(converted to PNG with the GIMP). Given 36 hours it produced the 401x401
> 13 votes

# Answer
## JavaScript (418 410 bytes)

Implemented as a function:

```
function A(s){P='<svg><g fill=none stroke=red transform=translate(400,400)>';Q=[];s=eval(s);S=-400*s[0][0];function d(c){P+='<circle r='+Math.abs(p=S/c[0])+' cx='+p*c[1]+' cy='+p*c[2]+' />'}for(c=4;c--;d(s[0]),s.push(s.shift()))Q.push(s.slice());for(;s=Q.shift();d(c)){c=[];for(i=4;i--;)c[i]=2*(s[0][i]+s[1][i]+s[2][i])-s[3][i];for(i=6;c[0]<S&&i;)Q.push([s[i--%3],s[i--%3],c,s[i%3]])}document.body.innerHTML=P}

```

Online demo (note: doesn't work in browsers which fail to honour the SVG spec's requirements with respect to implicit sizing, so I offer a slightly longer version which works around that bug; browsers may also render the SVG less accurately than e.g. Inkscape, although Inkscape is a bit stricter on quoting attributes).

Note that 8 bytes could be saved by using `document.write`, but that seriously borks jsFiddle.
> 12 votes

# Answer
# Mathematica 289 characters

By solving the bilinear system as per http://arxiv.org/pdf/math/0101066v1.pdf Theorem 2.2 (highly inefficient).

Spaces not needed, still golfing it:

```
w = {k, x, y};
d = IdentityMatrix;
j = Join;
p_~f~h_ := If[#[[-1, 1]] < 6! h,
    q = 2 d@4 - 1;
    m = #~j~{w};
    r = Complement[w /. NSolve[ And @@ j @@
                        MapThread[Equal, {Thread@m.q.m, 4 d@3 {0, 1, 1}}, 2], w], a];
    If[r != {},
     a~AppendTo~# & @@ r;
     Function[x, x~j~{#}~f~h & /@ r]@#]] & /@ p~Subsets~{3};
Graphics[Circle @@@ ({{##2}, 1}/# & @@@ (f[a = #, -Tr@#]; a))] &

```

A reduced size animation with input `{{-13, 0, 0}, {23, 10/13, 0}, {30, -84/65, -1/5}, {38, -44/65, 9/5}}`
> 7 votes

# Answer
## Maple (960 bytes)

I used Descartes Theorem to generate the Apollonian Gasket and then use Maple's plotting system to plot it. If I have time I want to further golf this and and change it to Python (Maple is definitely not the best for fractals). Here is a link to a free Maple player if you want to run my code.

```
X,Y,Z,S,N:=abs,evalf,member,sqrt,numelems;
f:=proc(J)
    L:=map((x)->[x[1],(x[2]+x[3]*I)/x[1]+50*(1+I)/X(J[1][2])],J);
    R:=Vector([L]);
    T,r:=X(L[1][3]),L[1][4];
    A(L[1][5],L[2][6],L[3][7],L[1][8],L[2][9],L[3][10],R,T,r);
    A(L[1][11],L[2][12],L[4][13],L[1][14],L[2][15],L[4][16],R,T,r);
    A(L[1][17],L[3][18],L[4][19],L[1][20],L[3][21],L[4][22],R,T,r);
    A(L[2][23],L[3][24],L[4][25],L[2][26],L[3][27],L[4][28],R,T,r);
    plots[display](seq(plottools[circle]([Re(R[i][29]),Im(R[i][30])],X(1/R[i][31])),i=1..N(R))):
end proc:
A:=proc(a,b,c,i,j,k,R,E,F)
    K:=i+k+j+2*S(i*k+i*j+k*j);
    if K>400*E then
    return;
    end if;
    C:=(a*i+c*k+b*j+2*S(a*c*i*k+b*c*j*k+a*b*i*j))/K;
    C2:=(a*i+c*k+b*j-2*S(a*c*i*k+b*c*j*k+a*b*i*j))/K;
    if Y(X(C-F))<1/E and not Z([K,C],R) then
    R(N(R)+1):=[K,C];
    A(a,b,C,i,j,K,R,E,F);
    A(a,c,C,i,k,K,R,E,F);
    A(b,c,C,j,k,K,R,E,F);
    end if:
    if Y(X(C2-F))<1/E and not Z([K,C2],R) then
    R(N(R)+1):=[K,C2];
    A(a,b,C2,i,j,K,R,E,F);
    A(a,c,C2,i,k,K,R,E,F);
    A(b,c,C2,j,k,K,R,E,F);
    end if:
end proc:

```

Some sample gaskets

```
f([[-1, 0, 0], [2, 1, 0], [2, -1, 0], [3, 0, 2]]);

```

```
f([[-9, 0, 0], [14, 5/9, 0], [26, -77/45, -4/5], [27, -8/5, 6/5]]);

```
> 4 votes

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


title: Sabotage a Train to Make It Run Late

text:
# Question
Title: Sabotage a Train to Make It Run Late
*"I want to go to the Araby bazaar to buy a present for the one I have fallen in love with. However, if I arrive too late all the stores will be closed and I won't be able to buy anything. Can you help me?*"

**Goal:** Get the boy to Araby from North Richmond Street before all the stores close.
**Actual Goal:** Make sure the boy doesn't arrive in Araby before the stores close.

Your program will take in input in the following format:

```
<time> <map>

```

where

* `<time>` is the maximum time the boy can spend travelling, in minutes. It is a positive integer.
* `<map>` is a graph of the routes the train can take.

Here is how the format for the graph works:

* Each statement is ended with a semicolon.
* Nodes in the map (which represent switches) are represented using single lower case letters.
* A path between nodes is represented with the syntax `a,X,b`, where `X` is an integer representing the weight of the path. The weight of the path is the time, in minutes, the train takes to go through those two nodes.
* Araby is represented with `a`, and North Richmond Street is represented with an `n`.
* All paths are bidirectional.

For instance, this graph (pretend the paths are bidirectional):

Image by Artyom Kalinin, via Wikimedia Commons. Used under the CC BY-SA 3.0 licence.

would be recorded in the graph notation as:

```
a,4,b;a,2,c;b,5,c;b,10,d;c,3,e;e,4,d;d,11,f;

```

Note that this input doesn't have an `n`, so it's an invalid input. Your program may do anything if given an invalid input.

Here is an example input:

```
21 n,4,b;n,2,c;b,5,c;b,10,d;c,3,e;e,4,d;d,11,a;

```

(It's just the same graph as the image above with `a` replaced by `n` and `f` replaced by `a`).

The boy must get from `n` to `a` within 21 minutes. If he takes the route `n` --\> `c` --\> `e` --\> `d` --\> `a`, he gets there in 20 minutes, which is in time. We could represent that route as a comma separated list of nodes:

```
n,c,e,d,a

```

On the other hand, the route `n` --\> `b` --\> `c` --\> `e` --\> `d` --\> `a` will cause the boy to take 27 minutes, which is not in time. We could represent that route like this:

```
n,b,c,e,d,a

```

Another possible route that will cause the boy to not make it in time is:

```
n,b,c,b,c,b,c,b,c,b,c,b,c,b,c,b,c,b,c,e,d,a

```

Your program should take in the input as described above, and **at first glance** appear to output a route that will cause the boy to make it in time, but **actually** outputs a route that causes the boy to not make it in time. For any given input there will always exist a route, without backtracking, that causes the boy to not make it in time.

This is an underhanded popularity contest, so the entry with the most votes wins. Votes are awarded for ingenuity in hiding the bug - the less obvious it is the better.

Here are some sample graphs to test your program with.

Input:

```
12 a,2,c;a,2,e;b,5,c;b,4,d;b,11,e;d,7,n;e,4,n;

```

A visual representation (this visual representation is only for clarity and does not constitute part of the challenge):

A *possible* output:

```
n,d,b,e,a

```

Input:

```
10 a,8,b;a,12,d;b,1,n;d,11,n;a,1,n;

```

Here is a visual image of the graph:

A *possible* output:

```
n,d,a

```

# Answer
> 2 votes
# Python 3 (not 2)

Edit: I'll ungolf this in the morning, oops.

It's a perfectly normal A-star search. Right? Riiiiiiight? Seems to work for all test cases.

```
def a(b,c,d):
    e,f,g=[],{},{}
    f[c]=0
    while f:
        h=sorted(f.keys(),key=lambda z:-f[z],reverse=True)[-1]
        if h==d:break
        e.append(h)
        for z in b[h]:
            if z in e:continue
            if z in f and f[z]>f[h]+b[z][h]:continue
            g[z]=h
            f[z]=f[h]+b[z][h]
        del f[h]
    i=[]
    j=d
    q=0
    while j!=c:
        i.append(j)
        q+=b[j][g[j]]
        j=g[j]
    return q,(i+[c])[::-1]
t,q=input().split(" ")
t=int(t)
q=q[:-1]
q=[i.split(",")for i in q.split(";")]
g={a:{}for a in __import__("functools").reduce(lambda zz,zy:zz+zy,[[v[0],v[2]]for v in q])}
for l in q:g[l[0]][l[2]]=g[l[2]][l[0]]=int(l[1])

r=a(g,'n','a')
print("time-good: %d, time-ours: %d" % (t, r[0]))
print("path: %s" % " -> ".join(r[1]))

```

---
Tags: popularity-contest, underhanded, graph-theory
---


title: 2D Collision Detection

text:
# Question
Title: 2D Collision Detection
This challenge is based on actual collision detection I had to write for a simple game recently.

Write a program or function which, given two objects, returns a truthy or falsy value depending on whether the two objects are in collision (i.e. intersect) or not.

You need to support three types of objects:

* **Line segments**: represented by 4 floats, indicating the two endpoints, i.e. *(x1,y1)* and *(x2,y2)*. You may assume that the endpoints are not identical (so the line segment is not degenerate).
* **Discs**: i.e. filled circles, represented by 3 floats, two for the centre *(x,y)* and one (positive) for the radius *r*.
* **Cavities**: these are a disc's complement. That is, a cavity fills all of 2D space, *except* a circular region, specified by a centre and radius.

Your program or function will receive two such objects in the form of an identifying integer (of your choice) and their 3 or 4 floats. You can take input via STDIN, ARGV or function argument. You may represent the input in any convenient form that is not preprocessed, e.g. 8 to 10 individual numbers, two comma-separated list of values or two lists. The result can be returned or written to STDOUT.

You may assume that the objects are either at least 10-10 length units apart or intersect by that much, so you don't need to worry about the limitations of floating point types.

This is code golf, so the shortest answer (in bytes) wins.

## Test Cases

Representing line segments with `0`, discs with `1` and cavities with `2`, using a list-based input format, the following should all produce a truthy output:

```
[0,[0,0],[2,2]], [0,[1,0],[2,4]]        # Crossing line segments
[0,[0.5,0],[-0.5,0]], [1,[0,0],1]       # Line contained in a disc
[0,[0.5,0],[1.5,0]], [1,[0,0],1]        # Line partially within disc
[0,[-1.5,0.5],[1.5,0.5]], [1,[0,0],1]   # Line cutting through disc
[0,[0.5,2],[-0.5,2]], [2,[0,0],1]       # Line outside cavity
[0,[0.5,0],[1.5,0]], [2,[0,0],1]        # Line partially outside cavity
[0,[-1.5,0.5],[1.5,0.5]], [2,[0,0],1]   # Line cutting through cavity
[1,[0,0],1], [1,[0,0],2]                # Disc contained within another
[1,[0,0],1.1], [1,[2,0],1.1]            # Intersecting discs
[1,[3,0],1], [2,[0,0],1]                # Disc outside cavity
[1,[1,0],0.1], [2,[0,0],1]              # Disc partially outside cavity
[1,[0,0],2], [2,[0,0],1]                # Disc encircling cavity
[2,[0,0],1], [2,[0,0],1]                # Any two cavities intersect
[2,[-1,0],1], [2,[1,0],1]               # Any two cavities intersect

```

while the following should all result in a falsy output

```
[0,[0,0],[1,0]], [0,[0,1],[1,1]]        # Parallel lines
[0,[-2,0],[-1,0]], [0,[1,0],[2,0]]      # Collinear non-overlapping lines
[0,[0,0],[2,0]], [0,[1,1],[1,2]]        # Intersection outside one segment
[0,[0,0],[1,0]], [0,[2,1],[2,3]]        # Intersection outside both segments
[0,[-1,2],[1,2]], [1,[0,0],1]           # Line passes outside disc
[0,[2,0],[3,0]], [1,[0,0],1]            # Circle lies outside segment
[0,[-0.5,0.5],[0.5,-0.5]], [2,[0,0],1]  # Line inside cavity
[1,[-1,0],1], [1,[1,1],0.5]             # Non-intersecting circles
[1,[0.5,0],0.1], [2,[0,0],1]            # Circle contained within cavity

```

# Answer
> 6 votes
## APL, ~~279~~ ~~208~~ ~~206~~ 203

```
s←1 ¯1
f←{x←⊣/¨z←⍺⍵[⍋⊣/¨⍺⍵]
2 2≡x:∧/0∧.=⌊(2⊃-⌿↑z)⌹⍣(≠.×∘⌽/x)⍉↑x←s×-/2⊢/↑z
2≡2⌷x:∨/((2⊃z)∇2,x[1]×(2⌷⊃z)+,∘-⍨⊂y÷.5*⍨+.×⍨y←⌽s×⊃-/y),x[1]=(×⍨3⊃⊃z)>+.×⍨¨y←(s↓⌽↑z)-2⌷⊃z
~x∨.∧x[1]≠(.5*⍨+.×⍨2⊃-⌿↑z)<-/⊢/¨z×s*1⌷x}

```

Line breaks in the function `f` are for clarity. They should be replaced with the statement separator

It has been so long since I last made such a complex APL program. I think the last time was this but I am not even sure that was as complex.

**Input format**
Basically same as the OP, except using `0` for cavity, `1` for disc and `2` for line segment.

**Major update**

I managed to golf a lot of chars using a different algorithm. No more `g` bulls\**t!!

The main function `f` is divided into cases:

---

**`2 2≡x`: Segment-segment**

In this case, calculate the vector from the end points of each line and solve a system of linear equations to check if the intersection is contained within the vectors.

Caveats:

* The end point of a vector is not considered as a part of the vector (while its origin is). However, if only the tip of a vector is on the other one, the input is invalid according to spec.
* Non-degenerate parallel segments always returns false, regardless of collinearity.
* If one of the segments is degenerate, always return false. If both segments are degenerate, always return true.

Examples: (Note caveat 1 in action in the figure on the right)

---

**`2≡2⌷x`: Segment-other**

In this case, the other object is a circular one. Check if the end points of the segment is within the circle using distance check.

In the disc case, also construct a line segment of the diameter perpendicular to the given segment. Check if the segments collide by recursion.
In the cavity case, sneak in a "times 0" in the construction of the said segment to make it degenerate. (See why I use `0` for cavity and `1` for disc now?) As the given segment is not degenerate, the segment-segment collision detection always return false.

Finally combine the results of the distance checks and the collision detection. For the cavity case, negate the results of the distance checks first. Then (in both cases) OR the 3 results together.

Regarding the segment-segment caveats, numbers 3 is addressed (and exploited). Number 2 is not a problems as we are intersecting perpendicular segments here, which are never parallel if they are not degenerate. Number 1 takes effect only in the disc case, when one of the given end points is on the constructed diameter. If the end point is well inside the circle, the distance checks would have taken care of it. If the end point is on the circle, since the constructed diameter is parallel to the given segment, the latter must be tangent to the circle with only one point touching the disc, which is not valid input.

Examples:

---

**Default case: Other-other**

Calculate the distance between the centers. Disc-disc collision occurs if and only if the distance is smaller than the sum of radii. Disc-cavity collision occurs if and only if the distance is greater than the difference in radii.

To take care of the cavity-cavity case, negate the result of the distance check, AND with each of the identifying integers and then OR them together. Using some logic, one can show that this process returns true if and only if both identifying integers are falsy (Cavity-cavity case), or if the distance check returned true

# Answer
> 5 votes
# Javascript - 393 bytes

Minified:

```
F=(s,a,t,b,e,x)=>(x=e||F(t,b,s,a,1),[A,B]=a,[C,D]=b,r=(p,l)=>([g,h]=l,[f,i]=y(h,g),[j,k]=y(p,g),m=Math.sqrt(f*f+i*i),[(f*j+i*k)/m,(f*k-i*j)/m]),u=(p,c)=>([f,g]=c,[i,j]=y(p,f),i*i+j*j<g*g),y=(p,c)=>[p[0]-c[0],p[1]-c[1]],[n,o]=r(C,a),[q,v]=r(D,a),w=(v*n-o*q)/(v-o),z=r(B,a)[0],Y=u(A,b),Z=u(B,b),[v*o<0&&w*(w-z)<0,Y||Z||o<D&&o>-D&&n*(n-z)<0,!Y||!Z,x,u(A,[C,D+B]),B>D||!u(A,[C,D-B]),x,x,1][s*3+t])

```

Expanded:

```
F = (s,a,t,b,e,x) => (
    x = e || F(t,b,s,a,1),
    [A,B] = a,
    [C,D] = b,
    r = (p,l) => (
        [g,h] = l,
        [f,i] = y(h,g),
        [j,k] = y(p,g),
        m = Math.sqrt( f*f + i*i ),
        [(f*j + i*k)/m, (f*k - i*j)/m] ),
    u = (p,c) => (
        [f,g] = c,
        [i,j] = y(p,f),
        i*i + j*j < g*g ),
    y = (p,c) => [p[0] - c[0], p[1] - c[1]],
    [n,o] = r(C,a),
    [q,v] = r(D,a),
    w = (v*n - o*q)/(v - o),
    z = r(B,a)[0],
    Y = u(A,b), Z = u(B,b),
    [   v*o < 0 && w*(w-z) < 0,
        Y || Z || o < D && o > -D && n*(n-z) < 0,
        !Y || !Z,
        x,
        u(A,[C,D+B]),
        B > D || !u(A,[C,D-B]),
        x,
        x,
        1
    ][s*3+t]);

```

Notes:

* defines function `F` that accepts the required arguments and returns the required value
* input format is identical to format in the OP, with the exception that the integer type code for each primitive is separate from the tuple. For example, `F( 0,[[0,0],[2,2]], 0,[[1,0],[2,4]] )` or `F( 1,[[3,0],1], 2,[[0,0],1] )`.
* code validated on all test cases supplied in the OP
* should handle all edge and corner cases, including zero-length line segments and zero-radius circles

# Answer
> 4 votes
# Python, 284

I'm using a pretty garbage algorithm compared to all these geometric tricks, but it gets the right answers even though it takes a over a minute to get through the test cases. The big advantage is that I only have to write the three scoring functions, and the hillclimbing takes care of all the edge cases.

Golfed:

```
import math,random as r
n=lambda(a,c),(b,d):math.sqrt((a-b)**2+(c-d)**2)
x=lambda(t,a,b),p:max(eval(["n(b,p)-n(a,b)+","-b+","b-"][t]+'n(a,p)'),0)
def F(t,j):
q=0,0;w=1e9
 for i in q*9000:
    y=x(t,q)+x(j,q)
    if y<w:p,w=q,y
    q=(r.random()-.5)*w+p[0],(r.random()-.5)*w+p[1]
 return w<.0001

```

Ungolfed:

```
import math
import random as r
def norm(a, b):
 return math.sqrt((a[0] - b[0])**2 + (a[1] - b[1])**2)

def lineWeight(a, b, p):
 l1 = norm(a, p)
 l2 = norm(b, p)
 return min(l1, l2, l1 + l2 - norm(a, b))

def circleWeight(a, r, p):
 return max(0, norm(a, p) - r)

def voidWeight(a, r, p):
 return max(0, r - norm(a, p))

def weight(f1, f2, s1, s2, p):
 return f1(s1[1], s1[2], p) + f2(s2[1], s2[2], p)

def checkCollision(s1, s2):
 a = [lineWeight, circleWeight, voidWeight]
 f1 = a[s1[0]]
 f2 = a[s2[0]]
 p = (0.0, 0.0)
 w = 0
 for i in a*1000:
  w = weight(f1, f2, s1, s2, p)
  p2 = ((r.random()-.5)*w + p[0], (r.random()-.5)*w + p[1])
  if(weight(f1, f2, s1, s2, p2) < w):
   p = p2
 if w < .0001:
  return True
 return False

```

And finally, a test script in case anyone else wants to try this in python:

```
import collisiongolfedbak
reload(collisiongolfedbak)

tests = [
[0,[0,0],[2,2]], [0,[1,0],[2,4]],        # Crossing line segments
[0,[0.5,0],[-0.5,0]], [1,[0,0],1],       # Line contained in a disc
[0,[0.5,0],[1.5,0]], [1,[0,0],1],        # Line partially within disc
[0,[-1.5,0.5],[1.5,0.5]], [1,[0,0],1],   # Line cutting through disc
[0,[0.5,2],[-0.5,2]], [2,[0,0],1],       # Line outside cavity
[0,[0.5,0],[1.5,0]], [2,[0,0],1],        # Line partially outside cavity
[0,[-1.5,0.5],[1.5,0.5]], [2,[0,0],1],   # Line cutting through cavity
[1,[0,0],1], [1,[0,0],2],                # Disc contained within another
[1,[0,0],1.1], [1,[2,0],1.1],            # Intersecting discs
[1,[3,0],1], [2,[0,0],1],                # Disc outside cavity
[1,[1,0],0.1], [2,[0,0],1],              # Disc partially outside cavity
[1,[0,0],2], [2,[0,0],1],                # Disc encircling cavity
[2,[0,0],1], [2,[0,0],1] ,               # Any two cavities intersect
[2,[-1,0],1], [2,[1,0],1] ,              # Any two cavities intersect
[0,[0,0],[1,0]], [0,[0,1],[1,1]] ,       # Parallel lines
[0,[-2,0],[-1,0]], [0,[1,0],[2,0]],      # Collinear non-overlapping lines
[0,[0,0],[2,0]], [0,[1,1],[1,2]],        # Intersection outside one segment
[0,[0,0],[1,0]], [0,[2,1],[2,3]],        # Intersection outside both segments
[0,[-1,2],[1,2]], [1,[0,0],1],           # Line passes outside disc
[0,[2,0],[3,0]], [1,[0,0],1],            # Circle lies outside segment
[0,[-0.5,0.5],[0.5,-0.5]], [2,[0,0],1],  # Line inside cavity
[1,[-1,0],1], [1,[1,1],0.5],             # Non-intersecting circles
[1,[0.5,0],0.1], [2,[0,0],1]            # Circle contained within cavity
]

for a, b in zip(tests[0::2], tests[1::2]):
 print collisiongolfedbak.F(a,b)

```

---
Tags: code-golf, geometry, decision-problem
---


title: Draw a Fractal in Under 200 Characters

text:
# Question
Title: Draw a Fractal in Under 200 Characters
After noticing all the fractal submissions/questions, I thought it would be fun to start a contest where everyone submits their favourite fractal.

**The Contest**

Generate a fractal in under 200 characters using any language. The output of the function can be an image, ascii art or any representation of a fractal you can think of. In your submission include your code, how to run your code, and sample outputs of your fractal. This is a popularity contest, so the submission with the most votes wins.

**Rules**

* You may use any libraries, except those which generate fractals (e.g. a library function that generates a mandelbrot set is not allowed)
* It is difficult to define a true fractal, so I will accept anything that has self-similarity and has fractal dimension greater than its topological dimension
* You may submit multiple answers

Good luck, have fun!

# Answer
> 4 votes
# Python, 127 bytes

Creates a Sierpinski triangle.

```
import Image
f=1e3
a=Image.new('RGB',(f,f))
p=a.load()
r=range(f)
for i in r:
 for j in r:p[i,j]=(i*16&j*16,)*3
a.save('s.png')

```

---
Tags: popularity-contest, ascii-art, graphical-output, fractal
---


title: Pluralize it!

text:
# Question
Title: Pluralize it!
### The challenge:

Write a program or function in any language that takes as an argument (command-line or function) a single English word. It returns or outputs the pluralized form of the word.

(To clarify, the program or function will be executed many times on different words, but separately - the list of words won't be passed all at once.)

### The scoring:

The score of a program or function is `-(characters in program + 1) * number of wrong answers`. Highest score wins. Joke answers will likely lose by a huge margin (I'm planning on putting in maybe 1,000 words) and if you're amazing you get the highest score of 0.

### Example test data:

```
woman
turn
fly
court
finger
blitz
pie
injury
vertex
alleyway
alloy
ox
goose
mouse
house
louse
waffle
right
bacterium
virus
cherub
chaetognath
boy
man
shaman
figure
prefix
etc.

```

Those are just some that I picked off the top of my head. The real test cases will have even stranger plurals, but the distribution between types of suffixes will be more even.

Enjoy!

### Additional Rule

No Mathematica. Sorry.

# Answer
## sed - 155 (not including #! line)

```
#!/bin/sed -Ef
s/man$/men!/
s/([aeiou](x|z))$/\1es!/
s/ium$/ia!/
s/([^!aeiou])y$/\1ies!/
s/((r|gh|l|s)[^!aeiou])$/\1s!/
s/([^!aeiou]{2}|.s)$/\1es!/
s/([^!])$/\1s/
s/!$//

```

This will read from stdin, and I think it will do an okay job for most input. The basic idea is that it tries each regex line by line. Whenever it matches it makes a replacement that appends `!` to make sure that no other regexes will match, then it drops the `!` on the last line.

I tried to deal with most special cases, but it will definitely fail on some (goose and mouse for example)

Sample invocation:

```
chmod a+x GordonBailey.sed
echo $word | ./GordonBailey.sed

```
> 3 votes

# Answer
## sed, 6 chars

Someone should give this a try...

```
s/$/s/

```

Invoked with `sed -f myscript.sed < words.txt > output.txt`
I can afford 22 times more mistakes, compared to Gordon Bailey's solution, and still win.

With the sample input I do win, because he misses "mice" and "lice" (and maybe more, there are some I need to look up), and this sample is too short for me to have 44 mistakes...
> 5 votes

# Answer
```
require 'open-uri'

def p(w)
  open("http://en.wiktionary.org/wiki/#{w}"){|f| f.read}.match(/plural-form-of.*?title=\"(.*?)\"/)[1]
end

```

ruby at 135. It got all of the sample input (though it will eventually begin returning 403s if you type quickly enough).
> 4 votes

# Answer
```
perl -mLingua::EN::Inflect=PL -pe's/.*/PL$&/e'

```
> 0 votes

# Answer
# Extended BrainFuck: 9

```
,[.,]||s|

```

Compiling:

```
beef ebf.bf < plural.ebf > plural.bf

```

Turns into the following BrainFuck code: (39)

```
,[.,]>++++++++++[-<+++++++++++>]<+++++.

```

Sample invocation:

```
$ echo -n test | beef plural.bf

```

Any BrainFuck interpreter can be used instead of beef. It takes one word in stdin and ends it with *EOF*. Alternatively you can use `echo test | bf -n plural.bf` where in this particular interpreter`-n` assumes *EOF* on first linefeed.
> 0 votes

---
Tags: code-golf, natural-language
---


# Question
Title: Chess - Find all legal moves (except castling and en passant)
Write the shortest code that calculates all possible (legal) moves of current player from a given FEN string. What is FEN string? (Wikipedia)

* Shortest code wins, language doesn't matter.
* Output moves must obey chess rules of movement **except *en passant*, castling, and pawn promotion.**
* Ignore check, checkmate, and stalemate, king cannot be captured situations too.

You can set outputs differently as you want (for example: `A2-A4`, `A2A4`, `a2a4`, `a2->a4`...)

**Test cases:**

```
# INPUT 1:

rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1

```

```
# OUTPUT 1

A2-A4, A2-A3, B2-B4, B2-B3, C2-C4, C2-C3, D2-D4, D2-D3, E2-E4, E2-E3,
F2-F4, F2-F3, G2-G4, G2-G3, H2-H4, H2-H3, B1-A3, B1-C3, G1-F3, G1-H3

```

```
# INPUT 2

7k/8/8/8/8/8/PP6/Q1q4K w - - 0 1

```

```
# OUTPUT 2

A1-B1, A1-C1, A2-A3, A2-A4, B2-B3, B2-B4, H1-H2, H1-G1, H1-G2

```

# Answer
> 9 votes
# C - 391 bytes

Takes input as command line arguments and prints to stdout with the squares labeled from 0 to 63.

OK, I had a few minutes so I tried to delete all the bits relating to the detection of check. I think it is now not very efficient though...

```
O(x,y){return((x&7)-(y&7))/5;}
B[64],*b=B,J=32,M,L,x,*X,N;
main(int c,char**V){
for(;x=*V[1]++;c=J&2**V[2])
x>56?*b++=x:x>47?b+=x-48:0;
for(;b-->B;)
for(M=-1,N=*b%J^16,*V=strchr("bGInFJOQrAHkAGHIqAGHIpGHIx",*b|J);*b&&*b&J^c&&(M=M<0?*++*V%J:-M,**V<96);)
for(x=b-B,L=N?9^*b&8:1+(x/8==1+c/6);L--*!(O(x,x+M)|O(x>>3,x+M>>3));L=!*X|~*X&J^c&&N|(!*X^M&1&&M<0^!c)?printf("%d-%d ",b-B,x),L*!*X:0)
X=B+(x+=M);}

```

**478 byte check-detecting version**

```
O(x,y){return((x&7)-(y&7))/5;}
B[64],*b=B,c,I,J=32;
main(int C,char**V){
int*D,M,L,t,x,*X,N;
for(;b-B<64;C=c=J&2**V[2])
(t=*V[1]++)>56?*b++=t:t>47?b+=t-48:0;
for(D=b;D-->B;)
for(M=-1,N=*D%J^16,*V=strchr("bGInFJOQrAHkAGHIqAGHIpGHIx",*D|J);*D&&*D&J^C&&(M=M<0?*++*V%J:-M,**V<96);)
for(x=D-B,L=N?9^*D&8:1+(x/8==1+C/6);L--*!(O(x,x+M)|O(x>>3,x+M>>3));L=!*X|~*X&J^C&&N|(!*X^M&1&&M<0^!C)?c^C?I|=*X%J==11:(*X=*D,*D=I=0,main(C^J,V+1),*D=*X,I||printf("%d-%d ",D-B,x)),L*!(*X=t):0)
X=B+(x+=M),t=*X;}

```

# Answer
> 2 votes
## Java 1455

```
String q(String f){int[][]b=new int[8][8];int i=0,j=0,k,l,m,n,c;HashSet<String>h=new HashSet<String>();while((c=f.charAt(i))>32){if(c>48&c<57)j+=c-49;if(c==47)j--;if(c>56)b[j%8][j/8]=c;i++;j++;}boolean w=f.charAt(++i)>99;for(i=0;i<8;i++)for(j=0;j<8;j++)if((c=b[i][j])<91?w&c>0:!w){switch(c%32){case 14:for(k=0;k<8;k++){l=(k/4+1)*(k%2*2-1)+i;m=(2-k/4)*(k%4/2*2-1)+j;if(b(l,m)&&(w&b[l][m]%91<40|!w&b[l][m]<91))h.add(h(i,j,l,m));}break;case 11:for(k=0;k<8;k++){l=i+(k==4?1:k/3-1);m=j+(k==4?1:k%3-1);if(b(l,m)&&(w&b[l][m]%91<40|!w&b[l][m]<91))h.add(h(i,j,l,m));}break;case 17:for(k=0;k<8;k++){for(n=1;n<9;n++){l=i+n*(k==4?1:k/3-1);m=j+n*(k==4?1:k%3-1);if(b(l,m)){c=b[l][m];if(w&c%91<40|!w&c<91)h.add(h(i,j,l,m));if(c>0)break;}else break;}}break;case 2:for(k=0;k<4;k++){for(n=1;n<9;n++){l=i+n*(k/2*2-1);m=j+n*(k%2*2-1);if(b(l,m)){c=b[l][m];if(w&c%91<40|!w&c<91)h.add(h(i,j,l,m));if(c>0)break;}else break;}}break;case 18:for(k=0;k<4;k++){for(n=1;n<9;n++){l=i+n*(k/2*(k%2*2-1));m=j+n*((1-k/2)*(k%2*-2+1));if(b(l,m)){c=b[l][m];if(w&c%91<40|!w&c<91)h.add(h(i,j,l,m));if(c>0)break;}else break;}}break;default:m=w?-1:1;if(b[i][j+m]<1){h.add(h(i,j,i,j+m));if(b[i][j+2*m]<1&j==(w?6:1))h.add(h(i,j,i,j+2*m));}for(l=-1;i+l<8&i+l>=0&l<2;l+=2){c=b[i+l][j+m];if(c>0&(c<91?!w:w))h.add(h(i,j,i+l,j+m));}}}return h.toString();}boolean b(int l,int m){return m>=0&m<8&l>=0&l<8;}String h(int i,int j,int l,int m){return""+g(i)+(8-j)+g(l)+(8-m);}char g(int i){return(char)(i+65);}

```

# Answer
> 2 votes
# Python 553 ~~649~~ ~~678~~

```
b,Q=raw_input(),range;R=Q(8);D="w"in b
for i in Q(9):b=b.replace(`i`,"_"*i)
if D:b=b.swapcase()
def X(h,v,c):
 h+=x;v+=y
 if c and h|v in R and"a">b[v*9+h]:print chr(65+x)+`8-y`+chr(65+h)+`8-v`;return"_"==b[v*9+h]
for y in R:
 for x in R:
  z=y*9+x;p=b[z];N=p=="n";j=[p in"qrk"]*4+[p in"qbk"]*4
  if"p"==p:j[D]=k=(1,-1)[D];X(1,k,b[z+10*k]<"_");X(-1,k,b[z+8*k]<"_")
  for i in Q(1,(2,(y==(1,6)[D])+2,8)["kp".find(p)]):
   for k in R:j[k]=X((0,0,-i,i,-i,i,-i,i)[k],(i,-i,0,0,-i,-i,i,i)[k],j[k])
  for v,h in((2,1),(1,2)):X(v,h,N);X(-v,-h,N);X(-v,h,N);X(v,-h,N)

```

Two-space indent is tab char, which saves 5 bytes.

It occurs to me that you can likely make it evaluate reasonable moves to a decent ply and keep it under 1024 bytes :) I started looking through other questions, but there doesn't seem to be a codegolf chess engine question...

# Answer
> 2 votes
# Python 638 637 (482?) bytes

```
exec"""p=raw_input()
for x in"12345678":p=p.replace(x,"~"*int(x))
b=map(ord,"#"*21+p[:71].replace("/","##")+"#"*21)
d,e=-10,126
if not"w"in p:b,d=[x^32*(64<x<e)for x in b],10
B=[-9,9,-11,11]
R=[-1,1,-d,d]
Q=B+R
c=Zx:chr(96+x%10)+chr(58-x/10)
for x,p in enumerate(b):
 def O(y):
    if 111<b[y]:print c(x)+c(y)
 s=ZL:[O(x+X)for X in L];m=ZL,z=x:L&(O(z+L[0]),m(L,z+L[0])if e==b[z+L[0]]else m(L[1:]))
 if p==80:e==b[x+d]&(O(x+d)or e==b[x+d*2]&35==b[x-d*2]&O(x+d*2)),111<b[x+d-1]<e&O(x+d-1),111<b[x+d+1]<e&O(x+d+1)
 p==75&s(Q),p==78&s([-12,12,-8,8,-21,21,-19,19]),p==82&m(R),p==66&m(B),p==81&m(Q)""".replace("Z","lambda ").replace("&"," and ")

```

Note: after `def O(y):` there is a newline and a tab char before `if`

Note: by using zlib module it's possible to get a valid Python source code of 482 bytes by simply compressing the real source:

```
#encoding=koi8-r
import zlib
exec zlib.decompress("x°MRKkЦ0>╞~┘Pы Eё╜Е4▌Ц█.9Br*1зБ┤B╠#°■╙=Лoъ╠M⌡│╬г0█\\pcл⌡╝x9╣ЧМф9^:Х╘e:·=м⌠Eй2oЭ╞нЫsQ9─ЩeсS{ЦAR ╕ПЭруюь4жрГыBшОhЖхпy`B▌╬ 58ёt:NхИHшк█╫ЁSK}VBmРПgOyР╢\n+'╬Z║╔▒╣иу√═╢╜-ы#G╙├з▓²Yк=╘л!dуkг≈┴?u$dOФ╘\n▐HфАюВ9]Шж╦╝╦9^┼▄пзИ√ Э│mi╜WeЧa3ъА╗╢бae┘.║WsьdЫ√Ы<ТВэГзьъ
ЙПiB╤≥П-Ъ■⌡<╡▌Б┬1╚3╕лGjщЫЙ(з╧н,>$Eш⌠FыdmШ<x,Р╔Mc;≥м╒2DLc!`Л≥рvЕFCИЪtyв%Н║╞╤≤O╝|'═┤)B|н*┘T╛▐рKпK;╔Я╓АШ&  бУ╗j└;│И╬Ж╝Щ\\4e]P&НРeZ╢5┼ДГt╚У")

```

# Answer
> 1 votes
# JavaScript (E6) 481 ~~492 550~~

**Edit** Fixed a nasty bug in knight moving. A lot of work to keep the byte count the same.

(Not counting leading spaces and newlines kept for readability)

```
B=f=>
  [for(c of(o=b='',f=f.split(w=' '))[0])b+=-c?w.repeat(c):c<'0'?z=10:c]+
  [...b].map((c,p)=>
    (K=d=>(d=b[p+d])==w?0:d>'a'?m:d>'A'?-m:9)(0)-1||(
      t='pPkKnNrRQqBb'.search(c),
      O=d=>K(d)<1?o+=w+P(p)+P(p+d):0,
      S=(d,s=0)=>O(d*++s)&&!K(d*s)&&S(d,s),
      //o+='\n'+P(p)+' '+c, // Uncomment to display pieces list
      t<2?[for(i of[~(s=t<1?z:-z),1-s])~K(i)||O(i)]+!K(s)&&O(s)&&(p/z|0)==t*5+1&!K(s+=s)&&O(s)
      :t<6?[for(i of t<4?[1,9,z,11]:[12,8,21,19])O(i)+O(-i)]
      :[for(i of[t>7&&9,t>7&&11,t<z,t<z&&z])S(i)+S(-i)]
    )
  ,m=f[1]<'w'?1:-1,
  //console.log(','+([...b]+',').replace(/1,0/g,'\n')), // Uncomment to display chessboard
  P=p=>'ABCDEFGH'[p%z]+(9+~p/z|0))&&o

```

**Less Golfed**

```
B=f=>(
  o=b='',[for(c of f)b+=-c?'.'.repeat(c):c],
  m=(w=b[72]=='w')?1:2,n=3-m,
  t=0,
  P=p=>'ABCDEFGH'[p%9]+(9+~p/9|0),
  b=b.slice(0,71),
  // console.log(b.replace(/\//g,'\n')), // Uncomment to display chessboard

  [...b].map((c,p)=>{
    r=p/9|0
    K=k=>(k=b[k])=='.'?0:k>'a'?m:k>'A'?n:9
    J=d=>K(p+d)<2,
    O=d=>J(d)?o+=' '+P(p)+P(p+d):0,
    S=(s,d)=>O(d*++s)&&!K(p+d*s)?S(s,d):0;

    if(K(p)==2){
      // o+='\n'+P(p)+ ' '+c; // Uncomment to display pieces list
      if (c=='P')
      {
        (f=!K(p-9))&&O(-9),
        f&r==6&&!K(p-18)&&O(-18),
        [for(i of[10,8])K(p-i)==1&&O(-i)]
      }
      else if (c=='p')
      {
        (f=!K(p+9))&&O(+9),
        f&r==1&&!K(p+18)&&O(+18),
        [for(i of[10,8])K(p+i)==1&&O(+i)]
      }
      else if (c=='K' |c=='k')
        [for(i of[1,8,9,10])O(i)+O(-i)]
      else if (c=='N' | c=='n')
        [for(i of[11,7,19,17])O(i)+O(-i)]
      else
      {
        if (c!='r' & c!='R')
          [for(i of[10,8])S(0,i)+S(0,-i)]
        if (c!='b' & c!='B')
          [for(i of[9,1])S(0,i)+S(0,-i)]
      }
    }
  }),
  o
)

```

**Test** in FireFox/FireBug console

```
B("7k/8/8/8/8/1P6/P7/Q1q4K w - - 0 1")

```

*Output*

```
B3B4 A2A3 A2A4 A1B2 A1C3 A1D4 A1E5 A1F6 A1G7 A1H8 A1B1 A1C1 H1G1 H1H2 H1G2

```

# Answer
> 1 votes
## JAVA 631 599 594

Fixed a bug in the 599-bytes version (thank you Jack for pointing this out!) and shortened the code to 594-bytes.

```
class F{
public static void main(String[]A){int p=0,i=8,u,v,d,z[]={0,1,-1,2,1,0,1};String f=A[0],S[]="p,n,rqk,bqk,aA,PNBRQK,aAPNBRQK".split(",");
for(;i>0;)f=f.replace(""+i,"a"+(--i==0?"":i));
for(;p<448;p++)
for(int k=p%7,w=A[1].equals("w")?32:0,c=f.charAt(p/7%8+p/56*9),a=z[k],b=k==4?2:1,q=0;S[(k/2-1|k-1)/2].indexOf(c+w)>=0&&q++<(k<3?1:4);i=a,a=b,b=-i){
for(i=1,d=97;d==97&&((u=p/7%8+i*a)|(v=p/56+i*b*(1-w/16)))>=0&&(u|v)<8&&i<(k>4?(c=='K'||c=='k')?2:9:(k<1&&p/56==w/6+1?3:2))&&S[61/(61^(k*k-2))+5].indexOf((d=f.charAt(u+9*v))-w)>=0;i++)System.out.printf("%c%d%c%d ",65+p/7%8,8-p/56,65+u,8-v);}}}

```

Compile: `javac F.java`
Run: `java F 6pk/6pp/8/8/8/p7/PP4pp/Q2p2pK w - - 0 1`
Output: `B2B3 B2B4 B2A3 A1B1 A1C1 A1D1 H1H2 H1G1 H1G2`

---
Tags: code-golf, chess
---


title: Bulgarian Solitaire

text:
# Question
Title: Bulgarian Solitaire
Bulgarian Solitaire is a single-player game made popular by Martin Gardner in his mathematical column in *Scientific American*.

You have `N` identical cards, split into piles. You take a card from each pile and form a new pile with the removed cards. You repeat this process until you reach a state you've already seen and so continuing would repeat the loop.

For example, say you have `8` cards, split into a pile of `5` and a pile of `3`. We write the pile sizes in descending order: `5 3`. Here's a transcript of the game:

```
5 3
4 2 2
3 3 1 1
4 2 2

```

You first remove a card from each of the two piles, leaving piles of `4` and `2`, and a newly-created pile of `2`, giving `4 2 2`. In the next step, these decrease to `3 1 1` followed with a new pile of `3`. Finally, the last step empties the piles of size `1` and produces`4 2 2` which has already appeared, so we stop.

Note that the sum of the pile-sizes stays the same.

Your goal is to print such a transcript of the game from a given starting configuration. This is code golf, so fewest bytes wins.

**Input**

A list of positive numbers in descending order representing the initial pile sizes. Take input via STDIN or function input. You can use any list-like structure you want.

You don't get the total number of cards `N` as an input.

**Output**

Print the sequence of pile sizes the game of Bulgarian Solitaire goes through. Note that printing is required, not returning. Each step should be its own line.

Each line should have a sequence of positive numbers in descending order with no `0`'s. You may have separators and start and end tokens (for example, `[3, 3, 1, 1]`). The numbers might have multiple digits, so they should be separated somehow.

Print the pile-size splits you see until and including reaching a repeat. So, the first line should be the input, and the last line should be a repeat of a previous line. There shouldn't be any other repeats.

**Test cases**

```
>> [1]
1
1

>> [2]
2
1 1
2

>> [1, 1, 1, 1, 1, 1, 1]
1 1 1 1 1 1 1
7
6 1
5 2
4 2 1
3 3 1
3 2 2
3 2 1 1
4 2 1

>> [5, 3]
5 3
4 2 2
3 3 1 1
4 2 2

>> [3, 2, 1]
3 2 1
3 2 1

>> [4, 4, 3, 2, 1]
4 4 3 2 1
5 3 3 2 1
5 4 2 2 1
5 4 3 1 1
5 4 3 2
4 4 3 2 1

```

# Answer
> 4 votes
# Pyth, ~~40~~ 25

```
QW!}QY~Y]Q=Q_S+fTmtdQ]lQQ

```

This is pretty close to a translation of my python 2 answer.

Sample run:

Input:

```
[4,4,3,2,1]

```

Output:

```
[4, 4, 3, 2, 1]
[5, 3, 3, 2, 1]
[5, 4, 2, 2, 1]
[5, 4, 3, 1, 1]
[5, 4, 3, 2]
[4, 4, 3, 2, 1]

```

How it works:

```
Q                          Q = eval(input()) # automatic
 W!}QY                     while not Q in Y:
      ~Y]Q                     Y += [Q]
               fTmtdQ                     filter(lambda T: T, map(lambda d: d - 1, Q))
            _S+      ]lQ           sorted(                                             + [len(Q)])[::-1]
          =Q_S+fTmtdQ]lQ       Q = sorted(filter(lambda T: T, map(lambda d: d - 1, Q)) + [len(Q)])[::-1]
                        Q      print(Q)
QW!}QY~Y]Q=Q_S+fTmtdQ]lQQ

```

# Answer
> 3 votes
# Ruby, 98

```
f=->c{g={c=>1}
p *loop{c=(c.map(&:pred)<<c.size).sort.reverse-[0]
g[c]?(break g.keys<<c): g[c]=1}}

```

## Explanation

* Input is taken as the arguments to a lambda. It expects an `Array`.
* Previous game states are stored in the `Hash` `g`.
* To create a new game state, use `Array#map` to decrease every element by 1, add the length of the `Array` as an element, sort it in decreasing order and delete the element `0`.
* To check if a game state has been seen before, checking if `g` has a key for new game state is sufficient.

# Answer
> 3 votes
# CJam, 26 bytes

```
q{~_:(_,+0-$W%]___&=}g{p}/

```

Try it online.

### Example run

```
$ cjam <(echo 'q{~_:(_,+0-$W%]___&=}g{p}/') <<< '[5 3]'
[5 3]
[4 2 2]
[3 3 1 1]
[4 2 2]

```

# Answer
> 2 votes
## CJam, ~~35 34~~ 33 bytes

(Damn, this power cut that I was not the first one to post in CJam)

```
l~{_p:(_,+{},$W%_`_S\#0<\S+:S;}g`

```

Input:

```
[1 1 1 1 1 1 1]

```

Output:

```
[1 1 1 1 1 1 1]
[7]
[6 1]
[5 2]
[4 2 1]
[3 3 1]
[3 2 2]
[3 2 1 1]
[4 2 1]

```

Try it online here

# Answer
> 1 votes
# Python 2, ~~148~~ ~~130~~ 101

```
l=input()
s=[]
print l
while l not in s:s+=l,;l=sorted([i-1for i in l if 1<i]+[len(l)])[::-1];print l

```

This simply goes remembers all previous iterations, and checks if the new one is in that list. Then, it prints it out.

Sample run:

Input:

```
[4,4,3,2,1]

```

Output:

```
[4, 4, 3, 2, 1]
[5, 3, 3, 2, 1]
[5, 4, 2, 2, 1]
[5, 4, 3, 1, 1]
[5, 4, 3, 2]
[4, 4, 3, 2, 1]

```

Edit: I reread the specs to golf, plus applied a lot of golfing.

# Answer
> 1 votes
# GolfScript, ~~50~~ 46

```
~.p$[]{[1$]+\.{(.!";"*~}%\,+$.-1%p\.2$?)!}do];

```

Can almost certainly be golfed further. Try it out here.

# Answer
> 1 votes
# Python 2 - 103

```
p=input()
m=[]
print p
while p not in m:m+=[p];p=sorted([x-1 for x in p if x>1]+[len(p)])[::-1];print p

```

Similar to Quincunx' answer, but replaces appends with addition, and removes the last two lines.

Sample output:

```
[4, 4, 3, 2, 1]
[5, 3, 3, 2, 1]
[5, 4, 2, 2, 1]
[5, 4, 3, 1, 1]
[5, 4, 3, 2]
[4, 4, 3, 2, 1]

```

# Answer
> 1 votes
## CJam, ~~40~~ ~~36~~ 34 bytes

```
]l~{a+_W=_p:(_,+$W%{},1$1$a#0<}gp;

```

Test it here. Enter input as a CJam-style array, like `[5 3]`, into the STDIN field. Output format is similar, so square brackets and spaces as delimiters.

Even if I golf this down further (which is definitely possible), there's no way to beat Pyth with this. Maybe it's time to learn J. Explanation coming later.

# Answer
> 1 votes
# Haskell, 99

```
import Data.List
g l=until(nub>>=(/=))(\l->l++[reverse$sort$length(last l):[x-1|x<-last l,x>1]])[l]

```

# Answer
> 1 votes
# JavaScript (E6) 113

Worst entry so far :(

```
F=l=>{
  for(k=[];console.log(l),!k[l];)
    k[l]=l=[...l.map(n=>(p+=n>1,n-1),p=1),l.length].sort((a,b)=>b-a).slice(0,p)
}

```

**Test** in FireFox/FireBug console

```
F([4,4,3,2,1])

```

*Output*

```
[4, 4, 3, 2, 1]
[5, 3, 3, 2, 1]
[5, 4, 2, 2, 1]
[5, 4, 3, 1, 1]
[5, 4, 3, 2]
[4, 4, 3, 2, 1]

```

# Answer
> 0 votes
## Python 3: 89 chars

```
g=lambda l,s=[]:print(l)!=l in s or g(sorted([x-1for x in l if~-x]+[len(l)])[::-1],s+[l])

```

Much like the Python solutions already posted, but with recursive function calls rather than loops. The list `s` stores the splits already seen, and short-circuits out the recursion in case of a repeat.

The function `print()` (this is Python 3) just needs to be somehow called in each loop. The tricky thing is that a `lambda` only allows a single expression, so we can't do `print(l);...`. Also, it outputs `None`, which is hard to work with. I wind up putting `print(l)` on one side of an inequality; `==` doesn't work for some reason I don't understand.

An alternative approach of sticking it in a list uses equally many characters.

```
g=lambda l,s=[]:l in s+[print(l)]or g(sorted([x-1for x in l if~-x]+[len(l)])[::-1],s+[l])

```

Using `print(*l)` would format the outputs like `4 2 2` rather than `[4,2,2]`.

---
Tags: code-golf, game
---


title: Turn nouns into plurals

text:
# Question
Title: Turn nouns into plurals
Your task is to take as input an English noun and output its plural. To win the challenge you must trade off code length against accuracy.

Entries will be scored according to this comma-separated list of 95642 English nouns and their plurals. Your score is the length of your code in bytes, **plus** the number of nouns in this file that it does **not** correctly pluralise. If you manage to correctly pluralise every single line in the file then you may apply a **50% bonus**. (I don't expect anyone to claim this, but you never know.) The lowest score wins.

Every line in the file consists of a word composed of letters `[a-z]`, followed by `,`, followed by the plural, which is also composed of letters `[a-z]`.

Please note that the data in the file is pretty terrible. It was scraped from Wiktionary using someone else's script. There are duplicates, there are things that are not real words, and there are entries that are clearly completely wrong. But none of this matters from the point of view of the challenge. The goal is to produce a program that will correctly reproduce the plurals *as written in this file*; their correspondence or otherwise to correct English plurals is irrelevant. Also please note that, like any dictionary, the provided file contains its fair share of offensive terms.

Input and output may be performed in any way you find convenient. (Function parameters, command-line input, etc.)

To evaluate your score you will probably need to write some testbed code that iterates over the provided file. Please include this in your answer. This code need not be in the same language as your pluralising program, and should not be golfed. (It should be readable, so we can verify that it works.)

A useful tip: while developing your code, you will probably find it helpful to modify your testbed code so that it prints out every line for which your function fails. That way you can easily see which additional cases you need to consider.

**Illustrative examples**

the Python code

```
def p(a):
 return a+'s'

```

is 24 bytes. However, if we run it through the following evaluation function

```
def testPlural(func):
    badLines = 0
    with open("simpleNouns.csv") as file:
        for line in file:
            noun, plural = line.rstrip().split(',')
            if plural != func(noun):
                badLines += 1
    return badLines

```

then we can see that it fails in 11246 cases, giving a score of 24 + 11246 = **11270**.

However, if we update the function to

```
import re
def p(a):
 a+='s'
 return re.sub('ys$','ies',a)

```

then its length has increased to 58 bytes, but it now fails in only 7380 cases, giving a score of 58 + 7380 = **7438**.

# Answer
> 1 votes
I'll start us out with something simple.

# Javascript 232+2730=2962

```
w=prompt();r="ay,ays;ey,eys;oy,oys;y,ies;us,i;um,a;is,es;x,xes;man,men;s,ses;sh,shes;ch,ches;z,zes".split(";");for(i=0;i<r.length;i++){b=r[i].split(",");if(w.slice(-b[0].length)==b[0])return w.slice(0,-b[0].length)+b[1];}alert(w+"s")

```

Uses a small list of replacement rules. Fails 2730 test cases out of 95642.

# Answer
> 1 votes
## Python, 262+2606 = 2868

Small improvement over Peter Olson's answer. Perhaps can be better reimplemented in other language.

```
import re
def p(n):
 s=n
 for a in r'fe;ves lf;lves ([iln])um;\1a ([cgil])us;\1i (?<![ar])is;es man;men ea;eae (?<!f)ix;ices ((?<!k)s|x|sh|ch|z|j);\1es ((?<=.)[^aeiou])y;\1ies (?<!s);s'.split():
  b,c=a.split(';')
  n=re.sub(b+'$',c,n)
  if n!=s:break
 return n

```

---
Tags: code-challenge, kolmogorov-complexity, natural-language
---


title: Calculate the troll toll to safely pass

text:
# Question
Title: Calculate the troll toll to safely pass
Inspired by https://puzzling.stackexchange.com/q/626

---

In your adventures you arrive at a series of 7 bridges you have to cross. Underneath each bridge lives a troll. In order to cross the bridge, you must first give the troll a number of cakes as a percentage of the number of cakes you are carrying. Because these are kind trolls, they will give back a certain number of cakes to you.

At the start of each day, the local troll king sets the percent cake tax that each traveler must pay, and the troll cake refund -- the number of cakes that each troll must give back to travelers.

Your job is to calculate the minimum number of cakes needed to pass all 7 troll bridges for the given conditions on that day.

### Assume:

1. Two input parameters: percent cake tax (integer from 0 to 100), and troll cake refund.
2. No one, not even trolls, wants a cake partially eaten by another troll. If you are left with a fraction of a cake the troll gets it.
3. If a troll accepts a cake tax, but then has to give you back all of the cakes (is left with the same or fewer cakes than before), it will become angry and eat you and your cakes.
4. Every troll must keep at least one complete cake.
5. You can only carry a maximum of 100 cakes.
6. You need to end the day where you are currently located or on the other side of all 7 bridges.

### Challenge:

Write a complete program to output the minimum number of cakes to travel for the current day or zero if it's not possible to safely travel today -- you will wait to see what the numbers are tomorrow.

Input should be passed as stdin, command line arguments or file input.

Shortest code (byte count) wins.

### Example:

25% cake tax, 2 troll cake refund.

start with 19 cakes
before troll 1: (19 * 0.75) = 14.25
after troll 1: (14 + 2) = 16

before troll 2: (16 * 0.75) = 12
after troll 2: (12 + 2) = 14

etc.

19 cakes -\> 16 -\> 14 -\> 12 -\> 11 -\> 10 -\> 9 -\> 8
18 cakes -\> 15 -\> 13 -\> 11 -\> 10 -\> 9 -\> 8 -\> 8 (rule 3)

For 18 cakes, the last troll wouldn't get to keep any cakes. Therefore, the minimum number of cakes for a 25%/2 day is 19.

```
input: 25 2
output: 19

```

### Example 2:

90% cake tax, 1 troll cake refund

100 cakes -\> 11 -\> 2 -\> 1 (rule 4)

The third troll didn't get to keep any cake. Therefore it is not possible to travel on a 90%/1 day even starting with the maximum number of cakes.

```
input: 90 1
output: 0

```

---

### Data

Put together a quick graph of input and output values. I was surprised this wasn't "smooth" (like a bell curve or similar); there are several noticeable islands.

Data for those interested. Columns are divided into 5% intervals, rows are units of 1 cake refund intervals (excel rotated the image). You can see there can't be a refund higher than 28 cakes.

```
27, 17, 13, 14, 15, 18, 20, 24, 53, 66, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
47, 27, 20, 19, 19, 19, 24, 39, 48, 68, 100, 0, 0, 0, 0, 0, 0, 0, 0, 0
67, 37, 28, 24, 23, 28, 27, 29, 50, 70, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
87, 47, 33, 29, 27, 28, 31, 44, 37, 72, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
0, 57, 40, 34, 31, 29, 34, 34, 62, 74, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 67, 48, 39, 35, 38, 37, 49, 57, 76, 92, 0, 0, 0, 0, 0, 0, 0, 0, 0
0, 77, 53, 44, 39, 38, 47, 39, 59, 78, 94, 0, 0, 0, 0, 0, 0, 0, 0, 0
0, 87, 60, 49, 43, 39, 40, 54, 46, 80, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
0, 97, 68, 54, 47, 48, 44, 44, 71, 82, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
0, 0, 73, 59, 51, 48, 47, 59, 73, 84, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
0, 0, 80, 64, 55, 49, 51, 49, 68, 86, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
0, 0, 88, 69, 59, 58, 54, 64, 70, 88, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
0, 0, 93, 74, 63, 58, 57, 54, 57, 90, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
0, 0, 100, 79, 67, 59, 67, 69, 82, 92, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
0, 0, 0, 84, 71, 68, 60, 59, 77, 94, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
0, 0, 0, 89, 75, 68, 64, 74, 79, 96, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
0, 0, 0, 94, 79, 69, 67, 64, 66, 98, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
0, 0, 0, 99, 83, 78, 71, 79, 91, 100, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
0, 0, 0, 0, 87, 78, 74, 69, 93, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
0, 0, 0, 0, 91, 79, 77, 84, 88, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
0, 0, 0, 0, 95, 88, 87, 74, 90, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
0, 0, 0, 0, 99, 88, 80, 89, 77, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
0, 0, 0, 0, 0, 89, 84, 79, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
0, 0, 0, 0, 0, 98, 87, 94, 97, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
0, 0, 0, 0, 0, 98, 91, 84, 99, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
0, 0, 0, 0, 0, 99, 94, 99, 86, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
0, 0, 0, 0, 0, 0, 97, 89, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0

```

# Answer
## CJam, ~~46~~ ~~43~~ ~~41~~ ~~39~~ ~~38~~ ~~36~~ 33 bytes

```
100:H,{)_7{ea:i~H@m2$*H/+@;}*>}#)

```

Input via ARGV.

There is an online interpreter, but unfortunately it doesn't support command-line arguments. For testing, you can mimick it from STDIN with this version:

```
rr]:A;
100:H,{)_7{A:i~H@m2$*H/+@;}*>}#)

```

Explanation of the ARGV-based version:

```
100:H                                  "Push a 100 and save it in H.";
     ,                                 "Create a range (as an array) from 0 to 99.";
      {                       }#       "Find the first index in [0,1,2,...,99] for which the
                                        block produces a truthy (non-zero) value.";
       )_                              "Increment and duplicate the current array element.";
         7{                }*          "Execute the block seven times.";
           ea:i                        "Push the command-line arguments as an array of strings
                                        and convert each element to an integer";
               ~                       "Unwrap the array.";
                H@                     "Push a 100 and rotate the stack to pull up
                                        the first command line argument.";
                  m                    "Subtract (from 100).";
                   2$                  "Copy the last iterations result.";
                     *H/               "Multiply and divide by 100, deducting tax.";
                        +              "Add the refund.";
                         @;            "Rotate top three stack elements, and discard the one that
                                        has been pulled to the top. This always leaves the last
                                        two results on the stack.";

                             >         "Make sure that the last result was less than the second
                                        to last. Yields 0 or 1.";
                                )      "After the # search completes, we'll get -1 if no such
                                        index exists, or one less than the desired number if it
                                        does, so we can just increment.";

```

The contents of the stack are automatically printed at the end of the program.
> 6 votes

# Answer
## CJam, ~~**44 40 38 37**~~ 35 bytes

```
l~U100:M),{{_M5$-*M/3$+_@<*}7*}=]W=

```

Or when using command line arguments and `{}#` trick, **33 bytes**:

```
100:M,{){_ea:i~M@-@*M/+_@<*}7*}#)

```

Not putting this one as my main as `{}#` approach is inspired from Martin's answer.

Example run:

Input:

```
25 2

```

Output:

```
19

```

Another:

Input:

```
15 14

```

Output:

```
100

```

**How it works**

```
l~                       "Read the two numbers, swap and convert tax to double";
  U100:M),               "Push 0 and [0, 1, ... 100] to stack, storing 100 in M";
          {  ...  }=     "Run this code for each element until top stack element is 1";
           {...}7*       "Run this code block 7 times";
_                        "Copy the array element";
  M5$                    "Push 100 and a copy tax % to stack";
     -*                  "Number = (100 - tax %) * Number";
       M/                "Integer divide the number by 100";
         3$+             "Add refund";
            _@<*         "Convert to 0 if refunded number > before tax one";
                    ]W=  "Take the last element of the stack";

```

Try it online here
> 5 votes

# Answer
## APL (39)

```
T R←⎕⋄⊃Z/⍨{⍵(⊢×>)R+⌊⍵×1-T÷M}⍣7¨Z←⍳M←100

```

Explanation:

* `T R←⎕`: read two numbers from the keyboard and store them in `T` (tax) and `R` (return).
* `Z←⍳M←100`: store the number `100` in `M`, and all numbers from `1` to `100` in `Z`.
* `{`...`}⍣7¨`: for each element in `Z`, run the following function 7 times:
    + `R+⌊1-T÷M`: calculate how many cakes need to be paid,
    + `⍵(⊢×>)`: multiply that amount by 1 if the troll ends up with more cake than he started, or by 0 if not.
* `⊃Z/⍨`: for each element in `Z`, replicate it by the number that that function gave. (So all numbers for which the function returned `0` disappear.) Then select the first item from that list. If the list ended up empty, this gives `0`.
> 4 votes

# Answer
# C, 83 bytes

```
int cake(int perc_taken, int given_back)
{
    int startcake = floor(100.f/perc_taken*given_back+1);
    for(int i = 0; i < 6; i++)
    {
        startcake = ceil((startcake-given_back) * 100.f/(100 - perc_taken));
    }
    return startcake;
}

```

If it works, it works for all possible startcakes, not just from 1 to 100.

EDIT: It works. Golfed:

```
n(int p,int g) {int s=100./p*g+1,i=0;for(;i++<6;){s=ceil((s-g)*100./(100-p));}return s;}

```

With the 'maximum 100 cakes' limit:

```
n(int p,int g) {int s=100./p*g+1,i=0;for(;i++<6;){s=ceil((s-g)*100./(100-p));}return s>100?0:s;}

```

91 bytes.
> 3 votes

# Answer
# CJam, 36 bytes

```
q~:R100:H*\d:T/i){R-H*HT-/m]}6*_H)<*

```
> 2 votes

# Answer
# C++ - 202 chars

As usual, my C++ did the worst:

```
#include<iostream>
int main(){double p,g,c=1,i,r,t;std::cin>>p>>g;for(;c<101;c++){r=c;for(i=0;i<7;i++){t=(int)(r*(1-(p/100))+g);if(t>=r){r=-1;break;}r=t;}if(r!=-1)break;}r!=-1?std::cout<<c:std::cout<<0;}

```
> 1 votes

# Answer
## APL, 36

```
x y←⎕⋄101|1⍳⍨y<x×{y+⍵-⌈⍵×x}⍣6⍳x÷←100

```

**Explanation**

Note that there is a "cake threshold". For tax rate `x` and refund `y`, you will need strictly more than `y÷x` cakes to pass the next bridge.

`x y←⎕` take input and assign to `x` (tax) and `y` (return)
`⍳x÷←100` divide `x` by 100, and then generate an array of 1 to 100

`{y+⍵-⌈⍵×x}⍣6` call the "pass bridge" function 6 times:
`⌈⍵×x` The number of cakes you have, times tax rate, round up (the amount you pay)
`⍵-` Subtract from the number of cakes you have
`y+` Add the refund

Then you get a 100-element array showing the number of cakes you are left with after crossing 6 bridges if you start with 1~100 cakes. To see if you can cross the last bridge, check if you are above the threshold `y÷x`. Alternatively:
multiply the array by `x`
`y<` check if greater than `y`

Finally,
`1⍳⍨` find the index of first occurrence of `1` (true), returns `101` if not found
`101|` mod 101
> 1 votes

# Answer
**C 128**

Pretty similar to the other C solution but I think that's inevitable. The main trick is breaking out of the inner loop with different values depending on whether it goes to completion or not. This allows me to use ?: when I couldn't if I used break;

```
t,r,j,k,l,p;main(i){for(scanf("%d%d",&t,&r),i=101;k=--i;){for(j=8;--j>0;)(p=r+k*(100-t)/100)<k?k=p:j=0;j?0:l=i;}printf("%d",l);}

```

Ungolfed

```
int t,r,j,k,l,p;
main(int i)
{
    for(scanf("%d%d",&t,&r),i=101;k=--i;)
    {
        for(j=8;--j>0;)
        {
            if((p=r+k*(100-t)/100)<k)
                k=p;
            else
                j=0;
        }
        j?0:l=i;
    }
    printf("%d",l);
}

```
> 1 votes

---
Tags: code-golf
---


title: Closest fraction

text:
# Question
Title: Closest fraction
## Task:

Your program is given a proper, positive simple fraction in the format `<numerator>/<denominator>`.

For this input, it must find two fractions.

1. A fraction that is less than the input.
2. A fraction that is greater than the input.

Both fractions must have a lower denominator than the input. Of all possible fractions, they should have the lowest difference to the input.

## Output:

Your program's output must be:

* A fraction that is smaller than the input, in the format `<numerator>/<denominator>`.
* Followed by a space character (ASCII-code 32).
* Followed by a fraction that is greater than the input, in the format `<numerator>/<denominator>`.

As follows:

```
«fraction that is < input» «fraction that is > input»

```

## Rules:

* All fractions outputted must be in lowest terms.
* All fractions outputted must be proper fractions.
* If there are no proper fractions possible that are allowed by the rules, you must output `0` instead of a fraction \< input, and `1` instead of a fraction \> input.
* You can choose whether you want to receive the fraction as a command-line argument (e.g. `yourprogram.exe 2/5`) or prompt for user input.
* You may assume your program won't receive invalid input.
* The shortest code (in bytes, in any language) wins.
* Any non-standard command-line arguments (arguments that aren't normally required to run a script) count towards the total character count.
* What your program **must not** do:

+ Depend on any external resources.
    + Depend on having a specific file name.
    + Output anything other than the required output.
    + Take exceptionally long to run. If your program runs over a minute for fractions with a 6-digit numerator and denominator (e.g. `179565/987657`) on an average home user's computer, it's invalid.
    + Output fractions with `0` as the denominator. You can't divide by zero.
    + Output fractions with `0` as the numerator. Your program must output `0` instead of a fraction.
    + Reduce an inputted fraction. If the fraction given as input is reducible, you must use the fraction as it is inputted.
* Your program must not be written in a programming language for which there did not exist a publicly available compiler / interpreter before this challenge was posted.

## Examples:

**Input:** `2/5`
**Output:** `1/3 1/2`

**Input:** `1/2`
**Output:** `0 1`

**Input:** `5/9`
**Output:** `1/2 4/7`

**Input:** `1/3`
**Output:** `0 1/2`

**Input:** `2/4`
**Output:** `1/3 2/3`

**Input:** `179565/987657`
**Output:** `170496/937775 128779/708320`

# Answer
> 3 votes
## Sage – ~~119~~ 117

```
x,X=map(int,raw_input().split('/'))
a=0
A=c=C=1
while C<X:exec("ab,,AB"[c*X>C*x::2]+"=c,C");c=a+b;C=A+B
print a/A,b/B

```

Sage is only needed in the last line, which takes care of the output. Everything else also works in Python.

Replace `raw_input()` with `sys.argv[1]` to have the input read from a command-line argument instead of a prompt. This does not change the character count. (Does not work in Python without importing `sys` first.)

This essentially recursively constructs the respective Farey sequence using mediants of the existing elements, but restricts itself to those elements closest to the input. From another point of view, it runs a nested-interval search on the respective Farey sequences.

It correctly processes all of the examples in less than a second on my machine.

Here is an ungolfed version:

```
x,X = map(Integer,sys.argv[1].split('/'))
x = x/X
a = 0
c = b = 1
while c.denominator() < X:
    if c > x:
        b = c
    else:
        a = c
    c = ( a.numerator() + b.numerator() ) / ( a.denominator() + b.denominator() )
print a,b

```

# Answer
> 12 votes
# Python 2.7 - 138

```
x,y=n,d=map(int,raw_input().split('/'))
while y:x,y=y,x%y
def f(p,a=d):
 while(a*n+p)%d:a-=1
 print`(a*n+p)/d`+('/'+`a`)*(a>1),
f(-x);f(x)

```

I started with the obvious brute-force solution, but I realized that since the OP wanted to be able to solve instances with six digit numerators and denominators in under a minute, I need a better solution than trying a trillion possibilities. I found a handy formula on the Wikipedia page for the Farey sequence: If a/b, c/d are neighbors in one of the Farey sequences, with `a/b<c/d`, then `b*c-a*b=1`. The while loop inside f in my program extends this fact to non-reduced numbers, using the gcd, which the other while loop calculates.

I've golfed this pretty hard already, but I'd love to hear any suggestions.

## Edits:

166-\>162: Removed `a` and `b` from the outer program. They were unnecessary.
162-\>155: `str()` -\> \`\`
155-\>154: Added `k`.
154-\>152: Removed `x` from inside the function, passed it as an argument instead.
152-\>150: Gave `a` a default value instead of passing it as an argument.
150-\>146: Changed the initialization of `x` and `y`.
146-\>145: Removed `k`.
145-\>144: Changed ... and ... or ... to (...,...)\[...\], thereby saving a space.
144-\>138: Changed (...,...)\[...\] to ...+...\*(...). Thanks to @mbomb007.

## Test cases:

```
2/5
1/3 1/2

1/2
0 1

2/4
1/3 2/3

179565/987657
170496/937775 128779/708320

12345678/87654321
12174209/86436891 11145405/79132382

```

The second to last test took under a second on my computer, while the last one took about 5-10 seconds.

# Answer
> 5 votes
## Mathematica, 163 bytes

```
{a,b}=FromDigits/@InputString[]~StringSplit~"/";r=Range[b-1];""<>Riffle[#~ToString~InputForm&/@(#@DeleteCases[#2[a/b*r]/r,a/b]&@@@{{Max,Floor},{Min,Ceiling}})," "]

```

This is severely limited by the input/output requirement as user input and strings. Dealing with strings is really cumbersome in Mathematica (at least when you want to golf). Doing this the natural way in Mathematica, (using just integers and rationals) I'd probably get this down to 50% of the size.

It can do 6-digit numbers in a few seconds on my machine.

Slightly more readable (not really ungolfed though):

```
{a, b} = FromDigits /@ InputString[]~StringSplit~"/";
r = Range[b - 1];
"" <> Riffle[#~ToString~
     InputForm & /@ (#[DeleteCases[#2[a/b*r]/r, a/b]] & @@@ {{Max,
       Floor}, {Min, Ceiling}}), " "]

```

For the fun of it, doing this "the natural way", i.e. as a function taking numerator and denominator and returning two rationals, this is only **84 characters** (so my 50% estimate was actually pretty close):

```
f[a_,b_]:=#@DeleteCases[#2[a/b*(r=Range[b-1])]/r,a/b]&@@@{{Max,Floor},{Min,Ceiling}}

```

# Answer
> 3 votes
# Julia - ~~127~~ 125 bytes

I've approached this from a mathematical perspective to avoid need for loops, so this code runs quite fast for large inputs (note: if a/b is the input, then a\*b must fit within Int64 (Int32 on 32 bit systems), otherwise nonsense answers are generated - if a and b are both expressible in Int32 (Int16 on 32 bit systems), no problems occur).

UPDATE: There's no longer a need to overload backslash for div, by using ÷, a net saving 2 bytes.

```
a,b=int(split(readline(),"/"));k=gcd(a,b);f=b-invmod(a÷k,b÷k);d=2b-f-b÷k;print(a*d÷b,d<2?" ":"/$d ",a*f÷b+1,"/$f"^(f>1))

```

Ungolfed:

```
a,b=int(split(readline(),"/")) # Read in STDIN in form a/b, convert to int
k=gcd(a,b)           # Get the greatest common denominator
f=b-invmod(a÷k,b÷k)  # Calculate the denominator of the next biggest fraction
d=2b-f-b÷k           # Calculate the denominator of the next smallest fraction
print(a*d÷b,d<2?" ":"/$d ",a*f÷b+1,"/$f"^(f>1)) # Calculate numerators and print

```

Basic idea: find the largest d and f less than b that satisfies ad-bc=gcd(a,b) (next smallest) and be-af=gcd(a,b) (next largest), then calculate c and e from there. Resulting output is c/d e/f, unless either d or f is 1, in which case the /d or /f is omitted.

Interestingly, this means that the code also works for positive improper fractions, so long as the input is not an integer (that is, gcd(a,b)=a).

On my system, inputting `194857602/34512958303` takes no perceivable time to output `171085289/30302433084 23772313/4210525219`

# Answer
> 2 votes
## JavaScript, 131

With fat arrow notation and `eval` calls :

```
m=>{for(e=eval,n=e(m),i=p=0,q=1;++i</\d+$/.exec(m);)if(n*i>(f=n*i|0))g=f+1,p=f/i>e(p)?f+'/'+i:p,q=g/i<e(q)?g+'/'+i:q;return p+' '+q}

```

The `179565/987657` stress test is executed in approximately **35 seconds** on Firefox, a lot more on Chrome (~ 6 minutes)

Faster method and without `eval` and fat arrow notation

```
for(n=eval(m=prompt(a=i=p=0,b=c=d=q=1));++i<m.match(/\d+$/);)if(n*i>(f=n*i|0))g=f+1,p=f*c>i*a?(a=f)+'/'+(c=i):p,q=g*d<i*b?(b=g)+'/'+(d=i):q;alert(p+' '+q)

```

The `179565/987657` stress test is executed in approximately 5 seconds.

Not golfed :

```
m=prompt(); //get input
a=0; c=1; //first fraction
b=1; d=1; //second fraction
n=eval(m); //evaluate input
for (i=1; i<m.match(/\d+$/); i++) { //loop from 1 to input denominator
  f=Math.floor(n*i);
  if (n*i > f) { //if fraction not equal to simplification of input
    g=f+1; // f/i and g/i are fractions closer to input
    if (f/i>a/c) a=f, c=i;
    if (g/i<b/d) b=g; d=i;
  }
}
alert(a+'/'+c+' '+b+'/'+d); //output values handling 0 and 1 correctly

```

# Answer
> 2 votes
# perl, 142 bytes (155 without CPAN)

```
use bare A..Z;$/="/";N=<>;D=<>;F=N/D;K=G=1;for$H(1..D){J<F&&J>E?(E,I):J>F&&J<G?(G,K):()=(J=$_/H,"$_/$H")for(Z=int F*H)..Z+1}print I||0," $K\n"

```

Or if CPAN modules are disallowed / 3-4 times faster code is needed:

```
$/="/";$N=<>;$D=<>;$F=$N/$D;$g=$G=1;for$d(1..$D){$f<$F&&$f>$E?($E,$e):$f>$F&&$f<$G?($G,$g):()=($f=$_/$d,"$_/$d")for($z=int$F*$d)..$z+1}print$e||0," $g\n"

```

The former version takes 9.55 seconds on my machine, the latter version 2.44 seconds.

Less unreadable:

```
($N, $D) = split(m[/], <>);
$F = $N / $D;
$G = 1;
foreach $d (1 .. $D) {
    $z = int $F * $d;
    foreach $_ ($z .. $z + 1) {
        $f = $_ / $d;
        ($f < $F && $f > $E ? ($E, $e) :
        ($f > $F && $f < $G ? ($G, $g) : ())) = ($f, "$_/$d");
    }
}
print $e || 0, ' ', $g || 1, "\n";

```

---
Tags: code-golf, math, number, rational-numbers, division
---


title: Emulate the Professor's typing

text:
# Question
Title: Emulate the Professor's typing
# Emulate the Professor's typing

**Background**

Unfortunately, the Professor is not able to use his keyboard properly: whenever he is meant to use the `Shift` key, he presses `Caps Lock` **once** before typing, and doesn't bother to correct himself. If there are two or more keys in a row that require `Shift`, he presses `Caps Lock` before the first one and does nothing before the others.

As his secretary, I want to replicate this effect so that people think that he is the one replying to his emails, not me. He knows his typing looks stupid, but he doesn't care.

**Task**

Write a program that takes STDIN or file input of some text, and then outputs that text as if it had been typed by the Professor.

This is **code golf**, and standard loopholes are not allowed.

**Keyboard layout**

```
Default:
` 1 2 3 4 5 6 7 8 9 0 - =
   q w e r t y u i o p [ ]
    a s d f g h j k l ; ' #
   \ z x c v b n m , . /

With shift:
¬ ! " £ $ % ^ & * ( ) _ +
   Q W E R T Y U I O P { }
    A S D F G H J K L : @ ~
   | Z X C V B N M < > ?

With caps lock:
` 1 2 3 4 5 6 7 8 9 0 - =
   Q W E R T Y U I O P [ ]
    A S D F G H J K L ; ' #
   \ Z X C V B N M , . /

```

**Example input / output**

(The `CapsLock` line is just there for your understanding, and should not be outputted in your program)

```
Input:    abc ** def ! (ghijkl) mnop
Output:   abc 88 DEF 1 9GHIJKL0 mnop
CapsLock:     *      * *      *       (* means Caps Lock was pressed before this character)

Input:    print("Hello, World!"); sys.exit()
Output:   print92HELLO, world120; SYS.EXIT90
CapsLock:      *        *    *            *

Input:    !ABC!abc!ABC!abc!x!y!z
Output:   1ABC1ABC1abc1abc1X1y1Z
CapsLock: *       *       * * *

```

# Answer
## Python 2 - 269 ~~275 290 318 337~~

Input is mostly safe if you use triple-quotes:`"""print("Hello, World!"); sys.exit()"""`

```
C=D=0
r=''
l,u,c=" `1234567890-=qwertyuiop[]asdfghjkl;'#\\zxcvbnm,./",' \xac!"\xa3$%^&*()_+QWERTYUIOP{}ASDFGHJKL:@~|ZXCVBNM<>?'," `1234567890-=QWERTYUIOP[]ASDFGHJKL;'#\\ZXCVBNM,./"
for h in input():w=h!=' ';U=h in u;C^=w&U&~D;D=U&w;r+=[l,c][C][[l,u][U].find(h)]
print r

```

Encoding doesn't seem to help much, ~~except with the awkward ¬ and £ characters (I've tried looking at other problems like this and I think I should try to use split?)~~(It doesn't seem like the keyboard compresses enough to make it worth `.decode`, etc...)

Also, spaces suck.

Edit note: Indexing is *weird*
> 5 votes

# Answer
# PowerShell - 295

Takes input from the console (Read-Host), and outputs to the console.

```
$d=@("``1234567890-=qwertyuiop[]asdfghjkl;'#\zxcvbnm,./ ","``1234567890-=QWERTYUIOP[]ASDFGHJKL;'#\ZXCVBNM,./ ",'¬!"£$%^&*()_+QWERTYUIOP{}ASDFGHJKL:@~|ZXCVBNM<>? ')
((Read-Host).ToCharArray()|%{if($_-eq' '-or$d[2].IndexOf($_)-lt0){$a=0}else{if(!$a){$b=!$b}$a=2}$d[$b][$d[$a].IndexOf($_)]})-join''

```
> 3 votes

---
Tags: code-golf, keyboard
---