Hitting 495 (Kaprekar) [duplicate]

Question

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

Answer 1

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 (c − a − 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.

Answer 2

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.

Answer 3

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.

Answer 4

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

Answer 5

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.

Answer 6

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.

Answer 7

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.

Answer 8

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

Answer 9

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

Answer 10

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)

Answer 11

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.

Answer 12

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)