# Question
Title: Write a program that turns every 17th bit of a text file to a 1
My coworker and I work on a legacy piece of software that we hate sometimes. Whenever you run it, debug asserts come flying everywhere, and it's never a guarantee that anything will work. The motivation for this round of code golf came from my coworker saying **the following about our software**.

*"It's like every time you run this program, you're agreeing to some terms of service that says every 17th bit on your hard drive will be turned into a 1"*

**Goal: Write a program that will make an exact copy of a file and turn every 17th bit of a text file into a 1**

* You may **NOT** turn **EVERY** bit of the file to a 1. i.e. your program must show some intelligence that it is only targeting every 17th bit
* You may **NOT** write to the original file in any way shape or form
* The **Winner** is the smallest program submission at the end of the month

Have fun with this one! Go!

# Answer
# CJam, 22 bytes

```
q256b2H#b1f|2H#b256b:c

```

Try it online.

Touches every 17th bit, counting from the last.

I've used STDIN and STDOUT since CJam has no file I/O. If that's not allowed, the program can be wrapped in a Bash script at the cost of 24 extra bytes:

```
cjam <(echo q256b2H#b1f\|2H#b256b:c)<"$1">"$2"

```

### How it works

```
q                      " Read from STDIN.                                                 ";
 256b                  " Convert to integer by considering the input a base 256 number.   ";
     2H#b              " Convert to array by considering the integer a base 2**17 number. ";
         1f|           " Set the LSB of every integer in the array element to 1.          ";
            2H#b       " Convert to integer by considering the array a base 2**17 number. ";
                256b   " Convert to array by considering the integer a base 256 number.   ";
                    :c " Turn character codes into characters.                            ";

```
> 9 votes

# Answer
## Perl 59

regex substitution on bit strings:

```
$/=$\;$_=unpack"B*",<>;s|(.{16}).|${1}1|g;print pack"B*",$_

```

usage:

```
perl this.pl < infile.txt > outfile.txt

```
> 6 votes

# Answer
# C, 125

**Assumes big-endian and 16-bit integers**.

Works by applying a bitwise-OR on every two bytes.

Input file is `y`, output is `z`.

```
unsigned a,b;main(c){void*f=fopen("y","r"),*g=fopen("z","w");while(b=fread(&c,1,2,f))c|=a,a?a/=2:(a=32768),fwrite(&c,1,b,g);}

```

Ungolfed

```
// The commented out /* short */ may be used if int is not 16 bits, and short is.
unsigned /* short */ a = 0,b;
main(/* short */ c){
    void *f = fopen("y", "r"), *g = fopen("z", "w");
    while(b = fread(&c, 1, 2, f)){
      // __builtin_bswap16 may be used if you are using GCC on a little-endian machine.
      //c = __builtin_bswap16(c);
        c |= a;
        if(a) a >>= 1;
        else a = 32768;
      //c = __builtin_bswap16(c);
        fwrite(&c, 1, b, g);
    }
}

```
> 2 votes

# Answer
# Python 2, 112 bytes

```
b=open('i').read().encode('hex')
open('o','w').write(('%x'%(int('1'+b,16)|16**len(b)/131071))[1:].decode('hex'))

```

This sets every 17th big-endian bit, starting 17th from the beginning. It uses no libraries. It works by converting the input file to a gigantic `n`-bit integer and bitwise ORing with `2**n/(2**17 - 1) == 0b10000000000000000100000000000000001…`.
> 2 votes

# Answer
# C - 139

Reads from a file named "i", outputs to a file named "o".

```
c;main(){unsigned char b,m=1;void *i=fopen("i","r"),*o=fopen("o","w");for(;(b=fgetc(i))<129;fputc(b,o))((c+=8)%17<8)?b|=m=(m-1)?m/2:128:0;}

```

With line breaks:

```
c;main()
{
    unsigned char b,m=1;
    void *i=fopen("i","r"),*o=fopen("o","w");
    for(;(b=fgetc(i))<129;fputc(b,o))
        ((c+=8)%17<8)?b|=m=(m-1)?m/2:128:0;
}

```

Counts bits of input and then uses a floating bitmask to set every seventeenth bit.
> 1 votes

# Answer
# Java - 247

Uses a `BitSet` and a simple loop instead of handling/masking the bytes manually. Of course this being java, the boilerplate is half the program, so it's not exactly short.

Still, *not last!* :D

```
import java.util.*;import java.nio.file.*;class F{public static void main(String[]a)throws Exception{BitSet b=BitSet.valueOf(Files.readAllBytes(Paths.get(a[0])));for(int j=0;j<b.size();b.set(j),j+=17);Files.write(Paths.get("o"),b.toByteArray());}}

```

No-scroll version:

```
import java.util.*;
import java.nio.file.*;
class F{
    public static void main(String[]a)throws Exception{
        BitSet b=BitSet.valueOf(Files.readAllBytes(Paths.get(a[0])));
        for(int j=0;j<b.size();b.set(j),j+=17);
        Files.write(Paths.get("o"),b.toByteArray());
    }
}

```
> 1 votes

# Answer
## Python - 98 bytes

Read from i, write to o. Uses bitarray library https://pypi.python.org/pypi/bitarray

```
from bitarray import*;a=bitarray();a.fromfile(open('i','rb'));a[::17]=1;a.tofile(open('o','wb'))

```

ungolfed

```
from bitarray import *
a=bitarray()
a.fromfile(open('i','rb'))
a[::17]=1
a.tofile(open('o','wb'))

```
> 1 votes

# Answer
# Cobra - 308

```
use System.Text.RegularExpressions
class P
    def main
        t,b='',File.readAllBytes('x')
        for n,i in b.numbered,for l in 8,b[n]=if(l,b[n],0)+if(Regex.replace(t+='00000000'[(j=Convert.toString(i,2)).length:]+j,'.{17}',do(m as Match)='[m]'[:-1]+'1')[n*=8:n+8][7-l]<c'1',0,2**l)to uint8
        File.writeAllBytes('y',b)

```

Every time I do one of these 'manipulate the individual bits of something' challenges, I wish that either Cobra or the .NET standard library had a `binary string => integer` converter.
> 0 votes

# Answer
# Javascript (+HTML5), 282

Probably not the shortest, but it's user friendly :D

It's cross browser, but it seems that chrome is the only one allowing it when the html file is a local file (= access with `file://...`). For the other browsers, you need to put it on a web server.

The output file should be saved to the default download directory, maybe with a file prompt (depending on your configuration).

```
<input type=file onchange="r=new FileReader();r.onloadend=function(){w=window;a=new Uint8Array(r.result);for(i=17;i<a.length*8;i+=17)a[i/8>>0]|=1<<8-i%8;w.location.replace(w.URL.createObjectURL(new Blob([a],{type:'application/octet-binary'})));};r.readAsArrayBuffer(this.files[0])">

```

Ungolfed version :

```
<input type=file onchange="
    var reader = new FileReader();
    reader.onloadend = function() {
        var arr = new Uint8Array(reader.result);
        for(var i = 17 ; i < arr.length * 8 ; i += 17) {
            arr[Math.floor(i / 8)] |= 1 << (8 - (i % 8));
        }
        window.location.replace(
            window.URL.createObjectURL(
                new Blob([arr], {type: 'application/octet-binary'})
            )
        );
    };
    reader.readAsArrayBuffer(this.files[0]);
">

```
> 0 votes

# Answer
# Python 3 - 187 bytes

---

Reads in from `i` and writes to `o`.

Code:

```
o=open;j="".join;f=list(j(format(x,"08b")for x in o("i","rb").read()))
f[16::17]="1"*(len(f)//17)
with o("o","wb") as f2:f2.write(bytes(int(j(f[i*8:(i+1)*8]),2)for i in range(len(f)//8)))

```

Ungolfed:

```
# read file and convert to binary string e.g. "101010010101010101"
f = list("".join(format(x, "08b") for x in open("in.txt", "rb").read()))
# set every 17th bit to 1
f[16::17] = "1" * (len(f)//17)
with open("out.txt","wb") as f2:
    data = []
    for i in range(len(f)//8)): # for each byte
        byte = "".join(f[i*8:(i+1)*8] # get each byte
        data.append(int(byte),2) # convert to int
    f2.write(bytes(data)) # convert to byte string and write

```
> 0 votes

# Answer
# Python 3 - 103 chars

Change `f` to the path of the file you want to read and `o` to path of the file you want to write to.

```
l=open;t=list(l(f,'r').read())
for i in range(len(t)):
 if i%18==0:t[i]='1'
l(o,'w').write(''.join(t))

```
> -1 votes

---
Tags: code-golf, bitwise
---


title: Score a game of Load, Defend and Shoot

text:
# Question
Title: Score a game of Load, Defend and Shoot
When I was a child, I used to play this game a lot.

### Rules

There are two players (let's call them A and B), and each player uses his hands as guns. There are three possible moves:

1. Hands up to load ammunition to your gun.

Each gun starts empty. Loading increases the ammunition by one.
2. Hands pointing to the other player to shoot.

This decreases the ammunition by one. You must have at least one unit of ammo to shoot.
3. Crossed arms to protect yourself from a shot.

Both players move simultaneously. If both players shoot at the same time, the bullets hit each other, and the game continues. The game ends when one player shoots while the other is loading ammunition.

Shooting and empty gun is considered *cheating*. If a player cheats while the other one performs a legal action, the cheater loses immediately. If both players cheat at the same time, the game continues.

Cheating attempts do not decrease ammunition, so it can never be negative.

### Challenge

Given the moves made by players A and B, output which player won the game: `1` for player A, `-1` for player B, and `0` for a draw. You can use any other triple of return values, but you need to state in your answer which ones you use.

The game may:

* end without having to process all moves;
* not end with the given moves, and thus it is considered a draw.

The input can be taken:

* as strings
* as arrays/lists of integers
* in any other way that does not pre-process the input

Full program or functions allowed. Since this is , the shortest answer in bytes wins!

### Test cases

```
A: "123331123"
B: "131122332"
    -----^                Player B shoots player A and wins.

Output: -1

```

```
A: "111322213312"
B: "131332221133"
    -------^              Player B cheats and loses.

Output: 1

```

```
A: "1333211232221"
B: "1213211322221"
    ----------^^          Both players cheat at the same time. The game continues.

Output: 0

```

```
A: "12333213112222212"
B: "13122213312232211"
         |       || ^---- Player A shoots player B and wins.
         ^-------^^------ Both players cheat at the same time. The game continues.

Output: 1

```

# Answer
> 6 votes
# Jelly, ~~33~~ ~~32~~ 24 bytes

```
Zæ%1.»0$+¥\>-‘żZḅ3Ff5,7Ḣ

```

This prints **5** instead of **-1**, and **7** instead of **1**. Try it online! or verify all test cases.

### How it works

```
Zæ%1.»0$+¥\>-‘żZḅ3Ff5,7Ḣ  Main link. Argument: A (digit list array)

Z                         Zip; group corresponding digits.
 æ%1.                     Map the digits in (-1.5, 1.5].
                          This replaces [1, 2, 3] with [1, -1, 0].
          \               Cumulatively reduce the pairs by doing the following.
     »0$                    Take the maximum of the left value and 0, i.e., replace
                            a -1 with a 0.
        +¥                  Add the modified left value to the right value.
                          This computes the available ammo after each action. An
                          ammo of -1 indicates a cheating attempt.
           >-             Compare the results with -1.
             ‘            Increment. And unilateral cheating attempt is now [1, 2]
                          or [2, 1], where 1 signals the cheater and 2 the winner.
              żZ          Pair each result with the corr., original digits.
                ḅ3        Convert each pair from base 3 to integer.
                          This maps [1, 2] and [2, 1] to 5 and 7.
                  F       Flatten the resulting, nested list.
                   f5,7   Discard all but 5's and 7's.
                       Ḣ  Grab the first element (5 or 7).
                          If the list is empty, this returns 0.

```

# Answer
> 2 votes
# Pyth, ~~48~~ ~~46~~ ~~49~~ 47 bytes

```
.xhfT|M.e,-FmgF.b/<dhkY2S2Q?}b_BS2-FbZ.b,NYCQ)0

```

Try it here!

Thanks to @isaacg for saving ~~2~~ 4 bytes!

Takes input as a 2-tuple with the list of the moves of player A first and the moves of player B second. Output is the same as in the challenge.

## Explanation

### Short overview

* First we group the moves of both players together, so we get a list of 2-tuples.
* Then we map each of those tuples to another 2-tuple in the form `[cheating win, fair win]` with the possible values `-1, 0, 1` for each of it, to indicate if a player won at this point (`-1, 1`) or if the game goes on (`0`)
* Now we just need to get the first tuple which is not `[0,0]`, and take the first non-zero element of it which indicates the winner

### Code breakdown

```
.xhfT|M.e,-FmgF.b/<dhkY2S2Q?}b_BS2-FbZ.b,NYCQ)0  # Q = list of the move lists

                                      .b,NYCQ    # pair the elements of both input lists
       .e                                        # map over the list of pairs with
                                                 # b being the pair and k it's index
            m             Q                      # map each move list d
               .b      2S2                       # map over [1,2], I can't use m because it's
                                                 # lambda variable conflicts with the one from .e
                  <dhk                           # d[:k+1]
                 /    Y                          # count occurences of 1 or 2 in this list
          -F                                     # (count of 1s)-(count of 2s), indicates cheating win
                           ?}b_BS2               # if b is (1,2) or (2,1)
                                  -Fb            # take the difference, indicates fair win
                                     Z           # else 0, no winner yet
         ,                                       # pair those 2 values
     |M                                          # For each resulting pair, take the first one if
                                                 # its not zero, otherwise the second one
   fT                                            # filter all zero values out
.xh                                              # try to take the first value which indicates the winner
                                             )0  # if thats not possible because the list is empty
                                                 # output  zero to indicate a draw

```

# Answer
> 1 votes
## Java, ~~226~~ ~~212~~ ~~200~~ ~~196~~ 194 bytes

*-14 bytes by re-ordering logic*

*-12 bytes thanks to Mr Public pointing out how to use a ternary operation for the shooting logic*

*-4 bytes by cramming load logic into one short-circuiting if*

*-2 bytes because `==1` === `<2` when input can only be `1`,`2`,`3`*

```
(a,b)->{for(int m=0,n=0,w,v,r=0,i=0,x;i<a.length;){w=a[i];v=b[i++];x=w==2?m<1?r--:m--:0;x=v==2?n<1?r++:n--:0;if(r!=0)return r;if(w<2&&++m>0&v==2)return -1;if(v<2&&++n>0&w==2)return 1;}return 0;}

```

Usage and indented version:

```
static BiFunction<Integer[], Integer[], Integer> game = (a,b) -> {
    for(int m=0,n=0,w,v,r=0,i=0,x;i<a.length;) {
        w=a[i];v=b[i++];
        // shoot
        x=w==2?m<1?r--:m--:0;
        x=v==2?n<1?r++:n--:0;
        if(r!=0)return r;
        // load
        if(w<2&&++m>0&v==2)return -1;
        if(v<2&&++n>0&w==2)return 1;
    }
    return 0;
};

public static void main(String[] args) {
    System.out.println(game.apply(new Integer[] {1,2,3,3,3,1,1,2,3}, new Integer[] {1,3,1,1,2,2,3,3,2}));
    System.out.println(game.apply(new Integer[] {1,1,1,3,2,2,2,1,3,3,1,2}, new Integer[] {1,3,1,3,3,2,2,2,1,1,3,3}));
    System.out.println(game.apply(new Integer[] {1,3,3,3,2,1,1,2,3,2,2,2,1}, new Integer[] {1,2,1,3,2,1,1,3,2,2,2,2,1}));
}

```

Not so straightforward implementation of the game rules anymore, but simple. Each cycle, does these operations:

* Load moves into temp variables
* If player shot
    + without ammo: bias cheate`r` towards losing
    + with ammo: decrement ammo
* If cheate`r` is not `0`, return the value because someone cheated
* If player reloaded
    + increment ammo
    + if other player shot, return loss

`x` is a dummy variable used to make the compiler let me use a ternary expression.

Wait, Java is SHORTER than Python?

# Answer
> 1 votes
# Python, 217 bytes

```
def f(A,B):
 x=y=0;c=[-1,1,0]
 for i in range(len(A)):
  a=A[i];b=B[i]
  for s in[0,1]:
   if(a,b)==(2,1):return c[s]*c[x<1]
   if(a,b)==(2,3)and x<1:return-c[s]
   x-=c[a-1];x+=x<0;a,b,x,y=b,a,y,x
 return 0

```

**Explanation**: Takes A and B as lists of integers. Simply goes through each pair of moves, adds or subtracts 1 if needed and returns when someone cheats or wins. Does the same thing twice using another for loop, once for A's move and once for B's move. Adds 1 if x goes below 0 to -1.

---
Tags: code-golf, game
---


# Question
Title: Print the difference in the Thue-Morse sequence
*Note, when I say "negate", I mean replace all ones with zeroes (i.e. a bitwise negation)*

The Thue-Morse sequence goes like 01101001

The way you generate it is:

Start by taking 0. Negate what is left and append it to the end.

So, take `0`. Negate it and add that to the end - `01`

Then take that and negate it and add that to the end - `0110`

And so on.

Another interesting property of this is that distance between zeros creates an "irrational" and non-repeating string.

So:

```
0110100110010110
|__|_||__||_|__|
 2  1 0 2 01 2          <------------Print this!

```

**Can you write a program that, when input n, will output the first n digits of the string to printed?**

This is code golf, so shortest number of bytes wins!

# Answer
> 2 votes
# Jelly, 9 bytes

```
;¬$‘¡TI’ḣ

```

Try it online!

### How it works

```
;¬$‘¡TI’ḣ  Main link. Argument: n

  $        Create a monadic chain that does the following to argument A (list).
 ¬         Negate all items of A.
;          Concatenate A with the result.
   ‘¡      Execute that chain n + 1 times, with initial argument n.
     T     Get all indices of truthy elements (n or 1).
      I    Compute the differences of successive, truthy indices.
       ’   Subtract 1 from each difference.
        ḣ  Keep the first n results.

```

# Answer
> 4 votes
# Python ~~3~~ 2, ~~104~~ ~~92~~ ~~88~~ 84 bytes

This is a pretty rudimentary solution based on building a ternary Thue-Morse sequence from scratch. This sequence is identical to the one being asked, though someone else will have to write a more thorough explanation of why that is. At any rate, this sequence is only a trivial modification of this one, A036580.

**Edit:** Changed the for loop into a list comprehension, changed from a function to a program, and changed the whole thing to Python 2. Thanks to Dennis for golfing help.

```
n=input()
s="2"
while len(s)<n:s="".join(`[1,20,210][int(i)]`for i in s)
print s[:n]

```

# Answer
> 3 votes
# Mathematica, ~~79~~ ~~68~~ 70 bytes

```
(Differences[Join@@Position[Nest[#~Join~(1-#)&,{0},#+2],0]]-1)[[;;#]]&

```

# Answer
> 3 votes
# Julia, ~~56~~ 50 bytes

```
n->(m=1;[m=[m;1-m]for _=0:n];diff(find(m))[1:n]-1)

```

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

We generate the bit-swapped Thue-Morse sequence by starting with an integer `m = 1`, then we append `1-m` to `m` as an array `n+1` times, where `n` is the input. This generates more terms than we need. We then locate the ones using `find(m)`, get the difference between consecutive values using `diff`, and subtract 1 elementwise. Taking the first `n` terms of the resulting array gives us what we want.

Saved 6 bytes and fixed an issue thanks to Dennis!

# Answer
> 3 votes
# MATL, ~~14~~ 11 bytes

```
Q:qB!Xs2\dQ

```

**Try it online!**

As pointed out by @TimmyD in his answer, the desired sequence is given by the consecutive differences of A001969. The latter can in turn be obtained as the Thue-Morse sequence plus 2\**n*. Therefore the desired sequence is given by the *(consecutive differences of the Thue-Morse sequence) plus one*.

On the other hand, the Thue-Morse sequence can be obtained as the number of ones in the binary representation of *n*, starting from *n*=0.

```
Q:q    % take input n implicitly and generate row vector [0,1,...,n]
B!     % 2D array where columns are the binary representations of those numbers
Xs     % sum of each column. Gives a row vector of n+1 elements
2\     % parity of each sum
d      % consecutive differences. Gives a row vector of n elements
Q      % increase by 1. Display implicitly

```

# Answer
> 3 votes
## PowerShell, 102 bytes

```
filter x($a){2*$a+([convert]::toString($a,2)-replace0).Length%2}
0..($args[0]-1)|%{(x($_+1))-(x $_)-1}

```

A little bit of a different way of computing. PowerShell doesn't have an easy way to "get all indices in this array where the value at that index equals *such-and-such*", so we need to get slightly creative.

Here we're using A001969, the "numbers with an even number of 1s in their binary expansion", which *completely coincidentally* gives the indices of the 0s in the Thue-Morse sequence. ;-)

The `filter` calculates that number. For example, `x 4` would give `9`. We then simply loop from `0` to our input `$args[0]`, subtracting `1` because we're zero-indexed, and each iteration of the loop print out the difference between the *next* number and the current number. Output is added onto the pipeline and implicitly output with newlines.

### Example

```
PS C:\Tools\Scripts\golfing> .\print-the-difference-in-the-thue-morse.ps1 6
2
1
0
2
0
1

```

# Answer
> 3 votes
## Haskell, 42 bytes

```
l=2:(([[0..2],[0,2],[1]]!!)=<<l)
(`take`l)

```

Usage example: `(`take`l) 7` -\> `[2,1,0,2,0,1,2]`.

It's an implementation of `a036585_list` from A036585 shifted down to `0`, `1` and `2`. Golfing: `concat (map f l)` is `f =<< l` and `f 0=[0,1,2]; f 1=[0,2]; f 2=[1]` is `([[0..2],[0,2],[1]]!!)`.

Note: `l` is the infinite sequence. It takes 10 bytes or about 25% to implement the take-first-`n`-elements feature.

# Answer
> 2 votes
# 05AB1E, ~~14~~ 13 bytes

Code:

```
ÎFDSÈJJ}¥1+¹£

```

Explanation:

```
Î              # Push 0 and input
 F     }       # Do the following n times
  DS           # Duplicate and split
    È          # Check if even
     JJ        # Join the list then join the stack
        ¥1+    # Compute the differences and add 1
           ¹£  # Return the [0:input] element

```

Try it online!

# Answer
> 2 votes
## Python, 69 bytes

```
t=lambda n:n and n%2^t(n/2)
lambda n:[1+t(i+1)-t(i)for i in range(n)]

```

The `i`th term of this sequence is `1+t(i+1)-t(i)`, where `t` is the Thue-Morse function. The code implements it recursively, which is shorter than

```
t=lambda n:bin(n).count('1')%2

```

# Answer
> 1 votes
## JavaScript (ES6), ~~73~~ 67 bytes

```
f=(n,s="2")=>s[n]?s.slice(0,n):f(n,s.replace(/./g,c=>[1,20,210][c]))

```

Port of @Sherlock9's answer.

edit: Saved 6 bytes thanks to @WashingtonGuedes.

# Answer
> 1 votes
# Perl, 45 + 2 = 47 bytes

```
$_=2;s/./(1,20,210)[$&]/ge until/.{@F}/;say$&

```

Requires the `-p` and `-a` flag:

```
$ perl -pa morse-seq.pl <<< 22
2102012101202102012021

```

Port of @Sherlock9 answer

Saved 9 bytes thanks to Ton

# Answer
> 1 votes
# Mathematica, 58 bytes

```
Differences[Nest[Join[#,1-#]&,{0},#]~Position~0][[;;#]]-1&

```

# Answer
> 1 votes
# Mathematica, 65 bytes

```
SubstitutionSystem[{"0"->"012","1"->"02","2"->"1"},"0",#][[;;#]]&

```

Beats my other answer, but doesn't beat the extra-~~spicy~~golfed version. Now normally I stick my code in quotes, then pull it out because Mathematica loves adding spaces to your code (which do nothing) but it never messes with strings, but that doesn't work for code that itself has quotes...

Whatever, I'm just using the magic builtin for this. Output is a string.

# Answer
> 1 votes
## CJam (19 bytes)

```
1ri){2b:^}%2ew::-f-

```

Online demo

This uses the approach of incrementing the successive differences between elements of the Thue-Morse sequence.

---

My shortest approach using rewriting rules is 21 bytes:

```
ri_2a{{_*5*)3b~}%}@*<

```

(Warning: slow). This encodes the rewriting rules

```
0  ->  1
1  ->  20
2  ->  210

```

as

```
x -> (5*x*x + 1) in base 3

```

# Answer
> 0 votes
# Mathematica (~~almost~~ nonverbal), ~~107~~ 110 bytes

```
({0}//.{n__/;+n<2#}:>{n,{n}/.x_:>(1-x)/._[x__]:>x}//.{a___,0,s:1...,0,b___}:>{a,+s/.(0->o),0,b}/.o->0)[[;;#]]&

```

The sequence is generated by repeatedly applying a replacement rule. Another rule transforms it to the desired output. If enough people are interested, I'll explain in detail.

**non-alphanumeric version**

```
({$'-$'}//.{$__/;+$/#
<($'-$')!+($'-$')!}:>
{$,{$}/.$$_:>(($'-$')
!-$$)/.{$$__}:>$$}//.
{$___,$'-$',$$:($'-$'
)!...,$'-$',$$$___}:>
{$,+$$/.($'-$'->$$$$)
,$'-$',$$$}/.$$$$->$'
-$')[[;;#]]

```

as suggested by CatsAreFluffy.

# Answer
> 0 votes
# Ruby, 57 bytes

A port of xnor's Python answer. The changes mostly lie in the ternary statement in `t` in place of the `and` due to `0` being truthy in Ruby, and using `(1..n).map` and `1+t[i]-t[i-1]` to save bytes vs. importing the list comprehension directly.

```
t=->n{n<1?n:n%2^t[n/2]}
->n{(1..n).map{|i|1+t[i]-t[i-1]}}

```

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


title: Creating a falling ball map

text:
# Question
Title: Creating a falling ball map
### Introduction

For the ones who never heard of this game before. You are playing a ball which needs to survive as long as possible. This is done by moving to the left or right, going to the holes. Since the map moves upwards, you need to go downwards to survive longer. If you search for images, you probably know which game I mean.

### The Task

Given a positive integer *n*, output a falling ball map of *n* layers. Between the layers, there are 4 newlines. The width of the layer is made up of 25 underscore characters, with **one** hole of length 5. That means that the total width is equal to 30. This is randomly shifted after each layer. An example of a valid layer is:

```
_______________     __________

```

The hole can also be at the edges, as if the layer is like a cylinder:

```
  _________________________

```

Note that there are 2 leading spaces and 3 trailing spaces. Making a *single* hole of width 5.

### Test cases

For *n*=4, this is a valid output:

```
_______________     __________

______     ___________________

_______________________     __

  _________________________

```

Note: the holes must be *uniformly* distributed. Trailing and/or leading newlines are allowed.

This is , so the submission with the least amount of bytes wins!

# Answer
# Pyth, 19 bytes

```
VQ.>+*\_25*d5O30*b4

```

Try it here!

# Explanation

```
VQ.>+*\_25*d5O30*b4  # Q = input

VQ                   # Repeat Q times
     *\_25           # 25 underscores
          *d5        # 5 spaces
    +                # concat the underscores and spaces
  .>         O25     # rotate this string 0-29 times
                *b4  # print the seperating newlines

```
> 6 votes

# Answer
# Ruby, 74 71 59

Thanks to Alex A. for reminding me that being basically one line means I can use the stabby lambda

```
f=->n{n.times{puts (('_'*25+' '*5)*2)[rand(30),30]+"\n"*5}}

```
> 4 votes

# Answer
# Pyth, 19 bytes

```
VQ.>r"5 25_"9O30*4b

```

Try it here

Thanks to FryAmTheEggman for catching a bug.
> 3 votes

# Answer
# Julia, 72 bytes

```
n->join([join(circshift(["_"^25*" "^5...],rand(1:30)))"\n"^5 for i=1:n])

```

This is an anonymous function that accepts an integer and returns a string. To call it, assign it to a variable.

We construct a string of 25 underscores followed by 5 spaces, then splat that into an array of characters. We circularly shift it a random number of times (between 1 and 30), join it back into a string, and tack on 5 newlines. This process is repeated *n* times, where *n* is the input. The resulting array is joined and returned.

Try it here
> 3 votes

# Answer
# PowerShell 65 Bytes

```
0..$args[0]|%{-join("_"*25+" "*5)[($r=Random 25)..($r-29)];,""*5}

```

Run a loop for *n* iterations. Get a random number and make a underscore string with 5 spaces at the end. Index into the the string as an array to pull starting from a random location. Negative indexing wraps from the end. Join that back up again and append 5 newlines.

Edit: I don't know why I thought I needed the parameter for `-Maximum` as it's positional. Thanks to TimmyD I shaved some bytes and forgot to get input so that drove me back up to 65.
> 3 votes

# Answer
# MATL, 23 bytes

```
:"95l25X"5Z"h30YrYS10ct

```

**Try it online!**

### Explanation

```
:"           % take input n implicitly. Repeat loop n times
  95l25X"    %   row vector with number 95 ('_') repeated 25 times
  5Z"        %   row vector of 5 blank spaces
  h          %   concatenate vertically
  30Yr       %   random number uniformly distributed on [1,2,...,30]
  YS         %   circularly shift
  10c        %   newline character. Includes another newline when printed
  t          %   duplicate
             % implicitly end loop and display stack contents

```
> 2 votes

# Answer
## Java, ~~177~~ 140 bytes

*-1 byte to Blue moving the i++*

*-2 bytes to me leaving meaningless whitespace in the original<br>*

*-34 bytes to Blue for realizing I didn't need the char\[\] at all*

Because, ya know, Java.

```
n->{String s="";for(;n-->0;){int r=(int)(Math.random()*30);for(int i=0;i<30;){s+=i>r&i<r+6|r>24&i++<=r%25?" ":"_";}s+="\n\n\n\n";}return s;}

```

Slightly ungolfed:

```
Function<Integer, String> fallingBall = n -> {
    String s = "";
    for (;n-->0;) {
        int r = (int)(Math.random()*30);
        for (int i=0; i<30; i++) {
            s += i>r&i<r+6|r>24&i<=r%25?" ":"_";
        }
        s += "\n\n\n\n";
    }
    return s;
}

```

Since Java doesn't have a String 'rotate', I had to take a different approach. I generated a random int 0-29 that represents the start index of the hole (OBO because `>` is shorter than `>=`). Each individual character is then decided by the logic

```
l[index] = (index>random && index<random+6) || (random>24 && index<=random%25) ? ' ' : '_';

```

This handles the "wrapping" nature of the whole.
> 2 votes

# Answer
# SpecBAS - 93 bytes

```
1 a$="_"*25+" "*5: INPUT n: FOR i=1 TO n: r=1+INT(RND*30): ?a$(r TO)+a$( TO r-1)''''': NEXT i

```

Makes a string of 25 underscores + 5 spaces, picks a random start point and splices the string at that position and tacks the start of string to end.

The apostrophe forces a newline, so 1 at end of string and 4 empty lines.
> 2 votes

# Answer
# Python, ~~119~~ 103 bytes

```
import random
s='_'*20+' '*5
def f(n,a=random.randint(0,25)):[print(s[a:]+s[:a]+3*'\n')for _ in' '*n]

```
> 1 votes

# Answer
# Python 3.5 - 109 113 bytes (+4 for printing out 4 new lines between each result):

```
def g(a,j='_'*25+' '*5):
 for l in range(a):import random;n=random.randrange(len(j)+1);print(j[-n:]+j[:-n]+'\r'*4)

```

# Ungolfed Form:

```
# j is the starting string with the 25 underscores and then 5 spaces at the end
def g(a,j='_'*25+' '*5):
    import random #Import the random module
    for l in range(a): # Do the following as many times as provided by the user
        n=random.randrange(len(j)+1) Get a random number in the range 0-29
        print(j[-n:]+j[:-n]+'\r'*4) #Shift the string characters right "n" times and print out the results with 4 new lines in between

```

Basically what is going on is that a string 'j', consisting of 25 underscore followed by 5 spaces, is given as an argument to the function "g". Then, the random module is imported, and, as many times as specified by the user, a random number is chosen in the range `0 => 29`, and the string, "j", is shifted right that many times. The result is then printed out after each iteration, with 4 new lines in between each result.
> 1 votes

---
Tags: code-golf, string, random
---


title: Commutation of 27 functions

text:
# Question
Title: Commutation of 27 functions
## Introduction

Let's define a *ternary function* as a function from the three-element set `S = {0,1,2}` to itself: it associates to each element of `S` another element of `S`. One example of a ternary function `f` is

```
f(0) = 0; f(1) = 2; f(2) = 0

```

There are exactly 27 different ternary functions, and we represent them with integers from 0 to 26: a function `f` is encoded as `f(0) + 3*f(1) + 9*f(2)`. The example function above is encoded as the number 6.

We can apply two ternary functions `f` and `g` in sequence, and if `f(g(k)) == g(f(k))` holds for all `k` in `S`, then the functions *commute*. Your task is to verify whether this is the case.

## Input

Your inputs are two integers in the inclusive range from 0 to 26. They represent two ternary functions `f` and `g`. Input must be taken in decimal, binary or unary (string of `1`s) format.

## Output

Your output is a truthy value if `f` and `g` commute, and a falsey value if they don't. You may not assume that the inputs are ordered.

## Examples

Consider the inputs 5 and 16. They encode the ternary functions

```
f(0) = 2; f(1) = 1; f(2) = 0
g(0) = 1; g(1) = 2; g(2) = 1

```

We have `f(g(1)) == f(2) == 0` and `g(f(1)) == g(1) == 2`, so `f` and `g` don't commute and the correct output is falsey.

On the other hand, the inputs 3 and 10 encode the ternary functions

```
f(0) = 0; f(1) = 1; f(2) = 0
g(0) = 1; g(1) = 0; g(2) = 1

```

and it can be verified that `f(g(k)) == g(f(k))` holds for all `k` in `S`. Then the correct output is truthy.

Here is the 27×27 table of all possible inputs, with `+` marking a truthy output and `-` a falsey output:

```
+ - - + - - + - - + - - + - - + - - + - - + - - + - -
- + - - - - - - - - - - + - - - - - - - - + - - - - -
- - + - - - - - - - - - - - - - - - - - - + - - + - -
+ - - + - - - - - - + - - + - - - - + - - + - - - - -
- - - - + - - - - - - - - + - - - - - - - + - - - - -
- - - - - + - - - - - - - + - - - - - - - + - - - - -
+ - - - - - + - - - - - - - - - - - - - - + - - - - -
- - - - - - - + - - - + - - - - - - - - - + - - - - -
- - - - - - - - + - - - - - - - - - + - - + - - - - -
+ - - - - - - - - + - - - - - - - - - - - + - - - - -
- - - + - - - - - - + - - - - - - - - - - + - - - - -
- - - - - - - + - - - + - - - - - - - - - + - - - - -
+ + - - - - - - - - - - + + - - - - - - - + + - - - -
- - - + + + - - - - - - + + + - - - - - - + + + - - -
- - - - - - - - - - - - - + + - - - - - - + - - - - -
+ - - - - - - - - - - - - - - + - - - - - + - - - - -
- - - - - - - - - - - - - - - - + - - - - + - + - - -
- - - - - - - - - - - - - - - - - + - - - + + - - - -
+ - - + - - - - + - - - - - - - - - + - - + - - - - +
- - - - - - - - - - - - - - - - - - - + - + - - - - +
- - - - - - - - - - - - - - - - - - - - + + - - - - +
+ + + + + + + + + + + + + + + + + + + + + + + + + + +
- - - - - - - - - - - - + + - - - + - - - + + - - - +
- - - - - - - - - - - - - + - - + - - - - + - + + - +
+ - + - - - - - - - - - - - - - - - - - - + - + + - +
- - - - - - - - - - - - - - - - - - - - - + - - - + +
- - - - - - - - - - - - - - - - - - + + + + + + + + +

```

## Rules and scoring

You can write a full program or a function. The lowest byte count wins, and standard loopholes are disallowed.

# Answer
> 4 votes
# Jelly, ~~17~~ ~~14~~ 13 bytes

```
+13ḃ3Um0ị2/⁼/

```

Try it online! or verify all 27×27 cases.

### How it works

```
+13ḃ3Um0ị2/⁼/  Main link. Argument: [f, g] (encoded as integers)

+13            Add 13 ([1, 1, 1] in base 3) to f and g.
   ḃ3          Convert f + 13 and g + 13 to bijective base 3.
               Bijective base 3 uses the digits 1 to 3 instead of 0 to 2.
               This yields [[f(2)+1, f(1)+1, f(0)+1], [g(2)+1, g(1)+1, g(0)+1]].
               The increments account for 1-based indexing.
     U         Reverse each digit array.
               This yields [[f(0)+1, f(1)+1, f(2)+1], [g(0)+1, g(1)+1, g(2)+1]].
      m0       Concatenate the list with a reversed copy of itself.
        ị2/    Split the result into pairs, and reduce each one by indexing.
               This computes g○f and f○g.
          ⁼/   Reduce by match; return 1 iff g○f = f○g.

```

# Answer
> 3 votes
# MATL, ~~19~~ 18 bytes

```
I:PII$YAZ{Y:)1Mw)=

```

Truthy is an array with all ones. Falsy is an array containing at least one zero.

Try it online! or verify all cases (takes a few seconds).

```
       % implicitly input an array of two numbers
I:P    % push [3 2 1]
I      % push 3
I$     % specify that the next function takes 3 inputs
YA     % convert input to base 3 with alphabet [3 2 1] and 3 digits. Gives 2x3 array
Z{     % convert into cell of two cells, one with each row
Y:     % split cell array. We have two arrays on the stack, one per function
)      % index operation to compute f ∘ g. Function composition is indexing
1M     % push the two arrays again
w      % swap the two arrays
)      % index operation to compute g ∘ f
=      % test for equality element-wise
       % implicitly display

```

# Answer
> 3 votes
## Python 2, 61 bytes

```
lambda m,n:all(n/3**(m/i%3)%3==m/3**(n/i%3)%3for i in[1,3,9])

```

Given an input `i`, we can implement the function represented by `n` by doing `n/3**i%3` to extract the `i`th ternary digit of `n`. The function checks that the same result is gotten for each of `0,1,2` when applying the functions in either order. Actually, since the first step is doing `3**`, this tests with `[1,3,9]` instead.

The code reuse looks wasteful, but I didn't see a better way. Compare:

```
q=lambda x,i:x/3**i%3;lambda m,n:all(q(m,q(n,i))==q(n,q(m,i))for i in[0,1,2])

```

# Answer
> 1 votes
# JavaScript (ES7), 68 bytes

```
(a,b)=>![0,1,2].some(n=>t(a,t(b,n))-t(b,t(a,n)),t=(a,n)=>a/3**n%3|0)

```

Unfortunately base 3 conversion was too expensive:

```
(a,b)=>[0,1,2].every(n=>a[b[n]]==b[a[n]],g=a=>(27+a).toString(3).slice(1),a=g(a),b=g(b))

```

# Answer
> 0 votes
# Mathematica, 77 bytes

```
Reverse[#][[#2+{1,1,1}]]==Reverse[#2][[#+{1,1,1}]]&@@IntegerDigits[{##},3,3]&

```

Mathematica's One-based indexing strikes again!

---
Tags: code-golf, number, decision-problem
---


title: Golomb's sequence to 1000000

text:
# Question
Title: Golomb's sequence to 1000000
This used to be an old Computer Olympiad Question, not sure what the actual source was.

Assume function `f`:

* `f(1) = 1`
* This `f(1), f(2), f(3), f(4), ...` sequence of numbers are in ascending order.
* Number `n` has been repeated `f(n)` times

Here is the sequence up to the fifteenth number:

```
n :     1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
f(n) :  1 2 2 3 3 4 4 4 5  5  5  6  6  6  6

```

for example number `4` has been repeated `f(4) = 3` times.

So what you should do is to print out the sequence till f(1000000). There are no inputs.

Also you can run out of memory, not an issue! Code with less bytes wins.

So this is how to output will look like: `1 2 2 3 3 4 4 4 5` ...

# Answer
## CJam (22 bytes)

```
1{_~$(~$-)~$)}A6#(/]S*

```

Online demo for only 15 terms

This relies on one of the formulae given in the entry for OEIS A001462, and the use of `~$` to index the stack from the bottom.
> 2 votes

# Answer
# Ruby, 55 bytes

Dynamic programming-style solution. Generates the table iteratively, and then prints the needed terms.

```
f,i=[0],0
f+=[i+=1]*(f[i]||i)while f.size<1e6
p f[1,1e6]

```
> 1 votes

# Answer
# MATL, ~~25~~ 22 bytes

```
FTTQ`@2+yy)1X"!htn1e7<

```

**Try it online** replacing `1e7` in the code by a more manageable number, such as `1e2`

This initiallizes the sequence as `[1 2 2]`, and from that builds the rest of the sequence applying its definition.
> 0 votes

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


title: Music Interval Solver

text:
# Question
Title: Music Interval Solver
In music theory, an interval is the difference between two pitches. Each pitch is defined by the number of half-steps (The difference between C and C#) or whole steps (The difference between C and D). One whole step is the same as two half-steps. Here is a list of all the default intervals and the number of half-steps they represent:

```
0     Perfect Unison
2     Major Second
4     Major Third
5     Perfect Fourth
7     Perfect Fifth
9     Major Sixth
11    Major Seventh
12    Perfect Octave

```

There are 3 variations on the default intervals, **minor**, **diminished**, and **augmented**.

* A **minor** interval is one half-step lower than a major interval, but not a perfect interval. So you have a minor second (1), a minor third (3), a minor sixth (8), and a minor seventh (10). There is no such thing as a minor fourth, minor fifth, minor unison or minor octave since these are all perfect intervals.
* A **diminished** interval is one half-step lower than a minor *or* perfect interval. There is diminished Second (0), diminished third (2), diminished fourth (4), diminished fifth (6), diminished sixth (7), diminished seventh (9) and diminished octave (11).
* An **augmented** interval is one half-step *higher* than a major or perfect interval. We have Augmented Unison (1), Augmented Second (3), Augmented third (5), Augmented Fourth (6), Augmented fifth, (8), Augmented sixth (10), and Augmented seventh (12).

# The challenge:

You must write a program or function that takes a number of half steps or whole steps and then prints *one of* the valid English descriptions of this interval. It doesn't matter which description you pick, as long as it exactly matches the IO table. You can take this as one string

```
"5w" == 5 whole steps
"3h" == 3 half steps

```

or as a number and a string/char.

```
5, "w" == 5 whole steps
3, "h" == 3 half steps.

```

You can assume that every input will be between 0 and 12 half steps.

# IO table

Here is a full list mapping the number of half-steps to all acceptable outputs.

```
0       Perfect unison, Diminished second
1       Minor second, Augmented unison
2       Major second, Diminished third
3       Minor third, Augmented second
4       Major third, Diminished fourth
5       Perfect fourth, Augmented third
6       Diminished fifth, Augmented fourth
7       Perfect fifth, Diminished sixth
8       Minor sixth, Augmented fifth
9       Major sixth, Diminished seventh
10      Minor seventh, Augmented sixth
11      Major seventh, Diminished octave
12      Perfect octave, Augmented seventh

```

Here is some sample I/O:

```
5w      Minor Seventh
5h      Augmented Third
12h     Perfect Octave
12w     UNDEFINED
1w      Diminished third
2h      Major Second

```

# Answer
# Ruby, Rev B 138 bytes

```
->n,s{i=12-n-n*(s<=>?h)
[a='Augmented','Major','Minor',d='Diminished',a,'Perfect',d][i%7]+' '+%w{seventh fifth third unison}[i%7/4+i/7*2]}

```

5 bytes saved by not repeating `Augmented/Diminished`. 1 byte saved by use of `?h`.

# Ruby, Rev A 144 bytes

```
->n,s{i=12-n-n*(s<=>'h')
%w{Augmented Major Minor Diminished Augmented Perfect Diminished}[i%7]+' '+%w{seventh fifth third unison}[i%7/4+i/7*2]}

```

The idea is to minimise the number of basic intervals (seventh fifth third and unison only) and take advantage of the fact that sevenths and fifths have an analogous relationship to that between thirds and unisons.

There are four types of seventh/third and 3 types of fifth/unison so the index variable `i` is set to 12 minus the number of half steps, so that the first term of the expression `i%7/4 + i/7*2` will correctly select the type of basic interval.

**ungolfed in test program**

```
f=->n,s{                 #n = number of steps. s= step size, w or h
  i=12-n-n*(s<=>'h')     # i=12-n. If s is later in the alphabet than 'h' subtract again for whole steps
  %w{Augmented Major Minor Diminished Augmented Perfect Diminished}[i%7]+
  ' '+%w{seventh fifth third unison}[i%7/4+i/7*2]
}

-1.upto(12){|j|
puts f[j,'h']
}

0.upto(6){|j|
puts f[j,'w']
}

```

**output**

```
Diminished unison
Perfect unison
Augmented unison
Diminished third
Minor third
Major third
Augmented third
Diminished fifth
Perfect fifth
Augmented fifth
Diminished seventh
Minor seventh
Major seventh
Augmented seventh

Perfect unison
Diminished third
Major third
Diminished fifth
Augmented fifth
Minor seventh
Augmented seventh

```

Undefined behaviour inputs: The function gives the correct answer of `diminished union` for -1 halfsteps, but fails for inputs over 12. For example, it outputs `perfect unison` for 14 half steps, as the algorithm is based on a cycle of 14 rather than 12.
> 2 votes

# Answer
# Python 2.7, 155 bytes

```
s='second unison third fourth sixth fifth seventh octave Diminished Augmented'.split()
def f(n,c):x=0xDE9CB87561430>>[4,8][c>'h']*n;print s[x%2+8],s[x/2%8]

```
> 2 votes

# Answer
## Python 2, 149 bytes

```
def f(n,c):n*=1+(c>'h');print(n-6)%13%2*"Diminished"or"Augmented",'octave seventh sixth fifth fourth third second unison'.split()[71056674174>>3*n&7]

```

First, whole steps are converted to half steps.

Then, `Diminished` vs `Augmented` is printed. These alternate for adjacent `n` except that `n=5` and `n=6` give the same, which is achieved by first putting them across a boundary modulo an odd number.

Finally, the distance is printed, computed via a three-bit lookup table. This is shorter than doing `int('6746543230210'[n])`.
> 2 votes

# Answer
# Retina, 153 bytes

```
\d+
$*
(.*)w|h
$1$1
^1*$
$.0
^[02479]|11
Diminished $0
^\d
Augmented $0
10|7
sixth
11
octave
12|9
seventh
8
fifth
4|6
fourth
5|2
third
1
unison
\d
second
```

Input number is first converted to unary, then doubled if followed by `w`, and any letters are removed, leaving only the unary number. This number is then converted back to decimal. Finally, some search and replace is applied to construct the final output.

Example runs:

```
6w => 111111w  => 111111111111 => 12 => Augmented 12 => Augmented seventh
7h => 1111111h => 1111111      => 7  => Diminished 7 => Diminished sixth
3w => 111w     => 111111       => 6  => Augmented 6  => Augmented fourth
0h => h        =>              => 0  => Diminished 0 => Diminished second
```

Try it online!
> 1 votes

# Answer
# Vitsy, 166 bytes

Well, this can definitely be further golfed.

```
WW2M1+*a+mZ
'dehsinimiD'
'roniM'
'rojaM'
'tcefreP'
'detnemguA'
'dnoces '
'htruof '
'htxis '
'evatco '
6m1m
6m2m
6m3m
6m5m
7m1m
7m4m
7m5m
8m1m
8m2m
8m3m
8m5m
9m1m
9m4m

```

This works by defining the minimal amount of items possible, then calling those items through the method syntax.

Try it Online!
> 0 votes

# Answer
## Java, ~~225~~ 224 bytes

There has got to be a better way to pack these strings but I don't have any ideas.

```
(i,s)->{String A="Augmented",M="Major",m="Minor",P="Perfect",D="Diminished",d=" Second",f=" Fourth",a=" Sixth",C=" Octave";String[]o=new String[]{D+d,m+d,M+d,A+d,P+f,A+f,D+a,m+a,M+a,A+a,D+C,P+C};i*=s=='w'?2:1;return o[i-1];}

```

Indented:

```
static BiFunction<Integer, Character, String> interval = (i,s) -> {
    String A="Augmented",M="Major",m="Minor",P="Perfect",D="Diminished",
            d=" Second",f=" Fourth",a=" Sixth",C=" Octave";
    String[] o = new String[] {D+d,m+d,M+d,A+d,P+f,A+f,D+a,m+a,M+a,A+a,D+C,P+C};
    i *= s=='w' ? 2 : 1;
    return o[i-1];
};

```
> 0 votes

# Answer
# Javascript 189 bytes

```
a=>(n='sutsftfxFvxov'[N=parseInt(a)*(a.slice(-1)>'v'?2:1)])&&((N>5?N+1:N)%2?'Augmented ':'Dimished ')+'unison,second,third,fourth,fifth,sixth,seventh,octave'.split`,`['ustfFxvo'.indexOf(n)]

 F=
  a=>
    (n='sutsftfxFvxov' //using the right side of the possible answers
                       //set n = the letter representing
                       //unison, first, second ...

       //set N to 12 for 12h, but 24 for 12w
       [N=parseInt(a)*(a.slice(-1)>'v'?2:1)])

  &&   //if we were out of range (12w) we'll return undefined

    (
      (N>5?N+1:N)%2?  //get Aug or Dim (right side goes)
                      //DADADAADADADA
                      //     ^^ makes this a pain
       'Augmented ':'Dimished '
     )
     +
            //turn n (which is u for unison, x for sixth, etc
            //into it's full name
       'unison,second,third,fourth,fifth,sixth,seventh,octave'
         .split`,`
     ['ustfFxvo'.indexOf(a)]

```
> 0 votes

---
Tags: code-golf, music
---


title: Random array without repetition

text:
# Question
Title: Random array without repetition
I was answering one challenge here and this task was part of the challenge. I've got a 73 bytes solution in javascript. But I think it is too much for a simple thing.

### Challenge

Given as input two integers:

* `N` the length of the expected array
* `R` the interval's range starting in one: `1..R`, not `0..R-1`

Output in each run of your program/function one different array of length `N` with values between `1..R` in such a way no one value occurs more than once.

You must use `R-value` in your code.

### Restrictions

You can assume: `2 <= N <= R`.

I really would like to see a javascript solution shorter than mine 73 bytes.

But of course, it is open to all languages!

If your language can not return an array, you can print all the numbers ;)

# Answer
## Dyalog APL, 1 byte

```
?

```

Just a builtin. Try it here.
> 16 votes

# Answer
# JavaScript (ES6), ~~68~~ 66 bytes

```
n=>r=>G=(s=new Set)=>s.size<n?G(s.add(Math.random()*r+1|0)):[...s]

```

Called as `F(N)(R)()`, where `F` is the function assignment, and `N`/`R` are the values.

You asked for shorter than 73 bytes in Js ;)

EDIT: The answer by @C5H8NNaO4 works within the fact that the rules don't specify the values must be uniform across `1..R`. Given that, here's a version works in 63 bytes (called as `F(R)(N)`):

```
r=>G=(n,s=[])=>n--?G((s[n]=n+1,n),s):s.sort(a=>new Date/a%1-.5)

```
> 9 votes

# Answer
# Octave, ~~22 19~~ 9 bytes

```
@randperm

```

`randperm(r,n)` does exactly what is requested. Note that this does not work (at least not in oldder versions) in Matlab.
> 7 votes

# Answer
# MATL, 2 bytes

```
Zr

```

Inputs are: first `R`, then `N`.

**Try it online!**

### Explanation

The function `Zr` takes two inputs (implicitly in this case) and does a random sampling without replacement. The first input, `R`, specifies that the population is `[1,2,...,R]`; and the second input, `N`, indicates the number of samples to take from the population.
> 5 votes

# Answer
## TI-84 BASIC OS 4.0, 12 bytes

```
Prompt N,R:randIntNoRep(1,R,N

```

The TI-84+ CSE (2013) and the CE (2015) are essentially the same limited BASIC dialect as the TI-84+, but there are a few new features. One of them is randIntNoRep's third argument.
> 5 votes

# Answer
# Pyth, 6 bytes

```
<.SSQE

```

Try it here!

Range comes on the first line and the length on the second.

# Explanation

```
<.SSQE    # Q = range, E = length

   SQ     # generate the range 1...Q
 .S       # shuffle the list
<    E    # take the first E elements

```

## Non-competing 5-byte version

The lastest addition to Pyth adds implicit `Q`s at the end of the program if needed. We can use this here by reversing the input format, so the length comes first and then the range.

```
<.SSE

```

Try it here!

Here `E` is the range, which we turn into a 1-based list with `S`, shuffle it with `.S` and take the first `Q` elements with `<`. `<` expects an integer which is implicitly added with a `Q`.
> 4 votes

# Answer
# J, ~~4~~ 3 bytes

One byte saved thanks to Zgarb! (Crossed out four is still a regular four :D)

```
1+?

```

call like `N (1+?) R`, e.g., `3 (1+?) 10`. This uses the "Roll" operator, and does exactly what is described, except under `0...n-1`. If we were allowed to do this, then the answer would be 1 byte,

```
?

```
> 4 votes

# Answer
# Reng v.2.1, ~~140~~ ~~103~~ ~~98~~ 97 bytes

This should work in earlier versions, too.

```
v      v      $/$'l#y0#z>(:)):(ez+#z zt>a$;!
>i#ci#x>cu1+lxetv    j21\!q   yy#-1y($/^
>n?~v
^oW <

```

You can try it here! Input is `maximum length`, such as `10 3`.

I am so proud of this, you don't even know. If someone beats me with a Java answer, that will make my day. If I beat a Java answer, consider my day made as well.

I will explain it more later, once I recover. Generally, though:

```
v         v      $/$r$
>i#bbi1+#x>:u1+lxet

```

This generates the random numbers. The other part checks if there are duplicates, and, if there are, the process is repeated. Else, the results are printed, with spaces joining the results.

Here are some examples:
> 4 votes

# Answer
# CJam, 8 bytes

```
{,:)mr<}

```

Try it here!

This is an unnamed block which expect the range on top of the stack and the length at the bottom and leaves a list on the stack.

# Explanation

```
,   e# 0-based range
:)  e# inkrement each element of the list so its 1-based
mr  e# shuffle the list
<   e# take the first n elements

```
> 3 votes

# Answer
# Bash + coreutils, 16

I think this is self-explanatory:

```
seq $2|shuf -n$1

```

Input `N` and `R` as command-line parameters.

Or as @rici points out, for the same score:

```
shuf -n$1 -i1-$2

```

Ideone.
> 2 votes

# Answer
# Ruby, ~~27~~ 23 bytes

Anonymous function, reasonably short and sweet.

-4 bytes from @manatwork

```
->n,r{[*1..r].sample n}

```
> 2 votes

# Answer
## Common Lisp, 90

**52** for the expression only

```
(use-package :alexandria)(lambda(R N)(coerce(subseq(shuffle(iota R :start 1))0 N)'vector))

```

### Ungolfed

```
;; Well known library
(use-package :alexandria)

(lambda(R N)
  (coerce                   ; make a vector from a list
    (subseq                 ; take the sublist from 0 to N
      (shuffle              ; shuffle a list
        (iota R :start 1))  ; build a list from 1 to R
    0 N)
    'vector))

```

Like other answers, if I don't count *use-package* and *lambda*, the remaining expression is `(coerce(subseq(shuffle(iota R :start 1))0 N)'vector)`, for 52 bytes.
> 2 votes

# Answer
# , 10 chars / 13 bytes

```
Ѩŝ⩤⁽1í)ą-î

```

`Try it here (Firefox only).`

# Explanation

```
           // implicit: î=input1, í=input2
  ⩤⁽1í)    // Inclusive range from 1 to í
Ѩŝ         // Shuffle resulting range
       ą-î // Get last îth items

```
> 2 votes

# Answer
## PowerShell v2+, 30 bytes

```
param($n,$r)1..$r|Random -c $n

```

Takes input `$n` and `$r`, constructs a range `1..$r`, pipes that to `Get-Random` with a `-C`ount of `$n`, which will select `$n` unique elements from the range. Output is left on the pipeline as an implicit array.
> 1 votes

# Answer
## Seriously, 5 bytes

```
,,R╨J

```

Try it online!

Explanation:

```
,,R╨J
,,R    push N, range(1, R+1)
   ╨   push a list containing all N-length permutations of range(1, R+1)
    J  select a random element from the list

```
> 1 votes

# Answer
# Python 3.5 - 54 53 bytes:

```
from random import*;lambda a,c:sample(range(1,c+1),a)

```

This uses the random module's `sample()` function to return an array with length "a" consisting of random, unique elements in the range `1 => c`.
> 1 votes

# Answer
# Clojure, 38 bytes

```
#(take %1(shuffle(map inc(range %2))))

```

An anonymous function taking N first and R second.
> 1 votes

# Answer
# Perl 6, 32 bytes

```
{(^$^a).permutations.pick[^$^b]}

```
> 1 votes

# Answer
# D, 29 bytes (expression only)

Assuming that std.random and std.range have been imported and that n and r are defined as variables, the program can be solved in the single expression:

```
iota(1,r).randomCover.take(n)

```
> 1 votes

# Answer
**ES6, 72**

```
r=>n=>[...Array(-~r).keys()].sort(a=>new Date/a%1-.5).filter(a=>a&&n-->0)

```

Like in @Mwr247's answer, you can call it with `F(R)(N)`, `F` being the function expression
> 1 votes

# Answer
# Mathcad, 67 "bytes"

creates a column vector of consecutive integers in range 1..R, joins it to a column vector of length R of (uniform) random numbers, sorts the resulting Rx2 matrix on the random number column, and then extracts the first n numbers from the randomized column of integers.
> 0 votes

# Answer
# Python, 56 (the obvious way)

```
lambda N,R:__import__('random').sample(range(1,R+1),k=N)

```
> 0 votes

# Answer
# TI-84 BASIC, 21 bytes

```
Prompt R,N:randIntNoRep(1,R→A:N→dim(ʟA:ʟA

```
> 0 votes

# Answer
# Perl 5, ~~51~~ 43 bytes

```
sub{@a=1..pop;map{splice@a,rand@a,1}1..pop}

```

Pretty straightforward anonymous sub that generates an array from 1 to R and then splices N random elements from it to return. Call with `->(N, R)`.
> 0 votes

---
Tags: code-golf, random, permutations
---


# Question
Title: Print out a shape in printable ASCII art based on a specific number of sides provided by the user
# The Challenge:

Just as the title says, your challenge is to use the printable ASCII characters to create a program that prints out a random polygon in the terminal based on the number of sides, *n* provided by the user, where n is an integer in the range `3 -> 10` including 3 and 10, in as few bytes as possible.

**For example:**

If n = 4 it should print out a 4 sided shape. For instance, it may print out a square, like so:

```
 ______
|      |
|      |
|______|

```

However, if the program is called again with the same attribute of n=4, it should print out a different polygon based on the same number of sides. For instance, maybe a plain, old parallelogram this time, like so:

```
    ______________
   /             /
  /             /
 /_____________/

```

As another example, consider n=6. At least once, it should print out a 6-sided polygon, such as the convex hexagon shown below:

```
    ________
   /        \
  /          \
 /            \
 \            /
  \          /
   \________/

```

But another time, it should print out a visually different polygon with 6 sides, for instance, maybe a concave hexagon like the following:

```
________
\      /
 \    /
  \  /
  /  \
 /    \
/______\

```

Finally, as a last example, if n=3, it may print out an isosceles triangle:

```
    / \
   /   \
  /_____\

```

However, another call with the same attribute should print out another kind of triangle, maybe like the following right triangle:

```
    /|
   / |
  /__|

```

**EDIT:** To fulfill @CatsAreFluffy's request, here is an example of an ASCII nine-sided polygon:

```
    ___
   /   \
  /     \
 /       \
 \       /
  \     /
   \   /
   /   \
  /     \
 /       \
 \       /
  \     /
   \   /
    \ /
     v

```

**NOTE: These are all just *examples*. Your polygons can be drawn in any style, as long as they meet the guidelines shown below.**

# Guidelines:

* Each number of sides, from 3-10, should have at least 2 different shapes associated with it.
* The program should print out a random shape from the shapes associated with each number of sides each time the program is executed with a specific number of visually distinguishable sides in the range `3 -> 10` given as an argument.
* The sides of the each polygon can be any length, such that every shape able to be drawn by the entire program has at least one side with the same length as all the others. For instance, a triangle should have at least one side with the same length as one of the sides of a parallelogram. So should the square, pentagons, rectangles, etc. with the parallelogram, and also with each other. As a reference, in the examples given in the challenge sections, each shape has at least one side with a length of 3 slashes.
* Standard loopholes apply.

# Answer
> 9 votes
# Java, ~~1887~~ 1866 bytes

Try in on Ideone

Saved 21 bytes due to unneeded "public" headers (Thanks to @Bálint!)

Not exactly a golfing challenge, but hey, why not?

I feel Java might actually be the best language for this challenge because no esolang could handle this, and many others don't have as good list manipulation (although Java's takes way more bytes).

Golfed:

```
import java.util.*;public class A{public static void main(String[]args){System.out.print((new P()).b(Integer.parseInt((new Scanner(System.in)).next())).s());}}class P{S p;public S b(int w){p=new S(w);int j=-1,k=-1,f=(w%2)*2,t,y,x;for(x=0;x<w/2-2+w%2;x++){t=r();y=r();if(j==t|k==y|t==y){x--;continue;}g(t,true,2);g(y,false,2-f);f=0;j=t;k=y;}while(1>0){t=r();y=r();if(w<4&t<1&y<1)continue;if(j==t|k==y|t==y|j==y){x--;continue;}g(t,true,3);g(y,false,3+(w<4?0:(w%2)*2));break;}return p;}void g(int w,boolean b,int h){if(w<1)p.u(h,b);else if(w<2)p.r(h,b);else p.l(h,b);}int r(){return (int)(Math.random()*3);}}class S{List<List<Character>>q,a;int h,s,u,o,e,r,b,t,g,n,m,x,y;public S(int d){s=d;h=s+s%2-1;u=h;o=h;b=s>3?(int)(Math.random()*3*s)+1:0;q=new ArrayList<List<Character>>();a=new ArrayList<List<Character>>();for(x=0;x<h;x++){q.add(new ArrayList<Character>());a.add(new ArrayList<Character>());}i(0,q);i(0,a);e=1;r=1;t=0;g=0;n=0;m=0;}public String s(){String p="";for(x=0;x<e+b+r;x++)p+=x>t+(s<4?1:0)&x<e+b+g?'_':' ';p+="\n";for(y=0;y<h;y++){for(x=0;x<e;x++)p+=y>h-2&x>n?'_':q.get(y).get(x);for(x=0;x<b;x++)p+=y>h-2?'_':' ';for(x=0;x<r;x++)p+=y>h-2&x<m-1?'_':a.get(y).get(x);p+="\n";}return p;}void i(int i,List<List<Character>>z){for(List<Character>l:z)l.add(i,' ');if(z==q){e++;if(i<=t)t++;if(i<=n)n++;}else{r++;if(i<=g)g++;if(i<=m)m++;}}void u(int v,boolean i){if(i){u-=v;for(y=0;y<v;)q.get(u+y++).set(t,'|');}else{o-=v;for(y=0;y<v;)a.get(o+y++).set(g,'|');}}void l(int v, boolean i){if(i){x=v-t;while(x-->0)i(0,q);t=x>0?0:t-v;u-=v;for(y=0;y<v;)q.get(y+u).set(t+y++,'\\');}else{x=v-g;while(x-->0)i(0,a);g=x>0?0:g-v;o-=v;for(y=0;y<v;)a.get(y+o).set(g+y++,'\\');}}void r(int v,boolean i){if(i){t+=v;y=t;while(e<=y)i(e,q);t=y-1;u-=v;for(y=0;y<v;)q.get(u+y).set(t-y++,'/');}else{g+=v;y=g;while(r<=y)i(r,a);g=v<1?g:y-1;o-=v;for(y=0;y<v;)a.get(o+y).set(g-y++,'/');}}}

```

Must be in file called `A.java` (for obvious reasons). To run:

1. In the terminal, type `javac A.java`
2. Then, if it gives you no errors, type `java A`
3. Finally, type the number of sides. This program actually supports side lengths up to 65536

As you can see in the example output below, the corners tend to be more open, and the sides not as smooth, as compared to the polygons in the examples. Also, it cannot produce a square, but still follows the official guidelines. If there are any problems I can change the answer to fix them.

Sample output:

```
3

  / |
 /  |
/___|

4
   ____
  /    \
 /      \
/________\

5
   _________
  /         |
 /          |
/           |
\           |
 \ _________|

6
  ____________
 |            \
 |             \
 |              \
 /               |
/_______________ |

7
 _____________________
\                     /
 \                   /
  \                 /
   |               /
   |              /
   \              \
    \ _____________\

8
 _______________
\               /
 \             /
  \           /
   |          \
   |           \
   /            |
  /____________ |

9
 __________
\          /
 \        /
  \      /
   |    /
   |   /
   /   \
  /     \
  |      |
  |_____ |

10
   ____
  /    \
 /      \
/        \
|         /
|        /
\        |
 \       |
  /      \
 /________\

```

EDIT: Finally! the ungolfed code is here! It's a bit long, but you probably already guessed that...

I will get to the explanation soon.

```
import java.util.*;
public class ASCII_Polygon_Driver
{
   public static void main(String[] args)
   {
      System.out.print(P.b(Integer.parseInt((new Scanner(System.in)).next())));
   }
}
class P
{
   static S p;
   public static S b(int w)
   {
      p = new S(w);
      int l1=-1,l2=-1,f=(w%2)*2,r1,r2,x;
      for(x=0;x<w/2-2+w%2;x++)
      {
         r1=r();
         r2=r();
         if(l1==r1){x--;continue;}
         if(l2==r2){x--;continue;}
         if(r1==r2){x--;continue;}
         g(r1,true,2);
         g(r2,false,2-f);
         f=0;
         l1=r1;
         l2=r2;
      }
      while(true)
      {
         r1=r();
         r2=r();
         if(w<4&r1<1&r2<1)continue;
         if(l1==r1|l2==r2|r1==r2|l1==r2){x--;continue;}
         g(r1,true,3);
         g(r2,false,3+(w<4?0:(w%2)*2));
         break;
      }
      return p;
   }
   static void g(int w,boolean b,int h)
   {
      if(w<1)p.goUp(h,b);
      else if(w<2)p.goRight(h,b);
      else p.goLeft(h,b);
   }
   static int r()
   {
      return (int)(Math.random()*3);
   }
}
class S
{
   public List<List<Character>> area1;
   public List<List<Character>> area2;
   private int wid1;
   private int wid2;
   private int spcb;
   public int hght;
   private int top1;
   private int top2;
   private int bot1;
   private int bot2;
   private int mid1;
   private int mid2;
   public int sides;
   private int x;
   private int y;
   public int y1;
   public int y2;
   public S(int numSides)
   {
      sides = numSides;
      hght = sides+sides%2-1;
      y1=hght;
      y2=hght;
      spcb = sides>3?(int)(Math.random()*3*sides)+1:0;
      area1 = new ArrayList<List<Character>>();
      area2 = new ArrayList<List<Character>>();
      for(x=0;x<hght;x++)
      {
         area1.add(new ArrayList<Character>());
         area2.add(new ArrayList<Character>());
      }
      insertCollum1(0);
      insertCollum2(0);
      wid1 = 1;
      wid2 = 1;
      top1 = 0;
      top2 = 0;
      bot1 = 0;
      bot2 = 0;
   }
   public String toString()
   {
      String out ="";

      for(x=0; x<wid1+spcb+wid2; x++)
      {
         out+=x>top1+1&x<wid1+spcb+top2?'_':' ';
      }
      out+="\n";
      for(y=0; y<hght; y++)
      {
         for(x=0; x<wid1; x++)out+=y>hght-2&x>bot1?'_':area1.get(y).get(x);
         for(x=0; x<spcb; x++)out+=y>hght-2?'_':' ';
         for(x=0; x<wid2; x++)out+=y>hght-2&x<bot2-1?'_':area2.get(y).get(x);
         out+="\n";
      }
      return out;
   }
   private void insertCollum1(int index)
   {
      for(List<Character> line : area1)
      {
         line.add(index,' ');
      }
      wid1++;
      if(index<=top1)top1++;
      if(index<=bot1)bot1++;
   }
   private void insertCollum2(int index)
   {
      for(List<Character> line : area2)
      {
         line.add(index,' ');
      }
      wid2++;
      if(index<=top2)top2++;
      if(index<=bot2)bot2++;
   }
   /*private void setChar1(int x, int y, char character, List<List<Character>> which)
   {
      which.get(y).set(x,character);
   }*/
   public void goUp(int howMany, boolean is1)
   {
      if(is1)
      {
         y1-=howMany;
         for(y=0;y<howMany;)
         {
            area1.get(y1+y++).set(top1,'|');
         }
      }
      else
      {
         y2-=howMany;
         for(y=0;y<howMany;)
         {
            area2.get(y2+y++).set(top2,'|');
         }
      }
   }
   public void goLeft(int howMany, boolean is1)
   {
      if(is1)
      {
         x = howMany-top1;
         while(x-->0)insertCollum1(0);
         top1 = Math.max(0,top1-howMany);
         y1-=howMany;
         for(y=0;y<howMany;)
         {
            area1.get(y+y1).set(top1+y++,'\\');
         }
      }
      else
      {
         x = howMany-top2;
         while(x-->0)insertCollum2(0);
         top2 = Math.max(0,top2-howMany);
         y2-=howMany;
         for(y=0;y<howMany;)
         {
            area2.get(y+y2).set(top2+y++,'\\');
         }
      }
   }
   public void goRight(int howMany,boolean is1)
   {
      if(is1)
      {
         top1+=howMany;
         y=top1;
         while(wid1<=y)insertCollum1(wid1);
         top1=y-1;
         y1-=howMany;
         for(y=0;y<howMany;)
         {
            area1.get(y1+y).set(top1-y++,'/');
         }
      }
      else
      {
         top2+=howMany;
         y=top2;
         while(wid2<=y)insertCollum2(wid2);
         top2=howMany<1?top2:y-1;
         y2-=howMany;
         for(y=0;y<howMany;)
         {
            area2.get(y2+y).set(top2-y++,'/');
         }
      }
   }
}

```

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


title: Fun with flags!

text:
# Question
Title: Fun with flags!
Write a full program with a source code of 256 bytes or less that looks at an image of a flag and determines what country that flag is from. A zip file containing the 196 different flags in the challenge can be downloaded from here. Source: \[Flagpedia\]. These 196 flag images are the only inputs your program has to handle.

Your program will take no input. The flag image will be in the same directory as your program and named "f.png". Your program will open this file, identify it, and print the two letter abbreviation for that country. If you use a language that can't open files, it's also acceptable to run your program as `./program < f.png`.

Each flag file is named the same as the expected output. All output above 2 letters will be ignored.

Here is a list of all the outputs/filenames:

```
ad, ae, af, ag, al, am, ao, ar, at, au, az, ba, bb, bd, be, bf, bg, bh, bi, bj,
bn, bo, br, bs, bt, bw, by, bz, ca, cd, cf, cg, ch, ci, cl, cm, cn, co, cr, cu,
cv, cy, cz, de, dj, dk, dm, do, dz, ec, ee, eg, eh, er, es, et, fi, fj, fm, fr,
ga, gb, gd, ge, gh, gm, gn, gq, gr, gt, gw, gy, hn, hr, ht, hu, id, ie, il, in,
iq, ir, is, it, jm, jo, jp, ke, kg, kh, ki, km, kn, kp, kr, ks, kw, kz, la, lb,
lc, li, lk, lr, ls, lt, lu, lv, ly, ma, mc, md, me, mg, mh, mk, ml, mm, mn, mr,
mt, mu, mv, mw, mx, my, mz, na, ne, ng, ni, nl, no, np, nr, nz, om, pa, pe, pg,
ph, pk, pl, pt, pw, py, qa, ro, rs, ru, rw, sa, sb, sc, sd, se, sg, si, sk, sl,
sm, sn, so, sr, st, sv, sy, sz, td, tg, th, tj, tl, tm, tn, to, tr, tt, tv, tw,
tz, ua, ug, us, uy, uz, va, vc, ve, vn, vu, ws, ye, za, zm, zw,

```

# Scoring

Here is a short python script that I will use to score each submission.

```
import os
import subprocess
import random

botlist = []
with open("bots.txt") as bots:
    for line in bots:
        line = line.split(", ")
        if len(line) >= 2:
            botLine = line + [0]
            botlist.append(botLine)

files = os.listdir(os.getcwd() + "/flags")
random.shuffle(files)

def test(bot_command):
    score = 0
    for filename in files:
        command = "COPY flags\\{} f.png".format(filename)
        os.system(command)

        print bot_command

        result = subprocess.check_output(bot_command, shell = True)
        if result[:2] == filename[:2]:
            score += 1

    return score

for i in range(len(botlist)):
    command = botlist[i][1]
    botlist[i][2] = test(command)

with open("output.txt", "w+") as output:
    for bot in botlist:
        output.write("{} got a score of {}.".format(bot[0], bot[2]))

os.system("del f.png")

```

Your score is the total number of flags correctly identified. In case of a tie, the earlier submission wins.

# Rules

* For my testing convenience, any language with a freely available interpreter/compiler for Windows 10 or Ubuntu can be used.
* Image processing libraries are allowed, but any builtins related to flags or countries are not allowed. (*cough* Mathematica *cough*)
* Please provide the full command needed to run your program along with links to any necessary libraries.
* Submissions may not interact with any file except "f.png".
* I don't have any hard time-limit on submissions, but please keep it relatively quick. I don't want the scoring script to take hours.

# Answer
> 11 votes
## CJam, ~~139~~ 141

There's a lot of unprintables in the code, so here's the `xxd` hexdump:

```
00000000: 7132 3925 3162 226d cec5 9635 b14b 69ee  q29%1b"m...5.Ki.
00000010: d9d0 66e8 97b8 e88d 2366 7857 9595 1c73  ..f.....#fxW...s
00000020: 9324 11b2 ddb8 7a3f 19ed bd37 07c0 cb86  .$....z?...7....
00000030: 394e b34a ecf0 8c9b f300 a216 2e2e 594a  9N.J..........YJ
00000040: 9a6b 3b2f 250a 9a25 783b 0e49 3e9c 6ab9  .k;/%..%x;.I>.j.
00000050: 8d6d d729 42d0 85f3 657b 7d86 af48 c6cb  .m.)B...e{}..H..
00000060: f7ff 980f b81c dd5e e8cb 4e34 d8ec edca  .......^..N4....
00000070: 6646 1b4d 7605 8937 ed58 2302 1cc1 ebfd  fF.Mv..7.X#.....
00000080: 16d3 b53e 3e2c d879 fe33 feef dd65 d49f  ...>>,.y.3...e..
00000090: 5d73 7ced 92e6 9526 c186 00bf d2a8 ffaa  ]s|....&........
000000a0: 65a0 3001 f42a 94d7 592f ebe7 8bdf 97a7  e.0..*..Y/......
000000b0: 0681 8ee1 9e0e 424b f6a1 4c50 1c8a 8de5  ......BK..LP....
000000c0: 481a 388c 6eaa 0c43 e1db 69df 567b 323f  H.8.n..C..i.V{2?
000000d0: 2573 c4ce b348 6fff 37e0 55b4 7c9a 7e7d  %s...Ho.7.U.|.~}
000000e0: 73a4 ef74 2b99 b765 2a2d d99f 986a 355c  s..t+..e*-...j5\
000000f0: db22 3236 3362 3236 6227 6166 2b32 2f3d  ."263b26b'af+2/=

```

This is exactly 256 bytes, with the program doing:

```
q29%                          Read input and keep every 29th char
    1b                        Sum code points
      "..."                   Push long string
           263b               Convert long string to base 263
               26b            Convert result to base 26
                  'af+        Add 'a to each element in the resulting array
                      2/      Split into chunks of length 2
                        =     Index sum cyclically to extract output

```

Run the program with the command

```
java -Dfile.encoding=ISO-8859-1 -jar cjam-0.6.5.jar flags.cjam < f.png

```

Thanks to @Dennis for help with getting this submission working.

# Answer
> 12 votes
# Python 2, Score = ~~68~~ 89

This solution uses the hash of the flag image file to create an index into a list of the country abbreviations. If more than one flag hashed to an index, only the first abbreviation will be returned (so it will fail some of those tests with more than one country in a hash bucket). This algorithm does however guarantee one correct answer for every non-empty hash bucket.

```
i=hash(open('f.png').read())%99*2
print'kgmviruasefridusvakpsmbtgrpwcdsdauninrsyalsg--game--espyscmtyebhgqom--kh--inhudjbw--ltroilbicv--jonaugke--svhtbg--simcknbnpelcplgncmmacimytnttlytgcflirsvemhtzuyqaerbfbepa--uzaenearcl--jmbbphkzrwieet'[i:i+2]

```

This program is 247 characters.

A more readable version:

```
encoded = 'kgmviruasefridusvakpsmbtgrpwcdsdauninrsyalsg--game--espyscmtyebhgqom--kh--inhudjbw--ltroilbicv--jonaugke--svhtbg--simcknbnpelcplgncmmacimytnttlytgcflirsvemhtzuyqaerbfbepa--uzaenearcl--jmbbphkzrwieet'
index = hash(open('f.png').read())%99 * 2
print encoded[index : index+2]

```

## Building the encoded string

To build the encoded string, I use a function to read in the flag files as strings, generate a hash from the string, and reduce the hash to a limited number of hash `buckets`:

```
def encode(buckets):
    lookup = {}
    for fn in os.listdir('flags'):
        name = fn[:2]
        signature = hash(open('flags/'+fn).read()) % buckets
        lookup[signature] = lookup.get(signature, '')+name
    return lookup

```

to return a dictionary of countries that match each signature, then use some code to convert the dictionary into a lookup string:

```
encoded = ''.join(lookup.get(v, '--')[:2] for v in range(buckets))

```

I needed to experiment a bit with which values of `buckets` gives the best results.

---
Tags: code-challenge, kolmogorov-complexity, image-processing, test-battery
---


title: Strongly Connected Components

text:
# Question
Title: Strongly Connected Components
Two distinct vertices in a directed graph are strongly connected if there is path in the graph from each to the other. A strongly connected component of the graph is a subset of the graph such that each pair of distinct vertices in the subset are strongly connected, and adding any more vertices to the subset would break this property.

Your challenge is to separate a graph into its strongly connected components. Specifically, you must output all of the SCCs in the graph.

**I/O:**

As input, you may use a list of directed edges, an adjacency list, an adjacency matrix, or any other reasonable input format. Ask if you're not sure. You may assume the graph has no totally disconnected vertices, and that there are no self edges, but you may not make any further assumptions. You may also optionally take the list of vertices as input, as well as the number of vertices.

As output, you must either give a partitioning of the vertices, such as a list of lists of vertices, where each sublist is a strongly connected component, or a labeling of vertices, where each label corresponds to a different component.

If you use a labeling, the labels must either be vertices, or a consecutive sequence of integers. This is to prevent offloafing the computation into the labels.

**Examples:**

These examples take lists of edges, where each edge is directed from the 1st entry to the second entry, and output partitions. You are free to use this format or another.

The input is on the first line, the output is on the second line.

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

[[1, 2], [2, 3], [3, 4]]
[[1], [2], [3], [4]]

[[1, 2], [2, 1], [1, 3], [2, 4], [4, 2], [4, 3]]
[[1, 2, 4], [3]]

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

```

**Scoring and restrictions:**

Standard loopholes are banned, as always. Also, built-ins which specifically deal with strongly connected components are banned.

Solutions should run in no more than an hour on the examples provided. (This is intended to prevent slow exponential solutions, and nothing else.)

This is code golf. Fewest bytes wins.

# Answer
> 3 votes
# Pyth, 13 bytes

```
.gu+Gs@LQG.{k

```

Demonstration, Test suite

Input is an adjacency list, represented as a dictionary which maps vertices to the list of vertices it has edges to (its directed neighbors). Output is a partition.

The essence of the program is that we find the set of vertices that are reachable from each vertex, and then group the vertices by those sets. Any two vertices in the same SCC have the same set of vertices reachable from them, because each is reachable from the other, and reachability is transitive. Any vertices in different components have different reachable sets, because neither's set contains the other.

**Code explanation:**

```
.gu+Gs@LQG.{k
                  Implicit: Q is the input adjacency list.
.g           Q    Group the vertices of Q by (Q is implicit at EOF)
  u       .{k     The fixed point of the following function,
                  starting at the set containing just that vertex
   +G             Add to the set
     s            The concatenation of
      @LQG        Map each prior vertex to its directed neighbors

```

# Answer
> 7 votes
## Python 2 using numpy, ~~71~~ 62 bytes

```
import numpy
def g(M,n):R=(M+M**0)**n>0;print(R&R.T).argmax(0)

```

Takes input as a `numpy` matrix representing adjacency and the number of nodes. Produces output as a `numpy` row matrix that labels each vertex by the lowest vertex number in its component.

For an adjacency matrix `M`, the matrix power `M**n` counts the number of `n`-step paths from each start vertex to each end vertex. Adding the identity to `M` via `M+M**0` modifies the adjacency matrix to add a self-loop to every edge. So, `(M+M**0)**n` counts paths of length at most `n` (with redundancy).

Since any path has length at most `n`, the number of nodes, any `(i,j)` where vertex `j` can be reached from `i` corresponds to a positive entry of `(M+M**0)**n`. The reachability matrix is then`R=(M+M**0)**n>0`, where the `>0` works entrywise.

Computing the entrywise `and` as `R&R.T`, where `R.T` is the transpose, then gives a matrix indicating the pairs of mutually reachable vertices. It's `i`th row is an indicator vector for vertices in the same strongly connected component as it. Taking its `argmax` of each row gives the index of the first `True` in it, which is the index of the smallest vertex in its component.

# Answer
> 4 votes
## JavaScript (ES6), 125 bytes

```
a=>a.map(([m,n])=>(e[m]|=1<<n|e[n],e.map((o,i)=>o&1<<m?e[i]|=e[m]:0)),e=[])&&e.map((m,i)=>e.findIndex((n,j)=>n&1<<i&&m&1<<j))

```

Takes a list of directed pairs as an argument, while the result is a array for each vertex giving the first vertex strongly connected to it, which I believe counts as a valid labelling. For example, with the input `[[1, 2], [2, 3], [2, 5], [2, 6], [3, 4], [3, 7], [4, 3], [4, 8], [5, 1], [5, 6], [6, 7], [7, 6], [8, 7], [8, 4]]` it returns `[, 1, 1, 3, 3, 1, 6, 6, 3]` (there is no vertex 0; vertexes 1, 2 and 5 have label 1; 3, 4 and 8 have label 3 while 6 and 7 have label 6).

# Answer
> 4 votes
# MATL, ~~26~~ 22 bytes

```
tnX^Xy+HMY^gt!*Xu!"@f!

```

This uses the same approach as @xnor's answer.

Works in current version (15.0.0) of the language.

Input is the adjacency matrix of the graph, with rows separated by semicolons. The first and last test cases are

```
[0 1 0 1; 0 0 1 0; 1 0 0 0; 0 0 0 0]

[0 1 0 0 0 0 0 0; 0 0 1 0 1 1 0 0; 0 0 0 1 0 0 1 0; 0 0 1 0 0 0 0 1; 1 0 0 0 0 1 0 0; 0 0 0 0 0 0 1 0; 0 0 0 0 0 1 0 0; 0 0 0 1 0 0 1 0]

```

**Try it online!**

```
t     % implicitly input adjacency matrix. Duplicate
n     % number of elements
X^    % square root
Xy    % identity matrix of that size
+     % add to adjacency matrix
HM    % push size again
Y^    % matrix power
g     % convert to logical values (0 and 1)
t!*   % multiply element-wise by transpose matrix
Xu    % unique rows. Each row is a connected component
!     % transpose
"     % for each column
  @   %   push that column
  f!  %   indices of nonzero elements, as a row
      % end for each. Implicitly display stack contents

```

---
Tags: code-golf, graph-theory
---


title: The last stage of contamination

text:
# Question
Title: The last stage of contamination
There is a virus inside a recipient of 5x5. As we know how it propagates its contamination, your mission is to output the last stage of the contamination.

### The recipient

It will be representend as a two dimensional array of 5x5:

```
0 0 0 0 1
0 0 0 0 1
0 0 0 1 1
0 0 1 1 1
0 1 1 1 1

```

Where `1` means a position where the virus has already contaminated, and `0` a position not contaminated.

### How the virus propagates

1. A contaminated position can not be clean.
2. A clean position will be contaminated in the next stage only if at least two of its adjacent positions (north, east, south and west cells) are contaminated.
3. The last stage of the contamination occurs when no more clean cells can be contaminated.

### Sample

Using as as stage 1 of the contamination the recipient described above, the stage 2 will be:

```
0 0 0 0 1
0 0 0 1 1
0 0 1 1 1
0 1 1 1 1
0 1 1 1 1

```

The stage 3 of the contamination will be:

```
0 0 0 1 1
0 0 1 1 1
0 1 1 1 1
0 1 1 1 1
0 1 1 1 1

```

The stage 4 of the contamination will be:

```
0 0 1 1 1
0 1 1 1 1
0 1 1 1 1
0 1 1 1 1
0 1 1 1 1

```

And the stage 5 (in this example, the last one) will be:

```
0 1 1 1 1
0 1 1 1 1
0 1 1 1 1
0 1 1 1 1
0 1 1 1 1

```

### Challenge

Given as input one stage of the contamination, you should output the last stage of the contamination.

You are allowed to write full program or a function. You can take the input as array/list, as separated numbers, or even as string. Chooses the best way that fits to your language.

The shortest answer in bytes wins!

### Another test cases

```
Input:
1 1 0 0 1
0 0 0 0 0
0 1 0 0 1
0 0 0 0 0
1 0 0 0 1

Output:
1 1 0 0 1
1 1 0 0 1
1 1 0 0 1
1 1 0 0 1
1 1 0 0 1

```

---

```
Input:
1 0 0 0 0
0 1 0 0 0
0 0 1 0 0
0 0 0 1 0
0 0 0 0 1

Output:
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1

```

---

```
Input:
1 0 0 1 0
0 0 1 0 1
0 0 0 0 0
1 0 0 0 0
0 0 1 0 0

Output:
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1

```

---

```
Input:
0 1 0 0 0
0 0 0 0 1
0 0 1 0 0
1 0 0 0 0
0 0 0 1 0

Output:
0 1 0 0 0
0 0 0 0 1
0 0 1 0 0
1 0 0 0 0
0 0 0 1 0

```

# Answer
> 13 votes
Since this is basically talking about a cellular automaton I give you..

# Golly Quicklife rule, 10 bytes

```
01234/234V

```

Input the rule, paste the grid into Golly, run pattern. The resulting pattern is the output.

Explanation:

```
01234 Survive on any number of neighbors
     /234 Born on >2 neighbors
         V Only directly adjacent neighbors count

```

Or if you insist on a full RuleLoader rule, 89 bytes:

```
@RULE X
@TABLE
n_states:2
neighborhood:vonNeumann
symmetries:permute
011001
011101
011111

```

Rulename is X, same steps as before.

# Answer
> 5 votes
# Python 2, 97 bytes

```
s=' '*6+input()
exec"s=s[1:]+('1'+s)[sum(s[i]<'1'for i in[-6,-1,1,6])>2or'/'>s];"*980
print s[6:]

```

Try it online. Input is taken as a quoted string with each row delimited by newlines. The `980` is not optimal and can be replaced with a lower multiple of 35. Since it has no impact on the length of this program, I have left the determination of the lowest safe upper bound as an exercise for the reader.

# Answer
> 3 votes
# Javascript (ES6), 91 89 87 bytes

As a function which accepts input as an array of numbers or strings.

-2 bytes from Neil (combining assignment of `y` with string conversion)

-2 bytes (removing variable `j`)

```
f=x=>(y=x.map((z,i)=>~(i%5&&x[i-1])+~(i%5<4&x[i+1])+~x[i-5]+~x[i+5]<-5|z))+[]==x?y:f(y)
```

```
<!-- Snippet demo with array <-> string conversion for convenience -->
<textarea id="input" cols="10" rows="5">0 0 0 0 1
0 0 0 0 1
0 0 0 1 1
0 0 1 1 1
0 1 1 1 1</textarea>
<button id="submit">Run</button>
<pre id="output"></pre>
<script>
strToArray=x=>x.match(/\d/g)
arrayToStr=x=>([]+x).replace(/(.),(.),(.),(.),(.),*/g, '$1 $2 $3 $4 $5\n')
submit.onclick=_=>output.innerHTML=arrayToStr(f(strToArray(input.value)))
</script>
```

# Answer
> 2 votes
# MATL, 22 bytes

```
tn:"t5Bt!=~2X53$Y+1>Y|

```

This works in current version (15.0.0) of the language.

**Try it online**!

Input format is: 2D array with rows separated by semicolons. So the four test cases have the following inputs:

```
[0 0 0 0 1; 0 0 0 0 1; 0 0 0 1 1; 0 0 1 1 1; 0 1 1 1 1]

[1 1 0 0 1; 0 0 0 0 0; 0 1 0 0 1; 0 0 0 0 0; 1 0 0 0 1]

[1 0 0 0 0; 0 1 0 0 0; 0 0 1 0 0; 0 0 0 1 0; 0 0 0 0 1]

[1 0 0 1 0; 0 0 1 0 1; 0 0 0 0 0; 1 0 0 0 0; 0 0 1 0 0]

```

### Explanation

This repeatedly performs a 2D convolution of the input array with the following mask, which defines which neighbours count as contaminating:

```
0 1 0
1 0 1
0 1 0

```

In order to obtain a result the same size as the original array, it is first padded with a frame of zeros and then only the "valid" part of the convolution is kept (i.e. that without edge effects).

A threshold of 2 is applied to the output of the convolution, and the result is element-wise ORed with the original input.

This must be done a sufficient number of times to ensure the final state has been reached. A simple criterion that fulfills this is: iterate as many times as the number of entries in the input array (that is, 25 times in the test cases).

```
t          % get input 2D array implicitly. Duplicate
n:"        % repeat as many times as elements in the input array
  t        %   duplicate array
  5B       %   number 5 in binary: row vector [1 0 1]
  t!       %   duplicate and transpose into column
  =~       %   compare for inequality with broadcast. Gives desired mask
  2X53$Y+  %   2D convolution. Output has same size as input
  1>       %   true for elements equal or greater than 2
  Y|       %   element-wise OR with previous copy of the array
           % end loop. Implicitly display

```

# Answer
> 1 votes
# TI-BASIC, 151 bytes

```
Prompt [A]
[A]→[B]
Lbl 0
[B]→[A]
For(Y,1,5
For(X,1,5
DelVar ADelVar BDelVar CDelVar D
If Y>1:[A](Y-1,X→A
If Y<5:[A](Y+1,X→B
If X>1:[A](Y,X-1→C
If X<5:[A](Y,X+1→D
max(A+B+C+D≥2,[A](Y,X→[B](Y,X
End
End
If [A]≠[B]:Goto 0
[B]

```

Input as `[[1,0,0,1,1][1,0,0,0,0]...]`.

# Answer
> 1 votes
# Lua, 236 bytes

```
s=arg[1]u=s.sub while p~=s do p=s s=s:gsub("(%d)()",function(d,p)t=0 t=t+((p-2)%6>0 and u(s,p-2,p-2)or 0)t=t+(p-7>0 and u(s,p-7,p-7)or 0)t=t+(p+5<30 and u(s,p+5,p+5)or 0)t=t+(p%6>0 and u(s,p,p)or 0)return t>1 and 1 or d end)end print(s)

```

Accepts input on the command line, and uses Lua's string manipulation to get the answer.

Ungolfed:

```
s=arg[1]
u=s.sub
while p~=s do
    p=s
    s=s:gsub("(%d)()", function(d, p)
                 t=0
                 t=t+((p-2)%6>0 and u(s,p-2,p-2)or 0)
                 t=t+(p-7>0 and u(s,p-7,p-7)or 0)
                 t=t+(p+5<30 and u(s,p+5,p+5)or 0)
                 t=t+(p%6>0 and u(s,p,p)or 0)
                 return t>1 and 1 or d
    end)
end
print(s)

```

# Answer
> 1 votes
# APL, ~~76~~ ~~72~~ 70 bytes

```
{⍵∨1<¯1 ¯1↓1 1↓↑+/(1 0)(¯1 0)(0 ¯1)(0 1){⍺[1]⊖⍺[2]⌽⍵}¨⊂¯1⊖¯1⌽7 7↑⍵}⍣≡

```

What this does is: expand the matrix to a 7x7 one, then center our argument (omega). From this matrix, generate 4 "child" matrices, each one shifted in a different direction (up/down/left/right), add them together (so we get the number of neighbours), drop the frame (to go back to a 5x5 matrix). Or this new matrix with the "old" one, to make sure we didn't drop any cells in the process (i.e. at the edge). Then, use the `⍣≡` combination to get to a fixed-point value.

```
{⍵∨1<¯1 ¯1↓1 1↓↑+/(1 0)(¯1 0)(0 ¯1)(0 1){⍺[1]⊖⍺[2]⌽⍵}¨⊂¯1⊖¯1⌽7 7↑⍵}⍣≡
                                                             7 7↑⍵    ⍝ Expand the matrix
                                                       ¯1⊖¯1⌽         ⍝ Center the original matrix
                  (1 0)(¯1 0)(0 ¯1)(0 1){⍺[1]⊖⍺[2]⌽⍵}¨⊂               ⍝ Construct 4 child matrices, each offset from the original one by the values on the left of {}
                +/                                                    ⍝ Sum each matrix into one giant matrix
               ↑                                                      ⍝ Mix
     ¯1 ¯1↓1 1↓                                                       ⍝ Transform the 7x7 matrix back to a 5x5 matrix
   1<                                                                 ⍝ Check which elements are smaller than 1
 ⍵∨                                                                   ⍝ "Or" this matrix and the generated matrix
{                                                                 }⍣≡ ⍝ Find the fixpoint

```

example (considering the function was assigned to `contaminate`):

```
          stage ⍝ the base matrix
0 0 0 0 1
0 0 0 0 1
0 0 0 1 1
0 0 1 1 1
0 1 1 1 1
      contaminate stage ⍝ apply the function
0 1 1 1 1
0 1 1 1 1
0 1 1 1 1
0 1 1 1 1
0 1 1 1 1

```

---
Tags: code-golf, binary-matrix
---