title: Xorting an array

text:
# Question
Title: Xorting an array
Conceptually, this challenge is really simple. You're given a list of non-negative integers `a<sub>i</sub>`. If possible, find a non-negative integer `N`, such that the list consisting of `b<sub>i</sub> = a<sub>i</sub> XOR N` is sorted. If no such `N` exists, output should be anything that can't be mistaken for a valid `N`, e.g. a negative number, nothing at all, an error etc.

Here is an example:

```
[4, 7, 6, 1, 0, 3]

```

If we take every element in this list `XOR 5`, we get

```
[1, 2, 3, 4, 5, 6]

```

which is sorted. (Note that it is not a requirement for the resulting list to have unique elements and contain no gaps. If the result of such an operation was `[0, 1, 1, 3]` that would still be valid.) On the other hand for the list

```
[4, 7, 1, 6, 0, 3]

```

no such `N` exists.

You may write a program or function, taking input via STDIN (or closest alternative), command-line argument or function argument and outputting the result via STDOUT (or closest alternative), function return value or function (out) parameter.

Input may be in any convenient list or string format. You may assume that the `a<sub>i</sub>` are less than `2<sup>31</sup>` each and that the list contains at least one element.

Your code must handle any of the test cases (especially the four large ones) in a matter of a few seconds.

Standard rules apply.

### Test Cases

For every test case which doesn't return `-1` there's an infinite number of correct answers. The one listed here is the smallest one. Additional solutions exist by additionally setting bits which are the same across all integers in the input (notably those which are larger than the most-significant bit in the largest number of the list).

```
[4 7 6 1 0 3] => 5
[4 7 1 6 0 3] => -1
[0 1 3 4 6 7] => 0
[4 2 3 1] => 6
[2 3 0 0 7 7 4 5 11 11] => 2
[2 3 0 0 7 7 5 4 11 11] => -1
[1086101479 748947367 1767817317 656404978 1818793883 1143500039] => -1
[180522983 1885393660 751646477 367706848 331742205 724919510 850844696 2121330641 869882699 1831158987 542636180 1117249765 823387844 731663826 1762069894 240170102 1020696223 1212052937 2041219958 712044033 195249879 1871889904 1787674355 1849980586 1308879787 1743053674 1496763661 607071669 1987302942 178202560 1666170841 1035995406 75303032 1755269469 200581873 500680130 561748675 1749521426 1828237297 835004548 934883150 38711700 1978960635 209243689 1355970350 546308601 590319412 959613996 1956169400 140411967 112601925 88760619 1977727497 672943813 909069787 318174568 385280382 370710480 809689639 557034312 865578556 217468424 346250334 388513751 717158057 941441272 437016122 196344643 379529969 821549457 97008503 872313181 2105942402 603939495 143590999 1580192283 177939344 853074291 1288703007 1605552664 162070930 1325694479 850975127 681702163 1432762307 1994488829 780869518 4379756 602743458 1963508385 2115219284 1219523498 559301490 4191682 1918142271 169309431 346461371 1619467789 1521741606 1881525154] => -1
[37580156 64423492 87193676 91914964 93632157 96332899 154427982 176139560 184435039 228963836 230164674 279802291 301492375 309127664 345705721 370150824 380319820 403997410 410504675 416543032 418193132 424733526 428149607 435596038 477224208 515649925 519407995 525469350 614538124 624884850 642649261 653488151 679260270 685637235 690613185 739141066 825795124 832026691 832633584 833213619 852655299 913744258 917674993 921902522 925691996 931307936 954676047 972992595 997654606 1020009811 1027484648 1052748108 1071580605 1108881241 1113730139 1122392118 1154042251 1170901568 1180031842 1180186856 1206428383 1214066097 1242934611 1243983997 1244736049 1262979035 1312007069 1312030297 1356274316 1368442960 1377432523 1415342434 1471294243 1529353536 1537868913 1566069818 1610578189 1612277199 1613646498 1639183592 1668015280 1764022840 1784234921 1786654280 1835593744 1849372222 1875931624 1877593764 1899940939 2007896363 2023046907 2030492562 2032619034 2085680072 2085750388 2110824853 2123924948 2131327206 2134927760 2136423634] => 0
[1922985547 1934203179 1883318806 1910889055 1983590560 1965316186 2059139291 2075108931 2067514794 2117429526 2140519185 1659645051 1676816799 1611982084 1736461223 1810643297 1753583499 1767991311 1819386745 1355466982 1349603237 1360540003 1453750157 1461849199 1439893078 1432297529 1431882086 1427078318 1487887679 1484011617 1476718655 1509845392 1496496626 1583530675 1579588643 1609495371 1559139172 1554135669 1549766410 1566844751 1562161307 1561938937 1123551908 1086169529 1093103602 1202377124 1193780708 1148229310 1144649241 1257633250 1247607861 1241535002 1262624219 1288523504 1299222235 840314050 909401445 926048886 886867060 873099939 979662326 963003815 1012918112 1034467235 1026553732 568519178 650996158 647728822 616596108 617472393 614787483 604041145 633043809 678181561 698401105 776651230 325294125 271242551 291800692 389634988 346041163 344959554 345547011 342290228 354762650 442183586 467158857 412090528 532898841 534371187 32464799 21286066 109721665 127458375 192166356 146495963 142507512 167676030 236532616 262832772] => 1927544832
[1922985547 1934203179 1883318806 1910889055 1983590560 1965316186 2059139291 2075108931 2067514794 2117429526 2140519185 1659645051 1676816799 1611982084 1736461223 1810643297 1753583499 1767991311 1819386745 1355466982 1349603237 1360540003 1453750157 1461849199 1439893078 1432297529 1431882086 1427078318 1487887679 1484011617 1476718655 1509845392 1496496626 1583530675 1579588643 1609495371 1559139172 1554135669 1549766410 1566844751 1562161307 1561938937 1123551908 1086169529 1093103602 1202377124 1193780708 1148229310 1144649241 1257633250 1241535002 1247607861 1262624219 1288523504 1299222235 840314050 909401445 926048886 886867060 873099939 979662326 963003815 1012918112 1034467235 1026553732 568519178 650996158 647728822 616596108 617472393 614787483 604041145 633043809 678181561 698401105 776651230 325294125 271242551 291800692 389634988 346041163 344959554 345547011 342290228 354762650 442183586 467158857 412090528 532898841 534371187 32464799 21286066 109721665 127458375 192166356 146495963 142507512 167676030 236532616 262832772] => -1

```

Finally, here are four very large test cases to ensure that submissions are sufficiently efficient:

### Why would anyone do this?

It occurred to me the other day that a XOR operation can "sort" an array, which makes it possible to perform a binary search on the array in *O(log n)* without having to sort it first. It appears to be possible to determine `N` in pseudolinear time, which would make this a faster alternative to most sorting algorithms, and it doesn't have the memory requirements of radix sort. Of course, a straight linear search through the unsorted array will be faster, but if you want to search the same array many times, a single linear pre-computation can bring down the time required for each search significantly.

Unfortunately, the class of lists this works on is rather limited (uniformly random distributions are unlikely to admit an `N`).

An interesting question is whether there are other bijective functions which are easier to check and/or are applicable for a wider class of lists.

# Answer
> 8 votes
# Jelly, 25 bytes

```
ṡ2Zµ^/Bo1Ḅ‘×>/|/H
Ç-¹^Ç¥?

```

The latest commits postdate this challenge, but the above code works with this revision, which predates it. Try it online!

To run the large test cases, depending on your shell, it may be necessary to wrap the above code in a program that reads input from STDIN. Try it online!

### Test cases

```
$ xxd -c 13 -g 1 xort-prog.jelly
0000000: ae 32 5a 8c 5e 2f 42 6f 31 a4 b6 94 3e  .2Z.^/Bo1...>
000000d: 2f 7c 2f 48 0a 92 2d 8e 5e 92 84 3f     /|/H..-.^..?
$ ./jelly f xort-prog.jelly '[4, 7, 6, 1, 0, 3]'; echo
5
$ ./jelly f xort-prog.jelly '[4, 7, 1, 6, 0, 3]'; echo
-1
$ ./jelly f xort-prog.jelly '[0, 1, 3, 4, 6, 7]'; echo
0
$ ./jelly f xort-prog.jelly '[4, 2, 3, 1]'; echo
6
$ ./jelly f xort-prog.jelly '[2, 3, 0, 0, 7, 7, 4, 5, 11, 11]'; echo
2
$ ./jelly f xort-prog.jelly '[2, 3, 0, 0, 7, 7, 5, 4, 11, 11]'; echo
-1
$
$ wget -q http://pastebin.com/raw/{P96PNi79,zCNLMsx9,GFLBXn5b,6F1Yn3gG}
$ xxd -c 14 -g 1 xort-func.jelly
0000000: ae 32 5a 8c 5e 2f 42 6f 31 a4 b6 94 3e 2f  .2Z.^/Bo1...>/
000000e: 7c 2f 48 0a 92 2d 8e 5e 92 84 3f 0a a0 92  |/H..-.^..?...
$ tr \  , < P96PNi79 | time -f '\n%es' ./jelly f xort-func.jelly
-1
3.69s
$ tr \  , < zCNLMsx9 | time -f '\n%es' ./jelly f xort-func.jelly
0
2.78s
$ tr \  , < GFLBXn5b | time -f '\n%es' ./jelly f xort-func.jelly
1096442624
2.73s
$ tr \  , < 6F1Yn3gG | time -f '\n%es' ./jelly f xort-func.jelly
-1
2.70s

```

### Idea

This uses a the same approach as @Jakube's answer, but my implementation is a bit different.

Jelly has no sorting yet, so we compute a xorting candidate, XOR the input list with it, compute a xorting candidate of the XORed list, and check if the new candidate is zero. If it is, we print the first candidate; otherwise, we print **-1**.

Also, Jelly seems to have no sane way to cast to integer yet (even integer division can return floats), so I had to come up with a rather creative way of rounding a list of numbers down to the next power of **2**. Rather than log-floor-pow, I convert all integers to binary, replace all binary digits with **1**, convert back to integer, add **1**, and divide by **2**.

### Code

```
ṡ2Zµ^/Bo1Ḅ‘×>/|/H  Helper link. Argument: M (list of integers)

ṡ2                 Yield all overlapping slices of length 2 (pairs) of M.
  Z                Zip to group first and second coordinates.
   µ               Begin a new, monadic chain.
    ^/             XOR the corresponding coordinates.
      B            Convert all results to binary.
       o1          OR (logical) all binary digits with 1.
         Ḅ         Convert back to integer.
          ‘        Increment all integers.
           ×>/     Multiply each rounded (a ^ b) by (a > b).
                   This replaces (a ^ b) with 0 unless a > b.
              |/   OR all results.
                H  Halve the result.

Ç-¹^Ç¥?            Main link. Input: L (list of integers)

Ç                  Call the helper link on L. Result: C (integer)
     ¥             Create a dyadic chain:
   ^                 XOR the elements of L with C.
    Ç                Call the helper link on the result.
      ?            If the result in non-zero:
 -                   Yield -1.
  ¹                Else, yield C.

```

# Answer
> 36 votes
# Pyth, ~~40~~ ~~36~~ ~~31~~ 30 bytes

```
Ju.|G^2slHxMf>FT.:Q2Z|tSIxRJQJ

```

Try it online: Demonstration or Test Suite

Each of the big test-cases finishes in a couple of seconds.

### Explanation:

First I'll explain the method and why it works. I'll do this with the example list: `[7, 2, 13, 9]`.

The first two numbers are already wrong (`7 > 2`). We want to xor with some number to change that inequality symbol (`7 xor X < 2 xor X`). Since xor operates on the binary representations, lets look at them.

```
7 = 1 1 1
2 =   1 0

```

When we apply xor with some number to each number, the value at some positions will change. If you change the values at the first position (`2^0`), the inequality symbol doesn't change. The same thing happens, when we change the values at the second position (`2^1`). Also the symbol won't change if we change values at the fourth, fifth, ... positions (`2^3`, `2^4`, ...). The inequality symbol only changes direction, if we change the third position (`2^2`).

```
7 xor 2^0 = 1 1 0   7 xor 2^1 = 1 0 1   7 xor 2^2 =   1 1   7 xor 2^3 = 1 1 1 1
2 xor 2^0 =   1 1   2 xor 2^1 =     0   2 xor 2^2 = 1 1 0   2 xor 2^3 = 1 0 1 0
     6 > 3               5 > 0               3 < 6               15 > 10

```

If we change multiple positions at once, of course the same thing happens. If any of the positions we change is the third, than the inequality symbol changes, otherwise not.

The next pair is already sorted: `2 < 13`. If we look at the binary representation, we notice, that we can xor anything to it and the inequality symbol is still correct, except when we change the fourth position (`2^3`).

```
 2 =     1 0    2 xor 2^3 = 1 0 1 0
13 = 1 1 0 1   13 xor 2^3 =   1 0 1
   2 < 13            10 > 5

```

So we don't want to change the fourth position. For the next pair we want to change something, since `13 > 9`. Here we again have to change the third position.

```
13 = 1 1 0 1   13 xor 2^2 = 1 0 0 1
 9 = 1 0 0 1    9 xor 2^2 = 1 1 0 1
   13 > 9            9 < 13

```

Now recap: To end up in a sorted list, we again have to change the third position and don't want to change the fourth position. All other positions doesn't matter. The smallest number is simply `4 = 0100`. Other choices would be `5 = 0101`, `6 = 0110`, `7 = 0111`, `20 = 10100`, `21 = 10101`, ...

Xoring with `4` will result in the list `[3, 6, 9, 13]`, with `6` will get `[1, 4, 11, 15]`, and with `21` will get `[18, 23, 24, 28]`.

So for a list, we need to find the positions, that will change the inequality symbol if it points into the wrong direction. We find the position simply by taking the most significant bit of the xor of the pair. We combine all these position (with or) to result in a candidate number. The we check, if we haven't accidentally destroyed the already sorted pairs.

```
Ju.|G^2slHxMf>FT.:Q2Z   implicit: Q = input list
                .:Q2    all substrings of length 2
            f>FT        filter for pairs that are in descending order
          xM            apply xor to each such pair
 u                  Z   reduce this list, start value G = 0
                           iteration value is H
     ^2slH                 2 to the power of floor(logarithm base 2 of H)
                           this gives a mask representing the most significant bit
  .|G                      update G with the bitwise or of G and ^
J                       store the result in J

|tSIxRJQJ
    xRJQ      xor each element of the input list with J
  SI          check if the list is sorted
 t            subtract 1
|       J     this number or (if equal to zero) J
              implicit print

```

# Answer
> 15 votes
# Ruby 2, 119

```
->a,*o{a.each_cons(2){|x,y|x==y||o[i=(x^y).bit_length-1]==1-(o[i]=x[i])&&(return-1)};(o.map(&:to_i).reverse*'').to_i 2}

```

Runs in 42 milliseconds on the large test cases.

Ungolfed:

```
def first_differing_bit(a,b)
  (a^b).bit_length - 1
end

def xort(ary)
  required_bits = []
  ary.each_cons(2) do |a,b|
    i = first_differing_bit(a,b)
    if i > -1
      bit = a[i]
      if required_bits[i] && required_bits[i] != bit
        return -1
      else
        required_bits[i] = bit
      end
    end
  end
  required_bits.map(&:to_i).reverse.join.to_i(2)
end

```

For once I wrote the ungolfed version first, then golfed it, since figuring out the right algorithm was a challenge in itself.

I actually tried to write something like this a few years ago to make a binary tree structure that would locally self-balance by letting each node redefine its comparison function dynamically. At first I thought I could just use xor, but as you say for random data there's unlikely to be a viable value.

# Answer
> 11 votes
# Julia, ~~174~~ ~~144~~ ~~77~~ ~~75~~ 71

\[EDIT\] Thanks to Alex A. for anonymizing & various shorthands.
\[EDIT 2\] Replaced my own implementation by the builtin `issorted()`.

Runs in linear time and handles the big files without noticeable delay. Works just as well for negative numbers.

```
l->(r=0;s=issorted;for d=63:-1:0 s((l$r).>>d)||(r$=2^d)end;s(l$r)?r:[])

```

Another variant that calculates the result closest to a given key (the above returns the smallest).

```
(l,r)->(s=issorted;for d=63:-1:0 s((l$r).>>d)||(r$=2^d)end;s(l$r)?r:[])

```

usage:

```
julia> xort = l->(r=0;s=issorted;for d=63:-1:0 s((l$r).>>d)||(r$=2^d)end;s(l$r)?r:[])
(anonymous function)

julia> xort([4 7 6 1 0 3])
5

```

Example, step by step: `[4 7 6 1 0 3] => 5`

```
Start with:
     4  0b0100
     7  0b0111
     6  0b0110
     1  0b0001
     0  0b0000
     3  0b0011
result  0b0000

If the first n bits are sorted, do nothing.
        0b0
        0b0
        0b0
        0b0
        0b0
        0b0
result  0b0000
          ^
If the first n bits are not sorted, flip the nth bit.
        0b01            0b00
        0b01            0b00
        0b01            0b00
        0b00      =>    0b01
        0b00            0b01
        0b00            0b01
result  0b0000          0b0100
           ^               ^
        0b000
        0b001
        0b001
        0b010
        0b010
        0b011
result  0b0100
            ^
        0b0000          0b0001  1
        0b0011          0b0010  2
        0b0010          0b0011  3
        0b0101    =>    0b0100  4
        0b0100          0b0101  5
        0b0111          0b0110  6
result  0b0100          0b0101  5
             ^               ^
If the bit flip does not sort the truncated integers, xorting is
impossible. We continue anyway and check for success in the end.

```

# Answer
> 8 votes
# JavaScript (ES6) 85 ~~97 114 117~~

**Edit** Removed stupid,useless last AND
**Edit2** Top bit search shortened
**Edit3** Wow! I discovered that ES6 (almost) has a *builtin* to find the top bit (Math.clz32 counts the top 0 bits)

This is based on the solution of @Jakube (pls upvote that). I could never have found it by myself.

Here I go one step forward, iterating the list once and keeping a bit mask with the bits that have to be flipped, and another one with the bits that have to be kept.

If there is an overlap of the bit masks, then no solution is possible, else the solution is "bits to flip"

As binary operations in javascript work only on signed 32 bits integers, the return value is a signed 32 bit integer that can be negative or 0.

If there is no solution the return value is 'X'

```
l=>l.map(v=>(t=v^p&&1<<(31-Math.clz32(v^p)),v>p?k|=t:c|=t,p=v),p=l[c=k=0])&&c&k?"X":c

```

**Test**

The longer tests on jsfiddle

```
X=l=>l.map(v=>(t=v^p&&1<<(31-Math.clz32(v^p)),v>p?k|=t:c|=t,p=v),p=l[c=k=0])&&c&k?"X":c

console.log=x=>O.textContent+=x+'\n'
;[
[[4,7,6,1,0,3], 5],
[[4,7,1,6,0,3], 'X'],
[[0,1,3,4,6,7], 0],
[[4,2,3,1], 6],
[[2,3,0,0,7,7,4,5,11,11], 2],
[[2,3,0,0,7,7,5,4,11,11], 'X'],
[[1086101479,748947367,1767817317,656404978,1818793883,1143500039],'X'],
[[180522983,1885393660,751646477,367706848,331742205,724919510,850844696,2121330641,869882699,1831158987,542636180,1117249765,823387844,731663826,1762069894,240170102,1020696223,1212052937,2041219958,712044033,195249879,1871889904,1787674355,1849980586,1308879787,1743053674,1496763661,607071669,1987302942,178202560,1666170841,1035995406,75303032,1755269469,200581873,500680130,561748675,1749521426,1828237297,835004548,934883150,38711700,1978960635,209243689,1355970350,546308601,590319412,959613996,1956169400,140411967,112601925,88760619,1977727497,672943813,909069787,318174568,385280382,370710480,809689639,557034312,865578556,217468424,346250334,388513751,717158057,941441272,437016122,196344643,379529969,821549457,97008503,872313181,2105942402,603939495,143590999,1580192283,177939344,853074291,1288703007,1605552664,162070930,1325694479,850975127,681702163,1432762307,1994488829,780869518,4379756,602743458,1963508385,2115219284,1219523498,559301490,4191682,1918142271,169309431,346461371,1619467789,1521741606,1881525154],'X'],
[[37580156,64423492,87193676,91914964,93632157,96332899,154427982,176139560,184435039,228963836,230164674,279802291,301492375,309127664,345705721,370150824,380319820,403997410,410504675,416543032,418193132,424733526,428149607,435596038,477224208,515649925,519407995,525469350,614538124,624884850,642649261,653488151,679260270,685637235,690613185,739141066,825795124,832026691,832633584,833213619,852655299,913744258,917674993,921902522,925691996,931307936,954676047,972992595,997654606,1020009811,1027484648,1052748108,1071580605,1108881241,1113730139,1122392118,1154042251,1170901568,1180031842,1180186856,1206428383,1214066097,1242934611,1243983997,1244736049,1262979035,1312007069,1312030297,1356274316,1368442960,1377432523,1415342434,1471294243,1529353536,1537868913,1566069818,1610578189,1612277199,1613646498,1639183592,1668015280,1764022840,1784234921,1786654280,1835593744,1849372222,1875931624,1877593764,1899940939,2007896363,2023046907,2030492562,2032619034,2085680072,2085750388,2110824853,2123924948,2131327206,2134927760,2136423634],0],
[[1922985547,1934203179,1883318806,1910889055,1983590560,1965316186,2059139291,2075108931,2067514794,2117429526,2140519185,1659645051,1676816799,1611982084,1736461223,1810643297,1753583499,1767991311,1819386745,1355466982,1349603237,1360540003,1453750157,1461849199,1439893078,1432297529,1431882086,1427078318,1487887679,1484011617,1476718655,1509845392,1496496626,1583530675,1579588643,1609495371,1559139172,1554135669,1549766410,1566844751,1562161307,1561938937,1123551908,1086169529,1093103602,1202377124,1193780708,1148229310,1144649241,1257633250,1247607861,1241535002,1262624219,1288523504,1299222235,840314050,909401445,926048886,886867060,873099939,979662326,963003815,1012918112,1034467235,1026553732,568519178,650996158,647728822,616596108,617472393,614787483,604041145,633043809,678181561,698401105,776651230,325294125,271242551,291800692,389634988,346041163,344959554,345547011,342290228,354762650,442183586,467158857,412090528,532898841,534371187,32464799,21286066,109721665,127458375,192166356,146495963,142507512,167676030,236532616,262832772],1927544832],
[[1922985547,1934203179,1883318806,1910889055,1983590560,1965316186,2059139291,2075108931,2067514794,2117429526,2140519185,1659645051,1676816799,1611982084,1736461223,1810643297,1753583499,1767991311,1819386745,1355466982,1349603237,1360540003,1453750157,1461849199,1439893078,1432297529,1431882086,1427078318,1487887679,1484011617,1476718655,1509845392,1496496626,1583530675,1579588643,1609495371,1559139172,1554135669,1549766410,1566844751,1562161307,1561938937,1123551908,1086169529,1093103602,1202377124,1193780708,1148229310,1144649241,1257633250,1241535002,1247607861,1262624219,1288523504,1299222235,840314050,909401445,926048886,886867060,873099939,979662326,963003815,1012918112,1034467235,1026553732,568519178,650996158,647728822,616596108,617472393,614787483,604041145,633043809,678181561,698401105,776651230,325294125,271242551,291800692,389634988,346041163,344959554,345547011,342290228,354762650,442183586,467158857,412090528,532898841,534371187,32464799,21286066,109721665,127458375,192166356,146495963,142507512,167676030,236532616,262832772],'X']
].forEach(t=>{
  var i=t[0],k=t[1],r=X(i)
  console.log((k==r?'OK ':'Error (expected '+k+') ')+r+' for input '+i)
})
```

```
<pre id=O></pre>
```

# Answer
> 8 votes
## ES6, 84 bytes

```
a=>(i=e=0,a.reduce((x,y)=>(z=1<<31-Math.clz32(x^y),x>y?i|=z:y>x?e|=z:z,y)),i&e?-1:i)

```

Edit: By the time it took me to write the answer the algorithm had already been independently posted by @Jakube; my algorithm is the same but this wasn't plagiarism honest! Also I notice another JavaScript answer has since been posted too. Sorry if I'm stepping on anyone's toes.

Edit: Saved 8 bytes thanks to edc65.

# Answer
> 5 votes
# C, 144 bytes

```
#include <strings.h>
#include <stdio.h>
m[2],l,i;main(v){while(scanf("%d",&v)==1)m[l<v]|=(i++&&v^l)<<~-fls(v^l),l=v;printf("%d",*m&m[1]?-1:*m);}

```

This is almost standard C99 (it misses a few `int` specifiers and has 1 argument for `main`). It also relies on `0<<-1` being 0 (which seems to be true when compiled with Clang at least — I haven't tested others)

I've taken Jakube's method and ported it to C. I think it does surprisingly well size-wise for C. It's also super-fast (0.061s to run all test files, including the massive 4). It takes input from STDIN and will print the matching value or -1 to STDOUT, so run it with one of:

```
echo "4 7 6 1 0 0 3" | ./xort
./xort < file.txt

```

Breakdown:

```
// Globals initialise to 0
m[2],                                    // Stores our bit masks
                                         // (m[0]=CHANGE, m[1]=MUST NOT CHANGE)
l,                                       // Last value
i;                                       // Current iteration
main(v){
    while(scanf("%d",&v)==1)             // Read each value in turn
        m[l<v]|=                         // If they are sorted, we mark a bit as
                                         // MUST NOT CHANGE (m[1]), otherwise we
                                         // mark as CHANGE (m[0])
                (i++&&v^l)               // If this is the first iteration,
                                         // or the value is unchanged, mark nothing
                          <<~-fls(v^l),  // Mark the highest bit which has changed
                                         // = (1<<(fls(v^l)-1)
        l=v;                             // Update last value
    printf("%d",
                *m&m[1]                  // Check if result is valid (if any bits
                                         // are both MUST NOT CHANGE and CHANGE,
                                         // it is not valid)
                       ?-1               // Print -1 on failure
                          :*m);          // Print value on success
}

```

# Answer
> 4 votes
# Julia, 124 bytes

```
f(x,g=0)=issorted(([g|=2^Int(log2(h)÷1)for h=map(k->k[1]$k[2],filter(j->j[1]>=j[2],[x[i-1:i]for i=2:endof(x)]))];g)$x)?g:-1

```

This is a function that accepts an integer array and returns an integer. It uses Jakube's approach.

Ungolfed:

```
function f{T<:Integer}(x::Array{T,1}, g::T=0)
    # Get all pairs of elements in the input array
    pairs = [x[i-1:i] for i = 2:endof(x)]

    # Filter to pairs in descending order
    desc = filter(j -> j[1] ≥ j[2], pairs)

    # Map XOR over these pairs
    xord = map(k -> k[1] $ k[2], desc)

    # For each element of this array, update the
    # parameter g (which defaults to 0) as the
    # bitwise OR of itself and 2^floor(log2(element))
    for h in xord
        g |= 2^Int(log2(h) ÷ 1)
    end

    # If the array constructed as g XOR the input is
    # sorted, we've found our answer! Otherwise -1.
    return issorted(g $ x) ? g : -1
end

```

# Answer
> 3 votes
## CJam, 37 bytes

```
q~_2ew{:>},{:^2mLi2\#}%0+:|_@f^_$=\W?

```

Test it here.

This uses the same algorithm as several of the other answers. It's essentially my reference implementation which I used to create the test cases. However, I did steal Jakube's trick of checking only the offending pairs and simply trying out the result with a sort. That breaks the pseudolinearity, but *O(n log n)* is still fast enough for the test cases. My original code also checked the pairs that are already in order, and built up a list of bits which must not be toggled in order to keep their relative order, and checked at the end that there are no overlaps between the two bit masks. This algorithm was originally suggested by Ben Jackson.

# Answer
> 3 votes
# Python 2, 204 bytes

```
def f(a):
 m=n=0
 for i in range(32):
  b=2**(31-i);m|=b
  for n in[n,n|b]:
   if not q(a,m,n):break
  else:return-1
 return n
def q(a,m,n):
 if a:p=a[0]&m^n
 for t in a:
  t=t&m^n
  if t<p:return 1
  p=t

```

The input is passed as a list to function f.

This code figures out the value of N (named n in the program) one bit at a time, starting with the most significant bit. (the "for i" loop)

For each bit position, the "for n" loop first tries using 0 for that bit of n. If that doesn't work, it tries using 1. If neither of these works, then there is no solution. Note that the else clause is on the "for n" loop, not the if statement. In Python, a for statement can have an else clause, which is executed after the loop runs to completion, but is *not* executed if we break out of the loop.

The q function checks for problems with the list order given the list (a), a bit mask (m), and the value to be xored with each value in the list (n). It returns 1 if there is a problem with the ordering, or None if the order is ok. None is the default return value, so that saved me several characters.

This code handles an empty list or a list with 1 element correctly, returning 0. The "if a:" in function q is there only to avoid an IndexError exception when the list is empty. So 5 more bytes could be removed if handling empty lists isn't required.

On my computer, large test case #3 took 0.262 seconds. #2 took about the same. All the test cases together took 0.765 seconds.

# Answer
> 2 votes
# Python 2, ~~226~~ 214 bytes

Simpleish algorithm, built it yesterday, golfed today.

```
o=input()
s=sorted
p=s(set(o),key=o.index)
n=q=0
while 1:
 a=1
 while 1-q and p[0]<p[1]:p=p[1:];q=len(p)==1
 if q:break
 while not p[0]^a<p[1]^a:a*=2
 n+=a;p=[i^a for i in p]
t=[a^n for a in o]
print[-1,n][s(t)==t]

```

Ungolfed:

```
def xor(a,b): return a^b

def rm_dupes(seq):
    seen = set()
    seen_add = seen.add
    return [x for x in seq if not (x in seen or seen_add(x))]

def rm_sorted(seq):
    while seq[0] < seq[1]:
        seq = seq[1:]
        if len(seq) == 1: return seq
    return seq

inp = input()
oi = inp

inp = rm_dupes(inp)
n=0
old_inp=0
while old_inp != inp:
    old_inp = inp
    inp = rm_sorted(inp)
    if len(inp)==1:break
    highest_set0 = len(bin(inp[0]))-3 # bin returns in form 0bxxx
    highest_set1 = len(bin(inp[1]))-3 # bin returns in form 0bxxx
    if highest_set1 == 0:
        try:
            t0 = max(int(bin(inp[0])[3:], 2), 1)
        except ValueError: toggle_amount = 1
        else: toggle_amount = t0^inp[0]
    else:
        fallen = False
        for i in xrange(max(highest_set0,highest_set1)+1):
            toggle_amount = 2**i
            if inp[0]^toggle_amount < inp[1]^toggle_amount:
                fallen = True
                break
        assert(fallen)
    n+=toggle_amount
    inp = [i^toggle_amount for i in inp]

out=map(xor, oi, [n]*len(oi))
if sorted(out)==out :print n
else:print -1

```

# Answer
> 2 votes
# C, 312 bytes

```
#define R return
t,i,*b;f(int*a,int l,int k){int s=a[0]>>k&1,j=-1,i=1;if(k<0)R 0;for(;i<l;++i){t=a[i]>>k&1;if(s!=t)if(j<0)j=i,s=t;else R 1;}if(j<0)R f(a,l,k-1);else{if(s+b[k]==2)R 1;b[k]=s+1;R f(a,j,--k)||f(a+j,l-j,k);}}h(int*a,int l){int c[32]={0};b=c;if(f(a,l,30))R -1;t=0;for(i=0;i<32;++i)t|=(b[i]&1)<<i;R t;}

```

Defines a function `h(int*a,int l)` taking a pointer to an array and its length. Here is a test program behemoth.

Slightly ungolfed:

```
int t, i, *b;

int f(int * a, int l, int k) {
    int s = a[0] >> k & 1;
    int j = -1;
    int i = 1;
    if (k < 0) return 0;
    for (; i < l; ++i) {
        t = a[i] >> k & 1;
        if (s != t) {
            if (j < 0) {
                j = i;
                s = t;
            } else return 1;
        }
    }
    if (j < 0) {
        return f(a, l, k - 1);
    } else {
        if (s + b[k] == 2) return 1;
        b[k] = s + 1;
        return f(a, j, --k) || f(a + j, l - j, k);
    }
}

int h(int * a, int l) {
    int c[32] = {0};
    b = c;
    if (f(a, l, 30)) return -1;
    t = 0;
    for (i = 0; i < 32; ++i) {
        t |= (b[i] & 1) << i;
    }
    return t;
}

```

# Answer
> 2 votes
# Mathematica, 99 97 Characters

Thanks to Martin Büttner for advices.

```
x@l_:=If[OrderedQ[l~BitXor~#],#,-1]&@Fold[#+#2Boole@!OrderedQ@⌊l~BitXor~#/#2⌋&,0,2^32/2^Range@32]

```

**Explanation:**

We will do multiple tries to modify `N` starting from zero, and do a test to validate the candidate `N`.

*Step 1.* We get these numbers (32-bit integers) "xor"ed by `N`(`= 0` now) and divided by `2^31`: `⌊l~BitXor~#/#2⌋`. There are three cases:

* ordered, e.g. `{0, 0, 1, 1, 1, 1, 1, 1}`;
* can be corrected, e.g. `{1, 1, 1, 1, 0, 0, 0, 0}`;
* else, e.g. `{0, 0, 1, 0, 0, 1, 1, 1}`.

We do nothing to `N` for the first case, or we add `2^31` to `N` to correct the order for the second case: `#+#2Boole@!OrderedQ@...`. While for the third case, it is impossible to xorting the list what ever we do, thus we just add `2^31` to `N` for simplicity (or anything!).

*Step 2.* We get these numbers "xor"ed by `N` and divided by `2^30`. There are again three cases:

* ordered, e.g. `{0, 1, 2, 2, 2, 2, 3, 3}`;
* can be corrected, e.g. `{1, 1 , 0, 0, 3, 2, 2, 2}`;
* else, e.g. `{3, 3, 1, 3, 2, 0, 1, 0}`.

We do nothing to `N` for the first case, or we add `2^30` to `N` to correct the order for the second case. Otherwise, we realize that xorting is impossible, thus we just add `2^30` to `N` for simplicity again.

*Step 3 ~ 32.* We recursively get these numbers "xor"ed by `N` and divided by `2^29`, `2^28`, ..., `2^0`. And do similar things: `Fold[...,0,2^32/2^Range[32]]`

*Step 33.* Now we finally get a candidate `N`. `If[OrderedQ[l~BitXor~#],#,-1]&` is used to check if such `N` indeed xorting the list. If the list can be xorting by some `N`, it is not difficult to proof that we will always encounter the first or the second case.

# Answer
> 2 votes
# Perl 6, 79 bytes

If there wasn't a time limit the shortest Perl 6 code would probably be

```
{first {[<=] $_ X+^@_},^2*.max} # 31 bytes

```

---

Instead I have to do something a bit more clever.
Since I took a while to come back to this, there was already an answer that describes a good algorithm, and the reasoning behind it.

```
{$/=0;for @_.rotor(2=>-1) ->(\a,\b){b>=a or$/+|=2**msb a+^b};$/if [<=] $/X+^@_} # 79

```

```
{
  # cheat by using a special variable
  # so there is no need to declare it
  $/=0;

  # takes the elements two at a time, backing up one
  for @_.rotor(2=>-1)
    # since that is a non-flat list, desugar each element into 2
    # terms
    ->(\a,\b){
      # if they are not sorted
      b>=a or
      # take the most significant bit of xoring the two values
      # and numeric or ｢+|｣ it into ｢$/｣
      $/+|=2**msb a+^b
    };

  # returns ｢$/｣ if the list is Xorted
  # otherwise returns Empty
  $/if [<=] $/X+^@_

  # ｢ $/ X[+^] @_ ｣
  # does numeric xor ｢+^｣ between ｢$/｣
  # and each element of the original list ｢@_｣
}

```

Usage:

```
# give it a lexical name for ease of use
my &code = {...}

say code [8,4,3,2,1];     # 15

say code [4,7,6,1,0,3]; # 5
say code [4,7,1,6,0,3]; # ()
say code [0,1,3,4,6,7]; # 0
say code [4,2,3,1];     # 6
say code [2,3,0,0,7,7,4,5,11,11]; # 2
say code [2,3,0,0,7,7,5,4,11,11]; # ()
say code [1086101479,748947367,1767817317,656404978,1818793883,1143500039]; # ()

# the example files
for 'testfiles'.IO.dir.sort».comb(/«\d+»/) {
  printf "%10s in %5.2f secs\n", code( @$_ ).gist, now - ENTER now;
}
#         () in  9.99 secs
#          0 in 11.70 secs
# 1096442624 in 13.54 secs
#         () in 11.44 secs

```

# Answer
> 1 votes
# Mathematica ~~650 415~~ 194 bytes

This challenge helped me understand quite a bit about `Xor` that I had never thought about. It took a long time to whittle down the code, but was worth the effort.

`BitXor` works directly on base 10 numbers. This greatly reduced the code from the earlier versions.

The logic is simple. One works, not with pairs of numbers (as some submissions did) but rather with the complete set of numbers after being `BitXor`ed with the current "key".

Start with tentative solution, or "key" of zero, that is with all bits are zero. When the original `n` numbers are `BitXor`ed with zero , they are returned, unaltered. Correlate the ordering of the numbers with the range`1, 2, ...n`, which represent a perfectly ordered list. The correlation, with a value between -1 and 1, reflects how well the numbers are ordered.

Then set the hi bit, obtain the new key, and `BitXor` the key with the current set of numbers. If the correlation between the new sequence of numbers and the perfectly ordered list is an improvement, keep the bit set. If not, leave the bit unset.

Proceed in this manner from the hi to the low bit. If the best correlation is 1, then the key is the solution. If not, it is -1.

There would be ways to make the code a bit more efficient, for example, by interrupting the process as soon as a solution is found, but this would require more coding and the current approach is very fast as it is. (The final and longest test case takes 20 msec.)

```
c@i_:=Correlation[Ordering@i,Range[Length[i]]]//N;
t@{i_,k_,b_,w_}:=(v= c@BitXor[i,m=k+2^(b-1)];{i,If[v>w,m,k],b-1,v~Max~w})
g@i_:= (If[#4==1,#2,-1] &@@Nest[t,{i,0,b=1+Floor@Log[2,Max@i],x=c@i},b])

```

---

```
g[{4, 7, 6, 1, 0, 3}]

```

> 5

---

```
g[{4, 7, 1, 6, 0, 3}]

```

> -1

---

```
g2@{0, 1, 3, 4, 6, 7}

```

> 0

---

```
g@{1922985547, 1934203179, 1883318806, 1910889055, 1983590560, 1965316186,2059139291, 2075108931, 2067514794, 2117429526, 2140519185, 1659645051, 1676816799, 1611982084, 1736461223, 1810643297, 1753583499, 1767991311, 1819386745, 1355466982, 1349603237, 1360540003, 1453750157, 1461849199, 1439893078, 1432297529, 1431882086, 1427078318, 1487887679, 1484011617, 1476718655, 1509845392, 1496496626, 1583530675, 1579588643, 1609495371, 1559139172, 1554135669, 1549766410, 1566844751, 1562161307,1561938937, 1123551908, 1086169529, 1093103602, 1202377124, 1193780708, 1148229310, 1144649241, 1257633250, 1247607861, 1241535002, 1262624219, 1288523504, 1299222235,840314050, 909401445, 926048886, 886867060, 873099939, 979662326,963003815, 1012918112, 1034467235, 1026553732, 568519178, 650996158,647728822, 616596108, 617472393, 614787483, 604041145, 633043809, 678181561, 698401105, 776651230, 325294125, 271242551, 291800692, 389634988, 346041163, 344959554, 345547011, 342290228, 354762650, 442183586, 467158857, 412090528, 532898841, 534371187, 32464799, 21286066, 109721665, 127458375, 192166356, 146495963, 142507512, 167676030, 236532616, 262832772}

```

> 1927544832

# Answer
> 1 votes
# Add++, ~~125~~ 119 bytes

```
D,g,@@,BxBBBDbU1€oB]BJ2$Bb1+
D,j,@,bUBSVcGbU£{g}B]BkAbUBSVcGbU£>B]BKBcB*¦Bo2/i
L!,B#a=
D,f,?!,{j}Vad{j}BF€Bx1]G$0=-1$Qp

```

Try it online!

<sub>I am actually really proud that Add++ is able to do this, and isn't the longest solution here</sub>

Declares a function `f` that takes each element as a separate argument (e.g. `$f>4>2>3>1`)

## How it works

Buckle up folks, it's going to be a long ride

```
D,g,@@,		; Declare a function 'g'
		; Example arguments: 		[4 7]
	Bx	; Xor;			STACK = [3]
	BB	; To binary;		STACK = [11]
	BD	; Digits;		STACK = [[1 1]]
	bU	; Unpack;		STACK = [1 1]
	1€o	; Replace 0s with 1s;	STACK = [1 1]
	B]	; Wrap;			STACK = [[1 1]]
	BJ	; Concatenate;		STACK = ['11']
	2$Bb	; From binary;		STACK = [3]
	1+	; Increment;		STACK = [4]
		;			Return   4

D,j,@,		; Declare a function 'j'
		; Example argument:		[[4 7 6 1 0 3]]
	bU	; Unpack;		STACK = [4 7 6 1 0 3]
	BS	; Overlapping pairs;	STACK = [4 7 6 1 0 3 [[4 7] [4 6] [6 1] [1 0] [0 3]]]
	VcG	; Keep first element;	STACK = [[[4 7] [4 6] [6 1] [1 0] [0 3]]]
	bU	; Unpack;		STACK = [[4 7] [4 6] [6 1] [1 0] [0 3]]
	£{g}	; Apply 'g' over each;	STACK = [4 2 8 2 4]
	B]	; Wrap;			STACK = [[4 2 8 2 4]]
	Bk	; Global save;		STACK = []		; GLOBAL = [4 2 8 2 4]
	A	; Push arguments;	STACK = [[4 7 6 1 0 3]]
	bU	; Unpack;		STACK = [4 7 6 1 0 3]
	BSVcGbU	; Overlapping pairs;	STACK = [[4 7] [4 6] [6 1] [1 0] [0 3]]
	£>	; Greater than each;	STACK = [0 1 1 1 0]
	B]	; Wrap;			STACK = [[0 1 1 1 0]]
	BK	; Global get;		STACK = [[0 1 1 1 0] [4 2 8 2 4]]
	BcB*	; Products;		STACK = [[0 2 8 2 0]]
	¦Bo	; Reduce by logical OR;	STACK = [10]
	2/i	; Halve;		STACK = [5]
		;			Return   5

L!,		; Declare 'lambda 1'
		; Example argument:		[[1 2 3 4 5]]
	B#	; Sort;			STACK = [[1 2 3 4 5]]
	a=	; Equal to argument;	STACK = [1]
		; 			Return   1

D,f,?!,		; Declare a function 'f'
		; Example arguments:		[[4 7 6 1 0 3]]
	{j}	; Call 'j';		STACK = [5]
	V	; Save;			STACK = []		; REGISTER = 5
	ad	; Push arguments twice;	STACK = [[4 7 6 1 0 3] [4 7 6 1 0 3]]
	{j}	; Call 'j';		STACK = [[4 7 6 1 0 3] 5]
	BF	; Flatten;		STACK = [4 7 6 1 0 3 5]
	€Bx	; Xor each with 5;	STACK = [1 2 3 4 5 6]
	1]	; Call 'lambda 1';	STACK = [1]
	G$	; Retrieve REGISTER;	STACK = [5 1]
	0=	; If equal to 0:
	-1$Q	;   Return -1
	p	; Else, pop condition;	STACK = [5]
		;			Return   5

```

# Answer
> 1 votes
# Stax, 29 bytes

```
¬√▬ⁿ{j╔■α√ï(íP♫_z(.▀ng▒JU↨@b┬

```

Run and debug online!

Uses @RainerP.'s solution (came up with the flipping bit part independently but uses the `32rr` part)

Linear time complexity.

Uses the unpacked version to explain.

```
32rr{|2Y;{y/m:^!c{,{y|^m~}Mm,:^ud:b
32rr                                   Range [32,31..0]
    {                      m           Map each number `k` in the range with
     |2Y                                   `2^k`
        ;{y/m                              Map each number `l` in the input to `floor(l/2^k)`
             :^!                           The mapped array is not non-decreasing
                                           This is the binary digit `l` is mapped to
                c{       }M                If that's true, do
                  ,{y|^m~                  Flip the corresponding bit of every element in the input
                            ,:^        The final array is sorted
                               ud      Take inverse and discard, if the final array is not sorted this results in zero-division error
                                 :b    Convert mapped binary to integer

```

# Answer
> 1 votes
# Japt, 11 bytes

(Eventually) Outputs `undefined` for falsey inputs.

```
@Ë^XÃäÎø1}f

```

Try it

```
@Ë^XÃäÎø1}f     :Implicit input of array U
@               :Function taking an integer X as argument
 Ë              :  Map U
  ^X            :    XOR X
    Ã           :  End map
     ä          :  Consecutive pairs
      Î         :  Signs of differences
       ø1       :  Contains 1?
         }      :End function
          f     :Get the first X>=0 that returns false

```

---
Tags: code-golf, array, sorting, bitwise
---


title: Triangular Square Numbers

text:
# Question
Title: Triangular Square Numbers
Square numbers are those that take the form of \\$n^2\\$ where \\$n\\$ is an integer. These are also called perfect squares, because when you take their square root you get an integer.

The first 10 square numbers are: (OEIS)

`0, 1, 4, 9, 16, 25, 36, 49, 64, 81`

---

Triangular numbers are numbers that can form an equilateral triangle. The n-th triangle number is equal to the sum of all natural numbers from 1 to n.

The first 10 triangular numbers are: (OEIS)

`0, 1, 3, 6, 10, 15, 21, 28, 36, 45`

---

Square triangular numbers are numbers that are both square and triangular.

The first 10 square triangular numbers are: (OEIS)

`0, 1, 36, 1225, 41616, 1413721, 48024900, 1631432881, 55420693056, 1882672131025, 63955431761796`

---

There is an infinite number of square numbers, triangle numbers, and square triangular numbers.

Write a program or named function that given an input (parameter or stdin) number \\$n\\$, calculates the \\$n\\$th square triangular number and outputs/returns it, where n is a positive nonzero number. (For \\$n=1\\$ return 0)

For the program/function to be a valid submission it should be able to return at least all square triangle numbers smaller than \\$2^{31}-1\\$.

# Bonus

-4 bytes for being able to output all square triangular numbers less than 2^63-1

-4 bytes for being able to theoretically output square triangular numbers of any size.

~~+8 byte penalty for solutions that take nonpolynomial time.~~

Bonuses stack.

This is code-golf challenge, so the answer with the fewest bytes wins.

# Answer
> 8 votes
# CJam, ~~12~~ 8 bytes

```
XUri{_34*@-Y+}*;

```

Makes use of the recurrence relation from the Wikipedia article.

The code is 16 bytes long and qualifies for both bonuses.

Try it online in the CJam interpreter.

### How it works

My code turned out to be identical to xnor's in always every aspect, except that I use CJam's stack instead of variables.

```
XU               e# Push 1 and 0 on the stack.
                 e# Since 34 * 0 - 1 + 2 = 1, this compensates for 1-based indexing.
  ri{        }*  e# Do int(input()) times:
     _34*        e#   Copy the topmost integer and multiply it by 34.
         @-      e#   Subtract the bottommost integer from the result.
           Y+    e#   Add 2.
               ; e# Discard the last result.

```

# Answer
> 8 votes
## Python 2, 45 - 4 - 4 = 37

```
a=1;b=0
exec"a,b=b,34*b-a+2;"*input()
print a

```

Iterates using the reccurence

```
f(0) = 1
f(1) = 0
f(k) = 34*f(k-1)-f(k-2)+2

```

In theory, this supports numbers of any size, but runs in exponential time, so it shouldn't qualify for the bonuses. Should work for numbers of any size. For example, for 100, gives

```
1185827220993342542557325920096705939276583904852110550753333094088280194260929920844987597980616456388639477930416411849864965254621398934978872054025

```

A recursive solution uses 41 chars, but shouldn't qualify because it takes exponential time.

```
f=lambda k:k>2and 34*f(k-1)-f(k-2)+2or~-k

```

# Answer
> 7 votes
# Pyth, 16 - 4 - 4 = 8 bytes

Uses the recursive formula from the OEIS article.

```
K1uhh-*34G~KGtQZ

```

It uses the post-assign command which is pretty new and seems really cool. Uses reduce to iterate `n-1` times because of 1-based indexing.

```
K1            Set K=1
u       tQ    Reduce input()-1 times
         Z    With zero as base case
 hh            +2
  -           Subtract
   *34G       34 times iterating variable
   ~K         Assign to K and use old value
    G         Assign the iterating variable.

```

Seems to be polynomial because it loops n times and does math & assignment each iteration, but I'm not a computer scientist. Finishes n=10000 almost instantly.

Try it here online.

# Answer
> 5 votes
# Oasis, 7 - 4 - 4 = -1

```
34*c-»T

```

Try it online!

Uses `a(0) = 0, a(1) = 1; for n >= 2, a(n) = 34 * a(n-1) - a(n-2) + 2`

Oasis supports arbitrary precision integers, so it should be able to go up to any number so long as no stack overflowing occurs. Let me know if this does not count for the bonus because of stack overflowing. It is also possible that this particular algorithm is non-polynomial, and let me know if that is the case.

Explanation:

```
34*c-»T -> 34*c-»10

a(0) = 0
a(1) = 1
a(n) = 34*c-»

34*c-»
34*    # 34*a(n-1)
   c-  # 34*a(n-1)-a(n-2)
     » # 34*a(n-1)-a(n-2)+2

```

---

Alternative solution:

```
-35*d+T

```

Instead uses `a(n) = 35*(a(n-1)-a(n-2)) + a(n-3)`

# Answer
> 4 votes
# JavaScript (ES6), 29-4 = 25 bytes

```
n=>n>1?34*f(n-1)-f(n-2)+2:n|0

```

Saved 5 bytes thanks to *@IsmaelMiguel*!

I've had to hardcode the 0, 1 and the negatives to avoid infinite recursion.

Console, I've named the function, `f`:

```
f(1);  // 0
f(13); // 73804512832419600
f(30); // 7.885505171090779e+42 or 7885505171090779000000000000000000000000000

```

**EDIT**: Turns out JavaScript will round the numbers to 16 (15) digits (Spec) because these numbers are too big causing an overflow. Put 714341252076979033 In your JavaScript console and see for yourself. It's more of a limitation of JavaScript

# Answer
> 3 votes
### Excel VBA - 90 bytes

Using the recurrence relation from the Wikipedia page:

```
n = InputBox("n")
x = 0
y = 1
For i = 1 To n
Cells(i, 1) = x
r = 34 * y - x + 2
x = y
y = r
Next i

```

When executed you are prompted for n, then the sequence up to and including n is output to column A:

It can be run up to and including n = 202 before it gives an overflow error.

# Answer
> 2 votes
# \[Not Competing\] Pyth (14 - 4 - 4 = 6 bytes)

```
K1u/^tG2~KGQ36

```

Used the first recurrence from OEIS, that after 0,1,36 you can find An = (An-1-1)2/An-2. A Not competing because this solution starts at 36, if you go lower you divide by zero (so input of 0 gives 36). Also had to hardcode 36.

Try it here

# Answer
> 2 votes
# Java, 53 - 4 = 49 bytes

It's another simple recursion, but I don't often get to post Java with a \<50 score, so...

```
long g(int n){return n<2?n<1?1:0:34*g(n-1)-g(n-2)+2;}

```

Now, for something *non*-recursive, it gets quite a bit longer. This one is both longer (112-4=108) -and- slower, so I'm not sure why I'm posting it except to have something iterative:

```
long f(int n){long a=0,b,c,d=0;for(;a<1l<<32&n>0;)if((c=(int)Math.sqrt(b=(a*a+a++)/2))*c==b){d=b;n--;}return d;}

```

# Answer
> 2 votes
# Julia, 51 bytes - 4 - 4 = 43

```
f(n)=(a=b=big(1);b-=1;for i=1:n a,b=b,34b-a+2end;a)

```

This uses the first recurrence relation listed on the Wikipedia page for square triangular numbers. It computes *n* = 1000 in 0.006 seconds, and *n* = 100000 in 6.93 seconds. It's a few bytes longer than a recursive solution but it's *way* faster.

Ungolfed + explanation:

```
function f(n)
    # Set a and b to be big integers
    a = big(1)
    b = big(0)

    # Iterate n times
    for i = 1:n
        # Use the recurrence relation, Luke
        a, b = b, 34*b - a + 2
    end

    # Return a
    a
end

```

Examples:

```
julia> for i = 1:4 println(f(i)) end
0
1
36
1225

julia> @time for i = 1:1000 println(f(i)) end
0
... (further printing omitted here)
elapsed time: 1.137734341 seconds (403573226 bytes allocated, 38.75% gc time)

```

# Answer
> 2 votes
## PHP, ~~65~~ ~~59~~ 56-4=52 bytes

```
while($argv[1]--)while((0|$r=sqrt($s+=$f++))-$r);echo$s;

```

repeat until square root of `$s` is ∈ℤ: add `$f` to sum `$s`, increment `$f`;
repeat `$argv[1]` times.
output sum.

# Answer
> 2 votes
# Jelly, 13 - 8 = 5 bytes

This qualifies for both bonuses.

```
×8‘,µÆ²Ạ
0Ç#Ṫ

```

Try it online!

Done alongside caird coinheringaahing in chat.

# Explanation

```
×8‘,µÆ²Ạ  ~ Helper link.

×8        ~ 8 times the number.
  ‘       ~ Increment.
   ,      ~ Paired with the current number.
    µ     ~ Starts a new monadic (1-arg) link.
     Æ²   ~ Vectorized "Is Square?".
       Ạ  ~ All. Return 1 only if both are truthy.

0Ç#Ṫ  ~ Main link.

0 #   ~ Starting from 0, collect the first N integers with truthy results, when applied:
 Ç    ~ The last link as a monad.
   Ṫ  ~ Last element. Output implicitly.

```

# Answer
> 2 votes
# Perl 6, 25 - 8 = 17 bytes

```
{(0,1,2-*+34* *…*)[$_]}

```

Try it online!

# Answer
> 2 votes
# 05AB1E, 10 - 8 = 2 bytes

```
1ÎGDŠ34*Ìα

```

Try it online!

# Answer
> 2 votes
# APL (Dyalog Extended), 23-4-4 = 15 bytes

```
{⍵<2:⍵⋄2+-/34 1×∇¨⍵-⍳2}

```

Recursive dfn

`⍵<2:⍵` is ⍵ less than 2, if so return ⍵

otherwise

`∇¨⍵-⍳2` apply the function (∇) to the two previous values

`34 1×` multiply by the array 34 1

`-/` subtract

`2+` add 2

Try it online!

# Answer
> 1 votes
# Prolog, ~~70~~ 74 - 4 - 4 = 66

```
n(X,R):-n(X,0,1,R).
n(X,A,B,R):-X=0,R=A;Z is X-1,E is 34*B-A+2,n(Z,B,E,R).

```

Running `n(100,R)` outputs:

```
X = 40283218019606612026870715051828504163181534465162581625898684828251284020309760525686544840519804069618265491900426463694050293008018241080068813316496

```

Takes about 1 second to run `n(10000,X)` on my computer.

**Edit**: The 66 version is tail-recursive. The previous non-tail-recursive version is the following:

```
n(X,[Z|R]):-X>1,Y is X-1,n(Y,R),R=[A,B|_],Z is 34*A-B+2;X=1,Z=1,R=[0];Z=0.

```

They have the same length in bytes but the non-tail-recursive generates stack overflows past a certain point (on my computer, around 20500).

# Answer
> 1 votes
# Javascript ES6, ~~77~~ ~~75~~ 71 chars

```
// 71 chars
f=n=>{for(q=t=w=0;n;++q)for(s=q*q;t<=s;t+=++w)s==t&&--n&console.log(s)}

// No multiplication, 75 chars
f=n=>{for(s=t=w=0,q=-1;n;s+=q+=2)for(;t<=s;t+=++w)s==t&&--n&console.log(s)}

// Old, 77 chars
f=n=>{for(s=t=w=0,q=-1;n;s+=q+=2){for(;t<s;t+=++w);s==t&&--n&console.log(s)}}

```
* The solution is linear.
* The solution can output all numbers less then 2^53 because of numbers type.
* The algorithm itself can be used for unlimited numbers.

Test:

```
f(11)

0
1
36
1225
41616
1413721
48024900
1631432881
55420693056
1882672131025
63955431761796

```

# Answer
> 1 votes
# C, 68 bytes

This was a fun challenge with C

`main(o,k){o==1?k=0:0;k<9e9&&k>=0&&main(34*o-k+2,o,printf("%d,",k));}`

Watch it run here: https://ideone.com/0ulGmM

# Answer
> 0 votes
# APL(NARS), 67 chars, 134 bytes

```
r←f w;c;i;m
c←0⋄i←¯1⋄r←⍬
→2×⍳0≠1∣√1+8×m←i×i+←1⋄r←r,m⋄→2×⍳w>c+←1

```

test:

```
  f 10
0 1 36 1225 41616 1413721 48024900 1631432881 55420693056 1882672131025

```

f would search in quadratic sequence the elements that are triangulars number too, so they have to follow the triangular check formula in APLs: 0=1∣√1+8×m with number m to check.

# Answer
> 0 votes
### **x86\_64 machine code - 46 bytes**

Borrowed code from Albert Renshaw C answer.

47 bytes using **`ret`** instruction.

```
0000000000400080 <triangular_square>:
  400080:   48 31 d2                xor    rdx,rdx      # rdx = 0
  400083:   6a 00                   push   0x0
  400085:   41 58                   pop    r8           # r8 = 0
  400087:   48 ff c3                inc    rbx          # rbx = 1
  40008a:   49 89 d8                mov    r8,rbx       # copy rbx value to r8

000000000040008d <triangular_square.loop>:
  40008d:   e3 1f                   jrcxz  4000ae <triangular_square.done>  # if rcx is zero go to .done
  40008f:   4d 6b c0 22             imul   r8,r8,0x22   # r8 * 0x22 (34)
  400093:   49 29 d0                sub    r8,rdx       # r8 - rdx
  400096:   49 83 c0 02             add    r8,0x2       # r8 + 2
  40009a:   4d 89 c1                mov    r9,r8        # copy r8 value to r9
  40009d:   48 ff c2                inc    rdx          # rdx + 1
  4000a0:   48 ff ca                dec    rdx          # rdx - 1
  4000a3:   48 87 da                xchg   rdx,rbx      # swap rbx value with rdx value
  4000a6:   4c 89 cb                mov    rbx,r9       # copy r9 value to rbx
  4000a9:   4c 89 c0                mov    rax,r8       # copy r8 value to rax (output)
  4000ac:   e2 df                   loop   40008d <triangular_square.loop>  # keep looping until rcx is zero

00000000004000ae <triangular_square.done>:

```

Input in `rcx` output in `rax`. You can use debugger to test it.

TODO: Make a tester program on TIO.

# Answer
> 0 votes
# Husk, ~~14~~ 20 - 8 = 12 bytes

```
→!¡otS:o+2§-←o*34→ḋ2

```

Try it online!

Uses the same recurrence relation as the CJam answer. There's probably a better way to do this.

# Husk, 8 - 4 = 4 bytes

```
!Θf£∫Nİ□

```

Try it online!

it can theoretically output square triangular numbers of any size, ~~but list intersection causes a stack overflow for anything above 3.~~

Instead of `n` uses , which is optimized for infinite lists.

Getting numbers takes a long, long, long time after 4.

---
Tags: code-golf, number
---


title: Integer Percentify

text:
# Question
Title: Integer Percentify
Write a function which takes in a list of positive integers and returns a list of integers approximating the percent of total for the corresponding integer in the same position.

All integers in the return list must exactly add up to 100. You can assume the sum of integers passed in is greater than 0. How you want to round or truncate decimals is up to you as long as any single resulting integer returned as a percentage is off by no more than 1 in either direction.

```
p([1,0,2])      ->  [33,0,67] or [34,0,66]
p([1000,1000])  ->  [50,50] or [49,51] or [51,49]
p([1,1,2,4])    ->  [12,12,25,51] or [13,12,25,50] or [12,13,25,50] or [13,13,25,49] or [13,12,26,49] or [12,13,26,49] or [12,12,26,50]
p([0,0,0,5,0])  ->  [0,0,0,100,0]

```

This is , so shortest code in bytes wins!

# Answer
# Dyalog APL, ~~21~~ ~~19~~ 16 bytes

```
+\⍣¯1∘⌊100×+\÷+/

```

The above is a train equivalent of

```
{+\⍣¯1⌊100×+\⍵÷+/⍵}

```

Try it online.

### How it works

```
                 ⍝ Sample input: 1 1 2 4
           +\    ⍝ Cumulative sum of input. (1 2 4 8)
              +/ ⍝ Sum of input. (8)
             ÷   ⍝ Divide the first result by the second. (0.125 0.25 0.5 1)
       100×      ⍝ Multiply each quotient by 100. (12.5 25 50 100)
      ⌊          ⍝ Round the products down to the nearest integer... (12 25 50 100)
     ∘           ⍝ and ...
  ⍣¯1            ⍝ apply the inverse of...
+\               ⍝ the cumulative sum. (12 13 25 50)

```
> 21 votes

# Answer
# TI-BASIC, ~~26~~ ~~23~~ 16 bytes

For TI-83+/84+ series calculators.

```
ΔList(augment({0},int(cumSum(ᴇ2Ans/sum(Ans

```

Thanks to @Dennis for a beautiful algorithm! We take the cumulative sum of the list after converting to percents, then floor, tack a 0 onto the front, and take differences. `ᴇ2` is one byte shorter than `100`.

At the same byte count is:

```
ΔList(augment({0},int(cumSum(Ans/sum(Ans%

```

Fun fact: `%` is a two-byte token that multiplies a number by .01—but there's no way to type it into the calculator! You need to either edit the source outside or use an assembly program.

Old code:

```
int(ᴇ2Ans/sum(Ans
Ans+(ᴇ2-sum(Ans)≥cumSum(1 or Ans

```

The first line calculates all floored percents, then the second line adds 1 to the first `N` elements, where `N` is the percentage left over. `cumSum(` stands for "cumulative sum".

Example with `{1,1,2,4}`:

```
          sum(Ans                  ; 8
int(ᴇ2Ans/                         ; {12,12,25,50}

                        1 or Ans   ; {1,1,1,1}
                 cumSum(           ; {1,2,3,4}
     ᴇ2-sum(Ans)                   ; 1
                ≥                  ; {1,0,0,0}
Ans+                               ; {13,12,25,50}

```

We won't have `N>dim([list]`, because no percentage is decreased by more than 1 in flooring.
> 14 votes

# Answer
# CJam, ~~25~~ ~~23~~ 22 bytes

```
{_:e2\:+f/_:+100-Xb.+}

```

*Thanks to @Sp3000 for 25 → 24.*

Try it online.

### How it works

```
_                   e# Push a copy of the input.
 :e2                e# Apply e2 to each integer, i.e., multiply by 100.
    \               e# Swap the result with the original.
     :+             e# Add all integers from input.
       f/           e# Divide the product by the sum. (integer division)
        _:+         e# Push the sum of copy.
           100-     e# Subtract 100. Let's call the result d.
               Xb   e# Convert to base 1, i.e., push an array of |d| 1's.
                 .+ e# Vectorized sum; increment the first |d| integers.

```
> 7 votes

# Answer
### J (8.04 beta), 59 bytes (30 stolen bytes)

30 byte literal J-port of Dennis's APL answer:

```
    f=.3 :'+/\^:_1<.100*(+/\%+/)y'

    f 1 1 2 4
12 13 25 50

```

59 bytes answer, best I could do myself:

```
f=.3 :0
p=.<.100*y%+/y
r=.100-+/p
p+((r$1),(#p-r)$0)/:\:p
)

```

(Based on the remainder having to go to the highest values, no more than +1 each, split over multiple values in the case of a remainder \> 1 or a tie for highest value).

e.g.

```
   f 1 0 2
33 0 67

   f 1000 1000
50 50

   f 1 1 2 4
12 12 25 51

   f 0 0 0 5 0
0 0 0 100 0

   f 16 16 16 16 16 16
17 17 17 17 16 16

   f 0 100 5 0 7 1
0 89 4 0 7 0

```

Explanation

* `f=.3 : 0` \- 'f' is a variable, which is a verb type (3), defined below (:0):
* `p=.` variable 'p', built from:
    + `y` is a list of numbers `1 0 2`
    + `+/y` is '+' put between each value '/', the sum of the list `3`
    + `y % (+/y)` is original y values divided by the sum: `0.333333 0 0.666667`
    + `100 * (y%+/y)` is 100x those values: `33.33.. 0 0.66...` to get the percentages.
    + `<. (100*y%+/y)` is the floor operator applied to the percentages: `33 0 66`
* `r=.` variable 'r', built from:
    + `+/p` is the sum of the floored percentages: `99`
    + `100 - (+/p)` is 100 - the sum, or the remaining percentage points needed to make the percentages sum to 100.
* result, not stored:
    + `r $ 1` is a list of 1s, as long as the number of items we need to increment: `1 [1 1 ..]`
    + `#p` is the length of the percentage list
    + `(#p - r)` is the count of items that won't be incremented
    + `(#p-r) $ 0` is a list of 0s as long as that count: `0 0 [0 ..]`
    + `((r$1) , (#p-r)$0)` is the 1s list followed by the 0s list: `1 0 0`
    + `\: p` is a list of indexes to take from `p` to put it in descending order.
    + `/: (\:p)` is a list of indexes to take from `\:p` to put that in ascending order
    + `((r$1),(#p-r)$0)/:\:p` is taking the elements from the 1 1 .. 0 0 .. mask list and sorting so there are 1s in the positions of the biggest percentages, one for each number we need to increment, and 0s for other numbers: `0 0 1`.
    + `p + ((r$1),(#p-r)$0)/:\:p` is the percentages + the mask, to make the result list which sums to 100%, which is the function return value.

e.g.

```
33 0 66 sums to 99
100 - 99 = 1
1x1 , (3-1)x0 = 1, 0 0
sorted mask   = 0 0 1

33 0 66
 0 0  1
-------
33 0 67

```

and

* `)` end of definition.

I'm not very experienced with J; I wouldn't be too surprised if there's a "turn list into percentages of the total" operation built in, and a cleaner way to "increment *n* biggest values" too. (This is 11 bytes less than my first attempt).
> 6 votes

# Answer
# Mathematica, 41 bytes

```
(s=Floor[100#/Tr@#];s[[;;100-Tr@s]]++;s)&

```
> 5 votes

# Answer
# Jelly, 7 bytes

-2 thanks to Dennis, reminding me to use another new feature (`Ä`) and using `:` instead of what I initially had.

```
ŻÄ×³:SI

```

Try it online!

# Jelly, 11 bytes

```
0;+\÷S×ȷ2ḞI

```

Try it online!

Done alongside caird coinheringaahing and user202729 in chat.

## How it works

```
0;+\÷S×ȷ2ḞI - Full program.

0;          - Prepend a 0.
  +\        - Cumulative sum.
    ÷S      - Divided by the sum of the input.
      ×ȷ2   - Times 100. Replaced by ×³ in the monadic link version.
         ḞI - Floor each, compute the increments (deltas, differences).

```
> 5 votes

# Answer
# JavaScript (ES6), 81 bytes

```
a=>(e=0,a.map(c=>((e+=(f=c/a.reduce((c,d)=>c+d)*100)%1),f+(e>.999?(e--,1):0)|0)))

```

That "must equal 100" condition (rather than rounding and adding up) nearly doubled my code (from 44 to 81). The trick was to add an pot for decimal values that, once it reaches 1, takes 1 from itself and adds it to the current number. Problem then was floating points, which means something like \[1,1,1\] leaves a remainder of .9999999999999858. So I changed the check to be greater than .999, and decided to call that precise enough.
> 4 votes

# Answer
# Haskell, ~~42~~ 27 bytes

```
p a=[div(100*x)$sum a|x<-a]

```

Pretty much the trivial method in Haskell, with a few spaces removed for golfing.

Console (brackets included to be consistent with example):

```
*Main> p([1,0,2])
[33,0,66]
*Main> p([1000,1000])
[50,50]
*Main> p([1,1,2,4])
[12,12,25,50]
*Main> p([0,0,0,5,0])
[0,0,0,100,0]

```

Edit: practised my putting, made some obvious replacements.

Original:

```
p xs=[div(x*100)tot|x<-xs]where tot=sum xs

```
> 4 votes

# Answer
### Haskell, ~~63~~ ~~56~~ 55 bytes

```
p l=tail>>=zipWith(-)$[100*x`div`sum l|x<-0:scanl1(+)l]

```
> 3 votes

# Answer
# JavaScript (ES6) 60 ~~63 95~~

Adapted and simplified from my (wrong) answer to another challenge
Thk to @l4m2 for discovering that this was wrong too

Fixed saving 1 byte (and 2 byte less, not counting the name `F=`)

```
v=>v.map(x=>(x=r+x*100,r=x%f,x/f|0),f=eval(v.join`+`),r=f/2)

```

Test running the snippet below in any EcmaScript 6 compliant browser

```
F=
v=>v.map(x=>(x=r+x*100,r=x%f,x/f|0),f=eval(v.join`+`),r=f/2)

console.log('[1,0,2] (exp [33,0,67] [34,0,66])-> '+F([1,0,2]))
console.log('[1000,1000] (exp [50,50])-> '+F([1000,1000]))
console.log('[1,1,2,4] (exp[12,12,25,51] [13,12,25,50] [12,13,25,50] [12,12,26,50])-> '+F([1,1,2,4]))
console.log('[0,0,0,5,0] (exp [0,0,0,100,0])-> '+F([0,0,0,5,0]))
console.log('[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,980] -> '+F([1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,980]))
console.log('[2,2,2,2,2,3] -> ' + F([2,2,2,2,2,3]))
```

```
<pre id=O></pre>
```
> 3 votes

# Answer
# Perl, 42 bytes

Based on Dennis's algorithm

Includes +1 for `-p`

Run with the list of numbers on STDIN, e.g.

```
perl -p percent.pl <<< "1 0 2"

```

`percent.pl`:

```
s%\d+%-$-+($-=$a+=$&*100/eval y/ /+/r)%eg

```
> 3 votes

# Answer
# Brain-Flak, 150 bytes

```
((([]){[{}]({}<>)<>([])}{})[()])<>([]){{}<>([{}()]({}<([()])>)<>(((((({})({})({})){}){}){}{}){}){}(<()>))<>{(({}<({}())>)){({}[()])<>}{}}{}([])}<>{}{}

```

Try it online!

Starting from the end and working backward, this code ensures at each step that the sum of the output numbers so far is equal to the total percentage encountered, rounded down.

```
(

  # Compute and push sum of numbers
  (([]){[{}]({}<>)<>([])}{})

# And push sum-1 above it (simulating a zero result from the mod function)
[()])

<>

# While elements remain
([]){{}

  # Finish computation of modulo from previous step
  <>([{}()]({}

    # Push -1 below sum (initial value of quotient in divmod)
    <([()])>

  # Add to 100*current number, and push zero below it
  )<>(((((({})({})({})){}){}){}{}){}){}(<()>))

  # Compute divmod
  <>{(({}<({}())>)){({}[()])<>}{}}{}

([])}

# Move to result stack and remove values left over from mod
<>{}{}

```
> 3 votes

# Answer
# Husk, 14 bytes

```
Ẋ-Θmȯ⌊*100/Σ¹∫

```

Try it online! or Verify all test cases

Algorithm from Dennis' answer.

## Explanation

```
Ẋ-Θmȯ⌊*100/Σ¹∫
             ∫ cumulative sums
   mȯ          map to the follwing 4 functions
          /Σ¹  divide by sum of input
      *100     times 100
     ⌊         floored
  Θ            prepend a zero
Ẋ-             fold consecutive pairs with subtraction

```
> 3 votes

# Answer
# Octave, 40 bytes

```
@(x)diff(ceil([0,cumsum(100*x/sum(x))]))

```
> 2 votes

# Answer
### Python 2, 89 bytes

```
def f(L):
 p=[int(x/0.01/sum(L))for x in L]
 for i in range(100-sum(p)):p[i]+=1
 return p

print f([16,16,16,16,16,16])
print f([1,0,2])

->

[17, 17, 17, 17, 16, 16]
[34, 0, 66]

```
> 2 votes

# Answer
# JavaScript, 48 bytes

```
F=

x=>x.map(t=>s+=t,y=s=0).map(t=>-y+(y=100*t/s|0))

// Test
console.log=x=>O.innerHTML+=x+'\n';

console.log('[1,0,2] (exp [33,0,67] [34,0,66])-> '+F([1,0,2]))
console.log('[1000,1000] (exp [50,50])-> '+F([1000,1000]))
console.log('[1,1,2,4] (exp[12,12,25,51] [13,12,25,50] [12,13,25,50] [12,12,26,50])-> '+F([1,1,2,4]))
console.log('[0,0,0,5,0] (exp [0,0,0,100,0])-> '+F([0,0,0,5,0]))
```

```
<pre id=O></pre>
```
> 2 votes

# Answer
# 05AB1E, 9 bytes

```
.¥IO/т*ï¥

```

Try it online!

*+3 for a bugfix*
> 2 votes

# Answer
# Vyxal, 12 bytes

```
∑/₁*ṙ:∑₁$-Þ…

```

Try it Online!

## Explained

```
∑/₁*ṙ:∑₁$-Þ…
∑             # sum(input)
 /            # input ÷ ↑         # get the weight of each number
  ₁*          # ↑ * 100           # and make it a percentage
    ṙ         # map(round, ↑)     # rounding each number
     :∑       # ↑, sum(↑)         # now sum the above
       ₁$-    # 100 - ↑           # and subtract from 100. The result represents any potential round errors that need correction
          Þ…  # distribute(↑, ↑↑) # spread ↑ over the rounded list evenly

```
> 2 votes

# Answer
# Rust, 85 bytes

This uses vectors instead of arrays because as far as I am aware there is no way to accept arrays of multiple different lengths.

```
let a=|c:Vec<_>|c.iter().map(|m|m*100/c.iter().fold(0,|a,x|a+x)).collect::<Vec<_>>();

```
> 1 votes

# Answer
# Japt v2.0a0, 13 bytes

```
å+ mzUx÷L)änT

```

Try it
> 1 votes

# Answer
# Jq 1.5, 46 bytes

```
add as$s|.[1:]|map(100*./$s|floor)|[100-add]+.

```

Expanded

```
  add as $s               # compute sum of array elements
| .[1:]                   # \ compute percentage for all elements
| map(100*./$s|floor)     # / after the first element
| [100-add] + .           # compute first element as remaining percentage

```

Try it online!
> 0 votes

# Answer
# PHP, 82 bytes

```
for(;++$i<$argc-1;$s+=$x)echo$x=$argv[$i]/array_sum($argv)*100+.5|0,_;echo 100-$s;

```

takes input from command line arguments, prints percentages delimited by underscore.

Run with `-nr` or try it online.
> 0 votes

---
Tags: code-golf, array
---


title: Solve 4x4 Mastermind in exactly 5 steps

text:
# Question
Title: Solve 4x4 Mastermind in exactly 5 steps
## Background

**Mastermind** is a game of code-breaking for two players. One of the players is *codemaker* (Alice) and the other is *codebreaker* (Bob).

4x4 means that the player should guess the length-4 sequence made of four alphabets (say `RGBY`). The hidden sequence may have duplicate letters, so there are \\$4^4 = 256\\$ possibilities in total.

At the start of the game, Alice sets up a hidden code, which Bob should guess correctly within a set number of turns. At each turn, Bob presents a guess, and Alice tells Bob how many of the positions are correct, and how many of the letters are correct but at a wrong position. For example, if the hidden code is `RRYG` and Bob guessed `BRGY`:

```
          Code: R R Y G
         Guess: B R G Y
       Correct: R(2nd-2nd)
Wrong position: Y(3rd-4th), G(4th-3rd)

```

Then Alice tells Bob the two counts `1, 2`. (Note that the first `R` in the code does not contribute to the counts because the second `R` in the guess was already consumed as Correct.) Bob repeats the guess with different sequences, until the guess is identical to the code (getting `4, 0`) or he runs out of turns.

## Challenge

The Dream World mastermind solver features four specific guesses so that the unique answer can be derived from their outcomes in all cases. The guesses are as follows:

```
1. R G G R
2. B B R R
3. Y Y G R
4. G B B Y

```

Given the outcomes of the four combinations above (four pairs of integers), output the unique hidden code.

You can assume the input is valid and the answer exists. You can choose to output any four distinct values (numbers/characters) in place of `RGBY`.

Standard rules apply. The shortest code in bytes wins.

NB: Fetching the results from the linked website is a standard loophole, and therefore forbidden.

## Test cases

Each pair in the input represents `(correct, misplaced)`. Note that the answer can be one of the four predefined guesses (generating a `(4, 0)` in the input).

```
(2, 0), (2, 0), (1, 0), (0, 0) => R R R R
(2, 1), (1, 0), (1, 2), (1, 1) => G G Y R
(0, 2), (0, 2), (0, 3), (1, 2) => G R Y B
(2, 0), (0, 0), (2, 0), (0, 2) => Y G G G
(1, 1), (4, 0), (1, 0), (1, 1) => B B R R

```

# Answer
# 05AB1E, ~~38~~ ~~33~~ 32 bytes

-6 bytes thanks to Kevin Cruijssen!

For each possible output this generates the input and selects the matching one. Colors are encoded as `B=0, G=1, R=2, Y=3`.

```
3Ý4ãʒU•˜ÐÐÛ•4в4äεœεX-0¢}¬Dràα‚}Q

```

Try it online!

**Commented**:

```
3Ý4ã              # Generate all possible outputs
3Ý                # range [0 .. 3]
  4и              # to the 4th cartesian power

ʒU ... Q          # filter the possible outputs
                  #   where the following equals the input
                  #   and assign the current output to variable X

•˜ÐÐÛ•4в4ä        # encode the 4 guesses
•˜ÐÐÛ•            # compressed integer 2517300803
      4в          # convert to base 4:
                  #   [2,1,1,2,0,0,2,2,3,3,1,2,1,0,0,3]
        4ä        # split into 4 groups:
                  #   [2,1,1,2],[0,0,2,2],[3,3,1,2],[1,0,0,3]

εœεX-0¢}¬Dràα‚}   # compute the score for each guess
ε             }   # map over the guesses ...
 œ                #   take all permutations
                  #     the first will be the original guess
  ε    }          #   map over the permuations ...
   X-             #     subtract the current output
     0¢           #     count the 0's
        ¬         #   get the head without popping
                  #     this is number of correct positions (c)
         D        #   duplicate it       => c, c, [...]
          r       #   reverse the stack  => [...], c, c
           à      #   take the maximum
                  #     this is number of correct colors,
                  #     correct and misplaced (c+m)
                  #                      => c+m, c, c
            α     #   absolut difference => |c-(c+m)|, c = m, c
             ‚    #   pair up     => [c, m]

```
> 4 votes

# Answer
# Jelly,  ~~29~~  28 bytes

```
4ṗ`ð“ßƙṫl‘ị⁸Œ!=§Ḣ,Ṁạ\ƲʋþZiị⁸

```

A monadic Link accepting a list of four lists of two integers (the `[correct, misplaced]` pairs in order) which yields a list of four integers (where `1,2,3,4` map to `R,G,B,Y` respectively).

**Try it online!** (footer remaps back to the letters representing the colours.)

### How?

```
4ṗ`ð“ßƙṫl‘ị⁸Œ!=§Ḣ,Ṁạ\ƲʋþZiị⁸ - Link: scores
4ṗ`                          - 4 Cartesian power 4 -> all boards
   ð                         - start a new dyadic chain f(boards, scores)
    “ßƙṫl‘                   - code-page indices = [21, 161, 245, 108]
           ⁸                 - chain's left argument, boards
          ị                  - index into -> the four test-boards
                       þ     - make a table of:
                      ʋ      -   last four links as a dyad:
            Œ!               -     all permutations (of the board in question)
              =              -     equals? (vectorises across the boards & test-board)
               §             -     sums
                     Ʋ       -     last four links as a monad:
                Ḣ            -       head -> total correctly placed
                  Ṁ          -       maximum -> total that could be correct by permuting
                 ,           -       pair
                    \        -       cumulative reduce by:
                   ạ         -         absolute difference -> [correct, misplaced]
                        Z    - transpose
                         i   - first index of (scores) in (that)
                           ⁸ - chain's left argument, boards
                          ị  - index into

```
> 2 votes

# Answer
# Python 3, 171 bytes

```
def f(s,a=0):b='%04i'%a;return([(w,sum(min(b.count(x),t.count(x))for x in{*t})-w)for t in('0110','2200','3310','1223')for w in[sum(map(str.__eq__,b,t))]]==s)*b or f(s,a+1)

```

Try it online!

-22 bytes thanks to ovs

Recursive function to test all possible combinations and find the matching input.

`sum(map(str.__eq__,b,t))` finds the number of correct positions for each combination.

`sum(min(b.count(x),t.count(x))for x in{*t})` finds the sum of the correct and misplaced positions. The number of misplaced positions is found by subtracting the number of correct positions.

Uses `0, 1, 2, 3` for `R, G, B, Y`, respectively.
> 1 votes

# Answer
# JavaScript (ES6),  ~~169 ... 160~~  153 bytes

Expects an array of 2-character strings `"CM"` with `C` = correct, `M` = misplaced. Returns an array of integers, with `0123` = `RGBY`.

```
f=(a,n)=>a.some((c,i)=>(g=n=>A=a.map(_=>4*(n/=4)&3))(n,b=g(3911125524>>>i*8)).map((v,k)=>c-=v^b[k]?b.some((w,j)=>v-w|v==A[j]?0:b[j]|=4):10)|c)?f(a,-~n):A

```

Try it online!

### How?

We generate all possible boards `A[]` and test them against the guesses `b[]` which are extracted from the 32-bit integer `3911125524` as follows:

```
3911125524 = 0xE91F0A14

0x14 = 00 01 01 00 -> R G G R
0x0A = 00 00 10 10 -> R R B B
0x1F = 00 01 11 11 -> R G Y Y
0xE9 = 11 10 10 01 -> Y B B G

```

We decrement the expected outcome `c` when a 'misplaced' digit is found and subtract 10 from `c` when a 'correct' digit is found. We stop when we have `c = 0` for all guesses.

### Commented

```
f = (a, n) =>                // a[] = input array, n = counter
  a.some((c, i) =>           // for each entry c at position i in a[]:
    ( g = n =>               //   g is a helper function turning a byte n
      A = a.map(_ =>         //   into an array of 4 2-bit values
        4 * (n /= 4) & 3     //   by isolating the 2 least significant bits
      )                      //   and dividing by 4 between each iteration
    )(                       //
      n,                     //   invoke g with n to create the board A[]
      b = g(                 //   invoke g with a byte extracted from ...
        3911125524 >>> i * 8 //   ... this 32-bit integer ...
      )                      //   ... to create the i-th guess b[]
    )                        //
    .map((v, k) =>           //   for each value v at position k in A[]:
      c -=                   //     update c:
        v ^ b[k] ?           //       if v is not equal to b[k]:
          b.some((w, j) =>   //         decrement c if there's some w at position j
            v - w |          //         in b[] such that v = w and v is not equal
            v == A[j] ?      //         to A[j] (i.e. A[j] is not 'correct'),
              0              //         in which case ...
            :                //
              b[j] |= 4      //         ... we invalidate b[j] by OR'ing it with 4
          )                  //
        :                    //       else:
          10                 //         subtract 10 from c
    )                        //   end of map()
    | c                      //   yield a truthy value if c is ≠ 0
  ) ?                        // end of some(); if truthy:
    f(a, -~n)                //   failure: do a recursive call with n + 1
  :                          // else:
    A                        //   success: return A[]

```
> 1 votes

# Answer
# Charcoal, 53 bytes

```
ΦＥ²⁵⁶⭆⁴﹪÷ιＸ⁴λ⁴⁼ＩθＥ⪪”)“∧.r⁹1”⁴⁺×⁹ΣＥι⁼§λξνΣＥ⁴⌊⟦№ιＩν№λＩν

```

Try it online! Link is to verbose version of code. Takes input as four strings containing pairs of digits in match mismatch order. Output uses digits `0-3` for the colours `RYGB`. Uses brute force. Explanation:

```
ΦＥ²⁵⁶⭆⁴﹪÷ιＸ⁴λ⁴

```

Filter through all possible 4-digit codes.

```
⁼Ｉθ

```

Convert the input pairs of digits to integers and compare with the result of...

```
Ｅ⪪”)“∧.r⁹1”⁴⁺

```

... checking the score of each of the patterns in the compressed string `0220330011202331` by taking the sum of...

```
×⁹ΣＥι⁼§λξν

```

... nine times the number of matching digits and...

```
ΣＥ⁴⌊⟦№ιＩν№λＩν

```

... the sum of matching and mismatching digits.

58 bytes to output using `RYGB`:

```
ΦＥ²⁵⁶⭆⁴§RYGB÷ιＸ⁴λ⁼ＩθＥ⪪”{⊞‴⊗⁵÷∧p<8'”⁴⁺×⁹ΣＥι⁼§λξνΣＥα⌊⟦№ιν№λν

```

Try it online! Link is to verbose version of code.
> 1 votes

# Answer
# , 194 bytes

```
function(r,a=apply,`~`=table,g=matrix(762201603%/%4^(15:0)%%4,4))(p=expand.grid(rep(list(t<-0:3),4)))[a(p,1,function(y)all(a(g,1,function(h)c(z<-sum(y==h),sum(pmin(~c(t,y),~c(t,h))-1)-z))==r)),]

```

Try it online!

Uses the integers 0,1,2,3 to indicate R,G,B,Y.

**How?** (commented and de-golfed gode)

```
solve_mastermind=
function(r,                             # get responses r as 8-element vector
  a=apply,                              # a = alias to apply() function (not used in de-golfed code here)
  `~`=table,                            # ~ = alias to table() function (not used in de-golfed code here)
  g=matrix(762201603%/%4^(15:0)%%4,4))  # g = matrix of guesses, compressed as a base-4 integer,
                                        #     and decompressed here using DIV powers-of-4 MOD 4
(p=expand.grid(rep(list(0:3),4)))       # p = all possible permutations of codes (a 256 x 4 matrix)
[                                       # Select & return the correct row from p:
 apply(p,1,function(y)                  # apply this function to all rows of p:
  all( ... )==r                         # return true if all these values are equal to the elements of r:
    apply(g,1,function(h)               # apply this function to all rows of g (that is, each of the 4 guesses):
    c(                                  # return a 2-element vector, consisting of:
      z<-sum(y==h),                     # 1. z = sum of elements of this code (y) that are equal to elements of this guess (h)
                                        #     so: correct position + correct colour
      sum(                              # 2. the sum of ...
        pmin(                           #     the minima of ...
          table(c(0:3,y)),              #      the count of the digits 0..3 in this code (y), +1
                                        #       (the table() function counts the number of each type of instance.
                                        #       However, we aren't sure that all of the digits will be present, and
                                        #       absent digits would normally be uncounted (instead of counted as zero).
                                        #       So we join the series 0..3 to y before counting the digits.
          table(c(0:3,h)))              #      and the count of the digits 0..3 in this guess (h), +1
                          -1)           #     minus one (to account for the digits that we added)
      -z)                               #    minus the number of correct position + correct colour
    )==r)),                             # (see above)
]

```
> 1 votes

---
Tags: code-golf, puzzle-solver
---


title: Generate Skolem sequences

text:
# Question
Title: Generate Skolem sequences
## Skolem sequences

A *Skolem sequence* is a sequence of `2n` numbers where every number `i` between `1` and `n` occurs exactly twice, and the distance between the two occurrences of `i` is exactly `i` steps. Here are some examples of Skolem sequences:

```
1 1
1 1 4 2 3 2 4 3
16 13 15 12 14 4 7 3 11 4 3 9 10 7 13 12 16 15 14 11 9 8 10 2 6 2 5 1 1 8 6 5

```

The following sequences are *not* Skolem sequences:

```
1 2 1 2      (The distance between the 1's is 2, not 1)
3 1 1 3      (The number 2 is missing)
1 1 2 1 1 2  (There are four 1's)

```

## Objective

Write a program, function, or expression to count the number of all Skolem sequences of a given length. More explicitly, your input is an integer `n`, and your output is the number of Skolem sequences of length `2n`. This sequence has an OEIS entry. For `n = 0`, you may return either `0` or `1`. The first few values, starting from `0`, are

```
0, 1, 0, 0, 6, 10, 0, 0, 504, 2656, 0, 0, 455936, 3040560, 0, 0, 1400156768

```

## Rules and scoring

This is code golf. Output format is lax within reason.

# Answer
### GolfScript, 48 46 characters

```
:b,1,{)2\?){{.2$&!{.2$|@@}*.+.4b?<}do;;}+%}@/,

```

The faster version (try online) - runs reasonable fast, e.g. `n=8` takes about two seconds. And the chosen approach takes really few characters.

This version also works with bitmasks. It builts the possible result array from 1 upwards, i.e. for `n=3`:

```
1: 000011        000110 001100 011000 110000
2: 010111 101011 101110        011101 110101 111010

```

While some results (like 000011) have two possible continuations, others (i.e. 001100) have none and are removed from the result array.

Explanation of the code:

```
:b           # save the input into variable b for later use
,            # make the list 0..b-1 (the outer loop)
1,           # puts the list [0] on top of the stack - initially the only possible
             # combination
{)           # {...}@/ does the outer loop counting from i=1 to b
  2\?)       # computes the smalles possible bit mask m=2^i+1 with two bits set
             # and distance of those equal to i (i.e. i=1: 11, i=2: 101, ...)
  {          # the next loop starts with this bitmask (prepended to code via
             # concatination {...}+
             # the loop itself iterates the top of the stack, i.e. at this point
             # the result array
             # stack here contains item of result array (e.g. 00000011)
             # and bitmask (e.g. 00000101)
    {        # the inner-most loop tries all masks with the current item in the result set
      .2$&!  # do item and result set share not single bit? then - {...}*
      {
        .2$| # then generate the new entry by or-ing those two
        @@   # push it down on the stack (i.e. put working items to top)
      }*
      .+     # shift the bit mask left by one
      .4b?<  # if still in the range loop further
    }do;;    # removes the remainders of the loop (i.e. item processed and mask)
  }+%        # stack now contains the new result array
}@/
,            # length of result array, i.e. the number of Skolem sequences

```
> 8 votes

# Answer
## GolfScript (46 chars)

```
:&1,\,{0,2@)?)2&*{2${1$^}%@+\2*}*;+}/{4&?(=},,

```

This is an expression which takes input on the stack. To turn it into a full program which takes input on stdin, prepend `~`

It is fairly inefficient - most of the savings I made in golfing it down from 56 chars ungolfed were by expanding the range of loops in ways which don't introduce incorrect results but do waste calculation.

The approach is bitwise masking of Cartesian products. E.g. (using binary for the masks) for `n=4` the ungolfed code would compute the xor of each element in the Cartesian product `[00000011 00000110 ... 11000000] x [00000101 00001010 ... 10100000] x ... x [00010001 ... 10001000]`. Any result with 8 bits could only be achieved by non-overlapping masks.

In order to optimise for size rather than speed, the code accumulates partial products (`S1 u S1xS2 u S1xS2xS3 ...`) and makes each product be of `2n` elements rather than just the `2n-1-i` which can actually contribute to a valid sequence.

### Speed

The golfed version runs for `n=5` in 10 seconds on my computer, and more than 5 minutes for `n=6`. The original ungolfed version computes `n=5` in less than a second, and `n=6` in about 1 minute. With a simple filter on intermediate results, it can compute `n=8` in 30 seconds. I've golfed it to 66 chars (as a program - 65 chars as an expression) while keeping the loops as restricted as possible and filtering intermediate collisions:

```
~:&1,\,{0,\).2\?)2&*@-{.{[\].~^.@~+<{;}*}+3$%@+\2*}*;\;}/{4&?(=},,

```
> 6 votes

# Answer
### J expression, 47 characters

```
 +/*/"1((=&{:+.2-#@])#;.2)\"1~.(i.!+:y)A.,~>:i.y

```

Example:

```
    y=:5
    +/*/"1((=&{:+.2-#@])#;.2)\"1~.(i.!+:y)A.,~>:i.y
10

```

Takes about 30 seconds for `y=:5` on my machine.

the algorithm is as slow as can be:

* `~.(i.!+:y)A.,~>:i.y` generates every permutation of `1 2 .. y 1 2 .. y` and removes duplicate entries
* `((=&{:+.2-#@])#;.2)\"1` computes:
    + `(...)\"1` for every prefix of every row:
        - `#;.2` counts the the elements before each occurence of the last element
        - `#@]` counts the number of counts (i.e. the number of occurences of the last element)
        - `=&{:` determines the "equality" "of" "last element"s of the count list and of the original list.
        - `+.` is a logical OR. `=&{:+.2-#@]` reads "either the last elements \[of the count list and the original list\] are equal, or there is only one element \[in the count list\] rather than two".
* `*/"1` multiplies (logical AND) over the rows of the condition table, determining which permutations are Skolem sequences.
* `+/` sums the ones and zeroes together.
> 6 votes

# Answer
### GolfScript, 49 characters

```
~:/..+?:d(,{d+/base(;:w;/,{.w?)w>1$?=},,/=},,/1=+

```

Expects the number `n` on STDIN. This is code-golf - don't try the code with `n` greater than 5.
> 5 votes

# Answer
# Husk, <sup>~~20~~</sup> 19 bytes

```
₁ḣ
ṁo=¹⁰(moF-¥)uPṘ2

```

Try it online!

Can be shortened further.

returns 1 for 0.

-1 byte from Jo king.

## Explanation

```
ṁo=ḣ¹`(moF-¥)ḣ¹uPṘ2ḣ
                   ḣ range from 1..n
                 Ṙ2  replicate each element 2 times
               uP    unique permutations of the list
ṁo                   map each permutation to the following two functions
                     and sum the results
     `               flip: f x y = f y x
      (mo   )        map each number to the following:
      (    ¥)ḣ¹      index of each number in 1..n in the permutation
      (  F- )        folded by subtraction
  =ḣ¹                are the differences equal to 1..n?

```
> 3 votes

# Answer
## Sage, 70

This is a little shorter than my original.

```
sum(1for i in DLXCPP([(i-1,j,i+j)for i in[1..n]for j in[n..3*n-i-1]]))

```

How it works:

Given a 0/1 matrix, the **exact cover** problem for that matrix is to find a subset of the rows that sum (as integers) to the all-ones vector. For example,

```
11001
10100
01001
00011
00010

```

has a solution

```
10100
01001
00010

```

My favorite approach to problems is to cast them to an exact cover problem. Skolem sequences efficiently facilitate this. I make an exact cover problem where solutions are in bijection with Skolem sequences of length `2n`. For example, a row of the problem for `n=6` is

```
  a   |  b
001000|001001000000 # S[b] = S[b+a+1] = a

```

where a 1 in position `a < n` means that symbol `a` is used. The remaining positions correspond to actual locations in the sequence. An exact cover corresponds to each symbol being used exactly once, and each location being filled exactly once. By construction, any symbol `k` in a location is `k` spaces away from its partner.

In Sage, `DLXCPP` is a "dancing links" implementation -- it solves the exact cover problem in an exceptionally graceful manner. It's one of my favorite algorithms ever, and being right at the surface in Sage makes combinatorial enumeration a joy.
> 1 votes

# Answer
# 05AB1E, 22 bytes

```
Ý¦©€DœʒU®εXQ0Úg<}®Q}Ùg

```

Results in \\$0\\$ for \\$n=0\\$.

Try it online or verify the test cases in the range \\$\[0,4\]\\$. (Unfortunately times out for \\$n\geq5\\$.)

**Explanation:**

```
Ý                 # Push a list in the range [0, (implicit) input `n`]
 ¦                # Remove the leading 0
                  # (builtin `L` would become list [1,0] for n=0 unfortunately,
                  # resulting in an incorrect result of 3 at the end)
  ©               # Store this list in variable `®` (without popping)
   €D             # Duplicate each, resulting in a flattened list [1,1,2,2,3,3,...,n,n]
     œ            # Get all permutations of this list
      ʒ           # Filter it by:
       U          #  Pop and store the current permutation in variable `X`
        ®         #  Push the ranged list [1,n] from variable `®`
         ε        #  Map it to:
          X       #   Check for each value in list `X`
           Q      #   whether it's equal to the current map value
                  #   (1 if truthy; 0 if falsey)
            0Ú    #   Remove all leading and trailing 0s
              g   #   Pop and get the length of the list
               <  #   Decrease it by 1
         }®Q      #  After the map: check if it's equal to the [1,n] ranged list
      }Ù          # After the filter: uniquify the remaining permutations
        g         # And pop and push the length
                  # (after which this is output implicitly as result)

```
> 1 votes

---
Tags: code-golf, math, sequence
---