title: Congruent Numbers

text:
# Question
Title: Congruent Numbers
### Definitions:

* A triangle is considered a ***right triangle*** if one of the inner angles is exactly 90 degrees.
* A number is considered ***rational*** if it can be represented by a ratio of integers, i.e., `p/q`, where both `p` and `q` are integers.
* A number `n` is a ***congruent number*** if there exists a right triangle of area `n` where all three sides are rational.
* This is OEIS A003273.

### Challenge

This is a challenge. Given an input number, `x`, output a distinct and consistent value if `x` is a congruent number, and a separate distinct and consistent value if `x` is not a congruent number. The output values do not necessarily need to be truthy/falsey in your language.

### Special Rule

For the purposes of this challenge, you can assume that the Birch and Swinnerton-Dyer conjecture is true. Alternatively, if you can prove the Birch and Swinnerton-Dyer conjecture, go claim your $1,000,000 Millennium prize. ;-)

### Examples

(Using `True` for congruent numbers and `False` otherwise).

```
5 True
6 True
108 False

```

### Rules and Clarifications

* Input and output can be given by any convenient method.
* You can print the result to STDOUT or return it as a function result. Please state in your submission what values the output can take.
* Either a full program or a function are acceptable.
* Standard loopholes are forbidden.
* This is so all usual golfing rules apply, and the shortest code (in bytes) wins.

# Answer
> 8 votes
# R, ~~179~~ ~~173~~ ~~142~~ ~~141~~ ~~137~~ ~~135~~ 134 bytes

Using the same arguments based on Tunnell's Theorem, returns a `0` if `n`is not congruent and `1` otherwise. (It took me a long while to spot the constraint on the condition only applying to squared-free integers.)

```
function(n){b=(-n:n)^2
for(i in b^!!b)n=n/i^(!n%%i)
P=1+n%%2
o=outer
!sum(!o(y<-o(8/P*b,2*b,"+")/P-n,z<-16/P*b,"+"),-2*!o(y,4*z,"+"))}

```

Try it online

Improvements brought by Arnaud and Giuseppe (the final code is mostly Guiseppe's!), with -3 thanks to Robin

Syntax analysis:

```
for(i in b[b>0])n=n/i^(!n%%i) #eliminates all square divisors of n
P=2^(n%%2)                    #n odd (2) or even (1)
o=outer                       #saves 3 bytes
o(8/P*b,2*b,"+")/P-n          #all sums of (8/P)x^2+(2/P)*y^2-n
o(...,16/P*b,"+")             #all sums of above and (16/P)*z^2
o(...,4*z,"+"))               #all sums of above and (64/P)*z^2
!o(...,4*z,"+"))              #all sums of above equal to zero
!sum(!...,2*!...)             #are zeroes twice one another (Tunnell)

```

with Tunnell's Theorem stating that n is congruent if and only if the number of integer solutions to 2x²+y²+8z²=n is twice as much as the number of integer solutions to 2x²+y²+32z²=n if n is odd and the number of integer solutions to 8x²+y²+16z²=n is twice as much as the number of integer solutions to 8x²+y²+64z²=n if n is even.

# Answer
> 3 votes
# C++ (gcc), ~~251~~ 234 bytes

Thanks to @arnauld for pointing out a silly typo on my part.

-17 bytes thanks to @ceilingcat.

```
#import<cmath>
int a(int n){int s=sqrt(n),c,x=-s,y,z,i=1,X;for(;++i<n;)for(;n%(i*i)<1;n/=i*i);for(;x++<s;)for(y=-s;y++<s;)for(z=-s;z++<s;c+=n&1?2*(n==X+24*z*z)-(n==X):2*(n==4*x*x+2*X+48*z*z)-(n/2==2*x*x+X))X=2*x*x+y*y+8*z*z;return!c;}

```

Try it online!

Returns 1 if `n` is congruent, 0 otherwise.

Given that we can assume that the Birch and Swinnerton-Dyer conjecture is true, I used Tunnel's Theorem as a test. Note that technically only nonzero x, y, and z need to be tested, as a set of positive (x, y, z) implies more sets for when each of those is negative, since the four numbers defined use the square of x, y, and z in their calculation. Additionally, since only the *ratio* of the two numbers A and B, or C and D, is desired, we need not even worry about these other sets. Thus, we only need to add 2 for every solution for A or C, and subtract 1 for every solution of B or D, and check if we end with 0. Also, the input is reduced to a squarefree integer, because if \\$q\\$ is a congruent number then \\$s^2q\\$ is also congruent (the algorithm seems to break on some square-containing numbers.

# Answer
> 3 votes
# Rust - 282 bytes

```
fn is(mut n:i64)->bool{let(mut v,p)=(vec![0;4],n as usize%2);while let Some(l)=(2..n).filter(|i|n%(i*i)==0).nth(0){n/=l*l;}for x in -n..=n{for y in -n..=n{for z in -n..=n{for i in 0..2{if n-6*x*x*(n+1)%2==2*x*x+(2-n%2)*(y*y+(24*i as i64+8)*z*z){v[2*p+i]+=1};}}}}v[2*p]==2*v[2*p+1]}

```
* Use Jerrold B. Tunnell's theorem, which I dont actually understand, but seems to work anyways.
* divide n by all its square factors, to make it 'square free', since in the papers below Tunnell's theorem is described for square-frees only.
    + I believe this might work because every congruent number, when multiplied by a square, creates a bigger congruent number, and vice versa. so by testing the smaller number, we can validate the larger, which in our case is n. (all the removed squares, can be multiplied together to make one big square).
* loop through all possible combinations of x,y,z integers, test Tunnell's equations: $$\text{if n is odd, test if n = }2x^2 + y^2 + 32z^2\text{ and/or } 2x^2 + y^2 + 8z^2$$ $$\text{if n is even, test if n = }8x^2 + 2y^2 + 64z^2 \text { and/or } 8x^2 + 2y^2 + 16z^2$$
    + in the code itself, the four equations have been smooshed into one, inside a loop, using modulo for even/odd
* keep a tally count of which equations match n
* after looping, test the ratios of the tallies (per Tunnell)

See Also:

*corrected even/odd, thanks*@Level River St

# Answer
> 2 votes
# APL (Dyalog Unicode), ~~73~~ 67 bytes

```
{e←2∨w←⍵÷×⍨⊃⌽⍒⍵|⍨×⍨⍳⍵⋄0=¯2⊥+/w=e×⍪(r∘.+⍨32 8∘.×r)∘.+2×e×r←0,2/×⍨⍳w}

```

Try it online!

-6 bytes thanks to @ngn and @H.PWiz.

Essentially the same algorithm as others.

### Ungolfed and how it works

```
f←{
  ⍝ Extract squarefree part of ⍵
  w←⍵÷×⍨⊃⌽⍒⍵|⍨×⍨⍳⍵
⍝             ×⍨⍳⍵  ⍝ Square of 1..⍵
⍝          ⍵|⍨      ⍝ Remainders of dividing ⍵ by each of the above
⍝       ⊃⌽⍒         ⍝ Last item of descending sort order; index of last 0
⍝ w←⍵÷×⍨            ⍝ Remove square term and name it w

  ⍝ 1 if odd, 2 if even; divide w by that
  w÷←e←2∨w
⍝    e←2∨w  ⍝ GCD of w with 2; name it e
⍝ w÷←       ⍝ Divide w by e and overwrite to w

  ⍝ Square of plus-minus range
  r←0,2/×⍨⍳w
⍝       ×⍨⍳w  ⍝ Square of 1..w
⍝ r←0,2/      ⍝ Make two copies of each number, prepend 0 and name it r

  ⍝ y2+32z2 (A/C) and y2+8z2 (B/D), with y and z swapped
  m←∘.(32 8⊥¨∘⊂,)⍨r
⍝   ∘.(         )⍨r  ⍝ Self outer product of r by...
⍝              ,     ⍝ Concatenate two input numbers and
       32 8⊥¨∘⊂      ⍝ Interpret as base-32 and base-8
⍝ m←                 ⍝ Name it m

  ⍝ Add 2×e×x2
  m←,m∘.+2×e×r
⍝    m∘.+2×e×r  ⍝ Outer product by + with 2×e×x2
⍝ m←,           ⍝ Flatten and overwrite m

  ⍝ count w in m and check if B/D is twice A/C
  0=¯2⊥⊃+/w=m
⍝         w=m  ⍝ Test for each sum being w
⍝      ⊃+/     ⍝ Count of 'w's in A/C and B/D
⍝   ¯2⊥        ⍝ (¯2×A/C) + B/D
⍝ 0=           ⍝ Equals 0?
}

```

# Answer
> 1 votes
# JavaScript (ES7), 165 bytes

Much like @NeilA.'s answer, this is based on Tunnell's theorem and therefore assumes that the Birch and Swinnerton-Dyer conjecture is true.

Returns a Boolean value.

```
n=>(r=(g=i=>i<n?g(i+!(n%i**2?0:n/=i*i)):n**.5|0)(s=2),g=(C,k=r)=>k+r&&g(C,k-1,C(k*k)))(x=>g(y=>g(z=>s+=2*(n==(X=(n&1?2:8)*x+(o=2-n%2)*y)+o*32*z)-(n==X+o*8*z))))|s==2

```

Try it online!

### How?

We first transform the input \\$n\\$ into its square-free counterpart \\$n'\\$, compute \\$r=\lfloor\sqrt{n'}\rfloor\\$ and initialize \\$s\\$ to \\$2\\$.

```
r = (                // we will eventually save isqrt(n) into r
  g = i =>           // g = recursive function taking an integer i
    i < n ?          //   if i is less than n:
      g(i + !(       //     do a recursive call with either i or i + 1
        n % i**2 ?   //     if n is not divisible by i²:
          0          //       yield 0 and therefore increment i
        :            //     else:
          n /= i * i //       divide n by i² and leave i unchanged
      ))             //     end of recursive call
    :                //   else:
      n ** .5 | 0    //     stop recursion and return isqrt(n)
  )(s = 2)           // initial call to g with i = s = 2

```

We then define the helper function \\$g\\$ which invokes a callback function \\$C\\$ with \\$k^2\\$ for \\$-r\<k\le r\\$.

```
  g = (C, k = r) =>  // C = callback function, k = counter initialized to r
    k + r &&         //   if k is not equal to -r:
    g(               //     do a recursive call:
      C,             //       pass the callback function unchanged
      k - 1,         //       decrement k
      C(k * k)       //       invoke the callback function with k²
    )                //     end of recursive call

```

We finally use 3 nested calls to \\$g\\$ to walk through all triplets \\$(x,y,z) \in \[-r+1,r\]^3\\$ and update \\$s\\$ to test whether \\$2A\_n = B\_n\\$ if \\$n\\$ is odd or \\$2C\_n=D\_n\\$ if \\$n\\$ is even, with:

$$\begin{align} &A\_n=\\#\\{(x,y,z)\in \[-r+1,r\]^3 \mid n=2x^2+y^2+32z^2\\}\\ &B\_n=\\#\\{(x,y,z)\in \[-r+1,r\]^3 \mid n=2x^2+y^2+8z^2\\}\\ &C\_n=\\#\\{(x,y,z)\in \[-r+1,r\]^3 \mid n=8x^2+2y^2+64z^2\\}\\ &D\_n=\\#\\{(x,y,z)\in \[-r+1,r\]^3 \mid n=8x^2+2y^2+16z^2\\} \end{align}$$

```
g(x =>                            // for each x:      \    NB:
  g(y =>                          //   for each y:     >-- all these values are
    g(z =>                        //     for each z:  /    already squared by g
      s +=                        //       add to s:
        2 * (                     //         +2 if:
          n == (                  //           n is equal to either
            X =                   //           An if n is odd (o = 1)
            (n & 1 ? 2 : 8) * x + //           or Cn if n is even (o = 2)
            (o = 2 - n % 2) * y   //
          ) + o * 32 * z          //
        ) - (                     //         -1 if:
          n == X + o * 8 * z      //           n is equal to either
        )                         //           Bn if n is odd
    )                             //           or Dn if n is even
  )                               //
)                                 // if s in unchanged, then n is (assumed to be) congruent

```

# Answer
> 1 votes
# Ruby, 126 bytes

```
->n{[8,32].product(*[(-n..-t=1).map{|i|i*=i;n%i<1&&n/=i;i}*2+[0]]*3).map{|j|d=2-n%2
k,x,y,z=j
2*d*x+y+k*z==n/d&&t+=k-16}
t==1}

```

Try it online!

found a place to initialize `t=1` and expanded the list of squares into a triplet instead of using `q` to make additional copies.

# Ruby, 129 bytes

```
->n{t=0
[8,32].product(q=(-n..-1).map{|i|i*=i;n%i<1&&n/=i;i}*2+[0],q,q).map{|j|d=2-n%2
k,x,y,z=j
2*d*x+y+k*z==n/d&&t+=k-16}
t==0}

```

Try it online!

Uses Tunnell's theorem like the other answers. I use a single equation as follows.

```
2*d*x^2 + y^2 + k*z^2 == n/d  where d=2 for even n and d=1 for odd n

```

We check the cases `k=8` and `k=32` and check if there are twice as many solutions for `k=8` than `k=32`. This is done by adding `k-16` to `t` every time we find a solution. This is either +16 in the case `k=32` or -8 in the case `k=8`. Overall the number is congruent if `t` is the same as its initial value at the end of the function.

It is necessary to find all solutions to the test equation. I see many answers testing between +/-`sqrt n`. It is perfectly OK to test also outside these limits if it makes code shorter, but no solutions will be found because the left side of the equation will exceed `n`. The thing I missed in the beginning is that negative and positive `x,y,z` are considered separately. Thus `-3,0,3` yields three squares `9,0,9` and all solutions must be counted separately (0 must be counted once and `9` must be counted twice.)

**Ungolfed code**

```
->n{t=0                              #counter for solutions

  q=(-n..-1).map{|i|i*=i;n%i<1&&n/=i #make n square free by dividing by -n^2 to -1^2 as necessary
  i}*2+[0]                           #return an array of squares, duplicate for 1^2 to n^2, and add the case 0

  [8,32].product(q,q,q).map{|j|      #make a cartesian product of all possible values for k,x,y,z and iterate
    d=2-n%2                          #d=1 for odd n, 2 for even n
    k,x,y,z=j                        #unpack j. k=8,32. x,y,z are the squared values from q.
    2*d*x+y+k*z==n/d&&t+=k-16}       #test if the current values of k,x,y,z are a valid solution. If so, adjust t by k-16 as explained above.
t==0}                                #return true if t is the same as its initial value. otherwise false.

```

---
Tags: code-golf, decision-problem, number-theory
---


title: Is the input Bl lu ur rr ry?

text:
# Question
Title: Is the input Bl lu ur rr ry?
This is based off this challenge.

Given an input string, check whether the string is blurry.

## What's a blurry string?

A blurry string is a string that's contained in the set of all blurrified pure-ASCII strings.

Take a non-blurrified pure-ASCII string `abc` as an example. You repeat every character of this twice:

```
aabbcc

```

And then insert spaces at every odd-even index.

```
a ab bc c

```

Then, remove the preceding 2 and succeeding 2 extra characters. If there isn't enough space left, ignore the abundant removing instructions.

```
ab bc

```

As an example, all of these strings are blurry (the empty line stands for an empty string):

```
Before  After
"a"   ->
"ab"  ->ab
"abc" ->ab bc
"abcd"->ab bc cd
...

(Before = the string before blurrification)
(After  = the string after blurrification,
i.e. the strings in the set of all blurry strings.)

```

## Specification

* The input string consists purely of printable ASCII characters. The only whitespace it will contain is the space character.
* You don't have to remove extra characters before the check.
* Your output can consist of any trailing whitespace, as long as it's possible to tell a truthy result from a falsy result.
* It's noteworthy that the definition of "blurry" in this challenge is **different** than the previous challenge.

## Test cases

Here is a program I use to check my test cases.

```
""          -> True
"ab"        -> True
"ab bc"     -> True
"aa aa"     -> True
"ab bc cd"  -> True
" b bc cd"  -> True
"ab bc c "  -> True
"a   c cd"  -> True
"        "  -> True

"a"         -> False
"abc"       -> False
"ab  bc  cd"-> False
"ab#bc#cd"  -> False
"abbccd"    -> False
"a ab bc cd"-> False
"a a ab b b"-> False
"ba cb dc"  -> False
"ba bc dc"  -> False
"FFaallssee"-> False
"a aa a"    -> False

```

# Answer
# Perl 5 with `-plF/^(.((.)\x20\3)*.|)$/`, 7 bytes

```
$_=@F^1

```

Try it online!

### Explanation

Continuing the theme of abusing `-F`, I ended up with the same expression used in the Retina answer. The `-F` argument splits the input string on the valid expression and will place an even number of elements in `@F`, if the regular expression doesn't match, `@F` will just contain one entry, the whole string. When numeric operators are applied to a list (`@F` in this case) the length is implicitly used, so we XOR with 1 to give `0` for the failing test cases and a positive integer for all others.
> 3 votes

# Answer
# Retina, 14 bytes

```
a`.((.) \2)*.|

```

Try it online!

# Explanation

`a` forces the match to be on the entire string

`.((.) \2)*.` just means any character (`.`) followed by a captured group repeated 0 to many times (`(...)*`) of any character saved into a second captured group (`(.)`) followed by a space and the same character that was matched in the second capture group (`\2`). The final `.` just matches the last character

`|` allows the empty string to match by having an alternative match of the empty string
> 7 votes

# Answer
# Python 3, ~~60~~ 54 bytes

-6 bytes thanks to Surculose Sputum!

```
a,*b,c=input()or'ab'
while b:x,y,z,*b=b;x[x!=z][y>' ']

```

Try it online! Output is via exit code.

By using different sets of errors for truthy/falsy inputs this can be 52 bytes, as suggested by Surculose Sputum.
> 6 votes

# Answer
# Python 2, 57 bytes

```
lambda x:x==''.join(c+' '+c for c in x[::3]+x[-1:])[2:-2]

```

Try it online!

Uses the same approach as my Pyth answer. The blurring portion of the code is based off of @Surculose Sputum's answer to the original "Blur a string" challenge.
> 5 votes

# Answer
# Haskell, 68 bytes

```
_#""=1<2
p#(' ':x:y:s)|p==x=y#s
_#_=2<1
f""=1<2
f(x:y:s)=y#s
f _=2<1

```

Try it online!

## Explanation

`f` is the entry point. No real tricks; loop through recursively ensuring that every third character is a space, while keeping track of the second character of the previous chunk each time and ensuring that it's equal to the first of the next chunk.
> 4 votes

# Answer
# Pyth, 13 bytes

```
qjd.:+%3Q>1Q2

```

Try it online!

```
qjd.:+%3Q>1Q2
      %3Q      Take every 3rd character of the input string
                (eg. "ab bc cd" becomes "abc")
     +   >1Q   Append the last character of the input string
 jd.:       2  "Blur" the resulting string
                (ie. find all substrings of length 2 and join on spaces)
q              Return true if that matches the input string

```
> 4 votes

# Answer
# 05AB1E, ~~16~~ ~~13~~ 12 bytes

```
¤º«3ô€нüJðýQ

```

Try it online!

Uses the blurring program here to re-blur the string. -1 byte thanks to Kevin Cruijssen!

## Old Answer Explained

```
3ô`©)€н`®θJüJðýQ
3ô                  # Split the input into chunks of 3
  `©                # Item split the above and store the last item in the register
    )               # Wrap everything back into a list
     €н             # Get the first character from each item in then above list
       `            # Item split the list generated from the above map
        ®θJ         # Join the above with the last letter from the register
           üJðý     # Blatant port of https://codegolf.stackexchange.com/a/203906/78850 -- i.e. blur the string
               Q    # Check to see if the blurred string is the input

```
> 4 votes

# Answer
# Charcoal, ~~26~~ 21 bytes

```
⁼✂θ¹±¹¦¹⭆✂θ¹±¹¦³⁺⁺ι ι

```

Try it online! Link is to verbose version of code. Outputs a Charcoal boolean, `-` for a blurry string, nothing if not. Explanation:

```
  θ                     Input string
 ✂ ¹±¹¦¹                Slice off the first and last characters
⁼                       Is equal to
          θ             Input string
         ✂ ¹±¹¦³        Every other third character
        ⭆               Map over characters and join
                ⁺⁺ι ι   Wrap a space in that character
                        Implicitly print

```
> 3 votes

# Answer
# Japt, 13 bytes

The empty string being truthy cost a couple of bytes :\

```
¶¬ë3 pUÌ ä+ ¸

```

Try it (includes all test cases)

```
¶¬ë3 pUÌ ä+ ¸     :Implicit input of string U
¶                 :Test for equality with
 ¬                :Split to an array
  ë3              :Take every 3rd element, starting with the first
     p            :Push
      UÌ          :  Last character of U
         ä+       :Consecutive pairs, reduced by concatenation
            ¸     :Join with spaces

```
> 3 votes

# Answer
# Red, ~~52~~ 51 bytes

```
func[a][s:[skip]parse a[opt[s any[copy t s" "t]s]]]

```

Try it online!
> 3 votes

# Answer
# Jelly, 8 bytes

```
m3żḊ$K⁼Ṗ

```

A monadic Link accepting a list of characters which yields `1` (blurry), or `0` (not blurry).

**Try it online!** Or see the test-suite.

### How?

```
m3żḊ$K⁼Ṗ - Link: list of characters, S
m3       - modulo-3-slice (S)
    $    - last two links as a monad (f(X)):
   Ḋ     -   remove the head (X)
  ż      -   zip together (X and that)
     K   - join with spaces
       Ṗ - remove the tail (S)
      ⁼  - equal?

```
> 2 votes

# Answer
# JavaScript (Node.js), 29 bytes

```
s=>/^.((.) \2)*.$|^$/.test(s)

```

Try it online!

Pure port
> 1 votes

---
Tags: code-golf, string, decision-problem
---


title: Who Took My Toilet Paper?

text:
# Question
Title: Who Took My Toilet Paper?
You step into the restroom, and notice that the toilet paper has missing! It occurs to you that someone had *stolen* it. Strangely enough, the first thing you would like to know is the amount of toilet paper the thief stole.

## Task

You are given three integers \\$ I \\$, \\$ R \\$, and \\$ G \\$, the details of the toilet paper, where \\$ I \\$ is the *radius* of the inner ring, \\$ R \\$ is the number of *rotations*, and \\$ G \\$ is the *thickness*. The task is to return/output out the *length* of the toilet paper.

The toilet paper can be viewed as an Archimedes' spiral, which starts at coordinate \\$ (I, 0) \\$, and rotates a total of \\$ R \\$ times in the counterclockwise direction, with a distance of \\$ G \\$ between each gap.

More formally, the Archimedes' spiral here is defined as the set of all points whose locations over time move away from the origin counterclockwise at a constant speed and with constant angular velocity.

Due to potential precision issues, your answer will be judged correct if they pass all the sample cases below when rounded to \\$ 1 \\$ decimal place.

In the diagram below, \\$ I = 5 \\$, \\$ R = 3 \\$, \\$ G = 4 \\$, and the total length is \\$ \approx 207.7 \\$.

## Test Cases

```
I R G -> answer rounded to 1 decimal place (note that the answer does not have to be rounded)
0 1 1 -> 3.4
5 3 4 -> 207.7
12 9 2 -> 1187.7

```

This is , so the shortest code in bytes wins!

# Answer
> 8 votes
# , 66 bytes

```
1#.2|@-/\1e3&((-:@[%:_1:)^[:i.1+[*0{])((*{:)+[*(1{])*1e3%~i.@#@[)]

```

Try it online!

This could be golfed more, but I'm putting it away for now.

Instead of taking an analytic approach I am using complex number arithmetic to break the spiral down into 1000 straight line segments per rotation, and then summing those segments.

I find the 500th root of -1, and keep multiplying it by itself to rotate it and get an approximation to the next spiral point.

Because the spiral also moves outward, we need to take the new vector, normalize it, multiply the normal vector by 1/1000 of the thickness, and then add that little correction to the new vector.

Conceptually, we're doing something similar to approximating a circle's circumference with the short sides of many triangles.

The idea is simple, but the golf part of it boils down to boring bookkeeping and argument parsing which isn't worth going into. In theory the realization of this method could be a lot shorter.

# Answer
> 7 votes
# Python 3, ~~93~~ ~~83~~ ~~76~~ 71 bytes

*-9 bytes if we don't explicitly round the results*
*-1 byte after changing n to 9999*
*-7 bytes thanks to dingledooper who rearranged the operations*
*-5 bytes thanks to xnor who changed the square root calculations to taking an absolute value of a complex number*

```
lambda i,r,g:sum(abs(1j+6.283*(t/n+i/g))for t in range(n*r))/n*g
n=9999

```

Try it online!

This is a straightforward numerical integration of a spiral length, without using any imports. `n` is chosen so that the results are sufficiently precise.

The length of a spiral is a sum $$L = \sum\_{t=1}^n L\_t,$$ where Lt is calculated as a hypothenuse in a *roughly* right triangle with sides $$\frac{2\pi}{n} r\_t = \frac{2\pi}{n}\left(i+\frac{gt}{n}\right)$$ and $$r\_{t+1}-r\_t = \frac{g}{n}$$.

# Answer
> 5 votes
# Python 3, 83 bytes

*Thanks @xnor for finding some important approximation, notably `h(t)=t*t+log(2*t+.5)`*

```
lambda i,r,g:g/2/T*(h(T*(i/g+r))-h(T*i/g))
h=lambda t:t*t+99*(2*t+.5)**.01
T=6.2832

```

Try it online!

The same solution as below, but uses several approximations:

* \\$2\pi \approx 6.2832\\$
* \\$ \theta\sqrt{1+\theta^2}+\sinh^{-1}\theta + C \\$
\\$ \approx \theta^2 + \ln(2\theta+0.5) +C \\$
\\$ \approx \theta^2 + 99(2\theta+0.5)^{0.01} + C\\$

---

"Exact" solution

# Python 3, ~~104~~ 100 bytes

*-3 bytes thanks to @mathjunkie!*
*-1 byte thanks to @xnor!*

```
lambda i,r,g:g/4/pi*(h(2*pi*(i/g+r))-h(2*pi*i/g))
from math import*
h=lambda t:t*hypot(t,1)+asinh(t)

```

Try it online!

This uses the exact formula. Maybe a good Taylor series approximation can be shorter.

The formula for the length of the spiral is: $$ L=\frac{G}{2\pi} \int\_{\frac{2\pi I}{G}}^{\frac{2\pi(I+GR)}{G}}\sqrt{1+\theta^2}d\theta $$ and the formula for the integral is: $$ \int \sqrt{1+\theta^2}d\theta=\frac{1}{2}\left(\theta\sqrt{1+\theta^2}+\sinh^{-1}\theta \right) $$

# Answer
> 5 votes
# Python 3, 60 bytes

```
lambda I,R,G:6.2831*R*(I+R*G/2)+G*8*((1+R/(I/G+.05))**.01-1)

```

Try it online!

An approximate method. Approximates `log` without an import using Surculose Sputum's nifty approximation

This approximation is quite accurate, achieving within 0.02 on all the test cases and within 0.1 on all single-digit inputs. It's possible to use looser approximations that work for all the test cases, but I'm not sure at what point this is overfitting. In the extreme, hardcoding the outputs would be very short. So, I'd like to exclude this answer from my bounty on outgolfing me since I'm not clear what golfs what be valid.

The first summand \\$2\pi(I+RG/2)R\\$ is what we get if we approximate the toilet paper spiral as instead being concentric circles with the same inner radius, thickness, and number of turns. The average of the circumferences of these \\$R\\$ circles is \\$2\pi(I+RG/2)\\$. This is \\$2\pi\\$ times the average of their radii of \\$I+RG/2\\$, or equivalently the average of the inner and outer radius.

The above approximation is already pretty good for the test cases, with error within 0.4. The second term approximates the additional circumference due to the spiral moving radially, rather than just tangentially as circles do. I got this from looking at the integral for arc length suggested by svavil. We then get rid of approximate `log` without an import using Surculose Sputum's approximation The constant of 8 is an approximation for \\$100/(4\pi)\\$, with 100 being inverse of the exponent 0.01 chosen for the log approximation. The `+0.05` fixes an approximation failing near \\$I/G=0\\$, which would otherwise cause a divide-by-zero. I originally calculated the desired values as \\$1/(4\pi)=0.08\\$, but heuristically 0.05 does better.

# Answer
> 2 votes
# C (gcc) -lm -m32, ~~129~~ ~~120~~ ~~117~~ 114 bytes

```
#define F float
F i(F u,F g){F s=hypot(u,g/=6.2832);return(u*s/g+g*log(s+u))/2;}
#define f(I,R,G)i(I+G*R,G)-i(I,G)

```

Try it online!

*5 bytes off thanks to ceilingcat (by using the hypot library function).*

*4 bytes off thanks to dingledooper (who suggested using a typedef to shorten the float declarations -- I ended up using a macro instead to implement the same idea).*

*3 bytes off by using an approximation to \\$2\pi\\$ that's sufficient for the accuracy required by the challenge.*

*3 more bytes thanks to ceilingcat (turning f from a function into a macro).*

The auxiliary function `i` computes the appropriate indefinite integral, and then `f` computes the desired definite integral by evaluating the indefinite integral at the two endpoints and subtracting.

# Answer
> 1 votes
# 05AB1E, 23 bytes

```
4°©*Ý*®/+nŽ›Ñ₄/*²n+tO®/

```

Port of *@svavil*'s Python answer (their revision without complex number), so make sure to upvote them!

Input-order as `r,g,i`.

Try it online or verify all test cases.

**Explanation:**

```
4°                      # Push 10**4: 10000
  ©                     # Store it in variable `®` (without popping)
   *                    # Multiply it by the first (implicit) input `r`
    Ý                   # Push a list in the range [0, 10000r]
     *                  # Multiply each value by the second (implicit) input `g`
      ®/                # Divide each by `®`
        +               # Add the third (implicit) input `i` to each value
         n              # Take the square of that
          Ž›Ñ           # Push compressed integer 39478
             ₄/         # Divide it by 1000: 39.478
               *        # Multiply it by each value
                ²       # Push the second input `g` again
                 n      # Square it
                  +     # And add it to each value as well
                   t    # Take the square-root of each value
                    O   # Sum everything together
                     ®/ # And divide it by `®`
                        # (after which the result is output implicitly)

```

See this 05AB1E tip of mine (section *How to compress large integers?*) to understand why `Ž›Ñ` is `39478`.

# Answer
> 1 votes
# SageMath, 70 bytes

```
lambda I,R,G:N(G/2/pi*(sqrt(1+x^2)).integral(x,2*pi*I/G,2*pi*(I/G+R)))

```

Try it online!

**How**

Uses the formula for the length of the spiral: $$ L=\frac{G}{2\pi} \int\_{\frac{2\pi I}{G}}^{\frac{2\pi(I+GR)}{G}}\sqrt{1+\theta^2}d\theta $$

from Surculose Sputum's Python answer.

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


title: Gossipping ladies

text:
# Question
Title: Gossipping ladies
## Problem description

Vertices \\$V\\$ of directed graph \\$G=(V,E)\\$ represent gossipping ladies; edge \\$(u,v) \in E\\$ signifies that lady \\$u\\$ knows of lady \\$v\\$ (which does not imply that lady \\$v\\$ knows of lady \\$u\\$). Assume that each lady knows of herself.

Intuitively, lady \\$a\\$ gossips about every lady \\$b\\$ she knows about, except herself, to every *other* lady \\$c\\$ whom \\$a\\$ knows about (other than \\$b\\$ herself). Lady \\$c\\$, upon hearing gossip *from* lady \\$a\\$ *about* lady \\$b\\$, will learn about \\$b\\$ but not about \\$a\\$. For \\$c\\$, this then means two things:

* \\$c\\$ will from now on gossip *about* \\$b\\$ to all other ladies she knows about, and
* \\$c\\$ will from now on gossip *to* \\$b\\$ about all other ladies she knows about, except about her own self.

Formally, the **Gossip Operation** \\$g(G)\\$ produces a graph \\$G' = (V, E')\\$, where $$E' = E \ \cup\ \\{(c,b) \ \vert\ \exists\ (a,b) \in E : a \neq b \ \land\ \exists\ (a,c) \in E: c \neq b \\}$$

(Added edges in red.)

The **Gossip Closure** of a graph \\$G\\$ is the fixed point of the Gossip Operation starting from \\$G\\$.

## Example

**Input:**

```
a:{a,b,c,d}
b:{b,e}
c:{c,d}
d:{d}
e:{e}
f:{f,a}
g:{g}

```

**Output:**

```
a:{a,b,c,d}
b:{b,e,c,d}
c:{c,d,b,e}
d:{d,b,c,e}
e:{e,b,c,d}
f:{f,a}
g:{g}

```

### Larger example

Original graph

After one iteration

Closure

Loops not shown in graphs.

## Task

Implement an algorithm of lowest possible time complexity, which given an directed unweighted graph\* \\$G\\$ in any suitable format (viz. any format supporting directed unweighted graphs), outputs its Gossip Closure.

* You may impose certain limits on the input, eg. an upper bound on graph density if your solution is better suited for sparse graphs.

# Answer
> 3 votes
# Prolog

```
:- use_module(library(dcgs)).
:- use_module(library(lists)).
:- use_module(library(pio)).

:- op(950, fx, *). *_.

% Read the data.
space --> " ", space.
space --> "".

seq([]) --> [].
seq([S|Ss]) --> [S], seq(Ss).

lines([L|Ls]) --> seq(L), "\n", lines(Ls),
    { \+ member('\n', L) }.
lines([]) --> [].

graph(S1-S2) --> space, seq(S1), space, ":", space, vertices(S2), space.

vertices([]) --> [].
vertices([V|Vs]) --> seq(V), space, ",", space, vertices(Vs).
vertices([V]) --> seq(V).

% Solve.

merge_vertices(Vs, Ws, Xs) :-
    append(Vs, Ws, Xs0),
    sort(Xs0, Xs).

merge_edges(As, Bs) :-
    merge_edges_(As, [], Bs1),
    keysort(Bs1, Bs).

merge_edges_([], Cs, Cs).
merge_edges_([A|As0], Bs0, Cs) :-
    U-Vs = A,
    (   select(U-Ws, As0, As1)
    ->  merge_vertices(Vs, Ws, Xs),
        append([U-Xs], As1, As),
        Bs = Bs0
    ;   append([A], Bs0, Bs),
        As = As0
    ),
    merge_edges_(As, Bs, Cs).

create_edges([], []).
create_edges([_], []).
create_edges(Vs0, Es) :-
    Vs0 = [_,_|_],
    findall(V-Vs, select(V, Vs0, Vs), Es).

gossip(G0, G) :-
    gossip_(G0, [], G).

gossip_([], G, G).
gossip_([E|Es], G0, G) :-
    U-Vs1 = E,
    (   select(U, Vs1, Vs)
    ->  true
    ;   Vs = Vs1
    ),
    create_edges(Vs, G1),
    append([E|G0], G1, G2),
    merge_edges(G2, G3),
    gossip_(Es, G3, G).

limit_gossip(G, G) :-
    gossip(G, G).
limit_gossip(G0, G) :-
    gossip(G0, G1),
    limit_gossip(G1, G).

build_graph(G, L) :- phrase(graph(G), L).

writeln(X) :-
    writeq(X), nl.

output(G) :-
    maplist(writeln, G).

test :-
    once((
        phrase_from_file(lines(Ls), 'g.txt'),
        maplist(build_graph, G1, Ls)
    )),
    limit_gossip(G1, G),
    output(G),
    halt.

:- initialization(test).

```

```
$ cat g.txt
a:a,b,c,d
b:b,e
c:c,d
d:d
e:e
f:f,a
g:g

```

# \[Complexity\]: \\$O(V^2\ln V)\\$

Where \\$V\\$ is the number of vertices.

---
Tags: graph-theory, fastest-algorithm
---


title: Look for n-plicates

text:
# Question
Title: Look for n-plicates
If you are given an array of numbers between 1 and 100 and an integer `n`, you must remove any instances of an item that appear greater than `n` times.

For example:

```
In : [92, 41, 81, 47, 28, 92, 84, 92, 81], n = 1
Out: [92, 41, 81, 47, 28, 84]

```

The most aesthetic/simple algorithm wins. And since this is a , you get to decide!

# Answer
> 1 votes
# , 21 16 15 bytes

```
(>:+/@(={:)\)#]

```

Try it online!

Overall, we make a boolean mask and apply it to the original list: `(...)#]`

To construct the mask, for each prefix `\` we sum `+/@` the number of times an element equals the last element of that prefix `(={:)`, which gives us a list the same size as the original, where each element holds the number of times the element has appeared so far. This is:

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

```

for the example list.

Then we check which elements are less than or equal `>:` to the left arg:

```
1 1 1 1 1 0 1 0 0

```

producing the mask we want.

---
Tags: array, popularity-contest
---


title: Starry Metagolf

text:
# Question
Title: Starry Metagolf
Starry is a funny esoteric programming language in which code consists only of `+*.,`'` where the actual command represented by each of those characters is determined by the number of spaces in front of it. That makes it tricky even to golf fixed-output challenges, because different commands can account for vastly different numbers of bytes. In particular, number literals have a unary representation which makes it necessary to build up larger numbers by operating on smaller ones.

Therefore, this challenge is about writing a program which can golf such Starry programs.

## How does Starry work?

*(A few details are left unspecified on esolangs, so I'm going with the behaviour of the Ruby interpreter.)*

Starry is a stack-based language, with a single stack of arbitrary-precision integer values (which is initially empty).

The only meaningful characters are:

```
+*.,`'

```

and spaces. All other characters are ignored. Each sequence of spaces followed by one of those non-space characters represents a single instruction. The type of instruction depends on the non-space character and the *number* of spaces.

The instructions are:

```
Spaces  Symbol  Meaning
0         +     Invalid opcode.
1         +     Duplicate top of stack.
2         +     Swap top 2 stack elements.
3         +     Rotate top 3 stack elements. That is, send the top stack element
                two positions down. [... 1 2 3] becomes [... 3 1 2].
4         +     Pop and discard top of stack.
n ≥ 5     +     Push n − 5 to stack.
0 mod 5   *     Pop y, pop x, push x + y.
1 mod 5   *     Pop y, pop x, push x − y.
2 mod 5   *     Pop y, pop x, push x * y.
3 mod 5   *     Pop y, pop x, push x / y, rounded towards -∞.
4 mod 5   *     Pop y, pop x, push x % y. The sign of the result matches the sign of y.
0 mod 2   .     Pop a value and print it as a decimal number.
1 mod 2   .     Pop a value and print it as an ASCII character. This throws an error
                if the value is not in the range [0, 255].
n         `     Mark label n.
n         '     Pop a value; if non-zero, jump to label n.

```

Note that the interpreter scans the source code for the labels before execution begins, so it's possible to jump forwards as well as backwards.

Of course, Starry also has input commands (using `,` analogously to `.`), but those are irrelevant for this challenge.

## The Challenge

Given a string, generate a Starry program which takes no input and prints that string exactly to STDOUT.

You may write a program or function, taking input via STDIN (or closest alternative), command-line argument or function argument and outputting the result via STDOUT (or closest alternative), function return value or function (out) parameter.

You may assume that the string is not longer than 128 characters and that it will consist only of printable ASCII characters (code points 0x20 to 0x7E).

Your solution should process any such input in less than 5 minutes on a reasonable desktop machine (there's some leeway to this; if it takes a few minutes more on my laptop I don't mind, but if it takes 15, I'll disqualify it).

Your solution will be tested on a number of different strings listed below. **Your score is the total byte count of the corresponding Starry programs.** In the case of a tie, the shortest metagolfer wins. That is, don't bother golfing your own code unless there is a tie (which I think will only happen in the case that an optimal solution is possible).

You must not optimise your code towards the specific test cases listed below. Specifically, you shouldn't hardcode hand-crafted solutions for them. Optimising towards classes of strings whose structure is similar to that of the given strings is fine. If I suspect anyone of hardcoding solutions, I reserve the right to replace some or all of the test cases (with strings of comparable structures).

## Test Cases

Each line is a separate test case:

```
Hello, World!
pneumonoultramicroscopicsilicovolcanoconiosis
.oOo.oOo.oOo.oOo.oOo.oOo.oOo.oOo.oOo.oOo.oOo.
Hickory, dickory, dock. The mouse ran up the clock. The clock struck 1. The mouse ran down. Hickory, dickory, dock.
36912059868043514648560046917066768694455682545071266675083273015450033938555319356951628735735013250100789433961153496780296165
bVZ48121347GLtpYnt76CZSxTpMDs6791EJE808077eySXldY162424ddTB90707UupwlWGb63618542VhA252989453TXrWgqGm85899uHOAY2oAKE198GOVUttvW63
7MYxoWBNt180CDHS5xBGvU70HHVB17bh8jYzIIiU6n6g98Rose1nOe8Svcg56nax20q30kT3Ttb2jHl5q2Iuf1vPbjPxm9cyKXwxc0OUK8pr13b2n7U9Y7RwQTc26A1I
n9}unwxVa}[rj+5em6K#-H@= p^X/:DS]b*Jv/_x4.a5vT/So2R`yKy=in7-15B=g _BD`Bw=Z`Br;UwwF[{q]cS|&i;Gn4)q=`!G]8"eFP`Mn:zt-#mfCV2AL2^fL"A

```

Credits for the second test case go to Dennis. Credits for the fourth test case go to Sp3000.

## Reference Solution

Here is a really basic reference solution in CJam:

```
q{S5*\iS*'+S'.}%

```

You can run it against the entire test suite here. The scores are:

```
1233
5240
4223
11110
7735
10497
11524
11392
Total: 62954

```

It's the simplest possible approach: push each character's code point as a literal, and then print it. It makes no use of small differences between consecutive characters, integer printing, repetitive parts of the string etc. I'll leave those things to you.

I believe there is a lot of room for improvement. For reference, the shortest handcrafted "Hello, World!" is only 169 bytes long.

# Answer
> 6 votes
# Ruby, ~~13461~~ 10997

```
$s = {};
def shortest a,b=nil
    return $s[[a,b]] if $s[[a,b]]
    l = []
    if b
        if a == b
            return $s[[a,b]] = ""
        elsif a > b
            l.push shortest(a-b)+" *"
            l.push " +   *"+shortest(1,b) if a > 1
            l.push " + *"+shortest(0,b) if a > 0
            l.push "    +"+shortest(b)
        elsif a < b
            l.push " +  *"+shortest(a*a,b) if a*a>a && a*a<=b
            l.push " +*"+shortest(a+a,b) if a+a<=b && a+a>a
            l.push shortest(b-a)+"*"
            l.push " +"+shortest(a,b/a)+"  *" if a>2 && b%a == 0
            l.push " +"+shortest(a,b-a)+"*" if a>1 && b>a*2
        end
    else
        l.push ' '*(a+5)+'+' #if a < 6
        (1..a/2).each {|n|
            l.push shortest(n)+shortest(n,a)
        }
    end
    return $s[[a,b]] = l.min_by{|x|x.length}
end

def starry(str)
    arr = str.bytes.map{|b|
        if b>47 && b<58
            b-48# change digets to numbers
        else
            b
        end
    }

    startNum = (1..128).min_by{|x|arr.inject{|s,y|s + [shortest(x,y).length+2,shortest(y).length].min}+shortest(x).length}
    #one number to be put on the stack at the start.

    code = shortest(startNum)
    code += [
        shortest(arr[0]),
        " +"+shortest(startNum, arr[0])
    ].min_by{|x|x.length}

    arr.each_cons(2) do |a|
        pr = a[0]<10?'.':' .'
        code += [
            pr+shortest(a[1]),
            " +"+pr+shortest(a[0], a[1]),
            pr+" +"+shortest(startNum, a[1])
        ].min_by{|x|x.length}
    end
    code += arr[-1]<10?'.':' .'
end

a = ["Hello, World!",
"pneumonoultramicroscopicsilicovolcanoconiosis",
".oOo.oOo.oOo.oOo.oOo.oOo.oOo.oOo.oOo.oOo.oOo.",
"Hickory, dickory, dock. The mouse ran up the clock. The clock struck 1. The mouse ran down. Hickory, dickory, dock.",
"36912059868043514648560046917066768694455682545071266675083273015450033938555319356951628735735013250100789433961153496780296165",
"bVZ48121347GLtpYnt76CZSxTpMDs6791EJE808077eySXldY162424ddTB90707UupwlWGb63618542VhA252989453TXrWgqGm85899uHOAY2oAKE198GOVUttvW63",
"7MYxoWBNt180CDHS5xBGvU70HHVB17bh8jYzIIiU6n6g98Rose1nOe8Svcg56nax20q30kT3Ttb2jHl5q2Iuf1vPbjPxm9cyKXwxc0OUK8pr13b2n7U9Y7RwQTc26A1I",
"n9}unwxVa}[rj+5em6K#-H@= p^X/:DS]b*Jv/_x4.a5vT/So2R`yKy=in7-15B=g _BD`Bw=Z`Br;UwwF[{q]cS|&i;Gn4)q=`!G]8\"eFP`Mn:zt-#mfCV2AL2^fL\"A"]
c = a.map{
    |s|
    starry(s).length
}
p c.inject(0){|a,b|a+b}

```

The method `starry` answers the given question.

Results:

```
230
639
682
1974
1024
1897
2115
2436
Total: 10997

```

### How it works

`shortest` is the main algorithm. It takes one number and finds the shortest way to place it on the stack, or it takes two numbers, and returns code to put the second on the stack assuming the first one is already on. `$s` is a Hash to hold the results of these operations for further use.

`starry` takes a string and splits it into an array of character codes (or numbers for digests). It starts the code with one number on the bottom of the stack. Next it calculates the shortest way it can generate each successive number, possibly copying the last one or using the number put on the stack at the beginning.

# Answer
> 9 votes
## Python 3, ~~17071~~ 11845

```
from functools import lru_cache
import heapq
import time

cases = r"""
Hello, World!
pneumonoultramicroscopicsilicovolcanoconiosis
.oOo.oOo.oOo.oOo.oOo.oOo.oOo.oOo.oOo.oOo.oOo.
Hickory, dickory, dock. The mouse ran up the clock. The clock struck 1. The mouse ran down. Hickory, dickory, dock.
36912059868043514648560046917066768694455682545071266675083273015450033938555319356951628735735013250100789433961153496780296165
bVZ48121347GLtpYnt76CZSxTpMDs6791EJE808077eySXldY162424ddTB90707UupwlWGb63618542VhA252989453TXrWgqGm85899uHOAY2oAKE198GOVUttvW63
7MYxoWBNt180CDHS5xBGvU70HHVB17bh8jYzIIiU6n6g98Rose1nOe8Svcg56nax20q30kT3Ttb2jHl5q2Iuf1vPbjPxm9cyKXwxc0OUK8pr13b2n7U9Y7RwQTc26A1I
n9}unwxVa}[rj+5em6K#-H@= p^X/:DS]b*Jv/_x4.a5vT/So2R`yKy=in7-15B=g _BD`Bw=Z`Br;UwwF[{q]cS|&i;Gn4)q=`!G]8"eFP`Mn:zt-#mfCV2AL2^fL"A
""".strip().splitlines()

@lru_cache(maxsize=128)
def shortest_m_to_n(m, n):
    if m is None:
        L = []
    else:
        L = [m]

    to_search = [[0, "", L]]
    seen = set()

    while True:
        length, code, stack = heapq.heappop(to_search)

        if len(stack) == 1 and stack[-1] == n:
            return code

        seen.add(tuple(stack))
        options = []

        for i in range(1, 11):
            new_stack = stack[:] + [i]
            new_code = code + ' '*(i+5) + '+'
            options.append([len(new_code), new_code, new_stack])

        if stack:
            new_stack = stack[:] + [stack[-1]]
            new_code = code + " +"
            options.append([len(new_code), new_code, new_stack])

        if len(stack) >= 2:
            x, y = stack[-2:]

            for i, op in enumerate(['+', '-', '*', '//', '%']):
                try:
                    new_elem = eval("{}{}{}".format(x, op, y))
                    new_stack = stack[:-2] + [new_elem]
                    new_code = code + ' '*i + '*'
                    options.append([len(new_code), new_code, new_stack])

                except ZeroDivisionError:
                    pass

        for op in options:
            if tuple(op[2]) in seen or len(op[2]) > 4 or op[2][-1] > 200:
                continue

            heapq.heappush(to_search, op)

def lcs(s1, s2):
    dp_row = [""]*(len(s2)+1)

    for i, c1 in enumerate(s1):
        new_dp_row = [""]

        for j, c2 in enumerate(s2):
            if c1 == c2 and not c1.isdigit():
                new_dp_row.append(dp_row[j] + c1)
            else:
                new_dp_row.append(max(dp_row[j+1], new_dp_row[-1], key=len))

        dp_row = new_dp_row

    return dp_row[-1]

def metagolf(s):
    keep = ""
    split_index = 0

    for i in range(1, len(s)):
        l = lcs(s[:i], s[i:][::-1])
        if len(l) > len(keep):
            keep = l
            split_index = i

    code = []
    stack = []
    keep_ptr = 0
    i = 0

    while i < len(s):
        c = s[i]
        n = ord(c)

        if c in "0123456789":
            code += [" "*(int(c)+5) + "+."]
            i += 1
            continue

        if stack:
            if stack[-1] == n:
                code += [" +", " ."]
            elif len(stack) >= 2 and stack[-2] == n:
                for j in range(len(code)):
                    if code[~j] == " +":
                        code[~j] = ""
                        break

                code += [" +", " ."]
                stack.pop()
            else:
                code += [shortest_m_to_n(stack[-1], n), " +", " ."]
                stack[-1] = n

        else:
            code += [shortest_m_to_n(None, n), " +", " ."]
            stack.append(n)

        while i < split_index and keep[keep_ptr:][:1] == c:
            code += [" +"]
            keep_ptr += 1
            stack.append(n)

        i += 1

    code = "".join(code)

    if code[-4:] == " + .":
        code = code[:-4] + " ."

    return code

total = 0

for case in cases:
    start_time = time.time()

    s = metagolf(case)
    print(len(s), time.time() - start_time)
    total += len(s)
    print(s)
    print('='*50)

print(total)

```

The relevant function is the aptly named `metagolf`.

The results are:

```
210
676
684
2007
1463
2071
2204
2530
Total: 11845

```

You can find the full output here.

### Brief explanation

I'm going to keep the explanation brief since there's many things still to be improved.

The basic algorithm just looks at pairs of chars, and finds the optimal way to transition from one char to another via BFS. Digits are currently pushed and printed immediately, although this will be changed later.

There's also a little longest-common-subsequence going on, to leave a few elements on the stack for reuse later. It's not as good as repetition, but provides decent savings.

# Answer
> 5 votes
# JavaScript, ~~25158~~ 23778

Now ES5-compatible!

```
String.prototype.repeat = String.prototype.repeat || function (n) { return Array(n+1).join(this); }

function starrify(x) {
  function c(x){return x.charCodeAt()}
  var char = x[0], result = ' '.repeat(c(char)+5)+'+ + .';
  x=x.slice(1);
  for(var i in x) {
    if (char < x[i]) {
      result += ' '.repeat(c(x[i])-c(char)+5)+'+* + .';
    } else if (char > x[i]) {
      if(c(char)-c(x[i]) < c(x[i])) {
        result += ' '.repeat(c(char)-c(x[i])+5)+'+ * + .';
      } else {
        result += ' '.repeat(c(x[i])+5)+'+ + .';
      }
    } else {
      result += ' + .';
    }
    char = x[i];
  }
  return result;
}

```

Results:

```
432
949
2465
3996
1805
3551
5205
5375
Total: 23778

```

A good start in my opinion, but obviously not finished. Instead of creating each char separately, it adds or subtracts from the previous char code. I'll add an full explanation when I'm done meta-golfing.

# Answer
> 2 votes
# C++, score: 9708

Uses an A\*-like search algorithm (i.e. what used to be A\* but was tweaked a lot so that it doesn't run out of RAM and searches fast enough, at the cost of finding non-optimal solutions), where the possible actions from a state are:

* Print a character (if it's the next character needed)
* Execute a precomputed sequence of commands to push the next character needed onto the stack
* Execute a precomputed sequence of commands to change the top of the stack number to the next character needed
* Duplicate the top of the stack, as long as that won't increase its size beyond 5
* Swap the top 2 items on the stack
* Rotate the top 3 items on the stack

Uses an algorithm extremely similar to the one used in MegaTom's Ruby answer to compute the sequences of commands mentioned (however it's slightly better, as it uses more possible transitions).

Doesn't handle digits as special, easier-to-print characters; the score would be even lower if it would.

The complete source code:

```
#include <x86intrin.h>
#include <iostream>
#include <streambuf>
#include <bitset>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>
#include <climits>
#include <random>
#include <set>
#include <list>
#include <map>
#include <unordered_map>
#include <deque>
#include <stack>
#include <queue>
#include <string>
#include <iomanip>
#include <unordered_set>
#include <thread>

//std::string shortestpath(int from, int to);
//std::string shortestpath(int to);
std::string shortestpath(int to, bool grown = false);
std::string shortestpath(int from, int to, bool grown = false);
std::map<std::pair<int,int>, std::pair<std::string, bool>> cache2;
std::map<int, std::pair<std::string, bool>> cache1;
std::string shortestpath(int to, bool grown)
{
    if(cache1.count(to) && (grown || cache1[to].second == false)) return cache1[to].first;
    std::vector<std::string> paths;
    paths.push_back(std::string(to + 6, ' ')); paths[0].back() = '+';
    for(int i = 1; i < to - 1; i++)
        paths.push_back(shortestpath(i, grown) + shortestpath(i, to, grown));
    cache1[to] = {*std::min_element(paths.begin(), paths.end(), [](auto a, auto b){return a.size() < b.size();}), false};
    return cache1[to].first;
}
std::string shortestpath(int from, int to, bool grown)
{
    if(to > 512 || from > 512) return "qwertyuiopqwertyuiopqwertyuiopqwertyuioqwertyuiopqweryuiopqwertyuiopqwertyuiopqwertyuioqwertyuiopqwertyuiopqwertyuiopqwertyuiopqwertyuiop";
    //printf("from=%d, to=%d\n", from, to);
    if(cache2.count({from, to}) && (grown || cache2[{from, to}].second == false)) return cache2[{from, to}].first;
    std::vector<std::string> paths;
    if(from == to) paths.push_back("");
    if(from > to) paths.push_back(shortestpath(from - to, grown) + " *");
    if(from > to && from > 0) paths.push_back(" + *" + shortestpath(0, to, grown));
    if(from > to && from > 1) paths.push_back(" +   *" + shortestpath(1, to, grown));
    //if(from > to) paths.push_back("    +" + shortestpath(to, grown));
    if(from > to)
        for(int i = to + 1; i < from; i++)
        {
            if(from % i == to) paths.push_back(shortestpath(i, grown) + "    *");
            if(from / i == to) paths.push_back(shortestpath(i, grown) + "   *");
        }
    if(from < to && from > 1 && (from*from <= to || !grown))
    {
        bool ng = from*from > to;
        paths.push_back(" +  *" + shortestpath(from*from, to, grown | ng));
    }
    if(from < to && from > 0 && (from+from <= to || !grown))
    {
        bool ng = from+from > to;
        paths.push_back(" +*" + shortestpath(from+from, to, grown | ng));
    }
    if(from < to && from > 1 && to >= 2 * from) paths.push_back(" +"+shortestpath(from,to/from, grown)+"  *" + shortestpath(to/from*from, to, grown));
    if(from < to && from > 1 && to >= 2 * from && !grown)
    {
        bool ng = (to/from+1) * from > to;
        paths.push_back(" +" + shortestpath(from, to/from + 1, grown + ng) + "  *" + shortestpath((to/from+1)*from, to, ng));
    }
    if(from < to && from > 0 && to >= 2*from) paths.push_back(" +"+shortestpath(from,to-from, grown)+"*");
    if(from < to) paths.push_back(shortestpath(to-from, grown)+"*");
    cache2[{from, to}] = {*std::min_element(paths.begin(), paths.end(), [](auto a, auto b){return a.size() < b.size();}), grown};
    return cache2[{from, to}].first;
}
std::string target;
struct astate
{
    std::vector<int> stack;
    int i = 0;
    int heur() const
    {
        return 3 * (target.size() - i);
    }
    bool operator < (const astate& rhs) const
    {
        if(i != rhs.i) return i > rhs.i;
        return stack < rhs.stack;
    }
};
struct sstate
{
    astate as;
    int f;
    bool operator < (const sstate& rhs) const
    {
        if(f != rhs.f) return f < rhs.f;
        if(as.heur() != rhs.as.heur()) return as.heur() < rhs.as.heur();
        return as < rhs.as;
    }
};

int metagolf(std::string target)
{
    std::map<int, int> icounts;
    int hw = 2;
    ::target = target;
    sstate start = {{{}, 0}, 0};
    std::map<astate, std::pair<astate, std::string>> prev;
    std::map<astate, int> dists; dists[start.as] = 0;
    std::set<sstate> openset; openset.insert(start);
    bool done = false;
    //int itsleft = 100;
    astate beststate = start.as;
    while(!openset.empty())
    {
        auto it = openset.begin();
        auto[cs, cf] = *it; openset.erase(it);
        icounts[cs.i]++;
        if(icounts[cs.i + 3] > 250) continue; //{ printf("continuing: i=%d\n", cs.i); continue; }
        int cd = dists[cs];
        if(cs.i == target.size()) { done = true; beststate = cs; break; };
        //print
        if(!cs.stack.empty() && cs.stack.back() == target[cs.i])
        {
            auto next = cs;
            int dist = cd + 2;
            next.i++; next.stack.pop_back();
            if(dists.count(next) == 0 || dist < dists[next])
            {
                dists[next] = dist;
                openset.insert({next, dist + hw*next.heur()});
                prev[next] = {cs, " ."};
            }
        }
        //shortestpath from
        if(!cs.stack.empty())
        {
            auto next = cs;
            std::string path = shortestpath(cs.stack.back(), target[cs.i]);
            int dist = cd + path.size();
            next.stack.back() = target[cs.i];
            if(dists.count(next) == 0 || dist < dists[next])
            {
                dists[next] = dist;
                openset.insert({next, dist + hw*next.heur()});
                prev[next] = {cs, path};
            }
        }
        //shortestpath to
        {
            auto next = cs;
            std::string path = shortestpath(target[cs.i]);
            int dist = cd + path.size();
            next.stack.push_back(target[cs.i]);
            if(dists.count(next) == 0 || dist < dists[next])
            {
                dists[next] = dist;
                openset.insert({next, dist + hw*next.heur()});
                prev[next] = {cs, path};
            }
        }
        //dup if size below 5
        if(!cs.stack.empty() && cs.stack.size() < 5)
        {
            auto next = cs;
            int dist = cd + 2;
            next.stack.push_back(next.stack.back());
            if(dists.count(next) == 0 || dist < dists[next])
            {
                dists[next] = dist;
                openset.insert({next, dist + hw*next.heur()});
                prev[next] = {cs, " +"};
            }
        }
        //swap
        if(cs.stack.size() >= 2)
        {
            auto next = cs;
            int dist = cd + 3;
            std::swap(next.stack.back(), next.stack[next.stack.size() - 2]);
            if(dists.count(next) == 0 || dist < dists[next])
            {
                dists[next] = dist;
                openset.insert({next, dist + hw*next.heur()});
                prev[next] = {cs, "  +"};
            }
        }
        //rot
        if(cs.stack.size() >= 3)
        {
            auto next = cs;
            int dist = cd + 4;
            std::swap(next.stack.back(), next.stack[next.stack.size() - 2]);
            std::swap(next.stack[next.stack.size() - 3], next.stack[next.stack.size() - 2]);
            if(dists.count(next) == 0 || dist < dists[next])
            {
                dists[next] = dist;
                openset.insert({next, dist + hw*next.heur()});
                prev[next] = {cs, "   +"};
            }
        }
    }
    astate cur = beststate;
    std::vector<std::string> code;
    while(cur < start.as || start.as < cur)
    {
        auto[pr, path] = prev[cur];
        code.push_back(path);
        cur = pr;
    }
    std::reverse(code.begin(), code.end());
    std::string ans;
    for(auto s : code) ans += s;
    printf("%s\n", ans.data());
    return ans.size();
}

int main()//int64_t argc, char*argv[])
{
    int ans = 0;
    for(int from = 0; from < 256; from++)
    for(int to = 0; to < 256; to++)
    {
        auto p = shortestpath(from, to);
        int len = p.size();
        ans += len;
        //if(len < 35) continue;
        //printf("%d->%d: %d\n", from, to, p.size());
        //printf("%s\n", p.data());
    }
    printf("total length of all transitions within [0, 256): %d\n", ans);
    std::vector<std::string> targets { "Hello, World!", "pneumonoultramicroscopicsilicovolcanoconiosis", ".oOo.oOo.oOo.oOo.oOo.oOo.oOo.oOo.oOo.oOo.oOo.", "Hickory, dickory, dock. The mouse ran up the clock. The clock struck 1. The mouse ran down. Hickory, dickory, dock.", "36912059868043514648560046917066768694455682545071266675083273015450033938555319356951628735735013250100789433961153496780296165", "bVZ48121347GLtpYnt76CZSxTpMDs6791EJE808077eySXldY162424ddTB90707UupwlWGb63618542VhA252989453TXrWgqGm85899uHOAY2oAKE198GOVUttvW63", "7MYxoWBNt180CDHS5xBGvU70HHVB17bh8jYzIIiU6n6g98Rose1nOe8Svcg56nax20q30kT3Ttb2jHl5q2Iuf1vPbjPxm9cyKXwxc0OUK8pr13b2n7U9Y7RwQTc26A1I", R"T(n9}unwxVa}[rj+5em6K#-H@= p^X/:DS]b*Jv/_x4.a5vT/So2R`yKy=in7-15B=g _BD`Bw=Z`Br;UwwF[{q]cS|&i;Gn4)q=`!G]8"eFP`Mn:zt-#mfCV2AL2^fL"A)T" };
    int res = 0;
    for(std::string target : targets)
    {
        int len = metagolf(target);
        res += len;
        printf("%d\n", len);
    }
    printf("total length of all programs: %d\n", res);
}

```

Output:

```
total length of all transitions within [0, 256): 1425541
        + +* +  * +* .      +          + +* +  ** + . +            +* + . + . +        +* + .                + +* +* + .         + +  * +* . +*      + * . + .        +* . .      + * .                + + +** .
208
            + + +  ** +* + .       + * + . +        + +  * * . +            +* + .  + +      + * . +      +* + .  + . + .  + . +        + * . +          +* . + +        +* + .  + +            + +* * + .  +       + * + .         + * .       +* + .   + . + . +         +* + .   +  + + .  + + .      +* . +           +* + .   + + .   + . + . +        +* + .   + . + .  + +        +* + . +            +* . + .   + . + . +       + * .  + +      + * + .   + + .  + . + .  + + .          + * + .  + + .         +* + .  + . .
517
       + + +* + +* + +* +**** + . +        + + + +* +  *  ** + . +         + +  * +* * + .   + + .  + . + .  + + .   + + .  + + .   + + .  + + .   + + .  + + .   + + .  + + .   + + .  + + .   + + .  + + .   + + .  + + .   + + .  + + .   + + .  + + .   + + .  + + .   + + .  + + .   + + .  + + .   + + .  + + .   + + .  + + .   + + .  + + .   + + .  + + .   + + .  + + .   + + .  + . . .
386
        + +* +  * +* .          + + +* +  ** + . + +           + * + .  +       +* + .         +* + .        +* + .            +* .                + +* +* + .         + +  * +* .   + +      +* .  + + .  + + .   +       +* + .         +* + . +        +* + .            +* .   + .         + +  * +* + .   + +      +* .  + + .   + + . +         + +** .  + +            + +** . + .  + +          + + +** * . +          +* .       +* + .   + + .   + +       + * . + .           +* + . +       + * .   + + .   + + .   + +        + * .   + +         + * . +        + +  ** .   + + .  + + . +          + * .  + + .   +      + * . +        +* + .   + . + .  + + +          + * + .  +         +* + .        +* . + .   + +        +* .  + +            + +** . + .  + +          + +* +* * . + .        + * . + .  + + . +        + +  ** + . +        +* .  + + .   +      + * + .  + + .   + +         + +** + . +      +* . +      + * .       +* .  + . . + .            + +  * + .        + * . + . + +        + + +  * +  ** + .          + +* +** + .        + * + .  + . +         + +** + .       +* + .           +* + .       + * + .   + + .   + .      + * . +         + * . +        + +  ** + .   +  + + .   +      + * + .   + +      +* + . +         + +** .   + . +            + +** . + . + +*         + +** .  + +           + * + . +           + * .       +* . + .        +* + .            +* . +        + +* +** + .   + + .   + + . +          +* + .  +      + * .       +* + . +         +* + .        +* + .            +* .   + + .   + . + +            + * + .  +         +* .      + * . .       +* .
1588
        + + +* +* +* +** + . + +        +* + .        +* + .  + +       + * + . +      +* .      + * + .   +       +* . + .      + * + . +       + * . . + .  + +      +* + .  + . +      +* . +        + * . + . + +       +* + .  + . +       +* . +      + * . + .   +  + + . + .   + . + . +        +* + .   + +          + * . +      +* .  + . + . + . +      +* . + . +       +* . + .  + . + +       + * + . + .      +* + . + .  + + .       +* . + +        + * + .  + + . +      + * . . +       + * . +          +* . +      + * . .  + + . + . . + + +       +* + .  + + .          + * . +      +* . +         + * + . +      + * .  + . + .        + * + . +      +* .  + + . +      + * . . + . . + +       + * + . + . +           +* . + .  + + +        +* . . + . . + . +       + * + .   + +           +* . . + . +      +* + . +        +* .   + + .   + . + . +         + * . +       +* .      +* . + + +       + * + .  + + .       +* . + .  + . +        + * + . +      +* .   + + . +      + * .   + . + . +      +* . + . . + +         +* + .      +* + .      +* + .  + +      +* . + . . + .  + +        +* + .  + +       + * + . . +       +* . + .      +* .  + + .  + + . +      +* + .      +* . +           + * + .       +* .  + . + . +          + * . + .      + * .
1261
            + +  * +* + .        + +* +* * + .         +* + . +         + + +  * + +*** + . +         +* . +        + * + . +      +* . . +      + * . + .        +* + . +         + +  ** + .          +* . + +*           +* + . +         + * .   +  +      + * . + +* .  + . + . +      + * + .   + +        + +* +** + .   +  + + .            + * + .          + +* + + +  *** .      +* . +*       +* + .  + +          + +** .      +* + .   +        +* . + . +      +* + .       +* . +          + * .  +      +* + . +          +* . . +       +* + . +         + +* * + .  + . . +      +* + . . + + +*            + * + . +          + +* +** . +        + +  * +* * + .          +* + .   +  + +* .      + * .      +* . +          + * + .  + . +      +* + . + +       +* + .  + . . + +* + . + .         + +  * * .         + +  ** . +         + +** . +      + * + . +            +* + .  + . . +        + +* +  ** + . +         + +  * +** + . +          + * + .  +       +* .         + * .       +* + .         + +  * * . + +* . +          +* + . +        + * . + .  + .       +* + . +        + * + . +      + * + . +       + * + . +        + +* +  ** .   + +* . +        + +* +** .  + + .  + . . + +      +* + .  + . + . +          + * + . +      +* .      + * + .  +        + + +  * +  ** + .         +* + .  + +* .      + * . +*      +* . + +*      +* . + + +          + + +*** + .  + + +*        + * . + . +        + * . + .      +* + . + . +*        +* . +      +* . +         + +** . +           + * + .   + +        + +  * +** .   + +           + * . +*      + * . . +         +* . +       + * .  + +            + * . +      +* + .   + . + .         + +** + .            +* + . +      + * .  + + +*       +* + . + .       +* .  +      +* .        + * + .        + * .
1763
          + + +  * +** + . + +                + +** + . +        + +* +** .  + + +*          + +** + .   + +*      +* . +          + +** . +                + * + .   +      +* . +         + * .            + +  * + . +            +* .      + * .   + +      +* + . +      +* . +          +* .         + +  ** .   + +       + * .   + + .  + + . +          +* .   +       + * . +          + + +  *** . + . +            + * .  + +           +* + . + .            + +** . . + + +           + * + .  + . +* + .           +* + .  +      +* . +       +* . + +          + + +** * + .  +        + +  * +** . +         + +  * * + . .  +      +* .         + * . + +      + * + .  + +* + .  + + . + +*          + * .        +* + . +      + * .          + +  ** + .  + +      +* + .         +* . +        + +  * * + .            + +  * .   + . +        + * .   + + .   + +      +* .   + +      +* .        + +* +  ** + .   + +       + * + .   +       +* . +       + * + .      +* . +* .       + * . +       +* . +          + +  * +* + .       + * + .  +          + * . +        +* + .  + . + +*          +* .        + + +  * +  ** + .  + + .   + . +       + * .  + + +*         + * . +      + * . + +*         +* + .        + +* +  * +* + .   +       +* . +       +* + . +*            +* . +      + * .   + +      +* .   + +      + * .  + + +* .       + * + .  + . +         + + + +  **  * + .  + +* + .         + +** + .  + . +            + +** + .   +        +* . +         + +** . + +*      +* .   + +      +* .  + +        +* + .   +         + +  ** . +      + * . .  + + +*      +* . +      + * .  + +         +* + .           +* + .   + . +            +* + . + +* + .       +* .  + + . +       +* . + +* . +      +* .   + + +*       + * .      + * + .  + + .  + +       +* + .   +  + +         +* .  + .        + * + .  + +*          +* . +      + * .       +* . + +*      +* . +      +* + .         +* . +         + +  ** + .  + .         + +** .
1938
          + +* + +  ** + .        + + + +  * +*  ** + .  + +          + + +*** + .  + +            +* + .  + .       +* + .      +* + .   + +        + + +* +  ** * + . +                +* .  + .          +* . + +* + .         + +* * . +            + +* * + . +          + +** + . + +*          + * . + +*        +* .      +* . +         + +  * +** + .  + +         + +* * .       +* + .   +        + * + .   + +            +* . +         +* .         + +  * +* . + +*       + * .  + + +*         +* . + +*       + * .       +* + .  +      +* + . +          + +** .          + +  ** . + +*      + * + .          +* . +          + * .   +       +* . +       + * + .   +  + + . + +*      +* .  + . + +          +* + .  + +      + * . +*        +* .      +* + .   +  + . + + +*          + +* * + .  + .      + * + .  + +         + +* +  ** . +        +* .  +      + * . +*       +* + . +          + +  ** + .          + +  * + +** . .  + +         + +** + .  + + +*      + * + .          +* . +       +* . +         + +* * + .         +* . . +          +* + .   + + .   + +            +* .         + +  * +* . +      + * .  + + . +       +* .  + + .   + . + +*        + * + .   + + .  + +           + * + .   + . +          +* . + +*         + +* * .       + * + .   + +          + * .  + + . + .  + +          + +* +* * .      +* + .  + +         +* + .   +           + * .       +* + . +           +* . +          + +* * .   +      +* . + +            + + +** * + .          + + +* +  ** .  + . + +*          + * . + + +*         + ** + .  + +            + +** .        +* . +        +* .   +       +* + .  + +        +* .                + + +** + . + +*          +* .   + . +          + * .   +      +* + . + + +*      + ** . + +*       +* + .          + +** + . +         + +  ** .        + * .   + . +        + * + .  + +* . +* . + +                +* + .  + +      +* + . + +*         +** . + + +** + .   + +*      + * + .  + + +*         + * .          +* + .  + +       + * .        + +  ** + .   + . +         + +* * . . . + . +*        + * .
2047
total length of all programs: 9708

```

---
Tags: metagolf, stack, starry
---


# Question
Title: Number of solutions to a binary weight equation
We define \\$a(n)\\$ as the 1-indexed position of \\$n\\$ in the sequence of positive integers with the same binary weight, i.e. the same number of 1's in their binary representation. This is A263017.

Given a positive integer \\$n\\$, your task is to determine how many positive integers \\$k\\$ satisfy:

$$k-a(k)=n$$

For instance, \\$n=6\\$ can be expressed as:

* \\$n=7-a(7)=7-1\\$ (\\$7\\$ being the 1st integer with 3 bits set)
* \\$n=12-a(12)=12-6\\$ (\\$12\\$ being the 6th integer with 2 bits set)

There's no other \\$k\\$ such that \\$k-a(k)=6\\$. So the expected answer is \\$2\\$.

This is .

### Test cases

```
Input Output
1     1
6     2
7     0
25    4
43    0
62    1
103   5
1000  0
1012  6
2000  1
3705  7
4377  8

```

Or as lists:

```
Input : [1, 6, 7, 25, 43, 62, 103, 1000, 1012, 2000, 3705, 4377]
Output: [1, 2, 0, 4, 0, 1, 5, 0, 6, 1, 7, 8]

```

# Answer
# MATL, 15 bytes

```
t4*:tB!s&=Rs-=s

```

Try it online! Or verify all test cases.

This makes use of the following result:

## Claim

\\$a(n) \le 3n/4\\$ for \\$n \geq 3\\$.

Here is a graphical illustration. The bound is quite loose, but it is sufficient to establish that only a *finite* number of values of \\$k\\$ need to be tested for a given \\$n\\$ (more on that in “How the code works”).

**Proof**

The sequence \\$a(n)\\$ (A263017) is the amount of numbers in the set \\$\\{1,2,\ldots,n\\}\\$ that have the same binary weight as \\$n\\$. The binary expansion of \\$n\\$ has \\$b \leq \log\_2 n + 1\\$ digits, with a leading 1. Let \\$w\\$ be the binary weight of \\$n\\$. Clearly \\$w \in \\{0,\ldots,b\\}\\$.

The number of unique permutations of the binary expansion of \\$n\\$, not necessarily with a leading 1, is \\${b\choose w}\\$. \\$a(n)\\$ will be at most equal to this value. It can be less, because some of the permutations may produce a number exceeding \\$n\\$. Thus,

$$ a(n) \leq {b\choose w}. $$

For \\$b\\$ even, the bound

$$ {2m \choose m} \leq \frac{4^m}{\sqrt{3m+1}} \text{ for all } m \geq 1 $$

and the fact that \\${b\choose w} \leq {b\choose b/2}\\$ imply that

$$ {b \choose w} \leq \frac{2^b}{\sqrt{\frac{3b+2}{2}}}. $$

For \\$b\\$ not necessarily even, the bound holds with \\$b\\$ replaced by \\$b+1\\$:

$$ {b \choose w} \leq \frac{2^{b+1}}{\sqrt{\frac{3b+5}{2}}}. $$

Since \\$b \leq \log\_2 n + 1\\$,

$$ a(n) \leq {b\choose w} \leq \frac{2^{b+1}}{\sqrt{\frac{3b+5}{2}}} \leq \frac{4n}{\sqrt{ 3/2 \cdot \log\_2 n + 4}}. $$

This is less than \\$3n/4\\$ for \\$n \geq 80478\\$, because

$$ \sqrt{3/2 \cdot \log\_2 80478 + 4}\ = 5.3333348 \> 16/3. $$

For \\$n = 3, \ldots, 80477 \\$, direct computation of \\$a(n)\\$ shows that \\$a(n) \leq 3n/4\\$. Therefore \\$a(n) \leq 3n/4\\$ for \\$n \geq 3\\$.

## How the code works

The above result implies that

$$ k-a(k) \geq k / 4. $$

for all \\$k \geq 3\\$. Thus, given \\$n\\$, to compute the number of positive integers \\$k\\$ that satisfy

$$ k-a(k)\ = n $$

it suffices to test the latter equality for \\$k = 1, \ldots, 4n\\$.

Consider input `1` as an example.

```
t4*  % Implicit input: n. Duplicate. Multiply by 4
     % STACK: 1, 4
:    % Range. Gives [1 2 ... 4*n]. This is the vector of k values
     % STACK: 1, [1 2 3 4]
tB   % Duplicate. Binary expansion. Gives a binary matrix, where each row
     % corresponds to a value of k
     % STACK: 1, [1 2 3 4], [0 0 1;
                             0 1 0;
                             0 1 1;
                             1 0 0]
!s   % Tranpose. Sum of each column. This gives the binary weights
     % STACK: 1, [1 2 3 4], [1 1 2 1]
&=   % Matrix of pair-wise equality comparisons
     % STACK: 1, [1 2 3 4], [1 1 0 1;
                             1 1 0 1;
                             0 0 1 0;
                             1 1 0 1]
R    % Upper triangular part. This sets elements below the diagonal to 0
     % STACK: 1, [1 2 3 4], [1 1 0 1;
                             0 1 0 1;
                             0 0 1 0;
                             0 0 0 1]
s    % Sum of each column. For each column k, this gives the amount of
     % number up to k with the same weight as k; that is, a(k). Note that
     % the condition "up to k" corresponds to having taken the upper
     % triangular part of the matrix
     % STACK: 1, [1 2 3 4], [1 2 1 3]
-    % Subtract, element-wise. This gives k-a(k)
     % STACK: 1, [0 0 2 1]
=    % Equality comparison, element-wise. This compares n with each
     % value k-a(k)
     % STACK: [0 0 0 1]
s    % Sum. Implicit display
     % STACK: 1

```
> 12 votes

# Answer
# Python 3, ~~98~~ 96 bytes

Saved 2 bytes thanks to Surculose Sputum!!!

```
lambda n:sum(n==sum(bin(i).count('1')!=bin(k).count('1')for i in range(1,k))for k in range(5*n))

```

Try it online!

Brute force and very slow.
> 5 votes

# Answer
# C (gcc), ~~106~~ \\$\cdots\\$ ~~100~~ 96 bytes

Saved 5 bytes thanks to the man himself Arnauld!!!
Saved ~~1~~ 5 bytes thanks to l4m2!!!
Saved 4 bytes thanks to ceilingcat!!!

```
b(n){n=n?1+b(n&n-1):0;}k;i;s;p;f(n){for(p=0,k=5*n;i=k--;p+=n==s)for(s=0;--i;)s+=b(i)!=b(k);s=p;}

```

Try it online!

Port of my Python answer, ~~much~~ a bit faster.
> 2 votes

# Answer
# APL (Dyalog Unicode), 41 bytesSBCS

```
{1⊥⍵=i-+⌿(⊢×∘.≤⍨∘⍳∘≢)∘.=⍨+⌿2∘⊥⍣¯1⊢i←⍳4×⍵}

```

Try it online! (Assumes ⎕IO ← 1)

This is a direct translation of Luis Mendo's really good answer so go give that one an upvote if you haven't.

**How it works** (reading the submission from right to left):

* `i←⍳4×⍵` multiply the input ⍵ by 4, create a range from 1 to 4⍵ and save it in the variable i for later;
* `2∘⊥⍣¯1` create a matrix of binary conversions (one col per number);
* `+⌿` column-wise sum;
* `∘.=⍨` matrix of pair-wise equality comparisons;
* `(⊢×∘.≤⍨∘⍳∘≢)` from which we extract the upper triangular part;
* `+⌿` column-wise sum again;
* `i-` the original range 1 ... 4⍵ minus the new vector;
* `⍵=` compared to the input number;
* `1⊥` and summed up.
> 1 votes

# Answer
# JavaScript (Node.js), 70 bytes

```
n=>f=(i=g=i=>+i&&1+g(i&i-1))=>i>5*n?0:(i-(g[j=g(i)]=-~g[j])==n)+f(-~i)

```

Try it online!

# JavaScript (Node.js), 81 bytes

```
n=>[...Array(n*5)].reduce(s=>s+=++i-(g[j=g(i)]=-~g[j])==n,i=0,g=i=>i&&1+g(i&i-1))

```

Try it online!

Thank Arnauld for -3 bytes
> 1 votes

# Answer
# C (gcc), 71 bytes

```
i,k;f(n){int C[99]={};for(i=k=0;i++/n/5<=k;)k+=i-++C[*C+=2-ffs(i)]==n;}

```

Try it online!

WTF is happening?

# C (gcc), 72 bytes mainly by dingledooper

```
i,k;f(n){int C[99]={};for(i=k=0;i++<5*n;)k+=i-++C[*C+=2-ffs(i)]==n;i=k;}

```

Try it online!

# C (gcc), 79 bytes

```
k;f(n){int C[99]={};for(k=0;k++<5*n;)*C+=k-++C[__builtin_popcount(k)]==n;k=*C;}

```

Try it online!

Port of my Javascript answer
> 1 votes

---
Tags: code-golf, binary, counting
---


# Question
Title: Humans hate pows and programmers hate humans - let's connect them!
# Background

The task is simple but every programmer has implemented it at least once. Stackoverflow has a lot of samples, but are they short enough to win?

# Problem story

You're a grumpy programmer who was given the task of implementing file size input for the users. Since users don't use bytes everyone will just enter "1M", "1K", "3G", "3.14M" - but you need bytes! So you write a program to do the conversion.

Then your manager hands you dozens of user reports with complaints about weird large numbers in file size input. It seems you'll need to code the reverse conversion too.

# What do you need to do?

Here's the trick: you should implement two-way conversion in single piece of code. Two separate functions used as needed? Nah, that's too simple - let's make one, short one!

For the purposes of this challenge, "kilobyte" means 1024 bytes, "megabyte" means 1024\*1024 = 1048576 bytes, and "gigabyte" means 1024\*1024\*1024 = 1073741824 bytes.

# Test data

```
Input   -> Output
5       -> 5
1023    -> 1023
1024    -> 1K
1K      -> 1024
1.5K    -> 1536
1536    -> 1.5K
1048576 -> 1M
1M      -> 1048576

```

# Rules

* Test value will not exceed 2\*1024\*1024\*1024 or 2G
* The following postfixes are used by users: K for kilobytes, M for megabytes, G for gigabytes
* Code is not required to work with negative numbers
* Do not use any external libraries (e.g. `BCMath` in PHP) besides bundled ones (e.g. `math.h`)
* Standard loopholes are disallowed
* Code should not produce anything on stderr
* Your program can take input and produce output using \[standard methods\].(http://meta.codegolf.stackexchange.com/questions/2447/default-for-code-golf-input-output-methods)

# Answer
> 3 votes
# Python 2, ~~204~~ 190 bytes

This is my first ever codegolf.

```
s=raw_input()
p=' KMG'
if s[-1]<='9':
 e=0;r=int(s)
 while r>=1024:r/=1024.0;e+=1
else:
 e=p.index(s[-1]);r=eval(s[:-1])
 while e>0:r*=1024;e-=1
print(`r`if r%1!=0 else`int(r)`)+p[e].strip()

```

# Answer
> 2 votes
# Pip, 60 bytes

```
l:" KMG"Fi1,4Ia>=Y1024x:(a/:y).l@ix|aR`.+([KMG])`_*y**(l@?B)

```

Takes input from the command line (assigned to `a` variable) and outputs to stdout.

**Ungolfed version:**

```
l : " KMG"
Y 1024
F i 1,4
 I a>=y {
  a /: y
  x : a . l@i
 }
x | a R `.+([KMG])` {a*y**(l@?b)}

```

**Algorithm:**

* For `i` from 1 through 3:
    + If `a >= 1024`, this is a byte value that needs to be converted to a larger unit:
        - Divide `a` by 1024
        - Set `x` to be the current value of `a` concatenated with the current unit
* If `x` was set by the previous step, output it. Otherwise, `a` was less than 1024 (with a possible unit suffix), so:
    + Do a regex replacement with a function on `a` if it has one of `KMG` at the end: translate the letter to the appropriate power of 1024 and multiply the number by the result.
    + For values less than 1024 without a suffix, this leaves the value unchanged.

# Answer
> 1 votes
# JavaScript, ~~144~~ 106 bytes

```
n=>((G=(M=(K=2<<9)<<10)<<10),+n>0?n<K?n:n<M?n/K+'K':n<G?n/M+'M':n/G+'G':eval(n.replace(/[KMG]/,m=>'*'+m)))

```

This can definitely be shortened, and will do later. Just wanted to get something ugly out there ;)

# Answer
> 1 votes
## C ~~206~~ 183 bytes

Got rid of as much as I could.

```
#include<stdlib.h>
main(y,z)char**z;{char*i="KMG";float f=atof(*++z);while(*++*z)y=**z;if(y>57){do f*=1024;while(y!=*i++);y=0;}else while(f>1023)y=*i++,f/=1024;printf("%.1lf%c",f,y);}

```

### Output

```
Input: 1023
Output: 1023.0

Input: 1M
Output: 1048576.0

Input: 1048576
Output: 1.0M

```

### Explanation

```
#include <stdlib.h> //needed for atof()
main(y,z)char **z; //y will hold the size indicator
{
    char *i="KMG";//holds the characters for the size indicators
    float f=atof(*++z); //get the number from the string

    while(*++*z) //loops through the string
        y=**z;
    if(y>57) //57 is ASCII for 9
    {
        do f*=1024;
        while(y!=*i++); //loop through until we hit the correct size
        y=0;
    }
    else
        while(f>1023) //loop through until number is less than 1024
            y=*i++,f/=1024;
    printf("%.1lf%c",f,y); //print number and size character
}

```

# Answer
> 0 votes
# Python2 199 bytes

this is silly but it works (ignoring the decimal precision question) as long as you have dozens of gigabytes of RAM. dont run it otherwise, your machine might freeze and lockup. The first thing it does is allocate a 2gigabyte array of integers.

```
n,bn={'K':2**10,'M':2**20,'G':2**30},range(2**30+1)
for i in bn:
 for j in 'KMG':
  if i>=n[j]: bn[i]=str(float(i/n[j]))+j
def f(i):
 if i[-1] in 'KMG': return n[i[-1]]*float(i[:-1])
 return bn[int(i)]

```

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

```
f=(n,m)=>n<1024?n+['.KMG'[m]]:n>0?f(n/1024,-~m):eval(n.replace(/.$/,'*32**$&',K=2,M=4,G=6))

```

Try it online!

# Answer
> 0 votes
# Ruby `-nl`, 100 bytes

```
~/.$/
i,n,s,k=0,$_.to_f,' KMG',1024
$&<?A?((n/=k;i+=1)until n<k):n*=k**(s=~/#$&/)
print n,s[i].strip

```

Try it online!

# Answer
> 0 votes
# C (gcc), 114 bytes

```
*i=L"KMG",d;c;main(S){float f;for(scanf(S="%f%c",&f,&c);c?f*=1024,c-*i++:f>1023?f/=1024,d=*i++:0;);printf(S,f,d);}

```

Try it online!

Thank ceilingcat for -11 bytes

---
Tags: code-golf
---


title: Can I Type This With My Left Hand?

text:
# Question
Title: Can I Type This With My Left Hand?
### Inspiration

The longest words that can be typed with only the left hand on a standard QWERTY keyboard are "sweaterdresses", "tesseradecades", and "aftercataracts" (Source: Wikipedia).

### Challenge

Given as input a "keyboard" \\$K\\$ and a string \\$S\\$ determine whether \\$S\\$ can be typed using only the left hand on keyboard \\$K\\$.

### Input

The keyboard \\$K\\$ will be provided as a list of 3 *rows*. You may take this input in any reasonable format (eg. a list of 3 strings, a list of 3 lists of characters, etc.), but please do not take the left-hand-side and right-hand-side of the keyboard separately, as that defeats the purpose of the challenge.

You may assume that the input contains only lowercase letters (or only uppercase letters if you wish). Each of the three rows of the keyboard may be of any non-zero size, but each letter from `a-z` will appear only once on the keyboard.

Example 1: \[`qwertyuiop`, `asdfghjkl`, `zxcvbnm`\]

Example 2: \[`qazwsxplkm`, `edcrfv`, `tgbyhnuji`\]

The string \\$S\\$ may also be taken as input in any reasonable format.

### Output

Output a truthy value if the string \\$S\\$ can be typed using the left hand on the keyboard \\$K\\$ and a falsey value otherwise.

**For the purposes of this challenge**: A word can be typed with the left hand if it is made up solely of letters appearing in the first half of each row of the keyboard. If a row contains an odd number of letters, the **middle letter is also included** in the first half.

Using the row `asdfghjkl` as an example, the word `gafs` can be typed with the left hand.

### Scoring

This is . Make your code as short as possible.

### Test Cases

These are formatted as \\$K\\$, \\$S\\$ `->` (expected output)

```
[qwertyuiop, asdfghjkl, zxcvbnm], qazg -> true
[qwertyuiop, asdfghjkl, zxcvbnm], qpazg -> false
[p, asdfghjklqwertyuio, zxcvbnm], sxzklkl -> true
[p, asdfghjklqwertyuio, zxcvbnm], b -> false
[qazwsxplkm, edocrfv, tgbyhnuji], bad -> true
[qazwsxplkm, edocrfv, tgbyhnuji], tex -> false
[thequick, brownfx, jmpsvlazydg], brow -> true
[thequick, brownfx, jmpsvlazydg], fox -> false

```

# Answer
# Python 3, 48 bytes

Takes as input \\$ K \\$ and \\$ S \\$, the keyboard and the target string. \\$ K \\$ is a taken as a list of lists.

```
lambda K,S:{r.pop(0)for r in K for i in r}>={*S}

```

Try it online!

## Explanation

It essentially converts \\$ S \\$ and the *valid* keyboard characters \\$ K' \\$ into sets, and returns `True` iff \\$ S \\$ is a subset of \\$ K' \\$. To obtain only the first half of each row of \\$ K \\$, we use the `pop` trick, which is explained in this answer of mine.

---

The previous answer, where \\$ K \\$ is taken as a list of strings instead.

# Python 3, 54 bytes

```
lambda K,S:{*''.join(r[:-~len(r)//2]for r in K)}>={*S}

```

Try it online!
> 8 votes

# Answer
# , 22 21 bytes

```
a:=(-.>.@-:@#$])~&.>/

```

Try it online!

*-1 byte thanks to FrownyFrog*

---

Takes input as boxed words, with the string to test at the end.

Reduces the list, set-subtracting `-.` the first half `-.>.@-:@#` of each row `$]` from the string to test.

Check if the result is empty: `a:=`
> 6 votes

# Answer
# 05AB1E, 8 bytes

-2 thanks to Kevin Cruijssen.

```
ε2ä¬}JÃQ

```

Try it online!

# Explanation

```
ε          For each item of the input list:
 2ä        Split into chunks of size 2
           (conveniently, the middle character is included in the left half)
   ¬}      Take the head of this list
     J     Join the output string
      Ã    List intersection with the input
       Q   is the input

```
> 5 votes

# Answer
# Bash \+ Unix utilities, 57 bytes

```
s()(echo ${1:0:(${#1}+1)/2});grep ^[`s $1``s $2``s $3`]*$

```

Try it online!

The three keyboard rows are passed as arguments, and the input string is passed on stdin.

Output is the exit code (0 for truthy, 1 for falsey).

This can probably be improved with clever golfing.
> 4 votes

# Answer
# Retina 0.8.2, ~~42~~ 34 bytes

```
r`(?<-1>.)+(?<=(\w\w)+),
,
D`\w
,$

```

Try it online! Link includes test cases. Explanation:

```
r`(?<-1>.)+(?<=(\w\w)+),
,

```

The `r` modifier causes the regex to be processed from right to left, so that the `,` is matched first, before the lookbehind then matches as many pairs of letters as possible. .NET captures each matching pair into a stack of values for capture group `1`. The balancing group then matches once for each value in the stack, thus deleting 1 character from the end of the row for every pair of letters.

```
D`\w

```

Remove all duplicate letters.

```
,$

```

Check that no letters of `S` remain.
> 3 votes

# Answer
# Jelly, 9 bytes

```
ŒH€ZḢFfƑ@

```

A dyadic Link accepting a list of lists of characters on the left and a list of characters on the right which yields `1` if the right may be typed with the left hand or `0` if not.

**Try it online!**

### How?

```
ŒH€ZḢFfƑ@ - Link: keys, word
ŒH€       - halve each
   Z      - transpose
    Ḣ     - head
     F    - flatten
        @ - with swapped arguments:
       Ƒ  -   is invariant under?:
      f   -     filter keep

```
> 3 votes

# Answer
# C (GCC) ~~114~~ ~~109~~ ~~108~~ ~~105~~ 102 bytes

-3 bytes ceilingcat

```
i,h,t,r;f(char**k,char*s){for(r=1;*s;++s)for(i=3;i--;)for(h=strlen(k[i]);t=k[i][++h/2];)r*=t!=*s;i=r;}

```

Try it online!
> 3 votes

# Answer
# Google Sheets, ~~106~~ 99 Bytes

```
=ArrayFormula(1-IsErr(Or(Find(Mid(B1,Row(Offset(A1,0,0,Len(B1))),1),Join(,Left(A:A,Round(Len(A:A)/2

```

Keyboard input is in the range `A1:A3`. The word is input in `B1`. After entering the formula, Sheets will automatically add 7 trailing parentheses.

`Join(,Left(A:A,Round(Len(A:A)/2)))` combines the left-hand side of the keyboard rows into a single string we can search later.

`Mid(B1,Row(Offset(A1,0,0,Len(B1))),1)` pulls each letter of the word, one character at a time.

`Or(Find(Mid(~),Join(~)))` searches for each character in the search string and returns the location of each (a positive integer). If it can't find the character, it returns the `#VALUE!` error. Therefore, `Or(~)` returns either `TRUE` or `#VALUE!`.

`1-IsErr(Or(~))` returns `1` for `TRUE` and `0` for `#VALUE!`.

`ArrayFormula(~)` makes all these pieces work on input and output arrays instead of individual cells. This only matters for joining the input keyboard into a string and pulling out one character at a time from the word.

---
> 3 votes

# Answer
# JavaScript (Node.js), 51 bytes

```
k=>s=>s.every(c=>k.some(l=>l.length/l.search(c)>2))

```

Try it online!

Input keyboard as an array of three strings. Input the word as an array of characters.
> 2 votes

# Answer
# x86 32-bit machine code: ~~34~~ 31 bytes

Strategy: build a bitmap of left-hand keys with bit test-and-set (`bts`), then loop over the input string and check against that bitmap (`bt`). 386 `bt*` instructions with a register destination mask the bit-index like shifts do, so we can use ASCII characters directly as bit indices. (0x61 .. 0x7a)

Inputs:

* EDI: `const char *str` (0-terminated C string)
* ESI: points at rows serialized into 3 back-to-back explicit-length strings in a buffer. 3x { dword length, char\[\] }, no indirection just flat byte stream concatenated to be loaded with lodsd / lodsb. Asm wrapper to do this conversion from an array of 3x `char*` included with the test harness on TIO.

Output: AL=first non-left-hand character (non-zero=falsy), or zero=truthy (the terminator). Assembly language can just as easily jump on non-zero as on zero so this is justified. An alternate version of this took an explicit-length string and returned 0 or 1 in the CF flag.

Clobbers: all GP registers except ESP

```
 1                                  tlh:
 2 00000000 31DB                        xor   ebx, ebx              ; left hand keys bitmap
 3 00000002 8D4B03                      lea   ecx, [ebx + 3]
 4                                  .rows:
 5 00000005 AD                          lodsd              ; length.  Upper bytes zero because each letter can appear at most once.
 6 00000006 8D2C06                      lea   ebp, [esi + eax]
 7 00000009 92                          xchg  edx, eax
 8                                    .keys:                   ; do{
 9 0000000A AC                              lodsb
10 0000000B 0FABC3                          bts   ebx, eax      ; bmap |= 1<<(c & 31)
11 0000000E 4A                              dec   edx
12 0000000F 4A                              dec   edx
13 00000010 7FF8                            jg   .keys        ; while(len-=2 > 0);  // handles the len=0 case where --len becomes negative
14 00000012 89EE                        mov   esi, ebp      ; skip 2nd half of string
15 00000014 E2EF                        loop  .rows
16
17                                  ;;; If the input string indexes any bit in EBX that isn't set, it's not left-hand typeable
18 00000016 89FE                        mov   esi, edi
19                                  .chars:               ; do{
20 00000018 AC                          lodsb
21 00000019 0FA3C3                      bt    ebx, eax
22 0000001C 72FA                        jc  .chars
23                                  .exit:
24                                      ; non-zero AL means we found a non-left-hand character.
25                                      ; zero means we found the terminating 0.  ASCII 'a' = 0x61 so our bitmap always has bit 0 = 0
26 0000001E C3                          ret

```

TODO:

* A better row input format to save instructions in the input code? (When I designed this format, I forgot about having to skip over the right half of a row that I wasn't going to read. `lea ebp, [start + len]` \+ `mov` was a bugfix. It would be nice to at least not need that many regs.)
* Maybe start with an all-1 bitmap and clear bits for right-hand keys? But that introduces a corner case for a row of length 1 which has no right-hand keys. Otherwise it might allow efficient looping to the end of a 0-terminated string.

I used the nice C test harness from @Noodle9's answer. This is 32-bit asm so it would be a double pain to get something runnable on TIO.run with NASM. (You can use FASM to make a 32-bit executable directly, without a separate linker invocation, but I think that doesn't link libc. You could I guess inline a simple strlen, or hard-code some data structures to at least exit with a 0 / 1 exit status...) I put the source + asm wrapper (to adapt to a normal C calling convention), and C test harness itself on TIO even though you can't actually try it there.

```
$ nasm -f elf32 -l/dev/stdout type-left-hand.asm &&
 gcc -Wall -fno-pie -no-pie -m32 type-left-hand.[co] &&
 ./a.out
qwertyuiop asdfghjkl zxcvbnm
qazg -> 1 (1)
qpazg -> 0 (1)
p asdfghjklqwertyuio zxcvbnm
sxzklkl -> 1 (1)
b -> 0 (1)
qazwsxplkm edocrfv tgbyhnuji
bad -> 1 (1)
tex -> 0 (1)
thequick brownfx jmpsvlazydg
brow -> 1 (1)
fox -> 0 (1)

```

`0 / 1 (1)` means *left-hand typeable (matches the correct result)*
> 2 votes

# Answer
# C (gcc), ~~116~~ \\$\cdots\\$ ~~108~~ 104 bytes

Saved 4 bytes thanks to rtpax!!!
Saved 4 bytes thanks to ceilingcat!!!

```
c;p;l;r;i;f(char**k,char*s){for(r=1;*s;++s)for(i=3;i--;r&=l>p*2)for(l=p=0;c=k[i][l];++l)p=c-*s?p:l;c=r;}

```

Try it online!

Takes the keyboard as an array of strings and the word as a string.
Returns \\$1\\$ for true and \\$0\\$ otherwise.
> 1 votes

# Answer
# Haskell, 69 bytes

```
x l=take(length l`div`2)l;l k s=all(\c->elem c$foldl(++)[]$map x k)s

```

Use (in `ghci`):

```
$ let kbd = ["qwertyuiop","asdfghjkl;","zxcvbnm,./"]
$ l kbd "stewardesses"
=> True
$ l kbd "joker"
=> False

```
> 1 votes

# Answer
# C# (Visual C# Interactive Compiler), ~~56~~ 63 bytes

```
k=>s=>s.All(c=>k.Any(l=>(uint)l.IndexOf(c)/(float)l.Length<.5))

```

Try it online!
> 1 votes

# Answer
# , ~~72~~ 71 bytes

```
function(k,s)all(t(sapply(k,function(x)match(s,x,0)))<(lengths(k)+2)/2)

```

Try it online!
> 1 votes

# Answer
# JavaScript (ES6), 53 bytes

Takes input as `(keyboard)(word)`. Returns a Boolean value.

```
k=>w=>!w.match(`[${k.map(r=>r.slice(-r.length/2))}]`)

```

Try it online!
> 0 votes

# Answer
# Charcoal, 12 bytes

```
⬤η⊙θ№…λ⊘⊕Ｌλι

```

Try it online! Link is to verbose version of code. Takes input as a list and a string. Output is a Charcoal boolean, i.e. `-` for true, nothing for false. Explanation:

```
 η              Input S
⬤               All characters
   θ            Input `K`
  ⊙             Any row
      λ         Current row
     …          Truncated to
       ⊘⊕Ｌλ     Half its length rounded up
    №      ι    Contains input character
                Implicitly print

```
> 0 votes

# Answer
# Python 2, ~~57~~ 55 bytes

*-2 bytes thanks to @ovs !*

```
lambda k,s:all(t.find(c)*2<len(t)for t in k for c in s)

```

Try it online!
> 0 votes

# Answer
# Python 3, 53 bytes

```
lambda k,w:all(max(map(r.find,w))<len(r)/2for r in k)

```

**Try it online!**
> 0 votes

---
Tags: code-golf, string, decision-problem
---