# Question
Title: Convert a repeated decimal to a fraction
This question doesn't need to apply to just terminating decimals - repeating decimals can also be converted to fractions via an algorithm.

Your task is to make a program that takes a repeated decimal as input, and output the corresponding numerator and denominator (in lowest terms) that produces that decimal expansion. Fractions greater than 1 should be represented as improper fractions like `9/5`. You can assume that input will be positive.

The repeated decimal will be given in this format:

```
5.3.87

```

with everything after the second dot repeated, like this:

```
5.3878787878787...

```

Your program will output two integers representing the numerator and denominator, separated by a slash (or the equivalent form in your language if you do not output plain text):

```
889/165

```

Note that terminating decimals will have nothing after the second dot, and decimals with no non-repeating decimal portion will have nothing between the two dots.

### Test cases

These test cases cover all of the required corner cases:

```
0..3 = 1/3
0.0.3 = 1/30
0.00.3 = 1/300
0.6875. = 11/16
1.8. = 9/5
2.. = 2/1
5..09 = 56/11
0.1.6 = 1/6
2..142857 = 15/7
0.01041.6 = 1/96
0.2.283950617 = 37/162
0.000000.1 = 1/9000000
0..9 = 1/1
0.0.9 = 1/10
0.24.9 = 1/4

```

If you wish, you can also assume that fractions without integer parts have nothing to the left of the first dot. You can test that with these optional test cases:

```
.25. = 1/4
.1.6 = 1/6
..09 = 1/11
.. = 0/1

```

# Answer
> 9 votes
# Dyalog APL (~~75~~ ~~73~~ ~~69~~ 68 characters)

Here is another and fifth attempt (most probably my last one); I spent the day trying to write some piece of code shorter than 80 characters and being fully consistent with the rules. This challenge made my day!

I finally got a line of APL made of 75 characters, working with Dyalog APL (but not on the online interpreter page because using the  *execute* function), which is the following one:

```
(N,D)÷D∨N←(⍎'0',1↓I/⍨2=+\P)+(⍎'0',I/⍨2>+\P)×D←D+0=D←⍎'0',⌽2↓⍕¯1+10⊥P←'.'=I← '1.2.3'

```

Of course I could make it a little shorter, but the special cases where one, two or three fields are missing. My code can even handle the `..` input case.

I know that APL is difficult to read, and since people enjoy understanding how a piece of code actually works, here are some explanation. Basically, I compute the final denominator in the variable D and the final numerator in the variable N.

APL is parsed from right to left.

* First, the string is stored in variable I (`I←`).
* Then it is mapped to a vector of booleans indicating where a dot is, and this vector is called P (`P←'.'=`). For instance '1.2.3' will be mapped to 0 1 0 1 0.
* This vector is digits in base 10 (`10⊥`); now '1.2.3' is 1010.
* Then 1 is substracted from this number (either with `1-⍨` or with `¯1+`, here I chose the second). Now '1.2.3' is 1009.
* Then this number is converted to a string (), two initial digits are removed (`2↓`), which makes 09 from our initial '1.2.3' example; the string is reversed ().
* Here, as a special case, I add an initial 0 character in front of the string; it makes me sad to use the four characters `'0',` but I did it for avoiding an error when the second and thirds fields are both empty. The string is converted back to a number () and it is stored in D, which is the denominator except when both last fields are empty, because in such case D is equal to 0.
* The `D←D+0=` piece of code set D to 1 if it is currently null, and now D contains the denominator (before GCD division however).
* This denominator is multiplied (`×`) with the content of the initial string I up to the second dot with `(⍎'0',I/⍨2>+\P)` which starts from P again (0 1 0 1 0 in my example), adds the successive numbers by cumulating them (which makes 0 1 1 2 2 in my example), check which values are smaller than 2 (making the boolean vector 1 1 1 0 0), and taking corresponding characters in I; another 0 is added in front of the string for preventing another trap (if the two initial fields are empty) and the whole is converted to a number.
* The last part of the input string is added to the previous product with `(⍎'0',1↓I/⍨2=+\P)`, which takes P again, adds by cumulating again, check which values are equal to 2 (see previous explanation), takes the characers, removes the first one which is a dot, adds a preventing initial 0 character and converts to a number.
* This product followed with a sum is stored in N which is the numerator.
* Finally the GCD is computed with D∨N and both numbers are divided by this GCD.

*edit:* Here is a fix for 73 characters:

```
(N,D)÷D∨N←(⍎'0',1↓P/I)+(⍎'0',I/⍨~P←2=+\P)×D←D+0=D←⍎'0',⌽2↓⍕¯1+10⊥P←'.'=I←

```

The idea of this hack is computing first the case where cumulative addition has values equal to 2, storing them for later and inverting this bitwise mask for getting the first case; thus computing the next case needs less characters.

*edit:* Here is another fix for 69 characters:

```
(N,D)÷D∨N←(⍎'0',1↓P/I)+(⍎'0',I/⍨~P←2=+\P)×D←⍎'1⌈0',⌽2↓⍕¯1+10⊥P←'.'=I←

```

The idea of this hack is to embed the most complicated special case as APL code in the string to be evaluated (at string to number conversion stage).

*edit:* Here is another fix for 68 characters:

```
(N,D)÷D∨N←(⍎'0',1↓P/I)+(⍎'0',I/⍨~P←2=+\P)×D←⍎'1⌈0',⌽3↓⍕1-10⊥P←'.'=I←

```

The idea of this hack is to replace *adding -1 to the value* for substracting 1 to that value by the operation *substracting that value to 1* then remove later one character more at the beginning (which will be the minus sign).

*edit:* Cosmetic change:

```
(N,D)÷D∨N←(⍎'0',1↓P/I)+(⍎'0',I/⍨~P←2=+\P)×D←1⌈⍎'0',⌽3↓⍕1-10⊥P←'.'=I←

```

No improvement in size, but more satisfied to get the *maximum* function out of the code to be evaluated.

# Answer
> 15 votes
# Perl 6 (~~93~~ ~~101~~ ~~100~~ ~~80~~ ~~68~~ 66 bytes)

```
$/=split ".",get;say ($0+($1+$2/(9 x$2.comb||1))/10**$1.comb).nude

```

The size was increased to handle nothing, instead of just failing. Mouq proposed to use `$/`, so it's now being used, and the code is 20 bytes shorter. Ayiko proposed replacing `/` with , so the code is even shorter (by 12 bytes). Then Mouq proposed replacing `chars` with `comb` (in numeric context, they are identical, because list of characters after conversion to number is number of characters).

Sample output:

```
$ perl6 script.p6
5.3.87
889 165
$ perl6 script.p6
2.0.0
2 1
$ perl6 script.p6
0..3
1 3
$ perl6 script.p6
0.0.3
1 30
$ perl6 script.p6
0.0.0
0 1
$ perl6 script.p6
0.1.6
1 6
$ perl6 script.p6
0.01041.6
1 96
$ perl6 script.p6
0.2.283950617
37 162
$ perl6 script.p6
123.456.789
41111111 333000

```

# Answer
> 6 votes
# J (~~85~~ ~~90~~ 89 chars)

My original function, which was 5 characters shorter than the second, had a couple of bugs: it didn't output integers as "n/1" and it gave the wrong answer on numbers with more than a dozen or so digits. Here's a corrected function in J that also incorporates Eelvex's suggestion to save a character:

```
f=:3 :0
'a t'=.|:(".@('0','x',~]),10x^#);._1'.',y
(,'/'&,)&":/(,%+.)&1+/a%*/\1,0 1-~}.t
)

```

It receives a string and returns a string. Here's a sample session:

```
   f '..'
0/1
   f '0.0.0'
0/1
   f '3..'
3/1
   f '..052631578947368421'
1/19
   f '0.2.283950617'
37/162
   f '.0.103092783505154639175257731958762886597938144329896907216494845360824742268041237113402061855670'
1/97

```

# Answer
> 5 votes
# C, 171

Quite long. Could be further reduced. No `scanf`, which really can't handle it if there aren't any numbers between the dots. No `strtol`. Just number crunching:

```
a,b,c,d,q;main(){while((q=getchar()-48)>-3)q<0?(d=b>0,b+=!b):d?(c=c*10+q,d*=10):(a=a*10+q,b*=10);for(a=a*--d+c,q=b*=d;q>1;a%q+b%q?--q:(a/=q,b/=q));printf("%d/%d\n",a,b);}

```

Test:

```
rfc <<< "2..142857"
15/7

```

# Answer
> 5 votes
# DC (not fully general, shortened to 76 characters)

Not fully general, but please, consider I did it with one of the oldest things in the world:

```
5.3.87 dsaX10r^d1-rla*sasbdscX10r^dlc*rlb*rlb*la+snsdlnld[dSarLa%d0<a]dsax+dldr/rlnr/f

```

**Edit:** I edit my solution; it isn't more general, but a little shorter:

```
sadsbX10r^sclaX10r^dd1-dsdlblc**rla*+dsnrld*dsd[dSarLa%d0<a]dsax+dldr/rlnr/f

```

Use it as:

```
5.3.87 sadsbX10r^sclaX10r^dd1-dsdlblc**rla*+dsnrld*dsd[dSarLa%d0<a]dsax+dldr/rlnr/f

```
* First field isn't required:

```
.1.3 sadsbX10r^sclaX10r^dd1-dsdlblc**rla*+dsnrld*dsd[dSarLa%d0<a]dsax+dldr/rlnr/f

```

is OK.
* Second and thirst field require at least one digit

# Answer
> 4 votes
## Javascript, 203

Way too long, but still fun. Newlines because semicolons are unreadable.

```
s=prompt(b=1).split(".")
P=Math.pow
a=s[0]
c=s[1]
d=P(10,l=c.length)
f=(P(10,s[2].length)-1)*P(10,l)||1
e=s[2]=+s[2]
a=d*a+b*c;b*=d
a=f*a+b*e;b*=f
function g(a,b){return b?g(b,a%b):a}g=g(a,b);a/g+"/"+b/g

```

# Answer
> 3 votes
# J (different method)

Another solution based on a very different method; this time it is fully general; only missing is the 1-denominator when an integer is submitted:

```
   ".((({.~(i.&1)),'+'"_,((":@(10&^)@#,'%~',])@}.@#~~:/\),'+%',((,~(##'9'"_),'%x:0'"_)@}.@#~2:=+/\@]))(=&'.')) '.1.3'
2r15
   ".((({.~(i.&1)),'+'"_,((":@(10&^)@#,'%~',])@}.@#~~:/\),'+%',((,~(##'9'"_),'%x:0'"_)@}.@#~2:=+/\@]))(=&'.')) '.1.'
1r10
   ".((({.~(i.&1)),'+'"_,((":@(10&^)@#,'%~',])@}.@#~~:/\),'+%',((,~(##'9'"_),'%x:0'"_)@}.@#~2:=+/\@]))(=&'.')) '1..'
1
   ".((({.~(i.&1)),'+'"_,((":@(10&^)@#,'%~',])@}.@#~~:/\),'+%',((,~(##'9'"_),'%x:0'"_)@}.@#~2:=+/\@]))(=&'.')) '1..3'
4r3

```

# Answer
> 3 votes
## GolfScript (67 chars)

```
`{'.'/1$=.10\,?@-).!+0@+~}+3,/1$4$*]-1%~;*+*+].~{.@\%.}do;{/}+/'/'@

```

NB This supports empty integer parts.

If the string is of the form `'n.p.q'` then the value is `n + p/E + q/(DE) = ((nD + p)E + q)/DE` where `D = 10^(len p)` and `E = 10^(len q) - 1`, *except* when `len q = 0`, in which case `E = 1` (to avoid division by 0).

Dissection:

```
           # Stack: 'n.p.q'
`{         # Combined with the }+ below this pulls the value into the block
           # Stack: idx 'n.p.q'
    '.'/   # Stack: idx ['n' 'p' 'q']
    1$=    # Stack: idx str   (where str is the indexed element of ['n' 'p' 'q'])
    .10\,? # Stack: idx str 10^(len str)
    @-)    # Stack: str 10^(len str)-idx+1
           #   If idx = 0 we don't care about the top value on the stack
           #   If idx = 1 we compute D = 10^(len 'p')
           #   If idx = 2 we compute E' = 10^(len 'q') - 1
    .!+    # Handle the special case E'=0; note that D is never 0
    0@+~   # Stack: 10^(len str)-idx+1 eval('0'+str) (GolfScript doesn't treat 011 as octal)
}+         # See above
3,/        # Run the block for idx = 0, 1, 2
           # Stack: _ n D p E q
1$4$*      # Stack: _ n D p E q D*E
]-1%~;     # Stack: D*E q E p D n
*+*+       # Stack: D*E q+E*(p+D*n)
].~        # Stack: [denom' num'] denom' num'
{.@\%.}do; # Stack: [denom' num'] gcd
{/}+/      # Stack: denom num
'/'@       # Stack: num '/' denom

```

Online demo which simulates running the program with each of the test inputs, one at a time.

# Answer
> 2 votes
# Ruby - 112

```
x,y,z=gets.chop.split".";y||='0';z||='0';puts((y.to_i+Rational(z.to_i,10**z.length-1))/10**y.length+x.to_i).to_s

```

This is my first experiment with ruby, so feel free to suggest improvements.

```
$ ruby20 % <<< '5.3.87'
889/165
$ ruby20 % <<< '0..3'
1/3
$ ruby20 % <<< '0.0.3'
1/30
$ ruby20 % <<< '0.00.3'
1/300
$ ruby20 % <<< '0.6875.0'
11/16
$ ruby20 % <<< '1.8.0'
9/5
$ ruby20 % <<< '2..'
2/1
$ ruby20 % <<< '..'
0/1

```

# Answer
> 2 votes
# Python

## No libraries - 156 characters

```
_=lambda a,b:b and _(b,a%b)or a;a,b,c=raw_input().split('.');d,e=int(a+b+c)-bool(c)*int(a+b),
(10**len(c)-bool(c))*10**len(b);f=_(d,e);print'%i/%i'%(d/f,e/f)

```

## Using `fractions` \- 127 characters

```
from fractions import*;a,b,c=raw_input().split('.');print Fraction(int(a+b+c)-bool(c)*int(a+b
),(10**len(c)-bool(c))*10**len(b))

```

# Answer
> 2 votes
## Mathematica, 143

As usual, Mathematica offers many high-level functions to do the job, but gives them verbose names.

```
x=StringTake;c=ToExpression;p=s~StringPosition~".";{o,t}=First/@p;u=StringLength@s-t;d=t-o-1;Rationalize@(c@x[s,t-1]+c@x[s,-u]/((10^u)-1)/10^d)

```

Sample output to be added later when I have time.

# Answer
> 2 votes
## Haskell

```
import Data.Ratio
f n=case s '.' n of
    [x,y,z]->(r x)%1+(r y)%(10^(length y))+(r z)%((10^t-1)*(10^(length y)))
        where
            r ""=0
            r n=read n
            t = if length z==0 then 9 else length z
s _ []=[[]]
s n (x:xs) | x==n = []:(s n xs)
           | otherwise = let (l:ls)=s n xs in (x:l):ls

```

# Answer
> 2 votes
## C, 164

This is similar to orion's C solution, even though I did it from scratch. I confess however stealing a number of his optimizations. It is not much shorter, but it handles .25. = 1/4 and 0.000000.1 = 1/9000000.

```
long a,b,c,d,e;main(){while((c=getchar()-48)>-3)c+2?a=a*10+c,b*=10:b?e=a,d=b:(b=1);
b>d?a-=e,b-=d:0;for(d=2;d<=a;)a%d+b%d?d++:(a/=d,b/=d);printf("%ld/%ld\n",a,b);}

```

# Answer
> 2 votes
Two python answers using no libraries. First handles the optional input without a digit before the first . and is 162 chars

```
_=lambda a,b:b and _(b,a%b)or a;i,t,r=raw_input().split(".");b=r!="";d=(10**len(r)-b)*10**len(t);n=int((i+t+r)or 0)-b*int((i+t)or 0);f=_(d,n);print "%i/%i"%(n,d)

```

Second doesn't handle nothing before the first digit but does handle all required inputs correctly and is 150 chars

```
_=lambda a,b:b and _(b,a%b)or a;i,t,r=raw_input().split(".");b=r!="";d=(10**len(r)-b)*10**len(t);n=int(i+t+r)-b*int(i+t);f=_(d,n);print "%i/%i"%(n,d)

```

# Answer
> 2 votes
# JavaScript (ECMASCript 6) ~~180~~ 175

```
G=(a,d)=>d?G(d,a%d):a;P=a=>+("1e"+a);L=a=>a.length;f=prompt().split(".");B=P(L(b=f[1]));D=P(L(b)+L(c=f[2]))-P(L(b))||1;alert((m=(f[0]+b||0)*D+B*(c||0))/(g=G(m,n=B*D))+"/"+n/g)

```

While it isn't a clear winner for the 300 bounty... this is the shortest I can come up with:

* *Changes from previous version:* some slight alteration to logic, and changes to the Power `P` function by altering it to `+("1e"+a)` instead of `Math.pow(10,a)` thereby saving a few more characters...

# Answer
> 1 votes
# Mathematica 175

```
f@i_:=
If[IntegerQ[g=FromDigits[Map[IntegerDigits@ToExpression@#&,StringSplit[i,"."]/.""-> {}]
/.{a_,b_,c_}:> {{Sequence@@Join[a,b],c},Length@a}]],HoldForm[Evaluate@g]/HoldForm@1,g]

```

Most of the routine goes to massaging the input. Approximately 50 chars went to handling integers.

---

## Examples

```
f["7801.098.765"]

```

More examples:

```
TableForm[
 Partition[{#, f[#]} & /@ {"19..87", "19.3.87", "5.3.87", "0.0.3", "0..3", "0.2.283950617",
"123.456.789", "6666.7777.8888", "2.0.0","0.0.0"}, 5], TableSpacing -> {5, 5}]

```

---

## How it would normally be accomplished in Mathematica

`FromDigits` can obtain a fraction directly from a recurring repeating decimal, provided that the input is of a particular form. Integers are displayed as integers.

```
z={{{1, 9, {8, 7}}, 2}, {{1, 9, 3, {8, 7}}, 2}, {{5, 3, {8, 7}}, 1}, {{{3}}, -1}, {{{3}}, 0},
{{2, {2, 8, 3, 9, 5, 0, 6, 1, 7}}, 0}, {{1, 2, 3, 4, 5, 6, {7, 8, 9}}, 3},
{{6, 6, 6, 6, 7, 7, 7, 7, {8}}, 4}, {{2}, 1}, {{0}, 1}}

FromDigits/@z

```

# Answer
> 1 votes
# J (96 characters)

I don't use the slash symbol as a separator (but solution in Mathematica doesn't either since it uses a graphical representation which is better anyway); in J language the fraction is displayed with `r` instead as `/`:

```
   (((-.@]#[)((".@[%#@[(10x&^)@-{.@])+({.@](10x&^)@-#@[)*<:@{:@](".%<:@(10x&^)@#)@}.[)I.@])(=&'.')) '1..3'
4r3
   (((-.@]#[)((".@[%#@[(10x&^)@-{.@])+({.@](10x&^)@-#@[)*<:@{:@](".%<:@(10x&^)@#)@}.[)I.@])(=&'.')) '123.456.789'
41111111r333000

```

# Answer
> 1 votes
# APL (not fully general)

Not fully general (like my solution for dc); works with Dyalog APL (but not on the online version of Dyalog APL, not sure why):

```
(R,F)÷(F←D×N)∨R←(⍎C)+D×(⍎I/⍨2>+\P)×N←10*¯1++/≠\P⊣D←¯1+10*⍴C←1↓I/⍨2=+\P←'.'=I← '123.456.789'

```

The first field is optional, but at least one digit is required for both other fields.

# Answer
> 1 votes
# JavaScript (189)

```
i=prompt().split(".");a=i[0];b=i[1];c=i[2];B=b.length;p=Math.pow;n=a+b+c-(a+b);d=p(10,B+c.length)-p(10,B);f=1;while(f){f=0;for(i=2;i<=n;i++)if(n%i==0&&d%i==0){n/=i;d/=i;f=1}};alert(n+"/"+d)

```

### Example:

Input:

```
5.3.87

```

Output:

```
889/165

```

# Answer
> 1 votes
# C (420 characters as written; less after removing unnecessary whitespace)

Note that this assumes 64-bit `long` (e.g. 64 bit Linux); it will fail for the test case `0.2.283950617` on systems using 32-bit `long`. This can be fixed at the cost of some characters by changing the type to `long long` and changing the `printf` format string accordingly.

```
#include <stdio.h>

long d[3], n[3], i;

int main(int c, char** v)
{
  while (c = *v[1]++)
    switch(c)
    {
    case '.':
      n[++i] = 1;
      break;
    default:
      d[i] = 10 * d[i] + c - '0';
      n[i] *= 10;
    }

  n[2] -= n[2] != 1;

  while (i--)
    d[2] += d[i] * n[i+1], n[i]*=n[i+1];

  i = d[2];
  *n = n[1];

  while (i)
    *d = i, i = *n%i, *n = *d;
  printf("%ld/%ld\n", d[2]/ *n, n[1]/ *n);
}

```

# Answer
> -3 votes
## GTB, 81

```
`_:s;_,1,l?_)-S;_,"."
s;A;,1,S;_,".")-1
s;_,1+S;_,"."),l?_)-S;_,"."))→_
x?A;+_)►Frac

```

**Example**

```
?3.25.
            13/4

```

---
Tags: code-golf, rational-numbers
---


title: Recognizing Repetition in strings

text:
# Question
Title: Recognizing Repetition in strings
Create a program which gets an input from the user and tells the user what repetitions exist in the it. A few examples of inputs the user could give and outputs they should get:

> Input: 112211221122
>
> Output: 1122 * 3

Or:

> Input: 123123
>
> Output: 123 * 2

Or:

> Input: 1234
>
> Output: No repetitions found!

Tiebreaker: if your code can recognize more than one repetition:

> Input: 123123456456
>
> Output: 123 * 2, 456 * 2

Then you win if you are tied for 1st place with someone's code who doesn't recognize more than one repetition.

If your code requires a limit on the repetition length, it should be able to recognize repetitions at least 4 characters long. This is a code-golf question, so the shortest code wins (but please explain the code in your answer)

# Answer
> 2 votes
# Perl, 74 (73 + 1) bytes

* Assumes `-n` flag (+1 byte).
* `say` is a feature of version 5.10 and needs to be enabled. This can be done by flag `-M5.010` or easier with `-E` instead of `-e`. Therefore I follow the other Perl answer in the calculation method of the costs.
* It also reports repetitions as long as they do not overlap.

```
s/(.+)(?{$i=1})(\1(?{$i++}))+/say"$1 * $i"/ge||say"No repetitions found!"

```

## Usage and tests

```
echo 112211221122 | perl -nE 's/(.+)(?{$i=1})(\1(?{$i++}))+/say"$1 * $i"/ge||say"No repetitions found!"'
1122 * 3

```

```
echo 123123 | perl -nE 's/(.+)(?{$i=1})(\1(?{$i++}))+/say"$1 * $i"/ge||say"No repetitions found!"'
123 * 2

```

```
echo 1234 | perl -nE 's/(.+)(?{$i=1})(\1(?{$i++}))+/say"$1 * $i"/ge||say"No repetitions found!"'
No repetitions found!

```

```
echo 123123456456 | perl -nE 's/(.+)(?{$i=1})(\1(?{$i++}))+/say"$1 * $i"/ge||say"No repetitions found!"'
123 * 2
456 * 2

```

## Ungolfed with comments

```
s/
    (.+)              # catches the repeat unit
    (?{ $i=1 })       # initialize counter $1 with 1
    (
        \1            # next repetition
        (?{ $i++ })   # increase counter
    )+                # repeat unit must appear at least twice
/
    say "$1 * $i"     # print result as a side effect of the replacement;
                      # "say" adds a new line at the end
/gex                  # g: global, find all repetitions (without overlap)
                      # e: replacement text is executed as code
                      # x: only ungolfed: readability and comments
    ||                # s/// returns the number of replacements,
                      # this is zero, if no repetitions could be found
    say "No repetitions found!"

```

# Answer
> 1 votes
# Perl (85 + 1 = 86 bytes)

Assumes `-n` flag (+1 byte) and `-M5.010` (free).

```
length>4&&($i=say"$1 x ",length($&)/length$1)while/(.+)\1+/g}{$i||say"No repetitions found!"

```

Sample:

```
~ $ echo 123123456456 | perl -nE 'length>4&&($i=say"$1 x ",length($&)/length$1)while/(.+)\1+/g}{$i||say"No patterns found!"'
123 x 2
456 x 2
~ $ echo 112211221122 | perl -nE 'length>4&&($i=say"$1 x ",length($&)/length$1)while/(.+)\1+/g}{$i||say"No patterns found!"'
1122 x 3

```

# Answer
> 1 votes
# JavaScript, 81

Assumes input is stored in variable `s`. Run this in a console.

```
x=s.match(/^(.+?)\1+$/)
x?x[1]+" * "+s.length/x[1].length:"No repetitions found!"

```

Does not support multiple repetition, but that is portrayed as optional.

Explanation: regex `/^(.+?)\1+$/` matches one or more characters and then those characters repeated one or more times. `?` is used to make the `+` lazy, so it works for `123123123123`.

# Answer
> 0 votes
# APL 71 characters

```
(1+B<S)⌷(⊂'no repetitions found!'),⊂W[B],S÷B←1⍳⍨∧/¨V=¨S⍴¨W←V↑⍨¨⍳S←⍴⊃V←⊂

```

Example:

```
(1+B<S)⌷(⊂'no repetitions found!'),⊂W[B],S÷B←1⍳⍨∧/¨V=¨S⍴¨W←V↑⍨¨⍳S←⍴⊃V←⊂ '123123'

```

Try it with my online compiled to javascript version of GNU APL: here.

---
Tags: code-golf
---


# Question
Title: Make the most useful program within 100 characters
In this task, you are allowed make an useful program to do anything you can write within 100 characters. You are allowed to use less characters, but not more.

Rules, just to protect from standard loopholes that are no longer funny:

1. Your program cannot access the internet, unless it really has to. For example, the program which shows the most upvoted question on this website may use the Internet to check this question. However, it's not allowed to browse the Internet in order to find its real source and run it.
2. Your program cannot be an interpreter for the language it was written in. However, Brainfuck interpreter in non-Brainfuck language would be fine.
3. Your program cannot execute external programs that does exactly what your program does. For example, you cannot run `vim`, and claim that your program is `vim` implementation.
4. Your program cannot be dangerous for the computer it's being ran on and other computers. You aren't allowed to write program like `rmdir /` (the example here intentionally doesn't work, don't fix it), and claim it's an useful program to remove all files on the computer.
5. Your program may be as slow as you want, and use as much resources as you want, as long you can prove it does what it meant to do.
6. You aren't allowed to make language specifically for this task. However, you are allowed to make interpreter for your invented language in some other programming language.

# Answer
## C - 47 bytes

The following program outputs every document ever written in human history, along with every document that will ever be written and loads of interesting texts that no human will ever come up with (along with a "little bit" of garbage in between). Just give it some time. Moreover, every time you run it, it will output different texts first! If *that's* not useful! (And all of that within half the character limit!)

```
main(){srand(time(0));while(1)putchar(rand());}

```

If you don't care about it outputting something else each time, you only need **41 bytes**!

```
main(){srand(0);while(1)putchar(rand());}

```

Not quite C99 conform, but it compiles smoothly with `gcc.exe (GCC) 4.7.0 20111220`.

The rules state

> Your program may be as slow as you want, and use as much resources as you want, as long you can prove it does what it meant to do.

No problem.

Some things, this program will output:

* a solution to every Millennium Problem
* tomorrow's newspaper articles
* the complete works of Shakespeare's (of course)
* your darkest secret
* all the other answers to this question

> Not really, because (as ace correctly mentioned in the comment), **rand()** is only a pseudo-random generator, that will wrap around at some point - probably way too early to produce a lot of meaningful texts. But I doubt that getting data from a true (hardware) random number generator is remotely possible within 100 characters. I'll leave this here for the fun of it, though.

As Dennis notes, the randomness of the the algorithm, could be somewhat improved (within the character limit), by using `rand()^rand()>>16` instead of `rand()`.
> 26 votes

# Answer
# BBC BASIC, 84 chars

```
MODE 6:INPUT T,A,B,A$,B$:FOR X=0 TO 1279:A=A+EVAL(A$):B=B+EVAL(B$):DRAW X,A+500:NEXT

```

**Plots the solutions to first and second order differential equations.**

Takes as user input:

```
Title (does nothing)
Start value for A (plotted value)
Start value for B (not plotted)
Expression for dA/dX
Expression for dB/dX

```

Inspired by a differential equation solving software called Polymath which I used when studying to be a chemical engineer. We would input different equations for reactants and products and see how the whole reaction system changed over time. A very simple software (not much more complex than this) but much more convenient for this purpose than Excel. Unfortunately I cannot do a complete clone of Polymath in 100 chars.
> 18 votes

# Answer
# Mathematica 76

This program constructs an applet that displays information regarding various properties for any of 240 countries. It opens with information about the adult population of Afghanistan. The user may change the country and property settings through drop-down lists.

Mathematica interoperates smoothly with WolframAlpha.
For this reason I believe the submission meets requirement #1 of the challenge: "Your program cannot access the internet, ***unless it really has to***".

This rather modest applet simply makes use of existing functionality in the Mathematica language. A short video provides some additional information about the applet.

```
d = CountryData; Manipulate[WolframAlpha[p <> " " <> c], {p, d["Properties"]}, {c, d[]}]

```

---

Below is a list of the first 20 (of 223) properties related to countries. With a additional programming one can obtain additional information regarding countries and analyze this information in Mathematica.

```
CountryData["Properties"][[;; 20]]

```

> {"AdultPopulation", "AgriculturalProducts", "AgriculturalValueAdded", "Airports", "AlternateNames", "AlternateStandardNames", "AMRadioStations", "AnnualBirths", "AnnualDeaths", "AnnualHIVAIDSDeaths", "ArableLandArea", "ArableLandFraction", "Area", "BirthRateFraction", "BorderingCountries", "BordersLengths", "BoundaryLength", "CallingCode", "CapitalCity", "CapitalLocation"}
> 10 votes

# Answer
# bash, 100 bytes

```
head -c${1--1} /dev/zero |
openssl enc -aes-128-ctr -pass file:/dev/random 2>/dev/null |
tail -c+17

```

This script prints a cryptographically secure stream of bytes. It takes an optional argument specifying the number of bytes it should print. By default, the output will be infinite.

Useful in cases where reading from `/dev/urandom` is just too darn slow.

### Benchmark

```
$ time head -c 1G /dev/urandom > /dev/null
Real    59.75
User    0.03
Sys     59.68
$ time random 1G > /dev/null
Real    0.68
User    0.64
Sys     0.86

```

This script generates up to 1.5 GiB per second on my i7-3770.

In contrast, reading from `/dev/urandom` manages to generate barely 1 GiB **per minute**.

### How it works

* `head -c${1--1} /dev/zero` outputs the specified amount of zero bytes. If no amount is specified, `${1--1}` equals -1 and *head* outputs an infinite amount.
* `openssl enc -aes-128-ctr -pass file:/dev/random` uses AES-128 in counter mode to encrypt the zero bytes, reading the password from `/dev/random`.
* `tail -c+17` gets rid of the output's 16-byte header.
> 9 votes

# Answer
## Javascript

Solve any equation (well, not all, but should work with common functions...)

```
r=s=>{for(x=e=a=1e-7;a;x-=e*a/(eval(s.replace(/x/g,x+e))-a))a=eval(s.replace(/x/g,x));return x}

```

Without ES6 (105 chars):

```
function r(s){for(x=e=a=1e-7;a;x-=e*a/(eval(s.replace(/x/g,x+e))-a))a=eval(s.replace(/x/g,x));return x}

```

Just give the left side of the equation assuming that the right side is zero.

Example :

* `r("x*x-9")` returns `3`
* `r("Math.sin(x)-1")` returns `1.5707963394347828` (pi/2)
* `r("Math.pow(2,x)-512")` returns `9`

*Warning :* can diverge on some functions (or if there is no solution) and freeze your browser tab, or return NaN.
> 7 votes

# Answer
# C - 99 characters

```
i;main(int c,char**a){for(a+=2;1+(c=getchar());)putchar(c+(**(a-1)-69?1:-1)**(*a+i++%strlen(*a)));}

```

This program allows encryption and decryption of any kind of data.

**Usage**

First... compile it!

```
gcc crypto.c crypto

```

If you want to encrypt the contents of `mypreciousdata.txt` with the key `mysecretkey`, and store the result in `myprotecteddata.txt`:

```
cat mypreciousdata.txt | ./crypto E mysecretkey > myprotecteddata.txt

```

Now, if you want to retrieve the decoded contents of `myprotecteddata.txt`:

```
cat myprotecteddata.txt | ./crypto D mysecretkey > mypreciousdata.txt

```

The longer the key, the safer!

**Explanation**

Please find the expanded and commented code below:

```
int main(int argc, char** argv)
{
    // retrieve the first argument passed to the program (action)
    char action = argv[1][0];

    // retrieve the second argument passed to the program (key)
    char* key = argv[2];

    // initialize character position in the key
    int i = 0;

    // initialize the current input character
    char c = 0;

    // loop until we reach the end of input
    while (c != -1){
        // get a character from stdin
        c = getchar();
        if (action == 'E'){
            // encode the current character
            putchar(c + key[i]);
        } else{
            // decode the current character
            putchar(c - key[i]);
        }
        // increment the position in the key, without overflow
        i = (i + 1) % strlen(key);
    }
}

```
> 6 votes

# Answer
# GolfScript

I managed to squeeze this into exactly 100 characters!

```
{{}/]{97-}%}:b~:|;"etaoinshrdlcumwfgypbvkjxqz"b:f,:&,{:x[|{&x-+&%f?}%{+}*\]}%$0=1=:x|{&x-+&%97+}%''+

```

It takes input of ROT-n encrypted text and outputs the text decoded. (Taken from here.) For example, when given the input `pmttwxmwxtmwnxzwoziuuqvoxchhtmakwlmowtnabiksmfkpivom`, the output is `8hellopeopleofprogrammingpuzzlescodegolfstackexchange`.
> 5 votes

# Answer
### JavaScript

To generate a unique id in javascript
```
Math.random().toString(30).slice(2);

```

Produces something like : `'h9d2f4aniimma7h1d3pbffi0foi8d3mf'`

strings of 30-32 alpha-numeric characters

```
Math.random().toString(36).slice(2)

```

Produces something like : `'uq2sze67hsacq5mi'`

Strings of length 14-16 .
> 5 votes

# Answer
# C++ 57

```
#include<iostream>
#include<conio.h>
int main(){std::cout<<getch();}

```

This program takes a character input and outputs its ASCII value.
> 4 votes

# Answer
## Fortran - 85 bytes

```
l=0;read(*,*)n;do while(n>0);i=mod(n,10);l=l+i;n=n/10;enddo;print*,"digit sum=",l;end

```

Reads in a number and prints out the sum of the digits. Useful for Project Euler problems.
> 3 votes

---
Tags: popularity-contest
---


title: My Robot Has Escaped the Lab!

text:
# Question
Title: My Robot Has Escaped the Lab!
My robot has short circuited somehow and randomly run off somewhere from my lab!

Luckily, whenever he does this, his shut-down sequence initiates, giving him enough time to randomly turn and run in the direction its facing for five rounds before he switches off. His gyro and accelerometer functions are still relaying the data back to the lab while he is still on.

The data will always come in the form of five sets of two numbers, for example.

`12:234,-135:47,-68:230,140:324,127,87`

Your mission, golfers is to a) simulate the robot's frantic run and turn sequence by displaying five sets of numbers in the form of `a1:d1,a2:d2,a3:d3,a4:d4,a5:d5` where `a`(n) is the clockwise angle (in degrees) such that `-179<=a<=+180` that the robot will turn from its current heading (initially it is at zero heading before it runs amok and turns for the first time), and `d`(n) is the distance in feet it has run before the next heading change which is such that `0<=d<=500` feet; and b) A calculated heading from the lab (which is also facing a heading of zero), distance in feet (accuracy up to 3 decimal places is strongly encouraged, -5 bytes if you do), and the orientation heading (in degrees) of where my robot it is facing when it has switched off.

Easy example:

```
Data: 0:1,45:1,90:1,90:1,90:1
Heading: 0
Distance: 1
Orientation: -45

```

The random turns and distances are just that, random. No set values are to be hard coded, we must see the randomness in action within the code.

Restrictions to randomness: No clock or date based references, we need to see a native `random` reference within the code. Whenever you run this code, the randomness must present itself with a possibility of showing 1 of 360 possible angles of turning with each turn-run round. So the robot may turn -36 degrees at one turn and may turn +157 degrees the next, followed by another turn of +2 degrees by another turn of -116 degrees and a final turn of +42 degrees on the final turn. At least 360 distinct values must be possible (between -179 to +180 degrees inclusive) with each random angle generation.

Restrictions to distance run: Similarly set, there are 501 possible distances the robot can run, (between 0 and 500 feet inclusive), so I expect the randomness to also be available when determining the robot's running distance. The robot could theoretically run 45, 117, 364, 27 and 6 feet with each of its respective rounds...

The data fed to you will always be in integer values... the robot will turn in integer ranges of degrees, and will run in integer ranges of distance. The output values however, will be floats...

This is code-golf. Shortest code wins... Now go find my robot!

PS: In reference to my "Accuracy up to 3 decimal places", if you can provide the heading (in degrees, to a MINIMUM of 3 decimal places) and a distance in feet (also accurate also to a MINIMUM 3 decimal places) you will get a -5 byte bonus).

# Answer
> 2 votes
# Perl 6: ~~188~~ 184 characters - 5 = 180 points

```
$_=((-179..180).pick=>(^501).pick)xx 5;my$o;$/=([+] .map:{unpolar .value,$o+=.key/($!=180/pi)}).polar;say "Data: {.fmt("%d:%d",",")}
Heading: {$1*$!}
Distance: $0
Orientation: {$o*$!}"

```

Golf with whitespace:

```
$_ = ((-179..180).pick => (^501).pick) xx 5;
my $o;
$/ = ([+] .map: {
    unpolar .value, $o += .key / ($!=180/pi)
}).polar;
say "Data: {.fmt("%d:%d", ",")}
Heading: {$1*$!}
Distance: $0
Orientation: {$o*$!}"

```

Ungolfed:

```
my &postfix:<°>  = */180*pi; # Deg → Rad
my &postfix:<㎭> = */pi*180; # Rad → Deg

my @data = ((-179..180).pick => (0..500).pick) xx 5;
say "Data: @data.fmt("%d:%d", ",")";

my $cum-angle = 0;
my $complex = [+] @data.map: {unpolar .value, $cum-angle += .key°}
my ($dist, $ang) = $complex.polar;

say "Heading: ",     $ang.㎭;
say "Distance: ",    $dist;
say "Orientation: ", $cum-angle.㎭;

```

This turns the data into complex numbers with `unpolar`, puts the sum of them into `$complex`, and then gets the polar coordinates as `$dist`, `$ang`.

The cumulative angle, `$cum-angle` is collected because the angles are relative to the robot as it moves through the lab and because we need the final angle of the robot in our output.

Sample output:

```
Data: -73:230,-144:453,-151:274,-52:232,88:322
Heading: -5.33408558001246
Distance: 378.74631610127
Orientation: -332

```

The only real trick the golf uses is that it (mis)uses all 3 of Perl 6's special variables to good effect:

* `$!` is used for radians ↔ degrees
* `$_` holds the data, and anything that looks like a lonely `.method()` actually means `$_.method()` (except inside the `map {…}` block, where `$_` actually takes on the value of the number pairs that make up the data)
* `$/` holds what is in the ungolfed version `($dist, $ang)`. `$0` and `$1` actually mean `$/[0]`, i.e., `$dist`, and `$/[1]`, i.e., `$ang`

# Answer
> 10 votes
# Ruby, ~~274~~ ~~252~~ ~~249~~ ~~245~~ ~~214~~ ~~211~~ ~~207~~ ~~204~~ 202 characters (-5 = 197)

How did PHP beat Ruby in char count?! \>:O Must find some way to golf more...

Edit: I beat the PHP answer, but the user who wrote it helped me do it! Go upvote him; he deserves it :-P

Another edit: Gah! He passed me again! You are a very worthy opponent, @MathieuRodic; congratulations, I have to let you win ;-)

```
P=(M=Math)::PI
puts"Data: #{([x=y=a=0]*5).map{a+=o=rand -179..e=180;x+=M.sin(b=a*P/e)*d=rand 500;y+=d*M.cos b;"#{o}:#{d}"}*?,}
Heading: #{M.atan(y/x)/P*-e+90}
Distance: #{M.hypot x,y}
Orientation: #{a}"

```

Ungolfed code (and ~~slightly~~ much older version):

```
data = Array.new(5) { [rand(-179..180), rand(0..500)] }
puts "Data: #{data.map{|x|"#{x[0]}:#{x[1]}"}.join ?,}"
x, y, a = [0] * 3
data.each do |o, d|
    a += o
    x += Math.sin(a * Math::PI / 180) * d
    y += Math.cos(a * Math::PI / 180) * d
end
puts "Heading: #{Math.atan(y / x) / Math::PI * -180 + 90}
Distance: #{Math.sqrt(x * x + y * y)}
Orientation: #{a}"

```

Sample output:

```
c:\a\ruby>robotgolf
Data: 94:26,175:332,14:390,159:448,-45:20
Heading: 124.52305879195005
Distance: 279.5742334385328
Orientation: 397

```

# Answer
> 5 votes
# PHP - 238 232 221 212 203 199 characters

```
for(;$i<5;$h+=$a=rand(-179,181),$x+=cos($b=$a*$k=M_PI/180)*$l=rand(0,501),$y+=$l*sin($b),$d.=($i++?",":"")."$a:$l");echo"Data: $d
Heading: $h
Distance: ".hypot($x,$y)."
Orientation: ".atan2($y,$x)/$k

```

(test it here: http://ideone.com/dNZnKX)

**Non-golfed version:**

```
$k = M_PI / 180;
$h = $x = $y = 0;
$d = "";

for ($i=5; $i--;){
    $h += $a = rand(-179,181);
    $x += ($l = rand(0, 501)) * cos($b = $k * $a);
    $y += $l * sin($b);
    $d .= ($d ? "," : "") . "$a:$l";
}

echo "Data: $d\nHeading: $h\nDistance: " . sqrt($x*$x + $y*$y) ."\nOrientation: " . atan2($y, $x)/$k . "\n";

```

(test it here: http://ideone.com/1HzWH7)

# Answer
> 3 votes
# Python - 264 259 256 258 - 5 = 253 characters

```
from math import*;import random as R;r,k,d=R.randint,pi/180,[];h=x=y=0;exec"a,l=r(-179,180),r(0,500);d+=[`a`+':'+`l`];h+=a;x+=l*cos(k*a);y+=l*sin(k*a);"*5;print('Data: %s\nHeading: %d\nDistance: %.3f\nOrientation: %d'%(','.join(d),h,hypot(x,y),atan2(y,x)/k))

```

(test it at http://ideone.com/FicW6e)

**Ungolfed version:**

```
from math import *
from random import randrange as r

k = pi / 180
h = x = y = 0
d = []
for i in range(5):
    a = r(-179,181)
    l = r(501)
    d += ['%d:%d' % (a, l)]
    h += a
    x += l * cos(k * a)
    y += l * sin(k * a)

print('Data: %s\nHeading: %d\nDistance: %.3f\nOrientation: %f' % (','.join(d), h, sqrt(x*x+y*y), atan2(y,x)/k))

```

(test it at http://ideone.com/O3PP7T)

NB: many answers include *-5* in their title, while their program does not represent the distance with *accuracy up to 3 decimal places*...

# Answer
> 1 votes
# Python 301-5=296

```
from math import*
r=__import__("random").randint
o=x=y=0
s=[]
for i in[0]*5:a=r(-179,180);d=r(0,500);o+=a;o+=180*((o<-179)-(o>180));n=pi*o/180;x+=d*cos(n);y+=d*sin(n);s+=["%d:%d"%(a,d)]
print"Data: "+",".join(s)+"\nHeading: %d"%degrees(atan(y/x))+"\nDistance: %f"%sqrt(x**2+y**2)+"\nOrientation: %d"%o

```

Nothing too fancy here, rather verbose. This is one problem for which I am not happy that python's trig functions work in radians.

```
> python robot.py
Data: 17:469,110:383,-146:240,-78:493,62:1
Heading: -17
Distance: 405.435748
Orientation: -35
> python robot.py
Data: -119:363,89:217,129:321,10:159,-56:109
Heading: -79
Distance: 130.754395
Orientation: 53

```

# Answer
> 0 votes
## Python 2 = ~~376~~ 319 characters (-5 for distance=314)

```
import random,math
h=x=y=0
for i in range(5):
    a=random.randint(-179,180)
    d=random.randint(0,500)
    print '%d:%d,'%(a,d),
    h+=a
    if h>180:
        h-=360
    x+=d*math.cos(h)
    y+=d*math.sin(h)
t=math.sqrt(x**2+y**2)
o=math.atan2(y,x)
print
print 'Heading: %d\nDistance: %3f\nOrientation: %d' % (h,t,o)

```

sample output

```
-141:245, 56:355, 145:223, -10:80, -38:253,
Heading: 12
Distance: 559.031404
Orientation: -2

```

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


title: So obviously, P = NP

text:
# Question
Title: So obviously, P = NP
SAT is the problem of determining whether a boolean expression can be made true. For example, (A) can be made true by setting A=TRUE, but (A && !A) can never be true. This problem is known to be NP-complete. See Boolean Satisfiability.

Your task is to write a program for SAT that executes in polynomial time, but may not solve all cases.

For some examples, the reason it is not *really* polynomial could be because:

1. There is an edge case that is not obvious but has a poor runtime
2. The algorithm actually fails to solve the problem in some unexpected case
3. Some feature of the programming language you are using actually has a longer runtime than you would reasonably expect it to have
4. Your code actually does something totally different from what it looks like it's doing

You may use any programming language (or combination of languages) you wish. You do not need to provide a formal proof of your algorithm's complexity, but you should at least provide an explanation.

The primary criteria for judging should be how convincing the code is.

This is a popularity contest, so the highest rated answer in a week wins.

# Answer
> 234 votes
## C#

> Your task is to write a program for SAT that appears to execute in polynomial time.

"Appears" is unnecessary. I can write a program that really does execute in polynomial time to solve SAT problems. This is quite straightforward in fact.

> MEGA BONUS: If you write a SAT-solver that actually executes in polynomial time, you get a million dollars! But please use a spoiler tag anyway, so others can wonder about it.

Awesome. Please send me the million bucks. **Seriously, I have a program right here that will solve SAT with polynomial runtime.**

Let me start by stating that I'm going to solve a variation on the SAT problem. I'm going to demonstrate how to write a program that *exhibits the unique solution of any 3-SAT problem*. The valuation of each Boolean variable has to be *unique* for my solver to work.

We begin by declaring a few simple helper methods and types:

```
class MainClass
{
    class T { }
    class F { }
    delegate void DT(T t);
    delegate void DF(F f);
    static void M(string name, DT dt)
    {
        System.Console.WriteLine(name + ": true");
        dt(new T());
    }
    static void M(string name, DF df)
    {
        System.Console.WriteLine(name + ": false");
        df(new F());
    }
    static T Or(T a1, T a2, T a3) { return new T(); }
    static T Or(T a1, T a2, F a3) { return new T(); }
    static T Or(T a1, F a2, T a3) { return new T(); }
    static T Or(T a1, F a2, F a3) { return new T(); }
    static T Or(F a1, T a2, T a3) { return new T(); }
    static T Or(F a1, T a2, F a3) { return new T(); }
    static T Or(F a1, F a2, T a3) { return new T(); }
    static F Or(F a1, F a2, F a3) { return new F(); }
    static T And(T a1, T a2) { return new T(); }
    static F And(T a1, F a2) { return new F(); }
    static F And(F a1, T a2) { return new F(); }
    static F And(F a1, F a2) { return new F(); }
    static F Not(T a) { return new F(); }
    static T Not(F a) { return new T(); }
    static void MustBeT(T t) { }

```

Now let's pick a 3-SAT problem to solve. Let's say

```
(!x3) &
(!x1) &
(x1 | x2 | x1) &
(x2 | x3 | x2)

```

Let's parenthesize that a bit more.

```
(!x3) & (
    (!x1) & (
        (x1 | x2 | x1) &
        (x2 | x3 | x2)))

```

We encode that like this:

```
static void Main()
{
    M("x1", x1 => M("x2", x2 => M("x3", x3 => MustBeT(
      And(
        Not(x3),
        And(
          Not(x1),
          And(
            Or(x1, x2, x1),
            Or(x2, x3, x2))))))));
}

```

And sure enough when we run the program, we get a solution to 3-SAT in polynomial time. In fact the runtime is **linear in the size of the problem**!

```
x1: false
x2: true
x3: false

```

> You said polynomial **runtime**. You said nothing about polynomial **compile time**. This program forces the C# compiler to try all possible type combinations for x1, x2 and x3, and choose the unique one that exhibits no type errors. The compiler does all the work, so the runtime doesn't have to. I first exhibited this interesting techinque on my blog in 2007: http://blogs.msdn.com/b/ericlippert/archive/2007/03/28/lambda-expressions-vs-anonymous-methods-part-five.aspx Note that of course this example shows that overload resolution in C# is at least NP-HARD. Whether it is NP-HARD or actually *undecidable* depends on certain subtle details in how type convertibility works in the presence of generic contravariance, but that's a subject for another day.

# Answer
> 166 votes
# Multi-language (1 byte)

The following program, valid in many languages, mostly functional and esoteric, will give the correct answer for a large number of SAT problems and has constant complexity (!!!):

```
0

```

Amazingly, the next program will give the correct answer for all remaining problems, and has the same complexity. So you just need to pick the right program, and you'll have the correct answer in all cases!

```
1

```

# Answer
> 34 votes
# JavaScript

By using iterated non-determinism, SAT can be solved in polynomial time!

```
function isSatisfiable(bools, expr) {
    function verify() {
        var values = {};
        for(var i = 0; i < bools.length; i++) {
            values[bools[i]] = nonDeterministicValue();
        }
        with(values) {
            return eval(expr);
        }
    }
    function nonDeterministicValue() {
        return Math.random() < 0.5 ? !0 : !1;
    }

    for(var i = 0; i < 1000; i++) {
        if(verify(bools, expr)) return true;
    }
    return false;
}

```

Example usage:

```
isSatisfiable(["a", "b"], "a && !a || b && !b") //returns 'false'

```

> This algorithm just checks given boolean formula a thousand times with random inputs. Almost always works for small inputs, but is less reliable when more variables are introduced.

By the way, I'm proud that I had the opportunity to utilize two of the most underused features of JavaScript right next to each other: `eval` and `with`.

# Answer
> 32 votes
## Mathematica + Quantum Computing

You may not know that Mathematica comes with quantum computer aboard

```
Needs["Quantum`Computing`"];

```

Quantum Adiabatic Commputing encodes a problem to be solved in a Hamiltonian (energy operator) in such way that its state of minimum energy ("ground state") represents the solution. Therefore adiabatic evolution of a quantum system to the ground state of the Hamiltonian and subsequent measurement gives the solution to the problem.

We define a subhamiltonian that corresponds to `||` parts of the expression, with appropriate combination of Pauli operators for variables and its negation

Where for expression like this

```
expr = (! x3) && (! x1) && (x1 || x2 || x1) && (x2 || x3 || x2);

```

the argument should look like

```
{{{1, x3}}, {{1, x1}}, {{0, x1}, {0, x2}, {0, x1}}, {{0, x2}, {0, x3}, {0, x2}}}

```

Here is the code to construct such argument from bool expression:

```
arg = expr /. {And -> List, Or -> List, x_Symbol :> {0, x},
    Not[x_Symbol] :> {1, x}};
If[Depth[arg] == 3, arg = {arg}];
arg = If[Depth[#] == 2, {#}, #] & /@ arg

```

Now we construct a full Hamiltonian, summing up the subhamiltonians (the summation corresponds to `&&` parts of the expression)

```
H = h /@ arg /. List -> Plus;

```

And look for the lowest energy state

```
QuantumEigensystemForm[H, -1]

```

If we got an eigenvalue of zero, then the eigenvector is the solution

```
expr /. {x1 -> False, x2 -> True, x3 -> False}
> True

```

> Unfortunately the official site for the "Quantum Computing" add-on is not active and I can't find a place to download it, I just still had it installed on my computer. The Add-on also have a documented solution to the SAT problem, on which I based my code.

# Answer
> 27 votes
Three approaches here, all involve a reduction of SAT into its 2D geometric lingua franca: nonogram logic puzzles. Cells in the logic puzzle correspond to SAT variables, constraints to clauses.

For a full explanation (and to please review my code for bugs!) I've already posted some insight to patterns within the nonogram solution space. See https://codereview.stackexchange.com/questions/43770/nonogram-puzzle-solution-space . Enumerating \>4 billion puzzle solutions and encoding them to fit in a truth table shows fractal patterns -- self-similarity and especially self-affinity. This affine-redundancy demonstrates structure within the problem, exploitable to reduce the computational resources necessary to generate solutions. It also shows a need for chaotic feedback within any successful algorithm. There is explanatory power in the phase transition behavior where "easy" instances are those that lie along the coarse structure, while "hard" instances require further iteration into fine detail, quite hidden from normal heuristics. If you'd like to zoom into the corner of this infinite image (all \<=4x4 puzzle instances encoded) see http://re-curse.github.io/visualizing-intractability/nonograms\_zoom/nonograms.html

**Method 1.** Extrapolate the nonogram solution space shadow using chaotic maps and machine learning (think fitting functions similar to those that generate the Mandelbrot Set).

Here is a visual proof of induction. If you can scan these four images left to right and think you have a good idea to generate the missing 5th... 6th... etc. images, then I have just programmed *you* as my NP oracle for the decision problem of nonogram solution existence. Please step forth to claim your prize as the world's most powerful supercomputer. I'll feed you jolts of electricity every now and then while the world thanks you for your computational contributions.

**Method 2.** Use Fourier Transforms on the boolean image version of inputs. FFTs provide global information about frequency and position within an instance. While the magnitude portion should be similar between the input pair, their phase information is completely different -- containing directionalized information about a solution projection along a specific axis. If you're clever enough you might reconstruct the phase image of the *solution* via some special superposition of the input phase images. Then inverse transform the phase and common magnitude back to the time domain of the solution.

What could this method explain? There are many permutations of the boolean images with flexible padding between contiguous runs. This allows a mapping between input -\> solution taking care of multiplicity while still retaining FFTs' property of bidirectional, unique mappings between time domain \<-\> (frequency, phase). It also means there's no such thing as "no solution." What it would say is that in a continuous case, there are greyscale solutions that you're not considering when looking at the bilevel image of traditional nonogram puzzle solving.

Why wouldn't you do it? It's a horrible way to actually compute, as FFTs in today's floating-point world would be highly inaccurate with large instances. Precision is a huge problem, and reconstructing images from quantized magnitude and phase images usually creates very approximate solutions, although maybe not *visually* for human eye thresholds. It's also very hard to come up with this superpositioning business, as the type of function actually doing it is currently unknown. Would it be a simple averaging scheme? Probably not, and there's no specific search method to find it except intuition.

**Method 3.** Find a cellular automata rule (out of a possible ~4 billion rule tables for von Neumann 2-state rules) that solves a symmetric version of the nonogram puzzle. You use a direct embedding of the problem into cells, shown here.

This is probably the most elegant method, in terms of simplicity and good effects for the future of computing. The existence of this rule isn't proven, but I have a hunch it exists. Here's why:

Nonograms require lots of chaotic feedback in the algorithm to be solved exactly. This is established by the brute force code linked to on Code Review. CA is just about the most capable language to program chaotic feedback.

It *looks* right, visually. The rule would evolve through an embedding, propogate information horizontally and vertically, interfere, then stabilize to a solution that conserved the number of set cells. This propogation route follows the path (backwards) that you normally think of when projecting a physical object's shadow into the original configuration. Nonograms derives from a special case of discrete tomography, so imagine sitting concurrently in two kitty-cornered CT scanners.. this is how the X-rays would propogate to generate the medical images. Of course, there are boundary issues -- the edges of the CA universe cannot keep propogating information beyond the limits, unless you allow a toroidal universe. This also casts the puzzle as a periodic boundary value problem.

It explains multiple solutions as transient states in a continuously oscillating effect between swapping outputs as inputs, and vis versa. It explains instances that have no solution as original configurations that don't conserve the number of set cells. Depending on the actual outcome of finding such a rule, it may even approximate unsolvable instances with a close solution where the cell states *are* conserved.

# Answer
> 10 votes
# C++

Here is a solution that is guaranteed to run in polynomial time: it runs in `O(n^k)` where `n` is the number of booleans and `k` is a constant of your choice.

> It is heuristically correct, which I believe is CS-speak for "it gives the correct answer most of the time, with a bit of luck" (and, in this case, an appropriately large value of `k` \- *edit* it actually occurred to me that for any fixed `n` you can set `k` such that `n^k > 2^n` \- is that cheating?).

```
#include <iostream>
#include <cstdlib>
#include <time.h>
#include <cmath>
#include <vector>

using std::cout;
using std::endl;
typedef std::vector<bool> zork;

// INPUT HERE:

const int n = 3; // Number of bits
const int k = 4; // Runtime order O(n^k)

bool input_expression(const zork& x)
{
  return
  (!x[2]) && (
    (!x[0]) && (
      (x[0] || x[1] || x[0]) &&
      (x[1] || x[2] || x[1])));
}

// MAGIC HAPPENS BELOW:

 void whatever_you_do(const zork& minefield)
;void always_bring_a_towel(int value, zork* minefield);

int main()
{
  const int forty_two = (int)pow(2, n) + 1;
  int edition = (int)pow(n, k);
  srand(time(6["times7"]));

  zork dont_panic(n);
  while(--edition)
  {
    int sperm_whale = rand() % forty_two;
    always_bring_a_towel(sperm_whale, &dont_panic);

    if(input_expression(dont_panic))
    {
      cout << "Satisfiable: " << endl;
      whatever_you_do(dont_panic);
      return 0;
    }
  }

  cout << "Not satisfiable?" << endl;
  return 0;
}
void always_bring_a_towel(int value, zork* minefield)
{
  for(int j = 0; j < n; ++j, value >>= 1)
  {
    (*minefield)[j] = (value & 1);
  }
}

void whatever_you_do(const zork& minefield)
{
  for(int j = 0; j < n; ++j)
  {
    cout << (char)('A' + j) << " = " << minefield[j] << endl;
  }
}

```

# Answer
> 3 votes
# ruby/gnuplot 3d surface

(ooh stiff competition!) ... anyway ... is a picture worth a thousand words? these are 3 separate surface plots made in gnuplot of the SAT transition point. the (x,y) axes are clause & variable count and the z height is total # of recursive calls in the solver. code written in ruby. it samples 10x10 points at 100 samples each. it demonstrates/uses basic principles of statistics and is a Monte Carlo simulation.

its basically a davis putnam algorithm running on random instances generated in DIMACS format. this is the type of exercise that ideally would be done in CS classes around the world so students could learn the *basics* but is almost not taught specifically at all... maybe some reason why there are so many bogus P?=NP proofs? there is not even a good wikipedia article describing the transition point phenomenon (any takers?) which is a very prominent topic in statistical physics & is key also in CS.\[a\]\[b\] there are *many* papers in CS on the transition point however very few seem to show surface plots! (instead typically showing 2d slices.)

the exponential increase in runtime is clearly evident in 1st plot. the saddle running through the middle of 1st plot is the transition point. the 2nd and 3rd plots show the % satisfiable transition.

\[a\] phase transition behavior in CS ppt Toby Walsh
\[b\] empirical probability of k-SAT satisfiability tcs.se
\[c\] great moments in empirical/experimental math/(T)CS/SAT, TMachine blog

> P=?NP ***QED!***

```
#!/usr/bin/ruby1.8

def makeformula(clauses)
    (1..clauses).map \
    {
            vars2 = $vars.dup
            (1..3).map { vars2.delete_at(rand(vars2.size)) * [-1, 1][rand(2)] }.sort_by { |x| x.abs }
    }

end

def solve(vars, formula, assign)

    $counter += 1
    vars2 = []
    formula.each { |x| vars2 |= x.map { |y| y.abs } }
    vars &= vars2

    return [false] if (vars.empty?)
    v = vars.shift
    [v, -v].each \
    {
            |v2|
            f2 = formula.map { |x| x.dup }
            f2.delete_if \
            {
                    |x|
                    x.delete(-v2)
                    return [false] if (x.empty?)
                    x.member?(v2)
            }
            return [true, assign + [v2]] if (f2.empty?)
            soln = solve(vars.dup, f2, assign + [v2])
            return soln if (soln[0])
    }
    return [false]
end

def solve2(formula)
    $counter = 0
    soln = solve($vars.dup, formula, [])
    return [$counter, {false => 0, true => 1}[soln[0]]]
end

c1 = 10
c2 = 100
nlo, nhi = [3, 10]
mlo, mhi = [1, 50]
c1.times \
{
    |n|
    c1.times \
    {
            |m|
            p1 = nlo + n.to_f / c1 * (nhi - nlo)
            p2 = mlo + m.to_f / c1 * (mhi - mlo)
            $vars = (1..p1.to_i).to_a
            z1 = 0
            z2 = 0
            c2.times \
            {
                    f = makeformula(p2.to_i)
                    x = solve2(f.dup)
                    z1 += x[0]
                    z2 += x[1]
            }
#           p([p1, p2, z1.to_f / c2, z2.to_f / c2]) # raw
#           p(z1.to_f / c2)                         # fig1
#           p(0.5 - (z2.to_f / c2 - 0.5).abs)       # fig2
            p(z2.to_f / c2)                         # fig3
    }
    puts
}

```

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


title: Find the optimal starting move of Chomp

text:
# Question
Title: Find the optimal starting move of Chomp
Chomp is a two-player game with a setup of a rectangle of pieces. Each player takes a turn removing any piece, along with all pieces above it and to its right. Whoever takes the bottom-left piece loses. It can be proven fairly easily that the first player always has a winning move (except with a 1-by-1 rectangle); find it.

1. Input is the dimensions of the rectangle (two numbers)
2. Output is the location of the winning move (two numbers)
3. If there is more than one winning move, then you can output any of them.

This is code golf; shortest code (any language) wins.

# Examples

*Note: The outputs are just the two numbers; the ASCII art below is just to demonstrate what the numbers mean.*

Input: 5 3 (indices 1-based starting from lower-left corner)

Output: 4 3

```
XXX--
XXXXX
XXXXX

```

Input: 4 4

Output: 2 2

```
X---
X---
X---
XXXX

```

# Bonus

Subtract 15 characters from your score if you output all of the winning moves. Each pair of numbers must be separated by a newline.

# Answer
> 7 votes
### GolfScript, 82 (108 97 characters - 15 bonus)

```
~),1/{{:F$0=),{F\+}/}%}@(*(0*\{1${1$\{\(@<},=},{1$\{\(@>},+(-!},:Y!{.,/+0}*;}/;Y{.-1=.@?)' '@)n}/

```

Since I didn't know for any heuristics this solution performs an exhaustive search over the solution space. You may try the code online. Although the implementation is very efficient the search space grows very fast with increasing input.

Examples:

```
> 5 3
4 3

> 5 4
3 3

> 6 6
2 2

```

As mentioned above the implementation does not rely on recursion but visits each node of the search space only once. Below you can find an annotated version of the code which describes the building blocks in more detail.

The representation of a single board of size *w* * *h* is given by a list of *w* numbers in the range *0* to *h*. Each number gives the amount of pieces in the corresponding column. Thus, a valid configuration is a list where the numbers are non-increasing from start to end (with any move you ensure that all columns to the right are at most as high as the chosen one).

```
~                   # Evaluate the input (stack is now w h)

# BUILDING THE COMPLETE STATE SPACE
# Iteratively builds the states starting with 1xh board, then 2xh board, ...

),1/                # Generate the array [[0] [1] ... [h]] which is the space for 1xh
{                   # This loop is now ran w-1 times and each run adds all states for the
                    # board with one additional column
  {                 # The {}/] block simply runs for each of the existing states
    :F$0=           #   Take the smallest entry (which has to be the last one)
    ),              #   For the last column all values 0..x are possible
    {F\+}/          #     Append each of these values to the smaller state
  }%
}@(*

# The order ensures that the less occupied boards are first in the list.
# Thus each game runs from the end of the list (where [h h ... h] is) to
# the start (where [0 0 ... 0] is located).

# RUN THROUGH THE SEARCH SPACE
# The search algorithm therefore starts with the empty board and works through all
# possible states by simply looping over this list. It builds a list of those states
# which are known as non-winning states, i.e. those states where a player should
# aim to end after the move

(                   # Skips the empty board (which is a winning configuration)
0*\                 # and makes an empty list out of it (which will be the list of
                    # known non-winning states (initially empty))
{                   # Loop over all possible states
  1$                #   Copy of the list of non-winning states
  {                 #   Filter those which are not reachable from the current state,
                    #   because at least one column has more pieces that the current
                    #   board has
    1$\{\(@<},=
  },
  {                 #   Filter those which are not reachable from the current state,
                    #   because no valid move exists
    1$\{\(@>},+     #     Filter those columns which are different between start and
                    #     end state
    (-!             #     If those columns are all of same height it is possible to move
  },
  :Y                #   Assign the result (list of all non-winning states which are
                    #   reachable from the current configuration within one move)
                    #   to variable Y

  !{                #   If Y is non-empty this one is a winning move, otherwise
                    #   add it to the list
    .,/+
    0               #     Push dummy value
  }*;
}/
;                   # Discard the list (interesting data was saved to variable Y)

# OUTPUT LOOP
# Since the states were ordered the last one was the starting state. The list of
# non-winning states were saved to variable Y each time, thus the winning moves
# from the initial configuration is contained in this variable.

Y{                  # For each item in Y
  .-1=.@?)          #   Get the index (1-based) of the first non-h value
  ' '               #   Append a space
  @)                #   Get the non-h value itself (plus one)
  n                 #   Append a newline
}/

```

# Answer
> 8 votes
## Python 2 3, 141-15=126

```
def win(x,y):w([y]*x)
w=lambda b,f=print:not[f(r+1,c+1)for r,p in enumerate(b)for c in range(p)if(r+c)*w(b[:r]+[min(i,c)for i in b[r:]],max)]

```

Brute-force minimax search. For every possible move, we recursively see if the opponent can win after we make that move. Pretty weakly golfed; someone else should be able to do much better. This feels like a job for APL.

* `win` is the public interface. It takes the dimensions of the board, converts it to a board representation, and passes that to `w`.
* `w` is the minimax algorithm. It takes a board state, tries all moves, builds a list whose elements correspond to winning moves, and returns True if the list is empty. With the default `f=print`, building the list has a side effect of printing the winning moves. The function name used to make more sense when it returned a list of winning moves, but then I moved the `not` in front of the list to save a space.
* `for r,p in enumerate(b)for c in xrange(p) if(r+c)`: Iterate over all possible moves. `1 1` is treated as not a legal move, simplifying the base case a bit.
* `b[:r]+[min(i,c)for i in b[r:]]`: Construct the state of the board after the move represented by coordinates `r` and `c`.
* `w(b[:r]+[min(i,c)for i in b[r:]],max)`: Recurse to see whether the new state is a losing state. `max` is the shortest function I could find that would take two integer arguments and not complain.
* `f(r+1,c+1)`: If `f` is print, prints the move. Whatever `f` is, it produces a value to pad the list length.
* `not [...]`: `not` returns `True` for empty lists and `False` for nonempty.

Original Python 2 code, completely ungolfed, including memoization to handle much larger inputs:

```
def win(x, y):
    for row, column in _win(Board([y]*x)):
        print row+1, column+1

class MemoDict(dict):
    def __init__(self, func):
        self.memofunc = func
    def __missing__(self, key):
        self[key] = retval = self.memofunc(key)
        return retval

def memoize(func):
    return MemoDict(func).__getitem__

def _normalize(state):
    state = tuple(state)
    if 0 in state:
        state = state[:state.index(0)]
    return state

class Board(object):
    def __init__(self, state):
        self.state = _normalize(state)
    def __eq__(self, other):
        if not isinstance(other, Board):
            return NotImplemented
        return self.state == other.state
    def __hash__(self):
        return hash(self.state)
    def after(self, move):
        row, column = move
        newstate = list(self.state)
        for i in xrange(row, len(newstate)):
            newstate[i] = min(newstate[i], column)
        return Board(newstate)
    def moves(self):
        for row, pieces in enumerate(self.state):
            for column in xrange(pieces):
                if (row, column) != (0, 0):
                    yield row, column
    def lost(self):
        return self.state == (1,)

@memoize
def _win(board):
    return [move for move in board.moves() if not _win(board.after(move))]

```

Demo:

```
>>> for i in xrange(7, 11):
...     for j in xrange(7, 11):
...         print 'Dimensions: {} by {}'.format(i, j)
...         win(i, j)
...
Dimensions: 7 by 7
2 2
Dimensions: 7 by 8
3 3
Dimensions: 7 by 9
3 4
Dimensions: 7 by 10
2 3
Dimensions: 8 by 7
3 3
Dimensions: 8 by 8
2 2
Dimensions: 8 by 9
6 7
Dimensions: 8 by 10
4 9
5 6
Dimensions: 9 by 7
4 3
Dimensions: 9 by 8
7 6
Dimensions: 9 by 9
2 2
Dimensions: 9 by 10
7 8
9 5
Dimensions: 10 by 7
3 2
Dimensions: 10 by 8
6 5
9 4
Dimensions: 10 by 9
5 9
8 7
Dimensions: 10 by 10
2 2

```

# Answer
> 2 votes
# Perl 6: ~~113~~ 108 characters - 15 = 93 points

This one was tough! Here's the uncached version, which is technically correct but will take a *very* long time for non-trivial inputs.

```
sub win(*@b){map ->\i,\j{$(i+1,j+1) if @b[i][j]&&!win @b[^i],@b[i..*].map({[.[^j]]})},(^@b X ^@b[0])[1..*]}

```

It works just like @user2357112's Python implementation (upvote him/her, I couldn't have figured this out without his/her work!) except that win() takes a Chomp board (array) instead of a width and length. It can be used like:

```
loop {
    my ($y, $x) = get.words;
    .say for @(win [1 xx $x] xx $y)
}

```

A version with memoization, which can actually handle decent inputs (not optimized for readability, though):

```
my %cache;
sub win (*@b) {
    %cache{
        join 2, map {($^e[$_]??1!!0 for ^@b[0]).join}, @b
    } //= map ->\i,\j{
        $(i+1,j+1) if @b[i][j] and not win
            @b[^i], @b[i..*].map({[.[^(* min j)]]}).grep: +*;
    },(^@b X ^@b[0])[1..*]
}

```

---
Tags: code-golf
---