Vários meses atrás, eu tive essa pergunta como um quebra-cabeça de pré-triagem para uma entrevista. Recentemente, ao pensar no material do blog, ele apareceu na minha cabeça como um bom exemplo para resolver um problema funcionalmente. Vou postar minha solução assim que terminar de escrever minha postagem no blog.

NOTA: Esta pergunta foi feita no StackOverflow há um ano e foi rebaixada após algumas respostas (incorretas). Suponho que foi prejudicada por ser uma pergunta óbvia de entrevista ou lição de casa. Nossas respostas aqui devem ter um código suficientemente profundo para que alguém não pense em usá-las!

Em uma corrida, você aposta usando a seguinte estratégia. Sempre que você perde uma aposta, você dobra o valor da aposta para a próxima rodada. Sempre que você vencer, a aposta para a próxima rodada será de um dólar. Você começa a rodada apostando um dólar.

Por exemplo, se você começar com 20 dólares e vencer a aposta na primeira rodada, perder a aposta nas próximas duas rodadas e depois vencer a aposta na quarta rodada, você terminará com 20 + 1-1-2 +4 = 22 dólares.

Espera-se que você complete a função g, que requer dois argumentos:

1. O primeiro argumento é um número inteiro, aque é o dinheiro inicial que somamos quando iniciamos as apostas.
2. O segundo argumento é uma string r. O i-ésimo caráter do resultado será 'W' (vitória) ou 'L' (derrota), indicando o resultado da i-ésima rodada.

Sua função deve retornar a quantidade de dinheiro que você terá depois que todas as rodadas forem jogadas.

Se, em algum momento, você não tiver dinheiro suficiente em sua conta para cobrir o valor da aposta, pare e devolva a soma que tiver nesse momento.

Amostra de execução

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

A função retorna 1neste caso

O vencedor é determinado pelo menor número de caracteres DENTRO da definição de função implícita. Cooperar por idioma, se desejar. Eu sei que o meu pode ser melhorado!

GolfScript, 33 caracteres

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

Exemplos ( online ):

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

Código anotado:

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

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

Chamá-lo assim: g(15,'LLLWLLLL').

Isso simplesmente percorre a cadeia, alterando o valor do dinheiro que baseamos no personagem.

Aqui está um exemplo de programa que executa testes nesta função:

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)

Saída de amostra:

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

Com uma pequena alteração no testador, podemos obter o lucro médio de muitas execuções:

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)

Saída de amostra (demorou um pouco, pois estamos chamando os 5000000tempos de função ):

-0.0156148

Edit: Obrigado a Howard e Danny por mais golfe.

EDIT: agora o programa verifica se há dinheiro suficiente para fazer a aposta. Isso realmente salva bytes.

R, 95 caracteres

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}

Recuado:

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
    }

Uso:

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

J - 63 55 char

Agora, com o bônus adicional de não estar incorreto! É exatamente exatamente como antes.

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

Toma a quantia inicial de dinheiro como argumento à esquerda e a sequência de vitórias / perdas à direita.

Explicação: O programa divide-se igualmente em algo como uma composição de duas funções, ambas detalhadas abaixo. O primeiro transforma a sequência de ganhos / perdas nos valores das apostas, com o sinal correspondente, e o segundo efetivamente descobre a resposta dada o dinheiro inicial e essa sequência de ganhos / perdas transformada.

;@('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

Observe que anexamos o dinheiro às apostas antes de receber as somas parciais, mas anexamos a aposta infinita ao final da lista de valores das apostas. É isso que muda o valor da conta em excesso da próxima aposta e o uso do infinito nos permite ter sempre o último elemento como um exemplo.

Uso:

   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

JavaScript (rascunho do ECMAScript 6) - 62 51 50 caracteres (no corpo da função)

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

Define uma função recursiva gcom dois argumentos:

• a- a quantidade atual de dinheiro que você tem; e
• r - a sequência de vitórias / derrotas.

E dois argumentos opcionais:

• t- o índice da rodada atual de apostas (inicialmente 0)
• b- a quantia em dinheiro da aposta atual (novamente inicialmente 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 caracteres (no corpo da função)

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

Explicação:

(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.

Testes

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

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

Eu defini a função g que recebe a (a quantidade de dinheiro que você tem no início) e r (que é o resultado das apostas) Inicializa o valor da primeira aposta em 1. Em seguida, para cada resultado das apostas, se for uma vitória ("W" em r), você ganha o dinheiro e a aposta volta para 1. Caso contrário, você perde o valor da aposta e o valor da próxima aposta dobra. Finalmente, ele retorna o dinheiro que você tem. Você pode usá-lo assim:

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

Eu acho que isso pode ser jogado além disso.

C, 107 caracteres

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);}

Estou usando uma função recursiva aqui, porque na maioria das vezes a implementação é mais curta. Mas não tenho muita certeza se é esse o caso aqui, porque eu precisava criar uma função adicional para o wrapper, de modo que minha função, na verdade, leva apenas 2 argumentos. O terceiro argumento na função fé necessário para a aposta atual (o acumulador).

Sem a função wrapper, essa solução teria apenas 73 caracteres, mas seria necessário passar um parâmetro adicional com o valor 1 (a aposta inicial) para obter o resultado adequado.

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);
}

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;}

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}

Amostras de execuções:

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

JSFiddle com registro

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
}

Javascript ( ES5 ) 69 64 60 bytes na função

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}

Variação: ( mesmo comprimento )

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}

Casos de teste: ( retirado da solução de plannapus )

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

Haskell, 62

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

ou com os dois argumentos nomeados (65 caracteres):

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

Observe que 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

Python 2 - 65 bytes

Agora derrotado pela melhor solução atual do Python, mas não posso compartilhar:

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

Como algumas outras soluções Python, eu uso os argumentos da função para declarar bfora da definição da função, mas como a função é recursiva, isso realmente serve a algum outro propósito além do golfe aqui.

Eu também precisava alterar a ordem dos argumentos da função para que a tupla descompactasse em argumentos da função funcionasse.

Caso você queira saber, r>"">a>=bé a abreviação de r and a>=b.

Ruby, 76 64 (no corpo da função) bytes

EDIT: melhorou a resposta removendo 3 bytes:

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

usando 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

usando 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}

a corrida :

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

C #, 74 caracteres dentro do método

Minha primeira tentativa neste 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;

Ou, mais legível:

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;

Bastante ingênuo, não há muitos truques ... principalmente aproveitando o char sendo ordinal e a string sendo enumerável. Salvando alguns caracteres por looping externo quando o jogador ficar sem dinheiro.

Golfscript, 51 41 36 35 bytes

Função interna

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

Isso pressupõe que começamos com uma quantia positiva de dinheiro e que a sequência de perdas e ganhos não estará vazia, para que pelo menos uma aposta possa ser realizada.

Exemplo

{
  # 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.

dá

[22 1 7 0]

Experimente online.

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;

O violino do .NET

Uma postagem no blog explicando

Java, 95 bytes (função interna)

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

Experimente online!

Ruby, 84 caracteres

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

A mesma abordagem da minha outra resposta em C, mas eu queria tentar ruby ​​para o Code-Golfing. A vantagem da versão C é que não preciso criar uma função de invólucro, posso simplesmente usar os valores padrão para parâmetros.

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

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

Eu sei que isso não é nem de longe a solução mais curta, mas eu queria demonstrar uma abordagem diferente, que itera mais sobre as perdas do que sobre as apostas individuais. int(bin(a)[3:],2)fornece o número inteiro com o bit mais significativo da representação binária de aexcluída, que é a quantidade de dinheiro que a pessoa terá depois de perder poderes crescentes de 2 até que não possa mais apostar, porque a é atualmente 1 maior que a sua quantidade real de dinheiro. Esta versão assume que o capital inicial é positivo.

C - 64 59 (Função interna)

Mais uma resposta em C. Aproveita o fato de que o valor da variável permanece na pilha. Portanto, esta falha ocorreu com alguns compiladores, mas funcionou corretamente onde quer que eu testei. Além disso, peguei o %2da tia para salvar um personagem. Desculpe!

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;
}

Lote - 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%

Exemplo -

H:\uprof>bet.bat 15 LLLWLLLL
1

Japt , 38 bytes

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

Tente

Provavelmente precisa de golfe :) Mas parece que está obtendo resultados corretos.

OBSERVAÇÃO Este é um programa completo que é trivial para se transformar em uma função anexando UV{. A contagem de bytes dentro da função será a mesma.

JS Transpilado Explicado:

// 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
 )

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

Experimente online!

Esse desafio precisa de algumas tarefas muito estranhas, o que significa que eu não poderia encadear uma grande atualização. Ele usa o fato de que 'W' é 87 em ASCII e 'L' é 76, portanto, a modificação por 2 fornece acesso a valores verdadeiros / falsos fáceis. |% t*yé o atalho padrão do toCharArray e a atualização da aposta usando a divisão acabou sendo a maneira mais barata que eu pude encontrar (divide-a pela metade em uma perda (dobrando-a) ou dividida por si mesma em uma vitória (definindo como 1) )

Além de muitos bytes, porque eu perdi a restrição. Vai trabalhar no golfe no patch

05AB1E , 19 bytes

vDX@iy'WQiX+1UëXxU-

Porto da resposta do GolfScript de @Howard , por isso não deixe de vota-lo também!

Observe que 05AB1E não possui funções, portanto, este é um programa completo.
Coloca a entrada da string primeiro e a entrada inteira em segundo (nova linha delimitada em STDIN).

Experimente online ou verifique mais alguns casos de teste .

Explicação:

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)