# Question
Title: How on earth did llhuii output the Evil Numbers in 42 bytes of Python?
*This is a tips question for golfing in Python concerning the Evil Numbers question on Anarchy Golf.*

An number is evil if its binary expansion has an even number of 1's. The challenge is to print the first 400 evil numbers `0,3,5,...,795,797,798`, one per line.

The Python 2 submissions are led by llhuii with a 42-byte solution. The next best is 46 bytes by mitchs, followed by five 47-byte submissions. It seems llhuii has found something truly magical that has eluded many strong Python golfers for over 2 years. Saving 4 or 5 bytes is huge for such a short golf.

I'm still at 47 bytes. I'm hoping we can crack this puzzle as a community. If we get an answer jointly, I'd submit it under the names of everyone who contributed. An answer to this question can be a piece of code or a new idea or a piece of analysis. If you are llhuii, please don't spoil it for us yet.

Though submissions are not revealed because this problem is Endless, we're given some leads. The winning submission took 0.1699 seconds to run, much longer than any other, suggesting an inefficient method. From the byte statistics, of the 42 characters, 23 are alphanumeric `[0-9A-Za-z]` and 19 are ASCII symbols. This means there is no whitespace in llhuii's solution.

You can test your code on the problem page, choosing Python from the language dropdown or uploading a `.py` file. Note that:

* Python 2.7 is used
* Your code must be a full program that prints
* There's no input for this problem, like
* Your program just has to print the 400 values as given, even if it would break on larger values
* Programs have 2 seconds to run
* Programs may terminate with error
* You may use `exec`; the "exec is denied" refers to shell exec

# Answer
> 61 votes
This isn't the same solution as llhuii's, but it's also 42 bytes long.

```
n=0;exec'print n;n^=(n^n+2)%3/2;n+=2;'*400

```

Try it online!

Thanks to @JonathanFrech, we're now at 40 bytes.

```
n=0;exec'print n;n=n+2^(n^n+2)/2%3;'*400

```

Try it online!

There's another byte to be saved, for a total of 39.

```
n=0;exec'print n;n=n+2^-(n^n+2)%3;'*400

```

Try it online!

# Answer
> 45 votes
## Getting 39 bytes

This is an explanation of how I got a 39-byte solution, which Dennis and JonathanFrech found separately as well. Or, rather, it explains how one could arrive at the answer in hindsight, in a way that's much nicer than my actual path to it, which was full of muddy reasoning and dead ends.

```
n=0
exec"print n;n=n+2^-(n+2^n)%3;"*400

```

Writing this a bit less golfed and with more parens, this looks like:

```
n=0
for _ in range(400):
  print n
  n=(n+2)^(-((n+2)^n))%3

```

**Bit parities**

We start with an idea from my 47-byte solution to output all numbers of the form `n=2*k+b` where `k` counts up `0,1,...,399` and `b` is a parity bit that makes the overall number of 1's even.

Let's write `par(x)` for the *bit parity* of `x`, that is the xor (`^`) all of bits in `x`. This is 0 if there's an even number of 1-bits (number is evil), and 1 if there's an odd number of 1-bits. For `n=2*k+b`, we have `par(n) = par(k)^b`, so to achieve evil `par(n)==0` we need `b=par(k)`, i.e. the last bit of `n` to be the bit parity of the preceding bits.

My first efforts at golfing were on expressing the `par(k)`, at first directly with `bin(k).count('1')%2`, and then with bit manipulation.

**Parity updates**

Still, there didn't seem to be a short expression. Instead, it helped to realize that there's more info to work with. Rather than just computing the bit parity of the current number,

```
k  ---->  par(k)

```

we can update the bit parity as we increment `k` to `k+1`.

```
k   ---->  par(k)
      |
      v
k+1 ---->  par(k+1)

```

That is, since we're counting up `k=0,1,2,...`, we merely need to maintain the current bit parity rather than calculating it from scratch each time. The bit parity update `par(k+1)^par(k)` is the parity of the number of bits flipped in going from `k` to `k+1`, that is `par((k+1)^k)`.

```
par(k+1) ^ par(k) = par((k+1)^k)
par(k+1) = par(k) ^ par((k+1)^k)

```

**Form of `(k+1)^k`**

Now we need to compute `par((k+1)^k)`. It might seem like we've gotten nowhere because computing bit parity is exactly the problem we're trying to solve. But, numbers expressed as `(k+1)^k` have the form `1,3,7,15,..`, that is one below a power of 2, a fact often used in bit hacks. Let's see why that is.

When we increment `k`, the effect of the binary carries is to invert the last `0` and all `1`'s to its right, creating a new leading `0` if there were none. For example, take `k=43=0b101011`

```
      **
  101011  (43)
 +     1
  ------
= 101100  (44)

  101011  (43)
 ^101100  (44)
  ------
= 000111  (77)

```

The columns causing a carry are marked with `*`. These have a `1` change to a `0` and pass on a carry bit of `1`, which keeps propagating left until it hits a `0` in `k`, which changes to `1`. Any bits further to the left are unaffected. So, when `k^(k+1)` checks which bit positions change `k` to `k+1`, it finds the positions of the rightmost `0` and the `1`'s to its right. That is, the changed bits form a suffix, so result is 0's followed by one or more 1's. Without the leading zeroes, there are binary numbers `1, 11, 111, 1111, ...` that are one below a power of 2.

**Computing `par((k+1)^k)`**

Now that we understand that `(k+1)^k` is limited to `1,3,7,15,...`, let's find a way to compute the bit parity of such numbers. Here, a useful fact is that `1,2,4,8,16,...` alternate modulo `3` between `1` and `2`, since `2==-1 mod 3` . So, taking `1,3,7,15,31,63...` modulo `3` gives `1,0,1,0,1,0...`, which are exactly their bit parities. Perfect!

So, we can do the update `par(k+1) = par(k) ^ par((k+1)^k)` as

```
par(k+1) = par(k) ^ ((k+1)^k)%3

```

Using `b` as the variable we're storing the parity in, this looks like

```
b^=((k+1)^k)%3

```

**Writing the code**

Putting this together in code, we start `k` and the parity bit `b` both at `0`, then repeatedly print `n=2*k+b` and update `b=b^((k+1)^k)%3` and `k=k+1`.

*46 bytes*

```
k=b=0
exec"print 2*k+b;b^=(k+1^k)%3;k+=1;"*400

```

Try it online!

We removed parens around `k+1` in `((k+1)^k)%3` because Python precedence does the addition first anyway, weird as it looks.

**Code improvements**

We can do better though by working directly with a single variable `n=2*k+b` and performing the updates directly on it. Doing `k+=1` corresponds to `n+=2`. And, updating `b^=(k+1^k)%3` corresponds to `n^=(k+1^k)%3`. Here, `k=n/2` before updating `n`.

*44 bytes*

```
n=0
exec"print n;n^=(n/2+1^n/2)%3;n+=2;"*400

```

Try it online!

We can shorten `n/2+1^n/2` (remember this is `(n/2+1)^n/2`) by rewriting

```
n/2+1 ^ n/2
(n+2)/2 ^ n/2
(n+2 ^ n)/2

```

Since `/2` removes the last bit, it doesn't matter if we do it before or after xor-ing. So, we have `n^=(n+2^n)/2%3`. We can save another byte by noting that modulo `3`, `/2` is equivalent to `*2` is equivalent to `-`, noting that `n+2^n` is even so the division is actual halving without flooring. This gives `n^=-(n+2^n)%3`

*41 bytes*

```
n=0
exec"print n;n^=-(n+2^n)%3;n+=2;"*400

```

Try it online!

Finally, we can combine the operations `n^=c;n+=2` into `n=(n+2)^c`, where `c` is a bit. This works because `^c` acts only on the last bit and `+2` doesn't care about the last bit, so the operations commute. Again, precedence lets us omit parens and write `n=n+2^c`.

*39 bytes*

```
n=0
exec"print n;n=n+2^-(n+2^n)%3;"*400

```

Try it online!

# Answer
> 14 votes
*This gives my (xnor's) 47-byte solution and the thinking that led me to it. Don't read this if you want to figure this out yourself.*

A natural first idea is to iterate through the numbers 0 to 799, printing only those with an even number of 1's in binary.

**52 bytes**

```
for n in range(800):
 if~bin(n).count('1')%2:print n

```

Try it online!

Here, the `~` takes the bit complement so as to switch `even<->odd` in the count and give a truthy value only on even counts.

We can improve this method by generating all the values instead of filtering. Observe that the output values are the numbers 0 to 399, each with a bit appended to make the number of 1 bits even.

```
0 = 2*0 + 0
3 = 2*1 + 1
5 = 2*2 + 1
6 = 2*3 + 0
...

```

So, the `n`th number is either `2*n+b` with either `b=0` or `b=1`. The bit `b` can be found by counting `1`'s in the bits of `n` and taking the count modulo 2.

**49 bytes**

```
for n in range(400):print 2*n+bin(n).count('1')%2

```

Try it online!

We can cut the 2 bytes for `2*` by iterating over `0,2,4,...`, which doesn't chance the count of `1`'s. We can do this by using an `exec` loop that runs 400 times and increasing `n` by 2 each loop.

**47 bytes**

```
n=0;exec"print n+bin(n).count('1')%2;n+=2;"*400

```

Try it online!

And, that's my 47-byte solution. I suspect most if not all the other 47-byte solutions are the same.

# Answer
> 13 votes
# llhuii’s Python 3 submission

Here are the Python 3 submissions for Evil Numbers at the time of writing:

llhuii probably ported their trick to Python 3, and came up with a solution that is

* 3 bytes longer than their Python 2 solution, and
* has 45 − (25 + 18) = 2 bytes of whitespace.

Porting xnor’s 47B to Python 3 literally, we get this 50B:

```
n=0;exec("print(n+bin(n).count('1')%2);n+=2;"*400)

```

I submitted it as `ppcg(xnor)`. (It adds parentheses to `exec` and `print`, which are now functions.) It has different code stats from the other Python 3 answers, which all have some amount of whitespace in them. Interesting!

There’s a shorter way to rewrite it though (`exec` tends to lose its competitive edge in Python 3):

```
n=0
while n<800:print(n+bin(n).count('1')%2);n+=2

```

It’s 49 bytes. I submitted it as `ppcg(xnor,alternative)`. This has two bytes of whitespace, just like llhui’s answer! This leads me to believe that llhuii’s Python 3 answer looks kinda like this (newline, then a `while` loop.) So llhuii probably used `exec` in Python 2 and `while` in Python 3, just like us; this explains the whitespace discrepancy.

---

Our 47B became a 49B in Python 3. What’s interesting, now, is that llhuii’s 42B didn’t become a 44B, it became a 45B! **Something about llhuii’s solution takes one byte extra in Python 3.** This could mean a variety of things.

* The first thing that comes to mind is **division**: maybe llhuii uses `/` in Python 2, which became `//` in Python 3. (If they’re counting in twos like us, then `n/2` might be used to shift `n` back to the right by one bit?)
* The other thing that comes to mind is **unary operators after print**. Our `print blah` became `print(blah)` (1 byte extra), but if llhuii wrote something like `print~-blah` in Python 2, it’d become `print(~-blah)` in Python 3.
* Maybe there are other ideas. Please let me know.

Code statistics for all Py3 solutions, including mine now:

# Answer
> 8 votes
# Other approaches

### 1) Using a formula for A001969

Rather than converting to binary, it might be possible to take advantage of the following formula (from OEIS):

> ```
> a(1) = 0
> for n > 1: a(n) = 3*n-3-a(n/2) if n is even
>            a(n) = a((n+1)/2)+n-1 if n is odd
>
> ```

I'm very bad at golfing in Python, so I'm not even going to try. But here is a quick attempt in JS.

*NB: I don't think it would be a valid JS submission as it's just filling an array without displaying it. And even so, it's 5 bytes longer than the current best JS solution (which is 45 bytes). But that's not the point here anyway.*

```
for(a=[n=0,3];n<199;)a.push(2*++n+a[n],6*n+3-a[n])

```

```
for(a=[n=0,3];n<199;)a.push(2*++n+a[n],6*n+3-a[n])

console.log(a.join`, `)
```

Hopefully it may give some inspiration.

Using an array is probably not a good idea because it needs to be initialized and updated. It might be more efficient (code size wise) to use a ***recursive function*** instead, which would explain why the winning solution is ***taking more time*** than the other ones.

### 2) Building the Thue-Morse sequence with substitutions

In theory, this code should work:

```
n=0;a="1";b="0";exec"t=a;a+=b;b+=t;print(int(b[n]))+n;n+=2;"*400

```

Try it online! (runnable version limited to 20 terms)

It computes the Thue-Morse sequence with consecutive substitutions and looks for the position of 1's (Evil Numbers) in the same loop.

But:

* It's far too long in its current form
* It quickly leads to a memory overflow

### 3) Building the Thue-Morse sequence with bitwise operations

Starting from Wikipedia's Direct Definition of the Thue-Morse sequence, I've come to this algorithm (switching back to JS ... sorry):

```
for(e=n=0;n<799;)(e^=!(((x=n++^n)^x/2)&170))||console.log(n)

```

where we keep track of the current *evilness* of the sequence in ***e*** and use ***170*** as a bitmask of odd bits in a byte.

# Answer
> 7 votes
By construction, `n+n^n` is always evil, but my poor Python skills could only come up with a 61-byte solution:

```
for n in sorted(map(lambda n:n+n^n,range(512)))[:400]:print n

```

Thanks to @Peilonrayz for saving 5 bytes and @Mr.Xcoder for saving 1 byte:

```
for n in sorted(n^n*2for n in range(512))[:400]:print n

```

# Answer
> 6 votes
## Idea: Shorter bit parity

It takes many characters to do `bin(n).count('1')%2` to compute the parity of the bit-count. Maybe an arithmetic way is shorter, especially given a limited bit length.

A cute same-length way is `int(bin(n)[2:],3)%2`, interpreting the binary value as base `3` (or any odd base). Unfortunately, 4 of the bytes are spend removing the `0b` prefix. It also works to do `int(bin(n)[2:])%9%2`.

Another idea comes from combining bits using xor. If `n` has binary representation `abcdefghi`, then

```
n/16 = abcde
n%16 =  fghi

r = n/16 ^ n%16 has binary representation (a)(b^f)(c^g)(d^h)(e^i)

```

So, `r=n/16^n%16` is evil if and only if `n` is evil. We can then repeat that as `s=r/4^r%4`, a value `s` in `0,1,2,3`, of which `1` and `2` are not evil, checkable with `0<s<3`.

**52 bytes**

```
n=0;exec"r=n/16^n%16;print(0<r/4^r%4<3)+n;n+=2;"*400

```

Try it online!

This turned out a good deal longer. There's many knobs to turn though of how to split the number, how to check the final number (maybe a bit-based lookup table). I suspect these can only go so far though.

# Answer
> 6 votes
# Nested counters approach

I have an idea for a different approach, but I am not experienced enough in python golfing, so I'll leave it here for you guys to consider as another possible starting point for golfing.

### The ungolfed idea:

```
n=0
i=1
for _ in"01":
 i^=1
 for _ in"01":
  i^=1
  for _ in"01":
   i^=1
   for _ in"01":
    i^=1
    for _ in"01":
     i^=1
     for _ in"01":
      i^=1
      for _ in"01":
       i^=1
       for _ in"01":
        i^=1
        for _ in"01":
          i^=1
          if n<800:print i+n
          n+=2

```

Try it online!

Nine levels nesting depth, all the loops are the same, so in my mind they should be built by `exec"something"*9+"deepest stuff"`. In practice I don't know if it is possible to do something like this with a for cycle.

Things to consider for golfing:

* maybe there is some other possibility to cycle twice other than a for loop (I tried a quine-like approach with the string to be executed passed to itself as a formatting argument twice,but my head exploded).
* there could also be a better alternative to `if n<800:`, which is needed here because otherwise we would keep printing evil numbers up to 2^10

# Answer
> 5 votes
# Idea: Reduce over XOR

If you XOR all the bits of `n` together, it will be `0` for evil and `1` for non-evil. You can do this with a recursive function (which may have thus taken more time?), like so:

```
f=lambda n:f(n/2^n&1)if n>1else-~-n

```

This returns 1 for evil.

That's 35 bytes, and checks whether or not a number is evil. Unfortunately, `filter` is already 6 bytes so this wasn't the optimal solution verbatim but this idea can probably be golfed.

# Answer
> 4 votes
# Substitution method : {1 -\> {1, -1}, -1 -\> {-1, 1}}

You can also make this substitution 10 times {1 -\> {1, -1}, -1 -\> {-1, 1}}, then flatten and check the positions of 1's

here is the mathematica code

```
(F = Flatten)@
Position[F@Nest[#/.{1->{1,-1},-1->{-1,1}}&,1,10],1][[;; 400]] - 1

```

# Answer
> 4 votes
# Idea: A006068 (“a(n) is Gray-coded into n”)

Neil’s idea of sorting all the `2n XOR n` intrigued me, so I tried to find the indices behind this sort. I wrote this code, and it reveals that we can write something like this:

```
for n in range(400):x=a(n);print 2*x^x

```

Where `a(n)` is A006068(n). Try it online!

However, this assumes we have some short way to compute A006068. This is already 38 bytes, assuming we can calculate it in 4 bytes (the `a(n)` part). The real implementation (in the TIO header) is far longer than that. Not much hope for this I think.

---
Tags: code-golf, tips, binary, python
---


title: Prove DeMorgan's laws

text:
# Question
Title: Prove DeMorgan's laws
Using the the ten inferences of the Natural Deduction System prove DeMorgan's laws.

## The Rules of Natural Deduction

* Negation Introduction: `{(P → Q), (P → ¬Q)} ⊢ ¬P`
* Negation Elimination: `{(¬P → Q), (¬P → ¬Q)} ⊢ P`
* And Introduction: `{P, Q} ⊢ P ʌ Q`
* And Elimination: `P ʌ Q ⊢ {P, Q}`
* Or Introduction: `P ⊢ {(P ∨ Q),(Q ∨ P)}`
* Or Elimination: `{(P ∨ Q), (P → R), (Q → R)} ⊢ R`
* Iff Introduction: `{(P → Q), (Q → P)} ⊢ (P ≡ Q)`
* Iff Elimination: `(P ≡ Q) ⊢ {(P → Q), (Q → P)}`
* If Introduction: `(P ⊢ Q) ⊢ (P → Q)`
* If Elimination: `{(P → Q), P} ⊢ Q`

## Proof structure

Each statement in your proof must be the result of one of the ten rules applied to some previously derived propositions (no circular logic) or an assumption (described below). Each rule operates across some propositions on the left hand side of the  (logical consequence operator) and creates any number of propositions from the right hand side. The If Introduction works slightly differently from the rest of the operators (described in detail below). It operates across one statement that is the logical consequent of another.

### Example 1

You have the following statements:

`{(P → R), Q}`

You may use And Introduction to make:

`(P → R) ʌ Q`

### Example 2

You have the following statements:

`{(P → R), P}`

You may use If Elimination to make:

`R`

### Example 3

You have the following statements:

`(P ʌ Q)`

You may use And Elimination to make:

`P`

or to make:

`Q`

## Assumption Propagation

You may at any point assume any statement you wish. Any statement derived from these assumptions will be "reliant" on them. Statements will also be reliant on the assumptions their parent statements rely on. The only way to eliminate assumptions is by If Introduction. For If introduction you start with a Statement `Q` that is reliant on a statement `P` and end with `(P → Q)`. The new statement is reliant on every assumption `Q` relies on *except* for assumption `P`. Your final statement should rely on no assumptions.

## Specifics and scoring

You will construct one proof for each of DeMorgan's two laws using only the 10 inferences of the Natural Deduction Calculus.

The two rules are:

```
¬(P ∨ Q) ≡ ¬P ʌ ¬Q

¬(P ʌ Q) ≡ ¬P ∨ ¬Q

```

Your score is the number of inferences used plus the number of assumptions made. Your final statement should not rely on any assumptions (i.e. should be a theorem).

You are free to format your proof as you see fit.

You may carry over any Lemmas from one proof to another at no cost to score.

## Example Proof

I will prove that `(P and not(P)) implies Q`

(Each bullet point is +1 point)

* Assume `not (Q)`
* Assume `(P and not(P))`
* Using And Elim on `(P and not(P))` derive `{P, not(P)}`
* Use And Introduction on `P` and `not(Q)` to derive `(P and not(Q))`
* Use And Elim on the statement just derived to make `P`

The new `P` proposition is different from the other one we derive earlier. Namely it is reliant on the assumptions `not(Q)` and `(P and not(P))`. Whereas the original statement was reliant only on `(P and not(P))`. This allows us to do:

* If Introduction on `P` introducing `not(Q) implies P` (still reliant on the `(P and not(P))` assumption)
* Use And Introduction on `not(P)` and `not(Q)` (from step 3) to derive `(not(P) and not(Q))`
* Use And Elim on the statement just derived to make `not(P)` (now reliant on `not(Q)`)
* If Introduction on the new `not(P)` introducing `not(Q) implies not(P)`
* We will now use negation elimination on `not(Q) implies not(P)` and `not(Q) implies P` to derive `Q`

This `Q` is reliant only on the assumption `(P and not(P))` so we can finish the proof with

* If Introduction on `Q` to derive `(P and not(P)) implies Q`

This proof scores a total of 11.

# Answer
## Score: 81

Each line should be worth 1 point. The De Morgan's laws are found at statements (3) and (6). Labels in brackets denote the previous statement(s) a line depends on if they are not immediately preceding.

```
(a) assume P {
    (aa) P ^ P
    (ab) P
    (ac) P v Q
} (a1) P -> P
  (a2) P -> P v Q
(1) assume ~P ^ ~Q {
    (1a) assume P v Q {
        (1aa) assume Q {
            (1aaa) assume ~P {
                (1aaaa) Q ^ Q [1aa]
                (1aaab) Q
                (1aaac) ~Q [1]
            } (1aaa1) ~P -> Q
              (1aaa2) ~P -> ~Q
            (1aab) P
        } (1aa1) Q -> P
        P [1a, a1, 1aa1]
        ~P [1]
    } (1a1) P v Q -> P
      (1a2) P v Q -> ~P
    (1b) ~(P v Q)
} (11) ~P ^ ~Q -> ~(P v Q)
(2) assume ~(P v Q) {
    (2a) ~(P v Q) ^ ~(P v Q)
    (2b) assume P {
        (2aa) ~(P v Q) [2a]
    } (2b1) P -> ~(P v Q)
    (2c) ~P [a2, 2b1]
    (2d) assume Q {
        (2da) ~(P v Q) [2a]
        (2db) P v Q
    } (2d1) Q -> ~(P v Q)
      (2d2) Q -> P v Q
    (2e) ~Q
    (2f) ~P ^ ~Q
} (21) ~(P v Q) -> ~P ^ ~Q
(3) ~(P v Q) == ~P ^ ~Q [11, 21]
(4) assume ~P v ~Q {
    (4a) assume ~P {
        (4aa) assume P ^ Q {
            (4aaa) P
            (4aab) ~P ^ ~P [4a]
            (4aac) ~P
        } (4aa1) P ^ Q -> P
          (4aa2) P ^ Q -> ~P
        (4ab) ~(P ^ Q)
    } (4a1) ~P -> ~(P ^ Q)
    (4b) assume ~Q {
        (4ba) assume P ^ Q {
            (4baa) Q
            (4bab) ~Q ^ ~Q [4b]
            (4bac) ~Q
        } (4ba1) P ^ Q -> Q
          (4ba2) P ^ Q -> ~Q
        (4bb) ~(P ^ Q)
    } (4b1) ~P -> ~(P ^ Q)
    (4c) ~(P ^ Q) [4, 4a1, 4b1]
} (41) ~P v ~Q -> ~(P ^ Q)
(5) assume ~(P ^ Q) {
    (5a) assume ~(~P v ~Q) {
        (5aa) ~(~P v ~Q) ^ ~(P ^ Q) [5, 5a]
        (5ab) assume ~P {
            (5aba) ~P v ~Q
            (5abb) ~(~P v ~Q) [5aa]
        } (5ab1) ~P -> ~P v ~Q
          (5ab2) ~P -> ~(~P v ~Q)
        (5ac) P
        (5ad) assume ~Q {
            (5ada) ~P v ~Q
            (5adb) ~(~P v ~Q) [5aa]
        } (5ad1) ~Q -> ~P v ~Q
          (5ad2) ~Q -> ~(~P v ~Q)
        (5ae) Q
        (5af) P ^ Q [5ac, 5ae]
        (5ag) ~(P ^ Q) [5aa]
    } (5a1) ~(~P v ~Q) -> P ^ Q
      (5a2) ~(~P v ~Q) -> ~(P ^ Q)
    (5b) ~P v ~Q
} (51) ~(P ^ Q) -> ~P v ~Q
(6) ~(P ^ Q) == ~P v ~Q [41, 51]

```
> 6 votes

# Answer
# Score: 59

## Explanation

I'll use a tree like structure for the proof as I find this style quite readable. Each line is annotated by the count of used rules, for example the "Example 1" in the challenge would be represented as this tree (growing bottom to top):

Note the unknown counts A,B and also the assumption Γ - so this is no theorem. To demonstrate how to prove a theorem, let us assume **A** and use an Or-introduction as follows:

Now this is still depending on the assumption **A** but we can derive a theorem by applying an If-introduction:

So we were able to derive the theorem ⊢ **A** → (**A****B**) in a total of 3 steps (1 assumption & 2 applied rules).

With this we can go on to prove a few new rules that help us to prove DeMorgan's Laws.

## Additional Rules

Let's first derive the Principle of Explosion and denote it with **PE** in further proofs:

From this we derive another form of it: **A** ⊢ ¬**A****X** \- we'll call it **CPE**:

We'll need another one where the negated term (¬) is an assumption and refer to it as **CPE-**:

From the two rules we just derived (**CPE** and **CPE-**), we can derive an important rule Double Negation:

The next thing to do is to prove something like Modus Tollens \- hence **MT**:

# Lemmas

## Lemma A

### Lemma A1

We'll need the following rule two times:

### Lemma A

By instantiating the just proved lemma twice we can show one direction of an equivalence, we will need it in the final proof:

## Lemma B

In order to show another direction, we'll need to do two times some quite repetitive stuff (for both arguments **A** and **B** in (**A****B**)) - this means here I could possibly golf the proof further..

### Lemma B1'

### Lemma B1

### Lemma B2'

### Lemma B2

### Lemma B

Finally the conclusion of **B1** and **B2**:

## Actual proof

Once we proved these two statements:

* **Lemma A**: ⊢ (**A****B**) → ¬(¬**A** ʌ ¬**B**)
* **Lemma B**: ⊢ ¬(**A****B**) → (¬**A** ʌ ¬**B**)

We can prove the first equivalence (¬(**A****B**) ≡ ¬**A** ʌ ¬**B**)) as follows:

And with the just proved rule together with Iff-Elimination we can prove the second equivalence too:

Not sure about the score - if I did it right, let me know if there's something wrong.

## Explanation

## Source

If somebody wants the tex source (needs mathpartir):

```
In the following a rule \textbf{XYZ'} will denote the rule XYZ's second last
step, for example \textbf{PE'} will be $ A \land \lnot A \vdash X $.

\section*{Principle of Explosion [PE]}

\begin{mathpar}
  \inferrule*[Left=$\to$-Intro,Right=10]
    {\inferrule*[Left=$\lnot$-Elim,Right=9]
      {\inferrule*[Left=$\to$-Intro,Right=4]
        {\inferrule*[Left=$\land$-Elim,Right=3]
          {\inferrule*[Left=Axiom,Right=2]
            { }
            { A \land \lnot A, \lnot X \vdash A \land \lnot A }
          }
          { A \land \lnot A, \lnot X \vdash A }
        }
        { A \land \lnot A \vdash \lnot X \to A } \\
       \inferrule*[Right=$\to$-Intro,Left=4]
          {\inferrule*[Right=$\land$-Elim,Left=3]
            {\inferrule*[Right=Axiom,Left=2]
              { }
              { A \land \lnot A, \lnot X \vdash A \land \lnot A }
            }
            { A \land \lnot A, \lnot X \vdash \lnot A }
          }
        { A \land \lnot A \vdash \lnot X \to \lnot A }
      }
      { A \land \lnot A \vdash X }
    }
    { \vdash (A \land \lnot A) \to X }
\end{mathpar}

\section*{Conditioned PE [CPE]}

\begin{mathpar}
  \inferrule*[Left=$\to$-Intro,Right=5]
  {\inferrule*[Left=$\to$-Elim,Right=4]
    {\inferrule*[Left=$\land$-Intro,Right=3]
      {\inferrule*[Left=Axiom,Right=1]
        { } { A \vdash A } \\
       \inferrule*[Right=Axiom,Left=1]
        { } { \lnot A \vdash \lnot A }
      }
      { A, \lnot A \vdash A \land \lnot A } \\
     \inferrule*[Right=PE,Left=0]
      { } { \vdash (A \land \lnot A) \to X }
    }
    { A, \lnot A \vdash X }
  }
  { A \vdash \lnot A \to X }
\end{mathpar}

to get \textbf{CPE$^-$}:

\begin{mathpar}
  \inferrule*[Left=$\to$-Intro,Right=1]
    {\inferrule*[Left=CPE',Right=0]
      { }
      { A, \lnot A \vdash X }
    }
    { \lnot A \vdash A \to X }
\end{mathpar}

\section*{Double Negation [DN]}

\begin{mathpar}
  \inferrule*[Left=$\equiv$-Intro,Right=5]
    {\inferrule*[Left=$\to$-Intro,Right=2]
      {\inferrule*[Left=$\lnot$-Elim,Right=1]
        {\inferrule*[Left=CPE$^-$,Right=0]
          { }
          { \lnot\lnot A \vdash \lnot A \to X } \\
          \inferrule*[Right=CPE$^-$,Left=0]
          { }
          { \lnot\lnot A \vdash \lnot A \to \lnot X }
        }
        { \lnot\lnot A \vdash A }
      }
      { \vdash \lnot\lnot A \to A } \\ \\ \\
      \inferrule*[Left=$\to$-Intro,Right=2]
        {\inferrule*[Left=$\lnot$-Intro,Right=1]
          {\inferrule*[Left=CPE,Right=0]
            { }
            {  A \vdash \lnot A \to X } \\
            \inferrule*[Right=CPE,Left=0]
            { }
            { A \vdash \lnot A \to \lnot X }
          }
          { A \vdash \lnot\lnot A }
        }
        { \vdash A \to \lnot\lnot A }
    }
    { \vdash \lnot\lnot A \equiv A  }
\end{mathpar}

\section*{Modus Tollens [MT]}

\begin{mathpar}
  \inferrule*[Left=$\to$-Intro,Right=6]
    {\inferrule*[Left=$\lnot$-Intro,Right=5]
      {\inferrule*[Left=Axiom,Right=1]
       { }
       { A \to \lnot B \vdash A \to \lnot B } \\
       \inferrule*[Right=$\to$-Intro,Left=3]
         {\inferrule*[Right=Axiom,Left=2]
           { }
           { A, B \vdash B }
         }
         { B \vdash A \to B }
       }
      { A \to \lnot B, B \vdash \lnot A }
    }
    { A \to \lnot B \vdash B \to \lnot A }
\end{mathpar}

\section*{Lemma A}

\textbf{Lemma A1}:

\begin{mathpar}
  \inferrule*[Left=$\to$-Intro,Right=9]
    {\inferrule*[Left=$\lor$-Elim,Right=8]
       { \inferrule*[Left=CPE,Right=3]
          {\inferrule*[Left=$\land$-Elim,Right=2]
            {\inferrule*[Left=Axiom,Right=1]
              { }
              { A \land B \vdash A \land B }
            }
            { A \land B \vdash B}
          }
          { A \land B \vdash \lnot B \to X } \\
         \inferrule*[Right=CPE,Left=3]
          {\inferrule*[Right=$\land$-Elim,Left=2]
            {\inferrule*[Right=Axiom,Left=1]
              { }
              { A \land B \vdash A \land B }
            }
            { A \land B \vdash A }
          }
          { A \land B \vdash \lnot A \to X } \\ \\ \\
         \inferrule*[Right=Axiom,Left=1]
          { }
          { \lnot A \lor \lnot B \vdash \lnot A \lor \lnot B }
       }
       { A \land B, \lnot A \lor \lnot B \vdash X }
    }
    { \lnot A \lor \lnot B \vdash (A \land B) \to X }
\end{mathpar}

\textbf{Lemma A}:

```
> 4 votes

# Answer
# Score: 65

The de Morgan laws are line 30 and line 65.

(I haven't made any particular effort to golf this, for example to see if there are some repeated proofs that could be abstracted out at the beginning.)

```
 1. assume ~(P\/Q)
 2.   assume P
 3.     P\/Q  by or-introl, 2
 4.   P -> P\/Q  by impl-intro, 2, 3
 5.   P -> ~(P\/Q)  by impl-intro, 2, 1
 6.   ~P  by neg-intro, 4, 5
 7.   assume Q
 8.     P\/Q  by or-intror, 7
 9.   Q -> P\/Q  by impl-intro, 7, 8
10.   Q -> ~(P\/Q) by impl-intro, 7, 1
11.   ~Q  by neg-intro, 9, 10
12.   ~P /\ ~Q  by and-intro, 6, 11
13. ~(P\/Q) -> ~P/\~Q  by impl-intro, 1, 12
14. assume ~P /\ ~Q
15.   ~P, ~Q  by and-elim, 14
16.   assume P \/ Q
17.     assume P
18.     P -> P  by impl-intro, 17, 17
19.     assume Q
20.       assume ~P
21.       ~P -> Q  by impl-intro, 20, 19
22.       ~P -> ~Q  by impl-intro, 20, 15
23.       P  by neg-elim, 21, 22
24.     Q -> P  by impl-intro, 19, 23
25.     P  by or-elim, 16, 18, 24
26.   P\/Q -> P  by impl-elim, 16, 25
27.   P\/Q -> ~P  by impl-elim, 16, 15
28.   ~(P\/Q)  by neg-intro, 26, 27
29. ~P/\~Q -> ~(P\/Q)  by impl-intro, 14, 28
30. ~(P\/Q) <-> ~P/\~Q  by iff-intro, 13, 29
31. assume ~(P/\Q)
32.   assume ~(~P\/~Q)
33.     assume ~P
34.       ~P\/~Q  by or-introl, 33
35.     ~P -> ~P\/~Q  by impl-intro, 33, 34
36.     ~P -> ~(~P\/~Q)  by impl-intro, 33, 32
37.     P  by neg-elim, 35, 36
38.     assume ~Q
39.       ~P\/~Q  by or-intror, 38
40.     ~Q -> ~P\/~Q  by impl-intro, 38, 39
41.     ~Q -> ~(~P\/~Q)  by impl-intro, 38, 32
42.     Q  by neg-elim, 40, 41
43.     P /\ Q  by and-intro, 37, 42
44.   ~(~P\/~Q) -> P /\ Q  by impl-intro, 32, 43
45.   ~(~P\/~Q) -> ~(P /\ Q)  by impl-intro, 32, 31
46.   ~P \/ ~Q  by neg-elim, 44, 45
47. ~(P/\Q) -> ~P\/~Q  by impl-intro, 31, 46
48. assume ~P\/~Q
49.   assume ~P
50.     assume P/\Q
51.       P, Q  by and-elim, 50
52.     P/\Q -> P  by impl-intro, 50, 51
53.     P/\Q -> ~P  by impl-intro, 50, 49
54.     ~(P/\Q)  by neg-intro, 52, 53
55.   ~P -> ~(P/\Q)  by impl-intro, 49, 54
56.   assume ~Q
57.     assume P/\Q
58.       P, Q  by and-elim, 57
59.     P/\Q -> Q  by impl-intro, 57, 58
60.     P/\Q -> ~Q  by impl-intro, 57, 56
61.     ~(P/\Q)  by neg-intro, 59, 60
62.   ~Q -> ~(P/\Q)  by impl-intro, 56, 61
63.   ~(P/\Q)  by or-elim, 48, 55, 62
64. ~P\/~Q -> ~(P/\Q)  by impl-intro, 48, 63
65. ~(P/\Q) <-> ~P\/~Q  by iff-intro, 47, 64

```
> 1 votes

---
Tags: atomic-code-golf, logic, proof-golf
---


title: BIU numbers (or Sumdivized numbers)

text:
# Question
Title: BIU numbers (or Sumdivized numbers)
# How to spot them

Take a positive integer k. Find its **divisors**. Find the **distinct prime factors of each divisor**. Sum all these factors together. If this number (sum) is a divisor of k (**if the sum divides k**) then, this number k, is a **BIU number**

# Examples

Let's take the number `54`
Find all the **divisors:** `[1, 2, 3, 6, 9, 18, 27, 54]`
Find the **distinct prime factors** of each divisor
**NOTE:** For the case of `1` we take as distinct prime factor `1`

```
1  -> 1
2  -> 2
3  -> 3
6  -> 2,3
9  -> 3
18 -> 2,3
27 -> 3
54 -> 2,3

```

Now we take the sum of **all** these prime factors
`1+2+3+2+3+3+2+3+3+2+3=27`
`27` divides 54 (leaves no remainder)
So, `54` **is** a **BIU number**.

Another (quick) example for `k=55`
**Divisors:** `[1,5,11,55]`
**Sum of distinct prime factors:** `1+5+11+5+11=33`
`33` is **NOT** a divisor of 55, that's why `55` is **NOT** a **BIU number**.

# BIU numbers

Here are the first 20 of them:

> 1,21,54,290,735,1428,1485,1652,2262,2376,2580,2838,2862,3003,3875,4221,4745, 5525,6750,7050...

but this list goes on and there are many **BIU numbers** that are waiting to be descovered by you!

# The Challenge

Given an integer `n>0` as **input**, **output** the **nth BIU number**

# Test Cases

***Input-\>Output***

```
1->1
2->21
42->23595
100->118300
200->415777
300->800175

```

This is .Shortest answer in bytes wins!

# Answer
# Jelly, ~~16~~ 15 bytes

```
ÆDÆfQ€SS‘ḍ
1Ç#Ṫ

```

Try it online!

Woohoo for builtins (but they mysteriously hide from me sometimes so *-1 byte thanks to @HyperNeutrino*)

**How it Works**

```
ÆDÆfQ€SS‘ḍ - define helper function: is input a BIU number?
ÆD             - divisors
  Æf           - list of prime factors
    Q€         - now distinct prime factors
      SS       - sum, then sum again ('' counts as 0)
        ‘      - add one (to account for '')
         ḍ     - does this divide the input?

1Ç#Ṫ - main link, input n
  #     - starting at
1          - 1
        - get the first n integers which meet:
 Ç         - helper link
   Ṫ    - tail

```
> 6 votes

# Answer
# 05AB1E, 9 bytes

```
µNNÑfOO>Ö

```

Uses teh **05AB1E** encoding. Try it online!
> 5 votes

# Answer
# Husk, 13 bytes

```
!fṠ¦ö→ΣṁoupḊN

```

Try it online!

### Explantaion

```
  Ṡ¦ö→ΣṁoupḊ    Predicate: returns 1 if BIU, else 0.
           Ḋ    List of divisors
       ṁ        Map and then concatenate
        oup     unique prime factors
      Σ         Sum
    ö→          Add one
  Ṡ¦            Is the argument divisible by this result
 f          N   Filter the natural numbers by that predicate
!               Index

```
> 4 votes

# Answer
# Mathematica, 85 bytes

```
If[#<2,1,n=#0[#-1];While[Count[(d=Divisors)@++n,1+Tr@Cases[d/@d@n,_?PrimeQ,2]]<1];n]&

```
> 3 votes

# Answer
# Actually, 16 bytes

```
u⌠;÷♂y♂iΣu@%Y⌡╓N

```

Try it online!

Explanation:

```
u⌠;÷♂y♂iΣu@%Y⌡╓N
u⌠;÷♂y♂iΣu@%Y⌡╓   first n+1 numbers x starting with x=0 where
   ÷                divisors
    ♂y              prime factors of divisors
      ♂iΣu          sum of prime factors of divisors, plus 1
  ;       @%        x mod sum
            Y       is 0
               N  last number in list

```
> 2 votes

# Answer
# Pyth, 22 bytes

```
e.f|qZ1!%Zhssm{Pd*M{yP

```

Try it here!

This is my first ever Pyth solution, I began learning it thanks to the recommendations of some very kind users in chat :-)... Took me about an hour to solve.

## Explanation

```
e.f|qZ1!%Zhssm{Pd*M{yP  - Whole program. Q = input.

 .f                     - First Q integers with truthy results, using a variable Z.
     qZ1                - Is Z equal to 1?
   |                    - Logical OR.
                   {yP  - Prime factors, powerset, deduplicate.
                 *M     - Get the product of each. This chunck and ^ are for divisors.
              m}Pd      - Get the unique prime factors of each.
           ss           - Flatten and sum.
          h             - Increment (to handle that 1, bah)
       %Z               - Modulo the current integer by the sum above.
      !                 - Logical negation. 0 -> True, > 0 -> False.
e                       - Last element.

```
> 2 votes

# Answer
# Haskell, 115 bytes

All of the list comprehensions here can probably be golfed down, but I'm not sure how. Golfing suggestions welcome! Try it online!

```
x!y=rem x y<1
b n=[a|a<-[1..],a!(1+sum[sum[z|z<-[2..m],m!z,and[not$z!x|x<-[2..z-1]]]|m<-[x|x<-[2..a],a!x]])]!!(n-1)

```

**Ungolfing**

This answer is actually three functions mashed together.

```
divisors a = [x | x <- [2..a], rem a x == 0]
sumPrimeDivs m = sum [z | z <- [2..m], rem m z == 0, and [rem z x /= 0 | x <- [2..z-1]]]
biu n = [a | a <- [1..], rem a (1 + sum [sumPrimeDivs m | m <- divisors a]) == 0] !! (n-1)

```
> 1 votes

# Answer
# Japt, ~~22~~ ~~21~~ 17 bytes

~~I feel like the `g` function method should lead to a shorter solution, but I can't figure out how it works!~~ Nope! Wrong method! But, in my defense, the `i` method didn't exist at the time.

1-indexed.

```
ÈvXâ mk câ x Ä}iU

```

Try it

```
ÈvXâ mk câ x Ä}iU     :Implicit input of integer U
È                     :Function taking an integer X as argument
 v                    :  Test X for divisibility by
  Xâ                  :    Divisors of X
     m                :    Map
      k               :      Prime factors
        c             :    Flatten after
         â            :      Deduplicating
           x          :    Reduce by addition
             Ä        :    Add 1
              }       :End function
               iU     :Get the Uth integer that returns true

```
> 0 votes

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


title: Generate Numpad-Friendly Numbers

text:
# Question
Title: Generate Numpad-Friendly Numbers
*Inspired by Generate Keyboard Friendly Numbers.*

## Background

Many number pads have the following layout:

`7``8``9`

`4``5``6`

`1``2``3`

`0`

We define a number's neighborhood as the set of cells orthogonally adjacent to it on the numpad shown, including itself. For example, 2's neighborhood is `{1,5,3,0,2}` and 0's neighborhood is `{1,2,0}`. There is a list of each number's neighborhood below, above test cases.

We define a ***numpad friendly number*** as a positive integer where, when written in decimal without leading zeroes, each digit except for the first is in the neighborhood of the previous digit.

For example,

* 7856 is a numpad friendly number because 8 is in the neighborhood of 7, 5 is in the neighborhoood of 8, and 6 is in the neighborhood of 5.
* 1201 is a numpad friendly number because 2 is in the neighborhood of 1, 0 is in the neighborhood of 2, and 1 is in the neighborhood of 0.
* 82 is **not** a numpad friendly number because 2 is not in the neighborhood of 8.
* 802 is **not** a numpad friendly number because 0 is not in the neighborhood of 8 (neighborhoods don't wrap around).

Related OEIS Sequence. Note that this related sequence is distinct because it counts `0` as adjacent to `7` instead of `1` and `2`.

# Challenge

Given a positive integer `n`, return the `n`-th or the first `n` numpad friendly numbers, where the first is 1. You may use 0-based indexing, where the 0-th numpad friendly number would be 1.

# Neighborhoods

Each digits's neighborhood is listed here:

```
0:{0,1,2}
1:{0,1,2,4}
2:{0,1,2,3,5}
3:{2,3,6}
4:{1,4,5,7}
5:{2,4,5,6,8}
6:{3,5,6,9}
7:{4,7,8}
8:{5,7,8,9}
9:{6,8,9}

```

# Test Cases / Sequence

These are the first 100 terms

```
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 20, 21, 22, 23, 25, 32, 33, 36, 41, 44, 45, 47, 52, 54, 55, 56, 58, 63, 65, 66, 69, 74, 77, 78, 85, 87, 88, 89, 96, 98, 99, 100, 101, 102, 110, 111, 112, 114, 120, 121, 122, 123, 125, 141, 144, 145, 147, 200, 201, 202, 210, 211, 212, 214, 220, 221, 222, 223, 225, 232, 233, 236, 252, 254, 255, 256, 258, 320, 321, 322, 323, 325, 332, 333, 336, 363, 365, 366, 369, 410, 411, 412, 414, 441, 444, 445, 447]

```

# Answer
# JavaScript (ES6), ~~104~~ ~~93~~ ~~89~~ 88 bytes

Returns the N-th term of the sequence, 1-indexed.

```
f=(i,k,n=k,N=n/5>>1)=>(N?8530025>>(n%10*6191^N%10*6191)%26&1:!i--)?N?f(i,k,N):k:f(i,-~k)

```

### Demo

```
f=(i,k,n=k,N=n/5>>1)=>(N?8530025>>(n%10*6191^N%10*6191)%26&1:!i--)?N?f(i,k,N):k:f(i,-~k)

for(n = 1; n <= 50; n++) {
  console.log('a(' + n + ') = ' + f(n))
}
```
> 9 votes

# Answer
# Perl 5, 123 + 1 (-p) = 124 bytes

```
while($_){$r=@d=++$\=~/./g;map$r&&=(120,1240,12350,236,1457,24568,3569,478,5789,689)[$d[$_-1]]=~/$d[$_]/,1..$#d;$r&&$_--}}{

```

Try it online!
> 4 votes

# Answer
# Jelly, ~~27~~ 24 bytes

Returns the N first terms of the sequence.

```
D⁽ÞȦ×^2\%26“⁷wð’æ»ḂẠ
1Ç#

```

Try it online!

This is a port of my JS answer.

```
D⁽ÞȦ×^2\%26“⁷wð’æ»ḂẠ    - helper link: test numpad-friendliness of a number, e.g. 1257
D                       - get decimal digits             -> [1, 2, 5, 7]
    ×                   - multiply by ...
 ⁽ÞȦ                    - ... the integer 6191           -> [6191, 12382, 30955, 43337]
     ^2\                - bitwise XOR overlapping reduce -> [10353, 18613, 53666]
        %26             - modulo 26                      -> [5, 23, 2]
                æ»      - right-shift by each value ...
           “⁷wð’        - ... the integer 8530025        -> [266563, 1, 2132506]
                  Ḃ     - isolate the LSB                -> [1, 1, 0] which means that 1->2
                                                            and 2->5 are OK and 5->7 is not
                   Ạ    - all (0 if there's any 0)       -> 0, i.e. not numpad-friendly :'(

1Ç#                     - main link: return the [input] first matching numbers,
                          using our helper link as a monad and starting with 1

```
> 3 votes

# Answer
# 05AB1E, ~~24~~ 23 bytes

```
µNSü‚εW_iO<ë<3BÆ}ÄR2‹}P

```

Try it online!

Returns the nth number in the sequence.

**Explanations:**

```
µNSü‚εW_iO<ë<3BÆ}ÄR2‹}P    Full program
µ                          Until counter is equal to input
 N                         Push current iteration number (e.g. 1025)
  S                        Split to a list of chars (-> ['1', '0', '2', '5'])
   ü‚                      Group into pairs (-> ['1', '0'], ['0', '2'], ['2', '5'])
     ε                     For each pair
      W_                      Is smallest digit equal to 0?
        iO<                      True: sum all digits and decrement
           ë                     False:
            <                       - decrement all digits
             3B                     - convert to base 3
               Æ                    - reduced substraction
                }             End if
                 Ä            Absolute value
                  R           Reverse
                   2‹         1 if result is < 2, 0 otherwise
                     }     End for each
                      P    Cumulative product (1 if all pair results are
                                     1, 0 otherwise)
                           -- implicit counter increment if stack value is 1

```

The main idea is that, apart from the `0` key, any digit decremented and converted to base 3 has the following properties:

* left and right neighbours have an absolute difference of 1
* up and down neighbours have an absolute difference of 10 which, reversed, is conveniently equal to 1
* any other pair of numpad keys result in different values, even when reversed

Of course we need a `if` statement to handle the `0` numpad key.
> 3 votes

# Answer
# Jelly, 26 bytes

```
’d-,.⁸?3µ€ạ/S
Dṡ2Ç€<2Ạ
1Ç#

```

Try it online!

-2 bytes thanks to caird coinheringaahing
-2 bytes thanks to Erik the Outgolfer

# Explanation

```
’d-,.⁸?3µ€ạ/S  Helper Link; compute the distance between two keys z = [x, y]
      ?        Switch:
     ⁸         If z (is not 0):
’              Decrement
 d             Divmod by:
  -,.          Else: [-1, 0.5] (special position for 0)
       3       3; right argument for divmod otherwise ignored
        µ      Begin a new monadic link / end this link
         €     Compute the position for each [x, y]
           /   Reduce on
          ạ    Absolute Difference
            S  Sum (this gives the Manhattan Distance)
Dṡ2Ç€<2Ạ       Helper Link; determine if a number <z> is numpad friendly
D              Convert number to decimal digits
 ṡ             Slice into overlapping slices of length
  2            2 (pairs)
    €          For each pair,
   Ç           The distance between the keys
     <2        Compare with 2 (the distance between two adjacent keys is 1; corners 2; 0 - 1 and 0 - 2 are 1.5)
       Ạ       All; either all of the distances are less than 2 or there were no distances
1Ç#            Main Link; find the first (input) numpad friendly numbers
  #            nfind; counting up from _ collect the first _______ matches that are
1                                      1
                                                           (input)
 Ç             Numpad Friendly

```
> 2 votes

# Answer
# MATL, ~~29~~ 27 bytes

```
`@J3:qEt!J*+hYAd|2>~A?@]NG-

```

Outputs the first `n` numpad-friendly numbers.

**Try it online!**

### Explanation

Each digit from `1` to `9` is encoded as a complex number representing its position in the numpad, using in a step-2 grid, where real part represents vertical position and imaginary part represents horizontal position. So `1` is `0+0j`, `2` is `0+2j`, `3` is `0+4j`, `4` is `2+0j`, ..., `9` is `4+4j`.

Digit `0` is encoded as `0+1j`, i.e. as if it were placed exactly between `1` and `2`.

For each candidate numpad-friendly number, a "decimal" base conversion is applied using the above complex numbers instead of the digits `0`, `1`, ..., `9`. This gives an array, of which the absolute consecutive differences are computed. The candidate number is numpad-friendly if and only if all absolute differences are at most `2` (i.e. the grid step). If that's the case, the number is left on the stack.

The code uses a `do`...`while` loop, which is exited when the amount of numbers in the stack equals the input `n`.

A unit grid would have been a more natural choice. Digits `1`, `2` and `0` would then correspond to `0+0j`, `1+0j` and `0.5+0j` respecrively. But it's golfier to use a step-2 grid, because multiplying by `2` (function `E`) and pushing `0+1j` (function `J`) is one byte shorter than pushing `0+0.5j` (`J2/` or `.5j`)
> 2 votes

# Answer
# Python 2, 134 bytes

```
g=lambda n,k=1:n and g(n-(lambda l:all(abs(a-b)<1.2for a,b in zip(l,l[1:])))([~-d%3+~-d/3*1j-d/~d*1.5for d in map(int,`k`)]),k+1)or~-k

```

Try it online!
> 2 votes

# Answer
# Mathematica, ~~249~~ ~~234~~ 202 bytes

```
(a=o=1;While[a<=#,s=IntegerDigits@o;t=1;p=0;While[t+p<Length@s,If[!FreeQ[(IntegerDigits/@{210,4210,53210,632,7541,86542,9653,874,9875,986})[[s[[t]]+1]],s[[t+1]]],t++,p++]];If[t==Length@s,a++];o++];o-1)&

```

Try it online!

*thanks user202729 for compressing data (-32 bytes)*

My results:

> 100 -\>447
> 1000 -\>20023
> 10000 -\>788777
> 1 votes

# Answer
# PHP, 124+1 bytes

```
while($argn-=$r)for($p=$r=~0,$x=++$n;$x>=1;$p=[7,23,47,76,178,372,616,400,928,832][$c],$x/=10)$r&=!!($p&1<<$c=$x%10);echo$n;

```

Run as pipe with `-nR` or try it online.
> 1 votes

# Answer
# Java 8, ~~192~~ 190 bytes

```
n->{int r=1,p;a:for(;n>0;){p=-1;for(int c:(r+++"").getBytes())if(p>-1&!"012;0124;01235;236;1457;24568;3568;478;5789;689".split(";")[c-=48].contains(p+""))continue a;else p=c;n--;}return~-r;}

```

Returns the (1-indexed) `n`'th number in the sequence.

This was surprisingly harder than I thought.. Probably just having some brain-farts this afternoon..

**Explanation:**

Try it here.

```
n->{                 // Method with integer as both parameter and return-type
  int r=1,           //  Return-integer
      p;             //  Previous digit
  a:for(;n>0;){      //  Loop (1) as long as the input is larger than 0
    p=-1;            //   Start `p` at an integer that is not 0-9 (-1 in this case)
    for(int c:(r+++"").getBytes())
                     //   Loop (2) over the digits of the current number
      if(p>=0        //    If this is not the first digit (`p` != -1),
         &!"012;0124;01235;236;1457;24568;3568;478;5789;689".split(";")[c-=48]
           .contains(p+""))
                     //    and the adjacent digits are NOT part of a NumberPad-Friendly Nr:
        continue a;  //     Go to the next iteration of loop (1)
      else           //    Else:
        p=c;         //     Set `p` to the current digit for the next iteration
                     //   End of loop (2) (implicit / single-line body)
      n--;           //   If we haven't encountered the `continue`, decrease `n` by 1
  }                  //  End of loop (1)
  return~-r;         //  Return the result-integer - 1
}                    // End of method

```
> 0 votes

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


title: Longest hypercube path

text:
# Question
Title: Longest hypercube path
# Challenge

You are given two distinct bit strings of the same length. (For example, `000` and `111`.) Your goal is to find a path from one to the other such that:

* At each step, you change only one bit (you can go from `000` to any of `001`, `010`, `100`).
* You cannot visit the same bit string twice.
* The path is as long as possible, under these constraints.

For example, going from `000` to `111`, we can take the path

```
000, 001, 011, 010, 110, 100, 101, 111

```

which visits all 8 bit strings of length 3, so it has to be the longest possible.

# Rules

* Standard loopholes apply.
* You may take the input as two strings of zeroes and ones, or as two arrays of zeroes and ones, or as two arrays of boolean values.
* You may **not** take the input as two integers with the right binary representation (writing `000` and `111` as `0` and `7` is not valid).
* If you want, you may take the length of the bit strings as input.
* Your program is allowed to output the path by printing the bit strings visited one at a time, or by returning an array of the bit strings visited (each in the same format as the input).
* Your output should include the start and end of the path (which are your inputs).
* This is , the shortest code in bytes wins.

# Examples

```
0 1 -> 0, 1
10 01 -> 10, 00, 01 or 10, 11, 01
000 111 -> any of the following:

   000, 100, 110, 010, 011, 001, 101, 111

   000, 100, 101, 001, 011, 010, 110, 111

   000, 010, 110, 100, 101, 001, 011, 111

   000, 010, 011, 001, 101, 100, 110, 111

   000, 001, 101, 100, 110, 010, 011, 111

   000, 001, 011, 010, 110, 100, 101, 111

1001 1100 -> 1001, 0001, 0000, 0010, 0011, 0111, 0101, 0100, 0110, 1110, 1010, 1011, 1111, 1101, 1100 (other paths exist)

```

# Answer
> 6 votes
# Husk, ~~27 26~~ 24 bytes

```
→foΛεẊδṁ≠ÖLm↓≠⁰←ġ→PΠmṠe¬

```

Brute force, so very slow. Try it online!

## Explanation

Husk reads naturally from right to left.

```
←ġ→PΠmṠe¬  Hypercube sequences ending in second input, say y=[1,1,0]
     mṠe¬  Pair each element with its negation: [[0,1],[0,1],[1,0]]
    Π      Cartesian product: [[0,0,1],[1,0,1],..,[1,1,0]]
   P       Permutations.
 ġ→        Group by last element
←          and take first group.
           The permutations are ordered so that those with last element y come first,
           so they are grouped together and returned here.

ÖLm↓≠⁰  Find first input.
  m     For each permutation,
   ↓≠⁰  drop all elements before the first input.
ÖL      Sort by length.

foΛεẊδṁ≠  Check path condition.
fo        Keep those lists that satisfy:
    Ẋ      For each adjacent pair (e.g. [0,1,0] and [1,1,0]),
      ṁ    take sum of
       ≠   absolute differences
     δ     of corresponding elements: 1+0+0 gives 1.
  Λε       Each value is at most 1.

→  Finally, return last element (which has greatest length).

```

# Answer
> 4 votes
# Mathematica, 108 bytes

```
a=#~FromDigits~2+1&;Last@PadLeft[IntegerDigits[#-1,2]&/@FindPath[HypercubeGraph@Length@#,a@#,a@#2,∞,All]]&

```

Input:

```
[{0, 0, 0, 0}, {1, 1, 1, 1}]

```

Output:

```
{{0, 0, 0, 0}, {0, 0, 0, 1}, {0, 0, 1, 1}, {0, 0, 1, 0}, {0, 1, 1, 0},
 {0, 1, 0, 0}, {0, 1, 0, 1}, {1, 1, 0, 1}, {1, 0, 0, 1}, {1, 0, 0, 0},
 {1, 1, 0, 0}, {1, 1, 1, 0}, {1, 0, 1, 0}, {1, 0, 1, 1}, {1, 1, 1, 1}}

```

# Answer
> 3 votes
# Mathematica, 175 bytes

Nice first question!

```
(m=#;n=#2;Last@SortBy[(S=Select)[S[Rest@Flatten[Permutations/@Subsets[Tuples[{0,1},(L=Length)@m]],1],First@#==m&&Last@#==n&],Union[EditDistance@@@Partition[#,2,1]]=={1}&],L])&

```

**Input**

> \[{0, 0, 0}, {1, 1, 1}\]

# Answer
> 3 votes
# Haskell, ~~212~~ 207 bytes

This is probably way too long, but it finally works now. (Thanks to @Lynn for the cartesian product trick!) Thansk @nimi for -5 bytes!

```
import Data.List
b%l=[l++[x|b/=last l,x`notElem`l,1==sum[1|(u,v)<-x`zip`last l,u/=v]]|x<-mapM id$[0>1..]<$b]
b!a|f<-nub.concat.((b%)<$>)=snd$maximum$map(length>>=(,))$filter((==b).last)$until(f>>=(==))f[[a]]

```

Try it online!

Explanation:

```
b%l -- helper function:
    -- given a path l (that should end in b) this generates all possible extensions
    -- of l (if not possible also l itself)
            x<-mapM id$[0>1..]<$b -- generate all possible vertices of the hypercube
             -- and check the criteria
           b/=last l,x`notElem`l,1==sum[1|(u,v)<-x`zip`last l,u/=v]
             -- extend if possible
    [l++[x|  ...                                                   ]| ... ]
b!a| -- actual function:
     -- first define a helper function:
    f<-nub.concat.((b%)<$>)
     -- begin with the vertex a and apply the function from above repeatedly
     -- until you cannot make the path any longer without violating the
     -- criteria
                                                                             until(f>>=(==))f[[a]]
     -- only take the paths that actually end in b
                                                          filter((==b).last)$
     -- and find the one with the maximum length
                           =snd$maximum$map(length>>=(,))$

```

# Answer
> 3 votes
# Haskell, ~~141~~ 123 bytes

```
c(a:b)=(1-a:b):map(a:)(c b)
c _=[]
q#z=[z]:[z:s|w<-c z,notElem w q,s<-(w:q)#w]
x!y=snd$maximum[(p*>x,p)|p<-[x]#x,last p==y]

```

Uses lists of integers. Try it online!

## Explanation

The main function is `!`, and the auxiliary functions are `#` and `c`. Given a list of bits, `c` gives all possible ways of flipping one of them, e.g. `[0,1,1] -> [[1,1,1],[0,0,1],[0,1,0]]`.

```
c(a:b)=        -- c on nonempty list with head a and tail b is
 (1-a:b):      -- the list with negated a tacked to b, then
 map(a:)(c b)  -- c applied recursively to b, with a tacked to each of the results.
c _=[]         -- c on empty list gives an empty list.

```

The function `#` takes a list of lists (the "memory") and a list (the "initial bitstring"). It constructs all hypercube paths that begin with the initial element, contain only distinct bitstrings, and do not step on the strings in the memory.

```
q#z=            -- # on memory q and initial string z is
 [z]:           -- the singleton path [z], and
 [z:s|          -- z tacked to each path s, where
  w<-c z,       -- w is obtained by flipping a bit of z,
  notElem w q,  -- w is not in the memory, and
  s<-(w:q)#w]   -- s is a path starting from w that avoids w and all elements of q.

```

The main function `!` ties it all together. A trick I use here is `p*>x` (`x` repeated `length p` times) instead of `length p`. Since longer repetitions of `x` come later in the natural ordering of lists, `maximum` chooses the longest path in either case, since the first coordinates of pairs are compared before the second ones.

```
x!y=          -- ! on inputs x and y is
 snd$maximum  -- the second element of the maximal pair in
 [(p*>x,p)|   -- the list of pairs (p*>x,p), where
  p<-[x]#x,   -- p is a path starting from x that avoids stepping on x, and
  last p==y]  -- p ends in y.

```

# Answer
> 3 votes
# Mathematica ~~116~~ 114 bytes

With several bytes saved thanks to Misha Lavrov.

```
Last@FindPath[Graph[Rule@@@Cases[Tuples[Tuples[{0,1},{l=Length@#}],{2}],x_/;Count[Plus@@x,1]==1]],##,{1,2^l},Alll]&

```

Input (8 dimensions)

```
[{1,0,0,1,0,0,0,1},{1,1,0,0,0,0,1,1}]//AbsoluteTiming

```

Output (length = 254, after 1.82 seconds)

```
{1.82393, {{1, 0, 0, 1, 0, 0, 0, 1}, {0, 0, 0, 1, 0, 0, 0, 1}, {0, 0, 0, 0, 0, 0, 0, 1}, {0, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 1, 0}, {0, 0,0, 0, 0, 0, 1, 1}, {0, 0, 0, 0, 0, 1, 1, 1}, {0, 0, 0, 0, 0, 1, 0, 1}, {0, 0, 0, 0, 0, 1, 0, 0}, {0, 0, 0, 0, 0, 1, 1, 0}, {0, 0, 0, 0,1, 1, 1,0}, {0, 0, 0, 0, 1, 0, 1, 0}, {0, 0, 0, 0, 1, 0, 0, 0}, {0, 0, 0, 0, 1, 0, 0, 1}, {0, 0, 0, 0, 1, 0, 1, 1}, {0, 0, 0, 0,1, 1, 1, 1}, {0, 0, 0, 0, 1, 1, 0, 1}, {0, 0, 0, 0, 1, 1, 0, 0}, {0, 0, 0, 1, 1, 1, 0, 0}, {0, 0, 0, 1, 0, 1, 0, 0}, {0, 0, 0, 1,0, 0, 0, 0}, {0, 0, 0, 1, 0, 0, 1, 0}, {0, 0, 0, 1, 0, 0, 1, 1}, {0, 0, 0, 1, 0, 1, 1, 1}, {0, 0, 0, 1, 0, 1, 0, 1}, {0, 0, 0, 1, 1, 1, 0, 1}, {0, 0, 0, 1, 1, 0, 0, 1}, {0, 0, 0, 1, 1, 0, 0, 0}, {0, 0, 0, 1, 1, 0, 1, 0}, {0, 0, 0, 1, 1, 0, 1, 1}, {0, 0, 0, 1,1, 1, 1, 1}, {0, 0, 0, 1, 1, 1, 1, 0}, {0, 0, 0, 1, 0, 1, 1, 0}, {0, 0, 1, 1, 0, 1, 1, 0}, {0, 0, 1, 0, 0, 1, 1, 0}, {0, 0, 1, 0,0, 0, 1, 0}, {0, 0, 1, 0, 0, 0, 0, 0}, {0, 0, 1, 0, 0, 0, 0, 1}, {0, 0, 1, 0, 0, 0, 1, 1}, {0, 0, 1, 0, 0, 1, 1, 1}, {0, 0, 1, 0,0, 1, 0, 1}, {0, 0, 1, 0, 0, 1, 0, 0}, {0, 0, 1, 0, 1, 1, 0, 0}, {0, 0, 1, 0, 1, 0, 0, 0}, {0, 0, 1, 0, 1, 0, 0, 1}, {0, 0, 1, 0,1, 0, 1, 1}, {0, 0, 1, 0, 1, 0, 1, 0}, {0, 0, 1, 0, 1, 1, 1, 0}, {0, 0, 1, 0, 1, 1, 1, 1}, {0, 0, 1, 0, 1, 1, 0, 1}, {0, 0, 1, 1,1, 1, 0, 1}, {0, 0, 1, 1, 0, 1, 0, 1}, {0, 0, 1, 1, 0, 0, 0, 1}, {0, 0, 1, 1, 0, 0, 0, 0}, {0, 0, 1, 1, 0, 0, 1, 0}, {0, 0, 1, 1,0, 0, 1, 1}, {0, 0, 1, 1, 0, 1, 1,1}, {0, 0, 1, 1, 1, 1, 1, 1}, {0, 0, 1, 1, 1, 0, 1, 1}, {0, 0, 1, 1, 1, 0, 0, 1}, {0, 0, 1, 1,1, 0, 0, 0}, {0, 0, 1, 1, 1, 0, 1, 0}, {0, 0, 1, 1, 1, 1, 1, 0}, {0, 0, 1, 1, 1, 1, 0, 0}, {0, 0, 1, 1, 0, 1, 0, 0}, {0, 1, 1, 1,0, 1, 0, 0}, {0, 1, 0, 1, 0, 1, 0, 0}, {0, 1, 0, 0, 0, 1, 0, 0}, {0, 1, 0, 0, 0, 0, 0, 0}, {0, 1, 0, 0, 0, 0, 0, 1}, {0, 1, 0, 0,0, 0, 1, 1}, {0, 1, 0, 0, 0, 0, 1, 0}, {0, 1, 0, 0, 0, 1, 1, 0}, {0, 1, 0, 0, 0, 1, 1, 1}, {0, 1, 0, 0, 0, 1, 0, 1}, {0, 1, 0, 0,1, 1, 0, 1}, {0, 1, 0, 0, 1, 0, 0, 1}, {0, 1, 0, 0, 1, 0, 0, 0}, {0, 1, 0, 0, 1, 0, 1, 0}, {0, 1, 0, 0, 1, 0, 1, 1}, {0, 1, 0, 0,1, 1, 1, 1}, {0, 1, 0, 0, 1, 1, 1, 0}, {0, 1, 0, 0, 1, 1, 0,0}, {0, 1, 0, 1, 1, 1, 0, 0}, {0, 1, 0, 1, 1, 0, 0, 0}, {0, 1, 0, 1,0, 0, 0, 0}, {0, 1, 0, 1, 0, 0, 0, 1}, {0, 1, 0, 1, 0, 0, 1, 1}, {0, 1, 0, 1, 0, 0, 1, 0}, {0, 1, 0, 1, 0, 1, 1, 0}, {0, 1, 0, 1,0, 1, 1, 1}, {0, 1, 0, 1, 0, 1, 0, 1}, {0, 1, 0, 1, 1, 1, 0, 1}, {0, 1, 0, 1, 1, 0, 0, 1}, {0, 1, 0, 1, 1, 0, 1, 1}, {0, 1, 0, 1,1, 0, 1, 0}, {0, 1, 0, 1, 1, 1, 1, 0}, {0, 1, 0, 1, 1, 1, 1, 1}, {0, 1, 1, 1, 1, 1, 1, 1}, {0, 1, 1, 0, 1, 1, 1, 1}, {0, 1, 1, 0,0, 1, 1, 1}, {0, 1, 1, 0, 0, 0, 1, 1}, {0, 1, 1, 0, 0, 0, 0, 1}, {0, 1, 1, 0, 0, 0, 0, 0}, {0, 1, 1, 0, 0, 0, 1, 0}, {0, 1, 1, 0,0, 1, 1, 0}, {0, 1, 1, 0, 0, 1, 0, 0}, {0, 1, 1, 0, 0, 1, 0, 1}, {0, 1, 1, 0, 1, 1, 0, 1}, {0, 1, 1, 0, 1, 0, 0, 1}, {0, 1, 1, 0,1, 0, 0, 0}, {0, 1, 1, 0, 1, 0, 1, 0}, {0, 1, 1, 0, 1, 0, 1, 1}, {0, 1, 1, 1, 1, 0, 1, 1}, {0, 1, 1, 1, 0, 0, 1, 1}, {0, 1, 1, 1,0, 0, 0, 1}, {0, 1, 1, 1, 0, 0, 0, 0}, {0, 1, 1, 1, 0, 0, 1, 0}, {0, 1, 1, 1, 0, 1, 1, 0}, {0, 1, 1, 1, 0, 1, 1, 1}, {0, 1, 1, 1,0, 1, 0, 1}, {0, 1, 1, 1, 1, 1, 0, 1}, {0, 1, 1, 1, 1, 0, 0, 1}, {0, 1, 1, 1, 1, 0, 0, 0}, {0, 1, 1, 1, 1, 0, 1, 0}, {0, 1, 1, 1,1, 1, 1, 0}, {0, 1, 1, 0, 1, 1, 1, 0}, {0, 1, 1, 0, 1, 1, 0, 0}, {0, 1, 1, 1, 1, 1, 0, 0}, {1, 1, 1, 1, 1, 1, 0, 0}, {1, 0, 1, 1,1, 1, 0, 0}, {1, 0, 0, 1, 1, 1, 0, 0}, {1, 0, 0, 0, 1, 1, 0, 0}, {1, 0, 0, 0, 0, 1, 0, 0}, {1, 0, 0, 0, 0, 0, 0, 0}, {1, 0, 0, 0,0, 0, 0, 1}, {1, 0, 0, 0, 0, 0, 1, 1}, {1, 0, 0, 0, 0, 0, 1, 0}, {1, 0, 0, 0, 0, 1, 1, 0}, {1, 0, 0, 0, 0, 1, 1, 1}, {1, 0, 0, 0,0, 1, 0, 1}, {1, 0, 0, 0, 1, 1, 0, 1}, {1, 0, 0, 0, 1, 0, 0, 1}, {1, 0, 0, 0, 1, 0, 0, 0}, {1, 0, 0, 0, 1, 0, 1, 0}, {1, 0, 0, 0,1, 0, 1, 1}, {1, 0, 0, 0, 1, 1, 1, 1}, {1, 0, 0, 0, 1, 1, 1, 0}, {1, 0, 0, 1, 1, 1, 1, 0}, {1, 0, 0, 1, 0, 1, 1, 0}, {1, 0, 0, 1,0, 0, 1, 0}, {1, 0, 0, 1, 0, 0, 0, 0}, {1, 0, 0, 1, 0, 1, 0, 0}, {1, 0, 0, 1, 0, 1, 0, 1}, {1, 0, 0, 1, 0, 1, 1, 1}, {1, 0, 0, 1,0, 0, 1, 1}, {1, 0, 0, 1, 1, 0, 1, 1}, {1, 0, 0, 1, 1, 0, 0, 1}, {1, 0, 0, 1, 1, 0, 0, 0}, {1, 0, 0, 1, 1, 0, 1, 0}, {1, 0, 1, 1,1, 0, 1, 0}, {1, 0, 1, 0, 1, 0, 1, 0}, {1, 0, 1, 0, 0, 0, 1, 0}, {1, 0, 1, 0, 0, 0, 0, 0}, {1, 0, 1, 0, 0, 0, 0, 1}, {1, 0, 1, 0,0, 0, 1, 1}, {1, 0, 1, 0, 0, 1, 1, 1}, {1, 0, 1, 0, 0, 1, 0, 1}, {1, 0, 1, 0, 0, 1, 0, 0}, {1, 0, 1, 0, 0, 1, 1, 0}, {1, 0, 1, 0,1, 1, 1, 0}, {1, 0, 1, 0, 1, 1, 0, 0}, {1, 0, 1, 0, 1, 0, 0, 0}, {1, 0, 1, 0, 1, 0, 0, 1}, {1, 0, 1, 0, 1, 0, 1, 1}, {1, 0, 1, 0,1, 1, 1, 1}, {1, 0, 1, 0, 1, 1, 0, 1}, {1, 0, 1, 1, 1, 1, 0, 1}, {1, 0, 0, 1, 1, 1, 0, 1}, {1, 0, 0, 1, 1, 1, 1, 1}, {1, 0, 1, 1,1, 1, 1, 1}, {1, 0, 1, 1, 0, 1, 1, 1}, {1, 0, 1, 1, 0, 0, 1, 1}, {1, 0, 1, 1, 0, 0, 0, 1}, {1, 0, 1, 1, 0, 0, 0, 0}, {1, 0, 1, 1,0, 0, 1, 0}, {1, 0, 1, 1, 0, 1, 1, 0}, {1, 0, 1, 1, 0, 1, 0, 0}, {1, 0, 1, 1, 0, 1, 0, 1}, {1, 1, 1, 1, 0, 1, 0, 1}, {1, 1, 0, 1,0, 1, 0, 1}, {1, 1, 0, 0, 0, 1, 0,1}, {1, 1, 0, 0, 0, 0, 0, 1}, {1, 1, 0, 0, 0, 0, 0, 0}, {1, 1, 0, 0, 0, 0, 1, 0}, {1, 1, 0, 0,0, 1, 1, 0}, {1, 1, 0, 0, 0, 1, 0, 0}, {1, 1, 0, 0, 1, 1, 0, 0}, {1, 1, 0, 0, 1, 0, 0, 0}, {1, 1, 0, 0, 1, 0, 0, 1}, {1, 1, 0, 0,1, 0, 1, 1}, {1, 1, 0, 0, 1, 0, 1, 0}, {1, 1, 0, 0, 1, 1, 1, 0}, {1, 1, 0, 0, 1, 1, 1, 1}, {1, 1, 0, 0, 0, 1, 1, 1}, {1, 1, 0, 1,0, 1, 1, 1}, {1, 1, 0, 1, 0, 0, 1, 1}, {1, 1, 0, 1, 0, 0, 0, 1}, {1, 1, 0, 1, 0, 0, 0, 0}, {1, 1, 0, 1, 0, 0, 1, 0}, {1, 1, 0, 1,0, 1, 1, 0}, {1, 1, 0, 1, 0, 1, 0, 0}, {1, 1, 0, 1, 1, 1, 0, 0}, {1, 1, 0, 1, 1, 0, 0, 0}, {1, 1, 0, 1, 1, 0, 0, 1}, {1, 1, 0, 1,1, 0, 1, 1}, {1, 1, 0, 1, 1, 0, 1, 0}, {1, 1, 0, 1, 1, 1, 1, 0}, {1, 1, 0, 1, 1, 1, 1, 1}, {1, 1, 0, 1, 1, 1, 0, 1}, {1, 1, 0, 0,1, 1, 0, 1}, {1, 1, 1, 0, 1, 1, 0, 1}, {1, 1, 1, 0, 0, 1, 0, 1}, {1, 1, 1, 0, 0, 0, 0, 1}, {1, 1, 1, 0, 0, 0, 0, 0}, {1, 1, 1, 0,0, 0, 1, 0}, {1, 1, 1, 0, 0, 1, 1, 0}, {1, 1, 1, 0, 0, 1, 0, 0}, {1, 1, 1, 0, 1, 1, 0, 0}, {1, 1, 1, 0, 1, 0, 0, 0}, {1, 1, 1, 0,1, 0, 0, 1}, {1, 1, 1, 0, 1, 0, 1, 1}, {1, 1, 1, 0, 1, 0, 1, 0}, {1, 1, 1, 0, 1, 1, 1, 0}, {1, 1, 1, 0, 1, 1, 1, 1}, {1, 1, 1, 0,0, 1, 1, 1}, {1, 1, 1, 1, 0, 1, 1, 1}, {1, 1, 1, 1, 0, 1, 1, 0}, {1, 1, 1, 1, 0, 0, 1, 0}, {1, 1, 1, 1, 0, 0, 0, 0}, {1, 1, 1, 1,0, 0, 0, 1}, {1, 1, 1, 1, 1, 0, 0, 1}, {1, 1, 1, 1, 1, 1, 0, 1}, {1, 1, 1, 1, 1, 1, 1, 1}, {1, 1, 1, 1, 1, 1, 1, 0}, {1, 1, 1, 1,1, 0, 1, 0}, {1, 1, 1, 1, 1, 0, 0, 0}, {1, 0, 1, 1, 1, 0, 0, 0}, {1, 0, 1, 1, 1, 0, 0, 1}, {1, 0, 1, 1, 1, 0, 1, 1}, {1, 1, 1, 1,1, 0, 1, 1}, {1, 1, 1, 1, 0, 0, 1, 1}, {1, 1, 1, 0, 0, 0, 1, 1}, {1, 1, 0, 0, 0, 0, 1, 1}}}

```

---

`Tuples[{0,1},{l=Length@#}],{2}]`& generates the numbers 0...8 as binary lists.

The outer `Tuples...{2}` produces all ordered pairs of those binary numbers.

`Plus@@x` sums each of the pairs, generating triplets of 0, 1.

`Cases....Count[Plus@@x, 1]==1` returns all of the sums that contain a single 1. These arise when the two original binary numbers are connected by an edge.

`Rules` connects the vertices of the graph, each vertex being a binary number.

`Graph` creates a graph corresponding to said vertices and edges.

`FindPath` finds up to 2^n paths connecting vertex a to vertex b, the given numbers.

`Last` takes the longest of these paths.

---

For three dimensions, the graph can be represented in a plane as shown here:

For the input, `{0,0,0}, {1,1,1}`, the following is output:

`{{{0, 0, 0}, {0, 0, 1}, {0, 1, 1}, {0, 1, 0}, {1, 1, 0}, {1, 0,
 0}, {1, 0, 1}, {1, 1, 1}}}`

This path can be found in the above graph.

It can also be conceived as the following path in 3-space, where each vertex corresponds to a point `{x,y,z}`. {0,0,0} represents the origin and {1,1,1} represents the "opposite" point in a unit cube.

So the solution path corresponds to a traversal of edges along the unit cube. In this case, the path is Hamiltonian: it visits each vertex one time (i.e. with no crossings and no vertices omitted).

# Answer
> 2 votes
# Jelly,  ~~25~~  27 bytes

+2 bytes to fix a bug with my golfing :( hopefully I'll find a shorter way though.

```
ṫi¥³ḣi
L2ṗŒ!ç€µạ2\S€ỊẠ×LµÞṪ

```

A full program taking the bit-strings using `1` and `2`* as lists. The arguments are `from` and `to`. The program prints a list of lists of the same.

* `0` and `1` may be used instead at the cost of a byte (add  between `L2ṗ` and `Œ!ç€...` to decrement).

**Try it online!**

### How?

**updating...**

```
ṫi¥³ḣi - Link 1, getSlice: list of lists, bitstrings; list, toBitstring
   ³   - get 3rd command line argument (fromBitstring)
  ¥    - last two links as a dyad:
 i     -   index (of fromBitstring in bitstrings)
ṫ      -   tail (bitstrings) from (that) index
     i - index (of toBitstring in that result)
    ḣ  - head to (that) index

L2ṗŒ!ç€µạ2\S€ỊẠ×LµÞṪ - Main link: list, fromBitstring; list, toBitstring
L                    - length (of fromBitstring)
 2                   - literal two
  ṗ                  - Cartesian power (of implicit range(2)=[1,2] with L(fromBitstring))
                     - ...i.e. all unique bitstrings of the required length (using [1,2])
   Œ!                - all permutations (of that list)
     ç€              - call the last link (1) as a dyad (i.e. f(that, toBitstring))
       µ         µÞ  - sort by the monadic function:
         2\          -   2-wise reduce with:
        ạ            -     absolute difference
           S€        -   sum €ach
             Ị       -   insignificant (vectorises) (abs(z)<=1 - for our purposes it's really just used for z==1 since only positive integers are possible)
              Ạ      -   all truthy? (1 if so 0 otherwise)
                L    -   length
               ×     -   multiply
                   Ṫ - tail (the last one is one of the maximal results)
                     - implicit print

```

---
Tags: code-golf, binary, graph-theory
---


title: A Slashy Dashy Spiral

text:
# Question
Title: A Slashy Dashy Spiral
Given a positive integer N, output the innermost N×N square of an ASCII art spiral made of `-|/\` that spirals clockwise inward.

The `-` is used for horizontal portions, `|` for vertical portions, and `/` and `\` for corners. The first character is `-` and the spiral proceeds left and down.

Specifically, when N is 1 the output is:

```
-

```

When N is 2 the output is:

```
/-
\-

```

When N is 3 the output is:

```
--\
/-|
\-/

```

When N is 4 the output is:

```
 /--\
 |/-|
 |\-/
 \---

```

Note how every output is a square of N by N characters.

The pattern continues in the same way:

```
N=1
-

N=2
/-
\-

N=3
--\
/-|
\-/

N=4
/--\
|/-|
|\-/
\---

N=5
----\
/--\|
|/-||
|\-/|
\---/

N=6
/----\
|/--\|
||/-||
||\-/|
|\---/
\-----

N=7
------\
/----\|
|/--\||
||/-|||
||\-/||
|\---/|
\-----/

N=8
/------\
|/----\|
||/--\||
|||/-|||
|||\-/||
||\---/|
|\-----/
\-------

etc.

```

The shortest code in bytes wins.

# Answer
# Charcoal, ~~17~~ 16 bytes:

```
↶⁴-Ｆ⊖Ｎ«↶²/ι↶²\-ι

```

Try it online! Link is to verbose version of code.

```
↷²-¶Ｆ⊖Ｎ«/ι↶²\-ι↶

```

Try it online! Link is to verbose version of code.

Edit: Saved 1 byte thanks to @icrieverytim.
> 6 votes

# Answer
# Python 2, ~~148~~ 134 bytes

```
f=lambda n,J=''.join:n<2and['-']or n%2and['-'*~-n+'\\']+map(J,zip(f(n-1),'|'*(n-2)+'/'))or map(J,zip('/'+'|'*n,f(n-1)))+['\\'+'-'*~-n]

```

Try it online!
> 4 votes

---
Tags: code-golf, string, ascii-art, geometry, integer
---


title: Elliptic system

text:
# Question
Title: Elliptic system
# Introduction

Given five points in the plane, your task is to compute the area of the ellipse passing through these points.

You can assume that exactly one non-degenerate ellipse can be constructed with the given input values.

# Rules

Input is `10` integers in any convenient form, corresponding to the `x` and `y` coordinates of the points. For example, you could take input as a list of `10` integers `[x1, y1, x2, y2, ..., x5, y5]`, or as `[[x1, y1], [x2, y2], ..., [x5, y5]]`, etc.. You may also handle decimal numbers, but only integers are required.

Output is a representation of the area of the ellipse. This may be some symbolic expression, or a decimal value with at least `8` digits of precision.

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

# Example Input and Output

Input:

> \[-2, 3, 2, 5, 5, 3, 4, 0, 1, -3\]

Output:

> 62.15326783788685

A depiction of the ellipse passing through these points:

More examples:

```
f(60, -92, -31, -10, 78, -19, -27, -35, 91, -37) = 9882.59540465108
f(-9, -4, 7, 7, 10, 1, -7, -10, 0, 7) = 269.5966648188643
f(-3, 2, 0, -5, 4, 0, -4, 1, -1, 2) = 98.54937293879908

```

# Answer
# Mathematica, ~~87~~ ~~80~~ 78 bytes

```
Area@ImplicitRegion[+##Sign@#&@@Det[{1,##,1##,#^2,#2^2}&@@@{x|y,##}]>0,{x,y}]&

```

Takes 5 inputs: `[{x1, y1}, ... , {x5, y5}]`.

Returns an exact/symbolic value.

## How?

Let `f(x, y)` denote the vector `(1, x, y, xy, x^2, y^2)` for some `x, y`.

Then, the determinant of the matrix with row vectors `[f(x, y), f(x1, y1), f(x2, y2), ..., f(x5, y5)]` is zero iff `(x, y)` is a point on the ellipse we are looking for. i.e. the determinant gives the expression for the ellipse.

Since the sign of the expression might be inverted, we take the constant term and multiply the entire expression by the sign of the constant. That way, we can set the expression greater than 0 to find the area.
> 9 votes

# Answer
# MATLAB, ~~130 124~~ 114 bytes

The input is takean as two column vectors, one for the x- and one for the y-coordinates. This method uses a least sequares regression, which provides the exact ellipse if all points are exactly on an ellipse, and then applies the formula provided here (thanks @orlp) to calculate the area.

```
function A=f(x,y);p=null([x.^2,2*x.*y,y.^2,2*x,2*y,0*x+1]);A=pi*det(p([1,2,4;2,3,5;4:6]))/abs(p(1)*p(3)-p(2)^2)^1.5

```

By appending following lines you can even plot the curve:

```
X=x;Y=y;
[x,y] = meshgrid(linspace(-7,7,50));
W = [x(:).^2,2*x(:).*y(:),y(:).^2,2*x(:),2*y(:),0*x(:)+1];
Z=x;Z(:) = W*p;
clf;plot(X,Y,'o');hold on;contour(x,y,Z,[0,0]);

```

Try it online!
> 5 votes

# Answer
## Mathematica 84 Bytes

I found this to be an interesting problem. Every ellipse is an affine transformation of the unit circle which can be parameterized as {x,y}={Cos(t),Sin(t)}, so the points on the circle can be mapped to the ellipse by {xE,yE}=A{x,y}+B where A is a constant matrix and B a vector. Plugging in the points yields 10 scalar equations and 11 scalar unknowns, but we can decide that the parameterization starts at t=0, so the system is solvable. The absolute value of the determinant of the matrix A is the ratio of the area of the ellipse to the unit circle so we multiply by Pi. Taking Max gets rid of the negative solution.

```
Max[π(a d-b c)/.Solve@MapThread[#2=={e,f}+{a,b}Cos@#+{c,d}Sin@#&,{{0,u,v,w,x},#}]]&

```

Usage:

```
%@{{-2, 3}, {2, 5}, {5, 3}, {4, 0}, {1, -3}}

```

Yields:

```
(1001 π)/(16 Sqrt[10])

```
> 3 votes

# Answer
# Mathematica, 144 bytes

```
x_±y_:=x^2a+b*x*y+y^2c+d*x+e*y+f;n=∞;Integrate[UnitStep[x±y/.FindInstance[And@@(#±#2==0&@@@#),{a,b,c,d,e,f},Reals,2][[1]]],{x,-n,n},{y,-n,n}]&

```

works for all test cases

**Input example**: `[{{-3, 2}, {0, -5}, {4, 0}, {-4, 1}, {-1, 2}}]`

**Results**

> 9882.59540465108163146329
> 269.596664818864334050934
> 98.5493729387989852754258

*-10 bytes from JungHwan Min*
± is 1-byte in default windows encoding \[CP-1252\]
> 2 votes

# Answer
# Desmos, 101 bytes

```
u
v
f(a,b,c,h,k,x,y)=(((x-h)cosc+(y-k)sinc)/a)^2+(((x-h)sinc-(y-k)cosc)/b)^2
f(m,n,o,p,q,u,v)~1
mn\pi

```

Online **Desmos** doesn't like multiline pastes, so you have to enter it in one line at a time, or

Try It Online!

Input is taken with the two lists `u` and `v`. The output is shown on the last line.

### Explanation:

* The first two lines name the input variables.
* The third line defines the equation for any ellipse, with radii `a` and `b`, rotation angle `c`, and offset `(h,k)`.

+ Prettified, it looks like this:
* The fourth line calculates a regression of `f` over the lists `u` and `v`, finding radii `m` and `n`, rotation angle `o`, and offset `(p,q)`.
* The last line calculates the area of the ellipse with the formula `A = pi*r1*r2`

You can also Try It Online (different link) for a slightly expanded, interactive visual version. You can move around the five points and view the ellipse and area in real time:

Alternatively, here is a slightly longer solution using this formula (same as @flawr's answer):

## Desmos, 106 bytes

```
u
v
f(A,B,C,D,E,F,x,y)=Axx+2Bxy+Cyy+2Dx+2Ey+F
f(G,H,I,J,K,L,u,v)~0
\pi(GIL+2HJK-JJK-GKK-HHL)/(GI-HH)^{1.5}

```

Try It Online!
> 2 votes

---
Tags: code-golf, math, geometry
---


# Question
Title: Like a path-segment; touched for the very first time
Given an ordered list of 2 or more 2D cartesian points, output a truthy value if either the path touches itself or self-intersects; otherwise output a falsy value if it does not touch itself or self-intersect.

You may assume that consecutive points in the list are distinct.

### Examples:

```
(0,0), (1,0) -> falsey
(0,0), (1,0), (0,0) -> truthy
(0,0), (1,0), (1,1), (0,0) -> truthy
(0,0), (2,0), (1,1), (1,-1) -> truthy
(0,0), (10,0), (0,1), (10,1), (0,2), (10,2) -> falsey

```

Note all the co-ordinates I gave here are integers. You may support co-ordinate inputs of whatever you like out of {integer, decimal, rational, floating-point, ...}. But your implementations calculations must give the correct answers for any inputs given.

# Answer
> 5 votes
# Python 2, ~~315~~ ~~309~~ ~~298~~ ~~382~~ ~~380~~ 372 bytes

```
s=sorted
w=lambda(x,y),(X,Y),(z,w):(X-x)*(w-y)-(z-x)*(Y-y)
def I(a,b):p,q=s(a);P,Q=s(b);n,N,m,M=w(p,q,P),w(p,q,Q),w(P,Q,p),w(P,Q,q);return(q>=P)*(Q>=p)if{n,N,m,M}=={0}else(b[1]!=a[0])*(n*N<=0>=m*M)
def f(l):
 i=0
 while i<len(l)-2:
	x=l[i:i+3];i+=1
	if w(*x)==0and s(x)==x:l.pop(i);i-=1
 L=zip(l,l[1:]);return any(I(*l)for l in[(k,x)for i,k in enumerate(L)for x in L[:i]])

```

Try it online!

Uses the algorithm from here, combined with this SO answer for collinear segments.

Edit: Fixed for line segments continuing in the same direction (eg `(0,0),(1,0),(2,0)`) by removing the middle point, (resulting in `(0,0),(2,0)`).

# Answer
> 3 votes
# Eukleides, ~~154~~ 148 bytes

```
number i (set p)
g=card(p);h=g;n=0;e=p[0];q=e.e
for d in p
if h<g-1
q=q.e
n=card(intersection(d.e,q))>1or d on q?1|n
end
e=d;h=h-1
end;return n;end

```

Function named `i` that, passed a set of points, returns 0 or 1. Semicolons and line breaks are interchangeable for ending a command, I just lumped a few things together for the sake of keeping the code visibly short since we're not used to legible code around here anyway.

Eukleides is a plane geometry language primarily for graphical output, but with decent programmatic abilities as well. I thought it'd be great for this task, but a few things frustrated me. First, it's worth noting that *sets* in Eukleides are essentially arrays of points, and when applicable are rendered out as paths made of connected line segments. Eukleides supports the iterative generation of sets via loci, akin to a for-loop that creates a set in the process. Had I been able to use a locus, it would have shaved off bytes, but apparently Eukleides doesn't like to reference a partially-formed locus from within itself.

The other major frustration was that if, seemingly, two identical line segments are on top of each other, `intersection` only returns one offending point (which makes sense, I suppose, there would be infinite intersections). My method is essentially to build up the path one step behind, and test the next line segment for intersections with the path. Because of the aforementioned intersection behavior I check separately for whether or not the point is *on* the path.

*Edit*: Cut off 1 byte by reordering the `or` statement to allow for the removal of a space before `or`; 5 more bytes by changing that `if` block into a ternary operation.

Test cases:

```
ta=point(0,0).point(1,0)
tb=point(0,0).point(1,0).point(0,0)
tc=point(0,0).point(1,0).point(1,1).point(0,0)
td=point(0,0).point(2,0).point(1,1).point(1,-1)
te=point(0,0).point(10,0).point(0,1).point(10,1).point(0,2).point(10,2)
print i(ta);print i(tb);print i(tc);print i(td);print i(te)

0
1
1
1
0

```

---
Tags: code-golf, geometry
---


title: How many chapters do I have?

text:
# Question
Title: How many chapters do I have?
*The Bible* is one of the most influential books ever written, and commonly cited as the best selling book of all time. It was written by approximately 40 different authors over hundreds of years before being compiled into it's current form. But what's interesting about The Bible is the way it's divided up. It is split up into 2 different testaments, which are split up into 66 smaller books, which are each split up into smaller chapters, which are each split up into individual verses.

I thought it would be a fun challenge to try to encode the number of chapters in each book in the shortest code possible. So for today's challenge, you must write a program or function that takes one of the books as input, and outputs the number of chapters in that book according to *The King James Version*.

You may take IO in any reasonable format, for example reading/writing STDIN/STDOUT or a file, function arguments/return values, prompting the user, etc. are all allowed. The input will always be one of the 66 books of The Bible, and only lowercase. This means that if you are given any other input, undefined behavior is allowed. Since there are only 66 possible inputs and outputs, they are all provided here, according to Wikipedia's page on Bible chapters in The King James Version:

```
genesis         50
exodus          40
leviticus       27
numbers         36
deuteronomy     34
joshua          24
judges          21
ruth            4
1 samuel        31
2 samuel        24
1 kings         22
2 kings         25
1 chronicles    29
2 chronicles    36
ezra            10
nehemiah        13
esther          10
job             42
psalms          150
proverbs        31
ecclesiastes    12
song of solomon 8
isaiah          66
jeremiah        52
lamentations    5
ezekiel         48
daniel          12
hosea           14
joel            3
amos            9
obadiah         1
jonah           4
micah           7
nahum           3
habakkuk        3
zephaniah       3
haggai          2
zechariah       14
malachi         4
matthew         28
mark            16
luke            24
john            21
acts            28
romans          16
1 corinthians   16
2 corinthians   13
galatians       6
ephesians       6
philippians     4
colossians      4
1 thessalonians 5
2 thessalonians 3
1 timothy       6
2 timothy       4
titus           3
philemon        1
hebrews         13
james           5
1 peter         5
2 peter         3
1 john          5
2 john          1
3 john          1
jude            1
revelation      22

```

Since this challenge is about finding the optimal way to encode every book name and chapter count, using any builtins that give information about The Bible are not permitted. However, since it would be interesting to see which languages have such builtins, feel free to share a second non-competing version along with your answer. Fetching information from external sources is also not permitted (none of the standard loopholes are allowed, but I thought it would be useful to explicitly mention that one).

As usual, this is a challenge, so try to make the shortest possible program (measured in bytes) as you can. Have fun golfing!

# Answer
> 12 votes
# Jelly, 127 bytes

```
“£ÐgƁ÷ḅ*Wßßɦ*⁷ċṗṿỵ×Ɓṿ⁷ḢQ’b7+\;“BƝ‘
OḄ;407;270;“ọḷḊḲɦ‘%/i@“¡Ṙ×!⁸Ọ5`ỊV-ṙQȷṖÞ(sĿȮ^k³M"ɓmEf¤*0C[ạƇŻȥ#BṚñİmZẓeȦUƈ!ċ€@Ȧʋ)ƙḅyẉ’b158¤ị¢

```

Try it online!

Test Cases

**How it Works**

Essentially, this tries to convert the ords of the characters input into a binary value, for example `"joel"` -\> `[106, 111, 101, 108]`-\> `2^3*106 + 2^2*111 + 2^1*101 + 2^0*108`.

Then, this value is taken mod 407, then mod 270, then \[a few more mods\], then mod 160. This is useful because it maps all 66 string inputs to integers between 0 and 158 (lucky on final mod).

The integer is indexed from the integer list `“ọḷḊḲɦ...ƙḅyẉ’b158¤` to find the value of `n` such that the input has the `n`-th least number of chapters. Joel happens to have the 7-th least number of chapters.

This value of `n` is further indexed into the list `“£ÐgƁ÷ḅ*Wßßɦ*⁷ċṗṿỵ×Ɓṿ⁷ḢQ’b7+\;“BƝ‘` to find the exact number of chapters.

Possible improvement: inputs with the same number of chapters can hash to the same value from the mods (0% collision is not necessary), but I did not account for that in my program to determine the sequence of mods.

# Answer
> 10 votes
# JavaScript (ES6), ~~251~~ 197 bytes

```
s=>`-  cE1$ " +%&  %  &!!· $!#&!!)!'=6 &!6".!  -!!Q$"/  779@@= % & $'1 U( I>!!  K * "S< :  9$!C %  . $. 9E1/ %!!'" + $ % `.split`!`.join`   `.charCodeAt(parseInt(s[2]+s[0]+s[5],36)%913%168%147)-33

```

### Test

```
let f =

s=>`-  cE1$ " +%&  %  &!!· $!#&!!)!'=6 &!6".!  -!!Q$"/  779@@= % & $'1 U( I>!!  K * "S< :  9$!C %  . $. 9E1/ %!!'" + $ % `.split`!`.join`   `.charCodeAt(parseInt(s[2]+s[0]+s[5],36)%913%168%147)-33

o.innerText = [
  ["genesis",         50 ],
  ["exodus",          40 ],
  ["leviticus",       27 ],
  ["numbers",         36 ],
  ["deuteronomy",     34 ],
  ["joshua",          24 ],
  ["judges",          21 ],
  ["ruth",            4  ],
  ["1 samuel",        31 ],
  ["2 samuel",        24 ],
  ["1 kings",         22 ],
  ["2 kings",         25 ],
  ["1 chronicles",    29 ],
  ["2 chronicles",    36 ],
  ["ezra",            10 ],
  ["nehemiah",        13 ],
  ["esther",          10 ],
  ["job",             42 ],
  ["psalms",          150],
  ["proverbs",        31 ],
  ["ecclesiastes",    12 ],
  ["song of solomon", 8  ],
  ["isaiah",          66 ],
  ["jeremiah",        52 ],
  ["lamentations",    5  ],
  ["ezekiel",         48 ],
  ["daniel",          12 ],
  ["hosea",           14 ],
  ["joel",            3  ],
  ["amos",            9  ],
  ["obadiah",         1  ],
  ["jonah",           4  ],
  ["micah",           7  ],
  ["nahum",           3  ],
  ["habakkuk",        3  ],
  ["zephaniah",       3  ],
  ["haggai",          2  ],
  ["zechariah",       14 ],
  ["malachi",         4  ],
  ["matthew",         28 ],
  ["mark",            16 ],
  ["luke",            24 ],
  ["john",            21 ],
  ["acts",            28 ],
  ["romans",          16 ],
  ["1 corinthians",   16 ],
  ["2 corinthians",   13 ],
  ["galatians",       6  ],
  ["ephesians",       6  ],
  ["philippians",     4  ],
  ["colossians",      4  ],
  ["1 thessalonians", 5  ],
  ["2 thessalonians", 3  ],
  ["1 timothy",       6  ],
  ["2 timothy",       4  ],
  ["titus",           3  ],
  ["philemon",        1  ],
  ["hebrews",         13 ],
  ["james",           5  ],
  ["1 peter",         5  ],
  ["2 peter",         3  ],
  ["1 john",          5  ],
  ["2 john",          1  ],
  ["3 john",          1  ],
  ["jude",            1  ],
  ["revelation",      22 ]
]
.every(s => (log += s[0] + ' --> ' +  (res = f(s[0])) + '\n', res == s[1]), log = '')
? log + '\nSUCCESS' : log + '\nFAIL'
```

```
<pre id=o></pre>
```

### Formatted and commented

```
s =>                                 // s = book name
  `-  cE1$ " +%&  %  &!!· (...)`     // data string (truncated)
  .split`!`.join`   `                // inflate padding characters '!' -> 3 spaces
  .charCodeAt(                       // read the ASCII code at the position found by
    parseInt(s[2] + s[0] + s[5], 36) // parsing 3 characters of the input in this exact
    % 913 % 168 % 147                // order as base 36 and applying three consecutive
  ) - 33                             // modulo operations, then subtract 33

```

# Answer
> 10 votes
# Excel, 373 bytes

Reusing @Misha's approach from the Mathematica answer (`6a+b+8c+5d+3e modulo 151`):

```
=CHOOSE(MOD(6*CODE(LEFT(A1,1))+CODE(MID(A1,2,1))+8*CODE(MID(A1,3,1))+5*CODE(MID(A1&A1,4,1))+3*CODE(MID(A1&A1,5,1)),151)+1,30,,,,27,,,,3,12,,,9,,149,,,28,,,13,,,35,3,,35,7,,8,,20,,49,23,13,4,,,4,,,,,,,2,,,39,,,15,3,,3,9,,12,27,,,,,,51,15,,,,70,,65,,21,11,,,4,,24,,,6,,2,1,,,,,,2,,,30,,,,,,23,,,33,,20,,,15,,,4,,4,,,12,2,,2,47,23,,2,,,,,41,,,3,,,5,,,,,11,,21,5,,,,5,2,3,26)+1
```

Lookup returns chapters `-1`, and then add the one. This changes `10` into `9` twice, and `,1,` into `,,` 4 times.

# Updated to old approach. Excel, ~~460~~ 401 bytes

Save as CSV, Book Name entered at end of first line (`C1`), result displayed in `C2`:

```
1c,16,revelation
1co,29,"=VLOOKUP(LEFT(C1,1)&MID(C1,3,1)&MID(C1,6,1),A:B,2)"
1j,5
1k,22
1p,5
1s,31
1t,6
1ts,5
2c,13
2co,36
2j,1
2k,25
2p,3
2s,24
2t,4
2ts,3
3j,1
a,9
at,28
c,4
d,12
du,34
e,12
ee,48
eh,6
eo,40
er,10
g,6
gn,50
h,3
hbw,13
hg,2
hs,14
i,66
j,42
jd,1
jds,21
je,3
jh,21
jm,5
jn,4
jr,52
js,24
lm,5
lv,27
m,7
ml,4
mr,16
mt,28
n,3
nhi,13
nm,36
o,1
p,150
pi,1
pip,4
po,31
r,16
rt,4
rv,22
s,8
t,3
zc,14
zp,3
```

For the lookup table, we can leave out `et 10` and `l 24` because these match on `er 10` and `js 24` respectively.

# Answer
> 9 votes
# Mathematica: ~~323~~ 294 bytes

```
Uncompress["1:eJxTTMoPSpvOwMBQzAIkfDKLSzJlgAwCBEhtJi8qwQUnpqESsqgEHyqhAjePBc7lgBOccEIUThiBCAm4AayECUZUghmV0EAlBFAdxILqN17CgWMCNwUn4QQnxEAEDyqBcLgkKsGO6gUmLAROX8rjJSRQCSU4IYpKILzAiDfEebG4wADVDmZchBYqgRYVbLgIRPiJ4VXHDDdKGuZ9AAP6TUg="][[Mod[ToCharacterCode@StringTake[#<>#,5].{6,1,8,5,3},151,1]]]&

```

### How it works

For a book beginning with character codes `a`,`b`,`c`,`d`,`e` (wrapping around if necessary) computes `6a+b+8c+5d+3e` modulo 151, which happens to be unique, and then looks up the number of chapters in a compressed list of length 151. (Unused entries in the list are filled in with duplicates of the previous entry. This encourages run-length encoding, maybe? Anyway, it helps.)

Thanks to @numbermaniac for the list compression idea, which is hard to put a number on but is a huge part of the improvement here.

# Old version: Mathematica, ~~548~~ ~~435~~ 407 bytes

```
Join["111112333333344444455555666789"~(p=StringPartition)~1,"1010121213131314141616162121222224242425272828293131343636404248505266"~p~2,{"150"}][[Max@StringPosition["2jn3jnjduoaapimhgi2pe2tshbkjeonhntttzpn2toclsjnjmlhpiprtu1jn1pe1tsjmjlmt1toehiglimcmsnoaometrerzdnlecs2cihbwnhihshzcr1cimrarmsjhojds1kgrva2sujsalku2kglviatcmte1co1supordur2conmreosjbbeeegnijriiahpas",""<>#&@Characters[#<>#][[{1,3,6}]]]/3]]&

```

### How it works

We convert each name `name` to characters 1, 3, and 6 of `namename` (e.g. `leviticus` becomes `lvi`, `job` becomes `jbb`) before looking it up.

The list we look things up in is slightly compressed by putting the 1-digit and the 2-digit chapter numbers together in strings.

# Mathematica: 40 bytes, non-competing

```
WolframAlpha["# chapters "<>#,"Result"]&

```

Yeah.

# Answer
> 6 votes
# Python 2, ~~244~~ 183 bytes

```
lambda n:ord('A("4,|O|;|>||_ /\xb5$+_>| _7|a|5-##_"_G"_/|7) $_$-|<|$_"&|||_;S_% |:_45_#||#|%7"_,_\'_)|_"|C_#|/_I|$_ "|,|_%|_8_Q|+||||_!|_C#'.replace('|','__')[hash(n)%839%434%152])-31

```

Try it online!

# Answer
> 5 votes
# Jelly,  ~~117 115~~  114 bytes

```
OP%⁽µW%⁽£İ%237
“ĿḊƘ⁹ƙƬṂ;ɓṭ6-ạʋ⁵%$Ẋf,¥ÆÑƈø¬ȦṘd⁾“ʂụṿⱮẆƊ¦ẠLjƒ~Ḅr©“Ẏw|!¡¢o“ŻɗṢ“3ɠ‘Zċ€ÇTḢị“£ẆJQ+k⁽’ḃ6¤+\;“£¬®µıñø"BƝ¤‘¤

```

**Try it online!** or see the test-suite

### How?

Hashes the product of the ordinals of the characters of the input string by taking ~~three~~ ~~two~~ three division remainders, looks up the result in a list of lists and uses the found index to look up the result in a list of book lengths.

When finding a hash function I only considered those which resulted in at most one bucket with any results over 255 to allow code-page indexing and then chose ones that minimised the total number of values to encode (after removing the "offending" bucket or if none existed the longest bucket). From 66 with three modulos I found a 59 (`%731%381%258`) a 58 (`%731%399%239`) then one with 56 entries (`%1241%865%251`) \[making for 117 bytes\] ...I then found a 58 using only two remainders (`%1987%251`) \[making for 115 bytes\]
...then I found a 55 using three remainders, which when two dummy entries are added allows for a further compression of the lookup list...

The code:

1.

```
“ĿḊƘ⁹ƙƬṂ;ɓṭ6-ạʋ⁵%$Ẋf,¥ÆÑƈø¬ȦṘd⁾“ʂụṿⱮẆƊ¦ẠLjƒ~Ḅr©“Ẏw|!¡¢o“ŻɗṢ“3ɠ‘

```

is a list of five lists of code-page indices (`“...“...“...“...“...“...‘`):

```
[[199,193,148,137,161,152,179,59,155,224,54,45,211,169,133,37,36,208,102,44,4,13,16,156,29,7,190,204,100,142],[167,225,226,149,207,145,5,171,76,106,158,126,172,114,6],[209,119,124,33,0,1,111],[210,157,183],[51,159]]

```

This is transposed using the atom `Z` to get the buckets; call this B:

```
[[199,167,209,210,51],[193,225,119,157,159],[148,226,124,183],[137,149,33],[161,207,0],[152,145,1],[179,5,111],[59,171],[155,76],[224,106],[54,158],[45,126],[211,172],[169,114],[133,6],37,36,208,102,44,4,13,16,156,29,7,190,204,100,142]

```

(the `0` and `1` are the dummy keys, allowing the `[179,5,111]` to be two further to the right - the transpose requires longer entries to be to the left)

2.

```
“£ẆJQ+k⁽’ḃ6¤+\;“£¬®µıñø"BƝ¤‘¤

```

Call this C (the chapter counts) - it's a list of integers:

```
[1,4,5,6,10,12,13,14,16,21,22,24,28,31,36,40,42,48,50,52,2,7,8,9,25,27,29,34,66,150,3]

```

and is constructed as follows (the two dummy keys above therefore allow `10,12,13` to be in ascending order):

```
“£ẆJQ+k⁽’ḃ6¤+\;“£¬®µıñø"BƝ¤‘¤
                            ¤ - nilad followed by link(s) as a nilad:
           ¤                  -   nilad followed by link(s) as a nilad:
“£ẆJQ+k⁽’                     -     base 250 number = 935841127777142
         ḃ6                   -     converted to bijective base 6 = [1,3,1,1,4,2,1,1,2,5,1,2,4,3,5,4,2,6,2,2]
            +\                -     cumulative reduce with addition = [1,4,5,6,10,12,13,14,16,21,22,24,28,31,36,40,42,48,50,52]
               “£¬®µıñø"BƝ¤‘  -   code-page indices = [2,7,8,9,25,27,29,34,66,150,3]
              ;               -   concatenate = [1,4,5,6,10,12,13,14,16,21,22,24,28,31,36,40,42,48,50,52,2,7,8,9,25,27,29,34,66,150,3]

```

Now the simplified version of the code is:

```
OP%⁽µW%⁽£İ%237 - Link 1, hash function: list of characters   e.g. "genesis"
O              - cast to ordinals             [103,101,110,101,115,105,115]
 P             - product                                    160493569871250
   ⁽µW         - base 250 literal                                      3338
  %            - modulo                                                1050
       ⁽£İ     - base 250 literal                                      1699
      %        - modulo                                                1050
           237 - literal                                                237
          %    - modulo                                                 102

Bċ€ÇTḢịC - Main link: list of characters                     e.g. "genesis"
B        - the list of buckets, B, described  in (1) above
   Ç     - call the last link as a monad (get the hashed value)         102
 ċ€      - count for €ach - yields 29 zeros and a one or 30 zeros       [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0]
    T    - truthy indexes - yields a list of length one or zero         [19]
     Ḣ   - head - extracts that value or zero if it was empty            19  ----------------------------------------------v
       C - the list of chapter lengths, C, described in (2) above       [1,4,5,6,10,12,13,14,16,21,22,24,28,31,36,40,42,48,50,52,2,7,8,9,25,27,29,34,66,150,3]
      ị  - index (the head value) into (the chapter list, c)             50
         -       - 1-indexed and modular so 0 yields 3 (the rightmost)

```

# Answer
> 3 votes
# Python 2, ~~438~~ ~~429~~ ~~416~~ ~~411~~ 409 bytes

```
lambda s:[c for x,c in zip('A|m|C|h|2|th|2 Co|D|y|E|Ep|Ec|x|ze|G|Ge|H|gg|He|Ho|I|Jo|oe|oh|na|sh|Ju|dg|Ja|Je| J|1 J|K|2 K|L|Le|Lu|M|ch|rk|tt|N|Ne|Nu|O|P|Pr|Ph|pp|Pe|2 P|R|Ro|Ru|S|Sa|2 S|T| T|2 T| Ti|2 Ti|Z|Zep'.split('|'),(28,9,4,29,36,16,13,12,34,10,6,12,40,48,6,50,3,2,13,14,66,42,3,21,4,24,1,21,5,52,1,5,22,25,5,27,24,7,4,16,28,3,13,36,1,150,31,1,4,5,3,22,16,4,8,31,24,3,5,3,6,4,14,3))if x in s.title()][-1]

```

Try it online!

Works by changing the input to Title Case, and finding the last matching substring in the list.

```
[('A', 28), ('m', 9), ('C', 4), ('h', 29), ('2', 36), ('th', 16), ('2 Co', 13), ...

```

Eg. `'1 samuel' -> '1 Samuel'` which matches `('m', 9), ('2', 36), ('S', 8), ('Sa', 31), ('2 S', 24)`. The last match is `('2 S', 24)`, so the answer is `24`

# Answer
> 3 votes
# 6502 machine code (C64), 204 bytes

```
00 C0 20 FD AE 20 9E AD 85 FD 20 A3 B6 A9 1E 85 FB A9 00 85 FC A8 B1 22 18 69
4A 65 FC 45 FB 85 FC E6 FB C8 C4 FD D0 EE A5 FC 4A 4A 4A 4A A8 A5 FC 29 0F 19
BA C0 A8 BE 3D C0 A9 00 4C CD BD 16 34 42 0D 01 00 04 03 04 1C 0A 00 06 15 07
00 16 00 22 03 02 0E 00 24 00 00 01 00 08 03 00 1C 03 01 00 00 00 00 00 03 03
00 00 00 24 10 1F 18 0E 10 00 00 00 32 30 1F 2A 00 0D 00 05 00 1B 00 0A 00 01
28 00 00 0C 96 00 10 00 00 00 18 00 00 03 00 00 00 00 00 00 15 09 00 05 00 04
00 00 04 00 00 04 00 00 18 00 1D 05 00 00 19 00 0D 00 00 06 06 0C 00 00 00 00
05 00 01 00 05 00 04 30 10 20 10 40 70 00 00 20 50 00 10 60 30 20

```

**Explanation**:

The key here is to use a special hashing function that maps without collissions to values `0` to `125` \*). The chapter numbers are then placed in a 126 bytes table. The hashing is done in full 8 bits, the final value is adjusted by looking up the high nibbles in yet another table, this way combining different high nibbles where the low nibbles don't collide.

Here's a commented disassembly listing of the code part:

```
.C:c000  20 FD AE    JSR $AEFD          ; consume comma
.C:c003  20 9E AD    JSR $AD9E          ; evaluate argument
.C:c006  85 FD       STA $FD            ; remember string length
.C:c008  20 A3 B6    JSR $B6A3          ; free string ....
.C:c00b  A9 1E       LDA #$1E           ; initial xor key for hash
.C:c00d  85 FB       STA $FB
.C:c00f  A9 00       LDA #$00           ; initial hash value
.C:c011  85 FC       STA $FC
.C:c013  A8          TAY
.C:c014   .hashloop:
.C:c014  B1 22       LDA ($22),Y        ; load next string character
.C:c016  18          CLC                ; clear carry for additions
.C:c017  69 4A       ADC #$4A           ; add fixed offset
.C:c019  65 FC       ADC $FC            ; add previous hash value
.C:c01b  45 FB       EOR $FB            ; xor with key
.C:c01d  85 FC       STA $FC            ; store hash value
.C:c01f  E6 FB       INC $FB            ; increment xor key
.C:c021  C8          INY                ; next character
.C:c022  C4 FD       CPY $FD            ; check for string length
.C:c024  D0 EE       BNE .hashloop      ; end of string not reached -> repeat
.C:c026   .hashadjust:
.C:c026  A5 FC       LDA $FC            ; load hash
.C:c028  4A          LSR A              ; shift left four times
.C:c029  4A          LSR A
.C:c02a  4A          LSR A
.C:c02b  4A          LSR A
.C:c02c  A8          TAY                ; and copy to y index register
.C:c02d  A5 FC       LDA $FC            ; load hash again
.C:c02f  29 0F       AND #$0F           ; mask low nibble
.C:c031  19 BA C0    ORA $C0BA,Y        ; and add high nibble from table
.C:c034  A8          TAY                ; copy to y index register
.C:c035  BE 3D C0    LDX .chapters,Y    ; load chapter number from table
.C:c038  A9 00       LDA #$00           ; accu must be 0 for OS function:
.C:c03a  4C CD BD    JMP $BDCD          ; print 16bit value in A/X

```

after that follows a table of the chapter numbers and finally a table of the high nibbles for the hash value.

**Online demo**

**Usage:** `sys49152,"name"`, for example `sys49152,"genesis"` (output `50`).

**Important:** If the program was load from disk (like in the online demo), issue a `new` command first! This is necessary because loading a machine program trashes some C64 BASIC pointers.

Hint about the casing: In the default mode of the C64, the input will appear as upper case. This **is** in fact lowercase, but the C64 has two modes and in the default upper/graphics mode, lowercase characters appear as uppercase and uppercase characters appear as graphics symbols.

---

\*) of course, this isn't as dense as it could be ... oh well, maybe I find an even better solution later ;)

# Answer
> 1 votes
# Java 8, ~~623~~ ~~597~~ 590 bytes

```
s->{int i=s.chars().map(c->c*c*c).sum()/13595;return s.contains("tt")?28:i<258?42:i<355?1:i<357?3:i<362?16:i<366?28:i<369?21:i<375?9:i<377?24:i<380?5:i<382?1:i<386?10:i<402?7:i<436?4:i<438?5:i<439?14:i<461?3:i<463?2:i<477?22:i<478?25:i<490?5:i<491?3:i<493?12:i<500?66:i<545?3:i<546?1:i<548?21:i<562?4:i<568?24:i<570?10:i<572?31:i<573?24:i<582?16:i<583?150:i<607?40:i<629?48:i<639?50:i<663?13:i<675?3:i<677?36:i<679?52:i<734?1:i<735?6:i<736?4:i<775?14:i<785?6:i<796?3:i<800?31:i<812?6:i<876?27:i<910?29:i<911?36:i<940?22:i<1018?4:i<1035?16:i<1036?13:i<1066?12:i<1092?34:i<1229?5:i<1230?3:8;}

```

-7 bytes thanks to *@Nevay* by changing the for-loop to a stream.

Can definitely be golfed more.. Just need to do some more testing.
It may not be the shortest answer by a long shot, and could be golfed by porting some existing answer, but I'm still proud to come up with something myself.. :)

**Explanation:**

Try it here.

1. Takes the power of 3 of each character (as ASCII value) in the input String
2. Takes the sum of those
3. Divides the result by `13595` as integer division (in Java this automatically truncates/floors the result).
4. This leaves 65 unique values (only `habakkuk` and `matthew` both have a value of `674`)
5. And then one giant ternary-if to return the correct result (with a few values combining in a single ternary-statement where possible (`381` and `382` both `1`; `425` and `436` both `4`; `649` and `663` both `13`; `952` and `1018` both `4`; `1122` and `1229` both `5`).

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