Ich baue einen riesigen Legoroboter und muss einige bestimmte Übersetzungsverhältnisse mithilfe eines Satzes von Zahnrädern erzeugen. Ich habe viele Zahnräder mit den üblichen Lego-Zahnradgrößen: 8, 16, 24 oder 40 Zähne. Schreiben Sie ein Programm, das ich verwenden kann, indem ich ein Übersetzungsverhältnis eingebe, und das Programm sagt mir, welche Kombination von Zahnrädern ich verwenden soll, um das angeforderte Übersetzungsverhältnis zu erhalten.

Das Eingabeverhältnis wird in der Standardeingabe (oder in der Entsprechung Ihrer Sprache) mit zwei durch einen Doppelpunkt getrennten Ganzzahlen angegeben. Ein Verhältnis von a:bbedeutet, dass sich die Abtriebswelle a/bso schnell drehen soll wie die Antriebswelle .

Der Ausgang auf der Standardausgabe sollte eine einzige Zeile eine durch Leerzeichen getrennte Liste von Übersetzungsverhältnissen enthält, in Form sein , x:ywo xdie Größe des Getriebes auf der Antriebswelle und yist die Größe des Getriebes auf der Ausgangswelle. Sie müssen die minimal mögliche Anzahl von Gängen für die angegebene Übersetzung verwenden. Jeder xund ymuss einer von 8,16,24,40.

Beispiele:

1:5 -> 8:40
10:1 -> 40:8 16:8
9:4 -> 24:16 24:16
7:1 -> IMPOSSIBLE
7:7 ->
6:15 -> 16:40

Wenn das gewünschte Übersetzungsverhältnis nicht möglich ist, drucken Sie "UNMÖGLICH". Wenn keine Zahnräder erforderlich sind, drucken Sie die leere Zeichenfolge.

Dies ist Code Golf, die kürzeste Antwort gewinnt.

Python - 204

Ok, ich gehe zuerst:

def p(n,a=[1]*9):
 n=int(n)
 for i in(2,3,5):
    while n%i<1:n/=i;a=[i]+a
 return a,n
(x,i),(y,j)=map(p,raw_input().split(':'))
print[' '.join(`a*8`+':'+`b*8`for a,b in zip(x,y)if a!=b),'IMPOSSIBLE'][i!=j]

Um die Ausgabe zu optimieren, kann dies vor der printAnweisung hinzugefügt werden.

for e in x:
 if e in y:x.remove(e);y.remove(e)

Ich glaube , das sind insgesamt 266 Zeichen .

Perl - 310 306 294 288 272

Ich bin ein bisschen verrostet mit Perl und habe noch nie Code-Golf gespielt ... aber keine Ausreden. Die Anzahl der Zeichen erfolgt ohne Zeilenumbrüche. Verwendung von Perl v5.14.2.

($v,$n)=<>=~/(.+):(.+)/;
($x,$y)=($v,$n);($x,$y)=($y,$x%$y)while$y;
sub f{$p=shift;$p/=$x;for(5,3,2){
while(!($p%$_)){$p/=$_;push@_,$_*8}}
$o="IMPOSSIBLE"if$p!=1;
@_}
@a=f($v);@b=f($n);
if(!$o){for(0..($#b>$#a?$#b:$#a)){
$a[$_]||=8;
$b[$_]||=8;
push@_,"$a[$_]:$b[$_]"}}
print"$o@_\n"

Ich freue mich auf Kritik und Hinweise. Es ist nicht so einfach, Tipps und Tricks für Code-Golf (in Perl) zu finden.

swi-prolog, 324 250 248 204 bytes

Prolog kann ein solches Problem ziemlich gut lösen.

m(P):-(g(P,L),!;L='IMPOSSIBLE'),write(L).
g(A:A,''):-!.
g(A:B,L):-A/C/X,C>1,B/C/Y,!,g(X:Y,L);A/C/X,!,B/D/Y,C*D>1,g(X:Y,T),format(atom(L),'~D:~D ~a',[C*8,D*8,T]).
X/Y/Z:-(Y=5;Y=3;Y=2;Y=1),Z is X//Y,Y*Z>=X.

Die Eingabe wird als zu prädizierender Begriffsparameter übergeben m. Die Ausgabe wird nach stdout geschrieben. Entschuldigung für das nachfolgende 'true'; Das ist nur die Art des Dolmetschers, mir mitzuteilen, dass alles in Ordnung war.

?- m(54:20).
24:40 24:16 24:8 
true.

?- m(7:7).
true.

?- m(7:1).
IMPOSSIBLE
true.

C 246 216 213 Bytes

In einem (vergeblichen) Versuch, meine eigene Prolog-Lösung zu schlagen, habe ich die C-Lösung komplett neu geschrieben.

b,c,d;f(a,b,p){while(c=a%5?a%3?a%2?1:2:3:5,d=b%5?b%3?b%2?1:2:3:5,c*d>1)c<2|b%c?d<2|a%d?p&&printf("%d:%d ",8*c,8*d):(c=d):(d=c),a/=c,b/=d;c=a-b;}main(a){scanf("%d:%d",&a,&b);f(a,b,0);c?puts("IMPOSSIBLE"):f(a,b,1);}

Meine ursprüngliche C-Lösung (246 Byte):

#define f(c,d) for(;a%d<1;a/=d)c++;for(;b%d<1;b/=d)c--;
b,x,y,z;main(a){scanf("%d:%d",&a,&b);f(x,2)f(y,3)f(z,5)if(a-b)puts("IMPOSSIBLE");else
while((a=x>0?--x,2:y>0?--y,3:z>0?--z,5:1)-(b=x<0?++x,2:y<0?++y,3:z<0?++z,5:1))printf("%d:%d ",a*8,b*8);}

Es war eine schöne Übung, um zu beweisen, dass es ohne das Erstellen von Listen möglich ist.

Pyth, 101 Bytes

(Mit ziemlicher Sicherheit keine Teilnahme am Wettbewerb, da eine neuere Sprache als September / 2012 verwendet wird.)

D'HJH=Y[)VP30W!%JN=/JN=Y+NY))R,YJ;IneKhm'vdcz\:J"IMPOSSIBLE").?V.t,.-Y.-hK=J.-hKYJ1In.*Npj\:m*8d_Np\ 

Eine Implementierung von @daniero 'Python-Antwort, jedoch halboptimiert für Pyth.

D'H                               - Define a function (') which takes an argument, H.
   JH                             - J = H (H can't be changed in the function)
     =Y[)                         - Y = []
         V                        - For N in ...
          P30                     - Prime factors of 30 (2,3,5)
             W!%JN                - While not J%N
                  =/JN            - J /= N
                      =Y+NY       - Y = N + Y
                           ))R,YJ - To start of function, return [Y,J]

ENDFUNCTION

If 
         cz\:  - Split the input by the ':'
     m'vd      - ['(eval(d)) for d in ^]
   Kh          - Set K to the first element of the map (before the :)
  e            - The second returned value
             J - The second returned value after the : (The variables are globals)
 n             - Are not equal

Then 
"IMPOSSIBLE" - Print "IMPOSSIBLE"

Else
V                                      - For N in
 .t                1                   - transpose, padded with 1's
             .-hKY                     - 1st function first return - 2nd function first return
           =J                          - Set this to J
       .-hK                            - 1st function first return - ^
    .-Y                                - 2nd function first return - ^
   ,              J                    - [^, J]
                                         (Effectively XOR the 2 lists with each other)
                    I                  - If
                     n.*N              - __ne__(*N) (if n[0]!=n[1])
                         pj\:m*8d_N    - print ":".join([`d*8` for d in reversed(N)])
                                   p\  - print a space seperator

Probieren Sie es hier aus

Oder testen Sie jeden Fall

ES6, 230 Bytes

x=>([a,b]=x.split`:`,f=(x,y)=>y?f(y,x%y):x,g=f(a,b),d=[],a/=g,f=x=>{while(!(a%x))a/=x,d.push(x*8)},[5,3,2].map(f),c=d,d=[],a*=b/g,[5,3,2].map(f),a>1?'IMPOSSIBLE':(c.length<d.length?d:c).map((_,i)=>(c[i]||8)+':'+(d[i]||8)).join` `)

Einer meiner längsten Golfplätze, also muss ich etwas falsch gemacht haben ... Ungolfed:

x => {
    [a, b] = x.split(":");
    f = (x, y) => y ? f(y, x % y) : x; // GCD
    g = f(a, b);
    f = x => {
        r = [];
        while (!(x % 5)) { x /= 5; r.push(5); }
        while (!(x % 3)) { x /= 3; r.push(3); }
        while (!(x % 2)) { x /= 2; r.push(2); }
        if (x > 1) throw "IMPOSSIBLE!";
        return r;
    }
    c = f(a);
    d = f(b);
    r = [];
    for (i = 0; c[i] || d[i]; i++) {
        if (!c[i]) c[i] = 8;
        if (!d[i]) d[i] = 8;
        r[i] = c[i] + ":" + d[i];
    }
    return r.join(" ");
}