title: Crosswalk Efficiency

text:
# Question
Title: Crosswalk Efficiency
A standard road intersection contains 4 sidewalk corners and four crosswalks connecting them. It could also have 2 diagonal walks.

```
    sRRRRs
    iOOOOi
    dAAAAd
    eDDDDe
side0----1walk
ROAD|\  /|ROAD
ROAD| \/ |ROAD
ROAD| /\ |ROAD
ROAD|/  \|ROAD
side2----3walk
    wRRRRw
    aOOOOa
    lAAAAl
    kDDDDk

```

Not all 6 crosswalks are needed to let pedestrians get from any corner to any other (assuming no jaywalking). It's better for traffic and cheaper for the highway department if there are fewer crosswalks. However, it is better for pedestrians if they can get across faster.

Let L be the total length of the crosswalks present in the intersection. Assume the intersection is a unit square, so the length of orthogonal walks is 1 and for diagonal walks it's sqrt(2).

Let W be the average distance a pedestrian needs to walk when crossing the intersection. Each corner fills up with pedestrians evenly and each pedestrian at a corner is randomly headed for one of the 3 other corners with equal chance.

When L and W are low we have an efficient intersection. Let `E = 1 / (W * L)` be the crosswalk efficiency of a particular set of crosswalks. Higher E means more efficient.

## Goal

Write a program that takes in a list of present crosswalks and outputs the efficiency.

Input will come from stdin in the form `01 32 21` (for example), which represents an intersection with crosswalks from corners 0 to 1, 3 to 2, and 2 to 1 (in a Z). Output to stdout.

Running your program might look something like

```
$ crosswalk.mylanguage 01 23
0.0

```

## Scoring

This is code golf. The submission with the fewest characters wins.

## Details

* Pedestrians always stay on the crosswalks and always take the shortest route.
* Pedestrians can change direction where the diagonals meet (and at corners).
* If all corners aren't connected take W to be infinity (and E to be 0).
* The input crosswalk edges are always unique and there are only up to 6.
* The input or corner order doesn't matter. `01 32 21` is the same as `23 21 10`.

# Answer
> 1 votes
# Python 3 - 424 characters

This uses precalculated values for W:

```
u,s=list(map(list,[map(int,x) for x in input().split()])),2**.5
q,p,o,w,e,r=sum(u,[]),(2*s+1)/3,(s+1)/3,(2*s+3)/3,(s+3)/3,(5*s+1)/6
print(.0 if len(set(q))<4 or len(q)<5 and q[0]^q[1]==q[2]^q[3]!=3 else 1/({66:p,80:p,34:w,48:w,42:e,49:e,10:5/3,17:5/3,72:r,65:r,74:o,81:o,73:p,41:(s+2)/2,64:s,18:4/3,82:(s+2)/3,50:(s+6)/6}[sum([(0,1,8,32)[q[x]^q[x+1]] for x in range(0,len(q),2)])]*sum(map(lambda a:(1,s)[a[0]^a[1]==3],u))))

```

It can be run like this:

```
echo 32 01 31 | python3 filename.py

```

# Answer
> 1 votes
# Python - 489

Uses all pairs shortest paths.

```
import re
R=re.sub
exec R("I"," in ",R("F","for ","""s,m,i=sum,map,int
r=2**.5/2
n=1e309
g=[0,1,1,n,r],[1,0,n,1,r],[1,n,0,1,r],[n,1,1,0,r],[r]*4+[0]
f="01021323"
o=lambda v:[list(v[x:x+2])FxIrange(0,len(v),2)]
v=o(f+"04142434")
q=m(sorted,R("12|21","14 24",R("03|30","04 34",raw_input())).split())
r=range(5)
u=[m(i,x)FxIv if x notIq]
l=s(g[i(y)][i(x)]Fy,xIq)
Fy,xIu:g[y][x]=n
FaIr:
 FbIr:
    FcIr:g[b][c]=min(g[b][a]+g[a][c],g[b][c])
w=s(g[i(y)][i(x)]Fy,xIo(f+"0312"))/6.
print 1/(w*l)"""))

```

---
Tags: code-golf
---


title: Courier Ception

text:
# Question
Title: Courier Ception
# Courier Ception

The program must accept any string as input and output an pixel image that shows the input string in Courier. All the letters that contain a 'hole' (like `abdegopqABDPQR` etc) that is surrounded by black pixels must be also filled black.

## Input

The Program must be able to accept any ASCII string as input. The input can be any way you want, as long as the program code itself does not have to change in order to accept a different input. (Except for e.g. the filename of the file that is to be read.) No standard loopholes. You can assume that each input contains at least one printable letter.

## Output

The output must be a black and white (no gray) pixel graphic that shows the string written in Courier (in black, background white), with the specified 'holes' filled. The fontsize of the whole string must be constant (that means no different scaling for each different letters) so that the full sized letters (e.g. `ABCDEFGHIJKLMNOPRSTUVWXYZ` but j and Q are bigger) must be at least 10px in height. (You do not have to write it to a file, any kind of display is ok as long as it is generated as pixelgraphics, as e.g. canvas in JavaScript.) Please post this graphic with your answer.

Access to courier.ttf / font libraries is allowed.

The program must as well count the number of black pixels and write it to console or what ever output method prefered in the end.

## Score

The score is evaluated as follows: The full program code must be used as input string to your program. The number of black pixels will be your score. **Program code that contains non-printable or non-ASCII letters is not allowed.** (As well as standard loopholes.) The lower the score the better.

# Answer
> 12 votes
## Mathematica, 4864 pixels

```
l = ImageData[Binarize[Rasterize[Style[j, FontSize -> 15]], .71]]
i = {{1, 1}}
While[Length[i] > 1 - 1,
 {r, c} = j = i[[1]]; l[[r, c]] = 2; i = i[[2 ;; -1]];
 If[FreeQ[i, {r, c} = J = j + #] && l[[r, c]] == 1,
    i = i~Join~{J}] & /@
  {{1, 1 - 1}, {1 - 1, 1}, {-1, 1 - 1}, {1 - 1, -1}}
 ]
Image[l = l /. 1 -> 1 - 1 /. 2 -> 1]
Count[l, 1 - 1, {2}]

```

Here is the picture:

In Mathematica when you write a "program" you just write a snippet. So this expects the input stored in `j` and the last thing it returns is the image and the count. This also spits out a bunch of errors, because I don't do bounds checking on `l`, but it produces the desired result anyway.

where `%` refers to said last output.

Thanks to Geobits for the idea for the algorithm. I'm flood-filling the image from the top-left corner with an invalid intensity, then I replace all remaining white pixels with black pixels, and the invalid ones with white ones.

Note that the `FreeQ` check isn't actually necessary for the program to work correctly, but for it to finish in a reasonable amount of time. If I'd leave it out, I'd actually score about 300 pixels less.

---
Tags: code-challenge, graphical-output
---


# Question
Title: Can the dog reach the neighbour's house?
A dog is leashed to a pole and the owner wants to know if it can venture to the neighbour's building. You're given a map, which contains the pole (represented by `x`), the owner's buildings (represented by `1`) and the neighbour's building (represented by `2`). Empty areas are padded with dots and every line has the same length. **EDIT: I forgot to mention, neighbour is always to the right from the dog.** Every tile represents an area of one square meter. You're also given the length of the dog's leash (as meters). The pole is at the center of the tile. For input you must use the STDIN (and respectively STDOUT for output), if it's available in your language. Otherwise create a function, which takes the input as parameters and returns the answer. An example input to the STDIN would look like this.

```
6
............
...11..222..
...11..222..
...11.......
.x.11.......
............

```

Additional newline is guaranteed after the input. The program should output `Yes` if the dog can reach the neighbour's building and otherwise `No`.

## Assumptions

* There can be several buildings belonging to the owner.
* There can only be one neighbour's building.
* The dog can't venture outside the map or through the buildings.
* The dog can't be trapped inside a building.
* The length of the leash is always an integer
* Distances are calculated in Euclidean metric.

This is a codegolf, shortest code wins.

## Test cases

Input:

```
6
............
...11..222..
...11..222..
...11.......
.x.11.......
............

```

Output: `No`

Input:

```
7
............
...11..222..
...11..222..
...11.......
.x.11.......
............

```

Output: `Yes`

Input:

```
7
........
...11...
..111.22
..111.22
.x111.22
..111.22
..111...

```

Output: `No`

Input:

```
8
........
...11...
..111.22
..111.22
.x111.22
..111.22
..111...

```

Output: `Yes`

# Answer
## PHP 781 chars

I know this can be smaller but I am sorry that I am confused. If I take your first two examples (answers no and yes), if diagonal moves are not allowed, answers should be no and no, surely. If diagonal moves are allowed, answers should be yes and yes. Have I misunderstood?

I also took beside to be the criteria of 'reached' as the dog can then wee on the building - however changing that to on top of can easily be done changing the pass counter which currently equals leash length.

Anyway, this allows for diagonal movement, non diagonal would be smaller than this.

```
<?php
$a.='7
............
...11..222..
...11..222..
...11.......
.x.11.......
...........';$b='No';$c=array();$d=array();function check_2($e,$f){if(($c[$e+1][$f-1]=='2')OR($c[$e+1][$f]=='2')OR($c[$e+1][$f+1]=='2')OR($c[$e][$f-1]=='2')OR($c[$e][$f]=='2')OR($c[$e][$f+1]=='2')OR($c[$e-1][$f-1]=='2')OR($c[$e-1][$f]=='2')OR($c[$e-1][$f+1]=='2')){return TRUE;;}else{return FALSE;}}str_replace("\n\r","\n",$a);$g=explode("\n",$a);$h=$g[0];unset($g[0]);$i=count($g);$j=0;foreach($g as $k){$l=str_split($k);$m=count($l)+1;unset($l[$m]);$c[$j]=$l;++$j;}$d=$c;for($n=0;$n<=$h;++$n){for($e=0;$e<$i;++$e){for($f=0;$f<$m;++$f){if($c[$e][$f]=='2'){$b='Yes';}if($c[$e][$f]=='x'){for($o=-1;$o<2;++$o){for($p=-1;$p<2;++$p){if($c[$e+$o][$f+$p]=='.'){$d[$e+$o][$f+$p]='x';}}}}}}$c=$d;}echo $b;?>

```

I am pretty sure I can make this smaller but with the confusion not sure which way to go.

Anyway this is my first flood fill so I am sure it can be done more efficiently. Most of the work was getting the input into a variable and a multi dimensional array.

The input it contained in the first variable $a. You can see it here on codepad.

I hope you like it. As a relative newbie and since this is the only answer I suppose I am officially winning here at the moment. Although I cannot imagine this will last long if someone else enters :-)
> 2 votes

---
Tags: code-golf
---


title: Basic Algebraic Expansion

text:
# Question
Title: Basic Algebraic Expansion
## Problem

I've got a GREAT new program that will change the way we think about math in computing, taking in strings of algebraic functions and doing AMAZING things with them! The only problem, is that I am only able to parse specific algebra, otherwise the universe folds into itself, which is bad. Fortunately, I only need a few basic operations in this amazing new program's input, but I still need it expanded!

## Rules

* An answer must be able to simplify the following expressions

+ `2+2` should reduce to `4`
    + `(5+x)+6` should reduce to `x+11`
    + `(x+2)^2` should reduce to `x^2+4*x+4`
    + `(x-5)*(3+7*x)` should reduce to `7*x^2-32*x-15`
    + `5*x+9*x` should reduce to `14*x`
    + `(2*x^2)*x^3` should reduce to `2*x^5`
* Answers must be able to COMPLETELY remove parenthesis, which implies that all distribution must take place.
* Answers should be able to handle all of the following operators and standard tokens:

+ `+` (The addition function)
    + `-` (The subtraction function)
    + `*` (The multiplication function)
    + `(` (The left parenthesis, used to indicate a group)
    + `)` (The right parenthesis, used to indicate the end of the last started group)
    + `x` (The standard variable)
    + `[0-9]+` (literal nonnegative numbers)
* Answers must be capable of at least squaring, using the notation expr^2, including (expr)^2 recursively, since (expr) is itself an expression ;)
* A solution must be in a standard infix notation, none of the RPN nonsense!
* No library functions such as Mathematica's `Simplify` to do this for you.
* Solution should be a function that takes in a single argument and return the expanded version

As this is code-golf, the answer with the fewest (key)strokes wins, 1 week from OP.

## Notes

There are no spaces in this world of math, of course! Only parenthesis.

So no division is required to save from factoring

Standard order of operations apply.

I'm aware that some of what I'm asking is simplification (e.g. `2+2=4`) where other parts are actually the opposite, such as expanding `(x+1)^2` to be `x^2+2x+1`. This is intentional. :)

-25 strokes for a solution that can do (expr)^n instead of just (expr)^2

-15 strokes for a solution able to evaluate juxtaposed multiplication, such as `4x+5x` == `9x`, or `4(x+1)` = `4x+4`

-5 strokes for a solution able to handle multiple variables (A variable being exactly one lowercase alphabet character)

-5 strokes for a solution able to remove leading 0's (`007` to just `7` \[Not today, Bond!\] \[Jeez now I feel like I'm writing Lisp\])

# Answer
> 2 votes
# J - 350 char - 25 = 325 pts

Forgive me, Roger Hui, for I have sinned.

```
x=:0 1
f=:(('+_';'-';'_';'-')rplc~' '-.~'+'}.@,@|.@,.s(}.@]`(,&":)@.t'*x'"_`('*x^',":)`(''"_)@.t=.*@<:@[)/"1@#~0~:0{|:@s=.,.i.@#)@p=:(0{::'()'+/@,:&,e'+'@((+/@,:&,-)~e'-')@(*/a e'*')@('^'(*/(a=.+//.@)/@#,:e=:2 :'(<@; ::({:u/&.>{.)/.~i.@#-i.@#(>+>:)(<,v){.@i.~])^:_'))@:(([^:(''-:])". ::])&.>)@([-.~;@]<@(p^:(1<#));.1~1,0=2*/\[:+/\(*0,}:@)1 _1 0{~i.)&;:])

```

The above monstrosity defines a number of variables, of which the variable `f` is a function satisfying the constraints in the question above. I claim the "expr^n" bonus for 25 points.

Here's the golf in action at the J REPL.

```
   x=:0 1
   f=:(('+_';'-';'_';'-')rplc~' '-.~'+'}.@,@|.@,.s(}.@]`(,&":)@.t'*x'"_`('*x^',":)`(''"_)@.t=.*@<:@[)/"1@#~0~:0{|:@s=.,.i.@#)@p=:(0{::'()'+/@,:&,e'+'@((+/@,:&,-)~e'-')@(*/a e'*')@('^'(*/(a=.+//.@)/@#,:e=:2 :'(<@; ::({:u/&.>{.)/.~i.@#-i.@#(>+>:)(<,v){.@i.~])^:_'))@:(([^:(''-:])". ::])&.>)@([-.~;@]<@(p^:(1<#));.1~1,0=2*/\[:+/\(*0,}:@)1 _1 0{~i.)&;:])

   f '2+2'
4
   f '(5+x)+6'
x+11
   f '(x+2)^2'
x^2+4*x+4
   f '(x-5)*(3+7*x)'
7*x^2-32*x-15
   f '5*x+9*x'
14*x
   f '(2*x^2)*x^3'
2*x^5
   f '(2*x+3)^(2+3)*2^3'   NB. bonus
256*x^8+1920*x^7+5760*x^6+8640*x^5+6480*x^4+1944*x^3

```

Here's the gist of what's going on.

* `'()'...@([-.~;@]<@(p^:(1<#));.1~1,0=2*/\[:+/\(*0,}:@)1 _1 0{~i.)&;:` \- Recursively break down the expression based on its parenthesized subexpressions, and evaluate them (the `...` bit, to be described below) as they are ready. `;:` performs the tokenizing.
* `(([^:(''-:])". ::])&.>)` \- Evaluate atoms. If the atom is numeric, it is turned into a scalar number. If the atom is an operator, it is left as-is. If the atom is the variable `x`, it is turned into the vector `0 1`. (That's why we define `x=:0 1` at the start.) In general we store the polynomial `a*x^n + b*x^(n-1) + ... + c*x + d` as the `n+1`-item list `d c ... b a`.
* `e=:2 :'(<@; ::({:u/&.>{.)/.~i.@#([->+>:){.@i.&(<,v))^:_'` \- This curious conjunction takes a verb on the left and a character on the right. It finds the first instance of that character in its tokenized, paren-less input, and evaluates it with the arguments around it, and repeats until there are no more such characters to find. Thus, we iteratively simplify the expression, with order of operations controlled by order of application of `e`.
* And then all the stuff in the front is just pretty-printing output. `rplc` is a standard library function for substring replacement. We can save another three chars if we're allowed to put the lowest degree terms first instead of the highest, by removing the `@|.`.

I am honestly uncertain whether I can squeeze any more characters out of this golf. I can't think of any other approach that doesn't require a similar amount of overengineering, but that doesn't mean there isn't one. Either way, I'm pretty sure I've squeezed all the obvious characters out of this version.

# Answer
> 2 votes
# JavaScript (EcmaScript 6) 698 (748-50 bonus) ~~725 780 1951~~

~~To be golfed~~. But I'm proud it works.
(Edit: bug fix, problems with brackets and minus)
(Edit2: golfed more, fixed bug in output)
(Edit3: golfed once more, last time I promise)

**Comment**

Basically, function X is an infix calculator that operates on literal polynomials.
Each polynomial is stored as a js object, the key being the term (x^3y^2) and the value being the numeric coefficient. Function A,M and E are add, multiply and exponent.

**Golfed Code**

(It cannot probably be golfed more...) Note: not counting newlines added for (ehm...) readability

```
K=x=>Object.keys(x).sort(),
A=(p,q,s,t,c)=>[(c=(s+1)*q[t]+~~p[t])?p[t]=c:delete(p[t])for(t in q)],
M=(p,q,t,c,o,u,f,r,v={})=>([A(v,(r={},[(c=p[f]*q[t])&&(r[o={},(u=f+t)&&(u.match(/[a-z]\^?\d*/ig).map(x=>o[x[0]]=~~o[x[0]]+(~~x.slice(2)||1)),K(o,u=k).map(i=>u+=o[i]>1?i+'^'+o[i]:i)),u]=c)for(f in p)],r),k)for(t in q)],v),
E=(p,n)=>--n?M(p,E(p,n)):p,
O=n=>{for(l=0;h(o=s.pop())>=h(n);)a=w.pop(b=w.pop()),o=='*'?a=M(a,b):o>d?a=E(a,b[k]):A(a,b,o),w.push(a);s.push(o,n)},
X=e=>(l=k='',w=[],s=[d='@'],h=o=>'@)+-*^('.indexOf(o),
(e+')').match(/\D|\d+/g).map(t=>(u=h(t))>5?(l&&O('*'),s.push(d)):u>1?O(t):~u?s.pop(s.pop(O(t)),l=1):(l&&O('*'),l=1,w.push(v={}),t<d?v[k]=t|0:v[t]=1)),
K(p=w.pop()).map(i=>(k+=(c=p[i])>1?s+c+i:c<-1?c+i:(c-1?'-':s)+(i||1),s='+')),k||0)

```

**Test** In FireFox console

```
['2+2','(5+x)+6','(x+2)^2','(a+b)(a-b)','(a+b)*(a-b)','(a-b)(a-b)', '(x-5)*(3+7*x)','5*x+9*x','(2*x^2)*x^3','(2*x+3)^(2+3)*2^3']
.map(x => x + ' => ' + X(x)).join('\n')

```

**Output**

```
2+2 => 4
(5+x)+6 => 11+x
(x+2)^2 => 4+4x+x^2
(a+b)(a-b) => a^2-b^2
(a+b)*(a-b) => a^2-b^2
(a-b)(a-b) => a^2-2ab+b^2
(x-5)*(3+7*x) => -15-32x+7x^2
5*x+9*x => 14x
(2*x^2)*x^3 => 2x^5
(2*x+3)^(2+3)*2^3 => 1944+6480x+8640x^2+5760x^3+1920x^4+256x^5

```

**Bonuses**

```
25: 2*x+3)^(2+3)*2^3 => 1944+6480x+8640x^2+5760x^3+1920x^4+256x^5
15: 4x+5x => 9x
5: 007x+05x^(06+2) => 7x+5x^8
5: (a+b)(a-b) => a^2-b^2

```

**Ungolfed Code**

```
Show=(p)=>(
  Object.keys(p).sort().map(i=>(c=p[i])-1?c+1?c+i:'-'+i:i).join('+').replace(/\+-/g,'-')
)
AddMonoTo=(poly, term, coeff, c)=>(
  (c = coeff + ~~poly[term]) ? poly[term]= c : delete(poly[term])
)
AddPolyTo=(p1, p2, s, t)=>(
  [ AddMonoTo(p1, t, (s+1)*p2[t]) for (t in p2)]
)
MulTerm=(t1, t2, o={})=>(
  (t1+=t2)&&
  (t1.match(/[a-z](\^\d+)?/g).every(x=>o[x[0]]=(~~x.slice(2)||1)+(~~o[x[0]])),
  Object.keys(o,t1='').sort().every(i=>t1+=o[i]>1?i+'^'+o[i]:i)),
  t1
)
MulMono=(poly, term, coeff, c, r={}, t)=>(
  [(c = poly[p]*coeff) && (r[MulTerm(p,term)] = c) for (p in poly) ],r
)
MulPoly=(p1, p2, r={}, p)=>(
  [AddPolyTo(r,MulMono(p2, p, p1[p]),'') for (p in p1)],r
)
ExpPoly=(p,n,r=p)=>{
  for(;--n;)r=MulPoly(r,p);
  return r
}
Expand=ex=>
{
  var tokens = ex.match(/\D|\d+/g).push(')')
  var t,a,b,v,LastV=0
  var vstack=[]
  var ostack=['_']
  var op={ '+': 3, '-':3, '*':4, '^':6, '(':8, _: 1, ')':2}
  var OPush=o=>ostack.push(o)
  var OPop=_=>ostack.pop()
  var VPush=v=>vstack.push(v)
  var VPop=v=>vstack.pop()

  var Scan=i=>
  {
    LastV=0 ;
    for (; (t=tokens[i++]) && (t != ')'); )
    {
      if (t == '(')
      {
        if (LastV) CalcOp('*')
        OPush('_'), i=Scan(i)
      }
      else if (op[t])
        LastV=0, CalcOp(t)
      else
      {
        if (LastV) CalcOp('*')
        LastV = 1
        VPush(v={})
        t < 'a' ? v[''] = t|0 : v[t] = 1
      }
    }
    CalcOp(t);
    OPop();
    OPop();
    LastV=1;
    return i;
  }
  var CalcOp=nop=>
  {
    for (; op[po = OPop()] >= op[nop];)
      b=VPop(), a=VPop(), CalcV(a,b,po);
    OPush(po), OPush(nop);
  }
  var CalcV=(a,b,o)=>
  {
    if (op[o] < 4)
      AddPolyTo(a,b,o)
    else if (o == '*')
      a=MulPoly(a,b)
    else // ^
      a=ExpPoly(a,b['']) // only use constant term for exp
    VPush(a)
  }
  Scan(0)

  return Show(vstack.pop())
}

```

# Answer
> 1 votes
# Mathematica: 56 - 25 - 15 - 5 - 5 = 6

Of course no library functions as `Expand` or `Distribute`, just pattern replacement. Mathematica does almost everything for us (hax!), what is left are just rules for distribution and power expansion. The only non-trivial examples therefore are `(x-5)*(3+7*x)` and `(x+2)^2`.

```
f=#//.{x_ y_Plus:>(x #&/@y),x_Plus^n_:>(x #&/@x)^(n-1)}&

```

Examples

```
(x-5)*(3+7*x) // f
-15 - 32 x + 7 x^2

(x + 2)^2 // f
4 + 4 x + x^2

```

---
Tags: code-golf
---


title: Break out of a loop

text:
# Question
Title: Break out of a loop
Now that we have over a hundred ways to get stuck in a loop, the next challenge is to get out.

Specifically, write a piece of code with a (seemingly) infinite loop, but somehow manage to break out.

The "infinite loop" can be a statement like `while true`, `for (;1>0;)` or anything else which obviously lasts forever. Recursion does not count (since stack overflows will quickly occur).

To break out, you need to execute an instruction written just after the loop. You can not just exit the program or leave the method.

Valid answer (if only it somehow exited the loop):

```
while (true)
    print("I'm stuck!")

print("I escaped!")

```

Invalid answer:

```
define loop() {
    while (true)
        print("I'm stuck!")
}

loop()
print("I escaped!")

```

# Answer
> 8 votes
# GolfScript

```
"0:1 Argentina - Germany":party~
{party puts 1}do
"Party is over."

```

Try it online.

### How it works

```
"0:1 Argentina - Germany" # Push party string.
:party                    # Save string in party variable.
~                         # Discard the string from the stack.
{                         #
  party                   # Push party string.
  puts                    # Print string followed by a newline.
  1                       # Push a truthy conditional on the stack.
}do                       # Pop conditional from the stack and repeat the loop if truthy.
"Party is over."          # Should never happen.

```

### Why is the party over?

> `~` not only discards he string; it evaluates it. Notably, it executes `0:1`. Since `1` is a valid identifier (which happens to have the default value `1`), this saves the value `0` in the variable `1`. Therefore, the loop's conditional will be falsy, so it is executed only once.

# Answer
> 4 votes
# C

Classic integer overflow.

```
#include<stdlib.h>

int main() {
    unsigned a = 0;
    unsigned b = 1000;
    while (a<b) {
        a++;
        b++;
    }
    puts("Hi");
    return 0;
}

```

# Answer
> 1 votes
# C/C++

The following program outputs

```
I'm stuck at 41...
I'm stuck at 18467...
I'm stuck at 6334...
I'm stuck at 26500...
I'm stuck at 19169...
I'm stuck at 15724...
I'm stuck at 11478...
I escaped at 29358!

```

(the output on your system may be different)

```
#include <stdio.h>
#include <stdlib.h>
#include <setjmp.h>

jmp_buf b;

int my_location()
{
    int result = rand();
    if (result % 7 == 0)
        longjmp(b, result);
    return result;
}

int main()
{
    int location = setjmp(b);

    if (location)
        return printf("I escaped at %d!\n", location);

    for (;;)
    {
        printf("I'm stuck at %d...\n", my_location());
    }
}

```

The "infinite" loop at the end of the `main` function is broken

> by the `longjmp` function, which is called when a random number becomes divisible by 7.

This is pretty standard... For people who are old enough to remember that trick (which was once pretty much the only way to implement this behavior in C).

# Answer
> 1 votes
## Befunge-98

This program breaks out of its infinite loop by randomly modifying itself

```
"ITRH"4(v
        >222Sac*%Se3*%S5%S.pp

```

# Answer
> 1 votes
# C

Patricide

```
#include <stdio.h>
#include <unistd.h>

int main(void) {
    pid_t id = fork();

    if (id != 0) {
        while(1) {
            wait(1);
            printf("Apples\n");
        }
    }
    else {
        wait(5);
        kill(getppid(), 9);
    }

    printf("Bananas\n");
}

```

Fork a child process and enter an endless loop: child process terminates the parent process with a KILL signal.

# Answer
> 0 votes
# Java with SnakeYAML library used

Know your libraries :)

```
import java.util.ArrayList;
import java.util.List;
import org.yaml.snakeyaml.Yaml;
public class UnLoop
{
    final static List<Object> queue = new ArrayList<>();
    public static void main(String[] args)
    {
        //running serializer nonstatic
        new Thread(()->{
        for(;;){
            if(queue.size()!=0)
            System.out.println(new Yaml().dump(
                    queue.remove(0)));

            }}).start();

        queue.add("DERP");
        queue.add(new String[]{"1","2","3","4"});
        queue.add(new java.awt.Point(1, 1));

    }
}

```

> Snakeyaml hates to serialize certain objects due to the way it works, java.awt.point is one of then, so it stackoverflows out

to satisfy the rule the loop is now a serializing thread and the data inerted from another thread

# Answer
> 0 votes
## C

```
#include <stdio.h>
int i;
int main()
{
    ++i;
    while(i)
    {
        i*=1000;
        printf("%d",i);
    }
}

```

---
Tags: popularity-contest, underhanded
---


title: There is water on my window

text:
# Question
Title: There is water on my window
## The scenario

I drive along a road with my car and it begins to rain. The raindrops are falling on my window randomly and now i ask myself, where is the biggest connected wet area?

## The task

To make it easier, the window is split in a matrix of 10\*10 squares. Your job is to find the biggest connected water-drop-area on the window.

## Input

There are two possible inputs, you can use a 2-dimensional Array or a 1-dimensional one. You can choose between any inputs like stdin, etc...
Example:

```
// 2-dimensional:
[[0,1,0,0,0,0,1,0,0,0],
 [0,1,1,0,0,0,0,1,1,0],
 [0,1,1,0,0,0,0,1,0,0],
 [0,1,0,0,0,0,0,0,0,0],
 [0,0,0,0,0,0,0,0,1,0],
 [0,0,0,1,1,0,0,0,1,0],
 [0,0,0,1,1,0,0,0,1,0],
 [0,0,0,0,0,1,1,0,1,0],
 [0,0,0,0,0,1,1,0,1,0],
 [0,0,0,0,0,0,0,0,0,0]]

// 1-dimensional
[0,1,0,0,0,0,1,0,0,0,
 0,1,1,0,0,0,0,1,1,0,
 0,1,1,0,0,0,0,1,0,0,
 0,1,0,0,0,0,0,0,0,0,
 0,0,0,0,0,0,0,0,1,0,
 0,0,0,1,1,0,0,0,1,0,
 0,0,0,1,1,0,0,0,1,0,
 0,0,0,0,0,1,1,0,1,0,
 0,0,0,0,0,1,1,0,1,0,
 0,0,0,0,0,0,0,0,0,0]

```

## Output

Your code has to put out the size of the biggest connected area and the x- and y-coordinates of the waterdrops which belong to this area in the format
"Size: Z Coordinates: (X1,Y1) (X2,Y2) ..."
Example for the previous input:

```
Size: 6 Coordinates: (1,0) (1,1) (2,1) (1,2) (2,2) (1,3)

```

The order of the Coordinates doesn't matter.

## Rules

* Waterdrops are connected, if they touch each other orthogonally
* Diagonal connections don't count
* There can be many areas and your code has to find the biggest one
* An empty field is represented as "0" and a wet field as "1"
* Post your solution with a short explanation and the output of the previous input
* The shortest code within the next 7 days will win
* If there are two areas with the same size, you can choose one

### Winner: Ventero with 171 - Ruby

# Answer
## Ruby, 171 characters

```
r=eval *$*
u=(0..99).map(&v=->p{-~p*r[p]>0?" (#{r[p]=0;u=p%c=10},#{p/c})"+v[p+c]+v[p-c]+v[u>0?p-1:p]+v[u<9?p+1:p]:""}).max_by &:size
puts"Size: #{u.size/6} Coordinates:"+u

```

Input via command line parameter as one-dimensional array.

Output for the sample input: `Size: 6 Coordinates: (1,0) (1,1) (1,2) (1,3) (2,2) (2,1)`

This answer uses a simple flood-fill approach, building a list of coordinates for each raindrop cluster. Most of the code is actually used for bounds checking and I/O.
> 3 votes

# Answer
# Python - 192

```
a=10;g+=[0]*a
def f(k):
 if g[k]:g[k]=0;return" (%d,%d)"%(k/a,k%a)+f(k+a)+f(k-a)+f(k+(k%a<9))+f(k-(k%a>0))
 return''
m=max(map(f,range(100)),key=len)
print"Size: "+`len(m)/6`+" Coordinates:"+m

```

Input (Paste before the code):

```
g=[0,1,0,0,0,0,1,0,0,0,0,1,1,0,0,0,0,1,1,0,0,1,1,0,0,0,0,1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,1,1,0,0,0,1,0,0,0,0,1,1,0,0,0,1,0,0,0,0,0,0,1,1,0,1,0,0,0,0,0,0,1,1,0,1,0,0,0,0,0,0,0,0,0,0,0]

```

Thanks Calvin's Hobbies for suggested edits!
> 5 votes

# Answer
# C# - 548 523 522 511 503 476

*(under 500... yey)*

I'm sure there's **lots** of room for improvement.

The way I inputted the data was to initialize an array. I didn't include that array in the score (if you think this is cheating I can change the code, but it will add relatively much code because C# isn't great at parsing arrays)

```
using o=System.Console;using l=System.Collections.Generic.List<int[]>;class P{
static int[,] a ={{0,1,0,0,0,0,1,0,0,0},{0,1,1,0,0,0,0,1,1,0},{0,1,1,0,0,0,0,1,0,0},{0,1,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,1,0},{0,0,0,1,1,0,0,0,1,0},{0,0,0,1,1,0,0,0,1,0},{0,0,0,0,0,1,1,0,1,0},{0,0,0,0,0,1,1,0,1,0},{0,0,0,0,0,0,0,0,0,0}};
static int w=10,h=w,x=0,y;static l t=new l(),m=new l();static void f(int r,int c){if(a[r,c]==1){a[r,c]=0;if(r<h)f(c,r+1);if(r>0)f(c,r-1);if(c<w)f(c+1,r);if(c>0)f(c-1,r);t.Add(new[]{c,r});}}static void Main(){for(;++x<w;)for(y=0;++y<h;){if(a[x,y]==1)f(x,y);if(t.Count>m.Count)m=t.FindAll(r=>true);t.Clear();}o.Write("Size: "+m.Count+" Coordinates: ");m.ForEach(c=>o.Write("({0},{1}) ",c[0],c[1]));}}

```

Test it at http://ideone.com/UCVCPM

**Note: The current version doesn't work in ideone because it doesn't like `using l=System.Collections...`, so the ideone version is slightly outdated (and longer)**

## How it works

It basically checks if there is a `1`. If it finds one, it uses the Flood Fill algorithm to replace all the adjacent `1`'s with `0` and adds the replaced coordinates to a temporary list. Afterwards it compares the top list (`m`) to the temporary list (`t`) and sets `m` to `t` if `t`contains more elements.
> 3 votes

# Answer
# Mathematica - 180 bytes

This function takes a 2-dimensional array.

### Golfed

```
f@x_:=(c=MorphologicalComponents[x,CornerNeighbors->False];m=Last@SortBy[ComponentMeasurements[c,"Count"],Last];Print["Size: ",Last@m," Coordinates: ",Reverse/@Position[c,m[[1]]]])

```

### Pretty

```
f@x_ := (
   c = MorphologicalComponents[x, CornerNeighbors -> False];
   m = Last@SortBy[ComponentMeasurements[c, "Count"], Last];
   Print["Size: ", Last@m, " Coordinates: ", Reverse/@Position[c, m[[1]]]]
   );

```

### Example

```
{0,1,0,0,0,0,1,0,0,0,0,1,1,0,0,0,0,1,1,0,0,1,1,0,0,0,0,1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,1,1,0,0,0,1,0,0,0,0,1,1,0,0,0,1,0,0,0,0,0,0,1,1,0,1,0,0,0,0,0,0,1,1,0,1,0,0,0,0,0,0,0,0,0,0,0};
w=Partition[%,10];
f@w

```

> Size: 6 Coordinates: {{1,2},{2,2},{2,3},{3,2},{3,3},{4,2}}

The output is slightly anomalous. Mathematica starts indexing at 1 instead of 0, and uses `{}` to indicate position. Add 2 bytes (`-1`) if the positions need to be 0-indexed. Add a lot of bytes if they need to use `()` instead of `{}` :(

### Explanation

`f` is a function of `x`. It defines `c` as a transformation of `x`, where each (i,j) now equals an integer corresponding to which connected component it belongs to. It involves the main work:

```
MorphologicalComponents[w, CornerNeighbors -> False] // Colorize

```

Then `m` computes how many elements are in each component, sorts them by that number, and takes the last result (meaning, with the most elements). The last line prints the count, and the positions in `c` of the index contained in `m`.
> 3 votes

# Answer
# Haskell, 246

```
r=[0..9]
q=[(i,j)|i<-r,j<-r]
t v p@(i,j)|elem p v||notElem p q||g!!j!!i==0=v|1<2=foldr(\(k,l)v->t v(i+k,j+l))(p:v)$zip[-1,0,1,0][0,-1,0,1]
(?)=map
a=t[]?q;(b,c)=maximum$zip(length?a)a
main=putStrLn.unwords$["Size:",show b,"Coordinates:"]++show?c

```

## Input

Two dimension and paste before code as `g`, for example:

```
g = [[0, 1, 1, ......, 0], [......], ....]

```

## Ungolfed

```
field = [
 [0,1,0,0,0,0,1,0,0,0],
 [0,1,1,0,0,0,0,1,1,0],
 [0,1,1,0,0,0,0,1,0,0],
 [0,1,0,0,0,0,0,0,0,0],
 [0,0,0,0,0,0,0,0,1,0],
 [0,0,0,1,1,0,0,0,1,0],
 [0,0,0,1,1,0,0,0,1,0],
 [0,0,0,0,0,1,1,0,1,0],
 [0,0,0,0,0,1,1,0,1,0],
 [0,0,0,0,0,0,0,0,0,0]
 ]
range = [0..9]
positions = [(i, j) | i <- range, j <- range]
directions = zip [-1, 0, 1, 0] [0, -1, 0, 1]
traverse visited pos@(i, j)
  | pos `elem` visited || pos `notElem` positions || field!!j!!i == 0 = visited
  | otherwise = foldr folder (pos:visited) directions
  where folder = (\(di, dj) visited -> traverse visited (i + di, j + dj))
blocks = map (traverse []) positions
(maxCount, maxBlock) = maximum $ zip (map length blocks) blocks
main = putStrLn.unwords $ ["Size:", show maxCount, "Coordinates:"] ++ map show maxBlock

```
> 2 votes

# Answer
### C# 374byte function

This is a heavily modified version of my answer to Are you in the biggest room?. It takes a one-dimensional array of ints, and returns a string in the style required. It works by building up disjoint sets from the input (first loop), tallying the size of each set and finding the largest set (second loop) and then appending any cells in that set to an output string (third loop) which is then returned.

```
static string F(int[]g){int s=10,e=0,d=s*s,a=0,b=d+1;int[]t=new int[b],r=new int[b];t[d]=d;System.Func<int,int>T=null,k=v=>t[T(v)]=t[v]<d?a:d;T=v=>t[v]!=v?T(t[v]):v;for(;a<d;a++)if(g[a]>0){e=t[a]=a;if(a>s)k(a-s);if(a%s>0)k(a-1);}else t[a]=d;for(;a-->0;)e=r[e]<++r[b=T(a)]&&b<d?b:e;var p="Size: "+r[e]+" Coordinates:";for(;d-->1;)p+=T(d)==e?" ("+d%s+","+d/s+")":"";return p;}

```

Less golfed (and with test code):

```
class P
{
    static int[] z = {0,1,0,0,0,0,1,0,0,0,0,1,1,0,0,0,0,1,1,0,0,1,1,0,0,0,0,1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,1,1,0,0,0,1,0,0,0,0,1,1,0,0,0,1,0,0,0,0,0,0,1,1,0,1,0,0,0,0,0,0,1,1,0,1,0,0,0,0,0,0,0,0,0,0,0};

    static string F(int[]g)
    {
        int s=10,e=0,d=s*s,a=0,b=d+1;

        int[]t=new int[b],r=new int[b];
        t[d]=d;
        System.Func<int,int>T=null,k=v=>t[T(v)]=t[v]<d?a:d;
        T=v=>t[v]!=v?T(t[v]):v;

        for(;a<d;a++)
            if(g[a]>0)
            {
                e=t[a]=a;
                if(a>s)k(a-s);
                if(a%s>0)k(a-1);
            }
            else
                t[a]=d;
        for(;a-->0;)
            e=r[e]<++r[b=T(a)]&&b<d?b:e;

        var p="Size: "+r[e]+" Coordinates:";
        for(;d-->1;)
            p+=T(d)==e?" ("+d%s+","+d/s+")":"";

        return p;
    }

    static void Main()
    {
        System.Console.WriteLine(F(z));
    }
}

```
> 2 votes

# Answer
# JavaScript (EcmaScript 6) 183 ~~189~~

A function with array input and string return value. If real output is needed (not clear to me) add 7 bytes for 'alert()'.

```
W=(a,n=10,x=0)=>(F=p=>a[p]|0&&(a[p]=0,o+=' ('+p%n+','+(p/n|0)+')',1+F(p-n)+F(p+n)+F(p-(p%n>0))+F(p+((p+1)%n>0))),a.map((e,p)=>(t=F(p,o=''))>x&&(x=t,k=o)),'Size: '+x+' Coordinates:'+k)

```

**Test Output**

```
Size: 6 Coordinates: (1,0) (1,1) (1,2) (1,3) (2,2) (2,1)

```

**More readable**

```
W=(a,n=10,x=0)=>
(
  F=p=>
    a[p]|0&&(
      a[p]=0,o+=' ('+p%n+','+(p/n|0)+')',
      1+F(p-n)+F(p+n)+F(p-(p%n>0))+F(p+((p+1)%n>0)) // modulo takes care of not overflowing out of a row
    ),
  a.map((e,p)=>(t=F(p,o=''))>x&&(x=t,k=o)),
  'Size: '+x+' Coordinates:'+k
)

```

**Explanation**

Get a single dimension array and an optional parameter with the size of a row. The function works also with different array dimensions, even x!=y.

*Pseudo code:*

```
 For each element,
   try to fill.
   During the fill operation build a string with the coordiinates.
   Remember the longest fill and the corresponding string and
 output that at the end.

```
> 1 votes

# Answer
## **JavaScript, 273**

Function takes array and returns string. My first attempt was ~500 characters and did not use Flood Fill. This one does. I'm learning JavaScript so any suggestions would be appreciated.

This function loops through the input array and for each 1 found it starts there and changes all connected to 1s to 0 using the Fill function. While doing so it remembers the blob with the most 1s. The Fill function changes the current position to 0 and then calls itself on the position above, to the right, below, and to the left.

```
function G(m){var B="",b=0;for(var p=0;p<m.length;p++)if(m[p]){var T="",t=0;
Z(p);if(t>b){b=t;B=T;}}return"Size: "+b+" Coordinates:"+B;function Z(p){if(m[p])
{m[p]=0;t++;T+=" ("+p%10+","+Math.floor(p/10)+")";if(p>9)Z(p-10);if(p%10)Z(p-
1);if(p<90)Z(p+10);if(p%10!=9)Z(p+1);}}}

```

Test here: http://goo.gl/9Hz5OH

**Readable Code**

```
var map = [0, 1, 0, 0, 0, 0, 1, 0, 0, 0,
           ...
           0, 0, 0, 0, 0, 0, 0, 0, 0, 0];

function F(map) {

    var bestBlob = "", bestLen=0;
    for (var p = 0; p < map.length; p++)
        if (map[p]) {
            var thisBlob = "", thisLen=0;
            Fill(p);
            if (thisLen > bestLen){
                bestLen=thisLen ; bestBlob = thisBlob;
            }
        }
    return "Size: " + bestLen + " Coordinates:" + bestBlob;

    function Fill(p) {
        if (map[p]) {
            map[p] = 0; thisLen++;
            thisBlob += " (" + p % 10 + "," + Math.floor(p / 10) + ")";
            if (p > 9) Fill(p - 10);
            if (p % 10) Fill(p - 1);
            if (p < 90) Fill(p + 10);
            if (p % 10 != 9) Fill(p + 1);
        }
    }
}

```
> 1 votes

# Answer
# Scala, 420

Hi, my entry takes a 2d array as a `List[List[Int]]`, returns a `String`

```
val o=for{(r, y)<-w.zipWithIndex;(v,x)<-r.zipWithIndex;if(v == 1)}yield(x,y);val a=o.flatMap(c=>o.collect{case(x,y)if{(x==c._1+1||x==c._1-1)&&y==c._2^(y==c._2+1||y==c._2-1)&&x==c._1}=>c->(x,y)}).groupBy(_._1).map(n => (n._1->n._2.map(t=>t._2)));val b=a.values.flatMap(v=>v.map(c=>a(c)++v));val l=b.collect{case x if (x.length==b.map(_.length).max)=>x}.head;println(s\"Size: ${l.length} Coordinates: ${l.mkString(" ")}\")

```

## Explanation

Given a window as a `List[List[Int]]`, first we find each "1" and save the coordinates in a list. Next we turn that list into a `Map` of the coordinate of each "1" to a list the coordinates of every adjacent "1". Then use the adjacency map to transitively link the sub-blobs into blobs, and finally we return the largest blob (and ignoring duplicate blobs since order of the returned coordinates does not matter).

## More Readable

```
 val w = {
  List(//0,1,2,3,4,5,6,7,8,9
    List(0,1,0,0,0,0,1,0,0,0), //0
    List(0,1,1,0,0,0,0,1,1,0), //1
    List(0,1,1,0,0,0,0,1,0,0), //2
    List(0,1,0,0,0,0,0,0,0,0), //3
    List(0,0,0,0,0,0,0,0,1,0), //4
    List(0,0,0,1,1,0,0,0,1,0), //5
    List(0,0,0,1,1,0,0,0,1,0), //6
    List(0,0,0,0,0,1,1,0,1,0), //7
    List(0,0,0,0,0,1,1,0,1,0), //8
    List(0,0,0,0,0,0,0,0,0,0)) //9
}

case class Coord(x: Int, y: Int)

val ones: List[Coord] = for{
  (row, y)   <- w.zipWithIndex
  (value, x) <- row.zipWithIndex
  if (value == 1)
} yield Coord(x,y)

val adjacencyMap: Map[Coord, List[Coord]] = ones.flatMap(keyCoord => ones.collect{
case Coord(adjacentX, adjacentY) if {
    (adjacentX == keyCoord.x + 1 || adjacentX == keyCoord.x - 1) && adjacentY == keyCoord.y ^
    (adjacentY == keyCoord.y + 1 || adjacentY == keyCoord.y - 1) && adjacentX == keyCoord.x
  }  => keyCoord->Coord(adjacentX,adjacentY)
}).groupBy(_._1).map(n => (n._1->n._2.map(t=>t._2) ))

val blobs: Iterable[List[Coord]] = adjacencyMap.values.flatMap(v => v.map(coord => adjacencyMap(coord)++v))

val largestBlob: List[Coord] = blobs.collect{case x if (x.length == blobs.map(b=> b.length).max) => x}.head

println(s"""Size: ${largestBlob.length} Coordinates: ${largestBlob.collect{case Coord(x,y) => (x,y)}.mkString(" ")}""")

```

Criticism is very much appreciated.
> 1 votes

---
Tags: code-golf
---


title: The Golf (re)Sort

text:
# Question
Title: The Golf (re)Sort
# The Golf (re)Sort

*Everyone is sorting arrays these days, and so do we at our day jobs. But we like to go out golfing. When we do, we sure like to take our time. It is important to have a stress free experience.*

*Since we like golfing so much, we have decided to make a sorting algorithm that will let us stay away from the desk as much as possible. We decided to make **Golf (re)Sort**, a sorting algorithm that takes as time long as possible to complete. This way we can spend more time doing what we like the most, golfing.*

---

The task is easy: **Sort an array of integers using an algorithm that takes as long time, and has as high O-notation, as possible.**

## The rules:

* The algorithm must be deterministic. Thus you may not use randomness in the algorithm (so no bogosort)
* You may not use any un-productive operations or loops. Eg.: `sleep 2`, `for i<n; i++ {/*no-op*/}`, `Open("www.the_internet.com").download`. Every operation needs to bring you closer to the goal of a sorted list. An example would be to simply reverse the array for no other reason than reversing the array to increase the Ω-notation.

## Provide:

* Name of the language
* The code
* An explanation to the approach + Ω(Big-Omega)-notation (lower bound).

## Scoring:

Scoring will be done by looking at the Ω-runtime. The higher the better.

---

# Example:

Language: **Ruby**

Code:

```
a = [6,9,7,5,7,90,9,6,4,32,9,7,4,223]
sorted = []

while a.count > 0
    min = [Float::INFINITY, -1]
    a.each_with_index do |e,i|
        min = [e,i] if e < min[0]
    end
    sorted << min[0]
    a.delete_at(min[1])
end

puts sorted.to_s

```

This is a variation on selection sort which have runtime of **Ω(n^2)**. It is slow because it scans the array for the lowest value, then pushes that to the result array. It then deletes the value from the original array and starts over.

# Answer
# Python

```
def ackermann(m, n):
    if m == 0:
        return n + 1
    if n == 0:
        return ackermann(m - 1, 1)
    return ackermann(m - 1, ackermann(m, n - 1))

def sort(lst):
    newlst = []
    while len(lst) > 0:
        a, i = min([(ackermann(n, n), i) for i, n in enumerate(lst)])
        newlst.append(lst[i])
        del lst[i]
    return newlst

```

Uses Ackermann function to slow things down. That may qualify as unproductive...

Use example:

```
print sort([3, 1, 2, 3, 0]) # --> [0, 1, 2, 3, 3]

```

It actually works quite well for numbers between 0 and 3. (Note that it's destructive and only works for non-negative integers.)

Runtime - I'm not quite sure.
> 1 votes

# Answer
## k4 (100)

```
  {{if[y<z;.z.s[x]'[y,m+1;(m:_(y+z)%2),z];if[(x m)>x z;@[x;z,m;:;x m,z]];.z.s[x;y;z-1]]}[x;0](#. x)-1}

```

This is a fairly straightforward (i.e. not particularly golfed) implementation of slowsort.

Here's a sample run, with timing information in milliseconds (the `\t` instruction):

```
  s:{{if[y<z;.z.s[x]'[y,m+1;(m:_(y+z)%2),z];if[(x m)>x z;@[x;z,m;:;x m,z]];.z.s[x;y;z-1]]}[x;0](#. x)-1}
  l:100?1000
  \t s`l
4270

```

The paper (*v.s.*) claims that the last few paragraphs of section 5 contain a proof of the running time of the algo, but I can't make heads or tails of it; all I know is that 4.2 seconds to sort 100 ints is *pretty slow*.

(I should also note that this implementation is an in-place sort, as given in the paper, which is why the list to sort is passed by name, rather than by value. This is rather strongly contrary to the functional programming principles of k4/q, but it was easier than figuring out a proper functional version.)
> 1 votes

# Answer
## Python

This one isn't golfed, because I'm not much of a code golfer yet.

```
def sorted(l):
    for i in range(1, len(l)):
        if l[i] < l[i-1]:
            return False
    return True

class T:
    def __init__(self,l1,l2):
        self.l1 = l1
        self.l2 = l2
        self.children = []

    def build(self):
        if len(self.l2) == 0:
            return
        else:
            for i in range(0, len(self.l2)):
                nl1 = self.l1[:]
                nl2 = self.l2[:]
                nl1.append(self.l2[i])
                nl2.pop(i)
                child = T(nl1, nl2)
                child.build()
                self.children.append(child)

    def find_sorted(self):
        if len(self.l2) == 0:
            if sorted(self.l1):
                return self.l1
            return None
        result = None
        for child in self.children:
            if child.find_sorted() is not None:
                result = child.find_sorted()
        return result

def sort(l):
    tree = T([],l)
    tree.build()
    return tree.find_sorted()

```

Been a while since I took any classes so I'm trying to think of how to word the complexity. I know the number of nodes in the tree can be calculated with:

```
def numberOfNodes(n):
    if n==0:
        return 1
    return 1 + n * numberOfNodes(n - 1)

```

It builds this entire tree and searches through every node. So for a list size grows very fast:

```
0       1
1       2
2       5
3       16
4       65
5       326
6       1957
7       13700
8       109601
9       986410
10      9864101

```

If searching every node is cheating I can change that.

A list of 9 elements took about 6 seconds, and a list of 10 elements ran out of memory (used at least 1.9 GB of ram before it chickened out 25 seconds in).
> 1 votes

# Answer
## Python, Omega(n^(n+2))

```
def sort(a):
    for i in xrange(len(a)**len(a)):
        b = list(a)
        for j in range(len(a)):
            k = i / len(a)**j % len(a)
            b[0], b[k] = b[k], b[0]
        if all(b[x] <= b[y] for x in range(len(a)) for y in range(x, len(a))):
            return b

```

Tries all possible orderings (and then some), returning only if the array is sorted. Uses Omega(n^2) to test if it's sorted, just to add insult to injury.
> 1 votes

---
Tags: sorting
---


title: ASCII Waterworks

text:
# Question
Title: ASCII Waterworks
# Intro

Consider a grid of the characters `f A\/` such as

```
f  f  f
      A
   A / \
\ /     A
    A \/
   /
 \/

```

where:

* `f` represents a faucet that pours a stream of water downward
* `A` bifurcates the stream of water above so exactly half goes left and exactly half goes right
* `\` shifts the stream of water above to the right by one unit
* `/` shifts the stream of water above to the left by one unit
* the combinations `\/` creates a trough with infinite capacity that collects the water streams above it
* `[space]` is empty space than the water can move through

From this we can imagine the path the water (`*`) would take as it comes out of the faucets and falls either into the troughs or out of the grid area:

```
f  f  f    <-- first second and third faucets
*  * *A*
* *A*/ \*
\*/ *  *A  <-- a '*' is not drawn to the right of this A because it would be out of the 9×7 bounds
 * *A*\/   <-- upper trough
 **/ *
 \/  *     <-- lower trough

```

Assuming the 3 faucets output the same amount of water one at a time we can see that

* All of the first faucet's water goes to the lower trough.
* One half of the second faucet's water goes to the lower trough and the other half is split between the lower trough and falling off the grid.
* One quarter of the third faucet's water goes to the lower trough, one quarter falls off the bottom of the grid, one quarter goes into the upper trough, and one quarter falls off the grid to the right.

From this we can tell that `(1 + 3/4 + 1/4 + 1/4) / 3 = 75%` of the water is caught by the troughs and `(1/4 + 1/4 + 1/4) / 3 = 25%` falls off the grid.

# Challenges

You may complete any or all of these challenges relating to this ASCII water flow setup. They are all code-golf, the shortest answer for each challenge is the winner. The accepted answer will be the person who completes the most challenges, with total code length as tie-breaker.

**Challenge 1**
Write a program that outputs the fraction of water that flows into troughs for a given grid. The output of the example above would simply be `0.75`.

**Challenge 2**
Write a program that, given a grid, draws the `*`'s in the places water flows as I've done above. You should not overwrite anything besides space characters and the grid should not change size. So for something like

```
 f
/A

```

nothing needs to be done since, although water does flow on either side of the A, it can't be drawn to the left without removing the `/` and it can't be drawn to the right without making the 2×2 grid bigger.

**Challenge 3 (Updated)**
Write a program that takes in two non-negative integers, the total T and the amount to keep K (T \>= K). Generate and draw a grid with exactly one `f` such that when that faucet pours out T units of water, exactly K will flow into troughs. If it is impossible to do this in a finite grid for a particular (T, K) pair then output 'Impossible'.

# Clarifications (apply to all challenges)

* Input can be via stdin, or a file, or even a function call on the string representation of the grid. Just make it obvious how to run different inputs.
* Output must go to stdout.
* `\A` and `A/` and `AA` are also troughs as you'd expect.
* A w by h grid will always be a well formatted rectangle of w\*h characters not counting newlines. There will be no missing trailing spaces and no occurrences of `*`.
* The grid dimensions can be as small as 1×1 and arbitrarily large. (Arbitrarily large within reason, int.maxValue or the like is an acceptable limit. Same goes for T and K.)
* A stream above an `f` flows right through it.
* The faucets can be anywhere, not just on the top row.
* `A` always divides the amount of water poured on it exactly in half.

*Note:* Things like `/A` and `//` are perfectly valid. The water *does* freely flow between the characters (though for challenge 2 there's not enough room to draw it).

So, in the setup

```
ff

/A

```

The left `f` stream pours down, hits the `/` and shifts left. The right `f` stream pours down, hits the `A`, half goes right and half goes left between the `A` and the `/`.

e.g.

```
 ff
 **
*/A*
** *
** *

```

# Answer
## All Challenges C# 690bytes (416bytes + 274bytes)

### Challenges 1&2 C# ~~579~~ ~~446~~ 416bytes

This is a complete program which should do Challenges 1 & 2, just about. It reads lines of input from stdin until it receives an empty line. It prints out the result for Challenge 2, and then the result for Challenge 1. Uses the .NET decimal class to hopefully avoid any rounding errors.

```
using C=System.Console;class P{static void Main(){decimal u,t=0,f=0;string c,z="";for(decimal[]n=null,o;(c=C.ReadLine())!="";z+='\n'){int s=c.Length,i=s,e;o=n;n=new decimal[s];for(o=o??n;i-->0;n[i]+=(e&2)*u/2){e=c[i]%13;u=o[i]/(e<1?2:1);if(e%8<1)if(i>0)if(c[i-1]%7<3)t+=u;else n[i-1]+=u;if(e<2)if(i<s-1)if(c[i+1]%2>0)t+=u;else n[i+1]+=u;if(e>9){u++;f++;}}for(;++i<s;)z+=c[i]<33&n[i]>0?'*':c[i];}C.WriteLine(z+t/f);}}

```

Less golfed:

```
using C=System.Console;
class P
{
    static void Main()
    {
        decimal u,t=0,f=0;
        string c,z="";

        for(decimal[]n=null,o;(c=C.ReadLine())!="";z+='\n')
        {
            int s=c.Length,i=s,e;
            o=n;
            n=new decimal[s];
            for(o=o??n;i-->0;n[i]+=(e&2)*u/2)
            {
                e=c[i]%13;
                u=o[i]/(e<1?2:1);

                if(e%8<1)
                    if(i>0)
                        if(c[i-1]%7<3)t+=u;
                        else n[i-1]+=u;
                if(e<2)
                    if(i<s-1)
                        if(c[i+1]%2>0)t+=u;
                        else n[i+1]+=u;
                if(e>9)
                {
                    u++;
                    f++;
                }
            }
            for(;++i<s;)
                z+=c[i]<33&n[i]>0?'*':c[i];
        }

        C.WriteLine(z+t/f);
    }
}

```

Test run (with a lack of trailing spaces which I promise are there):

```
f  f  f
      A
   A / \
\ /     A
    A \/
   /
 \/

f  f  f
*  * *A*
* *A*/ \*
\*/ *  *A
 * *A*\/
 **/ *
 \/  *
0.75

```

### Challenge 3 C# 274bytes

This is a complete program which should complete Challenge 3. I a managed to save 6bytes by writing my own integer parser to read the input rather than `Split`ing a `ReadLine` and using `long.Parse`;

```
using C=System.Console;class P{static void Main(){long t=-1,f=t,k;for(;f<0;)for(f=t,t=0;(k=C.Read())>47;)t=t*10+k-48;var r="Impossible\n";for(k=t;k<t*f;)k*=2;if(f<1||(k/f)*f==k)for(r=" f \n";t>0&t<f;t-=(t/f)*f)r+=((t*=2)<f?" ":"A")+"A \n/ /\n";C.Write(r+(t<f?"":"AAA\n"));}}

```

Less golfed:

```
using C=System.Console;
class P
{
    static void Main()
    {
        long t=-1,f=t,k;
        for(;f<0;)
            for(f=t,t=0;(k=C.Read())>47;)
                t=t*10+k-48;

        var r="Impossible\n";
        for(k=t;k<t*f;)
            k*=2;
        if(f<1||(k/f)*f==k)
            for(r=" f \n";t>0&t<f;t-=(t/f)*f)
                r+=((t*=2)<f?" ":"A")+"A \n/ /\n";
        C.Write(r+(t<f?"":"AAA\n"));
    }
}

```

Test run (again with a lack of trailing spaces which I promise are there):

```
32 17
 f
AA
/ /
 A
/ /
 A
/ /
 A
/ /
AA
/ /

```
> 3 votes

# Answer
First of all, I have a question regarding the challenge. Since I do not have enough reputation to comment on the question, I'm writing it here:

* What is the behavior of `/A` (water flowing on A), `//` (water flowing on the right side) and variations of this principle? Does the water flow to the first "free spot" on the side or does is flow "below" its neighbour?

---

Just a simple try, it can be waaaaay simplified (which I will do later by editing this post).

**Edit:** Second version, a little bit smaller. I went for a different approach: instead of looking for each cell to check what's comming from the top and sides, I start from the faucets and "flow" downwards with recursion.

## Javascript, 226 bytes (Challenge 1)

```
function f(c){function h(b,a,d,e){b<c.length&&0<=a&&a<c[0].length&&("\\"==c[b][a]?"/"==e||"A"==e?g+=d:h(b,a+1,d,"\\"):"/"==c[b][a]?"\\"==e||"A"==e?g+=d:h(b,a-1,d,"/"):"A"==c[b][a]?"A"==e||"\\"==e||"/"==e?g+=d:(h(b,a-1,d/2,"A"),h(b,a+1,d/2,"A")):h(b+1,a,d,c[b][a]))}for(var g=0,m=0,k=0;k<c.length;k++)for(var l=0;l<c[k].length;l++)"f"==c[k][l]&&(h(k+1,l,1),m++);alert(g/m)};

```

## Javascript, 204 bytes (Challenge 2)

```
function f(c){function e(b,a,d){b<c.length&&0<=a&&a<c[0].length&&("\\"==c[b][a]?"/"!=d&&"A"!=d&&e(b,a+1,"\\"):"/"==c[b][a]?"\\"!=d&&"A"!=d&&e(b,a-1,"/"):"A"==c[b][a]?"A"!=d&&"\\"!=d&&"/"!=d&&(e(b,a-1,"A"),e(b,a+1,"A")):(" "==c[b][a]&&(c[b][a]="*"),e(b+1,a,c[b][a])))}for(var g=0;g<c.length;g++)for(var h=0;h<c[g].length;h++)"f"==c[g][h]&&e(g+1,h)};

```

## Javascript, 238 bytes (Challenge 1 + 2)

```
function f(c){function h(b,a,d,e){b<c.length&&0<=a&&a<c[0].length&&("\\"==c[b][a]?"/"==e||"A"==e?g+=d:h(b,a+1,d,"\\"):"/"==c[b][a]?"\\"==e||"A"==e?g+=d:h(b,a-1,d,"/"):"A"==c[b][a]?"A"==e||"\\"==e||"/"==e?g+=d:(h(b,a-1,d/2,"A"),h(b,a+1,d/2,"A")):(" "==c[b][a]&&(c[b][a]="*"),h(b+1,a,d,c[b][a])))}for(var g=0,m=0,k=0;k<c.length;k++)for(var l=0;l<c[k].length;l++)"f"==c[k][l]&&(h(k+1,l,1),m++);alert(g/m)};

```

---

**How to use**

Provide a two dimensionnal representation ofthe map. Here is the example provided in the question:

```
var input = [["f"," "," ","f"," "," ","f"," "," "],[" "," "," "," "," "," ","A"," "," "],[" "," "," ","A"," ","/"," ","\\"," "],["\\"," ","/"," "," "," "," "," ","A"],[" "," "," "," ","A"," ","\\","/"," "],[" "," "," ","/"," "," "," "," "," "],[" ","\\","/"," "," "," "," "," "," "]];
f(input);

```

**Output**

Challenge 1: It will simply create a dialog box (alert) with the result (0.75 for the example above).

Challenge 2: It will directly modify the map. *Should I print it? If so, is console.log is accepted? as a valid output?*

Challenge 1+2: Both of above combined, *obviously*...
> 3 votes

# Answer
# Python 3, 186 bytes (Challenge 3)

I took the idea for the grid from VisualMelon's answer. The function should print a valid grid to stdout for arbitrarily large T and K, provided it is possible (finite size grid) of course.

```
from fractions import*
def c(T,K):
 p=print;g=gcd(T,K);K//=g;T//=g
 if T&(T-1):p('Impossible')
 else:
  p(' f ')
  while T-1:
   T//=2;p('A/'[K<T]+'A \n///')
   if K>=T:K-=T
  p('AAA'*K)

```

---

## How to use

Call the `c` function with the total amount and amount to keep as arguments.

```
>>> c(24, 9)
 f
/A
///
AA
///
AA
///

>>> c(6, 2)
Impossible

```
> 2 votes

---
Tags: code-golf, ascii-art
---


title: Syllabify English words - kind of

text:
# Question
Title: Syllabify English words - kind of
You're tasked with writing a program that syllabifies words in a string of text, by separating them with a hyphen. That would be a lot of work, so you want to skip some parts, mainly because you don't want to have a table of the pronunciations required for perfect algorithm. You also want to make it as short (and thus unreadable and unmaintainable) as possible as a revenge for being given this assignment.

You have two choices:

* Write a program that takes the string from STDIN and outputs the result to STDOUT.
* Write a function that takes the string as a single parameter, and returns the result.

## Specification

* In this case, string means any string-like construct in your language of choice (byte arrays, character arrays, strings...).
* Vowels are `a, e, i, o, u`
* The string given has `1 <= n <= 10` words, where each has a length between `1 - 30` characters, inclusive.. Your output should be those words hyphenated.
* All letters are lowercase and words are always separated with spaces. Thus, the input consists of characters `[a-z ]`
* Apply rules in order of importance.
* When a word is divided, start again with the right half of the word.

**Rules for syllabification**, in order of importance

Two consecutive same vowels count as one (ie. `feet` has only one vowel, but `beat` and `finding` have two). Every syllable has exactly one vowel, thus there is one syllable for each vowel.

1. If the **whole word** has only four letters, return it unchanged. (skip this for the rest of the word)
2. If the word has only one vowel, return the word unchanged.
3. If the word has two consecutive vowels, divide between them (ie. `diaspora` -\> `di-as-po-ra`)
4. When two or more consonants come between two vowels (same or different), divide after the first consonant (ie. `sis-ter`) unless the consonant part is `ck`, in which case divide the word after it. (ie. `nickel` -\> `nick-el`)
5. When a `y` comes between two vowels, divide the word after it (e.g. `paying` -\> `pay-ing`).
6. When one consonant comes between two vowels (same or different), divide before the consonant (ie. `dra-gon`)
7. Return the word unchanged if no division could be done.

I chose these rules, because they can be applied recursively without problems and require no pronunciation tables. Thus, they are not accurate, and for example rule #5 is often not correct. In general case though, it is.

## Example

```
In:  hello world
Out: hel-lo world

In:  have a nice day
Out: have a nice day

In:  pour some nickel and xenon there
Out: pour some nick-el and xe-non the-re

```

# Answer
> 6 votes
# Ruby, 144 bytes

If we're going for unmantainable, how about a single giant regex?

```
puts gets.split.map {|w| w.scan(/(^.{4}$|[^aeiou]*([aeiou])\2?((?=[^aeiouy]?[aeiou])|ck|[^aeiou]((?=.*[aeiou])|.*$)|$))/).map(&:first)*'-'}*' '

```

some output:

```
echo "hello world" | ruby syllable.rb
hel-lo world

echo "have a nice day" | ruby syllable.rb
have a nice day

echo "pour some nickel and xenon in there" | ruby syllable.rb
pour some nick-el and xe-non in the-re

echo "diaspora dragon paying sister hemlock happy quicksilver" | ruby syllable.rb
di-as-po-ra dra-gon pay-ing sis-ter hem-lock happy qu-ick-sil-ver

```

# Answer
> 8 votes
# Lua, 292

Lua might not have been the best language to do this in, but it works. It pretty much flows like the question asked. The rules are mainly in order with some optimizations: #2 is skipped (it isn't needed unless there is a one vowel word with "ck" at the beginning), and the ck and y rules are gone through before the rest of #4 and #6, which are combined. Since some vowels in the word need to be captured twice (after one hyphen and before another), that search is performed twice.

```
i=io.read()v="([aeiou])"for s in i:gfind("%l+ ?")do
if s:len()~=4 then
s=s:gsub(v..v,function(x,y)if x==y then return x..y;end;return x.."-"..y;end)s=s:gsub("ck"..v,"ck-%1")s=s:gsub(v.."y"..v,"%1y-%2")for b=1,2 do
s=s:gsub(v.."([^aeiou\-]?)([^aeiou\-]+)"..v,"%1%2-%3%4")end
end
io.write(s)end

```

## Ungolfed

```
function checkEquals(x,y)
    if x==y then
        return x..y
    end
    return x.."-"..y
end
i=io.read()
v="([aeiou])"
for s in i:gfind("%l+ ?") do
    if s:len()~=4 then
        s=s:gsub(v..v,checkEquals)
        s=s:gsub("ck"..v,"ck-%1")
        s=s:gsub(v.."y"..v,"%1y-%2")
        for b=1,2 do
            s=s:gsub(v.."([^aeiou\-]?)([^aeiou\-]+)"..v,"%1%2-%3%4")
        end
    end
    io.write(s)
end

```

Test it here: http://ideone.com/g57TzA

# Answer
> 4 votes
# Bash+coreultils, 173 bytes

I think I have all the latest rule changes:

```
v=aeiou
r="[$v])/\1-\2/g"
s=s/\([$v]
e="$s[^$v-])([^$v-]+$r
"
tr \  \\n|sed -r "/^([a-z]{4}|[^$v]*[$v][^$v]*)$/bx
$s)($r
${s}ck)($r
$e$e${s}y)($r
$s)([^$v-]$r
:x"|tr \\n \

```

Note the last character of the last line is a  (space).

I think this sufficiently satisfies *"unreadable and unmaintainable"* ;-)

Takes input from STDIN.

Mostly straight regex substitution. The first line of the `sed` expression matches for rules 1 and 2, then simply jumps to the `:x` label at the end of the expression.

The `tr`s at the start and end of the pipeline make the words newline-separated, so they are easier for `sed` to deal with. I was hoping to do and all `sed` answer, but this way is simpler and easier.

### Example:

```
$ ./sylabify.sh <<< "diaspora nickel sister dragon hello world have a nice day pour some nickel and xenon there paying tricks quicksilver"
di-as-po-ra nick-el sis-ter dra-gon hel-lo world have a nice day pour some nick-el and xe-non the-re pay-ing tricks qu-ic-ksil-ver $

```

---
Tags: code-golf
---