14
\$\begingroup\$

Directions

Write a program that, given an input integer n (n >= 0), outputs the smallest positive integer m where:

  • n = a[1]^b[1] + a[2]^b[2] + a[3]^b[3] + ... + a[k]^b[k]
  • a and b are finite sequences of the same length
  • all elements of a are less than m
  • all elements of b are less than m
  • all elements of a are different and integers a[x] >= 0
  • all elements of b are different and integers b[x] >= 0
  • a[x] and b[x] are not both 0 (since 0^0 is indeterminate)

This is , so fewest bytes wins.

Examples

In 0 -> Out 1
Possible Sum: 

In 1 -> Out 2
Possible Sum: 1^0

In 2 -> Out 3
Possible Sum: 2^1

In 3 -> Out 3
Possible Sum: 2^1 + 1^0

In 6 -> Out 4
Possible Sum: 2^2 + 3^0 + 1^1

In 16 -> Out 5
Possible Sum: 2^4

In 17 -> Out 4
Possible Sum: 3^2 + 2^3

In 23 -> Out 6
Possible Sum: 5^1 + 3^0 + 2^4 + 1^3

In 24 -> Out 5
Possible Sum: 4^2 + 2^3

In 27 -> Out 4
Possible Sum: 3^3

In 330 -> Out 7
Possible Sum: 6^1 + 4^3 + 3^5 + 2^4 + 1^0
\$\endgroup\$
  • \$\begingroup\$ How are we supposed to make a sequence of unique, nonnegative integers that has a non-infinite sum? \$\endgroup\$ – feersum Jan 17 '15 at 3:32
  • \$\begingroup\$ Also, the first case doesn't make sense because a sum with 0 terms would suffice. \$\endgroup\$ – feersum Jan 17 '15 at 3:34
  • \$\begingroup\$ @feersum I don't quite understand your question. My solution to this is a brute force search of all combinations where m<2 then m<3 then m<4 etc. until I find a sum that equals n. Also, I thought about having the sum for 0 be no terms, but then what is the output? m > ? \$\endgroup\$ – kukac67 Jan 17 '15 at 3:40
  • 1
    \$\begingroup\$ For finite sequences, you would usually do something like n = a[1]^b[1] + a[2]^b[2] + ... + a[k]^b[k]. \$\endgroup\$ – Volatility Jan 17 '15 at 8:43
  • 1
    \$\begingroup\$ Nice question. Just one quibble on the first test case: a and b are finite sequences of length 0, so there is no integer m which doesn't satisfy the constraints, and since there is no smallest integer the answer is not defined. Possible fixes would be to ask for the smallest natural number m (in which case you should change the expected answer there to 0) or for the smallest positive integer m. \$\endgroup\$ – Peter Taylor Jan 17 '15 at 8:43
2
\$\begingroup\$

GolfScript (59 chars)

~:T),{),.0{2$0-{2${{4$2$^}2*@3$\?4$+f~}%\;~}%+\;\;}:f~T&}?)

Online demo

This uses recursion to enumerate the values achieveable for a given m and searches for the first m which works. It's lightly inspired by xnor's answer but quite different in implementation.

Dissection

~:T                  # Evaluate input and store in T (for Target)
),{                  # Search [0 1 ... T] for the first m which matches a predicate
  ),.0               #   Push [0 ... m] to the stack twice and then 0
                     #   Stack holds: possibleAs possibleBs sum
  {                  #   Define the recursive function f
    2$0-{            #     Map over A in possibleAs (except 0)
      2${            #       Map over B in possibleBs (except 0)
        {4$2$^}2*    #         Duplicate respective possibles and remove selected values
        @3$\?4$+     #         Compute sum' = sum + A^B
        f            #         Recursive call gives an array [sums]
        ~            #         Push the sums to the stack individually
        }%           #       End map: this collects the sums into a combined array
      \;             #       Pop A, leaving just the combined [sums] inside the map
      ~              #       Repeat the trick: push to the stack individually
    }%               #     End map, collecting into a combined array
                     #     Stack now holds: possibleAs possibleBs sum [sums]
    +                #     Include the original sum in the array of reachable sums
    \;\;             #     Pop possibleAs and possibleBs
  }:f                #   End function definition
  ~                  #   Evaluate the function
  T&                 #   Test whether the sums contain T
}?                   # End search
)                    # Increment to get m
\$\endgroup\$
6
\$\begingroup\$

Python, 120

f=lambda n,A,B:n*all(f(n-a**b,A-{a},B-{b})for a in A for b in B)
g=lambda n,m=1,M={0}:f(n,M-{0},M)and g(n,m+1,M|{m})or m

The function f is an auxiliary function that checks whether n can not be expressed as a sum of powers with distinct bases from A and exponents from B. It uses a natural recursive strategy: n must be nonzero, and we try every possible choice of base and and exponent and they all need to fail. We removing them from the allowed lists and decrease n by the corresponding amount.

The function g is the main function. It searches for an m that works. M is the set of allowed values up to m-1. We remove 0 from the allowed exponents to stop 0**0 (which Python evaluates to 1) from being used. This doesn't hurt anything Because 0**x is a useless 0 for all other x.

\$\endgroup\$
  • \$\begingroup\$ You could probably change n and all() to n*all(). \$\endgroup\$ – grc Jan 18 '15 at 3:31
  • \$\begingroup\$ @grc Ah, you don't actually need the short circuiting because it bottoms out. Thanks for the improvement. \$\endgroup\$ – xnor Jan 18 '15 at 3:39
4
\$\begingroup\$

Python 2, 138 bytes

from itertools import*
S=lambda n,m=0,R=[]:m*any(n==sum(map(pow,*C))for k in R for C in product(*tee(permutations(R,k))))or S(n,m+1,R+[m])

(Thanks to @Jakube for all the tips)

I've never learnt so much about the itertools module as I have from this one question. The last case takes about a minute.

We start by searching from m = 1 and incrementing until we get a solution. To check for a solution we iterate over:

  • k = 0 to m-1, where k is the number of terms in the solution
  • All possible combination of terms (by zipping together two permutations of subsets of [0, 1, ... m-1] with size k), then summing and checking if we have n

Note that we iterate k up to m-1 — even though technically m terms are possible in total, there's always a solution with m-1 terms as 0^0 is not allowed and 0^b contributes nothing. This is actually important because 0^0 is treated as 1 by Python, which seems like a problem, but it turns out not to matter!

Here's why.

Suppose a solution found erroneously uses 0^0 as 1, e.g. 3^2 + 1^1 + 0^0 = 11. Since we only generate up to m-1 terms, there must be some j we are not using as a base (here j = 2). We can swap out the base 0 for j to get a valid solution, here 3^2 + 1^1 + 2^0 = 11.

Had we iterated up to all m terms, then we might have gotten incorrect solutions like m = 2 for n = 2, via 0^0 + 1^1 = 2.

\$\endgroup\$
  • \$\begingroup\$ Nice one. You can save 4 bytes by using imap though. imap(pow,C,D) ... for C,D in \$\endgroup\$ – Jakube Jan 17 '15 at 13:37
  • \$\begingroup\$ @Jakube I'm actually looking through the doc for itertools as we speak :P I already have another saving — tee. \$\endgroup\$ – Sp3000 Jan 17 '15 at 13:40
  • \$\begingroup\$ Me too. Also, my mistake. Why would someone suggest imap, when there is map?? -1 byte \$\endgroup\$ – Jakube Jan 17 '15 at 13:45
  • \$\begingroup\$ The default parameter for tee is already n=2. Saves 2 bytes. \$\endgroup\$ – Jakube Jan 17 '15 at 13:48
  • \$\begingroup\$ @Jakube Ahaha thanks. This is probably the first time I've ever used map with more than one iterable, and in fact this question's bring out a lot of firsts for me. \$\endgroup\$ – Sp3000 Jan 17 '15 at 13:48
4
\$\begingroup\$

GolfScript (90 84 bytes)

[0.,.]](~:T),(+{:x;{:|2,{:c)|=x),^{c[1$x]=:A^x^:-;[|~-+@A-?+@A+@]}%}/+~}%.[]*T&}?)\;

Online demo

Dissection

[0.,.]             # Base case: [sum As Bs] is [0 [] []]
](~:T              # Collect it in an array of cases; fetch parameter, eval, store in T.
),(+               # Create array [1 2 ... T 0]. Putting 0 at the end means that it won't
                   # be reached except when T is 0, and nicely handles that special case.
{                  # Loop over the values from that array...
  :x;              #   ...assigning each in turn to x (and popping it from the stack)
  {                #   Stack holds array of [sum As Bs] cases; map them...

    :|             #     Store [sum As Bs] in |
    2,{:c          #     For c in [0 1]...
      )|=x),^      #       Get [0 1 ... x]^ either As or Bs, depending on c
      {            #       Map these legal new As or Bs respectively...
        c[1$x]=:A  #         Work out which of that value or x is the new A
        ^x^:-;     #         And the other one is the new B
        [          #         Begin gathering in an array
          |~       #           Push sum As Bs to the stack
          -+       #           Add - to Bs to get Bs'
          @A-?+    #           Rotate sum to top and add A^- to get sum'
          @A+      #           Rotate As to top and add A to get As'
          @        #           Final rotation to put elements in the right order
        ]          #         Gather in array [sum' As' Bs']
      }%           #       End map
    }/             #     End for
    +~             #     Push all the elements corresponding to x^B and A^x on to the stack
  }%               #   End map, collecting the untouched [sum As Bs] and all the new
                   #   [sum' As' Bs'] arrays into a new array of reached cases.
  .[]*T&           #   Flatten a copy of that array and filter to values equal to T.
                   #   This gives a truthy value iff we've found a way to make T.
}?                 # Loop until we get a truthy value, and push the corresponding x
)\;                # Increment to get the value of m and discard the array of cases

The most elegant trick is the handling of the special case for 0.

\$\endgroup\$
  • \$\begingroup\$ I am really happy that CJam is this time not soo much shorter than standard python=P \$\endgroup\$ – flawr Jan 18 '15 at 11:34
  • \$\begingroup\$ @flawr, this is GolfScript, not CJam. CJam can probably be quite a bit shorter because it has a built-in for Cartesian products. And it might be that xnor's idea of a recursive function gives shorter GolfScript, too. \$\endgroup\$ – Peter Taylor Jan 18 '15 at 13:49
  • \$\begingroup\$ Oh sorry, just confused them=) \$\endgroup\$ – flawr Jan 18 '15 at 14:54
4
\$\begingroup\$

Haskell, 143 130

import Data.List
p n=head$[1..]>>=(\m->[m|let x=permutations[0..m-1]>>=inits,a<-x,b<-x,sum(zipWith(\x y->x^y*signum(x+y))a b)==n])

Usage example: p 23 -> 6.

This is a simple brute force search. For every list [0..0], [0..1], [0..2] ... [0..∞] take all initial segments of the permutations (e.g. [0..2]: permutations: [012], [102], [210], [120], [201], [021], initial segments for 1st permutation: [0], [01], [012], 2nd: [1], [10], [102], etc.). For every combination of 2 of those lists calculate the sum of powers. Stop when first one equals n.

\$\endgroup\$
  • \$\begingroup\$ you should use >>= rather than concatMap. they are just the same but with the arguments flipped. \$\endgroup\$ – proud haskeller Jan 18 '15 at 14:59
  • \$\begingroup\$ @proudhaskeller: Yes, thanks! \$\endgroup\$ – nimi Jan 18 '15 at 17:07
2
\$\begingroup\$

Python: 166 characters

from itertools import*;p=permutations
f=lambda n,r=[0]:any(n==sum(map(lambda x,y:(x+y>0)*x**y,a,b))for j in r for a,b in product(p(r,j),p(r,j)))*1or 1+f(n,r+[len(r)])

Explanation

The function f creates all possible integers, that can be expressed as sum of powers of of numbers in r. If starts with r = [0]. If any of those integers is equal to n, it returns the length of r, otherwise it call itself recursively with an extended r.

The computation of the all integers, that can be expressed as sum is done with two loops. The first loop is the for j in r, which tells us the length of the expression (2^3 + 1^2 has length 2). The inner loop iterates over all combinations of permutations of r of length j. For each I calculate the sum of powers.

\$\endgroup\$
2
\$\begingroup\$

JavaScript (ES6) 219 224

Recursive function. Starting with m=1, I try all combinations of integer 1..m for bases and 0..m for exponents (0 base is useless given 0^0 == undefined).
If no solution found, increase m and try again.
Special case for input 0 (in my opinion that is an error in the specs anyway)

The C function recursively generates all combinations from an array of given length, so that

C(3, [1,2,3]) --> [[3,2,1], [3,1,2], [2,3,1], [2,1,3], [1,3,2], [1,2,3]]

The third level every is used to zip together the array a of bases and b of exponents (there is no zip function in JavaScript). Using every to stop early when there is a solution not using all elements in the two arrays.

F=(n,j=1,k=[],
  C=(l,a,o=[],P=(l,a,i=l)=>{
    for(l||o.push(a);i--;)
      e=[...a],P(l-1,e.concat(e.splice(i,1)))
  })=>P(l,a)||o
)=>n&&C(k.push(j++),k)[E='every'](a=>C(j,[0,...k])[E](b=>a[E](x=>t-=Math.pow(x,b.pop()),t=n)))
?F(n,j,k):j

Test In FireFox/FireBug console

;[0,1,2,3,6,16,17,23,24,27,330].map(x=>[x,F(x)])

Output

[[0, 1], [1, 2], [2, 3], [3, 3], [6, 4], [16, 5], [17, 4], [23, 6], [24, 5], [27, 4], [330, 7]]

\$\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.