title: Subset Sum Orderings

text:
# Question
Title: Subset Sum Orderings
A set of `n` positive numbers has `2^n` subsets. We'll call a set "nice" if none of those subsets have the same sum. `{2, 4, 5, 8}` is one such nice set. Since none of the subsets has the same sum, we can sort the subsets by sum:

`[{}, {2}, {4}, {5}, {2, 4}, {2, 5}, {8}, {4, 5}, {2, 8}, {2, 4, 5}, {4, 8}, {5, 8}, {2, 4, 8}, {2, 5, 8}, {4, 5, 8}, {2, 4, 5, 8}]`

If we label the numbers `[2, 4, 5, 8]` with the symbols `[a, b, c, d]` in increasing order, we get the following abstract ordering:

`[{}, {a}, {b}, {c}, {a, b}, {a, c}, {d}, {b, c}, {a, d}, {a, b, c}, {b, d}, {c, d}, {a, b, d}, {a, c, d}, {b, c, d}, {a, b, c, d}]`

Another nice set of positive numbers can have the same abstract ordering, or a different one. For instance, `[3, 4, 8, 10]` is a nice set with a different abstract ordering:

`[{}, {a}, {b}, {a, b}, {c}, {d}, {a, c}, {b, c}, {a, d}, {b, d}, {a, b, c}, {a, b, d}, {c, d}, {a, c, d}, {b, c, d}, {a, b, c, d}]`

In this challenge, you must count the number of distinct abstract orderings of nice sets of `n` positive numbers. This sequence is OEIS A009997, and the known values, starting at `n=1`, are:

```
1, 1, 2, 14, 516, 124187, 214580603

```

For instance, for `n=3`, the following are the two possible abstract orderings:

```
[{}, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}]
[{}, {a}, {b}, {a, b}, {c}, {a, c}, {b, c}, {a, b, c}]

```

For `n=4`, the following are the 14 possible abstract orderings, plus an example nice set with that ordering:

```
[{}, {a}, {b}, {a, b}, {c}, {a, c}, {b, c}, {a, b, c}, {d}, {a, d}, {b, d}, {a, b, d}, {c, d}, {a, c, d}, {b, c, d}, {a, b, c, d}], [8, 4, 2, 1]
[{}, {a}, {b}, {a, b}, {c}, {a, c}, {b, c}, {d}, {a, b, c}, {a, d}, {b, d}, {a, b, d}, {c, d}, {a, c, d}, {b, c, d}, {a, b, c, d}], [10, 6, 3, 2]
[{}, {a}, {b}, {a, b}, {c}, {a, c}, {d}, {b, c}, {a, d}, {a, b, c}, {b, d}, {a, b, d}, {c, d}, {a, c, d}, {b, c, d}, {a, b, c, d}], [10, 7, 4, 2]
[{}, {a}, {b}, {a, b}, {c}, {a, c}, {d}, {a, d}, {b, c}, {a, b, c}, {b, d}, {a, b, d}, {c, d}, {a, c, d}, {b, c, d}, {a, b, c, d}], [8, 6, 4, 1]
[{}, {a}, {b}, {a, b}, {c}, {d}, {a, c}, {b, c}, {a, d}, {b, d}, {a, b, c}, {a, b, d}, {c, d}, {a, c, d}, {b, c, d}, {a, b, c, d}], [10, 8, 4, 3]
[{}, {a}, {b}, {a, b}, {c}, {d}, {a, c}, {a, d}, {b, c}, {b, d}, {a, b, c}, {a, b, d}, {c, d}, {a, c, d}, {b, c, d}, {a, b, c, d}], [8, 7, 4, 2]
[{}, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}, {d}, {a, d}, {b, d}, {c, d}, {a, b, d}, {a, c, d}, {b, c, d}, {a, b, c, d}], [10, 4, 3, 2]
[{}, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {d}, {a, b, c}, {a, d}, {b, d}, {c, d}, {a, b, d}, {a, c, d}, {b, c, d}, {a, b, c, d}], [8, 4, 3, 2]
[{}, {a}, {b}, {c}, {a, b}, {a, c}, {d}, {b, c}, {a, d}, {a, b, c}, {b, d}, {c, d}, {a, b, d}, {a, c, d}, {b, c, d}, {a, b, c, d}], [8, 5, 4, 2]
[{}, {a}, {b}, {c}, {a, b}, {a, c}, {d}, {a, d}, {b, c}, {a, b, c}, {b, d}, {c, d}, {a, b, d}, {a, c, d}, {b, c, d}, {a, b, c, d}], [10, 7, 6, 2]
[{}, {a}, {b}, {c}, {a, b}, {d}, {a, c}, {b, c}, {a, d}, {b, d}, {a, b, c}, {c, d}, {a, b, d}, {a, c, d}, {b, c, d}, {a, b, c, d}], [8, 6, 4, 3]
[{}, {a}, {b}, {c}, {a, b}, {d}, {a, c}, {a, d}, {b, c}, {b, d}, {a, b, c}, {c, d}, {a, b, d}, {a, c, d}, {b, c, d}, {a, b, c, d}], [10, 8, 6, 3]
[{}, {a}, {b}, {c}, {d}, {a, b}, {a, c}, {b, c}, {a, d}, {b, d}, {c, d}, {a, b, c}, {a, b, d}, {a, c, d}, {b, c, d}, {a, b, c, d}], [8, 6, 5, 4]
[{}, {a}, {b}, {c}, {d}, {a, b}, {a, c}, {a, d}, {b, c}, {b, d}, {c, d}, {a, b, c}, {a, b, d}, {a, c, d}, {b, c, d}, {a, b, c, d}], [7, 6, 5, 3]

```

---

The following is not a valid abstract ordering:

`{}, {a}, {b}, {c}, {d}, {a,b}, {e}, {a,c}, {b,c}, {a,d}, {a,e}, {b,d}, {b,e}, {c,d}, {a,b,c}, {a,b,d}, {c,e}, {d,e}, {a,b,e}, {a,c,d}, {a,c,e}, {b,c,d}, {b,c,e}, {a,d,e}, {b,d,e}, {a,b,c,d}, {c,d,e}, {a,b,c,e}, {a,b,d,e}, {a,c,d,e}, {b,c,d,e}, {a,b,c,d,e}`

This ordering implies that:

```
d < a + b
b + c < a + d
a + e < b + d
a + b + d < c + e

```

Summing these inequalities gives:

```
2a + 2b + c + 2d + e < 2a + 2b + c + 2d + e

```

which is a contradiction. Your code must not count this ordering. Such counterexamples first appear at `n=5`. Example from this paper, example 2.5 on page 3.

This ordering is invalid despite the fact that `A < B` implies that `A U C < B U C`, for any `C` disjoint from `A` and `B`.

---

Your code or program must be fast enough that you can run it to completion on `n=4` before submitting it.

Submissions may be programs, functions, etc. as usual.

Standard Loopholes are forbidden, as always. This is code golf, so shortest answer in bytes wins. Feel free to ask clarifying questions in the comments.

# Answer
> 11 votes
# Python 3 \+ SciPy, ~~396~~ ~~390~~ ~~385~~ ~~351~~ ~~336~~ 355 bytes

```
from scipy.optimize import*
n=int(input())
r=range(n)
def f(u):
 s=linprog(r,u,[-n]*len(u),options={'tol':.1});c=s.success;y=sorted(range(c<<n),key=lambda a:s.x.round()@[a>>i&1for i in r])
 for a,b in zip(y,y[1:]):
  v=[(a>>i&1)-(b>>i&1)for i in r]
  if~-(v in u):c+=f(u+[[-z for z in v]]);u+=v,
 return+c
print(f([[(i==j-1)-(i==j)for i in r]for j in r]))

```

Try it online!

This now runs for *n* = 5 in about 5 seconds. The `if~-(v in u):` can be removed for −18 bytes but a huge performance penalty.

If you want to print all the abstract orderings as they’re found instead of just counting them, add `if c:print(s.x.round(),y)` before the `for` loop. (Subsets are represented by binary integers where each bit corresponds to the presence or absence of one element: {*a*, *c*, *d*} ↔ 1101₂ = 13.)

### How it works

`f` recursively counts the abstract orderings satisfying a given list of constraints. We start with the constraints *n**a*, *a* \+ *n**b*, *b* \+ *n**c*, *c* \+ *n**d*. Using linear programming, we find a solution to the constraints (or return 0 if there isn’t one)—in this case we get *a* = 4, *b* = 8, *c* = 12, *d* = 16. We round the solution to integers, then compute a reference ordering by sorting all its subsets by their sum:

{*a*}, {*b*}, {*c*}, {*a*, *b*}, {*d*}, {*a*, *c*}, {*a*, *d*}, {*b*, *c*}, {*b*, *d*}, {*a*, *b*, *c*}, {*c*, *d*}, {*a*, *b*, *d*}, {*a*, *c*, *d*}, {*b*, *c*, *d*}, {*a*, *b*, *c*, *d*}

The rounding can’t cause any constraints to be violated by more than *n*/2, which is why we added a margin of *n*.

Since Python’s `sorted` is stable, any ties between the subsets are broken in the same reverse-lexicographic order in which we generated them. So we could imagine replacing {*a*, *b*, *c*, *d*} with {*a*·2^*n* \+ 2^0, *b*·2^*n* \+ 2^1, *c*·2^*n* \+ 2^2, *d*·2^*n* \+ 2^3} to get the same ordering without any ties.

The plan is to categorize all other abstract orderings by case analysis based on where they *first* disagree with the reference ordering:

Either {*a*} \> {*b*},
or {*a*} \< {*b*} \> {*c*},
or {*a*} \< {*b*} \< {*c*} \> {*a*, *b*},
or {*a*} \< {*b*} \< {*c*} \< {*a*, *b*} \> {*d*},

Within each case, we add these new constraints with a margin of *n*, and recursively call `f` with the new constraints added.

### Notes

For a while I conjectured (but did not assume) that the linear program solutions with margin 1 on the constraints will always be integers. This turns out to be false: a counterexample with *n* = 7 is {2.5, 30, 62.5, 73.5, 82, 87.5, 99.5}.

# Python, 606 bytes (faster, no external libraries)

```
n=int(input())
r=range(n)
e=enumerate
def l(u,x):
 for i,v in e(u):
  for j,a in e(v):
   if a<0:break
  else:return[0]*len(x)
  if sum(b*x[k]for k,b in e(v))>0:
   x=l([[b*w[j]-a*w[k]for k,b in e(v)if k!=j]for w in u[:i]],x[:j]+x[j+1:]);x.insert(j,0)
   for k,b in e(v):
    if k!=j:x[j]+=b*x[k];x[k]*=-a
 return x
def f(u,x):
 x=l(u,x);c=any(x);y=sorted(range(c<<n),key=lambda a:sum(x[i]*(a>>i&1)for i in r))
 for a,b in zip(y,y[1:]):
  v=[(a>>i&1)-(b>>i&1)for i in r]+[1]
  if~-(v in u):c+=f(u+[[-z for z in v[:-1]]+[1]],x);u+=v,
 return+c
print(f([[(i==j-1)-(i==j)for i in r]+[1]for j in r],[1]*(n+1)))

```

Try it online!

This runs for *n* = 5 in a quarter of a second, and *n* = 6 in 230 seconds (75 seconds in PyPy).

It includes a hand-coded linear programming solver using integer math in homogeneous coordinates to avoid floating point rounding issues.

# Answer
> 0 votes
# Ruby, 308 bytes, much faster

Runs the case 4 in ~150ms. No specialized library is used.

```
->n{t=2**(n-1)
n==0 ?[[0]]:P[n-1].map{|a|b=a.map{|i|i+t}
[*0..t].repeated_combination(t).select{|m|m[0]>=a.index(n-1)}.map{|m|c,d=a.dup,b.dup;m.reverse.map{|i|c.insert(i,d.pop)};c}}.flatten(1).select{|p|p.combination(2).all?{|(x,y)|x&~y==0||y&~x!=0&&n.times.all?{|i|x!=y<<i+1}&&p.index(x&~y)<p.index(y&~x)}}}

```

It recursively intersperse result of a minor case, for instance

> `[{}, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}]`

with the corresponding subsets with an additional element added - they have to keep the same relative order. It also ensures that the new singleton is added after all the previous singletons.

The part that check for compliance is the same as before, but not the combinations to test are much much less.

Expanded and commented version:

```
->n{
    t=2**(n-1)
    if n==0
        [[0]]
    else
        # for each one of the previous nice orderings
        P[n-1].map { |a|
            # create the missing sets, keep order
            b = a.map{|i|i+t}
            # intersperse the two sets
            [*0..t].repeated_combination(t) # select t insertion points
                .select do |m|
                    # ensure the new singleton is after the old ones
                    m[0] >= a.index(n-1)
                end
                .map do |m|
                    # do the interspersion
                    c,d=a.dup,b.dup
                    m.reverse.map{|i|c.insert(i, d.pop)}
                    c
                end
        }.flatten(1).select{ |p|
            # check if the final ordering is still nice
            p.combination(2).all? { |(x,y)|
                (x&~y==0) ||
                (y&~x!=0) &&
                n.times.all?{|i|x!=y<<i+1} &&
                (p.index(x&~y)<p.index(y&~x))
            }
        }
    end
}

```

# Ruby, 151 bytes, quite slow

(the case of three elements takes \<\< 1s, the case of four is still running)

```
->n{[*1...2**n-1].permutation.select{|p|p.combination(2).all?{|(x,y)|x&~y==0||y&~x!=0&&n.times.all?{|i|x!=y<<i+1}&&p.index(x&~y)<p.index(y&~x)}}.count}

```

It works on bitfield representation of the subsets, so one might have to massage the output if needed to display the subsets themselves.

formatted:

```
-> n {
  [*1...2**n-1]. # prepare permutations of non-empty and non-full sets
    permutation.
    select { |p|
      p.combination(2). # check all ordered pairs
        all? { |(x, y)|
          # first is subset of second
          x &~ y == 0 ||
          # second is not subset of first
          y &~ x != 0 &&
          # first is not a right shift of second
          # (this normalizes the ordering on atoms)
          n.times.all? { |i| x != y << i+1 } &&
          # after taking out common elements, ordering agrees
          p.index(x &~ y) < p.index(y &~ x)
        }
    }.
    count
}

```

---
Tags: code-golf, arithmetic, subsequence
---


title: Black Box Trigonometry

text:
# Question
Title: Black Box Trigonometry
Write a program or function that can distinguish the following 12 trigonometric functions: `sin`, `cos`, `tan`, `asin`, `acos`, `atan`, `sinh`, `cosh`, `tanh`, `asinh`, `acosh`, `atanh`.

Your program is given one of the above functions as black box and should output the function's name either as given above or the way it is named in your language.

This is , so the shortest answer in each language wins. You should show that your code works correctly by including test cases with all 12 possible inputs. If the language of your choice does not include build-ins for all of the above functions, you have to provide your own sensible implementations of the missing ones.

### Further Clarifications

* Using complex numbers to query the black box is allowed if the underlying build-ins can handle them.
* As \\$ dom\ acosh \cap dom\ atanh = \emptyset \\$ when using only real numbers, queries to the black box function can give domain errors. In this case you should assume that the black box only communicates the existence of an error, but not from which function it originates.
* If instead of an error some other value, e.g. `NaN` or `null`, is returned, then your submission should be able to handle them.

---

Thanks for the helpful sandbox feedback!

# Answer
> 22 votes
# Python 3.6.4 on Linux, 99 bytes

Bit of a silly answer, but:

```
lambda f:"asinh acos cos cosh atan atanh tan sin asin tanh sinh acosh".split()[hash(f(.029))%19%12]

```

Requires the trigonometric functions to be one out of the built-in `cmath` module for complex in/output.

# Answer
> 6 votes
# Perl 6, 75 bytes

```
->&f {([X~] ("","a"),<sin cos tan>,("","h")).min({abs(f(2i)-&::($_)(2i))})}

```

Try it online!

As it happens, all twelve of the functions to be discriminated amongst are built-in and all take complex arguments.

`[X~] ("", "a"), <sin cos tan>, ("", "h")` generates all twelve function names by reducing the three input lists with cross-product-concatenation. Given those, `.min(...)` finds the one which the smallest difference from the input function at `2i`.

# Answer
> 6 votes
# C (gcc), ~~178~~ 172 bytes

```
double d;_;f(double(*x)(double)){d=x(0.9247);_=*(int*)&d%12;puts((char*[]){"acosh","sinh","asinh","atanh","tan","cosh","asin","sin","cos","atan","tanh","acos"}[_<0?-_:_]);}

```

Try it online!

# Old but cool: C (gcc), 194 bytes

```
double d;_;f(double(*x)(double)){char n[]="asinhacoshatanh";d=x(0.9247);_=*(int*)&d%12;_=(_<0?-_:_);n[(int[]){10,5,5,0,14,10,4,4,9,14,0,9}[_]]=0;puts(n+(int[]){5,1,0,10,11,6,0,1,6,10,11,5}[_]);}

```

Try it online!

The `-lm` switch in TIO is merely to test. If you could write a *perfect* implementation of the standard trig functions you would get the right answer.

## Explanation

The idea was to find some input value such that when I interpret the outputs of each of the trig functions as integers they have different remainders modulo 12. This will allow them to be used as array indices.

In order to find such an input value I wrote the following snippet:

```
#include <math.h>
#include <stdlib.h>
#include <stdio.h>
#include <time.h>

// Names of trig functions
char *names[12] = {"sin","cos","tan","asin","acos","atan","sinh","cosh","tanh","asinh","acosh","atanh"};

// Pre-computed values of trig functions
double data[12] = {0};

#define ABS(X) ((X) > 0 ? (X) : -(X))

// Performs the "interpret as abs int and modulo by" operation on x and i
int tmod(double x, int i) {
    return ABS((*(int*)&x)%i);
}

// Tests whether m produces unique divisors of each trig function
// If it does, it returns m, otherwise it returns -1
int test(int m) {
    int i,j;
    int h[12] = {0}; // stores the modulos

    // Load the values
    for (i = 0; i < 12; ++i)
        h[i] = tmod(data[i],m);

    // Check for duplicates
    for (i = 0; i < 12; ++i)
        for (j = 0; j < i; ++j)
            if (h[i] == h[j])
                return -1;

    return m;
}

// Prints a nicely formatted table of results
#define TEST(val,i) printf("Value: %9f\n\tsin      \tcos      \ttan      \n  \t%9f\t%9f\t%9f\na \t%9f\t%9f\t%9f\n h\t%9f\t%9f\t%9f\nah\t%9f\t%9f\t%9f\n\n\tsin      \tcos      \ttan      \n  \t%9d\t%9d\t%9d\na \t%9d\t%9d\t%9d\n h\t%9d\t%9d\t%9d\nah\t%9d\t%9d\t%9d\n\n",\
        val,\
        sin(val), cos(val), tan(val), \
        asin(val), acos(val), atan(val),\
        sinh(val), cosh(val), tanh(val),\
        asinh(val), acosh(val), atanh(val),\
        tmod(sin(val),i), tmod(cos(val),i), tmod(tan(val),i), \
        tmod(asin(val),i), tmod(acos(val),i), tmod(atan(val),i),\
        tmod(sinh(val),i), tmod(cosh(val),i), tmod(tanh(val),i),\
        tmod(asinh(val),i), tmod(acosh(val),i), tmod(atanh(val),i))

// Initializes the data array to the trig functions evaluated at val
void initdata(double val) {
    data[0] = sin(val);
    data[1] = cos(val);
    data[2] = tan(val);
    data[3] = asin(val);
    data[4] = acos(val);
    data[5] = atan(val);
    data[6] = sinh(val);
    data[7] = cosh(val);
    data[8] = tanh(val);
    data[9] = asinh(val);
    data[10] = acosh(val);
    data[11] = atanh(val);
}

int main(int argc, char *argv[]) {
    srand(time(0));

    // Loop until we only get 0->11
    for (;;) {
        // Generate a random double near 1.0 but less than it
        // (experimentally this produced good results)
        double val = 1.0 - ((double)(((rand()%1000)+1)))/10000.0;
        initdata(val);
        int i = 0;
        int m;

        // Find the smallest m that works
        do {
            m = test(++i);
        } while (m < 0 && i < 15);

        // We got there!
        if (m == 12) {
            TEST(val,m);
            break;
        }
    }

    return 0;
}

```

If you run that (which needs to be compiled with -lm) it will spit out that with a value of 0.9247 you get unique values.

Next I reinterpeted as integers, applied modulo by 12, and took the absolute value. This gave each function an index. They were (from 0 -\> 11): acosh, sinh, asinh, atanh, tan, cosh, asin, sin, cos, atan, tanh, acos.

Now I could just index into an array of strings, but the names are very long and very similar, so instead I take them out of slices of a string.

To do this I construct the string "asinhacoshatanh" and two arrays. The first array indicates which character in the string to set to the null terminator, while the second indicates which character in the string should be the first one. These arrays contain: 10,5,5,0,14,10,4,4,9,14,0,9 and 5,1,0,10,11,6,0,1,6,10,11,5 respectively.

Finally it was just a matter of implementing the reinterpretation algorithm efficiently in C. Sadly I had to use the double type, and with exactly 3 uses, it was quicker to just use `double` three times then to use `#define D double\nDDD` by just 2 characters. The result is above, a description is below:

```
double d;_;                                 // declare d as a double and _ as an int
f(double(*x)(double)){                      // f takes a function from double to double
    char n[]="asinhacoshatanh";             // n is the string we will manipulate
    int a[]={10,5,5,0,14,10,4,4,9,14,0,9};  // a is the truncation index
    int b[]={5,1,0,10,11,6,0,1,6,10,11,5};  // b is the start index
    d=x(0.9247);                            // d is the value of x at 0.9247
    _=*(int*)&d%12;                         // _ is the remainder of reinterpreting d as an int and dividing by 12
    _=(_<0?-_:_);                           // make _ non-negative
    n[a[_]]=0;                              // truncate the string
    puts(n+b[_]);}                          // print the string starting from the correct location

```

Edit: Unfortunately just using a raw array is actually shorter, so the code becomes much simpler. Nonetheless the string slicing was fun. In theory an appropriate argument might actually come up with the right slices on its own with some math.

# Answer
> 6 votes
# Python 3.6.5 on Linux, ~~90~~ 85 bytes

```
h=hash;lambda f:h(f(.0869))%3%2*"a"+"tscaionns"[h(f(.14864))%3::3]+h(f(.511))%5%2*"h"

```

This builds upon orlp's answer; but instead of finding 1 magic number, we find 3! This basically just saves bytes by avoiding putting the string literals for "sin", "cos", and "tan" multiple times, instead building the answer one part at a time.

The first magic number is used to determine whether it's one of the "arc" trigonometric functions, prepending an "a" accordingly, the second for whether it's one of the "sin", "cos", or "tan" based functions, selecting the appropriate string, and the third for whether it's one of the hyperbolic functions, appending a "h" accordingly.

Like orlp's answer, it uses the functions from Python's built-in `cmath` module as input.

*Saved 5 bytes by using slice indexing into the middle string*

## Finding the Magic Numbers

For completeness, here's (more or less) the script I used to find these magic numbers. I mostly just worked straight in a python terminal, so the code is messy, but it gets the job done.

```
import cmath
fns = [(fn, getattr(cmath, fn)) for fn in ["sin","cos","tan","asin","acos","atan","sinh","cosh","tanh","asinh","acosh","atanh"]]

count_length = lambda num, modulus, base_modulus : len(str(num).rstrip('0').lstrip('0')) + (1 + len(str(modulus)) if modulus != base_modulus else 0)

min_length = float("inf")
min_choice = None
for modulus in range(2,10):
   for i in range(1,100000):
      num = i/100000.
      is_valid = True
      for fn in fns:
         val = hash(fn[1](num))%modulus%2
         if (val == 0 and fn[0][0]=="a") or (val == 1 and fn[0][0]!="a"):
            is_valid = False
      if is_valid:
         length = count_length(num, modulus, 2)
         if length < min_length:
            min_length = length
            min_choice = (modulus,num)
print(min_choice)

min_length = float("inf")
min_choice = None
for modulus in range(3,10):
   for i in range(100000):
      num = i/100000.
      mapping = {}
      is_valid = True
      for fn in fns:
         fn_type = "sin" if "sin" in fn[0] else "cos" if "cos" in fn[0] else "tan"
         val = hash(fn[1](num))%modulus%3
         if val in mapping and mapping[val] != fn_type:
            is_valid = False
            break
         mapping[val] = fn_type
      if is_valid:
         length = count_length(num, modulus, 3)
         if length < min_length:
            min_length = length
            min_choice = (modulus, num, mapping)
print(min_choice)

min_length = float("inf")
min_choice = None
for modulus in range(2,10):
   for i in range(1,100000):
      num = i/100000.
      is_valid = True
      for fn in fns:
         val = hash(fn[1](num))%modulus%2
         if (val == 0 and fn[0][-1]=="a") or (val == 1 and fn[0][-1]!="a"):
            is_valid = False
      if is_valid:
         length = count_length(num, modulus, 2)
         if length < min_length:
            min_length = length
            min_choice = (modulus,num)
print(min_choice)

```

# Answer
> 5 votes
# Python, ~~108~~ ~~94~~ 90 bytes

Compares the result of the input function to the results of all of the functions for the value `.2`.

```
from cmath import*
lambda f:[w for w in globals()if w[-1]in'shn'and eval(w)(.2)==f(.2)][0]

```

**Try it online**

*-14 bytes by Jonathan Allen*
*-4 bytes by Rod*

# Answer
> 4 votes
# Dyalog APL, ~~25~~ ~~21~~ 19 bytes

```
(8-(2○⍨8-⍳15)⍳⎕2)∘○

```

Try it online!

-3 thanks to H.PWiz
-2 thanks to ngn

Goes trough all the required trig functions (which in APL are `1 2 3 5 6 7 ¯1 ¯2 ¯3 ¯5 ¯6 ¯7○2`) plus some more things (this goes trough `-7..7`), finds which one matches `input○2`, and outputs that "with" , which outputs as `num∘○`

# Answer
> 3 votes
# JavaScript, ~~76~~ ~~67~~ 66 bytes

Not pretty but I went far too far down the rabbit hole with this over a few beers to *not* post it. Derived independently from Nit's solution.

```
b=>Object.getOwnPropertyNames(M=Math).find(x=>M[x](.8)+M==b(.8)+M)

```

Try it online

* Saved 6 bytes thanks to Neil
* Saved 1 bye thanks to l4m2

# Answer
> 3 votes
# C (gcc) with `-lm`, ~~374~~ ~~346~~ ~~324~~ 310 bytes

Thanks to Giacomo Garabello and ceilingcat for the suggestions.

I was able to save a bit more space by having a helper macro do token-pasting in addition to my original macro which does stringizing.

In the tests, I used a couple of non-library trig functions to confirm the validity of the results. As the results between the library and non-library functions weren't *exactly* the same floating-point value, I compared the difference of the results against a small value ε instead of using equality.

```
#import<math.h>
#define q(f)f,#f,
#define _(f,g)q(f##sin##g)q(f##cos##g)q(f##tan##g)
#define p for(i=0;i<24;i+=2)!j[i]
typedef double(*z)(double);*y[]={_(,)_(a,)_(,h)_(a,h)};i,x;*f(z g){int j[24]={x=0};char*c;for(double w;x++<9;)p&isnan(w=((z)y[i])(x))-isnan(g(x))|fabs(w-g(x))>1E-9?j[i]=1:0;p?c=y[i+1]:0;g=c;}

```

Try it online!

# Answer
> 2 votes
# JavaScript, ~~108~~ 70 bytes

I haven't tried golfing in pure Javascript in ages, so I'm sure there's stuff to improve here.

```
t=>Object.getOwnPropertyNames(m=Math).find(f=>m[f](.9,0)+''==t(.9)+'')

```

Pretty straightforward, checks every function on the `Math` prototype against an arbitrary value (0.9, many other values probably work) and compares with the result of the black box function.
Tested in Google Chrome, will break if the input black box function is not one of the trigs.

Cut off a ton of bytes thanks to Shaggy and Neil.

```
const answer = t=>Object.getOwnPropertyNames(m=Math).find(f=>m[f](.9,0)+''==t(.9)+'');
const tests = [Math.sin, Math.cos, Math.tan, Math.asin, Math.acos, Math.atan, Math.sinh, Math.cosh, Math.tanh, Math.asinh, Math.acosh, Math.atanh];

tests.forEach(test => console.log(test + ' yields ' + answer(test)));
```

# Answer
> 2 votes
# Wolfram Language (Mathematica), 86 bytes

```
#&@@Nearest[a=Join[a={Sin,Cos,Tan,Sinh,Cosh,Tanh},InverseFunction/@a];#@2&/@a->a,#@2]&

```

Try it online!

# Answer
> 2 votes
# Ruby, ~~71~~ 67 bytes

```
->g{Math.methods.find{|h|g[0.5]==Math.send(h,0.5)rescue p}||:acosh}

```

Try it online!

# Answer
> 2 votes
# , 73 bytes

```
function(b)Find(function(x)get(x)(1i)==b(1i),apropos('(sin|cos|tan)h?$'))

```

Try it online!

For the moment (R v3.5) it works.
If in a future R version it will be added a function matching this regex, then who knows :P

* -4 bytes thanks to @Giuseppe
* -9 bytes thanks to @JayCe
* -2 bytes using `Find` instead of `for`

# Answer
> 2 votes
# Perl 6, 39 bytes

```
{i.^methods.first({try $^a.(i)==.(i)})}

```

Try it online!

By the looks of things, one of the few to use introspection. `i` here is the complex number, whose value is unique for each trig function, so by iterating through all the methods we can find the matching method and implicitly spit out its name. The `try` is needed as some (unwanted) methods have the a different signature.

# Answer
> 1 votes
# HP 49G RPL, 88.0 bytes excluding 10 byte program header

Another solution using complex numbers! Enter and execute it in COMPLEX, APPROX mode. Takes the function on the stack.

```
2. SWAP EVAL { SIN COS TAN ASIN ACOS ATAN SINH COSH TANH ASINH ACOSH ATANH }
DUP 1. << 2. SWAP EVAL >> DOLIST ROT - ABS 0. POS GET

```

(the newlines don't matter)

For the constant 2.0, all twelve trig functions are defined in the complex plane, so we just evaluate all twelve and see which one matches. This time, the iterative solution is longer (111.5 bytes) because of the stack shuffling needed to get it. RPL, as far as I know, doesn't let you break out of a loop early.

# Answer
> 0 votes
# JavaScript (Node.js), 72 bytes

```
f=>eval('for(s=i=0;!s||s(.8)+s!=f(.8)+s;i++)s=Math[t=i.toString(30)];t')

```

Try it online!

---
Tags: code-golf, function, trigonometry
---


title: Hello world that handles errors

text:
# Question
Title: Hello world that handles errors
Write a program or function with the following functionality:

* The program/function first attempts to write the string `Hello, world!` to the standard output stream. (No other forms of output are acceptable for this challenge, as the focus is very much on the I/O rather than the trivial behaviour of the program itself.) Depending on whether it succeeded:
    + If it succeeded in outputting `Hello, world!`, the program/function exits without any further behaviour.
    + If it failed to produce the correct output due to an error, the program/function attempts to write the string `Error writing "Hello, world!"` to the standard error stream. (For the purposes of this challenge, you don't need error handling for the error handling itself.)

## Clarifications

* Your program/function will be run with no input (unless it's written in a language which absolutely requires input to work, in which case it will be run with the simplest possible input).
* When producing output, you may also produce a single trailing newline if you wish, but doing so is not mandatory.
* The definition of "error writing to standard output" that your program implements must treat at least the following cases as errors:

+ Standard output being nonexistent (i.e. `stdout` is a closed filehandle, no file descriptor 1 exists, or however those cases translate to the language and OS you're using);
    + Standard output referring to a file on a disk that has no free space left;
    + Standard output connecting to another program, which has already closed its end of the connection.

and must treat at least the following cases as success (i.e. not an error):

+ Standard output connects to a terminal, and `Hello, world!` is displayed onscreen.
    + Standard output connects to a file, and `Hello, world!` is written into the file.

You can choose the details of what counts as an output error, so long as it's consistent with the above rules.
* Your program/function should not crash upon encountering any of the error situations listed above. It's up to you what exit code you use.
* Your program/function should not describe the nature of the encountered error on the standard error stream; it should just print the string specified above. Extraneous output on standard error (e.g. compiler warnings) is only legal if it's produced unconditionally, regardless of whether an error is encountered or not.
* Your program only needs to work on one operating system (although it must be one on which the errors listed above make sense; I've tried to keep them general enough to work on most multitasking consumer operating systems, but weirder operating systems may well be excluded from this challenge). If your program is nonportable, list the assumptions it needs to run in the title of your submission.
* This task may not be possible in every language (not every language allows a program to handle output errors in a custom way). You'll have to pick a language where it is possible.
* Make sure that your program/function works! Don't just trust the documentation of library functions to do what they say they do. The error handling of simple output functions often turns out to be broken in practice, even if the functions claim to handle errors in theory.

## Test cases

Here's a way to simulate each of the error conditions above using `bash` on Linux (you don't have to use Linux, but it's likely the easiest system to test this on):

```
your_program_here >&-           # nonexistent stdout
your_program_here > /dev/full   # out of disk space
mkfifo test  # note: change "test" to a filename that isn't in use
true < test &
your_program_here > test        # connecting to a program that doesn't want input
rm test      # clean up the FIFO we used earlier

```

The first two testcases are deterministic. The last isn't (it relies on a race condition); for testing purposes, I recommend adding a delay between the start of your program and the actual output to standard output, in order to ensure that the race condition is resolved in the way that exposes the error.

## Victory condition

This is a challenge, so shorter is better. As (nearly) always, we're measuring the length of the program in bytes.

# Answer
> 6 votes
# Bash, ~~71~~ 60 bytes

```
h=Hello,\ world!
(echo $h)2>&-||echo Error writing \"$h\">&2

```

Try it online!

### How it works

After saving `Hello, world!` to the variable **h**, we do the following.

First, `(echo $h)2>&-` attempts to print `Hello, world!` to STDOUT. `2>&-` is required to prevent displaying the error message *echo: write error: Bad file descriptor* in case the write fails. Since writing to a named pipe that doesn't accept input would kill the Bash program with signal 13 (SIGPIPE), we execute the command in a subshell (`(...)`), so only the subshell will get killed.

Finally, if printing to STDOUT failed, the subshell will exit with a non-zero status code (141 for SIGPIPE, 1 for a generic error), so `echo Error writing \"$h\">&2` prints the desired message to STDERR.

# Answer
> 2 votes
# Python 2, 65 bytes

```
h='Hello, world!'
try:print h
except:exit('Error writing "%s"'%h)

```

Two bytes could be saved by printing single quotes.

Try it online!

# Answer
> 1 votes
# Zsh, 55 bytes

```
h=Hello,\ world!
2>&-<<<$h||<<<'Error writing "'$h\">&2

```

Unlike its cousin Bash, Zsh refuses to die because of a broken pipe.

Try it online!

# Answer
> 1 votes
# PowerShell, 80 Bytes

```
try{echo($h="Hello, World!") -ea 4}catch{$host.ui|% *rL* "Error writing ""$h"""}

```

explained:

```
try{
    #Attempt to 'echo' (write output) the string, and assign it to $h
    #Make sure the 'error action' is set to '4' to make it a terminating error.
    echo($h="Hello, World!") -ea 4
} catch {
    #Use the "WriteErrorLine" function in $host.ui to stderr
    $host.ui|% *rL* "Error writing ""$h"""
}

```

haven't managed to actually try this when it errors, but it definitely ~should~ work.

# Answer
> 1 votes
# C (gcc), ~~87~~ 86 bytes

```
f(){signal(13,1);write(1-puts("Hello, world!"),"Error writing \"Hello, world!\"",29);}

```

Try it online!

### Ungolfed

```
#include <signal.h>
#include <stdio.h>
#include <unistd.h>

void f(void)
{
    signal(SIGPIPE, SIG_IGN); // Works (and is required) on TIO. YMMV
    int fd = (puts("Hello, world!")) < 0 ? 2 : -13;
    write(fd, "Error writing \"Hello, world!\"", 29);
}

```

# Answer
> 0 votes
# Perl 5, 51 bytes

requires `-M5.01`, which is free

```
say$h="Hello, world!"or die"Error writing \"$h\"$/"

```

Tested in Strawberry Perl 5.24.0 by running the program as-is (printed to standard output) and by running

```
print f $h="Hello, world!"or die"Error writing \"$h\"$/"

```

(printed to standard error). I don't know how to test for other errors using Strawberry, but they *should* be handled the same….

# Answer
> 0 votes
# Javascript, ~~79~~ 76 bytes

```
try{(l=console).log(a="Hello, world!")}catch(e){l.error('Error writing '+a)}

```

# Answer
> 0 votes
## REXX, ~~111~~ 106 bytes

```
signal on notready
a='Hello, world!'
_=lineout(,a)
exit
notready:_=lineout('stderr','Error writing "'a'"')

```

The program relies on there being a stream called 'stderr'. This will probably not be the case on IBM systems.

# Answer
> 0 votes
**C, 77 bytes**

```
f(a){a="Error writing \"Hello, world!\"";write(1,a+15,13)-13&&write(2,a,29);}

```

for call

```
main(){f(1); return 0;}

```

# Answer
> 0 votes
# , 91 bytes

```
s="Hello, world!"
tryCatch(cat(s),error=function(e)cat('Error writing "','"',file=2,sep=s))

```

Try it online!

I tried erroring it by running it with `cat(s,file=12)` instead of `cat(s)`, and it prints the correct text to stderr. This is an `invalid connection` error otherwise.

---
Tags: code-golf, hello-world, file-system
---


title: Existential Golf

text:
# Question
Title: Existential Golf
Math has a lot of symbols. Some might say too many symbols. So lets do some math with pictures.

Lets have a paper, which we will draw on. To start the paper is empty, we will say that is equivalent to \\$\top\\$ or \\$\textit{true}\\$.

If we write other things on the paper they will also be true.

For example

Indicates that the claims \\$P\\$ and \\$Q\\$ are true.

Now let us say that if we draw a circle around some statement that statement is false. This represents logical not.

For example:

Indicates that \\$P\\$ is false and \\$Q\\$ is true.

We can even place the circle around multiple sub-statements:

Since the part inside the circle normally reads as \\$P\text{ and }Q\\$ by putting a circle around it it means \\$\text{not }(P\text{ and }Q)\\$. We can even nest circles

This reads as \\$\text{not }((\text{not }P)\text{ and }Q)\\$.

If we draw a circle with nothing in it, that represents \\$\bot\\$ or \\$\textit{false}\\$.

Since empty space was true, then the negation of true is false.

Now using this simple visual method we can actually represent any statement in propositional logic.

# Proofs

The next step after being able to represent statements is being able to prove them. For proofs we have 4 different rules that can be used to transform a graph. We always start with an empty sheet which as we know is a vacuous truth and then use these different rules to transform our empty sheet of paper into a theorem.

Our first inference rule is *Insertion*.

### Insertion

We will call the number of negations between a sub-graph and the top level it's "depth". *Insertion* allows us to introduce any statement we wish at an odd depth.

Here is an example of us performing insertion:

Here we chose \\$P\\$, but we could just as well choose any statement we wanted.

### Erasure

The next inference rule is *Erasure*. *Erasure* tells us that if we have a statement that is at a even depth we can remove it entirely.

Here is an example of erasure being applied:

Here we erased the \\$Q\\$, because it was \\$2\\$ levels nested. Even if we wanted to we could not have erased \\$P\\$ because it is \\$1\\$ level nested.

### Double Cut

*Double Cut* is an equivalence. Which means, unlike the previous inferences it can also be reversed. *Double Cut* tells us that we can draw two circles around any sub-graph, and if there are two circles around a sub-graph we can remove them both.

Here is an example of the *Double Cut* being used

Here we use *Double Cut* on \\$Q\\$.

### Iteration

*Iteration* is a equivalence as well.1 It's reverse is called *Deiteration* If we have a statement and a cut on the same level, we can copy that statement inside of a cut.

For example:

*Deiteration* allows us to reverse an *Iteration*. A statement can be removed via *Deiteration* if there exists a copy of it at the next level up.

---

This format of representation and proof is not of my own invention. They are a minor modification of a diagrammatic logic are called Alpha Existential Graphs. If you want to read more on this, there is not a ton of literature, but the linked article is a good start.

---

# Task

Your task will be to prove the following theorem:

This, when translated into traditional logic symbolization is

\\$((A\to(B\to A))\to(((\neg C\to(D\to\neg E))\to((C\to(D\to F))\to((E\to D)\to(E\to F))))\to G))\to(H\to G)\\$.

Also known as the Łukasiewicz-Tarski Axiom.

It may seem involved but existential graphs are *very* efficient when it comes to proof length. I selected this theorem because I do think it is an appropriate length for a fun and challenging puzzle. If you are having trouble with this one I would recommend trying some more basic theorems first to get the hang of the system. A list of these can be found at the bottom of the post.

This is so your score will be the total number of steps in your proof from start to finish. The goal is to minimize your score.

# Format

The format for this challenge is flexible you can submit answers in any format that is clearly readable, including hand-drawn or rendered formats. However for clarity I suggest the following simple format:

* We represent a cut with parentheses, whatever we are cutting is put inside of the parens. The empty cut would just be `()` for example.
* We represent atoms with just their letters.

As an example here is the goal statement in this format:

```
(((A((B(A))))(((((C)((D((E)))))(((C((D(F))))(((E(D))((E(F))))))))(G))))((H(G))))

```

This format is nice because it is both human and machine readable, so including it in your post would be nice.

If you want some nice(ish) diagrams here is some code that converts this format to \\$\LaTeX\\$:

Try it online!

As for your actual work I recommend pencil and paper when working out. I find that text just isn't as intuitive as paper when it comes to existential graphs.

# Example proof

In this example proof we will prove the following theorem:

Now this may seem alien to you at first but if we translate this into traditional logic notation we get \\$(A\rightarrow B)\rightarrow(\neg B\rightarrow \neg A)\\$, also known as the law of contra-positives.

**Proof:**

# Practice Theorems

Here are some simple theorems you can use to practice the system:

### Łukasiewicz' Second Axiom

### Meredith's Axiom

1: Most sources use a more sophisticated and powerful version of *Iteration*, but to keep this challenge simple I am using this version. They are functionally equivalent.

# Answer
# 19 steps

1. `(())` \[double cut\]
2. `(AB()(((G))))` \[insertion\]
3. `(AB(A)(((G))))` \[iteration\]
4. `(((AB(A)))(((G))))` \[double cut\]
5. `(((AB(A))(((G))))(((G))))` \[iteration\]
6. `(((AB(A))(((G))))((H(G))))` \[insertion\]
7. `(((AB(A))(((G)(()))))((H(G))))` \[double cut\]
8. `(((AB(A))(((DE()(C)(F))(G))))((H(G))))` \[insertion\]
9. `(((AB(A))(((DE(C)(DE(C))(F))(G))))((H(G))))` \[iteration\]
10. `(((AB(A))(((DE(CD(F))(DE(C))(F))(G))))((H(G))))` \[iteration\]
11. `(((AB(A))(((E(CD(F))(DE(C))(F)((D)))(G))))((H(G))))` \[double cut\]
12. `(((AB(A))(((E(CD(F))(DE(C))(E(D))(F))(G))))((H(G))))` \[iteration\]
13. `(((AB(A))(((G)((CD(F))(DE(C))(E(D))((E(F)))))))((H(G))))` \[double cut\]
14. `(((AB(A))(((G)((CD(F))(DE(C))(((E(D))((E(F)))))))))((H(G))))` \[double cut\]
15. `(((AB(A))(((G)((C((D(F))))(DE(C))(((E(D))((E(F)))))))))((H(G))))` \[double cut\]
16. `(((AB(A))(((G)((DE(C))(((C((D(F))))(((E(D))((E(F)))))))))))((H(G))))` \[double cut\]
17. `(((AB(A))(((G)((D(C)((E)))(((C((D(F))))(((E(D))((E(F)))))))))))((H(G))))` \[double cut\]
18. `(((AB(A))(((G)(((C)((D((E)))))(((C((D(F))))(((E(D))((E(F)))))))))))((H(G))))` \[double cut\]
19. `(((A((B(A))))(((G)(((C)((D((E)))))(((C((D(F))))(((E(D))((E(F)))))))))))((H(G))))` \[double cut\]

# Practice theorems

### Łukasiewicz’ second axiom: 7 steps

1. `(())` \[double cut\]
2. `(A()(B)(C))` \[insertion\]
3. `(A(A(B))(B)(C))` \[iteration\]
4. `(A(AB(C))(A(B))(C))` \[iteration\]
5. `((AB(C))(A(B))((A(C))))` \[double cut\]
6. `((AB(C))(((A(B))((A(C))))))` \[double cut\]
7. `((A((B(C))))(((A(B))((A(C))))))` \[double cut\]

### Meredith’s axiom: 11 steps

1. `(())` \[double cut\]
2. `(()(D(A)(E)))` \[insertion\]
3. `((D(A)(E))((D(A)(E))))` \[iteration\]
4. `((D(A)(E))((D(A)(E(A)))))` \[iteration\]
5. `((D(A)(E))(((E(A))((D(A))))))` \[double cut\]
6. `(((E)((D(A))))(((E(A))((D(A))))))` \[double cut\]
7. `(((E)((C)(D(A))))(((E(A))((D(A))))))` \[insertion\]
8. `(((E)((C)(D(A)(C))))(((E(A))((D(A))))))` \[iteration\]
9. `(((E)((C)((A)(C)((D)))))(((E(A))((D(A))))))` \[double cut\]
10. `(((E)((C)((A)(((C)((D)))))))(((E(A))((D(A))))))` \[double cut\]
11. `(((E)((C)((A(B))(((C)((D)))))))(((E(A))((D(A))))))` \[insertion\]

# Haskell proof searcher

(What, you thought I was going to do that by hand? :-P)

This only tries insertion, double cut introduction, and iteration. So it’s still possible these solutions could be beaten using erasure, double cut elimination, or deiteration.

```
{-# LANGUAGE ViewPatterns #-}

import Control.Applicative hiding (many)
import Data.Char
import Data.Function hiding ((&))
import qualified Data.Map as M
import Data.Maybe
import qualified Data.MultiSet as S
import qualified Data.PQueue.Prio.Min as Q
import System.IO
import Text.ParserCombinators.ReadP

type Var = Char

data Part
  = Var Var
  | Not Conj
  deriving (Eq, Ord)

instance Show Part where
  show (Var s) = [s]
  show (Not c) = "(" ++ show c ++ ")"

newtype Conj = Conj
  { parts :: S.MultiSet Part
  } deriving (Eq, Ord)

instance Show Conj where
  show (Conj (S.toAscList -> [])) = ""
  show (Conj (S.toAscList -> g:gs)) =
    show g ++ concat ["" ++ show g1 | g1 <- gs]

true :: Conj
true = Conj S.empty

not_ :: Conj -> Conj
not_ = Conj . S.singleton . Not

(&) :: Conj -> Conj -> Conj
Conj as & Conj bs = Conj (S.union as bs)

intersect :: Conj -> Conj -> Conj
intersect (Conj as) (Conj bs) = Conj (S.intersection as bs)

diff :: Conj -> Conj -> Conj
diff (Conj as) (Conj bs) = Conj (S.difference as bs)

splits :: Conj -> [(Conj, Conj)]
splits =
  S.foldOccur
    (\a o bcs ->
       [ (Conj (S.insertMany a o1 bs), Conj (S.insertMany a (o - o1) cs))
       | (Conj bs, Conj cs) <- bcs
       , o1 <- [0 .. o]
       ])
    [(true, true)] .
  parts

moves :: Bool -> Conj -> [(Conj, String)]
moves ev a =
  (do (b, c) <- splits a
      andMoves ev b c) ++
  (do (p, _) <- S.toOccurList (parts a)
      partMoves ev p (Conj (S.delete p (parts a))))

andMoves :: Bool -> Conj -> Conj -> [(Conj, String)]
andMoves ev a b = [(a, "insertion") | not ev]

partMoves :: Bool -> Part -> Conj -> [(Conj, String)]
partMoves ev (Not a) b =
  [(a1 & b, why) | (a1, why) <- notMoves ev a] ++
  [ (not_ (diff a d) & b, "iteration")
  | (d, _) <- splits (intersect a b)
  , d /= true
  ]
partMoves _ (Var _) _ = []

notMoves :: Bool -> Conj -> [(Conj, String)]
notMoves ev a =
  (case S.toList (parts a) of
     [Not b] -> [(b, "double cut")]
     _ -> []) ++
  [(not_ a1, why) | (a1, why) <- moves (not ev) a]

partSat :: Part -> Bool -> M.Map Var Bool -> [M.Map Var Bool]
partSat (Var var) b m =
  case M.lookup var m of
    Nothing -> [M.insert var b m]
    Just b1 -> [m | b1 == b]
partSat (Not c) b m = conjSat c (not b) m

conjSat :: Conj -> Bool -> M.Map Var Bool -> [M.Map Var Bool]
conjSat c False m = do
  (p, _) <- S.toOccurList (parts c)
  partSat p False m
conjSat c True m = S.foldOccur (\p _ -> (partSat p True =<<)) [m] (parts c)

readConj :: ReadP Conj
readConj = Conj . S.fromList <$> many readPart

readPart :: ReadP Part
readPart =
  Var <$> satisfy isAlphaNum <|> Not <$> (char '(' *> readConj <* char ')')

parse :: String -> Maybe Conj
parse s = listToMaybe [c | (c, "") <- readP_to_S readConj s]

partSize :: Part -> Int
partSize (Var _) = 1
partSize (Not c) = 1 + conjSize c

conjSize :: Conj -> Int
conjSize c = sum [partSize p * o | (p, o) <- S.toOccurList (parts c)]

data Pri = Pri
  { dist :: Int
  , size :: Int
  } deriving (Eq, Show)

instance Ord Pri where
  compare = compare `on` \(Pri d s) -> (s + d, d)

search ::
     Q.MinPQueue Pri (Conj, [(Conj, String)])
  -> M.Map Conj Int
  -> [[(Conj, String)]]
search (Q.minViewWithKey -> Nothing) _ = []
search (Q.minViewWithKey -> Just ((pri, (a, proof)), q)) m =
  [proof | a == true] ++
  uncurry search (foldr (addMove pri a proof) (q, m) (moves True a))

addMove ::
     Pri
  -> Conj
  -> [(Conj, String)]
  -> (Conj, String)
  -> (Q.MinPQueue Pri (Conj, [(Conj, String)]), M.Map Conj Int)
  -> (Q.MinPQueue Pri (Conj, [(Conj, String)]), M.Map Conj Int)
addMove pri b proof (a, why) (q, m) =
  case M.lookup a m of
    Just d
      | d <= d1 -> (q, m)
    _
      | null (conjSat a False M.empty) ->
        ( Q.insert (Pri d1 (conjSize a)) (a, (b, why) : proof) q
        , M.insert a d1 m)
    _ -> (q, m)
  where
    d1 = dist pri + 1

prove :: Conj -> [[(Conj, String)]]
prove c = search (Q.singleton (Pri 0 (conjSize c)) (c, [])) (M.singleton c 0)

printProof :: [(Conj, String)] -> IO ()
printProof proof = do
  mapM_
    (\(i, (a, why)) ->
       putStrLn (show i ++ ". `" ++ show a ++ "`  [" ++ why ++ "]"))
    (zip [1 ..] proof)
  putStrLn ""
  hFlush stdout

main :: IO ()
main = do
  Just theorem <- parse <$> getLine
  mapM_ printProof (prove theorem)

```
> 8 votes

# Answer
# 22 Steps

\\$\to\\$`(((())(())))` \[Double Cut x3\]

\\$\to\\$`(((AB())(CDE(F)()))H(G))` \[Insertion x3\]

\\$\to\\$`(((AB(A))(CDE(F)(CD(F)))(G))H(G))` \[Iteration x3\]

\\$\to\\$`(((A((B(A))))(((((C))DE(F)(C((D(F)))))(G))))((H(G))))` \[Double Cut x5\]

\\$\to\\$`(((A((B(A))))(((((C)DE)DE(F)(C((D(F)))))(G))))((H(G))))` \[Iteration\]

\\$\to\\$`(((A((B(A))))(((((C)((D((E)))))((((((D))E(F)))(C((D(F)))))))(G))))((H(G))))` \[Double Cut x5\]

\\$\to\\$`(((A((B(A))))(((((C)((D((E)))))((((((D)E)E(F)))(C((D(F)))))))(G))))((H(G))))` \[Iteration\]

\\$\to\\$`(((A((B(A))))(((((C)((D((E)))))((((((D)E)((E(F)))))(C((D(F)))))(G))))))((H(G))))` \[Double Cut\]

---

A few things I learned from completing this puzzle:

* Reduce the provided representation. This involves reversing double cuts and iterations. For example, this axiom reduces to `(((AB(A))(((C)DE)(CD(F))(E(D))(E(F)))(G))H(G))` after reversing double cuts, and `(((AB(A))(()CDE(F)))H(G)))` after reversing iterations.
* Look for stray atoms. For example, H is used as a dummy variable, and thus can be inserted at any point.

---

# Practice Theorem Solutions:

**Solution for Łukasiewicz' Second Axiom:** \[8 Steps\]

\\$\to\\$`(())` \[Double Cut\]

\\$\to\\$`(()AB(C))` \[Insertion\]

\\$\to\\$`((AB(C))AB(C))` \[Iteration\]

\\$\to\\$`((A((B(C))))A((B))(C))` \[Double Cut x2\]

\\$\to\\$`((A((B(C))))A(A(B))(C))` \[Iteration\]

\\$\to\\$`((A((B(C))))(((A(B))((A(C))))))` \[Double Cut x2\]

**Solution for Meredith's Axiom:** \[12 Steps\]

\\$\to\\$`(())` \[Double Cut\]

\\$\to\\$`(()(A)D(E))` \[Insertion\]

\\$\to\\$`(((A)D(E))(A)D(E(A)))` \[Iteration x2\]

\\$\to\\$`(((((A)D))(E))(A)D(E(A)))` \[Double Cut\]

\\$\to\\$`(((((A(B))D)(C))(E))(A)D(E(A)))` \[Insertion x2\]

\\$\to\\$`(((((A(B))(C)D)(C))(E))(A)D(E(A)))` \[Iteration\]

\\$\to\\$`(((((A(B))(((C)((D)))))(C))(E))(((((A)D))(E(A)))))` \[Double Cut x4\]
> 4 votes

---
Tags: math, logic, proof-golf
---


title: Stacked digit staircases

text:
# Question
Title: Stacked digit staircases
Given positive integers \\$w\\$ and \\$h\\$ output \\$w\\$ columns and \\$h\\$ rows of text as described below.

The first row begins with 11 `0`s, the second row with 10 `1`s, third with nine `2`s and so on down the the tenth row with two `9`s. On each of these first ten rows, following the initial run of consecutive digits, the next lowest digit appears two times before the second next lowest digit appears two times, with this pattern repeating forever. If a run of `0`s occurs, the digits after it are always `9`s.

Rows below the tenth row are the same as the row immediately above it but shifted to the right by one. The new digit that appears is the same as the previous leftmost digit if it was not next to another instance of itself. Otherwise it is the next highest digit (cycling from 9 back to 0).

The first \\$11\times10\\$ elements are as follows:

```
00000000000
11111111110
22222222211
33333333221
44444443322
55555544332
66666554433
77776655443
88877665544
99887766554

```

Here is an image with colored text to make the pattern more clear.

If you need to produce fewer columns/rows then you should simply crop the above text.

If you need to produce more columns/rows than this, existing staircases should be extended. If more columns/rows adds new staircases of consecutive digits, digits should be cyclicly chosen from the integers. Thus for input \\$(15,13)\\$ the output should be

```
000000000009988
111111111100998
222222222110099
333333332211009
444444433221100
555555443322110
666665544332211
777766554433221
888776655443322
998877665544332
099887766554433
009988776655443
100998877665544

```

Here is an image of this text with color:

### Rules

* Output can be given by any convenient method.
* Either a full program or a function are acceptable. If a function, you can return the output rather than printing it.
* You can return a list of lines if you prefer.
* You can return a 2D array of digits or list of lists of digits if you prefer.
* Standard loopholes disallowed.

Shortest code wins.

### Test cases

Input is taken as \\$(w,h)\\$ for the test cases.

```
1,1
0

3,2
000
111

20,1
00000000000998877665

11,10
00000000000
11111111110
22222222211
33333333221
44444443322
55555544332
66666554433
77776655443
88877665544
99887766554

15,13
000000000009988
111111111100998
222222222110099
333333332211009
444444433221100
555555443322110
666665544332211
777766554433221
888776655443322
998877665544332
099887766554433
009988776655443
100998877665544

```

# Answer
# C (gcc), ~~101~~ ~~100~~ 99 bytes

```
s,t;a(i,r){for(t=~0;++t<r;puts(""))for(s=0;s<i;putchar(48+(t+(s>10-t)*(10*s+9-(s+++t-11)/2))%10));}

```

Try it online!
> 7 votes

# Answer
# Python 3, ~~94~~ ~~93~~ ~~78~~ ~~77~~ 74 bytes

```
lambda x,y:[[[(j-i+10)//2%10,j][j+i<9]for i in range(x)]for j in range(y)]
```

-1 byte from dylnan

-15 bytes by returning a list of lists instead of printing from xnor

-1 byte by switching the order of the `(j-i+10)//2%10` and `j` parts of the `if`-`else`

-3 bytes from Jo King by changing the `if`-`else` to a list.

Try it online!
> 7 votes

# Answer
# Charcoal, ~~20~~ 17 bytes

```
Ｅη⭆θ﹪⌊⟦ι÷⁺⁻ιλχ²⟧χ

```

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

```
 η                  Height
Ｅ                   Map over implicit range
   θ                Width
  ⭆                 Map over implicit range and join
          ⁻ιλ       Subtract column from row
         ⁺   χ      Add 10
        ÷     ²     Integer divide by 2
       ι            Current row
     ⌊⟦        ⟧    Take the minimum
    ﹪           χ   Modulo by 10
                    Implicitly print each row on its own line

```

Edit: Saved 3 bytes by switching to @dzaima's algorithm.
> 2 votes

# Answer
# Jelly, 19 bytes

Uses a very similar approach to pizzapants' and Neil's. Saved 1 byte thanks to Jonathan Allan.

```
p’Ḣ_/HḞ+ʋS<9Ɗ?€5s%⁵

```

Try it online!

---

**The helper link**

```
_/HḞ+5

```

This is a monadic link (the Jelly equivalent of a single argument function), that can be invoked from the next link using the quick `Ç`. It takes a list of two integers and does the following on it:

```
_/

```

Reduce by subtraction.

```
HḞ+5%⁵

```

Floor its halve to an integer and add 5, then take it modulo 10.

**The main link**

```
p’ḢÇS<9Ɗ?€s

```

This is a dyadic link (the Jelly equivalent of a two-argument function), that can be invoked from the next link using the `ç` quick. It takes two integers \\$x\\$ and \\$y\\$ and performs the following:

```
p’

```

Cartesian product of their ranges, and then subtract \\$1\\$ from each integer in that list. It is equivalent to \\$(\[0, x)\cap \mathbb{Z}) \times (\[0, y)\cap \mathbb{Z})\\$.

```
S<9Ɗ?€

```

And for each of the pair in the Cartesian product, if their sum is less than 9, then:

Retrieve the head of the pair (first element). Otherwise,

```
Ç

```

Call the helper link (explained above) on the pair.

```
s%⁵

```

Finally, split the resulting list into chunks of length \\$y\\$ and take each mod 10.
> 2 votes

# Answer
# Canvas, 14 bytes

```
［⁷｛¹∔⁶＋»¹ｍ◂＠］］

```

Try it here!

While making this I noticed in several places I had negative modulos in Canvas (here, it meant that `»` \- floor div 2 - rounded towards 0). The previous 18 byte answer that worked without fixes doesn't work anymore (because I only save `main.js` between versions) but TIO still has the old version

Explanation:

```
[            ]  for 1..input
 ⁷{         ]     for 1..2nd input
   ¹∔               subtract from this loop counter the outer loops one
     ⁶+             add 12
       »            divide by 2, rounded to -∞
        ¹m          minimum of that & the outer loops counter
          ◂@        in the string "0123456789", get the xth char, 1-indexed

```
> 2 votes

# Answer
# Jelly, 14 bytes

```
_@þ:2+6«"J$’%⁵

```

A dyadic link taking \\$w\\$ on the left and \\$h\\$ on the right which yields a list of lists of digits.

**Try it online!** Or see a (post-formatted) test-suite.

### How?

```
_@þ:2+6«"J$’%⁵ - Link: integer w, integer h
  þ            - outer product using (i.e. [[f(i,j) for i in 1..w] for j in 1..h]):
_@             -   subtraction with swapped arguments (i.e. f(i,j): j-i)
               -   e.g. the 4th row is [3, 2, 1, 0,-1,-2,-3,-4,-5,-6,-7,-8,-9,-10,-11,...]
   :2          - integer divide by two (vectorises)
               -                       [1, 1, 0, 0,-1,-1,-2,-2,-3,-3,-4,-4,-5,-5,-6,...]
     +6        - add six (vectorises)
               -                       [7, 7, 6, 6, 5, 5, 4, 4, 3, 3, 2, 2, 1, 1, 0,...]
          $    - last two links as a monad:
         J     -   range of length -> [1,2,3,...,h]
        "      -   zip with:
       «       -     minimum (vectorises)
               -                       [4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 2, 2, 1, 1, 0,...]
           ’   - decrement (vectorises)
               -                       [3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 1, 1, 0, 0,-1,...]
             ⁵ - literal ten
            %  - modulo (vectorises)
               -                       [3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 1, 1, 0, 0, 9,...]

```
> 2 votes

# Answer
# Kotlin, 78 bytes

```
{w:Int,h:Int->List(h){r->List(w){c->if(c<11-r)r%10
else(r+9*((c-9+r)/2))%10}}}

```

Try it online!
> 2 votes

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


title: Double a number's continued fraction

text:
# Question
Title: Double a number's continued fraction
Your task is, given `x`, output `2*x`. Easy right!? But there's a catch: `x` will be given as a (possibly infinite) continued fraction, and the output must be a continued fraction. The input is guaranteed to be a real algebraic number whose degree is at most 2.

**Input**: The continued fraction of `x`. This is split into 3 parts: the integer part, the prefix, and the repeating part. The integer part consists of a single integer. The prefix and repeating part are (possibly empty) arrays of positive integers which describe the prefix and repeating part of the continued fraction. For example, the input `(3, [1], [2, 4])` represents the continued fraction `[3; 1, 2, 4, 2, 4, ...]`.

If the repeating part is empty, that indicates a rational number. For example, `(3, [1, 2], [])` represents `[3; 1, 2] = 11/3`. You must accept both forms of a rational number (i.e. `(3, [1, 1, 1], [])`, which is `[3; 1, 1, 1] = 11/3` should also be valid input).

**Output**: Output the continued fraction of twice the input, in the same format as the input. If the output is rational, you may output either form of the continued fraction. As long as the answer is equivalent to the correct answer, it is fine; no "compression" is necessary, so the infinite part might be "unrolled" a little (e.g. `[1; 4, 2, 3, 2, 3...]` may be written `(1, [4], [2, 3])` or `(1, [4, 2, 3], [2, 3])`). All answers must be exact.

**Test cases**: The exact form column is given for convenience.

```
Input               Exact Form       Output
(0, [] [])          0                (0, [] []) or (-1, [1], [])
(-5, [1, 1], [])    -4.5             (-9, [], []) or (-10, [1], [])
(3, [1, 2], [])     11/3             (7, [3], []) or (7, [2, 1], [])
(1, [], [2])        sqrt(2)          (2, [], [1, 4])
(-1, [2], [2, 1])   -1/sqrt(3)       (-2, [1, 5], [2, 6])

```

And finally a slightly larger test case to ensure precision: `(0, [1], [6, 1, 3, 1, 42, 1, 3, 1, 6, 2]) --> (1, [], [1, 2, 1, 8, 1, 20, 1, 8, 1, 2, 1, 2])`.

Shortest code wins!

**Hint**: You can perform arithmetic in a rather straightforward manner on continued fractions as described here. Doubling a continued fraction is just a special case of this algorithm (although the tricky part may be to find when the continued fraction repeats).

# Answer
> 6 votes
# Wolfram Language (Mathematica), 44 bytes

```
ContinuedFraction[2FromContinuedFraction@#]&

```

Try it online!

Mathematica has a builtin! Yay! Mathematica's builtin is super long. Aww.

Mathematica's continued fractions look like `{integer, ...prefix, {...repeating}}`

-1 thanks to JungHwan Min

# Answer
> 3 votes
# JavaScript (ES6), 267 bytes

```
(n,f,r)=>eval(`f=[0,...f];e=i=[0,2,1,0];o=j=[];k=[];m={};while([a,b,c,d]=e,c|d&&o)i*m[s=i+m+(e=c*d&&(q=a/c|0)==(b/d|0)?(o.push(q),[c,d,a-c*q,b-d*q]):1/(++i,[p,...f]=f+f?f:(i=r[0],r),p)?[b,a+b*p,d,c+d*p]:[b,b,d,d])]?k+(o=k)?o=0:(m={})[s]=1:m[s]=1;[2*n+j.shift(),j,k]`)

```

Accepts 3 arguments (n = integer part, f = prefix, r = repeating part). Outputs the three parts in an array. Try it online!

# Explanation

It's a fairly direct implementation of the algorithm for computing continued fraction arithmetic linked in the challenge here. Repeating terms are handled by storing intermediate matrices in a lookup table, waiting for a duplicate, and outputting the terms until the next appearance of that duplicate. It's inelegant and nearly doubles the bytes needed to handle continued fractions, but I could not think of a better alternative.

The leading term is computed separately to ensure that negative continued fractions retain positive values for all terms barring the first.

To prevent false positives when awaiting a repeated cycle, the lookup table stores the data as follows: `<index of input repeating part><delimiter><matrix values>`.

Note that the golfed version uses `eval` to save 1 byte.

```
(n, f, r) => {
    f = [0, ...f];                       // use a 0 to chop off the integer part
    e = i = [0,2,1,0];                   // e: matrix with starting values to handle doubling
                                         // 0 + 2x
                                         // ------
                                         // 1 + 0x
                                         // i: tracks index of repeating part; until the function loops through the
                                         // repeating part, i is equivalent to NaN
    o = j = [];                          // o: alias for group of terms currently being computed
                                         // j: output array of non-repeating terms
    k = [];                              // k: output array of repeating terms
    m = {};                              // lookup table
    while ([a,b,c,d] = e, c | d && o)    // destructure matrix
                                         // c | d stops loop if both a/c and b/d equal infinity
        i * m[s = i + m + (              // m also serves as the delimiter; JS will stringify it as "[object Object]"
                                         // if i equals a value that is coerced to NaN, this multiplication
                                         // will be falsy
            e = c * d && (q=a/c|0) == (b/d|0) // checks if either c or d is 0 to avoid converting an Infinity value to 0 using the bitwise or
                ? (o.push(q), [c, d, a - c*q, b - d*q]) // append the output term and compute the new matrix
                : 1/(++i, [p, ...f] = f+f ? f : (i=r[0], r), p) // 1/(... p) checks if p is a valid number
                                         // f+f is a short way to check length of f; if f is an empty
                                         // array, f+f = '' (which is falsy)
                                         // if f is empty, try to replace with r
                                         // if r is empty, the value of i will be set to undefined (e.g. NaN)
                    ? [b, a + b*p, d, c + d*p]
                    : [b,b,d,d]
            )
        ]                                // checks if matrix has been cached in lookup table
            ? k+(o=k)                    // if the repeating part of the output has a value...
                ? o=0                    // o serves as a flag to halt the loop
                : (m={})[s] = 1          // reset lookup table to only hold the first duplicate matrix
            : m[s] = 1;                  // otherwise flag a matrix as seen
    return [2*n + j.shift(), j, k]       // add the doubled integer part to the first term
}

```

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


title: Indexing Cha-Cha Slide

text:
# Question
Title: Indexing Cha-Cha Slide
## Introduction:

Although I originally had a Dutch song in my head, where the lyrics are: "*Doe 'n stapje naar voren, en 'n stapje terug*" (which translated to "*Take a little step forward, and a little step back*"), when I searched for the full lyrics, I realized they only got back and forth, and never sideways.

So, instead I now use the lyrics of Mr C The Slide Man a.k.a. DJ Casper - Cha-Cha Slide for this challenge.

If we ignore everything else and only look at the words "left", "right", "back", and "hop" (I counted "hop" as forward) including the mentioned amounts, the full song will have the following list (I'm using the abbreviations LRBH here):

```
LBHRLLBHRLBHHRRLLLRLBHHHHRRLLLBHHHHHRLRLRLHRLLBHHLRLBHH

```

Here the full song lyrics in a hideable JavaScript code-snippet (to save space), where the moves and amounts are surrounded with blocked brackets:

```
To the [left], take it [back] now y'all
One [hop] this time, [right] foot let's stomp
[Left] foot let's stomp, cha cha real smooth

Turn it out, to the [left]
Take it [back] now y'all
One [hop] this time, [right] foot let's stomp
[Left] foot let's stomp, cha cha now y'all

Now it's time to get funky
To the [right] now, to the [left]
Take it [back] now y'all
One [hop] this time, one [hop] this time
[Right] foot [two] stomps, [left] foot [two] stomps
Slide to the [left], slide to the [right]
Criscross, criscross
Cha cha real smooth

Let's go to work
To the [left], take it [back] now y'all
[Two] [hops] this time, [two] [hops] this time
[Right] foot [two] stomps, [left] foot [two] stomps
Hands on your knees, hands on your knees
Get funky with it, aahhhhhhhhhh yaaaa
Come on, cha cha now y'all

Turn it out, to the [left]
Take it [back] now y'all
[Five] [hops] this time
[Right] foot let's stomp, [left] foot let's stomp
[Right] foot again, [left] foot again
[Right] foot let's stomp, [left] foot let's stomp

Freeze, everybody clap yo hands
Come on y'all, check it out
How low can you go?
Can you go down low?
All the way to da floor?
How low can you go?
Can you bring it to the top?
Like it never never stop?
Can you bring it to the top?
One [hop], [right] foot now
[Left] foot now y'all
Cha cha real smooth

Turn it down, to the [left]
Take it [back] now y'all
One [hop] this time, one [hop] this time
Reverse, reverse
Slide to the [left], slide to the [right]
Reverse reverse, reverse reverse
Cha cha now y'all
Cha cha again
Cha cha now y'all
Cha cha again
Turn it down

To the [left], take it [back] now y'all
[Two] [hops] two hops, two hops two hops    EDIT: Made a mistake here, but bit to late to change it now..
```

## Challenge:

Now onto the challenge itself. We take one, two, or three inputs . One of them is a list of index-integers (so either non-negative for 0-indexed; or positive for 1-indexed). (The other inputs are optional and explained in the challenge rules.)

Every test case will start at a position `{x=0, y=0}`.
Now use the lyrics-list of moves and *remove* all moves at the given indices of the input-list. Then 'walk' over the moves (up to the largest index of the input-array) and output the position you'll end up at.

The moves will change the coordinates as follows:
\- `R`: `x+1`
\- `L`: `x-1`
\- `H`: `y+1`
\- `B`: `y-1`

## Challenge rules:

* The moves-list can be accessed any way you'd like. *†:* Can be an additional input; can be in a separated file on disk you'll read from; can be in a class-level variable you access. It will have to be in the form of `L`, `R`, `B` and `H` though (can be a string or character-list/array), so you cannot save the moves-list as `1`s and `-1`s or integers.
* The moves-list given above is hard-coded and will always be the same. (Which is also why it's fine to put it as class-level field instead of taking it as an input if this helps the byte-count of your answer.)
* Input-list can be both 0-indexed or 1-indexed (up to you)
* We only 'walk' the moves up to and excluding the largest index of the list.
    + *†:* You are also allowed to take this last item as separated integer input, instead of the last item of the input-array.
* Output of the x and y coordinates we end up at can be in any reasonable format (integer-array containing two items, delimited string, printed to STDOUT on two separated lines, etc.)
* You can assume the input-list is sorted from lowest to highest (or highest to lowest if that's what you prefer, in which case the first item is the initial size of the moves-list - if not taken as separated input). And it also won't contain any duplicated indices.
* If the largest index of the input-list is larger than the list of moves above (55 moves are in the moves-list above), we wrap around to the beginning of the list again (as many times as necessary depending on the largest index of the input).
* You are allowed to output `y,x` instead of `x,y`, but please specify this in your answer if you do.

## Example:

Input: `[0,4,8,10,13,14,27,34,42,43,44,50,53,56,59,60,64]`

Here the moves and (0-indexed) indices above one-another:

```
0, 1, 2, 3, 4, 5, 6, 7, 8, 9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64
L, B, H, R, L, L, B, H, R, L, B, H, H, R, R, L, L, L, R, L, B, H, H, H, H, R, R, L, L, L, B, H, H, H, H, H, R, L, R, L, R, L, H, R, L, L, B, H, H, L, R, L, B, H, H, L, B, H, R, L, L, B, H, R, L

```

Removing the indices of the input-list, we'll have the following moves-list remaining:

```
1, 2, 3, 5, 6, 7, 9,11,12,15,16,17,18,19,20,21,22,23,24,25,26,28,29,30,31,32,33,35,36,37,38,39,40,41,45,46,47,48,49,51,52,54,55,57,58,61,62,63
B, H, R, L, B, H, L, H, H, L, L, L, R, L, B, H, H, H, H, R, R, L, L, B, H, H, H, H, R, L, R, L, R, L, L, B, H, H, L, L, B, H, L, H, R, B, H, R

```

Now if we walk from position `{0, 0}` over the remaining moves, we'll have the following new coordinates after every move:

```
{0,0};B,{0,-1};H,{0,0};R,{1,0};L,{0,0};B,{0,-1};H,{0,0};L,{-1,0};H,{-1,1};H,{-1,2};L,{-2,2};L,{-3,2};L,{-4,2};R,{-3,2};L,{-4,2};B,{-4,1};H,{-4,2};H,{-4,3};H,{-4,3};H,{-4,5};R,{-3,5};R,{-2,5};L,{-3,5};L,{-4,5};B,{-4,4};H,{-4,5};H,{-4,6};H,{-4,7};H,{-4,8};R,{-3,8};L,{-4,8};R,{-3,8};L,{-4,8};R,{-3,8};L,{-4,8};L,{-5,8};B,{-5,7};H,{-5,8};H,{-5,9};L,{-6,9};L,{-7,9};B,{-7,8};H,{-7,9};L,{-8,9};H,{-8,10};R,{-7,10};B,{-7,9};H,{-7,10};R,{-6,10}

```

So the final output will be: `{-6, 10}`

## General rules:

* This is , so shortest answer in bytes wins.
Don't let code-golf languages discourage you from posting answers with non-codegolfing languages. Try to come up with an as short as possible answer for 'any' programming language.
* Standard rules apply for your answer, so you are allowed to use STDIN/STDOUT, functions/method with the proper parameters and return-type, full programs. Your call.
* Default Loopholes are forbidden.
* If possible, please add a link with a test for your code.
* Also, adding an explanation for your answer is highly recommended.

## Test cases:

```
0-indexed input: [0,4,8,10,13,14,27,34,42,43,44,50,53,56,59,60,64]
1-indexed input: [1,5,9,11,14,15,28,35,43,44,45,51,54,57,60,61,65]
Output: {-6, 10}

0-indexed input: [55]    (Note: There are 55 moves in the unmodified list)
1-indexed input: [56]    (Note: There are 55 moves in the unmodified list)
Output: {-6, 11}

0-indexed input: [0,1,4,5,6,9,10,15,16,17,19,20,27,29,30,37,38,39,41,44,45,46,49,51,52]
1-indexed input: [1,2,5,6,7,10,11,16,17,18,20,21,28,30,31,38,39,40,42,45,46,47,50,52,53]
Output: {10, 16}

0-indexed input: [2,3,7,8,11,12,13,14,18,21,22,23,24,25,26,31,32,33,34,35,36,38,40,42,43,47,48,50,53]
1-indexed input: [3,4,8,9,12,13,14,15,19,22,23,24,25,26,27,32,33,34,35,36,37,39,41,43,44,48,49,51,54]
Output: {-18, -7}

0-indexed input: [0]
1-indexed input: [1]
Output: {0, 0}

0-indexed input: [4,6,7,11,12,13,15,17,20,28,31,36,40,51,59,66,73,74,80,89,92,112,113,114,116,120,122,125,129,134,136,140,145,156,161,162,165,169,171,175,176,178,187,191,200]
1-indexed input: [5,7,8,12,13,14,16,18,21,29,32,37,41,52,60,67,74,75,81,90,93,113,114,115,117,121,123,126,130,135,137,141,146,157,162,163,166,170,172,176,177,179,188,192,201]
Output: {-17, 37}

0-indexed input: [25,50,75,100,125,150,175,200,225,250]
1-indexed input: [26,51,76,101,126,151,176,201,226,251]
Output: {-28, 49}

```

# Answer
# 05AB1E, ~~15~~ 12 bytes

Saved 3 bytes thanks to *Erik the Outgolfer*

```
ÝsKèIêRS¢2ôÆ

```

Try it online! or as a Test suite

**Explanation**

```
Ý                 # push range [0 ... input_int]
 sK               # remove all elements in input_list from this range
   è              # cyclically index into the moves-list with the remaining elements
    Iê            # push the unique chars of the move-list, sorted
      R           # reverse
       S¢         # count the occurrences of each char in "RLHB"
         2ô       # split into 2 parts
           Æ      # reduce each part by subtraction

```
> 4 votes

# Answer
# Ruby, ~~98 ... 58~~ 55 bytes

```
->a{([*0..a[-1]]-a).sum{|c|-1i**(m[c%55].ord%19)}.rect}

```

Try it online!

### Explanation:

The main trick is using complex numbers to represent moves: 'B' is -i, 'H' is +i, 'L' is -1 and 'R' is +1. If we convert all the moves into complex numbers, then with a single sum we get the right result.

I tried different ways, but then I found the magic number 19: we don't need to fiddle with regex matching because:

```
B  is ASCII 66; 66%19=9  and i^9  = i
H  is ASCII 72; 72%19=15 and i^15 =-i
L  is ASCII 76; 72%19=0  and i^0  = 1
R  is ASCII 82; 82%19=6  and i^6  =-1

```

So, put that all together, sum, invert the sign, and we're done.

Thanks Jakob for -3 bytes
> 7 votes

# Answer
# JavaScript (ES6), 85 bytes

As per the challenge rules, this code expects the global-scope string **m** to hold the list of moves. (Saving 3 bytes, as suggested by @KevinCruijssen.)

Takes input as a list of 0-based indices, ordered from lowest to highest.

```
a=>a.map(g=i=>j++<i&&g(i,p=m.search(m[~-j%55])*3%5,x+=--p%2,y-=--p%2),j=x=y=0)&&[x,y]

```

Try it online!

### How?

Each move character is converted to its position in the move string `"LBHR..."`. We multiply the result by **3** and apply a modulo **5**, which gives **p**. We then have:

* **dx = ((p-1) mod 2)**
* **dy = -((p-2) mod 2)**

Where the sign of **a mod b** is that of **a**.

```
 character | position | * 3 | mod 5 | dx | dy
-----------+----------+-----+-------+----+----
    'L'    |     0    |  0  |   0   | -1 |  0
    'B'    |     1    |  3  |   3   |  0 | -1
    'H'    |     2    |  6  |   1   |  0 | +1
    'R'    |     3    |  9  |   4   | +1 |  0

```
> 4 votes

# Answer
# Jelly, 14 bytes

```
Rḟị⁵ċⱮ⁵QṢṚ¤_2/

```

Try it online!

Argument 1/Left argument: Maximum 1-based index.
Argument 2/Right argument: 1-based indices.
Argument 3: Moves-list as a string. Function is still reusable if the third command-line argument is used for this purpose.
> 3 votes

# Answer
# Java 10, ~~129~~ ~~119~~ ~~112~~ ~~107~~ ~~100~~ 86 bytes

```
a->m->{var r=new int[2];for(;m-->0;)r[s[m%55]/73]-=a.add(m)?s[m%55]*3%5-2:0;return r;}

```

Takes the maximum as additional input; moves-list is a character-array on class-level.

Inspired by *@Emigna*'s 05AB1E answer.
-7 bytes thanks to *@Jakob*.
-14 bytes thanks to *@Geobits*.

Try it online.

**Explanation:**

```
a->m->{              // Method with Integer-Set & int parameters and int-array return
  var c=new int[2];  //  [x,y] result-array, starting at {0,0}
  for(;m-->0;)       //  Use the `m` input as index, and loop in the range (`m`, 0]
    r[s[m%55]/73]-=  //   Subtract from either x or y based on the character:
     a.add(m)?       //    If the input-set doesn't contain the current index `m`:
      s[m%55]*3%5-2  //     Modify the x or y coordinate based on the character
     :               //    Else:
      0;             //     Leave the x or y coordinate unchanged
  return r;}         //  Return count(R)-count(L) and count(H)-count(B) as result

```

`s[m%55]/73` maps to either the x or y coordinate depending on the character (Try it online):

```
Letter    Unicode value    /73

B         66               0
H         72               0
L         76               1
R         82               1

```

`s[m%55]*3%5-2` maps to the correct `+1` or `-1` depending the character (Try it online):

```
Letter    Unicode value    *3     %5    -2

B         66               198    3     1
H         72               216    1     -1
L         76               228    3     1
R         82               246    1     -1

```
> 3 votes

# Answer
# Python 3, 85 bytes

`b` is the index list (a `set`) and `l` is the end index. The move list (a string or character list) appears free as `s`. This is a port of *G B*'s Ruby answer, and an explanation of the approach can be found there.

```
def f(b,l):r=sum(-1j**(ord(s[i%55])%19)for i in set(range(l))-b);print(r.real,r.imag)

```

Try It Online

## Ungolfed

```
def f(b, l):
    r = sum(
        -1j ** (ord(s[i % 55]) % 19)
        for i in set(range(l)) - b
    );
    print(r.real, r.imag)

```
> 2 votes

# Answer
# MATL, 16 bytes

```
:wX-)Jw19\^s_&Zj

```

Try it online!

Takes 3 inputs like the Jelly answer, the largest index, the list of indices to skip, and the 55 character array.
> 2 votes

# Answer
# Clean, ~~148~~ ... 130 bytes

```
import StdEnv
$i=foldr(\a(x,y)|any((==)a)i=(x,y)=case m.[a rem 55]of'H'=(x,y+1);'B'=(x,y-1);'L'=(x-1,y);_=(x+1,y))(0,0)[0..last i]

```

Try it online!

Defines the function `$ :: [Int] -> (Int, Int)`, taking a list of (sorted from smallest to largest) indices to be removed from the moves before `foldr`-ing the applicable operations over `(0,0)`.
> 1 votes

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


title: Write a Program for winning sevens game

text:
# Question
Title: Write a Program for winning sevens game
> **Build a function in python that can win a Sevens game provided that there are only 2 players**

---

Here are the instructions from Wikipedia:

> All cards are dealt to the players, even if as a result some players have one card more than others. The owner of the seven of hearts begins by playing it. Similarly, the other three sevens may later be played as the first cards of their respective suits. After that, cards may be added in sequence down to the ace and up to the king. A player who cannot place a card passes.
>
> **You cannot pass if you have a card to play.**
>
> The one who gets the seven of hearts is the first to play.

The cards will be randomly distributed to the user and the computer.

The function will have two parameter:

1. List of cards remaining to play for computer
2. List cards that have been played

The syntax of a card is like this:

> `[value, suit]`

For example \[king, "clubs"\]

---

> The list of suits are:
>
> * clubs
> * spades
> * diamonds
> * hearts
>
> The list of values are:
>
> * 1
> * 2
> * 3 ....
> * 11(jack)
> * 12(queen)
> * 13(king)

The remaining cards for player 1 will be stored in list named `card_1_rem` and the remaining cards for player 2 will be stored in list named `card_2_rem`

The cards that have been played will be stored in a list called `played_cards`

---

The function will have to append the played card to the list called `played_cards` and subtract the item for the list called `card_1_rem` or `card_2_rem`

The return of one function will be the input of the competitor

The one who finishes his cards first, wins.

**Winning Condition**

---

Step 1: Users will submit their programs.

Step 2: I will test the programs against each other.

Step 3: The first program **to remain in first place (as measured by lowest total running score) for 50 consecutive games will be the winner**. This will help smooth out the effects of luck. However, a maximum of 10000 games will be played, and if no player meets the first criterion, then the player with the lowest total score after 10000 games wins.

Step 4: All the results will be uploaded to a github repo(which I will soon make).

---

> The loser has to count his points as follows
>
> ```
> Ace : 1
> 2 : 2
> 3 : 3
> 4 : 4
> 5 : 5
> 6 : 6
> 7 : 7
> 8 : 8
> 9 : 9
> 10 : 10
> jack : 10
> queen : 10
> king : 10
>
> ```
>
> For example if a king and an ace remain in the loser's hand, he gets 11 point.
>
> The objective is to minimize the points you have got.
>
> Winner gets 0 points

IMP : Submissions are allowed only in the Python 3 language.

The controller code of this challenge is here(major update has been done): https://gist.github.com/Salil03/19a093554205b52d05dc7dc55992375a

# Answer
> 2 votes
## Tactical

This ended up different enough that I felt it deserved a separate entry. This one calculates slightly smarter scores, looking not just at the next step but future choices for each player as well, based on the cards they hold. Seems to do a lot better than the "synergistic" version, better enough to beat the mysterious `player2` advantage.

```
def tactical(cards_in_hand, played_cards):
    def list2dict(lst):
        d = {}
        for val, suit in lst:
            if suit in d:
                d[suit].append(val)
            else:
                d[suit] = [val]
        return d
    def play_card(card):
        cards_in_hand.remove(card)
        played_cards.append(card)

    hand = list2dict(cards_in_hand)
    if not played_cards:
        if 7 in hand['hearts']:
            play_card([7, 'hearts'])
        return (cards_in_hand, played_cards)
    table = list2dict(played_cards)

    playable_cards = {}
    for suit in hand:

        if suit not in table:
            if 7 in hand[suit]:
                # Do I hold the majority of the cards of this suit?
                suit_advantage = (len(hand[suit]) - 6.5)
                playable_cards[(7, suit)] = suit_advantage * 20
                if 6 in hand[suit] and 8 in hand[suit]:
                    # opponent can't immediately make use of this
                    playable_cards[(7, suit)] += 20
            continue

        visible = set(table[suit] + hand[suit])
        opp_hand = set(range(1,14)) - visible

        highcard = max(table[suit]) + 1
        if highcard in hand[suit]:
            advantage = sum(c > highcard for c in hand[suit]) - sum(c > highcard for c in opp_hand)
            playable_cards[(highcard, suit)] = advantage * 10
            if highcard + 1 in opp_hand:
                playable_cards[(highcard, suit)] -= 20

        lowcard = min(table[suit]) - 1
        if lowcard in hand[suit]:
            advantage = sum(c < lowcard for c in hand[suit]) - sum(c < lowcard for c in opp_hand)
            playable_cards[(lowcard, suit)] = advantage * 10
            if lowcard - 1 in opp_hand:
                playable_cards[(lowcard, suit)] -= 20

    if not playable_cards:
        return (cards_in_hand, played_cards)

    best_card = max(playable_cards, key=playable_cards.get)
    #print(hand, "\n", table, "\n", best_card, ":", playable_cards[best_card])
    play_card(list(best_card))

    return (cards_in_hand, played_cards)

```

# Answer
> 2 votes
## Synergistic

I'm not really a Python guy, but wanted to give this a go. This builds the set of playable cards at each turn, and assigns each of them a simple static score. The card with the highest score is played (assuming any playable card exists).

```
def synergistic(cards_in_hand, played_cards):
    def list2dict(lst):
        d = {}
        for val, suit in lst:
            if suit in d:
                d[suit].append(val)
            else:
                d[suit] = [val]
        return d
    def play_card(card):
        cards_in_hand.remove(card)
        played_cards.append(card)

    hand = list2dict(cards_in_hand)
    if not played_cards:
        if 7 in hand['hearts']:
            play_card([7, 'hearts'])
        return (cards_in_hand, played_cards)
    table = list2dict(played_cards)

    playable_cards = {}
    for suit in hand:
        if 7 in hand[suit]:
            playable_cards[(7, suit)] = -1

        if suit not in table:
            continue
        visible = set(table[suit] + hand[suit])
        opp_hand = set(range(1,14)) - visible
        highcard = max(table[suit]) + 1

        if highcard in hand[suit]:
            if highcard+1 in opp_hand:
                playable_cards[(highcard, suit)] = 1
            else:
                playable_cards[(highcard, suit)] = 2

        lowcard = min(table[suit]) - 1
        if lowcard in hand[suit]:
            if lowcard - 1 in opp_hand:
                playable_cards[(lowcard, suit)] = 0
            else:
                playable_cards[(lowcard, suit)] = 1

    if not playable_cards:
        return (cards_in_hand, played_cards)

    best_card = list(max(playable_cards, key=playable_cards.get))
    #print(hand, "\n", table, "\n", best_card)
    play_card(best_card)

    return (cards_in_hand, played_cards)

```

By the way, the controller seemed to have several issues, including in score calculation and comparison. I made some changes to the controller here, please take a look and update your version if this seems right.

Two things I *haven't* fixed in the controller:

* why is the loop condition `(win2 <= 50) and (win1 <= 100)` ? This should probably be symmetrical, it should exit the loop whenever *either* of the players has 100 consecutive wins.
* trying some runs of the controller locally, with the same function for both players, Player 2 seems to win most of the time - it can't be inherent to the game since the initial 7H requirement would smooth that out (as @Veskah mentioned in the comments), so, yet undetected controller bugs? Or my player code somehow maintaining state and having a bias this way? Per-game, it's not like Player 2 dominates heavily (from the results output txt), but somehow the overall score per controller run ends up favouring player 2 much more than random (Player 1's total scores are often more than 2x that of Player 2).

# Answer
> 2 votes
**SearchBot**

```
import random

suits = ["clubs", "diamonds", "hearts", "spades"]
suit_mul = 14
hearts = suit_mul * suits.index("hearts")

def evaluate(hand):
    return sum(min(c % suit_mul, 10) for c in hand)

def rollout(hand0, hand1, runs):
    sign = -1
    counts = [[0.] * 8 for _ in range(2)]
    def counts_index(card):
        return 2 * (card // suit_mul) + ((card % suit_mul) > 7)
    for card in hand0:
        counts[0][counts_index(card)] += 1
    for card in hand1:
        counts[1][counts_index(card)] += 1
    while True:
        if not hand1:
            return sign * evaluate(hand0)
        can_play = []
        for i, run in enumerate(runs):
            if run[0] == 8 or run[1] == 6:
                if run[1] != 6:
                    run[0] = 7
                if run[0] != 8:
                    run[1] = 7
            suit = suit_mul * i
            rank = run[0] - 1
            next_low = suit + rank
            if next_low in hand0:
                if next_low - 1 in hand0:
                    runs[i][0] -= 1
                    hand0.remove(next_low)
                    counts[0][counts_index(next_low)] -= 1
                    can_play = []
                    break
                can_play.append((next_low, 0, -1))
            rank = run[1] + 1
            next_high = suit + rank
            if next_high in hand0:
                if next_high + 1 in hand0:
                    runs[i][1] += 1
                    hand0.remove(next_high)
                    counts[0][counts_index(next_high)] -= 1
                    can_play = []
                    break
                can_play.append((next_high, 1, 1))
        if can_play:
            weights = [(a - 1) / (a + b - 1) if a + b - 1 > 0 else 0 for a, b in zip(*counts)]
            weighted = [(0 if t[0] % suit_mul == 7 else weights[counts_index(t[0])], t) for t in can_play]
            weight = sum(t[0] for t in weighted)
            total = random.uniform(0, weight)
            for (w, (card, index, direction)) in weighted:
                total -= w
                if total <= 0:
                    break
            hand0.remove(card)
            counts[0][counts_index(card)] -= 1
            runs[card // suit_mul][index] += direction
        hand0, hand1 = hand1, hand0
        counts[0], counts[1] = counts[1], counts[0]
        sign *= -1

def select_move(hand0, hand1, runs, n=40):
    if hearts + 7 in hand0:
        return hearts + 7
    if hearts + 7 in hand1:
        return
    can_play = []
    for i, run in enumerate(runs):
        suit = suit_mul * i
        rank = run[0] - 1
        next_low = suit + rank
        if next_low in hand0:
            if next_low - 1 in hand0:
                return next_low
            can_play.append((next_low, 0, -1))
        rank = run[1] + 1
        next_high = suit + rank
        if next_high in hand0:
            if next_high + 1 in hand0:
                return next_high
            can_play.append((next_high, 1, 1))
    if not can_play:
        return
    if len(can_play) == 1:
        return can_play[0][0]
    scores = [0 for _ in can_play]
    for i, (card, index, sign) in enumerate(can_play):
        hand0_copy = set(hand0)
        runs_copy = [list(r) for r in runs]
        hand0_copy.remove(card)
        runs_copy[card // suit_mul][index] += sign
        for j in range(n):
            scores[i] -= rollout(set(hand1), set(hand0_copy), [list(r) for r in runs_copy])
    return can_play[scores.index(max(scores))][0]

def search(cards_in_hand, played_cards):

    def play_card(c):
        if c is None:
            return
        suit = suits[c // suit_mul]
        rank = c % suit_mul
        for i, card in enumerate(cards_in_hand):
            if card[0] == rank and card[1] == suit:
                del cards_in_hand[i]
                played_cards.append([rank, suit])
                return
        assert(False)

    hand = set(suit_mul * suits.index(s) + v for v, s in cards_in_hand)
    played = set(suit_mul * suits.index(s) + v for v, s in played_cards)
    opponent_hand = (suit_mul * s + v for v in range(1, 14) for s in range(4))
    opponent_hand = set(c for c in opponent_hand if c not in hand and c not in played)
    runs = [[8, 6] for _ in range(4)]
    for i, run in enumerate(runs):
        suit = suit_mul * i
        while suit + run[0] - 1 in played:
            run[0] -= 1
        while suit + run[1] + 1 in played:
            run[1] += 1
    card = select_move(hand, opponent_hand, runs)
    play_card(card)
    return cards_in_hand, played_cards

```

# Answer
> 0 votes
This is in python 3, but I'm pretty sure it'd work in python 2 as well. It effectively works linearly through the best (as per my limited understanding of the game) possible options at each step - highest scoring card that can match those already played, a new seven, and finally lower scoring cards, finishing by returning `None` if none of the previous options were possible.

```
def computer_play(computer_cards, dealt_cards):
    #look at dealt_cards and sort computer_cards by suit
    dealt_hearts = []
    dealt_spades = []
    dealt_clubs = []
    dealt_diamonds = []
    for i in dealt_cards:
        if i[1] == 'hearts':
            dealt_hearts.append(i[0])
        elif i[1] == 'spades':
            dealt_spades.append(i[0])
        elif i[1] == 'clubs':
            dealt_clubs.append(i[0])
        else:
            dealt_diamonds.append(i[0])
    #look at each suit and the highest card that can be played in each
    max_card_hearts = max(dealt_hearts, default=0) + 1
    max_card_spades = max(dealt_spades, default=0) + 1
    max_card_clubs = max(dealt_clubs, default=0) + 1
    max_card_diamonds = max(dealt_diamonds, default=0) + 1
    #play highest overall card
    if ['hearts', max_card_hearts] in computer_cards:
        return [max_card_hearts, 'hearts']
    elif ['spades', max_card_spades] in computer_cards:
        return [max_card_spades, 'spades']
    elif ['clubs', max_card_clubs] in computer_cards:
        return [max_card_clubs, 'clubs']
    elif ['diamonds', max_card_diamonds] in computer_cards:
        return [max_card_diamonds, 'diamonds']
    else:
        #if no cards that match suits out, check for sevens
        suits = {'hearts':max_card_hearts, 'clubs':max_card_clubs, 'spades':max_card_spades, 'diamonds':max_card_diamonds}
        for i in suits.keys():
            if [7, i] in computer_cards:
                return [7, i]
        #if no sevens, check for lowest card that can be played
        for i in suits:
            if [i, suits[i]-2] in computer_cards:
                return [i, suits[i]-2]
        #if nothing can be played, pass
        return None

```

I'll probably make more updates to it as I debug. The comments hopefully make it fairly clear what's going on.

---
Tags: king-of-the-hill, python
---