24
1
Let's count...
Count up to 2 and back to 1
Count up to 4 and back to 1
Count up to 6 and back to 1
... ok you got it...
put all these together and you'll get the following sequence
{1,2,1,2,3,4,3,2,1,2,3,4,5,6,5,4,3,2,1,2,3,4,5,6,7,8,7,6,5,4,3,2,1,2,3...}
Challenge
Given an integer n>0
for 1-indexed (or n>=0
for 0-indexed), output the nth term of this sequence
Test cases
Input->Output
1->1
68->6
668->20
6667->63
10000->84
Rules
your program must be able to compute solutions up to n=10000 in under a minute
This is code-golf, so the shortest code in bytes wins!
If I 0-index I have to support n = 0, right? That should probably be clarified. – Jakob – 2017-08-22T23:59:41.467
@Jakob yes you are right! I'll edit – None – 2017-08-23T00:02:50.303
2Who decides what takes a minute? A time-optimal Turing machine built from lego would take a really long time, while the same Turing machine simulated in, say, C, would presumably take seconds, or minutes, depending on what processor it runs on. Thus, if I submit said Turing machine description, is it valid? – Arthur – 2017-08-23T10:14:52.043
2@Arthur I think that you can understand why I made this restriction...I didn't want an algorithm to take "forever" to find n=10000 by producing a huge list.Most of the people here gave brilliant answers that find millions in seconds. – None – 2017-08-23T10:32:19.040
4@BillSteihn I think the restriction is unnecessary. – Erik the Outgolfer – 2017-08-23T10:38:17.567
2@EriktheOutgolfer gode golf answers can be tricky...without the restriction an answer that produces 10.000 tuples [1,2...2n..2,1] would be valid.The restriction is only for answers like this.I don't see where the problem is.I just want your answer to find all test cases in a reasonable amount of time. – None – 2017-08-23T11:01:54.463
@BillSteihn And where is the problem with creating something like
[1..2..1..4..1..(...)..1..2n..1]
? – Erik the Outgolfer – 2017-08-23T11:07:21.6001@EriktheOutgolfer If you want the 10.000th term and you compute 10.000 tuples you will get a list of 50.000.001 elements.You need RAM + time.. – None – 2017-08-23T11:23:06.513
3@StraklSeth General consensus here is that it should work in theory, not necessarily in practice. – Erik the Outgolfer – 2017-08-23T11:24:34.960
@EriktheOutgolfer ok.. I think that we made clear why I used this restriction.Now,this is my challenge and it doesn't belong to the "General consensus group".sorry – None – 2017-08-23T11:30:08.357
@EriktheOutgolfer Putting reasonable restrictions on output time is a common practice to prevent ridiculous brute-force approaches. It's been done like that dozens, if not hundreds of times here. Individual challenge authors can decide if they want to include a restriction like that or not. – AdmBorkBork – 2017-08-23T13:31:19.937
1@AdmBorkBork Still "under a minute" isn't well-defined then. – Erik the Outgolfer – 2017-08-23T13:44:47.613