Add /r/dailyprogrammer Challenge #305

6 files changed, 344 insertions, 0 deletions

diff --git a/daily/305easy/README.md b/daily/305easy/README.md
new file mode 100644
index 0000000..0f8876b
--- /dev/null
+++ b/daily/305easy/README.md
@@ -0,0 +1,50 @@
+# [[2017-03-06] Challenge #305 [Easy] Permutation base](https://www.reddit.com/r/dailyprogrammer/comments/5xu7sz/20170306_challenge_305_easy_permutation_base/)
+
+There may be an actual name to this base system (let us/me know in comments),
+and there is a math insight that makes this problem even easier, but it is
+still pretty easy with no math insight.
+
+For *permutation base 2*, the indexes and values start with:
+
+| index | value |
+| :---: | ----: |
+|   0   |    0  |
+|   1   |    1  |
+|   2   |   00  |
+|   3   |   01  |
+|   4   |   10  |
+|   5   |   11  |
+|   6   |  000  |
+|   7   |  001  |
+|   8   |  010  |
+|   9   |  011  |
+
+## Sample challenge
+
+What is the base-value for index `54`?
+
+What is the index-value for base `111000111`?
+
+## Example
+
+    permbase2 54
+    1 1 0 0 0
+
+    permbase2 inv 1 1 1 0 0 0 1 1 1
+    965
+
+## Challenge index inputs (some are 64-bit+ inputs)
+
+    234234234
+    234234234234234
+    234234234234234234234234
+
+## Challenge value inputs
+
+    000111000111111000111111000111111000111
+    11111111000111000111111000111111000111111000111
+
+## Bonus
+
+Extend the function to work with any base. Base 10 index value `10` is `00`.
+Index value `109` is `99`
diff --git a/daily/305easy/permbase.pas b/daily/305easy/permbase.pas
new file mode 100644
index 0000000..5513a77
--- /dev/null
+++ b/daily/305easy/permbase.pas
@@ -0,0 +1,50 @@
+uses math, strutils, sysutils;
+
+var
+  inv: string;
+  b: byte;
+  n: string;
+
+
+function permbase(
+  base: byte;
+  index: longint
+): string;
+
+  var
+    i: byte = 1;
+
+  begin
+    while base ** i <= index do
+      begin
+        index := index - base ** i;
+        inc(i)
+      end;
+    permbase := dec2numb(index, i, base)
+  end;
+
+
+function invpermbase(
+  base: byte;
+  value: string
+): longint;
+
+  begin
+    invpermbase := (base ** length(value) - base) div (base - 1) +
+                   numb2dec(value, base)
+  end;
+
+begin
+  (*
+   * Input format:
+   * <invert?>
+   * <base> <value>
+   *)
+  readln(inv);
+  readln(b, n);
+  n := delspace(n);
+  if strtobool(inv) then
+    writeln(invpermbase(b, n))
+  else
+    writeln(permbase(b, strtoint(n)))
+end.
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.
diff --git a/daily/305intermediate/README.md b/daily/305intermediate/README.md
new file mode 100644
index 0000000..b1854b9
--- /dev/null
+++ b/daily/305intermediate/README.md
@@ -0,0 +1,53 @@
+# [[2017-03-08] Challenge #305 [Intermediate] The Best Conjunction](https://www.reddit.com/r/dailyprogrammer/comments/5yaiin/20170308_challenge_305_intermediate_the_best/)
+
+## Description
+
+Your job is to find the best conjunction—that is, find the word with the most
+sub-words inside of it given a list of English words. Some example include:
+
+* Something (3 words: So, me, thing)
+* Awesomeness (3 words: awe, some, ness)
+
+## Formal Inputs & Outputs
+
+### Input description
+
+Use a [list of English words](http://www-personal.umich.edu/~jlawler/wordlist)
+and a *minimum sub-word length* (the smallest length of a sub-word in a
+conjuncted word) to find the *best conjunction* (most sub-words) in the
+dictionary!
+
+### Output description
+
+    minSize 3: disproportionateness (6: dis, pro, port, ion, ate, ness)
+    minSize 4: dishonorableness (4: dish, onor, able, ness)
+
+Find minSize 5
+
+## Notes/Hints
+
+* Be aware the file is split by `\r\n` instead of `\n`, and has some empty
+  lines at the end
+* In order to run in a reasonable amount of time, you will need an O(1) way of
+  checking if a word exists. (Hint: It won't be O(1) memory)
+* Make sure you're checking all possibilities—that is, given the word *sotto*,
+  if you begin with *so*, you will find that there is no word or combination of
+  words to create *tto*. You must continue the search in order to get the
+  conjunction of *sot* and *to*.
+
+## Bonus
+
+* Each sub-word must include the last letter of the previous subword. For
+  example *counterrevolutionary* would become *count*, *terre*, *evolution*,
+  *nary*
+* Instead of simply the last letter, allow any number of letters to be shared
+  between words (e.g. *consciencestricken* -> *conscience*, *sciences*,
+  *stricken*)
+
+## Credit
+
+This challenge was suggested by user /u/DemiPixel, many thanks!
+
+Have a good challenge idea?
+
+Consider submitting it to /r/dailyprogrammer_ideas
diff --git a/daily/305intermediate/conjunction.pas b/daily/305intermediate/conjunction.pas
new file mode 100644
index 0000000..2ff8548
--- /dev/null
+++ b/daily/305intermediate/conjunction.pas
@@ -0,0 +1,99 @@
+type
+  strarray = array of string;
+
+var
+  wordlist, a, maxa, mt: strarray;
+  i: int32;
+  size: int8 = 1;
+  s, maxs: string;
+
+
+function isnotin(
+  s: string;
+  a: strarray
+): boolean;
+
+  var
+    l, m, h: int32;
+
+  begin
+    l := 0;
+    h := length(a) - 1;
+    repeat
+      m := (l + h) div 2;
+      if s = a[m] then
+        exit(false)
+      else if s < a[m] then
+        h := m - 1
+      else
+        l := m + 1
+    until l > h;
+    isnotin := true
+  end;
+
+
+function conjunct(
+  s: string;
+  size: int8
+): strarray;
+
+  var
+    a: strarray;
+    i, j: int8;
+
+  begin
+    if s = '' then
+      exit(mt);
+    setlength(conjunct, 0);
+    for i := size to length(s) do
+      begin
+        if isnotin(copy(s, 1, i), wordlist) then
+          continue;
+        a := conjunct(copy(s, i + 1, length(s) - i), size);
+        if ((length(a) = 1) and
+            (copy(s, i + 1, length(s) - i) <> a[0])) or
+           (length(a) < length(conjunct)) then
+          continue;
+
+        setlength(conjunct, length(a) + 1);
+        for j := 1 to length(a) do
+          conjunct[j] := a[j - 1];
+        conjunct[0] := copy(s, 1, i)
+      end;
+  end;
+
+
+begin
+  setlength(wordlist, 69903); (* I know this is a bit cheaty *)
+  assign(input, 'wordlist');
+  reset(input);
+  for i := 0 to 69902 do
+    readln(wordlist[i]);
+  close(input);
+  setlength(mt, 0); (* for convenience *)
+
+  repeat
+    setlength(maxa, 0);
+    for s in wordlist do
+      begin
+        if length(s) < length(maxa) * size then
+          continue;
+        a := conjunct(s, size);
+        if length(a) > length(maxa) then
+          begin
+            setlength(maxa, length(a));
+            for i := 0 to length(a) - 1 do
+              maxa[i] := a[i];
+            maxs := s
+          end
+      end;
+    if length(maxa) = 0 then
+      break;
+
+    write('Min size ', size, ': ', maxs, ' (', length(maxa), ': ');
+    for i := 0 to length(maxa) - 2 do
+      write(maxa[i], ', ');
+    writeln(maxa[length(maxa) - 1], ')');
+    inc(size)
+  until false (* the loop should break before writing *)
+end.