19
\$\begingroup\$

We have a strictly increasing sequence of non-negative integers, like:

12 11 10

Wait! This sequence isn't strictly increasing, is it? Well, the numbers are written in different bases. The least possible base is 2, the biggest is 10.

The task is to guess bases each number is written, so that:

  • the sequence is strictly increasing,
  • the sum of the bases is maximised.

For instance, the solution for the sample will be:

6 8 10

because under those bases the sequence becomes 8 9 10 decimal - a strictly increasing sequence, and we are not capable of finding bases for which the sequence remains strictly increasing and whose sum is bigger than 6+8+10 .

Due to the second limitation a solution 3 5 7 is not satisfactory: in spite of fact that the sequence becomes 5 6 7 under those bases - we need to maximise the bases sum, and 3+5+7 < 6+8+10.

If under no bases 2<=b<=10 is it possible for the series to be strictly increasing, for instance:

102 10000 10

single

0

should be output.

The input sequence can be passed in the way it's most convenient for your solution (standard input / command line parameters / function arguments...).

\$\endgroup\$
  • 1
    \$\begingroup\$ Is 1 3 5 a rising sequence? What about 1 7 22? (in base 10) \$\endgroup\$ – Doorknob Aug 7 '15 at 20:35
  • \$\begingroup\$ Yes, 1 3 5 and 1 7 22 are both rising under base 10. So, the solution for both cases is 10 10 10 , because we need to maximize the sum of bases while assuring that the sequence is rising when n-th number is interpreted as being written in base equal to n-th term of solution. \$\endgroup\$ – pawel.boczarski Aug 7 '15 at 20:43
  • 2
    \$\begingroup\$ @Dennis Yes, I mean strictly increasing sequence. 1 1 1 or 3 3 4 are not rising. \$\endgroup\$ – pawel.boczarski Aug 7 '15 at 20:53
  • 3
    \$\begingroup\$ If comments indicate that the question is open to misinterpretation, don't just reply in comments. Edit the question so that other people don't waste time writing answers which interpret it differently to you. \$\endgroup\$ – Peter Taylor Aug 8 '15 at 7:04
  • 3
    \$\begingroup\$ And on the subject of ambiguities, one of the comments on my answer claims that we should assume that the numbers are written in canonical form in the given base. If this is so, please correct the phrase "The least possible base is 2" to something like "The least possible base is one greater than the largest digit value". \$\endgroup\$ – Peter Taylor Aug 8 '15 at 7:17
13
\$\begingroup\$

Pyth, 31 30 29 bytes

e+0f.x!sgM.:iVczdT2ZosN^STlcz

1 byte thanks to @Jakube.

Demonstration. Test Harness.

Input is given on STDIN, space separated. If newline separated input is allowed, I can shorten the program by 2 bytes.

Explanation:

e+0f.x!sgM.:iVczdT2ZosN^STlcz
                                  Implicit: z = input(), T = 10, Z = 0, d = ' '
                        ST        [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
                          lcz     len(z.split())
                       ^          All combinations w/replacement of that length.
                    osN           Order by increasing sum.
   f                              Filter on
              czd                 z.split(' ')
            iV   T                Vectorize the "Convert to base" operation over 
                                  the integers as strings and the base sequence.
          .:      2               Take length 2 subsequences.
        gM                        Map the >= operation over them.
      !s                          Sum and logically negate.
    .x             Z              If that throws an error, returns 0 (e.g. reject)
 +0                               Prepend a 0, in case no sequences are found.
e                                 Take the end of the list.

Including 1 in the list of possible bases is safe because i, which uses Python's int builtin, doesn't allow 1 as a base, and therefore always throws an error, which is caught and filtered out.

\$\endgroup\$
9
\$\begingroup\$

CJam, 43 bytes

0B,2>ea,m*{:+~}${ea::~_2$.b__Q|$=*@.b=}=p];

Reads command-line arguments and prints an array.

Try it online in the CJam interpreter.

Examples

$ cjam rise.cjam 12 11 10
[6 8 10]
$ cjam rise.cjam 19 18 17
0

How it works

0       e# Push a 0 (default return value).
B,2>    e# Push [0 ... 10] and remove the first two elements.
ea,     e# Push the number of command-line arguments (n).
m*      e# Cartesian power. Pushes all vectors of {2 ... 10}^n.
{:+~}$  e# Sort by the negated sums.
{       e# Find; for each vector V in {2 ... 10}^n:
  ea::~ e#   Evaluate each character of each command-line argument.
  _2$   e#   Copy the results and V.
  .b    e#   Vectorized base conversion (list to integer).
  __    e#   Push two copies.
  Q|$   e#   Deduplicate and sort the last copy.
  =     e#   Compare it to the first. Pushes 1/0 if equal/unequal.
  *     e#   Repeat the original result of .b that many times.
  @.b   e#   Vectorized base conversion (integer to list).
  =     e#   Compare the result to the modified command-line arguments.
        e#   Equality makes sure that the base was greater than all digits.
}=      e# If pushed 1, push V and break.
p       e# Print. Either prints the last V or 0 if none matched.
];      e# Clear the stack to avoid implicitly printing the 0 (if still present).
\$\endgroup\$
6
\$\begingroup\$

Julia, 176 156 145 118 109 99 97 bytes

A->try p=NaN;flipud(map(i->(k=11;t=p;while t<=(p=parseint("$i",k-=1))end;k),flipud(A)))catch;0end

Ungolfed:

function anonfunc(i)
  # Start with k=11 so that it evaluates to 10 on first while iteration
  k=11
  # set t to the previous value of p
  # Note: p here gets held over between iterations within the map
  t=p
  # Iterate through, dropping k by 1 and evaluating the integer in
  # base k and stopping if the value drops below t
  # Note: "p=" expression inside conditional to ensure k-=1 is evaluated
  # at least once (to make NaN work as desired)
  while t<=(p=parseint("$i",k-=1))
  end
  # if it dropped below t, return the base, k to be the corresponding
  # element in the map
  return k
end

function f(A)
  # Using try/catch to return 0 if no acceptable base found
  try
    # This is a trick to make sure the comparison in the while loop
    # evaluates to false on the first use of it (last value in A)
    p=NaN
    # Apply anonfunc to each element of A, starting with the last element
    # and store the result in S
    S=map(anonfunc,flipud(A))
    # S is backwards, so flip it and return it
    return flipud(S)
  catch
    # Will throw to here if parseint fails with the base due to having
    # a digit not acceptable in the base
    return 0
  end
end

Used with a 1d array input. If the function is assigned to c, then you would call c([12,11,10]) and it would output [6,8,10].

Note: I had used dec(i) inside the parseint command, but because i is a single-character variable name, and I don't need to access a component, I used "$i" to get the same result.

\$\endgroup\$
  • \$\begingroup\$ You've got some good tricks in here. Nice work. \$\endgroup\$ – Alex A. Aug 8 '15 at 17:24
  • \$\begingroup\$ This code seems to check bases for strictly decreasing sequence under usual left-to-right order of reading. \$\endgroup\$ – pawel.boczarski Aug 22 '15 at 9:24
  • \$\begingroup\$ @pawel.boczarski - I'm not sure what you mean, but if you'd like, I can provide some examples of what it outputs for certain inputs. For instance, if you assign the function the name c, then c([12,11,10]) outputs [6,8,10], which are the required bases. \$\endgroup\$ – Glen O Aug 22 '15 at 10:01
  • \$\begingroup\$ @GlenO Oh, I see. I used row vector [12 11 10] instead of [12,11,10] and that gave the undesired effect. \$\endgroup\$ – pawel.boczarski Aug 22 '15 at 10:16
  • \$\begingroup\$ @pawel.boczarski - ah, I see. Yeah, if you want it to work with row vectors, you'd need to replace "flipud" with "fliplr", in which case it will return a row vector of the bases. \$\endgroup\$ – Glen O Aug 22 '15 at 12:06
5
\$\begingroup\$

Julia, 259 204 183 bytes

Saved a bunch with help from Glen O.

A->(M(x)=maxabs(digits(x))+1:10;S=[];X={};for i=M(A[1]),j=M(A[2]),k=M(A[3]) s=map(parseint,map(dec,A),[i,j,k]);all(diff(s).>0)&&(S=[S,sum(s)];X=[X,{[i,j,k]}])end;X==[]?0:X[indmax(S)])

Ungolfed + explanation:

function f(A)
    # Define a function to obtain the smallest possible base range
    M(x) = (maxabs(digits(x)) + 1):10

    # Define container arrays for the sums and bases
    S = []
    X = {}

    # Loop over all possible bases for each of the elements
    for i = M(A[1]), j = M(A[2]), k = M(A[3])
        # Parse each element of the input as a string
        # in the given base
        s = map(parseint, map(dec, A), [i,j,k])

        # Push the sum and bases if s is rising
        if all(diff(s) .> 0)
            S = [S, sum(s)]
            X = [X, {[i,j,k]}]
        end
    end

    # If X is empty, return 0, otherwise return the bases
    isempty(X) ? 0 : X[indmax(S)]
end
\$\endgroup\$
  • \$\begingroup\$ OK, some golfing to be done... use "repr" instead of "string" in the map command, they'll work the same in this context and save two bytes. And we can save a few more by using an infix operator for parseint by writing "\ =parseint" and then using x[1]\i rather than p(x[1],i) - one more byte in the "\ " part, and then saving three for each use of p for a net saving of 8 bytes. Another one byte saved by replacing "maximum(digits(x)) with max(digits(x)...)" \$\endgroup\$ – Glen O Aug 8 '15 at 10:52
  • \$\begingroup\$ For a bigger saving, merge the for loops - use for i=M(A[1]):10,j=M(A[2]):10,k=M(A[3]):10 <code here>end;, saving eight for the dropped two end;s and eight for replacing ` for ` with ,. \$\endgroup\$ – Glen O Aug 8 '15 at 11:02
  • \$\begingroup\$ Actually, we can do even better for the parseint part. Drop the renaming of parseint entirely, and use s=map(parseint,x,[i,j,k]), saving 18 bytes relative to your original solution and 10 compared with my previous suggested improvement. And rather than s==sort(unique(s)), use all(diff(s).>0) to save another 3 bytes. \$\endgroup\$ – Glen O Aug 8 '15 at 11:51
  • \$\begingroup\$ There's certainly more that can be done, but I'll leave it to you, and try to come up with my own approach instead. \$\endgroup\$ – Glen O Aug 8 '15 at 11:53
  • \$\begingroup\$ Minor correction - I suggested using max(...) rather than maximum... but while it saves one byte, it fails for single-digit input values, so you have to use maximum. \$\endgroup\$ – Glen O Aug 8 '15 at 14:26
4
\$\begingroup\$

CJam (39 bytes)

{Afb:X,9,2f+m*{X\.b__$_&=*},{:+}$0\+W=}

This is an anonymous function which takes the input as an array of decimal integers on the stack and leaves the output as an array or the integer 0 on the stack. Online demo.

\$\endgroup\$
  • \$\begingroup\$ Also, this seems to sort by the sum of the resulting integers instead of the bases and it has the same problem my previous revision had (19 cannot be a base 9 number). \$\endgroup\$ – Dennis Aug 8 '15 at 2:59
  • 1
    \$\begingroup\$ Hmm. The question seems to need some improvement. \$\endgroup\$ – Peter Taylor Aug 8 '15 at 7:03
  • \$\begingroup\$ @PeterTaylor Pah, excuses ;) \$\endgroup\$ – Beta Decay Aug 8 '15 at 9:38
2
\$\begingroup\$

Python 2 (147 bytes)

def x(s):
 q=int;c=10;o=q(s[-1])+1;l=[]
 for i in map(str,s)[::-1]:
    n=q(i,c)
    while o<=n:
        c-=1;n=q(i,c)
        if 3>c:return 0
    l=[c]+l;o=n
 return l

Call the function x with a list of the ints.

Example:

print x([12,11,10])

prints

[6, 8, 10]
\$\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.