From 69a50f40bea8f04c2d2b1715dad5ea8c7d6ef507 Mon Sep 17 00:00:00 2001 From: Raphael McSinyx Date: Tue, 14 Mar 2017 10:23:43 +0700 Subject: Add /r/dailyprogrammer Challenge #305 --- daily/305easy/README.md | 50 ++++++++++++++++++ daily/305easy/permbase.pas | 50 ++++++++++++++++++ daily/305hard/README.md | 38 ++++++++++++++ daily/305hard/number.pas | 54 +++++++++++++++++++ daily/305intermediate/README.md | 53 +++++++++++++++++++ daily/305intermediate/conjunction.pas | 99 +++++++++++++++++++++++++++++++++++ 6 files changed, 344 insertions(+) create mode 100644 daily/305easy/README.md create mode 100644 daily/305easy/permbase.pas create mode 100644 daily/305hard/README.md create mode 100644 daily/305hard/number.pas create mode 100644 daily/305intermediate/README.md create mode 100644 daily/305intermediate/conjunction.pas 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: + * + * + *) + 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. -- cgit 1.4.1