title: Who's the king of the tournament?

text:
# Question
Title: Who's the king of the tournament?
## Background

Consider a round-robin tournament, in which each contestant plays one game against every other contestant. There are no draws, so every game has a winner and a loser. A contestant **A** is a *king* of the tournament, if for every other contestant **B**, either **A** beat **B**, or **A** beat another contestant **C** who in turn beat **B**. It can be shown that every tournament has at least one king (although there may be several). In this challenge, your task is to find the kings of a given tournament.

## Input and output

Your input is an `N × N` boolean matrix `T`, and optionally the number `N ≥ 2` of contestants. Each entry `T[i][j]` represents the outcome of the game between contestants `i` and `j`, with value 1 representing a win for `i` and 0 a win for `j`. Note that `T[i][j] == 1-T[j][i]` if `i != j`. The diagonal of `T` consists of 0s.

Your output shall be the list of kings in the tournament that `T` represents, using either 0-based or 1-based indexing. The order of the kings is irrelevant, but there should not be duplicates.

Both input and output can be taken in any reasonable format.

## Rules and scoring

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

## Test cases

These test cases use 0-based indexing. For 1-based indexing, increment each output value.

```
 2 [[0,0],[1,0]] -> [1]
 3 [[0,1,0],[0,0,0],[1,1,0]] -> [2]
 3 [[0,1,0],[0,0,1],[1,0,0]] -> [0,1,2]
 4 [[0,1,1,1],[0,0,1,0],[0,0,0,0],[0,1,1,0]] -> [0]
 4 [[0,1,1,0],[0,0,1,0],[0,0,0,1],[1,1,0,0]] -> [0,2,3]
 5 [[0,1,0,0,1],[0,0,0,0,1],[1,1,0,0,0],[1,1,1,0,1],[0,0,1,0,0]] -> [3]
 5 [[0,1,0,1,0],[0,0,1,1,1],[1,0,0,0,0],[0,0,1,0,1],[1,0,1,0,0]] -> [0,1,4]
 5 [[0,0,0,0,0],[1,0,1,1,0],[1,0,0,0,1],[1,0,1,0,1],[1,1,0,0,0]] -> [1,3,4]
 6 [[0,0,0,0,0,0],[1,0,1,1,0,0],[1,0,0,1,1,0],[1,0,0,0,1,1],[1,1,0,0,0,1],[1,1,1,0,0,0]] -> [1,2,3,4,5]
 6 [[0,0,1,1,1,0],[1,0,0,1,1,1],[0,1,0,0,1,0],[0,0,1,0,0,1],[0,0,0,1,0,1],[1,0,1,0,0,0]] -> [0,1,2,3,5]
 6 [[0,1,1,0,0,1],[0,0,0,1,0,1],[0,1,0,1,1,0],[1,0,0,0,1,1],[1,1,0,0,0,0],[0,0,1,0,1,0]] -> [0,1,2,3,4,5]
 8 [[0,0,1,1,0,1,1,1],[1,0,1,0,1,1,0,0],[0,0,0,1,1,0,0,0],[0,1,0,0,0,1,0,0],[1,0,0,1,0,1,0,0],[0,0,1,0,0,0,1,0],[0,1,1,1,1,0,0,1],[0,1,1,1,1,1,0,0]] -> [0,1,4,6,7]
20 [[0,0,1,1,0,1,1,0,0,0,0,1,1,0,1,1,1,1,0,1],[1,0,1,1,1,0,1,1,1,1,1,0,1,1,1,1,1,1,1,1],[0,0,0,1,0,0,0,1,1,0,1,0,1,0,0,0,0,0,1,1],[0,0,0,0,1,1,1,1,1,1,1,1,0,0,1,0,0,1,1,1],[1,0,1,0,0,0,0,1,1,0,1,1,1,0,1,1,1,1,0,1],[0,1,1,0,1,0,1,1,1,1,1,0,1,1,1,0,1,1,0,1],[0,0,1,0,1,0,0,1,1,0,1,0,1,1,1,1,1,0,1,0],[1,0,0,0,0,0,0,0,1,0,1,1,1,1,0,0,1,1,1,0],[1,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,0,1,1],[1,0,1,0,1,0,1,1,0,0,1,0,0,0,0,1,0,1,1,1],[1,0,0,0,0,0,0,0,0,0,0,1,1,1,0,1,0,0,0,0],[0,1,1,0,0,1,1,0,0,1,0,0,1,1,1,1,1,0,1,1],[0,0,0,1,0,0,0,0,0,1,0,0,0,0,1,1,0,1,1,1],[1,0,1,1,1,0,0,0,0,1,0,0,1,0,1,1,1,1,1,1],[0,0,1,0,0,0,0,1,0,1,1,0,0,0,0,1,1,0,0,1],[0,0,1,1,0,1,0,1,0,0,0,0,0,0,0,0,0,1,1,1],[0,0,1,1,0,0,0,0,0,1,1,0,1,0,0,1,0,0,1,1],[0,0,1,0,0,0,1,0,1,0,1,1,0,0,1,0,1,0,1,1],[1,0,0,0,1,1,0,0,0,0,1,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,1,1,0,0,1,0,0,0,0,0,0,0,1,0]] -> [0,1,3,4,5,7,8,11,15,17,18]

```

# Answer
> 9 votes
# Matlab, ~~36 35~~ 29 bytes

```
@(T,N)find(sum(T*T>-T,2)>N-2)

```

Let us find out if `i` is a king. Then for each `j` the value `T[i][j]==1 OR there is a k such that T[i][k] * T[k][l] == 1`. But the second condition can also be replaced by `sum_over_k(T[i][k] * T[k][l])>0`, but this is just an entry of the matrix `T*T` (if you consider `T` as a matrix). The `OR` can then be replayed by adding `T` to that result, so we just have to check if `n-1` values of the row `i` of `T*T+T` are greater than zero, to see whether `i` is king. This is exactly what my function does.

(This is MATLAB, so the indices are 1-based.)

The MATLAB matrices should be encoded with semicolons as line delimiters:

```
[[0,0,0,0,0];[1,0,1,1,0];[1,0,0,0,1];[1,0,1,0,1];[1,1,0,0,0]]

```

# Answer
> 7 votes
# Jelly, ~~13~~ ~~12~~ 11 bytes

```
a"€¹o/€oḅ1M

```

Output is 1-based. Try it online!

Alternatively, using bitwise operators instead of array manipulation:

```
×Ḅ|/€|ḄBS€M

```

Again, output is 1-based. Try it online!

### Background

For contestant **A**, we can find all **B** such that **A beat C beat B** by taking all rows that correspond to a **C** such that **C beat A**. Ifr the **B**th entry of the **Cth** is **1**, we have that **C beat B**.

If we compute the logical ORs of all corresponding entries of the selected columns, we get a a single vector indicating whether **A beat B** by transitivity or not. Finally, ORing the resulting vector with the corresponding row of the input matrix gives Booleans whether **A beat B**, either by transitivity or directly.

Repeating this for every row, we count the number of **1**'s in each vector, therefore computing the amount of contestants each **A** beat. Maximal counts correspond to kings of the tournament.

### How it works

```
a"€¹o/€oḅ1M  Main link. Argument: M (matrix)

   ¹         Yield M.
  €          For each row of M:
a"           Take the logical AND of each entry of that row and the corr. row of M.
    o/€      Reduce each resulting matrix by logical OR.
       o     Take the logical OR of the entries of the resulting maxtrix and the
             corr. entries of M.
        ḅ1   Convert each row from base 1 to integer, i.e. sum its elements.
          M  Get all indices of maximal sums.

```

```
×Ḅ|/€|ḄBS€M  Main link. Argument: M (matrix)

 Ḅ           Convert each row of M from base 2 to integer. Result: R
×            Multiply the entries of each column of M by the corr. integer.
  |/€        Reduce each row fo the resulting matrix by bitwise OR.
     |Ḅ      Bitwise OR the results with R.
       BS€   Convert to binary and reduce by sum.
             This counts the number of set bits for each integer.
          M  Get all indices of maximal popcounts.

```

# Answer
> 2 votes
## Python using numpy, 54 bytes

```
import numpy
lambda M:(M**0+M+M*M).all(1).nonzero()[0]

```

Takes in a numpy matrix, outputs a numpy row matrix of 0-based indices.

Another way to think of a king is as a contestant for which all contestants are in the union of the king, the people the king beat, and the people those people beat. In other words, for every contestant, there is a path of length at most 2 from the king to them among the "beat" relation.

The matrix `I + M + M*M` encodes the numbers of paths of 0, 1, or 2 steps from each source to each target. A player is a king if their row of this matrix has only positive entries. Since 0 is Falsey, `all` tells us if a row is all nonzero. We apply this to each row and output the indices of the nonzero results.

# Answer
> 2 votes
# MATL, ~~12~~ ~~10~~ 9 bytes

```
Xy+HY^!Af

```

Input is: first the number of contestants, and on a separate line a matrix with rows separated by semicolons. Output is 1-based.

For example, the fifth test case has input

```
4
[0,1,1,0; 0,0,1,0; 0,0,0,1; 1,1,0,0]

```

and the last test case has input

```
20
[0,0,1,1,0,1,1,0,0,0,0,1,1,0,1,1,1,1,0,1; 1,0,1,1,1,0,1,1,1,1,1,0,1,1,1,1,1,1,1,1; 0,0,0,1,0,0,0,1,1,0,1,0,1,0,0,0,0,0,1,1; 0,0,0,0,1,1,1,1,1,1,1,1,0,0,1,0,0,1,1,1; 1,0,1,0,0,0,0,1,1,0,1,1,1,0,1,1,1,1,0,1; 0,1,1,0,1,0,1,1,1,1,1,0,1,1,1,0,1,1,0,1; 0,0,1,0,1,0,0,1,1,0,1,0,1,1,1,1,1,0,1,0; 1,0,0,0,0,0,0,0,1,0,1,1,1,1,0,0,1,1,1,0; 1,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,0,1,1; 1,0,1,0,1,0,1,1,0,0,1,0,0,0,0,1,0,1,1,1; 1,0,0,0,0,0,0,0,0,0,0,1,1,1,0,1,0,0,0,0; 0,1,1,0,0,1,1,0,0,1,0,0,1,1,1,1,1,0,1,1; 0,0,0,1,0,0,0,0,0,1,0,0,0,0,1,1,0,1,1,1; 1,0,1,1,1,0,0,0,0,1,0,0,1,0,1,1,1,1,1,1; 0,0,1,0,0,0,0,1,0,1,1,0,0,0,0,1,1,0,0,1; 0,0,1,1,0,1,0,1,0,0,0,0,0,0,0,0,0,1,1,1; 0,0,1,1,0,0,0,0,0,1,1,0,1,0,0,1,0,0,1,1; 0,0,1,0,0,0,1,0,1,0,1,1,0,0,1,0,1,0,1,1; 1,0,0,0,1,1,0,0,0,0,1,0,0,0,1,0,0,0,0,0; 0,0,0,0,0,0,1,1,0,0,1,0,0,0,0,0,0,0,1,0]

```

**Try it online!**

### Explanation

```
Xy    % Implicitly take input: number. Push identity matrix with that size
+     % Implicitly take input: matrix. Add to identity matrix
HY^   % Matrix square
!     % Transpose
A     % Row vector with true entries for columns that contain all nonzero values
f     % Indices of nonzero values

```

# Answer
> 2 votes
## JavaScript (ES6), 83 bytes

```
a=>a.map((b,i)=>b.every((c,j)=>c|i==j|b.some((d,k)=>d&a[k][j]))&&r.push(i),r=[])&&r

```

# Answer
> 1 votes
# Javascript ~~136~~ ~~131~~ ~~121~~ 112 bytes

```
(n,m)=>m.map((a,k)=>eval(a.map((o,i)=>o||eval(a.map((p,j)=>p&&m[j][i]).join`|`)).join`+`)>n-2&&k+1).filter(a=>a)

```

---

Call using:

```
f=(n,m)=>m.map((a,k)=>eval(a.map((o,i)=>o||eval(a.map((p,j)=>p&&m[j][i]).join`|`)).join`+`)>n-2&&k+1).filter(a=>a)

f(20,[[0,0,1,1,0,1,1,0,0,0,0,1,1,0,1,1,1,1,0,1],
     [1,0,1,1,1,0,1,1,1,1,1,0,1,1,1,1,1,1,1,1],
     [0,0,0,1,0,0,0,1,1,0,1,0,1,0,0,0,0,0,1,1],
     [0,0,0,0,1,1,1,1,1,1,1,1,0,0,1,0,0,1,1,1],
     [1,0,1,0,0,0,0,1,1,0,1,1,1,0,1,1,1,1,0,1],
     [0,1,1,0,1,0,1,1,1,1,1,0,1,1,1,0,1,1,0,1],
     [0,0,1,0,1,0,0,1,1,0,1,0,1,1,1,1,1,0,1,0],
     [1,0,0,0,0,0,0,0,1,0,1,1,1,1,0,0,1,1,1,0],
     [1,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,0,1,1],
     [1,0,1,0,1,0,1,1,0,0,1,0,0,0,0,1,0,1,1,1],
     [1,0,0,0,0,0,0,0,0,0,0,1,1,1,0,1,0,0,0,0],
     [0,1,1,0,0,1,1,0,0,1,0,0,1,1,1,1,1,0,1,1],
     [0,0,0,1,0,0,0,0,0,1,0,0,0,0,1,1,0,1,1,1],
     [1,0,1,1,1,0,0,0,0,1,0,0,1,0,1,1,1,1,1,1],
     [0,0,1,0,0,0,0,1,0,1,1,0,0,0,0,1,1,0,0,1],
     [0,0,1,1,0,1,0,1,0,0,0,0,0,0,0,0,0,1,1,1],
     [0,0,1,1,0,0,0,0,0,1,1,0,1,0,0,1,0,0,1,1],
     [0,0,1,0,0,0,1,0,1,0,1,1,0,0,1,0,1,0,1,1],
     [1,0,0,0,1,1,0,0,0,0,1,0,0,0,1,0,0,0,0,0],
     [0,0,0,0,0,0,1,1,0,0,1,0,0,0,0,0,0,0,1,0]])

```

watchout because output is 1-indexed (saved a few bytes not trying to filter out 0s vs falses)

---
Tags: code-golf, array
---


# Question
Title: Program touch-tone instructions for my fingers
The keypad on my office phone has the following layout:

```
[1]  [2]  [3]
/.@  ABC  DEF

[4]  [5]  [6]
GHI  JKL  MNO

[7]  [8]  [9]
PQRS TUV WXYZ

[*]  [0]  [#]
 +    _

```

### Task:

Write a program that, given an input string, returns a list of instructions that my fingers need to follow in order the type/dial the message/number.

### Rules:

* 3 fingers (1,2 & 3) start on keys \[4\], \[5\] and \[6\]. This starting position is 0.
* The only instruction a finger receives is its new relative location.
* Once a key has been pressed, that is the finger's new starting position. Fingers do not return to their 'home row'.
* Moving a finger up the keypad's column is -1, -2 or -3, depending on where it was last used.
* Moving a finger down the keypad's column is 1, 2 or 3, depending on where it was last used.
* Keeping a finger on the same key means there is no movement (0). It is not included.
* Words which require a double letter (like 'OO' in 'BOOK' or 'DE' in CODE) will need a pause (P) between letters.
* When using Pause, the finger is not specified.
* A finger can only press the keys in its own column (1,4,7,\*) (2,5,8,0) (3,6,9,#)
* Typing certain letters requires multiple keypresses. To type 'F', 3 needs to be pressed 3 times.
* Input is not case sensitive.
* Input characters not available on the keypad should be ignored. (Hyphens and parenthesis of a phone number, for example)
* Input will either be alpha or numeric - not a mixture - so no need to switch between input methods mid-stream.
* When entering numbers, Pauses aren't necessary.
* This is so shortest code in bytes wins.

### Update

To slightly simplify matters, \[\*\] and \[#\] can be ignored. These will not feature in the input. But I'll buy you a beer if you do include them and get lowest byte count! (If you're in London ;-))

### Output:

A list of instructions, in the following format:

```
[direction] [finger_number] [new_relative_location], ...

```

Whitespace between instructions is optional.

### Test cases:

```
(123)-957 -> -11, -21, -31, 32, 21, 12
555-9273 -> 2,2,2,31,-21,11,-32
CODE GOLF -> -21,2,2, 3,3,3, -31, P, 3,3, 23, 1, 31,3,3, -22,2,2, -31,3,3
Code Golf -> -21,2,2, 3,3,3, -31, P, 3,3, 23, 1, 31,3,3, -22,2,2, -31,3,3

```

# Answer
> 1 votes
# Python 2, 423 bytes (no \*/# support)

```
k='/.@~ABC~DEF~GHI~JKL~MNO~PQRSTUV~WXYZ+~~~ '
d='123456789~0'
g={c:(i/12,i%12/4,i%4)for i,c in enumerate(k)}
g.update(((c,(i/3,i%3,0))for i,c in enumerate(d)))
del g['~']
def f(s):
 s,a=[c for c in s[::-1].upper() if c in g],[]
 q=[1,1,1]
 while s:
  y,x,r=g[s.pop()]
  n,m,_=(9,9,9)if not s else g[s[-1]]
  v=y-q[x]
  q[x]=y
  a+=[(v<0)*'-'+`x+1`+(v!=0)*`abs(v)`]+r*[`x+1`]+(c in k and(y,x)==(n,m))*['P']
 print','.join(a)

```

# Answer
> 0 votes
### Java, 701

```
static void main(String a[]){int q[]={1,1,1},w[]={0,0,0},f=9,n=0,p=1,x,y,r,l=0,d;String c,i=String.join(" ",a),o="";i=i.replaceAll("[^A-Za-z0-9/.@*#+ ]+", "").toUpperCase();String[]v="1/.@|4GHI|7PQRS&2ABC|5JKL|8TUV|0 &3DEF|6MNO|9WXYZ".split("&");for(;l<i.length();){c=""+i.charAt(l++);for(x=0;x<3;x++)if(v[x].contains(c)){n=x;String[]b=v[x].split("\\|");for(y=0;y<b.length;y++)if(b[y].contains(c)) {w[x]=y;p=b[y].indexOf(c);}}if(f==n&&q[f]==w[f]){if(i.matches("[^0-9]+"))o+="P,";for(r=0;r<p;r++)o+=(f+1)+",";}else{d=w[n]-q[n];if(d!=0)o+=d;for(r=0;r<p;r++){o=new StringBuilder(o).insert(d==0?o.length():o.length()-1,n+1).toString();d=0;o+=",";}}q[n]=w[n];f=n;}System.out.print(o.replaceAll(",$",""));}}

```

### Completely unoptimised and ungolfed

A starting point

```
public class Keypad {

public static void main(String a[]){

    int fingerRow[] = {1,1,1}, nextFingerRow[]=new int[3], finger=-1, nextFinger=0, repeat=1;
    String input = String.join(" ",a), out="";
    input=input.replaceAll("[^A-Za-z0-9/.@*#+ ]+", "").toUpperCase(); //strip nonsense
    System.out.println(input);
    boolean numbersOnly = input.charAt(0)>47 && input.charAt(0)<58;

    String[] columns = "1/.@|4GHI|7PQRS&2ABC|5JKL|8TUV|0 &3DEF|6MNO|9WXYZ".split("&");

    for (int l=0;l<input.length();l++) {
        // current letter
        String letter = ""+input.charAt(l);

        // find finger
        for (int i=0; i<3; i++) {
            if (columns[i].contains(letter)) {
                nextFinger = i;
                // find row
                String[] buttons = columns[i].split("\\|");
                for (int j=0; j<buttons.length; j++) {
                    if (buttons[j].contains(letter)) {
                        nextFingerRow[i]=j;
                        repeat=buttons[j].indexOf(letter);
                    }
                }
            }
        }

        // both same && letter? Add Pause.
        if (finger==nextFinger && fingerRow[finger]==nextFingerRow[finger]){
            if (!numbersOnly) out += "P,";
            for (int r=0; r<repeat;r++) {
                out += (finger+1)+",";
            }
        }
        else {
            // work out previous to current
            int distance = nextFingerRow[nextFinger] - fingerRow[nextFinger];
            if(distance!=0) out+=distance;
            // add finger
            for (int r=0; r<repeat;r++) {
                out = new StringBuilder(out).insert(distance==0?out.length():out.length()-1, nextFinger+1).toString();
                distance=0;
                out+=",";
            }
        }
        fingerRow[nextFinger] = nextFingerRow[nextFinger];
        finger = nextFinger;
    }
    System.out.println(out.replaceAll(",$",""));
}
}

```

### Sample run

```
CODE GOLF
-21,2,2,3,3,3,-31,P,3,3,23,1,31,3,3,-22,2,2,-31,3,3

```

---
Tags: code-golf
---


title: Human Friendly Filename Detection

text:
# Question
Title: Human Friendly Filename Detection
# Introduction

File names can be wildly varying things, ranging from a simple `blah.txt` to `303549020150514101638190-MSP0.txt`. The former is usually human generated, while the latter is often machine generated. Wouldn't it be nice to have a simple function to make educated guesses on whether or not a file might be considered "human-friendly"?

Inspired by a post by Eduard Florinescu that has since been deleted. His idea was good, but just needed a little fleshing out.

# Challenge

Write a program or function in the language of your choice that can take an string, and determine if it is considered "human-friendly", as defined by this challenge.

Some further details and rules are as follows:

* Input will be a string consisting of the 95 printable ascii characters.
* "human-friendly" shall be defined thusly:
    + Exclude the extension in the consideration. An extension is defined as the final period followed by a series of alpha-numeric characters (as few as 1, as many as 6).
    + No more than half of the string by length (excluding extension) may consist of the following defined groupings of characters (combined):
        - Decimal characters longer than 8 in a row.
        - Hexadecimal characters (upper xor lower case) of at least 16 in a row (must consist of letters and numbers, and of which at least a third of the characters are numbers).
        - Base64 characters (using `%+=` as the special characters) of at least 12 in a row (must consist of letters and numbers, be mixed case, and of which at least a third of the characters are uppercase letters).
    + If any of the above groupings overlap in definition (such as one that qualifies as base64, but has 8 digits in a row), choose the longest of them to be excluded.
* Output should be a truthy or falsy value, depending on if the string is considered "human-friendly" or not.
* Assume that only valid input will be used. Don't worry about error handling.

The winner will be determined by the shortest program/function. They will be selected in at least 7 days, or if/when there have been enough submissions. In the event of a tie, the answer that came earlier wins.

# Examples

Here's a few examples of input and output that your code should be able to handle:

```
"results_for__michael_greer.txt.zip" => true

"Georg Feuerstein - Connecting the Dots.pdf" => true

"M People - Search for the Hero-ntuqTuc6HxM.mp4" => true

"index.html?v=QTR4WGVTUzFsV3d8NHxvcmlnaW5hbHx8MTExMTAxBHxodHRwOi8vLCwsLHRyLDcsMA%3D%3D.html" => false

"ol2DCE0SIyQC(173).pdf" => false

"d41d8cd98f00b204e9800998ecf8427e.md5" => false

"12792331_807918856008495_7076645197310150318_o.jpg" => false

```

# Answer
> 1 votes
# Javascript, 466 bytes

```
s=>(s=s.split(/\.[a-z\d]{1,6}$/i)[j=d=0],h=s[l='length']/2|0,m=[],g=r=>(++j,m=m.concat((s[n='match'](r)||[]).map(x=>[x,j]))),p='replace',g(/\d{9,}/g),g(/[\da-f]{16,}/ig),g(/[\da-z%+=]{12,}/ig),m.sort((x,y)=>y[0][l]-x[0][l]).every(x=>x[1]-1?x[1]-2?s=s[p](x[0],y=>y[n](/[a-z]/)&&y[n](/\d/)&&(y+'A')[n](/[A-Z]/g)[l]>y[l]/3|0?(d+=y[l],''):y):s=s[p](x[0],y=>!!y[n](/[A-F]/)^!!y[n](/[a-f]/)&&(y+'0')[n](/\d/g)[l]>y[l]/3|0?(d+=y[l],''):y):(s=s[p](z=x[0],''),d+=z[l])),d<=h)

```

Explaining:

```
f=s=>(                                 // f: take string s (filename) as input
    s=s.split(/\.[a-z\d]{1,6}$/i)[j=d=0],  // s: input without extension
                                           // d: combined rules' sum
                                           // j: combined rule-number step
    h=s[l='length']/2|0,                   // h: half string
                                           // l: length
    m=[],                                  // m: matches
    g=r=>(++j,                             // j: next combined rule number
        m=m.concat(                            // m: join
            (s[n='match'](r)||[]).map(             // new (r)egex-matches
            x=>[x,j])                              // mapped with its rule number
    )),p='replace',                        // p: replace
    g(/\d{9,}/g),                          // combined rules §1
    g(/[\da-f]{16,}/ig),                   // combined rules §2
    g(/[\da-z%+=]{12,}/ig),                // combined rules $3
    m.sort((x,y)=>y[0][l]-x[0][l])         // matches ordered by length
        .every(x=>x[1]-1?                      // for combined rule §1
            x[1]-2?                                // for combined rule §2
                s=s[p](x[0],y=>                        // for combined rule §3
                    y[n](/[a-z]/)&&y[n](/\d/)&&            // if lower and digit and
                    (y+'A')[n](/[A-Z]/g)[l]>y[l]/3|0?      // upper at least `total/3`
                (d+=y[l],''):y)                        // replace by empty and sum up `d`
            :s=s[p](x[0],y=>                       // replace if
                !!y[n](/[A-F]/)^!!y[n](/[a-f]/)&&      // (upper xor lower case) and
                (y+'0')[n](/\d/g)[l]>y[l]/3|0?         // digits: at least `total/3`
            (d+=y[l],''):y)                        // by empty and sum up `d`
        :(s=s[p](z=x[0],''),d+=z[l]))          // no treatment
    ,d<=h                                  // output if "no more than half of string"
);

["results_for__michael_greer.txt.zip",
"Georg Feuerstein - Connecting the Dots.pdf",
"M People - Search for the Hero-ntuqTuc6HxM.mp4",
"index.html?v=QTR4WGVTUzFsV3d8NHxvcmlnaW5hbHx8MTExMTAxBHxodHRwOi8vLCwsLHRyLDcsMA%3D%3D.html",
"ol2DCE0SIyQC(173).pdf",
"d41d8cd98f00b204e9800998ecf8427e.md5",
"12792331_807918856008495_7076645197310150318_o.jpg"]
.forEach(x=>document.body.innerHTML+='<pre>"'+x+'" => '+f(x)+'</pre>')
```

---
Tags: code-golf, string, classification
---


title: Choose Scenes for a Movie

text:
# Question
Title: Choose Scenes for a Movie
# Introduction

Finally the movie company is financing your film. They have given you a maximum budget and they also set the running time of your movie.

Now you can start with the pre-production. You have a bunch of scenes already planned, but not all of them will fit into the budget and the film would get way too long as well. You know however the importance of each scene. You goal is to choose scenes, that the movie is not going to be too expensive, too long and mediocre.

# Input

You get the `running time` and the `budget` the studio has approved:

```
[25, 10]

```

You have the list of scenes including `running time`, `costs` and the `importance` for each of them:

```
[ [5, 2, 4], [7, 1, 3] ]

```

If arrays aren't working for you, choose another input format that suits your best. Times are in minutes. Budget and costs are in millions of random currency. The importance is a range from `[1–9]`. All numbers are integers.

# Output

Output the list of scenes to be included into the movie in the matter that:

* The sum of `importance` is maximized.
* The costs do not exceed the budget.
* The length is within a ±5 minutes range of the approved running time.

The order of scenes is unimportant and doesn't need to be preserved.

You can output a list of numbers or an array. Your output can have a zero- or a one-based index:

```
[0,2,5] – 0, 2, 5 – 0 2 5
[1,3,6] – 1, 3, 6 – 1 3 6

```

It may be possible, that multiple solutions apply to any given input. You only need to find one.

# Constraints

* Scenes can't be shortened nor can they get cheaper.
* Each scene can only be included once.

# Requirements

* Your program must finish in the time of the movie's actual length.
* Input is accepted from `STDIN`, command line arguments, as function parameters or from the closest equivalent.
* You can write a program or a function. If it is an anonymous function, please include an example of how to invoke it.
* This is so shortest answer in bytes wins.
* Standard loopholes are disallowed.

# Movies

Your first movie is a documentary about a small town in Germany called Knapsack1. This city was resettled due to environmental constraints in the 70s:

```
Movie: [25, 10]

Scenes: [
    [5,  2, 4],
    [5,  5, 7],
    [7,  1, 3],
    [8,  5, 3],
    [12, 3, 9],
]

```

Possible solution with running time `22`, budget `10` and an importance of `20`:

```
0, 1, 4

```

---

Your next project is an episode of Fargo:

```
Movie: [45, 25]

Scenes: [
    [2,  1, 1],
    [8,  5, 9],
    [10, 6, 8],
    [10, 3, 6],
    [10, 9, 7],
    [11, 4, 3],
    [19, 5, 6],
]

```

Possible solution with running time `40`, budget `24` and an importance of `31`:

```
0, 1, 2, 3, 4

```

---

Finally here are the scenes for a movie where "*M. McConaughey travels to a distant galaxy only to find out that Matt Damon got there first.*":

```
Movie: [169, 165]

Scenes: [
    [5,  8,  2],
    [5,  20, 6],
    [6,  5,  8],
    [6,  10, 3],
    [7,  6,  5],
    [7,  9,  4],
    [7,  8,  9],
    [7,  9,  5],
    [8,  6,  8],
    [8,  8,  8],
    [8,  5,  6],
    [9,  5,  6],
    [9,  8,  5],
    [9,  4,  6],
    [9,  6,  9],
    [9,  8,  6],
    [9,  7,  8],
    [10, 22, 4],
    [10, 12, 9],
    [11, 7,  9],
    [11, 9,  8],
    [12, 11, 5],
    [15, 21, 7],
]

```

Possible solution with running time `169`, budget `165` and an importance of `133`:

```
1, 2, 4, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 18, 19, 20, 21, 22

```

---

1 Any resemblance between the challenge's problem and actual locales is entirely coincidental.

# Answer
## MATLAB, 100 bytes

```
function X=o(m,s)
X=find(bintprog(-1*s(:,3),[s(:,2)';s(:,1)';-1*s(:,1)'],[m(2);m(1)+5;5-m(1)])==1);

```

The Binary Optimization problem is solved through the *bintprog* function, available in Matlab2013b; this function was replaced by intlinprog in newer Matlab versions.

Inputs are a vector (m), for movie constraints, and a matrix (s), for the scenes. In particular m is a two-element row vector \[running\_time budget\], while s is a Nx3 matrix, where N is the number of the scenes and each row is made up of \[running\_time costs importance\].
> 4 votes

# Answer
# Python 3, ~~211~~ 197 bytes

This solution brute-forces every combination of scenes starting from combinations of all scenes all the way down to combinations of just one scene, then selects the combination of scenes that has maximum importance. Brute-forcing was used as the cost in time was not particularly great, though it is definitely exponential. The output is zero-indexed.

```
from itertools import*
def m(t,b,s):l=len(s);r=range(l);f=lambda y,k:sum(s[q][k]for q in y);return max([j for i in r for j in combinations(r,l-i)if t-6<f(j,0)<t+6and f(j,1)<=b],key=lambda n:f(n,2))

```

**Ungolfing:**

```
import itertools
def movie_scenes(time, budget, scenes):
    length = len(s)
    r = range(length)
    f = lambda film_list, index: sum(scenes[q][index]for q in film_list)
    importance = 0
    possible_films = []
    for num_scenes in r:
        for film in itertools.combinations(r, num_scenes):
            run_time = f(film, 0)
            cost = f(film, 1)
            if time-6 < run_time < time+6 and cost <= budget:
                possible_films.append(film)
    return max(possible_films, key = lambda film: f(film, 2)

```
> 2 votes

# Answer
# Ruby, ~~172~~ ~~166~~ 165 bytes

I should really start checking if the Ruby versions of my Python answers are golfier before posting those Python answers. At any rate, this is the same brute-force approach to optimization as before. Any tips on golfing are welcome, including those that involve some actual optimization techniques.

```
->t,b,s{l=s.size;r=[*0...l];f=->y,k{y.reduce(0){|z,q|z+s[q][k]}};v=[];r.map{|i|r.combination(l-i).map{|j|v<<j if(t-5..t+5)===f[j,0]&&f[j,1]<=b}};v.max_by{|n|f[n,2]}}

```

**Ungolfed:**

```
def movie(time, budget, scenes)
  len = scenes.size
  range = [*0...len]
  f = -> y,k {y.reduce(0) {|z,q| z + s[q][k]}}
  potential_films = []
  range.map do |i|
    range.combination(len-i).map do |j|
    # len - i because range being combined must be 0..(len-1) as these are indices
    # but the number of elements in the combinations must be 1..len
      if (time-5..time+5).include?(f[j,0]) && f[j,1] <= budget
        potential_films << j
      end
    end
  end
  return potential_films.max_by{|n|f[n,2]}
end

```
> 1 votes

# Answer
## Haskell, 125 bytes

```
(m,n)&s=snd$maximum[(sum i,q)|q<-filter(>=0)<$>mapM(:[-1])[0..length s-1],(t,b,i)<-[unzip3$map(s!!)q],sum b<=n,abs(sum t-m)<6]

```

Usage example: `(25,10) & [(5,2,4),(5,5,7),(7,1,3),(8,5,3),(12,3,9)]` -\> `[0,1,4]`.

How it works:

```
let m be the running time
    n    the budget
    s    the list of scenes

    q<-filter ... s-1]                         -- loop q through the list of
                                               -- subsequences of the indices of s
                                               -- (0 based) -- details see below
                          map(s!!)q            -- extract the elements for the
                                               -- given indices
                    unzip3                     -- turn the list of triples
                                               -- into a triple of lists
          (t,b,i)<-[               ]           -- bind t, b and i to the lists
                                    sum b<=n   -- keep q if the sum of budgets <= n
                              abs(sum t-m)<6   -- and the time is within range
  (sum i,q)                                    -- for all leftover q make a pair
                                               -- (overall importance, q)
sum$maximum                                    -- find the maximum and drop
                                               -- overall importance

subsequence building:

                   [0..length s-1]         -- for all indices i of s
            (:[-1])                        -- make a list [i,-1]
        mapM                               -- and make the cartesian product
                                           -- e.g. [0,1] -> [[0,-1],[1,-1]] ->
                                           -- [[0,1],[0,-1],[-1,1],[-1,-1]]
filter(>=0)<$>                             -- drop all -1
                                           -- -> [[0,1],[0],[1],[]]

```

Found the subsequence trick a while ago in an answer of @xnor. It's shorter than `subsequence` which requires `import Data.List`.
> 1 votes

---
Tags: code-golf, optimization
---


title: Toy store profits

text:
# Question
Title: Toy store profits
# The story

"2016? Al..right," grumbled toy seller Hilbert. He opened his eyes, wiped salad dressing trickling out of his ear and ate a morning kick-start cremeschnitte. Exemplar holidays. He needs to go to work now though, and finish the year's accounting.

Christmas is a very yielding period of the year, especially for his sales. Hilbert knows exactly how it works: A person comes into a shop and buys the first gift they are offered. They pay for it and run off to another shop. In practice, what the gift actually is doesn't really make a difference. The price is also irrelevant, provided it is not too high. It all depends on the time remaining until Christmas -- the shorter the time, the greater the remorse of the customers, the greater the price they are willing to pay.

All it takes for Hilbert is to look at his watch -- and he knows right away how much his customers can spend. He can easily take advantage of this fact: He just finds the most expensive gift he can sell to a given customer, and offer it to them. Only now has he realized that he forgot to employ this cunning strategy last year. That's gonna change though!

Nevertheless, Hilbert would like to know how much his business would have flourished, if he had actually used his grand scheme. He's managed to put together a list of people who came to his store, he is however not sure how much money he could have made on them.

# Your task (TL;DR)

The input consists of an *ascending* list of prices of available gifts, and a list of customers' budgets. The list of budgets is in the same order as the customers arrived to the shop -- with a condition that every customer is willing to pay at least as much as the previous one, meaning it is also ascending.

**For each customer, find the most expensive gift they are willing to pay for, and output it's price. If no gifts within the budget are available, output a `0`.**

You get a `-40%` characters bonus, if the asymptotic time complexity of your algorithm is `O(n+m)` (rather than the trivial `O(n*m)`) Where `n, m` are the lengths of the input lists.

This is , shortest bytes wins. Standard loopholes are prohibited.

# Example

Input:

```
1 2 2 2 5 7 10 20
1 1 2 3 6 6 15 21 21 22

```

Output:

```
1 0 2 2 5 2 10 20 7 0

```

---

This task was taken from a local programming competition, and translated to English by me. Here is the original assignment: https://www.ksp.sk/ulohy/zadania/1131/

# Answer
# Pyth, ~~17~~ 16 bytes

*1 byte thanks to Pietu1998*

```
VE=.-Q]
e|fgNTQ0

```

Demonstration

**Explanation:**

```
VE=.-Q]<\n>e|fgNTQ0
                        Implicit: Q is the list of prices.
VE                      For N in the list of budgets
             f   Q      Filter the list of prices
              gNT       On the current person's budget being >= that price
            |     0     If there aren't any, use 0 instead.
          e             Take the last (most expensive) value.
      <\n>              Print it out.
  =.-Q                  Remove it from the list of prices.

```
> 5 votes

# Answer
## Haskell, 67 bytes

```
a#(b:c)|(h,t)<-span(<=b)a=last(0:h):(init(h++[0|h==[]])++t)#c
_#x=x

```

Usage example: `[1,2,2,2,5,7,10,20] # [1,1,2,3,6,6,15,21,21,22]` -\> `[1,0,2,2,5,2,10,20,7,0]`.

Split the prices in two parts: `(h,t)` where `h` are all prices \<= the budget of the next customer and `t` are all the others. Take the last price of `h` and continue recursively with all but the last of `h` plus `t` and the remaining budgets. `last(0:h)` evaluates to `0` if `h` is empty. Similar: `init (h++[0|h==[]]) ++ t` adds a dummy element `0` to `h` if `h` is empty, so that `init` has something to drop (`init` fails on the empty list).
> 4 votes

# Answer
## Java, 154 * 0.6 = 92.4 bytes

*-13 bytes because the lambda can actually use `int[]`, not `Integer[]` (thanks BunjiquoBianco)*

This should take O(n+m) time and O(n+m) additional space (assuming I understand big O notation).

```
g->b->{int l=g.length,L=b.length,G=0,B=0,A=0;int[]a=new int[l],s=new int[L];for(;B<L;){while(G<l&&g[G]<=b[B])a[A++]=g[G++];s[B++]=A>0?a[--A]:0;}return s;}

```

Indented: (Try it online!)

```
static int[] toyStore(int[]g,int[]b) {
    int gl=g.length,bl=b.length,gp=0,bp=0,ap=0;
    int[] a=new int[gl],s=new int[bl];
    for (;bp<bl;) {
        while(gp<gl&&g[gp]<=b[bp])a[ap++]=g[gp++];
        s[bp++]=ap>0?a[--ap]:0;
    }
    return s;
}

public static void main(String[] args)
{
    System.out.println(Arrays.toString(
        toyStore(new int[] {1,2,2,2,5,7,10,20},
                 new int[] {1,1,2,3,6,6,15,21,21,22})
        ));
}

```

I show the non-lambda expansion here because the type declaration is cleaner and it's the exact same logic. The lambda is present at the ideone link.

### Explanation:

Variables used:

* `g` is the list of gift prices, `b` is the list of budgets.
* `gl` is the length of `g` and `bl` is the length of `b`.
* `a` is a Stack for affordable gifts, `s` is the output array of sold gifts.
* `gp`, `bp`, and `ap` are pointers for `g`, `b`, and `a` respectively. `bp` is also the pointer for `s`.

Algorithm:

* For each budget in the length of budgets
    + While this budget can buy the gift at `g[gp]`
        - Push the budget onto the Stack `a` and increment `gp`
    + Pop the top of `a` into `s[bp]` if it exists, else put `0`.
> 3 votes

# Answer
## Haskell, 87 * 0.6 = 52.2 bytes

```
g s(p:q)d@(b:c)|p<=b=g(p:s)q d
g[]p(b:c)=0:g[]p c
g(s:t)p(b:c)=s:g t p c
g _ _ _=[]
g[]

```

Completely different from my other answer, because I'm going for the bonus.

The last line (-\> `g[]`) is not part of the definition, but calling overhead. Usage example: `g [] [1,2,2,2,5,7,10,20] [1,1,2,3,6,6,15,21,21,22]` -\> `[1,0,2,2,5,2,10,20,7,0]`.

Works basically in the same way as @CAD97's answer, i.e. uses a (initially empty) helper stack to keep track of the buyable items. In detail: check in order:

* if the first price is less or equal than the first budget, move the price to the stack. Call again.
* if the stack is empty, return a 0 followed by a recursive call with the budget dropped.
* if both stack and budget list are not empty, return the top of stack followed by a recursive call with stack & budget popped.
* else return the empty list.

This works in `m+n` time, because a) operations on the helper stack use constant time and b) in each of the recursive calls one of the lists is shortened by one element.
> 2 votes

# Answer
# Jelly, 15 bytes

```
ṀṄ;©®œ^
Rf@€ç/Ṁ

```

Try it online!

### How it works

```
ṀṄ;©®œ^  Helper link. Arguments: G, H (lists of affordable gifts)

Ṁ        Compute the maximum of G (0 if the list is empty).
 Ṅ       Print it.
  ; ®    Concatenate it with the register (initially 0).
   ©     Save the result in the register.
     œ^  Compute the multiset symmetric difference of the updated register and H.

Rf@€ç/Ṁ  Main link. Arguments: B (budgets), P (prices)

R        Range; replace each t in B with [1, ..., t].
 f@€     Intersect the list of prices with each budget range, obtaining, for each
         customer, the list of all gifts he's willing to pay for.
    ç/   Reduce the array of lists by the helper link.
         In each iteration, this computes and prints the most expensive gift for
         a customer, than removes the selected gift (and all previously
         selected gifts) from the next list.
      Ṁ  Compute the maximum of the resulting list, which corresponds to the last
         customer.

```
> 2 votes

# Answer
## JavaScript, 85 * 0.6 = 51 bytes

```
f=(a,b,s=[],[t,...u]=a,[v,...w]=b)=>v?t<=v?f(u,b,[...s,t]):[s.pop()|0,...f(a),w,s)]:[]

```

Another clone of @CAD97's answer.
> 1 votes

---
Tags: code-golf
---


title: Basic Latin character name to character

text:
# Question
Title: Basic Latin character name to character
Let's get back to basics!

* Your code, a complete program or function, must convert the official Unicode name of a printable Basic Latin character into the corresponding character. For example, for the input `LOW LINE` your code must output `_`.
* You only need to take a single character name as input.
* You cannot use any preexisting function or library, built-in or otherwise, which offers any logic relating specifically to Unicode character names (e.g. Python's `unicodedata`, Java's `Character.getName`, and so on.)
* For input other than one of these names, any behavior is acceptable.

This is code golf: shortest code in bytes wins.

To avoid any ambiguity, this is the full set of official character names we'll be using (borrowed from this question):

```
     SPACE
!    EXCLAMATION MARK
"    QUOTATION MARK
#    NUMBER SIGN
$    DOLLAR SIGN
%    PERCENT SIGN
&    AMPERSAND
'    APOSTROPHE
(    LEFT PARENTHESIS
)    RIGHT PARENTHESIS
*    ASTERISK
+    PLUS SIGN
,    COMMA
-    HYPHEN-MINUS
.    FULL STOP
/    SOLIDUS
0    DIGIT ZERO
1    DIGIT ONE
2    DIGIT TWO
3    DIGIT THREE
4    DIGIT FOUR
5    DIGIT FIVE
6    DIGIT SIX
7    DIGIT SEVEN
8    DIGIT EIGHT
9    DIGIT NINE
:    COLON
;    SEMICOLON
<    LESS-THAN SIGN
=    EQUALS SIGN
>    GREATER-THAN SIGN
?    QUESTION MARK
@    COMMERCIAL AT
A    LATIN CAPITAL LETTER A
B    LATIN CAPITAL LETTER B
C    LATIN CAPITAL LETTER C
D    LATIN CAPITAL LETTER D
E    LATIN CAPITAL LETTER E
F    LATIN CAPITAL LETTER F
G    LATIN CAPITAL LETTER G
H    LATIN CAPITAL LETTER H
I    LATIN CAPITAL LETTER I
J    LATIN CAPITAL LETTER J
K    LATIN CAPITAL LETTER K
L    LATIN CAPITAL LETTER L
M    LATIN CAPITAL LETTER M
N    LATIN CAPITAL LETTER N
O    LATIN CAPITAL LETTER O
P    LATIN CAPITAL LETTER P
Q    LATIN CAPITAL LETTER Q
R    LATIN CAPITAL LETTER R
S    LATIN CAPITAL LETTER S
T    LATIN CAPITAL LETTER T
U    LATIN CAPITAL LETTER U
V    LATIN CAPITAL LETTER V
W    LATIN CAPITAL LETTER W
X    LATIN CAPITAL LETTER X
Y    LATIN CAPITAL LETTER Y
Z    LATIN CAPITAL LETTER Z
[    LEFT SQUARE BRACKET
\    REVERSE SOLIDUS
]    RIGHT SQUARE BRACKET
^    CIRCUMFLEX ACCENT
_    LOW LINE
`    GRAVE ACCENT
a    LATIN SMALL LETTER A
b    LATIN SMALL LETTER B
c    LATIN SMALL LETTER C
d    LATIN SMALL LETTER D
e    LATIN SMALL LETTER E
f    LATIN SMALL LETTER F
g    LATIN SMALL LETTER G
h    LATIN SMALL LETTER H
i    LATIN SMALL LETTER I
j    LATIN SMALL LETTER J
k    LATIN SMALL LETTER K
l    LATIN SMALL LETTER L
m    LATIN SMALL LETTER M
n    LATIN SMALL LETTER N
o    LATIN SMALL LETTER O
p    LATIN SMALL LETTER P
q    LATIN SMALL LETTER Q
r    LATIN SMALL LETTER R
s    LATIN SMALL LETTER S
t    LATIN SMALL LETTER T
u    LATIN SMALL LETTER U
v    LATIN SMALL LETTER V
w    LATIN SMALL LETTER W
x    LATIN SMALL LETTER X
y    LATIN SMALL LETTER Y
z    LATIN SMALL LETTER Z
{    LEFT CURLY BRACKET
|    VERTICAL LINE
}    RIGHT CURLY BRACKET
~    TILDE

```

# Answer
> 26 votes
# IA-32 machine code, ~~161~~ ~~160~~ 122 bytes

Hexdump of the code:

```
33 c0 6b c0 59 0f b6 11 03 c2 b2 71 f6 f2 c1 e8
08 41 80 79 01 00 75 ea e8 39 00 00 00 08 2c 5e
4a bd a3 cd c5 90 09 46 04 06 14 40 3e 3d 5b 23
60 5e 3f 2d 31 32 29 25 2e 3c 7e 36 39 34 33 30
21 2f 26 7d 7c 2c 3b 7b 2a 37 5d 22 35 20 3a 28
5c 27 2b 38 5f 24 5a 3c 34 74 17 3c 1a 74 16 33
c9 86 c4 0f a3 0a 14 00 41 fe cc 75 f6 8a 44 02
0e c3 8a 01 c3 8a 01 04 20 c3

```

This code uses some hashing. By some brute-force search, I found that the following hash function can be applied to the bytes of the input string:

```
int x = 0;
while (s[1])
{
    x = (x * 89 + *s) % 113;
    ++s;
}

```

It multiplies `x` by 89, adds the next byte (ASCII-code), and takes a remainder modulo 113. It does this on all bytes of the input string except the last one, so e.g. `LATIN CAPITAL LETTER A` and `LATIN CAPITAL LETTER X` give the same hash code.

This hash function has no collisions, and the output is in the range 0...113 (actually, by luck, the range is even narrower: 3...108).

The hash values of all relevant strings don't fill that space completely, so I decided to use this to compress the hash table. I added a "skip" table (112 bits), which contains 0 if the corresponding place in the hash table is empty, and 1 otherwise. This table converts a hash value into a "compressed" index, which can be used to address a dense LUT.

The strings `LATIN CAPITAL LETTER` and `LATIN SMALL LETTER` give hash codes 52 and 26; they are handled separately. Here is a C code for that:

```
char find(const char* s)
{
    int hash = 0;
    while (s[1])
    {
        hash = (hash * 89 + *s) % 113;
        ++s;
    }

    if (hash == 52)
        return *s;
    if (hash == 26)
        return *s + 32;

    int result_idx = 0;
    int bit = 0;
    uint32_t skip[] = {0x4a5e2c08, 0xc5cda3bd, 0x04460990, 0x1406};
    do {
        if (skip[bit / 32] & (1 << bit % 32))
            ++result_idx;
        ++bit;
    } while (--hash);

    return "@>=[#`^?-12)%.<~69430!/&}|,;{*7]\"5 :(\\'+8_$"[result_idx];
}

```

The corresponding assembly language code (MS Visual Studio inline-assembly syntax):

```
_declspec(naked) char _fastcall find(char* s)
{
    _asm {
        xor eax, eax;
    mycalc:
        imul eax, eax, 89;
        movzx edx, [ecx];
        add eax, edx;
        mov dl, 113;
        div dl;
        shr eax, 8;
        inc ecx;
        cmp byte ptr [ecx + 1], 0;
        jne mycalc;

        call mycont;
        // skip table
        _asm _emit 0x08 _asm _emit 0x2c _asm _emit 0x5e _asm _emit 0x4a;
        _asm _emit 0xbd _asm _emit 0xa3 _asm _emit 0xcd _asm _emit 0xc5;
        _asm _emit 0x90 _asm _emit 0x09 _asm _emit 0x46 _asm _emit 0x04;
        _asm _emit 0x06 _asm _emit 0x14;
        // char table
        _asm _emit '@' _asm _emit '>' _asm _emit '=' _asm _emit '[';
        _asm _emit '#' _asm _emit '`' _asm _emit '^' _asm _emit '?';
        _asm _emit '-' _asm _emit '1' _asm _emit '2' _asm _emit ')';
        _asm _emit '%' _asm _emit '.' _asm _emit '<' _asm _emit '~';
        _asm _emit '6' _asm _emit '9' _asm _emit '4' _asm _emit '3';
        _asm _emit '0' _asm _emit '!' _asm _emit '/' _asm _emit '&';
        _asm _emit '}' _asm _emit '|' _asm _emit ',' _asm _emit ';';
        _asm _emit '{' _asm _emit '*' _asm _emit '7' _asm _emit ']';
        _asm _emit '"' _asm _emit '5' _asm _emit ' ' _asm _emit ':';
        _asm _emit '(' _asm _emit '\\' _asm _emit '\'' _asm _emit '+';
        _asm _emit '8' _asm _emit '_' _asm _emit '$';

    mycont:
        pop edx;
        cmp al, 52;
        je capital_letter;
        cmp al, 26;
        je small_letter;

        xor ecx, ecx;
        xchg al, ah;
    decode_hash_table:
        bt [edx], ecx;
        adc al, 0;
        inc ecx;
        dec ah;
        jnz decode_hash_table;

        mov al, [edx + eax + 14];
        ret;

    capital_letter:
        mov al, [ecx];
        ret;

    small_letter:
        mov al, [ecx];
        add al, 32;
        ret;
    }
}

```

Some noteworthy implementation details:

* It uses a `CALL` instruction to get a pointer to the code, where the hard-coded table resides. In 64-bit mode, it could use the register `rip` instead.
* It uses the `BT` instruction to access the skip table
* It manages to do the work using only 3 registers `eax`, `ecx`, `edx`, which can be clobbered - so there is no need to save and restore registers
* When decoding the hash table, it uses `al` and `ah` carefully, so that at the right place `ah` is decreased to 0, and the whole `eax` register can be used as a LUT index

# Answer
> 17 votes
# JavaScript ES6, 228 ~~236 247 257 267 274 287~~

Note: 7 chars saved thx @ev3commander

Note 2: **better than JAPT** after 7 major edits,

```
n=>n<'L'?"XC!DO$MP&OS'SK*N--FU.ZE0TW2HR3OU4FI5IX6EI8NI9EM;LS=R->IA@MF^AV`MM,NE1EN7LO:".replace(/(..)./g,(c,s)=>~n.search(s)?n=c[2]:0)&&n:'~  / ;  |?"\\ ) }]_+ #% < ( {['[(n<'Q')*13+n.length-(n>'T')-4]||n[21]||n[19].toLowerCase()

```

Run the snippet to test

```
F=n=>
  n<'L'?"XC!DO$MP&OS'SK*N--FU.ZE0TW2HR3OU4FI5IX6EI8NI9EM;LS=R->IA@MF^AV`MM,NE1EN7LO:"
  .replace(/(..)./g,(c,s)=>~n.search(s)?n=c[2]:0)&&n:
  '~  / ;  |?"\\ ) }]_+ #% < ( {['[(n<'Q')*13+n.length-(n>'T')-4]
  ||n[21]||n[19].toLowerCase()

//TEST
console.log=x=>O.innerHTML+=x+'\n'
;[
['&','AMPERSAND'],
['\'','APOSTROPHE'],
['*','ASTERISK'],
['^','CIRCUMFLEX ACCENT'],
[':','COLON'],
[',','COMMA'],
['@','COMMERCIAL AT'],
['8','DIGIT EIGHT'],
['5','DIGIT FIVE'],
['4','DIGIT FOUR'],
['9','DIGIT NINE'],
['1','DIGIT ONE'],
['7','DIGIT SEVEN'],
['6','DIGIT SIX'],
['3','DIGIT THREE'],
['2','DIGIT TWO'],
['0','DIGIT ZERO'],
['$','DOLLAR SIGN'],
['=','EQUALS SIGN'],
['!','EXCLAMATION MARK'],
['.','FULL STOP'],
['`','GRAVE ACCENT'],
['>','GREATER-THAN SIGN'],
['-','HYPHEN-MINUS'],
['A','LATIN CAPITAL LETTER A'],
['B','LATIN CAPITAL LETTER B'],
['C','LATIN CAPITAL LETTER C'],
['D','LATIN CAPITAL LETTER D'],
['E','LATIN CAPITAL LETTER E'],
['F','LATIN CAPITAL LETTER F'],
['G','LATIN CAPITAL LETTER G'],
['H','LATIN CAPITAL LETTER H'],
['I','LATIN CAPITAL LETTER I'],
['J','LATIN CAPITAL LETTER J'],
['K','LATIN CAPITAL LETTER K'],
['L','LATIN CAPITAL LETTER L'],
['M','LATIN CAPITAL LETTER M'],
['N','LATIN CAPITAL LETTER N'],
['O','LATIN CAPITAL LETTER O'],
['P','LATIN CAPITAL LETTER P'],
['Q','LATIN CAPITAL LETTER Q'],
['R','LATIN CAPITAL LETTER R'],
['S','LATIN CAPITAL LETTER S'],
['T','LATIN CAPITAL LETTER T'],
['U','LATIN CAPITAL LETTER U'],
['V','LATIN CAPITAL LETTER V'],
['W','LATIN CAPITAL LETTER W'],
['X','LATIN CAPITAL LETTER X'],
['Y','LATIN CAPITAL LETTER Y'],
['Z','LATIN CAPITAL LETTER Z'],
['a','LATIN SMALL LETTER A'],
['b','LATIN SMALL LETTER B'],
['c','LATIN SMALL LETTER C'],
['d','LATIN SMALL LETTER D'],
['e','LATIN SMALL LETTER E'],
['f','LATIN SMALL LETTER F'],
['g','LATIN SMALL LETTER G'],
['h','LATIN SMALL LETTER H'],
['i','LATIN SMALL LETTER I'],
['j','LATIN SMALL LETTER J'],
['k','LATIN SMALL LETTER K'],
['l','LATIN SMALL LETTER L'],
['m','LATIN SMALL LETTER M'],
['n','LATIN SMALL LETTER N'],
['o','LATIN SMALL LETTER O'],
['p','LATIN SMALL LETTER P'],
['q','LATIN SMALL LETTER Q'],
['r','LATIN SMALL LETTER R'],
['s','LATIN SMALL LETTER S'],
['t','LATIN SMALL LETTER T'],
['u','LATIN SMALL LETTER U'],
['v','LATIN SMALL LETTER V'],
['w','LATIN SMALL LETTER W'],
['x','LATIN SMALL LETTER X'],
['y','LATIN SMALL LETTER Y'],
['z','LATIN SMALL LETTER Z'],
['{','LEFT CURLY BRACKET'],
['(','LEFT PARENTHESIS'],
['[','LEFT SQUARE BRACKET'],
['<','LESS-THAN SIGN'],
['_','LOW LINE'],
['#','NUMBER SIGN'],
['%','PERCENT SIGN'],
['+','PLUS SIGN'],
['?','QUESTION MARK'],
['"','QUOTATION MARK'],
['\\','REVERSE SOLIDUS'],
['}','RIGHT CURLY BRACKET'],
[')','RIGHT PARENTHESIS'],
[']','RIGHT SQUARE BRACKET'],
[';','SEMICOLON'],
['/','SOLIDUS'],
[' ','SPACE'],
['~','TILDE'],
['|','VERTICAL LINE'],
].forEach(t=>{
  var r=F(t[1]),ok=r==t[0]
  //if (!ok) // uncomment to see just errors
  console.log(r+' ('+t[0]+') '+t[1]+(ok?' OK':' ERROR'))
})
console.log('DONE')
```

```
<pre id=O></pre>
```

# Answer
> 10 votes
# Japt, 230 bytes

```
V=U¯2;Ug21 ªU<'R©Ug19 v ªV¥"DI"©`ze¿twâ¿¿¿¿e¿i`u bUs6,8)/2ªUf"GN" ©"<>+=$#%"g`¤grp¤qºnupe`u bV /2 ªUf"T " ©"[]\{}()"g"QSUCAP"bUg6) ªUf" M" ©"!\"?"g"COE"bUg2) ªV¥"CO"©",:@"g"ANE"bUg4) ª" &'*-./\\;~^`_|"g`spaµpÂ¿è±¢¿Èögrlove`u bV /2

```

Each `¿` represents an unprintable Unicode char. Try it online!

Ungolfed:

```
V=Us0,2;Ug21 ||U<'R&&Ug19 v ||V=="DI"&&"zeontwthfofisiseeini"u bUs6,8)/2||Uf"GN" &&"<>+=$#%"g"legrpleqdonupe"u bV /2 ||Uf"T " &&"[]\{}()"g"QSUCAP"bUg6) ||Uf" M" &&"!\"?"g"COE"bUg2) ||V=="CO"&&",:@"g"ANE"bUg4) ||" &'*-./\\;~^`_|"g"spamapashyfusoreseticigrlove"u bV /2

```

This was really fun. I've split up the character names into several large chunks:

### 0. Take first two letters

`V=Us0,2;` sets variable `V` to the first two letters of `U`, the input string. This will come in handy later.

### 1. Capital letters

This is the easiest: the capital letters are the only ones that have a character at position 21, which all happen to be the correct letter and case. Thus, `Ug21` is sufficient.

### 2. Lowercase letters

Another fairly easy one; the only other name that has a character at position 19 is `RIGHT SQUARE BRACKET`, so we check if the name is comes before `R` with `U<'R`, then if it is (`&&`), we take the 19th char with `Ug19` and cast it to lowercase with `v`.

### 3. Digits

These names all start with `DI` (and fortunately, none of the others), so if `V=="DI"`, we can turn it into a digit. The first letters of some of the digits' names are the same, but the first two letters are sufficient. Combining these into one string, we get `ZEONTWTHFOFISISEEINI`. Now we can just take the index `b` of the first two chars in the digit's name with `Us6,8)`and divide by two.

### 4. `SIGN`

There are seven names that contain `SIGN`:

```
<    LESS-THAN SIGN
>    GREATER-THAN SIGN
+    PLUS SIGN
=    EQUALS SIGN
$    DOLLAR SIGN
#    NUMBER SIGN
%    PERCENT SIGN

```

First we check that it the name contains the word `SIGN`. It turns out `GN` is sufficient; `Uf"GN"` returns all instances of `GN` in the name, which is `null` if it contains 0 instances, and thus gets skipped.

Now, using the same technique as with the digits, we combine the first two letters into a string `LEGRPLEQDONUPE`, then take the index and divide by two. This results an a number from `0-6`, which we can use to take the corresponding character from the string `<>+=$#%`.

### 5. `MARK`

There are three characters that contain `MARK`:

```
!    EXCLAMATION MARK
"    QUOTATION MARK
?    QUESTION MARK

```

Here we use the same technique as with `SIGN`. `M` is enough to differentiate these three from the others. To translate to a symbol, this time checking one letter is enough: the character at position 2 is different for all three characters. This means we don't have to divide by two when choosing the correct character.

### 6. `LEFT/RIGHT`

This group contains the brackets and parentheses, `[]{}()`. It would be really complicated to capture both `LEFT` and `RIGHT`, but fortunately, they all contain the string . We check this with the same technique as we did with `SIGN`. To translate to a symbol, as with `MARK`, checking one letter is enough; the character at position 6 is unique for all six.

### 7. `CO`

The rest of the chars are pretty unique, but not unique enough. Three of them start with `CO`: `COMMA`, `COLON`, and `COMMERCIAL AT`. We use exactly the same technique as we did with the brackets, choosing the proper symbol based on the character at position 4 (`A`, `N`, or `E`).

### 8. Everything else

By now, the first two characters are different for every name. We combine them all into one big string `SPAMAPASHYFUSORESETICIGRLOVE` and map each pair to its corresponding char in `&'*-./\;~^`_|`.

### 9. Final steps

Each of the parts returns an empty string or `null` if it's not the correct one, so we can link them all from left to right with `||`. The `||` operator returns the left argument if it's truthy, and the right argument otherwise. Japt also has implicit output, so whatever the result, it is automatically sent to the output box.

Questions, comments, and suggestions welcome!

# Answer
> 3 votes
# Javascript, ~~501~~ ~~499~~ ~~469~~ ~~465~~ ~~451~~ 430 bytes

```
a=prompt();c="5SACEgEARKeQARKbNIGNbDIGNcPIGN9AANDaAPHEgLSIShRSIS8AISK9PIGN5CMMAcHNUS9FTOP7SDUSaDERO9DONE9DTWObDREEaDOURaDIVE9DSIXbDVENbDGHTaDINE5CLON9SLONeLIGNbEIGNhGIGNdQARKdC ATjLKETfRDUSkRKEThCENT8LINEcGENTiLKETdVINEjRKET5TLDE".match(/.{5}/g).indexOf(a.length.toString(36)+a[0]+a.slice(-3));if(c>=33)c+=26;if(c>=65)c+=26;alert(a.length==20&&a[0]=="L"?a.slice(-1).toLowerCase():a.length>21?a.slice(-1):String.fromCharCode(32+c))

```

# Explanation:

That long string is a compressed list. `a.length.toString(36)+a[0]+a.slice(-3)` determines how, if at all, the string will be represented in the list. Also, special logic for letters. (with strings, `a[0]` is a builtin shorthand for `a.charAt(0)`, by the way)

# Answer
> 3 votes
# Python 2, 237 bytes

Get the hash of the string and modulo divide it by 535. Subsequently convert it to a unicode character with that number. The position of the unicode character in a precompiled list of unicode characters is subsequently converted to the ascii character.

```
print chr(u"""ǶŀȎdȊÏöǖIhȏƜǓǱǠƣƚǆƩC+ĶÅĠěóƋŎªƱĳůŰűŪūŬŭŶŷŸŹŲųŴŵžſƀƁźŻżŽƆƇƈŖÐŗǀǼǿǾǹǸǻǺȅȄȇȆȁȀȃȂǭǬǯǮǩǨǫǪǵǴǷNȌ~B""".index(unichr(hash(raw_input())%535))+32)

```

# Answer
> 1 votes
## PowerShell, ~~603~~ ~~547~~ 464 bytes

```
$a=-split$args
$b=switch -W($a[0]){
"LEFT"{switch -w($a[1]){"C*"{"{"}"P*"{"("}"S*"{"["}}}
"RI*"{switch -w($a[1]){"C*"{"}"}"P*"{")"}"S*"{"]"}}}
"LA*"{("$($a[3])".ToLower(),$a[3])[$a[1]-like"C*"]}
"DI*"{@{ONE=1;TWO=2;THREE=3;FOUR=4;FIVE=5;SIX=6;SEVEN=7;EIGHT=8;NINE=9;ZERO="0"}[$a[1]]}
"COMME*"{"@"}
"APO*"{"'"}
}
$c='COM,LES<GRA`GRE>QUE?QUO"COL:REV\LOW_EXC!EQU=DOL$AMP&AST*PER%PLU+SEM;SOL/SPA CIR^HYP-FUL.NUM#TIL~VER|'
($b,$c[$c.IndexOf($a[0][0..2]-join'')+3])[!$b]

```

(`LineFeed` counts the same one byte as `;`, so I'll leave the breaks in for readability)

Edit 1 - Took many elements out of the switch statement and instead populated a hashtable for lookups.

Edit 2 - Oh yeah ... indexing into a string, that's the way to go ...

Essentially takes the input, splits it on spaces, and does a wildcard `switch` on the first word to filter out the goofy ones. Sets the result of that to `$b`. If `$b` doesn't exist, the string `$c` gets evaluated on the first three letters of the first word and outputs the character immediately following, otherwise we output `$b`.

Some tricks include the `LATIN CAPITAL LETTER R` which indexes into an array based on whether the second word is `CAPITAL`, and outputs the corresponding uppercase/lowercase letter. The other "trick" is for the `DIGIT`s, by indexing into a hashtable. Note that it's not shorter to do the same index-into-a-string trick here (it's actually longer by one byte).

# Answer
> 1 votes
## Javascript, ~~416~~ ~~411~~ 389 bytes

```
l=(E)=>{return E=E.replace(/LA.*N|BR.*T|SIGN|MARK| |TION/g,"").replace(/(.).*(.{3})/,"$1$2"),E.match("CER")?E[3]:E.match("SER")?E[3].toLowerCase():(a="SACE EAMA!QOTA\"NBER#DLAR$PENT%AAND&APHE'AISK*PLUS+CMMA,HNUS-FTOP.SDUS/CLON:SLON;LHAN<EALS=GHAN>QUES?CLAT@RDUS\\CENT^LINE_GENT`VINE|LSIS(RSIS)LARE[RARE]LRLY{RRLY}TLDE~DERO0DONE1DTWO2DREE3DOUR4DIVE5DSIX6DVEN7DGHT8DINE9",a[a.indexOf(E)+4])}

```

This is a more readable format(explanation coming later):

```
function l(k){
    k=k.replace(/LA.*N|BR.*T|SIGN|MARK| |TION/g,'').replace(/(.).*(.{3})/,'$1$2')
    if(k.match('CER')) return k[3];
    if(k.match('SER')) return k[3].toLowerCase();
    a="SACE EAMA!QOTA\"NBER#DLAR$PENT%AAND&APHE'AISK*PLUS+CMMA,HNUS-FTOP.SDUS/CLON:SLON;LHAN<EALS=GHAN>QUES?CLAT@RDUS\\CENT^LINE_GENT`VINE|LSIS(RSIS)LARE[RARE]LRLY{RRLY}TLDE~DERO0DONE1DTWO2DREE3DOUR4DIVE5DSIX6DVEN7DGHT8DINE9"
    return a[a.indexOf(k)+4];
}

```

Minus 5 bytes from combining key and value strings.

**Explanation:** The regular expressions on the first line reduce the inputs into unique 4 character keys. Note that uniqueness is only guaranteed for the specific set of names specified in the challenge, and duplicates would be very common for normal English! Even for this challenge, I had to remove common words like bracket and sign to get a unique set.

To return the character, I check to see if it's a latin character by check for the strings "SER" and "cer", and return the last character of the input, in lowercase for ser.

For everything else, I refer to a string that contains all of the 4 character keys, followed by the correct character. I then use indexof and ~~substring~~ character indices to pull and return the character.

**Edit:** Used more wildcards to reduce regex size, replaced substr with character indices and shaved off antoher twenty chars. Rule sticklers will note that this final update is posted after the challenge has ended, however I don't think it changed my ranking. This is just practice for a novice.

# Answer
> 1 votes
# Python 3, 148 bytes

```
lambda s:chr(83-b'gfhtg\32}urgx_}3qeo|e~cwu~S~q~I,vqG\34jc}d*9~~_L|p~~~~~JJy'[sum(b'  !" *1! "2;D$# ! # !!( '[ord(c)%25]-32for c in s[:-1])]+ord(s[-1]))

```

For your viewing convenience, I’ve replaced two non-printable bytes with the octal escape codes `\32` and `\34`; undo this to get the 148 byte function.

I computed parts of this hash function with GPerf.

# Answer
> 0 votes
# Perl 6,  ~~348~~  242 bytes

~~```
{
  /NI/??9!!chr 32+
  '0A40W00SV0M20LR0O20IJ0LH0WH0YS0H20ID0A50P10IH0F70K10HF0I30LL0JX0JF0HX0LU0LE0JF0AJ0IX0RK0M40XF0QR0PD15Z16016116216316416516616716816916A16B16C16D16E16F16G16H16I16J16K16L16M16N16O1140V313F0XS0FU0N712A12B12C12D12E12F12G12H12I12J12K12L12M12N12O12P12Q12R12S12T12U12V12W12X12Y12Z0ZA0PU11L0AA'
  .comb(3).map({:36($_)}).first(:k,[+] .ords)
} # 348

```~~
```
{chr 32+"\x95ǐǠŬšƉĘŗȌȴĎĽ\x96ŖŁöģěĈśŊčĂĹŔĸ¤ĦƱŮȃƿƍʶʷʸʹʺʻʼʽʾʿˀˁ˂˃˄˅ˆˇˈˉˊʠʡʢʣʤɝǚʅǥâĿʇʈʉʊʋʌʍʎʏʐʑʒʓʔʕʖʗʘʙʚʛɱɲɳɴɵțųɃ\x9b".ords.first: :k,[+] .ords.map(*%43)}

```

```
{
  chr 32+
  "\x95ǐǠŬšƉĘŗȌȴĎĽ\x96ŖŁöģěĈśŊčĂĹŔĸ¤ĦƱŮȃƿƍʶʷʸʹʺʻʼʽʾʿˀˁ˂˃˄˅ˆˇˈˉˊʠʡʢʣʤɝǚʅǥâĿʇʈʉʊʋʌʍʎʏʐʑʒʓʔʕʖʗʘʙʚʛɱɲɳɴɵțųɃ\x9b"
  .ords.first: :k,[+] .ords.map(*%43)
}

```

usage:

```
my &code = {...}

# testing
my $test = [~] (' '..'~')».uniname».&code;
my $comparison = [~] ' '..'~';
say $test eq $comparison; # True

say code 'HYPHEN-MINUS'; # -

```

---
Tags: code-golf, string, kolmogorov-complexity
---