title: It's Life, Jim, but not as we know it

text:
# Question
Title: It's Life, Jim, but not as we know it
You probably know *Conway's Game of Life*, the famous cellular automaton invented by mathematician John Conway. *Life* is a set of rules that, together, allow you to simulate a two-dimensional board of cells. The rules decide which cells on the board live and which ones die. With some imagination, you could say that *Life* is a zero-player game: a game with the objective to find patterns with interesting behavior, like the famous glider.

A zero-player game... Until today. You are to write a program that plays the Game of Life - and plays it to win, King of the Hill-style. Your opponent (singular) of course tries to do the same. The winner is either the last bot with any live cells, or the player with the most live cells after 10000 generations.

## Game rules

The rules are *almost* the same as normal (B3/S23) Life:

* A live cell with fewer than two friendly neighbors dies from starvation.
* A live cell with two or three friendly neighbors survives.
* A live cell with more than three friendly neighbors dies from overpopulation.
* A dead cell with exactly three neighbors of the same player comes alive to fight for that player *provided there are no enemy neighbors*.

...but after each generation, both you and your opponent get the opportunity to intervene. You can awake up to a maximum of 30 cells to fight for you. (Who goes first is decided by the server.)

The board is a (x,y) cells square. All squares are initially dead. The borders do not wrap around (this is not a torus-shaped world) and are permanently dead.

This is is a contest in the spirit of *Battlebots* and *Core Wars*. There is a central server that will run bots and it can be found here

## Protocol

The arena server speaks a simple JSON protocol communicated through argv

Where Values is a JSON encoded string

* `y_size`: the maximum y coords of tiles before they vanish
* `x_size`: the maximum x coords of tiles before they vanish
* `tick_id`: the current tick number
* `board`: a dictionary with keys in the form '(y,x)' and values in the form `bot_id` (int)
* `bot_id`: tiles in the board with this id are yours

Example:

```
 {"y_size":2000,"x_size":2000,"board":{},"bot_id":1,"tick_id":1}

```

Telling the server your choice:

* Send the server a list of tiles to turn to your colour.
* Only those that are empty will be changed
* Nested coords list format
    + `[[0,0], [0,1], [100,22]...]`

NOTE: Your bot doesn't have to update the tiles at all - the server does the updating itself

## Competition rules

* If your implementation fails to follow the protocol, the turn it does will be forfeited; The server will assume no change in state
* You are not allowed to willfully take advantage of a fault in the arena server.
* Have your AI decide on moves in a sane time. Please send your next move as fast as reasonably possible.
* Finally, please be nice to the server. It's there for your enjoyment.
* Not following these rules can lead to disqualification.
* In the event of a tie, both players have 1 win added to their total

## Running the controller yourself

The source for the controller can be found here. There are 2 ways of running the controller:

* Competition mode (terminal)
    + Setup with `python3 get_answers.py`
    + Run an all v all competition with each bot pitting it against every other.
* Testing mode (GUI)
    + Run `python3 nice_gui.py`
    + Click `Pull Answers`
    + If you want to add your own answer to try it before posting, click `File -> Add manual answer` and find the file and choose the language it's written in.
    + If your language isn't present ping me and I'll try to get it installed on the server I will run it on (installation and running instructions would be nice too!)
    + Choose 2 bots to pit against each other
    + Click `Run`
    + Watch the game...
* Installation
    + Requires python3
    + get\_answers requires bs4 and html5lib
    + controller requires a way of running .sh files (MinGW on windows)

## Scoring

The bot with the most wins starting from ~~`12/07/2016` (12th July)~~ `14/07/2016` (14th July, couldn't work out how to run a bot) wins.

---

### Help with the controller/gui can be asked in this chat room

---

This question has been in development since 2014 and was the most upvoted question in the sandbox. Special Thanks goes to Wander Nauta (original author and concept), PPCG Chat (comments and help) and anyone who commented in the sandbox post (more comments).

# Answer
## Python 3, Exploder

Puts small exploders around the place, with no regard to whether there is already a block there.

```
from random import randint
import sys,json,copy
q=json.loads(sys.argv[1])
x=q["x_size"];y=q["y_size"];F=[[0,1],[1,0],[1,1],[1,2],[2,0],[2,2]];D=[]
for g in [0]*5:
 X=randint(0,x);Y=randint(0,y);A=copy.deepcopy(F)
 for C in A:C[0]+=Y;C[1]+=X
 D+=A
print(D)

```
> 5 votes

# Answer
# Ruby, InterruptingBlockMaker

Instead of initializing gliders like the TrainingBot, it tries to create a 5x5 block-making switch machine as mentioned on Wikipedia at a random point in the maze. Then, with its remaining activations, it just finds enemy points and tries to pepper the nearby area with your cells in an attempt to interrupt them from growing and possibly messing up their patterns. Your cells will die in the next generation, but maybe they also stopped some growth to slow down your opponent!

v2: Optimized slightly (?) to try to minimize timeouts.

v3: Optimized interruption code to pre-sample a subset of active blocks before rejecting our own cell locations, to prevent timeouts further at the cost of some effectiveness in the interrupt cell attacks.

```
require 'json'

class Range
  def product range2
    self.to_a.product range2.to_a
  end
end

args = JSON.parse(ARGV[0])
bot_id = args["bot_id"]
width  = args["x_size"]
height = args["y_size"]
board  = args["board"]

generator = [[2,2], [2,3], [2,6], [3,2], [3,5], [4,2], [4,5], [4,6], [5,4], [6,2], [6,4], [6,5], [6,6]]

targets = []

iterations = 50
gen_location = nil
while !gen_location && iterations > 0
  y = rand height - 9
  x = rand width  - 9
  temp = (0...9).product(0...9).map{|_y, _x| [y + _y, x + _x]}
  if temp.all?{|_y,_x| !board["(#{y},#{x})"]}
    gen_location = temp
    targets += generator.map{|_y, _x| [y + _y, x + _x]}
  end

  iterations -= 1
end

enemies = board.keys.sample(100).reject {|k| board[k] == bot_id}
interrupts = []
enemies.each do |location|
  y, x = location.scan(/\d+/).map &:to_i
  interrupts |= ((y-1)..(y+1)).product((x-1)..(x+1)).reject{|y, x| gen_location.include?([y,x]) || board["(#{y},#{x})"]}
end

targets += interrupts.sample(30 - targets.size)

puts JSON.dump(targets)

```
> 8 votes

# Answer
## Python 2, TrainingBot

Because everyone needs one of these!

```
import random, copy
import sys, json

args = json.loads(sys.argv[1])
bot_id = args["bot_id"]
x_size = args["x_size"]
y_size = args["y_size"]
cur_tick = args["tick_id"]
board = args["board"]

glider = [[1,2],[2,1],[0,0],[0,1],[0,2]]

x_add = random.randrange(x_size)
y_add = random.randrange(y_size)
new_glider = copy.deepcopy(glider)
for coord in new_glider:
    coord[0]+=y_add
    coord[1]+=x_add
move = new_glider
print json.dumps(move)

```
> 4 votes

# Answer
# Java, Troll Bot

Troll Bot has thought about it, and he realizes he does NOT care about the enemy. In fact he just spams these factories to produce more of his guys randomly all over the map. After a while he realized that any additional cells are best used in clumps. These blocks of four cells will stick together and stop gliders in their tracks! He does not think he just fights. Also he is a big supporter of verbose object oriented programming. The troll also assumes that coords are in the format y,x, and he is asking to be tested. Just put him in a file called "TrollBot.java", and he'll be set!

```
package trollbot;

/**
 *
 * @author Rohans
 */
public class TrollBot{
public static class coord{
    public int x;
    public int y;
    public coord(int inX,int inY){
        x = inX;
        y = inY;
    }
    @Override
    public String toString(){
        return"["+x+","+y+"]";
    }
}
    /**
     * Input the JSON as the first cla
     * @param args the command line arguments
     */
    public static void main(String[] args) {
       String JSON="{\"bot_id\":1,\"y_size\":1000,\"x_size\":1000,\"board\":{}}";
    String[] JArray=args[0].split(",");
       int botId=Integer.parseInt(JSON.charAt(10)+"");
    int xSize=Integer.parseInt(JArray[2].substring(JArray[2].indexOf(":")+1));
    int ySize=Integer.parseInt(JArray[1].substring(JArray[1].indexOf(":")+1));
    int[][] board = new int[xSize][ySize];//0 indexed
//todo: parse the board to get an idea of state
    String soldiers="[";
//for now just ignore whats on the board and put some troll cells on
    //Attempts to create 3 10 cells factories of cells, hoping it does not place it on top of allies
    //Then puts random 2/2 blocks
  boolean[][] blockspam=new boolean[10][8];
  blockspam[7][1]=true;
  blockspam[5][2]=true;
  blockspam[7][2]=true;
  blockspam[8][2]=true;
  blockspam[5][3]=true;
  blockspam[7][3]=true;
  blockspam[5][4]=true;
  blockspam[3][5]=true;
  blockspam[1][6]=true;
  blockspam[3][6]=true;
  for(int z=0;z<3;z++){
     int xOffSet=(int) (Math.random()*(xSize-11));
     int yOffSet=(int) (Math.random()*(ySize-9));
     //stay away from edges to avoid odd interactions
     for(int i=0;i<blockspam.length;i++){
         for(int j=0;j<blockspam[i].length;j++){
             if(blockspam[i][j])
             soldiers+=new coord(j+yOffSet,i+xOffSet).toString()+",";
         }
     }
  }
  soldiers=soldiers.substring(0,soldiers.length()-1);
  for(int i=0;i<8;i++){
            int y=(int ) (Math.random()*(ySize-1));
            int x = (int) (Math.random()*(xSize-1));
      soldiers+=new coord(y,x).toString()+",";
                          soldiers+=new coord(y+1,x).toString()+",";
                          soldiers+=new coord(y,x+1).toString()+",";
                          soldiers+=new coord(y+1,x).toString()+",";

  }
  soldiers+="\b]";

  System.out.println(soldiers);
  //GO GO GO! Lets rule the board
    }

}

```
> 4 votes

# Answer
# Python 3, RandomBot

This bot has trouble making intelligent decisions, but it at least knows not to try to place things on top of other things. It'll randomly create gliders, boats, C/2 Orthagonals, and 2x2 blocks with various orientations, ensuring that when they're placed they're not overlapping with something else, ally or enemy.

This bot wasn't tested, seeing as I'm receiving all sorts of errors when I try to run the GUI. Also, I used the TrainingBot as the base and just edit, so any similarities in code is probably because of that.

```
import random, copy
import sys, json
args = json.loads(sys.argv[1])
bot_id = args["bot_id"]
x_size = args["x_size"]
y_size = args["y_size"]
board = args["board"]
occupied = [tuple(key) for key,value in iter(board.items())]
cellsleft=30
move=[]
choices = [[[1,2],[2,1],[0,0],[0,1],[0,2]],
           [[0,0],[0,1],[1,1],[1,0]],
           [[0,1],[1,0],[0,2],[0,3],[1,3],[2,3],[3,3],[4,3],[5,2],[5,0]],
           [[0,0],[1,0],[0,1],[2,1],[2,2]]]
while cellsleft>0:
    x_add = random.randrange(x_size)
    y_add = random.randrange(y_size)
    new_glider = copy.deepcopy(random.choice(choices))
    randomdirection = random.choice([[1,1],[1,-1],[-1,1],[-1,-1]])
    maxy=max([y[0] for y in new_glider])
    maxx=max([x[1] for x in new_glider])
    for coord in new_glider:
        coord[0]=coord[0]*randomdirection[0]+y_add
        coord[1]=coord[1]*randomdirection[1]+x_add
        cellsleft-=1
    set([tuple(x) for x in new_glider])
    if not set([tuple(x) for x in new_glider]) & (set(occupied)|set([tuple(x) for x in move])) and cellsleft>0:
        if min(y[0] for y in new_glider)<0: new_glider = [[y[0]+maxy,y[1]] for y in new_glider]
        if min(y[1] for y in new_glider)<0: new_glider = [[y[0],y[1]+maxx] for y in new_glider]
        move += new_glider
    elif set([tuple(x) for x in new_glider]) & (set(occupied)|set([tuple(x) for x in move])):
        cellsleft+=len(new_glider)

print(json.dumps(move))

```
> 3 votes

# Answer
## Python, GuyWithAGun

He's a guy, he's got a gun; he's mad. He just dumps glider guns everywhere with no regard to what anyone else is doing

```
import random, copy
import sys, json

args = json.loads(sys.argv[1])
bot_id = args["bot_id"]
x_size = args["x_size"]
y_size = args["y_size"]
tick_id = args["tick_id"]
board = args["board"]

start_squares = [[0,5],[2,5],[1,6],[2,6],
                 [35,3],[36,3],[35,4],[36,4]]
gun = [[11,5],[11,6],[11,7],
       [12,4],[12,8],
       [13,3],[13,9],
       [14,3],[14,9],
       [15,6],
       [16,4],[16,8],
       [17,5],[17,6],[17,7],
       [18,6],
       [21,3],[21,4],[21,5],
       [22,3],[22,4],[22,5],
       [23,2],[23,6],
       [25,1],[25,2],[25,6],[25,7]]

templates = [start_squares, gun]

def add_squares(pos, coords):
    new_squares = copy.deepcopy(coords)
    for coord in new_squares:
        coord[0]+=pos[0]
        coord[1]+=pos[1]
    return new_squares

def get_latest_pos():
    seed, template_id = divmod(tick_id, 2)
    random.seed(seed)
    cur_pos = [random.randrange(y_size),
               random.randrange(x_size)]
    cur_template = templates[template_id]
    try:
        return add_squares(cur_pos, cur_template)
    except IndexError:
        return []

move = get_latest_pos()

print json.dumps(move)

```
> 3 votes

# Answer
## Python 3, SquareBot

Puts squares everywhere- maybe

Squares are static objects in Life- they do not move. So if I place enough inert objects around the place, the gliders and explosions that others create will possibly be blocked, or at least dampened.

-Adapted from TrainingBot

```
from random import randint
import sys,json,copy
args=json.loads(sys.argv[1])
x=args["x_size"];y=args["y_size"]
square=[[0,0],[0,1],[1,0],[1,1]];D=[]
for g in range(7):
 X=randint(0,x);Y=randint(0,y)
 A=copy.deepcopy(square)
 for C in A:C[0]+=Y;C[1]+=X
 D+=A
print(D)

```

Although I am having trouble testing it
> 2 votes

---
Tags: king-of-the-hill, game-of-life
---


# Question
Title: Read numbers in the base of the largest digit and write it using underscores
This isn't as much a "challenge" as "a unique problem that there are no built-in functions to solve." Basically, you need to do this:

* Read some lines of numbers from `stdin`. These lines may contain trailing or preceding whitespace, and there may be empty lines. No lines will contain "just whitespace" other than a newline. Each non-empty line will have exactly one number. This:

```
 123

456\t

```

(where `\t` is a tab) is considered valid input.
* Read the numbers in the input in base `N+1`, where `N` is the largest digit in any of the lines. In this case, the largest digit is `6`, so the numbers would be read in base `7`, resulting in 6610 and 23710.
* Find the sum of the numbers. The sum of 6610 and 23710 is 30310.
* Convert the sum back to base `N+1` again. We'd convert 30310 to base `7`, which would be 6127.
* For each digit, print that many underscores, followed by a space. The last digit should instead be followed by a newline *or* a space and a newline. In our example, that would be `______ _ __\n` or `______ _ __ \n`, where `\n` is the newline character.

Here's an example in Python:

```
import sys

def convert_to_base(n, b):
    'Convert `n` to base `b`'
    res = []
    while n:
        res.append(n % b)
        n /= b
    return res[::-1]

# read the lines, discarding empty ones and stripping any whitespace
lines = map(str.strip, filter(None, list(sys.stdin)))
# find the largest digit, and add 1 to it to make our base
base = max(map(max, (map(int, line) for line in lines)))+1
# read the lines in the base and sum them
result = sum(int(line, base) for line in lines)
# print the result in the original base using underscores, separated by spaces
for number in convert_to_base(result, base):
    print '_'*number,
# print a newline
print

```

This is code golf: the shortest program wins!

# Answer
> 2 votes
# Pyth, 24 bytes

Just found this question via Twitter.

Notice that quite large parts of the program are similar to isaacg's solution (like base-conversion and the printing part), but the main algorithm is completely different.

```
.V0#jd*R\_jsiRbcjd.z)b.q

```

Try it online: Demonstration

My solution is based on this answer, I gave to a similar question two months ago.

### Explanation:

```
.V0                       for b in [0, 1, 2, ...):
   #__________________.q    try-catch block. If ___ is successful, exit the program (.q),
                            otherwise do nothing
               cjd.z)         read all input (.z), join lines by spaces (jd) and split (c))
                              this gives a list of numbers (but still in string format)
            iRb               convert each number from base b
           s                  sum, add all numbers up
          j          b        convert to base b
      *R\_                    multiply each digit with "_"
    jd                        join with spaces
                              implicit print

```

The infinite loop `.V0` combined with the try-catch `#___.q` basically finds the first number `b >= 0`, with which the conversion `iRb` doesn't throw an error. And this happens, when `b` is equal to the largest digit + 1.

# Answer
> 5 votes
# Pyth, 26

```
JscR).zjd*R\_jsiRKhseSsJJK

```

Demonstration.

```
JscR).z
     .z                       Take the input as a list of lines.
  cR)                         Remove all whitespace from each line.
 s                            Combine the lines.
J                             Save the result to J.
                              J is now the list of the string forms of the numbers.
       jd*R\_jsiRKhseSsJJK
                      sJ      Combine J into one string.
                    eS        Find the maximum of that string.
                   s          Convert it to an integer.
                  h           Add one.
                 K            Save to K. K is the base.
               iRK      J     Convert the strings in J to base K.
              s               Add them together.
             j           K    Convert the result back to base K, as a list of ints.
         *R\_                 Map each int in that list to that many underscores.
       jd                     Join on spaces and print.

```

# Answer
> 2 votes
# CJam, ~~28~~ 27 bytes

```
q_$W=~)_@N%::~fb:+\b'_f*S*N

```

*UPDATE - 1 byte saved thanks to Martin*

Try it online here

# Answer
> 0 votes
# PHP, ~~188~~ 182

```
function f($s){$b=max(str_split($s))+1;foreach(preg_split('/\s/',$s)as$x)$m+=base_convert($x,$b,10);foreach(str_split(base_convert($m,10,$b))as$d)echo' ',str_repeat('_',$d);echo'

```

';}

prints a leading blank instead of a trailing one. if not accepted, add +1.

breakdown:

```
function f($s)
{
    $b=max(str_split($s))+1;           // find base
    foreach(preg_split('/\s/',$s)as$x) // extract all words and loop
        $m+=base_convert($x,$b,10);    // convert, sum up
    foreach(str_split(base_convert($m,10,$b))as$d) // convert back, split into array, loop
        echo' ',str_repeat('_',$d);    // print underscores
    echo'
';                                     // append newline
}

```

I wonder if there is a golfier approach to this ...

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


title: Sequence avoiding near collision

text:
# Question
Title: Sequence avoiding near collision
# Task

Find a sequence of all numbers between min and max where every number differs from every other number in the sequence by at least "d" digits.

# Example of sub-sequence

For min = 0, max = 1000 and d = 2, the following is part of one possible solution sequence:

* 123 ← Good
* 132 ← Good
* 145 ← Good
* 146 ← Bad

# Notes

This is a bit practical. I was thinking about this as a problem that has kept cropping up over the years. Basically it's a pattern in URL shorteners / prize codes / conference room codes / etc...

I'd like to be able to hand out codes from a list, and have each code be: A - Simple to type, and B - Be somewhat unlikely to accidentally conflict with another code because of a typing mistake.

There's no reason to work in base ten. I've expressed the problem that way for clarity, but in real cases we'd take advantage of letters as well.

### Sub-Note

This is not *that* practical. If you use just six "digits" (allowing numbers and capital letters), then you have over two billion choices. That seems like plenty for most cases except for the URL shortener. Still I was thinking it would be nice to be able to generate a random number from that space and be able to quickly check that it was at least "d" different from all others that had been handed out up to that point. Generating a solution sequence is not quite the same problem, but it seemed interesting and I'm hoping that someone comes up with a clever way to structure the data in order to make it efficient to search for these near collisions.

# Answer
Here's a terrible, brute force way of generating a sequence. I haven't attempted to do much to make it fast, though there are probably several simple gains to be had here. I'm trying to think of a way to make this at least a couple of orders of magnitude faster rather than finding improvements of a few percent.

```
public static IEnumerable<int> GetDifferentCodes(int min, int digits, int minDifference)
{
    var max = Math.Pow(10, digits) - 1;
    var goodCodes = new List<int>();
    var goodCodeDigits = new List<short[]>();

    for (var i = min; i < max; i++)
    {
        var newDigits = GetDigits(i, digits);

        if (!goodCodeDigits.All(goodCode => HasMinDiff(goodCode, newDigits, digits, minDifference)))
            continue;
        goodCodes.Add(i);
        goodCodeDigits.Add(newDigits);
    }
    return goodCodes;
}

private static readonly int[] Powers = {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000};

private static short[] GetDigits(int num, int digits)
{
    var ret = new short[digits];
    for (var i = 0; i < digits; i++)
    {
        ret[i] = (short) ((num/Powers[i]) % 10);
    }
    return ret;
}

private static bool HasMinDiff(short[] goodDigits, short[] digitsToCheck, int digits, int minDiff)
{
    var difference = 0;
    for (var i = 0; i < digits; i++)
    {
        if (goodDigits[i] == digitsToCheck[i]) continue;
        if (++difference >= minDiff) return true;
    }
    return false;
}

```
> 0 votes

---
Tags: sequence, number-theory, fastest-algorithm
---


# Question
Title: Print the "even" permutations of symmetric group Sn in cyclic notation
# THE TASK

### DEFINITIONS

Consider the points {1,2,3,4,5} and all their permutations. We can find the total number of possible permutations of these 5 points by a simple trick: Imaging filling 5 slots with these points, the first slot will have 5 possible numbers, the second 4 (as one has been used to fill the first slot) the third 3 and so on. Thus the total number of Permutations is 5\*4\*3\*2\*1; this would be 5! permutations or 120 permutations. We can think of this as the symmetric group S5, and then Symmetric Group Sn would have `n! or (n*n-1*n-2...*1)` permutations.

An "even" permutation is one where there is an even number of even length cycles. It is easiest to understand when written in cyclic notation, for example `(1 2 3)(4 5)` permutes `1->2->3->1` and `4->5->4` and has one 3 length cycle `(1 2 3)` and one 2 length cycle `(4 5)`. When classifying a permutation as odd or even we ignore odd length cycles and say that this permutation \[`(1 2 3)(4 5)`\] is odd as it has an odd number {1} of even length cycles. Even examples:

1. `(1)(2 3)(4 5)` = two 2 length cycle | EVEN |
2. `(1 2 3 4 5)` = no even length cycles | EVEN | * note that if no even length cycles are present then the permutation is even.

Odd Examples:

1. `(1 2)(3 4 5)` = one 2 length cycle | ODD |
2. `(1)(2 3 4 5)` = one 4 length cycle | ODD |

As exactly half of the permutations in any Symmetric Group are even we can call the even group the Alternating Group N, So as S5 = 120 A5 = 60 permutations.

### NOTATION

Permutations should, for this at least, be written in cyclic notation where each cycle is in different parenthesis and each cycle goes in ascending order. For example `(1 2 3 4 5)` not `(3 4 5 1 2)`. And for cycles with a single number, such as: `(1)(2 3 4)(5)` the single / fixed points can be excluded meaning `(1)(2 3 4)(5) = (2 3 4)`. But the identity {the point where all points are fixed `(1)(2)(3)(4)(5)`} should be written as `()` just to represent it.

### THE CHALLENGE

I would like you to, in as little code possible, take any positive integer as an input {1,2,3,4...} and display all the permutations of the Alternating Group An where n is the input / all the even permutations of Sn. For example:

```
Input = 3
()
(1 2 3)
(1 3 2)

```

and

```
Input = 4
()
(1 2)(3 4)
(1 3)(2 4)
(1 4)(2 3)
(1 2 3)
(1 3 2)
(1 2 4)
(1 4 2)
(1 3 4)
(1 4 3)
(2 3 4)
(2 4 3)

```

And as with in the examples I would like for all cycles of one length to be elided, and as for the identity: outputs of  nothing, `()` {not only brackets but with whatever you are using to show different permutations} or `id` are acceptable.

# EXTRA READING

You can find more information here:

# GOOD LUCK

And as this is codegolf whoever can print the Alternating Group An's permutations in the shortest bytes wins.

# Answer
> 5 votes
# Pyth, 26 bytes

```
t#Mf%+QlT2mcdf<>dTS<dTd.pS

          m            .pSQ   Map over permutations d of [1, …, Q]:
             f        d         Find all indices T in [1, …, Q] such that
               >dT                the last Q-T elements of d
              <   S<dT            is less than the sorted first T elements of d
           cd                   Chop d at those indices
   f                          Filter on results T such that
      Q                         the input number Q
     + lT                       plus the length of T
    %    2                      modulo 2
                                is truthy (1)
t#M                           In each result, remove 0- and 1-cycles.

```

Try it online

This solution is based on a neat bijection between permutations in one-line notation and permutations in cycle notation. Of course, there’s the obvious bijection where the two notations represent the same permutation:

\[8, 4, 6, 3, 10, 1, 5, 9, 2, 7\] = (1 8 9 2 4 3 6)(5 10 7)

but that would take too much code. Instead, simply chop the one-line notation into pieces before all numbers that are smaller than all their predecessors, call these pieces cycles, and build a new permutation out of them.

\[8, 4, 6, 3, 10, 1, 5, 9, 2, 7\] ↦ (8)(4 6)(3 10)(1 5 9 2 7)

To reverse this bijection, we can take any permutation in cycle form, rotate each cycle so its smallest number is first, sort the cycles so that their smallest numbers appear in decreasing order, and erase all the parentheses.

# Answer
> 6 votes
# Mathematica, ~~84~~ ~~49~~ 31 bytes

```
GroupElements@*AlternatingGroup

```

Composition of two functions. Outputs in the form `{Cycles[{}], Cycles[{{a, b}}], Cycles[{{c, d}, {e, f}}], ...}` representing `(), (a b), (c d)(e f), ...`.

# Answer
> 3 votes
# , 53 bytes

```
[:(<@((>:@|.~]i.<./)&.>@#~1<#@>)@C.@#~1=C.!.2)!A.&i.]

```

The cycles in each permutation are represented as boxed arrays since J will zero-pad ragged arrays.

If the output is relaxed, using **41 bytes**

```
[:((1+]|.~]i.<./)&.>@C.@#~1=C.!.2)!A.&i.]

```

where each permutation may contain one-cycles and zero-cycles.

## Usage

```
   f =: [:(<@((>:@|.~]i.<./)&.>@#~1<#@>)@C.@#~1=C.!.2)!A.&i.]
   f 3
┌┬───────┬───────┐
││┌─────┐│┌─────┐│
│││1 2 3│││1 3 2││
││└─────┘│└─────┘│
└┴───────┴───────┘
   f 4
┌┬───────┬───────┬─────────┬───────┬───────┬───────┬───────┬─────────┬───────┬───────┬─────────┐
││┌─────┐│┌─────┐│┌───┬───┐│┌─────┐│┌─────┐│┌─────┐│┌─────┐│┌───┬───┐│┌─────┐│┌─────┐│┌───┬───┐│
│││2 3 4│││2 4 3│││1 2│3 4│││1 2 3│││1 2 4│││1 3 2│││1 3 4│││1 3│2 4│││1 4 2│││1 4 3│││2 3│1 4││
││└─────┘│└─────┘│└───┴───┘│└─────┘│└─────┘│└─────┘│└─────┘│└───┴───┘│└─────┘│└─────┘│└───┴───┘│
└┴───────┴───────┴─────────┴───────┴───────┴───────┴───────┴─────────┴───────┴───────┴─────────┘

```

For the alternative implemenation,

```
   f =: [:((1+]|.~]i.<./)&.>@C.@#~1=C.!.2)!A.&i.]
   f 3
┌─────┬─┬─┐
│1    │2│3│
├─────┼─┼─┤
│1 2 3│ │ │
├─────┼─┼─┤
│1 3 2│ │ │
└─────┴─┴─┘

```

# Answer
> 2 votes
# Jelly, ~~34~~ 28 bytes

```
L€’SḂ
ṙLR$Ṃµ€Ṣ
Œ!ŒṖ€;/Ç€ÑÐḟQ

```

Try it here.

## Explanation

Each line in a Jelly program defines a function; the bottom one is “`main`”.

* The first line defines a function that tests whether a cycle product is odd.

```
L€      Length of each
  ’     Add 1 to each length
   S    Take the sum
    Ḃ   Modulo 2

```
* The second line normalizes a partition of a permutation of `[1…n]` into a cycle product as follows:

```
     µ€    For each list X in the partition:
ṙLR$          Rotate X by each element in [1…length(X)].
    Ṃ         Get the lexicographically smallest element.
              Thus, find the rotation so that the smallest element is in front.
       Ṣ   Sort the cycles in the partition.

```

This will turn e.g. `(4 3)(2 5 1)` into `(1 2 5)(3 4)`.

Here is the main program. It takes an argument `n` from the command line, and:

```
Œ!              Compute all permutations of [1…n].
  ŒṖ€           Compute all partitions of each permutation.
     ;/         Put them in one big list.
       Ç€       Normalize each of them into a cycle product.
         ÑÐḟ    Reject elements satisfying the top function,
                i.e. keep only even cycle products.
            Q   Remove duplicates.

```

# Answer
> 2 votes
## JavaScript (Firefox 30-57), ~~220~~ ~~218~~ ~~212~~ 211 bytes

```
f=(a,p)=>a[2]?[for(i of a)for(j of f(a.filter(m=>m!=i),p,p^=1))[i,...j]]:[[a[p],a[p^1]]]

```

Sadly 88 bytes only suffices to generate the alternating group as a list of permutations of `a`, so it then costs me an additional ~~132~~ ~~130~~ ~~124~~ 123 bytes to convert the output to the desired format:

```
n=>f([...Array(n).keys()],0).map(a=>a.map((e,i)=>{if(e>i){for(s+='('+-~i;e>i;[a[e],e]=[,a[e]])s+=','+-~e;s+=')'}},s='')&&s)

```

I've managed to trim my ES6 version down to ~~222~~ ~~216~~ 215 bytes:

```
n=>(g=(a,p,t=[])=>a[2]?a.map(e=>g(a.filter(m=>m!=e),p,[...t,e],p^=1)):[...t,a[p],a[p^1]].map((e,i,a)=>{if(e>i){for(s+='('+-~i;e>i;[a[e],e]=[,a[e]])s+=','+-~e;s+=')'}},s='')&&r.push(s))([...Array(n).keys(r=[])],0)&&r

```

# Answer
> 1 votes
# GAP, 32 bytes

Thanks to @ChristianSievers for cutting the count in half.

```
f:=n->List(AlternatingGroup(n));

```

Usage at the prompt:

```
gap> f(4);
[ (), (1,3,2), (1,2,3), (1,4,3), (2,4,3), (1,3)(2,4), (1,2,4), (1,4)(2,3), (2,3,4), (1,3,4), (1,2)(3,4), (1,4,2) ]

```

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


title: I hate Mondays!

text:
# Question
Title: I hate Mondays!
You should a program in language X, which will only output its source code (i.e function as a quine) when it is not a monday. On monday it should output some string with a levehnstein distance of 4 from the source code. i.e if the code is aaaa on sunday it should output aaaa and on monday it could output ....aaaa or bbbb or cccc or ..aaaa.. etc

---

Read about Levehnstein difference here https://en.wikipedia.org/wiki/Levenshtein\_distance

---

Rules - Your solution must be testable
- No cheating quines, and any other standard loopholes allowed
- Should your language "X" lack access to the date it may assume its a random date at the cost of 35 bytes
- This is code golf and I will accept the shortest solution (in bytes) as winner

# Answer
> 7 votes
# Jolf, ~~19~~ ~~13~~ 9 bytes

```
?wfb+q~2q

```

Try it online.

Saved quite a few bytes thanks to Conor.

```
?wfb+q~2q

?wfb+q~2q
?          if
 wfb       the current weekday - 1 (which is 0 on Monday) is truthy
    +q~2   print the program's source code with 1000 appended to it
           else
        q  print the program's source code

```

# Answer
> 8 votes
# Javascript - ~~47~~ ~~45~~ ~~43~~ ~~42~~ ~~34~~ ~~32~~ 29 bytes

*8 bytes saved thanks to @Downgoat.*

*5 bytes saved thanks to @Dendrobium.*

```
f=_=>(Date()[0]!="M"&&"f=")+f

```

# Answer
> 5 votes
## CJam, ~~18~~ 17 bytes

```
{"_~"et7=({\}|}_~

```

Test it here.

On Mondays, it prints:

```
_~{"_~"et7=({\}|}

```

Dennis found a 16-byte solution which will break in the year 10,000 though:

```
{"_~"et_7=1=<}_~

```

On Mondays, this prints

```
{"_~"et_7=1=<}_~2016

```

... or whatever the current year is.

# Answer
> 3 votes
# Mathematica, 75 bytes

```
StringJoin[If[DayName[] == Monday, "0001", ""], ToString[#0, InputForm]] &

```

Anonymous function, takes no inputs and returns the output. Replace `Monday` with `Friday` (or whatever the current day is) to test.

# Answer
> 3 votes
# Vitsy \+ bash, ~~29~~ 26 bytes

```
'&"etad","M"-)[Y4\a]?rd3*Z

'                            Take a string of everything until hitting another '.
                             This will wrap around as it finds none.
 &                           Create a new stack and push the current stack over.
  "etad"                     Push the string "date" to the stack.
        ,                    Execute the current stack through shell.
         "M"-                Subtract the character "M" from the first item of the
                             current stack.
             )[    ]         If it is equal to zero, do the stuff in brackets.
               Y             Remove the current stack.
                4\a          Push the return character to the stack four times.
                    ?        Rotate over a stack (if there is none, stay put).
                     r       Reverse the stack.
                      d3*    Push the character ' to the stack.
                         Z   Print everything in the current stack.

```

This cannot be tried online as it accesses shell, however, feel free to test this with the downloadable interpreter found here.

Note that this is a variant of the standard quine, `'rd3*Z`.

# Answer
> 3 votes
## Batch, 128 bytes

```
@set/am=%date:~3,2%,a=(14-m)/12,y=%date:~6%-a,d=(%date:~0,2%+y+y/4-y/100+y/400+(m+47)*18/7+a*3)%%7
@if %d%==1 echo @:
@type %0

```

Since Windows XP, `date` doesn't give you the day of the week, so I must directly calculate it from the date. The leap year adjustment wants March-based years so `a` is used as an adjusting factor. `(m+47)*18/7` is quicker than using a month-based lookup table.

Note that you need to invoke the file using its full name (e.g. `monday.bat`). The `echo @:` counts as a distance of 4 because of the extra CR/LF; I used `@:` because the result is still a syntactically valid batch script.

# Answer
> 2 votes
# Java "Only" 2,897 bytes

Take a look at this monstrosity. Can someone help me test this on a monday, I cant figure out how to trick Java into thinking its monday.

```
import java.util.Calendar;public class Quine{public static void main(String[] args){char[] s={83,121,115,116,101,109,46,111,117,116,46,112,114,105,110,116,40,34,105,109,112,111,114,116,32,106,97,118,97,46,117,116,105,108,46,67,97,108,101,110,100,97,114,59,112,117,98,108,105,99,32,99,108,97,115,115,32,81,117,105,110,101,123,112,117,98,108,105,99,32,115,116,97,116,105,99,32,118,111,105,100,32,109,97,105,110,40,83,116,114,105,110,103,91,93,32,97,114,103,115,41,123,34,41,59,83,121,115,116,101,109,46,111,117,116,46,112,114,105,110,116,40,34,99,104,97,114,91,93,32,115,61,123,34,41,59,102,111,114,40,105,110,116,32,105,61,48,59,105,60,115,46,108,101,110,103,116,104,45,49,59,105,43,43,41,123,83,121,115,116,101,109,46,111,117,116,46,112,114,105,110,116,40,40,105,110,116,41,115,91,105,93,43,34,44,34,41,59,125,83,121,115,116,101,109,46,111,117,116,46,112,114,105,110,116,40,40,105,110,116,41,115,91,115,46,108,101,110,103,116,104,45,49,93,43,34,125,59,34,41,59,102,111,114,40,99,104,97,114,32,99,58,32,115,41,123,83,121,115,116,101,109,46,111,117,116,46,112,114,105,110,116,40,99,41,59,125,105,102,40,67,97,108,101,110,100,97,114,46,103,101,116,73,110,115,116,97,110,99,101,40,41,46,103,101,116,40,55,41,61,61,50,41,123,83,121,115,116,101,109,46,111,117,116,46,112,114,105,110,116,40,34,109,111,110,100,34,41,59,125,125,125,83,121,115,116,101,109,46,111,117,116,46,112,114,105,110,116,40,34,105,109,112,111,114,116,32,106,97,118,97,46,117,116,105,108,46,67,97,108,101,110,100,97,114,59,112,117,98,108,105,99,32,99,108,97,115,115,32,81,117,105,110,101,123,112,117,98,108,105,99,32,115,116,97,116,105,99,32,118,111,105,100,32,109,97,105,110,40,83,116,114,105,110,103,91,93,32,97,114,103,115,41,123,34,41,59,83,121,115,116,101,109,46,111,117,116,46,112,114,105,110,116,40,34,99,104,97,114,91,93,32,115,61,123,34,41,59,102,111,114,40,105,110,116,32,105,61,48,59,105,60,115,46,108,101,110,103,116,104,45,49,59,105,43,43,41,123,83,121,115,116,101,109,46,111,117,116,46,112,114,105,110,116,40,40,105,110,116,41,115,91,105,93,43,34,44,34,41,59,125,83,121,115,116,101,109,46,111,117,116,46,112,114,105,110,116,40,40,105,110,116,41,115,91,115,46,108,101,110,103,116,104,45,49,93,43,34,125,59,34,41,59,102,111,114,40,99,104,97,114,32,99,58,32,115,41,123,83,121,115,116,101,109,46,111,117,116,46,112,114,105,110,116,40,99,41,59,125,105,102,40,67,97,108,101,110,100,97,114,46,103,101,116,73,110,115,116,97,110,99,101,40,41,46,103,101,116,40,55,41,61,61,50,41,123,83,121,115,116,101,109,46,111,117,116,46,112,114,105,110,116,40,34,109,111,110,100,34,41,59,125,125,125};System.out.print("import java.util.Calendar;public class Quine{public static void main(String[] args){");System.out.print("char[] s={");for(int i=0;i<s.length-1;i++){System.out.print((int)s[i]+",");}System.out.print((int)s[s.length-1]+"};");for(char c: s){System.out.print(c);}if(Calendar.getInstance().get(7)==2){System.out.print("mond");}}}

```

# Answer
> 2 votes
# GolfScript, ~~21~~ 20 + 35 = ~~56~~ 55 bytes (or ~~22 + 0 = 22~~ 20)

With randomizing, no input expected (following the rules completely):

```
{7rand 0=2*)".~"*}.~

```

Alternatively, date as input, in format like Javascript's `new Date().toString()` (bending the rules a little):

```
{\.,%"M"=2*)".~"*}.~

```

Each solution looks like this:

```
{somecode2*)".~"*}.~

{                }    create a block
                  .   duplicate it
                   ~  execute one copy
 somecode             push 1 if monday or 0 otherwise
         2*           multiply by 2 (2 if monday, 0 otherwise)
           )          add 1 (3 if monday, 1 otherwise)
            ".~"      the tail...
                *     ...copied 1 or 3 times and concatenated together

```

Now the stack looks like this:

```
.~  (or .~.~.~)
{somecode2*)".~"*}

```

... and is printed bottom to top.

The somecode part for random:

```
7rand 0=

7rand          select a random number from 0 to 6, let 0 be monday
      0=       check if equal to 0 (1 if monday, 0 otherwise)

```

The somecode part for input:

```
\.,%"M"=
\             we have the input first and the block on top, so we need to swap them
 .            duplicate the input
  ,           replace the second copy with its length
   %          get every (length)-th character starting from 0, effectively fetching first (M on mondays, something else otherwise)
    "M"=      check if equal to M (1 on mondays, 0 otherwise)

```

# Answer
> 1 votes
## Java, 334 characters

```
import java.util.Calendar;interface Q{static void main(String[]a){String p="import java.util.Calendar;interface Q{static void main(String[]a){String p=%c%s%1$c;System.out.printf(p,34,p);if(Calendar.getInstance().get(7)==2)System.out.print(0<1);}}";System.out.printf(p,34,p);if(Calendar.getInstance().get(7)==2)System.out.print(0<1);}}

```

Based on @RohanJhunjhunwala 's solution, just using the quine method from over here. The difference of four comes by appending true if it's monday. I think it should be possible to shorten that a bit.

# Answer
> 1 votes
# Reng v.5, noncompeting, 56 bytes

Version 5 brings to you object oriented programming!

```
"68¹65¹84¹69¹4&A3¹A1¹B6¹68¹97¹C1¹6Ó`1e4*{Xo}2[r*]rao! ;~

```

This is a standard quine. Simply, `"<code>rao! ;~` executes `<code>`, then outputs the programming, then exits.

`¹` is Manhattan addition, e.g., digit concatenation. This gives the char codes of `DATE`, then `4&` retrieves the date from the date module. (Equivalently, `"DATE"4&`.) This pushes a date object. (While it looks like it should be easily retrievable from the display in the stack, this is just how it prints in the stack display. It is unable to be manipulated.)

The next series provides another pseudo string, translating to `getDay`. Then, we get the property `getDay` of the date object on the stack using . We then execute it with ```. This provides JS's `getDay`. When it's `1`, it's monday. We check for equality with `1` using `1e`, then multiply by four. `{Xo}` pushes a code block that prints (`o`) char 33 (`X`), or `!`. `2[r` creates a new stack with the top two items in reverse order. Then, we repeat (`*`) the code block 4 times (when monday) or 0 times (any other day). On monday, it prints 4 `!`s. Otherwise, it prints nothing. Then the string captured by wraparound is printed, and we have the rest of our source.

Output on monday:

```
!!!!68¹65¹84¹69¹4&A3¹A1¹B6¹68¹97¹C1¹6Ó`1e4*{Xo}2[r*]rao! ;~

```

On other days:

```
68¹65¹84¹69¹4&A3¹A1¹B6¹68¹97¹C1¹6Ó`1e4*{Xo}2[r*]rao! ;~

```

---
Tags: code-golf, quine, date
---


title: Compute the runs of a string

text:
# Question
Title: Compute the runs of a string
Consider the following definitions taken from The number of runs in a string by W. Rytter. Note that word, string and substring are all roughly synonyms.

> A run in a string is a nonextendable (with the same minimal period) periodic segment in a string.
>
> A period p of a word w is any positive integer p such that w\[i\]=w\[i+p\] whenever both sides of this equation are defined. Let per(w) denote the size of the smallest period of w . We say that a word w is periodic iff per(w) \<= |w|/2.

For, example consider the string `x = abcab`. `per(abcab) = 3` as `x[1] = x[1+3] = a`, `x[2]=x[2+3] = b` and there is no smaller period. The string `abcab` is therefore not periodic. However, the string `abab` is periodic as per(abab) = 2.

A run (or maximal periodicity) in a string w is an interval \[i...j\] with j\>=i, such that

* w\[i...j\] is a periodic word with the period p = per(w\[i...j\])
* It is maximal. Formally, neither w\[i-1\] = w\[i-1+p\] nor w\[j+1\] = w\[j+1-p\]. Informally, the run cannot be contained in a larger run with the same period.

Denote by RUNS(w) the set of runs of w.

**Examples**

The four runs of `atattatt` are \[4,5\] = tt, \[7,8\] = tt, \[1,4\] = atat, \[2,8\] = tattatt.

The string `aabaabaaaacaacac` contains the following 7 runs:

\[1,2\] = aa, \[4,5\] = aa, \[7,10\] = aaaa, \[12,13\] = aa, \[13,16\] = acac, \[1,8\] = aabaabaa, \[9,15\] = aacaaca.

Your output should be a list of runs. Each run should specify the interval it represents but does not need to output the substring itself. The exact formatting can be whatever is convenient for you.

The examples use 1-indexing but you are free to use 0-indexing instead if it is more convenient.

**TASK**

Write code that given a string w, output RUNS(w).

**Languages and input**

You can use any language you like and take the input string in whatever form is most convenient. You must give a full program however and you should show an example of your code running on the example input.

# Answer
# Pyth, 38 bytes

```
{smm,hk+ekdfgaFTdcx1xM.ttB+0qVQ>QdZ2Sl

  m                                 SlQ   map for d in [1, …, len(input)]:
                            qVQ>Qd          pairwise equality of input[:-d] and input[d:]
                        tB+0                duplicate this list, prepending 0 to one copy
                      .t          Z         transpose, padding with 0
                    xM                      pairwise xor
                  x1                        find all occurrences of 1
                 c                 2        chop into groups of 2
           f                                filter for groups T such that:
             aFT                              the absolute difference between its elements
            g   d                             is greater than or equal to d
   m                                        map for groups k:
     hk                                       first element
    ,  +ekd                                   pair with the last element plus d
 s                                        concatenate
}                                         deduplicate

```

Test suite
> 2 votes

# Answer
# CJam, 66

```
q:A,2m*{~A>_@)_@<2*@@2*<=},{_2$-2>2,.+={+}&}*]{[_1=\)\0=2*)+]}%_&p

```

Try it online

**Brief explanation:**

The algorithm works in 4 steps (first 3 of them corresponding with the 3 main blocks you can observe):

1. Find all \[length index\] pairs that correspond to a duplicated substring (such as a**aba***aba*aaacaacac); these are parts of runs.
2. Concatenate pairs that are part of the same run, i.e. consecutive indices and same length/period.
3. Construct the actual runs, by taking the minimum index and maximum index + 2 * length - 1.
4. At the end, remove the duplicated runs (which are the same interval obtained with a different period)

I'd like to golf it more, so this is all subject to change.
> 1 votes

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


# Question
Title: Parse and Process the Key-Language Input
Let's parse and process Key-Language! Given the input of a sequence of keyboard keypresses and/or special keys, write a program, function, etc. that outputs the product when all the actions are processed based on the following keyboard:

```
+-------------------------------------------------------+
| ~ | ! | @ | # | $ | % | ^ | & | * | ( | ) | - | + |   |
| ` | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 0 | _ | = |Del|
+-------------------------------------------------------+
|TAB| q | w | e | r | t | y | u | i | o | p | [ | ] | \ |
|   | Q | W | E | R | T | Y | U | I | O | P | { | } | | |
+-------------------------------------------------------+
|CAPS | a | s | d | f | g | h | j | k | l | ; | ' | RET |
|     | A | S | D | F | G | H | J | K | L | : | " |     |
+-------------------------------------------------------+
| SHIFT | z | x | c | v | b | n | m | , | . | / | SHIFT |
|       | Z | X | C | V | B | N | M | < | > | ? |       |
+-------------------------------------------------------+
|                                                       |
|                      SPACEBAR                         |
+-------------------------------------------------------+

```

The keys that output actual characters *not* consisting of whitespace and *are* able to be modified by other keys will be known as "character keys", and those that modify the output of other keys or output whitespace will be known as "special keys". The alphabet character keys, which will be shown in the input with uppercase letters, can be modified with either `Shift` or `Caps Lock` to produce uppercase letters, and the rest of the character keys can only be modified with `Shift` to produce their alternate characters. Therefore `A` in the input corresponds to the `a A` character key, whose normal output is `a` and whose modified output, obtainable with either the `Shift` or `Caps Lock` key, is `A`. On the other hand, `/`, which corresponds to the `/ ?` character key, has a normal output of `/` and a modified output of `?` obtainable with only with `Shift` this time.

# Rules

* The input will *always* be a *string* consisting of a sequence of the character keys and special keys. The full special key to string mapping for the input (i.e. the format they are guaranteed to be in the input) and their corresponding actions/outputs are as follows:

+ `<DEL> -> Delete the previous character (including whitespace). If called when string is empty, nothing happens. If called 2 or more times in a row, 2 consecutive deletes happen. For instance, "RE<DEL><DEL>" should return an empty string ("") and also "R<RET><DEL><DEL>E" should return just "E".`
    + `<CAPS> -> Enable Caps Lock until <CAPS> appears again, upon which it is disabled, although it is not guaranteed to be disabled by the end of the input. Enabling this only modifies the upcoming alphabet keys resulting in them outputting only uppercase letters. For instance, "<CAPS>RE<CAPS>" results in the output "RE", but <CAPS>.<CAPS> would still result in a ".".`
    + `<RET> -> Add a new line.`
    + `<SPC> -> Add a single blank space.`
    + `<TAB> -> Add 4 spaces.`
    + `<SHFT> -> Shift is held down resulting in the alternate character of the upcoming keypress to be output, after which the key is released. For instance, "<SHFT>A" results in the output "A", "<SHFT>1" results in the output "!", and "<SHFT>1234" results in the output "!234" as only the first upcoming keypress is modified and nothing else. It is guaranteed that a character key will succeed a <SHFT>. Therefore, <SHFT><SPC> is not a possible input.`
* An empty string is also possible as input, for which the output should be nothing.
* The use of *any* built-in that solves this problem directly is disallowed.
* The use of standard loopholes is disallowed.

# Test Cases

Presented in the format `Actual String Input -> Actual String Output` followed by an explanation for a few.

1. `1<SHFT>2<TAB><CAPS>R.KAP.<SPC><SHFT>123 -> 1@ R.KAP. !23`

Output `1` as the `1` key is pressed without a toggle, then Shift is held down and the `2` key is pressed resulting in the `@` output. Then the Shift key is released and Tab is pressed, resulting in a 4 spaced indentation. Following up, the Caps Lock key is pressed, after which the `R`,`.`,`K`,`A`,`P`, and `.` keys are pressed, resulting in the output `R.KAP.`. Finally, a single space is output followed by shift resulting in `!23` being output when the `1`,`2`, and `3` keys are pressed at the end.
2. `<SHFT>ABCDEFG<SHFT>HIJK<SHFT>1<SHFT>2<SHFT>3<SHFT>4567890 -> AbcdefgHijk!@#$567890`

The Shift key is held down followed by the `A` key, resulting in the output `A` followed by the output `bcdefg` when the `B-G` keys are pressed. Then, the Shift key is held down again succeeded by the `H` key, after which the output is `H`, followed by `ijk` when the `I-K` keys are pressed. Finally, the `1-4` keys are all modified as shift is held down before each keypress resulting in the output `!@#$` finished off by `567890` when the `5-0` keys re pressed.
3. `<CAPS>THIS<SPC>IS<SPC>IN<SPC>ALL<SPC>CAPS<CAPS><SPC>NOW<SPC>THIS<SPC>IS<SPC>IN<SPC>ALL<SPC>LOWERCASE -> THIS IS IN ALL CAPS now this is in all lowercase`
4. `<TAB><SPC><TAB><SHFT>1 -> !`
5. `<CAPS>WWW<CAPS>.CODEGOLF.STACKEXCHANGE<SHFT>.COM -> WWW.codegolf.stackexchange>com`
6. `PROGRAMMING<CAPS><SPC>IS<SPC><CAPS>AWESOME -> programming IS awesome`
7. `<DEL><RET><DEL><RET><DEL> -> "" (Empty String)`

The delete key is pressed in the beginning after which nothing happens. Then, the Return key is pressed resulting in a new line, which is deleted after the backspace key is pressed again. Finally, the same sequence (new line followed by backspace) is repeated. After all this, the output is an empty string.
8. `<SHFT>HI<SPC>HOW<SPC>ARE<SPC>YOU<SHFT>/<RET><SHFT>I<SPC><SHFT>AM<SPC>O<DEL><SHFT>GOOD<SHFT>1 -> Hi how are you?\nI Am Good!`
9. `<SHFT>,<CAPS>RET<CAPS><SHFT>. -> <RET>`

The string `<RET>` should be the *actual* string output. Thus, this should *not* output a new line.
10. `<CAPS>67890,.;'[]<CAPS> -> 67890,.;'[]`
11. `<CAPS><SHFT>A -> A`
12. `RE<DEL><DEL> -> "" (Empty String)`
13. `U<RET><DEL><DEL>I -> i`
14. `<DEL><DEL><DEL>5<DEL> -> "" (Empty string)`
15. `"" (Empty String) -> "" (Empty String)`

This is so the shortest code in bytes wins!

# Answer
> 6 votes
# 16-bit x86 machine code, 140 139 bytes

*Saved 1 byte by replacing DL with DX in the second-to-last opcode. Also corrected jump offsets in disassembly to match hex dump.*

Since the nature of the task requires some pre-initialized data, and the answer is not a full program but a function, I assume that there's a data section in the program and the linker promptly updates the address of the data. The address placeholder is denoted by '????'.

This is a hex representation of the code. The parameters are pointer to input string in SI and pointer to the output buffer in DI. Strings are assumed to be NULL-terminated.

```
8D1E????89F931D231C0FCAC84C07419D0EA72173C3C74263C41720A3C5A770684F675020C20AAEBE2AAC33C41720B3C5A76F324170402D7EBEC2C27EBF94646AC46240F74154848741748741948741A4848741A39F973B34FEBB04680F601EBAAB020AAAAAAB020EBBCB00AEBB84642EB99

```

Content of the mapping table (25 bytes):

```
"   =<_>?)!@#$%^&*( :{}|`

```

The byte count accounts for both code and data.

## Disassembly:

```
8d 1e ?? ??        lea    bx,ds:???? ;Load address of mapping table to BX
89 f9              mov    cx,di      ;Save pointer to output buffer in CX
31 d2              xor    dx,dx      ;DX is the status register, bit 0 - shift status
31 c0              xor    ax,ax      ;bit 8 - caps lock status
fc                 cld               ;Clear DF

_loop:
ac                 lodsb             ;Fetch next char
84 c0              test   al,al      ;If end of string found
74 19              je     _end       ;break
d0 ea              shr    dl,1       ;Copy shift flag to CF and clear it
72 17              jc     _shift     ;Branch to input procssing with shift set
3c 3c              cmp    al,0x3c    ;If AL == '<'
74 26              je     _special   ;branch to special character processing
3c 41              cmp    al,0x41    ;At this point anything
72 0a              jb     _out       ;not in 'A'..'Z' range
3c 5a              cmp    al,0x5a    ;should be printed unmodified
77 06              ja     _out
84 f6              test   dh,dh      ;If caps lock status flag is set
75 02              jne    _out       ;go to printing right away
0c 20              or     al,0x20    ;otherwise convert to lower case
_out:
aa                 stosb             ;Store AL into output buffer
eb e2              jmp    _loop      ;Continue
_end:
aa                 stosb             ;NULL-terminate the output string
c3                 ret               ;and return

_shift:
3c 41              cmp    al,0x41    ;AL in the range [0x27..0x3b] with
72 0b              jb     _xlat0     ;a couple of holes in it

3c 5a              cmp    al,0x5a    ;AL in the range 'A'..'Z'
76 f3              jbe    _out       ;Since shift is active, go print it

24 17              and    al,0x17    ;AL is 0x5b, 0x5c, 0x5d or 0x7e,
04 02              add    al,0x2     ;convert to the [0x15..0x18] range
_xlat:
d7                 xlatb             ;Lookup mapping table (AL=[BX+AL])
eb ec              jmp    _out
_xlat0:
2c 27              sub    al,0x27    ;Convert AL to be a zero-based index
eb f9              jmp    _xlat      ;Reuse lookup code

_special:                            ;The next 4 or 5 chars are special character opcode
46                 inc    si         ;Since correct input format is guaranteed
46                 inc    si         ;don't bother reading & checking all of them,
ac                 lodsb             ;just load the third one and skip the rest
46                 inc    si         ;The lower 4 bits of the 3rd char
24 0f              and    al,0xf     ;allow to differentiate opcodes

74 15              jz     _sc_caps   ;0x0
48                 dec    ax
48                 dec    ax
74 17              jz     _sc_tab    ;0x2
48                 dec    ax
74 19              jz     _sc_spc    ;0x3
48                 dec    ax
74 1a              jz     _sc_ret    ;0x4
48                 dec    ax
48                 dec    ax
74 1a              jz     _sc_shft   ;0x6

_sc_del:                             ;0xC, <DEL> opcode
39 f9              cmp    cx,di      ;Check the length of the current output
73 b3              jae    _loop      ;DI <= CX ==> NOOP
4f                 dec    di         ;Remove the last char
eb b0              jmp    _loop
_sc_caps:                            ;<CAPS> opcode
46                 inc    si         ;Consume leftover '>' from the input
80 f6 01           xor    dh,0x1     ;Flip caps lock status bit
eb aa              jmp    _loop
_sc_tab:                             ;<TAB> opcode
b0 20              mov    al,0x20    ;Space char
aa                 stosb             ;Print it three times
aa                 stosb             ;and let the <SPC> handler
aa                 stosb             ;do the last one
_sc_spc:                             ;<SPC> opcode
b0 20              mov    al,0x20    ;Space char
eb bc              jmp    _out       ;Go print it
_sc_ret:                             ;<RET> opcode
b0 0a              mov    al,0xa     ;Newline char
eb b8              jmp    _out       ;Go print it
_sc_shft:                            ;<SHFT> opcode
46                 inc    si         ;Consume leftover '>' from the input
42                 inc    dx         ;Set shift status bit (DL is guaranteed to be zero)
eb 99              jmp    _loop

```

For 32-bit instruction set the code is absolutely the same except for the first instruction which is 2 bytes longer due to 32-bit addressing (8d1d???????? lea ebx,ds:????????)

# Answer
> 4 votes
# Retina, 136 bytes

Probably can be golfed further.

```
<SHFT>
§
<SPC>

<TAB>

<CAPS>
¶
<RET>
þ
<DEL>
÷
T`L`l`(?<=^(.*¶.*¶)*).+
T`-=;'[]/\\,.w`\_+:"{}?|<>_)!@#$%^&*(lL`§.
§|¶

i(`þ
¶
[^§]?÷

```

Verify all testcases. (Slightly modified to run all testcases at once.)

# Answer
> 4 votes
# JavaScript (ES6), 207

Updated to fix the bug with repeated deletes, even some bytes shorter.

```
s=>s.replace(/<\w+>|./g,x=>(k=x[3])=='L'?o=o.slice(0,-1):k=='P'?l=!l:k=='F'?s=0:o+=k?k<'C'?'    ':k<'D'?' ':`
`:s?l?x.toLowerCase():x:s=")!@#$%^&*("[x]||'_={}|:"<>?'["-+[]\\;',./".indexOf(x)]||x,l=s,o='')&&o

```

*less golfed*

```
s=>s.replace( /<\w+>|./g, x =>
  (k=x[3]) == 'L' ? o = o.slice(0,-1)
  : k == 'P' ? l = !l
  : k == 'F' ? s = 0
  : o+= k ? k < 'C' ? '    ' : k < 'D' ? ' ' : '\n'
  : s ? l ? x.toLowerCase() : x
  : s = ")!@#$%^&*("[x] || '_={}|:"<>?' ["-+[]\\;',./".indexOf(x)] || x,
  l = s, o = ''
) && o

```

**Test**

```
F=
s=>s.replace(/<\w+>|./g,x=>(k=x[3])=='L'?o=o.slice(0,-1):k=='P'?l=!l:k=='F'?s=0:o+=k?k<'C'?'    ':k<'D'?' ':`
`:s?l?x.toLowerCase():x:s=")!@#$%^&*("[x]||'_={}|:"<>?'["-+[]\\;',./".indexOf(x)]||x,l=s,o='')&&o

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

;[["1<SHFT>2<TAB><CAPS>R.KAP.<SPC><SHFT>123", "1@    R.KAP. !23"]
,["<SHFT>ABCDEFG<SHFT>HIJK<SHFT>1<SHFT>2<SHFT>3<SHFT>4567890", "AbcdefgHijk!@#$567890"]
,["<CAPS>THIS<SPC>IS<SPC>IN<SPC>ALL<SPC>CAPS<CAPS><SPC>NOW<SPC>THIS<SPC>IS<SPC>IN<SPC>ALL<SPC>LOWERCASE", "THIS IS IN ALL CAPS now this is in all lowercase"]
,["<TAB><SPC><TAB><SHFT>1", "         !"]
,["<CAPS>WWW<CAPS>.CODEGOLF.STACKEXCHANGE<SHFT>.COM", "WWW.codegolf.stackexchange>com"]
,["PROGRAMMING<CAPS><SPC>IS<SPC><CAPS>AWESOME", "programming IS awesome"]
,["<DEL><RET><DEL><RET><DEL>", ""]
,["<SHFT>HI<SPC>HOW<SPC>ARE<SPC>YOU<SHFT>/<RET><SHFT>I<SPC><SHFT>AM<SPC>O<DEL><SHFT>GOOD<SHFT>1", "Hi how are you?\nI Am Good!"]
,["<SHFT>,<CAPS>RET<CAPS><SHFT>.", "<RET>"]
,["<CAPS>67890,.;'[]<CAPS>", "67890,.;'[]"]
,["<CAPS><SHFT>A", "A"]
,["U<RET><DEL><DEL>I", "i"]
,["RE<DEL><DEL>", ""]
,["", ""]].forEach(t=>{
  var i=t[0],k=t[1],r=F(i)
  console.log(
    k==r?'OK':'KO',i,'\n->',r,k==r?'\n':'(should be ->'+k+')\n'
  )
})
```

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

---
Tags: code-golf, string, parsing
---


title: Golf Down the PPCG Usernames

text:
# Question
Title: Golf Down the PPCG Usernames
A comment I made in chat and the ensuing conversation inspired me to make this challenge.

> *Am I the only one referred to by initials around here? We are all about golfing things down. We can have MB and D-nob and ... O.*

If I'm known as "CH" then I think everyone else ought to have an initial-based nickname as well.

Here's a list of the top 100 Programming Puzzles & Code Golf users by reputation to play with:

```
Martin Büttner
Doorknob
Peter Taylor
Howard
marinus
Dennis
DigitalTrauma
David Carraher
primo
squeamish ossifrage
Keith Randall
Ilmari Karonen
Quincunx
Optimizer
grc
Calvin's Hobbies
ugoren
Mig
gnibbler
Sp3000
aditsu
histocrat
Ventero
xnor
mniip
Geobits
J B
Joe Z.
Gareth
Jan Dvorak
isaacg
edc65
Victor
steveverrill
feersum
ace
Danko Durbić
xfix
PhiNotPi
user23013
manatwork
es1024
Joey
daniero
boothby
nneonneo
Joey Adams
Timwi
FireFly
dansalmo
grovesNL
breadbox
Timtech
Flonk
algorithmshark
Johannes Kuhn
Yimin Rong
copy
belisarius
professorfish
Ypnypn
trichoplax
Darren Stone
Riot
ProgramFOX
TheDoctor
swish
minitech
Jason C
Tobia
Falko
PleaseStand
VisioN
leftaroundabout
alephalpha
FUZxxl
Peter Olson
Eelvex
marcog
MichaelT
w0lf
Ell
Kyle Kanos
qwr
flawr
James_pic
MtnViewMark
cjfaure
hammar
bitpwner
Heiko Oberdiek
proud haskeller
dan04
plannapus
Mr Lister
randomra
AShelly
ɐɔıʇǝɥʇuʎs
Alexandru
user unknown

```

<sup>(this is how I got it)</sup>

# Challenge

Write a program or function that takes in a list of strings and outputs another list of strings of their minimal, unique, initial-based nicknames, giving preference to those closer to the start of the list.

Apply this method to each string S in the list in the order given to create the nicknames:

1. Split S up into words separated by spaces, removing all spaces in the process.
2. List the nonempty prefixes of the string of the first letters of the words in S, from shortest to longest.
e.g. `Just Some Name``J`, `JS`, `JSN`
3. Choose the first item in this list that is not identical to an already chosen nickname as the nickname for S. Stop if a nickname was chosen, continue to step 4 otherwise.
e.g. if `Just Some Name` was the first string then `J` is guaranteed to be the nickname.
4. List the prefixes again, but this time include the second letter of the first word in it's natural place.
e.g. `Just Some Name``Ju`, `JuS`, `JuSN`
5. Do the same as in step 3 for this list, stopping if a unique nickname is found.
6. Repeat this process with the remaining letters of the first word, eventually inserting letters into the second word, then the third, and so on, until a unique nickname is found.
e.g. The first unique string listed here will be the nickname:
`Jus`, `JusS`, `JusSN`
`Just`, `JustS`, `JustSN`
`Just`, `JustSo`, `JustSoN` (note that `o` was not added after `Just`)
`Just`, `JustSom`, `JustSomN`
`Just`, `JustSome`, `JustSomeN`
`Just`, `JustSome`, `JustSomeNa`
`Just`, `JustSome`, `JustSomeNam`
`Just`, `JustSome`, `JustSomeName`

In the end all the input strings should end up with a unique nickname (potentially identical to the string). **You may assume that none of the input strings will map to the same nickname using this method.**

# Example

**Updated to fix my mistake!**

For the input

```
Martin Buttner
Doorknob
Peter Taylor
Howard
marinus
Dennis
DigitalTrauma
David Carraher
Martin Bitter
Martin Butter
Martin Battle
Martini Beer
Mart Beer
Mars Bar
Mars Barn

```

the nicknames would be

```
M
D
P
H
m
De
Di
DC
MB
Ma
MaB
Mar
MarB
Mars
MarsB

```

# Details

* Input can be from a file (one name per line), or one name at a time via stdin/command line, or as a function argument of a list of strings, or as a function arg of a single string with newlines between names.
* Output should be printed to stdout (one nickname per line) or returned by the function as a list of strings, or as one string with newlines between nicknames.
* Ideally programs will work for names that contain any characters except line terminators. However, you may assume that all the names only contain printable ASCII. (The PPCG names don't.)
* Only the regular space character counts as a word separator. Leading and trailing spaces can be ignored.

# Scoring

The shortest submission in bytes wins. Tiebreaker goes to the answer posted earliest.

# Answer
> 8 votes
# CJam, ~~58~~ 53 bytes

This can be golfed a lot.. But for starters:

```
LqN/{:Q1<aQ,,:)QS/f{{1$<_,@-z1e>}%W<s}+{a1$&!}=a+}/N*

```

**Code Expansion**:

```
L                         "Put an empty array on stack. This is the final nickname array";
 qN/{  ...   }/           "Read the input and split it on new lines. Run the block for each";
     :Q1<a                "Store each name in Q and get its first char. Wrap it in an array";
          Q,,:)           "Get an array of 1 to length(name) integers";
               QS/        "Split the name on spaces";
f{{           }%   }      "for each of the integer in the array, run the code block";
                          "and then for each of the name part, run the inner code block";
   1$<                    "Copy the integer, take first that many characters from the";
                          "first part of the name";
      _,@-z1e>            "Get the actual length of the part and the number of characters";
                          "to be taken from the next name part, minimum being 1";
                W<        "Get rid of the last integer which equals 1";
                  s       "Concat all name parts in the array";
                    +     "Add the list of nick names as per spec with the first character";
{     }=                  "Get the first nick name that matches the criteria";
 a1$&                     "Wrap the nick name in an array and do set intersection with";
                          "the copy of existing nick names";
     !                    "Choose this nick name if the intersection is empty";
N*                        "After the { ... }/ for loop, the stack contains the final";
                          "nick names array. Print it separated with new lines";

```

Try it online here

# Answer
> 9 votes
# JavaScript (ES6) 159

Following the specs and not the example.

I generate the candidate nicknames having a current middle word (at the beginning, the first word). The words before the current are used 'as is'. The words after the current contribute with no - or just the first - character. The current word contributes with 1 more character for each loop.

Example 'Just Some Name' =\> 'Just','Some','Name'
Cw `Just`, position `1`, try `J`, `JS`, `JSN`
Cw `Just`, position `2`, try `Ju`, `JuS`, `JuSN`
Cw `Just`, position `3`, try `Jus`, `JusS`, `JusSN`
Cw `Just`, position `4`, try `Just`, `JustS`, `JustSN`
Now `Just` is exhausted, `Some` becomes Cw, position restarted to 2 (for position 1, all already tried)

Cw `Some`, position `2`, try `Just`, `JustSo`, `JustSoN`
Cw `Some`, position `3`, try `Just`, `JustSom`, `JustSomN`
Cw `Some`, position `4`, try `Just`, `JustSome`, `JustSomeN`
Now `Some` is exhausted, `Name` becomes Cw, position restarted to 2

Cw `Name`, position `2`, try `Just`, `JustSome`, `JustSomeNa`
Cw `Name`, position `3`, try `Just`, `JustSome`, `JustSomeNam`
Cw `Name`, position `4`, try `Just`, `JustSome`, `JustSomeName`
That's all folks!

**The code**

(q is current word position, p is slicing position)

```
F=l=>
  l.map(w=>{
    for(w=w.match(/[^ ]+/g),q=p=0;
        w.every((w,i)=>~o.indexOf(t+=i<q?w:i>q?w[0]:w.slice(0,p+1)),t='')
        &&(w[q][p++]||(p=1,w[++q]));
       );
    o.push(t)
  },o=[])&&o

```

**Test** In Firefox/FireBug console

```
F(['Martin Buttner','Doorknob','Peter Taylor','Howard','marinus'
  ,'Dennis','DigitalTrauma','David Carraher'
  ,'Martin Bitter','Martin Butter','Martin Battle','Martini Beer','Mart Beer'])

```

> \["M", "D", "P", "H", "m", "De", "Di", "DC", "MB", "Ma", "MaB", "Mar", "MarB"\]

# Answer
> 2 votes
# PHP, ~~327~~ ~~289~~ ~~275~~ ~~274~~ 270

There may still be a little golfing potential.

```
while($n=fgets(STDIN)){$c=count($w=preg_split('/\s+/',trim($n)));$p=[];for($k=0;$k<$c;$p[$k]++){for($t='',$j=0;$j<$c;$j++)$t.=substr($w[$j],0,$p[$j]+1);for($j=1;$j<=strlen($t);$j++)if(!in_array($v=substr($t,0,$j),$u))break 2;$k+=$p[$k]==strlen($w[$k]);}echo$u[]=$v,'
';}

```
* Program operates on stdin/stdout, works on ASCII, buggy on UTF
* usage: `php -d error_reporting=0 golfnicks.php < nicknames.txt`
* or `cat <<EOF | php -d error_reporting=0 golfnicks.php` \+ list of names + `EOF`
* To test as function in web browser: fetch the breakdown, uncomment all lines marked with `// FUNC` and comment the one marked with `//PROG`. Try `f(array_fill(0,21,'Just Some Name'));`

**breakdown**

```
#error_reporting(0);function f($a){echo'<pre>'; // FUNC
#foreach($a as$n) // FUNC
while($n=fgets(STDIN)) // PROG
{
    $c=count($w=preg_split('/\s+/',trim($n)));     // split name to words, count them
    $p=[];                                         // initialize cursors
    for($k=0;$k<$c;$p[$k]++)
    {
        for($t='',$j=0;$j<$c;$j++)$t.=substr($w[$j],0,$p[$j]+1); // concatenate prefixes
        for($j=1;$j<=strlen($t);$j++)              // loop through possible nicks
            if(!in_array($v=substr($t,0,$j),$u))   // unused nick found
                break 2;                           // -> break cursor loop
        $k+=$p[$k]==strlen($w[$k]);                // if Cw exhausted -> next word
        // strlen()-1 would be correct; but this works too)
    }
    echo$u[]=$v,'
';
}
#echo '</pre>';} // FUNC

```

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


title: Convert string to time

text:
# Question
Title: Convert string to time
This challenge is inspired by this other.

# The challenge

Write a program or a function in any programming language that given as input a string representing a time in English (see below, for further details) it outputs or prints the equivalent in the 24 hours "digital" format HH:MM.

Shortest code in bytes wins, standard loopholes are forbidden.

# Input format

Your program should be able to handle all this kind of inputs:

```
one minute past 'HOUR'
'MINUTES' minutes past 'HOUR'
quarter past 'HOUR'
half past 'HOUR'
one minute to 'HOUR'
'MINUTES' minutes to 'HOUR'
quarter to 'HOUR'
'HOUR'
'HOUR12' 'MINUTES' AM
'HOUR12' 'MINUTES' PM

```

where: `MINUTES` is a number from 1 to 59 written in English with hyphen; `HOUR` is the name of an hour in one of the formats:

```
midnight
noon
midday
'HOUR24' o'clock
'HOUR12' o'clock AM
'HOUR12' o'clock PM

```

`HOUR12` is a number from 1 to 12 written in English with hyphen; and `HOUR24` is a number from 1 to 23 written in English with hyphen.

# Some examples

```
midnight                                  ->   00:00
midday                                    ->   12:00
twelve o'clock                            ->   12:00
quarter to midnight                       ->   23:45
twenty-two minutes past eight o'clock PM  ->   20:22
thirty-four minutes to fifteen o'clock    ->   14:26
six o'clock AM                            ->   06:00
one minute to twenty-one o'clock          ->   20:59
seven thirteen AM                         ->   07:13
nine fourteen PM                          ->   21:14

```

Good luck!

# Answer
> 2 votes
# Ruby, ~~653~~ 597 Bytes

```
P=/ past | to /;T=%w{q twen thirty fourty fifty sixty el twe thi fourte fifte sixt sevent eighte ninet o tw th fo fi si s e n t}.zip([15,*(2..6).map{|i|i*10},*11..19,*1..10]).to_h;D={'middnight'=>0,'midday'=>12,'noon'=>12};n=->s{s.split('-').reduce(0){|p,v|(Array(T.find{|k,_|v.start_with? k}).last||0)+p}};i=->s{m=0;s=s.gsub(/^\s+|\s+$/,'');c=s.split(P);(c.reverse! if s.match(P));h=D[c[0]]||n.(c[0].gsub(/ o\'clock (A|P)m/,''));h+=(s.end_with?('PM') ? 12 : 0);m=n.(c[1]||c[0].split(' ')[1]) if c[1]||c[0].match(/^\w+ (?!o'clock)/);(m=60-m;h=(h-1)%24)if s.match(/ to /);(sprintf '%02d:%02d',h,m)}

```

Ungolfed:

```
P=/ past | to /
# configuration for translating english words to numbers
T=%w{q twen thirty fourty fifty sixty el twe thi fourte fifte sixt sevent eighte ninet o tw th fo fi si s e n t}.zip([15,*(2..6).map{|i|i*10},*11..19,*1..10]).to_h
D={'middnight'=>0,'midday'=>12,'noon'=>12}

# proc for translating english word groups to a number
n=-> s {
  s.split('-').reduce(0) { |p,v|
    (Array(T.find {|k,_| v.start_with? k}).last || 0) + p
  }
}

i=-> s {
  m=0
  s=s.gsub(/^\s+|\s+$/,'')
  c=s.split(P)
  (c.reverse! if s.match(P))

  # set the hour
  h=D[c[0]]||n.(c[0].gsub(/ o\'clock (A|P)m/,''))
  h+=(s.end_with?('PM') ? 12 : 0)

  # set the minute
  m=n.(c[1]||c[0].split(' ')[1]) if c[1]||c[0].match(/^\w+ (?!o'clock)/)

  # adjust for 'past'
  (m=60-m;h=(h-1)%24)if s.match(/ to /)

  sprintf '%02d:%02d',h,m
}

```

Verification script used:

```
examples = <<EXAMPLES
midnight                                  ->   00:00
midday                                    ->   12:00
twelve o'clock                            ->   12:00
quarter to midnight                       ->   23:45
twenty-two minutes past eight o'clock PM  ->   20:22
thirty-four minutes to fifteen o'clock    ->   14:26
six o'clock AM                            ->   06:00
one minute to twenty-one o'clock          ->   20:59
seven thirteen AM                         ->   07:13
nine fourteen PM                          ->   21:14
EXAMPLES

examples.split("\n").each do |example|
  text, expected = example.split(/\s+->\s+/)
  r = i.(text)
  raise "Unexpected result for \"#{text}\". Got \"#{r}\", expected \"#{expected}\"" unless r == expected
  print "."
end

```

Thank you to Kevin Lau for 47 bytes of optimization

---
Tags: code-golf, date, natural-language
---


# Question
Title: Print a table of numbers in decimal and 2**i bases
Computers live by binary. All programmers know binary.

But the `2**x` bases are often neglected as non-practical, while they have beautiful relations to binary.

To show you one example of such a beatiful relation, 19 will be my testimonial.

```
19 10011 103 23 13 j

```
* 19 is decimal, included for clarity.
* 10011 is 19 in binary.
* 103, in base 4 is made starting from binary this way:

+ log2(4) == 2, let us remember two.
    + Pad 10011 so that it has a multiple of 2 length -\> 010011
    + Take digits 2 by 2 from left to right and treat them as 2-digits binary numbers:

    - 01 -\> 1
        - 00 -\> 0
        - 11 -\> 3

**Done**, 10011 in base-4 is 103.

For base 8, do the same but 3-by-3 as log2(8) = 3.

* Pad 010011
* 010 -\> 2
* 011 -\> 3

23, **Done**.

For base 16, do the same but 4-by-4 as log2(16) = 4.

* Pad 00010011
* 0001 -\> 1
* 0011 -\> 3

13, **Done**.

**Task**

Given a max number as input, you shall output a table

```
base-ten-i base-two-i base-four-i base-eight-i base-sixteen-i base-thirtytwo-i

```

for i that goes from 0 to n inclusive. Binary numbers are the epitome of the absolute minimum needed to work, so your code should be as short as possible.

**Restrictions and bonuses**

* Base-ten -\> binary and binary -\> Base-ten built-ins are considered loopholes as Base-a -\> Base-b are.
* If you generate all the `2**i` (for i \> 2) bases by using the relations over mentioned you get a `*0.6` bonus, but general base conversions (written by yourself) are allowed.

**Example table**

```
> 32
0 0 0 0 0 0
1 1 1 1 1 1
2 10 2 2 2 2
3 11 3 3 3 3
4 100 10 4 4 4
5 101 11 5 5 5
6 110 12 6 6 6
7 111 13 7 7 7
8 1000 20 10 8 8
9 1001 21 11 9 9
10 1010 22 12 a a
11 1011 23 13 b b
12 1100 30 14 c c
13 1101 31 15 d d
14 1110 32 16 e e
15 1111 33 17 f f
16 10000 100 20 10 g
17 10001 101 21 11 h
18 10010 102 22 12 i
19 10011 103 23 13 j
20 10100 110 24 14 k
21 10101 111 25 15 l
22 10110 112 26 16 m
23 10111 113 27 17 n
24 11000 120 30 18 o
25 11001 121 31 19 p
26 11010 122 32 1a q
27 11011 123 33 1b r
28 11100 130 34 1c s
29 11101 131 35 1d t
30 11110 132 36 1e u
31 11111 133 37 1f v
32 100000 200 40 20 10

```

# Answer
# CJam, 54 * 0.6 = 32.4 bytes

```
q~){_5,f{)L@{2md@+\}h(%/Wf%W%{{\2*+}*_9>{'W+}&}%S\}N}/

```

Test it here.

For reference, here is a shorter solution which doesn't qualify for the bonus (at 39 bytes):

```
q~){:X5{SLX{2I)#md_9>{'W+}&@+\}h;}fIN}/

```
> 2 votes

# Answer
# Pyth, 52 * 0.6 = 31.2 bytes

```
L?b+%b2y/b2YVUhQjd+NmjkX|_uL++GGHZ_McyNd]ZUQ+jkUTGS5

```

Test it online

My non-bonus answer is 39 bytes

```
M?G+g/GHH@+jkUTG%GHkVUhQjd+N|R0gLN^L2S5

```
> 1 votes

# Answer
# PHP, ~~232~~ ~~230~~ ~~233~~ 217 * 0.6 = 130.2

no chance beating the golfing languages, but I liked the challenge.

```
for(;$d<=$n;$d++){echo'
',$d|0;for($k=$d,$b='';$k;$k>>=1)$b=($k&1).$b;for($w=1;$w<6;$w++,print" $z"|' 0')for($z='',$k=strlen($b);-$w<$k-=$w;$z=($e>9?chr($e+87):$e).$z)for($e=0,$y=1,$j=$w;$j--;$y*=2) $e+=$y*$b[$j+$k];}

```
* usage: prepend `$n=32;` or replace `$n` with `32` (or any other non-negative integer); call via cli
* If that is not accepted, replace `$n` with `$_GET[n]` (+6/+3.6) and call either in the browser
or on cli with `php-cgi -f bases.php -n=32`
* Replace the line break with `<br>` or prepend `<pre>` to test in browser
* may throw notices for undefined variables and unintialized string offsets in newer PHP versions.
Remove E\_NOTICE from error\_reporting (prepend `error_reporting(0);`) to suppress them.
* tested in 5.6

break down:

```
for(;$d<=$n;$d++) // loop decimal $d from 0 to $n
{
    echo'
',$d|0; // print line break and decimal
    for($k=$d,$b='';$k;$k>>=1)$b=($k&1).$b; // convert $d to binary
    for($w=1;$w<6;$w++,
        print" $z"|' 0' // print number generated in inner loop (echo doesn´t work here)
    )
        for($z='',$k=strlen($b);-$w<$k-=$w; // loop from end by $w
            $z=($e>9?chr($e+87):$e).$z // prepend digit created in body
        )
            for($e=0,$y=1,$j=$w;$j--;$y*=2) $e+=$y*$b[$j+$k]; // convert chunk to 2**$w
}

```

major edit:

* used some index magic to revamp the inner loop -\> now works backwards on the whole string (no more padding, no more splitting or copying the binary)
* moved parts of the loop bodies to the heads to eliminate braces
* had to add ~~7~~ 4 bytes to fix the decimal 0 results after the revamp

# non-bonus version, 142 bytes

```
for(;$d<=$n;$d++,print'
',$d|0)for($w=1;$w<6;$w++,print" $z"|' 0')for($k=$d,$y=1,$z='';$k&&$y<<=$w;$k>>=$w)$z=(9<($e=$k%$y)?chr($e+87):$e).$z;

```

**PHP beats Python?**
Even if I added the 6 (3.6) bytes to make the snippet a program, I´d still beat Python (223\*0.6=133.8 or 148 non-bonus vs. 158). Amazing.
> 0 votes

# Answer
## Python3 - 189, 167, 166 150 bytes

```
for i in range(int(input())+1):f=lambda b,n=i,c="0123456789abcdefghijklmnopqrstuv":n<b and c[n]or f(b,n//b)+c[n%b];print(i,f(2),f(4),f(8),f(16),f(32))

```

Saved 16 bytes with the help of @LeakyNun!

## Bonus version - 296 * 0.6 = 177.6 279 * 0.6 = 167.4 bytes

```
p=lambda b,c:"".join(str(int(b[i:i+c],2))for i in range(0,len(b),c))
z=lambda s:len(s)%2 and s or "0"+s
for i in range(int(input())+1):f=lambda n,b,c="0123456789abcdefghijklmnopqrstuv":n<b and c[n]or f(n//b,b)+c[n%b];v=f(i,2);d=z(v);print(i,v,p(d,2),p(d,3),p(d,4),p(d,5),f(i,32))

```

Slightly more readable version of the bonus version.

```
p=lambda b,c:"".join(str(int(b[i:i+c],2))for i in range(0,len(b),c))
z=lambda s:len(s)%2 and s or "0"+s
for i in range(int(input())+1):
    f=lambda n,b,c="0123456789abcdefghijklmnopqrstuv":n<b and c[n] or f(n//b,b) + c[n%b]
    v=f(i,2)
    d=z(v)
    print(i,v,p(d,2),p(d,3),p(d,4),p(d,5),f(i,32))

```
> 0 votes

# Answer
## Ruby, 80 bytes (non-bonus version)

```
m=ARGV[0].to_i;(0..m).each{|n|puts [10,2,4,8,16,32].map{|b|n.to_s(b)}.join(' ')}

```
> 0 votes

---
Tags: code-golf, number, number-theory, base-conversion, binary
---


title: Was it Really Canada Day?

text:
# Question
Title: Was it Really Canada Day?
July 1st is Canada day (yay Canada)! Or is it? It seems that the Wikipedia page for this day has a lot of Canada related content, but is there another day which is more Canadian?

Your task is to write a program or function which takes a date (month and day) as input and returns or outputs the number of mentions of "Canada" on the Wikipedia page for the inputed date. Some rules:

* Dates may be input in any reasonable format of your choice
* Your submission must pull data from the url `en.wikipedia.org/wiki/Month_Day`.
* Only `"Canada"` must be searched for and counted included substrings, and only in title case. `"Canadian"` does not count, however `"Canada's"` does count. As long as the exact, case-senstitive text `"Canada"` exists within a string, it is a match
* Contents of the page are considered anything within the corresponding `.html` file (i.e. what shows up if you download as page as a `.html` and open it in Notepad)
* Result may be output to STDOUT, returned, or displayed in any other reasonable manner

Test Cases:

```
July 1 => 34
May 14 => 1
Oct 31 => 2
July 4 => 2

```

This is code golf, so shortest submission wins

(As an unrewarded bonus, I'm interested to see what the day with the highest count is)

# Answer
# Pyth, 31 bytes

```
/jk'+"http://enwp.org/"z"Canada

```

Does not work on the online implementation, the server disables Internet access. I wanted to use http://wki.pe/July\_1 but sadly it's a client-side redirect so it fetches the wrong page. The input format is `July_1`.

The code is basically just:

```
"".join(open("http://enwp.org/"+input())).count("Canada")

```
> 4 votes

# Answer
# Bash, 43 42 40 bytes

```
curl -L enwp.org/$@|grep -o Canada|wc -l

```

Uses `curl`, `grep`, and `wc` to count occurrences of "Canada" in specified webpage. Like the other answers, input is given in the format `July_1`. This is my first time posting on the Code Golf SE and I'm not quite familiar with all of the rules. Any feedback would be most welcome.

*Didn't realize that output to* `STDERR` *is traditionally ignored. Thanks for the 3 bytes, Dennis!*
> 24 votes

# Answer
# Perl 5, 39 bytes

38 bytes, plus 1 for `-pe` instead of `-e`

```
$_=()=`curl -L enwp.org/$_`=~/Canada/g

```

Takes input like `July_1`.

Thanks to busukxuan for saving me seven bytes.
> 15 votes

# Answer
# Python 3.5, ~~117~~ ~~111~~ ~~98~~ 90 bytes

(*-8 bytes (`98 -> 90`) thanks to alexwlchan*)

```
from urllib.request import*
lambda i:urlopen('http://enwp.org/'+i).read().count(b"Canada")

```

Simply uses Python's built-in "urllib" library to fetch HTML data and then counts the occurrences of the word "Canada" in that data. Will try and golf more over time where and when I can. Call it by renaming the `lambda` function to anything and then calling that name like a normal function wrapped in `print()`. For instance, if the function were named `H`, then you would call it like `print(H(Month_Day))`.
> 7 votes

# Answer
# Mathematica, 60 bytes

```
Import["http://enwp.org/"<>#,"Source"]~StringCount~"Canada"&

```

Anonymous function. Similarly to the Perl 5 solution, takes input like `July_1`.
> 5 votes

# Answer
# C#, 85 bytes

```
return Regex.Matches(new WebClient().DownloadString("http://enwp.org/"+d),"Canada").Count;

```

Takes input `d` like `July_1`.

And `July_1` *is* truly Canada Day, having the most references. With `February_1` and `April_23` sharing 2nd place with 18 `"Canada"`s each.

# Find `"Canada"` day (in parallel), 207 bytes:

```
return Enumerable.Range(0,366).Select(i=>new DateTime(8,1,1).AddDays(i).ToString("MMMM_d")).AsParallel().OrderBy(d=>Regex.Matches(new WebClient().DownloadString("http://enwp.org/"+d),"Canada").Count).Last();

```

(Year 8 is the leap year with the shortest representation). Potentially inefficient, in that the `OrderBy` probably generates \>366 web calls, but just going for shorter and appears to complete in not much more time.
> 5 votes

# Answer
# PowerShell, 52 bytes

```
((iwr enwp.org/$($args[0]))-csplit"Canada").length-1

```
* Input as `July_1`.
* `iwr` is short for `Invoke-WebRequest`.
* `$($args[0])` is first command line argument. Start script as `OhCanada.ps1 July_1`.
* `-csplit` is case sensitive split.
> 5 votes

# Answer
# R, 99 96 bytes

x=function(d){p=readLines(paste0("http://enwp.org/",d));sum(nchar(p)-nchar(gsub("Canada","",p)))/6}

```
d=scan(,"");p=readLines(paste0("http://enwp.org/",d));sum(nchar(p)-nchar(gsub("Canada","",p)))/6

```

This takes input d in the form "July\_1" and returns the count of Canadas. It counts the words by counting the number of characters on the page, then removes the word Canada from the page and counts the characters again. The number of times Canada shows up is the difference in these counts divided by the number of letters in Canada, 6.

edit: I appreciate the tip below about replacing my function with scan.
> 4 votes

# Answer
# ES6, 89 bytes

```
d=>fetch('http://enwp.org/'+d).then(r=>r.text().then(t=>alert(t.split`Canada`.length-1)))

```

Sadly Unwrapping all the promises penalises the size :/
> 4 votes

# Answer
# Clojure, 71 bytes

```
#(count(re-seq #"Canada"(slurp(str"https://en.wikipedia.org/wiki/"%))))

```

Yeah, it would be nice to use `http://enwp.org` but I guess `slurp` does not handle redirects(?). Anonymous function which take day in the format "July\_1".
> 2 votes

# Answer
# Ruby + curl, 44 bytes

```
p`curl -L enwp.org/#$_`.scan(/Canada/).size

```

`ruby -n` \+ 43 bytes. Takes input like `July_1`.
> 2 votes

# Answer
# PHP, 65 bytes

```
echo substr_count(file_get_contents('http://enwp.org'),'Canada');

```
> 2 votes

---
Tags: code-golf, string, internet
---