title: Incremental Betting

text:
# Question
Title: Incremental Betting
Several months ago I had this question as a pre-screening puzzle for an interview. Recently when thinking about blog material, it popped in my head as a good example to use for solving a problem functionally. I'll post my solution to this as soon as I'm done writing my blog post.

NOTE: This question was asked on StackOverflow a year ago, and was downvoted after a few (incorrect) answers. I assume it was downvoted for being an obvious interview or homework question. Our answers here should be code golfed deep enough for someone not to think about using them!

---

In a race, you bet using the following strategy. Whenever you lose a bet, you double the value of the bet for the next round. Whenever you win, the bet for the next round will be one dollar. You start the round by betting one dollar.

For example, if you start with 20 dollars, and you win the bet in the first round, lose the bet in the next two rounds and then win the bet in the fourth round, you will end up with 20+1-1-2+4 = 22 dollars.

You are expected to complete the function, `g`, which takes two arguments:

1. The first argument is an integer `a` which is the initial money we amount we have when we start the betting.
2. The second argument is a string `r`. The ith character of outcome will be either 'W' (win) or 'L' (lose), denoting the result of the ith round.

Your function should return the amount of money you will have after all the rounds are played.

If at some point you don't have enough money in your account to cover the value of the bet, you must stop and return the sum you have at that point.

**Sample run**

```
1st round - Loss: 15-1 = 14
2nd round - Loss: 14-2 = 12 (Bet doubles)
3rd round - Loss: 12-4 = 8
4th round - Win: 8 + 8 = 16
5th round - Loss:16-1 = 15 (Since the previous bet was a win, this bet has a value of 1 dollar)
6th round - Loss: 15-2 = 13
7th round - Loss: 13-4 = 9
8th round - Loss: 9-8 = 1

```

The function returns `1` in this case

The winner is determined by least number of characters INSIDE of the implied function definition. Cooperate by language if desired. I know mine can be improved!

# Answer
> 5 votes
### GolfScript, 33 characters

```
{
1\{2$2$<!{1&{+1}{:b-b.+}if.}*;}/;
}:g;

```

*Examples (online):*

```
> 13 'LLLWLLLL'
6
> 4 'LWWLWLWWWL'
9
> 5 'LLLWWWLLWLWW'
2
> 2 'LW'
1

```

*Annotated code:*

```
1\            # prepare stack a b r
{             # for each char in r
  2$2$<!{     #   if a>=b
    1&        #     take last bit of character (i.e. 0 for L and 1 for W)
    {         #     if W
      +       #       a <- a+b
      1       #       b <- 1
    }{        #     else
      :b-     #       a <- a-b
      b.+     #       b <- 2*b
    }if       #     end if
    .         #     create dummy value
  }*          #   end if
  ;           #   drop (i.e. either the dummy or the character)
}/            # end for
;             # discard current bet value

```

# Answer
> 5 votes
# Python 2, ~~72~~ ~~68~~ 62 bytes

```
def g(a,s,n=1):
 for c in s:
    if a>=n:a,n=((a+n,1),(a-n,2*n))[c<'W']
 return a

```

Call it like so: `g(15,'LLLWLLLL')`.

This simply loops through the string, changing the value of the money that we have based on the character.

Here is a sample program that runs tests on this function:

```
import random
def g(a,s,n=1):
 for c in s:
    if a>=n:a,n=((a+n,1),(a-n,2*n))[c<'W']
 return a

for i in range(14):
    s=''.join(('L','W')[random.randint(0, 1)] for e in range(random.randint(10, 15)))
    print'g(%i,%s):'%(i,`s`),
    print g(i,s)

```

Sample output:

```
g(0,'LLWWWWWWLWWWWW'): 0
g(1,'WLLWWWWWWWW'): 1
g(2,'WWWLLLWLLW'): 2
g(3,'LLLLWLWLWWWWLL'): 0
g(4,'LWWWWLWLWWW'): 12
g(5,'WWLWWLLWWW'): 12
g(6,'LLLWWWLLLLWLLWL'): 3
g(7,'WWLLWWLWLWLWLLL'): 7
g(8,'WLLLWWWWWLLWLL'): 2
g(9,'WWWLLWLLLLLWL'): 6
g(10,'LWWWWLLLWL'): 7
g(11,'WLLLLWLWWWW'): 5
g(12,'WLLWWLWWWL'): 17
g(13,'LLLWLLWLWLWLWW'): 6

```

With a little change to the tester, we can get the average profit of many runs:

```
import random
def g(a,s,n=1):
 for c in s:
    if a>=n:a,n=((a+n,1),(a-n,2*n))[c<'W']
 return a

r=[]
for i in range(5000):
    for i in range(1000):
        s=''.join(('L','W')[random.randint(0, 1)] for e in range(random.randint(10, 15)))
        r+=[i-g(i,s)]
a=0
for n in r:
    a+=n
print float(a)/len(r)

```

Sample output (took quite a while, since we are calling the function `5000000` times):

```
-0.0156148

```

Edit: Thanks to Howard and Danny for further golfing.

EDIT: now the program checks for whether there is enough money to make the bet. This actually saves bytes.

# Answer
> 4 votes
### R, 95 characters

```
g=function(a,r){n=1;for(i in 1:nchar(r)){s=substr(r,i,i);if(s=='L'){a=a-n;n=n*2}else{a=a+n;n=1};if(n>a)break};a}

```

Indented:

```
g=function(a,r){
    n=1
    for(i in 1:nchar(r)){
        s=substr(r,i,i)
        if(s=='L'){
            a=a-n
            n=n*2
            }else{
                a=a+n
                n=1
                }
        if(n>a)break
        }
    a
    }

```

Usage:

```
> g(15,'LLWLLLL')
[1] 1
> g(20,'WLLW')
[1] 22
> g(13,'LLWLLLLWWLWWWLWLWW')
[1] 7

```

# Answer
> 3 votes
# J - 63 55 char

Now with the added bonus of not being incorrect! It's even exactly as long as before.

```
((+/\@,(0{<#[)_,~|@]);@('W'<@(2^i.@#);.1@,}:)*_1^=&'L')

```

Takes the starting amount of money as the left argument and the win/loss streak on the right.

Explanation: The program splits evenly into something like a composition of two functions, both detailed below. The first turns the win/loss streak into the values of the bets, with corresponding sign, and then the second actually figures out the answer given the initial money and this transformed win/loss streak.

```
;@('W'<@(2^i.@#);.1@,}:)*_1^=&'L'   NB. win/loss as sole argument
                         _1^=&'L'   NB. -1 for every L, +1 for W
      <@(      );.1                 NB. split vector into streaks:
   'W'              ,}:             NB.  cut on wins, shift right by 1
         2^i.@#                     NB. for each, make doubling run
;@(                    )*           NB. unsplit, multiply by signs

(+/\@,(0{<#[)_,~|@])   NB. money on left, above result on right
                |@]    NB. absolute value of bets
             _,~       NB. append infinity to end
 +/\@,                 NB. partial sums with initial money
      (  <  )          NB. 1 whenever money in account < bet
          #[           NB. select those money values corresp. to 1s
       0{              NB. take first such item

```

Note that we prepend the money to the bets before taking the partial sums, but we append the infinite bet to the end of the list of bet values. This is what shifts the value of the account overtop of the next bet, and using infinity allows us to always have the last element as a catch-all.

Usage:

```
   15 ((+/\@,(0{<#[)_,~|@]);@('W'<@(2^i.@#);.1@,}:)*_1^=&'L') 'LLLWLLLL'
1
   NB. naming for convenience
   f =: ((+/\@,(0{<#[)_,~|@]);@('W'<@(2^i.@#);.1@,}:)*_1^=&'L')
   20 f 'WLLW'
22
   2 f 'LW'
1
   13 f 'LLWLLLLWWLWWWLWLWW'
7
   12 13 14 15 28 29 30 31 (f"0 _) 'LLWLLLLWWLWWWLWLWW'  NB. for each left argument
6 7 0 1 14 15 39 40

```

# Answer
> 3 votes
# JavaScript (ECMAScript 6 Draft) - ~~62~~ ~~51~~ 50 Characters (in function body)

```
function g(a,r,t=0,b=1)
a>=b&&(c=r[t])?g((c=c>'L')?a+b:a-b,r,t+1,c||2*b):a

```

Defines a recursive function `g` with two arguments:

* `a` \- the current amount of money you have; and
* `r` \- the string of wins/losses.

And two optional arguments:

* `t` \- the index of the current round of betting (initially `0`)
* `b` \- the amount of money for the current bet (again initially `1`).

Ungolfed:

```
function g(a,r,t=0,b=1){      // declare a function g with arguments a,r,t,b where
                              // t defaults to 0 and b defaults to 1
c = r[t];                     // get the character in the win/loss string for the current
                              // round.
if (   a>=b                   // check if we have enough money
    && c )                    // and if the string has not ended
{
  if ( c > 'L' )              // check if we've won the round
  {
    return g(a+b,r,t+1,1);    // if so call g again adding the winnings and resetting the
                              // cost.
  } else {
    return g(a-b,r,t+1,2*b);  // otherwise, subtract from the total money and double the
                              // cost.
  }
} else {
  return a;                   // If we've run out of money or got to the end then return
                              // the current total.
}}

```

# JavaScript (ECMAScript 6) - ~~61~~ ~~58~~ 54 Characters (in function body)

```
function g(a,r)
(b=1,[b=b>a?b:x>'L'?(a+=b,1):(a-=b,b*2)for(x of r)],a)

```

Explanation:

```
(b=1,                        // Initialise the cost to 1
 [                           // for each character x of r using array comprehension
     b=
       b>a?b                 // if we have run out of money do b=b
       :x>'L'?(a+=b,1)       // else if we've won collect the winnings and reset b=1
             :(a-=b,2*b)     // else subtract the cost from the total money and double
                             // the cost for next round.
  for(x of r)]               // Repeat for each character
                             // array.
,a)                          // Finally, return a.

```

**Tests**

```
console.log(g(0,'LLLLLWWLWWLW')) // 0
console.log(g(1,'WWWLLLWWWWLLWW')) //1
console.log(g(2,'LLWLWWWWWWWL')) //1
console.log(g(3,'WWWWWWWLLLWL')) //3
console.log(g(4,'LWWLWLWWWL')) //9
console.log(g(5,'LLLWWWLLWLWW')) //2
console.log(g(6,'LWLLLLWWLWWW')) //0
console.log(g(7,'WWLWWLLLWLWLW')) //4
console.log(g(8,'WWLWWLLWLWL')) //13
console.log(g(9,'WWWLLLWLLWLWWW')) //5
console.log(g(10,'WLWLLWWWWWWWL')) //18
console.log(g(11,'WLWLWLWLLLWLLW')) //17
console.log(g(12,'WWLWWWLLWL')) //17
console.log(g(13,'WWWWLWLWWW')) //21
console.log(g(15,'LLLW')) //16
console.log(g(15,'LLLL')) //0
console.log(g(14,'LLLL')) //7
console.log(g(2,'LW')) //1
console.log(g(2,'LL')) //1
console.log(g(2,'WLL')) //0

```

# Answer
> 1 votes
## C#, 123

```
return q.Aggregate(new{b=1,c=w,x=1},(l,o)=>l.x<0?l:o=='W'?new{b=1,c=l.c+l.b,x=1}:new{b=l.b*2,c=l.c-l.b,x=l.c-l.b-l.b*2}).c;

```

The .NET Fiddle

A blog post explaining

# Answer
> 1 votes
# Python, 74 bytes

```
def g(a,r,b=1):
 for l in r:
  if l>"L":a+=b;b=1
  else:a-=b;b*=2
 return a

```

I defined function g which takes a (the amount of money you have at start) and r (which is the results of the bets) It initializes the amount of the first bet at 1. Then for each result of the bets, if it is a win ("W" in r) you gain the money and bet comes back to 1. Else you lose the amount of the bet, and the amount for the next bet doubles. Finally it returns the money you have. You can use it like this:

```
print g(20,"WLLW") # 22
print g(15,"LLLWLLLL") # 1

```

I think this can be golfed furthermore.

# Answer
> 1 votes
# C, 107 characters

```
f(int a,char*r,int n){return*r&&n<a?*r<77?f(a-n,r+1,n*2):f(a+n,r+1,1):a;}g(int a, char*r){return f(a,r,1);}

```

I'm using a recursive function here, because most of the time the implementation is shorter. But I'm not quite sure if it is the case here, because I needed to make an additional wrapper function so my function does in fact only take 2 arguments. The third argument in function `f` is needed for the current bet (the accumulator).

Without the wrapper function this solution would only be 73 characters long, but you would need to pass an additional parameter with the value 1 (the inital bet) to get the proper result.

ungolfed:

```
f(int a,char*r,int n){
    return *r&&n<a
                ?*r<77
                    ?f(a-n,r+1,n*2)
                    :f(a+n,r+1,1)
                :a;
}
g(int a,char*r){
    return f(a,r,1);
}

```

# Answer
> 1 votes
# Ruby, 76 64 (in function body) bytes

EDIT : improved the answer by removing 3 bytes :

```
n=1;r.each_char{|c|;c>'L'?(a+=n;n=1):(a-=n;n*=2);break if n>a};a

```

---

using func (82 bytes) :

```
def g(a,r);n=1;r.each_char{|c|;c>'L'?(a,n=a+n,1):(a,n=a-n,n*2);break if n>a};a;end

```

using lambda (76 bytes) :

```
g=->a,r{n=1;r.each_char{|c|;c>'L'?(a,n=a+n,1):(a,n=a-n,n*2);break if n>a};a}

```

the run :

```
p g.call(15, 'LLLWLLLL') # 1
p g.call(20, 'WLLW') # 22
p g.call(13, 'LLWLLLLWWLWWWLWLWW') # 7

```

# Answer
> 1 votes
# C, 90

```
g(int a,char*r){int c=1;while(*r){*r++%2?c=1,a++:(c*=2);if(c>a){c/=2;break;}}return++a-c;}

```

# Answer
> 1 votes
# Javascript, 63

```
function g(a,s){x=1;for(i in s)if(x<=a)s[i]>'L'?(a+=x,x=1):(a-=x,x*=2);return a}

```

Sample runs:

```
console.log(g(15, 'LLLWLLLL'));  //1
console.log(g(20, 'WLLW'));  //22
console.log(g(13, 'LLWLLLLWWLWWWLWLWW')); //7

```

**JSFiddle w/ logging**

Ungolfed:

```
function g(a,s){
  x=1;                //bet starts at 1
  for(i in s)         //loop through win/lose string
    if(x<=a)          //check if we still have money to bet
      s[i]>'L'?
        (a+=x,x=1):   //win: add the bet amount to your total, and reset bet to 1
        (a-=x,x*=2);  //lose: subtract the bet amount from your total, and double your bet
  return a            //return your money
}

```

# Answer
> 1 votes
# Javascript (*ES5*) 69 64 60 bytes within function

```
function g(a,r){b=1;for(i in r)b=b>a?b:r[i]>'L'?(a+=b,1):(a-=b,b*2);return a}

```

Variation: (*same length*)

```
function g(a,r,b){for(i in r)b=b?b>a?b:r[i]>'L'?(a+=b,1):(a-=b,b*2):1;return a}

```

Test cases: (*taken from plannapus's solution*)

```
g(15,'LLWLLLL'); // 1
g(20,'WLLW'); // 22
g(13,'LLWLLLLWWLWWWLWLWW'); // 7

```

# Answer
> 1 votes
# Golfscript, ~~51~~ ~~41~~ ~~36~~ 35 bytes

### Inner function

```
1\{@2$-@2*@(1&{@@+1@}*.3$3$<!*}do;;

```

This assumes that we start with a positive amount of money and that the win-loss string will be non-empty, so that at least one bet can be performed.

### Example

```
{
  # Push initial bet amount.
  1\
  # STACK: Money Bet Outcomes
  {
    # Subtract bet amount from money.
    @2$-
    # STACK: Bet Outcomes Money
    # Double bet amount.
    @2*
    # STACK: Outcomes Money Bet
    # Remove first character from win-loss string and check if its ASCII code is odd.
    @(1&
    # STACK: Money Bet Outcomes Boolean
    # If it is, we've won, so add the doubled bet amount to the money and push 1 as the
    # new bet amont.
    {@@+1@}*
    # STACK: Money Bet Outcomes
    # Duplicate win-loss string, bet amonut and money.
    .3$3$
    # STACK: Money Bet Outcomes Outcomes Bet Money
    # If the next bet amount is less than our money and the win-loss string is not empty,
    # repeat the loop.
    <!*
    # STACK: Money Bet Outcomes Boolean
  }do
  # STACK: Money Bet Outcomes
  ;;
  # STACK: Money
}:f                                      # Define function.

];                                       # Clear stack.

20 'WLLW'               f
2  'LW'                 f
13 'LLWLLLLWWLWWWLWLWW' f
14 'LLWLLLLWWLWWWLWLWW' f

]p                                       # Print results as array.

```

gives

```
[22 1 7 0]

```

Try it online.

# Answer
> 1 votes
# Haskell, 62

```
g a=fst.foldl(\(t,b)l->if l=='W'then(t+b,1)else(t-b,2*t))(a,1)

```

or with both arguments named (65 chars):

```
g a r=fst$foldl(\(t,b)l->if l=='W'then(t+b,1)else(t-b,2*t))(a,1)r

```

Note that `g a r = 1 + a + the number of Ws in r + the number of trailing Ls in r` (69):

```
g a r=a+1+l(filter(=='W')r)-2^l(takeWhile(/='W')(reverse r))
l=length

```

# Answer
> 1 votes
# Python 2 – 65 bytes

Now beaten by the current best Python solution, but I cannot not share it:

```
def g(r,a,b=1):
    if r>"">a>=b:a=g(r[1:],*[(a+b,1),(a-b,b*2)][r[0]<"W"])
    return a

```

As some other Python solutions, I use the function arguments for declaring `b` outside the function definition, but as the function is recursive, this actually serves some purpose other than golfing here.

I also needed to change the order of the function arguments in order for the tuple unpacking into function arguments to work.

In case you wonder, `r>"">a>=b` is short for `r and a>=b`.

# Answer
> 1 votes
# C#, 74 characters inside method

My very first attempt on this site...

```
int b=1;foreach(var c in r)if(b<=a){a+=c>'L'?b:-b;b=c>'L'?1:b*2;}return a;

```

Or, more readable:

```
int bet = 1;
foreach (var chr in r)
{                       // these brackets are left out in short version
   if (bet <= a)
   {
       a += chr > 'L' ? bet : -bet;
       bet = chr > 'L' ? 1 : bet * 2;
   }
}
return a;

```

Pretty naive, not that many tricks... mainly taking advantage of char being ordinal and string being enumerable. Saving a few characters by extraneous looping when player runs out of money.

# Answer
> 1 votes
# Java, 93 bytes (inside function)

-2 bytes thanks to ceilingcat

```
int b=1;for(int c:r.getBytes()){if(m<b)return m;if(c<87){m-=b;b*=2;}else{m+=b;b=1;}}return m;

```

Try it online!

# Answer
> 0 votes
# Ruby, 84 characters

```
def g(a,r,n=1)
return a if !r[0]||n>a
s=r[1..-1]
r[0]<?M?g(a-n,s,n*2):g(a+n,s,1)
end

```

Same approach as my other answer in C, but I wanted to try ruby for Code-Golfing. The advantage to the C version is that I don't need to create a wrapper function, I can simply use the default values for parameters.

# Answer
> 0 votes
# K, 76

```
g:{x+/-1_last'{(,1_*x),(("LW"!/:((2*;{1});(-:;::)))@\:**x)@\:x 1}\[(y;1;0)]}

```

.

```
k)g[15;"LLLWLLLL"]
1
k)g[20;"WLLW"]
22
k)g[50;"WLLLWLWLWLWLW"]
56

```

# Answer
> 0 votes
# C - ~~64~~ 59 (Inside function)

Yet another C answer. It takes advantage of the fact that the value of the variable stays on the stack. So this my fail with some compilers, but it did work properly wherever I tested. Also, I took the `%2` from tia to save a character. Sorry!

```
f(int s,char*r){
    int a=1;
    for(;*r&&(*r++%2?s+=a,a=1:s<a?0:(s-=a,a*=2)););
    a=s;
}

```

# Answer
> 0 votes
# Python, 86

```
def y(a,s):
 for l in s.split('W'):
    a+=1;k=2**len(l)
    if k>a:return int(bin(a)[3:],2)
 return a-k

```

I know this is nowhere near the shortest solution, but I wanted to demonstrate a different approach, that iterates over loss streaks rather than individual bets. `int(bin(a)[3:],2)` gives the integer with the most significant bit from the binary representation of `a` deleted, which is the amount of money the person will have after losing increasing powers of 2 until he or she can no longer bet, because a is currently 1 higher than his or her actual amount of money. This version assumes the initial capital is positive.

# Answer
> 0 votes
## Batch - 212

```
@echo off&setlocal enabledelayedexpansion&set r=%2&set a=%1&set c=1&powershell "&{'%2'.length-1}">f&set/pl=<f
for /l %%a in (0,1,%l%)do if "!r:~%%a,1!"=="L" (set/aa-=!c!&set/ac*=2) else set/aa+=!c!&set c=1
echo %a%

```

Expample -

```
H:\uprof>bet.bat 15 LLLWLLLL
1

```

# Answer
> 0 votes
# Japt, 38 bytes

```
V¬r@Z=WX<Z?X:Y¶'L?W=ZÑX-Z:(W=1X+Z}UW=1

```

Try it

Probably needs some golfing :) But it seems to getting correct results.

**NOTE** This is a full program that is trivial to turn into a function by prepending `UV{`. The byte count inside the function will be the same.

Transpiled JS Explained:

```
// V: input string of W's and L's
V
  // split V into an array of characters
  .q()
  // reduce
  .r(function(X, Y, Z) {
    return
      // W contains the current bet,
      // save it to a temp variable Z
      Z = W,
      // do we have enough to bet?
      X < Z
        // not enough to bet, return the previous amount
        ? X
         // we can bet, did we lose this round
         : Y === "L"
           // we lost, increment bet and decrease holdings
           ? (W = Z * 2, X - Z)
           // we won, reset bet and increase holdings
           : (W = 1, X + Z)
   },
   // U: initial holdings
   U,
   // initialize bet to 1
   W = 1
 )

```

# Answer
> 0 votes
# PowerShell, ~~68~~ 81 bytes

```
param($n,$s)$w=1;$s|% t*y|%{if($n-ge$w){$n+=(-$w,$w)[$_%2];$w/=(.5,$w)[$_%2]}};$n

```

Try it online!

This challenge needs some very awkward assignments meaning I couldn't chain together one big update. It does use the fact that 'W' is 87 in ASCII and 'L' is 76 so modding by 2 gives you access to easy true/false values. `|% t*y` is the standard toCharArray shortcut and updating the wager using division turned out to be the cheapest way I could find (divides it either by a half on a loss (doubling it), or divides it by itself on a win (setting it to 1)).

Plus many bytes because I missed constraint. Will work on golfing down the patch

# Answer
> 0 votes
# 05AB1E, 19 bytes

```
vDX@iy'WQiX+1UëXxU-

```

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

Note that 05AB1E has no functions, so this is a full program instead.
Takes the string input first, and the integer input second (newline delimited in STDIN).

Try it online or verify some more test cases.

**Explanation:**

```
v               # Loop over each character `y` of the (implicit) input-string:
 D              #  Duplicate the current integer
                #  (which is the implicit input-integer in the first iteration)
  X@i           #  If the integer is larger than or equal to variable `X`:
                #  (NOTE: variable `X` is 1 by default)
     y'WQi     '#   If the current character `y` is a 'W':
          X+    #    Increase the integer by `X`
          1U    #    And reset variable `X` to 1
         ë      #   Else (the current character `y` is an 'L' instead):
          X  -  #    Decrease the integer by `X`
           xU   #    And set variable `X` to double its current value
                # (the integer at the top of the stack is implicitly output after the loop)

```

---
Tags: code-golf, function
---


title: Play Zip, Zap, Zop

text:
# Question
Title: Play Zip, Zap, Zop
There's a little improv warm up game where you arrange yourselves in a circle and send zips, zaps, and zops around by pointing to a person and saying the next word in the sequence, then they do the same until all of you are warmed up or whatever.

Your task is to create a program that gives the next word in sequence given an input word. (Zip --\> Zap --\> Zop --\> Zip) Since there's a lot of different ways to say these three words and flairs that can be added to them, your program should imitate case and letter duplication and carry suffixes.

To elaborate, your input will be one or more `Z`s, then one or more `I`s, `A`s, or `O`s (all the same letter), then one or more `P`s, (all letters up to this point may be in mixed case) followed by some arbitrary suffix (which may be empty). You should leave the runs of `Z`s and `P`s, as well as the suffix exactly as received, but then change the `I`s to `A`s, `A`s to `O`s, or `O`s to `I`s, preserving case at each step.

## Example Test Cases

```
zip         ==> zap
zAp         ==> zOp
ZOP         ==> ZIP
ZiiP        ==> ZaaP
ZZaapp      ==> ZZoopp
zzzzOoOPppP ==> zzzzIiIPppP
Zipperoni   ==> Zapperoni
ZAPsky      ==> ZOPsky
ZoPtOn      ==> ZiPtOn
zipzip      ==> zapzip
zapzopzip   ==> zopzopzip
zoopzaap    ==> ziipzaap

```

## Rules and Notes

* You may use any convenient character encoding for input and output, provided that it supports all ASCII letters and that it was created prior to this challenge.
* You may assume the input word is some variant of Zip, Zap, or Zop. All other inputs result in undefined behavior.
    + Valid inputs will full-match the regex `Z+(I+|A+|O+)P+.*` (in mixed case)

Happy Golfing!

# Answer
> 9 votes
# JavaScript (Node.js),  ~~69 63 57~~  54 bytes

```
s=>Buffer(s).map(c=>s|c%4<1?s=c:c+c*90%320%34%24-8)+''

```

Try it online!

### How?

We process the input string \\$s\\$ character by character.

We reuse \\$s\\$ as a flag: as soon as a numeric value is stored in it, we know that we must not update anything else.

To identify `"p"` (112) and `"P"` (80), we use the fact that their ASCII codes are multiples of \\$4\\$ and the ASCII codes of the other letters at the beginning of the string (`"z"`, `"Z"` and vowels) are not.

To turn a vowel with ASCII code \\$c\\$ into its counterpart \\$n\\$ while leaving `z` and `Z` unchanged, we use the following function:

$$n=c+((((90\times c) \bmod 320)\bmod 34)\bmod 24)-8$$

```
 letter | ASCII code |  * 90 | % 320 | % 34 | % 24 | - 8 | new letter
--------+------------+-------+-------+------+------+-----+-----------------------
   'i'  |     105    |  9450 |  170  |   0  |   0  |  -8 | 105 -  8 =  97 -> 'a'
   'a'  |      97    |  8730 |   90  |  22  |  22  |  14 |  97 + 14 = 111 -> 'o'
   'o'  |     111    |  9990 |   70  |   2  |   2  |  -6 | 111 -  6 = 105 -> 'i'
   'z'  |     122    | 10980 |  100  |  32  |   8  |   0 | 122 +  0 = 122 -> 'z'
   'I'  |      73    |  6570 |  170  |   0  |   0  |  -8 |  73 -  8 =  65 -> 'A'
   'A'  |      65    |  5850 |   90  |  22  |  22  |  14 |  65 + 14 =  79 -> 'O'
   'O'  |      79    |  7110 |   70  |   2  |   2  |  -6 |  79 -  6 =  73 -> 'I'
   'Z'  |      90    |  8100 |  100  |  32  |   8  |   0 |  90 +  0 =  90 -> 'Z'

```

### Commented

```
s =>                  // s = input string
  Buffer(s)           // convert it to a Buffer of ASCII codes
  .map(c =>           // for each ASCII code c in s:
    s |               //   if s is numeric
    c % 4 < 1 ?       //   or c is either 'p' or 'P':
      s = c           //     turn s into a numeric value and yield c
    :                 //   else:
      c +             //     update c
        c * 90 % 320  //     by applying the transformation function
        % 34 % 24     //     (see above)
        - 8           //
  ) + ''              // end of map(); coerce the Buffer back to a string

```

# Answer
> 6 votes
# C (gcc),  ~~81 ... 61 48~~  46 bytes

*Saved 2 bytes thanks to @Grimy*

Port of my JS answer. Outputs by modifying the input string.

```
f(char*s){for(;*++s%4;*s+=*s*90%320%34%24-8);}

```

Try it online!

### Commented

```
f(char * s) {       // f = function taking the input string s
  for(;             //   for each character *s in s:
    *++s % 4;       //     advance the pointer; exit if *s is either 'p' or 'P' (it's safe
                    //     to skip the 1st character, as it's guaranteed to be 'z' or 'Z')
    *s +=           //     update the current character:
      *s * 90 % 320 //       apply a transformation formula that turns
      % 34 % 24     //       a vowel into the next vowel in the sequence
      - 8           //       while leaving 'z' and 'Z' unchanged
  );                //   end of for()
}                   // end of function

```

# Answer
> 5 votes
# Stax, 19 bytes

```
Ç╛√êΣ%,╖FP╚`=Lh←⌡·ƒ

```

Run and debug it

# Answer
> 5 votes
# Retina 0.8.2, 21 bytes

```
iT`Io`A\OIia\oi`^.+?p

```

Try it online! Transliterates letters up to and including the first `p`, although the `z` and `p` aren't in the transliteration section so aren't affected. The first `O` is quoted because it normally expands to `13567` and the second `o` is quoted because it too is magic; in the first part of the transliteration it expands to the other string. The resulting transliteration is therefore from `IAOIiaoi` to `AOIiaoi` then removing the duplicate source letters results in `IAOiao` to `AOIaoi`.

# Answer
> 4 votes
# C, 43 bytes

```
f(char*s){for(;*++s%4;*s^=*s%16*36%98%22);}

```

Try it online!

Based on Arnauld's answer. I did a brute-force search to find the shortest formula that turns a =\> o, o =\> i, i =\> a, z =\> z.

# Answer
> 3 votes
# Japt, ~~22~~ 20 bytes

-2 bytes thanks to Oliver

```
r"%v+"_d`i¬iao¯`pu}"

```

Try it online!

# Answer
> 3 votes
# , 110 76 bytes

-36 bytes thanks to Krill

This function takes an input of one string.

```
function(a)sub(s<-sub('z+(.+?)p.*','\\1',a,T),chartr('aioAIO','oaiOAI',s),a)

```

Try it online!

# Answer
> 2 votes
# Perl 6, ~~41~~ 33 bytes

```
{S:i{.+?p}=$/~~tr/iaoIAO/aoiAOI/}

```

Try it online!

Simple case-insensitive substitution to shift the vowel section.

# Answer
> 2 votes
# Python 3.8 (pre-release), ~~81~~ 78 bytes

```
lambda s,p='iaoIAO':''.join(('aoiAOI'+c)[(p:=p*(ord(c)%4)).find(c)]for c in s)

```

Try it online!

# Python 2, 98 bytes

```
lambda s:''.join(('aoiAOI'+c)[(-~-('p'in s[:i].lower())*'iaoIAO').find(c)]for i,c in enumerate(s))

```

Try it online!

# Answer
> 2 votes
# Java (JDK), 52 bytes

```
s->{for(int i=0;s[++i]%4>0;)s[i]^=s[i]%16*36%98%22;}

```

Try it online!

* Port of Grimy's C answer. Make sure to upvote his answer!

# Answer
> 1 votes
# C# (Visual C# Interactive Compiler), 60 bytes

```
n=>{for(int i=0;n[i]%4>0;)n[i]^=(char)(n[i++]%16*36%98%22);}

```

Based off of Grimy's C answer.

Try it online!

# Answer
> 1 votes
# Perl 5, 31 bytes

```
s/.+?p/$&=~y,iaoIAO,aoiAOI,r/ei

```

TIO

# Answer
> 1 votes
# SNOBOL4 (CSNOBOL4), 183 bytes

```
	INPUT (BREAK('Pp') SPAN('Pp')) . P REM . S
A	P 'a' ='o'	:S(A)
Z	P 'A' ='O'	:S(Z)F(P)
I	P 'i' ='a'	:S(I)
K	P 'I' ='A'	:S(K)F(P)
O	P 'o' ='i'	:S(O)
L	P 'O' ='I'	:S(L)
P	OUTPUT =P S
END

```

Try it online!

# Answer
> 1 votes
# Python 2, 84 bytes

```
f=lambda s,r='':s[0]in'pP'and r+s or f(s[1:],r+('aoiAOI'+s[0])['iaoIAO'.find(s[0])])

```

Try it online!

# Answer
> 1 votes
# C/C++ (VC++ compiler) 192bytes

this is a rather naive try but anyway

```
void f(char*I){int c[]={-8,14,6},B=1,v[]={105,97,111},j=0;for(*I;*I>0&B;I++){if(*I==80|*I==112){B=0;break;}if(*I==90|*I==122){}else{for(j;j<3;j++){if(*I==v[j]|*I==v[j]-32){*I+=c[j];break;}}}}}

```

some slightly more readable Version is this

```
#include "stdafx.h"

void f(char * theString)
{
    signed int change[] = {'a'-'i','o'-'a','o'-'i'}; // add this to the vowel to get the next one
    char theVowels[] = {'i','a','o'};
    int breaker = 1;
    printf("Input %s\n",theString);
    for (int i = 0;(theString[i] != '\0') && breaker; i++)
    {
        switch (theString[i])
        {
            case 'Z': /*fall through*/
            case 'z': break;
            case 'P': /*fall through*/
            case 'p': breaker = 0;
                      break;
            default:
            {
                for (int j = 0; j < 3; j++)
                {
                    if ((theString[i] == theVowels[j]) || (theString[i]==(theVowels[j]-'a'+'A')))
                    {
                        theString[i] += change[j];
                        break;
                    }
                }
            }
            break;
        }

    }
    printf("Output %s\n",theString);
}
int main()
{
    char theString[]= "zzzzIIIIp0815-4711"; // a test string
    f(theString);
    return 0;
}

```

# Answer
> 0 votes
# Ruby, 40 bytes

```
$_[$&]=$&.tr"IAOiao","AOIaoi"if/z+.+?p/i

```

Try it online!

# Answer
> 0 votes
# 05AB1E (legacy), 22 bytes

```
l'pkIg‚£ć…iaoDÀ‚Du+`‡ì

```

Try it online or verify all test cases.

Can definitely be golfed a bit more..

Uses the legacy version of 05AB1E instead of the Elixir rewrite, because `+` merges fields in same-length lists, whereas the new version would need a pair-zip-join `‚øJ` instead.

**Explanation:**

```
l                       # Lowercase the (implicit) input-string
                        #  i.e. "ZipPeroni" → "zipperoni"
 'pk                   '# Get the index of the first "p"
                        #  i.e. "zipperoni" → 2
    Ig‚                 # Pair it with the length of the entire input-string
                        #  i.e. 2 and "zipperoni" → [2,9]
       £                # Split the (implicit) input-string into parts of that size
                        #  i.e. "ZipPeroni" and [2,9] → ["Zi","pPeroni"]
        ć               # Extract head: push the head and remainder separately to the stack
                        #  i.e. ["Zi","pPeroni"] → ["pPeroni"] and "Zi"
         …iao           # Push string "iao"
             DÀ         # Duplicate, and rotate it once towards the left: "aoi"
               ‚        # Pair them up: ["iao","aoi"]
                Du      # Duplicate and transform it to uppercase: ["IAO","AOI"]
                  +     # Python-style merge them together: ["iaoIAO","aoiAOI"]
                   `    # Push both strings to the stack
                    ‡   # Transliterate; replacing all characters at the same indices
                        #  i.e. "Zi", "iaoIAO" and "aoiAOI" → "Za"
                     ì  # Prepend it to the remainder (and output implicitly)
                        #  i.e. ["pPeroni"] and "Za" → ["ZapPeroni"]

```

# Answer
> 0 votes
# PHP, 30 bytes

too simple for a TiO:

```
<?=strtr($argn,oiaOIA,iaoIAO);

```

Run as pipe with `-nF`. For PHP 7.2, put the string literals in quotes.

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


title: Is there a smaller tautogram checker?

text:
# Question
Title: Is there a smaller tautogram checker?
I got into code-golfing recently and tried to write the smallest tautogram checker.

A *tautogram* is a sentence in which all words start with the same letter, for example: **Flowers flourish from France**.

Given a sentence as input, determine whether it is a tautogram.

## Test Cases

```
Flowers flourish from France
    True

This is not a Tautogram
    False

```

I came up with this python code (because it is my main language):

```
print(True if len(list(set([x.upper()[0] for x in __import__('sys').argv[1:]]))) == 1 else False)

```

Usage:

```
python3 tautogram.py Flowers flourish from France
# True
python3 tautogram.py This is not a Tautogram
# False

```

The sentence may contain commas and periods, but no other special characters, only upper and lower case letters and spaces.

Its size is 98 bytes. Is there a smaller solution in any language?

# Answer
# 05AB1E, 5 bytes

```
l#€нË

```

Try it online!

---

```
l      # Lowercase input.
 #     # Split on spaces.
  €н   # a[0] of each.
    Ë  # All equal?

```

Did this on mobile excuse the no explanation.
> 7 votes

# Answer
# Python 2, 47 bytes

```
lambda s:len(set(zip(*s.lower().split())[0]))<2

```

Try it online!

Came up with this on mobile. Can probably be golfed more.
> 4 votes

# Answer
# PowerShell, ~~57~~ ~~50~~ 41 bytes

```
(-split$args|% s*g 0 1|sort -u).count-eq1

```

Try it online!

Takes input and `split`s it on whitespace. Loops through each word, and grabs the first letter by taking the `s`ubstrin`g` starting at position `0` and going for `1` character. Then `sort`s the letters (case-insensitive by default) with the `-u`nique flag to pull out only one copy of each letter, and verifies the `count` of those names are `-eq`ual to `1`. Output is implicit.

*-9 bytes thanks to mazzy.*
> 3 votes

# Answer
# Clojure, 80 bytes

Try it online!. TIO doesn't support Clojure's standard String library though, so the first version will throw a "Can't find lower-case" error.

```
(fn[s](use '[clojure.string])(apply =(map first(map lower-case(split s #" ")))))

```

Ungolfed:

```
(defn tautogram? [s]
  (use '[clojure.string])
  (->> (split s #" ") ; Get words
       (map lower-case)
       (map first) ; Get first letter of each word
       (apply =))) ; And make sure they're all the same

```

I made a version that avoids the import:

```
(fn [s](apply =(map #(if(<(-(int %)32)65)(int %)(-(int %) 32))(map first(take-nth 2(partition-by #(= %\ )s))))))

 ; -----

(defn tautogram? [s]
  (->> s
       (partition-by #(= % \ )) ; Split into words
       (take-nth 2) ; Remove spaces
       (map first) ; Get first letter
       ; Convert to uppercased letter code
       (map #(if (< (- (int %) 32) 65) ; If attempting to uppercase puts the letter out of range,
               (int %) ; Go with the current code
               (- (int %) 32))) ; Else go with the uppercased  code
       (apply =))) ; And check if they're all equal

```

But it's **112 Bytes**.
> 3 votes

# Answer
# Haskell, 71 bytes

```
f s|c<-fromEnum.head<$>words s=all(`elem`[-32,0,32]).zipWith(-)c$tail c

```

Try it online!

---

# Haskell, ~~61~~ 58 bytes (using `Data.Char.toLower`)

* Saved three bytes thanks to nimi.

```
import Data.Char
(all=<<(==).head).(toLower.head<$>).words

```

Try it online!
> 2 votes

# Answer
# 05AB1E (legacy), 5 bytes

```
#€¬uË

```

Try it online!

```
#     // split on spaces
 €¬   // get the first letter of each word
   uË // check if they're the same (uppercase) letter

```
> 2 votes

# Answer
# Perl 5 (`-p`), 20 bytes

```
$_=!/^(.).* (?!\1)/i

```

TIO

following comments in case bad punctuation (31 bytes)

```
$_=!/^\W*+(.).*(?=\b\w)(?!\1)/i

```

31 bytes

otherwise there's another approach, also with 31 bytes:

```
$h{ord()%32}++for/\w+/g;$_=2>%h

```

31 bytes other
> 2 votes

# Answer
# Brachylog, 5 bytes

```
ḷṇ₁hᵛ

```

Try it online!

```
         The input
ḷ        lowercased
 ṇ₁      and split on spaces
   hᵛ    is a list of elements which all start with the same thing.

```
> 2 votes

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

```
s=>!s.match(/\b\w+/g).some(p=s=>p-(p=Buffer(s)[0]&31))

```

Try it online!

Or **47 bytes** if each word (but the first) is guaranteed to be preceded by a space.
> 1 votes

# Answer
# Japt , 5 bytes

```
¸mÎro

```

Try it

```
¸mÎro     :Implicit input of string
¸         :Split on spaces
 m        :Map
  Î       :  Get first character
   r      :Reduce by
    o     :  Keeping the characters that appear in both, case-insensitive
          :Implicit output as boolean

```
> 1 votes

# Answer
# C# (Visual C# Interactive Compiler), 41 bytes

```
n=>n.Split().GroupBy(c=>c[0]|32).Single()

```

Throws an exception if false, nothing if true.

Try it online!
> 1 votes

# Answer
# Perl 6, 19 bytes

```
{[eq] m:g/<<./}o&lc

```

Try it online!
> 1 votes

# Answer
# Java, (36 bytes)

```
s->!s.matches("(?i)(.).* (?!\\1).*")

```

TIO
> 1 votes

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


# Question
Title: Counting the number of restricted forests on the Möbius ladder of length n
OEIS sequence A020872 counts the number of restricted forests on the Möbius ladder Mn.

## The Challenge

The challenge is to write a program that takes an integer as an input `n > 1` and returns `A020872(n)`, the number of restricted forests on the Möbius ladder Mn. This is , so shortest code wins. (An ulterior motive is to perhaps extend the length of this sequence by a bit.)

## Definitions

A *restricted forest* is a partition of the graph such that each part is either a (undirected) path or an isolated vertex.

The *Möbius ladder* Mn is a graph which can be thought of the 2n-gon with diagonals drawn between all opposite vertices.

## Example

Here are the 34 restricted forests on M2 (a square with diagonals drawn). Notice that the first graph is partitioned into four isolated vertices, the second is partitioned into one path and two isolated vertices, etc.

# Answer
> 10 votes
## CJam (58 56 chars)

Some characters unprintable, and one is a tab which will be mangled by the StackExchange software:

```
"¶3¬î¿Á·    7ÛÈmÈÚÚ¡"256b454b212f-{__W%.*A<1b+}qi*-4=

```

Online demo. This will run online for n=400 in about three seconds.

Encoded by `xxd`:

```
0000000: 22b6 0233 93ac eebf c1b7 0609 3794 dbc8  "..3........7...
0000010: 6dc8 1015 dada a122 3235 3662 3435 3462  m......"256b454b
0000020: 3231 3266 2d7b 5f5f 5725 2e2a 413c 3162  212f-{__W%.*A<1b
0000030: 2b7d 7169 2a2d 343d                      +}qi*-4=

```

### Explanation

A Möbius ladder is basically a ladder with two extra edges. Given a restricted forest on a ladder, it can be lifted to between 1 and 4 restricted forests on the Möbius ladder. The edges can be added provided that doesn't create a vertex of degree 3 or a cycle. The degrees of the four corners and their interconnections form 116 classes of restricted forest on the ladder, although some of them are equivalent due to symmetries of the rectangle. I wrote a program to analyse the extensions of a ladder of length n to one of length n+1, and then merged the classes into 26 equivalence classes. This gives a closed form

$$\begin{bmatrix} 1 \\ 1 \\ 1 \\ 1\end{bmatrix}^T \begin{bmatrix} 1 & 2 & 2 & 0 \\ 1 & 2 & 1 & 1 \\ 2 & 3 & 4 & 1 \\ 0 & 0 & 1 & 0 \\ \end{bmatrix}^{n-2} \begin{bmatrix} 0 \\ 1 \\ 0 \\ 0\end{bmatrix} + $$

$$\begin{bmatrix} 2 \\ 2 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 2 \\ 2\end{bmatrix}^T \begin{bmatrix} 2 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 0 & 1 & 0 & 0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 2 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 \\ 1 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 1 \\ 3 & 2 & 2 & 1 & 1 & 2 & 1 & 4 & 2 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 2 \\ \end{bmatrix}^{n-2} \begin{bmatrix} 0 \\ 0 \\ 2 \\ 2 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0\end{bmatrix} + $$

$$\begin{bmatrix} 1 \\ 2 \\ 4 \\ 4 \\ 1 \\ 1 \\ 3 \\ 2 \\ 2 \\ 2 \\ 3 \\ 4 \\ 4\end{bmatrix}^T \begin{bmatrix} 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 2 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 2 & 0 & 1 & 1 & 0 & 1 & 1 & 0 & 1 & 1 & 1 \\ 1 & 0 & 0 & 4 & 0 & 0 & 3 & 0 & 0 & 2 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 2 & 1 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 \\ 1 & 0 & 0 & 1 & 0 & 0 & 2 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 1 & 2 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 2 \\ 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 2 & 0 & 0 & 2 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 2 & 2 & 0 \\ 0 & 2 & 3 & 0 & 1 & 1 & 0 & 2 & 1 & 0 & 1 & 2 & 4 \\ \end{bmatrix}^{n-2} \begin{bmatrix} 1 \\ 0 \\ 1 \\ 1 \\ 2 \\ 0 \\ 1 \\ 0 \\ 0 \\ 0 \\ 1 \\ 2 \\ 1\end{bmatrix}$$

so values can be computed fast by taking three linear recurrences and then adding them, but this isn't looking very golfy.

However, if we take the irreducible factors of the various characteristic polynomials and multiply together one of each (ignoring multiplicity) we get a polynomial of degree 10 which gives a working single linear recurrence.

## Constructive approach (58 chars)

```
qi:Q2*,Wa*e!{Wa/{_W%e<}%$}%_&{{,1>},2few:~{:-z(Q(%}%0-!},,

```

Online demo. It will run online for `n=2` without problems and for `n=3` with a bit of patience. For `n=1` it crashes, but since OP has chosen to exclude that case from the requirements it's not a fundamental problem.

### Dissection

```
qi:Q          e# Take input from stdin, parse to int, store in Q
2*,Wa*e!      e# Take all permutations of (0, -1, 1, -1, 2, -1, ..., -1, 2*Q-1)
{             e# Map to canonical form...
  Wa/         e#   Split around the -1s
  {_W%e<}%    e#   Reverse paths where necessary to get a canonical form
  $           e#   Sort paths
}%
_&            e# Filter to distinct path sets
{             e# Filter to path sets with valid paths:
  {,1>},      e#   Ignore paths with fewer than two elements (can't be invalid; break 2ew)
  2few:~      e#   Break paths into their edges
  {:-z(Q(%}%  e#   The difference between the endpoints of an edge should be +/-1 or Q (mod 2Q)
              e#   So their absolute values should be 1, Q, 2Q-1.
              e#   d => (abs(d)-1) % (Q-1) maps those differences, and no other possible ones, to 0
              e#   NB {:-zQ(%}% to map them all to 1 would save a byte, but wouldn't work for Q=2
  0-!         e#   Test that all values obtained are 0
},
,             e# Count the filtered distinct path sets

```

---

A more efficient version takes 98 bytes:

```
qi2*:Q{a{__0=[1Q2/Q(]f+Qf%_&1$-\f{+E}~}:E~}/]{_W%>!},:MW=0{_{M\f{__3$_@&@:e<@|^{=}{^j}?}1b}{,)}?}j

```

Online demo

This builds the possible paths by depth-first search, then uses a memoised function which counts the possible restricted forests for a given set of vertices. The function works recursively on the basis that any restricted forest for a given non-empty set of vertices consists of a path containing the smallest vertex and a restricted forest covering the vertices not in that path.

# Answer
> 6 votes
# JavaScript (ES6),  ~~160 158~~  146 bytes

```
n=>(g=(e,v,p)=>[...Array(N=2*n),N-1,1,n].reduce((s,x,i)=>(m=1<<(x=i<N?i:(p+x)%N))&v?s:s+g((i>=N)/p?[...e,1<<p|m]:e,v|m,x),g[e.sort()]^(g[e]=1)))``

```

Try it online!

Notes:

* This is quite inefficient and will time-out on TIO for \\$n\>4\\$.
* \\$a(5) = 10204\\$ was found in a bit less than 3 minutes on my laptop.

### Commented

```
n => (                        // n = input
  g = (                       // g = recursive function taking:
    e,                        //   e[] = array holding visited edges
    v,                        //   v   = bitmask holding visited vertices
    p                         //   p   = previous vertex
  ) =>                        // we iterate over an array of N + 3 entries, where N = 2n:
    [ ...Array(N = 2 * n),    //   - 0...N-1: each vertex of the N-gon (starting points)
      N - 1,                  //   - N      : previous vertex \
      1,                      //   - N+1    : next vertex      }-- connected to p
      n                       //   - N+2    : opposite vertex /
    ].reduce((s, x, i) =>     // reduce() loop with s = accumulator, x = vertex, i = index:
      ( m = 1 << (            //   m is a bitmask where only the x-th bit is set
          x = i < N           //   and x is either:
              ? i             //   - i if i < N
              : (p + x) % N   //   - or (p + x) mod N otherwise
      )) & v ?                //   if this vertex was already visited:
        s                     //     leave s unchanged
      :                       //   else:
        s +                   //     add to s
        g(                    //     the result of a recursive call:
          (i >= N) / p ?      //       if p and x are connected (i >= N and p is defined):
            [ ...e,           //         append to e[]:
              1 << p | m      //           the edge formed by p and x
            ]                 //           and uniquely identified by 1 << p | 1 << x
          :                   //       else:
            e,                //         leave e[] unchanged
          v | m,              //       mark the vertex x as visited
          x                   //       previous vertex = x
        ),                    //     end of recursive call
      g[e.sort()] ^           //   sort the edges and yield 1 if this list of edges has not
      (g[e] = 1)              //   already been encountered; either way, save it in g
    )                         // end of reduce()
)``                           // initial call to g with e = ['']

```

# Answer
> 2 votes
# Jelly, ~~61~~ 58 bytes

```
®R,³;Ø+
Ḥ©Ḷµ1ị+¢%®ḟ€;€€1¦-Ẏ;€)Ẏ$ƬẎṣ€-Ẉ’ẠƊƇU¹Ø.ị>/Ɗ?€€Ṣ€QL‘

```

Try it online!

This is the shorter version; it is optimised for shorter length versus algorithmic complexity and speed.

# Jelly, 85 bytes

```
%®ḟ
1ị+³;Ø+¤ç,1ị+®_3¤R‘¤Ʋç;€-Ʋ“”2ị>-Ʋ?Ẏ;€
Ḥ©Ḷ;€-Ç€Ẏ$ƬẎṣ€-Ẉ=1ẸƊÐḟU¹1ị>0ị$Ʋ?€€Ṣ€QL‘+=2$

```

Try it online!

Here’s a longer version that adds extra code to avoid trying redundant paths. The check for n=2 at the end is to cope with the specific case for n=2 which looks like a red/blue cross in the example and isn’t generated by this code. This second version completed n=4 in less than 13 seconds on TIO, but times out for higher numbers.

---
Tags: code-golf, sequence, combinatorics, graph-theory, set-partitions
---


# Question
Title: For 2 arrays, subtract every element in one array from the position-matching element in the other
For 2 arrays each with X elements, what is the SHORTEST code to subtract every element in the second from every element in the first, 1 to 1

so, for example:

A1 = \[10,11,12\]

A2 = \[1,2,3\]

A1 "-" A2 should == \[9,9,9\]

# Answer
## R, 3 chars

(following Chris' counting method that includes the variable names in the count)

```
a-b

```

`a` and `b` can be defined as follows:

```
a <- c(10,11,12)
b <- c(1,2,3)

```

(`c` is the array construction function in R)
> 12 votes

# Answer
# J, 1 char

I will answer too because finally I don't have to use 2 bytes worth of enclosing brackets for J. :)

```
   -

   10 11 12 - 1 2 3
9 9 9

```
> 7 votes

# Answer
## Scheme, 11 chars

Assume the lists are named `a` and `b`:

```
(map - a b)

```

Example:

```
(map - '(10 11 12) '(1 2 3))  ; => (9 9 9)

```
> 5 votes

# Answer
## In Haskell (10):

```
zipWith(-)

```

will do the job. Please note, that the lists will be truncated, if their length isn't equal.
> 4 votes

# Answer
```
>>> class L(list):
...  def __sub__(self, other):
...   return map(int.__sub__,self, other)
...
>>> a=L([10,11,12])
>>> b=L([1,2,3])
>>> a-b
[9, 9, 9]
>>>

```
> 4 votes

# Answer
# ES6, 20

```
a.map((x,i)=>x-b[i])

```
> 4 votes

# Answer
### In Python (24):

```
map(lambda a,b:a-b,a,b)

```

### Smaller (21):

```
map(int.__sub__,a,b)

```
> 3 votes

# Answer
Groovy:

```
List a = [1,2,3]
List b=[2,7,9]
[0,1,2].each { println(a[it]-b[it]) }

```
> 2 votes

# Answer
### Scala, 51 chars

```
Array(10,11,12) zip Array(1,2,3)map(x=>x._1-x._2)

```

(but includes initialisation, Array-Declaration)

```
(10 to 12).zip (1 to 3)map(x=>x._1-x._2)

```

is a bit shorter, but produces an Vector.

```
a zip b.map(x=>x._1-x._2)

```

is even shorter, but of course I could do

```
a zip b.map f

```

then. Or just

```
g

```
> 2 votes

# Answer
# CJam, 10 bytes

CJam is newer than this challenge, but I thought it's funny how uncompetitive it is for once:

```
l~]z{~-}%p

```

This is an STDIN to STDOUT program, reading input like `[10 9 8] [1 2 3]`. I know everyone else is answering in snippets, but that wouldn't really be shorter here, because you'd have to replace `]` by something like `a\a\+`.
> 2 votes

# Answer
# TI-BASIC, 5 bytes

```
L1-L2

```

Input lists are stored in the `L1` and `L2` tokens. (TI-BASIC doesn't have STDIN or equivalent.)
Answer is stored in `Ans`.

**Example:**

```
{10,11,12→L1
      {10 11 12}
{1,2,3→L2
         {1 2 3}
L1-L2
         {9 9 9}

```
> 1 votes

# Answer
Not counting `USE: syntax math sequences ; !` because it's not needed (on the REPL).

Factor: `[ - ] 2map`
> 0 votes

# Answer
Not the shortest, but this is what I came up with in javascript...

```
t=0;
ar=[];
for(i=0;i<ar.length;i++){
   t=a[i]-b[i];
   ar.push(temp);
};

```

**Input:** a = \[10,11,12\], b = \[1,2,3\]
**Output:** \[9,9,9\]
> 0 votes

# Answer
# 8th, 10 bytes

**Code**

```
' n:- a:op

```

**Explanation**

`a:op` takes two arrays and invokes the word `n:-` to the corresponding elements of "a1" and "a2", producing a new array "a3".

**Example**

```
ok> [10,11,12] [1,2,3] ' n:- a:op .
[9,9,9]

```
> 0 votes

# Answer
# Java 8, 45 bytes

```
a->b->{for(int i=0;i<a.length;a[i]-=b[i++]);}

```

Modifies the first input-array instead of returning a new one to save bytes.

**Explanation:**

Try it here.

```
a->b->{            // Method with two integer-array parameters and no return-type
  for(int i=0;     //  Start at index 0
      i<a.length;  //  Loop over the input arrays by index
    a[i]-=b[i++]   //   Modify array `a` by subtracting the values of `b` on the same index
  );               //  End of loop
}                  // End of method

```
> 0 votes

# Answer
# Java 8, 29 bytes

I got creative with I/O types for this. It's a lambda (curried) from an ordered `IntStream` (A1) to a lambda from a mutable `List<Integer>` (implementing `remove(int)`, e.g. `ArrayList`) (A2) to `IntStream`. Assign to `Function<IntStream, Function<List<Integer>, IntStream>>`.

```
s->l->s.map(n->n-l.remove(0))

```

Try It Online

Yeah, that's right; I'm using stateful lambdas. I could lose 4 byes by taking A2 as a `Stack` and using `pop`, but I'm hesitant to stray that far from the `List` interface.
> 0 votes

# Answer
# Pyt, 3 bytes

```
←←-

```

Takes arrays as input; alternatively, if the arrays are already on the stack, with the second one on the top, it's one character:

```
-

```

Explanation:

```
←        Get first array
 ←       Get second array
  -      Get elementwise difference (as an array)

```

Try it online!
> 0 votes

# Answer
# Funky, 27 bytes

```
a=>b=>a::map((n i)=>n-b[i])

```

Try it online!
> 0 votes

# Answer
# Jelly, 1 byte

```
_

```

Try it online!
> 0 votes

# Answer
# Add++, 7 bytes

```
L*,BcB_

```

Try it online!

Auto vectorisation is so boring.
> 0 votes

# Answer
# Zsh, 27 bytes

That's right, you can zip arrays in your shell scripts!

**Input**: arrays `a` and `b`
**Output**: stdout

```
for x y (${a:^b}) <<<$[x-y]

```

Try it online! (It takes more code to read stdin into arrays than it does to pairwise subtract!)

If the output must be another array, either **27** or **29** bytes.

```
for x y (${a:^b}) c+=$[x-y]    # if c was declared as an array
for x y (${a:^b}) c+=($[x-y])  # if c was not declared

```
> 0 votes

# Answer
# SmileBASIC, 13 bytes

```
ARYOP 1,A,A,B

```

Inputs: `A`, `B`
Output: `A`
> 0 votes

# Answer
# Japt, 3 bytes

```
í-V

```

Try it

```
í-V     :Implicit input of arrays U & V
í V     :Interleave both
 -      :Reduce each pair by subtraction

```
> 0 votes

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


title: BF Last binary digit

text:
# Question
Title: BF Last binary digit
### Task

Your task is to write as short as possible program preferably in Brainf\**k which determines the last digit of given number after it's conversion from decimal to binary system.

### Input

An integer in decimal system consisting of up to 200 digits. There is a newline character (ASCII 10) after the given number

### Output

One digit (1 or 0) which is the last digit of given number after it's conversion to binary system.

### Example

`4372667135165131576213 -> 1`

# Answer
# Wolfram Language (Mathematica), 13 bytes

```
Boole@OddQ@#&

```

Try it online!
> 0 votes

---
Tags: code-golf, brainfuck
---


title: Tips for golfing in Racket / Scheme

text:
# Question
Title: Tips for golfing in Racket / Scheme
What general tips do you have for golfing in Racket / Scheme? I'm looking for ideas that can be applied to code golf problems in general that are at least somewhat specific to Racket / Scheme (e.g. "remove comments" is not an answer).

---

I'm aware Scheme and Racket (formerly PLT Scheme) are technically different languages but are quite similar in many ways and much code (I suspect) will run mostly as intended in either. If your tip only applies to one of the aforementioned languages, note as such.

# Answer
The expressions `'x`, ``x`, `,x`, an `,@x` automatically expand to `(quote x)`, `(quasiquote x)`, `(unquote x)`, and `(unquote-splicing x)`, respectively. This is purely a syntactic transformation, and can be applied anywhere. This gives a convenient notation for one-variable functions:

```
; Defining a function:
(define ,x (+ x x))
; Calling a function:
(display ,2)

```

which expands to

```
; Defining a function:
(define (unquote x) (+ x x))
; Calling a function:
(display (unquote 2))

```

I'm not sure what the semantics for shadowing a syntactic keyword such as `quote` or `quasiquote` with a bound variable, although code like the above worked in the interpreters I tested it on, and `unquote-splicing` is less than ideal since it has a two-character abbreviation, but `unquote` is an auxillary syntax with a one-character abbreviation and so is ideal for this hack.
> 3 votes

# Answer
In **Racket**, `λ` and `lambda` are synonymous keywords for constructing anonymous functions, but `λ` is 2 bytes where `lambda` is 6.

In **Scheme**, there's no such keyword `λ` and you're stuck with `lambda`.
> 9 votes

# Answer
Use `~a` to convert numbers and symbols to strings.
> 7 votes

# Answer
# Use shorter synonyms

There's a number of procedures in Racket that have mostly-equivalent shorter versions. (They are usually not equivalent: for example, `(car (cons 1 2))` works where `(first (cons 1 2))` fails. But you can make the substitution if you know they are synonyms in your case.)

This list is probably incomplete: I probably don't know about most of the things that could go in this list yet.

* `(= a b)` instead of `(equal? a b)` when comparing numbers.
* `'(1 2)` instead of `(list 1 2)`.
* `car`, `cadr`, `cdr` for `first`, `second`, and `rest`.
* `null?` instead of `empty?`
* `modulo` instead of `remainder` when the modulus is positive.
* `floor` instead of `truncate` when its argument is positive.
> 6 votes

# Answer
When using **Racket**, bind variables using `λ` to shave off a few bytes. In **Scheme**, `lambda` makes this trick not applicable, unless one is binding four or more variables.

Example: One variable saves 2 bytes over `let`/`define`

```
(define n 55)(* n n) ; 20 bytes

(let([n 55])(* n n)) ; 20 bytes

((λ(n)(* n n))55) ; 18 bytes

```
> 5 votes

# Answer
In **Racket**, `require` forms can have multiple arguments.

```
(require net/url net/uri-codec)

```

Is way shorter than

```
(require net/url)(require net/uri-codec)

```

I don't know much about **Scheme**, but it doesn't seem to have a `require` builtin.
> 5 votes

# Answer
# Omit needless spaces

This can be considered a "trivial" tip, but it has to be pointed out somewhere.

Any time you read Racket code written by *normal* people (e.g. in the Racket documentation) it will have all the spaces put in: for example,

```
(append (list 1 2) (list 3 4) (list 5 6) (list 7 8))

```

In fact, since `(` and `)` can't be part of variable names, we can delete all the spaces around them and not lose any ambiguity (and, more importantly, still get valid code). So the above expression can instead be:

```
(append(list 1 2)(list 3 4)(list 5 6)(list 7 8))

```
> 4 votes

# Answer
The following tips are for **Racket**:

### Default arguments

Especially useful for creating aliases for long function names that are used often.

Assume the golf allows you to write a function that consumes the argument, and assume you need to use `reverse` a lot. You'll start with something like:

```
(λ(x) ... reverse ... reverse ... reverse ...

```

You can instead take in an additional argument, with a shorter name than `reverse`, and set its default value to `reverse`:

```
(λ(x[r reverse]) ... r ... r ... r ...

```

Furthermore, it's useful if you have a helper function that you use in many places with some of the same arguments. Remember to reorder the arguments to the function as needed, so you can use as many default arguments as possible, and remove the arguments from multiple callsites.

### `match`

This one is a little harder to summarize in a small post, so read up on the Racket Docs for this one. In a nutshell, `match` allows you extract elements and sequences of elements in a certain order from a list, and the quasiquote syntax lets you stitch the mutilated list back together:

```
(match (range 10)
 [`(,xs ... 3 ,ys ... 6 ,zs ...)
  `(,@(map f xs) 3 ,@(map f ys) 6 ,@(map f sz))]
 ...

```

It also gives you an easy way to work with regular expressions and do additional computation on the resulting groups afterwards,

### Named `let`

See the named `let *proc-id* ...` syntax here.

This allows you to write recursive functions that are called immediately without `define` or actually calling the function after you've defined it.

Something like:

```
(define (fib i)
  (if (< i 2) i
      (+ (fib (- i 1)) (fib (- i 2)))))
(fib 10)

```

can be shortened to:

```
(let fib {[i 10]}
  (if (< i 2) i
      (+ (fib (- i 1)) (fib (- i 2)))))

```

This last one is silly, but I haven't been able to use this little trick anywhere so far:
`(apply map list matrix)` takes a transpose of `matrix`, where `matrix` is some rectangular list of lists, like `'((1 2 3) (a b c))`.
Let me know if this does prove to be useful.
> 4 votes

# Answer
As Winny pointed out, `#!` can usually be used instead of `#lang`, saving four bytes.

```
#lang racket ;12 bytes
#!racket ;8 bytes

```
> 1 votes

---
Tags: code-golf, tips, lisp
---


title: Sum integers in a string

text:
# Question
Title: Sum integers in a string
# **Input**

A string.

### **Output**

The sum of all integers in the line.

### **Constraints**

1≤Length of line≤500

### **Sample test Case**

**Input**

```
the 5is 108 seCONd4 a

```

**Output**

```
117

```

**Explanation**

Sum is: 5+108+4=117

# Answer
# 05AB1E (legacy), 5 bytes

```
.œþOà

```

Try it online or verify a few more test cases. (Times out for the larger test cases due to the  builtin.)

# 05AB1E, ~~11~~ 6 bytes

```
þмS¡þO

```

Try it online or verify a few more test cases.

**Explanation:**

```
.œ      # Get all partitions of the (implicit) input-string,
        # which are all possible ways of dividing the input-strings into substrings
  þ     # Only leave the items consisting of digits for each partition
        # (in the new version of 05AB1E, an explicit `€` is required)
   O    # Sum each inner list
    à   # Pop and push its maximum
        # (after which the result is output implicitly)

þм      # Only leave the non-digits of the (implicit) input-string
        #  i.e. "the 5is 108 seCONd4 a" → "the is  seCONd a"
  S     # Split it into a list of characters
        #  → ["t","h","e"," ","i","s"," "," ","s","e","C","O","N","d"," ","a"]
   ¡    # Split the (implicit) input-string by each of these characters
        #  → ["","","","","5","","","108","","","","","","","4","",""]
    þ   # Remove the empty strings by only leaving the digits
        #  → ["5","108","4"]
     O  # And sum these numbers (which is output implicitly)
        #  → 117

```
> 5 votes

# Answer
# Javascript, ~~34~~ 32 bytes

`s=>eval(s.match(/\d+/g).join`+`)`

Match all digits and join them by a `+` turning it into 5+108+4, eval the result.
Only works on positive integers.

Saved 2 bytes thanks to Arnauld

```
f=
    s=>eval(s.match(/\d+/g).join`+`)

g=()=>b.innerHTML = f(a.value)
g()
```

```
<input id=a value="the 5is 108 seCONd4 a" onkeyup="g()">
<pre id=b>
```
> 4 votes

# Answer
# Perl 6, 14 bytes

```
{sum m:g/\d+/}

```

Try it online!

Anonymous code block that returns the sum of all series of digits
> 4 votes

# Answer
# , 64 48 45 bytes

After seeing the PowerShell entry I was able to golf this further.

```
function(s)eval(parse(,,gsub('\\D+','+0',s)))

```

Try it online!
> 4 votes

# Answer
# Retina 0.8.2, 8 bytes

```
\d+
$*
1

```

Try it online!

* The first line matches all numbers
* The second line replaces these by 1s, repeated said number of times
* The last line is a match, and counts the total number of 1s in the string
> 3 votes

# Answer
# APL (Dyalog Unicode), 11 bytes

Anonymous tacit prefic function

```
+/#⍎¨∊∘⎕D⊆⊢

```

Try it online!

the argument

partitioned (runs of True become pieces, run of False are separators) by

membership
of
`⎕D` the set of digits

`#⍎¨` evaluate each in the root namespace

`+/` sum
> 3 votes

# Answer
# Bash, 43 bytes

```
for n in ${1//[!0-9]/ };{((s+=n));};echo $s

```

Replaces every non-number with a space, and then sums them together.

-5 bytes thanks to GammaFunction
> 3 votes

# Answer
# Zsh, 21 bytes

```
<<<$[${1//[^0-9]/+0}]

```

Try it online!

```
  ${1           }  # the 5is 108 seCONd4 a
  ${1//[^0-9]/+0}  # +0+0+0+05+0+0+0108+0+0+0+0+0+0+04+0+0
$[${1//[^0-9]/+0}] # 117

```

Unfortunately, bash complains because it interprets `0108` as octal. Zsh does not (unless `setopt octalzeroes`)
> 3 votes

# Answer
# PowerShell, 29 bytes

```
($args-replace'\D+','+0')|iex

```

Try it online!
> 2 votes

# Answer
# Charcoal, 5 bytes

```
ＩΣ⁺ψＳ

```

Try it online! Link is to verbose version of code. Explanation: Charcoal's `Sum` operator automatically extracts numbers from a string, however if the string contains no non-digit characters then instead it takes the digital sum, so I concatenate a null byte to avoid this. The result is then cast back to string for implicit output.
> 2 votes

# Answer
# Haskell, 50 bytes

```
sum.map read.words.map f
f x|'/'<x,x<':'=x
f _=' '

```

Try it online!

There's probably a better way, but this is the most obvious one.
> 2 votes

# Answer
## Ruby, ~~32~~ 27 characters

```
->s{eval s.scan(/\d+/)*?+}

```

### Acknowledgments
> 1 votes

# Answer
# Java 10, 66 bytes

This is a lambda from `String` to `int`.

```
s->{var r=0;for(var n:s.split("\\D"))r+=new Long("0"+n);return r;}

```

Negative integers aren't supported. Presumably that's okay.

Try It Online

## Acknowledgments
> 1 votes

# Answer
# Python 3, ~~63~~ ~~59~~ 56 bytes

Why not. Obligatory regex answer. ~~Could probably dock off 6 by using Python 2, but whatever.~~ Doesn't apply anymore since I'm using an eval approach instead of using map.

```
import re;x=lambda y:eval('+'.join(re.findall('\d+',y)))

```

Explanation:

```
import re; # Import regex module
x=lambda y: eval(                                 ) # Run as Python code
                  '+'.join(                     ) # Joined by '+'
                            re.findall('\d+',y) # A list of all matches of regex \d+ in string y

```

Try it online!
> 1 votes

# Answer
# Cubix, 17 bytes

```
?|i.I!/s+q;;>p.O@

```

Try it online!

```
    ? |
    i .
I ! / s + q ; ;
> p . O @ . . .
    . .
    . .

```

Watch it run

A fairly simple one. `I` in cubix will take the first integer in the input and push it to the stack. This has the effect of skipping all the characters. The rest of it is dealing with the additional and detecting the end of the input.

* `I!` Input an integer and test it for 0
* `s+q;;` If not zero, swap TOS (forces and initial 0) and add. Push result to the bottom of stack and clean out the top. Return to beginning.
* `/i?` If zero, redirect and do a character input to check
* `|?;/` If positive (character) turn right into a reflect, this then pushes it back through the checker `?` and turns right onto the pop from stack, leaving 0 on TOS. The IP then gets redirected back into the main loop.
* `I>p.O@` if negative (end of input) turn left, do integer input, bring the bottom of stack to top, output and halt.
> 1 votes

# Answer
# PHP, ~~40~~ 39 bytes

```
<?=array_sum(preg_split('(\D)',$argn));

```

Try it online!

Run with `php -nF` input is from STDIN. Example:

```
$ echo the 5is 108 seCONd4 a | php -nF sumint.php
117

```
> 1 votes

# Answer
# Haskell, 43 bytes

```
f s|[(n,r)]<-reads s=n+f r|h:t<-s=f t|1>0=0

```

Try it online!

Makes use of `reads`.
> 1 votes

# Answer
# Ahead, 13 bytes

This works because `I` simply scans the input stream for the next token that looks like a number, ignoring anything else.

```
~Ilj~#
 >K+O@

```

Try it online!
> 1 votes

# Answer
# QuadR, 9 bytes

```
+/⍎⍵
\D

```

Try it online!

`+/` sum of

evaluation as APL of

the result of

`\D` replacing each non-digit with

a space
> 0 votes

# Answer
# Japt `-x`, 5 bytes

```
f/\d+

```

Try it online!
> 0 votes

# Answer
# Attache, 23 bytes

```
Sum##N=>MatchAll&"\\d+"

```

Try it online!

A more interesting, but indirect, answer (37 bytes): `{Sum!Reap[ReplaceF[_,/"\\d+",Sow@N]]}`

## Explanation

```
Sum##N=>MatchAll&"\\d+"

```

This has the form:

```
f##g=>h&x

```

which, when expanded and parenthesized, becomes:

```
f ## (g => (h&x))

```

`##` composes two functions together, `=>` creates a function mapping the left function over the result of the right function, and `&` binds an argument to a side of a function. For input `_`, this is equivalent to:

```
{ f[Map[g, h[_, x]]] }

```

First, then, we `MatchAll` runs of digit characters (`\\d+`). After, we convert each run to an actual integer using the `N` function. Finally, we take the sum of these numbers using `Sum`.
> 0 votes

# Answer
# APL(NARS), chars 13, bytes 26

```
{+/⍎¨⍵⊂⍨⍵∊⎕D}

```

test:

```
  f←{+/⍎¨⍵⊂⍨⍵∊⎕D}
  f 'the 5is 108 seCONd4 a'
117

```
> 0 votes

# Answer
# Java 8, ~~53~~ 130 bytes

105 bytes + 25 bytes for regex import

```
s->{long c=0;for(Matcher m=Pattern.compile("\\d+").matcher(s);m.find();c+=new Long(m.group()));return c;}

```

Try it online!
**Explanation**

```
s->{                                                    // Lambda function
    long c=0;                                           // Sum is zero
    for(Matcher m=Pattern.compile("\\d+").matcher(s);   // Prepare regex matcher
        m.find();                                       // While the string contains unused matches...
        c+=new Long(m.group()));                        // Add those matches to the output
    return c;                                           // Return the output
   }

```
> 0 votes

# Answer
# C# (Visual C# Interactive Compiler), ~~117~~ 111 bytes

```
a=>System.Text.RegularExpressions.Regex.Replace(a,@"\D+"," ").Split(' ').Select(x=>x==""?0:int.Parse(x)).Sum();

```

Try it online.
> 0 votes

# Answer
# Perl 5 `-p`, 17 bytes

```
s/\d+/$\+=$&/eg}{

```

Try it online!
> 0 votes

# Answer
# Japt v2.0a0 `-x`, 3 bytes

Another test drive for my (very-WIP) interpreter.

```
q\D

```

Try it

```
q\D     :Implicit input of string
q       :Split on
 \D     :  Non-digit characters (/[^0-9]/)
        :Implicitly reduce by addition and output

```
> 0 votes

# Answer
# Java (JDK), ~~98~~ ~~94~~ 93 bytes

```
s->java.util.Arrays.stream(s.split("\\D")).filter(t->!t.isEmpty()).mapToLong(Long::new).sum()

```

Try it online!

`-4 bytes` by using `Long::new` instead of `Long::valueOf`.
`-1 byte` by shortening the regex - if we're already removing empty strings later, making some extras when splitting is fine.

# Explained

```
s->                            // Lambda (target type is ToLongFunction<String>)
    java.util.Arrays.stream(   // Stream the result of
        s.split("\\D")        // splitting on non-digits
    )
    .filter(t->!t.isEmpty())   // Discard any empty strings
    .mapToLong(Long::new)      // Convert to long
    .sum()                     // Add up the stream's values.

```
> 0 votes

# Answer
# SNOBOL4 (CSNOBOL4), 81 bytes

```
	S =INPUT
D	S SPAN('0123456789') . N REM . S	:F(O)
	O =O + N	:(D)
O	OUTPUT =O
END

```

Try it online!
> 0 votes

# Answer
**Swift, 109 bytes**

```
func s(a:String){var d=0,t=0;a.forEach{(c) in if let e=Int(String(c)){d=d*10+e}else{t+=d;d=0}};t+=d;print(t)}

```

Try it online!
> 0 votes

# Answer
# Pip, 6 bytes

```
$+a@XI

```

Treats `-123` as a negative integer. Try it online!

```
  a     Command-line input
   @XI  Regex find all integers (XI is a variable predefined as the regex `-?\d+`)
$+      Fold on +

```

---

If hyphens should be ignored rather than treated as minus signs, then the following works for **7 bytes**:

```
$+a@+XD

```

`XD` is a preset variable for ``\d``; `+XD` adds the regex `+` modifier to it, making it match 1 or more digits.
> 0 votes

# Answer
# LiveScript, ~~38~~ 33 bytes

```
(.match(/\d+/g)reduce ->+&0+ +&1)

```

Explanation:

```
(.match(/\d+/g)reduce ->+&0+ +&1)
(.match                         ) # BIOP, implicit function clause
       (/\d+/g)                   # The regex
               reduce             # After a `)`, the `.` is implicit
                      ->          # Pass a function
                        +&0+ +&1  # & refers to `arguments`, &0 is `arguments[0]` etc.
                                  # `++` is the concat operator hence the space

```

# LiveScript with `eval`, 27 bytes

```
->eval it.match(/\d+/g)*'+' # A function using the implicit argument `it` and `ary*str`
eval . (.match(/\d+/g)*'+') # Same, but using function composition

```
> 0 votes

---
Tags: code-golf, string, number, integer, parsing
---


title: Calculating total slots

text:
# Question
Title: Calculating total slots
Given a list of jobs, which must be done in order, with each taking a slot to do, how long will it take to perform them all if after doing a job the same job cannot be done for the next two slots (cooling off slots)? However, a different job can be assigned in this cooling off slots.

**For example,**

```
[9,10,9,8] => output: 5

```

Because jobs will be allocated as `[9 10 _ 9 8]`.
1. First, 9 needs two cooling off spots _ \_. So we start with `9 _ _`.
2. Next job 10 is different from the previous job 9, so we can allocate one of _ \_. Then we will have `9 10 _`.
3. Third, 9 cannot be allocated now, since first job 9 is the same job and it needs cooling off time. `9 10 _ 9`.
4. Last, 8 is not same as any other previous two jobs, so it can be allocated right after 9 and since this is last job, it does not need cooling off time. Final list is `9 10 _ 9 8` and expected output is 5, which is the number of spots (or number of slots)

**Test cases:**

```
[1,2,3,4,5,6,7,8,9,10] => output : 10 ([1 2 3 4 5 6 7 8 9 10])
[1,1,1] => output: 7 ([1 _ _ 1 _ _ 1])
[3,4,4,3] => output: 6 ([3 4 _ _ 4 3])
[3,4,5,3] => output: 4 ([3 4 5 3])
[3,4,3,4] => output : 5 ([3 4 _ 3 4])
[3,3,4,4] => output : 8 ([3 _ _ 3 4 _ _ 4])
[3,3,4,3] => output : 7 ([3 _ _ 3 4 _ 3])
[3,2,1,3,-4] => output : 5 ([3 2 1 3 -4])
[] => output : 0 ([])
[-1,-1] => output : 4 ([-1 _ _ -1])

```

Input value can be any integer (negative, 0, positive). Length of job-list is 0 \<= length \<= 1,000,000.
Output will be an integer, the total number of slots, which is indicated in test case as output. The list inside the parenthesis is how the output would be generated.

**Winning criterion**

# Answer
> 2 votes
# Jelly, 14 bytes

```
ṫ-i⁹⁶ẋ⁸;;µƒ⁶L’

```

Try it online!

# Answer
> 5 votes
# 05AB1E, 22 bytes

```
v¯R¬yQiõˆ}2£yåiˆ}yˆ}¯g

```

Try it online or verify all test cases.

**Explanation:**

```
v           # Loop over the integers `y` of the (implicit) input-list:
 ¯R         #  Push the global_array, and reverse it
   ¬        #  Get the first item (without popping the reversed global_array itself)
    yQi  }  #  If it's equal to the integer `y`:
       õˆ   #   Add an empty string to the global_array
   2£       #  Then only leave the first 2 items of the reversed global_array
     yåi }  #  If the integer `y` is in these first 2 items:
        ˆ   #   Add the (implicit) input-list to the global_array
 yˆ         #  And push the integer `y` itself to the global_array
}¯g         # After the loop: push the global array, and then pop and push its length
            # (which is output implicitly as result)

```

# Answer
> 3 votes
# Brachylog, 10 bytes

It's always nice to see problem where Brachylog performs best

```
⊆Is₃ᶠ≠ᵐ∧Il

```

# Explanation

```
⊆I           # Find the minimal ordered superset of the input (and store in I) where:
   s₃ᶠ       #     each substring of length 3
      ≠ᵐ     #     has only distinct numbers
        ∧Il  # and output the length of that superset

```

Try it online!

# Answer
> 2 votes
# , 123 bytes

```
`-`=nchar;x=scan(,'');while(x!=(y=gsub("([^,]+),(([^,]*,){0,1})\\1(,|$)","\\1,\\2,\\1\\4",x)))x=y;-gsub("[^,]","",y)+(-y>1)

```

Try it online - single program!

Try it online - multiple examples!

A full program that reads a comma-separated list of integers as the input, and outputs the slots needed. I’m sure this could be golfed some more, and implementing this regex-based solution in some other languages would be more efficient in bytes.

Note on the second TIO I’ve wrapped it in a function to permit multiple examples to be shown. This function also shows the final list, but this is not output my the main program if run in isolation.

# Answer
> 2 votes
# Charcoal, ~~27~~ 23 bytes

```
Ｆθ«Ｗ№✂υ±²¦¦¦ι⊞υω⊞υι»ＩＬυ

```

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

```
Ｆθ«

```

Loop over the jobs.

```
Ｗ№✂υ±²¦¦¦ι⊞υω

```

Add cooling off spots while the job is one of the last two in the result.

```
⊞υι»

```

Add the current job to the result.

```
ＩＬυ

```

Print the number of spots.

# Answer
> 2 votes
# , ~~81~~ 70 bytes

```
sum(l<-rle(s<-scan())$l*3-3,1-l%/%6,((r=rle(diff(s,2)))$l+1)%/%2*!r$v)

```

Try it online!

After several unsuccessful attempts, the code turned rather ugly and not so short, but at least it works now...

First, we evaluate the lengths of consecutive runs of the same job. E.g. for `3, 3, 4, 3` this gives:

```
Run Length Encoding
  lengths: int [1:3] 2 1 1
  values : num [1:3] 3 4 3

```

Each of these runs produces `(len - 1) * 3 + 1` steps (`+ 1` is handled separately).

Next, we process occurrences of the same job 2 places apart, like: `x, y, x`, by using `diff(s, lag=2)`. The resulting vector is also chunked into consecutive runs (`r`) by `rle` function. Now, because of various interleaved alternations we need to add `ceiling(r$len/2)` steps for all runs of zeroes. E.g.:

`x y x` (length 1) and `x y x y` (length 2) both need 1 extra step: `x y _ x (y)`

`x y x y x` (length 3) and `x y x y x y` (length 4) both need 2 extra steps: `x y _ x y _ x (y)`

Finally, we need to compensate for occurrences of these alternations in the middle of a long run of the same job: `x, x, x, x...`, hence `1-l%/%6` instead of simply `1`.

# Answer
> 2 votes
# TSQL query, 158 bytes

Input data as a table.

The query is recursive so

> OPTION(MAXRECURSION 0)

is necessary, because the list of numbers can exceed 100 although it can only go handle 32,767 recursions - is the limitation really needed in this task ?

```
DECLARE @ table(a int, r int identity(1,1))
INSERT @ VALUES(3),(3),(4),(4);

WITH k as(SELECT null b,null c,1p
UNION ALL
SELECT iif(a in(b,c),null,a),b,p+iif(a in(b,c),0,1)FROM @,k
WHERE p=r)SELECT sum(1)-1FROM k
OPTION(MAXRECURSION 0)

```

**Try it online**

# Answer
> 2 votes
# , ~~74~~ 68 bytes

```
length(Reduce(function(x,y)c(y,rep("",match(y,x[2:1],0)),x),scan()))

```

Try it online!

Constructs the work array (in reverse), then takes the length. Just a bit ~~shorter~~ longer than Kirill L.'s answer, so sometimes, the naive approach is pretty good. EDIT: shorter again! I also borrowed Kirill's test template.

*-6 bytes replacing* `max(0,which(y==x[2:1]))` *with* `match(y,x,0)`.

# Answer
> 2 votes
# Python 2, 67 bytes

```
r=[]
for x in input():
 while x in r[-2:]:r+=r,
 r+=x,
print len(r)

```

Try it online!

Implements the challenge pretty literally. Uses copies of the list itself as "blanks", since these can't equal any number.

# Answer
> 1 votes
# Perl 6, 98 bytes

```
{($!=$,|$_ Z$_ Z .[1..*+1])>>.repeated.squish(:with({$+^=[*] $! ne$^a ne$^b,$b==($!=$a)})).sum+$_}

```

Try it online!

Blergh, there's got to be a better way of doing this. I'm not 100% sure this is fully correct, though it passes all the edge cases I could think of.

Basically, this starts by grouping all the triplets of the input list, with padding to either side. For example, `[1,2,1,2]` becomes `(Any,1,2), (1,2,1), (2,1,2), (1,2,Nil)`. We get the `repeated` elements in each triplet, becoming `(), (1), (2), ()`.

It then `squish`es consecutive elements that are not the same list, but are the same size (to not squish something like `[1,1,1]`), and the first element is not equal to the element before it (because we can't merge the hours in `[1,1,2,2]`), and finally the element before hasn't also been squished (`[1,2,1,2,1,2]`). So `(1), (2)` in the above example above would be squished together.

Finally, we get the `sum` of all lengths of this list, which represent our inserted hours, and add the length of the original list.

For example:

```
(1,1,1) => (Any,1,1),(1,1,1),(1,1,Nil) => (1),(1,1),(1) => (no squishes) => 4+3 = 7
(1,2,1,2,1,2) => (Any,1,2), (1,2,1), (2,1,2), (1,2,1), (2,1,2), (1,2,Nil) => (),(1),(2),(1),(2),() => squish (1),(2) and (1),(2) => 2+6 = 8

```

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

```
f=([x,...a],p,q)=>1/x?1+f(x!=p&x!=q?a:[x,...a,x=f],x,p):0

```

Try it online!

### Commented

```
f = (             // f is a recursive function taking:
  [x,             //   x   = next job
      ...a],      //   a[] = array of remaining jobs
  p,              //   p   = previous job, initially undefined
  q               //   q   = penultimate job, initially undefined
) =>              //
  1 / x ?         // if x is defined and numeric:
    1 +           //   add 1 to the grand total
    f(            //   and do a recursive call to f:
      x != p &    //     if x is different from the previous job
      x != q ?    //     and different from the penultimate job:
        a         //       just pass the remaining jobs
      :           //     else:
        [ x,      //       pass x, which can't be assigned yet
          ...a,   //       pass the remaining jobs
          x = f   //       set x to a non-numeric value
        ],        //
      x,          //     previous job = x
      p           //     penultimate job = previous job
    )             //   end of recursive call
  :               // else:
    0             //   stop recursion

```

# Answer
> 1 votes
# Perl 5 `-pl`, ~~42~~ 40 bytes

```
$a{$_}=~s/.*/$\=$&if++$\<$&;$\+3/e}{$_=0

```

Try it online!

# Answer
> 1 votes
# C (gcc), 69 bytes

```
f(j,l)int*j;{j=l>1?(*j-*++j?j[-1]==j[l>2]?j++,l--,3:1:3)+f(j,l-1):l;}

```

Try it online!

Straightforward recursion.

```
f(j,l)int*j;{               //Jobs, (array) Length
    j=l>1                   //if l > 1, do a recursion:
        ? (*j-*++j          // check if first and second elements are equal (j++)
            ? j[-1]==       //  1st!=2nd; check if first and third are equal
                j[l>2]      //  (first and second if l==2, but we already know 1st!=2nd)
                ? j++,l--,3 //   1st==3rd (j++,l--) return 3+f(j+2,l-2)
                : 1         //   1st!=3rd (or l==2) return 1+f(j+1,l-1)
            : 3             //  1st==2nd            return 3+f(j+1,l-1)
          )+f(j,l-1)        // j and l were modified as needed
        : l;                // nothing more needed  return l
}

```

# Answer
> 1 votes
# Perl 6, 48 bytes

```
{$!=0;.map:{{$_=($!=$!+1 max$_)+3}((%){$_})};$!}

```

Try it online!

**45 bytes** if the list has at least two elements:

```
+*.reduce:{$^b,|(*xx 3-(|$^a,*,$b...$b)),|$a}

```

Try it online!

# Answer
> 1 votes
# Smalltalk, 125 bytes

```
c:=0.n:=q size.1to:n-2do:[:i|(j:=q at:i)=(k:=q at:i+1)ifTrue:[c:=c+2].j=(m:=q at:i+2)ifTrue:[c:=c+1]].k=m ifTrue:[c:=c+1].c+n

```

**Explanation**

```
c : accumulator of proximity penalty
q : input array.
n := q length
i : iteration index from 1 to: n-2 (arrays are 1-based in Smalltalk).
j := memory for element i, saves some few bytes when reused
k := similar to j but for i+1.
m := similar to k but for i+2.

```

# Answer
> 0 votes
## Batch, 184 bytes

```
@echo off
@set l=-
@set p=-
@set n=0
@for %%j in (%*)do @call:c %%j
@exit/b%n%
:c
@if %1==%l% (set l=-&set/an+=2)else if %1==%p% set l=-&set/an+=1
@set p=%l%&set l=%1&set/an+=1

```

Input is via command-line arguments and output is via exit code. Explanation:

```
@set l=-
@set p=-

```

Track the last two jobs.

```
@set n=0

```

Initialise the count.

```
@for %%j in (%*)do @call:c %%j

```

Process each job.

```
@exit/b%n%

```

Output the final count.

```
:c

```

For each job:

```
@if %1==%l% (set l=-&set/an+=2)else if %1==%p% set l=-&set/an+=1

```

If we processed the job recently, add in an appropriate number of cooling off spots. Additionally, clear the last job so that the next job only triggers cooling off if it's the same as this job.

```
@set p=%l%&set l=%1&set/an+=1

```

Update the last two jobs and allocate a spot to this job.

# Answer
> 0 votes
# Python 3, ~~79~~ 75 bytes

*-3 bytes thanks to mypetlion*
*-1 byte thanks to Sara J*

```
f=lambda a,b=[]:a and f(*[a[1:],a,a[:1]+b,[b]+b][a[0]in b[:2]::2])or len(b)

```

Try it online!

# Answer
> 0 votes
**Swift, 114 bytes**

```
func t(a:[Int]){
var s=1
for i in 1...a.count-1{s = a[i-1]==a[i] ? s+3:i>1&&a[i-2]==a[i] ? s+2:s+1}
print("\(s)")}

```

Try it online!

# Answer
> 0 votes
# Java (JDK), 110 bytes

```
j->{int p,q;for(p=q=j.length;p-->1;q+=j[p]==j[p-1]?2:(p>1&&j[p]==j[p-2]&(p<3||j[p-1]!=j[p-3]))?1:0);return q;}

```

Try it online!

Ungolfed commented code:

```
j -> {
    int p, q = j.length; // Run all jobs
    for (p = q; p-- > 1;) { // reverse iterate
        q += j[p] == j[p - 1] ? 2 : // add 2 if prev same
        (p > 1 && j[p] == j[p - 2] & // 1 if 2prev same
        (p < 3 || j[p - 1] != j[p - 3]) // except already done
        ) ? 1 : 0; // otherwise 0
    }
    return q;
}

```

# Answer
> 0 votes
# Jelly, 20 bytes

```
ṫ-i⁹⁶x;
⁶;ç³Ṫ¤¥¥³¿L’

```

Try it online!

Although this is rather similar to @EriktheOutgolfer’s shorter answer, I wrote it without seeing his. In any case his is better!

### Explanation

Helper dyadic link, takes current list as left item and next item as right

```
ṫ-            | take the last two items in the list
  i⁹          | find the index of the new item
    ⁶x        | that many space characters
      ;       | prepend to new item

```

Main monadic link, takes list of integers as input

```
⁶             | start with a single space
 ;            | append...
  ç³Ṫ¤¥       | the helper link called with the current list
              | as left item and the next input item as right
       ¥³¿    | loop the last two as a dyad until the input is empty
          L   | take the length
           ’  | subtract one for the original space

```

# Answer
> 0 votes
# Python 2, 75 bytes

```
lambda a:len(reduce(lambda b,c:b+[c]*-~((c in b[-2:])+(c in b[-1:])),a,[]))

```

Try it online!

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

```
(a,i=0,h={})=>a.map(n=>h[n]=3+(i=h[n]>++i?h[n]:i))|i

```

Try it online!

# Answer
> 0 votes
# APL (Dyalog Classic), 22 bytes

```
≢∊(⊢,⍨⊣,# #↓⍨⍳⍨)/⍵,⊂⍬⍬

```

Try it online!

# Answer
> 0 votes
# Zsh, ~~66~~ 60 bytes

*-6 bytes from implicit `"$@"`*

```
for j
{((i=$a[(I)$j]))&&a=
a=("$a[-1]" $j)
((x+=i+1))}
<<<$x

```

Try it online! I highly recommend adding `set -x` to the start so you can follow along.

```
for j                   # Implicit "$@"
{                       # Use '{' '}' instead of 'do' 'done'
    (( i=$a[(I)$j] )) \ # (see below)
        && a=           # if the previous returned true, empty a
    a=( "$a[-1]" $j )   # set the array to its last element and the new job
    (( x += i + 1 ))    # add number of slots we advanced
}
<<<$x                   # echo back our total

```

```
((i=$a[(I)$j]))
    $a[     ]           # Array lookup
       (I)$j            # Get highest index matched by $j, or 0 if not found
  i=                    # Set to i
((           ))         # If i was set nonzero, return true

```

`a` always contains the last two jobs, so if the lookup finds a matching job in `a[2]`, we increment by three (since the job slots will be `[... 3 _ _ 3 ...]`).

If `a` is unset, the lookup will fail and the arithmetic expansion will return an error, but that only happens on the first job and isn't fatal.

We can save one more byte if we use `$[x+=i+1]` instead, and there are no commands on the users system comprised entirely of digits.

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

```
f=a=>for(var c=0,i=0;i<a.length;i++,c++)a[i-1]==a[i]?c+=2:a[i-2]==a[i]&&(c++,a[i-1]=void 0)
return c}

```

Try it online!

Unpacked code looks as follows:

```
function f(a)
{
    var c = 0;
    for (var i = 0; i < a.length; i++, c++)
    {
        if (a[i - 1] == a[i])
            c+=2;
        else if (a[i - 2] == a[i])
            c++,a[i-1]=undefined;
    }

    return c;
}

```

My first ever code-golf attempt, can probably be optimized a lot by shrinking the array and passing it recursively.

# Answer
> 0 votes
# K (ngn/k), 27 bytes

```
{#2_``{y,#[0|2-x?y;`],x}/x}

```

Try it online!

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


title: Eight coins for the fair king

text:
# Question
Title: Eight coins for the fair king
This is a "counterpart" of another puzzle, Eight coins for the fair king on Puzzling.SE.

You can read the above puzzle for the background. The details about this puzzle are as follows.

A set of 8 kinds of coins of different values are created, the king wants you to find out the maximum N such that any number of price from 0 to N can be paid with a combination no more than 8 coins and without charges.

For example, (taken from Glorfindel's answer). If a set of coins of values 1, 2, 5, 13, 34, 89, 233, 610 are given, your program should output 1596, because every number between 0 and 1596 (inclusive) can be represented by the sum of no more than 8 numbers from the given list (numbers may repeat), while 1597 cannot be represented in that way.

In a mathematical way, if the input is a set S consisting of 8 positive integers, the desired output N satisfies that for any number *n* between 0 and N, there exists x1, x2, x3, ..., x8 such that

$$x\_1 + x\_2 + ... + x\_8 = n \quad\textrm{and}\quad x\_1, x\_2, ...,x\_8 \in \\{0\\} \cup S$$

Your goal is to write a program, a function, or a snippet that takes 8 numbers as input, and output the maximum N as described above.

Rules:

* Flexible I/O allowed, so your program can take the input in any form that's best suitable. You may assume that the input numbers are sorted in the way that best suits your program.
    + Please state it in your answer if your program depends on input order
* Input is a set of 8 different, positive integers (no zeros). The output is one non-negative integer.
    + In case there's no 1 in the input set, your program should output 0 because any number from 0 to 0 satisfies the requirement.
    + In the case of invalid input (the set contains zero, negative or duplicate numbers), your program can do anything.
* Standard loopholes are forbidden.
* Your program should run within a few minutes on a modern computer.

Test cases (mostly taken from the answers under the linked question on Puzzling):

```
[1, 2, 3, 4, 5, 6, 7, 8] => 64
[2, 3, 4, 5, 6, 7, 8, 9] => 0
[1, 3, 4, 5, 6, 7, 8, 9] => 72
[1, 2, 5, 13, 34, 89, 233, 610] => 1596
[1, 5, 16, 51, 130, 332, 471, 1082] => 2721
[1, 6, 20, 75, 175, 474, 756, 785] => 3356

```

This is a , so the shortest program or snippet in each language wins!

# Answer
# Python 3, ~~113~~ 62 bytes

```
for i in[1]*3:x|={a+b for a in x for b in x}
while{i+1}&x:i+=1

```

Here `x` is the input as a set of ints, and `i` is the output.

Try it online!

(Thanks: Erik the Outgolfer, Mr. Xcoder, Lynn)
> 14 votes

# Answer
# Jelly, 12 bytes

```
œċⱮ8Ẏ§ṢQJƑƤS

```

Try it online!

Takes on average ~3.7 seconds to run all test cases on TIO on my phone, so surprisingly it is quite fast.

### Explanation

```
œċⱮ8Ẏ§ṢQJƑƤS     Monadic link / Full program.
  Ɱ8             Promote 8 to [1 ... 8] and for each value k:
œċ                    Generate all combinations of k elements from the list.
    Ẏ§           Tighten, then sum. Flatten to a 2D list then sum each.
      ṢQ         Sort the result and remove equal entries.
        JƑƤ      For each prefix of this list, return 1 if it is equal to its length range, 0 otherwise.
           S     Finally, sum the result (counts the 1's which is equivalent to what is being asked).

```
> 9 votes

# Answer
## Haskell, ~~56~~ 50 bytes

```
g c=[x|x<-[1..],all((/=x).sum)$mapM(0:)$c<$c]!!0-1

```

Try it online!

A brute force approach. Add `0` to the list of coins and try all combinations of 8 picks. Find the first number `n` that is not equal to the sum of any of the picks and return `n-1`.

Takes about 5m30s for `[1, 2, 5, 13, 34, 89, 233, 610]` on my 7 year old laptop hardware.

Edit: -6 bytes thanks to @Ørjan Johansen

An even shorter version (-2 bytes, again thanks to @Ørjan Johansen) is

### Haskell, 48 bytes

```
g c=[x|x<-[1..],all((/=x).sum)$mapM(:0:c)c]!!0-1

```

but it uses significantly more memory and runs into heavy paging on my machine and does not finish "within a few minutes".
> 7 votes

# Answer
# JavaScript (ES6),  ~~100 88 80~~  76 bytes

This is essentially a brute-force search, but enhanced with pruning to speed it up. The average execution time for the test cases is close to 1 second on TIO.

Assumes that the input array is sorted from highest to lowest.

```
a=>[...Array(a[0]*9)].findIndex(g=(i=8,s)=>s*i>0?a.every(x=>g(i-1,s-x)):s)-1

```

Try it online!

### Commented

```
a =>                      // a[] = input array
  [...Array(a[0] * 9)]    // create an array of 9 * max(a) entries
  .findIndex(             // find the position of the first truthy result
    g = (i = 8, s) =>     // g = recursive function taking a counter i, initialized to 8
                          //     and a sum s, initialized to the position in the above array
      s * i > 0 ?         //   if s is positive and i is not equal to 0:
        a.every(x =>      //     for each value x in a[]:
          g(i - 1, s - x) //       do a recursive call with i - 1 and s - x
        )                 //     end of every()
      :                   //   else:
        s                 //     yield s (s = 0 means success and makes findIndex go on)
  ) - 1                   // end of findIndex(); decrement the result

```
> 4 votes

# Answer
# Jelly, 9 bytes

```
Żœċ8§ḟ’$Ṃ

```

Try it online!

### How it works

```
Żœċ8§ḟ’$Ṃ  Main link. Argument: A (array)

Ż          Prepend a 0 to A.
 œċ8       Take all combinations of length 8, with repetitions.
    §      Take the sum of each combination.
       $   Combine the two links to the left into a monadic chain.
      ’      Decrement all sums.
     ḟ       Filterfalse; keep only sums that do not appear in the decremented sums.
        Ṃ  Take the minimum.

```
> 4 votes

# Answer
# Wolfram Language (Mathematica), 53 bytes

```
LengthWhile[CoefficientList[(1+Tr[x^#])^8,x],#>0&]-1&

```

Try it online!
> 4 votes

# Answer
# Python 2, 145 bytes

```
from itertools import*
x=set(map(sum,reduce(chain,map(combinations_with_replacement,[input()]*9,range(9)))))
print~-min(set(range(1,max(x)+2))-x)

```

Try it online!
> 3 votes

# Answer
# Pari/GP, 57 bytes

```
a->n=-1;while(polcoeff((1+sum(i=1,8,x^a[i]))^8,n++),);n-1

```

Try it online!
> 3 votes

# Answer
# Python 2, ~~125~~ ~~115~~ 111 bytes

```
lambda c:sum(i==j for i,j in enumerate(sorted(set(map(sum,product([0]+c,repeat=8))))))-1
from itertools import*

```

Try it online!

Expects a list of integers as input.

Explanation:

```
# an anonymous function
lambda c:
                                                          # get all length-8 combinations of values, from (0,0,0,0,0,0,0,0) to (8,8,8,8,8,8,8,8)
                                                          # zero is added to ensure that combinations of fewer than 8 coins are represented Ex:(1,0,0,0,0,0,0,0)
                                                          product([0]+c,repeat=8)
                                                  # for each combination, sum the values
                                                  map(sum,.......................)
                                       # get unique values, then sort them smallest to largest
                                       sorted(set(................................))
             # for each index, value pair, return if the index is equal to the value
             i==j for i,j in enumerate(.............................................)
         # in Python arithmetic, False is 0 and True is 1. So, count how many items match their index.
         # Since zero was added to the list, there will always be one extra match (0==0). So offset by one.
         sum(........................................................................)-1
from itertools import*

```
> 2 votes

# Answer
# Perl6, 65 63 41 bytes (39 37 chars)

```
{@_=(0,|@_)X+(0,|@_)for ^3;($_ if $_==$++for @_.sort.unique)-1}

```

Try it online!

This is an anonymous block that gets passed its data as an array. The `(0,|@_)` is a quick way to add a `0` to `@_`, and even though it's done twice, it's still a bit shorter than `@_.push: 0;` which would then need spaces after the `_`. This is a brute force approach that cheeses a bit on the fact that it's 8 combinations. After cross adding, an anonymous list is created for sequential values. With math operators, lists evaluate to their length, so the -1 pulls double duty: accounting for the 0 and coercing to Int.

This can take its sweet time, but by changing one or both `(0,|@_)` to `(0,|@_.unique)` before the first `for` it can be sped up considerably. That adds **+7** (runtime \<60s) or **+14** (runtime \<10s) to the score if you feel the first is too slow (I did this for the linked code to avoid timeouts after 60 seconds).

**Edit:** JoKing in the comments improved it (same idea, cross add, then return the last consecutive result) to an astonishing 39 chars (41 bytes):

```
{(@_=@_ X+0,|@_)xx 3;first *+1∉@_,^∞}

```

Try it online!

The final tabulation doesn't need a 0, saving a few bytes by only needing to add 0 in once. The `xx 3` mimics the for loop (still cheeses on the coins being a power of 2). The `first` sub returns the first number in the infinite list `0..*` (`^Inf` is possible too, but doesn't save space) whose `+1` is not a member of the cross added list. Like mine, it's slow, so add **+7** for a `unique` after the first equals if you feel it's too slow for guidelines.
> 2 votes

# Answer
# JavaScript (Node.js), ~~171~~ ~~145~~ 115 bytes

```
f=(s,n=3)=>n?f(s=new Set(a=[0,...s]),n-1,a.map(m=>a.map(n=>s.add(m+n)))):Math.min(...[...s].filter(m=>!s.has(m+1)))

```

Try it online! Port of @Mark's Python 3 answer. 108 bytes in Firefox 30-57:

```
f=(s,n=3)=>n?f(new Set((for(n of s=[0,...s])for(m of s)n+m)),n-1):Math.min(...[...s].filter(m=>!s.has(m+1)))

```
> 1 votes

# Answer
# Wolfram Language (Mathematica), 46 bytes

```
0//.x_/;Min[Tr/@FrobeniusSolve[#,x+1]]<9:>x+1&

```

Try it online!

Brute force approach: checks integers counting upward until it reaches a value that can't be paid for in 8 coins. Very, very slow (tio times out), but I'm fairly sure the condition is correct.
> 1 votes

# Answer
# Clean, 161 bytes

```
import StdEnv,Data.List
$l=:[1:_]#k=sort(nub(map sum(iter 8(concatMap(\[h:t]=[[e,h:t]\\e<-[0:l]|e>=h]))[[0]])))
=length(takeWhile((>=)1)(zipWith(-)(tl k)k))
$_=0

```

Try it online!
> 0 votes

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