Variant of racetrack with exact finishing point and zero terminal velocity Introduction
The challenge is a very interesting variant of the game racetrack and those two challenges:

To Vectory! – The Vector Racing Grand Prix
Program a Racing Car

Source of this challenge is here (in German): c't-Racetrack
This challenge is especially interesting (and different from the two abovementioned challenges) because it combines a huge search-space with some exact conditions that have to be met. Because of the huge search-space exhaustive search techniques are hard to use, because of the exact conditions approximate methods are also not easily usable. Because of this unique combination (plus the underlying intuition from physics) the problem is fascinating (and everything in connection with racing cars is fascinating anyway ;-)
Challenge
Have a look at the following racetrack (source):

You have to start at (120,180) and finish exactly at (320,220) ("Ziel" in German) without touching one of the walls.
The car is controlled by acceleration vectors of the form (a_x,a_y) - as an example:
(8,-6)
(10,0)
(1,9)

The first number is the acceleration for the x-vector, the second for the y-vector. They have to be integers because you are only allowed to use the integer points on the grid. Additionally the following condition has to be met:
a_x^2 + a_y^2 <= 100,

which means that acceleration in any direction has to be below or equal to 10.
To see how it works have a look at the following picture (source):

As an example: Starting from (120,180) you accelerate by 8 in x-direction and by -6 in y-direction. For the next step this is your velocity where you add your acceleration (10,0) to get (physically correct) your next resulting movement (to point (146,168). The resulting movement is what counts when it comes to examining whether you touched one of the walls. In the next step you again add your next acceleration vector to your current velocity to get the next movement and so on. So at every step your car has a position and a velocity. (In the illustrative picture above the blue arrows are for the velocity, the orange arrows for acceleration and the dark red arrows for the resulting movement.)
As an additional condition you have to have (0,0) terminal velocity when you are on the finishing point (320,220).
The output has to be a list of acceleration vectors in the abovementioned form.
The winner is the one who provides a program which finds a solution with the fewest acceleration vectors.
Tiebreaker
Additionally it would be great if you can show that this is an optimal solution and whether this is the only optimal solution or whether there are several optimal solutions (and which they are).
It would also be good if you could give a general outline of how your algorithm works and comment the code so that we can understand it.
I have a program which checks whether any given solution is valid and I will give feedback.
Addendum
You can use any programming language but I would be especially delighted if somebody used R because I use it a lot in my day job and somehow got used to it :-)
Addendum II
For the first time I started a bounty - hopefully this get's the ball rolling (or better: get's the car driving :-)

Python, 24 steps (work in progress)
The idea was to solve the continuous problem first, vastly reducing the search space, and then quantize the result to the grid (by just rounding to the nearest gridpoint and searching the surrounding 8 squares)
I parametrize the path as a sum of trigonometric functions (unlike polynomials, they dont diverge and are easier to keep in check). I also control the velocity directly instead of the acceleration, because its easier to enforce the boundary condition by simply multiplying a weighting function that tends to 0 at the end.
My objective function consists of
-exponential score for acceleration > 10
-polynomial score for euclidean distance between the last point and the target
-high constant score for each intersection with a wall, decreasing towards the edges of the wall
To minimize the score, i throw it all into Nelder-Mead optimization and wait a few seconds. The algorithm always succeeds in getting to the end, stopping there and not exceeding the maximum acceleration, but it has troubles with walls. The path either teleports through corners and gets stuck there, or stops next to a wall with the goal just across (left image)

During testing, i got lucky and found a path that was squiggled in a promising way (right image) and after tweaking the parameters some more i could use it as a starting guess for a successful optimization.
Quantization
After finding a parametric path, it was time to remove the decimal points. Looking at the 3x3 neighborhood reduces the search space from roughly 300^N to 9^N, but its still too big and boring to implement. Before i went down this road, i tried adding a "Snap to Grid" term to the objective function (the commented parts). A hundred more steps of optimization with the updated objective and simply rounding was enough to get the solution.

[(9, -1), (4, 0), (1, 1), (2, 2), (-1, 2), (-3, 4), (-3, 3), (-2, 3), (-2, 2), (
-1, 1), (0, 0), (1, -2), (2, -3), (2, -2), (3, -5), (2, -4), (1, -5), (-2, -3),
(-2, -4), (-3, -9), (-4, -4), (-5, 8), (-4, 8), (5, 8)]

The number of steps was fixed and not part of optimization, but since we have an analytical description of the path, (and since the maximal acceleration is well below 10) we can reuse it as a starting point for further optimization with a smaller number of timesteps
from numpy import *
from scipy.optimize import fmin
import matplotlib.pyplot as plt
from matplotlib.collections import LineCollection as LC

walls = array([[[0,0],[500,0]],   # [[x0,y0],[x1,y1]]
        [[500,0],[500,400]],
        [[500,400],[0,400]],
        [[0,400],[0,0]],

        [[200,200],[100,200]],
        [[100,200],[100,100]],
        [[100,100],[200,100]],

        [[250,300],[250,200]],

        [[300,300],[300,100]],
        [[300,200],[400,200]],
        [[300,100],[400,100]],

        [[100,180],[120, 200]], #debug walls
        [[100,120],[120, 100]],
        [[300,220],[320, 200]],
        #[[320,100],[300, 120]],
])

start = array([120,180])
goal = array([320,220])

###################################
# Boring stuff below, scroll down #
###################################
def weightedintersection2D(L1, L2):
    # http://stackoverflow.com/questions/563198/how-do-you-detect-where-two-line-segments-intersect
    p = L1[0]
    q = L2[0]
    r = L1[1]-L1[0]
    s = L2[1]-L2[0]
    d = cross(r,s)
    if d==0: # parallel
        if cross(q-p,r)==0: return 1 # overlap
    else:
        t = cross(q-p,s)*1.0/d
        u = cross(q-p,r)*1.0/d
        if 0<=t<=1 and 0<=u<=1: return 1-0*abs(t-.5)-1*abs(u-.5) # intersect at p+tr=q+us
    return 0

def sinsum(coeff, tt):
    '''input: list of length 2(2k+1),
    first half for X-movement, second for Y-movement.
    Of each, the first k elements are sin-coefficients
    the next k+1 elements are cos-coefficients'''
    N = len(coeff)/2
    XS = [0]+list(coeff[:N][:N/2])
    XC =     coeff[:N][N/2:]
    YS = [0]+list(coeff[N:][:N/2])
    YC =     coeff[N:][N/2:]
    VX = sum([XS[i]*sin(tt*ww[i]) + XC[i]*cos(tt*ww[i]) for i in range(N/2+1)], 0)
    VY = sum([YS[i]*sin(tt*ww[i]) + YC[i]*cos(tt*ww[i]) for i in range(N/2+1)], 0)
    return VX*weightfunc, VY*weightfunc

def makepath(vx, vy):
    # turn coordinates into line segments, to check for intersections
    xx = cumsum(vx)+start[0]
    yy = cumsum(vy)+start[1]
    path = []
    for i in range(1,len(xx)):
        path.append([[xx[i-1], yy[i-1]],[xx[i], yy[i]]])
    return path

def checkpath(path):
    intersections = 0
    for line1 in path[:-1]: # last two elements are equal, and thus wrongly intersect each wall
        for line2 in walls:
            intersections += weightedintersection2D(array(line1), array(line2))
    return intersections

def eval_score(coeff):
    # tweak everything for better convergence
    vx, vy = sinsum(coeff, tt)
    path = makepath(vx, vy)
    score_int = checkpath(path)
    dist = hypot(*(path[-1][1]-goal))
    score_pos = abs(dist)**3
    acc = hypot(diff(vx), diff(vy))
    score_acc = sum(exp(clip(3*(acc-10), -10,20)))
    #score_snap = sum(abs(diff(vx)-diff(vx).round())) + sum(abs(diff(vy)-diff(vy).round()))
    print score_int, score_pos, score_acc#, score_snap
    return score_int*100 + score_pos*.5 + score_acc #+ score_snap

######################################
# Boring stuff above, scroll to here #
######################################
Nw = 4 # <3: paths not squiggly enough, >6: too many dimensions, slow
ww = [1*pi*k for k in range(Nw)]
Nt = 30 # find a solution with tis many steps
tt = linspace(0,1,Nt)
weightfunc = tanh(tt*30)*tanh(30*(1-tt)) # makes sure end velocity is 0

guess = random.random(4*Nw-2)*10-5
guess = array([ 5.72255365, -0.02720178,  8.09631272,  1.88852287, -2.28175362,
        2.915817  ,  8.29529905,  8.46535503,  5.32069444, -1.7422171 ,
       -3.87486437,  1.35836498, -1.28681144,  2.20784655])  # this is a good start...
array([ 10.50877078,  -0.1177561 ,   4.63897574,  -0.79066986,
         3.08680958,  -0.66848585,   4.34140494,   6.80129358,
         5.13853914,  -7.02747384,  -1.80208349,   1.91870184,
        -4.21784737,   0.17727804]) # ...and it returns this solution

optimsettings = dict(
    xtol = 1e-6,
    ftol = 1e-6,
    disp = 1,
    maxiter = 1000, # better restart if not even close after 300
    full_output = 1,
    retall = 1)

plt.ion()
plt.axes().add_collection(LC(walls))
plt.xlim(-10,510)
plt.ylim(-10,410)
path = makepath(*sinsum(guess, tt))
plt.axes().add_collection(LC(path, color='red'))
plt.plot(*start, marker='o')
plt.plot(*goal, marker='o')
plt.show()

optres = fmin(eval_score, guess, **optimsettings)
optcoeff = optres[0]

#for c in optres[-1][::optimsettings['maxiter']/10]:
for c in array(optres[-1])[logspace(1,log10(optimsettings['maxiter']-1), 10).astype(int)]:
    vx, vy = sinsum(c, tt)
    path = makepath(vx,vy)
    plt.axes().add_collection(LC(path, color='green'))
    plt.show()

To Do: GUI that lets you draw an initial path to get a rough sense of direction. Anything is better than randomly sampling from 14-dimensional space


Probability to clear the board or win In the game Hearthstone there is a playing board containing friendly and enemy minions, and two heroes - yours and the enemy's.

To generalize and simplify, we will assume it's your turn, the opponent has 0-7 minions with given health values on the board, and is at H life points. We will ignore our side of the board entirely.

Now we will cast a supercharged version of Arcane Missiles. This ability shoots a random enemy (uniformly selected from all alive minions and the hero) for 1 damage, repeated A times. Note that if a target dies (reduced to 0 health), it can not be hit again.

Given H, A and a list L containing the health values of the minions, output the probability as a percentage accurate to 2 digits after the decimal point that either or both the hero dies, or every minion dies (clearing the board).

Some examples logically derived:

H: 30, A: 2, L: [1, 1]

We have no chance of killing our opponent here. To clear the board, both shots
must hit a minion. The first shot has a 2/3 chance of hitting a minion, then
that minion dies. The second shot has a 1/2 chance. The probability of clearing
the board or killing our opponent is thus 2/6 = 33.33%.

H: 2, A: 3, L: [9, 3, 4, 1, 9]

We have no chance of clearing the board here. 2/3 shots must hit the hero. However,
if any of the shots hit the 1 health minion, it dies, increasing the odds for
future shots.

4/6 the first shot hits a health minion. The next two shots must hit the hero,
for a total probability of 4/6 * 1/6 * 1/6.

1/6 the first shot hits the 1 health minion and it dies. The next two shots must
hit the hero, for a total probability of 1/6 * 1/5 * 1/5.

1/6 the first shot hits the hero. Then there are three options again:

    1/6 the second shot hits the hero.
    4/6 the second shot hits a healthy minion. The last shot must hit 1/6.
    1/6 the second shot hits the 1 health minion. The last shot must hit 1/5.

This last option gives a probability of 1/6 * (1/6 + 4/6 * 1/6 + 1/(5*6)). The
total probability is the chance of any of these scenarios happening, or:

    4/6 * 1/6 * 1/6 + 1/(6*5*5) + 1/6 * (1/6 + 4/6 * 1/6 + 1/(5*6)) = 7.70%

As you can see, it gets complicated quickly... Good luck!

Your score is the number of bytes of code of your answer. If your code computes a probability exactly rather than simulating boards, halve your score. Lowest score wins.

Pyth, (67 bytes) / 2 = 33.5

L_,*lbJ*FeCbsm*hd/JedbM?&hHstH?GymgtG-XdKH_1_!dlH,01,TT*100cFghQstQ

This qualifies for the bonus even though I had to manually implement arbitrary precision rationals.

(I wish Pyth5 was already a thing).

Input from STDIN in the format A, H, L

Demonstration.

Corrected to output percentage. Percentage is as acurate as possible, due to use of integer math until the last step.

At the high level, the first segment, L_,*lbJ*FeCbsm*hd/Jedb, is a helper function which takes a list of rationals in the form of 2 element lists, and outputs their average as an (unreduced) rational.

The second segment, M?&hHstH?GymgtG-XdKH_1_!dlH,01,TT, recusively calculates the probability of victory.

The third segment, cFghQstQ formats the input to fit the function and performs the final division.

On the second example case, the final unreduced 2-tuple is too long to fit on the screen:

[83158592487544376524800000000000000000000, 1079462498636393349120000000000000000000000]

Fortunately, Pyth does have arbitrary precision integers.


Counting the Endpoints of an ASCII Art You should write a program or function which receives a string representing an ASCII art as input and outputs or returns the number of endpoints in the input.

The input will consist of the characters space - | + (with 0, 2, 2 and 4 endpoints respectively) and linebreaks. E.g.:

-|++-
  +

Two adjacent characters are connected and hence lose 1 endpoint each in the following cases:

--  -+  +- |  |  +  +  ++
           |  +  |  +

The first example has

2+2+2+2+1+
    3        = 12

endpoints.

Input

Input will be a string consisting of the characters space, -, |, + and newline.
Input length can be 0 length and any input matching the above description is valid (in regex input is [ -+|\n]*).
Trailing newline is optional.

Output

A single non-negative integer, the number of endpoints.

Examples

Outputs are after the last row of their inputs.

+
4

-|++-
  +
12

+--+
|  |
+--+
8

  |  |
  +--+-- |||
12

--++
 |||--
10

<empty input>
0

|
|
2

--
++--
 ++
   --+
  +++ ||

 ----
30

This is code golf so the shortest entry wins.

Snails, 29
A
\+|\-)lr!\-|(\+|\|)n!\|}!\+

I added line comments with ,,, in order to make a commented version.
A                    ,, Count all accepting paths
        \+ | \- )    ,, Literal '+' or '-'
        lr           ,, Set direction to left or right
        !\-          ,, Assert next char is not '-'
    |                ,, Or...
        ( \+ | \| )  ,, Literal '+' or '|'
        n            ,, Turn 90 degrees right or left (from initial direction right)
        !\|          ,, Assert next char is not '|'
}                    ,, Group everything previous
!\+                  ,, Assert next char is not '+'


Shortest URL regex match in JavaScript Create the shortest regular expression that will roughly match a URL in text when run in JavaScript

Example:

"some text exampley.com".match(/your regular expression goes here/);

The regular expression needs to

capture all valid URLS that are for http and https.
not worry about not matching for URL looking strings that aren't actually valid URLS like super.awesome/cool
be valid when run as a JavaScript regex

Test criteria:

Match:

http://example.com
http://example.com/
http://example.com/super
https://example.com/super
example.com/super
example.com
example.com/su-per_duper/?add=yes&subtract=no
example.com/archive/index.html
twitter.com/#!/reply
example.com/234ret2398oent/234nth
codegolf.stackexchange.com/questions/464
crazy.wow.really.example.com/?cat=nth%3E
example-example.com
example1.com

Not Match:

example
super/cool
Good Morning
i:can
hello.

Here is a test that might help clarify a bit http://jsfiddle.net/MikeGrace/gsJyr/

I apologize for the lack of clarity, I hadn't realized how awful matching URLs was.

This one works:

var re = /(^|\s)((https?:\/\/)?[\w-]+(\.[\w-]+)+\.?(:\d+)?(\/\S*)?)/gi;

/*
(^|\s)                            : ensure that we are not matching an url
                                    embeded in an other string
(https?:\/\/)?                    : the http or https schemes (optional)
[\w-]+(\.[\w-]+)+\.?              : domain name with at least two components;
                                    allows a trailing dot
(:\d+)?                           : the port (optional)
(\/\S*)?                          : the path (optional)
*/

Passes the tests at http://jsfiddle.net/9BYdp/1/

Also matches:

example.com. (trailing dot)
example.com:8080 (port)


Storing a DNS name as compactly as possible in memory (preferably in C#) What is the most compact way to encode/save DNS names in memory?

For example, storing "www.google.com" as a string in .NET will result in the object being encoded as UTF-16, and it will consume twice as much memory as plain ASCII... but for the purpose of storing DNS names, ASCII is overkill.

The only characters that are needed are:

A..Z  (case insensitive)
0..9
Hyphen
underscore
period
Asterisk (not legal DNS, but used in ACLs such as *.google.com) always as a leading character, never elsewhere.

A total of 40 characters.. which fits within single byte with plenty room to spare.

My code golf question/challenge is what is the most compact way to store a string of characters in memory and maximizing in memory storage?

The inspiration for this challenge came from this blog entry.

You could interpret it as a base 39 number. Since only the first character can be an asterisk, you can encode it as the sign. If i use the characters as digits in the order you named them, www.google.com would be 10903065870001232914011 in decimal and 24f0e6f41d8ecd3a65b in hex, which could be stored in 10 bytes.

*.google.com would be -310664672884413873 in decimal and fbb04c2040762a4f in hex, if you store it in 8 bytes.


Draw a distribution diagram! Challenge

You are given three integers as input - min_value, max_value, sample_size, that you can pass to your answer as either array or several parameters.

Your task is to output a diagram in any convenient format, that shows the frequency of numbers in the (min_value, max_value) range showing up when a random number in the (min_value, max_value) range is picked sample_size times. The random number sequence should be generated within your answer.

With large ranges and sample sizes, you're free to change the steps your diagram uses, as long as the representation remains accurate.

Example

With [1, 5, 10] as input:

o o o x o
x o x x x
x x x x x
1 2 3 4 5

With [1, 100, 15] as input (in steps of 10, so 00 shows 1-9, 10 shows 10-19, etc.):

xx oo oo xx oo xx oo oo oo oo
xx oo oo xx oo xx xx oo oo oo
xx xx oo xx xx xx xx xx xx oo
00 10 20 30 40 50 60 70 80 90

Scoring

This is code-golf, so shortest code in bytes wins.

Octave, 34 32 bytes

@(a,b,n)hist(--a+randi(b-a,n,1))

Doesn't work on TIO, but works on Octave-online.net.

It creates a histogram (bar chart) looking like this:

I'd say that counts as "Any convenient format".

If non-zero bins must be shown, then this can be solved in 38 bytes:

@(a,b,n)hist(--a+randi(b-a,n,1),a+1:b)


This challenge is about recursion (Robbers' thread) Robbers thread

In this thread, your task is to find a non-recursive solution which produces the same integer series of a submission not marked as 'safe' in the Cops' thread.

Challenge synopsis

In many languages, recursive functions can significantly simplify a programming task. However, the syntax overhead for a proper recursion may limits its usability in code-golf.

The cops will create a program or function taking a single integer n, which will generate the first n entries of an integer series, using only recursion.1.

The robbers will try to find a shorter program or function in the same language, generating the same integer series, using no recursion2.

If the cops' submission is not cracked within ten days (240 hours), the cop will prove it was in fact possible to have a shorter non-recursive approach by revealing their own solution. They may then mark their submission as safe.

The winner of the cops challenge will be the shortest (according to code-golf) recursion-based submission marked safe.

The winner of the robbers challenge will be the robber who cracked the most solutions.

1: It only needs to be recursive in syntax; you don't need to worry about for example tail call optimization.

2: Again, non-recursive in syntax; so you can't post a recursive solution and claim its compiled to a loop thanks to tail call optimization.

Requirements

Each submission will take a single integer n (zero- or one-based). The submission will then output or return the first n entries of the same integer series as the cops' entry. The input and output method may differ between the recursive and non-recursive approach.

Your robbers' entry must be strictly shorter in byte-count than the recursive solution. It must work for at least the same n, or up to n=2^15-1, whichever is smaller.

Recursion

For the sake of this challenge, recursion is defined as creating the desired sequence using a function (or function-like construct) that calls itself (or calls a sequence of functions that ends up calling itself). The recursion depth should go to infinity as n goes to infinity. The non-recursive approach is anything that is not recursive.

Octave, by Sanchises 27 bytes

There are so many, many ways to do this in a loopy-way. For instance this one, if an explicit loop is needed:

for i=1:input('')disp(i)end

Try it online!

Or, if you want to create a vector (I haven't golfed this terribly well, since using a loop like this is kinda pointless):

x=0;for i=1:input(''),x(i)=i;end,x

Or 7 bytes if it's OK to not use a loop at all:

@(n)1:n


Solve 4x4 Mastermind in exactly 5 steps Background
Mastermind is a game of code-breaking for two players. One of the players is codemaker (Alice) and the other is codebreaker (Bob).
4x4 means that the player should guess the length-4 sequence made of four alphabets (say RGBY). The hidden sequence may have duplicate letters, so there are \$4^4 = 256\$ possibilities in total.
At the start of the game, Alice sets up a hidden code, which Bob should guess correctly within a set number of turns. At each turn, Bob presents a guess, and Alice tells Bob how many of the positions are correct, and how many of the letters are correct but at a wrong position. For example, if the hidden code is RRYG and Bob guessed BRGY:
          Code: R R Y G
         Guess: B R G Y
       Correct: R(2nd-2nd)
Wrong position: Y(3rd-4th), G(4th-3rd)

Then Alice tells Bob the two counts 1, 2. (Note that the first R in the code does not contribute to the counts because the second R in the guess was already consumed as Correct.) Bob repeats the guess with different sequences, until the guess is identical to the code (getting 4, 0) or he runs out of turns.
Challenge
The Dream World mastermind solver features four specific guesses so that the unique answer can be derived from their outcomes in all cases. The guesses are as follows:
1. R G G R
2. B B R R
3. Y Y G R
4. G B B Y

Given the outcomes of the four combinations above (four pairs of integers), output the unique hidden code.
You can assume the input is valid and the answer exists. You can choose to output any four distinct values (numbers/characters) in place of RGBY.
Standard code-golf rules apply. The shortest code in bytes wins.
NB: Fetching the results from the linked website is a standard loophole, and therefore forbidden.
Test cases
Each pair in the input represents (correct, misplaced). Note that the answer can be one of the four predefined guesses (generating a (4, 0) in the input).
(2, 0), (2, 0), (1, 0), (0, 0) => R R R R
(2, 1), (1, 0), (1, 2), (1, 1) => G G Y R
(0, 2), (0, 2), (0, 3), (1, 2) => G R Y B
(2, 0), (0, 0), (2, 0), (0, 2) => Y G G G
(1, 1), (4, 0), (1, 0), (1, 1) => B B R R

05AB1E, 38 33 32 bytes
-6 bytes thanks to Kevin Cruijssen!
For each possible output this generates the input and selects the matching one. Colors are encoded as B=0, G=1, R=2, Y=3.
3Ý4ãʒU•˜ÐÐÛ•4в4äεœεX-0¢}¬Dràα‚}Q

Try it online!
Commented:
3Ý4ã              # Generate all possible outputs
3Ý                # range [0 .. 3]
  4и              # to the 4th cartesian power

ʒU ... Q          # filter the possible outputs
                  #   where the following equals the input
                  #   and assign the current output to variable X

•˜ÐÐÛ•4в4ä        # encode the 4 guesses
•˜ÐÐÛ•            # compressed integer 2517300803
      4в          # convert to base 4:
                  #   [2,1,1,2,0,0,2,2,3,3,1,2,1,0,0,3]
        4ä        # split into 4 groups:
                  #   [2,1,1,2],[0,0,2,2],[3,3,1,2],[1,0,0,3]

εœεX-0¢}¬Dràα‚}   # compute the score for each guess
ε             }   # map over the guesses ...
 œ                #   take all permutations
                  #     the first will be the original guess
  ε    }          #   map over the permuations ...
   X-             #     subtract the current output
     0¢           #     count the 0's
        ¬         #   get the head without popping
                  #     this is number of correct positions (c)
         D        #   duplicate it       => c, c, [...]
          r       #   reverse the stack  => [...], c, c
           à      #   take the maximum
                  #     this is number of correct colors,
                  #     correct and misplaced (c+m)
                  #                      => c+m, c, c
            α     #   absolut difference => |c-(c+m)|, c = m, c
             ‚    #   pair up     => [c, m]


Branch Out - Monkey Edition The Monkey has swung home to find his tree all in pieces.

He likes order and scoops up all his 'tree-parts' and sets them out in 3 groups.

The Monkey's 3 nested lists:

STEP = [['S', '1', 'B', '3'], ['S', '3', 'B', '11'], ['S', '5', 'B', '12'], ['S', '4', 'B', '13'], ['S', '2', 'B', '14']]

TRANSITION = [['T', '2', 'B', '4'], ['T', '7', 'B', '4'], ['T', '3', 'S', '4'], ['T', '5', 'S', '5'], ['T', '1', 'S', '2'], ['T', '8', 'S', '2'], ['T', '6', 'S', '1'], ['T', '9', 'S', '2'], ['T', '4', 'S', '1'], ['T', '10', 'S', '1']]

BRANCH = [['B', '3', 'T', '1'], ['B', '3', 'T', '7'], ['B', '4', 'S', '3'], ['B', '11', 'T', '3'], ['B', '11', 'T', '5'], ['B', '12', 'T', '6'], ['B', '12', 'T', '8'], ['B', '13', 'T', '4'], ['B', '13', 'T', '9'], ['B', '14', 'T', '2'], ['B', '14', 'T', '10']]

Each element holds information as such:

# Example

STEP[0]  =  ['S', '1', 'B', '3']

Where:

'S' is the STEP type
'1' is the STEP number id
'B' is the linked BRANCH type
'3' is the linked BRANCH number id

Starting from a STEP the data is all linked, so using the linked reference you can find the next element and the next until another STEP is reached.

This is some parameters of the data:

STEPS are connected to single BRANCHES
BRANCHES are connected to one or more TRANSITIONS
TRANSITIONS can be connected to a single BRANCH or STEP

The BRANCH data can have a fork where a single BRANCH id has one or more options for TRANSITIONS.

Re-create this monkey's tree (nested list format is fine) in the shortest way possible (he is not a fan of long instructions):

           [S1]
            |
          B3|_________
            |         |
           [T1]     [T7]
            |         |
            |       B4|
            |         |
           [S2]     [S3]

And list all the routes on this tree:

Routes = [[S1, B3, T1, S2], [S1, B3, T7, B4, S3]]

UPDATE: This is Code-golf and from the data given you need to output the display of the tree ( This can be different from my example but requires the same elements to be displayed in any format) and as you cycle through the problem to output all the possible routes as a BONUS.

Notes:

This is a single-rooted tree
You may use a different format for input but please explicitly state the input format in your solution

Java (JDK), 570 bytes

t->{return "Routes = "+Arrays.deepToString(Arrays.stream(r(t.get(0).get(0),t,t.get(0).get(0)).split("\\[")).filter(d->d.endsWith("]")).map(d->d.replaceAll("]", "")).map(d->d.split("(?=[A-Z])")).collect(Collectors.toList()).toArray());};String r(String s, List<List<String>>t, String b){List<String>o = t.stream().filter(e->e.get(0).equals(s)).map(e->e.get(1)).collect(Collectors.toList());if(s.matches("^S(?!(?:1)$)\\d+"))return s;if(o.size()>1){String x="";for(String n:o){x+="["+b+r(n,t,b+n)+"]";}return x;}if(o.size()==1)return s+r(o.get(0),t,b+o.get(0));return "]";}

As you may notice by my code I´m still learning a lot every day.
My answer is neighter pretty nor short and I honestly even hope this works for different testcases even though I tested a couple.
But I hope that this question gets the attention it deserves and there will be more answers I can learn from.

INPUT

String[][] STEP = { { "S1", "B3" },  ... ,{ "B14", "T2" }, { "B14", "T10" } };
List<List<String>> tupels = Arrays.stream(STEP).map(Arrays::asList).collect(Collectors.toList());
z(tupels);

I converted your given Input into an 2D-Java-Array String[][] and converted that into a List<List<String>>.

CODE

The first method calls a recursive method to get all routes and formats the output.

t->{
return "Routes ="+Arrays.deepToString(
  Arrays.stream(r(t.get(0).get(0),t,t.get(0).get(0)).split("\\["))
 .filter(d->d.endsWith("]")).map(d->d.replaceAll("]", ""))
 .map(d->d.split("(?=[A-Z])")).collect(Collectors.toList()).toArray());
};

The second method is the recursive method which gathers all the possible routes

String r(String s, List<List<String>>t, String b){
  List<String>o =t.stream().filter(e->e.get(0).equals(s)).map(e->e.get(1))
  .collect(Collectors.toList());
  if(s.matches("^S(?!(?:1)$)\\d+"))
    return s;
  if(o.size()>1){
    String x="";
    for(String n:o){
      x+="["+b+r(n,t,b+n)+"]";
    }
    return x;
  }
  if(o.size()==1)
    return s+r(o.get(0),t,b+o.get(0));
  return "]";
}

Try it online!


Count how many characters are in the program's source Write a program that counts and prints the number of characters in it's own source code to standard output.

The number must be generated from counting the characters.

This Ruby solution would not be allowed:

puts 6

because it is not calculated. Spaces, tabs, new lines, etc should be counted.

The program must be smallest possible in any programming language.

Bash, 10

Pretty boring, but:

Prints the code size in bytes, and nothing else.
Filename may contain spaces.

Make sure that the file doesn't have a new line at the end! If it does, it will output 11.

wc -c<"$0"

If the file doesn't have spaces in its name, you can get 8 characters:

wc -c<$0


Convert from binary to unary in 7x7 Manufactoria In the game manufactoria, take in a binary number and output that number of red pieces.
The catch? The board-size is only 7x7:

Here's the manufactoria code for the problem:

http://pleasingfungus.com/Manufactoria/?ctm=Razors;Treat_the_input_as_a_binary_number_and_output_that_number_of_reds;b:r|brr:rrrr|brb:rrrrr|brbb:rrrrrrrrrrr|:|brrrr:rrrrrrrrrrrrrrrr|brbr:rrrrrrrrrr;7;3;0;

I have a solution, so it most definitely exists.

EDIT: Least "total parts" wins (as reported by manufactoria engine)

21 20 19 parts! Ha!

http://pleasingfungus.com/Manufactoria/?lvl=32&code=q12:9f0;c12:8f3;g9:8f1;q9:9f4;b10:8f3;p10:9f0;r10:10f1;y11:9f0;g12:5f3;c12:6f3;r9:6f3;c9:7f2;r10:6f0;p10:7f2;q11:7f1;i12:7f7;p13:7f6;r13:6f0;c13:8f0;&ctm=Razors;Treat_the_input_as_a_binary_number_and_output_that_number_of_reds;b:r|brr:rrrr|brb:rrrrr|brbb:rrrrrrrrrrr|:|brrrr:rrrrrrrrrrrrrrrr|brbr:rrrrrrrrrr;7;3;0;

Edit 2: Back to the original design, but with two parts shaved off by creative reuse of conveyors.  The 7 × 7 board really does start to feel confining — I've come up with several ways to shrink this further, if I only had one more row of vertical space...


Which were the latest 13 consecutive years with the most friday 13. in total? Shortest program wins, of course.

Wolfram Language 171 bytes
Any modern 13-year interval will have between 20 and 24 Friday the 13ths.
SortBy[{{#[[1,1]],#[[-1,1]]},Total[#[[2]]&/@#]}&/@Partition[Table[{y,Length@Cases[DateObject@{y,m,13}~Table~{m,12},x_/;DayName@x==Friday]},{y,1900,2019}],13,1],Last][[-1]]

* {{2007, 2019}, 24} *)

The above generates all the Friday the 13ths for each year between 1900 and 2019, partitions the results into intervals of 13 years, and finds the total for each such interval.  The interval of 2007-2019 has 24, the maximum number of Friday the 13ths.
If 2019 cannot be used, the correct answer will be the interval of 200-2018, which also contains 24 Friday the 13ths.


Build a simple room in ASCII-art A room can be made up of connected rectangles, for instance an L-shaped room. Such a room can be described by a list of dimensions describing the size of each rectangle.

Assume you have two input lists. The first contains the width of rectangles stacked vertically over each other. The second contains the height of the rectangles.

As an example, the input [4 6][3 2] will be a 4-by-3 rectangle on top of a 6-by-2 rectangle. The figure below shows this shape. Note that the walls are considered "thin", thus it's the spaces between the wall that's determined by the input.

[4 6][3 2]
 ____
|    |
|    |
|    |_
|      |
|______|

The challenge is: Take a list of dimensions as input, and output the shape of the room as ASCII-art. The format must be as in the sample figures:

All horizontal walls are shown using underscores
All vertical walls are shown using bars
There shall be no walls where the rectangles are connected
The left wall is straight
For more details, have a look at the test cases

Assumptions you can make:

All dimensions are in the range [1 ... 20]

All horizonal dimensions are even numbers

The number of rectangles will be in the range [1 ... 10]
Only valid input is given
Optional input format (you can decide the order of the input dimensions, please specify in the answer).

Test cases:

[2][1]
 __
|__|

---

[4][2]
 ____
|    |
|____|

---

[2 6 2 4][2 2 1 3]
 __
|  |
|  |___
|      |
|   ___|
|  |_
|    |
|    |
|____|

---

[2 14 6 8 4 18 2 10 4 2][1 2 3 1 2 1 1 1 2 1]
 __
|  |___________
|              |
|       _______|
|      |
|      |
|      |_
|     ___|
|    |
|    |_____________
|   _______________|
|  |______
|     ____|
|    |
|   _|
|__|


Generate the outline of an island from a seed The challenge is to draw the outline of an 'island', generated using a seed as input.

Input (seed): string of 6 characters (exactly) allowing only lowercase letters (i.e. abcdefghijklmnopqrstuvwxyz) - examples: 'island', 'aaaaaa', 'jhgcfj'
Each seed is to give a unique island (i.e. no two seeds will give the same output)
No output is to be a transformation of another seed's output. That's translation, reflection, rotation, scaling or any combination thereof.
Using the same seed should always give the same output
Output: 600px by 600px image

A valid island is drawn using a single line, which:

forms a closed loop
is 1px thick with no smoothing, blurring etc.
is continuous (i.e. after drawing a pixel the next pixel will be in one of the 8 adjoining spaces that isn't occupied)
does not cross itself at any point
does not leave the boundaries of the image
is black (#000), on a background of white (#FFF)
has no lines of reflective symmetry
must enclose white space

Source code has a limit of 500 bytes.

Aside from that, popularity decides; most votes wins.

BBC basic
Here's a very simple algorithm, which could be refined for more realism. If there are further changes in the rules I'm willing to change / delete.
take the 6 character string and add }@ to ensure asymmetry (this particular choice of characters gives islands that vaguely resemble Antarctica)
draw a line that connects 8 points at 45 degree intervals, with distance from the centre determined by the ASCII code.
  INPUT a$
  a$=a$+"}@"
  MOVE 364,300
  FOR i=1 TO 8
    r=4*ASC(MID$(a$,i))-192
    DRAW 300+r*COS(i*PI/4),300+r*SIN(i*PI/4)
  NEXT


N times program for the N-th number Given an array of positive integers A as the input, generate a program that, when repeated for k times, output the kth(1-index) value of the array.

For example, if the array is [1,11], the output should be a program that outputs 1, and when repeated twice, output 11. Code like print(end="1"); in Python 3 works: print(end="1"); prints 1 and print(end="1");print(end="1"); prints 11

Smallest sum of code lengths to solve all test cases win. Your meta code should solve 500 test cases in 60s, and each of your solution code should return in 10s. Meta code and solution code needn't be in the same language, but all solutions your meta-program generates should be in same language.

Pretest data and generator can be seen here. 7 days later will use the sum of submission time(e.g. 12:34 mean 1234) to be the random seed and generate another test case as the final test case.

The final seed is 7335 in GMT+8, so the final test data is here

Python 3, generates Stax

This uses a variety of strategies.  Most strategies only apply under certain conditions, but there's one fallback strategy that is always usable.  At the end, the smallest candidate program is selected.

from functools import reduce
from math import sqrt

symbols = " !#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\]^_abcdefghijklmnopqrstuvwxyz{|}"

def uncycle(arr):
    for size in range(1, len(arr)):
        if all(e == arr[i % size] for (i, e) in enumerate(arr)):
            return arr[:size]
    return arr

def constant(val):
    return "A" if val == 10 else str(val)

def shift(val):
    if not val: return ""
    return constant(abs(val)) + "+-"[val < 0]

def encode(a, offsetMode):
    result = "";
    if offsetMode:
        for i in range(len(a) - 1, 0, -1):
            a[i] -= a[i - 1]
    for i in range(len(a)):
        parts = []
        signBit = (a[i] < 0) * 2
        continuing = (offsetMode and i == len(a) - 1) * 1
        remain = abs(a[i])
        while remain > 22:
            parts.insert(0, remain % 46 * 2 + continuing);
            remain //= 46
            continuing = 1

        parts.insert(0, remain * 4 + signBit + continuing)
        result += "".join(symbols[p] for p in parts)

    return result

def cram(arr):
    flat = encode(arr, False)
    offset = encode(arr, True)
    return offset if len(offset) < len(flat) else flat;

def issquare(num):
    root = int(sqrt(num))
    return root * root == num

def isgeometric(arr):
    r = arr[0]
    return all(r ** (i + 1) == e for (i,e) in enumerate(arr))

def generateProgram(arr):
    candidates = []
    rotated = uncycle(arr)
    rotated = rotated[-1:] + rotated[:-1]

    deltas = [b - a for a,b in zip(arr, arr[1:])]

    # single constant strategy
    if len(arr) == 1:
        candidates.append(constant(arr[0]))

    # repeated constant
    elif len(set(arr)) == 1:
        num = arr[0]
        if num == 10: candidates.append("A")
        if num % 2 == 0: candidates.append(constant(num // 2) + "H")
        if issquare(num): candidates.append(str(int(sqrt(num))) + "J")
        candidates.append(constant(num - 1) +  "^")

    # repdigit
    if len(arr) == 2 and 10 < arr[1] == arr[0] * 11 < 100:
        candidates.append(str(arr[0]) + "p")

    # single digits
    if max(arr) < 10:
        candidates.append("".join(map(str, rotated)) + "E|X@")

    # max 10
    if max(arr) == 10 and rotated[0] != 1:
        candidates.append("".join(str(e - 1) for e in rotated) + "E|X@^")

    fns = [
        ("", lambda x: x),
        ("H", lambda x: 2 * x),
        ("^", lambda x: x + 1),
        ("J", lambda x: x * x),
        ("Hv", lambda x: 2 * x - 1),
        ("H^", lambda x: 2 * x + 1),
        ("^H", lambda x: 2 * x + 2),
        ("HJ", lambda x: 4 * x * x),
        ("JH", lambda x: 2 * x * x),
        (":T", lambda x: x * (x + 1) / 2),
        ("|F", lambda x: reduce(lambda a, b: a*b, range(1, x+1))),
        ("J^", lambda x: x * x + 1),
        ("^J", lambda x: x * x + 2 * x + 1),
    ]
    for (stax, fn) in fns:
        if all(fn(i + 1) == e for (i,e) in enumerate(arr)):
            candidates.append("|X" + stax)

    # fixed delta
    if len(set(deltas)) == 1:
        delta = deltas[0]
        start = arr[0] - delta
        if start == 0:
            candidates.append(shift(delta))
        if delta == 1:
            candidates.append("|X" + shift(start))
        elif delta == -1:
            candidates.append("|x" + shift(start))
        elif delta > 1:
            candidates.append("|X" + constant(delta) + "*" + shift(start))
        elif delta < -1:
            candidates.append("|x" + constant(-delta) + "*" + shift(start))

    # geometric series
    if isgeometric(arr):
        candidates.append(constant(arr[0]) + "*")

    # prefix
    if len(arr) == 2 and arr[1] // 10 == arr[0] < 10:
        candidates.append("." + str(arr[1]) + "|X(")

    # suffix
    if len(arr) == 2 and arr[0] % 10 == arr[1] < 10:
        candidates.append("." + "".join(map(str, arr)) + "|X)")

    # uncycled cram
    candidates.append('"' + cram(rotated) + '"!|X@')

    candidates.sort(key=len)
    return candidates[0]

while True:
    arr = eval(input())
    prog = generateProgram(arr)
    print(prog)

Try it online!

Update: Validation  It will be time consuming to execute each multiplicity of each program separately.  It's possible to run them all at the same time.  In order to do this, a small piece of code must be used.  It's responsible for a few things.

Do implicit output if any.  Normally, at the end of a stax program, the top of stack is printed if there has been no other output.  When running multiple programs in the same source file, this must be done explicitly.
Clear both stacks.
Reset registers.  For these programs only the x register is used.

This boilerplate should be applied after every individual program to be executed.

|d{P}{zP}?0XLd

For example, the input [5,2,7,3] produces the stax program 3527E|X@.  All four multiplicities can be tested at once.

3527E|X@
|d{P}{zP}?0XLd

3527E|X@3527E|X@
|d{P}{zP}?0XLd

3527E|X@3527E|X@3527E|X@
|d{P}{zP}?0XLd

3527E|X@3527E|X@3527E|X@3527E|X@
|d{P}{zP}?0XLd

Try it online!

In this way, it's possible to test all the multiplicities of all the program in the same run, assuming nothing breaks.  It would probably be the largest stax program ever executed if all 500 are done.


Calculate the lowest number where the sum of the sequence of numbers exceeds a given value Given you have an infinite sequence of numbers defined as follows:

1: 1 = 1
2: 1 + 2 = 3
3: 1 + 3 = 4
4: 1 + 2 + 4 = 7
5: 1 + 5 = 6
6: 1 + 2 + 3 + 6 = 12
7: 1 + 7 = 8
...

The sequence is the sum of the divisors of n, including 1 and n.

Given a positive integer x as input, calculate the lowest number n which will produce a result greater than x.

Test cases

f(100) = 48, ∑ = 124
f(25000) = 7200, ∑ = 25389
f(5000000) = 1164240, ∑ = 5088960

Expected Output

Your program should return both n and the sum of its divisors, like so:

$ ./challenge 100
48,124

Rules

This is code-golf so the shortest code in bytes, in each language wins.

Jelly, 18 12 11 10 bytes

1Æs>¥#ḢṄÆs

Try it online!

-1 byte thanks to Mr. Xcoder!

How it works

1Æs>¥#ḢṄÆs - Main link. Argument: n (integer)
1   ¥#     - Find the first n integers where...
 Æs        -   the divisor sum
   >       -   is greater than the input
       Ṅ   - Print...
      Ḣ    -   the first element
        Æs - then print the divisor sum


10 Clickbaits you can't resist Write a program/function/script that takes a natural number i from 1 to 10 as input and outputs the URL of the Question with the i th hottest question on the Code Golf Portal

The ordering should be like in https://codegolf.stackexchange.com/?tab=hot.
For example:
input 1
output https://codegolf.stackexchange.com/questions/127047/the-spain-license-plates-game
(at the point of this edit)

There are no strong restrictions to the output, as long as the url can be reasonably retrieved. Valid outputs include strings, console printing etc.

It's Code Golf, so shortest code in Bytes wins.

Notes

If your program automatically opens a browser with the webpage, it counts as valid output and is totally cool.

If your program does not retrieve the ranking from current information (i.e. hardcoding the links), it is not valid.

The contest ends with the end of June.

As questioned: The indexing must be 1 based, ie: the input 1 must return the the first site of the hottest questions.

Comment

I hope this question is not too clickbaity, as the stack exchange editor program was mocking me for the title. Originally I planned this challenge with Youtube trends, where it would haven been more fitting.

Python + requests, 128 bytes

from requests import*
lambda n:get('http://api.stackexchange.com/questions?sort=hot&site=codegolf').json()['items'][n-1]['link']


Relative vs Absolute If someone facing north at point A in this grid wanted directions to follow the green path (as they can only follow gridlines) to point B you might tell them:

Go North, North, West, East, East, South, East, East.

or equivalently

Go Forward, Forward, Left, Back, Forward, Right, Left, Forward.
(Where a command of Right, Left, or Back implicitly means turn in that direction, then go forward.)

Write a function with one argument that translates between these absolute and relative directions along the same path, not just to the same point. Assume the directed person always starts facing north.

If the argument is a string of the letters NSEW, return the equivalent relative directions.
e.g. f("NNWEESEE") returns the string FFLBFRLF.

If the argument is a string of the letters FBLR, return the equivalent absolute directions.
e.g. f("FFLBFRLF") returns the string NNWEESEE.

The empty string yields itself. Assume no other input cases.

If your language does not have functions or strings use whatever seems most appropriate.

The shortest code in bytes wins.

CJam, 57 53 49

{"NESW""FRBL"_3$&!!:Q$:R^^f#0\{{+0\}Q*_@-R=\}%);}

Previous version

{"NESW""FRBL"_3$0=#W>:Q{\}*:R;f#0\{{+0\}Q*_@-R=\}%);}

Example:

{"NESW""FRBL"_3$0=#W>:Q{\}*:R;f#0\{{+0\}Q*_@-R=\}%);}:T;
"NNWEESEE"T
N
"FFLBFRLF"T

Output:

FFLBFRLF
NNWEESEE

How it works

{
  "NESW""FRBL"             " Push the two strings. ";
  _3$0=#W>                 " Check if the first character is in FRBL. ";
  :Q                       " Assign the result to Q. ";
  {\}*                     " Swap the two strings if true. ";
  :R;                      " Assign the top string to R and discard it. ";
  f#                       " Find each character of the input in the string. ";
  0\                       " Push a 0 under the top of the stack. ";
  {                        " For each item (index of character): ";
    {                      " If Q: ";
      +0\                  " A B -> 0 (A+B) ";
    }Q*
    _@-                    " C D -> D (D-C) ";
    R=                     " E -> E-th character in R ";
    \                      " Swap the top two items. ";
  }%
  );                       " Discard the last item in the list. ";
}


Calculate the most digits of pi There are a lot of challenges on this site regarding pi, but none that challenge you to calculate as many digits of pi as possible.

As you all may know, pi in its decimal form goes on for infinity, so calculating it in its entirety is near to impossible. However, I challenge you to write a program in your language of choice that can calculate as many digits of pi as possible, and include an explanation with your code. The winner will be decided by popularity contest.

The only restriction is that your program cannot connect to the internet. The point is not to have your program search the internet for the most digits of pi.

So in summary, the goal is to write a program that computes as many digits of pi as possible (in decimal, so 3.14159....). Your program cannot simply connect to the internet and lookup digits, it needs to calculate it.

Note here that the goal here is to calculate as many digits as possible, but that is not the winning criteria. The winner will be based on popularity (number of upvotes). Remember, we're here to learn just as much as to have fun.

Winner will be decided on July 16 at 10 AM eastern time.

And please, don't be this guy. Let's have fun.


Tips for Golfing in Vyxal Vyxal is a golfing language that has 500+ different commands (achieved through overloads), and is a known beater of Jelly, 05AB1E and most golfing languages.
Henceforth, it seems like a good idea to share some of the tips and tricks of the industry used to get terse programs in Vyxal.
One tip per answer, and no stupid tips like "oh remove comments and whitespace".

Brackets/Structures autocomplete
Totally not stolen from Tips for golfing in keg because Vyxal totally isn't supposed to be keg but 69 times better
If you have a structure (e.g. if/for/while/function/lambda) at the end of your program, and EOF follows, you can leave the closing bracket/semicolon off. Note that this only applies if you are submitting a full program.
For example:
9(0,)

Can be shortened to:
9(0,

And:
{:1=[1,]}

Can be shortened to:
{:1=[1,


Calculate n Kaprekar Numbers A Kaprekar number is an n-digit number k that, when the first n or n-1 digits of k^2 are added to the second n the digits of N^2, the result is N.

Examples:

9^2 = 81.  8+1 = 9.
45^2 = 2025.  20+25 = 45.
297^2 = 88,209. 88+209 = 297

The Kaprekar sequence begins at 1.

Write a program that calculates and outputs the first n Kaprekar numbers, with n being in the range, but not limited to the range, of 1 to 100.  Each Kaprekar number must be separated with whitespace and nothing else.

More Kaprekar numbers can be found here to check your program against, but this resource MAY NOT be used in any way to help with the calculation - in other words, no hard-coding, reading from this source, or using it in any other exploitive way - all the numbers must be generated by your program.

Shortest code wins.

Perl - 63 bytes

#!perl -l
map{1while$l=length++$_,$_**2=~/.{$l}$/,$`+$&^$_;print}($_)x<>

Counting the shebang as one byte. Input is taken from stdin.

This has an acceptable runtime for n ≤ 50, after that it gets a bit slow.

Sample usage:

$ echo 20 | perl kaprekar.pl
1
9
45
55
99
297
703
999
2223
2728
4950
5050
7272
7777
9999
17344
22222
77778
82656
95121


Tips for restricted source in zsh Adapted from tips for restricted-source in Python
Just like code-golf, restricted-source pushes one to exploit quirks and hidden features of the zsh language. While we already have a place to collect all these tips for code-golf, those for restricted-source remain transmitted by word of mouth or hidden deep within the manual pages.
So, what are some tips for solving restricted-source challenges in zsh?
Please only include 1 tip per answer. Please downvote answers with multiple tips in them.

What makes a good tip here?
There are a couple of criteria I think a good tip should have:

It should be (somewhat) non obvious.
Similar to the code-golf tips, it should be something that someone who has golfed in zsh (or bash) a bit and read the tips page would not immediately think of. For example, "replace a + b with a+b to avoid using spaces" is obvious to any golfer since it is already a way to make your code shorter and thus not a good tip.

It should not be too specific.
Since there are many different types of source restrictions, answers here should be at least somewhat applicable to multiple source restrictions, or one common source restriction.  For example tips of the form "How to X without using character(s) Y" are generally useful since banned characters is a common source restriction.  The thing your tip helps to do should also be somewhat general.  For example tips of the form "How to create numbers with X restriction" are useful since many programs utilize numbers regardless of the challenge.  Tips of the form "How to implement Shor's algorithm with X restriction" are basically just answers to a challenge you just invented and not very helpful to people solving other challenges.

Globbing
Globs are patterns used to match files and other strings. If you can't use a particular character but you need to access a command with that character in its name, you can often approximate it with a glob, like /*/ls
The full description of glob syntax is under Filename Generation in zshexpn(1), but here is a summary:

? matches any single character
* matches zero or more characters
<1-10> matches any number between 1 and 10

<-> matches any number

[a-d] matches any character in the set abcd
[:name:] matches any character in the named set (full details in the man-page)
[^a] or [!a] matches any character except a

[^] or [!] matches any single character

(a|b) matches a or b
With the option --nocaseglob, globbing is case-insensitive. This allows you to do /*/LS instead of ls
With the option --extendedglob, you can use the additional syntax:

^pattern matches anything except pattern
a~b matches pattern a but not b
a~^b matches both patterns a and b
a# matches zero or more instances of a
a## matches one or more instances of a


Tips for golfing in PowerShell What general tips do you have for golfing in Windows PowerShell? I'm looking for ideas that can be applied to code golf problems in general that are at least somewhat specific to PowerShell (e.g. "remove comments" is not an answer). Please post one tip per answer.

—taken nearly verbatim from marcog's question.

Powers of 10 literals with scientific notation:

4e6 = 4000000

Powers of 2 literals:

4KB = 4096
4MB = 4194304
4GB = 4294967296

# TB and PB suffixes also exist, but less useful for golf.

Could come in handy.


You're on a 8 day streak! Duolingo, the language learning app, has a lot of things going for it, but there is one major issue that drives me crazy. It tells me how many days in a row I've used the app with a message like You're on a 7 day streak! Setting aside hyphenation and whether the number should be spelled out, this works fine for most numbers, but is indisputably wrong when it says You're on a 8 day streak! I'm not using it to learn English but this is still unfortunate behavior for a language app.

You're going to help out the Duolingo team by writing a complete program or function that figures out whether a given number should be preceded by a or an. A number is preceded by a if its pronunciation in spoken English begins with a consonant or semivowel sound, and preceded by an if its pronunciation begins with a vowel sound. Thus the only numbers preceded by an are those whose pronunciation begins with eight, eleven, eighteen, or eighty.

Presumably the Duolingo dev team left this bug in because they ran out of space for more source code in the app, so you need to make this code as short as possible in the hopes they can squeeze it in.

Your code must take an integer from 0 to 2,147,483,647 and output a or an. A trailing newline is optional. For the purposes of this challenge, 1863 is read as one thousand eight hundred and sixty-three, not eighteen hundred and sixty-three.

Test cases:

0 → a
8 → an
11 → an
18 → an
84 → an
110 → a
843 → an
1111 → a
1863 → a
8192 → an
11000 → an
18000 → an
110000 → a
180000 → a
1141592 → a
1897932 → a
11234567 → an
18675309 → an

Python 2, 60 bytes
lambda n:'a'+'n'[:`n`[0]=='8'or`n`[:2]in len(`n`)%3/2*'118']

An anonymous function. Adds an n if either:

The first digit is 8
The first two digits are 11 or 18, and the length is 2 modulo 3.


Like a quine, but not Very simple, write a program that at first glance appears to be a quine, but is not. Upon running, the program actually prints the source to a real quine, obviously distinct from the original program in some way, preferably creative, but since this is a popularity contest, the answer with the most upvotes wins.

Standard Loopholes which are no longer funny are forbidden.

CJam

{"_~"}_~

Well, whether this looks like a real quine to you depends on whether you're used to CJam or GolfScript, but anyway, it looks like and prints the standard quine:

{"_~"}_~

Wait, isn't that the same thing?

   Nope, there's a space at the end of the first code. I believe the same thing would work in almost any language with almost any quine.

Test it here.


Be there, for the square Sometimes when you're lying in bed and reading a message, your phone screen will pop into landscape mode right in the middle of a sentence. Only being able to read left to right, you find yourself incapacitated, unable to process the text in front of you.

To ensure that this won't happen again, you decide to make every message readable from any angle, whether your phone screen is rotated or mirrored. To make this happen, each message is printed as a square, with each side of the square containing the message, either in the original order or in reverse.

For backwards compatibility, the top side of the square should be the original message.
To make each message square as compact as possible, the first and last character of the message should be a part of two sides of the square. This means that the top side reads normally, the bottom side is in reverse, the left side reads top-bottom, and the right side reads bottom-top.

Input

A single string, with 2 or more characters. You should not assume that the string only contains alphanumerical characters or similar.

Output

The Squarification™ of the string. It is permissible to leave some whitespace at the end of each line, and a single newline at the end of the output.

Examples

Input: 'ab'
ab
ba

Input: 'abc'

abc
b b
cba

Input: 'Hello, world!'
Hello, world!
e           d
l           l
l           r
o           o
,           w

w           ,
o           o
r           l
l           l
d           e
!dlrow ,olleH

This challenge looks like A cube of text, but I'm hoping that it's different enough that there will be some clever answers.

As this is code-golf, get ready to trim some bytes!

Charcoal, 4 bytes

Ｓ‖Ｏ^

Try it online! Link is to verbose version of code. Explanation:

Ｓ       Input the string and implicitly print it
 ‖      Reflect...
  Ｏ     ... overlapping the first and last character...
   ^    ... in the ↙↘ directions (^ is shorthand for ↙↘).


Tips for golfing in Nim What general tips do you have for golfing in Nim? I'm looking for ideas which can be applied to code-golf problems and which are also at least somewhat specific to Nim (e.g. "remove comments" is not an answer).

Please post one tip per answer.

Use the future module

The future module contains two main byte-saving features: lambdas and list comprehensions. Lambdas are extremely useful.

For example, this:

proc f(s:any):any=s&", world!"

can be shortened to this:

import future
s=>s&", world!"

which saves a byte. Note, however, that lambdas can't be used outside of a parameter list -- so to test your code, you'll have to do something like this:

import future
proc test(f: string -> string) = echo f "Hello"
test(s=>s&", world!")

As well, list comprehensions can be used with the future module. For example, this code prints a seq (@[...]) of all squares less than 100 divisible by 4:

import future
echo lc[x*x|(x<-1..9,x*x mod 4==0),int]


Domino Effect Problem Last week we had a programming contest in my university and I am very curious about one of the problems , one which only one team (but from another city) was able to solve. Maybe its not that hard, but I cant find any solutions that will take less than a second of execution time. The problem is the following:

Problem

You have N domino tiles separated by different amounts (integer values that are given to you) and you know the height H of these tiles (all have the same height). They are all placed standing up so that if you push one it falls in the direction of the next one. This way, if tile I is close enough (H or less) to tile I+1, the first one will push the second one when it is pushed down, producing the domino effect. Suppose that not all the distances that separate the tiles are smaller than H, what's the minimum amount of moves you need to make in order to have all the distances be at most H? You can't move the first nor the last tile. Print a falsey value if it is not possible.

Note: You are only allowed to move integer amounts and only to spots on the line defined by tile i-1 and tile i+1. This means you cant grab one and place it wherever you want.

Here are the input sizes: (3 ≤ N ≤ 1000) (1 ≤ H ≤ 50)  and the distances (1 ≤ Di ≤ 100 for i = 1, 2, ..., N-1). Someone uploaded it to SPOJ recently

  Input:

  N H

  d1 d2 d3 d4 ... d(n-1)

  Output:

  Minimum amount of moves.

Sample

  Input1

  8 3

  2 4 4 1 4 3 2

  Output1

  3

Sample2

  Input2

  10 2

  1 2 2 2 2 2 2 2 3

  Output2

  8

Sample3

  Input3

  5 2

  2 2 2 2

  Output3

  0

Sample4

  Input4

  5 3

  1 6 2 4

  Output4

  -1 (NOT POSSIBLE)

I have only found a good solution for two cases (Pseudo-Code):

D=sum_of_all_distances
MaxPossible=(N-1)*H

if D==MaxPossible and there is no di such that di>H
    Answer=0

else if D>MaxPossible
    Answer=-1

Python

N, H = map(int, raw_input().split())
D = map(int, raw_input().split())

# map from (number of dominoes, distance to last domino) to
# the number of moves needed to adjust the first number of dominoes
# exactly that far.
M = {}
M[1,0] = 0

for i in xrange(2, N+1):      # i = number of dominos to try
  for d in xrange(H*(i-1)+1):
    M[i,d] = 1e9
  for d in xrange(H*(i-1)+1): # position of last domino
    for e in xrange(1, H+1):  # distance from last domino to previous one
      if d-e > H*(i-2): continue
      if d-e < 0: continue
      if sum(D[:i-1]) == d:
        # don't move last domino, arrange rest
        M[i,d] = min(M[i,d], M[i-1,d-e])
      else:
        # arrange rest, move last domino to right location
        M[i,d] = min(M[i,d], 1 + M[i-1,d-e])

print M.get((N,sum(D)), -1)

Standard dynamic programming.  Runs pretty much instantaneously on the example inputs.  How big a problem do we have to solve in under a second?


Sequence of integer square roots Let's define a sequence of integer square roots. First, a(1) = 1. Then, a(n) is the smallest positive integer not seen before such that

sqrt(a(n) + sqrt(a(n-1) + sqrt(... + sqrt(a(1)))))

is an integer. Some  examples:

a(2) is 3 because it's the smallest integer such that sqrt(a(2) + sqrt(a(1))) = sqrt(a(2) + 1) is integer, and 3 hasn't occured in the sequence before.

a(3) is 2 because it's the smallest integer such that sqrt(a(3) + sqrt(a(2) + sqrt(a(1)))) = sqrt(a(3) + 2) is integer, and 2 hasn't occured in the  sequence before.

a(4) is 7 because sqrt(a(4) + 2) is integer. We couldn't have a(4) = 2 because 2 already occured in our sequence.

Write a program or function that given a parameter n returns a sequence of numbers a(1) to a(n).

The sequence starts 1,3,2,7,6,13,5, ....

Source of this sequence is from this Math.SE question.

A plot of the first 1000 elements in the sequence:

Python 2, 80 bytes

s=[]
exec'x=q=1\nwhile(x in s)+q%1:x+=1;q=(v+x)**.5\nv=q;s+=x,;'*input()
print s

Try it online!


Fill in the Blanks, Please! (No, not this nor any of these)

Given a string and a list of strings, fill in the all blanks in the input string with corresponding strings.

Input/Output

The input string contains only alphabetic characters, spaces, and underscores. It is nonempty and does not start with an underscore. In other words, the input string matches the regex ^[a-z A-Z]([a-z A-Z_]*[a-z A-Z])?$

Every string in the input list is nonempty and contains only alphanumeric characters and spaces. In other words, they match the regex ^[a-z A-Z]+$.

A blank is a contiguous sequence of underscores (_) which is neither preceded nor proceeded by an underscore.

The input string contains n blanks for some positive integer n, and the list of strings contains exactly n strings.

The output is obtained by replacing each k-th blank in the input string by the k-th string in the input list of strings.

Example

Given an input string "I like _____ because _______ _____ing" and a list of strings ["ice cream", "it is", "satisfy"], we can find the output as follows:

The first blank comes directly after "like ". We fill that in with "ice cream" to get "I like ice cream because ______ _____ing".
The second blank comes directly after "because ". We fill that in with "it is" to get "I like ice cream because it is _____ing".
The third blank comes directly after "is ". We fill that in with "satisfy" to get "I like ice cream because it is satisfying".

We output the final string "I like ice cream because it is satisfying".

Test Cases

input string, input list => output
"Things _____ for those who ____ of how things work out _ Wooden",["work out best","make the best","John"] => "Things work out best for those who make the best of how things work out John Wooden"
"I like _____ because _______ _____ing",["ice cream","it is","satisfy"] => "I like ice cream because it is satisfying"
"If you are ___ willing to risk _____ you will ha_o settle for the ordi_____Jim ______n",["not","the usual","ve t","nary ","Roh"] => "If you are not willing to risk the usual you will have to settle for the ordinary Jim Rohn"
"S____ is walking from ____ to ____ with n_oss of ___ W_____ Churchill",["uccess","failure","failure","o l","enthusiasm","inston"] => "Success is walking from failure to failure with no loss of enthusiasm Winston Churchill"
"If_everyone_is_thinking ____ ____ somebody_isnt_thinking G____e P____n",[" "," "," ","alike","then"," "," ","eorg","atto"] => "If everyone is thinking alike then somebody isnt thinking George Patton"
"Pe_________e __say ____motivation does__ last Well___her doe_ bathing____thats why we rec____nd it daily _ __________lar",["opl","often ","that ","nt"," neit","s","  ","omme","Zig","Zig"] => "People often say that motivation doesnt last Well neither does bathing  thats why we recommend it daily Zig Ziglar"

Convex, 5 bytes

'_%.\

Try it online!

Convex is a CJam-based language, and this answer is almost the same as my CJam answer, except for l~ which is unneeded here, since Convex does automatic argument evaluation at the start of the program.

Explanation:

'_%.\ e# Full program only
'_    e# Push '_'
  %   e# Split and remove empty chunks
   .\ e# Vectorize by Swap


Shortest program whose concatenated program+output is a permutation of the 95 printable ASCII characters Write a program that's as short as possible (as measured by byte-count), takes no input, contains no comments, and outputs a character string/sequence, such that concatenated program+output is exactly 95 characters long and contains every printable ASCII character exactly once, i.e. program+output is a permutation of the 95 characters with ASCII codes 32-126:

 !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~

In the event of a tie, the winner is the entry whose (95-character) concatenated program+output is closest to the above string, as measured by the Levenshtein edit-distance (i.e. the number of single-character deletions, insertions, or substitutions required to put it into ASCII order).

GolfScript, 14 characters
{`),32>46-^}.~

Output:
 !"#$%&'(*+/015789:;<=?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]_abcdefghijklmnopqrstuvwxyz|


Harmonious "Convergence" The Alternating Harmonic Series is a well known convergent series.

"Clearly", it is obvious that it converges to the natural log of 2. Or does it?

Since the series is not absolutely convergent, by simply rearranging the terms, I can make it approach anything I want. Suppose I want the series to converge to e. All I'd have to do is this:

If you didn't catch the pattern, there isn't an obvious one. Here's how it works:

Consider the terms of the alternating harmonic series in terms of positive and negative terms.
Add together just enough positive terms to exceed our target (e). (aka sum > target)
Subtract the next negative term.
Go back to 2.

Note that at step 2, if our sum == target, you should add another positive term.

From this we can define a sequence associated with each number as follows:

Follow the algorithm above
For each positive term, output 1.
For each negative term, output 0.

Let's call this sequence the "Harmonious Bit Pattern" of a number. For example, the HBP of e begins as:

1, 1, 1, 1, <32 times>, 0, 1, 1, <54 times>, 0, 1, 1, ...

Your challenge:

You will be given:

a rational input target in the range [-10, 10] (note: even reaching 10 via the harmonic series takes many millions of terms). This may be a decimal (aka 1.1) or you may take a rational directly (aka 12/100)
a positive int n input, specifying the number of terms of the Harmonious Bit Pattern to output.

You are expected to output the exact Harmonious Bit Pattern of the target to the specified number of terms. You may output space separated values, comma separated, no separation, etc; just as long as the pattern of 0s and 1s is clearly visible and is read left to right with consistent separation.

Test Cases

>>> 0, 1
1
>>> 0, 2
10
>>> 0, 7
1000010
>>> 1, 10
1101011011
>>> 1.01, 3
110
>>> 1.01, 24
110101101101101101101101
>>> 2.71, 32
11111111111111111111111111111111
>>> 2.71, 144
111111111111111111111111111111110111111111111111111111111111111111111111111111111111111101111111111111111111111111111111111111111111111111111111
>>> -9.8, 100
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

Note that since -9.8 is so large, the first 1 that would be output is somewhere around the 149496620th term (that was computed via floats, so the value might not be exact).

Perl, 69 bytes

use bigrat;$s+=.5/($s>$ARGV[$_=0]?-++$n:++$p-++$_/2),print for 1..pop

Takes inputs as command line arguments.

Explanation: bigrat enables fractions everywhere for accurate calculations. $s is the current sum of terms, $ARGV[0] is the target value, pop (same as $ARGV[1]) represents the number of terms, $p and $n represent the positive and negative term counts. $_ is either 1 or 0 depending on whether a positive or negative term was added.


Infinitely Print Zeno's Dichotomy Paradox (1/(2^n)) Wikipedia: Zeno's Dichotomy Paradox

An infinite number of mathematicians walk into a bar. The first one orders a beer. The second one orders half a beer. The third one orders a fourth of a beer. The bartender stops them, pours two beers and says, "You're all a bunch of idiots."
Reddit

Print the following series for as long as the program runs, with the denominator of each item being multiplied by two each time:
1 + 1/2 + 1/4 + 1/8 + 1/16 + 1/32 + ...
As n approaches infinity, the sum of this sequence approaches 2.
Rules
No, you may not print 2.
You may not print 1/1 as the first item.
You may remove spaces 1+1/2+... or add spaces 1 + 1 / 2 + ... as you need.
You may use newlines instead of spaces as a delimiter due to popular demand.
You may append a . plus a constant number of 0s to the denominator if need be.
"Infinitely" means no unnecessary delays, and for as long as possible limited by the current (variable) system's specs, but not limited by your current language.
Standard loopholes apply.
This is code-golf, so shortest answer in bytes wins.

05AB1E, 10 9 bytes

Saved 1 byte thanks to Erik the Outgolfer

[No…+1/J?

Try it online!

Explanation

[           # loop over N infinitely [0 ...]
 No         # calculate 2^N
   …+1/J    # join with the string "+1/"
        ?   # print without newline


Permutation Square Root In math, a permutation σ of order n is a bijective function from the integers 1...n to itself. This list:
2 1 4 3

represents the permutation σ such that σ(1) = 2, σ(2) = 1, σ(3) = 4, and σ(4) = 3.
A square root of a permutation σ is a permutation that, when applied to itself, gives σ. For example, 2 1 4 3 has the square root τ =3 4 2 1.
k           1 2 3 4
τ(k)        3 4 2 1
τ(τ(k))     2 1 4 3

because τ(τ(k)) = σ(k) for all 1≤k≤n.
Input
A list of n>0 integers, all between 1 and n inclusive, representing a permutation. The permutation will always have a square root.
You may use a list of 0...n-1 instead as long as your input and output are consistent.
Output
The permutation's square root, also as an array.
Restrictions
Your algorithm must run in polynomial time in n. That means you can't just loop through all n! permutations of order n.
Any builtins are permitted.
Test cases:
Note that many inputs have multiple possible outputs.
2 1 4 3
3 4 2 1

1
1

3 1 2
2 3 1

8 3 9 1 5 4 10 13 2 12 6 11 7
12 9 2 10 5 7 4 11 3 1 13 8 6

13 7 12 8 10 2 3 11 1 4 5 6 9
9 8 5 2 12 4 11 7 13 6 3 10 1


Saddle points in a matrix A matrix can be thought of as the altitudes of a surface in 3D space.
Consider the 8 neighbours (orthogonal and diagonal) of a cell as a cyclic sequence in clockwise (or anticlockwise) order. Some neighbours may be higher than the original cell, some lower, and some levelled at the same height as the original cell. We split the cycle of neighbours into segments according to that property and discard the levelled segments. If we end up with exactly 4 segments alternating between higher and lower, we call the original cell an order-2 saddle point. Boundary cells (edges and corners) are never considered to be saddle points. Your task is to output the number of order-2 saddle points in a given matrix.

For instance, in the matrix

3 3 1
4 2 3
2 1 2

the central cell's neighbours in clockwise order are

3 3 1 3 2 1 2 4
+ + - +   -   +  // + for higher, - for lower
a a b c   d   a  // segments

Note that the list is cyclic, so we consider the final 4 part of the initial segment a. The signs of segments abcd are alternating - this is indeed a saddle point.

Another example:

1 7 6
5 5 5
2 5 6

Neighbours:

1 7 6 5 6 5 2 5
- + +   +   -
a b b   c   d

We have 4 +/- segments but their signs are not alternating, so this is not a saddle point. Note how segment b is separated from segment c by a levelled segment. We discard the levelled segment, but b and c remain separated. Same goes for d and a.

Third example:

3 9 1
8 7 0
3 7 8

Neighbours:

3 9 1 0 8 7 3 8
- + - - +   - +
a b c c d   e f

The signs are alternating but the number of +/- segments is 6. This is known as a monkey saddle or an order-3 saddle point. For the purposes of this challenge we should not count it.

Write a function or a complete program. Input is an integer matrix as typically represented in your language. It will consist of integers between 0 and 9 inclusive. Output is a single integer. Standard loopholes are forbidden. The shortest solution per language wins, as code-golf (obviously?) indicates.

in                                   out

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

[[1,7,6],[5,5,5],[2,5,6]]             0

[[3,9,1],[8,7,0],[3,7,8]]             0

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

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

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

JavaScript (ES6), 179 bytes

a=>a.map((r,y)=>r.map((v,x)=>t+=x*y/r[x+1]&&a[y+1]?[...(S='12221000')+S].map((n,i)=>p-(p=d=Math.sign(v-a[y+~-n][x+~-S[i+2&7]]))&&d?s&s!=-(s=d)?T=a:T++:0,T=s=p=0)|T>>1==4:0),t=0)|t

Try it online!

How?

We iterate on each cell \$v_{y,x}\$ of each row \$r_y\$ of the input matrix.

We first make sure that we're not located over an edge of the matrix with:

x * y / r[x + 1] && a[y + 1]

(neither \$x\$ or \$y\$ is \$0\$ and both \$v_{y,x+1}\$ and \$r_{y+1}\$ are defined)

We iterate twice on each neighbor cell and keep track of the number of valid segments in \$T\$. By doing this, each segment is guaranteed to be counted twice, except the first one which may be counted either twice or three times, depending on its starting point in relation to the starting point of the cycle. Either way, we have \$\lfloor{T/2}\rfloor=4\$ for order-2 saddle points, in which case we increment the counter \$t\$.

Example:

If the first segment is aligned with the starting point:

neighbor cells: AAAABCCD --> AAAABCCDAAAABCCD
                             ^   ^^ ^^   ^^ ^  --> T = 8

If it is not aligned:

neighbor cells: AABCCDAA --> AABCCDAAAABCCDAA
                             ^ ^^ ^^   ^^ ^^   --> T = 9

We iterate on neighbor cells by starting with the rightmost one and moving clockwise with:

[...(S = '12221000') + S].map((n, i) => a[x + ~-n][y + ~-S[i + 2 & 7]])

Try it online!

We store the sign of the difference between the current cell and its current neighbor in \$d\$. We keep track of the previous value of \$d\$ in \$p\$ and the previous sign (for non-zero values) in \$s\$.

The logic to update \$p\$, \$s\$ and \$T\$ reads as follows:

p - (p = d) && d ? s & s != -(s = d) ? T = a : T++ : 0

In plain English:

Ignore identical consecutive values.
Ignore segments with \$d=0\$.
Increment \$T\$ on valid sign transitions.
Whenever an invalid sign transition is detected, do T = a to force all upcoming operations on \$T\$ to either NaN or \$0\$, thus invalidating the final test.


"Snail" number sequence lookup You are given integers N and M, 1 <= N,M <= 10^6 and indexes i and j. Your job is to find the integer at position [i][j]. The sequence looks like this (for N=M=5, i=1, j=3 the result is 23):

 1  2  3  4  5
16 17 18 19  6
15 24 25 20  7
14 23 22 21  8
13 12 11 10  9

Shortest code wins. Good luck!

Mathematica, 63 55 bytes

f=If[#5<1,#+#4,f[#+#2,#3-1,#2,#5-1,#2-1-#4]]&;g=1~f~##&

This defines a function g which can be called like

g[5, 5, 1, 3]

I'm using a recursive approach. It uses up to 2(N+M) iterations, depending on how far down the spiral the result is found. It does handle all inputs (up to g[10^6,10^6,5^5-1,5^5], which requires the most iterations) within a few seconds, but for larger inputs, you'll need to increase the default iteration limit like

$IterationLimit = 10000000;

Basically, if k is the starting number of the spiral, I'm checking if the j index is 0 in which case I can just return k + i. Otherwise, I throw away the top row, rotate the spiral by 90 degrees (anti-clockwise), increment k accordingly, and look at the remaining spiral instead. We can move to the next spiral with the following mapping of parameters:

kn+1 = kn + mn
Mn+1 = Nn - 1
Nn+1 = Mn
in+1 = jn - 1
jn+1 = nm - in - 1

This assumes that M is the width and N is the height.


I'm thinking of a number (Robber's thread) Cop's thread here

In this cops-and-robbers challenge cops will think of a positive integer.  They will then write a program or function that outputs one value when provided the number as input and another value for all other positive integer inputs.  Cops will then reveal the program in an answer keeping the number a secret.  Robbers can crack an answer by finding the number.

Your job as robbers is to find that number.  Once found you can make an answer here detailing the number and how you found it.  You should link the original answer being cracked in your answer.

Your score will be the number of cracks with more being better.

Java, by okx

Note: the original challenge to which this post answers has been deleted, it's however still accessible with the link to anyone having the privilege to see deleted answers. The explanations below include what the challenge was about.

Number: 18

The code is effectively looking for primes with the form 112n-2.

By this Wikipedia list, we know that the 20th largest known prime number has 2,900,832 digits. No prime with the form 112n-2 are in that list, so that digit number will be our limit.

All numbers of the form 112n-2 that have at most that many digits have this constraint: n < 22. Factordb tells us that 11222-2 has 4,367,918 digits. This is proof enough.

The code by okx limits us to n above 6.

So, let's do the list:

112n-2 is factorizable for n = 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 19, 20 and 21 (factors proofs are on factordb.com and wolfram alpha; factordb has some proofs that wolfram alpha hasn't and vice-versa).

The only value n for which we can't prove the factorization is 18 (factordb, WolframAlpha).

So (a) if there is a prime number of the form 112n-2 with n > 6, then (b) 6 < n < 22, and (c) I proved each number with such n is composite except for 18, so (d) the prime we're looking for has n = 18.

Note that I don't exclude that 11218-2 is composite. I haven't proved that that number is a prime: I only proved that if the OP thought about that number, it can only be 18. If that number is indeed a prime, congrats to okx for finding it :-)

However

There are no proof that 11218-2 is the only number, though. It's the only number in the range of numbers for which we can currently prove the primality.

So I don't exclude the fact that one day someone might prove that 11251-2 or 112124-2 is prime.

I therefore believe that the original entry by okx is invalid because there are no such proof that for n between 19 and the (231-1)231-1 (the theoretical limit of Java's BigInteger), there are no other primes.


Hot moo shuffle: milk an array Background
Milking the deck is the name given to the following card shuffling method:

'Pinch' the deck to remove the top and bottom cards simultaneously. (With lots of imagination, this action resembles milking a cow.) This pair of cards forms the base of a new pile.
Repeat, adding each pair of cards to the top of the new pile, until the whole deck has been used.

Example
Suppose we start with a deck of six cards, [1, 2, 3, 4, 5, 6] (lower-indexed elements are nearer to the top). Let's milk the deck:

old = [1, 2, 3, 4, 5, 6], new = []
Remove [1, 6]: old = [2, 3, 4, 5], new = [1, 6]
Remove [2, 5]: old = [3, 4], new = [2, 5, 1, 6]
Remove [3, 4]: old = [], new = [3, 4, 2, 5, 1, 6]

After milking, the deck is therefore ordered [3, 4, 2, 5, 1, 6].
Challenge
Your task in this code-golf challenge is to implement the milking operation on a given array and output/return the result. The input array will contain only positive integers, not necessarily distinct. If the input array contains an odd number of elements, then the last milking step transfers only one element (the last one remaining) from the input to the output array.
Test cases
Input -> Output
[1, 2, 3, 4, 5, 6] -> [3, 4, 2, 5, 1, 6]
[1, 2, 3, 4, 5, 6, 7] -> [4, 3, 5, 2, 6, 1, 7]
[9, 7, 5, 3, 1, 2, 4, 6, 8, 10] -> [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
[1, 1, 2, 1, 2] -> [2, 1, 1, 1, 2]
[] -> []

R, 53 50 48 bytes

f=function(x,y=rev(x))if(c(y,F))c(f(y[-1]),y[1])

Try it online!
Repeatedly takes the bottom card & flips the deck.


mastermind horse battery staple Objective

Given a list of three-word passphrases, crack them all. Each time you guess, you will be given a clue in the style of Mastermind, depicting how many characters match the password, and how many are in their correct position. The objective is to minimize the total number of guesses over all test cases.

Passphrases

From my system's default word list, I randomly chose 10,000 distinct words to make the dictionary for this challenge. All words consist of a-z only. This dictionary can be found here (raw).

From this dictionary, I generated 1000 passphrases consisting of three random space-separated words each (apple jacks fever, for example). Individual words can be reused within each passphrase (hungry hungry hippos). You can find the list of passphrases here (raw), with one per line.

Your program can use/analyze the dictionary file however you want. You cannot analyze the passphrases to optimize for this specific list. Your algorithm should still work given a different list of phrases

Guessing

To make a guess, you submit a string to a checker. It should return only:

The number of characters in your string also in the passphrase (not in the correct position)
The number of characters in the correct position

If your string is a perfect match, it may output something indicating that (mine uses -1 for the first value).

For example, if the passphrase is the big cat and you guess tiger baby mauling, the checker should return 7,1. 7 characters (ige<space>ba<space>) are in both strings but different positions, and 1 (t) is in the same position in both. Notice that spaces count.

I've written an example (read: not optimized) function in Java, but feel free to write your own as long as it gives only the information required.

int[] guess(String in){
    int chars=0, positions=0;
    String pw = currentPassword; // set elsewhere, contains current pass
    for(int i=0;i<in.length()&&i<pw.length();i++){
        if(in.charAt(i)==pw.charAt(i))
            positions++;
    }
    if(positions == pw.length() && pw.length()==in.length())
        return new int[]{-1,positions};
    for(int i=0;i<in.length();i++){
        String c = String.valueOf(in.charAt(i));
        if(pw.contains(c)){
            pw = pw.replaceFirst(c, "");
            chars++;
        }
    }
    chars -= positions;
    return new int[]{chars,positions};
}

Scoring

Your score is simply the number of guesses you submit to the checker (counting the final, correct one) for all test phrases. The lowest score wins.

You must crack all the phrases in the list. If your program fails on any of them, it is invalid.

Your program must be deterministic. If run twice on the same set of passphrases, it should return the same result.

In the case of a tie for first, I will run the tied entries on my computer four times each, and the lowest average time to solve all 1000 cases wins. My computer is running Ubuntu 14.04, with an i7-3770K and 16GB of some sort of RAM, in case that makes a difference to your program. For that reason, and to facilitate testing, your answer should be in a language which has a compiler/interpreter that can be downloaded from the web free of charge (not including free trials) and does not require sign up/registration.

Title adapted from XKCD

Python 3.4 - min: 21, max: 29, total: 25146, time: 20min
min: 30, max: 235, total: 41636, time: 4min
Update:

Use binary search to find space. The idea is borrowed from Orby's answer. One spot I optimized is that if you found 2 spaces in a range when searching for the first space, you can narrow the search range of the second space.
Save wrong guesses along with their result. Compare with them in following guesses. This can save a lot.
Reduce letter enumerate count to 12, thanks to update #2.

This mehod don't use randomness so the score will not change.
First it use guesses like the following to find the first and second spaces in the answer.
. ......................
.. .....................
... ....................
.... ...................
# more follows, until two spaces found.

Then, it count occurrence of each letter by guessing aaaaa..., bbbbb.......
After these it will cost about 40 steps. In fact, we don't need to try all the letters and we can try them in arbitary order. In most cases, trying about 20 letters is enough. Here I choose 21.
Now it know the length of the first word and the second word so it can filter out a list of candidates for these two words. Normally it will have about 100 candidates left for each.
Then it just enumerate the first and the second word. Once the first two words is enumerated, we can infer all valid third word since we know it's character counts.
To optimize for speed, I use the concurrent.futures to add multiprocessing to the program. So you need Python 3 to run it and I tested it with Python 3.4 on my Linux box. Also, you need to install numpy.
import sys
import functools
from collections import defaultdict
from concurrent.futures import ProcessPoolExecutor
import numpy as np

def debug(*args, **kwargs):
    return
    print(*args, **kwargs)

def compare(answer, guess):
    b = sum(1 for x, y in zip(guess, answer) if x == y)
    a = 0
    c = defaultdict(int)
    for x in answer:
        c[x] += 1

    for x in guess:
        if c.get(x, 0) > 0:
            a += 1
            c[x] -= 1
    return a, b

def checker_task(guesser):
    @functools.wraps(guesser)
    def task(case):
        i, answer = case
        return (i, answer, run_checker(answer, guesser))
    return task

def run_checker(answer, guesser):
    guess_count = 0
    guesser = guesser()
    guess = next(guesser)
    while True:
        guess_count += 1
        if answer == guess:
            break
        try:
            guess = guesser.send(compare(answer, guess))
        except StopIteration:
            raise Exception('Invalid guesser')
    try:
        guesser.send((-1, -1))
    except StopIteration:
        pass
    return guess_count

# Preprocessing
words = list(map(str.rstrip, open('dict.txt')))
words_with_len = defaultdict(list)
for word in words:
    words_with_len[len(word)].append(word)

M = 12
chars = 'eiasrntolcdupmghbyfvkwzxjq'[:M]
char_ord = {c: i for i, c in enumerate(chars)}

def get_fingerprint(word):
    counts = [0] * (M + 1)
    for c in word:
        counts[char_ord.get(c, M)] += 1
    return tuple(counts[:-1])

word_counts = {word: np.array(get_fingerprint(word)) for word in words}

# End of preprocessing

# @profile
@checker_task
def guesser1():
    # Find spaces using binary search
    max_word_len = max(map(len, words))
    max_len = max_word_len * 3 + 2
    # debug('max_len', max_len)
    s_l = [1, 3]
    s_r = [max_len - 3, max_len - 1]

    for i in range(2):
        while s_l[i] + 1 < s_r[i]:
            # debug(list(zip(s_l, s_r)))
            mid = (s_l[i] + s_r[i]) // 2
            guess = '.' * s_l[i] + ' ' * (mid - s_l[i])
            a, b = yield guess
            if b > 1 and i == 0:
                s_l[1] = max(s_l[1], s_l[0] + 2)
                s_r[1] = min(s_r[1], mid)
                s_r[0] = mid - 2
            elif b > 0:
                s_r[i] = mid
            else:
                s_l[i] = mid
        if i == 0:
            s_l[1] = max(s_l[1], s_l[0] + 2)

    spaces = s_l
    del s_l, s_r

    word_lens = [spaces[0], spaces[1] - spaces[0] - 1, None]
    debug('word_lens', word_lens)
    debug('spaces', spaces)
    char_counts = [0] * M
    for i, c in enumerate(chars):
        guess = c * max_len
        _, char_counts[i] = yield guess

    char_counts = np.array(char_counts)

    candidates = [words_with_len[word_lens[0]], words_with_len[word_lens[1]], words]
    for i, ws in enumerate(candidates):
        candidates[i] = [word for word in ws if np.alltrue(char_counts >= word_counts[word])]
    P = defaultdict(list)
    for word in candidates[2]:
        P[get_fingerprint(word)].append(word)
    debug('candidates', list(map(len, candidates)))

    wrong_guesses = []
    # @profile
    def search(i, counts, current):
        if i == 2:
            rests = tuple(char_counts - counts)
            for word in P[rests]:
                current[i] = word
                guess_new = ' '.join(current)
                for guess, t in wrong_guesses:
                    if t != compare(guess_new, guess):
                        break
                else:
                    yield current
            return
        for word in candidates[i]:
            counts += word_counts[word]
            if np.alltrue(char_counts >= counts):
                current[i] = word
                yield from search(i + 1, counts, current)
            counts -= word_counts[word]

    try_count = 0
    for result in search(0, np.array([0] * M), [None] * 3):
        guess = ' '.join(result)
        a, b = yield guess
        try_count += 1
        if a == -1:
            break
        wrong_guesses.append((guess, (a, b)))
    debug('try_count', try_count)

def test(test_file, checker_task):
    cases = list(enumerate(map(str.rstrip, open(test_file))))
    scores = [None] * len(cases)
    with ProcessPoolExecutor() as executor:
        for i, answer, score in executor.map(checker_task, cases):
            print('-' * 80)
            print('case', i)
            scores[i] = score
            print('{}: {}'.format(answer, score))
            sys.stdout.flush()
    print(scores)
    print('sum:{} max:{} min:{}'.format(sum(scores), max(scores), min(scores)))

if __name__ == '__main__':
    test(sys.argv[1], guesser1)


Densely packed decimal (DPD) to decimal For nandgame fans: Please try out DPD to decimal in logic gates too!

Background

Densely packed decimal (DPD) is a way to efficiently store decimal digits in binary. It stores three decimal digits (000 to 999) in 10 bits, which is much more efficient than naive BCD (which stores one digit in 4 bits).

Notations

The lowercase letters a to i are the bits that are copied to the decimal representation.
0 and 1 are the exact bits in the input or output bit patterns.
x bits are ignored in the conversion.

Conversion table

The following is the conversion table from 10 bits of DPD to three decimal digits. Each decimal digit is represented as 4-bit binary (BCD). Both sides are written left to right from the most significant digit to the least.

Bits                 =>  Decimal         (Digit range)
a b c d e f 0 g h i  =>  0abc 0def 0ghi  (0-7) (0-7) (0-7)
a b c d e f 1 0 0 i  =>  0abc 0def 100i  (0–7) (0–7) (8–9)
a b c g h f 1 0 1 i  =>  0abc 100f 0ghi  (0–7) (8–9) (0–7)
g h c d e f 1 1 0 i  =>  100c 0def 0ghi  (8–9) (0–7) (0–7)
g h c 0 0 f 1 1 1 i  =>  100c 100f 0ghi  (8–9) (8–9) (0–7)
d e c 0 1 f 1 1 1 i  =>  100c 0def 100i  (8–9) (0–7) (8–9)
a b c 1 0 f 1 1 1 i  =>  0abc 100f 100i  (0–7) (8–9) (8–9)
x x c 1 1 f 1 1 1 i  =>  100c 100f 100i  (8–9) (8–9) (8–9)

Task

Convert 10 bits of DPD to 3 digits of decimal.

Test cases

DPD           Decimal
0000000101    005
0001100011    063
0001111001    079
0000011010    090
0001011110    098
1010111010    592
0011001101    941
1100111111    879
1110001110    986
0011111111    999
1111111111    999  * Output is same regardless of the `x` bits

Input

The default input format is a list of 10 bits. The bits should follow the exact order above, or the reverse of it. You may choose to use an equivalent string or integer representation instead. Unlike my other challenges, reordering or using nested structures is not allowed.

For the input [1, 1, 0, 0, 0, 1, 0, 1, 0, 0], the following formats are allowed:

List of bits: [1, 1, 0, 0, 0, 1, 0, 1, 0, 0]
String: "1100010100"
Binary integer: 788 or 0b1100010100
Decimal integer: 1100010100
Reversed: [0, 0, 1, 0, 1, 0, 0, 0, 1, 1] and reversed in any other formats above

The following formats are NOT allowed:

Arbitrary reordering of bits: [0, 0, 0, 0, 0, 1, 1, 1, 0, 1]
Nested structures: [[1, 1, 0], [0, 0, 1], [0, 1, 0, 0]] or [0b110, 0b001, 0b0100]

Output

The default output format is a list of 3 decimal digits. Each digit should be represented as 0 to 9, either an integer or a character. As in input, you can choose string or integer representation. If you choose integer representation, leading zeroes can be omitted.

Scoring & winning criterion

Standard code-golf rules apply. The shortest program or function in bytes for each language wins.


Find the intersection point of a plane and ray Given a ray with a point and a vector and a plane with a point and a normal vector to the plane. You have to find the intersection point of the plane and the ray..

So your job if you choose to accept is to write a shortest function that will do the job.

RULES:
The submission must be a complete program
And that's all

INPUT FORMAT:
x y z rx ry rz //gives the ray point and the ray vectors
x y z px py pz //gives the point on the plane and the vector normal to plane

OUTPUT FORMAT:
(x,y,z) //intersection point

Test Case:
2 3 4 0.577 0.577 0.577
7 1 3 1 0 0
(7,8,9)

The shortest codes in bytes win.

References: https://www.siggraph.org/education/materials/HyperGraph/raytrace/rayplane_intersection.htm  thanks orlp for the reference

Perl, 107 bytes

Tested for all test cases (i.e. not tested at all)
Run with each input number on its own line on STDIN

perl -M5.010 plane.pl
0
1
0
0
0
1
3
3
1
0
0
1
^D

plane.pl:

#!/usr/bin/perl
$$_=<>for a..l;say$a+($t=($j*($g-$a)+$k*($h-$b)+$l*($i-$c))/($j*$d+$k*$e+$l*$f))*$d,$",$b+$t*$e,$",$c+$t*$f

This kind of problem is absolutely not a good match for perlgolf. Perl lacks vector operations and uses too many $s