title: Sums of prime factors

text:
# Question
Title: Sums of prime factors
2013 has the prime factorization `3*11*61`. 2014 has the prime factorization `2*19*53`. An interesting property regarding these factorizations is that there exist distinct primes in the factorizations of 2013 and 2014 that sum to the same number: `11+61=19+53=72`.

Write a program or function that takes as its input two positive integers greater than 1 and returns a truthy value if there exist a sum of selected prime factors of one number that is equal to a sum of selected prime factors in the second number, and a falsey value otherwise.

---

**Clarifications**

* More than two prime factors can be used. Not all of the prime factors of the number need to be used in the sum. It is not necessary for the number of primes used from the two numbers to be equal.
* Even if a prime is raised to some power greater than 1 in the factorization of a number, it can only be used once in the sum of primes for the number.
* 1 is not prime.
* Both input numbers will be less than `2^32-1`.

---

**Test cases**

```
5,6
    5=5
    6=2*3
    5=2+3
==>True

2013,2014
    2013=3*11*61
    2014=2*19*53
    11+61=19+53
==>True

8,15
    8=2^3
    15=3*5
    No possible sum
==>False

21,25
    21=3*7
    25=5^2
    No possible sum (can't do 3+7=5+5 because of exponent)
==>False

```

---

This is code golf. Standard rules apply. Shortest code in bytes wins.

# Answer
> 10 votes
# Julia, ~~95~~ 93 bytes

```
g(x)=reduce(vcat,map(p->map(sum,p),partitions([keys(factor(x))...])))
f(a,b)=g(a)∩g(b)!=[]

```

The primary function is `f` and it calls a helper function `g`.

Ungolfed:

```
function g(x::Integer)
    # Find the sum of each combination of prime factors of the input
    return reduce(vcat, map(p -> map(sum, p), partitions([keys(factor(x))...])))
end

function f(a::Integer, b::Integer)
    # Determine whether there's a nonzero intersection of the factor
    # sums of a and b
    return !isempty(g(a) ∩ g(b))
end

```

Saved 2 bytes thanks to Darth Alephalpha

# Answer
> 7 votes
# Pyth - ~~17~~ ~~12~~ 11 bytes

*Thanks to @FryAmTheEggman for fixing my answer and saving a byte.*

```
@FmsMty{PdQ

```

Test Suite.

# Answer
> 7 votes
## Pyth, 11 bytes

```
t@FmsMy{PdQ

```

Input in the form `30,7`.

```
t@FmsMy{PdQ     implicit: Q=input tuple
      y         powerset of
       {        unique elements of
        Pd      prime factorizations of d
    sM          Map sum over each element of the powerset
    sMy{Pd      lambda d: all sums of unique prime factors of d
   m      Q     Map over Q. Produces a two-element list.
 @F             Fold list intersection
t               Remove first element, which is a 0.
                If no other common sums, the remaining empty list is falsy.

```

# Answer
> 5 votes
## Haskell, ~~115~~ 106 bytes

```
import Data.Numbers.Primes
import Data.List
p=map sum.tail.subsequences.nub.primeFactors
a#b=p a/=p a\\p b

```

Usage example: `2013 # 2014` -\> `True`.

`p` makes a list of all prime factors of it's argument, removes duplicates, makes a list of all subsequences, drops the first one (which is always the empty list) and finally sums the subsequences. `#` checks whether `p a` is not equal to the difference `p a \\ p b`. If not equal, they have at least one common element.

# Answer
> 3 votes
## CJam, 23 bytes

```
q~{mf_&0a\{1$f++}/}/&0-

```

Test it here.

The truthy value will be all common sums concatenated, the falsy value is the empty string.

### Explanation

```
q~     e# Read and evaluate input.
{      e# For each of the two numbers...
  mf   e# Get the prime factors.
  _&   e# Remove duplicates.
  0a\  e# Put an array containing a 0 below to initialise the list of possible sums.
  {    e# For each prime factor...
    1$ e#   Make a copy of the available sums so far.
    f+ e#   Add the current factor to each of them.
    +  e#   Combine with the list of sums without that factor.
  }/
}/
&      e# Set intersection between the two lists of sums.
0-     e# Remove the 0 which is always in the intersection.

```

# Answer
> 3 votes
# Japt, 25 bytes

```
[UV]=N®k â à mx};Ud@J<VbX

```

Outputs `true` or `false`. Try it online!

### Ungolfed and explanation

```
[UV]=N®   k â à mx};Ud@ J<VbX
[UV]=NmZ{Zk â à mx};UdX{J<VbX

          // Implicit: N = list of inputs
[UV]=N    // Set variables U and V to the first to items in N,
mZ{    }  // with each item Z mapped to:
Zk        //  Generate list of Z's factors.
â         //  Keep only the unique items.
à         //  Generate all combinations.
mx        //  Sum each combination.
UdX{      // Check if any item X in U fulfills this condition:
J<VbX     //  -1 is less than V.indexOf(X).
          // Implicit: output last expression

```

For an extra byte, you can split up the factorize-unique-combine-sum code between both inputs, with the added advantage of having a time complexity of `O(O(25-byte version)^2)`:

```
Uk â à mx d@J<Vk â à mx bX

```

# Answer
> 3 votes
# Brachylog, ~~10~~ 9 bytes

```
{ḋd⊇+ℕ₁}ᵛ

```

Try it online!

The predicate succeeds returning `[the sum, the sum]` if it exists, and fails if the sum does not exist.

```
{            Start of inline predicate.
 ḋ           The prime factors of the input,
  d          with duplicates removed.
   ⊇         Some subset of the unique prime factors
    +ℕ₁      has a sum greater than 0 which is output.
       }ᵛ    The predicate can have the same output for both elements of the input.

```

-1 byte thanks to Fatalize (the creator of Brachylog) reminding me that the *verify* meta-predicate exists.

# Answer
> 2 votes
# MATL, 23 bytes

```
2:"iYfutn2w^1-:B!Y*]!=z

```

Uses current release, 2.0.2, which is earlier than this challenge.

The numbers are provided as two separate inputs. Output is `0` or `1`.

### Example

```
>> matl 2:"iYfutn2w^1-:B!Y*]!=z
> 2013
> 2014
1

```

### Explanation

```
2:           % vector of two numbers, to generate two iterations
"            % for loop
  i          % input number
  Yfu        % get prime factors without repetitions
  tn         % duplicate and get number of elements in array N
  2w^1-:     % numbers from 1 to 2^N
  B!Y*       % convert to binary, transpose and matrix multiply to produce all sums
]            % end
!=z          % true if any value is equal to any other

```

# Answer
> 2 votes
# Mathematica, 58 bytes

```
Tr/@Rest@Subsets[#&@@@FactorInteger@#]&/@IntersectingQ@##&

```

### Explanation:

This is an anonymous function.

First, `IntersectingQ` checks if two lists are intersecting. But the inputs are numbers instead of lists, so it remains unevaluated. For example, if the inputs are `2013` and `2014`, then `IntersectingQ@##&` returns `IntersectingQ[2013, 2014]`.

`Tr/@Rest@Subsets[#&@@@FactorInteger@#]&` is another anonymous function that takes an integer, gets a list of its prime factors without repetitions, takes the power set, removes the empty set, and then takes the sum of each set. So `Tr/@Rest@Subsets[#&@@@FactorInteger@#]&[2013]` returns `{3, 11, 61, 14, 64, 72, 75}`.

Then map `Tr/@Rest@Subsets[#&@@@FactorInteger@#]&` over the expression `IntersectingQ[2013, 2014]`. `Tr/@Rest@Subsets[#&@@@FactorInteger@#]&[2013]` and `Tr/@Rest@Subsets[#&@@@FactorInteger@#]&[2014]]` are lists, so we can get the collect result this time.

# Answer
> 2 votes
# PARI/GP, 98 bytes

Factor, grab primes (`[,1]`), loop over nonempty subsets, sum, and uniq, then intersect the result of this for the two numbers. The returned value is the number of intersections, which is truthy unless they are 0.

```
f(n,v=factor(n)[,1])=Set(vector(2^#v-1,i,vecsum(vecextract(v,i))))
g(m,n)=#setintersect(f(m),f(n))

```

# Answer
> 2 votes
# APL (Dyalog Extended), ~~23~~ 17 bytesSBCS

-5 thanks to ngn

Anonymous tacit infix function.

```
1<≢⍤∩⍥(∊0+⍀.,∪⍤⍭)

```

Try it online!

`⍥{``}` apply the following anonymous function to both arguments:

prime factors

then

the unique ones of those

`0+⍀.,` addition table reduction of zero concatenated to each factor

**ϵ**nlist (flatten)

the intersection

then

the tally of those

`1<` is there more than one? (one because the sums of no factors)

# Answer
> 2 votes
# 05AB1E, ~~10~~ 8 bytes

```
f€æO`å¦à

```

-2 bytes thanks to *@Emigna*.

Try it online or verify all test cases.

**Explanation:**

```
f         # Get all distinct prime factors of both values in the (implicit) input-list
          #  i.e. [2013,2014] → [[3,11,61],[2,19,53]]
 €æ       # Get the powerset for each
          #  → [[[],[3],[11],[3,11],[61],[3,61],[11,61],[3,11,61]],
          #     [[],[2],[19],[2,19],[53],[2,53],[19,53],[2,19,53]]]
   O      # Sum each inner-most list
          #  → [[0,3,11,14,61,64,72,75],[0,2,19,21,53,55,72,74]]
    `     # Push both lists to the stack
     å    # Check for each value in the second list if it's present in the first list
          #  → [1,0,0,0,0,0,1,0]
      ¦   # Remove the first item (since the powerset included empty leading lists)
          #  → [0,0,0,0,0,1,0]
       à  # Check if any are truthy by taking the maximum (which is output implicitly)
          #  → 1

```

# Answer
> 1 votes
# Japt, 12 bytes

```
®k â à mx
rø

```

Run it online

# Answer
> 1 votes
# Python 3, 206 bytes

This is a lambda function (m), which takes in 2 numbers and returns a set containing any sums of prime factors that they have in common. In Python this is a truthy value when non-empty, and a falsey value when empty.

Edit: Turns out my original answer didn't work for prime inputs, as pointed out by @JoKing. This has been fixed (along with some other bugs) at the tragic cost of 40 bytes.

```
q=__import__('itertools').permutations
def p(n):
 i,s=2,set()
 while~-n:
  if n%i:i+=1
  else:n//=i;s|={i}
 return s
s=lambda f:{sum(i)for l in range(1,len(f)+1)for i in q(f,l)}
m=lambda a,b:s(p(a))&s(p(b))

```

Quick explanation using comments:

```
#Alias for permutations function
q=__import__('itertools').permutations
#Returns set of prime factors of n, including n, if prime
def p(n):
 i,s=2,set()
 while~-n:
  if n%i:i+=1
  else:n//=i;s|={i}
 return s
#Returns all possible sums of 2 or more elements in the given set
s=lambda f:{sum(i)for l in range(1,len(f)+1)for i in q(f,l)}
#Returns any shared possible sums of prime factors of a and b (the intersection of the sets)
m=lambda a,b:s(p(a))&s(p(b))

```

Try it online!

# Answer
> 1 votes
# APL(NARS), 50 char, 100 bytes

```
{⍬≢↑∩/+/¨¨{⍵∼⊂⍬}¨{0=⍴⍵:⊂⍬⋄s,(⊂1⌷⍵),¨s←∇1↓⍵}¨∪¨π¨⍵}

```

here π would find the array of factors on its argument;

```
{0=⍴⍵:⊂⍬⋄s,(⊂1⌷⍵),¨s←∇1↓⍵}

```

would be the function that find all subsets... i have to say that it seems {⍵operator itsArguments}¨ (for each left) and ¨ (for each right) can imitate loop with fixed number of cycles and ¨¨ is ok in to see subsets of one set... this way of see it seems reduce symbols in describe loops...; test

```
  h←{⍬≢↑∩/+/¨¨{⍵∼⊂⍬}¨{0=⍴⍵:⊂⍬⋄s,(⊂1⌷⍵),¨s←∇1↓⍵}¨∪¨π¨⍵}
  h 5 6
1
  h 2013 2014
1
  h 8 15
0
  h 21 25
0

```

One little analysis:

```
π¨⍵  for each arg apply factor
∪¨ for each arg apply unique
{0=⍴⍵:⊂⍬⋄s,(⊂1⌷⍵),¨s←∇1↓⍵}¨ for each arg apply subsets
{⍵∼⊂⍬}¨ for each argument subtract Zilde enclosed (that would be the void set)
+/¨¨ for each arg (for each arg apply +/)
⍬≢↑∩/ apply intersection, get the first argument and see if it is Zilde (this it is right because enclosed Zilde it seems is the void set)

```

# Answer
> 1 votes
# Japt , 14 bytes

```
®k â ã mx
rf Ê

```

Saved 3 bytes thanks to @Shaggy

Try it

# Answer
> 0 votes
# Gaia, ~~16~~ 11 bytes

```
ḍzΣ¦
↑@↑&ỵ!

```

Try it online!

The top function (first line) calculates the sums of the powerset of prime factors, and the second function finds if any of the elements of the intersection are nonzero.

---
Tags: code-golf, number, decision-problem, combinatorics, factoring
---


# Question
Title: Don't repeat yourself in Rock-Paper-Scissors
Upon the rumor that Codegolf will have a *Rock-Paper-Scissors tournament* you look into the topic of **square-free words**. A word made of the letters `R`, `P`, `S` is *square-free* if it does not contain a sequence that repeats twice. That is to say, the word can not be written as

```
a x x b

```

where `a` and `b` are words of any length and `x` is a word of length at least one, all made of the letters `R`, `P`, `S`.

## Task

Write a program that generates the *square-free* words of the letters `R`, `P`, `S` of length `n` where the number `1 <= n <= 10` is taken as input.

## Example

For example the *square-free* words of length 3 are

`RPR`, `RSR`, `RPS`, `RSP`, `SPS`, `SRS`, `SRP`, `SPR`, `PRP`, `PSP`, `PSR`, `PRS`

and those of length 4 are

`RPRS`, `RPSR`, `RPSP`, `RSRP`, `RSPR`, `RSPS`, `PRPS`, `PRSR`, `PRSP`, `PSRP`, `PSRS`, `PSPR`, `SRPR`, `SRPS`, `SRSP`, `SPRP`, `SPRS`, `SPSR`

and note that for example `SPSP` or `PRPR` are not square-free

## Rules

* This is codegolf, shortest program wins, standard loopholes are closed.
* You may print the words or create them in memory.
* Your program may be written as a function.

## References

Wikipedia entry on square-free words

The number of square-free ternary words of given length are in https://oeis.org/A006156

Related: Arbitrary-Length Ternary Squarefree Words

# Answer
# Ruby, 39 bytes

```
->n{(?P*n..?S*n).grep_v /[^RPS]|(.+)\1/}

```

This hilariously inefficient function generates all strings of length N that lie alphabetically between N Ps and N Ss, then filters out the vast majority that contain non-RPS characters. The actual squarefree check just uses a Regexp backreference: `(.+)\1`.

More idiomatic **65 bytes** that finish in a reasonable amount of time for N=10:

```
->n{%w[R P S].repeated_permutation(n).map(&:join).grep_v /(.+)\1/}

```

Edit: Saved a byte thanks to G B.
> 21 votes

# Answer
# Jelly, ~~15~~ 14 bytes

```
“RPS”ṗẆ;"f$$Ðḟ

```

Try it online!

### How it works

```
“RPS”ṗẆ;"f$$Ðḟ  Main link. Argument: n

“RPS”ṗ          Cartesian power; yield all strings of length n over this alphabet.
            Ðḟ  Filterfalse; keep only strings for which the quicklink to the left
                returns a falsy result.
           $      Monadic chain. Argument: s (string)
      Ẇ             Window; yield the array A of all substrings of s.
          $         Monadic chain. Argument: A
       ;"             Concatenate all strings in A with themselves.
         f            Filter; yield all results that belong to A as well.

```
> 11 votes

# Answer
## Retina, 28 bytes

```
+%1`1
R$'¶$`P$'¶$`S
A`(.+)\1

```

Try it online!

Takes input in unary.

### Explanation

```
+%1`1
R$'¶$`P$'¶$`S

```

This generates *all* strings made up of `RPS` of length `n`. The way we do this is that we repeatedly replace the first `1` in each line. Let's think about the line as `<1>`, where `<` is everything in front of the match and `>` is everything after the match (they're `$`` and `$'` respectively in regex substitution syntax, but those look less intuitive). We replace the `1` with `R>¶<P>¶<S`, where  are linefeeds. So the full result of this substitution is actually `<R>¶<P>¶<S>`, which is three copies of the line, with the `1` replace with `R`, `P`, `S`, respectively, in each of the three copies. This process stops once all `1`s have substituted.

```
A`(.+)\1

```

Finally, we simply discard all lines that contain a repetition.
> 7 votes

# Answer
# Mathematica, 61 bytes

```
""<>#&/@{"R","P","S"}~Tuples~#~DeleteCases~{___,x__,x__,___}&

```

Try it online!
> 7 votes

# Answer
# Husk, ~~15~~ 14 bytes

*-1 byte thanks to Zgarb!*

```
fȯεfoE½QΠR"RPS

```

Try it online!

Builds all possible sequences of the correct length and keeps only the ones whose all substrings (except the empty one) are composed by two different halves.

Damn, I really wanted to beat Jelly here.
> 7 votes

# Answer
# Java 8, ~~285~~ 277 bytes

```
import java.util.*;Set r=new HashSet();n->p("",((1<<3*n)+"").replaceAll(".","PRS"),n)void p(String p,String s,int n){int l=s.length(),i=0;if(l<1&&(s=p.substring(0,n)).equals(s.replaceAll("(.*)\\1","")))r.add(s);for(;i<l;p(p+s.charAt(i),s.substring(0,i)+s.substring(++i,l),n));}

```

Although Java is almost always verbose, in this case it's definitely not the right language for a challenge like this. Generating permutations with substrings is bad for performance and inefficient.

Can definitely be golfed some more, though.

-8 bytes thanks to *@Jakob*.

**Explanation:**

Try it here. (Performance is too bad for test cases above 3, but it does work locally..)

```
import java.util.*;   // Required import for Set and HashSet

Set r=new HashSet();  // Result-Set on class-level

n->                   // Method with integer parameter and no return-type
  p("",((1<<3*n)+"").replaceAll(".","PRS"),n)
                      //  Get all permutations and save them in the Set
                      // End of method (implicit / single-line return-statement)

void p(String p,String s,int n){
                      // Separated method with 2 String & int parameters and no return-type
  int l=s.length(),   //  The length of the second input-String
      i=0;            //  Index-integer, starting at 0
  if(l<1              //  If the length is 0,
     &&(s=p.substring(0,n)).equals(s.replaceAll("(.*)\\1","")))
                      //  and it doesn't contain a repeated part:
    r.add(s);         //   Add it to the result-Set
  for(;i<l;           //  Loop (2) from 0 to `l`
    p(                //   Recursive-call with:
      p+s.charAt(i),  //    Prefix-input + the character of the second input at index `i`
      s.substring(0,i)+s.substring(++i,l),
                      //    and the second input except for this character
      n)              //    and `n`
  );                  //  End of loop (2)
}                     // End of separated method

```
> 6 votes

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

```
f=lambda n:{c+s for c in'RPS'*n for s in f(n-1)or{''}if all(k-s.find(c+s[:k])for k in range(n))}

```

Returns a set of strings.

Try it online!
> 5 votes

# Answer
# Julia 0.6, 65 bytes

```
!n=n>0?["$c"s for s=!~-n,c="RPS"if~ismatch(r"(.+)\1","$c"s)]:[""]

```

Try it online!
> 5 votes

# Answer
# Perl 5, 37 bytes

```
sub r{grep!/(.+)\1/,glob"{R,S,P}"x<>}

```

Try it online!

Function returns an array of the square free strings.

**Explained:**

The `glob` generates all combinations of R, S, & P with length equal to the input. The `grep` statement filters out the ones that are not square free.
> 5 votes

# Answer
# , 97 bytes

```
cat((x=unique(combn(rep(c('p','r','s'),n),n<-scan(),paste,collapse='')))[!grepl("(.+)\\1",x,,T)])

```

Try it online!

`combn(rep(c('p','r','s'),n),n,paste,collapse='')` computes all `n`-character strings with `p`, `r`, `s`, but it unfortunately duplicates many(\*), so we uniquify it, and take those that match the regex `(.+)\1`, using perl-style matching, then we print out the resultant list.

(\*) technically, it generates all combinations of the `3n` letters in `p,r,s` repeated 3 times taken `n` at a time, then applies `paste(..., collapse='')` to each combination rather than computing the `3^n` strings directly, but this is golfier than an `expand.grid` (the true Cartesian product).
> 4 votes

# Answer
## JavaScript (Firefox 30-57), 69 bytes

```
f=n=>n?[for(x of f(n-1))for(y of'RPS')if(!/(.+)\1/.test(y+=x))y]:['']

```

Since all substrings of square-free words are also square-free the check can be done recursively.
> 4 votes

# Answer
# Haskell, ~~101~~ 98 bytes

```
f n=[x:r|x:r<-mapM(\_->"RPS")[1..n],[x]#r]
h#t@(x:r)=h/=take(length h)t&&(h++[x])#r&&[x]#r
h#t=1<3

```

Try it online!
> 3 votes

# Answer
## JavaScript (ES7), 93 bytes

```
n=>[...Array(3**n)].map(g=(d=n,i)=>d?'RPS'[i%3]+g(d-1,i/3|0):'').filter(s=>!/(.+)\1/.test(s))

```

Converts all the integers from 0 to 3ⁿ to (reversed padded) base 3 using `RPS` as digits and filters them for square-free words.
> 3 votes

# Answer
# Julia, 88

```
f(n)=[filter(A->!ismatch.(r"(.+)\1",join(A)),Iterators.product(repeated("RPS",n)...))...]

```

Nothing fancy.
> 3 votes

# Answer
## C# / LINQ, 169

```
Enumerable.Range(0,(int)Math.Pow(3,n)).Select(i=>string.Concat(Enumerable.Range(1,n).Select(p=>"PRS"[(i/(int)Math.Pow(3,n-p))%3]))).Where(s=>!Regex.IsMatch(s,@"(.+)\1"))

```

There has to be a better way to do this :)
> 2 votes

# Answer
## F#, 143

```
let f n=[1..n]|>List.fold(fun l _->List.collect(fun s->["R";"P";"S";]|>List.map((+)s))l)[""]|>Seq.filter(fun x->not(Regex.IsMatch(x,"(.+)\1")))

```
> 2 votes

# Answer
# k, 56 bytes

```
f:{$[x;(,/"RPS",/:\:f x-1){x@&~~/'(2,y)#/:x}/1_!x;,""]}

```

The lack of native regex puts k well behind the curve for once. I went with a recursive solution, since the characters to implement it were saved by a simpler squarefree check.

```
$[ test ; if-true ; if-false ]

```

is k's ternary operator, here we do interesting stuff for non-zero length, and return a single empty string if asked for zero-length words.

```
(,/"RPS",/:\:f x-1)

```

takes the cartesian product of "RPS" and all n-1 length squarefree words. ,/:\\: joins each element of the right to the left, giving a length 3 array of length n arrays. ,/ flattens this into a length 3n array.

```
{x@&~~/'(2,y)#/:x}

```

takes the first n letters of each string and compares it to the second n, then reduces the array to only where they do not match. Because we know the previous result is square-free, only the substrings starting at the first character need matching - simplifying the check here was worth the characters spent implementing recursion. Finally,

```
/1_!x

```

applies the lambda to the initial result set to its left, iterating over each substring length from 1 to (word length)-1. !x generates a list from 0 to x-1, then 1\_ removes the first element (since 0-length substrings will always match)

Sacrificing a few characters we can use .z.s to self-reference rather than rely on the function name, and instead of checking substrings up to length n-1 only check floor(n/2) for performance. It finds all length 49 words (of which there are 5207706) in about 120 seconds on a 7700k, above that I run into the 4GB limit of free 32-bit k.

```
{$[x;(,/"RPS",/:\:.z.s x-1){x@&~~/'(2,y)#/:x}/1+!_x%2;,""]}

```
> 2 votes

# Answer
# Python 2, 99 bytes

```
import re
f=lambda n:n and[c+s for c in'RPS'for s in f(n-1)if not re.search(r'(.+)(\1)',c+s)]or['']

```

Try it online!
> 1 votes

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


title: 1, 2, 3, 14... or is it 15?

text:
# Question
Title: 1, 2, 3, 14... or is it 15?
A well known song by the Irish rock band U2 starts with the singer Bono saying "1, 2, 3, 14" in Spanish ("*uno, dos, tres, catorce*").

There are various theories as to the significance of those numbers. Apparently the official explanation is "*we drank too much that night*". But there's a more interesting hypothesis: Bono is referring to some integer sequence from OEIS, such as

**A107083**:

> Integers `k` such that `10^k + 31` is prime.
> `1`, `2`, `3`, `14`, `18`, `44`, `54`, ...

In an interview, when asked the inevitable question "why 14", Bono admitted he was a bit tired of that number. The journalist suggested "15" instead, and in that night's concert the lyrics were indeed changed into "1, 2, 3, 15". (The story can be read here, in Spanish). Quite likely the journalist took inspiration from

**A221860**:

> Indices `k` such that `prime(k) - k` is a power of `2`, where `prime(k)` is the `k`-th prime.
> `1`, `2`, `3`, `15`, `39`, `2119`, `4189897`, ...

# The challenge

Write two programs in the same language. The first should take an input `n` and output the `n`-th term of A107083, or the first `n` terms. Similarly, the second should output the `n`-th term of A221860, or the first `n` terms.

The **score** is the **sum** of **lengths** of the two programs, in bytes, plus the **square** of the **Levenshtein distance** between the byte representations of the two programs.

If a character encoding is used such that each character corresponds to one byte, this script can be used to measure Levenshtein distance.

For example, if the two programs are `abcdefgh` and `bcdEEfg`, the score is `8 + 7 + 4^2 = 31`.

Lowest score wins.

# Aditional rules

* The output can be `1`-based or `0`-based, independently for each sequence (so it is allowed if one of the programs is `1`-based and the other is `0`-based).
* Each program can, consistently but independently of the other, either output the `n`-th term or the first `n` terms.
* Programs or functions are allowed, independently for each sequence.
* Input and output means and format are flexible as usual. Standard loopholes are forbidden.

# Answer
# Jelly, 16 + 16 + 1² = 33

### A107083

```
⁵*+31ÆḍÆNB>/
1Ç#

```

Try it online!

### A221860

```
⁵*+31ÆạÆNB>/
1Ç#

```

Try it online!

### How it works

```
1Ç#           Main link. Argument: n

1             Set the return value to 1.
 Ç#           Call the helper link with arguments k, k + 1, k + 2, ... until n of
              them return a truthy value. Return the array of n matches.

⁵*+31ÆḍÆNB>/  Helper link. Argument: k

⁵*            Yield 10**k.
  +31         Yield 10**k + 31.
     Æḍ       Count the proper divisors of 10**k + 31.
              This yields c = 1 if 10**k + 31 is prime, an integer c > 1 otherwise.
       ÆN     Yield the c-th prime.
              This yields q = 2 if 10**k + 31 is prime, a prime q > 2 otherwise.
         B    Binary; yield the array of q's digits in base 2.
          >/  Reduce by "greater than".
              This yields 1 if and only if the binary digits match the regex /10*/,
              i.e., iff q is a power of 2, i.e., iff 10**k + 31 is prime.

⁵*+31ÆạÆNB>/  Helper link. Argument: k

     Æ        Unrecognized token.
              The token, as well as all links to its left, are ignored.
       ÆN     Yield p, the k-th prime.
      ạ       Take the absolute difference of k and p, i.e., p - k.
         B    Binary; yield the array of (p - k)'s digits in base 2.
          >/  Reduce by "greater than".
              This yields 1 if and only if the binary digits match the regex /10*/,
              i.e., iff p - k is a power of 2.

```
> 20 votes

# Answer
# Pyth, 9 + 11 + 9² = 101 bytes

## 1, 2, 3, 14

```
.fP_+31^T

```

Try it online!

## 1, 2, 3, 15

```
.fsIl-e.fP_

```

Try it online!
> 5 votes

# Answer
# Jelly, 12 + 12 + 8² = 88 bytes

## 1, 2, 3, 14

```
ÆN_µæḟ2=
1Ç#

```

Try it online!

## 1, 2, 3, 15

```
10*+31ÆP
1Ç#

```

Try it online!
> 4 votes

# Answer
# Jelly, 11B + 10B + 7B² = 70

## 1, 2, 3, 14

```
⁵*+31ÆP
1Ç#

```

Try it online!

## 1, 2, 3, 15

```
ạÆNBSỊ
1Ç#

```

Try it online!
> 3 votes

# Answer
# MATL, 17+17+7² = 83

## 1, 2, 3, 14, ... (17 bytes)

```
0G:"`Q11qy^31+Zp~

```

Try it online!

## 1, 2, 3, 15, ... (17 bytes)

```
0G:"`QtYqy-Bzq~p~

```

Try it online!

Both employ the similar scheme of `0G:"`Q` to have a counter running up and returning when a condition has been met `n` times. The actual program then is fairly straightforward. The `15` variant has some filler (`~p~`) to minimise the Levenshtein distance, while the `14` program employs an `11qy` rather than `t10w` to match the other program better.

Shared part:

```
0      % Push counter (initially zero)
 G:"   % Loop `n` times
    `  % Do .... while true
     Q % Increment counter

```

Top program:

```
11q         % Push 10
   y        % Duplicate counter
    ^       % Power
     31+    % Add 31
        Zp  % isprime
          ~ % If not, implicitly continue to next iteration.
            % Else, implicit display of counter.

```

Bottom program:

```
tYq         % Nth prime based on counter
   y-       % Duplicate counter, subtract from nth prime.
     Bzq    % Number of ones in binary presentation, minus one (only zero for powers of two).
        ~p~ % Filler, effectively a NOP.
            % If not zero, implicitly continue to next iteration
            % Else, implicitl display of counter.

```
> 3 votes

# Answer
# 05AB1E (legacy), 10 + 11 + 62 = ~~84~~ ~~69~~ 57 bytes

## 1, 2, 3, 14, ... (A107083)

```
Îµ>Ð°32<+p

```

Try it online.

## 1, 2, 3, 15, ... (A221860)

```
Îµ>Ð<ØαD<&_

```

Try it online.

Both output the 1-based \\$n\\$th value.

Uses the legacy version of 05AB1E, since it does `½` (*increase `counter_variable` by 1 if the top of the stack is truthy*) implicitly after each iteration of `µ`-loops (*while `counter_variable` is not equal to \\$a\\$ yet, do ...*).

**Explanation:**

```
Î            # Push 0 and the input
 µ           # While the counter_variable is not equal to the input yet:
  >          #  Increase the top by 1
   Ð         #  Triplicate it (which is our `k`)
    °32<+    #  Take 10 to the power `k`, and add 31
         p   #  Check if this is a prime
             #  (implicit: if it is a prime, increase the counter_variable by 1)
             # (implicitly output the top of the stack after the while-loop)

Î            # Push 0 and the input
 µ           # While the counter_variable is not equal to the input yet:
  >          #  Increase the top by 1
   Ð         #  Triplicate it (which is out `k`)
    <Ø       #  Get the 0-indexed k'th prime
      α      #  Get the absolute difference of this prime with the copied `k`
       D<&   #  Calculate `k` Bitwise-AND `k-1`
          _  #  And check if this is 0 (which means it's a power of 2)
             #  (implicit: if it is 0, increase the counter_variable by 1)
             # (implicitly output the top of the stack after the while-loop)

```
> 1 votes

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


# Question
Title: Find efficient seating arrangement in a line
We have X Girls and Y Boys in a class. If more girls sit together they will not behave. Similarly if more boys sit together they will not behave.

Write a program/algorithm to get maximum same gender that will be seated if seating is done to efficiently to get them behave.

Example 1: 5 girls and 1 boy Expected Output: 3 Explanation: G G B **G G G**

Example 2: 7 girls and 3 boys Expected Output: 2 Explanation: **G G** B G B G G B G G

# Answer
> 4 votes
# Python 2, 26 bytes

```
lambda b,g:-min(b/~g,g/~b)

```

Try it online!

# Answer
> 1 votes
# JavaScript (Node.js), 31 bytes

*Port of @TFeld python answer*

```
a=>b=>-Math.min(a/~b,b/~a)+.5|0

```

Try it online!

---
Tags: math, code-challenge
---


title: Is this draw by repetition?

text:
# Question
Title: Is this draw by repetition?
# Problem:

In chess, there is a somewhat well known rule about draw by repetition. If the same position is repeated 3 times (or more) then the player intending to make the move which will cause the this repetition can claim a draw.

Sometimes this is an easy task for an arbiter to spot, if the last few moves are just the players moving backwards and forwards. Sometimes it is less trivial, when pieces have moved significantly between repeated positions.

The problem in this challenge is to output a truthy value if the claimed position is draw by repetition (has been seen 3 times or more) and a falsey value if the claimed position is not draw by repetition, given a list of moves in coordinate notation as described below, or any notation of your choosing (but you'll have to convert the test cases).

---

### What is a position?

In a real world scenario, the position would be affected by things such as whether a player can castle or whether en-passant is possible; you should **not** consider these in your solution to the problem. In this problem a position is defined simply by the configuration of the pieces on the board. So, for the purposes of this problem, two positions are seen to be the same if each square on both boards is occupied by the same type of piece of the same colour. This does not have to be the exact piece for example white's knights could swap squares and if all other pieces fulfill the criteria this would still be the same position.

---

### What does a valid notation look like?

Although I will go on to explain coordinate notation, you are free to take input by a notation system you choose. Provided that:

* Each item in the notation describes any or all of: the piece/pieces involved; whether check, checkmate, double check, checkmate or stalemate have been delivered; if en-passant capture has occurred; the initial position; the final position.
* You may **not** have information about repetition in your notation.

So as long as these criteria are met I am happy to accept, as long as you specify in your answer, your notation system. This could be e.g. 0 indexed row,column tuples or whatever makes sense for your program.

---

### Coordinate Notation

Coordinate notation is a notation which describes purely the moves as a system of coordinates.

A move is described as first the initial coordinate from the set `{A1-H8}` and then the destination coordinate again from the same set. So the King's Gambit would look like (as a collection of strings)

```
{"E2-E4","E7-E5","F2-F4"}

```

I believe it's the best notation to use for this problem because it is not littered with extraneous information like whether check has occurred or what the type of piece moving is. As mentioned before the notation can be of your choice, so you could use another notation e.g. algebraic notation or you could adapt this notation (e.g. remove the dashes, or take as a list of tuples)

---

## Rules:

* You should **not** consider whether a position or move is valid, only whether it causes repetition
* You can assume that castling and pawn promotion will **not** occur.
* You should take a list of strings as input and output a truthy or falsey value corresponding to whether the third (or more) repetition has occurred on the final move
* The game always starts at the standard starting position for chess. The initial position can count towards repetition.
* Draw by repetition has not occurred if the position is not repeated by the final move

---

## General rules:

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

---

### Test Cases

You should return truthy values for:

```
{"B1-C3","B8-C6","C3-B1","C6-B8","B1-C3","B8-C6","C3-B1","C6-B8"}
{"B1-C3","B8-C6","C3-B1","C6-B8","B1-C3","B8-C6","C3-B1","C6-B8","B1-C3","B8-C6","C3-B1","C6-B8"}
{"B1-C3","B8-C6","D2-D4","D7-D5","D1-D3","D8-D6","C3-B1","C6-B8","B1-C3","B8-C6","D3-D1","D6-D8","D1-D3","D8-D6"}
{"D2-D4","B8-C6","E2-E4","C6-D4","D1-E2","D4-E6","E2-F3","E6-D4","F3-D1","D4-C6","D1-E2","C6-D4","E1-D1","D4-C6","D1-E1","C6-D4"}
{"B1-C3","B8-C6","C3-B1","C6-B8","B1-C3","B8-C6","C3-B1","C6-B8","B1-C3","B8-C6","C3-B1","C6-B8","B1-C3"}

```

And falsey values for:

```
{}
{"E2-E4","E7-E5","F2-F4"}
{"B1-C3","B8-C6","C3-B1","C6-B8","B1-C3","B8-C6","C3-B1","C6-B8","F2-F4","F7-F5"}
{"E2-E4","E7-E5","G1-F3","B8-C6","F1-C4","G8-F6","F3-G5","D7-D5","E4-D5","F6-D5","G5-F7"}
{"D2-D4","B8-C6","E2-E4","C6-D4","D1-E2","D4-C6","E2-D1","C6-D4","D1-E2","D4-C6","E2-D1"}
{"B1-C3","B8-C6","C3-B5","C6-B4","B5-D4","B4-D5","D4-C6","D5-C3","C6-B8","C3-B1","B8-C6","B1-C3","C6-B8","C3-B1"}
{"E2-E4","E7-E5","D1-E2","E8-E7","E1-D1","D8-E8","E2-E1","E7-D8","E1-E2","E8-E7","E2-E1","E7-E8"}

```

# Answer
# APL (Dyalog Extended), ~~55~~ ~~49~~ ~~47~~ ~~45~~ 44 bytesSBCS

-4 thanks to ngn.

Full program. Prompts for reversed list of reversed coordinate pairs:
e.g. `{"B1-C3","B8-C6"}` is `[[[8,2],[6,3]],[[1,2],[3,3]]]`

```
2≤≢s∩{0,∘⊃@⍺⊃s,←⊂⍵}/⎕,⊂(⊖⍪-)¯4↑⍉6,⍪5,∘⌽⍥⍳s←3

```

Try it online! (includes the utility function `Coords` which translates OP's format)

**Set up a list of states:**

`s←3` assign three to `s` (for **s**tates)

Since 3 is not a valid board state, it will not affect our repetition count, and we need the pass-through value of the assignment…

**Build a chess board representation:**

`5`… discard that for the result of applying the following derived function between 5 and 3:
`⍥⍳` extend both arguments to their **ɩ**ndices;
`[1,2,3,4,5]``[1,2,3]`
`,∘⌽` the left side concatenated with the reverse of the right side
`[1,2,3,4,5,3,2,1]` this represent the officers

make into table;
`[[1],`
`[2],`
`[3],`
`[4],`
`[5],`
`[3],`
`[2],`
`[1]]`

`6,` prepend (to each row) a six, representing pawns;
`[[6,1],`
`[6,2],`
`[6,3],`
`[6,4],`
`[6,5],`
`[6,3],`
`[6,2],`
`[6,1]]`

transpose;
`[[6,6,6,6,6,6,6,6],`
`[1,2,3,4,5,3,2,1]]`

`¯4↑` take negative (i.e. the last) four (rows), padding with zeros, representing empty squares;
`[[0,0,0,0,0,0,0,0],`
`[0,0,0,0,0,0,0,0],`
`[6,6,6,6,6,6,6,6],`
`[1,2,3,4,5,3,2,1]]`

`(``)` apply the following tacit function to that:

`-` negate (this represents the opposite colour);
`[[ 0, 0, 0, 0, 0, 0, 0, 0],`
`[ 0, 0, 0, 0, 0, 0, 0, 0],`
`[-6,-6,-6,-6,-6,-6,-6,-6],`
`[-1,-2,-3,-4,-5,-3,-2,-1]]`

`⊖⍪` stack the flipped argument on top of that, giving us the full board;
`[[ 1, 2, 3, 4, 5, 3, 2, 1],`
`[ 6, 6, 6, 6, 6, 6, 6, 6],`
`[ 0, 0, 0, 0, 0, 0, 0, 0],`
`[ 0, 0, 0, 0, 0, 0, 0, 0],`
`[ 0, 0, 0, 0, 0, 0, 0, 0],`
`[ 0, 0, 0, 0, 0, 0, 0, 0],`
`[-6,-6,-6,-6,-6,-6,-6,-6],`
`[-1,-2,-3,-4,-5,-3,-2,-1]]`

**Construct a list of moves followed by the initial state:**

enclose that (to treat it as a single unit)

`⎕,` prompt for the list of moves, and prepend that to the initial state

**Reduce\* by a function which appends the current state to the list and makes a move:**

`{``}/` reduce by the following anonymous lambda:

the right argument (the current state)

enclose it to treat it as a unit

`s,←` in-place append it to the list of states

disclose it to use that state

…`@⍺` at the elements with the two coordinates that the left argument represents, put:
`0` a zero
`,` followed
by
the first value
this effectively "moves" the value at the first coordinate to the second coordinate, leaving behind a zero

**Check if we have three or more of the final state:**

`s∩` the intersection of all states with that final one; the subset of states identical to it

tally them up

`2≤` check if there are two or more (i.e. three or more including the final state)

---

* APL is right-associative, so first the function is called with the initial state as right argument and the initial move as left argument, and then its result, the new state, becomes the new right argument with the second move as new left argument, etc. The final result is the
> 9 votes

# Answer
# , ~~180~~ ~~177~~ 144 bytes

```
function(M,`+`=rep,l=c(1:5,3:1,6+8,0+16)){z=rev(Reduce(function(x,y){x[y[2:1]]=x[y]*1:0;x},M,c(l,-rev(l)),,T));sum(sapply(z,identical,el(z)))>2}

```

Try it online!

-3 bytes thanks to Giuseppe
-29 bytes thanks to Nick Kennedy's use of `Reduce` and `-rev(l)`
-4 bytes by reversing `z`

Takes as input a vector of integers between 1 and 64 denoting the squares. The TIO includes a function to transform into that format. The different pieces are stored as integers between 1 and 6 and between -1 and -6.

Explanation:

```
function(M,                                # M is the vector of moves
         `+` = rep,
         l = c(1:5, 3:1, 6 + 8, 0 + 16)) { # initial position of white pieces
  z = rev(Reduce(function(x, y) {
    x[y[2:1]] = x[y] * 1:0                 # a piece moves from y[1] to y[2]; y[1] becomes 0
    x
  }, M, c(l, -rev(l)), , T))
  sum(sapply(z, identical, el(z))) > 2    # find number of past positions identical to the last position
}

```
> 6 votes

# Answer
# Java 10, ~~336~~ ~~330~~ ~~287~~ ~~285~~ ~~282~~ 276 bytes

```
m->{var V=new java.util.HashMap();int i=64,A[]=new int[i];var t="";for(;i-->0;)t+=A[i]=(i%56<8?i%8*35%41%10%8+2:9>>i/16&1)*(i/32*2-1);V.put(t,1);for(var a:m){for(t="",A[a[1]]=A[a[0]],A[a[0]]=0,i=64;i-->0;)t+=A[i];V.compute(t,(k,v)->v!=null?(int)v+1:1);}return(int)V.get(t)>2;}

```

-11 bytes thanks to *@Arnauld* by changing `i%56<8?"ABCDECBA".charAt(i%56%7):i%48<16?1:0` to `i%56<8?i%8*35%41%10%8+2:9>>i/16&1`.

Input as a 2D array of integers where \\$a1=0, b1=1, ..., h8=63\\$ (i.e. `{"E2-E4",...` is `[[12,28],...`).

Try it online.

**Explanation:**

```
m->{                   // Method with 3D character array parameter and boolean return-type
  var V=new java.util.HashMap();
                       //  Create a Map to store the occurrences of the board-states
  int i=64,            //  Index integer, starting at 64
      A[]=new int[i];  //  Create the 8 by 8 board
  var t="";            //  Temp-String, starting empty
  for(;i-->0;)         //  Loop `i` in the range (64,0]:
    t+=                //    Append the string `t` with:
      A[i]=            //     Fill the `i`'th cell with:
        i%56<8?        //      If it's either the first or eighth row:
         i%8*35%41%10%8+2
                       //       Fill it with 2,7,3,5,9,3,7,2 based on index `i`
        :9>>i/16&1)    //      Else if it's either the second or seventh row:
                       //       Fill it with 1
                       //      Else (the third, fourth, fifth, or sixth rows):
                       //       Fill it with 0
        *(i/32*2-1);   //      Then multiply it by -1 or 1 depending on whether `i`
                       //      is below 32 or not
  V.put(t,1);          //  Then set string `t` in the map to 1 for the initial state
  for(var a:m){        //  Loop over each of the input's integer-pairs:
    for(t="",          //   Make the String empty again
        A[a[1]]=       //   Set the to-cell of the current integer-pair of the input to:
          A[a[0]],     //    The value in the from-cell of the same integer-pair
        A[a[0]]=0,     //   And then empty this from-cell
        i=65;i-->0;)   //   Inner loop `i` in the range (64,0]:
          t+=A[i];     //    Append the `i`'th value to the String `t`
    V.compute(t,(k,v)->v!=null?(int)v+1:1);}
                       //   Increase the value in the map for String `t` as key by 1
  return(int)V.get(t)  //  Return whether the value in the map for the last String `t`
          >2;}         //  is at least 3

```

The values of the pieces after filling them with `A[i]=(i%56<8?i%8*35%41%10%8+2:9>>i/16&1)*(i/32*2-1)` are:

```
     a  b  c  d  e  f  g  h
  +------------------------
1 | -2 -7 -3 -5 -9 -3 -7 -2
2 | -1 -1 -1 -1 -1 -1 -1 -1
3 |  0  0  0  0  0  0  0  0
4 |  0  0  0  0  0  0  0  0
5 |  0  0  0  0  0  0  0  0
6 |  0  0  0  0  0  0  0  0
7 |  1  1  1  1  1  1  1  1
8 |  2  7  3  5  9  3  7  2

```

Try it online.
> 3 votes

# Answer
# JavaScript (Node.js),  ~~121~~  111 bytes

Expects the moves in `[sq0, sq1]` format, where each square is in \\$\[0..63\]\\$ with \\$\text{a8}=0\\$, \\$\text{b8}=1\\$, ..., \\$\text{h1}=63\\$.

Returns a Boolean value.

```
a=>[a,...a].map(([x,y])=>r=b[b[b[y]=b[x],x]=0,b]=-~b[b],b=[...'89ABCA981111111'+10n**32n+0x7e5196ee74377])&&r>2

```

Try it online!

## How?

### Pieces

The values used to identify the pieces do not really matter as long as there's one unique value per piece type.

We use:

* **0** for empty squares
* **1** / **8** / **9** / **A** / **B** / **C** for ♟ / ♜ / ♞ / ♝ / ♛ / ♚
* **2** / **3** / **4** / **5** / **6** / **7** for ♙ / ♖ / ♘ / ♗ / ♕ / ♔

### Board and initial position

The board is stored in the array \\$b\\$ which is initialized by splitting the concatenation of the following parts:

* `'89ABCA981111111'` → the 8 black major pieces, followed by the first 7 black pawns
* `10n**32n` → the last black pawn on \\$\text{h7}\\$ (\\$1\\$) followed by 32 empty squares (\\$0\\$)
* `0x7e5196ee74377` → all white pieces (expends to `2222222234567543` in decimal)

which results in:

```
    a b c d e f g h
  +----------------
8 | 8 9 A B C A 9 8
7 | 1 1 1 1 1 1 1 1
6 | 0 0 0 0 0 0 0 0
5 | 0 0 0 0 0 0 0 0
4 | 0 0 0 0 0 0 0 0
3 | 0 0 0 0 0 0 0 0
2 | 2 2 2 2 2 2 2 2
1 | 3 4 5 6 7 5 4 3

```

### Keeping track of the positions

The variable \\$b\\$ is also used as an *object* to keep track of all encountered positions. The key for each position is \\$b\\$ itself, but this time as an *array* and implicitly coerced to a string.

This is why we do:

```
b[b] = -~b[b]

```

## Commented

```
a =>                    // a[] = input
  [ a,                  // dummy entry to mark the initial position as encountered once
    ...a                // append the actual data
  ].map(([x, y]) =>     // for each pair of squares [x, y] in this array:
    r =                 //   store the last result in r
    b[                  //   update b[b]:
      b[                //     update b[x]:
        b[y] = b[x],    //       set b[y] to b[x]
        x               //       set b[x] ...
      ] = 0,            //     ... to 0
      b                 //     set b[b] ...
    ] = -~b[b],         //   ... to b[b] + 1 (or 1 if b[b] is undefined)
    b = [...(…)]        //   initialize b[] (see above)
  )                     // end of map()
  && r > 2              // return true if the last result is greater than 2

```
> 3 votes

# Answer
# Jelly, ~~41~~ 37 bytes

```
Ø0;6x8;“Ġ²F’D¤UN;ƊW;µị@⁹Ṫ¤¦0⁹¦$\ċṪ$>1

```

Try it online!

A monadic link that takes the input as a list of pairs of 1-indexed row-major moves `[from, to]` and returns a 1 for draws and 0 for not.

Note the footer code on TIO translates the moves as supplied by the OP to the numeric format, but per the discussion below the question, the numeric format would have been a valid input.

### Explanation

```
Ø0                                    | 0,0
  ;6                                  | concatenate to 6 (pawn)
    x8                                | repeat each 8 times (two blank rows and 1 row of pawns)
      ;“Ġ²F’D¤                        | concatenate to 1,2,3,4,5,3,2,1
              UN;Ɗ                    | concatenate a negated flipped version to this one
                  W;                  | wrap as a list and concatenate the input list to the board
                    µ                 | start a new monadic chain
                              $\      | reduce using the two links below
                     ị@⁹Ṫ¤¦           | replace the item pointed to by the second coordinate by the value of the one at the first
                           0⁹¦        | replace the item at first coordinate with zero
                                ċṪ$   | finally count the items equal to the final one (not including it)
                                   >1 | and check of >1

```
> 3 votes

# Answer
# C# (Visual C# Interactive Compiler), 204 bytes

```
n=>{var j=new List<char[]>();var d=("ABCDECBATTTTTTTT"+new string('Z',32)+7777777712345321).ToArray();foreach(var(a,b)in n){j.Add(d.ToArray());d[b]=d[a];d[a]='Z';}return j.Count(r=>r.SequenceEqual(d))>1;}

```

Takes input as a list of tuples of integers, where the first integer is where to move from, and the second is where to move to. 0 represents A1, 1 is A2, and 63 is H8.

Try it online!

```
n=>{
  var j=new List<char[]>();    //Initialize a list to save states of a board
  var d=("ABCDECBATTTTTTTT" +  //White pieces
  new string('Z',32) +         //Empty spaces
  7777777712345321)            //Black pieces
  .ToArray(); //Initialize the chessboard
  foreach(var(a,b)in n){       //Foreach (source square, destination square) in the input
    j.Add(d.ToArray());        //  Add the current board to the list
    d[b]=d[a];                 //  Set the destination square to the source square's value
    d[a]='Z';                  //  And set the souce square to empty
  }
  return j.Count(         //Return that the amount...
    r=>r.SequenceEqual(d) //  of past positions that are equal to the current position...
  )>1;                    //is at least two
}

```
> 2 votes

# Answer
# Charcoal, 62 bytes

```
≔↨²³⁴⁵⁶⁴³²χηＦ⁴⁸⊞η÷⁻⁴⁰ι³²Ｆ…η⁸⊞η±ιＦθ«⊞υ⮌η§≔η⊟ι§η§ι⁰§≔η⊟ι⁰»›№υ⮌η¹

```

Try it online! Link is to verbose version of code. Takes input as an array of pairs of numbers where the squares are numbered `A1`, `B1`, ... `H8` (0-indexed) so for instance the first test case would be represented as `[[[1, 18], [57, 42], [18, 1], [42, 57], [1, 18], [57, 42], [18, 1], [42, 57]]]` and outputs a `-` if the position is a draw by repetition. Conversion program. All in one. Explanation:

```
≔↨²³⁴⁵⁶⁴³²χη

```

Split the number `23456432` into individual digits. These represent the white pieces.

```
Ｆ⁴⁸⊞η÷⁻⁴⁰ι³²

```

Add in the pawns and the empty rows. The white pawns have value `1` and the black pawns `-1`.

```
Ｆ…η⁸⊞η±ι

```

Append a negated copy of the white pieces, which represent the black pieces.

```
Ｆθ«

```

Loop over the moves.

```
⊞υ⮌η

```

Save a copy of the board. (Reversing is the golfiest way to copy the board.)

```
§≔η⊟ι§η§ι⁰

```

Update the destination with the source piece.

```
§≔η⊟ι⁰

```

Remove the source piece.

```
»›№υ⮌η¹

```

Determine whether the current position was seen more than once before.
> 2 votes

# Answer
# Java (JDK), ~~246~~ ~~245~~ 244 bytes

```
import java.util.*;n->{var j=new ArrayList<char[]>();var d=("ABCDECBATTTTTTTT"+"".repeat(32)+7777777712345321l).toCharArray();for(var k:n){j.add(d.clone());d[k[1]]=d[k[0]];d[k[0]]=1;}return j.stream().filter(x->Arrays.equals(d,x)).count()>1;}

```

Try it online!

```
import java.util.*;                   //Import the java.util package

n->{                                  //Function taking in int[][],
                                      //where each int[] is a a pair of numbers
  var j = new ArrayList<char[]>();    //List to save each position of the chessboard
  var d =                             //The chessboard's starting position
    ("ABCDECBATTTTTTTT" +             //  All the white pieces
    "&#1".repeat(32) +                //  Plus the empty squares
    7777777712345321l)                //  And the black pieces
  .toCharArray();                     //Split to array of chars
  for(var k:n){                       //Foreach [sourceSquare, destinationSquare] in input
    j.add(d.clone());                 //  Add the current position to the list
    d[ k[1] ] = d[ k[0] ];            //  Set the destination square's value
                                      //  to the source squares
    d[ k[0] ] = 1;                    //  And clear the source square
}                                     //End foreach
return j.stream()                     //Convert list of states to stream
  .filter(x ->                        //Filter each position by
    Arrays.equals(d,x)                //  if the position equals the final position
  ).count() > 1;                      //And return if there are at least two
                                      //positions that are left
}

```
> 0 votes

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


title: Valid term from quadratic sequence?

text:
# Question
Title: Valid term from quadratic sequence?
You are given four numbers. The first three are \\$a\\$, \\$b\\$, and \\$c\\$ respectively, for the sequence:

$$T\_n=an^2+bn+c$$

You may take input of these four numbers in any way. The output should be one of two distinct outputs mentioned in your answer, one means that the fourth number is a term in the sequence (the above equation has at least one solution for \\$n\\$ which is an integer when \\$a\\$, \\$b\\$, \\$c\\$ and \\$T\_n\\$ are substituted for the given values), the other means the opposite.

This is code golf, so the shortest answer in bytes wins. Your program should work for any input of \\$a, b, c, T\_n\\$ where the numbers are negative or positive (or 0), decimal or integer. To avoid problems but keep some complexity, non-integers will always just end in \\$.5\\$. Standard loop-holes disallowed.

## Test cases

```
a   |b   |c   |T_n |Y/N
------------------------
1   |1   |1   |1   |Y     #n=0
2   |3   |5   |2   |N
0.5 |1   |-2  |-0.5|Y     #n=1
0.5 |1   |-2  |15.5|Y     #n=5
0.5 |1   |-2  |3   |N
-3.5|2   |-6  |-934|Y     #n=-16
0   |1   |4   |7   |Y     #n=3
0   |3   |-1  |7   |N
0   |0   |0   |1   |N
0   |0   |6   |6   |Y     #n=<anything>
4   |8   |5   |2   |N

```

# Answer
# Jelly,  ~~11~~  10 bytes

```
_/Ær1Ẹ?%1Ạ

```

A monadic Link which accepts a list of lists\* `[[c, b, a], [T_n]]` and yields `0` if `T_n` is a valid solution or `1` if not.

* admittedly taking a little liberty with "You may take input of these four numbers in any way".

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

### How?

```
_/Ær1Ẹ?%1Ạ - Link: list of lists of integers, [[c, b, a], [T_n]]
 /         - reduce by:
_          -   subtraction                    [c-T_n, b, a]
      ?    - if...
     Ẹ     - ...condition: any?
  Ær       - ...then: roots of polynomial     i.e. roots of a²x+bx+(c-T_n)=0
    1      - ...else: literal 1
       %1  - modulo 1 (vectorises)            i.e. for each: keep any fractional part
           -                                       note: (a+bi)%1 yields nan which is truthy
         Ạ - all?                             i.e. all had fractional parts?
           -                                       note: all([]) yields 1

```

---

If we could yield non-distinct results then `_/Ær1Ẹ?ḞƑƇ` would also work for 10 (it yields `1` when all values are solutions, otherwise a list of the distinct solutions and hence always an empty list when no solutions - this would also meet the standard Truthy vs Falsey definition)
> 4 votes

# Answer
# JavaScript (ES7), 70 bytes

Returns a Boolean value.

```
(a,b,c,t)=>(t-=c,(a*=2)?(x=(b*b+2*a*t)**.5-b)%a&&(x+b+b)%a:b?t%b:t)==0

```

Try it online!

## How?

For the sake of clarity, we define \\$d = T\_n-c\\$. (The same variable \\$t\\$ is re-used to store this result in the JS code.)

### Case \\$a\neq0\\$

The equation really is quadratic:

$$T\_n=an^2+bn+c\\ an^2+bn-d=0$$

With \\$a'=2a\\$, the discriminant is:

$$\Delta=b^2+2a'd$$

and the roots are:

$$n\_0=\frac{-b-\sqrt{\Delta}}{a'}\\ n\_1=\frac{-b+\sqrt{\Delta}}{a'}$$

The equation admits an integer root if \\$\sqrt{\Delta}\\$ is an integer and either:

$$\begin{align}&-b-\sqrt{\Delta}\equiv 0\pmod{a'}\\ \text{ or }&-b+\sqrt{\Delta}\equiv 0\pmod{a'}\end{align}$$

### Case \\$a=0, b\neq0\\$

The equation is linear:

$$T\_n=bn+c\\ bn=d\\ n=\frac{d}{b}$$

It admits an integer root if \\$d\equiv0\pmod b\\$.

### Case \\$a=0, b=0\\$

The equation is not depending on \\$n\\$ anymore:

$$T\_n=c\\ d=0$$
> 6 votes

# Answer
# 05AB1E, 35 bytes

```
Æ©²Āi²4P³n+tÐdi(‚³-Ä²·Ä%P}ë®³Āi³%]_

```

Port of *@Arnauld*'s JavaScript answer, so make sure to upvote him!

Takes the input in the format \\$\[t,c\], a, b\\$.

Try it online

**Explanation:**

```
Æ                         # Reduce the (implicit) input-list by subtraction (`t-c`)
 ©                        # Store this value in the register (without popping)
  ²Āi                     # If the second input `a` is not 0:
     ²4P                  #  Calculate `(t-c)*a*4`
        ³n+               #  Add the third input `b` squared to it: `(t-c)*a*4+b*b`
           t              #  Take the square-root of that
                          #  (NOTE: 05AB1E and JS behave differently for square-roots of
                          #   negative integers; JS produces NaN, whereas 05AB1E leaves the
                          #   integer unchanged, which is why we have the `di...}` here)
            Ð             #  Triplicate this square
             di           #  If the square is non-negative (>= 0):
               (‚         #   Pair it with its negative
                 ³-       #   Subtract the third input `b` from each
                   Ä      #   Take the absolute value of both
                    ²·Ä%  #   Modulo the absolute value of `a` doubled
                          #   (NOTE: 05AB1E and JS behave differently for negative modulos,
                          #    which is why we have the two `Ä` here)
                        P #   Then multiply both by taking the product
              }           #  And close the inner if-statement
    ë                     # Else (`a` is 0):
     ®                    #  Push the `t-c` from the register
      ³Āi                 #  If the third input `b` is not 0:
         ³%               #   Take modulo `b`
    ]                     # Close both if-else statements
     _                    # And check if the result is 0
                          # (which is output implicitly)

```
> 1 votes

# Answer
# Jelly, 15 bytes

```
_3¦UÆr=Ḟ$;3ị=ɗẸ

```

Try it online!

Built-in helps here but doesn’t handle a=b=0 so this is handled specially.
> 0 votes

# Answer
# Wolfram Language (Mathematica), 38 bytes

```
Solve[n^2#+n#2+#3==#4,n,Integers]!={}&

```

Try it online!
> 0 votes

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


title: Implement tab completion

text:
# Question
Title: Implement tab completion
Tab completion is a useful feature that auto-completes partially written commands. You're going to be implementing it.

For example, if the available commands were `['apply','apple','apple pie','eat']`, then `a` would complete to `appl`, as all of the commands that start with `a` also start with `appl`.

# Input/Output

You need to input a string, A, and a set of strings, B.

You need to output the longest common prefix of all B that starts with A.

* If none of the options starts with A, then return A
* You can assume that B is nonempty, and that all strings are nonempty
* You cannot assume that any of the options start with A, nor that the common prefix will be longer than A
* You can be case sensitive or case insensitive.
* You only need to handle printable ASCII
* Built-ins that explicitly do this task are allowed

# Test cases:

```
'a'       ['apply','apple','apple pie','eat'] => 'appl'
'a'       ['apple pie']                       => 'apple pie'
'apple'   ['eat','dine']                      => 'apple'
'program' ['programa','programb']             => 'program'
'*%a('    ['*%a()-T>','*%a()-T<','@Da^n&']    => '*%a()-T'
'a'       ['abs','absolute','answer']         => 'a'
'a'       ['a','abs']                         => 'a'
'one to'  ['one to one','one to many']        => 'one to '

```

Note the trailing space on the last test case

This is a , so make your answers as short as possible!

# Answer
> 10 votes
## JavaScript (ES6), 75 bytes

```
(s,a)=>/^(.*).*(\n\1.*)*$/.exec(a.filter(e=>e.startsWith(s)).join`
`)[1]||s

```

Explanation: Filters on all matching prefixes, then joins with newlines and matches against a regex that finds the longest common prefix of all lines. If there are no prefixes then the regex returns an empty string in which case we simply return the original string.

# Answer
> 7 votes
# Jelly, ~~14~~ 12 bytes

```
ḣJ$€ċÐff\ṪṪȯ

```

Try it online! or verify all test cases.

### How it works

```
ḣJ$€ċÐff\ṪṪȯ  Main link. Left argument: B. Right argument: A

  $€          Convert the two links to the left into a monadic chain and apply it
              to each string s in B.
 J              Generate the indices of s, i.e., [1, ..., len(s)].
ḣ               Head; for each index i, take the first i characters of s.
              This generates the prefixes of all strings in B.
     Ðf       Filter; keep prefixes for which the link to the left returns 1.
   ċ            Count the number of times A appears in the prefixes of that string.
       f\     Do a cumulative (i.e., keeping all intermediate values) reduce by
              filter, keeping only common prefixes. f/ is a more obvious choice,
              but it errors on an empty array, i.e., when A isn't a prefix of any
              string in B.
         Ṫ    Tail; take the last prefix array (if any) or return 0.
          Ṫ   Tail; take the last common prefix (if any) or return 0.
           ȯ  Logical OR (flat); replace 0 with A, leave strings untouched.

```

# Answer
> 6 votes
# Pyth, ~~14~~ 13 bytes

*Thanks to @isaacg for -1 byte*

```
.xe@F/#z._MQz

```

A program that takes the list of strings, and then the string, on STDIN and prints the result.

Verify all test cases

**How it works**

```
.xe@F/#z._MQz  Program. Inputs: Q, z
        ._MQ   Map prefixes over Q
     /#z       Filter that by count(z)>0, removing the prefixes corresponding to elements
               in Q that do not start with z
   @F          Fold intersection over that. This yields all the common prefixes
  e            Yield the last element of that, giving the longest common prefix, since the
               prefixes are already sorted by length
.x             But if that throws an exception since no elements of Q start with z:
            z  Yield z instead
               Implicitly print

```

# Answer
> 5 votes
## PowerShell v3+, 112 bytes

```
param($a,$b)if($c=@($b-like"$a*")){([char[]]$c[0]|%{($i+="$_")}|?{($c-like"$_*").count-eq$c.count})[-1]}else{$a}

```

Takes input as a string `$a` and an array of strings `$b`. Uses the `-like` operator to pull out those elements from `$b` that (case-insensitive) starts with `$a`, explicitly cast those as an array `@(...)` (since the result could be one match as a scalar, in which case indexing later fails), and store that array into `$c`.

That forms the `if` clause. If there's nothing in `$c` (i.e., nothing starts with `$a`, so the array is empty), then output `$a` with the `else`. Otherwise ...

We cast the first element of `$c` as a `char`-array and loop through each element, string-concatenating with the previous `$i` and placing the strings on the pipeline via encapsulating parens. Those are filtered through `|?{...}` (the `Where-Object` clause) to verify that the `.count` of `$c` is `-eq`ual to the `.count` of things in `$c` that are `-like` the substring (i.e., the substring matches everything in $c). Since we're building our substrings in order shortest to longest, we need the last `[-1]` of the resultant strings.

### Test Cases

```
PS C:\Tools\Scripts\golfing> $tests=@('a',@('apply','apple','apple pie','eat')),@('a',@('apple pie')),@('apple',@('eat','dine')),@('program',@('programa','programb')),@('one to',@('one to one','one to many')),@('*%a(',@('*%a()-T>', '*%a()-T<', '@Da^n&'))

PS C:\Tools\Scripts\golfing> $tests|%{""+$_[0]+" ("+($_[1]-join',')+") -> "+(.\implement-tab-completion.ps1 $_[0] $_[1])}
a (apply,apple,apple pie,eat) -> appl
a (apple pie) -> apple pie
apple (eat,dine) -> apple
program (programa,programb) -> program
one to (one to one,one to many) -> one to
*%a( (*%a()-T>,*%a()-T<,@Da^n&) -> *%a()-T

```

# Answer
> 4 votes
## Python 2, 122 bytes

```
s=input();l=[x for x in input()if x[:len(s)]==s]or[s];i=len(l[0])
while len(l)>1:i-=1;l=set(x[:i]for x in l)
print l.pop()

```

Full program; takes string and list from stdin exactly as given in the examples, except the inputs must be on separate lines.

Verify all test cases

# Answer
> 3 votes
# Perl, 61 bytes

Includes +2 for `-0p`

Run with the first word followed by the dictionary words on STDIN:

```
tabcompletion.pl
a
apply
apple
apple pie
eat
^D

```

`tabcompletion.pl`:

```
#!/usr/bin/perl -0p
/^(.+)
((?!\1).*
)*(\1.*).*
((?!\1).*
|\3.*
)*$|
/;$_=$3||$`

```

# Answer
> 3 votes
# Perl, 54 bytes

Includes +2 for `-Xp` (can be combined with `-e`) and +3 for `-i` (cannot be combined)

Give dictionary on STDIN and the word after the `-i` option, e.g.:

```
perl -ia -Xpe '/^\Q$^I\E.*?(?{$F[$a{$&}++]=$&})^/}{$_=pop@F||$^I'
apply
apple
apple pie
eat
^D

```

Just the code:

```
/^\Q$^I\E.*?(?{$F[$a{$&}++]=$&})^/}{$_=pop@F||$^I

```

# Answer
> 2 votes
# Python 2, 112 bytes

```
lambda n,h:[a.pop()for a in[{s[:-i]for s in h if s.find(n)==0}for i in range(-len(`h`),0)]+[{n}]if len(a)==1][0]

```

# Answer
> 2 votes
## Haskell, 67 bytes

```
(a:b)?(c:d)|a==c=a:(b?d)
_?_=""
s%l=foldr1(?)$max[s][x|x<-l,x?s==s]

```

The auxiliary function `?` finds the longest common prefix of two strings by recursively taking the first character as long as it's the same for both strings and the strings are non-empty.

The main function `%` first keeps only the strings in the list that start with the given one `s`, checked by the longest common prefix with `s` being `s`. To handle there being no valid competitions, it adds `s` to an empty result via `max`. Then, it finds the longest common prefix of those by folding the binary function `?`.

# Answer
> 2 votes
# Python 2, 75 bytes

```
import os
lambda s,x:os.path.commonprefix([t for t in x if s<=t<s+'ÿ'])or s

```

*Thanks to @xnor for suggesting the built-in, originally used by @BetaDecay in this answer.*

For scoring purposes, `ÿ` can be replaced with a DEL byte. Test it on Ideone.

# Answer
> 1 votes
## D, 88 bytes

```
S f(S)(S p,S[]q){try p=q.filter!(a=>a.startsWith(p)).fold!commonPrefix;catch{}return p;}

```

**Usage:**

```
assert(f("a", ["apply","apple","apple pie","eat"]) ==  "appl");

```

The code simply removes all elements from `q` that don't start with `p`, then computes the largest common initial subsequence of the remaining elements.

The templated parameters save us two repetitions of `string` and one of `auto`. The exception misuse lets us avoid the temporary variable and conditional that would otherwise be necessary to handle the case where no elements of `q` start with `p`.

# Answer
> 1 votes
# Python 2, ~~107~~ 102 bytes

```
s,x=input();r='';q=1
for c in zip(*[t for t in x if s<=t<s+'ÿ']):q/=len(set(c));r+=c[0]*q
print r or s

```

For scoring purposes, `ÿ` can be replaced with a DEL byte. Test it on Ideone.

*Thanks to @xnor for saving 5 bytes!*

# Answer
> 1 votes
# PHP, ~~167~~ ~~160~~ ~~157~~ 152 bytes

```
<?for($r=preg_grep("$^".preg_quote($s=$_GET[s])."$",$a=$_GET[a]);$r[0]>$s&&preg_grep("$^".preg_quote($t=$s.$r[0][strlen($s)])."$",$a)==$r;)$s=$t;echo$s;

```

I could save 3 more bytes by assigning variables with `preg_grep` and `preg_quote`, but eh.

**breakdown**

```
for(
    // find items in $a that start with $s
    $r=preg_grep("$^".preg_quote($s=$_GET[s])."$",$a=$_GET[a]);
    // while the first match is longer than $s
    $r[0]>$s
    // and appending the next character of the first match
    &&preg_grep("$^".preg_quote($t=$s.$r[0][strlen($s)])."$",$a)
    // does not change the matches
    ==$r
;)
    // keep appending
    $s=$t;
return$s;

```

# Answer
> 1 votes
# PHP, 156 Bytes

with much Help from Titus Thank You

```
<?foreach($_GET[t]as$v)if(strstr($v,$s=$_GET[s])==$v)$r[]=$z=$v;for(;$i++<strlen($z);){$s=substr($z,0,$i);foreach($r as$x)if($x[$i]!=$z[$i])break 2;}echo$s;

```

# PHP, 199 Bytes

32 Bytes saves by Titus with array\_unique

```
<?foreach($_GET[t]as$v)if(strstr($v,$s=$_GET[s])==$v)$r[]=$v;for(;$i++<strlen($r[0]);$a=[]){foreach($r as$x)$a[]=substr($x,0,$i);if(count($r)==count($a)&count(array_unique($a))<2)$s=$a[0];}echo$s;

```

I know that the Regex Solution by Titus was shorter till Titus help me to improve my way. Maybe the way I found is interesting for you

# Answer
> 1 votes
## Retina, 60 bytes

```
^(.*)(\n(?!\1).*)*(\n(\1.*)).*(\n((?!\1)|\4).*)*$
$4
s`\n.*

```

The trailing new line is significant. Takes input as the string on a line and then each word on a separate line (but no trailing newline!). Works in a similar way to my JavaScript answer by matching the longest common prefix of all lines that begin with the string on the first line. If it doesn't find one then it simply deletes all the words.

# Answer
> 0 votes
# Scala, 119 bytes

```
def f(s:String,a:Seq[Char]*)=a filter(_ startsWith s)reduceOption(_ zip _ takeWhile(t=>t._1==t._2)map(_._1))getOrElse s

```

Ungolfed:

```
def tabComplete(input: String, options: Seq[Char]*) = {
  options.
  filter((x: String) => x.startsWith(input)).
  reduceOption((x: Seq[Char], y: Seq[Char]) =>
    x.zip(y).
    takeWhile((t: (Char, Char)) => t._1 == t._2).
    map((t: (Char, Char)) => t._1)
  ).getOrElse(input)
}

```

Explanation:

```
def g(s:String,a:Seq[Char]*)= //define a method g with a string and a vararg array of strings as parameter
  a filter(_ startsWith s)    //filter the options to contains only elements starting with the input
  reduceOption(               //if the filtered array is nonempty, reduce it:
    _ zip _                     //zip two elements together
    takeWhile(t=>t._1==t._2)    //take the tuples while they contain the same char
    map(_._1)                   //take the first element from each tuple
  )getOrElse s                //else return the input

```

# Answer
> 0 votes
# PowerShell, 101 bytes

*Based on Nail's awesome regexp*.

```
if($args-join'
'-cmatch'^(.*)(\n(?!\1).*)*(\n(\1.*)).*(\n((?!\1)|\4).*)*$'){$Matches.4}else{$args[0]}

```

Try it online!

# Answer
> 0 votes
# 05AB1E, 14 bytes

```
ʒIÅ?}€ηøʒË}‚˜θ

```

Try it online or verify all test cases.

**Explanation:**

```
ʒ   }           # Filter the (implicit) input-list
 IÅ?            #  Does it start with the (second) input-string
                #   i.e. ["codex","bla","codegolf"] and "c" → ["codex","codegolf"]
     €η         # Then take the prefixes of every remaining string
                #  → [["c","co","cod","code","codex"],
                #     ["c","co","cod","code","codeg","codego","codegol","codegolf"]]
       ø        # Zip/transpose; swapping rows/columns
                #  → [["c","c"],["co","co"],["cod","cod"],["code","code"],["codex","codeg"]]
        ʒ }     # Filter:
         Ë      #  Only keep sublists which only contain the same substrings
                #   → [["c","c"],["co","co"],["cod","cod"],["code","code"]]
           ‚    # Pair it with the (second implicit) input
                #  → ["c",["c","c"],["co","co"],["cod","cod"],["code","code"]]
                # (workaround if nothing in the input-list starts with the input-string)
            ˜   # Flatten this list
                #  → ["c","c","c","co","co","cod","cod","code","code"]
             θ  # And only leave the last item (which is output implicitly as result)
                #  → "code"

```

# Answer
> 0 votes
# Gaia, 12 bytes

```
e…¦&⊢…Ė⁇_+ₔ)

```

Try it online!

Takes input as B, then A.

```
e		| eval B as list of strings
 …¦		| take prefixes of each string
   &⊢		| reduce by set intersection
     …		| take list prefixes of each.
      Ė⁇	| Keep only those with A as an element
	_	| flatten
	 +ₔ	| add A to the beginning of the list
	   )	| take the last element

```

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


title: Valid Badminton Score?

text:
# Question
Title: Valid Badminton Score?
## Introduction:

I saw there was only one other badminton related challenge right now. Since I play badminton myself (for the past 13 years now), I figured I'd add some badminton-related challenges. Here the first one:

## Challenge:

**Input:** Two integers
**Output:** One of three distinct and unique outputs of your own choice. One indicating that the input is a valid badminton score AND the set has ended with a winner; one indicating that the input is a valid badminton score AND the set is still in play; one indicating the input is not a valid badminton score.

With badminton, both (pairs of) players start with 0 points, and you stop when one of the two (pairs of) players has reached a score of 21, with at least 2 points difference, up to a maximum of 30-29.

So these are all possible input-pairs (in either order) indicating it's a valid badminton score AND the set has ended:

```
[[0,21],[1,21],[2,21],[3,21],[4,21],[5,21],[6,21],[7,21],[8,21],[9,21],[10,21],[11,21],[12,21],[13,21],[14,21],[15,21],[16,21],[17,21],[18,21],[19,21],[20,22],[21,23],[22,24],[23,25],[24,26],[25,27],[26,28],[27,29],[28,30],[29,30]]

```

And these are all possible input-pairs (in either order) indicating it's a valid badminton score BUT the set is still in play:

```
[[0,0],[0,1],[0,2],[0,3],[0,4],[0,5],[0,6],[0,7],[0,8],[0,9],[0,10],[0,11],[0,12],[0,13],[0,14],[0,15],[0,16],[0,17],[0,18],[0,19],[0,20],[1,1],[1,2],[1,3],[1,4],[1,5],[1,6],[1,7],[1,8],[1,9],[1,10],[1,11],[1,12],[1,13],[1,14],[1,15],[1,16],[1,17],[1,18],[1,19],[1,20],[2,2],[2,3],[2,4],[2,5],[2,6],[2,7],[2,8],[2,9],[2,10],[2,11],[2,12],[2,13],[2,14],[2,15],[2,16],[2,17],[2,18],[2,19],[2,20],[3,3],[3,4],[3,5],[3,6],[3,7],[3,8],[3,9],[3,10],[3,11],[3,12],[3,13],[3,14],[3,15],[3,16],[3,17],[3,18],[3,19],[3,20],[4,4],[4,5],[4,6],[4,7],[4,8],[4,9],[4,10],[4,11],[4,12],[4,13],[4,14],[4,15],[4,16],[4,17],[4,18],[4,19],[4,20],[5,5],[5,6],[5,7],[5,8],[5,9],[5,10],[5,11],[5,12],[5,13],[5,14],[5,15],[5,16],[5,17],[5,18],[5,19],[5,20],[6,6],[6,7],[6,8],[6,9],[6,10],[6,11],[6,12],[6,13],[6,14],[6,15],[6,16],[6,17],[6,18],[6,19],[6,20],[7,7],[7,8],[7,9],[7,10],[7,11],[7,12],[7,13],[7,14],[7,15],[7,16],[7,17],[7,18],[7,19],[7,20],[8,8],[8,9],[8,10],[8,11],[8,12],[8,13],[8,14],[8,15],[8,16],[8,17],[8,18],[8,19],[8,20],[9,9],[9,10],[9,11],[9,12],[9,13],[9,14],[9,15],[9,16],[9,17],[9,18],[9,19],[9,20],[10,10],[10,11],[10,12],[10,13],[10,14],[10,15],[10,16],[10,17],[10,18],[10,19],[10,20],[11,11],[11,12],[11,13],[11,14],[11,15],[11,16],[11,17],[11,18],[11,19],[11,20],[12,12],[12,13],[12,14],[12,15],[12,16],[12,17],[12,18],[12,19],[12,20],[13,13],[13,14],[13,15],[13,16],[13,17],[13,18],[13,19],[13,20],[14,14],[14,15],[14,16],[14,17],[14,18],[14,19],[14,20],[15,15],[15,16],[15,17],[15,18],[15,19],[15,20],[16,16],[16,17],[16,18],[16,19],[16,20],[17,17],[17,18],[17,19],[17,20],[18,18],[18,19],[18,20],[19,19],[19,20],[20,20],[20,21],[21,21],[21,22],[22,22],[22,23],[23,23],[23,24],[24,24],[24,25],[25,25],[25,26],[26,26],[26,27],[27,27],[27,28],[28,28],[28,29],[29,29]]

```

Any other pair of integer would be an invalid badminton score.

## Challenge rules:

* I/O is flexible, so:
    + You can take the input as a list of two numbers; two separated numbers through STDIN or function parameters; two strings; etc.
    + Output will be three distinct and unique values of your own choice. Can be integers (i.e. `[0,1,2]`, `[1,2,3]`, `[-1,0,1]`, etc.); can be Booleans (i.e. `[true,false,undefined/null/empty]`); can be characters/strings (i.e. `["valid & ended","valid","invalid"]`); etc.
    + **Please specify the I/O you've used in your answer!**
* **You are allowed to take the input-integers pre-ordered from lowest to highest or vice-versa.**
* The input integers can be negative, in which case they are of course invalid.

## General rules:

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

## Test cases:

These test cases are valid, and the set has ended:

```
0 21
12 21
21 23
28 30
29 30

```

These test cases are valid, but the set is still in play:

```
0 0
0 20
12 12
21 21
21 22

```

These test cases are invalid:

```
-21 19
-19 21
-1 1
12 22
29 31
30 30
42 43
1021 1021

```

# Answer
> 1 votes
# Stax, 20 bytes

```
ÇåπßéD╩¬7▼ß▌ΣU¬í╡S┤╘

```

Run and debug it

It takes input in the same format as the examples. `0` means there's a valid winner. `1` means the game is in progress. `-1` means invalid score.

In pseudo-code, with ordered inputs `x` and `y`, the algorithm is

```
sign(clamp(x + 2, 21, 30) - y) | (x < 0 || x >= 30 ? 0 : -1)

```
* `sign` means numeric sign (`-1`, `0`, or `1`)
* `clamp` forces its first argument into the specified half-open interval

# Answer
> 7 votes
# Python 2, 47 bytes

```
lambda a,b:[61>60-a>b<3+max(19,a)for b in-~b,b]

```

Try it online!

Outputs a list of two Booleans. Thanks to TFeld for writing a test suite in their answer that made it easy to check my solution.

```
ended: [False, True]
going: [True, True]
invalid: [False, False]

```

The key insight is that a valid score ends the game exactly if increasing the higher value `b` makes the score invalid. So, we just code up the validity condition, and check it for `(a,b+1)` in addition to `(a,b)` to see if the game has ended.

Validity is checked via three conditions that are chained together:

* `b<3+max(19,a)`: Checks that the higher score `b` isn't past winning, with either `b<=21` or `b<=a+2` (win by two)
* `60-a>b`: Equivalent to `a+b<=59`, ensuring the score isn't above `(29,30)`
* `61>60-a`: Equivalent to `a>=0`, ensures the lower score is non-negative

---

# Python 2, 44 bytes

```
lambda a,b:[b-61<~a<a>b/22*b-3for b in-~b,b]

```

Try it online!

An improved validity check by TFeld saves 3 bytes. The main idea is to branch on "overtime" `b>21` with `b/22*b` which effectively sets below-21 scores to zero, whereas I'd branched on `a>19` with the longer `max(19,a)`.

---

# Python 2, 43 bytes

```
lambda a,b:a>>99|cmp(2+max(19,a)%30-a/29,b)

```

Try it online!

Outputs:

```
ended: 0
going: -1
invalid: 1

```

Assumes that the inputs are not below \\$-2^{99}\\$.

# Answer
> 6 votes
# Python 2, ~~97~~ ~~95~~ ~~75~~ ~~72~~ ~~71~~ ~~70~~ ~~69~~ ~~64~~ ~~55~~ ~~54~~ ~~52~~ ~~51~~ ~~50~~ 48 bytes

```
lambda a,b:(b-61<~a<a>b/22*b-3)*~(19<b-(b<30)>a)

```

Try it online!

Takes input as pre-ordered `a,b`.

Returns `-2`, `-1`, `0` for `ended`, `in play`, `invalid`.

-1 byte, thanks to Kevin Cruijssen

---

Left part (`b-61<~a<a>b/22*b-3`) is a validity-check, and right part (`19<b-(b<30)>a`) is a check for game ended.

# Answer
> 4 votes
# JavaScript (ES6),  ~~55 53~~  48 bytes

*Thanks to @KevinCruijssen for noticing that I was not fully assuming \\$a\le b\\$ (saving 5 bytes)*

Takes input as `(a)(b)` with \\$a\le b\\$. Returns \\$0\\$ (valid), \\$1\\$ (ended) or \\$2\\$ (invalid).

```
a=>b=>a<0|a>29|b>30|b>21&b-a>2?2:b>20&b-a>1|b>29

```

Try it online!

# Answer
> 4 votes
# Jelly, 25 bytes

```
»19«28‘<‘×+2>ɗʋ⁹×,%Ƒ“œþ‘ɗ

```

Try it online!

Left argument: minimum. Right argument: maximum.
Invalid: `0`. Ongoing: `1`. Ended: `2`.

Mathematically, this works as below (the left argument is \\$x\\$, the right is \\$y\\$):

$$\[a\]=\cases{a\colon1\\\lnot a\colon0}\\\otimes(a,b)=(a\bmod30,b\bmod31)\\x,y\in\mathbb Z\\X:=\min(\max(x+1,20),29)\\p:=(x,y)\\\(\[X\<y\]+1)\[X+2\>y\]\[p=\otimes p\]$$

Explanation:

```
»19«28‘<‘×+2>ɗʋ⁹×,%Ƒ“œþ‘ɗ Left argument: x, Right argument: y
»19«28‘                   X := Bound x + 1 in [20, 29]:
»19                         X := max(x, 19).
   «28                      X := min(X, 28).
      ‘                     X := X + 1.
       <‘×+2>ɗʋ⁹          X := If X + 2 <= y, then 0, else if X < y, then 2, else 1:
       <                    t := If X < y, then 1, else 0.
        ‘                   t := t + 1.
          +2>ɗ              u := Check if X + 2 > y:
          +2                  u := X + 2.
            >                 u := If u > y, then 1, else 0.
         ×                  X := t * u.
                 ,%Ƒ“œþ‘ɗ z := If x mod 30 = x and y mod 31 = y, then 1, else 0:
                 ,          z := (x, y).
                  % “œþ‘    m := z mod (30, 31) = (x mod 30, y mod 31).
                   Ƒ        z := If z = m, then 1, else 0.
                ×         X * z.

```

# Answer
> 4 votes
# C# (Visual C# Interactive Compiler), ~~53~~ 52 bytes

```
a=>b=>b<0|a-b>2&a>21|b>29|a>30?3:a>20&a-b>1|a>29?1:2

```

Called as `f(max)(min)`. Returns 3 for invalid, 1 for finished, 2 for ongoing.

Saved 1 byte thanks to Kevin Cruijjsen

Try it online!

# Answer
> 3 votes
# VDM-SL, 80 bytes

```
f(i,j)==if(j-i>2and j>21)or(i<0or i=30or j>30)then{}else{(j>20and j-i>1or j=30)}

```

This function takes the scores ordered in ascending order and returns the empty set if the score is invalid or the set containing whether the set is complete (so {true} if the set is complete and valid and {false} if the set is incomplete and valid)

A full program to run might look like this:

```
functions
f:int*int+>set of bool
f(i,j)==if(j-i>2and j>21)or(i<0or i=30or j>30)then{}else{(j>20and j-i>1or j=30)}

```

### Explanation:

```
if(j-i>2 and j>21)             /*if scores are too far apart*/
or(i<0 or i=30 or j>30)        /*or scores not in a valid range*/
then {}                        /*return the empty set*/
else{                       }  /*else return the set containing...*/
     (j>20 and j-i>1 or j=30)  /*if the set is complete*/

```

# Answer
> 3 votes
# Java (JDK), ~~59~~ 48 bytes

```
a->b->b<0|b>29|a>b+2&a>21|a>30?0:a<21|a<30&a<b+2

```

Try it online!

Returns an `Object`, which is the `Integer` `0` for invalid games and the `Boolean`s `true` and `false` for valid ongoing games and for valid finished games respectively. Takes the score ordered (and curried), with the higher score first.

`-2 bytes` by inverting the end-of-match check.
`-11 bytes` by currying, using bitwise operators, and some return type autoboxing trickery - thanks to @KevinCruijssen

## Ungolfed

```
a->                      // Curried: Target type IntFunction<IntFunction<Object>>
    b->                  // Target type IntFunction<Object>
                         // Invalid if:
            b<0          //    Any score is negative
          | b > 29       //    Both scores above 29
          |   a > b + 2  //    Lead too big
            & a > 21     //        and leader has at least 21 points
          | a > 30       //    Anyone has 31 points
        ? 0              // If invalid, return 0 (autoboxed to Integer)
                         // If valid, return whether the game is ongoing (autoboxed to Boolean)
                         // Ongoing if:
        :   a < 21       //    Nobody has 21 points
          |   a < 30     //    Leader has fewer than 30 points
            & a < b + 2  //        and lead is small

```

# Answer
> 3 votes
# APL (Dyalog Unicode), 35 bytesSBCS

Infix tacit function where ended is 2, ongoing is 1, invalid is 0, smaller and larger scores are left.

```
(,≡30 31|,)×(⊢<2+X)×1+⊢>X←29⌊20⌈1+⊣

```

Try it online!

Implements Erik the Outgolfer's mathematical formulas combined into

$$X:=\min(\max(x+1,20),29)\\\ (\[X\< y\]+1)\[X+2\>y\]\[(x,y)=(x\bmod30,y\bmod31)\]$$ rearranged (as if traditional mathematical notation had vectorisation and inline assignments) to

$$\[(x,y)=(x,y)\bmod(30,31)\]×\[y\<2+X\]×(1+\[y\< (X:=\min(29,\max(20,1+x)))\])$$

and translated directly to APL (which is strictly right-associative, so we avoid some parentheses):

$$((x,y)≡30\ 31|x,y)×(y\<2+X)×1+y\>X←29⌊20⌈1 +x$$

This can be converted into a tacit function simply by substituting \\$⊣\\$ for \\$x\\$ and \\$⊢\\$ for \\$y\\$, symbolising the left and right arguments rather than the two variables:

$$((⊣,⊢)≡30\ 31|⊣,⊢)×(⊣\<2+X)×1+⊢\>X←29⌊20⌈1+⊣$$

Now \\$⊣⎕⊢\\$ is equivalent to \\$⎕\\$ for any infix function \\$⎕\\$, so we can simplify to

$$(,≡30\ 31|,)×(⊣\<2+X)×1+⊢\>X←29⌊20⌈1+⊣$$

which is our solution; `(,≡30 31|,)×(⊢<2+X)×1+⊢>X←29⌊20⌈1+⊣`:

the left argument; \\$x\\$
`1+` one plus that; \\$1+x\\$
`20⌈` maximum of 20 and that; \\$\max(20,…)\\$
`29⌊` minimum of 29 and that; \\$\min(29,…)\\$
`X←` assign that to `X`; \\$X:=…\\$
`⊢>` is the right argument greater (0/1)?; \\$\[y\>…\]\\$
`1+` add one; \\$1+…\\$
`(` multiply the following by that; \\$(…)×…\\$
`2+X` two plus `X`; \\$2+X\\$
`⊢<` is the right argument less than that (0/1); \\$\[y\<…\]\\$
`(` multiply the following by that; \\$(…)×…\\$
`,` concatenate the arguments; \\$(x,y)\\$
`30 31|` remainders when divided by these numbers; \\$…\mod(30,31)\\$
`,≡` are the concatenated arguments identical to that (0/1)?; \\$\[(x,y)=…\]\\$

# Answer
> 3 votes
# x86 Assembly, 42 Bytes

Takes input in `ECX` and `EDX` registers. Note that `ECX` must be greater than `EDX`.
Outputs into `EAX`, where `0` means the game's still on, `1` representing the game being over and `-1` (aka `FFFFFFFF`) representing an invalid score.

```
31 C0 83 F9 1E 77 1F 83 FA 1D 77 1A 83 F9 15 7C
18 83 F9 1E 74 12 89 CB 29 D3 83 FB 02 74 09 7C
08 83 F9 15 74 02 48 C3 40 C3

```

Or, more readable in Intel Syntax:

```
check:
    XOR EAX, EAX
    CMP ECX, 30     ; check i_1 against 30
    JA .invalid     ; if >, invalid.
    CMP EDX, 29     ; check i_2 against 29
    JA .invalid     ; if >, invalid.
    CMP ECX, 21     ; check i_1 against 21
    JL .runi        ; if <, running.
    CMP ECX, 30     ; check i_1 against 30
    JE .over        ; if ==, over.
    MOV EBX, ECX
    SUB EBX, EDX    ; EBX = i_1 - i_2
    CMP EBX, 2      ; check EBX against 2
    JE .over        ; if ==, over.
    JL .runi        ; if <, running.
                    ; if >, keep executing!
    CMP ECX, 21     ; check i_1 against 21
    JE .over        ; if ==, over.
                    ; otherwise, it's invalid.
    ; fallthrough!
    .invalid:
        DEC EAX     ; EAX = -1
        RETN
    .over:
        INC EAX     ; EAX = 1
    ; fallthrough!
    .runi:
        RETN        ; EAX = 0 or 1

```

Fun fact: this function *almost* follows the C Calling Convention's rules on which registers to preserve, except I had to clobber `EBX` to save some bytes on stack usage.

---

### Optional (not included in byte-count)

By adding the following 6 bytes directly before start of the code above, you can pass `ECX` and `EDX` unordered:

```
39 D1 7D 02 87 CA

```

Which is the following in readable Intel Syntax:

```
CMP ECX, EDX
JGE check
XCHG ECX, EDX

```

# Answer
> 2 votes
# Retina 0.8.2, 92 bytes

```
\d+
$*
^(1{0,19},1{21}|(1{20,28}),11\2|1{29},1{30})$|^(1*,1{0,20}|(1{0,28}),1?\4)$|.+
$#1$#3

```

Try it online! Link includes test cases. Takes input in ascending order. Explanation: The first stage simply converts from decimal to unary so that the scores can be properly compared. The second stage contains six alternate patterns, grouped into three groups so that three distinct values can be output, which are `10` for win, `01` for ongoing and `00` for illegal. The patterns are:

* Against 0-19, a score of 21 is a win
* Against 20-28, a score of +2 is a win
* Against 29, a score of 30 is a win
* Against any (lower) score, a score of 0-20 is ongoing
* Against a score of up to 28, a score of +1 is ongoing
* Anything else (including negative scores) is illegal

# Answer
> 1 votes
# Bash 4+, ~~97~~ ~~89~~ ~~91~~ 88 bytes

Assume that inputs are ascending. Used concepts from VDM-SL answer. Try it Online
`z==0` \- game in progress
`z==1` \- game completed
`z==2` \- invalid

***-8** by bracket cleanup from `(( & | ))` conditions*
***+2** fixing a bug, thanks to Kevin Cruijssen*
***-3** logic improvements by Kevin Cruijssen*

```
i=$1 j=$2 z=0
((j-i>2&j>21|i<0|i>29|j>30?z=2:0))
((z<1&(j>20&j-i>1|j>29)?z=1:0))
echo $z

```

# Answer
> 1 votes
# APL (Dyalog Unicode), ~~33~~ 32 bytesSBCS

```
{h⍵+1 0}+h←(⊢≡31 30|⊢)×21 2∨.≥-\

```

Try it online!

in: a pair in descending order

out: 2=ongoing, 1=ended, 0=invalid

tests stolen from Adám's answer

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


title: Expand and Contract

text:
# Question
Title: Expand and Contract
Take a positive integer \\$k\\$ as input. Start with \\$n := 1\\$ and repeatedly increase \\$n\\$ by the largest integer power of ten \\$i\\$ such that \\$i \le n\\$ and \\$i + n \le k\\$.

Repeat until \\$n = k\\$ and return a list of all intermediate values of \\$n\\$, including both the initial \\$1\\$ and the final \\$k\\$.

During this process, growth will initially be limited by the former inequality, and only afterwards by the latter; the growth will take the form of an initial "expansion" period, during which \\$n\\$ is increased by ever-larger powers, followed by a "contract" period, during which \\$n\\$ is increased by ever-smaller powers in order to "zoom in" on the correct number.

## Test Cases

```
1 => [1]
10 => [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
321 => [1,  2,  3,  4,  5,  6,  7,  8,  9,
        10, 20, 30, 40, 50, 60, 70, 80, 90,
        100, 200, 300, 310, 320, 321]
1002 => [1,   2,   3,   4,   5,   6,   7,   8,   9,
         10,  20,  30,  40,  50,  60,  70,  80,  90,
         100, 200, 300, 400, 500, 600, 700, 800, 900,
         1000, 1001, 1002]

```

This is , so the shortest answer (in bytes) wins.

# Answer
> 8 votes
# Haskell, 72 68 64 63 bytes

```
f=(1!)
c!t|t==c=[c]|t>c=c:(c+10^(pred.length.show.min c$t-c))!t

```

Try it online!

Thanks Sriotchilism O'Zaic for -4 bytes!

### Usage

```
f 321
[1,2,3,4,5,6,7,8,9,10,20,30,40,50,60,70,80,90,100,200,300,310,320,321]

```

### Explanation

```
c!t         -- c=current number, t=target number
 |t==c=[c]  -- Target is reached, return last number
 |t>c=c:(c+10^(pred.length.show.min c$t-c))!t
      c:                                        -- Add current number to list
                                min c$t-c       -- The minimum of the current number, and the difference between the current number and the target
                    length.show.                -- The length of this number
               pred.                            -- Minus 1
           10^(                          )      -- Raise 10 to this power
         c+                                     -- Add that to the current number
        (                                 )!t   -- Recursion

```

# Answer
> 6 votes
# JavaScript (ES6), 50 bytes

```
f=n=>n?[...f(n-(1+/(^10)?(0*$)/.exec(n)[2])),n]:[]

```

Try it online!

## How?

### Theory

The following steps are repeated until \\$n=0\\$:

* look for the number \\$k\\$ of trailing zeros in the decimal representation of \\$n\\$
* decrement \\$k\\$ if \\$n\\$ is an exact power of \\$10\\$
* subtract \\$x=10^k\\$ from \\$n\\$

### Implementation

The value of \\$x\\$ is directly computed as a string with the following expression:

```
+---- leading '1'
|
1 + /(^10)?(0*$)/.exec(n)[2]
     \____/\___/
        |    |
        |    +---- trailing zeros (the capturing group that is appended to the leading '1')
        +--------- discard one zero if n starts with '10'

```

**Note**: Excluding the leading `'10'` only affects exact powers of \\$10\\$ (e.g. \\$n=\color{red}{10}\color{green}{00}\\$) but does not change the number of captured trailing zeros for values such as \\$n=\color{red}{10}23\color{green}{00}\\$ (because of the extra non-zero middle digits, `'10'` is actually not matched at all in such cases).

# Answer
> 3 votes
# Python 2, 61 bytes

```
f=lambda k,n=1:n<k and[n]+f(k,n+10**~-len(`min(n,k-n)`))or[n]

```

Try it online!

# Answer
> 2 votes
# Perl 6, ~~48~~ 41 bytes

```
->\k{1,{$_+10**min($_,k-$_).comb/10}...k}

```

Try it online!

### Explanation:

```
->\k{                                   }  # Anonymous code block taking k
     1,                             ...k   # Start a sequence from 1 to k
       {                           }       # Where each element is
        $_+          # The previous element plus
           10**      # 10 to the power of
                           .comb     # The length of
               min($_,k-$_)          # The min of the current count and the remainder
                                /10  # Minus one

```

# Answer
> 2 votes
# APL (Dyalog Unicode), 30 bytesSBCS

Anonymous tacit prefix function. Prints numbers on separate lines to stdout.

```
{⍺=⍵:⍺⋄⍺∇⍵+10*⌊/⌊10⍟⍵,⍺-⎕←⍵}∘1

```

Try it online!

`{``}∘1` anonymous infix lambda with 1 curried as initial \\$n\\$:

`⍺=⍵` if \\$k\\$ and \\$n\\$ are equal:

return (and implicitly print) \\$k\\$

else:

`⎕←⍵` print \\$n\\$

`⍺-` subtract that from \\$k\\$

`⍵,` prepend \\$n\\$

`10⍟`\\$\log\_{10}\\$ of those

floor those

`⌊/` minimum of those

`10*` ten raised to the power of that

`⍵+`\\$n\\$ plus that

`⍺∇` recurse using same \\$k\\$ and new \\$n\\$

# Answer
> 2 votes
# 05AB1E, 15 bytes

```
1[=ÐIαD_#‚ßg<°+

```

Port of *@PaulMutser*'s (first) Haskell answer, so make sure to upvote him!!

Try it online or verify all test cases.

Outputs the numbers newline delimited.
If it must be a list, I'd have to add 3 bytes:

```
X[DˆÐIαD_#‚ßg<°+}¯

```

Try it online or verify all test cases.

**Explanation:**

```
1             # Push a 1 to the stack
 [            # Start an infinite loop
  =           #  Print the current number with trailing newline (without popping it)
  Ð           #  Triplicate the current number
   Iα         #  Get the absolute difference with the input
     D        #  Duplicate that absolute difference
      _       #  If this difference is 0:
       #      #   Stop the infinite loop
      ‚ß      #  Pair it with the current number, and pop and push the minimum
        g<°   #  Calculate 10 to the power of the length of the minimum minus 1
           +  #  And add it to the current number

```

# Answer
> 1 votes
# Jelly, 19 bytes

```
1µ«³_$DL’⁵*$+µ<³$Ð¿

```

Try it online!

# Answer
> 1 votes
# Wolfram Language (Mathematica), 51 bytes

```
Union@NestList[#+10^Floor@Log10@Min[s-#,#]&,1,s=#]&

```

Try it online!

# Answer
> 1 votes
## Batch, 131 bytes

```
@set/an=i=1
:e
@if %n%==%i%0 set i=%i%0
@echo %n%
:c
@set/an+=i
@if %n% leq %1 goto e
@set/an-=i,i/=10
@if %i% neq 0 goto c

```

Takes input as a command-line parameter and outputs the list of numbers to STDOUT. Explanation:

```
@set/an=i=1

```

Start with `n=1` and `i=1` representing the power of 10.

```
:e
@if %n%==%i%0 set i=%i%0

```

Multiply `i` by 10 if `n` has reached the next power of 10.

```
@echo %n%

```

Output the current value of `n`.

```
:c
@set/an+=i
@if %n% leq %1 goto e

```

Repeat while `i` can be added to `n` without it exceeding the input.

```
@set/an-=i,i/=10

```

Restore the previous value of `n` and divide `i` by 10.

```
@if %i% neq 0 goto c

```

If `i` is not zero then try adding `i` to `n` again.

# Answer
> 1 votes
# , 67 65 bytes

-2 bytes thanks to Giuseppe

```
k=scan();o=1;i=10^(k:0);while(T<k)o=c(o,T<-T+i[i<=T&i+T<=k][1]);o

```

Pretty simple. It takes a set of powers of 10 beyond what would be needed in reverse order `i`.

(I would prefer to use `i=10^rev(0:log10(k))` instead of `i=10^(k:0)` since the latter is computationally ineffecient, but golf is golf!).

Then in a while loop, applies the conditions to `i` and takes the first (i.e. largest); updates `n`, and appends to output

Try it online!

# Answer
> 1 votes
# Jelly, 12 bytes

```
1+«ạæḟ⁵«Ɗɗ¥Ƭ

```

Try it online!

# Answer
> 1 votes
# Pip, 27 bytes

```
Wa>Po+:y/t*Y1Ty>o|o+y>ay*:t

```

Try it online!

In pseudocode:

```
a = args[0]
o = 1
print o
while a > o {
  y = 1
  till y > o || o + y > a
    y *= 10
  o += y / 10
  print o
}

```

I'm pretty pleased with the golfing tricks I was able to apply to shorten this algorithm. By initializing, updating, and printing stuff in the loop header, I was able to avoid needing curly braces for the loop body. There's probably a golfier algorithm, though.

# Answer
> 0 votes
# Japt, 18 bytes

```
ÆT±ApTmTnU)sÊÉÃf§U

```

Try it

```
ÆT±ApTmTnU)sÊÉÃf§U     :Implicit input of integer U
Æ                      :Map the range [0,U)
 T±                    :  Increment T (initially 0) by
   A                   :  10
    p                  :  Raised to the power of
     Tm                :    The minimum of T and
       TnU             :      T subtracted from U
          )            :    End minimum
           s           :    Convert to string
            Ê          :    Length
             É         :    Subtract 1
              Ã        :End map
               f       :Filter
                §U     :  Less than or equal to U

```

# Answer
> 0 votes
# C# (Visual C# Interactive Compiler), ~~123~~ 122 bytes

```
m=>{var a=new[]{1}.ToList();int s;for(;(s=a.Last())<m;)a.Add(s+(int)Math.Pow(10,(int)Math.Log(s<m-s?s:m-s,10)));return a;}

```

Try it online!

# Answer
> 0 votes
# Prolog (SWI), 142 bytes

```
L-D-M:-append(L,[D],M).
N-L-C-X-R-I:-I=1,C is X*10,N-L-C-C-R-1;D is C+X,(D<N,L-D-M,N-M-D-X-R-I;D>N,N-L-C-(X/10)-R-0;L-D-R).
N-R:-N-[]-0-1-R-1.

```

Try it online!

Explanation coming tomorrow or something

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