9
\$\begingroup\$

Introduction

You are a friend of a curator for an art museum, who has had the recent delight of getting modern art from four artists (some of which may give the curator zero pieces of art, young scoundrels). As this is modern art, all of any given artist's pieces look exactly the same. Your friend wants to use a computer to help decide which order to place these pieces in.

Program Requirements

Your program must take five integers (passed to a function or inputted through stdin (or someway else)). The first four are the number of paintings supplied by each of the four artists. The last value is an permutation index i (counting from 1, not 0). The curator wishes to see the ith permutation by lexicographic order of the paintings.

Your program must output this permutation in any reasonable format: e.g. abbccd or [0 1 1 2 2 3]. The runtime for input totalling fewer than ten paintings must take less than an hour (this should hopefully be no problem).

You are not allowed to use any in-built functions to work out permutations

Examples

Input: 0 1 2 0 2

Given that we have one painting by artist B and two by artist C (and they all look the same), the permutations in lexicographic order are:

['bcc', 'cbc', 'ccb']

The highlighted permutation would be the correct output, because it is the second in lexicographic order.

Input: 1 2 0 1 5

['abbd', 'abdb', 'adbb', 'babd', 'badb', 'bbad', 'bbda', 'bdab', 'bdba', 'dabb', 'dbab', 'dbba']

Testing

Here are some tests that should be correct.

1 2 4 1 5    - ABBDCCCC
2 2 3 1 86   - ABBCACDC
4 1 2 0 24   - AACACBA
1 4 3 2 65   - ABBCBBDCDC

A short piece of code in Python3 that should randomly generate inputs and outputs is available here (not valid for entry, this uses the Python import of permutations):

from itertools import permutations
from random import randint
a,b,c,d,n = randint(1,2),randint(1,2),randint(1,3),randint(1,3),randint(1,15)
print(str(a) + " " + str(b) + " " + str(c) + " " + str(d) + " " + str(n) + " - " + str(sorted(set([''.join(p) for p in permutations(a * "a" + b * "b" + c * "c" + d * "d")]))[n-1]))

Scoreboard

Optimizer - CJam       - 39  - Confirmed - Bruteforce
EDC65     - JavaScript - 120 - Confirmed - Bruteforce
Jakube    - Python2    - 175 - Confirmed - Algorithmic
\$\endgroup\$
  • 1
    \$\begingroup\$ You say, " all of the pieces look exactly the same". Do you mean "all the the pieces from a given artist look exactly the same, but pieces from different artists look different"? \$\endgroup\$ – DavidC Jan 4 '15 at 17:04
  • \$\begingroup\$ This wouldn't be a valid entry, but I think it might still be useful for someone: {:A.a.{~97+[:I.}: is valid J and works, but uses A. for most of the work, so it isn't valid. If you could write a function that replaces A. and subsitute it in this function, you'd have a valid answer. \$\endgroup\$ – ɐɔıʇǝɥʇuʎs Jan 4 '15 at 17:05
  • \$\begingroup\$ @ɐɔıʇǝɥʇuʎs - You don't have to use "ABCD", you can use any character/numerical/symbolic system at all. I'm afraid I don't know J, and so cannot tell the exact problem, but hope this helps =) \$\endgroup\$ – Alexander Craggs Jan 4 '15 at 17:07
  • \$\begingroup\$ @PopeyGilbert Well, a version that just spits out numbers would be {:A.[:I.}:... The thing is that, but I still don't think A. would be valid: jsoftware.com/help/dictionary/dacapdot.htm \$\endgroup\$ – ɐɔıʇǝɥʇuʎs Jan 4 '15 at 17:10
  • \$\begingroup\$ What if the required permutation does not exists? 1 0 0 0 100 ? \$\endgroup\$ – edc65 Jan 4 '15 at 20:29
5
\$\begingroup\$

Python 2: 175 163 chars

This is not a serious golfing answer. With a different algorithm I reached 138 byte. Just wanted to post this here, because it doesn't use brute force. Complexity is Theta(#pictures).

f=lambda x:0**x or x*f(x-1)
def g(Q,n):
 while sum(Q):
  for j in 0,1,2,3:
   p=f(sum(Q)-1)*Q[j]
   for k in Q:p/=f(k)
   if p<n:n-=p
   else:print j;Q[j]-=1;break

Usage:

g([1, 4, 3, 2], 65)

edit:

Same algorithm, just some golfing: don't import the factorial method and little changes in the order of the calculations.

Pyth translation: 61 characters

Lu*GhHUb1WsPQV4J*@QNytsPQFZPQ=J/JyZ)I<JeQ XQ4-eQJ)EN XQNt@QNB

Nothing special here, exact translation of my python code. Way too long though. I had too use a few ugly (long) things. The first 9 letter alone is the definition of the factorial.

Lu*GhHUb1    def y(b): G=1; for H in range(b): G*= H+1; return G

Also stuff like Q[j]-=1 is way too long: XQNt@QN (1 character more than Python!!!)

Usage:

Try it here: Pyth Compiler/Executor. Disable debug mode and use [2, 2, 3, 1, 86] as input.

\$\endgroup\$
  • \$\begingroup\$ It works! Congratulations on coming up with the first Python solution! However, I did find that in my environment I have to move from math import* outside the function. Adding you to the leaderboard! \$\endgroup\$ – Alexander Craggs Jan 5 '15 at 10:36
  • \$\begingroup\$ Wow... Your solution is incredibly efficient - For 32 paintings it takes only 0.034 seconds o.0. \$\endgroup\$ – Alexander Craggs Jan 5 '15 at 10:48
3
\$\begingroup\$

CJam, 50 43 39 bytes

q~(])\{W):Wa*}%s:X{Xm*:s_&}X,(*{$X=},$=

This can be golfed a lot.

Takes input from STDIN in following format:

4 1 2 0 24

Outputs the painting. For example for above input:

0020210

Try it online here

Do note that the online compiler gives up for larger painting sizes. You will have to try larger inputs on the Java version

\$\endgroup\$
  • \$\begingroup\$ Congratulations on being the first solver! 50 bytes is certainly a hard value to beat. I'll add you as the top of the leaderboard! \$\endgroup\$ – Alexander Craggs Jan 4 '15 at 17:13
  • \$\begingroup\$ @PopeyGilbert you should at least wait for 1 week or so before accepting an answer \$\endgroup\$ – Optimizer Jan 4 '15 at 17:52
  • \$\begingroup\$ Ah, okay, I'm very sorry! In my previous challenge I just changed the accepted answer when someone got beaten. My bad. \$\endgroup\$ – Alexander Craggs Jan 4 '15 at 17:53
  • 1
    \$\begingroup\$ @PopeyGilbert That's very noble of you (and I wish all challenger authors did), and in principle there's nothing wrong with accepting early if you do, but some people seem to get offended if a challenge around here accepts an answer early (because, I guess, no one expects the author to change the accepted answer). \$\endgroup\$ – Martin Ender Jan 4 '15 at 17:59
  • \$\begingroup\$ I personally think that there should be at least 2 answers to choose between before accepting, even if its done early. Of course if there is only 1 answer till a week or so, accept it. \$\endgroup\$ – Optimizer Jan 4 '15 at 18:01
3
\$\begingroup\$

JavaScript (ES6) 120 138 147

As a function with the required five parameters, output via console.
Using symbols 0,1,2,3. I calc the total of symbols, then build and check every base 4 number having the required number of digits. Numbers with the wrong number of any digit are discarded.
Note: with JavaScript 32 bit integer this works for up to 15 paintings.

Edit Shorter (avoid .toString) and way faster (modified exit condition). Time for each test below 1 sec.

Edit2 no algorithm change, golfed more (indentation added for readability)

F=(w,x,y,z,n)=>{
  for(a=0;n;n-=l=='0,0,0,0')
    for(l=[w,x,y,z],t=w+x+y+z,v='',b=a++;t--;b/=4)--l[d=b&3],v=d+v;
  console.log(v)
}

Ungolfed And no FireFox required

F=function(w,x,y,z,n) {
  for(a=0; n; a++) // exit when solution found (if wrong parameters, run forever)
  {
    l=[w,x,y,z]; // required number of each symbol
    t=w+x+y+z; // total of digits
    v=''; // init output string
    for(b=a;
      t--; // digit count down
      b >>= 2) // shift for next digit
    {
        d = b & 3; //get digit
        --l[d]; // decrement for the current digit
        v = d + v; // add to output string         
    }
    l[0]|l[1]|l[2]|l[3] // if digits ok
    ||--n // decrement counter
  }
  console.log(v) // when found, exit for and print the answer
}

Test In FireBug/FireFox console

F(1, 2, 4, 1, 5) 
F(2, 2, 3, 1, 86)
F(4, 1, 2, 0, 24)
F(1, 4, 3, 2, 65)

Output

01132222
01120232
0020210
0112113232
\$\endgroup\$
  • \$\begingroup\$ Hello! Having a bit of trouble running it. I'm downloading FireFox to see if that will help. I'll add you to the leaderboard! \$\endgroup\$ – Alexander Craggs Jan 4 '15 at 21:13
  • \$\begingroup\$ I found rather a nice table here - I'll assume Firefox is necessary. Tested and it works! Changed leaderboard to confirmed. \$\endgroup\$ – Alexander Craggs Jan 4 '15 at 21:21
  • \$\begingroup\$ Leaderboard but no upvote ... you really don't like it! :( \$\endgroup\$ – edc65 Jan 4 '15 at 21:28
  • \$\begingroup\$ Agh! I'm so sorry =( It's upvoted now =) \$\endgroup\$ – Alexander Craggs Jan 4 '15 at 21:30
  • \$\begingroup\$ I wonder how long this algorithm will be in CJam. But as of now, I have no idea how this works :P \$\endgroup\$ – Optimizer Jan 4 '15 at 21:54
2
\$\begingroup\$

Pyth, 20

@fqPQm/TdU4^U4sPQteQ

Try it here.

Input is in Python list form, e.g. [1, 2, 4, 1, 5]

Output is also in Python list form, e.g. [0, 1, 1, 3, 2, 2, 2, 2] for the above input.

The solution is brute force, and takes about 10 seconds, worst case, on my machine.

How it works:

@fqPQm/TdU4^U4sPQteQ
           ^U4sPQ         All permutations of [0, 1, 2, 3] with length equal to the number
                          of paintings.
     m/TdU4               Find the count (/) of paintings by painter in the input list.
 fqPQ                     Filter the permutations on the counts being the desired counts
                          in the input.
                          This gives all possible orderings of the paintings.
@                teQ      Index into this list at the given location - 1. (0-indexing)
\$\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.