23
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ 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? \$\endgroup\$ – DavidC Sep 2 '12 at 22:19
  • \$\begingroup\$ Interesting question... 1:5 -> 8:40 and 10:1 -> 40:8 make sense but the others not so much. \$\endgroup\$ – Rob Sep 2 '12 at 23:25
  • \$\begingroup\$ @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. \$\endgroup\$ – Keith Randall Sep 2 '12 at 23:51
  • \$\begingroup\$ @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. \$\endgroup\$ – Keith Randall Sep 2 '12 at 23:53
  • 2
    \$\begingroup\$ @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. \$\endgroup\$ – Keith Randall Sep 3 '12 at 15:55
4
\$\begingroup\$

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*8`for 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.

\$\endgroup\$
  • 1
    \$\begingroup\$ <1 can replace ==0. Also, if b:a=...return a can be return b and...or a. \$\endgroup\$ – ugoren Sep 3 '12 at 11:32
  • \$\begingroup\$ Doesn't work for, e.g., 23:12. \$\endgroup\$ – Keith Randall Sep 3 '12 at 20:32
  • \$\begingroup\$ 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. \$\endgroup\$ – daniero Sep 4 '12 at 6:49
  • \$\begingroup\$ There you go; I think this one works as expected. Even made it smaller :) \$\endgroup\$ – daniero Sep 4 '12 at 16:56
  • \$\begingroup\$ Looks pretty good, but it isn't optimal. 6:15 can be done with 16:40 but your code returns 24:40 16:24. \$\endgroup\$ – Keith Randall Sep 5 '12 at 4:30
4
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ You can save 9 chars by removing $1:$2 -> , it is not required in the output. \$\endgroup\$ – DaveRandom Sep 6 '12 at 9:00
  • \$\begingroup\$ Oh, I misread the spec. Thanks. \$\endgroup\$ – Patrick B. Sep 6 '12 at 9:20
  • \$\begingroup\$ You can reduce statements like $a[$_]=8 if!$a[$_]; to $a[$_]||=8; \$\endgroup\$ – ardnew Sep 10 '12 at 14:12
  • \$\begingroup\$ Newlines count as one character. \$\endgroup\$ – Timtech Jan 4 '14 at 18:31
  • \$\begingroup\$ The first line can be abbreviated to ($v,$n)=split/:|\s/,<>; (untested). \$\endgroup\$ – msh210 Jan 6 '16 at 20:33
2
\$\begingroup\$

swi-prolog, 324 250 248 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.
\$\endgroup\$
2
\$\begingroup\$

C, 246 216 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.

\$\endgroup\$
2
+100
\$\begingroup\$

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

\$\endgroup\$
0
\$\begingroup\$

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(" ");
}
\$\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.