10
\$\begingroup\$

You have been given N piles of coins. You have decided to divide each of those B1, B2, ..., BN piles among separate groups of people. The amount of people receiving coins has to be a prime number and the amount of money given to each person must be different in each pile.

Input: N, B1, B2, ..., BN (The amount of coins in each individual pile).

Output: NP1, NP2, ..., NPN with NP being the number of people(prime number) receiving the coins. If this is impossible then yield some unachievable result (like 0, -1, None, [], or "impossible") or raise an error.

Example:

3
7 8 9

Output: 7 2 3

Because 7 is the only prime number that can divide 7 evenly, the same for 8 and 2 and 9 and 3. Also, notice that (7 / 7 = 1) ≠ (8 / 2 = 4) ≠ (9 / 3 = 3).

\$\endgroup\$
9
  • 2
    \$\begingroup\$ N is a redundant input, may we forego taking it? \$\endgroup\$ Dec 23, 2017 at 23:37
  • \$\begingroup\$ May we yield some other non-achievable result (e.g. 0, an empty list, a string like "impossible", or raise an error) for impossible cases? (I'd actually recommend only valid input, or allowing undefined behaviour in such cases, but it's up to you.) \$\endgroup\$ Dec 23, 2017 at 23:40
  • 2
    \$\begingroup\$ You may forego the input of N. And yes to the second question. \$\endgroup\$
    – McLinux
    Dec 23, 2017 at 23:41
  • \$\begingroup\$ So, the lowest prime divisor of each number? \$\endgroup\$ Dec 23, 2017 at 23:53
  • \$\begingroup\$ @totallyhuman not quite - if the input were say [7,8,8] it would be impossible (since using 2 for both 8 results in two 4s.) Furthermore, if the input were say [7,30,30] then [7,2,2] would be invalid but [7,2,3] and [7,3,2] amongst others would work. \$\endgroup\$ Dec 24, 2017 at 0:01

3 Answers 3

5
\$\begingroup\$

05AB1E, 13 bytes

Ò.»â€˜ʒ÷DÙQ}θ

Try it online!

A port of my Pyth answer.

  • Ò gets the prime factÒrs of each.
  • folds a dyadic command, â (cârtesiân product) between each two elements in the list from right to left with opposite right/left operands.
  • €˜ flattens ach.
  • ʒ...} filtʒrs those which satisfy the following condition:
    • ÷ pairwise integer division with the input.
    • D Duplicate (pushes two copies of the item to the stack).
    • Ù removes duplicate elements, keeping a ÙniqÙe occurrence of each element.
    • Q checks for eQuality.
  • θ gets the last element.
\$\endgroup\$
4
\$\begingroup\$

Jelly,  15  14 bytes

³:ŒQẠ
ÆfŒpÇÐfṪ

A full-program which accepts one argument, a list of numbers, and prints a representation of another list of numbers, or 0 if the task is impossible.

Try it online!

How?

³:ŒQẠ - Link 1, unique after division?: list of primes, Ps   e.g. [7,2,2]  or  [7,3,3]
³     - program's first input                                e.g. [7,8,8]  or  [7,9,30]
 :    - integer division by Ps                                    [1,4,4]      [1,3,10]
  ŒQ  - distinct sieve                                            [1,1,0]      [1,1,1]
    Ạ - all truthy?                                               0            1

ÆfŒpÇÐfṪ - Main link: list of coin stack sizes, Bs   e.g. [7,8,12]
Æf       - prime factorisation (vectorises)               [[7],[2,2,2],[2,2,3]]
  Œp     - Cartesian product                              [[7,2,2],[7,2,2],[7,2,3],[7,2,2],[7,2,2],[7,2,3],[7,2,2],[7,2,2],[7,2,3]]
     Ðf  - filter keep if:
    Ç    -   call last link (1) as a monad                 1       1       0       1       1       0       1       1       0
         -                                                [[7,2,2],[7,2,2],[7,2,2],[7,2,2],[7,2,2],[7,2,2]]
       Ṫ - tail (note: tailing an empty list yields 0)    [7,2,2]
         - implicit print
\$\endgroup\$
1
  • \$\begingroup\$ +1 Haha, I think µ⁼Q would work as an alternative to the fancy distinct sieve, but good job! \$\endgroup\$
    – Mr. Xcoder
    Dec 24, 2017 at 6:59
2
\$\begingroup\$

Pyth, 15 bytes

ef{I/VQT.nM*FPM

Try it here!

How?

ef{I/VQT.nM*FPM | Full program, which foregoes the size.
                |
             PM | Prime factorisation of each integer.
           *F   | Fold Cartesian Product over the list of primes.
        .nM     | Flatten each.
 f              | Filter.
  {I/VQT        | Filter condition (uses a variable T).
    /V          | Vectorised integer division...
      QT        | Over the input and the current item.
  {I            | Is invariant over deduplication (removing duplicates)?
e               | Take the last element.
                | Output the result implicitly.
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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