# Question
Title: Smallest slice of array containing a number of items
Take this array:

```
[1, 2, 6, 4, 4, 1, 0, 0, 2, 0, 4, 1, 4, 2, 4, 8, 1, 2, 4]

```

There are quite a few places where `[1, ..., 2, ..., 4]` appears, where `...` is any number of items. These include `[1, 2, 6, 4]`, `[1, 0, 0, 2, 0, 4]`, `[1, 0, 0, 2, 0, 4, 1, 4]`, and `[1, 2, 4]`. The shortest of these is simply `[1, 2, 4]`.

**Task:**

Given two arrays of any (reasonable) data type you choose, find the shortest slice of the first which contains all items in the second in order. There is guaranteed to be at least one such slice.

If there are multiple, you may return any one of them. Neither array will be empty. Duplicate items may appear in the second list.

**Test cases:**

```
[1, 2]                        [1, 2]        ->  [1, 2]
[2, 1, 3, 2]                  [1, 2]        ->  [1, 3, 2]
[1, 2, 4, 8]                  [1, 4, 8]     ->  [1, 2, 4, 8]
[0, 1, 1, 0, 0, 1, 1, 1, 0]   [0, 1, 0]     ->  [0, 1, 1, 0]
[1, 5, 3, 7, 1, 3, 3, 5, 7]   [1, 3, 5, 7]  ->  [1, 3, 3, 5, 7]
[1, 2, 5, 1, 3, 5]            [1, 5]        ->  [1, 2, 5] OR [1, 3, 5]

```

**Other:**

This is , so shortest answer in bytes per language wins!

# Answer
# Jelly, 7 bytes

```
ẆŒPi¥ƇḢ

```

Try it online!

-1 byte thanks to Unrelated String

```
ẆŒPi¥ƇḢ   Main Link
      Ḣ   Find the first
Ẇ         slice (ordered by length)
     Ƈ    where
   i      the right list's index is truthy (occurs in)
 ŒP       the powerset (stable ordered)

```

1-indexing saves me a byte, thank you Dennis!
> 7 votes

# Answer
# Brachylog, 8 bytes

```
⟨s⊇⟩ᶠlᵒh

```

Try it online!

```
⟨  ⟩ᶠ       Find every
 s          substring of the first input
  ⊇         containing the second input as a substring.
     lᵒ     Sort by length
       h    and take the first.

```
> 6 votes

# Answer
# Husk, 8 bytes

```
◄Lfo€⁰ṖQ

```

Try it online!

yes another carriage in the 8-byte golflang answer train.
> 6 votes

# Answer
# , 64 bytes

```
]{~0({.+i.@>:@g)@>@{[:(]/:(g=.{:-{.)&>)@(#~]=/:~&.>)@,@{[:<@I.=/

```

Try it online!

Well 8-byte folks, let's *square* the byte count, shall we?

I could save bytes here by just trying every possible subset, but this approach seemed more interesting, and for most inputs is likely faster.

## the idea

Consider `1 3 5 7 f 1 5 3 7 1 3 3 5 7`:

* Create an equality table:

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

```
* Get indexes of ones:

```
┌───┬─────┬───┬───┐
│0 4│2 5 6│1 7│3 8│
└───┴─────┴───┴───┘

```
* Cartesian product:

```
┌───────┬───────┬───────┬───────┬
│0 2 1 3│0 2 1 8│0 2 7 3│0 2 7 8│ ...etc...
└───────┴───────┴───────┴───────┴

```
* Filter only elements that are ordered:

```
┌───────┬───────┬───────┬───────┬───────┐
│0 2 7 8│0 5 7 8│0 6 7 8│4 5 7 8│4 6 7 8│
└───────┴───────┴───────┴───────┴───────┘

```
* Sort by difference between first and last element:

```
┌───────┬───────┬───────┬───────┬───────┐
│4 5 7 8│4 6 7 8│0 2 7 8│0 5 7 8│0 6 7 8│
└───────┴───────┴───────┴───────┴───────┘

```
* Take first element, and construct full range between first and last:

```
 4 5 6 7 8

```
* Use those to index into the input:

```
1 3 3 5 7

```
> 6 votes

# Answer
# JavaScript (ES6),  ~~89 87~~  83 bytes

*Saved 4 bytes thanks to @tsh*

Expects `(haystack)(needle)`.

```
a=>b=>a.reduce((r,_,i)=>b.every(x=>j=a.indexOf(x,j)+1,j=i)/r[j-i]?a.slice(i,j):r,a)

```

Try it online!

### Commented

```
a =>                  // a[] = haystack
b =>                  // b[] = needle
a.reduce((r, _, i) => // for each entry at position i in a[]:
  b.every(x =>        //   for each entry x in b[]:
    j =               //     update j to:
      a.indexOf(x, j) //       the index of x in a[], starting at j
      + 1,            //       to which we add 1
    j = i             //     starting with j = i
  )                   //   end of every()
  / r[j - i]          //   test whether r[j - i] is defined
  ?                   //   if successful:
    a.slice(i, j)     //     update r[] to the current slice of a[]
  :                   //   else:
    r,                //     leave r[] unchanged
  a                   //   start with r[] = a[]
)                     // end of reduce()

```

---

# JavaScript (ES6),  ~~91~~  89 bytes

*Saved 2 bytes thanks to @tsh*

Expects `(needle)(haystack)`.

```
b=>g=(a,n)=>a.some((_,i)=>`${s=a.slice(i,i+n)}`.match(`^${b.join`,(.*,)*`}$`))?s:g(a,-~n)

```

Try it online!

### How?

We turn the needle `b[]` into a regular expression:

```
RegExp(`^${b.join`,(.*,)*`}$`)

```

Example:

```
[1, 4, 8] ~> /^1,(.*,)*4,(.*,)*8$/

```

We recursively look for the smallest `n` such that there exists a slice `s[]` of `a[]` of length `n` that matches this regular expression.
> 5 votes

# Answer
# JavaScript (ES6), 93 bytes

```
a=>b=>a.reduce(r=>1/r[p=b.map((m,j)=>t=m-a[i]?p[j]:j?p[j-1]:i),++i-t]?a.slice(t,i):r,a,i=p=0)

```

Try it online!

For inputs \\$ a\left\[1\dots N\right\] \\$ and \\$ b\left\[1\dots M\right\] \\$

Let matrix \\$p\_{N\times M}\\$ be

$$ p\_{i,j}=\begin{cases} i & b\_j=a\_i \land j=1 \\ p\_{i-1,j-1} & b\_j=a\_i \land j\>1 \land i\>1 \\ p\_{i-1,j} & b\_j\ne a\_i \land i \> 1 \\ -\infty & \text{otherwise} \\ \end{cases} $$

the minimal length of output \\$L\\$ is

$$ L = \min\_{i \in 1\dots N} i-p\_{i,M}+1 $$

And the output is

$$ a\left\[p\_{i,M}\dots i\right\] $$

where \\$i\\$ is the value for minimal \\$L\\$.

This solution works in \\$ O\left(M^2\right) \\$ time and \\$ O\left(N\right) \\$ extra memory.
> 4 votes

# Answer
# Vyxal, 9 bytes

```
ÞS'ṗ⁰c;Þg

```

Try it Online!

```
       Þg # Shortest
ÞS        # sublist
  '   ;   # where
   ṗ      # powerset
     c    # contains
    ⁰     # input

```
> 4 votes

# Answer
# 05AB1E, 8 bytes

```
Œé.ΔæX.å

```

Try it online or verify all test cases.

**Explanation:**

```
Œ         # Get all sublists of the (implicit) input-list
 é        # Sort these sublists by smallest to largest length
  .Δ      # Find the first sublist which is truthy for:
    æ     #  Get the powerset of this sublist
     I.å  #  And check if it contains the second input-list
          # (after which this shortest found result is output implicitly)

```
> 3 votes

# Answer
# Python 2, 94 bytes

Using `iter` to check if `s` is a subsequence of `b` is a trick I've first seen on this answer.

```
def f(a,b,i=0):l=len(a);s=a[i%l:][:i/l];x=iter(s);return s*all(v in x for v in b)or f(a,b,i+1)

```

Try it online!
> 2 votes

# Answer
# Charcoal, 60 bytes

```
≔Ｅ⌕Ａθ⊟η⟦¹ι⟧ζＦ⮌η«ＦζＦ⌕Ａ…θ§κ¹ι⊞υ⟦⁻Σκλλ⟧≔υζ≔⟦⟧υ»≔⌊ζε≔⊟εδＩ✂θδ⁺δ⊟ε

```

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

```
≔Ｅ⌕Ａθ⊟η⟦¹ι⟧ζ

```

Get the last element of the array to match and find all of its indices in the array to search, yielding an array `[1, i]` for each position. These values relate to the length and start position of a slice of the array to search, initially only containing the last element of the array to match.

```
Ｆ⮌η«

```

Loop over the remaining elements in reverse order.

```
Ｆζ

```

Loop over the matches so far.

```
Ｆ⌕Ａ…θ§κ¹ι

```

Loop over all the positions of the next element in the prefix of the current match.

```
⊞υ⟦⁻Σκλλ⟧

```

Save the new match length and start position.

```
≔υζ≔⟦⟧υ

```

Move the working list back to the list of matches and clear the working list again.

```
»≔⌊ζε≔⊟εδ

```

Get the match with the shortest length and get its start position.

```
Ｉ✂θδ⁺δ⊟ε

```

Output the slice of that length at that position.
> 2 votes

# Answer
# Retina, 34 bytes

```
1A`
,
.$*
~)`^
1G`¶Lw`
N$`
$.&
1G`

```

Try it online! Takes two newline-separated lists of distinctive words (i.e. no word is contained in another word) but link is to test suite that splits on semicolons for convenience. Explanation:

```
1A`

```

Delete the array to search.

```
,
.$*

```

Replace each comma with a regex for arbitrary content.

```
^
1G`¶Lw`

```

Prefix a command to delete the array to match and list all overlapping matches in the array to search.

```
~)`

```

Evaluate the result on the original input.

```
N$`
$.&

```

Sort the matches by length.

```
1G`

```

Take the first.
> 2 votes

# Answer
# , ~~95~~, 94 bytes

#### Assuming `combn` always returns sorted indexes

At the moment the assumption is valid in all R versions, but is not documented; the alternative (longer) solution is reported at the bottom of the answer

* -1 byte thanks to @Dominc van Essen

```
function(v,s,`+`=length){for(x in combn(+v,+s,,F))if(all(v[x]==s)&+v[T]>+(y=x:x[+x]))T=y;v[T]}

```

Try it online!

## Unrolled code with explanation:

```
function(v,s){                  # take full vector v and the vector to search s
  r=v                           # init shortest slice r to full vector v
  for(x in combn(length(v),     # for each combination x of length(s) elements taken
                 length(s),,F){ # from the vector of indexes 1:length(v)
                                # (we assume x is sorted ascending)
    a=v[x:x[+x]]                # get the slice between first and last index in x
    if(all(v[x]==s) &           # if the values of the combinations == s and
       length(r) > length(a))   # the slice is shorter than r
      r=a                       # store the new slice
  }
  r                             # return the shortest slice
}

```

---

Version without assumption:

# , 107 bytes

```
function(v,s,r=v,`+`=length){for(x in combn(+v,+s,,F)){y=sort(x);if(all(v[x]==s)&+r>+(a=v[x:x[+x]]))r=a};r}

```

Try it online!
> 2 votes

# Answer
# Japt, 9 bytes

```
ã æÈà deV

```

Try it

```
ã æÈà deV     :Implicit input of arrays U=haystack & V=needle
ã             :Sub-arrays of U
  æ           :Get the first that returns true
   È          :When passed through the following function
    à         :  Combinations
      d       :  Any
       eV     :    Equal to V

```
> 2 votes

# Answer
# GForth, 241 bytes

```
: s 1 /string ;
: d 2drop ;
: o 2over ;
: h over >r begin o drop c@ scan 2>r s 2r> 2 pick 0= over 0= 2* or ?dup until nip 2nip 1+ swap r@ - r> -rot or ;
: f 2dup 2>r begin o o h dup r@ u< if 2rdrop 2>r else d then s dup 0= until d d 2r> 1+ ;

```

Try it online!

## Formatted & commented version

also a bit ungolfed

: s 1 /string ;
: d 2drop ;
: o 2over ;

\ find the first match. if there is no match, return a string with the maximum length (-1)
: h ( target container -- caddr u )
    \ store the start address of the string on the return stack
    over >r
    begin
        \ remove characters from the front of the string until
        \ the string starts with the same character as
        \ the target string (or until it is empty)
        o drop c@ scan

        \ remove a character from the front of the target string
        2>r s 2r>

        \ some magic that gives -1 if the target string is empty,
        \ -2 if the container string is empty, and 0 otherwise
        2 pick 0= over 0= 2* or
        \ duplicate the top of the stack if it isn't zero
        ?dup
        \ exit the loop if the top of the stack is something other than zero
    until
    \ get rid of everything on the stack except for new address of the string
    \ if there was a match, this will be the address of the end of the match.
    nip 2nip
    \ use this and the saved start address to reconstruct the match.
    1+ swap r@ - r> -rot
    \ if we didn't get a match, use the magic from before to replace the length with -1
    or ;

: f ( target container -- caddr u )
    \ store the current shortest match on the return stack.
    \ since it is given that there will be a match in the array,
    \ we put that on the return stack first
    2dup 2>r

    begin
        \ find the first match, and compare its length to
        \ the length of the match on the return stack
        o o h dup r@ u< if
            \ if it is shorter, replace the string on the return stack with it
            2rdrop 2>r
        else
            \ otherwise, discard it
            d
        then
        \ remove a charachter from the front of the string
        s
        \ if there are no more charachters in the string, exit the loop
        dup 0=
    until
    \ get rid of everything and retrive the stored match
    d d 2r>
    \ there's an off by one error here somewhere. rather than fix it, just add one.
    1+ ;

```
</code></pre>
> 1 votes

# Answer
# \>= 4.1.0, 139 bytes

```
\(x,y,`~`=\(a,b)paste(a,collapse=b))(u<-combn(1:sum(x|1),2,\(z)if(grepl(y~" .* ",(v=x[z[1]:z[2]])~"  "))v,F))[order((m=lengths(u))/!!m)][1]

```

Try it online!

A function that takes the `x` as the vector to look within and `y` as the vector to look for. Returns a length 1 list containing the shortest matching contiguous subsequence of `x`. TIO link replaces `\` with `function` since TIO is running an earlier version of R.
> 1 votes

# Answer
# Python 3.8, 152 bytes

The other python answer is too good - but just leaving mine here anyway

```
from itertools import*
f=lambda a,b:min(((Y:=c[0][0]),(Z:=c[-1][0]),a[Y:Z+1],Z-Y)[::-1]for c in combinations(enumerate(a),len(b))if[*zip(*c)][1]==b)[1]

```

older uncondensed version

```
from itertools import*
def f(a,b):
    #print(*permutations(a), sep='\n')
    combis = [*combinations(enumerate(a),len(b))]
    #print(combis)
    F=[(combi[0][0],combi[-1][0]) for combi in combis if [*zip(*combi)][1]==b]
    #print(F)
    s,e = min(F, key=lambda i:i[1]-i[0])
    #print(s,e,a,a[s:e+1])
    return a[s:e+1]

```
> 1 votes

# Answer
# Wolfram Language (Mathematica), 67 bytes

```
(c=___;#1/.{c,x:Shortest[PatternSequence@@Riffle[#2,c]..],c}:>{x})&

```

Try it online!

No brutal force, just patterns usage
> 1 votes

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


title: Passwords Strong Against Bishops

text:
# Question
Title: Passwords Strong Against Bishops
Not to be confused with Password Bishop Goodness!

Given a string, answer (truthy/falsy or two consistent values) if it constitutes a password which is *strong against bishops*.

A password is *strong against bishops* if it is a string consisting of alternating letters (in `a-h`) and digits (in `1-8`) such that each pair of characters can be interpreted as a square on a chessboard, and if you place a white pawn on each square named in the password, then there is no way for a white bishop to travel, in any number of consecutive moves, from any square in the first (`1`) row to any square in the last (`8`) row.

## Examples

### Passwords strong against bishops

* `a1b1c1d1e1f1g1h1`
* `a8b8c8d8e8f8g8h8`
* `a1b2c3d4d5f5f4g3g4h2b5`
* `h4g4f4e4c4b4a4c3e3`
* `a1b1c1d1e1f1g1a8b8c8d8e8f8g8`
* `b4b5d4d5f4f5g3h5`

> For example, `a1b1c1d1e1f1g1a8b8c8d8e8f8g8` corresponds to the position  and `b4b5d4d5f4f5g3h5` corresponds to the position

### Passwords weak against bishops

* `a4c4e4g4g5d6f6e3d2b2` (well-formed but not strong — thanks Jo King for this example!)
* `b1c1d1e1f1g1h1a8b8c8d8e8f8g8` (well-formed but not strong)
* `h4g4f4e4c4b4a4c3` (well-formed but not strong)
* `d4` (well-formed but not strong)
* `b4b5d4d5f4f5g2h5` (well-formed but not strong)
* `correct horse battery staple` (ill-formed)
* `1a1b1c1d1e1f1g8a8b8c8d8e8f8g` (ill-formed)
* `a` (ill-formed)
* `aa` (ill-formed)

# Answer
## Ruby, ~~115~~ ~~182~~ 163 bytes

```
->s{z=('00'..'99').map{|x|x=~/[09]/||s[(x[1].ord+48).chr+x[0]]};(11..18).map &g=->x{z[x]||[x-11,x-9,x+z[x]=9,x+11].map(&g)};s=~/^([a-h][1-8])*$/&&(z[81,9]-[9])[8]}

```

Try it online!

Returns `1` for strong and `nil` for weak. (The +67 bytes was for taking into account "backtracking.")

```
->s{
 z=                             # this is the board
 ('00'..'99').map{|x|           # coordinates are described as y*10 + x
  x=~/[09]/||                   # truthy if out of bounds...
  s[(x[1].ord+48).chr+x[0]]     # ...or impassable
 }                              # now only the passable squares are falsey
 (11..18).map                   # for each x position at y=1,
  &g=->x{                       # call helper function on that square
   z[x]||                       # if the square is passable (i.e. falsey),
    [x-11,x-9,x+z[x]=9,x+11]    # mark it impassable by setting to 9 (truthy)
     .map(&g)                   # call helper recursively for each neighbor
  }
 s=~/^([a-h][1-8])*$/           # make sure the input was valid,
 &&(z[81,9]-[9])[8]             # and check that the last row was never reached
}

```

A few tricks that were used:

* Instead of the numerical range `0..99`, we use the *string* range `'00'..'99'` so that the number is automatically left-padded to 2 digits and stringified. This makes out of bounds checking very short -- match with regex `/[09]/`.
* Inside the helper function, while building the list of new coordinates `[x-11, x-9, x+9, x+11]`, we simultaneously assign `z[x]` to `9` in the process, which happens to be a truthy value (marking the square visited).
* In the last line, we want to check that the array `z[81,9]` does not contain `9`. We do this by removing all instances of `9` (`z[81,9]-[9]`), then asking for the 9th element of the resulting array (`[8]`). Since we know the array originally had 9 elements, if any were removed, we'll get `nil`, whereas if they all remained, we'll get the last element of the array (which happens to always be `1`).
> 4 votes

# Answer
# Python 2, 330 318 313 309 370 bytes

```
import numpy as n
b=n.ones([8,8])
q=r=1
s=input()
l=len(s)
def g(x,y=0,p=0):
    if b[y,x]and p<32:
        if y<7:
            if x<7:
                g(x+1,y+1,p+1)
                if y:g(x+1,y-1,p+1)
            if x:
                g(x-1,y+1,p+1)
                if y:g(x-1,y-1,p+1)
        else:global q;q=0
for i in range(l/2):
    x=ord(s[2*i])-97;y=ord(s[2*i+1])-49
    if y>8or y<0 or l%2or x>8or x<0:r=0
    if r:b[7-y,x]=0
map(g,range(8))
print q&r

```

Try it online!

Try practical version online! (original can take 4^32 operations to check completely, I suggest using this one - same number of bytes)

Not a super short solution - I couldn't figure out how to make a lambda function version of g shorter than g itself.

-4 bytes thanks to Quuxplusone

+61 bytes accounting for backtracking (thanks for pointing that out Jo King and for the golfing tips)
> 2 votes

# Answer
# Python 2, ~~490~~ ~~476~~ 474

```
def f(p):
 a=[set(ord(c)-33 for c in s)for s in"* )+ *, +- ,. -/ .0 / \"2 !#13 \"$24 #%35 $&46 %'57 &(68 '7 *: )+9; *,:< +-;= ,.<> -/=? .0>@ /? 2B 13AC 24BD 35CE 46DF 57EG 68FH 7G :J 9;IK :<JL ;=KM <>LN =?MO >@NP ?O BR ACQS BDRT CESU DFTV EGUW FHVX GW JZ IKY[ JLZ\\ KM[] LN\\^ MO]_ NP^` O_ R QS RT SU TV UW VX W".split()];x=set((ord(p[i+1])-49)*8+ord(p[i])-97 for i in range(0,len(p),2))
 r=set(range(8))-x
 for i in range(99):r=set().union(*[a[c]for c in r])-x
 return all(c<56 for c in r)

```

Try it online!

This works by "flood-fill." First we create a list `a` of which squares are adjacent to which other squares, bishopwise. Then we create a set `x` of exclusions (based on the password). Then we initialize a set `r` of reachable squares, which starts out as just the first row (minus any exclusions), and repeatedly "flood" outward from there, 99 times, which should be more than enough. Finally, we test to see if any of the squares in the last row ended up in our reachable set. If so, we have a weak password! If not, we have a strong password.

Disadvantage, perhaps disqualifying (I don't know the usual rule here): If the password is ill-formed (such as "correct horse battery staple"), then we throw an exception instead of returning `False`. But we do always return `True` iff the password is strong!

Minus 16 bytes thanks to Jo King. We inline `a` in the one place it's used, and constant-fold some math.

```
def f(p):
 x=set(ord(p[i])-489+8*ord(p[i+1])for i in range(0,len(p),2));r=set(range(8))-x
 for i in[1]*99:r=set().union(*[[set(ord(k)-33for k in s)for s in"* )+ *, +- ,. -/ .0 / \"2 !#13 \"$24 #%35 $&46 %'57 &(68 '7 *: )+9; *,:< +-;= ,.<> -/=? .0>@ /? 2B 13AC 24BD 35CE 46DF 57EG 68FH 7G :J 9;IK :<JL ;=KM <>LN =?MO >@NP ?O BR ACQS BDRT CESU DFTV EGUW FHVX GW JZ IKY[ JLZ\\ KM[] LN\\^ MO]_ NP^` O_ R QS RT SU TV UW VX W".split()][c]for c in r])-x
 return all(c<56for c in r)

```
> 2 votes

# Answer
# Wolfram Language (Mathematica), ~~339~~ ~~316~~ ~~358~~ ~~353~~ 345 bytes

-23 bytes thanks to @Doorknob.

+42 bytes accounting for backtracking.

```
p[m_]:=StringPartition[#,m]&;l=Range@8;f[n_]:=Check[w=(8#2+#1-8)&@@@({LetterNumber@#,FromDigits@#2}&@@@(p@1/@p[UpTo@2]@n));g=Graph[Sort/@UndirectedEdge@@@Position[Outer[EuclideanDistance@##&,#,#,1],N@Sqrt@2]&@GraphEmbedding@GridGraph@{8,8}//Union]~VertexDelete~w;c:=#~Complement~w&;m=0;Do[m+=Length@FindPath[g,i,j],{i,c@l},{j,c[l+56]}];m==0,0>1]

```

Try it online!

I rewrote most of this to account for backtracking, I think there may be an easier way to define the graph `g`, Mathematica has `GraphData[{"bishop",{8,8}}]` which is the graph of all moves a bishop can make on a chessboard (Bishop Graph), but this graph includes connections further than nearest diagonal neighbor. If anyone knows a shorter way to do that let me know. Credit for the graph construction goes to this MathematicaSE answer.

Returns `True` for strong passwords, `False` for weak/ill-formed passwords. Note that for most of the ill-formed passwords it will produce a bunch of error messages and then return `False`. If this is not in line with the rules then they can be suppressed by changing `f[n_]:=...` to `f[n_]:=Quiet@...` costing 6 bytes.

Ungolfed:

```
p[m_] := StringPartition[#, m] &;

f[n_] :=
 Check[
  w = (8 #2 + #1 -
       8) & @@@ ({LetterNumber@#, FromDigits@#2} & @@@ (p@1 /@
        p[UpTo@2]@n));
  r = GridGraph[{8, 8}];
  g = Graph[Sort /@ UndirectedEdge @@@
             Position[Outer[EuclideanDistance@## &, #, #, 1],N@Sqrt@2] &@
              GraphEmbedding@r // Union]~VertexDelete~w;
  s = Complement[{1,2,3,4,5,6,7,8},w];
  e = Complement[{57,58,59,60,61,62,63,64},w];
  m = 0;
  Do[m += Length@FindPath[g, i, j], {i, s}, {j, e}];
  If[m == 0,True,False]
  , False]

```

Breakdown:

```
p[m_]:=StringPartition[#,m]&

```

Takes a string argument and splits it into a list of strings each of length `m`.

```
Check[...,False]

```

Returns `False` if any error messages are produced, which is how we catch the ill-formed strings (i.e. assume they are well-formed, inevitably producing an error down the line).

```
(8*#2 + #1 - 8) & @@@ ({LetterNumber@#, FromDigits@#2} & @@@ (p@1 /@
        p[UpTo@2]@n));

```

Takes the string of pawn positions and splits it such that `"a2h5b"` becomes `{{"a","2"},{"h","5"},{"b"}}`, then `LetterNumber` will convert the letter to a number (`a -> 1`, etc) and `FromDigits` converts the numeral into an integer. If the string is not well formed, this step will produce an error which will be caught by `Check`, returning `False`. These two numbers are then converted to an integer corresponding to a square on the board.

```
r = GridGraph[{8, 8}];
g = Graph[
     Sort /@ UndirectedEdge @@@
          Position[Outer[EuclideanDistance@## &, #, #, 1],
           N@Sqrt@2] &@GraphEmbedding@r // Union]~VertexDelete~w;

```

Constructs the graph of all nearest-neighbor diagonal edges with the pawn positions deleted.

```
s = Complement[{1,2,3,4,5,6,7,8},w];
e = Complement[{57,58,59,60,61,62,63,64},w];

```

These are lists of unoccupied starting and ending vertices respectively

```
m=0
Do[m += Length@FindPath[g, i, j], {i, s}, {j, e}];
If[m == 0,True,False]

```

Loops over the starting and ending vertices, for each pair `FindPath` will be a list of paths between them. If there are no paths between them, it will be an empty list, so `Length@` returns `0`. If there are no paths at all, then `m` will be zero, and we return `True`, otherwise return `False`.
> 1 votes

# Answer
# Clean, 285 bytes

```
import StdEnv,Data.List
$_[_]=1<0
$a[x,y:l]=case[[u,v]\\u<-[0..7],v<-[0..7]|u==toInt x-97&&v==toInt y-49]of[p]= $[p:a]l;_=1<0
$a _=all(\[_,y]=y<7)(iter 64(nub o\e=e++[k\\[u,v]<-e,p<-[-1,1],q<-[-1,1],k<-[[abs(u+p),abs(v+q)]]|all((<>)k)a&&all((>)8)k])(difference[[e,0]\\e<-[0..7]]a))

```

#

```
$[]

```

Try it online!

`$[]` is `$ :: [[Int]] [Char] -> Bool` composed with the first argument, giving `\ [Char] -> Bool`.

The function works by consuming the string two characters at a time, immediately returning false if the string is in an invalid format as soon as it sees the invalid part. Once the string has been processed, it places a bishop on every empty square on one side of the board and moves them in every way possible 64 times and checks if any of the end positions is in the target row.
> 1 votes

# Answer
# Python 3.8 (pre-release), 192 bytes

```
import re
s=p=input()
t={0,1}
while s!=t:s=t;t=t|{i for x in s for i in[x-9,x-7,x+7,x+9]if-9<i<72and-2<x%8-i%8<2and"%c%d"%(97+i%8,i/8)not in p}
print(max(s)<64and""==re.sub("[a-h][1-8]","",p))

```

Try it online!
> 0 votes

---
Tags: code-golf, string, decision-problem, path-finding, chess
---


title: Reverse Polish notation

text:
# Question
Title: Reverse Polish notation
You must evaluate a string written in Reverse Polish notation and output the result.

The program must accept an input and return the output. For programming languages that do not have functions to receive input/output, you can assume functions like readLine/print.

You are not allowed to use any kind of "eval" in the program.

Numbers and operators are separated by one **or more** spaces.

You must support at least the +, -, * and / operators.

You need to add support to negative numbers (for example, `-4` is not the same thing as `0 4 -`) and floating point numbers.

**You can assume the input is valid and follows the rules above**

## Test Cases

Input:

```
-4 5 +

```

Output:

```
1

```

---

Input:

```
5 2 /

```

Output:

```
2.5

```

---

Input:

```
5 2.5 /

```

Output:

```
2

```

---

Input:

```
5 1 2 + 4 * 3 - +

```

Output:

```
14

```

---

Input:

```
4 2 5 * + 1 3 2 * + /

```

Output:

```
2

```

# Answer
## Ruby - 95 77 characters

```
a=[]
gets.split.each{|b|a<<(b=~/\d/?b.to_f: (j,k=a.pop 2;j.send b,k))}
p a[0]

```

Takes input on stdin.

### Testing code

```
[
  "-4 5 +",
  "5 2 /",
  "5 2.5 /",
  "5 1 2 + 4 * 3 - +",
  "4 2 5 * + 1 3 2 * + /",
  "12 8 3 * 6 / - 2 + -20.5 "
].each do |test|
  puts "[#{test}] gives #{`echo '#{test}' | ruby golf-polish.rb`}"
end

```

gives

```
[-4 5 +] gives 1.0
[5 2 /] gives 2.5
[5 2.5 /] gives 2.0
[5 1 2 + 4 * 3 - +] gives 14.0
[4 2 5 * + 1 3 2 * + /] gives 2.0
[12 8 3 * 6 / - 2 + -20.5 ] gives 10.0

```

Unlike the C version this returns the last valid result if there are extra numbers appended to the input it seems.
> 16 votes

# Answer
## Python - 124 chars

```
s=[1,1]
for i in raw_input().split():b,a=map(float,s[:2]);s[:2]=[[a+b],[a-b],[a*b],[a/b],[i,b,a]]["+-*/".find(i)]
print s[0]

```

**Python - 133 chars**

```
s=[1,1]
for i in raw_input().split():b,a=map(float,s[:2]);s={'+':[a+b],'-':[a-b],'*':[a*b],'/':[a/b]}.get(i,[i,b,a])+s[2:]
print s[0]

```
> 12 votes

# Answer
## Scheme, 162 chars

(Line breaks added for clarity—all are optional.)

```
(let l((s'()))(let((t(read)))(cond((number? t)(l`(,t,@s)))((assq t
`((+,+)(-,-)(*,*)(/,/)))=>(lambda(a)(l`(,((cadr a)(cadr s)(car s))
,@(cddr s)))))(else(car s)))))

```

Fully-formatted (ungolfed) version:

```
(let loop ((stack '()))
  (let ((token (read)))
    (cond ((number? token) (loop `(,token ,@stack)))
          ((assq token `((+ ,+) (- ,-) (* ,*) (/ ,/)))
           => (lambda (ass) (loop `(,((cadr ass) (cadr stack) (car stack))
                                    ,@(cddr stack)))))
          (else (car stack)))))

```

---

**Selected commentary**

``(,foo ,@bar)` is the same as `(cons foo bar)` (i.e., it (effectively) returns a new list with `foo` prepended to `bar`), except it's one character shorter if you compress all the spaces out.

Thus, you can read the iteration clauses as `(loop (cons token stack))` and `(loop (cons ((cadr ass) (cadr stack) (car stack)) (cddr stack)))` if that's easier on your eyes.

``((+ ,+) (- ,-) (* ,*) (/ ,/))` creates an association list with the *symbol* `+` paired with the *procedure* `+`, and likewise with the other operators. Thus it's a simple symbol lookup table (bare words are `(read)` in as symbols, which is why no further processing on `token` is necessary). Association lists have O(n) lookup, and thus are only suitable for short lists, as is the case here. :-P

† This is not technically accurate, but, for non-Lisp programmers, it gets a right-enough idea across.
> 11 votes

# Answer
# MATLAB – 158, 147

```
C=strsplit(input('','s'));D=str2double(C);q=[];for i=1:numel(D),if isnan(D(i)),f=str2func(C{i});q=[f(q(2),q(1)) q(3:end)];else q=[D(i) q];end,end,q

```

(input is read from user input, output printed out).

---

Below is the code prettified and commented, it pretty much implements the postfix algorithm described (with the assumption that expressions are valid):

```
C = strsplit(input('','s'));         % prompt user for input and split string by spaces
D = str2double(C);                   % convert to numbers, non-numeric are set to NaN
q = [];                              % initialize stack (array)
for i=1:numel(D)                     % for each value
    if isnan(D(i))                   % if it is an operator
        f = str2func(C{i});          % convert op to a function
        q = [f(q(2),q(1)) q(3:end)]; % pop top two values, apply op and push result
    else
        q = [D(i) q];                % else push value on stack
    end
end
q                                    % show result

```

---

## Bonus:

In the code above, we assume operators are always binary (`+`, `-`, `*`, `/`). We can generalize it by using `nargin(f)` to determine the number of arguments the operand/function requires, and pop the right amount of values from the stack accordingly, as in:

```
f = str2func(C{i});
n = nargin(f);
args = num2cell(q(n:-1:1));
q = [f(args{:}) q(n+1:end)];

```

That way we can evaluate expressions like:

```
str = '6 5 1 2 mean_of_three 1 + 4 * +'

```

where `mean_of_three` is a user-defined function with three inputs:

```
function d = mean_of_three(a,b,c)
    d = (a+b+c)/3;
end

```
> 8 votes

# Answer
## c -- 424 necessary character

```
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define O(X) g=o();g=o() X g;u(g);break;
char*p=NULL,*b;size_t a,n=0;float g,s[99];float o(){return s[--n];};
void u(float v){s[n++]=v;};int main(){getdelim(&p,&a,EOF,stdin);for(;;){
b=strsep(&p," \n\t");if(3>p-b){if(*b>='0'&&*b<='9')goto n;switch(*b){case 0:
case EOF:printf("%f\n",o());return 0;case'+':O(+)case'-':O(-)case'*':O(*)
case'/':O(/)}}else n:u(atof(b));}}

```

Assumes that you have a new enough libc to include `getdelim` in stdio.h. The approach is straight ahead, the whole input is read into a buffer, then we tokenize with `strsep` and use length and initial character to determine the class of each. There is no protection against bad input. Feed it "+ - * / + - ...", and it will happily pop stuff off the memory "below" the stack until it seg faults. All non-operators are interpreted as floats by `atof` which means zero value if they don't look like numbers.

**Readable and commented:**

```
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char *p=NULL,*b;
size_t a,n=0;
float g,s[99];
float o(){        /* pOp */
  //printf("\tpoping '%f'\n",s[n-1]);
  return s[--n];
};
void u(float v){  /* pUsh */
  //printf("\tpushing '%f'\n",v);
  s[n++]=v;
};
int main(){
  getdelim(&p,&a,EOF,stdin); /* get all the input */
  for(;;){
    b=strsep(&p," \n\t"); /* now *b though *(p-1) is a token and p
                 points at the rest of the input */
    if(3>p-b){
      if (*b>='0'&&*b<='9') goto n;
      //printf("Got 1 char token '%c'\n",*b);
      switch (*b) {
      case 0:
      case EOF: printf("%f\n",o()); return 0;
      case '+': g=o(); g=o()+g; u(g); break;
      case '-': g=o(); g=o()-g; u(g); break;
      case '*': g=o(); g=o()*g; u(g); break;
      case '/': g=o(); g=o()/g; u(g); break;
    /* all other cases viciously ignored */
      }
    } else { n:
      //printf("Got token '%s' (%f)\n",b,atof(b));
      u(atof(b));
    }
  }
}

```

**Validation:**

```
 $ gcc -c99 rpn_golf.c
 $ wc rpn_golf.c
  9  34 433 rpn_golf.c
 $ echo -4 5 + | ./a.out
1.000000
 $ echo 5 2 / | ./a.out
2.500000
 $ echo 5 2.5 / | ./a.out
2.000000

```

Heh! Gotta quote anything with `*` in it...

```
 $ echo "5 1 2 + 4 * 3 - +" | ./a.out
14.000000
 $ echo "4 2 5 * + 1 3 2 * + /" | ./a.out
2.000000

```

and my own test case

```
 $ echo "12 8 3 * 6 / - 2 + -20.5 " | ./a.out
-20.500000

```
> 7 votes

# Answer
## Haskell (155)

```
f#(a:b:c)=b`f`a:c
(s:_)![]=print s
s!("+":v)=(+)#s!v
s!("-":v)=(-)#s!v
s!("*":v)=(*)#s!v
s!("/":v)=(/)#s!v
s!(n:v)=(read n:s)!v
main=getLine>>=([]!).words

```
> 7 votes

# Answer
## Perl (134)

```
@a=split/\s/,<>;/\d/?push@s,$_:($x=pop@s,$y=pop@s,push@s,('+'eq$_?$x+$y:'-'eq$_?$y-$x:'*'eq$_?$x*$y:'/'eq$_?$y/$x:0))for@a;print pop@s

```

Next time, I'm going to use the recursive regexp thing.

Ungolfed:

```
@a = split /\s/, <>;
for (@a) {
    /\d/
  ? (push @s, $_)
  : ( $x = pop @s,
      $y = pop @s,
      push @s , ( '+' eq $_ ? $x + $y
                : '-' eq $_ ? $y - $x
                : '*' eq $_ ? $x * $y
                : '/' eq $_ ? $y / $x
                : 0 )
      )
}
print(pop @s);

```

I though F# is my only dream programming language...
> 6 votes

# Answer
### Windows PowerShell, 152 ~~181~~ ~~192~~

In readable form, because by now it's only two lines with no chance of breaking them up:

```
$s=@()
switch -r(-split$input){
  '\+'        {$s[1]+=$s[0]}
  '-'         {$s[1]-=$s[0]}
  '\*'        {$s[1]*=$s[0]}
  '/'         {$s[1]/=$s[0]}
  '-?[\d.]+'  {$s=0,+$_+$s}
  '.'         {$s=$s[1..($s.count)]}}
$s

```

**2010-01-30 11:07** (192) – First attempt.

**2010-01-30 11:09** (170) – Turning the function into a scriptblock solves the scope issues. Just makes each invocation two bytes longer.

**2010-01-30 11:19** (188) – Didn't solve the scope issue, the test case just masked it. Removed the index from the final output and removed a superfluous line break, though. And changed double to `float`.

**2010-01-30 11:19** (181) – Can't even remember my own advice. Casting to a numeric type can be done in a single char.

**2010-01-30 11:39** (152) – Greatly reduced by using regex matching in the `switch`. Completely solves the previous scope issues with accessing the stack to pop it.
> 6 votes

# Answer
**Racket 131:**

```
(let l((s 0))(define t(read))(cond[(real? t)
(l`(,t,@s))][(memq t'(+ - * /))(l`(,((eval t)(cadr s)
(car s)),@(cddr s)))][0(car s)]))

```

Line breaks optional.

Based on Chris Jester-Young's solution for Scheme.
> 5 votes

# Answer
## Python, 166 characters

```
import os,operator as o
S=[]
for i in os.read(0,99).split():
 try:S=[float(i)]+S
 except:S=[{'+':o.add,'-':o.sub,'/':o.div,'*':o.mul}[i](S[1],S[0])]+S[2:]
print S[0]

```
> 4 votes

# Answer
# Python 3, 119 bytes

```
s=[]
for x in input().split():
 try:s+=float(x),
 except:o='-*+'.find(x);*s,a,b=s;s+=(a+b*~-o,a*b**o)[o%2],
print(s[0])

```

Input: `5 1 1 - -7 0 * + - 2 /`

Output: `2.5`

(You can find a 128-character Python 2 version in the edit history.)
> 4 votes

# Answer
# JavaScript (157)

This code assumes there are these two functions: readLine and print

```
a=readLine().split(/ +/g);s=[];for(i in a){v=a[i];if(isNaN(+v)){f=s.pop();p=s.pop();s.push([p+f,p-f,p*f,p/f]['+-*/'.indexOf(v)])}else{s.push(+v)}}print(s[0])

```
> 3 votes

# Answer
## Perl, 128

This isn't really competitive next to the other Perl answer, but explores a different (suboptimal) path.

```
perl -plE '@_=split" ";$_=$_[$i],/\d||
do{($a,$b)=splice@_,$i-=2,2;$_[$i--]=
"+"eq$_?$a+$b:"-"eq$_?$a-$b:"*"eq$_?
$a*$b:$a/$b;}while++$i<@_'

```

Characters counted as diff to a simple `perl -e ''` invocation.
> 3 votes

# Answer
# flex - 157

```
%{
float b[100],*s=b;
#define O(o) s--;*(s-1)=*(s-1)o*s;
%}
%%
-?[0-9.]+ *s++=strtof(yytext,0);
\+ O(+)
- O(-)
\* O(*)
\/ O(/)
\n printf("%g\n",*--s);
.
%%

```

If you aren't familiar, compile with `flex rpn.l && gcc -lfl lex.yy.c`
> 3 votes

# Answer
## PHP, ~~439~~ ~~265~~ ~~263~~ ~~262~~ ~~244~~ 240 characters

```
<? $c=fgets(STDIN);$a=array_values(array_filter(explode(" ",$c)));$s[]=0;foreach($a as$b){if(floatval($b)){$s[]=$b;continue;}$d=array_pop($s);$e=array_pop($s);$s[]=$b=="+"?$e+$d:($b=="-"?$e-$d:($b=="*"?$e*$d:($b=="/"?$e/$d:"")));}echo$s[1];

```

This code should work with stdin, though it is not tested with stdin.
It has been tested on all of the cases, the output (and code) for the last one is here:
http://codepad.viper-7.com/fGbnv6

**Ungolfed, ~~314~~ ~~330~~ 326 characters**

```
<?php
$c = fgets(STDIN);
$a = array_values(array_filter(explode(" ", $c)));
$s[] = 0;
foreach($a as $b){
    if(floatval($b)){
        $s[] = $b;
        continue;
    }
    $d = array_pop($s);
    $e = array_pop($s);
    $s[] = $b == "+" ? $e + $d : ($b == "-" ? $e - $d : ($b == "*" ? $e * $d : ($b == "/" ? $e / $d :"")));
}
echo $s[1];

```
> 2 votes

# Answer
Python, 161 characters:

```
from operator import*;s=[];i=raw_input().split(' ')
q="*+-/";o=[mul,add,0,sub,0,div]
for c in i:
 if c in q:s=[o[ord(c)-42](*s[1::-1])]+s
 else:s=[float(c)]+s
print(s[0])

```
> 2 votes

# Answer
# Python 3, ~~126~~ 132 chars

```
s=[2,2]
for c in input().split():
    a,b=s[:2]
    try:s[:2]=[[a+b,b-a,a*b,a and b/a]["+-*/".index(c)]]
    except:s=[float(c)]+s
print(s[0])

```

There have been better solutions already, but now that I had written it (without having read the prior submissions, of course - even though I have to admit that my code looks as if I had copypasted them together), I wanted to share it, too.
> 2 votes

# Answer
## Python, 130 characters

Would be 124 characters if we dropped `b and` (which some of the Python answers are missing). And it incorporates 42!

```
s=[]
for x in raw_input().split():
 try:s=[float(x)]+s
 except:b,a=s[:2];s[:2]=[[a*b,a+b,0,a-b,0,b and a/b][ord(x)-42]]
print s[0]

```
> 2 votes

# Answer
# JavaScript ES7, 119 bytes

I'm getting a bug with array comprehensions so I've used `.map`

```
(s,t=[])=>(s.split` `.map(i=>+i?t.unshift(+i):t.unshift((r=t.pop(),o=t.pop(),[r+o,r-o,r*o,r/o]['+-*/'.indexOf(i)]))),t)

```

Try it online at ESFiddle
> 2 votes

# Answer
# C 153

Sometimes a program can be made a bit shorter with more golfing and sometimes you just take completely the wrong route and the much better version is found by someone else.

**Thanks to @ceilingcat for finding a much better (and shorter) version**

```
double atof(),s[99],*p=s;y,z;main(c,v)char**v;{for(;--c;*p=z?z-2?~z?z-4?p+=2,atof(*v):*p/y:*p*y:*p-y:*p+y)z=1[*++v]?9:**v-43,y=*p--;printf("%f\n",s[1]);}

```

Try it online!

My original version:

```
#include <stdlib.h>
#define O(x):--d;s[d]=s[d]x s[d+1];break;
float s[99];main(c,v)char**v;{for(int i=1,d=0;i<c;i++)switch(!v[i][1]?*v[i]:' '){case'+'O(+)case'-'O(-)case'*'O(*)case'/'O(/)default:s[++d]=atof(v[i]);}printf("%f\n",s[1]);}

```

If you are compiling it with mingw32 you need to turn off globbing (see https://www.cygwin.com/ml/cygwin/1999-11/msg00052.html) by compiling like this:

```
gcc -std=c99 x.c C:\Applications\mingw32\i686-w64-mingw32\lib\CRT_noglob.o

```

If you don't * is automatically expanded by the mingw32 CRT into filenames.
> 2 votes

# Answer
# C, 232 229 bytes

Fun with recursion.

```
#include <stdlib.h>
#define b *p>47|*(p+1)>47
char*p;float a(float m){float n=strtof(p,&p);b?n=a(n):0;for(;*++p==32;);m=*p%43?*p%45?*p%42?m/n:m*n:m-n:m+n;return*++p&&b?a(m):m;}main(c,v)char**v;{printf("%f\n",a(strtof(v[1],&p)));}

```

## Ungolfed:

```
#include <stdlib.h>

/* Detect if next char in buffer is a number */
#define b *p > 47 | *(p+1) > 47

char*p; /* the buffer */

float a(float m)
{
    float n = strtof(p, &p); /* parse the next number */

    /* if the next thing is another number, recursively evaluate */
    b ? n = a(n) : 0;

    for(;*++p==32;); /* skip spaces */

    /* Perform the arithmetic operation */
    m = *p%'+' ? *p%'-' ? *p%'*' ? m/n : m*n : m-n : m+n;

    /* If there's more stuff, recursively parse that, otherwise return the current computed value */
    return *++p && b ? a(m) : m;
}

int main(int c, char **v)
{
    printf("%f\n", a(strtof(v[1], &p)));
}

```

## Test Cases:

```
$ ./a.out "-4 5 +"
1.000000
$ ./a.out "5 2 /"
2.500000
$ ./a.out "5 2.5 /"
2.000000
$ ./a.out "5 1 2 + 4 * 3 - +"
14.000000
$ ./a.out "4 2 5 * + 1 3 2 * + /"
2.000000

```
> 2 votes

# Answer
## PHP - 259 characters

```
$n=explode(" ",$_POST["i"]);$s=array();for($i=0;$i<count($n);$s=$d-->0?array_merge($s,!$p?array($b,$a,$c):array($p)):$s){if($c=$n[$i++]){$d=1;$a=array_pop($s);$b=array_pop($s);$p=$c=="+"?$b+$a:($c=="-"?$b-$a:($c=="*"?$b*$a:($c=="/"?$b/$a:false)));}}echo$s[2];

```

Assuming input in POST variable *i*.
> 1 votes

# Answer
## C# - 392 characters

```
namespace System.Collections.Generic{class P{static void Main(){var i=Console.ReadLine().Split(' ');var k=new Stack<float>();float o;foreach(var s in i)switch (s){case "+":k.Push(k.Pop()+k.Pop());break;case "-":o=k.Pop();k.Push(k.Pop()-o);break;case "*":k.Push(k.Pop()*k.Pop());break;case "/":o=k.Pop();k.Push(k.Pop()/o);break;default:k.Push(float.Parse(s));break;}Console.Write(k.Pop());}}}

```

However, if arguments can be used instead of standard input, we can bring it down to

## C# - 366 characters

```
namespace System.Collections.Generic{class P{static void Main(string[] i){var k=new Stack<float>();float o;foreach(var s in i)switch (s){case "+":k.Push(k.Pop()+k.Pop());break;case "-":o=k.Pop();k.Push(k.Pop()-o);break;case "*":k.Push(k.Pop()*k.Pop());break;case "/":o=k.Pop();k.Push(k.Pop()/o);break;default:k.Push(float.Parse(s));break;}Console.Write(k.Pop());}}}

```
> 1 votes

# Answer
### Scala 412 376 349 335 312:

```
object P extends App{
def p(t:List[String],u:List[Double]):Double={
def a=u drop 2
t match{
case Nil=>u.head
case x::y=>x match{
case"+"=>p(y,u(1)+u(0)::a)
case"-"=>p(y,u(1)-u(0)::a)
case"*"=>p(y,u(1)*u(0)::a)
case"/"=>p(y,u(1)/u(0)::a)
case d=>p(y,d.toDouble::u)}}}
println(p((readLine()split " ").toList,Nil))}

```
> 1 votes

# Answer
## C# - 323 284 241

```
class P{static void Main(string[] i){int x=0;var a=new float[i.Length];foreach(var s in i){var o="+-*/".IndexOf(s);if(o>-1){float y=a[--x],z=a[--x];a[x++]=o>3?z/y:o>2?z*y:o>1?z-y:y+z;}else a[x++]=float.Parse(s);}System.Console.Write(a[0]);}}

```

Edit: Replacing the Stack with an Array is way shorter

Edit2: Replaced the ifs with a ternary expression
> 1 votes

# Answer
## Perl, 159

```
sub c{pop@s}sub z{push@s,$_[0]}while(<>){($_,$a)=/(\S*) ?(.*)/;z$_ if/\d/;z(('-'eq$_?- c:c)+c)if/[+-]/;z(('/'eq$_?1/c:c)*c)if/[*\/]/;redo if$_=$a;print c."\n"}

```

And here's the ungolfed version:

```
#!/usr/bin/perl

sub c{pop @stack}
sub z{push @stack,$_[0]}
while (<>) {
    ($_, $a) = /(\S*) ?(.*)/;
    z$_ if /\d/;
    z(('-'eq$_?- c:c)+c) if /[+-]/;
    z(('/'eq$_?1/c:c)*c) if /[*\/]/;
    redo if $_=$a;
    print c . "\n"
}

```

Not really much to look at, but I'm pretty happy with it. I managed to at least beat the Scheme version :)
> 1 votes

# Answer
# Python 2

I've tried out some different approaches to the ones published so far. None of these is quite as short as the best Python solutions, but they might still be interesting to some of you.

## Using recursion, 146

```
def f(s):
 try:x=s.pop();r=float(x)
 except:b,s=f(s);a,s=f(s);r=[a+b,a-b,a*b,b and a/b]['+-*'.find(x)]
 return r,s
print f(raw_input().split())[0]

```

## Using list manipulation, 149

```
s=raw_input().split()
i=0
while s[1:]:
 o='+-*/'.find(s[i])
 if~o:i-=2;a,b=map(float,s[i:i+2]);s[i:i+3]=[[a+b,a-b,a*b,b and a/b][o]]
 i+=1
print s[0]

```

## Using `reduce()`, 145

```
print reduce(lambda s,x:x in'+-*/'and[(lambda b,a:[a+b,a-b,a*b,b and a/b])(*s[:2])['+-*'.find(x)]]+s[2:]or[float(x)]+s,raw_input().split(),[])[0]

```
> 1 votes

# Answer
# Python - 206

```
import sys;i=sys.argv[1].split();s=[];a=s.append;b=s.pop
for t in i:
 if t=="+":a(b()+b())
 elif t=="-":m=b();a(b()-m)
 elif t=="*":a(b()*b())
 elif t=="/":m=b();a(b()/m)
 else:a(float(t))
print(b())

```

Ungolfed version:

```
# RPN

import sys

input = sys.argv[1].split()
stack = []

# Eval postfix notation
for tkn in input:
    if tkn == "+":
        stack.append(stack.pop() + stack.pop())
    elif tkn == "-":
        tmp = stack.pop()
        stack.append(stack.pop() - tmp)
    elif tkn == "*":
        stack.append(stack.pop() * stack.pop())
    elif tkn == "/":
        tmp = stack.pop()
        stack.append(stack.pop()/tmp)
    else:
        stack.append(float(tkn))

print(stack.pop())

```

Input from command-line argument; output on standard output.
> 1 votes

# Answer
# ECMAScript 6 (131)

Just typed together in a few seconds, so it can probably be golfed further or maybe even approached better. I might revisit it tomorrow:

```
f=s=>(p=[],s.split(/\s+/).forEach(t=>+t==t?p.push(t):(b=+p.pop(),a=+p.pop(),p.push(t=='+'?a+b:t=='-'?a-b:t=='*'?a*b:a/b))),p.pop())

```
> 1 votes

# Answer
## Matlab, 228

```
F='+-/*';f={@plus,@minus,@rdivide,@times};t=strsplit(input('','s'),' ');i=str2double(t);j=~isnan(i);t(j)=num2cell(i(j));while numel(t)>1
n=find(cellfun(@(x)isstr(x),t),1);t{n}=bsxfun(f{t{n}==F},t{n-2:n-1});t(n-2:n-1)=[];end
t{1}

```

Ungolfed:

```
F = '+-/*'; %// possible operators
f = {@plus,@minus,@rdivide,@times}; %// to be used with bsxfun
t = strsplit(input('','s'),' '); %// input string and split by one or multiple spaces
i = str2double(t); %// convert each split string to number
j =~ isnan(i); %// these were operators, not numbers ...
t(j) = num2cell(i(j)); %// ... so restore them
while numel(t)>1
    n = find(cellfun(@(x)isstr(x),t),1); %// find left-most operator
    t{n} = bsxfun(f{t{n}==F}, t{n-2:n-1}); %// apply it to preceding numbers and replace
    t(n-2:n-1)=[]; %// remove used numbers
end
t{1} %// display result

```
> 1 votes

# Answer
# K5, 70 bytes

```
`0:*{$[-9=@*x;((*(+;-;*;%)@"+-*/"?y).-2#x;x,.y)@47<y;(.x;.y)]}/" "\0:`

```

I'm not sure when K5 was released, so this *might* not count. Still awesome!
> 1 votes

# Answer
# C++, 265 bytes

Worse than first thought, looking for improvements.

```
#include<iostream>
#include<string>
#include<stack>
#define G s.top();s.pop()
using namespace std;int main(){string t; stack<float>s;while(cin>>t)if(47<t.back()&t.back()<58)s.push(stof(t));else{float a,b=G;a=G;s.push(t=="+"?a+b:t=="-"?a-b:t=="*"?a*b:a/b);}cout<<G;}

```

**Usage**

```
Run -> input -> enter -> Ctrl+Z -> enter  (windows)
                      -> Ctrl+D           (unix)

```

Ungolfed

```
#include <iostream>
#include <string>
#include <stack>
#define G s.top(); s.pop()
using namespace std;

int main()
{
    string t;
    stack<float> s;
    while (cin >> t)
    {
        if (47 < t.back() & t.back() < 58)
            s.push(stof(t));
        else
        {
            float a, b = G;
            a = G;
            s.push(t=="+" ? a+b : t=="-" ? a-b : t=="*" ? a*b : a/b);
        }
    }
    cout << G;
}

```
> 1 votes

# Answer
## Mathetmatica, 143 bytes

```
Last@Flatten[#~ImportString~"CSV"&/@StringSplit@#]//.{{a___,b_,c_,o_String,d___}:>{a,o[b,c],d},"+"->Plus,"*"->Times,"/"->Divide,"-"->Subtract}&

```

Anonymous function, takes a string as input (`StringSplit[#]`), splits at whitespace, `ImportString[#,"CSV"]` acts on each element separately (it's like a soft form of eval), converting number-like strings to numbers, however operators remain as strings.

`//.` \- repeatedly apply replacement rule: go through the input list, until you hit an operator character, e.g. `{1, 4, 2, / *}` becomes `{1 /[4,2] *}`, then `{*[1, /[4,2]]}`.

String-forms of operators are replaced with the names of the actual Mathematica functions which do the required thing. Output is a number.
> 1 votes

# Answer
# 05AB1E (legacy), ~~32~~ ~~30~~ 29 bytes

```
#vyDd≠i©'+Qi+ë®'-Qi-ë®'*Qi*ë/

```

Try it online or verify all test cases.

**Explanation:**

```
#                # Split the (implicit) input-string on spaces
 vy              # Loop `y` over each item:
   D             #  Duplicate `y` so it's now twice on the stack
    d≠i          #  If it's NOT a number:
       ©         #   Store the operator-character in variable `®` (without popping)
        '+Qi    '#   If it's a "+":
            +    #    Add the top two numbers together
       ë®'-Qi   '#   Else-if it's a "-":
             -   #    Subtract the top two numbers from each other
       ë®'*Qi   '#   Else-if it's a "*":
             *   #    Multiply the top two numbers together
       ë         #   Else (it's a "/"):
        /        #    Divide the top two numbers
                 # (after the loop: implicitly output the result)

```

We're using the legacy version, because `d` checks if a value is a number, whereas the new 05AB1E version would check if it's a non-negative number (\\$\geq0\\$) instead.

---

If `eval` would have been allowed, it's **~~14~~ 11 bytes** instead:

```
9LD(s'(«:.V

```

Try it online or verify all test cases.

**Explanation:**

```
9L           # Push the list [1,2,3,4,5,6,7,8,9]
  D          # Duplicate it on the stack
   (         # Negate each integer: [-1,-2,-3,-4,-5,-6,-7,-8,-9]
    s        # Swap to get the original list again
     '(«    '# Append a "(" to each: ["1(","2(","3(","4(","5(","6(","7(","8(","9("]
        :    # Replace all "-N" with "N(" in the (implicit) input-string
         .V  # Eval the string as 05AB1E code
             # (implicitly output the result)

```

Negative numbers are indicated with a trailing `(` instead of leading `-` in 05AB1E. Apart from that, the calculations are also done in Reverse Polish Notation style.
> 1 votes

# Answer
# , ~~132 105~~ 96 bytes

```
for(i in scan(,""))F="if"(grepl("[0-9]",i),c(as.double(i),F),c(get(i)(F[2],F[1]),F[-1:-2]));F[1]

```

Try it online!

Port of Amro's Matlab answer. I never realized the two languages had so much in common. Saved 27 bytes thanks to Giuseppe ! See edit history for test cases.
> 1 votes

# Answer
# Runic Enchantments, 118 bytes

```
?!/rRlril1-{=
R:0q}"+0"{:}≠?\"-0"{:}≠?\"*0"{:}≠?\"/0"{≠?\R}l1=?!@
\r\ /<?6+{{~{~/?7-S{{~{~/?8 *{{~{~/?7,S{{~/\

```

Try it online!

Runic already operates in Reverse Polish Notation, so its just a matter of reading the input and converting from char-based symbols to actual operators.

Due to the near-perfect space usage on the lower line, `≠?\` works out to the same number of bytes as `=?!\`, but is easier to read.

### Explanation

```
    /<                                                Entry
?!\rRlril1-{=                                         Read all inputs
/r/                                                   Reverse the stack (we need to parse from front to back, not back to front; mirrors flipped to preserve visual flow direction within the explanation)
R                                                     Initial parsing loop entry
 :                                                    Duplicate
  0q}                                                 Concat TOS with a 0 on the end
     "+0"                                             Construct string +0 (checking for addition)
         {:}                                          RoL, Dup, RoR (this allows the same i0 string concatenation to be reused)
            ≠?\                                       Compare, if not equal, continue
               "-0"{:}≠?\"*0"{:}≠?\"/0"{≠?\           Do the same for -, *, and /
                                           R          Bottom-of-loop entry
                                            }         Rotate numerical value to bottom of stack
                                             l1=?!@   If stack is only 1 object, print and terminate
           ~{~/                                       If equal, pop no-longer-needed i0 concatenations and the original input char
        +{{                                           Add most recent 2 values
      ?6                                              Skip to bottom-of-loop
               ?7-S{{~{~/?8 *{{~{~/?7,S{{~/           Similar chunks for -, *, and /
                                           \          Mirror up to bottom of main loop (after-math skips wind up here)
                                     ,S{{~            Note that division does not need to pop no-longer-needed concatenated string, as we used up the last one in the comparison

```

Invalid input characters will be treated as their decimal equivalents because `char`s implicitly convert to `int`s. Strings will crash.

Operators *must* be compared with their string equivalents, again, because `char`s implicitly convert to `int`s. A numerical `43` is identical to the character `+`. `0q` is the shortest method of generating a unique string representation of the stack object that can be compared with known expected strings. Additionally a string *may not be the ToS* when constructing a new string or the two strings are automatically concatenated.
> 1 votes

# Answer
# JavaScript (Node.js), 92 bytes

```
s=>(g=(d,c=q.pop())=>1/c?+c:(b=g(d=g()),c)>'-'?b/d:c>'+'?b-d:c>'*'?b+d:b*d)(q=s.split(/ +/))

```

Try it online!
> 1 votes

# Answer
# Python 2.7 (205 bytes)

Edit: Version 2. After consideration I was able to shave off a lot by using the operator module:

```
from operator import *
f={'*':mul,'/':div,'+':add,'-':sub}
def e(r):
    l=[]
    for i in r:
        try:i=float(i);l.append(i)
        except:l.append(f[i](*l[-2:]));del l[-3:-1]
    return l
print e(raw_input().split())[0]

```
> 0 votes

# Answer
# Java 243

Input comes from the command line. Element 0 in the Float\[ \] isn't actually used for storing the inputs, however it is needed for the first assignment of the temp value. The Float constructor takes care of parsing for negative values and values with a decimal place.

```
interface R{static void main(String[]a){Float t,f[]=new Float[a.length];int i=0;for(String s:a){t=f[i];switch(s){case"-":t=-t;case"+":f[--i]+=t;break;case"/":t=1/t;case"*":f[--i]*=t;break;default:f[++i]=new Float(s);}}System.out.print(f[i]);}}

```

Ungolfed:

```
interface ReversePolishNotation{
    static void main(String[]arg){
        Float temp, fVals[]=new Float[arg.length];
        int i=0;
        for(String str:arg){
            temp=fVals[i];
            switch(str){
                case"-":
                    temp=-temp;
                case"+":
                    fVals[--i]+=temp; break;
                case"/":
                    temp=1/temp;
                case"*":
                    fVals[--i]*=temp; break;
                default:
                    fVals[++i]=new Float(str);
            }
        }
        System.out.print(fVals[i]);
    }
}

```
> 0 votes

# Answer
# Kotlin, 175 bytes

```
{var s=List(0){0f}
for(t in it.split(" ")){try{s=s+t.toFloat()}catch(e:Exception){val(a,b)=s.takeLast(2)
s=s.dropLast(2)+listOf(a+b,a-b,a*b,a/b)["+-*/".indexOf(t)]}}
s.last()}

```

Try it online!
> 0 votes

# Answer
# Dart, 196 bytes

```
F(l,n)=>l.removeAt(l.length-1-n);G(a,b,c)=>c=='+'?a+b:c=='-'?a-b:c=='*'?a*b:a/b;f(s){var l=[];s.split(' ').forEach((a){l.add('+-*/'.contains(a)?G(F(l,1),F(l,0),a):double.parse(a));});return l[0];}

```

Try it online!
> 0 votes

# Answer
# Perl 5.10+: 95 bytes

```
perl '-anEmy@a;push@a,/\d/?$_:do{$j=pop@a;$i=pop@a;($i*$j,$i+$j,0,$i-$j,0,$i/$j)[-42+ord]}for@F;say$a[0]'

```

Size 95 bytes (diff with `perl -e ''` which is 10 bytes).

Ungolfed, expanding command line flags (thanks to `perl -MO=Deparse '-anE...`) and slightly edited:

```
use feature 'say';
while (defined($_ = readline)) {
    our @F = split(' ', $_, 0);
    my @a;
    push @a, /\d/ ? $_ : do {
        $j = pop @a;
        $i = pop @a;
        ($i * $j, $i + $j, 0, $i - $j, 0, $i / $j)[-42 + ord($_)]
    } foreach (@F);
    say $a[0];
}

```

Notes:

* See documentation of perl command line switches about `-a`, `-n` and `-E`
* ASCII values of the following chars are useful to understand the expression involving `ord`:
> ```
> * 42
> + 43
> - 45
> / 47
>
> ```

## An alternate implementation using regexp matching and replacement: 100 bytes

```
perl '-pEwhile(s!\b([-0-9.]+)\s+([-0-9.]+)\s+([-+*/])!" ".($1*$2,$1+$2,0,$1-$2,0,$1/$2)[-42+ord$3]!e){}y/ //d'

```

Ungolfed:

```
use feature 'say';

while (defined($_ = readline ARGV)) {
    while (s[\b([-0-9.]+)\s+([-0-9.]+)\s+([-+*/])][' ' . ($1 * $2, $1 + $2, 0, $1 - $2, 0, $1 / $2)[-42 + ord($3)];]e) {
        ();
    }
    y/ //d;
} continue {
    die "-p destination: $!\n" unless print $_;
}

```
> 0 votes

# Answer
## **Javascript, 112 bytes**

```
r=c=>(s=[],f=(a,b,o)=>eval(`${b}${o}${a}`),c.split(' ').forEach(e=>s.push(!+e?f(s.pop(),s.pop(),e):+e)),s.pop())

```

Zero error checking, uses the eval function, but it works with all valid RPN expressions.

r is a function (eg. r('2 3 +') returns 4)
> 0 votes

# Answer
# PHP, 172 bytes (Demo)

```
<?foreach(preg_split('~ +~',fgets(STDIN))as$v)if(floatval($v))$s[]=$v;else{[$e,$d]=array_splice($s,-2);$s[]=$v=="+"?$e+$d:($v=="-"?$e-$d:($v=="*"?$e*$d:$e/$d));}echo $s[0];

```

Previously entertained techniques:

```
<?do{$_GET[a]=preg_replace_callback('~(-?[\d.]+) +(-?[\d.]+) +([*/+-])~',fn($m)=>($m[3]=='+'?$m[1]+$m[2]:($m[3]=='-'?$m[1]-$m[2]:($m[3]=='*'?$m[1]*$m[2]:$m[1]/$m[2]))),$_GET[a],1,$c);}while($c);echo $_GET[a]; // 208

<?$v=$_GET[a];do{$v=preg_replace_callback('~(-?[\d.]+) +(-?[\d.]+) +([*/+-])~',fn($m)=>($m[3]=='+'?$m[1]+$m[2]:($m[3]=='-'?$m[1]-$m[2]:($m[3]=='*'?$m[1]*$m[2]:$m[1]/$m[2]))),$v,1,$c);}while($c);echo $v; // 202

<?while(preg_match('~(.*?)(-?[\d.]+) (-?[\d.]+) ([*/+-])(.*)~',$_GET[a],$m))$_GET[a]=$m[1].($m[4]=='+'?$m[2]+$m[3]:($m[4]=='-'?$m[2]-$m[3]:($m[4]=='*'?$m[2]*$m[3]:$m[2]/$m[3]))).$m[5];echo $_GET[a]; // 198

<?$v=$_GET[a];while(preg_match('~(.*?)(-?[\d.]+) +(-?[\d.]+) +([*/+-])(.*)~',$v,$m))$v=$m[1].($m[4]=='+'?$m[2]+$m[3]:($m[4]=='-'?$m[2]-$m[3]:($m[4]=='*'?$m[2]*$m[3]:$m[2]/$m[3]))).$m[5];echo $v;  // 194

```
> 0 votes

# Answer
## JavaScript, 106

```
e=i=>i.split(' ').reduce((s,t)=>[s,isNaN(t)?eval([s.pop(),s.pop()].reverse().join(t+' ')):t].flat(),[])[0]

```

**Testing code**

```
console.log([
    '-4 5 +',
    '5 2 /',
    '5 2.5 /',
    '5 1 2 + 4 * 3 - +',
    '4 2 5 * + 1 3 2 * + /'
].map(e))

```

**Output**

```
[1, 2.5, 2, 14, 2]

```

UPD I've just noticed that eval is not allowed, but it's not the only JS solution with eval so I'd let it posted
> 0 votes

# Answer
# AWK, 104 bytes

```
{for(;i++<NF;d[e]=b?--b?--b?--b?f/g:f*g:f-g:f+g:$i)(b=index("+-*/",$i))?(g=d[e--])(f=d[e]):e++}1,$0=d[e]

```

Try it online!

This one mostly abuses ternaries like a case statement to save characters... The code loops through each conditional argument, setting variable `b` to 0-5 depending on whether the argument is a number (`b==0`) or an index 1-4 into the string `"+-*/"`. Then the "end of loop" code uses `b` to either compute the results of a mathematical operation, or just to reference the current argument.

It uses array `d` like a stack.

```
for(;i++<NF;                                     ) - loops through args
            d[e]=b?--b?--b?--b?f/g:f*g:f-g:f+g:$i  - effectively a "case" statement

```

And the body of the loop does:

```
(b=index("+-*/",$i))?                  :    - sets "b" to 0-5, also if/then/else
                     (g=d[e--])(f=d[e])     - set "f" and "g" to args to be used in math
                                        e++ - for numbers, advance stack pointer

```

And once all the argument have been processed:

```
1,$0=d[e] - the "1," forces output even if "d[e]" is 0

```
> 0 votes

# Answer
# JavaScript (Node.js), 112 bytes

```
s=>s.split` `.map(i=>1/i?i&&t.push(+i):t.push([(r=t.pop())+(o=t.pop()),o-r,r*o,o/r]['+-*/'.indexOf(i)]),t=[])&&t

```

Try it online!

Modified from an existing answer but did thorough modify :(
> 0 votes

# Answer
# Factor, 87 bytes

```
[ " "split [ dup dec> [ dec> ] [ last "+-*/"index { + - * / } nth execute ] if ] each ]

```

Try it online!

Or, if word lookup (i.e. converting a string to an executable function of the same name) doesn't count as too eval-y:

# Factor, 72 bytes

```
[ " "split [ dup dec> [ dec> ] [ "math"lookup-word execute ] if ] each ]

```

Try it online!
> 0 votes

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


# Question
Title: Generate all possible equations from a list of numbers
*This is my first codegolf post so let me know if I have missed anything. Thanks :)*

# **Description**

You are given a list of numbers with `2 < n <= 6` length i.e. \[1, 10\] or \[75, 9, 9, 8, 2, 100\]. Given the basic operators `+ - / *` you must try and generate all possible equations. The list of numbers to pull from is: `[1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 25, 50, 75, 100]`.

Defining this list **as is** for your program does not count towards the byte count, same goes for defining the list of operators. There are two separate **winning** conditions: 1) Smallest program; 2) Fastest program.

Generating all equations when `n = 6` results in ~200 billion equations. It might be wise to verify that your code works with lower lengths values first, or a subset from the list of numbers.

**Rules**

1. Equations must be in postfix notation
2. No duplicate equations i.e. `1 1 2 + +` and `1 1 2 + +`
3. Handle commutativity i.e. `1 10 + 2 4 + +` and `10 2 1 4 + + +`. Remove commutative equations so only one remains.

**Extra Challenges**

* Calculate all equations, only accepting positive 3 digit solutions. If at any stage during the process the solution becomes negative `1 100 -` or non-int `100 3 /`, stop processing the entire equation and move onto the next equation.

**Final Notes**

Some of you may have recognised the list of numbers from Countdown or Letters and Numbers. I myself wrote a program (unoptimized, but functional) to calculate all possible 3 digit solutions under the shows rules. It took 90 minutes to run with multithreading, though the slowest part was calculating the equations, not generating them.

Good luck!

# Answer
> 2 votes
# 05AB1E, 31 bytes

```
æ¦€œ€`"+-/*"Igãâε¬s`s¦∍S«ðý}ÙIK

```

Goes for the code-golf portion. Brute-force approach, so pretty slow.
Doesn't handle the *Extra Challenge* portion.

Try it online.

**Explanation:**

```
æ             # Get the powerset of the (implicit) input-list
 ¦            # Remove the leading empty sublist
  €œ          # Map over each powerset-list, and get all its permutations
    €`        # Flatten the list of lists of lists one level down
"+-/*"        # Push the string of operators
      Ig      # Push the input-length
        ã     # Get the cartesian power of the two
â             # Get the cartesian product of the two lists to create all possible pairs
 ε            # Map over each pair of [list, operator-string]:
  ¬           # Push the head (the list) (without popping)
   s          # Swap so the pair is at the top of the stack again
    `         # Pop and push the list and string separately to the stack
     s        # Swap so the list is at the top of the stack
      ¦       # Remove its first item
       ∍      # Shorten the operator string to the length of this list
        S     # Convert the operator string to a list of characters
         «    # Merge it to the list of integers
          ðý  # Join it by spaces
 }Ù           # After the map: uniquify the results
   IK         # Remove the singular input-integers, since they're not equations
              # (after which the result is output implicitly)

```

Since 05AB1E uses Reverse Polish/Postfix notation, here the program with additional footer to get the result of each equation: Try it online.

---
Tags: code-golf, combinatorics, permutations, fastest-code
---