Add /r/dailyprogrammer Challenge #305

2 files changed, 92 insertions, 0 deletions

diff --git a/daily/305hard/README.md b/daily/305hard/README.md
new file mode 100644
index 0000000..8448fff
--- /dev/null
+++ b/daily/305hard/README.md
@@ -0,0 +1,38 @@
+# [[2017-03-10] Challenge #305 [Hard] Numbers for Sale](https://www.reddit.com/r/dailyprogrammer/comments/5yoo87/20170310_challenge_305_hard_numbers_for_sale/)
+
+## Description
+
+KimCo Global, the global corporation from DPRK, is secretly developing an
+awesome new  product for its loyal costumers called Number. It is what is says
+- Number, but not just any Number, each Number is a unique positive integer.
+Each number costs its value - so 1 costs $1, 5 costs $5, etc. KimCo Global puts
+each number from 1 to 10^15 on sale. 
+
+Your friend, a salesman for KimCo Global, needs your help to optimize their
+profits. He received all available Numbers whose sum of digits equals 69 and
+seeks to sell them for the highest value he can. His regular accountant is of
+no help, can you assist?
+
+What is the total of positive integers less than 10^15 whose sum of digits
+equal 69?
+
+## Credit
+
+This challenge was suggested by user /u/raluralu, many thanks. If you have any
+challenge ideaas, please do share them on /r/dailyprogrammer_ideas and there's
+a good chance we'll use them. 
+
+## EDIT 2017-03-11
+
+There's been some discussion about the ambiguity of this challenge - is it
+asking for the *sum* of all of those Numbers or the *quantity* of Numbers that
+fit the constraint? I have to admit the original submission from
+/r/dailyprogrammer_ideas was also a bit ambiguous. I believe the submitter who
+wrote it does not speak English natively, and so they had some ambiguity in
+their presentation. As such, I copied their question complete with ambiguity. 
+
+Because of this, I think either will be fine - the sum or the quantity. 
+
+The real challenge, and why this is a Friday hard one, is writing a better than
+naive solution as some of you have picked up. Some of it is math and some of it
+is programming.
diff --git a/daily/305hard/number.pas b/daily/305hard/number.pas
new file mode 100644
index 0000000..6a2d6e5
--- /dev/null
+++ b/daily/305hard/number.pas
@@ -0,0 +1,54 @@
+var
+  a: array[0..15] of byte;
+
+
+function factorial(n: byte): int64;
+  begin
+    if n < 2 then
+      exit(1);
+    factorial := factorial(pred(n)) * n
+  end;
+
+
+function number(
+  a: array of byte;
+  depth: byte
+): int64;
+
+  var
+    i, sum: byte;
+    b: array[0..9] of byte;
+
+  begin
+    if depth = 15 then
+      begin
+        sum := 0;
+        for i := 1 to 15 do
+          inc(sum, a[i]);
+        if sum <> 69 then
+          exit(0);
+        number := 1307674368000; (* factorial(15) *)
+        for i := 0 to 9 do
+          b[i] := 0;
+        for i := 1 to 15 do
+          inc(b[a[i]]);
+        for i := 0 to 9 do
+          number := number div factorial(b[i]);
+        exit
+      end;
+
+    number := 0;
+    i := a[depth];
+    inc(depth);
+    repeat
+      a[depth] := i;
+      number := number + number(a, depth);
+      inc(i)
+    until i = 10
+  end;
+
+
+begin
+  a[0] := 0;
+  writeln(number(a, 0))
+end.