title: Chemical sentences! Decrypting

text:
# Question
Title: Chemical sentences! Decrypting
# Background

You are sitting in chemistry class and your friend keep sending you these strange letters. It is your job to decrypt the messages into words.

*This is the inverse of this challenge.*

# The Challenge

**Input**: A list or a string of integers from 1 to 118.

**Output**: The words for each chemical element if possible. Otherwise return False, throw an error, or blank. Note in your program 0 must return a whitespace or newline. Ignore all integers not in range.

**Test cases** Input 1:

```
9 53 75

```

Output 1:

```
fire

```

Input 2:

```
91 120 91

```

Output 2:

```
papa

```

Input 3:

```
9 53 75 0 53 16 0 9 92 7

```

Output 3:

```
fire is fun

```

**Note**: Again no built in functions for generating the periodic system or external libaries. Standard loopholes are not allowed.

# Scoring

Submissions will be scored in **bytes**. I recommend this website to keep track of your byte count, though you can use any counter you like.

This is , so the lowest score wins!

# Answer
# Pyth, 264 bytes

```
s@L+" "-R0+c"h0helibeb0c0n0o0f0nenamgalsip0s0clark0casctiv0crmnfeconicuzngageassebrkrrbsry0zrnbmotcrurhpdagcdinsnsbtei0xecsbalaceprndpmsmeugdtbdyhoertmybluhftaw0reosirptauhgtlpbbipoatrnfrraacthpau0nppuamcmbkcfesfmmdnolrrfdbsgbhhsmtdsrgcn"2c"uutfl0uuplv0uusuuo"3rz7

```
> 4 votes

# Answer
# Par, 261 bytes

```
` 0h0helibeb0c0n0o0f0nenamgalsip0s0clark0casctiv0crmnfeconicuzngageassebrkrrbsry0zrnbmotcrurhpdagcdinsnsbtei0xecsbalaceprndpmsmeugdtbdyhoertmybluhftaw0reosirptauhgtlpbbipoatrnfrraacthpau0nppuamcmbkcfesfmmdnolrrfdbsgbhhsmtdsrgcn`2%`uutfl0uuplv0uusuuo`3%+l✶´gΣ'0-

```

One byte is used per character, even `Σ`, since a specialized encoding is used. See here.

Input is Lisp-style, e.g. `(9 53 75 0 53 16 0 9 92 7)`

```
` 0h0hel...n`  ## Elements until Uut
2%             ## Split into pieces of size 2
`uutfl0u...o`  ## Elements from Uut
3%             ## Split into pieces of size 3
+              ## Combine into list of elements
l✶             ## Read array of numbers
´g             ## Find the element at each index
Σ              ## Concatenate
'0-            ## Remove all 0's

```
> 2 votes

# Answer
# Python 2.x, 295 bytes

Golfed code:

```
import re;print''.join([re.findall('[A-Z ][a-z]*',' HHeLiBeBCNOFNeNaMgAlSiPSClArKCaScTiVCrMnFeCoNiCuZnGaGeAsSeBrKrRbSrYZrNbMoTcRuRhPdAgCdInSnSbTeIXeCsBaLaCePrNdPmSmEuGdTbDyHoErTmYbLuHfTaWReOsIrPtAuHgTlPbBiPoAtRnFrRaAcThPaUNpPuAmCmBkCfEsFmMdNoLrRfDbSgBhHsMtDsRgCnUutFlUupLvUusUuo')[e]for e in i])

```

NB: to shave 8 bytes, output for this version is in mixed caps (doesn't break any rules), missing the `.lower()` ending

---

# ~~387 bytes~~

Golfed code:

```
print''.join([' ,h,he,li,be,b,c,n,o,f,ne,na,mg,al,si,p,s,cl,ar,k,ca,sc,ti,v,cr,mn,fe,co,ni,cu,zn,ga,ge,as,se,br,kr,rb,sr,y,zr,nb,mo,tc,ru,rh,pd,ag,cd,in,sn,sb,te,i,xe,cs,ba,la,ce,pr,nd,pm,sm,eu,gd,tb,dy,ho,er,tm,yb,lu,hf,ta,w,re,os,ir,pt,au,hg,tl,pb,bi,po,at,rn,fr,ra,ac,th,pa,u,np,pu,am,cm,bk,cf,es,fm,md,no,lr,rf,db,sg,bh,hs,mt,ds,rg,cn,uut,fl,uup,lv,uus,uuo'.split(',')[e]for e in i])

```

---

> Input: **A list** or a string **of integers** from 1 to 118.

Usage: `i=[9,53,75,0,53,16,0,9,92,7]`

> Output: The words for each chemical element if possible. Otherwise return False, **throw an error**, or blank. Note in your program 0 must return a whitespace or newline. Ignore all integers not in range.

PS: used 2.x for the `print` statement without parenthesis
> 2 votes

# Answer
# JavaScript (ES6), ~~347~~ 279 bytes

```
l=>l.map(n=>" HHeLiBeBCNOFNeNaMgAlSiPSClArKCaScTiVCrMnFeCoNiCuZnGaGeAsSeBrKrRbSrYZrNbMoTcRuRhPdAgCdInSnSbTeIXeCsBaLaCePrNdPmSmEuGdTbDyHoErTmYbLuHfTaWReOsIrPtAuHgTlPbBiPoAtRnFrRaAcThPaUNpPuAmCmBkCfEsFmMdNoLrRfDbSgBhHsMtDsRgCnUutFlUupLvUusUuo".match(/[ A-Z][a-z]*/g)[n]||"").join``

```

## Explanation

Uses @CSᵠ's idea of seperating the element names by capital letters. Converting the output to all upper or lower case would add 14 bytes.

```
l=>
  l.map(n=>                   // iterate through each number

    " HHeLiBeBCNOFNeNaMgAlSiPSClArKCaScTiVCrMnFeCoNiCuZnGaGeAsSeBrKrRbSrYZrNbMoTcRuRhPdAgCdInSnSbTeIXeCsBaLaCePrNdPmSmEuGdTbDyHoErTmYbLuHfTaWReOsIrPtAuHgTlPbBiPoAtRnFrRaAcThPaUNpPuAmCmBkCfEsFmMdNoLrRfDbSgBhHsMtDsRgCnUutFlUupLvUusUuo"
      .match(/[ A-Z][a-z]*/g) // split the elements by the first letter being upper-case

        [n]                   // add the element name to the output
          ||""                // add nothing if the number was out of range
  ).join``                    // return the output as a string

```

## Test

```
<input type="text" id="input" value="9 53 75 0 53 16 0 9 92 7" /><button onclick='result.innerHTML=(

l=>l.map(n=>" HHeLiBeBCNOFNeNaMgAlSiPSClArKCaScTiVCrMnFeCoNiCuZnGaGeAsSeBrKrRbSrYZrNbMoTcRuRhPdAgCdInSnSbTeIXeCsBaLaCePrNdPmSmEuGdTbDyHoErTmYbLuHfTaWReOsIrPtAuHgTlPbBiPoAtRnFrRaAcThPaUNpPuAmCmBkCfEsFmMdNoLrRfDbSgBhHsMtDsRgCnUutFlUupLvUusUuo".match(/[ A-Z][a-z]*/g)[n]||"").join``

)(input.value.split(" "))'>Go</button><pre id="result"></pre>
```
> 2 votes

# Answer
# ES6, 396 bytes

A very trivial approach:

```
var C=c=>c.map(a=>(" .h.he.li.be.b.c.n.o.f.ne.na.mg.al.si.p.s.cl.ar.k.ca.sc.ti.v.cr.mn.fe.co.ni.cu.zn.ga.ge.as.se.br.kr.rb.sr.y.zr.nb.mo.tc.ru.rh.pd.ag.cd.in.sn.sb.te.i.xe.cs.ba.la.ce.pr.nd.pm.sm.eu.gd.tb.dy.ho.er.tm.yb.lu.hf.ta.w.re.os.ir.pt.au.hg.tl.pb.bi.po.at.rn.fr.ra.ac.th.pa.u.np.pu.am.cm.bk.cf.es.fm.md.no.lr.rf.db.sg.bh.hs.mt.ds.rg.cn.uut.fl.uup.lv.uus.uuo").split(".")[a]||"").join("");

```

Test it
> 1 votes

# Answer
# Java, 470 bytes

```
interface B{static void main(String[]a){for(int i=0;i<a.length;i++)System.out.print(" ,h,he,li,be,b,c,n,o,f,ne,na,mg,al,si,p,s,cl,ar,k,ca,sc,ti,v,cr,mn,fe,co,ni,cu,zn,ga,ge,as,se,br,kr,rb,sr,y,zr,nb,mo,tc,ru,rh,pd,ag,cd,in,sn,sb,te,i,xe,cs,ba,la,ce,pr,nd,pm,sm,eu,gd,tb,dy,ho,er,tm,yb,lu,hf,ta,w,re,os,ir,pt,au,hg,tl,pb,bi,po,at,rn,fr,ra,ac,th,pa,u,np,pu,am,cm,bk,cf,es,fm,md,no,lr,rf,db,sg,bh,hs,mt,ds,rg,cn,uut,fl,uup,lv,uus,uuo".split(",")[Integer.parseInt(a[i])]);}}
```

Accepts input as command line arguments. Uses an interface declaration to shorten class/main declaration. It will *definitely* error for invalid input. Because Java.
> 1 votes

# Answer
# Ruby, 282

```
->a{a.each{|n|" HHeLiBeBCNOFNeNaMgAlSiPSClArKCaScTiVCrMnFeCoNiCuZnGaGeAsSeBrKrRbSrYZrNbMoTcRuRhPdAgCdInSnSbTeIXeCsBaLaCePrNdPmSmEuGdTbDyHoErTmYbLuHfTaWReOsIrPtAuHgTlPbBiPoAtRnFrRaAcThPaUNpPuAmCmBkCfEsFmMdNoLrRfDbSgBhHsMtDsRgCnUutFlUupLvUusUuo".bytes{|j|n-=1-j/96;n==-1&&$><<j.chr}}}

```

**Ungolfed in test program**

Each number in turn is assigned to `n`. We run through the magic string bytewise, decreasing `n` unless the ASCII code is more than 96. When `n` is -1 we print a byte from the magic string. As `n` remains the same until all characters for that element are printed, all characters for that element are printed. Out of range numbers are simply ignored.

```
f=->a{
  a.each{|n|
    " HHeLiBeBCNOFNeNaMgAlSiPSClArKCaScTiVCrMnFeCoNiCuZnGaGeAsSeBrKrRbSrYZrNbMoTcRuRhPdAgCdInSnSbTeIXeCsBaLaCePrNdPmSmEuGdTbDyHoErTmYbLuHfTaWReOsIrPtAuHgTlPbBiPoAtRnFrRaAcThPaUNpPuAmCmBkCfEsFmMdNoLrRfDbSgBhHsMtDsRgCnUutFlUupLvUusUuo".
    bytes{|j|n-=1-j/96;n==-1&&print(j.chr)}
  }
}

f[[59,8,24,95,49,0,15,92,40,99,0,95,60,0,27,4,0,27,53,9]]

```

**Output**

```
PrOCrAmIn PUZrEs AmNd CoBe CoIF

```

Mixed case. All lowercase would cost an extra 9. All uppercase would cost an extra 7.
> 1 votes

# Answer
# JavaScript, ~~275~~ ~~273~~ 272 bytes

```
a=>a.map(b=>" HHeLiBeBCNOFNeNaMgAlSiPSClArKaCaScTiVCrMnFeCoNiCuZnGaGeAsSeBrKrRbSrYZrNbMoTcRuRhPdAgCdInSnSbTeIXeCsBaLaCePrNdPmSmEuGdTbDyHoErTmYbLuHfTaWReOsIrPtAuHgTlPbBiPoAtRnFrRaAcThPaUNpPuAmCmBkCfEsFmMdNoLrRfDbSgBhHsMtDsRgCnUutFlUupLvUusUuo".split(/(?=[A-Z])/)[b]).join``

```

You can try it here : JSFiddle
> 1 votes

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


title: What is that angle?

text:
# Question
Title: What is that angle?
The goal of this challenge is to determine the angle of a line in a image.

Rules on the image:

* The image background will be white (`#FFFFFF`)
* The stroke of the line will be black (`#000000`)
* The line will NOT be anti-aliased
* The image will be 100x100 pixels
* The line will start at the center of the image
* The line will start pointing down (6-OClock)
* The line will be 50 pixels long
* The angle of the line will be measured going counterclockwise from the starting position
* The image codec will be either `.jpg` or `.png`

Input format will be a file name passed by the command line arg, script input, or function arg. Output format is simple - just output the number of degrees (e.g. `90`).

Answers can be ±1 degree of the stated measure. Here are a few example images:

A reference image at 45 degrees with gray background

0 degrees

45 degrees

50 degrees

130 degrees

230 degrees

324 degrees

Here is the code used to create the images (this is coded with Processing):

```
int deg = 45;

int centX = width/2, centY = height/2;

background(255);
noSmooth();
line(centX,
     centY,
     centX + sin(radians(deg))*50,
     centY + cos(radians(deg))*50);

saveFrame("line-"+deg+".png");// image codec can be changed here. use '.png' or '.jpg'

```

# Answer
# Pyth - ~~28~~ 26 bytes

Uses same sort of brute force strategy as the js answer.

```
f!@F+]'zm+50s*48.t.tT7d_U2

```

Takes input as filename from stdin.

```
f                     Filters from 1 till predicate is matched
 !                    Boolean not so that only pixel with zero value matched
  @F+]                Folds by indexing to get pixel value
   'z                 Reads image filename input
   m         _U2      Maps over both trig ratios
    +50               Adds 50 to pixel value
     *48              Multiplies pixel value by 48
      .t    d         Takes trig ratio with appropriate option
        .t 7          Degrees to radians
          T           Filter var

```
> 7 votes

# Answer
# JavaScript (ES6), 225 ~~227~~ ~~244~~ bytes

Let's get the ball rolling:

```
f=s=>{(i=new Image).src=s;c=document.createElement`canvas`.getContext`2d`;c.drawImage(i,0,0,100,100);for(a=360;a--,r=a/180*(m=Math).PI;)if(!c.getImageData(50+48*m.cos(r),50+48*m.sin(r),1,1).data[1]){alert((450-a)%360);break}}

```

Simply pass the URL of the image to the function:

```
f('90deg.png');

```

Alerts degrees within the ±1 range. Passed all test cases.

**Ungolfed**

```
f=s=>{
    // create new image and set source
    (i=new Image).src=s;
    // create canvas and get context
    c=document.createElement`canvas`.getContext`2d`;
    // set width/height to 100px and draw image on canvas
    c.drawImage(i,0,0,100,100);
    // check whether for any degree on the theoretical circle a black pixel is found
    for(a=360;a--,r=a/180*(m=Math).PI;)
        if(!c.getImageData(50+48*m.cos(r),50+48*m.sin(r),1,1).data[1]){
            // wait, it should be ccw and the board is rotated 90 degrees
            alert((450-a)%360);
            break
        }
}

```

**Edits**

* *Saved* **17 bytes** – figured I don't need to set the width and height of the canvas element.
* *Saved* **2 bytes** by negating the condition.
> 9 votes

# Answer
# Matlab, ~~118~~ 104 bytes

I generate a matrix of the same size as the image with complex numbers (0 in the center) and exctract from that matrix the values which are on the line. The argument of the mean of those is then displayed.

Thanks to @ThomasKwa for suggesting an improvement in accuracy which also resulted in shorter code!!!

```
I=imread(input('','s'));
[y,x]=ndgrid(-50:49);
c=y+i*x;
disp(mod(angle(mean(c(~I(:,:,1))))*180/pi+360,360))

```
> 5 votes

# Answer
## Matlab, ~~86~~ 77 bytes

Here's another way using Matlab:

```
[I,J]=find(~im2bw(imread(input('','s'))));mode(mod(round(atan2d(J-51,I-51)),360))

```

This reads the file (stolen from **flawr**), and finds the indices of the black pixels. Then, it works out the vector that points from the centre of the image to each black pixel, and uses `atan2d` to find the angle, rounding to get integer angles, and doing `mod(...,360)` to get results in the right range. To get the correct angle (there is a bit of error for the pixels close to the centre), take the most commonly calculated angle.

Thanks to **slvrbld** for the `im2bw` suggestion!
> 5 votes

# Answer
# Labview, 10098 Bytes

Let's put another labview code out there.

Since there is no official way to count bytes in labview i use the size of the file when saved. Alternatively counting every wire and function as 1and the case as 2 it would come out to 71.

Load image, flatten to 1D, scan for 0s from both sides and take the first, calc back to point and use geometry to get angle.
> 3 votes

---
Tags: code-golf, image-processing
---


title: Title Keywords in Context

text:
# Question
Title: Title Keywords in Context
This challenge is based on a problem described in *D. Parnas, On the criteria to be used in decomposing systems into modules*, and elaborated upon in *J. Morris, Real Programming in Functional Languages*.

Write a program or function which takes a list of book titles from `stdin` or as an argument, in a reasonable, convenient format for your language. For example,

```
Green Sleeves
Time Was Lost

```

or

```
("Green Sleeves";"Time Was Lost")

```

Return or print to `stdout` an alphabetized list of the keywords, showing their context within the original titles by enclosing each keyword in angle braces (`<` and `>`). As with input, output can be in a reasonable format which is convenient for your language- newline-separated lines, a list of strings, etc:

```
<Green> Sleeves
Time Was <Lost>
Green <Sleeves>
<Time> Was Lost
Time <Was> Lost

```

Titles will consist of a series of keywords separated by a single space. Keywords will contain only alphabetic characters. Keywords are to be sorted lexicographically. Titles will be unique, and keywords will be unique within each title but the same keyword may exist in several titles. If a keyword exists in more than one title, the output should list each appearance *in an arbitrary order*. For example, given this input:

```
A Dugong
A Proboscis

```

A valid output would be either:

```
<A> Proboscis
<A> Dugong
A <Dugong>
A <Proboscis>

```

Or:

```
<A> Dugong
<A> Proboscis
A <Dugong>
A <Proboscis>

```

This is - the winner is the shortest solution in bytes. Standard loopholes are disallowed.

# Answer
# Pyth, ~~25~~ ~~24~~ 22 bytes

```
VSsm,Rdcd\ QAN:HGjG"<>

```

Try it online.

Takes input as an array of lines, like `["Green Sleeves","Time Was Lost"]`.

### Explanation

```
VSsm,Rdcd\ QAN:HGjG"<>   implicit: Q = evaluated input

   m       Q                   map input lines:
       cd\                         split input line to words
    ,Rd                          replace each word by pair [word, entire line]
  s                          concatenate results for all input lines
 S                         sort the array of pairs lexicographically
V                        loop over the array
            AN             assign the word to G and the corresponding line to H
                 jG"<>       put the word between <>
              :HG          replace the word by the above in the line and print

```
> 4 votes

# Answer
# Japt, 55 bytes

Perhaps this could be made shorter, but I'm not sure how...

```
P+UqR £XqS m_+S+X) q', n £Xs1+XbS)rXs0,XbS),@"<{X}>")qR

```

### How it works

```
P+UqR m@XqS m_+S+X) q', n m@Xs1+XbS)rXs0,XbS),@"<{X}>")qR
          // Implicit: U = input string, S = a space, P = empty string
UqR m@    // Split input at newlines, then map each item X to:
XqS m_    //  X split at spaces, with each item Z mapped to:
+S+X)     //   Z + a space + X.
P+   q',  // Parse the result as a string, and split at commas. Due to JS's default
          // array-to-string conversion (joining with commas), this flattens the array.
n         // Sort the result lexicographically.
m@Xs1+XbS // Map each item X to everything after the first space,
rXs0,XbS  // replacing the original keyword with
@"<{X}>"  // "<" + keyword + ">".
qR        // Join the result with newlines.
          // Implicit: output last expression

```
> 2 votes

# Answer
## CJam, ~~41~~ ~~36~~ 32 bytes

```
q~{:AS/{A1$/"<>"@**}/}%{'</1=}$p

```

Test it here.
> 1 votes

# Answer
## Haskell, 113 bytes

```
import Data.List
g l=[(m,h++('<':m++['>']):t)|(h,m:t)<-zip(inits l)$tails l]
f=map(unwords.snd).sort.(>>=g.words)

```

Usage example: `f ["Green Sleeves","Time Was Lost"]` -\> `["<Green> Sleeves","Time Was <Lost>","Green <Sleeves>","<Time> Was Lost","Time <Was> Lost"]`.
> 1 votes

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


title: Loop Detection - not that kind!

text:
# Question
Title: Loop Detection - not that kind!
The goal of this challenge is to find the direction and area enclosed by a loop.

# Input:

A rectangular grid consisting entirely of these characters: `^v<>`

(Optionally, you may also be given the dimensions of the grid before the grid itself in decimal with a prefix, suffix, and separator character of your choice.)

A **loop** in the grid is a set of the aforementioned characters such that one points to the next, pointing to the next, eventually pointing back at the first character. For example:

```
<>>v>     >>v
^^<>v     ^ >v
>^<<<     ^<<<
>^<v>

```

The left grid is the sample input; the right grid is the loop isolated.

The input grid will contain either no loops at all or one loop; you do not have to worry about any cases in which the grid contains more than one loop.

# Output:

If the grid contains no loop, output `X`.

If the grid contains two arrows pointing at each other, output `0`.

If the grid contains a counterclockwise loop, count the characters enclosed by the loop, including the border. Output that number.

If the grid contains a clockwise loop, follow the same process for the counterclockwise loop, but output the negative of that number. For instance, the above input grid would have an output of `-11`: 10 come from the loop itself, and 1 from the character enclosed by the loop.

This is . Shortest code wins.

# Test cases:

```
<<^
^>v
^v<

```

Output `X`.

```
<<<<
><<<
>>^>

```

Output `0`.

```
<>^^<
>>>v>
<^^>v
<^>>v
>^<<<

```

Output `-15`.

```
v<<<<
>v>>^
v<^<<
>>>>^

```

Output `20`.

# Answer
> 4 votes
# C#, 604 bytes

Complete program, accepts input (line-delimitated layout, no dimensions) from STDIN, outputs to STDOUT.

```
using C=System.Console;class P{static void Main(){int w=0,W,i,j,t,k,l,c;string D="",L;for(;(L=C.ReadLine())!=null;D+=L)w=L.Length;var R=new[]{-1,0,1,w,-w};L="X";for(W=i=D.Length;i-->0;){var M=new int[W];for(k=j=i;i>0;){M[j]=++k;t=j+R[c=D[j]%5];if(t<0|t>=W|c<3&t/w!=j/w|c>2&t%w!=j%w)break;j=t;if((l=M[j])>0){var J=new int[W+1];System.Func<int,int>B=null,A=s=>J[s]<0?0:J[k=B(s)]=k==W?k:i;B=x=>J[x]==x?x:B(J[x]);for(i=J[W]=W;i>0;)J[--i]=M[i]<l?i%w<1|i%w>w-2|i<w|i>W-w?W:i:-1;for(;i<W;)if(J[++i]<0)l=D[i]%5/2-1;else{A(i-1);if(i>w)A(i-w);}for(c=W;i-->0;L=""+(c>2?c:0)*l)c-=J[i]<0?0:B(i)/W;}}}C.WriteLine(L);}}

```

The program works by first reading in the layout, needless to say, and then iterating over every cell. We then run a 'snake' from each cell, which follows the arrows until it runs off the edge, or runs into itself. If it runs into itself, then we know we have found a loop (or one of those "\>\<" things), and it also knows how much of the snake is in the loop.

Once we know we have a loop, we know which cells are on the loop, and we create a map from each cell (+1, for reasons) to either itself, `-1` (means it's on the loop), or `W` (the whole width) if it's on the edge (or the +1 (which is at index `W`) to simplify things further one).

While we do this, we also find the direction that the 'last' element of the loop has (that is, the last element of the loop on the last row that has elements from the loop on it). This element must be a "\<" or an "^", and this tells us the clockness (CW/CCW) of the loop (translated to -1/+1).

We then perform a disjoin set pass, which assigns all the elements that are outside the loop to the `W` set. We then subtract how many of these there are from `W` to get the number contained on and in the loop. If this number is less than 3, we replace it with 0. We multiply this by the clockness, set it as the result, and somehow escape from the for loops, where the result is output.

If, however, most of the above never happens (because no snake ever finds itself), then the result remains as "X", and that is outputted.

```
using C=System.Console;

class P
{
    static void Main()
    {
        int w=0, // width
        W, // full length
        i, // used for iterating over all the cells
        j, // keeps track of where the snake as got to
        t, // t is next j
        k, // how far along the snake we are, kind of
        // later on, k is used as temp for A
        l, // stores a threshold for how far along the snake the loop starts
        // later on, l stores the last seen pointer - this tells us the clockness
        c; // the translated direction
        // later on, c is a backwards-count

        string D="", // D is the map
        L; // used for reading lines, and then storing the result

        // might not be the best yay of doing this
        for(;(L=C.ReadLine())!=null; // read a line, while we can
            D+=L) // add the line to the map
            w=L.Length; // record the width

        var R=new[]{-1,0,1,w,-w}; // direction table (char%5) - might be able to replace this array with some bit bashing/ternary

        L="X"; // can't seem to fit this in anywhere... (don't strictly need to re-use L)
        for(W=i=D.Length;i-->0;) // for each cell, we send a 'snake' to try to find the loop from that cell
        {
            var M=new int[W]; // stores how far along the snake this point is

            for(k=j=i; // k's value doesn't really matter, as long as it's not stupidly big
                i>0;) // the i>0 check is just for when we return (see comment at the end of the code)
            {
                M[j]=++k; // store snake point and advance distance

                t=j+R[c=D[j]%5]; // t is position after move (translate <>v^ to 0234 (c is direction))
                //c=D[j]%5; // translate <>v^ to 0234 (c is direction)
                //t=j+R[c]; // t is position after move
                if(t<0|t>=W|c<3&t/w!=j/w|c>2&t%w!=j%w)
                    break; // hit an edge - will always happen if we don't find a loop - give up on this snake
                j=t; // move to new position

                if((l=M[j])>0) // we've been here before...
                {
                    // disjoint sets (assign all the edges to one set, assign all the ones on the line to another set, do adjacent disjoint, return size-outteredge (minus if necessary)
                    var J=new int[W+1]; // looks like we can reuse M for this

                    System.Func<int,int>B=null,
                    // whatever s points at should point to i, unless s points to W, in which case it should keep point to W
                    A=s=>J[s]<0?0:J[k=B(s)]=k==W?k:i;
                    // read the value this points to
                    B=x=>J[x]==x?x:B(J[x]);

                    for(i=J[W]=W;i>0;)
                        J[--i]=M[i]<l? // if we are not part of the loop
                            i%w<1|i%w>w-2|i<w|i>W-w? // if we are on the edge
                                W: // on the edge
                                i: // not on the edge
                             -1; // this is on the loop

                    // now fill in
                    // we don't have to worry about wrapping, the important bit being an un-wrapping closed loop
                    // i = 0
                    for(;i<W;)
                        if(J[++i]<0) // we are on the loop
                            l=D[i]%5/2-1; // last one must be ^(4) or <(0)
                        else{ // can probably crush this into an l returning l assigning term (with if above)
                            A(i-1);
                            if(i>w)
                                A(i-w);
                        }

                    // now count the number of non-edges
                    for(c=W; // assume everything is a non-edge
                        i-->0;
                        L=""+(c>2?c:0)*l) // set output to be number of non-edges * clockness (or 0 if too few)
                        c-=J[i]<0?0:B(i)/W; // subtract 1 if an edge (B(i) is W), othewise 0

                    // at this point, i is 0, so we will fall out of all the loops
                }
            }
        }

        C.WriteLine(L); // output result
    }
}

```

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


title: Check my program!

text:
# Question
Title: Check my program!
## Challenge

Make an error-checker in the least amount of possible bytes! If you received an HTML program as a string through standard input, your program will be able to find all the errors and return to standard output. If the program is over 2000 characters, return that as an error too.

## Errors

As there has been discrepancy, I will provide the errors you can check for.

Regular:

* File too long
* Tag not closed
* Non-empty element not closed
    + XHTML self-closing will not give you any bonus.
* Entity not closed (i.e. `&amp` vs `&`)
* CSS rule with no selector attached (i.e. `{color:white;}` vs `span {color:white;}`
* CSS unclosed property-value pair (i.e. `color:white` vs `color:white;`)
* Errors with brackets (e.g. no closing bracket, rules outside brackets, etc.)
    + Each different rule about brackets counts separately.
* Undefined tag (worth x10)
* Undefined attribute (worth x4)
* Undefined CSS property (worth x10)

Let me make this clear:

### You are not expected to complete all or even most of these.

Completing 7 of them would be incredible, but not necessary. Please though, try as many as you can while keeping the byte count relatively low!

## Scoring

* -10 bytes for every type of SyntaxError checked (e.g. undefined tag, oversized file \[see above\], etc.)
* -30 bytes for every type of SyntaxError checked that returns a customized error message and line number. (for a total of -40 bytes per error)
    + You may not have a customized message less than 20char.
* -100 bytes if your program can check embedded CSS in the document for at least 3 types of errors. (this includes `<element style="">` and `<style></style>`.
* +100 bytes if you check only 3 or less types of errors.
* ~0 bytes if your final score is negative.

As this is my first code-golf challenge, please comment if you think the scores are out of range.

## Rules

* You **may not** use a built-in function to check for errors.
* You **must** check for at least 1 error type. No blank answers! :D
* You **must** return *at minimum* the number of errors in the document.
* When you post your score, you **should** use this Markdown format:
Output:
> # My Language, ~~Unbonused bytes~~ Final Score
>
> ```
> code here
>
> ```
>
> **Solves:**
>
> + First Error
>     + Second Error
>     + Et Cetera
>
> Why/How it works

Markdown:

```
# My Language, <s>Unbonused bytes</s> Final Score #
    code here
**Solves:**
* First Error
* Second Error
* Et Cetera
Why/How it works

```

* You **may** add additional strikethroughed numbers if you wish in between the two values.

## Winning

After one week, the answer with the smallest number of bytes will win. If there is a tie, the answer with the most upvotes will win. If there is still a tie, I hold the divine power to choose. The winning answer will be accepted.

After the deadline, others can still post their answers, but no reward will be given.

## Good Luck!

This is my first challenge, so if anything is lacking in any way, please comment. Thank you!

# Answer
> 4 votes
# Unefunge 98, ~~15 9 - 10(1 error type)~~ 36 bytes - 40(one error with detatiled message) + 100 (only one error type) = ~~105 99~~ 96

This code only checks the file size.

```
'Ϩ#@k~"elif rellams a edivorP<NAK>"k,1q

```

Note that the code above contains a unicode number with code point 2000 (counted as two bytes) and an unprintable character with character code 21 (negative ackoledgement) represented by `<NAK>`. The error message produces is "Provide a smaller file".

Old 15-byte version:

```
2aaa***#@k~1q

```

How it works:

The programs `2aaa***` (in the old version) and  push the number 2000 on to the stack. Then the `#` character jumps over the `@` and `k` extecutes `~`, getting a char from user input, 2000 times. If eof is read, `~` reflects the program onto the `@` terminating with a zero exit code. If no eof is encountered, `1q` exits with exit code 1, indicating that there is one error in the input (its too big).

---
Tags: code-challenge, string, error-correction
---


title: Implement LaTeX accent macros

text:
# Question
Title: Implement LaTeX accent macros
## Introduction

The LaTeX typesetting system uses macros for defining accents. For example, the letter ê is produced by `\hat{e}`. In this challenge, your task is to implement an ASCII version of this functionality.

## Input

Your input is a non-empty string of printable ASCII characters. It will not contain newlines.

## Output

Your output is a string consisting of two lines. The first line contains accents, and the second line the characters they belong to. It is obtained from the input as follows (`A` denotes an arbitrary character):

* Every `\bar{A}` is replaced by `A` with `_` on top of it.
* Every `\dot{A}` is replaced by `A` with `.` on top of it.
* Every `\hat{A}` is replaced by `A` with `^` on top of it.
* **For a -10% bonus:** every `\tilde{A}` is replaced by `A` with `~` on top of it.
* All other characters have a space above them.

For example, the input

```
Je suis pr\hat{e}t.

```

results in the output

```
          ^
Je suis pret.

```

## Rules and scoring

You can assume that the characters `\{}` only occur in the macros `\bar{}`, `\dot{}` and `\hat{}` (and `\tilde{}` if you go for the bonus). All macro arguments are exact one character long, so `\dot{foo}` and `\dot{}` will not occur in the input. The output can be a newline-separated string, or a list/pair of two strings. Any amount of trailing and preceding whitespace is allowed, as long as the accents are in the correct places. In particular, if there are no accents, the output can be a single string.

You can write a full program or a function. The lowest byte count (after bonuses) wins, and standard loopholes are disallowed.

## Test cases

Without bonus:

```
Input:
No accents.
Output:

No accents.
Input:
Ch\hat{a}teau
Output:
  ^
Chateau
Input:
Som\bar{e} \dot{a}cc\hat{e}nts.
Output:
   _ .  ^
Some accents.
Input:
dot hat\dot{h}a\hat{t}\hat{ }x\bar{x}dot
Output:
       . ^^ _
dot hathat xxdot
Input:
\hat{g}Hmi\hat{|}Su5Y(\dot{G}"\bar{$}id4\hat{j}gB\dot{n}#6AX'c\dot{[}\hat{)} 6\hat{[}T~_sR\hat{&}CEB
Output:
^   ^     . _   ^  .      .^  ^     ^
gHmi|Su5Y(G"$id4jgBn#6AX'c[) 6[T~_sR&CEB

```

With bonus:

```
Input:
Ma\tilde{n}ana
Output:
  ~
Manana
Input:
\dot{L}Vz\dot{[}|M.\bar{#}0\hat{u}U^y!"\tilde{I} K.\bar{"}\hat{m}dT\tilde{$}F\bar{;}59$,/5\bar{'}K\tilde{v}R \tilde{E}X`
Output:
.  .   _ ^     ~   _^  ~ _      _ ~  ~
LVz[|M.#0uU^y!"I K."mdT$F;59$,/5'KvR EX`

```

# Answer
> 4 votes
# Pyth, ~~51~~ ~~46~~ ~~45~~ ~~43~~ ~~41~~ 40 bytes

I remove the curly braces and split at `\`, just like Reto Koradi's CJam answer does. The codes `bar`, `dot` and `hat` are recognized simply by the last decimal digit of the character code of the first character, modulo 3. I just add ~~`barf`~~ (RIP) `""""` to the first part and remove it in the end to save the code for handling the first part specially.

```
jtMsMCm,+@".^_"eChd*\ -ld4>d3c-+*4Nz`H\\

```

Try it online. Test suite.

# Answer
> 3 votes
# Julia, ~~204~~ 184 bytes * 0.9 = 165.6

```
x->(r=r"\\(\w)\w+{(\w)}";t=[" "^endof(x)...];while ismatch(r,x) m=match(r,x);(a,b)=m.captures;t[m.offsets[1]-1]=a=="b"?'_':a=="d"?'.':a=="h"?'^':'~';x=replace(x,r,b,1)end;(join(t),x))

```

This is an anonymous function that accepts a string and returns a tuple of strings corresponding to the top and bottom lines. The top line will have trailing whitespace. To call the function, give it a name, e.g. `f=x->...`

Ungolfed:

```
function f(x::AbstractString)
    # Store a regular expression that will match the LaTeX macro call
    # with capture groups for the first letter of the control sequence
    # and the character being accented
    r = r"\\(\w)\w+{(\w)}"

    # Create a vector of spaces by splatting a string constructed with
    # repetition
    # Note that if there is anything to replace, this will be longer
    # than needed, resulting in trailing whitespace
    t = [" "^endof(x)...]

    while ismatch(r, x)
        # Store the RegexMatch object
        m = match(r, x)

        # Extract the captures
        a, b = m.captures

        # Extract the offset of the first capture
        o = m.captures[1]

        # Replace the corresponding element of t with the accent
        t[o-1] = a == "b" ? '_' : a == "d" ? '.' : a == "h" ? '^' : '~'

        # Replace this match in the original string
        x = replace(x, r, b, 1)
    end

    # Return the top and bottom lines as a tuple
    return (join(t), x)
end

```

# Answer
> 2 votes
# CJam, 53 bytes

```
Sl+'\/(_,S*\@{(i2/49-"_. ^"=\3>'}-_,(S*@\+@@+@@+\}/N\

```

Try it online

Explanation:

```
S       Leading space, to avoid special case for accent at start.
l+      Get input, and append it to leading space.
'\/     Split at '\.
(       Split off first sub-string, which does not start with an accent.
_,      Get length of first sub-string.
S*      String of spaces with the same length.
\       Swap the two. First parts of both output lines are now on stack.
@       Rotate list of remaining sub-strings to top.
{       Loop over sub-strings.
  (       Pop first character. This is 'b, 'd, or 'h, and determines accent.
  i       Convert to integer.
  2/      Divide by two.
  49-     Subtract 49. This will result in 0, 1, or 4 for the different accents.
  "_. ^"  Lookup string for the accents.
  =       Get the correct accent.
  \       Swap string to top.
  3>      Remove the first 3 characters, which is the rest of the accent string
          and the '{.
  '}-     Remove the '}. All the macro stuff is removed now.
  _,(     Get the length, and subtract 1. This is the number of spaces for the first line.
  S*      Produce the spaces needed for the first line.
  @\+     Bring accent and spaces to top, and concatenate them.
  @@+     Get previous second line and new sub-string without formatting to top,
          and concatenate them.
  @@+     Get previous first line and new accent and spacing to top,
          and concatenate them.
  \       Swap the two lines to get them back in first/second order.
}/      End loop over sub-strings.
N\      Put newline between first and second line.

```

# Answer
> 1 votes
## Haskell, 156 * 0.9 = 140.4 bytes

```
g('\\':a:r)=(q,l):g s where q|a=='b'='_'|a=='d'='.'|a=='h'='^'|a=='t'='~';(_,_:l:_:s)=span(<'{')r
g(a:b)=(' ',a):g b
g""=[('\n','\n')]
f=uncurry(++).unzip.g

```

Usage example:

```
*Main> putStr $ f "\\dot{L}Vz\\dot{[}|M.\\bar{#}0\\hat{u}U^y!\"\\tilde{I} K.\\bar{\"}\\hat{m}dT\\tilde{$}F\\bar{;}59$,/5\\bar{'}K\\tilde{v}R \\tilde{E}X`"
.  .   _ ^     ~   _^  ~ _      _ ~  ~
LVz[|M.#0uU^y!"I K."mdT$F;59$,/5'KvR EX`

```

How it works: go through the input string character by character and build a list of pairs of characters, the left for the upper output string, the right for the lower output string. If a `\` is found, take the appropriate accent, else a space for the left element. Finally transform the list of pairs into a single string.

# Answer
> 0 votes
# Python 3, 203 bytes

Without bonus:

```
l=list(input())
b=list(" "*len(l))
try:
 while 1:s=l.index("\\");t=l[s+1];del l[s+6];del l[s:s+5];b[s] = "b"==t and "_" or "d"==t and "." or "h"==t and "^" or "*";
except:print("".join(b)+"\n"+"".join(l));

```

I really hope there is a shorter version.

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


title: Reimplementing square root

text:
# Question
Title: Reimplementing square root
Define a function, s, which takes a number and returns the square root.

No use of library functions, such as Java's Math.sqrt() or PHP's built in sqrt(), allowed.

# Answer
> 32 votes
## Python - 11 chars

Technically not a library function :)

```
input()**.5

```

As a function it's 16 chars

```
f=lambda x:x**.5

```

# Answer
> 24 votes
## Python (13 chars)

`f=.5.__rpow__`

This is equivalent to `f=lambda x:x**.5`, but 3 bytes shorter.

# Answer
> 17 votes
## Python - 41 chars

Takes a while to run for large numbers :)

```
n=input()
i=0
while i*i<n:i+=1e-9
print i

```

# Answer
> 15 votes
## Java (163)

Implementing a double precision square root calculator by making use of the fast invert square root stuff from quake and a new constant for the 64bit floats. In java. Yay for verbosity.

```
public double i(double a){double b=a/2;long c=0x5fe6ec85e7de30daL-(Double.doubleToRawLongBits(a)>>1);a=Double.longBitsToDouble(c);return a*(1.5-b*a*a);};s=1/i(x);

```

# Answer
> 9 votes
## **J, ~~6~~, 5**

Using power:

```
^&0.5

```

Or, perhaps more mnemonically:

```
^&1r2

```

Using the slightly less "cheaty" method, `exp(log(x)/2)`.

```
-:&.^.

```

Except since `exp` is the inverse of `log`, we simply "**halve** (`-:`) **under** (`&.`) **log** (`^.`)"

Not that normally a J programmer would not name a method this short; he'd simply embed in in a larger program.

# Answer
> 8 votes
# Haskell, 9 characters

```
s=(**0.5)

```

Similar to @gnibbler's Python solution.

# Answer
> 5 votes
Naive solution, accepts only positive integer inputs.

```
s n=foldr (\x a->x*x==n||a) False [1..]

```

Haskell, 39 characters.

# Answer
> 5 votes
**LISP (66)**

Using Babylonian method.

```
(defun s(A)
   (do((x 1(*(+ x(/ A x)).5))(n 100(1- n)))((zerop n)x)))

```

# Answer
> 5 votes
## Python - 65

A simple solution using Newton's method.

```
def s(x):
 t=1.0
 while 1e-9<abs(x-t*t):t-=(t*t-x)/2/t
 return t

```

# Answer
> 5 votes
C with some bad form and deprecated features:

```
s(int n,int g){return g*g-n?s(n,random()%n):g;}

```

If your compiler is enough of a liberal hippie, it should be possible to call s(n) and (eventually) receive the desired value.

# Answer
> 4 votes
```
def sqrt_newton(x):
 f,g,w,d=lambda a:a*a-x,lambda a:2.0*a,x/2.0,1e-4
 while abs(f(w))>d:w-=(f(w)/2.0/w)
 return w

```

reduced version of https://gist.github.com/713104

# Answer
> 3 votes
```
return 1.f/InvSqrt(x);

```

InvSqrt of course courtesy of Quake.

What, you mean you wanted an accurate result?

# Answer
> 3 votes
## C++ (61)

*Uses Heron's Method:*

```
f64 s(f64*x,u64 n=9){*x=(x[1]/*x+*x)/2;return n?s(x,--n):*x;}

```

Recursion, pointers, optional arguments, and ternary operators FTW!

---

Usage:

```
f64 x[2] = {12.0, 12.0};
std::cout << s(x);

```

# Answer
> 2 votes
## C++ (35)

```
f64 s(f64 x){return exp(log(x)/2);}

```

I promise I didn't use `sqrt()`!

# Answer
> 2 votes
## ActionScript3 (53)

Using Newton's method. (Hooray 4 IEEE 754)

```
function s(b,d=2){return b==d*d?d:s(b,d-(d*d-b)/2/d)}

```

I know I'm TOO late but I just wanted to write something I did :(

# Answer
> 2 votes
# JavaScript, 121

No, it doesn't even come close, but it is more optimal than other solutions and doesn't use `Math.pow` with fractions.

```
s=n=>{for(var c=Math.pow(10,(''+Math.floor(n)).length),v=0,l;(l=v*v<n),c>1e-10;l!=v*v<n?c/=10:0)v*v<n?v+=c:v-=c;return v}

```

# Answer
> 2 votes
# GolfScript - 21

It uses the Babylonian method and works only with integers. According to my tests, it's good for up to 56 digits.

```
{1{.2$\/+2/}99*\;}:s;

```

Usage: `1000 s` -\> `31`

I think this is the shortest solution so far that doesn't call some kind of power function or external library.

# Answer
> 2 votes
# k (17 chars)

Iterative (implementation of Babylonian method):

```
{{.5*y+x%y}[x]/x}

```

Iterates until two successive values are *equal*

Example:

```
sqrt[1234] = {{0.5*y+x%y}[x]/x}1234
1b

```

Also the mandatory `xexp[;0.5]` for 10.

# Answer
> 1 votes
# Python, 44

```
def s(x):t=1.;exec"t=(t+x/t)/2;"*99;return t

```

Tested with:

```
for x in [0, (3+5**0.5)/2, 1000, 10**5, 10**11]:
    print x, '->', s(x)

```

Output:

```
0 -> 1.57772181044e-30
2.61803398875 -> 1.61803398875
1000 -> 31.6227766017
100000 -> 316.227766017
100000000000 -> 316227.766017

```

# Python, 50 49

In case you like recursion:

```
s=lambda x,t=1.,r=99:r and s(x,t/2+x/t/2,r-1)or t

```

Same testing code, same output.

# Answer
> 1 votes
**Mathematica 27**

```
f@x_:=Nest[(#+x/#)/2&,1.,9]

```

# Answer
> 1 votes
## Golf-Basic 84, 9 characters

```
i`Ad`A^.5

```

As a function, **15** characters:

```
i`A:Return A^.5

```

# Answer
> 1 votes
## JavaScript, 36 (or 14 without the function)

```
function s(n){return Math.pow(n,.5)}

```

# Answer
> 1 votes
**AWK, 8**

```
1,$0^=.5

```

Following solution can handle all values except 0

**AWK, 6**

```
$0^=.5

```

# Answer
> 1 votes
# Befunge 98 - 18

```
&00pv
0*::<+1vj!`g0

```

This **program** takes an input number from the user, and ends by pushing the integer square root on the stack (note that you said square root, but didn't specify whether floating point was necessary). Here is a function (well, closest thing to one) (requiring free access to cell `00`) (**15** chars):

```
00p::*00g`!jv1+

```

# Answer
> 1 votes
In these I expect the byte to be squared is in the current cell. It needs 8 cells to the right empty and it will have answers in the 4 cells starting from where the number was. These are:

1. integer result
2. a alternative result (would be the same or one higher if those multiplied is closer to the argument)
3. remainder
4. flag for negative remainder

# Extended BrainFuck: 310

```
>+4>15+4<[>>+<+<[->[->->>+<<]>[-<+>>]<+<<]>[-]>[-]3<[->+>>+3<]>[-<+>]4>[-<+3<+4>]<<[->-[>+>>]>[+[-<+>]>+>>]5<]3>[-3<+3>]<[->>+>+3<]<[->+4>+5<]>+[>>[-<]<[>]<-]3>+<[[-]>[-]>[-4<+4>]5<+<+4>]>[->[-]<[-3<+3>]]3<[->+<]<<[->>+4<->>]<+<[-[+3>[-]>>[-]4<-]>[-5>+4<]<]>[->]<<]<[-]5>[-4<+<+5>]>>[-6<+6>]<[-3<+3>]<<[-<<+>>]

```

It turns into the following:

# BrainFuck: 390 (the same as above run through the compiler)

```
>+>>>>+++++++++++++++<<<<[>>+<+<[->[->->>+<<]>[-<+>>]<+<<]>[-]>[-]<<<[->+>>+<<<]>[-<+>]>>>>[-<+<<<+>>>>]<<[->-[>+>>]>[+[-<+>]>+>>]<<<<<]>>>[-<<<+>>>]<[->>+>+<<<]<[->+>>>>+<<<<<]>+[>>[-<]<[>]<-]>>>+<[[-]>[-]>[-<<<<+>>>>]<<<<<+<+>>>>]>[->[-]<[-<<<+>>>]]<<<[->+<]<<[->>+<<<<->>]<+<[-[+>>>[-]>>[-]<<<<-]>[->>>>>+<<<<]<]>[->]<<]<[-]>>>>>[-<<<<+<+>>>>>]>>[-<<<<<<+>>>>>>]<[-<<<+>>>]<<[-<<+>>]

```

It's Newtons method starting at guess 16 and goes downwards. It stops when the last iteration didn't make a different integer result. This is actualy from the `sqrt` macro of EBF since I use it to implement print-string operator `|`. Here's the part from EBF source ungolfed:

```
; sqrt ^0  uses  9 cells that need to be empty
; will be fuzzy after calling because of divmod
; returns ^0 result
;         ^1 same as ^0 or it increased by 1. typically will ^2*^3 be closerto the requested argument than ^2*^2
;         ^2 remainder
;         ^3 indicates if remainder is negative
{sqrt
  check for wrong usage !diff:diff
  :in:guess:temp:cur:div:mod:res:indicator
  @in
  $guess+     ;initial guess is 16, but
  $mod 15+    ; its in mod and incremented (rounded up)
  $guess(     ; worst case is 1 with 5 iterations
      $cur+$temp+
      $guess(-$temp[->-$mod+$cur]>[@cur-$temp+$div]$cur+)
      $temp(-)$cur(-)
      $in(-$guess+$cur+)
      $guess(-$in+)
      $mod(-$div+$guess+)
      $cur &roundivmod ; remainder wil now be in mod
      $mod(-$res+)
      $cur(-$mod+$guess-)
      $temp+
      $guess[-[+$div(-)$res(-)$temp-]>[-@temp$indicator+$cur]$temp]>[-@temp>]
  )
  $in(-)
  $mod(-$guess+$in+)
  $indicator(-$guess+)
  $res(-$cur+)
  $div(-$temp+)
  $in
  !indicator!res!mod!div!cur!temp!guess!in
}

;; helper macros
; roundivmod uses divmod and puts the rounded result in ^0 and indication of rounded in ^1
; and a remainder (which ^1 is an indication is either reduction or inrement) in ^2
{roundivmod
    &divmod @cur
    ; *0|n-rem|rem|res|
    >>>(-<<<+)
    <(->>+>+) make double copy of remainder
    ; res|n-rem|0|0|rem|rem
    <(->+>>>>+)
    ; res|0|n-rem|0|rem|rem|n-rem
    >+[>>[-<]<[>]<-]
    >>>+<(
       [-]>[-]
       >(-<<<<+)
       <<<<<+<+
      )
     >(-
        >[-]
        <(-<<<+)
      )
  end divide
}

; this does the divmod. compiler is fuzzy after so caller must fix position to calling
{divmod[->-[>+>>]>[+[-<+>]>+>>]<<<<<]}

```

# Answer
> 1 votes
# Julia (9) characters

```
f(x) = x^.5

```

# Answer
> 1 votes
**Java: 74 characters**

I'm leaving the square root as an exact answer because I don't enjoy approximations :)

```
enum A{;public static void main(String[]a){System.out.println('√'+a[0]);}}

```

or

```
enum A {

    ;public static void main(String[] a) {
        System.out.println('√' + a[0]);
    }
}

```

# Answer
> 1 votes
## F# (12)

It seems like cheating since other languages has similar solutions. But it works.

```
let s n=n**0.5

```

# Answer
> 0 votes
### Scala 78 chars:

```
type D=Double
def q(x:D,g:D=9):D=if(math.abs(g*g-x)<.001)g else q(x,(g+x/g)/2)

```

invocation:

```
scala> q(12345)
res36: D = 111.10805572305925

```

# Answer
> 0 votes
# Postscript ~~94~~ 89

Babylonian method. Iterates until successive values are equal.

```
s{dup 2 div{2 copy div 1 index add .5 mul
2 copy eq{exit}if exch pop}loop pop exch pop}def

```

Commented:

```
/s{
    dup 2 div  % S x
    {  % S x
        2 copy div  % S x S/x
        1 index add .5 mul  % S x (S/x+x)/2
        2 copy eq { exit } if  % S x (S/x+x)/2
        exch pop  % S (S/x+x)/2:->x
    }loop
    pop exch pop
}def

```

# Answer
> 0 votes
## 228 ( a lot but **pure** bash only! ;)

For the count:

```
x=(600000 200000);z=${x[$(($1&1))]} y=1;while [ $y -ne $z ] ;do y=$z;printf -v z "%u" $(((${y}000+${1}00000000000/${y})/2));printf -v z "%.0f" ${z:0:${#z}-3}.${z:${#z}-3};done;z=0000$z;printf "%.3f\n" ${z:0:${#z}-4}.${z:${#z}-4}

```

As a function:

```
sqrt() {
    local -a xx=(600000 200000)
    local x1=${xx[$(($1&1))]} x0=1
    while [ $x0 -ne $x1 ] ;do
    x0=$x1
    printf -v x1 "%u" $(( (${x0}000 + ${1}00000000000/${x0} )/2 ))
    printf -v x1 "%.0f" ${x1:0:${#x1}-3}.${x1:${#x1}-3}
    done
    x1=0000$x1
    printf "%.3f\n" ${x1:0:${#x1}-4}.${x1:${#x1}-4}
}

sqrt 2000000
1414.214

sqrt 1414214
1189.207

echo $((1189207000/1414214))
840

```

(Nota: **840 x 1189** is A0 paper size in milimeters ;-)

## The same, but working under , , , and (busybox):

```
sqrt() {
    _val=$1
    set -- 6 2
    x1=$(eval echo \$$((1+(_val&1))))00000 x0=1
    while [ $x0 -ne $x1 ] ;do
    x0=$x1
    x1=000$(( (${x0}000 + ${_val}000000000/${x0} )/2 ))
    x1=$(printf "%.0f" $(echo $x1|sed 's/\(...\)$/.\1/'))
      done
    printf "%.3f\n" $(echo $x1|sed 's/\(...\)$/.\1/')
}

```

# Answer
> 0 votes
# dc, 46 chars

## Babylonian method \- iterative with given precision:

```
Fk?sp?sn1[ddstlnr/+2/pdlt-[0r-]sbd0>blp<a]dsax

```

Takes precision and `N` from stdin. Example invocation (first number is the precision, second number is N:

```
{ echo 0.0000001 ; echo 489 ; } | dc -e'Fk?sp?sn1[ddstlnr/+2/pdlt-[0r-]sbd0>blp<a]dsax'

```

It prints all the iterations, just for fun. Printing only last one is trivial change - just move the `p` behind `/+2/` at the end of the program.

Explanation:

* `Fk` sets precision to 15 (see the hexa trick here)
* `?sp` and `?sn` asks for input and stores it to the registers
* `1` is the original seed
* the iteration is computed by `ddstlnr/+2/`. Then, `dlt-` computes difference from previous iteration. `[0r-]sbd0>b` performs absolute value of the difference, and if it is greater than the specified precision, loop continues - `lp<a`.

# Answer
> 0 votes
```
 /*Fast inverse square root*/
/* from http://en.wikipedia.org/wiki/Fast_inverse_square_root */
float rsqrt( float y,int iter)
{
    const unsigned int fpMagic = 0x5f3759de << 1;
    /*evil floating point bitlevel hacking*/
    unsigned int *i;
    if (sizeof(int) != sizeof(float))
    return -1.0;
    int j;
    const float threehalfs = 1.5F;
    float x2 = y * 0.5F;
    void *p = &y;
    i = p;
    *i = (fpMagic - *i) >> 1;
    /* Newton iterations */
    for (j=0; j < iter; j++)
    {
    y  *=  threehalfs - ( x2 * y * y ) ;
    }
    return 1.0 / y;
}

```

# Answer
> 0 votes
# CoffeeScript (12)

```
s=(n)->n**.5

```

Thanks to gnibbler's post for the `.5` idea, I wouldn't have remembered that by myself.

# Answer
> 0 votes
# TI-BASIC, 3

```
2ˣ√Ans

```

If that's invalid:

## 4

```
Ans^.5

```

If that's also invalid:

## 5

```
e^(.5ln(Ans

```

If that's also invalid:

## 21

Babylonian method.

```
Ans→N
While Ans²≠N
mean({Ans,N/Ans
End
Ans

```

# Answer
> 0 votes
## Seriously, 4 bytes

 This language is 4 years newer than this challenge

```
1½,^

```

This does the following Python code in Seriously:

```
n=input();n**.5

```

# Answer
> 0 votes
# Vitsy, 5 Bytes

This language is 4 years newer than the challenge. Go figure.

Not so hard...

```
12/^N
12/      Push 1/2.
   ^     Put the input to the power of 1/2.
    N    Output as number.
```

# Answer
> 0 votes
## Perl 6,  ~~13~~  12 chars

```
sub s{$^a**½} # 13 chars / 14 bytes

```

```
my &s=* **½; # 12 chars / 13 bytes

```

---
Tags: code-golf, math
---


title: Who's that probability distribution?

text:
# Question
Title: Who's that probability distribution?
## Introduction

In this challenge, you are given a list of nonnegative floating point numbers drawn independently from some probability distribution. Your task is to infer that distribution from the numbers. To make the challenge feasible, you only have five distributions to choose from.

Note that all of the above distributions have mean exactly 1/2.

## The Task

Your input is an array of nonnegative floating point numbers, of length between 75 and 100 inclusive. Your output shall be one of the letters `UTBEG`, based on which of the above distributions you guess the numbers are drawn from.

## Rules and Scoring

You can give either a full program or a function. Standard loopholes are disallowed.

In this repository, there are five text files, one for each distribution, each exactly 100 lines long. Each line contains a comma-delimited list of 75 to 100 floats drawn independently from the distribution and truncated to 7 digits after the decimal point. You can modify the delimiters to match your language's native array format. To qualify as an answer, your program should correctly classify **at least 50 lists from each file**. The score of a valid answer is **byte count + total number of misclassified lists**. The lowest score wins.

# Answer
> 6 votes
# Julia, ~~60~~ 62 bytes + ~~25~~ 2 errors = ~~82~~ 64

```
k->"EGTBU"[(V=std(k);any(k.>1)?V>.34?1:2:V<.236?3:V>.315?4:5)]

```

This is fairly simple. The variance for the distributions are mostly different - it's 1/4 for exponential, 1/8 for beta, 1/12 for gamma and uniform, and 1/24 for triangular. As such, if we use variance (here done using `std` for standard deviation, the square root of variance) to determine the likely distribution, we only need to do more to distinguish gamma from uniform; for that, we look for a value larger than 1 (using `any(k.>1)`) - that said, we do the check for both exponential and gamma, as it improves overall performance.

To save a byte, indexing the string `"EGTBU"` is done instead of directly evaluating to a string within the conditionals.

For testing, save the txt files into a directory (keeping the names as-is), and run the Julia REPL in that directory. Then, attach the function to a name as

```
f=k->"EGTBU"[(V=std(k);any(k.>1)?V>.34?1:2:V<.236?3:V>.315?4:5)]

```

and use the following code to automate the testing (this will read from the file, convert into an array of arrays, use the function, and output for each mismatch):

```
m=0;for S=["B","E","G","T","U"] K=open(S*".txt");F=readcsv(K);
M=Array{Float64,1}[];for i=1:100 push!(M,filter(j->j!="",F[i,:]))end;
close(K);n=0;
for i=1:100 f(M[i])!=S[1]&&(n+=1;println(i," "S,"->",f(M[i])," ",std(M[i])))end;
println(n);m+=n;end;println(m)

```

Output will consist of rows containing the case that mismatched, the correct distribution -\> the determined distribution, and the variance calculated (eg. `13 G->E 0.35008999281668357` means that the 13th row in G.txt, which should be a gamma distribution, is determined to be an exponential distribution, with the standard deviation being 0.35008999...)

After each file, it also outputs the number of mismatches for that file, and then at the end it also displays the total mismatches (and it should read 2 if run as above). Incidentally, it should have 1 mismatch for G.txt and 1 mismatch for U.txt

# Answer
> 7 votes
# R, ~~202 192 184 182 162~~ 154 bytes + 0 errors

```
function(x)c("U","T","B","E","G")[which.max(lapply(list(dunif(x),sapply(x,function(y)max(0,2-4*abs(.5-y))),dbeta(x,.5,.5),dexp(x,2),dgamma(x,3,6)),prod))]

```

This is based on the Bayesian formula P(D=d|X=x) = P(X=x|D=d)\*P(D=d)/P(X=x), where D is the distribution and X is the random sample. We pick the d such that P(D=d|X=x) is greatest of the 5.

I assume a flat prior (i.e. P(D=di) = 1/5 for i in \[1,5\]), which means that P(D=d) in the numerator is the same in all cases (and the denominator would be the same in all cases anyways), so we can golf away everything but the P(x=X|D=d), which (except for the triangular distribution) simplify to native functions in R.

ungolfed:

```
function(x){
  u=prod(dunif(x))
  r=prod(sapply(x,function(y)max(0,2-4*abs(.5-y))))
  b=prod(dbeta(x,.5,.5))
  e=prod(dexp(x,2))
  g=prod(dgamma(x,3,6))
  den=.2*u+.2*r+.2*b+.2*e+.2*g
  c("U","T","B","E","G")[which.max(c(u*.2/den,r*.2/den,b*.2/den,e*.2/den,g*.2/den))]
}

```

Note that the ungolfed version is not exactly equivalent to the golfed version because getting rid of the denominator avoids the case of Inf/Inf which occurs if you allow the beta distribution to be over the closed interval \[0,1\] instead of (0,1) - as the sample data does. An additional if statement would handle that but since it's for illustrative purposes only it's probably not worth adding the complexity that is not at the heart of the algorithm.

Thanks @Alex A. for additional code reductions. Especially for which.max!

# Answer
> 6 votes
# CJam, 76

```
{2f*__{(z.4<},,%,4e<"UBT"="EG"\*\$-2=i3e<=}

```

The source code is **43** bytes long and misclassifies **33** lists.

### Verification

```
$ count()(sort | uniq -c | sort -nr)
$ cat score.cjam
qN%{',' er[~]
  {2f*__{(z.4<},,%,4e<"UBT"="EG"\*\$-2=i3e<=}
~N}/
$ for list in U T B E G; { echo $list; cjam score.cjam < $list.txt | count; }
U
     92 U
      6 B
      2 T
T
    100 T
B
     93 B
      7 U
E
     92 E
      8 G
G
     90 G
      6 E
      3 T
      1 U

```

### Idea

Differentiating the exponential and gamma distribution from the remaining ones is easy, since they are the only distributions that take values greater than **1**.

To decide between *gamma*, *exponential* and others, we take a look at the second highest value of the sample.

* If it lies in **\[1.5, ∞)**, we guess *gamma*.
* If it lies in **\[1, 1.5)**, we guess *exponential*.
* If it lies in **\[0, 1)**, we have three remaining possibilities.

The remaining distributions can be differentiated by the percentage of sample values that lie close to the mean (**0.5**).

We divide the length of the sample by the count of values that fall in **(0.3, 0.7)** and take a look at the resulting quotient.

+ If it lies in **(1, 2\]**, we guess *triangular*.
    + If it lies in **(2, 3\]**, we guess *uniform*.
    + If it lies in **(3, ∞)**, we guess *beta*.

### Code

```
2f*    e# Multiply all sample values by 2.
__     e# Push to copies of the sample.
{      e# Filter; for each (doubled) value in the sample:
  (z   e#   Subtract 1 and apply absolute value.
  .4<  e#   Check if the result is smaller than 0.4.
},     e# If it is, keep the value.
,/     e# Count the kept values (K).
%      e# Select every Kth value form the sample, starting with the first.
,      e# Compute the length of the resulting array.
       e# This performs ceiled division of the sample length by K.
4e<    e# Truncate the quotient at 4.
"UBT"= e# Select 'T' for 2, 'U' for 3 and 'B' for 4.
"EG"\* e# Place the selected character between 'E' and 'G'.
\$     e# Sort the remaining sample.
-2=i   e# Extract the second-highest (doubled) value and cast to integer.
3e<    e# Truncate the result at 3.
=      e# Select 'E' for 3, 'G' for 2 and the character from before for 1.

```

# Answer
> 3 votes
# Matlab, ~~428~~ 328 bytes + 33 misclassified

This program is basically comparing the real CDF with an estimated one given the data, and then calculating the mean distance between those two: I think the image explains more:

The data shown in this image here shows pretty clearly that it belongs to the turquoise distribution, as it is quite close to that one, so that is basically what my program is doing. It can probably be golfed somewhat more. For me that was first of all a conceptual challenge, not very golfy.

This approach is also independent of the pdfs chosen, it would work for **any** set of distributions.

Following (ungolfed) code should show how it is done. The golfed version is below.

```
function r=p(x);
data=sort(x(1:75));
%% cumulative probability distributiosn
fu=@(x)(0<x&x<1).*x+(1<=x).*1;
ft=@(x)(0<x&x< 0.5).* 2.*x.^2+(1-2*(1-x).^2).*(0.5<=x&x<1)+(1<=x);
fb=@(x)(0<x&x<1).*2.*asin(sqrt(x))/pi+(1<=x);
fe=@(x)(0<x).*(1-exp(-2*x));
fg=@(x)(0<x).*(1-exp(-x*6).*(1+x*6+1/2*(6*x).^2));
fdata = @(x)sum(bsxfun(@le,data,x.'),2).'/length(data);
f = {fe,fg,fu,ft,fb};
str='EGUTB';
%calculate distance to the different cdfs at each datapoint
for k=1:numel(f);
dist(k) = max(abs(f{k}(x)-fdata(x)));
end;
[~,i]=min(dist);
r=str(i);
end

```

Fully golfed version:

```
function r=p(x);f={@(x)(0<x).*(1-exp(-2*x)),@(x)(0<x).*(1-exp(-x*6).*(1+x*6+18*x.^2)),@(x)(0<x&x<1).*x+(1<=x),@(x)(0<x&x<.5).*2.*x.^2+(1-2*(1-x).^2).*(.5<=x&x<1)+(1<=x),@(x)(0<x&x<1).*2.*asin(sqrt(x))/pi+(1<=x)};s='EGUTB';for k=1:5;d(k)=max(abs(f{k}(x)-sum(bsxfun(@le,x,x.'),2).'/nnz(x)));end;[~,i]=min(d(1:5-3*any(x>1)));r=s(i)

```

# Answer
> 2 votes
# Perl, 119 bytes + 8 misclassifications = 127

I've made a tiny decision tree on three features:

* $o: boolean: if any samples \> 1.0
* $t: count: 0-th minus 6-th 13-ile clipped into the 0-1 range,
* $h: count: 0-th minus 6-th plus 12-th 13-ile clipped into the 0-1 range

Invoked with `perl -F, -lane -e '...'`. I'm not sure if I should add a penalty for the non-standard parameters. If the commas were spaces, I guess I could have gotten away without the *-F,*

```
for(@F){$b[$_*13]++;$o++if$_>1}
$h=($t=$b[0]-$b[6])+$b[12];
print$o?($t>-2?"e":"g"):($h=19?"b":"u"));
$o=@b=()

```

The slightly formatted output (without the -l flag) is:

```
bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb
    bbbbbbbbbbbbbbbbbbbbbbbbubbbbbbbbbbbbbbbbbbbbbbb
eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee
    eeegeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee
gggggggegggggggggggggggggggggggggggggggggggggggggggg
    gggggggggggggggggggggggggggggggggggggggggggggggg
tttttttttttttttttttttttttttttttttttttttttttttttttttt
    ttttttttttttttttttttttttttttuttttttttttttutttttt
uuuuuuuuuuuuuuuuuuuuuuuuuuutuuuuuuuuuuuuuuuubuuuuuuu
    uuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuutuuuu

```

# Answer
> 0 votes
# Python, 318 bytes + 35 missclassifications

```
from scipy.stats import*
from numpy import*
def f(l):
    r={'U':kstest(l,'uniform')[1],'T':kstest(l,'triang',args=(.5,))[1],'B':kstest(l,'beta',args=(.5,.5))[1],'E':kstest(l,'expon',args=(0,.5,))[1],'G':kstest(l,'gamma',args=(3,0,1/6.0))[1]}
    if sum([x>1 for x in l]): r['U'],r['T'],r['B']=0,0,0
    return max(r,key=r.get)

```

**Idea:** the distribution is guessed based on the p-value of the Kolmogorov-Smirnov test.

**Test**

```
from scipy.stats import*
from numpy import*
import os
from io import StringIO
dir=os.path.dirname(os.path.abspath(__file__))+"/random-data-master/"

def f(l):
    r={'U':kstest(l,'uniform')[1],'T':kstest(l,'triang',args=(.5,))[1],'B':kstest(l,'beta',args=(.5,.5))[1],'E':kstest(l,'expon',args=(0,.5,))[1],'G':kstest(l,'gamma',args=(3,0,1/6.0))[1]}
    if sum([x>1 for x in l]): r['U'],r['T'],r['B']=0,0,0
    return max(r,key=r.get)

U=[line.rstrip('\n').split(',') for line in open(dir+'U.txt')]
U=[[float(x) for x in r] for r in U]
T=[line.rstrip('\n').split(',') for line in open(dir+'T.txt')]
T=[[float(x) for x in r] for r in T]
B=[line.rstrip('\n').split(',') for line in open(dir+'B.txt')]
B=[[float(x) for x in r] for r in B]
E=[line.rstrip('\n').split(',') for line in open(dir+'E.txt')]
E=[[float(x) for x in r] for r in E]
G=[line.rstrip('\n').split(',') for line in open(dir+'G.txt')]
G=[[float(x) for x in r] for r in G]

i,_u,_t,_b,_e,_g=0,0,0,0,0,0
for u,t,b,e,g in zip(U,T,B,E,G):
    _u+=1 if f(u)=='U' else 0
    _t+=1 if f(t)=='T' else 0
    _b+=1 if f(b)=='B' else 0
    _e+=1 if f(e)=='E' else 0
    _g+=1 if f(g)=='G' else 0
    print f(u),f(t),f(b),f(e),f(g)
print _u,_t,_b,_e,_g,100*5-_u-_t-_b-_e-_g

```

---
Tags: code-challenge, probability-theory, classification
---


title: The unique multiplication spiral

text:
# Question
Title: The unique multiplication spiral
This one is inspired by Calvin's Hobbies recent multiplication table challenge.

Write a function or program that takes an integer `N` as input and prints or returns a N-by-N unique multiplication spiral. The code must (in theory) work for N between 0 and 1000 (outputting this can be hard though). The output should be equivalent to the table produced by the following procedure:

1. Fill out an N-by-N multiplication table. E.g. for N = 3:

```
1 2 3
2 4 6
3 6 9

```
2. Follow a spiral clockwise from the upper left corner, noting the numbers that you visit. When you visit a number which you have already visited, replace it with 0.

A few examples might make it more clear:

```
n = 0:
0

n = 1:
1

n = 2:       //   Spiral order:
1  2         //   1  2
0  4         //   4  3

n = 3:
1  2  3      //   1  2  3
0  4  6      //   8  9  4
0  0  9      //   7  6  5

n = 4:
1  2  3  4   //   1   2   3   4
0  0  6  8   //  12  13  14   5
0  0  9 12   //  11  16  15   6
0  0  0 16   //  10   9   8   7

n = 5:
1   2   3   4   5
0   0   6   8  10
0   0   9  12  15
0   0   0  16  20
0   0   0   0  25

n = 10:
1   2   3   4   5   6   7   8   9  10
0   0   0   0   0  12  14  16  18  20
0   0   0   0  15   0  21  24  27  30
0   0   0   0   0   0  28  32  36  40
0   0   0   0  25   0  35   0  45  50
0   0   0   0   0   0  42  48  54  60
0   0   0   0   0   0  49  56  63  70
0   0   0   0   0   0   0  64  72  80
0   0   0   0   0   0   0   0  81  90
0   0   0   0   0   0   0   0   0 100

```

The numbers are found like this:

Any reasonable output format is accepted, but it must be an N-by-N matrix, it cannot be just a list. Formats such the ones below are accepted, as there are N easily distinguishable 1-by-N columns, or N-by-1 rows:

```
[[1 2 3][0 4 6][0 0 9]]   <-- OK

[[1 0 0][2 4 0][3 6 9]]   <-- OK

ans =                     <-- OK
    1  2  3
    0  4  6
    0  0  9

```

**Shortest code in bytes win.**

# Answer
> 3 votes
# J, 22 bytes

```
,~$[:(*~:)[:,1*/~@:+i.

```

It output a 0-by-0 matrix for `n=0`.

# Answer
> 8 votes
# Mathematica ~~123 122 117 98 92~~ 73 bytes

With 24 bytes saved thanks to LegionMammal978 and another 19 by alephalpha !

---

Surprisingly, in this table, multiple instances of any whole number `n` will have the same relative ordering in the spiral as they do in the table itself! The first appearance of a number `n` lies at the very cell where that number appears first in the table (when one fills in the table row by row). This means that the approach can disregard the spiral constraint altogether, for it has no bearing on the outcome. (See explanation below.)

```
ReplacePart[t=1##&~Array~{#,#},Join@@(Rest[t~Position~#]&/@Union@@t)->0]&

```

---

## Example

```
ReplacePart[t=1##&~Array~{#,#},Join@@(Rest[t~Position~#]&/@Union@@t)->0]&[10]

```

> {{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, {0, 0, 0, 0, 0, 12, 14, 16, 18, 20}, {0, 0, 0, 0, 15, 0, 21, 24, 27, 30}, {0, 0, 0, 0, 0, 0, 28, 32, 36, 40}, {0, 0, 0, 0, 25, 0, 35, 0, 45, 50}, {0, 0, 0, 0, 0, 0, 42, 48, 54, 60}, {0, 0, 0, 0, 0, 0, 49, 56, 63, 70}, {0, 0, 0, 0, 0, 0, 0, 64, 72, 80}, {0, 0, 0, 0, 0, 0, 0, 0, 81, 90}, {0, 0, 0, 0, 0, 0, 0, 0, 0, 100}}

---

```
Grid[%]

```

---

## Explanation

We exploit the fact that the spiral-order of the positions of any digit, n, is the same as the the order of row-col positions returned by the function, `Positions`!

The location of the first occurrence of each number (whether one orders by the spiral or by the table position) will be the first element returned by `Position`. That first-occurrence cell will be left as it is. The remaining instances of the number are replaced by 0.

Let's look at how this works, examining for the case of `n==18`. The idea is to start with the multiplication table:

```
(t = Table[k Range@#, {k, #}] &[10]) // Grid

```

and locate the row-col positions of each number. For example, 18 is located at Row 2, Col 9 (the first instance); Row 3, Col 6; Row 6, Col 3; and Row 9, Col 2. These have the respective spiral-order positions {44, 58, 68, 82}.

```
Position[t, 18]

```

> {{2, 9}, {3, 6}, {6, 3}, {9, 2}}

as the following table shows.

The final 3 instances of 18 need to be replaced by 0. (We'll use a large bold blue zeros so they can be easily spotted.)

```
ReplacePart[%, {{3, 6}, {6, 3}, {9, 2}} -> Style[0, {Blue, Bold, 16}]]// Grid

```

# Answer
> 2 votes
# MATLAB, ~~96 88 87 86~~ 79 bytes

This is the 79 byte code, which follows the example outputs (for n=0 specifically)

```
n=input('');m=+(n>0);for i=1:n;a=i*(1:i);for j=a;m(m==j)=0;end;m(1:i,i)=a;end;m

```

This one is 75 bytes, has the same behaviour except for n=0 which will produce an empty array as per the implication of the question (N by N array = 0 by 0 = empty array).

```
n=input('');m=[];for i=1:n;a=i*(1:i);for j=a;m(m==j)=0;end;m(1:i,i)=a;end;m

```

This also works with **Octave**. You can try it online here. The code is already added as a file named 'multspiral.m'. So at the Octave prompt, type `multspiral` and press enter. You should then enter the size of the table (e.g. 4). The output will then be printed.

---

### How does it work?

First this takes an input number as required (e.g. 6, 4, etc.)

```
n=input('');

```

Then we handle cases for `n=0` and `n=1` \- these are given special treatment as they are two that don't follow the rule I am using for generating the arrays - in fact this could be 5 bytes shorter if not for the obscure `n=0` case.

```
m=+(n>0);

```

Then for all values of `n>2`, we do some looping until the matrix is grown to the correct size.

```
for i=2:n;

```

There are actually only three simple differences between `n` and `n+1` for all `n>=2`. These are:

1. A new column is added rightmost in the array which contains the numbers `n(1:n)`. This is easily calculated with:

```
 a=i*(1:i);

```
2. Any elements which will be added in that new column must be removed from the existing matrix (set to zero) as they will always come later in the spiral than the new column. This is removed using a nestled for loop to set all elements in the current matrix which are in the new column to be zero.

```
for j=a;
    m(m==j)=0;
end;

```
3. There is a new row bottom most for which every element except that which is in the new column will be zero. When the new column added, because of the out of bounds indices that has been intentionally created are padded automatically with 0. One of MATLAB's strong features is that it can grow arrays without any special handling, so we can add the new row and column simply with:

```
m(1:i,i)=a;

```

Finally we have the end of the for loop - which once reached, the matrix `m` contains our output. As you are flexible with your output format, the matrix is shown by simply having `m` as a new line without a semicolon

```
end;
m

```

As an example, if we run the program, enter the number 10, we get the following output:

```
m =
     1     2     3     4     5     6     7     8     9    10
     0     0     0     0     0    12    14    16    18    20
     0     0     0     0    15     0    21    24    27    30
     0     0     0     0     0     0    28    32    36    40
     0     0     0     0    25     0    35     0    45    50
     0     0     0     0     0     0    42    48    54    60
     0     0     0     0     0     0    49    56    63    70
     0     0     0     0     0     0     0    64    72    80
     0     0     0     0     0     0     0     0    81    90
     0     0     0     0     0     0     0     0     0   100

```

# Answer
> 2 votes
# Python, ~~99 95 90 89 87~~ 81 bytes

Golfed code:

```
n=range(1,input()+1);m=[]
for x in n:l=[(x*y,0)[x*y in m]for y in n];m+=l;print l

```

Ungolfed:

```
n=range(1,input()+1);
m=[]
for x in n:
  l=[(x*y,0)[x*y in m]for y in n];
  m+=l;
  print l

```

Output:

```
10
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
[0, 0, 0, 0, 0, 12, 14, 16, 18, 20]
[0, 0, 0, 0, 15, 0, 21, 24, 27, 30]
[0, 0, 0, 0, 0, 0, 28, 32, 36, 40]
[0, 0, 0, 0, 25, 0, 35, 0, 45, 50]
[0, 0, 0, 0, 0, 0, 42, 48, 54, 60]
[0, 0, 0, 0, 0, 0, 49, 56, 63, 70]
[0, 0, 0, 0, 0, 0, 0, 64, 72, 80]
[0, 0, 0, 0, 0, 0, 0, 0, 81, 90]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 100]

```

# Answer
> 1 votes
## Haskell, ~~103~~ 99 bytes

```
import Data.Lists
f 0=[[0]]
f n=chunksOf n$foldr(\c d->c:replace[c][0]d)[][a*b|a<-[1..n],b<-[1..n]]

```

Usage example: `f 4`-\> `[[1,2,3,4],[0,0,6,8],[0,0,9,12],[0,0,0,16]]`.

I've just discovered the `Data.Lists` module which has nice functions on lists (such as `replace`) and re-exports `Data.List`, `Data.List.Split` and `Data.List.Extras`.

# Answer
> 1 votes
# Ruby, ~~67~~ ~~63~~ 61 bytes

```
->n{s,x=1..n,{};s.map{|c|s.map{|r|x[v=c*r]==1?0:(x[v]=1;v)}}}

```

**63 bytes**

```
->n{s,x=1..n,{};s.map{|c|s.map{|r|e=x[v=c*r]==1?0:v;x[v]=1;e}}}

```

**67 bytes**

```
->n{s,x=1..n,[];s.map{|c|s.map{|r|e=x.include?(v=c*r)?0:v;x<<v;e}}}

```

**Usage:**

```
->n{s,x=1..n,{};s.map{|c|s.map{|r|x[v=c*r]==1?0:(x[v]=1;v)}}}[10]
=> [[1, 2, 3, 4, 5, 6, 7, 8, 9, 10], [0, 0, 0, 0, 0, 12, 14, 16, 18, 20], [0, 0, 0, 0, 15, 0, 21, 24, 27, 30], [0, 0, 0, 0, 0, 0, 28, 32, 36, 40], [0, 0, 0, 0, 25, 0, 35, 0, 45, 50], [0, 0, 0, 0, 0, 0, 42, 48, 54, 60], [0, 0, 0, 0, 0, 0, 49, 56, 63, 70], [0, 0, 0, 0, 0, 0, 0, 64, 72, 80], [0, 0, 0, 0, 0, 0, 0, 0, 81, 90], [0, 0, 0, 0, 0, 0, 0, 0, 0, 100]]

```

---
Tags: code-golf, number, arithmetic
---


# Question
Title: substring conversion (in Haskell). Can you beat this?
Ok, I found myself with a nice little problem:

you will get from `stdin` a string. In this string you will find some hex colors (like `#ff00dd`). You must return the string with the colors inverted (`#ff00dd` inverted is `#00ff11`).

A sample input/output could be:

```
ascscasad #ff00ff csdcas dcs c#001122 #qq5500
ascscasad #00ff00 csdcas dcs c#ffeedd #qq5500

```

As I am proficient in Haskell, I tackled the problem with it. Came up with this code, and I think it's the best I can do. Do you see any way to improve it / a completely different way to make it shorter?

```
import Text.Regex.Posix ( (=~) )

main = getLine >>= putStrLn . f

f [] = []
f x = let (b, q, p) = x =~ "#[0-f]{6}"
          c = '#' : ['0'..'f'] ++ "#"
          a = zip c (reverse c)
          r = map ( (maybe '@' id) . (flip lookup $ a) ) q
      in b ++ r ++ f p

```

I am also interested to compare other languages to Haskell, so post in other languages are welcome, too!

# Answer
> 3 votes
# Perl, 44 chars

Two different tweaks can get it to this length, one suggested by Primo:

```
s/#\K[\da-f]{6}/sprintf"%06x",~hex ff.$&/eg

```

Another one by playing around with the `/ee` modifier:

```
s/#\K[\da-f]{6}/"sprintf'%06x',~0xff$&"/eeg

```

Requires -p command line switch (1 char included in count).

Works for lower-case hex numbers (as in example). An `i` switch added to the regex would make it work for upper-case as well (though not preserving the case of the original number).

# Answer
> 2 votes
## APL 86

Index origin zero. Takes either a single colour hex string or multiple space separated colour strings as screen input via ←⍞

```
,' ',h[⊃16,¨,¨⍉¨(⊂16 16)⊤¨255-16⊥¨⍉¨(⊂3 2)⍴¨(⊂h←'0123456789abcdef#')⍳¨(c≠' ')⊂c←⍞~'#']

input: #ff00dd  output: #00ff22

input: #ff00dd #00ff22 output: #00ff22 #ff00dd

```

# Answer
> 1 votes
# Ruby, 46 bytes

```
gets.gsub(/#(\h+)/){"#%06x"%(0xffffff^$1.hex)}

```

---
Tags: code-golf
---


title: golffs - Implement a FUSE filesystem

text:
# Question
Title: golffs - Implement a FUSE filesystem
Implement a FUSE filesystem in minimum bytes.

Your program must do three things:

* Mounting the virtual filesystem to a directory
* Handling requests to enumerate files in that directory (showing one file)
* Handling requests to read the file in that directory

Rules:

* `ls` (a system program, you don't need to implement it) must show `hello.txt` file (other unrelated files can also be visible, as well as errors may be printed). `hello.txt` must be exact, `68 65 6c 6c 6f 2e 74 78 74` in hex).
* `cat` (a system program) pointed to the file should output `Hello, world.` (punctuation, case and end of lines may differ. A bunch of zero bytes can also slip unnoticed). It can also be `cat m/hello.txt; echo` if there is no trailing newline.
* It must be actual FUSE filesystem, not just a regular file created by your program. For example, freezing your program should freeze the `hello.txt` file (`cat` and `ls` would hang). Creating a socket instead of mounting FUSE filesystem isn't an allowed workaround. Your mounted filesystem should be visible in `/proc/mounts` (or platform analogue).
* For 200 bytes penalty, you may depend on libfuse or use it's header files (or depend on the appropriate FUSE binding in some other language)
* Detaching is optional
* You program may be platform-specific. Somebody else on that platform should check and write a comment that it works (or not)
* Your program can't be a kernel module (`fuse.ko` is the involved kernel module on Linux and is considered a part of environtment, not your program)
* Your program can access `/dev/fuse` (or platform analogue) directly. It may require root access (or changing permissions) for it if needed. It can also rely on `fusermount` for the mounting step (like the example below). Whether using `fusermount` for mounting carry penalty or not I have not decided yet (because of I don't know implementation details enough): if the rest feels like talking to kernel directly then it should not be a problem.
* Additional compilation and invocation parameters are added to the score. A directory to be mounted may be specified as a free (non-penalty) parameter or may be just hardcoded (like `m`)

Example (directly based on official hello.c):

```
#define FUSE_USE_VERSION 26

#include <fuse.h>
#include <stdio.h>
#include <string.h>
#include <errno.h>
#include <fcntl.h>

static const char *hello_str = "Hello, world\n";
static const char *hello_path = "/hello.txt";

static int hello_getattr(const char *path, struct stat *stbuf)
{
    int res = 0;

    memset(stbuf, 0, sizeof(struct stat));
    if (strcmp(path, "/") == 0) {
        stbuf->st_mode = S_IFDIR | 0755;
        stbuf->st_nlink = 2;
    } else if (strcmp(path, hello_path) == 0) {
        stbuf->st_mode = S_IFREG | 0444;
        stbuf->st_nlink = 1;
        stbuf->st_size = strlen(hello_str);
    }
    return res;
}

static int hello_readdir(const char *path, void *buf, fuse_fill_dir_t filler,
             off_t offset, struct fuse_file_info *fi)
{
    filler(buf, hello_path + 1, NULL, 0);
    return 0;
}

static int hello_open(const char *path, struct fuse_file_info *fi)
{
    return 0;
}

static int hello_read(const char *path, char *buf, size_t size, off_t offset,
              struct fuse_file_info *fi)
{
    size_t len;
    (void) fi;
    if(strcmp(path, hello_path) != 0)
        return -ENOENT;

    len = strlen(hello_str);
    if (offset < len) {
        if (offset + size > len)
            size = len - offset;
        memcpy(buf, hello_str + offset, size);
    } else
        size = 0;

    return size;
}

static struct fuse_operations hello_oper = {
    .getattr    = hello_getattr,
    .readdir    = hello_readdir,
    .open        = hello_open,
    .read        = hello_read,
};

int main(int argc, char *argv[])
{
    return fuse_main(argc, argv, &hello_oper, NULL);
}

```

```
$ gcc -D_FILE_OFFSET_BITS=64 golffs.c -lfuse -o golffs
$ ./golffs  m     # uses fusermount under the hood
$ ls m
hello.txt
$ cat m/hello.txt
Hello, world
$ fusermount -u m

```

Score of the example: 1974 + 29 (compilation parameters) + 0 (invocation parameters) + 200 (penalty) = 2203

# Answer
> 3 votes
## Perl, 1348 998 846 748 714 683 642 575 520 + strlen("perl -mFuse") + 200 penalty for Fuse.pm = 731 bytes

Was interesting diversion from usual golf challenges. Started life as a version of https://metacpan.org/source/DPATES/Fuse-0.16/examples/example.pl before getting stripped down.

```
%k=('hello.txt'=>{});sub f{$_=shift;s,^/,,;return$_}Fuse::main(mountpoint=>$ARGV[0],getattr=>sub{$c=f(shift);$c=~s,^/,,;$c=~s/^$/\./;return(exists($k{$c})?0:-2,0,$c eq'.'?16877:33261,1,0,0,0,12,0,0,0,1024,0)},getdir=>sub{return(keys%k),0},open=>sub{return(0,[rand()])},statfs=>sub{return0},read=>sub{$c=f(shift);($x,$z,$h)=@_;return-2 unless exists($k{$c});if(!exists($k{$c})){$u=fuse_get_context();return sprintf("pid=0x%08x uid=0x%08x gid=0x%08x\n",@$u{'pid','uid','gid'})}return$z==12?0:substr("Hello, world",$z,$x)})

```

Long lines, but if presented via `fold`, appears as below:

```
# fold foo.pl
%k=('hello.txt'=>{});sub f{$_=shift;s,^/,,;return$_}Fuse::main(mountpoint=>$ARGV
[0],getattr=>sub{$c=f(shift);$c=~s,^/,,;$c=~s/^$/\./;return(exists($k{$c})?0:-2,
0,$c eq'.'?16877:33261,1,0,0,0,12,0,0,0,1024,0)},getdir=>sub{return(keys%k),0},o
pen=>sub{return(0,[rand()])},statfs=>sub{return0},read=>sub{$c=f(shift);($x,$z,$
h)=@_;return-2 unless exists($k{$c});if(!exists($k{$c})){$u=fuse_get_context();r
eturn sprintf("pid=0x%08x uid=0x%08x gid=0x%08x\n",@$u{'pid','uid','gid'})}retur
n$z==12?0:substr("Hello, world",$z,$x)})
#

```

Example use:

```
# perl -mFuse foo.pl m &
[1] 6410
# ls -ld m
drwxr-xr-x 1 root root 0 Jan  1  1970 m
# cd m
# ls -l
total 0
-rwxr-xr-x 1 root root 12 Jan  1  1970 hello.txt
# cat hello.txt
Hello, world#

```

---
Tags: code-golf, file-system
---


title: Fully parenthesize expressions

text:
# Question
Title: Fully parenthesize expressions
Today your challenge is to produce all possible full parenthesizations of an expression.

Your input is a single line of printable ASCII containing one or more terms separated by operators. The input might also contains spaces - you must ignore these. A term is `[a-zA-Z0-9]`, an operator is `[^ ()a-zA-Z0-9]`. You may assume that the input is always valid.

Output all possible ways to fully parenthesize the given expression, separated by newlines with an optional trailing newline.

Do **not**:

* Parenthesize terms - only parenthesize around operators.
* Reorder the terms.
* Output any spaces.

Example input/output:

```
N
N

a * b
(a*b)

x_x_0
(x_(x_0))
((x_x)_0)

a * b|c|d
(a*(b|(c|d)))
(a*((b|c)|d))
((a*b)|(c|d))
((a*(b|c))|d)
(((a*b)|c)|d)

```

---

Smallest code in bytes wins.

# Answer
> 3 votes
# Pyth, 38 bytes

```
L?tbsmmjj@bdk"()"*y<bdy>bhd:1lb2bjy-zd

```

Try it online.

It defines a recursive function that:

* returns the input if its length is 1
* takes all two-splits of the input on operators, and for each split:
    + calls itself recursively on each of the halves
    + takes the Cartesian product of the results of each half
    + joins each result by the operator at the split
    + parenthesizes the joined result
* and finally concatenates the resulting arrays.

The function is then called with the input string with spaces removed and the results are joined by newlines.

# Answer
> 3 votes
# JavaScript (ES6), ~~208~~ 197 bytes

```
s=>((q=x=>x.map((_,i)=>(a=[...x.slice(0,i*=2),p="("+x[i]+x[++i]+x[++i]+")",...x.slice(i+1)],x[i]?a[1]?q(a):r.push(p):0)))([...s.replace(/ /g,o="")],r=[]),r.map((l,i)=>r.indexOf(l)<i?0:o+=l+`
`),o)

```

## Explanation

Uses a recursive function that takes an array of `[ t, o, t, o, etc... ]` and parenthesises each consecutive pair of two terms together like `[ (tot), o, etc... ]` and repeats this process until there is only one element in the array, then filters out the duplicate values.

```
s=>(                                  // s = input string
  (q=x=>                              // q = parenthesise array function
    x.map((_,i)=>(
      a=[                             // a = p with parenthesised pair of terms
        ...x.slice(0,i*=2),
        p="("+x[i]+x[++i]+x[++i]+")", // parenthesise and join 2 terms and an operator
        ...x.slice(i+1)
      ],
      x[i]?a[1]                       // make sure the loop is not over
        ?q(a)                         // check next level of permutations
        :r.push(p)                    // add the permutation to the results
      :0
    ))
  )([...s.replace(/ /g,               // remove spaces and parenthesise all expressions
    o="")],                           // o = output string
    r=[]),                            // r = array of result strings
  r.map(                              // filter out duplicates
    (l,i)=>r.indexOf(l)<i?0:o+=l+`
`
  ),o)                                // return o

```

## Test

```
Input = <input type="text" id="input" value="a * b|c|d" /><button onclick='results.innerHTML=(

s=>((q=x=>x.map((_,i)=>(a=[...x.slice(0,i*=2),p="("+x[i]+x[++i]+x[++i]+")",...x.slice(i+1)],x[i]?a[1]?q(a):r.push(p):0)))([...s.replace(/ /g,o="")],r=[]),r.map((l,i)=>r.indexOf(l)<i?0:o+=l+`
`),o)

)(input.value)'>Go</button><pre id="results"></pre>
```

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