Is My Swipe Pattern Legal? Most Android smartphones allow the user to use a swipe pattern to open their phone:

Certain patterns are legitimate, and others are impossible. Given an input swipe pattern, return a truthy or falsy indicating if the given input pattern is legal or not.

Input

The grid is labelled row-wise 1 through 9:

1 2 3
4 5 6
7 8 9

The input is a number comprised of the nodes visited from first to last. For example, the swipe pattern above is 12357.

Input can be a decimal number, string or list of numbers. It will not contain 0 because there is no node 0.

Amendment: indexing 0-8 is allowed since a lot of languages index from 0. If you use 0-8, it'll be necessary to indicate as such at the beginning of your answer and adjust the test cases accordingly.

Rules

Every node starts as unvisited initially and may only be visited once. Any pattern which visits a node more than once is falsy.
A truthy pattern must contain at least one swipe, so a minimum of 2 nodes.
It's not possible to skip over an unvisited node directly in line with another.
For example, 13 is falsy because 2 is unvisited and directly in line.
It is only possible to skip over a visited node. 42631 is an example of this.
Lines may cross otherwise. For example, 1524 is truthy.
Assume node widths are insignificant and ignore practical issues (finger thickness, etc). So 16 is truthy even though it may be slightly harder to achieve in reality.

Test Cases

1 -> false
12 -> true
13 -> false
16 -> true
31 -> false
33 -> false
137 -> false
582 -> true
519 -> true
1541 -> false
12357 -> true
15782 -> true
19735 -> false
42631 -> true
157842 -> true
167294385 -> true
297381645 -> false
294381675 -> true

This is code-golf, so the fewest number of bytes wins.

JavaScript (ES6), 64 bytes

Takes input as an array of numbers. Falsy values are 0 or NaN. Truthy values are strictly positive integers.

a=>a[p=1]*a.every(n=>a[p=a[n&p&p*n%5<0|~(p-=n)==9&&p/2]&&-n]^=p)

Test cases

let f =

a=>a[p=1]*a.every(n=>a[p=a[n&p&p*n%5<0|~(p-=n)==9&&p/2]&&-n]^=p)

console.log('[Truthy]')
console.log([
  [1,2],
  [1,6],
  [5,8,2],
  [5,1,9],
  [1,2,3,5,7],
  [1,5,7,8,2],
  [1,6,7,2,9,4,3,8,5],
  [4,2,6,3,1],
  [1,5,7,8,4,2],
  [2,9,4,3,8,1,6,7,5]
]
.map(f).join(' '))

console.log('[Falsy]')
console.log([
  [1],
  [1,3],
  [3,1],
  [3,3],
  [1,3,7],
  [1,5,4,1],
  [1,9,7,3,5],
  [2,9,7,3,8,1,6,4,5]
]
.map(f).join(' '))

How?

Preamble

Two digits are vertically, horizontally or diagonally opposed if:

they are both odd, different from each other and different from 5 (figure 1)
OR they are both even and their sum is 10 (figure 2)

Besides, the digit standing between two opposed digits n and p is equal to (n + p) / 2.

Formatted source code

a =>
  // force a falsy result if a[1] is undefined
  a[p = 1] *
  // walk through all values n in a[]
  a.every(n =>
    // access either a[-n] or a[undefined]
    a[
      // set p to either -n or undefined
      p =
        // read either a[0] or a[in_between_digit]
        a[
          n & p & p * n % 5 < 0 | ~(p -= n) == 9
          && p / 2
        ]
        && -n
    ]
    // toggle the flag
    ^= p
  )

Keeping track of previous digits

Flags for visited digits are stored at negative indices in the input array a, so that they don't collide with its original elements.

If p is set to -n:

If the current digit n was not previously selected, a[-n] ^= -n will set the flag and let the every() loop go on with the next iteration. Otherwise, it will clear the flag and force the loop to fail immediately.
If p is set to undefined:

a[undefined] ^= undefined results in 0, which also forces the loop to fail.

Detecting opposed digits

The following expression is used to test whether the current digit n and the previous digit -p are opposed digits, as defined in the preamble:

n & p & ((p * n) % 5 < 0) | ~(p -= n) == 9

which is equivalent to:

n & p & ((p * n) % 5 < 0) | (p -= n) == -10

Note: In JS, the result of the modulo has the same sign as the dividend.

It can be interpreted as:

(n is odd AND -p is odd AND (neither -p or n is equal to 5)) OR (n + -p = 10)

Therefore, this expression returns 1 if and only if n and -p are opposed digits or they are the same odd digit. Because a digit can't be selected twice, this latter case is correctly taken care of anyway.

If this expression returns 1, we test a[p / 2] (where p is now equal to the negated sum of the digits) in order to know whether the 'in-between digit' was previously visited. Otherwise, we test a[0] which is guaranteed to be truthy.

About the first iteration

The first iteration is a special case, in that there is no previous digit and we want it to be unconditionally successful.

We achieve that by initializing p to 1, because for any n in [1 .. 9]:

(1 * n) % 5 can't be negative
~(1 - n) can't be equal to 9

Original answer, 90 bytes

Removed from this post so that it doesn't get too verbose. You can see it here.


Levenshtein distance & OEIS (Robbers) This is the Robber post. The Cop post is here.

Your task is to take an integer input N and output the Nth digit in the sequence OEIS A002942.

The sequence consists of the square numbers written backwards:

1, 4, 9, 61, 52, 63, 94, 46, 18, 1, 121, 441, ...

Note that leading zeros are trimmed away (100 becomes 1, not 001). Concatenating this into a string (or one long number gives):

1496152639446181121441

You shall output the Nth digit in this string/number. You may choose to take N as 0-indexed or 1-indexed (please state which one you choose).

Test cases (1-indexed):

N = 5,      ==> 1
N = 17,     ==> 1   <- Important test case! It's not zero.
N = 20,     ==> 4
N = 78,     ==> 0
N = 100,    ==> 4
N = 274164, ==> 1

Your code should work for numbers up to N = 2^15 (unless your language can't handles 32 bit integers by default, in which case N can be lower).

Robbers:

You should try to crack the Cops' posts.

Your code must be in the same language as the Cop post, and have a Levenshtein distance exactly equal to the distance given by the cop. Your code cannot be longer than the original solution (but it can be the same size).

You may check the Levenshtein distance here!

The winner will be the robber that cracked the most posts.

Haskell, Laikoni

((show.(*1).read.reverse.show.(^2)=<<[1..])!!)

Try it online!

The (*1) was necessary  for type checking.


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

Spaces after keywords are optional because of tokenisation. For example:

INPUT answer$
PRINT answer$
IF answer$ = 'Hi' THEN
  PRINT 'Hi!'
ENDIF

Can be shortened to

INPUTanswer$
PRINTanswer$
IFanswer$='Hi'THEN
  PRINT'Hi!'
ENDIF

The corollary of this is, a variable name cannot start with a keyword. So PRINTa is not a valid variable name. However printa is.

Spaces before keywords can be more tricky. Variable names can end with a keyword, so if variable name and keyword are run together they will be interpreted as a variable name.

For example the following gives a "no such variable" error because the variable aPRINT is not defined:

  a=7
  IF7=aPRINT"seven"

By rearranging this can be avoided:

  a=7
  IFa=7PRINT"seven"

This is a trivial example, but frequently rearranging an expression to end in a number or bracket instead of a variable name will enable you to eliminate a trailing space.


Yet another "draw a box" Question The following problem is a common interview question, thus dull answers are discouraged. Go short or creative, best if both:

Create the following pattern

###########
##       ##
# #     # #
#  #   #  #
#   # #   #
#    #    #
#   # #   #
#  #   #  #
# #     # #
##       ##
###########

In case you cry "dupe",
 I see your point but this is a slight variation and I hope it differs enough to be greenlit.

Charcoal, 9 bytes

Ｐ¬↙×⁶#‖Ｏ¬

Try it online!


Fixing a logic system You are given a set of logic statements. Your challenge is to remove any ones that contradict the others, but in the optimal way (i.e. removing a minimal number of statements).

Challenge

You will write a program or a function that takes as input a list of statements, removes the minimal number of statements such that there is a solution and outputs the rest.

Logic

Statements consist of variables A-Z and operators between them.

There are 5 operators: - (not), v (or), ^ (and), -> (if) and <-> (iff).

Truth table:

A | B | -A | AvB | A^B | A->B | A<->B
0 | 0 |  1 |  0  |  0  |   1  |   1
0 | 1 |  1 |  1  |  0  |   1  |   0
1 | 0 |  0 |  1  |  0  |   0  |   0
1 | 1 |  0 |  1  |  1  |   1  |   1

These operators can be combined together with parenthesis ():

A | B | -(AvB) | Av(-A) | A^(-A) | (AvB)->(-B)
0 | 0 |    1   |    1   |    0   |      1
0 | 1 |    0   |    1   |    0   |      0
1 | 0 |    0   |    1   |    0   |      1
1 | 1 |    0   |    1   |    0   |      0

Logic systems consist of 1 or more statements.

A solution to the logic system is a state where all of the statements are simultaneously true.

Examples of logic systems:

AvB
-(A<->B)
(AvB)->(-B)

The only solution is A = 1, B = 0.

A^B
-(B<->A)

This one has no solution; with no combination of A and B both of the statements are true.

Input

You will receive a set of statements as input. This can be taken via STDIN or function arguments, formatted as an array (in a convenient format) or a newline-separated or space-separated string.

The statements will be of the following form (in almost-ABNF):

statement        = variable / operation
operation        = not-operation / binary-operation
not-operation    = "-" operand
binary-operation = operand binary-operator operand
operand          = variable / "(" operation ")"
variable         = "A"-"Z"
binary-operator  = "v" / "^" / "->" / "<->"

Example statements:

A
Av(-B)
(A<->(Q^C))v((-B)vH)

Output

You must return the (possibly) reduced set of statements, in the exact form you received them. Again, the list can be formatted as an array of strings or a newline-separated or space-separated string.

Rules

You should always remove the minimal number of statements. If there are multiple possible solutions, output one of them.
You may assume that the input always contains at least 1 statement and that no statements are repeated in the input.
You may not assume that the output always contains a statement. (see examples)
Using standard loopholes contradicts with your answer being valid, and one of them must be removed.
This is code-golf, so the shortest answer in bytes wins.

Examples

Input:

A^(-A)

Output:

(nothing)

Input:

A^B A<->(-B) A<->B

Output:

A^B A<->B

Input:

["AvB","A^B"]

Output:

["AvB","A^B"]

Python 3, 431 bytes

Not very golfed right now, but I figure I'd get the ball rolling with an answer. Try it here, g() is the main function.

import re,itertools as H
def g(i):
 y=re.sub(r'\W','',''.join(set(i)).upper());l=i.split()
 def e(s):
  def f(a):
   for v,w in a:exec(v+'='+w)
   return eval(re.sub('[^A-Z()]+',lambda x:{'v':' or ','^':'*','<->':'==','->':'<=','-':'not '}[x.group()],s))
  return[c for c in H.product("01",repeat=len(y))if f(zip(y,c))]
 for n in range(len(l),-1,-1):
  for q in H.combinations(l,n):
   if e('('+')^('.join(q)+')'):return' '.join(q)


Further golfing this C# code from Scramble words while preserving their outlines I'll start off by saying I checked and checked again that this question should be on topic.

I will also clearly state that this is a tips question about further golfing a certain set of code not a challenge.

I recently answered the following challenge:  Scramble words while preserving their outlines:

  It is well known that a text can still be read while the innards of its words have been scrambled, as long as their first and last letters plus their overall outlines remain constant. Given a printable Ascii+Newline text, scramble each word according to these rules:

  Scrambling must be (pseudo) random.
  A word is a sequence of the Latin characters, A through Z.
  Only initial letters will ever be uppercase.
  The first and last letters must stay untouched.
  When scrambling, only letters within one of the following groups may exchange places:

  acemnorsuvwxz
  bdfhkl
  gpqy
  it
  j (stays in place)

My answer is in C# and coming in, currently, at 394 bytes:

namespace System{using Text.RegularExpressions;using Linq;s=>Regex.Replace(s,@"[A-Za-z](([acemnorsu-xz])|([bdfhkl])|([gpqy])|([it]))*?[a-z]?\b",m=>{var a=m.Value.ToCharArray();for(int i=1,j;++i<6;){var c=m.Groups[i].Captures;var n=c.Cast<Capture>().Select(p=>p.Index-m.Index).ToList();foreach(Capture p in c){a[j=n[new Random().Next(n.Count)]]=p.Value[0];n.Remove(j);}}return new string(a);});}

I think there's room for golfing in the Linq statement and foreach loop at least.

Can this code be further golfed down?

As I am using linq in my program, I can change ToCharArray to ToArray to save 4 bytes.

I can also change the namespace around to be either System.Linq or System.Text.RegularExpressions to save a further 6 bytes by removing the using for it:

namespace System.Text.RegularExpressions

As @MartinEnder♦ points out in the comments I can save 10 bytes by re-ordering the groups in the regex and changing [A-Za-z] to \p{L}:

\p{L}(([gpqy])|(i|t)|(j)|([bdf-l])|([a-z]))*?[a-z]?\b


Merging a dict compression referencing the original list into 1 line Background

A question wanted to solve a problem in a way that made it unreasonably complex: https://stackoverflow.com/a/31551257/29347

The problem in the original question is:

  Take a list of (key, value) and produce a dict such that {key: sum(value)}

My Problem

I want to use dict compression with list.count or str.count but constructing the iterable, iterating and referencing it in one motion has me stumped.

a = [("a",1), ("b",3), ("a",5)]

# b = "abbbaaaaa"
b = "".join(b[0] * b[1] for b in a)

# dict_a = {'a': 6, 'b': 3}
dict_a = {e[0]: b.count(e) for e in b}

Goal

Remove the need for the variable b thus merging the two lines whilst staying true to the solution.

dict_a = {t[0] : sum(tp[1] for tp in a if tp[0] == t[0]) for t in a}

Horribly slow, but hey it's a one liner!


Set Theory Operations Union Only My obsession with set theory continues. I believe that most programming languages have neither sets as possible structures nor set theory operations such as Union and Intersection. If I am wrong then this question becomes trivial and I learn something new.

It would be fun to ask for the code golf construction of a full set structure where a set could contain any possible structures within the language and operators such as is a member of, is a subset of, union and intersection etc. However that is much too broad. So I will simplify the puzzle.

Terminology

An Alphaset has only lower case letters as elements.

The structure for an Alphaset can be defined as you wish and the method used should be explained. It could be just a list of letters read from a file.

As an example I will use an array as a structure for an Alphaset.

An Alphaset can contain a letter once only and order does not matter.

['a','b','c'], ['b','c','a'] and ['c','a','b'] are equivalent Alphasets.

The operation Union forms an Alphaset from two Alphasets.

['a','b','c'] Union ['d','a', 'g', 'b'] is ['a', 'b', 'c', 'd', 'g'] or an equivalent.

A Big Alphaset has the same structure as an Alphaset but can contain repeated letters, eg ['a', 'b', 'a', 'c', 'b'] is a Big Alphaset.

If A and B are any combination of Alphasets and Big Alphasets then A Union B must return an Alphaset.

This gives a way of producing an Alphaset from a Big Alphaset should it ever be necessary for when A is a Big Alphaset the A Union A will be an Alphaset.

Puzzle

Input

A an Alphaset or Big Alphaset

B an Alphaset or Big Alphaset

Ouput

An Alphaset that is the Union of A and B.

Test Data

Testing should demonstrate that order of elements within the Alphaset does not matter.

ie the following should all produce equivalent results.

['a','b','c'] Union ['a', 'c', 'd']

['b','c','a'] Union ['c', 'd', 'a']

['c','b','a'] Union ['d', 'a', 'c']

Shortest code wins

Python2 - 21 (or 15) (or 1)

Sets should be in the format set([element1, element2, element3...])

print input()|input()

If running from the interactive prompt is allowed, remove the print.

Note: If the Mathematica answer qualifies as being 1 character, then in the Python interactive prompt this should also qualify as 1 character:

set(['a','b','d','z'])|set(['c','z','d','a','k','a'])

Sample input:

set(['a','b','d','z'])
set(['c','z','d','a','k','a'])

Sample output:

set(['a', 'c', 'b', 'd', 'k', 'z'])


Largest power of 2 that divides \$n\$ Related, related
Introduction
The ruler sequence is the sequence of the largest possible numbers \$a_n\$ such that \$2^{a_n}\mid n\$. It is so-called because its pin plot looks similar to a ruler's markings:

However, with a slight modification, we can also get a similar sequence. This sequence is \$\{a_1,a_2,a_3,…\}\$ where \$a_n\$ is the largest power of 2 such that \$a_n\mid n\$ (relevant OEIS).
The first 100 terms of this sequence are:
1, 2, 1, 4, 1, 2, 1, 8, 1, 2, 1, 4, 1, 2, 1, 16, 1, 2, 1, 4, 1, 2, 1, 8, 1, 2, 1, 4, 1, 2, 1, 32, 1, 2, 1, 4, 1, 2, 1, 8, 1, 2, 1, 4, 1, 2, 1, 16, 1, 2, 1, 4, 1, 2, 1, 8, 1, 2, 1, 4, 1, 2, 1, 64, 1, 2, 1, 4, 1, 2, 1, 8, 1, 2, 1, 4, 1, 2, 1, 16, 1, 2, 1, 4, 1, 2, 1, 8, 1, 2, 1, 4, 1, 2, 1, 32, 1, 2, 1, 4

Challenge
Your challenge is to do one of these three things:

Take a positive integer \$n\$ as input and return the \$n\$th term of this sequence.
Take a positive integer \$n\$ as input and return the first \$n\$ terms of this sequence.
Output the sequence infinitely.

Test Cases
12 -> 4
64 -> 64
93 -> 1
8 -> 8
0 -> (undefined behavior)

Rules

You may output the sequence in any convenient format - e.g. as a list or some other iterable or separated by any non-digit separator, as long as it is constant between all terms.
You may output the term(s) in any convenient format - e.g. as an integer, as an integer string, as a float with the decimal part consisting of only zeros, ditto but as a string, or as a Boolean (True) iff the term is 1.
You may choose to use either zero- or one-indexing.
Standard loopholes are forbidden.
Trailing whitespace is allowed.
If possible, please link to an online interpreter (e.g. TIO) to run your program on.
Please explain your answer. This is not necessary, but it makes it easier for others to understand.
Languages newer than the question are allowed. This means you could create your own language where the empty program generates this sequence, but don't expect any upvotes.
Non-programming languages are allowed. A non-programming language is a language which doesn't satisfy both of these conditions:

Able to take two integers as input and print their sum
Able to take one integer as input and print a truthy value if it is prime, and a falsy value if it is not

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

Python 2, 13 bytes
Takes a positive integer \$ n \$ as input and returns the \$ n \$th term of the sequence.

lambda n:n&-n

Try it online!
The largest power of \$ 2 \$ that divides \$ n \$ is also the lowest set bit. The bitwise magic is a bit difficult to explain, but it uses the fact that ~n + 1 in its binary representation produces the same lowest set bit as n.
Python 2, 26 bytes
Outputs the sequence infinitely.

n=1
while 1:print-n&n;n+=1

Try it online!
Python 2, 33 bytes
Takes a positive integer \$ n \$ as input and returns the first \$ n \$ terms of the sequence.

f=lambda n:n*[0]and f(n-1)+[n&-n]

Try it online!


JavaScript (Node.js), 40 bytes

Thanks to @Neil for saving 5 bytes on this version and 2 bytes on the BigInt version

Takes input as (t)(base), where \$t\$ is 1-indexed.

n=>g=(b,x=11)=>--n?g(b,+x.toString(b)):x

Try it online!

JavaScript (Node.js), 48 bytes (BigInt version)

Takes input as (t)(base), where \$t\$ is 1-indexed. Returns a BigInt.

n=>g=(b,x=11n)=>--n?g(b,BigInt(x.toString(b))):x

Try it online!


Naming ionic compounds An ionic compound is named like so: (metal name) (non-metal suffixed with -ide). Here is a list of all the suffixes that need to be replaced with -ide:

-on -ogen -ygen -ine -orus -ur -ic -ium

The number of atoms of each element in the compound is not used in naming ionic compounds. Ignore the multivalent metal naming rules.

NaCl -> sodium + chlorine -> sodium chloride.
K2S -> potassium + sulphur -> potassium sulphide (or sulfide).
Yb2P3 -> ytterbium + phosphorus -> ytterbium phosphide.
PbTe2 -> lead + tellurium -> lead telluride.

A string containing an ionic compound (NaCl, K2S, Yb2P3) will be given as input. No polyatomic ions will be given. The program has to output the name of this compound.

Since nobody wants to compile the periodic table data themselves, here is a paste that has the names, symbols, and whether or not it is a metal of each element, in this order: (name) (symbol) (is metal?). You can save this to an external file (the length of the file will not be counted), or you can store the data within your program (just discount the length of that string from there.) You may not need all the information provided. Every element is seperated by a newline.

As always with code golf challenges, shortest code wins.

Ruby, 114

f,s=$*[0].split /\d*(?=[A-Z]|\Z)/
puts (n=Hash[*<<X.split-%w[0 1]].invert)[f]+" "+n[s].sub(/(i..|.gen|..)\Z/,"ide")
Hydrogen H 0
Helium He 0
Lithium Li 1
Beryllium Be 1
Boron B 0
Carbon C 0
Nitrogen N 0
Oxygen O 0
Fluorine F 0
Neon Ne 0
Sodium Na 1
Magnesium Mg 1
Aluminium Al 1
Silicon Si 0
Phosphorus P 0
Sulfur S 0
Chlorine Cl 0
Argon Ar 0
Potassium K 1
Calcium Ca 1
Scandium Sc 1
Titanium Ti 1
Vanadium V 1
Chromium Cr 1
Manganese Mn 1
Iron Fe 1
Cobalt Co 1
Nickel Ni 1
Copper Cu 1
Zinc Zn 1
Gallium Ga 1
Germanium Ge 1
Arsenic As 0
Selenium Se 0
Bromine Br 0
Krypton Kr 0
Rubidium Rb 1
X

Uses a paste of the element text that I haven't counted in the score. I remove the metal tag (since I'm assuming the compounds are always given with the metal first, so I don't actually need it) and build a dictionary with it. I identify the part to replace with "ide" by checking the end of the string for three letters starting with i, four letters ending with gen, or otherwise just the last two characters.


Reverse Polish notation You must evaluate a string written in Reverse Polish notation and output the result.

The program must accept an input and return the output. For programming languages that do not have functions to receive input/output, you can assume functions like readLine/print.

You are not allowed to use any kind of "eval" in the program.

Numbers and operators are separated by one or more spaces.

You must support at least the +, -, * and / operators.

You need to add support to negative numbers (for example, -4 is not the same thing as 0 4 -) and floating point numbers.

You can assume the input is valid and follows the rules above

Test Cases

Input:

-4 5 +

Output:

1

Input:

5 2 /

Output:

2.5

Input:

5 2.5 /

Output:

2

Input:

5 1 2 + 4 * 3 - +

Output:

14

Input:

4 2 5 * + 1 3 2 * + /

Output:

2

Ruby - 95 77 characters

a=[]
gets.split.each{|b|a<<(b=~/\d/?b.to_f: (j,k=a.pop 2;j.send b,k))}
p a[0]

Takes input on stdin.

Testing code

[
  "-4 5 +",
  "5 2 /",
  "5 2.5 /",
  "5 1 2 + 4 * 3 - +",
  "4 2 5 * + 1 3 2 * + /",
  "12 8 3 * 6 / - 2 + -20.5 "
].each do |test|
  puts "[#{test}] gives #{`echo '#{test}' | ruby golf-polish.rb`}"
end

gives

[-4 5 +] gives 1.0
[5 2 /] gives 2.5
[5 2.5 /] gives 2.0
[5 1 2 + 4 * 3 - +] gives 14.0
[4 2 5 * + 1 3 2 * + /] gives 2.0
[12 8 3 * 6 / - 2 + -20.5 ] gives 10.0

Unlike the C version this returns the last valid result if there are extra numbers appended to the input it seems.


How high can you go? (A coding+algorithms challenge) Now that everyone has developed their (often amazing) low level coding expertise for How slow is Python really? (Or how fast is your language?) and How Slow Is Python Really (Part II)? it is time for a challenge which will also stretch your ability to improve an algorithm.

The following code computes a list of length 9. Position i in the list counts the number of times at least i consecutive zeros were found when computing the inner products between F and S. To do this exactly, it iterates over all possible lists F of length n and lists S of length n+m-1.

#!/usr/bin/python
import itertools
import operator

n=8
m=n+1
leadingzerocounts = [0]*m
for S in itertools.product([-1,1], repeat = n+m-1):
    for F in itertools.product([-1,1], repeat = n):
        i = 0
        while (i<m and sum(map(operator.mul, F, S[i:i+n])) == 0):
            leadingzerocounts[i] +=1
            i+=1
print leadingzerocounts

The output is

  [4587520, 1254400, 347648, 95488, 27264, 9536, 4512, 2128, 1064]

If you increase n to 10,12,14,16,18,20 using this code it very rapidly becomes far too slow.

Rules

The challenge is to give the correct output for as large an n as possible. Only even values of n are relevant.
If there is a tie, the win goes to the fastest code on my machine for the largest n.
I reserve the right not to test code that takes more than 10 minutes.
You may change the algorithm in any way you like as long as it gives the correct output. In fact you will have to change the algorithm to make any decent progress toward winning.
The winner will be awarded one week from when the question was set.
The bounty will be awarded when it is due which is a little after when the winner will be awarded.

My Machine The timings will be run on my machine. This is a standard ubuntu install on an AMD FX-8350 Eight-Core Processor.  This also means I need to be able to run your code. As a consequence, only use easily available free software and please include full instructions how to compile and run your code.

Status.

C. n = 12 in 49 seconds by @Fors
Java. n = 16 in 3:07 by @PeterTaylor
C++. n = 16 in 2:21 by @ilmale
Rpython. n = 22 in 3:11 by @primo
Java. n = 22 in 6:56 by @PeterTaylor
Nimrod. n = 24 in 9:28 seconds by @ReimerBehrends

The winner was Reimer  Behrends with an entry in Nimrod!

As a check, the output for n = 22 should be [12410090985684467712, 2087229562810269696, 351473149499408384, 59178309967151104, 9975110458933248, 1682628717576192, 284866824372224, 48558946385920, 8416739196928, 1518499004416, 301448822784, 71620493312, 22100246528, 8676573184, 3897278464, 1860960256, 911646720, 451520512, 224785920, 112198656, 56062720, 28031360, 14015680].

The competition is now over but... I will offer 200 points for every submission that increases  n by 2 (within 10 minutes on my computer) until I run out of points. This offer is open forever.

Nimrod (N=22)

import math, locks

const
  N = 20
  M = N + 1
  FSize = (1 shl N)
  FMax = FSize - 1
  SStep = 1 shl (N-1)
  numThreads = 16

type
  ZeroCounter = array[0..M-1, int]
  ComputeThread = TThread[int]

var
  leadingZeros: ZeroCounter
  lock: TLock
  innerProductTable: array[0..FMax, int8]

proc initInnerProductTable =
  for i in 0..FMax:
    innerProductTable[i] = int8(countBits32(int32(i)) - N div 2)

initInnerProductTable()

proc zeroInnerProduct(i: int): bool =
  innerProductTable[i] == 0

proc search2(lz: var ZeroCounter, s, f, i: int) =
  if zeroInnerProduct(s xor f) and i < M:
    lz[i] += 1 shl (M - i - 1)
    search2(lz, (s shr 1) + 0, f, i+1)
    search2(lz, (s shr 1) + SStep, f, i+1)

when defined(gcc):
  const
    unrollDepth = 1
else:
  const
    unrollDepth = 4

template search(lz: var ZeroCounter, s, f, i: int) =
  when i < unrollDepth:
    if zeroInnerProduct(s xor f) and i < M:
      lz[i] += 1 shl (M - i - 1)
      search(lz, (s shr 1) + 0, f, i+1)
      search(lz, (s shr 1) + SStep, f, i+1)
  else:
    search2(lz, s, f, i)

proc worker(base: int) {.thread.} =
  var lz: ZeroCounter
  for f in countup(base, FMax div 2, numThreads):
    for s in 0..FMax:
      search(lz, s, f, 0)
  acquire(lock)
  for i in 0..M-1:
    leadingZeros[i] += lz[i]*2
  release(lock)

proc main =
  var threads: array[numThreads, ComputeThread]
  for i in 0 .. numThreads-1:
    createThread(threads[i], worker, i)
  for i in 0 .. numThreads-1:
    joinThread(threads[i])

initLock(lock)
main()
echo(@leadingZeros)

Compile with

nimrod cc --threads:on -d:release count.nim

(Nimrod can be downloaded here.)

This runs in the allotted time for n=20 (and for n=18 when only using a single thread, taking about 2 minutes in the latter case).

The algorithm uses a recursive search, pruning the search tree whenever a non-zero inner product is encountered. We also cut the search space in half by observing that for any pair of vectors (F, -F) we only need to consider one because the other produces the exact same sets of inner products (by negating S also).

The implementation uses Nimrod's metaprogramming facilities to unroll/inline the first few levels of the recursive search. This saves a little time when using gcc 4.8 and 4.9 as the backend of Nimrod and a fair amount for clang.

The search space could be further pruned by observing that we only need to consider values of S that differ in an even number of the first N positions from our choice of F. However, the complexity or memory needs of that do not scale for large values of N, given that the loop body is completely skipped in those cases.

Tabulating where the inner product is zero appears to be faster than using any bit counting functionality in the loop. Apparently accessing the table has pretty good locality.

It looks as though the problem should be amenable to dynamic programming, considering how the recursive search works, but there is no apparent way to do that with a reasonable amount of memory.

Example outputs:

N=16:

@[55276229099520, 10855179878400, 2137070108672, 420578918400, 83074121728, 16540581888, 3394347008, 739659776, 183838720, 57447424, 23398912, 10749184, 5223040, 2584896, 1291424, 645200, 322600]

N=18:

@[3341140958904320, 619683355033600, 115151552380928, 21392898654208, 3982886961152, 744128512000, 141108051968, 27588886528, 5800263680, 1408761856, 438001664, 174358528, 78848000, 38050816, 18762752, 9346816, 4666496, 2333248, 1166624]

N=20:

@[203141370301382656, 35792910586740736, 6316057966936064, 1114358247587840, 196906665902080, 34848574013440, 6211866460160, 1125329141760, 213330821120, 44175523840, 11014471680, 3520839680, 1431592960, 655872000, 317675520, 156820480, 78077440, 39005440, 19501440, 9750080, 4875040]

For purposes of comparing the algorithm with other implementations, N=16 takes about 7.9 seconds on my machine when using a single thread and 2.3 seconds when using four cores.

N=22 takes about 15 minutes on a 64-core machine with gcc 4.4.6 as Nimrod's backend and overflows 64-bit integers in leadingZeros[0] (possibly not unsigned ones, haven't looked at it).

Update: I've found room for a couple more improvements. First, for a given value of F, we can enumerate the first 16 entries of the corresponding S vectors precisely, because they must differ in exactly N/2 places. So we precompute a list of bit vectors of size N that have N/2 bits set and use these to derive the initial part of S from F.

Second, we can improve upon the recursive search by observing that we always know the value of F[N] (as the MSB is zero in the bit representation). This allows us to predict precisely which branch we recurse into from the inner product. While that would actually allow us to turn the entire search into a recursive loop, that actually happens to screw up branch prediction quite a bit, so we keep the top levels in its original form. We still save some time, primarily by reducing the amount of branching we are doing.

For some cleanup, the code is now using unsigned integers and fix them at 64-bit (just in case someone wants to run this on a 32-bit architecture).

Overall speedup is between a factor of x3 and x4. N = 22 still needs more than eight cores to run in under 10 minutes, but on a 64-core machine it's now down to about four minutes (with numThreads bumped up accordingly). I don't think there's much more room for improvement without a different algorithm, though.

N=22:

@[12410090985684467712, 2087229562810269696, 351473149499408384, 59178309967151104, 9975110458933248, 1682628717576192, 284866824372224, 48558946385920, 8416739196928, 1518499004416, 301448822784, 71620493312, 22100246528, 8676573184, 3897278464, 1860960256, 911646720, 451520512, 224785920, 112198656, 56062720, 28031360, 14015680]

Updated again, making use of further possible reductions in search space. Runs in about 9:49 minutes for N=22 on my quadcore machine.

Final update (I think). Better equivalence classes for choices of F, cutting runtime for N=22 down to 3:19 minutes 57 seconds (edit: I had accidentally run that with only one thread) on my machine.

This change makes use of the fact that a pair of vectors produces the same leading zeros if one can be transformed into the other by rotating it. Unfortunately, a fairly critical low-level optimization requires that the top bit of F in the bit representation is always the same, and while using this equivalence slashed the search space quite a bit and reduced runtime by about one quarter over using a different state space reduction on F, the overhead from eliminating the low-level optimization more than offset it. However, it turns out that this problem can be eliminated by also considering the fact that F that are inverses of one another are also equivalent. While this added to the complexity of the calculation of the equivalence classes a bit, it also allowed me to retain the aforementioned low-level optimization, leading to a speedup of about x3.

One more update to support 128-bit integers for the accumulated data. To compile with 128 bit integers, you'll need longint.nim from here and to compile with -d:use128bit. N=24 still takes more than 10 minutes, but I've included the result below for those interested.

N=24:

@[761152247121980686336, 122682715414070296576, 19793870419291799552, 3193295704340561920, 515628872377565184, 83289931274780672, 13484616786640896, 2191103969198080, 359662314586112, 60521536552960, 10893677035520, 2293940617216, 631498735616, 230983794688, 102068682752, 48748969984, 23993655296, 11932487680, 5955725312, 2975736832, 1487591936, 743737600, 371864192, 185931328, 92965664]

import math, locks, unsigned

when defined(use128bit):
  import longint
else:
  type int128 = uint64 # Fallback on unsupported architectures
  template toInt128(x: expr): expr = uint64(x)

const
  N = 22
  M = N + 1
  FSize = (1 shl N)
  FMax = FSize - 1
  SStep = 1 shl (N-1)
  numThreads = 16

type
  ZeroCounter = array[0..M-1, uint64]
  ZeroCounterLong = array[0..M-1, int128]
  ComputeThread = TThread[int]
  Pair = tuple[value, weight: int32]

var
  leadingZeros: ZeroCounterLong
  lock: TLock
  innerProductTable: array[0..FMax, int8]
  zeroInnerProductList = newSeq[int32]()
  equiv: array[0..FMax, int32]
  fTable = newSeq[Pair]()

proc initInnerProductTables =
  for i in 0..FMax:
    innerProductTable[i] = int8(countBits32(int32(i)) - N div 2)
    if innerProductTable[i] == 0:
      if (i and 1) == 0:
        add(zeroInnerProductList, int32(i))

initInnerProductTables()

proc ror1(x: int): int {.inline.} =
  ((x shr 1) or (x shl (N-1))) and FMax

proc initEquivClasses =
  add(fTable, (0'i32, 1'i32))
  for i in 1..FMax:
    var r = i
    var found = false
    block loop:
      for j in 0..N-1:
        for m in [0, FMax]:
          if equiv[r xor m] != 0:
            fTable[equiv[r xor m]-1].weight += 1
            found = true
            break loop
        r = ror1(r)
    if not found:
      equiv[i] = int32(len(fTable)+1)
      add(fTable, (int32(i), 1'i32))

initEquivClasses()

when defined(gcc):
  const unrollDepth = 4
else:
  const unrollDepth = 4

proc search2(lz: var ZeroCounter, s0, f, w: int) =
  var s = s0
  for i in unrollDepth..M-1:
    lz[i] = lz[i] + uint64(w)
    s = s shr 1
    case innerProductTable[s xor f]
    of 0:
      # s = s + 0
    of -1:
      s = s + SStep
    else:
      return

template search(lz: var ZeroCounter, s, f, w, i: int) =
  when i < unrollDepth:
    lz[i] = lz[i] + uint64(w)
    if i < M-1:
      let s2 = s shr 1
      case innerProductTable[s2 xor f]
      of 0:
        search(lz, s2 + 0, f, w, i+1)
      of -1:
        search(lz, s2 + SStep, f, w, i+1)
      else:
        discard
  else:
    search2(lz, s, f, w)

proc worker(base: int) {.thread.} =
  var lz: ZeroCounter
  for fi in countup(base, len(fTable)-1, numThreads):
    let (fp, w) = fTable[fi]
    let f = if (fp and (FSize div 2)) == 0: fp else: fp xor FMax
    for sp in zeroInnerProductList:
      let s = f xor sp
      search(lz, s, f, w, 0)
  acquire(lock)
  for i in 0..M-1:
    let t = lz[i].toInt128 shl (M-i).toInt128
    leadingZeros[i] = leadingZeros[i] + t
  release(lock)

proc main =
  var threads: array[numThreads, ComputeThread]
  for i in 0 .. numThreads-1:
    createThread(threads[i], worker, i)
  for i in 0 .. numThreads-1:
    joinThread(threads[i])

initLock(lock)
main()
echo(@leadingZeros)


Strongly Connected Components Two distinct vertices in a directed graph are strongly connected if there is path in the graph from each to the other. A strongly connected component of the graph is a subset of the graph such that each pair of distinct vertices in the subset are strongly connected, and adding any more vertices to the subset would break this property.
Your challenge is to separate a graph into its strongly connected components. Specifically, you must output all of the SCCs in the graph.
I/O:
As input, you may use a list of directed edges, an adjacency list, an adjacency matrix, or any other reasonable input format. Ask if you're not sure. You may assume the graph has no totally disconnected vertices, and that there are no self edges, but you may not make any further assumptions. You may also optionally take the list of vertices as input, as well as the number of vertices.
As output, you must either give a partitioning of the vertices, such as a list of lists of vertices, where each sublist is a strongly connected component, or a labeling of vertices, where each label corresponds to a different component.
If you use a labeling, the labels must either be vertices, or a consecutive sequence of integers. This is to prevent offloafing the computation into the labels.
Examples:
These examples take lists of edges, where each edge is directed from the 1st entry to the second entry, and output partitions. You are free to use this format or another.
The input is on the first line, the output is on the second line.
[[1, 2], [2, 3], [3, 1], [1, 4]]
[[1, 2, 3], [4]]

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

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

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

Scoring and restrictions:
Standard loopholes are banned, as always. Also, built-ins which specifically deal with strongly connected components are banned.
Solutions should run in no more than an hour on the examples provided. (This is intended to prevent slow exponential solutions, and nothing else.)
This is code golf. Fewest bytes wins.

Python 2 using numpy, 71 62 bytes

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

Takes input as a numpy matrix representing adjacency and the number of nodes. Produces output as a numpy row matrix that labels each vertex by the lowest vertex number in its component.
For an adjacency matrix M, the matrix power M**n counts the number of n-step paths from each start vertex to each end vertex. Adding the identity to M via M+M**0 modifies the adjacency matrix to add a self-loop to every edge. So, (M+M**0)**n counts paths of length at most n (with redundancy).
Since any path has length at most n, the number of nodes, any (i,j) where vertex j can be reached from i corresponds to a positive entry of (M+M**0)**n. The reachability matrix is thenR=(M+M**0)**n>0, where the >0 works entrywise.
Computing the entrywise and as R&R.T, where R.T is the transpose, then gives a matrix indicating the pairs of mutually reachable vertices. It's ith row is an indicator vector for vertices in the same strongly connected component as it. Taking its argmax of each row gives the index of the first True in it, which is the index of the smallest vertex in its component.


Compute the antipode of a point on curve A curve is a set of points on a square grid such that each point has exactly two neighbors in the four-neighbor neighborhood and the points form a single connected component. That is, the graph induced by the points on a grid graph is isomorphic to a single cycle. "Induced" means that two points cannot touch in the input without being neighbors in the cycle.

An antipode of a vertex V in a graph is a vertex furthest away from V. The antipode is always unique on an even-length cycle (and every cycle on a grid graph is even-length). The distance shall be measured as induced by the cycle itself without respect for the underlying square grid.

Your input shall be an image of a curve. The curve will be marked out with a sequence of number sign characters (#) on a background out of space characters (). One of the points on the curve will be marked with the P character ("pode"). Your output shall be the same as the input except one curve point shall be replaced with A ("antipode").

You may assume the characters will be padded to a rectangular shape. You may assume the first and last row and column of input will be composed entirely of spaces (input is padded with background). Alternatively you may assume that the first and last row and column will each contain a curve point (input has minimum padding).

You may input and output this grid as a single newline-separated string, as an array of rows, or as a 2D array of individual characters. This choice shall be the same for the input and output. If your language allows this, you may output by modifying the input in place instead of returning the modified string or array.

Possible inputs:

P#    P##   #P#   #####      #####P# #######   #####P#########   #####P#########
##    # #   # #   #   #      #     # #     #   #             #   #             #
      ###   ###   ## ##      # ### # # ### #   # ### ### ### #   #             #
###                # # ###   # # # # # # # #   # # # # # # # #   #             #
# P#    ### ###    # ### #   # # ### ### # #   # # ### ### # #   #             #
## #    # ### #    #     #   # #         # #   # #         # #   #             #
 # #    P     #    ##### P   # ########### #   # ##### ##### #   #             #
 ###    #######        ###   #             #   #     # #     #   #             #
                             ###############   ####### #######   ###############

Corresponding outputs:

P#    P##   #P#   #A###      #####P# #A#####   #####P#########   #####P#########
#A    # #   # #   #   #      #     # #     #   #             #   #             #
      ##A   #A#   ## ##      # ### # # ### #   # ### ### ### #   #             #
###                # # ###   # # # # # # # #   # # # # A # # #   #             #
# P#    ### ##A    # ### #   # # ### ### # #   # # ### ### # #   #             #
## #    # ### #    #     #   # #         # #   # #         # #   #             #
 A #    P     #    ##### P   # ########### #   # ##### ##### #   #             #
 ###    #######        ###   #             #   #     # #     #   #             #
                             ###############   ####### #######   #########A#####

Vertex distances from the podes (modulo 10) (do not output these):

P1    P12   1P1   5A543      54321P1 9A98765   54321P123456789   54321P123456789
1A    1 3   2 2   4   2      6     2 8     4   6             0   6             0
      23A   3A3   32 01      7 109 3 7 109 3   7 901 789 543 1   7             1
321                1 9 543   8 2 8 4 6 2 8 2   8 8 2 6 A 6 2 2   8             2
4 P1    234 89A    0 876 2   9 3 765 543 7 1   9 7 345 987 1 3   9             3
56 2    1 567 9    9     1   0 4         6 0   0 6         0 4   0             4
 A 3    P     8    87654 P   1 56789012345 9   1 54321 56789 5   1             5
 654    1234567        321   2             8   2     0 4     6   2             6
                             345678901234567   3456789 3210987   345678901A10987

Python 2, 333 221 215 bytes

-17 bytes thanks to @JanDvorak

g=input()
y=map(max,g).index('P')
x=g[y].index('P')
m=[k[:]for k in g]
v=x;w=y
while'#'in sum(m,[]):x,y,(v,w)=v,w,[(x+a,y+b)for a,b in((1,0),(-1,0),(0,1),(0,-1))if'#'==m[y+b][x+a]][0];m[w][v]='_'
g[w][v]='A'
print g

Try it online!

Python 3, 402 288 282 bytes, String IO

g=[[*k]for k in open(0).read().split('\n')]
y=[max(k)for k in g].index('P')
x=g[y].index('P')
m=[k[:]for k in g]
v=x;w=y
while'#'in sum(m,[]):x,y,(v,w)=v,w,[(x+a,y+b)for a,b in((1,0),(-1,0),(0,1),(0,-1))if'#'==m[y+b][x+a]][0];m[w][v]='_'
g[w][v]='A'
print('\n'.join(map(''.join,g)))

Try it online!

Animation of the code running:


Output N in base -10 Challenge:

In the programming language of your choice, accept an integer  as input in base 10, and output it in the negadecimal notation, which is also known as base -10

Example algorithm:

This is an algorithm taken from Wikipedia to convert base 10 to any negative base in VB.NET:

Function toNegativeBase(Number As Integer , base As Integer) As System.Collections.Generic.List(Of Integer)

    Dim digits As New System.Collections.Generic.List(Of Integer)
    while Number <> 0
        Dim remainder As Integer= Number Mod base
        Number = CInt(Number / base)

        if remainder < 0 then
            remainder += system.math.abs(base)
            Number+=1
        end if

        digits.Insert(0, remainder)
    end while

    return digits
end function

Obviously, you can use any algorithm, as long as it fulfills the challenge

Example inputs / outputs:

Input:

12

Output:

192

Another example:

Input:

2048

Output:

18168

Rule:

You must not use any built-in methods that solve this problem that exist in your programming language

This is a code-golf, so shortest code wins!


Choose-Your-Own-Language Code Let's take a grid of 16x16 printable ASCII characters (code points 0x20 to 0x7E). There are 30-choose-15 paths from the top left to the bottom right corner, making only orthogonal moves, like the following example:

##..............
.#..............
.######.........
......##........
.......##.......
........#.......
........#.......
........#.......
........###.....
..........###...
............#...
............####
...............#
...............#
...............#

Each such path consists of exactly 31 characters. Note that each of those characters is on a different of the 31 anti-diagonals:

0123456789ABCDEF
123456789ABCDEFG
23456789ABCDEFGH
3456789ABCDEFGHI
456789ABCDEFGHIJ
56789ABCDEFGHIJK
6789ABCDEFGHIJKL
789ABCDEFGHIJKLM
89ABCDEFGHIJKLMN
9ABCDEFGHIJKLMNO
ABCDEFGHIJKLMNOP
BCDEFGHIJKLMNOPQ
CDEFGHIJKLMNOPQR
DEFGHIJKLMNOPQRS
EFGHIJKLMNOPQRST
FGHIJKLMNOPQRSTU

This is not an example grid. This is a visualisation of the 31 anti-diagonals.

We'll call a grid diagonally unique if no anti-diagonal contains the same character twice. If the grid has this property, no two paths will contain the same string. (Just to clarify, the visualisation itself is basically the opposite of diagonally unique.)

The Challenge

Design a diagonally unique 16x16 grid, such that as many paths as possible are valid code which prints Jabberwocky to STDOUT (with optional trailing line break) in as many languages as possible. Each code may either be a full program, or the body of a parameterless function without return statement (this is in order not to discourage languages that need to have their code in some boilerplate function/class/namespace).

Note: For simplicity you can use some reserved character for unused cells like Ypnypn did.

For each valid path, please clearly state one programming language it is valid in.

The winner is the submission with the largest number of languages covered by the above list. (Alternatively, for each language you want to count, show one path which is valid in that language, but make sure not to count any path for two languages.)

In the event of a tie, count the grid cells which are not covered by any valid path. Fewer unused cells win. If there is still a tie, I'll accept the answer with the most (net) votes.

Validation Script

I just quickly put together a little CJam snippet you can use to validate that a grid is diagonally unique.

Go to the online CJam interpreter.
Paste the following code

l:A;
qN/W%A16**33/z{A-__|=}%:*"D""Not d"?"iagonally unique"

In the input field, put you reserved character on the first line (use an unused character if you don't make sue of a reserved character), and then your grid in line 2 to 17. E.g., for Ypnypn's answer:

~
 pr~~~~~~~~~~~~~
 tin~~~~~~~~~~~~
~ypt(~~~~~~~~~~~
~~ef(~~~~~~~~~~~
~~  "J~~~~~~~~~~
~~~~~ab~~~~~~~~~
~~~~~~be~~~~~~~~
~~~~~~~rwo~~~~~~
~~~~~~~~~ck~~~~~
~~~~~~~~~~y~~~~~
~~~~~~~~~~\n~~~~
~~~~~~~~~~~")) ~
~~~~~~~~~~~  ;
~~~~~~~~~~~~~~~
~~~~~~~~~~~~~~~
~~~~~~~~~~~~~~~

Run.

Let me know if you think it has a bug.

30 33 35 Languages

Reserved character: ~

 println!~~~~~~~
 puts    (1,~~~~
    echo   '~~~~
"cWprintfn"Ja~~~
Eork~~~;'Jabbe~~
\ui)K00~~~~~br~~
]tteL~0~~~~~ew~~
]<~ln(0~~~~~ro~~
`<~~~ 0~~~~~wc~~
m"~~~ "~~~~~ok~~
rJ~~~'J~~~~~cy~~
j"<< "a~~~~~k'..
^~~~~~bberwoy");
f~~~~~~~~~~c'  ;
t~~~~~~~~~~ky"
XX"););  5f+');

Languages:

01. Rust        | println! (  "Jabberwocky") ;  |
02. Groovy      | println     "Jabberwocky"     |
03. E           | println  (  "Jabberwocky")    |
04. Swift       | println  (  "Jabberwocky") ;  |
05. Julia       | println  (  "Jabberwocky");;  |
06. Processing  | println  (  "Jabberwocky")  ; |
07. Falcon      | printl   (  "Jabberwocky")    |
08. ALGOL 68    | print    (  "Jabberwocky")    |
09. Vala        | print    (  "Jabberwocky") ;  |
10. Pawn        | print    (  "Jabberwocky");;  |
11. Batsh       | print    (  "Jabberwocky")  ; |
12. freeBASIC   | print       "Jabberwocky"     |
13. Rebol       | print       "Jabberwocky"  ;  |
14. Red         | print       "Jabberwocky"   ; |
15. AWK         | print       'Jabberwocky'     |
16. Perl        | print       'Jabberwocky'  ;  |
17. bc          | print       'Jabberwocky'   ; |
18. Euphoria    |  puts    (1,"Jabberwocky")    |
19. C           |  puts    (  "Jabberwocky") ;  |
20. Tcl         |  puts       "Jabberwocky"     |
21. Ruby        |  puts       'Jabberwocky'     |
22. Zsh         |      echo   "Jabberwocky"     |
23. Bash        |      echo   "Jabberwocky"  ;  |
24. tcsh        |      echo   "Jabberwocky"   ; |
25. PHP         |      echo   'Jabberwocky'     |
26. Fish        |      echo   'Jabberwocky'  ;  |
27. Dash        |      echo   'Jabberwocky'   ; |
28. F#          |      printfn"Jabberwocky"   ; |
29. C++         |    cout<<"J"<< "abberwocky" ; |
30. D           |     Writeln(  'Jabberwocky'); |
31. Pascal      |     WriteLn(  'Jabberwocky'); |
32. Delphi      |     Writeln(  "Jabberwocky"); |
33. GolfScript  |      print;'Jabberwocky'..;;  |
34. CJam        |   "E\]]`mrj^ftXX"););  5f+'); |
35. Pyth        |      pk)K00000"Jabberwocky"   |

(Pyth and CJam thanks to user23013)


Jimmy these arrays down My coworker, Jimmy is kinda new to C/C++. He's also kind of a slow learner. Now, to be fair, his code always compiles, but he has some really sloppy habits. For example, everybody knows that you can define an array like this:
int spam[] = {4, 8, 15, 16, 23, 42};

Everybody that is, except for Jimmy. He is convinced that the only way to make an array is like this:
int spam[6];
spam[0] = 4;
spam[1] = 8;
spam[2] = 15;
spam[3] = 16;
spam[4] = 23;
spam[5] = 42;

I keep fixing this for him in code-review, but he won't learn. So I need you to write a tool that automagically does this for him when he commits¹.
The challenge
I want you to write either a full program or a function that takes in a multiline string as input, and outputs the more compact version of the C array. The input will always follow this format, whitespace included:
identifier_one identifier_two[some_length];
identifier_two[0] = some_number;
identifier_two[1] = some_number;
identifier_two[2] = some_number;
...
identifier_two[some_length - 1] = some_number;

In short, the input will always be valid and well defined C. In more detail:
All of the identifiers will be made up of just letters and underscores. The length will always be at least one, and there will never be any missing or out of bounds indexes. You may also assume that the indexes are in order. For example:
foo bar[3];
bar[0] = 1
bar[2] = 9;

foo bar[1];
bar[0] = 1;
bar[1] = 3;

and
foo bar[3];
bar[2] = 9;
bar[0] = 1
bar[1] = 3

are all invalid inputs, and may cause undefined behavior in your submission. You may also assume that all of the numbers will be valid decimal numbers, negative or positive. The input will not have extraneous spaces. The output should always follow this format, whitespace included:
identifier_one identifier_two[] = {n1, n2, n3, ...};

Here is some sample data:
Input:
spam eggs[10];
eggs[0] = 0;
eggs[1] = 4;
eggs[2] = 8;
eggs[3] = -3;
eggs[4] = 3;
eggs[5] = 7;
eggs[6] = 888;
eggs[7] = 555;
eggs[8] = 0;
eggs[9] = -2;

Output:
spam eggs[] = {0, 4, 8, -3, 3, 7, 888, 555, 0, -2};

Input:
char ans[2];
ans[0] = 52;
ans[1] = 50;

Output:
char ans[] = {52, 50};

Input:
blah_blah quux[1];
quux[0] = 105;

Output:
blah_blah quux[] = {105};

You may take your input and output in any reasonable format, such as STDIN/STDOUT, function arguments and return value, reading and writing files etc. Standard loopholes apply. The shortest answer in bytes wins!

¹This is passive-aggressive and a terrible idea. You did not get this idea from me.

Vim, 43 36 bytes

You don't need to give Jimmy a script, just teach him to use a proper text editor. (literal returns for clarity)

:%s/.*=//|%s/;\n/,/<cr><cr>
3wcf ] = {<esc>
$s};


Husk, 15 14 bytes

zȯḋm←CtNCİ□ṁḋN

Try it online!

Continually prints the results as an infinite list.

Explanation

I wonder whether there's a better way to get every nth element from a list than splitting the list into chunks of length n and retrieving the head of each chunk.

      tN          Get a list of all natural numbers except 1. (A)

             N    Get a list of all natural numbers.
           ṁḋ     Convert each to its binary representation and join them
                  all into a single list.
         İ□       Get a list of squares of all natural numbers.
        C         Cut the list of bits into chunks of corresponding sizes. (B)

zȯ                Zip (A) and (B) together with the following function.
     C            Split the bit list (from B) into chunks of the given length
                  (from A).
   m←             Get the head of each chunk. This is the diagonal of the
                  bit list arranged as a square.
  ḋ               Interpret the resulting bits as binary digits and return
                  the result.

To be clear, we extract the diagonal of an n x n square by splitting its linear form into chunks of length n + 1 and retrieving the first element of each chunk:

[[1 , 0 , 1 , 0
  0],[1 , 0 , 1
  1 , 0],[1 , 0
  0 , 1 , 0],[1]]


Error-detecting Self-repairing Program Your task is to create a program where if any one character is deleted, it will detect which character was deleted and then re-insert the deleted character in its own source file.

For instance, if your program is RadiationHardened and it is modified to RadiaionHardened, then your program must output that the 5th byte (0-indexed) was modified and then the program source must be RadiationHardened immediately after execution.

Notes and rules

You may assume that exactly one character was deleted in the source code before execution. Behavior for the unmodified program is undefined.
You may assume the changed byte will be deleted, not transposed, inserted, or replaced.
In the case of a run of multiple of the same character, you may report either the first or the last index of the run, but be consistent about which you use. For example baaad being deleted to baad can report either 1 or 3 (zero indexed), but must be the same throughout the entire program.
You do not need to write out the entire source to its own file. You need only re-insert the deleted byte.
Unlike the typical rules for radiation-hardened quines, detecting the changed byte from reading the program's own source code is fair game.
You can output the changed byte index through any reasonable format. Be consistent about whether it is 0-indexed or 1-indexed or any other notation. You may even output a number within a template string.

This is code-golf so the shortest program wins.

Good luck!

EDIT1: changed requirement from replacement to deletion

EDIT2: added rule for runs of duplicates

Befunge-98 (FBBI), 344 296 248 bytes

20020xxnngg33%%!!2200gg''00--3300gg33%%!!4400gg55%%!!22kk++55##rr55kk::00gg\\11pp00gg\\11++11pp22++00::pp00gg\\11++00gg--!!zz!!22**++00::gg00gg8844**--!!55++jj..''gg::00rr00::gg\\--..''220011''0011::''002211''223311''00441144kkppgg11001100::99oo@@

Try it online!

Verification!

Befunge-98 is the first esoteric language that I could find that was both 2D and had file output. This is a full solution (with a trailing newline) stored in a file named as a tab character. It outputs as 0-indexed, and outputs the first index in a run of characters (though there's only ever pairs).

There's a few golfs to be made, especially as there are 15 no-ops in the code, now just one no-op! I will be working on making this shorter, with the goal of getting to or below 200 bytes.


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

For reference, the online compiler is here.

@Sp3000 pointed out there is also Tips for Regex Golf. Answers here should focus specifically on Retina features and not on general regex golfing tips.

Combine loops if possible

In non-trivial computations you'll often find yourself using several loops to process data:

+`stage1
+`stage2
+`stage3

So this runs stage1 until the output converges, then stage2 until the output converges and then stage3 until the output converges.

However, it's always worth examining the stages in detail. Sometimes it's possible to run the loop in an interleaved fashion as stage1, stage2, stage3, stage1, stage2, stage3, ... instead (this depends a lot on what the stages actually do, but sometimes they make completely orthogonal changes or work well as a pipeline). In this case you can save bytes by wrapping them in a single loop:

{`stage1
stage2
}`stage3

If stage1 is the first stage or stage3 is the last stage of the program you can then even omit on of those parentheses as well (which means this can already save bytes for a loop of two stages).

A recent use of this technique can be seen in this answer.


Your Base to 1-2-3-Tribonacci to Binary back to Your Base Background

The 1-2-3-Tribonacci Sequence

Imagine for a second that you could make a fibonacci sequence by replacing the standard iteration formula with the following:

Basically, instead of summing the last two to get the next, you sum the last three. This is the basis for the 1-2-3-Tribonacci sequence.

Brown's Criterion

Brown's Criterion state that you may represent any integer value as a sum of members of a sequence provided that:

For all n greater than 1,

What this means for the challenge

You may describe any positive integer as a sum of members of the 1-2-3-Tribonacci sequence formed by the following initial conditions:

This is known as, for every value in this sequence, the ratio between terms is never greater than 2 (the ratio averages out at about 1.839).

How to write in this numerical representation system

Let's say that you use a little-endian representation. Line up members of the sequence like so:

1  2  3  6 11 20 37 68

Then, you take your number to be represented (for our tests, let's say it's 63) and find the values of the given 1-2-3-Tribonacci which sum to 63 (using the largest values first!). If the number is part of the sum, put a 1 under it, 0 if not.

1  2  3  6 11 20 37 68
0  0  0  1  0  1  1  0

You may do this for any given integer - just verify that you use the largest values below your given input first!

Definition (finally)

Write a program or function that will do the following given some positive integer input n (written in any standard base) between 1 and your language's maximum value:

Convert the value into the defined 1-2-3-Tribonacci's numerical representation.
Using this binary-like representation, and read it as if it were binary. This means that the digits stay the same, but what they mean changes.
Take this binary number and convert it into the base of the original number.
Output or return this new number.

However, as long as the output is valid, you needn't follow these steps. If you magically find some formula that is shorter (and mathematically equivalent), feel free to use it.

Examples

Let the function f be the function described by the definition, and let [] represent steps taken (as little-endian, though it shouldn't matter) (you do not need to follow this process, this is just the process described):

>>> f(1)
[1]
[1]
[1]
1

>>> f(5)
[5]
[0, 1, 1]
[6]
6

>>> f(63)
[63]
[0, 0, 0, 1, 0, 1, 1]
[104]
104

Javascript 117 111 bytes

Thanks to @theonlygusti for helping golf off 5 bytes

x=>{r=0;a=[1,2,3];i=1;while(a[++i]<x)a[i+1]=a[i]+a[i-1]+a[i-2];for(;x;i--)if(x>=a[i]){r+=1<<i;x-=a[i]}return r}

How It Works

First, the function generates all tribonacci numbers until it finds one greater than the input

a=[1,2,3];i=1;for(;a[++i]<x;)a[i+1]=a[i]+a[i-1]+a[i-2];

Next, it reverse searches the list of numbers. If a number is less than the input, it adds 2^(index of that number) to the return value and reduces the input by that number.

for(;x;i--)if(x>=a[i]){r+=1<<i;x-=a[i]}

Finally it returns the result.

Try it Online


How do I find the longest palindrome in a string? The challenge:

  Make a function that finds the longest palindrome inside a string.

Note: This is a code-trolling question. Please do not take the question and/or answers seriously. More information here.

Python

def longest_palindrome(s):
    return 'racecar'

Example usage:

>>> print longest_palindrome('I like racecars!')
racecar

Note: this may only work for certain strings.


Chess endgame: White to Mate In One Given an 8x8 grid of letters representing the current state of a game of chess, your program's task is to find a next move for white that results in checkmate (the answer will always be mate in one move).

Input

Input will be on STDIN - 8 lines of 8 characters each. The meanings of each character are as follows:

K/k - king
Q/q - queen
B/b - bishop
N/n - knight
R/r - rook
P/p - pawn
- - empty square

Upper case letters represent white pieces, and lower case represents black.
The board will be oriented so that white is playing up from the bottom and black is playing down from the top.

Output

A move for white that results in checkmate, in algebraic notation. You do not need to notate when a piece has been taken, nor do you need to be concerned about disambiguating between two identical pieces which can make the same move.

Sample input

Example 1

Input:

------R-
--p-kp-p
-----n--
--PPK---
p----P-r
B-------
--------
--------

Output:

c6

Example 2

Input:

--b-r--r
ppq-kp-p
-np-pn-B
--------
---N----
--P----P
PP---PP-
R--QRBK-

Output:

Nf5

Example 3

Input:

---r-nr-
-pqb-p-k
pn--p-p-
R-------
--------
-P-B-N-P
-BP--PP-
---QR-K-

Output:

Rh5

You can assume that the solution will not involve castling or en-passant.

This is code-golf - shortest solution wins.

(Examples taken from mateinone.com - puzzles 81, 82 and 83)

Ruby, 589 512 510 499 493 characters
R=0..7
a=->b{o=[];R.map{|r|R.map{|c|v=Hash[?K,[6,7,8,11,13,16,17,18],?R,s=[157,161,163,167],?B,t=[156,158,166,168],?Q,s+t,?N,[1,3,5,9,15,19,21,23],?P,[32,181,183]][z=b[r][c]];v&&v.map{|s|k=2!=l=s/25+1;u=r;v=c;l.times{u+=s/5%5-2;v+=s%5-2;R===u&&R===v||break;t=b[u][v];j=t<?.&&l<8;(j||t=~/[a-z]/&&k)&&o<<=(h=b.map &:swapcase;h[u][v]=h[r][c];h[r][c]=?-;[z+"%c%d"%[97+v,8-u],h.reverse]);j&&(k||r==6)||break}}}};o}
a[$<.map{|l|l}].map{|m,b|a[b].any?{|f,x|a[x].all?{|g,y|y*""=~/K/}}||$><<m[/[^P]+/]}

Input is given via stdin, e.g.:
> ruby mateinone.rb
--------
--------
--------
-k------
b-------
-N-P----
--------
-----K-Q
^Z
Qb7

The output is not just one move that forces a mate in one but every move that does so.
Edit 1: The function e was used only once so I inlined it. Second, the encoding now is based on number 5 instead of 10. And refactoring the cloning of the board saved quite a few chars.
Edit 2: Still not as much improvement as I wanted. Changing the hash from {a=>b,c=>d} to Hash[a,b,c,d]. This costs 4 characters but saves one per key-value pair.
Edit 3: Only minor reductions: inlining M (4 characters), t==?- -> t<?. (2), removing Pawn in algebraic notation at the end (2), replaced puts (3). The program is now less than 500 characters.
Edit 4: It is interesting how much one can still find in such a program. Moved an invariant outside the loop and found another duplicate calculation.


Decipher the mathematical symbols If you've read the book Contact by Carl Sagan, this challenge may seem
familiar to you.

Given an input of a set of mathematical equations consisting of a number, an
unknown operator, another number, and a result, deduce which operators
represent addition, subtraction, multiplication, or division.

Each input equation will always consist of

a non-negative integer
one of the letters A, B, C, or D
another non-negative integer
the character =
a final non-negative integer

concatenated together. For example, a possible input is 1A2=3, from which you
can deduce that A represents addition. Each of the integers will satisfy 0 ≤ x ≤ 1,000.

However, it's not always as simple as that. It is possible for there to be
ambiguity between:

5A0=5: addition/subtraction
1A1=1: multiplication/division
0A5=0: multiplication/division
2A2=4: addition/multiplication
4A2=2: subtraction/division
0A0=0: addition/subtraction/multiplication

and so on. The challenge is to use this ability to narrow down choices,
combined with process of elimination, to figure out what operator each letter
represents. (There will always be at least one input equation, and it will
always be possible to unambiguously, uniquely match each letter used in the input with a single operator.)

For example, let's say the input is the following equations:

0A0=0: this narrows A down to addition, subtraction, or multiplication
(can't divide by 0).
10B0=10: B has to be either addition or subtraction.
5C5=10: C is obviously addition, which makes B subtraction, which makes A
multiplication.

Therefore, the output for these input equations should match A with *, B
with -, and C with +.

Input may be given as either a single whitespace-/comma-delimited string or
an array of strings, each representing one equation. Output may be either a
single string ("A*B-C+"), an array (["A*", "B-", "C+"]), or a dictionary / dict-like 2D array ({"A": "*", ...} or [["A", "*"], ...]).

You may assume that a number will never be divided by another number it isn't divisible by (so, you don't need to worry about whether division should be floating point or truncated).

Since this is code-golf, the shortest code in bytes wins.

Test cases:

In                       Out
-------------------------------
0A0=0 10B0=10 5C5=10     A*B-C+
100D100=10000            D*
4A2=2 4B2=2 0A0=0        A-B/
15A0=15 4B2=2 2C2=0      A+B/C-
1A1=1 0A0=0              A*
0A0=0 2A2=4 5B0=5 2B2=4  A*B+
2A2=4 0C0=0 5B0=5 5A0=5  A+B-C*
0A1000=0 4A2=2           A/

MATL, 53 bytes
j61tthYX'+-*/'X{Y@!"t'ABCD'!XKX{@YXU?K@Y}hwxKGm1L3$).

Uses current version (10.1.0)
EDIT (June 12, 2016): to adapt to changes in the language, replace Y} by g and 1L3$) by Y). The link below incorporates those modifications
Try it online!
Explanation
This tests all possible permutations of the four operators in a loop until one permutation makes all equations true.
To test if equations are true, a regex is applied to replace the four letters by the operators (in the order dictated by the current permutation), and the string is converted to numbers (evaluated). This gives an array with as many numbers as equations, in which equations that are true become 1 and equations that are false become 0. If this vector only contains 1 values, we're done.
The solution found assigns operators to the four letters, but not all of them necessarily appear in the input. So a final test is done to discard not used letters (and their matching operators).
j            % input data string
61           % '=' (ASCII)
tth          % duplicate twice and concat: '==' (ASCII)
YX           % regexprep to change '=' into '==' in input string
'+-*/'       % push string
X{           % transform into cell array {'+','-','*','/'}
Y@!          % all permutations, each in a column
"            % "for" loop. Iterate columns (that is, permutations)
  t          %   duplicate data string containing '=='
  'ABCD'!XK  %   create column array ['A';'B';'C';'D'] and copy to clipboard K
  X{         %   transform into column cell array {'A';'B';'C';'D'}
  @          %   push column cell array with current permutation of operator symbols
  YX         %   regexprep. Replaces 'A',...,'D' with current permutation of operators
  U          %   convert to numbers, i.e. evaluate string
  ?          %   if all numbers are 1 (truthy result): found it! But before breaking...
    K        %     push column array ['A';'B';'C';'D']
    @Y}      %     push column array with current permutation of operator symbols
    h        %     concatenate horizontally into 4x2 char array
    wx       %     delete original input so it won't be displayed
    K        %     push ['A';'B';'C';'D']
    G        %     push input string
    m        %     logical index that tells which of 'A',...,'D' were in input string
    1L3$)    %     apply that index to select rows of the 4x2 char array
    .        %     we can now break "for" loop
             %   implicitly end "if"
             % implicitly end "for"
             % implicitly display stack contents


Plight of the Concorde Background

The traveling salesman problem (TSP) asks for the shortest circuit that visits a given collection of cities.  For the purposes of this question, the cities will be points in the plane and the distances between them will be the usual Euclidean distances (rounded to the nearest integer).  The circuit must be "round-trip", meaning it must return to the starting city.

The Concorde TSP solver can solve instances of the Euclidean traveling salesman problem, exactly and much faster than one would expect.  For example, Concorde was able to solve an 85,900-point instance exactly, parts of which look like this:

However, some TSP instances take too long, even for Concorde.  For example, no one has been able to solve this 100,000-point instance based on the Mona Lisa.  (There is a $1,000 prize offered if you can solve it!)

Concorde is available for download as source code or an executable.  By default, it uses the built-in linear program (LP) solver QSopt, but it can also use better LP solvers like CPLEX.

The challenge

What is the smallest TSP instance you can generate that takes Concorde more than five minutes to solve?

You can write a program to output the instance, or use any other method you would like.

Scoring

The fewer points in the instance the better.  Ties will be broken by the file size of the instance (see below).

Standardization

Different computers run faster or slower, so we will use the NEOS Server for Concorde as the standard of measurement for runtime.  You can submit a list of points in the following simple 2-d coordinate form:

#cities
x_0 y_0
x_1 y_1
.
.
.
x_n-1 y_n-1

The settings that should be used on NEOS are "Concorde data(xy-list file, L2 norm)", "Algorithm: Concorde(QSopt)", and "Random seed: fixed".

Baseline

The 1,889-point instance rl1889.tsp from TSPLIB takes "Total Running Time: 871.18 (seconds)", which is more than five minutes.  It looks like this:

88 Cities, 341 seconds runtime on NEOS

In a recent paper we constructed a family of hard to solve euclidean TSP instances. You can download the instances from this family as well as code for generating them here:

http://www.or.uni-bonn.de/%7Ehougardy/HardTSPInstances.html

The 88 city instance from this family takes Concorde on the NEOS server more than 5 minutes. The 178-city instance from this family takes already more than a day to solve.


Generate the set of prepend-append permutations in lexicographically sorted order Define a prepend-append sequence of length n to be a permutation of the numbers 1, 2, ..., n that can be generated by the following procedure:

Start with the number 1.
For each number from 2 to n, place this number to the beginning or end of the sequence (either prepend or append it, hence the name of the sequence).

For example, this is a valid way to generate a prepend-append sequence of length 4:

1
21     [beginning]
213    [end]
2134   [end]

Your task is to build a program or function that will take a number n from 3 to 30 as input, and print or return all prepend-append sequences of length n in lexicographical order (if you're outputting strings and not lists, numbers above 9 will be represented as letters a-u, to preserve string length). For example, this is that order for n = 4:

1234  [RRR]
2134  [LRR]
3124  [RLR]
3214  [LLR]
4123  [RRL]
4213  [LRL]
4312  [RLL]
4321  [LLL]

In general, there are 2n-1 prepend-append permutations of length n.

You may not use any built-in sorting functions in your language in your code. The shortest program to do this in any language wins.

CJam, 22 20 19 17 bytes

]]l~{)f+_1fm>|}/p

Code expansion:

]]                   "Put [[]] onto stack. What we will do with this array of array is";
                     "that in each iteration below, we will first append the next";
                     "number to all present arrays, then copy all the arrays and";
                     "move the last element to first in the copy";
  l~                 "Read input number. Lets call it N";
    {         }/     "Run this code block N times ranging from 0 to N - 1";
     )f+             "Since the number on stack starts from 0, add 1 to it and append";
                     "it to all arrays in the array of array beginning with [[]]";
        _1fm>        "Copy the array of array and move last element from all arrays";
                     "to their beginning";
             |       "Take set union of the two arrays, thus joining them and eliminating";
                     "duplicates. Since we started with and empty array and started adding";
                     "numbers from 1 instead of 2, [1] would have appeared twice if we had";
                     "simply done a concat";
                p    "Print the array of arrays";

How it works:

This is a debug version of the code:

]]l~ed{)edf+ed_ed1fm>ed|ed}/edp

Let's see how it works for input 3:

[[[]] 3]                                 "]]l~"            "Empty array of array and input";
[[[]] 1]                                 "{)"              "First iteration, increment 0";
[[[1]]]                                  "{)f+"            "Append it to all sub arrays";
[[[1]] [[1]]]                            "{)f+_"           "Copy the final array of array";
[[[1]] [[1]]]                            "{)f+_1fm>"       "shift last element of each";
                                                           "sub array to the beginning";
[[[1]]]                                  "{)f+_1fm>|}"     "Take set based union";
[[[1]] 2]                                "{)"              "2nd iteration. Repeat";
[[[1 2]]]                                "{)f+"
[[[1 2]] [[1 2]]]                        "{)f+_";
[[[1 2]] [[2 1]]]                        "{)f+_1fm>";
[[[1 2] [2 1]]]                          "{)f+_1fm>|}";
[[[1 2] [2 1]] 3]                        "{)";
[[[1 2 3] [2 1 3]]]                      "{)f+"
[[[1 2 3] [2 1 3]] [[1 2 3] [2 1 3]]]    "{)f+_";
[[[1 2 3] [2 1 3]] [[3 1 2] [3 2 1]]]    "{)f+_1fm>";
[[[1 2 3] [2 1 3] [3 1 2] [3 2 1]]]      "{)f+_1fm>|}";
[[[1 2 3] [2 1 3] [3 1 2] [3 2 1]]]      "{)f+_1fm>|}/";

Try it online here


Convert a Forsyth-Edwards Notation string to ASCII art In chess, Forsyth-Edwards Notation, more commonly called "FEN", is a textual way of transcribing boards. It describes each of the board's eight rows (called "ranks" in chess) from top to bottom from White's perspective. The pieces are written as K (king), Q (queen), R (rook), B (bishop), N (knight), and P (pawn). Black pieces use these letters in lowercase, and white pieces use these letters in uppercase. Empty spaces are indicated by a number from 1 to 8 indicating how many consecutive empty spaces there are. A completely empty rank would be 8, a single black rook in the rightmost column (called "files" in chess) would be 7r, and two white pawns on each end of a row would be PP4PP. Ranks are separated by a /. There is normally other information added, indicating which side is to move, castling and en passant rights, move number, and halfmove clock, but we will ignore them for the purposes of this challenge.

Input

A FEN string, from the command line or STDIN, as you please. You may assume that this string is always valid.

Output

Write to STDOUT a simple ASCII art representation of the board as it would actually appear:

Pieces are represented by their character in FEN
Empty squares are represented by spaces
Pieces and squares are separated by a pipe | and there are pipes on each side of the board

So an empty board, written as 8/8/8/8/8/8/8/8 in FEN, would appear as

| | | | | | | | |
| | | | | | | | |
| | | | | | | | |
| | | | | | | | |
| | | | | | | | |
| | | | | | | | |
| | | | | | | | |
| | | | | | | | |

The starting position of a chess game is written as rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR, and would appear as

|r|n|b|q|k|b|n|r|
|p|p|p|p|p|p|p|p|
| | | | | | | | |
| | | | | | | | |
| | | | | | | | |
| | | | | | | | |
|P|P|P|P|P|P|P|P|
|R|N|B|Q|K|B|N|R|

The final position of Anderssen-Kieseritzky 1851, called "The Immortal Game" in the chess community, is written as r1bk3r/p2pBpNp/n4n2/1p1NP2P/6P1/3P4/P1P1K3/q5b1, and your program when fed that input would output:

|r| |b|k| | | |r|
|p| | |p|B|p|N|p|
|n| | | | |n| | |
| |p| |N|P| | |P|
| | | | | | |P| |
| | | |P| | | | |
|P| |P| |K| | | |
|q| | | | | |b| |

Retina, 13 bytes

\d
$*
/
¶

|

Try it online!

Explanation

The first part (note the trailing space):

\d
$*

is to convert a to the specific number of spaces. Retina has a $* feature to repeat. The way it works is: <num>$*<char> if there is no <num>, Retina will assume $& or the matched string, in this case the matched number.

The next part:

/
¶

is pretty simple, it replaces all / with ¶ which is a newline.

The last part works the same:

|

This will replace everything (hence why there is nothing on the first line) with |. Putting a | everywhere.


Let's golf a BIBABOBU decoder While I was traveling in the future, I noticed a funny game among kids circa 2275. When they don't want their great-great-great-great-grand parents to understand what they're saying, they use the BIBABOBU speak. Obviously, I couldn't understand anything either with my pre-cyborg era brain and I felt (or technically: I will feel) really silly. So, I'd need a decoder for my next visit.

BIBABOBU?

While it's been deprecated for a long time, ASCII is still commonly used in the pop culture of 2275 and this language is based upon it.

A string is BIBABOBU-encoded that way:

Convert all characters to their ASCII codes.
Take the 2-digit hexadecimal representation of each code and convert them using the following table:

0: BI  4: BIDI  8: BADI  C: BODI
1: BA  5: BIDA  9: BADA  D: BODA
2: BO  6: BIDO  A: BADO  E: BODO
3: BU  7: BIDU  B: BADU  F: BODU

Example

"Hello!" → 48 65 6C 6C 6F 21 → "BIDIBADI BIDOBIDA BIDOBODI BIDOBODI BIDOBODU BOBA"

However, the corresponding input would be given without any space to mimic the monotonous intonation that kids are using to make this even harder to understand without implants:

"BIDIBADIBIDOBIDABIDOBODIBIDOBODIBIDOBODUBOBA"

Clarifications and rules

Remember that I need a decoder, not an encoder.
Decoded characters are guaranteed to be in the range [ 32...126 ].
The input is guaranteed to contain en even number of BIBABOBU-encoded hexadecimal digits.
You may take input in either full lowercase or full uppercase. Mixed cases are not allowed.
Because bit flips are quite common during a time travel, this is code-golf in order to minimize the risks.

Test cases

NB: Linefeeds are used below for formatting purposes only. You are not supposed to handle them.

Input:
BIDABIDIBIDOBIDABIDUBUBIDUBIDI

Output:
Test

Input:
BIDABIDUBIDOBIDABIDOBODIBIDOBUBIDOBODUBIDOBODABIDOBIDABOBIBIDUBIDIBIDOBODUBOBIBUBOBUBOBUBI
DUBUBIDABOBA

Output:
Welcome to 2275!

Input:
BIDIBADIBIDOBIDABIDOBODIBIDOBODIBIDOBODUBOBODIBOBIBIDABIDIBIDOBADABIDOBODABIDOBIDABOBIBIDA
BIDIBIDUBOBIDOBABIDUBIDOBIDOBIDABIDOBODIBIDOBIDABIDUBOBOBABOBIBIDABADABIDOBODUBIDUBIDABOBI
BIDOBODIBIDOBODUBIDOBODUBIDOBADUBOBIBIDUBUBIDOBODUBOBIBIDOBIDOBIDUBIDABIDOBODOBIDOBODOBIDU
BADABOBA

Output:
Hello, Time Traveler! You look so funny!

Input:
BIDIBABIDOBODOBIDOBIDIBOBIBIDUBADABIDOBODUBIDUBIDABOBIBIDOBIDIBIDOBODUBIDOBODOBOBIDUBIDUBI
DIBOBIBIDUBIDABIDOBODOBIDOBIDIBIDOBIDABIDUBOBIDUBUBIDUBIDIBIDOBABIDOBODOBIDOBIDIBOBIBIDUBI
DUBIDOBADIBIDOBABIDUBIDIBOBIBIDIBADABOBIDUBIDOBODABOBIBIDUBUBIDOBABIDUBADABIDOBADABIDOBODO
BIDOBIDUBOBODIBOBIBIDOBIDIBIDOBODUBOBIBIDUBADABIDOBODUBIDUBIDABUBODUBOBIBIDIBADIBIDOBABOBI
BIDOBADIBIDOBABOBIBIDOBADIBIDOBABOBA

Output:
And you don't understand what I'm saying, do you? Ha ha ha!

05AB1E, 36 35 33 bytes

Saved 1 byte thanks to Mr.Xcoder
Saved 2 bytes thanks to KevinCruijssen

ć©¡®ì®D…IAO©â'D«‚˜®'U«âJskh2ôJHçJ

Try it online!
or as a Test Suite

Explanation

ć©¡                                 # extract the head ("B") and split input on it
   ®ì                              # prepend "B" to each
     ®D                            # push 2 copies of "B"
       …IAO©â                      # cartesian product with "IAO"
             'D«                   # append "D" to each
                ‚˜                 # add the leftover "B" to the list
                  ®'U«â            # cartesian product with "IAOU"
                       J           # join each to string
                        sk         # get the index of each word of the input in this list
                          h        # convert each to hex
                           2ôJ     # format as pairs of chars
                              H    # convert to int
                               çJ  # convert from ascii-codes to string


Convert Chevrons to Soliduses Write a program that takes in a string containing only spaces, newlines, and angle brackets: <, > (chevrons). Output a string of spaces, newlines, and slashes: /, \ (soliduses) whose shapes correspond to the input, but rotated a quarter turn clockwise, with a column of spaces inserted between each row of the original input (for aesthetics).

For example, if the input is this:

<>

The output would be this:

/\
\/

If the input is this:

><<<>
 <><

The output would be this:

   \/
/\ /\
\/ /\
/\ /\
   \/

If the input is this:

>>  <<
<>  <>
  <
  ><

The output would be this:

      /\ \/
      \/ \/
\/ /\
/\
      /\ /\
      \/ /\

Notice how there is a single column of spaces between the original input rows in the last two examples.

You may write a full program that takes the input in any usual way (command line, stdin) and prints the output, or you may write a function with a string argument, that prints or returns the output.

Empty leading and trailing rows or columns of whitespace in the input do not need to be present in the output. Additionally, there may be any amount of leading and/or trailing spaces and/or newlines in the output, in any locations, as long as the resulting shapes are correct. In other words, the translation of the ascii art does not matter, only the shapes and their relation to one another do.

You may optionally assume the input has a trailing newline.

The shortest code in bytes wins.

CJam, 35 bytes
qN/_s,S*f+{iD%[S3*" \/"_$]=}f%W%zN*

Try it online here


List of programming languages that can run code at runtime What all languages have a construct similar to python's eval, so you can write code during runtime and run it?

A list would be helpful for certain programming challenges - ones where it is obvious an eval is either necessary or highly efficient.

A few I recall:

Lua: loadstring("2 + 2")
*Script (Coffee, Java, Type, Action): eval("2 + 2")
Erlang / Elixir: Code.eval_string("a + b", [a: 2, b: 2], file: __ENV__.file, line: __ENV__.line)
J: ". '2 + 2' (eval it right away) or 3 : '2 + 2' (define a function; (3 : '2 + 2') 0 runs it)
Ruby: eval "2 + 2"
Perl: eval "2 + 2"
Bash: a="ls | wc -l", eval $a
PHP: eval("2 + 2")
Lisp, obviously: (setq test'(+ 2 2)) and (eval test)
Python: eval('2 + 2')
ColdFusion: <cfset x = "int(2+2)"> and <cfset y = Evaluate(x)>
FORTH: S" 2 2 + ." eval (note: it depends on the implementation; most use either EVALUATE or eval)
VBScript, VBA: Execute('2 + 2') (note: for VBA as far as I recall, it's eval)
Smalltalk: Compiler evaluate:'2 + 2'
APL: The ⍎ primitive executes a character vector that contains a valid APL expression: ⍎ '2×3' or ⍎ 'S←A String'. The former will execute the mathematical expression and return 6; the latter will create a variable S in the APL workspace, and assign it the value A String
PowerShell: invoke-expression '2 + 2'
R: eval(parse(text = "2 + 2"))
Io: doString("2 + 2")
Burlesque: "2 2.+"pe

Other languages:

Java: see ScriptEngine functionality.
C, C++: they can execute shellcode
D: via mixins, int a = 0; and then mixin("a = 2 + 2;"); (note: the string must be constant and known at the compile time)


Get thee behind me Satan-Prime! Satan-Primes
who are they?
they are Primes containing 666
these are Satan-Primes:[46663,266677,666599,666683,616669]
these are NOT :[462667,665669,36363631,555]
Plot
Every number bigger than 6661 has Satan-Primes behind him
The Challenge
Given an integer n>6661 find the Satan-Prime behind (or equal) and closest to itself.
Examples
Integer n=30000 has 3 Satan-Primes(SP) behind it:[6661, 16661, 26669].
Your code must return 26669 which is the closest behind it
Test Cases
Input->Output
6662->6661
10000->6661
66697->66697 (a SP returns himself)
328765->326663
678987->676661
969696->966677

Rules
Yor code should work for any n in the range of your language.
This is code-golf, so the shortest answer in bytes wins!

Neim, 9 bytes

>ͻ:D+6S÷

Explanation:

>         Increment input
 ͻ        Start infinite loop
  :        Previous prime
   D       Duplicate
    +6     Push 666
      S    Swap
          See if 666 is a substring of the top of the stack
        ÷  If true, break

Try it online!


Converting Strings to Decimals (Gone Wrong) What?
Many programming languages, both practical and esoteric, have functions, methods, etc to convert a given string to a decimal number. This is how the process might work:

For each character in the given string.

Take the character's ASCII value and subtract it by 48.
Multiply the output value by 10. (The output at the first iteration is 0)
Add the subtracted ASCII value to the output.

Let us do this process for the string "109":

The ASCII value of 1 is 49. Subtract it by 48, and we get 1. We multiply the output by 10, we get 0. Finally, we add 1 to 0 and get one.

Next, we subtract 0's ASCII value (48) by 48, we get 0. We multiply 1 by 10, we get 10. Nothing happens when we add 0.

Then we subtract 9's ASCII value (57) by 48, we get 9. We multiply 10 by 10 and get 100. We add 9 to 100 and get 109.

There, we successfully converted "109" to 109! It is just as simple!
The problem is that most languages do not like it when the converting string has non-digital characters (characters with an ASCII value not in the range 48-57 inclusive). They would most likely throw some nasty errors or exceptions at us.
How 'bout we ignore that!
Task
Given a printable string from STDIN (you can assume that \$1 ≤ \text{Input Length} ≤ 10\$), implement a program or function to badly convert it to an integer according to the above steps, and output or return it back.
Strings can contain whitespace characters (Spaces, tabs and linefeeds).
For another example string "Hi!":

The ASCII value of H is 72:
72 - 48 = 24
0 * 10 = 0
0 + 24 = 24

The ASCII value of i is 105:
105 - 48 = 57
24 * 10 = 240
240 + 57 = 297.

The ASCII value of ! is 33:
33 - 48 = -15
297 * 10 = 2970
2970 + -15 = 2955

This means that "Hi!" converted to an integer is 2955!
Standard I/O rules apply.
Note: if your language does not support input, feel free to tell me in your answers (you can put the "input" strings in your source code)!
More test cases
STDIN                  Output
"123456789"         ->  123456789
"0123456789"        ->  123456789
"-12345"            -> -287655
"Lorem"             ->  350191
"Ipsum"             ->  321451
"AAAAAAAA"          ->  188888887
"        "          -> -177777776
"A"                 ->  17
" "                 -> -16
"
"                   -> -38

Standard code-golf rules apply!

Shakespeare Programming Language, 258 252 bytes
-6 bytes thanks to the default.
,.Ajax,.Puck,.Act I:.Scene I:.[Exeunt][Enter Ajax and Puck]
Ajax:Open mind.
Puck:Is I nicer zero?If soYou is the sum ofI twice the difference
     betweenthe product ofyou the sum ofa cat a big big cat the factorial
     ofa big big cat.
     If soLet usAct I.Open heart

Try it online!
The golfiest representation of the integer 48 is as twice the factorial of a big big cat, i.e. \$48=2\times (2\times2\times1)!\$.
This corresponds to
Ajax = 0
Puck = 0
Begin Act I
Puck = read_input (as ASCII codepoint value)
if(Puck>0){
    Ajax = Puck + 2 * (Ajax * (4+1) - 4!)
    Go to Act I
}
print(Ajax) (as an integer)


Generate math problems Generate math problems (addition, subtraction, or multiplication) using numbers 0-10. Provide feedback on whether the user was right or wrong and show a score.

Specifics:

Must generate addition, subtraction, or multiplication problems
Numbers used must be 0-10
Each problem must be equally likely
If user is correct, must print "correct!" (with the exclamation point)
If user is wrong, must print "wrong!" (with the exclamation point)
After providing correct or wrong feedback, must show score with these specifications:

Starts with "Score:"
Shows number correct and then "correct"
Pipe (|) separation
Shows number wrong and then "wrong"
2 newlines for separation

Must repeat forever

For counting characters, the Text Mechanic counter will be used.

Sample session:

1-7=-6
correct!
Score: 1 correct | 0 wrong

9+3=12
correct!
Score: 2 correct | 0 wrong

4*5=20
correct!
Score: 3 correct | 0 wrong

7-8=3
wrong!
Score: 3 correct | 1 wrong

1*1=3
wrong!
Score: 3 correct | 2 wrong

7+6=

Post-mortem update:

Perl 130 bytes

Combining techniques from dan1111's excellent solution with my own, I was able to squeeze one more byte:

@b=qw(Score: 0 correct | 0 wrong);$b[$#x=eval^<>?4:1]++while print"$b[@x]!
@b

"x/./,$_=(0|rand 11).chr(41^2+rand 3).~~rand 11,'='

There's a few things that might not be immediately obvious. If @x is an array, then $#x (the largest index of @x) will be one smaller than the length of @x. In this way, I can use $#x to point to the appropriate counting variable, and the length of @x to the corresponding message in a single assignment, without having to +1. The score string is repeating by /./, which will return 1 if an only if $_ is non-empty.

Perl 131 bytes

Here's my Perl attempt, which is more or less a direct translation of my PHP solution below.

@r=correct,${_^($n=eval^<>?z:r)}++while@z=wrong,print"@$n!
Score: $- @r | $% @z

"x@r,$_=(0|rand 11).chr(41^2+rand 3).~~rand 11,'='

$- and $% are used for counting variables as they default to 0, alleviating the need for a printf, and at the same time allowing me to combine the print statements into one. The score string is not printed the first iteration because @r has not yet been defined, and therefore x@r (repeat by the length of the array @r) repeats the string zero times, resulting in an empty string.

Once again using chr(41^2+rand 3) to generate +*-, as well as a bitwise xor _^ to switch between r→- and z→%. I would have liked to use a type glob for *n=eval^<>?z:r, saving a byte @$n→@n, but unfortunately typed as a string this comes back as either *main::r or *main::z, which isn't very useful.

</bandwagon>

PHP 157 (155) bytes

Just to get a smattering of languages:

<?for($X=$Y=+$x=correct;$y=wrong;)echo$q=rand(0,10).chr(rand(2,4)^41).rand(0,10),'=',eval("\${_&\$n=$q^fgets(STDIN)?y:x}++;"),$$n,"!
Score: $X $x | $Y $y

";

The initial $X=$Y=+ is necessary, because undefined variables print as an empty string, instead of 0. Unfortunate, but still shorter than using a printf. One thing to notice is the 'magic formula' chr(rand(2,4)^41). 2^41 = 43 (+), 3^41 = 42 (*) and 4^41 = 45 (-). chr(rand(3,5)^46) would also work, but in a different order.

This can be made 2 bytes shorter by using a few binary characters:

<?for($‡=$†=+$x=correct;$y=wrong;)echo$q=rand(0,10).chr(rand(2,4)^41).rand(0,10),~Â,eval("\${~\$n=$q^fgets(STDIN)?y:x}++;"),$$n,"!
Score: $‡ $x | $† $y

";

where †, ‡ and Â are characters 134, 135 and 194 respectively.


Numbers that are actually letters Given a non-negative integer input, write a program that converts the number to hexadecimal and returns a truthy value if the hexadecimal form of the number contains only the characters A through F and a falsey value otherwise.

Test cases

10
==> True (A in hexadecimal)

100
==> False (64 in hexadecimal)

161
==> False (A1 in hexadecimal)

11259375
==> True (ABCDEF in hexadecimal)

0
==> False (0 in hexadecimal)

Bonus: -40 bytes if your program prints Only letters for the challenge described above, Only numbers if the hexadecimal version of the number only contains the digits 0-9 and Mix if the hexadecimal number contains at least one number and at least one letter.

This is code golf. Standard rules apply. Shortest code in bytes wins. Either functions or full programs are allowed.

Pyth, 43 - 40 = 3 bytes

?&K@J.HQG-JG"Mix"%"Only %sers"?K"lett""numb

Test suite

This achieves the bonus. Only numbers and Only letters fortunately only differ by 4 letters. printf-style formatting is used with %.

The selection system is done by both taking the intersection of the hex with G, the alphabet, and subtracting out G. If neither ends up falsy, it's a mix, while if the intersection is falsy, it's numbers, and if the subtraction is falsy, it's letters.