Is my Diffy game degenerate? Recently I posted a question about Diffy games which has gone unanswered.  Thats fine, the question is really hard, but I would like to make an easier question about Diffy games so that we can get the ball rolling.

How Diffy works

Copied from Find Diffy Games

The Diffy game works like as follows:  You start with a list of non-negative integers, in this example we will use

3 4 5 8

Then you take the absolute difference between adjacent numbers

 (8)  3   4   5   8
    5   1   1   3

Then you repeat.  You repeat until you realize you have entered a loop. And then generally the game starts from the beginning again.

3 4 5 8
5 1 1 3
2 4 0 2
0 2 4 2
2 2 2 2
0 0 0 0
0 0 0 0

Most games end in a string of all zeros, which is considered to be a lose state, but a rare few games get stuck in larger loops.

Task

Given the starting state of a Diffy game determine whether or not the game eventually reaches a state of all zeros.  You should output a Truthy or Falsy value for each of the two states.  Which corresponds to which does not matter.

The goal is to minimize the number of bytes in your source.

Pyth, 6 bytes

suaV+e

Test suite

This program is very suave. 0 (falsy) means all zeroes, anything else (truthy) means not all zeroes.

How it works:

suaV+e
suaV+eGGGQ    Variable introduction.
 u       Q    Apply the following function repeatedly to its previous result,
              starting with the input. Stop when a value occurs which has
              occurred before.
  aV          Take the absolute differences between elements at the same indices of
        G     The previous list and
    +eGG      The previous list with its last element prepended.
s             The repeated value is returned. Sum its entries. This is zero (falsy)
              if and only if the entries are all zero.


Ridiculous Runtime Errors Write programs that produce crazy, obscure, ridiculous, or just plain nutty runtime errors.  Obfuscation and golfitude (shortness) not required.

solutions that look like they should work fine are better.
solutions that look like they should break one way but break another are better.
solutions that are nondeterministic are better as long as they are reproducible sometimes.
solutions with long distance between error cause and manifestation are better.
bonus points for producing errors that should be impossible.
bonus points for errors that crash the runtime (like making python segment fault) or operating system.

The unit of score shall be upvotes.

Addendum 1

Compiler misbehaviors are fine too.

The obligatory PHP one (which still hasn't been fixed as of 5.4):

<?::

Outputs:

Parse error: syntax error, unexpected T_PAAMAYIM_NEKUDOTAYIM on line 1

Whaa?


Output the qwerty keyboard Given a character, output (to the screen) the entire qwerty keyboard layout (with spaces and newlines) that follows the character. The examples make it clear.

Input 1

f

Output 1

g h j k l
z x c v b n m

Input 2

q

Output 2

w e r t y u i o p
a s d f g h j k l
z x c v b n m

Input 3

m

Output 3

(Program terminates without output)

Input 4

l

Output 4

z x c v b n m

Shortest code wins. (in bytes)

P.S.

Extra newlines, or extra spaces at the end of a line are accepted.

CJam, 42 40 bytes

"wertyuiop asdfghjkl zxcvbnm"q/W=S%Sf*N*

Test it here.

Explanation

"we...nm"
     e# Push the letters in order, without q. We don't need q, because it will never
     e# be part of the output.
q/   e# Split the string around the input. If the input is "q", the entire string
     e# will go into a single chunk.
W=   e# Select the last chunk.
S%   e# Split the string around spaces, discarding empty segments (only relevant for the
     e# first segment if the input is "p" or "l").
Sf*  e# Join each line by spaces.
N*   e# Join the lines by linefeeds.


How to pluralize ellipsis? It's obviously ellipsisessieses.
Inspired by a chat message.
Your challenge
Given a list or space or comma-separated string of words, ellipsisessiesesify them.
To ellipsisessieses-ify a word:

Start with the word.
Add the first letter of the original word to the end.
Add 2 of the last letter of the original word to the end.
Add the second-to-last letter of the original word to the end.
Add the first letter of the original word to the end.
Add the last letter of the original word to the end.
Repeat steps 5 & 6 once.
You're done!

You can assume:

The input words will only be alphanumeric
Input & output can be a space-separated string or list
The input will contain only words
The words will be at least 2 letters long
The input will match the regex /^[a-z0-9]{2,}( [a-z0-9]{2,})*$/i
You can have a different input and output format
More to come...

Test cases:
ellipsis -> ellipsisessieses
goat -> goatgttagtgt
covfefe -> covfefeceefcece
programmer5000 -> programmer5000p000p0p0
up vote down goat -> upuppuupup voteveetveve downdnnwdndn goatgttagtgt
it is golf yo -> itittiitit isissiisis golfgfflgfgf yoyooyyoyo
crossed out 44 is still 44 -> crossedcddecdcd outottuotot 4444444444 isissiisis stillslllslsl 4444444444

Shorteststtsstst answerarrearar ininniinin bytesbssebsbs winswssnwsws!

JavaScript (ES6), 58 57 bytes

NB: This turns out to use the same trick as Jonathan Allan in this Jelly answer (though I noticed after posting).

Saved 1 byte thanks to Jonathan Allan

Works on arrays of strings.

s=>s.map(s=>s+'01120101'.replace(/./g,n=>s.substr(-n,1)))

Test cases

let f =

s=>s.map(s=>s+'01120101'.replace(/./g,n=>s.substr(-n,1)))

console.log(f(['ellipsis']))
console.log(f(['goat']))
console.log(f(['covfefe']))
console.log(f(['programmer5000']))
console.log(f(['up', 'vote', 'down', 'goat']))
console.log(f(['it', 'is', 'golf', 'yo']))
console.log(f(['crossed', 'out', '44', 'is', 'still', '44']))


Run through an array We all often hear the idiom "walk through the array" to mean "map the function over the following array". However, I need it done (now!), so I want you to run through the array.

How do I run?

Imagine there's a wild pack of wolves behind you

Running through an array is like walking through one, except you  can skip over elements. Yes, it's sometimes messy, but it (generally) works. "Which elements are skipped?", you may ask. Well, this is done at random. Let's walk through running through the array!

Let e be the current element.
Let random generate a random float in [0,1). If random() < 0.5, then you go the next element and then to step 1. (You may generate a number by other means, so long as their is an (ideally) equal chance of skipping and remaining. E.g., you can use choose an element from a two-member set and perform the action based on the result.)
Otherwise, you perform function f on e.

Objective

Given an array/list/string like either A and a number K, run through the array, adding K to each member accessed. Output/return this array. A will only contain non-negative integers, and K will only ever be a non-negative integers. This is a code-golf, so the shortest program in bytes wins.

Test cases (examples)

K, A => possible K'
[1, 2, 3, 4], 0 => [1, 2, 3, 4]
[1, 2, 3, 4], 1 => [1, 3, 3, 5]
[0, 0, 0, 0], 2 => [2, 0, 0, 2]

Clojure, 41 37 bytes

(fn[a k](map #(+(*(rand-int 2)k)%)a))

Knocked off a couple of bytes by multiplying by 0 or 1 and dropping the "if". Credit to most all of the other submitters!


LaTeX Table Generator Write a function or program which, given a number of lines and columns, generates a corresponding tabular environment for LaTeX with no data in it.

Table format and tabular Environment

Here is an example of a table with 2 rows and 4 columns:

As you can see, we do not count the first row nor do we count the first column: those are for the labels of the table.

The top left corner is also "missing", in that there is no border around it.

The corresponding LaTeX's code to generate this table is the following:

\begin{tabular}{|c|c|c|c|c|}
    \cline{2-5}
    \multicolumn{1}{c|}{} & & & & \\
    \hline
    & & & & \\
    \hline
    & & & & \\
    \hline
\end{tabular}

There are as many c in the first line as there are total columns (that is, 1 more than the number of columns given as input). These c are separated by | (and there are | on both the extreme left and extreme right too).
The first horizontal separator is generated by \cline{2-X} where X is the index of the last column (starting from 1).
The first element of the first row is always \multicolumn{1}{c|}{} (this removes the borders of the top left corner).
Each row has C &, C being the number of columns given as input. Each line ends with \\.
Each row is followed by a \hline.

Formatting details

You must indent everything between the begin{tabular}{...} and \end{tabular} tags with 4 spaces.
The &'s are separated with exactly one space on each row. The first one of the row does not have an extra space before it (since it already has 4 spaces before it). Note that this is not true for the first row, where the first & has a space before it because of the \multicolumn element.
\\ is separated from the last & by a space.
Each \hline and row description is on its own new line.

Input

Input is a couple of two integers representing the number of columns and the number of rows. Note that this is the number of columns and rows excluding the very first row and very first column.

You may assume that the row and column inputs will always be at least 1, and less than 1024.

Those two numbers can be taken whichever way is most appropriate in your language (two args, a list, etc.).

Output

The output is a string of the LaTeX code that generates a table with the appropriate number of rows and columns. This can be returned from a function or outputted to STDOUT.

A trailing new line is allowed after the \end{tabular}. Trailing spaces are not allowed at the end of any line.

Test cases

Input: (1,1)
Output:
\begin{tabular}{|c|c|}
    \cline{2-2}
    \multicolumn{1}{c|}{} & \\
    \hline
    & \\
    \hline
\end{tabular}

Input: 2 rows, 4 columns
Output:
\begin{tabular}{|c|c|c|c|c|}
    \cline{2-5}
    \multicolumn{1}{c|}{} & & & & \\
    \hline
    & & & & \\
    \hline
    & & & & \\
    \hline
\end{tabular}

Scoring

This is code-golf, so the shortest code in bytes \emph{wins}.

Python 2, 197 bytes

This solution uses string formatting to reduce repetition. Each string component is assembled, then placed within the template. It is tricky to use so many backslashes in Python strings. I used the raw string r'\\' and multi-line '''blah \n blah''' string techniques here.

def a(d,e):
 c='c|'*e;b='& '*e+r'\\';g=' '*4+b+'\n    \\hline\n';f=g*d;h='{tabular}'
 return r'''\begin%s{|c|%s}
    \cline{2-%s}
    \multicolumn{1}{c|}{} %s
    \hline
%s\end%s'''%(h,c,e+1,b,f,h)

Before the minifier, it looks like this:

def latextable(height, width):
    columns = 'c|' * width;
    linespec = '& ' * width + r'\\';
    line = ' '*4 + linespec + '\n    \\hline\n';
    block = line * height;
    mode = '{tabular}'
    return r'''\begin%s{|c|%s}
    \cline{2-%s}
    \multicolumn{1}{c|}{} %s
    \hline
%s\end%s''' % (mode, columns, width+1, linespec, block, mode)

print latextable(1, 1)
print latextable(2, 4)

The output tests:

\begin{tabular}{|c|c|}
    \cline{2-2}
    \multicolumn{1}{c|}{} & \\
    \hline
    & \\
    \hline
\end{tabular}
\begin{tabular}{|c|c|c|c|c|}
    \cline{2-5}
    \multicolumn{1}{c|}{} & & & & \\
    \hline
    & & & & \\
    \hline
    & & & & \\
    \hline
\end{tabular}

As a side note, I wrote a latex macro processor like this to format my thesis. I think I spent longer on developing that macro processor than on writing the words...


How many pages have issues? At work I've been acting as quality control on our public documents, to make sure that they are WCAG 2.0 compliant. Given the length of some of these documents there tend to be issues, and so I record the issues and the pages they occur on.

The challenge: Given a string input, output a count of all distinct pages within the string.

Rules:

Input will consist of of a non-empty string containing the pages, page ranges, and the issue. Multiple pages and page ranges are guaranteed to be separated by commas ,.

pgs 810-812, 897, 1043, 1047, 1219, 1308, 1317, 1323 restructure reading boxes

pgs 810-812,897,1043, 1047,1219, 1308, 1317, 1323 restructure reading boxes

Both of the above are possible valid inputs.

This input can be multiple lines, with each line representing a different issue.

pgs 810-812, 897, 1043, 1047, 1219, 1308, 1317, 1323 restructure reading boxes
pgs 816, 819, 826, 827, 829, 853, 861, 866, 885, 1043, 1142, 1143, 1164 table needs to be read as table or figure

You can take a multiline input as a list of strings, with each item in the list being a line. The output is still based on the entirety of the list.

The input format is not necessarily pgs <page numbers> <issue>.

Both pg 1324 read all and Read all are valid inputs.

If the string consists of only <Issue>, this represents that the document is a single page, and thus the output would be 1 (no matter how many lines of input there are). If there is more than one page, you are guaranteed to not have this format as a line of the input.

Test Cases:

Input:
------
pgs 810-812, 897, 1043, 1047, 1219, 1308, 1317, 1323 restructure reading boxes

Output:
-------
10

Input:
------
pgs 587,897, 936, 939,946, 1308 single figure
pgs 810-812, 897, 1043, 1047, 1219,1308,1317, 1323 restructure reading boxes

Output:
-------
14

Input:
------
pgs 824, 873, 941-943, 1032, 1034, 1036-1040, 1055, 1071, 1153, 1154, 1228 figures as figures
pgs 1036-1040 Color Contrast for negative balance numbers does not meet WGAC 2.0 guidelines
pg 1324 read all

Output:
-------
18

Input:
------
Incorrect Reading Order

Output:
-------
1

Input:
------
Incorrect Reading Order
Pg 1 Read Table as Table
Pgs 1 Color Contrast for negative balance numbers does not meet WGAC 2.0 guidelines

Output:
-------
1

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

05AB1E, 51 38 bytes
-13 bytes thanks to Kevin Cruijssen!
',ð:#ʒ'-м€.ïß}D.ï≠ÅÏ'-¡¤LsнUʒX<›]˜Ùg1M

Try it online!
Explanation
                                      // Implicitly Read in multiline string
 ',ð:#                                //Swap commas with spaces and split on spaces
      ʒ'-м€.ïß}                       //Filter list to only those with - removed are numbers
               D                      //Duplicate
                .ï≠ÅÏ                 //For all the ones that aren't numbers (so the ranges)
                    '-¡               //Split on dashes
                       ¤L             //Generate list from 1 to the highest number
                         sнU          //Stick the lower number in the variable U
 ʒ®<›]                                //Filter out numbers less than the lower number
      ˜                               //deep flatten
        Ùg                            //Uniquify and count
          1M                          //Push 1 then output the largest number in the stack


Output subdivisions of international standard paper sizes ISO Paper Sizes Defined:

The A series paper sizes are defined by the following requirements:

The length divided by the width is the square root of 2.
The A0 size has an area of 1 unit.
Each subsequent size A(n) is defined as A(n-1) cut in half parallel to its shorter sides.

Task:

given an input f[n] output A0 divided into n subdivisions.

Test cases:

f[1] to f[12]:

Here, A0 is given by f[1], but this indexing isn't essential.

Winning criteria:

The shortest code in bytes wins.


What's the chance that I'll win a door prize? My local ACM chapter gives out door prizes to people who come to the meetings. You get an increased chance of winning if you solve the programming puzzle, however (but I always solve that puzzle). Thus, some people have 1 entry, while others have 2. But wait! The way the raffle program works is not by adding in another entry when someone solves the puzzle. Instead, it keeps track of the number of "lives" a person has, decrementing that if that person is chosen in each pass of it's random sampling algorithm. So it works like this:

Doorknob: 1.  xnor: 2.  Justin: 2.  Alex: 1.  Dennis: 2.

Then the program randomly chooses one of [Doorknob, xnor, Justin, Alex, Dennis], decrements the number (say it chooses Justin):

Doorknob: 1.  xnor: 2.  Justin: 1.  Alex: 1. Dennis: 2.

And repeats. If someone's number of "lives" goes to 0 (let's choose Justin again), they're removed from the list:

Doorknob: 1.  xnor: 2.  Alex: 1.  Dennis: 2.

This continues until there's one person left; that person is the winner.

Now the real question is, what was the probability that I would have won?

You will be given two inputs:

n. This is the number of people entered into the challenge
k. This is the number of people (of those n) who have 2 lives. This number always includes you.

So if I had a function p and called p(10, 5), that would be the probability of winning the prize where there are 10 people total, 5 of which only have 1 life, whereas 5 (including you) have 2 lives.

You are expected to output the probability of winning either exactly, or as a decimal. At any rate, answers must be accurate up to and including the 4th decimal place after the decimal point. Whether or not you round to that digit is up to you.

Your solution may be a randomized solution which outputs the answer to the 4th decimal place with high probability. You may assume that the built in RNG you use is truly random, and it must output the correct answer with at least 90% probability.

Furthermore, your code need only work for n, k <= 1000, although I did provide test cases larger than that for those curious.

Test Cases

Note: some of these are general formulae.

n,    k   |  output
----------+---------
1,    1   |  1
2,    2   |  0.5
2,    1   |  0.75
3,    1   |  11/18 = 0.611111111
1000, 1   |  0.007485470860550352
4,    3   |  0.3052662037037037
k,    k   |  1/k
n,    1   |  (EulerGamma + PolyGamma[1 + n])/n    (* Mathematica code *)
          |  (γ + ψ(1 + n))/n
10,   6   |  0.14424629234373537
300,  100 |  0.007871966408910648
500,  200 |  0.004218184180294532
1000, 500 |  0.0018008560286627948
---------------------------------- Extra (not needed to be a valid answer)
5000, 601 |  0.0009518052922680399
5000, 901 |  0.0007632938197806958

For another few checks, take p(n, 1) * n as follows:

n     |  output
------+---------
1     | 1
2     | 1.5
3     | 1.8333333333333335
10    | 2.928968253968254
100   | 5.1873775176396215
-------------------------- Extra (not needed to be a valid answer)
100000| 12.090146129863305

MATL, 42 bytes

:<~QXJx`J`tf1Zry0*1b(-tzq]f1=vts3e8<]6L)Ym

This uses a probabilistic (Monte Carlo ) approach. The experiment is run a large number of times, from which the probability is estimated. The number of realizations is selected to ensure that the result is correct up to the fourth decimal with probability at least 90%. However, this takes a very long time and a lot of memory. In the link below the number of realizations has been reduced by a factor of 106 so that the program ends in a reasonable amout of
time; and only the first decimal is guaranteed to be accurate with at least 90% probability.

EDIT (July 29, 2016): due to changes in the language, 6L needs to be replaced by 3L. The link below incorporates that modification.

Try it online!

Background

Let p denote the probability to be computed. The experiment described in the challenge will be run for a number n of times. Each time, either you win the prize (“success”) or you don't. Let N be the number of successes. The desired probability can be estimated from N and n. The larger n is, the more accurate the estimation will be. The key question is how to select n to fulfill to the desired accuracy, namely, to assure that at least 90% of times the error will be less than 10−4.

Monte Carlo methods can be

Fixed-size: a value of n is fixed in advance (and then N is random);
Variable-size: n is determined on the fly by the simulation results.

Among the second category, a common used method is to fix N (desired number of successes) and keep simulating until that number of successes is achieved. Thus n is random. This technique, called inverse binomial sampling or negative-binomial Monte Carlo, has the advantage that the accuracy of the estimator can be bounded. For this reason it will be used here.

Specifically, with negative-binomial Monte Carlo x = (N−1)/(n−1) is an unbiased estimator of p; and the probability that x deviates from p by more than a given ratio can be upper-bounded. According to equation (1) in this paper (note also that the conditions (2) are satisfied), taking N = 2.75·108 or larger ensures that p/x belongs to the interval [1.0001, 0.9999] with at least 90% probability. In particular, this implies that x is correct up to the 4th decimal place with at least 90% probability, as desired.

Code explained

The code uses N = 3e8 to save one byte. Note that doing this many simulations would take a long time. The code in the link uses N = 300, which runs in a more reasonable amount of time (less than 1 minute in the online compiler for the first test cases); but this only assures that the first decimal is correct with probability at least 90%.

:        % Take k implicitly. Range [1 ... k]
<~       % Take n implicitly. Determine if each element in the previous array is
         % less than or equal than n
Q        % Add 1. This gives an array [2 ... 2 1 ... 1]
XJx      % Copy to clipboard J. Delete from stack
`        % Do...while. Each iteration is a Monte Carlo realization, until the
         % desired nunber of successes is reached
  J      %   Push previously computed array [2 ... 2 1 ... 1]
  `      %   Do...while. Each iteration picks one door and decrements it, until
         %   there is only one
    t    %     Duplicate
    f    %     Indices of non-zero elements of array
    1Zr  %     Choose one of them randomly with uniform distribution
    y0*  %     Copy of array with all values set to 0
    1b(  %     Assign 1 to chosen index
    -    %     Subtract
    tzq  %     Duplicate. Number of nonzero elements minus 1. This is falsy if
         %     there was only one nonzero value; in this case the loop is exited
  ]      %   End do...while
  f1=    %   Index of chosen door. True if it was 1 (success), 0 otherwise
  v      %   Concatenate vertically to results from previous realizations
  ts3e8< %   Duplicate. Is the sum less than 3e8? If so, the loop is exited
]        % End do...while
6L)      % Remove last value (which is always 1)
Ym       % Compute mean. This gives (N-1)/(n-1). Implicitly display


Produce a Simple Station Model A station model is a diagram for recording the weather at a certain place and time.

Challenge

You must write the shortest code possible to graphically output a simplified (explained later) station model.

Ticks

A tick is a line on the wind barb. A 50 knot tick is a triangle. A 10 knot tick is a line. A 5 knot tick is half the length of a 10 knot tick. The windspeed is indicated by summing the ticks, using the largest value symbols whenever possible. The ticks start at the end of the line and are arranged in descending order of size toward the circle. An exception is 5 knots, where the tick is placed a short distance away from the end (to avoid ambiguity with 10 knots.)

Here is some pseudocode to calculate the ticks required

set f=int(s/5)
set t=int(f/2)
f=f-(t*2)
set ft = int(t/5)
t=t-(ft*5)

Where f is the number of 5 knot ticks, t is the number of 10 knot ticks and ft is the number od 50 knot ticks. (This rounds down to the nearest 5, but your code should round up or down, whichever is nearer.) Note that there is only ever one 5 knot tick.

Other

You may only display two things on your station model: wind speed and direction. These must be supplied by the user: hardcoding is not permitted. The wind speed must be a positive integer in knots while the wind direction must be in letters (e.g. NNE, W, ESE). 16 points of the compass will be considered (up to three letters.) See http://en.wikipedia.org/wiki/Points_of_the_compass

The 50 knots tick must be as in the picture above.

Set cloud cover to clear (the circle must be empty.)
The highest wind speed allowed is 201 knots (round it to 200).

Since the wind ticks only increase in imcrements of 5, round all wind speeds to the nearest 5.

As always, since this is code golf, the shortest code wins.

Examples

All of the following have a cloud cover of clear.

20 knots, SW (225°)

15 knots, N (0°)

Test cases

50 knots, NNE
0 knots
12 knots S
112 knots WNW

BBC BASIC, 273 ASCII characters (not golfed yet)

Emulator at http://www.bbcbasic.co.uk/bbcwin/bbcwin.html

Parsing the direction is a dirty hack. I simply take a walk through a cartesian grid for each letter input. They aren´t echoed to the screen, and the input is terminated when a space is received.

As this is codegolf, I don't bother to normalise the direction vector. Therefore the size of the symbol drawn is dependent on the number of characters input. The proportions are the same for all inputs, however. Also, for the 3-letter inputs the angle is 4 degrees closer to the diagonal than it should be. For example, NNE is atan(0.5)=26.57 degrees instead of the correct 22.5 degrees, but it is barely noticeable. Both these points could be corrected for about 20-30 characters.

After the direction, the speed is input (this is echoed to the screen and terminated with a newline.)

  x=0
  y=0
  REPEAT
    d=GET                             :REM get character from keyboard
    x+=(d=87)-(d=69)                  :REM d=87 evaluates to -1 if "W", d=69 is -1 if "E"
    y+=(d=83)-(d=78)                  :REM d=83 evaluates to -1 if "S", d=69 is -1 if "N"
  UNTILd=32
  x*=20                               :REM boost the sizes of x and y
  y*=20                               :REM normalization code would go here
  INPUTs
  s=INT(s/5+.5)                       :REM divide s by 5 and round to nearest int. 50-tick=10, 10-tick=2, 5-tick=1
  MOVE600,500                         :REM move to centre of circle
  PLOT145,x,y                         :REM draw circle centred at 600,500 with 600+x,500+y on its edge. cursor remains at the latter position.
  IFs=0END                            :REM exit if wind=0
  DRAWBY 9*x,9*y                      :REM draw the shaft of the arrow, 9 units long, from current position
  IFs>1 MOVEBY x,y                    :REM if rounded windspeed >5 move one more space out.
  WHILEs>1                            :REM while there are still 50-ticks and 10-ticks to draw
    MOVEBY 2*y,-2*x                   :REM move 2 units clockwise of the shaft
    PLOT1-(s>9)*80,-2*y-x,2*x-y       :REM draw a diagonal line back to the shaft. If s is 10 or over, plot mode 81 will take the last 2 positions of the graphics cursor and draw a triangle.
    s-=2-(s>9)*8                      :REM Decrement s by 2 or 10, according to the last barb drawn.
  ENDWHILE
  IFs MOVEBY -x,-y:DRAWBY x/2+y,y/2-x :REM If s=1 draw the 5-tick. Unlike the other ticks, it is drawn from its root outwards.

Output

All the test cases from the quesion are shown, plus two more to illustrate 2-letter directions:

50 knots, NNE
0 knots
12 knots S
112 knots WNW
195 knots SE
5 knots SW

In order to show them all together, I didn't clear the screen between runs. The different sizes (but constant proportions) of the arrows can be seen.


Confirm the Illuminati The Illuminati commands you (with their mind control) to output the following string:

         ^
        /_\
       /_|_\
      /_|_|_\
     /_|/o\|_\
    /_|_\_/_|_\
   /_|_|_|_|_|_\
  /_|_|_|_|_|_|_\
 /_|_|_|_|_|_|_|_\
/_|_|_|_|_|_|_|_|_\

Rules:

Trailing spaces are allowed for each line.
Leading spaces in each line are required.
Trailing whitespace is allowed after the full required output.
Since this is a code-golf challenge, the winner shall be the shortest program in bytes.
Since this is a kolmogorov-complexity challenge, hardcoded output is allowed.
Standard Loopholes apply.
Update: You may use tabs instead of spaces, with each tab counting as 4 spaces. If you want for some reason.

Sandbox (I would leave it for the full 72 hours recommended by the sandbox FAQ, but with 7 upvotes and next to no negative feedback, 38 should be fine)

Vim, 40 bytes
-2 bytes thanks to DJMcMayhem
9i_|␛r\I/␛qqYPxR /␛q8@qr^4jhR/o\␛jr/2hr\

You can see it in action in this GIF made using Lynn's python script


Enter your name via a D-pad The puzzle:
Consider a console/hand-held game with a d-pad where you are required to enter a name of sorts. This appeared in many older games before the use of QWERTY was popularised in consoles (e.g. I believe the Wii uses a QWERTY keyboard layout for input). Typically, the on-screen keyboard looks to the effect of*:
Default:
0 1 2 3 4 5 6 7 8 9
A B C D E F G H I J
K L M N O P Q R S T
U V W X Y Z _ + ^ =

With the case switched:
0 1 2 3 4 5 6 7 8 9
a b c d e f g h i j
k l m n o p q r s t
u v w x y z - + ^ =

That is, all alphanumeric keys and the following:
_: A single space
-: A hyphen
+: Switch case for the next letter only
^: Toggle caps lock (that is, switch the case of all letters)
=: Enter, complete
*Obviously I replaced keys like "BKSP" and "ENTER" with shorter versions
And then the hardware would include a d-pad (or some form of control where you could go up, down, left and right)
The screen also typically let you move from one side directly to the other. That is, if you were focussed on the letter J, pressing right would allow you to move to the letter A.
Whenever I was entering my name, I'd always try to work out the quickest way to do so.
Goal:
Your program will take string input which may include any alphanumeric character including a space and hyphen, and your goal is to output the shortest amount of key presses on the d-pad to output the required string.
Considerations:
You do not need to include the key pressed for pressing the actual character.
Focus always starts at the A
Enter = must be pressed at the end
Example:
input: Code Golf
output: 43
Explained:
A -> C = 2
C -> ^ = 6 (moving to the left)
^ -> o = 5
o -> d = 2
d -> e = 1
e -> + = 5
+ -> _ = 1
_ -> + = 1
+ -> G = 3
G -> o = 3
o -> l = 3
l -> f = 5
f -> = = 6
Note that it is quicker to hit the + twice for a _ and a G than it is to hit ^ once, then swap back.
The winning submission (I'll allow at least 1w) will be the shortest solution (in bytes). As this is my first question, I hope this is clear and not too hard.

Swift 1.2, 812 588 670 bytes

Edit: Removed 224 bytes by replacing the large arrays of numbers with a Range and converting it to an Array instead.

Edit2: Added looping vertically

typealias S=String
typealias I=Int
var A:(I)->S={S(UnicodeScalar($0))},B:(I)->(I,I)={a in(a%10,a/10)},a=Array(48...57).map{A($0)},b=[a+(Array(65...90)+[32,43,94,61]).map{A($0)},a+(Array(97...122)+[45,43,94,61]).map{A($0)}],z=Process.arguments
z.removeAtIndex(0)
func C(e:I,f:I)->I{let(a,b)=B(e),(c,d)=B(f)
return min(abs(d-b), abs(4-(d-b)))+min(abs(c-a),abs(10-(c-a)))}
func D(c:S,_ e:I=10,_ f:Bool=false,_ g:Bool=false)->I{if count(c)==0{return C(e,39)}
let h=c.startIndex,i=c.endIndex,j=S(c[h])
if let k=find(b[f ?1:0],j){return C(e,k)+D(c[advance(h,1)..<i],k,(g ?(!f):f),false)}else{return min(C(e,37)+D(c,37,!f,true),C(e,38)+D(c,38,!f,false))}}
print(D(" ".join(z)))

To run, put the code in a .swift file and run it with swift <filename> <your name>

This uses the simple approach where the two 'keyboards' are stored as arrays.

B:(I)->(I,I)={a in(a%10,a/10)}
Converts an index from the array to an x,y position on the virtual keyboard.

func C(e:I,f:I)->I{let(a,b)=B(e),(c,d)=B(f)
 return abs(d-b)+min(abs(c-a),abs(10-(c-a)))} Takes a start/end index and returns the minimum number of moves to get from once to the other (accounting for horizontal wrap)

func D(c:S,_ e:I=10,_ f:Bool=false,_ g:Bool=false)->I Is the main recursive function that does most of the calculations.  It calculates the distance from the current position to the target character, unless the case should change, then it calculates both the shift and the caps lock methods and takes the smallest.

Running swift codegolf.swift Code Golf prints 43


Shortest self-avoiding path given a sequence of turns Write a program or function which, given a non-empty sequence of right or left turns, outputs the length of the shortest self-avoiding path on a 2D lattice with those turns.

The input should be taken as a string, with each character being R or L for a right or left turn respectively.

The output should be an integer, the length of the shortest path with the given turns.

This is a gode golf - shortest code wins.

Example

Given the input

LLLLLLLLLLRRL

The shortest path is the following (starting at #):

+-+-+-+-+-+-+
|           |
+ . + +-+-+ +
|   | |   | |
+ +-+ + #-+ +
| |   |     |
+ +-+ +-+-+-+
|   |
+-+-+ . . . .

And the total length of this path is 29 (counting the -s and |s, not the +s).

Test Cases

L 2
RRRRRRRRRR 23
LRRLRLRRRRL 15
LLRRLRRRRLLL 17
LLRRRRRRLLLL 21
LLLLRLLRRLLRL 16
LRLRLRLLRLRRL 14
RLLRRRRLLRRLRL 17
RRRRLLRLLLRLRL 20
LLLLRRLRLRRRLRL 19
RRRLRRRLRRLRLRL 20

Prolog, 284 bytes

e(S,[0|X]):-e(S,X).
e([A|S],[A|X]):-S=X;e(S,X).
v(X/Y,76,Y/Z):-Z is -X.
v(X/Y,82,Z/X):-Z is -Y.
v(D,0,D).
c([],0/0-0/1,[0/0]).
c([H|T],K/L-D/E,[K/L|C]):-c(T,I/J-X/Y,C),v(X/Y,H,D/E),K is I+X,L is J+Y,\+member(K/L,C).
n(X):-X=0;n(Y),X#=Y+1.
p(S,L):-n(L),length(X,L),e([0|S],X),c(X,_,_).

This is a pretty straightforward statement of the algorithm, and fairly inefficient (not all the test cases ran in reasonable time, although most did). It works via generating all possible lengths for the output from 1 upwards (n); generating all possible sequences of left/forward/right of that length which are consistent with the input (implemented in e; the new path is called X); then checking for the first such path that's valid (c, which calls into v to handle the effects of left and right turns on the x and y deltas). The return length is the first output seen in L. (+2 penalty if you want to prevent the function returning other possible outputs for the length if you backtrack into it; it's never quite clear how Prolog's idiosyncratic function returns should be counted.)

There isn't much in the way of golfing tricks here, but there is some. n was implemented with a constraint solver because it allows more whitespace to be removed without confusing the parser; this might require GNU Prolog to be used, not sure on that. (I couldn't do the same in c as it needs to handle negative numbers.) The implementation of e is considerably less efficient than it needs to be, via matching a list in multiple ways; the more efficient e([],[]). would be six bytes longer (it'd allow the S=X; on line 2 to be removed, but that's only a gain of four compared to a loss of ten). To allow me to match coordinates and directions as a whole, or just part, I represent them as X/Y (i.e. an unevaluated AST, which can be matched on), allowing me to use infix notation.

Prolog, 256 bytes, too inefficient to easily test

Of course, because this is Prolog, many of the functions are reversible, e.g. c can be used to generate all paths from the origin to a particular coordinate pair. Additionally, c naturally generates from shortest to longest. This means that instead of asking for a minimum length explicitly, we can just get c to generate all paths that go anywhere, then look for the first one that's consistent with the input:

e(S,[0|X]):-e(S,X).
e([A|S],[A|X]):-S=X;e(S,X).
v(X/Y,76,Y/Z):-Z is -X.
v(X/Y,82,Z/X):-Z is -Y.
v(D,0,D).
c([],0/0-0/1,[0/0]).
c([H|T],K/L-D/E,[K/L|C]):-c(T,I/J-X/Y,C),v(X/Y,H,D/E),K is I+X,L is J+Y,\+member(K/L,C).
p(S,L):-c(X,_,_),length(X,L),e([0|S],X).

This has exponential performance (O(3n), where n is the output). However, I did manage to verify it on some of the smaller tests (it takes around 7 seconds to output 14, and around 20 to output 15, on my computer).


Loophole for other challenge You are to post an answer you posted that exploited a loophole in the challengers question. Bonus points if it caused them to rewrite the question.

For example, one challenge was to write a program that such that if a random character is removed, it still works, and your score is how many characters it fails on. Some one posted the empty program, since then it would fail on no characters (though the compiler would fail) and the question had to be changed. He was unrightly down-voted, so I hope he sees this challenge.

This is a popularity contest, so whoever gets the most votes wins!

In my answer to Loophole for other challenge, I deliberately exploit the fact that the poster didn't specify that the answer had to be responding to another question.  This made my answer recursive and self-referential.

I also golfed my answer (even though it was a popularity contest).  0 bytes of code.


Tips for golfing in Proton Proton is a quite new language created by PPCG user Hyper Neutrino.

It is very similar to Python, and has similar syntax to the language Cheddar, hence there are some clever tricks you can use in order to reduce your byte count. Let's get those cool tricks listed here. As usual, please post one tip per answer and avoid obvious things (e.g. remove spaces). If you have any further questions about any of the tips listed, there is a dedicated chat room for Proton.

Use currying when you need a lambda with 2 arguments
If you want a function with 2 arguments, currying syntax always saves 1 byte. For example:
f=(a,b)=>a+b

Is one byte longer than:
f=a=>b=>a+b

The first function can be called with f(number_1, number_2), whilst the latter is called using f(number_1)(number_2).
Try it online!


Giant Babylonian Matrices Introduction

The Babylonians had a clever method for finding square roots.  To find the square root of a number N, you start with a guess, then refine it by repeatedly evaluating a line of computer code (or papyrus scroll equivalent):

guess = (guess + N/guess) / 2

If the guess is smaller than sqrt(N), N/guess must be larger than sqrt(N), so averaging these two terms should get you closer to the true answer.  It turns out this method converges fairly quickly to the correct answer:

N = 7
guess = 1
guess = 4.0
guess = 2.875
guess = 2.65489
guess = 2.64577
guess = 2.64575
guess = 2.64575

Extension

Does an equivalent algorithm exist for matrices?  Throwing all mathematical rigor aside, if we wish to find the 'square root' of a square matrix M, we may again start with a guess, then refine it by repeatedly evaluating a line of code:

guess = (guess + inverse(guess)*M) / 2

where inverse() is the matrix inverse function, and * is matrix multiplication.  Instead of 1, our initial guess is an identity matrix of the appropriate size.

However, convergence is no longer guaranteed - the algorithm diverges for most (but not all) inputs.  If M produces a convergent series, it is a Babylonian matrix.  Furthermore, the converged value is actually the real square root of the matrix (i.e., guess*guess = M).

Example

Here's an example using a 2x2 matrix, showing convergence of the series:

M = [[7,2],[3,4]]
guess = [[1.,      0.      ], [0.,       1.     ]]  <-- 2x2 identity matrix
guess = [[4.,      1.      ], [1.5,      2.5    ]]
guess = [[2.85294, 0.558824], [0.838235, 2.01471]]
guess = [[2.60335, 0.449328], [0.673992, 1.92936]]
guess = [[2.58956, 0.443035], [0.664553, 1.92501]]
guess = [[2.58952, 0.443016], [0.664523, 1.92499]]
guess = [[2.58952, 0.443016], [0.664523, 1.92499]]

After only a few iterations, the series converges to within 1e-9.  After a while, it grows unstable as rounding errors add up, but the initial stability is demonstrated, which is sufficient.

Task

Your job is to find a square matrix M, populated by the integers 1 through 9, which, when given an initial guess of an identity matrix of the proper size, converges successfully.  Matrices should be submitted as comma-delimited text (or attached text files, if they are too large), with either brackets or newlines separating subsequent rows.

Rules

Even though the matrix M and starting guess use integers (mainly for display convenience), all arithmetic should be conducted using double-precision floating point.  Integer-specific operators (such as 3/2 evaluating to 1) are prohibited.

Divide-by-zero errors, singular matrices, and over/underflows cannot be used to coerce a sequence into 'converging'.  The values must be proper floating-point numbers at all times to be considered to have converged.

The algorithm is considered to have converged if an iteration produces no change larger than 1e-9, in any individual cell.

You may use external mathematics libraries for matrix inversion (no need to reinvent the wheel).

Win Condition

The winner is the largest submitted valid Babylonian matrix made of integers 1-9, after one week.  You must also submit the code you used to find the matrix.

We produce such a matrix of any dimension n. It is simply a matrix of all 1's except 2's on the diagonal.

r = range(n)
M = [[1 + (i==j) for i in r] for j in r]

Example:

n=5
M=[[2 1 1 1 1]
   [1 2 1 1 1]
   [1 1 2 1 1]
   [1 1 1 2 1]
   [1 1 1 1 2]]

 #Within 10 steps, the procedure converges to the matrix's square root
  [[ 1.28989795  0.28989795  0.28989795  0.28989795  0.28989795]
   [ 0.28989795  1.28989795  0.28989795  0.28989795  0.28989795]
   [ 0.28989795  0.28989795  1.28989795  0.28989795  0.28989795]
   [ 0.28989795  0.28989795  0.28989795  1.28989795  0.28989795]
   [ 0.28989795  0.28989795  0.28989795  0.28989795  1.28989795]]

In general, the procedure converges for matrices with positive real eigenvalues. This is because if we work in the basis of eigenvectors of the original matrix, it and all its iterates are diagonal matrices, and we can view the procedure as applying the Babylonian method to each individual diagonal entry. The starting matrix is the still the identity in this basis.

Since the Babylonian method converges only if the original value was positive, the matrix version converges when every eigenvalue is real and positive. I'm not sure what happens for complex eigenvalues.

I constructed the given matrix to have positive eigenvalues as follows. First, start with the matrix of all ones, which is rank-1, and so has a single eigenvalue (of n) and all others 0. Then, add the identity, which shifts the eigenvalues up by 1 to get (n+1,1,1,...,1). Iterating makes the eigenvalues converge to (sqrt(n+1),1,1,...,1). Note that the 1's are unchanged by each iteration.


Yes, of course I'm an adult! I think we've all done this as a kid: some websites require a minimum age of 18, so we just subtract a few years from the year of birth and voilà, we 'are' 18+.
In addition, for most rides at amusement parks the minimum height to enter is 1.40 meters (here in The Netherlands it as at least). Of course this can be cheated less easily than age, but you could wear shoes with thick heels, put your hair up, wear a hat, stand on your toes, etc.
Input:
Your program/function accepts a positive integer or decimal.
Output:

Is the input an integer >= 18? Simply print the input.
Is the input an integer 0-17? Print 18.
Is the input a decimal >= 1.4? Simply print the input.
Is the input a decimal 0.0-1.4? Print 1.4.

Challenge rules:

Assume the input will always be in the range of 0-122 (oldest woman ever was 122) or 0.0-2.72 (tallest man ever was 2.72).
You are allowed to take the input as a String, object, or anything else you prefer.
The decimal inputs will never have more than three decimal places after the decimal point.
2 or 2. both aren't valid outputs for 2.0. You are free to output 2.00 or 2.000 instead of 2.0 however.
Just like the input the output will never have more than three decimal places after the point.

General rules:

This is code-golf, so shortest answer in bytes wins.
Don't let code-golf languages discourage you from posting answers with non-codegolfing languages. Try to come up with an as short as possible answer for 'any' programming language.
Standard rules apply for your answer, so you are allowed to use STDIN/STDOUT, functions/method with the proper parameters, full programs. Your call.
Default Loopholes are forbidden.
If possible, please add a link with a test for your code.
Also, please add an explanation if necessary.

Test cases:
0      ->  18
1      ->  18
2      ->  18
12     ->  18
18     ->  18
43     ->  43
115    ->  115
122    ->  122

0.0    ->  1.4
1.04   ->  1.4
1.225  ->  1.4
1.399  ->  1.4
1.4    ->  1.4
1.74   ->  1.74
2.0    ->  2.0
2.72   ->  2.72

Python 2.7, 34 bytes

lambda x:max(x,[18,1.4]['.'in`x`])


Speak digits from 0 to 9 aloud Inspired by this question from electronics.SE, here's a challenge for you:

Write a program or subroutine that takes in a sequence of decimal digits (0 to 9) and speaks them aloud, without using an existing speech synthesis tool.

Input:

You may ask for the input digits to be provided in any reasonable format, e.g. as a string of ASCII digits, an array of integers, a BCD-encoded number, etc.  If your solution is an executable program, you may take the input as a command line parameter, read it from standard input, or obtain it in any other reasonable manner.

Your program must be able to speak at least eight digits per invocation.  You may assume that the first digit is not zero, unless it is the only digit.

Output:

Your program may either speak the numbers directly using an audio device, or it may output a playable sound file.  The output file, if any, may be in any standard audio format, or it may consist of raw sample data.  If you output raw sample data, please note the appropriate parameters for playback (sample rate, bits per sample, endianness, signed/unsigned, # of channels).  Formats supported by aplay are preferred.

You are free to decide the details on how the numbers will be spoken, but your output should consist of English language digits spoken in a manner understandable to a typical English speaker, and it should be clear enough for the listener to be able to accurately transcribe a spoken eight-digit random number.  No, just beeping n times doesn't count.  Don't forget to include pauses between the digits.

Scoring:

Standard code-golf scoring rules apply: Your score is the length of your code in bytes or, if your code is written in Unicode text, in Unicode characters.  Lowest score wins.  Any language goes.

As the original question on electronics.SE was about embedded programming, I felt it would be appropriate to toss a bone to authors using low-level languages: if your solution is written in a compiled language, you may choose to count the length of the compiled executable file in bytes as your score.  (Yes, precompiled bytecode, such as a Java .class file, is OK too.)  If you choose to make use of this option, please include a copy of the compiled executable in your answer (e.g. as a hex dump) along with your source code and the compiler version and options you used to generate it.

An honorable mention, along with a +50 rep bounty, will be granted to the first answer that also meets the criteria of the original question, i.e. is capable of running on an embedded MCU with 4 kb of flash and 1 kb of SRAM.

Restrictions:

You may not make use of any files or network resources that are not part of your chosen language's standard runtime environment, unless you count the length of said files or resources as part of your score.  (This is to disallow e.g. loading audio samples from the web.)

You may also not use any pre-existing speech synthesis tools or libraries or compilations of audio data (unless you also count their size as part of your score), even if they're included in your chosen language's standard runtime environment.

ruby - 3710 = 90 characters code + 3620 bytes data
require'zlib'
$><<$*[0].chars.map{|x|Zlib::Inflate.inflate File.open(x).read}.join(?0*5e3)

input: a single command line argument, the number to read
output: raw sound data, PCM 8bit/8kHz
This can read any input string, as long as

it only contains characters that are valid file names. for only four chars, you can enlarge that set to all characters.
you have the neccessary files.
why oh you space dee oh en apostrophe tee space em i en dee space tee aitch i es period

5e3 encodes the pause between two words. Here, 5ksamples ~= 0.6s. Tweak as desired.
Now, the tricky part is to get the sample files in 4K and yet be able to decompress them easily and in sufficient quality. Here is how I got them:

Take a Text-to-speech engine able to produce sound files. Wikipedia has one.
Feed it a text containing all digits, ideally close together. I used http://en.wikipedia.org/wiki/Base_13
Downsample.
Cut out each part in a sound editor.
Save as a raw file.
Decimate each sample (discard low-order bits).
Deflate.

Now, one has to choose a sample rate and decimation amount. Too much, and the sound won't be understandable. Too little, and you don't fit. I have settled for 8kHz/3b. There they are: https://github.com/honnza/drops/raw/master/digits.zip

8KHz * 4b/sample and higher quality - too big
8KHz * 3b/sample - low quality, but it fits into 4K
8KHz * 2b/sample - kch kchhhhhhhhh [not understandable]
2KHz * 8b/sample - too big
2KHz * 3b/sample - kch kchhhhhhhhh
1KHz * 8b/sample - kch kchhhhhhhhh

Here's the decimation script:
require'zlib'
Dir.glob "*.raw" do |fname|
  File.open fname[/\d/], "wb" do |out|
    File.open fname do |input|
      bytes = input.bytes.to_a
      bytes.map! {|x|x&0xE0}
      dfl = Zlib::Deflate.deflate(bytes.pack("C*"),9)
      dfl.each_byte do |byte|
        out.print byte.chr
      end
      puts "done #{fname}: #{dfl.size}"
    end
  end
end

As for the original challenge: there are 476 bytes of space for code and the file table. This might be slightly too much depending on how tiny we can get with a DEFLATE library. If neccessary, we can cut a few corners here and there by cropping the audio samples a bit more aggresively. [fo:r] or [o:] doesn't really matter but it saves bytes. I have been somewhat benevolent when cropping the numbers. Also, a different decimation scheme or sacrificing some decimation for downsampling might help - I'll toy with these later. Also, dropping the DEFLATE headers might save a tiny amount of space.
Concatenating sound samples is quite easy, but 4K is a little cramped. If you are not bound by 4k space, I suggest less decimation. 4 bits per sample actually fares quite well and is only slightly bigger.


Counting up and down while doubling the increments Input:

A non-empty list / vector where each element holds a value/character, indicating if you'll count up  or down. I'll use 1 and -1, but you may choose whatever you like. You can only use two values, you can't use 1,2,3... and -1,-2,-3..., for up and down respectively.

Challenge:

You'll use the numbers in the geometric series 1, 2, 4, 8, 16, 32.... Every time you start counting up or down, you'll count in increments of 1, then 2, then 4 and so on. If you change and start counting the other way then you'll subtract 1, then 2, then 4 and so on. The output shall be the number you get to in the end.

Examples:

In the example below, the first line is the input, the second line is the numbers you're counting up/down, the third line is the cumulative sum, and the last line is the output.

Example 1:

1   1   1   1   1   1   1   1   1   1
1   2   4   8   16  32  64  128 256 512
1   3   7   15  31  63  127 255 511 1023
1023

Example 2:

1   1   1   1   1   1   -1  -1  -1  -1  1   1   1
1   2   4   8   16  32  -1  -2  -4  -8  1   2   4
1   3   7   15  31  63  62  60  56  48  49  51  55
55

As you can see, the first 1 or -1 "resets" the value we're counting, and consecutive sequences of 1 or -1 means doubling the value.

Example 3:

-1  -1  1   1   -1  -1  -1
-1  -2  1   2   -1  -2  -4
-1  -3  -2  0   -1  -3  -7
-7

Some additional test cases to account for some potential corner cases.

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

1
1
-------
-1
-1
-------
-1   1  -1   1  -1   1  -1   1  -1   1  -1   1
0

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

Husk, 3 bytes

ṁḋg

Try it online!

Explanation

ṁḋg
  g  Group equal adjacent elements,
ṁ    take sum of
 ḋ   base-2 decoding of each group.


Draw dice results in ASCII Show the random result of a dice toss if done with a cube shaped die, in ASCII.

$ dice

should result in one of

-----
|   |
| o |
|   |
-----

-----
|o  |
|   |
|  o|
-----

-----
|o  |
| o |
|  o|
-----

-----
|o o|
|   |
|o o|
-----

-----
|o o|
| o |
|o o|
-----

-----
|o o|
|o o|
|o o|
-----


Contest: fastest way to sort a big array of Gaussian-distributed data Following the interest in this question, I thought it would be interesting to make answers a bit more objective and quantitative by proposing a contest.

The idea is simple: I have generated a binary file containing 50 million gaussian-distributed doubles (average: 0, stdev 1). The goal is to make a program that will sort these in memory as fast as possible. A very simple reference implementation in python takes 1m4s to complete. How low can we go?

The rules are as follows: answer with a program that opens the file "gaussian.dat" and sorts the numbers in memory (no need to output them), and instructions for building and running the program. The program must be able to work on my Arch Linux machine (meaning you can use any programming language or library that is easily installable on this system).

The program must be reasonably readable, so that I can make sure it is safe to launch (no assembler-only solution, please!).

I will run the answers on my machine (quad core, 4 Gigabytes of RAM). The fastest solution will get the accepted answer and a 100 points bounty :)

The program used to generate the numbers:

#!/usr/bin/env python
import random
from array import array
from sys import argv
count=int(argv[1])
a=array('d',(random.gauss(0,1) for x in xrange(count)))
f=open("gaussian.dat","wb")
a.tofile(f)

The simple reference implementation:

#!/usr/bin/env python
from array import array
from sys import argv
count=int(argv[1])
a=array('d')
a.fromfile(open("gaussian.dat"),count)
print "sorting..."
b=sorted(a)

EDIT: only 4 GB of RAM, sorry

EDIT#2: Note that the point of the contest is to see if we can use prior information about the data. it is not supposed to be a pissing match between different programming language implementations!

Here is a solution in C++ which first partitions the numbers into buckets with same expected number of elements and then sorts each bucket separately. It precomputes a table of the cumulative distribution function based on some formulas from Wikipedia and then interpolates values from this table to get a fast approximation.

Several steps run in multiple threads to make use of the four cores.

#include <cstdlib>
#include <math.h>
#include <stdio.h>
#include <algorithm>

#include <tbb/parallel_for.h>

using namespace std;

typedef unsigned long long ull;

double signum(double x) {
    return (x<0) ? -1 : (x>0) ? 1 : 0;
}

const double fourOverPI = 4 / M_PI;

double erf(double x) {
    double a = 0.147;
    double x2 = x*x;
    double ax2 = a*x2;
    double f1 = -x2 * (fourOverPI + ax2) / (1 + ax2);
    double s1 = sqrt(1 - exp(f1));
    return signum(x) * s1;
}

const double sqrt2 = sqrt(2);

double cdf(double x) {
    return 0.5 + erf(x / sqrt2) / 2;
}

const int cdfTableSize = 200;
const double cdfTableLimit = 5;
double* computeCdfTable(int size) {
    double* res = new double[size];
    for (int i = 0; i < size; ++i) {
        res[i] = cdf(cdfTableLimit * i / (size - 1));
    }
    return res;
}
const double* const cdfTable = computeCdfTable(cdfTableSize);

double cdfApprox(double x) {
    bool negative = (x < 0);
    if (negative) x = -x;
    if (x > cdfTableLimit) return negative ? cdf(-x) : cdf(x);
    double p = (cdfTableSize - 1) * x / cdfTableLimit;
    int below = (int) p;
    if (p == below) return negative ? -cdfTable[below] : cdfTable[below];
    int above = below + 1;
    double ret = cdfTable[below] +
            (cdfTable[above] - cdfTable[below])*(p - below);
    return negative ? 1 - ret : ret;
}

void print(const double* arr, int len) {
    for (int i = 0; i < len; ++i) {
        printf("%e; ", arr[i]);
    }
    puts("");
}

void print(const int* arr, int len) {
    for (int i = 0; i < len; ++i) {
        printf("%d; ", arr[i]);
    }
    puts("");
}

void fillBuckets(int N, int bucketCount,
        double* data, int* partitions,
        double* buckets, int* offsets) {
    for (int i = 0; i < N; ++i) {
        ++offsets[partitions[i]];
    }

    int offset = 0;
    for (int i = 0; i < bucketCount; ++i) {
        int t = offsets[i];
        offsets[i] = offset;
        offset += t;
    }
    offsets[bucketCount] = N;

    int next[bucketCount];
    memset(next, 0, sizeof(next));
    for (int i = 0; i < N; ++i) {
        int p = partitions[i];
        int j = offsets[p] + next[p];
        ++next[p];
        buckets[j] = data[i];
    }
}

class Sorter {
public:
    Sorter(double* data, int* offsets) {
        this->data = data;
        this->offsets = offsets;
    }

    static void radixSort(double* arr, int len) {
        ull* encoded = (ull*)arr;
        for (int i = 0; i < len; ++i) {
            ull n = encoded[i];
            if (n & signBit) {
                n ^= allBits;
            } else {
                n ^= signBit;
            }
            encoded[i] = n;
        }

        const int step = 11;
        const ull mask = (1ull << step) - 1;
        int offsets[8][1ull << step];
        memset(offsets, 0, sizeof(offsets));

        for (int i = 0; i < len; ++i) {
            for (int b = 0, j = 0; b < 64; b += step, ++j) {
                int p = (encoded[i] >> b) & mask;
                ++offsets[j][p];
            }
        }

        int sum[8] = {0};
        for (int i = 0; i <= mask; i++) {
            for (int b = 0, j = 0; b < 64; b += step, ++j) {
                int t = sum[j] + offsets[j][i];
                offsets[j][i] = sum[j];
                sum[j] = t;
            }
        }

        ull* copy = new ull[len];
        ull* current = encoded;
        for (int b = 0, j = 0; b < 64; b += step, ++j) {
            for (int i = 0; i < len; ++i) {
                int p = (current[i] >> b) & mask;
                copy[offsets[j][p]] = current[i];
                ++offsets[j][p];
            }

            ull* t = copy;
            copy = current;
            current = t;
        }

        if (current != encoded) {
            for (int i = 0; i < len; ++i) {
                encoded[i] = current[i];
            }
        }

        for (int i = 0; i < len; ++i) {
            ull n = encoded[i];
            if (n & signBit) {
                n ^= signBit;
            } else {
                n ^= allBits;
            }
            encoded[i] = n;
        }
    }

    void operator() (tbb::blocked_range<int>& range) const {
        for (int i = range.begin(); i < range.end(); ++i) {
            double* begin = &data[offsets[i]];
            double* end = &data[offsets[i+1]];
            //std::sort(begin, end);
            radixSort(begin, end-begin);
        }
    }

private:
    double* data;
    int* offsets;
    static const ull signBit = 1ull << 63;
    static const ull allBits = ~0ull;
};

void sortBuckets(int bucketCount, double* data, int* offsets) {
    Sorter sorter(data, offsets);
    tbb::blocked_range<int> range(0, bucketCount);
    tbb::parallel_for(range, sorter);
    //sorter(range);
}

class Partitioner {
public:
    Partitioner(int bucketCount, double* data, int* partitions) {
        this->data = data;
        this->partitions = partitions;
        this->bucketCount = bucketCount;
    }

    void operator() (tbb::blocked_range<int>& range) const {
        for (int i = range.begin(); i < range.end(); ++i) {
            double d = data[i];
            int p = (int) (cdfApprox(d) * bucketCount);
            partitions[i] = p;
        }
    }

private:
    double* data;
    int* partitions;
    int bucketCount;
};

const int bucketCount = 512;
int offsets[bucketCount + 1];

int main(int argc, char** argv) {
    if (argc != 2) {
        printf("Usage: %s N\n N = the size of the input\n", argv[0]);
        return 1;
    }

    puts("initializing...");
    int N = atoi(argv[1]);
    double* data = new double[N];
    double* buckets = new double[N];
    memset(offsets, 0, sizeof(offsets));
    int* partitions = new int[N];

    puts("loading data...");
    FILE* fp = fopen("gaussian.dat", "rb");
    if (fp == 0 || fread(data, sizeof(*data), N, fp) != N) {
        puts("Error reading data");
        return 1;
    }
    //print(data, N);

    puts("assigning partitions...");
    tbb::parallel_for(tbb::blocked_range<int>(0, N),
            Partitioner(bucketCount, data, partitions));

    puts("filling buckets...");
    fillBuckets(N, bucketCount, data, partitions, buckets, offsets);
    data = buckets;

    puts("sorting buckets...");
    sortBuckets(bucketCount, data, offsets);

    puts("done.");

    /*
    for (int i = 0; i < N-1; ++i) {
        if (data[i] > data[i+1]) {
            printf("error at %d: %e > %e\n", i, data[i], data[i+1]);
        }
    }
    */

    //print(data, N);

    return 0;
}

To compile and run it, use this command:

g++ -O3 -ltbb -o gsort gsort.cpp && time ./gsort 50000000

EDIT: All buckets are now placed into the same array to remove the need to copy the buckets back into the array. Also the size of the table with precomputed values was reduced, because the values are accurate enough. Still, if I change the number of buckets above 256, the program takes longer to run than with that number of buckets.

EDIT: The same algorithm, different programming language. I used C++ instead of Java and the running time reduced from ~3.2s to ~2.35s on my machine. The optimal number of buckets is still around 256 (again, on my computer).

By the way, tbb really is awesome.

EDIT: I was inspired by Alexandru's great solution and replaced the std::sort in the last phase by a modified version of his radix sort. I did use a different method to deal with the positive/negative numbers, even though it needs more passes through the array. I also decided to sort the array exactly and remove the insertion sort. I will later spend some time testing how do these changes influence performance and possibly revert them. However, by using radix sort, the time decreased from ~2.35s to ~1.63s.


Husk, 8 bytes

ḟṠ€ȯmΠṖṘ

Extremely slow.
Try it online!

Explanation

ḟṠ€ȯmΠṖṘ  Implicit inputs, say L=[3,4] and n=5.
ḟ         Find the lowest integer k≥n that satisfies:
       Ṙ   Replicate L by k: [3,3,3,3,3,4,4,4,4,4]
      Ṗ    Powerset: [[],[3],[4],..,[3,3,3,3,3,4,4,4,4,4]]
    mΠ     Product of each: [1,3,4,..,248832]
 Ṡ€ȯ       k is in this list.


Is it a Satisfying Number? inspired by this chat conversation

A satisfying number is a number whose decimal representation is of the form abx, with the following properties:

x is the longest trailing repeating suffix, or the last digit if there is no repetition at the end (123333 -> 3333, 545656 -> 5656, 123 -> 3)
b is the single digit prior to x (123333 -> 2, 55545656 -> 4)
a is the remaining prefix (123333 -> 1, 55545656 -> 555)
a == c**b (** denotes exponentation), where c is the number of repetitions of the smallest repeating portion of x (1623333 -> 4 (3 3 3 3, not 33 33))

For example, 8300 is a satisfying number with a = 8, b = 3, c = 2, and x = 00. 24651 is not a satisfying number, because x = 1, b = 5, a = 246, and there is no integer c that satisfies c^5 = 246. 1222 is also not a satisfying number, because with x = 222 and b = 1, there are no remaining digits for a.

Given a positive integer n >= 100, output whether or not n is a satisfying number.

Examples

8300: True (a=8, b=3, c=2, x=00)
24651: False
1222: False
92555: True (a=9, b=2, c=3, x=555)
64633: True (a=64, b=6, c=2, x=33)
512944: True (a=512, b=9, c=2, x=44)
123: True (a=1, b=2, c=1, x=3)
822809: False
376664: False
723799: False
1234: False
34330000000: True (a=343, b=3, c=7, x=0000000)
92313131: True (a=9, b=2, c=3, x=313131)
16424442444: True (a=16, b=4, c=2, x=24442444)

Jelly, 26 bytes

feels too long

DŒṖṖEÐƤḄ$ÐṀLÐṂṪµḢ*@0¦LµṪ⁼Ḍ

A monadic link taking an integer and returning 1 if the input is satisfying and 0 if not.

Try it online! or see a test-suite

How?

DŒṖṖEÐƤḄ$ÐṀLÐṂṪµḢ*@0¦LµṪ⁼Ḍ - Link: integer, n    e.g. 8300
D                          - to decimal list          [8,3,0,0]
 ŒṖ                        - all partitions           [[[8],[3],[0],[0]],[[8],[3],[0,0]],[[8],[3,0],[0]],[[8],[3,0,0]],[[8,3],[0],[0]],[[8,3],[0,0]],[[8,3,0],[0]],[[8,3,0,0]]]
   Ṗ                       - pop (the "no tail" one)  [[[8],[3],[0],[0]],[[8],[3],[0,0]],[[8],[3,0],[0]],[[8],[3,0,0]],[[8,3],[0],[0]],[[8,3],[0,0]],[[8,3,0],[0]]]
         ÐṀ                - keep maximal under the operation: e.g. for [[8,3],[0],[0]]
        $                  -   last two links as a monad:
     ÐƤ                    -     for suffixes:   i.e. [[[8,3],[0],[0]],[[0],[0]],[[0]]]
    E                      -       all equal?         [0              ,1        ,1]
       Ḅ                   -     convert from binary  3
                           -          ...which yields [[[8],[3],[0],[0]],[[8,3],[0],[0]]]
            ÐṂ             - keep minimal under the operation:
           L               -   length
                           -          ...which yields [[[8,3],[0],[0]]]
              Ṫ            - tail (rightmost)         [[8,3],[0],[0]]
               µ           - monadic chain separation
                Ḣ          - yield head and modify    [8,3]   ...leaving [[0],[0]]
                     L     - length (of modified)     2
                    ¦      - sparse application       (to the [8,3])
                   0       -   ...to index: 0         (to the rightmost digit, the 3)
                 *@        -   power (sw@p args)      [8,8]  ([8, 3*@2] = [8, 2*3] = [8,8])
                      µ    - monadic chain separation
                       Ṫ   - yield tail and modify    8   ...leaving [8]
                         Ḍ - from decimal (modified)  8
                        ⁼  - equal?                   1


Unix timestamp to datetime string Given a unix timestamp as an input, give a datetime string, in a format like so: "YYMMDD.HHmm"

Rules

The input is a number (integer) of a millisecond-precise UNIX epoch time (milliseconds since 1970 January 1st 00:00:00.000 UTC).
The values must be padded with zeroes if they are 1 character instead of 2. (e.g.: for "DD", "1" is not acceptable, but "01" is.)
The output must be a single string. No arrays.
Leap second handling doesn't matter.
Shortest wins.

Good luck!

Example

Input: 1547233866744
Output: 190111.1911

JavaScript (ES6), 65 bytes

n=>'101010.1010'.replace(i=/\d/g,x=>new Date(n).toJSON()[i=x-~i])

Try it online!

How?

We initialize the pointer \$i\$ to a non-numeric value (coerced to \$0\$) and then add alternately \$2\$ and \$1\$ to it to pick the relevant characters from the ISO-8601 conversion of the input timestamp.

yyyy-mm-ddThh:mm:ss.sssZ
  ^^ ^^ ^^ ^^ ^^

JavaScript (ES6), 66 bytes

n=>'235689.BCEF'.replace(/\w/g,x=>new Date(n).toJSON()[+`0x${x}`])

Try it online!

How?

Once the input timestamp is converted in ISO-8601 format, all required characters can be accessed with a single hexadecimal digit.

yyyy-mm-ddThh:mm:ss.sssZ
  ↓↓ ↓↓ ↓↓ ↓↓ ↓↓
0123456789ABCDEF


Executable haiku that outputs a haiku Puzzle:

Write a short, three-line program which:

has 5/7/5 syllables per line when read aloud
outputs a haiku when run.

An example of a program having the correct structure, but non-haiku output, is (Python):

>>> for x in range(3):
...     print "EXTERMINATE HUMANS"
... # I am a Dalek.
...
EXTERMINATE HUMANS
EXTERMINATE HUMANS
EXTERMINATE HUMANS

(The comment is a bit of a cop-out.)

This reads aloud as:

  for x in range three

  print EXTERMINATE HUMANS!

  I am a Dalek.

Any language is acceptable. For the purposes of reading aloud, symbols like !@#$%^&*()_+ can be ignored if you want, or pronounced aloud, admitting something like Waka Waka Bang Splat. (I'm sure there will be a Perl entry like !***(!:, )(*@@@#, )_(*)!.)

Extra points if either the code or the output is especially funny, or especially zen.

Edit: If your language requires boilerplate before it can do anything interesting (#include <iostream>?) then I'm happy to ignore the boilerplate.

I've accepted Paul Richter's Common Lisp haiku on the grounds that it made me laugh for a good five minutes.

Honorable mention for Timwi's creative rule-bending (compiler output?!) and for the extremely memorable line "Static void. I long for you."

  Now this question ends;

  Many more haikus await.

  Continue posting!

C#

Program:

#warning Lonesome
class _{
    static void Eye(long forYou='
        ){ /* My program ends here. */ ;}}

Read:

Warning: Lonesome class.
Static void. I long for you.
My program ends here.

Compiler output:

#warning: 'Lonesome'        (read: hash warning lonesome)
Empty character literal     (read: empty character lit’ral)
Newline in constant


Count the changes in an array Your task today is to write a program or function that takes an array of integers, and counts the number of times, reading it left to right, that the value changes. This is easier to show with an example: [1 1 1 2 2 5 5 5 5 17 3] => [1 1 1 **2** 2 **5** 5 5 5 **17** **3**] => 4

Test case:

Input           |   Output
[]              |   0
[0]             |   0
[0 1]           |   1
[0 0]           |   0
[1 2 3 17]      |   3
[1 1 1 2 2 3]   |   2
[-3 3 3 -3 0]   |   3

This is code-golf, fewest bytes wins!

MATL, 2 bytes
dz

Try it online! Or verify all test cases.
Explanation
     % Implicit input
d    % Consecutive differences
z    % Number of nonzeros
     % Implicit display


Music: What's the name of this chord? This is the reverse of Music: what's in this chord?, which is to print the notes in a given chord. This time the input is a list of notes in a chord, and your task is to output which chord it is.

Your program should support the following triadic chords. Examples are given with root C. Chords with other roots are the same chords with all notes rotated so C will become that root note, e.g. Dmaj consists of D, F# and A.

        C C#D D#E F F#G G#A A#B
          Db  Eb    Gb  Ab  Bb
Cmaj    C       E     G
Cm      C     D#      G
Caug    C       E       G#
Cdim    C     D#    F#
Csus4   C         F   G
Csus2   C   D         G

Note that Caug is the same as Eaug and G#aug, and Csus4 is the same as Fsus2. You can output either one but there is a bonus if you output them all.

And the seventh chords for the bonus are listed in the follow table:

        C C#D D#E F F#G G#A A#B
          Db  Eb    Gb  Ab  Bb
C7      C       E     G     A#
Cm7     C     D#      G     A#
Cmmaj7  C     D#      G       B
Cmaj7   C       E     G       B
Caug7   C       E       G#  A#
Cdim7   C     D#    F#    A

Rules

You can write either a complete program or a function.
The input is a list of notes, separated by a space or another convenient character. It can also be an array of strings (if it take input from function argument) or the string representation of such array.
Input doesn't have to be in specific order.
There may be duplicated notes in the input. They must be treated the same way as there is only one of them.
The output is the name of the chord. In case it will output multiple names, the same rule for input applies.
If the input isn't a supported chord, you should print the notes as-is. Your program can also support other chords not listed in the tables above (which is valid but has no bonus).
You can use other notations listed in the Wikipedia article. But if you choose C for C major, you should add a human readable prefix in either case to distinguish a chord with a single note.
You cannot use built-in functions for this task (if there is any).
This is code-golf. Shortest code in bytes wins.

Examples

Input: C D# G Output: Cm.
Input: C Eb G Output: Cm.
Input: C Eb F# Output: Cdim.
Input: F A C# Output: Faug, Aaug, C#aug, Dbaug or Faug Aaug C#aug, Faug Aaug Dbaug in any order.
Input: F D F F F F A A F Output: Dm.
Input: C D Output: C D.

Bonuses

-30 if it prints them all if there are more than one interpretations (for aug, sus4/sus2 and dim7).
-70 if it also supports seventh chords.
-200 if it accepts MIDI input and prints each chord it have received. Note that the notes doesn't have to begin or end at the same time. You decide what happens in the intermediate states (as long as it doesn't crash or stop working). You may assume there are no notes in percussion channels (or there is only one channel if that's convenient). It is recommended to also provide a text (or array) version for testing, especially if it is platform-dependent.

Pyth 190 character - 30 - 70 = 90

=Q{cQdL+x"C D EF G A B"hb&tlbt%hx" #b"eb3FZQJx[188 212 199 213 200 224 2555 2411 2412 2556 2567 2398)u+*G12hHSm%-dyZ12mykQ0IhJ+Z@c"sus2 maj dim aug m sus4 7 m7 mmaj7 maj7 aug7 dim7"dJ=T0;ITQ

Not really happy with it. Used hard-coded chords.

Usage:

Try it here: Pyth Compiler/Executor. Disable debug mode and use "C D# G" as input.

Explanation:

First some preparation:

=Q{cQd
   cQd  split chord into notes "C D# G" -> ["C", "D#", "G"]
  {     set (eliminate duplicates)
=Q      Q = ...

Then a function that converts notes into integer

L+x"C D EF G A B"hb&tlbt%hx" #b"eb3
defines a function g(b),
  returns the sum of
     index of "D" in "C D EF G A B"
     and the index of "#" in " #b"
       (if b than use -1 instead of 2)

Then for each note, shift the coord and look it up in a table

FZQJx[188 ...)u+*G12hHSm%-dyZ12mykQ0IhJ+Z@c"sus2 ..."dJ=T0;ITQ
               implicit T=10
FZQ            for note Z in chord Q:
   mykQ         map each note of Q to it's integer value
   m%-dyZ12     shift it by the integer value of Z modulo 12
   S            sort it
   u+*G12hH 0   convert it to an integer in base 12
   x[188 ...)   look it up in the list (-1 if not in list)
   J            and store the value in J

   IhJ               if J>=0:
   +Z@c"sus2 ..."dJ   print the note Z and the chord in the list
=T0                   and set T=0
;            end loop
ITQ          if T:print chord (chord not in list)


Can you connect the dots? This challenge is based off of Flow Free.  An online version can be found here: http://www.moh97.us/

You will be given a puzzle, and you must return 1 if the puzzle is solvable, or 0 if it is not.

To solve a puzzle, the player must create a path to connect each pair of numbers using every empty square exactly once.

You are passed in the dimensions of the square, and then the x,y,c (where c is a number representing the color) of each dot.  For example:

If 5,5 0,0,0 3,0,1 1,1,2 1,2,2 4,2,1 4,4,0 was passed to you, it would represent:

0..1.
.2...
.2..1
....0

And should return 1.

Here are some more test problems:

5,2 2,0,1 0,1,2 4,1,2 represents:

..1..
2...2

and is not solvable because there is only 1 1.

4,2 0,0,0 3,0,0 0,1,0 3,1,0 represents:

0..0
0..0

and is not solvable because it includes more than 2 0s.

8,6 0,0,1 7,5,1 represents:

1.......
........
........
........
........
.......1

and is not solvable (as you can't use every square).

2,5 0,0,1 2,0,6 4,0,6 0,1,4 3,1,4 4,1,1 represents:

1.6.6
4..41

and is not solvable because you cannot connect the 1s.

6,3 1,0,4 5,0,1 0,1,4 1,1,3 5,1,3 0,2,2 3,2,2 5,2,1 represents:

.4...1
43...3
2..2.1

and is not solvable because you cannot connect the 1s (or the 3s), as the two paths must necessarily cross.

5,2 0,0,1 3,0,1 0,1,3 4,1,1 represents:

1..1.
3...3

and is not solvable because you cannot use all of the squares in building a path.

2,2 0,0,0 1,1,0 represents:

1.
.1

and is not solvable because you can't use all of the squares here either

Here are some more tests:

5,5 0,3,0 0,4,1 1,2,2 1,3,1 2,0,0 3,0,4 3,1,2 3,3,5 3,4,4 4,4,5 should return 1

13,13 1,1,0 9,1,1 10,1,2 11,1,3 1,2,4 2,2,5 5,2,6 7,2,7 3,3,0 5,4,6 6,4,1 9,6,3 4,7,8 5,8,9 12,8,8 11,9,10 2,10,4 4,10,2 9,10,5 11,10,7 1,11,9 12,12,10 should return 1

7,7 0,0,0 0,1,1 1,1,2 2,1,3 4,2,4 0,3,1 5,3,3 0,4,4 2,4,5 5,4,2 0,5,0 1,5,5 3,5,6 3,7,6 should return 0

This is a code golf, and the standard rules apply.

Haskell

import Data.List.Split
import qualified Data.Sequence as Q
import Data.List
import Control.Monad

data A a = S a | E a | P a | X deriving Eq

sc = foldr1 (Q.><)
sp b x y p = Q.update y (Q.update x p $ b `Q.index` y) b
dt b c | S c `elem` sc b = E c
       | otherwise = S c
ad b [x, y, c] = sp b x y (dt b c)

ep b [x, y, c] = do
  let nps = filter ob [(x+1, y), (x-1, y), (x, y+1), (x, y-1)]
      ns = map gp nps
  [b | E c `elem` ns] ++ do
    (x', y') <- filter ((== X) . gp) nps
    ep (sp b x' y' (P c)) [x', y', c]
  where ob (u, v) = 0 <= u && u < length (b `Q.index` 0) && 0 <= v && v < length b
        gp (u, v) = b `Q.index` v `Q.index` u

rd i = let [c, r] : ps = (map read . splitOn ",") <$> words i :: [[Int]]
           e = Q.replicate r $ Q.replicate c X
           cs = map last ps
           ss = nubBy (\[_,_,c1] [_,_,c2] -> c1 == c2) ps
           b = foldl ad e ps
           bs = foldM ep b ss
       in if even (length cs) && length ss == length cs `div` 2 &&
             (all (\[j,k] -> j==k) . chunksOf 2 . sort $ cs) &&
             any (null . Q.elemIndicesL X . sc) bs
           then 1
           else 0

main = rd <$> getContents >>= print

Key

sc: Seq concat
sp: set position
dt: dot type (ie, start or end of line)
ad: add dot
ep: extend path
rd: run dots (primary pure algorithm)


Doubled-letter steganography Steganography hides a given message inside a given carrier, producing a package that does not look suspicious. For this challenge, you will write a program that takes an ASCII message and an ASCII carrier as input, and return or print a package that is identical to the carrier except characters corresponding to the message are doubled, in the same order that they appear in the message.

Rules:

If the carrier already contains sequences of the same character more than once, and they are not used to encode a character of the message, the program will reduce them to a single character.
If the carrier does not contain the message characters in the right order, the program may return nothing, the carrier itself, or an error.
You may assume that the message and carrier are non-empty ASCII strings.
Capitalization matters: A is not equivalent to a.
When more than one package is valid, your program may output any or all of them.
Space is a character like any other character.

Test cases:

Message      Carrier              Package
"hi"         "has it arrived?"    "hhas iit arived?" OR "hhas it ariived?"
"sir"        "has it arrived?"    "hass iit arrived?"
"foo"        "has it arrived?"    "" OR "has it arrived?" OR an error.
"Car"        "Cats are cool."     "CCaats arre col."
"car"        "Cats are cool."     "" OR "Cats are cool." OR an error.
"Couch"      "Couch"              "CCoouucchh"
"oo"         "oooooooooo"         "oooo"
"o o"        "oooo oooa"          "oo  ooa"

This is code golf, so fewest bytes wins.

Jelly, 28 bytes

ẹⱮŒp<ƝẠ$ƇṪ
nƝ+çṬ¥a⁸ḟ0Ḥç¦ð¹ç?

A full program taking carrier and message as command line arguments which prints the result
(For a non-packable message prints the unchanged carrier).

Try it online! Or see the test-suite.

How?

ẹⱮŒp<ƝẠ$ƇṪ - Link 1, helper function to find the indices to double: carrier, message
           -                               e.g. "programming", "rom"
 Ɱ         - map across message with:
ẹ          -   indices of                       [[2,5], [3], [7,8]]
  Œp       - Cartesian product                  [[2,3,7],[2,3,8],[5,3,7],[5,3,8]]
        Ƈ  - filter keep if:
       $   -   last two links as a monad:
     Ɲ     -     for neighbours:
    <      -       less than?                    [1,1]   [1,1]   [0,1]   [0,1]
      Ạ    -     all truthy?                     1       1       0       0
           -                                    [[2,3,7],[2,3,8]]
         Ṫ - tail (if empty yields 0)                    [2,3,8]

nƝ+çṬ¥a⁸ḟ0Ḥç¦ð¹ç? - Main Link: carrier, message
                ? - if...
               ç  - ...condition: last Link (the helper function) as a dyad
             ð    - ...then: perform the dyadic chain to the left (described below)
              ¹   - ...else: do nothing (yields carrier)
                  - (the then clause:)
 Ɲ                - for neighbours in the carrier
n                 - not equal?
     ¥            - last two links as a dyad:
   ç              -   call last Link (the helper function) as a dyad
    Ṭ             -   untruth (e.g. [2,5] -> [0,1,0,0,1])
  +               - add (vectorises)
      a⁸          - logical AND with carrier
        ḟ0        - filter out zeros
            ¦     - sparse application...
           ç      - ...to indices: call last Link (the helper function) as a dyad
          Ḥ       - ...do: double (e.g. 'x' -> 'xx')


The Most Durable Pokemon Types Background

This question is similar to this one. I have provided all of the information needed below. If you are familiar with the other challenge then note that we are ranking all defenses instead of seeing the effectiveness of a single attack. This is important because it means that the tables are inverses of each other and the goal of this challenge is to be without user input.

In Pokemon there are 18 types:

Normal    Fighting  Flying  Poison  Ground  Rock
Bug       Ghost     Steel   Fire    Water   Grass
Electric  Psychic   Ice     Dragon  Dark    Fairy

Pokemon have either one or two unique types that define them (a "type combination"). For example, a Bulbasaur has the type combination Grass/Poison (it has two types, Grass and Poison) and a Charmander has the type combination Fire (having just one type). The order of types does not matter (i.e. Grass/Poison is the same as Poison/Grass).

These types all have strengths and weaknesses:

A type can be weak to another type. Fire is weak against Water. This results in Fire having a 2× multiplier against Water.
A type can be resistant to another type. Water is resistant to Water. This results in Water having a 0.5× multiplier against Water.
A type can be immune to another type. Flying is immune to Ground. This results in Flying having a 0× multiplier against Ground.

Anything else receives a standard 1× multiplier. Normal against Normal would result in a 1× multiplier is an example of this. These strengths and weaknesses can be compounded or negated as well. For example, Fire is weak to Water but a Fire/Water dual type would have a 1× multiplier against Water since the weakness from Fire would negate the resistance from Water. For a full table and a further explanation, see below.

Objective

The goal here is to output a list of all types combinations, sorted in the order of their defensive ability, and listing their numbers of (resistances+immunities), weaknesses, and the ratio between those. Specifically, the sort order is as follows: type combinations with the best ratio of (resistances+immunities) to weaknesses are listed first, and if there is a tie, type combinations with the most resistances and immunities will win the tiebreak. You can produce this list via any means (an obvious method is to do a type effectiveness calculation against each type combination, but you are allowed to store precalculated or partially precalculated output in your program if doing so would make it shorter.)

Type effectiveness table

For a human readable table, see the Pokemon database. Note: the columns of this list are what we are considering. But just in case, here is the table I'm thinking of in a compressed computer-friendly matrix of effectiveness. I've multiplied every value by 2 so we don't have to deal with pesky decimals:

           Attacking type
            (same order)
   Nor   222222422222202222
   Fir   214211224221422211
D  Wat   211441222222222212
e  Ele   222122224122222212
f  Gra   241114241424222222
e  Ice   242221422222422242
n  Fig   222222222441122124
d  Poi   222212114241222221
i  Gro   224044212222122222
n  Fly   222414120221422222
g  Psy   222222122214242422
   Bug   242212121422422222
T  Roc   114242414122222242
y  Gho   022222012221242422
p  Dra   211114222222224224
e  Dar   222222422204212124
   Ste   142211404111121211
   Fai   222222142221220142

Example

If this problem had requested only output for single-type type combinations, then a valid output would look like this:

Steel -> 11/3 = 3.66
Electric -> 3/1 = 3
Poison -> 5/2 = 2.5
Fire -> 6/3 = 2
Water -> 4/2 = 2
Ghost -> 4/2 = 2
Fairy -> 4/2 = 2
Fly -> 4/3 = 1.333
Dragon -> 4/3 = 1.333
Fighting -> 3/3 = 1
Normal -> 1/1 = 1
Ground -> 3/3 = 1
Psychic -> 2/2 = 1
Bug -> 3/3 = 1
Dark -> 3/3 = 1
Grass -> 4/5 = 0.8
Rock -> 4/5 = 0.8
Ice -> 1/4 = 0.25

However, your program will also need to list all of the dual-type combinations in the output, so its output will be considerably longer.

Best of luck! Shortest code in bytes wins.


List of first n prime numbers most efficiently and in shortest code Rules are simple:

First n primes (not primes below n), should be printed to standard output separated by newlines (primes should be generated within the code)
primes cannot be generated by an inbuilt function or through a library, i.e. use of a inbuilt or library function such as, prime = get_nth_prime(n), is_a_prime(number), or factorlist = list_all_factors(number) won't be very creative.
Scoring - Say, we define Score = f([number of chars in the code]), O(f(n)) being the complexity of your algorithm where n is the number of primes it finds. So for example, if you have a 300 char code with O(n^2) complexity, score is 300^2 = 90000, for 300 chars with O(n*ln(n)), score becomes 300*5.7 = 1711.13 (let's assume all logs to be natural logs for simplicity)
Use any existing programming language, lowest score wins

Edit: Problem has been changed from finding 'first 1000000 primes' to 'first n primes' because of a confusion about what 'n' in O(f(n)) is, n is the number of primes you find (finding primes is the problem here and so complexity of the problem depends on the number of primes found)

Note: to clarify some confusions on complexity, if 'n' is the number of primes you find and 'N' is the nth prime found, complexity in terms of n is and N are not equivalent i.e. O(f(n)) != O(f(N)) as , f(N) != constant * f(n) and N != constant * n, because we know that nth prime function is not linear, I though since we were finding 'n' primes complexity should be easily expressible in terms of 'n'.

As pointed out by Kibbee, you can visit this site to verify your solutions (here, is the old google docs list)

Please Include these in your solution -

what complexity your program has (include basic analysis if not trivial)
character length of code
the final calculated score

This is my first CodeGolf Question so, if there is a mistake or loophole in above rules please do point them out.

Python (129 chars, O(n*log log n), score of 203.948)

I'd say the Sieve of Eratosthenes is the way to go. Very simple and relatively fast.

N=15485864
a=[1]*N
x=xrange
for i in x(2,3936):
 if a[i]:
  for j in x(i*i,N,i):a[j]=0
print [i for i in x(len(a))if a[i]==1][2:]

Improved code from before.

Python (191 156 152 chars, O(n*log log n)(?), score of 252.620(?))

I cannot at all calculate complexity, this is the best approximation I can give.

from math import log as l
n=input()
N=n*int(l(n)+l(l(n)))
a=range(2,N)
for i in range(int(n**.5)+1):
 a=filter(lambda x:x%a[i] or x==a[i],a)
print a[:n]

n*int(l(n)+l(l(n))) is the top boundary of the nth prime number.


Signal-Interrupting Quines Quining has a long history - if you haven't heard of it, click the tag and read up a little on it.

Your Task

Output an infinite series of 1s (with no other spacing [newlines, spaces, etc.]) UNTIL SIGINT (typically CTRL-C) is called. When it is called, output the program source.

Rules

It must be a valid quine:

No reading source from the disk.
See all other standard loopholes relating to quines.

You may use any language.
As this is a code golf, the shortest answer wins!

Python 3, 76 bytes

s="while 1:\n try:print(end='1')\n except:-print('s=%r;exec(s)'%s)";exec(s)

Note that the byte count includes a trailing newline. This also uses -print to error out after quining.


Codegolf the sequence of distance-3 Hamming Codewords (A075926) Codegolf the hamming code (with distance equals 3)!

The sequence looks like this: 0, 7, 25, 30, 42, 45, 51, 52, 75, 76, 82, 85, 97, 102, 120, 127, 385, 390, 408, 415, 427, 428, 434, 437, 458, 461, 467, 468, 480, 487, 505, 510, 642, 645, 667, 668, 680...

Task

Given n output the first n items in OEIS sequence A075926. Your program should work for any integer n where 0 <= n < 2^15. This sequence is known as the sequence of hamming codewords with distance being 3.

Rules:

Post both an ungolfed version of your code (or an explatation), and the golfed version, so that other people can understand how it works
If your program is written in a language with a compiler, specify which compiler and the compiler settings you used. Non-standard language features are allowed as long as it compiles with the compiler you specified, and the compiler was created prior to this question

Sequence Definition:
Given a distance 3 hamming codeword k, the variants of k are k itself, and any nonnegative integer that can be produced by flipping one of k's bits. The nth hamming codeword is the smallest nonnegative integer that doesn't share a variant with any preceeding distance 3 hamming codeword. Here are the first twenty d-3 hamming codewords in binary:

  0,
  111,
  11001,
  11110,
  101010,
  101101,
  110011,
  110100,
  1001011,
  1001100,
  1010010,
  1010101,
  1100001,
  1100110,
  1111000,
  1111111,
  110000001,
  110000110,
  110011000,
  110011111,
  110101011

Ungolfed C++ code to produce sequence:

//Flips the nth bit
size_t flipN(size_t val, int bit) {
    return val ^ (1ull << bit);
}
void Hamming(size_t n) {
    int bits_to_use = 20;
    //This vector keeps track of which numbers are crossed off
    //As either hamming codewords or their variants.
    std::vector<bool> vect(1ull << bits_to_use, false);
    size_t pos = 0;
    size_t val = 0;
    while(val <= n) {
        //Checks to see that pos hasn't been crossed off
        if(vect[pos]) goto loopend;
        for(int i=0; i < bits_to_use; ++i)
        {
            if(vect[flipN(pos, i)]) goto loopend;
            //Checks to see that none of the variants
            //of pos have been crossed off
        }
        //If both those conditions are satisfied, output pos
        //As the next hamming codeword
        cout << pos << endl;
        //Here we cross off all the variants
        vect[pos] = true;
        for(int i=0; i < bits_to_use; ++i)
        {
            vect[flipN(pos, i)] = true;
        }
        ++val;
        loopend:
        ++pos;
    }
}

Python 2, 98 97 bytes

-1 byte thanks to Mr. Xcoder

x=input()
l=[]
i=0
while len(l)<x:s=any(bin(i^n).count('1')<3for n in l);i+=s;l+=[i]*-~-s
print l

Try it online!

Straightforward implementation, using xor to calculate the hamming distance.
The inner loop is equivalent to :

if any(bin(i^n).count('1')<3 for n in l):
   i+=1
else:
   l.append(i)


Save the Geese from Extinction The species of geese known as Alex A are known for residing in triangular grids consisting of 64 cells:

(Picture taken from this unrelated Project Euler problem.)

We'll label each cell with the numbers 0 to 63 starting from the top row and then moving from left to right on each row below that. So the top cell is 0 and the bottom-right cell is 63.

Each cell has three borders. We can label each border in the form a,b where a and b are the numbers of the cells that share that border. For instance, the border between cell 0 and 2 would be called 0,2 or 2,0 (it doesn't matter what order you put them in).

The labeling system for borders on the very edge of the grid are different, since the cells on the edge of the grid have a border that they don't share with other cells. If a border is only part of one cell, we will use the letter X. For instance, the three borders of cell 0 are 0,2, 0,X, and 0,X.

Some of the cells contain geese. However, these geese will be killed by evil foxes (that come from outside the borders of the grid) if you don't protect them. And if all the geese die then BrainSteel will be sad. Therefore we will write a program that builds fences around the geese to protect them from the foxes. The geese should exist in a single fully enclosed polygon of fences. Our fence budget is quite low so use the least number of fences possible.

Input Description

A list of numbers, comma separated, from 0 to 63, representing the cells that contain geese. Example:

6,12

Output Description

A list of borders that need to have fences built on them to protect the geese successfully. This should be the smallest number of fences possible. Example:

5,6 6,7 11,12 12,13

C#, 530 bytes

Complete C# program, takes input as a single line from STDIN, and outputs a single line to STDOUT, with a trailing " ".

This is rather long... and has way too much x/y/z repetition, but I've not been able to reduce it to anything sensible thus far, and have an exam in 2 hours, might come back to this tomorrow.

using Q=System.Console;class P{static void Main(){int q=9,w=0,e=9,r=0,t=9,u=0,i=0,x=0,y=0,z=0,p=0;System.Action V=()=>{z=(int)System.Math.Sqrt(i);p=(x=i-z*z)%2;x/=2;y=(++z*z--+~i)/2;},W=()=>{Q.Write(i+","+(x<0|y++<0|z>7?"X":""+(z*z+2*x+1-p))+" ");};foreach(var g in Q.ReadLine().Split(',')){i=int.Parse(g);V();q=q>x?x:q;w=w<x?x:w;e=e>y?y:e;r=r<y?y:r;t=t>z?z:t;u=u<z?z:u;}for(i=64;i-->0;){V();if(!(x<q|x>w|y<e|y>r|z<t|z>u))if(p>0){if(y==r)W();if(x++==w)W();x--;if(z--==t)W();}else{if(y--==e)W();if(x--==q)W();x++;if(z++==u)W();}}}}

This diagram explains most of what is going on.

Recognize that because we can't have 0-width sections, a "hexagon" is always going to be the cheapest shape (and has the benefit of giving the geese the maximum of space to move in).

The program works by first translating all the input cell indices into x/y/z coords, and finding the min/max of each of x/y/z.

z = floor(root(i))
x = floor((i - z^2) / 2)
y = floor((z+1)^2 - i - 1) / 2)
p = (i - z^2) % 2

Next, it goes through each cell index, and checking if it fits in the 'hexagon' bound we have described. If it is then it checks if it's on any of the extreme edges of the bounds (i.e. x = xmin, or y = ymax) and adds corresponding edges if it is. It has to work out the index of the edge it's next to. For x and z, we just increment/decrement them however we want, and then use the following formula:

i = z^2 + 2*x + (1-p)

Notice that the "parity" always changes, and that y is not involved. For y, we don't have to change anything, but the code is a bit of a mess because it has to perform "triangle" bounds checking to detect whether the cell next door should be an "X" or not.

Example solution (Cells with geese just in from the three corners):

Input
2,50,62

Output
62,63 61,X 59,X 57,X 55,X 53,X 51,X 50,49 48,X 36,X 35,X 25,X 24,X 16,X 15,X 9,X 8,X 4,X 3,X 2,0 1,X

Tidier code with comments:

using Q=System.Console;

class P
{
    static void Main()
    {
        int q=9,w=0,e=9,r=0,t=9,u=0, // min/max x/y/z/ (init min high, and max low)
        i=0, // index of cell we are looking at
        x=0,y=0,z=0,p=0; // x,y,z dimension

        System.Action V=()=>
            { // translates the index into x/y/z/p
                z=(int)System.Math.Sqrt(i);
                p=(x=i-z*z)%2; // 'parity'
                x/=2; // see p assignment
                y=(++z*z--+~i)/2; // ~i == -i - 1
            },
            W=()=>
            { // writes out the edge of i, and the cell described by x/z/inverse of p   (the inversion of p handles y +/-)
                Q.Write(i+","+ // write out the edge
                        (x<0|y++<0|z>7?"X":""+(z*z+2*x+1-p)) // either X (if we go out of 'trianlge' bounds), or we translate x/z/inverse of p into an index
                        +" "); // leaves a trailing space (as shown in example output)
            };

        foreach(var g in Q.ReadLine().Split(',')) // for each cell with geese
        {
            i=int.Parse(g); // grab index of cell
            V(); // compute x/y/z/p
            q=q>x?x:q; // sort out mins/maxes
            w=w<x?x:w;
            e=e>y?y:e;
            r=r<y?y:r;
            t=t>z?z:t;
            u=u<z?z:u;

            // code like the above suggests a solution with a couple of arrays would be better...
            // I've not had success with that yet, but maybe in a couple of days I will try again
        }

        for(i=64;i-->0;) // for each cell
        {
            V(); // compute x/y/z/p
            if(!(x<q|x>w|y<e|y>r|z<t|z>u)) // if we are inside the 'hex' bounds
                if(p>0)
                { // x max, y max, z min
                    // these checks check that we are on the extremes of the 'hex' bounds,
                    // and set up the appropriate vars for W calls to put the edges in
                    // must do y first, because W modifies it for us (saves 2 bytes in the next block)
                    if(y==r) // don't need the ++ (can't go out of 'trianlge' bounds)
                        W();
                    if(x++==w)
                        W();
                    x--;
                    if(z--==t)
                        W();
                    //z++; not used again
                }
                else
                { // x min, y min, z max
                    if(y--==e) // do need the -- (used for 'trianlge' bounds checking)
                        W();
                    // y is reset in W, as such
                    if(x--==q)
                        W();
                    x++;
                    if(z++==u)
                        W();
                    //z--; not used again
                }
        }
    }
}