12
\$\begingroup\$

This question already has an answer here:

Input:

A three digit number

  • from stdin or as an argument
  • not all digits are the same
  • may start with one or two zero's

Process

Order the input-digits ascending and descending to form two new numbers. Subtract the smallest from the largest. Use the difference as new input. NB: This process needs 3 digits, so 10 has to be returned, or taken care of, as 010.

Repeat this process (Kaprekar transformation) until you hit 495.

Output:
The number of steps it took to reach 495.

Example:

Input: 211

211 – 112 = 099
990 – 099 = 891 (rather than 99 - 99 = 0)
981 – 189 = 792
972 – 279 = 693
963 – 369 = 594
954 − 459 = 495

Output: 6

\$\endgroup\$

marked as duplicate by Martin Ender Nov 2 '15 at 13:14

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • \$\begingroup\$ May I assume, that the input doesn't consists of three identical digits like in 111 or 222? \$\endgroup\$ – FUZxxl Mar 5 '11 at 12:33
  • \$\begingroup\$ Yes (second bullet: not all digits are the same). \$\endgroup\$ – steenslag Mar 5 '11 at 13:06
  • 1
    \$\begingroup\$ Complete set of test cases: svn.lando.us/joey/Public/SO/CG1255/testcases.txt \$\endgroup\$ – Joey Mar 5 '11 at 19:36
  • \$\begingroup\$ Warning: in some programming languages (e.g. JavaScript), numbers starting with zeros (e.g. 077) are parsed as octals if you're not careful. \$\endgroup\$ – Joey Adams Mar 6 '11 at 3:06
  • 1
    \$\begingroup\$ @MartinBüttner how is this question about three-digit numbers a duplicate of the four-digit version? \$\endgroup\$ – Paŭlo Ebermann Feb 9 '16 at 22:25

12 Answers 12

9
\$\begingroup\$

Golfscript, 29 26 characters

.$)\0=-.5<{7\}4if-\~495=!*

Basically a mix of Joey's PS- and my Ruby-solution.

Edit: Thanks Nabb for a suggestion on how to shorten this by 3 characters.

\$\endgroup\$
21
\$\begingroup\$

Windows PowerShell, 61 65 70 72 73 82

Evil alternative approach. It becomes apparent if you desperately search for patterns in the input.

Be sure to also check out Ventero's Ruby and Golfscript solutions which use the same technique which was sort of a joined work :-)

(7..3+1..5)[($x=($a="$args")[0..2]|sort)[2]-$x[0]]*($a-ne495)

A little explanation might be in order for this, I guess. Suppose you have a number consisting of three digits. For convenience they are labeled a, b and c here with c being the largest. You then are going to subtract abc from cba.

If we picture that, we are going to get (ca − 1), 9 and (10 + a - c) as the individual digits. This will always hold, no matter the input digits. This also means that the middle digit get no say in how long the sequence will be, simply because it always is 9.

So basically the first and last digit of the sorted digits suffice in determining the length of the sequence. One can easily make a list with every conceivable combination of first and last digit (there are only 45) to search for patterns there.

As it turns out, there are at least two. Both play with the first few results of the different digits: [6 5 4 3 1 2 3 4 5]. First, taking the difference between the largest and the smallest digit and subtracting one gives the appropriate index in the aforementioned list of results. Second, interpreting the smallest and largest digit as a single number and doing modulo 11 yields the same, except that one has to prepend another 6 to the list.

\$\endgroup\$
  • 1
    \$\begingroup\$ A rare case of golfing leading to fast code. \$\endgroup\$ – steenslag Mar 6 '11 at 20:26
  • 1
    \$\begingroup\$ Accepted answer for admiration of analysis. \$\endgroup\$ – steenslag Mar 9 '11 at 0:49
11
\$\begingroup\$

J, 43 37

<:$".@(\:,'-',/:)~@":@((3$10)&#:)^:a:

Sample run (note how stripping the 3 leading chars displays a trace):

   <:$".@(\:,'-',/:)~@":@((3$10)&#:)^:a:211
6
   ".@(\:,'-',/:)~@":@((3$10)&#:)^:a:211
211 99 891 792 693 594 495
   <:$".@(\:,'-',/:)~@":@((3$10)&#:)^:a:494
1
   <:$".@(\:,'-',/:)~@":@((3$10)&#:)^:a:495
0

This version repeatedly (^:) converts to decimal ((3$10)&#:), concatenates the descending list (\:), a minus sign '-' and the ascending list (/:), and evaluates (".). Until the result is stable (a:). Then it counts the number of returned elements (<:$).

I'm as surprised as you it needs fewer characters than the table lookup variant.

\$\endgroup\$
  • \$\begingroup\$ I like how you have made the 495 implicit by stopping at a fixed point. \$\endgroup\$ – Joey Mar 8 '11 at 13:06
4
\$\begingroup\$

Python, 89 characters

n=input()
c=0
while n-495:s=''.join(sorted('%03d'%n));n=int(s[::-1])-int(s);c+=1
print c
\$\endgroup\$
4
\$\begingroup\$

J, 40

Using the Joey/Ventero approach. (go upvote them first)

(-&4`(7&-)@.(<&5)".'-'1}\:~y)-'495'-:y=.

This doesn't beat Golfscript, but I liked the idea of sorting the number, replacing the middle digit with a - and evaluating that.

\$\endgroup\$
3
\$\begingroup\$

Ruby 1.8, 64 55 52 48 characters

l=gets.bytes;i=l.max-l.min;p /495/?0:i<5?7-i:i-4

Note that the input shouldn't contain a line break.

For Ruby 1.9, the solution needs an additional space before the last colon.

  • (64 -> 55) Thanks to Joey for pointing out that the input already consists of 3 digits.
  • (55 -> 53) Thanks to steenslag for pointing out Array#minmax
  • (53 -> 52) Actually just using Array#max and Array#min directly is shorter.
  • (52 -> 48) Implicitly match a regexp against $_ to test for 495.
\$\endgroup\$
  • \$\begingroup\$ Rather amazing... is this the same trick as @Joey's evil approach? \$\endgroup\$ – steenslag Mar 5 '11 at 21:01
  • \$\begingroup\$ @steenslag: Yes, we both developed it together, kinda. \$\endgroup\$ – Joey Mar 5 '11 at 21:07
  • \$\begingroup\$ I'm by no means a math expert, but this could be a minor mathematical novelty. Can it be expanded to include four digits, or even more? \$\endgroup\$ – steenslag Mar 5 '11 at 23:25
  • \$\begingroup\$ @steenslag: There is a similar number for four digits, but I don't know whether such a formula exists. It may be likely, though I suspect in that case it would look more like (3rd and 4th digit) minus (2nd and 1st digit). Feel free to experiment, though. The discovery above was coincidental after looking at the map I created that maps sorted digits to the result :-) \$\endgroup\$ – Joey Mar 5 '11 at 23:29
3
\$\begingroup\$

Windows PowerShell, 80 79

for($a="$args";$a-495;++$i){$a=-join($x="00$a"[-1..-3]|sort)[2..0]-+-join$x}+$i

History:

  • 2011-03-05 00:27 (113) Initial attempt.
  • 2011-03-05 00:33 (107) One sort has to suffice.
  • 2011-03-05 00:36   (92) Inlined the filter.
  • 2011-03-05 00:41   (87) No format string anymore. There are other ways.
  • 2011-03-05 00:43   (85) Unnecessary parentheses.
  • 2011-03-05 01:01   (83) -eq-.
  • 2011-03-05 15:42   (80) I no longer need to cast the initial input to int. Removed unneeded parentheses.
  • 2015-09-11 08:20   (79) I can move a + and save a space by abusing that - can only mean arithmetic and thus always converts both operands to a number.

Side note: My test cases.

\$\endgroup\$
2
\$\begingroup\$

C - 133

newline added for appearance

c;main(n,l,h,t,i){scanf("%d",&n);for(;n!=495;c++,n=(h-l)*99)
for(l=n%10,h=l,i=2;i--;)t=(n/=10)%10,t<l?l=t:t>h?h=t:0;printf("%d\n",c);}
\$\endgroup\$
2
\$\begingroup\$

APL, 42 chars/bytes*

{⍵=495:⍺+0⋄L←⍵⊤⍨3⍴10⋄(⍺+1)∇10⊥L[⍒L]-L[⍋L]}

APL entry was missing from historic golf! Had to rectify. Trivial implementation, nothing fancy. Tested on ngn/apl.

Explanation

The function is initially called with a single number . It will recursively call itself with the number of steps already taken and the new number .

⍵=495: ⍺+0

Terminating condition: if is 495, return the number of steps already taken (0 if is yet undefined—this may differ in other dialects.)

L←(3⍴10)⊤⍵

Decode into a list of 3 digits base 10. Above is reflected to save 1 char.

(⍺+1) ∇ 10⊥L[⍒L]-L[⍋L]  

Sort the list both ways, subtract one from the other member-wise, encode the result in base 10 (this works for negative digits too; may differ in other dialects) and recurse, adding 1 to (or just 1 if undefined, see above.)

⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯
*: APL can be written in its own (legacy) single-byte charset that maps APL symbols to the upper 128 byte values. Therefore, for the purpose of scoring, a program of N chars that only uses ASCII characters and APL symbols can be considered to be N bytes long.

\$\endgroup\$
  • 1
    \$\begingroup\$ 42 characters. Incidental? :) \$\endgroup\$ – tomsmeding Jul 29 '13 at 21:17
1
\$\begingroup\$

Lua 173 bytes

Going for the longest one:

T=table c=T.concat i=1 n=tonumber p=io.read()while l~="495"do l={p:match"(%d)(%d)(%d)"}T.sort(l)k={}k[1]=l[3]k[2]=l[2]k[3]=l[1]p=('%03i'):format(c(k)-c(l))i=i+1 end print(i)
\$\endgroup\$
1
\$\begingroup\$

Python, 63

f=lambda n:n-495and-~f(99*(int(max(`n`))-int(min(`n`))*(n>99)))

A recursive function. Gives 0 for n==495 and otherwise transforms n and increments the counter by 1 with -~.

The transformation uses the fact that for three-digit numbers abc-cba equals 99*(a-c). To account for two-digit numbers, we set the min digit to 0 unless n>99.

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

JavaScript 145

This was the best I could do on such short notice:

for(n=prompt(i=o=e='');!i--|n-495;o+=n+' - '+a+' = '+(n=(p=n-a+e)[2]?p:0+p)+'\n')b=n.split(e).sort(),n=b.reverse(a=b.join(e)).join(e);alert(o+~i)

\$\endgroup\$

Not the answer you're looking for? Browse other questions tagged or ask your own question.