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
fuente
[1, 1, 1, 1, 2, 2, 2]
? Supongo que sí.Respuestas:
Mathematica, 37
444860 6062bytesTome 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!
Split
divide 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:El código se usa
Differences
para determinar si los elementos adyacentes son iguales.Paso a paso:
Permutations@#
genera todas las permutaciones de la lista de entrada a una lista N! * N.Differences/@
calcula la diferencia entre N elementos y genera una lista N! * (N-1).1##&@@@
calcula la multiplicación de todas las listas. Si una lista contiene0
(dos elementos adyacentes son iguales), el resultado será0
, de lo contrario, distinto de cero, a una N! lista.Clip[]
actúa comoSign[]
, transforma la lista de (-inf, inf) a [-1, 1]Tr@Abs
convierte todo-1
en1
y ahora la lista N! -length contiene solo0
(inválido) y1
(válido). Así que solo sumamos la lista.fuente
Permutations@#~Count~Except@{___,x_,x_,___}&
.Count[Split/@Permutations@#,{{_}..}]&
37 bytes!Jalea , 7 bytes
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
fuente
Œ!QIẠ€S
? Pruébalo en línea!P
sobre cualquier átomo por su simplicidad.P€
lugar deẠ€
seguiría funcionando.05AB1E , 7 bytes
Pruébalo en línea!
-1 gracias a nmjcman101 por otra respuesta.
fuente
Mathematica, 50 bytes
¡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 ..."
fuente
Python 3.5 , 65 bytes
Pruébalo en línea!
fuente
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".chars
o alguna otra variedad de formatear método que sea válida en Ruby.Requiere 2.4 para
Enumerator#uniq
(las versiones anteriores solo lo tenían disponible en laArray
clase). Como tal, el enlace TIO agrega 5 bytes para convertir el enumerador de permutación a una matriz primero a través deto_a
, ya que no tiene la función anterior.Pruébalo en línea!
fuente
R, 72 bytes
Crea la función
Toma información en el formulario
[1,1,1,1,2,2,2]
según el comentario de Erik the Outgolfer. Utilizacombinat
lapermn
función para crear una lista de todas las permutaciones y luegounique
obtener todas las entradas distintas.sapply
luego aplica la siguiente función en todas las entradas:Que se evalúa como
Tenga en cuenta que esto
x
no es lo mismo quex
en la entrada de la función grande. Usar otro personaje en esta función engañaríapryr::f
a 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 losFALSE
ceros y ceros en ceroTRUE
, por lo que el vector se convierteFALSE FALSE FALSE FALSE FALSE
. Sumando eso para verificar si hay algunaTRUE
s (TRUE
implicaríadiff=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.fuente
Jalea , 11 bytes
Pruébalo en línea!
fuente
Python 2 ,
14089 bytesEl formato de entrada es
'aaaabbb'
para caso de prueba[4,3]
.Pruébalo en línea!
fuente
Casco , 8 bytes
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.
fuente
Ruby,
8476 bytesUna 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):
fuente
x=p
como la condición inicial?p
actúa como un alias denil
en este caso y debe satisfacer la comprobación para la que se está utilizando.MATL ,
118 bytesEl 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
fuente