12
\$\begingroup\$

We are putting balls into a fixed number a bins. These bins begin empty.

Empty bin (a=4): 0 0 0 0 

And one by one we add balls to the bins.

0 0 0 1  or
0 0 1 0  or
0 1 0 0  or
1 0 0 0

We need a quick way to loop over all the possible states the bins take, without duplicates and without missing any and we don't want to enumerate all the possible bins. So instead we assign each bin-configuration an index.

We assign the index by sorting the possible configurations in a specific way:

  1. Sort ascending by sum: so first 0 0 0 0, then the possible configurations with 1 ball added, then 2, etc.

  2. Then sort within each sum in ascending order, from the first bin to the last:

    0 0 0 2
    0 0 1 1
    0 0 2 0 
    0 1 0 1
    0 1 1 0 
    0 2 0 0 
    etc
    
  3. The index is then assigned ascending through this list:

    0 0 0 0  -> 1
    0 0 0 1  -> 2
    0 0 1 0  -> 3
    0 1 0 0  -> 4
    1 0 0 0  -> 5
    0 0 0 2  -> 6
    0 0 1 1  -> 7
    0 0 2 0  -> 8
    0 1 0 1  -> 9
    0 1 1 0  -> 10
    0 2 0 0  -> 11 
    

Rules

Create a function or program that takes a list of any size with non-negative integers and print or output its index. You can assume a to be at least 2. Shortest code wins. You may use 0-indexed output or 1-indexed, but specify which you use. NB: all examples here are 1-indexed.

Example code

Not golfed, in R:

nodetoindex <- function(node){
  a <- length(node)
  t <- sum(node)
  if(t == 0) return(1)

  index <- choose(t-1 + a, a)

  while(sum(node) != 0){
    x <- node[1]
    sumrest <- sum(node)
    if(x == 0){
      node <- node[-1]
      next
    }
    a <- length(node[-1])
    index <- index + choose(sumrest + a, a) - choose(sumrest - x + a, a)
    node <- node[-1]
  }
  return(index + 1)
} 

Test cases

10 10 10 10 -> 130571
3 1 4 1 5 9 -> 424407
2 9 -> 69
0 0 0 -> 1
0 0 1 -> 2
0 0 0 0 0 0 -> 1
1 0 0 0 0 1 -> 23
\$\endgroup\$
  • \$\begingroup\$ How does sorting via the numerical value of the concatenation work when the counts have different numbers of digits? \$\endgroup\$ – TheBikingViking Dec 6 '16 at 18:29
  • \$\begingroup\$ @TheBikingViking hmm, hadn't thought of that, I changed the wording to reflect the example code and the test cases. Within each sum, the configurations are sorted first in the first bin, then in the second, and so forth. \$\endgroup\$ – JAD Dec 6 '16 at 19:18
3
\$\begingroup\$

Jelly, 8 bytes

S0rṗLSÞi

Try it online!

Brute-force solution. The first test case is too much for TIO, but I've verified it locally on my laptop. The second test case requires too much RAM, even for my desktop computer.

How it works

S0rṗLSÞi  Main link. Argument: A (array)

S         Compute the sum s of A.
 0r       Create the range [0, ..., s].
    L     Yield the length l of A.
   ṗ      Cartesian power; yield the array of all l-tuples over [0, ..., s], in
          lexicographical order.
     SÞ   Sort the l-tuples by their sums. The sorting mechanism is stable, so
          l-tuples with the same sum are still ordered lexicographically.
       i  Find the index of A in the generated array of tuples.
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Nice. Your remark about RAM reminded me of the source of this challenge. For my thesis I needed to loop over all possible arrays for some a=8 and as high as possible balls. The idea to transform the arrays to indices and just loop over those came exactly from the limitation of RAM :P \$\endgroup\$ – JAD Dec 7 '16 at 11:23
  • \$\begingroup\$ Which is also why the example code is so wordy :P \$\endgroup\$ – JAD Dec 7 '16 at 11:25
1
\$\begingroup\$

Clojure, 152 bytes

#(loop[v[(vec(repeat(count %)0))]i 1](if-let[r((zipmap v(range))%)](+ r i)(recur(sort(set(for[v v i(range(count v))](update v i inc))))(+ i(count v)))))

Not as easy as I thought. Less golfed version:

(def f (fn[t](loop[v[(vec(repeat(count t)0))]i 1]
               (if-let[r((zipmap v(range))t)](+ r i)
                 (recur (sort-by (fn[v][(apply + v)v]) (set(for[v v i(range(count v))](update v i inc))))
                        (+ i(count v)))))))

Loops over current states v, creates a hash-map from elements of v to their rank, if the searched state is found then its rank is returned (+ the number of previously seen states). If not found then recurses with a new set of possible states.

Oh actually we don't need that custom sorting function as all states within each loop has identical sum. This isn't as slow as I expected as [3 1 4 1 5 9] took only 2.6 seconds.

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

Mathematica, 50 bytes

A port of Dennis's Jelly answer.

0~Range~Tr@#~Tuples~Length@#~SortBy~Tr~Position~#&

Unnamed function taking a list of integers as input, and returning a depth-2 list with a single integer as output; for example, the input for the last test case is {1,0,0,0,0,1} and the output is {{23}}.

A slightly ungolfed version is:

Position[SortBy[Tuples[Range[0,Tr[#]],Length[#]],Tr],#]&

Often we can save individual bytes in Mathematica by using prefix notation (function@n instead of function[n]) and infix notation (a~function~b instead of function[a,b]). This only works, however, when the resulting code happens to mesh well with Mathematica's intrinsic precedence order for applying functions. I was kind of amazed here that, with six sets of square brackets, it actually worked to remove all of them and save six bytes with the (pleasantly bracketless) submitted code.

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.