title: Klein Topololyglots

text:
# Question
Title: Klein Topololyglots
Klein is a 2D language I have designed that can be embedded on 12 different topological surfaces. A Klein program can be run on different surfaces by changing the command line arguments.

The topology determines where the instruction pointer goes when it goes off the edge of the program. When moving off of the edge the ip will jump to an edge with the matching color, and will maintain its position relative to the arrow, i.e. the pointer will conserve its distance from the arrow head.

For example topology `000`, the topology used by most 2D languages, causes the instruction pointer to wrap around to the other side when if moves off an edge.

# Task

The task is pretty simple, write a Klein program that when run will output the topology it is run in. The individual numbers may be separated by spaces. (e.g. `000` and `0 0 0` are both permissible output). You may choose to either use or ignore the `-A` command line flag it will not cost you bytes if you use it.

This is so the shortest answer will be the winner.

Here is a online test driver that can be used to test all of the topologies at once. To run in integer mode remove the `-A`.

# Answer
# ~~52~~ 48 bytes

```
./@$0<$
21\./01
..>..!\
@
.<..<\
20//\11
@01$00@

```

Try it online!

Test Driver

## Explanation

In Klein the IP starts in the top left corner going right. The first step I wanted my program to do was to send the IP off the top of the program to determine the first and third bit. The IP would reenter the program as follows depending on the topology:

```
             ^
            I|P
            ./.....
201, 211 -->.......<-- 100, 110
            .......
            .......
            .......
200, 210 -->.......<-- 101, 111
            .......
             ^   ^
             |   |
            000 001
            010 011

```

I decided that the my program would record the third bit of the topology before the second bit but swap them (using `$`) before the end. To that end I added code to push the first and third bits of each topology at the IP's points of entry described above.

```
./.....
21...01
.......
.......
.......
20...11
.0...0.

```

Next I focused on the topologies with `1` or `2` as their first bit. I decided to recombine them and send them off on the side not connected to the north side so I could determine their second bit.

```
                      ./.....
                      21\./01
                      ..>....--> 200, 201, 210, 211
                      .......
100, 101, 110, 111 <--....<..
                      20/.\11
                      .0...0.
                        ^ ^
                        | |
                        / \
                      110 100
                      111 101
                      210 200
                      211 201

```

Conveniently this regrouped the topologies by their second bit so I could push that to the stack.

```
./.....
21\./01
..>....
.......
....<..
20/.\11
.01.00.

```

After that I just needed to swap the second and third bit and have the program terminate.

```
./.$...
21\./01
..>....
@......
....<..
20//\11
.01$00.

```

Now that the topologies with `1` or `2` as their first bit worked, I could focus on making the topologies with `0` give the correct output. The first step was recombining them so that they could be separated into two groups based on their second bit.

```
                      ./.$...
                      21\./01
                      ..>....<-- 010, 011
                      @......
000, 001, 010, 011 <--.<..<<.<-- 000, 001
                      20//\11
                      .01$00.

```

I first focused on those topologies with `1` as their second bit. These presented a challenge because for them the IP was on a line already used by the topologies with `2` as their first bit. Since it would be tricky to fit more than one instruction on that line (a single instruction can be jumped using the `!` instruction) and I was running low on space as a whole, I decided to redirect the IP off that line and reuse an existing `1` instruction to push the second bit.

```
./.$...
21\./01
..>..!\
@......
.<..<<.
20//\11
.01$00.

```

Now all that was left to do for the topologies with `1` as their second bit was to fix the order of the second and third bit and terminate.

```
       ^
       |
 ./.$..$
 21\./01
 ..>..!\
 @......
 .<..<<.
 20//\11
 @01$00@
 ^     ^
 |     |
011   010

```

Lastly remained the topologies with `0` as their second bit. There was not much space left in the program with the largest unused space being on the top line so it was there that I redirected the IP for the topologies with `0` as their second bit.

```
./.$.<$
21\./01
..>..!\
@......
.<..<\.
20//\11
@01$00@

```

I still needed to push `0` for the second bit and fix the order of the second and third bit as well as terminate the program. Fortunately, I was able to reuse an existing `$` instruction so the `0` and `@` instructions could fit in the remaining spaces.

```
./@$0<$
21\./01
..>..!\
@......
.<..<\.
20//\11
@01$00@

```

Finally the nops can be stripped from the ends of lines to get the final program.
> 34 votes

# Answer
# ~~116~~ ~~88~~ ~~86~~ ~~77~~ ~~69~~ ~~61~~ ~~60~~ ~~59~~ ~~58~~ ~~54~~ ~~53~~ 50 bytes

```
\2..@2
/1\<$00
/>!..>!
0//
@0$10@1
011\.<0
\.<@>1@

```

Try it online!
> 15 votes

# Answer
# ~~44 41 40 38~~ 37 bytes

```
\\1.>2
/0./
@./$(\
$>0!>
11$/10
$.@.1

```

Try it online!

Test driver.

Uses a 6 by 6 square. The shortest I could get with an 8 by 8 square is 38 bytes if anyone wants to try improving it.

### Explanation:

One the first pass-through the code encodes the first two numbers for the prefixes `0` and `1`. For `2`, it encodes the third number then the first.

```
     201  200
     211  210
       |  |
       v  v
   -> \\1.>2
 IP<- /../..  <- 000, 001
      ...$..
      .>0...
      .1..10  <- 010, 011
      ....1.
       ^  ^
       |  |
     100  110
     101  111

```

Then we pass the IPs through the third edge to decide the final number. We combine the IPs with the same prefix.

```
     201  200
     211  210
       |  |
       v  v
   -> \\1.>2  -> 0,2 or 1,2
 IP<- /../..  <- 000, 001
      ...$..
      .>0!>.  -> 1
      .1./10  <- 010, 011
      ....1.
       ^ |^
       | v|
       | 0|
     100  110
     101  111

```

For the `0` and `1` prefixes, they both come out the top edge to decide the third number.

```
     201  200
     211  210
       |  |
       |10|
       vvvv
   -> \\1.>2  -> 2
 IP<- /0./..  <- 000, 001
      @./$..
      .>0!>.  -> 1
      .1./10  <- 010, 011
      ....1.
       ^ |^
       | v|
       | 0|
     100  110
     101  111

```

For the `2` prefix, the IPs come out the corners from the bottom edge.

```
     201  200
     211  210
       |  |
       |10|
       vvvv
   -> \\1.>2  -> 2
 IP<- /0./..  <- 000, 001
      @./$(\
      $>0!>.  -> 1
      11$/10  <- 010, 011
      $.@.1.
      ^^ |^^
      || v||
      1| 0|0
     100  110
     101  111

```

Both edges swap the first and third number, push the second number and swaps it with the third to get the correct order.
> 15 votes

---
Tags: code-golf, polyglot, topology, klein
---


# Question
Title: A greeting bot for a colleague from work
I have a colleague at work that works from home every Tuesday and Thursday. At around 8:00 AM he sends us a message with the following text:

> Hello today I'm working from home

In order to relieve him from the burden of doing this every day he stays at home, we would like to automate this task for him.

### The challenge

Write in as few bytes as possible a piece of code that:

* Receives the current time: your code may receive values for the current year, month (1-12), day of month (1-31), hour (0-23) and minute (0-59) and the day of the week (you can choose whether this number starts from 0 or 1, and if 0/1 means Sunday, Monday or any other day); alternatively you may receive a structure such as `Date`, `DateTime`, `Calendar` or any other time-related structure, if your language allows it. You can also receive a string with the date in `yyyyMMddHHmm` if you want, or two separate strings for date and time, and then an integer with the day of week. Feel free.
* Returns two consistent *truthy* and *falsey* values, indicating if the message must be sent to the work chat or not.

### Rules

* This piece of code is assumed to be invoked periodically. The exact periodicity is irrelevant, nonetheless.
* The truthy value must be returned if the day of week is Tuesday or Thursday and the time is 8:00 AM with an error margin of 10 minutes (from 7:50 to 8:10 inclusive).
* The truthy value must be sent only if it is the first time the code is invoked between those hours for the specified day. We don't want the bot to send the same message several times in a row. The way you manage this restriction will be entirely up to you.
* Your code may be an independent program executed repeatedly or it may be part of a bigger code that is always running. Your choice.
* You may assume that there will be no reboots between executions of the code.
* You may assume that the date will always be correct.
* Explanations about your code and specifically about the method used to achieve persistence are encouraged.

### Examples

```
(Week starts on Monday: 1, the following invokations will be made in succession)
2018,08,27,08,00,1 = falsey (not Tuesday or Thursday)
2018,08,28,07,45,2 = falsey (out of hours)
2018,08,28,07,55,2 = truthy (first time invoked this day at the proper hours)
2018,08,28,08,05,2 = falsey (second time invoked this day at the proper hours)
2018,08,28,08,15,2 = falsey (out of hours)
2018,08,29,08,00,3 = falsey (not Tuesday or Thursday)
2018,08,29,18,00,3 = falsey (not Tuesday or Thursday)
2018,08,30,07,49,4 = falsey (out of hours)
2018,08,30,07,50,4 = truthy (first time invoked this day at the proper hours)
2018,08,30,07,50,4 = falsey (second time invoked this day at the proper hours)
2018,08,30,08,10,4 = falsey (third time invoked this day at the proper hours)
2018,08,30,08,11,4 = falsey (out of hours)
2018,09,04,08,10,2 = truthy (first time invoked this day at the proper hours)

```

This is , so may the shortest code for each language win!

# Answer
> 15 votes
# JavaScript (ES6), 43 bytes

```
f=(D,t,d)=>5>>d&t>749&t<811&&!f[D]*(f[D]=1)

```

Try it online!

### Input

* the date as a string in `yyyymmdd` format
* the time as a string in `hhmm` format
* the day of week as a 0-indexed integer, with `0` = Tuesday, `1` = Wednesday, ..., `6` = Monday

### Output

Returns `0` or `1`.

### Commented

```
f = (            // named function, as the underlying object will be used as storage
  D,             // D = date (string)
  t,             // t = time (string)
  d              // d = day of week (integer)
) =>             //
  5              // 5 is 0000101 in binary, where 1's are set for Tuesday and Thursday
  >> d &         // test the relevant bit for the requested day of week
  t > 749 &      // test whether we are in the correct time slot
  t < 811        //
  && !f[D] *     // make sure that this date was not already invoked at a correct time
  (f[D] = 1)     // and store it in the underlying object of f()

```

# Answer
> 5 votes
# APL (Dyalog Unicode), ~~61~~ ~~53~~ ~~50~~ ~~48~~ ~~37~~ 36 bytesSBCS

Anonymous infix lambda. Called with `YYYYMMDD f hhmm` and then prompts for weekday number; 2 and 4 are Tuesday and Thursday. Redefines the global `D` to remember dates.

```
D←⍬
{≢D,←⍺/⍨(⎕∊2 4)∧(⍺∊D)<30≥|780-⍵}

```

Try it online!

`D←⍬` initialise `D` to be an empty set

`{``}` anonymous lambda;  is `YYYYMMDD`,  is `hhmm`
`780-⍵` difference between 780 (mean of 0750 and 0810) and the time
`|` absolute value of that
`30≥` is 30 greater or equal to that?
`(``)<` and it is not true that:
`⍺∊D` the date is a member of `D`
`(``)∧` and it is true that:
`⎕∊2 4` the prompted for weekday is a member of the set {2,4}
`⍺/⍨` use that to compress the date (i.e. gives {} if false, {date} if true)
`D,←` append that to `D`
and return its tally (i.e. 0 or 1, which are APL's false and true)

# Answer
> 5 votes
# Python 3, 69 bytes

```
f=lambda w,r,*t,l={0}:r not in l!=w in(2,4)<(7,49)<t<(8,11)!=l.add(r)

```

Try it online!

Takes input as `f(day of the week, date, hours, minutes)`, where date can be in any consistent format.

# Answer
> 4 votes
# , ~~114~~ 106 bytes

```
function(D,y=D:"%D",u=D$h==7&D$mi>49|D$h==8&D$mi<11&D$w%in%2^4&!y%in%L,`:`=format,`^`=c){L<<-L^y[u];u}
L=F

```

Try it online!

### Persistence:

Date is checked against `L`, the list of dates where the code returned TRUE. When the code returns TRUE, today's date is appended to this list. Otherwise the list is not modified.

Saved 6 bytes thanks to @Giuseppe!

Made the code actually work and saved 2 bytes thanks to @digEmAll!

# Answer
> 4 votes
## Excel formula, 85 bytes

`=IF(AND(MID(WEEKDAY(A1)/0,684;3;1)="3";A1-INT(A1)>=0,32638;A1-INT(A1)<=0,34028);TRUE)`

Weekday with no parameters are from 1 (Sunday) to 7 (Saturday). The days we want are 3 and 5. Dividing all numbers from 1 to 7 for 0,648, only 3 and 5 gives a result where the first decimal is 3 (Got it by dividing with rand())

Input is inserted on Cell A1

# Answer
> 4 votes
# Clean, ~~343~~ ~~326~~ ~~303~~ ~~279~~ 216 bytes

Clean is so ill-suited to this it's like trying to paint a fence with a chainsaw.

```
import StdEnv,System.Environment,System._Unsafe
?(y,x,z)=y*480+x*40+z
$y h m d=(d-3)^2==1&&((h-8)*60+m)^2<121&&appUnsafe(setEnvironmentVariable"l"(fromInt(?y)))(maybe 0toInt(accUnsafe(getEnvironmentVariable"l")))< ?y

```

Try it online!

Golfing then explaination.

# Answer
> 2 votes
# C (gcc),  ~~78~~   ~~50~~  49 bytes

```
D;f(d,w,t){w=d-D&&w<4&&w%2&&t>749&&t<811&&(D=d);}

```

Try it online!

The expected inputs are:

* `d`: the date, as a single number `yyyymmdd`
* `w`: the day of the week, starting with Monday (0)
* `t`: the time, as a single number `hhmm`

# Explanation

```
D;                                      // the date we last said hello.
f(d,                                    // date
    w,                                  // day of the week
      t)                                // time
{
  w=                                    // replaces return
    d-D                                 // if we did not say hello today
       &&w<4&&w%2                       // and we are Tuesday(1) or Thursday(3)
                 &&t>749&&t<811         // and time is between 7:50 and 8:10, inclusive
                               &&(D=d); // then we say hello (evaluated to true) and update D
}

```

# Edits

* Saved 28 bytes thanks to Adám
* Saved 1 more byte, since `abs()` was actually not helping with the new version

# Answer
> 2 votes
## Batch, 109 bytes

```
@if %3 neq 2 if %3 neq 4 exit/b1
@if %2 geq 07:50 if %2 leq 08:10 if .%1 neq .%l% set l=%1&exit/b0
@exit/b1

```

Takes input in the form `date` `time` `dow` e.g. `2018-09-04 08:10 2` and outputs via exit code. Explanation: The environment variable `l` (or any other single letter would work) is used to store the last successful date that passes the test. (The date format itself does not matter as long as it is consistent and does not contain spaces.)

# Answer
> 2 votes
# Perl 6, 33 bytes

```
{811>$^t>749>5+>$^w%2>(%){$^d}++}

```

Try it online!

Heavily inspired by Arnauld's solution. Uses the same input format.

# Answer
> 1 votes
## **C#**, 121 Bytes

```
int[] d=new int[]{2,4};
double s=>Now.TimeOfDay.TotalSeconds;
bool h=>d.Contains((int)Now.DayOfWeek)&&s>=470&&s<=490;

```

Moving all three to the same line reduces size to `117` bytes. `h` is used as a property, just read the value prior to sending the message:

```
if (h) SendMessage();

```

# Answer
> 1 votes
## F#, 119 bytes

```
let f w d h m l = if not(l|>Seq.contains d)&&[3;5]|>Seq.contains w&&(h=7&&m>49||h=8&&m<11)then(l@[d],true)else(l,false)

```

`let f w d h m l =`

declare function called `f` with parameters `w` (day of week) `d` (date) `h` (hour) `m` (minute) `l` (list of dates it's run on)

`if not(l|>Seq.contains d)` if the list of dates doesn't contain the passed date

`&&[3;5]|>Seq.contains w` and the day is Tuesday (3) or Wednesday (5)

`&&(h=7&&m>49||h=8&&m<11)` and the time is between (exclusive) 7:49 and 8:11

`then(l@[d],true)` then return a tuple containing the list of dates with the current date appended, and true

`else(l,false)` else return a tuple containing the list of dates without today and false

---
Tags: code-golf, decision-problem, date, stateful
---


title: Primality testing formula

text:
# Question
Title: Primality testing formula
Your goal is to determine whether a given number `n` is prime in the fewest bytes. But, your code must be a single Python 2 expression on numbers consisting of only

* operators
* the input variable `n`
* integer constants
* parentheses

No loops, no assignments, no built-in functions, only what's listed above. Yes, it's possible.

**Operators**

Here's a list of all operators in Python 2, which include arithmetic, bitwise, and logical operators:

```
+    adddition
-    minus or unary negation
*    multiplication
**   exponentiation, only with non-negative exponent
/    floor division
%    modulo
<<   bit shift left
>>   bit shift right
&    bitwise and
|    bitwise or
^    bitwise xor
~    bitwise not
<    less than
>    greater than
<=   less than or equals
>=   greater than or equals
==   equals
!=   does not equal

```

All intermediate values are integers (or False/True, which implicitly equals 0 and 1). Exponentiation may not be used with negative exponents, as this may produce floats. Note that `/` does floor-division, unlike Python 3, so `//` is not needed.

Even if you're not familiar with Python, the operators should be pretty intuitive. See this table for operator precedence and this section and below for a detailed specification of the grammar. You can run Python 2 on TIO.

**I/O**

**Input:** A positive integer `n` that's at least 2.

**Output:** 1 if `n` is prime, and 0 otherwise. `True` and `False` may also be used. Fewest bytes wins.

Since your code is an expression, it will be a snippet, expecting the input value stored as `n`, and evaluating to the output desired.

Your code must work for `n` arbitrarily large, system limits aside. Since Python's whole-number type is unbounded, there are no limits on the operators. Your code may take however long to run.

# Answer
# 43 bytes

```
(4**n+1)**n%4**n**2/n&2**(2*n*n+n)/-~2**n<1

```

Try it online!

The method is similar to Dennis' second (deleted) answer, but this answer is easier to be proved correct.

# Proof

### Short form

The most significant digit of `(4**n+1)**n%4**n**2` in base \\$2^n\\$ that is not divisible by \\$n\\$ will make the next (less significant) digit in `(4**n+1)**n%4**n**2/n` nonzero (if that "next digit" is not in the fractional part), then a `&` with the bitmask `2**(2*n*n+n)/-~2**n` is executed to check if any digit at odd position is nonzero.

### Long form

Let \\$\[a\_n,\dots,a\_1,a\_0\]\_b\\$ be the number having that base \\$b\\$ representation, i.e., \\$a\_nb^n+\dots+a\_1b^1+a\_0b^0\\$, and \\$a\_i\\$ be the digit at "position" \\$i\\$ in base \\$b\\$ representation.

* \\$\texttt{2\**(2\*n\*n+n)/-~2\**n} =\lfloor{2^{(2n+1)n}\over1+2^n}\rfloor =\lfloor{4^{n^2}\times 2^n\over1+2^n}\rfloor =\lfloor{{(4^{n^2}-1)\times 2^n\over1+2^n} +{2^n\over1+2^n}}\rfloor \\$.

Because \\$2^n\times{4^{n^2}-1\over1+2^n} =2^n(2^n-1)\times{(4^n)^n-1\over4^n-1} =\[2^n-1,0,2^n-1,0,2^n-1,0\]\_{2^n}\\$ (with \\$n\\$ \\$2^n-1\\$s) is an integer, and \\$\lfloor{2^n\over1+2^n}\rfloor=0\\$, `2**(2*n*n+n)/-~2**n` = \\$\[2^n-1,0,2^n-1,0,2^n-1,0\]\_{2^n}\\$.

Next, consider $$\begin{align} \texttt{(4\**n+1)\**n} &=(4^n+1)^n \\ &=\binom n04^{0n}+\binom n14^{1n}+\dots+\binom nn4^{n^2} \\ &=\left\[\binom nn,0,\dots,0,\binom n1,0,\binom n0\right\]\_{2^n} \end{align}$$

\\$4^{n^2}=(2^n)^{2n}\\$, so `%4**n**2` will truncate the number to \\$2n\\$ last digits - that excludes the \\$\binom nn\\$ (which is 1) but include all other binomial coefficients.

About `/n`:

* If \\$n\\$ is a prime, the result will be \\$\left\[\binom n{n-1}/n,0,\dots,0,\binom n1/n,0,0\right\]\_{2^n}\\$. All digits at odd position are zero.
* If \\$n\\$ is not a prime:

Let \\$a\\$ be the largest integer such that \\$n\nmid\binom na\\$ (\\$n\>a\>0\\$). Rewrite the dividend as

\\$\left\[\binom n{n-1},0,\binom n{n-2},0,\dots,\binom n{a+1}, 0,0,0,\dots,0,0,0\right\]\_{2^n} + \left\[\binom na,0,\binom n{a-1},0,\dots,\binom n0\right\]\_{2^n}\\$

The first summand has all digits divisible by \\$n\\$, and the digit at position \\$2a-1\\$ zero.

The second summand has its most significant digit (at position \\$2a\\$) not divisible by \\$n\\$ and (the base) \\$2^n\>n\\$, so the quotient when dividing that by \\$n\\$ would have the digit at position \\$2a-1\\$ nonzero.

Therefore, the final result (`(4**n+1)**n%4**n**2/n`) should have the digit (base \\$2^n\\$, of course) at position \\$2a+1\\$ nonzero.

Finally, the bitwise AND (`&`) performs a vectorized bitwise AND on the digits in base \\$2^n\\$ (because the base is a power of 2), and because \\$a\texttt &0=0,a\texttt&(2^n-1)=a\\$ for all \\$0\le a\<2^n\\$, `(4**n+1)**n%4**n**2/n&2**(2*n*n+n)/-~2**n` is zero iff `(4**n+1)**n%4**n**2/n` has all digits in first \\$n\\$ odd positions zero - which is equivalent to \\$n\\$ being prime.
> 39 votes

# Answer
# Python 2, 56 bytes

```
n**(n*n-n)/(((2**n**n+1)**n**n>>n**n*~-n)%2**n**n)%n>n-2

```

Try it online!

This is a proof-of-concept that this challenge is doable with only arithmetic operators, in particular without bitwise `|`, `&`, or `^`. The code uses bitwise and comparison operators only for golfing, and they can easily be replaced with arithmetic equivalents.

However, the solution is extremely slow, and I haven't been able to run \\$n=6\\$\`, thanks to two-level exponents like \\$2^{n^n}\\$.

The main idea is to make an expression for the factorial \\$n!\\$, which lets us do a Wilson's Theorem primality test \\$(n-1)! \mathbin{\\%} n \> n-2 \\$ where \\$ \mathbin{\\%}\\$ is the modulo operator.

We can make an expression for the binomial coefficient, which is made of factorials

$$\binom{m}{n} \ = \frac{m!}{n!(m-n)!}$$

But it's not clear how to extract just one of these factorials. The trick is to hammer apart \\$n!\\$ by making \\$m\\$ really huge.

$$\binom{m}{n} \ = \frac{m(m-1)\cdots(m-n+1)}{n!}= \frac{m^n}{n!}\cdot \left(1-\frac{1}{m}\right)\left(1-\frac{2}{m}\right)\cdots \left(1-\frac{n-1}{m}\right)$$

So, if we let \\$c \\$ be the product \\$ \left(1-\frac{1}{m}\right)\left(1-\frac{2}{m}\right)\cdots \left(1-\frac{n-1}{m}\right)\\$, we have

$$n! = \frac{m^n}{\binom{m}{n}} \cdot c$$

If we could just ignore \\$c\\$, we'd be done. The rest of this post is looking how large we need to make \\$m\\$ to be able to do this.

Note that \\$c\\$ approaches \\$1\\$ from below as \\$ m \to \infty \\$. We just need to make \\$m\\$ huge enough that omitting \\$c\\$ gives us a value with integer part \\$n!\\$ so that we may compute

$$n! = \left\lfloor \frac{m^n}{\binom{m}{n}} \right\rfloor $$

For this, it suffices to have \\$1 - c \< 1/n!\\$ to avoid the ratio passing the next integer \\$n!+1\\$.

Observe that \\$c\\$ is a product of \\$n\\$ terms of which the smallest is \\$ \left(1-\frac{n-1}{m}\right)\\$. So, we have

$$c \> \left(1-\frac{n-1}{m}\right)^n \> 1 - \frac{n-1}{m} n \> 1-\frac{n^2}{m},$$

which means \\$1 - c \< \frac{n^2}{m}\\$. Since we're looking to have \\$1 - c \< 1/n!\\$, it suffices to take \\$m \geq n! \cdot n^2\\$.

In the code, we use \\$m=n^n\\$. Since Wilson's Theorem uses \\$(n-1)!\\$, we actually only need \\$m \geq (n-1)! \cdot (n-1)^2\\$. It's easy to see that \\$m=n^n\\$ satisfies the bound for the small values and quickly outgrows the right hand side asymptotically, say with Stirling's approximation.
> 9 votes

# Answer
This answer doesn't use any number-theoretic cleverness. It spams Python's bitwise operators to create a manual "for loop", checking all pairs \\$1 \leq i,j \< n\\$ to see whether \\$i \times j = n\\$.

# Python 2, way too many bytes (278 thanks to Jo King in the comments!)

```
((((((2**(n*n)/(2**n-1)**2)*(2**((n**2)*n)/(2**(n**2)-1)**2))^((n*((2**(n*n-n)/(2**n-1))*(2**((n**2)*(n-1))/(2**n**2-1))))))-((2**(n*n-n)/(2**n-1))*(2**((n**2)*(n-1))/(2**(n**2)-1))))&(((2**(n*(n-1))/(2**n-1))*(2**((n**2)*(n-1))/(2**(n**2)-1)))*(2**(n-1)))==0))|((1<n<6)&(n!=4))

```

Try it online!

This is a lot more bytes than the other answers, so I'm leaving it ungolfed for now. The code snippet below contains functions and variable assignment for clarity, but substitution turns isPrime(n) into a single Python expression.

```
def count(k, spacing):
    return 2**(spacing*(k+1))/(2**spacing - 1)**2
def ones(k, spacing):
    return 2**(spacing*k)/(2**spacing - 1)

def isPrime(n):
    x = count(n-1, n)
    y = count(n-1, n**2)
    onebits = ones(n-1, n) * ones(n-1, n**2)
    comparison = n*onebits
    difference = (x*y) ^ (comparison)
    differenceMinusOne = difference - onebits
    checkbits = onebits*(2**(n-1))
    return (differenceMinusOne & checkbits == 0 and n>1)or 1<n<6 and n!=4

```

# Why does it work?

I'll do the same algorithm here in base 10 instead of binary. Look at this neat fraction:

$$ \frac{1.0}{999^2} = 1.002003004005\dots $$

If we put a large power of 10 in the numerator and use Python's floor division, this gives an enumeration of numbers. For example, \\$ 10^{15}/(999^2) = 1002003004 \\$ with floor division, enumerating the numbers \\$ 1,2,3,4 \\$.

Let's say we multiply two numbers like this, with different spacings of zeroes. I'll place commas suggestively in the product.

$$ 1002003004 \times 1000000000002000000000003000000000004 = $$ $$ 1002003004,002004006008,003006009012,004008012016 $$

The product enumerates, in three-digit sequences, the multiplication table up to 4 times 4. If we want to check whether the number 5 is prime, we just have to check whether \\$ 005 \\$ appears anywhere in that product.

To do that, we XOR the above product by the number \\$ 005005005\dots005 \\$, and then subtract the number \\$ 001001001\dots001 \\$. Call the result \\$d\\$. If \\$ 005 \\$ appeared in the multiplication table enumeration, it will cause the subtraction to carry over and put \\$ 999 \\$ in the corresponding place in \\$d\\$.

To test for this overflow, we compute an AND of \\$d\\$ and the number \\$ 900900900\dots900 \\$. The result is zero if and only if 5 is prime.
> 4 votes

---
Tags: code-golf, decision-problem, restricted-source, primes, python
---


# Question
Title: I'm thinking of a number (Robber's thread)
> Cop's thread here

In this challenge cops will think of a positive integer. They will then write a program or function that outputs one value when provided the number as input and another value for all other positive integer inputs. Cops will then reveal the program in an answer keeping the number a secret. Robbers can crack an answer by finding the number.

Your job as robbers is to find that number. Once found you can make an answer here detailing the number and how you found it. You should link the original answer being cracked in your answer.

Your score will be the number of cracks with more being better.

# Answer
> 9 votes
# Java, by okx

Note: the original challenge to which this post answers has been deleted, it's however still accessible with the link to anyone having the privilege to see deleted answers. The explanations below include what the challenge was about.

**Number: `18`**

The code is effectively looking for primes with the form 112*n*-2.

By this Wikipedia list, we know that the 20th largest known prime number has 2,900,832 digits. No prime with the form 112*n*-2 are in that list, so that digit number will be our limit.

All numbers of the form 112*n*-2 that have at most that many digits have this constraint: `n < 22`. Factordb tells us that 11222-2 has 4,367,918 digits. This is proof enough.

The code by okx limits us to `n` above 6.

So, let's do the list:

112*n*-2 is factorizable for `n` = , , , 10, 11, 12, 13, 14, 15, 16, 17, 19, 20 and 21 (factors proofs are on factordb.com and wolfram alpha; factordb has some proofs that wolfram alpha hasn't and vice-versa).

The only value `n` for which we can't prove the factorization is 18 (factordb, WolframAlpha).

So (a) if there is a prime number of the form 112*n*-2 with `n > 6`, then (b) `6 < n < 22`, and (c) I proved each number with such `n` is composite except for 18, so (d) the prime we're looking for has `n = 18`.

Note that I don't exclude that 11218-2 is composite. I haven't proved that that number is a prime: I only proved that if the OP thought about that number, it can only be 18. If that number is indeed a prime, congrats to okx for finding it :-)

### However

There are no proof that 11218-2 is the only number, though. It's the only number in the range of numbers for which we can currently prove the primality.

So I don't exclude the fact that one day someone might prove that 11251-2 or 112124-2 is prime.

I therefore believe that the original entry by okx is invalid because there are no such proof that for `n` between 19 and the (231-1)231-1 (the theoretical limit of Java's `BigInteger`), there are no other primes.

# Answer
> 9 votes
# Perl 6, by Ramillies

```
11

```

The function `series($x)` is simply the first 108 terms of the Taylor series for `e^x` evaluated at `i*(x % 8*π)`. Since `e^2πi = 1`, this reduces to simply `e^ix`: the `% 8*π` serves only to bound the error of the truncated series.

The  function integrates the provided `Callable` in the interval `[0,2π]` using the trapezoid method. The integrand in question is `(e^ix)^11/(e^inx)`, or simply `e^(11-n)ix`. This integrates to 0 in that interval for all `n != 11`. At `n = 11`, the integrand reduces to simply `1`. Hence the answer is `11`, and the desired output is `6.28`.

While `11` is the only answer in theory, the sampling in the integral is imperfect. Consequently, any integer of the form `87931k+11` should work.

# Answer
> 8 votes
# Python 3, Erik Brody Dreyer

### Number: `105263157894736842`

Try it online!

---

### How?

Everyone's favorite tool: OEIS!

1. Go to oeis.org
2. Search "last digit first doubles number"
3. Find Entry A087502 entitled
> Smallest positive integer which when written in base n is doubled when the last digit is put first.
4. Find the base 10 entry (105263157894736842)
5. Confirm it works

# Answer
> 8 votes
# Tampio, fergusq

**Number: `27`**

The program prints `nolla` for 27 and `"1" negatiivisena` for all other inputs. It times out on TIO, unfortunately, but works offline.

Whew, this was a fun one to work through. Wiktionary and this Finnish dictionary I found online actually helped a surprising amount, as a lot of Tampio syntax relies on inflection.

I first tried translating the program into Haskell-like pseudocode, but the "case system" of Tempio and how function calls worked kept tripping me up. Eventually, I ended up running all of the code from the definition of `sata` downward, which gave me surprisingly easily that `sata == 55`, and `funktio` wasn't difficult to reverse engineer from there as it was simple arithmetic that could be deduced from trial and error.

# Answer
> 7 votes
# JavaScript, by Eli R

The number is `7464822360768511`

I first disabled the anti-debugging function (by overwriting `Function.prototype.constructor` to a function with evals any code except `debugger`) then debugged the guess function by stepping into it.

From what I understood the guess function initializes a random number generator on a fixed seed then generate a random number and compare it to the input. As the input isn't used in the random number generation it can be ignored allowing to skip directly to the result.

# Answer
> 5 votes
# Jelly, Erik the Outgolfer's answer

**Number: `134`**

The following program:

```
5ȷ2_c⁼“ḍtṚøWoḂRf¦ẓ)ṿẒƓSÑÞ=v7&ðþạẆ®GȯżʠṬƑḋɓḋ⁼Ụ9ḌṢE¹’

```

can be cracked using the number `134`. This outputs `0` for all numbers except for `134`, which gives `1`.

**Try it online!**

---

# How did I find it?

TBH, I have no idea how it works. I have added `Ç€G` at the end and mapped over `[1...1000]` to see where the `1` is. Then, I ran script to count the number of zeros before the `1`.

# Answer
> 5 votes
# Ly, LyricLy

Answer: 239

I already wrote two Ly programs, so this wasn't too difficult. I think I would have somehow used the result from the loop in case someone tries to remove it. BTW, the fragment `nI` means that it doesn't always terminate successfully.

# Answer
> 5 votes
# Python 2, Sisyphus

```
print~~[all([c[1](c[0](l))==h and c[0](l)[p]==c[0](p^q) for c in [(str,len)] for o in [2] for h in [(o*o*o+o/o)**o] for p,q in [(60,59),(40,44),(19,20),(63,58),(61,53),(12,10),(43,42),(1,3),(35,33),(37,45),(17,18),(32,35),(20,16),(22,30),(45,43),(48,53),(58,59),(79,75),(68,77)]] + [{i+1 for i in f(r[5])}=={j(i) for j in [q[3]] for i in l} for q in [(range,zip,str,int)] for r in [[3,1,4,1,5,9]] for g in [q[1]] for s in [[p(l)[i:i+r[5]] for p in [q[2]] for i in [r[5]*u for f in [q[0]] for u in f(r[5])]]] for l in s + g(*s) + [[z for y in [s[aprint~~[all([c[1](c[0](l))==h and c[0](l)[p]==c[0](p^q) for c in [(str,len)] for o in [2] for h in [(o*o*o+o/o)**o] for p,q in [(60,59),(40,44),(19,20),(63,58),(61,53),(12,10),(43,42),(1,3),(35,33),(37,45),(17,18),(32,35),(20,16),(22,30),(45,43),(48,53),(58,59),(79,75),(68,77)]] + [{i+1 for i in f(r[5])}=={j(i) for j in [q[3]] for i in l} for q in [(range,zip,str,int)] for r in [[3,1,4,1,5,9]] for g in [q[1]] for s in [[p(l)[i:i+r[5]] for p in [q[2]] for i in [r[5]*u for f in [q[0]] for u in f(r[5])]]] for l in s + g(*s) + [[z for y in [s[i+a][j:j+r[0]] for g in [q[0]] for a in g(r[0])] for z in y] for k in [[w*r[0] for i in [q[0]] for w in i(r[0])]] for i in k for j in k] for f in [q[0]]]) for l in [int(raw_input())]][0]

```

Try it online!

Answer:

```
126437958895621473374985126457193862983246517612578394269314785548769231731852649

```

## Explanation

Slightly less convoluted:

```
print~~[all(
	[len(str(l))==81 and str(l)[p]==str(p^q)
		for p,q in [(60,59),(40,44),(19,20),(63,58),(61,53),(12,10),(43,42),(1,3),(35,33),(37,45),(17,18),(32,35),(20,16),(22,30),(45,43),(48,53),(58,59),(79,75),(68,77)]
	]
	+
	[{i+1 for i in range(9)}=={int(i) for i in l}
		for s in [[str(l)[9*u:9*u+9] for u in range(9)]]
			for l in s + zip(*s) + [[z for y in [s[i+a][j:j+3] for a in range(3)] for z in y] for k in [[w*3 for w in range(3)]] for i in k for j in k]]) for l in [int(raw_input())]][0]

```

Try it online!

Firstly, this part:

```
[len(str(l))==81 and str(l)[p]==str(p^q)
        for p,q in [(60,59),(40,44),(19,20),(63,58),(61,53),(12,10),(43,42),(1,3),(35,33),(37,45),(17,18),(32,35),(20,16),(22,30),(45,43),(48,53),(58,59),(79,75),(68,77)]
]

```

checks if the sudoku is in the following form:

```
.2.|...|...
...|6..|..3
.74|.8.|...
-----------
...|..3|..2
.8.|.4.|.1.
6..|5..|...
-----------
...|.1.|78.
5..|..9|...
...|...|.4.

```

Then this part checks for validity:

```
[{i+1 for i in range(9)}=={int(i) for i in l}
        for s in [[str(l)[9*u:9*u+9] for u in range(9)]]
            for l in s + zip(*s) + [[z for y in [s[a][j:j+3] for a in range(3)] for z in y] for k in [[w*3 for w in range(3)]] for i in k for j in k]]

```

# Answer
> 3 votes
# Pyth, Mr. Xcoder

```
hqQl+r@G7hZ@c." y|çEC#nZÙ¦Y;åê½9{ü/ãÑª#¤
ØìjX\"¦Hó¤Ê#§T£®úåâ«B'3£zÞz~Ð£ë"\,a67Cr@G7hZ

```

Try it here. Number: `9`

# Answer
> 3 votes
# Swift 3, TheIOSCoder

**Number: `387849`.**

This returns `222` for the number above, and `212` for others.

**Test Here.**

---

# How?

The relation is quite obvious: `.pi*123456.0` multiplies `3.1415...` by `123456.0` and converts it to an Integer. This means it is equal to `387848`. Then, it checks if the parameter equals the number above incremented by `1` (`n==1+...`). The value is `387848 + 1`, which is `387849`...

# Answer
> 3 votes
# Java, Sleafar

```
23

```

The program traces `n` iterations of a fractal, and checks whether a specific point is removed in the `n`th iteration. In each iteration, each segment is replaced by eight smaller segments in the following pattern:

```
  +
  |
+-+
|
+-+-+
    |
  +-+
  |
  +

```

Since no points are ever added to the line `y=.5` after the first iteration, I only had to handle the set of points included along this line. This set is similar to the construction of the Cantor set, but with the middle half removed instead of the middle third.

The program I used to crack it:

```
import java.math.BigDecimal;

public class Main {

        public static int f(BigDecimal x) {
                BigDecimal[] result = x.divideAndRemainder(BigDecimal.ONE);
                if (result[0].compareTo(BigDecimal.ZERO) == 0 || result[0].compareTo(BigDecimal.valueOf(3)) == 0) {
                        return 1+f(result[1].multiply(BigDecimal.valueOf(4)));
                }
                return 0;
        }

	public static void main(String[] args) {
		BigDecimal x = new BigDecimal(args[0]);
		System.out.println(f(x));
	}
}

```

Try it online!

# Answer
> 2 votes
# Haskell, flawr

I think the number is 12018.

I found it by defining in PARI/GP `f(x,k)=1/x^2-1/x^(2-1/k)` and `g(k)=sumpos(x=1,f(x,k))-sumpos(x=12345679,f(x,k))` and some binary searching.

I don't like that one could trivially transform the program into one that returns the number and uses the same time and memory as the original program needs for any input.

# Answer
> 2 votes
# Brain-Flak, Nitrodon

The number is:

```
1574

```

Try it online!

Here's the program I use to crack it

```
n!(0:_)=n
n!a=(n+1)!zipWith(+)a(tail a++[0])
main=print$0![45646,253224,392678,8676,-24]

```

Try it online!

# Answer
> 2 votes
# Java, user902383

The secret number is `3141592`

Explanation:

After expanding all the `\u00xx` escapes, you get:

```
public class Mango {
static void convert(String s){for(char c : s.toCharArray()){ System.out.print("\\u00"+Integer.toHexString(c));}}
public static void main(String[] args) {int x  = Integer.parseInt(args[0]);
double a= x/8.-392699;double b = Math.log10((int) (x/Math.PI+1))-6;
System.out.println((a/b==a/b?"Fail":"OK" ));
}}

```

(the `convert` method isn't used).

This computes some floating point math on the result, and then requires that `a/b` isn't equal to itself. The number for which that is true is `nan`, which is produced by `0/0`. It turns out that if `a` is 0, then `b` is `log10(0/pi + 1)` which is also 0, so `a` has to be 0 and x has to be `392699*8`.

# Answer
> 2 votes
# Python 3, user71546

```
def check(x):
    if x < 0 or x >= 5754820589765829850934909 or pow(x, 18446744073709551616, 5754820589765829850934909) != 2093489574700401569580277 or x % 4 != 1:
        return "No way ;-("
    return "Cool B-)"

print(check(141421356237))

```

Try it online!

The number is **141421356237**.

The other three numbers which satisfy the first two conditions are 1459265341309891512760823, 5754820589765688429578672, and 4295555248455938338174086.

### How I solved it

The gist of this challenge is to find the number that meets the following, given the prime `p = 5754820589765829850934909` and a value `a = 2093489574700401569580277`:

* `0 <= x < p`
* `x ** (2 ** 64) % p == a`
* `x % 4 == 1`

The second one can be rephrased to "find the modular square root of modular square root of ... (64 times) of `a` modulo `p`."

Since the given prime is 5 modulo 8, we can use the following formula from the above link (though I couldn't find the reference that supports it):

\\$ v = (2a)^{(p-5)/8} \mod p \\$

\\$ i = 2av^2 \mod p \\$

\\$ r = av(i-1) \mod p \\$

\\$ r' = p - r \\$

Then we have two output values `r` and `r'` for an input value `a`. But not every number has such a square root, so we have to check if `r*r % p == a` is actually met.

So I wrote a quick J script to find the 64th modular square roots.

```
p =: 5754820589765829850934909x
a =: 2093489574700401569580277x
powmod =: p&|@^

f =: monad define
for. i.64 do.
  v =: p | (2*a) powmod (p-5)%8
  i =: p | 2*a*v*v
  x =: p | a*v*i-1    NB. Apply the above formula
  a =: (a=p|x*x) # x  NB. Filter by actually being the modular square root
  a =: a, p-a         NB. Concat r with r'
  a
end.
)

res =: f ''

```

Try it online!

`res` has the four values shown above; the last filtering by modulo 4 gives the answer.

---
Tags: code-challenge, cops-and-robbers
---


title: Find Array Runs

text:
# Question
Title: Find Array Runs
**Find the runs inside an array**

A run is defined as three or more numbers that increment from the previous with a constant step. For example `[1,2,3]` would be a run with step 1, `[1,3,5,7]` would be a run with step 2, and `[1,2,4,5]` is not a run.

We can express these runs by the notation `i to j by s` where `i` is the first number of the run, `j` is the last number of the run, and `s` is the step. However, runs of step 1 will be expressed `i to j`.

So using the arrays before, we get:

* `[1,2,3] -> "1to3"`
* `[1,3,5,7] -> "1to7by2"`
* `[1,2,4,5] -> "1 2 4 5"`

In this challenge, it is your task to do this for arrays that may have multiple runs.

**Example Python code with recursion**

IO is flexible

**Input**

Array of sorted positive ints (no duplicates)

**Output**

String of the runs separated by a space, or a string array of the runs

Does not need to be greedy in a particular direction

Can have trailing whitespace

**Test Cases**

```
In: [1000, 1002, 1004, 1006, 1008, 1010]
Out: "1000to1010by2"

In: [1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233]
Out: "1to3 5 8 13 21 34 55 89 144 233"

In: [10, 20, 30, 40, 60]
Out: "10to40by10 60"

In: [5, 6, 8, 11, 15, 16, 17]
Out: "5 6 8 11 15to17"

In: [1, 2, 3, 4, 5, 6, 7, 9, 11, 13, 15, 30, 45, 50, 60, 70, 80, 90, 91, 93]
Out: "1to7 9to15by2 30 45 50to90by10 91 93"

```

This is so least number of bytes wins.

# Answer
> 5 votes
# Jelly,  ~~42~~  40 bytes

-2 thanks to Kevin Cruijssen (filter out twos, `ḟ2`, rather than replacing twos with zeros, `2,0y`)

```
ŒṖIE×LƲ€ḟ2SƊÞṪµ.ịU,Iḟ1ƊQ€Fż“to“by”ṁṖƊ$)K

```

A full program printing the result.
(As a monadic Link a list containing a mixture of integers and characters would be yielded)

**Try it online!**
(Too inefficient for the largest test-case to complete within 60s, so I removed `[1,2,3,4]`.)

### How?

```
ŒṖIE×LƲ€ḟ2SƊÞṪµ.ịU,Iḟ1ƊQ€Fż“to“by”ṁṖƊ$)K - Main Link: list of numbers
ŒṖ                                       - all partitions
           ƊÞ                            - sort by last three links as a monad:
      Ʋ€                                 -   last four links as a monad for €ach:
  I                                      -     incremental differences (of the part)
   E                                     -     all equal?
     L                                   -     length (of the part)
    ×                                    -     multiply
        ḟ2                               -   filter discard twos
          S                              -   sum
             Ṫ                           - tail (gets us the desired partition of the input)
              µ                       )  - perform this monadic chain for €ach:
               .                         -   literal 0.5
                ị                        -   index into (the part) - getting [tail,head]
                 U                       -   upend - getting [head,tail]
                      Ɗ                  -   last three links as a monad:
                   I                     -     incremental differences (of the part)
                     1                   -     literal one
                    ḟ                    -     filter discard (remove the ones)
                  ,                      -   pair -> [[head,tail],[deltasWithoutOnes]]
                       Q€                -   de-duplicate €ach -> [[head,tail],[delta]] or [[head,tail],[]] or [[loneValue],[]]
                         F               -   flatten -> [head,tail,delta] or [head,tail] or [loneValue]
                                     $   -   last two links as a monad:
                                    Ɗ    -     last three links as a monad:
                           “to“by”       -       literal list [['t', 'o'], ['b', 'y']]
                                   Ṗ     -       pop (get flattened result without rightmost entry)
                                  ṁ      -       mould ["to","by"] like that (i.e. ["to","by"] or ["to"] or [])
                         ż               -     zip together
                                       K - join with spaces
                                         - implicit print

```

# Answer
> 6 votes
# Swift, 246 bytes

```
func f(_ a:[Int]){
var c=a.count,m=a+a,z=0,r:String=""
for i in 1..<c{m[i]-=a[i-1];if m[i]==m[i-1]{m[i-1]=0}};m[0]=1
for i in 0..<c{if m[i]==0 {z=1}else if z==0{r+=" \(a[i])"}else{r+="to\(a[i])"+(m[i]>1 ? "by\(m[i])":"");z=0;m[i+1]=1}}
print(r)
}

```

Try it online!

# Answer
> 3 votes
# K (ngn/k), 102 bytes

```
{1_,//${H:" ",h:*x;l:+/&\x=h+(!#x)*d:--/2#x;$[l>2;(H;"to";x l-1;(~d=1)#,"by",d;o l_x);l;H,o 1_x;""]}x}

```

Try it online!

# Answer
> 3 votes
# JavaScript (ES6), 129 bytes

Returns an array of strings.

```
a=>(a.map((n,i)=>n+[n-a[i+1]||''])+'').replace(/(\d+)(-\d+)(?:,\d+\2)+,(\d+)/g,(_,a,b,c)=>a+'to'+(~b?c+'by'+-b:c)).split(/-\d+,/)

```

Try it online!

## How?

### Step #1

We first append to each number a suffix consisting of a leading `'-'` followed by the difference with the next number, except for the last entry which is left unchanged. This new array is coerced to a string.

```
(a.map((n, i) => n + [n - a[i + 1] || '']) + '')

```

Example:

```
Input : [ 1, 2, 3, 5, 9, 11, 13, 20 ]
Output: "1-1,2-1,3-2,5-4,9-2,11-2,13-7,20"

```

### Step #2

We identify all runs in the resulting string and replace them with the appropriate notation.

```
.replace(
  /(\d+)(-\d+)(?:,\d+\2)+,(\d+)/g,
  (_, a, b, c) => a + 'to' + (~b ? c + 'by' + -b : c)
)

```

Example:

```
Input : "1-1,2-1,3-2,5-4,9-2,11-2,13-7,20"
Output: "1to3-2,5-4,9to13by2-7,20"

```

### Step #3

Finally, we split the string on the remaining suffixes, including the trailing commas.

```
.split(/-\d+,/)

```

Example:

```
Input : "1to3-2,5-4,9to13by2-7,20"
Output: [ '1to3', '5', '9to13by2', '20' ]

```

# Answer
> 2 votes
# Ruby, ~~125~~ 118 bytes

```
->a{i=y=0;a.chunk{|x|-y+y=x}.map{|z,w|2-i<(s=w.size)?"#{w[i*s]}to#{w[~i=0]}"+"by#{z}"*(z<=>1)+' ':' '*i+w*' '*i=1}*''}

```

Try it online!

### Explanation

Ruby's Enumerable has a useful `chunk` method that does precisely what we need here - it groups items by consecutive runs of the same return value from the block, in our case - the difference between the current (`x`) and previous (`y`) value.

The caveat is that such strategy won't capture the first element of the run, e.g. here only the two last elements are grouped together:

```
Input: [5, 6, 8, 11, 15, 16, 17]
Grouped: [[5, [5]], [1, [6]], [2, [8]], [3, [11]], [4, [15]], [1, [16, 17]]]

```

Therefore, while mapping to the correctly formatted strings, when we encounter a new potential run (chunk with \> 1 item), we must track if the previous item was single (`i=1`) or already used in another run (`i=0`). If there is an unused single item, it becomes the starting point of the run, and lowers the chunk size threshold from 3 to 2.

# Answer
> 2 votes
# , ~~238~~ 217 bytes

Thanks @digEmAll for -19 bytes.

```
function(v,R=rle(diff(v)),L=R$l,S=sum(L|1),Y=0)if(!S)cat(v)else for(i in 1:S){D=R$v[i]
N=L[i]-F
if(N>1){N=N+1
cat(v[Y+1],'to',v[Y+N],'by'[D>1],D[D>1],' ',sep='')
F=1}else{N=N+(i==S)
if(N>0)cat(v[Y+1:N],'')
F=0}
Y=Y+N}

```

Try it online!

# Answer
> 2 votes
# , ~~180~~ 175 bytes

```
r=rle(c(0,diff(a<-scan())));for(j in 1:sum(1|r$l)){l=r$l[j];v=r$v[j];i=T+l-1;cat("if"(l>2-F,paste0(a[T][!F],"to",a[i],"by"[v>1],v[v>1]," "),c("",a[T:i])[-3^F]));T=i+1;F=l<3-F}

```

Try it online!

Conceptually, this is a port of my Ruby answer, though obviously quite a bit different technically.

5 bytes saved by JayCe.

# Answer
> 1 votes
# Clean, ~~208~~ ... 185 bytes

```
import StdEnv,Data.List,Text
l=length
$[]=""
$k=last[u<+(if(v>[])("to"<+last v<+if(u<v!!0-1)("by"<+(v!!0-u))"")"")+" "+ $t\\i=:[u:v]<-inits k&t<-tails k|l(nub(zipWith(-)i v))<2&&l i<>2]

```

Try it online!

# Answer
> 1 votes
# JavaScript (Node.js), ~~177~~ 173 bytes

```
a=>{for(h=t=p=d=0,o=[];(c=a[t])||h<t;p=c,t++)d||!c?c-p!=d?(o.push(...[[a[h]+"to"+p+(d>1?"by"+d:"")],[p],[p-d,p]][t-h<3?t-h:0]),d=0,h=t--):0:!d&&t-h?d=c-p:0;return o.join` `}

```

Try it online!

# Answer
> 1 votes
# Python 2, ~~170~~ 166 bytes

```
def f(a):
 j=len(a)
 while j>2:
	l,r=a[:j:j-1];s=(r-l)/~-j
	if a[:j]==range(l,r+1,s):return[`l`+'to%d'%r+'by%d'%s*(s>1)]+f(a[j:])
	j-=1
 return a and[`a[0]`]+f(a[1:])

```

Try it online!

# Answer
> 1 votes
# Jelly, 41 bytes

```
ŒṖIE€Ạ$>Ẉ2eƊƲƇṪµ.ịṚj⁾to;IḢ⁾by;ẋ⁻1$ƲƊµḊ¡€K

```

Try it online!

Full program.

# Answer
> 1 votes
# gvm (commit 2612106) bytecode, 108 bytes

Expects the size of the array in one line, then the members each in one line.

Hexdump:

```
> hexdump -C findruns.bin
00000000  e1 0a 00 10 00 e1 0b 00  ff c8 92 00 f4 f7 10 00  |................|
00000010  01 b0 20 03 00 ff 0a 01  a2 01 c8 92 00 f4 01 c0  |.. .............|
00000020  03 00 ff 0a 02 d0 72 01  0a 03 c8 92 00 f4 05 b0  |......r.........|
00000030  20 a2 02 c0 02 02 6a 03  8b 00 ff f6 06 b0 20 a2  | .....j....... .|
00000040  02 f4 ce 0a 02 c8 92 00  f6 07 6a 03 8b 00 ff f6  |..........j.....|
00000050  f2 b9 66 01 a2 02 00 01  8a 03 f6 05 b9 69 01 a2  |..f..........i..|
00000060  03 92 00 f4 ac c0 74 6f  00 62 79 00              |......to.by.|
0000006c

```

Test runs:

```
> echo -e "7\n5\n6\n8\n11\n15\n16\n17\n" | ./gvm findruns.bin
5 6 8 11 15to17
> echo -e "20\n1\n2\n3\n4\n5\n6\n7\n9\n11\n13\n15\n30\n45\n50\n60\n70\n80\n90\n91\n93\n" | ./gvm findruns.bin
1to7 9to15by2 30 45 50to90by10 91 93

```

Manually assembled from this:

```
0100  e1        rud                     ; read length of array
0101  0a 00     sta     $00             ; -> to $00
0103  10 00     ldx     #$00            ; loop counter
                  readloop:
0105  e1        rud                     ; read unsigned number
0106  0b 00 ff  sta     $ff00,x         ; store in array at ff00
0109  c8        inx                     ; next index
010a  92 00     cpx     $00             ; length reached?
010c  f4 f7     bne     readloop        ; no -> read next number
010e  10 00     ldx     #$00            ; loop counter
0110  01                                ; 'lda $20b0', to skip next instruction
                  runloop:
0111  b0 20     wch     #' '            ; write space character
0113  03 00 ff  lda     $ff00,x         ; load next number from array
0116  0a 01     sta     $01             ; -> to $01
0118  a2 01     wud     $01             ; and output
011a  c8        inx                     ; next index
011b  92 00     cpx     $00             ; length reached?
011d  f4 01     bne     compare         ; if not calculate difference
011f  c0        hlt                     ; done
                  compare:
0120  03 00 ff  lda     $ff00,x         ; load next number from array
0123  0a 02     sta     $02             ; -> to $01
0125  d0        sec                     ; calculate ...
0126  72 01     sbc     $01             ; ... difference ...
0128  0a 03     sta     $03             ; ... to $03
012a  c8        inx                     ; next index
012b  92 00     cpx     $00             ; length reached?
012d  f4 05     bne     checkrun        ; if not check whether we have a run
012f  b0 20     wch     #' '            ; output space
0131  a2 02     wud     $02             ; output number
0133  c0        hlt                     ; done
                  checkrun:
0134  02 02     lda     $02             ; calculate next ...
0136  6a 03     adc     $03             ; ... expected number in run
0138  8b 00 ff  cmp     $ff00,x         ; compare with real next number
013b  f6 06     beq     haverun         ; ok -> found a run
013d  b0 20     wch     #' '            ; otherwise output space ...
013f  a2 02     wud     $02             ; ... and number
0141  f4 ce     bne     runloop         ; and repeat searching for runs
                  haverun:
0143  0a 02     sta     $02             ; store number to $02
0145  c8        inx                     ; next index
0146  92 00     cpx     $00             ; length reached?
0148  f6 07     beq     outputrun       ; yes -> output this run
014a  6a 03     adc     $03             ; calculate next expected number
014c  8b 00 ff  cmp     $ff00,x         ; compare with real next number
014f  f6 f2     beq     haverun         ; ok -> continue parsing run
                  outputrun:
0151  b9 66 01  wtx     str_to          ; write "to"
0154  a2 02     wud     $02             ; write end number of run
0156  00 01     lda     #$01            ; compare #1 with ...
0158  8a 03     cmp     $03             ; ... step size
015a  f6 05     beq     skip_by         ; equal, then skip output of "by"
015c  b9 69 01  wtx     str_by          ; output "by"
015f  a2 03     wud     $03             ; output step size
                  skip_by:
0161  92 00     cpx     $00             ; length of array reached?
0163  f4 ac     bne     runloop         ; no -> repeat searching for runs
0165  c0        hlt                     ; done
                  str_to:
0166  74 6f 00                          ; "to"
                  str_by:
0169  62 79 00                          ; "by"
016c

```

# Answer
> 1 votes
# Python 2, ~~138~~ 136 bytes

-2 bytes thanks to Erik the Outgolfer.

```
r=[];d=0
for n in input()+[0]:
 a=n-([n]+r)[-1]
 if(a-d)*d:
	if r[2:]:r=["%dto"%r[0]+`r[-1]`+"by%s"%d*(1%d)]
	print r.pop(0),
 r+=n,;d=a

```

Try it online!

# Answer
> 1 votes
# 05AB1E (legacy), ~~49~~ 50 bytes

```
.œʒε¥Ë}P}Σ€g2KO>}¤εD©g≠i¬s¤„toý¬®¥0èDU≠i„byX««]˜ðý

```

Way too long, but I'm already glad it's working. This challenge is a lot harder than it looks imo.. Can without a doubt be golfed further.
`Σ€g2KO>}¤` is a port of `2,0ySƲÞṪ` from *@JonathanAllan*'s Jelly answer (thanks!).

Try it online. (NOTE: Times out for the big test cases.)

+1 byte as bug-fix because `0` is always put at a trailing position when sorting.

**Explanation:**

```
.œ                       # Get all partions of the (implicit) input-list
                         #  i.e. [1,2,3,11,18,20,22,24,32,33,34]
                         #   → [[[1],[2],[3],[11],[18],[20],[22],[24],[32],[33],[34]],
                         #      [[1],[2],[3],[11],[18],[20],[22],[24],[32],[33,34]],
                         #      [[1],[2],[3],[11],[18],[20],[22],[24],[32,33],[34]],
                         #      ...]
  ʒ     }                # Filter this list by:
   ε  }                  #  Map the current sub-list by:
    ¥Ë                   #   Take the deltas, and check if all are equal
                         #    i.e. [1,2,3] → [1,1] → 1
                         #    i.e. [1,2,3,11] → [1,1,8] → 0
       P                 #  Check if all sub-list have equal deltas
  Σ      }               # Now that we've filtered the list, sort it by:
   €g                    #  Take the length of each sub-list
                         #   i.e. [[1,2,3],[11,18],[20,22,24],[32,33],[34]]
                         #    → [3,2,3,2,1]
                         #   i.e. [[1,2,3],[11],[18,20,22,24],[32,33,34]]
                         #    → [3,1,4,3]
     2K                  #  Remove all 2s
                         #   i.e. [3,2,3,2,1] → ['3','3','1']
       O                 #  And take the sum
                         #   i.e. ['3','3','1'] → 7
                         #   i.e. [3,1,4,3] → 11
        >                #  And increase the sum by 1 (0 is always trailing when sorting)
          ¤              # And then take the last item of this sorted list
                         #  i.e. for input [1,2,3,11,18,20,22,24,32,33,34]
                         #   → [[1,2,3],[11],[18,20,22,24],[32,33,34]]
  ε                      # Now map each of the sub-lists to:
   D©                    #  Save the current sub-list in the register
     g≠i                 #  If its length is not 1:
                         #    i.e. [11] → 1 → 0 (falsey)
                         #    i.e. [18,20,22,24] → 4 → 1 (truthy)
        ¬s¤              #   Take the head and tail of the sub-list
                         #    i.e. [18,20,22,24] → 18 and 24
           „toý          #   And join them with "to"
                         #    i.e. 18 and 24 → ['18to24', '18to20to22to24']
               ¬         #   (head to remove some access waste we no longer need)
                         #    i.e. ['18to24', '18to20to22to24'] → '18to24'
        ®                #   Get the sub-list from the register again
         ¥               #   Take its deltas
                         #    i.e. [18,20,22,24] → [2,2,2]
          0è             #   Get the first item (should all be the same delta)
                         #    i.e. [2,2,2] → 2
            DU           #   Save it in variable `X`
              ≠i         #   If the delta is not 1:
                         #     i.e. 2 → 1 (truthy)
                „byX«    #    Merge "by" with `X`
                         #     i.e. 2 → 'by2'
                     «   #    And merge it with the earlier "#to#"
                         #     i.e. '18to24' and 'by2' → '18to24by2'
                      ]  # Close the mapping and both if-statements
˜                        # Flatten the list
                         #  i.e. ['1to3',[11],'18to24by2','32to34']
                         #   → ['1to3',11,'18to24by2','32to34']
 ðý                      # And join by spaces (which we implicitly output as result)
                         #  i.e. ['1to3',11,'18to24by2','32to34']
                         #   → '1to3 11 18to24by2 32to34'

```

# Answer
> 0 votes
# Perl 5, 154 bytes

```
{my(@r,$r);@r&&(@$r<2||$$r[1]-$$r[0]==$_-$$r[-1])?push@$r,$_:push@r,$r=[$_]for@_;join" ",map@$_<3?@$_:("$$_[0]to$$_[-1]by".($$_[1]-$$_[0]))=~s/by1$//r,@r}

```

Same with spaces, newlines, #comments and `sub by`:

```
sub by {
  my(@r,$r);
  @r &&                               # if at least one run candidate exists and...
   ( @$r<2                            # ...just one elem so far
     || $$r[1]-$$r[0] == $_-$$r[-1] ) # ...or diff is same
    ? push @$r, $_                    # then add elem to curr. run candidate
    : push @r, $r=[$_]                # else start new run cand. with curr elem
        for @_;
  join " ",
    map @$_<3                                         # is it a run?
    ? @$_                                             # no, just output the numbers
    : ("$$_[0]to$$_[-1]by".($$_[1]-$$_[0]))=~s/by1$//r, # yes, make run, delete by1
    @r                                                # loop run candidates
}

```

Try it online!

...for passing tests from OP.

# Answer
> 0 votes
# Retina 0.8.2, 77 bytes

```
\d+
$*
(1+)(?= \1(1+))
$1:$2
1:(1+) (1+:\1 )+(1+)
1to$3by$1
:1+|by1\b

1+
$.&

```

Try it online! Link includes test cases. Explanation:

```
\d+
$*

```

Convert to unary.

```
(1+)(?= \1(1+))
$1:$2

```

Compute consecutive differences.

```
1:(1+) (1+:\1 )+(1+)
1to$3by$1

```

Convert runs to `to...by` syntax.

```
:1+|by1\b

```

Remove unconverted differences and `by1`.

```
1+
$.&

```

Convert to decimal.

---
Tags: code-golf, array
---


# Question
Title: Convert a percentage to a "simple" ratio
You run a political website, and have determined that people have a better intuitive understanding when the chance of winning or losing an election is expressed as a *ratio* ("5 in 7") than when it is expressed as a *percentage* ("71%").

But you also don't want to display confusing ratios like "58 in 82", you'd like them to be more easily understood, even if they aren't quite as precise.

So, **given a percentage between 0.1% and 99.9%, return the closest "easy-to-understand" ratio "*x in y*", using the following rules**:

1. Most values (see exceptions below) should return the **closest ratio out of 10 or lower**. 55% should return "5 in 9", not "11 in 20".
2. Ratios should be **reduced to their lowest terms**. 65% should return "2 in 3", not "4 in 6".
3. Values under 10% should return the **closest ratio of the form "*1 in n*" where *n* is one of (10,12,15,20,30,40,50,60,70,80,90,100)**. For example, 6% should return "1 in 15".
4. Values over 90% should return the **closest ratio of the form "*n-1 in n*" where *n* is one of (10,12,15,20,30,40,50,60,70,80,90,100)**. For example, 98.7% should return "79 in 80".
5. Values under 1% should return "**\<1 in 100**"
6. Values over 99% should return "**\>99 in 100**"

Or, to think about it another way, your program should return the **closest ratio from the following possible outputs** (I've included their approximate values for your convenience):

```
<1 in 100
 1 in 100  = 1.00%
 1 in 90   = 1.11%
 1 in 80   = 1.25%
 1 in 70   = 1.43%
 1 in 60   = 1.67%
 1 in 50   = 2.00%
 1 in 40   = 2.50%
 1 in 30   = 3.33%
 1 in 20   = 5.00%
 1 in 15   = 6.67%
 1 in 12   = 8.33%
 1 in 10   = 10.00%
 1 in 9    = 11.11%
 1 in 8    = 12.50%
 1 in 7    = 14.29%
 1 in 6    = 16.67%
 1 in 5    = 20.00%
 2 in 9    = 22.22%
 1 in 4    = 25.00%
 2 in 7    = 28.57%
 3 in 10   = 30.00%
 1 in 3    = 33.33%
 3 in 8    = 37.50%
 2 in 5    = 40.00%
 3 in 7    = 42.86%
 4 in 9    = 44.44%
 1 in 2    = 50.00%
 5 in 9    = 55.56%
 4 in 7    = 57.14%
 3 in 5    = 60.00%
 5 in 8    = 62.50%
 2 in 3    = 66.67%
 7 in 10   = 70.00%
 5 in 7    = 71.43%
 3 in 4    = 75.00%
 7 in 9    = 77.78%
 4 in 5    = 80.00%
 5 in 6    = 83.33%
 6 in 7    = 85.71%
 7 in 8    = 87.50%
 8 in 9    = 88.89%
 9 in 10   = 90.00%
 11 in 12  = 91.67%
 14 in 15  = 93.33%
 19 in 20  = 95.00%
 29 in 30  = 96.67%
 39 in 40  = 97.50%
 49 in 50  = 98.00%
 59 in 60  = 98.33%
 69 in 70  = 98.57%
 79 in 80  = 98.75%
 89 in 90  = 98.89%
 99 in 100 = 99.00%
>99 in 100

```

**Other stipulations:**

* Numeric input can be in the range of **0.1 to 99.9** or in the range of **0.001 to 0.999**, whichever is more convenient. You must handle at least 3 significant digits.
* You must output a *ratio* ("3 in 4"), not the equivalent *fraction* ("3/4").
* If there are two ratios equally close to the input, your program can return either one. 7.5% could return "1 in 12" or "1 in 15".
* Leading/trailing white space and/or new lines are fine

**Examples**:

```
Input  :   Output
 0.5   :  <1 in 100
 1.0   :   1 in 100
 1.5   :   1 in 70
 7.5   :   1 in 15  or  1 in 12 (either is acceptable)
 9.2   :   1 in 10
13.1   :   1 in 8
29.2   :   2 in 7
29.3   :   3 in 10
52.7   :   1 in 2
52.8   :   5 in 9
72.0   :   5 in 7
73.9   :   3 in 4
88.8   :   8 in 9
90.8   :   9 in 10
94.2   :  19 in 20
98.7   :  79 in 80
98.9   :  89 in 90
99.0   :  99 in 100
99.1   : >99 in 100

```

This is a challenge, shortest code in each language wins.

(Similar to, but not duplicate of: Convert a decimal to a fraction, Closest fraction, Approximate floating point number with n-digit precision)

# Answer
> 6 votes
# T-SQL, 385 bytes

```
SELECT TOP 1IIF(i>.99,'>',IIF(i<.01,'<',''))+n+' in '+d
FROM t,(SELECT ISNULL(PARSENAME(value,2),'1')n,PARSENAME(value,1)d FROM
STRING_SPLIT('100,90,80,70,60,50,40,30,20,15,12,10,9,8,7,6,5,2.9,4,2.7,3.10,3,3.8,2.5,3.7,4.9,2,5.9,4.7,3.5,5.8,2.3,7.10,5.7,3.4,7.9,4.5,5.6,6.7,7.8,8.9,9.10,11.12,14.15,19.20,29.30,39.40,49.50,59.60,69.70,79.80,89.90,99.100',','))m
ORDER BY ABS(i-ABS(n)/d)

```

Input is via pre-existing table **t** with numeric field **i**, per our IO standards.

That input table is joined with an in-memory table parsed from a string via `STRING_SPLIT` (which separates rows) and `PARSENAME` (which separates numerator and denominator via `.`).

The table is sorted by distance from the input value **i**, and returns the top row, formatted appropriately.

# Answer
> 5 votes
# JavaScript (ES7), ~~164~~ ~~159~~ 144 bytes

Expects an input ratio in \\$\]0,1\[\\$.

```
r=>(g=m=>--n+11?g((q=n>1?n*10:n+10-~'13'[n],d=((p=r<.1?1:r>.9?q-1:n<0&&r*q+.5|0)/q-r)**2)>m?m:(o=p+' in '+q,d)):r<.01?'<'+o:r>.99?'>'+o:o)(n=11)

```

Try it online!

### How?

We try all possible ratios \\$p/q\\$. For each of them, we compute:

$$d=(p/q-r)^2$$

We update the best score \\$m\\$ (the lower, the better) each time \\$d\\$ is lower than or equal to \\$m\\$.

We go from the highest value of \\$q\\$ to the lowest one, so that a smaller denominator is preferred in case of a tie.

### Commented

```
r => (g = m =>               // r = input; g() = recursive function, taking m = best score
  --n + 11 ?                 // decrement n; if n is still greater than or equal to -10:
    g(                       //   do a recursive call to g():
      ( q =                  //     compute q = denominator:
        n > 1 ?              //       if n is greater than 1:
          n * 10             //         q = n * 10 (20, 30, ..., 100)
        :                    //       else:
          n + 10 - ~'13'[n], //         q = 12 if n = 0, 15 if n = 1, n + 11 if n < 0
        d = ((               //     compute d = (p / q - r)²:
          p =                //       compute p = numerator:
          r < .1 ?           //         if r is less than 0.01:
            1                //           p = 1
          :                  //         else:
            r > .9 ?         //           if r is greater than 0.90:
              q - 1          //             p = q - 1
            :                //           else:
              n < 0 &&       //             if n is negative (i.e. q is in [1,10]):
              r * q + .5 | 0 //               p = round(r * q)
                             //             otherwise: p = 0 (which will be ignored)
          ) / q - r          //       compute p / q - r
        ) ** 2               //       and square the result (cheaper than absolute value)
      ) > m ?                //     if d is greater than m:
        m                    //       leave m unchanged
      : (                    //     else:
        o = p + ' in ' + q,  //       update the output string o
        d                    //       and update m to d
    ))                       //   end of recursive call
  :                          // else (all possible ratios have been tried out):
    r < .01 ? '<' + o :      //   if r is less than 0.01, prefix with '<'
    r > .99 ? '>' + o :      //   if r is greater than 0.99, prefix with '>'
    o                        //   otherwise, just return o
)(n = 11)                    // initial call to g() with m = n = 11

```

# Answer
> 5 votes
# Charcoal, 84 bytes

```
ＮθＦ¹¹«Ｆ⊖ι⊞υ⟦⊕κι⟧≔⎇⊖ι∨×χι¹²¦¹⁵ιＦ²⊞υ⟦∨κ⊖ιι⟧»≔Ｅυ↔⁻θ∕§ι⁰§ι¹η≔⌕η⌊ηη×<‹θ·⁰¹×>›θ·⁹⁹⪫§υη in

```

Try it online! Link is to verbose version of code. Takes input as a decimal rather than a percentage. Explanation:

```
Ｎθ

```

Input the fraction.

```
Ｆ¹¹«

```

Run from \\$ n = 0 \\$ to \\$ n = 10 \\$.

```
Ｆ⊖ι⊞υ⟦⊕κι⟧

```

Generate ratios for \\$ \frac 1 n \\$ to \\$ \frac {n - 1} n \\$.

```
≔⎇⊖ι∨×χι¹²¦¹⁵ι

```

Get the \\$ n^{th} \\$ element of the list \\$ 12, 15, 20 ... 100 \\$ into \\$ n \\$.

```
Ｆ²⊞υ⟦∨κ⊖ιι⟧»

```

Generate ratios for \\$ \frac {n - 1} n \\$ and \\$ \frac 1 n \\$.

```
≔Ｅυ↔⁻θ∕§ι⁰§ι¹η

```

Calculate the decimal values of all the ratios and take the absolute difference with the original input.

```
≔⌕η⌊ηη

```

Find the index of the least absolute difference. In case of a tie (e.g. \\$ \frac 1 2 \\$ and \\$ \frac 2 4 \\$), take the ratio generated first.

```
×<‹θ·⁰¹

```

Print a `<` if the input is less than \\$ 0.01 \\$.

```
×>›θ·⁹⁹

```

Print a `>` if the input is greater than \\$ 0.99 \\$.

```
⪫§υη in

```

Join the numerator and denominator of the appropriate ratio with `in` and print.

# Answer
> 4 votes
# Python 2, ~~261~~ ~~278~~ ~~261~~ ~~237~~ 177 bytes

```
lambda n:' <>'[(n<.01)-(n>.99)]+'%d in %d'%min([(a,b)for b in[[12,15]+r(10,110,10),r(1,11)][.1<n<.9]for a in r([1,b-1][n>.9],[b,2][n<.1])],key=lambda(a,b):abs(1.*a/b-n))
r=range

```

Try it online!

# Answer
> 4 votes
# Jelly, 58 bytes

```
⁵R×⁵;12,15µ’,1,€)Ẏ;⁵Œc¤ð÷/ạ¥ÞḢj“ in ”
”<”>“”>.99$?<.01$?;Ç

```

Try it online!

-16 bytes thanks to Arnauld (can just prepend the `<` and `>` instead of rewriting the whole phrase)
-6 bytes and bug-fixes thanks to Jonathan Allan

# Answer
> 3 votes
# Jelly,  ~~53~~  52 bytes

```
_.01,.99Ṡµ<0ịØ<ḣE⁵Ż×⁵+12,5Ṡ,’Ɗż€$Ẏ;⁵Œc¤÷/ạ¥Þ³Ḣj“ in

```

A full program which prints the result.

**Try it online!**

Or see the test-suite

Note that the test-suite is altered to make the code a monadic link by:

1. using the register keep a track of the current "program input", with `³` to `®`; and
2. closing the list of characters code for " in ", with `“ in`  to `“ in ”`

### How?

Starts with code that forces any necessary printing of the `<` or `>` sign and then code which constructs all the numerator-denominator pairs (with some redundant not simplified form versions, all after their simplified form) and prints the minimally different division-evaluated entry using a stable sort joined with  `in` .

```
_.01,.99Ṡµ<0ịØ<ḣE⁵Ż×⁵+12,5Ṡ,’Ɗż€$Ẏ;⁵Œc¤÷/ạ¥Þ³Ḣj“ in  - Main Link: number in [0,1], n
 .01,.99                                             - literal pair = [0.01, 0.99]
_                                                    - subtract -> [n - 0.01, n - 0.99]
        Ṡ                                            - sign (vectorises) (-1 if <0; 1 if >0; else 0)
         µ                                           - start a new monadic link
                                                     -   call that X
          <0                                         - less than zero? (vectorises)
             Ø<                                      - literal list of characters = "<>"
            ị                                        - index into (vectorises) ("<<" if n < 0.01; ">>" if n >= 0.99; else "><")
                E                                    - all (of X) equal? (1 if ((n < 0.01) OR (n > 0.99)) else 0
               ḣ                                     - head to index ("<" if n < 0.01; ">" if n > 0.99; else "")
                                                     -   (the following nilad forces a print of that)
                 ⁵                                   - literal 10
                  Ż                                  - zero-range -> [0,1,2,3,4,5,6,7,8,9,10]
                   ×⁵                                - multiply by 10 -> [0,10,20,30,40,50,60,70,80,90,100]
                      12,5                           - literal pair = [12,5]
                     +                               - add -> [12,15,20,30,40,50,60,70,80,90,100]
                                $                    - last two links as a monad
                             Ɗ                       -   last three links as a monad
                          Ṡ                          -     sign -> [1,1,1,1,1,1,1,1,1,1,1]
                            ’                        -     decrement -> [11,14,19,29,39,49,59,69,79,89,99]
                           ,                         -     pair -> [[1,1,1,1,1,1,1,1,1,1,1],[11,14,19,29,39,49,59,69,79,89,99]]
                              ż€                     -   zip with for €ach -> [[[1,12],[1,15],[1,20],[1,30],[1,40],[1,50],[1,60],[1,70],[1,80],[1,90],[1,100]],[[11,12],[14,15],[19,20],[29,30],[39,40],[49,50],[59,60],[69,70],[79,80],[89,90],[99,100]]]
                                 Ẏ                   - tighten -> [[1,12],[1,15],[1,20],[1,30],[1,40],[1,50],[1,60],[1,70],[1,80],[1,90],[1,100],[11,12],[14,15],[19,20],[29,30],[39,40],[49,50],[59,60],[69,70],[79,80],[89,90],[99,100]]
                                      ¤              - nilad followed by link(s) as a nilad:
                                   ⁵                 -   literal 10
                                    Œc               -   unordered pairs -> [[1,2],[1,3],[1,4],[1,5],[1,6],[1,7],[1,8],[1,9],[1,10],[2,3],[2,4],[2,5],[2,6],[2,7],[2,8],[2,9],[2,10],[3,4],[3,5],[3,6],[3,7],[3,8],[3,9],[3,10],[4,5],[4,6],[4,7],[4,8],[4,9],[4,10],[5,6],[5,7],[5,8],[5,9],[5,10],[6,7],[6,8],[6,9],[6,10],[7,8],[7,9],[7,10],[8,9],[8,10],[9,10]]
                                  ;                  - concatenate -> [[1,12],[1,15],[1,20],[1,30],[1,40],[1,50],[1,60],[1,70],[1,80],[1,90],[1,100],[11,12],[14,15],[19,20],[29,30],[39,40],[49,50],[59,60],[69,70],[79,80],[89,90],[99,100],[1,2],[1,3],[1,4],[1,5],[1,6],[1,7],[1,8],[1,9],[1,10],[2,3],[2,4],[2,5],[2,6],[2,7],[2,8],[2,9],[2,10],[3,4],[3,5],[3,6],[3,7],[3,8],[3,9],[3,10],[4,5],[4,6],[4,7],[4,8],[4,9],[4,10],[5,6],[5,7],[5,8],[5,9],[5,10],[6,7],[6,8],[6,9],[6,10],[7,8],[7,9],[7,10],[8,9],[8,10],[9,10]]
                                           Þ         - sort by:
                                          ¥          -   last two links as a dyad:
                                                     -       ...(with right argument of
                                            ³        -           the program input, n)
                                        /            -     reduce by:
                                       ÷             -       division
                                         ạ           -     absolute difference
                                             Ḣ       - head
                                               “ in  - literal list of characters " in "
                                              ;      - concatenate
                                                     - implicit print

```

# Answer
> 3 votes
# Clean, ~~224~~ ~~198~~ 197 bytes

```
import StdEnv,Data.List,Text
t=toReal
$p=if(p<1.0)"<"if(p>99.0)">"""+snd(minimum[(abs(p-t n*1E2/t d),n<+" in "<+d)\\i<-[10,12,15:[20,30..100]],(n,d)<-[(1,i),(i-1,i):diag2[1..10][1..10]]|gcd n d<2])

```

Try it online!

Explained:

```
t = toReal                              // give `toReal` a shorter name
$ p
 = if(p < 1.0)                          // if the percentage is less than 1%
  "<"                                   // prepend "<"
 if(p > 99.0)                           // if the percentage is > 99%
  ">"                                   // prepend ">"
  ""                                    // otherwise prepend nothing
 + snd (                                // to the second element of
  minimum [                             // the smallest item in a list composed of
   (                                    // pairs of
    abs (                               // the absolute value of
     p -                                // the difference between the percentage
     t n*1E2 / t d                      // and the ratio
    )
   ,                                    // associated with
    n <+ " in " <+ d                    // the string representation of the ratio
   )                                    // in the form of a tuple
   \\ i <- [10, 12, 15: [20, 30..100]]  // for every special denominator `i`
   , (n, d) <- [(1, i), (i - 1, i): diag2 [1..10] [1..10]]
                                        // for every ratio `n` : `d`
   | gcd n d < 2                        // where `n` / `d` cannot be further simplified
  ]
 )

```

# Answer
> 2 votes
# Perl 6, 118 bytes

```
{'<'x(.01>$_)~'>'x($_>.99)~(|(1..9 X ^11),|map({|(1,$_-1 X$_)},12,15,|(^11 X*10))).min({abs $_-[/] @^a}).join(' in ')}

```

Try it online!

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


# Question
Title: Find the \$\left(n^2\right)^\text{th }n\$-gonal number
Given a non-negative integer, \\$n\\$, yield the \\$(n^2)^\text{th } n\\$-gonal number.

### Further Detail:

The \\$x\\$-gonal numbers, or *polygonal numbers*, are also known as the *two-dimensional figurate numbers*.

Many people will be familiar with the triangular numbers, these are the \\$3\\$-gonal numbers:

$$F(3,n)=\sum\_{i=1}^{n}(i)=\frac{n(n+1)}{2}$$

The triangular numbers are OEIS A000217:

```
0, 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 66, 78, 91, 105, 120, 136, 153, 171, 190, ...

```

Probably even more will be familiar with the square numbers, these are the \\$4\\$-gonal numbers:

$$F(4,n)=\sum\_{i=1}^{n}(2i-1)=n^{2}$$

The square numbers are OEIS A000290:

```
0, 1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196, 225, 256, 289, 324, 361, ...

```

In general the \\$k^\text{th }x\\$-gonal number is the number of pebbles required to iteratively build up an \\$x\\$-sided polygon by adding pebbles to \\$x-2\\$ of the sides, here are a few formulae:

\begin{align} F(x,k)&=\sum\_{i=1}^{k}\left(1+\sum\_{j=2}^{i}(x-2)\right) \\ &=\frac{k^2(x-2)-k(x-4)}{2} \\ &=\frac{k(k-1)}{2}(x-2)+k\\ &=(x-3)\sum\_{i=1}^{k-1}(i)+\sum\_{i=1}^{k}(i)\\ &=(x-2)(k-1)+1+F(x,k-1) \end{align}

I'm sure there are plenty more.
Note that the last one is recursive but that \\$F(x,0)=0\\$.

### The challenge

...is to golf code for \\$G(n)=F(n,n^2)\\$ for non-negative \\$n\\$.
i.e. Given a non-negative integer, \\$n\\$, yield the \\$(n^2)^\text{th } n\\$-gonal number.
This is not (currently) in the OEIS:

```
0, 1, 4, 45, 256, 925, 2556, 5929, 12160, 22761, 39700, 65461, 103104, 156325, 229516, 327825, 457216, 624529, 837540, 1105021, ...

```

### Notes

You may yield a list of these numbers up to and including the required one if preferred.
For example, given an input of `5` you may yield either:

* the integer `925`, or
* the list `[0, 1, 4, 45, 256, 925]`
* ...**but not `[0, 1, 4, 45, 256]` or `[1, 4, 45, 256, 925]`**

Results may also be results of floating point calculation and may deviate as such, so long as infinite precision floating point arithmetic would yield correct results.

---

Win by creating the shortest code in bytes in a language. The overall winner will be the shortest across all languages, but please don't let golfing languages dissuade you from entering in your favourite language - the primary goals are to challenge yourself and have fun!

# Answer
# Wolfram Language (Mathematica), 19 bytes

```
#(4-#-2#^2+#^3)#/2&

```

Try it online!

Just a golfy version of the second formula.

## With `PolygonalNumber` built-in, 23 bytes

```
PolygonalNumber[#,#^2]&

```

Try it online!

As expected, the Mathematica built-in is longer than the golfed version.
> 6 votes

# Answer
# Neim, 2 bytes

```
ᛦℙ

```

Try it online!

¯\\\_(ツ)\_/¯ First Neim answer, right tool for the job. By the way, the advice I give on my *About me* page still holds for my own posts: Don't upvote trivial solutions, please.
> 5 votes

# Answer
# Jelly, 8 bytes

```
²Ḷ×_2$‘S

```

Try it online!

In short, it generates the range \\$\[0,1,2,\dots,(n-1)^2\]\\$, multiplies every integer in that range with \\$n-2\\$, increments each of them (to avoid adding \\$n^2\\$ at the end, saving 1 byte), then sums the resulting list.
> 3 votes

# Answer
# 05AB1E, 4 bytes

```
nsÅU

```

Try it online!
> 2 votes

# Answer
# Pyth, ~~14~~ 9 bytes

```
smh*d-Q2*

```

Try it online!
> 2 votes

# Answer
# Python 2, ~~31~~ 30 bytes

```
lambda k:(k*k*(k-2)-k+4)*k*k/2

```

Try it online!

---

Saved:

* -1 byte, thanks to joH1
> 2 votes

# Answer
# JavaScript (ES7), 26 bytes

```
n=>n**4*(n-2)-n*n*(n-4)>>1

```

Try it online!

---

# Recursive (ES6), 33 bytes

A quick attempt from mobile. Not really optimized for \\$(n,n^2)\\$.

```
x=>(g=k=>k&&(x-2)*--k-~g(k))(x*x)

```

Try it online!
> 1 votes

# Answer
# cQuents, 20 bytes

```
$0:$$+$$/2($$-1)($-2

```

Try it online!

## Explanation

```
$0                      Zero indexing
  :                     Mode: sequence (output nth term)
                        Each term equals:
   $$+                    index * index +
      $$/2                index * index / 2 *
          ($$-1)($-2      (index * index - 1) * (index - 2
                    )    ) implicit

```
> 1 votes

# Answer
# Charcoal, 17 bytes

```
Ｉ⊘↨⟦¹±²±¹¦⁴¦⁰¦⁰⟧Ｎ

```

Try it online! Link is to verbose version of code. Explanation: Uses the second formula expanded into the polynomial \\$ \frac{1}{2} ( x^5 - 2x^4 - x^3 + 4x^2 ) \\$ which is calculated by treating it as an arbitrary base conversion before halving and casting to string for implicit output.
> 1 votes

# Answer
# Physica, 25 bytes

```
->n:(n^4-n^2)/2*(n-2)+n^2

```

Try it online!

---

```
->n:n^2*(4-n-2*n^2+n^3)/2

```

Try it online!

---

```
->n:n^5/2-n^4-n^3/2+2*n*n

```

Try it online! | **Try all of them at once as a test suite!**
> 1 votes

# Answer
# Jelly, ~~11~~ 10 bytes

```
²µ½_2×’H×+

```

Try it online!

Uses the formula \\$F(x,k)=\frac{k(k-1)}{2}(x-2)+k\\$ as given in the challenge.
> 1 votes

# Answer
# Clean, 38 bytes

```
import StdEnv
$x=x^2*(x^3/2-x^2-x/2+2)

```

Try it online!
> 1 votes

# Answer
# APL (Dyalog), 17 bytes

```
×⍨×2+×⍨-⍨.5×*∘3-⊢

```

Try it online!
> 1 votes

# Answer
# MATL, 9 bytes

```
U:qG2-*Qs

```

Try it online!

This uses Mr. Xcoder's Jelly approach.
> 1 votes

# Answer
# K (oK), 23 bytes

```
{((x-2)*k%2%k-1)+k:x*x}

```

Try it online!

Prefix function; implementation of the second formula: \\$\frac{k(k-1)}{2}(x-2)+k\\$

### How:

```
{((x-2)*k%2%k-1)+k:x*x} # Main function, argument x.
                 k:x*x  # def k = n²
 ((x-2)*k%2%k-1)+       # calculate k + (((k/2)/(k-1))*(x-2))

```
> 1 votes

# Answer
# Haskell (31 bytes)

```
g k=(k*k*k*k*(k-2)-k*k*(k-4))/2

```
> 1 votes

# Answer
# Haskell, 27 bytes

```
f k=(k^4*(k-2)-k^2*(k-4))/2

```

Try it online!

My first attempt at golfing in Haskell, basically same as almost any answer :

Nothing worth explaining here.
> 1 votes

# Answer
# C (gcc), ~~60~~ ~~36~~ 34 bytes

-24 bytes thanks to Jonathan Allan

-2 bytes by factorizing again an `n*n` expression.

```
g(n){return(n*n*(n-2)-n+4)*n*n/2;}

```

Try it online!

Factored version of the second formula, uses a single function.

Entry point is function `g(n)`, value is returned as integer.
> 1 votes

# Answer
# Ruby, 25 bytes

```
->n{(4-n+(n-2)*n*=n)*n/2}

```

Try it online!
> 1 votes

# Answer
# Pyt, 4 bytes

```
Đ²⇹ᑭ

```

Try it online!

### Explanation:

```
        Implicit input
Đ       Duplicate
 ²      Square
  ⇹     Swap top two elements on the stack
   ᑭ    Get the (n^2)th n-gonal number
        Implicit output

```
> 0 votes

---
Tags: code-golf, math, sequence, integer
---


# Question
Title: Sorting out redundant text from screen scraper application
You are writing a screen scraper application monitoring a text-only chat window. Text is added at the bottom of the window.

The application takes screenshot of the chat window. If a change has occurred since last screenshot (new\_screenshot != old\_screenshot), the screenshot is saved.

After X time, all images are merged to one image, where the oldest image is on the top. This large image is send to a server for OCR, and a string of text is returned.

**Challenge:** Sort out redundant text.

Example: Chat window is 5 lines high and is initially empty. The solution must work with empty and not-empty initial chat window. More than one line can be added at each screenshot.

**Input to algorithm:**

1 Lorem ipsum dolor sit amet,
1 Lorem ipsum dolor sit amet,
2 consectetur adipiscing elit
1 Lorem ipsum dolor sit amet,
2 consectetur adipiscing elit
3 Mauris porttitor enim sed tincidunt interdum.
1 Lorem ipsum dolor sit amet,
2 consectetur adipiscing elit
3 Mauris porttitor enim sed tincidunt interdum.
4 Morbi elementum erat nec nulla auctor, eget porta odio aliquet.
1 Lorem ipsum dolor sit amet,
2 consectetur adipiscing elit
3 Mauris porttitor enim sed tincidunt interdum.
4 Morbi elementum erat nec nulla auctor, eget porta odio aliquet.
5 Nam aliquet velit vel elementum tristique.
2 consectetur adipiscing elit
3 Mauris porttitor enim sed tincidunt interdum.
4 Morbi elementum erat nec nulla auctor, eget porta odio aliquet.
5 Nam aliquet velit vel elementum tristique.
6 Donec ac tincidunt urna.
3 Mauris porttitor enim sed tincidunt interdum.
4 Morbi elementum erat nec nulla auctor, eget porta odio aliquet.
5 Nam aliquet velit vel elementum tristique.
6 Donec ac tincidunt urna.
7 Proin pretium, metus non porttitor lobortis, tortor sem rhoncus urna
4 Morbi elementum erat nec nulla auctor, eget porta odio aliquet.
5 Nam aliquet velit vel elementum tristique.
6 Donec ac tincidunt urna.
7 Proin pretium, metus non porttitor lobortis, tortor sem rhoncus urna
8 quis finibus leo lorem sed lacus.
5 Nam aliquet velit vel elementum tristique.
6 Donec ac tincidunt urna.
7 Proin pretium, metus non porttitor lobortis, tortor sem rhoncus urna
8 quis finibus leo lorem sed lacus.
1 Lorem ipsum dolor sit amet,

**Expected result:**

1 Lorem ipsum dolor sit amet,
2 consectetur adipiscing elit
3 Mauris porttitor enim sed tincidunt interdum.
4 Morbi elementum erat nec nulla auctor, eget porta odio aliquet.
5 Nam aliquet velit vel elementum tristique.
6 Donec ac tincidunt urna.
7 Proin pretium, metus non porttitor lobortis, tortor sem rhoncus urna
8 quis finibus leo lorem sed lacus.
1 Lorem ipsum dolor sit amet,

**UPDATE:** I forgot an important detail in the original challenge: The same line can come multiple times, **but never two times in a row** so just deduplicating is not enough.

# Answer
# Japt `-R`, 11 bytes

This passes the test case but the spec still isn't clear enough

```
·ò¨ mÌò¦ mg

```

Try it
> 0 votes

---
Tags: string, sequence, text-processing
---