Coloreame un Polo

22

Digamos que tu trabajo es pintar postes, y un cliente te pide que pintes un poste con 4 secciones rojas y 3 secciones amarillas. Puedes hacerlo fácilmente de la siguiente manera:

r y r y r y r

Con solo rayas amarillas y rojas. Ahora digamos que su cliente le pide que pinte un poste con 2 secciones rojas, 2 secciones amarillas y 1 sección verde . Hay un par de maneras en que puedes pintar tu poste

g y r y r
y g r y r
y r g y r
y r y g r
y r y r g
g r y r y
r g y r y
r y g r y
r y r g y
r y r y g
y r g r y
r y g y r

Más precisamente, eso es 12 maneras de pintar el poste. Esto explota más colores y secciones involucradas

Ahora, si su cliente dice que quiere 3 secciones rojas y 1 sección amarilla, no hay forma de pintar un poste así. Porque no importa cómo intente organizar las secciones, dos secciones rojas se tocarán, y cuando dos secciones rojas se toquen, se convertirán en una sola sección roja.

Y esa es más o menos nuestra única regla para pintar postes

Las secciones adyacentes pueden no ser del mismo color.

Tarea

Dada una lista de colores y secciones requeridas, muestre la cantidad de formas posibles de pintar un poste según lo solicitado. Puede representar colores de cualquier manera razonable (enteros, caracteres, cadenas), pero nunca se le darán más de 255 colores diferentes a la vez. Si lo desea, incluso puede elegir no tener los colores asignados a los nombres y simplemente tomar una lista de recuentos de secciones si eso es más fácil.

Casos de prueba

Estos son bastante difíciles de calcular a mano, especialmente a medida que se hacen más grandes. Si alguien tiene un caso de prueba sugerido, lo agregaré.

[4,3]    -> 1
[2,2,1]  -> 12
[3,1]    -> 0
[8,3,2]  -> 0
[2,2,1,1]-> 84
Asistente de trigo
fuente
¿Podemos tomar la entrada como, por ejemplo, "rrrryyy" para [4,3]?
Leo
@Leo Claro que eso es perfectamente razonable.
Wheat Wizard
¿Puedo obtener información como [1, 1, 1, 1, 2, 2, 2]? Supongo que sí.
Erik the Outgolfer
44
No es súper importante, pero poner en mayúscula la palabra Polo hace que parezca que estás hablando de una persona de Polonia.
NH.

Respuestas:

9

Mathematica, 37 44 48 60 60 62 bytes

Tome la entrada como una lista de enteros {1, 1, 1, 2, 2}. Pruébalo en Wolfram Sandbox .

Método de coincidencia de patrones, gracias @Not a tree!

Count[Split/@Permutations@#,{{_}..}]&

Splitdivide una sola lista en sublistas de elementos consecutivos, por ejemplo, {1, 1, 2, 3, 4, 4}en{{1, 1}, {2}, {3}, {4, 4}}

{{_}..}es, a saber, {{_}, {_}, {_}, ...}. El patrón coincide con una lista de sublistas unarias.

Differences método, 48 bytes:

Tr@Abs@Clip[1##&@@@Differences/@Permutations@#]&

El código se usa Differencespara determinar si los elementos adyacentes son iguales.

Paso a paso:

  1. Permutations@# genera todas las permutaciones de la lista de entrada a una lista N! * N.
  2. Differences/@ calcula la diferencia entre N elementos y genera una lista N! * (N-1).
  3. 1##&@@@calcula la multiplicación de todas las listas. Si una lista contiene 0(dos elementos adyacentes son iguales), el resultado será 0, de lo contrario, distinto de cero, a una N! lista.
  4. Clip[]actúa como Sign[], transforma la lista de (-inf, inf) a [-1, 1]
  5. Tr@Absconvierte todo -1en 1y ahora la lista N! -length contiene solo 0(inválido) y 1(válido). Así que solo sumamos la lista.
Keyu Gan
fuente
44
Puede guardar 4 bytes con un poco de coincidencia de patrones: Permutations@#~Count~Except@{___,x_,x_,___}&.
No es un árbol
2
Tengo otro: ¡ Count[Split/@Permutations@#,{{_}..}]&37 bytes!
No es un árbol
7

Jalea , 7 bytes

Œ!QIẠ€S

Pruébalo en línea!

Toma datos como, por ejemplo, [1,1,1,1,2,2,2]para [4,3]. El caso de [8,3,2]prueba tarda demasiado en ejecutarse en TIO.

Cómo funciona

Œ!QIẠ€S - main link, input as a list
Œ!      - all permutations
  Q     - remove duplicates
   I    - take increments (returns a 0 for two adjacent identical numbers)
    Ạ€  - apply “all” atom to each: 0 for containing 0 and 1 otherwise
      S - sum
fireflame241
fuente
Abusaste del
Funciona Œ!QIẠ€S? Pruébalo en línea!
nmjcman101
@ nmjcman101 Eso parece funcionar. Buen hallazgo! Preferí el Psobre cualquier átomo por su simplicidad.
fireflame241
@ fireflame241 Técnicamente ese no es el átomo absoluto, es el átomo total.
Erik the Outgolfer
Por cierto en P€lugar de Ạ€seguiría funcionando.
Erik the Outgolfer
5

Mathematica, 50 bytes

Expand[1##&@@(LaguerreL[#,-1,x](-1)^#)]/._^i_:>i!&

¡Pruébalo en matemáticas o en el sandbox de Wolfram !

Toma datos como en los casos de prueba, por ejemplo, {4,3}significa "4 franjas rojas, 3 franjas amarillas".

Esta es una implementación ingenua de una fórmula que encontré aquí . "Ingenuo" significa "No tengo idea de cómo funcionan las matemáticas, así que por favor no me pidas una explicación ..."

No un arbol
fuente
1
¿Podemos tener una explicación de las matemáticas dadas en esta respuesta?
TheLethalCoder
@TheLethalCoder Secundado, ¿alguien puede explicarme las matemáticas?
No es un árbol
3

Ruby 2.4, 47 bytes

De entrada es una lista de caracteres: Para el caso de prueba [4,3], de entrada puede ser %w[a a a a b b b], "1111222".charso alguna otra variedad de formatear método que sea válida en Ruby.

->x{x.permutation.uniq.count{|a|a*''!~/(.)\1/}}

Requiere 2.4 para Enumerator#uniq(las versiones anteriores solo lo tenían disponible en la Arrayclase). Como tal, el enlace TIO agrega 5 bytes para convertir el enumerador de permutación a una matriz primero a través de to_a, ya que no tiene la función anterior.

Pruébalo en línea!

Tinta de valor
fuente
3

R, 72 bytes

pryr::f(sum(sapply(unique(combinat::permn(x)),pryr::f(!sum(!diff(x))))))

Crea la función

function (x) 
{
    sum(sapply(unique(combinat::permn(x)), pryr::f(!sum(!diff(x)))))
}

Toma información en el formulario [1,1,1,1,2,2,2]según el comentario de Erik the Outgolfer. Utiliza combinatla permnfunción para crear una lista de todas las permutaciones y luego uniqueobtener todas las entradas distintas. sapplyluego aplica la siguiente función en todas las entradas:

pryr::f(!sum(!diff(x)))

Que se evalúa como

function (x) 
!sum(!diff(x))

Tenga en cuenta que esto xno es lo mismo que xen la entrada de la función grande. Usar otro personaje en esta función engañaría pryr::fa creer que la gran función necesita otro argumento.

De todas formas, cuando se les da una permutación, esta función toma la diferencia entre el vector: 2 1 3 4 2 1 -> -1 2 1 -2 -1. !convierte los FALSEceros y ceros en cero TRUE, por lo que el vector se convierte FALSE FALSE FALSE FALSE FALSE. Sumando eso para verificar si hay alguna TRUEs ( TRUEimplicaría diff=0-> dos los mismos números consecutivos). Podemos invertir esto nuevamente !para obtener un valor booleano sobre si hay o no valores consecutivos en la permutación.

Sumar estos booleanos nos da el número total de permutaciones donde este no es el caso.

No funciona para el caso de [8,3,2]prueba porque requiere un vector de 46 GB para almacenar esas permutaciones.

JAD
fuente
2

Python 2 , 140 89 bytes

El formato de entrada es 'aaaabbb'para caso de prueba [4,3].

lambda s:len({p for p in permutations(s)if all(map(cmp,p,p[1:]))})
from itertools import*

Pruébalo en línea!

Felipe Nardi Batista
fuente
2

Casco , 8 bytes

#ȯ¬ṁtguP

Pruébalo en línea! Toma entrada en el formato "aaabb"para [3,2]. Tiempos de espera en el caso de prueba más largo.

Explicación

No hay nada lujoso aquí, solo cuenta las permutaciones únicas donde todos los grupos de elementos adyacentes tienen longitud 1.

#ȯ¬ṁtguP
       P  Permutations.
      u   Remove duplicates.
#ȯ        Count how many satisfy the following condition:
     g    group adjacent elements,
   ṁt     concatenate tails of groups
  ¬       and negate.
Zgarb
fuente
2

Ruby, 84 76 bytes

f=->a,x=p{i=s=0;a.map{a[i-=1]-=1;a[i]<0||i!=x&&s+=f[a,i];a[i]+=1}.max>0?s:1}

Una función lambda recursiva. Mira cada color posible y dosifica una búsqueda de árbol recursiva, contando la cantidad de veces que usa todas las rayas.

Explicación (para la versión anterior):

f=->
  a, # a is the input array in [3,3,4] form
  x = -1 # x is the last color placed (-1 when run normaly, used in recursive calls)
{
  j = i = s = 0;
  # i is the index
  # s is the sum of valid final patterns (the answer)
  # j is used to count the total stripes

  a.map{|e| # Iterate over array of colors

    a[i] -= 1; # remove a stripe of current color (the array will be used in recursive call)

    s += f[a,i] if i!=x && e>0;
      # add to sum recursively if:
        # we are not using the same color as the last color AND
        # we have stripes of the current color left to paint

    a[i] += 1; # replace the stripe we removed above 

    j += a[i]; # add stripes to j

    i+=1 # increment the index

  }; # End loop

  j == 0 ? 1 : s
  # if we had stripes, give the recursive sum, otherwise return 1 
}
MegaTom
fuente
x=pcomo la condición inicial? pactúa como un alias de nilen este caso y debe satisfacer la comprobación para la que se está utilizando.
Value Ink
1

MATL , 11 8 bytes

Y@Xu!dAs

El formato de entrada es [1 1 1 1 2 2 2]para [4 3], etc.

Se queda sin memoria para el último caso de prueba.

Pruébalo en línea!

Explicación

Y@    % Implicit input. Matrix of all permutations. Each row is a permutation
Xu    % Unique rows
!     % Transpose
d     % Consecutive differences along each column
A     % All: true for columns such that all its entries are nonzero
s     % Sum. Implicitly display
Luis Mendo
fuente