Extreme Whitewater Canoeing You are paddling a canoe down a fairly fast whitewater river. Suddenly, your paddles explode, and you find yourself in a dangerous situation hurtling down a river rapid without any paddles. Luckily, you still have your programming skills, so you decide to carve a program on the side of your canoe to help you survive the rapids. However, there is not much surface area on the side of the canoe to write your program with, so you must make the program as short as possible.

The river can be represented as an 8 by 16 grid. We will label the columns with the numbers 0 to 7 and the rows with the numbers 0 to 15.

        y
--------15
--------14
--------13
--------12
--------11
--------10
--------9
--------8
--------7
--------6
--------5
--------4
--------3
--------2
--------1
--------0
01234567
x

Above: A completely calm, ordinary river with no obstructions. Naturally, this is not the river you are on.

You begin at the coordinate (4, 0) and from there move uncontrollably up the river (i.e. the vector (0,1)) until you hit a rock (represented by an o in these examples). When you hit a rock, you will have a 55% chance of moving past the rock to the left (i.e. the vector (-1,1)) and a 45% chance of moving past the rock to the right (i.e. the vector (1,1)). If the canoe is on the far left or right columns, it will always move towards the centre. If there are no rocks, it will move straight upwards.

        y
----x---15
----xo--14
-o--x---13
----x---12
---ox---11
---x----10
---xo---9
---ox---8
----xo--7
-----x--6
----ox--5
-o--x---4
----x---3
----xo--2
----x---1
----x---0
01234567

Above: A possible route the canoe might take, represented using the character x

Given the map of the river, write a program that will output the probability of the canoe finishing at a given column.

Accept input in whichever method is convenient for your program (e.g. STDIN, command line argument, raw_input(), reading from a file, etc). The first part of the input is a single integer from 0 to 7, representing the column the program will find the probability for. Following that is a list of tuples in the form x,y representing the position of the stones.

An example:

Input:

4 4,1 5,5 3,5

This would indicate a river with rocks at the positions (4,1), (5,5), and (3,5), and asks for the probability of the canoe ending at the 4th column.

Output:

0.495

Note that in this example, the positions of the rocks were symmetrical, allowing the problem to be solved with a binomial distribution. This won't always be the case!

Also, the river will always be crossable. That is, there will never be two rocks that are positioned adjacent to each other horizontally. See Glenn's comment for an example of an impossible case.

This is code golf, so lowest number of characters wins. Feel free to ask questions in the comments if the specification isn't clear.

Ruby, 204 191 172 characters

c,*r=gets.split
o=[0]*8
s=->x,y,p{y>14?o[x]+=p :(r.index("#{x},#{y+=1}")?(x<1?s[x+1,y,p]:(x>6?s[x-1,y,p]:(s[x-1,y,p*0.55]+s[x+1,y,p*0.45]))):s[x,y,p])}
s[4,0,1]
p o[c.to_i]

It recursively simulates all possibly outcomes while keeping track of each individual outcome's probability, then it adds that probability to a cumulative counter when y == 15.

Fancy tricks:

c,*r=gets.split - the "splat" operator (*) takes all the remaining elements of gets.split and sticks them in the r array
next {something} if {condition}: essentially equivalent to

if {condition}
    {something}
    return
end

"Discovered" by evolving from if condition; something; return; end to return something if condition to break something if condition, and then I figured I would try a shorter "loop operator" to see if it would work (which it did, of course).
Thanks to @MartinBüttner for suggesting to use chained ternary operators (which ended up becoming the enormous third line in the golfed code above) and eliminating the above point (which saved 19 (!) characters).

I did use a somewhat fancy trick with those, though: I realized that s[foo],s[bar] doesn't work in Ruby for two method calls in one statement. So at first I changed it to (_=s[foo],s[bar]) (a dummy variable), but then I realized I could just add and throw away the return values: s[foo]+s[bar]. This only works because calls to s will only ever "return" other calls to s or a number (o[x]+=p), so I don't have to worry about checking for nil.
Other various optimizations: p instead of puts for printing numbers, <1 instead of ==0 (since the canoe never leaves the river) and similar comparisons elsewhere, [0]*8 for initial probabilities as Ruby's numbers are always "pass by value"

Ungolfed:

column, *rocks = gets.chomp.split
outcomes = Array.new(8, 0)
simulate = -> x, y, probability {
    if y == 15
        outcomes[x] += probability
    elsif rocks.index("#{x},#{y + 1}")
        case x
        when 0 then simulate[x + 1, y + 1, probability]
        when 7 then simulate[x - 1, y + 1, probability]
        else
            simulate[x - 1, y + 1, probability * 0.55]
            simulate[x + 1, y + 1, probability * 0.45]
        end
    else
        simulate[x, y + 1, probability]
    end
}
simulate[4, 0, 1.0]
p outcomes
puts outcomes[column.to_i]


Shortening a long number When dealing with long numbers when code golfing, getting the length of your code down can be difficult, so do you have any tips for making a number shorter and easier to manage?

For example, the following Pyth code prints "Hello world", but at 44 bytes, that is unsatisfactory:

Vcjkj85942000775441864767076 2 7=k+kCiN2)k

So how would I shorten the long number, 85942000775441864767076?

Perfect timing for this question. @isaacg just added a new feature today, that allows to shorten such numbers immensely.

The basic technique is to convert the number to base 256 and convert it to chars. You can do this using the code ++NsCMjQ256N. You can then use the resulting string in combination with C, which does exactly the opposite (convert chars to int and interpret the result as base-256 number). So you get 13 chars: C"2ìÙ½}ü¶d". Some of the chars are unprintable.

But notice that I said 13 CHARS, not bytes. If I copy the chars and count the with https://mothereff.in/byte-counter, it says 13 chars and 18 bytes. This is due the character encoding of chars, which is UTF-8 by default. And UTF-8 only allows 2^7 different 1-byte character. Every char c with ord(c) > 127 actually gets stored using two bytes instead of one.

And here come's @isaacg's new feature into play. He changed the default code-format from UTF-8 to iso-8859-1. iso-8859 can represent 256 characters with only 1 byte. So now you can actually reach 13 BYTES. This is only possible with the standard compiler though, this doesn't work in the online compiler.

First you want to convert the number to hex-values by using this script: jdm.[2.Hd"0"jQ256. This gives you  12 32 ec d9 bd 07 7d fc b6 64.  Afterwards copy those numbers into your code-file using a hex-editor (e.g. hexedit for linux).

Notice:

Obviously you remove the " at the end, if the string is the last part of the code.
This only works if there is no 34 (the byte 22) in the base-256 representation of you numbers, since this is the " char and will end the string. Escaping works though (5C 22).
Btw, when you open a file with a hex-editor you will likely see the byte 0A or 0d 0a at the end, which you can remove. This only indicates the end of the line.


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

Need to use a method on variable for which you haven't yet constrained the type? Just compare it against a literal of the type you want it to be then throw away the result to annotate that variable's type:

let f (x:string)=x.Length
let f x=x="";x.Length


Produce an unexpected word The goal is to write program that will produce a word unexpectedly (program doesn't look like it is going to produce a word).

Example (JavaScript):

alert(([0][1]+"").slice(4,8))

  alerts "fine" - jsfiddle.

Explanations:

   1. [0][1] returns undefined, because there only one element in array [0]
 2.  Adding empty string converts undefined to string "undefined"
 3. slice(4,8) outputs fifth to eight characters of undefined

This is underhanded popularity contest.

Python2.x

import re
try: re.compile("[")
except re.error, e: print e.message.split()[0]

try it


Predict the Landslide Landslides

In this challenge, your job is to predict the extent of damage caused by a massive landslide.
We use the following simplified two-dimensional model for it, parameterized by an initial height h >= 0 and a critical coefficient c > 0.
You start with a cliff of height h, and it is assumed that the terrain is completely flat infinitely to the left and to the right of it.
For h = 6, the situation looks like this:

##########
##########
##########
##########
##########
##########
-----------------------

The - are immovable bedrock, and the # are unstable soil.
If the height difference between two neighboring columns is more than c, a landslide occurs: the top c units of soil from the left column fall down to the next c columns on the right, one to each.
The rightmost non-empty column in the figure is unstable for c = 2, so a landslide is triggered:

#########
#########
##########
##########
##########
############
-----------------------

The column is still unstable, which causes a second landslide:

#########
#########
#########
#########
############
############
-----------------------

Now, the column on its left has become unstable, so a new landslide is triggered there:

########
########
#########
###########
############
############
-----------------------

After this, the cliff is stable again.
The nice thing about this model is that the order in which the landslides are processed does not matter: the end result is the same.

The Task

Your program is given the integer parameters h and c as inputs (the order does not matter, but you must specify it on your answer), and it should output the total number of columns that the landslide affects.
This means the number of columns in the resulting stable cliff whose height is strictly between 0 and h.
In the above example, the correct output is 4.

You can write a full program or a function.
The lowest byte count wins, and standard loopholes are disallowed.

Test Cases

These are given in the format h c -> output.

0  2  -> 0
2  3  -> 0
6  2  -> 4
6  6  -> 0
10 1  -> 10
15 1  -> 14
15 2  -> 11
15 3  -> 6
40 5  -> 16
80 5  -> 28
80 10 -> 17

CJam, 62 57 bytes

As far as I can see, this is completely different approach to implement the solution from aditsu's answer.

q~:C;:HaH)*H){(:I\_@>2<:-C>{I0a*C~)+C1a*+]z1fb_,}I?}h-H-,

Input goes in the form of h c

Example:

80 5

Output:

28

How it works

The logic is pretty straight forward here with a few tricks used to reduce code size.

Get h + 1 (+ 1 for h = 0 case) length array with each element being h to represent the cliff
Start iterating from the right most index of this array

If the two elements from current index have different more than c

Remove c from the current index element
Add 1 to next c elements of the array from the current index
Make the current index equal to the length of this new array
This makes sure that we stabilize the stones to the right of the current index first

else, reduce the current index

When we hit the left most index, we are making sure that all adjacent indexes have less than or equal to c difference
Remove any 0 or h value from the array and get length.

Code expansion

q~:C;:HaH)*H){(:I\_@>2<:-C>{I0a*C~)+C1a*+]z1fb_,}I?}h-H-,
q~:C;:HaH)*H)
q~:C;:H                  "Read the input, evaluate it, store height in H and coeff. in C";
       aH)*              "Wrap the height number in an array and repeat it H + 1 times";
           H)            "Put H+1 on stack, representing the current index of iteration";
{(:I\_@>2<:-C>{I0a*C~)+C1a*+]z1fb_,}I?}h
(:I\_@>2<:-C>
(:I                      "Decrement the current index and store it in I";
   \_                    "Swap to put array on top and make 1 copy";
     @>2<                "Get the two elements starting from Ith index";
         :-              "Get the difference. The best part of this approach is that";
                         "For the right most index, where there is only element, it";
                         "returns the element itself, which is the expected difference";
           C>            "Check if difference is greater than C";
{I0a*C~)+C1a*+]z1fb_,}   "This block will be executed when the difference is more than C";
 I0a*                    "Get an array of I length and all elements 0";
     C~)+                "Get -C value and append it to the above array";
         C1a*+           "Get C length array of 1s and concat with the above array";
              ]          "Wrap the two arrays, the cliff and the above one in an array";
               z1fb      "Transpose to get number pairs and add those pairs. For example";
                         "If we are at the right most index with H = 80 and C = 5,";
                         "The right section of the cliff looks like:";
                         "[ ... 80 80 80 80 80] and the array created in above step";
                         "looks like [ ... 0 0 0 0 -5 1 1 1 1 1]. After z, we have:";
                         "[ ... [80 0] [80 0] [80 0] [80 0] [80 -5] [1] [1] [1] [1] [1]]";
                         "After 1fb we get [ ... 80 80 80 80 75 1 1 1 1 1]";
                   _,    "Take a copy of the above resultant array and take its length";
I?                       "If difference was not greater than C, put I on stack";
                         "Now we either have the decremented index or new array length";
                         "on stack."
{ ... }h                 "This is a do while loop which makes sure that we iterate to";
                         "the left of the array. This loops runs till the top stack";
                         "element is 0 while not popping the top element";
        -H-,             "After the loop, we have the final cliff array and 0 on stack";
                         "Remove any 0 elements from the array, then remove any H";
                         "elements from the array and then take length to get the";
                         "number of columns which were modified";

Try it online here


Third time the charm Your task, if you wish to accept it, is to write a program that outputs a positive integer (higher than 0). If the source code is duplicated the output must remain the same. The tricky part is that if the source code is typed three times (triplicated?) the output will be multiplied by 3.
Rules

You must build a full program. That is, your output has to be printed to STDOUT.

The initial source must be at least 1 byte long.

Both the integers must be in base 10 (outputting them in any other base or with scientific notation is forbidden).

Your program must not take input (or have an unused, empty input).

Outputting the integers with trailing / leading spaces is allowed.

Leading Zeroes are allowed only if the numbers of digits is consistent eg: 001 - 001 - 003 or 004 - 004 - 012

You may not assume a newline between copies of your source.

This is code-golf, so the shortest (original) code in each language wins!

Default Loopholes apply.

Example
Let's say your source code is Abc and its corresponding output is 4. If I write AbcAbc instead and run it, the output must still be 4. However if I write AbcAbcAbc and run it, the output must be 12.

Shamelessly stolen Derived from Mr. Xcoder's challenge

Wumpus, 6 bytes

{~)
@O

Try it online!
Try it doubled!
Try it tripled!

Prints 1 and 3.

Explanation

I found a ton of 6-byte solutions by brute force search, but none for 5 bytes. That doesn't necessarily mean there aren't any at 5 bytes but they'd probably use weird characters or something.

I ended up picking this solution because it doesn't print any leading zeros (most of them do) and it has some interesting control flow. Let's start with the single program:

So the executed code is:

{~)O@

{   Turn the IP left by 60°.
~   Swap two implicit zeros on the stack, does nothing.
)   Increment the top zero to 1.
O   Print it.
@   Terminate the program.

Easy enough. Now the doubled program. Since the first line gets appended onto the second line, the grid extends to width 5 (and height 3) which changes the control flow significantly:

The IP goes around that loop exactly once, so the executed code is:

{~){~)){~O@

{~) As before, we end up with a 1 on top of the stack.
{   Turn left by 60° again.
~   Swap the 1 with the 0 underneath.
))  Increment the zero to 2.
{   Turn left by 60° again.
~   Swap the 2 with the 1 underneath.
O   Print the 1.
@   Terminate the program.

Finally, the tripled program is quite similar to the doubled one, but we get a couple more important commands onto that third line:

So the executed code is:

{~){~)){~~)O@

{~){~)){~
    As before. We end up with a 1 on top of the stack and a 2 underneath.
~   Swap the 1 with the 2 underneath.
)   Increment the 2 to a 3.
O   Print the 3.
@   Terminate the program.


Drawing Epicyclogons An epicycloid is the curve a point on a circle makes as it rolls around another circle. A cyclogon is the shape a point on a regular polygon makes as it rolls across a plane. An epicyclogon is the curve traced by a point on one regular polygon as it rolls around another.

Write a program that draws an epicyclogon given r, r1, r2, n1, n2:

r = number of clockwise revolutions rolling polygon makes around stationary polygon (any real number as limited by float values)
r1 = distance from center of stationary polygon to each of its vertices (positive real number)
r2 = distance from center of rolling polygon to each of its vertices (positive real number)
n1 = number of sides stationary polygon has (integer greater than 2)
n2 = number of sides rolling polygon has (integer greater than 2)

Notes

When r is negative the roller should go counterclockwise.
For r, one revolution occurs when the line connecting the centroids of the two shapes sweeps out a full 360 degrees. This notion is expanded to include all values of r. (So in a quarter revolution the line connecting the centroids sweeps out 90 degrees.)
These arguments should come from the command line or your program should prompt for them (e.g. with Python's input()).
r1 and r2 are relative to each other, not the dimensions of the image. So you can set one "unit" to be any number of actual pixels.

The point you must trace out is one of the vertices of the rolling shape. The shapes must start with this vertex touching a stationary vertex and two sides adjacent:

The exact starting vertices and the angle of the stationary polygon do not matter.

Output

The output should go to an image that is at least 600x600 pixels (or some variable dimension than can be set to 600). It must show the entire epicyclogon curve specified by the parameters, well framed in the image.

The rolling and stationary polygons must also be drawn (with the roller in it's final state). The two shapes and the epicyclogon should be three noticeably different colors.

There must also be a simple way to not draw the polygons (a change of true to false in the code suffices).

Please show us at least 2 output images. It's ok to shrink them if necessary.

Scoring

The shortest code that produces valid output images wins.

Bonuses

Minus 50 bytes if the output is an animated gif (or similar) of the curve being drawn.
Minus 150 bytes if you let n1 and n2 take the value 2 so the shapes become line segments of length 2 * r1 (or r2), "rolling" around each other. How you handle r when n1 and n2 are 2 is up to you since the centroids don't revolve around each other the way they do in other cases. (Not "rolling" at all does not count as handling it.)

Since I am quite eager to see this novel idea executed well (and it's not exactly a cakewalk), I am going to award 150 bounty rep to the winner. The contest will end the same day the bounty runs out.

The bounty will not be awarded to the winner if it is clear that they simply rewrote most of the code from another submission.

Library functions that already happen to do this (if there are any) are not allowed.

Note: This came from my leftover questions that anyone is free to post. But if no one else posts them there's a good chance I will in time. :P

Java - 2,726 2,634 - 200 = 2434 characters

Improved from 3800 ish bytes

Thanks to all for your suggestions (especially pseudonym117), here is the new version.

I added a class P which is the point class and a class L which extends ArrayList

I also added some minor logic changes.

Here is the main class (not golfed):

import java.awt.*;
import java.awt.geom.*;

import javax.swing.*;
public class Polygons2 extends JPanel{
    public static void main(String[] args) throws InterruptedException{new Polygons2(args);}
    double q=Math.PI*2;
    int d=1;
    public Polygons2(String[] args) throws InterruptedException{
        double revolutions=Double.valueOf(args[0])*q;
        double stationaryRadius = Double.valueOf(args[1]);
        double rollingRadius = Double.valueOf(args[2]);
        int stationarySides = Integer.valueOf(args[3]);
        int rollingSides = Integer.valueOf(args[4]);
        double dist = stationaryRadius+rollingRadius+70;
        P sp = new P(dist,dist);
        P rp = new P(sp.x,sp.y-rollingRadius-stationaryRadius);
        //get points for rolling polygon and stationary polygon
        int key=0;
        for(double stationaryAngle=-q/4;stationaryAngle<q-q/4;stationaryAngle+=q/stationarySides){
            P p=new P(Math.cos(stationaryAngle)*stationaryRadius+sp.x,Math.sin(stationaryAngle)*stationaryRadius+sp.y);
            p.k=key;key++;
            stationaryPoints.add(p);
        }
        for(double rollingAngle=q/4;rollingAngle<q+q/4;rollingAngle+=q/rollingSides){
            P p=new P(Math.cos(rollingAngle)*rollingRadius+rp.x,Math.sin(rollingAngle)*rollingRadius + rp.y);
            p.k=key;key++;
            rollingPoints.add(p);
        }
        double g=(q/2)-((q/2-(q/rollingSides))/2) - ((q/2-(q/stationarySides))/2)-.05;
        for(P p:rollingPoints){p.r(getPoint(0), g);}
        //set up JFrame
        JFrame f = new JFrame();
        f.add(this);
        f.setSize((int)dist*2+60,(int)dist*2+60);
        f.setVisible(true);
        int[] pKeys= new int[]{stationaryPoints.get(0).k,rollingPoints.get(0).k};
        int index=1;
        P rc = rollingPoints.c();
        P sc =stationaryPoints.c();
        double currentRadian=Math.atan2(rc.y-sc.y,rc.x-sc.x);
        double totalRadian = 0;
        while(Math.abs(totalRadian)<revolutions){
            P rc2 = rollingPoints.c();
            P sc2 =stationaryPoints.c();
            double angle = Math.atan2(rc2.y-sc2.y,rc2.x-sc2.x);
            if(currentRadian-angle<2){totalRadian+=(angle-currentRadian);}
            currentRadian=angle;
            L clone=(L)path.clone();
            clone.add(new P(rollingPoints.get(1).x,rollingPoints.get(1).y));
            path = clone;
            for(P p:rollingPoints){
                p.r(getPoint(pKeys[index]),.01);
                int size = stationaryPoints.size();
                for(int i=0;i<size;i++){
                    P stationaryPointAtI = stationaryPoints.get(i);
                    P nextPoint=null;
                    if(i==size-1){nextPoint=stationaryPoints.get(0);}
                    else{nextPoint=stationaryPoints.get(i+1);}
                    if(p.b(stationaryPointAtI, nextPoint)==1&&containsKey(pKeys,p.k)==0){
                        //rolling point is between 2 stationary points
                        if(index==1){index=0;}else{index=1;}
                        pKeys[index]=p.k;
                    }
                    int size2=rollingPoints.size();
                    for(int h=0;h<size2;h++){
                        P nextPoint2=null;
                        if(h==size2-1){nextPoint2=rollingPoints.get(0);}
                        else{nextPoint2=rollingPoints.get(h+1);}
                        if(stationaryPointAtI.b(rollingPoints.get(h), nextPoint2)==1&&containsKey(pKeys,stationaryPointAtI.k)==0){
                            //stationary point is between 2 rolling points
                            if(index==1){index=0;}else{index=1;}
                            pKeys[index]=stationaryPointAtI.k;
                        }
                    }
                }
            }
            repaint();
            Thread.sleep(5);
        }
    }
    volatile L path = new L();
    L rollingPoints = new L();
    L stationaryPoints = new L();
    P getPoint(int key){
        for(P p:rollingPoints){if(p.k==key){return p;}}
        for(P p:stationaryPoints){if(p.k==key){return p;}}
        return null;
    }
    int containsKey(int[] keys,int key){
        for(int i:keys){if(key==i){return 1;}}
        return 0;
    }
    @Override
    public void paintComponent(Graphics g){
        Path2D.Double sPath = new Path2D.Double();
        sPath.moveTo(stationaryPoints.get(0).x, stationaryPoints.get(0).y);
        for(P p:stationaryPoints){
            sPath.lineTo(p.x, p.y);
        }
        sPath.closePath();
        Path2D.Double rPath = new Path2D.Double();
        rPath.moveTo(rollingPoints.get(0).x, rollingPoints.get(0).y);
        for(P p:rollingPoints){
            rPath.lineTo(p.x, p.y);
        }
        rPath.closePath();
        g.setColor(Color.white);
        g.fillRect(0,0,getWidth(),getHeight());
        Graphics2D t = (Graphics2D)g;
        if(d==1){
        t.setColor(Color.black);
        t.draw(sPath);
        t.setColor(Color.blue);
        t.draw(rPath);
        }
        g.setColor(Color.green);
        for(P p:path){g.fillOval((int)p.x-1, (int)p.y-1, 2, 2);}
    }
}

And the golfed version:

import java.awt.*;import java.awt.geom.*;import javax.swing.*;import static java.lang.Math.*;class Polygons2Golfed extends JPanel{public static void main(String[]a)throws Exception{new Polygons2Golfed(a);}double q=PI*2;int d=1;public Polygons2Golfed(String[]a)throws Exception{double b,c,f;b=Double.valueOf(a[1]);c=Double.valueOf(a[2]);int d,e;d=Integer.valueOf(a[3]);e=Integer.valueOf(a[4]);f=b+c+100;P o=new P(f,f);P r=new P(o.x,o.y-c-b);int s=0;for(double u=-q/4;u<q-q/4;u+=q/d){P p=new P(cos(u)*b+o.x,sin(u)*b+o.y);p.k=s;s++;l.add(p);}for(double u=q/4;u<q+q/4;u+=q/e){P p=new P(cos(u)*c+r.x,sin(u)*c+r.y);p.k=s;s++;k.add(p);}double g=q/e/2+q/d/2-.05;for(P p:k){p.r(v(0),g);}JFrame j=new JFrame();j.add(this);j.setSize((int)f*2+60,(int)f*2+60);j.setVisible(true);m=new int[]{l.get(0).k,k.get(0).k};int ad=1;P rc=k.c();P sc=l.c();double ab,ac;ab=atan2(rc.y-sc.y,rc.x-sc.x);ac=0;while(abs(ac)<Double.valueOf(a[0])*q){P rc2=k.c();P sc2=l.c();double ah=atan2(rc2.y-sc2.y,rc2.x-sc2.x);if(ab-ah<2)ac+=(ah-ab);ab=ah;L ag=(L)n.clone();ag.add(new P(k.get(1).x,k.get(1).y));n=ag;for(P p:k){p.r(v(m[ad]),.01);int af=l.size();for(int i=0;i<af;i++){P aa=l.get(i);P w=null;if(i==af-1){w=l.get(0);}else{w=l.get(i+1);}if(p.b(aa, w)==1&&w(p.k)==0){if(ad==1)ad=0;else ad=1;m[ad]=p.k;}int ae=k.size();for(int h=0;h<ae;h++){P u=null;if(h==ae-1)u=k.get(0);else u=k.get(h+1);if(aa.b(k.get(h),u)==1&&w(aa.k)==0){if(ad==1)ad=0;else ad=1;m[ad]=aa.k;}}}}repaint();Thread.sleep(5);}}L n=new L();L k=new L();L l=new L();P v(int key){for(P p:k){if(p.k==key)return p;}for(P p:l){if(p.k==key)return p;}return null;}int[]m;int w(int key){for(int i:m){if(key==i)return 1;}return 0;}@Override public void paintComponent(Graphics g){Path2D.Double aq=new Path2D.Double();aq.moveTo(l.get(0).x,l.get(0).y);for(P p:l){aq.lineTo(p.x, p.y);}aq.closePath();Path2D.Double aw=new Path2D.Double();aw.moveTo(k.get(0).x, k.get(0).y);for(P p:k){aw.lineTo(p.x, p.y);}aw.closePath();g.setColor(Color.white);g.fillRect(0,0,getWidth(),getHeight());Graphics2D t=(Graphics2D)g;if(d==1){t.setColor(Color.black);t.draw(aq);t.setColor(Color.blue);t.draw(aw);}g.setColor(Color.green);for(P p:n){g.fillOval((int)p.x-1,(int)p.y-1,2,2);}}}

As well as classes P:

import java.awt.geom.*;class P{double x,y;public P(double a,double b){x=a;y=b;}int k;void r(P c,double g){double a,r;a=Math.atan2(y-c.y,x-c.x)+g;r=Math.sqrt((c.x-x)*(c.x-x)+(c.y-y)*(c.y-y));x=Math.cos(a)*r+c.x;y=Math.sin(a)*r+c.y;}public int b(P a,P b){if(Line2D.ptSegDist(a.x,a.y,b.x,b.y,x,y)<.5)return 1;return 0;}}

And L:

import java.util.*;public class L extends ArrayList<P>{public P c(){double x,y;x=0;y=0;for(P p:this){x+=p.x;y+=p.y;}return new P(x/size(),y/size());}}

Change int d to 0 or 1 to show polygons

arguments - 1 100 50 5 2

args - 1.5 100 100 7 3

args - 2 40 100 3 7


Number of FIFO cache misses This challenge is really simple (and a precursor to a more difficult one!).

Given an array of resource accesses (simply denoted by nonnegative integers) and a parameter n, return the number of cache misses it would have assuming our cache has capacity n and uses a first-in-first-out (FIFO) ejection scheme when it is full.

Example:

4, [0, 1, 2, 3, 0, 1, 2, 3, 4, 0, 0, 1, 2, 3]
0 = not in cache (miss), insert, cache is now [0]
1 = not in cache (miss), insert, cache is now [0, 1]
2 = not in cache (miss), insert, cache is now [0, 1, 2]
3 = not in cache (miss), insert, cache is now [0, 1, 2, 3]
0 = in cache (hit), cache unchanged
1 = in cache (hit), cache unchanged
2 = in cache (hit), cache unchanged
3 = in cache (hit), cache unchanged
4 = not in cache (miss), insert and eject oldest, cache is now [1, 2, 3, 4]
0 = not in cache (miss), insert and eject oldest, cache is now [2, 3, 4, 0]
0 = in cache (hit), cache unchanged
1 = not in cache (miss), insert and eject oldest, cache is now [3, 4, 0, 1]
2 = not in cache (miss), insert and eject oldest, cache is now [4, 0, 1, 2]
3 = not in cache (miss), insert and eject oldest, cache is now [0, 1, 2, 3]

So in this example there were 9 misses. Maybe a code example helps explain it better. In Python:

def num_misses(n, arr):
    misses = 0
    cache = []
    for access in arr:
        if access not in cache:
            misses += 1
            cache.append(access)
            if len(cache) > n:
                cache.pop(0)
    return misses

Some further testcases (which contains a hint towards the next challenge - notice anything curious?):

0, [] -> 0
0, [1, 2, 3, 4, 1, 2, 3, 4] -> 8
2, [0, 0, 0, 0, 0, 0, 0] -> 1
3, [3, 2, 1, 0, 3, 2, 4, 3, 2, 1, 0, 4] -> 9
4, [3, 2, 1, 0, 3, 2, 4, 3, 2, 1, 0, 4] -> 10

Shortest code in bytes wins.

JavaScript (ES6), 55 bytes
Method #1: the cache overwrites the input
Takes input in currying syntax (cache_size)(list).

n=>a=>a.map(x=>a[a.indexOf(x,k>n&&k-n)<k||k++]=x,k=0)|k

Try it online!
How?
We overwrite the input array a[ ] with the cache, using a separate pointer k initialized to 0.
We use a.indexOf(x, k > n && k - n) < k to test whether x is in the cache.
The cache can't grow faster than the original array is walked through, so each value is guaranteed to be found, either within or beyond the cache window (i.e. indexOf() will never return -1).
A value is in the cache if it is found at an index between max(0, k - n) and k - 1 (both bounds included), in which case we do a[true] = x. This only affects a property of the underlying object behind a[ ] but does not alter the array a[ ]. Otherwise, we do a[k++] = x.
Example
Below are the different steps for the input [1, 1, 2, 3, 3, 2, 1, 4] with a cache size of 2:

bold borders: map() pointer
brackets: cache pointer k
orange: current cache window
yellow: expired cache values

JavaScript (ES6), 57 bytes
Method #2: the cache is appended at the end of the input
Takes input in currying syntax (cache_size)(list).
n=>a=>a.map(x=>n*~a.indexOf(~x,-n)||a.push(~x)&k++,k=0)|k

Try it online!
How?
Because the input array a[ ] is guaranteed to contain non-negative integers, we can safely append the cache at the end of a[ ] by using the one-complement ~x of each value x.
We use n * ~a.indexOf(~x, -n) to test whether ~x is found among the last n values. Whenever this test fails, we append ~x to a[ ] and increment the number of misses k.
Example
Below are the different steps for the same example as above, using this method. Because cache values are simply appended at the end of the array, there is no explicit cache pointer.


Find acronym-like words in a sentence Let's say you have a sentence like:

this is a very long sentence with several words of no significance

It contains only the 26 lowercase letters of the alphabet and spaces.

And you have a dictionary, where each word contains any number of the 26 lowercase letters and nothing else:

henge
renton

Then the output should contain, among others:

tHis is a vEry long seNtence with several words of no siGnificancE
tHis is a vEry long senteNce with several words of no siGnificancE
this is a veRy long sENTence with several wOrds of no significaNce

So, every line of the output is the original sentence, but if only the uppercase letters of a line are taken, they should form a dictionary word. The program should find all possible such lines.

JavaScript, 474 bytes
k=((e,r)=>{for(o=[],e=[...e],r=[...r],w=r.reduce((r,h,n)=>!(r[n]=e.map((e,r)=>h==e?r:"").filter(Number))||r,[]),[z]=w,h=[],x=0;x<w.reduce((e,r)=>e*=r.length||e,1);x++)z.forEach((e,r)=>{for(g=[z[r]],j=1;j<w.length;j++)for(n=w[j],y=0;y<n.length;y++)if(g.slice(-1)[0]<n[y]&&!h.some(e=>e.toString()==[...g,n[y]].toString())){g.push(n[y]);break}h.push(g)});return h.filter(e=>e.length==w.length).forEach(r=>{d=[...e],r.forEach(e=>d[e]=d[e].toUpperCase()),o.push(d.join(""))}),o})

Live example:

k=((e,r)=>{for(o=[],e=[...e],r=[...r],w=r.reduce((r,h,n)=>!(r[n]=e.map((e,r)=>h==e?r:"").filter(Number))||r,[]),[z]=w,h=[],x=0;x<w.reduce((e,r)=>e*=r.length||e,1);x++)z.forEach((e,r)=>{for(g=[z[r]],j=1;j<w.length;j++)for(n=w[j],y=0;y<n.length;y++)if(g.slice(-1)[0]<n[y]&&!h.some(e=>e.toString()==[...g,n[y]].toString())){g.push(n[y]);break}h.push(g)});return h.filter(e=>e.length==w.length).forEach(r=>{d=[...e],r.forEach(e=>d[e]=d[e].toUpperCase()),o.push(d.join(""))}),o})

console.log(k('this is a very long sentence with several words of no significance', 'henge'));

Explanation:
For each letter in the word, an array of indices is constructed corresponding to every position of that letter in the sentence.
Then inside a nest of 4 for loops, every possible path from the first array to the last array is computed, where each step is into an element with greater numeric value in the next array.
This produces an array of paths whose length is equal to the maximum possible paths, which is the product of multiplying the length of each letter indices array (this number gets big real quick as the length of the word increases).
Then all paths whose length is smaller than the word are excluded, since they failed to find a valid step between each array.
You can see the unminified logic at this stackoverflow answer.
I am confused by this line (even though it's my code), whose intent is to check the existing paths before adding a step to the current path to make sure its constructing a unique path:
if (!paths.some(p => p.toString() == [...path, arrays[j][y]].toString())) {
  path.push(arrays[j][y]);
  break;
}

It seems to me like this should erroneously prevent construction of multiple paths who share any beginning steps.  But it actually works as intended.  So I am stumped.


Print a specific value in the infinite Walsh matrix The Walsh matrix is an interesting fractal matrix with the property that every single value in a Walsh matrix has a value of either -1 or 1. Additionally, the size of a Walsh matrix is always a power of 2.

Because each Walsh matrix is identical to the top-left quarter of the immediately higher-order Walsh matrix, we can create a generalized "infinite Walsh matrix" by considering the limit of the sequence of Walsh matrices of order N, as N goes to infinity. From here on, we will call this infinite generalization the Walsh matrix.

Your task is to build a program that takes the coordinates of a location in the Walsh matrix and returns the value that occurs there.

Your program will accept two integers x and y as input (in any form you choose), and output the value that appears in the x+1th row of the y+1th column of the Walsh matrix. For example, the input

2 5

will return 1, as the 3rd row in the 6th column of the Walsh matrix has a value of 1. The input

6 4

will return -1, as the 7th row in the 5th column of the Walsh matrix has a value of -1. The input

2834719 394802

will return -1, as the 2384720th row of the 394803rd column has a value of -1.

The shortest code to do this in any language wins.

GolfScript (18 15 14 bytes)

~&2base-1\0-,?

Takes input space-separated; outputs to stdout. Thanks to Howard for pointing out that the space in the 15-char solution was removable.

The way I reasoned to this solution is quite simple. Take the highest set bit of x|y: this tells you the size of the smallest Walsh matrix which contains the relevant index. Then clearing that bit in both x and y drops us down to the top-left quadrant, and we need to multiply by -1 if we were previously in the bottom-right quadrant: i.e. if the bit was set in both x and y. By induction down the bit sequence, we just need to count the number of bits set in x&y.


Magic Sequences of length n A magic sequence is a sequence of non-negative integers x[0..n-1] such that there are exactly x[i] instances of i

For instance, 6,2,1,0,0,0,1,0,0,0 is a magic sequence since there are 6 0's, 2 1’s, and so on.

Write a function which when given n, outputs all magic sequences of length n

The program that can produce the correct output for the highest value of n within 10 seconds win. (All programs are welcome, though)

For example, Alice's program can deal with upto n=15 within 10 seconds while Bob's can deal with upto n=20 within the same time. Bob wins.

Platform: Linux 2.7GHz @ 4 CPUs

Python, n≈108

def magic_sequences(n):
    if n==4:
        return (1, 2, 1, 0),(2, 0, 2, 0)
    elif n==5:
        return (2, 1, 2, 0, 0),
    elif n>=7:
        return (n-4,2,1)+(0,)*(n-7)+(1,0,0,0),
    else:
        return ()

This uses the fact, which I'll prove, that the only Magic sequences of length n are:

[1, 2, 1, 0] and  [2, 0, 2, 0] for n=4
[2, 1, 2, 0, 0] for n=5
[n-4, 2, 1, 0, 0, ..., 0, 0, 1, 0, 0, 0] for n>=7

So, for n>=7, one only needs to return a huge tuple. I can do this for up to roughly n=10^8 on my laptop, which is likely limited by memory; any more and it freezes up. (Thanks to trichoplax for the idea of using tuples rather than lists.) Or, if one can instead print a dictionary of nonzero entries, {0:n-4, 1:2, 2:1, (n-4):1}, one can do this for ginormous n.

I prove the uniqueness for n>=7; the other ones can be checked by brute force or casework.

The sum of the entries of l is the total count of all numbers of the list, which is its length n. The list has l[0] zeroes, and so n-l[0] nonzero entries. But by definition l[0] must be nonzero or we get a contradiction, and each of the other nonzero entries is at least 1. This already accounts for a sum of l[0] + (n-l[0]-1)*1 = n-1 out of the overall sum of n. So not counting l[0], there can be at most one 2 and no entry bigger than 2.

But that means the only nonzero entries are l[0], l[1], l[2], and l[l[0]], whose values are at most l[0] and a permutation of 1,1,2, which gives a maximum sum of l[0]+4. Since this sum is n, which is at least 7, we have l[0]>=3, and so l[l[0]]=1. Now, there's at least one 1, which means l[1]>=1, but if l[1]==1 that's another 1, so l[1]>=2, which implies l[1] is the lone 2. This gives l[2]=1, and all the remaining entries are 0, so l[0]=n-4, which completes the solution.


Tokenize a Stack-Based language I've been working on another stack-based golfing language called Stackgoat. In this challenge you'll  be writing a Tokenizer for Stackgoat (or really any general stack-based languages).

Examples

"PPCG"23+
["PPCG", '23', '+']

'a "bc" +
['"a"', '"bc"', '+']

12 34+-"abc\"de'fg\\"
['12', '34', '+', '-', '"abc\"de'fg\\"']

"foo
['"foo"']

(empty input)
[]

' ""
['" "', '""']

Specification

The three types you'll need to handle are:

Strings, anything within ""
Numbers, any sequence of digits
Operators, any other single character besides whitespace

Whitespace is essentially ignored unless it is within a string or separates two numbers.

String / char spec:

Strings are delimited by a ", and when  a \ is encountered, the next character should be escaped.
Chars are prepended by a ' and the character after the ' should be converted into a string literal. 'a -> "a"
' will always have a character after it
Closing quotes should be auto-inserted

Rules:

No form of eval is allowed

Input / Output:

Input can be taken through STDIN, function parameters, or your language's equivalent.
Output should be an array or your language's closest equivalent.

Retina, 68 64 63 bytes

M!s`"(\\.|[^"])*"?|'.|\d+|\S
ms`^'(.)|^"(([^\\"]|\\.)*$)
"$1$2"

or

s`\s*((")(\\.|[^"])*(?<-2>")?|'.|\d+|.)\s*
$1$2¶
\ms`^'(.)
"$1"

I think this covers all the funky edge cases, even those not covered by the test cases in the challenge.

Try it online!


Construct a pentagon avoiding compass use Rules

You will start with only two elements: Points \$A\$ and \$B\$ such that \$A \neq B\$.  These points occupy a plane that is infinite in all directions.

At any step in the process you may do any of the three following actions:

Draw a line that passes through two points.
Draw a circle centered at one point such that another point lies on the circle.
Add a new point where two objects (lines and circles) intersect.

Your goal is to create 5 points such that they form the vertices of a regular pentagon (a convex polygon with 5 sides equal in length) using as few circles as possible.  You may, of course, have other points but 5 of them must for a regular pentagon.  You do not have to draw the edges of the pentagon for your scoring.

Scoring

When comparing two answers the one that draws fewer circles is better.  In the case of a tie in circles the answer that draws the fewest lines is better.  In the case of a tie in both circles and lines the answer that adds the fewest points is better.

Anti-Rules

While the rules list is exhaustive and details everything you can do, this list is not. Just because I don't say you can't do something does not mean you can.

You cannot create "arbitrary" objects.  Some constructions you will find will do things like add a point at an "arbitrary" location and work from there.  You cannot add new points at locations other than intersections.
You cannot copy a radius.  Some constructions will involve taking a compass setting it to a radius between two points and then picking it up and drawing a circle elsewhere.  You cannot do this.
You cannot perform limiting processes.  All constructions must take a finite number of steps.  It is not good enough to approach the answer asymptotically.
You cannot draw an arc or part of a circle in order to avoid counting it as a circle in your scoring.  If you want to visually use arcs when showing or explaining your answer because they take up less space go ahead but they count as a circle for scoring.

Tools

You can think through the problem on GeoGebra.  Just go over to the shapes tab.  The three rules are equivalent to the point, line and circle with center tools.

Burden of Proof

This is standard but I would like to reiterate.  If there is a question as to whether a particular answer is valid the burden of proof is on the answerer to show that their answer is valid rather than the public to show that the answer is not.

What is this doing on my Code-Golf site?!

This is a form of atomic-code-golf similar to proof-golf albeit in a bit of a weird programming language. There is currently a +22/-0 consensus on the meta that this sort of thing is allowed.

2 circles, 13 lines, 17 points

Try it on GeoGebra

Let circle(A, B) intersect circle(B, A) at C and D.
Let AB intersect circle(A, B) again at E.
Let AB intersect circle(B, A) again at F.
Let AD intersect circle(A, B) again at G.
Let AD intersect CF at H.
Let BG intersect DF at I.
Let HI intersect circle(A, B) at J and K.
Let BG intersect EJ at L.
Let BJ intersect EG at M.
Let BG intersect EK at N.
Let BK intersect EG at O.
Let LM intersect circle(A, B) at P and S.
Let NO intersect circle(A, B) at Q and R.

Then EPQRS is a regular pentagon.

Why it works

Let BE intersect GJ at T, and let BE intersect GK at U.  The complete quadrilateral BEGJ shows that T is the polar of LM, which is the intersection of the tangents at P and S.  Similarly, the complete quadrilateral BEGK shows that U is the polar of NO, which is the intersection of the tangents at Q and R.

Let FG intersect HI at V.  The diagonals DV and GI of the complete quadrilateral DGVI intersect FH at harmonic conjugates with respect to F and H; since the first is at ∞, the second is the midpoint C of FH, which is to say that C, D, V are collinear.

Let CG intersect HI at W.

Now for the fun part.  Line FUBAT is perspective about G to line VKIHJ, which is perspective about D to circle CKDGJ, which is perspective about C to line HKVWJ, which is perspective about G to line AUF∞T.  Composing these four perspecitivities yields a projectivity FUBAT ⌅ AUF∞T.  Since a one-dimensional projectivity is determined by three points, T and U are determined as the two fixed points of FBA ⌅ AF∞.

Assigning coordinates with A = 0, B = −1, F = −2, this projectivity is defined by x ↦ 4/x + 2, and its fixed points T = 1 + √5 = sec(2π/5) and U = 1 − √5 = −sec(2π/10), exactly as required to make EPQRS a regular pentagon.


Counting polydominoes Background
A polyomino of size \$n\$ is a contiguous shape made from joining \$n\$ unit squares side by side. A domino is a size-2 polyomino.
A polydomino of size \$2n\$ is defined as a polyomino of size \$2n\$ which can be tiled with \$n\$ dominoes.
The following are some examples of polydominoes for \$n=3\$ (hexominoes).
. O O  |  . O . .  |  O O O .  |  O O O O O O
O O .  |  O O O O  |  O . O O  |
O O .  |  O . . .  |           |

The following are some hexominoes that are not polydominoes.
. O .  |  O . . .  |  O . O .
O O O  |  O O O O  |  O O O O
O O .  |  O . . .  |

Challenge
Given a positive integer \$n\$, count the number of distinct polydominoes of size \$2n\$. Rotations and reflections are considered as the same shape. Different tilings of the same shape does not count either. You may take the value of \$2n\$ as input instead (you may assume the input is always even in this case).
The following shape has two ways to tile with dominoes, but it is counted only once just like other hexominoes.
. O O
O O .
O O .

The sequence is OEIS 056786.
Test cases
The following are the expected results for \$n=1 \cdots 9\$.
1, 4, 23, 211, 2227, 25824, 310242, 3818983, 47752136

Ruby, 266 250 242 bytes

->n,*z{j=(h=1,m=1i,-1,*r=[-m,0]).product h;(r.map{|c|j.map{|v,w|k=r+[v+=c,v+w];k|k==k&&(w=j.map{|y,q|(x=k.map{|v|y*[v,v.conj][q*q]}).map{|g|g-x.map(&:real).min-m*x.map(&:imag).min}.sort_by &:rect})-z==w&&z<<w[0]}};r,*z=z)until r[-n];z.size+1}

Try it online!
Not particularly original, I just recycled my solution to a similar problem, and changed some small details:

start with the basic domino (instead of single tile)
add 2 tiles on each step (instead of one)
check for reflection by using the complex conjugate (instead of only rotation using powers of i)
stop when reaching size 2n (instead of n) -> Accept 2n as input

How it works:
See the linked post for the full explanation. Basically, use complex numbers to make it easier.
Performance:
43 seconds for n=5 (size 10) on TIO
Thanks Dingus for saving some bytes, the function is a mess and could probably be much shorter anyway if implemented properly.


Solitaire Dreams - Creating a winnable solitaire starting hand It's me. Cave Johnson.

It's May 21st. You are working at Aperture Science, finest company on Earth, and tomorrow we're releasing Version 3.0 of our flagship windowing system (or WindowS): CavOS. Unfortunately, tomorrow morning, our chief competitor is releasing Version 3.0 of their WindowS too!

It's been leaked to me, Cave Johnson, CEO that the competing WindowS has one feature that CavOS lacks: A game of Klondike Solitaire. I, Cave Johnson, am concerned that this omission will lead to drastically lower sales. As such, I, Cave Johnson, have devised a competition between the programming interns to create a game of Solitaire. The programmer whose entry is chosen will get the opportunity to join the exciting GlaDOS AI project.

I, Cave Johnson, has a few requirements:

Due to the fact that the Software must ship tomorrow, the shortest program will be chosen such that it can fit in the spare sectors of the already printed, imaged floppies.
Don't worry about the gameplay. Our customers have printers don't they? All I need is for your program to produce a list showing: The order of the cards in the deck, and the contents of each of the 7 piles. The deck will be dealt from the top. The piles will be visible from the bottom. Use the abbreviations H, D, C, S for Hearts, Diamonds, Clubs and Spades. Use the abbreviations K, Q, J, A for King, Queen, Jack, and Ace. Each card should be separated by a space. The first line should show the deck, the second the card of the first and smallest pile, the third the cards of the second pile and so on. You are welcome to use T instead of 10 if you wish.
We're making lemonade here - not sucking lemons. I, Cave Johnson, don't like losing, and neither do our customers. Every game must be winnable
The game must be randomised. No attempting to encode a single game. There are  7000 trillion possible Klondike hands, and about 90% of them are winnable. I'd be happy with a program that can produce 256 or more different hands. If your language lacks a manner to get random numbers (from a timer or the like), then assume that you can get a seed in a manner appropriate for your language.
Our customers are reasonably clever. Assume for winnability that they're playing Draw 3, with no limits on times through the deck

On behalf of everybody (and everything) at Aperture, I wish you all good luck. We're counting on you.

"Caroline? How do I shut this damn thing off?"

Out of character: assume the rules of Windows, Draw 3, Not-vegas solitaire. I've attempted to cross every t and dot every i, but ask if you've any questions. Good luck.

Example output:

5H AS 7C 8S QH ...
AH
JS 10S
JC JH 7C
9D AC 8D 7C
.
.
.


Is this string a palindrome (in Morse Code)? Challenge

Inspired by this video

As you may know, a palindrome is a word that is spelled the same forward as it is backward. The word "PULP" is not a palindrome, but when translated into Morse Code (with the spacing between letters removed), "PULP" becomes ".--...-.-...--." which is a palindrome. Your task is to write a program or function which takes a string and returns whether that word is a palindrome in International Morse Code.

A: .-
B: -...
C: -.-.
D: -..
E: .
F: ..-.
G: --.
H: ....
I: ..
J: .---
K: -.-
L: .-..
M: --
N: -.
O: ---
P: .--.
Q: --.-
R: .-.
S: ...
T: -
U: ..-
V: ...-
W: .--
X: -..-
Y: -.--
Z: --..

Rules

Input

Input can be taken in any reasonable format. The input string will contain only letters in any case you prefer. The string will not contain spaces, numbers, or punctuation.

Output

Your program should output 1 of 2 constant distinct results based on whether the input is a palindrome, e.g. True/False, 1/0, HOTDOG/NOTHOTDOG

Scoring

This is code-golf so shortest answer in bytes wins. Standard loopholes are forbidden.

Test Cases

Input  =>  Output

"PULP"       => True
"RESEARCHER" => True
"HOTDOGS"    => True
""           => True
"A"          => False
"RACECAR"    => False
"PROGRAMMING"=> False
"PUZZLES"    => False

Jelly, 28 bytes

ØAŻŻ“¡9o|çṫ¡X1ỴỌġQ’œ?iⱮḃ2FŒḂ

Try it online!

ØA                             The uppercase alphabet.
  ŻŻ                           Prepend two zeroes.
    “¡9o|çṫ¡X1ỴỌġQ’œ?          Get the 73540211105102870315464559332nd permutation.
                                  (= “ETIANMSURWDKGOHVF0L0PJBXCYZQ”)
                     iⱮ        Find indices of input letters in this list.
                       ḃ2      Bijective base 2: map [1,2,3,4,5…] to
                                 [1], [2], [1,1], [1,2], [2,1], …
                         F     Flatten.
                          ŒḂ   Is palindrome?

I wrote this answer looking at one of these (read the rows from right-to-left, and you get my magic string!):


Change to conventional algebra notations The Challenge

Given an algebraic expression (eg 2ab, change it so it follows standard convention rules.

The Rules

Letters should be in alphabetical order. ie 2ab is allowed but not 2ba.
Numbers should always go first. ie 2ab is allowed but ab2 is not.
Exponentiation will be given as a^b to mean a to the power of b.
These rules must be applied to every sub-expression. ie 2ab + ba3 becomes 2ab + 3ab, 2vd * vd5 becomes 2dv * 5dv. This must work for at least addition, subtraction, multiplication, division, modulus and exponentiation.
Exponentiation is assumed to belong to the variable immediately preceding it and must stay with the variable it is assigned to. ie 2ba^2 becomes 2a^2b. This means that all variables to the right of ^ are part of the exponentiation.

Sample Input/Output

Input can be given with any amount of white space, which must be ignored. Output can use either one space or none. For example, 2ab               +3ba could become 2ab + 3ab or 2ab+3ab

Input -> Output
2ba -> 2ab
4gb + 5vh * gh7 -> 4bg + 5hv * 7gh
2ba^2 -> 2a^2b
5xk^2ba -> 5k^2abx

(The last couple of outputs don't make sense mathematically because of order of operations, but you don't have to worry about that.)

Scoring

Standard code golf, shortest answer in bytes wins. Answer can be a program which takes input, or a function (can be anonymous).

Ruby, 112 + 1 (p flag) = 113 bytes
Run as ruby -pe with the code surrounded by single quotes. Full program, even if it looks like just a recursive function at the beginning.
f=->s{s.scan(/(\w)(\^.+)?/).map{|a,b|[a,b&&?^,b&&f[b]]}.sort_by &:first};gsub(/[\w^]+/){f[$&]*""};gsub(/\s+/,"")


Play a Perfect Game of 4x4 Hex Background

Hex is a two-player abstract strategy game played on a K×K rhombus of hexagonal tiles.
Two opposite sides of the rhombus are colored white, and the other two black, and the two players, black and white, take turns in placing a token of their color on an unoccupied tile.
The player who first manages to construct a path between the opposite sides of their color is the winner.
It is known that the game cannot end in a draw, and that the first player has a winning strategy regardless of the board size (see the Wikipedia page for details).

The Task

In this challenge, we fix the board size at K = 4, and represent the board as the following grid.
The thick lines denote adjacent tiles.

Your task is to produce a winning strategy for the first player, which you can choose to be either black or white.
This means that whichever legal moves the opposing player makes, your play must result in a victory.
Your input is a game position (the arrangement of tokens on the board), and your output is a legal move, in the format specified below.
If you want to find a winning strategy yourself, do not read this spoiler:

   Outline of one possible winning strategy, assuming white goes first.

 First select 5. After that, if you have a path from 5 to the bottom row OR black selects 0 or 1 at any point, respond by selecting whichever of 0 or 1 is vacant.

 If black selects 9 or 13, select 10 and then whichever of 14 or 15 is vacant. If black does not select 9, 13 or 14, then select 9 and next whichever of 13 or 14 is vacant.

 If black selects 14, respond by selecting 15. Next, select 10 if it is vacant; if black selects 10, respond with 11. If black then selects 6, respond with 7, and next whichever of 2 or 3 is vacant. If black does not select 6, select it, so you have a path from 5 to the bottom row.

Input and Output

Your input is a string of 16 characters WBE, which stand for white, black and empty.
They represent the tiles of the board, as enumerated above.
You can choose the input method (which also determines your output method) from the following:

Input from STDIN, output to STDOUT.
Input as one command line argument, output to STDOUT.
Input as 16 single-character command line arguments, output to STDOUT.
Input as argument of named function, output as return value.

Your output represents the tile on which you place your next token, as it is your turn to move.
You can choose from the following output formats:

A zero-based index (as used in the above picture).
A one-based index.
The input string with one E replaced by whichever of W or B you chose for your player.

Rules

Your strategy must be deterministic.
You are not required to correctly handle game positions that are unreachable from the empty board using your strategy, or positions that are already winning for either player, and you may crash on them.
Conversely, on boards that are reachable using your strategy, you must return a legal move.

This is code-golf, so the lowest byte count wins.
Standard loopholes are disallowed.

Testing

I have written a Python 3 controller for validating entries, since it would be extremely tedious to do by hand.
You can find it here.
It supports the first three input formats and Python 3 functions (functions in other languages have to be wrapped into programs), all three output formats, and both players.
If a strategy is not winning, it will output a losing game it found, so you can tweak your program.


Another amicable number problem Two numbers are said to be 'amicable' or 'friends' if the sum of the proper divisors of the first is equal to the second, and viceversa.  For example, the proper divisors of 220 are: 1, 2, 4, 5, 10, 11, 20, 22, 44, 55, 110 which sum up to 284.  284's proper divisors are 1, 2, 4, 71 and 142, which sum to 220, thus 220 and 284 are friends. Write a function which returns true if and only if a number is a friend of some other number.

Examples:

friend(220) ==> true

friend(7) ==> false

friend(284) ==> true

Function with least number of chars wins.

NOTE: I just found out that there is a similar question, but I believe this one is simpler and perhaps more general.

Python, 67

a=lambda x:sum(i for i in range(1,x)if x%i<1)
b=lambda x:x==a(a(x))


Implement a FuzzyFinder Inspired by this link I found on Reddit.

A FuzzyFinder is a feature of many text editors. As you start to type a file path S, the FuzzyFinder kicks in and shows you all files in the current directory containing the string you entered, sorted by the position of S in the file.

Your task is to implement a fuzzy finder. It should be program or function that takes (via stdin, function argument, or command line) a string S and a list of strings L, formatted however you wish, and returns or prints the result of running the fuzzy finder. The search should be case-sensitive. Results where S is in the same position in multiple strings may be sorted however you wish.

Example:

Input: mig, [imig, mig, migd, do, Mig]
Output:
    [mig, migd, imig]
OR
    [migd, mig, imig]

This is code golf, so the shortest solution wins.

CJam, 18 15 bytes

{1$#)}q~2$,@$p;

Try it online in the CJam interpreter.

I/O

Input:

"mig" ["imig" "mig" "migd" "do" "Mig"]

Output:

["mig" "migd" "imig"]

How it works

      q~        e# Read and evaluate the input from STDIN.
                e# Pushes a needle and an array of haystacks.
{    }          e# Define a code block:
 1$             e#   Copy the needle.
   #            e#   Compute the index of the needle in the haystack.
    )           e#   Add 1 to the index.
        2$      e# Copy the block.
          ,     e# Filter: Keep only haystacks for which the code block
                e#         pushed a non-zero value.
           @    e# Rotate the block on top of the stack.
            $   e# Sort: Arrange the haystacks according to the values
                e#       pushed by the code block.
             p  e# Print the filtered and sorted haystacks.
              ; e# Discard the needle.


Sample a random non-decreasing sequence Input: Two integers n and k given in any form that is convenient for your code

Output A random non-decreasing sequence of k integers, each in the range 1 to n.   The sample should be chosen uniformly from all non-decreasing sequences of k integers with integers in the range 1 to n.

The output can be in any reasonable format you find convenient.

You can use whatever pseudo-random generator your favorite library/language provides.

We can assume that the integers n,k > 0.

Example

Say n,k = 2. The non-decreasing sequences are

1,1
1,2
2,2

Each sequence should have probability 1/3 of being outputted.

Restriction

Your code should run in no more than a few seconds for k = 20 and n = 100.

What doesn't work

If you just sample each integer randomly from the range 1 to n and then sort the list you won't get a uniform distribution.

Python, 89 bytes

from random import*
lambda n,k:[x-i for i,x in enumerate(sorted(sample(range(1,n+k),k)))]

Generating an increasing sequence rather than a non-decreasing one would be straightforward: this is just a random subset of k numbers between 1 and n, sorted.

But, we can convert an increasing sequence to a non-decreasing one by shrinking each gap between consecutive numbers by 1. So, a gap of 1 becomes a gap of 0, making equal numbers. To do so, decrease the i'th largest value by i

r[0], r[1], ..., r[n-1]  =>  r[0]-0, r[1]-1, ..., r[n-1]-(n-1)

For the result to be from 1 to n, the input must be from 1 to n+k-1. This gives a bijection between non-decreasing sequences of numbers between 1 and n, to increasing sequences between 1 and n+k-1. The same bijection is used in the stars and bars argument for counting such sequences.

The code uses the python function random.sample, which takes k samples without replacement from the input list. Sorting it gives the increasing sequence.


How many squares are there? This challenge is inspired by a picture that often roams on Facebook that looks like this. Except our base square will look more like this:

┌─┬───┬─┐
├─┼─┬─┼─┤
├─┼─┴─┼─┤
├─┼─┬─┼─┤
└─┴─┴─┴─┘

The square is made out of n x m 1x1 square, you have to count how many sub-squares (1x1, 2x2, 3x3, 4x4, 5x5, etc.) can fit within that square. Squares can be missing some grid lines (like in the example above) or be complete like in the example bellow. Which means a mathematical breakdown is not possible (as far as I know).

Inputs:

The amount of lines (n) of input to build the square;
A square made from the following characters: ─ ┐ ┌ └ ┴ ┘ ┬ ├ ┤ ┼ | across n lines of input.

Output:

The amount of squares of any size that can fit within the input square (we only want a single number here, not a number for each size).

Winning criterion:

The smallest answer (number of bytes) wins.

Test Cases:

In:

5
┌─┬─┬─┬─┐
├─┼─┼─┼─┤
├─┼─┼─┼─┤
├─┼─┼─┼─┤
└─┴─┴─┴─┘

Out: 30

In:

3
┌─┬─┐
├─┼─┤
└─┴─┘

Out: 5

In:

5
┌─┬─┐
├─┴─┤
├───┤
├─┬─┤
└─┴─┘

Out: 7

In:

4
┌─┬─┬─┬─┬─┬─┐
├─┼─┼─┼─┼─┼─┤
├─┼─┼─┼─┼─┼─┤
└─┴─┴─┴─┴─┴─┘

Out: 32

In:

2
┌─┐
└─┘

Out: 1

In:

4
┌─┬─┬─┬─┬─┬─┐
├─┴─┼─┼─┼─┴─┤
├─┬─┼─┼─┼─┬─┤
└─┴─┴─┴─┴─┴─┘

Out: 22

JavaScript (ES6), 292 bytes 306 325

Edit I did the byte count totally wrong, corrected now thx http://bytesizematters.com/ correct for the last time I hope thx  Cᴏɴᴏʀ O'Bʀɪᴇɴ see https://goo.gl/LSHC1U (and 1 byte less using a literal newline insteads of '\n')

(h,z)=>(o=>{r=p=>" ),┌(─┐┬'└│├┘┴┤┼".search(z[p]);for(q=s=0;++s<o/2&s<h;)for(y=0;y<(h-s)*o;y+=o)for(x=0;x<o-s*2;q+=!n,x+=2)for(n=i=0,t=x,u=y;i<=s;t+=2,u+=o,i++)n|=i<s&(!(r(t+y)&r(t+y+s*o)&1)|!(r(x+u)&r(x+u+s*2)&2))|i>0&(!(r(t+y)&r(t+y+s*o)&4)|!(r(x+u)&r(x+u+s*2)&8))})(-~z.search`
`)|q

Longer than I expected (probably a few more byte can be shaved off)

All possible squares are checked and counted.

The r function map each character to a bitmap having

1 : horizontal line center to right
2 : vertical line center to bottom
4 : horizontal line center to left
8 : vertical line center to top

A square of any size must have

4 in all cells except the first in top and bottom row
1 in all cells except the last in top and bottom row
8 in all cells except the first in leftmost and rightmost column
2 in all cells except the last in leftmost and rightmost column

Test

f=(h,z)=>(o=>{r=p=>" ),┌(─┐┬'└│├┘┴┤┼".search(z[p]);k=(p,d,m)=>r(p)&r(p+s*d)&m;for(q=s=0;++s<o/2&s<h;)for(y=0;y<(h-s)*o;y+=o)for(x=0;x<o-s*2;q+=!n,x+=2)for(n=i=0,t=x,u=y;i<=s;t+=2,u+=o,i++)n=n|i<s&(!k(t+y,o,1)|!k(x+u,2,2))|i>0&(!k(t+y,o,4)|!k(x+u,2,8));})(-~z.search`
`)|q

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

// Less golfed

Uf=(h,z)=>{
  o=-~z.search`\n`;
  w=o/2;
  r=p=>" ),┌(─┐┬'└│├┘┴┤┼".search(z[p]);
  k=(p,d,m)=>r(p)&r(p+s*d)&m;
  for(q=s=0;++s<w&s<h;)
    for(y=0;y<(h-s)*o;y+=o)
      for(x=0;x<(w-s)*2;q+=!n,x+=2)
        for(n=i=0,t=x,u=y;i<=s;t+=2,u+=o,i++)
          n|=i<s&(!k(t+y,o,1)|!k(x+u,2,2))
          |i>0&(!k(t+y,o,4)|!k(x+u,2,8));
  return q
}

;[[5,`┌─┬───┬─┐
├─┼─┬─┼─┤
├─┼─┴─┼─┤
├─┼─┬─┼─┤
└─┴─┴─┴─┘`,20]
,[5,`┌─┬─┬─┬─┐
├─┼─┼─┼─┤
├─┼─┼─┼─┤
├─┼─┼─┼─┤
└─┴─┴─┴─┘`,30]
,[3,`┌─┬─┐
├─┼─┤
└─┴─┘`,5]
,[5,`┌─┬─┐
├─┴─┤
├───┤
├─┬─┤
└─┴─┘`,7]
,[4,`┌─┬─┬─┬─┬─┬─┐
├─┼─┼─┼─┼─┼─┤
├─┼─┼─┼─┼─┼─┤
└─┴─┴─┴─┴─┴─┘`,32]
,[2,`┌─┐
└─┘`,1]
,[4,`┌─┬─┬─┬─┬─┬─┐
├─┴─┼─┼─┼─┴─┤
├─┬─┼─┼─┼─┬─┤
└─┴─┴─┴─┴─┴─┘`,22],
,[6,`┌─┬─────┐
├─┼─┬─┐ │
│ ├─┼─┼─┤
│ └─┼─┼─┤
│   └─┼─┤
└─────┴─┘`,12],
,[6,`┌─┬─┬─┬─┐
├─┴─┼─┼─┤
│   └─┼─┤
├─┬─┬─┼─┤
├─┼─┼─┼─┤
└─┴─┴─┴─┘`,23]]
.forEach(t=>{
  var r=t[0],a=t[1],k=t[2],x=f(r,a)
  console.log(x==k?'OK '+x:'KO '+x+' Expected '+k,'\n'+a)
})


Generate the Stöhr sequence I am learning Ruby and wrote my first nontrivial code to solve this problem.
The challenge is to generate the first n elements of the Stöhr sequence, S, which is defined as follows:

S[0] = 1
S[n] is the smallest number that cannot be expressed as the sum of two distinct previous elements in the sequence.

Thus the sequence begins with 1, 2, 4, 7, and 10. The next element is 13, because 11 (=1+10) and 12 (=2+10) are sums of previous elements, but 13 is not.
I am looking for the shortest code. My own, in Ruby, is 108 characters long, but maybe I'll wait to see what others come up with before posting it?

APL, 7

In APL you can choose if you want to work with index 0 or index 1.
You do this by setting global variable ⎕IO←0

If we choose to work in index 0 we have:

+\3⌊1⌈⍳

Explanation:

⍳    creates a sequence 0...n   (0 1 2 3 4 5)
1⌈   takes whichever is bigger, number in sequence or 1 (1 1 2 3 4 5)
3⌊   takes whichever is lower, number in sequence or 3 (1 1 2 3 3 3)
+\   partial sums for the sequence (1 2 4 7 10 13)

Try it on tryapl.org


Construct ASCII arches I like ascii art and I get bored a lot, so I found some ascii characters and started to make random things, 8-bit mario castle, mazes, and arches. I found that the arches could easily be stacked in a neat way.

╔═══════╗
║╔═════╗║
║║╔═══╗║║
║║║╔═╗║║║
╨╨╨╨─╨╨╨╨

Challenge

Create a program, function, or any other standard format that accepts an integer that is greater than or equal to 0 (unless you are doing the bonus) and outputs  ascii art with the amount of arches specified.

Test Cases

Input:

7

Output:

╔═════════════╗
║╔═══════════╗║
║║╔═════════╗║║
║║║╔═══════╗║║║
║║║║╔═════╗║║║║
║║║║║╔═══╗║║║║║
║║║║║║╔═╗║║║║║║
╨╨╨╨╨╨╨─╨╨╨╨╨╨╨

Alt:

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

Input:

1

Output:

╔═╗
╨─╨

Alt:

+-+
| |
---

If the integer is 0 then don't output anything
This question will be in utf-8, each character will count as a "byte"
This is codegolf so the shortest answer wins.
You have the option of using +-+ instead of ╔═╗, --- instead of ╨─╨, and | instead of ║

Bonus (not decided whether to allow this on the alternate version because it wouldn't be as hard)

-10% if the program supports negative numbers and flips the arches like so

╥╥╥╥─╥╥╥╥
║║║╚═╝║║║
║║╚═══╝║║
║╚═════╝║
╚═══════╝

Python 2, 106 bytes (94 chars)
n=input();j=1
exec"s=j/2*'║';print s+'╔'+'═'*(2*n-j)+'╗'+s;j+=2;"*n
if n:t='╨'*n;print t+'─'+t

Pretty straightforward. Prints line by line with a changing number of horizontal and vertical bars. The last line is printed separately.
I feel like I'm missing some optimizations. The fact that the chars are multiple bytes means you can't do something like '║╨'[n>0], so I didn't find a good way to print the last line in the loop. It's ugly that there's so much manipulation going on with the counter. I'd like update strings directly, like s+='║', but the index is also used for horizontal bars.


Crazy but Rational Bases We have many challenges based on base 10, base 2, base 36, or even base -10, but what about all the other rational bases?
Task
Given an integer in base 10 and a rational base, return the integer in that base (as an array, string, etc.).
Process
It's difficult to imagine a rational base, so let's visualize it using Exploding Dots:
Consider this animation, expressing 17 in base 3:

Each dot represents a unit, and boxes represent digits: the rightmost box is the one's place, the middle box is the 3^1 place, and the leftmost box is the 3^2 place.
We can begin with 17 dots at the one's place. However, this is base 3, so the ones place has to be less than 3. Therefore, we "explode" 3 dots and create a dot on the box to the left. We repeat this until we end up with a stable position with no explodable dots (i.e. 3 dots in the same box).
So 17 in base 10 is 122 in base 3.

A fractional base is analogous to exploding some number of dots to more than one dots. Base 3/2 would be exploding 3 dots to create 2.
Expressing 17 in base 3/2:

So 17 in base 10 is 21012 in base 3/2.

Negative bases work similarly, but we must keep track of signs (using so-called anti-dots, equal to -1; represented by an open circle).
Expressing 17 in base -3:

Note, there are extra explosions to make the sign of all the boxes the same (ignoring zeros).
Thus, 17 in base 10 is 212 in base -3.
Negative rational bases work similarly, in a combination of the above two cases.
Rules

No standard loopholes.
The sign of each "digit" in the output must be the same (or zero).
The absolute value of all digits must be less than the absolute value of the numerator of the base.
You may assume that the absolute value of the base is greater than 1.
You may assume that a rational base is in its lowest reduced form.
You may take the numerator and the denominator of the base separately in the input.
If a number has multiple representations, you may output any one of them. (e.g. 12 in base 10 can be {-2, -8} and {1, 9, 2} in base -10)

Test cases:
Format: {in, base} -> result
{7, 4/3}        ->  {3, 3}
{-42, -2}       ->  {1, 0, 1, 0, 1, 0}
{-112, -7/3}    ->  {-6, -5, 0, -1, 0}
{1234, 9/2}     ->  {2, 3, 6, 4, 1}
{60043, -37/3}  ->  {-33, -14, -22, -8}

Since some inputs may have multiple representations, I recommend testing the output using this Mathematica snippet on TIO.
This is code-golf, so submissions with shortest byte counts in each language win!

For more information on exploding dots, visit the global math project website! They have a bunch of cool mathy stuff!

Python 2, 42 39 bytes

n,a,b=input()
while n:print n%a;n=n/a*b

Try it online!

Thanks to @xnor for finding the shorter form.

Obsolete version (42 bytes):

f=lambda n,a,b:n and[n%a]+f(n/a*b,a,b)or[]

Try it online!

Parameters: input, numerator (with sign) and denominator.

Returns an array, lowest digit first.

This just works because the division and modulo in Python follows the sign of the denominator, so we don't have to care about same signs explicitly.

Test case output:

f(7, 4, 3)       == [3, 3]
f(-42, -2, 1)    == [0, -1, -1, -1, -1, -1, -1]
f(-112, -7, 3)   == [0, -1, 0, -5, -6]
f(1234, 9, 2)    == [1, 4, 6, 3, 2]
f(60043, -37, 3) == [-8, -22, -14, -33]


Symmetric difference Surprised that we don't have a symmetric difference challenge yet.

Given two lists only containing positive integers, return all items among these two lists that aren't contained in both of the lists.

Rules

From the set definition:

  A set is a collection of definite distinct items.

So you can assume the items in the input lists are always unique.
You can also take input as a set if your language supports it.

Test cases

Here is a sample program that generates the test cases.

[1,2,3],[2,3,4] -> [1,4]

APL (Dyalog Unicode), 3 bytes

∪~∩

Try it online!

How it works

∪~∩  ⍝ Input: two sets as vectors
∪    ⍝ Set union
 ~   ⍝ Set minus
  ∩  ⍝ Set intersection

The rest is just for fun.

APL (Dyalog Unicode), 4 bytes

~∪~⍨

Try it online!

~∪~⍨
~     ⍝ Set difference (a~b)
 ∪    ⍝ Set union
  ~⍨  ⍝ Set difference reversed (b~a)

APL (Dyalog Unicode), 5 bytes

~⍨∪⍨~

Try it online!

This one is palindromic!

How it works

~⍨∪⍨~
~⍨     ⍝ Set difference reversed (b~a)
  ∪⍨   ⍝ Set union reversed
    ~  ⍝ Set difference (a~b)


A Dance of Many Dimensions Challenge
Given a n-dimensional array of integers and a permutation of the first n natural numbers, permute the array dimensions accordingly.
Details
This challenge is inspired by MATLABs permute. demonstration
The permutation is given as a list of integers, e.g. [1,3,2] means 1 gets mapped to 1, 2 gets mapped to 3 and 3 gets mapped to 2 (here the ith entry is the value i gets mapped to). But you can use other formats that are convenient, for instance as cycles or as a function. If it is more convenient you can also use 0-based indexing.
The array can be assumed to be a full "rectangular" m1 x m2 x ... x mn-array (i.e. you can assume it is not ragged/jagged).
You can assume that n is not too large, as many languages have a limit of the number of dimensions in a nested array.
If your language does not support multidimensional arrays, you can also take a string that represents the array as input.
Examples

Any n-dimensional array with the identity permutation [1,2,3,...,n] will be unchanged.
The array [[10,20,30],[40,50,60]] with the permutation [2,1] gets mapped to [[10,40],[20,50],[30,60]].
The array [[[1,2],[3,4]],[[5,6],[7,8]]] with the permutation [2,3,1] gets mapped to [[[1,3],[5,7]],[[2,4],[6,8]]].

Languages with built-in solutions

based on this proposal by xnor

APL (Dyalog Unicode), 1 byte

⍉

Try it online!

J, 2 bytes

|:

Try it online!

R, 5 bytes

aperm

Try it online!

Octave/MATLAB, 8 bytes

@permute

Try it online!

Wolfram Language (Mathematica), 9 bytes

Transpose

Try it online!

Julia, 11 bytes

permutedims

Try it online!


Reconstruct the ASCII art from a string I have a bunch of ASCII art that I have recovered from a failed hard drive. Unfortunately, all of the newlines were stripped out, and I don't know the resolution of the original artwork. I do know that each one was originally rectangular, but to make matters worse, all the white space at the beginning and end was stripped out too!

I do at least know what one small piece of each one looks like. Can you help me recover the artwork based on the input stream of bytes and the piece of ASCII art I remember?

Example

I remember this one:

__(((55^$$%^/\__%%//\/_666332@12

Had this diamond in it:

/\
\/

The original artwork in this case was 8 characters wide:

__(((55^
$$%^/\__
%%//\/_6
66332@12

Then there's this one, which had a bigger diamond in it.

/\/\/\/\/\:;/  \00F\/\/\  /E%epopox\/e

The diamond looked like this:

 /\
/  \
\  /
 \/

The original artwork contained that diamond, but the white space surrounding the diamond was not white space in the original artwork. I’ve only added in the white space to the left to get the indentation right.

More generally, in each row, any space to the left of the first non-white-space character is indentation padding, and any white space to the right necessarily represents actual white space.

Note that this is also one of those pieces that has had its white space trimmed off. Here's the original, 11 characters wide, with white space restored:

   /\/\/\/\
/\:;/  \00F
\/\/\  /E%e
popox\/e

Remember, the amount of white space removed is unknown. That means I can’t even figure out the possibilities for line length by finding the divisors of the input’s character count.

Input

A string of characters (the artwork, sans newlines, trimmed of white space at the beginning and end), and a two-dimensional string of characters (the piece to look for)

Essentially, the string of characters can be generated from the original artwork thus: artwork.Replace("\n", "").Trim(" ")

Output

The original artwork with newlines inserted where necessary, and with trimmed white space re-added to the beginning of the first line and the end of the last line. If there is more than one possible solution, you may return one arbitrarily (or all of them if you really want to).

Test Cases

Input:
__(((55^$$%^/\__%%//\/_666332@12
/\
\/

Output:
__(((55^
$$%^/\__
%%//\/_6
66332@12

-----------
Input:
 _-/\-_-_vv:;/  \00F\\||\  /E%epopox\/e0
 /\
/  \
\  /
 \/

Output:
   _-/\-_-_
vv:;/  \00F
\\||\  /E%e
popox\/e0

--------
Input:
__               (  )               ||                ||            ___|""|__.._     /____________\    \____________/~~~.
(  )
 ||
 ||
 ""

Output:
     __
    (  )
     ||
     ||
 ___|""|__.._
/____________\
\____________/~~~.

--------
Input:
..XX...XX.......X..X..X  X.....X..X...X  X.....XX......XX...
 XX
X  X
X  X
 XX

Output:
..XX...XX.......
X..X..X  X.....X
..X...X  X.....X
X......XX...

Notably, in this last case, the following is not valid output:

..XX...XX......
.X..X..X  X....
.X..X...X  X...
..XX......XX...

Credit to jrei @ asciiart.eu for the joystick

Rules

This is code golf, so shortest answer in bytes wins.
Default I/O rules apply


Arranging arbitrary rectangles to fill a space Can these rectangles fill a rectangular space?

Given a bunch of rectangles, you are asked whether or not they can be arranged to fill a rectangular space.

Specs

Given a bunch of arbitrary m x n rectangles; 0 <= m, n <= 1000, determine whether or not it is possible to arrange them so that they cover exactly a rectangular area without any holes or overlaps. The rectangles cannot be rotated, and each rectangle may only be placed once.

Input

The input for this is very flexible, as long as the input gives some sort of list of 2-space dimensions. For example, both of the following are valid:

Separated by Space, Return

1 2
1 5
4 5
3 6

List of Dimensions

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

Output

Any sort of true/false values like true/false, 0/1, T/F, True/False, etc. If you are going to use an output method that's not very obvious, please specify in your answer.

Examples

Test Case 1

Input:

1 1
1 5
2 6

Output:
true (or something similar)
How to arrange it:

XYYYYY
ZZZZZZ
ZZZZZZ

Test Case 2

Input:

1 1
2 2

Output:
false (or something similar)
Explanation: It becomes obvious that you cannot arrange two squares of different sizes and get their edges to line up.

Test Case 3

Input:

1 1
1 2
1 2
2 1
2 1

Output:
true (or something similar)
How to arrange it:

AAB
DEB
DCC

As @ETHProductions pointed out, for all of the other test cases, you can keep combining rectangles with a common edge length until you have only one rectangle, so this test case is just to break any code that uses this idea.

Test Case 4

Input:

3 2
4 1
2 1
4 1
2 1
5 2
3 2
1 4
3 2
2 1
2 1
1 1
5 1

Output:
true (or something similar)
How to arrange it:

AAABBBBEE
AAACCDDDD
FFFFFGGGH
FFFFFGGGH
IIIJJKKLH
IIIMMMMMH

Note: You do not need to state how to arrange it, you only need to determine whether not it can be arranged.

This is code golf, so the shortest answer in bytes wins! I will accept the shortest answer as of January 14th, but feel free to submit answers later than that since I can still give upvotes! :)

Happy golfing!

~ A.L.

P.S. If you know what tag should be applied to this problem, please add it, I have absolutely no idea what to put as a tag other than code-golf.

EDIT: Your program should be able to process up to 25 rectangles, in at most 10 seconds on a decent computer (I'll be quite flexible on this rule).

EDIT: I've extended the submission acceptance deadline to the last day of the year, but I doubt I'll get an answer by then...

EDIT: I've extended the submission acceptance deadline by 2 weeks, so if no more answers come in by then, the current C answer will be accepted! :)

Haskell, 226 bytes

((y,z):l)&(w,x)|x*y<1=(w+y,x+z):l
(q:l)&p=p:q:l
(p@(u,v):r@(y,z):l)%q@(w,x)=[((y-w,z):l)&q&(u,v-x)|w<=y,x<=v]++[p:m|m<-(r:l)%q]
_%_=[]
g m(p:n)l=any(g[]$m++n)(l%p)||g(p:m)n l
g[]_[_,_,_]=0<1
g _[]_=0<0
($[(0,9^9),(9^9,0)]).g[]

Try it on Ideone

How it works

This recursively searches for all partial tilings whose shape is a Young diagram, adding one rectangle at a time, and checks whether any of the final results are rectangles.

To see that any tiling of a rectangle can be built this way: in any tiling of a nonempty Young diagram, let R be the set of rectangles in the tiling whose southwest corner does not touch any other rectangle.  Since each concave vertex of the Young diagram is edge-adjacent (not merely corner-adjacent) to at most one rectangle in R, and the number of these concave vertices is one less than the number of rectangles in R, there must be at least one rectangle in R that is edge-adjacent to none of these concave vertices.  Removing it yields another Young diagram, so we can proceed by induction.


Which is better - Emacs or Vim? (Google fight) Greetings, noble code golfers. Today you will resolve the most ancient and distinguished of debates - Emacs or Vim?

Your challenge is to take two search terms as input, and output which of those terms has the most Google search results. (This is obviously completely fair. What do you mean, biased?)

Here are some example inputs and outputs:

Input: emacs and vim
Output: vim (totally not creating any flamewars in the comments)

Input: google and microsoft
Output: google

Input: code golf stack exchange and code review stack exchange
Output: code golf stack exchange (yeah!)

And here are some edge cases just for fun (and for testing your solutions):

Input: About 1,000,000 results and About 100,000 results
Output: About 100,000 results

Input: This will autocotrect and Another testcase
Output: Another testcase (if you don't consider autocorrecting, then the first one will win)

For the following test cases, you must remove the # signs in the search terms first, since they rely on the term having a specific amount of results and posting the term here would ruin that.

Input: Thissear#chter#mhasno#results and Another testcase
Output: Another testcase (just a test for zero results)

Input: "These exact wo#rds do#n't exi#st# on the Internet" and Another testcase
Output: Another testcase (testing "s)

Input: Abo#ut 1,65#2,85#3,2#86 re#sults and Another testcase
Output: Another testcase (this one is tricky - the above search term has one result)

Input: "Abo#ut 4#8,234,8#75,14#7 res#ults" and Another testcase
Output: Another testcase (also tricky - no results, so it displays the search term)

You don't need to handle the corner-case of "quoted" searches returning "No results, showing results without quotes instead" because that would just be too complicated. You don't need to handle inputs with the same number of results either.

This is code-golf, so the shortest code in bytes will win!

Ruby, 203 180 bytes

->*s{s.map{|x|[(open("http://www.google.com/search?nord=1&q=#{URI.escape x}&nfpr=1").read.match(/s">(About )?([\d,]+) result/)||[?0])[-1].split(?,).join.to_i,x]}.max[1]}

+11 bytes for the -ropen-uri flag (plus space).

Input is taken as two arguments.

URL explanation:

?nord=1: prevent auto-redirect from HTTP to HTTPS
&q=#{URI.escape x}: escape the query so "s work
&nfpr=1: no autocorrect

The whole map turns ['emacs','vim'] into [[2150000, 'emacs'], [14900000, 'vim']]. (You can see this by changing the .max[1] at the end to .inspect.) Then, the max is taken, which will grab the one with the most results, and [1] is used to get the search term.


Write a "Look-and-Say Numbers" generator There is a sequence of numbers called the "Look-and-Say Numbers".

Here is an example of the first 5 terms of the sequence, starting at 1 (with spaces added between the digits):

     1
    1 1
    2 1
  1 2 1 1
1 1 1 2 2 1

The pattern is simple, once you see it.

The sequence starts with 1. There is one 1, so the next number is 11 (as in one of the number 1).

In this number, there are 2 1s, so the next number is 21.

In this number there is 1 2, and 1 1, so the next number is 1211.

In this number there is 1 1, followed by 1 2, followed 2 1s - so the number is 111221.

The Task

You must write a program that generates the first n terms of this sequence, where n is given by stdin. The sequence will start at 1.

This is a code-golf task, so shortest code wins.

Mathematica, 68 bytes

There's no STDIN in Mathematica, so here is a function instead

s=FromDigits/@NestList[Flatten[Reverse@@@Tally/@Split[#]]&,{1},#-1]&

Usage:

s[5]

> {1, 11, 21, 1211, 111221}


Enthusiastically Russianify a String Many of you may have interacted with people from Russia on the internet at some point, and a subset of you may have noticed the slightly odd method they have of expressing themselves.

e.g. удали игру нуб)))

where the ))) are added for emphasis on the previous statement, I have been working on a theory that the ratio of )'s to the rest of the string is directly proportional to the amount of implied emphasis, however I oftentimes find it difficult to compute the ratio on the fly, as I am also trying to cope with a slew of abuse, so I would like the shortest possible code to help me calculate what the resulting string should be, for a value of enthusiasm between 0 and 500%, given the original, unenthusiastic string, this will aid my research greatly as I will not have to type out bulky scripts every time I wish to test my hypothesis.

So, the challenge:

write a full program or function, which, provided two arguments, a string of unknown length, and a number, in either integer format (between 0 and 500) or in decimal format (between 0 and 5, with 2 points of accuracy) will

return/display the original string, suffixed with a number of )'s
the number will be the calculated as a ratio of the input number to the string length.
so if the number 200, or 2.00 was provided, 200% of the string must be suffixed as )'s
the number of brackets rounded to in decimal situations does not matter.
script is required to support Printable ASCII characters.
only has to support one input number format, of your choice.

Examples:

"codegolf" 125      = codegolf))))))))))
"codegolf" 75       = codegolf))))))
"noob team omg" 0.5 = noob team omg))))))
"hi!" 4.99          = hi!)))))))))))))))

Example code (PowerShell) (with decimal input):

Function Get-RussianString ([string]$InputStr,[decimal]$Ratio){
    $StrLen = $InputStr.Length
    $SuffixCount = $StrLen * $Ratio
    $Suffix = [string]::New(")",$SuffixCount)
    return $InputStr + $Suffix
}

Get-RussianString "codegolf" 0.5
codegolf))))

This is code-golf so shortest code wins!


Divisor sum from prime-power factorisation The task is to compute the divisor sum of a number given its prime factorisation.

Input

Two arrays (or something equivalent) of length n, one containing the prime factor and the other containing the corresponding exponent.

Output

The sum of all divisors (including the number itself).

Example

The number 240 has 2, 3, and 5 as prime factors with 4, 1, and 1 as the respective exponents. The expected output would then be 744.

Input: [2,3,5] [4,1,1]
Output: 744

Scoring

Shortest code in bytes wins!

If your solution's run time complexity is O(sum of exponents) rather than O(product of exponents), your score may be multiplied by 0.8.

There was a similar question posted here, but it wasn't a challenge. I think the problem is interesting enought to be golfed.

The winner will be choosen this weekend

CJam, 15 bytes * 0.8 = 12

q~.{_@)#(\(/}:*

Try it online. The input order is exponent list first, then list of primes (-3 bytes thanks to @Dennis).

For each prime-exponent pair (p, e) find

(p^(e+1) - 1)/(p - 1)

then find the product of all of these. E.g. for 240 this would be

(1 + 2 + 4 + 8 + 16)(1 + 3)(1 + 5) = 31 * 4 * 6 = 744

Depending on how exponentiation is implemented, this can be better than O(sum of exponents).


Code 39 Barcode Scanner Code 39, developed in 1974, is one of the most commonly used symbologies, or types, of barcodes, although it is the UPC/EAN system that is most often seen in retail sales. Code 39 barcodes can encode uppercase letters, numbers, and some symbols and are trivial to print from computer software using a special font. This led to their widespread commercial and industrial use (e.g. company ID badges, asset tracking, factory automation).

Create the shortest program or function to read a Code 39 barcode in any orientation from a 512x512 pixel grayscale image; the barcode might not be aligned horizontally or vertically.

Your program must accept a standard image file format and produce the data encoded in the barcode as its standard output or return value (not including any start/stop character).
No image contains more than one valid Code 39 barcode, and no barcode encodes a space character (ASCII 32).
If no valid Code 39 barcode is shown in the image, the program must output a single question mark (?).

I have prepared a JavaScript reference implementation and test suite of images in PNG format, both with valid barcodes and without. The reference implementation, which fails only 3 of 46 test cases in most recent Web browsers, is intended to show one possible decoding algorithm, not to strictly conform to the above specification.

A valid submission passes at least 80% of these tests (37/46) and takes no more than one minute to do so for each image on a reasonably fast CPU (e.g. 2.6 GHz quad-core). My reference implementation passes 93% of tests and processes each image within 10 seconds (on my desktop PC running Google Chrome).

(This question was proposed on Meta on May 28, 2011.)

Python, 899 chars

import sys,random
raw_input()
X,Y=map(int,raw_input().split())
input()
I=[' x'[v<'~']for v in sys.stdin.read()]
M={196:' ',168:'$',148:'*',388:'.',52:'0',97:'2',49:'4',112:'6',292:'8',73:'B',25:'D',88:'F',268:'H',28:'J',67:'L',19:'N',82:'P',262:'R',22:'T',193:'V',145:'X',208:\
'Z',42:'%',138:'+',133:'-',162:'/',289:'1',352:'3',304:'5',37:'7',100:'9',265:'A',328:'C',280:'E',13:'G',76:'I',259:'K',322:'M',274:'O',7:'Q',70:'S',385:'U',448:'W'\
,400:'Y'}
N=500
for w in' '*30000:
 a,b,c,d=eval('random.random(),'*4);A=''.join(I[int((a+(c-a)*i/N)*X)+X*int((b+(d-b)*i/N)*Y)]for i in range(N)).lstrip();T=A.count(' x')+1;K=A.count('x')/T;L=A.count\
(' ')/T;s='';z=c=0
 while A:
  z*=2;y=A.find(' ')
  if y<0:y=len(A)
  z+=y>K;A=A[y:]
  z*=2;y=A.find('x')
  if y<0:y=len(A)
  z+=y>L;A=A[y:];c+=2
  if c>9:
   if z/2in M:s+=M[z/2];z=c=0
   else:break
 if s and'*'==s[0]and'*'==s[-1]and'*'!=s:print s[1:-1];break

This code takes a pnm format image as input, so I normally run it like:

pngtopnm s01.png | ./barcode.py

The code itself just picks lots of random scanlines and tries to match the black and white runs on that scanline to the code39 patterns.  It is randomized so it can fail to find barcodes on occasion.  (I get about a 20% false negative failure rate on the test images.)  When it fails it takes about a minute to run, when it succeeds it often does so much quicker than that.  I've never seen a false positive.


I want my book to be away from this table Story

So I have a book that I want to separate from my table with nothing but other books. I want to know how many books do I need to achieve this with \$n\$ book lengths.

Here's a visualization that my friend at Wolfram drew for me:

More information about the topic in Wolfram and Wikipedia.

Challenge

Given an integer input \$n\$, output how many books needed for the top book to be \$n\$ book length away from the table horizontally.
or
Find the smallest integer value of \$m\$ for input \$n\$ in the following inequality.
$$\sum_{i=1}^{m}\frac{1}{2i} \geq n$$

Edit: for fractions use at least a IEEE single-precision floating point. sorry for editing challenge after posting

(OEIS A014537)

Test cases

 1          4
 2         31
 3        227
 5      12367
10  272400600

Octave, 41 40 33 bytes
1 byte saved thanks to @Dennis

@(n)find(cumsum(.5./(1:9^n))>n,1)

Try it online!
Explanation
This uses the fact that harmonic numbers can be lower-bounded by a logarithmic function.
Also, the >= comparison can be replaced by > because harmonic numbers cannot be even integers (thanks, @Dennis!).
@(n)                                   % Anonymous function of n
                     1:9^n             % Range [1 2 ... 9^n]
                .5./(     )            % Divide .5 by each entry
         cumsum(           )           % Cumulative sum
                            >n         % Is each entry greater than n?
    find(                     ,1)      % Index of first true entry


Test if given number is a Reverse Keith? Slighty inspired by my previous challenge regarding Keith Numbers I want to propose a challenge to create a function that takes an integer and gives back a true or false depending on the number is a Reverse Keith number or not.
A reverse Keith uses the same little algorithm as Keith numbers, but ends up with it's starting number in reverse.
For example 12 is a Reverse Keith number

12
1 + 2 = 3
2 + 3 = 5
3 + 5 = 8
5 + 8 = 13
8 + 13 = 21

APL (28)

⍙∊{1↓⍵,+/⍵}⍣{⊃⍺≥⍙∘←⍎⌽∆}⍎¨∆←⍞

Using more or less the same method as TwiNight did in the other question but reversing the number.

Explanation:

∆←⍞: read a line as text, store in ∆
⍎¨: evaluate each character
{1↓⍵,+/⍵}: add the sum of the list to the end of the list, and drop the first item,
⍣: until
{⊃⍺≥⍙∘←⍎⌽∆}: the first item on the list is greater or equal to ⍙, which is the evaluation (⍎) of the reverse (⌽) of ∆.
⍙∊: see if ⍙ is contained in the final list.


You call this optimized? The task is simple, post 2 code snippets that perform the same task, where one seems very optimized at first glance, but actually is significantly slower than the other.

Only one rule:

Both snippets must finish with the exact same output (for the same given input, if any).

Python 3

Seems fast...

 print(0 < 10**100 - 1 < 10**100)

Seems slow...

 print(10**100 - 1 in range(0, 10**100))

But the two run in very similar times! range has an efficient implementation of in


Resize rasterized text and make it look non-pixellated This is a screenshot of some text typed in a text editor:

This is the same text at a larger size.

Notice how visible the aliasing is on letters with prominent diagonal strokes like x and z.  This issue is a major reason why raster fonts have lost popularity to “scalable” formats like TrueType.

But maybe this isn't an inherent problem with raster fonts, just with the way scaling of them is typically implemented.  Here's an alternative rendering using simple bilinear interpolation combined with thresholding.

This is smoother, but not ideal.  Diagonal strokes are still bumpy, and curved letters like c and o are still polygons.  This is especially noticeable at large sizes.

So is there a better way?

The task

Write a program that takes three command-line arguments.

resize INPUT_FILE OUTPUT_FILE SCALE_FACTOR

where

INPUT_FILE is the name of the input file, which is assumed to be an image file containing black text on a white background. You may use any mainstream raster image format (PNG, BMP, etc.) that's convenient.
OUTPUT_FILE is the name of the output file.  It can be either a raster or vector image format.  You may introduce color if you're doing some ClearType-like subpixel rendering.
SCALE_FACTOR is a positive floating-point value that indicates how much the image may be resized.  Given an x × y px input file and scaling factor s, the output will have a size of sx × sy px (rounded to integers).

You may use a third-pary open-source image processing library.

In addition to your code, include sample outputs of your program at scale factors of 1.333, 1.5, 2, 3, and 4 using my first image as input.  You may also try it with other fonts, including proportionally-spaced ones.

Scoring

This is a popularity contest.  The entry with the greatest number of upvotes minus downvotes wins.  In case of an exact tie, the earlier entry wins.

Edit: Deadline extended due to lack of entries.  TBA.

Voters are encouraged to judge based primarily on how good the output images look, and secondarily on the simplicity/elegance of the algorithm.

Ruby, with RMagick

The algorithm is very simple—find patterns of pixels that look like this:

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

and add triangles to make them look like this:

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

Code:

#!/usr/bin/ruby

require 'rmagick'
require 'rvg/rvg'
include Magick

img = Image.read(ARGV[0] || 'img.png').first
pixels = []
img.each_pixel{|px, x, y|
    if px.red == 0 && px.green == 0 && px.blue == 0
        pixels.push [x, y]
    end
}

scale = ARGV[2].to_f || 5.0
rvg = RVG.new((img.columns * scale).to_i, (img.rows * scale).to_i)
    .viewbox(0, 0, img.columns, img.rows) {|cnv|
    # draw all regular pixels
    pixels.each do |p|
        cnv.rect(1, 1, p[0], p[1])
    end
    # now collect all 2x2 rectangles of pixels
    getpx = ->x, y { !!pixels.find{|p| p[0] == x && p[1] == y } }
    rects = [*0..img.columns].product([*0..img.rows]).map{|x, y|
        [[x, y], [
            [getpx[x, y  ], getpx[x+1, y  ]],
            [getpx[x, y+1], getpx[x+1, y+1]]
        ]]
    }
    # WARNING: ugly code repetition ahead
    # (TODO: ... fix that)
    # find this pattern:
    # ?X
    # XO
    # where X = black pixel, O = white pixel, ? = anything
    rects.select{|r| r[1][0][1] && r[1][1][0] && !r[1][2][1] }
        .each do |r|
            x, y = r[0]
            cnv.polygon x+1,y+1, x+2,y+1, x+1,y+2
        end
    # OX
    # X?
    rects.select{|r| r[1][0][1] && r[1][3][0] && !r[1][0][0] }
        .each do |r|
            x, y = r[0]
            cnv.polygon x+1,y+1, x+0,y+1, x+1,y+0
        end
    # X?
    # OX
    rects.select{|r| r[1][0][0] && r[1][4][1] && !r[1][5][0] }
        .each do |r|
            x, y = r[0]
            cnv.polygon x+1,y+1, x+0,y+1, x+1,y+2
        end
    # XO
    # ?X
    rects.select{|r| r[1][0][0] && r[1][6][1] && !r[1][0][1] }
        .each do |r|
            x, y = r[0]
            cnv.polygon x+1,y+1, x+2,y+1, x+1,y+0
        end
}
rvg.draw.write(ARGV[1] || 'out.png')

Outputs (click any to view image by itself):

1.333

1.5

2

3

4