title: Knights and Knaves

text:
# Question
Title: Knights and Knaves
This is .

In this challenge, we will be writing programs/functions that solve "Knights and Knaves" puzzles.

**Background**

You find yourself on an island ... etc. ... every person on the island except for you is either a *knight* or a *knave*.

Knights can only make **true** statements.

Knaves can only make **false** statements.

I don't want to rigorously define "statement," but we will say a statement is anything which is either "true" or "false." Note that this excludes paradoxical sentences.

For the purposes of this challenge, you will be coming across groups of islanders; they will make statements to you.

**Your task is to determine who is a Knight and who is a Knave.**

**Input:**

You will be given (in any reasonable format) the following information:

* A list of the people present. They will be named with uppercase alphabet characters "A-Z". The limit on the number of people imposed by this will not be exceeded.
* The statements that each person makes. See below for important details about this.

**Output**

You will then output (in any reasonable format) what each person is. For example, if there were players `A B C D` and `A` is a knight, but the rest are knaves, you could output

```
A: 1
B: 0
C: 0
D: 0

```

**Important details:**

* Uppercase alphabet characters A-Z refer to islanders.
* The characters `0` (zero) and `1` (one) refer to a "Knave" and a "Knight", respectively. (You can any other two non A-Z characters, as long as you specify)
* Each islander present may make any natural number of statements, or may choose to say nothing.
* The normal **logical operators** can be used in statements (**IS\*, AND, OR, NOT**). On top of this, **De Morgan's Laws** and **Conditionals** may be used. The following are examples of how they might be presented in a spoken puzzle followed by how they might be input into your program.

(\* on a more technical note. The "IS" operator is really used as containment (which isn't a logical operator). When I say "A is a Knight", I really mean "A is a member of the set of Knights". The true operator used would be 'ϵ'. For simplicity's sake, we will instead be using '='.)

I use the following (you may use whatever, as long as it is reasonable and consistent):

* `^` AND
* `v` OR
* `=` IS
* `~` NOT
* `=>` IMPLIES
* `X:` Person *X* claims that...

Person *Z* could make any combination of any of the following types of statements:

Person *Z* says that...

1. Person *A* is a Knight.

`Z: A = 1`
2. Person *Q* is a Knave.

`Z: Q = 0`
3. I am a Knight.

`Z: Z = 1`
4. Person *A* is a Knight OR Person *B* is a Knight.

`Z: ( A = 1 ) v ( B = 1)`
5. Person *C* is a Knight AND I am a Knave.

`Z: ( C = 1 ) ^ ( Z = 0 )`
6. Person *R* is NOT a Knight.

`Z: ~( R = 1 )`

On top of this, input may also use De Morgan's Laws

7. It is NOT True that both person A and Person B are Knaves

`Z: ~( ( A = 0 ) ^ ( B = 0 ) )`
8. It is False that either person A or person B is a Knight

`Z: ~( ( A = 1 ) v ( B = 1) )`

Finally, conditionals and their negations may be used

9. If I am a Knight, then person B is a Knave

`Z: ( Z = 1 ) => ( B = 0 )`
10. It is NOT True that If person B is a Knight, Then Person C is a Knave.

`Z: ~( ( B = 1 ) => ( C = 0 ) )`

**Notes on conditionals**

Check out wikipedia for more info.

A conditional statement takes the form *p* =\> *q*, where *p* and *q* are themselves statements. *p* is the "antecedent " and *q* is the "consequent". Here is some useful info

* The negation of a condition looks like this: ~( p =\> q ) is equivalent to p ^ ~q
* A false premise implies anything. That is: if *p* is false, then any statement *p* =\> *q* is true, regardless of what *q* is. For example: "if 2+2=5 then I am Spiderman" is a true statement.

**Some simple test cases**

These cases are given in the following fashion (1) how we would pose the problem in speech (2) how we might pose it to the computer (3) the correct output that the computer might give.

1. Person A and Person B approach you on the road and make the following statements:

A: B is a knave or I am a knight.

B: A is a knight.

Answer:

> B is a Knight and A is a Knight.

Input:

```
A B        # Cast of Characters
A: ( B = 0 ) v ( A = 1)
B: A = 1

```

Output:

> ```
>
>     A = 1
>     B = 1
>
> ```

2. Persons A, B, and F approach you on the road and make the following statements:

A: If I am a Knight, then B is a Knave.

B: If that is true, then F is a Knave too.

Answer:

> A is a Knight, B is a Knave, F is a Knight.

Input

```
A B F
A: ( A = 1 ) => ( B = 0 )
B: ( A = 1 ) => ( F = 0 )

```

Output:

> ```
>
>     A = 1
>     B = 0
>     F = 1
>
> ```

3. Q, X, and W approach you on the road and make the following statements:

W: It is not true that both Q and X are Knights.

Q: That is true.

X: If what W says is true, then what Q says is false.

Answer:

> W and Q are Knights. X is a Knave.

Input

```
Q X W
W: ~( ( Q = 1 ) ^ ( X = 1 ) )
Q: W = 1
X: ( W = 1 ) => ( Q = 0 )

```

Output

> ```
>
>     W = 1
>     Q = 1
>     X = 0
>
> ```

*There is a similar challenge from 3 years ago that focuses on parsing and does not contain conditionals or De Morgan's. And therefore, I would argue, is different enough in focus and implementation to avoid this being a dupe.*

*This challenge was briefly closed as a dupe. It has since been reopened.*

*I claim that this challenge is, first off, different in focus. The other challenge focuses on English parsing, this does not. Second it uses only AND and OR whereas this uses conditionals and allows for the solving of many more puzzles. At the end of the day, the question is whether or not answers from that challenge can be trivially substituted to this one, and I believe that the inclusion of conditionals and conditional negations adds sufficient complexity that more robust changes would need to be made in order to fit this challenge.*

# Answer
> 6 votes
# Python 3, ~~450~~ ~~342~~ 307 bytes

Edit: it turns out I forgot an import...

My first solution takes advantage of having flexible naming for queries

```
from functools import*
def g(c,r):c=c.split();l,y=len(c),range;d=[dict((c[i],n>>i&1)for i in y(l))for n in y(2**l)];return[n[1]for n in[[eval(reduce(lambda x,y:x.replace(y,str(d[i][y])),d[i],')and '.join(['not',''][d[i][s[0]]]+'('+s[2:].replace('->','<1or')for s in r)+')')),d[i]]for i in y(len(d))]if n[0]]

```

You can call the above one with

```
g('Q X W', ['W: not( ( Q == 1 ) and ( X == 1 ) )','Q: W == 1', 'X: ( W == 1 ) -> ( Q == 0 )'])

```

The next one here uses the same format of queries as seen in the OP, it also doesn't have some of the modifications I made to the first one. It is 417 bytes because it converts between the two formats.

```
from functools import*
def g(c,r):c=c.split();l,y=len(c),range;d=[{**dict((c[i],n>>i&1)for i in y(l)),**{'v':'or','^':'and','=':'==','~':'not'}}for n in y(2**l)];f=lambda r,c:reduce(lambda x,y:x.replace(y,str(c[y])),c,('(0<1'+''.join([')^ '+['~',''][c[t[0]]]+'('+t[1]for t in[s.split(":")for s in r]])+')').replace('=>','<1or'));return[dict((o,j) for o,j in n[0].items() if o in c) for n in[[d[i],eval(f(r,d[i]))]for i in y(len(d))]if n[1]]

```

And it can be called by:

```
g('Q X W', ['W: ~( ( Q = 1 ) ^ ( X = 1 ) )','Q: W = 1', 'X: ( W = 1 ) => ( Q = 0 )'])

```

They both return

```
[{'X': 0, 'W': 1, 'Q': 1}]

```

Ungolfed Explanation:

```
from functools import *
def knight_and_knaves(cast,rules):
    # turns 'A B C' into ['A','B','C']
    cast = cast.split()
    # gets all numbers that can fit in len(cast) bits
    bitmasks = range(2 ** len(cast))
    # for every bitmask, apply the value for a bit to the boolean value for each cast member.
    # This returns a dictionary of all possible outcomes.
    d=[dict((cast[i], n>>i & 1) for i in range(len(cast))) for n in bitmasks]
    # Split rules at colon
    rules = [s.split(":")for s in rules]
    # Turns list of rules into one python expression, joins each rule with ')and ', maybe a 'not' depending on if the hypothesis has the rule as a lie, and '('.
    # Also replaces '->' with '<1or' which is equivalent to it. Also starts with '(True' and ends with ')' to resolve missing parentheses
    transform_rules = lambda d, rules: ('(True' + ''.join([')and ' + ['not', ''][d[rule[0]]] + '(' + rule[1].replace('->','<1or') for rule in rules]) + ')')
    # Applys transform_rules on each outcome and evaluates the result, storing it into a list of lists where each element is [outcome, value]
    outcomes=[[d[i],eval(reduce(lambda x,y:x.replace(y,str(d[i][y])),d[i],transform_rules(d[i], rules)))] for i in range(len(d))]
    # Filters outcomes if value is True
    return[n[0]for n in outcomes if n[1]]

```

Also, the second solution needs 3.5 (not 3.4) due to the use of PEP 448

# Answer
> 1 votes
# Mathematica, 80 bytes

```
F[c_,s_]:=Select[Thread[c->#]&/@{True,False}~Tuples~Length@c,And@@Equal@@@s/.#&]

```

---

**Explanation**

The function `F` takes two arguments,

* `c` is a list of all characters' names,
* `s` is a list of statements, each of which contains two parts - who says what.

For example, there are three characters, Q, X and W.

```
characters={q,x,w};

```

And they say,

```
statements=
   {{w, !((q==True)&&(x==True))   },
    {q, w==True                   },
    {x, Implies[w==True,q==False] }};

```

where `True` and `False` means Knights and Knaves respectively. Then

```
F[characters, statements]

```

will give `{{q->True, x->False, w->True}}`, which means there is only one solution that Q and W are Knights while X is a Knave. If there are more than one solution, the output will look like `{{...},{...},...}`

---

The algorithm is very simple. `{True,False}~Tuples~Length@c` gives all possible combinations of Knights and Knaves among the characters. Then `Thread[c->#]&/@` construct an array of rules based on these combinations. In the case of two characters A and B, the array will be

```
{{a->True, b->True },
 {a->True, b->False},
 {a->False,b->True },
 {a->False,b->False}}

```

Substituting the statements with one row of these rules, we will get an array looks like

```
{{True,True},{True,False},{False,False}}

```

The first column of this array is the identities of the speakers, and the second column indicates whether their statements are true or false. A valid solution requires the accordance between speakers' identities and their statements. The array above means that this combination is not a solution, since the second speaker, a Knight, makes an incorrect statement.

```
Select[...,And@@Equal@@@s/.#&]

```

does the substitutions and select those combinations that satisfy the condition.

# Answer
> 1 votes
## Ruby, 128

This is the same algorithm as everyone else, try all possible combinations of knaves and knights and see which sticks. I have another that I'm working on, but I think it'll be longer (though more interesting).

The statement inputs must be:

* `&` AND
* `|` OR
* `==` IS
* `!` NOT
* `>` IMPLIES
* `X:` Person X claims that...

I also require each statement and sub-statement to be in parentheses. The only problem with this version is that it goes through at most 2^26 iterations, and if they're not all knaves, **at least 2^(26-n) iterations**! To put that in perspective, that means that if there are two people, and at least one is not a knave, it will take **a minimum of 16,777,216 iterations**!

To limit that, I submit the following at 168 bytes. Sub in `26` for `#{o.size}` to cut it back to 161.

```
->s{o=s[/.*?$/].split
i=0
eval h=o.zip(("%0#{o.size}b"%i+=1).chars).map{|k|k*?=}*?;until h&&o.all?{|t|!s[/#{t}:(.*)$/]||eval("(#{t}<1)^(#{$1.gsub(?>,'!=true||')})")}
h}

```

But if I can instead use an array of people and a map of statements e.g.:

```
c[[?A, ?B],
  {
    ?A=> "( B == 0 ) | ( A == 1)",
    ?B=> "A == 1"
  }
 ]

```

Then I get it down to 128.

```
->o,s{i=0
eval h=o.zip(("%026b"%i+=1).chars).map{|k|k*?=}*?;until h&&s.all?{|t,k|eval("(#{t}<1)^(#{k.gsub(?>,'!=true||')})")}
h}

```

---
Tags: code-golf
---


title: Congruence Relations

text:
# Question
Title: Congruence Relations
Given 3 positive integers `a`, `b`, and `n` (whose maximum values are the maximum representable integer value in your language), output a truthy value if `a ≡ b (mod n)`, and falsey otherwise. For those unfamiliar with congruency relations, `a ≡ b (mod n)` is true iff `a mod n = b mod n` (or, equivalently, `(a - b) mod n = 0`).

## Restrictions

* Built-in congruence testing methods are forbidden
* Built-in modulo operations are forbidden (this includes operations such as Python's `divmod` function, which return both the quotient and the remainder, as well as divisibility functions, residue system functions, and the like)

## Test Cases

```
(1, 2, 3) -> False
(2, 4, 2) -> True
(3, 9, 10) -> False
(25, 45, 20) -> True
(4, 5, 1) -> True
(83, 73, 59) -> False
(70, 79, 29) -> False
(16, 44, 86) -> False
(28, 78, 5) -> True
(73, 31, 14) -> True
(9, 9, 88) -> True
(20, 7, 82) -> False

```

This is , so shortest code (in bytes) wins, with earliest submission as a tiebreaker.

# Answer
# Jelly, 5 bytes

```
_ÆD⁵e

```

Making heavy use of *Anything else that is not forbidden is allowed.*

Try it online!

### How it works

```
_ÆD⁵e  Main link. Left input: a. Right input: b. Additional input: n

_      Subtract b from a.
 ÆD    Compute all divisors of the difference.
   ⁵e  Test if n is among the divisors.

```
> 5 votes

# Answer
## Python 2, 27 bytes

```
lambda a,b,n:(a-b)/n*n==a-b

```

Checks if `a-b` is a multiple of `n` by dividing by `n`, which automatically floors, and seeing if multiplying back by `n` gives the same result.
> 4 votes

# Answer
# Julia, 24 bytes

```
f(a,b,n,t=a-b)=t÷n==t/n

```

This is a function that accepts three integers and returns a boolean.

We simply test whether *a* \- *b* integer divded by *n* is equal to *a* \- *b* float divided by *n*. This will be true when there is no remainder from division, i.e. *a* \- *b* | *n*, which implies that *a* \- *b* (mod *n*) = 0.
> 4 votes

# Answer
## Pyth, 7 bytes

```
!@UQ-FE

```

Uses Pyth's cyclic indexing.

```
  UQ         range(first line). [0,...,Q-1]
    -FE      Fold subtraction over the second line.
 @           Cyclic index UQ at -FE
!            Logical NOT

```
> 4 votes

# Answer
## Minkolang 0.15, ~~14~~ 11 bytes

```
nn-n$d:*=N.

```

Try it here! Input is expected as `a b n`.

### Explanation:

```
n              Take number from input -> a
 n             Take number from input -> a, b
  -            Subtract               -> a-b
   n           Take number from input -> a-b, n
    $d         Duplicate stack        -> a-b, n, a-b, n
      :        Integer division       -> a-b, n, (a-b)//n
       *       Multiply               -> a-b, (a-b)//n*n
        =      1 if equal, 0 otherwise
         N.    Output as number and stop.

```
> 3 votes

# Answer
## Haskell, 23 bytes

```
(a#b)n=div(a-b)n*n==a-b

```

Usage example: `(28#78)5` -\> `True`.

Same method as in @xnor's answer.
> 3 votes

# Answer
# MATL, 9 bytes

```
Sdt:i*0hm

```

Input format is

```
[a b]
n

```

**Try it online!**

```
S     % implicitly input [a, b]. Sort this array
d     % compute difference. Gives abs(a-b)
t:    % duplicate and generate vector [1,2,...,abs(a-b)]; or [] if a==b
i*    % input n and multiply to obtain [n,2*n,...,abs(a-b)*n]; or []
0h    % concatenate element 0
m     % ismember function. Implicitly display

```
> 3 votes

# Answer
# Retina, 20

```
^(1+) \1*(1*) \1*\2$

```

Input is given in unary, space-separated, in order `n a b`. Output 1 for truthy and 0 for falsey.

Try it online.

---

If you prefer decimal input then you can do this:

```
\d+
$&$*1
^(1+) \1*(1*) \1*\2$

```

Try it online.
> 3 votes

# Answer
# APL, 15 bytes

```
{(⌊d)=d←⍺÷⍨-/⍵}

```

This is a dyadic function that accepts *n* on the left and *a* and *b* as an array on the right.

The approach here is basically the same as in my Julia answer. We test whether *a* \- *b* / *n* is equal to the floor of itself, which will be true when *a* \- *b* (mod *n*) = 0.
> 2 votes

# Answer
# JavaScript (ES6), 27 bytes

@CᴏɴᴏʀO'Bʀɪᴇɴ posted a version which does not work; here is the "common algorithm" that people are using in a form which "works":

```
(a,b,n)=>n*(0|(a-b)/n)==a-b

```

The word "works" is in scare quotes because the shortcut we're using for `Math.floor()` implicitly truncates a number to be in the signed 32-bit range, so this cannot handle the full 52-bit-or-whatever space of integers that JavaScript can describe.
> 2 votes

# Answer
## CJam, 7 bytes

```
l~-\,=!

```

Input order is `n a b`.

Test it here.

### Explanation

```
l~  e# Read input and evaluate to push n, a and b onto the stack.
-   e# Subtract b from a.
\,  e# Swap with n and turn into range [0 1 ... n-1].
=   e# Get (a-b)th element from that range, which uses cyclic indexing. This is
    e# equivalent to modulo, and as opposed to the built-in % it also works correctly
    e# for negative (a-b).
!   e# Negate, because a 0 result from the previous computation means they are congruent.

```
> 2 votes

# Answer
## Python 3, 27 bytes

```
lambda a,b,n:pow(a-b,1,n)<1

```

`pow(x,y,n)` calculates `(x**y)%n`, so this is just `(a-b)**1%n`.
> 1 votes

# Answer
## ES6, 28 bytes

```
(a,b,n)=>!/\./.test((a-b)/n)

```

Works by looking for a decimal point in (a-b)/n which I'm hoping is allowed.
> 1 votes

# Answer
## Seriously, 10 bytes

```
,,,-A│\)/=

```

Takes input as `N\nA\nB\n` (capital letters used to distinguish from newlines).

Try it online

This uses the same method as @AlexA's answer

Explanation (capital letters used as variable names for explanatory purposes):

```
,,,-A│\)/=
,,,         push N, A, B
   -A       push C = abs(A-B)
     │      duplicate entire stack (result is [N, C, N, C])
      \)/=  1 if C//N == C/N (floored division equals float division)

```
> 1 votes

# Answer
## F#, 24 bytes

```
fun a b n->(a-b)/n*n=a-b

```

Implements the same check as @xnor's answer.
> 0 votes

---
Tags: code-golf, math, arithmetic
---


title: Generate lazy microwave input

text:
# Question
Title: Generate lazy microwave input
Related: Program my microwave oven and Generate lazy values.

My colleague is so lazy that he doesn't even bother to move his finger when programming the microwave oven. (This is actually true!)

Help him find the microwave input that gives the time closest to what he wants, but where all digits are the same. If two inputs result in the same time difference from the desired time, choose the one with fewer digits. If both have the same number of digits, choose the lesser – so he doesn't have to wait so long.

Input is the integer that a perfectionist would enter, e.g. `430` is 4 minutes and 30 seconds while `100` and `60` each is 1 minute. It will be greater than 0 and will not exceed 9999.

Output must an integer, e.g. `444` is 4 minutes and 44 seconds and `55` is 55 seconds.

Both input and output may only be in simple seconds (no minutes) if the total time is below 1 minute and 40 seconds.

This is , so your code must be as short as possible.

## Test cases:

```
  30 →   33
  60 →   55
  70 →  111
  90 →   88
 100 →   55
 101 →   66
 120 →   77
 130 →   88
 200 →   99
 201 →  222
 500 →  444
 700 →  666
1000 →  888
1055 →  999
1056 → 1111
1090 → 1111

```

# Answer
> 4 votes
# Jelly, 26 bytes

```
bȷ2ḅ60
³ÇạÇ,
9Rẋ€4R¤ḌFÇ€ṂṪ

```

Explanation:

```
bȷ2ḅ60             f(x) = x tobase 100 frombase 60
³ÇạÇ,              g(x) = (abs(f(arg) - f(x)), x)
9Rẋ€4R¤            main(arg) = [1..9] repeat each with [1..4],
       ḌF           then get digits and flatten,
         Ç€         then map g,
           Ṃ        then minimum,
            Ṫ       then last element.

```

Try it online!

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

```
n=>{c=n=>n*3+n%100*2;d=n=c(n);for(r=i=0;i<1e4;i++)/^(.)\1*$/.test(i)&(m=c(i)-n,m<0?m=-m:m)<d&&(d=m,r=i);return r}

```

Uses a helper function `c` which calculates five times the actual number of elapsed seconds.

# Answer
> 2 votes
# Dyalog APL, 37 bytes

```
{⍵⊃⍨⊃⍋⊃|-/(60⊥0 100∘⊤)¨⎕⍵}⍎¨,⎕D∘./⍨⍳4

```

`⍳4` 1 2 3 4
`⎕D` "0123456789"
`∘./⍨` repetition table (like a multiplication table, but where each cell contains B repetitions of A instead of A×B)
`,` make table into list of strings
`⍎¨` make each string into number (Now we have a list off all possible results.)
`{``}` function where the argument is represented by
`⎕⍵` precede argument with prompted input
`(` apply to each of the two (the argument and the list)...
`0 100∘⊤` convert to base-100
`60⊥` convert from base-60
`-/` calculate the difference between the two
`|` absolute value
extract list (because `-/` encapsulated its result)
sort order (Does not sort, only returns the order in which to place the arguments to achieve ascending order. If two elements are equal, they stay in current order. Since our list has elements of increasing length, this takes care of ties.)
the first one, i.e. the one with smallest absolute difference from the input `⍵⊃⍨` take that element from the argument list (the list of possible results)

Thanks to the colleague in question for shaving off one byte.

---

Note: I did not have any solution at the time of posting the OP.

---
Tags: code-golf, number, date
---


title: How many letters in this word?

text:
# Question
Title: How many letters in this word?
Inspired by Project Euler #17, this is your challenge. Write a full program or function that takes a number as input, then print or return how many letters it would take to count up to and including that number in English (starting at one). You do not include spaces, commas, or hyphens, but you should include the word `and`. For example. 342 is spelled: `Three Hundred and Forty-Two`. This is 23 letters long.

Your input will be a positive integer. You do not have to handle invalid inputs. Built-ins or libraries that convert numbers to English are not allowed.

Here are all of the rules for how to spell numbers. (Note: I realize that some people use a different set of rules for how to spell numbers. This will just be the official rules for the purpose of this challenge)

# 1 to 20

> one, two, three, four, five, six, seven, eight, nine, ten, eleven, twelve, thirteen, fourteen, fifteen, sixteen, seventeen, eighteen, nineteen, twenty

# 21 to 99

Join these:

> Twenty, thirty, forty, fifty, sixty, seventy, eighty, ninety

to these:

> -one, -two, -three, -four, -five, -six, -seven, -eight, -nine,

Note that **four** has a **u** but **forty** does not!

Examples:

```
53: Fifty-three
60: sixty
72: seventy-two
99: ninety-nine

```

# 100 to 999

Write out how many hundreds (one hundred, two hundred, three hundred, etc.), an "**and**", and the rest of the number as above. The **and** does count towards your letter score.

Examples:

```
101: One hundred and one
116: One hundred and sixteen
144: One hundred and forty-four
212: Two hundred and twelve
621: Six Hundred and twenty-one

```

# 1,000 to 999,999

Write how many thousands (one thousand, two thousand, etc.), a comma, then the rest of the number as above. Note that if you have no hundreds, you still need the **and**.

Examples:

```
1,101: One thousand, one hundred and one
15,016: Fifteen thousand and sixteen
362,928: Three hundred and sixty-two thousand, nine hundred and twenty-eight

```

# Millions

Write out how many millions, then the rest of the number as above. Note that "A million" is 6 zeroes "1,000,000".

Examples:

```
191,232,891: One hundred and ninety-one million, two hundred and thirty-two thousand, eight hundred and ninety-one
1,006,101: One million, six thousand, one hundred and one

```

The same rule applies to billions, trillions, quadrillions and above, but for the purpose of this challenge, you don't have to handle any number above 999,999,999 (Nine Hundred and ninety-nine million, nine-hundred and ninety-nine thousand, nine hundred and ninety-nine.)

# Python solver

Here is a short python script to verify answers:

```
import en

def get_letter_num(s):
    count = 0
    for c in s:
        if c.isalpha():
            count += 1
    return count

number = input()
count = 0
for i in xrange(1, number + 1):
    count += get_letter_num(en.number.spoken(i))

print count

```

Note that this usesthe NodeBox linguistics library to convert numbers to English. (yes, I just broke my own rule, but this isn't a competing answer) This is freely available here.

# Sample I/O

```
7: 27
19: 106
72: 583
108: 1000
1337: 31,131
1234567: 63,448,174

```

# Answer
# Python 2, ~~266~~ ~~259~~ ~~236~~ ~~229~~ 228 bytes

This works for all inputs below one billion. This works for all test cases.

```
def l(n):b=[6,3,2][(n<1000)+(n<10**6)];c=10**b;return int("0335443554"[n%10])+int("0366555766"[n/10])+(n-10in[4,6,7,9])if n<100else l(n/c)+(l(n%c)or-3*(b<3))+7+(b<6)+2*(b<3)+3*(b>2)*(0<n%c<101)
print sum(map(l,range(input()+1)))

```

To modify it to fit the question as stated (e.g. don't treat numbers ending with 100 special) simply replace the number 101 at the end of the first line with 100.

Explanation:

```
def l(n):
    b=[6, 3, 2][(n < 1000) + (n < 10**6)] # b = 2 if n < 1000 else 3 if n < 1000000 else 6
    c=10**b
    return (                            # Parenthesis added for readability.
            int("0335443554"[n % 10]) + # Compute length of last digit. one -> 3, seven -> 5, etc.
            int("0366555766"[n / 10]) + # Compute length of second to last digit. ten -> 3, eighty -> 6, etc.
            (n - 10 in[4, 6, 7, 9])     # Add one to length if the number is 14, 16, 17, or 19.

            if n < 100 else             # Use above procedure if the number is under 100.
                                        # If otherwise, use below procedure.

            l(n / c) +                  # Compute length of the top portion of number.
                (l(n % c) or            # Compute length of bottom portion of number.
                -3 * (b < 3)) +         # If the number < 1000 and is a multiple of 100,
                                        # subtract 3 from the length because of missing and.
            7 +                         # Add 7 to the length for "million"
            (b < 6) +                   # Add 8 to the length for "thousand"
            2 * (b < 3) +               # Add 10 to the length for "hundred and"
                3 *                     # Add 3 to the length for another "and"
                (b > 2) *               # if the number >= 1000
                (0 < n % c < 101)       # and the bottom portion > 0 and <= 100
    )
print sum(map(l,range(input()+1)))      # For the reader to figure out.

```
> 1 votes

---
Tags: code-golf, math, number
---


title: Output the Military Order

text:
# Question
Title: Output the Military Order
In almost every row nowadays, the people tends to order themselves as militaries would do.

# Challenge

Suppose `4` people where:

* person `1` has priority against person `2, 3 and 4`,
* person `2` has priority against person `3 and 4`,
* person `3` has priority against person `4`,
* person `4` has the lowest priority.

Then, when ordering those `1...4` people in a row, the possibilities are:

```
1
2
3
4
1 2
1 3
1 4
2 3
2 4
3 4
1 2 3
1 2 4
1 3 4
2 3 4
1 2 3 4

```

*Your mission is:*

Given as input the number `N` of people. Output all the possibilities for `1...N` people in the military order.

Since this is , then the shotest answer in bytes wins!

---

Input can be integer or string, followed by optional newline/whitespace, or an argument to your function. You can assume `1<=N<=10`.

The output should be every sequence in a row, in any order. For each row, output a list/array or any other valid way for the numbers in military order.

# Answer
> 5 votes
## Pyth, ~~14~~ ~~9~~ 4 bytes

```
tySQ

```

Try it here!

Thanks @FryAmTheEggman for showing me the `y` function :)

# Answer
> 9 votes
# Haskell, 41 bytes

```
f 0=[[]]
f n=[id,(++[n])]<*>f(n-1)
tail.f

```

# Answer
> 7 votes
# Japt, 5 bytes

(Yes, this is me, ETHproductions.)

```
1òU à

```

Test it online! (This version has a few extra bytes to pretty-print the output.)

### How it works

```
      // Implicit: U = input integer
1òU   // Generate the inclusive range [1..U].
à     // Generate all combinations of this range.
      // Implicit: output last expression

```

# Answer
> 6 votes
# Jelly, 4 bytes

```
RŒPḊ

```

Basically the same thing as Pyth. `R`ange, `ŒP`ower set, equeue. Try it here!

# Answer
> 5 votes
## Haskell, 38 bytes

```
f n=init$filter(>0)<$>mapM(:[0])[1..n]

```

The function `(:[0])` takes `x` to `[x,0]`. Doing `mapM` of this onto `[1..n]` takes the Cartesian product of `[[1,0],[2,0],...,[n,0]]`, giving each subset of `[1..n]` with missing elements replaced by `0`.

```
*Main> mapM(:[0])[1..3]
[[1,2,3],[1,2,0],[1,0,3],[1,0,0],[0,2,3],[0,2,0],[0,0,3],[0,0,0]]

```

Finally, zeroes are filtered out from each list and the empty list at the end is removed.

# Answer
> 4 votes
## Mathematica, 20 bytes

```
Rest@*Subsets@*Range

```

Composes an unnamed function that takes an integer and returns a list of lists. We need `Rest` because `Subsets` contains the empty list.

# Answer
> 2 votes
## Haskell, 44 bytes

```
import Data.List
f x=tail$subsequences[1..x]

```

As so often, the `import` ruins the score.

`tail` removes the first list (which is always the empty list) of all subsequences of the list from `1` to `x`.

# Answer
> 2 votes
# GAP, 21 bytes

```
Combinations([1..n]);

```

Not really a programming accomplishment, but it also includes the empty ordering...

# Answer
> 1 votes
## CJam, 18 bytes

```
L]ri{)1$f++}/:$1>p

```

Test it here.

Uses a trick I learned from Dennis once upon a time to generate the powerset.

# Answer
> 1 votes
# Julia, 42 bytes

```
N->[collect(combinations(1:N,i))for i=1:N]

```

This is an anonymous function that accepts an integer and returns an array of arrays. We simply get the combinations of size `i` for each `i` from 1 to `N`. Because of the way `combinations` is implemented in Julia, the arrays are already sorted.

Example:

```
julia> f=N->[collect(combinations(1:N,i))for i=1:N]
(anonymous function)

julia> f(4)
4-element Array{Any,1}:
 [[1],[2],[3],[4]]
 [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
 [[1,2,3],[1,2,4],[1,3,4],[2,3,4]]
 [[1,2,3,4]]

```

# Answer
> 1 votes
# MATL, 11 bytes

```
2i^q:B!"@!f

```

**Try it online!**

```
2i^q    % 2^n-1, where n is the input number
:       % range [1,...,2^n-1]
B       % convert to binary. Gives 2D array where each number is a row
!       % transpose
"       % for each column
  @     %   push that column
  !     %   transpose into a row
  f     %   indices of nonzero elements
        % implicit end for each
        % implicitly display stack contents

```

As an example, with input `3`, the code `2i^q:` gives the array `[1 2 3 4 5 6 7]`. Then `B!` gives the 2D array

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

```

and then the loop `"@!f` gives `3` in the first iteration, `2` in the second, `[2 3]` in the third etc.

# Answer
> 1 votes
# MATLAB / Octave, 49 bytes

```
function f(n)
for r=1:n,disp(nchoosek(1:n,r));end

```

This generates the vector `[1,2,...,n]`. Then generates all subsets with `1` element, all subsets with `2` elements, ..., with `n` elements.

Example run:

```
>> f(4)
     1
     2
     3
     4
     1     2
     1     3
     1     4
     2     3
     2     4
     3     4
     1     2     3
     1     2     4
     1     3     4
     2     3     4
     1     2     3     4

```

# Answer
> 1 votes
## CJam (18 bytes)

```
ri)e!{_0#<$}%_&1>`

```

is equivalent to

```
ri)e!_0f#.<:$_&1>`

```

and very different to

```
ri,:)Maf+:m*:e_);`

```

but they're all the same length.

# Answer
> 1 votes
# R, 36 bytes

```
function(x)sapply(1:n,combn,x=n,s=F)

```

`combn` returns all cmbinations of `x` taken `m` at a time. if `x` is a single integer, returns all combinations of `1:n`. `sapply` required to vectorize over `m`. `s=F` stops the results being simplified and thus returns a list as required.

# Answer
> 1 votes
# Python, 69 bytes

```
def f(n):print[[j+1for j in range(n)if 1&i>>j]for i in range(1,1<<n)]

```

The key here is that we're really just asking, in order, which bits are 1 for each number `i` in the set of all `n`-bit numbers.

# Answer
> 1 votes
## JavaScript (ES7 proposed), 78 bytes

```
n=>[for(i of Array(2**n).keys())if(i)[for(j of Array(n).keys())if(i&1<<j)j+1]]

```

Based on @MegaTom's binary power set answer. Only works up to n=32.

# Answer
> 1 votes
## Seriously, 11 bytes

```
,R;╗`╜╧i`Mi

```

~~This code is super gross. I'm disgusted at how it turned out. I really need to work on Seriously 2.~~ Actually I'm just an idiot. Still need to work on Seriously 2, though.

Try it online!

Explanation:

```
,R;╗`╜╧i`Mi
,R;╗         get two copies of range(1, input+1), store one in register 0
    `   `M   map:
     ╜╧        n-length permutations of range(1, input+1)
       i       flatten list
          i  flatten list

```

# Answer
> 0 votes
# Python 3, 92

Saved 17 bytes thanks to mathmandan.

Stupid itertools and its long function names.

```
from itertools import*
lambda i:[y for n in range(i)for y in combinations(range(1,i+1),n+1)]

```

# Answer
> 0 votes
## Ruby, 47 bytes

```
->n{(r=*1..n).flat_map{|x|[*r.combination(x)]}}

```

```
->n{
(r=*1..n)         # set r to [1, 2, 3, ..., n-1, n]
.flat_map{|x|     # map and then flatten resulting array one level...
[*                # a golfy variant of .to_a
r.combination(x)  # combination as in combinatorics, conveniently already sorted
]}}

```

# Answer
> 0 votes
# Ruby, 50 bytes

A shorter ruby solution exists, using a completely different method.

This solution uses the unique idea of looking at all the numbers from `1` to `2^n-1` and getting a list of which bits are `1`, for each number.

```
->n{(1...2**n).map{|i|(1..n).reject{|a|i[a-1]<1}}}

```

---
Tags: code-golf, combinatorics
---


# Question
Title: Implement my method of adding numbers mentally
*Note: This challenge has been changed to eliminate the strict whitespace manipulation requirements that made this challenge low-quality. Some rules regarding whitespace have been changed.*

---

I'm rather good at mental math, particularly adding positive integers in my head. Here is my method for adding the numbers together (`n` is a positive integer):

* Arrange the numbers in a horizontal row
* Reorder the numbers so the `2n-1`th number in the sequence is the `n`th smallest number in the sequence and the `2n`th number in the sequence is the `n`th largest number in the sequence.
* Add the `2n-1`th number to the `2n`th number. Print the results of these additions on the next line.
* Repeat the previous step until a final result is obtained.

Your challenge is to write a program or function that prints each of the above steps until the sum of all the inputted numbers is reached. The final result must be separated from the adding steps by an additional blank newline. You may assume that all numbers inputted are unique so as to avoid confusion with the second step (and that the input is not empty). Numbers can be inputted in any format. Numbers in rows should be separated from each other by one space.

**Test cases**

For each of these, the input and output start a newline after their labels.

*Case 1*

```
Input:
314 495 767 214 141

Output:
141 767 214 495 314   //Reordering the input
908 709 314           //Adding
1617 314

1931                  //Final result

```

*Case 2*

```
Input:
884

Output:
884   //Reordering the input

884   //Final result

```

Note that there is no adding step here because the reordering of the input produces the final result.

*Case 3*

```
Input:
5033 7825 2167 6374 5050 5389 3915 7231 3025 1954 7249 5143 7567 9857 462 3504 6165 6681 6361 6367

Output:
462 9857 1954 7825 2167 7567 3025 7249 3504 7231 3915 6681 5033 6374 5050 6367 5143 6361 5389 6165
10319 9779 9734 10274 10735 10596 11407 11417 11504 11554
20098 20008 21331 22824 23058
40106 44155 23058
84261 23058

107769

```

---

This is code golf. Standard rules apply. Answer with the fewest bytes wins.

# Answer
# Ruby, ~~148~~ ~~144~~ 142 bytes

```
f=->a{a.sort!
(a.size/2).times{a[~-$.+=2,0]=a.pop}
a*="  "
puts$`+$&+$'while a.gsub!(/\d+\s+\d+/){"#{eval$&.split*?+}".ljust$&.size}
puts'',a}

```

So disappointingly long... To run:

```
f[ [314,495,767,214,141] ]

```

Prints:

```
141  767  214  495  314
908       709       314
1617                314

1931

```
> 5 votes

---
Tags: code-golf, math, number
---


title: Build a Calculus Interpreter I

text:
# Question
Title: Build a Calculus Interpreter I
A struggling manufacturer named **Tennessee Instrumental** is desperate to get into the calculator business. Problem is, they don't have any software engineers on payroll, and the deadline is *coming up fast*.

It's your job to help **TI** configure a basic calculus-ready calculator that can simplify expressions input as strings, and as a bonus (since they're on such a tight schedule), they don't care what language you use to get there! They do, however, care about how much space you take up. Not very good with hardware, it seems. Keep it brief, **fewest bytes** gets you hired.

# Goal

### Create a function which can simplify a basic calculus expression

Your calculator must be able to perform the following operations:

* `+` Addition
* `-` Subtraction and Negation
* `*` Multiplication
* `/` Division
* `^` Exponentiation
* `()` Parenthetical Reduction
* `()'` Derivation (first order)

Your calculator must also be able to use **x** as a placeholder variable. **Do not solve for x.** That will come in time.

# Input

Input is a **string** containing the plaintext version of the expression you're looking to simplify. The only valid input characters are `0-9`, `x`, `+`, `-`, `*`, `/`, `^`, `()`, `'`, and . Some examples of valid inputs are listed below:

```
"1"
"5 + 8"
"(5x + 3)(4x + 2)"
"4x - 9x + 15"
"24x / 6"
"5x^2 + 14x - 3"  // Use ^ for exponentiation
"(20x^2)'"        // Use ()' for derivation

```

# Output

Output is a **string** containing the plaintext version of the expression after simplification.

The only acceptable operators left over are `+`, `-`, `/`, and `^`. Multiples of variables should be indicated as `2x`, `-5x`, etc. Fractions should be reduced as far as possible, and parentheses and derivations must be completely eliminated, with the exception of cases such as `ln(x)` which syntactically cannot be made to make sense without them.

The input examples from above should output as follows:

```
"1"                => "1"
"5 + 8"            => "13"
"(5x + 3)(4x + 2)" => "20x^2 + 22x + 6"
"4x - 9x + 15"     => "-5x + 15"
"24x / 6"          => "4x"
"5x^2 + 14x - 3"   => "5x^2 + 14x - 3"
"(20x^2)'"         => "40x"

```

Last but not least, if a derivation function exists in your language, **you may not use it**. Derivations must be done as manually as possible. Whitespace around the basic four operators and lack of whitespace around `^` and within `()` is preferred.

# Answer
# Mathematica, 159 Bytes

```
ToString@Expand@ToExpression[StringReplace[#,"("~~a__~~")'"->"d["~~ a ~~"]"]<>"//.{d[a_ x^n->a n x^(n-1),d[x]->1,d[a__]/;a~FreeQ~x->0,d[a__+b__]->d[a]+d[b]}"]&

```

NOTE: While this works on all the examples it won't currently work on all sensible differentiable input because it doesn't balance brackets when looking for derivatives. I'll change this once I've had the time to think of a sufficiently concise way of doing it. I'm sure there's some other stuff that goes wrong too, so please let me know if you spot something! There are a few bytes that are easily golfed off too, I'll get to those..
> 4 votes

---
Tags: code-golf, string, interpreter, calculus
---


title: Sandpile integers

text:
# Question
Title: Sandpile integers
### Challenge

You will be given a positive integer `n` as input. Output should be a pyramid-like sandpile built on the rules specified below:

* Each integer "falls" downward from the same initial starting point, like sand falling into a conal-shape.
* Numbers greater than the number directly below it when it hits the sandpile will fall to the right, if able.
* Numbers less than the number directly below it when it hits the sandpile will fall to the left, if able.
* Numbers equal to the number directly below it when it hits the sandpile will stay in place.
* Numbers are able to fall to the left/right if they can move down and to the left/right respectively. That is, if there is already a number below and to the left/right, depending on the direction, the currently falling number does not move.
* A number will continue to tumble down the sandpile until it cannot be moved into its next position, or hits the floor.

### Notes

The initial comparison check only applies to the first encountered integer, not for each successive encounter as it tumbles down the sandpile.

Trailing spaces are okay but trailing new lines are not.

No leading spaces or new lines except where needed to preserve the structure of the sandpile.

You may write a full program or function.

You may assume input will only contain some combination `[0-9]`.

This is , shortest code in bytes will be marked winner by the Ides of March

**Examples**

1

```
1

```

12345

```
35
124

```

54321

```
 13
245

```

555444333222111

```
    2
    2
    2
  135
 1345
13445

```

111222333444555

```
4
4
4
135
1235
12235

```

7313623030872935273465247457435345345350

```
    3
    3
    3
    3
    34
    355
    3644
   239475
  201277445
020373685575

```

# Answer
## JavaScript (ES6), ~~260~~ 208 bytes

```
s=>[...s].map(c=>a[g(n,(c>(l=a[n].slice(-1)))-(c<l))]+=c,n=s.length,a=Array(n+n).fill(''),g=(i,d)=>a[i].length>a[i+d].length?g(i+d,d):n)&&[...a[n]].map((_,i)=>a.map(c=>c?c[i]||' ':c).join``).reverse().join`\n`

```

Edit: Saved 25 bytes by realising that the first character isn't a special case. Saved 15 bytes by using an array of strings instead of an array of arrays of chars. Saved 12 bytes in miscellaneous fixes, including using a literal `\n` (not shown). That makes this whole 20% shorter! I wanted to get rid of `reverse` but that costs more than I can then save by replacing `map` with `replace`.

Ungolfed:

```
function sandpile(str) {
    var arr = new Array(str.length * 2); // max width of sandpile is approx. 2√n but this is close enough
    for (i = 0; i < arr.length; i++) arr[i] = '';
    for (i = 0; i < str.length; i++) {
        var digit = str[i];
        var pos = str.length; // start dropping here
        if (digit < str[pos][str[pos].length - 1]) {
            while (str[pos - 1].length < str[pos].length) pos--;
        } else if (digit > str[pos][str[pos].length - 1]) {
            while (str[pos + 1].length < str[pos].length) pos++;
        }
        str[pos] += digit; // drop the digit
    }
    var len = arr[str.length].length; // final height
    // remove the unused columns, and then pad the columns with spaces for the transpose
    for (i = 0; i < arr.length; ) {
        if (!arr[i]) arr.splice(i, 1);
        else arr[i++] += ' '.repeat(len);
    }
    ans = '';
    for (i = len; i-- > 0; ) {
        for (j = 0; j < arr.length; j++) ans += arr[j][i];
        ans += '\n';
    }
    return ans;
}

```
> 4 votes

---
Tags: code-golf, math, number
---


title: The Holier Numbers

text:
# Question
Title: The Holier Numbers
As we learned from The Holy Numbers, there are 5 holy digits (`0, 4, 6, 8, 9`), and positive integers consisting solely of those digits are holy. Additionally, the holiness of a number is the sum of the holes in the number (`+2` for every `0` or `8`, and `+1` otherwise).

Now, there is an additional property to take into consideration, to truly and accurately represent the holiness of a number. You see, it's not just the number of holes in the digit that matters, but also where in the number it occurs.

Consider the number `88`. By our old rules, it would have a holiness of `4`. But that's hardly fair! The `8` on the left is doing more work than the other `8` \- 10 times the work! It should be rewarded for its work. We will reward it with extra holiness points equal to the total holiness of all the digits to its right (including the extra holiness points granted by this rule to the digits on its right), minus 1.

Here are more examples to take into consideration:

```
Number: 8080
Digital holiness: (2 + 7 - 1) + (2 + 3 - 1) + (2 + 1 - 1) + (2 + 0 - 1)
Total holiness: 15

Number: 68904
Digital holiness: (1 + 5 - 1) + (2 + 2 - 1) + (1 + 1 - 1) + (2 + 0 - 1) + (1 + 0 - 1)
Total holiness: 10

```

All of the digits are appropriately rewarded for their work with extra holiness, and all is well. We shall call this property "enhanced holarity".

In the great language Python, an algorithm for calculating enhanced holarity might look something like this:

```
# assumes n is a holy number
def enhanced_holarity(n):
    if n < 10:
        return 1 if n in [0, 8] else 0
    else:
        digits = list(map(int,str(n)[::-1]))
        res = []
        for i,x in enumerate(digits):
            res.append(enhanced_holarity(x))
            if i > 0:
                res[i] += sum(res[:i])
        return sum(res)

```

## The Challenge

Given an integer `n > 0`, output the first `n` Holy Numbers, sorted by ascending enhanced holarity, using numeric value as a tiebreaker. You may assume that the input and output will be no greater than the maximum representable integer in your language or `2^64 - 1`, whichever is less.

For reference, here are some test cases (input, followed by output):

```
25
4, 6, 9, 44, 46, 49, 64, 66, 69, 94, 96, 99, 0, 8, 84, 86, 89, 40, 48, 60, 68, 90, 98, 80, 88

100
4, 6, 9, 44, 46, 49, 64, 66, 69, 94, 96, 99, 444, 446, 449, 464, 466, 469, 494, 496, 499, 644, 646, 649, 664, 666, 669, 694, 696, 699, 0, 8, 84, 86, 89, 844, 846, 849, 864, 866, 869, 894, 896, 899, 40, 48, 60, 68, 90, 98, 404, 406, 409, 484, 486, 489, 604, 606, 609, 684, 686, 689, 80, 88, 804, 806, 809, 884, 886, 889, 440, 448, 460, 468, 490, 498, 640, 648, 660, 668, 690, 698, 840, 848, 860, 868, 890, 898, 400, 408, 480, 488, 600, 608, 680, 688, 800, 808, 880, 888

200
4, 6, 9, 44, 46, 49, 64, 66, 69, 94, 96, 99, 444, 446, 449, 464, 466, 469, 494, 496, 499, 644, 646, 649, 664, 666, 669, 694, 696, 699, 944, 946, 949, 964, 966, 969, 994, 996, 999, 4444, 4446, 4449, 4464, 4466, 4469, 4494, 4496, 4499, 4644, 4646, 4649, 4664, 4666, 4669, 4694, 4696, 4699, 0, 8, 84, 86, 89, 844, 846, 849, 864, 866, 869, 894, 896, 899, 40, 48, 60, 68, 90, 98, 404, 406, 409, 484, 486, 489, 604, 606, 609, 684, 686, 689, 904, 906, 909, 984, 986, 989, 4044, 4046, 4049, 4064, 4066, 4069, 4094, 4096, 4099, 80, 88, 804, 806, 809, 884, 886, 889, 440, 448, 460, 468, 490, 498, 640, 648, 660, 668, 690, 698, 940, 948, 960, 968, 990, 998, 4404, 4406, 4409, 4484, 4486, 4489, 4604, 4606, 4609, 4684, 4686, 4689, 840, 848, 860, 868, 890, 898, 400, 408, 480, 488, 600, 608, 680, 688, 900, 908, 980, 988, 4004, 4006, 4009, 4084, 4086, 4089, 800, 808, 880, 888, 4440, 4448, 4460, 4468, 4490, 4498, 4640, 4648, 4660, 4668, 4690, 4698, 4040, 4048, 4060, 4068, 4090, 4098, 4400, 4408, 4480, 4488, 4600, 4608, 4680, 4688, 4000, 4008, 4080, 4088

```

# Answer
> 1 votes
# Python 2, ~~138~~ 122 bytes

This looks for holy numbers up to 5*N* for an input *N*, which is ridiculously slow:

```
e=lambda s:s and(s[0]in'08')+e(s[1:])*2or 0
lambda N:sorted([`x`for x in range(5**N)if set(`x`)<=set('04689')][:N],key=e)

```

Here the limit is 5*N*2, and you can actually run the test cases, at the cost of a single byte:

```
e=lambda s:s and(s[0]in'08')+e(s[1:])*2or 0
lambda N:sorted([`x`for x in range(5*N*N)if set(`x`)<=set('04689')][:N],key=e)

```

The first snippet is valid, as 5*N* ≥ 5*N*2 for all positive integers *N*.

# Answer
> 2 votes
## Lua, 317 Bytes

I had some troubles doing this, some things in Lua don't work as I think it does. I will have to try and play with them if I want to golf this down. You can test lua online by replacing `arg[1]` by the number of elements you want :).

```
function f(y)h=0(y..''):reverse():gsub(".",function(c)h=c:find("[08]")and 1+h or h end)return h end
x,a=0,{}while(#a<arg[1]+0)do a[#a+1],x=(x..''):find("^[04689]*$")and x or nil,x+1 end
for i=1,#a do m=1
for j=1,#a do x=a[m]m=(f(x)~=f(a[j])and f(x)>f(a[j])or x>a[j])and j or m
end end print(a[m])table.remove(a,m)end

```

### Ungolfed and explanations

```
function f(y)                     -- function returning the enhanced holiness of a holy number
  h=0                             -- h is the cumulated holyness of processed digits
  (y..''):reverse()               -- reverse the digits in y
         :gsub(".",function(c)    -- iterate over each digits
     h=c:find("[08]")and 1+h or h -- ternary based on the digit being [08] or [469]
   end)
  return h                        -- return h
end

x,a=0,{}                          -- initialise a counter, and the array of holy numbers
while(#a<arg[1]+0)                -- iterate until we have n holy numbers
do
  a[#a+1]=(x..'')
      :find("^[04689]*$")         -- if we can't find an unholy digit
             and x or nil         -- insert x into a
  x=x+1                           -- increment x anyway
end

for i=1,#a                        -- iterate n times(current size of a)
do
  m=1                             -- m is the index of the lowest value
  for j=1,#a                      -- iterate over a
  do
    x=a[m]                        -- x is shorter to write than a[m]
    m=(f(x)~=f(a[j])              -- nested ternaries, translated in
        and f(x)>f(a[j])          -- nested if below
        or x>a[j])and j or m
  end
  print(a[m])                     -- output a[m]
  table.remove(a,m)               -- remove it from the table a
end

```

The nested ternaries used for the new value of `m` can be translated in nested ifs as:

```
if(f(a[m])~=f(a[j])) then         -- if a[m] and a[j] don't have the same holyness
  if(f(a[m])>f(a[j])) then m=j end-- compare by holyness
else
  if(a[m]>a[j]) then m=j end      -- else, compare by numeric value

```

Also, I would have loved to replace the nested `for` by using `table.sort`, but, for a reason I don't know, the following doesn't work despite not producing an infinite loop or crushing the sort function.

```
table.sort(a,function(i,j)
    return f(i)~=f(j)
         and f(i)>f(j)
         or i>j
end)

```

# Answer
> 1 votes
## JavaScript (ES6), ~~166~~ 165 bytes

```
f=n=>[...Array(n)].map((_,i)=>i.toString(5)).sort((a,b)=>e(a)-e(b),e=n=>'0b'+[...n.replace(/./g,c=>'10010'[c])].reverse().join``).map(n=>+n.replace(/./g,c=>"04689"[c]))

```

Edit: Saved 1 byte by returning an array of strings.

Ungolfed:

```
function base5_to_extended_holiness_binary(c) {
    return "10010"[c];
}
function extended_holiness(n) {
    var binary = n.toString(5).replace(/./g, base5_to_extended_holiness_binary);
    binary = s.split("").reverse().join("");
    return parseInt(s, 2);
}
function extended_holiness_sort(a, b) {
    return extended_holiness(a) - extended_holiness(b);
}
function base5_to_holy_number(c) {
    return "04689"[c];
}
function list_by_extended_holiness(n) {
    var array = new Array(n);
    for (var i = 0; i < n; i++)
         array[i] = i;
    array = array.sort(extended_holiness_sort);
    for (var i = 0; i < n; i++)
        array[i] = parseInt(array[i].toString(5).replace(/./g, base5_to_holy_number);
    return array;
}

```

---
Tags: code-golf, number, sequence
---


# Question
Title: It's the end, but the code-golf has been prepared for
Welcome to BBC Casting. We need a program that we can use to select a new actor to play **The Doctor** on **Doctor Who**. In the spirit of the show, your program will perform a regeneration from one actor's name to the next.

We will test your program by running through the 13 names of actors who have already played The Doctor and then run it another 13 times. We will pass the output from one call as the input to the next in a loop.

**Detailed Requirements**

* Your program will take a string as its only input and output a single string. It must not store any state between calls or use any additional resources outside of the program.
* If the input is your starting string, your program must return "William Hartnell", the first name on the list.
    + You should select and document any string you wish to use as the starting string, as long as it isn't the name of a listed actor. My example below uses an empty string.
* If the input string is an actor's name (other than the last), your program must return the next name on the list following the name inputted.
* For any other inputs, behavior of your program is undefined.
* The list of actors below is incomplete. You must complete the list by selecting 13 more names of actors you feel would be good at playing The Doctor.
    + Each extra name must be of a professional actor with an IMDB page.
    + The extra names returned by your program must be the actors' names exactly as listed on IMDB, including case, accents and diacritics.
    + The completed list of 26 actors must be 26 distinct individuals with distinct names.
* You may interpret input and output according to the constraints of your language's execution environment. (Parameters, quotes, end-of-lines, stdin/out, encoding etc.)
* Shortest conforming program wins. Normal code-golf rules apply.
* You may use someone else's list of actors. If you do, give appropriate credit and share the glory. (Finding a list of actors that would compress well might be part of the challenge.)

The first half of the list of names is as follows. These strings must be output exactly as shown, preserving case including the extra capital letter in "McCoy" and "McGann".

```
William Hartnell
Patrick Troughton
Jon Pertwee
Tom Baker
Peter Davison
Colin Baker
Sylvester McCoy
Paul McGann
John Hurt
Christopher Eccleston
David Tennant
Matt Smith
Peter Capaldi

```

**For example:**

```
YourProgram("") returns "William Hartnell".
YourProgram("William Hartnell") returns "Patrick Troughton".
YourProgram("Patrick Troughton") returns "Jon Pertwee".
/* 10 more. */
YourProgram("Peter Capaldi") returns "Pauley Perrette".
YourProgram("Pauley Perrette") returns "Nathan Fillion".
/* 12 more. */

```

# Answer
## Python 2, 340 bytes

```
#coding:L1
import zlib;r=zlib.decompress("x5mÂ@¯Â 8]c]u×Xã-q1H5½ýRãþ#÷O³PÌsÆ=¹IºÁÑêx¼*~W=¿ñX,èÆ{v6ø¢§<â¦©Yô³é¦üäÇ¼Ý¥¦NAs+Ò5(´£96ÉÃë}»eJ9>3óz8²*©ãÜ¡+âÃG®¡;å^pY\nÁ|þ7Ü9¿\"®ICmYXqÁÊ½$f,g¶3yÞ!ZéûfÇñÑTU¶ Û\r[M8Ì¨põ)ËåÂxïÑ¬LÂÜlßÜ\nwI×+nX`£åep;·ûÃVÿ À]b").split('.');print r[r.index(input())+1]

```

The encoding is Latin-1 (aka ISO-8859-1). That first line is important because Python 2 doesn't like non-ASCII characters in files by default (and using Python 3 wouldn't help, because it expects UTF-8 by default, along with loads of other issues).

Takes quoted input (single and double both work), with the initial input as the empty string (`''`).

The strategy I used was constructing a list of period-separated names (starting with an empty string) and compressing it with zlib (which gave better results over both shoco and lzma). This program decompresses that list, splits it on periods, and outputs the element in the list that follows the input.

I didn't use any real strategy with choosing the next 13 actors, other than picking living British actors (sorry, Alan Rickman, you would've been great) that I liked who haven't played a Doctor yet. The rationale was, the character distribution in the first 13 names is fairly random (as far as names go), so it's unlikely (in my opinion) that 13 more names could be picked that would make a significant difference in compressed size.

For reference, the list I used (with an extra linebreak to separate the new actors):

```
William Hartnell
Patrick Troughton
Jon Pertwee
Tom Baker
Peter Davison
Colin Baker
Sylvester McCoy
Paul McGann
John Hurt
Christopher Eccleston
David Tennant
Matt Smith
Peter Capaldi

Emma Watson
Patrick Stewart
Ian McKellen
Benedict Cumberbatch
Tom Hiddleston
Sean Connery
Hugh Laurie
Daniel Radcliffe
Rupert Grint
Gary Oldman
Simon Pegg
Keira Knightley
Liam Neeson

```
> 2 votes

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


title: Confuse the Word spell checker!

text:
# Question
Title: Confuse the Word spell checker!
Your task is to make a program that will take an input of a **word** of any length, in the Calibri font. This word will be made out of letter characters that are found on a normal QWERTY keyboard. There will be no accents or any other characters (i.e punctuation, numbers etc).

So, the original characters are:

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

The program will then scramble it to change the characters so they look similar or exactly the same, which would probably confuse a spell checker by flagging it, but it would confuse me as it looks the same as the normal word, with the unchanged character.

An example of this is the Unicode character `U+0430`, Cyrillic small letter a ("а"), can look identical to Unicode character `U+0061`, Latin small letter a, ("a") which is the lowercase "a" used in English.

Another example is the Russian letters а, с, е, о, р, х and у have optical counterparts in the basic Latin alphabet and look close or identical to a, c, e, o, p, x and y.

Rules:

1. The program has to work out similar characters. This means that they **cannot be stored in any form**. This means that Unicode value or the character itself.
2. This is a code golf - the shortest answer wins!
3. You have to post the ungolfed version too to avoid cheating that can't be detected when its golfed!
4. You can use any function or program to do this, as long as words are not stored there either.
5. You must use UTF-8. Other inputs and outputs are banned. This is so that I am actually able to read what you are outputting, and what I am inputting, so I do not have a random mass of squares, question marks and ❮ther rand❮m punctuati❮n!
6. It has to work with any word that I input.

A working example (Copy and paste this into word and insert a space after, it should flag the second one and not the first one.)

```
Halim
Hаlim

```

Some helpful info is here

Good Luck! Begin

# Answer
## JavaScript, 71 characters

```
function f(s){return "\u202E"+s.split("").reverse().join("")+"\u202C";}

```

Try it out on JSFiddle.

By the way, this would be a good bit shorter in CoffeeScript (**53 characters**)

```
f=(s)->"\u202E#{s.split('').reverse().join ''}\u202C"

```

**EDIT:** I just noticed that UTF-8 requirement. That's going to be tough in JavaScript. :-/
> 12 votes

# Answer
# Python3 - 51

```
print(''.join(chr(ord(c)+0xFEE0)for c in input()))

```

The lazy way!

Slightly ungolfed

```
r=''
for c in input():
    r += chr(ord(c) - 0x20 + 0xFF00) # convert to fullwidth ASCII range
print(r)

```
> 9 votes

# Answer
# Common Lisp, 142

I have no font named Calibri, and most of my fonts lack these symbols, but DejaVu Sans has them. I replace letters with Mathematical Alphanumeric Symbols. The spell checker does not flag any errors. Instead, it fails to detect errors, even if words have obvious typos.

Golfed:

```
(ignore-errors(do(c)(())(setf c(char-code (read-char)))(write-char(code-char(cond((< 64 c 91)(+ c 120159))((< 96 c 123)(+ c 120153))(t c))))))

```

Ungolfed:

```
(ignore-errors      ; Ignore when (read-char) signals end of file.
  (do (c) (())      ; Loop forever with variable c.
    (setf c (char-code (read-char)))
    (write-char
     (code-char
      (cond
         ;; Replace A to Z with U+1D5A0 to U+1D5B9.
         ((< 64 c 91) (+ c 120159))
         ;; Replace a to z with U+1D5BA to U+1D5D3.
         ((< 96 c 123) (+ c 120153))
         ;; Keep other characters.
         (t c))))))

```

## Usage

* `clisp asconfuse.lisp <in >out`
* `ecl -shell asconfuse.lisp <in >out`
* `sbcl --script asconfuse.lisp <in >out`

I assume that your Lisp interpreter has Unicode support and your locale is UTF-8. Do not use `abcl`, because it has problems outside the Basic Multilingual Plane.

**Unix clones:** You can run `locale` in a terminal. If the line for LC\_CTYPE does not mention UTF-8, try `export LC_CTYPE=en_US.UTF-8`.

## Example

I pasted some output into LibreOffice. My text has obvious spelling errors, but LibreOffice fails to detect them. It draws no red squiggles under the words, and the spell-check button only reports, "The spellcheck is complete."

The text is, " ." Firefox also finds no spelling errors in this text.
> 8 votes

# Answer
# Dyalog APL, 7 chars

```
∊''∘,¨

```

There is a U+FEFF (Zero Width No-Break Space, a.k.a Unicode BOM) between the quotes. This character occurs in in the Calibri font. The character `''` is  prepended `,` to each `¨` character in the argument, and the whole thing is then flattened .
> 5 votes

---
Tags: code-golf
---


# Question
Title: Find if a number contains a digit without ever using using its string representation
### The Challenge:

Find if a number contains a digit. The number and the digit are to be taken as input. Output must be a boolean value. But you are not allowed to use the string representation of the number at any time. Now don't count upon a `char*` either. You must devise a mathematical way to do it.

**Rules:**

• You can't use a `string`/`char[]` representation of the number. Same goes for the digit.

• It must be a complete program.

• Input can be in any form.

• Output must be a boolean value.

*This is code-golf, so shortest code wins!*.

**Test Cases**:

```
Input: 51, 5
Output : True
------------------------
Input: 123456789, 0
Output : False
------------------------
Input: 1111, 1
Output : True

```

*Disclaimer*: *I don't understand much Pyth/CJam/Japt and similar languages. Thus I hope everyone will be honest enough not to break the rules. Never mind, the community is always there to help me :)*

# Answer
# Perl 6, 27 bytes

```
{$^a.polymod(10 xx*)∋$^b}

```

### Usage:

```
# make it an infix op, because I can
my &infix:<contains> = {$^a.polymod(10 xx*)∋$^b}

say 51 contains 5; # True
say 123456789 contains 0; # False
say 1111 contains 1; # True

# you can use infix ops as oddly named subs as well
say infix:<contains> 1230, 0; # True

say map {$^a.polymod(10 xx*)∋$^b}, 10,0, 12,3, 12,2;
# (True False True)

```

```
# proof it isn't doing anything string related
'hi' contains 'h';
# Method 'polymod' not found for invocant of class 'Str'

```

```
# Since it uses a Set operator the second argument has to be an Int
# not a Str
say 123 contains '1'; # False
# not a Rat
say 123 contains 1.0; # False
# not a Num
say 123 contains 1e0; # False
# but an Int
say 123 contains 1; # True

```

### Explanation:

`polymod` is similar to `divmod` from other languages, except it takes the number and a list of divisors. Here I give it an endless list of `10`s so that it splits it up into a list of digits.

Then I see if the resulting list contains the second argument by using the *'contains as member'* (  / `(cont)` ) Set operator.
> 3 votes

# Answer
# Haskell, 42 bytes

Called like `number!digitToFind`:

```
n!d|n<d=1>2|mod n 10==d=1<2|1<2=div n 10!d

```
> 2 votes

# Answer
# MATL, ~~15~~ 14 bytes

```
t`10H#\t]xN$hm

```

**Try it online!**

```
t                   % take 1st input (number) implicitly. Duplicate
 `      ]           % do...while loop
  10                % push number 10, to be used as divisor
    H#\             % divmod. Pushes remainder and then quotient
       t            % duplicate quotient. Used as loop condition: exit if zero
         x          % delete last quotient (which is zero)
          N$h       % concatenate all partial results in an array
             =      % take 2nd input (digit) implicitly.
              m     % ismember function. True if digit is in array

```
> 2 votes

# Answer
# PHP, ~~66~~ ~~65~~ ~~62~~ 47 bytes

```
in_array($d,array_map('intval',str_split($n)));

```

`$n` is the number to be searched
`$d` is the digit to search for

This code converts the `number` into `array[number]`, then scans the array for a matching digit. Returns `true` if any digit matches.

Alternatively, if `number->string->array[string]->array[number]` is not valid (even though no operations use it *as* a string), there's this at **62 bytes**, for any `$n > 0`:

```
function f($n,$d){return$n&&($d==$n%10||f(($n-$n%10)/10,$d));}

```
> 0 votes

# Answer
# Python 3, 59

It uses the same approach as every other approach.

```
def f(x,s):
 while x:
  x,r=divmod(x,10)
  if r==s:return 1

```
> 0 votes

# Answer
# Befunge-93, 38 bytes

```
&&00pv >0.@.1<
%*25:<_^#:/_ ^#\*25-g00

```

Arguments are taken in the form `MainNum Digit`. It's the same algorithm that everyone else is doing (check if mod 10 is equal to the digit; if not, div 10 until it equals 0), since that's pretty much the optimal way to do this one.
> 0 votes

# Answer
## JavaScript (ES6), 30 bytes

```
d=>g=n=>n%10==d||n>9&&g(n/10|0)

```

Examples:

```
f=d=>g=n=>n%10==d||n>9&&g(n/10|0)
f(0)(0) -> true
f(0)(10) -> true
f(0)(12) -> false
f(1)(12) -> true
f(2)(12) -> true
f(3)(12) -> false

```
> 0 votes

---
Tags: code-golf, number
---


# Question
Title: Output all numbers below certain number containing certain digits
# Output all numbers in certain range containing certain digits

### Task

1. Take an input of digits through console, prompt, or a file (in the decimal number system). These digits should be separated by spaces.
2. Take an input of the "maximum" through console, prompt, or a file
3. If you use a file, the program must output `"[Data taken from file]"`
4. Print all natural numbers (including 0) below the maximum containing **at least one** of the digits specified by the user (they may contain other digits), separated by a single space. **Leading `0`s do not count!**
5. If there is a sequence of 10 or more consecutive numbers, it should output the first and last, separated by a `-->`

### Rules

* Standard loopholes are (obviously) not allowed
* Programs must complete the tasks above
* The answer with the fewest characters wins

### Examples

```
>>> 1 3
>>> 100
1 3 10 --> 19 21 23 30 --> 39 41 43 51 53 61 63 71 73 81 83 91 93

```

---

```
>>> 1 2 4 5 6 7
>>> 29
1 2 4 5 6 7 10 --> 28

```

---

```
>>> 0 1 2 3 4 5 6 7 8 9
>>> 9999999
0 --> 9999998

```

---

```
[Data taken from file]
1 3 5 7 9

```

# Answer
## GolfScript ~~74~~ 71 (DEMO)

```
' ':§/)~\n*:x;,{`x&},99:c;{.c)=!{§\}*:c}%[§]/{.,9>{('-->'@)\;}{~}if}%§*

```

### Description:

The code expects the parameters passed via the console, like so:

```
echo "1 3 100" | ruby golfscript.rb numbers.gs

```

Here's the annotated code:

```
' ':§/                  # Split input by space and save the
                        # space character in variable `§`

)~                      # Take the last input and convert to int
                        # This is the "maximum" parameter.

\n*:x;                  # Take the list of digits and join them with
                        # newlines, resulting in a string.
                        # Save the result in variable `x` and take it
                        # off the stack

,                       # Take the "maximum" parameter and make an
                        # array [0, max)

{`x&},                  # Filter the array, leaving only numbers that
                        # contain the right digits (that have at least
                        # one char in common with string `x`)

99:c;                   # Save the value 99 in a new variable, `c`.

{                       # For each element (`n`) in the array:
  .                     #   - duplicate `n` on the stack
  c)=!{§\}*             #   - if it does not equal `c`+1 add a space before it
  :c                    #   - assign the value of `n` to `c`
}%

[§]/                    # Split the resulting array by spaces

{                       # For each element `a` in the array of arrays:
  .                     #   - duplicate `a` on the stack
  ,9>                   #   - check if length > 9
  {('-->'@)\;}          #   - if `a`'s length is >9, then push "(min)", "-->" and "(max)"
                        #     on the stack
  {~}if                 #   - otherwise, just place the elements of the current array
                        #     on the stack
}%
§*                      # make a string representing the elements of the resulting array,
                        # separated by spaces

```
> 3 votes

# Answer
## Ruby, ~~186~~ ~~181~~ 177 bytes

```
a=gets.split;puts ([0]+(0...gets.to_i).select{|x|(x.to_s.split('')&a).any?}).each_cons(2).slice_before{|m,n|m+1<n}.map{|a|c=a.map &:last;c.count>9?[c[0],'-->',c.last]:c}.join' '

```

Ungolfed explanation:

```
# Read numbers from input and split into array
a = gets.split

# Loop from 0 to maximum number, exclusive
puts ([0]+(0...gets.to_i).select { |x|
  # Only include numbers that include at least one input digit
  (x.to_s.split('')&a).any?
})    # Add dummy element to the beginning of array
.each_cons(2)   # Get each array of 2 consecutive elements
.slice_before { |m, n| #
  m + 1 < n # "Slice" the array if m and n are not consecutive
}.map { |a|
  c = a.map &:last # Get all the last elements in `a`
  if c.count > 9
    # 10 or more consecutive elements. Get the first and last, and
    # an arrow in-between
    [c[0],'-->',c.last]
  else
    c
  end
}.join ' ' # Add space in-between all elements, and print result

```
> 5 votes

# Answer
# JavaScript (E6) 153 ~~157 161 163 177~~

Input and output via `prompt`

The main loop filters the numbers with a regexp and builds spans of consecutive numbers (as arrays). The O function concatenates the spans converting them to string. If the elements in a span array are 10 or more, instead of taking all elelements it just take the first and last number.

Test in FireFox/FireBug console

```
P=prompt,m=P(d=P());
O=_=>(
  o+=s[9]?s[0]+" -->"+p:s.join(''),s=[]
);
for(s=[o=''],p=n=0;n<m;++n)
  (n+'').match("["+d+"]")&&
  (
    n+~p&&O(),s.push(p=' '+n)
  );
O(),P(o)

```
> 4 votes

# Answer
## Mathematica, ~~233~~ ~~191~~ ~~171~~ 165 bytes

```
t=StringSplit;Flatten[Split[Cases[Range@Input[d=t@InputString[]]-1,m_/;ToString@m~t~""⋂d!={}],#2-#<2&]/.{e:{__Integer}/;Length@e>9:>{#&@@e,"-->",Last@e}}]~Row~"  "

```

I'm taking the input from two prompts which is as close to command line as it gets in Mathematica.

Ungolfed:

```
t = StringSplit;
Flatten[
  Split[
    Cases[
     Range@Input[d = t@InputString[]] - 1,
     m_ /; ToString@m~t~"" \[Intersection] d != {}
     ],
    #2 - # < 2 &
    ] /. {e : {__Integer} /; Length@e > 9 :> {# & @@ e, "-->", Last@e}}
  ]~Row~"  "

```

I'm simply filtering a range with all numbers to the relevant ones and then I'm collapsing consecutive subsequences with a repeated rule replacement.
> 3 votes

# Answer
## Perl - ~~170~~ 162

```
$a=<>;chop$a;$a=~s/ /|/g;@b=grep{/$a/}(0..<>-1);while(++$c<@b){if($b[$c]-$b[$c-1]>1){($e=$c-$d)>9&&splice(@b,$d+1,$e-2,'-->')&&($c-=$e-3);$d=$c}}print join' ',@b

```

Ungolfed with comments:

```
$a=<>;    #Read digits
chop$a;$a=~s/ /|/g;    #Turn digit string into regex
@b=grep{/$a/}(0..<>-1);    #Assign @b as list of numbers from 0 to second input which match the digits
while(++$c<@b){    #Loop $c through indexes of list
    if($b[$c]-$b[$c-1]>1){    #If next number is not consecutive, do arrow adding stuff
        ($e=$c-$d)>9&&    #If the number of previous consecutive numbers is at least 10
            splice(@b,$d+1,$e-2,'-->')&&    #Replace all but the first and last with '-->'
            ($c-=$e-3);    #Subtract from index to compensate for decreased list length
        $d=$c    #Set $d (fist index of consecutive range) to current index
    }
}
print join' ',@b    #Print the list

```
> 3 votes

# Answer
# Ruby, 105 (or 110 if you need to add `.chop` to the gets to make your input work)

Run with command line flags `pl`.

```
r=/[#$_]/
$_=(?1...gets).grep(r).slice_before{|e|-1>eval("#@l-"+@l=e)}.map{|a|a[9]?[a[0],'-->',a[-1]]:a}*' '

```

Convert the first input to a character class in a regex. Generate all numeric strings between 1 and the next input (exclusive) and find the ones that match the regex. `slice_before` trick is stolen from August to find contiguous ranges, it gets shorter by using an instance variable to remember the last element so I don't need `each_cons`, but longer since I'm working with strings. I check for ranges of size 10 or more by seeing whether they have a 10th element or not (`a[9]`), and replace their internal elements with the arrow.
> 3 votes

# Answer
# Python - ~~208 202~~ 211

```
D=raw_input()
n=input()
s=[`i`for i in range(n)if sum(d in`i`for d in D)]
i=0
while i<len(s):
 j=len(s)
 while j:
  j-=1
  try:
   if int(s[j])-int(s[i])==j-i>8:s[i+1:j]=['-->']
  except:1
 i+=1
print' '.join(s)

```
> 2 votes

# Answer
# Bash+coreutils, 94 bytes

```
seq -s\  0 $[$1-1]|sed -r "s/\b[^ ${2// }]+\b/:/g
s/([0-9]+)( [0-9]+){9,}/\1 -->\2/g
s/: ?//g"

```
* `seq` generates all numbers below the maximum
* The first `sed` line replaces any number not containing the interesting digits with `:`
* The second `sed` line searches for runs of 10 or more space-separated numbers and replaces with `start --> end`
* The final `sed` line removes unnecessary `:` and spaces.

### Output:

```
$ ./belowdigits.sh 100 "1 3"
1 3 10 --> 19 21 23 30 --> 39 41 43 51 53 61 63 71 73 81 83 91 93
$ ./belowdigits.sh 29 "1 2 4 5 6 7"
1 2 4 5 6 7 10 --> 28
$ ./belowdigits.sh 999999 "0 1 2 3 4 5 6 7 8 9"
0 --> 999998
$

```
> 2 votes

# Answer
## Python, 227

Currently the longest, but whatever.

```
a=raw_input().split()
l=[i for i in range(input())if any(x in str(i)for x in a)]
for i in l:
 for j in l[::-1]:
  try:L=l.index;l=l[:L(i)+1]+['-->']+l[L(j):]if j-i==L(j)-L(i)and j-i>8 else l
  except:1
print' '.join(map(str,l))

```
> 1 votes

# Answer
# Haskell, ~~195~~ 194

```
main=interact$(\[d,m]->v$f(any(`elem`f(/=' ')d).s)[0..read m-1]).lines
s=show
f=filter
v l@(x:m)|g l>x+8=unwords[s x,"->",s$g l,v$f(>g l)l]|0<1=s x++' ':v m
v[]=""
g s=f(`notElem`s)[s!!0..]!!0-1

```

not very short but Imho quite good for this specific question and language.
> 1 votes

# Answer
# Python 2, 202 191

Another try at Python, using the same idea as @August's Ruby solution:

```
a=raw_input()
s=[x for x in range(input())if any(c in`x`for c in a)]
for _,g in __import__('itertools').groupby(s,lambda x:x+1in s):
 l=map(str,g)
 print len(l)<9and' '.join(l)or l[0]+' -->',

```

PS: Coincidentally, the first two lines ended up nearly identical to both other Python entries.
> 1 votes

# Answer
# R 224 w/o Comment

```
a=as.character
l=length
x=a(scan())                                                 # Read digits
s=a(0:(scan()-1))                                           # Read max number
p=as.numeric(s[Reduce(`|`,lapply(x,function(x)grepl(x,s)))])# Find all numbers we want
j=1                                                         # Print the arrow "-->"
for (i in 1:l(z<-c(rle(diff(p))$l,1))){if(z[i]<9)cat(p[j:(j+z[i]-1)],"")else
cat(p[j],"-->","")
j=j+z[i]}

```
> 1 votes

# Answer
## PHP, ~~273~~ ~~258~~ ~~255~~ ~~248~~ ~~256~~ ~~239~~ 234 bytes

What a mess.

### Submission:

```
function n($s,$b){$r=$q=$f="";for($g=-1;$g++<$b;){$i=0;foreach(explode(" ",$s)as$d){$i+=in_array($d,str_split($g));}if($i&&$b-$g){$q[]=$g;$f=$f?:$g;}elseif($f){$r.=($g-$f>9?$q[0]." --> ".($g-1):implode(" ",$q))." ";$q=$f="";}}echo$r;}

```

### Exploded view:

```
function n($s, $b) {
  $r = $q = $f = "";
  for ($g = -1; $g++ < $b;) {
    $i = 0;
    foreach(explode(" ", $s) as $d) {
      $i += in_array($d, str_split($g));
    }
    if ($i && $b-$g) {
      $q[] = $g;
      $f = $f ?: $g;
    } elseif ($f){
      $r .= ($g-$f > 9 ? $q[0] . " --> " . ($g-1)
                       : implode(" ", $q)        ) . " ";
      $q = $f = "";
    }
  }
  echo $r;
}

```

### Variable explanations:

`$b`: *string*, upper **b**ound (input)
`$s`: *string*, digit **s**tring (input)
`$d`: *int*, individual **d**igit in `$s`
`$g`: *int*, current **g**uess
`$i`: *int*, number of times a digit exists **i**n the current guess
`$f`: *int*, **f**irst correct guess in a chain
`$q`: *array*, correct guess **q**ueue
`$r`: *string*, final **r**esult (output)

This is **super** unoptimized, still tweaking it.

**Edits:**
**-18:** Combining variable inits, merging two `$i` inits.
**-7:** Removing `$a` declaration.
**+8:** Fixed two bugs: now allows `0` as output, now allows `$b-1` and `--> $b-1` as output.
**-17:** God, I love ternary operators.
**-5:** Let's treat `$i` as an `int` full-time, and simplify the resets.
> 1 votes

---
Tags: code-golf, number
---


# Question
Title: Four steps to the left: vipers. Four steps to the right: a cliff. Don't die!
## Introduction

Suppose for a moment that the vipers and cliff are only **two** steps away, instead of three.

```
            o
           ---
Hsss!       |
 ';;' ___  /_\  ___  _
                      |

```

You are, unfortunately, a captive of a sadistic torturer. You **must** take a step either to the left or to the right every turn. If you don't, they shoot you dead instantly. You are allowed to plan out your steps beforehand, but once you take your first step, you can't change your plan. (And no dawdling either; they'll shoot you.)

Suddenly, a bright idea comes to mind...

> Ah! I can just alternate stepping right and left! Step right, step left, step right, step left, and so on...

Ah ah ah, not so fast. Like I said, the torturer is sadistic. They get to choose whether you take every step, or every second step, or every third step, and so on. So if you naively choose the sequence `RLRLRL...` then they can force you to take every second step, which starts with `LL`. Uh oh! You've been bitten by vipers! Blackness swoops over you and all else fades away...

Actually no, you're not dead yet. You still have to come up with your plan. After thinking about it for a few minutes, you realize you are doomed. There is no way to plan out a series of steps that will guarantee your survival. The best you can come up with is `RLLRLRRLLRR`.1 Eleven safe steps and no more. If the twelfth step is `R`, then the Torturer will make you take every step and then the last three steps send you off the cliff. If the twelfth step is `L`, then the Torturer will make you take every third step (`LRLL`), which puts you right in the brood of vipers and their lethal bites.

You pick `R` as the twelfth step, hoping to delay your demise as long as possible. With the wind roaring in your ears, you wonder to yourself...

> What if I had three steps?

---

**Spoiler alert!**

You would still die. As it turns out, no matter how many steps you have, there will be some point where no matter what choice you make, there is a sequence of steps your Torturer can pick to ensure you meet your deadly fate.2 However, when the vipers and cliff are three steps away, you can take a total of 1160 safe steps and when they're four steps away, there are at least 13,000 safe steps!3

## The challenge

Given a single integer `n < 13000`, output a sequence of `n` safe steps, assuming the cliff and the vipers are four steps away.

## Rules

* Can be either a full program or a function.
* Input can be taken through STDIN or equivalent, or as a function argument.
* Output must have **two distinct characters** (which can be `+/-`, `R/L`, `1/0`, etc.).
* Any whitespace in the output doesn't matter.
* Hard-coding a solution is not allowed. That would trivialize this challenge.
* Your program should (in theory) finish in a decent amount of time. As in, `n=13000` might take like a month, but it shouldn't take a thousand years or more. That is, **no brute force.** (Well, at least *try* to avoid it.)
* **Life bonus:** provide a series of `2000` safe steps. If you do this, the Torturer will be so impressed by your tenacity, perseverance, and forethought that they'll let you live. *This one time.* (Treat this sequence as a binary number and provide the decimal equivalent for verification. This is intended to reward answers that finish quickly as answers are allowed to take a very long time.)
* **Score: bytes**, unless you qualify for the **bonus - multiply by 0.75**.

---

1 There is a good explanation of this problem and "solution" by one of the stars of Numberphile, James Grime, over on his YouTube channel here: https://www.youtube.com/watch?v=pFHsrCNtJu4 .

2 This 80-year-old conjecture, known as Erdos' discrepancy problem, was proved very recently by Terence Tao. Here is a very nice article on Quanta Magazine about this: https://www.quantamagazine.org/20151001-tao-erdos-discrepancy-problem/ .

3 Source: *A SAT Attack on the Erdos Discrepancy Conjecture*, by Boris Konev and Alexei Lisitsa. Retrieved from here: http://arxiv.org/pdf/1402.2184v2.pdf .

# Answer
> 6 votes
# Java, 915 * 0.75 = 686.25

```
import java.util.*;class E implements Comparable<E>{static
int n,m,t,u;byte[]a;int k=2,b,d;E(){a=new byte[5];a[1]=13;}E(E
x){a=Arrays.copyOf(x.a,n+1);k=x.k;d=x.d;b=x.b;}int
g(int x){return(a[x]+1)%3-1;}void s(int x,int y){a[x]=(byte)(a[x]/3*3+(y+3)%3);}void
S(int x,int y){a[x]=(byte)(a[x]%3+(y+3)*3);}E
w(int x){if(g(k)==-x)return null;E e=new E(this);e.s(k,x);e.S(e.k++,x);for(m=0;++m<k;)if(k%m<1){u=e.a[m]/3-3+x;if(u==(k<9?2:4)*x)return
null;e.S(m,u);if(u==3*x){e.b++;if(k+m<=n){if(e.g(k+m)==x)return
null;e.s(k+m,-x);}}}return e;}public int compareTo(E o){m=d-o.d+(b-o.b)/60+(o.k-k)/150;return
m==0?o.k-k:m;}public static void main(String[]a){n=Integer.valueOf(a[0]);Queue<E>q=new PriorityQueue<>();q.add(new
E());for(;;){E x=q.remove(),y;if(x.k>n){for(t=0;++t<x.k;)System.out.print((x.g(t)+1)/2);return;}t=x.g(x.k<9?1:x.k%9==0?x.k/9:x.k%9);y=x.w(t);if(y!=null)q.add(y);y=x.w(-t);if(y!=null){y.d++;q.add(y);}}}}

```

Input is taken as a command-line argument.

This tries almost all possibilities (the only restriction is that the first 8 steps should only go within -1..1), going step by step, using a magic voodoo heuristic to choose which way to try first.

It solves 2000 and even 4000 within 1 second on my (fairly fast) computer. Needs more RAM for bigger numbers; the largest input I solved within 8GB is 5023 and it took about 30 seconds.

Decimal representation of the solution for 2000 steps, as requesed for the bonus:

```
67629177464446960798008264442022667063957880432486338092706841703491740570274032860458934082821213021464065304260003487277917407152662394728833698812373924467640518368465012204980858438160127647802572983143425507448999967241207186701518207195015015739598846687434709056793597015487555707466358473564611432637890414593517116857771284711814076853125419306285869381974622557155019992727242896503018802441210966188045211779436703341152749688824296759097963388158731237092792251164105828728858516951458791084595247591674731645830905744761534078963607725435881491831508342871545788662307953494333833994658998

```

Append `Yb` to it in CJam to convert back to binary.

About the heuristic: first, there is a pattern I'm using: every 9 steps try to repeat the first 9, except every (9\*x)th step tries to repeat the x'th step. This is inspired from the solution I downloaded and used (hardcoded) in my python answer.

I'm keeping track of the number of times I deviated from the pattern, and also the number of times I got to an "edge" (1 step from dying). The heuristic function is basically a weighted combination of those 2 numbers and the number of steps taken so far.

The heuristic could be further tweaked to improve the speed, and there are several ways to add a random factor into it too.
In fact, I've just read about multiplicative functions in relation to this problem, and it looks like that can provide a *significant* improvement (TODO: implement this later).

Ungolfed and commented:

```
import java.util.*;

public class Erdos implements Comparable<Erdos> {
    static int n; // input (requested number of steps)
    static int m, t, u; // auxiliary variables

    byte[] a; // keeps each step and sum combined into 1 byte
    int k = 2; // number of steps + 1 (steps are 1-based)
    int edge; // number of times we got to an edge
    int diff; // number of differences from the expected pattern

    // start with one step
    Erdos() {
        a = new byte[5];
        set(1, 1);
        setSum(1, 1);
    }

    // copy constructor
    Erdos(Erdos x) {
        a = Arrays.copyOf(x.a, n + 1);
        k = x.k;
        diff = x.diff;
        edge = x.edge;
    }

    // get the x'th step (can be -1, 0 or 1)
    int get(int x) {
        return (a[x] + 1) % 3 - 1;
    }

    // set the x'th step
    void set(int x, int y) {
        a[x] = (byte) (a[x] / 3 * 3 + (y + 3) % 3);
    }

    // get the sum of every x'th step (should be within -3..3)
    int getSum(int x) {
        return a[x] / 3 - 3;
    }

    // set the sum of every x'th step
    void setSum(int x, int y) {
        a[x] = (byte) (a[x] % 3 + (y + 3) * 3);
    }

    // try to add a step with value x (1 or -1)
    Erdos grow(int x) {
        if (get(k) == -x) // predetermined step doesn't match
            return null;
        Erdos e = new Erdos(this);
        e.set(k, x);
        e.setSum(e.k++, x);
        for (m = 0; ++m < k;)
            if (k % m < 1) { // check all divisors of k
                u = e.getSum(m) + x; // updated sum
                if (u == (k < 9 ? 2 : 4) * x) // use limit 2 for the first 8 steps, 4 for the rest
                    return null; // dead
                e.setSum(m, u);
                if (u == 3 * x) { // we're at an edge
                    e.edge++;
                    if (k + m <= n) { // predetermine future step - should be going back
                        if (e.get(k + m) == x) // conflict
                            return null;
                        e.set(k + m, -x);
                    }
                }
            }
        return e;
    }

    public int compareTo(Erdos o) { // heuristic function
        m = diff - o.diff + (edge - o.edge) / 60 + (o.k - k) / 150;
        return m == 0 ? o.k - k : m;
    }

    public static void main(String[] a) {
        n = Integer.valueOf(a[0]);
        Queue<Erdos> q = new PriorityQueue<>();
        q.add(new Erdos());
        for (;;) {
            Erdos x = q.remove(), y;
            if (x.k > n) { // we made it
                for (t = 0; ++t < x.k;)
                    System.out.print((x.get(t) + 1) / 2);
                return;
            }
            t = x.get(x.k < 9 ? 1 : x.k % 9 == 0 ? x.k / 9 : x.k % 9); // next step based on the pattern
            y = x.grow(t);
            if (y != null)
                q.add(y);
            y = x.grow(-t);
            if (y != null) {
                y.diff++;
                q.add(y);
            }
        }
    }
}

```

# Answer
> 1 votes
# Python 2, 236 bytes

```
n=input();r=len;u=[("",[0]*(n//4))]
while n>r(u[-1][0]):
 y,t=u.pop()
 for c in 0,1:
  s=t[:];u+=(y+"LR"[c],s),
  for i in range(r(s)):
   if-~r(y)//-~i*-~i==-~r(y):s[i]+=2*c-1;
   if abs(s[i])>3:u.pop();break;
print(u[-1][0])

```

This is fairly fast, for a brute-force-ish method, only taking a few seconds for n=223, but much longer for n\>=224.

**Explanation:** Keep track of a list of string-list pairs (s,u), where the list u is such that u\[i\] is the current position after following every ith step in the string. For each string in the list, try to add "L" or "R", then change the values in the list that intersect. (i.e. if the resulting string has length 10, add or subtract 1 from positions 1,2,5 and 10, according to the directions you moved). If you exceed 3 or -3 throw the new pair away, otherwise keep it in the list. The longest strings are kept at the end. Once you have a string of length n, return it.

# Answer
> 0 votes
# Python 2, 729 bytes

```
n=0
for x in"eJytVU2LwyAQPWzTvZjjspcsxFYTBdNuQSEF+///1jp+p5o0hYVSBl9nfOObNz1MlAgqzMcEEwQkDyIkFpDYCW0UnChbyZJiK2sfhDcYmu9hT0GdIPQvLduAmoCvvqEssvq84CVCpLzrNcOOspLhY6/KswB6FmoSxGPBcWts7lsMp/0q83da1hgC6k7GoqBir1ruAFIVvWIdTi++oGIAyZw8mkuG03uDDc+rEsSWTmFBwbLgtTF8hl1e/lpCigR7+pM5V9lIqVJBjStzKNRRQDp6UOrvwga6VFrGcWz6YHwLNYWUYeZfWO/DQTq7i4dAxixeszmtFEw7Cr5v9R3lRVF55TDzY6QRrSfzF9NLE7lAZ+vLnGgYLZ/FlCuoRcOugeFduHTqRWmyh1J91XpIndIbEk8jifL8hs8qQ8vjAVoGqhK5Tm/O5svpXd82QH4Azq05kYnhj93PzLbcTisFzXWfDqIC5zsq3jU7UUhSh1R3L4+i4HCXKlrGyywSBttPr2zpL4gCDPtk2HPN5tgZFomzSDPfGAlASus+e4KlLcjS0vPQ0f5/mR/r1s4PcxsgMLRSMp617AveCuup2OCAPBT6yltWrPO9azsbp6fphR87Lc7VzcbEt5F4Ydg/NzhXTA==".decode("base64").decode("zip"):n=n*64+ord(x)
print bin(n)[2:input()+2]

```

I think this qualifies for the bonus too if the idea is "to reward answers that finish quickly".

However, this is a hard-coded answer, which is not in the spirit of the challenge (although not explicitly disallowed when I wrote it).

---
Tags: code-golf, sequence, subsequence
---


title: Tips for Golfing in Vitsy

text:
# Question
Title: Tips for Golfing in Vitsy
While there are only a few users of the Vitsy programming language right now, I wish to create a place for tips for golfing in Vitsy.

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

For reference, the online interpreter is here, the esolang page is here, and you can receive answer-per-answer help here.

# Answer
# Do not doubt the power of `m`

Background: `Fm` calls the a specified line index in the current Vitsy class. (`F` is the line index you seek).

The `m` command (method) has saved me literally hundreds of bytes in the past. Any algorithm that uses repeated steps, or a common character sequence (such as `D1M-` (floor algorithm)).

This is extremely helpful in repetitive kolmogorov complexity challenges.

Instead of:

```
WD1M-(something else here)WD1M-(something different)WD1M-l\[NaO]
```

Use:

```
1m(something else here)1m(something different)1ml\[NaO]
WD1M-
```

(floor(prompt))

Also, you can return from method statements with `;`, allowing for looping until condition(s) (over the general `[ ]` syntax, which isn't as powerful):

```
1mN
<;)
```

(loops through code until finding non-zero, popping it from the stack and returning to first line)
> 2 votes

# Answer
# Remember that `\[]` *always runs at least once*

Even if the top item of the stack is zero or less, `\[]` always runs. Think of it more as a `do{}for();` loop. This has caught me off more than once, but it is important.
> 2 votes

# Answer
# Filling Zeroes on an Empty Stack

Normally, to fill up the stack with a number, you would do something like this:

```
a\a

```

This fills up the stack with 10 10s, by pushing 10 10 times. However, if you wanted to push 10 0s, you'd do this:

```
a\0

```

After a recent update, however, the stack will attempt to fix for IndexOutOfBoundsExceptions by pushing 0s to a possibly empty stack, meaning that, if on an empty stack, you can do:

```
a%

```

Since `%` calls `multistack`, it tries to access every member between the top item (which is nothing after it pops `10`) and the index you specify. Therefore, you get a stack with 10 0s when this is called. You can use this trick up to approximately 11380, although, annoyingly, it doesn't always go to a specific point...

```
UNKNOWN:Desktop addisonc17$ vitsy --code "2d^2b^+2a^+26^+25^+24^+5+%lNaO"
java.lang.StackOverflowError thrown in [command line] at command #0,25: %
UNKNOWN:Desktop addisonc17$ vitsy --code "2d^2b^+2a^+26^+25^+24^+5+%lNaO"
11381

```

Past that, you'll have to use the normal duplication method.
> 1 votes

---
Tags: code-golf, tips
---


title: A little bool magic

text:
# Question
Title: A little bool magic
# Challenge

Given the following C# method:

```
private static bool Test(bool a, bool b)
{
    if (a && b) return false;
    if (a) if (b) return true;
    return false;
}

```

Supply the values `a` and `b` so that `true` is returned.

# Winning condition

The first entry who can supply the correct arguments to make the given method evaluate to `true` wins.

# Answer
```
static void Main(string[] args)
{
    bool a, b;
    unsafe
    {
        int* pa = (int*)&a;
        int* pb = (int*)&b;
        *pa = 1;
        *pb = 2;
    }

        Console.Write(Test(a, b));
}

```

This prints `True` for me with the C# implementation that comes with Visual Studio 2015. I actually don't know any C#, but I figured I'd try to write some C code and see if it worked. I was hoping that the compiler would assume that True is always represented as 1 and use a bitwise AND. In Debug mode, this is indeed the case (it worked with Release too). It uses a bitwise AND for the first condition and two comparisons to zero for the second:

```
            if (a && b) return false;
002C2E92  movzx       eax,byte ptr [ebp-3Ch]
002C2E96  movzx       edx,byte ptr [ebp-40h]
002C2E9A  and         eax,edx
002C2E9C  and         eax,0FFh
002C2EA1  mov         dword ptr [ebp-44h],eax
002C2EA4  cmp         dword ptr [ebp-44h],0
002C2EA8  je          002C2EB2
002C2EAA  xor         edx,edx
002C2EAC  mov         dword ptr [ebp-48h],edx
002C2EAF  nop
002C2EB0  jmp         002C2EE4
            if (a) if (b) return true;
002C2EB2  movzx       eax,byte ptr [ebp-3Ch]
002C2EB6  mov         dword ptr [ebp-4Ch],eax
002C2EB9  cmp         dword ptr [ebp-4Ch],0
002C2EBD  je          002C2EDC
002C2EBF  movzx       eax,byte ptr [ebp-40h]
002C2EC3  mov         dword ptr [ebp-50h],eax
002C2EC6  cmp         dword ptr [ebp-50h],0
002C2ECA  je          002C2EDC
002C2ECC  mov         eax,1
002C2ED1  and         eax,0FFh
002C2ED6  mov         dword ptr [ebp-48h],eax
002C2ED9  nop
002C2EDA  jmp         002C2EE4
            return false;
002C2EDC  xor         edx,edx
002C2EDE  mov         dword ptr [ebp-48h],edx
002C2EE1  nop
002C2EE2  jmp         002C2EE4
        }
002C2EE4  mov         eax,dword ptr [ebp-48h]
002C2EE7  lea         esp,[ebp-0Ch]
002C2EEA  pop         ebx
002C2EEB  pop         esi
002C2EEC  pop         edi
002C2EED  pop         ebp
002C2EEE  ret

```
> 20 votes

---
Tags: programming-puzzle, c#
---


title: Find the beats in an MP3 file

text:
# Question
Title: Find the beats in an MP3 file
In this challenge, your task is to take an simple recording in mp3 format and find the time offsets of the beats in the file. Two example recordings are here:

https://dl.dropboxusercontent.com/u/24197429/beats.mp3 https://dl.dropboxusercontent.com/u/24197429/beats2.mp3

Here is the third recording with much more noise than the two previous:

https://dl.dropboxusercontent.com/u/24197429/noisy-beats.mp3

For example, the first recording is 65 seconds long and contains exactly (unless I miscounted!) 76 beats. Your job is to devise a program that takes such an mp3 file as input and outputs a sequence of the time offsets in milliseconds of the beats in the file. A beat is defined to occur, of course, when the guitarist playing plucks one or more strings.

Your solution must:

* Work on any mp3 file of similar "complexity". It can fail on to noisy recordings or to quickly played melodies -- I don't care.
* Be fairly precise. Tolerance is +/- 50 ms. So if the beat occurs at 1500 ms and your solution reports 1400, then that is unacceptable.
* Use only free software. Calling ffmpeg is allowed as is using any freely available third party software for your language of choice.

The winning criteria is ability to successfully detect beats despite noise in the supplied files. In case of a tie, the shortest solution wins (length of 3rd party code isn't added to the count).

# Answer
# Python 2.7 492 bytes (beats.mp3 only)

This answer can identify the beats in `beats.mp3`, but will not identify all notes on `beats2.mp3` or `noisy-beats.mp3`. After the description of my code, I'll go into detail as to why.

This uses PyDub (https://github.com/jiaaro/pydub) to read in the MP3. All other processing is NumPy.

## Golfed Code

Takes a single command line argument with the file name. It will output each beat in ms on a separate line.

```
import sys
from math import *
from numpy import *
from pydub import AudioSegment
p=square(AudioSegment.from_mp3(sys.argv[1]).set_channels(1).get_array_of_samples())
n=len(p)
t=arange(n)/44.1
h=array([.54-.46*cos(i/477) for i in range(3001)])
p=convolve(p,h, 'same')
d=[p[i]-p[max(0,i-500)] for i in xrange(n)]
e=sort(d)
e=d>e[int(.94*n)]
i=0
while i<n:
 if e[i]:
  u=o=0
  j=i
  while u<2e3:
   u=0 if e[j] else u+1
   #u=(0,u+1)[e[j]]
   o+=e[j]
   j+=1
  if o>500:
   print "%g"%t[argmax(d[i:j])+i]
  i=j
 i+=1

```

## Ungolfed Code

```
# Import stuff
import sys
from math import *
from numpy import *
from pydub import AudioSegment

# Read in the audio file, convert from stereo to mono
song = AudioSegment.from_mp3(sys.argv[1]).set_channels(1).get_array_of_samples()

# Convert to power by squaring it
signal = square(song)
numSamples = len(signal)

# Create an array with the times stored in ms, instead of samples
times = arange(numSamples)/44.1

# Create a Hamming Window and filter the data with it. This gets rid of a lot of
# high frequency stuff.
h = array([.54-.46*cos(i/477) for i in range(3001)])
signal = convolve(signal,h, 'same') #The same flag gets rid of the time shift from this

# Differentiate the filtered signal to find where the power jumps up.
# To reduce noise from the operation, instead of using the previous sample,
# use the sample 500 samples ago.
diff = [signal[i] - signal[max(0,i-500)] for i in xrange(numSamples)]

# Identify the top 6% of the derivative values as possible beats
ecdf = sort(diff)
exceedsThresh = diff > ecdf[int(.94*numSamples)]

# Actually identify possible peaks
i = 0
while i < numSamples:
 if exceedsThresh[i]:
  underThresh = overThresh = 0
  j=i
  # Keep saving values until 2000 consecutive ones are under the threshold (~50ms)
  while underThresh < 2000:
   underThresh =0 if exceedsThresh[j] else underThresh+1
   overThresh += exceedsThresh[j]
   j += 1
  # If at least 500 of those samples were over the threshold, take the maximum one
  # to be the beat definition
  if overThresh > 500:
   print "%g"%times[argmax(diff[i:j])+i]
  i=j
 i+=1

```

## Why I miss notes on the other files (and why they are incredibly challenging)

My code looks at changes in signal power in order to find the notes. For `beats.mp3`, this works really well. This spectrogram shows how the power is distributed over time (x axis) and frequency (y axis). My code basically collapses the y axis down to a single line.  Visually, it's really easy to see where the beats are. There's a yellow line that tapers off again and again. I highly encourage you to listen to `beats.mp3` while you follow along on the spectrogram to see how it works.

Next I'll go to `noisy-beats.mp3` (because that's actually easier than `beats2.mp3`. . Once again, see if you can follow along with recording. Most of the lines are fainter, but still there. However, in some spots, the bottom string is still ringing when the quiet notes start. That makes finding them especially hard, because now, you have to find them by changes in frequency (the y axis) rather than just amplitude.

`beats2.mp3` is incredibly challenging. Here's the spectrogram  In the first bit, there some lines, but some notes really bleed over the lines. To reliably identify notes, you'd have to start tracking the pitch of the notes (fundamental and harmonics) and seeing where those change. Once the first bit is working, the second bit is twice as hard as the tempo doubles!

Basically, to reliably identify all of these, I think it takes some fancy note detection code. Seems like this would be a good final project for someone in a DSP class.
> 6 votes

---
Tags: code-golf, music
---