title: You're a Romanizer, Baby

text:
# Question
Title: You're a Romanizer, Baby
Romanization of Japanese is converting Japanese text into Latin characters. In this challenge, you will be given a string of Japanese characters as input and expected to convert them to the correct ASCII string.

# What You'll Need To Know

The Japanese language has three writing systems: hiragana (the curvy one used for short words), katakana (the angle-y one used for sounds and words borrowed from other langauges), and kanji (the dense characters originally from Chinese). In this challenge we will only worry about hiragana.

There are 46 characters in the hiragana syllabary. Each character represents a syllable. The characters are organized by first sound (consonant) and second sound (vowel). The columns in order are `aiueo`.

```
 : あいうえお
k: かきくけこ
s: さしすせそ
t: たちつてと
n: なにぬねの
h: はひふへほ
m: まみむめも
y: や　ゆ　よ
r: らりるれろ
w: わ　　　を
N: ん

```

(if you copy and paste this table note that I have used ideographic spaces U+3000 to space out y and w)

So, for instance, あとめ should produce an output of `atome`. The first character is `a`, the second is `to`, and the third is `me`.

# Exceptions

Like any good language, Japanese has exceptions to its rules, and the hiragana table has several. These characters are pronounced slightly differently than their location in the table would imply:

し: `shi`, not `si`
ち: `chi`, not `ti`
つ: `tsu`, not `tu`
ふ: `fu`, not `hu`

# Dakuten ゛

The word 'dakuten' means 'muddy mark': the dakuten turns sounds into their voiced equivalents (usually); for example, か `ka` turns into か゛ `ga`. A full list of the changes:

`k``g`
`s``z`
`t``d`
`h``b`

The exceptions change too: し゛: `ji` (or `zhi`), not `zi`
ち゛: `ji`, not `di`
つ゛: `dzu`, not `du`
(ふ゛ acts as you would expect; it is not an exception)

The handakuten is an *additional* character ゜ that applies to the `h` row. If placed after a character, it changes the character's sound to `p` rather than `b`.

Both the dakuten and handakuten are going to be given as individual characters. You will not need to deal with the precomposed forms or the combining characters.

# Small Characters

Finally, there are small versions of some of the characters. They modify characters that come before or after them.

ゃゅょ

These are the small forms of `ya`, `yu`, and `yo`. They are only placed after sounds in the `i`-column; they remove the `i` and add their sound. So, きや turns into `kiya`; きゃ turns into `kya`.

If placed after `chi` or `shi` (or their dakuten-ed forms), the `y` is removed too. しゆ is `shiyu`; しゅ is `shu`.

The last thing you'll have to deal with is the small `tsu`. っ doubles the consonant that comes after it, no matter what; it does nothing else. For instance, きた is `kita`; きった is `kitta`.

# Summary, Input, and Output

Your program must be able to transliterate: the 46 basic hiragana, their dakuten and handakuten forms, and their combinations with small characters.

Undefined behavior includes: small `ya`, `yu`, and `yo` not after a character with `i`, small `tsu` at the end of a string, dakuten on an unaffected character, handakuten on a non-`p` character, and anything else not mentioned in the above spec/introduction.

You may assume all inputs are valid and contain only the Japanese characters mentioned above.

Case does not matter in output; you may also replace `r` with `l` or a lone `n` with `m`. Output can have either one space between every syllable or no spaces at all.

**This is : shortest code in bytes wins.**

# Test Cases

Many test cases for each individual part are given in the spec. Some additional cases:

ひらか゛な → `hiragana`

かたかな → `katakana`

た゛いき゛ゃくてんさいは゛ん → `daigyakutensaiban`

ふ゜ろく゛らみんく゛は゜す゛るこうと゛こ゛るふ → `puroguramingupazurucoudogorufu`

か゛んほ゛って → `ganbatte`

# Notes

* I do not know much Japanese besides what I've written here. Please let me know if I've made any mistakes.
* I was originally planning to include katakana too (so my English transliteration test case could be *slightly* more accurate), but that would be too much for a code golf challenge.
* The Unicode names include the transliteration of each character individually, but without the exceptions. This may or may not be helpful to you.
* Thanks to squeamishossifrage for correcting two typos!
* I'm sorry if this is too long; I attempted to fit most of the quirks of hiragana into the challenge but some things (like small vowel-only hiragana, changing n to m in front of some consonants, and the repetition mark) had to be cut to keep the challenge manageable.
* I'm not at all sorry for the title. It's a masterpiece.

# Answer
> 7 votes
# Python 2, 638 bytes

```
import unicodedata
s=input()
k=[0x309B,0x309C,0x3063]
m=[0x3083,0x3085,0x3087]
e={0x3057:'shi',0x3061:'chi',0x3064:'tsu',0x3075:'fu'}
d={0x3057:'ji',0x3061:'ji',0x3064:'dzu'}
D=dict(zip('ksth','gzdb'))
f=lambda c:unicodedata.name(c).split()[-1].lower()if ord(c)not in e else e[ord(c)]
g=lambda c:d[c]if c in d else D[f(c)[0]]+f(c)[1:]
R=[]
r=[]
t=[]
i=0
while i<len(s):
 c=ord(s[i])
 if c==k[0]:R[-1]=g(s[i-1])
 elif c==k[1]:R[-1]='p'+R[-1][1:]
 elif c in m:R[-1]=R[-1][:-1];n=f(s[i]);R+=[n[1:]]if r[-1]in[0x3057,0x3061]else[n];r+=[c]
 elif c==k[2]:t+=[len(R)]
 else:R+=[f(s[i])];r+=[c]
 i+=1
for i in t:R[i]=R[i][0]+R[i]
print ''.join(R)

```

Takes input as unicode string.

Test it on Ideone

# Answer
> 6 votes
# Python 2, 447 bytes

```
import unicodedata as u
r=str.replace
i=''.join('x'*('SM'in u.name(x)or ord(x)==12444)+u.name(x)[-2:].strip()for x in raw_input().decode('utf-8'))
for a,o in zip('KSTH','GZDB'):
    for b in'AEIOU':i=r(r(i,a+b+'xRK','P'+b),a+b+'RK',o+b)
for a,b,c,d in zip('STDZ',('SH','CH','J','J'),'TDHH',('TS','DZ','F','F')):i=r(r(i,a+'I',b+'I'),c+'U',d+'U')
for a in'CH','SH','J':i=r(i,a+'IxY',a)
for a in'BCDFGHJKMNPRSTWYZ':i=r(i,'xTSU'+a,a+a)
print r(i,'Ix','')

```

This takes Unicode input directly, which made me lose a few bytes because of the `decode('utf-8')` but I think is more in the spirit of the challenge.

I began by replacing every character by the last two characters of its unicode name, as suggested in the notes of the puzzle. Unfortunately, this doesn't distinguish between alternate versions of the same character, so I had to make an ugly hack to add an 'x' before the small characters and the handakuten.

The rest of the for loops are just fixing exceptions, in order:

1. the first for loop turns dakutens and handakutens into the correct consonants;
2. the second for loop deals with the hiragana exceptions of shi, chi, tsu and fu;
3. third for loop deals with the exceptions before a small y- character (like sha, jo);
4. fourth for loop deals with doubling consonants after a small tsu.
5. final line deals with small y-.

I wish I could have combined more steps, but in some cases the steps have to be performed in order to avoid conflicts.

Try it online! (a multi-line version with more examples can be found here).

# Answer
> 6 votes
## Swift 3, 67 64 characters

let r={(s:String) in s.applyingTransform(.toLatin, reverse: false)}

```
let r={(s:String)in s.applyingTransform(.toLatin,reverse:false)}

```

# Answer
> 5 votes
# Python 3, 259 bytes

```
import re,unicodedata as u
s=re.sub
n=u.normalize
k,*r=r'NFKC DZU DU TSU TU \1\1 SM.{6}(.) \1 (CH|J|SH)Y \1 ISMALL.(Y.) CHI TI JI [ZD]I SHI SI FU HU'.split()
t=''.join(u.name(c)[16:]for c in n(k,s(' ','',n(k,input()))))
while r:t=s(r.pop(),r.pop(),t)
print(t)

```

Try it online!

## Explanation

We’re in luck with this input format! Look what happens if I pass the input through NFKC normalization:

```
>>> nfkc = lambda x: u.normalize('NFKC', x)
>>> [u.name(c) for c in 'は゛']
['HIRAGANA LETTER HA', 'KATAKANA-HIRAGANA VOICED SOUND MARK']
>>> [u.name(c) for c in nfkc('は゛')]
['HIRAGANA LETTER HA', 'SPACE', 'COMBINING KATAKANA-HIRAGANA VOICED SOUND MARK']

```

The dakuten gets replaced by a space and a combining dakuten. Now that space is all that’s separating the は from its dakuten. So we get rid of it and normalize *again*:

```
>>> [u.name(c) for c in nfkc(nfkc('は゛').replace(' ', ''))]
['HIRAGANA LETTER BA']

```

Bingo. The fifth line turns the input into something like

```
KONOSUBARASIISEKAINISISMALL YUKUHUKUWO

```

Then we apply 9 boring regex substitutions crammed in `r`, and we’re done:

```
KONOSUBARASHIISEKAINISHUKUFUKUWO

```

(Jonathan French saved 4 bytes, writing `import re,unicodedata as u` instead of `import re;from unicodedata import*`. Thanks!)

# Answer
> 0 votes
# Lexurgy, ~~549~~ 498 bytes

Lexurgy *does* have a romanizer function that uses the rules as everything else, but it's meant more for debugging/additional output purposes and is not useful for this challenge.

```
Symbol sh,ch,ts
k:
{あ,い,う,え,お,か,き,く,け,こ,さ,し,す,せ,そ,た,ち,つ,て,と,な,に,ぬ,ね,の,は,ひ,ふ,へ,ほ,ま,み,む,め,も,ら,り,る,れ,ろ,や,ゆ,よ,わ,を,ん,ゃ,ゅ,ょ}=>{a,i,u,e,o,ka,ki,ku,ke,ko,sa,shi,su,se,so,ta,chi,tsu,te,to,na,ni,nu,ne,no,ha,hi,hu,he,ho,ma,mi,mu,me,mo,ra,ri,ru,re,ro,ya,yu,yo,wa,wo,n,Ya,Yu,Yo}
v:
{k,s,t,ch,ts,h,sh} []$1 ゛=>{g,z,d,j,dz,b,j} $1 *
h []$1 ゜=>p $1 *
hu=>fu
s:
iY=>* y
iY=>*/{ch,sh,j} _
っ []$1=>$1 $1

```

Ungolfed explanation:

Symbol sh, ch, ts # treat these as a single character

# unfortunate kana -> latin mappings
Class kana {あ,い,う,え,お,か,き,く,け,こ,さ,し,す,せ,そ,た,ち,つ,て,と,な,に,ぬ,ね,の,は,ひ,ふ,へ,ほ,ま,み,む,め,も,ら,り,る,れ,ろ,や,ゆ,よ,わ,を,ん,ゃ,ゅ,ょ}
Class latin {a,i,u,e,o,ka,ki,ku,ke,ko,sa,shi,su,se,so,ta,chi,tsu,te,to,na,ni,nu,ne,no,ha,hi,hu,he,ho,ma,mi,mu,me,mo,ra,ri,ru,re,ro,ya,yu,yo,wa,wo,n,Ya,Yu,Yo}
# voicing mappings
Class unvoiced {k,s,t,ch,ts,h,sh}
Class voiced {g,z,d,j,dz,b,j}

kana-to-latin:
@kana => @latin

voicing:
@unvoiced []$1 ゛ => @voiced $1 * # apply dakuden
h []$1 ゜ => p $1 * # apply handakuden

fu: # explicit exception for ふ
hu => fu

small-y: # small やゆよ
i => * / _ Y
Y => y

shyu: # handle ちぢしじ
y => * / {ch,sh,j} _

small-tsu: # gemination (duplication of a character) is the prototypical use-case for capturing
っ []$1 => $1 $1
```
</code></pre>

# Answer
> 0 votes
# Python3, 607 bytes:

```
def f(s):
 V='aiueo'
 v,k,d,u,w,t,l,q,g,j=(t:=b.split('\n'))[0][3:],{a:i[0]+V[j]for i in t[1:]for j,a in enumerate(i[3:])},'',0,0,0,{'し':'shi','ち':'chi','つ':'tsu','ふ':'fu'},{'し':'ji','ち':'ji','つ':'dzu'},{'k':'g','s':'z','t':'d','h':'b'},{'ゃ':'ya','ゅ':'yu','ょ':'yo'}
 k['ん']='n'
 for i in s:
  if i in v:d+=(w:=V[v.index(i)])
  if(W:=l.get(i,k.get(i))):d+=(w:=(W[0]*(t+1)+W[1:]));t=0
  if'゛'==i and u!='ふ':d=d[:-1*len(w)]+(w:=q.get(u,g.get(w[0],w[0])+w[1]));I=1
  if'゜'==i:d=d[:-1*len(w)]+(w:='p'*len(w[:-1])+w[-1])
  if i in j:d=d[:-1*len(w)]+(w:=w[:-1]+j[i][i in['し','ち']:])
  if i=='っ':t=1
  u=i
 return d

```

Try it online!

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


# Question
Title: Deranged !Combinatorics: Compute the Subfactorial
The **subfactorial** or **rencontres numbers** (A000166) are a sequence of numbers similar to the factorial numbers which show up in the combinatorics of permutations. In particular the **n**th subfactorial **!n** gives the number of derangements of a set of **n** elements. A derangement is a permutation in which no element remains in the same position. The subfactorial can be defined via the following recurrence relation:

```
!n = (n-1) (!(n-1) + !(n-2))

```

In fact, the same recurrence relation holds for the factorial, but for the subfactorial we start from:

```
!0 = 1
!1 = 0

```

(For the factorial we'd have, of course, **1! = 1**.)

Your task is to compute **!n**, given **n**.

## Rules

Like the factorial, the subfactorial grows very quickly. It is fine if your program can only handle inputs **n** such that **!n** can be represented by your language's native number type. However, your *algorithm* must in theory work for arbitrary **n**. That means, you may assume that *integral* results and intermediate value can be represented exactly by your language. Note that this excludes the constant **e** if it is stored or computed with finite precision.

The result needs to be an exact integer (in particular, you cannot approximate the result with scientific notation).

You may write a program or a function and use any of the standard methods of receiving input and providing output.

You may use any programming language, but note that these loopholes are forbidden by default.

This is , so the shortest valid answer – measured in *bytes* – wins.

## Test Cases

```
n     !n
0     1
1     0
2     1
3     2
4     9
5     44
6     265
10    1334961
12    176214841
13    2290792932
14    32071101049
20    895014631192902121
21    18795307255050944540
100   34332795984163804765195977526776142032365783805375784983543400282685180793327632432791396429850988990237345920155783984828001486412574060553756854137069878601

```

# Answer
> 20 votes
## Funciton, 336 bytes

Byte count assumes UTF-16 encoding with BOM.

```
┌─╖┌─╖  ┌─╖
│f╟┤♭╟┐┌┤♭╟┐
╘╤╝╘═╝├┘╘═╝├────┐
 │┌─╖ │ ┌┐┌┘╔═╗╓┴╖
 ││f╟─┴┐└┴┼─╢0║║f║
 │╘╤╝  │  │ ╚═╝╙─╜
 │┌┴╖ ┌┴╖┌┴╖ ╔═╗
 ││+╟┐│×╟┤?╟┐║1║
 │╘╤╝│╘╤╝╘╤╝┘╚╤╝
 └─┘ └─┘  └───┘

```

This defines a function `f` which takes one integer and outputs another integer at a 90 degree turn to the left. It works for arbitrarily large inputs.

Try it online!

Considering this is Funciton it's even *reasonably* fast (n = 20 takes about 14 seconds on TIO). The main slowdown comes from the double-recursion, as I don't think the Funciton interpreter automatically memoises functions.

Unfortunately, some monospaced fonts don't correctly monospace the  and/or insert small gaps between the lines. Here's a screenshot of the code from TIO in all its beauty:

I think it might be possible to golf this some more, e.g. by changing the condition from `>0` to `<1` and swapping the branches of the conditional, so that I could reuse the number literal, or maybe by using a completely different formula, but I'm quite happy with how compact it is already.

### Explanation

This basically implements the recursion given in the challenge, although it uses the base case **!(-1) = !0 = 1**. **n-1** and **n-2** are computed with the predecessor function , and the intermediate result **n-1** is reused in three places. There isn't much more to it, so I'll just quickly go through the control flow:

```
               ─┐
               ╓┴╖
               ║f║
               ╙─╜

```

This is the function header which emits the function's input **n** long the attached line. This immediately reaches T-junction, which simply duplicates the value.

```
        ┌┐┌┘╔═╗
        └┴┼─╢0║
          │ ╚═╝

```

The `0` box is just a numeric literal. A 4-way junction computes two functions: the path that leads off the bottom computes **0 \< n**, which we'll use to determine the base case. The path that goes left separately computes **0 \<\< n** (a left-shift), but we discard this value with the Starkov construct.

```
         ┌┴╖ ╔═╗
         ┤?╟┐║1║
         ╘╤╝┘╚╤╝
          └───┘

```

We lead this into the three-way conditional `?`. If the value is false, we return the constant result `1`. The loose end right of the `?` is the function output. I'm twisting it around by 180 degrees here, so that the relative orientation of input and output of `f` is more convenient in the rest of the program.

If the condition was true, then the other value will be used. Let's look at the path that leads to this branch. (Note that Funciton's evaluation is actually lazy so that this branch will never be evaluated if it's not needed, which makes the recursion possible in the first place.)

```
        ┌─╖
      ┐┌┤♭╟┐
      ├┘╘═╝
      │
     ─┴┐

```

In the other branch we first compute **n-1** and then split the path twice so we get three copies of the value (one for the coefficient of the recurrence, one for the first subfactorial, the last for **n-2**).

```
┌─╖┌─╖
│f╟┤♭╟
╘╤╝╘═╝
 │┌─╖
 ││f╟
 │╘╤╝
 │┌┴╖
 ││+╟
 │╘╤╝
 └─┘

```

Like I said, we decrement one copy again with another , then we feed both **n-1** and **n-2** recursively to `f` and finally add the two results together in the `+`.

```
       ┐
       │
      ┌┴╖
     ┐│×╟
     │╘╤╝
     └─┘

```

All that's left is to multiply **n-1** by **!(n-1) + !(n-2)**.

# Answer
> 13 votes
# Oasis, 5 bytes

Uses the formula given by Martin. Code:

```
+n<*X

```

Dissected version:

```
+n<*

```

with `a(0) = 1` and `a(1) = 0`.

Explanation, `a(n) =`:

```
+       # Add the previous two terms, a(n - 1) + a(n - 2).
 n<     # Compute n - 1.
   *    # Multiply the top two elements.

```

Try it online!

# Answer
> 10 votes
# Haskell, 25 bytes

```
f 0=1
f n=n*f(n-1)+(-1)^n

```

Try it online! Uses the other recurrence from the OEIS page.

# Answer
> 7 votes
# Jelly, 7 bytes

```
R=Œ!Ḅċ0

```

This approach constructs the derangements, so it's rather slow.

Try it online!

### How it works

```
R=Œ!Ḅċ0  Main link. Argument: n

R        Range; yield [1, ..., n].
  Œ!     Yield all permutations of [1, ..., n].
 =       Perform elementwise comparison of [1, ..., n] and each permutation.
    Ḅ    Unbinary; convert each result from base 2 to integer. This yields 0 for
         derangements, a positive value otherwise.
     ċ0  Count the number of zeroes.

```

# Answer
> 7 votes
# Brachylog (2), 11 bytes

```
⟦₁{p:?\≠ᵐ}ᶜ

```

Try it online!

## Explanation

This is basically just a direct translation of the spec from English to Brachylog (and thus has the advantage that it could easily be modified to handle small changes to the specification, such as finding the number of derangements of a specific list).

```
⟦₁{p:?\≠ᵐ}ᶜ
⟦₁           Start with a list of {the input} distinct elements
  {      }ᶜ  Then count the number of ways to
   p         permute that list
      \      such that taking corresponding elements
    :?       in {the permutation} and the list of distinct elements
       ≠     gives different elements
        ᵐ    at every position

```

# Answer
> 5 votes
# Languages with built-in solutions

Following xnor's suggestion this is a CW answer into which trivial solutions based on a single built-in to compute the subfactorial or generate all derangements should be edited.

## Mathematica, 12 bytes

```
Subfactorial

```

# Answer
> 5 votes
# Python 3, ~~35~~ 32 bytes

```
f=lambda n:n<1or(-1)**n+n*f(n-1)

```

This uses the recurrence relation **!n = n !(n-1) + (-1)n** from @Laikoni's Haskell answer, with base case **!0 = 1**.

Try it online!

# Answer
> 5 votes
# MATL, ~~9~~ 8 bytes

```
:tY@-!As

```

Similarly to @Dennis' Jelly answer, this actually builds the permutations and counts how many of them are derangements; so it is slow.

Try it online!

```
:     % Input n implicitly: Push [1 2 ... n]
t     % Duplicate
Y@    % Matrix of all permutations, each on a row
-     % Element-wise subtract. A zero in a row means that row is not a derangement
!     % Transpose
A     % True for columns that don't contain zeros
s     % Sum. Implicitly display

```

# Answer
> 5 votes
# , 9 bytes

```
o2!÷Øe+.Ḟ

```

As you can see by removing the , **M** uses symbolic math, so there will be no precision issues.

Try it online! Not the shortest solution that has been posted, but *fast*.

### How it works

```
o2!÷Øe+.Ḟ  Main link. Argument: n

o2         Replace input 0 with 2, as the following formula fails for 0.
  !        Compute the factorial of n or 2.
   ÷Øe     Divide the result by e, Euler's natural number.
      +.   Add 1/2 to the result.
        Ḟ  Floor; round down to the nearest integer.

```

# Answer
> 4 votes
# Mathics, 21 bytes

```
Round@If[#>0,#!/E,1]&

```

I am *very* new to this and have no idea what I'm doing...

Try it online!

# Answer
> 3 votes
# 05AB1E, 8 bytes

```
ÎƒN*®Nm+

```

Try it online!

**Explanation**

```
Î         # initialize stack with 0 and input
 ƒ        # for N in range [0 ... input]:
  N*      # multiply top of stack with N
    ®Nm   # push (-1)^N
       +  # add

```

# Answer
> 3 votes
# Ruby, 27 bytes

```
f=->n{n<1?1:n*f[n-1]+~0**n}

```

`~0**n` is shorter than `(-1)**n`!

# Answer
> 3 votes
## CJam (10 bytes)

```
1qi{~*)}/z

```

Online demo.

This uses the recurrence `!n = n !(n-1) + (-1)^n`, which I derived from `n! / e` and then discovered was already in OEIS.

### Dissection

The loop calculates `(-1)^n !n`, so we need to take the absolute value at the end:

```
1     e# Push !0 to the stack
qi{   e# Read an integer n and loop from 0 to n-1
  ~   e#   Bitwise not takes i to -(i+1), so we can effectively loop from 1 to n
  *   e#   Multiply
  )   e#   Increment
}/
z     e# Take the absolute value

```

# Answer
> 3 votes
# Quipu, 73 bytes

```
\/1&1&2&1&
1&++++^^[]
++2&0&--1&
2&[][]1&++
??**%%??/\
  3&4&
  []==
  --
```

Attempt This Online!

Based on Aaroneous Miller's factorial answer.

Equivalent pseudocode:

```
  a = [0, 0, 0, 0, 0]    // implicitly
0:
  a[0] = input + 1
  goto 2
1:
  a[1] = (a[1] + 1) * a[2] - a[3]
2:
  a[2] = (a[2] + 1) % a[0]
  if a[2] == 0 goto 4
3:
  a[3] = 2 - a[3]
  goto 1
4:
  a[4] = a[1] + 1
  print a[4]

```

# Answer
> 2 votes
# MATLAB, 33 bytes

```
@(n)(-1)^n*hypergeom([1 -n],[],1)

```

Anonympus function that uses the formula in Section 3 of *Derangements and applications* by Mehdi Hassani.

Example use:

```
>> @(n)(-1)^n*hypergeom([1 -n],[],1)
ans =
    @(n)(-1)^n*hypergeom([1,-n],[],1)
>> ans(6)
ans =
   265

```

# Answer
> 2 votes
## JavaScript (ES6), 26 bytes

```
f=n=>!n||n*f(n-1)-(~n%2|1)

```

Uses the recurrence relation from @Laikoni's answer. In ES7 you can save a byte by using `+(-1)**n` instead of `-(~n%2|1)`.

# Answer
> 2 votes
### PostScript, ~~81~~ ~~76~~ 69 bytes

Here are implementations of both formulae.

n\*f(n-1)+(-1)^n

~~/f{dup 0 eq{pop 1}{dup dup 1 sub f mul exch 2 mod 2 mul 1 sub sub}ifelse}def~~

```
/f{dup 0 eq{pop 1}{dup dup 1 sub f mul -1 3 2 roll exp add}ifelse}def

```

That version outputs a float. If it's necessary to output an integer:

```
/f{dup 0 eq{pop 1}{dup dup 1 sub f mul -1 3 2 roll exp cvi add}ifelse}def

```

which weighs in at 73 bytes.

The other formula is a little longer: 81 bytes.

(n-1)\*(f(n-1)+f(n-2))

```
/f{dup 1 le{1 exch sub}{1 sub dup f exch dup 1 sub f 3 -1 roll add mul}ifelse}def

```

These functions get their argument from the stack, and leave the result on the stack.

You can test the functions, either in a file or at an interactive PostScript prompt (eg GhostScript) with

```
0 1 12{/i exch def [i i f] ==}for

```

**output**

```
[0 1]
[1 0.0]
[2 1.0]
[3 2.0]
[4 9.0]
[5 44.0]
[6 265.0]
[7 1854.0]
[8 14833.0]
[9 133496.0]
[10 1334961.0]
[11 14684570.0]
[12 176214848.0]

```

Here's a complete PostScript file which renders the output to the screen or a printer page. (Comments in PostScript start with `%`).

```
%!PS-Adobe-3.0

% (n-1)*(f(n-1)+f(n-2))
% /f{dup 1 le{1 exch sub}{1 sub dup f exch dup 1 sub f 3 -1 roll add mul}ifelse}def

% n*f(n-1)+(-1)^n
/f{dup 0 eq{pop 1}{dup dup 1 sub f mul -1 3 2 roll exp add}ifelse}def

% 0 1 12{/i exch def [i i f] ==}for

/FS 16 def              %font size
/LM 5 def               %left margin
/numst 12 string def    %numeric string buffer

/Newline{currentpoint exch pop FS sub LM exch moveto}def
/Courier findfont FS scalefont setfont
LM 700 moveto

(Subfactorials) Newline
0 1 12{
    dup numst cvs show (: ) show f numst cvs show Newline
}for
showpage
quit

```

# Answer
> 2 votes
# Raku, 22 bytes

```
1,{++$*$_+($*=-1)}...*

```

Try it online!

This is an expression for the infinite sequence of subfactorials.

# Answer
> 2 votes
# Python 3, 27 bytes

```
f=lambda n:n<1or f(n-1)*n^1

```

Try it online!

Based on @Laikoni's formula and the observation that *n* and !*n* always have opposite parity.

Broken down:

n odd -\> n x !(n-1) also odd -\> adding (-1)^n=-1 is the same as unsetting the lowest bit

n even -\> n x !(n-1) also even -\> adding (-1)^n=1 is the same as setting the lowest bit

therefore flipping the lowest bit works in either case

# Answer
> 1 votes
# PHP, 69 Bytes

```
function f($i){return$i>1?$i*f($i-1)+(-1)**$i:1-$i;}echo f($argv[1]);

```

use this way `a(n) = n*a(n-1) + (-1)^n`

# Answer
> 1 votes
# PHP, 50 44

```
for(;$i++<$argn;)$n=++$n*$i-$i%2*2;echo$n+1;

```

Run with `echo <n> | php -nR '<code>`

The beauty of `a(n) = n*a(n-1) + (-1)^n` is that it depends only on the previous value. This allows it to be implemented iteratively instead of recursively. This saves a long *function* declarition.

*-6 bytes* by @Titus. Thanks !

# Answer
> 1 votes
# Alice, ~~20~~ 18 bytes

```
1/o
k\i@/&wq*eqE+]

```

Try it online!

### Explanation

This uses the recursion from Laikoni's answer, **!n = n !(n-1) + (-1)n**. Similar to the Funciton answer, I'm using the base case **!(-1) = 1**. We put that **1** on the stack with `1.`. Then this...

```
.../o
...\i@/...

```

... is just the usual decimal I/O framework. The main code is actually

```
&wq*eqE+]k

```

Broken down:

```
&w    Push the current IP address N times to the return address stack, which
      effectively begins a loop which will be executed N+1 times.
  q     Push the position of the tape head, which we're abusing as the
        iterator variable n.
  *     Multiply !(n-1) by n.
  e     Push -1.
  q     Retrieve n again.
  E     Raise -1 to the nth power.
  +     Add it to n*!(n-1).
  ]     Move the tape head to the right.
k     Jump back to the w, as long as there is still a copy of the return
      address on the return address stack. Otherwise, do nothing and exit
      the loop.

```

# Answer
> 1 votes
# Julia 1.0, 21 bytes

```
!n=n<1||n*!~-n+(-1)^n

```

Try it online!

with the following formula from the OEIS page: $$ a(0)=1,\ a(n) = n\*a(n-1) + (-1)^n $$

# Answer
> 1 votes
# TI-Basic, ~~12~~ 19 bytes

```
Ans!∑((-1)^K/K!,K,0,Ans

```

with the following formula from the OEIS page: $$ a(n) = n!\*\sum\_{k=0..n}(-1)^k/k! $$

### previous answer (12 bytes)

```
round(Ans!/,0)+not(Ans

```

this is invalid because  (euler number) is stored with limited precision, which is explicitly forbiden by the challenge

# Answer
> 1 votes
# 05AB1E, 8 bytes

```
0Lλè+N<*

```

I know there is already a great 8 bytes 05AB1E answer, but this uses a completely different approach.

Try it online or verify all test cases.

**Explanation:**

```
  λ       # Start a recursive environment,
   è      # to output the (implicit) input'th value
0L        # Starting with a(0)=1 and a(1)=0
          # Where every following a(n) is calculated as:
    +     #  Add two values together
          #  (since + requires 2 arguments, it implicitly uses a(n-2) and a(n-1))
     N<*  #  Multiplied by n-1
          # (after which the result of a(input) is output implicitly)

```

# Answer
> 1 votes
# Pari/GP, 26 bytes

```
n->n!*sum(k=0,n,(-1)^k/k!)

```

Try it online!

---

# Pari/GP, 28 bytes

```
f(n)=if(n,n*f(n-1)+(-1)^n,1)

```

Try it online!

---

# Pari/GP, 15 bytes (invalid because of finite precision)

```
n->n!\/exp(!!n)

```

Try it online!

# Answer
> 0 votes
# Actually, 18 bytes

```
;!@ur⌠;!@0Dⁿ/⌡MΣ*≈

```

Try it online!

Explanation:

```
;!@ur⌠;!@0Dⁿ/⌡MΣ*≈
;                   duplicate input
 !                  n!
  @ur               range(0, n+1) (yields [0, n])
     ⌠;!@0Dⁿ/⌡M     for each i in range:
      ;               duplicate i
       !              i!
        @0Dⁿ          (-1)**i
            /         (-1)**i/i!
               Σ    sum
                *   multiply sum by n!
                 ≈  floor into int

```

---

A 12-byte version that would work if Actually had more precision:

```
;!╠@/1½+L@Y+

```

Try it online!

Unlike all of the other answers (as of posting), this solution uses neither the recursive formula nor the summation formula. Instead, it uses the following formula:

This formula is relatively easy to implement in Actually:

```
!╠@/1½+L
!         n!
 ╠        e
  @/      divide n! by e
    1½+   add 0.5
       L  floor

```

Now, the only problem is that the formula only holds for positive `n`. If you try to use `n = 0`, the formula incorrectly yields `0`. This is easily fixed, however: by applying boolean negation to the input and adding that to the output of the formula, the correct output is given for all non-negative `n`. Thus, the program with that correction is:

```
;!╠@/1½+L@Y+
;             duplicate input
 !            n!
  ╠           e
   @/         divide n! by e
     1½+      add 0.5
        L     floor
         @Y   boolean negate the other copy of the input (1 if n == 0 else 0)
           +  add

```

# Answer
> 0 votes
# C, 34 bytes

```
a(n){return n?n*a(n-1)-n%2*2+1:1;}

```

Explanation:

```
a(n){                            } define a function called a of n
     return                     ;  make the function evaluate to...
            n?                :1   set the base case of 1 when n is 0
              n*a(n-1)             first half of the formula on the page
                      -n%2*2+1     (-1)**n

```

# Answer
> 0 votes
## Mathematica, 40 bytes

```
±0=1;±1=0;±n_:=(n-1)(±(n-1)+±(n-2))

```

Which comes in at 31 bytes under the default ISO 8859-1 encoding.

# Answer
> 0 votes
# R, 47 bytes

```
n=scan();`if`(!n,1,floor(gamma(n+1)/exp(1)+.5))

```

Uses the same formula as Mego's answer.

Alternate method, 52 bytes using the `PerMallows` library

```
n=scan();`if`(!n,1,PerMallows::count.perms(n,n,'h'))

```

# Answer
> 0 votes
# Stacked, 30 bytes

```
[:[#-::#-f\f+*]$not,\2<# !]@:f

```

Try it online!

Simple recursive function. Uses the fact that `!n = not n` for `n < 2`. Call as `n f`.

---
Tags: code-golf, sequence, number-theory, combinatorics, permutations
---


title: Shortest way to coerce to array

text:
# Question
Title: Shortest way to coerce to array
Given a variable a (non array) or (any\[\]) convert to (any\[\])

```
function example(s: string | string[]) {
   const e = Array.isArray(s) ? s: [s]
   return e
}

```

Is `Array.isArray(s) ? s: [s]` the shortest way?

# Answer
## 10 bytes

```
[s].flat()

```

This works by doing a shallow flat on `[s]`. So, if `s` is anything other than an array, nothing can be flattened and it will stay as `[s]`. But if `s` *is* an array, the outer `[]` will be flattened away, leaving a shallow clone of `s`.

Note that you can also use this to concat a number of arrays, either with other arrays or non-array elements:

```
[r,s,t].flat()

```

This is actually a trick I wasn't aware of until now. It's still a byte longer than `concat` though, if the first item's guaranteed to be an array:

```
r.concat(s,t)

```

When `r` could be anything, `[r,s,t].flat()` seems to be the best option.
> 19 votes

# Answer
aparently this works `t.map?t:[t]`
> 4 votes

---
Tags: tips, javascript
---


title: Egyptian fractions summing to n

text:
# Question
Title: Egyptian fractions summing to n
An "Egyptian fraction" is a list of *distinct* fractions with a numerator of \\$1\\$. For example:

\\$ \frac 1 1+ \frac 1 2 + \frac 1 3 + \frac 1 6 \\$

The "size" of an Egyptian fraction is just the number of terms involved.

Your task is to take a positive integer \\$n\\$ and output the smallest Egyptian fraction that sums to \\$n\\$. In the case of ties (there are ties) you may output any of the tied fractions.

Since the numerator is always 1 you may output your answer as a list of denominators instead.

This is so the goal is to minimize the size of your source code within the bounds of your chosen language and algorithm with answers being scored in bytes.

Fast answers are encouraged but must take steps to achieve the goal such as removing unnecessary whitespace or giving the variables short names. Feel free to include **(fast)** in your answer title along with the language and byte count if you do give it a go for speed.

## Precision

While our default precision is that the algorithm needs to be *theoretically* correct, if you try to do this challenge with floating point numbers you will get results that are wrong almost immediately. It's also not at all difficult to solve this challenge using only integers. For this reason in addition to being theoretically correct answers must also give correct calculations for \\$n \< 4\\$.

As an additional clarification *theoretically* correct means that you cannot for example assume some arbitrary bound on the size of the denominator to restrict your search space. Any bounds used to restrict the search space must be theoretically justified.

## Test cases

The sizes for the first 3 solutions next to a potential output are:

\\$ 1, \frac 1 1\\ 4, \frac 1 1+ \frac 1 2 + \frac 1 3 + \frac 1 6 \\ 13, \frac 1 1+\frac 1 2+\frac 1 3+\frac 1 4+\frac 1 5+\frac 1 6+\frac 1 7+\frac 1 8+\frac 1 9+\frac 1{15}+\frac 1{18}+\frac 1{40}+\frac 1{42} \\ \\$

The first two I have calculated and verified by hand. The third one was verified by a computer program that ran for about 5 seconds. Since the search space is infinite, I am not 100% sure that my program doesn't miss some potential solution. But I have hand verified that there are no solutions up to 11. And I do have a solution of size 13.

My program doesn't find a solution for 4 in a reasonable amount of time but it is easy to check that the answer is at least 31 terms long, and my program confirms that it is at least 32 terms long.

# Answer
# Haskell, 103 bytes

```
head.([1..]>>=).g 1 0
g b i a d=[[]|a<1]++[j:o|j<-[max(div(b-1)a)i+1..div(b*d)a],o<-g(b*j)j(a*j-b)$d-1]

```

Try it online!

This uses iterative deepening depth-first search, using the bound \\$\frac a{bd} ≤ \frac 1j ≤ \frac ab\\$ on the first term \\$\frac1j\\$ of a size-\\$d\\$ Egyptian fraction for \\$\frac ab\\$. Unclear if this qualifies as “fast”, but it does solve \\$n = 4\\$ in a few seconds:

\begin{split} 4 = {}&\frac11 + \frac12 + \frac13 + \frac14 + \frac15 + \frac16 + \frac17 + \frac18 + \frac19 + \frac1{10} + \frac1{11} + \frac1{12} \+ \frac1{13} \\ &+ \frac1{14} + \frac1{15} + \frac1{16} + \frac1{17} + \frac1{18} + \frac1{19} + \frac1{20} + \frac1{21} + \frac1{22} + \frac1{23} + \frac1{24} \\ &+ \frac1{25} + \frac1{26} + \frac1{27} + \frac1{28} + \frac1{30} + \frac1{34} + \frac1{100} + \frac1{11934} + \frac1{14536368}. \end{split}
> 9 votes

# Answer
# Python 3, 159 130 125 bytes

```
f=lambda x,s={1},i=1,p=1,l=[]:i<7**x**x**x and f(x,s^{i},1+i*(i in s),p*i,l+[s]*(sum(p//y for y in s)==x*p))or min(l,key=len)

```

Try it online!

Bruteforces trough all Egyptian fractions, in order of maximum denominator. A limit of \\$7^{x^{x^x}}\\$ is used to stop the program. Then the shortest fraction is picked.

Now the elephant in the room is the upper bound \\$7^{x^{x^x}}\\$. This corresponds to the maximum denominator in an optimal solution. Let's see how this bound is obtained.

Let's first make an upper bound for the length of the Egyptian fraction. To construct the egyptian fraction for `x`, we first greedily pick unit fractions, until the next one would get us over `x`. For example, if `x` is 2, then we would do \\$\frac{1}{1}+\frac{1}{2}+\frac{1}{3}\\$, stopping before \\$\frac{1}{4}\\$, since that would result in a sum greater then 2. Note that this initial tail has length less than \\$e^x\\$.

Now we have \\$2-(\frac{1}{1}+\frac{1}{2}+\frac{1}{3})=\frac{1}{6}\\$. Here we got lucky, and the difference is already a unit fraction. If it isn't, we can use the greedy algorithm to turn the difference into a unit fraction. The amount of fractions that the greedy algorithm introduces is at most the denominator of the difference. The denominator is less than the numerator which is less than \\$e^x!\\$.

Finally, if we have an integer egyptian fraction of length `l`, the numerator can be at most `l^l`. To see why, note that the numerator of the last fraction can't be greater than the product of the other numerators.

Now we have the upper bound \\$(e^x!)^{e^x!}\\$. When \\$x\ge 4\\$, \\$(e^x!)^{e^x!}\<7^{x^{x^x}}\\$. The seven takes care of values of \\$x\\$ less than 4.

Proof for \\$(e^x!)^{e^x!}\<x^{x^{x^x}}\\$:

\\$(e^x!)^{e^x!}\<((e^x)^{e^x})^{(e^x){e^x}}=(e^{xe^x})^{e^{xe^x}}=e^{xe^xe^{xe^x}}=e^{xe^{x+xe^x}}\\$

\\$x+xe^x\< x^x\\$

\\$xe^{x+xe^x} \< x^{x^x}\\$

\\$e^{xe^{x+xe^x}}\<7^{x^{x^x}}\\$
> 6 votes

# Answer
# Python 3, ~~180~~ ~~161~~ 152 bytes

```
def f(n):
 u,*r=0,(0,1,n,1)
 for l,q,a,b,*x in r:
  if(l>u>0)|a==0:u=l;o=x
  if u<1or(u-l)*b>=a*q>0:r+=(l+1,q+1,a*q-b,q*b,*x,q),(l,q+1,a,b,*x)
 return o

```

Try it online!

This does a kind of breadth-first search over sets of fractions. When it finds a first valid representation, it uses the length of that as an upper bound.
With the upper bound we can cut search branches when the target number can't be reached with the remaining number of fractions.

This only uses integer arithmetic, given enough memory and time it should be able to calculate any value.

Local results:

```
$ time python3 ef.py
1 [1]
2 [1, 2, 3, 6]
3 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 15, 230, 57960]
python3 ef.py  15.89s user 2.03s system 98% cpu 18.148 total

```

---

At the cost of ~60 bytes we can use sharper bounds for cutting the search, skip fractions that would lead to higher sums, and traverse the search tree in a depth-first order. This allows us to get \\$n=4\\$ on TIO:

```
def f(n):
 u,*r=0,(0,1,n,1)
 while r:
  l,q,a,b,*x=r.pop()
  if a*q==b:
   if(l+1>u>0)<1:u=l+1;o=x+[q]
  elif u<1or(u+~l)*b>=a*q>0:A=a*q-b;B=q*b;D,M=divmod(B,A);r+=(l,q+1,a,b,*x),(l+1,max(q+1,D+(M>0)),A,B,*x,q)
 return o

```

Try it online!
> 5 votes

# Answer
# Python3, 386 bytes:

```
def f(n):
 A,I=[1],[]
 while sum(1/i for i in A)+1/(A[-1]+1)<=n:A.append(A[-1]+1)
 q = [(A[:],n,0)]
 while 1:
  c,d,k = q.pop(0)
  if(s:=sum(1/i for i in c))==n:return c
  F=1
  if d:
   l= c[-1]
   while (s+1/(l:=l+1))>n or l in I:
    if l>10e7:I.append(A.pop());q=[(A[:],n,0)];F=0;break
   if F:q.append((c+[l],d-(k:=l>(c[-1]+1)),k))
  if k and F:
   q.append((c[:-1]+[c[-1]+1],d,k))

```

Try it online!

Local results (Macbook Pro):

```
1 [1]
2 [1, 2, 3, 6]
3 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 15, 230, 57960]
4 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 31, 32, 33, 34, 45, 7397, 82673165]
python3 egyptian_tests.py  29.14s user 0.15s system 99% cpu 29.480 total

```
> 0 votes

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


# Question
Title: Perl: eval an unpacked hex value passed through any level of ssh
## Task

Make code given on the command line that takes an unpacked hex value as input and `eval`s that in Perl. Like this:

```
perl -e 'map{eval}pack q/h*/,q/072796e6470222458656275672370202d6f62756020222b302072796e6470222478616e60202f6e6560202771697020247f6020246f602029647e2c5e622/'

```

But with one additional restriction: Your code must survive any level of `ssh`

(and the example above does not survive because the space would need to be quoted:

```
# This does not work
ssh server perl -e 'map{eval}pack q/h*/,q/072796e6470222458656275672370202d6f62756020222b302072796e6470222478616e60202f6e6560202771697020247f6020246f602029647e2c5e622/'
# This would survive 1 level of ssh but not 2
ssh server perl -e 'map{eval}pack\ q/h*/,q/072796e6470222458656275672370202d6f62756020222b302072796e6470222478616e60202f6e6560202771697020247f6020246f602029647e2c5e622/'

```

)

So:

```
ssh server your_code hexvalue
ssh server ssh server2 your_code hexvalue
ssh server ssh server2 ssh server3 your_code hexvalue

```

should all give the same result. You will not be told the number of levels of `ssh`.

You can assume the login shell is bash.

You can choose to include the hex value in the program (in which case it obviously does not count towards the length of your code) or have it given as an argument to your program.

You are also allowed to preprocess the hex value (e.g. convert it to another format) and use that value instead. But you cannot do the `eval` locally: It must be run on the remote server. The preprocessing code is of course also code thus also part of the byte count.

## Test

Given the value:

```
072796e6470222458656275672370202d6f62756020222b302072796e6470222478616e60202f6e6560202771697020247f6020246f602029647e2c5e622

```

your program should print:

```
There's  more  than  one  way  to  do  it.

```

And:

```
4216d3223616d656c622b302072796e6470222140242160296e6024786560246563737562747e2c5e622

```

should print:

```
A camel in the dessert.

```

Finally:

```
072796e647020686f63747e616d65606

```

should print the hostname of the server that you `ssh` to.

## Scoring

Code that only uses Perl wins over code that uses Bash+Perl which wins over code in any other languages.

In case of a tie: Code without warnings wins.

In case of a tie: Shortest code wins.

*Edit*

Clarified preprocessing is allowed, but not for free, and warnings are frowned upon, but not illegal.

# Answer
# Perl only; (+0 bytes) 23 bytes

Saved two bytes thanks to Ole Tange themself! (`'+'` -\> `+`)

```
map{eval}pack+q/h*/,q/$hexvalue/

```

Disclaimer: I have no experience with Perl whatsoever.
However, this seems to work fine, I simply replaced the single space in the example with `'+'`, which has now been golfed to just `+`.

For example:

```
ssh localhost ssh localhost [...] ssh localhost perl -e 'map{eval}pack'+'q/h*/,q/072796e647020686f63747e616d65606/'

```

(We can't seem to ssh even to `localhost` over on TIO though)
> 4 votes

# Answer
# Pure Perl 5, 6 bytes + 8 bytes for a change to the preprocessing format = 14 bytes

```
eval+v

```

Try it online!

This is followed by the code that you want to evaluate written with codepoints in decimal and separated by periods, e.g.

```
perl -e eval+v112.114.105.110.116.32.50.42.50

```

Produces a warning about ambiguous syntax (the `+` could be interpreted as either unary + (a no-op) or as addition), but the parse that Perl chooses by default works.

## Encoders

The format listed in the question is *not* the usual hex encoding; the first example starts with `07`, which in a normal hexdump, would represent the BEL character. I suspect it has been produced using code that's something like this:

```
print unpack("h*", "print 2*2")

```

(A "regular" hexdump would use the `H*` unpack format, rather than `h*`.)

To produce the format used by this answer, you unpack with `c*` rather than `h*`, and with `$,` set to `"."`:

```
$,=".";print unpack("C*", "print 2*2")

```

Encoding it using Perl therefore takes 8 more bytes than encoding the format stated in the question.

Alternatively, you can use this online encoder, written in Jelly.

## Explanation

```
eval+vn.n.n.n.n.n…
eval                 Evaluates a string literal as code
    +                No-op (used here as a whitespace substitute)
     vn.n.n.n.n.n…   String literal specified using character codes

```

All the characters in this program are invariant under shell escaping (it's just letters, digits, `+` and `.`), so it can be passed through any number of shell command lines and will remain intact.
> 0 votes

---
Tags: code-golf, perl
---


title: Golf Conway's Primordial Still-Life

text:
# Question
Title: Golf Conway's Primordial Still-Life
## Background

*Note: This configuration was co-found by one of our fellow code golf enthusiasts, Zgarb*

A 29 year old conjecture by John Conway about the Game of Life was recently solved.

To quote Conway from the linked article:

> Indeed, is there a Godlike still-life, one that can only have existed for all time (apart from things that don’t interfere with it)?

That is, a configuration in the game of life that could not have evolved but, if it exists, must have been part of the game's starting condition?

The answer is yes, such still-lifes do exist, and the first one discovered looks like this:

## Task

The challenge is simple: output this 22 by 28 primordial still-life as ascii text.

Fewest bytes wins.

Notes:

* You can choose any characters you like to represent live and dead cells.
* Trailing whitespace is allowed.
* Allowed loophole: If you discover a *different* primordial still life, you may output that.

Here it is with `x` for dead and  for live:

```
      xxxx  xxxx  xxxx  x
   xx x  xx x  xx x  xx x
   x xx  x xx  x xx  x xx
xxxx  xxxx  xxxx  xxxx  xxx
  x xx  x xx  x xx  x xx  x
 x  xx x  xx x  xx x  xx x
xxxx  xxxx  xxxx  xxxx  xxxx
x  xx x  xx x  xx x  xx x  x
x  x xx  x xx  x xx  x xx  x
xxxx  xxxx  xxxx  xxxx  xxxx
  x xx  x xx  x xx  x xx  x
 x  xx x  xx x  xx x  xx x
xxxx  xxxx  xxxx  xxxx  xxxx
x  xx x  xx x  xx x  xx x  x
x  x xx  x xx  x xx  x xx  x
xxxx  xxxx  xxxx  xxxx  xxxx
  x xx  x xx  x xx  x xx  x
 x  xx x  xx x  xx x  xx x
 xxx  xxxx  xxxx  xxxx  xxxx
   xx x  xx x  xx x  xx x
   x xx  x xx  x xx  x xx
   x  xxxx  xxxx  xxxx

```

And here it is with `1` for dead and `0` for live:

```
0000001111001111001111001000
0001101001101001101001101000
0001011001011001011001011000
1111001111001111001111001110
0010110010110010110010110010
0100110100110100110100110100
1111001111001111001111001111
1001101001101001101001101001
1001011001011001011001011001
1111001111001111001111001111
0010110010110010110010110010
0100110100110100110100110100
1111001111001111001111001111
1001101001101001101001101001
1001011001011001011001011001
1111001111001111001111001111
0010110010110010110010110010
0100110100110100110100110100
0111001111001111001111001111
0001101001101001101001101000
0001011001011001011001011000
0001001111001111001111000000

```

# Answer
> 14 votes
# Nibbles, 37 33 bytes

```
?, &" ";3
    ! = $ `. ;~ `/ $ `D -2
                :;!$ `' \@:.\$\$
             `'<14>>^_$
      `. 5 ~/$~
      ~ >@$
   @$ ~
15a

```

That's 66 nibbles, each taking half a byte in the binary form.

This could probably be improved, and will definitely be beaten by the things that specialize in ascii art as it uses rotate which nibbles doesn't have as a built in. BTW the trivially binary encoded way is 82 bytes in nibbles (use \`D -2 and reverse the result to deal with 0 prefixes).

Run it like this:

```
> nibbles life.nbl

      aaaa  aaaa  aaaa  a
   aa a  aa a  aa a  aa a
   a aa  a aa  a aa  a aa
aaaa  aaaa  aaaa  aaaa  aaa
  a aa  a aa  a aa  a aa  a
 a  aa a  aa a  aa a  aa a
aaaa  aaaa  aaaa  aaaa  aaaa
a  aa a  aa a  aa a  aa a  a
a  a aa  a aa  a aa  a aa  a
aaaa  aaaa  aaaa  aaaa  aaaa
  a aa  a aa  a aa  a aa  a
 a  aa a  aa a  aa a  aa a
aaaa  aaaa  aaaa  aaaa  aaaa
a  aa a  aa a  aa a  aa a  a
a  a aa  a aa  a aa  a aa  a
aaaa  aaaa  aaaa  aaaa  aaaa
  a aa  a aa  a aa  a aa  a
 a  aa a  aa a  aa a  aa a
aaaa  aaaa  aaaa  aaaa  aaaa
a  aa a  aa a  aa a  aa a  a
a  a aa  a aa  a aa  a aa  a
aaaa  aaaa  aaaa  aaaa  aaaa
  a aa  a aa  a aa  a aa  a
 a  aa a  aa a  aa a  aa a
 aaa  aaaa  aaaa  aaaa  aaaa
   aa a  aa a  aa a  aa a
   a aa  a aa  a aa  a aa
   a  aaaa  aaaa  aaaa

```

## How?

It starts with the basic building block of

```
# #
 ##
 #

```

which concatenated as bits is 346 or 15a in hex. This is extracted to space and 'a' with ``D -2` and put into groups of 3 with ``/ 3`

It then rotates this clockwise with transpose of the reverse ``'\` and appends the lines with `! <lhs> <rhs> :`

Finally this is rotated 180 degrees by reversing it and each line.

This constructs the basic square that you can see in the image with the hairs going out.

```
a a  a
 aaaa
 a  aa
aa  a
 aaaa
a  a a

```

This is then replicated 3 times x and y and truncated to the window (14). Then we remove 5,2,1 spaces (generated by iterating /2 starting from 5) from the front using a zip with a custom fn (drop). This is justified with `&" "` using a size of 3, but really any value \<= 14 would work since it also checks the max size of any element. 3 is used because that value is saved and used in 3 other places (saving 1 nibble each in binary form).

```
      aaaa  aa
   aa a  aa a
   a aa  a aa
aaaa  aaaa  aa
  a aa  a aa
 a  aa a  aa a
aaaa  aaaa  aa
a  aa a  aa a
a  a aa  a aa
aaaa  aaaa  aa
  a aa  a aa
 a  aa a  aa a
aaaa  aaaa  aa
a  aa a  aa a

```

The really cool thing is that the final product can also be constructed by a rotation of this. And so this rotation code is saved as a function using `;~`. It is a bit awkward to call as it needs to know the return type by calling it on some function before it is finished being defined. But here we want to call it on the result of calling it, which can't be done. So instead I take the result and put it into an if statement on a list `?,` it will be true and inside the true clause `$` will be the value we want to call the function on. The `<14>>^3` code was also repeated and had the same issue, but here I used iteration and took the 3rd element so that the code was applied twice.

Edit: Zgarb confirmed that the 28x28 version is also a still life (it is fully rotationally symmetric). This saved 2 bytes by not having to do `<11` to trunctate during the final rotation. Thanks!

# Answer
> 11 votes
# Wolfram Language (Mathematica), 131 bytes

```
Uncompress@"1:eJxTTMoPCt7DxMBgAAaGQIBGAkVjDAyNwJIGhthIuLwBRAM6CZbHYjKMhOrHpR0qj9VqCEnAfEOwPG7tcHlcDiDG/JHufgOC5lOWfsDyWMwHAQA6Moq3"

```

Try it online!

Uses `1` for dead cells, `0` for living and background (grey) cells.

A boring answer using Mathematica's `Uncompress` built-in.

---

# Wolfram Language (Mathematica) \+ my LifeFind package, 147 bytes

```
<<Life`
SeedRandom@1703
a=ArrayPad[SearchPattern[6,6,Agar->1>0][[1]],{{9,7},{9,13}},Periodic]
Do[a[[i,1;;7-2i]]=1;a=Reverse@a,4,{i,3}]
Print@@@a

```

Uses `0` for dead cells, `1` for living and background (grey) cells.

Spent some time to find the correct random seed...

I wrote this package to find interesting patterns in Conway's Game of Life and other cellular automata.

`SearchPattern[6,6,Agar->1>0]` tries to find a 6x6 stable agar. When the random seed is `1703`, it finds the following pattern:

```
 ##
#  ##
#  # #
 ##
  # ##
 #  ##

```

After that, the code pads the pattern periodically to a 22x28 array, and sets the background cells at the corners to `1` (this part takes so many bytes!), and then prints the result.

# Answer
> 6 votes
# Charcoal, 48 bytes

```
Ｇ↘³↓²↘²↓¹⁵↙³←²↙²←²¹↖³↑²↖²↑¹⁵↗³→²↗²”{“↧n⍘∨)¿UV·÷Σ

```

Try it online! Link is to verbose version of code. Works by defining a polygon that outlines the configuration and filling it with the 6×6 pattern. (The top left corner actually has coordinates `(0, -24)` but as the fill is 6×6 it comes to the same thing.)

I also tried a number of other approaches. Simply printing a compressed string took 63 bytes. Printing half of the string twice, rotating in between, took 61 bytes. Filling an array with the pattern and then deleting the corners took 54 bytes. Drawing a rectangle with the pattern and then deleting the corners took 49 bytes.

# Answer
> 6 votes
# Excel, ~~137~~ 89 characters, 171 bytes

Taylor Raine did their thing.

```
=BASE(UNICODE(MID("ó㏈ښᩨ֖ᙘ㳳㏎ବⲲፍഴ㳳㏏⚚ᩩ▖ᙙ㳳㏏ବⲲፍഴ㳳㏏⚚ᩩ▖ᙙ㳳㏏ବⲲፍഴᳳ㏏ښᩨ֖ᙘӳ㏀",SEQUENCE(22,2),1)),2,14)

```

There's a possibility the exact characters won't translate well from Excel to the browser, so here's the encoded string as list of Unicode codes instead (keeping in mind that some are two bytes wide):

```
243, 13256, 1690, 6760, 1430, 5720, 15603, 13262, 2860, 11442, 4941, 3380, 15603, 13263, 9882, 6761, 9622, 5721, 15603, 13263, 2860, 11442, 4941, 3380, 15603, 13263, 9882, 6761, 9622, 5721, 15603, 13263, 2860, 11442, 4941, 3380, 7411, 13263, 1690, 6760, 1430, 5720, 1267, 13248

```

The approach takes the (probably not optimized) approach of breaking the desired into chunks and storing those as Unicode characters. The function takes that string, converts each character to its binary equivalent, then breaks it into 2 columns of 14 bit chunks.

---

Let's start by shortening the formula. We'll refer to this whole mess as `string`:

```
"ó㏈ښᩨ֖ᙘ㳳㏎ବⲲፍഴ㳳㏏⚚ᩩ▖ᙙ㳳㏏ବⲲፍഴ㳳㏏⚚ᩩ▖ᙙ㳳㏏ବⲲፍഴᳳ㏏ښᩨ֖ᙘӳ㏀"

```

Now the formula looks like this:

```
=BASE(UNICODE(MID(string,SEQUENCE(22,2),1)),2,14)

```
* `SEQUENCE(22,2)` creates an array 2 columns wide and 22 rows tall for 44 total items in the array. `string` is 44 characters long so that'll fit nicely. It counts over then down like this:

> ```
> | 1 | 2 |
> | 3 | 4 |
> | 5 | 6 |
>
> ```

* `MID(string,SEQUENCE(~),1)` pulls out each character from `string` one at a time.
* `UNICODE(MID(~))` converts those characters to their (decimal) unicode number.
* `BASE(UNICODE(~),2,14)` converts those decimal numbers to their binary equivalent with each result padded with leading zeros so they're at least 14 bits long.

The end result is two columns of data as shown in the screenshot below. I also split out the results into individual cells and added conditional formatting to show the results visually. The formula is only in cell `A1` and the output automatically spills into the range `A1:B22`.

---

~~I don't know what kind of ritual I need to perform to summon Taylor Raine but I'm sure they can improve upon this bloated answer. I already tried using chunks longer than 16 bits but it starts breaking in weird ways.~~

# Answer
> 4 votes
# Vyxal, 87 bytes

```
»ƛUċ≬r¾□ƈ1K↵ẏǐṅȧꜝq6⟩λ∵†⇧↳∨¬ṫ«X¡„q∪[>±∩λxƒẊ[øȧẇ/hAh<∨T⅛⇧¥WnWU°⋎ƈ_S↳‡a∑⋏‡ø¨z≈cƛ÷a»₀Sτ22/⁋

```

Try it Online!

Naive base compression.

```
»...»        # Base-255 compressed integer
     ₀Sτ     # Decompress into base 22 with 1s and 0s
        22/⁋ # Split into 22 pieces and join on newlines

```

# Answer
> 4 votes
# Jelly, 85 bytes

```
“¦÷fİȷ⁻ƒỌU,ɠṘµINọþọ^°56ß~+Œ:ḟyṘdạʠȷẇḌẆ[ŻṁỤ°8zẉİ¬{ḋzỵḣuṄ}Ṗj|ĠỌ½Ɲœiḥd⁷ɦȮʋḢ/iÇØ#¤œ’Bs28Y

```

Try it online!

Boring compression approach, but hey, it beats Vyxal. Outputs `1` for dead and `0` for live.

## How it works

```
“¦÷...#¤œ’Bs28Y - Main link.
“¦÷...#¤œ’      - Compressed base-250 number; 267895893890769127503254177532545466822034310678965401690230443467397769491824224432265750760013635073235874891500166493638274198855494319824095093907255178782140555126842877012017876031
          B     - Binary
           s28  - Split into chunks of size 28
              Y - Join by newlines

```

Fun fact, using base 2 is the shortest of all approaches in the form "large compressed number, to base, split"

# Answer
> 4 votes
# 05AB1E (legacy), ~~46~~ 45 bytes

```
Ƶöb3ô4FDøí‚øJÂí«}¦22£€¦4F28£øíεN3‹i411NèFX0.;

```

Port of *@DarrenSmith*'s Nibble answer, so make sure to upvote him as well!

Uses the legacy version of 05AB1E to save 2 bytes, since it can zip/transpose with lists of strings, whereas the new version requires a character-matrix instead.

Outputs as a list of lines, with `1`/`0` for dead/alive respectively.

Try it online (feel free to remove the footer to see the actual output).

**Explanation:**

```
Ƶö                  # Push compressed integer 346
  b                 # Convert it to binary: 101011010
   3ô               # Split it into parts of size 3: ["101","011","010"]
4F                  # Loop 4 times:
  D                 #  Duplicate the list of strings
   øí               #  Rotate it 90 degrees clockwise:
   ø                #   Zip/transpose; swapping rows/columns
    í               #   Reverse each inner string
     ‚              #  Pair it together with the original list of strings
      ø             #  Zip/transpose to create pairs of lines
       J            #  Join those inner pairs together to a single line
        Â           #  Bifurcate this list (short for Duplicate & Reverse copy)
         í          #  Reverse each line in the reversed copy
          «         #  Merge these lines to the list
 }                  # Close the loop
                    # (we now have a grid of 48x48 characters)
  ¦                 # Remove the first line
   22£              # Then keep just the first 22 lines
      €             # Map over each remaining line:
       ¦            #  Remove the first character
4F                  # Loop 4 times again:
  28£               #  Keep just (up to) the first 28 characters
  øí                #  Rotate 90 degrees clockwise again
    ε               #  Map over each line:
     N3‹i           #   If this is one of the first three lines:
         411Nè      #    Index the map-index into [4,1,1]
              F     #    Loop that many times:
               X0.; #     Replace the first 1 with a 0
                    # (after which the list of lines is output implicitly)

```

See this 05AB1E tip of mine (section *How to compress large integers?*) to understand why `Ƶö` is `346`.

# Answer
> 3 votes
# JavaScript (Node.js), 193 bytes

```
(x='xxxx  ',y='xx x  ',z='x xx  ',h=`      ${e=x+x+x}x
 ${g='  '+y+y+y+y}
 ${c='  '+z+z+z+z}
${b=e+x+'xxx'}
${c}x
 x${g}
${b}x
x${g}x
x${c}x
${b}x
${c}x `)=>h+`
`+[...h].reverse().join``

```

Try it online!

Here we go...

A lot of variables, dollar signs, curly braces, single quotes, pluses, and a tiny reverse at the end.

# Answer
> 3 votes
# Excel, 111 bytes

```
AO1 =IF(I1:AJ22,,INDEX(A1:F6,MOD(ROW(6:27),6)+1,MOD(COLUMN(F:AG),6)+1))

```

Link to Spreadsheet

`A1:F6` contains the repeating pattern. `I1:AJ22` contains a mask for blank cells. Takes advantage of the spreadsheet structure. The code is 67 bytes, pattern is 20 bytes, mask is 24 bytes for a total of 111 bytes.

Not as clever as @EngineerToast 's answer but it gets the job done.

# Answer
> 2 votes
# JavaScript (ES6),  ~~113~~  106 bytes

Outputs a string of `0`'s and `1`'s.

```
f=(n=616)=>--n&&((x=n>>8?615-n:n,y=x/28|0,x%=28)>=5>>y&x<24+y+!y&21703951>>x%6+y%6*45%71)+[`
`[n%28]]+f(n)

```

Try it online!

### How?

We use the following formula to get the state of the cell of the \\$6\times6\\$ pattern at \\$(x,y)\\$:

```
21703951 >> x + y * 45 % 71

```

The cell is alive if the result is odd or dead if it's even.

Notes:

* Because bitwise operations are limited to 32 bits, we cannot use a 36-bit bitmask.
* The value of the shift is implicitly reduced modulo \\$32\\$ as per the ECMAScript specification.

Try it online!

# Answer
> 1 votes
# Ruby, 108 bytes

```
j=4
28.times{|i|printf"%022b
","O)YO24"[i%6].ord%64*266305&2**(23-k=j.abs)-2**k>>1-(i-4)%24/23
i%23<4&&j-=1}

```

Try it online!

Prints the pattern rotated 90 degrees (which per comments from OP is allowed because it's still primordial.)

The output is a binary matrix produced line by line as the bitwise `AND` of the following:

```
"O)YO24"[i%6].ord%64*266305

```

Four copies of the repeating pattern (the character encodes the bitmap, the `%64` removes spurious bits to the left and the constant `266305` is `100000100000100001` in binary)

```
2**(23-k=j.abs)-2**k>>1-(i-4)%24/23

```

This is a mask consisting of a long string of `1`'s followed by a short string of `0`'s according to the formula `2**(23-k)-2**k`.

As the pattern gets wider, `k` reduces from 4 to 0, stops reducing, then increases back to 4. This is done by varying `j` on the last line.

To ensure the spurious output in the 23rd and 24th bits (those on the left) are deleted, the mask must be shifted one place to the right. But to get the pinwheel effect this should not occur on the 4th and 28th row. This is achieved by `>>1-(i-4)%24/23`

# Answer
> 0 votes
# Perl 5 \+ `-p0513`, 95 bytes

Outputs `0`s and `1`s, transliterated in the link.

```
$_=unpack"B*",'..<...h.Ye.<..'.',..$.M4..<...i.Ye.<..'x2 .',..$.M4s.<...h.Ye.<..';s/.{28}\K/./g
```

Try it online!

## Explanation

`unpack`s the binary representation from characters (repeating the duplicated section in the middle using string repetition - `x`) before inserting newlines every 28 characters. Probably not optimal but, was do-able on mobile!

---
Tags: code-golf, ascii-art, kolmogorov-complexity, game-of-life
---


title: Is this continuous terrain? Part II

text:
# Question
Title: Is this continuous terrain? Part II
*Caves and Cliffs edition*

Part 1, Very related

You're given a piece of ASCII art representing a piece of land, like so:

```
   /‾\         _ __
__/ _/         \‾
  _/  __/‾\     |
 /   /     ‾\   |
 \_/‾        \_/

```

But unlike in the previous challenge, the terrain is mountainous, with caves and cliffs, and can turn back on itself. Also, a new character is introduced, `|`, which can connect to any of its four corners.

Since an overline () is not ASCII, you can use a `~` or `-` instead.

Your challenge is still to determine if it is connected by the lines of the characters such that a single line connects them all without backtracking or crossing itself. For example, the above can be traced like so:

To clarify the connections:

* `_` can only connect on the bottom on either side
* (or `~` or `-`) can only connect on the top on either side
* `/` can only connect on the top right and bottom left
* `\` can only connect on the top left and bottom right
* `|` can connect on all four corners, but not to anything that connects to more than one corner. `|` must have a single connection above itself and a single connection below.

That one's a bit confusing, so the following are legal:

```
|
 \

|
\

 _
|_

‾|
/

```

And the following aren't:

```
|
‾
_
|

||

```

It doesn't matter where the connections start and end as long as they're all connected. Note that one line's bottom is the next line's top, so stuff like this is allowed:

```
_
 ‾

\
 \

 _
/

\
 ‾

```

You can assume input will only contain those characters plus spaces and newlines, and will contain at least one non-space character per column.

Input can be taken as ASCII art, an array of rows, a character matrix, etc.

## Testcases

Separated by double newline.

Truthy:

```
\
 \

\_
  \ /\/\_
   ‾     \

/\
  \/

\_
  ‾\

   /‾\
__/   ‾\_
         \_/‾\
              \

   /‾\         _ __
__/ _/         \‾
  _/  __/‾\     |
 /   /     ‾\   |
 \_/‾        \_/

/‾\
\ /
/ \

____   _
 ___| | |
|  ___| |
| |___  |
|___  | |
 ___| | |
|_____| |

 _
/ \  _
| |_|

 _
|_\

```

Falsy:

```
/
 \

//

 ‾‾
/  \

‾
 _

\____/
      /‾‾‾\

\_
/

| |
‾‾‾

|_|
| |

```

# Answer
# Charcoal, 190 bytes

```
ＷＳ⊞υιＦυ«⸿Ｆι«Ｍ³→Ｆ№\|/κＰ|@#≡κ_Ｐ^²‾ＰV²/Ｐ/²\Ｐ\²»⸿⸿»Ｊ⁰¦⁰Ｆυ«⸿Ｆι«Ｍ³→≡κ|Ｆ⁸¿‹ ⊟ＫＤ³✳λＰ✳λ²»⸿⸿»ＵＭＫＡ⎇⁼#ιψι≔⟦⟧θＦ×³ＬυＦ×³⊕⌈ＥυＬκ«Ｊκι≔ＬΦＫＭ‹ λη¿∧‹ ＫＫ›²η⊞θ⟦ικη⟧»¿∨⁻²Ｌθ⊙θ⊖⊟ι⎚«≔⊟θηＪ⊟η⊟ηＷ⌕ＡＥＫＭ‹ κ¹✳⁻³⊟ιψ¿⊖ＬＫＡ⎚«⎚¹

```

Try it online! Link is to verbose version of code. Takes input as a list of newline-terminated strings and outputs a Charcoal boolean, i.e. `-` for continuous, nothing if not. Explanation:

```
ＷＳ⊞υι

```

Input the terrain.

```
Ｆυ«

```

Loop over the rows of the terrain.

```
⸿

```

Start each row on a new line. This is because we'll be drawing above the current line, so we want the actual drawing to start at row `0`.

```
Ｆι«

```

Loop over each character of the row.

```
Ｍ³→

```

Space the characters 3 apart. (This should be one before and two after, but unfortunately `Switch` makes doing that less golfy.)

```
Ｆ№\|/κ

```

If the current character is a `\`, `|` or `/`, then...

```
Ｐ|@#

```

... output a marker in case the character above or below is a `|`.

```
≡κ

```

Switch on the current character.

```
_Ｐ^²

```

If it's a `_` then write to the centre and the bottom left and bottom right corners of this `3×3` square.

```
‾ＰV²

```

If it's a  then write to the centre and the top left and top right corners.

```
/Ｐ/²

```

If it's a `/` then draw from the bottom left to the top right.

```
\Ｐ\²

```

If it's a `\` then draw from the top left to the bottom right.

```
»⸿⸿

```

Add another two rows so that each row is spaced 3 apart vertically as well.

```
»Ｊ⁰¦⁰

```

Jump back to the beginning.

```
Ｆυ«⸿Ｆι«Ｍ³→

```

Loop through the rows and columns as before.

```
≡κ|

```

This time, only process `|` characters.

```
Ｆ⁸

```

Check all 8 directions. (Actually directions `0` and `4` are useless, but it's easier to include them.)

```
¿‹ ⊟ＫＤ³✳λ

```

See if there's a `\`, `|` or `/` in that direction.

```
Ｐ✳λ²

```

If so then draw a connection to it.

```
»⸿⸿

```

Finish processing each row.

```
»ＵＭＫＡ⎇⁼#ιψι

```

Remove any unused `#`s.

```
≔⟦⟧θ

```

Start collecting points that do not have two neighbours.

```
Ｆ×³ＬυＦ×³⊕⌈ＥυＬκ«Ｊκι

```

Loop over each cell of the canvas, taking into account that it's offset by `2` characters to the right.

```
≔ＬΦＫＭ‹ λη

```

Get the number of neighbours of this cell.

```
¿∧‹ ＫＫ›²η

```

If this cell is not empty and does not have two neighbours, then...

```
⊞θ⟦ικη⟧

```

... add it to the list.

```
»¿∨⁻²Ｌθ⊙θ⊖⊟ι

```

If there aren't exactly two points with exactly one neighbour each, then...

```
⎚«

```

... simply clear the canvas, otherwise:

```
≔⊟θηＪ⊟η⊟η

```

Jump to one of the two ends.

```
Ｗ⌕ＡＥＫＭ‹ κ¹

```

While there is an adjacent character...

```
✳⁻³⊟ιψ

```

... erase the current character and move in that direction.

```
¿⊖ＬＫＡ

```

If there is more than one character left, then...

... simply clear the canvas, otherwise...

```
«⎚¹

```

... clear the canvas and output success.
> 4 votes

---
Tags: code-golf, ascii-art, pattern-matching
---


title: Diamond Puzzles!

text:
# Question
Title: Diamond Puzzles!
**Explanation:**

Last year in math class, on homework we would occasionally get these extremely simple, although equally annoying questions called diamond puzzles. These were basically questions where we would be given a sum, and a product then were asked to find the two numbers which when multiplied give the product, and when added give the sum. These drove me crazy, since the only way I knew how to solve them (in Algebra I) was to just list the factors of the product then see which ones added to make the sum. (Since I didn't know how to use Quadratics at the time) Not to mention, they weren't exactly challenging math. However, It just occured to me that I should have just written a program. So that is your challenge today! Write a program that can solve a diamond puzzle.

**Examples**  Apologies for the blurry image, its the best I could find. Also, ignore the numbers in bubbles.The top of the diamond is the product, the bottom is the sum, the right and left are the two numbers. Answers are as follows: (These are also your test cases)

1. 9, -7
2. -2, -1
3. 5, 8
4. -9, -9

**Rules:**

* You may not use any pre-defined functions or classes which accomplish this for you.
* Your code must be a complete program, or function which either returns or prints the answers once it finds them
* The input is the sum and product, which are inputted as a function parameters or user input

**Specifications:**

* Assume that the two numbers, the sum, and the product will always be an integer.
* The two answers will both be between -127 to 127.
* Your input will be two integers (Sum and Product).

Remember this is code-golf, so shortest byte count wins. Please title your answer with the standard ##Language Name, Byte Count

Edit: Also, Doorknob pointed out that this is essentially "factor a quadratic of form x^2 + bx + c,". That is another way to think about and approach this challenge. :D

# Answer
> 19 votes
# Jelly, ~~15~~ ~~11~~ 10 bytes

```
Hð+,_ðH²_½

```

Try it online!

The following binary code works with this version of the Jelly interpreter.

```
0000000: 48 98 2b 2c 5f 98 48 8a 5f 90  H.+,_.H._.

```

### Idea

This is based on the fact that

### Code

```
Hð+,_ðH²_½    Left input: s -- Right input: p

 ð   ð        This is a link fork. We define three links, call the left and right
              link with the input as arguments, then the middle link with the
              results as arguments.

H             Left link, dyadic. Arguments: s p

H             Halve the left input.

     ðH²_½    Right link, dyadic. Arguments: s p

      H       Halve the left input.
       ²      Square the result.
        _     Hook; subtract the right input from the result.
         ½    Apply square root to the difference.

 ð+,_         Middle link, dyadic. Arguments: (results of the previous links)

  +           Compute the sum of the results.
    _         Compute the difference of the results.
   ,          Pair.

```

# Answer
> 13 votes
# Unicorn, ~~4650~~ ~~2982~~ ~~1874~~ 1546

```
[ ✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨  (    ✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨     ( ) )  2         ✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨  (  ✨✨✨✨✨✨✨   4   ✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨     ( ) )    ✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨ ]

```

Now with goats, rainbows, and sparkles!

Hopefully shorter than Java.

---

Uses a custom encoding which can be applied with `ApplyEncoding`

## Explanation

How does this work??? With the magic of unicorns (and a little code).

Unicorn is compiled into JavaScript

Each section is separated by a space, and each section represents a character in the JavaScript code.

If the section contains unicorns, the section's character is the section's length, converted to a char code (e.g. 32 unicorns would be a space)

If the section contains goats, the section's length is doubled and then converted to a char code.

---

If the program's special chars don't show, here's a picture:

---

This is non competing because Unicorn was made after this challenge was posted.

# Answer
> 8 votes
# JavaScript ES6, ~~45~~ ~~39~~ 37* bytes

```
(q,p)=>[x=p/2+Math.sqrt(p*p/4-q),p-x]

```

* Thanks to Dennis!

# Answer
> 4 votes
# TeaScript, 22 bytes ~~30 31~~

```
[d=y/2+$s(y*y/4-x),y-d

```

Not *that* bad. Would be much shorter if I could of gotten some golfing features finished earlier such as ~~unicorn~~ unicode shortcuts

Try it online

# Answer
> 4 votes
# dc, 16

```
?ddd*?4*-v+2/p-p

```

Reads sum then product from separate lines of STDIN. -ve numbers must be entered with an underscore instead of a minus sign. e.g.

```
$ { echo 2; echo _63; } | dc -e'?ddd*?4*-v+2/p-p'
9
-7
$

```

### Explanation:

Same basic quadratic solution for `sum = a + b` and `product = a * b`. This calculates solution `a` as:

```
a = [ sum + √( sum² - 4 * product ) ] / 2

```

And calculates solution `b` as:

```
b = sum - a

```

### Expanded:

```
?                   # push sum to stack
 ddd                # duplicate 3 times (total 4 copies)
    *               # sum squared
     ?              # push product to stack
      4*            # multiply by 4
        -           # subtract (4 * product) from (sum squared)
         v          # take square root of (sum squared) - (4 * product)
          +         # add sum to square root of (sum squared) - (4 * product)
           2/       # divide by 2 to give solution a
             p      # print with newline and without pop
              -     # subtract solution a from sum to give solution b
               p    # print with newline and without pop

```

Dividing by 2 is done late to prevent loss precision. It is possible to divide by 2 earlier, but this requires fractional precision which needs more characters.

# Answer
> 3 votes
# MATL, 33 bytes

```
-100:100t!2$t+i=bb*i=&2#2$1fv101-

```

Outputs the two numbers in two different lines. If no solution exists it produces no output. If several solutions exist it produces only the pair of numbers corresponding to one solution.

### Example

The following was run in Octave with the current GitHub commit of the compiler.

```
>> matl -r '-100:100t!2$t+i=bb*i=&2#2$1fv101-'
> 2
> -63
 9
-7

```

### Explanation

```
-100:100           % row vector -100, -99, ..., 100
t!                 % duplicate and transpose into column vector
2$t                % duplicate the two vectors
+                  % sum with singleton expansion (all combinations)
i=                 % does it equal input? Produces logical matrix
bb                 % move the two vectors to top
*                  % multiply with singleton expansion (all combinations)
i=                 % does it equal input? Produces logical matrix
&                  % logical "and"
2#2$1f             % find row and column of the first "true" value in logical matrix
v101-              % concatenate vertically and subtract 101

```

# Answer
> 3 votes
# Julia, ~~46~~ ~~44~~ 32 bytes

```
f(b,c)=(x=b+√(b^2-4c))/2,b-x/2

```

An function f that takes the sum and then the product.

My first Julia answer. @AlexA., you should be proud of me.

Thanks @Dennis and @Alex A. for all the help. I got to cross out the 44. :P

# Answer
> 3 votes
# Pyth, ~~21~~ 18 bytes

*Saved 3 bytes thanks to @Dennis*

```
,J/+@-^Q2*4E2Q2-QJ

```

Test suite

My second Pyth program ever, so it can probably be golfed with built-ins. Suggestions are welcome!

### How it works

```
,J/+@-^Q2*4E2Q2-QJ   Implicit: Q = first line of input
,                    Create and output a list of these items:
 J                     Set variable J to the result of these operations:
      ^Q2                Square Q.
     -   *4E             Subtract 4*(next line of input).
    @       2            Take the square root.
   +         Q           Add Q.
  /           2          Divide by 2.
                       The list is currently [J].
               -QJ     Push Q-J; the list is now [J, Q-J].
                     EOF; list is sent to output.

```

(This explanation may not be 100% correct; I'm not very familiar with Pyth.)

Note that `/` is integer division. By replacing it with `c`, we could make this work with non-integer inputs as well.

# Answer
> 3 votes
# Python 3, ~~49~~ 44 bytes

There are probably some ways to golf this down even further, but this looks pretty good as is.

```
def f(s,p):s/=2;d=(s*s-p)**.5;return s+d,s-d

```

# Answer
> 3 votes
# Java , 82 (69 λ) bytes with quadratic formula (127 (114 λ) bytes brute-force)

*Brute-Force: (Vanilla, Java 7)*

```
int[] n(int s,int p){for(int a=-100;a<=100;a++)for(int b=-100;b<=100;b++) if(a+b==s&&a*b==p)return new int[]{a,b};return null;}

```

*λ-enhanced: (Java 8)*

```
(s,p)->{for(int a=-100;a<=100;a++)for(int b=-100;b<=100;b++) if(a+b==s&&a*b==p)return new int[]{a,b};return null;}

```

Assign lambda to `java.util.function.BiFunction<Integer, Integer, int[]>` and call `apply()`.

Plain old brute-force approach. Just the working function is here, and since Java can't return multiple values, we return a 2-element `int` array with the required numbers.

The full brute-force approach based program can be found here on ideone.com, with λ version here.

Golfing this involved removing all unnecessary braces.

*Ungolfed:*

```
int[] n(int s,int p){//sum and product as function parameters,in that order
    for(int a=-100;a<=100;a++){//iterate first no. from -100 to 100
        for(int b=-100;b<=100;b++){//iterate second no. from -100 to 100
            //if the 2 nos. satisfy the diamond-puzzle condition,
            //pack them in an int array and return them
            if(a+b==s&&a*b==p)return new int[]{a,b};}
     }//if no such pair exists, return null
return null;}

```

*Quadratic Approach: (Vanilla, Java 7)*

```
int[] n(int s,int p){int x=s+(int)Math.sqrt(s*s-4*p);return new int[]{x/2,s-x/2};}

```

*λ-enhanced: (Java 8)* (s,p)-\>{int x=s+(int)Math.sqrt(s\*s-4\*p);return new int\[\]{x/2,s-x/2};}

(Usage as for brute-force λ above).

Parameters and return criteria are the same as the brute-force solution above.

Uses the good old quadratic formula used by almost all other answers here, and cannot be golfed down much further unless someone helps me out here. It's pretty clear so I'm not including an ungolfed version.

The full quadratic approach based program is here on ideone.com, with λ version here.

# Answer
> 3 votes
# convey, 52 bytes

```
{?~1
4*"v
 v*#2
`-.v
*%2v
.10-`
v0 v"
"-v,<
>,+
 2%}

```

Try it online!

Golfed version of this answer.

# Answer
> 2 votes
## Japt, ~~28~~ ~~22~~ ~~21~~ 20 bytes

```
[X=V/2+(V²/4-U ¬V-X]

```

Input is made in the form of `-63 2`.

Explanation:

* `U` and `V` are the two inputs (`-63` and `2` in the first case)
* `²` squares the number
* `q` extracts the square root

# Answer
> 2 votes
# APL, ~~27~~ 21 bytes

```
h(+,-).5*⍨⊣-⍨h×h←.5×⊢

```

This is a dyadic function train that accepts integers on the right and left and returns an array. To call it, assign it to a variable.

Ungolfed:

```
                h←.5×⊢       ⍝ Define a train h for halving the input
              h×             ⍝ b^2/4
          ⊣-⍨                ⍝ b^2/4 - c
      .5*⍨                   ⍝ sqrt(b^2/4 - c)
h(+,-)                       ⍝ Return the halved pair

```

Try it online

Saved 6 bytes thanks to Dennis!

# Answer
> 2 votes
# CJam, 18 bytes

```
q~2d/_2#@-mq_2$+p-

```

Try it online!

### How it works

```
q~                  e# Read an evaluate all input. STACK: product sum
  2d/               e# Divide the sum by 2.0.
     _              e# Push a copy of the result.
      2#            e# Square the copy.
        @-          e# Rotate the product on top and subtract it from the square.
          mq        e# Apply square root.
            _2$     e# Push copies of the root and the halved sum.
               +p   e# Add and print.
                 -  e# Subtract the originals.

```

# Answer
> 1 votes
**MathCAD 15. 38 Bytes**

With a mathematical formula, programming in MathCAD is easy. The language is even designed to handle complex numbers with ease. However there are shorter languages that can solve the problem.

# Answer
> 1 votes
# , 21 chars / 30 bytes

```
[x=í/2+√ í²/4-î⦆,í-x]

```

`Try it here (Firefox only).`

Meh. This should be visual enough for y'all to get the idea; however, if you must, `î = input1, í = input2`.

# Answer
> 1 votes
## wx `d`, ~~14~~ 12 bytes

Just  with a few instructions added.

```
○Äπ√akû▀╧Θ°v

```

Decompressed:

```
a*S4*-Q+2/:aS-

```

# Answer
> 1 votes
# , 12 bytes

```
1-@>@{p.@,&1

```

Try it online!

# Answer
> 1 votes
# APL (Dyalog Unicode), 14 bytesSBCS

```
⊣(⊢,-)(⊢×-)⍣¯1

```

Try it online!

A tacit function whose left arg is the sum and the right is the product. Finds one solution to the quadratic equation using the built-in numerical solver, and then gives both solutions based on the result.

The "power operator" `f⍣n` runs the function `f` `n` times, but if `n` is negative, runs the *inverse* of `f` `-n` times. The inverse of `f` is, in the numerical point of view, equivalent to solving the equation `f x = y` with a given value of `y`. Dyadic form `a(f⍣n)y` solves `(a f x) = y`.

### How it works

```
⊣(⊢,-)(⊢×-)⍣¯1  ⍝ left: sum s, right: product p
      (⊢×-)     ⍝ A function that, when left-bound with s, computes x*(s-x)
           ⍣¯1  ⍝ Find one solution to x*(s-x)=p, i.e. x^2-sx+p=0
⊣(   )          ⍝ With s as left and x as right arg,
  ⊢,-           ⍝ Give (x,s-x)

```

# Answer
> 0 votes
## PHP, 62 bytes

```
<?=($x=($p=$_GET[p])/2+sqrt($p*$p/4-$q=$_GET[q]))." ".($p-$x);

```

This could be pretty long but being full-featured PHP web-"program". Accepts the arguments via the "get" request.

Demo.

# Answer
> 0 votes
# TI-BASIC, 20 bytes

Takes `Q` from `Ans`, and `P` from `Prompt`. Call like `P:prgmNAME`.

```
Prompt P
P/2+√(P²/4-Ans
{Ans,P-Ans

```

---
Tags: code-golf, math, polynomials, factoring
---


# Question
Title: Predicting pumpkin planting plans' potential problems
You are going to be planting pumpkins soon, and you are preparing your supplies. Pumpkins come in all sorts of sizes and have their sizes written on the seed bag. A pumpkin that is size n will grow to be n units wide. However pumpkins need their space.

If a pumpkin is stuck between two other pumpkins with not enough space to reach its full size it will be ruined. So you want to make a program that takes a plan of how you are going to plant your pumpkins and determines if there is enough space for all the pumpkins.

As input it will take a list of non-negative integers. A zero will represent space with no pumpkins planted, and a positive number will represent that a pumpkin of that size will be planted there. So for example:

```
[0,0,0,1,0,0,0,0,0,5,0,0,0,6,0,0]

```

There are three pumpkins planted here of sizes `1`, `5` and `6`.

A pumpkin will grow to fill as much space as is given, but it can't detach from it's root, and it can't grow past the fence (the start and end of the list).

So for example in the above the 5 pumpkin *could* grow as follows:

```
[0,0,0,1,0,0,0,0,0,5,0,0,0,6,0,0]
           ^^^^^^^^^

```

Since that is 5 units wide and contains the place we planted it. But it *can't* grow like:

```
[0,0,0,1,0,0,0,0,0,5,0,0,0,6,0,0]
         ^^^^^^^^^

```

Because even though that is 5 units wide it doesn't include the root.

In perhaps a miracle of nature, pumpkins will push each other out of the way if they get in space they need. So for example if the `5` starts growing to the right, the `6` will push it back to the left since it needs that space.

Ultimately this means if there is a valid way for the pumpkins to grow without ruining each other they will.

It's only when there isn't enough space at all will a pumpkin get ruined.

So in the example everything is ok, this plan works:

```
[0,0,0,1,0,5,5,5,5,5,6,6,6,6,6,6]

```

But here:

```
[6,0,0,0,0,3,0,0,0,0,0]

```

There's not enough space for the `6` to grow even when the `3` grows as far to the right as possible

## Task

Take as input a non-empty list of non-negative integers. Output whether that list is a working plan. You should output one of two distinct values if it is a working plan and the other if it is not.

This is so the goal is to minimize the size of your source code as scored in bytes.

## Test cases

```
[1] -> True
[0,0] -> True
[3] -> False
[3,0] -> False
[3,0,0,2,0] -> True
[0,3,0,4,0,0,0] -> True
[0,0,1,0,3,1,0,0] -> False
[0,0,0,1,0,0,0,0,0,5,0,0,0,6,0,0] -> True
[6,0,0,0,0,3,0,0,0,0,0] -> False
[0,0,5,0,0,1] -> True
[2,0,2] -> False
[0,0,2,2] -> False
[2,2,0,0] -> False

```

# Answer
> 7 votes
# Jelly, 19 bytes

Hmm, I don't think we want any `ṀȯLƊ` on our pumpkins :( I also feel like this is beatable\*!

```
ŒṖṀȯLƊ⁼LƊȧTE$Ɗ€Ȧ$ƇẸ

```

A monadic Link accepting a list that yields `1` if a valid plan or `0` otherwise.

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

### How?

```
ŒṖṀȯLƊ⁼LƊȧTE$Ɗ€Ạ$ƇẸ - Link: list of integers, Plan
ŒṖ                 - all ways to partition Plan
                Ƈ  - filter keep those partitions for which:
               $   -   last two links as a monad:
             Ɗ€    -     for each part, last three links as a monad:
        Ɗ          -       last three links as a monad:
     Ɗ             -         last three links as a monad:
  Ṁ                -           maximum of the part
    L              -           length of the part
   ȯ               -           logical OR
       L           -         length of the part
      ⁼            -         equal? (1 if enough space for the largest pumpkin
                                    ignoring others in the part; 0 otherwise)
            $      -       last two links as a monad:
          T        -         truthy indices
           E       -         all equal? (1 for those parts with up to one
                                         non-zero; 0 otherwise)
         ȧ         -       logical AND (1 for good parts; 0 otherwise)
               Ạ   -     all? (1 for good partitions; 0 otherwise)
                 Ẹ - any? (1 if the plan will work; 0 otherwise)

```

---

* Maybe it's not that bad... This different approach is much more efficient but a couple of bytes longer (greedily grow the outermost pumpkin using outer zeros if possible) - outputs `0` if the plan is valid or `1` otherwise:

```
Ḋ⁸¹ƇḢ»TḟTḊ$fJḢ¤¡ṚµÐLẸ

```

# Answer
> 4 votes
# Haskell, ~~55~~ 54 bytes

-1 byte thanks to Wheat Wizard!

```
(!0)
(x:y)!i|x>0=i<1&&y!max(i+x-1)0|w<-i-1=y!w
_!i=i<1

```

Try it online!

The recursive function `(!)` looks at first like it should be implemented with a `foldl`, but the `i<1&&` check makes this infeasible.

# Answer
> 4 votes
# Python 3, 73 72 67 bytes

```
f=lambda p,*v,s=0:p*s<1==f(*v,s=max(s+p,0<p or s)-1)if v else p+s<2

```

Try it online!

Takes input as varargs

`s` represents the amount of tiles a pumpkin can grow. Negative values, such as `-2` mean that the pumpkin has two spaces to the left that it can grow. If `s` is positive, it means that this space will be occupied by a pumpkin, thus no pumpkins can grow.

# Answer
> 4 votes
# JavaScript (ES6),  ~~55~~  54 bytes

Returns a Boolean value.

This algorithm attempts to put each pumpkin as far as possible to the left.

```
a=>[...a,1].every((v,i)=>v?p=p+v>i++?p<i&&p+v:i:1,p=0)

```

Try it online!

---

# JavaScript (ES6), 49 bytes

*A port of @AnttiP's answer suggested by @AnttiP*

Returns \\$0\\$ or \\$1\\$.

```
a=>a.every(p=>1>s*p*(s=(s+=p-1)*p<0?0:s),s=0)&s<1

```

Try it online!

# Answer
> 4 votes
# , 35 32 bytes

```
*=&(+/)0=[:(],(+{:)0&>.~0<:[)/<:

```

Try it online!

## the idea

We'll devise an adjusted scan sum such that the number of zeros in that sum will tell us the number of possible fully grown pumpkins.

Example using `0 0 0 3 0 4 0 0 0`:

* First, subtract 1:

```
_1 _1 _1 2 _1 3 _1 _1 _1  (A)

```
* Also, note the locations of our input pumpkins seeds, as these indexes will require special treatment in our scan sum:

```
0 0 0 1 0 1 0 0 0         (B)

```
* Now, consider the scan sum of A, but with a twist: If the sum is negative at one of the B locations, we'll reset it to 0:

```
_1 _2 _3 0 _1 2 1 0 _1
         ^
         would be _1, but we reset it to 0

```
* Finally, realize what 0 means: It means a pumpkin has finished fitting into some available space. The zero reset reflects that in a configuration like:

```
 0   0   0   0  3  0  2  input
 0   0   3   3  3  2  2  grown pumpkins
_1  _1  _1  _1  2 _1  1  input - 1
_1  _2  _3  _4  0 _1  0  adjusted scan sum

```

where the 3 pumpkin can fit entirely to the left of its seed with extra space to spare, pumpkin 2 cannot avail itself of that space.
* So, if the number of zeros in our scan-sum-with-a-twist equals the number of positive integers in our input, the input is valid.

# Answer
> 2 votes
# Python 3, 108 bytes:

```
def f(l):
 p=s=0
 for i in l:
  if i:
   if p:return 1
   p=max(i-1-s,s:=0)
  else:s+=p<1;p-=p>0
 return p>s

```

Try it online!

# Answer
> 2 votes
# Charcoal, 29 bytes

```
¹≔⁰η⊞θ¹Ｆθ¿ι¿‹η⁰⎚≔⌊⟦⁰⁻⊖ιη⟧η≦⊕η

```

Try it online! Link is to verbose version of code. Outputs a Charcoal boolean, i.e. `-` for enough space, nothing if not. Explanation:

```
¹

```

Assume there is enough space.

```
≔⁰η

```

Start with no space to the left of the patch. This variable becomes positive if there is space for a pumpkin to grow to the left or negative if a pumpkin is growing to the right.

```
⊞θ¹

```

End with no space to the right of the patch. This is handled by appending a pumpkin of size 1, which makes the calculations easier without changing the result.

```
Ｆθ

```

Loop through the patch.

```
¿ι

```

If there is a pumpkin, then:

```
¿‹η⁰

```

If a pumpkin to the left needs the space, then...

... there is a conflict, so clear the canvas.

```
≔⌊⟦⁰⁻⊖ιη⟧η

```

Otherwise, make this pumpkin grow as far to the left as it can.

```
≦⊕η

```

Otherwise, there is either less pumpkin growing to the right or more space for pumpkin to grow to the left.

Alternative formulation, also 29 bytes:

```
¹≔⁰η⊞θ¹Ｆθ«≦⊕η¿ι¿›η⁰≔⌊⟦⁰⁻ιη⟧η⎚

```

Try it online! Link is to verbose version of code. The only difference here is that the amount of space is incremented before the conditions, which just requires an adjustment to the condition and space calculation.

# Answer
> 2 votes
# Retina 0.8.2, 55 bytes

```
\d+
$*
+1`\B((,)+(?<-2>1)+)1|1(1+)(,)\B
1$1$4$3
M`11
^0

```

Try it online! Link includes test cases. Explanation:

```
\d+
$*

```

Convert the input to unary.

```
+1`

```

Repeatedly process the leftmost pumpkin that still needs space.

```
\B((,)+(?<-2>1)+)1

```

Match a pumpkin that can grow to the left (but only as far as its size),

```
|1(1+)(,)\B

```

... or a pumpkin that can grow to the right.

```
1$1$4$3

```

Mark that space as consumed by that pumpkin.

```
M`11
^0

```

Check that all of the pumpkins are fully grown.

# Answer
> 0 votes
# 05AB1E, 20 bytes

```
.œεεày0¢>yg)Ëy_P~]Pà

```

Try it online or verify all test cases.

**Explanation:**

Check if there is any partition for which each part satisfies one of two conditions: either all items are 0; or the maximum, length, and amount of 0s + 1 are all three the same.

```
.œ          # Get all partitions of the (implicit) input-list
  ε         # Map over each partition:
   ε        #  Map over each part:
    Z       #    Push the maximum (without popping)
    s0¢>    #    Swap, and count the amount of 0s + 1
    yg      #    And also push the length of the part
        )   #    Wrap all three values into a list
         Ë  #    Pop and check if all three are the same
          ~ #   OR:
    y_P     #    Check if all values in this part are 0s
]           # Close the nested loop
 P          # Product of each: Check if all parts in a partition are truthy
  à         # Pop and push max: Check if any partition is truthy
            # (after which the result is output implicitly)

```

---
Tags: code-golf, array, decision-problem
---