Mixed Base-Konvertierung

12

Hintergrund

Die meisten Leute hier sollten mit mehreren Basissystemen vertraut sein: dezimal, binär, hexadezimal, oktal. ZB im Hexadezimalsystem würde die Zahl 12345 16 darstellen

1*16^4 + 2*16^3 + 3*16^2 + 4*16^1 + 5*16^0

Beachten Sie, dass wir normalerweise nicht erwarten, dass sich die Basis (hier 16) von Ziffer zu Ziffer ändert.

Eine Verallgemeinerung dieser üblichen Positionssysteme ermöglicht es Ihnen, für jede Ziffer eine andere numerische Basis zu verwenden. Wenn wir beispielsweise zwischen Dezimal- und Binärsystem wechseln würden (beginnend mit der Basis 10 in der niedrigstwertigen Ziffer), würde dies die Zahl 190315 [2,10] darstellen

1*10*2*10*2*10 + 9*2*10*2*10 + 0*10*2*10 + 3*2*10 + 1*10 + 5 = 7675

Wir bezeichnen diese Basis als [2,10]. Die Basis ganz rechts entspricht der niedrigstwertigen Ziffer. Dann gehen Sie durch die Basen (nach links), während Sie durch die Ziffern (nach links) gehen, und wickeln sich um, wenn es mehr Ziffern als Basen gibt.

Weitere Informationen finden Sie in Wikipedia .

Die Herausforderung

Schreiben Sie ein Programm oder eine Funktion, die anhand einer Liste von Ziffern, Deiner Eingabe- Iund einer Ausgabebasis Odie Ganzzahl, die durch dargestellt wird, Dvon Basis Izu Basis konvertiert O. Sie können Eingaben über STDIN, ARGV oder Funktionsargumente vornehmen und das Ergebnis entweder zurückgeben oder an STDOUT ausgeben.

Sie können annehmen:

  • dass die Zahlen in Iund Oalle größer sind als 1.
  • die Iund Osind nicht leer.
  • dass die eingegebene Nummer in der angegebenen Basis gültig ist (dh keine Ziffer größer als die Basis).

Dkönnte leer sein (darstellen 0) oder führende Nullen haben. Ihre Ausgabe sollte keine führenden Nullen enthalten. Insbesondere ein Ergebnis darstellen0 als leere Liste zurückgegeben werden.

Sie dürfen keine integrierten oder Basis-Konvertierungsfunktionen von Drittanbietern verwenden.

Dies ist Codegolf, die kürzeste Antwort (in Bytes) gewinnt.

Beispiele

D               I                  O        Result
[1,0,0]         [10]               [2]      [1,1,0,0,1,0,0]
[1,0,0]         [2]                [10]     [4]
[1,9,0,3,1,5]   [2,10]             [10]     [7,6,7,5]
[1,9,0,3,1,5]   [2,10]             [4,3,2]  [2,0,1,1,0,1,3,0,1]
[52,0,0,0,0]    [100,7,24,60,60]   [10]     [3,1,4,4,9,6,0,0]
[0,2,10]        [2,4,8,16]         [42]     [1,0]
[]              [123,456]          [13]     []
[0,0]           [123,456]          [13]     []
Martin Ender
quelle
Darf ich eine unendliche Liste als Basisbeschreibung benötigen oder muss ich sie selbst infinitifizieren?
John Dvorak
@JanDvorak Sie meinen, wenn Sie damit rechnen können, dass die Basislisten bereits eine ausreichende Anzahl von Wiederholungen aufweisen, um alle Ziffern abzudecken? Nein, du musst dich umwickeln oder wiederholen.
Martin Ender
Ich gehe davon aus, dass eine leere Liste als Basis UB ist, aber können wir davon ausgehen, dass die Liste der Ziffern nicht leer ist? Wie lautet die Richtlinie für nachgestellte Nullen?
John Dvorak
Ich habe nämlich nichts gegen eine leere Liste für Eingaben, aber ich würde gerne produzieren, []wenn die Eingabe ist[0]
John Dvorak
Darf ich eine Liste von Ziffern in umgekehrter Reihenfolge anfordern und vorlegen (LSD zuerst)?
John Dvorak

Antworten:

6

CJam, 45

q~_,@m>0@{@(:T+@T*@+}/\;La{\)_@+@@md@@j@+}jp;

Endlich fand ich eine gute Verwendung von j.

Wie es funktioniert

Long ArrayList Block jFührt den Block aus, der eine Ganzzahl als Parameter verwendet, und Long jruft diesen Block im Block rekursiv auf. Außerdem werden die vom Block zurückgegebenen Werte in einem internen Array gespeichert, das vom Array-Parameter initialisiert wird. Der Block wird nicht ausgeführt, wenn sich die Eingabe bereits im Array befindet, und stattdessen wird der Wert im Array zurückgegeben.

Wenn ich es also mit einem Array eines leeren Arrays initialisiere, wird das leere Array für die Eingabe 0 zurückgegeben und der Block wird für jede andere Eingabe ausgeführt.

q~_,@m>0@{@(:T+@T*@+}/\;     " See below. Stack: O decoded-D ";
La                           " Initialized the value with input 0 as empty list. ";
{
  \)_@+@@md@@                " See below. Stack: remainder O quotient ";
  j                          " Call this block recursively except when the same quotient has
                               appeared before, which is impossible except the 0.
                               Stack: remainder O returned_list ";
  @+                         " Append the remainder to the list. ";
}j
p;                           " Format and output, and discard O. ";

CJam, 49 48

q~_,@m>0@{@(:T+@T*@+}/\;{\)_@+@@md@@}h;;_{}?]W%`

Eingabe sollte sein O I D.

Beispiele:

$ while read; do <<<$REPLY ./cjam-0.6.2.jar <(echo 'q~_,@m>0@{@(:T+@T*@+}/\;{\)_@+@@md@@}h;;_{}?]W%`');echo; done
[2] [10] [1 0 0]
[10] [2] [1 0 0]
[10] [2 10] [1 9 0 3 1 5]
[4 3 2] [2 10] [1 9 0 3 1 5]
[10] [100 7 24 60 60] [52 0 0 0 0]
[42] [2 4 8 16] [0 2 10]
[13] [123 456] []
[13] [123 456] [0 0]
[1 1 0 0 1 0 0]
[4]
[7 6 7 5]
[2 0 1 1 0 1 3 0 1]
[3 1 4 4 9 6 0 0]
[1 0]
""
""

Wie es funktioniert

q~           “ Read the input and evaluate. ";
_,@m>        " Rotate I to the right by the length of D. ";
0@{          " For each item in D, with the result initialized to 0: ";
  @(:T+      " Rotate I to the left, and set the original first item to T. ";
  @T*@+      " Calculate result * T + current. ";
}/
\;           " Discard I. ";
{            " Do: ";
  \)_@+      " Rotate O to the right, and get a copy of the original last item. ";
  @@md       " Calculate divmod. ";
  @@         " Move O and the quotient to the top of the stack. ";
}h           " ...while the quotient is not 0. ";
;;           " Discard O and the last 0. ";
_{}?         " If the last item is still 0, discard it. ";
]W%          " Collect into an array and reverse. ";
`            " Turn the array into its string representation. ";
jimmy23013
quelle
Ich muss aufhören, Array-Rotation zu verwenden, nur weil CJam es hat ... Dieser _{}?Trick ist wirklich ordentlich.
Dennis
@sudo {}e|ist das gleiche.
Jimmy23013
Würde es Ihnen etwas ausmachen, eine Erklärung für die verwendete Version hinzuzufügen j? :)
Martin Ender
@ MartinBüttner Fertig.
Jimmy23013
3

CJam, 62 61 59 57 Bytes

q~Wf%~UX@{1$*@+\@(+_W=@*@\}/;\;{\(+_W=@\md@@}h;;]W%_0=!>p

Liest die Eingabearrays [O I D]ab STDIN. Probieren Sie es online aus.

Wie es funktioniert

q~         " Read from STDIN and evaluate the input. Result: [O I D]                      ";
Wf%~       " Reverse each of the three arrays and dump them on the stack.                 ";
UX@        " Push U (0) and X (1); rotate D on top of both.                               ";
{          " For each N in D:                                                             ";
  1$*      "   N *= X                                                                     ";
  @+       "   U += N                                                                     ";
  \@(+     "   I := I[1:] + I[:1]                                                         ";
  _W=@*    "   X *= I[-1]                                                                 ";
  @\       "   ( U I X ) ↦ ( I U X )                                                      ";
}/         "                                                                              ";
;\;        " Discard I and X.                                                             ";
{          " R := []; Do:                                                                 ";
  \(+      "   O := O[1:] + O[:1]                                                         ";
  _W=@\md  "   R += [U / O[-1]], U %= O[-1]                                               ";
  @@       "   ( O U R[-1] ) ↦ ( R[-1] O U )                                              ";
}/         " While U                                                                      ";
;;]        " Discard U and O.                                                             ";
W%         " Reverse R.                                                                   ";
_0=!>      " Execute R := R[!R[0]:] to remove a potential leading zero.                   ";
p          " Print a string presentation of R.                                            ";

Testfälle

$ cjam mixed-base.cjam <<< '[ [2]     [10]             [1 0 0]       ]'
[1 1 0 0 1 0 0]
$ cjam mixed-base.cjam <<< '[ [10]    [2]              [1 0 0]       ]'
[4]
$ cjam mixed-base.cjam <<< '[ [10]    [2 10]           [1 9 0 3 1 5] ]'
[7 6 7 5]
$ cjam mixed-base.cjam <<< '[ [4 3 2] [2 10]           [1 9 0 3 1 5] ]'
[2 0 1 1 0 1 3 0 1]
$ cjam mixed-base.cjam <<< '[ [10]    [100 7 24 60 60] [52 0 0 0 0]  ]'
[3 1 4 4 9 6 0 0]
$ cjam mixed-base.cjam <<< '[ [42]    [2 4 8 16]       [0 2 10]      ]'
[1 0]
$ cjam mixed-base.cjam <<< '[ [13]    [123 456]        []            ]'
""
$ cjam mixed-base.cjam <<< '[ [13]    [123 456]        [0 0]         ]'
""

Beachten Sie, dass leere Zeichenfolgen und leere Arrays sind nicht zu unterscheiden CJam, so []pdruckt "".

Dennis
quelle
4
D: OMG niemals ein 62 Byte CJam Programm gesehen
Optimizer
@Optimizer Dies ist wahrscheinlich meine längste CJam-Einsendung.
Esolanging Fruit
@Dennis Das war doch kein Code-Golf , oder?
Esolanging Fruit
@ Challenger5 War es nicht, aber ich bezweifle, dass eine Golfversion kürzer als 200 Bytes wäre.
Dennis
2

Python 2 - 318

from operator import *
d,i,o=input()
c=len
def p(l):return reduce(mul,l,1)
n=sum(x[1]*p((i[-x[0]%c(i)-1:]+x[0]/c(i)*i)[1:]) for x in enumerate(d[::-1]))
r=[]
j=1
t=[]
k=c(o)
while p(t)*max(o)<=n:t=(o[-j%k-1:]+j/k*o)[1:];j+=1
while j:j-=1;t=(o[-j%k-1:]+j/k*o)[1:];r+=[n/p(t)];n%=p(t)
print (r if r[0] else [])

Ich habe die Reihenfolge der Argumente versehentlich durcheinander gebracht, also musste ich sie umkehren. Ich werde am Slice-Fu arbeiten, damit die Listen später in die andere Richtung funktionieren. Ich habe bereits meine gesamte Mittagspause verschwendet: p

Fest

FryAmTheEggman
quelle
Sag nicht "Verschwenden";)
Martin Ender
Sie sollten in der Lage sein, bis zu 286 Bytes Golf zu spielen: repl.it/JbIk
Zacharý
@ Zacharý Dies war mein erster Golf, ich denke, ich bin mir sicher, dass er viel kürzer sein kann! Die Antwort von Feersum zeigt das ganz gut, denke ich. Wenn Sie möchten, können Sie diese Antwort bearbeiten, aber ich fürchte, ich bin nicht besonders motiviert, sie zu verbessern.
FryAmTheEggman
2

APL, 78

{1↓(⊃1⌷⍺)({t←⍺[(⍴⍺)|⍴⍵]
(⌊0⌷⍵÷t)(t|0⌷⍵),1↓⍵}⍣{0=0⌷⍵}),+/(0,⍵)×⌽×\1,(⍴⍵)⍴⌽⊃0⌷⍺}

Beispiele:

f←{1↓(⊃1⌷⍺)({t←⍺[(⍴⍺)|⍴⍵]
  (⌊0⌷⍵÷t)(t|0⌷⍵),1↓⍵}⍣{0=0⌷⍵}),+/(0,⍵)×⌽×\1,(⍴⍵)⍴⌽⊃0⌷⍺}
(,10)(,2) f 1 0 0
1 1 0 0 1 0 0
(,2)(,10) f 1 0 0
4
(2 10)(,10) f 1 9 0 3 1 5
7 6 7 5
(2 10)(4 3 2) f 1 9 0 3 1 5
2 0 1 1 0 1 3 0 1
(100 7 24 60 60)(,10) f 52 0 0 0 0
3 1 4 4 9 6 0 0
(2 4 8 16)(,42) f 0 2 10
1 0
(123 456)(,13) f ⍬

⍴(123 456)(,13) f ⍬
0
(123 456)(,13) f 0 0

⍴(123 456)(,13) f 0 0
0
jimmy23013
quelle
Nur für die Allgemeinbildung - mit eingebautem Code: {{⍵↓⍨1⍳⍨×⍵}(99⍴⎕)⊤⍵⊥⍨⎕⍴⍨⍴⍵}Nimmt D als richtiges Argument und fragt dann nach I und O.
Adám
2

Python 2 - 122

Sehr unkompliziert, es ist uns nicht gelungen, spezielle Golf-Tricks zu finden.

def f(D,I,O):
 n,i,l=0,-len(D),[]
 for d in D:n=n*I[i%len(I)]+d;i+=1
 while n:i-=1;b=O[i%len(O)];l=[n%b]+l;n/=b
 return l

Ungolfed:

def f(D,I,O):
    n = 0
    for i in range(len(D)):
        dn = len(D) - i
        n = n * I[-dn % len(I)] + D[i]
    l = []
    i = 0
    while n:
        i -= 1
        b = O[i%len(O)]
        l = [n%b] + l
        n /= b
    return l

Edit: 116-Byte-Programmversion dank FryAmTheEggman

D,I,O=input()
n,i,l=0,-len(D),[]
for d in D:n=n*I[i%len(I)]+d;i+=1
while n:i-=1;b=O[i%len(O)];l=[n%b]+l;n/=b
print l

Diese Version akzeptiert kommagetrennte Eingaben, z [1,9,0,3,1,5], [2,10], [10]

Feersum
quelle
@FryAmTheEggman Ich bin mir nicht sicher, wie Eingaben in Anführungszeichen akzeptiert werden können, aber das Trennen der Arrays durch Kommas funktioniert.
Feersum
1

k2 - 83 74 char

Funktion mit einem Argument. Dies war für K viel besser geeignet als für J, weshalb ich J nicht benutze. Es wäre nur eine Ladung Box- / Unbox-Müll, und das will niemand. Dies ist im k2-Dialekt (erfordert möglicherweise einige Anpassungen, um in der Open Source-Implementierung Kona zu funktionieren), aber ich werde dies in k4 ändern, wenn ich es dort kürzer spielen kann.

{:[#x@:|&~&\~x;|*{x 1}.[{_(x,y!*z;y%*z;1!z)}]/(();+/x*1*\(1-#x)#y;|z);()]}

Ich werde darauf hinweisen, dass ich mich hier für die Wählerisch- keit einsetze und sage, dass eine Artikelliste als solche eingegeben werden muss. ,2ist eine Liste eines Elements, wobei dieses Element der Skalar ist 2. Oft sind Skalare und Listen mit einem Element austauschbar, aber es gibt eine Logik in diesem Golf, die auf der Annahme von Listenargumenten beruht.

Um den Golf zu erklären, werde ich ihn in zwei Teile aufteilen. Fist der Golf, List die Hauptschleife, die die Ausgabe berechnet. Der genaue Mechanismus der Schleife besteht darin, dass diese Lwiederholt auf ihre Argumente angewendet wird, bis das zweite Argument Null ist. Dann wird dieses Ergebnis zurückgegeben. (Dies ist der .[L]/Teil.)

L: {_(x,y!*z;y%*z;1!z)}
F: {:[#x@:|&~&\~x;|*{x 1}.[L]/(();+/x*1*\(1-#x)#y;|z);()]}

Durch Explosion:

{_(x,y!*z;y%*z;1!z)}  /function, args x y z
  (      ;    ;   )   / update each arg as follows:
               1!z    /  new z: rotate z left
            *z        /  head of z (current base digit)
          y%          /  y divided by that
 _                    /  new y: floor of that
     y!*z             /  y modulo head of z
   x,                 /  new x: append that to old x

{:[#x@:|&~&\~x;|*{x 1}.[L]/(();+/x*1*\(1-#x)#y;|z);()]}  /function, args x y z
            ~x                                           /find the 0s in x
          &\                                             /find leading zeros
        &~                                               /indices of digits that aren't
    x@ |                                                 /those items from x, reverse order
    x :                                                  /assign to x
 :[#          ;                                      ]   /if length is 0:
                                                   ()    / return empty list
                                                  ;      /else:
                      .[L]/                              / loop L repeatedly
                 {x 1}                                   / until y = 0
                           (  ;               ;  )       / starting with args:
                            ()                           /  Lx: empty list
                                       1-#x              /  number of input digits, minus 1
                                      (    )#y           /  cyclically extend base leftward
                                   1*\                   /  running product, start at 1
                                 x*                      /  multiply digits by these
                               +/                        /  Ly: sum of the above
                                               |z        /  Lz: out base, reverse order
               |*                                        / first elem of result, reversed

In Aktion:

  {:[#x@:|&~&\~x;|*{x 1}.[{_(x,y!*z;y%*z;1!z)}]/(();+/x*1*\(1-#x)#y;|z);()]}[1 0 0; ,10; ,2]
1 1 0 0 1 0 0
  f:{:[#x@:|&~&\~x;|*{x 1}.[{_(x,y!*z;y%*z;1!z)}]/(();+/x*1*\(1-#x)#y;|z);()]}
  f[1 0 0; ,2; ,10]
,4
  f .' ((1 9 0 3 1 5; 2 10;           ,10)  /f apply each
>       (1 9 0 3 1 5; 2 10;           4 3 2)
>       (52 0 0 0 0;  100 7 24 60 60; ,10)
>       (0 2 10;      2 4 8 16;       ,42)
>       (();          123 456;        ,13)
>       (0 0;         123 456;        ,13))
(7 6 7 5
 2 0 1 1 0 1 3 0 1
 3 1 4 4 9 6 0 0
 1 0
 ()
 ())
algorithmshark
quelle
0

Perl 6 , 67 Bytes

{[R,] [+]([R,](@^a)Z*1,|[\*] |[R,](@^b)xx*).polymod: |[R,](@^c)xx*}

Versuch es

Erweitert:

{  # bare block lambda with placeholder parameters @a,@b,@c

  [R,]    # reduce the following using reverse meta op 「R」 combined with 「,」 op
          # (shorter than 「reverse」)

    [+](  # sum

        [R,](@^a) # reverse of first argument

      Z[*]        # zipped using &infix:<*> with the following

        1,
        |                    # slip the following in (flattens)
          [\*]               # triangle reduce

            |[R,](@^b) xx*   # reverse of second argument repeated infinitely
    )

    .polymod: |[R,](@^c) xx* # moduli the reverse of third argument repeated
}

Falls Sie sich nicht sicher sind, was die Dreiecksreduzierung bewirkt:

[\*] 1,2,3,4,5
# 1, 1*2, 1*2*3, 1*2*3*4, 1*2*3*4*5
# 1,   2,     6,      24,       120

Wenn ich die Eingänge vertauschen und umgekehrt ausgeben könnte, wären es 47 Bytes.

{[+](@^a Z*1,|[\*] |@^b xx*).polymod: |@^c xx*}

Versuch es

Brad Gilbert b2gills
quelle