-2
Challenge: Add two numbers. In O(n^m) time, where n and m are the two numbers given. Sleeping, or your language equivalent, is not allowed.
Input: Two integers, separated by a space.
Output: The sum of the two integers.
Additional notes: The exact timing doesn't matter, as long as the input 1000 2 takes roughly 1/1000th the time as the input 1000 3
iirelu
Posted 2019-09-26T06:17:38.617
Reputation: 19
1
Anonymous tacit infix function:
⊃*⍴+
However, if it really needs to take the two arguments together, separated by a space, we need the following anonymous tacit prefix function:
⊃*/⍴+/
+ or +/ sum the numbers
⍴ cyclically reshape that to the following length:
* or */ one number raised to the power of the other
⊃ pick the first element of that
Adám
Posted 2019-09-26T06:17:38.617
Reputation: 37 779
0
lambda n,m:sum(range(n**m))and m+n
Alternatively, as suggested by user202729:
lambda n,m:n**m*[1]and n+m
which also works with Python 3.
Chas Brown
Posted 2019-09-26T06:17:38.617
Reputation: 8 959
1Why sum(…)? Isn't range(n**m) already $O(n^m)$? – Adám – 2019-09-26T08:40:44.890
@Adám Yes in Python 2, but not in Python 3 where range doesn't actually create the list: TIO
What about [1]*? – user202729 – 2019-09-26T11:05:16.267
@user202729 : I'd guess you're right. – Chas Brown – 2019-09-27T05:31:49.913
3O(n^m) time means at most n^m asymptotically. I think you want theta. – xnor – 2019-09-26T06:26:23.840
5I presume you want people to use some kind of super slow algorithm, but there's nothing stopping them from doing simple addition followed by an
n^mloop of NOPs to pad the runtime. I don't think there's a way around that (we do not allow unobservable requirements) but just a warning that submissions may be less interesting than you envisioned. – Sanchises – 2019-09-26T06:30:26.1402Is it OK if a program takes n^m time to complete after printing the sum, or would it have to take the time before printing? – xnor – 2019-09-26T06:35:18.677
4Why the awkward input requirement. Can I really not just take two arguments? – Adám – 2019-09-26T07:04:01.460
So
2 100should be approximately 100 septillion times slower than100 2? – Stewie Griffin – 2019-09-26T07:27:08.2432
Maybe try the sandbox next time to get feedback on your challenge before you post it. And why not try to answer some challenges yourself! Then you get a good feel for what works.
– Sanchises – 2019-09-26T09:25:12.130@Sanchises Given that all of the current answers are doing effectively that (no-op to pad run time) I'll guess that they're allowed... – user202729 – 2019-09-26T11:06:48.067