No jogo de tabuleiro The Settlers of Catan , existem cinco tipos de recursos: Brick, Log, Ore, Wheat e Sheep. Construir um assentamento custa um tijolo, um tronco, um trigo e uma ovelha. No entanto, você também pode trocar quatro recursos idênticos para obter um recurso de um tipo diferente. Por exemplo, se você tivesse quatro minérios na mão, poderia trocá-los e obter uma ovelha.
Seu trabalho é determinar se posso ou não construir um acordo, dada a minha mão.
Sua tarefa
Entrada será uma seqüência de letras B
, L
, O
, W
, e S
, tomado em qualquer formato razoável. Essas letras correspondem aos cinco tipos de recursos fornecidos acima. Você deve saber se tenho ou não os recursos necessários para construir um acordo, levando em consideração a possibilidade de negociar quatro do mesmo tipo.
Isso é código-golfe , então o código mais curto em bytes vence.
Notas
- Você não precisa exibir quais negociações eu preciso realizar ou quantos acordos eu poderia construir. Um simples "sim" ou "não" serve.
- Você não pode assumir que a entrada está em qualquer ordem específica. Em particular, você não pode supor que os recursos do mesmo tipo estejam agrupados, assim
OBLSO
como uma entrada válida. - Esse é um problema de decisão ; portanto, você pode usar qualquer valor que queira que signifique "sim" e "não", desde que os dois valores escolhidos sejam distintos e consistentes.
- As únicas regras com as quais estamos preocupados aqui são as listadas acima. Regras mais complicadas de Colonos de Catan, como negociar com outros jogadores ou em portos, não são relevantes aqui.
- Os caracteres de entrada (
B
,L
,O
,W
,S
) pode ser substituído por outros valores se é mais fácil para o seu idioma específico de escolha, desde que há cinco entradas distintas. Se você usar outros valores de entrada, especifique-os na sua resposta.
Exemplos
BLWS -> Yes
OOOOWLB -> Yes (trade four O for a S)
OOW -> No
BBBO -> No
(empty input) -> No
BBBBLW -> No
BBBBBLW -> Yes (trade four B for a S)
OOOOOOOOOOOOOOOO -> Yes (sixteen O; trade for B, L, W, S)
BLBLBLBLBL -> Yes (trade L for W and B for S)
BLSWBLSWBLSW -> Yes (extra, unused resources are ignored)
fonte
Respostas:
Python 2 , 54 bytes
Experimente online!
Para cada um de nossos recursos, contamos o número de "liberdades" dadas por ter n desse recurso. A liberdade representa uma oportunidade de preencher um dos espaços de tijolo-log-trigo-ovelha que precisamos preencher para resolver, respondendo pelo fato de que podemos converter nossos recursos.
Para todo o BLSW, ter um dos recursos nos dá uma liberdade, e todo excesso adicional de 4 nos dá outro. A regra da contagem da liberdade é assim:
Então n tijolos / toras / trigo / ovelha dão ⌊ (n + 3) / 4⌋ liberdades.
Para os minérios, apenas o excesso de quartetos conta. A regra da contagem da liberdade é assim:
Então n minérios dar ⌊n / 4⌋ liberdades.
Teorema: podemos resolver se, e somente se, tivermos ≥ 4 dessas "liberdades".
Então, contamos nossas liberdades e verificamos se existem ≥ 4 delas. Para lidar com a contagem de minérios como ⌊n / 4⌋ mas outros recursos ⌊ (n + 3) / 4⌋, aumentamos artificialmente as contagens dos outros recursos em 3 e depois contamos ⌊n / 4⌋ para todos eles. Fazemos isso mapeando em
(s+"BLSW"*3).count
vez des.count
.Prova :
Suponha que possamos resolver. Então, para cada um de [B, L, S, W], (a) usamos 1 desse recurso que já possuíamos ou (b) sacrificamos 4 de algum outro recurso (incluindo minérios) para criá-lo. Nos dois casos, contamos pelo menos 1 liberdade pelas regras acima. Portanto, temos ≥ 4 liberdades.
Suponha que tenhamos 4 liberdades, k das quais são devidas a "excessos" (toda liberdade de minérios é um excesso, e toda liberdade de outros recursos além do primeiro também é) e 4-k são testemunhas de possuir pelo menos uma brick / log / wheat / sheep (aquele que deu a "primeira liberdade"). Em seguida, preenchemos 4-k slots com o tijolo / log / trigo / ovelha que nos deu nossa primeira liberdade e preenchemos os k slots restantes, convertendo nossos excessos. Todos os 4 slots estão preenchidos e podemos resolver. Obviamente, ainda podemos fazer isso se tivermos mais de quatro liberdades.
Essa prova é péssima, mas estou com sono. Tenho certeza de que há uma explicação melhor.
fonte
s
éOOOOBLW
, você acaba ficandosum(n/4for n in map(("OOOOBLWBBBLLLSSSWWW").count,"BLSWO"))>3
... por isso para cada um deBLOWS
você contar quantas vezes ele aparece no essa seqüência inicial de"BLWS"*3
, em seguida, resumir."OOOOBLWBLSWBLSWBLSW"
, na verdade, mas as contagens são os mesmos, é claro.)in"BLSWO"
é desnecessário em Python, não é? Parece funcionar na TIO, pelo menos ..Python 2 ,
5251 bytes-1 byte graças a Luke (substitua
>=0
por<0
, invertendo osFalse
/True
resultados)Uma função sem nome, utilizando uma sequência de caracteres B , O , W , L e S (como no OP) e retornando
False
se você puder resolver ouTrue
não.Experimente online! (coage a saída para o
yes/no
do OP).Quão?
Esta é uma porta da minha resposta Jelly. Precisamos compensar qualquer B , W , L ou S ausente do restante depois de usar um de cada um deles. Como tal, podemos adicionar um O extra à nossa mão, reduzir todas as contagens em um, depois dividir todas as contagens por quatro e depois somar - se o resultado for zero ou mais, podemos resolver (ou porque não havia recursos necessários ausentes) ou porque podemos negociar para adquirir o (s) desaparecido (s)).
fonte
False
para'yes'
eTrue
para'no'
? Então você pode mudar>=
para<
, economizando 1 byte.Pitão , 14 bytes
Experimente aqui! ou Verifique todos os casos de teste.
Pitão ,
31 27 1716 bytesVerifique os casos de teste.
Como isso funciona?
Explicação nº 1
Explicação nº 2
Estes são os códigos usados pelo meu programa:
fonte
+%ld4/ld4
->s.Dld4
//Q4 4
pode ser/Q16
, mas eu realmente não estou certo ...BBBO
, por exemplo4
e dividir por4
.Geléia ,
1312 bytesUm link monádico que aceita uma lista de números representando os recursos que você possui e que retorna
1
se puder se estabelecer ou0
não.Os recursos são
1, 2, 3, 4, 5
onde5
representa Ore .Experimente online! ou consulte a suíte de testes (usando o OP IO).
Quão?
A idéia é primeiro contar os recursos por tipo e, em seguida, reduzir todas as contagens de B , L , W e S em um - se não contarmos nenhum desses quatro, agora eles terão entradas de -1 - precisamos adquirir eles de nossos recursos restantes (na verdade, isso é obtido adicionando O (
5
) extra e reduzindo todas as cinco contagens em 1 ). Em seguida, dividimos por inteiro todos esses valores por quatro para ver quantas unidades podemos negociar com cada uma de nossas contagens restantes por tipo de recurso, sem afetar as contagens -1 e 0 (observe que -1 dividido por inteiro por quatro é-1 , não 0 ). Por fim, somamos os valores e verificamos se o resultado é maior ou igual a zero (aqui, maior que -1 pode ser usado, pois sempre temos números inteiros).fonte
Java 8, 101 bytes
Lambda de
int[]
atéboolean
. Atribuir aFunction<int[], Boolean>
.Experimente Online
Entrada e saída
A entrada é uma matriz de números inteiros de 0 a 4, inclusive. 4 representa o minério e os outros mapeamentos são imateriais. Meus casos de teste são traduções diretas daqueles em questão, com 0 como Brick, 1 como Log, 2 como Wheat e 3 como Sheep.
A saída é se um assentamento pode ser construído.
Ungolfed
Explicação
h
é o número de quádruplos de recursos disponíveis para negociação. Nós iteramos sobre cada tipo de recurso (exceto Ore), aumentandoh
para cada quádruplo de recursos extras que temos e diminuindo onde nenhum recurso está presente. Então nosso resultado é seh
não é negativo.A linha
ajusta
h
adequadamente, independentemente de não haver recursos (escassez) ou de pelo menos um recurso (excedente).f[i]
é decrementado para contabilizar o recurso necessário no caso de superávit, produzindo -1 no caso de falta. O deslocamento à direita assinado reduz a expressão para 0 (caso excedente) ou -1 (caso excedente), de modo que um OR bit a bit com o númerof[i++] / 4
de quádruplos excedentes (no caso excedente) não tem efeito no caso escassez, mas resulta no número próprio caso excedente.Agradecimentos
fonte
...for(h=f[4]/4;i<4;h+=f[i++]/4)n+=--f[i]>>-1;return~h<n;
.a->{int h,f[]=new int[5],i=0;for(int x:a)f[x]++;for(h=f[4]/4;i<4;h+=f[i++]/4)h+=--f[i]>>-1;return~h<0;}
a->{int h,f[]=new int[5],i=0;for(int x:a)f[x]++;for(h=f[4]/4;i<4;)h+=--f[i]>>-1|f[i++]/4;return~h<0;}
Retina , 34 bytes
Experimente online! Explicação: A construção de uma liquidação requer 4 recursos, que são seus primeiros B, L, W ou S ou quaisquer outros 4 recursos do mesmo tipo. Isso equivale a adicionar três de cada um desses quatro tipos de recursos e contar para ver se você tem quatro conjuntos de quatro.
fonte
Gelatina , 23 bytes
Experimente online!
Consulte a seguinte tabela para obter os valores:
fonte
Retina , 43 bytes
Experimente online!
fonte
Python 3 ,
7978 bytesEdit: -1 byte graças a @ Mr.Xcoder
Experimente online!
fonte
MATL , 19 bytes
Entrada é um vetor de linha numérica em que as letras são representadas como números da seguinte maneira:
A saída é
1
para verdade,0
para falsidade.Experimente online !: verifique todos os casos de teste .
Como funciona
BLWS
) são diferentes de zero. Isso fornece um número c .Código comentado
fonte
> <> , 61 bytes
Experimente online!
Usa o seguinte mapeamento de recursos:
Realmente não importa o que o mapeamento é usado, contanto que eles estão na faixa
0-4
, e0
é usado para O. faz uso do fato de que procura a combinaçãoBLWS
é o mesmo que olhar para a combinaçãoOBLWS
enquanto já tendo umO
em mão.fonte
05AB1E , 19 bytes
0 -> Minério
1 -> Tijolo
2 -> Log
3 -> Trigo
4 -> Ovelha
Retorna 0 quando falso e 1 caso contrário.
Experimente online!
Explicação:
Solução não competitiva: 17 bytes
Houve um erro no 05AB1E quando enviei a solução pela primeira vez, em que alguns operadores lidaram mal com entradas vazias. Isso resultou nessa solução respondendo
1
a uma entrada vazia. Agora isso foi corrigido, portanto, esta solução funciona perfeitamente.A diferença aqui é que adicionamos um minério antes de remover um de cada recurso, indiscriminadamente, contando o número de recursos removidos dessa maneira. Em seguida, decrementamos o contador em 1 para obter o número correto de B, L, W e S.
Experimente online!
fonte
JavaScript (SpiderMonkey) , 116 bytes
Experimente online!
Super má resposta desajeitada. Tenho certeza de que poderia ser limpo mais. Método inspirado na resposta de Lynn neste tópico.
fonte
Kotlin ,
131129 bytesSubmissão
Teste
Não pode funcionar no TryItOnline, mas funciona no try.kotlinlang.org
fonte