title: How much more reputation do I need?

text:
# Question
Title: How much more reputation do I need?
Programming Puzzles and Code Golf has graduated from beta. Soon we will get a custom site design, and with that the reputation boundaries for privileges will go up. A lot of users will lose privileges on the site. So your task is to write a program that tells us how much extra reputation we'll need to keep our privileges.

## Task

Your task is to write the shortest code to find the amount of extra reputation a user will need to keep their current privileges after the site design, given the number of reputation points.

## Input / Output

You can accept input and give output in any way you like, so long as it follows these rules:

**Input** \- An integer from 1 to 250000+ *inclusive*. Your program or function *should* be able to accept numbers bigger than this, but it *must* accept numbers in this range.

**Output** \- An integer representing the number of reputation points the user will need to get to keep their current privileges after the graduation.

No standard loopholes, please.

## Example algorithm

1. Set variable `i` to the input
2. Set variable `r` to variable `i`.
3. While `r` is not in list `beta`:
    1. Subtract `1` from `r`.
4. Set `n` to the position of `r` in `beta`.
5. Set `r` to item `n` of `graduated`.
6. Set variable `o` to the result of `r` `-` `i`.
7. If `o` `<` `0`:
    1. Set variable `o` to `0`.
8. Output variable `o`.

## Tables

### Table of privileges that will change

```
 | privilege name              | beta rep | graduation rep |
-+-----------------------------+----------+----------------+-
 | create tags                 |      150 |           1500 |
 | access review queues        |      350 |            500 |
 | cast close and reopen votes |      500 |           3000 |
 | established user            |      750 |           1000 |
 | edit questions and answers  |     1000 |           2000 |
 | create tag synonyms         |     1250 |           2500 |
 | approve tag wiki edits      |     1500 |           5000 |
 | access to moderator tools   |     2000 |          10000 |
 | protect questions           |     3500 |          15000 |
 | trusted user                |     4000 |          20000 |
 | access to site analytics    |     5000 |          25000 |
-+-----------------------------+----------+----------------+-
 | privilege name              | beta rep | graduation rep |

```

### Table of privileges that won't change

```
 | privilege name               | reputation |
-+------------------------------+------------+-
 | create posts                 |          1 |
 | participate in meta          |          1 |
 | create wiki posts            |         10 |
 | remove new user restrictions |         10 |
 | vote up                      |         15 |
 | flag posts                   |         15 |
 | talk in chat                 |         20 |
 | comment everywhere           |         50 |
 | set bounties                 |         75 |
 | create chatrooms             |        100 |
 | edit community wiki          |        100 |
 | vote down                    |        125 |
-+------------------------------+------------+-
 | privilege name               | reputation |

```

## Testcases

```
wizzwizz4                |   750 |  2250
cat                      |  2004 |  7996
Dennis ♦                 | 72950 |     0
Dr Green Eggs and Ham DJ |  4683 | 15317
New User                 |     1 |     0

```

Not all reputation counts are correct at time of writing
If you want your past or present reputation count here, just comment below and I'll maybe add it.

# Answer
> 4 votes
# Python, 101 bytes

```
lambda n:max(0,eval("+(n>=%d)*%d"*7%(5e3,5e3,4e3,5e3,35e2,5e3,2e3,5e3,15e2,2e3,5e2,15e2,150,15e2))-n)

```

# Answer
> 4 votes
# Jelly, ~~40~~ 37 bytes

```
19112203.3b11×ȷḞ>Ḥ¬×9999322D‘¤S×.ȷ_»0

```

Try it online! or verify all test cases.

### How it works

```
19112203.3b11×ȷḞ>Ḥ¬×9999322D‘¤S×.ȷ_»0  Main link. Argument: n

19112203.3b11                          Convert the float to base 11. Yields
                                       [10, 8, 7, 4, 3, 1, 0.30000000074505806].
             ×ȷ                        Multiply each by 1000.
               Ḟ                       Floor. Yields
                                       [10000, 8000, 7000, 4000, 3000, 1000, 300].
                 Ḥ                     Unhalve; yield 2n.
                >                      Compare each integer in the list with 2n.
                  ¬                    Negate the resulting Booleans.
                             ¤         Chain the three links to the left:
                    9999322D           Convert the integer to base 10.
                            ‘          Increment each digit. Yields
                                       [10, 10, 10, 10, 4, 3, 3].
                   ×                   Multiply the Booleans with the corr. digits.
                              S        Compute the sum of the products.
                               ×.ȷ     Multiply the sum by 500.
                                  _    Subtract n.
                                   »0  Return the maximum of the difference and 0.

```

# Answer
> 3 votes
## JavaScript (ES6), ~~137~~ ~~135~~ ~~102~~ 81 bytes

```
n=>(n-=[5,0,.3,.6,1,2,3,4][[.3,1,3,4,7,8,10].findIndex(m=>m*500>n)+1]*5e3)<0?-n:0

```

If the user has 5000 or more reputation then `findIndex` fails, returning -1, so the result is incremented to that I can index into the array of new reputations needed. Edit: Saved 21 bytes by scaling the input and output array.

```
   [.3,1,3,4,7,8,10]        Old reputations of note, divided by 500
    .findIndex(m=>m*500>n)  Skip ones that have been achieved
     +1                     Normalise the return value
  [5,0,.3,.6,1,2,3,4][]     Index into new reputation needed
   *5e3                     Scaling factor
 n-=                        Compare to the current reputation
()<0?-n:0                   Negate to return the requirement

```

# Answer
> 3 votes
# CJam, 38 bytes

```
0000000: 72 69 5f 35 30 2f 22 64 50 46 28 1e 0a 03 22 66  ri_50/"dPF(..."f
0000010: 3c 3a 2b 22 fa c8 96 64 32 1e 0f 00 22 3d 69 65  <:+"...d2..."=ie
0000020: 32 5c 2d 55 65 3e                                2\-Ue>

```

Try it online! or verify all test cases.1

### How it works

```
ri                        Read an integer n from STDIN.
  _50/                    Push a copy and divide it by 50.
     "…"                  Push the string with code points [100 80 70 40 30 10 3].
        f<                Compare each code point with n / 50.
          :+              Add the resulting Booleans.
            "…"           Push the string with code points
                          [250 200 150 100 50 30 15 0].
               =          Select the one at the index of the sum.
                i         Convert from character to integer.
                 e2       Multiply by 100.
                   \-     Subtract n from the product.
                     Ue>  Take the maximum of the difference and 0.

```

1 Note that the code contains a null byte, which causes problems in some browsers.

# Answer
> 2 votes
# Python ~~156~~ 152 bytes

```
s=str.split;n=input()
for k,v in map(s,s('5e3 5r4e3 5r3500 30./7r2e3 5r1500 10./3r500 6r1 1','r')):
 w=u(k);r=eval(v)*w
 if w<=n:print max(0,r-n);break

```

The data string (`5e3 5r4e3 5r3500 30./7r2e3 5r1500 10./3r500 6r1 1`) is a list with the format `(old_rep1) (new_rep1/old_rep1)r(old_repr) (new_rep2/old_rep2)` only including privleges which set the new max rep (users with \>750 rep still need at least 3k rep post-graduation, even though they will be an established user at 1k. The list is sorted from highest rep first to lowest rep last.

# Answer
> 2 votes
## Python, 88 bytes

```
lambda n:max(sum(500*b*(n>=a*500)for a,b in zip([.3,1,3,4,7,8,10],[3,3,4]+[10]*4))-n,0)

```

For each new beta privilege exceeded, adds the rep amount needed to get to the next graduated privilege. Then, the additional rep needed is the new rep minus the current rep, but no less than 0.

Both rep boundary lists are shortened by rep in multiples of `500`.

# Answer
> 1 votes
# Pyth - ~~71~~ ~~70~~ ~~69~~ ~~77~~ ~~75~~ 77 bytes

```
eS,Z-@CM"\x00ǴϨלߐৄஸᎈ✐㪘丠憨"xKCM"\x00ŞˮϨӢǴלߐඬྠᎈ"e<#QK

```

Test Suite.

# Answer
> 1 votes
## LiveCode 8, 318 bytes

```
function g c
    local b,g,r
    put c into r
    put "0.15,0.35,0.5,0.75,1,1.25,1.5,2,3.5,4,5" into b
    split b by ","
    put "0.3,0.1,0.6,0.2,0.4,0.5,1,2,3,4,5" into g
    split g by ","
    repeat with i=1 to 11
       if c>b[i]*1000 and not c>g[i]*5000 then put max(r,g[i]*5000) into r
    end repeat
    return r-c
 end g

```

As `wizzwizz4` suggested, here is an explanation:

```
function g c

```

Create a function named `g` taking a single parameter `c`. `c` is the user's current reputation. Equivalent to `def g(c)` in Python.

```
local b,g,r

```

Create three local variables: `b`,`g`, and `r`. `b` will be the reputation cutoffs for privileges in beta, `g` will contain the new reputation cutoffs after graduation, and `r` will represent the total reputation the user will have to have after graduation to retain their privileges.

```
put c into r

```

This copies the value of `c`(the user's current reputation) into `r`. Equivalent to `r=c` in Python)

```
put "0.15,0.35,0.5,0.75,1,1.25,1.5,2,3.5,4,5" into b

```

Similar to above, this sets b to a string containing a comma-deliminated list of the reputation cutoffs in beta, divided by 1000. Equivalent to `b="0.15,0.35,0.5,0.75,1,1.25,1.5,2,3.5,4,5"` in Python.

```
split b by ","

```

This splits the local variable `b` into an array, using `,` as the delimiter. This array now contains the reputation cutoffs in beta, divided by 1000. Equivalent to `b.split(",")` in Python.

```
put "0.3,0.1,0.6,0.2,0.4,0.5,1,2,3,4,5" into g
split g by ","

```

Same as above, except that `g` now contains a list of the reputation cutoffs after graduation, divided by 5000

```
repeat with i=1 to 11

```

Similar to a `for` loop in other languages, this repeates 11 times, with `i` assigned the next value in the sequence 1 to 11 each time. Arrays in LiveCode start at index 1. In Python, this would be `for i in range(11)`.

```
if c>b[i]*1000 and not c>g[i]*5000 then put max(r,g[i]*5000) into r

```

This is the main logic of the function. It checks to see if the user has enough reputation for the privilege in position `i` of the beta list, if so, and if they don't have enough reputation for the privilege after graduation, it sets the variable `r`(representing the total reputation that the user will have to have to retain their privileges after graduation) to the reputation cutoff after graduation for that privilege (only if the new reputation is higher than the previous one). The equivalent Python code would be `if c>b[i]*1000 and not c>g[i]*5000:
 r=max(g[i]*5000,r)` end repeat Ends the repeat loop. Similar to C or Java's `}`. LiveCode uses the syntax `end 'insert contruct name` to end a `repeat` loop, an `if`, a `switch` etc...

```
return r-c

```

Fairly self-explanatory.

```
end g

```

Ends the function `g`.

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


title: Driftsort an array

text:
# Question
Title: Driftsort an array
Driftsort is a simple way to "sort" an array. It works by "sliding" or "rotating" the elements over in the array until the array is sorted, or until the array fails to be sorted.

Let's walk through two examples. First, consider the array `[10, 2, 3, 4, 7]`. Since the array is not sorted, we rotate it once. (This can happen in either direction, so long as it remains the same direction.) Then, the array becomes:

```
[7, 10, 2, 3, 4]

```

This is not sorted, so we rotate again.

```
[4, 7, 10, 2, 3]

```

And again:

```
[3, 4, 7, 10, 2]

```

And a final time:

```
[2, 3, 4, 7, 10]

```

And it's sorted! So the array `[10, 2, 3, 4, 7]` is driftsortable. Here are all the rotations of the array, for clarity:

```
[10, 2, 3, 4, 7]
[7, 10, 2, 3, 4]
[4, 7, 10, 2, 3]
[3, 4, 7, 10, 2]
[2, 3, 4, 7, 10]

```

Consider now the array `[5, 3, 9, 2, 6, 7]`. Look at its rotations:

```
[5, 3, 9, 2, 6, 7]
[7, 5, 3, 9, 2, 6]
[6, 7, 5, 3, 9, 2]
[2, 6, 7, 5, 3, 9]
[9, 2, 6, 7, 5, 3]
[3, 9, 2, 6, 7, 5]

```

None of these arrays are sorted, so the array `[5, 3, 9, 2, 6, 7]` is not driftsortable.

---

**Objective** Given a nonempty array/list of integers as input to a program/function, implement driftsort on the input and output it, or output a falsey value (**or** an empty array/list) if it cannot be driftsorted. The integers are bound to your languages max/min, but this must be at least 255 for the max, and 0 for the min.

You may use built-in sorting methods, but not a built-in which solves the challenge.

This is a , so the shortest program in bytes.

## Test cases

```
input => output
[1] => [1]
[5, 0, 5] => [0, 5, 5]
[3, 2, 1] => false
[0, 9, 3] => false
[1, 2, 3, 4] => [1, 2, 3, 4]
[4, 1, 2, 3] => [1, 2, 3, 4]
[0, 2, 0, 2] => false
[5, 3, 9, 2, 6, 7] => false
[0, 0, 0, 0, 0, 0, 0] => [0, 0, 0, 0, 0, 0, 0]
[75, 230, 30, 42, 50] => [30, 42, 50, 75, 230]
[255, 255, 200, 200, 203] => [200, 200, 203, 255, 255]

```

# Answer
# Jelly, 6 bytes

```
ṙỤċṢȧṢ

```

Try it online! or verify all test cases.

### How it works

```
ṙỤċṢȧṢ  Main link. Argument: A (list)

 Ụ      Grade up; return the indices of A, sorted by their corresponding values.
ṛ       Rotate A by each index, yielding the list of all rotations.
   Ṣ    Yield A, sorted.
  ċ     Count the number of times sorted(A) appears in the rotations.
        This gives 0 if the list isn't driftsortable.
    ȧṢ  Logical AND with sorted(A); replaces a positive count with the sorted list.

```
> 9 votes

# Answer
# Ruby, 33

```
->a{a.any?{a.sort==a.rotate!}&&a}

```

`a.any?` fires up to once for each element in the array, except it stops (and returns true) as soon as the array has been mutated into a sorted state. If this happens, we return the mutated array. Otherwise we return the false value that `any?` returns.
> 18 votes

# Answer
## Python 2, 51 bytes

```
lambda l:sorted(l)*(map(cmp,l[-1:]+l,l).count(1)<3)

```

Doesn't bother rotating. Instead, sorts the list, then sees if the original is drift-sortable by checking if there's at most one decrease among consecutive elements of the cyclified list. The count is `<3` because `map` pads the shorter list with `None` at the end, adding a fake decrease.
> 14 votes

# Answer
## Pyth, 9 bytes

```
*SQ}SQ.:+

```

Explanation:

```
           - Q = eval(input())
         + -    Q+Q
       .:  -   sublists(^)
   }       -  V in ^
    SQ     -   sorted(Q)
*SQ        - ^ * sorted(Q) (return sorted(Q) if ^ True)

```

Try it here!

Or use a test suite!
> 10 votes

# Answer
# Matlab, ~~61~~ ~~47~~ 41 bytes

Thanks @Suever for -6 bytes!

```
@(a)sort(a)+0*min(strfind([a,a],sort(a)))

```

If `strfind([a,a],sort(a))` tries to find the sorted input vector as a 'substring' of the unsorted, that was appended to itself. If true, the input is driftsortable and we get a vector of length 2, if not we get a empty vector. `min` just transforms this to an number / empty vector. Adding the sorted vector to 0 just displays it, adding it to an empty vector throws an error.
> 6 votes

# Answer
# Julia, ~~71~~ ~~66~~ 52 bytes

```
x->(y=sort(x))∈[circshift(x,i)for i=1:endof(x)]&&y

```

This is an anonymous function that accepts an array and returns an array or a boolean. To call it, assign it to a variable.

For an input array *x*, we construct the set of all rotations of *x* and check whether the sorted version *x* is an element of that list. If it is, we return *x* sorted, otherwise we return false.

Saved 19 bytes thanks to Dennis!
> 5 votes

# Answer
## JavaScript (ES6), ~~72~~ ~~70~~ 65 bytes

```
a=>a.map(y=>{c+=x>y;x=y},x=a.slice(c=-1))|c<1&&a.sort((a,b)=>a-b)

```

Returns `0` on failure. Previous ~~85~~ ~~83~~ 80-byte version avoided calling `sort`:

```
a=>a.map((y,i)=>{x>y&&(c++,j=i);x=y},x=a.slice(c=-1))|c<1&&a.splice(j).concat(a)

```

Edit: Saved 2 bytes by initialising `c` to `-1` instead of `0`. Saved 5 bytes by switching from `reduce` to `map`, sigh...
> 4 votes

# Answer
# Pip, 15 + 1 = ~~17~~ 16 bytes

Ugh, the other golfing languages are blowing this out of the water. However, since I've already written it...

```
L#gI$<gPBPOgYgy

```

Takes input as space-separated command-line arguments. Requires `-p` or another array-formatting flag to display the result legibly rather than concatenated. The false case outputs an empty string, which is visible by virtue of the trailing newline.

```
                 Implicit: g is array of cmdline args; y is empty string
L#g              Loop len(g) times:
         POg       Pop the first item from g
      gPB          Push it onto the back of g
    $<             Fold on < (true if g is now sorted)
   I        Yg     If true, yank g into y
              y  Autoprint y

```
> 4 votes

# Answer
# 05AB1E, 12 bytes

Code:

```
DgFÀÐ{Qi,}}0

```

Uses **CP-1252** encoding. Try it online!.
> 3 votes

# Answer
## Snowman 1.0.2, 27 bytes

```
((}#AsO|##aC,as|aLNdE`aR*))

```

This is a subroutine that takes input from and outputs to the current permavar.

Try it online!

```
((                       ))  subroutine
  }                          set our active variables b, e, and g:
                              .[a] *[b] .[c]
                              .[d]      *[e]    (* represents an active variable)
                              .[f] *[g] .[h]
   #                         store the input in variable b
    AsO                      sort in-place
       |                     swap b with g; now sorted input is in g
        ##                   store the input again in b and e
          aC                 concat; now the input doubled is in b and e is empty
            ,                swap e/g; now b has 2*input and e has sorted input
             as              split 2*input on sort(input) and store result in g
               |             bring the result up to b (we no longer care about g)
                aLNdE        take length and decrement; now we have 0 in b if the
                               array is not driftsortable and 1 if it is
                     `aR     repeat e (the sorted array) b times:
                               if b is 0 (nondriftsortable), returns [] (falsy)
                               otherwise (b=1), returns sorted array unchanged
                        *    put this back into the permavar

```
> 3 votes

# Answer
# Javascript ES6, ~~48~~ ~~45~~ 43 chars

```
x=>~(x+[,x]).indexOf(x.sort((a,b)=>a-b))&&x

```

Test:

```
f=x=>~(x+[,x]).indexOf(x.sort((a,b)=>a-b))&&x
;`[1] => [1]
[5, 0, 5] => [0, 5, 5]
[3, 2, 1] => false
[0, 9, 3] => false
[1, 2, 3, 4] => [1, 2, 3, 4]
[4, 1, 2, 3] => [1, 2, 3, 4]
[0, 2, 0, 2] => false
[5, 3, 9, 2, 6, 7] => false
[0, 0, 0, 0, 0, 0, 0] => [0, 0, 0, 0, 0, 0, 0]
[75, 230, 30, 42, 50] => [30, 42, 50, 75, 230]
[255, 255, 200, 200, 203] => [200, 200, 203, 255, 255]`
.split`
`.map(t => t.replace(/^(.*) => (.*)$/, "f($1)+'' == $2")).every(eval)

```
> 3 votes

# Answer
# MATL, ~~13~~ ~~12~~ ~~10~~ 9 bytes

```
SGthyXfa*

```

The same idea as @flawr's answer where we hijack `strfind` (`Xf`) to find the sorted version of the input within the concatenation of two copies of the input.

**Try it Online!**

**Explanation**

```
        % Implicitly get input
S       % Sort the input
Gth     % Explicitly grab the input again and concatenate with itself
y       % Copy the sorted version from the bottom of the stack
Xf      % Look for the sorted version as a subset
a       % Gives a 1 if there were matches and 0 otherwise
*       % Multiply by the sorted array. Yields all zeros for no match and the
        % sorted array when a match was found
        % Implicitly display the stack contents

```
> 3 votes

# Answer
# Julia, 33 bytes

```
x->sum(diff([x;x]).<0)<3&&sort(x)

```

Try it online!

### How it works

This concatenates the array **x** with itself and counts the number of pairs that are out of order, i.e. the number of contiguous subarrays **\[a, b\]** for which **b - a \< 0**. If **c** is the number of unordered pairs of **x** itself and **t** is **1** if **x**'s last element is larger than its first, `sum` will return **2c + t**.

The array **x** is driftsortable iff **(c, t) = (1, 0)** (**x** has to be rotated to the smaller value of the only unordered pair), **(c, t) = (0, 1)** (**x** is sorted) or **(c, t) = (0, 0)** (**x** is sorted and all of its elements are equal), which is true iff **2c + t \< 3**.
> 3 votes

# Answer
# Brachylog, 39 bytes

```
l:0re:?{[0:L],!L.|rh$(L,?h-1=:L:1&.}.o.

```

I really need to add an optional argument to `$( - circular permute left` to permute more than once... this would have been 13 bytes. This will wait after implementing a stable new transpiler in Prolog.

### Explanation

```
l:0re                                     I = a number between 0 and the length of Input
     :?{[0:L],!L.|rh$(L,?h-1=:L:1&.}      All this mess is simply circular permutating the
                                          input I times
                                    .o.   Unify the Output with that circular permutation
                                          if it is sorted, else try another value of I

```
> 2 votes

# Answer
# Ruby, 47 bytes

Recursive function. Returns `nil` if the input array cannot be driftsorted.

```
f=->a,i=0{a.sort==a ?a:a[i+=1]?f[a.rotate,i]:p}

```
> 2 votes

# Answer
## CJam, ~~17~~ 13 bytes

*Thanks to Dennis for saving 4 bytes.*

```
{_$\_+1$#)g*}

```

An unnamed block (function) which takes and returns a list.

Test suite.

### Explanation

This essentially uses xnor's observation that the sorted list appears in twice the original list if its drift sortable:

```
_$   e# Duplicate input and sort.
\_+  e# Get other copy and append to itself.
1$   e# Copy sorted list.
#    e# Find first position of sorted list in twice the original,
     e# of -1 if it's not found.
)g   e# Increment and take signum to map to 0 or 1.
*    e# Repeat sorted array that many times to turn it into an empty
     e# array if the input was not drift sortable.

```
> 2 votes

# Answer
# C++ 14, 242 chars

```
#include<iostream>
#include<vector>
#include<algorithm>
#define b v.begin()
using namespace std;int main(){vector<int>v;int x,n=0;for(;cin>>x;++n)v.push_back(x);for(x=n;x--;rotate(b,b+1,b+n))if(is_sorted(b,b+n)){for(x:v)cout<<x<<' ';return 0;}}

```

If I can't leave output empty, 252 chars http://ideone.com/HAzJ5V

```
#include<iostream>
#include<vector>
#include<algorithm>
#define b v.begin()
using namespace std;int main(){vector<int>v;int x,n=0;for(;cin>>x;++n)v.push_back(x);for(x=n;x--;rotate(b,b+1,b+n))if(is_sorted(b,b+n)){for(x:v)cout<<x<<' ';return 0;}cout<<'-';}

```

Ungolfed version http://ideone.com/Dsbs8W

```
#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

#define b v.begin()

int main()
{
  vector <int> v;
  int x, n=0;

  for(;cin>>x;++n)
    v.push_back(x);

  for(x=n;x--;rotate(b,b+1,b+n))
    if(is_sorted(b,b+n))
    {
      for(x:v) cout<<x<<' ';
      return 0;
    }

  cout << '-';
}

```

PS: Based on @MichelfrancisBustillos's idea.
> 2 votes

# Answer
# Java 7, 207 bytes

```
int[]D(int[]i){int x,z;z=x=-1;int[]d=new int[i.length];while(++x<i.length)if(i[x]>i[(x+1)%i.length])if(z<0)z=(x+1)%i.length;else return null;if(z<0)z=0;x=-1;while(++x<d.length)d[x]=i[z++%i.length];return d;}

```

**Detailed** *try here*

```
// driftsort in ascending-order
int[] D(int[]i)
{
    int x = -1,z = -1;
    int[] d = new int[i.length];

    while ((++x) < i.length)
    {
        if (i[x] > i[(x+1)%i.length])
        {
            if(z < 0) z = (x+1)%i.length;
            else return null; // not driftsortable
        }
    }

    if(z < 0) z = 0;
    x = -1;
    while ((++x) < d.length)
    {
        d[x] = i[(z++)%i.length];
    }

    return d;
}

```
> 2 votes

# Answer
# Java 175

prints out the output as space separated values, or prints `f` for a falsey value.

```
void d(int[]a){String s;for(int v,w,x=-1,y,z=a.length;++x<z;){v=a[x];s=""+v;for(y=0;++y<z;v=w){w=a[(x+y)%z];if(v>w){s="f";break;}s+=" "+w;}if(y==z)break;}System.out.print(s);}

```

goes through all the combinations of the array of integers until it finds the valid sequence or runs out of combinations. the array isn't modified, but instead the driftsorted sequence is stored as a space delimited string.

a bit more readable:

```
void driftsort(int[]array){
    String str;
    for(int previous,current,x=-1,y,len=array.length;++x<len;){
        previous=array[x];
        s=""+previous;
        for(y=0;++y<len;previous=current){
            current=array[(y+x)%len];
            if(previous>current){
                str="false";
                break;
            }
            str+=" "+current;
        }
        if(y==len)break;
    }
    System.out.print(str);
}

```

try it online
> 2 votes

# Answer
# C, 105 bytes

```
i,s;main(c,v)char**v;{c--;while(i++<c)if(atoi(v[i])>atoi(v[i%c+1]))c*=!s,s=i;while(--i)puts(v[s++%c+1]);}

```

This accepts the input integers as separate command-line arguments and prints the output list as one integer per line.

If the list isn't driftsortable, the program exits prematurely due to a floating point exception, so its empty output represents an empty list.

### Verification

```
$ gcc -o driftsort driftsort.c 2>&-
$ ./driftsort 1 | cat
1
$ ./driftsort 5 0 5 | cat
0
5
5
$ ./driftsort 3 2 1 | cat
$ ./driftsort 0 9 3 | cat
$ ./driftsort 1 2 3 4 | cat
1
2
3
4
$ ./driftsort 4 1 2 3 | cat
1
2
3
4
$ ./driftsort 0 2 0 2 | cat
$ ./driftsort 5 3 9 2 6 7 | cat
$ ./driftsort 0 0 0 0 0 0 0 | cat
0
0
0
0
0
0
0
$ ./driftsort 75 230 30 42 50 | cat
30
42
50
75
230
$ ./driftsort 255 255 200 200 203 | cat
200
200
203
255
255

```
> 2 votes

# Answer
## Ruby, 28

```
->a{(a*2*?,)[a.sort!*?,]&&a}

```

Returns either the sorted array, or `nil` (which is a falsy value) if the input is not drift-sortable.
> 2 votes

# Answer
# Python, 53 bytes

```
s,N=sorted,lambda x:s(x)*(str(s(x))[1:-1]in str(x+x))

```

If you want to test this head over to https://www.repl.it/languages/python3 and copy paste this:

```
s,N=sorted,lambda x:s(x)*(str(s(x))[1:-1]in str(x+x))
print(N([1,2,3,4,5,0]))

```

How it works:

* `s` is a variable storing the `sorted` python function which sorts lists
* `N` is the main function
* The input list sorted: `s(x)` is multiplied by whether or not the list is driftsortable `str(s(x))[1:-1]in str(x+x)` (thanks to @xnor)
    + This works because `[1,2,3,4]*false` results in an empty list `[]`
    + and `[1,2,3,4]*true` results in `[1,2,3,4]`
> 2 votes

# Answer
# Python, 83 bytes

```
def f(l):g=sorted(l);return g if any(l[x:]+l[:x]==g for x in range(len(l)))else 1>2

```

This got put to shame by the other python answers, but I might as well post it anyway. I really dislike the

```
range(len(l)))

```

part. Is there a faster way to iterate through the list?
> 1 votes

# Answer
# MATLAB/Octave, 118 bytes

```
function r(a)
i=0
while (~issorted(a) && i<length(a))
    a=a([2:end 1]),i=i+1
end
if issorted(a)
    a
else
    0
end

```
> 1 votes

# Answer
## PowerShell v2+, ~~87~~ 80 bytes

```
param($a)0..($a.length-1)|%{if($a[$_-1]-gt$a[$_]){$c--}};(0,($a|sort))[++$c-ge0]

```

Steps through the input list `$a`, checking each pairwise element (including the last and first) to see if there is more than one decreasing pair. If the particular pair is decreasing, we decrement `$c`. Outputs either the sorted list, or single element `0`, based on the value of `$c` at the end. If more than one "bad" pair is present, then `++$c` will still be negative, otherwise it will be at least `0`, so the second element of the pseudo-ternary is chosen (`$a|sort`).

I see xnor did something similar, but I came up with this independently.
> 1 votes

# Answer
## C++, 313 ~~359~~ ~~370~~ bytes

*Huge shoutout to @Qwertiy for getting this working and teaching me some great golfing methods!*

### Golfed:

```
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main(){vector<int> v;int x,c=0,s=0,y;while(cin>>x)v.push_back(x);do if(rotate(v.begin(),v.begin()+1,v.end()),c++,is_sorted(v.begin(),v.end()))s=1;while(!s&c<=v.size());if(s)for(y=0;y<v.size();y++)cout<<v[y]<<" ";else cout<<"False";}

```

### Ungolfed:

```
#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int main(){
  vector <int> v;
  int x, c=0, s=0, y;

  while(cin>>x)
    v.push_back(x);

  do
    if (
      rotate(v.begin(),v.begin()+1,v.end()),
      c++,
      is_sorted(v.begin(),v.end())
    ) s = 1;
  while(!s & c <= v.size());

  if (s)
    for(y=0; y<v.size(); y++)
      cout<<v[y]<<" ";
  else
    cout<<"False";
}

```
> 1 votes

# Answer
# Factor, 47 bytes

```
[ dup dup append [ natural-sort ] dip subseq? ]

```

join the sequence onto itself, then check if the sorted rendition of the original is a subsequence.
> 1 votes

# Answer
# Mathematica ~~55 50 61~~ 58 bytes

With 3 bytes saved thanks to Martin Büttner.

My earlier attempts did not pass all of the test case. I needed to add `Union` to avoid repetitions in list that were input in order.

```
Join@Union@Cases[NestList[RotateRight,#,Length@#],Sort@#]&

```

**Tests**

```
Join@Union@Cases[NestList[RotateRight,#,Length@#],Sort@#]&/@
{{1},{5,0,5},{3,2,1},{0,9,3},{1,2,3,4},{4,1,2,3},{0,2,0,2},{5,3,9,2,6,7},
{0,0,0,0,0,0,0},{75,230,30,42,50},{255,255,200,200,203}}

```

> {{1}, {0, 5, 5}, {}, {}, {1, 2, 3, 4}, {1, 2, 3, 4}, {}, {}, {0, 0, 0, 0, 0, 0, 0}, {30, 42, 50, 75, 230}, {200, 200, 203, 255, 255}}

---

**Explanation**

Right rotate the input list from 1 to `n` times, where `n` is the length of the input list. If the sorted input list is among the output rotated lists, return it; otherwise return an empty list.
> 1 votes

# Answer
## C#, ~~125~~ 117 bytes

```
int[]d(int[] m){int r=0;for(int i=0;i<m.Length-1;i++)if(m[i+1]<m[i])r++;if(r<2){Array.Sort(m);return m;}return null;}

```

ungolfed:

```
int[] driftsort(int[] m)
    {
        int r = 0;
        for (int i = 0; i < m.Length - 1; i++)
            if (m[i + 1] < m[i])
                r++;

        if (r < 2) { Array.Sort(m); return m; }
        return null;
    }

```

there is much to get smaller here, advice would be appreciated

thanks to Erik Konstantopoulos for -8
> 1 votes

# Answer
# Mathcad, TBD

In Mathcad, 0 (scalar) == false.

(Equivalent) byte count is TBD until counting method agreed. Approx 52 bytes using a byte = operator / symbol keyboard equivalence.
> 1 votes

# Answer
# PHP, 98 bytes

Outputs a `1` if driftsortable, else nothing

```
$a=$argv[1];$b=$a;sort($a);foreach($a as $v){echo($a===$b?1:'');array_unshift($b, array_pop($b));}

```
> 1 votes

---
Tags: code-golf, sorting
---


title: Linear Independence

text:
# Question
Title: Linear Independence
Given a set of vectors all of the same positive finite dimension, output a falsey value if they are linearly dependent and a truthy value if they are linearly independent. A set of vectors v1, v2, ... is linearly dependent if for some scalars a1, a2, ... not all equal to 0, a1v1 \+ a2v2 \+ ... = 0. (0 is the zero vector.)

Note: Using an inbuilt function to find the rank of a matrix or test vectors for linear dependence is not allowed.

Note 2: All input will be formed from integers.

Test cases (input -\> output):

```
[[0,1],[2,3]] -> True
[[1,2],[2,4]] -> False
[[2,6,8],[3,9,12]] -> False
[[1,2],[2,3],[3,4]] -> False
[[1,0,0],[0,1,0],[0,0,1]] -> True
[[0]] -> False
[] -> True
[[1,1],[0,1],[1,0]] -> False
[[1,2,3],[1,3,5],[0,0,0]] -> False

```

# Answer
# Matlab - ~~19~~ 16 bytes

```
@(A)det(A*A')>.5

```

If the product of the matrix and its transpose is singular, then the rows of the matrix are linearly dependent. The determinant is non-negative, and since the entries are integral (thank you Alex A.), the determinant is integral and can be compared to .5.

It would have been nice to just do `@(A)~det(A*A')`, but unfortunately `det` can give almost-zero for singular matrices.

Try it on ideone
> 5 votes

# Answer
# Julia, ~~28~~ 27 bytes

```
X->X==[]||eigmin(X'X)>eps()

```

This is an anonymous function that accepts a 2-dimensional array with the vectors as columns and returns a boolean. To call it, assign it to a variable.

For any real, non-singular matrix **X**, the square matrix **X**T**X** is positive definite. Since a matrix is non-singular if and only if all of its column vectors are linearly independent and non-singular implies **X**T**X** is positive definite, we can declare the vectors to be linearly independent if the product is positive definite. A matrix is positive definite if and only if all of its eigenvalues are strictly positive, or equivalently when its smallest eigenvalue is strictly positive.

So for an input matrix **X**, we construct **X**T**X** and get the minimum eigenvalue using `eigmin(X'X)`. To account for floating point error, we check this against the machine precision, `eps`, rather than 0, to declare positivity. Since we also want empty input to return `true`, we can simply add the condition `X==[]`.

Saved 1 byte thanks to Dennis!
> 5 votes

# Answer
# R, ~~72~~ 60 bytes

```
function(x,m,n)!is.null(x)&&all(pracma::rref(x)==diag(,m,n))

```

This is a function that accepts the vectors as columns in a matrix as well as the dimensions of the matrix and returns a logical. To call it, assign it to a variable. It requires the `pracma` package to be installed but it doesn't have to be imported.

The actual checking for linear independence is done by row reducing the matrix to echelon form and checking whether that's equal to an identity matrix of matching dimension. We just need a special case for when the input is empty.

Saved 12 bytes with help from Luis Mendo!
> 3 votes

# Answer
# Mathematica - 29 bytes

```
#=={}||Det[#.Transpose@#]!=0&

```

Uses the property that the product of the eigenvalues of matrix A is equal to the determinant of A.

Sample

```
#=={}||Det[#.Transpose@#]!=0&@{{1,2,3},{1,3,5},{0,0,0}}
>>  False

```
> 3 votes

# Answer
# Julia, 14 bytes

```
M->det(M'M)>.5

```

Based on @Anna's MATLAB answer and @AlexA.'s Julia answer. Expects a matrix whose columns are the input vectors and returns a Boolean.

`det` returns a float, so we cannot compare the result directly with **0**. However, since the entries of **M** are integers, the lowest possible positive determinant is **1**.

### Verification

```
julia> f = M->det(M'M)>.5
(anonymous function)

julia> [f(M) for M in(
         [0 2;1 3],
         [1 2;2 4],
         [2 3;6 9;8 12],
         [1 2 3;2 3 4],
         [1 0 0;0 1 0;0 0 1],
         zeros((1,1)),
         zeros((0,0)),
         [1 0 1;1 1 0],
         [1 1 0;2 3 0;3 5 0]
       )]
9-element Array{Any,1}:
  true
 false
 false
 false
  true
 false
  true
 false
 false

```
> 3 votes

# Answer
# NARS2000 APL, 12 bytes

```
(≡≤-.×)⊢+.×⍉

```

### How it works

```
(≡≤-.×)⊢+.×⍉  Monadic function. Right argument: M

           ⍉  Transpose M.
       ⊢      Yield M.
        +.×   Perform matrix multiplication.
              For empty M, this yields a zero vector (for some reason).
(     )       Apply this matrix to the matrix product:
   -.×          Compute the determinant.
                This (mistakenly) yields 0 if M is empty.
 ≡              Yield the depth of M (1 is non-empty, 0 if empty).
  ≤             Compare.
                Since 0≤0, this corrects the error.

```
> 3 votes

# Answer
# Octave, ~~32~~ 27 bytes

*Thanks to @Suever for removing 5 bytes!*

```
@(x)~numel(x)|any(rref(x)')

```

The code defines an anonymous function. To call it assign it to a variable or use `ans`. The result is a non-empty array, which in Octave is truthy if all its entries are nonzero.

Try all test cases online.

This is based on the reduced row echelon form of a matrix. A non-empty matrix is full-rank iff each row of its reduced row echelon form contains at least one non-zero entry. This is checked by condition `any(rref(x)'`, where `'` can be used to transpose instead of `.'` because the entries are not complex. The empty matrix is dealt with separately by the condition `~numel(x)` (which is the same as `isempty(x)` but shorter).
> 2 votes

# Answer
# JavaScript (ES6), 162

```
M=>M.sort((a,b)=>P(a)-P(b),P=r=>r.findIndex(v=>v)).map(_=>M=M.map((r,i)=>(p=P(r))>q?(k=M[i],q=p,r):r.map((v,j)=>v*k[q]-k[j]*r[p]),q=-1))&&M.every(r=>r.some(v=>v))

```

Reduce the matrix and check if every row has at least 1 non zero element.

*Less golfed*

```
M=>(
  P=r=> P=r=>r.findIndex(v=>v)), // First nonzero element position or -1
  // sort to have P in ascending order, but rows all 0 are at top
  M.sort((a,b)=>P(a)-P(b)),
  M.map(_=> // repeat transformation for the number of rows
    M=M.map((r,i)=>(
      p = P(r),
      p > q
       ? (k=M[i], q=p, r)
         // row transform
         // note: a 0s row generate a NaN row as p is -1
       : r.map((v,j) => v*k[q] - k[j]*r[p])
     )
     ,q=-1
    )
  ),
  // return false if there are rows all 0 or all NaN
  M.every(r=>r.some(v=>v))
)

```

**Test**

```
F=M=>M.sort((a,b)=>P(a)-P(b),P=r=>r.findIndex(v=>v))
.map(_=>M=M.map((r,i)=>
(p=P(r))>q?(k=M[i],q=p,r):r.map((v,j)=>v*k[q]-k[j]*r[p])
,q=-1))&&M.every(r=>r.some(v=>v))

console.log=(...x)=>O.textContent += x +'\n'

;[[[0,1],[2,3]] // True
,[[1,2],[2,4]] // False
,[[2,6,8],[3,9,12]] // False
,[[1,2],[2,3],[3,4]] // False
,[[1,0,0],[0,1,0],[0,0,1]] // True
,[[0]] // False
,[[0,0],[1,1]] // False
,[] // True
,[[1,1],[0,1],[1,0]] // False
,[[1,2,3],[1,3,5],[0,0,0]] // False
,[[1,2,3],[4,5,6]] // True
].forEach(m=>console.log(m,F(m)))
```

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

# Answer
# MATL, ~~13~~ 11 bytes

```
t!Y*2$0ZnYo

```

Thanks to Luis for golfing off two bytes.

Based on Anna's MATLAB answer.

# Explanation

```
t!Y*2$0ZnYo
t              duplicate input
 !             transpose
  Y*           matrix product, yields X^T * X
    2$0Zn      determinant
         Yo    round

```
> 2 votes

# Answer
# Python 2 with NumPy - ~~85~~ ~~112~~ ~~103~~ 102 bytes

```
import numpy
x=input(i)
try:print reduce(lambda a,b:a*b,numpy.linalg.eigvals(x))
except:print(x==[])|0

```

Hopefully can get a few off, FGITW.
> 1 votes

# Answer
# MATL, 33 bytes

```
|ssQt_w2$:GZy1)Z^!2$1!G*Xs!Xa~s3<

```

This uses current release (16.1.0) of the language, which predates the challenge.

Input format is

```
[0 1; 2 3]

```

or

```
[[0 1];[2 3]]

```

**Try it online!**

### Explanation

This uses only integer opeations, so it is not subject to rounding errors (as long as the involved integers don't exceed `2^52`).

It works by applying the definition. It suffices to test for integer scalars *a*1, *a*2, ... between −*S*−1 and *S*+1, where *S* is the sum of absolute values of all numbers in the input 2D array. In fact much lower values of *S* could be used, but this one requires few bytes to compute.

All "combinations" (Cartesian product) of values *a*1, *a*2, ... between −*S*−1 and *S*+1 are tested. The input vectors **v**1, **v**2, ... are independent iff only *one* of the linear combinations *a*1**v**1+*a*2**v**2+... gives a **0** result (namely that for coefficients *a*1, *a*2, ... = 0).

```
|ssQ    % sum of absolute values of input plus 1
t_w     % duplicate, negate, swap
2$:     % binary range: [-S-1 -S ... S+1]
GZy1)   % push input. Number of rows (i.e. number of vectors), N
Z^      % Cartesian power. Gives (2S+3)×N-column array
!2$1!   % Permute dimensions to get N×1×(2S+3) array
G       % Push input: N×M array
*       % Product, element-wise with broadcast: N×M×(2S+3) array
Xs      % sum along first dimension (compute each linear combination): 1×M×(2S+3)
!       % Transpose: M×1×(2S+3)
Xa~     % Any along first dimension, negate: 1×1×(2S+3). True for 0-vector results
s       % Sum (number of 0-vector results)
2<      % True if less than 2

```
> 1 votes

# Answer
# J, 18 bytes

```
1<:[:-/ .*|:+/ .*]

```

This is a tacit verb that accepts a matrix with the vectors as columns and returns 0 or 1 depending on whether the vectors are linearly dependent or independent, respectively.

The approach is based on Anna's Matlab answer and Dennis' Julia answer. For a matrix **X**, the square matrix **X**T**X** is singular (i.e. has zero determinant) if the columns of **X** are linearly independent. Since all elements of **X** are guaranteed to be integers, the smallest possible nonzero determinant is 1. Thus we compare 1 ≤ det|**X**T**X**| to get the result.

Examples (note that `|: >` is just for shaping the input):

```
  f =: 1<:[:-/ .*|:+/ .*]
  f |: > 0 1; 2 3
1
  f |: > 1 2; 2 4
0
  f |: > 2 6 8; 3 9 12
0
  f |: > 1 2; 2 3; 3 4
0
  f |: > 1 0 0; 0 1 0; 0 0 1
1
  f 0
0
  f (0 0 $ 0)
1
  f |: > 1 1; 0 1; 1 0
0
  f |: > 1 2 3; 1 3 5; 0 0 0
0

```

Made possible with help from Dennis!
> 1 votes

# Answer
# Jelly, ~~5~~ 2 bytes

```
ÆḊ

```

Try it online!
> 1 votes

---
Tags: code-golf, math, linear-algebra
---


title: Tips for golfing in Jolf

text:
# Question
Title: Tips for golfing in Jolf
Jolf is a procedural golfing language made by @CᴏɴᴏʀO'Bʀɪᴇɴ.

What tips do you have for golfing in Jolf?

Please post one tip per answer.

These tips should be at least somewhat specific to Jolf, e.g. remove comments is an answer, but not a very good one.

# Answer
> 4 votes
# JavaScript fall back

If for some strange reason Jolf isn't golfy enough, or simply cannot cope, it may be of use to use JavaScript eval. This can happen in one of two ways.

## 1. Designed eval

Anything inside of `$...$` is literally carried over to the JS transpilation. For example, `+3$~$5` transpiles to `add(3, ~5)`. Equivalently, `+3:~5`.

## 2. Array eval

You can use JS arrays in Jolf! Mostly. It's kind of a bug, but I'm not going to fix it. For example:

```
u[3*5,5/6,(3+4)/5]

```

Transpiles to:

```
sum([2 * 3, 5 / 3, (3 + 4) / 5]);

```

# Answer
> 7 votes
# Know your auto-assigning variables!

Jolf has many ways to "auto assign" variables. The standard one is `γ`, which takes the value of the next expression. `Β` is the same thing, but converts the next expression to a number.

Also, `ζ` (zeta) is a variable initialized to `-1/12` (guess why), and can be re-assigned with `Ζ` (Zeta).

For example, let's say you want to compare `I` (the input string) to an operation over itself. For now, let's see if `I + I = reverse(I + I)`. This is written as, conventionally:

```
=+II_+II

```

But this can be golfed down to:

```
=γ+II_γ

```

# Answer
> 6 votes
# Use `@`

`@` is a command that takes the next character in the source code and returns that character's code point. (For example, `@X` returns 88.) This is often very useful since you can express any number between 0 and 255 in two bytes.

# Answer
> 4 votes
# Read the source

As of right now, there are a lot of undocumented things -- the mysterious `m` module among them, which has a lot of builtins. However, they do exist in the source, and it's really not hard to read once you get the hang of it, so read the source.

# Answer
> 3 votes
# Increase Function Arity

Every function has an arity. For example, `+` has an arity of 2. If you want to (say) add 5 elements, you *could* use 5 +s... *or* do `+θ12345`. Specifically:

* `θ` incrases the arity of the function by 3.
* increases the arity of the parent function by 3. (So `*+~θ345678` increases the arity of the `*` by 3)
* `M` increases the arity of the function by 2.
* `~M` increases the arity of the parent function by 2.
* `;` increases the arity of the function by 1.
* `~;` increases the arity of the parent function by 1.
* `η` decreases the arity of the function by 1.
* decreases the arity of the parent function by 1.
* `\xad` sets the arity of the parent function to the next character's charcode.

# Answer
> 2 votes
# Take advantage of implicit input

If a function does not have enough arguments, it will look to the input for the remainder of the arguments. For example:

```
+uz

```

Would transpile to:

```
add(sum(unaryRange(x)), x)

```

It's equivalent to

```
+uzxx

```

# Answer
> 1 votes
# Use `o` to store values

Similar to how other languages can assign variables for easy/short referencing, Jolf has `o`.

For example, `oThx` prints the input plus 1.

This is a useless example, but when the expression is more complicated than `hx`, it can save some serious byteage.

Also, `v"var name"<val>` allows for a multi-char variable name, and `V"var name"` gets a variable from the scope.

Thanks to Conor for explaining this to me, and giving the previous sentence.

---
Tags: code-golf, tips
---


title: Create a Boolean parser (continued)

text:
# Question
Title: Create a Boolean parser (continued)
Continuation of this challenge because the author is gone and the question is closed.

---

What you need to do is create a Boolean parser.

---

Boolean expressions, in case you haven't heard of them yet, have two inputs and one output.

There are four "gates" in boolean arithmetic, namely:

* OR (represented by `|`) (binary operator, between arguments)
* AND (represented by `&`) (binary operator, between arguments)
* XOR (represented by `^`) (binary operator, between arguments)
* NOT (represented by `!`) (unary operator, argument on right)

These gates operate on their inputs which are either true (represented by `1`) or false (represented by `0`). We can list the possible inputs (`A` and `B` in this case) and the outputs (`O`) using a truth table as follows:

```
XOR
A|B|O
-----
0|0|0
0|1|1
1|0|1
1|1|0

OR
A|B|O
-----
0|0|0
0|1|1
1|0|1
1|1|1

AND
A|B|O
-----
0|0|0
0|1|0
1|0|0
1|1|1

NOT
A|O
---
0|1
1|0

```

An example input would be `1^((1|0&0)^!(1&!0&1))`, which would evaluate to:

```
 1^((1|0&0)^!(1&!0&1))
=1^(( 1 &0)^!(1&!0&1))
=1^(   0   ^!(1&!0&1))
=1^(   0   ^!(1& 1&1))
=1^(   0   ^!(  1 &1))
=1^(   0   ^!    1   )
=1^(   0   ^    0    )
=1^0
=1

```

The output would be `1`.

### Details

* As seen in the example, there is no order of prevalence. All are evaluated from left to right, except when inside parentheses, which should be evaluated first.
* The input will only contain `()!^&|01`.
* You can choose any 8-byte character to replace the 8 characters above, but they must have a 1-to-1 mapping and must be stated.
* Specifically, the function `eval` is not allowed to be used on any string **derived from the input**. Specifically, the function `input` (or the equivalent in the language) and any function that calls it cannot be used by `eval`. You also cannot concatenate the `input` into your string inside the `eval`.

### Scoring

This is . Shortest solution in bytes wins.

# Answer
> 6 votes
# JavaScript (ES6) 116 bytes

**edit** thx @user81655 for 3 bytes saved and a bug found

```
s=>[...s].map(x=>x<2?v=m[x]:x<6?m=[,,m[1]+m[0],0+v,v+1,v+(1^v)][x]:x>6?v=o.pop()[v]:m=o.push(m)&&a,o=[v=a=m='01'])|v

```

Probably not the best approach, but no eval and no boolean operators, just truth tables.

Character used:

* ! -\> 2
* & -\> 3
* | -\> 4
* ^ -\> 5
* ( -\> 6
* ) -\> 7

**Test**

```
f=s=>[...s].map(x=>x<2?v=m[x]:x<6?m=[,,m[1]+m[0],0+v,v+1,v+(1^v)][x]:x>6?v=o.pop()[v]:m=o.push(m)&&a,o=[v=a=m='01'])|v

console.log=(...x)=>O.textContent+=x+'\n'

test=[ ["1^((1|0&0)^!(1&!0&1))",1]
// be more careful, step by step
,["0&0",0],["0&1",0],["1&0",0],["1&1",1]
,["0|0",0],["0|1",1],["1|0",1],["1|1",1]
,["0^0",0],["0^1",1],["1^0",1],["1^1",0]
,["0&!0",0],["0&!1",0],["1&!0",1],["1&!1",0]
,["0|!0",1],["0|!1",0],["1|!0",1],["1|!1",1]
,["0^!0",1],["0^!1",0],["1^!0",0],["1^!1",1]
,["!0&0",0],["!0&1",1],["!1&0",0],["!1&1",0]
,["!0|0",1],["!0|1",1],["!1|0",0],["!1|1",1]
,["!0^0",1],["!0^1",0],["!1^0",0],["!1^1",1]
// nand, nor
,["!(0&0)",1],["!(0&1)",1],["!(1&0)",1],["!(1&1)",0]
,["!(0|0)",1],["!(0|1)",0],["!(1|0)",0],["!(1|1)",0]
     ]

test.forEach(([x,check]) => {
  // remap operators (each one on its line, just to be clear)
  var t = x.replace(/!/g,"2")
  t = t.replace(/&/g,"3")
  t = t.replace(/\|/g,"4")
  t = t.replace(/\^/g,"5")
  t = t.replace(/\(/g,"6")
  t = t.replace(/\)/g,"7")
  r = f(t)
  console.log((r==check?'OK':'KO')+' '+x +' '+r)
})
```

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

# Answer
> 6 votes
# Retina, 49 bytes

```
+`(<1>|!0|1[ox]0|0[ox]1|1[ao]1)|<0>|!1|\d\w\d
$#1

```

I have no idea how did it come out so short.

Character mapping:

```
^ -> x
& -> a
| -> o
( -> <
) -> >

```

`1`, `0`, and `!` are left unchanged.

This works by replacing all truthy expressions (single `1` in parentheses, `!0`, `1&1`, `1^0`, `0|1`, etc.) with `1`, and all other (single `0` in parentheses, `!1`, `1&0`, `1^1`, `0|0`, etc.) with `0`.

Try it online!
Try it online with automatic character mapping!

# Answer
> 3 votes
# grep + shell utils, 131 bytes

```
rev|grep -cP '^(((0|R((?9)(x(?1)|a(?4))|(?2)([oxa](?4)|a(?1)|))L|(1|R(?1)L)!)(!!)*)[xo](?1)|(1|R(?1)L|(?2)!)([ao](?1)|[xo](?4)|))$'

```

The following chars are renamed:

```
( -> L
) -> R
| -> o
& -> a
^ -> x

```

I started trying to write a grep solution, but discovered that it did not work well with the left-associative infix operators. I needed to have a pattern like (chain of operators) = (chain of operators) (binary op) (single operand), but this contains a possible infinite recursion, so grep refuses to execute it. But I noticed that I *could* parse right-associative operators. This made the `!` operator a pain, but it was still possible. So I made a regex for calculating backwards boolean expressions, and sent the input through `rev`. The regex itself, which matches true expressions, is 116 bytes.

TODO: choose different characters for the input so that I can distinguish all the used groups of operators with built-in character classes.

# Answer
> 2 votes
# Python, 210 bytes

```
from operator import*;
def t(o):c=o.pop(0);return ord(c)-48if c in"01"else[p(o),o.pop(0)][0]if"("==c else 1-t(o)
def p(o):
 v=t(o)
 while o and")"!=o[0]:v=[xor,or_,and_]["^|&".index(o.pop(0))](v,t(o))
 return v

```

Really bad recursive descent, I expect this to be beaten in a heartbeat.

# Answer
> 2 votes
# Mathematica, ~~139~~ 129 bytes

```
a=StringPartition;StringReplace[#,{"(0)0&00&11&00|00^01^1"~a~3|"!1"->"0","(1)1&10|11|01|10^11^0"~a~3|"!0"->"1"},1]&~FixedPoint~#&

```

A simple string-replacement solution scores far better than I hoped for.

# Answer
> 2 votes
# JavaScript ES6, 223 bytes

```
x=>(Q=[],S=[],[...x].map(t=>{q=+t&&Q.push(t);if(t==")")while((a=S.pop())!="(")Q.push(a);else if(!q)S.push(t)}),k=[],p=_=>k.pop(),Q.concat(S.reverse()).map(e=>k.push(+e||e<"#"?1-p():e<"'"?p()&p():e<","?p()|p():p()^p())),p())

```

Uses a shunting yard algorithm.

```
x=>(Q=[],S=[],[...x].map(t=>{q=+t&&Q.push(t);if(t==")")while((a=S.pop())!="(")Q.push(a);else
if(!q)S.push(t)}),k=[],p=_=>k.pop(),Q.concat(S.reverse()).map(e=>k.push(+e||e<"#"?1-p():e<"'"
?p()&p():e<","?p()|p():p()^p())),p())

```

Uses `+` for OR, `!` for negation, `^` for XOR, and `&` for and. `0` and `1` are used for their respective values. Sure, I could golf some by making the operators numbers, but I'm not winning the JavaScript prize even if I do, so I thought I'd make it at least somewhat readable and correct.

# Answer
> 1 votes
# Java, 459 bytes

```
String p(String s){int x,y;while((y=s.indexOf("b"))>=0){x=s.lastIndexOf("a",y);s=s.replaceAll(s.subString(x,y+1),p(s.subString(x+1,y)));}String t,a="1",b="0";while(s.indexOf("!")>=0){s=s.replaceAll("!0",a);s=s.replaceAll("!1",b);}while(s.length()>1){t=s.subString(0,3);if(t.charAt(1)=='l')s=s.replaceFirst(t,t.equals("0l0")?b:a);else if(t.charAt(1)=='&')s=s.replaceFirst(t,t.equals("1&1")?a:b);else s=s.replaceFirst(t,t.charAt(0)==t.charAt(2)?b:a);}return s;}

```

`AND` is `&`

`OR` is `l`(lowercase L)

`XOR` is `x` (or any other character that happens to play nice with `String`'s methods such as `String.replaceAll(...)`)

`NOT` is `!`

`(` is `a`

`)` is `b`

here's a more readable version:

```
String parseBoolean( String str ) {
    int start,end;
    //look for matching brackets ab
    while( (end = str.indexOf( "b" )) >= 0 ) {
        start = str.lastIndexOf( "a", end );
        str = str.replaceAll( str.subString( start, end + 1 ), parseBoolean( str.subString( start + 1, end ) ) );
    }
    String temp, one = "1", zero = "0";
    //handle all the !'s
    while( str.indexOf( "!" ) >= 0 ) {
        str = str.replaceAll( "!0", one );
        str = str.replaceAll( "!1", zero );
    }
    //handle the remaining operators from left to right
    while( str.length() > 1 ){
        temp = str.subString( 0, 3 );
        //check for OR
        if( temp.charAt( 1 ) == 'l' )
            str = str.replaceFirst( temp, temp.equals( "0l0" ) ? zero : one );
        //check for AND
        else if(t.charAt(1)=='&')
            str = str.replaceFirst( temp, temp.equals( "1&1" ) ? one : zero );
        //handle XOR
        else
            str = str.replaceFirst( temp, temp.charAt( 0 ) == temp.charAt( 2 ) ? zero : one );
    }
    return str;
}

```

try it online

# Answer
> 1 votes
# C, 247

Golfed:

```
b(char*s){int i,j,k,l;if(*s==40){for(j=i=1;i+=s[++j]==41?-1:s[j]==40?1:0,i;);s[j++]=0;b(s+1);sprintf(s,"%s%s",s+1,s+j);}!s[1]?:(b(s+1),i=*s,j=1,k=s[1],i>47&i<50?:(s[1]=i==33?(j=0,k^1):(l=s[-1],i==38?k&l:i==94?k^l|'0':k|l),sprintf(s-j,"%s",s+1)));}

```

Ungolfed, with `main()` (takes expression as 1st arg). The golfed version has no debugging printfs and uses 2-digit ascii codes instead of char literals (`40 == '('`). I could have saved some characters by mapping `()|^&!` to `234567` \- this would have made many manipulations and tests easier after subtracting `48` from each.

```
char*z;                 // tracks recursion depth; not used in golfed version
b(char*s){
    int i,j,k,l;
    printf("%u> '%s'\n", s-z, s);
    if(*s=='('){        // handles parenthesis
        for(j=i=1;i+=s[++j]==')'?-1:s[j]=='('?1:0,i;);
        s[j++]=0;
        b(s+1);         // s+1 to s+j gets substituted for its evaluation
        sprintf(s,"%s%s",s+1,s+j);
    }
    !s[1]?:(            // if 1 char left, return
        b(s+1),         // evaluate rest of expression
        i=*s,
        j=1,
        k=s[1],
        printf("%u: '%c'\n", s-z, i),
        i>47&i<50?:(    // if 0 or 1, skip substitution
                        // otherwise, perform boolean operation
            s[1]=i=='!'?(j=0,k^1):(l=s[-1],i=='&'?k&l:i=='|'?k|l:k^l|'0'),
                        // and replace operation with result
            sprintf(s-j,"%s",s+1),printf("%u= '%s'\n", s-z, s-j)));
    printf("%u< '%s'\n", s-z, s);
}
int main(int argc, char **argv){
    char *s;
    sscanf(argv[1],"%ms",&s);
    z=s;
    b(s);
    printf("%s => %s\n", argv[1], s);
}

```

# Answer
> 1 votes
# Java, 218

Uses pattern-matching, but avoids the out-of-order replacements of my previous failed Java attempt (sharp eyes there, @Kenny Lau!).

Golfed:

```
String e(String s){Matcher m=Pattern.compile("(<1>|1o[01]|0o1|1a1|1x0|0x1|n0)|(<0>|0o0|0a[01]|1a0|1x1|0x0|n1)").matcher(s);return m.find()?e(s.substring(0,m.start())+(m.group(1)==null?"0":"1")+s.substring(m.end())):s;}

```

Ungolfed, reads input from arguments and applies the mapping `oaxn` for `|&^!` and `<>` for `()`:

```
import java.util.regex.*;

public class B{
    String e(String s){
        System.out.println(s);
        Matcher m=Pattern
            .compile(
                "(<1>|1o[01]|0o1|1a1|1x0|0x1|n0)|"+
                "(<0>|0o0|0a[01]|1a0|1x1|0x0|n1)")
            .matcher(s);
        return m.find()?e(s.substring(0,m.start())+(m.group(1)==null?"0":"1")+s.substring(m.end())):s;
    }

    public static String map(String s, String ... replacements) {
        for (String r: replacements) {
            s = s.replace(r.substring(0,1), r.substring(1));
        }
        return s;
    }

    public static void main(String ... args){
        for (String s: args) System.out.println(new B().e(
            map(s,"(<",")>","|o","&a","!n","^x")
        ));
    }
}

```

Java's `m.group(i)` tells you which group matched; the 1st group is for true substitutions and the 2nd one for false ones. This is iterated in strict left-to-right order until no substitutions are performed.

---
Tags: code-golf, parsing, logic-gates
---


title: Code Golf : Parsing google results

text:
# Question
Title: Code Golf : Parsing google results
When you search something on google, within the results page, the user can see green links, for the first page of results.

In the shortest form possible, in bytes, using any language, display those links to stdout in the form of a list. Here is an example, for the first results of the stack exchange query :

### Input :

you choose : the URL (`www.google.com/search?q=stackexchange&ie=utf-8&oe=utf-8`) or just `stackexchange`

### Output :

```
french.stackexchange.com/, stackoverflow.com/, fr.wikipedia.org/wiki/Stack_Exchange_Network, en.wikipedia.org/wiki/Stack_Exchange,...

```

### Rules :

* You may use URL shorteners or other search tools/APIs as long as the results would be the same as searching https://www.google.com.
* It's ok if your program has side effects like opening a web browser so the cryptic Google html/js pages can be read as they are rendered.
* You may use browser plugins, userscripts...
* If you can't use stdout, print it to the screen with, eg. a popup or javascript alert !
* You don't need the ending / or the starting http(s)://
* You should not show any other link
* Shortest code wins !
* Good luck !

EDIT : This golf ends the 07/08/15.

# Answer
> 17 votes
# Bash + grep + lynx, 38

Since we can open a web browser, then I will use `lynx`:

```
lynx -dump $1|grep -Po '(?<=d:)[^&]+'

```

(Thanks to @manatwork for `grep` usage instead of `sed`)

We pass in the whole URL in as a parameter:

```
$ ./gr.sh "www.google.com/search?q=stackexchange&ie=utf-8&oe=utf-8"
http://stackexchange.com/
https://en.wikipedia.org/wiki/Stack_Exchange
https://twitter.com/stackexchange
https://play.google.com/store/apps/details?id=com.stackexchange.marvin
https://github.com/StackExchange/StackExchange.Redis
https://github.com/StackExchange/StackExchange.Redis/blob/master/Docs/Basics.md
https://www.crunchbase.com/organization/stack-exchange
$

```

Which gives the same list as:

# Answer
> 4 votes
# Ruby, ~~91~~ 77 bytes

```
require'open-uri';open(gets).read.scan(/ed:(.*?)\+/){|x|puts URI.decode x[0]}

```

~~Would've been shorter without all the `require`s. ARGH!!!~~ **EDIT**: So, turns out, I *don't* need the second require! Thanks to @manatwork for pointing that out.

Older version (with the useless `require`):

```
require'open-uri';require 'uri';open(gets).read.scan(/ed:(.*?)\+/){|x|puts URI.decode x[0]}

```

# Answer
> 4 votes
**Wolfram Language (Mathematica), 135**

```
StringJoin/@(Cases[URLExecute["www.google.com/search",{"q"->#},"XMLObject"],XMLElement["cite",_,l_]:>l,-1]/.XMLElement["b",_,{s_}]:>s)&

```

more readable:

```
StringJoin/@(Cases[
    URLExecute["www.google.com/search",{"q"->#},"XMLObject"],
    XMLElement["cite",_,l_]:>l,-1] /.
    XMLElement["b",_,{s_}]:>s)

```

# Answer
> 3 votes
# Python 3, 141 bytes

Nowhere near Digital Trauma's answer, but it was fun to work out the regex :D

```
import re
print('\n'.join(map(lambda x:x[3:],re.findall('te>http[s]?://\w+\.[a-z]+[](/a-z\.)?]+',__import__("requests").get(input()).text))))

```

For input `http://www.google.com/search?q=stackexchange&ie=utf-8&oe=utf-8` the program outputs:

```
https://en.wikipedia.org/wiki/
https://twitter.com/
https://play.google.com/store/apps/details?id...
https://www.crunchbase.com/organization/
https://www.facebook.com/
https://github.com/

```

Implements grc's tip

# Answer
> 3 votes
# Factor, 31 bytes

There happens to be a library for this.

```
[ google-search [ url>> ] map ]

```

---
Tags: code-golf, parsing, internet
---


# Question
Title: Permutations with Indistinguishable Items
Given a list of integers, output the number of permutations of the integers, with indistinguishable permutations counted once. If there are `n` integers, and each group of indistinguishable numbers has length `n_i`, this is `n! / (n_1! * n_2! * ...)`

## Rules

* Input will be some form of list as arguments to a function or the program with 1 to 12 non-negative integers.
* Output will be printing or returning the number of permutations as described above.
* No standard loopholes or built-in functions (generating permutations, combinations, etc.). Factorials are allowed.

## Test Cases

**Inputs:**

```
1, 3000, 2, 2, 8
1, 1, 1
2, 4, 3, 2, 3, 4, 4, 4, 4, 4, 1, 1

```

**Outputs:**

```
60
1
83160

```

# Answer
## Python, 48 bytes

```
f=lambda l:l==[]or len(l)*f(l[1:])/l.count(l[0])

```

A recursive implementation.

In the formula, `n! / (n_1! * n_2! * ...)`, if we remove the first element (say it's `1`), the number of permutation for the remaining `n-1` elements is

```
(n-1)! / ((n_1-1)! * n_2! * ...) ==
n! / n / (n_1! / n_1! * n_2! * ...) ==
n/n_1 * (n! / (n_1! * n_2! * ...)`)

```

So, we get the answer by multiplying by `n/n1`, the reciprocal-fraction of elements that equal the first one, by the recursive result for the rest of the list. The empty list gives the base case of 1.
> 6 votes

# Answer
# MATL, ~~14~~ ~~13~~ 12 bytes

```
fpGu"@G=s:p/

```

**Try it online!**

### Explanation

The approach is very similar to that in @Adnan's answer.

```
f       % Take input implicitly. Push array of indices of nonzero entries.
        % This gives [1 2 ... n] where n is input length.
p       % Product (compute factorial)
Gu      % Push input. Array of its unique elements
"       % For each of those unique values
  @     %   Push unique value of current iteration
  G=s   %   Number of times (s) it's present (=) in the input (G)
  :p    %   Range, product (compute factorial)
  /     %   Divide
        % End for each implicitly. Display implicitly

```
> 4 votes

# Answer
# 05AB1E, ~~15~~ ~~14~~ 13 bytes

Code:

```
D©g!rÙv®yQO!/

```

Explanation:

```
               # implicit input
D©             # duplicate and save a copy to register
  g!           # factorial of input length (total nr of permutations without duplicates)
    rÙv        # for each unique number in input
       ®yQO!   # factorial of number of occurances in input
            /  # divide total nr of permutations by this
               # implicit output

```

Uses **CP-1252** encoding.

Try it online!.
> 3 votes

# Answer
## JavaScript (ES6), ~~64~~ 61 bytes

```
a=>a.sort().map((x,i)=>r=r*++i/(x-y?(y=x,c=1):++c),y=r=-1)|-r

```

Uses the formula given, except calculating each factorial incrementally (so for example the `r=r*++i` effectively calcluates `n!`).

Edit: Originally I accepted any finite numbers but I saved 3 bytes when @user81655 pointed out that I only needed to support positive integers (although I actually accept non-negative integers).
> 2 votes

# Answer
# Pyth, 11 bytes

```
/.!lQ*F/V._

```

Test suite

Uses the standard formula, `n! / (count1! * count2! * ...)`, except that the factorials of the counts are found by counting how many times each element occurs in the prefix leading up to that, then multiplying all such numbers together.

Explanation:

```
/.!lQ*F/V._
/.!lQ*F/V._QQ    Implicit variable introduction.
                 Q = eval(input())
         ._Q     Form all prefixes of the input.
       /V   Q    Count how many times each element occurs in the prefix
                 ending with that element.
     *F          Fold on multiplication - take the product.
 .!lQ            Take the factorial of the input length
/                Divide.

```
> 2 votes

# Answer
# Pyth - ~~14~~ 12 bytes

```
/F.!M+lQ/LQ{

```

Test Suite.
> 1 votes

# Answer
# Ruby, ~~75~~ 74 bytes

Kinda wish that Ruby's `Math` module had a factorial function so I didn't have to build my own.

```
->l{f=->x{x<2?1:x*f[x-1]};l.uniq.map{|e|f[l.count e]}.inject f[l.size],:/}

```
> 1 votes

# Answer
## CJam, 17 bytes

```
q~_,\$e`0f=+:m!:/

```

Test it here.

### Explanation

```
q~   e# Read input and evaluate.
_,   e# Duplicate and get length.
\$   e# Swap with other copy and sort it.
e`   e# Run-length encode. Since the list is sorted, this tallies the numbers.
0f=  e# Select the tally of each number.
+    e# Prepend the length of the input.
:m!  e# Compute the factorial of each number in the list.
:/   e# Fold division over it, which divides each factorial of a tally into
     e# the factorial of the length.

```
> 1 votes

# Answer
# J, 13 bytes

```
#(%*/)&:!#/.~

```

## Usage

```
   f =: #(%*/)&:!#/.~
   f 1 3000 2 2 8
60
   f 1 1 1
1
   f 2 4 3 2 3 4 4 4 4 4 1 1
83160

```

## Explanation

```
#(%*/)&:!#/.~  Input: A
         #/.~  Partition A by equal values and get the size of each, these are the tallies
#              Get the size of A
      &:!      Take the factorial of both the size and the tallies
   */          Reduce using multiplication the factorial of the tallies
  %            Divide the factorial of the size by that product and return

```
> 1 votes

# Answer
# Jelly, 8 bytes

```
W;ĠL€!:/

```

Try it online!

```
W;ĠL€!:/ example input:             [1, 3000, 2, 2, 8]
W        wrap:                      [[1, 3000, 2, 2, 8]]
  Ġ      group index by appearance: [[1], [3, 4], [5], [2]]
 ;       concatenate:               [[1, 3000, 2, 2, 8], [1], [3, 4], [5], [2]]
   L€    map by length:             [5, 1, 2, 1, 1]
     !   [map by] factorial:        [120, 1, 2, 1, 1]
      :/ reduce by division:        120÷1÷2÷1÷1 = 60

```
> 1 votes

---
Tags: code-golf, math, combinatorics, counting, permutations
---


# Question
Title: One-to-one correspondence between pairs of integers and the positive integers
It is well-known that there are one-to-one correspondences between pairs of integers and the positive integers. Your task is to write code defining such a correspondence (by defining a pair of functions/programs that are inverses of each other) in your programming language of choice, plus a correctness check (see below) with the smallest number of bytes for the correspondence definition (not taking the correctness check into account).

The solution must include :

* the definition of a function/program f having two integer arguments and returning an integer (that's one direction of the bijection).
* either the definition of a function/program g having one integer argument and returning a pair of integers (might be an array, a list, the concatenation of the two integers separated by something ...) or two functions/programs a and b having an integer argument and returning an integer (that's the other direction).
* an additional code snippet checking that for the f and g (or f and a,b) you defined above, you have g(f(x,y))=(x,y) (or a(f(x,y))=x and b(f(x,y))=y) for any integers x,y in the range -100 \< x \< 100,-100 \< y \< 100. Note that f and g have to work for values outside of this range as well.

You may rename a,b,f or g of course. The two solutions do not have to be written in the same language.

Below is a not-optimal-at-all solution in PARI/GP, with 597 characters for the function definitions.

```
plane_to_line(x,y)={
my(ax,ay,z);
ax=abs(x);
ay=abs(y);
if((ax<=ay)*(y<0),        z=4*y*y-2*y+x+2;);
if((ax<=ay)*(y>=0),       z=4*y*y-2*y-x+2;);
if((ay<=ax)*(x<0),        z=4*x*x    -y+2;);
if((ay<=ax)*(x>=0)*(y<0), z=4*x*x+4*x+y+2;);
if((ay<=ax)*(x>=0)*(y>=0),z=4*x*x-4*x+y+2;);
if((x==0)*(y==0),z=1;);
return(z);
}

line_to_plane(z)={
my(l,d,x,y);
l=floor((1+sqrt(z-1))/2);
d=z-(4*l*l-4*l+2);
if(d<=l,x=l;y=d;);
if((l<d)*(d<=3*l),x=2*l-d;y=l;);
if((3*l<d)*(d<=5*l),x=(-l);y=4*l-d;);
if((5*l<d)*(d<=7*l),x=d-6*l;y=(-l););
if((7*l<d)*(d<8*l) ,x=l;y=d-8*l;);
if(z==1,x=0;y=0;);
return([x,y]);
}

```

and the correctness-check code :

```
accu=List([])
m=100;
for(x=-m,m,for(y=-m,m,if(line_to_plane(plane_to_line(x,y))!=[x,y],\
listput(accu,[x,y]);)))
Vec(accu)

```

# Answer
# MATL, ~~43~~ 36 bytes

This uses the `spiral` (`1YL`) function, which generates a square 2D array of given size with values arranged in an outward spiral. For example, with input `7` it produces

```
43 44 45 46 47 48 49
42 21 22 23 24 25 26
41 20  7  8  9 10 27
40 19  6  1  2 11 28
39 18  5  4  3 12 29
38 17 16 15 14 13 30
37 36 35 34 33 32 31

```

The center of the array, which contains `1`, corresponds to the tuple `[0 0]`. The upper left corner corresponds to `[-3 -3]` etc. So for example *f* (-3,-3) will be 43 and *g* (43) will be \[-3 -3\].

The code generates a 2D array with this spiral matrix, as large as needed to do the conversion. Note that larger sizes always give the same result for the entries already included in smaller sizes.

### From **Z**2 to **N** (18 bytes):

```
|X>tEQ1YLGb+QZ}3$)

```

Try it online!

```
|X>   % input is a 2-tuple. Take maximum of absolute values
tEQ   % duplicate. Multiply by 2 and increase by 1. This gives necessary size of spiral
1YL   % generate spiral
G     % push input 2-tuple again
b+Q   % bubble up, add, increase by 1. This makes the center correspont to [0 0]
Z}    % split tuple into its values
3$)   % use those two value as indices into the spiral array to obtain result

```

### From **N** to **Z**2 (~~25~~ 18 bytes)

```
Eqt1YLG=2#fhw2/k-q

```

Try it online!

```
Eq      % input is a number. Multiply by 2, add 1. This assures size is enough and odd
t1YL    % duplicate. Generate spiral of that size
G=      % compare each entry with the input value
2#fh    % 2-tuple of row and column indices of matching entry
w2/k-q  % swap. Offset values so that center corresponds to [0 0]

```

### Snippet for checking

Note that `G` needs to be modified to accomodate the fact that we have don't have a single input. The code is slow, so the link checks tuples with values from -9 to 9 only. For -99 to 99 just replace the first line.

The code tests each tuple with values in the defined range. It does the conversion to a number, then from that number back to a tuple, and then checks if the original and recovered tuple are equal. The results should all be `1`, indicating that all comparisons give `true`.

It takes a while to run.

Try it online!

```
-9:9                     % Or use -99:99. But it takes long
HZ^!"@                   % Cartesian power: gives tuples [-9 -9] ... [9 9].
                         % For each such tuple
|X>tEQ1YL@b+QZ}3$)       % Code from Z^2 to N with `G` replaced by `@` (current tuple)
XJ                       % Copy result into clipboard J
Eqt1YLJ=2#fhw2/k-q       % Code from N to Z^2 with `G` replaced by `J`
@!X=                     % Compare original tuple with recovered tuple: are they equal?

```
> 7 votes

# Answer
## JavaScript (ES6), 171 bytes

```
(x,y)=>(h=x=>parseInt((x^x>>31).toString(2)+(x>>>31),4),h(x)*2+h(y))
x=>(h=x=>parseInt(x.toString(2).replace(/.(?!(..)*$)/g,''),2),i=x=>x<<31>>31^x>>>1,[i(h(x>>>1)),i(h(x))])

```

Bit twiddling: negative numbers have their bits flipped; each integer is then doubled, and 1 added if it was originally negative; the bits from the integers are then interleaved. The reverse operation deletes alternate bits, divides by 2, and flips all the bits if the value was negative. I could save 3 bytes by limiting myself to 15-bit values instead of 16-bit values.

```
f=(x,y)=>(h=x=>parseInt((x^x>>31).toString(2)+(x>>>31),4),h(x)*2+h(y))
g=x=>(h=x=>parseInt(x.toString(2).replace(/.(?!(..)*$)/g,''),2),i=x=>x<<31>>31^x>>>1,[i(h(x>>>1)),i(h(x))])
for(i=-100;i<=100;i++)for(j=-100;j<100;j++)if(g(f(i,j))[0]!=i||g(f(i,j))[1]!=j)alert([i,j])
```
> 4 votes

# Answer
# Jelly, ~~50~~ ~~48~~ ~~46~~ ~~45~~ ~~43~~ ~~40~~ 39 bytes

## Plane to line (~~18~~ ~~17~~ 16 bytes):

```
AḤ_<0$
+RS+
,Ñç/

```

Try it online!

## Line to plane (~~32~~ ~~30~~ ~~29~~ ~~27~~ ~~24~~ 23 bytes):

```
HĊN⁸¡
³R‘R’U⁹¡F³ịÇ
ç1,¢

```

Try it online!

## Explanation:

I'll only explain `plane to line`, because `line to plane` is just its opposite.

Firstly, we convert each integer to a natural number, by the function `f(x) = 2*|x| - (x<0)`.

Then, we convert the two natural numbers to another two natural numbers, by the function `g(x,y) = (x+y,y)`.

Finally, we convert them into one natural number, by the function `h(x,y) = (x+1)C2 + y`
> 3 votes

---
Tags: code-golf, number, arithmetic, grid, open-ended-function
---


title: Negative base conversion

text:
# Question
Title: Negative base conversion
We already have a base conversion question, but not one with negative bases (nope, this doesn't count).

(Corresponding wiki article.)

You will receive a number (may be negative) and a base (must be negative), and your task is to convert the number into the base.

The base will only be from `-10` to `-2`.

### Specs

* You may receive the number in any positive base, including unary.
* You may choose receive the magnitude of the base instead (`10` instead of `-10`).
* The input can be taken in any reasonable format.

### Scoring

This is , shortest solution in bytes wins.

### Testcases

```
input        output
8163, -10    12243
-8163, -10   9977
17, -3       212

```

# Answer
> 0 votes
## Jelly, 1 byte

```
b

```

Jelly supports negative bases with its base conversion builtin.

Try it online!

(`bV` at two bytes if the output must be a single integer.)

---
Tags: code-golf, base-conversion
---


# Question
Title: Taylor Series of a Function with Periodic Derivatives
Taylor series are a very useful tool in calculating values of analytic functions that cannot be expressed in terms of elementary functions, using only information about that function at a single point.

In this challenge, you won't be actually doing any math with them, but merely making string representations of taylor series of functions with periodic derivatives.

# Specs

You will takes a input three things:

1. A cycle of the derivatives of the function, including the original function as a list of strings, e.g. `["sin(x)", "cos(x)", "-sin(x)", "-cos(x)"]`.
2. A number `a`, the point around which to center the approximation.
3. A positive integer `n`, the number of terms of the series to output.

The general form for the nth term of a taylor series is:

```
f^(n)(a)/n!*(x-a)^n

```

where `f^(n)` is the nth derivative of `f`. Here is the taylor series of `f` in a better formatted image from wikipedia:

.

The above example with `sin(x)`, and `a` of 1, and `n` of 6, would have an output of:

```
sin(1) + cos(1)*(x-1) - sin(1)/2*(x-1)^2 - cos(1)/6*(x-1)^3 + sin(1)/24*(x-1)^4 + cos(1)/120*(x-1)^5

```

You can do the whitespace want. However, you have to replace `+ -` and `- -` with `-` and `+` respectively. Also, if the series is a maclaurin series, and `a` is `0`, you cannot have `(x-0)`. `(x)` and just `x` is fine, but not `(x-0)`. Niether can you have `^0` nor `^1` nor `/1` . Additionally, you must expand out the factorials in the denominators. Multiplication by juxtaposition is not allowed.

# Test cases

```
["e^x"], 0, 4  ->  e^0 + e^0*x + e^0*x^2/2 + e^0*x^3/6
["sin(x)", "cos(x)", "-sin(x)", "-cos(x)"], 1, 6 -> sin(1) + cos(1)*(x-1) - sin(1)/2*(x-1)^2 - cos(1)/6*(x-1)^3 + sin(1)/24*(x-1)^4 + cos(1)/120*(x-1)^5
["e^(i*x)", "i * e^(i*x)", "-e^(i*x)", "-i*e^(i*x)"], 0, 7 -> e^(i*0) + i*e^(i*0)*x - e^(i*0)*x^2/2 - i*e^(i*0)*x^3/6 + e^(i*0)*x^4/24 + i*e^(i*0)*x^5/120 - e^(i*0)*x^6/720

```

This is , so shortest code in **bytes** wins!

# Answer
## JavaScript (ES6), 183 bytes

```
(c,a,n)=>[...Array(n)].map((_,i)=>(s=c[i%c.length].replace(/x/g,a),i?s=s.replace(/^-?/,c=>c?` - `:` + `)+(a>0?`*(x-${a})`:a<0?`*(x+${-a})`:`*x`):s,i>1?s+`^${i}/${f*=i}`:s),f=1).join``

```

Lots of tedious string manipulation. Explanation:

```
(c,a,n)=>                               Parameters
 [...Array(n)].map((_,i)=>(             Loop i from 0 to n-1
  s=c[i%c.length]                       Get the right element from the cycle
   .replace(/x/g,a),                    Substitute a in for x
  i?                                    If i > 0
   s=s.replace(/^-?/,c=>c?` - `:` + `)  Turn the sign into an operator
    +(a>0?`*(x-${a})`                   If a > 0 then * (x - a)
     :a<0?`*(x+${-a})`                  If a < 0 then * (x + -a)
     :`*x`)                             If a == 0 then * x
   :s,                                  No change if i < 1
  i>1?                                  If i > 1
   s+`^${i}/${f*=i}`                    Append ^ i / i!
   :s),                                 No change if i < 2
  f=1                                   0! == 1
 ).join``                               Join all the results together

```

170 bytes if you remove all the whitespace:

```
(c,a,n)=>[...Array(n)].map((_,i)=>(s=c[i%c.length].replace(/x/g,a),i?s=(s[0]=='-'?'':'+')+s+(a>0?`*(x-${a})`:a<0?`*(x+${-a})`:`*x`):s,i>1?s+`^${i}/${f*=i}`:s),f=1).join``

```
> 1 votes

# Answer
# Python 2, 181 bytes

```
D,a,N=input()
D=["+"*(d[0]!="-")+d.replace("x",`a`)for d in D]
x=a and"*(x-%s)"%a or"*x"
r=D[0][1:]+(D[1]+x)*(N>1)
n=f=2
while n<N:r+=D[n%len(D)]+"/"+`f`+x+"^"+`n`;n+=1;f*=n
print r

```
> 0 votes

# Answer
# Python 3.5, 308 299 bytes:

```
def g(f,a,n,L=len,S=str):import math,re;A=S(a);print('+'.join(t.replace('x',A)+re.sub('(\W\(x-\d+\)\^0|/1|\*1|\^1|\*0)(?!\d+)','',g)for t,g in zip(f*(n//L(f))+f[:n%L(f)],['*'+A+'/'+S(math.factorial(n))+'*'+'(x-'+A+')^'+S(n)for n in range(n)])).replace('+-','-').replace('--','+').replace('x-0','x'))

```

This *always* outputs in the order according to the equation `f^(n)(a)/n!*(x-a)^n`. For instance, if the expected output for one of the terms is `e^0*x^2/2`, it instead outputs `e^0/2*x^2`. However, they are both basically the same answer, so I hope this is okay. Confirmed by OP that this is okay. This works perfectly as I have had no issues with it. I will shorten this over time wherever I can.

**Note:** In the output, all `(x-0)` are replaced with `(x)`.

Try it online! (Ideone) (Accepts input on 3 lines, where the first line is the input list, `f`, the second line is `a`, and the third line is `n`)

# Explanation

For the purposes of this explanation, assume the function is executed with the values `"e^(i*x)", "i*e^(i*x)", "-e^(i*x)", "-i*e^(i*x)"],0,7`. That being said, basically, what's going on in the main part, step-by-step, is:

1. `'+'.join(t.replace('x',A)+re.sub('(\W\(x-\d+\)\^0|/1|\*1|\^1|\*0)(?!\d+)','',g)for t,g in zip(f*(n//L(f))+f[:n%L(f)],['*'+A+'/'+S(math.factorial(n))+'*'+'(x-'+A+')^'+S(n)for n in range(n)]))`

A list is created from each item pair in a zip object containing the input list, `f`, with `n` number of items, and another list which contains each term in the sequence *except* the items in `f`. In this second list, `*+a` is added, followed by a `/`\+ `n!` for each value, `n`, in the range `n`, and finally, a lone `*` followed by `(x-a)^n`. After all this is done, for each item pair in this zip object, `t` corresponding to each object in `f` and `g` corresponding to each value in the second list, each `'x'` in `t` is replaced with `a`, and every `g` goes through a regular expression substitution, namely `(\W\(x-\d+\)\^0|/1|\*1|\^1|\*0)(?!\d+)`, in which every `(x-a)^0`, `/1`,`*1`,`^1`, and `*0` is matched and replaced with `''` as long as each of those are *not* followed by any more integers. After all this substitution is done, each `t` and `g` are concatenated together, and each term created using this method is joined with `+`s and returned. For this particular case in which `"e^(i*x)", "i*e^(i*x)", "-e^(i*x)", "-i*e^(i*x)"],0,7` is the input, this part would return:

```
e^(i*0)+i*e^(i*0)*(x-0)+-e^(i*0)/2*(x-0)^2+-i*e^(i*0)/6*(x-0)^3+e^(i*0)/24*(x-0)^4+i*e^(i*0)/120*(x-0)^5+-e^(i*0)/720*(x-0)^6

```

As you can see, those `+-`s, `--`s, and `(x-0)`s exist. However, these will all be replaced with `-`,`+`,and `(x)` respectively in the next part.
2. `'+'.join(t.replace('x',A)+re.sub('(\W\(x-\d+\)\^0|/1|\*1|\^1|\*0)(?!\d+)','',g)for t,g in zip(f*(n//L(f))+f[:n%L(f)],['*'+A+'/'+S(math.factorial(n))+'*'+'(x-'+A+')^'+S(n)for n in range(n)])).replace('+-','-').replace('--','+').replace('x-0','x')`

Here is where those substrings such as `+-`,`++`,and `(x-0)` in the now joined string are replaced with their correct substitutes using Python's built-in sub-string replacement function. After all the replacing has been done, this finally returns the finished product, which in this case would be:

```
e^(i*0)+i*e^(i*0)*(x)-e^(i*0)/2*(x)^2-i*e^(i*0)/6*(x)^3+e^(i*0)/24*(x)^4+i*e^(i*0)/120*(x)^5-e^(i*0)/720*(x)^6

```
> 0 votes

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


title: Kolmogorov complexity Chad Gadya

text:
# Question
Title: Kolmogorov complexity Chad Gadya
**EDIT** It is not clear how answers to the question of compressing a long text, without cumulative properties are relevant to golfing a short cumulative strong, any more than general Lempel Ziv techniques are relevant to code-golfing. Take note that the complexity of 99 bottles of beer is not O(Sqrt(n))

Knuth suggested the notion of theoretical complexity of songs (Knuth, Donald E. "The complexity of songs." Communications of the ACM 27.4 (1984): 344-346.), noting that most cumulative songs are O(sqrt(n)).

Cumulative songs never showed up in PPCG. The challenge this time is Chad Gadya, a famous cumulative song in Aramaic and Hebrew, sung in cumulation of the seder. The lyrics can be found, e.g., here (blue text). (There are slight variations, so use this one, copied below).

To state the obvious, Chad Gadya belongs in the complexity class of the famous "Läuschen und Flöhchen" tale by the Grimm brothers, and some other more or less famous English songs, i.e., O(sqrt n).

The challenge is to write a program, in any programming language, that produces the song, each verse in its own line. The program takes no input, and cannot cheat by using, e.g., `wget`. A greater challenge is to make the solution so small that it can fit in a twitter message. (I bet no one here would be able to meet this challenge)

A short such program could be useful for twitter/sms holiday greetings. Please minimize the number of bytes (not characters). Output should be in UTF8.

**Why is this interesting?**

* Knuth paper on the the complexity of cumulative songs
* Song is *very* short; standard tricks would not help.
* Space savings in Niqqud is an extra challenge.
* Repetitions are not only due to the cumulative nature of the song.
* The twitter objective seems impossible.
* The song itself is quite short, much shorter than other songs that have been posted here. Compression of short text is more challenging than that of long text.

**Output**

```
חַד גַּדְיָא, חַד גַּדְיָא דִּזְבַן אַבָּא בִּתְרֵי זוּזֵי. חַד גַּדְיָא, חַד גַּדְיָא
וַאֲתָא שׁוּנְרָא, וְאָכְלָה לְגַדְיָא, דִּזְבַן אַבָּא בִּתְרֵי זוּזֵי. חַד גַּדְיָא, חַד גַּדְיָא
וַאֲתָא כַלְבָּא, וְנָשַׁךְ לְשׁוּנְרָא, דְּאָכְלָה לְגַדְיָא, דִּזְבַן אַבָּא בִּתְרֵי זוּזֵי. חַד גַּדְיָא, חַד גַּדְיָא
וַאֲתָא חוּטְרָא, וְהִכָּה לְכַלְבָּא, דְּנָשַׁךְ לְשׁוּנְרָא, דְּאָכְלָה לְגַדְיָא, דִּזְבַן אַבָּא בִּתְרֵי זוּזֵי. חַד גַּדְיָא, חַד גַּדְיָא
וַאֲתָא נוּרָא, וְשָׂרַף לְחוּטְרָא, דְּהִכָּה לְכַלְבָּא, דְּנָשַׁךְ לְשׁוּנְרָא, דְּאָכְלָה לְגַדְיָא, דִּזְבַן אַבָּא בִּתְרֵי זוּזֵי. חַד גַּדְיָא, חַד גַּדְיָא
וַאֲתָא מַיָּא, וְכָבָה לְנוּרָא, דְּשָׂרַף לְחוּטְרָא, דְּהִכָּה לְכַלְבָּא, דְּנָשַׁךְ לְשׁוּנְרָא, דְּאָכְלָה לְגַדְיָא, דִּזְבַן אַבָּא בִּתְרֵי זוּזֵי. חַד גַּדְיָא, חַד גַּדְיָא
וַאֲתָא תוֹרָא, וְשָׁתָה לְמַיָּא, דְּכָבָה לְנוּרָא, דְּשָׂרַף לְחוּטְרָא, דְּהִכָּה לְכַלְבָּא, דְּנָשַׁךְ לְשׁוּנְרָא, דְּאָכְלָה לְגַדְיָא, דִּזְבַן אַבָּא בִּתְרֵי זוּזֵי. חַד גַּדְיָא, חַד גַּדְיָא
וַאֲתָא הַשּׁוֹחֵט, וְשָׁחַט לְתוֹרָא, דְּשָׁתָה לְמַיָּא, דְּכָבָה לְנוּרָא, דְּשָׂרַף לְחוּטְרָא, דְּהִכָּה לְכַלְבָּא, דְּנָשַׁךְ לְשׁוּנְרָא, דְּאָכְלָה לְגַדְיָא, דִּזְבַן אַבָּא בִּתְרֵי זוּזֵי. חַד גַּדְיָא, חַד גַּדְיָא
וַאֲתָא מַלְאַךְ הַמָּוֶת, וְשָׁחַט לְשׁוֹחֵט, דְּשָׁחַט לְתוֹרָא, דְּשָׁתָה לְמַיָּא, דְּכָבָה לְנוּרָא, דְּשָׂרַף לְחוּטְרָא, דְּהִכָּה לְכַלְבָּא, דְּנָשַׁךְ לְשׁוּנְרָא, דְּאָכְלָה לְגַדְיָא, דִּזְבַן אַבָּא בִּתְרֵי זוּזֵי. חַד גַּדְיָא, חַד גַּדְיָא
וַאֲתָא הַקָּדוֹשׁ בָּרוּךְ הוּא, וְשָׁחַט לְמַלְאַךְ הַמָּוֶת, דְּשָׁחַט לְשׁוֹחֵט, דְּשָׁחַט לְתוֹרָא, דְּשָׁתָה לְמַיָּא, דְּכָבָה לְנוּרָא, דְּשָׂרַף לְחוּטְרָא, דְּהִכָּה לְכַלְבָּא, דְּנָשַׁךְ לְשׁוּנְרָא, דְּאָכְלָה לְגַדְיָא, דִּזְבַן אַבָּא בִּתְרֵי זוּזֵי. חַד גַּדְיָא, חַד גַּדְיָא

```

If you find it hard to deal with Hebrew and Aramaic (tough luck...), try first getting your hands dirty with Läuschen und Flöhchen, and then proceed to the real challenge.

A related, but different question is that of "99 Bottles of Beer". If you care about complexity, you would notice that the theoretical complexity of bottles of beers is different from that of the two farthing kid.

# Answer
# Python 2, ~~633 603 589~~ 584 bytes (384 chars)

Note: the file must begin with a 3-byte “UTF-8 BOM” (EF BB BF), which Stack Exchange does not seem to preserve.

```
v="נָשַׁךְ הִכָּה שָׂרַף כָבָה שָׁתָה".split()+["שָׁחַט"]*4
c=', '.join(["חַד גַּדְיָא"]*2)
b=" דִּזְבַן אַבָּא בִּתְרֵי זוּזֵי. "+c
print c+b
e='אָכְלָה לְגַדְיָא,'+b
for i,t in enumerate("שׁוּנְרָא|כַלְבָּא|חוּטְרָא|נוּרָא|מַיָּא|תוֹרָא|שׁוֹחֵט|מַלְאַךְ הַמָּוֶת|הַקָּדוֹשׁ בָּרוּךְ הוּא".split('|')):
 print'וַאֲתָא '+(t if i!=7else'הַשּׁ'+t[4:])+' וְ'+e
 e=v[i]+' לְ'+t+', דְּ'+e

```

Output:

```
חַד גַּדְיָא, חַד גַּדְיָא דִּזְבַן אַבָּא בִּתְרֵי זוּזֵי. חַד גַּדְיָא, חַד גַּדְיָא
וַאֲתָא שׁוּנְרָא וְאָכְלָה לְגַדְיָא, דִּזְבַן אַבָּא בִּתְרֵי זוּזֵי. חַד גַּדְיָא, חַד גַּדְיָא
וַאֲתָא כַלְבָּא וְנָשַׁךְ לְשׁוּנְרָא, דְּאָכְלָה לְגַדְיָא, דִּזְבַן אַבָּא בִּתְרֵי זוּזֵי. חַד גַּדְיָא, חַד גַּדְיָא
וַאֲתָא חוּטְרָא וְהִכָּה לְכַלְבָּא, דְּנָשַׁךְ לְשׁוּנְרָא, דְּאָכְלָה לְגַדְיָא, דִּזְבַן אַבָּא בִּתְרֵי זוּזֵי. חַד גַּדְיָא, חַד גַּדְיָא
וַאֲתָא נוּרָא וְשָׂרַף לְחוּטְרָא, דְּהִכָּה לְכַלְבָּא, דְּנָשַׁךְ לְשׁוּנְרָא, דְּאָכְלָה לְגַדְיָא, דִּזְבַן אַבָּא בִּתְרֵי זוּזֵי. חַד גַּדְיָא, חַד גַּדְיָא
וַאֲתָא מַיָּא וְכָבָה לְנוּרָא, דְּשָׂרַף לְחוּטְרָא, דְּהִכָּה לְכַלְבָּא, דְּנָשַׁךְ לְשׁוּנְרָא, דְּאָכְלָה לְגַדְיָא, דִּזְבַן אַבָּא בִּתְרֵי זוּזֵי. חַד גַּדְיָא, חַד גַּדְיָא
וַאֲתָא תוֹרָא וְשָׁתָה לְמַיָּא, דְּכָבָה לְנוּרָא, דְּשָׂרַף לְחוּטְרָא, דְּהִכָּה לְכַלְבָּא, דְּנָשַׁךְ לְשׁוּנְרָא, דְּאָכְלָה לְגַדְיָא, דִּזְבַן אַבָּא בִּתְרֵי זוּזֵי. חַד גַּדְיָא, חַד גַּדְיָא
וַאֲתָא הַשּׁוֹחֵט וְשָׁחַט לְתוֹרָא, דְּשָׁתָה לְמַיָּא, דְּכָבָה לְנוּרָא, דְּשָׂרַף לְחוּטְרָא, דְּהִכָּה לְכַלְבָּא, דְּנָשַׁךְ לְשׁוּנְרָא, דְּאָכְלָה לְגַדְיָא, דִּזְבַן אַבָּא בִּתְרֵי זוּזֵי. חַד גַּדְיָא, חַד גַּדְיָא
וַאֲתָא מַלְאַךְ הַמָּוֶת וְשָׁחַט לְשׁוֹחֵט, דְּשָׁחַט לְתוֹרָא, דְּשָׁתָה לְמַיָּא, דְּכָבָה לְנוּרָא, דְּשָׂרַף לְחוּטְרָא, דְּהִכָּה לְכַלְבָּא, דְּנָשַׁךְ לְשׁוּנְרָא, דְּאָכְלָה לְגַדְיָא, דִּזְבַן אַבָּא בִּתְרֵי זוּזֵי. חַד גַּדְיָא, חַד גַּדְיָא
וַאֲתָא הַקָּדוֹשׁ בָּרוּךְ הוּא וְשָׁחַט לְמַלְאַךְ הַמָּוֶת, דְּשָׁחַט לְשׁוֹחֵט, דְּשָׁחַט לְתוֹרָא, דְּשָׁתָה לְמַיָּא, דְּכָבָה לְנוּרָא, דְּשָׂרַף לְחוּטְרָא, דְּהִכָּה לְכַלְבָּא, דְּנָשַׁךְ לְשׁוּנְרָא, דְּאָכְלָה לְגַדְיָא, דִּזְבַן אַבָּא בִּתְרֵי זוּזֵי. חַד גַּדְיָא, חַד גַּדְיָא

```

How it works:

I first create a list of all the nouns and verbs. It's in a string with a separator because that's a lot cheaper, byte-wise. I also have the ending piece in a variable.

The first part of the first line (חד גדיא, חד גדיא) is already contained at the end, so i just slice it and prepend.

Each of the next lines follows the same format, so i keep a running variable `e` (for end) of the part that gets copied, and just print the part that changes.

The line of השוחט needs to be special-cased.

Code shortened to use BOM by suggestion of Anders Kaseorg and msh210, and optimized with some tricks from msh210's answer.
> 2 votes

# Answer
# Perl 5, 632 bytes

```
$g="חַד גַּדְיָא";$g.=", $g";$\="דִּזְבַן אַבָּא בִּתְרֵי זוּזֵי. $g";@a=split b,"שׁוּנְרָאbכַלְבָּאbחוּטְרָאbנוּרָאbמַיָּאbתוֹרָאbשׁוֹחֵטbמַלְאַךְ הַמָּוֶתbהַקָּדוֹשׁ בָּרוּךְ הוּאbגַדְיָא";@c{@a}=@a;$c{'שׁוֹחֵט'}="הַשּׁוֹחֵט";@d=qw/אָכְלָה נָשַׁךְ הִכָּה שָׂרַף כָבָה שָׁתָה/;push@d,('שָׁחַט')x3;print$g.$";for$i(0..8){$/="\nוַאֲתָא $c{$a[$i]}, וְ$d[$i] לְ$a[$i-1], ";$/.="דְּ$d[$i-$_] לְ$a[$i-$_-1], "for 1..$i;print$/}

```
> 2 votes

# Answer
# Python 2, 331 bytes

(This source contains non-printable bytes, so it is presented as a hexdump that can be decoded with `xxd -r`.)

```
00000000: efbb bf70 7269 6e74 2278 01ed 54b5 6145  ...print"x..T.aE
00000010: 310c ec33 85fb c08e 3f0b 7c66 6668 c2ec  1..3....?.|ffh..
00000020: 39a4 7572 3917 8630 932b 4ba6 23bf a74d  9.ur9..0.+K.#..M
00000030: b9d0 aad1 8ad8 bb42 0eb5 2d97 5ada 318f  .......B..-.Z.1.
00000040: 2c18 9456 4eb5 8189 3216 8646 4b18 ca62  ,..VN...2..FK..b
00000050: dd6a 99ab 1bac aee4 4cdb 461b 5a17 8bed  .j......L.F.Z...
00000060: 68f6 cc6b d1b6 70f8 025c 30c7 ba71 d7af  h..k..p..\0..q..
00000070: b5c0 fb46 0470 47eb a84b a8bb 187b 186b  ...F.pG..K...{.k
00000080: 467b 282b 09c2 b7f2 eea2 0529 c278 d623  F{(+.......).x.#
00000090: d450 84b5 8e1c 9275 2cd0 33ff 0512 9bbc  .P.....u,.3.....
000000a0: ad95 0453 0364 57ac e79c 3a41 d67f cd8b  ...S.dW...:A....
000000b0: 116f 0b7d 58eb 3eba 15b6 4d1d dfd4 2e32  .o.}X.>...M....2
000000c0: feb7 865c 72d0 b6a3 6fa3 8bba ecd9 468e  ...\r...o.....F.
000000d0: 92eb 339e 664f 3798 b84a 1e61 01dd c6f3  ..3.fO7..J.a....
000000e0: 8d6c 27db f71b 9f8d afa1 5d8b 25ff 2b1c  .l'.......].%.+.
000000f0: 3ad3 5618 5c30 af69 9177 9211 e5e5 94be  :.V.\0.i.w......
00000100: ee97 d323 4f27 87b1 5c72 085e 9773 dd3c  ...#O'..\r.^.s.<
00000110: 16d9 3ac9 956a 7f58 b2f9 fb5b 12ab ca10  ..:..j.X...[....
00000120: a0c4 61c2 3302 b9b8 5996 1e89 f9f9 e741  ..a.3...Y......A
00000130: 91bf e181 e407 720b 7329 ec60 222e 6465  ......r.s).`".de
00000140: 636f 6465 2827 7a69 7027 29              code('zip')

```
> 1 votes

# Answer
# GolfScript, 577 bytes

```
"חַד גַּדְיָא, חַד גַּדְיָא. ":d"דִּזְבַן אַבָּא בִּתְרֵי זוּזֵי. "d+"\n"+:c"גַדְיָא,שׁוּנְרָא,כַלְבָּא,חוּטְרָא,נוּרָא,מַיָּא,תוֹרָא,שׁוֹחֵט,מַלְאַךְ הַמָּוֶת,הַקָּדוֹשׁ בָּרוּךְ הוּא"","/:y;"אָכְלָה,נָשַׁךְ,הִכָּה,שָׂרַף,כָבָה,שָׁתָה,שָׁחַט,שָׁחַט,שָׁחַט"","/:x;9,{"וַאֲתָא "\.6="הַ"""if\.y\1+=\", וְ"\.x\=\" לְ"\.y\=\,-1%{", דְּ"\.x\=\" לְ"\.y\=\;}%". "c}%

```

Store the nouns and actions in variables by splitting strings. Using a list of lists of increasing sizes, each in descending order - `[[1],[2,1],[3,2,1]...]` \- print the first and subsequent lines of each stanza using those index values.
> 1 votes

---
Tags: code-golf, kolmogorov-complexity
---