title: Pick the longest stick

text:
# Question
Title: Pick the longest stick
You are a young programming geek living with your 2 other best friends. Every week, one of you has to do all the chores of the house and you decide whose turn it is by picking a stick. The one who picks the shortest stick loses and does all the chores.

As all of you are programmers and love creating puzzles, you have modified the "Pick the shortest stick" into a computer puzzle.

**Here are the rules of the puzzle.**

1. You will be given a 2D matrix, where each column represents a stick.
2. In each column, 1 represents a portion of the stick and 0 is an empty space
3. When going from top to bottom in each column, initially you have `0`'s and as soon as you hit a `1`, the stick has started and rest of the column will be filled with `1` only
4. You can write your program to pick one column. The size of the stick in that column determines the winner/loser. Size of stick == number of 1s in that column.
5. However, that program can only have a linear worst-case time complexity.

As all of you are programmers, you will know if someone else's program is shooting the time complexity limit.

**Your job is to:**

* Write a program or function that accepts input in either a 2D format or array of strings.
* Input can be taken from STDIN/prompt/console or a function argument.
* If you are reading the input from STDIN/prompt then you can assume that the reading of input and converting it to an array takes 0 time (even though the code to do so has to be there in your answer)
* Determine the column with the longest stick in it.
* Output can be the function's return value or to STDOUT/console/alert.
* The program/function must have linear worst-case time complexity, `O(m+n)` where `m` is the number of rows and `n` the number of columns.

**Input can be either one of the following formats:**

2D array:

```
[ [0, 0, 0, 0],
  [1, 0, 0, 0],
  [1, 1, 0, 1],
  [1, 1, 1, 1] ]

```

Array of Strings:

```
[ "0000", "1000", "1101", "1111" ]

```

**The input will have following properties:**

* Size of the array is unknown, assume a rectangle of any size
* In any column, coming top down, if you see a 1, then everything below will be a one
* Empty-columns (i.e. 0-length) sticks *are* allowed.

**This is a code-golf so shortest code wins**!\*

Please explain your code, or give the ungolfed version (to verify time complexity) along with which of the two input formats you expect.

**UPDATE** Linear time complexity here means O(n+m) where n is column size and m is row size. (For those who were unclear)

**UPDATE 2** This definitely **can** be done in linear time. And if you are posting an answer, feel free to delay posting the logic/algorithm by a couple of days for a fair fight :)

**UPDATE 3** I'll go over all answers in couple of hours to validate time complexity and the program :)

# Answer
> 4 votes
# GolfScript, 45 chars

```
:^,:y;0:x{^y(=x=2%y*{y(:y;x\}{x):x}if^0=,<}do

```

Takes input as an array of strings, returns (0-based) index of tallest column. It runs in O(*rows* \+ *columns*) iterations, and each iteration should take essentially constant time (at least assuming constant-time arithmetic). The only array/string operations done within the loop are element lookups (`=`) and taking the length of a string (`,`), both of which take constant time in GolfScript.

Try it online.

### Explanation:

Like most of the solutions here, this code works by starting at the lower left corner of the matrix, walking up or right depending on whether the current element of the matrix is 1 or 0, and keeping track of the column where it last moved up.

At the beginning of the program, I assign the input array to the variable `^`, its length (i.e. the number of rows) to `y`, and 0 to `x`. The value 0 is also left on the stack; during the following loop, it will be replaced by the index of the tallest column.

Within the main loop, `^y(=x=` extracts the `x`-th character of the `y-1`-th row in `^`. This actually returns the ASCII code of the character, so `2%` is needed to drop all but the last bit. As a special case, if `y` equals 0 (which can happen if the tallest column found so far reaches all the way to the top row), the bit looked up will actually come from the *last* row in the matrix (index -1), but the following `y*` forces it to zero, thus effectively creating a virtual all-zeros row at the top of the matrix.

The following `if` will then execute one of the two code blocks preceding it, depending on whether the looked-up bit is non-zero (true) or zero (false). If non-zero, `y` is decremented by one, and the current value of `x` replaces the tallest column index on the stack (with the old value temporarily left on top of it). If zero, `x` is simply incremented by one (and temporarily left on the stack, on top of the tallest column index).

Finally, `^0=` extracts the first row of the matrix, `,` returns its length, and `<` compares it with the column index temporarily left on the stack (which will equal `x` if it was just incremented) If the index is less that the length of the row, the loop repeats.

**Ps.** Based on my testing, it should be possible to shorten this program by one character by replacing the string length test `,<` at the end of the loop with `>`, which cuts the string at the given index and returns the end portion (which will be empty, and thus false, at the end of the loop). However, while cutting a string like that *appears* to be implemented as a constant-time operation in GolfScript (or, rather, in Ruby, which GolfScript runs on top of), I have not found any official documentation saying so. Just to be safe, I've chosen to feature the slightly longer, but definitely O(1), version above.

# Answer
> 6 votes
## Ruby, ~~83~~ ~~75~~ ~~68~~ ~~66~~ 63 bytes

```
f=->m{m[b=c=i=0].map{(c=i;b-=1)while(r=m[b-2])&&r[i]>0;i+=1};c}

```

Defines a function `f` which takes the 2D array form as input.

> I'm starting at the bottom left, keeping track of maximum stick length (actually, minus that) and the corresponding column. In each column, if there are still `1`s above the previous maximum stick length, I walk up the stick to the end and remember the new maximum length and column. That means that I'm iterating once along the columns and at most once along the rows (specifically I'm iterating as far as the maximum stick length), which is precisely `O(m+n)`.

# Answer
> 4 votes
# Python 2 - ~~71, 69, 73, 75~~ 81

```
j=i=-1
M=input()
for m in M[0]:
 j+=1
 while-i<len(M)and M[i][j]:i-=1;J=j
print J

```

# Answer
> 2 votes
# C, 64 bytes

Edit: I learned that the question asks for the location of the longest column and not its length.

The first line is the golfed code and the rest is the sample invocation.

```
g(int m,int n,int**a,int*r){for(*r=n;n*m;a[m][n]?m--,*r=n:--n);}

/* usage:
    m = number of rows
    n = number of columns
    a = 1-based 2D array such that a[i][j] gives the value at the ith row and jth column
    r = address of return value
    Returns (to r) the 1-indexed location of a column with the longest length, or 0 if n=0
    */

int main()
{
    int flat[4*4] = {1, 0, 0, 0,
                     1, 0, 0, 1,
                     1, 1, 0, 1,
                     1, 1, 1, 1};
    int*twoD[4] = {flat-1,flat+3,flat+7,flat+11};
    int ret;
    g(4,4,twoD-1,&ret);
    printf("%d", ret);
    return 0;
}

// old function which determines longest length (65 bytes)
f(int m,int n,int**a,int*r){for(*r=m;n*m;a[m][n]?m--:--n);*r-=m;}

```

# Answer
> 2 votes
**C++ :: 78**

Unlike the other C solution, this is the whole program. (no invocation needed, no need to tell the function the size of the array). Unfortunately this means it is longer as `main` must be used instead of a single character function name, I have to interpret the input and then output the answer, where the other solution handles that "elsewhere". Also my first code golf.
compiled with `g++ file.cpp -include iostream`, run with `./a 000 010 110 111` (for example) == array of strings (I believe this is allowed in the question spec)

```
int c;main(int r,char**v){for(r--;r*v[r][c];v[r][c]-48?std::cout<<c,r--:++c);}

```

The above version outputs the current best found so far on each iteration. The final output digit is the answer. Switching from processing from bottom left instead of bottom right and `0` indexing reduced this solution by 10(!) characters.
switching to c++ drops submission by one more character as `std::cout<<` is shorter than `putchar(-48)` and it should also explicitly support more than 9 sticks with proper output (though it may get harder to differentiate each output)
Removing the answer field and outputting it direcly cut another 6 characters. It now only outputs the current best when it moves up which cuts out some output at least.
Entire file is now only 78 bytes in size - approaching the function only solution that the other `C` submission uses. (with lots of extra code to support said function).

As below description is out of date:

> `c` is global so is initialised with `0`
> `r` is the number of inputs (rows) +1 (name of program)
> `v` is the array of strings with `v[0]` being invalid (name of program)
> As it is 0 indexed, `r` is out of bounds, so decrement.
> While `r!=0` (pointing at valid string) and character `c` in the string is not the null terminator `'\0'`
> if character is not '0'
> go up a row (`r`) and output the column (`c`)
> else go to next column (`c`)
> done

Can I even golf this further?

Ungolfed code (with extra output):

> ```
> #include `<`stdio.h`>`
> #include `<string.h`>
>
> int main(int argc, char* argv[])
> {
>   int rows = argc-1;
>   int cols = strlen(argv[1]);
>   int ans;
>
>   printf("rows: %d, cols: %d\n",rows, cols);
>
>   while((rows)&&cols)
>   {
>     if (argv[rows][cols-1]-'0')
>     {
>       printf("stick @%d,%d\n",cols,rows);
>       ans = cols;
>       rows--;
>     }
>     else
>     {
>       printf("no stick @%d,%d\n",cols,rows);
>       cols--;
>     }
>   }
>   printf("%d",ans);
> }
> ```
> It uses the length of the strings to find out the number of columns and argc to find the number of rows. Starting in the bottom right corner, it follows these simple rules: If cell is a stick, then move up, set answer to current column. If cell is not a stick, then move to the left. O(n+m): as it only moves up and left, it can only have max n+m reads. It exits early if it falls off the top or left of the array.

# Answer
> 2 votes
### PHP 5.4 - 108 bytes

(113 if you include the `<?php`)

Input format: Array will be read as a JSON string.

```
php longest_stick.php "[[0, 0, 0, 0],[1, 0, 0, 0],[1, 1, 0, 1],[1, 1, 1, 1]]"

```

Whitespace added for readability - all newlines and leading spaces can be removed.

```
<?php
$t=count($s=json_decode($argv[1]))-1;
foreach($s[0] as $k=>$_)
    while($s[$t][$k]) {
        $t--;
        $l = $k;
    }
echo $l?:0;

```

Minified version:

```
<?php $t=count($s=json_decode($argv[1]))-1;foreach($s[0] as $k=>$_)while($s[$t][$k]){$t--;$l=$k;}echo $l?:0;

```

Kind of stealing the algorithm from Martin here, but it's nice to play around with languages that aren't seen as often here XD

# Answer
> 2 votes
**C#: 236 Chars**

```
int p(int[,] a){int y=0,s=0,i=0,x;for(;++y<=a.GetUpperBound(0);)for(x=i;x<=a.GetUpperBound(1);){if(a[y,x++]==0)break;s=y;i++;}return s;}

```

ungolfed:

```
int p(int[,] a)
{
    int selectedRow=0;
    int maxLength=0;
    for(var y = 0; y<=a.GetUpperBound(0); y++)
        for(var x=maxLength; x<=a.GetUpperBound(1); x++)
        {
            if(a[y,x++]==0)
                break;
            selectedRow=y;
            maxLength++;
        }
    return selectedRow;
}

```

# Answer
> 2 votes
# Cobra - 98

```
def f(a)
    s,x,y=0,0,a.count-1
    while y+1and x<a[0].count
        while a[y][x],y,s=y-1,x
        x+=1
    print s

```

# Answer
> 1 votes
# OCaml - 144 characters

```
let s a=Array.(let rec f i j m=if i=0then m else if a.(i).(j)=0then if j=length a.(i)-1then m else f i(j+1)m else f(i-1)j j in f(length a-1)0 0)

```

Takes an `int array array` as input, and starts from below left, moving up or right if it sees a `1` or a `0`. Column count starts at `0`.

## Usage

```
 s [| [| 0; 0; 0; 0 |]; [| 0; 0; 1; 0|]; [| 1; 0; 1; 0 |]; [| 1; 1; 1; 0 |]; [| 1; 1; 1; 1 |] |];;
 - : int = 2

```

## Ungolfed

```
let s a = Array.(
  let rec f i j m = (* m is the longest stick seen so far *)
    if i=0 then m (* A column is full: this is the longest possible stick and j=m anyway *)
    else if a.(i).(j)=0 then (* current column is shorter than a previously seen stick *)
      if j=length a.(i)-1 then m (* we have examined all columns, just return m *)
      else f i(j+1) m (* start examining next column *)
    else f (i-1) j j (* current column is longer than all the ones previously seen. Check how long the stick is *)
  in
  f (length a-1) 0 0)

```

# Answer
> 0 votes
## T-SQL - ~~71~~ 64

Takes table A as input

```
SELECT IDENTITY(INT, 1, 1) R, A INTO A
FROM (VALUES
 ('0000')
,('1000')
,('1101')
,('1111')
) AS A(A)

```

And the query is

```
SELECT TOP(1)CHARINDEX('1',A)FROM A WHERE A LIKE'%1%' ORDER BY R

```

SQLFiddle

This returns the first row from the table a ordered by r where there is a 1 in string a.

`TOP(1)` restricts the result to the first row returned.

`CHARINDEX('1',A)` returns the position of the first 1 in the string or zero if it isn't found.

`WHERE A LIKE'%1%'` filters to rows where A contains a 1

`ORDER BY R` ensures the table is read from top down

# Answer
> 0 votes
# Delphi 122 chars

Sigh...it is such a voluminous language.

Update: had to add 6 characters in changing function the return type from I to integer. The function still compiled as the test program had a "type I=integer;" statement left over from an earlier version of the program.

```
function S(A:array of string):integer;var n,c:integer;begin n:=0; repeat c:=Pos('1',A[n]);inc(n) until c>0; result:=c;end;

```

# Answer
> 0 votes
# scheme - 236 chars

Even longer than the delphi version...there is probably a way to do this much more efficiently with scheme. And even worse - I just noticed it is order m\*n.

```
(define (s l) (cond ((eq? (cdr l) '()) (car l)) (else (map + (car l) (s (cdr l)))))) (define (u l) (define (t n p q l) (cond ((eq? l '()) p) ((< n (car l)) (t (car l) q (+ 1 q) (cdr l))) (else (t n p (+ 1 q) (cdr l))))) (t 0 0 1 (s l)))

```

l is a list of the form '((0 0 0 0) (1 0 0 0) (1 1 0 1) (1 1 1 1)). I think that is a fair representation of a 2D array input for scheme.

(s l) sums the n-th elements of each of the sub-lists of a list of lists of nuimbers, so (s '((0 0 0 0) (1 0 0 0) (1 1 0 1) (1 1 1 1))) would return (3 2 1 2).

(u l) returns the 'index' of the largest entry of a list of numbers (using the helper function t), so (u '(3 2 1 2)) will return 1 (as the largest element '3 in the list '(3 2 1 2) is at position 1).

# Answer
> 0 votes
# Racket 70

Golfed:

```
(define(h m)(for/last([r m]#:final(memv 1 r))(length(takef r even?))))

```

Assumes input is a two-dimensional array, which in Racket would be a list of lists:

```
(define m
  '((0 0 0 0)
    (1 0 0 0)
    (1 1 0 1)
    (1 1 1 1)))

```

Ungolfed:

```
(define (h m)
  ;; step through rows, stopping at the first that contains a 1
  (for/last ([r m] #:final (memv 1 r))
    (length (takef r even?)))) ; pop off the leading zeroes to get the column index

```

Returns the column index with the longest stick.

# Answer
> 0 votes
# JavaScript, ES6, 76 characters

```
W=a=>(j=>{for(k=i=a.length-1;~i&~j;)a[i][j]?(k=j,i--):j--})(a[0].length-1)|k

```

Takes array of array input.

# Answer
> 0 votes
# JavaScript ES6, 65 bytes

Takes both input formats

```
f=(a,t)=>a.reduceRight((p,c)=>t+1?t:(x=c.indexOf(1,p))+1?x:t=p,0)

```

**Explained:**

Iterates from bottom to top. Uses `String.prototype.indexOf()` or `Array.prototype.indexOf()` depending on the input on each value. Finds the first index of each row with a 1 from the previous offset, if it finds none then it sets the `t` variable to the last offset and doesn't perform anymore `indexOf` calls.

---
Tags: code-golf, restricted-complexity
---


# Question
Title: Cycle lengths for Perfect shuffles of decks of any size
## Challenge

In the shortest amount of code:

1. Compute the length of the permutation cycle of a perfect shuffle on a deck of cards of any size *n* (where *n* ≥ 2 and *n* is even).
2. Output a table of all cycle lengths for 2 ≤ *n* ≤ 1000 (*n* even).

Note that there are two basic ways of defining a perfect shuffle. There is the ***out-shuffle***, which keeps the first card on top and the last card on bottom, and there is the ***in-shuffle***, which moves the first and last cards one position toward the center. You may choose whether you are doing an out-shuffle or an in-shuffle; the algorithm is almost identical between the two.

* **out-shuffle** of 10-card deck: \[1,2,3,4,5,6,7,8,9,10\] ↦ \[1,6,2,7,3,8,4,9,5,10\].
* **in-shuffle** of 10-card deck: \[1,2,3,4,5,6,7,8,9,10\] ↦ \[6,1,7,2,8,3,9,4,10,5\].

## Graphical example

Here, we see that an *out-shuffle* on a 20-card deck has a cycle length of 18 steps. (This is for illustration only; your solution is not required to output cycles graphically.) The classic 52-card deck, on the other hand, has an out-shuffle cycle length of only 8 steps (not shown).

An *in-shuffle* on a 20-card deck has a cycle length of only 6 steps.

## Tabular example of output

Your program should output something similar to this, although you may choose any tabular format that you like best. This is for an out-shuffle:

```
2 1
4 2
6 4
8 3
10 6
12 10
14 12
16 4
18 8
20 18
22 6
24 11
26 20
28 18
30 28
32 5
34 10
36 12
38 36
40 12
...many lines omitted...
1000 36

```

## Questions

1. Does there seem to be any connection between the number input *n* and its cycle count, when *n* is a power of 2?
2. How about when *n* is not a power of 2?
3. Curiously, a 1000-card deck has an out-shuffle cycle count of only 36, while a 500-card deck has an out-shuffle cycle count of 166. Why might this be?
4. What is the largest number you can find whose cycle count *c* is vastly smaller than *n*, meaning that ratio *n*/*c* is maximized?

# Answer
> 6 votes
# Haskell, ~~47~~ ~~46~~ 44 (in shuffle)

```
[[i|i<-[1..],mod(2^i)n<2]!!0|n<-[3,5..1001]]

```

the basic realization is that this is the order of 2 in the multiplicative group of modulus `n+1`.

# Answer
> 5 votes
# Pyth, 16 bytes

```
mfq1%^2T+3yd)500

```

In-shuffle using A002326.

# Answer
> 2 votes
# Pyth, 22 bytes

```
V500,JyhNl{.u.iFc2NJUJ

```

Try it online: Demonstration. Replace 500 with a smaller number, if it is too slow.

### Explanation:

```
V500                     for N in [0, 1, ..., 499]:
      yhN                   (N + 1) * 2
     J                      assign to J
           .u      JUJ      apply the following expression J times
                            to N, starting with N = [0, 1, ..., J - 1],
                            and return all intermediate results:
                c2N            split N into 2 halfs
             .iF               and interleave them
         l{                 remove duplicates and give length
    ,                       make a pair and print

```

# Answer
> 2 votes
## Mathematica, 53 (in-shuffle)

```
Grid[{2#,MultiplicativeOrder[2,2#+1]}&/@Range[1,500]]

```

or, not antagonistically spaced

```
Grid[{2 #, MultiplicativeOrder[2, 2 # + 1]} & /@ Range[1, 501]]

```

Output:

```
   2    2
   4    4
   6    3
   8    6
  10   10
  12   12
  14    4
  16    8
  18   18
  20    6
 (* digits, digits, bo bidgits, banana fana, ... *)
  498  166
  500  166
 (* skip a bit, brother ...  *)
  998   36
 1000   60

```

Every entry in both columns is horizontally centered in their columns, but I don't have the fractional spaces ` ` ... ` ` here to replicate that.

Observations:

* Out-shuffle is in-shuffle on a deck two cards smaller. (Note that the first and last cards are in fixed position throughout the out-shuffle demonstration.) Consequently, the two choices will lead to similar output lists -- the second column will be shifted by one row. Regarding the "powers of two" hint, the in-shuffle of power of two decks has the pattern `{2^n - 2, n}`, `{2^n, 2n}`. (Out-shuffle pairs `2^n` with `n`.)
* Observe in the in-shuffle example that the distance of `2` from the closest end of the deck doubles at each step. `{2, 4, 8, 15 = -5, -10, -20}`. In fact, this is true for *every* card. We therefore only need to know which power of `2` is congruent to `1` mod `n+1` where `n` is the number of cards. (Note that in the example, the cards in the last column, column `-1`, are doubled to the penultimate column, `-2`, meaning that `0` is congruent to one more card than is in the deck, thus "mod `n+1`".) Therefore, the MultiplicativeOrder\[\] function is the way to go (in Mathematica).
* By default, one would try TableForm\[\] instead of Grid\[\], but the output is similar.

# Answer
> 0 votes
# C,86 (or 84)

Score excludes unnecessary whitespace, included for clarity.

```
i,j,n;
main(){
  for(;n<1002;printf("%d %d\n",n,j),n+=2)
    for(i=n,j=1;i=i*2%(n+1),i-n;)j++;
}

```

This is an in-shuffle, which as pointed out by others, is just the out shuffle with the stationary cards at both ends removed.

As pointed out by others, in the in-shuffle, the position of each card doubles each time, but this must be taken modulo `n+1`. I like to think of the extra card position being position zero to the left of the table (you can think of this as holding both the stationary cards from the out-shuffle too). Obviously the position of the card must always be positive, hence the zero position always remains empty for the in-shuffle case.

The code initialises `i` to the value of `n`. Then it multiplies by 2, takes the result mod `(n+1)` and checks to see if `i` has returned to its initial value (`i-n` is zero.) It increments `j` for each iteration, except the last one (hence the need initialise `j` to 1.)

In principle, `i` could be with any value in the range `1..n`, so long as the comparison at the end checked if it was intialised to the same number. The reason for picking `n` was to make sure the program works for the case `n==0`. the problem was that any number modulo `(0+1)` is zero, so the loop never terminated in this case if `i` was initialised to a constant such as 1.

The question examples includes the equivalent case `n==2` for the out shuffle, so it was interpreted that this case is required. If it isn't, two bytes `n,` could be saved by initializing `i` to 1, the same value as `j`.

---
Tags: code-golf, number, number-theory, permutations, card-games
---


title: Find X in a partially sorted Array

text:
# Question
Title: Find X in a partially sorted Array
Your job is to find the location (read index) of a given element `X` in an array gone through the following transformation process:

1. Take a fully sorted integer array of size `N` (`N` is known implicitly)
2. Take any random number of mutually exclusive even index pairs (as in that no index appears in more than 1 pair) from the array and swap the elements on those indexes.

A sample array can be like

```
[5, 2, 3, 4, -1, 6, 90, 80, 70, 100]

```

formed by

```
// Take fully sorted integer array
[-1, 2, 3, 4, 5, 6, 70, 80, 90, 100]
// Take some even index pairs : (0, 4) and (6, 8)
// Swap the elements in these indexes. i.e., element at 4<sup>th</sup> index goes to 0<sup>th</sup> etc.
// Final array:
[5, 2, 3, 4, -1, 6, 90, 80, 70, 100]

```

and a sample `X` to find in this array can be

```
-1

```

You should output the index of the element `X` in the final array (`4` in the above example) or `-1` if the element is not found in the array.

**Rules**

* In built searching functions are prohibited.
* You must write a method/function/program which takes input from STDIN/Command line arguments/Function arguments.
* Input must be in `<Array> <X>` format. Example: `[5, 2, 3, 4, 1, 6, 9, 8, 7, 10] 1`
* ~~The input array may also contain duplicate integers. In such case, any one index can be the output. **UPDATE** : You may assume that total number of duplicates \<\< (far less than) size of array.~~ For the benefit of the question in general, duplicates are now prohibited to avoid playing a role in time complexity of the searching algorithm.
* Output should be the index of the element `X` in the array or `-1` if not present.

**Scoring**

* Being a and a , your score is calculated by `<byte count of your program>*<coeff. of complexity>`
* Coefficient of Complexity is decided based on the worst case time complexity of your code (Big-O) using the mappings given below.
* If your code needs to know the length of the array, it can calculate length using inbuilt methods and that won't be added to the time complexity of the searching part of the code.

```
Time Complexity      Coefficient
--------------------------------
O(1)                 0.25
O(log(n))            0.5
O(n)                 5
O(n*log(n))          8.5
O(n^2)               10
O(greater than n^2)  20

```

Minimum score wins!

**Bonus**

* Multiply your final score by `0.5` if you can handle a case where the array has gone through the step 2 in the transformation process `I` times (instead of just 1), where `I` is passed as the third parameter in input.
* Note that while going through step 2, `I` times, pairs in each step are mutually exclusive, but pairs in different steps can have common indexes.

# Answer
> 7 votes
# JavaScript (E6) 97.5 (39\*5\*0.5)

(O(n), linear search, the array can be scrambled again and again)
The function accepts (and ignores) a third parameter

```
F=(a,x)=>a.map((e,i)=>e-x?0:j=i,j=-1)|j

```

or

```
F=(a,x)=>a.some((e,i)=>(j=i,e==x))?j:-1

```

or

```
F=(a,x)=>a.every((e,i)=>(j=i,e-x))?-1:j

```

**Test** in FireFox/FireBug console

```
F([5, 2, 3, 4, -1, 6, 90, 80, 70, 100],-1, 2)

```

*Output*

```
4

```

# Answer
> 4 votes
# Golfscript, 20 * 2.5 = 50

```
~{={0:-1}*0):0}+%;-1

```

Explanation:

* `~` \- eval the input. It should be in the form `[-1 0 3 2 4] 3`.
* `{...}+%` \- prepend the last argument (needle) to `{...}`, then map the resulting function over the array
* `;-1` \- discard the results of the mapping, and push `-1` to the stack.

The real fun is what happens inside:

* `=` \- check if the needle matches the haystack element
* `{0:-1}` \- take the current value of the variable `0` and store it into the variable `-1`.
* `*` \- execute the function n times = execute if the previous is true.
* `0):0` \- increment the current value of `0`.

yep. In golfscript, ~~numeric~~ all literals are just variables initialised to some useful values.

# Answer
> 3 votes
### Haskell, 51 * 2.5 = 127.5

```
a 0= -1;a x=x;f[]_= -1;f(h:t)n|h==n=0|1>0=a$1+f t n

```

ungolfed:

```
adjust 0 = -1
adjust x =  x

find []     _ = -1
find (x:xs) n | x == n    = 0
              | otherwise = adjust $ 1 + find xs n

```

# Answer
> 2 votes
# Python ~~79.75 (319\*0.5\*0.5)~~ 106.5 (213\*0.5)

**UPDATE**: Since the time complexity is determined by worst case for any number of swaps, I have reduced my algorithm to work only for the case `I=1`, which results in O(log n) time.

The findX function is f~~, while g, and h are helpers.~~

The function uses the ordering of the odd indices to apply search to find where X should be. If X has been swapped then it uses a second binary to search to find where X has been swapped to, based on the value found at where X should have been. Since I use two binary searches in the worst case it is O(logN).

~~I find X by applying a binary search on the odd indices. If X is not found on the odd indices, I check the array at the even index where X should be if the array was ordered (call this value n1). If n1 equals X, I found the index. If n1 does not equal X I use the same binary search to find where n1 should be in the ordered array (to see if X was swapped with n1). Call this new value n2. If n2 equals X, I found the index. Otherwise I use the same binary search to find where n1 should be in the ordered array (to see if X was swapped with n2) ... etc.~~

~~The algorithm terminates when X is found or n1 is found a second time.<br>~~

~~Essentially my algorithm traces the random swapping in reverse. That is, it will 'decode' the last swap, then 'decode' the second last swap, and so on until I decode the first swap. For each 'decode', I use a binary search ( O(logN) time ), plus an additional binary search to find the first index. The algorithm will 'decode' the simplest sequence of random swaps to get to the given state (e.g. the algorithm will not apply any decoding to an array that had the same swapping applied twice). Also, note that any sequence of swapping will be equivalent to a sequence of swapping of length less than or equal to N/2. Hence the complexity is at worst O(min(I, N/2) * logN) and the algorithm works for I swaps.~~

```
def f(l,X):
   m=len(l)
   i=g(l,X,0,m-m%2)
   return -1 if i>=m else i if l[i]==X else g(l,l[i],0,m-m%2)
def g(l,X,n,m):
   a=(n+m)//2
   a+=a%2-1
   return n if m<=n else g(l,X,a+1,m) if l[a]<X else g(l,X,n,a-1) if l[a]>X else a

```

~~def h(l,F,X,s,m): i=g(l,F,0,m-m%2) return -1 if i==s or i\>=m else i if l\[i\]==X else h(l,l\[i\],X,s,m)~~

Ex:

`print f([-1, 2, 3, 4, 5, 6, 70, 80, 90, 100],-1)
print f([5, 2, 3, 4, -1, 6, 90, 80, 70, 100],-1)
print f([5, 2, 3, 4, -1, 6, 90, 80, 70, 100], 5)
print f([-1, 2, 70, 4, 90, 6, 3, 80, 5, 100],-1)`

Output:

`0
4
0
0`

# Answer
> 1 votes
# JavaScript ES6, 95 (38\*5\*0.5)

Performs an `O(n)` search. Accepts bonus parameter but ignores it

```
f=(a,x)=>a.reduce((p,c,i)=>c-x?p:i,-1)

```

---
Tags: code-challenge, search
---


title: GolfScript, CJam, or Pyth?

text:
# Question
Title: GolfScript, CJam, or Pyth?
Which language usually produces shorter golfed code: Pyth, CJam or Golfscript?

In asking this, I do not mean which has a prettier syntax or which has the most useful commands, I mean overall, which one is usually the shortest? What types of problems would we expect each language to have an advantage in?

# Answer
There is no simple answer to this question.

GolfScript almost never beats CJam. It has a lot less built-ins than CJam and the overall syntax is a bit more verbose. For example, `print` and `{+}*` become `o` and `:+` in CJam.

The only exceptions are extremely trivial problems where the fact that GolfScript implicitly reads from STDIN is an advantage and the few occasions where block concatenation is useful (example).

With CJam and Pyth, it's a bit more complicated. Both languages can beat the other in particular challenges, although, by my completely unscientific observation, Pyth seems to have the upper hand on more occasions.

A few particular cases where picking one over the other is rather easy:

* Choose Pyth if it has a built-in that CJam lacks and significantly simplifies the task.

For example, Pyth has `r<iterable>2`, which is Python's `swapcase()`. If that's useful in a challenge (example), it will be hard to beat with CJam.
* On occasions, you have to build the output piece by piece. After finishing the program, CJam implicitly prints the entire stack, so you can just dump the pieces and let the interpreter do the rest.

For example, challenges are usually won by CJam.
* The length of a single built-in may be a decisive factor in a challenge.

Here, Pyth's `C`, which is shorter than CJam's `256b`, was enough to outgolf CJam.

This would be longer in Pyth, partly because trigonometric functions are 3-character built-ins in Pyth and 2-character built-ins in CJam.

To sum it up, there is no single language that will magically make you win all code golf competitions. You haven't even considered APL, J, K, O, Q, TI-BASIC, Retina, Perl, sed and Mathematica, which all have beaten both CJam and Pyth in a few occasions.

You have several options:

* Learn Pyth *and* CJam. Use the one that's more suited for each task.
* Learn the one (first) you like better.

Personally, I'm crazy about stack-based languages, which I find much more easier to write and read.
* Learn the one suited better for the challenges you enjoy.

is your thing? Go with CJam. Nothing beats ? Forget about both and learn J.
> 25 votes

# Answer
Doorknob posted the following statistics on Chat, which I understand are based on answers to existing challenges. All credit goes to him. They certainly agree what I would have imagined.

```
golfscript is shorter than pyth 6 times (~13.043%)
golfscript is shorter than cjam 16 times (~20.513%)
pyth is shorter than golfscript 39 times (~84.783%)
pyth is shorter than cjam 59 times (~60.204%)
cjam is shorter than golfscript 57 times (~73.077%)
cjam is shorter than pyth 31 times (~31.633%)

```

I was going to leave these to Doorknob to post, but I found them interesting and thought if the question is going to stay open a while longer, it would be nice to post them for posterity, before it gets closed.

Obviously the best language will depend on each specific challenge, and this data only considers the corpus of challenges that we have at the moment. A change in the type of challenges would alter the balance between the languages.

Additionally, this data reflects the state of the languages today (Aug 2015). The languages are still in development, so it will be interesting to see how they perform in later versions.

This only covers challenges where at least two of the languages participated, which is probably fairer than considering all challenges. Nevertheless, as in virtually any statistical analysis, it is arguable that there could be some selection bias. It's possible that many challenges were so suited to a particular language that the others were not even considered.
> 8 votes

# Answer
Considering that the point of code golf is to think in terms of a given language's kolmogerov complexity, in my opinion it doesn't matter much which language you use as long as you are clever. All of {Golfscript,CJam,Pyth,J} allow you to exercise creativity as do non-golfing languages. While code-golf technically claims "shortest code wins" this typically only really matters within each language. Often more important (as far as I can tell from looking at voting patterns, etc) is how creative or difficult your solution is.

For example HQ9+ while hilarious doesn't really win a 99 bottles of beer competition, because writing `9` isn't exactly showing effort. Meanwhile the Malbolge execution of 99 bottles of beer is considered incredibly cool despite being very lengthy due to its creative nature and the effort put in to make it. If HQ9+ did win we could merely define a language `L` which states: `L` outputs the solution to this problem, otherwise the code is compiled as C and executed.

This is why most old golfing sites still in operation are language-specific (Perl, Vim, C \[if you count IOCCC\]) because comparing code-sizes of different languages just doesn't make much sense. Most languages will have at least one challenge where they win. That doesn't make them 'better' than the alternatives.

Interestingly enough I have found that if you stretch the definition of language too much you get very creative/odd solutions to problems. (EG: many ASCII-art competitions could be won by a series of Vim keystrokes over at vimgolf.com).

If code-length is really all you care about, there are even more terse languages then the mentioned Golf-oriented languages. The reason they are often used for golfing is that their code-size is typically directly related to algorithmic complexity, whereas in for example C, you may sacrifice algorithmic complexity for shorter syntax to out-golf the competition. Meanwhile the even terser languages aren't really designed to be human programmable, and are more oriented to approximating kolmogorov complexity or theoretical applications.

My recommendation: learn whichever golfing language is based on a language you like. If you enjoy Python, learn Pyth. If you enjoy Ruby, learn GolfScript. If you like C/C++/Java learn CJam (and if you find you enjoy CJam you may wish to look into Joy which is a similarly concatenative-stack-based language designed for usability rather than golfability)
> 1 votes

---
Tags: code-golf, tips, golfscript, pyth, cjam
---


title: Cryptic Kicker //

text:
# Question
Title: Cryptic Kicker //
**Cryptic Kicker**

A common but insecure method of encrypting text is to permute the letters of the alphabet. In other words, each letter of the alphabet is consistently replaced in the text by some other letter. To ensure that the encryption is reversible, no two letters are replaced by the same letter. Your task is to decrypt several encoded lines of text, assuming that each line uses a different set of replacements, and that all words in the decrypted text are from a dictionary of known words.

***Input***

The input consists of lowercase words, in alphabetical order. These words compose the dictionary of words which may appear in the decrypted text. Following the dictionary are several lines of input. Each line is encrypted as described above.

There are no more than 1,000 words in the dictionary. No word exceeds 16 letters. The encrypted lines contain only lower case letters and spaces and do not exceed 80 characters in length.

***Output***

Decrypt each line and print it to standard output. If there are multiple solutions, any one will do. If there is no solution, replace every letter of the alphabet by an asterisk.

***Sample Input***

```
and dick jane puff spot yertle

bjvg xsb hxsn xsb qymm xsb rqat xsb pnetfn
xxxx yyy zzzz www yyyy aaa bbbb ccc dddddd

```

***Sample Output***

```
dick and jane and puff and spot and yertle
**** *** **** *** **** *** **** *** ******

```

Here's the solution. Please note that I am not a horse running in the race for the shortest bytes **/** Competitive programmer. I just like puzzles!

(Source)

# Answer
# Python 3, 423 bytes

```
import sys,re
S=re.sub
D,*L=sys.stdin.read().split('\n')
def f(W,M=[],V="",r=0):
 if len({d for(s,d)in M})==len(M):
  if[]==W:return V.lower()
  for d in D.split():p='([a-z])(?%s.*\\1)';m=re.match(S(p%'=',')\\1=P?(',S(p%'!',').>\\1<P?(',W[0].translate(dict(M))[::-1]))[::-1]+'$',d.upper());r=r or m and f(W[1:],M+[(ord(s),m.group(s))for s in m.groupdict()],V+d+" ")
  return r
for l in L:print(f(l.split())or S('\w','*',l))

```

Reads input from STDIN and writes output to STDOUT, using the same format as the sample input/output.

## Explanation

For each line of ciphertext, we perform the following procedure:

We keep a map, *M*, of all the letter transformations we've already established (which is initially empty). We do it in such a way that the source letters are all lowercase and the destination letters are all uppercase.

We process the words in the ciphertext in order. For each word, we find all the words in the dictionary it might match, as follows:

Suppose that our word, *w*, is `glpplppljjl` and that *M* contain the rule `j -> P`. We first transform *w* using the existing rules in *M*, getting `glpplpplPPl`. We then transform *w* into the following python-flavored regex:

```
(?P<g>.)(?P<l>.)(?P<p>.)(?P=p)(?P=l)(?P=p)(?P=p)(?P=l)PP(?P=l)

```

The rules of the transformation are as follows:

* The first occurrence of each lowercase letter, *`x`*, is replaced with `(?P<`*`x`*`>.)`. This defines a named capture group, called *`x`*, that matches a single cahracter.
* Every subsequent occurrence each lowercase letter, *`x`*, is replaced with `(?P=`*`x`*`)`. This is a backreference to the character previsouly captured by the named group *`x`*.

We perform this transformation by reversing *w*, then applying the two following regex substitutions:

```
s/([a-z])(?!.*\1)/)>\1<P?(/
s/([a-z])(?=.*\1)/)\1=P?(/

```

and then reversing the result. Note that the characters previously transformed by *M* appear as uppercase, and therefore remain unchanged.

We match the resulting regex against each of the dictionary words, where the dictionary words appear as uppercase. For example, the above regex would match the word `MISSISSIPPI`. If we find a match, we extract the new transformation rules from it, and add them to *M*. The new transformation rules are simply the characters captured by each of the capture groups. In the above regex, the group `g` matches `M`, the group `l` match `I`, and the group `p` matches `S`, giving us the rules `g -> M, l -> I, p -> S`. We have to make sure that the resulting rules are consistent, that is, that no two source letters map to the same destination letter; otherwise, we reject the match.

We then proceed to the next word, using the augmented transformation rules. If we can match all the ciphertext words using this process, we have decrypted the text. If we can't match a word against any of the dictionary words, we backtrack and try to match the previous words against different dictionary words. If this process fails, there is no solution, and we print a row of asterisks.
> 3 votes

# Answer
# CJam, ~~62~~ 56 bytes

```
qN%Sf/(f{\:C,m*{C..+`Sa`m2/Q|z_''f-Qf|=},C:,'*f*a+0=S*N}

```

Quite slow and memory hungry, but works for the test case with the Java interpreter.

### Example run

```
$ cat input; echo
and dick jane puff spot yertle

bjvg xsb hxsn xsb qymm xsb rqat xsb pnetfn
xxxx yyy zzzz www yyyy aaa bbbb ccc dddddd
$ time cjam kicker.cjam < input
dick and jane and puff and spot and yertle
**** *** **** *** **** *** **** *** ******

real    5m19.817s
user    6m41.740s
sys     0m1.611s

```
> 2 votes

---
Tags: code-golf, cryptography
---


title: Laplace transform of a polynomial

text:
# Question
Title: Laplace transform of a polynomial
Your goal is to write a program that will print out the Laplace transform of a polynomial function with integer coefficients \\$f(x)\\$. The Laplace transform of \\$f(x)\\$ is defined as \\$\int\_0^\infty f(x) e^{-sx} dx\\$.

The standard input for the polynomial function will be

```
a+bx+cx^2+dx^3+...

```

If the coefficient is zero, that term is omitted. It can be taken in from any standard type of input.

```
This is valid input: 1+x^2-5x^4+20x^5
These aren't:
0
1+0x
1+x^1
x^0+x

```

You may output from any standard type of output, in any readable order. Trailing newline is permitted. No using built in evaluation functions.

Examples:

```
Input: 1
Output: 1/s

Input: 3-x
Output: 3/s-1/s^2

```

This is code golf, so the shortest entry in bytes wins.

# Answer
# CJam, 57 bytes

```
l_"+-":Pf&sN+\PSerS/.{'^-'x/2We]"11".e|:~~:Em!*"/s^"E)+@}

```

Try it online in the CJam interpreter.
> 2 votes

# Answer
# Perl, 129 bytes

Regex-based solution:

```
sub f{@_[0]<2?1:@_[0]*f(@_[0]-1)}$_=<>;s/(\d*)x\^?(\d*)/f($2?$2:1)*($1?$1:1).'^'.($2?$2+1:2)/eg;s/(?<!\^)(\d+)/$1.'\/s'/eg;print

```

Multiline:

```
sub f{@_[0]<2?1:@_[0]*f(@_[0]-1)} # define factorial subroutine
$_=<>; # read input
# do the laplace transform for all non-constant terms, without dividing by s:
s/(\d*)x\^?(\d*)/f($2?$2:1)*($1?$1:1).'^'.($2?$2+1:2)/eg;
s/(?<!\^)(\d+)/$1.'\/s'/eg; # divide non-exponents by s
print

```
> 1 votes

---
Tags: code-golf, math, polynomials
---


title: Sort the Textbooks

text:
# Question
Title: Sort the Textbooks
# Sort the Textbooks

School is starting soon (if it hasn't already) and so it's time to get our textbooks in order. You need to sort your books in alphabetical order but that takes too long so you decide to write a program to do it.

### Examples

**Input:**

```
 _
| |  _
|F| | |
|o|_|P|
|o|B|P|
| |a|C|
| |r|G|
|_|_|_|

```

**Output:**

```
   _
  | |_
  |F| |
 _|o|P|
|B|o|P|
|a| |C|
|r| |G|
|_|_|_|

```

---

### Input

The input will be a set of books which need to rearranged alphabetically. It will contain only: `|`, `_`, , and `A-Za-z`. The titles of the books are read vertically, top-bottom.

You may choose to assume the input is padded with whitespace to fit a rectangle. If you choose to have your input padded with whitespace, please specify this in your answer.

The very maximum book height your program will need to handle is 5,120 lines tall without failing.

The books will always be 1-thick and their will always be at least one book in the input

### Output

The output will need to be the same set of books organized in alphabetical order. The height of the books must stay the same and the title must have the same spacing from the top when re-arranged.

Books should be sorted alphabetically. If your language sports a sort function you can use that. Otherwise you can use alphabetical sorting as described here.

**Book Title Examples**

```
 _
| |
| |
|F|
|o|
|o|
| |
| |
|B|
|a|
|r|
| |
| |
|_|

```

This books title is:

```
"Foo  Bar"

```

Book titles will *only* contain letters and spaces.

Trailing whitespace is allowed

---

# Winning

This is so shortest code in bytes wins.

# Answer
# CJam, 60 bytes

```
qN/:Kz1>2%{_{" _"-}#>}$_{_'_#>,}%2,\*2ew{:e>('|*K,Se[}%.\zN*

```

I tried porting my Python answer, which is also similar to @RetoKoradi's approach.

Try it online. The input should be padded with spaces to form a rectangle.
> 5 votes

# Answer
# Python 3, 231 bytes

```
def f(s):
 *M,L=sorted(["".join(c).strip()for c in zip(*s.split("\n"))][1::2],key=lambda x:x[1:-1].strip()),;l=m=0
 for r in L+[""]:n=len(r);M+="|"*~-max(n,l),r;m=max(n,m);l=n
 for r in zip(*[x.rjust(m)for x in M]):print(*r,sep="")

```

Just a quick hack. Zip the books, sort, rezip, taking care of the columns of `|` while we're at it.

Input a multiline string, padded with trailing spaces to a rectangle. The output has one more trailing space on each line than necessary.

## Ungolfed

```
def f(s):
  new_cols = []

  # Zip columns, removing the spaces above each book
  # [1::2] is to skip columns of |s, keeping only the books
  books = ["".join(c).strip() for c in zip(*s.split("\n"))][1::2]

  # Sort based on title, [1:-1] to remove the top and bottom _s
  books.sort(key=lambda x:x[1:-1].strip())

  last = 0
  max_height = 0

  for book in (books + [""]):
    height = len(book)

    # Append |s as necessary for the left edge of the current book
    # The +[""] above is for the right edge of the last book
    new_cols.extend(["|"*(max(height, last) - 1), book])

    max_height = max(height, max_height)
    last = height

  # Rezip columns, add back spaces as necessary and print
  for col in zip(*[x.rjust(max_height) for x in new_cols]):
      print("".join(col))

```
> 8 votes

# Answer
## Ruby (~~209~~ ~~204~~ ~~200~~ 198 bytes)

```
a=n.tr(?|,' ').split$/
i=!p;t=a.map(&:chars).transpose.map(&:join).select{i^=a}.sort_by{|s|s[/[A-Z]/][0]}
x=0;t.map{|t|y=0;u=p;t.chars{|c|u&&a[y][x,3]=?|*3;a[y][x+1]=c;y+=1;u|=c=='_'};x+=2}
a.join$/

```

The `transpose` function in this solution requires that all lines are the same length, hence the input needs to be padded with whitespace.

### Explanation

```
def sort_books(n)
  a = n.tr(?|,' ')  # pre-emptively remove all the '|'.
    .split $/         # and split into an array of lines
                      # ($/ is the INPUT_RECORD_SEPARATOR, typically "\n")
                      # we're going to write our answer into `a` later

  i = !p # i = true; we'll use this as a flip-flop variable
         # Kernel#p returns nil with no args

  # we're now going to get a sorted array of book titles (t)
  t = a.map(&:chars)  # break array into nested array of every character
       .transpose     # and transpose the entire array
       .map(&:join)   # this gives us an array of "horizontal" book titles with dividers

       .select { i ^= a } # select every second line
                          # (i.e. just titles without dividers)
                          # `i` starts off true
                          # `a` is truish (it's our original array)
                          # `^=` is the bitwise xor assignment,
                          #      it will alternate true/false on each execution

       .sort_by { |s| s[/[A-Z]/][0] } # sort by the first alphabetical char

  # use counters for less chars than `each_with_index`
  # x and y are cartesian coordinates in the final array

  x = 0 # start in the left-hand column

  # go through each title
  t.map { |t|
    y = 0 # each book title starts on the top row

    u = p # `u` is "have we reached the book's spine yet?" (or are we above it?)
          # `u` starts off false and we'll set it true when we see the first '_'
          # after which we'll start writing the book's edges

    # go through each character of each title, including leading spaces and '_'s
    # this will "descend" down the array writing each letter of the title
    # along with the "edges"
    t.chars { |c|

      u &&                  # if we're on the spine
        a[y][x,3] = ?|*3;   # write ||| in the next 3 columns
                            # the middle | will be overwriten by the title char

      a[y][x+1] = c; # write the current title char into the second (x+1) column

      y+=1; # descend to the next row

      u |= c == '_' # Since '_' is the top and bottom of the book,
                    # this toggles whether we're on the spine
    }
    x += 2 # jump to the right 2 columns and start on the next title
  }
  a.join $/ # hopefully this is obvious
end

```
> 6 votes

# Answer
# Python 2 - 399 bytes

Expects the input to not have a trailing newline.

```
import sys;a=str.strip;L=list(sys.stdin);b=len(L[-1])/2;s=['']*b
for l in L:
    i=0
    for c in l[1:-1:2]:s[i]+=c;i+=1
s=sorted([a(a(x),'_')for x in s],key=a);y=map(len,s);m=[y[0]]+[max(y[i],y[i+1])for i in range(b-1)]
for i in range(max(y)+1):
    h=max(y)-i;l='';j=0
    for x in s:l+='|'if h<m[j]else' ';l+='_' if h==len(x)else' 'if h>len(x)else x[-h-1];j+=1
    print l+('|'if h<y[-1]else' ')
print'|_'*b+'|'

```
> 5 votes

# Answer
# CJam, ~~75~~ ~~66~~ 65 bytes

```
qN/z(;2%{_{" _"#W=}#>}$es:P;_W>+{_'_#_Pe<)S*2$,'|*.e<@@:P;}%);zN*

```

This expects input padded with spaces to form a rectangle.

Try it online

Thanks to @Sp3000 and @Dennis for suggestions on string trimming on chat, as well as clueing me in that the `$` operator can take a block as an argument.

I'm still not entirely happy with the second loop. But after trying a few other options without better success, I'm getting tired.

Explanation:

```
qN/     Read input and split at newlines.
z       Transpose to turn columns into lines.
(;      Drop first line...
2%      ... and every second line after that, to keep only lines with titles.
{       Start block that maps lines for sort.
  _       Copy.
  {       Start block for matching first title letter.
    " _"#   Search for character in " _".
    W=      True if not found.
  }#      End match block. This gets position of first character not in " _".
  >       Trim leading spaces and '_.
}$      End of sort block. Lines are now sorted alphabetically by title.
es:P;   Store large number in P. P holds previous position of '_ in following loop.
_W>+    Repeat last title line, so that final separator line is generated.
{       Loop over title lines.
  _'_#    Find position of '_.
  _       Copy position. Will store it in P after the minimum has been determined.
  P       Get position of '_ in previous line.
  e<)     Take the smaller of the two '_ positions, and decrement.
  S*      Generate leading spaces from the count.
  2$,     Get length of title line.
  '|*     Generate full line length sequence of '|.
  .e<     Overlap spaces with '| to give the final separator.
  @@      Get '_ position to top, and stack in order for next loop iteration.
  :P;     Store '_ position in P.
}%      End of loop over lines.
);      Remove last line, which was a repeat.
z       Transpose to turn lines into columns again.
N*      Join with newline characters.

```
> 5 votes

# Answer
# Scala ~~359~~ 341 bytes

expects all lines to be of the same length (i.e. padded with spaces)

```
(s:String)=>{def f(s:String)=(" "/:s)((r,c)=>if(r.last=='|'||c=='_')r+"|"else r+" ").init;val h=s.lines.toSeq.transpose.collect{case s if s.exists(_.isLetter)=>s.mkString}.sortBy(_.filter(!_.isWhitespace));((Seq(f(h(0)))/:h.sliding(2))((s,l)=>s:+l(0):+f(l.minBy(_.indexOf('_')))):+h.last:+f(h.last)).transpose.map(_.mkString).mkString("\n")}

```

ungolfed & commented:

```
//anonymous method that takes the books ascii-art string
(s: String) => {

  //method to convert the middle to a border
  def f(s: String) =
    //fold (starting from non empty string since we use `.last`)
    (" "/:s)((r,c) =>
      if(r.last=='|'||c=='_')r+"|"
      else r+" "
    ).init.tail

  //h is a sequence of strings of the middle of the books
  val h =
    //transpose lines of input string, and take only the lines the contains letters (middle of the books)
    s.lines.toSeq.transpose.collect{
      case s if s.exists(_.isLetter) =>
        s.mkString
    }.sortBy(_.filter(!_.isWhitespace)) //sort the books by title (actually by "_$title" since we filter out just whitspaces)

  //fold over pairs of books and add the last manually
  (
    (Seq(f(h(0)))/:h.sliding(2))((s,l) =>
      s :+ l(0) :+ f(l.minBy(_.indexOf('_'))) //convert higher book to border and append to folded accumulator
    ) :+ h.last :+ f(h.last) //add last book manually
  ).transpose.map(_.mkString).mkString("\n") //transpose back and construct the output string
}

```
> 1 votes

---
Tags: code-golf, ascii-art, sorting
---


title: join lists by common elements

text:
# Question
Title: join lists by common elements
You have N lists

```
A = [5, 6, 10, 15]
B = [3, 0, 7, 4]
C = [49, 59, 29]
D = [19, 29, 39]
E = [9, 15, 3, 10]

```

You have to combine them such that: Two lists which have a common elements they should be next to each other. In this case answer is:

```
A,E,B,C,D
[5, 6, 10, 15, 9, 3, 0, 7, 4, 49, 59, 29, 19, 39]

```

**E** comes after **A** as they have 2 common elements. After **E** the **B** comes as they have common elements. **B** do not have common elements with **C** or **D** so anything can come (**C** or **D**), lets say **C** comes. Now **C** should be followed by **D** as they have common elements.

**Note:** This is also acceptable solution

```
B,E,A,C,D
C,D,A,E,B
....

```

Thus the main condition is if two lists have common elements they should be next to each other.

**Note 2:** For simplicity we assume a list can have common elements with maximum 2 other lists. However there can be list which have no common elements with any other list.

**Note 3:** Output format : preferably both, the name of list and the number sequence.

# Answer
# CJam, ~~47~~ 44 bytes

```
q~]e!{_2ew[{~_,@@\-,-}/]:+_W>{:W;:L}&}/];L:p

```

Explanation:

```
                                             e# L = [], W = -1
q~                                           e# Evaluate input
  ]                                          e# Wrap in array
   e!                                        e# Push all unique permutations
     {                               }/      e# For each permutation:
      _2ew                                   e#   Push all overlapping slices of length 2
           {         }/                      e#   For each slice:
            ~_,@@\-,-                        e#     Push number of common elements
          [            ]:+                   e#   Sum the number of common elements from all the slices
                          _W>{     }&        e#   If sum > W:
                              :W;            e#     Assign sum to W and pop off the stack
                                 :L          e#     Assign the permutation to L
                                       ];    e# Clear the stack
                                         L:p e# Print each list in L

```

Try it online.
> 1 votes

---
Tags: code-golf, combinatorics
---


title: Non-repeating random numbers

text:
# Question
Title: Non-repeating random numbers
Find the shortest way to generate a random number between 0-9 without repeating the last generated number. Here is an example written in javascript.

```
var n=t=0;
while(n==t){
  t=Math.floor(Math.random()*9);
}
n=t;

```

I don't know if it is possible, but it would be interesting if there is a solution using only one variable.

To clarify the solution can be in any language. Based on the comments I am going to disallow using arrays since apparently that makes it very easy and this is code-golf so the shortest answer wins.

# Answer
> 9 votes
# Pyth, 7 bytes

```
e=+ZhO9

```

Try it online: Demonstration

### Explanation

```
          implicit: Z = 0
     O9   Generate a random int from [0, 1, ..., 8]
    h     add 1
 =+Z      add this to Z and update Z
e         print Z modulo 10

```

# Answer
> 5 votes
# CJam, ~~10~~ 8 bytes

Thanks @Dennis for a 2 bytes golf!

You can repeat this piece of code how many times you want.

```
A,W-mR:W

```

Explanation:

```
         e# At startup, W = -1
A,       e# Push [0 ... 9]
  W-     e# Remove W from the list
    mR   e# Random choice from list
      :W e# Assign to W
         e# The number is left on the stack

```

Try it online.

# Answer
> 4 votes
# K5, 19 bytes

Not particularly clever:

```
t:-1;r:{t::*1?10^t}

```

Each time `r` is invoked, it picks 1 random number (`*1?`) from the set formed by taking the range 0-9 except (`^`) the previous random number and then stores the result in t (`t::`). We initialize t (`t:-1;`) such that the first result can be any digit 0-9.

The definition of `r` is purely for convenience in repeatedly invoking it, so you're really only using a single variable.

## edit:

Just for fun, here's a k5 program which will generate a sequence of N numbers containing no immediate repetitions (as in the above problem) without using *any* variables:

```
1_(*1?10^)\[;-1]

```

For example,

```
  1_(*1?10^)\[;-1]10
1 8 0 6 8 5 1 0 5 1
  1_(*1?10^)\[;-1]3
4 0 7

```

Doesn't work quite right in my K implementation, so I suppose writing this and discovering a bug was a decent use of my time!

# Answer
> 2 votes
# Java, 62 bytes

```
int a(int p){p+=9*(p+Math.random());return p%10==p/10?9:p%10;}

```

This is a function. You call it with the previously returned value. Uses only the variable supplied.

# 2 variables, 59 bytes

```
int a(int p){int a=(int)(Math.random()*9);return a==p?9:a;}

```

# Answer
> 2 votes
# Julia - ~~25~~ 18 bytes

```
t=(rand(1:9)+t)%10

```

Or, for a slightly longer, iterative solution:

```
while t==(t=rand(0:9))end

```

No temporary second variable necessary.

# Answer
> 1 votes
# Python 2, 79 bytes

Here's a simple one you can repeatedly run in a REPL:

```
from random import*
try:p
except:p=n=0
while p==n:n=int(random()*9)
print n
p=n

```

# Answer
> 1 votes
# Octave, 24 bytes

Here's an anonymous function using one variable (plus the function handle):

```
r=@(n)mod(randi(9)+n,10)

```

Sample run:

```
>> n=5;
>> n=r(n)
n =  2

```

# Answer
> 1 votes
**Java 8, 89 bytes**

As an IntStream...

```
// Int Stream (89 bytes)
IntStream.iterate(0,(o)->new Random().ints(0,10).filter(x->x!=o).findFirst().getAsInt());

```

Minimal usage...

```
// Usage (119 bytes)
IntStream.iterate(0,(o)->new Random().ints(0,10).filter(x->x!=o).findFirst().getAsInt()).forEach(System.out::println);

```

# Answer
> 0 votes
# Javascript, 39 bytes

Not the most exciting answer, but it is in Javascript.

```
t=-1;while(t==(t=(Math.random()*9)|0));

```

To test it:

```
//set the value here, or it will produce repeated numbers:
t=-1;
for(var i=0; i < 10; i++){
    //generate a new random number, using the code in the answer
    while(t==(t=(Math.random()*9)|0));

    document.write(t + '<br>');
}
```

# Answer
> 0 votes
# Python 3, ~~42~~ 33 bytes

If your criteria for "random" is generating a number 0-9,

> \[...\] without repeating the last generated number.

Something like this would work:

```
i=(i+1)%10if"i"in globals()else 0

```

---
Tags: code-golf
---


title: Counting Pages of a Book

text:
# Question
Title: Counting Pages of a Book
# Task

Given the page of a book **P** on stdin, count all occurrences of the digits 0-9 in each member of the range 1 to **P**. There is no page zero and your program should handle any number less than 1,000,000. Since putting a constraint on how you can do it is difficult to explain there will be a time limit of 3 seconds instead. That may be too short for some of the answers already submitted but mine runs faster than that so it is possible.

# Examples (plus a list of the occurences):

```
input: 10

0 = 1  (10)
1 = 2  (1, 10)
2 = 1  (2)
3 = 1  (3)
4 = 1  (4)
5 = 1  (5)
6 = 1  (6)
7 = 1  (7)
8 = 1  (8)
9 = 1  (9)

```

```
input: 20

0 = 2  (10, 20)
1 = 11 (1, 10, 11 ... 18, 19)
2 = 3  (2, 12, 20)
3 = 2  (3, 13)
4 = 2  (4, 14)
5 = 2  (5, 15)
6 = 2  (6, 16)
7 = 2  (7, 17)
9 = 2  (8, 18)

```

# Answer
> 4 votes
## Matlab, 43 bytes

```
y=hist(+num2str(1:input('')),47:57);y(2:11)

```

Example:

```
>> y=hist(+num2str(1:input('')),47:57);y(2:11)
10
ans =
     1     2     1     1     1     1     1     1     1     1

```

**How it works:**

`1:input('')` generates a vector of numbers from 1 to the input number.

`num2str` converts all those numbers to a space-separated string (char array).

The `+` converts from char to ASCII codes. Digits are 48 to 57 in ASCII.

`hist` counts how many times each of those ASCII codes appears. Actually the count for value 47 is necessary too, because `hist` collects all lower values in the first bin. So that 47 just intercepts all spaces and prevents them from being confused as zeroes.

Lastly, `y(2:11)` removes that first count and prints the result.

# Answer
> 3 votes
# CJam, ~~18~~ ~~14~~ 10 bytes

*Thanks @Dennis for a 4 bytes golf.*

```
qi,:)s$e`p

```

Try it online.

# Explanation

```
qi         e# Convert input to integer
  ,:)      e# Push [1 ... input]
     s     e# Convert to string (concats all numbers)
      $    e# Sort the string
       e`  e# Run-length encode
         p e# Print

```

# Answer
> 2 votes
# K5, 43 bytes (27 without fancy output formatting)

```
`0:"\n"/($!10){x," = ",$#&y=*x}\:,/$1+!.0:`

```

Without formatting:

```
($!10){#&y=*x}\:,/$1+!. 0:`

```

Might not handle all numbers up to `1e9`...(well, it could, with lots of memory).

Also, it's the same core algorithm as the Matlab answer. Ironically enough, I wrote this earlier this morning (before the Matlab answer), but then got distracted by Sonic 06 videos and forgot to post it... :(

Still cool.

---
Tags: code-golf
---


title: Binary Stream With Unknown Byte-Width

text:
# Question
Title: Binary Stream With Unknown Byte-Width
**Context:**

> You are a cryptographer. You have stumbled upon a mysterious group of individuals, who present you with a challenge, which you must solve in order to join their secret society.

**Description:**

> You have been given a binary stream consisting of 3 byte sequences that have a random width (unchanging per-stream). This stream has the following properties:
>
> 1. The first two bytes in a sequence are randomly generated unsigned binary numbers.
> 2. The third byte is the sum of the first two bytes.
> 3. If the sum overflows, the carry-bit disappears (That is, it does not affect the first 2 bytes).
> 4. The bytes are big-endian.
> 5. The byte-width will always be between 3 and 16.

**Examples of potential streams**:

> A stream is an infinite series of 3 byte sequences, where the first 2 bytes are randomly generated for each sequence in the series.
>
> Byte-width = 5: 01001 01010 10011 10010 11101 01111 ... is a valid stream (without spaces, of course). 01001 + 01010 = 10011, and 10010 + 11101 = 01111 (after integer overflow).
>
> Byte-width = 10: 1100110011 0101010101 0010001000 ... is a valid stream. 1100110011 + 0101010101 = 0010001000 (after overflow).

**The Rules:**

> Write a program that consumes the binary stream, and outputs (with 100% certainty) the byte-width. This puzzle has two parts, efficiency and code-golf.
>
> Efficiency: Your score in this section is determined by the average number of bits your program must consume to make it's determination (after N\>=1000 runs).
>
> Golf: Your score in this section is determined by the number of characters used in your code. This number does not include the scaffolding to generate the stream, includes/imports, or boilerplate. For example, in C/C++: int main(){ ONLY\_THIS\_COUNTS }.
>
> Your final score is equal to the multiplication of your scores in both sections. The lowest score wins.

# Answer
# Haskell 59.5 * 228 = 13566

```
import Data.List
import Data.List.Split
import Prelude.Unicode
import System.Random

findBW strm
 | i == 0    = (16, rest)
 | i < 3     = findBW rest
 | otherwise = (i, rest)

 where
 (bw,rest) = splitAt 4 strm
 i = sum $ zipWith ((*).(2^)) [0..] bw

mkStream i strm = first ++ second ++ sum ++ mkStream i rest
 where
 (first,tmp) = splitAt i strm
 (second,rest) = splitAt i tmp
 sum = reverse $ g (reverse first) (reverse second) 0

run 100000 reps _ = print $ (reps*16*3) / 100000
run n reps gen = do
 p validstream
 run (n+1) (reps+rep) gen2

 where
 (gen1,gen2) = System.Random.split gen
 (bytewidth, rndstream) = findBW $ randomRs (0::Int,1) gen1
 validstream = mkStream bytewidth rndstream
 rep = fst $ until(\(_,t)->sum[1|x<-h#t,x]<2)(\(n,s)->(n+1,tail#s))(1,f validstream)

main = do
 gen <- getStdGen
 run 0 0 gen

r=reverse
(#)=map
h=head
g[]_ _=[]
g(a:b)(c:d)e=mod(a+c+e)2:g b d(div(a+c+e)2)
c(m:n:o:p)=(g(r m)(r n)0≡r o):c p
f s=(scanl1(∧).c.(`chunksOf`s))#[3..16]
p=print.(3+).h.elemIndices True .(h#).until(\t->sum[1|x<-h#t,x]<2)(tail#).f

```

The average bits consumed in a run on 100,000 streams are around 59.3x / 59.4x , so I take 59.5 as the multiplier. For the golf part I count the characters of function `p` and it's helper functions, i.e. all characters beginning with `r=reverse` to the end. `p` is the function that analyses a bit stream and prints the byte-width. Note: there are some unicode characters, all counting 1.

How it works: split the bit stream in chunks of 3 bits, 4 bits, ... 16 bits and check for validity. Repeat taking 3 of the chunks for every size until there's only one valid set. That means I consume 3\*16 = 48 bits per repetition. Most of the time one ore two repetitions are enough.
> 2 votes

---
Tags: code-challenge
---


# Question
Title: Find the largest independent set in a high-dimensional lattice-like graph
For a given positive integer `n`, consider all binary strings of length `2n-1`. For a given string `S`, let `L` be an array of length `n` which contains the count of the number of `1`s in each substring of length `n` of `S`. For example, if `n=3` and `S = 01010` then `L=[1,2,1]`. We call `L` the counting array of `S`.

We say that two strings `S1` and `S2` of the same length *match* if their respective counting arrays `L1` and `L2` have the property that `L1[i] <= 2*L2[i]` and `L2[i] <= 2*L1[i]` for all `i`.

**Task**

For increasing `n` starting at `n=1`, the task is to find the size of the largest set of strings, each of length `2n-1` so that no two strings match.

Your code should output one number per value of `n`.

**Score**

Your score is the highest `n` for which no one else has posted a higher correct answer for any of your answers. Clearly if you have all optimum answers then you will get the score for the highest `n` you post. However, even if your answer is not the optimum, you can still get the score if no one else can beat it.

**Example answers**

For `n=1,2,3,4` I get `2,4,10,16`.

**Languages and libraries**

You can use any available language and libraries you like. Where feasible, it would be good to be able to run your code so please include a full explanation for how to run/compile your code in linux if at all possible.

**Leading entries**

* **5** by Martin Büttner in **Mathematica**
* **6** by Reto Koradi in **C++**. Values are `2, 4, 10, 16, 31, 47, 75, 111, 164, 232, 328, 445, 606, 814, 1086`. The first 5 are known to be optimal.
* **7** by Peter Taylor in **Java**. Values are `2, 4, 10, 16, 31, 47, 76, 111, 166, 235`.
* **9** by joriki in **Java**. Values are `2, 4, 10, 16, 31, 47, 76, 112, 168`.

# Answer
# 2, 4, 10, 16, 31, 47, 76, 112, 168

For each n, this Java code determines the possible counting arrays and then finds non-matching sets of increasing size, for each size starting with a random set and improving it by randomized steepest descent. In each step, one of the elements of the set is randomly uniformly selected and replaced by another counting array randomly uniformly selected among the ones not in use. The step is accepted if it does not increase the number of matches. This latter prescription appears to be crucial; accepting steps only if they reduce the number of matches isn't nearly as effective. The steps leaving the number of matches invariant allow the search space to be explored, and eventually some space may open up to avoid one of the matches. After 2^24 steps without improvement, the previous size is output for the present value of n, and n is incremented.

The results up to n = 9 are `2, 4, 10, 16, 31, 47, 76, 112, 168`, improving on the previous results for n = 8 by one and for n = 9 by two. For higher values of n, the limit of 2^24 steps may have to be increased.

I also tried simulated annealing (with the number of matches as the energy), but without improvement over steepest descent.

### Code

save as `Question54354.java`
compile with `javac Question54354.java`
run with `java Question54354`

```
import java.util.Arrays;
import java.util.HashSet;
import java.util.Random;
import java.util.Set;

public class Question54354 {
    static class Array {
        int [] arr;

        public Array (int [] arr) {
            this.arr = arr;
        }

        public int hashCode () {
            return Arrays.hashCode (arr);
        }

        public boolean equals (Object o) {
            return Arrays.equals (((Array) o).arr,arr);
        }
    }

    static int [] indices;
    static int [] [] counts;
    static boolean [] used;

    static Random random = new Random (0);

    static boolean match (int [] c1,int [] c2) {
        for (int k = 0;k < c1.length;k++)
            if (c1 [k] > 2 * c2 [k] || c2 [k] > 2 * c1 [k])
                return false;
        return true;
    }

    static int matches (int i) {
        int result = 0;
        for (int j = 0;j < indices.length;j++)
            if (j != i && match (counts [indices [i]],counts [indices [j]]))
                result++;
        return result;
    }

    static void randomize (int i) {
        do
            indices [i] = random.nextInt (counts.length);
        while (used [indices [i]]);
    }

    public static void main (String [] args) {
        for (int n = 1,length = 1;;n++,length += 2) {
            int [] lookup = new int [1 << n];
            for (int string = 0;string < 1 << n;string++)
                for (int bit = 1;bit < 1 << n;bit <<= 1)
                    if ((string & bit) != 0)
                        lookup [string]++;
            Set<Array> arrays = new HashSet<Array> ();
            for (int string = 0;string < 1 << length;string++) {
                int [] count = new int [n];
                for (int i = 0;i < n;i++)
                    count [i] = lookup [(string >> i) & ((1 << n) - 1)];
                arrays.add (new Array (count));
            }
            counts = new int [arrays.size ()] [];
            int j = 0;
            for (Array array : arrays)
                counts [j++] = array.arr;
            used = new boolean [counts.length];

            int m;
            outer:
            for (m = 1;m <= counts.length;m++) {
                indices = new int [m];
                for (;;) {
                    Arrays.fill (used,false);
                    for (int i = 0;i < m;i++) {
                        randomize (i);
                        used [indices [i]] = true;
                    }
                    int matches = 0;
                    for (int i = 0;i < m;i++)
                        matches += matches (i);
                    matches /= 2;
                    int stagnation = 0;
                    while (matches != 0) {
                        int k = random.nextInt (m);
                        int oldMatches = matches (k);
                        int oldIndex = indices [k];
                        randomize (k);
                        int newMatches = matches (k);
                        if (newMatches <= oldMatches) {
                            if (newMatches < oldMatches) {
                                matches += newMatches - oldMatches;
                                stagnation = 0;
                            }
                            used [oldIndex] = false;
                            used [indices [k]] = true;
                        }
                        else
                            indices [k] = oldIndex;

                        if (++stagnation == 0x1000000)
                            break outer;
                    }
                    break;
                }
            }
            System.out.println (n + " : " + (m - 1));
        }
    }
}

```
> 7 votes

# Answer
## 2, 4, 10, 16, 31, 47, 76, 111, 166, 235

### Notes

If we consider a graph `G` with vertices `0` to `n` and edges joining two numbers which match, then the tensor power `G^n` has vertices `(x_0, ..., x_{n-1})` forming the Cartesian power `{0, ..., n}^n` and edges between matching tuples. The graph of interest is the subgraph of `G^n` induced by those vertices which correspond to the possible "counting arrays".

So the first subtask is to generate those vertices. The naïve approach enumerates over `2^{2n-1}` strings, or on the order of `4^n`. But if we instead look at the array of first differences of the counting arrays we find that there are only `3^n` possibilities, and from the first differences we can deduce the range of possible initial values by requiring that no element in the zeroth differences is less than `0` or greater than `n`.

We then want to find the maximum independent set. I'm using one theorem and two heuristics:

* Theorem: the maximum independent set of a disjoint union of graphs is the union of their maximum independent sets. So if we break a graph down into unconnected components we can simplify the problem.
* Heuristic: assume that `(n, n, ..., n)` will be in a maximum independent set. There's a fairly large clique of vertices `{m, m+1, ..., n}^n` where `m` is the smallest integer which matches `n`; `(n, n, ..., n)` is guaranteed to have no matches outside that clique.
* Heuristic: take the greedy approach of selecting the vertex of lowest degree.

On my computer this finds `111` for `n=8` in 16 seconds, `166` for `n=9` in about 8 minutes, and `235` for `n=10` in about 2 hours.

### Code

Save as `PPCG54354.java`, compile as `javac PPCG54354.java`, and run as `java PPCG54354`.

```
import java.util.*;

public class PPCG54354 {
    public static void main(String[] args) {
        for (int n = 1; n < 20; n++) {
            long start = System.nanoTime();

            Set<Vertex> constructive = new HashSet<Vertex>();
            for (int i = 0; i < (int)Math.pow(3, n-1); i++) {
                int min = 0, max = 1, diffs[] = new int[n-1];
                for (int j = i, k = 0; k < n-1; j /= 3, k++) {
                    int delta = (j % 3) - 1;
                    if (delta == -1) min++;
                    if (delta != 1) max++;
                    diffs[k] = delta;
                }

                for (; min <= max; min++) constructive.add(new Vertex(min, diffs));
            }

            // Heuristic: favour (n, n, ..., n)
            Vertex max = new Vertex(n, new int[n-1]);
            Iterator<Vertex> it = constructive.iterator();
            while (it.hasNext()) {
                Vertex v = it.next();
                if (v.matches(max) && !v.equals(max)) it.remove();
            }

            Set<Vertex> ind = independentSet(constructive, n);
            System.out.println(ind.size() + " after " + ((System.nanoTime() - start) / 1000000000L) + " secs");
        }
    }

    private static Set<Vertex> independentSet(Set<Vertex> vertices, int dim) {
        if (vertices.size() < 2) return vertices;

        for (int idx = 0; idx < dim; idx++) {
            Set<Set<Vertex>> p = connectedComponents(vertices, idx);
            if (p.size() > 1) {
                Set<Vertex> ind = new HashSet<Vertex>();
                for (Set<Vertex> part : connectedComponents(vertices, idx)) {
                    ind.addAll(independentSet(part, dim));
                }
                return ind;
            }
        }

        // Greedy
        int minMatches = Integer.MAX_VALUE;
        Vertex minV = null;
        for (Vertex v0 : vertices) {
            int numMatches = 0;
            for (Vertex vi : vertices) if (v0.matches(vi)) numMatches++;
            if (numMatches < minMatches) {
                minMatches = numMatches;
                minV = v0;
            }
        }

        Set<Vertex> nonmatch = new HashSet<Vertex>();
        for (Vertex vi : vertices) if (!minV.matches(vi)) nonmatch.add(vi);
        Set<Vertex> ind = independentSet(nonmatch, dim);
        ind.add(minV);
        return ind;
    }

    // Separates out a set of vertices which form connected components when projected into the idx axis.
    private static Set<Set<Vertex>> connectedComponents(Set<Vertex> vertices, final int idx) {
        List<Vertex> sorted = new ArrayList<Vertex>(vertices);
        Collections.sort(sorted, new Comparator<Vertex>() {
                public int compare(Vertex a, Vertex b) {
                    return a.x[idx] - b.x[idx];
                }
            });

        Set<Set<Vertex>> connectedComponents = new HashSet<Set<Vertex>>();
        Set<Vertex> current = new HashSet<Vertex>();
        int currentVal = 0;
        for (Vertex v : sorted) {
            if (!match(currentVal, v.x[idx]) && !current.isEmpty()) {
                connectedComponents.add(current);
                current = new HashSet<Vertex>();
            }

            current.add(v);
            currentVal = v.x[idx];
        }

        if (!current.isEmpty()) connectedComponents.add(current);
        return connectedComponents;
    }

    private static boolean match(int a, int b) {
        return a <= 2 * b && b <= 2 * a;
    }

    private static class Vertex {
        final int[] x;
        private final int h;

        Vertex(int[] x) {
            this.x = x.clone();

            int _h = 0;
            for (int xi : x) _h = _h * 37 + xi;
            h = _h;
        }

        Vertex(int x0, int[] diffs) {
            x = new int[diffs.length + 1];
            x[0] = x0;
            for (int i = 0; i < diffs.length; i++) x[i+1] = x[i] + diffs[i];

            int _h = 0;
            for (int xi : x) _h = _h * 37 + xi;
            h = _h;
        }

        public boolean matches(Vertex v) {
            if (v == this) return true;
            if (x.length != v.x.length) throw new IllegalArgumentException("v");
            for (int i = 0; i < x.length; i++) {
                if (!match(x[i], v.x[i])) return false;
            }
            return true;
        }

        @Override
        public int hashCode() {
            return h;
        }

        @Override
        public boolean equals(Object obj) {
            return (obj instanceof Vertex) && equals((Vertex)obj);
        }

        public boolean equals(Vertex v) {
            if (v == this) return true;
            if (x.length != v.x.length) return false;
            for (int i = 0; i < x.length; i++) {
                if (x[i] != v.x[i]) return false;
            }
            return true;
        }

        @Override
        public String toString() {
            if (x.length == 0) return "e";

            StringBuilder sb = new StringBuilder(x.length);
            for (int xi : x) sb.append(xi < 10 ? (char)('0' + xi) : (char)('A' + xi - 10));
            return sb.toString();
        }
    }
}

```
> 11 votes

# Answer
# Mathematica, `n = 5`, 31 strings

I just wrote a brute force solution using Mathematica's built-ins to verify Lembik's example answers, but it can handle `n = 5` as well:

```
n = 5;
s = Tuples[{0, 1}, 2 n - 1];
l = Total /@ Partition[#, n, 1] & /@ s
g = Graph[l,
  Cases[Join @@ Outer[UndirectedEdge, l, l, 1],
   a_ <-> b_ /;
    a != b && And @@ Thread[a <= 2 b] && And @@ Thread[b <= 2 a]]]
set = First@FindIndependentVertexSet[g]
Length@set

```

As a bonus, this code produces a visualisation of the problem as a graph where each edge indicates two matching strings.

Here is the graph for `n = 3`:
> 10 votes

# Answer
# C++ (heuristic): 2, 4, 10, 16, 31, 47, 75, 111, 164, 232, 328, 445, 606, 814, 1086

This is slightly behind Peter Taylor's result, being 1 to 3 lower for `n=7`, `9` and `10`. The advantage is that it's much faster, so I can run it for higher values of `n`. And it can be understood without any fancy math. ;)

The current code is dimensioned to run up to `n=15`. Run times increase roughly by a factor of 4 for each increase in `n`. For example, it was 0.008 second for `n=7`, 0.07 seconds for `n=9`, 1.34 seconds for `n=11`, 27 seconds for `n=13`, and 9 minutes for `n=15`.

There are two key observations I used:

* Instead of operating on the values themselves, the heuristic operates on counting arrays. To do this, a list of all unique counting arrays is generated first.
* Using counting arrays with small values is more beneficial, since they eliminate less of the solution space. This is based on each count `c` excluding the range of `c / 2` to `2 * c` from other values. For smaller values of `c`, this range is smaller, which means that fewer values are excluded by using it.

### Generate Unique Counting Arrays

I went brute force on this one, iterating through all values, generating the count array for each of them, and uniquifying the resulting list. This could certainly be done more efficiently, but it is good enough for the kinds of values we're operating with.

This is extremely quick for the small values. For the larger values, the overhead does become substantial. For example, for `n=15`, it uses about 75% of the whole runtime. This would definitely be an area to look at when trying to go much higher than `n=15`. Even just the memory usage for building a list of the counting arrays for all values would start to become problematic.

The number of unique counting arrays is about 6% of the number of values for `n=15`. This relative count becomes smaller as `n` becomes larger.

### Greedy Selection of Counting Array Values

The main part of the algorithm selects counting array values from the generated list using a simple greedy approach.

Based on the theory that using counting arrays with small counts is beneficial, the counting arrays are sorted by the sum of their counts.

They are then checked in order, and a value is selected if it is compatible with all previously used values. So this involves one single linear pass through the unique counting arrays, where each candidate is compared to the values that were previously selected.

I have some ideas on how the heuristic could potentially be improved. But this seemed like a reasonable starting point, and the results looked quite good.

### Code

This is not highly optimized. I had a more elaborate data structure at some point, but it would have needed more work to generalize it beyond `n=8`, and the difference in performance did not seem very substantial.

```
#include <cstdint>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <sstream>
#include <iostream>

typedef uint32_t Value;

class Counter {
public:
    static void setN(int n);

    Counter();
    Counter(Value val);

    bool operator==(const Counter& rhs) const;
    bool operator<(const Counter& rhs) const;

    bool collides(const Counter& other) const;

private:
    static const int FIELD_BITS = 4;
    static const uint64_t FIELD_MASK = 0x0f;

    static int m_n;
    static Value m_valMask;

    uint64_t fieldSum() const;

    uint64_t m_fields;
};

void Counter::setN(int n) {
    m_n = n;
    m_valMask = (static_cast<Value>(1) << n) - 1;
}

Counter::Counter()
  : m_fields(0) {
}

Counter::Counter(Value val) {
    m_fields = 0;
    for (int k = 0; k < m_n; ++k) {
        m_fields <<= FIELD_BITS;
        m_fields |= __builtin_popcount(val & m_valMask);
        val >>= 1;
    }
}

bool Counter::operator==(const Counter& rhs) const {
    return m_fields == rhs.m_fields;
}

bool Counter::operator<(const Counter& rhs) const {
    uint64_t lhsSum = fieldSum();
    uint64_t rhsSum = rhs.fieldSum();
    if (lhsSum < rhsSum) {
        return true;
    }
    if (lhsSum > rhsSum) {
        return false;
    }

    return m_fields < rhs.m_fields;
}

bool Counter::collides(const Counter& other) const {
    uint64_t fields1 = m_fields;
    uint64_t fields2 = other.m_fields;

    for (int k = 0; k < m_n; ++k) {
        uint64_t c1 = fields1 & FIELD_MASK;
        uint64_t c2 = fields2 & FIELD_MASK;

        if (c1 > 2 * c2 || c2 > 2 * c1) {
            return false;
        }

        fields1 >>= FIELD_BITS;
        fields2 >>= FIELD_BITS;
    }

    return true;
}

int Counter::m_n = 0;
Value Counter::m_valMask = 0;

uint64_t Counter::fieldSum() const {
    uint64_t fields = m_fields;
    uint64_t sum = 0;
    for (int k = 0; k < m_n; ++k) {
        sum += fields & FIELD_MASK;
        fields >>= FIELD_BITS;
    }

    return sum;
}

typedef std::vector<Counter> Counters;

int main(int argc, char* argv[]) {
    int n = 0;
    std::istringstream strm(argv[1]);
    strm >> n;

    Counter::setN(n);

    int nBit = 2 * n - 1;
    Value maxVal = static_cast<Value>(1) << nBit;

    Counters allCounters;

    for (Value val = 0; val < maxVal; ++val) {
        Counter counter(val);
        allCounters.push_back(counter);
    }

    std::sort(allCounters.begin(), allCounters.end());

    Counters::iterator uniqEnd =
        std::unique(allCounters.begin(), allCounters.end());
    allCounters.resize(std::distance(allCounters.begin(), uniqEnd));

    Counters solCounters;
    int nSol = 0;

    for (Value idx = 0; idx < allCounters.size(); ++idx) {
        const Counter& counter = allCounters[idx];

        bool valid = true;
        for (int iSol = 0; iSol < nSol; ++iSol) {
            if (solCounters[iSol].collides(counter)) {
                valid = false;
                break;
            }
        }

        if (valid) {
            solCounters.push_back(counter);
            ++nSol;
        }
    }

    std::cout << "result: " << nSol << std::endl;

    return 0;
}

```
> 3 votes

---
Tags: code-challenge, math, graph-theory, optimization
---


title: Build Me a Pyramid

text:
# Question
Title: Build Me a Pyramid
You need to build a pyramid from cubes. Cubes can be viewed from 2 angles:

```
  _____        _____
 /\    \      /    /\
/  \____\    /____/  \
\  /    /    \    \  /
 \/____/      \____\/

```

This is an example for 2-size cubes from the 2 possible angles. The height of the cubes is `$size` slashes (or back-slashes), and the width of the cube is `2 * $size` underscores. The top level width should contain an extra underscore character.

Input will be provided as a string containing a number (size of cubes), slash or backslash (to indicate direction/angle), and another number (height of the pyramid).

Examples:

Input:

```
1/1

```

Output:

```
 ___
/\__\
\/__/

```

Input:

```
1\1

```

Output:

```
 ___
/__/\
\__\/

```

Input:

```
2/1

```

Output:

```
  _____
 /\    \
/  \____\
\  /    /
 \/____/

```

Input:

```
1/2

```

Output:

```
     ___
 ___/\__\
/\__\/__/
\/__/\__\
    \/__/

```

Input:

```
2\2

```

Output:

```
  _____
 /    /\
/____/  \_____
\    \  /    /\
 \____\/____/  \
 /    /\    \  /
/____/  \____\/
\    \  /
 \____\/

```

Input:

```
1/3

```

Output:

```
         ___
     ___/\__\
 ___/\__\/__/
/\__\/__/\__\
\/__/\__\/__/
    \/__/\__\
        \/__/

```
* Trailing/leading whitespaces are OK.
* Standard loopholes are disallowed.
* You can assume input will always be valid.
* You may assume the input won't cause too big output, i.e: no line wrapping when the output is printed to the terminal.
* Size of cube & height of pyramid is positive (i.e. ≥ 1)
* This is code-golf, so shortest code in bytes wins.

# Current Winner is:

**Glen O** with 270 bytes in julia

challenge stays open. if you beat the current best, I'll update the accepted answer.

# Answer
> 3 votes
# Julia - ~~503~~ ~~455~~ ~~369~~ ~~346~~ ~~313~~ 270 bytes

```
f=A->(t=47∉A;h='/'+45t;(m,n)=int(split(A,h));W=2m*n+1;X=(l=3m+1)n+m+1;s=fill(' ',X,W);s[end,:]=10;for i=1:n,j=i:n,M=1:m s[M+i*l+[[L=[J=(2j-i)m,J,J-m]+M W-L]X.-[l,m,0] [0 m].+[1,m,m].+[J,J+m,J-m]X-l]]=[1,1,1]*[h 139-h 95 s[i*l,i*m-m+1]=95]end;print((t?s:flipud(s))...))

```

Ungolfed:

```
function f(A)
  t=47∉A      # Determine if '/' is in A ('/' = char(47))
  h='/'+45t   # Set h to the appropriate slash ('\\' = char(92), 92=47+45)
  (m,n)=int(split(A,h)) # Get the two integers from A
  W=2m*n+1    # Get number of rows of output (vertical height of pyramid)
  X=(l=3m+1)n+m+1 # Get columns of output + 1 (for newlines)
  s=fill(' ',X,W) # Create 'canvas' of size X x W
  s[end,:]=10 # Put newlines at end of each output row
  for i=1:n, j=i:n, M=1:m
    # This is where the fun happens.
    # K and L represent the shifting points for '/' and '\\' in the
    # horizontal and vertical directions.
    # They are used to make the code neater (and shorter).
    K=M+i*l-[l,m,0]
    L=[J,J,J-m]+M
    # The next two assign the slashes to appropriate places
    s[K+L*X]=h
    s[K+(W-L)X]=139-h
    # This one puts the first 2m underscores in each of the underscore sets
    s[M+i*l-l+[0 m].+[1,m,m].+[J,J+m,J-m]X]=95
    # This places the final underscores on the top edges (repeatedly)
    s[i*l,i*m-m+1]=95
  end
  # The above produces the array orientation for backslash, but uses
  # the "wrong" slashes along the diagonals if there's a forward slash.
  # This line flips the matrix in that case, before printing it.
  print((t?s:flipud(s))...))
end

```

Usage:

```
f("3/2")

```

or

```
f("2\\3")

```

# Answer
> 9 votes
# Perl, 343 bytes

```
$_=<>;$_=~/(\d+)(\S)(\d+)/;$v=$2eq'/';$w=$1*3+1;for$y(0..$1*2*$3){$k=$w*$3+$1-1;for$z(0..$k){$x=$v?$k-$z:$z;$q=($y+$1-1)/$1|0;$r=$x/$w|0;$d=$q+$r&1;$f=($y-1)%$1;$f=$1-$f-1if$d;$g=($x-$f)%$w;$u=$r;$q=2*$3-$q+1,$u++if$q>$3;print(($q>=$r&&$q&&$g==0)||($q>$r&&$g==$w-$1)?$d^$v?'/':'\\':$q>=$u&&$y%$1==0&&$g>0&&$g<($w-$1+($q==$r))?"_":$")}print$/}

```

Multiline with comments:

```
$_=<>;$_=~/(\d+)(\S)(\d+)/;$v=$2eq'/'; # read input
$w=$1*3+1; # compute width of each cube in chars
for$y(0..$1*2*$3){$k=$w*$3+$1-1;for$z(0..$k){ # iterate over rows, columns
    $x=$v?$k-$z:$z;   # flip x co-ordinate based on 2nd param
    $q=($y+$1-1)/$1|0;$r=$x/$w|0;   # parallelogram row and column index
    $d=$q+$r&1;  # flag parallelogram as left or right leaning
    $f=($y-1)%$1;$f=$1-$f-1if$d;  # compute a zig-zag offset
    $g=($x-$f)%$w;  # compute column position, offset by zig-zag
    $u=$r;$q=2*$3-$q+1,$u++if$q>$3; # vertical threshold for printing chars
    print(($q>=$r&&$q&&$g==0)||($q>$r&&$g==$w-$1)?$d^$v?'/':'\\': # output slash
    $q>=$u&&$y%$1==0&&$g>0&&$g<($w-$1+($q==$r))?"_":$") # underscore or space
}print$/}   # print out newline at end of row

```

Example output:

```
2/3
                _____
               /\    \
         _____/  \____\
        /\    \  /    /
  _____/  \____\/____/
 /\    \  /    /\    \
/  \____\/____/  \____\
\  /    /\    \  /    /
 \/____/  \____\/____/
       \  /    /\    \
        \/____/  \____\
              \  /    /
               \/____/

```

I also tried implementing it as a C function using the same algorithm, hoping to save bytes from the luxury of single-character variable names, but it ended up 15 bytes larger, at 358 bytes (needs to be compiled with `-std=c89` under gcc to leave off the `void` in the function header):

```
j(char*s){int c,p,v,x,y,k,z,u,g,w,r,d,q,f;char e;sscanf(s,"%d%c%d",&c,&e,&p);v=e=='/';w=c*3+1;for(y=0;y<=c*2*p;y++){k=w*p+c-1;for(z=0;z<=k;z++){x=v?k-z:z;q=(y+c-1)/c;r=x/w;d=q+r&1;f=(y+c-1)%c;if(d)f=c-f-1;g=(x-f)%w;u=r;if(q>p){q=2*p-q+1;u++;}printf("%c",(q>=r&&q&&g==0)||(q>r&&g==w-c)?d^v?'/':'\\':q>=u&&y%c==0&&g>0&&g<(w-c+(q==r))?'_':' ');}printf("\n");}}

```

# Answer
> 3 votes
# Ruby, 332

The only golfing done so far is elimination of comments and indents. I will golf later.

```
gets.match(/\D/)
d=$&<=>"@"
n=$`.to_i
m=2*n
p=$'.to_i
a=(0..h=4*n*p).map{' '*h*2}
(p*p).times{|j|
x=h-j/p*(3*n+1)*d
y=h/2+(j/p-j%p*2)*n
if j%p<=j/p
(-n).upto(n){|i|
a[y+i][i>0?x+m+1-i :x-m-i]=?/
a[y+i][i>0?x-m-1+i :x+m+i]='\\'
a[y+n][x+i]=a[y-n][x+i]=a[y][x-d*(n+i-1)]=?_
a[y+i+(i>>9&1)][x+d*i.abs]='\_/'[(0<=>i*d)+1]
}
end
}
puts a

```

I set up an array of spaces and poke the individual characters into it. There is quite a lot of overdrawing both of one cube on top of another (work from bottom to top) and within the cube itself, to avoid extra code. I make the pyramid by drawing a rhombus (similar to https://codegolf.stackexchange.com/a/54297/15599) and surpressing the top half.

The hard part was drawing the scalable cube. I started off with a perimeter hexagon with 2n+1 `_`characters on the horizontal sides. I also had had 2n+1 `/` and `\` ,so I had one too many, but by plotting the `_` last I overwrite them.

The internal lines are the only ones that are changed depending on the direction the cube is facing. I plot all the `/` and `\` with a single assignment. `abs` helps reverse the direction, and `i>>9&1` adds an extra 1 to the negative values of i, which lowers the top part down. for `i`=0 one of the required `_` is overplotted, so the selector string `'\_/'` contains all three symbols, selected according to the sign of `i`.

The whitespace around the output is ample but not excessive: 4\*p\*n high and 8\*p\*n wide (the latter is to enable the apex cube to always be in the centre of the output.) I understand "trailing / leading whitespaces" to include whole lines, but can revise if necessary.

**Ungolfed code**

```
gets.match(/\D/)                                   #find the symbol that is not a digit. it can be extracted from $&
d=$&<=>"@"                                         #direction, -1 or 1 depends if ascii code for symbol is before or after "@"
n=$`.to_i                                          #side length extracted from match variable $`
m=2*n
p=$'.to_i                                          #pyramid height extracted from match variable $'
a=(0..h=4*n*p).map{' '*h*2}                        #setup an array of h strings of h*2 spaces

(p*p).times{|j|                                    #iterate p**2 times
  x=h-j/p*(3*n+1)*d                                #calculate x and y coordinates for each cube, in a rhombus
  y=h/2+(j/p-j%p*2)*n                              #x extends outwards (and downwards) from the centre, y extends upwards

  if j%p<=j/p                                      #only print the bottom half of the rhombus, where cube y <= cube x
    (-n).upto(n){|i|                               #loop 2n+1 times, centred on the centre of the cube
      a[y+i][i>0?x+m+1-i :x-m-i]=?/                #put the / on the perimeter of the hexagon into the array
      a[y+i][i>0?x-m-1+i :x+m+i]='\\'              #and the \ also.
      a[y+n][x+i]=a[y-n][x+i]=a[y][x-d*(n+i-1)]=?_ #plot all three lines of _ overwriting the / and \ on the top line
      a[y+i+(i>>9&1)][x+d*i.abs]='\_/'[(0<=>i*d)+1]#plot the internal / and \ overwriting unwanted _
    }
  end
}
puts a

```

---
Tags: code-golf, ascii-art
---