30
\$\begingroup\$

Say you list the positive integers in a triangle, then flip it left-to-right. Given a number, output the number it's sent to. This is a self-inverse mapping.

         1                      1         
       2   3                  3   2       
     4   5   6    <--->     6   5   4     
   7   8   9  10         10   9   8   7   
11  12  13  14  15     15  14  13  12  11

This is the n'th element of A038722, one-indexed:

1, 3, 2, 6, 5, 4, 10, 9, 8, 7, 15, 14, 13, 12, 11, ...

This sequence reverses contiguous chunks of the positive integers with increasing lengths:

 1, 3, 2, 6, 5, 4, 10, 9, 8, 7, 15, 14, 13, 12, 11, ...
<-><----><-------><-----------><------------------>

Test cases:

1 -> 1
2 -> 3
3 -> 2
4 -> 6
14 -> 12
990 -> 947
991 -> 1035
1000 -> 1026
1035 -> 991
1036 -> 1081
12345 -> 12305

Leaderboard:

var QUESTION_ID=117879,OVERRIDE_USER=20260;function answersUrl(e){return"https://api.stackexchange.com/2.2/questions/117879/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(e,s){return"https://api.stackexchange.com/2.2/answers/"+s.join(";")+"/comments?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){answers.push.apply(answers,e.items),answers_hash=[],answer_ids=[],e.items.forEach(function(e){e.comments=[];var s=+e.share_link.match(/\d+/);answer_ids.push(s),answers_hash[s]=e}),e.has_more||(more_answers=!1),comment_page=1,getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){e.items.forEach(function(e){e.owner.user_id===OVERRIDE_USER&&answers_hash[e.post_id].comments.push(e)}),e.has_more?getComments():more_answers?getAnswers():process()}})}function getAuthorName(e){return e.owner.display_name}function process(){var e=[];answers.forEach(function(s){var r=s.body;s.comments.forEach(function(e){OVERRIDE_REG.test(e.body)&&(r="<h1>"+e.body.replace(OVERRIDE_REG,"")+"</h1>")});var a=r.match(SCORE_REG);a&&e.push({user:getAuthorName(s),size:+a[2],language:a[1],link:s.share_link})}),e.sort(function(e,s){var r=e.size,a=s.size;return r-a});var s={},r=1,a=null,n=1;e.forEach(function(e){e.size!=a&&(n=r),a=e.size,++r;var t=jQuery("#answer-template").html();t=t.replace("{{PLACE}}",n+".").replace("{{NAME}}",e.user).replace("{{LANGUAGE}}",e.language).replace("{{SIZE}}",e.size).replace("{{LINK}}",e.link),t=jQuery(t),jQuery("#answers").append(t);var o=e.language;/<a/.test(o)&&(o=jQuery(o).text()),s[o]=s[o]||{lang:e.language,user:e.user,size:e.size,link:e.link}});var t=[];for(var o in s)s.hasOwnProperty(o)&&t.push(s[o]);t.sort(function(e,s){return e.lang>s.lang?1:e.lang<s.lang?-1:0});for(var c=0;c<t.length;++c){var i=jQuery("#language-template").html(),o=t[c];i=i.replace("{{LANGUAGE}}",o.lang).replace("{{NAME}}",o.user).replace("{{SIZE}}",o.size).replace("{{LINK}}",o.link),i=jQuery(i),jQuery("#languages").append(i)}}var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk",answers=[],answers_hash,answer_ids,answer_page=1,more_answers=!0,comment_page;getAnswers();var SCORE_REG=/<h\d>\s*([^\n,]*[^\s,]),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/,OVERRIDE_REG=/^Override\s*header:\s*/i;
body{text-align:left!important}#answer-list,#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"> <div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr></thead> <tbody id="answers"> </tbody> </table> </div><div id="language-list"> <h2>Winners by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr></thead> <tbody id="languages"> </tbody> </table> </div><table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table> <table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table>

\$\endgroup\$

18 Answers 18

15
\$\begingroup\$

JavaScript (ES7), 26 bytes

n=>((2*n)**.5+.5|0)**2-n+1

An implementation of the following formula from OEIS:

formula

Demo

let f =

n=>((2*n)**.5+.5|0)**2-n+1

for(n = 1; n <= 50; n++) {
  console.log(n, '->', f(n))
}

\$\endgroup\$
  • \$\begingroup\$ I like the OR operation to chunk it into an integer! nice job! \$\endgroup\$ – CraigR8806 Apr 28 '17 at 13:15
7
\$\begingroup\$

Jelly, 8 7 bytes

RṁR€UFi

Thanks to @ErikTheOutgolfer for saving 1 byte!

Try it online!

How it works

RṁR€UFi  Main link. Argument: n

R        Range; yield [1, ..., n].
  R€     Range each; yield [[1], [1, 2], [1, 2, 3], ..., [1, ..., n]].
 ṁ       Mold the left argument like the right one, yielding
         [[1], [2, 3], [4, 5, 6], ...]. The elements of the left argument are 
         repeated cyclically to fill all n(n+1)/2 positions in the right argument.
    U    Upend; reverse each flat array, yielding [[1], [3, 2], [6, 5, 4], ...].
     F   Flatten, yielding [1, 3, 2, 6, 5, 4, ...].
      i  Index; find the first index of n in the result.
\$\endgroup\$
6
\$\begingroup\$

Alice, 27 bytes

Thanks to Sp3000 for the .C idea.

/o
\i@/.2:e2,tE*Y~Z.H2*~.C+

Try it online!

Explanation

I think there may be a shorter way to compute this using triangular numbers, but I thought this is an interesting abuse of a built-in, so here's a different solution.

The basic idea is to make use of Alice's "pack" and "unpack" built-ins. "Pack", or Z, takes two integers maps them bijectively to a single integer. "Unpack", or Y, inverts this bijection and turns one integer into two. Normally, this can be used to store a list or tree of integers in a single (large) integer and recover the individual values later. However, in this case we can use the functions in the opposite order, to let the nature of the bijection work for us.

Unpacking one integer into two integers basically consists of three steps:

  1. Map ℤ → ℕ (including zero) with a simple "folding". That is, map negative integers to odd naturals, and non-negative integers to even naturals.
  2. Map ℕ → ℕ2, using the Cantor pairing function. That is, the naturals are written along the diagonals of an infinite grid and we return the indices:

       ...
    3  9 ...
    2  5 8 ...
    1  2 4 7 ...
    0  0 1 3 6 ...
    
       0 1 2 3
    

    E.g. 8 would be mapped to the pair (1, 2).

  3. Map 2 → ℤ2, using the inverse of step 1 on each integer individually. That is, odd naturals get mapped to negative integers, and even naturals get mapped to non-negative integers.

To pack two integers into one, we simply invert each of those steps.

Now, we can see that the structure of the Cantor pairing function conveniently encodes the triangle we need (although the values are off-by-one). To reverse those diagonals, all we need to do is swap the x and y coordinates into the grid.

Unfortunately, since all three of the above steps are combined into a single built-in Y (or Z), we need to undo the ℤ → ℕ or ℕ → ℤ mappings ourselves. However, while doing so we can save a couple of bytes by directly using + → ℤ or ℤ → ℕ+ mappings, to take care of the off-by-one error in the table. So here is the entire algorithm:

  1. Map + → ℤ using (n/2) * (-1)n-1. This mapping is chosen such that it cancels the implicit ℤ → ℕ mapping during unpacking, except that it shifts the value down by 1.
  2. Unpack the result into two integers.
  3. Swap them.
  4. Pack the swapped values into a single integer again.
  5. Map ℤ → ℕ+ using |2n| + (n≥0). Again, this mapping is chosen such that it cancels the implicit ℕ → ℤ mapping during packing, except that it shifts the value up by 1.

With that out of the way, we can look at the program:

/o
\i@/...

This is simply a framework for linear arithmetic programs with integer input and output.

.    Duplicate the input.
2:   Halve it.
e    Push -1.
2,   Pull up the other copy of the input.
t    Decrement.
E    Raise -1 to this power.
*    Multiply. We've now computed (n/2) * (-1)^(n-1).
Y    Unpack.
~    Swap.
Z    Pack.
.H   Duplicate the result and take its absolute value.
2*   Double.
~    Swap with other copy.
.C   Compute k-choose-k. That's 1 for k ≥ 0 and 0 for k < 0.
+    Add. We've now computed |2n| + (n≥0).
\$\endgroup\$
5
\$\begingroup\$

Jelly, 8 bytes

Ḥ½+.Ḟ²‘_

Try it online!

Port of my MATL answer.

\$\endgroup\$
4
\$\begingroup\$

MATL, 15 11 bytes

EX^.5+kUG-Q

Try it online!

This uses the formula

a(n) = floor(sqrt(2*n)+1/2)^2 - n + 1.
\$\endgroup\$
4
\$\begingroup\$

Octave, 71 68 bytes

3 bytes saved thanks to Conor O'Brien.

x=triu(ones(n=input('')));x(~~x)=1:nnz(x);disp(nonzeros(flip(x))(n))

This doesn't work for large inputs due to memory limitations.

Try it online!

Explanation

Consider input n = 4. The code first builds the matrix

 1     1     1     1
 0     1     1     1
 0     0     1     1
 0     0     0     1

Then it replaces nonzero entries in column-major order (down, then across) by 1, 2, 3 ... :

 1     2     4     7
 0     3     5     8
 0     0     6     9
 0     0     0    10

Then it flips the matrix vertically:

 0     0     0    10
 0     0     6     9
 0     3     5     8
 1     2     4     7

Finally, it takes the n-th nonzero value in column-major order, which in this case is 6.

\$\endgroup\$
  • 1
    \$\begingroup\$ @rahnema1 That e is genius! You should definitely post it as an answer, together with your other very good suggestions. As for ans =, I'm never sure it it's valid or not \$\endgroup\$ – Luis Mendo Apr 28 '17 at 8:55
4
\$\begingroup\$

Haskell, 31 bytes

r=round
f n=r(sqrt$2*n)^2-r n+1

Try it online!

This answer just uses the formula. It is the least interesting answer here, but it also happens to be the golfiest.

Haskell, 38 36 34 bytes

x!y|x<=y=1-x|v<-y+1=v+(x-y)!v
(!0)

Try it online!

(!0) is the point free function we are concerned with.

Explanation

Let me start out by saying I'm very happy with this answer.

The basic idea here is that if we remove the largest triangular number smaller than our input we can reverse it and add the triangular number back. So we define an operator !, ! takes our regular input, x, but it also takes an extra number y. y keeps track of the size of the growing triangular number. If x>y we want to recurse, we decrease x by y and increase y by one. So we calculate (x-y)!(y+1) and add y+1 to it. If x<=y we have reached our base case, to reverse x's placement in the row of the triangle we return 1-x.

Haskell, 54 bytes

f x|u<-div(x^2-x)2=[u+x,u+x-1..u+1]
(!!)$0:(>>=)[1..]f

Try it online!

(!!)$0:(>>=)[1..]f is a point-free function

Explanation

The first thing we are concerned with is f, f is a function that takes x and returns the xth row of th triangle in reverse. It does this by first calculating the x-1nd triangular number and assigning it to u. u<-div(x^2-x)2. We then return the list [u+x,u+x-1..u+1]. u+x is the xth triangular number and the first number on the row, u+x-1 is one less than that and the second number on the row u+1 is one more than the last triangular number and thus the last number on the row.

Once we have f we form a list (>>=)[1..]f, which is a flattening of the triangle. We add zero to the front with 0: so that our answers will not be offset by one, and supply it to our indexing function (!!).

Haskell, 56 bytes

f 0=[0]
f x|u<-f(x-1)!!0=[u+x,u+x-1..u+1]
(!!)$[0..]>>=f

Try it online!

This one is 2 bytes longer but a bit more elegant in my opinion.

\$\endgroup\$
3
\$\begingroup\$

C (gcc), 48 bytes

k,j,l;f(n){for(k=j=0;k<n;)l=k,k+=++j;n=1+k-n+l;}

Try it online!

Probably suboptimal, but I'm pretty happy with this one. Uses the fact that

NTFN = TN + A057944(N) - N + 1

(If I wrote the formula down correctly, that is.)

\$\endgroup\$
  • \$\begingroup\$ You're not calling return, but the a return value is used. That is undefined behavior. \$\endgroup\$ – 2501 Apr 28 '17 at 1:45
  • \$\begingroup\$ @2501 As long as the program works, it's allowed. And, writing to the first argument of a function is equivalent to returning a value. \$\endgroup\$ – Conor O'Brien Apr 28 '17 at 1:47
  • \$\begingroup\$ And, writing to the first argument of a function is equivalent to returning a value. No such thing exists in the C language. The standard even explicitly says using the returned value from a function that doesn't return is undefined behavior. \$\endgroup\$ – 2501 Apr 28 '17 at 1:48
  • 1
    \$\begingroup\$ @2501 You seem to be confusing the C environment (gcc) for the C specification. Yes, the C language/spec calls it undefined, but it is implemented as such. So when I say "equivalent", I am most definitely referring to the implementation of C by gcc and most other compilers. On PPCG, we don't write "perfect" code--much code goes against specification for the sake of golfing. As I said, as long as it works, it's a valid answer. \$\endgroup\$ – Conor O'Brien Apr 28 '17 at 1:51
  • \$\begingroup\$ @2501 I encourage you to read some articles on the meta site, particularly this one. \$\endgroup\$ – Conor O'Brien Apr 28 '17 at 2:01
2
\$\begingroup\$

05AB1E, 30 bytes

U1V[YLO>X›iYLOX-UY<LO>X+,q}Y>V

Try it online!

\$\endgroup\$
  • \$\begingroup\$ I was about to say "What? An 05AB1E answer with no Unicode?" but then the one non-ASCII character ruins it... :P Nice first answer, though, welcome to Programming Puzzles and Code Golf! \$\endgroup\$ – clismique Apr 28 '17 at 7:25
  • \$\begingroup\$ @Qwerp-Derp Thank you very much! I just started learning this language, so I'm not surprised my answer was that bad. \$\endgroup\$ – Eduardo Hoefel May 3 '17 at 0:12
2
\$\begingroup\$

Husk, 6 bytes

!ṁ↔´CN

Try it online!

Explanation

!ṁ↔´CN  -- implicit input N, for example: 4
   ´ N  -- duplicate the natural numbers:
           [1,2,3,…] [1,2,3,…]
    C   -- cut the second argument into sizes of the first:
           [[1],[2,3],[4,5,6],[7,8,9,10],…]
 ṁ↔     -- map reverse and flatten:
           [1,3,2,6,5,4,10,9,8,7,15,…
!       -- index into that list:
           6
\$\endgroup\$
2
\$\begingroup\$

tinylisp, 78 bytes

(d _(q((R N T)(i(l T N)(_(a R 1)N(a T R))(a 2(a T(s T(a N R
(d f(q((N)(_ 2 N 1

Defines a function f that performs the mapping. Try it online!

Ungolfed

We find the smallest triangular number that is greater than or equal to the input number, as well as which row of the triangle our number is in. From these, we can calculate the flipped version of the number.

  • If the current triangular number is less than N, recurse to the next row of the triangle. (We treat the top row as row 2 to make the math simpler.)
  • Otherwise, the flipped version of N is (T-N)+(T-R)+2.

The main function flip simply calls the helper function _flip starting from the top row.

(load library)

(def _flip
 (lambda (Num Row Triangular)
  (if (less? Triangular Num)
   (_flip Num (inc Row) (+ Triangular Row))
   (+ 2
    (- Triangular Num)
    (- Triangular Row))))))

(def flip
 (lambda (Num) (_flip Num 2 1)))
\$\endgroup\$
1
\$\begingroup\$

05AB1E, 9 bytes

·LD£í˜¹<è

Try it online!

Explanation

·L          # push range [1 ... 2n]
  D         # duplicate
   £        # split the first list into pieces with size dependent on the second list
    í       # reverse each sublist
     ˜      # flatten
      ¹<è   # get the element at index <input>-1

Array flattening unfortunately doesn't handle larger lists very well.
At the cost of 1 byte we could do ·t2z+ïn¹-> using the mathematical formula floor(sqrt(2*n)+1/2)^2 - n + 1 found on OEIS.

\$\endgroup\$
1
\$\begingroup\$

Batch, 70 bytes

@set/ai=%2+1,j=%3+i
@if %j% lss %1 %0 %1 %i% %j%
@cmd/cset/ai*i+1-%1

Uses a loop to find the index of the triangular number at least as large as n.

\$\endgroup\$
0
\$\begingroup\$

PHP, 35 Bytes

<?=((2*$argn)**.5+.5^0)**2-$argn+1;

Same formula that is used in Arnaulds Approach

\$\endgroup\$
0
\$\begingroup\$

C#, 46 44 bytes

n=>Math.Pow((int)(Math.Sqrt(2*n)+.5),2)-n+1;

I port @Arnauld's solution. Thank you!

  • Pow of 0.5 is Sqrt. 2 bytes saved!
\$\endgroup\$
0
\$\begingroup\$

APL (Dyalog), 27 bytes

I've got two solutions at the same bytecount.

A train:

⊢⊃⊃∘(,/{⌽(+/⍳⍵-1)+⍳⍵}¨∘⍳)

Try it online!

And a dfn:

{⍵⊃⊃((⍳⍵),.{1+⍵-⍳⍺}+\⍳⍵)}

Try it online!

Both of these solutions first create the flipped triangle and then extract element at the index stated by the argument (1-based).

\$\endgroup\$
0
\$\begingroup\$

J, 25 bytes

3 :'>:y-~*:>.-:<:%:>:8*y'

As an explanation, consider f(n) = n(n+1)/2. f(r), given the row r, returns the leftmost number of the the rth row of the mirrored triangle. Now, consider g(n) = ceiling[f⁻¹(n)]. g(i), given the index i, returns the row on which index i is found. Then, f(g(n)) returns the leftmost number of the row on which index n is found. So, h(n) = f(g(n)) - (n - f(g(n)-1)) + 1 is the answer to the above problem.

Simplifying, we get h(n) = [g(n)]² - n + 1 = ceiling[(-1 + sqrt(1 + 8n))/2]² - n + 1.

From the looks of @Arnauld's formula, it appears that:

ceiling[(-1 + sqrt(1 + 8n))/2] = floor[1/2 + sqrt(2n)].

\$\endgroup\$
0
\$\begingroup\$

Pyt, 13 12 bytes

←Đ2*√½+⌊²-~⁺

Port of Arnauld's approach

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.