title: Read my free-form date

text:
# Question
Title: Read my free-form date
Given a date written in any (must handle all in the same program) of the following formats, parse it into a valid `yyyy/mm/dd date`.

```
17th May 2012
March 14th, 2016
20 February 2014
September 14, 2017
Sunday, June 8, 2015

```

**Rules**

* Dates will sometimes be invalid, ie. incorrect day for the month or number of months in a year, you must handle both cases. Either by erroring out or returning a consistent falsey value, you choose. (They will however stick to the template formats above)
* Padding for days and months less than 10 must be used to create a two digit output.
* Month names will always be the full name, not shortened to their three character counterparts.
* You can assume the year will always be within the 0000-9999 range.
* Negative numbers need not be handled.
* You can create a full program or function so output can be in any format, printed to console or returned from a function.
* Input will always be a string, output must always be a string, if it makes it shorter to take it as a single argument in an array eg. `["17th May 2012"]` you may do so and output can be the same `["2012/05/17"]`
* You can assume spelling in input will be correct.

**BONUS:** cos who here doesnt like a challenge ;)

If you can manage to also allow the input formats of `The Fourteenth of March, 2016` or `March the Fourteenth, 2016` you may take an extra **20 bytes** off your code with any final byte counts less than 1 resulting in 1.

Here are the full written numbers for each of the days to avoid any confusion on spelling.

```
First, Second, Third, Fourth, Fifth, Sixth, Seventh, Eighth, Nineth, Tenth, Eleventh, Twelfth, Thirteenth, Fourteenth, Fifteenth, Sixteenth, Seventeenth, Eighteenth, Nineteenth, Twentieth, Twenty First, Twenty Second, Twenty Third, Twenty Fourth, Twenty Fifth, Twenty Sixth, Twenty Seventh, Twenty Eighth, Twenty Nineth, Thirtieth, Thirty First

```

**Test Cases**

```
INPUT                           | Output
17th May 2012                   | 2012/05/17
March 14th, 2016                | 2016/03/14
20 February 2014                | 2014/02/20
September 14, 2017              | 2017/09/14
Sunday, June 8, 2015            | 2015/06/08
1st January 1918                | 1918/01/01

The Fourteenth of March, 2016   | 2016/03/14
March the Fourteenth, 2016      | 2016/03/14
November the Seventeenth, 2019  | 2019/11/17
The Thirtieth of April, 2016    | 2016/04/30

30 February 2014                | Invalid
September 99, 2017              | Invalid
Sunday, June8, 2015             | Invalid

The Thirty First of April, 2016 | Invalid

```

# Answer
# Rails, ~~41~~, ~~37~~ 35 bytes

```
->x{x.to_date.strftime('%Y/%m/%d')}

```

I don't know of an online interpreter for Rails, but here is a screenshot demonstrating this proc
> 4 votes

# Answer
# PowerShell, ~~91~~ ~~89~~ ~~91~~ 56 bytes

```
date("$args"-replace'th|rd|st|(\b.*)day|,')-f yyyy/MM/dd

```

Try it online!

Takes input as a string. Uses a `-replace` to get rid of junk, then uses the built-in `Get-Date` command with the `-f`ormat flag to specify the required `yyyy/MM/dd` format. That string is left on the pipeline and output is implicit.

*Saved two bytes thanks to Mr Xcoder. Saved a huge chunk thanks to TessellatingHeckler's regex golfing.*
> 8 votes

# Answer
# PHP, ~~73~~ 164+1 bytes

```
for(preg_match("#(\d+)[^\d]+(\d+)#",$d=$argn,$r);$m++<12;)strpos(_.$d,date(F,strtotime($r[2].-$m)))&&printf(checkdate($m,$r[1],$r[2])?"$r[2]/%02d/%02d":E,$m,$r[1]);

```

Run as pipe with `-nR` or try it online.

The date check was really expensive: I had to disassemble the date before using a builtin, then try and error on the month name.
> 4 votes

# Answer
# Python 3 \+ parsedatetime library, ~~152~~ ~~139~~ ~~155~~ 153 bytes

Saved 13 bytes thanks to Jonathan Allan

Added 16 bytes to handle dates with invalid length days

Saved 2 bytes by removing lambda assignment

```
lambda s:re.search(f'(^| ){str(h(s)[0].tm_mday)[:2]}[^\d]',s)and time.strftime('%Y/%m/%d',h(s)[0])
import parsedatetime as p,time,re
h=p.Calendar().parse

```

Try it online!

Does not support bonus dates
> 3 votes

# Answer
# Python 2, 193 bytes

```
lambda s:time.strftime('%Y/%m/%d',time.strptime(re.sub(r'^(\w+) (\d+)',r'\2 \1',re.sub('^ ','',re.sub('(th|rd|st)|(Sun|Mon|Tues|Wednes|Thurs|Fri|Satur)day|,','',s))),'%d %B %Y'))
import re,time

```

Try it online!

;-; pls halp
> 1 votes

# Answer
# Java (OpenJDK 8), 190 + 26 = 216 bytes

```
import java.time.format.*;

s->DateTimeFormatter.ofPattern("uuuu/MM/dd").format(DateTimeFormatter.ofPattern("[EEEE, ][d ]MMMM [d, ]uuuu").withResolverStyle(ResolverStyle.STRICT).parse(s.replaceAll("(\\d)[a-z].","$1")))

```

Try it online!

**Important note:** it was *shorter* to also validate the day of week instead of ditching it, so that validation is included!

I haven't tried with `SimpleDateFormat` beyond the obvious cases which all accepted dates like 30 February. So I had to ditch it and I used Java 8's `DateTimeFormatter`.

## Explanation

```
"[EEEE, ][d ]MMMM [d, ]uuuu"

```

This format means :

* optional day-of-week followed by comma and space `[EEEE, ]` (happens in `Sunday, ...`),
* followed by optional day with space `[d ]`,
* followed by month in full letters `MMMM` and space,
* followed by optional day with comma and space `[d, ]`,
* followed by year of era `uuuu` to let the parser know we're in Gregorian era.

Code:

```
import java.time.format.*;                                     // Required for DateTimeFormatter, *and* ResolverStyle

s->DateTimeFormatter.ofPattern("uuuu/MM/dd")                   // Output format
  .format(
    DateTimeFormatter.ofPattern("[EEEE, ][d ]MMMM [d, ]uuuu")  // Input format
      .withResolverStyle(ResolverStyle.STRICT)                 // Invalidates xxxx-02-30 instead of transforming it into xxxx-02-28
      .parse(
        s.replaceAll("(\\d)[a-z].","$1")                       // remove st, nd, rd, th
       )
    )

```

# Credits

* 2 bytes in the regex thanks to Neil.
> 1 votes

# Answer
## JavaScript (ES6), ~~124~~ 122 bytes

```
f=
s=>(d=new Date(s.replace(/.[dht]\b/,'')+' +0')).getDate()==s.match(/\d\d?/)&&d.toISOString().replace(/-(..)(T.*)?/g,'/$1')
```

```
<input oninput=o.textContent=f(this.value)><pre id=o>
```
> 1 votes

---
Tags: code-golf, string, date
---


title: Pick up your phone! It's vibrating!

text:
# Question
Title: Pick up your phone! It's vibrating!
You just recently got a new phone, but you don't quite like the way it vibrates, you've decided you want to create your own vibration patterns. So, you've written a program where you used the keywords `long`, `short` and `pause` to make your phone vibrate according to these keywords.

## Task

Create a small program that accepts a string of `long`, `short`, and `pause` and outputs another string representing the phonetic sound of a phone vibrating; `Rrrr - Rr`

`long` sounds are `Rrrr`
`short` sounds are `Rr`
(Casing matters)
`pause` is a dash `-`
all sounds are delimited by dash with surrounding spaces `' - '`

## Test Cases

input: `long long short long short`
output: `Rrrr - Rrrr - Rr - Rrrr - Rr`

input: `long long long short short short`
output: `Rrrr - Rrrr - Rrrr - Rr - Rr - Rr`

input: `short short short pause short short short`
output: `Rr - Rr - Rr - - - Rr - Rr - Rr`

input: `long short short long long pause short short`
output: `Rrrr - Rr - Rr - Rrrr - Rrrr - - - Rr - Rr`

This is a question so answers will be scored in bytes, with the fewest bytes winning.

# Answer
# Pyke, ~~22~~ 20 bytes

```
cFh.o6.&\R*\-|l4)J" -

```

Try it here!

```
c                      -  split(input, " ")
 Fh.o6.&\R*\-|l4)      -  for i in ^:
  h                    -        ^[0]
   .o                  -       ord(^)
     6.&               -      ^ & 6
        \R*            -     ^
           \-|         -    ^ or "-"
              l4       -   ^.title()
                 J" -  - " - ".join(^)

```

The crux of this answer is the transformation of `["long", "short", "pause"]` into `[4, 2, 0]`. It gets the code point of the first letter of each word and `AND`s it with 6. By lucky coincidence it transforms to the values we're looking for. (I searched through quite a few other longer solutions before finding this one). Once that's done, we can further transform that list of ints into `["RRRR", "RR", ""]` by multiplying our int by `"R"` which then turns into `["RRRR", "RR", "-"]` and finally title casing it to get `["Rrrr", "Rr", "-"]`. We then join the resulting list by `" - "`
> 12 votes

# Answer
# JavaScript, ~~70~~ 63 bytes

*2 bytes saved thanks to Luke*

```
a=>a.replace(/./g,a=>[['Rr','rr','-',' - ']['onp '.search(a)]])

```

Try it online!
> 14 votes

# Answer
# Haskell, ~~71~~ ~~66~~ 59 bytes

```
g 'o'="Rr"
g 'n'="rr"
g 'p'="-"
g ' '=" - "
g _=""
f=(g=<<)

```

Try it online!

Oh right, `=<<` is concatMap.

Takes advantage of the fact that `"long"` and `"short"` both have the letter `o`.
> 11 votes

# Answer
# 05AB1E, ~~33~~ ~~27~~ ~~25~~ 21 bytes

```
#εÇн6&'m×™'-)éθ}… - ý

```

Try it online!

**Explanation**

```
#                       # split input on spaces
 ε             }        # apply to each
  Çн                    # get the character code of the head
    6&                  # AND with 6
      'm×               # repeat "m" this many times
         ™              # title case
          '-)           # wrap in a list with "-"
             éθ         # get the longest string
                … - ý   # join to string using " - " as separator

```

Saved 3 bytes using the `AND 6` trick from *muddyfish's* pyke answer
> 7 votes

# Answer
# JavaScript (ES6), ~~65~~ 59 bytes

```
s=>s.split` `.map(x=>x<'m'?'Rrrr':x<'q'?'-':'Rr').join` - `

```

```
let f =

s=>s.split` `.map(x=>x<'m'?'Rrrr':x<'q'?'-':'Rr').join` - `

console.log(f("long long short long short")); // => Rrrr - Rrrr - Rr - Rrrr - Rr
console.log(f("long long long short short short")); // => Rrrr - Rrrr - Rrrr - Rr - Rr - Rr
console.log(f("short short short pause short short short")); // => Rr - Rr - Rr - - - Rr - Rr - Rr
console.log(f("long short short long long pause short short")); // => Rrrr - Rr - Rr - Rrrr - Rrrr - - - Rr - Rr
```
> 7 votes

# Answer
# Python 2, ~~76~~ ~~69~~ 64 bytes

```
lambda s:' - '.join('Rrrr'[:ord(b[0])&6]or'-'for b in s.split())

```

Try it online!

**Alternates:**

### Python 2, ~~76~~ 69 bytes

```
lambda s:' - '.join(['Rrrr','-','Rr'][ord(b[1])%3]for b in s.split())

```

Try it online!

### Python 2, 69 bytes

```
lambda s:' - '.join('-Rrrr'['o'in b:8-ord(b[1])%9]for b in s.split())

```

Try it online!
> 6 votes

# Answer
# Retina, ~~31~~ 29 bytes

*1 byte saved thanks to Dom Hastings<br>1 byte saved thanks to Neil*

```
[^lhp ]

l
hrr
h
Rr
p
-

 -

```

Try it online!

This is different approach than @DomHastings's answer.
> 5 votes

# Answer
# Mathematica, 81 bytes

```
StringReplace[#,{"long"->"Bzzz -","short"->"Bz -","pause"->"- -"}]~StringDrop~-2&

```

Try it online!
> 5 votes

# Answer
# Röda, ~~73~~ ~~57~~ ~~47~~ ~~46~~ ~~40~~ 44 bytes

```
f&a{a~=*`s\w+|l;Rr;ong;rr;p\w+;-; ; - `/";"}

```

Try it online!

+4 bytes due to rule change (must use `Rrrr` instead of any 4 letter variant).

Previous code:

```
{[[split()|["Bzzz"]if[_="long"]else["Bz"]if[_1="short"]else["-"]]&" - "]}

```
> 4 votes

# Answer
## Perl 5, 39 bytes

**37 bytes code + 2 for `-pa`.**

```
$_=join" - ",map/p/?"-":Bz.zz x/l/,@F

```

Try it online!
> 4 votes

# Answer
# , 77 bytes

```
cat(c('Rrrr','Rr','-')[match(scan(,''),c('long','short','pause'))],sep=' - ')

```

Takes input through STDIN, checks whether the input matches `long`, `short` or `pause` and swaps the matches for `Rrrr`, `Rr` or `-` respectively.

This is then printed with `-` padded with spaces as separator, matching the desired output.
> 4 votes

# Answer
# C (gcc), ~~93~~ ~~77~~ 76 bytes

*-2 bytes thanks to Scepheo!*
*-1 byte thanks to Cyoce!*

Takes a NULL terminated \**char or equivalent as an input.

```
f(char**a){for(;*a;*++a&&printf(" - "))printf(**a&6?**a&1?"Rr":"Rrrr":"-");}

```

Try it online!

Explanations:

```
f(char**a){
  // While the string at the current position is not NULL
  for(;*a;
    // Advances the pointer to the next string
    // Then if the current string is not NULL, prints a delimiter
    *++a&&printf(" - ")
  )
    /*
      If the 1st char of the string is not a 'p'
        If the 1st char is not a 'l'
          Prints "Rr"
        Else
          Prints "Rrrr"
      Else:
        Prints "-"
     */
    printf(**a&6?**a&1?"Rr":"Rrrr":"-");
}

```
> 4 votes

# Answer
# , 72 bytes

Takes input from stdin, prints to stdout.

```
cat(sapply(scan(,''),switch,long="vvvv",short="vv",pause="-"),sep=" - ")

```

Try it online!
> 3 votes

# Answer
## Batch, 88 bytes

```
@set/ps=
@set s=%s: = - %
@set s=%s:long=Rrrr%
@set s=%s:short=Rr%
@echo %s:pause=-%

```

Takes input on STDIN. Unfortunately loop overhead costs 26 bytes so this is just boring replacements.
> 3 votes

# Answer
# Retina, 31 bytes

```
short|l
Bz
ong
zz
pause
-

 -

```

-1 byte thanks to @fergusq!

Try it online!
> 2 votes

# Answer
# PHP, 113 bytes

```
<?$s=[];for($i=1;$i<$argc;$i++){$c=$argv[$i][0];$s[]=($c<'m')?'Rrrr':(($c<'q')?'-':'Rr');}echo implode(' - ',$s);

```

Try it online!

First attempt at code golf, so probably a lot of optimisations available!
> 2 votes

# Answer
# Vim (52 bytes)

`:s/long/Rrrr/ge|s/short/Rr/ge|s/pause/-/ge|s/ / - /g`*enter*

Can probably be made shorter...
> 2 votes

# Answer
# Excel, 100 bytes

```
=REPLACE(SUBSTITUTE(SUBSTITUTE(SUBSTITUTE(A1,"long","- Bzzz"),"short","- Bz"),"pause","- -"),1,2,"")

```

Per examples, Input is `SPACE` separated string, as is output.

Question itself does not mention a `SPACE` requirement, allowing for a slightly shorter **97 byte** solution:

```
=REPLACE(SUBSTITUTE(SUBSTITUTE(SUBSTITUTE(A1,"long","-Bzzz"),"short","-Bz"),"pause","--"),1,1,"")

```
> 1 votes

# Answer
# , 32 bytes

```
Í /ò
çl/CRrrr
ço/CRr
çp/-
HòJa-

```

Try it online!
> 1 votes

# Answer
## AutoIt, 145 bytes

```
EXECUTE(STRINGREPLACE('MSGBOX(0,0,STRINGSTRIPWS(====INPUTBOX(0,0),"PAUSE",""),"LONG","Rrrr"),"SHORT","Rr")," "," - "),4))',"=","STRINGREPLACE("))

```

(AutoIt is really bad choice for code golf, tried my best to make it small as possible)
> 1 votes

# Answer
# Sed, 50 bytes

Takes input from `stdin`, prints to `stdout`

```
s/l\w*/Rrrr -/g
s/s\w*/Rr -/g
s/p\w*/- -/g
s/ -$//

```

Edit - saved 2 bytes

# Sed, 40 bytes

Copying idea from Nitrodon's answer

```
s/[srtaue]//g
y/lhongp/RRrrr-/
s/ / - /g

```

Edit: saved another 2 bytes
> 1 votes

# Answer
# Alice, 37 bytes

```
/ lRnrhR
\""orgrp-""!yi'."?-e"ySNo?@/

```

Try it online!

### Explanation

This program makes the following substitutions:

* `l`, `h``R`
* `o`, `n`, `g``r`
* `p``-`
* Space → Space
* Everything else → Nothing

```
"longhp "!i.?eyN?"RrrrR- "y' " - "So@

"longhp "    Push this string
!            Immediately move to tape
i            Take input string
.            Duplicate
?ey          Remove all instances of the characters "longhp " from copy
N            Remove the remaining characters from the original, leaving only "longhp "
?"RrrrR- "y  Replace the characters in "longhp " with the corresponding characters in "RrrrR- "
' " - "S     Replace all spaces with " - "
o            Output
@            Terminate

```
> 1 votes

# Answer
# Python 2, 69 bytes

```
lambda s:" - ".join((ord(i[0])&6)*"R"or"-"for i in s.split()).title()

```

Try it online!

Port of my Pyke answer
> 0 votes

# Answer
# SOGL V0.12, 28 bytes

```
θ{K;⁄5κ« r*; p=?X┌}}¹" - ”∑ū

```

Try it Here!

fun fact: if it was allowed to delimit with  `-`  or  `-`  it'd be a byte shorter
> 0 votes

# Answer
# Paradoc (v0.2.10), 21 bytes (CP-1252)

```
Wμ‹6&'r\°"-":Ãu}« rTc

```

Try it online!

Takes a string on the stack and results in a string on the stack. Prepend `i` to turn into a full program that reads from STDIN.

Uses `&6` like the Pyke answer and everybody else, but joins the tokens together slightly differently, by adding a `"-"` token after each noise, deleting the last one, and then joining these tokens by spaces. Seems to save a byte over joining by `" - "`.

Explanation:

```
W                     .. Break into words
 μ             }      .. Map over this block:
  ‹                   .. Take the first character
   6&                 .. Binary AND with 6, to get 4, 2, or 0
     'r               .. Character "r"
       \              .. Swap top two of stack
        °             .. Replicate, to get "rrrr", "rr", or ""
         "-"          .. Push string "-"
            :         .. Duplicate on stack
             Ã        .. Compute the max...
              u       .. ... underneath the top of the stack (so, of the
                      .. second and third elements on the stack, i.e. the
                      .. string of "r"s and "-")
                      .. The mappped block ends here; we now have
                      .. something like ["rrrr", "-", "-", "-", "rr", "-"]
                «     .. Take all but the last
                  r   .. Join with spaces (this built-in's name is two
                      .. characters, the first of which is a space)
                   Tc .. Title-case

```

v0.2.11 will support shaving two more bytes by replacing  with `x` and `"-"` with `'-`.
> 0 votes

# Answer
# Ruby, 78 bytes

```
p ARGV[0].chars.map{|c|{p:'-',o:'Rr',g:'rr',' '.to_sym=>' - '}[c.to_sym]}.join

```

The only important parts of the input are `p`, `o`, `g`, and space... ignore the rest.

* `short` becomes `o`
* `long` becomes `og`
* `pause` becomes `p`

Try it online!
> 0 votes

# Answer
# Ruby, 67 bytes

```
p ARGV[0].split(' ').map{|w|w<'m'?'Rrrr':w<'q'?'-':'Rr'}.join ' - '

```

**This is Johan Karlsson's JavaScript solution ported to Ruby.** If you like this answer, you should upvote Johan's answer.

The key idea is to compare the word strings `'short'`, etc. to a single character in order to distinguish between words.

```
| Word  | < 'm' | < 'q' | Output |
|-------|-------|-------|--------|
| short | false | false | 'Rr'   |
| long  | true  | N/A   | 'Rrrr' |
| pause | false | true  | '-'    |

```

Or, in alphabetical order:

* long
* m
* pause
* q
* short

Try it online!
> 0 votes

# Answer
# Python 3, 66 bytes

```
' - '.join(['Rrrr','-','Rr'][ord(s[1])%3]for s in input().split())

```

Try it online!
> 0 votes

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


title: Count forth and back then double up

text:
# Question
Title: Count forth and back then double up
**Let's count...**

Count up to 2 and back to 1
Count up to 4 and back to 1
Count up to 6 and back to 1
... ok you got it...

put all these together and you'll get the following sequence

```
 {1,2,1,2,3,4,3,2,1,2,3,4,5,6,5,4,3,2,1,2,3,4,5,6,7,8,7,6,5,4,3,2,1,2,3...}

```

**Challenge**
Given an integer `n>0`for 1-indexed (or `n>=0` for 0-indexed), output the nth term of this sequence

**Test cases**

```
Input->Output

1->1
68->6
668->20
6667->63
10000->84

```

**Rules**

your program must be able to compute solutions up to n=10000 in under a minute

This is , so the shortest code in bytes wins!

# Answer
> 16 votes
# JavaScript (ES7),  ~~59 ... 44~~  43 bytes

*Saved 1 byte thanks to Titus*

Expected input: 1-indexed.

```
n=>(n-=(r=(~-n/2)**.5|0)*r*2)<++r*2?n:r*4-n

```

Initially inspired by a formula for A004738, which is a similar sequence. But I ended up rewriting it entirely.

### Test cases

```
let f=

n=>(n-=(r=(~-n/2)**.5|0)*r*2)<++r*2?n:r*4-n

console.log(f(1))     // -> 1
console.log(f(68))    // -> 6
console.log(f(668))   // -> 20
console.log(f(6667))  // -> 63
console.log(f(10000)) // -> 84
```

### How?

The sequence can be arranged as a triangle, with the left part in ascending order and the right part in descending order.

Below are the first 4 rows, containing the first 32 terms:

```
            1 | 2
        1 2 3 | 4 3 2
    1 2 3 4 5 | 6 5 4 3 2
1 2 3 4 5 6 7 | 8 7 6 5 4 3 2

```

Now, let's introduce some variables:

```
 row  | range   | ascending part              | descending part
 r    | x to y  | 1, 2, ..., i                | 4(r+1)-(i+1), 4(r+1)-(i+2), ...
------+---------+-----------------------------+-----------------------------------------
  0   |  1 -  2 |                           1 | 4-2
  1   |  3 -  8 |                   1   2   3 | 8-4  8-5  8-6
  2   |  9 - 18 |           1   2   3   4   5 | 12-6 12-7 12-8  12-9  12-10
  3   | 19 - 32 |   1   2   3   4   5   6   7 | 16-8 16-9 16-10 16-11 16-12 16-13 16-14

```

We start with 2 elements at the top and add 4 elements on each new row. Therefore, the number of elements on the 0-indexed row ***r*** can be expressed as:

```
a(r) = 4r + 2

```

The 1-indexed starting position ***x*** of the row ***r*** is given by the sum of all preceding terms in this arithmetic series plus one, which leads to:

```
x(r) = r * (2 + a(r - 1)) / 2 + 1
     = r * (2 + 4(r - 1) + 2) / 2 + 1
     = 2r² + 1

```

Reciprocally, given a 1-indexed position ***n*** in the sequence, the corresponding row can be found with:

```
r(n) = floor(sqrt((n - 1) / 2))

```

or as JS code:

```
r = (~-n / 2) ** 0.5 | 0

```

Once we know ***r(n)***, we subtract the starting position ***x(r)*** minus one from ***n***:

```
n -= r * r * 2

```

We compare ***n*** with ***a(r) / 2 + 1 = 2r + 2*** to figure out whether we are in the ascending part or in the descending part:

```
n < ++r * 2 ?

```

If this expression is true, we return ***n***. Otherwise, we return ***4(r + 1) - n***. But since ***r*** was already incremented in the last statement, this is simplified as:

```
n : r * 4 - n

```

# Answer
> 7 votes
# Haskell, 37 bytes

```
(!!)$do k<-[1,3..];[1..k]++[k+1,k..2]

```

Try it online!

Zero-indexed. Generates the list and indexes into it. Thanks to Ørjan Johansen for saving 2 bytes!

---

# Haskell, 38 bytes

```
(!!)[min(k-r)r|k<-[0,4..],r<-[1..k-2]]

```

Try it online!

Zero-indexed. Generates the list and indexes into it.

---

# Haskell, 39 bytes

```
n%k|n<k=1+min(k-n)n|j<-k+4=(n-k)%j
(%2)

```

Try it online!

Zero-indexed. A recursive method.

# Answer
> 6 votes
# Python, 46 bytes

```
f=lambda n,k=2:-~min(n,k-n)*(n<k)or f(n-k,k+4)

```

Try it online!

Zero indexed.

# Answer
> 5 votes
## Husk, 8 bytes

```
!…ṁoe1DN

```

1-indexed. Try it online!

## Explanation

```
!…ṁoe1DN  Implicit input (an integer).
       N  Positive integers: [1,2,3,4,...
  ṁo      Map and concatenate
      D   double: [2,4,6,8,...
    e1    then pair with 1: [1,2,1,4,1,6,1,8,...
 …        Fill gaps with ranges: [1,2,1,2,3,4,3,2,1,2,3,4,5,6,...
!         Index with input.

```

# Answer
> 3 votes
# Perl 6, 29 bytes

```
{({|(1...$+=2...2)}...*)[$_]}

```

Try it online

0-based

## Expanded:

```
{  # bare block lambda with implicit parameter ｢$_｣

  (
    # generate an outer sequence

    {           # bare block lambda

      |(        # flatten into outer sequence

        # generate an inner sequence

        1       # start at 1

        ...     # go (upward) towards:

        $       # an anonymous state variable (new one for each outer sequence)
          += 2  # increment by 2

        ...     # go (downward) towards:

        2       # stop at 2 (1 will come from the next inner sequence)

      )
    }

    ...         # keep generating the outer sequence until:
    *           # never stop

  )[ $_ ]       # index into outer sequence
}

```

The inner sequence `1...$+=2...2` produces

```
(1, 2).Seq
(1, 2, 3, 4, 3, 2).Seq
(1, 2, 3, 4, 5, 6, 5, 4, 3, 2).Seq
(1, 2, 3, 4, 5, 6, 7, 8, 7, 6, 5, 4, 3, 2).Seq
(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 9, 8, 7, 6, 5, 4, 3, 2).Seq
...

```

To get it to be 1-based, add `0,` before the second `{`, or add `-1` after `$_`

# Answer
> 3 votes
# R, 64 bytes

```
function(n)unlist(sapply(seq(2,n,2),function(x)c(2:x-1,x:2)))[n]

```

Function that takes an argument `n`. It creates a vector `2:n` with increments of 2. For each of these, the vector `1:(x-1)` and `x:2` is created. This in total will be longer than `n`. We `unlist` it, to get a vector and take the `n`-th entry.

# Answer
> 2 votes
# Jelly, ~~10~~, 9 bytes

```
ḤŒḄṖµ€Fị@

```

Try it online!

Also 1 indexed, and finishes pretty fast.

One byte saved thanks to @ErikTheOutgolfer!

Explanation:

Hypothetically, let's say the input (`a`) is 3.

```
    µ€      # (Implicit) On each number in range(a):
            #
Ḥ           # Double
            #   [2, 4, 6]
            #
 ŒḄ         # Convert to a range, and Bounce
            #   [[1, 2, 1], [1, 2, 3, 4, 3, 2, 1], [1, 2, 3, 4, 5, 6, 5, 4, 3, 2, 1]]
            #
   Ṗ        # Pop
            #   [[1, 2], [1, 2, 3, 4, 3, 2], [1, 2, 3, 4, 5, 6, 5, 4, 3, 2]]
            #
     F      # Flatten
            #   [1, 2, 1, 2, 3, 4, 3, 2, 1, 2, 3, 4, 5, 6, 5, 4, 3, 2]
            #
      ị@    # Grab the item[a]
            #   1
            #

```

# Answer
> 2 votes
# Python 2, 56 bytes

```
def f(x):n=int((x/2)**.5);print 2*n-abs(2*n*n+2*n+1-x)+2

```

Try it online!

This is 0-indexed.

*-1 byte thanks to @JustinMariner*

**How this Works**

We note that the 1-indexed `n`-th group (`1, 2, ... 2n ..., 2, 1`) occurs from elements numbered 0-indexed `2(n-1)^2` to `2n^2`.

To find the element at index `x`, we can find the group number `n` that `x` is in. From that, we calculate the distance from the center of the group that `x` is. (This distance is `abs(2*n**2+2*n+2-x)`).

However, since the elements *decrease* further away from the center of a group, we subtract the distance from the maximum value of the group.

# Answer
> 2 votes
# 05AB1E, 8 bytes

### Code:

```
ÅÈ€1Ÿ¦¹è

```

Uses the **05AB1E** encoding. Try it online!

### Explanation:

```
ÅÈ           # Get all even numbers until input (0, 2, ..., input)
  €1         # Insert 1 after each element
    Ÿ        # Inclusive range (e.g. [1, 4, 1] -> [1, 2, 3, 4, 3, 2, 1])
     ¦       # Remove the first element
      ¹è     # Retrieve the element at the input index

```

# Answer
> 2 votes
# JavaScript, 39 bytes

```
f=(n,t=2)=>n>t?f(n-t,t+4):n>t/2?t-n+2:n

```

# Answer
> 1 votes
# MATL, 15 bytes

```
li:"@EZv4L)]vG)

```

1-based.

**Try it online!**

This times out for the largest test cases in TIO, but finishes in time on my desktop computer (compiler running on MATLAB R2017a). To display elapsed time, add `Z`` at the end of the code.

```
>> matl 'li:"@EZv4L)]vG)Z`'
> 10000
84
15.8235379852476

```

### Explanation

The code generates many more terms than necessary. Specifically, it computes `n` "pieces" of the sequence, where each piece is a count up and back to 1.

```
l       % Push 1
i       % Push input, n
:       % Range [1 2 ...n]
"       % For each k in that range
  @E    %   Push 2*k
  Zv    %   Symmetric range: [1 2 ... 2*k-1 2*k 2*k-1 ... 2 1]
  4L)   %   Remove last entry: [1 2 ... 2*k-1 2*k 2*k-1 ... 2]
]       % End
v       % Concatenate all stack contents into a column vector
G)      % Get n-th entry. Implicitly display

```

# Answer
> 1 votes
# Husk, ~~12~~ 10 bytes

```
!ṁ§¤+hḣṫİ0

```

Try it online!

1-indexed, works quite fast

### Explanation

```
!ṁ§¤+hḣṫİ0
 ṁ      İ0    Map the following function over the even numbers and concatenate the results together
  §   ḣṫ      Get the ranges 1-n and n-1, then...
   ¤+h         remove the last element from both of them and concatenate them together
!             Return the element of the resulting list at the given index

```

# Answer
> 1 votes
# Mathematica, 90 bytes

```
Flatten[{1}~Join~Table[Join[Rest[p=Range@i],Reverse@Most@p],{i,2,Round[2Sqrt@#],2}]][[#]]&

```

Try it online!

# Answer
> 1 votes
# Ruby, ~~78~~ 75 bytes

*Saved 1 byte thanks to Step Hen*

*Saved 1 byte thanks to Mr. Xcoder*

```
->n{a=0;b=2;c=1;n.times{if a==b then c=0;b+=2;end;c=1if a<2;a+=c<1?-1:1};a}

```

Try it online!

Hopefully I can get some tips for pulling the bytecount down more. I tried to take a simple approach.

# Answer
> 1 votes
# Retina, 62 bytes

```
.+
$*
^((^.|\2..)*)\1.
6$*1$2$2;1
(?=.+;(.+))\1(.+).*;\2.*
$.2

```

Try it online! Link includes test cases. Input is 1-indexed. The first stage is just decimal to unary conversion. The second stage finds the highest square number `s` strictly less than half of `n`; `$1` is , while `$2` is `2s-1`. It calculates two values, first the number of numbers in the current up/down run, which is `4(s+1) = 4s+4 = 2$2+6`, and secondly the position within that run, which is `n-2s² = n-(2$1+1)+1 = n-$&+1`, which just requires a `1` to make up for the `1` used to enforce the strict inequality. The final stage then counts from that position to both the start and end of the run and takes the lower result and converts it to decimal.

# Answer
> 1 votes
# Mathematica, 67 bytes

```
(t=z=1;While[(x=3-4t+2t^2)<#,t++;z=x];If[#-z>2t-2,4t-5+z-#,#-z+1])&

```

Try it online!

# Answer
> 1 votes
# Perl 5, 43 + 1 (-p) = 44 bytes

```
$_=($n=2*int sqrt$_/2)+2-abs$n/2*$n+$n+1-$_

```

Try it online!

I was working on a formula to calculate the n-th element directly. Then I saw that @fireflame241 had done that work, and I golfed it into Perl.

~~\# Perl 5, 50 + 1 (-n) = 51 bytes~~

```
push@r,1..++$",reverse 2..++$"while@r<$_;say$r[$_]

```

Try it online!

Results are 0 indexed.

# Answer
> 1 votes
# Haskell, ~~115~~ 81 bytes

```
y%x=snd(span(<x)$scanl(+)y[y+1,y+3..])!!0
g 1=1
g x|1%x>2%x=1+g(x-1)|1>0=g(x-1)-1

```

Try it online!

There is some magic going on here. Could probably be shorter if I used a normal approach though.

## Explanation

First we define `%`. `%` is a function that takes two variables `x`, and `y`. It constructs a list `scanl(+)y[y+1,y+3..]` and finds the first element of that list greater than `x`. `scanl(+)` just performs iterative sums, to get the triangular numbers we would do `scanl(+)0[1..]`, to get the square numbers we would do `scanl(+)0[1,3..]`. The two lists in particular we will be constructing are `scanl(+)2[3,5..]` and `scanl(+)1[2,4..]` these are the inflection points of the pattern.

Now we define the main function `g` which takes an `x`. If `x` is one we return `1` because that's the first value. Otherwise we check the next two inflection points, if the down inflection is larger `1%x>2x` we return the successor of `g$x-1` otherwise we return the predecessor of `g$x-1`.

## Ok but why does that work?

First of all "Whats with the way we find vertices?". Its important to note the distance between consecutive vertices of the same type. You will notice that the differences are growing by 2 each time. This makes sense because the triangles bases become wider by 2 each time. We can make a list constant difference using a list literal like so `[2,4..]` and we use `scanl(+)` to to turn these lists into our vertex lists, based on the location of the first vertex and the first difference.

So now that we have a way of finding upward and downward vertices we can use that information to get the values. We say that the first value is `1` otherwise we have to take either the successor or the predecessor. If the next vertex is a upward one we want to take the predecessor, otherwise we take the successor.

# Haskell, ~~56~~ ~~51~~ 46 bytes

Here's my better solution with less math and fewer bytes.

```
d x|e<-[1..x-1]=e++map(x+1-)e
(([1..]>>=d)!!0)

```

Try it online!

# Answer
> 1 votes
# Pyke, 14 bytes

```
SF}SDtO_+)sQt@

```

Try it here!

```
S              -    range(1, input)
 F}SDtO_+)     -   for i in ^:
  }            -      ^ * 2
   S           -     range(1, ^)
        +      -    ^ + v
     tO_       -     ^[1:-1:-1]
          s    -  sum(^)
           Qt@ - ^[input-1]

```

# Answer
> 1 votes
# C# (.NET Core), 120 bytes

Explanation: pretty simple, the first nested loop climbs up to our max, the second climbs back down to 2. The repeat for each multiple of 2.

```
x=>{var a=0;for(int i=2,j=0;j<x;i+=2){for(var b=1;b<=i&j<x;b++,j++){a=b;}for(var c=i-1;c>1&j<x;c--,j++){a=c;}}return a;}

```

Try it online!

# Answer
> 1 votes
# Java (OpenJDK 8), 53 bytes

```
n->{int i=2;for(;n>i;i+=4)n-=i;return n>i/2?i-n+2:n;}

```

Try it online!

*-2 bytes thanks to Nevay.*

1-indexed.

**TL;DR** We split the sequence into convenient chunks, find the chunk `n` is in, then find the `nth` position in the chunk.

Here, we can split the sequence like `[[1,2],[1,2,3,4,3,2],[1,2,3,4,5,6,5,4,3,2],...]`, which gives us chunk sizes of `4i-2`. Starting with `i=2`, we subtract `i` from `n`, essentially moving upwards a chunk at a time. Once we satisfy `n<=i`, we know `n` is now the position of the correct value in the current chunk.

We then get the value by comparing `n` to `i`, the size of the chunk. The midpoint of each chunk is equal to `i/2+1`; if `n` is less than this, we simply return `n`. If `n` is greater, we return `i-n+2`.

# Example

```
n = 16, i = 2

Is n > i? Yes, n = n - 2 = 14, i = i + 4 = 6
Is n > i? Yes, n = n - 6 = 8, i = i + 4 = 10
Is n > i? No, stop looping.
10 / 2 + 1 = 6
Is n > 6? Yes, return i - n + 2 = 8 - 6 + 2 = 4

```

# Answer
> 1 votes
# Python 2, 5! bytes (120 bytes :P)

```
r=range
a=[]
for i in r(2,998,2):
	for j in r(1,i+1): a.append(j)
	for j in r(i-1,1,-1): a.append(j)
print a[input()-1]

```

Try it online!

Straightforward, makes the list and then takes input'th element

# Answer
> 0 votes
# Python 3, 184 156 bytes

```
l,n,r=list,next,range
h=lambda x:l(r(1,x))+l(r(x-2,1,-1))
def g():
	x=3
	while True:yield from h(x);x+=2
def f(i):
	x=g()
	for _ in r(i-1):n(x)
	return n(x)

```

Try it online!

golfed with Python generator for "lazy" evaluation

# Answer
> 0 votes
# QBIC, 47 bytes

```
g=q{p=p+1~p=:|_Xg\g=g+q~g=1or g>=r|r=r+1┘q=q*-1

```

## Explanation

```
g=q         var g is the current value of the sequence; set to 1 at the start
{           DO infinitely
p=p+1       raise the step counter (var p)
~p=:|_Xg    IF p equals the input term a (read from cmd line) THEN QUIT, printing g
\           ELSE
g=g+q       raise (or decrement) g by q (q is 1 at the start of QBIC)
~g=1        IF g is at the lower bound of a subsequence
    or g>=r OR g is at the upper bound (r start as 2 in QBIC)
|r=r+1      THEN increment r (this happens once on lower bound, and once on upper,
            total of 2 raise per subsequence)
┘q=q*-1     and switch q from 1 to -1

```

# Answer
> 0 votes
# Pyth,  ~~19~~  18 bytes

```
-yhKs@/Q2 2a*yKhKt

```

**Try it here!**

# Answer
> 0 votes
# Röda, 54 bytes

```
f n{seq 1,n|{|i|seq 1,2*i;seq 2*i-1,2}_|head n+2|tail}

```

Try it online!

Call with: `try f(n)`

This function returns quickly the answer, but *after* that does some unnecessary calculations and eventually runs out of memory.

As the function does return the actual answer shortly after it is called (clearly under a minute), I think this answer is valid.

(In Röda functions can return values before they exit due to parallelism.)

# Answer
> 0 votes
# C# (.NET Core),99 95 86 bytes

```
n=>{int i=1,t=2,d=0;for(;n>1;){i+=1-2*d;if(i==t){d++;t+=2;}if(i==1)d--;n--;}return i;}

```

Try it online!

Lambda function that takes and returns an integer. Single loop that handles counting up and down.

# Answer
> 0 votes
# PHP, 65+1 bytes

```
for($x=$d=$z=1;--$argn;)$d=($x+=$d)>1?$x>$z?-1:$d:!!$z+=2;echo$x;

```

Run as pipe with `-R` or try it online (or uncomment one of the other versions).

A port of tsh´s recursive JavaScript takes 66 bytes:

```
function f($n,$t=2){return$t<2*$n?$t<$n?f($n-$t,$t+4):$t-$n+2:$n;}

```

A port of Arnauld´s solution takes 62+1:

```
$n=$argn;echo($n-=($r=(~-$n/2)**.5|0)*$r*2)<++$r*2?$n:$r*4-$n;

```

A golfed port of Xanderhall´s Java has the shortest code so far (55+1 bytes):

```
for($n=$argn;$n+2>$i+=4;)$n-=$i-2;echo$n*2>$i?$i-$n:$n;

```

---
Tags: code-golf, sequence, counting, restricted-time
---


title: Make this dice game fair

text:
# Question
Title: Make this dice game fair
This challenge is adapted from the British Informatics Olympiad.

---

## Dice game

Two players are playing a dice game where they each roll a pair of dice, and the highest sum wins. The pairs of dice have the same number of sides, but do not have to have the same values on each side. Therefore, the game is fair if for both pairs of dice all possible sums can be made with equal probability.

For example, if Player 1 has the following dice:

```
{1,2,3,4,5,6} {1,2,3,4,5,6}

```

Then they can produce the following sums:

```
    1  2  3  4  5  6
 +------------------
1|  2  3  4  5  6  7
2|  3  4  5  6  7  8
3|  4  5  6  7  8  9
4|  5  6  7  8  9  10
5|  6  7  8  9  10 11
6|  7  8  9  10 11 12

```

If Player 2 has:

```
{1,2,2,3,3,4} {1,3,4,5,6,8}

```

They can produce:

```
    1  2  2  3  3  4
 +------------------
1|  2  3  3  4  4  5
3|  4  5  5  6  6  7
4|  5  6  6  7  7  8
5|  6  7  7  8  8  9
6|  7  8  8  9  9  10
8|  9  10 10 11 11 12

```

This game is fair as the minimum for both is 2, the maximum is 12, and each sum occurs the same number of times, e.g 7 can be made 6 ways with each pair.

---

## Challenge

Write a program/function that takes two dice as input, and optionally an integer representing the number of sides each dice contain, and prints/returns a different pair of dice that could be used to play a fair game with the two input dice, or any falsey value if there is no solution different from the input.

---

# Specifications

* The number of sides on both dice must be the same, and equal to the number of sides on the input pair of dice. This number will always be an integer greater than or equal to 1.
* The two dice returned can be the same, but the pair must not be the same as the input pair.
* Different order pairs are not different; {1,2,3} {4,5,6} is the same as {4,5,6} {1,2,3}.
* Your program does not need to produce a result quickly, as long as it will eventually produce correct output.
* The values on the input pair of dice dice will always be integers between 1 and 9 inclusive, but the values returned can be any integer ≥1.
* If there is more than one possible solution, only one needs to be returned.
* Input/Output can be in any reasonable format.

## Test Cases

```
6
1 2 2 3 3 4
8 6 5 4 3 1

1 2 3 4 5 6
1 2 3 4 5 6

```

---

```
4
1 1 1 1
1 4 5 8

1 1 4 4
1 1 5 5

```

---

```
3
1 3 5
2 4 6

False

```

---

```
8
1 2 3 4 5 6 7 8
1 2 3 4 5 6 7 8

Any of the following:

1 2 2 3 3 4 4 5       |    1 2 2 3 5 6 6 7   |    1 2 3 3 4 4 5 6
1 3 5 5 7 7 9 11      |    1 3 3 5 5 7 7 9   |    1 2 5 5 6 6 9 10

```

# Answer
# Jelly, 34 bytes

```
+þµFṢ
ç©ṀRœċL}Œċµç/⁼®µÐf
,Ṣ€,Ṛ$ḟ@ç

```

Returns a list of all possible pairs of dice up to ordering of dice and faces\* (excluding any that are the same dice as the input pair).

**Try it online!**

This is a brute-forcer, and is not efficient (too slow to even run the 6-face test case at TIO).

```
+þµFṢ - Link 1, sorted sums: dieA, dieB
 þ    - outer product with
+     -     addition (make a table of the sums, a list of lists)
  µ   - monadic chain separation
   F  - flatten into one list
    Ṣ - sort

ç©ṀRœċL}Œċµç/⁼®µÐf - Link 2, all possible fair dice pairs (including input): dieA, dieB
ç                  - call the last link (1) as a dyad
 ©                 - save the result to the register for later use too
  Ṁ                - maximum (the largest sum)
   R               - range [1,2,...,maxSum]
       }           - use right argument (dice B) to turn the monad into a dyad:
      L            -     length
    œċ             - all combinations with replacement (i.e. all dice with faces between 1 and maxSum inclusive [overkill, but golfier than less])
        Œċ         - all pairs of these dice
          µ        - monadic chain separation
               µÐf - filter keep:
            /      -     reduce with:
           ç       -         last link (1) as a dyad (the sorted sums of the current pair)
              ®    -     retrieve register value (the sorted sums of the input pair)
             ⁼     -     equal?

,Ṣ€,Ṛ$ḟ@ç - Main link: dieA, dieB
,         - pair - [dieA, dieB]
 Ṣ€       - sort €ach - [dieASorted, dieBSorted]
     $    - last two links as a monad:
    Ṛ     -     reverse - [dieBSorted, dieASorted]
   ,      -     pair - [[dieASorted, dieBSorted], [dieBSorted, dieASorted]]
        ç - call the last link (2) as a dyad (with dieA, dieB)
       @  - reversed @rguments:
      ḟ   -     filter out - removes any results that are equivalent to the input pair.

```

* i.e. if `[[1,1,4,4],[1,1,5,5]]` is a possibility (like in one of the examples) there wont be a `[[1,1,5,5],[1,1,4,4]` or `[[1,4,1,4],[1,1,5,5]]`, etc.
> 2 votes

# Answer
# C++14, 130 bytes

As unnamed lambda assuming `M` to be like `std::vector<std::vector<int>>`. Fair is `0`, anything else is unfair.

```
#include<map>
[](auto&M){auto g=[](auto&v){std::map<int,int>m;for(int x:v)for(int y:v)m[x+y]++;return m;};return g(M[0])-g(M[1]);}

```

Ungolfed:

```
#include<map>

auto f=
[](auto&M){
 auto g=[](auto&v){
  std::map<int,int>m;
  for(int x:v)
   for(int y:v)
    m[x+y]++;
  return m;
 };
 return g(M[0])==g(M[1]);
}
;

```
> 1 votes

# Answer
# Python, 228 bytes

```
from itertools import*;s,C=lambda x,y:sorted(sum([[i+j for j in y]for i in x],[])),combinations_with_replacement;f=lambda k,l,m:([[*a]for a in C([*C([*range(1,s(l,m)[-1])],k)],2)if(s(l,m)==s(*a))*~-([*a]in[[l,m],[m,l]])]+[0])[0]

```

This was from a long time ago; I could probably golf this a bit better now.
> 1 votes

---
Tags: code-golf
---


title: Naturally linear Diophantine equations

text:
# Question
Title: Naturally linear Diophantine equations
A linear Diophantine equation in two variables is an equation of the form **ax + by = c**, where **a**, **b** and **c** are constant integers and **x** and **y** are integer variables.

For many naturally occurring Diophantine equations, **x** and **y** represent quantities that cannot be negative.

### Task

Write a program or function that accepts the coefficients **a**, **b** and **c** as input and returns an arbitrary pair of **natural numbers** (0, 1, 2, …) **x** and **y** that verify the equation **ax + by = c**, if such a pair exists.

### Additional rules

* You can choose any format for input and output that involves only the desired integers and, optionally, array/list/matrix/tuple/vector notation of your language, as long as you don't embed any code in the input.
* You may assume that the coefficients **a** and **b** are both non-zero.
* Your code must work for any triplet of integers between **-260** and **260**; it must finish in under a minute on my machine (Intel i7-3770, 16 GiB RAM).
* You may not use any built-ins that solve Diophantine equations and thus trivialize this task, such as Mathematica's `FindInstance` or `FrobeniusSolve`.
* Your code may behave however you want if no solution can be found, as long as it complies with the time limit and its output cannot be confused with a valid solution.
* Standard rules apply.

### Examples

1. The examples below illustrate valid I/O for the equation **2x + 3y = 11**, which has exactly two valid solutions ( **(x,y) = (4,1)** and **(x,y) = (1,3)** ).

```
Input:  2 3 11
Output: [4 1]

Input:  (11 (2,3))
Output: [3],(1)

```
2. The only valid solution of **2x + 3y = 2** is the pair **(x,y) = (1,0)**.
3. The examples below illustrate valid I/O for the equation **2x + 3y = 1**, which has **no valid solutions**.

```
Input:  (2 3 1)
Output: []

Input:  1 2 3
Output: -1

Input:  [[2], [3], [1]]
Output: (2, -1)

```
4. For **(a, b, c) = (1152921504606846883, -576460752303423433, 1)**, all correct solutions **(x,y)** satisfy that **(x,y) = (135637824071393749 - bn, 271275648142787502 + an)** for some non-negative integer **n**.

# Answer
> 6 votes
# Pyth, 92 bytes

```
I!%vzhK%2u?sm,ed-hd*ed/F<G2cG2@G1G+~Q,hQ_eQj9 2)J*L/vzhKtKeoSNm-VJ/RhK_*LdQsm+LdtM3/V*LhK_JQ

```

It's quite a monster.

Try it online: Demonstration. The input format is `c\n[a,b]` and the output format is `[x,y]`.

In the case that no integer solution exists, I'll print nothing, and in the case that no natural integer solution exists, I'll simply print a random integer solution.

### Explanation (Rough Overview)

1. At first I'll find an integer solution to the equation `ax + by = gcd(a,b)` by using the Extended Euclidean algorithm.
2. Then I'll modify the solution (my multiplying `a` and `b` with `c/gcd(a,b)`) to get an integer solution of `ax + by = c`. This works, if `c/gcd(a,b)` is an integer. Otherwise there doesn't exist a solution.
3. All the other integer solutions have the form `a(x+n*b/d) + b(y-n*a/d) = c` with `d = gcd(a,b)` for integer `n`. Using the two inequalities `x+n*b/d >= 0` and `y-n*a/d >= 0` I can determine 6 possible values for `n`. I'll try all 6 of them and print the solution with the highest lowest coefficient.

### Explanation (Detailed)

The first step is to find an integer solution to the equation `ax' + by' = gcd(a,b)`. This can be done by using the extended Euclidean algorithm. You can get an idea on how it works at Wikipedia. The only difference is, that instead of using 3 columns (`r_i s_i t_i`) I'll use 6 columns (`r_i-1 r_i s_i-1 s_i t_i-1 t_i`). This way I don't have to keep the last two rows in memory, only the last one.

```
K%2u?sm,ed-hd*ed/F<G2cG2@G1G+~Q,hQ_eQj9 2)   implicit: Q = [a,b] (from input)
                                     j9 2    convert 9 to base 2: [1,0,0,1]
                            + Q              add to Q => [a,b,1,0,0,1]
                                             this is the initial row
   u                                     )   start with G = ^ and update G repeatedly
                                             by the following expression, until
                                             the value of G doesn't change anymore
    ?                   @G1                    if G[1] != 0:
                     cG2                         split G into parts of 2
      m                                          map the parts d to:
       ,                                           the pair
        ed                                           d[1]
          -hd*ed/F<G2                                d[0]-d[1]*G[0]/G[1]
     s                                           unfold
                                               else:
                           G                     G (don't change it, stop criterion for u)
 %2                                          take every second element
                                             we get the list [gcd(a,b),x',y']
K                                            store this list in K
                             ~Q,hQ_eQ        afterwards change Q to [Q[0],-Q[1]] = [a,-b]
                                             This will be important for the other parts.

```

Now I want to find a solution to `ax + by = c`. This is possible only, when `c mod gcd(a,b) == 0`. If this equation is satisfied, I simply multiplying `x',y'` with `c/gcd(a,b)`.

```
I!%vzhK...J*L/vzhKtK   implicit: z = c in string format (from input)
  %vzhK                evaluated(z) mod K[0] (=gcd(a,b))
I!                     if not ^ than:
             /vzhK        c/K[0]
           *L     tK      multipy ^ to each element in K[1:] (=[x',y'])
          J               and store the result in J, this is now [x,y]

```

We have an integer solution for `ax + by = c`. Notice, that `x`, `y` or both may be negative. So our goal is to transform these to non-negative.

The nice thing about Diophantine equations is, that we can describe all solution using only one initial solution. If `(x,y)` is a solution, that all other solutions are of the form `(x-n*b/gcd(a,b),y+n*a/gcd(a,b))` for `n` integer.

Therefore we want to find a `n`, where `x-n*b/gcd(a,b) >= 0` and `y+n*a/gcd(a,b >= 0`. After some transformation we end up with the two inequalities `n >= -x*gcd(a,b)/b` and `n >= y*gcd(a,b)/a`. Notice that the inequality symbol might look in the other direction due the division with a potential negative `a` or `b`. I don't care that much about it, I simply say that one number of `-x*gcd(a,b)/b - 1, -x*gcd(a,b)/b, -x*gcd(a,b)/b + 1` definitly satisfies inequality 1, and one number of `y*gcd(a,b)/a - 1, y*gcd(a,b)/a, y*gcd(a,b)/a + 1` satisfies inequality 2. It there is a `n`, that satisfies both inequalities, one of the 6 numbers also does.

Then I calculate the new solutions `(x-n*b/gcd(a,b),y+n*a/gcd(a,b))` for all 6 possible values of `n`. And I print the solution with the highest lowest value.

```
eoSNm-VJ/RhK_*LdQsm+LdtM3/V*LhK_JQ
                               _J    reverse J => [y,x]
                           *LhK      multiply each value with K[0] => [y*gcd,x*gcd]
                         /V      Q   vectorized division => [y*gcd/a,-x*gcd/b]
                  m                  map each d of ^ to:
                      tM3              [-1,0,1]
                   +Ld                 add d to each ^
                 s                   unfold
                                     these are the possible values for n
    m                                map each d (actually n) of ^ to:
             *LdQ                      multiply d to Q => [a*n,-b*n]
            _                          reverse => [-b*n,a*n]
        /RhK                           divide by K[0] => [-b*n/gcd,a*n/gcd]
     -VJ                               vectorized subtraction with J
                                       => [x+b*n/gcd,y-a*n/gcd]
 oSN                                 order the solutions by their sorted order
e                                    print the last one

```

The sort by their sorted order thing works the following way. I'm using the example `2x + 3y = 11`

I sort each of the 6 solutions (this are called keys), and sort the original solutions by their keys:

```
solutions: [1, 3], [4, 1], [7, -1], [-5, 7], [-2, 5], [1, 3]
keys:      [1, 3], [1, 4], [-1, 7], [-5, 7], [-2, 5], [1, 3]
sort by key:
solutions: [-5, 7], [-2, 5], [7, -1], [1, 3], [1, 3], [4, 1]
keys:      [-5, 7], [-2, 5], [-1, 7], [1, 3], [1, 3], [1, 4]

```

This sorts a complete non-negative solution to the end (if there is any).

# Answer
> 1 votes
* after Dennis' remarks, that made my previous idea upside-down, i had to change the code from its roots and it took me long term debugging, and cost me twice n° of bytes :'(.

## Matlab (660)

```
a=input('');b=input('');c=input('');if((min(a*c,b*c)>c*c)&&a*c>0&&b*c>0)||(a*c<0&&b*c<0),-1,return,end,g=abs(gcd(a,b));c=c/g;a=a/g;b=b/g;if(c~=floor(c)),-1,return,end,if(c/a==floor(c/a)&&c/a>0),e=c/a-b;if(e>0),e,a,return,else,c/a,0,return,end,end,if(c/b==floor(c/b)&&c/b>0),e=c/b-a;if(e>0),b,e,return,else,0,c/b,return,end,end,f=max(abs(a),abs(b));if f==abs(a),f=b;b=a;a=f;g=0.5;end,e=(c-b)/a;f=(c-2*b)/a;if(e<0&&f<e),-1,elseif(e<0&&f>e),for(i=abs(c*a):abs((c+1)*a)),e=(c-i*b);if(mod(e,a)==0)if(g==0.5),i,e/a;else,e/a,i,end,return,end,end,else for(i=1:abs(a)),e=(c-i*b);if(e/a<0),-1,elseif(mod(e,a)==0),if(g==0.5),i,e/a,else,e/a,i,end,return,end,end,end,-1

```

> * Well , i know its not golfed, since that type of languages isnt adapted for code length reduction, but, i can ensure that time-complexity is at its best.

## Explanation:

* the code takes three invariants a,b,c as input, these last ones are subdued to couple of conditions before proceeding to calculate:

1- if (a+b\>c) and (a,b,c\>0) no solution!

2- if (a+b \< c) ,(a,b,c\<0) no solution!

3- if (a, b) have common opposite signs of c : no solution!

4- if GCD(a,b) dosnt divide c, then no solution again! , otherwise, divide all variants by GCD.
* after this , we have to check another condition out, it should ease and shorteb the way to desired solution.

5- if c divide a or b , solution s= (x or y)=(c-\[ax,yb\])/\[b,a\]=C/\[b,a\]+\[ax,yb\]/\[b,a\]=S+\[ax,yb\]/\[b,a\] where S is natural so ax/b or by/a would have henceforth non-negative direct solutions which are respectively x=b or y=a . (notice that solutions can be just nil values in case previous arbitrary solutions are revealed negatives)
* when the program reaches this stage, a narrower range of solutions for x=(c-yb)/a is swept instead, thanks to congruence, of sweeping larger ranges of numbers ,which is come accross repetitively by regular cycles. the largest search field is \[x-a,x+a\] where a is the divisor.

## TRY IT

# Answer
> 0 votes
# Axiom, 460 bytes

```
w(a,b,x,u)==(a=0=>[b,x];w(b rem a,a,u,x-u*(b quo a)))
d(a,b,k)==(o:List List INT:=[];a=0 and b=0=>(k=0=>[1,1];[]);a=0=>(k=0=>[[1,0]];k rem b=0=>[1,k quo b];[]);b=0=>(k=0=>[[0,1]];k rem a=0=>[k quo a,1];[]);r:=w(a,b,0,1);q:=k quo r.1;(y,x,u,v):=(q*(r.1-r.2*a)quo b,q*r.2,b quo r.1,a quo r.1);m:=min(80,4+abs(k)quo min(abs(a),abs(b)));l:=y quo v;x:=x+l*u;y:=y-l*v;for n in -m..m repeat(t:=x+n*u;z:=y-n*v;t>=0 and z>=0 and t*a+z*b=k=>(o:=cons([t,z],o)));sort(o))

```

ungolf and some test

```
-- input a b and k for equation a*x+b*y=k
-- result one List of List of elments [x,y] of solution of
-- that equation with x and y NNI (not negative integers)
-- or Void list [] for no solution
diopanto(a,b,k)==
  o:List List INT:=[]
  a=0 and b=0=>(k=0=>[1,1];[])
  a=0=>(k=0=>[[1,0]];k rem b=0=>[1,k quo b];[])
  b=0=>(k=0=>[[0,1]];k rem a=0=>[k quo a,1];[])
  r:=w(a,b,0,1)
  q:=k quo r.1
  (y,x,u,v):=(q*(r.1-r.2*a)quo b,q*r.2,b quo r.1,a quo r.1)
  m:=min(80,4+abs(k)quo min(abs(a),abs(b)))
  l:=y quo v           -- center the interval
  x:=x+l*u; y:=y-l*v
  for n in -m..m repeat
     t:=x+n*u;z:=y-n*v
     t>=0 and z>=0 and t*a+z*b=k=>(o:=cons([t,z],o))
  sort(o)

 ------------------------------------------------------
(4) -> d(0,-9,0)
   (4)  [[1,0]]
                                                  Type: List List Integer
(5) -> d(2,3,11)
   (5)  [[4,1],[1,3]]
                                                  Type: List List Integer
(6) -> d(2,3,2)
   (6)  [[1,0]]
                                                  Type: List List Integer
(7) -> d(2,3,1)
   (7)  []
                                                  Type: List List Integer
(8) -> d(1152921504606846883,-576460752303423433,1)
   (8)
   [[135637824071393749,271275648142787502],
    [712098576374817182,1424197152749634385],
    [1288559328678240615,2577118657356481268],
    [1865020080981664048,3730040161963328151],
    [2441480833285087481,4882961666570175034]]
                                                  Type: List List Integer

```

In the other 'solutions' possible there was a bug because it tried to save the infinite solutions in one List; now it is imposed the limit of 80 solutions max

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


# Question
Title: FORTY TWO? SIX? NINE? Understand these and much more!
Given the written, spelled-out representation of an integer from `1` to `10^15-1` inclusive, convert it to an actual integer in decimal.

# Input Format

The input will always be a string of groups, where each group is composed only of letters and spaces(). The groups are separated by commas.

You may choose whether you want the letters to be all lowercase, all uppercase, or title case.

For the purposes of this challenge, there are no hyphens (`-`) between e.g. `"forty-two"`, so tokens within groups are separated by spaces only.

The input will contain no words `and`.

You can test if an input is valid by putting it as input into this Retina program.

Here is a full table of tokens:

```
Units:

+1 | "one"
+2 | "two"
+3 | "three"
+4 | "four"
+5 | "five"
+6 | "six"
+7 | "seven"
+8 | "eight"
+9 | "nine"

Teens:

+10 | "ten"
+11 | "eleven"
+12 | "twelve"
+13 | "thirteen"
+14 | "fourteen"
+15 | "fifteen"
+16 | "sixteen"
+17 | "seventeen"
+18 | "eighteen"
+19 | "nineteen

Tens:

+20 | "twenty"
+30 | "thirty"
+40 | "forty"
+50 | "fifty"
+60 | "sixty"
+70 | "seventy"
+80 | "eighty"
+90 | "ninety"

Hundred:

×100 | "hundred"

Place markings:

×10^3  | "thousand"
×10^6  | "million"
×10^9  | "billion"
×10^12 | "trillion

```

# How to Evaluate a Spelled-out Representation

We will be working with the example input `"forty five thousand,one hundred thirteen"`

First, split the input into groups by commas, to get e.g. `["forty five thousand","one hundred thirteen"]`

Then, evaluate each group:

1. Split by spaces to get a list of tokens
2. Start with a running total of 0
3. For each token, do as the table says. If the token is `9`, do `+9` and add `9` to the running total. If the token is `thousand`, multiply the running total by `1000`.

For the second example group, this would be:

```
running total    token
0
1                "one"
100              "hundred"
113              "thirteen"

```

For the first example group, this yields `45000`.

After this is done, sum each group to get the output e.g.`45113`.

Note that you do not have to evaluate the number exactly as I had laid it out as long as you produce the same results. For example, you could do string substitution to get an expression you can eval.

# Test Cases

```
"one" -> 1
"ten" -> 10
"forty" -> 40
"one hundred" -> 100
"one thousand" -> 1000
"ten million" -> 10000000
"one hundred billion" -> 100000000000
"ten trillion" -> 10000000000000
"nine hundred ninety nine trillion,nine hundred ninety nine billion,nine hundred ninety nine million,nine hundred ninety nine thousand,nine hundred ninety nine" -> 999999999999999
"two hundred forty one trillion,eight hundred sixty one billion,seventy seven million,one hundred fifty four thousand,twenty eight" -> 241861077154028
"four hundred eighty five trillion,six hundred fifty seven billion,six hundred million,four hundred eighty two thousand,one hundred seventy eight" -> 485657600482178
"three hundred eighty nine trillion,five hundred twenty billion,one hundred ninety seven million,nine hundred fifty thousand,nine hundred eighty four" -> 389520197950984
"one hundred fifty five trillion,five hundred five billion,four hundred fifty eight million,six hundred seventy thousand,six hundred sixty one" -> 155505458670661
"one hundred fifty two trillion,ninety three billion,two hundred twenty one million,nine hundred thirty two thousand,five hundred eighty" -> 152093221932580
"three hundred forty three trillion,two hundred eighty six billion,nine hundred sixty five million,six hundred four thousand,two hundred seventy nine" -> 343286965604279
"six hundred ninety eight trillion,nine hundred seventy five billion,one hundred five million,sixty thousand,two hundred forty" -> 698975105060240
"five hundred seventy four trillion,one hundred sixty billion,five hundred ninety eight million,one hundred nine thousand,sixty two" -> 574160598109062
"four hundred seventy seven trillion,two hundred twenty five billion,eight hundred sixty three million,one hundred eighteen thousand,eight hundred four" -> 477225863118804
"eighty seven trillion,two hundred eighty three billion,six hundred eighty eight million,eight hundred fifty three thousand,sixty nine" -> 87283688853069
"eight hundred trillion,fifty billion,five hundred seven million,eighty thousand,fifty" -> 800050507080050
"seven hundred seventy three trillion,three hundred billion,four hundred thousand,nine" -> 773300000400009
"three hundred trillion,two hundred eighty eight billion" -> 300288000000000
"four hundred trillion,two hundred six billion,sixty six million,sixty" -> 400206066000060
"eight trillion,ninety nine million,four hundred sixty thousand,four hundred" -> 8000099460400
"seventy trillion,six hundred billion,forty million,seven hundred thousand" -> 70600040700000
"one hundred twenty billion,one hundred million,seventy thousand,forty" -> 120100070040
"four billion,eight hundred million,five hundred four thousand,five hundred six" -> 4800504506
"five hundred trillion,three hundred fifty five billion,seventy six thousand" -> 500355000076000
"fifty eight trillion,ninety eight billion,forty" -> 58098000000040

```

---

## Not a Duplicate

The other question involves the units only modifying the previous value, such that every 'group' is composed of only an integer and a modifier. This requires a more dynamic approach in order to calculate groups of varying sizes.

# Answer
# Mathematica, 28 bytes

~~<sup>*Mathematica has a builtin for everything*</sup>~~

```
Interpreter@"SemanticNumber"

```

Of course, Mathematica has a built-in interpreter for spelled-out numbers.

Try it on Wolfram Sandbox

### Usage

```
f=Interpreter@"SemanticNumber"

```

```
f["three hundred trillion,two hundred eighty eight billion"]

```

> ```
> 300288000000000
>
> ```

```
f["five hundred seventy four trillion,one hundred sixty billion,five hundred ninety eight million,one hundred nine thousand,sixty two"]

```

> ```
> 574160598109062
>
> ```
> 9 votes

# Answer
# Python 2, 491 bytes

```
a,m,s,r={'one':1,'two':2,'three':3,'four':4,'five':5,'six':6,'seven':7,'eight':8,'nine':9,'ten':10,'eleven':11,'twelve':12,'thirteen':13,'fourteen':14,'fifteen':15,'sixteen':16,'seventeen':17,'eighteen':18,'nineteen':19,'twenty':20,'thirty':30,'forty':40,'fifty':50,'sixty':60,'seventy':70,'eighty':80,'ninety':90},{'hundred':100,'thousand':1e3,'million':1e6,'billion':1e9,'trillion':1e12},input(),0
for i in s.split(','):
 j=0
 for k in i.split():j=j+a[k]if k in a else j*m[k]
 r+=j
print r

```

Try it online!
> 2 votes

---
Tags: code-golf, natural-language
---


title: Primus-Orderus Primes

text:
# Question
Title: Primus-Orderus Primes
# Who are they?

Primus-Orderus Primes (POP) are primes which contain their **order** in the sequence of primes.
So the `nth` prime, in order to be POP, must contain all the digits of `n` in a certain way which I'll explain.

# Examples

Let's get things clearer: All digits of `n` must appear among the digits of POP in the same order they appear in `n`

The `6469th` prime is `64679` which is POP because it contains all digits of `6469` in the right order .
`1407647` is POP because it is the `107647th` prime number

**14968819** is **POP** (968819th prime).So this challenge is **NOT** OEIS (A114924)

1327 is **NOT POP** because it is the `217th` prime (digits are not in the right order)

# The Challenge

You guessed right!
Given an integer `n`, output the `nth` POP

# Test Cases

input-\> output

```
1->17
3->14723
5->57089
10->64553
29->284833
34->14968819

```

This is so the shortest answer in bytes wins!

**All these should be 1-Indexed**

# Answer
> 3 votes
# Mathematica, 104 bytes

Extremely **efficient**

```
(t=i=1;While[t<#+1,If[!FreeQ[Subsets[(r=IntegerDigits)@Prime@i,{Length@r@i}],r@i],t++];i++];Prime[i-1])&

```

finds n=34 in under a minute

# Answer
> 3 votes
# Husk, 11 bytes

```
!fS¤o€Ṗdṗİp

```

Try it online!

Not that fast, computes f(5) in around 30 seconds on TIO

### Explanation

```
!fS¤o€Ṗdṗİp
 f       İp    Filter the list of prime numbers and keep only those for which:
  S¤o€Ṗdṗ       The "d"igits of its index in the "ṗ"rime numbers are an "€"lement of the
                  "Ṗ"owerset of its "d"igits
!              Return the element at the desired index of this filtered list

```

# Answer
> 2 votes
# Python 2 \+ gmpy2, 188 162 bytes

Quite efficient, finds n=34 in 22 seconds on TIO!

Could probably be golfed a bit

```
from gmpy2 import*
def F(a,b):
 i=k=0
 while b[i:]and a[k:]:k+=a[k]==b[i];i+=1
 return"0">a[k:]
x=input()
u=z=1
while x:z=next_prime(z);x-=F(`u`,`z`);u+=1
print z

```

Try it online!

# Answer
> 1 votes
# 05AB1E, 11 bytes

```
µN<Ø©æNå½}®

```

Try it online!

Extremely inefficient.

# Answer
> 0 votes
# Jelly, 12 bytes

```
ÆNDŒPḌċµ#ṪÆN

```

Try it online!

Extremely inefficient but works.

---
Tags: code-golf, sequence, primes
---


title: Fold the integer to save space!

text:
# Question
Title: Fold the integer to save space!
The crazy mathematician owns a wide collection of numbers, and therefore the space he has left is quite limited. To save some, he must fold his integers, but unfortunately he is really lazy. Your task, if you wish to help him, is to create a function / program that folds a given positive integer for our number maniac.

# How to fold an integer?

If it is evenly divisible by the sum of its digits, divide it by the sum of its digits. If it doesn't meet that requirement, take its remainder when divided by the sum of its digits. Repeat the process until the result reaches `1`. The folded integer is the number of operations you had to perform. Let's take an example (say `1782`):

1. Get the sum of its digits: `1 + 7 + 8 + 2 = 18`. `1782` is evenly divisible by `18`, so the next number is `1782 / 18 = 99`.
2. `99` is not evenly divisible by `9 + 9 = 18`, hence we take the remainder: `99 % 18 = 9`.
3. `9` is obviously divisible by `9`, so we divide it and obtain `1`.

The result is `3`, because 3 operations were required in order to reach `1`.

## Rules and Specs

* Some integers might have the sum of digits equal to `1`, such as `10` or `100`. Your program doesn't need to handle such cases. That means, you will be guaranteed that the integer given as input doesn't have the sum of digits equal to `1`, and no operation with the given integer will result in a number whose sum of digits is `1` (except for `1` itself, which is the "target"). For example, you will never receive `10` or `20` as input.
* The input will be a positive integer higher than `1`.
* **Default Loopholes** apply.
* You can take input and provide output by **any standard mean**.

---

# Test Cases

```
Input     -> Output

2         -> 1
5         -> 1
9         -> 1
18        -> 2
72        -> 2
152790    -> 2
152       -> 3
666       -> 3
777       -> 3
2010      -> 3
898786854 -> 4

```

Here is **a program** that lets you visualize the process and try more test cases.

---

This is , so the shortest code *in each language* (scored in bytes) wins!

# Answer
# 05AB1E, ~~13~~ 12 bytes

```
[¼DSO‰0Kθ©#®

```

Try it online!

**Explanation**

```
[               # start loop
 ¼              # increment counter
  D             # duplicate current value
   SO           # sum the digits in the copy
     ‰          # divmod the current value by its digit-sum
      0K        # remove 0 from the resulting list
        θ       # pop the last element
         ©      # store a copy in register
          #     # if the current value is 1, break
           ®    # push the copy from register
                # implicitly output counter

```
> 6 votes

# Answer
# Python 2, ~~63~~ 57 bytes

-1 thanks to totallyhuman
-1 thanks to Mr. Xcoder
-4 thanks to reffu

```
def f(n):a=sum(map(int,`n`));return n>1and-~f(n%a or n/a)

```

Try it online!
> 6 votes

# Answer
# JavaScript (ES6), ~~66~~ ~~58~~ ~~51~~ 49 bytes

Takes input as an integer. Returns `false` for `0` or `1` and throws an overflow error when it encounters any number whose digits add up to `1`.

```
f=n=>n>1&&f(n%(x=eval([...""+n].join`+`))||n/x)+1

```
* 8 bytes saved with help from Justin.

---

## Test it

```
o.innerText=(

f=n=>n>1&&f(n%(x=eval([...""+n].join`+`))||n/x)+1

)(i.value=898786854);oninput=_=>o.innerText=f(+i.value)
```

```
<input id=i type=number><pre id=o>
```
> 5 votes

# Answer
# Haskell, ~~85~~ 78 bytes

```
f 1=0
f n|r<1=1+f(n`div`s)|1<2=1+f r where s=sum(read.pure<$>show n);r=n`rem`s

```

Saved 7 bytes thanks to Bruce Forte.

Try it online.
> 5 votes

# Answer
## Husk, 12 bytes

```
←€1¡Ṡ§|÷%oΣd

```

Try it online!

## Explanation

```
←€1¡Ṡ§|÷%oΣd  Implicit input, e.g. n=1782
    Ṡ§|÷%oΣd  This part defines the transformation.
         oΣ   Sum of
           d  digits: s=18
    Ṡ   %     n mod s: 0
     §|       or (take this branch if last result was 0)
       ÷      n divided by s: 99
   ¡          Iterate the transformation: [1782,99,9,1,1,1,...
 €1           Index of 1 (1-based): 4
←             Decrement: 3
              Print implicitly.

```
> 4 votes

# Answer
# Japt, ~~22~~ ~~19~~ 17 bytes

*-3 bytes thanks to @Shaggy.*
*-2 bytes thanks to @ETHproductions*

```

ìx
>1©1+ßU%VªU/V

```

Try it online!
> 3 votes

# Answer
# C# (.NET Core), 87 bytes

```
n=>{int i=0,k,l;for(;n>1;++i){for(l=n,k=0;l>0;l/=10)k+=l%10;n=n%k>0?n%k:n/k;}return i;}

```

Try it online!

Lambda function that takes and returns an integer.
> 3 votes

# Answer
# Retina, 100 bytes

```
$
;
{`(.+);
$1$*1;$&
(?<=;.*)\d(?=.*;)
$*
.*;1;(.*)
$.1
r`(1)*(\3)*;(1+);
$#1;$#2;1
0;(.*);|;.*;
$1;

```

Try it online! Link only includes smaller test cases as the larger ones take too long.
> 2 votes

# Answer
# Mathematica, 73 bytes

```
(t=#;For[r=0,t>1,r++,If[(s=Mod[t,g=Tr@IntegerDigits@t])<1,t=t/g,t=s]];r)&

```
> 2 votes

# Answer
# PHP, 68+1 bytes

unary output:

```
for($n=$argn;$n>1;$n=$n%($s=array_sum(str_split($n)))?:$n/$s)echo 1;

```

decimal output, 73+1 bytes:

```
for($n=$argn;$n>1;$i++)$n=$n%($s=array_sum(str_split($n)))?:$n/$s;echo$i;

```

Run as pipe with `-nR` or try it online.

---

The Elvis operator requires PHP 5.3 or later. For older PHP, replace `?:` with `?$n%$s:` (+5 bytes).
> 2 votes

# Answer
# Haskell, ~~94~~ ~~93~~ ~~89~~ 88 bytes

This feels really long..

```
length.fst.span(/=1).iterate g
g x|(d,m)<-x`divMod`sum[read[d]|d<-show x]=last$m:[d|m<1]

```

Try it online!

Thanks @Laikoni & @nimi for golfing off 1 byte each!
> 2 votes

# Answer
# C (gcc), ~~83~~ ~~81~~ ~~76~~ 73 bytes

```
i,k,s;f(n){k=n;for(i=0;k>1;i++,n=k=k%s?:k/s)for(s=0;n;n/=10)s+=n%10;n=i;}

```

Try it online!
> 2 votes

# Answer
# Ruby, 46 bytes

```
f=->n{s=n.digits.sum;n<2?0:1+f[n%s<1?n/s:n%s]}

```
> 2 votes

# Answer
# Jelly, 12 bytes

```
dDS$Ṛȯ/µÐĿL’

```

Try it online!
> 1 votes

# Answer
# Perl, ~~71~~ bytes, ~~64~~ bytes, 63 bytes

```
-pl

$c=0;while($_>1){$s=0;$s+=$_ for/./g;$_=$_%$s?$_%$s:$_/$s;++$c};$_=$c

```

Try it online

EDIT: saved 7 bytes, thanks to Xcali's comment

```
-p

while($_>1){$s=0;$s+=$_ for/./g;$_=$_%$s?$_%$s:$_/$s;++$c}$_=$c

```

EDIT: since 5.14 non destructive substitution s///r

```
-pl

while($_>1){$s=eval s/\B/+/gr;$_=$_%$s?$_%$s:$_/$s;++$c}$_=$c

```
> 1 votes

# Answer
# Pyth, ~~20~~ 14 bytes

```
tl.ue-.DNsjNT0

```

Try it here.
> 1 votes

# Answer
# Dyalog APL, 36 bytes

```
{x←+/⍎¨⍕⍵⋄1=⍵:0⋄0=x|⍵:1+∇⍵÷x⋄1+∇x|⍵}

```

Try it online!

**How?**

```
{
   x←+/⍎¨⍕⍵      ⍝ x = digit sum
   1=⍵:0         ⍝ if arg = 1: bye
   0=x|⍵:1+∇⍵÷x  ⍝ if arg divisible by x: recurse with arg/x
   1+∇x|⍵        ⍝ recurse with arg mod x
}

```
> 1 votes

# Answer
# Gaia, 13 bytes

```
-@{:ΣZ¤∨)‡}°\

```

Try it online!

### Explanation

```
-              Push -1 (this will be the counter)
 @             Push input (the starting number)
  {:ΣZ¤∨)‡}°   Repeat this block until the results of 2 consecutive runs are the same:
   :            Copy the number
    Σ           Digital sum
     Z          Divmod number by digital sum
      ¤         Swap
       ∨        Logical or: left-most non-zero out of (number mod sum, number div sum)
        )‡      Increment the counter
            \  Delete the final 1, implicitly print the counter

```
> 1 votes

# Answer
## Matlab, 150 bytes

```
function[d]=X(x)
d=0;while ~strcmp(x,'1')z='sum(str2num(x(:)))';a=eval(['rem(',x,',',z,')']);y=num2str(a*(a>0)+eval([x,'/',z])*(a==0));x=y;d=d+1;end

```

Inputs should be given to the function as a string, such as X('152').

The function works by while looping and incrementing d. The `x=y;` line was necessary to avoid an error of Matlab trying to read and overwrite a variable value at the same time, apparently, which was a new one on me.

Ungolfed:

```
function[d]=X(x)
d=0;
while ~strcmp(x,'1')
    z='sum(str2num(x(:)))';
    a=eval(['rem(',x,',',z,')']);
    y=num2str(a*(a>0)+eval([x,'/',z])*(a==0));
    x=y;
    d=d+1;
end

```
> 1 votes

# Answer
# Haskell, 68 bytes

```
f 1=0
f n=1+[f x|x<-[mod n,div n]<*>[sum$read.pure<$>show n],x>0]!!0

```

Try it online! Based on w0lf's answer.
> 0 votes

# Answer
# , 85 bytes

```
function(n){while(n>1){n="if"(x<-n%%(d=sum(n%/%10^(nchar(n):0)%%10)),x,n/d)
F=F+1}
F}

```

Anonymous function that returns the required output.

Verify all test cases!
> 0 votes

---
Tags: code-golf, number, integer, division
---


title: How hard can I crush my array?

text:
# Question
Title: How hard can I crush my array?
Lets define the process of crushing an array of numbers. In a crush we read the array left to right. If at a point we encounter two of the same element in a row we remove the first one and double the second one. For example here is the process of crushing the following array

```
[5,2,2,3]
 ^
[5,2,2,3]
   ^
[5,2,2,3]
     ^
[5,4,3]
   ^
[5,4,3]
     ^

```

The same element can be collapsed multiple times, for example `[1,1,2]` becomes `[4]` when crushed.

We will call an array uncrushable when the process of crushing that array does not change it. For example `[1,2,3]` is still `[1,2,3]` after being crushed.

Your task is to take an array and determine the number of crushes required to make it uncrushable. You need only support integers on the range of **0** to **232-1**

This is so answers will be scored in bytes with less bytes being better.

## Test Cases

```
[1] -> 0
[1,1] -> 1
[2,1,1] -> 2
[4,2,1,1] -> 3
[2,2,2,1,1] -> 3
[0,0,0,0] -> 1
[4,0,0,0,4] -> 1
[4,0,0,0,0,4] -> 1
[] -> 0

```

# Answer
# x86 assembly (64-bit), 66 65 bytes

```
31 c0 57 59 56 51 56 5f 4d 31 c0 48 83 c6 08 48
83 e9 01 76 1b fc f2 48 a7 75 15 48 d1 67 f8 51
56 57 f3 48 a5 5f 5e 59 fd 48 a7 49 ff c0 eb e5
59 5e 4c 29 c1 48 ff c2 4d 85 c0 75 c7 48 ff c8
c3

```

String instructions were helpful. Having to correct for off-by-one errors in a 64-bit environment was not.

Fully commentated source code:

```
.globl crush
crush:
/* return value */
xor %eax, %eax
/* save our length in rcx */
push %rdi
pop %rcx
pass:
/* save the start of the string and the length */
push %rsi
push %rcx
/* this is the loop */
/* first copy source to dest */
push %rsi
pop %rdi
/* and zero a variable to record the number of squashes we make this pass */
xor %r8, %r8
/* increment source, and decrement ecx */
add $8,%rsi
sub $1,%rcx
/* if ecx is zero or -1, we're done (we can't depend on the code to take care of this
automatically since dec will leave the zero flag set and cmpsq won't change it) */
jbe endpass
compare:
/* make sure we're going forward */
cld
/* compare our two values until we find two that are the same */
repne cmpsq
/* if we reach here, we either found the end of the string, or
we found two values that are the same. check the zero flag to
find out which */
jne endpass
/* okay, so we found two values that are the same. what we need
to do is double the previous value of the destination, and then
shift everything leftwards once */
shlq $1, -8(%rdi)
/* easiest way to shift leftwards is rep movsq, especially since
our ecx is already right. we just need to save it and the rsi/rdi */
push %rcx
push %rsi
push %rdi
rep movsq
pop %rdi
pop %rsi
pop %rcx
/* problem: edi and esi are now one farther than they should be,
since we can squash this dest with a different source. consequently
we need to put them back where they were. */
std
cmpsq
/* we don't need to put ecx back since the list is now one shorter
than it was. */
/* finally, mark that we made a squash */
inc %r8
/* okay, once we've reached this point, we should have:
 edi and esi: next two values to compare
 ecx: number of comparisons left
so we just jump back to our comparison operation */
jmp compare
endpass:
/* we reached the end of the string. retrieve our old ecx and esi */
pop %rcx
pop %rsi
/* rsi is accurate, but rcx is not. we need to subtract the number of squashes
that we made this pass. */
sub %r8, %rcx
/* record that we performed a pass */
inc %rax
/* if we did make any squashes, we need to perform another pass */
test %r8, %r8
jnz pass
/* we reached the end; we've made as many passes as we can.
decrement our pass counter since we counted one too many */
dec %rax
/* and finally return it */
ret

```

I may try doing this in 32-bit, if only for fun, since those REX prefixes really killed me.

Edit: shaved one byte off by replacing lodsq with add, %rdx with %rax, and collapsing two cld's into one.
> 12 votes

# Answer
# Pyth, 22 bytes

```
tl.uu?&GqeGH+PGyH+GHN[

```

Verify all testcases.
> 9 votes

# Answer
# Haskell, 66 bytes

```
f(a:b:x)|a==b=f$a+a:x|1>0=a:f(b:x)
f x=x
g x|f x==x=0|1>0=1+g(f x)

```

Try it online!

## Explanation

`f` is a function that crushes a list. It performs the crush as desribed in the question. `g` is a function that counts the number of crushes. If `f x==x`, `g x=0` otherwise `g x=1+g(f x)`.
> 6 votes

# Answer
# Paradoc (v0.2.10), 16 bytes (CP-1252)

```
{—1\ε=k+x}]»}IL(

```

Try it online! / with header/footer that check all test cases

Takes a list on the stack, and results in a number on the stack.

Pretty straightforward implementation, to be quite honest. Crushes a list by starting with a sentinel -1, looping through the list, pushing each element and adding it to the element beneath it iff they're equal. At the end we cut off the -1. We only crush equal numbers together and all the problem's numbers are nonnegative, so the -1 sentinel won't affect the crushing process. With crushing implemented, it's only a matter of counting iterations to its fixed point.

Explanation:

```
{            }I  .. Iterate this block: repeatedly apply it until a fixed
                 .. point is reached, and collect all intermediate results
 —1              ..   Push -1 (note that that's an em dash)
   \             ..   Swap it under the current list of numbers
    ε    }       ..   Execute this block for each element in the list:
     =           ..     Check if it's equal to the next element on the stack...
      k          ..       ... while keeping (i.e. not popping either of) them
       +         ..     Add the top two elements of the stack...
        x        ..       ... that many times (so, do add them if they were
                 ..       equal, and don't add them if they weren't)
          ]      ..   Collect all elements pushed inside the block that
                 ..     we're iterating into a list
           »     ..   Tail: take all but the first element (gets rid of the -1)
              L  .. Compute the length of the number of intermediate results
               ( .. Subtract 1

```

If we could assume the input were nonempty, we wouldn't need the sentinel and could shave 2 bytes: `{(\ε=k+x}]}IL(`

Another fun fact: we only lose 2 bytes if we force ourselves to only use ASCII: `{1m\{=k+x}e]1>}IL(`
> 5 votes

# Answer
# JavaScript (ES6), 86 bytes

```
f=a=>a.length>eval("for(i=0;a[i]>-1;)a[i]==a[++i]&&a.splice(--i,2,a[i]*2);i")?1+f(a):0

```

## Ungolfed and Explained

```
f=a=>                           // function taking array a
    a.length > eval("           // if a.length > the result of the following...
        for(i=0; a[i]>-1;)      //   loop from 0 until the current value is undefined (which is not > -1)
            a[i] == a[++i] &&   //     if the current value equals the next one...
                a.splice(--i,   //       splice the array at the first index of the pair...
                    2,          //       by replacing 2 items...
                    a[i]*2);    //       with the current item * 2
                                //       this also decrements the counter, which means the current value is now the next
    i")                         //   return the counter, which is new a.length
        ? 1+f(a)                // if that was true, the array was crushed. add 1 and recur with the new array
        : 0                     // otherwise just return 0

```

## Tests

```
f=a=>a.length>eval("for(i=0;a[i]>-1;)a[i]==a[++i]&&a.splice(--i,2,a[i]*2);i")?1+f(a):0

;[ [1], [1,1], [2,1,1], [4,2,1,1], [2,2,2,1,1], [0,0,0,0], [4,0,0,0,4], [4,0,0,0,0,4], []
].forEach(x=>console.log( JSON.stringify(x) + " -> " + f(x) ))
```

```
.as-console-wrapper{max-height:100%!important}
```
> 4 votes

# Answer
# JavaScript, 67 bytes

```
f=a=>a.map(a=>k[k[d-1]!=a?d++:(a*=z=2,d-1)]=a,k=d=[z=0])&&z&&f(k)+1

```

Try it online!
> 4 votes

# Answer
# Brain-Flak, 144 bytes

```
([])({<{}>(<(([][()]){[{}]<({}[({})]<(())>){({}<{}>({})<>)((<>))}>{}{{}(<(({}){})>)}{}([][()])})>{()(<{}>)}{}{}<><([]){{}({}<>)<>([])}>{}<>)}<>)

```

Try it online!

### Explanation

```
([])                                                                 Push stack height (starts main loop if list nonempty)
     {                                                       }       Do while the last iteration involved at least one crush:
      <{}>                                                           Remove crush indicator
           <(...)>                                                   Do a crush iteration
                  {()(<{}>)}                                         Evaluate to 1 if list was changed
                            {}{}                                     Remove zeroes
                                <>                        <>         On other stack:
                                  <([]){{}        ([])}>{}           Do while stack is nonempty:
                                          ({}<>)<>                   Move to first stack
          (                                                 )        Push 1 if crush worked, 0 otherwise
    (                                                         <>)    Push sum of results on other stack and implicitly print

```

The crush function evaluates to the number of pairs of items that were crushed together:

```
([][()]){[{}]                                                            ([][()])}    Do while stack height isn't 1:
              ({}[({})]      )                                                        Calculate difference between top two elements
                       <(())>                                                         Push a 1 below difference
                              {                    }                                  If difference was nonzero (don't crush this pair)
                               ({}    ({})<>)                                         Reconstruct top element and place on other stack
                                  <{}>       ((<>))                                   Push zeros to exit this conditional and skip next
             <                                      >{}                               Evaluate as zero
                                                       {              }{}             If difference was zero (crush this pair):
                                                        {}                            Evaluate as previously pushed 1
                                                          (<(({}){})>)                Double top of stack

```
> 3 votes

# Answer
# Java 8, 120 bytes

A lambda from `List<Long>` to `Integer`. Input list must implement `remove(int)` (e.g. `ArrayList`). Assign to `Function<List<Long>, Integer>`.

```
l->{int c=-1,i,f=1;for(;f>0;c++)for(f=i=0;++i<l.size();)if(l.get(i)-l.get(i-1)==0)l.set(i-=f=1,2*l.remove(i));return c;}

```

Try It Online

## Ungolfed lambda

```
l -> {
    int
        c = -1,
        i,
        f = 1
    ;
    for (; f > 0; c++)
        for (f = i = 0; ++i < l.size(); )
            if (l.get(i) - l.get(i - 1) == 0)
                l.set(i -= f = 1, 2 * l.remove(i));
    return c;
}

```

`c` counts the number of crushes so far, `i` is the index into the list, and `f` indicates whether to continue crushing the list when an iteration finishes. Inside the loops, each adjacent pair is compared. `i` is incremented unconditionally, so if an element is removed by crushing, `i` is decremented first to cancel out the increment. The former element is removed from the list.

## Acknowledgments

* Bugfix thanks to Olivier Grégoire: boxed equality test
> 3 votes

# Answer
# Python 2, 112 110 108 107 105 100 bytes

**Edit:** saved 2 bytes by removing `or` in return statement

**Edit:** saved 2 bytes by having `i` as the index of the second of the two elements to be accessed

**Edit:** saved 1 byte thanks to @Mr.Xcoder

**Edit:** saved 7 bytes thanks to @jferard

```
def f(x):
 i=e=1
 while x[i:]:
	if x[~-i]==x[i]:del x[i];i-=1;x[i]*=2;e=2
	i+=1
 return~-e and-~f(x)

```

Try it online!
> 2 votes

# Answer
## JavaScript (ES6), 83 bytes

```
f=([x,y,...a],b=[],c)=>1/x?x==y?f([x+y,...a],b,1):f([y,...a],[...b,x],c):c?1+f(b):0

```

Explanation: The elements are recursively extracted from the original array and unique values are appended to `b` while `c` is a flag to indicate whether the array had been successfully crushed.
> 2 votes

# Answer
# JavaScript (ES6), 70 bytes

```
f=(a,j=m=0,t=[])=>a.map(e=>t[e==t[j-1]?(e*=m=2,j-1):j++]=e)&&m&&1+f(t)

```

**Explanation:**

```
f=(
  a,                  //the input
  j=m=0,              //j is the index into t; m starts out falsey
  t=[]                //t will hold the crushed array
)=>
  a.map(e=>           //for each element in the array
    t[e==t[j-1] ?     //if the element repeats:
      (e*=m=2,        //... multiply it by two, set m to truthy,
       j-1) :         //... and index the previous element of t.
      j++             //else append to t, and increment its index.
    ]=e               //set this index of t to the current value of e
  ) &&                //map is always truthy
  m &&                //if m is falsey, return 0
  1+f(t)              //else return 1 plus the recurse on t

```

**Test Cases:**

```
f=(a,j=m=0,t=[])=>a.map(e=>t[e==t[j-1]?(e*=m=2,j-1):j++]=e)&&m&&1+f(t)

console.log(f([1])) // 0
console.log(f([1,1])) // 1
console.log(f([2,1,1])) // 2
console.log(f([4,2,1,1])) // 3
console.log(f([2,2,2,1,1])) // 3
console.log(f([0,0,0,0])) // 1
console.log(f([4,0,0,0,4])) // 1
console.log(f([4,0,0,0,0,4])) // 1
console.log(f([])) // 0
```
> 2 votes

# Answer
# Perl 5, 96 bytes

94 code, 2 for `-pa`

```
do{$\++;$l=@F;for($i=0;++$i<@F;){$F[$i]==$F[$i-1]&&splice@F,$i,2,$F[$i--]*2}}while$l!=@F}{$\--

```

Try it online!
> 2 votes

# Answer
# J, 54 bytes

```
[:<:@#[:".@":@(,`(+:@[,}.@])@.({.@]=[))/^:a:@".@":_,|.

```

Try it online!

Not my best golf by any means. Surely there has to be a better way of converting a list with one item to an atom.

# Explanation

```
crush =. ,`(+:@[ , }.@])@.({.@] = [)/
times =. <:@# [: ".@":@crush^:a:@".@": _ , |.

```

### crush

This crushes an array once. It needs to be given the array in *reverse* since J's insert works right-to-left (something I learned today). This doesn't particularly matter, since all we need to output is the number of times we can crush the array.

```
,`(+:@[ , }.@])@.({.@] = [)/
                           /  Fold/reduce from the right
                  {.@] = [    Head of the running array equals the left argument?
   +:@[ ,                     If so, prepend double the argument to
          }.@]                the array minus its head
,                             Else, prepend the left argument.

```

### times

This is fairly straightforward: apply crush to the array until our result converges, but there are a few issues I had to deal with that result in much more code than I anticipated.

First, when crushing reduces to a single element, that element is actually in a one item list (i.e. it is nonatomic), so the function is applied *again* resulting in overcounting. To fix this, I used a hack I came up with to reduce a single element list to an atom which is `".@":` (convert to string and then evaluate).

Second, `crush` errors on the empty list. I *think* you can define how a function should behave on receiving empty input with insert (`/`), but I couldn't find anything after a cursory look, so I'm using another workaround. This workaround is to prepend `_` (infinity) to the list since it will never affect the number of times the array is crushed (`_ > 2^64`). *However*, this results in a single element list consisting of `_` when given the empty list, so we need to convert to an atom *again* before crushing.

```
<:@# [: ".@":@crush^:a:@".@": _ , |.
                                  |.  Reverse input
                              _ ,     Prepend infinity
                        ".@":         Convert single-element list to atom
              crush                   Crush the list and after
        ".@":                         Convert single-element list to atom
                   ^:a:               until it converges, storing each
                                      iteration in an array
<:@#                                  Length of the resulting list minus 1

```
> 1 votes

# Answer
# Jelly, 21 bytes

```
ṪḤ,⁼?⁹⁸;µ/Ḋ$¹L’$?ÐĿL’

```

Try it online!
> 1 votes

# Answer
# , ~~142~~ 75 bytes

```
function(l){while(any(z<-which(!diff(l)))){l[z]=l[z]*2
l=l[-z-1]
F=F+1}
+F}

```

Try it online!
> 1 votes

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


title: Code Golf Banner

text:
# Question
Title: Code Golf Banner
Ouput the following banner:

```
   _____          _         _____       _  __
  / ____|        | |       / ____|     | |/ _|
 | |     ___   __| | ___  | |  __  ___ | | |_
 | |    / _ \ / _` |/ _ \ | | |_ |/ _ \| |  _|
 | |___| (_) | (_| |  __/ | |__| | (_) | | |
  \_____\___/ \__,_|\___|  \_____|\___/|_|_|

```

The code that has the fewest bytes wins! I'm interested to see what clever formulas some of you come up with, bare in mind I just created this in notepad with no clever formula in mind so you may not be likely in finding one.

# Answer
# Jelly, 128 bytes

```
“UyɠȯaẹṇṾƊSḳẋƘø;ṫṃ42MọẆẇB3tʂñṅƈṠUẈṣcC\ÑḢ¦¿$Ọỵịnß⁻ȥ2¶ø⁸Ḥ¢ȮN÷ẹƘḣƘßFĠC⁸⁴ʠe'ȮƊẹġƒhSṅsɼĖḟṘʋÆỌVKɠeḌ⁽ṗ?=ƈƥḍP⁴ĿḳaɲƬ*ṪñṪ’ṃ“_/|\`( ),”s46Y

```

Try it online!

This is just a direct compression, no tricks :).
> 1 votes

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