# Question
Title: Terminating, Purely Periodic, or Eventually Periodic?
## Introduction

A decimal is terminating if it has a finite number of decimal digits. For example, 0.4 (2/5) is terminating because it has one decimal digit.

A decimal is purely periodic if it has an infinite number of decimal digits and has no decimal digits before its repetent (the part of the decimal that repeats.) For example, 0.142857142857142… (1/7) is purely periodic because it has a repetend 142857, which starts repeating immediately after the decimal point.

A decimal is eventually periodic if it has an infinite number of decimal digits and has a finite number of decimal digits before its repetent (the part of the decimal that repeats.) For example, 0.166666666666666… (1/6) is eventually periodic because its repetend 6 starts repeating after a 1.

## Your task

Write a program or function that, when given numbers *p* and *q* (integers, 0 \<= *p* \< *q* \<= 100), will determine if the decimal representation of *p*/*q* is terminating, purely periodic, or eventually periodic.

You must output `a` if it's Terminating (i.e. 0.1), `b` if it's Purely Periodic (i.e. 0.333...), or `c` if it's Eventually Periodic (i.e. 0.166...), where `a`, `b`, and `c` are any distinct, constant strings of your choice.

## Test cases

```
0/1 => Terminating
0/2 => Terminating
1/2 => Terminating
0/3 => Terminating
1/3 => Purely Periodic
2/3 => Purely Periodic
0/4 => Terminating
1/4 => Terminating
2/4 => Terminating
3/4 => Terminating
0/5 => Terminating
1/5 => Terminating
2/5 => Terminating
3/5 => Terminating
4/5 => Terminating
0/6 => Terminating
1/6 => Eventually Periodic
2/6 => Purely Periodic
3/6 => Terminating
4/6 => Purely Periodic
5/6 => Eventually Periodic
0/7 => Terminating
1/7 => Purely Periodic
2/7 => Purely Periodic
3/7 => Purely Periodic
4/7 => Purely Periodic
5/7 => Purely Periodic
6/7 => Purely Periodic
0/8 => Terminating
1/8 => Terminating
2/8 => Terminating
3/8 => Terminating
4/8 => Terminating
5/8 => Terminating
6/8 => Terminating
7/8 => Terminating
0/9 => Terminating
1/9 => Purely Periodic
2/9 => Purely Periodic
3/9 => Purely Periodic
4/9 => Purely Periodic
5/9 => Purely Periodic
6/9 => Purely Periodic
7/9 => Purely Periodic
8/9 => Purely Periodic
0/10 => Terminating
1/10 => Terminating
2/10 => Terminating
3/10 => Terminating
4/10 => Terminating
5/10 => Terminating
6/10 => Terminating
7/10 => Terminating
8/10 => Terminating
9/10 => Terminating
0/11 => Terminating
1/11 => Purely Periodic
2/11 => Purely Periodic
3/11 => Purely Periodic
4/11 => Purely Periodic
5/11 => Purely Periodic
6/11 => Purely Periodic
7/11 => Purely Periodic
8/11 => Purely Periodic
9/11 => Purely Periodic
10/11 => Purely Periodic
0/12 => Terminating
1/12 => Eventually Periodic
2/12 => Eventually Periodic
3/12 => Terminating
4/12 => Purely Periodic
5/12 => Eventually Periodic
6/12 => Terminating
7/12 => Eventually Periodic
8/12 => Purely Periodic
9/12 => Terminating
10/12 => Eventually Periodic
11/12 => Eventually Periodic
0/13 => Terminating
1/13 => Purely Periodic
2/13 => Purely Periodic
3/13 => Purely Periodic
4/13 => Purely Periodic
5/13 => Purely Periodic
6/13 => Purely Periodic
7/13 => Purely Periodic
8/13 => Purely Periodic
9/13 => Purely Periodic
10/13 => Purely Periodic
11/13 => Purely Periodic
12/13 => Purely Periodic
0/14 => Terminating
1/14 => Eventually Periodic
2/14 => Purely Periodic
3/14 => Eventually Periodic
4/14 => Purely Periodic
5/14 => Eventually Periodic
6/14 => Purely Periodic
7/14 => Terminating
8/14 => Purely Periodic
9/14 => Eventually Periodic
10/14 => Purely Periodic
11/14 => Eventually Periodic
12/14 => Purely Periodic
13/14 => Eventually Periodic
0/15 => Terminating
1/15 => Eventually Periodic
2/15 => Eventually Periodic
3/15 => Terminating
4/15 => Eventually Periodic
5/15 => Purely Periodic
6/15 => Terminating
7/15 => Eventually Periodic
8/15 => Eventually Periodic
9/15 => Terminating
10/15 => Purely Periodic
11/15 => Eventually Periodic
12/15 => Terminating
13/15 => Eventually Periodic
14/15 => Eventually Periodic

```

You can find all test cases here.

You are allowed to choose your own 3 values for the output, but it must be clear as to which one it is.

Remember, this is , so the code with the smallest number of bytes wins.

## Hints

Terminating:

> The prime factorization of a terminating decimal's denominator in simplest form consists only of 2s and 5s.

Purely Periodic:

> The prime factorization of a purely periodic decimal's denominator in simplest form does not include any 2s or 5s.

Eventually Periodic:

> The prime factorization of an eventually periodic decimal's denominator in simplest form includes at least one 2 or 5, but also includes other numbers.

## Leaderboards

Here is a Stack Snippet to generate both a regular leaderboard and an overview of winners by language.

To make sure that your answer shows up, please start your answer with a headline, using the following Markdown template:

```
# Language Name, N bytes

```

where `N` is the size of your submission. If you improve your score, you *can* keep old scores in the headline, by striking them through. For instance:

```
# Ruby, <s>104</s> <s>101</s> 96 bytes

```

If there you want to include multiple numbers in your header (e.g. because your score is the sum of two files or you want to list interpreter flag penalties separately), make sure that the actual score is the *last* number in the header:

```
# Perl, 43 + 2 (-p flag) = 45 bytes

```

You can also make the language name a link which will then show up in the leaderboard snippet:

```
# [><>](http://esolangs.org/wiki/Fish), 121 bytes

```

```
var QUESTION_ID=95926,OVERRIDE_USER=12537;function answersUrl(e){return"https://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(e,s){return"https://api.stackexchange.com/2.2/answers/"+s.join(";")+"/comments?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){answers.push.apply(answers,e.items),answers_hash=[],answer_ids=[],e.items.forEach(function(e){e.comments=[];var s=+e.share_link.match(/\d+/);answer_ids.push(s),answers_hash[s]=e}),e.has_more||(more_answers=!1),comment_page=1,getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){e.items.forEach(function(e){e.owner.user_id===OVERRIDE_USER&&answers_hash[e.post_id].comments.push(e)}),e.has_more?getComments():more_answers?getAnswers():process()}})}function getAuthorName(e){return e.owner.display_name}function process(){var e=[];answers.forEach(function(s){var r=s.body;s.comments.forEach(function(e){OVERRIDE_REG.test(e.body)&&(r="<h1>"+e.body.replace(OVERRIDE_REG,"")+"</h1>")});var a=r.match(SCORE_REG);a&&e.push({user:getAuthorName(s),size:+a[2],language:a[1],link:s.share_link})}),e.sort(function(e,s){var r=e.size,a=s.size;return r-a});var s={},r=1,a=null,n=1;e.forEach(function(e){e.size!=a&&(n=r),a=e.size,++r;var t=jQuery("#answer-template").html();t=t.replace("{{PLACE}}",n+".").replace("{{NAME}}",e.user).replace("{{LANGUAGE}}",e.language).replace("{{SIZE}}",e.size).replace("{{LINK}}",e.link),t=jQuery(t),jQuery("#answers").append(t);var o=e.language;/<a/.test(o)&&(o=jQuery(o).text()),s[o]=s[o]||{lang:e.language,user:e.user,size:e.size,link:e.link}});var t=[];for(var o in s)s.hasOwnProperty(o)&&t.push(s[o]);t.sort(function(e,s){return e.lang>s.lang?1:e.lang<s.lang?-1:0});for(var c=0;c<t.length;++c){var i=jQuery("#language-template").html(),o=t[c];i=i.replace("{{LANGUAGE}}",o.lang).replace("{{NAME}}",o.user).replace("{{SIZE}}",o.size).replace("{{LINK}}",o.link),i=jQuery(i),jQuery("#languages").append(i)}}var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk",answers=[],answers_hash,answer_ids,answer_page=1,more_answers=!0,comment_page;getAnswers();var SCORE_REG=/<h\d>\s*([^\n,]*[^\s,]),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/,OVERRIDE_REG=/^Override\s*header:\s*/i;
```

```
body{text-align:left!important}#answer-list,#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}
```

```
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"> <div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr></thead> <tbody id="answers"> </tbody> </table> </div><div id="language-list"> <h2>Winners by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr></thead> <tbody id="languages"> </tbody> </table> </div><table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table> <table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table>
```

# Answer
# Jelly, 10 bytes

```
:gÆfḍ⁵ṢQ¬Ḅ

```

Accepts denominator and numerator (in that order) as arguments. Returns **0** for terminating, **1** for purely periodic, and **2** for eventually periodic. Try it online! or verify all test cases.

### How it works

```
:gÆfḍ⁵ṢQ¬Ḅ  Main link. Arguments: d (denominator), n (numerator)

 g          Compute the GCD of d and n.
:           Divide d by the GCD, yielding the denominator of the simplified form.
  Æf        Yield all prime factors of the previous result.
    ḍ⁵      Test 10 for divisibility by each prime factor.
            This yields 1 for 2 and 5, 0 for all other primes.
      Ṣ     Sort the resulting Booleans.
       Q    Unique; deduplicate the sorted Booleans.
        ¬   Logical NOT; replace 0 with 1 and vice versa to yield one of the
            following arrays.
              [    ]  <- no prime factors (denominator 1)
              [   0]  <- only 2 and 5
              [1   ]  <- neither 2 nor 5
              [1, 0]  <- mixed
         Ḅ  Unbinary; convert from base 2 to integer.
            This maps [] and [0] to 0, [1] to 1, and [1, 0] to 2.

```
> 8 votes

# Answer
## JavaScript (ES6), ~~70~~ .. ~~68~~ 53 bytes

```
f=(a,b,s=[],x)=>a?(s[a]^=a)?f(a*10%b,b,s,x||a):x==a:0

```

Returns **0** for terminating, **true** for purely periodic and **false** for eventually periodic.

### How it works

What we're doing here is actually simulating a division by hand:

1. `a?...:0` \- If the numerator is zero, we stop here and return `0`. The sequence is *terminating*.
2. `(s[a]^=a)?...:x==a` \- If we've already encountered this numerator before, it means that the sequence is periodic and is going to repeat forever. We stop here and return either `true` if `a` is equal to the first value `x` of the sequence (*purely periodic*) or `false` if it's not (*eventually periodic*).
3. `f(a*10%b,b,s,x||a)` \- Else, we multiply the numerator `a` by 10. We compute the remainder of the division by the denominator `b`. And we repeat the process by using this remainder as the new numerator. (We also pass `a` as the first value of the sequence if it's not already stored in `x`.)

### Example

* **Blue**: numerator = 1
* **Green**: denominator = 7
* **Red**: multiplications by 10
* **Black**: remainders
* **Gray**: quotient digits (we don't really care about them here, and the above code is not computing them at all)
> 11 votes

# Answer
# Python, ~~62~~ ~~61~~ 59 bytes

```
f=lambda n,d,r=[0,0]:(r[:3]+r).count(n)or f(10*n%d,d,r+[n])

```

Prints **1** for eventually periodic, **2** for purely periodic, and **4** for terminating.

Verify all test cases on repl.it.
> 9 votes

# Answer
# Perl, ~~49~~ ~~46~~ 45 bytes

Includes +3 for `-p`

Based on Dennis's elegant idea but implemented in a perlish way

Give input numbers on STDIN

```
terminating.pl <<< "2 26"

```

`termninating.pl`:

```
#!/usr/bin/perl -p
/ /;1until$a{$_=$_*10%$' or$`}++;$_=$a{$`}

```

Prints a 2 if terminating. 1 if periodic and nothing if eventually periodic
> 6 votes

# Answer
# JavaScript (ES6), ~~91~~ ~~88~~ ~~85~~ ~~79~~ ~~75~~ ~~74~~ 78 bytes

```
f=(n,d,g=(a,b)=>b?g(b,a%b):a,t=g(d/=c=g(n,d),10))=>n*~-d?t-1?f(n/c,d/t)/0:1:+f

```

Outputs `NaN` for terminating, `1` for purely periodic, and `Infinity` for eventually periodic.

### Test snippet

```
f=(n,d,g=(a,b)=>b?g(b,a%b):a,t=g(d/=c=g(n,d),10))=>n*~-d?t-1?f(n/c,d/t)/0:1:+f

l=(n,d)=>console.log(n+"/"+d+":",f(n,d))

for(i=1;i<10;i++)for(j=0;j<i;j++)l(j,i);
```

## Explanation

First, we divide both **n** and **d** by **gcd(d,n)**, to reduce the fraction to its simplest form. This lets us avoid situations like **2/6** where the result would otherwise be calculated as purely periodic. We also define variable **t** as **gcd(d,10)**; this will be used later.

The first check is whether **n** is **0** or **d** is **1**. If **n\*(d-1)** is 0, we return `+f`, or **NaN**: the fraction is **terminating**.

The next check is whether **t** is **1**. If so, we return **1**: the fraction is **purely periodic**.

If **t** is *not* **1**, we divide **d** by **t**, run the whole function again, and divide by 0. If **n/(d/t)** is terminating, this returns **NaN/0 = NaN**: the fraction is **terminating**. Otherwise, it returns **1/0 = Infinity**: the fraction is **eventually periodic**.
> 3 votes

# Answer
## Batch, 247 bytes

```
@set/af=%1,g=%2
:g
@if not %f%==0 set/ah=g,g=f,f=h%%g&goto g
@set/ae=d=%2/g
:l
@set/ag=-~!(d%%2)*(!(d%%5)*4+1)
@if not %g%==1 set/ad/=g&goto l
@if %d%==1 (echo Terminating)else if %d%==%e% (echo Purely Periodic)else echo Eventually Periodic

```

Uses my fast gcd10 trick from Fraction to exact decimal. Obviously I could save a bunch of bytes by using a custom output format.
> 3 votes

# Answer
# Mathematica, 41 bytes

```
Ordering@{d=Denominator@#,GCD[d,10^d],1}&

```

Outputs `{3,1,2}` if the input has a terminating decimal expansion, `{2,3,1}` if the input has a purely periodic decimal expansion, and `{3,2,1}` if the input has an eventually periodic decimal expansion.

Based on the sneaky trick: if `d` is the denominator of a fraction in lowest terms, then the greatest common divisor of `d` and `10^d` equals `d` if `d` has only 2s and 5s in its prime factorization; equals `1` if `d` has neither 2s nor 5s in its prime factorization; and equals some integer in between if `d` has 2s/5s and other primes.

The `Ordering` function just reports where the smallest, next smallest, and largest elements of the triple are, with ties broken left-to-right.

Flaw: returns the variant output `{1,2,3}` instead of `{3,1,2}` if the input is 0.

# Mathematica, 46 bytes, perverse

```
b[a][[Log[d=Denominator@#,GCD[d,10^d]]]][[1]]&

```

Returns `a[[1]]` if the input has a terminating decimal expansion, `b[[1]]` if the input has a purely periodic decimal expansion, and `b[a]` if the input has an eventually periodic decimal expansion. Throws an error in all cases!

As above, we want to know whether that greatest common divisor equals 1, d, or somewhere in between. The base-d logarithm of that gcd equals 0, 1, or something in between.

Now we start torturing Mathematica. `b[a][[n]]` denotes the `n`th part of the expression `b[a]`. So `b[a][[1]]` returns `a`; `b[a][[0]]` returns `b`; and `b[a][[x]]`, where `x` is a number between 0 and 1, makes Mathematica throw the error "Part::pkspec1: The expression `x` cannot be used as a part specification." and returns `b[a][[x]]` unevaluated.

This already distinguishes the three cases appropriately, except that the output for the eventually periodic case is `b[a][[x]]`, which is non-constant because `x` is the actual logarithm of something. So then we apply `[[1]]` to the outputs already described. Because of how Mathematica internally represents `b[a][[x]]`, the result of `b[a][[x]][[1]]` is simply `b[a]`. On the other hand, applying `[[1]]` to `a` results in a different error "Part::partd: Part specification a\[\[1\]\] is longer than depth of object." and returns `a[[1]]` unevaluated (and similarly for `b`).

Flaw: lies about the input 0, returning `b[a]` instead of `a[[1]]`.
> 3 votes

# Answer
# Actually, 15 bytes

This is based on Dennis' Jelly answer. **0** is terminating, **1** is purely periodic, and **2** is eventually periodic. Golfing suggestions welcome. Try it online!

```
▼Ny9u♀%SR♂b╔2@¿

```

**Ungolfing**

```
      Implicit input [a, b].
▼     Divide a and b by gcd(a,b).
Ny    Get the unique prime divisors of the reduced denominator.
9u    Push 10.
♀%    10 mod every member of uniq_p_d.
SR    Sort the mods and reverse.
♂b    Logical buffer. Converts every (10 % p != 0) to 1, and everything else to 0.
        Meaning if 2 or 5 divided b, they are now 0, and every other prime is now 1.
╔     Uniquify the list.
        If terminating, return [0].
        If purely periodic, return [1].
        If eventually periodic, return [1, 0].
        Else, (if b was 1), return [].
2@¿   Convert from binary to decimal. Return 0, 1, or 2.
      Implicit return.

```
> 2 votes

# Answer
# C 173 Bytes

Takes two integers from stdin, prints 1 for purely periodic, -1 for eventually periodic, and 0 for terminating.

```
int r;main(_,n,d){_-1?_-2?d-1?d%2&&d%5?r=1:d%2?main(3,n,d/5):main(3,n,d/2),r=r?-1:0:r=0:d?main(2,d,n%d):r=n:scanf("%d %d",&n,&d),main(2,n,d),main(3,n/r,d/r),printf("%d",r);}

```

Ungolfed:

```
// returns 1 for periodic, 0 for terminating, <0 for eventually periodic
int periodic(int num, int den) { // 3
    if (den == 1) return 0;
    if (den % 2 && den % 5) // pure periodic
        return 1;
    if (den % 2) return periodic(num,den/5) ? -1 : 0;
    return periodic(num,den/2) ? -1 : 0;
}

int gcd(int num, int den) { // 2
    if (den)
        return gcd(den,num%den);
    return num;
}

int main(n,d) // 1
{
    scanf("%d %d",&n,&d);
    printf("%d",periodic(n/gcd(n,d),d/gcd(n,d)));
    return 0;
}

```

Half-golfed:

```
int r;main(_,n,d){
    _-1?
    _-2?
    // periodic
    d-1?
        d%2&&d%5?
            r=1:
                d%2?
                    main(3,n,d/5): //periodic
                    main(3,n,d/2), //periodic
                        r=r?-1:0:
                r=0
    // gcd
    :d?main(2,d,n%d):r=n // gcd
    // main
    :scanf("%d %d",&n,&d),
     main(2,n,d), // gcd
     main(3,n/r,d/r), // periodic
     printf("%d",r);
}

```
> 2 votes

# Answer
# PHP, 126 Bytes

```
$d=$argv[2];$a[]=$n=$argv[1];while($n%$d&&!$t){$n*=10;$t=in_array($n%=$d,$a);$a[]=$n;}if($a[1]&&$t)$t+=$a[0]!=end($a);echo+$t;

```

Prints 0 for terminated and 1 for purely periodic 2 for eventually. Let me explain if a numerator is twice in the array here starts the periodic session if it is terminated the `echo end($a);` value is `0` If you not trust me put `$t=count($a)>$d?2:0;` in the loop

To make it more clear please add `print_r($a);` or `var_dump($a);` or `json_encode($a);` after the loop

you can see one numerator twice or a zero at the end of the array if a numerator is twice count the items between the two items and you can get the length of the periodic and you can see the position by the first numerator where the periodic begins

So after that we can find the position and the length of the periodic sequence with `if($t){echo $p=array_search(end($a),$a);echo $l=count($a)-$p-1;}`

## Visualize the periodic

```
$d=$argv[2];
$a[]=$n=$argv[1]; #array numerator
$r[]=$n/$d^0; #array result of the division
$r[]=".";
while($n%$d&&!$t){
    $n*=10;
    $n-=$d*$r[]=$n/$d^0;
    $t=in_array($n%=$d,$a); #stop if numerator is twice
    $a[]=$n;
}
if($a[1]&&$t)$t+=$a[0]!=end($a); #periodic term starts directly?
if($t){
    echo $p=array_search(end($a),$a)."\n"; #output the beginning position of the periodic term
    echo $l=count($a)-$p-1; #output the length of the periodic term
    echo "\n";
    echo str_repeat(" ",2+$p).str_repeat("_",$l-1)."\n"; #visualize the periodic term
    #echo join(array_slice($r,0,1+$p)).join(array_slice($r,1+$p))."\n";# if you want only the periodic term
    echo join($r); #result if the division
}
echo+$t; # 0 terminated 1+2 periodic 2 periodic start not directly

```

## Output visualize the periodic term

```
1/18
   _
0.05

1/12
    _
0.083

1/13
  ______
0.076923

1/14
   ______
0.0714285

```

An other way with 130 Bytes

```
$r=bcdiv(($z=$argv)[1],$z[2],400);for($p=2;$i++<200;)if(substr($r,2,$i)==substr($r,2+$i,$i))$p=1;echo strlen(rtrim($r,0))<50?0:$p;

```

Expanded Version

```
$r=bcdiv(($z=$argv)[1],$z[2],400); # 100 is the maximal denominator
# we need a string length with the double value of the sum the length from 1 until the denominator
for($p=2;$i++<200;)if(substr($r,2,$i)==substr($r,2+$i,$i))$p=1;
# all results begin with 0.
#take two substrings with the same length after that and comparize both.
#if we found 2 same substrings we have a periodic which starts at the first decimal place
echo strlen(rtrim($r,0))<50?0:$p;
# if we can trim the length of the result we have a terminated result

```
> 1 votes

# Answer
# Mathematica, 44 bytes

```
If[ListQ@Last@#,Length@#==1]&@@RealDigits@#&

```

Returns `Null` for Terminating, `True` for purely periodic, and `False` for eventually periodic.

# Explanation

```
RealDigits

```

Find the decimal expansion of N. (repeated digits are surrounded by an extra head `List {}`).

```
ListQ@Last@#

```

Check whether the last element of the decimal expansion is a `List`.

```
Length@#==1

```

If the above condition is `True`, check whether the entire decimal expansion consists of one thing. (A `List` counts as one entity). (returns `True` or `False`)

(If the condition is `False`, then a `Null` is returned because there is no third argument for `If`)
> 1 votes

# Answer
# Pyth, ~~31~~ 27 bytes

```
AQ={P/HiGH?l@H=j25T?l-HT1Z2

```

Input

```
4,12

```

You can try it here. Prints **1** for eventually periodic, **2** for purely periodic, and **0** for terminating. This is my first time answering in codegolf. Any suggestions are welcome.

## Explanation

```
AQ                                              // 1st element to G and 2nd element to H
    ={P                                         // Assign unique prime factors to H
        /H                                      // Simplify denominator
            iGH                                 // Find GCD
                ?l                              // Check length of filtered H
                    @H                          // Filter H by Y
                        =j25T                   // Assign a set [2,5] to T
                                ?l-HT           // Check length of H - T
                                        1Z2     // Print result

```

Note that \[2,3\] filtered by \[2,5\] = \[2\] but \[2,3,5\] - \[2,5\] = \[3\].
> 1 votes

# Answer
## PARI/GP, 64 bytes

```
f(x,y)=if(setminus(factor(y=y/gcd(x,y))[,1]~,[2,5]),gcd(y,10)>1)

```

Outputs nothing for terminating, 0 for purely and 1 for eventually periodic.

Not very fancy, I hoped for something better when I started.
> 1 votes

# Answer
# 05AB1E, ~~16~~ 11 bytes

Saved 5 bytes thanks to @Adnan!

```
¿²r/fTrÖbÙJ

```

Prints 0 for Purely Periodic, 1 for Terminating, and 10 for Eventually Periodic.

Explanation:

```
                 # Implicit input
                 # Implicit input
  ¿              # Take GCD of numbers
   ²             # Push top value from input register
    r            # Reverse stack order
     /           # Divide (denominator by GCD)
      f          # Find unique prime factors
       TrÖ       # Test 10 for divisibility
          b      # Convert (True -> 1, False -> 0)
           Ù     # Deduplicate array
            J    # Join chars in array
                 # Implicit print

```

Input is taken as *p* newline *q*.

Try it online!
> 1 votes

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


title: How old is that map?

text:
# Question
Title: How old is that map?
Referencing xkcd 1688:

Your task is to deduct the age of a map by asking the user questions. These question must be exactly the same as in the xkcd guide, except from the capitalisation and additional newline(s). Additionally, you should give the user some options to choose from, which don't have to be in the order as in the xkcd image. If the input doesn't match any of the expected answers, your program/function may behave in any undefined way. At the end, you should output the year/timespan the map was created.

## Examples (`>` denotes input, but you may choose something else):

### Example 1:

```
ISTANBUL OR CONSTANTINOPLE?
(CONSTANTINOPLE, NEITHER, ISTANBUL)

>ISTANBUL

DOES THE SOVIET UNION EXISTS?
(YES, NO)

>NO

ZAIRE?
OR: 'HONG KONG (UK)'
(YES, NO)

>NO

SERBIA / MONTENEGRO ARE?
(ONE COUNTRY, TWO COUNTRIES)

>TWO COUNTRIES

HOW MANY SUDANS ARE THERE?
(ONE, TWO)

>ONE

2007-11

```

### Example 2:

```
ISTANBUL OR CONSTANTINOPLE?
(CONSTANTINOPLE, NEITHER, ISTANBUL)

>how are you

error

```

# Answer
# Game Maker Language (GM 8.0), ~~10262~~ ~~10228~~ ~~10152~~ ~~10115~~ ~~8746~~ 1 + 8699 = 8700 bytes

We define a script named `X` (1 byte). Each question is labelled with an integer. `X` takes such an integer, prompts the user with the corresponding question, and either returns the appropriate message or calls the next question. At each question, the user is prompted for an integer corresponding to the possible options. If the user does not match any of the options, then the prompt is exited.

```
A=argument1 Y="##YES (1), NO (2)"I="IS THERE A BIG LAKE IN THE MIDDLE OF "H="HOW MANY "switch argument0{case H:return show_message(A)break
case I:return get_integer(A,1)break
case 1:switch X(I,"ISTANBUL OR CONSTANTINOPLE##CONSTANTINOPLE (1), NEITHER (2), ISTANBUL(3)"){case 1:X(2)break case 2:X(19)break case 3:X(74)}break
case 2:switch X(I,"DO ANY OF THESE EXIST?#- INDEPENDENT CANADA#- US TERRITORY OF ALASKA#- TOKYO"+Y){case 2:X(3)break case 1:X(11)}break
case 3:switch X(I,"THE HOLY ROMAN EMPIRE?"+Y){case 1:X(H,"1805 OR EARLIER (BEFORE THIS POINT, THE MODERN IDEA OF A COMPLETE POLITICAL MAP OF THE WORLD GETS HARD TO APPLY.)")break case 2:X(4)}break
case 4:switch X(I,"THE UNITED STATES?"+Y){case 2:X(H,"HOW SURE ARE YOU THAT THIS MAP IS IN ENGLISH")break case 1:X(5)}break
case 5:switch X(I,"TEXAS IS...##PART OF MEXICO (1), INDEPENDENT (2), PART OF THE US (3)"){case 1:X(6)break case 2:X(H,"1834-45")break case 3:X(9)}break
case 6:switch X(I,"FLORIDA IS PART OF...##SPAIN (1), THE US (2)"){case 1:X(7)break case 2:X(8)}break
case 7:switch X(I,"PARAGUAY?"+Y){case 2:X(H,"1806H0")break case 1:X(H,"1811H7")}break
case 8:switch X(I,"VENEZUELA AND/OR ECUADOR?"+Y){case 2:X(H,"1818-29")break case 1:X(H,"1830-33")}break
case 9:switch X(I,"DOES RUSSIA BORDER THE SEA OF JAPAN?"+Y){case 2:X(10)break case 1:X(H,"1858-67")}break
case 10:switch X(I,"THE US'S SOUTHERN BORDER LOOKS...##WEIRD (1), NORMAL (2)"){case 1:X(H,"1846-53")break case 2:X(H,"1854-56")}break
case 11:switch X(I,"SOUTH AFRICA?"+Y){case 2:X(12)break case 1:X(16)}break
case 12:switch X(I,"RHODESIA?"+Y){case 2:X(13)break case 1:X(15)}break
case 13:switch X(I,"IS BOLIVIA LANDLOCKED?"+Y){case 2:X(14)break case 1:X(H,"1884-95")}break
case 14:switch X(I,'"BUDA" AND "PEST" OR "BUDAPEST"?##BUDA AND PEST (1), BUDAPEST (2)'){case 1:X(H,"1868-72")break case 2:X(H,"1873-83")}break
case 15:switch X(I,"IS NORWAY PART OF SWEDEN?"+Y){case 1:X(H,"1896H905")break case 2:X(H,"1906-09")}break
case 16:switch X(I,"AUSTRIA-HUNGARY?"+Y){case 1:X(17)break case 2:X(18)}break
case 17:switch X(I,"ALBANIA?"+Y){case 2:X(H,"1910H2")break case 1:X(H,"1913H8")}break
case 18:switch X(I,"LENINGRAD?"+Y){case 2:X(H,"1919-23")break case 1:X(H,"1924-29")}break
case 19:switch X(I,"DOES THE OTTOMAN EMPIRE EXIST?"+Y){case 1:X(2)break case 2:X(20)}break
case 20:switch X(I,"THE SOVIET UNION?"+Y){case 2:X(21)break case 1:X(63)}break
case 21:switch X(I,"NORTH KOREA?"+Y){case 2:X(22)break case 1:X(56)}break
case 22:switch X(I,"SAINT TRIMBLE'S ISLAND?"+Y){case 2:X(23)break case 1:X(H,"NO, I MADE THAT ONE UP.")}break
case 23:switch X(I,"IS JAN MAYEN PART OF THE KINGDOM OF NORWAY?##NOT YET (1), WHAT? (2), YES (3)"){case 1:X(2)break case 2:X(24)break case 3:X(49)}break
case 24:switch X(I,"CAN YOU SEE THE FAMILIAR CONTINENTS?"+Y){case 1:X(25)break case 2:X(31)}break
case 25:switch X(I,"THIS SOUNDS LIKE A PHYSICAL MAP OR SATELLITE PHOTO.##YES, THAT'S IT (1)"){case 1:X(26)}break
case 26:switch X(I,"IS LAKE CHAD MISSING?"+Y){case 2:X(27)break case 1:X(30)}break
case 27:switch X(I,"HOW FAR EAST DO THE AMERICAN PRAIRIES REACH?##INDIANA (1), THE MISSISSIPPI (2), NEBRASKA (3), WHAT PRAIRIES? (4)"){case 1:X(H,"BEFORE 1830")break case 2:X(H,"1830s-80s")break case 3:X(28)break case 4:X(29)}break
case 28:switch X(I,I+"SOUTHERN CALIFORNIA? (CREATED BY MISTAKE)"+Y){case 2:X(H,"1860sH900s")break case 1:X(H,"1910s")}break
case 29:switch X(I,I+"GHANA? (CREATED ON PURPOSE)"+Y){case 2:X(H,"1920s-50s")break case 1:X(H,"1960s-70s")}break
case 30:switch X(I,"IS THE ARAL SEA MISSING?"+Y){case 2:X(H,"1970s-90s")break case 1:X(H,"2000s+")}break
case 31:switch X(I,'RIVERS "SIRION" OR "ANDUIN"?'+Y){case 1:X(32)break case 2:X(36)}break
case 32:switch X(I,"MORDOR?"+Y){case 2:X(33)break case 1:X(34)}break
case 33:switch X(I,"BELERIAND?"+Y){case 1:X(H,"FIRST AGE")break case 2:X(H,"EARLY SECOND AGE")}break
case 34:switch X(I,"NÚMENOR?"+Y){case 1:X(H,"LATE SECOND AGE")break case 2:X(35)}break
case 35:switch X(I,"THE FOREST EAST OF THE MISTY MOUNTAINS IS...##GREENWOOD THE GREAT (1), MIRKWOOD (2), THE WOOD OF GREENLEAVES (3)"){case 1:X(H,"EARLY THIRD AGE")break case 2:X(H,"LATE THIRD AGE")break case 3:X(H,"FOURTH AGE")}break
case 36:switch X(I,"CAIR PARAVEL?"+Y){case 1:X(37)break case 2:X(41)}break
case 37:switch X(I,"CALORMEN?"+Y){case 2:X(38)break case 1:X(40)}break
case 38:switch X(I,"LOTTA ISLANDS?"+Y){case 2:X(39)break case 1:X(H,"DAWN TREADER")}break
case 39:switch X(I,"BERUNA##FORD (1), BRIDGE (2)"){case 1:X(H,"THE LION, THE WITCH, AND THE WARDROBE")break case 2:X(H,"PRINCE CASPIAN")}break
case 40:switch X(I,"WEIRD RECURSIVE HEAVEN?"+Y){case 2:X(H,"ONE OF THE RANDOM LATER BOOKS")break case 1:X(H,"THE LAST BATTLE")}break
case 41:switch X(I,"MOSSFLOWER?"+Y){case 1:X(H,"REDWALL")break case 2:X(42)}break
case 42:switch X(I,"IS THE WORLD ON THE BACK OF A TURTLE?"+Y){case 1:X(H,"DISCWORLD")break case 2:X(43)}break
case 43:switch X(I,"ARE YOU SURE THIS IS A MAP?"+Y){case 1:X(44)break case 2:X(46)}break
case 44:switch X(I,"DID YOU MAKE IT YOURSELF?##YES (1)"){case 1:X(45)}break
case 45:X(I,"IT'S VERY NICE.##THANK YOU! (1)")break
case 46:switch X(I,"IS IT TRYING TO BITE YOU?"+Y){case 2:X(47)break case 1:X(48)}break
case 47:switch X(I,"IS IT LARGER THAN A BREADBOX?"+Y+", ABOUT THE SAME (3)"){case 1:X(H,"TUBA")break case 2:X(H,"STAPLER")break case 3:X(H,"BREADBOX")}break
case 48:switch X(I,"IF YOU LET IT GO, WHAT DOES IT DO?##HISSES AND RUNS AWAY (1), SCREECHES AND FLAPS AROUND THE ROOM BREAKING THINGS (2)"){case 1:X(H,"CAT")break case 2:X(H,"SEAGULL")}break
case 49:switch X(I,"PAKISTAN?"+Y){case 2:X(50)break case 1:X(52)}break
case 50:switch X(I,H+"GERMANYS ARE THERE?##ONE (1), ONE, BUT IT'S HUGE (2), TWO (3)"){case 1:X(51)break case 2:X(H,"1941-45")break case 3:X(H,"1946-47")}break
case 51:switch X(I,"PERSIA OR IRAN?##PERSIA (1), IRAN (2)"){case 1:X(H,"1930-34")break case 2:X(H,"1935-40")}break
case 52:switch X(I,"CAMBODIA?"+Y){case 2:X(53)break case 1:X(55)}break
case 53:switch X(I,"ERITREA IS A PART OF...##ITALY (1), ETHIOPIA (2)"){case 1:X(54)break case 2:X(H,"1952-53")}break
case 54:switch X(I,"CANADA IS...##MISSING A PIECE (1), FINE (2)"){case 1:X(H,"1948")break case 2:X(H,"1949-52")}break
case 55:switch X(I,"THE UNITED ARAB REPUBLIC?"+Y){case 2:X(H,"1954-57")break case 1:X(H,"1958-60")}break
case 56:switch X(I,'ZAIRE? OR: "HONG KONG (UK)"'+Y){case 1:X(H,"1992-96")break case 2:X(57)}break
case 57:switch X(I,"SERBIA AND MONTENEGRO ARE...##ONE COUNTRY (1), TWO COUNTRIES (2)"){case 1:X(58)break case 2:X(59)}break
case 58:switch X(I,"EAST TIMOR?"+Y){case 2:X(H,"1997-2001")break case 1:X(H,"2002-06")}break
case 59:switch X(I,H+"SUDANS ARE THERE?##ONE (1), TWO (2)"){case 1:X(H,"2007H1")break case 2:X(60)}break
case 60:switch X(I,"IS CRIMEA DISPUTED?"+Y){case 1:X(61)break case 2:X(H,"2012H3")}break
case 61:switch X(I,'"COLORADO" OR "DANGER-RADIOACTIVE EXCLUSION ZONE-AVOID"?##COLORADO (1), DANGER (2)'){case 1:X(H,"2014-21")break case 2:X(62)}break
case 62:switch X(I,"DOES THE WARNING MENTION THE SPIDERS?"+Y){case 2:X(H,"2022")break case 1:X(H,"2023 OR LATER")}break
case 63:switch X(I,"SAUDI ARABIA?"+Y){case 2:X(H,"1922-32")break case 1:X(64)}break
case 64:switch X(I,"IS MOST OF WEST AFRICA A GIANT FRENCH BLOB?"+Y){case 1:X(49)break case 2:X(65)}break
case 65:switch X(I,H+"VIETNAMS ARE THERE?##TWO (1), ONE (2)"){case 1:X(66)break case 2:X(69)}break
case 66:switch X(I,"BANGLADESH?"+Y){case 2:X(67)break case 1:X(H,"1972-75")}break
case 67:switch X(I,"IS THE AREA SOUTH OF LAKE VICTORIA...##BRITISH (1), TANGANYIKA (2), TANZANIA (3)"){case 1:X(68)break case 2:X(H,"1961-64")break case 3:X(H,"1965-71")}break
case 68:switch X(I,"THE TOWN ON I-25 BETWEEN ALBUQUERQUE AND EL PASO IS...##HOT SPRINGS (1), TRUTH OR CONSEQUENCES (2)"){case 1:X(H,"1948-49")break case 2:X(H,"1950-52")}break
case 69:switch X(I,"JIMMY CARTER IS...##BEING ATTACKED BY A GIANT SWIMMING RABBIT (1), FINE (2)"){case 1:X(H,"APRIL 20, 1979")break case 2:X(70)}break
case 70:switch X(I,"THE SINAI IS PART OF WHAT COUNTRY?## ISRAEL (1), MOSTLY ISRAEL (2), MOSTLY EGYPT (3), EGYPT (4)"){case 1:X(H,"1976-79")break case 2:X(H,"1980")break case 3:X(H,"1981")break case 4:X(71)}break
case 71:switch X(I,"WHAT'S THE CAPITAL OF MICRONESIA?## KOLONIA (1), PALIKIR (2)"){case 1:X(72)break case 2:X(73)}break
case 72:switch X(I,"REPUBLIC OF THE UPPER VOLTA OR BURKINA FASO?## UPPER VOLTA (1), BURKINA FASO (2)"){case 1:X(H,"1982-84")break case 2:X(H,"1985-88")}break
case 73:switch X(I,"(NUMBER OF YEMENS)+(NUMBER OF GERMANYS)=?## FOUR (1), THREE (2), TWO (3)"){case 1:X(H,"1989-EARLY 1990")break case 2:X(H,"MIDH990")break case 3:X(H,"LATE 1990H991")}break
case 74:switch X(I,"DOES THE SOVIET UNION EXIST?"+Y){case 1:X(64)break case 2:X(56)}break}

```

`#` is the newline character.

**How to run**

* New `.gmk` file
* Create a script `X` with contents as above
* Create an object `O` with Create Event: execute code: `X(1)`
* Create a room `R` and put one instance of `O` in it
* Run the game

**Golfing**

* The option `YES` now always precedes `NO`, and we define the string `Y="##YES (1), NO (2)"` for reuse.
* `"IS THERE A BIG LAKE IN THE MIDDLE OF "` and `"HOW MANY "` are long enough and occur sufficiently many times for abbreviation to pay off. They are assigned to `I` and `H`.
* In Game Maker, any user-defined function usually must be done in a separate script. The consensus on the policy for counting bytes for multi-file programs, was that *"If files are reused ... count the contents of that file as many times as you use it"*. As such, we use `X` itself, rather than a separate script, to abbreviate `get_integer` and `show_message`. Explicitly,
    + If `X` is called with zeroth argument `H`, then it returns `show_message` of the first argument.
    + If `X` is called with zeroth argument `I`, then it returns `get_integer` of the first argument, showing default input `1`.

**Ungolfed**, with options in the original order and no abbreviations at all:

```
// script X, takes node number, prompts question and returns message or calls X with next node number

switch argument0
{
case 1: switch get_integer("ISTANBUL OR CONSTANTINOPLE##CONSTANTINOPLE (1), NEITHER (2), ISTANBUL(3)",1)
  {
    case 1: X(2); break;
    case 2: X(19); break;
    case 3: X(74); break;
  }; break;
case 2: switch get_integer("DO ANY OF THESE EXIST?#- INDEPENDENT CANADA#- US TERRITORY OF ALASKA#- TOKYO##NO (1), YES (2)",1)
  {
    case 1: X(3); break;
    case 2: X(11); break;
  }; break;
case 3: switch get_integer("THE HOLY ROMAN EMPIRE?##YES (1), NO (2)",1)
  {
    case 1: show_message("1805 OR EARLIER (BEFORE THIS POINT, THE MODERN IDEA OF A COMPLETE POLITICAL MAP OF THE WORLD GETS HARD TO APPLY.)"); break;
    case 2: X(4); break;
  }; break;
case 4: switch get_integer("THE UNITED STATES?##NO (1), YES (2)",1)
  {
    case 1: show_message("HOW SURE ARE YOU THAT THIS MAP IS IN ENGLISH"); break;
    case 2: X(5); break;
  }; break;
case 5: switch get_integer("TEXAS IS...##PART OF MEXICO (1), INDEPENDENT (2), PART OF THE US (3)",1)
  {
    case 1: X(6); break;
    case 2: show_message("1834-45"); break;
    case 3: X(9); break;
  }; break;
case 6: switch get_integer("FLORIDA IS PART OF...##SPAIN (1), THE US (2)",1)
  {
    case 1: X(7); break;
    case 2: X(8); break;
  }; break;
case 7: switch get_integer("PARAGUAY?##NO (1), YES (2)",1)
  {
    case 1: show_message("1806-10"); break;
    case 2: show_message("1811-17"); break;
  }; break;
case 8: switch get_integer("VENEZUELA AND/OR ECUADOR?##NO (1), YES (2)",1)
  {
    case 1: show_message("1818-29"); break;
    case 2: show_message("1830-33"); break;
  }; break;
case 9: switch get_integer("DOES RUSSIA BORDER THE SEA OF JAPAN?##NO (1), YES (2)",1)
  {
    case 1: X(10); break;
    case 2: show_message("1858-67"); break;
  }; break;
case 10: switch get_integer("THE US'S SOUTHERN BORDER LOOKS...##WEIRD (1), NORMAL (2)",1)
  {
    case 1: show_message("1846-53"); break;
    case 2: show_message("1854-56"); break;
  }; break;
case 11: switch get_integer("SOUTH AFRICA?##NO (1), YES (2)",1)
  {
    case 1: X(12); break;
    case 2: X(16); break;
  }; break;
case 12: switch get_integer("RHODESIA?##NO (1), YES (2)",1)
  {
    case 1: X(13); break;
    case 2: X(15); break;
  }; break;
case 13: switch get_integer("IS BOLIVIA LANDLOCKED?##NO (1), YES (2)",1)
  {
    case 1: X(14); break;
    case 2: show_message("1884-95"); break;
  }; break;
case 14: switch get_integer('"BUDA" AND "PEST" OR "BUDAPEST"?##BUDA AND PEST (1), BUDAPEST (2)',1)
  {
    case 1: show_message("1868-72"); break;
    case 2: show_message("1873-83"); break;
  }; break;
case 15: switch get_integer("IS NORWAY PART OF SWEDEN?##YES (1), NO (2)",1)
  {
    case 1: show_message("1896-1905"); break;
    case 2: show_message("1906-09"); break;
  }; break;
case 16: switch get_integer("AUSTRIA-HUNGARY?##YES (1), NO (2)",1)
  {
    case 1: X(17); break;
    case 2: X(18); break;
  }; break;
case 17: switch get_integer("ALBANIA?##NO (1), YES (2)",1)
  {
    case 1: show_message("1910-12"); break;
    case 2: show_message("1913-18"); break;
  }; break;
case 18: switch get_integer("LENINGRAD?##NO (1), YES (2)",1)
  {
    case 1: show_message("1919-23"); break;
    case 2: show_message("1924-29"); break;
  }; break;
case 19: switch get_integer("DOES THE OTTOMAN EMPIRE EXIST?##YES (1), NO (2)",1)
  {
    case 1: X(2); break;
    case 2: X(20); break;
  }; break;
case 20: switch get_integer("THE SOVIET UNION?##NO (1), YES (2)",1)
  {
    case 1: X(21); break;
    case 2: X(63); break;
  }; break;
case 21: switch get_integer("NORTH KOREA?##NO (1), YES (2)",1)
  {
    case 1: X(22); break;
    case 2: X(56); break;
  }; break;
case 22: switch get_integer("SAINT TRIMBLE'S ISLAND?##NO (1), YES (2)",1)
  {
    case 1: X(23); break;
    case 2: show_message("NO, I MADE THAT ONE UP."); break;
  }; break;
case 23: switch get_integer("IS JAN MAYEN PART OF THE KINGDOM OF NORWAY?##NOT YET (1), WHAT? (2), YES (3)",1)
  {
    case 1: X(2); break;
    case 2: X(24); break;
    case 3: X(49); break;
  }; break;
case 24: switch get_integer("CAN YOU SEE THE FAMILIAR CONTINENTS?##YES (1), NO (2)",1)
  {
    case 1: X(25); break;
    case 2: X(31); break;
  }; break;
case 25: switch get_integer("THIS SOUNDS LIKE A PHYSICAL MAP OR SATELLITE PHOTO.##YES, THAT'S IT (1)",1)
  {
    case 1: X(26); break;
  }; break;
case 26: switch get_integer("IS LAKE CHAD MISSING?##NO (1), YES (2)",1)
  {
    case 1: X(27); break;
    case 2: X(30); break;
  }; break;
case 27: switch get_integer("HOW FAR EAST DO THE AMERICAN PRAIRIES REACH?##INDIANA (1), THE MISSISSIPPI (2), NEBRASKA (3), WHAT PRAIRIES? (4)",1)
  {
    case 1: show_message("BEFORE 1830"); break;
    case 2: show_message("1830s-80s"); break;
    case 3: X(28); break;
    case 4: X(29); break;
  }; break;
case 28: switch get_integer("IS THERE A BIG LAKE IN THE MIDDLE OF SOUTHERN CALIFORNIA? (CREATED BY MISTAKE)##NO (1), YES (2)",1)
  {
    case 1: show_message("1860s-1900s"); break;
    case 2: show_message("1910s"); break;
  }; break;
case 29: switch get_integer("IS THERE A BIG LAKE IN THE MIDDLE OF GHANA? (CREATED ON PURPOSE)##NO (1), YES (2)",1)
  {
    case 1: show_message("1920s-50s"); break;
    case 2: show_message("1960s-70s"); break;
  }; break;
case 30: switch get_integer("IS THE ARAL SEA MISSING?##NO (1), YES (2)",1)
  {
    case 1: show_message("1970s-90s"); break;
    case 2: show_message("2000s+"); break;
  }; break;
case 31: switch get_integer('RIVERS "SIRION" OR "ANDUIN"?##YES (1), NO (2)',1)
  {
    case 1: X(32); break;
    case 2: X(36); break;
  }; break;
case 32: switch get_integer("MORDOR?##NO (1), YES (2)",1)
  {
    case 1: X(33); break;
    case 2: X(34); break;
  }; break;
case 33: switch get_integer("BELERIAND?##YES (1), NO (2)",1)
  {
    case 1: show_message("FIRST AGE"); break;
    case 2: show_message("EARLY SECOND AGE"); break;
  }; break;
case 34: switch get_integer("NÚMENOR?##YES (1), NO (2)",1)
  {
    case 1: show_message("LATE SECOND AGE"); break;
    case 2: X(35); break;
  }; break;
case 35: switch get_integer("THE FOREST EAST OF THE MISTY MOUNTAINS IS...##GREENWOOD THE GREAT (1), MIRKWOOD (2), THE WOOD OF GREENLEAVES (3)",1)
  {
    case 1: show_message("EARLY THIRD AGE"); break;
    case 2: show_message("LATE THIRD AGE"); break;
    case 3: show_message("FOURTH AGE"); break;
  }; break;
case 36: switch get_integer("CAIR PARAVEL?##YES (1), NO (2)",1)
  {
    case 1: X(37); break;
    case 2: X(41); break;
  }; break;
case 37: switch get_integer("CALORMEN?##NO (1), YES (2)",1)
  {
    case 1: X(38); break;
    case 2: X(40); break;
  }; break;
case 38: switch get_integer("LOTTA ISLANDS?##NO (1), YES (2)",1)
  {
    case 1: X(39); break;
    case 2: show_message("DAWN TREADER"); break;
  }; break;
case 39: switch get_integer("BERUNA##FORD (1), BRIDGE (2)",1)
  {
    case 1: show_message("THE LION, THE WITCH, AND THE WARDROBE"); break;
    case 2: show_message("PRINCE CASPIAN"); break;
  }; break;
case 40: switch get_integer("WEIRD RECURSIVE HEAVEN?##NO (1), YES (2)",1)
  {
    case 1: show_message("ONE OF THE RANDOM LATER BOOKS"); break;
    case 2: show_message("THE LAST BATTLE"); break;
  }; break;
case 41: switch get_integer("MOSSFLOWER?##YES (1), NO (2)",1)
  {
    case 1: show_message("REDWALL"); break;
    case 2: X(42); break;
  }; break;
case 42: switch get_integer("IS THE WORLD ON THE BACK OF A TURTLE?##YES (1), NO (2)",1)
  {
    case 1: show_message("DISCWORLD"); break;
    case 2: X(43); break;
  }; break;
case 43: switch get_integer("ARE YOU SURE THIS IS A MAP?##YES (1), NO (2)",1)
  {
    case 1: X(44); break;
    case 2: X(46); break;
  }; break;
case 44: switch get_integer("DID YOU MAKE IT YOURSELF?##YES (1)",1)
  {
    case 1: X(45); break;
  }; break;
case 45: switch get_integer("IT'S VERY NICE.##THANK YOU! (1)",1)
  {
    case 1: break;
  }; break;
case 46: switch get_integer("IS IT TRYING TO BITE YOU?##NO (1), YES (2)",1)
  {
    case 1: X(47); break;
    case 2: X(48); break;
  }; break;
case 47: switch get_integer("IS IT LARGER THAN A BREADBOX?##YES (1), NO (2), ABOUT THE SAME (3)",1)
  {
    case 1: show_message("TUBA") break;
    case 2: show_message("STAPLER") break;
    case 3: show_message("BREADBOX") break;
  }; break;
case 48: switch get_integer("IF YOU LET IT GO, WHAT DOES IT DO?##HISSES AND RUNS AWAY (1), SCREECHES AND FLAPS AROUND THE ROOM BREAKING THINGS (2)",1)
  {
    case 1: show_message("CAT") break;
    case 2: show_message("SEAGULL") break;
  }; break;
case 49: switch get_integer("PAKISTAN?##NO (1), YES (2)",1)
  {
    case 1: X(50); break;
    case 2: X(52); break;
  }; break;
case 50: switch get_integer("HOW MANY GERMANYS ARE THERE?##ONE (1), ONE, BUT IT'S HUGE (2), TWO (3)",1)
  {
    case 1: X(51); break;
    case 2: show_message("1941-45") break;
    case 3: show_message("1946-47") break;
  }; break;
case 51: switch get_integer("PERSIA OR IRAN?##PERSIA (1), IRAN (2)",1)
  {
    case 1: show_message("1930-34") break;
    case 2: show_message("1935-40") break;
  }; break;
case 52: switch get_integer("CAMBODIA?##NO (1), YES (2)",1)
  {
    case 1: X(53); break;
    case 2: X(55); break;
  }; break;
case 53: switch get_integer("ERITREA IS A PART OF...##ITALY (1), ETHIOPIA (2)",1)
  {
    case 1: X(54); break;
    case 2: show_message("1952-53"); break;
  }; break;
case 54: switch get_integer("CANADA IS...##MISSING A PIECE (1), FINE (2)",1)
  {
    case 1: show_message("1948"); break;
    case 2: show_message("1949-52"); break;
  }; break;
case 55: switch get_integer("THE UNITED ARAB REPUBLIC?##NO (1), YES (2)",1)
  {
    case 1: show_message("1954-57"); break;
    case 2: show_message("1958-60"); break;
  }; break;
case 56: switch get_integer('ZAIRE? OR: "HONG KONG (UK)"##YES (1), NO (2)',1)
  {
    case 1: show_message("1992-96"); break;
    case 2: X(57); break;
  }; break;
case 57: switch get_integer("SERBIA AND MONTENEGRO ARE...##ONE COUNTRY (1), TWO COUNTRIES (2)",1)
  {
    case 1: X(58); break;
    case 2: X(59); break;
  }; break;
case 58: switch get_integer("EAST TIMOR?##NO (1), YES (2)",1)
  {
    case 1: show_message("1997-2001"); break;
    case 2: show_message("2002-06"); break;
  }; break;
case 59: switch get_integer("HOW MANY SUDANS ARE THERE?##ONE (1), TWO (2)",1)
  {
    case 1: show_message("2007-11"); break;
    case 2: X(60); break;
  }; break;
case 60: switch get_integer("IS CRIMEA DISPUTED?##YES (1), NO (2)",1)
  {
    case 1: X(61); break;
    case 2: show_message("2012-13"); break;
  }; break;
case 61: switch get_integer('"COLORADO" OR "DANGER-RADIOACTIVE EXCLUSION ZONE-AVOID"?##COLORADO (1), DANGER (2)',1)
  {
    case 1: show_message("2014-21"); break;
    case 2: X(62); break;
  }; break;
case 62: switch get_integer("DOES THE WARNING MENTION THE SPIDERS?##NO (1), YES (2)",1)
  {
    case 1: show_message("2022"); break;
    case 2: show_message("2023 OR LATER"); break;
  }; break;
case 63: switch get_integer("SAUDI ARABIA?##NO (1), YES (2)",1)
  {
    case 1: show_message("1922-32"); break;
    case 2: X(64); break;
  }; break;
case 64: switch get_integer("IS MOST OF WEST AFRICA A GIANT FRENCH BLOB?##YES (1), NO (2)",1)
  {
    case 1: X(49); break;
    case 2: X(65); break;
  }; break;
case 65: switch get_integer("HOW MANY VIETNAMS ARE THERE?##TWO (1), ONE (2)",1)
  {
    case 1: X(66); break;
    case 2: X(69); break;
  }; break;
case 66: switch get_integer("BANGLADESH?##NO (1), YES (2)",1)
  {
    case 1: X(67); break;
    case 2: show_message("1972-75"); break;
  }; break;
case 67: switch get_integer("IS THE AREA SOUTH OF LAKE VICTORIA...##BRITISH (1), TANGANYIKA (2), TANZANIA (3)",1)
  {
    case 1: X(68); break;
    case 2: show_message("1961-64"); break;
    case 3: show_message("1965-71"); break;
  }; break;
case 68: switch get_integer("THE TOWN ON I-25 BETWEEN ALBUQUERQUE AND EL PASO IS...##HOT SPRINGS (1), TRUTH OR CONSEQUENCES (2)",1)
  {
    case 1: show_message("1948-49"); break;
    case 2: show_message("1950-52"); break;
  }; break;
case 69: switch get_integer("JIMMY CARTER IS...##BEING ATTACKED BY A GIANT SWIMMING RABBIT (1), FINE (2)",1)
  {
    case 1: show_message("APRIL 20, 1979"); break;
    case 2: X(70); break;
  }; break;
case 70: switch get_integer("THE SINAI IS PART OF WHAT COUNTRY?## ISRAEL (1), MOSTLY ISRAEL (2), MOSTLY EGYPT (3), EGYPT (4)",1)
  {
    case 1: show_message("1976-79"); break;
    case 2: show_message("1980"); break;
    case 3: show_message("1981"); break;
    case 4: X(71); break;
  }; break;
case 71: switch get_integer("WHAT'S THE CAPITAL OF MICRONESIA?## KOLONIA (1), PALIKIR (2)",1)
  {
    case 1: X(72); break;
    case 2: X(73); break;
  }; break;
case 72: switch get_integer("REPUBLIC OF THE UPPER VOLTA OR BURKINA FASO?## UPPER VOLTA (1), BURKINA FASO (2)",1)
  {
    case 1: show_message("1982-84"); break;
    case 2: show_message("1985-88"); break;
  }; break;
case 73: switch get_integer("(NUMBER OF YEMENS)+(NUMBER OF GERMANYS)=?## FOUR (1), THREE (2), TWO (3)",1)
  {
    case 1: show_message("1989-EARLY 1990"); break;
    case 2: show_message("MID-1990"); break;
    case 3: show_message("LATE 1990-1991"); break;
  }; break;
case 74: switch get_integer("DOES THE SOVIET UNION EXIST?## YES (1), NO (2)",1)
  {
    case 1: X(64); break;
    case 2: X(56); break;
  }; break;
}

```

**Numbering system**

* Version 1: before reordering of `YES`, `NO` options to save bytes
* Version 2 (current): (reordered option numbers in black)
> 8 votes

---
Tags: code-golf, kolmogorov-complexity
---


title: A Triangular Slice of Squared Pi

text:
# Question
Title: A Triangular Slice of Squared Pi
*Inspired by Bake a slice of Pi*

### Challenge

Given input `3 <= n <= 100` and `3 <= y <= n`, construct an `n x n` matrix of the decimal portion of `pi` (`14159...`), starting in the top left. Then, take the upper-right triangle of size `y x y` and concatenate it together. Output the resulting number.

For example, for input `n = 5`, `y = 3`, the following matrix is constructed

```
14159
26535
89793
23846
26433

```

Then, the upper-right `3 x 3` triangle would be

```
159
 35
  3

```

so `159353` is the output.

### Input

Two integers -- `n` representing the size of the square matrix of the digits of pi, and `y` representing the upper-right triangle -- in any convenient format.

### Output

* The resulting sliced and concatenated number, either printed/displayed to the screen, returned as a string, etc.
* Trailing/leading whitespace is optional, so long as there's no whitespace *in* the output (i.e., `159 35 3` or the like would be invalid).
* Note that since we're explicitly looking for the digits of `pi`, and not an approximation or mathematical calculation, answers should not round the final digit of the matrix.

### Rules

* This is so all the usual rules for golfing apply, and the shortest code (in bytes) wins.
* Either a full program or function are acceptable.
* Standard loopholes are forbidden.

### Examples

```
 n  y  output
-------------
 3  3  141923
 5  3  159353
 6  4  1592589383
 6  6  141592535893238643794
20 12  358979323846950288419715820974944628620899211706792306647223172745025559196615

```

# Answer
# 05AB1E, 19 bytes

Uses CP-1252 encoding.

```
nžs¦¦¹ôI£íRvyN>£J}R

```

Try it online!

**Explanation**

`n=5, y=3` used for example

```
nžs                  # push pi to n^2 digits
                     # STACK: 3.1415926535897932384626433
   ¦¦                # remove the first 2 chars
                     # STACK: 1415926535897932384626433
     ¹ô              # split into n*n matrix
                     # STACK: ['14159', '26535', '89793', '23846', '26433']
       I£            # keep the first y rows
                     # STACK: ['14159', '26535', '89793']
         íR          # reverse the list of rows and each individual row
                     # STACK: ['39798', '53562', '95141']
           v     }   # for each y,N (row, index) in the list
            yN>£J    # keep the first index+1 digits of the row and join to string
                     # STACK: 353951
                  R  # reverse the string
                     # STACK: 159353
                     # implicit print

```
> 7 votes

# Answer
# Python 2 (with sympy), 100 bytes

```
from sympy import*
lambda n,y:''.join(c for i,c in enumerate(`pi.round(n*n+1)`[2:])if i%n-i/n>n-y-1)

```

---

### No sympy, ~~260 246 244 233 231~~ 218 bytes

```
p=lambda n,y,a=-30,b=10,c=3,d=2,e=0,f=5,s='',i=0:i<n*n and p(n,y,*[((2*b+a)*f,b*d,c*f,d+1,(b*(7*d)+2+(a*f))/(c*f),f+2,s,i),(10*(a-e*c),10*b,c,d,((10*(3*b+a))/c)-10*e,f,s+(str(e)[:i%n-i/n>n-y-1]),i+1)][4*b+a-c<e*c])or s

```

This employs "The Spigot Algorithm For Pi" of Stanley Rabinowitz and Stan Wagon.

The standard arguments would be `a,b,c,d,e,f=0,1,1,1,3,3` to yield the first digit of pi, `3`, since that is not required the algorithm is initialised to the point before `1` is yielded, which saves two bytes even though `a` and `b` are longer as the result does not require slicing and `i` can start at `0` rather than `-1`.

Hits default recursion limit for last test case
Uses `//` for the first of the divisions so that `str(v)` may be replaced by ``v`` (otherwise it would end in `L` for a long).
**repl.it**

---

A non-recursive version for 232 bytes which evaluates the last test case too:

```
def p(n,y):
 a,b,c,d,e,f,i,s=-30,10,3,2,0,5,0,''
 while i<n*n:
    if 4*b+a-c<e*c:s+=`e`[:i%n-i/n>n-y-1];g=10*(a-e*c);e=((10*(3*b+a))//c)-10*e;b*=10;i+=1
    else:g=(2*b+a)*f;h=(b*(7*d)+2+(a*f))/(c*f);b*=d;c*=f;f+=2;d+=1;e=h
    a=g
 print s

```

**repl.it** (first indent is one space, second indent is one tab)
> 5 votes

# Answer
# Mathematica, 82 bytes

```
Print@@Join@@Partition[RealDigits[Pi-3,10,#^2][[1]],#][[i,i-#2-1;;]]~Table~{i,#2}&

```
> 4 votes

# Answer
# MATL, ~~23~~ ~~22~~ 27 bytes

*1 Byte saved thanks to @Luis*

```
UtEYPwY$IbH+&:)GetGi-&R!g)!

```

**Try it Online**

**Explanation**

```
        % Implicitly grab input (n)
Ut      % Square n and duplicate
E       % Multiply n^2 by 2
YP      % Pi literal
w       % Flip the stack
Y$      % Compute the first 2 * (n^2) digits of pi (accounts for rounding)
IbH+&:) % Grab the first n^2 digits after the decimal
Ge      % Reshape it into an n x n matrix in row-major ordering
t       % Duplicate this matrix
Gi-     % Grab the second input (y) and compute the difference between n and y
&R!     % Get the upper diagonal part and transpose to convert to lower diagonal
g)      % Convert it to a logical array and use it to select the digits of interest
!       % Transpose the result and implicitly display

```
> 3 votes

# Answer
# Perl, 67 bytes

```
s/ /bpi++$_**2/e;$%=$';$%-=print/(.{$%})$/ for/\d{$`}/g

```

Requires the command line option `-nMbignum=bpi`, counted as 12. Input is taken from stdin.

**Sample Usage**

```
$ echo 3 3 | perl -nMbignum=bpi primo-square-pi.pl
141923

$ echo 5 3 | perl -nMbignum=bpi primo-square-pi.pl
159353

$ echo 6 4 | perl -nMbignum=bpi primo-square-pi.pl
1592589383

$ echo 6 6 | perl -nMbignum=bpi primo-square-pi.pl
141592535893238643794

$ echo 20 12 | perl -nMbignum=bpi primo-square-pi.pl
358979323846950288419715820974944628620899211706792306647223172745025559196615

```
> 2 votes

# Answer
# C#, 232 bytes 268 bytes

Edit:

I originally used a constant string for Pi outside of the method, but it seems this was cheating. I've had to use the C# Math.PI value, which only has 14 decimal places, so the highest `m` value I can use is 3. Back to the drawing board...

Golfed:

```
IEnumerable<string>f(int m,int t){var a=new string[m, m];var b=Math.PI.ToString().Replace("3.","").Substring(0,m*m).ToArray();var c=0;for(int i=0;i<m;i++){for(int j=0;j<m;j++){a[i, j]=b[c]+"";c++;}}c=0;while(t>0){for(int i=t;i>0;i--){yield return a[c,m-i];}t--;c++;}}}

```

Ungolfed:

```
  class ATriangularSliceOfSquaredPi
  {
    //http://www.piday.org/million/
    //const string p = "1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679821480865132823066470938446095505822317253594081284811174502841027019385211055596446229489549303819644288109756659334461284756482337867831";

    public IEnumerable<string> f(int m, int t)
        {
          var a = new string[m, m];

          //var b = p.Substring(0, m * m).ToArray();
          var b = Math.PI.ToString().Replace("3.", "").Substring(0, m * m).ToArray();

          var c = 0;

          for (int i = 0; i < m; i++)
          {
            for (int j = 0; j < m; j++)
            {
              a[i, j] = b[c] + "";
              c++;
            }
          }

          c = 0;

          while (t > 0)
          {
            for (int i = t; i > 0; i--)
            {
              yield return a[c, m - i];
            }
            t--;
            c++;
          }
        }
      }

```

Not the shortest answer, but I was just happy I solved this one...

Test Output:

```
m   t   output
3   3   141923

```

5 3 159353
6 4 1592589383
6 6 141592535893238643794
20 12 358979323846950288419715820974944628620899211706792306647223172745025559196615
> 0 votes

---
Tags: code-golf, pi
---


title: Write a self-aware program

text:
# Question
Title: Write a self-aware program
A standard (but disputed) test of self-awareness is the mirror test: An animal is considered self aware if it can recognize itself in the mirror.

Your task is to write a program that is self-aware according to this test. More exactly:

* The program reads input in whatever form is suitable for your language.
* If the input contains a mirror image of its own source code, it produces a truthy value, otherwise a falsey value.
* A valid mirror image is the exact source of the program with the order of characters reversed, with no extra characters in between. As a special exception, for systems/languages that don't use single characters to terminate/separate lines (e.g. using a CR/LF sequence), the line termination sequence is allowed, but not required to be kept intact on reversal. However the program must be consistent in its treatment of lines.

For example, on a system using CR/LF as line separator, the sequence `AB<cr><lf>CD` may be reversed either to `DC<cr><lf>BA` (keeping the line ending intact) or to `DC<lf><cr>BA` (completely reversing the character sequence).
* The mirror image must be detected also if it is preceded or followed by junk, even if that junk contains reversed fragments of the code.

This is code golf; the shortest entry wins.

Note this is *not* the same as this question because of (a) the reversal of the code, and (b) the fact that it has to tolerate junk before and after the reversed code, including junk that is very similar to the actual reversed code.

# Answer
## Retina, 1 byte

```
x

```

Try it online!

Prints a positive integer when the input contains at least one "reversed" copy of the source and `0` otherwise.

Any character that isn't a backtick or a regex metacharacter (`[()?*+\\^$.`) would work.
> 1 votes

---
Tags: code-golf, quine, subsequence
---


title: Fraction to exact decimal

text:
# Question
Title: Fraction to exact decimal
Write a program or function that given two integers *a, b* outputs a string containing a decimal number representing the fraction *a/b* **exactly**.

If *a/b* is integer, simply output the value, without a decimal dot or leading zeroes:

```
123562375921304812375087183597 / 2777 -> 44494913907563850333124661
81 / 3 -> 27
-6 / 2 -> -3

```

If *a/b* is not integer but has a finite representation in base 10, output the value without leading or trailing zeroes (except a single zero before the dot):

```
1 / 2 -> 0.5
3289323463 / -250000000 -> -13.157293852

```

Finally, if **and only if** (so no `0.999...`) *a/b* is not integer and does not have a finite representation, output the finite part followed by the repeating part in parenthesis. The repeating part must be as small as possible, and start as early as possible.

```
-1 / 3 -> -0.(3)
235 / 14 -> 16.7(857142)
123 / 321 -> 0.(38317757009345794392523364485981308411214953271028037)
355 / 113 -> 3.(1415929203539823008849557522123893805309734513274336283185840707964601769911504424778761061946902654867256637168)

```

---

Your program must work for all above examples in under 10 seconds on a modern desktop PC. Smallest program in bytes wins.

# Answer
# Perl 6,  ~~63 58~~  50 bytes

```
{->$a,$b {$a~"($b)"x?$b}(|($^a.FatRat/$^b).base-repeating(10))}

```

```
{->\a,$b {a~"($b)"x?$b}(|($^a.FatRat/$^b).base-repeating)}

```

```
{$/=($^a.FatRat/$^b).base-repeating;$0~"($1)"x?$1}

```

Test it

If you don't care that it will only work with denominators that fit into a 64 bit integer it can be shortened to just 43 bytes:

```
{$/=($^a/$^b).base-repeating;$0~"($1)"x?$1}

```

### Expanded:

```
{
  # store in match variable so that we can
  # use ｢$0｣ and ｢$1｣
  $/ = (

    # turn the first value into a FatRat so that
    # it will continue to work for all Int inputs
    $^a.FatRat / $^b

  ).base-repeating;

  # ｢$0｣ is short for ｢$/[0]｣ which is the non-repeating part
  $0

  # string concatenated with
  ~

  # string repeat once if $1 is truthy (the repeating part)
  # otherwise it will be an empty Str
  "($1)" x ?$1
}

```
> 4 votes

# Answer
## Python 2, 174 bytes

```
x,y=input()
a=abs(x)
b=abs(y)
r=a%b*10
L=[]
M=''
while~-(r in L):L+=r,;M+=str(r/b);r=r%b*10
i=L.index(r)
t=M[:i]+"(%s)"%M[i:]*(M[i:]>'0')
print"-%d."[x*y>=0:(t>'')+3]%(a/b)+t

```

I'm not quite convinced about the validity of this answer, but it's worked for the test cases above and other test cases I've thrown at it. It looks like a right mess though, so I'm sure there's plenty of room for golfing.

The initial setup takes absolute values of both arguments to ensure that we're dealing with nonnegative numbers (saving the sign calculation for later), and delegates the quotient part of the result to Python's arbitrary precision arithmetic. The fractional part is done with the grade-school division algorithm until we get a repeat in the remainder. We then look up when we last saw this repeat in order to get the period, and construct the string accordingly.

Note that the algorithm's actually quite slow due to the O(n) `in` operation, but it's fast enough for the examples.
> 9 votes

# Answer
## Batch, ~~349~~ 344 bytes

```
@echo off
set/ad=%2,i=%1/d,r=%1%%d
if not %r%==0 set i=%i%.&if %r% leq 0 set/ar=-r&if %i%==0 set i=-0.
set d=%d:-=%
set/ae=d
:g
if %r%==0 echo %i%&exit/b
set/ag=-~!(e%%2)*(!(e%%5)*4+1)
if not %g%==1 set/ae/=g&call:d&goto g
set/as=r
set i=%i%(
:r
call:d
if %r%==%s% echo %i%)&exit/b
goto r
:d
set/ar*=10,n=r/d,r%%=d
set i=%i%%n%

```

Edit: Saved 5 bytes by removing unnecessary characters. "Ungolfed":

```
@echo off
set /a d = %2
set /a i = %1 / d
set /a r = %1 % d
if not %r%==0 (
    set i=%i%.                  Decimal point is required
    if %r% leq 0 (
        set /a r = -r           Get absolute value of remainder
        if %i%==0 set i=-0.     Fix edge case (-1/3 = 0 remainder -1)
    )
)
set d = %d:-=%                  Get absolute value of divisor
set /a e = d
:g
if %r%==0 echo %i% & exit /b    Finished if there's no remainder
set /a g = gcd(e, 10)           Loop through nonrecurring decimals
if not %g%==1 (
    set /a e /= g
    call :d
    goto g
)
set /a s = r                    Save remainder to know when loop ends
set i=%i%(
:r
call :d
if %r%==%s% echo %i%)&exit/b
goto r
:d                              Add the next decimal place
set /a r *= 10
set /a n = r / d
set /a r %= d
set i=%i%%n%

```
> 5 votes

# Answer
# Java, 625 605

Golfed code:

```
import static java.math.BigInteger.*;
String f(BigInteger a, BigInteger b){BigInteger[]r=a.divideAndRemainder(b);String s=r[0].toString();if(r[1].signum()<0)s="-"+s;if(!ZERO.equals(r[1])){s+='.';List<BigInteger>x=new ArrayList();List<BigInteger>y=new ArrayList();for(BigInteger d=TEN.multiply(r[1].abs());;){BigInteger[]z=d.divideAndRemainder(b.abs());int i=y.indexOf(z[1]);if(i>-1&&i==x.indexOf(z[0])){for(int j=0;j<i;++j)s+=x.get(j);s+='(';for(int j=i;j<x.size();++j)s+=x.get(j);s+=')';break;}x.add(z[0]);y.add(z[1]);if(ZERO.equals(z[1])){for(BigInteger j:x)s+=j;break;}d=TEN.multiply(z[1]);}}return s;}

```

Note: I count the static import as part of the function for golfing purposes.

This function starts out by getting the division result. It adds the integral portion and sign, if necessary. Then if there is a remainder, it performs base 10 long division. At each step, perform the division. Store the calculated digit and the remainder in two lists. If we encounter the same digit and remainder again, there is a repeated portion and we know what index it starts at. The code either adds the digits (no repeat) or the pre-repeat digits, then the repeated digits enclosed in parentheses.

This is a bit big mostly because of `BigInteger`. If the inputs did not overflow even a `long` then it could be a bit shorter. Still, I expect there are ways to improve this entry.

Ungolfed code with main method for testing:

```
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.List;

import static java.math.BigInteger.*;

public class FractionToExactDecimal {

  public static void main(String[] args) {
    // @formatter:off
    String[][] testData = new String[][] {
      { "123562375921304812375087183597", "2777", "44494913907563850333124661" },
      { "81", "3", "27" },
      { "-6", "2", "-3" },
      { "1", "2", "0.5" },
      { "3289323463", "-250000000", "-13.157293852" },
      { "-1", "3", "-0.(3)" },
      { "235", "14", "16.7(857142)" },
      { "123", "321", "0.(38317757009345794392523364485981308411214953271028037)" },
      { "355", "113", "3.(1415929203539823008849557522123893805309734513274336283185840707964601769911504424778761061946902654867256637168)" }
    };
    // @formatter:on

    for (String[] data : testData) {
      System.out.println(data[0] + " / " + data[1]);
      System.out.println("  Expected -> " + data[2]);
      System.out.print("    Actual -> ");
      System.out.println(new FractionToExactDecimal().f(new BigInteger(data[0]), new BigInteger(data[1])));
      System.out.println();
    }
  }

  // Begin golf
  String f(BigInteger a, BigInteger b) {
    BigInteger[] r = a.divideAndRemainder(b);
    String s = r[0].toString();
    if (r[1].signum() < 0) s = "-" + s;
    if (!ZERO.equals(r[1])) {
      s += '.';
      List<BigInteger> x = new ArrayList();
      List<BigInteger> y = new ArrayList();
      for (BigInteger d = TEN.multiply(r[1].abs());;) {
        BigInteger[] z = d.divideAndRemainder(b.abs());
        int i = y.indexOf(z[1]);
        if (i > -1 && i == x.indexOf(z[0])) {
          for (int j = 0; j < i; ++j)
            s += x.get(j);
          s += '(';
          for (int j = i; j < x.size(); ++j)
            s += x.get(j);
          s += ')';
          break;
        }
        x.add(z[0]);
        y.add(z[1]);
        if (ZERO.equals(z[1])) {
          for (BigInteger j : x)
            s += j;
          break;
        }
        d = TEN.multiply(z[1]);
      }
    }
    return s;
  }
  // End golf
}

```

Program output:

```
123562375921304812375087183597 / 2777
  Expected -> 44494913907563850333124661
    Actual -> 44494913907563850333124661

81 / 3
  Expected -> 27
    Actual -> 27

-6 / 2
  Expected -> -3
    Actual -> -3

1 / 2
  Expected -> 0.5
    Actual -> 0.5

3289323463 / -250000000
  Expected -> -13.157293852
    Actual -> -13.157293852

-1 / 3
  Expected -> -0.(3)
    Actual -> -0.(3)

235 / 14
  Expected -> 16.7(857142)
    Actual -> 16.7(857142)

123 / 321
  Expected -> 0.(38317757009345794392523364485981308411214953271028037)
    Actual -> 0.(38317757009345794392523364485981308411214953271028037)

355 / 113
  Expected -> 3.(1415929203539823008849557522123893805309734513274336283185840707964601769911504424778761061946902654867256637168)
    Actual -> 3.(1415929203539823008849557522123893805309734513274336283185840707964601769911504424778761061946902654867256637168)

```
> 2 votes

# Answer
# PHP, 277 Bytes

```
list(,$n,$d)=$argv;$a[]=$n;$n-=$d*$r[]=$n/$d^0;!$n?:$r[]=".";while($n&&!$t){$n*=10;$n-=$d*$r[]=$n/$d^0;$t=in_array($n%=$d,$a);$a[]=$n;}if($t){$l=count($a)-($p=array_search(end($a),$a));echo join(array_slice($r,0,2+$p))."(".join(array_slice($r,2+$p,$l)).")";}else echo join($r);

```
> 1 votes

# Answer
# Mathematica 198 bytes

```
i=Integer;t=ToString;a_~h~b_:=f[a/b];f@q_i:= t@q;
f@q_:=""<>{t@IntegerPart[q],".",RealDigits[FractionalPart[q]][[1]]//.{{x___,{k__i}}:> {x,"("<>(t/@{k})<>")"},{x__i,j___String}:>""<> {""<>t/@{x},j}}}

```

---

## UnGolfed

```
(* hand over quotient of a, b to function f *)
h[a_, b_] := f[a/b];

(* if the quotient is an integer, return it as a string *)
f[q_Integer] := ToString@q;

(* otherwise, return the integer part, followed by a decimal point ...*)
f[q_] := "" <> {ToString@IntegerPart[q], ".",

   (* replacing the repeating part (if it exists) between parentheses *)
   RealDigits[FractionalPart[q]][[1]] //. {{x___, {i__Integer}} :> {x, "(" <>(ToString /@ {i}) <> ")"},

   (* and the non-repeating part (if it exists) without parentheses *)
   {x__Integer, i___String} :> "" <> {"" <> ToString /@ {x}, i}}}

```

---

## Tests

```
h @@@ {{81, 3}, {-81, 3}, {1, 4}, {-13, 3}, {19, 7}, {3289323463, 25000}, {235, 14}, {1325, 14}}

```

{"27", "-27", "0.25", "-4.(3)", "2.(714285)", "131572.93852", "16.7(857142)", "94.6(428571)"}
> 0 votes

---
Tags: code-golf, number, rational-numbers, restricted-time
---


title: Sobel edge detector

text:
# Question
Title: Sobel edge detector
Your task is to write a program that takes an input image and run it through edge-detection to become an output image.

The edge-detection works as follows (if unclear, see sobel edge detection):

* The value for a pixel is the total brightness of a pixel, so if it is in color, you will need to convert it to grayscale first (to keep things simple and golf-able, you can take the average value for R, G and B).
* The formulae for Gx and Gy for pixel p(i,j) are:
    + Gx = -1 * p(i-1, j-1) \- 2 * p(i-1, j) \- 1 * p(i-1, j+1) \+ 1 * p(i+1, j-1) \+ 2 * p(i+1, j) \+ 1 * p(i+1, j+1)
    + Gy = -1 * p(i-1, j-1) \- 2 * p(i, j-1) \- 1 * p(i+1, j-1) \+ 1 * p(i-1, j+1) \+ 2 * p(i, j+1) \+ 1 * p(i+1, j+1)
* The value for the size of the edge at that pixel is then: √(Gx2 \+ Gy2)

The output image is for each pixel the size of the edge √(Gx2 \+ Gy2) as greyscale.

Bonuses:

* Perform a gaussian blur to smooth out the image before edge-detection kicks in, to omit any smaller edges. This gives a bonus of -30% on the end result.
* Take the angle of the edge in account. You give the output pixel some color, by taking the same greyscale value and adding color from a color wheel using the angle obtained from the formula arctan(Gy/Gx). This gives another bonus of -30% on the end result.

Rules:

* You may omit the value for the edgepixels, and set them to black, or you may use 0 for any pixel outside the image.
* Your ouput image must be in an image format that can be opened on most computers.
* Output must be written to disk or be pipeable to a file.
* Input is given as a commandline argument, in the form of a relative path to the image, or piped in from the commandline.
* This is code golf, so shortest code in bytes wins!

# Answer
> 13 votes
# J, ~~166 164 161 154 150 144~~ 143 bytes.

Not golfed too much; I mostly collapsed my longer implementation (see below), so there's probably lots of room for improvement. Uses BMP library. Saves result in file `o`. I handled edgepixels by only using full 3x3 cells, so the final image has width and height smaller by 2 pixels.

```
load'bmp'
S=:s,.0,.-s=:1 2 1
p=:([:*:[:+/[:,*)"2
'o'writebmp~256#.3#"0<.255<.%:(S&p+(|:S)&p)3 3,.;._3(3%~])+/"1(3#256)#:readbmp}:stdin''
exit''

```

Usage:

```
echo 'image.bmp' | jconsole golf.ijs

```

Expanded:

```
load 'bmp'

sobel1 =: 3 3 $ 1 0 _1 2 0 _2 1 0 _1
NB. transposed
sobel2 =: |: sobel1
NB. read image
image =: readbmp }: stdin''
NB. convert default representation to R,G,B arrays
rgbimage =: (3 # 256) #: image
NB. convert to grayscale
greyimage =: 3 %~ (+/"1) rgbimage
NB. 3x3 cells around each pixel
cells =: 3 3 ,.;._3 greyimage
NB. multiply 3x3 cell by 3x3 sobel, then sum all values in it
partial =: 4 : '+/"1 +/"1 x *"2 y'
NB. square partial (vertical and horizontal) results, sum and root
combine =: [: %: *:@[ + *:@]
NB. limit RGB values to 255
limit =: 255 <. ]
newimage =: limit (sobel1&partial combine sobel2&partial) cells
NB. convert back to J-friendly representation
to_save =: 256 #. 3 #"0 <. newimage
to_save writebmp 'out.bmp'
NB. jconsole stays open by default
exit''

```

Sample input and output:

# Answer
> 1 votes
# Python, 161\*0.7=112.7 bytes

With the Gaussian Blur bonus.

As you did not explicitly forbid built-in methods, here is OpenCV:

```
from cv2 import*
from numpy import*
g=GaussianBlur(cvtColor(imread(raw_input()),6),(3,3),sigmaX=1)
x,y=Sobel(g,5,1,0),Sobel(g,5,0,1)
imwrite('s.png',sqrt(x*x+y*y))

```

### Without bonus, 136 bytes

```
from cv2 import*
from numpy import*
g=cvtColor(imread(raw_input()),6)
x,y=Sobel(g,5,1,0),Sobel(g,5,0,1)
imwrite('s.png',sqrt(x*x+y*y))

```
* Edit1: Replaced the named constans by their values.
* Edit2: Uploaded samples

# Answer
> 0 votes
# MATLAB, 212\*0.4=84.8 bytes

Using the filter toolbox and the HSV colorspace

```
function f(x);f=@(i,x)imfilter(i,x);s=@(x)fspecial(x);S=s('sobel');A=f(double(rgb2gray(imread(x)))/255,s('gaussian'));X=f(A,S);Y=f(A,S');imwrite(hsv2rgb(cat(3,atan2(Y,X)/pi/2+0.5,0*A+1,sqrt(X.^2+Y.^2))),'t.png')

```

or ungolfed

```
function f(x)
f=@(i,x)imfilter(i,x);
s=@(x)fspecial(x);
S=s('sobel');
A=f(double(rgb2gray(imread(x)))/255,s('gaussian'));
X=f(A,S);
Y=f(A,S');
imwrite(hsv2rgb(cat(3,atan2(Y,X)/pi/2+0.5,0*A+1,sqrt(X.^2+Y.^2))),'t.png')

```

# Answer
> 0 votes
# Love2D Lua, 466 Bytes

```
A=arg[2]i=love.image.newImageData q=math t=i(A)g=i(t:getWidth()-2,t:getHeight()-2)m={{-1,-2,-1},{0,0,0},{1,2,1}}M={{-1,0,1},{-2,0,2},{-1,0,1}}t:mapPixel(function(_,_,r,g,b)a=(r+g+b)/3 return a,a,a end)g:mapPixel(function(x,y)v=0 for Y=0,2 do for X=0,2 do v=v+(t:getPixel(x+X,y+Y)*m[Y+1][X+1])end end V=0 for Y=0,2 do for X=0,2 do V=V+(t:getPixel(x+X,y+Y)*M[Y+1][X+1])end end v=q.max(q.min(q.sqrt(V^2+v^2),255),0)return v,v,v end)g:encode('png',"o")love.event.quit()

```

Takes command line input, outputs to a file called "o" under your Love2D appsdata folder. Love2D Wont let you save files anywhere else.

Just about as golfed as I could get it, probably could be golfed further.

## Explained

```
-- Assign the Input to A
A=arg[2]

-- Assign some macros to save FUTURE BYTES™
i=love.image.newImageData
q=math

-- t is the original image, g is the new output image. g is two pixels smaller, which is easier and better looking than a border.
t = i(A)
g = i(t:getWidth()-2,t:getHeight()-2)

-- m and M are our two sobel kernals. Fairly self explanitary.
m = {{-1,-2,-1}
    ,{0,0,0}
    ,{1,2,1}}

M = {{-1,0,1}
    ,{-2,0,2}
    ,{-1,0,1}}

-- Convert t to grayscale, to save doing this math later.
t:mapPixel(function(_,_,r,g,b)a=(r+g+b)/3 return a,a,a end)

-- Execute our kernals
g:mapPixel(function(x,y)
    -- v refers to the VERTICAL output of the Kernel m.
    v=0
    for Y=0,2 do
        for X=0,2 do
            v=v+(t:getPixel(x+X,y+Y)*m[Y+1][X+1])
        end
    end

    -- V is the HORIZONTAL of M
    V=0
    for Y=0,2 do
        for X=0,2 do
            V=V+(t:getPixel(x+X,y+Y)*M[Y+1][X+1])
        end
    end

    -- Clamp the values and sum them.
    v = q.max(q.min(q.sqrt(V^2 + v^2),255),0)
    -- Return the grayscale.
    return v,v,v
end)

-- Save, renaming the file. The golfed version just outputs as 'o'
g:encode('png',"S_".. A:gsub("(.*)%....","%1.png"))

-- Quit. Not needed, but I'm a sucker for self contained LOVE2D
love.event.quit()

```

## Test

## And...

Although it doesn't actually improve my score (Makes it worse infact), here is the version with the colour wheel implemented.

900 - 270 = 630 Bytes

```
A=arg[2]i=love.image.newImageData q=math t=i(A)g=i(t:getWidth()-2,t:getHeight()-2)m={{-1,-2,-1},{0,0,0},{1,2,1}}M={{-1,0,1},{-2,0,2},{-1,0,1}}function T(h,s,v)if s <=0 then return v,v,v end h,s,v=h*6,s,v/255 local c=v*s local x=(1-q.abs((h%2)-1))*c local m,r,g,b=(v-c),0,0,0 if h < 1 then r,g,b=c,x,0 elseif h < 2 then r,g,b=x,c,0 elseif h < 3 then r,g,b=0,c,x elseif h < 4 then r,g,b=0,x,c elseif h < 5 then r,g,b=x,0,c else r,g,b=c,0,x end return(r+m)*255,(g+m)*255,(b+m)*255 end t:mapPixel(function(_,_,r,g,b)a=(r+g+b)/3 return a,a,a end)g:mapPixel(function(x,y)v=0 for Y=0,2 do for X=0,2 do v=v+(t:getPixel(x+X,y+Y)*m[Y+1][X+1])end end V=0 for Y=0,2 do for X=0,2 do V=V+(t:getPixel(x+X,y+Y)*M[Y+1][X+1])end end h=v H=V v=q.max(q.min(q.sqrt(V^2+v^2),255),0)h=q.atan2(H,h)/q.pi*2 return T(h,1,v,255)end)g:encode('png',"S_".. A:gsub("(.*)%....","%1.png"))G=love.graphics.newImage(g)love.event.quit()

```

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


title: Combinatorial products of unique primes

text:
# Question
Title: Combinatorial products of unique primes
## Statement of problem

Given a set of unique, consecutive primes (not necessarily including 2), generate the products of all combinations of first powers of these primes — e.g., no repeats — and also 1. For example, given the set { 2, 3, 5, 7 }, you produce { 1, 2, 3, 5, 6, 7, 10, 14, 15, 21, 30, 35, 42, 70, 105, 210 } because:

```
  1  =  1
  2  =  2
  3  =  3
  5  =  5
  6  =  2 x 3
  7  =  7
 10  =  2 x 5
 14  =  2 x 7
 15  =  3 x 5
 21  =  3 x 7
 30  =  2 x 3 x 5
 35  =  5 x 7
 42  =  2 x 3 x 7
 70  =  2 x 5 x 7
105  =  3 x 5 x 7
210  =  2 x 3 x 5 x 7

```

Note that if the cardinality of your input set is k, this will give you 2^k members in your output set.

## Rules/Conditions

1. You can use any language. Aim for the smallest character count of source code.
2. Your solution must be either a complete program or a complete function. The function can be anonymous (if your language supports anonymous functions).
3. Your solution should be able to support products up to at least 2^31. Don't worry about detecting or handling integer overflow if you are passed numbers whose product is too great to represent. However, please state the limits of your calculations.
4. You may accept either a list or a set and produce either a list or a set. You may assume the input is sorted but you are not required to produce sorted output.

## Background

When or why is this useful? One place it is very useful is in generating a table of *multipliers* to race in parallel in an integer factoring algorithm known as Square Forms Factorization. There, each odd multiplier you try decreases the probability of the algorithm failing (to find a factor) by approximately 50% on hard semiprimes. So with the set of generating primes { 3, 5, 7, 11 }, which produces a set of 16 trial multipliers to race in parallel, the algorithm fails approximately 2^–16 of the time on hard semiprimes. Adding 13 to the primes list produces a set of 32 trial multipliers, reducing the chance of failure to approximately 2^–32, giving a drastic improvement in outcome at no additional computational expense (because even with twice as many multipliers racing in parallel, on average it still finds the answer in the same total number of steps).

# Answer
> 18 votes
# Pure Bash, 32 bytes

```
eval echo \$[{1,${1// /\}*{1,}}]

```

Reads input list (single space separated) passed as a command-line arg.

Three different shell expansions are used:

1. `${1// /\}*{1,}` is a parameter expansion that replaces spaces in `2 3 5 7` with `}*{1,` to give `2}*{1,3}*{1,5}*{1,7`. `\$[{1,` and `}]` are added to the start and end respectively to give `\$[{1,2}*{1,3}*{1,5}*{1,7}]`. The `\$[` is backslash-escaped to prevent attempts to do arithmetic expansion at this stage.
2. `\$[{1,2}*{1,3}*{1,5}*{1,7}]` is a brace expansion. Because brace expansion typically happens before parameter expansion, we use have to use`eval` to force the parameter expansion to happen first. The result of the brace expansion is `$[1*1*1*1] $[1*1*1*7] $[1*1*5*1] ... $[2*3*5*7]`.
3. `$[1*1*1*1] $[1*1*1*7] $[1*1*5*1] ... $[2*3*5*7]` is a list of arithmetic expansions, which are then evaluated to give the list of numbers we require.

### Output:

```
$ ./comboprime.sh "2 3 5 7"
1 7 5 35 3 21 15 105 2 14 10 70 6 42 30 210
$

```

# Answer
> 12 votes
# CJam, 13 bytes

```
1aq~{1$f*+}/p

```

Reads an array (e.g., `[2 3 5 7]`) from STDIN. Try it online.

An anonymous function would have the same byte count:

```
{1a\{1$f*+}/}

```

### Example run

```
$ cjam <(echo '1aq~{1$f*+}/p') <<< '[]'
[1]
$ cjam <(echo '1aq~{1$f*+}/p') <<< '[2 3 5 7]'
[1 2 3 6 5 10 15 30 7 14 21 42 35 70 105 210]

```

### How it works

```
1a               " Push R := [1].              ";
  q~             " Read an array A from STDIN. ";
    {     }/     " For each a ∊ A:             ";
     1$f*+       "     R += { ra : r ∊ R }     ";
            p    " Print.                      ";

```

# Answer
> 9 votes
# Haskell, 22

the solution is an anonymous function:

```
map product.mapM(:[1])

```

example usage:

```
*Main> map product.mapM(:[1]) $ [2,3,5]
[30,6,10,2,15,3,5,1]

```

**explanation:**
`(:[1])` is a function which given a number `x` returns the list `[x,1]`.
`mapM(:[1])` is a function which given a list of numbers maps the function `(:[1])` over them, and returns every possible way to choose an element from every list. for example, `mapM(:[1]) $ [3,4]` first maps the function to get `[[3,1] , [4,1]]`. then the possible choices are `[3,4]` (choosing the first number of both) `[3,1]` `[1,4]` and `[1,1]` so it returns `[[3,4],[3,1],[1,4],[1,1]]`.
then `map product` maps over all choices and returns their products, which are the wanted output.
this function is polymorphic in its type meaning that it can operate on all types of numbers. you could input it a list of `Int` and the result would be a list of `Int` but could also be applied on a list of type `Integer` and return a list of `Integer`. this means that overflow behavior is not specified by this function but by the input's type (yay Haskell's expressive type system :) )

# Answer
> 8 votes
## Mathematica, ~~18~~ 17 bytes

```
1##&@@@Subsets@#&

```

That's an anonymous function. Call it like

```
1##&@@@Subsets@#&[{2,3,5,7}]

```

# Answer
> 4 votes
# Update: C (function f), 92

Even as a function, this is still the longest entry here. It's the first time I've passed an array of unknown length as a function argument in C, and apparently there is no way for a C function to know the length of an array passed to it, as the argument is passed as a pointer (regardless of the syntax used). Hence a second argument is required to indicate the length.

I kept the output to stdout, because setting up an integer array and returning it would almost certainly be longer.

Thanks to Dennis for the tips.

See the function `f` (92 characters excluding unnecessary whitespace) in the test programs below.

**Output via printf**

```
j;

f(int c,int*x){
  int p=1,i;
  for(i=c<<c;i--;p=i%c?p:!!printf("%d ",p))p*=(i/c>>i%c)&1?1:x[i%c];
}

main(int d,char**v){
  d--;
  int y[d];
  for(j=d;j--;)y[j]=atoi(v[j+1]);
  f(d,y);
}

```

**Output via array pointer**

```
j,q[512];

f(int c,int*x,int*p){
    for(int i=-1;++i-(c<<c);p[i/c]*=(i/c>>i%c)&1?1:x[i%c])i%c||(p[i/c]=1);
}

main(int d,char**v){
  d--;
  int y[d];
  for(j=d;j--;)y[j]=atoi(v[j+1]);
  f(d,y,q);
  for(j=1<<d;j--;)printf("%d ",q[j]);
}

```

# C (program),108

excluding unnecessary whitespace.

```
p=1,i;
main(int c,char**v){
  c-=1;
  for(i=c<<c;i--;i%c||(printf("%d ",p),p=1))(i/c>>i%c)&1||(p*=atoi(v[i%c+1]));
}

```

Input from commandline, output to stdout. C isn't going to win here, but maybe I will try converting to a function tomorrow.

Basically we iterate through all `1<<c` combinations of primes, with each bit of `i/c` being associated with the presence or absence of a particular prime in the product. The "inner loop" `i%c` runs through the primes, multiplying them according to the value of `i/c.` When `i%c` reaches 0, the product is output, then set to 1 for the next "outer" iteration.

curiously, `printf("%d ",p,p=1)` does not work (it always prints a 1.) This is not the first time I have seen odd behaviour when a value is used in a `printf` and assigned later in the same bracket. It is possible in this case that the second comma is not being treated as an argument separator, but rather as an operator.

**Usage**

```
$ ./a 2 3 5 7
1 2 3 6 5 10 15 30 7 14 21 42 35 70 105 210

```

# Answer
> 3 votes
## Python: 55 chars

```
f=lambda l:l and[x*l[0]for x in f(l[1:])]+f(l[1:])or[1]

```

Recursively generates the products by choosing to include or exclude each number in turn.

# Answer
> 3 votes
# Haskell, 27 bytes

This is a Haskell implementation of @sudo's CJam answer as an anonymous function. It won't beat the awesome Haskell solution of @proud haskeller, but I'll drop it here anyway.

```
foldr((=<<)(++).map.(*))[1]

```

**Explanation:** `foldr` takes in a binary function, a value, and a list. Then it replaces each cons cell in the list by an application of the function, and the end of the list by the value, like this: `foldr f v [a,b,c] == f a (f b (f c v))`. Our value is a one-element list containing `1`, and the binary function is `f = (=<<)(++).map.(*)`. Now, `f` takes a number `n`, makes a function `(n*)` that multiplies by `n`, makes from it a function `g = map(n*)` that applies that function to all elements of a list, and feeds *that* function to `(=<<)(++)`. Here, `(++)` is the concatenation function, and `(=<<)` is *monadic bind*, which in this case takes in `(++)` and `g`, and gives a function that takes in a list, applies `g` to a copy of it, and concatenates the two.

In short: start with `[1]`, and for each number `n` in the input list, take a copy of the current list, multiply everything by `n`, and append it to the current list.

# Answer
> 3 votes
# PARI/GP, 26 bytes

```
v->divisors(factorback(v))

```

Longer versions include

```
v->divisors(prod(i=1,#v,v[i]))

```

(30 bytes) and

```
v->divisors(fold((x,y)->x*y,v))

```

(31 bytes).

Note that if the input was a *factorization matrix* rather than a set, 18 bytes could be saved using `divisors` alone. But converting a set to a factorization matrix seems to take more than 18 bytes. (I can do it in 39 bytes directly as `v->concat(Mat(v~),Mat(vectorv(#v,i,1)))` or 24 bytes by multiplying and re-factoring`v->factor(factorback(v))`, can anyone do better?)

# Answer
> 2 votes
# Sage – ~~36~~ 34

Essentially, the same as Martin Büttner’s solution, if I understand it correctly. As I mentioned it in a comment, I might as well post it as an answer.

```
lambda A:map(prod,Combinations(A))

```

This is an anonymous function, which can for example be called as follows:

```
(lambda A:map(prod,Combinations(A)))([2,3,5,7])

```

# Answer
> 2 votes
# J (20)

This turned out longer than I hoped or expected.Still: shorter than haskel!

```
*/@:^"1#:@i.@(2&^)@#

```

## Usage:

```
    f=:*/@:^"1#:@i.@(2&^)@#
    f 2 3 5 7
1 7 5 35 3 21 15 105 2 14 10 70 6 42 30 210

```

This works for any set of numbers, not just primes. Also, the primes can be of unlimited size, as long as the array has the postfix `x`: `2 3 5 7x`

# Answer
> 2 votes
# 05AB1E, 2 bytes

```
æP

```

Try it online!

**Explanation**

```
æ   # powerset
 P  # product

```

# Answer
> 1 votes
# R, 56 bytes

```
r=1;for(i in 1:length(s))r=c(r,apply(combn(s,i),2,prod))

```

I'm considering here that s is the set (and a list). I'm sure it can be made even shorter. I'll see.

# Answer
> 1 votes
# PHP, 97 Bytes

```
<?for(;$i++<array_product($a=$_GET[a]);){$t=$i;foreach($a as$d)$t%$d?:$t/=$d;if($t<2)echo"$i\n";}

```

---
Tags: code-golf, math, number-theory, combinatorics, primes
---


title: Natural Pi #1 - Sand

text:
# Question
Title: Natural Pi #1 - Sand
## Goal

Generate (`N`) random line segments of uniform length (`l`), check if they cross the equidistant (`t`) parallel lines.

## Simulation

**What are we simulating?** Buffon's needle. Smooth out the sand in your sandbox, draw a set of equally spaced parallel lines (call the distance in between `t`). Take a straight stick of length `l` and drop it `N` times into the sandbox. Let the number of times it crossed a line be `c`. Then `Pi = (2 * l * n) / (t * c)`!

**How are we simulating this?**

* Take input `N,t,l`
* With `N, t, l` all being positive integers
* Do the following `N` times:
    + Generate a uniformly random integer coordinate `x,y`
    + With `1 <= x, y <= 10^6`
    + `x,y` is the center of a line segment of length `l`
    + Generate a uniformly random integer `a`
    + With `1 <= a <= 180`
    + Let `P` be the point where the line segment would cross the x-axis
    + Then `a` is the angle `(x,y), P, (inf,0)`
* Count the number, `c`, of line segments that cross the line `x = i*t` for any integer `i`
* Return `(2 * l * N) / (t * c)`

## Specification

* **Input**
    + Flexible, take input in any of the standard ways (eg function parameter,STDIN) and in any standard format (eg String, Binary)
* **Output**
    + Flexible, give output in any of the standard ways (eg return, print)
    + White space, trailing and leading white space is acceptable
    + Accuracy, please provide at least 4 decimal places of accuracy (ie `3.1416`)
* **Scoring**
    + Shortest code wins!

## Test Cases

Your output may not line up with these, because of random chance. But on average, you should get about this much accuracy for the given value of `N, t, l`.

```
Input (N,t,l)    ->  Output
-----------        ------
10,10,5          -> ?.????
10,100,50        -> ?.????
1000,1000,600    -> 3.????
10000,1000,700   -> 3.1???
100000,1000,700  -> 3.14??

```

### TL;DR

These challenges are simulations of algorithms that only require nature and your brain (and maybe some re-usable resources) to approximate Pi. If you really need Pi during the zombie apocalypse, these methods don't waste ammo! There are nine challenges total.

# Answer
> 9 votes
# R, ~~113~~ ~~100~~ ~~75~~ ~~70~~ ~~68~~ ~~67~~ ~~65~~ ~~59~~ ~~63~~ 57 bytes

As a statistical, functional programming language, it's not surprising that R is fairly well-suited to this kind of task. The fact that most functions can take vectorized input is really helpful for this problem, as rather than looping over `N` iterations, we just pass around vectors of size `N`. Thanks to @Billywob for some suggestions that lead to cutting off 4 bytes. Many thanks to @Primo for patiently explaining to me how my code wasn't working for cases where `t > l`, which is now fixed.

```
pryr::f(2*l*N/t/sum(floor(runif(N)+sinpi(runif(N))*l/t)))

```

Try it online!

Sample output:

```
N=1000, t=1000, l=500
3.037975

N=10000, t=1000, l=700
3.11943

N=100000, t=1000, l=700
3.140351

```

## Explanation

The problem boils down to determining whether the two `x` values of the needle are on either side of a parallel line. This has some important consequences:

1. `y`-values are irrelevant
2. The absolute location on the `x`-axis is irrelevant, only the position relative to the closest parallel lines.

Essentially this is a task in a 1-dimensional space, where we generate a line with length in \[0, `l`\] (the angle `a` determines this length), and then we check to see how many times this length exceeds `t`. The rough algorithm is then:

1. Sample `x1` values from \[0, 1000000\]. Since parallel lines occur at every `t`th point along the `x`-axis, the relative `x`-position is `x` modulo `t`.
2. Sample an angle `a`.
3. Calculate the `x2` position based on `a`.
4. Check how many times `x1+x2` fits into `t`, i.e. take the floor of `(x1+x2)/t`.

Sampling `N` numbers in \[0, 1e6\] modulo `t` is equivalent to simply sampling `N` numbers in \[0, `t`\]. Since `(x1+x2)/t` is equivalent to `x1/t + x2/t`, the first step becomes sampling from \[0, `t`\]/`t`, i.e. \[0, 1\]. Lucky for us, that is the default range for R's `runif` function, which returns `N` real numbers from 0 to 1 from a uniform distribution.

```
                          runif(N)

```

We repeat this step to generate `a`, the angle of the needle.

```
                                         runif(N)

```

These numbers are is interpreted as a half-turn (i.e. `.5` is 90 degrees). (The OP asks for degrees from 1 to 180, but in comments it's clarified that any method is allowed if it is as or more precise.) For an angle `θ`, `sin(θ)` gives us the x-axis distance between the ends of the needle. (Normally you'd use the cosine for something like this; but in our case, we are considering the angle `θ` as being relative to the y-axis, not the x-axis (that is, a value of 0 degrees goes *up*, not *right*), and therefore we use the sine, which basically phase-shifts the numbers.) Multiplied by `l` this gives us the `x` location of the end of the needle.

```
                                   sinpi(runif(N))*l

```

Now we divide by `t` and add the `x1` value. This yields `(x1+x2)/t`, which is how far the needle protrudes from `x1`, in terms of number of parallel lines. To get the integer of how many lines were crossed, we take the `floor`.

```
                    floor(runif(N)+sinpi(runif(N))*l/t)

```

We calculate the sum, giving us the count `c` of how many lines are crossed by needles.

```
                sum(floor(runif(N)+sinpi(runif(N))*l/t))

```

The rest of the code is just implementing the formula for approximating pi, that is, `(2*l*N)/(t*c)`. We save some bytes on parentheses by taking advantage of the fact that `(2*l*N)/(t*c) == 2*l*N/t/c`:

```
        2*l*N/t/sum(floor(runif(N)+sinpi(runif(N))*l/t))

```

And the whole thing is wrapped into an anonymous function:

```
pryr::f(2*l*N/t/sum(floor(runif(N)+sinpi(runif(N))*l/t)))

```

# Answer
> 6 votes
# Perl, 97 bytes

```
#!perl -p
/ \d+/;$_*=2*$'/$&/map{($x=(1+~~rand 1e6)/$&)-$a..$x+($a=$'/$&/2*sin~~rand(180)*71/4068)-1}1..$_

```

Counting the shebang as one, input is taken from stdin, space separated. If non-integer random values were allowed, this could be somewhat shorter.

I have taken one liberty, approximating *π/180* as *71/4068*, which is accurate within *1.48·10<sup>-9</sup>*.

**Sample Usage**

```
$ echo 1000000 1000 70000 | perl pi-sand.pl
3.14115345174061

```

---

**More-or-less mathematically equivalent substitutions**

Assuming the x-coordinate represents the left-most point of the needle, rather than its middle, as specified in the problem description:

**89 bytes**

```
#!perl -p
/ \d+/;$_*=2*$'/$&/map{($x=(1+~~rand 1e6)/$&)..$x+($'/$&*sin~~rand(180)*71/4068)-1}1..$_

```

The problem specifies that `x` is to be sampled as a random integer. If we project the line spacing to a gap of one, this will leave us with values of the form `n/t` with `0 <= n < t`, not necessarily uniform, if `t` does not evenly divide `1e6`. Assuming that a uniform distribution is nonetheless acceptable:

**76 bytes**

```
#!perl -p
/ \d+/;$_*=2*$'/$&/map{($x=rand)..$x+($'/$&*sin~~rand(180)*71/4068)-1}1..$_

```

Note that since `rand` will always be less than one (and therefore truncated to zero), it is not necessary at the start of the range:

**70 bytes**

```
#!perl -p
/ \d+/;$_*=2*$'/$&/map{1..(rand)+($'/$&*sin~~rand(180)*71/4068)}1..$_

```

Assuming that the angle of the needle need not be an integer degree, but only uniformly random:

**59 bytes**

```
#!perl -p
/ \d+/;$_*=2*$'/$&/map{1..(rand)+abs$'/$&*sin rand$`}1..$_

```

Assuming that the angle may be any uniform distribution:

**52 bytes**

```
#!perl -p
/ \d+/;$_*=2*$'/$&/map{1..(rand)+abs$'/$&*sin}1..$_

```

The above is a mathematically correct simulation of Buffon's Needle. However, at this point I think most people would agree that this isn't actually what the question asked for.

---

**Really pushin' it**

We could just throw away half of the test cases, whenever the second endpoint is to the left of the first (rather than swapping them):

**47 bytes**

```
#!perl -p
/ \d+/;$_*=$'/$&/map{1..(rand)+$'/$&*sin}1..$_

```

Note that the values of `t` and `l` are inconsequential to the results of the experiment. We could just ignore them (implicitly assuming them to be equal):

**28 bytes**

```
#!perl -p
$_/=map{1..(rand)+sin}1..$_

```

Obviously non-competing, but you have to admit, it does have a certain elegance to it.

# Answer
> 4 votes
# Python 2, 141 bytes

shameless port of rtumbull, already skipping `y` because totally not needed.

```
from math import*
from random import*
lambda N,t,l:(2.*l*N)/(t*sum(randint(1,1e6)%t+abs(cos(randint(1,180)*pi/180))*l>t for _ in range(N)))

```

Problem is only, that pi is already known in the program.

Here it is (golfable) with unknown pi and no trigonometric functions

```
def g(N,t,l):
 c=0
 for _ in range(N):
    x,y=gauss(0,1),gauss(0,1);c+=randint(1,1e6)%t+abs(x/sqrt(x*x+y*y))*l>t
 return(2.*l*N)/(t*c)

```

`x,y` in `g` is only for the direction.

---
Tags: code-golf, math, random, pi, approximation
---