title: Dominate a zero-sum game

text:
# Question
Title: Dominate a zero-sum game
Consider a zero-sum game with 2 contestants. Each round, each contestant chooses, independently of each other, one of \\$n \ge 2\\$ different choices. Depending on the two chosen choices, one player is awarded an amount from the other player's pot. For example, the following table shows the gains (positive integers) and losses (negative integers) for Player 1 for each of \\$9\\$ possible choices:

$$\begin{array}{c|c|c|c} & \text{Player 1 chooses A} & \text{Player 1 chooses B} & \text{Player 1 chooses C} \\ \hline \text{Player 2 chooses A} & 1 & 2 & 2 \\ \hline \text{Player 2 chooses B} & -2 & 1 & 2 \\ \hline \text{Player 2 chooses C} & 3 & -1 & 0 \\ \end{array}$$

For example, if Player 1 chooses \\$A\\$ and Player 2 chooses \\$C\\$, Player 1 gains \\$3\\$ and Player 2 loses \\$3\\$.

However, this table is needlessly complex. We can see that, assuming both players are playing to win, some choices are always suboptimal. For example, Player 1 would never choose \\$B\\$. No matter what Player 2 chooses, Player 1 choosing \\$C\\$ will produce a result that is either better or equal to \\$B\\$, as each element in \\$C\\$ is greater than or equal to its corresponding element in \\$B\\$. Therefore, we can say that \\$C\\$ **dominates** \\$B\\$, and we can remove \\$\text{Player 1 chooses B}\\$ from our matrix:

$$\begin{array}{c|c|c} & \text{Player 1 chooses A} & \text{Player 1 chooses C} \\ \hline \text{Player 2 chooses A} & 1 & 2 \\ \hline \text{Player 2 chooses B} & -2 & 2 \\ \hline \text{Player 2 chooses C} & 3 & 0 \\ \end{array}$$

Additionally, we can see that Player 2 would never choose \\$A\\$ over \\$B\\$, as their payoff is always higher or equal from \\$B\\$ than it is from \\$A\\$, as each value in \\$B\\$ is *less than or equal to* it's corresponding element in \\$A\\$. So if Player 1 chooses \\$A\\$, then Player 2 either loses \\$1\\$ (\\$A\\$), gains \\$2\\$ (\\$B\\$) or loses \\$3\\$ (\\$C\\$). If Player 1 instead chooses \\$C\\$, then Player 2 either loses \\$2\\$ (\\$A\\$), loses \\$2\\$ (\\$B\\$) or gains \\$0\\$ (\\$C\\$). In either case, Player 2 would choose \\$B\\$ over \\$A\\$, as their result would never be worse when choosing \\$B\\$.

Therefore, we can say that \\$B\\$ **dominates** \\$A\\$, and we can remove \\$\text{Player 2 chooses A}\\$ from the matrix:

$$\begin{array}{c|c|c} & \text{Player 1 chooses A} & \text{Player 1 chooses C} \\ \hline \hline \text{Player 2 chooses B} & -2 & 2 \\ \hline \text{Player 2 chooses C} & 3 & 0 \\ \end{array}$$

Here however, no more choices dominate. This is our final matrix, and would be the output for this input.

---

You are to take a rectangular matrix \\$n\times m\\$, where \\$n, m \ge 2\\$, and output the same matrix with all dominated options removed. You may also take the matrix transposed and/or with reversed signs from the examples provided in the question.

The matrices will only contain integers between \\$-9\\$ and \\$9\\$ (inclusive). You may also take \\$n\\$ and/or \\$m\\$ as input if you wish. The matrix is not guaranteed to contain any dominated options. The matrix may be reduced to a \\$1\times1\\$ matrix, at which point there are no more dominated options.

You may input and output in any convenient format. If there is more than one valid output, you may output any valid one. This is so the shortest code in bytes wins.

## Test cases

Done by hand, don't hesitate to point out mistakes or suggest more

```
Input
Output
Explanation

[[ 1  2  2]
 [-2  1  2]
 [ 3 -1  0]]
[[-2  2]
 [ 3  0]]
Column C dominates Column B, Row B dominates Row A

[[ 2  1  3  3]
 [ 0  0 -1  0]
 [ 1  1  0  0]]
[[0]]
Column A dominates B, Column D dominates C, Row B dominates Rows A+C, Column B dominates Column D (or vice versa)

[[ 2  0  4  1  2]
 [-1  6  0 -3  3]
 [ 0 -2  1 -1  1]
 [ 4 -2  1  2  3]]
[[1]]
Column E dominates Column D, Row C dominates Row D, Column E dominates Column A, Row C dominates Row A, Column E dominates Column E, Row C dominates Row B, Column E dominates Column B

[[ 7 -3 -5 -9 -8 -2]
 [ 6  7  6 -1  2  0]
 [-5 -8  3 -1 -8 -8]
 [-8  8  1  0  9 -2]
 [-3  0 -1 -4  8  1]
 [-2  2 -4  3 -7 -2]
 [ 4  8  1  8 -9 -9]
 [-1 -6 -4  1  9  5]]
[[ 7 -3 -5 -9 -8 -2]
 [-5 -8  3 -1 -8 -8]
 [-8  8  1  0  9 -2]
 [-3  0 -1 -4  8  1]
 [-2  2 -4  3 -7 -2]
 [ 4  8  1  8 -9 -9]
 [-1 -6 -4  1  9  5]]
Row C dominates Row B

[[  4 -6  2  ]
 [ -2 -5 -9  ]
 [  6 -2 -2  ]
 [  8  0  7  ]
 [ -9  4  2  ]]
[[ 4 -6  2]
 [-2 -5 -9]
 [-9  4  2]]
Row C dominates Row D, Row B dominates Row C

[[ 9 -7]
 [ 2  4]]
[[ 9 -7]
 [ 2  4]]
No rows or columns dominate

[[ 2  2  2]
 [ 2  3  2]
 [ 2  2  2]]
[[2]]
 Column B dominates Columns A+C, Row A dominates Rows B+C

[[ 1  4]
 [ 2  0]
 [ 1  4]]
[[ 2  0]  or [[ 1  4]
 [ 1  4]]     [ 2  0]]
 Rows A and C are equal so we remove one of them. Either output is OK, but removing both rows isn't.

```

Note that for the 7th test case, there are many different ways to get to the final version

# Answer
# , 43 41 40 39 bytes

```
f=.(#~1=1#.]*/ .>:|:)@~.
f&.:-&.|:@f^:_

```

Try it online!

## tldr how

Create a function `f` to filter out dominated rows.

Apply plain `f`, followed by `f` "under" a negative transpose, until we reach a fixed point.
> 5 votes

# Answer
# Jelly,  ~~22~~  21 bytes

```
Qµ>Ạ€TLʋ€’ỊTịNZ
Ç⁺$ƬṪ

```

**Try it online!** Or see the test-suite.

### How?

```
Ç⁺$ƬṪ - Link: matrix
   Ƭ  - collect up inputs to this until no change:
  $   -   last two links as a monad:
Ç     -     call Link 1 (see below)
 ⁺    -     repeat that
    Ṫ - tail

Qµ>Ạ€TLʋ€’ỊTịNZ - Link 1: matrix
Q               - de-duplicate (since one of any repeats wants keeping)
 µ              - start a new monadic chain, call that X
         ’      - with a decremented version of X, say Z, on the right:
       ʋ€       -   for each row in X:
  >             -     (row) greater than (Z) (vectorises)
   Ạ€           -     for each comparison: all truthy?
     T          -     truthy indices (i.e. indices in X which dominate row,
                                      including the index of row itself)
      L         -     length
          Ị     - insignificant? (vectorises) (i.e. 1 if no other row dominates, else 0)
           T    - truthy indices
            ị   - index into:
             N  -   negated (X)
              Z - transpose

```

---

As a single Link (21):
`Qµ>Ạ€TLʋ€’ỊTịNZµ$⁺$ƬṪ`
...or:
`Qµ>Ạ€TLʋ€’ỊTịNZµ$Ƭm2Ṫ`
> 4 votes

# Answer
# Haskell, ~~106~~ ~~101~~ 100 bytes

* -5 bytes thanks to kops.

```
until=<<((==)<*>)$g.g
g m=transpose.map(map(0-))$nub m\\(m>>=tail.mapM(\i->[i..9]))
import Data.List

```

Try it online!

The relevant function is `until=<<((==)<*>)$g.g`, which takes as input a matrix in the format described in the statement (not transposed and without flipped signs).

Very slow, but hey, we are codegolfing! See below for a (much) more efficient version.

## How?

Most of the work is done by `g`. This function takes a matrix `m` as input and returns the matrix obtained after "half an operation". To be more specific, `g` takes `m`, removes dominated rows, then transposes `m` and flips all the signs. These last two operations are basically equivalent to swapping the roles of Player 1 and Player 2. It's not hard to see that applying `g` twice performs a full iteration: dominated rows and columns are removed, the two transpositions cancel out, and so do the two sign flipping. Let's now look at the code.

```
g m=                            -- the function g takes a matrix m and returns
    transpose.                  -- the transpose of
    map(map(0-))$               -- the matrix obtained by flipping the signs of
    nub m                       --   m with duplicate rows removed
    \\(                         --   to which we also remove
        m>>=                    --   any row obtained by taking a row of m (say r)
            tail.               --   and taking any but the first
            mapM(               --   list whose j-th entry
                \i->[i..9]))    --   lies between i and 9 (where i is the j-th entry of r)

```

`nub m` yields `m` with duplicate rows deleted; this is necessary since otherwise duplicate rows could potentially stick around forever. `m>>=tail.mapM(\i->[i..9])` basically generates a list of all the possible rows (strictly) dominated by some row of `m` (this is obviously the slow part, since there can be up to \\$\approx m\cdot19^n\\$ such rows).

---

The anonymous function `until=<<((==)<*>)$g.g` (courtesy of kops) iterates `g.g` until the resulting matrix stops changing.

# Haskell, ~~107~~ ~~102~~ 101 bytes, much faster

* -5 bytes thanks to kops.

```
    until=<<((==)<*>)$g.g
    g m=transpose[(0-)<$>r|r<-nub m,all(or.zipWith(<)r)$m\\(r<$m)]
    import Data.List

```

Try it online!
> 3 votes

# Answer
# Charcoal, 40 bytes

```
Ｆ⊗Ｌ⁺θ§θ⁰≔Ｅ§θ⁰±ＥΦθ⬤θ⎇⁼μξ¬›νπ⊙μ‹ρ§ξς§μλθＩθ

```

Try it online! Link is to verbose version of code. Outputs using Charcoal's default format (each cell on its own line with rows double-spaced from each other). Explanation:

```
Ｆ⊗Ｌ⁺θ§θ⁰

```

Loop a large enough number of times (twice the number of rows and columns; probably overkill, so 4 bytes could be saved if this is the case).

```
Φθ⬤θ⎇⁼μξ¬›νπ⊙μ‹ρ§ξς

```

Keep rows which, for each row, have at least one cell less than the corresponding cell from the other row, unless the two rows are equal, in which case keep the first of the duplicates.

```
≔Ｅ§θ⁰±Ｅ...§μλθ

```

Transpose and negate the filtered matrix. (Actually to save bytes the matrix is filtered for each column of the transpose. Fortunately this doesn't result in enough nesting to trouble the buggy deverbosifier on the version of Charcoal currently on TIO.)

```
Ｉθ

```

Output the remaining matrix.
> 1 votes

# Answer
# Ruby, ~~112 ...~~ 102 bytes

```
->m{1until m==[:min,:max].map{|x|m=m.transpose|[];m-=m.combination(2).map{|a,b|a.zip(b).map &x}}[1];m}

```

Try it online!
> 1 votes

---
Tags: code-golf, integer, matrix
---


title: Spanish Verb Conjugator

text:
# Question
Title: Spanish Verb Conjugator
## Explanation

¡Hola! For those of you who don't take Spanish, a verb is conjugated based on the person who does the action. Here's a chart:

```
English                   Spanish
I                         Yo
You                       Tú
He                        Él
She                       Ella
You (formal)              Usted
We all                    Nosotros
You all                   Vosotros
They (masculine, plural)  Ellos
They (feminine, plural)   Ellas
You (plural)              Ustedes

```

In Spanish, all verbs end with `ar`, `er`, or `ir`. Here's another helpful chart:

```
          Ar    Er    Ir
Yo        o     o     o
Tú        as    es    es
Él        a     e     e
Ella      a     e     e
Usted     a     e     e
Nosotros  amos emos imos
Vosotros  áis  éis  ís
Ellos     an   en   en
Ellas     an   en   en
Ustedes   an   en   en

```

## Challenge

Given a pronoun and an unconjugated verb, **write the shortest program or function** that outputs the verb conjugated for the pronoun in the present tense.

Conjugations are given in the tables above, where it is a process of replacing the `ar/er/ir` ending with its respective conjugated ending.

You do not need to worry about accented output (i.e. "Vosotros" verbs can be conjugated as `ais eis is`). You also do not need to worry about stem changing and irregular verbs.

---

## Examples

```
Input        Output
Yo escribir  Escribo
Tu enseñar   Enseñas
Ella querer  Quere (It should be quiere but ignore stem changes)

```

You can find more words with which to test here: http://spanish.speak7.com/spanish\_vocabulary\_verbs.htm. Note that contester should be contestar.

---

## Challenge: Stem Changes

In Spanish, some verbs have stem changes. Let's take the verb `querer` for example. In all forms *except nosotros and vosotros*, the first `e` changes to `ie`. So, `yo quiero`, but `nosotros queremos`.

**If your program can account for stem changes, you may subtract twice the length of each word you support from your final score**.

For example, if you support the `i` -\> `ie` change `querer` and only `querer`, you can subtract twice the length of `querer`, or 12, from your score.

For some stem-changing verbs, try this: https://conjuguemos.com/chart.php?language=spanish&id=2&etre=no&commands=no&all=no&source=public

---

(As I am not a native Spanish speaker, please correct me on any mistakes)

# Answer
> 3 votes
# Python, ~~172~~ ~~168~~ 743 characters - 1796 bonus = -1053

Updated to take the stem-changing challenge.

```
p,v=raw_input().split()
y="aee";z=y+'n'
x=["ooo",y+'s',y,y,y,"aeimos","ae\x00is",z,z]["YoTuElEaUdNsVsEsUs".index(p[0]+p[-1])/2]
s=v[:-2]
X=v='eJw1UuHS5CAIe1aqrNsZhR6w/tj5Hv4Sv7uODRYDxEzlylKTplHS3xrS/3yIm4kntCTVSipkazaZ\n+AA32h3tY1ut+VL7NreXxsEEsgSheGynlJv/GNVvsPs9CIl2hoCSV+gYfuH7rdAyIQdr3+x92yCg\n2g7WEp4vMfTKgogyHabbL4z1l1p/1PLBCF4o9AjtmJBc6wpOTJykM+O0Ib2Y+FyCAuv5wcwCd+Ks\n4+XCdSwhqMIf/eJOFPMjV/rc0jw6IEvm8vjKdBuy/JryMPmEXwIiDInhtK01n1iDPrGu6/A5uy4/\nkBVd89R1OjvHCXbSnoDyaB23nhseElHosf45rzYC1zOevyDojQ548fjGCGg8M5aD8EAmB9GqgFHk\nBzRwDwJ6EcgK5aSDZ2/4TSAjKOMXd3gPh6sTq/+GApG0wkSYdzSBz/AXclUQ+g=='.decode('base64').decode('zip')
if s in X:
 j=X.index(s)<326
 s=(s.replace('oe'[j],'ui'[j]+'e'),s)[p[0]in'NV']
print s+x["aei".index(v[-2])]+x[3:]

```

**Usage**:

```
$ echo "Ellas querer" | python conj_golf2.py
quieren

```

**Test on non-stem-changing inputs**:

```
Yo ensenar -> enseno
Yo escribir -> escribo
Tu ensenar -> ensenas
Tu escribir -> escribes
El ensenar -> ensena
El escribir -> escribe
Ella ensenar -> ensena
Ella escribir -> escribe
Usted ensenar -> ensena
Usted escribir -> escribe
Nosotros ensenar -> ensenamos
Nosotros escribir -> escribimos
Vosotros ensenar -> ensenais
Vosotros escribir -> escribis
Ellos ensenar -> ensenan
Ellos escribir -> escriben
Ellas ensenar -> ensenan
Ellas escribir -> escriben
Ustedes ensenar -> ensenan
Ustedes escribir -> escriben

```

**Stem-changing input examples**:

It does both e-\>ie changes and o-\>ue changes, properly avoiding the nostros + vostros cases:

```
$ echo "Yo abstenir"|python conj_golf2.py
abstieno
$ echo "Nostros abstenir"|python conj_golf2.py
abstenimos
$ echo "Tu almorzar"|python conj_golf2.py
almuerzas
$ echo "Vostros almorzar"|python conj_golf2.py
almorzais

```

Here is how the bonus was determined and the data string generated, from which you can deduce the verbs on which it works:

```
e="absten.acert.adher.adquer.advert.apret.asent.atraves.calent.cerr."+\
  "circunven.comenz.confer.confes.consent.conten.contraven.conven.convert."+\
  "difer.diger.discern.disent.freg.gobern.hed.hel.her.herv.infer.inger."+\
  "invern.invert.malher.manifest.ment.neg.nev.obten.ofend.pens.perd."+\
  "quer.recomend.reg.seg.sembr.sent.serr.sosegsosten.soterr.subarrend."+\
  "suger.tembl.tend.ten.tent.transfer.tropez.ven.vert"

u="absolv.acord.acost.almorz.along.amobl.apost.aprob.asol.avergonz."+\
  "coc.col.colg.cont.cost.degoll.demol.demostr.desaprob.descolg.descontr."+\
  "desos.destorc.devolv.disolv.dol.dorm.encontr.engros.envolv.forz.holg."+\
  "holl.llov.mol.mor.mostr.mov.ol.pobl.prob.record.reforz.remord.remov.renov."+\
  "repobl.resolv.resoll.reson.retorc.revolc.revolv."+\
  "rod.rog.sol.sold.sol.solt.son.torc.tost.tron.vol.volc.volv"

words = e.split(".") + u.split(".")
bonus = 0
for word in words:
    bonus += (len(word)+2)*2
print "Bonus: %d from %d stem-changing verbs" % (bonus, len(words))

s=(e+"|"+u).replace(".","")
zipped = s.encode('zip')
b64 = zipped.encode('base64')
print "The separator is at index %d" % s.index("|")
print "Uncompressed: %d chars, %d repr" % (len(s), len(`s`))
print "Compressed: %d chars, %d repr" % (len(zipped), len(`zipped`))
print "Comp+B64: %d chars, %d repr" % (len(b64), len(`b64`))

print "v="+`b64`

```

Which gives:

```
$ python conj_help.py
Bonus: 1796 from 127 stem-changing verbs
The separator is at index 326
Uncompressed: 645 chars, 647 repr
Compressed: 331 chars, 1015 repr
Comp+B64: 450 chars, 458 repr
v='eJw1UuHS5CAIe1aqrNsZhR6w/tj5Hv4Sv7uODRYDxEzlylKTplHS3xrS/3yIm4kntCTVSipkazaZ\n+AA32h3tY1ut+VL7NreXxsEEsgSheGynlJv/GNVvsPs9CIl2hoCSV+gYfuH7rdAyIQdr3+x92yCg\n2g7WEp4vMfTKgogyHabbL4z1l1p/1PLBCF4o9AjtmJBc6wpOTJykM+O0Ib2Y+FyCAuv5wcwCd+Ks\n4+XCdSwhqMIf/eJOFPMjV/rc0jw6IEvm8vjKdBuy/JryMPmEXwIiDInhtK01n1iDPrGu6/A5uy4/\nkBVd89R1OjvHCXbSnoDyaB23nhseElHosf45rzYC1zOevyDojQ548fjGCGg8M5aD8EAmB9GqgFHk\nBzRwDwJ6EcgK5aSDZ2/4TSAjKOMXd3gPh6sTq/+GApG0wkSYdzSBz/AXclUQ+g==\n'

```

# Answer
> 3 votes
# Python, 240 bytes - (extremely large) bonus

```
from re import*;import urllib2 as u,sys;x=sys.argv
try:
 print search('>.*?'+sub('a','o',sub('ella','el',x[1]))+'.*? ([^<]*)',sub(u'\u00e9','e',sub(u'\u00fa','u',u.urlopen("http://smarturl.it/xz?word="+x[2]).read()))).group(1)
except:
 pass

```

Sample Output:

```
Input         | Output
yo escribir   | escribo
tu escribir   | escribes
tu ensenar    | ensenas
ella querer   | quiere
ellas querer  | quieren
nosotros vive | vi
tu acordar    | acuerdas

```

Explanation:

This code uses an existing free conjugation website (http://www.conjugation.org/) that returns various conjugations from a large database of verbs. I reduced the URL slightly by using a free online URL shortener that allows parameters to be passed through the redirection (http://smarturl.it/). I simply make a HTTP request based on the verb specified, remove the accents from the `u` and `e` in the source, find the pronoun in the HTML using regular expressions, then return associated conjugation.

It's impossible to tell how many verbs have stem changes without polling the entire database against a dictionary. It's probably safe to assume the negative bonus from this database is much larger than any bonus from encoded lists passed in (which increase the length of the code).

I could obviously have handled the accented characters better, but it would've required encode/decode and extra handling within the regular expressions.

# Answer
> 2 votes
# Freepascal, 218 chars -30 = 189

It's a tough call to beat the (original) python answer, especially with Pascal. I may try and improve tomorrow, possibly with a similar concept in a different language. I will not be submitting a stem-changing answer, as I see this as a linguistic rather than programming challenge.

```
var y,p,v:string;BEGIN y:='amosemosimosais eis is  as  eso eso   o   an  en  en';readln(p);readln(v);writeln(copy(v,1,length(v)-2),copy(y,6*(7-pos(p[1],' yt v n'))+pos(v[length(v)-1],y),pos(p[length(p)],'u s')+1));END.

```

Ungolfed version:

```
var y,p,v:string;
BEGIN
  y:='amosemosimosais eis is  as  eso eso   o   an  en  en';
  readln(p);readln(v);
  writeln(copy(v,1,length(v)-2),
  copy(y,6*(7-pos(p[1],' yt v n'))+pos(v[length(v)-1],y),pos(p[length(p)],'u s')+1));
END.

```

**Explicación (In Spanish for the -30 bonus since you asked)**

el primer `copy` extrae la raíz del verbo, teniendo como parámetros el *string*, el indice para empezar (en este caso 1) y la cantidad de letras (en este caso *length-2.*) El segundo extrae su desinencia.

`6*(7-pos(p[1],' yt v n')` se evalúa según la primera letra del pronombre. Si el pronombre es él/ella(o/s) o usted(es),`pos` se evalúa a cero, así que el valor dentro de los paréntesis es 7. `pos(v[length(v)-1],y` busca la penúltima letra del infinitivo en `amosemosimos` así que avanza 4 por cada tipo de verbo, formando un ciclo de 12. El resto de `y` consiste en todas las desinencias. Se ha logrado intercalar parcialmente las desinencias para "tu" y "yo." Sin embargo queda cierta cantidad de espacio en blanco que me gustaría eliminar. Así se define el indice para buscar la desinencia en y.

`pos(p[length(p)],'u s')+1)` determina el numero de caracteres para imprimir. si el pronombre no termina en `s` o `u` solo se imprime un cáracter. De esta manera suprimimos la segunda letra de `an en en` en el caso de un pronombre de tercera persona singular: él, ella, usted.

**Output**

# Answer
> 2 votes
# JavaScript (V8), 191 bytes

```
p=>v=>v.replace(/.r$/,e=>({"Yo":"o","Él":x=e[0]=="a"?"a":"e","Tú":x+"s","Ea":x,"Ud":x,"Ns":e[0]+"mos","Vs":({"a":"áis","e":"éis","i":"ís"})[e[0]],"Es":n=x+"n","Us":n})[p[0]+p.slice(-1)])

```

# Answer
> 1 votes
# perl, 155 chars

Just a bunch of regular expressions this time. You can get shorter code by rearranging things slightly so that the pronoun comes after the verb, since we only really care about the end of the verb:

```
$_=<>;s/(.+) (.*)(.)r/$2$3 $1/;s/. yo/o/||s/ tú/s/||s/ n.*/mos/||s/ v.*/is/||s/ .*s$/n/||s/ .*//;s/i(n?)$/e$1/;s/ais$/áis/;s/eis$/éis/;s/iis$/ís/;print

```

Seems like the above is currently the winner of code that ignores the bonus.

```
ski@anito:~$ c='$_=<>;s/(.+) (.*)(.)r/$2$3 $1/;s/. yo/o/||s/ tú/s/||s/ n.*/mos/||s/ v.*/is/||s/ .*s$/n/||s/ .*$//;s/i(n?)$/e$1/;s/ais$/áis/;s/eis$/éis/;s/iis$/ís/;print'; for p in yo tú él ella usted ellos ellas ustedes vosotros nosotros ; do for v in mar mer mir ; do echo "$p $v" | perl -e "$c" ; done ; done ; echo -n "$c" | wc -c
mo
mo
mo
mas
mes
mis
ma
me
me
ma
me
me
ma
me
me
man
men
men
man
men
men
man
men
men
máis
méis
mís
mamos
memos
mimos
155

```

# Answer
> 1 votes
# perl, 243 chars

This time focusing on hash lookup. I'm fairly surprised I couldn't get this smaller.

```
$_=<>;s/^(ustede|ell[oa])s\b/x/;s/^(él|ella|usted)\b/w/;%t=(yo,[o,o,o],"tú",[es,as,es],w,[e,a,e],x,[en,an,en],nosotros,[imos,amos,emos],vosotros,[qw(ís áis éis)]);@t=keys%t;$"="|";s/^(@t)\s+(\S*)([aei])r$/$2.$t{$1}[ord($3)%3]/e||die;print

```

And if input validation isn't important, 186 chars:

```
$_=<>;s/^[ue].*s /x /;s/^[éeu].* /w /;%_=(y=>[o,o,o],t,[es,as,es],w,[e,a,e],x,[en,an,en],n,[imos,amos,emos],v,[qw(ís áis éis)]);s/^(.)\S*\s+(.*)([aei])r$/$2.$_{$1}[ord($3)%3]/e;print

```

# Answer
> 1 votes
# Bash, 301 ~~309 (bugfix)~~ ~~307~~ 299 including new lines

Not great compared to the other ones out there. Could be improved.

It exploits some convenient coincidences.

The bugfix relies on no Spanish verb having "ii" anywhere, due to the way it saves characters when handling vosotros with -ir verbs. Please correct me if that's wrong.

Assumes valid input: first argument is the lower case pronoun, with any necessary accents; second argument is the infinitive of the verb. No stem changes implemented. Outputs the conjugated verb, in lower case, without accents.

```
e=`tail -c3<<<$2`
f=`echo ${e:0:-1}`
s=`echo ${2:0:-2}`
if [ $1 = yo ];then o="$s"o;elif [ $1 = nosotros ];then o="$s$f"mos;elif [ $1 = vosotros ];then o="$s$f"is;else
if [ $f = i ];then f=e;fi
if [ $1 = tú ];then
o="$s$f"s;elif [ `tail -c2<<<$1` = s ];then
o="$s$f"n;else o=$s$f;fi
fi
tr -s i<<<$o

```

Explained. \` \` is an obscure notation for `$( )`, saving one char.

```
e=`tail -c3<<<$2`

```

get the verb ending

```
f=`echo ${e:0:-1}`

```

get the first char of the verb ending

```
s=`echo ${2:0:-2}`

```

get the verb stem

```
if [ $1 = yo ]; then
o="$s"o;

```

Verb stem+o. $o is our output

```
elif [ $1 = nosotros ]; then
o="$s$f"mos;

```

take stem+first letter of ending+mos

```
elif [ $1 = vosotros ]; then
o="$s$f"is;

```

stem+first letter of ending+is (no accents)

```
else
if [ $f = i ];then f=e;fi

```

in all scenarios except the two above, -ir verbs behave as -er verbs. change $f to e if it is i.

```
if [ $1 = tú ]; then
o="$s$f"s;

```

stem+$f+s

```
elif [ `tail -c2<<<$1` = s ]; then

```

if the last letter of the ending is s. this includes ellos, ellas, ustedes which all have the same endings. how convenient.

```
o="$s$f"n;

```

stem+$f+n

```
else o=$s$f;fi

```

we are assuming valid input, so the only other possibilities are Él, Ella and Usted, all with the same endings

```
fi
tr -s i <<< $0

```

print output, removing double i's (which appear when you use vosotros with an ir verb)

# Answer
> 0 votes
## Java – Too Long

I'm not even going to bother counting. If anyone would like to better golf this, please do. I'll eventually implement the stem-changing challenge.

```
public class Conjugator {

    public static void main(String[] args) {
        setup();
        String p = args[0].toLowerCase(), v = args[1];
        String e = v.substring(v.length() - 2);
        v = v.substring(0, v.length() - 2);
        String f = data.get(e).get(p);
        System.out.println(v + f);
    }

    static HashMap<String, HashMap<String, String>> data = new HashMap<String, HashMap<String, String>>();

    public static void add(String ending, String pronoun, String fin) {
        HashMap<String, String> hm = data.get(ending);
        if (hm == null) {
            hm = new HashMap<String, String>();
            hm.put(pronoun, fin);
            data.put(ending, hm);
            return;
        }
        hm = data.get(ending);
        hm.put(pronoun, fin);
    }

    public static void setup() {
        add("ar", "yo", "o");
        add("ar", "tu", "as");
        add("ar", "el/ella/usted", "a");
        add("ar", "nosotros", "amos");
        add("ar", "vosotros", "ais");
        add("ar", "ellos/ellas/ustedes", "an");

        add("er", "yo", "o");
        add("er", "tu", "es");
        add("er", "el/ella/usted", "e");
        add("er", "nosotros", "emos");
        add("er", "vosotros", "eis");
        add("er", "ellos/ellas/ustedes", "en");

        add("ir", "yo", "o");
        add("ir", "tu", "es");
        add("ir", "el/ella/usted", "e");
        add("ir", "nosotros", "imos");
        add("ir", "vosotros", "is");
        add("ir", "ellos/ellas/ustedes", "en");
    }
}

```

# Answer
> 0 votes
# perl, 298 characters

```
$_=<>;($p,$b,$x)=/^\s*(yo|tú|él|ellas?|ellos|usted|ustedes|[nv]osotros)\s+(\S*)([aei])r\s*$/;sub r{($z,$y)=@_;return if$p!~/^($z)/;if($p!~/ros$/){$x="e" if$x eq"i"}$x=""if$z eq yo;$x={qw(a áis e éis i ís)}->{$x}if$p=~/^v/;print"$b$x$y";exit}r yo,o;r t,"s";r"[eu].+s",n;r"[éeu]","";r n,mos;r v

```

or if we can throw caution to the wind and assume valid input, 246 chars:

```
$_=<>;($p,$b,$x)=/^(\S+)\s+(\S*)([aei])r$/;sub r{($z,$y)=@_;return if$p!~/^($z)/;if($p!~/ros$/){$x="e" if$x eq"i"}$x=""if$z eq yo;$x={qw(a áis e éis i ís)}->{$x}if$p=~/^v/;print"$b$x$y";exit}r yo,o;r t,"s";r"[eu].+s",n;r"[éeu]","";r n,mos;r v

```

test output:

```
ski@anito:~$ c='$_=<>;($p,$b,$x)=/^(\S+)\s+(\S*)([aei])r$/;sub r{($z,$y)=@_;return if$p!~/^($z)/;if($p!~/ros$/){$x="e" if$x eq"i"}$x=""if$z eq yo;$x={qw(a áis e éis i ís)}->{$x}if$p=~/^v/;print"$b$x$y";exit}r yo,o;r t,"s";r"[eu].+s",n;r"[éeu]","";r n,mos;r v'; for p in yo tú él ella usted ellos ellas ustedes vosotros nosotros ; do for v in mar mer mir ; do echo "$p $v" | perl -le "$c" ; done ; done ; echo -n "$c" | wc -c
mo
mo
mo
mas
mes
mes
ma
me
me
ma
me
me
ma
me
me
man
men
men
man
men
men
man
men
men
máis
méis
mís
mamos
memos
mimos
246

```

# Answer
> 0 votes
# JavaScript (Node.js), 195 bytes

```
(p,v)=>(x=v.charAt(v.length-2))&&(y=p.charAt(0))&&v.substring(0,v.length-2)+(p=='Yo'?'o':p.endsWith('ros')?x+(y=='N'?'mos':(x=='i'?'':'i')+'s'):(x=='i'?'e':x)+(y=='T'?'s':p.endsWith('s')?'n':''))

```

Try it online!

Doesn't handle the stem changes. It would cost a few more bytes to add the accents to the Vosotros form conjugations. If the input has accents, the output will include them. Also, it doesn't matter if accents are included in the pronouns or not; my program happens to ignore the characters that have accents on them.

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


title: Shift Tac Toe - Code Golf Challenge

text:
# Question
Title: Shift Tac Toe - Code Golf Challenge
## Shift Tac Toe

Shift Tac Toe is a game that combines Tic Tac Toe and Connect 4 together. In this game, you start with a 3 by 3 board, and each row is connected to a slider that you can move left and right. At the start, the sliders all start to the very right(this means that you can't move the slider to the right on the first turn). Each slider can hold a total of 5 pieces. Each turn, the player can drop an O or a X in one of the 3 columns of the Tic Tac Toe grid depending on which turn it is, or the player can move one of the sliders one spot to the left or to the right. All pieces fall to the bottom most space that is unoccupied. The pieces can also fall from one slider to another outside the 3 by 3 grid. If a piece is outside the 3 by 3 grid and doesn't fall into the bottom slider, then the piece is taken out. If it does reach the bottom slider, it will stay in play. A notable example of this is shown in the following grid:

```
     --- --- --- --- ---
    |   |   |   |   - O -
 --- --- --- --- --- ---
-   |   |   |   |   -
 --- --- --- --- --- ---
    |   |   |   |   -   -
     --- --- --- --- ---
In the grid above, the dashes(-) indicate the part of the sliders that are outside of the 3 by 3 grid and the vertical bars(|) indicate the 3 by 3 grid.
As you can see, this is the starting board except that the middle slider is one spot over to the left, and that there is an O at the very top right.
What happens in this scenario? There is nothing immediately underneath it, so does it go out of play?
No. This is because it still falls into the bottom slider, which means that it is still in play.

The final grid is this:
     --- --- --- --- ---
    |   |   |   |   -   -
 --- --- --- --- --- ---
-   |   |   |   |   -
 --- --- --- --- --- ---
    |   |   |   |   - O -
     --- --- --- --- ---

```

Pieces can also stack outside of the 3 by 3 grid. Players will alternate between O and X, with the O player going first.

## Example game:

```
Start with 3 by 3 grid with sliders all the way to the right:

 --- --- --- --- ---
|   |   |   |   -   -
 --- --- --- --- ---
|   |   |   |   -   -
 --- --- --- --- ---
|   |   |   |   -   -
 --- --- --- --- ---

The O player places an O in the middle column of the 3 by 3 grid and it falls to the bottom:

 --- --- --- --- ---
|   |   |   |   -   -
 --- --- --- --- ---
|   |   |   |   -   -
 --- --- --- --- ---
|   | O |   |   -   -
 --- --- --- --- ---

The X player then places an X in the middle column:

 --- --- --- --- ---
|   |   |   |   -   -
 --- --- --- --- ---
|   | X |   |   -   -
 --- --- --- --- ---
|   | O |   |   -   -
 --- --- --- --- ---

The O player then pushes the middle row slider one space to the left.
Notice that after the slider moves, there is nothing under the X anymore, so it falls down.
Also note that the slider has moved one space to the right as indicated below:

     --- --- --- --- ---
    |   |   |   |   -   -
 --- --- --- --- --- ---
-   |   |   |   |   -
 --- --- --- --- --- ---
    | X | O |   |   -   -
     --- --- --- --- ---

The X player places a X in the rightmost column:

     --- --- --- --- ---
    |   |   |   |   -   -
 --- --- --- --- --- ---
-   |   |   |   |   -
 --- --- --- --- --- ---
    | X | O | X |   -   -
     --- --- --- --- ---

The O player then moves the bottom slider one spot to the left.
Notice that all the pieces shift one place to the left, and the leftmost X is now out of the playing field:

     --- --- --- --- ---
    |   |   |   |   -   -
 --- --- --- --- --- ---
-   |   |   |   |   -
 --- --- --- --- ---
- X | O | X |   |   -
 --- --- --- --- ---

The X player places a X in the leftmost column:

     --- --- --- --- ---
    |   |   |   |   -   -
 --- --- --- --- --- ---
-   | X |   |   |   -
 --- --- --- --- ---
- X | O | X |   |   -
 --- --- --- --- ---

The O player places an O in the leftmost column:

     --- --- --- --- ---
    | O |   |   |   -   -
 --- --- --- --- --- ---
-   | X |   |   |   -
 --- --- --- --- ---
- X | O | X |   |   -
 --- --- --- --- ---

The X player shifts the top slider one place to the left. Notice that the O falls one place down because there is nothing beneath it:

 --- --- --- --- ---
-   |   |   |   |   -
 --- --- --- --- ---
- O | X |   |   |   -
 --- --- --- --- ---
- X | O | X |   |   -
 --- --- --- --- ---

The O player is not very good at this game, so he shifts the middle slider one place to the right.
This shifts all the pieces in the middle row one place to the right:

 --- --- --- --- ---
-   |   |   |   |   -
 --- --- --- --- --- ---
    | O | X |   |   -   -
 --- --- --- --- --- ---
- X | O | X |   |   -
 --- --- --- --- ---

The X player wins the game by placing a X in the middle column:

 --- --- --- --- ---
-   |   | X |   |   -
 --- --- --- --- --- ---
    | O | X |   |   -   -
 --- --- --- --- --- ---
- X | O | X |   |   -
 --- --- --- --- ---

```

Your job is to take in a string or array of any length that only consists of 9 unique characters(you choose the characters). Three of the characters will choose which column you place the X or O(depending on whose turn it is), three of them will choose which slider to move right, and the last three will choose which slider to move left. You can assume that the input only has these 9 characters. The output should be a 3 by 3 matrix or some kind of list/string that clearly shows the final position of the grid upon following the instructions of the input. You can assume that all inputs are valid. Each character takes up a turn. Also, if any move results in a winning move(forms 3 in a row in the 3 by 3 grid like regular Tic-Tac-Toe), then ignore the rest of the input. Note that the pieces that form the winning 3 in a row *all* have to be in the 3 by 3 grid. The two example grids below are NOT winning positions:

```
Grid #1:
 --- --- --- --- ---
|   |   |   |   -   -
 --- --- --- --- ---
|   |   |   |   -   -
 --- --- --- --- ---
|   |   | O | O - O -
 --- --- --- --- ---
This is not a winning move because two of the O's are outside the playing field, despite the fact that it forms a 3 in a row.
Using the character assignment stated below, this grid pattern can be achieved with 99372467643.

Grid #2:
 --- --- --- --- ---
|   |   |   |   - O -
 --- --- --- --- ---
|   |   |   | O - X -
 --- --- --- --- ---
|   |   | O | X - X -
 --- --- --- --- ---
This is not a winning position because two of the O's are outside the playing field.
Using the character assignment below, this grid pattern can be achieved with 939318836537734654

```

In the examples below, `1`, `2`, and `3` mean drop in the leftmost, middle, and rightmost column respectively. `4`, `5`, and `6` mean to move the top, middle, and bottom slider to the right respectively, and `7`, `8`, and `9` mean to move the top, middle, and bottom slider to the left respectively.

## Examples

```
Input will be in the form of a string
Output will be a list of lists, with each sub-list representing a row(I'm Python programmer so this list format might not be compatible with all languages).
The first, second, and third sub-list correspond to the top, middle, and bottom row of the 3 by 3 grid respectively.
The output will have 'O' for the O pieces, 'X' for the X pieces, and an empty string for empty spaces.

Input: 123332
Output:
[['','','O'],
 ['','X','X'],
 ['O','X','O']]

Input: 33387741347
Output:
[['','',''],
 ['','','O'],
 ['X','O','X']]

Input: 2283911752
Output:
[['','X',''],
 ['O','X',''],
 ['O','X','']]

Input: 228374739
Output:
[['','',''],
 ['','',''],
 ['X','X','X']]

Input: 8873334917349
Output:
[['','',''],
 ['','','O'],
 ['X','X','O']]

Input: 799333466
Output:
[['','',''],
 ['','',''],
 ['','','']]

Input: 99372467643
Output:
[['','',''],
 ['','',''],
 ['','','O']]

Input: 939318836537734654
Output:
[['','',''],
 ['','',''],
 ['','','O']]

```

This is , so shortest code wins!

# Answer
> 3 votes
# MATLAB, 727 Bytes

Try it online

```
b=nan(3,7);m=num2str(input(''));a=@(B)any(all(B)|all(B,2)'|all(diag(B))|all(diag(flip(B))));A=@(x,y)x(:,3:5)==y;n=@(x)isnan(x);
o=[1;1;1];
for i=1:numel(m)
t=1+mod(i,2);M=str2num(m(i));
switch M
case{1,2,3}
c=2+M;b(sum(n(b(:,c))),c)=t;case{4,5,6}
r=M-3;o(r)=o(r)+1;b(r,2:7)=b(r,1:6);b(r,1)=nan;case{7,8,9}
r=M-6;o(r)=o(r)-1;b(r,1:6)=b(r,2:7);b(r,7)=nan;end
r=o(3);
if r==1
b(:,[1,2])=nan;
elseif r==0
b(:,[1,7])=nan;
else
b(:,[6,7])=nan;
end
for j=1:7
d=n(b(:,j));e=sum(d);b(:,j)=[nan(e,1); b(~d,j)];
end
if r==1
b(:,[1,2])=nan;
elseif r==0
b(:,[1,7])=nan;
else
b(:,[6,7])=nan;
end
B=A(b,1);if a(B)
break
end
B=A(b,2);if a(B)
break
end
end
b(b==1)=79;b(b==2)=88;b(n(b))=0;disp(char(b(:,3:5)));

```

Explanation:

This challenge is a bit of a beast. First the user runs the program and inputs the moveset as either a single large number or a character array. For large numbers, due to numerical precision, a character array is required. I define a few often used functions that take up a lot of space so that they can be called with one character rather than a whole lot. Then I loop through each character in the input and use a switch statement to determine the move. 1-3 places the piece at the lowest available spot in the right column. 4-6 shift the row left and 7-9 shift it right. After, all invalid positions (outside the sliders) are removed automatically, as nothing could possibly stay there. Then, all columns are shifted so that things are settled as far down as they can go after 'falling'. Invalid positions are removed again in case a token fell onto another but was still outside a slider. The last thing to do is check the victory condition and break if it is found.

Overall, I had to chip my way out of a few sandtraps but I golfed as best I could. I'll take a triple bogey if no one else is fighting me for it.

---
Tags: code-golf, grid, tic-tac-toe
---


title: Truncate continued fractions

text:
# Question
Title: Truncate continued fractions
Related: Cleaning up decimal numbers

## Background

A **continued fraction** is a way to represent a real number as a sequence of integers in the following sense:

$$ x = a\_0 + \cfrac{1}{a\_1 + \cfrac{1}{a\_2 + \cfrac{1}{\ddots + \cfrac{1}{a\_n}}}} = \[a\_0; a\_1,a\_2,\cdots,a\_n\] $$

Finite continued fractions represent rational numbers; infinite continued fractions represent irrational numbers. This challenge will focus on finite ones for the sake of simplicity.

Let's take \\$\frac{277}{642}\\$ as an example. It has the following continued fraction:

$$ \frac{277}{642} = 0 + \cfrac{1}{2 + \cfrac{1}{3 + \cfrac{1}{6 + \cfrac{1}{1 + \cfrac{1}{3 + \cfrac{1}{3}}}}}} = \[0;2, 3, 6, 1, 3, 3\] $$

If we truncate the continued fraction at various places, we get various *approximations* of the number \\$\frac{277}{642}\\$:

$$ \begin{array}{c|c|c|c} \style{font-family:inherit}{\text{Continued Fraction}} & \style{font-family:inherit}{\text{Fraction}} & \style{font-family:inherit}{\text{Decimal}} & \style{font-family:inherit}{\text{Relative error}}\\\hline \[0\] & 0/1 & 0.0\dots & 1 \\\hline \[0;2\] & 1/2 & 0.50\dots & 0.15 \\\hline \[0;2,3\] & 3/7 & 0.428\dots & 0.0067 \\\hline \[0;2,3,6\] & 19/44 & 0.4318\dots & 0.00082 \\\hline \[0;2,3,6,1\] & 22/51 & 0.43137\dots & 0.00021 \\\hline \[0;2,3,6,1,3\] & 85/197 & 0.431472\dots & 0.000018 \\\hline \[0;2,3,6,1,3,3\] & 277/642 & 0.4314641\dots & 0 \end{array} $$

These are called *convergents* of the given number. In fact, the convergents are the *best approximations* among all fractions with the same or lower denominator. This property was used in a proposed machine number system of rational numbers to find the approximation that fits in a machine word of certain number of bits.

(There are some subtle points around "best approximation", but we will ignore it and just use the convergents. As a consequence, if your language/library has a "best rational approximation" built-in, it is unlikely to correctly solve the following task.)

## Task

Given a rational number \\$r\\$ given as a finite continued fraction and a positive integer \\$D\\$, find the best approximation of \\$r\\$ among its convergents so that its denominator does not exceed \\$D\\$.

The continued fraction is guaranteed to be a finite sequence of integers, where the first number is non-negative, and the rest are strictly positive. You may output the result as a built-in rational number or two separate integers. The output fraction does not need to be reduced.

Standard rules apply. The shortest code in bytes wins.

## Test cases

```
[0, 2, 3, 6, 1, 3, 3], 43 => 3/7
[0, 2, 3, 6, 1, 3, 3], 44 => 19/44
[5, 6, 7], 99 => 222/43

```

# Answer
> 8 votes
# JavaScript (ES6),  ~~72 68~~  67 bytes

Expects `(max_denominator)(seq)`. Returns `[numerator, denominator]`.

```
m=>g=([v,...a],n=0,d=1,N=1,D=0)=>(d+=D*v)<=m?g(a,N,D,N*v+n,d):[N,D]

```

Try it online!

### Commented

```
m =>             // outer function taking m = maximum denominator
g = (            // inner recursive function taking:
  [v,            //   v = next term from the continued fraction
      ...a],     //   a[] = remaining terms
  n = 0,         //   n = previous numerator
  d = 1,         //   d = previous denominator
  N = 1,         //   N = current numerator
  D = 0          //   D = current denominator
) =>             //
  (d += D * v)   // we compute the new denominator d = D * v + d
                 // this results in NaN if v is undefined,
                 // which forces the comparison to fail
  <= m ?         // if it's less than or equal to m:
    g(           //   do a recursive call:
      a,         //     pass the remaining terms of the continued fraction
      N, D,      //     pass the current numerator and denominator
      N * v + n, //     pass the new numerator
      d          //     pass the new denominator
    )            //   end of recursive call
  :              // else:
    [N, D]       //   we're done: return [N, D]

```

# Answer
> 4 votes
# , 25 23 bytes

```
(]{:@#~0#.>:)2 x:(+%)/\

```

Try it online!

-2 thanks to Bubbler

## how

We'll use `43 f 0, 2, 3, 6, 1, 3, 3x` as an example...

* `(+%)/\` For each prefix `\`, reduce from the right `/` using the J hook `(+%)`, which adds its left arg to the inverse of its right argument. This returns rational numbers:

```
0 1r2 3r7 19r44 22r51 85r197 277r642

```
* `2 x:` Convert to pairs:

```
0   1
1   2
3   7
19  44
22  51
85  197
277 642

```
* `]...#~...` Filter that list for valid denominators with the following mask:

+ `>:` Is each number less than or equal to the left arg:

    ```
    1 1
    1 1
    1 1
    1 0
    1 0
    0 0
    0 0

    ```
    + `0#.` Convert to a "base 0" number. This will be `1` only for pairs whose 2nd element (denominator) is `1`:

    ```
    1 1 1 0 0 0 0

    ```
* Our filtered list becomes:

```
0   1
1   2
3   7

```
* `{:@` Return the last element.

# Answer
> 4 votes
# Wolfram Language (Mathematica), 47 bytes

```
Last@*Cases[a_/;Denominator@a<=#]@*Convergents&

```

Try it online!

-25 bytes from @att

# Answer
> 3 votes
# Stax, 14 bytes

```
╪£pÇUßi⌂Ω♫M⌂░◘

```

Run and debug it

takes inputs as `<max denominator>,<continued fraction>`.

## Explanation

```
|[{r{su+km{Rn^<oH
|[{      m        for each prefix of the continued fraction
   r               reverse
    {   k          reduce by:
     su+            swap, reciprocal and add
          {    o  order by:
           R       denominator
            n^<    lesser than 2nd input + 1 ?
                H last element

```

# Answer
> 2 votes
# Charcoal, 38 bytes

```
ＦＬθ«≔⟦§θι¹⟧ζＦ⮌…θι≔⁺⁺⊟ζ×ζκζζ¿¬›§ζ¹ηＰ⪫ζ/

```

Try it online! Link is to verbose version of code. Explanation:

```
ＦＬθ«

```

Loop over the prefixes.

```
≔⟦§θι¹⟧ζ

```

Form a "fraction" of the current element.

```
Ｆ⮌…θι

```

Loop over the preceding elements.

```
≔⁺⁺⊟ζ×ζκζζ

```

Invert the fraction and add on the element. This is some decidedly tricky coding. The old denominator is popped from the fraction, leaving behind the old numerator as a list of one element. This is vectorised multiplied by the element and added to the denominator, thus making a list of just the new numerator. The old numerator, still in its list, is then list concatenated to it, where it becomes the new denominator.

```
¿¬›§ζ¹ηＰ⪫ζ/

```

If the denominator is still small enough, overprint the previous fraction (if any) with the current fraction.

# Answer
> 2 votes
# , ~~88~~ 80 bytes

```
function(x,y,`~`=cbind,z=1:0~0:1){for(i in x)z=z[,1]*i+z[,2]~z;z[,z[2,]<=y][,1]}

```

Try it online!

# Answer
> 1 votes
# Python 3, 162 bytes

```
lambda x,y:min((abs(q-g(*x)),q)for q in[g(*x[:i+1])for i in range(len(x))]if q.denominator<=y)[1]
g=lambda v,*k:v+Fraction(*k and(1,g(*k)))
from fractions import*

```

Try it online!

-28 bytes thanks to ovs

# Answer
> 1 votes
# Haskell, ~~70~~ 69 bytes

```
x?m=last[y|y<-f x,y!!1<=m]
f(h:t)=[h,1]:[[a*h+b,a]|[a,b]<-f t]
f[]=[]

```

Try it online!

The relevant function is `(?)`, which takes as input the continued fraction `x` (as a list of integers) and the maximum denominator `m`. The output is a list of integers `[numerator,denominator]`.

## How?

```
x?m=            -- x=continued fraction, y=maximum denominator
  last[         -- return the last
    y|y<-f x,   --   convergent of x
    y!!1        --   whose denominator (i.e. second element)
      <=m       --     is at most m
  ]

```

```
f                   -- helper function for computing convergents
  (h:t)=            --   h=first number, t=rest of the continued fraction
    [h,1]:          --     the first convergent is h (i.e. h/1)
    [[a*h+b,a]      --     the other convergents are h+b/a (i.e. (a*h+b)/a)
      |[a,b]<-f t]  --       where a/b ranges over the convergents of t
f[]=[]              -- base case for the empty continued fraction

```

# Answer
> 1 votes
# Retina, 74 bytes

```
,
¶$%`,
¶
/1¶
+`\d+,(\d+)/(.+)
$.($2*_$1**)/$1
N$r`.*(\d+)
$1
L`.+¶(?!.+/)

```

Try it online! Takes the continued fraction and denominator on separate lines, but link includes test suite that splits on `;` for convenience. Explanation:

```
,
¶$%`,

```

Get all prefixes of the continued fraction.

```
¶
/1¶

```

Start each prefix with a denominator of 1.

```
+`\d+,(\d+)/(.+)
$.($2*_$1**)/$1

```

Calculate each resulting rational number from right to left.

```
N$r`.*(\d+)
$1

```

Sort the desired denominator into the list of rational numbers.

```
L`.+¶(?!.+/)

```

Output the rational number whose denominator is the largest that does not exceed the desired denominator.

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


title: Solve the knapsack problem

text:
# Question
Title: Solve the knapsack problem
## Knapsack Problem

(Actually, this is a **subset of real knapsack problem**.... - there's nothing to optimize!)

The knapsack problem is:

> Given positive integers , and an integer S, find non-negative integers satisfies

... or in (my bad) English...

> Suppose you have many stuffs which weights , find configurations of those stuffs which weights S.

## Problem

> Find **all** configurations of stuffs, which information is given by input.

## Input

You can make your own format, but you should enable users to input **the sum of stuffs(S)**, **weights of stuffs , and names of each stuffs**.

Stuffs' name may contain `[a-zA-Z0-9 _]` (alphanumeric + `_` \+ space).

You may assume that the input is correct, are positive, and S is non-negative.

For example, consider this pseudo-real world situation, where a man orders appetizers worth exactly $15.05:

A possible input is:

```
1505
215 Mixed fruit
275 French fries
335 Side salad
355 Hot wings
420 Mozzarella sticks
580 Sampler plate

```

## Output

Print all possible configurations (no same configurations, one configuration per one line, each line contains pairs of amount of a stuff and name of the stuff).

Stuff with zero amount can be omitted.

If there's no configuration possible, simply print `X`.

## Example

Input and output format (and order) can be vary.

This is JS code I made roughly:

```
var s=prompt(),a=s.split('/'),b=[],c,i=1,t=a[0];while(i<a.length){c=a[i].split(/^([^ ]*) /);c.shift();b.push(c);i++;}
var d=[],l=b.length,p=0,_=0;for(i=0;i<l;i++)d[i]=0;
function as(x,y){for(var i=0,s=0;i<x.length;i++)s+=x[i][0]*y[i];return s}
function cs(x,y){for(var i=0,s='';i<x.length;i++)s+=y[i]+' '+x[i][1]+', ';return s}
while(p>=0){
    p=0;
    while((q=as(b,d))>=t){
        if(q==t){console.log(cs(b,d));_=1}
        d[p]=0;p++;if(p>=l){p=-1;break;}
        d[p]++;
    }
    if(p==0) d[0]++;
}
if(!_) console.log('X');

```

---

Input

`1505/215 Mixed fruit/275 French fries/335 Side salad/355 Hot wings/420 Mozzarella sticks/580 Sampler plate`

Output

```
7 Mixed fruit, 0 French fries, 0 Side salad, 0 Hot wings, 0 Mozzarella sticks, 0 Sampler plate,
1 Mixed fruit, 0 French fries, 0 Side salad, 2 Hot wings, 0 Mozzarella sticks, 1 Sampler plate,

```

---

Input

`5/1 A/1 B/1 C`

Output

```
5 A, 0 B, 0 C,
4 A, 1 B, 0 C,
3 A, 2 B, 0 C,
2 A, 3 B, 0 C,
1 A, 4 B, 0 C,
0 A, 5 B, 0 C,
4 A, 0 B, 1 C,
3 A, 1 B, 1 C,
2 A, 2 B, 1 C,
1 A, 3 B, 1 C,
0 A, 4 B, 1 C,
3 A, 0 B, 2 C,
2 A, 1 B, 2 C,
1 A, 2 B, 2 C,
0 A, 3 B, 2 C,
2 A, 0 B, 3 C,
1 A, 1 B, 3 C,
0 A, 2 B, 3 C,
1 A, 0 B, 4 C,
0 A, 1 B, 4 C,
0 A, 0 B, 5 C,

```

---

Input

`10/20 A/11 B`

Output

`X`

---

Input

`250/35 Portal 2/21 Minecraft/12 Braid`

Output

```
5 Portal 2, 3 Minecraft, 1 Braid,
2 Portal 2, 8 Minecraft, 1 Braid,
2 Portal 2, 4 Minecraft, 8 Braid,
2 Portal 2, 0 Minecraft, 15 Braid,

```

Input

`250/33 Portal 2/21 Minecraft/12 Braid`

Output

`X`

---

## Winner

Since this is the code golf game, person with shortest code win.

If two codes have same length, then a code with highest votes win.

# Answer
> 1 votes
## Python, 185 chars

```
S,C,N=input()
R=range(len(C))
F=lambda i,w:sum([[x+[j]for x in F(j,w-C[j])]for j in R[i:]],[])if w>0 else[[]][w<0:]
for L in F(0,S):print[(L.count(i),N[i])for i in R];S=0
if S:print'X'

```

run it with input like this:

```
echo "[1505,[215,275,335,355,420,580],['MF','FF','SS','HW','MS','SP']]" | ./knapsack.py

```

which encodes S, a list of costs, and a list of item names corresponding to those costs.

It outputs list of item counts and item names:

```
[(7, 'MF'), (0, 'FF'), (0, 'SS'), (0, 'HW'), (0, 'MS'), (0, 'SP')]
[(1, 'MF'), (0, 'FF'), (0, 'SS'), (2, 'HW'), (0, 'MS'), (1, 'SP')]

```

# Answer
> 3 votes
# Mathematica, 59 chars

```
Tally/@IntegerPartitions[#1,All,#2/._[x_,_]->x]/.#2/.{}->X&

```

Invoke with

```
%[1505, {215 -> "MF", 275 -> "FF", 335 -> "SS", 355 -> "HW", 420 -> "MS", 580 -> "SP"}]

```

# Answer
> 0 votes
### Ruby, 136 characters

```
a,*b=*$<
c=->s,u,e{f,*r=e;f ?(0..s/h=f.to_i).map{|n|c[s-n*h,u+[n.to_s+f[/ .*/]],r]}:s>0?[]:u*?,}
r=c[a.to_i,[],b].flatten
puts r[0]?r:?X

```

Input must be given on STDIN, one line for the total amount and then one line per item (weight, followed by space, followed by name).

Example input:

```
250
35 Portal 2
21 Minecraft
12 Braid

```

Output:

```
2 Portal 2,0 Minecraft,15 Braid
2 Portal 2,4 Minecraft,8 Braid
2 Portal 2,8 Minecraft,1 Braid
5 Portal 2,3 Minecraft,1 Braid

```

# Answer
> 0 votes
### Python, 356 characters

I took a slight hit for reading from the command line:

```
from sys import argv
x=int(argv[1])
t=argv[3::2]
c=argv[2::2]
n=len(t)
s=[0]*n
d=1
g=1
while d:
    i=0
    s[i]+=1
    while int(c[i])*s[i]>x:
        s[i]=0
        if i+1>=n:
            d=0
        else:
            i+=1
            s[i]+=1
    if d and sum(map(lambda y:int(c[y])*s[y],range(n)))==x:
        g=0
        print zip(t, s)
if g:print"X"

```

Example input:

```
python stuff.py 1505 215 'Mixed fruit' 275 'French fries' 335 'Side salad' 355 'Hot wings' 420 'Mozzarella sticks' 580 'Sampler plate'

```

Output:

```
[('Mixed fruit', 7), ('French fries', 0), ('Side salad', 0), ('Hot wings', 0), ('Mozzarella sticks', 0), ('Sampler plate', 0)]
[('Mixed fruit', 1), ('French fries', 0), ('Side salad', 0), ('Hot wings', 2), ('Mozzarella sticks', 0), ('Sampler plate', 1)]

```

# Answer
> 0 votes
# JavaScript (V8), 225 bytes

```
(t,k,l,a=d=0)=>[...Array(t+1)].flatMap((_,j)=>[...Array(k[L="length"]**j)].map((_,i)=>eval("r=[];while(j-r[L])r.push(i%k[L]),i=i/k[L]|0;r")).filter(p=>(a=m=d=0,p.map(i=>(a+=k[i],d|=i<m,m=i)),a==t&&!d)).map(p=>p.map(i=>l[i])))

```

I had a bunch of really neat ideas for how to golf this but they ended up not working.

---
Tags: code-golf
---


# Question
Title: The Game of Cat And Mice | With Matrices
# Challenge

This coding challenge is to figure out how many rounds the cat can live.
In a \\$4\times4\\$ matrix, there are a number of mice and exactly 1 cat.
Example: $$ \begin{array} {|r|r|}\hline & & & ⬜ \\ \hline ⬜ & & ⬜ & ⬜ \\ \hline ⬜ & ⬜ & ⬜ & \\ \hline & & & \\ \hline \end{array} $$

But in each square of the matrix, like a house, up to 5 mice can live in it.
I indicate it with a number in front of the mouse.
There are also squares where there are no mice =\> Indicated with a blank square. Example: $$ \begin{array} {|r|r|}\hline 1 & 2 & 3 & ⬜ \\ \hline ⬜ & 5 & ⬜ & ⬜ \\ \hline ⬜ & ⬜ & ⬜ & 2 \\ \hline 1 & 4 & 1 & 1 \\ \hline \end{array} $$

# About the Cat and Mouse

The cat can, and must, move up, down, left, right and diagonal, **1 step** at a time. Take into note, that the cat can only eat 1 mouse per round. The cat will always eat a mouse, because it is always hungry.

The cat prefers the house with the most mice in it, although it knows it can eat just one at a time (don't ask me why).
After the cat has eaten a mouse, the number of mice in the house will of course decrease.
After the cat has eaten a mouse, the cat lives in the home of the eaten mouse, possibly with other mice for the remainder of the round.

In the starting position, the cat can only live where there is no mice. But even after the first round, of course the cat must live in a house of the mice.

This goes on and on, till:

# Game End

These are the scenarios, when the game ends:

* When there are no more mice around the cat to eat anymore.
=\> The cat will starve. (Note the cat cannot eat another mouse in the current house since it must move on, so can end up starving while residing with mice - like in example 5)
* When at least 2 of the houses, the cat **can visit**, has the highest and same number of mice.
=\> The cat will die of frustration.

# Rules

* The Input must be a list, or an array, or some datatype that can store the number of mice in the house, and where the cat is.
* Where there is no mice, you can indicate it with just \\$0\\$
* If you use an array, it could be 1 dimensional, but also 2 dimensional.
* The output must be an integer, the number of rounds the cat did survive.
* Standard Loopholes apply, of course.
* This is , so the shortest code wins.

Good luck!

Note: In the above matrix I showed, the output must be \\$3\\$.
=\> Death because: the cat can't decide in which house of mice to eat.

## Example

### Example 1

* Starting state: $$ \begin{array} {|r|r|}\hline 1 & 2 & 3 & ⬜ \\ \hline ⬜ & 5 & ⬜ & ⬜ \\ \hline ⬜ & ⬜ & ⬜ & 2 \\ \hline 1 & 4 & 1 & 1 \\ \hline \end{array} $$
* After 1 round: $$ \begin{array} {|r|r|}\hline 1 & 2 & 3 & ⬜ \\ \hline ⬜ & 4\\!\\!\\!\\!\\!\\!\\!\\! & ⬜ & ⬜ \\ \hline ⬜ & ⬜ & ⬜ & 2 \\ \hline 1 & 4 & 1 & 1 \\ \hline \end{array} $$
* After 2 rounds: $$ \begin{array} {|r|r|}\hline 1 & 2 & 2\\!\\!\\!\\!\\!\\!\\!\\! & ⬜ \\ \hline ⬜ & 4 & ⬜ & ⬜ \\ \hline ⬜ & ⬜ & ⬜ & 2 \\ \hline 1 & 4 & 1 & 1 \\ \hline \end{array} $$
* After 3 rounds: $$ \begin{array} {|r|r|}\hline 1 & 2 & 2 & ⬜ \\ \hline ⬜ & 3\\!\\!\\!\\!\\!\\!\\!\\! & ⬜ & ⬜ \\ \hline ⬜ & ⬜ & ⬜ & 2 \\ \hline 1 & 4 & 1 & 1 \\ \hline \end{array} $$
* 4th Round: **Death of frustration** $$ \begin{array} {|r|r|}\hline 1 & \underbrace{2} & \underbrace{2} & ⬜ \\ \hline ⬜ & 3\\!\\!\\!\\!\\!\\!\\!\\! & ⬜ & ⬜ \\ \hline ⬜ & ⬜ & ⬜ & 2 \\ \hline 1 & 4 & 1 & 1 \\ \hline \end{array} $$

So it just survived 3 rounds.

### Example 2

* Starting Stage $$ \begin{array} {|r|r|}\hline 1 & 5 & 1 & ⬜ \\ \hline ⬜ & 5 & ⬜ & ⬜ \\ \hline ⬜ & ⬜ & ⬜ & 2 \\ \hline ⬜ & ⬜ & ⬜ & 1 \\ \hline \end{array} $$
* End Stage: 1 Round $$ \begin{array} {|r|r|}\hline 1 & 5 & ⬜ & ⬜ \\ \hline ⬜ & 5 & ⬜ & ⬜ \\ \hline ⬜ & ⬜ & ⬜ & 2 \\ \hline ⬜ & ⬜ & ⬜ & 1 \\ \hline \end{array} $$

### Example 3

* Starting Stage $$ \begin{array} {|r|r|}\hline 1 & 5 & 1 & ⬜ \\ \hline ⬜ & 5 & ⬜ & ⬜ \\ \hline 2 & ⬜ & 1 & 4 \\ \hline ⬜ & ⬜ & 1 & 1 \\ \hline \end{array} $$
* End Stage: 7 Rounds $$ \begin{array} {|r|r|}\hline 1 & 2 & 1 & ⬜ \\ \hline ⬜ & 1\\!\\!\\!\\!\\!\\!\\!\\! & ⬜ & ⬜ \\ \hline 2 & ⬜ & 1 & 4 \\ \hline ⬜ & ⬜ & 1 & 1 \\ \hline \end{array} $$

### Example 4

* Starting Stage $$ \begin{array} {|r|r|}\hline ⬜ & ⬜ & ⬜ & ⬜ \\ \hline ⬜ & 1 & ⬜ & ⬜ \\ \hline ⬜ & ⬜ & 1 & 1 \\ \hline ⬜ & ⬜ & ⬜ & 2 \\ \hline \end{array} $$
* End Stage: 5 Rounds $$ \begin{array} {|r|r|}\hline ⬜ & ⬜ & ⬜ & ⬜ \\ \hline ⬜ & ⬜ & ⬜ & ⬜ \\ \hline ⬜ & ⬜ & ⬜ & ⬜ \\ \hline ⬜ & ⬜ & ⬜ & ⬜ \\ \hline \end{array} $$

### Example 5

* Starting Stage $$ \begin{array} {|r|r|}\hline ⬜ & 3 & ⬜ & ⬜ \\ \hline ⬜ & 2 & ⬜ & ⬜ \\ \hline ⬜ & ⬜ & 1 & ⬜ \\ \hline ⬜ & ⬜ & ⬜ & ⬜ \\ \hline \end{array} $$
* End Stage: 4 Rounds $$ \begin{array} {|r|r|}\hline ⬜ & 1\\!\\!\\!\\!\\!\\!\\!\\! & ⬜ & ⬜ \\ \hline ⬜ & ⬜ & ⬜ & ⬜ \\ \hline ⬜ & ⬜ & 1 & ⬜ \\ \hline ⬜ & ⬜ & ⬜ & ⬜ \\ \hline \end{array} $$ Good luck again!

# Answer
> 5 votes
# Python 3.8, ~~167~~ \\$\cdots\\$ ~~159~~ 155 bytes

Saved ~~2~~ 5 bytes thanks to ovs!!!
Saved 4 bytes thanks to Delfad0r!!!

```
def f(a,c,r=0):
 while(l:=sorted([[z,-a.get(c+z,0)]*2for x in(1,1j,1+1j,1-1j)for z in(x,-x)],key=list.pop))[0][1]<l[1][1]:r+=1;c+=l[0][0];a[c]-=1
 return r

```

Try it online!

Inputs a dictionary mapping each house in the array (represented by a complex number) to the number of mice in that house along with the position of the cat as a complex number.
Return the number of rounds before the cat "dies" (no cats or mice where harmed in this answer, they're all professional actors just playing their parts).

# Answer
> 3 votes
# JavaScript (ES7),  ~~122 113 112~~  111 bytes

*Saved 1 byte thanks to @l4m2*

Expects `(mice_array)(cat_x, cat_y)`.

```
m=>g=(x,y)=>!m.reduce((o,v,n)=>6>>(n%4-x)**2+((n>>2)-y)**2&1?v>h?!(p=n,h=v):o|v==h:o,h=0)&&1+g(p&3,p>>2,m[p]--)

```

Try it online!

### Commented

This is a bit similar to my answer to my own challenge.

```
m =>                   // m[] = flat array of mice
g =                    // g is a recursive function taking
(x, y) =>              // the position (x, y) of the cat
!m.reduce((o, v, n) => // for each value v at position n in m[]:
  6 >>                 //   bitmask of valid squared distances
  (n % 4 - x) ** 2 +   //   compute (prev_x - x)²
  ((n >> 2) - y) ** 2  //   + (prev_y - y)²
  & 1 ?                //   if it's either 1 or 2:
    v > h ?            //     if v is greater than the highest value h:
      !(p = n, h = v)  //       copy n to p and v to h, clear o
    :                  //     else:
      o | v == h       //       set o if v = h (frustrated cat!)
  :                    //   else:
    o,                 //     leave o unchanged
  h = 0                //   start with o = h = 0
)                      // end of reduce()
&&                     // if it's falsy:
  1 +                  //   increment the final result
  g(                   //   and do a recursive call:
    p & 3,             //     new x
    p >> 2,            //     new y
    m[p]--             //     decrement m[p]
  )                    //   end of recursive call

```

# Answer
> 3 votes
# Haskell, ~~137~~ 134 bytes

```
(x,y)!l|d<-[a|a@((i,j),k)<-l,((x-i)^2+(y-j)^2-2)^2<2],m<-foldr(max.snd)1d,[i]<-[i|(i,k)<-d,k==m]=1+i!((i,m-1):[a|a<-l,fst a/=i])|0<1=0

```

Try it online!

The function `(!)` takes as input the position of the cat `(x,y)` and a list with one `((i,j),k)` entry for each house, where house at position `(i,j)` as `k` mice (possibly zero).

# Answer
> 2 votes
# Charcoal, 39 bytes

```
Ｅ⁴ＳＪＮＮＷ⁼№ＫＭ⌈ＫＭ¹«⊞υωＭ✳⁻³⌕ＫＭ⌈ＫＭＰＩ⊖ＫＫ»⎚ＩＬυ

```

Try it online! Link is to verbose version of code. Takes as input a list of 4 strings of digits, followed by the 0-indexed across and down coordinates. Explanation:

```
Ｅ⁴Ｓ

```

Print the mouse counts to the canvas.

```
ＪＮＮ

```

Move to the cat's starting position.

```
Ｗ⁼№ＫＭ⌈ＫＭ¹«

```

Repeat while the cat has a unique choice of best move.

```
⊞υω

```

Track the number of moves.

```
Ｍ✳⁻³⌕ＫＭ⌈ＫＭ

```

Actually make that move. (Annoyingly the `Peek` and the `Direction` directions don't match up with each other...)

```
ＰＩ⊖ＫＫ

```

Decrement the number of mice at the new position.

```
»⎚ＩＬυ

```

Clear the canvas and output the number of moves taken.

---
Tags: code-golf, math, array, grid, matrix
---


title: Do I have a prime twin?

text:
# Question
Title: Do I have a prime twin?
An Integer is *prime* if and only if it is positive and has exactly 2 distinct divisors: 1 and itself. A twin prime pair is made of two elements: `p` and `p±2`, that are both prime.

You will be given a positive integer as input. Your task is to return a truthy / falsy depending on whether the given integer belongs to a twin pair, following the standard rules (the values need to be consistent).

## Test Cases

* Truthy (Twin Primes): `3, 5, 7, 11, 13, 17, 19, 29, 31, 41, 43`
* Falsy (not Twin Primes): `2, 15, 20, 23, 37, 47, 97, 120, 566`

This is , so the shortest code in bytes wins!

# Answer
> 21 votes
# Brachylog, ~~9~~ 8 bytes

```
ṗ∧4√;?+ṗ

```

Try it online!

### Explanation

```
ṗ           Input is prime
 ∧          And
  4√        A number whose square is 4 (i.e. -2 or 2)
    ;?+     That number + the Input…
       ṗ    …is prime

```

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

```
%6+_2_ÆP⁺

```

Try it online!

### Background

With the exception of **(3, 5)**, all twin prime pairs are of the form **(6k - 1, 6k + 1)**.

Since **(6k - 1) + (6k - 1) % 6 - 3 = 6k - 1 + 5 - 3 = 6k + 1** and
**(6k + 1) + (6k + 1) % 6 - 3 = 6k + 1 + 1 - 3 = 6k - 1**, given an input **n \> 3**, it is sufficient to check whether **n** and **n + n % 6 - 3** are both prime.

This formula *happens to* work for **n = 3** as well, as **3 + 3 % 6 - 3 = 3** is prime and **3** is a twin prime.

### How it works

```
%6+_2_ÆP⁺  Main link. Argument: n

%6         Compute n%6.
  +        Add n to the result.
   _2      Subtract 2.
     _ÆP   Subtract 1 if n is prime, 0 if not.
           If n is not a prime, since (n + n%6 - 2) is always even, this can only
           yield a prime if (n + n%6 - 2 = 2), which happens only when n = 2.
        ⁺  Call ÆP again, testing the result for primality.

```

# Answer
> 9 votes
# Python 3, 53 bytes

```
lambda n:sum((n+n%6-3)*n%k<1for k in range(2,4*n))==2

```

Try it online!

### Background

All integers take one of the following forms, with integer **k**: **6k - 3**, **6k - 2**, **6k - 1**, **6k**, **6k + 1**, **6k + 2**.

Since **6k - 2**, **6k**, and **6k + 2** are all even, and since **6k - 3** is divisible by **3**, all primes except **2** and **3** must be of the form **6k - 1** or **6k + 1**. Since the difference of a twin prime pair is **2**, with the exception of **(3, 5)**, all twin prime pairs are of the form **(6k - 1, 6k + 1)**.

Let **n** be of the form **6k ± 1**.

* If **n = 6k -1**, then **n + n%6 - 3 = 6k - 1 + (6k - 1)%6 - 3 = 6k - 1 + 5 - 3 = 6k + 1**.
* If **n = 6k + 1**, then **n + n%6 - 3 = 6k + 1 + (6k + 1)%6 - 3 = 6k + 1 + 1 - 3 = 6k - 1**.

Thus, *if* **n** is part of a twin prime pair and **n ≠ 3**, it's twin will be **n + n%6 - 3**.

### How it works

Python doesn't have a built-in primality test. While there are short-ish ways to test a single number for primality, doing so for two number would be lengthy. We're going to work with divisors instead.

```
sum((n+n%6-3)*n%k<1for k in range(2,4*n))

```

counts how many integers **k** in the interval **\[2, 4n)** divide **(n + n%6 - 3)n** evenly, i.e., it counts the number of divisors of **(n + n%6 - 3)n** in the interval **\[2, 4n)**. We claim that this count is **2** if and only if **n** is part of a twin prime pair.

* If **n = 3** (a twin prime), **(n + n%6 - 3)n = 3(3 + 3 - 3) = 9** has two divisors (**3** and **9**) in **\[2, 12)**.
* If **n \> 3** is a twin prime, as seen before, **m := n + n%6 - 3** is its twin. In this case, **mn** has exactly four divisors: **1, m, n, mn**.

Since **n \> 3**, we have **m \> 4**, so **4n \< mn** and exactly two divisors (**m** and **n**) fall into the interval **\[2, 4n)**.
* If **n = 1**, then **(n + n%6 - 3)n = 1 + 1 - 3 = -1** has no divisors in **\[2, 4)**.
* If **n = 2**, then **(n + n%6 - 3)n = 2(2 + 2 - 3) = 2** has one divisor (itself) in **\[2, 8)**.
* If **n = 4**, then **(n + n%6 - 3)n = 4(4 + 4 - 3) = 20** has four divisors (**2**, **4**, **5**, and **10**) in **\[2, 16)**.
* If **n \> 4** is even, **2**, **n/2**, and **n** all divide **n** and, therefore, **(n + n%6 - 3)n**. We have **n/2 \> 2** since **n \> 4**, so there are at least three divisors in **\[2, 4n)**.
* If **n = 9**, then **(n + n%6 - 3)n = 9(9 + 3 - 3) = 81** has three divisors (**3**, **9**, and **21**) in **\[2, 36)**.
* If **n \> 9** is a multiple of **3**, then **3**, **n/3**, and **n** all divide **n** and, therefore, **(n + n%6 - 3)n**. We have **n/3 \> 3** since **n \> 9**, so there are at least three divisors in **\[2, 4n)**.
* Finally, if **n = 6k ± 1 \> 4** is not a twin prime, either **n** or **m := n + n%6 - 3** must be composite and, therefore, admit a proper divisor **d \> 1**.

Since either **n = m + 2** or **m = n + 2** and **n, m \> 4**, the integers **d**, **m**, and **n** are *distinct* divisors of **mn**. Furthermore, **m \< n + 3 \< 4n** since **n \> 1**, so **mn** has at least three divisors in **\[2, 4n)**.

# Answer
> 5 votes
# 05AB1E, ~~10~~ 9 bytes

Saved 1 byte thanks to *Datboi*

```
ÌIÍ‚pZIp*

```

Try it online! or as a Test Suite

**Explanation**

```
Ì           # push input+2
 IÍ         # push input-2
   ‚        # pair
    p       # isPrime
     Z      # max
      Ip    # push isPrime(input)
        *   # multiply

```

# Answer
> 4 votes
# PHP, 52 bytes

```
<?=($p=gmp_prob_prime)($n=$argn)&&$p($n+2)|$p($n-2);

```

without GMP, **84 bytes**

(using my prime function from stack overflow)

```
<?=p($n=$argn)&&p(2+$n)|p($n-2);function p($n){for($i=$n;--$i&&$n%$i;);return$i==1;}

```

Run as pipe with `-nF`. Empty output for falsy, `1` for truthy.

Dennis´ great solution ported to PHP, **56 bytes**

```
while($i++<4*$n=$argn)($n+$n%6-3)*$n%$i?:$s++;echo$s==3;

```

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

# Answer
> 4 votes
# Perl 6, 24 bytes

```
?(*+(0&(-2|2))).is-prime

```

Try it online!

`*` is the argument to this anonymous function. `0 & (-2 | 2)` is the junction consisting of the numbers `0` AND either `-2` OR `2`. Adding `*` to this junction produces the junction of the number `*` AND either of the numbers `* - 2` OR `* + 2`. Calling the `is-prime` method on this junction returns a truthy value if `*` is prime AND either `* - 2` OR `* + 2` are prime. Finally, the `?` collapses the truthy junction to a boolean value, satisfying the consistent-return-values condition.

# Answer
> 3 votes
# Pyth, ~~14 12~~ 11 bytes

```
&P_QP-3+%Q6

```

Test Suite.

---

Saved 3 bytes using the formula in @Dennis' answer. Saved 1 byte thanks to @Dennis.

---

# Pyth, 14 bytes **Initial Solution*

```
&|P_ttQP_hhQP_

```

Test Suite.

# Answer
> 3 votes
# Mathematica, 33 bytes

```
(P=PrimeQ;P@#&&(P[#+2]||P[#-2]))&

```

Try it online!

# Answer
> 3 votes
# MATL, 11 bytes

```
HOht_v+ZpAa

```

Output is `0` or `1`.

Try it online!

### Explanation

```
H    % Push 2
O    % Push 0
h    % Concatenate horizontally: gives [2 0]
t_   % Push a negated copy: [-2 0]
v    % Concatenate vertically: [2 0; -2 0]
+    % Add to implicit input
Zp   % Isprime
A    % All: true for columns that only contain nonzeros
a    % Any: true if there is at least a nonzero. Implicit display

```

# Answer
> 3 votes
# Retina, ~~45~~ 44 bytes

```
.*
$*
11(1+)
$1¶$&¶11$&
m`^(11+)\1+$

1<`1¶1

```

Returns 1 if the input is a twin prime, 0 otherwise

Try it online!

### Explanation

```
.*
$*

```

Convert to Unary

```
11(1+)
$1¶$&¶11$&

```

Put n-2, n, and n+2 on their own lines

```
m`^(11+)\1+$

```

(Trailing newline) Remove all composites greater than 1

```
1<`1¶1

```

Check if there are two consecutive primes (or 1,3 because 3 is a twin prime)

# Answer
> 3 votes
# Factor \+ `math.primes`, 42 bytes

```
[| x | 0 2 -2 [ x + prime? ] tri@ or and ]

```

Try it online!

Originally inspired by trying to golf Michael Chatiskatzi's answer, I've then modified it enough that I thought worth posting it as a separate answer.

### Explanation

This is a lambda function using the local variable `x` to refer to the element at the top of the stack when the function is called (its argument).

`[ x + prime? ]` defines a function that adds `x` to a number and checks if the result is prime. This is then applied using `tri@` to the three values `0`,`2`,`-2`, resulting in three booleans determining if `x`,`x+2` and `x-2` are primes. We combine the last two with `or`, and the result of this with the first with `and`.

The total function is then equivalent to `isprime(x+0) and (isprime(x+2) or isprime(x-2))`

# Answer
> 2 votes
# 05AB1E, 8 bytes

Port of Dennis' Jelly answer

```
6%+ÍIp-p

```

Try it online! or as a Test Suite

**Explanation**

```
6%         # n mod 6
  +        # add n
   Í       # subtract 2
    Ip-    # subtract isPrime(n)
       p   # isPrime

```

# Answer
> 2 votes
# Excel VBA, ~~102~~ 100 Bytes

No primality built-ins for VBA `:(`

### Code

Anonymous VBE immediate window function that takes input from cell `[A1]` and outputs either `1` (truthy) or `0` (falsy) to the VBE Immediate window

```
a=[A1]:?p(a)*(p(a-2)Or p(a+2))

```

### Helper Function

```
Function p(n)
p=n>2
For i=2To n-1
p=IIf(n Mod i,p,0)
Next
End Function

```

---

## Alternatively, 122 Bytes

### Code

Recursive primality checking function based solution

```
a=[A1]:?-1=Not(p(a,a-1)Or(p(a-2,a-3)*p(a+2,a+1)))

```

### Helper Function

```
Function p(n,m)
If m>1Then p=p(n,m-1)+(n Mod m=0)Else p=n<=0
End Function

```

# Answer
> 2 votes
# JavaScript, 91 bytes, 81 bytes thanks to Jared Smith

```
p=n=>{for(i=2;i<n;)if(n%i++==0)return !!0;return n>1},t=n=>p(n)&&(p(n+2)||p(n-2))

```

**Explanation**

`p` tells wether the given number `n` is prime or not, and `t` tests given number `n` and `n±2`.

**Example**

```
var twinPrimes = [3, 5, 7, 11, 13, 17, 19, 29, 31, 41, 43];
var notTwinPrimes = [2, 15, 20, 23, 37, 47, 97, 120, 566];

p=n=>{for(i=2;i<n;)if(n%i++==0)return !!0;return n>1},t=n=>p(n)&&(p(n+2)||p(n-2))

for (var n of twinPrimes) {
  console.log(n, ': ', t(n));
}

for (var n of notTwinPrimes) {
  console.log(n, ': ', t(n));
}
```

# Answer
> 1 votes
# J, 23 bytes

```
1&p:*.0<+/@(1 p:_2 2+])

```

Try it online!

### how?

```
1&p:                               is the arg a prime?
    *.                             boolean and
                                   one of +2 or -2 also a prime
                     (1 p:_2 2+])  length 2 list of booleans indicating if -2 and +2 are primes
               @                   pipe the result into...
      0<+/                         is the sum of the elements greater than 0
                                   ie, at least one true

```

# Answer
> 1 votes
# Ruby, 38 + 6 = 44 bytes

Requires options `-rprime`.

```
->n{n.prime?&[n-2,n+2].any?(&:prime?)}

```

Try it online!

# Answer
> 1 votes
# JavaScript(ES6), 54 bytes

```
a=x=>f(x)&(f(x+2)|f(x-2));f=(n,x=n)=>n%--x?f(n,x):x==1

```

```
a=x=>f(x)&(f(x+2)|f(x-2));f=(n,x=n)=>n%--x?f(n,x):x==1

console.log("True")
console.log("---------------------")
console.log(a(3))
console.log(a(5))
console.log(a(7))
console.log(a(11))
console.log(a(13))
console.log(a(17))
console.log(a(19))
console.log(a(29))
console.log(a(31))
console.log(a(41))
console.log(a(43))
console.log("False")
console.log("---------------------")
console.log(a(2))
console.log(a(15))
console.log(a(20))
console.log(a(23))
console.log(a(37))
console.log(a(47))
console.log(a(97))
console.log(a(120))
console.log(a(566))
```

# Answer
> 1 votes
# Japt, 13 bytes

```
j ©[U+2U-2]dj

```

Returns `true` and `false` for whether or not the number is part of a prime twin pair.

Try it online!

## Explanation

Implicit: `U` = input integer

```
j ©

```

Check if the input is prime (`j`), AND (`©`) ...

```
[U+2U-2]dj

```

Using the array `[U+2, U-2]`, check if any items are true (`d`) according to the primality function (`j`).

Implicit output of the boolean result of `is input prime AND is any ±2 neighbor prime`.

# Answer
> 1 votes
# Husk, 8 bytes

```
Vṗ(§e+-2

```

Try it online!

# Answer
> 1 votes
# Factor \+ `math.primes`, 46 bytes

```
[ dup 2 [ + ] 2keep - [ prime? ] tri@ or and ]

```

**Demonstartion** of every state of the stack for the example number 43:

```
  43   dup    2  [ + ]  2keep    - [ prime? ] tri@   or   and

|    |     |    |  + |    2   |    | prime? |      |    |     |
|    |     |  2 |  2 |   43   | 41 |     41 |    t |    |     |
|    |  43 | 43 | 43 |   45   | 45 |     45 |    f |  t |     |
| 43 |  43 | 43 | 43 |   43   | 43 |     43 |    t |  t |   t |

```

Try it online!

# Answer
> 1 votes
# Regex (ECMAScript or better), ~~48~~ ~~35~~ ~~29~~ 28 bytes

*-20 bytes thanks to H.PWiz*

```
^(xx)?(?!(xx(x*))\3?\2+$)xxx

```

Try it online! \- ECMAScript
Try it online! \- Perl
Try it online! \- Java
Try it online! \- Python
Try it online! \- Ruby
Try it online! \- PCRE
Try it online! \- .NET

Takes its input in unary, as a string of `x` characters whose length represents the number.

Commented and indented:

```
^                 # tail = N = input number
# Assert either that N-2 and N are prime, or that N and N+2 are prime.

(xx)?             # tail -= 2, optionally
# Assert that neither tail nor tail+2 are composite. For testing that they are both prime,
# this has false positives for tail=0, tail=1, and tail=2.
(?!               # Assert that the following can't match:
    (xx(x*))      # \2 = any number >= 2; \3 = \2 - 2
    \3?           # tail -= \3, optionally; if this is done, we're asserting that tail+2 is
                  #             composite (divisible by \2 with a quotient >= 3), otherwise
                  #             we're asserting tail is composite (quotient >= 2).
    \2+$          # Assert that tail is positive and divisible by \2
)
xxx               # Assert that tail >= 3, preventing the false positives.
                  # The "quotient >= 3" requirement above is why tail=2 can be one of them,
                  # as it prevents 2+2 from being seen as composite.

```

## 29 bytes

```
^                  # tail = N = input number
# Assert either that N-2 and N are prime, or that N and N+2 are prime.

(xx)?              # tail -= 2, optionally
# Assert that neither tail nor tail+2 are composite. For testing that they are both prime,
# this has false positives for tail=0 and tail=1.
(?!                # Assert that the following can't match:
    (xx)?          # tail -= 2, optionally; if this is done, we're asserting that tail is
                   #            composite, otherwise we're asserting tail+2 is composite.
    (x*)           # \3 = S-2, where S is a potential divisor to test against M = tail+2;
                   # tail -= \3
    (\3xx)+$       # assert that tail is positive and divisible by \3+2, which is
                   # equivalent to asserting M is divisible by S with a quotient >= 2
)
xx                 # Assert that tail >= 2, preventing the false positives.

```

## 48 bytes

This misses the fact that we can switch between testing N-2 and N or testing N and N+2. Instead, this regex switches between testing N and N-2 or testing N and N+2, which results in tests not having enough in common to be collapsed together.

```
^   # tail = N = input number
(
    # Assert that neither N nor N-2 are composite. But we want N and N-2 to be prime, so
    # this gives false positives for 0, 1, and 2.
    (?!              # Assert that the following can't match:
        (xx)?        # tail -= 2, optionally
        (xx+)        # \3 = any number >= 2
        \3+$         # Assert that tail is positive and divisible by \3
    )
|   # or...
    # Assert that neither N nor N+2 are composite. But we want N and N+2 to be prime, so
    # this gives false positives for 0 and 1.
    (?!              # Assert that the following can't match:
        (xx(x*))     # \4 = any number >= 2; \5 = \4 - 2
        \4*(xx)?\5$  # Assert that either tail or tail+2 is positive and divisible by \4
    )
)
xxx                  # Block the false positives on every number less than 3

```

## 51 bytes (not golfed at all)

```
^                      # tail = N = input number
(?!(xx+)\1+$)          # Assert that N is not composite. But we want N to be prime,
                       # so this gives false positives for 0 and 1.
(
    (?!xx(xx+)\3+$)    # Assert that N-2 is not composite. But we want N-2 to be prime, so this
                       # gives false positives for 0, 1, and 2.
|   # or...
    (?!(x*)(xx\4)+$)   # Assert that N+2 is not composite. Has no false positives for primality.
)
xxx                    # Block the false positives on every number less than 3

```

# Regex (ECMAScript), 67 bytes

Just for kicks, here is a port of Dennis's Jelly algorithm:

```
^(?!(xx+)\1+$)(?=(x{6})*(x*))xxx(?!(xx+)(?=\4*(x*)).*(?=\5\3$)\4+$)

```

Try it online!

```
^                      # tail = N = input number
(?!(xx+)\1+$)          # Assert N is not composite
(?=(x{6})*(x*))        # \3 = N % 6
xxx                    # assert N>=3; tail -= 3
# Assert tail + \3 is not composite
(?!                    # Assert the following can't match:
    (xx+)              # \4 cycles through all values such that 2 <= \4 <= tail,
                       #    and is tested as a possible divisor of tail + \3
    (?=\4*(x*))        # \5 = tail % \4
    .*(?=\5\3$)        # tail = \5 + \3
    \4+$               # Assert that tail is positive and divisible by \4
)

```

### \\$\large\textit{Anonymous functions}\\$

# JavaScript (ES6), 50 bytes

```
n=>/^(..)?(?!(..(.*))\3?\2+$).../.test(Array(n+1))

```

Try it online!

# Ruby, 41 bytes

```
->n{?x*n=~/^(xx)?(?!(xx(x*))\3?\2+$)xxx/}

```

Try it online!
Try it online! \- test cases only

### \\$\large\textit{Full programs}\\$

# Retina, 34 bytes

```
.*
$*
^(11)?(?!(11(1*))\3?\2+$)111

```

Try it online! \- test cases only

# Answer
> 1 votes
# APL (Dyalog Unicode), 35 bytes

```
{∨/2∧/∊∘{(⊢~∘.×⍨)1↓⍳⍵}¨⍨|2(-,⊢,+)⍵}
 ∨/ ⍝ reduce by bitwise OR
   2∧/ ⍝ logical AND bit array, two at a time (overlapping)
     ∊∘{...}¨⍨ ⍝ for each, check if in list of primes
       (⊢~∘.×⍨)1↓⍳⍵ ⍝ find element of range that is not in matrix of composite numbers (list of primes)
         | ⍝ absolute value of array
           2(-,⊢,+)⍵ ⍝ create array (2-n, n, 2+n)

```

Try it online!

# Answer
> 0 votes
# PHP, 85 bytes **24 bytes thanks to Mayube**

```
e($n){return f($n)&&((f($n-2)||f($n+2)))
f($n){for($i=$n;--$i&&$n%$i;)return $i==1;}

```

# Answer
> 0 votes
# Python 2, 75 bytes

```
lambda x:p(x)*(p(x-2)|p(x+2))
p=lambda z:(z>1)*all(z%i for i in range(2,z))

```

Try it online!

# Answer
> 0 votes
# Excel, 84 bytes

Current Excel 365:

```
=LET(x,SEQUENCE(A1+2),(SUM((MOD(A1,x)=0)*1)=2)*(SUM((MOD(A1+MOD(A1,6)-3,x)=0)*1)=2))

```

Future Excel (73 bytes):

```
=LET(p,LAMBDA(a,SUM((MOD(a,SEQUENCE(a))=0)*1)=2),p(A1)*p(A1+MOD(A1,6)-3))

```

---
Tags: code-golf, number, decision-problem, primes
---