Appends or Prepends? Depends Brain-flak turns one year old tomorrow! In honor of it's birthday, we're having a PPCG style birthday party, where several users post brain-flak related questions! Help us celebrate! :)

Brain-flak is an esoteric language I wrote where all of the commands are brackets and all of the brackets must be fully matched. To borrow my own definition:

For the purpose of this challenge, a "bracket" is any of these characters: ()[]{}<>.

A pair of brackets is considered "matched" if the opening and closing brackets are in the right order and have no characters inside of them, such as
()
[]{}

Or if every subelement inside of it is also matched.
[()()()()]
{<[]>}
(()())

Subelements can also be nested several layers deep.
[(){<><>[()]}<>()]
<[{((()))}]>

A string is considered "Fully matched" if and only if:

Every single character is a bracket,

Each pair of brackets has the correct opening and closing bracket and in the right order

In celebration of brain-flak's first birthday, today's challenge is about taking an unbalanced set of brackets, and determining what types of operations are needed to make it valid brain-flak.

For example, (( is not valid brain-flak code, but if we append )) to it, it becomes (()), which is fully balanced, and therefore valid brain-flak. That makes this input appendable.

Similarly, >} is not valid, but we can prepend {< to it to make {<>}, which is valid. That makes this input prependable.

Some inputs are slightly more complicated. For example, )][({ cannot be made valid purely by appending or prepending. But it can be made valid by prepending [( and appending })]. Therefore, this input is both prependable and appendable.

Lastly, some inputs can never be made valid brain-flak code by any combination of appending or prepending. For example, (> can never be made valid. (Prepending < creates <(>, and appending ) creates (>), neither of which are valid) Therefore, this input is neither appendable or prependable.

For today's challenge, you must write a program or function that takes a string of brackets and determines if the string is
appendable
prependable
both
neither

You may pick what values you use to represent for each case. For example, outputting 1, 2, 3, 4, or 'a', 'p', 'b', 'n', or 1, 'foo', 3.1415, -17, or whatever is fine. As long as each output is distinct and consistent, that's fine. You must however, clearly specify which output corresponds to which case.
You may return this value in whichever format is most convenient (for example, returning from a function, printing to STDOUT, modifying arguments, writing to a file, etc.).
You can assume that the input will never be valid brain-flak or empty.
Examples
The following inputs are all prependable:
))
(((()()())))}
)>}]
()[]{}<>)

These are all appendable:
(({}{})
((((
([]()())(
{<<{

These are all both:
))((
>()[(()){
>{

And these are all neither:
)(}
{(((()()()))>
[}
((((((((((>
((((((((((<>()]

As usual, this is code-golf, so standard loopholes apply, and the shortest answer in bytes wins!

This challenge is particularly difficult in brain-flak, so maximum brownie points to any and every answer written in brain-flak. :)

Jelly, 33 32 37 35 34 bytes

bug found, horrible fix +5 bytes, better fix - 2 bytes, using a trick of Adnan's I saw here for -1 more.

“({[<“)}]>”Z;@WœṣF¥/µÐLO‘&2µIṀ>0ȯQ

Return values:

prepends [2]
 appends [0]
    both [2,0]
 neither 1

(Invalid input returns spurious results, although valid Brain-flack, returns [].)

Try it online! - a test suite (prints mushed representations, so 20 for [2,0], and ignores lines containing any -).


Am I a Cullen Number? A Cullen Number is any number that is contained in the sequence generated using the formula:

C(n) = (n*2^n)+1.

Your Task:

Write a program or function that receives an input and outputs a truthy/falsy value based on whether the input is a Cullen Number.

Input:

A non-negative integer between 0 and 10^9 (inclusive).

Output:

A truthy/falsy value that indicates whether the input is a Cullen Number.

Test Cases:

Input:    Output:
1   --->  truthy
3   --->  truthy
5   --->  falsy
9   --->  truthy
12  --->  falsy
25  --->  truthy

Scoring:

This is code-golf, so the lowest score in bytes wins.

x86_64 machine code (System V ABI), 28 27 bytes

-1 byte thanks to @Cody Gray, thanks!

A constant-time algorithm!

_cullen:
   0:   0f bd cf    bsrl    %edi, %ecx
   3:   0f bd c1    bsrl    %ecx, %eax
   6:   89 ca       movl    %ecx, %edx
   8:   29 c2       subl    %eax, %edx
   a:   0f bd c2    bsrl    %edx, %eax
   d:   29 c1       subl    %eax, %ecx
   f:   d3 e1       shll    %cl, %ecx
  11:   ff c1       incl    %ecx
  13:   31 c0       xorl    %eax, %eax
  15:   39 f9       cmpl    %edi, %ecx
  17:   0f 94 c0    sete    %al
  1a:   c3          retq

Explanation:

Let y an integer and x=y*2^y + 1.
Taking logs, we have y + log2(y) = log2(x-1), thus y=log2(x-1)-log2(y). Plugging back the value of y, we get y=log2(x-1)-log2(log2(x-1)-log2(y)). Doing this one more time, we obtain: y=log2(x-1)-log2[log2(x-1)-log2(log2(x-1)-log2(log2(x-1)-log2(y)))].

Let us remove the last terms (of the order of log2(log2(log2(log2(x)))), this should be safe!), and assume that x-1≈x, we obtain:
y≈log2(x)-log2[log2(x)-log2(log2(x))]

Now, letting f(n) = floor(log2(n)), it can be verified manually that y can be exactly retrieved by:
y=f(x)-f[f(x)-f(f(x))],
for y < 26, and thus x ⩽ 10^9, as specified by the challenge(1).

The algorithm then simply consists of computing y given x, and verify that x == y*2^y + 1.
The trick is that f(n) can simply be implemented as the bsr instruction (bit-scan reverse), which returns the index of the first 1-bit in n, and y*2^y as y << y.

Detailed code:

_cullen:                                 ; int cullen(int x) {
   0:   0f bd cf    bsrl    %edi, %ecx   ;  int fx = f(x);
   3:   0f bd c1    bsrl    %ecx, %eax   ;  int ffx = f(f(x));
   6:   89 ca       movl    %ecx, %edx
   8:   29 c2       subl    %eax, %edx   ;  int a = fx - ffx;
   a:   0f bd c2    bsrl    %edx, %eax   ;  int ffxffx = f(a);
   d:   29 c1       subl    %eax, %ecx   ;  int y = fx - ffxffx;
   f:   d3 e1       shll    %cl, %ecx    ;  int x_ = y<<y;
  11:   ff c1       incl    %ecx         ;  x_++;
  13:   31 c0       xorl    %eax, %eax
  15:   39 f9       cmpl    %edi, %ecx
  17:   0f 94 c0    sete    %al
  1a:   c3          retq                 ;  return (x_ == x);
                                         ; }

(1)In fact, this equality seems to hold for values of y up to 50000.


Finding duplicate balls in a basket? A basket is full with \$n\$ colored balls. For each color except one, there are at least 2 balls with that color. Find the color which only has one ball. in \$O(n)\$ space complexity.
What if each ball is repeated exactly  twice?
You can consider the input to be an array or a list or any container of colors as strings with a maximum length of 100
This is code-golf so the shortest code in bytes wins.

Python - 17 chars

Solely as an expression:

min(B,key=B.count)

Full, standalone program with input and output, 34 chars:

B=input()
print min(B,key=B.count)

edit: What gnibbler said.


Correct using a Parity Block For more information on Parity: Wikipedia

Challenge

Write a program that takes an input (stdin, argv, ect) of four nibbles and two parity nibbles. Your program should then test to see whether the 'block' is valid, using even parity; if it is then output 1. Then try to make any corrections, if correction is possible output the corrected block. If you cannot correct the block output -1. You can assume the parity nibbles are never corrupt.

To re-cap and clarify:

If the input is valid output 1.
If the input is invalid and fixable output the fixed block.
If the input is invalid and cannot be fixed output -1.
You can only edit bits if their respective row and column in the parity bit is incorrect.

Input Format:

<NIBBLE> <NIBBLE> <NIBBLE> <NIBBLE> <PARITY-Y> <PARITY-X>

So 1010 0111 1101 1011 1011 0111 Would look like:

Winning

This is code-golf: Smallest program wins.

Input and Output Examples

Input 1010 0111 1101 1011 1011 0111
Output 1
The Input is Valid

Input 1010 0011 1101 1011 1011 0111
Output 1010 0111 1101 1011
The Input was Invalid, but correctable

Input 1010 0001 1101 1011 1011 0111
Output -1
The Input was Invalid, and not correctable

Python 2, 387

I feel it's kinda long though.
Do suggest improvements or any fixes...

i=raw_input()
z="""#h(a?(a&1)^h(a/2)~a@0
#y(i,m,l,c=0?h(i&m)|y(i>>l,m,l,c+1)*2~c<4@0
#p(i?y(i,4369,1)*16+y(i,15,4)
k=i.replace(" ","")
m=int(k[:16],2)
c=int(k[-8:],2)
#s(i?s(i>>4)+" "+bin(i&15^16)[3:]~i@""
#q(j=16):d=m^1<<j;!s(d)[1:]~p(d)==c@q(j-1)~j@-1
#f(?1~p(m)==c@q()"""
for k,l in("?","):!"),("!","return "),("@"," else "),("#","def "),("~","if "):z=z.replace(k,l)
exec z
print f()

Slightly ungolfed...

def y(i,m,l,c=0):
    h=lambda a:(a&1)^h(a/2)if a else 0 # Calculate how many set bits in i
    return h(i&m)|y(i>>l,m,l,c+1)*2if c<4 else 0 # Sets the parity bits accordingly recursively

p=lambda i:y(i,4369,1)*16+y(i,15,4) # Returns the y and x parity together

i="1010 0111 1101 1011 1011 0111"

k=i.replace(" ","") # Remove all spaces
m=int(k[:16],2)     # Extracts the matrix
c=int(k[-8:],2)     # Extracts the parities

s=lambda i:s(i>>4)+" "+bin(i&15^16)[3:]if i else""
# Converts from int to space separated hexas in binary

def f(i):
    if p(m)==c:return 1 # If calculated parities matches the test
    for i in range(16): # Else, for each of the 16 bits in the matrix
        d=m^1<<i        # xor it
        if p(d)==c:return s(d)[1:] # return the matrix if its parities matches the test
    return -1 # If all else fails, return -1

print f(i)


Magnetic Sculptures... in Space! Background

This is a continuation of my earlier challenge, where the task was to compute the shape of a sculpture obtained by dropping magnets into a huge pile.

Good news: the eccentric artist liked your work, and has another project for you. He still works with magnetic sculptures, but has decided to expand his art studio -- into space! His current method is to blast a single cube-shaped magnet into the orbit, and shoot other magnets at it to create a huge magnetic satellite.

Input

Your input is a finite list of 0s and 1s, given either in the native list format of your language, or a string. It is interpreted as a "blueprint" of a work of art, and is processed in order from left to right as follows.

You start with a single magnet floating at some integer coordinate of the 2D plane, and keep adding more magnets as per the directives. The directive 0 rotates the entire sculpture 90 degrees in the counter-clockwise direction. In the case of the directive 1, the artist finds the leftmost column of the sculpture, and shoots a new magnet to it from below. The new magnet sticks to the bottom-most existing magnet in the column, and becomes a part of the sculpture. Note that the magnet does not stick to other magnets in the neighboring column, unlike in the earlier challenge; its speed is now astronomical!

Output

The artist wants to know whether the complete sculpture will fit into his garage (how he'll get it down from the orbit remains unclear). Thus, your output is the width and height of the sculpture, ordered from lower to higher. They can be given as a two-element list, a pair, or as a string separated by a comma.

Example

Consider the input sequence

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

To process it, we start with one magnet floating in space:

#

The first directive is 1, so we shoot a new magnet from below:

#
#

The next directive is 0, so we rotate the sculpture:

##

The next two directives are 1,1, which means we'll shoot two magnets to the leftmost column:

##
#
#

Then, we rotate again and shoot once, as directed by 0,1:

#
###
#

Finally, we rotate twice and shoot twice:

  #
###
# #
#

The resulting sculpture has width 3 and height 4, so we output [3,4].

Rules

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

Test Cases

[1,0,1] -> [2,2]
[1,0,1,1,0,1,0,0,1,1] -> [3,4]
[1,1,0,1,1,0,1,0,1,1] -> [4,5]
[1,1,0,1,1,0,1,0,1,1,0] -> [4,5]
[1,0,1,0,0,0,1,1,0,0,0,1,1,0,0,0,1,1] -> [3,3]
[0,1,0,1,1,1,1,0,0,1,0,1,0,0,1,1,0,1,0,1,0,0,1,1,0,1,0,0,0,0,1,0,1,0,1,1,0,0,1,1] -> [5,7]
[1,0,1,1,1,1,0,1,0,0,0,0,1,1,1,0,1,1,0,1,0,1,0,0,0,0,0,0,1,1,0,1,0,1,1,1,1,0,1,1,0,0,1,1,1,1,0,0,0,0,1,1,0,0,1,1,0,1,0,0,1,1,0,1,1,0,0,1,0,1,0,0,1,0,1,1,1,0,1,1,0,0,1,0,1,1,0,0,0,1,0,1,1,0,0,1,0,1,1,0] -> [11,12]

Pyth: 34 33 bytes

Sml{dCuS?+G,hhGtehGHm,_ekhkGQ],ZZ

Input is a list of ones and zeros, like in the question. Try it online: Pyth Compiler/Executor

Explanation:

It's a one-on-one translation of the following Python 2 code (126 bytes).

print sorted(map(len,map(set,zip(*reduce(lambda s,i:([[-b,a]for a,b in s],s+[[min(s)[0],min(s)[1]-1]])[i],input(),[[0,0]])))))

I create a list of coordinates of the single magnets. This is initialized with the magnet [0,0]. Then for each of the integers of the blueprint I manipulate the list in the following way. If the next integer is 0, I rotate the sculpture by changing the coordinates for each magnet [a,b] to [-b,a] (basically multiplying with a rotation matrix). If the next integer is a 1, I search for the minimal piece [a,b] (which is automatically the lowest magnet of the leftmost column) and append the magnet [a,b-1] to the list.

After all the input is processed, I create 2 sets (for removing duplicates), one for the x-values and one for the y values, and print the sizes of them in sorted order.

Sml{dCuS?+G,hhGtehGHm,_ekhkGQ],ZZ
                             ],ZZ  starting list G=[(0,0)]
      u                     Q],ZZ  for H in input(): manipulate G
       S                              Sort G after each manipulation
        ?          H                  G = ... if H==1 else ...
                    m,_ekhkG            [(-b,a) for a,b in G)] (rotate)
         +G,hhGtehG                     G+[(G[0][0],G[0][1]-1)]
                                        (G[0] is the lowest magnet in the leftmost column)
     C                             Zip the coords together
                                    (creates 2 lists, x- and y-coords)
 ml{d                              for each of those list compute number of unique values
S                                  sort and print

An idea for improvement: Using complex numbers as coords for the magnets. A rotation is just a multiplication by j and subtracting j from the lowest magnet in the leftmost column. Sadly finding this lowest leftmost magnet takes way too many chars in Python, not even talking of finding the rectangle.


The GOLF CPU Golfing Challenge: Prime Partitions This challenge is the first of a series of fewest-operations problems that should be written in the GOLF CPU.  You can find the next one here

A partition of a number, N, is a list of numbers that add up to N.  A prime partition is a list of prime numbers that add up to N.

For this challenge, you are given a single integer N ≥ 2.  You need generate the shortest possible prime partition for N.  If there are multiple possible partitions, you can print any of them.

Examples:

9: [2, 7]
12: [5, 7]
95: [89, 3, 3]
337: [337]
1023749: [1023733, 13, 3]
20831531: [20831323, 197, 11]

Your program should be written in GOLF CPU.  For input/output you can either use STDIO or the registers.  The list can be in any order, and if you are using STDOUT, can be separated by whitespace or commas (no brackets needed).  Obviously, hardcoding the solutions isn't allowed, nor is hardcoding more than the first few primes.

This is a fewest-operations problem, so the answer that solves the examples above with the fewest amount of cycles wins!

Total cycles for examples: 477,918,603

Update 1: Updated to use Lemoine's conjecture.

Update 2: Updated to use the Sieve of Eratosthenes instead of naively finding the primes.

Run with:

python3 assemble.py 52489-prime-partitions.golf
python3 golf.py 52489-prime-partitions.bin x=<INPUT>

Example run:

$ python3 golf.py 52489-prime-partitions.bin x=10233
5
5
10223
Execution terminated after 194500 cycles with exit code 0.

Cycle count for example input:

Input    Cycles
9        191
12       282
95       1,666
337      5,792
1023749  21,429,225
20831531 456,481,447

We consider the first (N+1)*8 bytes of the heap, to be an array containing N+1 64-bit values. (As the heap is limited in size, this will only work for N < 2^57). The value of the entry at i*8 indicates wether i is a prime:

Value Description
-1    Not a prime
0     Unknown
1     The largest prime found
n > 1 This is a prime and the next prime is n

When we are done building the array it will look like [-1, -1, 3, 5, -1, 7, -1, 11, -1, -1, -1, 13, ...].

We use the Sieve of Eratosthenes to build the array.

Next the program does the following in pseudo-code:

if is_prime(x):
    print x
else:
    if is_even(x):
        for p in primes:
            if is_prime(x - p):
                print p, x - p
                exit
    else:
        if is_prime(x - 2):
            print 2, x - 2
        else:
            for p in primes:
                if is_prime(x - 2 * p):
                    print p, p, 2 * p
                    exit

This is guaranteed to work because of Lemoine's conjecture and Goldbach's weak conjecture. Lemoine's conjecture hasn't be proven yet, but it's probably true for numbers below 2^57.

    call build_primes

    mov q, x
    call is_prime

    jnz print_prime, a

    and b, x, 1
    jz find_pair, b

    # Check if x - 2 is a prime
    sub q, x, 2
    call is_prime
    jnz print_prime_odd2, a

# Input: x, b
find_pair:
    mov p, 2
find_pair_loop:
    mov d, p
    jz find_pair_even, b

    add d, d, p

find_pair_even:
    sub q, x, d

    call is_prime
    jnz print_prime2_or_3, a

    shl i, p, 3
    lw p, i
    jmp find_pair_loop

print_prime2_or_3:
    jz print_prime2, b

    mov x, p
    call write_int_ln

print_prime2:
    mov x, p
    call write_int_ln

    mov x, q
    call print_prime

print_prime_odd2:
    mov p, 2
    call print_prime2

print_prime:
    call write_int_ln
    halt 0

# Input: x
# Memory layout: [-1, -1, 3, 5, -1, 7, -1, 11, ...]
# x: max integer
# p: current prime
# y: pointer to last found prime
# i: current integer
build_primes:
    sw 0, -1
    sw 8, -1
    sw 16, 1
    mov y, 16

    mov p, 2

build_primes_outer:
    mulu i, r, p, p
    jnz build_primes_final, r

    geu a, i, x
    jnz build_primes_final, a

build_primes_inner:
    shl m, i, 3
    sw m, -1

    add i, i, p

    geu a, i, x
    jz build_primes_inner, a

build_primes_next:
    inc p
    shl m, p, 3
    lw a, m
    jnz build_primes_next, a

    sw y, p
    mov y, m
    sw y, 1

    jmp build_primes_outer

build_primes_final:
    inc p
    geu a, p, x
    jnz build_primes_ret, a

    shl m, p, 3
    lw a, m
    jnz build_primes_final, a

    sw y, p
    mov y, m
    sw y, 1

    jmp build_primes_final

build_primes_ret:
    ret

# Input: q
# Output: a
is_prime:
    shl m, q, 3
    lw a, m
    neq a, a, -1
    ret a

write_int:
    divu x, m, x, 10
    jz write_int_done, x
    call write_int
write_int_done:
    add m, m, ord("0")
    sw -1, m
    ret

write_int_ln:
    call write_int
    mov m, ord("\n")
    sw -1, m
    ret


Highest perimeter polyomino This is code golf. The winner is the valid code with the smallest number of bytes.

Challenge

Given inputs M and N, the width and height of a rectangular grid of squares, output a polygon that satisfies the following:

The polygon edges are made up only of square edges: there are no diagonal edges - all are vertical or horizontal.
The polygon has no holes: every square outside the polygon may be reached by orthogonal steps on squares outside the polygon, starting from a square outside the polygon on the outer boundary of the rectangle.
The polygon has no self-intersection: of the square edges meeting at a vertex, no more than 2 may be part of the polygon perimeter.
The polygon is connected: any square in the polygon must be reachable from any other square in the polygon via orthogonal steps that stay within the polygon.
The polygon has the maximum possible perimeter: according to the formula shown below.

Your code must work for M and N from 1 to 255.

Formula for maximum perimeter

The challenge here is finding the most golfable of those polygons with the maximum perimeter. The maximum perimeter itself is always defined by the formula:

This is true because for a maximum perimeter every square vertex must be on the perimeter. For an odd number of vertices this is not possible and the best that can be attained is one vertex less (since the perimeter is always even).

Output

Output the shape as a string of newline separated characters (N rows of exactly M characters). Here I am using space for squares outside the polygon, and '#' for squares inside the polygon, but you may use any two visually distinct characters, provided their meaning is consistent for all inputs.

You may include up to one leading newline and up to one trailing newline.

If you wish, you may instead output M rows of exactly N characters, and you may choose M by N output for some inputs and N by M output for others.

Examples

Invalid due to a hole:

###
# #
###

Invalid due to intersection (touching diagonally - a vertex with 4 square edges on the perimeter) and, incidentally, a hole:

##
# #
###

Invalid due to being disconnected:

#
# #
  #

Valid polygon of maximum perimeter:

# #
# #
###

Credits

I initially underestimated how quickly the value of the maximum perimeter could be calculated, and was going to just ask for that value as the output. Thanks to the wonderfully helpful people in chat for explaining how to work out the maximum perimeter for arbitrary N and M and helping turn this into a challenge that will last for more than one answer...

Specifically thanks to:

Sparr, Zgarb, feersum, jimmy23013.

Ruby, Rev 1, 66
->(m,n){n.times{|i|puts ("#"*m**(1-i%2)).rjust(m,i>n-2?"# ":" ")}}

Used raising m to power 0 o 1 to decide whether 1 or m #'s will be printed.
Used > to test for last row instead of ==.
Can't get rid of the space after puts, nor any brackets!
Ruby, Rev 0, 69
->(m,n){n.times{|i|puts ("#"*(i%2==0?m:1)).rjust(m,i==n-1?"# ":" ")}}

This is an anonymous lambda function. Use it like this:
f=->(m,n){n.times{|i|puts ("#"*(i%2==0?m:1)).rjust(m,i==n-1?"# ":" ")}}

M=gets.to_i
N=gets.to_i
f.call(M,N)

In the end, after asking if M and N could be interchanged I didnt need it.

Typical outputs for N odd. If we delete the # on their own on the right hand side, clearly we will have (N+1)(M+1). Including them to join the shape removes 2 squares of horizontal perimeter and adds 2 squares of vertical perimeter, so there is no change.
Here we rely on the expression "#"*(i%2==0?m:1) to give alternating rows of M# symbols and one # symbol, and right justify to M characters.
5                        6
5                        5
#####                    ######
    #                         #
#####                    ######
    #                         #
#####                    ######

Typical outputs for N even. 5 6 clearly has the same perimeter as 6 5, or an increment of M+1=6 compared with 5 5 by addition of vertical perimeter due to the crenelation of the bottom row. 6 6 has the same as 6 5 plus an increment of (M+1)-1=6 in the vertical perimeter. Thus they are in accordance with the formula.
5                        6
6                        6
#####                    ######
    #                         #
#####                    ######
    #                         #
#####                    ######
# # #                    # # ##

It's very handy that Ruby's rjust allows you to specify the padding to use for the empty cells. Normally the padding is set to " " but for the last row we switch to "# " (note that padding will only be needed on the last row if N is even. Where N is odd the last row will be complete and there will be no justifying, so you won't see the crenelations.)
Check it out here.


Golf this Thumb-2 Constant! One thing that is constantly frustrating when golfing ARM Thumb-2 code is generating constants.
Since Thumb only has 16-bit and 32-bit instructions, it is impossible to encode every immediate 32-bit value into a single instruction.
Additionally, since it is a variable length instruction set, some methods of generating a constant are smaller than others.
I hate that. Write a program or function that does this work for me so I don't have to think about it. (*shudder*)
There are four different variants of the mov instruction as well as a pseudo instruction which loads from a constant pool.
They are either 2 bytes, 4 bytes, or 6 bytes long.
These are the following:

movs: 2 bytes. Generates any 8-bit unsigned value from 0x00 to 0xFF in the low 8 bits, setting the other bits to 0.
mov: 4 bytes. Generates any 8-bit unsigned value bitwise rotated any number of bits,† filling the rest with 0 bits.
mvn: 4 bytes. The same as mov, but generates the one's complement of that rotated 8-bit value, filling the rest with 1 bits.
movw: 4 bytes. Can set the low 16 bits to any 16-bit unsigned value from 0x0000-0xFFFF, and the high 16 bits to 0.
ldr: 6 bytes. The last resort. Can generate any 32-bit value, but is slow and larger than the other options.

†: Note that this is dramatically oversimplified, the real encoding would make this challenge quite frustrating.
The input will be a 32-bit integer, either by string (base 10 signed/unsigned or hex), stdin, or value.
Every value from 0x00000000 to 0xFFFFFFFF must be handled. It is a critical part of the challenge. Watch out for signed shift issues.
However, you can safely assume all inputs will fit into 32 bits, since ARM is a 32-bit architecture.
The output will be the shortest instruction to encode this constant.
The output format is whatever is easiest, as long as the values are distinct and you indicate which instruction corresponds to each output.
There will be a few cases where multiple answers are correct. You may either output one of the correct answers, or all of them. However, you must only display the shortest answers. So, for example, you must only output ldr when none of the other instructions can generate it.
Test cases (values are in hex to show the bit patterns)
0x00000000 -> movs
0x00000013 -> movs
0x000000ff -> movs
0x12345678 -> ldr
0x02300000 -> mov
0xffffffff -> mvn
0x00ffffff -> mvn
0x00001200 -> mov or movw
0x11800000 -> mov
0x80000000 -> mov
0x00000100 -> mov or movw
0x0000f00d -> movw
0xfff3dfff -> mvn
0x03dc0000 -> mov
0xf000000f -> mov
0x00003dc0 -> mov or movw
0x0021f300 -> ldr
0x00100010 -> ldr
0xffff0000 -> ldr

Standard loopholes apply.
Note that as and objdump will not help; they will use the real encoding which is wrong.
Being code-golf, the smallest answer in bytes per language wins.

JavaScript (ES6), 57 bytes
Returns false for "mov", true for "movs", 2 for "ldr", 3 for "mvn" or 4 for "movw".

f=(n,r)=>n>>8?~n>>8?r>31?n>>16?2:4:f(n>>>31|n*2,-~r):3:!r

Try it online!
Commented
f = (                       // f is a recursive function taking:
  n,                        //   n = input
  r                         //   r = rotation counter, initially undefined
) =>                        //
  n >> 8 ?                  // if some of the upper 24 bits of n are not 0's:
    ~n >> 8 ?               //   if some of the upper 24 bits of n are not 1's:
      r > 31 ?              //     if the input was rotated 32 times (which means
                            //     that we've tried all possible rotations and we
                            //     are back to the original value):
        n >> 16 ?           //       if some of the upper 16 bits of n are not 0's:
          2                 //         return 2 for "ldr"
        :                   //       else:
          4                 //         return 4 for "movw"
      :                     //     else:
        f(                  //       do a recursive call:
          n >>> 31 | n * 2, //         rotate n by 1 position to the left
          -~r               //         increment r
        )                   //       end of recursive call
    :                       //   else:
      3                     //     return 3 for "mvn"
  :                         // else:
    !r                      //   return true for "movs" if r is zero'ish
                            //   or false for "mov" if r is greater than 0


Build an engine for a maze game This is a follow up of Print a maze question. If you like this question, please add more maze generation algorithms ;).

For this task you'll have to implement a game engine for one player who must find the treasure in a maze and get out of the dungeon.

The engine starts by reading the maze from standard input followed by a line containing a . (dot) a file given as argument in the command line. Next the player @ is placed in a random location on the map. Then engine starts interacting with the player through standard io:

Commands from engine to player:

continue: Game not finished. The surroundings are printed followed by a .. Player is represented by @ character. Unobservable cells are represented by ?.
finished: Game finished. The number of steps is printed and the game stops.

Commands from player to engine:

north: Moves player up.
south: Moves player down.
west: Move player left.
east: Move player right.

Any invalid command (such as hitting a wall) from player is ignored, but still counted. You are free to define the surroundings to your liking.

Points for the shortest code.
Points for complex surroundings (e.g. print large regions and replace cells that are not visible by ?).
No points for code that doesn't respect the io format

Example:

In this example the surroundings is defined as the 3x3 cell with the player in the middle.

$ cat maze
+-+-+
  |#|
|   |
+---+
$ python engine.py maze
 |#
 @
---
.
east
|#|
 @|
--+
.
north
+-+
|@|
  |
.
south
|#|
 @|
--+
.
west
 |#
 @
---
.
west
  |
|@
+--
.
north
+-+
 @|
|
.
west
finished
7

C99, 771 characters

#include <ncurses.h>
#include <string.h>
#define MIN(A,B) (A<B?A:B)
#define MAX(A,B) (A>B?A:B)
#define T(C,X,Y) case C:if((m[x+X][y+Y]==' ')||(m[x+X][y+Y]=='#'))x+=X,y+=Y;s++;break;
char m[24][81],M[24][81];int i,j,I=0,J,x,y,s=0;
int main(int c,char**v){FILE*f=fopen(v[1],"r");
for(I=0;fgets(m[I],80,f);I++)J=MAX(J,strlen(m[I]));
J--;f=fopen("/dev/random","r");do{x=fgetc(f)%I;y=fgetc(f)%J;}
while(m[x][y]!=' ');initscr();curs_set(0);do{
switch(c){T('e',0,1)T('n',-1,0)T('s',1,0)T('w',0,-1)}
for(i=MAX(0,x-1);i<MIN(x+2,I);i++)for(j=MAX(0,y-1);j<MIN(y+2,J);j++)M[i][j]=1;
for(i=0;i<I;i++)for(j=0;j<J;j++)mvaddch(i,j,M[i][j]?m[i][j]:'?');
mvaddch(x,y,'@');refresh();}while((m[x][y]!='#')&&(c=getch())!='q');
if(m[x][y]=='#')mvprintw(I,0,"Finished in %d steps!",s),getch();endwin();}

Requires and makes use of ncurses. Only one macroization for length, and the N and M macros are to replace the missing minimum and maximum opperators, and I don't think there is much more to do on that.

It assumes the input maze does not exceed 80 characters wide, and that the a maze filename has been passed on the command-line, and that the number of parameters is low enough that the initial value of c isn't a movement command.

Deviates from the standard in that it takes single character direction commands as the lowercase first letter of the ones suggested.
Does show unknown regions as '?'s.

More readable with comments:

#include <ncurses.h>
#include <string.h>

#define MIN(A,B) (A<B?A:B)/*unsafe,but short*/
#define MAX(A,B) (A>B?A:B)/*unsafe,but short*/
// #define MAX(A,B) ((_A=A)>(_B=B)?_A:_B) /* safe but verbose */
#define T(C,X,Y) case C:if((m[x+X][y+Y]==' ')||(m[x+X][y+Y]=='#'))x+=X,y+=Y;s++;break;
char m[24][81],M[24][81];/* [m]ap and [M]ask; NB:mask intialized by default */
int i,j, /* loop indicies over the map */
  I=0,J, /* limits of the map */
  x,y,   /* player position */
  s=0;   /* steps taken */
int main(int c,char**v){
  FILE*f=fopen(v[1],"r"); /* fragile, assumes that the argument is present */
  /* Read the input file */
  for(I=0;fgets(m[I],80,f);I++)J=MAX(J,strlen(m[I])); /* Read in the map */
  J--;
  /* note that I leak a file handle here */
  f=fopen("/dev/random","r");
  /* Find a open starting square */
  do{
    x=fgetc(f)%I; /* Poor numeric properties, but good enough for code golf */
    y=fgetc(f)%J;
  } while(m[x][y]!=' ');
  /* setup curses */
  initscr(); /* start curses */
  //  raw();     /* WARNING! intercepts C-c, C-s, C-z, etc...
  //          * but shorter than cbreak()
  //          */
  curs_set(0); /* make the cursor invisible */
  /* main loop */
  do {
    switch(c){
      T('e',0,1)
      T('n',-1,0)
      T('s',1,0)
      T('w',0,-1)
    }
    /* Update the mask */
    for(i=MAX(0,x-1);i<MIN(x+2,I);i++)
      for(j=MAX(0,y-1);j<MIN(y+2,J);j++)
    M[i][j]=1;
    /* draw the maze as masked */
    for(i=0;i<I;i++)
      for(j=0;j<J;j++)
    mvaddch(i,j,M[i][j]?m[i][j]:'?');
    /* draw the player figure */
    mvaddch(x,y,'@');
    refresh(); /* Refresh the display */
  } while((m[x][y]!='#')&&(c=getch())!='q');
  if(m[x][y]=='#')mvprintw(I,0,"Finished in %d steps!",s),getch();
  endwin();
}


Character Frequency in a String Given a string of printable ASCII, output the frequency of each character in that string.

The Challenge

Input is given as a string of printable ASCII characters (decimal [32-126] inclusive).
Output the frequency of each character, in ASCII order.
The output must have a format similar to [character][separator][count]. Provided that there is a single, non-newline separating string between the character and its frequency, it is a valid output.
Output can be a single string, multiple strings, list of 2-tuples, array of tuples, etc.
Input and output can be given using any convenient method.
Standard loopholes are forbidden.
This is code-golf, so shortest in bytes wins.

Sample I/O

abcd
//outputs
a: 1
b: 1
c: 1
d: 1

Over 9001!
//outputs
  [ 1
! [ 1
0 [ 2
1 [ 1
9 [ 1
O [ 1
e [ 1
r [ 1
v [ 1

--<-<<+[+[<+>--->->->-<<<]>]<<--.<++++++.<<-..<<.<+.>>.>>.<<<.+++.>>.>>-.<<<+.
//outputs (as 2-tuples)
(+,14),(-,13),(.,13),(<,21),(>,13),([,2),(],2)

Su3OH39IguWH
//outputs (as 2d array)
[[3,2],[9,1],[H,2],[I,1],[O,1],[S,1],[W,1],[g,1],[u,2]]

Python 3, 50, 43, 41 bytes

lambda s:{c:s.count(c)for c in sorted(s)}

Try it online!


How divisible are you? You are to create a program which, when given a positive integer \$n\$, outputs a second program. This second program, when run, must take a second positive integer \$x\$ and output one of two distinct values depending on whether \$x\$ is divisible by \$n\$. Those values must be consistent for a given \$n\$ but can be different values for different \$n\$.

However, for each value of \$n\$, the outputted program may only contain bytes whose code points are divisible by \$n\$. You may use any pre-existing code page to score and restrict your answer, but the code pages used for both programs must be the same. In addition, both programs must be in the same language (including versions. Python 3 \$\ne\$ Python 2). Your score is the highest consecutive value of \$n\$ your program works for. That is, your program must work for \$n = 1, 2, 3\$ and \$4\$ in order to have a score of \$4\$. All solutions must work for \$n = 1\$ and \$n = 2\$ at a minimum. The program with the highest \$n\$ wins.

05AB1E, n=13, 189 bytes

'Ì6×ÐI" ÿB`0¢ "D"₁h44₁44÷÷÷ÝÐÃм₁hhhÐÃ44u4÷÷÷₁h44₁44÷÷÷ǝ÷ƶê4₁÷÷ 1 Èÿ°À4ô¤¬ xÒÍÍ<_Zÿ11*Ò88w8*н¡Ë18*Ë xh`H°` ₂6₂6₂6$--«üuÆ-«üuÆ-«üuÆΘ ÒæP<<<<<<<<<<n(Zd XXšXXÜýвXšXš¥Æ≠≠ ÿÿð¨и0Ì<0ǝÀ0ÿäÀ`∍`Ā"#Iè

Try it online! or validate codepoint divisibility.

n=1: 1 simply returns 1, since all integers are divisible by 1.

n=2: È is the built-in for that, and its codepoint is even.

n=3 TIO:

3B        # convert input to base 3
  `       # get the last digit
   0¢     # count occurences of 0 in that digit

n=4 TIO:

°         # 10**input
 À        # rotate left
  4ô      # split in chunks of 4 digits
    ¤     # get the last chunk
     ¬    # get the first digit of that chunk

n=5 TIO:

x         # double the input
 Ò        # prime factorization
  ÍÍ<     # subtract 5 from each prime
     _    # equal to 0?
      Z   # maximum

n=6 works identically to n=3.

n=7 TIO:

11*               # multiply the input by 11
   Ò              # prime factorization
    88w8*н        # first digit of 88*8, namely 7
          ¡       # split the prime factorization on 7
           Ë      # are all sublists equal?
            18*   # multiply by 18
               Ë  # are all digits equal?

n=8 TIO:

x         # double the input
 h        # convert to hex
  `       # get the last digit
   H      # convert from hex
    °     # 10**x
     `    # get the last digit

n=9 TIO:

₂           # push 26
 6          # push 6
  $         # push 1 and input
   -        # subtract: 1 - input
    -       # subtract: 6 - (1 - input) = 5 + input
     «      # concatenate: "26" + (5 + input)
      üu    # for each pair of digit, uppercase the second one
            # (used to convert to a list of digits, but drops the first digit)
        Æ   # reduce by subtraction: 6 - sum(digits(5 + input))
            # the above sequence is repeated twice, yielding 6 - sum(digits(sum(digits(sum(digits(5 + input))))))
         Θ  # is it equal to 1?

Note that this algorithm doesn’t work for arbitrary large numbers (but it still works up to 10^10000000000, which is good enough).

n=10 TIO:

Ò                  # prime factorization of the input
 æ                 # power set
  P                # product of each subset
   <<<<<<<<<<      # subtract 10 from each
             n     # square each
              (    # negate each
               Z   # maximum
                d  # is it >= 0?

Divisibility by 10 is usually the easiest, but unfortunately there’s no compliant way to get the last digit.

n=11 TIO:

X                  # push 1
 Xš                # prepend 1: [1, 1]
   XXÜ             # 1, with trailing 1s trimmed off (aka empty string)
      ý            # join: 11
       в           # convert input to base 11
        Xš         # prepend 1
          Xš       # prepend 1
            ¥      # deltas
             Æ     # reduce by subtraction
              ≠≠   # is it equal to 1?

n=12 TIO:

ÌÌÌÌÌÌÌÌÌÌÌÌ           # add 24 to the input
 ð                     # space character
  ¨                    # drop the last character (empty string)
   и                   # make a list of input empty strings
    0Ì<0ǝ              # replace the first element with 1
     À                 # rotate left
      0ÌÌÌÌÌÌä         # split in 12 parts of approximately equal length
                       # (if the input isn’t divisible by 12, the first sublists will be longer)
       À               # rotate left
        `              # dump all to the stack
         ∍             # cycle the before-last sublist to match the length of the last sublist
          `            # get the last element
           Ā           # truthify

n=13 ([0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]): TIO

₁h44₁44÷÷÷               # hex(256) / (44 / (256 / 44)) = 12
 Ý                       # range [0..12]
  ÐÃ                     # duplicate (well, triplicate then pop the third copy)
    м                    # remove (leaves a list of 13 empty strings)
     ₁hhhÐÃ44u4÷÷÷       # 13
      ₁h44₁44÷÷÷         # 12
       ǝ                 # set the element at index 12 to 13
        ÷                # integer division
                         # dividing by the empty string yields the numerator,
                         # so the result is 12x the input, followed by input / 13
         ƶ               # multiply each element by its index
                         # the last element is now equal to input iff 13 divides input
          ê              # sorted uniquify
           4₁÷÷          # divide by 0 (sets all elements to 0)


Draw diagonal lines of text Given an input of a list of words, output the words with their letters arranged
diagonally:

p
 r
  o
p  g
 u  r
  z  a
a  z  m
 n  l  m
  d  e  i
c     s  n
 o        g
  d
g  e
 o
  l
   f

(The above should be the output for the input programming puzzles and code golf.)

To be precise, each word starts on the first column and three rows below the
previous word, and each successive letter moves one column to the right and one
row down.

The input may be provided as either a single string of words, separated by
exactly one space, or a list/array of words. The words will only be composed of
lowercase letters, a-z, and will always be at least one character long.

The output may be a single string, an array of lines, or an array of arrays of
characters. Leading or trailing whitespace is not allowed, except for a single
trailing newline.

Further test cases:

a bcd efgh i j

a

b
 c
  d
e
 f
  g
i  h

j

x

x

verylongword short

v
 e
  r
s  y
 h  l
  o  o
   r  n
    t  g
        w
         o
          r
           d

Since this is code-golf, the shortest code in bytes will win!

Vim, 85, 76, 66, 52 keystrokes/bytes
When I first looked at this challenge, I thought "This is perfect for vim!" And then when I tried it everything went wrong. Here it is, in all of it's messy hacky glory:
:se ve=all|s/ /\r\r\r/g
qqGo<esc>?\<.\S
lDjP@qq@qG?.
jdG

Try it online, thanks to the (mostly) backwards compatible V interpreter.
Explanation:
At first I thought I could do this beautifully simple 37 byte version:
:se ve=all
qq:g/\S\S/norm ^lDjP
@qq@q

Unfortunately, it's not that simple. Let's take it line by line:
:se ve=all

This enables a feature called 'virtual editing'. It allows the cursor to move to columns that don't exist yet. This answer would be basically impossible without it.
Now we need to separate out the words onto different lines. So we'll replace each space with 3 newlines. Since this is an ex command we can run it simultaneously with our last ex command :se ve=all by seperating the two with a bar.
|s/ /\r\r\r/g

Now the buffer looks like this:
Programming

Puzzles

and

code-golf

Here's where the fun begins. We set up the traditional recursive macro with: qq, and then call this:
G               " Move to the last line
 o<esc>         " Append an extra newline

?               " Search backwards for
 \<.            " Any character at the beginning of a word
    \S          " Followed by a non-space character
l               " Move one character to the right
 D              " Delete eveything until the end of this line
  j             " Move down one line
   P            " Paste what we just deleted

Then we finish the recursive macro with @qq@q. At this point, we have all of the diagonals, we just need to do a little clean up.
G                   " Move to the last line
 ?.                 " Search backwards for any character
j                   " Move down one line
 dG                 " Delete until the end of the buffer


Arbitrary Randomness Randomness is fun. Challenges with no point are fun.

Write a function that, given integer input n, will output a set (unordered, unique) of exactly n random integers between 1 and n^2 (inclusive) such that the sum of all integers is equal to n^2.

Randomness does not have to be uniform, provided each valid set has a non-zero chance to occur.

Shortest answer in bytes (per each language) wins.

Examples

Input (n) = 1, Target (n^2) = 1
Sample of possible outputs:
1

Input = 2, Target = 4
Sample of possible outputs:
3, 1
1, 3

Input = 3, Target = 9
Sample of possible outputs:
6, 1, 2
3, 5, 1
4, 3, 2

Input = 4, Target = 16
Sample of possible outputs:
1, 3, 5, 7
2, 4, 1, 9
8, 3, 1, 4

Input = 5, Target = 25
Sample of possible outputs:
11, 4, 7, 1, 2
2, 3, 1, 11, 8
6, 1, 3, 7, 8

Input = 8, Target = 64
Sample of possible outputs:
10, 3, 9, 7, 6, 19, 8, 2
7, 16, 2, 3, 9, 4, 13, 10
7, 9, 21, 2, 5, 13, 6, 1

Bonus Task: Is there a formula to calculate the number of valid permutations for a given n?

Brachylog (v2), 15 bytes (random) or 13 bytes (all possibilities)

Random

~lℕ₁ᵐA+√?∧A≜₁ᵐ≠

Try it online!

Function submission (seen in TIO with a wrapper making it into a full program).

Explanation

~lℕ₁ᵐA+√?∧A≜₁ᵐ≠
~l               Specify a property of a list: its length is equal to the input,
    ᵐ              and it is composed entirely of
  ℕ₁                 integers ≥ 1,
       √           for which the square root of the
      +              sum of the list
        ?              is the input.
     A   ∧A      Restricting yourself to lists with that property,
           ≜₁      pick random possible values
             ᵐ       for each element in turn,
              ≠    until you find one whose elements are all distinct.

All possibilities

~lℕ₁ᵐ<₁.+√?∧≜

Try it online!

Function submission, which generates all possible outputs.

Explanation

~lℕ₁ᵐ<₁.+√?∧≜
~l               Specify a property of a list: its length is equal to the input,
    ᵐ              it is composed entirely of
  ℕ₁                 integers ≥ 1,
     <₁            it is strictly increasing,
         √         and the square root of the
        +            sum of the list
          ?            is the input.
       .   ∧≜    Generate all specific lists with that property.

I'm fairly surprised that ∧≜ works (you'd normally have to write ∧~≜ in order to brute-force the output rather than the input), but it turns out that ≜ has an input=output assumption so it doesn't matter which way round you run it.

Bonus task

In order to get some insight into the sequence of the number of possibilities, I created a different TIO wrapper which runs the program on successive integers to give the sequence of output counts:

1,1,3,9,30,110,436,1801,7657,33401

A trip to OEIS discovers that this is already a known sequence, A107379, described pretty much as in the question (apparently you get the same sequence if you restrict it to odd numbers). The page lists several formulas for the sequence (although none is particularly simple; the second looks like a direct formula for the value but I don't understand the notation).


Simple DTMF decoding: find the phone key! This is a simple challenge which hopefully may lead to some creative answers.

Quoting Wikipedia: "Dual-tone multi-frequency signaling (DTMF) is an in-band telecommunication signaling system using the voice-frequency band over telephone lines between telephone equipment and other communications devices and switching centers."

Task

Given two integers representing the column and row frequencies in the following table, your task is to output the corresponding key:

       | 1209 Hz | 1336 Hz | 1477 Hz
-------+---------+---------+---------
697 Hz |    1    |    2    |    3
770 Hz |    4    |    5    |    6
852 Hz |    7    |    8    |    9
941 Hz |    *    |    0    |    #

Examples

If the input is [ 1209, 852 ], the expected output is "7".
If the input is [ 1477, 941 ], the expected output is "#".

Rules

You must take input as integers in any reasonable format, such as two separate variables or an array of two variables. Please specify in which order your program is expecting them (either column_freq, row_freq or row_freq, column_freq).
The input is guaranteed to be valid.
You must print or output a character. However, you're also allowed to output an integer for digit keys.
This is code-golf, so the shortest answer in bytes wins!

JavaScript (ES6), 39 35 bytes

a=>b=>"310*58# 47269"[a%b%83%16%13]

Maps the two inputs into numbers in the range [0, 13) by calculating:
col % row % 83 % 16 % 13.
Takes input in currying syntax (f(col)(row)) and returns a single-char string.

Test Cases

let f=
a=>b=>"310*58# 47269"[a%b%83%16%13]

console.log( f(1336)(941) )
console.log( f(1209)(697) )
console.log( f(1336)(697) )
console.log( f(1477)(697) )
console.log( f(1209)(770) )
console.log( f(1336)(770) )
console.log( f(1477)(770) )
console.log( f(1209)(852) )
console.log( f(1336)(852) )
console.log( f(1477)(852) )
console.log( f(1209)(941) )
console.log( f(1477)(941) )
.as-console-wrapper{max-height:100%!important}

History

Started with the range of [0, 20) with calculation col % row % 29 % 20, which required 8 wasted characters in the mapping.


Output in the Correct Order Ok lets say we get a input the following csv file (all entries are quoted strings)

ID,    Before,   After,   Value
 1,         3,       5,    Cat
 2,         5,        ,    Apple
 3,         4,       1,    Dog
 4,          ,       3,    Elephant
 5,         1,       2,    Banana

Output a csv file in which the entries are usage sequence order.

ID,    Before,   After,   Value
 2,         5,        ,    Apple
 5,         1,       2,    Banana
 1,         3,       5,    Cat
 3,         4,       1,    Dog
 4,          ,       3,    Elephant

Notes:
The Values may not necessarily appear in alphabetical order all the time, just that in this example they are.
No revaluing of the IDs being use. They must be the same as input.

Input and Output files will be pass as args to program.

Ruby 109 108

Saved one whole character by using randomization instead of searching!

h,*t=[*$<]
t.shuffle!until t.each_cons(2).all?{|c|a,b=c.map{|y|y.lstrip.split /[,\s]+/}
a[1]==b[0]}
puts h,t

This only prints to stdout, so to save to a file use ruby csv.rb in.csv > out.csv.

$ cat test.csv
ID,    Before,   After,   Value
 1,         3,       5,    Cat
 2,         5,        ,    Apple
 3,         4,       1,    Dog
 4,          ,       3,    Elephant
 5,         1,       2,    Banana
$ ruby csv.rb test.csv
ID,    Before,   After,   Value
 2,         5,        ,    Apple
 5,         1,       2,    Banana
 1,         3,       5,    Cat
 3,         4,       1,    Dog
 4,          ,       3,    Elephant

Old version

puts gets,[*$<].permutation.find{|x|x.each_cons(2).all?{|c|a,b=c.map{|y|y.lstrip.split /[,\s]+/}
a[1]==b[0]}}

It simply finds the permutation of the lines where, for each line, the second column (Before) equals the first column (ID) of the next line.


Print the Australian Flag! Here we go again! This is my last flag for now!

I originally wanted to do my national flag but I thought the stars were too hard so I posted Print the British Flag! instead, which itself was inspired by Print the American Flag!. This challenge would be better for 3 September (Australian National Flag Day) or 26 January (Australia Day) but I couldn't wait that long! The Commonwealth Star is a bit messy but I'm pleased with the rest of the design. Once again you need to view it at 90 degrees.

Produce the following design in the fewest bytes!

 ________________________________________________
|XXXXXXXXXXXXXXXXXXXXXXXX\  \XXXX  0000  XXXX//0/|
|XXXXXXXXXXXXXXXXXXXXXXXX0\  \XXX  0000  XXX//0/ |
|XXXXXXXXXXXXXXXXXXXXXXXX\0\  \XX  0000  XX//0/  |
|XXXXXXXXXXXXXXXXXXXXXXXX\\0\  \X  0000  X//0/  /|
|XXXXXXXXXXXXXXXXXXXXXXXXX\\0\  \  0000  //0/  /X|
|XXXXXXXXXXXXXXXXXXXXXXXXXX\\0\    0000  /0/  /XX|
|XXXXXXXXXXXXXXXXXXXXXXXXXXX\\0\   0000  0/  /XXX|
|XXXXXXXXXXXXXXXXXXXXXXXXXXXX\\0\  0000  /  /XXXX|
|XXXXXXXX|\XXXXX-/XXXXXXXXXXXX\\0  0000    /XXXXX|
|XXXXX-XX| \XX- /XXXXXXXXXXXXXX\\  0000   /XXXXXX|
|XXXXX\ -|      --XXXXXXX          0000          |
|XXXXXXX\          -XXXXX000000000000000000000000|
|XXXXXXX/          -XXXXX000000000000000000000000|
|XXXXX/ -|      --XXXXXXX          0000          |
|XXXXX-XX| /XX- \XXXXXXXXXXXXXX/   0000  \\XXXXXX|
|XXXXXXXX|/XXXXX-\XXXXXXXXXXXX/    0000  0\\XXXXX|
|XXXXXXXXXXXXXXXXXXXXXXXXXXXX/  /  0000  \0\\XXXX|
|XXXXXXXXXXXXXXXXXXXXXXXXXXX/  /0  0000   \0\\XXX|
|XXXXXXXXXXXXXXXXXXXXXXXXXX/  /0/  0000    \0\\XX|
|XXXXXXXXXXXXXXXXXXXXXXXXX/  /0//  0000  \  \0\\X|
|XXXXXXXXXXXXXXXXXXXXXXXX/  /0//X  0000  X\  \0\\|
|XXXXXXXXXXXXXXXXXXXXXXXX  /0//XX  0000  XX\  \0\|
|XXXXXXXXXXXXXXXXXXXXXXXX /0//XXX  0000  XXX\  \0|
|XXXXXXXXXXXXXXXXXXXXXXXX/0//XXXX  0000  XXXX\  \|
|XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX|
|XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX|
|XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX|
|XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX|
|XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX|
|XXXXXXXXXXXXXXXXXXXXXXXXX|\/|XXXXXXXXXXXXXXXXXXX|
|XXXXXXXXXXXXXXXXXXXXXXXX>    >XXXXXXXXXXXXXXXXXX|
|XXXXXXXXXXXXXXXXXXXXXXXXX|/\|XXXXXXXXXXXXXXXXXXX|
|XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX|
|XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX|
|XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX|
|XXXXXX|\/|XXXXXXXXXXXXXXXXXXXXXXXXXXXX|\/|XXXXXX|
|XXXXX>    >XXXXXXXXXXXXXXXXXXXXXXXXXX>    >XXXXX|
|XXXXXX|/\|XXXXXXXXXXXXXXXXXXXXXXXXXXXX|/\|XXXXXX|
|XXXXXXXXXXXXXXXXXXXXX/|XXXXXXXXXXXXXXXXXXXXXXXXX|
|XXXXXXXXXXXXXXXXXXX>   >XXXXXXXXXXXXXXXXXXXXXXXX|
|XXXXXXXXXXXXXXXXXXXXX\|XXXXXXXXXXXXXXXXXXXXXXXXX|
|XXXXXXXXXXXXXXXXXXXXXXXXXXXX|\/|XXXXXXXXXXXXXXXX|
|XXXXXXXXXXXXXXXXXXXXXXXXXXX>    >XXXXXXXXXXXXXXX|
|XXXXXXXXXXXXXXXXXXXXXXXXXXXX|/\|XXXXXXXXXXXXXXXX|
|XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX|
|XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX|
|XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX|
|XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX|

Things to watch out for: there is a space at the end of the first line. No other trailing spaces are allowed. The dimensions are 50 x 49 (48 x 48 plus borders on three sides).The fifth star (5-pointed) in the Southern Cross is slightly smaller and a different design from the others (7-pointed). A trailing newline is allowed but not required.

My code editor has a thumbnail view of the code at the side. This is what this design looks like:

Not bad!

Python 2, 446 Bytes

Just decodes the Base64 and decompresses using zlib.

import zlib,base64
print zlib.decompress(base64.b64decode("eNrl1MFtwzAMBdCeMwUXEOgJPIcPBLqIhk8ofkq2QdFQb215iZDkgdSXZfpeLHrVY1JCJPpJtH2KSNfMG9c52WBORAUlRL7MDNJESsT6dGIiG8yNE4gjIzCdmMiJGyMQDwQGXUycSW2ncBS+GScQnZTPUhMtxPc+neAXJ0KlUqtS8Gfq5V2sxmAyvjS0TWoQXiW8PljbPuv25bp97kTkun1dWiJF7sKPEubhKLmdILrA5ETFOEqYlDCeRd++mYyYGIPBJARiXDGYhECcLrKZjJg4vy6ayQYzcXkpqXk4l6j+C6nCdY3s+ljti11Y6q9MbBJPEJ+TWTxBfKNLHE8Q32wvyZQx2bMpZ12k/jTkKMechDk+dQly/FMX+Q3ohQN5"))


Draw the Easter Bunny This happy individual is known in folklore as the Easter Bunny.

Colours
It is created using 4 colours:

Light pink
Dark pink
White
Black

(I'm happy for these colours to be approximated in your answer. It does not need to be this precise shade)
Shapes
It is constructed of these shapes:

Two tall ellipses in light pink (outer ears). They have the same height and width.
Two tall ellipses in dark pink (inner ears). They are smaller than the outer ears and one is drawn on top of each of the outer ears. They are the same height and width.
One large circle in light pink (head). It intersects with the bottom third of both outer ears (but no higher).
Two circles in white (outer eyes). They are drawn on the head. Their diameter is less than the width of the outer ears. They have the same horizontal position as the outer ears.
Two circles in black (inner eyes). They have a smaller diameter than the outer eyes. One is drawn on each of the outer eyes.
One vertical line in black (upper mouth). It is drawn on the head and is lower than the bottom of the outer eyes. It is roughly equidistant from each eye.
Two arcs in black (lower mouth). They are drawn on the head and arc downwards from a horizontal line. Both intersect with the bottom of the upper mouth, but one goes right and the other goes left.

The Rules

Use any language and tools you like.
Output can be an image, html, svg, or other markup.
It's code golf, so aim to do it in the smallest number of bytes.
Please include a screenshot of the result.
Please feel free to approximate the colours defined.

Happy Easter!

T-SQL, 445 439 bytes
DECLARE @ GEOMETRY='MULTIPOINT((3 3),(7 3))',
@l GEOMETRY='CIRCULARSTRING(3 6,3.3 9,3 12,2.7 9,3 6)',@r GEOMETRY
SET @=@.STBuffer(.6)SET @r=@l.STUnion('CIRCULARSTRING(7 6,7.3 9,7 12,6.7 9,7 6)')
SELECT*FROM(VALUES(@),(@),(@),(@r.STBuffer(.3)),(@),(@),(@),(@),(@),(@),(@),(@),(@),
(@),(@),('CIRCULARSTRING(7 0,6 -1,5 0,5 1,5 1,5 0,5 0,4 -1,3 0)'),
(GEOMETRY::Point(5,1,0).STBuffer(5).STUnion(@r.STBuffer(1.3)).STDifference(@.STBuffer(.4)))
)a(g)

This site could use more T-SQL-based drawings!
Run on SQL 2017, but uses SQL geo-spatial storage features added back in SQL 2008. Line breaks are for readability only.
Output:

So, this was a pain to do in T-SQL, since spatial objects aren't exactly designed for drawing (no "ellipse" object, for example). Even more, getting the colors even close to right required a bit of trial and error.
Basically I'm constructing the following geometric objects:

The eyes (@), which are points expanded into disks using STBuffer(.6) (the set of all points within 0.6 of those starting points)
The ears (@r), which are generated as pointy curves, but are "puffed out" using STBuffer into either the inner or outer ears
The face, which is a disk plus the ears minus the eyes. I have to construct this and display it as a single object, or SQL would display it in different colors.
The mouth, which is a curve created using CIRCULARSTRING

To get the colors right, I have to SELECT these in the proper order. SSMS has a built-in sequence of colors for objects displayed in the spatial results pane, so the dark pink inner ears had to come 4th, and the light pink face had to come 16th. This required putting in a whole bunch of extra copies of the eyes, which is ok since we want them as close to black as possible (colors are somewhat transparent, so stacking them makes them darker).
Help and inspiration from the following resources:

Drawing in color in SQL
Botticelli’s Birth of Venus using T-SQL
SQL Server Christmas card

EDIT: Moved the bunny down by 4 units, which changes some coordinates to a single digit, saving 6 bytes. No change in displayed output.


Draw an Empty Scrabble Board A standard Scrabble board is a 15×15 grid of spaces to place letter tiles. Most of the spaces are blank but some are double word scores (pink), triple word scores (red), double letter scores (light blue), and triple letter scores (blue). There is usually a star in the very center (which counts as a double word score).

Write a program or function that outputs a standard, empty Scrabble board in ASCII form where:

. represents an empty space
D represents a double word score
T represents a triple word score
d represents a double letter score
t represents a triple letter score
X represents the center star

That is, your exact output must be

T..d...T...d..T
.D...t...t...D.
..D...d.d...D..
d..D...d...D..d
....D.....D....
.t...t...t...t.
..d...d.d...d..
T..d...X...d..T
..d...d.d...d..
.t...t...t...t.
....D.....D....
d..D...d...D..d
..D...d.d...D..
.D...t...t...D.
T..d...T...d..T

optionally followed by a trailing newline.

The shortest code in bytes wins.

MATL, 59 54 52 bytes

4t:g2I5vXdK8(3K23h32h(H14(t!XR+8: 7:Pht3$)'DtdTX.'w)

Try it online!

Explanation

The code follows three main steps:

Generate the 8x8 matrix

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

Extend it to the 15x15 matrix

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

Index the string 'DtdTX.' with that matrix to produce the desired result.

Step 1

4        % Push 4
t:       % Duplicate, range: pushes [1 2 3 4]
g        % Logical: convert to [1 1 1 1]
2I5      % Push 2, then 3, then 5
v        % Concatenate all stack vertically into vector [4 1 1 1 1 2 3 5]
Xd       % Generate diagonal matrix from that vector

Now we need to fill the nonzero off-diagonal entries. We will only fill those below the diagonal, and then make use symmetry to fill the others.

To fill each value we use linear indexing (see this answer, length-12 snippet). That means accessing the matrix as if it had only one dimension. For an 8×8 matrix, each value of the linear index refers to an entry as follows:

1   9         57
2  10         58
3  11
4
5  ...       ...
6
7             63
8  16 ... ... 64

So, the following assigns the value 4 to the lower-left entry:

K        % Push 4
8        % Push 8
(        % Assign 4 to the entry with linear index 8

The code for the value 3 is similar. In this case the index is a vector, because we need to fill several entries:

3        % Push 3
K        % Push 4
23h      % Push 23 and concatenate horizontally: [4 23]
32h      % Push 32 and concatenate horizontally: [4 23 32]
(        % Assign 4 to the entries specified by that vector

And for 2:

H        % Push 2
14       % Push 14
(        % Assign 2 to that entry

We now have the matrix

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

To fill the upper half we exploit symmetry:

t!       % Duplicate and transpose
XR       % Keep the upper triangular part without the diagonal
+        % Add element-wise

Step 2

The stack now contains the 8×8 matrix resulting from step 1. To extend this matrix we use indexing, this time in the two dimensions.

8:       % Push vector [1 2 ... 7 8]
7:P      % Push vector [7 6 ... 1]
h        % Concatenate horizontally: [1 2 ... 7 8 7 ... 2 1]. This will be the row index
t        % Duplicate. This will be the column index
3$       % Specify that the next function will take 3 inputs
)        % Index the 8×8 matrix with the two vectors. Gives a 15×15 matrix

Step 3

The stack now contains the 15×15 matrix resulting from step 2.

'DtdTX.' % Push this string
w        % Swap the two elements in the stack. This brings the matrix to the top
)        % Index the string with the matrix


An Old Irish Blessing, reasked (without using encodings) How much can you golf a program to print "An Old Irish Blessing" without using unprintable ASCII characters?

That restricts us to ASCII characters 32-126 (better still, 32,65-90,97-122 and 13(CR))

For reference that version of the proverb is 205 characters long (excl. newlines).
I'm curious if anything beats Huffman-encoding incl. spaces.

Golfscript, 198 characters
[]"-!9 4(% 2/!$<)3A50H/ -%%4 9/5
XXXN7).X\"?!,7I3>4UU2I!#+
[[[S35.;(`A[2- 50/.]]]&]%
YO2!U3F|,`/&4ZZZZZK)%,$3
!.$ }4),ze-%%Z!'!k\n-!9 '/S(/]hh )o4(%GG,/7 /&A)3;!v"{.32>{.58<{32+}{56-~1$>2<}if}*+}/+

Output:
$ ruby golfscript.rb blessing.gs
MAY THE ROAD RISE UP TO MEET YOU
MAY THE WIND BE ALWAYS AT YOUR BACK
MAY THE SUN SHINE WARM UPON YOUR FACE
THE RAINS FALL SOFT UPON YOUR FIELDS
AND UNTIL WE MEET AGAIN
MAY GOD HOLD YOU IN THE HOLLOW OF HIS HAND

The poem is compressed to 158 characters by using part of the ASCII range for back-references (of fixed length 2). The coding scheme is as follows:
[10]      : newline (unencoded)
[32]      : space (unencoded)
[33..57]  : literal (33=A, 34=B, ... 57=Y, Z not needed)
[58..126] : back-reference relative to the end of the decompressed string so far.

The remaining 40 characters make up the decompression code which can probably be golfed a little further, since this is my first attempt at Golfscript.

Case-sensitive version, 207 characters
Same concept, but trading some of the back-reference range for lower case letters at the cost of some compression.
[]"-AY THE ROAD RISaUPhO MEET YOU
xxxnWINxB_ALWiS^TuuRiACK
{{{sSUN[HINa{RM UPON}}}F}E
4HoRAuS fLL SOFTzzzzzkIELDS
!NDlNTIwWE MEEzAGAIN
-AY 'OsHOLxYOU k THEggLOW OF (ISeAND"{.32>{.90<{32+}{88-~1$>2<}if}*+}/+

Output:
$ ruby golfscript.rb blessing-casesensitive.gs
May the road rise up to meet you
May the wind be always at your back
May the sun shine warm upon your face
The rains fall soft upon your fields
And until we meet again
May God hold you in the hollow of His hand


Roll a cube to a target position You have your very heavy cubical box on a flat floor at position (0,0). All you can do with it is roll it in four cardinal directions (east, north, west, south). Your task is to bring it to a target position, such that the side facing up is the same as before your manipulations.

Make a program or function which receives target coordinates and returns the minimal sequence of moves which results in the box arriving to target in upright position.

Input: two integers x, y

Get it in any convenient format - as a pair, as a complex number, etc.
You can assume x² + y² ≠ 0

Output: a string of instructions containing characters E, N, W, S

Spaces and newlines are allowed
UPPER-CASE, lower-case and MiXeD-cAsE are allowed

Test cases:

2, 2 => EENN
2, 3 => ENENN
1, 0 => NES
-1, 0 => NWS
-1, -1 => ESWNWS
3, 4 => ENNENEN
-9, 0 => NWWWWWWWWWS
20, 5 => EEEEEEEEEEEEEEEEEEENENNNN

Note: the solutions above are not unique, so your code can have slightly different output. But it's required to output a minimal solution.

Invalid test cases:

0, 0 => not required to handle (the solution is an empty string)
1, 0 => N (invalid - the box arrives to x=0, y=1)
1, 0 => E (invalid because the box on its side)
2, 2 => ENWNESENWNES (invalid because it's not minimal)

JavaScript (ES6),  146 ... 138  125 bytes
Saved 2 bytes thanks to @Klaycon
Takes input as [x,y]. Brute-forces a path.
p=>eval("for(n=0;s=([X,Y]=p,k=0,++n+'').replace(/./g,n=>n<4&&'ENWS'[X+=~-n%2,Y+=~-~-n%2,k+=(n&2^6)+(k-~n)%3,n]),X|Y|k%6;);s")

Try it online!
How?
The position of the top face is \$k \bmod 6\$:
$$\begin{array}{c|c|c|c|c|c}
0&1&2&3&4&5\\[5px]
\hline
\text{top}&\text{left}&\text{back}&\text{bottom}&\text{right}&\text{front}
\end{array}$$
The current direction is \$n\$:
$$\begin{array}{c|c|c|c}
0&1&2&3\\[5px]
\hline
\text{East}&\text{North}&\text{West}&\text{South}
\end{array}$$
Given \$k\$ and \$n\$, the new position of the top face is:
$$k'=k+((n\operatorname{and}2)\operatorname{xor}6)+((k+n+1)\bmod3)$$
The values of \$k'\bmod6\$ given \$n\$ and \$k\bmod6\$ are summarized in the following table:
$$\begin{array}{c|cccccc}
k \bmod 6 & 0 & 1 & 2 & 3 & 4 & 5\\
\hline
n = 0 & 1 & 3 & 2 & 4 & 0 & 5\\
n = 1 & 2 & 1 & 3 & 5 & 4 & 0\\
n = 2 & 4 & 0 & 2 & 1 & 3 & 5\\
n = 3 & 5 & 1 & 0 & 2 & 4 & 3
\end{array}$$
Commented
Note: this is a version without eval() for readability
p => {                   // p = [x, y] = starting position
  for(                   // main loop:
    n = 0;               //   start with n = 0
    s = (                //   s is the move string that we're going to build
      [X, Y] = p,        //     start with [X, Y] = starting position
      k = 0,             //     start with k = 0
      ++n + ''           //     increment n and coerce it to a string
    ).replace(/./g, n => //   for each digit n in the resulting string:
      n < 4 &&           //     abort if n is greater than or equal to 4
      'ENWS'[            //     replace it with a direction character
        X += ~-n % 2,    //       X += dx
        Y += ~-~-n % 2,  //       Y += dy
        k +=             //       update k
          (n & 2 ^ 6) +  //
          (k - ~n) % 3,  //
        n                //       actual index for the direction character
      ]                  //
    ),                   //   end of replace()
    X | Y | k % 6;       //   stop when X = Y = k mod 6 = 0
  );                     // end of for()
  return s               // return the solution
}                        //


When in Rome, Count as Romans do? Background

This challenge is inspired by this website, which published the following diagram:

This diagram shows us that the longest Roman Numeral expression under 250 is that of 188, which requires 9 numerals to express.

Challenge

The standard symbols used to express most Roman Numerals are the following: {I, V, X, L, C, D, M}, where the characters' numeric values are M=1000, D=500, C=100, L=50, X=10, V=5, I=1.

In this challenge, your goal is to, given an positive integer n, compute the number of valid Roman Numeral representations that can be composed through concatenating n of the standard symbols.

Then, your program must output the result of this computation!

Input: A positive integer n.

Output: The number of valid roman numeral expressions of length n.

Rules for Roman Numeral Expressions

Roman Numerals originally only had "additive" pairing, meaning that numerals were always written in descending order, and the sum of the values of all the numerals was the value of the number.

Later on, subtractive pairing, the use of placing a smaller numeral in front of a larger in order to subtract the smaller from the larger, became commonplace to shorten Roman Numeral expressions. Subtractive pairs cannot be chained, like in the following invalid expression: IXL.

The following are the modern day rules for additive and subtractive pairing.

Only one I, X, and C can be used as the leading numeral in part of a subtractive pair.
I can only be placed before V or X in a subtractive pair.
X can only be placed before L or C in a subtractive pair.
C can only be placed before D or M in a subtractive pair.
Other than subtractive pairs, numerals must be in descending order (meaning that if you drop the leading numeral of each subtractive pair, then the numerals will be in descending order).
M, C, and X cannot be equalled or exceeded by smaller denominations.
D, L, and V can each only appear once.
Only M can be repeated 4 or more times.

Further Notes

We will not be using the bar notation; rather, we will simply add more Ms to express any number.
These are the only rules that we will follow for our roman numerals. That means that odd expressions, such as IVI, will also be considered valid in our system.
Also remember that we are not counting the number of numbers that have expressions of length n, since some numbers have multiple expressions. Instead, we are solely counting the number of valid expressions.

Test Cases

1 → 7

2 → 31

3 → 105

I checked the above by hand, so please make sure to double check the test cases, and add more if you can!

Winning Criteria

This is a code-golf challenge, so have fun! I will only accept solutions that can handle at least inputs from 1 through 9. Any more is bonus!

Edit

As requested by commenters, find below, or at this pastebin link, the 105 combos I counted for n=3

  III
  IVI
  IXI
  IXV
  IXX
  VII
  XII
  XIV
  XIX
  XVI
  XXI
  XXV
  XXX
  XLI
  XLV
  XLX
  XCI
  XCV
  XCX
  XCL
  XCC
  LII
  LIV
  LIX
  LVI
  LXI
  LXV
  LXX
  CII
  CIV
  CIX
  CVI
  CXI
  CXV
  CXX
  CXL
  CXC
  CLI
  CLV
  CLX
  CCI
  CCV
  CCX
  CCL
  CCC
  CDI
  CDV
  CDX
  CDL
  CDC
  CMI
  CMV
  CMX
  CML
  CMC
  CMD
  CMM
  DII
  DIV
  DIX
  DVI
  DXI
  DXV
  DXX
  DXL
  DXC
  DLI
  DLV
  DLX
  DCI
  DCV
  DCX
  DCL
  DCC
  MII
  MIV
  MIX
  MVI
  MXI
  MXV
  MXX
  MXL
  MXC
  MLI
  MLV
  MLX
  MCI
  MCV
  MCX
  MCL
  MCC
  MCD
  MCM
  MDI
  MDV
  MDX
  MDL
  MDC
  MMI
  MMV
  MMX
  MML
  MMC
  MMD
  MMM

Edit 2:

Use the following non-golfed code, as courtesy of Jonathan Allan to check your results.

Edit 3:

I apologize for all of the errors in this challenge. I'll make sure to do a better job next time!

Python 2, 177 168 162 bytes

import re,itertools as q
f=lambda n:sum(None!=re.match("^M*(CM|CD|D?C{0,3})(XC|XL|L?X{0,3})(IX|IV|V?I{0,3})$",(''.join(m)))for m in q.product('MDCLXVI',repeat=n))

Try it online!

I'm pretty new, help me golf this! This checks for actual roman numerals, the regex needs to be adjusted to account for the odd cases such as IVI

-9 bytes thanks to @Dead Possum!

-6 bytes thanks to @ovs


Irreducible polynomials over GF(5) A polynomial with coefficients in some field F is called irreducible over F if it cannot be decomposed into the product of lower degree polynomials with coefficients in F.

Consider polynomials over the Galois field GF(5). This field contains 5 elements, namely the numbers 0, 1, 2, 3, and 4.

Task

Given a positive integer n, compute the number of irreducible polynomials of degree n over GF(5). These are simply the polynomials with coefficients in 0-4 which cannot be factored into other polynomials with coefficients in 0-4.

Input

Input will be a single integer and can come from any standard source (e.g. STDIN or function arguments). You must support input up to the largest integer such that the output does not overflow.

Output

Print or return the number of polynomials that are irreducible over GF(5). Note that these numbers get large rather quickly.

Examples

In : Out
 1 : 5
 2 : 10
 3 : 40
 4 : 150
 5 : 624
 6 : 2580
 7 : 11160
 8 : 48750
 9 : 217000
10 : 976248
11 : 4438920

Note that these numbers form the sequence A001692 in OEIS.

Jelly, 30 23 22 20 bytes
ÆF>1’PḄ
ÆDµU5*×Ç€S:Ṫ

Try it online! or verify all test cases at once.
Algorithm
This uses the formula
$$\text{A001692}(n) = \frac 1 n \sum_{d|n} \mu(d)5^\frac n d$$
from the OEIS page, where \$d | n\$ indicates that we sum over all divisors \$d\$ of \$n\$, and \$\mu\$ represents the Möbius function.
Code
ÆF>1’PḄ       Monadic helper link. Argument: d
              This link computes the Möbius function of d.

ÆF            Factor d into prime-exponent pairs.
  >1          Compare each prime and exponent with 1. Returns 1 or 0.
    ’         Decrement each Boolean, resulting in 0 or -1.
     P        Take the product of all Booleans, for both primes and exponents.
      Ḅ       Convert from base 2 to integer. This is a sneaky way to map [0, b] to
              b and [] to 0.

ÆDµU5*×Ç€S:Ṫ  Main link. Input: n

ÆD            Compute all divisors of n.
  µ           Begin a new, monadic chain. Argument: divisors of n
   U          Reverse the divisors, effectively computing n/d for each divisor d.
    5*        Compute 5 ** (n/d) for each n/d.

       Ç€     Map the helper link over the (ascending) divisors.
      ×       Multiply the powers by the results from Ç.
         S    Add the resulting products.
          :Ṫ  Divide the sum by the last divisor (n).


Symbolic Differentiation of Composed Functions Symbolic Differentiation 2: Back on the Chain Gang

Task

Write a program that takes in a certain sort of function from stdin and differentiates it with respect to x, using the chain rule.* The input function will be a string of the following form:

"trig_1 trig_2 trig_3 ... x"

where trig_n is a trigonometric function sin or cos, and there are at most four functions in the term. The example string

"cos sin sin x"

represents the function cos(sin(sin(x))).

Your output must take the following form:

k(trig_1 trig_2 x)(trig_a trig_b trig_c x)(trig_m trig_n x) et cetera

where k is a constant and parentheses represent groups to be multiplied together.

*The chain rule states that D[f(g(x))] = f'(g(x)) * g'(x)

Examples

"sin sin sin sin x" ==> 1(cos x)(cos sin x)(cos sin sin x)(cos sin sin sin x)
"cos x" ==> -1(sin x)
"cos sin x" ==> -1(cos x)(sin sin x)

Scoring

Your score is the length of your program in bytes, multiplied by three if you use a built-in or a library that does symbolic algebra.

Similar Challenges

The previous installment: polynomial differentiation
Polynomial integration
General differentiation

Java 8, 224 214 bytes

Let the games begin!

interface B{static void main(String[]a){String o="";int v=2,z=a.length-1,i=z,k;for(;i>0;o+="x)"){if(a[--i].equals("cos")){o+="(sin ";v=(v+2)%4;}else o+="(cos ";for(k=i;++k<z;)o+=a[k]+" ";}System.out.print(v-1+o);}}

This could (theoretically) extend infinitely.

Output for sin cos sin sin cos sin cos sin sin sin cos sin sin cos sin cos cos cos sin x:

1(cos x)(sin sin x)(sin cos sin x)(sin cos cos sin x)(cos cos cos cos sin x)(sin sin cos cos cos sin x)(cos cos sin cos cos cos sin x)(cos sin cos sin cos cos cos sin x)(sin sin sin cos sin cos cos cos sin x)(cos cos sin sin cos sin cos cos cos sin x)(cos sin cos sin sin cos sin cos cos cos sin x)(cos sin sin cos sin sin cos sin cos cos cos sin x)(sin sin sin sin cos sin sin cos sin cos cos cos sin x)(cos cos sin sin sin cos sin sin cos sin cos cos cos sin x)(sin sin cos sin sin sin cos sin sin cos sin cos cos cos sin x)(cos cos sin cos sin sin sin cos sin sin cos sin cos cos cos sin x)(cos sin cos sin cos sin sin sin cos sin sin cos sin cos cos cos sin x)(sin sin sin cos sin cos sin sin sin cos sin sin cos sin cos cos cos sin x)(cos cos sin sin cos sin cos sin sin sin cos sin sin cos sin cos cos cos sin x)


Generate input for this hardware I have a hardware that has a 32-bit input register. The register has the following characteristics:

The 32-bit register consists of eight 4-bit fields.
Each 4-bit field holds a value in signed-magnitude; it can hold an integer between -7 and +7 inclusive, including -0 and +0 (signed zeroes).

For example, the hexadecimal value 0xABCD1234 represents the field values [-2, -3, -4, -5, +1, +2, +3, +4]. In fact, one hex digit represents one 4-bit value with the following mapping:

Hex    |  Input value
---------------------
0 ~ 7  |  +0 ~ +7
8 ~ F  |  -0 ~ -7

In order to operate this hardware, I figured that the most natural inputs would be 8 consecutive increasing values, treating -0 and +0 as distinct. So the input values will be one of the following:

field values for 8 fields        => 32-bit register value
[-7, -6, -5, -4, -3, -2, -1, -0] => 0xFEDCBA98 (offset -4)
[-6, -5, -4, -3, -2, -1, -0, +0] => 0xEDCBA980 (offset -3)
...
[-3, -2, -1, -0, +0, +1, +2, +3] => 0xBA980123 (balanced, offset 0)
...
[+0, +1, +2, +3, +4, +5, +6, +7] => 0x01234567 (offset +4)

I define the input 0xBA980123 as balanced, and the other inputs have an offset from the balanced input. The balanced input itself has offset 0.

Task

Given the offset, output the desired value for the input register for my hardware as described above.

Input and output

The input (offset) is an integer between -4 and 4 inclusive. You can take it as a string, optionally with explicit sign (e.g. +4).

You can output the result value as an integer or a string. If you choose to output as a string (either returning or printing), you can use base 2, 8, 10 or 16. In case of hexadecimal, mixing upper- and lowercase letters are allowed. Base prefixes (e.g. 0b or 0x), leading zeros, and leading/trailing whitespaces are also allowed.

You may use signed 32-bit values for output instead (imagine the values being used in a C program); in that case, the output values will be subtracted by 2^32, except for the input +4.

Scoring

The standard code-golf rules apply. The shortest code in bytes wins.

All test cases

There are only nine possible inputs, so here is the list of all input/output values your program/function needs to support.

input =>  output hex | decimal    | signed 32bit
-4    =>  0xFEDCBA98 | 4275878552 | -19088744
-3    =>  0xEDCBA980 | 3989547392 | -305419904
-2    =>  0xDCBA9801 | 3703216129 | -591751167
-1    =>  0xCBA98012 | 3416883218 | -878084078
 0    =>  0xBA980123 | 3130523939 | -1164443357
 1    =>  0xA9801234 | 2843742772 | -1451224524
 2    =>  0x98012345 | 2550211397 | -1744755899
 3    =>  0x80123456 | 2148676694 | -2146290602
 4    =>  0x01234567 | 19088743   | 19088743

Ruby, 30 bytes

Simple and clean. Outputs a substring of the larger with the right offset because it seemed cheaper than any method I could think of that calculated it properly.

->o{"FEDCBA9801234567"[o+4,8]}

Try it online!


Smallest multiplier that reveals a factor of a semiprime Given a semiprime N, find the smallest positive integer m such that the binary representation of one of the two factors of N can be found in the binary representation of N * m.

Example

Let's consider the semiprime N = 9799.

We try different values of m, starting at 1:

 m |  N * m |   N * m in binary
---+--------+------------------
 1 |   9799 |    10011001000111
 2 |  19598 |   100110010001110
 3 |  29397 |   111001011010101
 4 |  39196 |  1001100100011100
 5 |  48995 |  1011111101100011
 6 |  58794 |  1110010110101010
 7 |  68593 | 10000101111110001
 8 |  78392 | 10011001000111000
 9 |  88191 | 10101100001111111
10 |  97990 | 10111111011000110
11 | 107789 | 11010010100001101

We stop here because the binary representation of the last product contains 101001 which is the binary representation of 41, one of the two factors of 9799 (the other one being 239).

So the answer would be 11.

Rules and notes

Trying even values of m is pointless. They were shown in the above example for the sake of completeness.
Your program must support any N for which N * m is within the computing capabilities of your language.
You are allowed to factorize N beforehand rather than trying each possible substring of the binary representation of N * m to see if it turns out to be a factor of N.
As proven by MitchellSpector, m always exists.
This is code-golf, so the shortest answer in bytes wins. Standard loopholes are forbidden.

Test cases

The first column is the input. The second column is the expected output.

         N |    m |         N * m |                              N * m in binary | Factor
-----------+------+---------------+----------------------------------------------+-------
         9 |    3 |            27 |                                      [11]011 |      3
        15 |    1 |            15 |                                       [11]11 |      3
        49 |    5 |           245 |                                   [111]10101 |      7
        91 |    1 |            91 |                                    10[1101]1 |     13
       961 |   17 |         16337 |                             [11111]111010001 |     31
      1829 |    5 |          9145 |                             1000[111011]1001 |     59
      9799 |   11 |        107789 |                          1[101001]0100001101 |     41
     19951 |   41 |        817991 |                       1[1000111]101101000111 |     71
    120797 |   27 |       3261519 |                     11000[1110001]0001001111 |    113
   1720861 |  121 |     208224181 |               11000110100[100111111101]10101 |   2557
 444309323 |  743 |  330121826989 |    100110011011100110010[1101010010101011]01 |  54443
 840000701 | 4515 | 3792603165015 | 11011100110000[1000110000111011]000101010111 |  35899
1468255967 |   55 |   80754078185 |      1001011001101010100010[1110001111]01001 |    911

05AB1E, 18 16 15 bytes

-2 bytes thanks to Riley!

-1 byte thanks to Emigna!

[N¹*b¹Ñ¦¨båOiNq

Explanation:

[                   # Infinite loop start
 N                  # Push the amount of times we have iterated
  ¹*               # Multiplied by input
    b              # Convert to binary
     ¹Ñ¦¨b         # Calculate the proper divisors of the input in binary excluding one
          åO       # Check if a substring of N * m in binary is in the divisors
            iNq    # If so, print how many times we have iterated and terminate the program

Try it online!


Conversion to Boolean satisfiability Given a matrix M all of whose entries are 0 or 1, we want to known whether there exists a non-zero vector v with each element in {-1, 0, 1}, such that Mv = 0.

An easy way to do this is just to try all possible vectors v. The M is m by n then there are 3n - 1 such vectors.  But of course this is PPCG, so we don't want to do anything so simple!

Instead, this task is to convert the problem into an instance of  Boolean satisfiability problem.

Input

An m by n matrix M written out with one row per line each space separated. The first list has m and n on it, space separated. For example this 3 by 4 matrix M.

3 4
1 1 0 1
0 1 1 0
0 0 1 1

In this case there does not exist a non-zero vector v, all of whose entries are -1,0 or 1 such that Mv = 0.

Output

An instance of 3-SAT in simplified DIMACS format.

The instance of 3-SAT that you output should be satisfiable if and only if there exists a non-zero vector v, all of whose entries are -1,0 or 1 such that Mv = 0.

The file format will be in a simplified version of the DIMACS format using this specification taken from http://www.satcompetition.org/2009/format-benchmarks2009.html

c
c start with comments
c
c
p cnf 5 3
1 -5 4 0
-1 5 3 4 0
-3 -4 0

The file can start with comments, that is lines begining with the character c.
    Right after the comments, there is the line p cnf nbvar nbclauses indicating that the instance is in CNF format; nbvar is the exact number of variables appearing in the file; nbclauses is the exact number of clauses contained in the file.
    Then the clauses follow. Each clause is a sequence of distinct non-null numbers between -nbvar and nbvar ending with 0 on the same line; it cannot contain the opposite literals i and -i simultaneously. Positive numbers denote the corresponding variables. Negative numbers denote the negations of the corresponding variables.

Score

I will test your code on a 20 by 40 matrix and the score will be the total number of non-comment lines in your 3-SAT instance. Smaller is better.

Running time of your code

Your code should take less than 1 minute to run.  I don't want to restrict the languages used but I will attempt to test any code I can run otherwise I will just trust the timing you give.  For small instances you could of course just compute the answer but this won't work for matrices of the size I will test.

More examples

Your 3-SAT instances for the following matrices should be unsatisfiable.

1 1 0 1
0 1 1 0
0 0 1 1

1 1 0 1 0
0 1 1 0 1
0 0 1 1 0
0 0 0 1 1

1 0 0 1 0 1 1 0 0
1 1 0 0 1 0 1 1 0
0 1 1 0 0 1 0 1 1
0 0 1 1 0 0 1 0 1
0 0 0 1 1 0 0 1 0
0 0 0 0 1 1 0 0 1

1 1 0 1 0 0 1 1 1 0 0 1
1 1 1 0 1 0 0 1 1 1 0 0
0 1 1 1 0 1 0 0 1 1 1 0
0 0 1 1 1 0 1 0 0 1 1 1
0 0 0 1 1 1 0 1 0 0 1 1
0 0 0 0 1 1 1 0 1 0 0 1
0 0 0 0 0 1 1 1 0 1 0 0

Your 3-SAT instances for the following matrices should be satisfiable.

1 1 0 1 1 1 0
1 1 1 0 1 1 1
0 1 1 1 0 1 1
0 0 1 1 1 0 1
0 0 0 1 1 1 0

1 0 1 0 0 1 0 0 0
0 1 0 1 0 0 1 0 0
0 0 1 0 1 0 0 1 0
0 0 0 1 0 1 0 0 1
0 0 0 0 1 0 1 0 0
0 0 0 0 0 1 0 1 0

1 0 0 1 1 1 0 1 0 0 1 1
0 1 0 0 1 1 1 0 1 0 0 1
0 0 1 0 0 1 1 1 0 1 0 0
0 0 0 1 0 0 1 1 1 0 1 0
0 0 0 0 1 0 0 1 1 1 0 1
0 0 0 0 0 1 0 0 1 1 1 0
0 0 0 0 0 0 1 0 0 1 1 1

A possible short cut for the busy programmer

One possibly easier route to tacking this problem could be to output Pseudo-Boolean Constraints. See page 6 of http://www.cril.univ-artois.fr/PB12/format.pdf for example. There are then different open source tools and libraries which will convert that to 3-SAT.

OCaml, ≤ 475318

After defining the basic logic gates (I ended up using only AND and OR), I compose them to make a variable for each of the possible partial sums of a row of M and v. A total of O(mn2) variables/clauses are used. This is an initial effort that doesn't make any attempt to simplify the formula. In the worst case (a matrix with no zeroes), it generates 475,318 clauses for a 20x40 matrix.

let rec genlist f n =
    match n with
    | 0 -> []
    | n -> let e = f() in e :: genlist f (n-1)
;;

let numvars = ref 0 ;;
type var = V of int | Const of bool;;
let mkv () = incr numvars; V !numvars;;
type clause = Cl1 of var | Cl2 of var*var | Cl3 of var*var*var ;;
let clauses = ref [] ;;
let req (x:clause) = if x <> Cl1(Const true) then clauses := x :: !clauses ;;
let deref = (!);;
let (!) = function
    | V x -> V (-x)
    | Const c -> Const (not c)
;;

let mkeq (a:var) (b:var) = match a,b with
    | Const true, b -> b
    | Const false, b -> !b
    | a, Const true -> a
    | a, Const false -> !a
    | a,b -> let v = mkv() in
    req@@Cl3 ( !v, a, !b ) ;
    req@@Cl3 ( !v, !b, a ) ;
    req@@Cl3 ( v, a, b ) ;
    req@@Cl3 ( v, !a, !b );
    v
;;

let mkxor a b = ! (mkeq a b) ;;

let mkor (a:var) (b:var) = match a,b with
    | Const false, b -> b
    | Const true, _ -> Const true
    | _, Const true -> Const true
    | a, Const false -> a
    | a,b -> let v = mkv() in
    req@@Cl2 ( v, !a ) ;
    req@@Cl2 ( v, !b ) ;
    req@@Cl3 ( !v, a, b ) ;
    v
;;

let mkand a b = ! (mkor !a !b) ;;

let mkorl l =
    let rec mkorl_ = function
        | a::b::tl -> mkor (mkor a b) (mkorl_ tl)
        | a::[] -> a
        | [] -> Const false
    in mkorl_ (List.filter (function | Const false -> false | _ -> true) l)
;;
let nextsums sums (minus1, zero, plus1) =
    let rec nextsums_ prev sums (minus1, zero, plus1) =
    match sums with
        | cur::next::tl ->
            ( mkorl [mkand minus1 next; mkand zero cur; mkand plus1 prev] ) ::
            ( nextsums_ cur (next::tl) (minus1, zero, plus1) )
        | cur::_ ->
            (mkor (mkand zero cur) (mkand plus1 prev)) ::
            ( nextsums_ cur [] (minus1, zero, plus1) )
        | _ -> [mkand plus1 prev]
    in
    (mkand minus1 (List.hd sums)) ::
    nextsums_ (Const false) sums (minus1, zero, plus1)
;;

let rec entry_zero row v sums maxsum =
    if row=[] then List.nth sums maxsum else
    if List.hd row = 0 then entry_zero (List.tl row) (List.tl v) sums maxsum else
    let (a,b,c) = List.hd v in
    let elemv = if List.hd row = -1 then (c,b,a) else (a,b,c) in
    entry_zero (List.tl row) (List.tl v) (nextsums sums elemv) (maxsum+1)
;;

let req1of3 (a,b,c) =
    req@@Cl2(!a, !b);
    req@@Cl2(!a, !c);
    req@@Cl2(!b, !c);
    req@@Cl3(a, b, c);;

let rdint () = Scanf.bscanf Scanf.Scanning.stdin " %d" (fun x -> x) ;;

let m = rdint();;
let n = rdint();;

let vec = genlist (fun () -> (mkv(), mkv(), mkv()) ) n;;
List.iter req1of3 vec;;

let mat = genlist (fun () -> genlist rdint n) m;;

List.iter (fun row -> req@@Cl1 (entry_zero row vec [Const true] 0) ) mat;;

let nonzeros = List.map (function _,z,_ -> !z) vec ;;
req@@Cl1 (mkorl nonzeros) ;;

exception Bug of string;;
let str_clause (cl:clause) = match cl with
    | Cl1(V a) -> Printf.sprintf "%d 0" a
    | Cl2(V a,V b) -> Printf.sprintf "%d %d 0" a b
    | Cl3(V a,V b,V c) -> Printf.sprintf "%d %d %d 0" a b c
    | _ -> raise @@ Bug "there seems to be";;
let (!) = deref;;

Printf.printf "p cnf %d %d\n" !numvars (List.length !clauses) ;;
List.iter (fun cl -> print_endline (str_clause cl)) !clauses ;;


Tips for golfing in uBasic UBASIC is a freeware basic interpreter written by Yuji Kida at Rikkyo University in Japan, specialized for mathematical computing. It is considered to be a "ready-to-run" language that and is capable of running on DOS and Windows.
What general tips do you have for golfing in uBasic? Any ideas that can be applied to code golf problems in general that are at least somewhat specific to uBasic. Please post one tip per answer.

Some helpful links
uBasic Wikipedia Page
Try it Online

Use ? in place of Print

Instead of using the Print command, ? may be used, as is the case in many BASIC languages - this means that the most simplest uBASIC Hello, World! program is as follows
0?"Hello, World!"

Rather than
10 Print "Hello, World!"

Try it Online!