title: Binary Recurrence Sequences

text:
# Question
Title: Binary Recurrence Sequences
A binary recurrence sequence is a recursively-defined sequence of the following form:

$$F(1) = a\_1 \\ \vdots \\ F(y) = a\_y \\ F(n) = \alpha F(n-x) + \beta F(n-y), n \> y$$

This is a generalization of the Fibonacci (\\$x = 1, y = 2, a = \[1, 1\], \alpha = 1, \beta = 1\\$) sequence and the Lucas (\\$x = 1, y = 2, a = \[2, 1\], \alpha = 1, \beta = 1\\$) sequence.

## The Challenge

Given \\$n, x, y, a, \alpha\\$, and \\$\beta\\$, in any reasonable format, output the \\$n\\$th term of the corresponding binary recurrence sequence.

## Rules

* You may choose for the sequence to be either 1-indexed or 0-indexed, but your choice must be consistent across all inputs, and you must make note of your choice in your answer.
* You may assume that no invalid inputs would be given (such as a sequence that terminates prior to \\$n\\$, or a sequence that references undefined terms, like \\$F(-1)\\$ or \\$F(k)\\$ where \\$k \> n\\$). As a result of this, \\$x\\$ and \\$y\\$ will always be positive.
* The inputs and outputs will always be integers, within the boundaries of your language's natural integer type. If your language has unbounded integers, the inputs and outputs will be within the range \\$\[-2^{31}, 2^{31}-1\]\\$ (i.e. the range for a 32-bit signed two's complement integer).
* \\$a\\$ will always contain exactly \\$y\\$ values (as per the definition).

## Test Cases

Note: all test cases are 0-indexed.

```
x = 1, y = 2, a = [1, 1], alpha = 1, beta = 1, n = 6 => 13
x = 1, y = 2, a = [2, 1], alpha = 1, beta = 1, n = 8 => 47
x = 3, y = 5, a = [2, 3, 5, 7, 11], alpha = 2, beta = 3, n = 8 => 53
x = 1, y = 3, a = [-5, 2, 3], alpha = 1, beta = 2, n = 10 => -67
x = 5, y = 7, a = [-5, 2, 3, -7, -8, 1, -9], alpha = -10, beta = -7, n = 10 => 39

```

# Answer
> 2 votes
# Jelly, 11 bytes

```
⁴Cịæ.⁵ṭµ¡⁶ị

```

**Try it online!**  |  |  |  |

### How it works

```
⁴Cịæ.⁵ṭµ¡⁶ị  Main link. Arguments: a; [x, y]; [α, β]; n (1-based)

       µ     Combine the links to the left into a chain.
        ¡    Execute that chain n times, updating a after each execution.
⁴              Yield [x, y].
 C             Complement; yield [1 - x, 1 - y].
  ị            Retrieve the elements of a at those indices.
               Indexing is 1-based and modular in Jelly, so this retrieves
               [a[-x], a[-y]] (Python syntax).
     ⁵         Yield [α, β].
   æ.          Take the dot product of [a[-x], a[-y]] and [α, β].
         ⁶   Yield n.
          ị  Retrieve the element of a at index n.

```

# Answer
> 2 votes
## JavaScript (ES6), ~~51~~ 44 bytes

```
(x,y,z,a,b)=>g=n=>n<y?z[n]:a*g(n-x)+b*g(n-y)

```

Note that the function is partially curried, e.g. `f(1,2,[1,1],1,1)(8)` returns 34. It would cost 2 bytes to make the intermediate functions independent of each other (currently only the last generated function works correctly).

Edit: Saved 7 bytes thanks to @Mego pointing out that I'd overlooked that the the passed-in array always contains the first `y` elements of the result.

# Answer
> 2 votes
## Python 2, 62 bytes

```
x,y,l,a,b=input();f=lambda n:l[n]if n<y else a*f(n-x)+b*f(n-y)

```

A direct recursive solution. All inputs are taken from STDIN except for `n` as a function argument, a split that's is allowed by default (though contentiously).

There doesn't seem to be a way to save bytes with `and/or` in place of `if/else` because `l[n]` could be falsey as 0.

# Answer
> 2 votes
## Haskell, ~~54~~ 48 bytes

```
l@(x,y,a,p,q)%n|n<y=a!!n|k<-(n-)=p*l%k x+q*l%k y

```

# Answer
> 1 votes
# Python 2, 59 bytes

```
x,y,A,a,b,n=input()
exec'A+=a*A[-x]+b*A[-y],;'*n
print A[n]

```

Test it on Ideone.

# Answer
> 0 votes
# J, 43 bytes

```
{:{](],(2>@{[)+/ .*]{~1-@>@{[)^:(3>@{[)>@{.

```

Given an initial sequence of terms *A*, computes the next term *n* times using the parameters of *x*, *y*, *α*, and *β*. Afterwards, it selects the *nth* term in the extended sequence and outputs it as the result.

## Usage

Since J only supports 1 or 2 arguments, I group up all the parameters as a list of boxed lists. The initial seed values *A* are first, followed by the parameters of *x* and *y* as a list, followed by the parameters of *α* and *β* as a list, and ending with the value *n*.

```
   f =: {:{](],(2>@{[)+/ .*]{~1-@>@{[)^:(3>@{[)>@{.
   2 3 5 7 11;3 5;2 3;8
┌──────────┬───┬───┬─┐
│2 3 5 7 11│3 5│2 3│8│
└──────────┴───┴───┴─┘
   f 2 3 5 7 11;3 5;2 3;8
53
   f _5 2 3 _7 _8 1 _9;5 7;_10 _7;10
39

```

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


title: Visualize a Difference Pyramid

text:
# Question
Title: Visualize a Difference Pyramid
A difference pyramid is a pyramid where each new diagonal is the absolute value of the differences between the elements of the last diagonal. For example, if we start with the array

```
2 5 4 9 3 4

```

Now, we arrange these in a diagonal column:

```
     2
      5
       4
        9
         3
          4

```

Now, we fill in the next diagonal. The absolute differences between the consecutive elements of this array are:

```
3 1 5 6 1

```

So that is our next diagonal.

```
     2
    3 5
     1 4
      5 9
       6 3
        1 4

```

Repeat until the pyramid is filled in:

```
     2
    3 5
   2 1 4
  2 4 5 9
 1 3 1 6 3
0 1 4 5 1 4

```

# The Challenge

Given a list of positive integers in the range `[0, 9]`, generate this ASCII-art representation of the difference pyramid for that particular array. The input is guaranteed to contain at least two elements. You may take these numbers in any reasonable format. (Array/list/whatever you call it, a string, command line arguments, etc.) Trailing spaces on each line and up to one trailing newline are allowed.

# Test IO

```
[1, 2, 3, 4, 5, 6, 7, 8, 9]

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

[4, 7]

 4
3 7

[3, 3, 3]

  3
 0 3
0 0 3

[1, 3, 6, 3, 4, 9]

     1
    2 3
   1 3 6
  1 0 3 3
 1 2 2 1 4
1 0 2 4 5 9

[8, 7, 3, 2, 4, 5, 9, 1, 6]

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

```

As usual, this is code-golf, so standard loopholes apply, and shortest answer in bytes wins!

---

*Inspired by this OEIS and this conjecture.*

# Answer
# Jelly, 16 bytes

```
IA$ṖÐ¿UṚz”@ṚGḟ”@

```

Try it online!

### Background

Generating the differences is quite straightforward. For input

```
[1, 2, 3, 4, 5, 6, 7, 8, 9]

```

`IA$ṖÐ¿` (absolute value of increments while there is more than one element) yields the following ragged 2D array.

```
[1, 2, 3, 4, 5, 6, 7, 8, 9]
[1, 1, 1, 1, 1, 1, 1, 1]
[0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0]
[0, 0, 0, 0]
[0, 0, 0]
[0, 0]
[0]

```

`U` reverses the order of the columns and  the order of the rows, yielding the following.

```
[0]
[0, 0]
[0, 0, 0]
[0, 0, 0, 0]
[0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0]
[1, 1, 1, 1, 1, 1, 1, 1]
[9, 8, 7, 6, 5, 4, 3, 2, 1]

```

Now, we transpose rows and columns with `z”@`, which pads all rows to the same length before transposing. The result is the following.

```
[0, 0, 0, 0, 0, 0, 0, 1, 9]
[@, 0, 0, 0, 0, 0, 0, 1, 8]
[@, @, 0, 0, 0, 0, 0, 1, 7]
[@, @, @, 0, 0, 0, 0, 1, 6]
[@, @, @, @, 0, 0, 0, 1, 5]
[@, @, @, @, @, 0, 0, 1, 4]
[@, @, @, @, @, @, 0, 1, 3]
[@, @, @, @, @, @, @, 1, 2]
[@, @, @, @, @, @, @, @, 1]

```

Reversing the rows gives

```
[@, @, @, @, @, @, @, @, 1]
[@, @, @, @, @, @, @, 1, 2]
[@, @, @, @, @, @, 0, 1, 3]
[@, @, @, @, @, 0, 0, 1, 4]
[@, @, @, @, 0, 0, 0, 1, 5]
[@, @, @, 0, 0, 0, 0, 1, 6]
[@, @, 0, 0, 0, 0, 0, 1, 7]
[@, 0, 0, 0, 0, 0, 0, 1, 8]
[0, 0, 0, 0, 0, 0, 0, 1, 9]

```

To turn the 2D array into a whitespace-separated string, we use the built-in grid atom (`G`). It joins columns by spaces and rows by linefeeds, yielding the following result.

```
@ @ @ @ @ @ @ @ 1
@ @ @ @ @ @ @ 1 2
@ @ @ @ @ @ 0 1 3
@ @ @ @ @ 0 0 1 4
@ @ @ @ 0 0 0 1 5
@ @ @ 0 0 0 0 1 6
@ @ 0 0 0 0 0 1 7
@ 0 0 0 0 0 0 1 8
0 0 0 0 0 0 0 1 9

```

All that's left to do is removing the padding character with `ḟ”@`, yielding

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

```

which is the desired output.
> 8 votes

# Answer
# J, ~~46~~ ~~42~~ ~~39~~ 36 bytes

```
(#\-#)|."_1#{.[:":@|./.<@#2&(|@-/\)]

```

A straight-forward implementation. Generates a table of successive differences between each pair and repeats it a number of times equal to the length of the input array. Then traverses each diagonal of that table to form the rows of the triangle. The rest is formatting the rows into a pyramid.

## Usage

```
   f =: (#\-#)|."_1#{.[:":@|./.<@#2&(|@-/\)]
   f 2 5 4 9 3 4
     2
    3 5
   2 1 4
  2 4 5 9
 1 3 1 6 3
0 1 4 5 1 4
   f 4 7
 4
3 7
   f 8 7 3 2 4 5 9 1 6
        8
       1 7
      3 4 3
     0 3 1 2
    2 2 1 2 4
   0 2 0 1 1 5
  0 0 2 2 3 4 9
 1 1 1 1 1 4 8 1
0 1 0 1 0 1 3 5 6

```

## Explanation

```
(#\-#)|."_1#{.[:":@|./.<@#2&(|@-/\)]  Input: list A
                         #            Get len(A)
                       <@             Box it
                                   ]  Get A
                          2&(     )   Repeat len(A) times on A initially
                          2      \      Get each iverlapping sublist of size 2
                                /       Reduce it using
                             |@-          The absolute value of the difference

                                      This will form a table where each row contains the
                                      successive differences
              [:     /.               Operate on the diagonals of that table
                   |.                 Reverse each diagonal
                ":@                   Format each into a string
           #                          Get len(A)
            {.                        Take that many from the strings of diagonals
 #\                                   Get the length of each prefix of A
                                      Makes the range [1, 2, ..., len(A)]
    #                                 Get len(A)
   -                                  Subtract the len(A) from each in the prefix range
                                      Makes [-len(A)+1, ..., -1, 0]
      |."_1                           Rotate each string left using each value
                                      A negative rotate left = rotate right
                                      Output the pyramid

```
> 2 votes

# Answer
## CJam, 29 bytes

```
q~{_2ew::-:z}h]W%zzeeSff*W%N*

```

Try it online! (The first and last line enable a linefeed-separated test suite.)

This uses the triangle-rotation and layouting code from this answer and the triangle itself is generated with the same principle as in this answer.
> 2 votes

# Answer
# Pyth, 22 bytes

```
jmX-jN_Pd;N;_.t_M.uaVt

```

Try it online!
> 1 votes

# Answer
# Python 3, 144 bytes

```
def f(x):
 y=[x]
 for i in range(len(x)-1):y+=[['']*-~i+[abs(y[i][j]-y[i][j+1])for j in range(i,len(y[i])-1)]]
 for i in zip(*y):print(*i[::-1])

```

A function that takes input of a list `x` via argument and prints the result to STDOUT.

**How it works**

The program takes input of a list `x`, and initialises a nested list `y` such that `y[0] = x`. The absolute differences for the last list in `y` (initially `x`) are then generated and appended as a list to `y` until a list of length `1` is reached; at each stage, the list is pre-padded with spaces such that all lists in `y` have the same length as `x`. Next, `y` is transposed, leaving it containing a tuple for each output line, but reversed. Each tuple in the transpose is unpacked, reversed and printed, leaving the difference pyramid on STDOUT.

Try it on Ideone
> 1 votes

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


title: Unzip some numbers

text:
# Question
Title: Unzip some numbers
Your task is to create a program or function that generates a zipper with a length of 10 lines. Each line of the zipper is represented by two dashes `--`:

```
--
--
--
--
--
--
--
--
--
--

```

The program/function will take a percentage (divisible by 10) as input, and the output will be the zipper "unzipped" (dashes separated) from the top by the percentage, revealing the 1-indexed, lowest level repeated 2 times, with all prior levels repeated 4, 6, 8, ...etc. times, while keeping the bottom of the zipper centered.

### Examples

```
>>10%
-11-
 --
 --
 --
 --
 --
 --
 --
 --
 --

>>50%
-1111111111-
 -22222222-
  -333333-
   -4444-
    -55-
     --
     --
     --
     --
     --

>>100%
-11111111111111111111-
 -222222222222222222-
  -3333333333333333-
   -44444444444444-
    -555555555555-
     -6666666666-
      -77777777-
       -888888-
        -9999-
         -10-

```

The input (percentage) can be formatted however you like (50%, .5, 50, 5 \[zero implied\], etc), and it will always be in the range of 0 to 100 and divisible by 10. The spacing in the examples must be preserved in your output.

# Answer
> 10 votes
# Python 2 - ~~184~~ ~~151~~ 146 Bytes

```
def r(n):
  n/=10
  for i in range(1,11):
    if n<0:print"%s--"%p
    elif i>9:print" %s-10-"%p
    else:p=" "*~-i;print"%s-%s-"%(p,`i`*2*n);n-=1

```

The last number kinda messed with me a little. I might be able to remove the second if statement if I look at it later.

EDIT: Thx to mbomb007 for removing 3 bytes. Thanks to charredgrass for the formatting tips to help remove lots and lots of bytes! :-D Thanks to TheBikingViking for helping with yet another two bytes!

# Answer
> 10 votes
# Python 2, 74 bytes

```
n=input()
x=0
exec"print' '*x+'-'+`x+1`*(n-x<<1-x/9)+'-';x=min(x+1,n);"*10

```

Saved two bytes by `exec`-ifying a loop, thanks to Dennis.

EDIT: I took a slightly different approach and saved two more bytes.

# Answer
> 4 votes
## PowerShell v2+, ~~130~~ ~~120~~ ~~116~~ 110 bytes

```
param($n)$i=0;10..1|%{" "*$i+(("-"+("$($i+1)"*([math]::Max($n-10+$_,0))*2)),"-10")[$n-$_-eq9]+"-";$i+=$i-ne$n}

```

Edit 1 - Golfed 10 bytes by eliminating `$x` variable and slightly redoing how the string is formulated.
Edit 2 - Golfed another 4 bytes by redoing how input happens and by redoing how `$i` is calculated each loop.
Edit 3 - Saved 6 bytes by OP allowing input as `0..10`, so no need to divide by 10.

Surprisingly difficult!

Takes input as `1`,`5`, etc., stored in `$n`. Sets helper `$i` variable (one of the very rare times that a variable needs to be initialized to `0` in PowerShell), and then starts a loop from `10` to `1`.

Each iteration, we set start our string with a number of spaces equal to `$i`, followed by a pseudo-ternary `(... , ...)[]`. Inside the pseudo-ternary, we select a string of either `-` with a number of digits (the higher of `$n-10+$_` or `0`, multiplied by 2), or the string `-10` -- the selection is based on whether we're at the 10th iteration and our input was `100`. We concatenate that with a final `-`. That resultant string is placed onto the pipeline.

Finally, we increment `$i`, and this was really tricky. We wound up using a binary-cast-to-int trick to only increment `$i` up until it reaches `$n`, and then keeping it at the same value thereafter. This ensures we've reached the "end" of the zipper indentation at the appropriate level.

Once the loop has finished, the resultant strings are all accumulated on the pipeline and output is implicit.

### Examples

```
PS C:\Tools\Scripts\golfing> .\unzip-some-numbers.ps1 70
-11111111111111-
 -222222222222-
  -3333333333-
   -44444444-
    -555555-
     -6666-
      -77-
       --
       --
       --

PS C:\Tools\Scripts\golfing> .\unzip-some-numbers.ps1 100
-11111111111111111111-
 -222222222222222222-
  -3333333333333333-
   -44444444444444-
    -555555555555-
     -6666666666-
      -77777777-
       -888888-
        -9999-
         -10-

```

# Answer
> 3 votes
# Python, ~~95~~ 84 bytes

I wasn't aware lambdas were legal, thanks @Dr Green Eggs and Iron Man

```
lambda p:'\n'.join(' '*min(p,l)+'-'+(2-(l==9))*(p-l)*str(l+1)+'-'for l in range(10))

```

# Answer
> 3 votes
# Pyth, ~~37~~ 34 bytes

```
~~=h/QTjm+*;thS,dQj<*`d20eS,0y-Qd"--"ST~~
=h/QTjm+*;thS,dQj*`d/y-Qdl`d"--"ST

```

Test suite.

# Answer
> 2 votes
# MATL, ~~48~~ ~~41~~ 35 bytes

```
0:9"@GhX<Z"45h@QVG@-E@8>-OhX>Y"h45h

```

**Try it online!**

# Answer
> 1 votes
# Ruby, 74 bytes

Uses the implied-zero format specified in the question, so `40%` is `f[4]` if the anonymous function is assigned to `f`. If a full percentage is needed, +6 bytes for `n/=10;`

Try it online!

```
->n{10.times{|i|puts' '*[i,n].min+"-#{i>8?10:(i+1).to_s*2*(n-i)if i<n}-"}}

```

# Answer
> 1 votes
# Python 3, ~~98, 90, 87~~, 85 bytes.

Takes the number already divided by 10. I can probably remove some of the parens, but this is pretty closed to fully golfed.

```
lambda n:'\n'.join(' '*min(i,n)+'-%s-'%(str(i+1)*(n>i>8or(n-i)*2))for i in range(10))

```

# Answer
> 1 votes
# Javascript es7, 105 bytes

```
A=>[...Array(10)].map((a,i)=>' '.repeat((d=A<i)?A:i)+('-'+(i+1+'').repeat(d?0:i<9?2*(A-i):1)+'-')).join`
`

```

---

call with

```
f=A=>[...Array(10)].map((a,i)=>' '.repeat((d=A<i)?A:i)+('-'+(i+1+'').repeat(d?0:i<9?2*(A-i):1)+'-')).join`
`

f(10)
f(5)
f(0)

```

# Answer
> 1 votes
# Haskell, 83 bytes

```
f n=unlines[[[1..y]>>" ",take(2*(n-y))$cycle$show$y+1]>>=(++"-")|y<-min n<$>[0..9]]

```

# Answer
> 1 votes
# Python 2.7, 113 108 77 bytes

n=input()
for x in range(0,10):
v=str(x+1)\*(n-x)*2
if x*n\>89:v='10'
print' '\*min(x,n)+'-'+v+'-'

First time playing golf. Gonna keep going, try to get it \<100.
Assumes input is 1-10.

Edit: Used some tricks from @LeakyNun 's answer (thanks), then crunched it a bit further and got... basically the same answer :/ Didn't know about the \`int\` string conversion, and 2 - boolean let me get rid of the if statement, which let me get rid of the whole v variable. Very cool.

My version:

```
n=input()
for x in range(10):print' '*min(x,n)+'-'+`x+1`*(n-x)*(2-(x>8))+'-'

```

# Answer
> 0 votes
# Python 2, 81 bytes

```
n=input()/10
for i in range(10):print(' '*min(i,n)+'-'+2*(n-i)/-~(i>8)*`i+1`+'-')

```

Ideone it!

# Answer
> 0 votes
# Python 2.7, ~~110~~ ~~99~~ ~~95~~ 91 bytes:

```
G=input();i=1;exec"print' '*[~-i,G][i>G]+'-%s-'%[`i`*(2*-~G-i*2),'10'][(i>9)*G>9];i+=1;"*10

```

A full program that takes input by an integer in the inclusive range `[1,10]`, where `10` means `100%` and `1` means `10%`. Can probably be golfed down a bit more.

Try It Online! (Ideone)

# Answer
> 0 votes
# PHP 5.3, ~~92~~ 91 bytes

```
<?for(;$i<10;$i++)echo'
'.str_pad('-'.str_repeat($i+1,$n>9&&$i>8?:($n-$i)*2).'-',22,' ',2);

```
* for PHP 5.3 with `register_globals=1` and `short_open_tags=1` (and `error_reporting=0`)
call in cli with `php-cgi -f <filename> n=<number>`
* number from 0 to 10

* to call in web browser with `<scriptpath>?n=<number>`: prepend `<pre>`
* for 4.0.1 \< PHP \< 5.3: replace `?:` with `?1:` (+1)
* for PHP\>=5.4: replace the first `$n` with `($n=$_GET[n])` (+11)

**ungolfed as a function** (any PHP\>=4.0.1)

```
function unzip($n) // $n from 0 to 10
{
    for($i=0;$i<10;$i++)                // $i = line number -1
        $s.='
'.str_pad(                              // pad the result of the following on both sides
            '-'.                            // prepend '-'
            str_repeat($i+1,                // print line number
                ($n>9&&$i>8 ? 1             // in tenth line, if $n is 10: once
                : ($n-$i)*2)                    // else  2*($n-$i) times
            ).'-'                           // append '-'
            , 22,' ', STR_PAD_BOTH);    // pad to 22 width with SPC on both sides
    return $s;
}

```

**test suite**

```
echo'<table border=1><tr>';
for($i=0;$i<11;$i++)echo'<th>',$i*10,'%</th>';
echo'</tr><tr>';
for($i=0;$i<11;$i++)echo'<td><pre>', unzip($i), '</pre></td>';
echo '</table>';

```

Now this is new to me: PHP beats JavaScript.
This approach is golfed to the min, I think.

# Answer
> 0 votes
# Julia, 73 bytes

```
x->join([" "^min(x,a)*"-$("$(a+1)"^(x>a?a>8?1:2(x-a):0))-"for a=0:9],'
')

```

First Julia answer! Tips are appreciated.

Try it online!

# Answer
> 0 votes
# Perl, 122 bytes

```
$k=<>;for(my $i=0;$i++<10;){$s="-"."$i"x($k/10-$i+1);$p=length $s;$l=$l>$p?$l:$p;printf "%${l}s%s\n",$s,scalar reverse $s}

```

# Answer
> 0 votes
## Common Lisp (Lispworks), 314 bytes

```
(defun f()(let((s(string(read))))(let((n(/(parse-integer(subseq s 0(1-(length s))))10)))(if(> n 0)(progn(dotimes(r n)(progn(dotimes(c r)#1=(format t" "))(format t"-")(if(=(1+ r)10)(format t"10")(dotimes(j(* 2(- n r)))(format t"~S"(1+ r))))(format t"-~%")))(dotimes(d(- 10 n))(dotimes(c n)#1#)(format t"--~%")))))))

```

ungolded:

```
    (defun f ()
      (let ((s (string (read))))
        (let ((n (/ (parse-integer (subseq s 0 (1- (length s)))) 10)))
          (if (> n 0)
              (progn
                (dotimes (r n)
                  (progn
                    (dotimes (c r)
                      (format t " "))
                    (format t "-")
                    (if (= (1+ r) 10)
                        (format t "10")
                      (dotimes (j (* 2 (- n r)))
                        (format t "~S" (1+ r))))
                    (format t "-~%")))
                (dotimes (d (- 10 n))
                  (dotimes (c n)
                    (format t " "))
                  (format t "--~%")))))))

```

Usage:

```
    CL-USER 2515 > (f)
    10%
    -11-
     --
     --
     --
     --
     --
     --
     --
     --
     --
    NIL

    CL-USER 2516 > (f)
    50%
    -1111111111-
     -22222222-
      -333333-
       -4444-
        -55-
         --
         --
         --
         --
         --
    NIL

    CL-USER 2517 > (f)
    100%
    -11111111111111111111-
     -222222222222222222-
      -3333333333333333-
       -44444444444444-
        -555555555555-
         -6666666666-
          -77777777-
           -888888-
            -9999-
             -10-
    NIL

```

# Answer
> 0 votes
## APL, 46 bytes

```
{↑(⍳10){(''↑⍨1-⍺⌊a+1),1⌽'--',⍵⍴⍕⍺}¨10↑2×⌽⍳a←⍵}

```

The argument should be given as the percentage divided by 10 (that is: a simple integer, in the range \[0,10\]).

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


title: Decompose string into blocks

text:
# Question
Title: Decompose string into blocks
Your program's input is a string containing whitespaces, parentheses, and other characters. The string is assumed to be parenthesed correctly, i.e. each right parenthesis matches a unique left parenthesis and vice versa : so the program is allowed to do anything on incorrectly parenthesed strings, such as `)abc`, `(abc` or `)abc(`. The character interval between a left parenthesis and the corresponding right parenthesis (including the parentheses) is called a *parenthesed interval*. Your program's job is to decompose the string into blocks according to the rules below, and output the result as a "vertical list", with one block per line.

Now, two characters in the string are in the same block if either

(a) there is no whitespace character strictly between them

or

(b) there is a parenthesed interval containing them both.

Also,

(c) Whitespaces not in any parenthesed interval are mere separators and to be discarded in the decomposition. All the other characters (including whitespaces) are retained.

For example, if the input is

```
I guess     () if(you say ( so)), I'll have((  ))to pack my (((things))) and go

```

The output should be

```
I
guess
()
if(you say ( so)),
I'll
have((  ))to
pack
my
(((things)))
and
go

```

Another useful test (thanks to NinjaBearMonkey) :

```
Hit the ( Road (Jack Don't) come ) back (no (more ) ) no more

```

The output should be

```
Hit
the
( Road (Jack Don't) come )
back
(no (more ) )
no
more

```

The shortest code in bytes wins.

# Answer
> 3 votes
# MATL, 22 bytes

```
j0G40=G41=-YsG32=*g(Yb

```

**Try it online!**

### Explanation

This uses a builtin function for splitting a string at spaces. To avoid splitting at spaces between matching parentheses, these are first detected and replaced by character 0. This is not detected as a space by the string-splitting function, but is treated as a space by the implicit display function.

```
j        % Take input as a string.
0        % Push 0
G40=     % True for occurrences of '('
G41=     % True for occurrences of ')'
-Ys      % Subtract and cumulative sum. Positive values correspond to characters
         % between matching parentheses
G32=     % True for occurrences of space
*g       % Multiply, convert to logical. Gives true for spaces between matching
         % parentheses
(        % Assign 0 to those positions. This replaces spaces between matching
         % parentheses by character 0
Yb       % Split at spaces, treating consecutive spaces as a single space.
         % Character 0 does not cause splitting, but is displayed as a space

```

# Answer
> 8 votes
## Retina, 31 bytes

```
S-_` (?=([^)]|(\()|(?<-2>.))+$)

```

Try it online!

This is a standard exercise in balancing groups. We simply match all spaces from which we can reach the end of the string while passing only correctly matched parentheses (since the ones we don't want to remove are followed by an unmatched closing parenthesis), and split the input around those matches. The `_` option removes empty segments in case there are several spaces in a row and the `-` suppresses the default behaviour to include captured substrings in the result.

# Answer
> 7 votes
# Retina, 30 bytes

```
!`(\(()|(?<-2>)\)|(?(2).|\S))+

```

1 byte shorter...

Try it here.

# Answer
> 3 votes
## JavaScript (ES6), 61 bytes

```
s=>s.replace(/[()]| +/g,c=>(c<`(`?n:c<`)`?++n:n--)?c:`
`,n=0)

```

Works by matching all parentheses and runs of spaces, maintaining a count of the nesting depth and replacing the run with a newline if the nesting depth is zero.

# Answer
> 2 votes
## APL, ~~55~~ 53 bytes

```
{⍵⊂⍨((⍵≠' ')∨~b)×+\1,¯1↓(b←0=+\1 ¯1 0['()'⍳⍵])∧⍵=' '}

```

To be run in `⎕ml←3`. Usual trick: cumulative scans of 1s and -1s to identify the areas enclosed by parentheses. Where the cumulative sum is 0, then we are outside parentheses. Boolean and the vector with the boolean vector with 1s where there are spaces. Rotate by 1 to the right inserting a 1 on the left. Build another running sum where each change identifies a segment. We're almost done, but we still need to remove the spaces at level 0. That's what the left side of the multiplication does: it zeroes out the level 0 spaces in the running sum. The dyadic enclose `⊂⍨` splits every time the running sum changes while throwing away the zeroes.

# Answer
> 1 votes
## Perl, 80 bytes (79 + `-n` flag)

```
$r=qr/[^\(\)]*(\((??{$r})\))?[^\(\)]*/;/((([^ \(]*(\($r\))?)+ *)(?{say$^N}))+/

```

Run with :

```
perl -M5.010 -ne '$r=qr/[^\(\)]*(\((??{$r})\))?[^\(\)]*/;/((([^ \(]*(\($r\))?)+ *)(?{say$^N}))+/'

```

It might not be easy to read, so here are the explanations :

```
# The first regex ($r) is meant to match anything between two matching parenthesis
$r = qr/ [^\(\)]*         # match anything but parenthesis
         (\(               # match an opening parenthesis
           (??{$r})        # reccursive call to the same regex
          \)               # match a closing parenthesis
         )?               # the 3 previous lines are optionnal
         [^\(\)]*         # match anything but parenthesis
       /x;

# The second regex kinda split the input according to the rules
/(
    (
     ([^ \(]*           # match anything but spaces and parenthesis
      (\($r\))?          # optionnal : match an opening parenthesis, then let the
                         #   first regex match anything until the matching closing parenthesis.
     )+                 # repeat (no spaces out of parenthesis has been found yet)
     \ *               # match the space(s) that delimite the outputed lines.
    )
    (?{say$^N})       # execute the code 'say $^N' which prints the content
                      #   of the last closed group (which is the line above)
 )+                 # repeat as many times as possible
/x

```

# Answer
> 1 votes
# C (32-bit), 115 113 bytes

```
s,*P;main(q,c){char*p=P=1[P=c],*o=p;for(;c=*p++;c^=32,s+=c^9?c==8:-1,*o=s|c?c^32:10,o+=s|c||q,q=c);*o=0;puts(P);}

```

Compile as 32-bit C, and pass input string as command-line argument. E.g.:

```
~/golf/ λ gcc -m32 -w golf.c && ./a.out "Hit the ( Road (Jack Don't) come ) back (no (more ) ) no more"
Hit
the
( Road (Jack Don't) come )
back
(no (more ) )
no
more

```

---
Tags: code-golf, balanced-string
---


title: Miniature Faking

text:
# Question
Title: Miniature Faking
As any *amateur* photographer can tell you, extreme post-processing is **always good.** One such technique is called "miniature-faking".

The object is to make an image look like a photograph of a miniaturized, toy version of itself. This works best for photographs taken from a moderate/high angle to the ground, with a low variance in subject height, but can be applied with varying effectiveness to other images.

**The challenge:** Take a photograph and apply a miniature-faking algorithm to it. There are many ways to do this, but for the purposes of this challenge, it boils down to:

* **Selective blur**

> Some part of the image should be blurred to simulate a shallow depth-of-field. This is usually done along some gradient, whether linear or shaped. Choose whatever blur/gradient algorithm you like, but between 15-85% of the image must have "noticeable" blur.
* **Saturation boost**

> Pump up the color to make things appear they were painted by hand. Output must have an average saturation level of \> +5% when compared to input. (using HSV saturation)
* **Contrast Boost**

> Increase the contrast to simulate harsher lighting conditions (such as you see with an indoor/studio light rather than the sun). Output must have a contrast of \> +5% when compared to input. (using RMS algorithm)

Those three alterations **must** be implemented, and **no other** enhancements/alterations are allowed. No cropping, sharpening, white balance adjustments, nothing.

* Input is an image, and can be read from a file or memory. You may use external libraries to *read and write* the image, but you **cannot** use them to *process* the image. Supplied functions are also disallowed for this purpose (you can't just call `Image.blur()` for example)
* There is no other input. The processing strengths, levels, etc, must be determined by the program, not by a human.
* Output can be displayed or saved as a file in a standardized image format (PNG, BMP, etc).
* Try to generalize. It should not work on only *one* image, but it's understandable that it won't work on *all* images. Some scenes simply do not respond well to this technique, no matter how good the algorithm. Apply common sense here, both when answering and voting on answers.
* Behavior is undefined for invalid inputs, and those images which are impossible to satisfy the spec. For example, a grayscale image cannot be saturated (there is no base hue), a pure white imaged cannot have increased contrast, etc.
* Include at least two output images in your answer:

> One must be generated from one of the images in this dropbox folder. There are six to choose from, but I tried to make them all viable to varying degrees. You can see sample outputs for each in the `example-outputs` subfolder. Please note that these are full 10MP JPG images straight out of the camera, so you have a lot of pixels to work on.
>
> The other can be any image of your choice. Obviously, try to choose images that are freely usable. Also, include either the original image or a link to it for comparison.

---

For example, from this image:

You might output something like:

For reference, the example above was processed in GIMP with an angular box-shaped gradient gaussian blur, saturation +80, contrast +20. (I don't know what units GIMP uses for those)

For more inspiration, or to get a better idea what you're trying to achieve, check out this site, or this one. You can also search for `miniature faking` and `tilt shift photography` for examples.

---

This is a popularity contest. Voters, vote for the entries you feel look the best while staying true to the objective.

---

**Clarification:**

Clarifying what functions are disallowed, it was not my intent to ban *math* functions. It was my intent to ban *image manipulation* functions. Yes, there's some overlap there, but things like FFT, convolutions, matrix math, etc, are useful in many other areas. You should *not* be using a function that simply takes an image and blurs. If you find a suitably mathy way to *create* a blur, that fair game.

# Answer
> 14 votes
## Java : Reference Implementation

Here's a basic reference implementation in Java. It works best on high-angle shots, and it's horribly inefficient.

The blur is a very basic box blur, so it loops over the same pixels much more than necessary. The contrast and saturation *could* be combined into a single loop also, but the vast majority of the time spent is on blur, so it wouldn't see much gain from that. That being said, it works fairly quickly on images under 2MP or so. The 10MP image took some time to complete.

The blur quality could easily be improved by using *basically anything* but a flat box blur. The contrast/saturation algorithms do their job, so no real complaints there.

There is no real intelligence in the program. It uses constant factors for the blur, saturation, and contrast. I played around it with it to find happy medium settings. As a result, there *are* some scenes that it doesn't do very well. For instance, it pumps the contrast/saturation so much that images with large similarly-colored areas(think sky) break up into color bands.

It's simple to use; just pass the file name in as the only argument. It outputs in PNG regardless of what the input file was.

### Examples:

**From the dropbox selection:**

These first images are scaled down for ease of posting. Click the image to see full-size.

After:

Before:

**Miscellaneous selection:**

After:

Before:

```
import java.awt.Graphics;
import java.awt.image.BufferedImage;
import java.io.File;
import java.io.IOException;

import javax.imageio.ImageIO;

public class MiniFake {

    int maxBlur;
    int maxDist;
    int width;
    int height;

    public static void main(String[] args) {
        if(args.length < 1) return;
        new MiniFake().run(args[0]);
    }

    void run(String filename){
        try{
            BufferedImage in = readImage(filename);
            BufferedImage out = blur(in);
            out = saturate(out, 0.8);
            out = contrast(out, 0.6);

            String[] tokens = filename.split("\\.");
            String outname = tokens[0];
            for(int i=1;i<tokens.length-1;i++)
                outname += "." + tokens[i];
            ImageIO.write(out, "png", new File(outname + "_post.png"));
            System.out.println("done");
        } catch (Exception e){
            e.printStackTrace();
        }
    }

    BufferedImage contrast(BufferedImage in, double level){
        BufferedImage out = copyImage(in);
        long lumens=0;
        for(int x=0;x<width;x++)
            for(int y=0;y<height;y++){
                int color = out.getRGB(x,y);
                lumens += lumen(getR(color), getG(color), getB(color));
            }
        lumens /= (width * height);

        for(int x=0;x<width;x++)
            for(int y=0;y<height;y++){
                int color = out.getRGB(x,y);
                int r = getR(color);
                int g = getG(color);
                int b = getB(color);
                double ratio = ((double)lumen(r, g, b) / (double)lumens) - 1d;
                ratio *= (1+level) * 0.1;
                r += (int)(getR(color) * ratio+1);
                g += (int)(getG(color) * ratio+1);
                b += (int)(getB(color) * ratio+1);
                out.setRGB(x,y,getColor(clamp(r),clamp(g),clamp(b)));
            }
        return out;
    }

    BufferedImage saturate(BufferedImage in, double level){
        BufferedImage out = copyImage(in);
        for(int x=0;x<width;x++)
            for(int y=0;y<height;y++){
                int color = out.getRGB(x,y);
                int r = getR(color);
                int g = getG(color);
                int b = getB(color);
                int brightness = Math.max(r, Math.max(g, b));
                int grey = (int)(Math.min(r, Math.min(g,b)) * level);
                if(brightness == grey)
                    continue;
                r -= grey;
                g -= grey;
                b -= grey;
                double ratio = brightness / (double)(brightness - grey);
                r = (int)(r * ratio);
                g = (int)(g * ratio);
                b = (int)(b * ratio);
                out.setRGB(x, y, getColor(clamp(r),clamp(g),clamp(b)));
            }
        return out;
    }

    BufferedImage blur(BufferedImage in){
        BufferedImage out = copyImage(in);
        int[] rgb = in.getRGB(0, 0, width, height, null, 0, width);
        for(int i=0;i<rgb.length;i++){
            double dist = Math.abs(getY(i)-(height/2));
            dist = dist * dist / maxDist;
            int r=0,g=0,b=0,p=0;
            for(int x=-maxBlur;x<=maxBlur;x++)
                for(int y=-maxBlur;y<=maxBlur;y++){
                    int xx = getX(i) + x;
                    int yy = getY(i) + y;
                    if(xx<0||xx>=width||yy<0||yy>=height)
                        continue;
                    int color = rgb[getPos(xx,yy)];
                    r += getR(color);
                    g += getG(color);
                    b += getB(color);
                    p++;
                }

            if(p>0){
                r /= p;
                g /= p;
                b /= p;
                int color = rgb[i];
                r = (int)((r*dist) + (getR(color) * (1 - dist)));
                g = (int)((g*dist) + (getG(color) * (1 - dist)));
                b = (int)((b*dist) + (getB(color) * (1 - dist)));
            } else {
                r = in.getRGB(getX(i), getY(i));
            }
            out.setRGB(getX(i), getY(i), getColor(r,g,b));
        }
        return out;
    }

    BufferedImage readImage(String filename) throws IOException{
         BufferedImage image = ImageIO.read(new File(filename));
         width = image.getWidth();
         height = image.getHeight();
         maxBlur = Math.max(width, height) / 100;
         maxDist =  (height/2)*(height/2);
         return image;
    }

    public BufferedImage copyImage(BufferedImage in){
        BufferedImage out = new BufferedImage(in.getWidth(), in.getHeight(), BufferedImage.TYPE_INT_ARGB);
        Graphics g = out.getGraphics();
        g.drawImage(in, 0, 0, null);
        g.dispose();
        return out;
    }

    static int clamp(int c){return c<0?0:c>255?255:c;}
    static int getColor(int a, int r, int g, int b){return (a << 24) | (r << 16) | (g << 8) | (b);}
    static int getColor(int r, int g, int b){return getColor(0xFF, r, g, b);}
    static int getR(int color){return color >> 16 & 0xFF;}
    static int getG(int color){return color >> 8 & 0xFF;}
    static int getB(int color){return color & 0xFF;}
    static int lumen(int r, int g, int b){return (r*299)+(g*587)+(b*114);}
    int getX(int pos){return pos % width;}
    int getY(int pos){return pos / width;}
    int getPos(int x, int y){return y*width+x;}
}

```

# Answer
> 11 votes
## C#

Instead of doing any iterative box blurs, I decided to go the entire way and write a Gaussian blur. The `GetPixel` calls really slow it down when using large kernels, but it's not really worthwhile to convert the methods to use `LockBits` unless we were processing some larger images.

Some examples are below, which use the default tuning parameters I set (I didn't play with the tuning parameters much, because they seemed to work well for the test image).

For the test case provided...

Another...

Another...

The saturation and contrast increases should be fairly straightforward from the code. I do this in the HSL space and convert it back to RGB.

The 2D Gaussian kernel is generated based on the size `n` specified, with:

```
EXP(-((x-x0)^2/2+(y-y0)^2/2)/2)

```

...and normalized after all kernel values are assigned. Note that `A=sigma_x=sigma_y=1`.

In order to figure out where to apply the kernel, I use a blur weight, calculated by:

```
SQRT([COS(PI*x_norm)^2 + COS(PI*y_norm)^2]/2)

```

...which gives a decent response, essentially creating an ellipse of values that are protected from the blur that gradually fades further out. A band-pass filter combined with other equations (maybe some variant of `y=-x^2`) could potentially work better here for certain images. I went with the cosine because it gave a good response for the base case I tested.

```
using System;
using System.Drawing;
using System.Drawing.Imaging;
using System.IO;

namespace FakeMini
{
    static class Program
    {
        static void Main()
        {
            // Some tuning variables
            double saturationValue = 1.7;
            double contrastValue = 1.2;
            int gaussianSize = 13; // Must be odd and >1 (3, 5, 7...)

            // NxN Gaussian kernel
            int padding = gaussianSize / 2;
            double[,] kernel = GenerateGaussianKernel(gaussianSize);

            Bitmap src = null;
            using (var img = new Bitmap(File.OpenRead("in.jpg")))
            {
                src = new Bitmap(img);
            }

            // Bordering could be avoided by reflecting or wrapping instead
            // Also takes advantage of the fact that a new bitmap returns zeros from GetPixel
            Bitmap border = new Bitmap(src.Width + padding*2, src.Height + padding*2);

            // Get average intensity of entire image
            double intensity = 0;
            for (int x = 0; x < src.Width; x++)
            {
                for (int y = 0; y < src.Height; y++)
                {
                    intensity += src.GetPixel(x, y).GetBrightness();
                }
            }
            double averageIntensity = intensity / (src.Width * src.Height);

            // Modify saturation and contrast
            double brightness;
            double saturation;
            for (int x = 0; x < src.Width; x++)
            {
                for (int y = 0; y < src.Height; y++)
                {
                    Color oldPx = src.GetPixel(x, y);
                    brightness = oldPx.GetBrightness();
                    saturation = oldPx.GetSaturation() * saturationValue;

                    Color newPx = FromHSL(
                                oldPx.GetHue(),
                                Clamp(saturation, 0.0, 1.0),
                                Clamp(averageIntensity - (averageIntensity - brightness) * contrastValue, 0.0, 1.0));
                    src.SetPixel(x, y, newPx);
                    border.SetPixel(x+padding, y+padding, newPx);
                }
            }

            // Apply gaussian blur, weighted by corresponding sine value based on height
            double blurWeight;
            Color oldColor;
            Color newColor;
            for (int x = padding; x < src.Width+padding; x++)
            {
                for (int y = padding; y < src.Height+padding; y++)
                {
                    oldColor = border.GetPixel(x, y);
                    newColor = Convolve2D(
                        kernel,
                        GetNeighbours(border, gaussianSize, x, y)
                       );

                    // sqrt([cos(pi*x_norm)^2 + cos(pi*y_norm)^2]/2) gives a decent response
                    blurWeight = Clamp(Math.Sqrt(
                        Math.Pow(Math.Cos(Math.PI * (y - padding) / src.Height), 2) +
                        Math.Pow(Math.Cos(Math.PI * (x - padding) / src.Width), 2)/2.0), 0.0, 1.0);
                    src.SetPixel(
                        x - padding,
                        y - padding,
                        Color.FromArgb(
                            Convert.ToInt32(Math.Round(oldColor.R * (1 - blurWeight) + newColor.R * blurWeight)),
                            Convert.ToInt32(Math.Round(oldColor.G * (1 - blurWeight) + newColor.G * blurWeight)),
                            Convert.ToInt32(Math.Round(oldColor.B * (1 - blurWeight) + newColor.B * blurWeight))
                            )
                        );
                }
            }
            border.Dispose();

            // Configure some save parameters
            EncoderParameters ep = new EncoderParameters(3);
            ep.Param[0] = new EncoderParameter(System.Drawing.Imaging.Encoder.Quality, 100L);
            ep.Param[1] = new EncoderParameter(System.Drawing.Imaging.Encoder.ScanMethod, (int)EncoderValue.ScanMethodInterlaced);
            ep.Param[2] = new EncoderParameter(System.Drawing.Imaging.Encoder.RenderMethod, (int)EncoderValue.RenderProgressive);
            ImageCodecInfo[] codecs = ImageCodecInfo.GetImageEncoders();
            ImageCodecInfo ici = null;
            foreach (ImageCodecInfo codec in codecs)
            {
                if (codec.MimeType == "image/jpeg")
                    ici = codec;
            }
            src.Save("out.jpg", ici, ep);
            src.Dispose();
        }

        // Create RGB from HSL
        // (C# BCL allows me to go one way but not the other...)
        private static Color FromHSL(double h, double s, double l)
        {
            int h0 = Convert.ToInt32(Math.Floor(h / 60.0));
            double c = (1.0 - Math.Abs(2.0 * l - 1.0)) * s;
            double x = (1.0 - Math.Abs((h / 60.0) % 2.0 - 1.0)) * c;
            double m = l - c / 2.0;
            int m0 = Convert.ToInt32(255 * m);
            int c0 = Convert.ToInt32(255*(c + m));
            int x0 = Convert.ToInt32(255*(x + m));
            switch (h0)
            {
                case 0:
                    return Color.FromArgb(255, c0, x0, m0);
                case 1:
                    return Color.FromArgb(255, x0, c0, m0);
                case 2:
                    return Color.FromArgb(255, m0, c0, x0);
                case 3:
                    return Color.FromArgb(255, m0, x0, c0);
                case 4:
                    return Color.FromArgb(255, x0, m0, c0);
                case 5:
                    return Color.FromArgb(255, c0, m0, x0);
            }
            return Color.FromArgb(255, m0, m0, m0);
        }

        // Just so I don't have to write "bool ? val : val" everywhere
        private static double Clamp(double val, double min, double max)
        {
            if (val >= max)
                return max;
            else if (val <= min)
                return min;
            else
                return val;
        }

        // Simple convolution as C# BCL doesn't appear to have any
        private static Color Convolve2D(double[,] k, Color[,] n)
        {
            double r = 0;
            double g = 0;
            double b = 0;
            for (int i=0; i<k.GetLength(0); i++)
            {
                for (int j=0; j<k.GetLength(1); j++)
                {
                    r += n[i,j].R * k[i,j];
                    g += n[i,j].G * k[i,j];
                    b += n[i,j].B * k[i,j];
                }
            }
            return Color.FromArgb(
                Convert.ToInt32(Math.Round(r)),
                Convert.ToInt32(Math.Round(g)),
                Convert.ToInt32(Math.Round(b)));
        }

        // Generates a simple 2D square (normalized) Gaussian kernel based on a size
        // No tuning parameters - just using sigma = 1 for each
        private static double [,] GenerateGaussianKernel(int n)
        {
            double[,] kernel = new double[n, n];
            double currentValue;
            double normTotal = 0;
            for (int i = 0; i < n; i++)
            {
                for (int j = 0; j < n; j++)
                {
                    currentValue = Math.Exp(-(Math.Pow(i - n / 2, 2) + Math.Pow(j - n / 2, 2)) / 2.0);
                    kernel[i, j] = currentValue;
                    normTotal += currentValue;
                }
            }
            for (int i = 0; i < n; i++)
            {
                for (int j = 0; j < n; j++)
                {
                    kernel[i, j] /= normTotal;
                }
            }
            return kernel;
        }

        // Gets the neighbours around the current pixel
        private static Color[,] GetNeighbours(Bitmap bmp, int n, int x, int y)
        {
            Color[,] neighbours = new Color[n, n];
            for (int i = -n/2; i < n-n/2; i++)
            {
                for (int j = -n/2; j < n-n/2; j++)
                {
                    neighbours[i+n/2, j+n/2] = bmp.GetPixel(x + i, y + j);
                }
            }
            return neighbours;
        }
    }
}

```

# Answer
> 8 votes
# Java

Uses a fast running-average two-way box blur to be speedy enough to run multiple passes, emulating a Gaussian blur. Blur is an elliptical gradient instead of bi-linear as well.

Visually, it works best on large images. Has a darker, grungier theme. I'm happy with how the blur turned out on appropriately-sized images, it's quite gradual and hard to discern where it "begins."

All computations done on arrays of integers or doubles (for HSV).

Expects file path as argument, outputs file to same location with suffix " miniaturized.png" Also displays the input and output in a JFrame for immediate viewing.

(click to see large versions, they're way better)

### Before:

### After:

I may have to add some smarter tone mapping or luma preservation, as it can get quite dark:

### Before:

### After:

Still interesting though, puts it in a whole new atmosphere.

### The Code:

```
import java.awt.*;
import java.awt.image.*;
import java.io.*;

import javax.imageio.*;
import javax.swing.*;

public class SceneMinifier {

    static final double CONTRAST_INCREASE = 8;
    static final double SATURATION_INCREASE = 7;

    public static void main(String[] args) throws IOException {

        if (args.length < 1) {
            System.out.println("Please specify an input image file.");
            return;
        }

        BufferedImage temp = ImageIO.read(new File(args[0]));

        BufferedImage input = new BufferedImage(temp.getWidth(), temp.getHeight(), BufferedImage.TYPE_INT_ARGB);
        input.getGraphics().drawImage(temp, 0, 0, null); // just want to guarantee TYPE_ARGB

        int[] pixels = ((DataBufferInt) input.getData().getDataBuffer()).getData();

        // saturation

        double[][] hsv = toHSV(pixels);
        for (int i = 0; i < hsv[1].length; i++)
            hsv[1][i] = Math.min(1, hsv[1][i] * (1 + SATURATION_INCREASE / 10));

        // contrast

        int[][] rgb = toRGB(hsv[0], hsv[1], hsv[2]);

        double c = (100 + CONTRAST_INCREASE) / 100;
        c *= c;

        for (int i = 0; i < pixels.length; i++)
            for (int q = 0; q < 3; q++)
                rgb[q][i] = (int) Math.max(0, Math.min(255, ((rgb[q][i] / 255. - .5) * c + .5) * 255));

        // blur

        int w = input.getWidth();
        int h = input.getHeight();

        int k = 5;
        int kd = 2 * k + 1;
        double dd = 1 / Math.hypot(w / 2, h / 2);

        for (int reps = 0; reps < 5; reps++) {

            int tmp[][] = new int[3][pixels.length];
            int vmin[] = new int[Math.max(w, h)];
            int vmax[] = new int[Math.max(w, h)];

            for (int y = 0, yw = 0, yi = 0; y < h; y++) {
                int[] sum = new int[3];
                for (int i = -k; i <= k; i++) {
                    int ii = yi + Math.min(w - 1, Math.max(i, 0));
                    for (int q = 0; q < 3; q++)
                        sum[q] += rgb[q][ii];
                }
                for (int x = 0; x < w; x++) {

                    int dx = x - w / 2;
                    int dy = y - h / 2;
                    double dist = Math.sqrt(dx * dx + dy * dy) * dd;
                    dist *= dist;

                    for (int q = 0; q < 3; q++)
                        tmp[q][yi] = (int) Math.min(255, sum[q] / kd * dist + rgb[q][yi] * (1 - dist));

                    if (y == 0) {
                        vmin[x] = Math.min(x + k + 1, w - 1);
                        vmax[x] = Math.max(x - k, 0);
                    }

                    int p1 = yw + vmin[x];
                    int p2 = yw + vmax[x];

                    for (int q = 0; q < 3; q++)
                        sum[q] += rgb[q][p1] - rgb[q][p2];
                    yi++;
                }
                yw += w;
            }

            for (int x = 0, yi = 0; x < w; x++) {
                int[] sum = new int[3];
                int yp = -k * w;
                for (int i = -k; i <= k; i++) {
                    yi = Math.max(0, yp) + x;
                    for (int q = 0; q < 3; q++)
                        sum[q] += tmp[q][yi];
                    yp += w;
                }
                yi = x;
                for (int y = 0; y < h; y++) {

                    int dx = x - w / 2;
                    int dy = y - h / 2;
                    double dist = Math.sqrt(dx * dx + dy * dy) * dd;
                    dist *= dist;

                    for (int q = 0; q < 3; q++)
                        rgb[q][yi] = (int) Math.min(255, sum[q] / kd * dist + tmp[q][yi] * (1 - dist));

                    if (x == 0) {
                        vmin[y] = Math.min(y + k + 1, h - 1) * w;
                        vmax[y] = Math.max(y - k, 0) * w;
                    }
                    int p1 = x + vmin[y];
                    int p2 = x + vmax[y];

                    for (int q = 0; q < 3; q++)
                        sum[q] += tmp[q][p1] - tmp[q][p2];

                    yi += w;
                }
            }
        }

        // pseudo-lighting pass

        for (int i = 0; i < pixels.length; i++) {
            int dx = i % w - w / 2;
            int dy = i / w - h / 2;
            double dist = Math.sqrt(dx * dx + dy * dy) * dd;
            dist *= dist;

            for (int q = 0; q < 3; q++) {
                if (dist > 1 - .375)
                    rgb[q][i] *= 1 + (Math.sqrt((1 - dist + .125) / 2) - (1 - dist) - .125) * .7;
                if (dist < .375 || dist > .375)
                    rgb[q][i] *= 1 + (Math.sqrt((dist + .125) / 2) - dist - .125) * dist > .375 ? 1 : .8;
                rgb[q][i] = Math.min(255, Math.max(0, rgb[q][i]));
            }
        }

        // reassemble image

        BufferedImage output = new BufferedImage(input.getWidth(), input.getHeight(), BufferedImage.TYPE_INT_ARGB);

        pixels = ((DataBufferInt) output.getData().getDataBuffer()).getData();

        for (int i = 0; i < pixels.length; i++)
            pixels[i] = 255 << 24 | rgb[0][i] << 16 | rgb[1][i] << 8 | rgb[2][i];

        output.setRGB(0, 0, output.getWidth(), output.getHeight(), pixels, 0, output.getWidth());

        // display results

        display(input, output);

        // output image

        ImageIO.write(output, "PNG", new File(args[0].substring(0, args[0].lastIndexOf('.')) + " miniaturized.png"));

    }

    private static int[][] toRGB(double[] h, double[] s, double[] v) {
        int[] r = new int[h.length];
        int[] g = new int[h.length];
        int[] b = new int[h.length];

        for (int i = 0; i < h.length; i++) {
            double C = v[i] * s[i];
            double H = h[i];
            double X = C * (1 - Math.abs(H % 2 - 1));

            double ri = 0, gi = 0, bi = 0;

            if (0 <= H && H < 1) {
                ri = C;
                gi = X;
            } else if (1 <= H && H < 2) {
                ri = X;
                gi = C;
            } else if (2 <= H && H < 3) {
                gi = C;
                bi = X;
            } else if (3 <= H && H < 4) {
                gi = X;
                bi = C;
            } else if (4 <= H && H < 5) {
                ri = X;
                bi = C;
            } else if (5 <= H && H < 6) {
                ri = C;
                bi = X;
            }

            double m = v[i] - C;

            r[i] = (int) ((ri + m) * 255);
            g[i] = (int) ((gi + m) * 255);
            b[i] = (int) ((bi + m) * 255);
        }

        return new int[][] { r, g, b };
    }

    private static double[][] toHSV(int[] c) {
        double[] h = new double[c.length];
        double[] s = new double[c.length];
        double[] v = new double[c.length];

        for (int i = 0; i < c.length; i++) {
            double r = (c[i] & 0xFF0000) >> 16;
            double g = (c[i] & 0xFF00) >> 8;
            double b = c[i] & 0xFF;

            r /= 255;
            g /= 255;
            b /= 255;

            double M = Math.max(Math.max(r, g), b);
            double m = Math.min(Math.min(r, g), b);
            double C = M - m;

            double H = 0;

            if (C == 0)
                H = 0;
            else if (M == r)
                H = (g - b) / C % 6;
            else if (M == g)
                H = (b - r) / C + 2;
            else if (M == b)
                H = (r - g) / C + 4;

            h[i] = H;
            s[i] = C / M;
            v[i] = M;
        }
        return new double[][] { h, s, v };
    }

    private static void display(final BufferedImage original, final BufferedImage output) {

        Dimension d = Toolkit.getDefaultToolkit().getScreenSize();
        int wt = original.getWidth();
        int ht = original.getHeight();
        double ratio = (double) wt / ht;
        if (ratio > 1 && wt > d.width / 2) {
            wt = d.width / 2;
            ht = (int) (wt / ratio);
        }
        if (ratio < 1 && ht > d.getHeight() / 2) {
            ht = d.height / 2;
            wt = (int) (ht * ratio);
        }

        final int w = wt, h = ht;

        JFrame frame = new JFrame();
        JPanel pan = new JPanel() {
            BufferedImage buffer = new BufferedImage(w * 2, h, BufferedImage.TYPE_INT_RGB);
            Graphics2D gg = buffer.createGraphics();

            {
                gg.setRenderingHint(RenderingHints.KEY_INTERPOLATION, RenderingHints.VALUE_INTERPOLATION_BICUBIC);
                gg.setRenderingHint(RenderingHints.KEY_ANTIALIASING, RenderingHints.VALUE_ANTIALIAS_ON);
            }

            @Override
            public void paint(Graphics g) {
                gg.drawImage(original, 0, 0, w, h, null);
                gg.drawImage(output, w, 0, w, h, null);
                g.drawImage(buffer, 0, 0, null);
            }
        };
        frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        pan.setPreferredSize(new Dimension(w * 2, h));
        frame.setLayout(new BorderLayout());
        frame.add(pan, BorderLayout.CENTER);
        frame.pack();
        frame.setVisible(true);
    }
}

```

# Answer
> 8 votes
#

This was a nice challenge. The settings for blur, saturation, and contrast are hard-coded but can be easily changed if desired. However, the area in focus is hard-coded as a horizontal line in the center. It can not be simply modified like the other settings. It was chosen since most of the test images feature views across a city.

After performing a Gaussian blur, I split the image horizontally into 5 regions. The top and bottom regions will receive 100% of the blur. The middle region will receive 0% of the blur. The two remaining regions will both scale proportionally to the inverse cube from 0% to 100%.

The code is to be used as a script in J and that script will be in the same folder as `input.bmp` which will be the input image. It will create `output.bmp` which will be a *fake miniature* of the input.

The performance is good and on my pc using an i7-4770k, it takes about 20 seconds to process an image from the OP's set. Previously, it took about 70 seconds to process an image using standard convolution with the `;._3` subarray operator. The performance was improved by using FFT to perform convolution.

This code requires the `bmp` and `math/fftw` addons to be installed. You can install them using `install 'bmp'` and `install 'math/fftw'`. Your system may also need the `fftw` library to be installed.

```
load 'bmp math/fftw'

NB. Define 2d FFT
fft2d =: 4 : 0
  s =. $ y
  i =. zzero_jfftw_ + , y
  o =. 0 * i
  p =. createplan_jfftw_ s;i;o;x;FFTW_ESTIMATE_jfftw_
  fftwexecute_jfftw_ p
  destroyplan_jfftw_ p
  r =. s $ o
  if. x = FFTW_BACKWARD_jfftw_ do.
    r =. r % */ s
  end.
  r
)

fft2 =: (FFTW_FORWARD_jfftw_ & fft2d) :. (FFTW_BACKWARD_jfftw & fft2d)
ifft2 =: (FFTW_BACKWARD_jfftw_ & fft2d) :. (FFTW_FORWARD_jfftw & fft2d)

NB. Settings: Blur radius - Saturation - Contrast
br =: 15
s =: 3
c =: 1.5

NB. Read image and extract rgb channels
i =: 255 %~ 256 | (readbmp 'input.bmp') <.@%"_ 0 ] 2 ^ 16 8 0
'h w' =: }. $ i

NB. Pad each channel to fit Gaussian blur kernel
'hp wp' =: (+: br) + }. $ i
ip =: (hp {. wp {."1 ])"_1 i

NB. Gaussian matrix verb
gm =: 3 : '(%+/@,)s%~2p1%~^(s=.*:-:y)%~-:-+&*:/~i:y'

NB. Create a Gaussian blur kernel
gk =: fft2 hp {. wp {."1 gm br

NB. Blur each channel using FFT-based convolution and unpad
ib =: (9 o. (-br) }. (-br) }."1 br }. br }."1 [: ifft2 gk * fft2)"_1 ip

NB. Create the blur gradient to emulate tilt-shift
m =: |: (w , h) $ h ({. >. (({.~ -)~ |.)) , 1 ,: |. (%~i.) 0.2 I.~ (%~i.) h

NB. Tilt-shift each channel
it =: i ((m * ]) + (-. m) * [)"_1 ib

NB. Create the saturation matrix
sm =: |: ((+ ] * [: =@i. 3:)~ 3 3 |:@$ 0.299 0.587 0.114 * -.) s

NB. Saturate and clamp
its =: 0 >. 1 <. sm +/ .*"1 _ it

NB. Contrast and clamp
itsc =: 0 >. 1 <. 0.5 + c * its - 0.5

NB. Output the image
'output.bmp' writebmp~ (2 <.@^ 16 8 0) +/ .* 255 <.@* itsc

exit ''

```

---
Tags: popularity-contest, image-processing
---


# Question
Title: Sort a list of unknown values with the least amount of comparisons
In this optimization challenge you will write a program that sorts a single array by only comparing elements through asking the user on stdout to input comparison results on stdin.

*The below protocol is line-based, so everytime you print to stdout or read from stdin it is assumed a newline follows. Throughout the question below it is assumed that the user (read: the scoring program) has an array it wants sorted in a 0-based indexed array called `array`. For technical reasons I suggest flushing after every print to stout.*

1. As your first step your program must read the array size `n` from stdin.
2. Then, as often as you wish, you can print `a < b` to stdout, with two integers `0 <= a, b < n`. Then the user will enter `1` in stdin if `array[a] < array[b]`, and `0` otherwise.
3. Finally, once your program is convinced it has correctly deduced the order of the array, it must print `a ...` to stdout, where `...` is a space separated list of integers indicating the order. So if your program outputs `a 3 0 1 4 2` it means your program has deduced

```
array[3] <= array[0] <= array[1] <= array[4] <= array[2]

```

Note that your program never knew the contents of `array`, and never will.

You can only ask for `<` on stdin to sort the array. You can get other comparison operations by these equivalencies:

```
a > b        b < a
a <= b       !(b < a)
a >= b       !(a < b)
a != b       (a < b) || (b < a)
a == b       !(a < b) && !(b < a)

```

Finally, since your program interacts with the scoring program on stdout, print debug information to stderr.

---

Your program will be scored using the following Python program:

```
from __future__ import print_function
from subprocess import Popen, PIPE
import sys, random

def sort_test(size):
    array = [random.randrange(0, size) for _ in range(size)]
    pipe = Popen(sys.argv[1:], stdin=PIPE, stdout=PIPE, bufsize=0, universal_newlines=True)
    print(str(size), file=pipe.stdin); pipe.stdin.flush()
    num_comparisons = 0
    while True:
        args = pipe.stdout.readline().strip().split()
        if args and args[0] == "a":
            answer_array = [array[int(n)] for n in args[1:]]
            if list(sorted(array)) != answer_array:
                raise RuntimeError("incorrect sort for size {}, array was {}".format(size, array))
            return num_comparisons
        elif len(args) == 3 and args[1] == "<":
            a, b = int(args[0]), int(args[2])
            print(int(array[a] < array[b]), file=pipe.stdin); pipe.stdin.flush()
            num_comparisons += 1
        else:
            raise RuntimeError("unknown command")

random.seed(0)
total = 0
for i in range(101):
    num_comparisons = sort_test(i)
    print(i, num_comparisons)
    total += num_comparisons
print("total", total)

```

You score your program by typing `python score.py yourprogram`. The scoring is done by having your program sort one random array of each size 0 to 100 and counting the amount of comparisons your program asks for. **These random arrays can have duplicates**, your algorithm must be able to handle equal elements. In the event there are duplicates, there are no requirements on the order of the equal elements. So if the array is `[0, 0]` it doesn't matter if you output `a 0 1` or `a 1 0`.

**You may not optimize specifically for the particular arrays the scoring program generates.** I may change the RNG seed at any point in time. **Answers using built-in sorting algorithms are permitted to be posted for interest's sake, but are non-competing.**

Program with lowest score wins.

# Answer
> 3 votes
# Python, score 23069

This uses the Ford–Johnson merge insertion sorting algorithm.

```
from __future__ import print_function
import sys

def less(x, y):
    print(x, '<', y)
    sys.stdout.flush()
    return bool(int(input()))

def insert(x, a, key=lambda z: z):
    if not a:
        return [x]
    m = len(a)//2
    if less(key(x), key(a[m])):
        return insert(x, a[:m], key) + a[m:]
    else:
        return a[:m + 1] + insert(x, a[m + 1:], key)

def sort(a, key=lambda z: z):
    if len(a) <= 1:
        return a
    m = len(a)//2
    key1 = lambda z: key(z[-1])
    b = sort([insert(x, [y], key) for x, y in zip(a[:m], a[m:2*m])], key=key1)
    if len(a) % 2:
        b += [[a[-1], None]]
    for k in range(m, len(a)):
        l, i, (x, y) = max((-i.bit_length(), i, t) for i, t in enumerate(b) if len(t) == 2)
        b[:i + 1] = insert([x], b[:i], key=key1) + [[y]]
    if len(a) % 2:
        b.pop()
    return [x for x, in b]

print('a', ' '.join(map(str, sort(range(int(input()))))))

```

# Answer
> 1 votes
# Python, 333300 score

```
from __future__ import print_function
import sys

size = int(input())

def less(a, b):
    print(a, "<", b); sys.stdout.flush()
    return bool(int(input()))

array = list(range(size))
for _ in range(size):
    for i in range(0, size-1):
        if less(array[i+1], array[i]):
            array[i], array[i+1] = array[i+1], array[i]

print("a", " ".join(str(i) for i in array)); sys.stdout.flush()

```

This is an example program, implementing the simplest form of bubblesort, always doing `n*(n-1)` comparisons per array.

I scored this program by saving it as `sort.py` and typing `python score.py python sort.py`.

# Answer
> 1 votes
# Python 3, 28462 score

Quick sort. Pivot is leftmost item.

The score is expected, because:

```
from __future__ import print_function
import sys
size = int(input())

def less(a, b):
    print(a, "<", b); sys.stdout.flush()
    return bool(int(input()))

def quicksort(array):
    if len(array) < 2:
        return array
    pivot = array[0]
    left = []
    right = []
    for i in range(1,len(array)):
        if less(array[i],pivot):
            left.append(array[i])
        else:
            right.append(array[i])
    return quicksort(left)+[pivot]+quicksort(right)

array = list(range(size))
array = quicksort(array)

print("a", " ".join(str(i) for i in array)); sys.stdout.flush()

```

Scores for each size tested:

```
size score
0 0
1 0
2 1
3 3
4 6
5 8
6 11
7 12
8 15
9 17
10 23
11 33
12 29
13 32
14 37
15 45
16 58
17 47
18 52
19 79
20 72
21 60
22 85
23 138
24 87
25 98
26 112
27 107
28 128
29 142
30 137
31 136
32 158
33 143
34 145
35 155
36 169
37 209
38 163
39 171
40 177
41 188
42 167
43 260
44 208
45 210
46 230
47 276
48 278
49 223
50 267
51 247
52 263
53 293
54 300
55 259
56 319
57 308
58 333
59 341
60 306
61 295
62 319
63 346
64 375
65 344
66 346
67 370
68 421
69 507
70 363
71 484
72 491
73 417
74 509
75 495
76 439
77 506
78 484
79 458
80 575
81 505
82 476
83 500
84 535
85 501
86 575
87 547
88 522
89 536
90 543
91 551
92 528
93 647
94 530
95 655
96 580
97 709
98 671
99 594
100 637
total 28462

```

# Answer
> 1 votes
# Python 2 (non-competing), 23471 score

```
from __future__ import print_function
import sys
size = int(input())

def cmp(a, b):
    print(a, "<", b); sys.stdout.flush()
    return [1,-1][bool(int(input()))]

array = list(range(size))
array = sorted(array,cmp=cmp)

print("a", " ".join(str(i) for i in array)); sys.stdout.flush()

```

Scores for each size tested:

```
size score
0 0
1 0
2 1
3 4
4 5
5 7
6 9
7 14
8 17
9 20
10 21
11 26
12 30
13 35
14 37
15 41
16 45
17 51
18 52
19 57
20 63
21 63
22 72
23 79
24 79
25 80
26 91
27 93
28 96
29 105
30 110
31 116
32 124
33 123
34 131
35 130
36 142
37 144
38 156
39 154
40 163
41 168
42 177
43 178
44 183
45 183
46 192
47 194
48 212
49 207
50 216
51 221
52 227
53 239
54 238
55 243
56 255
57 257
58 260
59 270
60 281
61 284
62 292
63 293
64 303
65 308
66 312
67 321
68 328
69 328
70 342
71 348
72 352
73 358
74 367
75 371
76 381
77 375
78 387
79 400
80 398
81 413
82 415
83 427
84 420
85 435
86 438
87 448
88 454
89 462
90 462
91 479
92 482
93 495
94 494
95 502
96 506
97 520
98 521
99 524
100 539
total 23471

```

---
Tags: code-challenge, sorting, test-battery
---


title: Stacking blocks

text:
# Question
Title: Stacking blocks
Given an input of a list of blocks to drop at certain points, output the height of the resulting "tower."

The best way to explain this challenge is by example. The input will be a list of *2n* integers representing *n* blocks. The first integer is the block's x position, 0-indexed, and the second is how wide the block is. For example, an input of `2 4` represents the block (with x coordinates labeled below):

```
  ####
0123456789

```

Now, let's say the input is `2 4 4 6`. That is, one block at x=2 with a width of 4, and one at x=4 with a width of 6:

```
    ######
  ####

```

Note that a.) blocks always "drop" from the very top of the tower and b.) blocks will never "fall over" (i.e. they will always balance). So, an input of `2 4 4 6 12 1` represents:

```
    ######
  ####      #

```

Note that the final block has fallen all the way to the "ground."

Your final output should be the maximum height of the tower at each x-value up to the largest. Hence, the input `2 4 4 6 12 1` should result in output `0011222222001`:

```
    ######
  ####      #
0011222222001

```

Input may be given as either a whitespace-/comma-separated string, an array of integers, or function/command line arguments. The block positions (x values) will always be integers 0 or greater, the width will always be an integer 1 or greater, and there will always be at least one block.

Output may be given as a single string separated by non-numerical characters (ex. `"0, 0, 1, ..."`), a single string listing all the digits (ex. `"001..."`—the maximum height is guaranteed to be 9 or less), or an array of integers.

Since this is , the shortest code in bytes will win.

Test cases:

```
In                                   Out
---------------------------------------------------------
2 4 4 6 12 1                         0011222222001
0 5 9 1 6 4 2 5                      1133333222
0 5 9 1 2 5 6 4                      1122223333
0 5 2 5 6 4 9 1                      1122223334
20 1 20 1 20 1                       00000000000000000003
5 5                                  000011111
0 2 1 2 2 2 3 2 4 2 5 2 6 2 7 2 8 4  123456789999

```

# Answer
## CJam, ~~34~~ 30 bytes

```
Lq~2/{eeWf%e~_2$:).*:e>f*.e>}/

```

Input as a CJam-style array, output as a string of digits.

Run all test cases.

Here are two variants of another idea, but it's currently 2 bytes longer:

```
Lq~2/{_:\3$><0+:e>)aeez.*e_.e>}/
LQ~2/{_:\3$><0+:e>)aeez.+e~.e>}/

```
> 2 votes

# Answer
## Python 3, 89

```
def f(a):
 h=[]
 while a:x,w,*a=a;h[:x+w]=(h+[0]*x)[:x]+[max(h[x:x+w]+[0])+1]*w
 return h

```

Try it online.

The function takes and returns a list of integers.

```
def f(a):                       # input as list of integers
  h=[]                          # list of heights
  while a:                      # while there's input left
    x,w,*a=a;                   # pop first 2 integers as x and w

    h[:x+w]=                    # change the heights between 0 and x+w
      (h+[0]*x)[:x]+            # left of x -> unchanged but padded with zeros
      [max(h[x:x+w]+[0])+1]*w   # between x and x+w -> set to the previous max + 1

  return h                      # return the list of heights

```
> 6 votes

# Answer
## Ruby, ~~88~~ 87 bytes

```
f=->i{o=[]
(s,l,*i=i
r=s...s+l
o[r]=[([*o[r]]+[0]).max+1]*l
o.map! &:to_i)while i[0]
o}

```

Try it online.

Inspired by grc's answer, but in a different language and just slightly shorter.

**Explanation:**

```
f=->i                        # lambda with parameter i, expects array of ints
{
    o=[]                     # output
    (
        s,l,*i=i             # pop start and length
        r = s...s+l          # range is used twice, so shorten it to 1 char
        o[r] =
            [(
                    [*o[r]]  # o[r] returns nil if out of bounds, so splat it into another array
                    +[0]     # max doesn't like an empty array, so give it at least a 0
            ).max+1]*l       # repeat max+1 to fill length
        o.map! &:to_i        # replace nil values with 0
    ) while i[0]             # i[0] returns nil when i is empty, which is falsy
    o                        # return o
}

```
> 2 votes

# Answer
## APL, 79 bytes

```
{⊃{o←(z←(≢⍵)⌈a←+/⍺)↑⍵⋄e←(z↑(-a)↑⍺[1]⍴1)⋄o+0⌈o-⍨e×e⌈.+e×o}/⌽(⊂⍬),↓(⌽2,0.5×≢⍵)⍴⍵}

```

Input as an APL Array, output as an APL array of digits.
> 1 votes

# Answer
### Java 1.8, ~~351~~ 329 bytes

Not thrilled with this first attempt - I'm sure the double looping, and all those Integer.valueOf's can be golfed some more.

```
interface B{static void main(String[]x){Byte b=1;int i=0,s,c,m=0,h,a=x.length,t[];for(;i<a;){s=b.valueOf(x[i++]);c=b.valueOf(x[i++]);m=m>s+c?m:s+c;}t=new int[m];for(i=0;i<a;){h=0;s=b.valueOf(x[i++]);c=b.valueOf(x[i++]);for(m=s;m<s+c;m++)if(t[m]>=h)h=t[m]+1;for(m=s;m<s+c;)t[m++]=h;}for(i=0;i<t.length;)System.out.print(t[i++]);}}

```

### Ungolfed

```
interface B {
static void main(String[]x){
    int start, count, maxWidth=0, height, args=x.length, totals[];
    Byte b=1;
    for (int i=0; i<args;){
        start = b.valueOf(x[i++]);
        count = b.valueOf(x[i++]);
        maxWidth = maxWidth>start+count ? maxWidth : start+count;
    }
    totals=new int[maxWidth];
    for (int i=0; i<args;){
        height=0;
        start = b.valueOf(x[i++]);
        count = b.valueOf(x[i++]);
        for (int j = start; j<start+count; j++) {
            if (totals[j]>=height) {
                height=totals[j]+1;
            }
        }
        for (int j = start; j<start+count; j++) {
            totals[j] = height;
        }
    }
    for (int i=0;i<totals.length; i++){
        System.out.print(totals[i]);
    }
}
}

```
> 0 votes

---
Tags: code-golf
---


# Question
Title: Write the prettiest bytebeat composition
Bytebeat is a style of music one can compose by writing a simple C program that's output is piped to `aplay` or `/dev/dsp`.

```
main(t){for(;;t++)putchar(((t<<1)^((t<<1)+(t>>7)&t>>12))|t>>(4-(1^7&(t>>19)))|t>>7);}

```

There is a good deal of information on the bytebeat site, a javascript implementation, and more demos and example compositions in this thread.

Very simple rules : Try to write a pretty sounding composition. Most up votes wins since that's obviously subjective, although not that subjective considering the usual results.

# Answer
> 16 votes
(Signed 16-bit little endian, 8000Hz mono (`--format=S16_LE`))

## Music

**Much** better than before! (although it's quite long)

`main(t){for(;;t++)putchar(((7&(((t>>17)+1)>>2)+((t>>10)&1+2*(t>>18&1))*(("23468643"[7&t>>12]-48)+(3&t>>11))+((3&t>>17)>0)*(3&t>>9)*!(1&t>>10)*(((2+t>>10&3)^(2+t>>11&3))))*t*"@06+"[3&t>>15]/32));}`

(You can listen this at here)

I wrote this, but even I don't know how some part works, like `>0` and (especially) the first `7&`.

Change for loop to `for(;!(t>>22);t++)`... to listen it 'once'. I don't know whether it "loops" exactly the same way, however.

## Melody (base of above music)

I love this melody I made (C-G-A-F ftw), but it's too 'plain'...

`main(t){for(;;t++)putchar(((t>>10)&1)*(t*("23468643"[7&t>>12]-48)+t*(3&t>>11))*"@06+"[3&t>>15]/32);}`

## Simple music (which I made before)

`main(t){for(;;t++)putchar(t*(3&t>>11)+(t&t>>11)*4*!((t>>11)%3));}`

# Answer
> 3 votes
The ruler function in C minor:

```
#include <math.h>
#include <stdio.h>

#define PI 3.14159265358979323846

#define step(freq, n) ((freq) * pow(2, (n) / 12.0))
#define note(n)       step(440, n)
#define MIDDLE_C      note(-9)

int count_zeros(unsigned int n)
{
    int count = 0;
    for (; (n & 1) == 0; n >>= 1)
        count++;
    return count;
}

int minor_note(int note)
{
    int octave = note / 7;
    int scale[] = {0, 2, 3, 5, 7, 8, 10};

    note %= 7;
    if (note < 0) {
        note += 7;
        octave--;
    }

    return scale[note] + octave*12;
}

int main(void) {
    double t = 0.0;
    double freq = MIDDLE_C * 2;
    double step = PI * 2 / 8192;
    int n = 0;
    int i = 0;

    for (i = 1;; t += step, i++) {
        if (i == 1024) {
            i = 0;
            n++;
            freq = step(MIDDLE_C, minor_note(count_zeros(n)));
        }

        putchar(sin(t * freq) * 50.0 + 128.0);
    }

    return 0;
}

```

# Answer
> 3 votes
```
main(t){for(;;t+=(t%6)?1:2)putchar((((t<<t^(t>>8))|(t<<7))*((t<<t&(t>>12))|(t<<10))));}

```

# Answer
> 3 votes
Emphasising "beat" over "byte":

```
#include<math.h>

double s(double,double);double r(double,double);double d(double);double f(double);

char bytebeat(int t){return (d(f(t/4000.)/3) + 1) * 63;}
double f(double t){
  double sn=s(1./2,t-1); sn*=(sn*sn);
  return 3*s(1./4,1/s(1,t))+3*s(4,1/sn)/2+s(4,1/(sn*sn*sn*sn*sn))/4
       +2*s(55+18.3*r(1./2,t),t)+s(110+s(5,t)/4000,t)*s(1,t)+s(220+110*r(1,t)+55*r(3,t),t)/5
       +s(880+440*r(1./2,t)-220*r(1,t)+110*r(2,t)+s(5,t)/4000,t)
       *(2+s(1760+438*r(3./2,t)-1234*r(2,t)+423*r(5,t),t))/9
       +s(s(1,t)+s(1./2,t)+s(1./4,t)+s(1./8,t),t)*s(s(1,t)+s(1./2,t)+s(1./4,t)+s(1./8,t)+1,t)
       +r(264+11*r(1./20,t),t)*s(1./20,t);
}
double s(double f,double t){return d(sin(f*3.14159265*(t+999)));}
double r(double f,double t){return s(f,t)<0;}
double d(double a){return tanh(a+a*a/4);}

main(t){for(;;++t)putchar(bytebeat(t));}

```

To be used at 8 kHz, uint8 mono. Sounds best over decently bass-capable loudspeakers.

# Answer
> 2 votes
```
main(){for(;;)putchar(rand());}

```

Sounds like the ocean ;-)

# Answer
> 0 votes
Combined melody and harmony:

```
r=3,
r=3,
m=(t*(t>>12|t>>13|t>>14|t>>15|t>>16|t>>17|t>>18))&63,

h= ((t&t>>7&t>>6)|t*5&t>>8-c^t*6&t>>9-c|t*7&t>>12-c^t*9&t>>11-c^t*11&t>>22^t*19&t>>20^t*14&t>>20|t*23&t>>15-c|t*12&t>>9|t*30&t>>30|t>>5|t>>4)-31, m|h

```

---
Tags: popularity-contest, c, music
---