Shortest code to make a Too-low --- Too-high game

Perl 5.10+: 159 144 bytes − 350 = −206 points

say"Guess 16 bit signed number";$==32767-rand 65536;say(TOO.$",$_<0?LOW:HIGH)while++$i,$_=<>-$=;say"Congrats! You found the number in $i turns!"

Edit 2: With the recent rules change that allows me to use any string literal for the "congrats" message, I can save 15 bytes from my original 159-byte solution.  There's nothing particularly novel or interesting about the new code above as compared to the old code (I just got rid of the p function, and call say directly instead), so the remainder of this post will describe the original code, shown below:

sub p{say join$",@_}p Guess,16,bit,signed,number;$==32767-rand 65536;p(TOO,$_<0?LOW:HIGH)while++$i,$_=<>-$=;p Congrats."!",You,found,the,number,in,$i,turns."!"

Yeah, I'm abusing the hell out of rule 1.  Who needs strings, when you can have barewords? ;-)

Run with perl -M5.010 to enable the Perl 5.10+ say feature (or replace the body of the p function with print join$",@_,$/ for an extra cost of 5 bytes).

Bonus scores:

−300 points: "display the game rules before starting the game"
−50 points: "display number of turns taken in the end of game"

The code contains no string literals in a strict sense, so I'd say that rule 1 is, technically, not violated.  The trick is that, in Perl, without use strict, any identifier that doesn't correspond to a known language keyword or subroutine will simple evaluate to its own name.  The function p then simply takes a list of words and prints them out, separated by spaces.

Example play-through:

Guess 16 bit signed number
0
TOO HIGH
-10000
TOO LOW
-5000
TOO HIGH
-7500
TOO LOW
-6250
TOO HIGH
-6875
TOO LOW
-6553
TOO HIGH
-6700
TOO HIGH
-6790
TOO LOW
-6745
TOO HIGH
-6767
TOO LOW
-6756
TOO HIGH
-6761
Congrats! You found the number in 13 turns!

Edit: Oh, right, the rules say I need to post an un-golfed version of the code too, so here it goes.  Technically, it's "de-golfed", since I usually compose my code golf programs in more or less fully golfed form from the beginning, and it can sometimes be tricky to remove all the "golfy" optimizations without fundamentally changing how some parts of the program work.  Still, I've at least tried to add whitespace, comments and more meaningful function / variable names:

sub output {
    # print all arguments separated by spaces, plus a newline:
    # (in the golfed code, I use the special variable $" instead of " " for a space)
    say join " ", @_;
}

# print the rules:
output Guess, 16, bit, signed, number;

# choose a random number between -32768 and 32767 inclusive:
# (in the golfed version, using the special variable $= allows
# the int() to be left out, since $= can only take integer values)
$number = int( 32767 - rand 65536 );

# loop until the input equals the chosen number, printing "TOO LOW / HIGH":
# (the loop ends when $diff == 0, since 0 is false in Perl)
output (TOO, $diff < 0 ? LOW : HIGH) while ++$count, $diff = (<> - $number);

# print congratulations, including the loop count:
output Congrats."!", You, found, the, number, in, $count, turns."!";

Ps. As an alternative, if just using barewords instead of strings feels too cheaty for you, here's a 182-byte solution that doesn't use the letters TOLWHIG even in barewords (but does use them in a transliteration operator).  It still gets the same bonuses, for a total score of 182 − 350 = −168 points:

sub t{pop=~y/kpqvxyz/tolwhig/r}say"Guess 16 bit signed number";$==32767-rand 65536;say uc t"kpp ".($_<0?qpv:xyzx)while++$n,$_=<>-$=;say t"Cpnzraks! Ypu fpund kxe number yn $n kurns!"

The output looks exactly the same as above.  Per the (original) rules, I do use the letters t and i in printing the rules, since it's allowed; eliminating even those uses would only cost two extra bytes, though.  Conversely, making all the output uppercase (which, based on comments above, seems to be allowed) would let me save three bytes.


MATLAB/Octave, 58 56 55  bytes
Thanks @LuisMendo for -1 byte!
input('');tic;for k=1:7;input('');end;fix(48e3/toc)/100

You have to press enter 9 times. (Also works in Octave.)
Here you see it in action, left MATLAB, right Octave:


Python 3, 71
Saved 22 bytes thanks to Ogaday.
Saved 3 bytes thanks to DSM.
Saved a bunch of bytes thanks to an array of bools being valid.
*k,=map(ord,input())
x=65
while x<=max(k):print([v==x for v in k]);x+=1

Takes uppercase command line input.


Sorting by user input. What can be worse?

function sort(array) {
    newArray = new Array
    notSorted = true;
    while (notSorted) {
        sortfail = false;
        i = -1
        for (;;) {
            if ((++i + 1) == array.length) break;
            if (confirm("is " + array[i] + " less than " + array[i + 1])) {
                newArray[i] = array[i]
                newArray[i + 1] = array[i + 1]
            } else {
                newArray[i] = array[i + 1]
                newArray[i + 1] = array[i]
                array[i] = newArray[i]
                array[i + 1] = newArray[i + 1]
                sortfail = true
            }
        }
        array = newArray;
        if (!sortfail) notSorted = false
    }
    return array
}

console.log(sort([2,1,3]))

See live example


Pyth, 40 36 34 32 bytes
-1 byte by @isaacg
JstPz_W}\+zjl#m.[J*\*-J*}\tzyd;J

A semicolon inside a lambda is now the lambda variable's global value, a feature that saves one byte.
                         Implicit: z = input
JstPz                    J = size.
_W }\+z                  Reverse if "+" in z
j l# m                J  Join the nonempty lines in map lambda d:... over range(J)
      .[J            ;   Pad the following with spaces (;) to length J
         *\*               "*", this many times:
            -J*}\tzyd        J if "t" not  in z,
                             otherwise the correct number for a triangle.

Try it here.
Test suite.


Python

for i in `n`:print' ottffssennwhoiieiieoruvxvgn  ere ehe  e   nt'[int(i)::9]

"Inspired" by https://codegolf.stackexchange.com/a/32156/18638


CJam, 109 94 bytes (2nd bonus)
A very naive and long solution
q'#/);{__'*-:A-,_g{){;}*A_}*;'0/{_,g{)~".?~1"a'[,65>292994 5b{/(X):X+\s}%+1:Xm>=\,=}*}%S*1/~}%

This is a full program, although a function will be of the same length.
The input goes into STDIN
Example:
8#99999#055#33#999#***22#666#2#777#3#

Output:
T9 BOARD

Try it online here


The struggling college student's GPA Calculator

Jelly,  15  21 bytes (12 with no rounding)
+6 bytes for the strict formatting (almost certainly possible in less but it's bed time)
Oạ69.Ḟ×S×ȷ2÷⁹S¤RLDż”.

A full program taking the grades and the respective credit hours which prints the calculated GPA (Note: the rounding method is to floor, as allowed in the OP).
Try it online!
With no rounding for 12 bytes:
Oạ69.Ḟ×S÷⁹S¤

How?
Oạ69.Ḟ×S×ȷ2÷⁹S¤RLDż”. - Link: list of characters, grades; list of number, creditHours
                      -                                   e.g. "AFBDC", [5, 2, 4, 1, 2]
O                     - cast to ordinals (vectorises)          [65,70,66,68,67]
  69.                 - literal 69.5
 ạ                    - absolute difference (vectorises)       [4.5,0.5,3.5,1.5,2.5]
     Ḟ                - floor (vectorises)                     [4,0,3,1,2]
      ×               - multiply by creditHours (vectorises)   [20,0,12,1,4]
       S              - sum                                    37
         ȷ2           - literal 100
        ×             - multiply                               3700
              ¤       - nilad followed by link(s) as a nilad:
            ⁹         -   chain's right argument, creditHours  [5, 2, 4, 1, 2]
             S        -   sum                                  14
           ÷          - division                               264.2857142857143
               R      - range                                  [1,2,3,...,264]
                L     - length                                 264
                 D    - digits                                 [2,6,4]
                   ”. - literal '.'
                  ż   - zip together                           [[2,'.'],6,4]
                      - implicit print (smashing)              2.64


Score: 27462
About time I'd compete in a GOLF challenge :D
    # First we look at the last 6 bits of the number. These bits must be
    # one of the following:
    #
    #     0x00, 0x01, 0x04, 0x09, 0x10, 0x11,
    #     0x19, 0x21, 0x24, 0x29, 0x31, 0x39
    #
    # That's 12/64, or a ~80% reduction in composites!
    #
    # Conveniently, a 64 bit number can hold 2**6 binary values. So we can
    # use a single integer as a lookup table, by shifting. After shifting
    # we check if the top bit is set by doing a signed comparison to 0.

    and b, n, 0b111111
    shl v, 0xc840c04048404040, b
    le q, v, 0
    jz no, q
    jz yes, n

    # Hacker's Delight algorithm - Newton-Raphson.
    mov c, 1
    sub x, n, 1
    geu q, x, 2**32-1
    jz skip32, q
    add c, c, 16
    shr x, x, 32
skip32:
    geu q, x, 2**16-1
    jz skip16, q
    add c, c, 8
    shr x, x, 16
skip16:
    geu q, x, 2**8-1
    jz skip8, q
    add c, c, 4
    shr x, x, 8
skip8:
    geu q, x, 2**4-1
    jz skip4, q
    add c, c, 2
    shr x, x, 4
skip4:
    geu q, x, 2**2-1
    add c, c, q

    shl g, 1, c
    shr t, n, c
    add t, t, g
    shr h, t, 1

    leu q, h, g
    jz newton_loop_done, q
newton_loop:
    mov g, h
    divu t, r, n, g
    add t, t, g
    shr h, t, 1
    leu q, h, g
    jnz newton_loop, q
newton_loop_done:

    mulu u, h, g, g
    cmp s, u, n
    halt 0
yes:
    mov s, 1
no:
    halt 0


Repeat every other character in string starting with second character


Mathematica 34 bytes
Here are a few ways to obtain the Pearson product moment correlation.  They all produce the same result.
From Dr. belisarius: 34 bytes
Dot@@Normalize/@(#-Mean@#&)/@{x,y}

Built-in Correlation function I: 15 chars
This assumes that x and y are lists corresponding to each variable.
x~Correlation~y

0.76909

Built-in Correlation function II: 31 chars
This assumes d is a list of ordered pairs.
d[[;;,1]]~Correlation~d[[;;,2]]

0.76909

The use of ;; for All thanks to A Simmons.

Relying on the Standard Deviation function: 118 115 chars
The correlation can be determined by:
s=StandardDeviation;
m=Mean;
n=Length@d;
x=d[[;;,1]];
y=d[[;;,2]];
Sum[((x[[i]]-m@x)/s@x)((y[[i]]-m@y)/s@y),{i,n}]/(n-1)

0.76909

Hand-rolled Correlation: 119 chars
Assuming x and y are lists...
s=Sum;n=Length@d;m@p_:=Tr@p/n;
(s[(x[[i]]-m@x)(y[[i]]-m@y),{i,n}]/Sqrt@(s[(x[[i]]-m@x)^2,{i,n}] s[(y[[i]] - m@y)^2,{i,n}]))

0.76909


Haskell, 655 bytes

u%w=u!!w
r=zip[-1,0,1,1,1,0,-1,-1][-1,-1,-1,0,1,1,1,0]
g _[]_= -1
g i(e:l)x|x==e=i|1>0=g(i+1)l x
l?x=g 0 l x
d _[]_ _=[]
d i(e:l)t v|i==t=v:l|1>0=e:d(i+1)l t v
c=d 0
f n|all(==0).concat.q$n=n|1>0=f$foldr(\p b->s b[k,m]p)n$k!m where
 h=length n-1
 e=mapM(\w->[0..w])[h,h]
 i!j=[[x,y]|[x,y]<-e,x>i-2&&x<i+2&&y>j-2&&y<j+2]
 q o=[[sum[1|[x,y]<-w!l,let
  u=(x-w,y-l)
  p=(w-x,l-y)in u/=p&&('1'==(o%w%l)%(r?u))/=('1'==(o%x%y)%(r?p))]|l<-[0..h]]|w<-[0..h]]
 v[x,y][a,b]|q n%x%y>q n%a%b=[x,y]|1>0=[a,b]
 [k,m]=foldr1 v e
 s w[x,y][a,b]|x==a&&y==b=w|'1'==w%x%y%(r?(a-x,b-y))=z '0'|'1'==w%a%b%(r?(x-a,y-b))=z '1'|1>0=w where z u=c w x$c(w%x)y$c(w%x%y)(r?(a-x,b-y))u

Man... 655 is a lot. I'm sure this isn't the best approach but since no one's answered this challenge yet I figured I would throw something at it.

Input is a list of lists of strings, viz. [[String]] or, equivalently, [[[Char]]]. The string format is "76543210", where the string is a '0' or a '1' in any given position based on whether or not the node points in that corresponding direction. This should conform with the spec:

  7 represents the most significant bit, and 0 the least significant; in other words, the bits are given in the order 76543210.

But the examples below that seem to contradict it, instead doing something more like ?7654321, so I'm not sure.

Test suite:

main :: IO ()
main = print $ f
    [ ["00000100", "00010000", "00000000"]
    , ["00000001", "10000000", "00010000"]
    , ["00000000", "00000000", "10000001"]
    ]

(That's the last test case in the spec^)


Python, 54 + 56 = 110 bytes
Counter:
m=lambda x:sum(y.isspace()for y in x)
+1
0<9or x.split()

Splitter:
m=lambda x:sum(y.isspace()for y in x)+10<9or x.split()

For the counter, we use the fact that Python is okay with having just an expression on a line. It's necessary to split up +1 and 0<9or x.split() to stop a NameError from being thrown, as 0<9 being True prevents x.split() from being evaluated due to short circuiting.
For the splitter, since the number of whitespace is always nonnegative, sum(y.isspace()for y in x)+10<9 is always False and the splitting function comes into play.

Alternative 1, 59 + 60 = 119 bytes
Counter:
m=lambda x:[x.split(),sum(y.isspace()for y in x)][min([1])]

Splitter:
m=lambda x:[x.split(),sum(y.isspace()for y in x)][m in([1])]

The results of both counting and splitting are stored in a two-element list. The list is indexed by either min([1]), returning the minimum of the one-element list containing 1, or m in([1]), which returns False (equivalent to 0) as m is not contained in [1].

Alternative 2, 67 + 69 = 136 bytes
Counter:
ted=1;s=lambda x:[x.split(),sum(y.isspace()for y in x)][not s or ted]

Splitter:
ted=1;s=lambda x:[x.split(),sum(y.isspace()for y in x)][not sorted]

Like above, the results of both counting and splitting are stored in a two-element list. sorted is a built-in function which is a truthy value, so not sorted returns False (equivalent to 0). For not s or ted, since s is a function and also truthy, not s is False and ted = 1 is returned.

Alternative 3, 59 + 60 = 119 bytes
Counter:
def f(s):a=s.split();a1=len(s)-len((s*0).join(a));return a1

Splitter:
def f(s):a=s.split();a1=len(s)-len((s*0).join(a));return a
1

This is a function where splitter's result is stored in the variable a, and counter's result is stored in the variable a1. Like before, Python is fine with having just an expression on a line, in this case 1. Splitting up a1 determines what to return from the function.


TI-BASIC, 13 bytes
For TI-83+/84+ series calculators.
Degree
Input Y
min(ΔList(R►Pθ(Ans,∟Y

To use this program, enter the list {x1,x2} through the Ans variable, and {y1,y2} at the prompt.


Perl, 87 84

open A,f;"@ARGV"eq s/[cs]h/j/gr=~y/stnmrljkfpzdcgqvb\0-z/0-90177789/dr&&print for<A>

Takes input in as the command line parameter:

$perl m.pl 23940

Can be made somewhat shorter if the word list would be allowed on the standard input:

$perl -lnE'INIT{$;=pop}$;eq s/[cs]h/j/gr=~y/stnmrljkfpzdcgqvba-z/0-90177789/dr&&say' 99 <f


Golf the Sequence whose Exponential Generating Function is tangent

CJam (33 32 27 26 23 20 bytes)

2,{ee::*_(@+.+}ri*0=

Online demo

Dissection

This essentially implements the recurrence described by xnor.

2,        e# [0 1] represents the base case f(0,j) = j==1
{         e# Loop...
  ee::*   e#   Multiply each array element by its index
  _(@+.+  e#   Sum the array shifted left and the array shifted right
}ri*      e# ... n times
0=        e# Evaluate at j=0

Or with a rather different approach, for 23 bytes:

ri_1&a{{1$+}*]W%0+}@*0=

Online demo. Thanks to Dennis for 3 bytes.

Dissection

1a         e# Push [1]
{          e# Repeat...
  {1$+}*]  e#   Compute array of partial sums
  W%0+     e#   Reverse and append 0
}qi:A*     e# ... A times, where A is the input value
0=A1&*     e# Result is first element if A odd, and 0 otherwise

Or with a very different approach, for 29 bytes:

qie!Ma-{W\+W+3ew{_$.=1=},!},,

Online demo

Unfortunately a special case is required for input 0.

Dissection

qi            e# Take an integer n from stdin
e!            e#   Compute all permutations of [0 ... n-1]
Ma-           e#   Special-case n=0
{             e#   Filter...
  W\+W+       e#     Prepend and postpend -1
  3ew         e#     Take slices of 3 consecutive elements
  {           e#     Filter...
    _$.=1=    e#       Test whether the middle element is the second largest
  },!         e#     ... and require no matches
},,           e#   ... and count

You may be thinking "WTF?! He's answering the wrong question." If so, that's understandable, but both approaches do indeed give the correct results.


Finding prime numbers without using "prime characters"

CJam, 19 18 30 34 33 19 17 21 20 bytes

Try it online.

{_3\#,2>__ff*:~-<N*}

This is probably one of the most horribly inefficient algorithms I've ever implemented. But I did it for the size!

My answer consists of a code block, which acts like an anonymous function in CJam. Run it with an integer immediately preceding it on the stack, and the resulting list is dumped onto the stack. I treat the upper bound on the input as infinite so I don't have to check that bound.

My algorithm starts by raising 3 to the inputth power, which is guaranteed to give a number larger than the input-th prime if the input is valid. Then a list of the integers from 2 to this number minus one is generated, which is a large enough swath to contain all the prime numbers we want. To get rid of the composite numbers... sigh... we create a list of every pairwise product, which should generate all composite numbers from 4 to some stupidly large value, large enough for our purposes. Then it's just a matter of removing every element from the original list that is in this composite list, trimming it down to the first input elements, and joining the elements with the newline character.

The algorithm should work for any input. However, whether or not the interpreter/computer has enough memory or time is a whole other question, because the time and space requirements are exponential with respect to the input. So if the input is larger than about 5 for the online interpreter or about 8 for the offline one, then the answer to that question is probably no.


Haskell, 94 87 82 bytes
f s=and[j i-2<j(i-x)|let j i=last$0:[1+j(i-x)|x<-s,x<i],i<-[1..2*last s],x<-s,x<i]

this solution works by defining a function j which perform's the cashier's algorithm and tells us how many coins the cashier used. we then check up to twice the biggest number in the list, assuming that the system has been canonical for all previous numbers, that taking the biggest possible coin is the right choice.
this solution assumes the input is sorted.
proof checking up to twice the biggest number is enough:
assume that the system is not canonical for some number i, and let k be the biggest number in the list not bigger than i. assume that i >= 2k and the system is canonical for all numbers less than i.
take some optimal way to make i out of coins, and assume it doesn't contain the coin k. if we throw away one of the coins, the new sum of coins must be bigger than k and smaller than i - but the cashier's algorithm on this number would use the k coin - and therefore, this set of coins can be replaced with an equal set of coins containing the coin k, and therefore there is a set of coins containing the coin k for the number i, and by induction the cashier's algorithm returns the optimal choice.
this argument really shows that we only need to check until the sum of the two biggest elements - but it is lengthier to do so.
Edit: five bytes off thanks to Ørjan Johansen!


APL (Dyalog Extended), 3 bytesSBCS

+/=

Try it online!

+/ sum the mask where = equal to the prototypical element of that element, which is space for characters.


Charcoal, 20 17 bytes

-3 bytes thanks to Neil.

Ｎν↙ν↑↑ν↖ν ×_ν↗ν‖Ｍ

Try it online! Link is to verbose version.

I'm pretty happy with this golf so...

Explanation

Ｎν                 take a number as input and store in ν
  ↙ν               print / ν times downwards to the left
    ↑              move up once
     ↑ν            print | ν times upwards
       ↖ν          print \ ν times upwards to the left
                   print a space
          ×_ν      print _ ν times
             ↗ν    print / ν times upwards to the right
               ‖Ｍ  reflect horizontally

     /\
    /  \    "No, this is Patrick!"
___/    \___
\   ☉ ☉    /
 \       /
  \      /
  |  /\  |
  | /  \ |
  |/    \|


Use the fall at the end for instructions

This is a pretty simple tip but many MarioLANG programs end something like this, ending with Mario falling down:

.....
=====

and this can be written instead as this:

....
===.

saving two bytes.

If your program has an elevator near an end like this you can often improve even further. This:

]!......
=#======

 <
="

goes to this:

]!.
=#.
  .
  .
 <.
=".

You do have to be careful with the last one though, since the added spaces to get to the final instructions can in many situations be more costly than just writing it largely on one line.


CJam, 46 44 43 38 37 34 bytes

rA,sd`f#3fmd2/2ew::.-::mh:+2mO"cm"

Thanks to @user23013 for suggesting mh, which made it possible to save 5 bytes.

Try it online in the CJam interpreter.

How it works

r     e# Read a token from STDIN.
A,    e# Push [0 1 2 3 4 5 6 7 8 9].
s     e# Stringify: [0 1 2 3 4 5 6 7 8 9] -> "0123456789"
d     e# Cast to Double: "0123456789" -> 123456789.0
`     e# Inspect: 123456789.0 -> "123456789.0"
f#    e# Push the index of each character from the input in "123456789.0".
3fmd  e# Push the quotient and residue of each index divided by 3.
2/    e# Split the resulting array into pairs.
2ew   e# Convert the array of pairs in the array of all overlapping pairs of pair.
::.-  e# Reduce each pair using vectorized difference: [[a b][c d]] -> [a-b c-d]
::mh  e# Reduce each reduced pair to its 2-norm distance: [a b] -> sqrt(aa + bb)
:+    e# Sum all distances.
2mO   e# Round to two decimal places.
"cm"  e# Push "cm".


Jelly,  33  27 bytes
-1 thanks to caird coinheringaahing (use of ))
Ø[j
%⁵Ç¡);”XÇ¡⁶i”];C$$¦ƬḊ¤G

A full program that accepts \$x\$ and \$y\$ and prints the result.
Try it online!
How?
Ø[j - Link 1, wrap in []: a
Ø[  - list of characters = ['[', ']']
  j - join (with a) = ['[', a, ']']

%⁵Ç¡);”XÇ¡⁶i”];C$$¦ƬḊ¤G - Main Link: x, y
    )                   - for each (v in [1..x]):
 ⁵                      -   ten
%                       -   (v) modulo (10)
   ¡                    -   repeat (y times):
  Ç                     -     call last Link (1) as a monad
                     ¤  - nilad followed by link(s) as a nilad:
      ”X                -   character = 'X'
         ¡              -   repeat (y times):
        Ç               -     call last Link (1) as a monad
                   Ƭ    -   loop until no change, collecting up inputs:
                  ¦     -     sparse application...
                 $      -     ...to (1-based) indices: last two links as a monad:
           i”]          -       first index of character ']' (call this i)
                $       -       last two links as a monad:
               C        -         complement -> 1-i
              ;         -         concatenate -> [i, 1-i]
          ⁶             -     ...of: space character (replaces innermost [] with spaces)
                    Ḋ   -   dequeue (remove the leading one with all []s present)
     ;                  - concatenate
                      G - format as a grid
                        - implicit print


Consider

[
    "ABCD"
    "EFGH"
    "IJKL"
]

To obtain the main diagonal and the diagonals above it, we can shift out the first char of the second row and the first two of the third:

[
    "ABCD"
    "FGH"
    "KL"
]

Note that all columns correspond to a diagonal, so "zipping" the array (i.e., transposing rows and columns) will yield an array containing the aforementioned four diagonals:

[
    "AFK"
    "BGL"
    "CH"
    "D"
]

We're still missing the diagonals below the main diagonal.

If we zip A itself and repeat the above process, we'll obtain an array containing the main diagonal and all diagonals below it. All that's left it to compute the set union of both arrays.

Putting it all together:

[.zip]{:A,,{.A=>}%zip}/|

[.zip]{              }/  # For the original array and it's transpose, do the following:
       :A                # Store the array in A.
         ,,{    }%       # For each I in [ 0 1 ... len(A) ], do the following:
            .A=>         # Push A[I] and shift out its first I characters.
                  zip    # Transpose the resulting array.
                       | # Perform set union.

Try it online.

Finally, if we only need the diagonals because we're searching for a string inside them (like in the Word Search Puzzle, which I assume inspired this question), a "less clean" approach might also be suitable.

You can use

..,n**\.0=,\,+)/zip

to obtain all diagonals, plus some unnecessary linefeed characters.

I've explained the process in detail in this answer.

Try it online.


CJam, 31 bytes

{'_'~]-3>U):U{)__,1>:*)\%}g*}_~

Try it online in the CJam interpreter.

Idea

To check for primality, we'll use Wilson's theorem, which states that an integer n > 1 is prime if and only if (n - 1)! ≡ -1 (mod n), which is true if and only if (n - 1)! + 1 % n == 0.

Code

{                           }_~ e# Define a block and execute a copy.
                                e# The original block will be on top of the stack.
 '_'~]                          e# Push those characters and wrap the stack in an array.
      -3>                       e# Keep only the last three elements (QUINE).
         U):U                   e# Increment U (initially 0).
             {           }g     e# Do-while loop:
              )__               e# Increment the integer I on the stack (initially U).
                 ,1>            e#   Push [1 ... I-1].
                    :*          e#   Multiply all to push factorial(I-1).
                      )\%       e#   Push factorial(I-1) + 1 % I.
                                e# While the result is non-zero, repeat.
                                e# This pushes the next prime after U.
                           *    e# Repeat QUINE that many times.


Retina, 61 37 bytes

r1>`[A-Z]?[a-z]+|[A-Z]+|\d+
_$&
T`L`l

Try it online! (Slightly modified to run a full test suite.)

Explanation

Instead of finding word boundaries to insert underscores, we simply match each word and prepend a _. Matching words from the left is a bit annoying because of the UUl rule, but using .NET's right-to-left matching we can easily match words greedily. To avoid a leading _, we make use of Retina's limits.

r1>`[A-Z]?[a-z]+|[A-Z]+|\d+
_$&

The r activates right-to-left mode, the 1> tells Retina to process everything except the first match (counting from left to right). Then there's four types of "words": Ulll, lll, UUU, ddd. These are easily matched with the given pattern. The substitution just writes a _ followed by the word itself.

T`L`l

This simply turns upper case into lower case to complete the transformation.


Haskell, 25 24 23 17 bytes

mapM$min"^v".pure

Try it online!

-1 byte thanks to @H.PWiz

-1 byte thanks to @nimi

Returns a list of strings. The TIO has 2 extra bytes for the function declaration - I've seen other people leave it off when they write the function pointfree so I'm doing the same unless told otherwise.

Previous Answer (25 bytes)

g 'v'="v^"
g x=[x]
mapM g

The explanations are all for the previous answer, which works pretty much the same way, except I inlined the definition of g. The way g works now is by using lexical comparison to substitute ^v for v and keep everything else the same.

Interestingly, this works for arbitrary switchboards:

>>> mapM g "-----^-----"
  ["-----v-----", "-----^-----"]

Explanation (Short)

g 'v'="v^" -- for 'v', choose between 'v' or '^'
g x=[x]    -- for any other character, choose just that character
mapM g     -- find all ways to choose characters using g on the given input

Explanation (Long)

mapM is a pretty scary function for those not familiar with Haskell. But it's not hard to understand in this context. By making it act on Strings (which in Haskell are lists of characters), I've specialized it to its definition for lists. So in this context, its type signature is

mapM :: (a -> [b]) -> [a] -> [[b]]
--      ^^^^^^^^^^                  arg 1: a function from any a to a list of b
--                    ^^^           arg 2: a list of a
--                           ^^^^^ return: a list of list of b

It is actually even more specialized in my usage of it - a and b are both Char - so we can see the type signature as

mapM :: (Char -> String) -> String -> [String]

Let's quickly look at what g does before explaining how mapM works.

g :: Char -> String
g 'v' = "v^"
g  x  = [x]

g uses pattern matching to convert the Char 'v' into the string "v^"; everything else gets converted to a singleton string (remember, strings are just lists of Chars, so we can put x in a singleton list). Testing on the REPL, we find this is the case

>>> g 'a'
  "a"
>>> g 'b'
  "b"
>>> g 'v'
  "v^"

Note that g has the right type to be an argument of mapM (unsurprisingly!).

We'll explore how mapM works by giving it g and the argument

"-v-\n-v-"

as input.

mapM first maps g over the String, and because g converts Chars to Strings, this gives us a list of Strings

["-", "v^", "-", "\n", "-", "v^", "-"]

While this is the correct output type, mapM does slightly more. You can think of it as forming all Strings that you could create from this list if you had to pick a single character from each String in it (in order).

So for the first element, you have no choice other than to pick the Char '-'. For the second element, you can choose between 'v' and '^', so on and so forth.

It's roughly equivalent to this python code:

result = []
for x1 in "-":
  for x2 in "v^":
    for x3 in "-":
      ...
        result.append(''.join([x1, x2, x3, x4, x5, x6, x7]))

Except that since Haskell separates between Chars and Strings, when it puts the Chars into a list, it doesn't need to join them.

So the final output is

["-v-\n-v-", "-v-\n-^", "-^-\n-v-", "-^-\n-^-"]

as desired.


05AB1E,  10  8 bytes

-2 bytes thanks to Emigna (use "bifurcation" instruction Â to replace duplicate and reverse DR & increment the loop to avoid needing to close it.)

G¹N>вÂQO

Try it online!

How?

G¹N>вÂQO
G        - for N in range(1, input()+1):
 ¹       -   1st input
  N      -   N (the loop variable)
   >     -   increment
    в    -   base conversion
     Â   -   push reverse
      Q  -   equal?
       O -   sum
         - print top of stack


Shortest string expressions stable under deleting quotes

C  (4 chars)

The expression

""""

satisfies the minimal requirement of three characters. It encodes the empty string, no matter even if you omit one level of quotes:

 ""

If you want the resulting string to be at least three characters, here is an expression of length 10 which results in three characters of string, namely three spaces:

""   "   "
 "   "

If you don't like spaces either, here are four printable characters in a length 12 expression:

""/**/"/**/"
 "/**/"/**/

Putting these expressions into a small program:

#include <stdio.h>
#define CASE(s) printf("'%s'\n", s)
int main() {
  CASE("""");
  CASE("");
  CASE(""   "   ");
  CASE("   "   );
  CASE(""/**/"/**/");
  CASE("/**/"/**/);
}

Output:

''
''
'   '
'   '
'/**/'
'/**/'


Python 2, 123 120 bytes

N=sorted(map(int,raw_input().split(' ')));print(''.join((''if n+1in N else'-'+`n`)if n-1in N else' '+`n`for n in N)[1:])

If the input can be a list as a function argument then (thanks mbomb007 and xnor for the conditionals)

93 90 81 bytes

def f(N):print''.join((' '+`n`,`-n`*-~-(n+1in N))[n-1in N]for n in sorted(N))[1:]

(77 bytes if leading whitespace is acceptable - drop the final [1:])


Bash, 135 bytes

convert +antialias -pointsize 99 label:$1 -fill red -draw 'color 0,0 floodfill' -fill black -opaque white -fill white -opaque red i.png

Uses ImageMagick (convert).

Sample output:

convert
  +antialias                              # disable antialiasing
  -pointsize 99                           # annoyingly necessary (see below)
  label:$1                                # draw input text
  -fill red -draw 'color 0,0 floodfill'   # flood fill from (0,0) with red
  -fill black -opaque white               # replace all white with black
  -fill white -opaque red                 # replace all red with white
  i.png

Disabling antialiasing is required because otherwise antialiased interior parts of the letters wouldn't flood fill. Setting the font to a large size is also required because some fonts have "gaps" in letters that should have "holes" in them at small font sizes (in my tests, the a wasn't filled at the default small font size).


J, 16 15 bytes

[h"2[h"1 h=.,,[

This is an anonymous verb. Try it online!

Thanks to Adám for 1 byte!

Explanation

[h"2[h"1 h=.,,[  Wrapper is x, present is y.
            ,    Prepend x to y
             ,   then append
              [  x.
                 This gives x y x, and the wrapper automatically spreads to form 2D slices.
         h=.     Save the above operation (not its result) to h.
    [h"1         Apply h to x and every 2D slice of the previous result.
[h"2             Apply h to x and every 1D slice of the result of that.


Code golfing my guess the number game with feedback in NS-HUBASIC - Can it be code golfed any further?

 134  133 characters

Note: I don't know for sure whether a line-break counts as 1 character.

0N=RND(10)+1:DIMT$(2):T$(0)="TOO LOW.":T$(1)="CORRECT.":T$(2)="TOO HIGH."
1I."WHAT'S MY NUMBER? (1-10) ",G:?T$(SGN(G-N)+1):IF G-N T.1

Example output


Compressing the Atomic Ionization Energies


Mathematica, 105 97 91 bytes

-6 bytes thanks to Roman!

a=StringReplace;ToString@ToExpression@a[#,{"*"->"**","+"->"~~"}]~a~{" ** "->"*","~~"->"+"}&

Replaces + and * with ~~ (StringExpression) and ** (NonCommutativeMultiply) respectively, evaluates it, stringifies it, and replaces the operators back.


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

<?::

Outputs:

Parse error: syntax error, unexpected T_PAAMAYIM_NEKUDOTAYIM on line 1

Whaa?


Python 3, 86 \$\cdots\$ 81 77 bytes

Saved 3 bytes thanks to mypetlion!!!
Saved 4 bytes thanks to Shieru Asakoto!!!

print(f"http://{'.'.join(chr(i+97)*int(1+.7**-i/120)for i in range(26))}.me")

Try it online!

Uses Shieru Asakoto's 0-based formula.


05AB1E, 38 bytes, Loovjo, A000290

nXtdief e():return X*X
pr e(input())##

Try it online!

Very likely not the intended solution, but it works.

Explanation

n      # square input
 X     # push 1
  t    # push sqrt(1)
   d   # push is_number(1.0)
    i  # if true do the rest of the code (1.0 is not a number so it will never execute)


MATL, 12 bytes
t1Y)-X$&Yvoz

Input is a matrix, where each row defines a point.
Try it online! Or verify all test cases.
Explanation
The code uses the singular value decomposition of a matrix, which is done symbolically to prevent floating-point issues. The rank of a matrix equals the number of non-zero singular values.
t      % Implicit input: matrix of integer values. Duplicate
1Y)    % Get the first row
-      % Subtract, with broadcast. This subtracts this row from each row
X$     % Convert to symbolic matrix. Note that integers, are represented
       % exactly as floating-point values up to ±2^53.
&Yv    % Single-output singular value decomposition. Gives a vector with
       % the singular values
o      % Convert to floating point. Note that 0 is represented exactly
       % as a floating-point value
z      % Number of nonzeros. Implicit output


Can I exit the maze with this many bombs?

JavaScript (ES7),  126 125  119 bytes
Expects (matrix)(bombs), where the matrix is filled with -1 for an empty cell and -2 for a wall.
Returns false if we can exit the maze, or true if we can't.

m=>g=(b,X=0,Y=0)=>m.every((r,y)=>m[Y+1]||r[X+1]?r.every((v,x)=>r[x]*=v>0|(X-x)**2+(Y-y)**2!=1||g(b-~v,x,y,r[x]=1)):b<0)

Try it online!
Commented
m =>                        // m[] = matrix
g = (                       // g is a recursive function taking:
  b,                        //   b = number of bombs
  X = 0, Y = 0              //   (X, Y) = current position, starting at (0, 0)
) =>                        //
  m.every((r, y) =>         // for each row r[] at position y in m[]:
    m[Y + 1] ||             //   if there's a row below the current cell
    r[X + 1] ?              //   or there's a column on the right:
      r.every((v, x) =>     //     for each value v at position x in r[]:
        r[x] *=             //       restore r[x] if any of these tests is true:
          v > 0 |           //         - v is greater than 0 (this cell was visited)
          (X - x) ** 2 +    //         - the squared distance between
          (Y - y) ** 2 != 1 //           (x, y) and (X, Y) is not equal to 1
          ||                //
          g(                //         - this recursive call is truthy:
            b - ~v,         //             decrement b if v = -2
            x, y,           //             use the new position (x, y)
            r[x] = 1        //             mark r[x] as visited by setting it to 1
          )                 //           end of recursive call
      )                     //     end of inner every()
    :                       //   else (bottom-right cell):
      b < 0                 //     return true if we've used too many bombs
  )                         // end of outer every()


Display powers of Phi with Fibonacci precision

dc, 26 bytes

99k5v1+2/?^d5v/.5+0k1/k1/p

Due to the initial precision of 99 digits after the comma, this will work up yo input 11. A dynamic (or higher static) precision is possible, but would elevate the byte count.

Test cases

$ for ((i = 0; i < 11; i++)) { dc -e '99k5v1+2/?^d5v/.5+0k1/k1/p' <<< $i; }
1
1.6
2.6
4.23
6.854
11.09016
17.94427190
29.0344418537486
46.978713763747791812296
76.0131556174964248389559523684316960
122.9918693812442166512522758901100964746170048893169574174

How it works

Since the desired output is φn, we can calculate the the Fibonacci number F(n) as ⌊φn ÷ √5 + 0.5⌋ with little additional effort.

99k                         Set the precision to 99.
   5v                       Compute the square root of 5.
     1+                     Add 1.
       2/                   Divide by 2.
                            This pushes the golden ratio.
         ?                  Read the input from STDIN.
          ^                 Elevate the golden ratio to that power.
           d                Push a copy.
            5v/             Divide it by the square root of 5.
               .5+          Add 0.5.
                  0k        Set the precision to 0.
                    1/      Divide by 1, truncating to the desired precision.
                            This pushes F(n).
                      k     Set the precision to F(n).
                       1/   Divide by 1, truncating to the desired precision.
                         p  Print.


Calculate the difficulty of a Code Golf question

JavaScript (ES6), 40 39 bytes

v=>a=>"**********".substring(10-v/a/70)

Because substring provides the required clamping and "ceil"ing behaviour. Edit: Normally I'm too lazy to bother, but because it got 4 upvotes, I've followed @MarsUltor's advice to save 1 byte by currying.


Wolfram Language, 259 bytes
o=DirectedEdges->True
i|->RelationGraph[(d=Abs[#1[[2]]-#2[[2]]];#1!=#2&&NoneTrue[i,RegionMember[Line[p={#1[[2]],#2[[2]]}]~RegionDifference~Point@p]@*Last]&&Switch[#1[[1]],r,Times@@d==0,b,Equal@@d,n,Sort@d=={1,2}])&,i,o]~IsomorphicGraphQ~CycleGraph[Length@i,o]

Try it online!
(uses \[Function] rather than |->, as TIO doesn't have the most recent version of the language)
Defines a function that takes in a list of piece positions as input, each in the form {piece, {row, column}} where piece is one of r, b, or n.
Un-golfed explanation:
i|->
IsomorphicGraphQ[                (*check if the following graphs are equivalent*)
  CycleGraph[Length[i], DirectedEdges -> True],
                                 (*cyclic graph with length of input*)
  RelationGraph[                 (*graph defined by a functional relation*)
    (d = Abs[#1[[2]] - #2[[2]]]; (*set `d` to absolute difference in coordinates*)
    #1 != #2 &&                  (*no pieces attack themselves*)
    NoneTrue[i,                  (*no other pieces are...*)
      RegionMember[RegionDifference[Line[p = {#1[[2]], #2[[2]]}], Point[p]]] @* Last
    ] &&                         (*between these two pieces*)
    Switch[First @ #1,           (*switch by attacking piece*)
      r, Times @@ d == 0,        (*rooks attack when one coordinate offset is zero*)
      b, Equal @@ d,             (*bishops attack when both offsets are equal*)
      n, Sort[d] == {1, 2}]      (*knights attack when one offset is 1 and the other is 2*)
    )&, i, DirectedEdges->True], (*apply to list of pieces*)
]&


Haskell, 69 68 64 bytes

x#n=take n$x++zipWith3 id(cycle[(+),(*),(-),(/)])(x#n)(tail$x#n)

x1 and x2 are taken as a list. Usage example: [1,3] # 8 -> [1.0,3.0,4.0,12.0,-8.0,-1.5,-9.5,14.25].

Laziness makes it possible to define an infinite recursive list where we take the first n elements.

Haskell, 66 bytes

(h%g)y x=x:g(h x y)y
a=(+)%b
b=(*)%c
c=(-)%d
d=(/)%a
(.a).(.).take

Different approach, slightly longer. Argument order is N, x2, x1. Usage example: ( (.a).(.).take ) 8 3 1 -> [1.0,3.0,4.0,12.0,-8.0,-1.5,-9.5,14.25].

Defines 4 functions a, b, c and d which take two arguments y, x  and make a list by putting x in front of a call to the next function with y as the second argument and x op y as the first. For example a is: a y x = x : (b (x+y) y), b does multiplication: b y x = x : (c (x*y) y), etc.

Edit: @Michael Klein saved a byte in the 1st variant (#). Luckily I also found one byte for the second variant, so both have the same length again.

Edit II: @Zgarb found 2 bytes in the second version to save, and I 4 in the first, so they are no longer of the same length.


Monkey Island: The Head of the Navigator

Python, 224 + 97 + 1 = 322 characters

A most straightforward solution to start us all off. Thanks to gnibbler for helping me shave off 18 bytes!

n=0
print open('z','rb').read().decode('zip').split('|')[n]
open(__file__,'r+').write("n="+`n+1`)

Requires the file z to be present in the same directory (+1 for filename, +224 for file size):

$ hexdump z
0000000 9c78 d1ad 6e3d 30c3 050c bde0 78a7 165b
0000010 0723 92c8 48a9 b43a 8209 192c 9b29 0491
0000020 a2ab 9fa1 021a f87a 715a f46c d100 1026
0000030 1efc 1e41 5172 4721 c3b3 1527 607c 4c70
0000040 6191 87e8 0c91 7825 7b6e 2d47 dfef 4c8e
0000050 0edd d25f e540 8b54 8fbe 4bb8 c500 7ade
0000060 288d c418 c4d9 6cae 0f7f 7bab 6832 9be5
0000070 be21 7aa9 537d c2c2 24dd 25a3 c50f e41a
0000080 ca1c 1ff4 a7c9 a439 d5cc 9a4d b207 3fe9
0000090 0e7c 529c 4e79 3afc 7cef bf79 6f5e 672f
00000a0 8b9f 6d1d 8832 5359 1698 2482 92c3 3270
00000b0 43cd 560e 899b a4ad 1ab2 548a aed9 0bf1
00000c0 238f 0697 bd63 168f 36e9 b411 0a1e fef6
00000d0 eee8 1d64 1a28 aec9 10e3 7ff7 3a0b d9ab
00000e0

$ ls -l z
-rw-r--r--+ 1 Laxori mkpasswd 224 2014-09-22 22:35 z

You can generate z with the following:

>>> open('z','wb').write("""eJyt0T1uwzAMBeC9p3hbFiMHyJKpSDq0CYIsGSmbkQSroqGfGgJ6+FpxbPQA0SYQ/B5BHnJRIUez
wycVfGBwTJFh6IeRDCV4bntHLe/fjkzdDl/SQOVUi76PuEsAxd56jSgYxNnErmx/D6t7MmjlmyG+
qXp9U8LC3SSjJQ/FGuQcyvQfyac5pMzVTZoHsuk/fA6cUnlO/DrvfHm/Xm8vZ5+LHW0yiFlTmBaC
JMOScDLNQw5Wm4mtpLIailTZrvELjyOXBmO9jxbpNhG0Hgr2/ujuZB0oGsmu4xD3fws6q9k=""".decode('base64'))

Output:

$ python monkeyisland.py
Guybrush: May I please have that necklace?
Head: No, but thanks for asking so politely.
$ python monkeyisland.py
Guybrush: Oh come on, pleeeeease?
Head: You can beg all you want, but you can't have it.
$ python monkeyisland.py
Guybrush: Pretty please?
Head: You can beg all you want, but you can't have it.
$ python monkeyisland.py
Guybrush: Pretty PRETTY please?
Head: You can beg all you want, but you can't have it.
$ python monkeyisland.py
Guybrush: Pretty please with sugar on top?
Head: Oh, all right, you big baby. You can have it. Hey, what good's a necklace if you don't have shoulders?
$ python monkeyisland.py
Traceback (most recent call last):
  File "monkeyisland.py", line 2, in <module>
    print open('z','rb').read().decode('zip').split('|')[n]
IndexError: list index out of range


Husk, 7 bytes

mLġ≤ṁḋN

Try it online!

Takes no input and prints ALL the numbers!

Explanation

mLġ≤ṁḋN
      N        The list of all positive integers [1,2,3...]
    ṁḋ         Convert each to binary and concatenate the resulting digits
  ġ≤           Split them in groups where each digit is less than or equal to the previous one (basically cuts wherever there is a 0 followed by a 1)
mL             Compute the length of each group


Perl, 32 + 32 = 64

The string is expected in STDIN. The output is written to STDOUT. White space is ignored. My interpretation of the task is that the program should be able to run on itself to get the score.

$/ = $,;
$_ = <>;
s x\sxxg;
$\ = length;
print s x[0-9a-z]xxgi,
      ' + ',
      s x.xxg,
      ' = '

Ungolfed with comments

$/ = $,; # The input separator becomes undefined, because the default for $, is "undef"
$_ = <>; # now $_ takes the whole file (STDIN) instead of the first line
s x\sxxg; # $_ =~ s/\s//g;
          # white space is removed from $_
$\ = length; # The number of the other characters are put into $\,
             # which is automatically printed the end of "print".
print s x[0-9a-z]xxgi, # s/[0-9a-z]//gi
                       # Remove alphanumeric characters and return their count
      ' + ',
      s x.xxg, # s/.//g
               # Remove the remaining special characters and return their count.
               # "." does not catch new lines, but we have already
               # removed white spaces including new lines.
      ' = '

I found several variations with the same byte counts, e.g.:

$/ = $x;
$_ = <>, s x\sxxg;
$\ = split $x;
print s x[\da-z]xxgi,
      " + ",
      s x.xxg,
      ' = '

Examples

Example from the question:

echo 'http://stackexchange.com' | perl a.pl
20 + 4 = 24

Running on itself (a.pl):

cat a.pl | perl a.pl
32 + 32 = 64

The file size is 104 bytes, thus 40 bytes are ignored as white space.

Perl, 29 + 29 = 58

$_=<>;s x\sxxg;$\=length;print s x[0-9a-z]xxgi,' + ',s/.//g,' = '

The string is expected at STDIN and it is limited to the first line. The result is printed to STDOUT.
White space is ignored.

Ungolfed

$_ = <>;
s x\sxxg; # same as s/\s//gx; removes white space;
$\ = length($_); # sum is automatically appended at the end of print
print sx[0-9a-z]xxgi, # same as s/[0-9a-z]//gi;
                      # the number of alphanumeric characters
      ' + ',
      s/.//g, # the number of the remaining special characters
      ' = '

Examples

File a.pl contains the Perl script.

Example from the question:

echo 'http://stackexchange.com' | perl a.pl
20 + 4 = 24

Running on itself:

cat a.pl | perl a.pl
29 + 29 = 58

The file size of a.pl is 65 bytes, thus 7 bytes are ignored as white space.


Python 2, \$ O(2^{\frac{|W|}2} \cdot |B| \cdot |W| + |W|^2) \$, 203 bytes

Naive implementation, looks at all combinations of possible weights \$W\$ and barbells \$B\$.

lambda B,W,T:min([(w+w[::-1],b)for w in p(sorted(sum([W.count(x)/2*[x]for x in set(W)],[])))for b in B],key=lambda(a,b):((T-sum(a)-b)**2,len(a)))
p=lambda l:l and[l[:1]+x for x in p(l[1:])]+p(l[1:])or[l]

Try it online!

Ungolfed

def f(Barbells, Weights, Target):
  # For every pair of same weights keep one, order them ascending
  usable_weights = concat([Weights.count(x)/2 * [x] for x in set(Weights)])
  usable_weights = sorted(usable_weights)

  # list all possible combinations of symmetric weights and barbells
  possible_setups = [(w+w[::-1], b)for w in powerset(usable_weights)for b in Barbells]

  # Find the one with the weight being the closest to the target,
  # on a tie take the one with the lowest number of weights
  return min(possible_setups, key=lambda(a,b): ((Target - sum(a) - b)**2, len(a)))

concat = lambda ls:sum(ls, [])
powerset = lambda l:l and [l[:1]+x for x in powerset(l[1:])]+powerset(l[1:]) or [[]]

Try it online!


ANSI C, 385 390 Characters

int N,a=1,x,y,d=1,u,k,l;int main(int c,char**v){for(;a<c;)N+=strlen(v[a++]);int H=N*2,W=N*4,m=H,n=N,q=m,w=n;char*p,F[W][H],*o;memset(F,32,W*H);for(a=1;a<c;a++){q=(x=m)<q?m:q;w=(y=n)<w?n:w;m=-1;for(p=v[a];*p;p++){F[x][y]=*p;if(m<0&&a<c-1&&(o=strchr(v[a+1],*p))){u=o-v[a+1];m=d?x:x-u*2;n=d?y-u:y;}if(d)x+=2;else y++;}d=!d;}for(l=w;l<H;l++){for(k=q;k<W;)putchar(F[k++][l]);putchar(10);}}

Call it like this: ./crossword This site graduated finally

Ungolfed version:

int N,a=1,x,y,d=1,u,k,l;
int main(int c, char **v) {
    for(;a<c;)
        N+=strlen(v[a++]);
    int H = N*2, W = N*4, m = H, n = N, q=m, w=n;
    char *p,F[W][H], *o;
    memset(F, 32, W*H);
    for (a=1; a < c; a++) {
        q=(x=m)<q?m:q;
        w=(y=n)<w?n:w;
        m=-1;
        for (p=v[a]; *p; p++) {
            F[x][y] = *p;
            if (m<0&&a<c-1&&(o = strchr(v[a+1], *p))) {
                u = o-v[a+1];
                m = d ? x : x-u*2;
                n = d ? y-u : y;
            }
            if (d) x+=2; else y++;
        }
        d=!d;
    }
    for (l = w; l < H; l++) {
        for (k = q; k < W;)
            putchar(F[k++][l]);
        putchar(10);
    }
}

Thank you tucuxi for the tips!


Find columns where all characters are the same

APL, 25 characters

∩/{0=⍴⍵:⍬⋄(⊂⍵,⍨¨⍳⍴⍵),∇⍞}⍞

I used Dyalog APL (version 13) as my interpreter. It handles both inputs of unequal length and Unicode (UTF-8) characters.

Examples:

      ∩/{0=⍴⍵:⍬⋄(⊂⍵,⍨¨⍳⍴⍵),∇⍞}⍞
abcdefg
avcddeg
acbdeeg

  1 a  4 d  7 g

      ∩/{0=⍴⍵:⍬⋄(⊂⍵,⍨¨⍳⍴⍵),∇⍞}⍞
test日本
blat日本国foo

  4 t  5 日  6 本

Explanation, somewhat from right to left:

The main chunk of this answer is the direct function (basically, anonymous function), defined within the curly braces. Its right argument is specified by ⍵.

0=⍴⍵:⍬ is our first expression, and it checks if we've gotten an empty line (i.e., we are done). It uses a guard (a familiar construct to many functional programmers) to conditionally execute the expression to the right of the colon. In this case, if 0 is equal to the shape/length (⍴) of the right argument, we return the empty set (⍬).
⋄ separates the two expressions within the function. If the previous expression didn't get evaluated (and thus didn't return anything), we move to the next expression.
We recursively call the function using the self-reference function (∇). The argument to the function is a line of non-evaluated user input, given by quote-quad (⍞).
⊂⍵,⍨¨⍳⍴⍵ creates pairs for each character in the string, where each pair's first element is its position in the string, and its second element is the character.
⍳⍴⍵ gives a vector from 1 to ⍴⍵, or the length of the input string.
⍵,⍨¨ applies the commuted concatenation function (,⍨) to each (¨) element to its left (⍵, in this case the user's input) and right. Commuting the concatenation function causes its left and right arguments to be swapped.
Finally, we enclose the result using ⊂, so that we can differentiate between lines of input.

We initially feed our function with user input (⍞).
Finally, we reduce (/) our resulting vector of vectors of pairs using the intersection function (∩), yielding the pairs that are found in all of the sub-vectors.


Python 3, 76 bytes

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

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


Python, 184 chars

import os,re
M=os.read(0,99)
s=0
t='x'
for p in range(72):
 c=sum(len(re.match(r'\.w+b|',M[p::d]).group()[2:])for d in(-10,-9,-8,-1,1,8,9,10))
 if c>s:s=c;t='(%d,%d)'%(p/9,p%9)
print t

Coordinates are given as (y,x) with (0,0) in the upper left.

$ ./othello.py < othello1
(5,3)
$ ./othello.py < othello2
(1,1)
$ ./othello.py < othello3
x


Retina 0.8.2, 229 bytes

T`#^`d
s`@.*
$&_
@\d|@ ( *\d)
@=$1
(\d *) @|\d@
$1=@
m`^(((.))*@.*\n(?<-2>.)*(?(2)$))(\d| ((.*\n)+(?<-3>.)*(?(3)$)\d))
$1=$5
m`^(((.))*)(\d|(\d(.*\n)+(?<-2>.)*(?(2)$)) )(.*\n(?<-3>.)*(?(3)$)@)
$1$5=$7
@
x
}sT`=`@`.*0.*
s`.*0.*

_

Try it online! Outputs 0 for unsolvable, since solutions must take at least one step. Explanation:

T`#^`d

Change the candle and exit to golfier characters, saving 7 bytes

s`@.*
$&_

If there are still squares to check, then increment the counter. (This allows the loop to terminate once it runs out of squares to check.)

@\d|@ ( *\d)
@=$1

Mark the square to the right if it is lit.

(\d *) @|\d@
$1=@

Mark the square to the left if it is lit.

m`^(((.))*@.*\n(?<-2>.)*(?(2)$))(\d| ((.*\n)+(?<-3>.)*(?(3)$)\d))
$1=$5

Mark the square below if it is lit.

m`^(((.))*)(\d|(\d(.*\n)+(?<-2>.)*(?(2)$)) )(.*\n(?<-3>.)*(?(3)$)@)
$1$5=$7

Mark the square above if it is lit.

@
x

Turn the squares that were checked into walls.

sT`=`@`.*0.*

If the exit still exists, then turn all of the marked squares into squares that need to be checked.

}`

Repeat the above until the exit is reached or no new steps could be taken.

s`.*0.*

If the exit was not reached then delete the count.

_

Convert the count to decimal and delete the input.


Counting up and down while doubling the increments

Husk, 3 bytes

ṁḋg

Try it online!

Explanation

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


Rock Paper Scissors Meta-Gaming Tournament

Anti-99%-of-posts
(code,r)=>{var S="S";var R="R";var P="P";var x=S+R+P;var y=R+P+S;var z=P+S+R
if(code.includes("17")){return "P";}
else if(code.includes("[r%2]")){return"RR"[r%2]}
else if(code.includes("[r%3]")){
if (code.includes(x)){return (R+P+S)[r%3];}
else if(code.includes(y)){return (P+S+R)[r%3];}
else if(code.includes(z)){return (S+R+P)[r%3];}
}else{if(code.includes("scissors")){return "R"}else if (code.includes("rock")){return "P"}else if (code.includes("paper") ){return "S"}else{return "P"}}}

Haha. Testing it on submissions gives either a win or a tie.


05AB1E, 7 6 bytes

€ćÁ2ôJ

Explanation:

€ć      Extract head of each
  Á     Rotate to the right
    2ô  Split into pieces of length two
      J Join

Try it online!


Write a program to print the sum of the ascii codes of the program

PHP, m4, and other cat-like languages: 150

150

Found this solution using a simple Haskell program to brute-force it:

f :: String -> Bool
f s = (read s :: Int) == (sum . map fromEnum) s

main = mapM_ print [filter f $ sequence $ replicate n ['0'..'9'] | n <- [1..10]]


Ruby, ><>, HQ9+, Befunge-93, 62 characters
#9&1+.@.10[0[fr'
puts"\u0048ello World!"#.1*57;!?lo r]r}:*3da'

"Hello World!" (Ruby)
Relevant part of code:
puts"\u0048ello World!"
quine (><>)
After colliding with the # mirror, both lines are read as string literals and printed with a newline between.
99 bottles of beer on the wall (HQ9+)
Code contains no H or Q, and exactly one 9, so the lyrics of the song are printed once.
+1 program (Befunge-93)
After jumping over 9 due to the # trampoline, a simple +1 program is run &1+.@


Evaluate expressions with significant figures

Java 11, 1325 1379 1356 1336 1290 bytes

import java.math.*;String c(String s)throws Exception{String r="",T=r,a[],b[],z="\\.";int i=0,l,A[],M=0,m=s.length(),j,f=0,q=m;if(s.contains("(")){for(;i<m;){var c=s.charAt(i++);if(f<1){if(c==40){f=1;continue;}r+=c;}else{if(c==41&T.replaceAll("[^(]","").length()==T.replaceAll("[^)]","").length()){r+="x"+s.substring(i);break;}T+=c;}}return c(r.replace("x",c(T)));}else{for(a=s.split("[\\+\\-\\*/]"),A=new int[l=a.length];i<l;f=b.length>1&&(j=b[1].length())>f?j:f)M=(j=(b=a[i++].split(z))[0].length())>M?j:M;for(b=a.clone(),i=0;i<l;A[i]=b[i].contains(".")?j=b[i].length()-1:b[i].replaceAll("0*$","").length(),i++)for(q=(j=b[i].replace(".","").length())<q?j:q,j=a[i].split(z)[0].length();j++<M;)b[i]=0+b[i];double R=new Double(new javax.script.ScriptEngineManager().getEngineByName("JS").eval(s)+""),p;for(int x:A)m=x<m?x:m;m=m==M&R%1==0&(int)R/10%10<1&(j=(r=R+"").split(z)[0].length())>m?j-q>1?q:j:R>99?m:R%10==0?r.length()-1:m<1?1:m;R=new BigDecimal(R).round(new MathContext((R<0?-R:R)<1?m-1:m)).doubleValue();r=(m<M&(p=Math.pow(10,M-m))/10>R?(int)(R/p)*p:R)+"";l=r.length()-2;r=(r=f<1?r.replaceAll(z+"0$",""):r+"0".repeat(f)).substring(0,(j=r.length())<m?j:r.contains(".")?(j=r.replaceAll("^0\\.0+","").length())<m?m-~j:m+1:m);for(i=r.length();i++<l;)r+=0;return r.replaceAll(z+"$","");}}

+54 bytes to fix the edge case 501*2.0 (gave result 1002 before, but now correct 1000).
I now understand why this challenge was unanswered for almost two years.. >.> This challenge has more special cases than the Dutch language, which is saying something..
Java is certainly not the right language for these kind of challenges (or any codegolf challenge for that matter.. ;p), but it's the only language I know good enough to even attempt a difficult challenge like this.
Input format as String without spaces (if that is not allowed, you can add s=s.replace(" ","") (+19 bytes) at the top of the method).
Try it online.
Explanation:
Sorry for the long post.
if(s.contains("(")){
  for(;i<m;){
    var c=s.charAt(i++);
    if(f<1){
      if(c==40){
        f=1;
        continue;}
      r+=c;}
    else{
      if(c==41&T.replaceAll("[^(]","").length()==T.replaceAll("[^)]","").length()){
        r+="x"+s.substring(i);
        break;}
      T+=c;}}
  return c(r.replace("x",c(T)));}

This part is used for input containing parenthesis. It will get the separated parts and use recursive-calls.

0.4*(2*6) becomes 0.4*A, where A is a recursive call to c(2*6)
(8.3*0.02)+(1.*(9*4)+2.2) becomes A+B, where A is a recursive call to c(8.3*0.02) and B a recursive call to c(1.*(9*4)+2.2) → which in turn becomes 1.*C+2.2, where C is a recursive call to c(9*4)

for(a=s.split("[\\+\\-\\*/]"),A=new int[l=a.length];
    i<l;
    f=b.length>1&&(j=b[1].length())>f?j:f)
  M=(j=(b=a[i++].split(z))[0].length())>M?j:M;

This first loop is used to fill the values M and k, where M is the largest integer-length regarding significant figures and k the largest decimals-length.

1200+3.0 becomes M=2, k=1 (12, .0)
999+2.00 becomes M=3, k=2 (999, .00)
300.+1-300. becomes M=3, k=0 (300, .)

for(b=a.clone(),i=0;
    i<l;
    A[i]=b[i].contains(".")?j=b[i].length()-1:b[i].replaceAll("0*$","").length(),i++)
  for(q=(j=b[i].replace(".","").length())<q?j:q,
      j=a[i].split(z)[0].length();
      j++<M;)
    b[i]=0+b[i];

This second loop is used to fill the arrays A and b as well as value q, where A is the amount of significant figures, b hold the integers with leading zeroes to match M, and q is the lowest length disregarding dots.

1200+3.0 becomes A=[2, 5] (12, 00030), b=[1200, 0003.0], and q=2 (30)
999+2.00 becomes A=[3, 5] (999, 00200), b=[999, 002.00], and q=3 (both 999 and 200)
300.+1-300. becomes A=[3, 3, 3] (300, 001, 300), b=[300., 001, 300.], and q=1 (1)
501*2.0 becomes A=[3, 4] (501, 0020), b=[501, 002.0], and q=2 (20)

double R=new Double(new javax.script.ScriptEngineManager().getEngineByName("JS").eval(s)+"")

Uses a JavaScript engine to eval the input, which will be saved in R as double.

1200+3.0 becomes R=1203.0
999+2.00 becomes R=1001.0
300.+1-300. becomes R=1.0

for(int x:A)
  m=x<m?x:m;

This sets m to the smallest value in the array A.

A=[2, 5] becomes m=2
A=[3, 5] becomes m=3
A=[3, 3, 3] becomes m=3

 m=m==M                // If `m` equals `M`
   &R%1==0             // and `R` has no decimal values (apart from 0)
   &(int)R/10%10<1     // and floor(int(R)/10) modulo-10 is 0
   &(j=(r=R+"").split(z)[0].length())>m?
                       // and the integer-length of R is larger than `m`:
    j-q>1?             //  If this integer-length of `R` minus `q` is 2 or larger:
     q                 //   Set `m` to `q` instead
    :                  //  Else:
     j                 //  Set `m` to this integer-length of `R`
   :R>99?              // Else-if `R` is 100 or larger:
    m                  //  Leave `m` the same
   :R%10==0?           // Else-if `R` modulo-10 is exactly 0:
    r.length()-1       //  Set `m` to the total length of `R` (minus the dot)
   :m<1?               // Else-if `m` is 0:
    1                  //  Set `m` to 1
   :                   // Else:
    m;                 //  Leave `m` the same

This modifies m based on multiple factors.

999+2.00 = 1001.0 & m=3,q=3 becomes m=4 (because m==M (both 3) → R%1==0 (1001.0 has no decimal values) → (int)R/10%10<1 ((int)1001.0/10 becomes 100 → 100%10<1) → "1001".length()>m (4>3) → "1001".length()-q<=1 (4-3<=1) → so m becomes the length of the integer-part "1001" (4))
3.839*4 = 15.356 & m=1,q=1 stays m=1 (because m==M (both 1) → R%1!=0 (15.356 has decimal values) → R<=99 → R%10!=0 (15.356%10==5.356) → m!=0 → so m stays the same (1))
4*7*3 = 84.0 & m=1,q=1 stays m=1 (because m==M (both 1) → R%1==0 (84.0 has no decimal values) → (int)R/10%10>=1 ((int)84/10 becomes 8 → 8%10>=1) → R<=99 → R%10!=0 (84%10==4) → m!=0 → so m stays the same (1))
6.0+4.0 = 10.0 & m=2,q=2 becomes m=3 (because m!=M (m=2, M=1) → R<=99 → R%10==0 (10%10==0) → so m becomes the length of the total R (minus the dot) "10.0".length()-1 (3))
0-8.8 = -8.8 & m=0,q=1 becomes m=1 (because m!=M (m=0, M=1) → R<=99 → R%10!=0 (-8.8%10==-8.8) → m<1 → so m becomes 1)
501*2.0 = 1001.0 & m=3,q=2 becomes m=2 (because m==M (both 3) → R%1==0 (1001.0 has no decimal values) → (int)R/10%10<1 ((int)1001.0/10 becomes 100 → 100%10<1) → "1001".length()>m (4>3) → "1001".length()-q>1 (4-2>1) → so m becomes q (2))

R=new BigDecimal(R).round(new MathContext((R<0?-R:R)<1?m-1:m)).doubleValue();

Now R is rounded based on m.

1001.0 & m=4 becomes 1001.0
0.258 & m=3 becomes 0.26 (because abs(R)<1, m-1 (2) instead of m=3 is used inside MathContext)
-8.8 & m=1 becomes -9.0
1002.0 & m=2 becomes 1000.0

m<M&(p=Math.pow(10,M-m))/10>R?(int)(R/p)*p:R;

This modifies the integer part of R if necessary.

300.+1-300. = 1.0 & m=3,M=3 stays 1.0 (because m>=M → so R stays the same (1.0))
0.4*10 = 4.0 & m=1,M=2 stays 4.0 (because m<M → (10^(M-m))/10<=R ((10^1)/10<=4.0 → 10/10<=4.0 → 1<=4.0) → so R stays the same (4.0))
300+1-300 = 1.0 & m=1,M=3 becomes 0.0 (because m<M → (10^(M-m))/10>R ((10^2)/10>1.0 → 100/10>1.0 → 10>1.0) → so R becomes 0.0 because of  int(R/(10^(M-m)))*(10^(M-m)) (int(1.0/(10^2))*(10^2) → int(1.0/100)*100 → 0*100 → 0)

r=(...)+"";                  // Set `R` to `r` as String (... is the part explained above)
l=r.length()-2;              // Set `l` to the length of `R` minus 2
r=(r=k<1?                    // If `k` is 0 (no decimal values in any of the input-numbers)
      r.replaceAll(z+"0$","")
                             //  Remove the `.0` at the end
     :                       // Else:
      r+"0".repeat(f)
                             //  Append `k` zeroes after the current `r`
  ).substring(0,             // Then take the substring from index `0` to:
     (j=r.length())<m?       //  If the total length of `r` is below `m`:
       j                     //   Leave `r` the same
     :r.contains(".")?       //  Else-if `r` contains a dot
       (j=r.replaceAll("^0\\.0+","").length())<m?
                             //   And `R` is a decimal below 1,
                             //   and its rightmost decimal length is smaller than `m`
        m-~j                 //    Take the substring from index 0 to `m+j+1`
                             //    where `j` is this rightmost decimal length
       :                     //   Else:
        m+1                  //    Take the substring from index 0 to `m+1`
     :                       //  Else:
      m);                    //   Take the substring from index 0 to `m`

This sets R to r as String, and modifies it based on multiple factors.

1203.0 & m=4,k=2 becomes 1203. (because k>=1 → so r becomes 1001.000; r.length()>=m (8>=4) → r.contains(".") → r.length()>=m (8>=4) → substring from index 0 to m+1 (5))
6.9 & m=2,k=2 stays 6.9 (because k>=1 → so r becomes 6.900; r.length()>=m (5>=2) → r.contains(".") → r.length()>=m (5>=2) → substring from index 0 to m+1 (3))
1.0 & m=3,k=0 becomes 1 (because k<1 → so r becomes 1; r.length()<m (1<3) → substring from index 0 to r.length() (1))
25.0 & m=4,k=4 becomes 25.00 (because k>=1 → so r becomes 25.00000; r.length()>=m (8>=4) → r.contains(".") → r.length()>+m (8>=4) → substring from index 0 to m+1 (5))
0 & m=1,k=0 stays 0 (because k<1 → so r stays 0; r.length()>=m (1>=1) → !r.contains(".") → substring from index 0 to m (1))

for(i=r.length();i++<l;)
  r+=0;

This puts trailing zeroes back again to the integer part if necessary.

r="12" & R=1200.0 becomes r="1200"
r="1" & R=10.0 becomes r="10"
r="8" & R=80.0 becomes r="80"

return r.replaceAll(z+"$","");

And finally we return the result, after we've removed any trailing dots.

1203. becomes 1203
5. becomes 5

Can definitely be golfed by a couple hundred bytes, but I'm just glad it's working now. It already took a while to understand each of the cases and what was being asked in the challenge. And then it took a lot of trial-and-error, testing and retesting to get to the result above. And while writing this explanation above I was able to remove another ±50 bytes of unused code..


Like a path-segment; touched for the very first time

Python 2, 315 309 298 382 380 372 bytes

s=sorted
w=lambda(x,y),(X,Y),(z,w):(X-x)*(w-y)-(z-x)*(Y-y)
def I(a,b):p,q=s(a);P,Q=s(b);n,N,m,M=w(p,q,P),w(p,q,Q),w(P,Q,p),w(P,Q,q);return(q>=P)*(Q>=p)if{n,N,m,M}=={0}else(b[1]!=a[0])*(n*N<=0>=m*M)
def f(l):
 i=0
 while i<len(l)-2:
	x=l[i:i+3];i+=1
	if w(*x)==0and s(x)==x:l.pop(i);i-=1
 L=zip(l,l[1:]);return any(I(*l)for l in[(k,x)for i,k in enumerate(L)for x in L[:i]])

Try it online!

Uses the algorithm from here, combined with this SO answer for collinear segments.

Edit: Fixed for line segments continuing in the same direction (eg (0,0),(1,0),(2,0)) by removing the middle point, (resulting in (0,0),(2,0)).


Charcoal, 9 bytes

Ｆ⮌Ａ«↑⮌ι‖↗

Try it online! Link is to verbose version of code. Explanation: Works by drawing the text backwards, transposing the canvas after every word. 10 bytes for string input:

Ｆ⮌Ｓ≡ι ‖↗←ι

Try it online! Link is to verbose version of code. Explanation: Draws the text backwards, transposing the canvas for spaces.


Pyth, 11 8 bytes
.<W-0zz1

A lot more boring than my previous answer.
Every number that contains a 0 digit maps to itself. Any other number maps to the number that has its digits rotated by 1. So for example:
1 -> 1
10 -> 10
15 -> 51 -> 15
104 -> 104
123 -> 231 -> 312 -> 123


What's different in Sesos?

Golfing in Sesos is similar to golfing in brainfuck in that it has limited control flow, and that you have to grapple with the specifics of memory layout.

However, this does not mean you should write brainfuck code first and then translate it instruction-by-instruction to Sesos!

Here are some things that are different:

You barely pay for repeated commands. For example, add 1 is a 1-byte Sesos program. add 100 is a 3-byte Sesos program. add 1000 is still a 3-byte Sesos program. This means that things that would have been prohibitively expensive in brainfuck (e.g. ++++++++++) are fine in Sesos.
Unless you have set mask on, cells are not 8-bit unsigned integers—they are signed bignums. This means that you can do things like store an offset into an array as a cell without having to worry about the possibility of the array being more than 256 elements and causing overflow.
Control flow is a bit more flexible: you have do-while loops that are guaranteed to execute at least once (with the use of nop). You also have jne, which is the equivalent of ,] in a single instruction.


CJam, 3 × 3 (5 symbols)

[5,
S*3
/N*

Try it online in the CJam interpreter.

How it works

[   e# Unmatched [. Does nothing.
 5, e# Push [0 1 2 3 4].
S*  e# Join the integers, separating by spaces. Pushes "0 1 2 3 4".
  3 e#
/   e# Split into chunks of length 3. Pushes ["0 1" " 2 " "3 4"].
 N* e# Join the chunks, separated by linefeeds. Pushes the output.

Output

0 1
 2
3 4


Ruby, 101 97 bytes
Simple approach that calculates the reach from each node and considers if a child node can be reached via any of the other nodes. Seemingly fails on cyclic graphs, but the definition of a DAG implies that it shouldn't be cyclic anyways.
Try it online!
->g{r=->i{i|i.map{|j|r[g[j]||[]]}.inject([],:|)}
g.all?{|e|e==e&e&&e.none?{|i|r[e-[i]].index i}}}


AI01 - Python 3

I can't find a better name for it yet :-P .

Identifier: ray-ai01

Technology: Python 3

Selected: yes

Arguments: ai01.py identifier port

Description: Work by inference. When the number of cards that the owner is not known is less than a threshold, this AI starts to eliminate all impossible solutions by recursive global inference. Otherwise, it use local inference.

#!/usr/bin/env python
import itertools

from speedclue.playerproxy import Player, main
from speedclue.cards import CARDS
from speedclue.protocol import BufMessager

# import crash_on_ipy

class Card:
    def __init__(self, name, type):
        self.name = name
        self.possible_owners = []
        self.owner = None
        self.in_solution = False
        self.disproved_to = set()
        self.type = type

    def __repr__(self):
        return self.name

    def log(self, *args, **kwargs):
        pass

    def set_owner(self, owner):
        assert self.owner is None
        assert self in owner.may_have
        for player in self.possible_owners:
            player.may_have.remove(self)
        self.possible_owners.clear()
        self.owner = owner
        owner.must_have.add(self)
        self.type.rest_count -= 1

    def set_as_solution(self):
        # import pdb; pdb.set_trace()
        assert self.owner is None
        self.type.solution = self
        self.in_solution = True
        for player in self.possible_owners:
            player.may_have.remove(self)
        self.possible_owners.clear()
        self.type.rest_count -= 1

    def __hash__(self):
        return hash(self.name)

class CardType:
    def __init__(self, type_id):
        self.type_id = type_id
        self.cards = [Card(name, self) for name in CARDS[type_id]]
        self.rest_count = len(self.cards)
        self.solution = None

class PlayerInfo:
    def __init__(self, id):
        self.id = id
        self.must_have = set()
        self.may_have = set()
        self.selection_groups = []
        self.n_cards = None

    def __hash__(self):
        return hash(self.id)

    def set_have_not_card(self, card):
        if card in self.may_have:
            self.may_have.remove(card)
            card.possible_owners.remove(self)

    def log(self, *args, **kwargs):
        pass

    def update(self):
        static = False
        updated = False
        while not static:
            static = True
            if len(self.must_have) == self.n_cards:
                if not self.may_have:
                    break
                for card in self.may_have:
                    card.possible_owners.remove(self)
                self.may_have.clear()
                static = False
                updated = True
            if len(self.must_have) + len(self.may_have) == self.n_cards:
                static = False
                updated = True
                for card in list(self.may_have):
                    card.set_owner(self)

            new_groups = []
            for group in self.selection_groups:
                group1 = []
                for card in group:
                    if card in self.must_have:
                        break
                    if card in self.may_have:
                        group1.append(card)
                else:
                    if len(group1) == 1:
                        group1[0].set_owner(self)
                        updated = True
                        static = False
                    elif group1:
                        new_groups.append(group1)
            self.selection_groups = new_groups

            if len(self.must_have) + 1 == self.n_cards:
                # There is only one card remain to be unknown, so this card must
                # be in all selection groups
                cards = self.may_have.copy()
                for group in self.selection_groups:
                    if self.must_have.isdisjoint(group):
                        cards.intersection_update(group)

                for card in self.may_have - cards:
                    static = False
                    updated = True
                    self.set_have_not_card(card)

        # assert self.must_have.isdisjoint(self.may_have)
        # assert len(self.must_have | self.may_have) >= self.n_cards
        return updated

class Suggestion:
    def __init__(self, player, cards, dplayer, dcard):
        self.player = player
        self.cards = cards
        self.dplayer = dplayer
        self.dcard = dcard
        self.disproved = dplayer is not None

class AI01(Player):
    def prepare(self):
        self.set_verbosity(0)

    def reset(self, player_count, player_id, card_names):
        self.log('reset', 'id=', player_id, card_names)
        self.fail_count = 0
        self.suggest_count = 0
        self.card_types = [CardType(i) for i in range(len(CARDS))]
        self.cards = list(itertools.chain(*(ct.cards for ct in self.card_types)))
        for card in self.cards:
            card.log = self.log
        self.card_map = {card.name: card for card in self.cards}
        self.owned_cards = [self.card_map[name] for name in card_names]
        self.players = [PlayerInfo(i) for i in range(player_count)]
        for player in self.players:
            player.log = self.log
        self.player = self.players[player_id]
        for card in self.cards:
            card.possible_owners = list(self.players)
        n_avail_cards = len(self.cards) - len(CARDS)
        for player in self.players:
            player.may_have = set(self.cards)
            player.n_cards = n_avail_cards // player_count \
                + (player.id < n_avail_cards % player_count)
        for card in self.owned_cards:
            card.set_owner(self.player)
        for card in self.cards:
            if card not in self.owned_cards:
                self.player.set_have_not_card(card)
        self.suggestions = []
        self.avail_suggestions = set(itertools.product(*CARDS))
        self.possible_solutions = {
            tuple(self.get_cards_by_names(cards)): 1
            for cards in self.avail_suggestions
        }
        self.filter_solutions()

    def filter_solutions(self):
        new_solutions = {}
        # assert self.possible_solutions
        join = next(iter(self.possible_solutions))
        for sol in self.possible_solutions:
            for card, type in zip(sol, self.card_types):
                if card.owner or type.solution and card is not type.solution:
                    # This candidate can not be a solution because it has a
                    # card that has owner or this type is solved.
                    break
            else:
                count = self.check_solution(sol)
                if count:
                    new_solutions[sol] = count
                    join = tuple(((x is y) and x) for x, y in zip(join, sol))
        self.possible_solutions = new_solutions
        updated = False
        for card in join:
            if card and not card.in_solution:
                card.set_as_solution()
                updated = True
                self.log('found new target', card, 'in', join)

        # self.dump()
        return updated

    def check_solution(self, solution):
        """
        This must be called after each player is updated.
        """
        players = self.players
        avail_cards = set(card for card in self.cards if card.possible_owners)
        avail_cards -= set(solution)
        if len(avail_cards) >= 10:
            return 1
        count = 0

        def resolve_player(i, avail_cards):
            nonlocal count
            if i == len(players):
                count += 1
                return
            player = players[i]
            n_take = player.n_cards - len(player.must_have)
            cards = avail_cards & player.may_have
            for choice in map(set, itertools.combinations(cards, n_take)):
                player_cards = player.must_have | choice
                for group in player.selection_groups:
                    if player_cards.isdisjoint(group):
                        # Invalid choice
                        break
                else:
                    resolve_player(i + 1, avail_cards - choice)

        resolve_player(0, avail_cards)
        return count

    def suggest1(self):
        choices = []
        for type in self.card_types:
            choices.append([])
            if type.solution:
                choices[-1].extend(self.player.must_have & set(type.cards))
            else:
                choices[-1].extend(sorted(
                    (card for card in type.cards if card.owner is None),
                    key=lambda card: len(card.possible_owners)))

        for sgi in sorted(itertools.product(*map(lambda x:range(len(x)), choices)),
                key=sum):
            sg = tuple(choices[i][j].name for i, j in enumerate(sgi))
            if sg in self.avail_suggestions:
                self.avail_suggestions.remove(sg)
                break
        else:
            sg = self.avail_suggestions.pop()
            self.fail_count += 1
            self.log('fail')
        self.suggest_count += 1
        return sg

    def suggest(self):
        sg = []
        for type in self.card_types:
            card = min((card for card in type.cards if card.owner is None),
                key=lambda card: len(card.possible_owners))
            sg.append(card.name)
        sg = tuple(sg)

        if sg not in self.avail_suggestions:
            sg = self.avail_suggestions.pop()
        else:
            self.avail_suggestions.remove(sg)
        return sg

    def suggestion(self, player_id, cards, disprove_player_id=None, card=None):
        sg = Suggestion(
            self.players[player_id],
            self.get_cards_by_names(cards),
            self.players[disprove_player_id] if disprove_player_id is not None else None,
            self.card_map[card] if card else None,
        )
        self.suggestions.append(sg)
        # Iter through the non-disproving players and update their may_have
        end_id = sg.dplayer.id if sg.disproved else sg.player.id
        for player in self.iter_players(sg.player.id + 1, end_id):
            if player is self.player:
                continue
            for card in sg.cards:
                player.set_have_not_card(card)
        if sg.disproved:
            # The disproving player has sg.dcard
            if sg.dcard:
                if sg.dcard.owner is None:
                    sg.dcard.set_owner(sg.dplayer)
            else:
                # Add a selection group to the disproving player
                sg.dplayer.selection_groups.append(sg.cards)
            self.possible_solutions.pop(tuple(sg.cards), None)

        self.update()

    def update(self):
        static = False
        while not static:
            static = True
            for card in self.cards:
                if card.owner is not None or card.in_solution:
                    continue
                if len(card.possible_owners) == 0 and card.type.solution is None:
                    # In solution
                    card.set_as_solution()
                    static = False

            for type in self.card_types:
                if type.solution is not None:
                    continue
                if type.rest_count == 1:
                    card = next(card for card in type.cards if card.owner is None)
                    card.set_as_solution()
                    static = False

            for player in self.players:
                if player is self.player:
                    continue
                if player.update():
                    static = False

            if self.filter_solutions():
                static = False

    def iter_players(self, start_id, end_id):
        n = len(self.players)
        for i in range(start_id, start_id + n):
            if i % n == end_id:
                break
            yield self.players[i % n]

    def accuse(self):
        if all(type.solution for type in self.card_types):
            return [type.solution.name for type in self.card_types]
        possible_solutions = self.possible_solutions
        if len(possible_solutions) == 1:
            return next(possible_solutions.values())
        # most_possible = max(self.possible_solutions, key=self.possible_solutions.get)
        # total = sum(self.possible_solutions.values())
        # # self.log('rate:', self.possible_solutions[most_possible] / total)
        # if self.possible_solutions[most_possible] > 0.7 * total:
        #     self.log('guess', most_possible)
        #     return [card.name for card in most_possible]
        return None

    def disprove(self, suggest_player_id, cards):
        cards = self.get_cards_by_names(cards)
        sg_player = self.players[suggest_player_id]
        cards = [card for card in cards if card in self.owned_cards]
        for card in cards:
            if sg_player in card.disproved_to:
                return card.name
        return max(cards, key=lambda c: len(c.disproved_to)).name

    def accusation(self, player_id, cards, is_win):
        if not is_win:
            cards = tuple(self.get_cards_by_names(cards))
            self.possible_solutions.pop(cards, None)
            # player = self.players[player_id]
            # for card in cards:
            #     player.set_have_not_card(card)
            # player.update()
        else:
            self.log('fail rate:', self.fail_count / (1e-8 + self.suggest_count))
            self.log('fail count:', self.fail_count, 'suggest count:', self.suggest_count)

    def get_cards_by_names(self, names):
        return [self.card_map[name] for name in names]

    def dump(self):
        self.log()
        for player in self.players:
            self.log('player:', player.id, player.n_cards,
                sorted(player.must_have, key=lambda x: x.name),
                sorted(player.may_have, key=lambda x: x.name),
                '\n    ',
                player.selection_groups)
        self.log('current:', [type.solution for type in self.card_types])
        self.log('possible_solutions:', len(self.possible_solutions))
        for sol, count in self.possible_solutions.items():
            self.log('  ', sol, count)
        self.log('id|', end='')

        def end():
            return ' | ' if card.name in [g[-1] for g in CARDS] else '|'

        for card in self.cards:
            self.log(card.name, end=end())
        self.log()
        for player in self.players:
            self.log(' *'[player.id == self.player.id] + str(player.id), end='|')
            for card in self.cards:
                self.log(
                    ' ' + 'xo'[player in card.possible_owners or player is card.owner],
                    end=end())
            self.log()

if __name__ == '__main__':
    main(AI01, BufMessager)

The AI code can be found here.


MATL, 10 bytes

0i2$:tXgZ~

The compiler (and in particular this program) now seems to work in Octave, although it still needs some refinement. You can provisionally use this GitHub commit.

Edit (Mar 30 '16): Try it online!

Example

>> matl 0i2$:tXgZ~
> 9
0  1  2  3  4  5  6  7  8  9
1  0  3  2  5  4  7  6  9  8
2  3  0  1  6  7  4  5 10 11
3  2  1  0  7  6  5  4 11 10
4  5  6  7  0  1  2  3 12 13
5  4  7  6  1  0  3  2 13 12
6  7  4  5  2  3  0  1 14 15
7  6  5  4  3  2  1  0 15 14
8  9 10 11 12 13 14 15  0  1
9  8 11 10 13 12 15 14  1  0

Explanation

0i2$:       % vector 0, 1, 2, ... up to input number
t           % duplicate
Xg          % nd-grid
Z~          % bitxor


Python 3, 194 190 196 193 175 164 162 bytes

def f(n,k):
 for i in range(len(n)-1):
  y=max(n[i:]);j=n[::-1].index(y)
  if(y>n[i])*k:n[i],n[~j]=y,n[i];k-=1
 if len(n)-len({*n})<k%2:n[-2:]=n[:-3:-1]
 return n

Try it online!

Pretty tough to golf this challenge in a real world language - I like it :)

After golfing down to 190 bytes (and below..), I found some cases where the algorithm would not find the maximum possible value. Bugfixing forced me back up to 196 193 bytes :/

... then I found some ways to better handle branching on k and went down below 180 :)

After the comment from Chas Brown, switching from integer to list I/O saved 28 bytes! (And more golfing another 2..)

Then, another bug: the algorithm incorrectly handles remaining swaps, if there are equal digits present. The fix cost 19 bytes.

Algorithm:

For each digit, starting from the leftmost one, swap it with the rightmost maximum digit, if that one is bigger. First line of the for-loop finds the maximum and its index. Second line does the swap.
If there are k' swaps left, swap two equal digits, or the two rightmost k' times. I.e. if  there are two equal digits present, or if k' is even, no more swaps have to be done. Else, just swap the last two digits once.


Ruby, 196

This was way harder that I initially thought. I had to handle a lot of obscure cases and ended up with a lot of ugly code. But is was a lot of fun! :)

Strategy

Every Collatz Sequence ends up with a sequence of powers of 2 (ex: [16, 8, 4, 2, 1]). As soon as a power of 2 is encountered, we divide by 2 until we reach 1. Let's call the first power of 2 in a sequence closest pow2 (as this is also the closest power of 2 to our number using Collatz Distance). For the given range (51-562), all the possible closest pow2 numbers are: [16, 64, 128, 256, 512, 1024]

Short version

The algorithm performs:

a binary search to figure out the closest power of 2 to the current number
a linear search to figure out every previous element in the sequence until the target number is discovered.

Detailed version

Given a game with the target number r, the strategy is the following:

Use binary search to figure out the power of 2 that is closest to r in as few steps as possible.
If the closest power of 2 that was found is the solution, stop. Otherwise continue to 3.
Since the power of 2 that was found is the first power of 2 occurring in the sequence, if follows that that value was reached by doing a (* 3 + 1) operation. (If it came after a /2 operation, then the previous number would also have been a power of 2). Compute the previous number in the sequence by doing the reverse operation (-1 and then /3)
If that number is the target, stop. Otherwise continue to 5.
Given the current number known from the sequence, it is needed to go back and discover the previous number in the sequence. It is not known whether the current number was arrived at by a (/2) or (*3 +1) operation, so the algorithm tries them both and sees which one yields a number that is closer (as Collatz Distance) from the target.
If the newly discovered number is the right one, stop.
Using the newly discovered number, go back to step 5.

The results

Running the algorithm for all the numbers in the 51-562 range takes around a second on a normal PC and the total score is 38665.

The code

Try it online!

require 'set'

# Utility methods
def collatz(n)
  [].tap do |results|
    crt = n
    while true
      results << crt
      break if crt == 1
      crt = crt.even? ? crt / 2 : crt * 3 + 1
    end
  end
end

def collatz_dist(m, n)
  cm = collatz(m).reverse
  cn = collatz(n).reverse
  common_length = cm.zip(cn).count{ |x, y| x == y }
  cm.size + cn.size - common_length * 2
end

GuessResult = Struct.new :response, :score
# Class that can "play" a game, responding
# :right, :closer, :farther or :same when
# presented with a guess
class Game

  def initialize(target_value)
    @r = target_value
    @score = -1
    @dist = nil
    @won = false
  end
  attr_reader :score

  def guess(n)
    # just a logging decorator over the real method
    result = internal_guess(n)
    p [n, result] if LOGGING
    result
  end

  private

  def internal_guess(n)
    raise 'Game already won!' if @won
    @score += 1
    dist = collatz_dist(n, @r)
    if n == @r
      @won = true
      return GuessResult.new(:right, @score)
    end
    response = nil
    if @dist
      response = [:same, :closer, :farther][@dist <=> dist]
    end
    @dist = dist
    GuessResult.new(response)
  end

end

# Main solver code

def solve(game)
  pow2, won = find_closest_power_of_2(game)
  puts "Closest pow2: #{pow2}" if LOGGING

  return pow2 if won
  # Since this is the first power of 2 in the series, it follows that
  # this element must have been arrived at by doing *3+1...
  prev = (pow2 - 1) / 3
  guess = game.guess(prev)
  return prev if guess.response == :right

  solve_backward(game, prev, 300)
end

def solve_backward(game, n, left)
  return 0 if left == 0
  puts "***      Arrived at  ** #{n} **" if LOGGING
  # try to see whether this point was reached by dividing by 2
  double = n * 2
  guess = game.guess(double)
  return double if guess.response == :right

  if guess.response == :farther && (n - 1) % 3 == 0
    # try to see whether this point was reached by *3+1
    third = (n-1) / 3
    guess = game.guess(third)
    return third if guess.response == :right
    if guess.response == :closer
      return solve_backward(game, third, left-1)
    else
      game.guess(n) # reset to n...
    end
  end
  return solve_backward(game, double, left-1)
end

# Every Collatz Sequence ends with a sequence of powers of 2.
# Let's call the first occurring power of 2 in such a sequence
# POW2
#
# Let's iterate through the whole range and find the POW2_CANDIDATES
#
RANGE = [*51..562]
POWERS = Set.new([*0..15].map{ |n| 2 ** n })

POW2_CANDIDATES =
  RANGE.map{ |n| collatz(n).find{ |x| POWERS.include? x} }.uniq.sort
# Turns out that the candidates are [16, 64, 128, 256, 512, 1024]

def find_closest_power_of_2(game)
  min = old_guess = 0
  max = new_guess = POW2_CANDIDATES.size - 1
  guess = game.guess(POW2_CANDIDATES[old_guess])
  return POW2_CANDIDATES[old_guess], true if guess.response == :right
  guess = game.guess(POW2_CANDIDATES[new_guess])
  return POW2_CANDIDATES[new_guess], true if guess.response == :right
  pow2 = nil

  while pow2.nil?

    avg = (old_guess + new_guess) / 2.0

    case guess.response
    when :same
      # at equal distance from the two ends
      pow2 = POW2_CANDIDATES[avg.floor]
      # still need to test if this is correct
      guess = game.guess(pow2)
      return pow2, guess.response == :right
    when :closer
      if old_guess < new_guess
        min = avg.ceil
      else
        max = avg.floor
      end
    when :farther
      if old_guess < new_guess
        max = avg.floor
      else
        min = avg.ceil
      end
    end

    old_guess = new_guess
    new_guess = (min + max) / 2
    new_guess = new_guess + 1 if new_guess == old_guess
    # so we get next result relative to the closer one
    # game.guess(POW2_CANDIDATES[old_guess]) if guess.response == :farther
    guess = game.guess(POW2_CANDIDATES[new_guess])

    if guess.response == :right
      pow2 = POW2_CANDIDATES[new_guess]
      break
    end

    if min == max
      pow2 = POW2_CANDIDATES[min]
      break
    end

  end

  [pow2, guess.response == :right]

end

LOGGING = false

total_score = 0
51.upto(562) do |n|
  game = Game.new(n)
  result = solve(game)
  raise "Incorrect result for #{n} !!!" unless result == n
  total_score += game.score
end
puts "Total score: #{total_score}"


Jelly, 3 bytes in Jelly's codepage

FẊṁ

Explanation:

FẊṁ
F    flatten list
 Ẋ   shuffle the output from the previous line
  ṁ  unflatten the list, shaping it like…

Because the program is incomplete (ṁ doesn't have a second argument stated), the default is to use the program input; thus ṁ causes the output to have the same sublist pattern as the input.

Try it online!


05AB1E (legacy),  9  7 bytes

Saved 2 bytes thank to @KevinCruijssen

µNÓ0Kp»

Try it online!

µ           # while counter_variable != input:
 N          #   push iteration counter                       e.g. 125
  Ó         #   get prime exponents                          -> [0, 0, 3]
   0K       #   filter out zeros                             -> [3]
     p      #   is prime?                                    -> [1]
      »     #   join with newlines: we use » instead of J
            #   so that [0,1] is not interpreted as truthy   -> 1
            #   implicit: if 1, increment counter_variable


Not-endless Recursion without a base case

C - factorial
simple as that
int not_factorial(int n){return 1;}
int factorial(int n)
{
    int (*maybe_factorial[])(int) = {factorial, not_factorial};
    return n*maybe_factorial[!(n-1)](n-1);
}

the function factorial is almost like a basic recursive approach but not_factorial only returns 1.If I create an array of function pointers
(0: fac, 1: not_fac), then I can control which one should be executed at the next call:
maybe_factorial[0](n-1) calls factorial
maybe_factorial[1](n-1) calls not_factorial.
!(n-1) means if n > 1 return 0 else return 1


C (gcc), 308 306 bytes

Function f receives (height, width, flattened array, pointer to ans), and returns answer by pointer.

If there's no 1 in the matrix, it will return 0.

#define v A[i]
N,M,K,R,C,T,i,*A;s(x,y){i=x*M+y;if(!(x<0|y<0|x>=N|y>=M|v^1))v=2,s(x,y+1),s(x,y-1),s(x+1,y),s(x-1,y);}g(i){if(C<R){if(i^K){g(i+1);if(!v)C+=v=1,g(i+1),v=0,C--;}else{T=1;for(i=0;i<K&&!v;i++);s(i/M,i%M);for(i=0;i<K;i++)T&=v^1,v=!!v;if(T)R=C;}}}f(n,m,a,b)int*a,*b;{K=R=(N=n)*(M=m),A=a;g(0);*b=R;}

Try it online!

Ungolfed:

N,M,R,C,T,i,*A; // height, width, result, recursion depth

s(x,y)
{ // depth first search: replace all 1 in the same connected component with 2
    i=x*M+y;
    if(!(x<0|y<0|x>=N|y>=M|A[i]^1)) { // check if out of boundary
        A[i]=2;
        s(x, y+1),s(x, y-1),s(x+1, y),s(x-1, y);
    }
}

g(i)
{ // enumerate all posible solutions
    if(C<R) {
        if(i!=N*M) {
            g(i+1);      // nothing change for this entry
            if (!A[i]) { // set the entry to 1
                C++, A[i]=1;
                g(i+1);
                C--, A[i]=0;
            }
        }
        else {
            T=1;
            for (i=0; i<N*M && !A[i]; i++); // find first non-zero entry
            s(i/M, i%M);     // replace the connected component
            for (i=0; i<N*M; i++) {
                T&=A[i]!=1;   // check if no other components
                A[i]=!!A[i]; // change 2s back to 1
            }
            if (T) R=C;      // update answer
        }
    }
}

f(n,m,a,b)int*a,*b;{
    R=(N=n)*(M=m), A=a;
    g(0);
    *b=R;
}


CJam, 78 76 73 68 62 bytes

relA,s-:_2ew{:-},{{i"x8LÑejPG ÀÏi"225b28b=A+Ab}/.-:ma}%e`,

Note that the code contains unprintable characters.

Borrowing @isaacg's clever idea of using RLE to count the paths saved 6 bytes.

Try it online in the CJam interpreter. If the link doesn't work, copy the code from this paste.

How it works

rel      e# Read a token from STDIN and cast it to lowercase.
A,s-     e# Remove all digits.
:_       e# Duplicate each element of the argument (string/array).
2ew      e# Push all overlapping slices of length 2.
{:-},    e# Filter out slices where both elements are equal.
{        e# For each slice:
  {      e#   For each character of the slice:
    i    e#     Push its code point.

    "x8LÑejPG ÀÏi"225b28b

         e#     Convert the string from base 225 to base 28, pushing the array
         e#     [15 7 16 17 18 27 26 8 9 0 3 11 4 6 24 1 22 5 21 10 25 23 12 2 13 14].
         e#     These are the positions on the QWERTY keyboard, starting from the
         e#     upper left corner and going right.

    =    e#     Select the element that corresponds to the code point.

         e#     Arrays wrap around in CJam. Since 'a' has code point 97, the array has
         e#     length 26 and 97 % 26 == 19, 'a' corresponds to the 20th element.

    A+Ab e#     Add 10 and convert to base 10. Example: 8 -> [1 8]
  }/     e#
  .-     e#     Vectorized subtraction. [a b] [c d] -> [a-c b-d]
  :ma    e#     atan2. Pushes the angle of the direction. [y x] -> arctan(y/x)
}%       e#
e`       e# Apply run-length encoding.
,        e# Count the runs.


APL (Dyalog Unicode), 30 chars

×/!⍨,z,1÷((z←!∘≢⊢)⌸⊢),×∘≢!⍨1⊥⊢

Try it online!

Using @orlp’s formula.