# Lego gear ratios

I'm building a giant lego robot and I need to generate some particular gear ratios using a set of gears. I have lots of gears with the common lego gear sizes: 8, 16, 24, or 40 teeth. Write a program I can use where I input a gearing ratio and the program tells me what combination of gears I should use to get the requested ratio.

The input ratio will be specified on standard input (or your language's equivalent) with two integers separated by a colon. A ratio of a:b means that the output shaft should turn a/b times as fast as the input shaft.

The output to standard output should be a single line containing a space-separated list of gear ratios, in the form of x:y where x is the size of the gear on the input shaft and y is the size of the gear on the output shaft. You must use the minimum possible number of gears for the given ratio. Each x and y must be one of 8,16,24,40.

examples:

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


If the desired gear ratio is impossible, print "IMPOSSIBLE". If no gears are required, print the empty string.

This is code golf, shortest answer wins.

• Aren't the ratio of teeth inversely proportional to the angular velocity? So, for example if the desired input output velocity is 1:5, shouldn't the ratio be 40:8 instead of 8:40? Or is the left-hand ratio the effective gear teeth to actual gear teeth ratio you want? – DavidC Sep 2 '12 at 22:19
• Interesting question... 1:5 -> 8:40 and 10:1 -> 40:8 make sense but the others not so much. – Rob Sep 2 '12 at 23:25
• @DavidCarraher: I guess you can define it either way. I tried to be internally consistent. 1:5 means the output shaft turns 5 times slower, and an 8 tooth gear on the input and a 40 tooth gear on the output makes that happen. – Keith Randall Sep 2 '12 at 23:51
• @MikeDtrick: well, 10:1 -> 40:8 16:8, not what you said. What about the others confuses you? 9:4 is implemented doing 3:2 twice. 3:2 is implemented using 24:16. – Keith Randall Sep 2 '12 at 23:53
• @MikeDtrick: Yes to your first question. To get 10:1 you can do 5:1 (using 40 teeth / 8 teeth) and then 2:1 (using 16 teeth / 8 teeth). 7:7 is the same as 1:1, so it requires no gears to implement. – Keith Randall Sep 3 '12 at 15:55

# Python - 204

Ok, I'll go first:

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*8for a,b in zip(x,y)if a!=b),'IMPOSSIBLE'][i!=j]

edit:

To 'optimize' the output, this can be added before the print statement,

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


bringing the total up to 266 characters, I believe.

• <1 can replace ==0. Also, if b:a=...return a can be return b and...or a. – ugoren Sep 3 '12 at 11:32
• Doesn't work for, e.g., 23:12. – Keith Randall Sep 3 '12 at 20:32
• Well spotted. It goes through since 12 is dividable. Adding elif i!=1:return[] to the original solves the problem but introduces another one. $python gears.py <<< 21:28 => 24:16.. I'm gonna look into it. Looks like the problem wasn't so simple after all :D I Think the code has to be even longer, or I need another approach. – daniero Sep 4 '12 at 6:49 • There you go; I think this one works as expected. Even made it smaller :) – daniero Sep 4 '12 at 16:56 • Looks pretty good, but it isn't optimal. 6:15 can be done with 16:40 but your code returns 24:40 16:24. – Keith Randall Sep 5 '12 at 4:30 # Perl - 310 306 294 288 272 I'm a little rusty with perl and never did a code-golf... but no excuses. Char-count is without line-breaks. Using 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"  I'm looking forward to critics and hints. It's not so easy to find tips and tricks for code-golf (in perl). • You can save 9 chars by removing $1:$2 -> , it is not required in the output. – DaveRandom Sep 6 '12 at 9:00 • Oh, I misread the spec. Thanks. – Patrick B. Sep 6 '12 at 9:20 • You can reduce statements like $a[$_]=8 if!$a[$_]; to $a[$_]||=8; – ardnew Sep 10 '12 at 14:12 • Newlines count as one character. – Timtech Jan 4 '14 at 18:31 • The first line can be abbreviated to ($v,\$n)=split/:|\s/,<>; (untested). – msh210 Jan 6 '16 at 20:33

# swi-prolog, 324250248 204 bytes

Prolog does pretty well at solving a problem like this.

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.


Input is passed as a term parameter to predicate m. Output is written to stdout. Sorry about the trailing 'true'; that's just the interpreter's way of letting me know everything was fine.

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

?- m(7:7).
true.

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


# C, 246216 213 bytes

In a (futile) attempt to beat my own Prolog solution, I completely rewrote the C solution.

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);}


My original C solution (246 bytes):

#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);}


It was a nice exercise to prove it can be done without building lists.

## Pyth, 101 bytes

### (Almost certainly non-competing in contest as uses a language newer than sep/2012)

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


An implementation of @daniero' python answer but semi-optimised for 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


Try it here

Or test every case

## 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 )


One of my longest golfs, so I must have done something wrong... 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(" ");
}