Aufstieg, Abfolge, Aufstieg

19

Wir haben eine streng zunehmende Folge von nicht negativen ganzen Zahlen, wie:

12 11 10

Warten! Diese Reihenfolge nimmt nicht unbedingt zu, oder? Nun, die Zahlen sind in verschiedenen Basen geschrieben. Die kleinstmögliche Basis ist 2, die größte ist 10.

Die Aufgabe besteht darin, zu erraten, dass jede Zahl so geschrieben ist, dass:

  • die Reihenfolge nimmt strikt zu,
  • Die Summe der Basen wird maximiert.

Die Lösung für die Stichprobe lautet beispielsweise:

6 8 10

weil unter diesen Basen die Sequenz 8 9 10dezimal wird - eine streng ansteigende Sequenz, und wir sind nicht in der Lage, Basen zu finden, für die die Sequenz streng ansteigt und deren Summe größer als ist 6+8+10.

Aufgrund der zweiten Einschränkung ist eine Lösung 3 5 7nicht zufriedenstellend: Trotz der Tatsache, dass die Sequenz 5 6 7unter diesen Basen liegt, müssen wir die Basensumme maximieren und 3+5+7 < 6+8+10.

Wenn es unter keinen 2<=b<=10Umständen möglich ist, dass die Reihe streng ansteigt, zum Beispiel:

102 10000 10

Single

0

sollte ausgegeben werden.

Die Eingabesequenz kann so übergeben werden, wie es für Ihre Lösung am bequemsten ist (Standardeingabe / Befehlszeilenparameter / Funktionsargumente ...).

pawel.boczarski
quelle
1
Ist 1 3 5eine aufsteigende Sequenz? Was ist 1 7 22? (in der Basis 10)
Türklinke
Ja, 1 3 5und 1 7 22beide steigen unter die Basis 10. Die Lösung für beide Fälle ist also 10 10 10, dass wir die Summe der Basen maximieren müssen, während wir sicherstellen, dass die Sequenz steigt, wenn die n-te Zahl so interpretiert wird, dass sie in die Basis gleich n geschrieben wird -ter Begriff der Lösung.
pawel.boczarski
2
@ Tennis Ja, ich meine streng steigende Reihenfolge. 1 1 1oder 3 3 4steigen nicht.
pawel.boczarski
3
Wenn Kommentare darauf hindeuten, dass die Frage falsch interpretiert werden kann, antworten Sie nicht nur in Kommentaren. Bearbeiten Sie die Frage so, dass andere keine Zeit damit verschwenden, Antworten zu schreiben, die sie für Sie anders interpretieren.
Peter Taylor
3
Und zum Thema der Mehrdeutigkeiten behauptet einer der Kommentare zu meiner Antwort, dass wir davon ausgehen sollten, dass die Zahlen in der angegebenen Basis in kanonischer Form geschrieben sind. In diesem Fall korrigieren Sie bitte den Ausdruck " Die kleinste mögliche Basis ist 2 " in " Die kleinste mögliche Basis ist eine Stelle größer als der größte Ziffernwert ".
Peter Taylor

Antworten:

13

Pyth, 31 30 29 Bytes

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

1 Byte danke an @Jakube.

Demonstration. Testgeschirr.

Die Eingabe erfolgt auf STDIN, durch Leerzeichen getrennt. Wenn eine durch Zeilenumbrüche getrennte Eingabe erlaubt ist, kann ich das Programm um 2 Bytes kürzen.

Erläuterung:

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.

Die Aufnahme 1in die Liste möglicher Basen ist sicher, da iPythons intBuilt-in 1als Basis nicht zulässig ist und daher immer einen Fehler auslöst , der abgefangen und herausgefiltert wird.

isaacg
quelle
9

CJam, 43 Bytes

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

Liest Befehlszeilenargumente und druckt ein Array.

Probieren Sie es online im CJam-Interpreter aus .

Beispiele

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

Wie es funktioniert

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).
Dennis
quelle
6

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

Wird mit einem 1d-Array-Eingang verwendet. Wenn die Funktion zugewiesen ist c, würden Sie aufrufen c([12,11,10])und es würde ausgeben [6,8,10].

Hinweis: Ich habe dec(i)den Befehl parseint verwendet. Da es sich jedoch ium einen aus einem Zeichen bestehenden Variablennamen handelt und ich nicht auf eine Komponente zugreifen muss "$i", wurde das gleiche Ergebnis erzielt .

Glen O
quelle
Sie haben hier ein paar gute Tricks. Gute Arbeit.
Alex A.
Dieser Code scheint die Basen auf eine streng abnehmende Reihenfolge unter der üblichen Ablesereihenfolge von links nach rechts zu prüfen.
pawel.boczarski
@ pawel.boczarski - Ich bin mir nicht sicher, was du meinst, aber wenn du möchtest, kann ich einige Beispiele dafür geben, was es für bestimmte Eingaben ausgibt. Zum Beispiel, wenn Sie die Funktion des Namen zuweisen c, dann c([12,11,10])Ausgaben [6,8,10], die die benötigten Basen sind.
Glen O
@ GlenO Oh, ich verstehe. Ich habe [12 11 10]stattdessen einen Zeilenvektor verwendet [12,11,10], was den unerwünschten Effekt ergab.
pawel.boczarski
@ pawel.boczarski - ah, ich verstehe. Ja, wenn Sie möchten, dass es mit Zeilenvektoren funktioniert, müssen Sie "flipud" durch "fliplr" ersetzen. In diesem Fall wird ein Zeilenvektor der Basen zurückgegeben.
Glen O
5

Julia, 259 204 183 Bytes

Habe mit Hilfe von Glen O einen Haufen gerettet.

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 + Erklärung:

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
Alex A.
quelle
OK, ein bisschen Golfen muss gemacht werden ... benutze "repr" anstelle von "string" im Map-Befehl, sie funktionieren in diesem Zusammenhang genauso und sparen zwei Bytes. Und wir können ein paar mehr sparen, indem wir einen Infix-Operator für parseint verwenden, indem wir "\ = parseint" schreiben und dann x [1] \ i anstelle von p (x [1], i) verwenden - ein Byte mehr im "\" Teil, und speichern Sie dann drei für jede Verwendung von p für eine Nettoeinsparung von 8 Bytes. Ein weiteres Byte wird durch Ersetzen von "Maximum (Ziffern (x)) durch Maximum (Ziffern (x) ...)"
Glen O
Führen Sie für eine größere Speicherung die for-Schleifen zusammen for i=M(A[1]):10,j=M(A[2]):10,k=M(A[3]):10 <code here>end;und speichern Sie acht für die abgelegten zwei end;s und acht für das Ersetzen von `for` durch ,.
Glen O
Tatsächlich können wir es für den Parseint-Teil noch besser machen. Löschen Sie die Umbenennung von parseint vollständig und verwenden Sie s=map(parseint,x,[i,j,k]), um 18 Byte im Vergleich zu Ihrer ursprünglichen Lösung und 10 Byte im Vergleich zu meinen vorherigen Verbesserungsvorschlägen zu sparen. Und anstatt s==sort(unique(s)), verwenden Sie all(diff(s).>0)weitere 3 Bytes zu speichern.
Glen O
Es kann sicherlich noch mehr getan werden, aber ich überlasse es Ihnen und versuche stattdessen, meinen eigenen Ansatz zu finden.
Glen O
Kleinere Korrekturen - Ich habe vorgeschlagen, max (...) anstelle von maximum zu verwenden, aber während ein Byte gespeichert wird, schlägt dies bei einstelligen Eingabewerten fehl, sodass Sie maximum verwenden müssen.
Glen O
4

CJam (39 Bytes)

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

Dies ist eine anonyme Funktion, die die Eingabe als Array von Dezimalzahlen auf dem Stapel verwendet und die Ausgabe als Array oder Ganzzahl 0auf dem Stapel belässt . Online-Demo .

Peter Taylor
quelle
Dies scheint auch nach der Summe der resultierenden ganzen Zahlen anstelle der Basen zu sortieren, und es hat dasselbe Problem, das meine vorherige Revision hatte ( 19kann keine Basis 9 sein).
Dennis
1
Hmm. Die Frage scheint verbessert zu werden.
Peter Taylor
@ Peter Taylor Pah, Entschuldigungen;)
Beta Decay
2

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

Rufen Sie die Funktion xmit einer Liste der Ints auf.

Beispiel:

print x([12,11,10])

druckt

[6, 8, 10]
Blau
quelle