Golf the Pigeonhole sort Implement the Pigeonhole sort. This is a variant of the Bucket sort, and its logic is very simple: index your items (by a given function) and then return all non-empty indexes' items.

Your program/function should get an array of items in the most comfortable way for your language of choice, (i.e. a parameter, stdin, etc.), and in any format you like (for example: JSON). It should return/output a sorted array.

Do not modify the given array.

The second parameter that will be given to your program/function will be the "sort-by function". For exmaple, in JavaScript it will be something like function(item){return item.id;}.

For simplicity, you can assume this function returns a unique positive Integer for each item in the given array.

Shortest code wins. Only ASCII is allowed.

Ruby, 43

def s a,*b,&f
a.map{|x|b[f[x]]=x}
b-[p]
end

Calling looks like

p s(["a","ccc","bb","eeeee"],&:length)
  -> ["a", "bb", "ccc", "eeeee"]

Tricks: *b in the arg list creates an empty output array (so long as you don't, y'know, pass any args). &f creates a lambda reference to the passed-in block that can be called via f[] (normal Ruby convention is to use yield). a.map iterates over the input array without modifying it and is one character shorter than a.each. b-[p] strips out the nil values, equivalent to b.compact.


Interlocking Brackets Write a program or function that takes in an eight byte string containing one of each of the characters ()[]{}<> arranged in any way such that the four respective bracket types match. For example, ]<([){}> is invalid input because the square brackets don't match (though all the others do).

Print or return an integer from 0 to 6 that denotes how many of the six possible pairings of the four bracket types are interlocked. Bracket type pairs are considered interlocked if exactly one bracket of one type occurs between the brackets of the other type. So ([)] and [(]) are interlocked but ()[], [](), ([]), and [()] are not.

The shortest code in bytes wins.

Input/Output Examples

()[]{}<> : 0
([{<>}]) : 0
<>{[]}() : 0
{<>([])} : 0
<(>)[{}] : 1
<[({)}]> : 1
[{<}]>() : 2
{<>([}]) : 2
<{(>})[] : 3
[(]<){>} : 3
<([>{)}] : 4
(<{[>})] : 4
(<[{)>}] : 5
<{[(>})] : 5
[{<(]}>) : 6
(<{[)>}] : 6

CJam, 18

l7~f&_f{\/~;&}s,2/

Thanks isaacg for some golfing ideas :)
Try it online or try all examples

Explanation:

l         read a line of input
7~f&      clear the lowest 3 bits of each character
           the goal is to convert brackets of the same type to the same char
_         duplicate the resulting string, let's call it S
f{…}      for each character in S, and S (the char and S are pushed every time)
  \       swap the character with S
  /       split S around that character, resulting in 3 pieces:
           before, between, after
  ~       dump the pieces on the stack
  ;       pop the last piece
  &       intersect the first 2 pieces
          after the loop, we have an array of strings
          containing the chars interlocking to the left with each char of S
s         join all the string into one string
,         get the string length
2/        divide by 2, because S has duplicated characters


How long should my microwave run? I'm hungry. Let's microwave something. Given a numerical input of between 1 and 4 digits, output the number of seconds that the microwave should run.
Details
The trick is figuring out if the user is inputting seconds or a combination of seconds and minutes. The ones and the tens places should be interpreted as seconds and the hundreds and thousands places should be minutes. For example, the value 1234 should be interpreted as 12 minutes, 34 seconds and 9876 should be 98 minutes, 76 seconds. Typing 130 and 90 should both result in a cook time of 90 seconds.
Here are a few other inputs and outputs:

1 = 1
11 = 11
111 = 71
1111 = 671
9 = 9
99 = 99
999 = 639
9999 = 6039

Rules
This is code-golf, so the shortest program in bytes wins. Standard loopholes are not allowed. The winning entry must return the right answer when given any integer input from 1 to 9999.

Python 2, 19 bytes

lambda t:t-t/100*40

Try it online!


Wait, but what's e^N? Objective:

The objective is to calculate e^N for some real or imaginary N (e.g. 2, -3i, 0.7, 2.5i, but not 3+2i). This is code golf, so, shortest code (in bytes) wins.

So, for example:

N = 3, e^N = 20.0855392
N = -2i, e^N = -0.416146837 - 0.9092974268i

The letter i shouldn't be capitalized (since in math it is lowercase)

If your language supports raising numbers to complex numbers, you can't use that. You may use built-in real exponentiation.

For any answer where b (in a + bi) is negative, it is OK to have both the plus and minus sign (e.g. 2 + -3i), since that is understood to be (2 - 3i)

Bonus (-15 bytes): Solve this for N is a any complex number (e.g. 5 + 7i). If you are going for the bonus, you can assume that both components will always be given (even for the standard objective)

CJam, 22 - 15 = 7
l~_mc\ms@me:X*\X*'+@'i

Try it online here
Takes input in the form of a b where a is the real component and b is the complex.
For ex. 2i is
0 2

gives
-0.4161468365471424+0.9092974268256817i


Truth Tables: Your great-grandfather's computer If you remember back to your schooling years, you might remember learning about Truth Tables. They seemed boring, but they are basis for logic and (some would argue) all computing...

Problem

Your mission, should you choose to accept it is to write a program, function, or widget of code that can output a truth table given input.

Input

Input will be a string (like data structure) containing the logic statement to make the Truth Table into. For example:

p ∧ q

This means p and q(logical conjuction) and will output:

 p  q  p ∧ q
 T  T    T
 T  F    F
 F  T    F
 F  F    F

Notice the spacing: The item of the column is in the center of the header

Characters

Score via characters, not bytes
The logic comparison characters are special and not always what they look like. Use these characters:

Logical Conjunction (AND): ∧ U+2227

Logical Disjunction (OR): ∨ U+2228

Logical Negation (NOT) ~ or ¬ U+7e and U+ac respectively

Bonuses

All of these bonuses are optional, but will knock points off your score. Pick any.

Logical Negation

Logical Negation is a unary operator in truth tables. It is the equivalent of ! in most C-based languages. It makes false=>true and vise versa. It is notated with a ¬ or ~ (you must support both). Supporting this will knock off 10% of your score. You must, however, add an additional column to show its results:
For example:

~p ∧ q

will output:

p  ~p  q  ~p ∧ q
T  F   T     F
T  F   F     F
F  T   T     T
F  T   F     F

Pretty Print

The normal table notation is boring. Let's make it pretty! Pretty print format is as follows for p ∧ q is as follows:

+---+---+-------+
| p | q | p ∧ q |
+---+---+-------+
| T | T |   T   |
+---+---+-------+
| T | F |   F   |
+---+---+-------+
| F | T |   F   |
+---+---+-------+
| F | F |   F   |
+---+---+-------+

Special details for pretty printing:

There is a 1 space padding in each cell
Cell values are still centered

If you pretty print your tables, from your code and then multiply by 0.6. Use this function for this bonus:

score = 0.6 * code

Examples

p ∧ q:

p  q  p ∧ q
T  T    T
T  F    F
F  T    F
F  F    F

p ∨ q:

p  q  p ∨ q
T  T    T
T  F    T
F  T    T
F  F    F

~p ∧ q:

p  ~p  q  ~p ∧ q
T   F  T     F
T   F  F     F
F   T  T     T
F   T  F     F

~p ∨ q:

p  ~p  q  ~p ∧ q
T   F  T     T
T   F  F     F
F   T  T     T
F   T  F     T

Rules

Standard loopholes apply
No external resources
If you're going to break the rules, be clever ;)

Shortest Code (in characters) wins. Good Luck!

JavaScript (ES6), 141

Simple function, no bonus, 141 chars. (140 uft8, 1 unicode wide)

Complex function handling ~ or ¬, 254 chars (253 utf, 1 unicode wide), score 229

Could save 6 bytes using alert instead of console.log, but alert is particularly unfit to display tables.

Test running the snippet below in an EcmaScript 6 compliant browser (tested with Firefox. Won't work in Chrome as Chrome does not support .... Also, the bonus version use an extension of split that is Firefox specific).

/* TEST: redirect console.log into the snippet body */ console.log=x=>O.innerHTML+=x+'\n'

// Simple
F=s=>{[a,o,b]=[...s],z='  ',r=a+z+b+z+a+` ${o} ${b}
`;for(w='FT',n=4;n--;r+=w[c]+z+w[e]+z+z+w[o<'∧'?c|e:c&e]+`
`)c=n&1,e=n>>1;console.log(r)}

// Simple, more readable
f=s=>{
   [a,o,b]=[...s]
   r=a+'  '+b+'  '+a+` ${o} ${b}\n`
   for(w='FT',n=4; n--; )
   {
     c = n&1, e = n>>1, x=o<'∧' ? c|e : c&e
     r += w[c]+'  '+w[e]+'    '+w[x]+'\n'
   }
   console.log(r)
}

// 10% Bonus
B=s=>{[a,o,b]=s.split(/([∧∨])/),t=a>'z',u=b>'z',z='  ',r=(t?a[1]+z:'')+a+z+(u?b[1]+z:'')+b+z+a+` ${o} ${b}
`;for(s=v=>'FT'[v]+z,n=4;n--;r+=s(c)+(t?s(d)+' ':'')+s(e)+(u?s(f)+' ':'')+(t?'   ':z)+s(o<'∧'?d|f:d&f)+`
`)c=n&1,d=c^t,e=n>>1,f=e^u;console.log(r)}

Test1 = ['q∨p','q∧p']
Test2 = Test1.concat([
  '~q∨p','q∨~p','~q∨~p','~q∧p','q∧~p','~q∧~p',
  '¬q∨p','q∨¬p','¬q∨¬p','¬q∧p','q∧¬p','¬q∧¬p'
])

console.log('SIMPLE')
Test1.forEach(t=>F(t));

console.log('BONUS')
Test2.forEach(t=>B(t));


Read a crossword with a twist! Similar to this question, but this is a crossword variation!

Instead of only one letter per grid square, you can have one or two.

Input:

A 2d array, or whatever works in your language.
You can assume valid inputs
Any array size must work

Output:

An array of all the words

Across and down
All words must be joined together, i.e. linked in an unbroken chain of words (if not return false)
Words must be at least two grid squares, not letters

Example:

[["",  "wo", "r",  "k"],
[ "",   "r",  "",   ""],
[ "he", "l",  "lo", ""],
[ "",   "d",  "ad", ""]]

Returns:

["work", "world", "hello", "load", "dad"]

Example:

[["he", "ll", "o"],
[ "",   "",   ""],
[ "wo", "r",  "ld"]]

Returns:

false

This is fastest-code, so I'll be running this on windows 7 with 2.5ghz and 16gb of ram. If your code is really esoteric, provide a link to the compiler so I can actually run it.

Python 3

import numpy
from scipy.ndimage import measurements

def crosswords(arr):
    M=numpy.asarray(arr)
    # check connectivity
    if measurements.label(numpy.where(M!='',1,0))[-1] != 1:
        return 'false'

    words = []
    def get_words(mat):
        for r in mat:
            word,counter='',0
            for c in r:
                if c=='':
                    if counter>1:
                        words.append(word)
                    word, counter = '', 0
                else:
                    word, counter = word+c, counter+1
            if counter > 1:
                words.append(word)
    get_words(M)
    # transpose M
    get_words(M.T)
    return words

Usage:

Function takes an array of array of strings as input:

crosswords(
[["",  "wo", "r",  "k"],
[ "",   "r",  "",   ""],
[ "he", "l",  "lo", ""],
[ "",   "d",  "ad", ""]])

Returns the string false when connectivity returns multiple labels.
Returns array of valid words otherwise.

I timed it with timeit, time.time() and using the console command time and but I don't know which one to use or which one to post here.


Tree traversal: Depth-first search Write the shortest code that traverses a tree, depth-first.

Input

Any programmatical structure found in your language of choice: lists, tuples, queues etc.

Output

A list of "names" of the nodes in correct order as shown in Depth-first search article at Wikipedia.

Haskell — 70 characters

data N a=N{v::a,c::[N a]}
d n=f[n][]
f(x:y)=f(c x++y).(++[v x])
f _=id

In a more readable format:

data Node a = Node {value::a, children::[Node a]}

dfs :: Node a -> [a]
dfs node = dfs' [node] []
  where dfs' [] result = result
        dfs' (x:xs) result = dfs' (children x ++ xs) (result ++ [value x])

Sample tree:

sampleTree =
    Node 1 [Node 2 [Node 3 [Node 4 [],
                            Node 5 []],
                    Node 6 []],
            Node 7 [],
            Node 8 [Node 9 [Node 10 [],
                            Node 11 []],
                    Node 12 []]]

Sample run:

*Main> dfs sampleTree
[1,2,3,4,5,6,7,8,9,10,11,12]


Chop off the matrix to get the desired sum Definition
Given a matrix \$M\$ of non-negative integers and a non-negative integer \$k\$, we define \$F_k\$ as the "chop-off" function that removes all rows and all columns in \$M\$ that contain \$k\$.
Example:
$$\begin{align}M=\pmatrix{\color{red}6&\color{red}1&\color{white}{\bbox[red,1pt]{5}}\\1&2&\color{red}8\\\color{red}9&\color{red}8&\color{white}{\bbox[red,1pt]{5}}\\6&0&\color{red}4}\\\\F_5(M)=\pmatrix{1&2\\6&0}\end{align}$$
Your task
Given \$M\$ and a target sum \$S\$, your task is to find all possible values of \$k\$ such that the sum of the remaining elements in \$F_k(M)\$ is equal to \$S\$.
Example:
Given the above matrix \$M\$ and \$S=9\$:

\$k=5\$ is a solution, because \$F_5(M)=\pmatrix{1&2\\6&0}\$ and \$1+2+6+0=9\$
\$k=1\$ is the only other possible solution: \$F_1(M)=\pmatrix{5\\4}\$ and \$5+4=9\$

So the expected output would be \$\{1,5\}\$.
Clarifications and rules

The input is guaranteed to admit at least one solution.
The sum of the elements in the original matrix is guaranteed to be greater than \$S\$.
You may assume \$S>0\$. It means that an empty matrix will never lead to a solution.
The values of \$k\$ may be printed or returned in any order and in any reasonable, unambiguous format.
You are allowed not to deduplicate the output (e.g. \$[1,1,5,5]\$ or \$[1,5,1,5]\$ are considered valid answers for the above example).
This is code-golf.

Test cases
M = [[6,1,5],[1,2,8],[9,8,5],[6,0,4]]
S = 9
Solution = {1,5}

M = [[7,2],[1,4]]
S = 7
Solution = {4}

M = [[12,5,2,3],[17,11,18,8]]
S = 43
Solution = {5}

M = [[7,12],[10,5],[0,13]]
S = 17
Solution = {0,13}

M = [[1,1,0,1],[2,0,0,2],[2,0,1,0]]
S = 1
Solution = {2}

M = [[57,8,33,84],[84,78,19,14],[43,14,81,30]]
S = 236
Solution = {19,43,57}

M = [[2,5,8],[3,5,8],[10,8,5],[10,6,7],[10,6,4]]
S = 49
Solution = {2,3,4,7}

M = [[5,4,0],[3,0,4],[8,2,2]]
S = 8
Solution = {0,2,3,4,5,8}

K (ngn/k), 39 bytes

{a@&y=x{+//x*(&/'b)&\:&/b:~x=y}/:a:,/x}

Try it online!

thanks @Adám for this explanation:

{…} function, x is M and y is S

 ,/x flatten M (these are the k candidates)

 a: assign to a

 x{…}/: apply the following function to each while using M as fixed left argument (x):

  x=y Boolean matrix indicating where elements of M equal the current k candidate

  ~ negate that

  b: assign that to b

  &/ AND reduction (finds columns without that k)

  (…)&\: AND that with each of the following:

   &/'b AND reduction of each (finds rows without that k)

  x* multiply M by that

  +// grand sum

 y= list of Booleans indicating where S equals those sums

 & indices of Trues

 a@ use that to index into the elements (the k candidates)


Compiled quine variant Thinking about various quine puzzles here, I got an idea for another one:

Compose a program that outputs its own compiled code to a file (or multiple files, if the compiled code is). (This means that only compiled languages are eligible.)

Rules

Standard quine rules - no cheating allowed. In particular:

The program cannot read the compiled code from disk, cannot store it somewhere etc. It must compute it somehow without external help.
If the program is compiled to several files (i.e. several Java .class files), it must output them all.
You can use any existing libraries available for your language. However:

The libraries you use cannot be something created just for this task. (For example in order to keep some information away from what's considered to be the program.)
Any libraries you use must be older than your program. You cannot just create a program that loads a piece of data from an external library, compile the program, and copy the compiled code into the library - that'd be cheating.
You cannot embed a compiler of your language in any form. In particular, you cannot just take a standard quine and hook it up with a compiler to produce the compiled output.

As mentioned, only compiled languages are eligible. You can use a scripting language as long as it can be compiled to a bytecode that's reasonably different from the source form (if you're not sure, better ask).

Notes

Most likely, this puzzle can be solved reasonably only in languages that compile to some sort of bytecode that can be manipulated. For example, Java and compiled bytecode seems good for the task. (But if you find a genuine solution in some other compiled language, that's fine too, as long as it isn't some sort of cheating.)

Submission

Don't submit the compiled program (as this could be potentially dangerous). Instead post your sources and a description what to do to create the final program.

Evaluation

Let voters decide the best solution. Personally I'd appreciate solution that are elegant, short (in their source form) and didactic - that explain what's going on.

Bonuses

Bonus points for

Let the program output a compressed file containing its compiled code. This has the additional benefit that if the program is compiled into more files, the output will be a single packed file. For example, in Java try to create an executable JAR file that outputs the JAR itself.
Outputting the MD5 sum of the compiled file(s) - so the program would write its compiled code and its MD5 sum.

Assembly (DOS .com file)

start:

%rep 2
    call $+3

    mov ah, 9
    mov dx, 100h + (end - start) / 2
    int 21h

    mov ah, 2
    mov dl, "$" - 1
    inc dx
    int 21h

    ret
    db "$"

%endrep

end:

Assemble with nasm quine.asm -o quine.com. Try with dosbox quine.com.

Proof of correctness (you can also verify by the smilies here):


Who can escape the Nonary Game? The Nonary Game is a fictional game played in the video game trilogy of the same name. Your goal is to find how many players (at best) can escape a given game, in as few bytes of code as possible.

Rules of the game

There are 9 players, numbered 1 to 9.
All players start in the same room.
There are any number of doors, each one with a 1 to 9 number. There may be duplicate or missing door numbers.
Door are one-way connections between rooms. Each door can only be used once.
Only groups of 3 to 5 players can go through a door.
A group can only go through a door if the sum of their numbers modulo 9 matches the door’s number modulo 9.
Any player who goes through a 9 door escapes (wins).

Examples

┌───┬───┬───┐
│   6   4   9
│ < │   |   |
│   3   5   9
└───┴───┴───┘

< represents the starting point. All players start there.

In this setting, everybody can escape. There are various ways to achieve this, one of which is:

[1, 2, 3, 4, 5] go though door 6 ((1+2+3+4+5) % 9 = 6), while [6, 7, 8, 9] go through door 3 ((6+7+8+9) % 9 = 3). Everybody meets up in the second room.
[1, 2, 3, 7] go through door 4, while [4, 5, 6, 8, 9] go through door 5.
[1, 2, 3, 4, 8] go through one of the 9 doors, [5, 6, 7, 9] go through the other one.

┌───┬───┐
│   │   |
│ < 8   9
│   │   |
└───┴───┘

This time, at most 4 people can escape:

[1, 3, 5, 8, 9] go through door 8.
[1, 3, 5, 9] go through door 9.

Other lists of survivors are possible, such as [2, 3, 4] or [1, 4, 6, 7], but there's no way for more than 4 people to escape.

The challenge

Given a map, output the maximum numbers of player who can escape.

Don’t worry, you don’t need to parse my awful diagrams! Input is a labeled directed graph, which you can represent in any convenient format (edge set, adjacency matrix...).
If your representation requires labels for rooms, you can use any consistent set of values. However, doors must be represented by the integers 1 to 9.
The input will always have at least one 9 door. All 9 doors always lead to the exit, while other doors never do.
Your submission can be a function or full program.
Standard loopholes are banned.

Test cases

Inputs are shown as lists of [door number, from room, to room] triplets, with 0 being the starting room and -1 being the exit. If you choose to use another format, you’ll have to convert them appropriately.

Input                                                                      Output
[[6, 0, 1], [3, 0, 1], [4, 1, 2], [5, 1, 2], [9, 2, -1], [9, 2, -1]]       9
[[8, 0, 1], [9, 1, -1]]                                                    4
[[9, 0, -1]]                                                               5
[[2, 0, 1], [1, 1, 2], [9, 2, -1]]                                         0
[[2, 0, 1], [3, 1, 2], [9, 2, -1]]                                         3
[[1, 0, 1], [9, 1, -1], [1, 0, 2], [9, 2, -1]]                             4
[[2, 0, 1], [3, 0, 1], [5, 1, 2], [4, 0, 2], [9, 2, -1], [9, 2, -1]]       8
[[3, 0, 1], [4, 0, 1], [5, 0, 1], [9, 1, -1], [7, 1, 2], [9, 2, -1]]       7
[[1, 0, 1], [2, 0, 1], [4, 0, 1], [9, 1, -1], [8, 1, 2], [9, 2, -1]]       6
[[6, 0, 1], [7, 0, 1], [9, 1, -1], [9, 1, -1]]                             7

JavaScript (ES6), 219 bytes
A slower but significantly shorter version using bitmasks instead of strings.

f=(D,P=[511],e=m=0)=>P.map((X,r)=>[...Array(-~X)].map((_,p)=>D.map(([d,s,t],j)=>(N=(g=(n,k)=>n&&n%2+g(n>>1,++k,x+=n%2*k))(p&=X,x=0))<3|N>5|r-s|x%9^d%9||f(D.filter(_=>j--),A=[...P],e+!~t*N,A[r]^=p,A[t]^=p))),m=m>e?m:e)|m

Try it online!
NB: The reason why it's slower is that we do not compute the powersets of the players. Given a bitmask of players \$X\$, we iterate on all \$(X \operatorname{AND} p)\$ for \$0\le p\le X\$ without deduplicating.

JavaScript (ES7),  293 272  271 bytes
Takes input in the format described in the challenge. This is a brute force search.

f=(D,P=[17**6+'8'],e=m=0)=>P.map((X,r)=>X&&[...X].reduce((a,x)=>[...a,...a.map(y=>y+x)],['']).map(p=>D.map(([d,s,t],j)=>p<99|p[5]|r-s|eval([...p].join`+`)%9^d%9||f(D.filter(_=>j--),A=[...P],e+!~t*p.length,A[r]=X.replace(eval(`/[${p}]/g`),''),A[t]=[A[t]]+p))),m=m>e?m:e)|m

Try it online! (the first test case times out on TIO)
How?
The array P[] holds a list of strings describing the players in each room.
We start with P=['241375698'] (using \$17^6=24137569\$), which means that all players are initially located in room \$0\$.
For each room X at position r, we compute the powerset of X:
[...X].reduce((a, x) => [...a, ...a.map(y => y + x)], [''])

For each group of players p in there and for each door [d,s,t] at index j, we test if the group is unable to pass through the door:
                         // we can't pass if:
p < 99 |                 // there are less than 3 players
p[5] |                   // or there are more than 5 players
r - s |                  // or the source room s is not equal to the current room
eval([...p].join`+`) % 9 // or the sum of the players modulo 9
^ d % 9                  // does not match the ID of the door modulo 9

If the group can pass, we do a recursive call:
f(                       //
  D.filter(_ => j--),    // remove the door that has just been used from D[]
  A = [...P],            // use a copy A[] of P[]
  e + !~t * p.length,    // if t = -1, add the length of p to e (number of escaped guys)
  A[r] = X.replace(      // remove the players from the source room A[r]
    eval(`/[${p}]/g`),   //
    ''                   //
  ),                     //
  A[t] = [A[t]] + p      // and append them to the target room A[t]
)                        //

We keep track of the maximum number of escaped players in m and eventually return it.


Triangular Dependencies A triangular number is a number that is the sum of n natural numbers from 1 to n. For example 1 + 2 + 3 + 4 = 10 so 10 is a triangular number.

Given a positive integer (0 < n <= 10000) as input (can be taken as an integer, or as a string), return the smallest possible triangular number that can be added to the input to create another triangular number.

For example given input 26, adding 10 results in 36, which is also a triangular number. There are no triangular numbers smaller than 10 that can be added to 26 to create another triangular number, so 10 is the correct result in this case.

0 is a triangular number, therefore if the input is itself a triangular number, the output should be 0

Testcases

Cases are given in the format input -> output (resulting triangular number)

0     -> 0   (0)
4     -> 6   (10)
5     -> 1   (6)
7     -> 3   (10)
8     -> 28  (36)
10    -> 0   (10)
24    -> 21  (45)
25    -> 3   (28)
26    -> 10  (36)
34    -> 21  (55)
10000 -> 153 (10153)

Scoring

This is code-golf so fewest bytes in each language wins!

Java 8, 58 57 bytes

n->{int i=0,m=0;while(n!=0)n+=n<0?++i:--m;return-~i*i/2;}

Online test suite

Thanks to Dennis for a 1-byte saving.


Jelly, 2 bytes

_Ṣ

Try it online!

or Try all test cases

_   # Subtract from...
 Ṣ  # The input array sorted


Shortest Program To Find Lowest Common Ancestor of Two Nodes in a Binary Tree Any two separate nodes in a binary tree have a common ancestor, which is the root of a binary tree. The lowest common ancestor(LCA) is thus defined as the node that is furthest from the root and that is the ancestor of the two nodes.

The following are binary trees and the lowest common ancestors of the some of their nodes.

The LCA of 13 and 15 is 14.

The LCA of 47 and 49 is 48.

The LCA of 4 and 45 is 40.

The LCA of 13 and 14 is 14.

The LCA of 15 and 47 is 40.

Challenge

Write the shortest program possible that accepts as input the root of a binary tree and references to any two nodes in the binary tree. The program returns a reference to the LCA node of the two inputted nodes.

Assumption

Assume there is a least common ancestor present for any two nodes in the binary tree.

Input

The root of a binary tree and references to any two nodes in the binary tree that the lowest common ancestor must be found for. The root of the binary tree may be in the form of a reference to the root object or even a list that is a valid representation of a binary tree.

Output

If using a pointer-based representation of a tree returns a reference to the node that is the LCA of the two inputted nodes.

If using a list representation returns the node_id for the lowest common ancestor of the two inputted nodes.

Definition of a Binary Tree

A tree is an object that contains a value and either three other trees or pointers to them.

The structure of the binary tree looks something like the following:

typedef struct T
{
   struct T *l;
   struct T *r;
   struct T *p; //this is the parent field
   int v;
}T;

If using a list representation for a binary tree and since certain node values in the binary tree may reappear, the list representation must have an additional node_id parameter that looks something like this:

[[node_id,node_value],left_tree, right_tree, parent_tree]

R with ape package, 12 bytes

ape::getMRCA

Built-in. Called as ape::getMRCA(tree, c(node1, node2)).


Regex for multiples of 9 It is easy to describe a finite state machine that recognizes multiples of 9: keep track of the digit sum (mod 9) and add whatever digit is accepted next. Such a FSM has only 9 states, very simple! By the equivalence between FSM-recognizability and regular languages, there is a regular expression for multiples of 9. However, any such regular expression is likely... very... long. As in, likely on the order of a gigabyte.

There is a worked example at https://www.quaxio.com/triple/ for multiples of 3. At the bottom of the page, the author provides a somewhat "hand-optimized" solution that's a bit shorter than the naive conversion from FSM to regex.

The challenge:

You must make a regex to detect multiples of 9. Since such a regex is expected to be very long, I ask that you provide a program that can print out your regex. (If you really want to give a whole regex, perhaps host it elsewhere and link it here!)

You must be able to tell us the exact character count of your program's output -- so having a program that simply tries all regexes up to a certain length, until it finds one that works, is not acceptable unless it runs quickly enough that you can run it to completion and give us the resulting regex length!

Points are for having the shortest output regex, not based on program length, of course. Since the regex is the "program" I am asking for, and it's just too long to conveniently transmit here, I'm still tagging this code-golf.

Rules:

The input will only include characters matching [0-9]*.
Your regex should match multiples of 9, but not anything else. Cases that aren't made entirely of the digits 0-9 and are invalid inputs can either match or fail as you wish.
Given the motivation that it's easily recognized by a DFA, the resulting regex must actually be regular expression in the more theoretic terminology, that is, only operators under which regular languages are closed. To be precise, the only things that are allowed:

Literals, character ranges ([ab], [a-f], [^k]), Kleene star (*), anchors (^ and $), grouping via parentheses, alternation (|), optional terms (?), one-or-more terms (+), lookaheads ((?=)), negative lookaheads ((?!)), lookbehinds ((?<=)), negative lookbehinds ((?<!)), conditionals (as in https://www.regular-expressions.info/conditional.html -- (?(?=test)then|else) ), and backreferences of bounded length (see below).

Examples of things that are not allowed:

Backreferences of arbitrary length, forward references, Recursion, subroutines, looping constructs, executable code, any variation of 'eval', or built-in constructs for casting the string to an arithmetic value.

Backreferences that can be shown to have a bounded-length binding string are acceptable, as they can be stored in finite state and do not alter the regularity of the language. For instance, the regex (..2.[3-5])4\1.\1 is acceptable, as there is bound length on the capturing group \1. This is a regular construction. A construct such as (2*)0\1 is not acceptable, as the captured group cannot be stored in finite state.
Your regex is free to accept or reject integers with extraneous leading zeroes as you wish. However, the string "0" must be accepted.

Haskell, 207,535 202,073 bytes

5,462 bytes saved by using 0|9 instead of [09] where possible.

digits n
  | x == 0    = "0|9"
  | otherwise = show x
  where x = mod n 9

regex 0 = "[09]*"
regex n = (regex' n (-1) (-1)) ++ "*"

regex' 0 start end = digits (end - start)
regex' n start end = '(':(regex' 0 start end) ++ (concat ['|':(regex' (n-x) (start-x) (-1)) ++ (regex (n-x))
                                                  ++ (regex' (n-x) (-1) (end-x)) | x <- [1..n]]) ++ ")"

main = do
  putStr ("^" ++ (regex 8) ++ "$")

Try it online!

Just a quick adaptation of the regex given in the footnotes of the linked article to get things started.

Pastebin of output regex, courtesy of Herman Lauenstein.

While I have not been able to test the full regex, modifying the program to check divisibility by 3 instead gives something exactly equivalent to the regex I based this on.  Furthermore, modifying the program to check the digit sum's divisibility by 4 or 5 also seems to work on the numbers I tested it on.


Standard atmosphere properties The International Standard Atmosphere (ISA) is a model of the Earth's atmosphere at "reference" conditions. It includes information on pressure, temperature, and density change vs. altitude.

The ISA tabulates these properties at various layers, and an estimation of the value of interest can by found by the following procedure:

Find the highest layer A which has a base altitude lower than or equal to the altitude of interest.
Linearly interpolate between layers A and A+1 to find the properties at the altitude of interest.

For example, suppose you want to find the temperature at a geometric altitude above MSL of 40000m. Thus, A=3, and the temperature is (in degrees C):

T = (-2.5+44.5)*(40000-32000)/(47000-32000)-44.5 = -22.1

The goal of this challenge is given a geometric altitude above MSL, find the standard temperature, pressure, and density at that altitude.

For the purposes of this challenge, use the table of the 1976 ISA model (presented on Wikipedia). Here is a link a Gist containing the data in CSV format. Note that the CSV file includes the missing density values from Wikipedia's page.

Input

The input is a single finite real number representing the geometric altitude above MSL in meters. This number is guaranteed to be between [-611,86000) (i.e. it is greater than or equal to -611, and is strictly less than 86000).

The input may come from any source desired (function input, stdio, etc.)

Output

The output are the 3 real numbers representing the standard temperature, pressure, and density at the input altitude. The answer should be accurate to within 0.1%. The answer may be in order desired, as long as it is obvious which value represents which quantity (ex.: the first number is always temperature, the second number is always density, and the third number is always pressure). Note that the magnitude of the quantity does not count as make it obvious what the value represents.

You are welcome to choose any units to output your answers in as long as they properly describe the quantity of interest. Ex.: you may output temperature in degrees Fahrenheit, Celsius, Kelvin, etc., but you can't output the temperature in meters. Your code does not need to output the units abbreviation if it is always the same for a given quantity, but you should specify in your answer what units your answer uses.

The output may be to any sink desired (stdio, return value, output parameter, etc.).

Examples

All examples use meters for input, and output in the order temperature (C), pressure (Pa), density (kg/m^3).

-611
19, 108900, 1.2985

0
15.0335, 104368, 1.24943

12000
-56.5, 20771, 0.333986

47350
-2.5, 110.91, 0.0014276

71803
-58.502, 3.95614764, 6.42055e-5

Scoring

This is code golf; shortest answer in bytes wins. Standard loopholes are prohibited. You may use any built-ins desired. If you are using any external resources to store the tabulated data, you must include the size of the resource (in bytes) as read into your program as part of your score.

Ex.: Say you read in a compressed version of the CSV table I linked which is 100 bytes long (uncompressed is 333 bytes), and your code is 126 bytes long. Then your net score is 100+126=226.

MATL, 152 bytes
'!Q%:5-aeo\!=XBf=H]3|X"Pj7#UGj{r_DH&!+.eFc;u4 kG9Q[rQA(^D1dW- @[E8{Ul0!AXC|MDi8}:&D(j&1_zMU.`[^HQvWoi5}*1UApz %Ld3A)N<$A*7!wBgm'F4Y2'- .;e'hZaU1&Z)i&1Yn

Output is in the same order as described in the challenge
Try it online! Or verify all test cases.
Explanation
Most of the code, '!Q%:5...!wBgm', is a compressed string containing the table. F4Y2'- .;e'hZa decompresses this into the string -611 19 ... 6.961e-6. Note that some decimals have been removed, as they are not needed to fulfill the 0.1% accuracy criterion.
The decompressed string is interpreted as an array with U. This produces the 8×4 table with the required data. The first column shown in the challenge is not needed. Then 1&Z) separates the first column from the rest.
i takes a number as input, and &1Yn applies linear interpolation using the three types of data: first column of the table, remaining columns, input. The result of the interpolation is implicitly displayed.
The input can also be a column vector, and then each row of the output refers to one of the input values. This is used for verifying all test cases at once.


Tips for golfing in J GolfScript gets its own way far too often and I feel that a repository of handy hints for golfing in J might help in the fight against the evil empire. What tips do you have for making this already terse language shorter?

For those wanting to learn J, the obvious place to begin is the jsoftware site and particularly the vocabulary, the Learning J guide and the J for C programmers guide.

There are a number of subtleties to squeezing out the last few characters in J. For the following, assume that each capital letters is a primitive verb (i.e. I am removing the spaces that would otherwise be required to delimit names).

When you have a train going, and you need to apply a function atop another partway through, ([:FLGR) and (LF@:GR) have the same number of characters, but (LF@GR) saves one. If the frame of G is greater than or equal to the monad rank of F, this is a valid transformation. Notably, all trains have infinite rank, as do , ,. ,: ~. /: \: [ ] and most uses of # and |..
If you have to pick strings out of a list, and these strings have no spaces, use >i{ab`cd`ef. It's dirty, but it saves characters for each new string you have to deal with, unless you're just pulling single characters, and even then the charlist has to be length 4 to be shorter. What's happening is that undefined names are treated as references to verbs, and when you take the gerunds of those verbs you get a boxed string of the name. Any names that are already defined as having type noun, adverb, or conjunction cannot be used in this fashion, because those names get resolved before ` can have at them.
If you're lucky enough to have an expression to work with and not just a tacit verb, it's almost always worth it to assign any bits you reuse to variables, be they nouns, verbs, or adverbs. The parens will sometimes pay themselves back by fitting right into where you had spaces before, and most such definitions are worth it if they're reused even once more.
Conjunctions like (FGH)^:(u`v`w) can be rewritten u`v`w(FGH^:). This works for any length of train, even 1, though you only save anything if this trick removes parens from the right argument. This trick only works when you preload the left operand. (Have no idea what just happened? Look up 'tacit adverbs', and study the Parsing and Execution section of the J Dictionary.)
Don't use a.&i., use u:! {&a. and 3&u: are equivalent on length, though, and the former might be more useful in a conjunction (depending on the conjunction).
Things like (2%~F) and (F%2:) are equivalent in length. This is useful because sometimes, depending on what the rest of your train looks like, you can restructure it with @ tricks as written in the first point, to save some desperate characters. (And of course, if F is ] and the train is a monad, using %&2 saves a char, duh.)
Hook-like trains with ] or [ as the leftmost verb, e.g. (]FGH).

] lets you break up a dyadic application and use the right argument only. (Swap to left with (]FGH)~, at a penalty of at least 1 character, maybe more.) Saves a char over (FGH)@], and is very handy in gerunds!
[ in a hook applied monadically allows you to do something for the side effects on the right side, then return the argument again. Most common usage is with 1!:2, possibly with formatting junk.

I/O sucks. Speed up the process by making loops out of everything you can. 1!:1 has rank 0, and both of 1!:2 3 have rank _ 0, for example, so utilise this by making arrays of 1s and run 1!:1 directly over them. Note that ". also has rank 1, so you can usually just put that directly after 1!:1, too, and not have to attach it via @ or rank shenanigans.
It's not easy to find places to put this, but :: can be useful.

::]^:_ is a particularly powerful combination, for example, that lets you do something dangerous until you can't do it anymore. (Subject to the usual ^:_-as-a-loop caveats.)
This also lets you use { on lists that don't have the desired index, because it throws a domain error when that happens. Useful to e.g. take the head of a list only if it exists (try using ::] to return the empty list, or ::_1: to return an error code, and so on).

]`($:@u)@.v can usually be made shorter than u^:v^:_, especially on definitions of u and v that can be played around with. A similar case holds for the conditional-like u^:(1-v) vs. ]`u@.v. Consider your options, especially when you have lots of named verbs floating about. It's also a little more flexible, but remember, if using $:, there is a recursion depth that it's easy to bump up against. (Usually something like 1800 iterations?)


Create an N-Dimensional Simplex (Tetrahedron) The Simplest N-Dimensional shape one can create for any dimension is a Simplex, and this is a set of N+1 points that are all equal distance away from eachother.

For 2 dimensions, this is an equilateral triangle, for 3 dimensions, this is an regular tetrahedron, at 4 dimensions is the 5-Cell and so on.

The Challenge

Given an Integer dimension N as input, output an Array/List/Stack/Whatever of N Dimensional points that represent a Simplex of this dimension. That is, N+1 vertexes that are equal and non-zero distance from eachother.

Reference implementation in Lua

Examples

1 -> [[0], [1]]
2 -> [[0, 0], [1, 0], [0.5, 0.866...]]
4 -> [[0, 0, 0, 0], [1, 0, 0, 0], [0.5, 0.866..., 0, 0], [0.5, 0.288..., 0.816..., 0], [0.5, 0.288..., 0.204..., 0.790...]]

Notes

Input is a number in any standard format, and will always be an integer greater than 1 and less than 10
Hardcoding is allowed for input of 1, but nothing higher.
Reasonable error is allowed in the output. Issues with floating point arithmetic or trig may be ignored.
Any transformation of the N dimensional simplex is allowed, aslong as it remains Regular and Non-zero.
Standard Loopholes are forbidden.
This is code-golf, so fewest bytes wins.

Python 78 66 Bytes
lambda n:[i*[0]+[n]+(n+~i)*[0]for i in range(n)]+[n*[1+(n+1)**.5]]

Surely can be improved, especially at handling n=1```. (How is that even a simplex?) Just realized that's not necessary. Can probably be improved still ^^
Try it online!
[i*[0]+[1]+(n+~i)*[0]for i in range(n)] creates identity matrix. All points have distance sqrt(2) from each other. (thanks to Rod for improving)
Now we need a n+1-th point with the same distance to all other points. We have to choose (x, x, ... x).
Distance from (1, 0, ...  ) to (x, x, ... x) is sqrt((x-1)²+x²+...+x²). If we want an n dimensional simplex this turns out to be sqrt((x-1)²+(n-1)x²), as we have one 1 and n-1 0s in the first point. Simplify a bit: sqrt(x²-2x+1+(n-1)x²) = sqrt(nx²-2x+1)
We want this distance to be sqrt(2).
sqrt(2) = sqrt(nx²-2x+1)
2 = nx²-2x+1
0 = nx²-2x-1
0 = x²-2/n*x+1/n
Solving this quadratic equation (one solution, other one works fine, too):
x = 1/n+sqrt(1/n²+1/n) = 1/n+sqrt((n+1)/n²) = 1/n+sqrt(n+1)/n = (1+sqrt(n+1))/n
Put that in a list n times, put that list in a list and join with identity matrix.

-4 Bytes thanks to Alex Varga:
Multiply each vector by n. This changes the creation of the identity matrix to lambda n:[i*[0]+[n]+(n+~i)*[0] (same length) and gets rid of the division by n in the additional point, so it becomes n*[1+(n+1)**.5], saving two brackets and the /n.


A Nice, Simple Web Scraping Code Golf Introduction
This is a web scraping Code Golf challenge that attempts to take stock Name and price columns from the 'Most Active' list on this New York Times URL.
Why is this challenge interesting?
Challenge:
Scrape these figures from this NYT page and turn it into a data frame using the smallest number of bytes possible (IE: import pandas as pd (should you choose to use Python) would give you a score of 19 (19 bytes). The data frame must be printed or returned as output.

Shortest Code by bytes wins the challenge. That's it!
Input:

import requests
from bs4 import BeautifulSoup
import pandas as pd

url='https://markets.on.nytimes.com/research/markets/overview/overview.asp'

def pull_active(url):
    # your code
    response = requests.get(url)
    if response.status_code == 200:
      print("Response Successful")
    else:
      print("Response Unsuccessful")
      return()
    bs_object = BeautifulSoup(response.content,'lxml')
    st_value = bs_object.find_all('td',class_='colPrimary')
    st_name = bs_object.find_all('a',class_="truncateMeTo1")
    x = []
    y = []
    for tag in st_name:
      x.append(tag.get_text())
    for tag in st_value:
      y.append(tag.get_text())
    data = {'Name': x[0:8],
            'Price': y[0:8]}
    df = pd.DataFrame(data)
    return(df)
pull_active(url)

Score: 773 bytes
To beat it, any code under 773 bytes.
Output:

  Name    Price
0 General Electric Co 10.11
1 Advanced Micro Devices Inc  33.13
2 PG&E Corp   6.14
3 Fiat Chrysler Automobiles NV    14.98
4 Neuralstem Inc  1.83
5 AT&T Inc    38.20
6 GrubHub Inc 34.00
7 Twitter Inc 29.86

...

Bash + lynx, 73
lynx -dump http://nyti.ms/2BY72Ph|grep -Po '\[(1[6-9]|2[0-3])]\K[^.]*...'

Output is as follows:
General Electric Co          10.11
Advanced Micro Devices Inc   33.13
PG&E Corp                    6.14
Fiat Chrysler Automobiles NV 14.98
Neuralstem Inc               1.83
AT&T Inc                     38.20
GrubHub Inc                  34.00
Twitter Inc                  29.86


Corrupting A Binary File By Interpreting It As Text Using FTP's ASCII mode to transfer binary files is a bad idea. It is likely to corrupt your data. Badly. Let's simulate this corruption!

Your task is to write a program which takes a file as input and outputs the corrupted version of the file. Because how exactly your file gets corrupted is dependent on both the FTP client and server and their systems/implementations, for this challenge, we will use the following rules for corruption, in this order:

Clear the high bit in each byte of the file. (Masking with 0x7F is an option here)
When encountering escape (0x1b) followed by [, delete from the escape character through the next letter character (A-Z and a-z), inclusive.
Escape followed by any other character should remove both the escape and the character following it.
All control codes (characters in the range 0x00-0x1F, inclusive, and 0x7F) other than tab (0x09) and linefeed (0x0a) should be removed.

Other rules

Input and output can be in any convenient format. You do not need to use actual files.
Shortest code wins, of course.
Standard rules and loopholes apply.

Perl 5, 62 53 bytes

y/\x80-\xff/\0-\c?/;s/\e(\[.*?[a-z]|.)|[^\t\n -~]//gi

Try it online! No, I don't know how to input nonprinting characters, particularly illegal UTF-8 sequences, into TIO. Edit: Saved 10 bytes thanks to @NahuelFouilleul.


Creating a HQ9+ interpreter The goal of this code golf is to create an interpreter for the programming language HQ9+
There are 4 commands in this programming language:

H - prints "Hello, world!"
Q - prints the source code of the program
9 - prints the lyrics of the song "99 bottles of beer"
+ - increments the accumulator

The rules:

Because the accumulator isn't defined, you can ignore the command +
Your program should prompt for input (this input will be the source code) or the source code is read from a file
You are not allowed to put the lyrics of "99 bottles of beer" in a file, and read the text from the file
You are not allowed to use a compression algorithm such as GZip or BZip to compress the song text: you have to create your own compression algorithm. This doesn't have to be a complex algorithm, but try to compress the text as much as possible (remember: this is a code-golf, the code with the fewest bytes wins)
If the source code contains a char that isn't H, Q, 9 or +, then output "Source code contains invalid characters" before running any commands! This means that, if the source code is H1 for example, then don't output Hello, world! before you output Source code contains invalid characters. No, immediately output Source code contains invalid characters
If your interpreter accepts both uppercase and lowercase characters, then you get -8 to your character count

Good luck!

APL (Dyalog) (326 - 8 = 318)

Paste it in an editor window and call H. Input is taken from the keyboard.

H
⎕←'Source code contains invalid characters'/⍨~∧/'HhQq9+'∊⍨V←⍞
B←' of beer'
W←' on the wall'
L←⎕TC[2]
Z←{k←' bottle','s'/⍨⍵≠1⋄⍵<0:'99',k⋄⍵=0:'No',k⋄k,⍨⍕⍵}
{⍵∊'Hh':⎕←'Hello, world!'
⍵∊'Qq':⎕←V
⍵∊'9':{⎕←G,K,(G←Z⍵),B,L,(⊃'Go to the store and buy some more' 'Take one down and pass it around'[1+×⍵]),L,(Z⍵-1),K←B,W,L}¨1-⍨⌽⍳100}¨V


Write an xkcd feed bot The new xkcd feed bot room gave me an idea for a simple challenge.
Your code will have to monitor the xkcd website and output all the new comics to the user.
Specs

When first run it should just sit around waiting.
Then, when randall posts a new comic, within a minute, it should display the new comic in any of our usual standards for images (display, save, etc.)
If the comic is interactive and not a simple image, then print out the string "interactive comic".
This does not include the comics which are an image inside a link, those still have to be displayed normally.
After displaying the image, it should go back to waiting around for the next update.
Your program cannot access any sites except http://xkcd.com

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

PowerShell v2+ & Default Browser, 215 217 bytes

$l=date;for(){if(($x=([xml](iwr xkcd.com/rss.xml)).rss.channel.item[0]).pubdate-ge$l){if(($y=$x.description)-match'img src'){saps ($y-replace'<img src="'-replace'" .*')}else{echo "interactive comic"}}$l=date}

WARNING: Running this as-is will likely make Randall very mad at you, due to the high frequency of calls to the RSS feed ... so, y'know, don't do that. (See below for an alternate version that can be used in a one-off manner)

Sets the $last time we displayed a comic to the result of Get-Date. Then, enter an infinite for loop.

Each iteration, we iwr (alias for Invoke-WebRequest) the RSS feed for the site. That's parsed as [xml] (yes, PowerShell can cast as XML), and the .rss.channel.item[0] thereof (i.e., the newest) is stored in $x. If the .pubDate is -ge$l (i.e., newer than the last comic we showed), we have a new comic to display.

So, we first check the .description field (saved in $y), to see if it matches img src. If so, we parse out the img from $y, and feed that to saps (alias for Start-Process). Since it's a URI, this relies on Windows' default behavior for "executing" a URI, that is, it opens the default browser to that location. (If this is too cheaty, let me know and we can iwr down the actual image and save it.)

Otherwise, we echo out that we've got an interactive comic.

In either case, we update our $l date to "now" since we just displayed a comic.

Saved 7 bytes thanks to Matt for reminding me that http:// can be implied

"Safe" version that executes just once and displays the latest comic

$l=(date).AddDays(-3);if(($x=([xml](iwr http://xkcd.com/rss.xml)).rss.channel.item[0]).pubdate-ge$l){if(($y=$x.description)-match'img src'){saps ($y-replace'<img src="'-replace'" .*')}else{echo "interactive comic"}}

You can run this one safely to see how the logic works. It'll only execute once and only display the latest comic.


Notcalc (Calculate the wrong answer) Goal:
Given two natural numbers (integers from 0 to infinity), output a number that is not the sum of those numbers, but is a natural number.
Example solutions (TI-Basic):

A+B+1

not(A+B)

Invalid solutions:

A+B-1 (for inputs 0,0, it returns -1, which is not natural)

"ABC" (ABC is not a number)

Notes:

The output must always be a sum of two natural numbers (which is actually just a natural number)

-1, undefined, infinity, NaN and Error messages are not natural numbers. For our purposes, 0 is natural (although not all mathematicians agree).

RProgN, 4 3 1 Byte
Crossed out 4 is still 4 ;(
E

The most simple of solutions, compares if A and B are equal. Pushes true, which RProgN sees as 1, if they are the same, or false aka 0 otherwise.
Test Cases
0+0 = 1
1+0 = 0
0+1 = 0
1+1 = 1

Try it online!


Output 2015 as QR code Mission is simple. Just output number 2015 as QR code and write it to file named newyear.png in PNG format. Code must be valid any day, so maybe you shall not use current year.

QR code as text looks like this:

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

The result written in newyear.png must contain that QR code with white 5 pixel borders and one pixel sized dots. It must not contain anything else than QR code.

Raw file, 184 bytes = 173-byte file + 11-byte filename

I hope this does not break any standard loopholes. But the output "has a high   kolmogorov-complexity and the shortest way to produce it would (most likely) be to just print it literally...".

Base 64 of the file:

iVBORw0KGgoAAAANSUhEUgAAAB8AAAAfAQAAAAA31SuUAAAAdElEQVR4XnXOMQ5BQRRA0euVRFgGCq1ubIyJpSh11I
qJWIjo+fnt/JnJe55WornlycXMVAB+Qp49A7U/J8rqlIQReG5Quz6Rx8eA6VaF5R7a5arooXg2LaKvd8KGRyBPJLoy
D640pxZ3pay/creL5KnEvwcfvE46ggJMibIAAAAASUVORK5CYII=

Instead of golfing a program I golfed the resulting PNG image. QR code is a very flexible format, there are many parameters that can be fiddled: the encoding of the input, the error correction level, and the masking image. These will all generate different symbols and thus compressed to files of different sizes.

So I have written a program to generate all these combinations (resulting 6720 files), and then use PNGOUT to pick the one which compressed to the smallest file. It turns out to be a file that:

First write "20" in alphanumeric mode
Then write "1" in numeric mode
Then write "5" in numeric mode
Use the "H" (High) error correction level
Use the "110" data masking

This is called test-3-1-H-Diamonds.bmp if you used the program below. This image is 175-byte long after running PNGOUT. With "high" error correction level in "version 1" QR code, we can modify up to 8 pixels in the data part without ruining the data. With a bit of manual trial-and-error I can reduce it further to 173 bytes presented above. It can probably be smaller but exhausting all combinations requires 208C8 ~ 7.5 × 1013 checks which I'm not going to do ;)

The Rust (0.13.0-nightly (5ba610265)) program that generates all combinations:

/*

Also put these into your Cargo.toml:

[dependencies]
qrcode = "0.0.3"
bmp = "0.0.3"

*/

extern crate qrcode;
extern crate bmp;

use qrcode::bits::Bits;
use qrcode::optimize::Segment;
use qrcode::types::{Version, EcLevel, Mode};
use qrcode::ec::construct_codewords;
use qrcode::canvas::{Canvas, MaskPattern, Module};

use bmp::{Image, Pixel};

use std::num::Int;

const BLACK: Pixel = Pixel { r: 0, g: 0, b: 0};
const WHITE: Pixel = Pixel { r: 255, g: 255, b: 255 };

static SEGMENT_SEPARATIONS: [&'static [(uint, uint)]; 8] = [
    &[(0, 1), (1, 2), (2, 3), (3, 4)],
    &[(0, 1), (1, 2), (2, 4)],
    &[(0, 1), (1, 3), (3, 4)],
    &[(0, 2), (2, 3), (3, 4)],
    &[(0, 1), (1, 4)],
    &[(0, 2), (2, 4)],
    &[(0, 3), (3, 4)],
    &[(0, 4)],
];

const ALL_EC_LEVELS: &'static [EcLevel] = &[EcLevel::L, EcLevel::M, EcLevel::Q, EcLevel::H];
const ALL_MODES: &'static [Mode] = &[Mode::Numeric, Mode::Alphanumeric, Mode::Byte];
const ALL_MASK_PATTERNS: &'static [MaskPattern] = &[
    MaskPattern::Checkerboard,
    MaskPattern::HorizontalLines,
    MaskPattern::VerticalLines,
    MaskPattern::DiagonalLines,
    MaskPattern::LargeCheckerboard,
    MaskPattern::Fields,
    MaskPattern::Diamonds,
    MaskPattern::Meadow,
];

fn run(ec_level: EcLevel, mask_pattern: MaskPattern, segments: &[Segment], filename: &str) {
    let version = Version::Normal(1);
    let mut bits = Bits::new(version);
    if bits.push_segments(b"2015", segments.iter().map(|s| *s)).is_err() {
        return;
    }
    if bits.push_terminator(ec_level).is_err() {
        return;
    }
    let data = bits.into_bytes();
    let (encoded_data, ec_data) = construct_codewords(&*data, version, ec_level).unwrap();
    let mut canvas = Canvas::new(version, ec_level);
    canvas.draw_all_functional_patterns();
    canvas.draw_data(&*encoded_data, &*ec_data);
    canvas.apply_mask(mask_pattern);
    let canvas = canvas;

    let width = version.width();
    let real_image_size = (width + 10) as uint;
    let mut image = Image::new(real_image_size, real_image_size);
    for i in range(0, real_image_size) {
        for j in range(0, real_image_size) {
            image.set_pixel(i, j, WHITE);
        }
    }
    for i in range(0, width) {
        for j in range(0, width) {
            if canvas.get(i, j) == Module::Dark {
                image.set_pixel((i + 5) as uint, real_image_size - (j + 6) as uint, BLACK);
            }
        }
    }
    image.save(filename);
}

fn main() {
    for (z, separations) in SEGMENT_SEPARATIONS.iter().enumerate() {
        let mut segments = separations.iter().map(|&(b, e)| Segment {
            mode: Mode::Numeric, begin: b, end: e
        }).collect::<Vec<_>>();

        let variations_count = ALL_MODES.len().pow(segments.len());
        for i in range(0, variations_count) {
            let mut var = i;
            for r in segments.iter_mut() {
                r.mode = ALL_MODES[var % ALL_MODES.len()];
                var /= ALL_MODES.len();
            }
            for ec_level in ALL_EC_LEVELS.iter() {
                for mask_pattern in ALL_MASK_PATTERNS.iter() {
                    let filename = format!("results/test-{}-{}-{}-{}.bmp", z, i, *ec_level, *mask_pattern);
                    run(*ec_level, *mask_pattern, &*segments, &*filename);
                }
            }
        }
        println!("processed {}/{}", z, 8u);
    }
}


Shared Birthday Party An office (let's call it "The Office") is going to cut down on wasted time in 2019 by consolidating office birthday parties. Any two people with a birthday between Monday and Friday (inclusive) of the same week will be celebrated with a Shared Birthday Party some time that week. People whose birthdays fall on a Saturday or Sunday get no party at all.

Some people do not like sharing a birthday party with people who do not share their actual birthday. They will be Very Angry to have a Shared Birthday Party.

We are going to simulate an office and find the first week in which someone gets Very Angry about their Shared Birthday Party.

The Challenge

Write a program or function that outputs the first ISO week number for 2019 in which someone in a simulated office gets Very Angry about their Shared Birthday Party, subject to the following basic rules:

input an integer N > 1, which is the number of workers in the office.
the N birthdays themselves are distributed uniformly at random from Jan 1 to Dec 31 (ignore Feb 29).
but the working weeks for the purposes of determining Shared Birthday Parties are the 2019 ISO Week Dates, which are between 2019-W01-1 (2018-12-31) and 2019-W52-7 (2019-12-29). A new ISO week starts every Monday. (I think this is all you really need to know about ISO weeks for this challenge).
for the N people in the office, each has a 1/3 chance of having a Very Angry Shared Birthday Party personality type, so you'll have to simulate that too.
but they will not be angry if the party is shared with people who have the same birthday.
output the ISO week number (exact format for this is flexible as long as the week number is clear) for the first occurrence of a Very Angry person. If there are no angry people, you can output anything that isn't confused with an ISO week or the program can error out etc.

Some simplifying assumptions:

as I mentioned, ignore the February 29 issue completely (an unneeded complication)
ignore public holidays (this is an international community so our holidays will differ) and just assume the office is open on each weekday.

Rules

This is code-golf. Shortest answer in bytes for each language wins. Default loopholes forbidden.

Code explanations welcome.

Worked Examples

Contrived Example 1 with input N = 7. First and second columns are random as described in the rules (but not actually random here of course).

Angry Type
Person?    Birthday   ISO Week   Comment
================================================================================
   N       2018-12-31      W01   In the 2019 ISO week date year
   Y       2018-12-31      W01   Same birthday, so no anger happens
   N       2019-02-05      W06
   Y       2019-03-15      W11   No anger happens because other W11 b-day is a Saturday
   N       2019-03-16      W11
   N       2019-09-08      W36   My birthday!
   Y       2019-12-30       -    Not in the 2019 ISO week date year

So no anger happens. The program or function can error out or output something not confused with an ISO week number.

Example 2 with N unspecified.

Angry Type
Person?    Birthday   ISO Week   Comment
================================================================================
   N       2019-01-19      W03
   Y       2019-02-04      W06
   N       2019-02-05      W06   No anger because not an angry person
  ...             ...      ...   (No angry people until...)
   Y       2019-03-12      W11   Very Angry Person!
   N       2019-03-14      W11
  ...             ...      ...   ...

The output would be W11 or something equivalent.

Python 2, 172 202 bytes

def f(n):
 D=set();A=[];R=randint
 while n:
	n-=1;w,d=R(1,52),R(1,5)
	if R(0,364)>104:D|={(w,d)};A+=[w]*(R(0,2)>1)
 return next((a for a in sorted(A)if[w for w,d in D].count(a)>1),0)
from random import*

Try it online!

oops! Missed a requirement; cost 30 bytes.

It is given by the OP that your birthday is not 29 February.

If your birthday is 30 December, it will not fall in any ISO week of 2019, so in any case you cannot be a Very Angry ISO week of 2019.

That leaves 364 other birthdays to consider you being Very Angry about. 104 of these fall on weekends when we have stipulated that you won't get Very Angry about it. So we only care about you 260/365 of the time; i.e., when R(0,364)>104 (randint's range is inclusive). Given that constraint, it is equiprobable that your weekday birthday falls in any of the 52 ISO weeks of 2019, and any weekday of that week; and, independently, that you are 1 in 3 likely to be a Very Angry person.

D is then a set of (weeknum,weekday) so that if a potentially Angry person shares an actual birthday, then there's no need to be Amgry unless there's yet another person having a birthday that week.

0 is returned if no Very Angry people manifest during any ISO 2019 week; otherwise, the ISO week number of the earliest meltdown is returned.


Write a Deadfish Interpreter Sandbox, Codidact
A rewrite of this question with a simpler input format and guidelines.
Challenge
Deadfish uses a single accumulator, on which all commands are to be performed.
It has the following commands:

Command
Description

i
increment the accumulator

d
decrement the accumulator

s
square the value of the accumulator

o
output the value of the accumulator as a number

If, after executing a command, the accumulator is equal to -1 or equal to 256, the accumulator must be reset to zero.
I/O
Input can be taken as a single string, list of codepoints, or any other reasonable format. It is guaranteed that the input will only consist of deadfish commands.
Output can be given as an array of numbers, or just the numbers printed with separators between them.
Testcases
(some are borrowed from the Esolangs wiki)
iissso -> 0
diissisdo -> 288
iissisdddddddddddddddddddddddddddddddddo -> 0
isssoisoisoisoiso -> 1,4,25,676,458329
ooooosioiiisooo -> 0,0,0,0,0,1,16,16,16
iiii -> nothing
iiiiiiiissdiiiiiiiiiiiiiiiiio -> 4112
o -> 0

Without Outputs

flex, 86 \$\cdots\$ 83 82 bytes
Saved 2 bytes and got moved into TIO thanks to Mukundan314!!!

%{
a;m(){a*=a!=256;}
%}
%%
i m(++a);
d m(a&&--a);
s m(a*=a);
o printf("%d ",a);
%%

Try it online!
flex stands for fast lexical analyser generator. It takes input as above and generates a lexer in C.
The input comprises of a C declaration section:
%{
a;m(){a*=a!=256;}
%}

where here we simply declare the accumulator a (implicitly as an int) and a function to set the accumulator to \$0\$ if it's \$256\$ after a computation.
This is followed by the rules section comprised of all the regexes that need to be parsed along with their actions (in C):
%%
i m(++a);
d m(a&&--a);
s m(a*=a);
o printf("%d ",a);
%%

here we have our 4 characters along with the code to run when each is encountered. Decrement will only happen if the accumulator is non-zero.
There's a program section that follows this but it will simply default to a main that runs the parser if left out (as in this case).
You can generate the C-source code lexer from the above (in file deadfish.l) and compile it with the following:
flex deadfish.l
gcc lex.yy.c -o deadfish -lfl

After compiling, running the following:
echo iissso | ./deadfish
echo diissisdo | ./deadfish
echo iissisdddddddddddddddddddddddddddddddddo | ./deadfish
echo isssoisoisoisoiso | ./deadfish
echo ooooosioiiisooo | ./deadfish
echo iiiiiiiissdiiiiiiiiiiiiiiiiio | ./deadfish

outputs:
0
288
0
1 4 25 676 458329
0 0 0 0 0 1 16 16 16
4112

You can also just run it as ./deadfish and have an interactive deadfish environment to play with to your heart's content!


Elo Rating Calculator Related

Task

Your task is to calculate the new Elo rating (FIDE rating system) for a player after winning, losing or drawing a game of chess.

To calculate the Elo rating two formulas are needed:

R' = R0 + K*(S - E)
E = 1 / (1 + 10 ^ ((R1 - R0) / 400))

where:

R' is the new rating for player0,
R0 is the current rating of player0 and R1 is the current rating of player1,
S is the score of the game: 1 if player0 wins, 0 if player0 loses or
0.5 if player0 draws,
K = 40 if the given history has a length < 30, even if it exceeds 2400
K = 20 if the given history has a length >= 30 and never exceeds 2400 (<2400),
K = 10 if the given history has a length >= 30 and exceeds 2400 at any point (>=2400)

(if history has a length < 30 but a max value >= 2400 K will equal 40)

Input

History of player0's ratings as an array of positive integers greater than 0, where the last item is the players current rating. If no history is given, the current rating will be 1000
Rating of player1 as an integer
Score, either 1, 0 or 0.5

Output

R', A decimal integer of player0's new rating

Examples

input: [], 1500, 1
  K = 40 (length of history is less than 30)
  E = 1 / (1 + 10 ^ ((1500 - 1000) / 400)) = 0.0532
  R' = 1000 + 40*(1 - 0.0532) = 1038
output: 1038

input: [1000, 1025, 1050, 1075, 1100, 1125, 1150, 1175, 1200, 1225, 1250, 1275, 1300, 1325, 1350, 1375, 1400, 1425, 1450, 1475, 1500, 1525, 1550, 1575, 1600, 1625, 1650, 1675, 1700, 1725], 1000, 0
  K = 20 (length of history is more than 30 but never exceeds 2400)
  E = 1 / (1 + 10 ^ ((1000 - 1725) / 400)) = 0.9848
  R' = 1725 + 20*(0 - 0.9848) = 1705
output: 1705

input: [1000, 1025, 1050, 1075, 1100, 1125, 1150, 1175, 1200, 1225, 1250, 1275, 1300, 1325, 1350, 1375, 1400, 1425, 1450, 1475, 1500, 1525, 1550, 1575, 1600, 1625, 1650, 1800, 2100, 2500], 2200, 0.5
  K = 10 (length of history is more than 30 and exceeds 2400)
  E = 1 / (1 + 10 ^ ((2200 - 2500) / 400)) = 0.8490
  R' = 2500 + 10*(0.5 - 0.8490) = 2497
output: 2497

Test cases:

[2256,25,1253,1278,443,789], 3999, 0.5 -> 809
[783,1779,495,1817,133,2194,1753,2169,834,521,734,1234,1901,637], 3291, 0.5 -> 657
[190,1267,567,2201,2079,1058,1694,112,780,1182,134,1077,1243,1119,1883,1837], 283, 1 -> 1837
[1665,718,85,1808,2546,2193,868,3514,436,2913,6,654,797,2564,3872,2250,2597,1208,1928,3478,2359,3909,581,3892,1556,1175,2221,3996,3346,238], 2080, 1 -> 248
[1543,2937,2267,556,445,2489,2741,3200,528,964,2346,3467,2831,3746,3824,2770,3207,613,2675,1692,2537,1715,3018,2760,2162,2038,2637,741,1849,41,193,458,2292,222,2997], 3814, 0.5 -> 3002

Notes

You won't get an input with fewer scores than 30 and a maximum score higher than 2400

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

Octave, 106 bytes

This assumes the history never contains a zero.

@(h,r,s)(h=[1e3,h])(n=nnz(h))+((40-(20*(n>30)))-(10*((n>30)&(max(h)>2401))))*(s-(1/(1+10^((r-h(n))/400))))

This outputs (after some formatting):

Correct - Calculated
1038    - 1037.87
1705    - 1705.3
2497    - 2496.51

Try it online!

Note: According to the FIDE-scoring system: If you play 41 games against a player having a score of 5000 (more than 2000 points higher than the highest achieved score ever), you'll end up with a score of 2400. I believe that fewer scores than 30, and a maximum score higher than 2400 should be considered invalid input (but that's OP's decision).

Check it here


Compress my Malbolge! Background

Malbolge is truly intriguing language. But programs written in it are also extraordinairly huge (and in some cases, unpostable on PPCG).

Your challenge (shall you accept it) is, to compress and decompress given normalized Malbolge program. Devise your own lossless algorithm. You may compress your data further using an existing algorithm afterwards, but you must cite the algorithm used. You may use dictionaries.

Input

On the input, there will be given (in most cases very long) string, containing only following characters: i</*jpov. Example data:

iooooooooooooooooooooovoooioooipooooo<ooooooooooivojo<<<<<oio*ioooooooooooooooopiooooooooooooooooooo/jpooooooooooo

Example bigger chunk of data, 86 kilobytes big.

Output

Well, not very much to say about it, output depends on the algorithm.

Rules:

Input taken by your program, compressed, and then decompressed, shall be identical.
Submissions are scored by the following formula: \$ \frac{Compressed}{Original} \times 100\% \$, applied to the example 86 kilobytes big chunk.
If a submission abuses the fact that only one example chunk is provided (eg. by hardcoding it), I reserve right to add more example chunks.
Standard loopholes are forbidden, I/O rules apply.

Note: 7zip with PPMd algorithm manages to compress the code with 2,95% score.

Score with test 1: 38.6%, Score with test 2: 4.9%

Compressor

Jelly, 97 bytes

ṡ2ṢŒɠżQƊ1ị>ɗƇ3NÞḣ8Ṫ€,‘ɼ$€Ẏœṣ;@W}ɗjƭƒ
7©ṛ⁸“i</*jpov”iⱮ’Ç31¡
“i</*jpov”iⱮḅ8b256,ÇĖF€LÞḢL;L};÷/$ʋ,ḷɗ

Try it online!

Decompressor

Jelly, 44 bytes

ḅ256ḃ8
ḣ3s2ṚṣḢ}©¥jƭƒṫ5µṛ®n8Ɗ¿‘
ḢĿị“i</*jpov”

Try it online!

Explanation

Uses two different methods and picks the one with the shortest output.

Method 1: Convert the input from base 8 to base 256
Method 2: Repeatedly finds the 8 most common sublists of length 2 and replaces them with an integer between 8 and 255. The dictionary is stored at the beginning of the output.

The first byte of the output indicates the method used.

Input to compressor is a string of Malbolge. Output is a list of integers between 0 and 255. This could easily be encoded in Jelly’s code page if preferred. Input and output to/from decompressor mirror the compressor.


Convert 1 into any positive integer using only the operations *3 and /2 Any positive integer can be obtained by starting with 1 and applying a sequence of operations, each of which is either "multiply by 3" or "divide by 2, discarding any remainder".

Examples (writing f for *3 and g for /2):

4 = 1 *3 *3 /2 = 1 ffg
6 = 1 ffggf = 1 fffgg
21 = 1 fffgfgfgggf

Write a program with the following behavior:

Input: any positive integer, via stdin or hard-coded. (If hard-coded, the input numeral will be excluded from the program length.)
Output: a string of f's and g's such that <input> = 1 <string> (as in the examples). Such a string in reverse order is also acceptable. NB: The output contains only f's and g's, or is empty.

The winner is the entry with the fewest bytes of program-plus-output when 41 is the input.

We're getting dirty, friends!

JAVA 210 207  199 characters

public class C{public static void main(String[] a){int i=41;String s="";while(i>1){if(i%3<1){s+="f";i/=3;}else if(i%3<2){s+="g";i+=i+1;}else{s+="g";i+=i+(Math.random()+0.5);}}System.out.println(s);}}

non-golfed:

public class C {

    public static void main(String[] a) {

        int i = 41;
        String s = "";
        while (i > 1) {
            if (i % 3 == 0) {
                s += "f";
                i /= 3;
            } else {
                if (i % 3 == 1) {
                    s += "g";
                    i += i + 1;
                } else {
                    s += "g";
                    i += i + (Math.random() + 0.5);
                }
            }
        }
        System.out.println(s);
    }
}

output : depending on the faith of the old gods, the shortest i had was 30. Note that the output must be read from the right.

234

1 ggfgfgfgfggfggfgffgfggggfgffgfggfgfggggfgffgfggfgfggfgfggfgfgggggfffgfggfgfggfgfgggffgggggfffgfggggfgffgfggfgfggfgfggfgfggfgfggfgfggfgfggggfgffgfggfgfggfgfggfgfggfgfggfgfggggggggggggfgfgfggggfgfgfggfffgfgfggffgfgfggfgfggggffgfgfffff

108

1 gggffgfgfggggggfggggfgffggggfgfgfgfgfgffgggfgggggfggfffggfgfffffgggffggfgfgggffggfgfgggffggggggfgfgffgfgfff

edit 45

1 ggfgfgfgfgggfggfffgfggfgfgggggggffgffgfgfff

points : 318 199+30 = 229

edit1 (2*i+1)%3==0 --> (2*i) % 3 ==1

Nota Bene if you use Java 6 and not Java 7 while golfing, you can use

public class NoMain {
    static {
        //some code
        System.exit(1);
    }
}

39 characters structure instead of a standard structure which is 53 characters long.


Smallest possible runnable Mach-O executable What is the smallest possible runnable Mach-O executable on x86_64? The program can do nothing (not even returning a return code), but must be a valid executable (must run without errors).

My try:

GNU Assembler (null.s):

.text
.globl _main

_main:
    retq

Compilation & Linking:

as -o null.o null.s
ld -e _main -macosx_version_min 10.12 -o null null.o -lSystem

Size: 4248 bytes

Looking at the hex values it seems there is a lot of zero padding which maybe can be removed, but I don't know how. Also I don't know if it is possible to make the exectubale run without linking libSystem...

Smallest runnable Mach-O has to be at least 0x1000 bytes. Because of XNU limitation, file has to be at least of PAGE_SIZE.
See xnu-4570.1.46/bsd/kern/mach_loader.c, around line 1600.

However, if we don't count that padding, and only count meaningful payload, then minimal file size runnable on macOS is 0xA4 bytes.

It has to start with mach_header (or fat_header / mach_header_64, but those are bigger).

struct mach_header {
    uint32_t    magic;      /* mach magic number identifier */
    cpu_type_t  cputype;    /* cpu specifier */
    cpu_subtype_t   cpusubtype; /* machine specifier */
    uint32_t    filetype;   /* type of file */
    uint32_t    ncmds;      /* number of load commands */
    uint32_t    sizeofcmds; /* the size of all the load commands */
    uint32_t    flags;      /* flags */
};

It's size is 0x1C bytes.
magic has to be MH_MAGIC.
I'll be using CPU_TYPE_X86 since it's an x86_32 executable.
filtetype has to be MH_EXECUTE for executable, ncmds and sizeofcmds depend on commands, and have to be valid.
flags aren't that important and are too small to provide any other value.

Next are load commands.
Header has to be exactly in one mapping, with R-X rights -- again, XNU limitations.
We'd also need to place our code in some R-X mapping, so this is fine.
For that we need a segment_command.

Let's look at definition.

struct segment_command { /* for 32-bit architectures */
    uint32_t    cmd;        /* LC_SEGMENT */
    uint32_t    cmdsize;    /* includes sizeof section structs */
    char        segname[16];    /* segment name */
    uint32_t    vmaddr;     /* memory address of this segment */
    uint32_t    vmsize;     /* memory size of this segment */
    uint32_t    fileoff;    /* file offset of this segment */
    uint32_t    filesize;   /* amount to map from the file */
    vm_prot_t   maxprot;    /* maximum VM protection */
    vm_prot_t   initprot;   /* initial VM protection */
    uint32_t    nsects;     /* number of sections in segment */
    uint32_t    flags;      /* flags */
};

cmd has to be LC_SEGMENT, and cmdsize has to be sizeof(struct segment_command) => 0x38.
segname contents don't matter, and we'll use that later.

vmaddr has to be valid address (I'll use 0x1000), vmsize has to be valid & multiple of PAGE_SIZE, fileoff has to be 0, filesize has to be smaller than size of file, but larger than mach_header at least (sizeof(header) + header.sizeofcmds is what I've used).

maxprot and initprot have to be VM_PROT_READ | VM_PROT_EXECUTE. maxport usually also has VM_PROT_WRITE.
nsects are 0, since we don't really need any sections and they'll add up to size.
I've set flags to 0.

Now, we need to execute some code. There are two load commands for that: entry_point_command and thread_command.
entry_point_command doesn't suit us: see xnu-4570.1.46/bsd/kern/mach_loader.c, around line 1977:

1977    /* kernel does *not* use entryoff from LC_MAIN.  Dyld uses it. */
1978    result->needs_dynlinker = TRUE;
1979    result->using_lcmain = TRUE;

So, using it would require getting DYLD to work, and that means we'll need __LINKEDIT, empty symtab_command and dysymtab_command, dylinker_command and dyld_info_command. Overkill for "smallest" file.

So, we'll use thread_command, specifically LC_UNIXTHREAD since it also sets up stack which we'll need.

struct thread_command {
    uint32_t    cmd;        /* LC_THREAD or  LC_UNIXTHREAD */
    uint32_t    cmdsize;    /* total size of this command */
    /* uint32_t flavor         flavor of thread state */
    /* uint32_t count          count of uint32_t's in thread state */
    /* struct XXX_thread_state state   thread state for this flavor */
    /* ... */
};

cmd is going to be LC_UNIXTHREAD, cmdsize would be 0x50 (see below).
flavour is x86_THREAD_STATE32, and count is x86_THREAD_STATE32_COUNT (0x10).

Now the thread_state. We need x86_thread_state32_t aka _STRUCT_X86_THREAD_STATE32:

#define _STRUCT_X86_THREAD_STATE32  struct __darwin_i386_thread_state
_STRUCT_X86_THREAD_STATE32
{
    unsigned int    __eax;
    unsigned int    __ebx;
    unsigned int    __ecx;
    unsigned int    __edx;
    unsigned int    __edi;
    unsigned int    __esi;
    unsigned int    __ebp;
    unsigned int    __esp;
    unsigned int    __ss;
    unsigned int    __eflags;
    unsigned int    __eip;
    unsigned int    __cs;
    unsigned int    __ds;
    unsigned int    __es;
    unsigned int    __fs;
    unsigned int    __gs;
};

So, it is indeed 16 uint32_t's which would be loaded into corresponding registers before thread is started.

Adding header, segment command and thread command gives us 0xA4 bytes.

Now, time to craft the payload.
Let's say we want it to print Hi Frand and exit(0).

Syscall convention for macOS x86_32:

arguments passed on the stack, pushed right-to-left
stack 16-bytes aligned (note: 8-bytes aligned seems to be fine)
syscall number in the eax register
call by interrupt

See more about syscalls on macOS here.

So, knowing that, here's our payload in assembly:

push   ebx          #; push chars 5-8
push   eax          #; push chars 1-4
xor    eax, eax     #; zero eax
mov    edi, esp     #; preserve string address on stack
push   0x8          #; 3rd param for write -- length
push   edi          #; 2nd param for write -- address of bytes
push   0x1          #; 1st param for write -- fd (stdout)
push   eax          #; align stack
mov    al, 0x4      #; write syscall number
#; --- 14 bytes at this point ---
int    0x80         #; syscall
push   0x0          #; 1st param for exit -- exit code
mov    al, 0x1      #; exit syscall number
push   eax          #; align stack
int    0x80         #; syscall

Notice the line before first int 0x80.
segname can be anything, remember? So we can put our payload in it. However, it's only 16 bytes, and we need a bit more.
So, at 14 bytes we'll place a jmp.

Another "free" space is thread state registers.
We can set anything in most of them, and we'll put rest of our payload there.

Also, we place our string in __eax and __ebx, since it's shorter than mov'ing them.

So, we can use __ecx, __edx, __edi to fit the rest of our payload.
Looking at difference between address of thread_cmd.state.__ecx and end of segment_cmd.segname we calculate that we need to put jmp 0x3a (or EB38) in last two bytes of segname.

So, our payload assembled is 53 50 31C0 89E7 6A08 57 6A01 50 B004 for first part, EB38 for jmp, and CD80 6A00 B001 50 CD80 for second part.

And last step -- setting the __eip. Our file is loaded at 0x1000 (remember vmaddr), and payload starts at offset 0x24.

Here's xxd of result file:

00000000: cefa edfe 0700 0000 0300 0000 0200 0000  ................
00000010: 0200 0000 8800 0000 0000 2001 0100 0000  .......... .....
00000020: 3800 0000 5350 31c0 89e7 6a08 576a 0150  8...SP1...j.Wj.P
00000030: b004 eb38 0010 0000 0010 0000 0000 0000  ...8............
00000040: a400 0000 0700 0000 0500 0000 0000 0000  ................
00000050: 0000 0000 0500 0000 5000 0000 0100 0000  ........P.......
00000060: 1000 0000 4869 2046 7261 6e64 cd80 6a00  ....Hi Frand..j.
00000070: b001 50cd 8000 0000 0000 0000 0000 0000  ..P.............
00000080: 0000 0000 0000 0000 0000 0000 2410 0000  ............$...
00000090: 0000 0000 0000 0000 0000 0000 0000 0000  ................
000000a0: 0000 0000                                ....

Pad it with anything up to 0x1000 bytes, chmod +x and run :)

P.S. About x86_64 -- 64bit binaries are required to have __PAGEZERO (any mapping with VM_PROT_NONE protection covering page at 0x0). IIRC they [Apple] didn't make it required on 32bit mode only because some legacy software didn't have it and they're afraid to break it.


Mathematica, 95 86 bytes

Since the method of input has not been specified, I'm simply expecting the resolution to be saved as an integer in the variable n

r={{""}};Do[r=ArrayFlatten[r/.q_String:>{{q<>"2",q<>"1"},{q<>"3",q<>"4"}}],{Log2@n}];r

With indentation:

r = {{""}};
Do[
  r = ArrayFlatten[
    r /. q_String :> {{q <> "2", q <> "1"}, {q <> "3", q <> "4"}}
  ],
  {Log2@n}
];
r


A Formula for Congruences The Chinese Remainder Theorem can be quite useful in modular arithmetic.

For example, consider the following set of congruence relations:

For sets of congruence relations like this, where all the bases (3, 5, 7 in this example) are co-prime with each other, there will be one and only one integer n between 1 and the product of the bases (3*5*7 = 105 in this example) inclusive that satisfies the relations.

In this example, the number would be 14, generated by this formula:

where 2, 4, and 0 are given from the above example.

70, 21, 15 are the coefficients of the formula and they are dependent on the bases, 3, 5, 7.

To calculate the coefficients of the formula (70, 21, 15 in our example) for a set of bases, we use the following procedure.

For each number a in a set of bases:

Find the product of all of the other bases, denoted as P.
Find the first multiple of P that leaves a remainder of 1 when divided by a. This is the coefficient of a.

For example, to calculate the coefficient that corresponds to the base 3, we find the product of all the other bases (i.e. 5*7 = 35) and then find the first multiple of that product that leaves a remainder of 1 when divided by the base.

In this case, 35 leaves a remainder of 2 when divided by 3, but 35*2 = 70 leaves a remainder of 1 when divided by 3, so 70 is the corresponding coefficient for 3. Similarly, 3*7 = 21 leaves a remainder of 1 when divided by 5 and 3*5 = 15 leaves a remainder of 1 when divided by 7.

In a nutshell

For each number a in a set of numbers:

Find the product of all of the other numbers, denoted as P.
Find the first multiple of P that leaves a remainder of 1 when divided by a. This is the coefficient of a.

The challenge

The challenge is, for a set of two or more bases, to find the set of corresponding coefficients.
The set of bases are guaranteed to be pairwise co-prime and each base is guaranteed to be larger than 1.
Your input is a list of integers as input [3,4,5] or space-separated string "3 4 5" or however your inputs work.
Your output should either be a list of integers or space-separated string that denotes the set of coefficients.

Test cases

input             output
[3,5,7]           [70,21,15]
[2,3,5]           [15,10,6]
[3,4,5]           [40,45,36]
[3,4]             [4,9]
[2,3,5,7]         [105,70,126,120]
[40,27,11]        [9801,7480,6480]
[100,27,31]       [61101,49600,56700]
[16,27,25,49,11]  [363825,2371600,2794176,5583600,529200]

Many thanks to Leaky Nun for his help in writing this challenge. As always, if the problem is unclear, please let me know. Good luck and good golfing!

Haskell, 61 55 53 bytes

f x=[[p|p<-[0,product x`div`n..],p`mod`n==1]!!0|n<-x]

Defines a function f that takes input and gives output as a list of integers.

f x=[                                          |n<-x]  (1)
              product x                                (2)
                       `div`n                          (3)

First we loop over all integers in the input (1). Then we take the product of all of the integers (2) and divide by n to get just the product of the non-n integers, which is P (3).

           [0,               ..]                       (4)
     [p|p<-                     ,p`mod`n==1]           (5)
                                            !!0        (6)

Then we use the result (P) as the step value for a range starting at zero (4). We take the result, [0, P, 2P, 3P, ...], and filter it on values for which the result of a mod-n operation is one (5). Finally, we take the first element, which works thanks to lazy evaluation (6).

Thanks to @xnor for 2 bytes!


How long is a Welsh word? Write a program or function which receives as input a string representing a Welsh word (UTF-8 unless otherwise specified by you).

The following are all single letters in Welsh:

  a, b, c, ch, d, dd, e, f, ff, g, ng, h, i, j, l, ll, m, n, o, p, ph, r, rh, s, t, th, u, w, y

To quote Wikipedia,

  While the digraphs ch, dd, ff, ng, ll, ph, rh, th are each written with two symbols, they are all considered to be single letters. This means, for example that Llanelli (a town in South Wales) is considered to have only six letters in Welsh, compared to eight letters in English.

These letters also exist in Welsh, though they are restricted to technical vocabulary borrowed from other languages:

  k, q, v, x, z

Letters with diacritics are not regarded as separate letters, but your function must accept them and be able to count them. Possible such letters are:

  â, ê, î, ô, û, ŷ, ŵ, á, é, í, ó, ú, ý, ẃ, ä, ë, ï, ö, ü, ÿ, ẅ, à, è, ì, ò, ù, ẁ

(This means that ASCII is not an acceptable input encoding, as it cannot encode these characters.)

Notes:

This is code golf.
You do not have to account for words like llongyfarch, in which the ng is not a digraph, but two separate letters. This word has nine letters, but you can miscount it as eight. (If you can account for such words, that's kind of awesome, but outside the scope of this challenge.)
The input is guaranteed to have no whitespace (unless you prefer it with a single trailing newline (or something more esoteric), in which case that can be provided). There will certainly be no internal whitespace.

Test cases:

Llandudno, 8
Llanelli, 6
Rhyl, 3
Llanfairpwllgwyngyllgogerychwyrndrobwllllantysiliogogogoch, 50 (really 51, but we'll count 50)
Tŷr, 3
Cymru, 5
Glyndŵr, 7

Retina, 23 bytes

i`[cprt]h|dd|ff|ng|ll|.

Try it online!

Even moar regex.


running consecutive commands in bash Usually to run multiple commands consecutively one would do:

sudo apt update && sudo apt upgrade # 35 characters

I can't help but feel there's a neat trick to running these with less keystrokes, and you golfers here love challenges :)

I've found a ton of answers around various SE Sites related to running arguments to different commands or commands in parallel, but nothing like what I'm after.

I've come to achieve what I want a couple of ways, but it's way longer and more difficult to type:

 x=('update' 'upgrade') && for i in ${x[*]}; do sudo apt $i; done

I quickly shortened this to:

for x in update upgrade; do sudo apt $x; done

then

for x in update upgrade;do sudo apt $x;done # 43 characters

Using bash, what is a golfed way of achieving the above? shortest line wins

(this is my first post to the group, please be kind if I've used the wrong tags) ;)

edit: as pointed out my own loops don't exactly do what is in the question due to the && being conditional on the first command not having an error (I do know this). There's also the fact that my loops (and the original command line without the -y switch) still requires user input to complete. An oversight. Time for some more explicit instructions.

My original thought was to have something like:

echo update upgrade | sudo apt

with the objective of just running one after the other.

In the interests of trying to open this up to other languages, let's expand it thusly:

Objectives:

run both commands
require no more than one additional keystroke by the user
can outsource this to other other languages/scripts*
can be scripted if:

gracefully fails (error messages are ok, but it shouldn't try and execute anything else in error)
it's something commonly or "unobtrusively installable" in linux/ubuntu (I feel I may regret this line)
the script takes at least three arguments

command to run

argument 1

argument 2

argument n

or specified on the command line, (see next example)
in this second case, see the note below

./twice "sudo apt" update upgrade

*I have it in mind that someone could construct a cute little binary/script from a printf, but the essence is, if it can be run from an executable script, all characters of the script EXCEPT the first line (the shebang) count.

If I've totally messed this up, feel free to close. Cheers

40 bytes

for a in ${@:2};do eval "${1} ${a}";done

Usage: ./[filename] "[primary command]" [arguments]

Ex. ./twice "sudo apt" update upgrade (Assumes 'twice' as file name)

Was this what you wanted?

Note: Please golf me further if it is possible, and correct me if I'm wrong. This was my first bash entry.


Compute the perimeter density matrix Introduction

The perimeter density matrix is an infinite binary matrix M defined as follows.
Consider a (1-based) index (x, y), and denote by M[x, y] the rectangular sub-matrix spanned by the corner (1, 1) and (x, y).
Suppose that all values of M[x, y] except Mx, y, the value at index (x, y), have already been determined.
Then the value Mx, y is whichever of 0 or 1 that puts the average value of M[x, y] closer to 1 / (x + y).
In case of a tie, choose Mx, y = 1.

This is the sub-matrix M[20, 20] with zeros replaced by dots for clarity:

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

For example, we have M1, 1 = 1 at the upper left corner, since 1 / (1 + 1) = ½, and the average of the 1 × 1 sub-matrix M[1, 1] is either 0 or 1; that's a tie, so we choose 1.

Consider then the position (3, 4).
We have 1 / (3 + 4) = 1/7, and the average of the sub-matrix M[3, 4] is 1/6 if we choose 0, and 3/12 if we choose 1.
The former is closer to 1/7, so we choose M3, 4 = 0.

Here is the sub-matrix M[800, 800] as an image, showing some of its intricate structure.

The task

Given a positive integer N < 1000, output the N × N sub-matrix M[N, N], in any reasonable format.
The lowest byte count wins.

R, 158 154 141  bytes
Edit: Because the only 1 in the upper 2x2 submatrix is the top left M[1,1] we can start the search for 1s when {x,y}>1 so no need for the if statement.
M=matrix(0,n<-scan(),n);M[1]=1;for(i in 2:n)for(j in 2:n){y=x=M[1:i,1:j];x[i,j]=0;y[i,j]=1;d=1/(i+j);M[i,j]=abs(d-mean(x))>=abs(d-mean(y))};M

The solution is highly inefficient as the matrix is duplicated twice for each iteration. n=1000 took just under two and a half hours to run and produces a matrix of 7.6 Mb.
Ungolfed and explained
M=matrix(0,n<-scan(),n);                        # Read input from stdin and initialize matrix with 0s
M[1]=1;                                         # Set top left element to 1
for(i in 2:n){                                  # For each row
    for(j in 2:n){                              # For each column
        y=x=M[1:i,1:j];                         # Generate two copies of M with i rows and j columns
        x[i,j]=0;                               # Set bottom right element to 0
        y[i,j]=1;                               # Set bottom right element to 1
        d=1/(i+j);                              # Calculate inverse of sum of indices
        M[i,j]=abs(d-mean(x))>=abs(d-mean(y))   # Returns FALSE if mean(x) is closer to d and TRUE if mean(y) is
    }
};
M                                               # Print to stdout

Output for n=20
      [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10] [,11] [,12] [,13] [,14] [,15] [,16] [,17] [,18] [,19] [,20]
[1,]     1    0    0    0    0    0    0    0    0     0     0     0     0     0     0     0     0     0     0     0
[2,]     0    0    0    0    0    1    0    0    0     0     0     0     0     0     0     0     0     0     0     0
[3,]     0    0    1    0    0    0    0    0    0     0     0     0     0     0     0     0     0     0     0     0
[4,]     0    0    0    0    0    0    0    0    0     0     0     0     0     0     0     0     0     0     0     0
[5,]     0    0    0    0    1    0    0    0    0     0     0     0     0     0     0     0     0     0     0     0
[6,]     0    1    0    0    0    0    0    0    0     0     0     0     0     0     0     0     0     0     0     0
[7,]     0    0    0    0    0    0    0    0    0     0     0     0     0     0     0     0     0     0     0     0
[8,]     0    0    0    0    0    0    0    0    0     0     0     0     0     0     0     0     0     1     0     0
[9,]     0    0    0    0    0    0    0    0    0     0     0     0     0     0     1     0     0     0     0     0
[10,]    0    0    0    0    0    0    0    0    0     0     0     0     1     0     0     0     0     0     0     0
[11,]    0    0    0    0    0    0    0    0    0     0     1     0     0     0     0     0     0     0     0     0
[12,]    0    0    0    0    0    0    0    0    0     0     0     0     0     0     0     0     0     0     0     0
[13,]    0    0    0    0    0    0    0    0    0     1     0     0     0     0     0     0     0     0     0     0
[14,]    0    0    0    0    0    0    0    0    0     0     0     0     0     0     0     0     0     0     0     0
[15,]    0    0    0    0    0    0    0    0    1     0     0     0     0     0     0     0     0     0     0     0
[16,]    0    0    0    0    0    0    0    0    0     0     0     0     0     0     0     0     0     0     0     0
[17,]    0    0    0    0    0    0    0    0    0     0     0     0     0     0     0     0     0     0     0     0
[18,]    0    0    0    0    0    0    0    1    0     0     0     0     0     0     0     0     0     0     0     0
[19,]    0    0    0    0    0    0    0    0    0     0     0     0     0     0     0     0     0     0     0     0
[20,]    0    0    0    0    0    0    0    0    0     0     0     0     0     0     0     0     0     0     0     0


Number of coins needed to make change Relatable scenario: I'm going to the store to buy a single item, but only have a $100k bill. As a result, I need exactly $99,979 in change, and in the fewest coins/bills possible because I'm quite obviously a very practical person.
The denominations of these coins/bills follow the hyperinflation sequence: \$1, 2, 5, 10, 20, 50, 100, 200\$, and so on.
(I'd proposed an OEIS sequence for this, but the first 100k terms are identical to another one so it got rejected)
Task:
Given an amount of money as a nonnegative integer, such as \$73\$, return the minimum number of coins/bills needed to total to that amount. In this example, it would be \$4\$. The coins required would be \$50 + 20 + 2 + 1\$.
As per the standard rules for sequence, you can also choose to return all terms up to an inputted index, or return a (potentially infinite) lazy list or generator that represents the whole sequence.
Test cases:
0       0
1       1
2       1
3       2
4       2
5       1
6       2
7       2
8       3
9       3
10      1
11      2
20      1
30      2
37      4
90      3
111     3
147     5
1000    1
1002    2
1010    2
12478   9

Other:
This is code-golf, so shortest answer in bytes per language wins!

JavaScript (ES7),  36  35 bytes
Similar to other answers. Using a Black Magic formula instead of a lookup table.

f=n=>n&&(n%10)**29%3571%4+f(n/10|0)

Try it online!
Here is a script that looks for \$(p,m)\$ pairs such that \$(n^p\bmod m)\bmod 4=a_n\$ for all \$n\in[0..9]\$.
It's worth noting that this code takes IEEE-754 precision errors into account. So the results are correct but the math is wrong.
With exact values, we could do instead:
$$\big((n \bmod 10)^{18}\bmod 4011\big)\bmod 4$$
Or better yet, as suggested by @dingledooper:
$$\big((n \bmod 10)^{55}\bmod 767\big)\bmod 4$$
For instance, in Python:
Python 2, 40 bytes

f=lambda n:n and(n%10)**55%767%4+f(n/10)

Try it online!

JavaScript (ES7), 71 bytes
Expects the amount as a string.
A naive recursive approach that subtracts one coin/bill at a time.

n=>(k=10**n.length,g=t=>+n?k>n?g(t,k/=~++i%3?2:2.5):g(t+1,n-=k):t)(i=0)

Try it online!