From cf7269205b346cf16b35d258989bb19819427e9b Mon Sep 17 00:00:00 2001 From: Raphael McSinyx Date: Wed, 12 Oct 2016 22:16:44 +0700 Subject: Add /r/dailyprogrammer Challenge #287 [Easy] --- daily/287easy/README.md | 64 ++++++++++++++++++++++++++++++ daily/287easy/kaprekar.c | 79 +++++++++++++++++++++++++++++++++++++ daily/287easy/kaprekar.pas | 98 ++++++++++++++++++++++++++++++++++++++++++++++ daily/287easy/kaprekar.py | 40 +++++++++++++++++++ 4 files changed, 281 insertions(+) create mode 100644 daily/287easy/README.md create mode 100644 daily/287easy/kaprekar.c create mode 100644 daily/287easy/kaprekar.pas create mode 100755 daily/287easy/kaprekar.py (limited to 'daily') diff --git a/daily/287easy/README.md b/daily/287easy/README.md new file mode 100644 index 0000000..2ef0423 --- /dev/null +++ b/daily/287easy/README.md @@ -0,0 +1,64 @@ +# [[2016-10-10] Challenge #287 [Easy] Kaprekar's Routine](https://www.reddit.com/r/dailyprogrammer/comments/56tbds/20161010_challenge_287_easy_kaprekars_routine/) + +## Description + +Write a function that, given a 4-digit number, returns the largest digit in +that number. Numbers between 0 and 999 are counted as 4-digit numbers with +leading 0's. + + largest_digit(1234) -> 4 + largest_digit(3253) -> 5 + largest_digit(9800) -> 9 + largest_digit(3333) -> 3 + largest_digit(120) -> 2 + +In the last example, given an input of `120`, we treat it as the 4-digit number +`0120`. + +*Today's challenge is really more of a warmup for the bonuses. If you were able +to complete it, I highly recommend giving the bonuses a shot!* + +## Bonus 1 + +Write a function that, given a 4-digit number, performs the "descending digits" +operation. This operation returns a number with the same 4 digits sorted in +descending order. + + desc_digits(1234) -> 4321 + desc_digits(3253) -> 5332 + desc_digits(9800) -> 9800 + desc_digits(3333) -> 3333 + desc_digits(120) -> 2100 + +## Bonus 2 + +Write a function that counts the number of iterations in Kaprekar's Routine, +which is as follows. + +Given a 4-digit number *that has at least two different digits*, take that +number's descending digits, and subtract that number's ascending digits. For +example, given `6589`, you should take `9865 - 5689`, which is `4176`. Repeat +this process with `4176` and you'll get `7641 - 1467`, which is `6174`. + +Once you get to 6174 you'll stay there if you repeat the process. In this case +we applied the process 2 times before reaching 6174, so our output for `6589` +is `2`. + + kaprekar(6589) -> 2 + kaprekar(5455) -> 5 + kaprekar(6174) -> 0 + +Numbers like 3333 would immediately go to 0 under this routine, but since we +require at least two different digits in the input, all numbers will eventually +reach 6174, which is known as Kaprekar's Constant. Watch +[this video](https://www.youtube.com/watch?v=d8TRcZklX_Q) if you're still +unclear on how Kaprekar's Routine works. + +What is the largest number of iterations for Kaprekar's Routine to reach 6174? +That is, what's the largest possible output for your `kaprekar` function, given +a valid input? Post the answer along with your solution. + +*Thanks to [/u/BinaryLinux](https://www.reddit.com/u/BinaryLinux) and +[/u/Racoonie](https://www.reddit.com/u/Racoonie) for posting the idea behind +this challenge in +[/r/daliyprogrammer_ideas](https://www.reddit.com/r/daliyprogrammer_ideas)!* diff --git a/daily/287easy/kaprekar.c b/daily/287easy/kaprekar.c new file mode 100644 index 0000000..3121d88 --- /dev/null +++ b/daily/287easy/kaprekar.c @@ -0,0 +1,79 @@ +#include + +char a[4]; + +char largest_digit(short n) +{ + char m = n / 1000; + + if (m < n % 1000 / 100) + m = n % 1000 / 100; + + if (m < n % 100 / 10) + m = n % 100 / 10; + + return (m < n % 10) ? n % 10 : m; +} + +void sort_digits(short n) +{ + char i, j; + + a[0] = n / 1000; + a[1] = n % 1000 / 100; + a[2] = n % 100 / 10; + a[3] = n % 10; + + for (i = 0; i < 3; i++) + for (j = i + 1; j < 4; j++) + if (a[i] < a[j]) { + a[i] += a[j]; + a[j] = a[i] - a[j]; + a[i] -= a[j]; + } +} + +short desc_digits(short n) +{ + sort_digits(n); + + return a[0] * 1000 + a[1] * 100 + a[2] * 10 + a[3]; +} + +short asc_digits(short n) +{ + sort_digits(n); + + return a[3] * 1000 + a[2] * 100 + a[1] * 10 + a[0]; +} + +unsigned long long kaprekar(short n) +{ + char i; + + for (i = 0; n ^ 6174; i++) + n = desc_digits(n) - asc_digits(n); + + return i; +} + +int main() +{ + printf("largest_digit(1234) -> %hhd\n", largest_digit(1234)); + printf("largest_digit(3253) -> %hhd\n", largest_digit(3253)); + printf("largest_digit(9800) -> %hhd\n", largest_digit(9800)); + printf("largest_digit(3333) -> %hhd\n", largest_digit(3333)); + printf("largest_digit(120) -> %hhd\n\n", largest_digit(120)); + + printf("desc_digits(1234) -> %hd\n", desc_digits(1234)); + printf("desc_digits(3253) -> %hd\n", desc_digits(3253)); + printf("desc_digits(9800) -> %hd\n", desc_digits(9800)); + printf("desc_digits(3333) -> %hd\n", desc_digits(3333)); + printf("desc_digits(120) -> %hd\n\n", desc_digits(120)); + + printf("kaprekar(6589) -> %lld\n", kaprekar(6589)); + printf("kaprekar(5455) -> %lld\n", kaprekar(5455)); + printf("kaprekar(6174) -> %lld\n", kaprekar(6174)); + + return 0; +} diff --git a/daily/287easy/kaprekar.pas b/daily/287easy/kaprekar.pas new file mode 100644 index 0000000..7378f2d --- /dev/null +++ b/daily/287easy/kaprekar.pas @@ -0,0 +1,98 @@ +type + aos = array[0 .. 3] of shortint; + +function largest_digit(n: smallint): shortint; + var + m: shortint; + + begin + m := n div 1000; + + if m < n mod 1000 div 100 then + m := n mod 1000 div 100; + + if m < n mod 100 div 10 then + m := n mod 100 div 10; + + if m < n mod 10 then + exit(n mod 10) + else + exit(m) + end; + +function sorted_digits(n: smallint): aos; + var + a: aos; + i, j: shortint; + + begin + a[0] := n div 1000; + a[1] := n mod 1000 div 100; + a[2] := n mod 100 div 10; + a[3] := n mod 10; + + for i := 0 to 2 do + for j := i + 1 to 3 do + if a[i] < a[j] then + begin + inc(a[i], a[j]); + a[j] := a[i] - a[j]; + dec(a[i], a[j]) + end; + + exit(a) + end; + +function desc_digits(n: smallint): smallint; + var + a: aos; + + begin + a := sorted_digits(n); + + exit(a[0] * 1000 + a[1] * 100 + a[2] * 10 + a[3]) + end; + +function asc_digits(n: smallint): smallint; + var + a: aos; + + begin + a := sorted_digits(n); + + exit(a[3] * 1000 + a[2] * 100 + a[1] * 10 + a[0]) + end; + +function kaprekar(n: smallint): qword; + var + i: shortint = 0; + + begin + while n <> 6174 do + begin + n := desc_digits(n) - asc_digits(n); + inc(i) + end; + + exit(i) + end; + +begin + writeln('largest_digit(1234) -> ', largest_digit(1234)); + writeln('largest_digit(3253) -> ', largest_digit(3253)); + writeln('largest_digit(9800) -> ', largest_digit(9800)); + writeln('largest_digit(3333) -> ', largest_digit(3333)); + writeln('largest_digit(120) -> ', largest_digit(120)); + writeln; + + writeln('desc_digits(1234) -> ', desc_digits(1234)); + writeln('desc_digits(3253) -> ', desc_digits(3253)); + writeln('desc_digits(9800) -> ', desc_digits(9800)); + writeln('desc_digits(3333) -> ', desc_digits(3333)); + writeln('desc_digits(120) -> ', desc_digits(120)); + writeln; + + writeln('kaprekar(6589) -> ', kaprekar(6589)); + writeln('kaprekar(5455) -> ', kaprekar(5455)); + writeln('kaprekar(6174) -> ', kaprekar(6174)) +end. diff --git a/daily/287easy/kaprekar.py b/daily/287easy/kaprekar.py new file mode 100755 index 0000000..d976e66 --- /dev/null +++ b/daily/287easy/kaprekar.py @@ -0,0 +1,40 @@ +#!/usr/bin/env python3 + +def largest_digit(n): + return int(max(str(n))) + + +def desc_digits(n): + return int(''.join(sorted('{:04}'.format(n), reverse=True))) + + +def asc_digits(n): + return int(''.join(sorted('{:04}'.format(n)))) + + +def kaprekar(n): + i = 0 + + while n != 6174: + n = desc_digits(n) - asc_digits(n) + i += 1 + + return i + + +if __name__ == '__main__': + print('largest_digit(1234) -> {}'.format(largest_digit(1234))) + print('largest_digit(3253) -> {}'.format(largest_digit(3253))) + print('largest_digit(9800) -> {}'.format(largest_digit(9800))) + print('largest_digit(3333) -> {}'.format(largest_digit(3333))) + print('largest_digit(120) -> {}\n'.format(largest_digit(120))) + + print('desc_digits(1234) -> {}'.format(desc_digits(1234))) + print('desc_digits(3253) -> {}'.format(desc_digits(3253))) + print('desc_digits(9800) -> {}'.format(desc_digits(9800))) + print('desc_digits(3333) -> {}'.format(desc_digits(3333))) + print('desc_digits(120) -> {}\n'.format(desc_digits(120))) + + print('kaprekar(6589) -> {}'.format(kaprekar(6589))) + print('kaprekar(5455) -> {}'.format(kaprekar(5455))) + print('kaprekar(6174) -> {}'.format(kaprekar(6174))) -- cgit 1.4.1