Color me a Pole

Question

Lets say your job is to paint poles, and a client asks you to paint a pole with 4 red sections and 3 yellow sections. You can do that pretty easily as follows:

r y r y r y r

With just yellow and red stripes. Now lets say your client asks you to paint a pole with 2 red sections, 2 yellow sections, and 1 green section. There are a couple of ways you could paint your pole

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

More precisely thats 12 ways to paint the pole. This blows up the more colors and sections that are involved

Now if your client says they want 3 red sections and 1 yellow section there is no way to paint a pole like that. Because no matter how you attempt to arrange the sections two red sections will touch, and when two red sections touch they become a single red section.

And that is pretty much our one rule for painting poles

Adjacent sections may not be of the same color

Task

Given a list of colors and sections required, output the number of possible ways to paint a pole as requested. You may represent colors in any reasonable way (integers, characters, strings), but you will never be given more than 255 different colors at a time. If you wish you can even choose to not have the colors assigned names and just take a list of section counts if that is easier.

Test Cases

These are rather hard to calculate by hand, especially as they get larger. If anyone has a suggested test case I'll add it.

[4,3]    -> 1
[2,2,1]  -> 12
[3,1]    -> 0
[8,3,2]  -> 0
[2,2,1,1]-> 84

Answer 1

Mathematica, 37 44 48 60 62 bytes

Take input as a list of integers {1, 1, 1, 2, 2}. Try it on Wolfram Sandbox.

Pattern-matching method, thanks @Not a tree !

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

Split splits a single list into sublists of consecutive elements, e.g. {1, 1, 2, 3, 4, 4} into {{1, 1}, {2}, {3}, {4, 4}}

{{_}..} is, namely, {{_}, {_}, {_}, ...}. The pattern matches a list of unary sublists.

Differences method, 48 bytes:

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

The code uses Differences to determine whether adjacent elements are the same.

Step by step:

1. Permutations@# generates all permutations of input list to a N!*N list.
2. Differences/@ calculates the difference between N elements, and yields a N!*(N-1) list.
3. 1##&@@@ calculates the multiplication of all lists. If a list contains 0 (two adjacent elements are the same), the result will be 0, otherwise non-zero, to a N! list.
4. Clip[] acts like Sign[], transform the list from (-inf, inf) to [-1, 1]
5. Tr@Abs turns all -1 into 1 and now the N!-length list contains only 0 (invalid) and 1 (valid). So we just sum the list.

Answer 2

Jelly, 7 bytes

Œ!QIẠ€S

Try it online!

Takes input as e.g. [1,1,1,1,2,2,2] for [4,3]. The [8,3,2] testcase takes too long to run on TIO.

How it Works

Œ!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

Answer 3

05AB1E, 7 bytes

œÙ€¥PĀO

Try it online!

-1 thanks to nmjcman101 on another answer.

Answer 4

Mathematica, 50 bytes

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

Try it in Mathics, or at the Wolfram sandbox!

Takes input like in the test cases — e.g. {4,3} means "4 red stripes, 3 yellow stripes".

This is a naïve implementation of a formula I found here. "Naïve" means "I have no idea how the maths works so please don't ask me for an explanation…"

Answer 5

Python 3.5, 65 bytes

f=lambda s,p=0:sum(f(s.replace(c,'',1),c)for c in{*s}-{p})or''==s

Try it online!

Answer 6

Ruby 2.4, 47 bytes

Input is a list of characters: For the test case [4,3], input can be %w[a a a a b b b], "1111222".chars, or some other array formatting method that's valid in Ruby.

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

Requires 2.4 for Enumerator#uniq (earlier versions only had it available on the Array class). As such, the TIO link adds 5 bytes to convert the permutation enumerator to an array first via to_a, since it does not have the above function.

Try it online!

Answer 7

R, 72 bytes

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

Creates the function

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

Takes input in the form [1,1,1,1,2,2,2] as per Erik the Outgolfer's comment. Uses combinat's permn function to create a list of all permutations, and then unique to get all distinct entries. sapply then applies the following function on all entries:

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

Which evaluates to

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

Note that this x is not the same as the x in the big function's input. Using another character in this function would fool pryr::f into believing the big function needs another argument.

Anyways, when given a permutation, this function takes the difference between the vector: 2 1 3 4 2 1 -> -1 2 1 -2 -1. ! converts nonzero's into FALSE and zeros into TRUE, so the vector becomes FALSE FALSE FALSE FALSE FALSE. Summing that to check if there are any TRUEs (TRUE would imply diff=0 --> two the same consecutive numbers). We can again invert this with ! to get a boolean on whether or not there are consecutive values in the permutation.

Summing over these booleans gives us the total number of permutations where this is not the case.

Doesn't work for the [8,3,2] testcase because it requires a vector of 46GB to store those permutations.

Answer 8

Jelly, 11 bytes

Œ!Q⁻2\Ạ$ÐfL

Try it online!

Answer 9

Python 2, 140 89 bytes

Input format is 'aaaabbb' for test case [4,3].

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

Try it online!

Answer 10

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}

A recursive lambda function. Looks at each possible color and dose a recursive tree search, counting the number of times it uses all stripes.

Explanation (for old version):

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 
}

Answer 11

Husk, 8 bytes

#ȯ¬ṁtguP

Try it online! Takes input in the format "aaabb" for [3,2]. Times out on the longest test case.

Explanation

Nothing fancy here, just counting the unique permutations where all groups of adjacent elements have length 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.

Answer 12

MATL, 11 8 bytes

Y@Xu!dAs

Input format is [1 1 1 1 2 2 2] for [4 3], etc.

Runs out of memory for the last test case.

Try it online!

Explanation

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