title: Covering a Skyline with brush strokes

text:
# Question
Title: Covering a Skyline with brush strokes
Given a non-negative integer skyline height list, answer how many uninterrupted 1-unit-high horizontal brush strokes are needed to cover it.

`[1,3,2,1,2,1,5,3,3,4,2]`, visualised as:

```
      5
      5  4
 3    5334
 32 2 53342
13212153342

```

needs nine brush strokes:

```
      1
      2  3
 4    5555
 66 7 88888
99999999999

```

### Examples

`[1,3,2,1,2,1,5,3,3,4,2]``9`

`[5,8]``8`

`[1,1,1,1]``1`

`[]``0`

`[0,0]``0`

`[2]``2`

`[2,0,2]``4`

`[10,9,8,9]``11`

# Answer
> 36 votes
# JavaScript (Node.js), 38 bytes

```
a=>a.map(v=>(n+=v>p&&v-p,p=v),p=n=0)|n

```

Try it online!

Simply a greedy algorithm which scan from left to right, only draw lines if needed, and draw it as long as possible.

Thanks Arnauld, save ~~2~~ 3 bytes

# Answer
> 31 votes
# 05AB1E,  ~~8 7~~  5 bytes

*Saved 2 bytes thanks to @Adnan*

```
0š¥þO

```

Try it online!

### How?

This is using the algorithm that was first found by @tsh. If you like this answer, make sure to upvote their answer as well!

Each time a skyscraper is lower than or as high as the previous one, it can be painted 'for free' by simply extending the brushstrokes.

For instance, painting skyscrapers \\$B\\$ and \\$C\\$ in the figure below costs nothing.

On the other hand, we need 2 new brushstrokes to paint skyscraper \\$E\\$, no matter if they're going to be reused after that or not.

For the first skyscraper, we always need as many brushstrokes as there are floors in it.

Turning this into maths:

$$S=h\_0+\sum\_{i=1}^n \max(h\_i-h\_{i-1},0)$$

If we prepend \\$0\\$ to the list, this can be simplified to:

$$S=\sum\_{i=1}^n \max(h\_i-h\_{i-1},0)$$

### Commented

```
0š¥þO     # expects a list of non-negative integers  e.g. [10, 9, 8, 9]
0š        # prepend 0 to the list                    -->  [0, 10, 9, 8, 9]
  ¥       # compute deltas                           -->  [10, -1, -1, 1]
   þ      # keep only values made of decimal digits
          # (i.e. without a minus sign)              -->  ["10", "1"]
    O     # sum                                      -->  11

```

# Answer
> 8 votes
# Haskell, 32 bytes

```
(0%)
p%(h:t)=max(h-p)0+h%t
p%_=0

```

Try it online!

An improvement on Lynn's solution that tracks the previous element `p` instead of looking at the next element. This makes the base case and recursive call shorter in exchange for needing to invoke `(0%)`.

`max(h-p)0` could be `max h p-p` for the same length.

# Answer
> 7 votes
# Python 3, 37 bytes

```
lambda a:sum(a)-sum(map(min,a[1:],a))

```

Try it online!

<sub>-5 bytes by switching to Python 3, thanks to Sarien</sub>

---

# Python 2, ~~47~~ ~~43~~ 42 bytes

```
lambda a:sum(a)-sum(map(min,a[1:],a[:-1]))

```

Try it online!

Alt:

```
lambda a:sum(a)-sum(map(min,zip(a[1:],a)))

```

Try it online!

# Answer
> 7 votes
# Haskell, 35 bytes

```
f(a:b:c)=max(a-b)0+f(b:c)
f a=sum a

```

Try it online!

Line 2 could be `f[a]=a` if I didn't also have to handle the case `[]`.

# Answer
> 6 votes
# Jelly, 5 bytes

A port of my 05AB1E answer, which itself is similar to @tsh JS answer.

```
ŻI0»S

```

Try it online!

### Commented

```
ŻI0»S    - main link, expecting a list of non-negative integers  e.g. [10, 9, 8, 9]
Ż        - prepend 0                                             -->  [0, 10, 9, 8, 9]
 I       - compute the deltas                                    -->  [10, -1, -1, 1]
  0»     - compute max(0, v) for each term v                     -->  [10, 0, 0, 1]
    S    - sum                                                   -->  11

```

# Answer
> 5 votes
# K (oK), ~~12~~ 7 bytes

-5 bytes thanks to ngn!

A k (oK) port of Arnauld's 05AB1E solution (and tsh's JavaScript solution):

```
+/0|-':

```

Try it online!

# , 15 bytes

A J port of Arnauld's 05AB1E solution (and tsh's JavaScript solution):

```
1#.0>./2-~/\0,]

```

Try it online!

## My naive solution:

# , 27 bytes

```
1#.2(1 0-:])\0,@|:@,~1$~"0]

```

Try it online!

# Answer
> 5 votes
# Haskell, ~~34~~ 32 bytes

*2 bytes trimmed by Lynn*

```
g x=sum$max 0<$>zipWith(-)x(0:x)

```

Try it online!

So to start we have `zipWith(-)`. This takes two lists and produces a new list of their pairwise differences. We then combine it with `x` and `(0:x)`. `(0:)` is a function that adds zero to the front of a list and by combining it with `zipWith(-)` we get the differences between consecutive elements of that list with a zero at the front. Then we turn all the negative ones to zero with `(max 0<$>)`. This creates a new list where each element is the number of new strokes that has to be started at each tower. To get the total we just sum these with `sum`.

# Answer
> 5 votes
# Dyalog APL, 11 bytes

```
+/0⌈¯2-/0,⊢

```

`,` concatenate, so `0,` concatenates 0.

`¯2-/`
or
`¯2` length of window. (minus means the window is rotated)
`-/` does a window operation of `-`(minus) with window size `2`

`0⌈` the operation is called ceiling, but when it gets an input from both sides it also does "get the larger of the two inputs" so `0⌈1 3 0 ¯2` will give `1 3 0 0`.

and finally, a `+/` which is a sum.

Try it!

# Answer
> 3 votes
# Japt, 8 bytes

*-2 bytes from @Shaggy*

```
mîT Õ¸¸è

```

**Explanation**

```
mîT Õ¸¸è      Full program. Implicit input U
                e.g. U = [2,0,2]
mîT             Map each item X and repeat T(0) X times
                     U = ["00","","00"]
    Õ           Transpose rows with columns
                     U = ["0 0","0 0"]
     ¸¸         Join using space and then split in space
                     U = ["0","0","0","0"]
        è       Return the count of the truthy values

```

Try it online!

# Answer
> 3 votes
# MATL, 8 bytes

```
0whd3Y%s

```

Try it online!

Pretty much @Arnauld's algorithm. Saved one byte (thanks @LuisMendo) by casting to `uint64` rather than selecting `)` positive entries.

# Answer
> 3 votes
# , 30 bytes

```
sum(pmax(0,diff(c(0,scan()))))

```

Try it online!

Porting of @Arnauld solution which in turn derives from @tsh great solution

# Answer
> 3 votes
# Japt `-x`, ~~7~~ 6 bytes

```
änT f¬

```

Try it

1 byte saved thanks to Oliver.

```
änT f¬     :Implicit input of integer array
ä          :Consecutive pairs
 n         :Reduced by inverse subtraction
  T        :After first prepending 0
    f      :Filter elements by
     ¬     :Square root (The square root of a negative being NaN, which is falsey)
           :Implicitly reduce by addition and output

```

# Answer
> 3 votes
# Common Lisp, ~~88~~ 87 bytes

```
(lambda(s)(let((o 0))(dolist(c s)(incf o(max 0 c))(mapl(lambda(y)(decf(car y)c))s))o))

```

## non-minified

```
(lambda (skyline)
  (let ((output 0))
    (dolist (current-skyscraper-height skyline)
      (incf output (max 0 current-skyscraper-height))
      (mapl (lambda (skyscraper)
              (decf (car skyscraper) current-skyscraper-height))
            skyline))
    output)))

```

Test it

When one tower is painted, it takes a number of brushstrokes equal to it's height. These brushstrokes translate to all the following ones, which is indicated here by subtracting the current tower's height from all other towers (and itself, but that doesn't matter). If a following tower is shorter, then it will be pushed to a negative number, and this negative number will subsequently subtracted from the towers that follow (indicating brushstrokes that could not be translated from a previous tower to the next ones). It actually just subtracts the number from *all* tower heights, including previous ones, but this doesn't matter because we don't look at the previous ones again.

# Answer
> 3 votes
# Husk, 4 bytes

```
ΣẊ>Θ

```

Try it online!

Uses the same algorithm as everybody else (see here for an explanation), it just does so with fewer bytes than anybody else :D

### Explanation

```
ΣẊ>Θ
   Θ    Prepend a 0 to the values
 Ẋ      For each pair of adjacent values (a,b)
  >     Return b-a if b>a else 0
Σ       Sum all of these values

```

`>` in Husk does a great job for this task: it does return a truthy value iff `b>a`, but this truthy value also happens to be the difference `b-a`, accomplishing two tasks in one go!

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

```
Z>Lε@γPO}O

```

Try it online or verify all test cases.

**Explanation:**

```
Z            # Get the maximum of the (implicit) input-list
 >           # Increase it by 1 (if the list only contains 0s)
  L          # Create a list in the range [1, max]
   ε         # Map each value to:
    @        #  Check if this value is >= for each value in the (implicit) input
     γ       #  Split into chunks of adjacent equal digits
      P      #  Take the product of each inner list
       O     #  Take the sum
        }O   # And after the map: take the sum (which is output implicitly)

```

# Answer
> 2 votes
# Retina 0.8.2, 21 bytes

```
\d+
$*
(1+)(?=,\1)

1

```

Try it online! Link includes test cases. Explanation:

```
\d+
$*

```

Convert to unary.

```
(1+)(?=,\1)

```

Delete all overlaps with the next tower, which don't need a new stroke.

```
1

```

Count the remaining strokes.

# Answer
> 2 votes
# Nekomata, 5 bytes

```
ç-P‼∑

```

Attempt This Online!

A port of @Arnauld's 05AB1E answer.

```
ç-P‼∑
ç           Prepend zero
 -          Minus to get the delta
  P‼        Filter by positive
    ∑       Sum

```

# Answer
> 2 votes
# Thunno 2 `S`, ~~6~~ 5 bytes

```
0ƤṢ0§

```

Attempt This Online!

Port of @Arnauld's 05AB1E answer.
*-1 thanks to @alephalpha*

#### Explanation

```
0ƤṢ0§   # Implicit input
0Ƥ      # Prepend a 0
  Ṣ     # Compute deltas
   0§   # Maximum with 0
        # S flag sums the list
        # Implicit output

```

# Answer
> 1 votes
# Perl 5, 21 bytes

```
$\+=$_>$'&&$_-$';//}{

```

TIO

How

* `-p` \+ `}{` \+ `$\` trick
* `//` matches empty string so that for next line postmatch `$'` will contain previous line
* `$\+=$_>$'&&$_-$'` to accumulate difference between current line and previous if current is greater than previous, (could also be written `$\+=$_-$' if$_>$'`, but perl doesn't parse `$\+=$_-$'if$_>$'` the same)

# Answer
> 1 votes
# C# (Visual C# Interactive Compiler) with flag `/u:System.Math`, 47 bytes

```
n=>n.Select((a,i)=>i<1?a:Max(a-n[i-1],0)).Sum()

```

Try it online!

## Old version, with flag `/u:System.Math`, 63 bytes

```
n=>n.Aggregate((0,0),(a,b)=>(a.Item1+Max(0,b-a.Item2),b)).Item1

```

I feel like this solution is more elegant than the first one. It goes through the array with a two-value tuple as a starting value, picking up values, and stores the value before it in the second part of the tuple.

Try it online!

# Answer
> 1 votes
# Pyth, 8 bytes

```
s>#0.++0

```

Yet another port of @tsh's marvellous answer. Takes the sum (`s`) of the positive values (`>#0`) of the deltas (.+) of the input with 0 prepended (`+0Q`, trailing Q inferred).

Try it online here, or verify all the test cases at once here.

## String joining method, 10 bytes

This was the solution I wrote before browsing the other answers.

```
lcj.t+d*LN

```

Test suite.

```
lcj.t+d*LNQ   Implicit: Q=eval(input()), b=<newline>, N=<quote mark>
              Trailing Q inferred
        L Q   Map each element of Q...
       * N    ... to N repeated that many times
     +b       Prepend a newline
   .t         Transpose, padding with spaces
  j           Join on newlines
 c            Split on whitespace
l             Take the length, implicit print

```

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

A port of @Arnauld's solution.

```
Tr@Select[{##,0}-{0,##},#>0&]&@@#&

```

Try it online!

# Answer
> 1 votes
# Clojure, 50 bytes

```
#((reduce(fn[[s n]i][(+(max(- i n)0)s)i])[0 0]%)0)

```

Try it online! (Why doesn't this print anything?)

```
#( ; begin anonymous function
    (reduce
        (fn [[s n] i] ; internal anonymous reducing function, destructures accumulator argument into a sum and the previous item
            [(+ (max (- i n) 0) s ; the sum part of the accumulator becomes the previous sum plus the larger of zero and the difference between the current number and the last one, which is how many new strokes need to be started at this point
            i]) ; ...and the previous item part becomes the current item
        [0 0] ; the initial value of the accumulator gives no strokes yet, and nothing for them to cover yet
        %) ; reduce over the argument to the function
    0) ; and get the sum element of the last value of the accumulator.

```

# Answer
> 1 votes
# Java (JDK), 57 bytes

```
a->{int s=0,p=0;for(int x:a)s-=(x>p?p:x)-(p=x);return s;}

```

Try it online!

Another port of tsh's Javascript answer. So make sure you've upvoted them.

Note that I used subtraction instead of addition because it allowed me to write `(p=x)` as right operand in the same statement.

# Answer
> 1 votes
# Factor \+ `math.unicode`, 24 bytes

```
[ dup 0 prefix [v-] Σ ]

```

Try it online!

## Explanation

```
         ! { 10 9 8 9 }
dup      ! { 10 9 8 9 } { 10 9 8 9 }
0        ! { 10 9 8 9 } { 10 9 8 9 } 0
prefix   ! { 10 9 8 9 } { 0 10 9 8 9 }
[v-]     ! { 10 0 0 1 }  (subtract two vectors, clamping negative numbers to 0)
Σ        ! 11

```

# Answer
> 1 votes
# Kotlin

```
fun f(test:IntArray):Int{var s=0;var p=0;test.forEach{val f=(if(it>p)p else it);p=it;s-=f-p};return s}

```

Try it yourself

# Answer
> 1 votes
# Arturo, ~~35~~ 33 bytes

```
$=>[l:0sum map&'x[max@[0x-l]l:x]]

```

Try it

# Answer
> 1 votes
# Uiua, 11 bytes

```
/+↥0-↘¯1⊂0.

```

Try it!

Port of tsh's JavaScript answer.

```
/+↥0-↘¯1⊂0.
          .  # duplicate
        ⊂0   # prepend a zero
     ↘¯1     # drop last element
    -        # subtract the two arrays
  ↥0         # change negative numbers to zero
/+           # sum

```

# Answer
> 0 votes
# MATL, ~~15~~ ~~14~~ 13 bytes

```
ts:<~"@Y'x]vs

```

Input is a column vector, using `;` as separator.

Try it online! Or verify all test cases.

### Explanation

```
t       % Implicit input: column vector. Duplicate
s       % Sum
:       % Range from 1 to that. Gives a row vector
<~      % Greater or equal? Element-wise with broadcast
"       % For each column
  @     %   Push current columnn
  Y'    %   Run-length encoding. Gives vector of values (0, 1) and vector of lengths
  x     %   Delete vector of lengths
]       % End
v       % Vertically concatenate. May give an empty array
s       % Sum. Implicit display

```

# Answer
> 0 votes
# Stax, 8 bytes

```
Φ┐Γ╟φφ.╨

```

Run and debug it

Uses the widely used approach from tsh's JavaScript solution.

---
Tags: code-golf, number, array, geometry, counting
---


title: Recognize a counting tree

text:
# Question
Title: Recognize a counting tree
Let a counting tree be a rooted tree in which every node is labeled with the number of descendants it has.

We can represent such trees as ragged lists with each node being represented by a list containing its label followed by its children. For example the following is a counting tree:

```
[5,[2,[0],[0]],[0],[0]]

```

However the brackets themselves are redundant since the labels fully capture the structure of the counting tree. So we can represent them simply as lists of integers. The example above is:

```
[5,2,0,0,0,0]

```

However not all lists of integers represent a counting tree. For example:

```
[5,1,2,0,0,0]

```

This can't work because `2` must be a child of `1`, but it needs more descendants.

## Challenge

Take as input a non-empty list of non-negative integers and determine if it represents a counting tree as described above. Output one of two distinct consistent values, one if the input is a valid counting tree the other if it is not.

This is so the goal is to minimize the size of your source code as measured in bytes.

## Test cases

## Valid

```
[5,2,0,0,0,0]
[5,2,1,0,0,0]
[5,2,1,0,1,0]
[5,3,1,0,0,0]
[6,5,4,3,2,1,0]
[0]

```

## Invalid

```
[0,0,0,0,0,0]
[5,2,1,1,0,0]
[5,2,0,1,0,0]
[5,3,1,0,1,0]
[6,2,1,0,0,0]
[5,3,1,0,0,1]
[5,2,3,0,0,0]

```

# Answer
# Nekomata \+ `-e`, 13 bytes

```
qCᵉLR↔<a*$h→L

```

Attempt This Online!

---

Here is the original answer in an old version of Nekomata:

## Nekomata \+ `-e`, 16 bytes

```
qCᵉLR↔$-ᵐP∀*$h→L

```

This is a new golfing language I'm working on. It's still in a very early stage of development.

I haven't made the first release, so the link above is to the latest commit.

This is a non-deterministic language inspired by Curry, Brachylog and other language. Functions in Nekomata may have multiple possible results, and the interpreter will choose the result via backtracking.

## Explanation

A port of @Neil's Charcoal answer.

```
qCᵉLR↔$-ᵐP∀*$h→L

                    # Take [5,2,0,0,0,0] as an example
                    # The stack is initialized with an infinite cycle of the input
q                   # Non-deterministically choose a contiguous subsequence of the input
                    # Take [2,0,0] as an example
                    # The stack is now ..., [5,2,0,0,0,0], [2,0,0]
 C                  # Uncons; pop a list and push the tail and the head
                    # The stack is now ..., [5,2,0,0,0,0], [0,0], 2
  ᵉL                # Check if the length of the tail is equal to the head
                    # The stack is still ..., [5,2,0,0,0,0], [0,0], 2 since the check passes
    R               # Range from 1 to n
                    # The stack is now ..., [5,2,0,0,0,0], [0,0], [1,2]
     ↔              # Reverse
                    # The stack is now ..., [5,2,0,0,0,0], [0,0], [2,1]
      $             # Swap
                    # The stack is now ..., [5,2,0,0,0,0], [2,1], [0,0]
       -            # Subtract
                    # The stack is now ..., [5,2,0,0,0,0], [2,1]
        ᵐP          # Check if all elements of the list are positive
                    # The stack is still ..., [5,2,0,0,0,0], [2,1] since the check passes
          ∀         # Find all possible results of a non-deterministic computation
                    # The stack is now ..., [5,2,0,0,0,0], [[3,4,3,2,1],[2,1],[],[],[],[]]
           *        # Multiply; this will fail if the two lists has different lengths
                    # The stack is now ..., [[15,20,15,10,5],[4,2],[],[],[],[]]
            $       # Swap
                    # Note that there are infinite many copies of the input on the stack
                    # The stack is now ..., [[15,20,15,10,5],[4,2],[],[],[],[]], [5,2,0,0,0,0]
             h      # Head of a list
                    # The stack is now ..., [[15,20,15,10,5],[4,2],[],[],[],[]], 5
              →     # Increment
                    # The stack is now ..., [[15,20,15,10,5],[4,2],[],[],[],[]], 6
               L    # Check if the length of the list is equal to the number
                    # The check passes, so there is a result

```

The flag `-e` set the interpreter to `CheckExistence` mode, which prints `True` if the computation has any result, and `False` otherwise. We don't care what the result really is.
> 9 votes

# Answer
# Vyxal, 17 bytes

```
ʀėṠ:Ẋ'ɖ↔ꜝnF;?ḣL≠∨

```

Try it Online!

Outputs a falsy value if it is a counting tree and a truthy if it's not.

Uses the fact that it is a counting tree iff

1. the first number is equal to the length of the rest of the list
2. for each pair of values `a`, `b` at indices `i`, `j` respectively the inclusive ranges `[i, i+a]` and `[j, j+b]` are either disjoint or one is a subset of the other

Get all inclusive ranges.

```
ʀ   # elementwise inclusive range from 0
 ė  # enumerate
  Ṡ # elementwise sum

```

Get all pairs and keep only those that don't satisfy 2.

```
:         # duplicate
 Ẋ        # cartesian product
  '     ; # filter by:
          #                        [[1,2,3],[3,4]]
   ɖ↔     #   scan by intersection [[1,2,3],[3]]
     ꜝ    #   keep truthy          [[1,2,3],[3]]
      n   #   push argument        [[1,2,3],[3]], [[1,2,3],[3,4]]
       F  #   set difference       [[3]]
          #   empty are falsy, non-emtpy are truthy

```

Check if 1. is not satisfied and combine the two.

```
?     # push input
 ḣ    # head extract
  L   # length
   ≠  # not equal
    ∨ # or

```
> 8 votes

# Answer
# Curry (PAKCS), 36 bytes

```
f[0]=1
f(a:b++c)=f b*f(a-length b:c)

```

Attempt This Online!
> 6 votes

# Answer
# Python, 63 bytes

```
f=lambda T,*t:T!=len(t)or T>0<f(T-(x:=t[0]+1),*t[x:])|f(*t[:x])

```

Attempt This Online!

Returns False for trees and True for fakes.
> 6 votes

# Answer
# Charcoal, ~~28~~ 23 bytes

```
∧⁼§θ⁰⊖Ｌθ⬤θ⬤✂θ⁺ικκ±¹¬›λμ

```

Try it online! Link is to verbose version of code. Outputs a Charcoal boolean, i.e. `-` for a counting tree, nothing if not. Explanation: Based on @AndrovT's approach, the first element must be one less than the length, then given any element `e`, the next `e` elements must all be less than the sequence from `e` down to `1`, although the code actually extracts the elements in reverse so that within their slice they must not exceed their 0-based index.

```
   θ                    Input array
  § ⁰                   First element
 ⁼                      Equals
       θ                Input array
      Ｌ                 Length
     ⊖                  Decremented
∧                       Logical And
         θ              Input array
        ⬤               All elements satisfy
            θ           Input array
           ✂            Sliced from
              ι         Current value
             ⁺          Plus
               κ        Current index
                κ       To current index
                 ±¹     In reverse
          ⬤             All elements satisfy
                     λ  Inner value
                   ¬›   Is not greater than
                      μ Inner index
                        Implicitly print

```

Example: For the input `[5,2,1,0,1,0]`, the length is `6` so the first element must be `5`, then the subsequent `5` elements must be less than `5,4,3,2,1`; the `2` elements after the `2` must be less than `2,1` and the `1` element after each `1` must be less than `1`. (Trivially the `0` elements after each `0` satisfy the property as well.)

Previous 28-byte approach:

```
Ｆθ«⊞υιＷ∧υ¬↨υ⁰≧⁻¬⊟υυ¬υ»¿∨υ⊖ⅈ⎚

```

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

```
Ｆθ«

```

Loop over the input integers.

```
⊞υι

```

Push them to the predefined empty list.

```
Ｗ∧υ¬↨υ⁰

```

While the list ends in `0`...

```
≧⁻¬⊟υυ

```

... remove the trailing `0` and decrement the remaining elements.

```
¬υ

```

Count the number of counting trees found.

```
»¿∨υ⊖ⅈ⎚

```

Check that there was exactly one counting tree and that it ended with the last element.
> 6 votes

# Answer
# Retina 0.8.2, 61 bytes

```
\d+
$*
+%`^((1)*)1(1*),(\1(?!1)(?<-2>,1*)*)(?(2)^)
$4¶$3
^¶*$

```

Try it online! Link includes test cases. Explanation: Port of @alephalpha's Curry answer.

```
\d+
$*

```

Convert to unary.

```
+%`^((1)*)1(1*),(\1(?!1)(?<-2>,1*)*)(?(2)^)
$4¶$3

```

Repeatedly split each rooted tree into its first branch and remaining branches.

```
^¶*$

```

Check that there are only twigs left.
> 3 votes

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

```
T=t=>t.shift()!=t.length|C(t)
C=$=>$>C&&C($.splice($[0]+1))|T($)

```

Try it online!

Code with comments:

```
isTree = tree =>
  tree[0] + 1 === tree.length &&
  isChildren(tree.slice(1))
isChildren = children =>
  children.length === 0 ||
    isTree(children.slice(0, children[0] + 1)) &&
    isChildren(children.slice(children[0] + 1))

```

Changing `!=` into `-` makes it 64 bytes by returning truthy vs. falsy.

~~-1~~-2 byte by l4m2.
> 2 votes

# Answer
# 05AB1E, 19 bytes

```
ŒʒćsgQ}εāR‹}˜P*ćsgQ

```

Inspired by *@Neil*'s top Charcoal, which is a port of *@AndrovT*'s Vyxal answer.

Try it online or verify all test cases.

**Explanation:**

```
Œ           # Get all sublists of the (implicit) input-list
 ʒ          # Filter it by:
  ć         #  Extract head; pop and push remainder-list and first item seperately
   s        #  Swap so the remainder-list is at the top of the stack
    g       #  Pop and push its length
     Q      #  Check if the length of the remainder-list and first item are equal
 }ε         # After the filter: map over each remaining sublist:
   ā        #  Push a list in the range [1,length] (without popping the list)
    R       #  Reverse it to [length,1]
     ‹      #  Element-wise less-than check: [a<length,b<length-1,...,y<2,z<1]
  }˜        # After the map: flatten the list of checks
    P       # Product to check if all were truthy
     *      # Multiply this 1/0 to each value in the (implicit) input-list
      ćsgQ  # Do a similar check as before within the filter on the input-list itself
            # (after which the result is output implicitly)

```

I've been unable to find anything shorter for `*ćsgQ` which works for both the `[0,0,0,0,0,0]` and `[6,2,1,0,0,0]` test cases. Checking whether the input-list is in the filtered list of sublists is an equal-bytes alternative:

```
ŒéʒćsgQ}¤IÊªεāR‹}˜P

```

Try it online or verify all test cases.

**Additional explanation:**

```
 é          # Sort the sublists by length (shortest to longest)

  ¤         # Push the last sublist after the filter (without popping the list of lists)
   IÊ       # Check that it's NOT equals to the input-list
     ª      # Append this 0 or 1 to the list of sublists
            # (`āR‹` will succeed for 0 and fail for 1)

```
> 2 votes

# Answer
# Haskell, ~~85~~ 65 bytes

*-20 bytes thanks to @Wheat Wizard*

```
h(n:w)=f(n:take n w)&&h(drop n w)
h _=1>0
f(n:w)=h w&&n==length w

```

Attempt This Online!
> 2 votes

# Answer
# tinylisp 2, 88 bytes

```
(d F(\(L)(? L(*(<(h L)(# L))(F(](h L)(t L)))(F([(h L)(t L))))1
(\(L)(*(F L)(=(h L)(#(t L

```

The submission is the anonymous function in the second line.

You can try it at Replit. Example session:

```
tl2> (d F(\(L)(? L(*(<(h L)(# L))(F(](h L)(t L)))(F([(h L)(t L))))1
F
tl2> (\(L)(*(F L)(=(h L)(#(t L
(() (L) (* (F L) (= (h L) (# (t L)))))
tl2> (d G _)
G
tl2> (G (list 5 2 1 0 1 0))
1

```

### Explanation

Our recursive helper function, `F`, analyzes a list as follows:

* Is it empty? Return `1` (truthy).
* Otherwise, split the list, conceptually, into head (first element) and tail (remaining elements).
    + Is the head greater than or equal to the list's total length? (This means the root of this subtree doesn't have enough children.) Return `0` (falsey).
    + Split the tail at the index given by the head. Recurse over each of these sublists. Return `1` if both results are `1`; otherwise return `0`.

```
(d F(\(L)(? L ... 1)))
(d F                 ) ; Define F as
    (\(L)           )  ; Lambda function taking list L
         (? L      )   ; If L is nonempty
              ...      ; (see below)
                  1    ; Else, return 1

(*(<(h L)(# L))(F(](h L)(t L)))(F([(h L)(t L))))
(*                                             ) ; Multiply these (logical AND):
  (<(h L)(# L))                                  ; 1. Head of L < length of L
               (F             )                  ; 2. Recursive call on:
                 (]          )                   ;    Take
                   (h L)                         ;    (head of L) elements
                        (t L)                    ;    from tail of L
                               (F             )  ; 3. Recursive call on:
                                 ([          )   ;    Drop
                                   (h L)         ;    (head of L) elements
                                        (t L)    ;    from tail of L

```

`F` verifies that a list represents a "forest" of zero or more counting trees concatenated. Our main function also needs to verify that we have exactly one counting tree. To do so, we first call `F` on the list, and then check whether the head is exactly equal to the length of the tail.

```
(\(L)(*(F L)(=(h L)(#(t L)))))
(\(L)                        ) ; Lambda function taking list L
     (*                     )  ; Multiply these (logical AND):
       (F L)                   ; 1. Call F on L
            (=             )   ; 2. These are equal:
              (h L)            ;    Head of L
                   (#(t L))    ;    Length of tail of L

```
> 2 votes

# Answer
# JavaScript (ES6), 75 bytes

Returns \\$0\\$ for valid, or \\$1\\$ for invalid.

```
f=([v,...a],s=v)=>v+1&&a.length!=s|f(a.slice(v=a[0]),s-++v)|f(a.slice(0,v))

```

Try it online!
> 0 votes

# Answer
# Wolfram Language (Mathematica), 147 bytes

```
(a=#;l=Length@a;And@@(IntervalMemberQ[#1,#2]||Length@IntervalIntersection[#1,#2]==0&@@@Subsets[Interval@{#,#+a[[#]]}&/@Range@l,{2}])&&a[[1]]==l-1)&

```

Try it online!

I was looking at the problem in terms of interval arithmetic, and it seems got the same algorithm as @AndrovT. Unfortunately, Mathematica has almost no shorthands for cool functions, so code looks huge (

Explained:

```
(*Total logic And*)
And @@
 (*In True case intervals must be disjointed or nested*)
 (IntervalMemberQ[#1, #2] ||
     Length@IntervalIntersection[#1, #2] == 0 & @@@
   (*All subsets length 2*)
   Subsets[
    (*All intervals i + array[i]*)
    Interval@{#, # + a[[#]]} & /@ Range@l
    , {2}])
        (*Is first element equal length of the rest*)
        && a[[1]] == l - 1 &

```
> 0 votes

---
Tags: code-golf, decision-problem, parsing, tree-traversal
---


# Question
Title: Write the shortest self-identifying program (a quine variant)
Write a program that will generate a "true" output iff the input matches the source code of the program, and which generates a "false" output iff the input does not match the source code of the program.

This problem can be described as being related to quines, as the program must be able to somehow compute its own source code in the process.

This is code golf: standard rules apply. Your program must not access any special files, such as the file of its own source code.

*Edit: If you so choose, true/false can be replaced with True/False or 1/0.*

# Example

If the source code of your program is `bhiofvewoibh46948732));:/)4`, then here is what your program must do:

## Input (Stdin)

```
bhiofvewoibh46948732));:/)4

```

## Output (Stdout)

```
true

```

## Input

```
(Anything other than your source code)

```

## Output

```
false

```

# Answer
# JavaScript : 26

```
function f(s){return s==f}

```

I don't know if a JavaScript file really qualifies as a "program".
> 37 votes

# Answer
# Haskell, 72 characters

```
main=interact$show.(==s++show s);s="main=interact$show.(==s++show s);s="

```

Note: there is no end-of-line character at the end of the script.

```
$ runhaskell Self.hs < Self.hs
True

```
> 10 votes

# Answer
# Perl, ~~Infinity~~ ~~41~~ 38 Characters

```
$_=q(print<>eq"\$_=q($_);eval"|0);eval

```

**Update:** The program no longer ends with a newline, which means it will work correctly on multi-line files. You have to enter input from STDIN without hitting enter. On Windows I was only able to do this by reading from a file.

Original solution:

```
print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(print<>==q(...

```
> 9 votes

# Answer
## GolfScript, 11 chars

```
{`".~"+=}.~

```

Without the `=`, this code would be a quine that generates its own source code as a string. The `=` makes it compare this string to its input and output `1` if they match and `0` if they don't. Note that the comparison is exact — in particular, a trailing newline at the end of the input will cause it to fail.

**Explanation:**

* `{ }` is a code block literal in GolfScript;
* `.` duplicates this code block, and `~` executes the second copy (leaving the first on the stack);
* ``` stringifies the code block, and `".~"+` appends `.~` to it;
* finally, `=` compares the resulting string with the input (which is pushed on the stack as a string by the GolfScript interpreter before the program starts) and returns `1` if they match and `0` if they don't.
> 9 votes

# Answer
# \>\<\>, 68 bytes

Fishes love eating fish poop. Now we know they can distinguish theirs from their friends'.

```
00v      0+1~$^?)0~\;n0\
  >:@@:@gi:0(?\:a=?/=?!/$1+
  0n;n*=f$=2~~/

```

You can try it online !
> 9 votes

# Answer
# Python 2, 55

```
a='a=%r;print a%%a==raw_input()';print a%a==raw_input()

```

Tested:

`a='a=%r;print a%%a==raw_input()';print a%a==raw_input()` -\> `True`

`(anything else)` -\> `False`
> 7 votes

# Answer
# JavaScript ES6, ~~16~~ 14 bytes

```
$=_=>_==`$=`+$

```

Minus two bytes thanks to Neil.

31 bytes if we must take input via prompt.

```
$=_=>prompt()==`$=${$};$()`;$()

```

38 bytes if we must output via alert.

```
$=_=>alert(prompt()==`$=${$};$()`);$()

```

This is the *proper* way to do it, as Optimizer's answer does not accept the entire source code.
> 7 votes

# Answer
# Node.js : 54

```
function f(){console.log(f+'f()'==process.argv[2])}f()

```

You test it by saving it into a file `f.js` (the exact name has no importance) and using

```
node f.js "test"

```

(which outputs false) or

```
node f.js "$(< f.js)"

```

(which outputs true)

I also made a different version based on eval :

```
eval(f="console.log('eval(f='+JSON.stringify(f)+')'==process.argv[2])")

```

It's now at 72 chars, I'll try to shorten that when I have time.
> 6 votes

# Answer
# Smalltalk (Pharo 2.0 dialect), 41 bytes

Implement this **41** chars method in String (ugly formatting for code-golf):

```
isItMe^self=thisContext method sourceCode

```

Then evaluate this in a Workspace (printIt the traditional Smalltalk way)
The input is not read from stdin, it's just a String to which we send the message (what else a program could be in Smalltalk?):

```
'isItMe^self=thisContext method sourceCode' isItMe.

```

But we are cheating, sourceCode reads some source file...
Here is a variant with **51** chars which does not:

```
isItMe
    ^ self = thisContext method decompileString

```

And test with:

```
'isItMe
    ^ self = thisContext method decompileString' isItMe

```

If a String in a Workspace is not considered a valid input, then let's see how to use some Dialog Box in **116** chars
Just evaluate this sentence:

```
(UIManager default request: 'type me') = (thisContext method decompileString withSeparatorsCompacted allButFirst: 7)

```

Since decompile format includes CR and TAB, we change that withSeparatorsCompacted.
Then we skip the first 7 chars are 'doIt ^ '

Finally a **105** chars variant using stdin, just interpret this sentence from command line, just to feel more mainstream:

```
Pharo -headless Pharo-2.0.image eval "FileStream stdin nextLine = (thisContext method decompileString withSeparatorsCompacted allButFirst: 7)"

```
> 5 votes

# Answer
# flex - 312 chars

```
Q \"
N \n
S " "
B \\
P "Q{S}{B}{Q}{N}N{S}{B}n{N}S{S}{Q}{S}{Q}{N}B{S}{B}{B}{N}P{S}{Q}{P}{Q}{N}M{S}{Q}{M}{Q}{N}%%{N}{P}{N}{M}{N} putchar('1');"
M "(.|{N})* putchar('0');"
%%
Q{S}{B}{Q}{N}N{S}{B}n{N}S{S}{Q}{S}{Q}{N}B{S}{B}{B}{N}P{S}{Q}{P}{Q}{N}M{S}{Q}{M}{Q}{N}%%{N}{P}{N}{M}{N} putchar('1');
(.|{N})* putchar('0');

```

Can probably be made shorter, but it works with multi-line input (necessary since the source code is multiple lines) and even for inputs that contain the program as a substring. It seems many of the answers so far fail on one or both of these.

Compile command: `flex id.l && gcc -lfl lex.yy.c`
> 4 votes

# Answer
## D (133 chars)

```
enum c=q{import std.stdio;import std.algorithm;void main(){auto i=readln();writeln(equal("auto c=q{"~c~"};mixin(c);",i));}};mixin(c);

```
> 3 votes

# Answer
# JavaScript (V8), 35

```
function i(){alert(prompt()==i+[])}

```

call `i()` and it will prompt for input
> 3 votes

# Answer
# GolfScript - 26

```
":@;[34]@+2*=":@;[34]@+2*=

```

Inspired from http://esolangs.org/wiki/GolfScript#Examples

Another version:

```
"[34].@@;+2*="[34].@@;+2*=

```

Too bad that `\` is both swap and escape...
> 3 votes

# Answer
# Python, 187 bytes

```
import sys;code="import sys;code=!X!;print(sys.stdin.read()==code.replace(chr(33),chr(34)).replace(!X!,code,1))";print(sys.stdin.read()==code.replace(chr(33),chr(34)).replace("X",code,1))

```

Careful not to add newline at the end. Someone with better Python-fu might be able to shorten it.
> 3 votes

# Answer
# Python 2, 47 bytes

```
_='_=%r;print _%%_==input()';print _%_==input()

```

A simple quine with the added check.
> 3 votes

# Answer
# CJam, 12 bytes

```
{s"_~"+q=}_~

```

Try it online!

### Explanation

This just uses the standard CJam quine framework.

```
{s"_~"+q=}    e# Push this block (function literal).
          _~  e# Copy and run it.

```

What the block does:

```
 s            e# Stringify the top element (this block itself).
  "_~"+       e# Append "_~". Now the source code is on the stack.
       q      e# Read the input.
        =     e# Check if it equals the source code.

```
> 3 votes

# Answer
## Tcl, 111 chars

```
set c {set c {$c};puts [expr {[read stdin] eq [subst -noc \$c]}]};puts [expr {[read stdin] eq [subst -noc $c]}]

```
> 2 votes

# Answer
## Perl, 52 char

```
$_='$/=$\;$_="\$_=\47$_\47;eval";print<>eq$_|0';eval

```
> 2 votes

# Answer
# Husk, 11 bytes

```
=hS+s"=hS+s

```

Try it online!

### Explanation

The explanation uses `¨` to delimit strings (to avoid unreadable escaping):

```
     "=hS+s  -- string literal: ¨=hS+s¨
  S+         -- join itself with
    s        -- | itself "showed": ¨"=hS+s"¨
             -- : ¨=hS+s"=hS+s"¨
 h           -- init: ¨=hS+s"=hS+s¨
=            -- is the input equal?

```

By removing the function `=` you can verify that it will indeed only match the source itself.
> 2 votes

# Answer
# Python 2, 40 bytes

```
s="print's=%r;exec s'%s==input()";exec s

```

Try it online!
> 2 votes

# Answer
# \>\<\>, 24 bytes

```
'1rd3*i={*}50l3-?.~i)*n;

```

Try it online!

Wrapping string literal followed by checking whether the input is identical to the stack, with a final check that there is no more input.
> 2 votes

# Answer
# Jelly, 10 bytes

```
“Ṿ;$⁼”Ṿ;$⁼

```

Try it online!

```
“Ṿ;$⁼”Ṿ;$⁼
“Ṿ;$⁼”      String literal: 'Ṿ;$⁼'
        $   Next two links act on the string literal
      Ṿ     Uneval: '“Ṿ;$⁼”'
       ;    Append string: '“Ṿ;$⁼”Ṿ;$⁼' (source code)
         ⁼  Is the string above equal to the input?

```
> 2 votes

# Answer
# Zsh, 33 bytes

```
f () {
	[ "`type -f f`" = $1 ]
}

```

Try it online!

The extra spaces, tab, and newlines are required. `type -f f` does not print the original source, but the function formatted in a particular way, with indentation and a trailing newline.
> 2 votes

# Answer
# , 54 bytes

```
f=function(s)s==paste0("f=function(s)s==", body(f)[3])

```

Try it online!

`body` gets the body of the function (splitting it a bit, so that `body(f)[3]` is everything from `paste0` onwards). Interestingly, `body` reformats the code, adding spaces after commas, etc. This is thus a rare case of an R golf answer with a space after a comma.

This works because `body(f)` is an object of type `language`, and there exists an `as.character` method for this type. On the other hand, `f` and `args(f)` are of type `closure`, and cannot be converted to character type as far as I can tell. Please don't ask me what the language type is for…
> 2 votes

# Answer
# (version-dependent), 46 bytes

```
f=function(x)x==paste0('f=',capture.output(f))

```

`capture.output` \- as the function name suggests - retrieves the text string that results from entering the function name `f` directly to , which should output the body of the function. We manually prepend this with `f=` so that it exactly\* matches the program code, and check whether the function argument `x` is the same as this.
\*See below

There are a couple of caveats, though, that depend on the  version used:

1. Early versions of  (like my own version 3.2.1) return the originally-defined function body as-is when the function name is entered to . However, later versions add additional formatting, like inserting spaces and newlines, which breaks this code: this unfortunately includes the installation (3.5.2) on 'Try it online'. Later still, much newer  versions (I tested 4.0.3) return to the as-is output formatting and everything is Ok again... except...
2. The most recent versions of  compile functions at the first run, and thereafter append a 'byte code' specific for the compiled function to the outputted function body. This means that `capture.output` returns two strings, beginning at the second time the function is run. Luckily, the function body is still the first one (the byte code is the second one), so the result of supplying the program code as input is `TRUE FALSE`, which evaluates to 'truthy' in  and so counts as a 'true' output for this challenge.

Special thanks to Robin Ryder for helping to uncover the version-dependence of 's function outputting.
> 2 votes

# Answer
# Vyxal, 12 bytes

```
`:q$+=`:q$+=

```

Try it Online!

I finished making this, and then realized that it is almost identical to the Vyxal quine that @Lyxal wrote, but with the addition of `=` to check if the input is equal.

Explanation:

```
              # Implicit input
`:q$+=`       # Push the string ':q$+='
       :      # Duplicate the string
        q     # Quotify; put backticks around the topmost string
         $    # Swap the top two values on the stack
          +   # Concatenate the two strings
           =  # Check if the input is equal to the string
              # Implicit output

```
> 2 votes

# Answer
## C - 186 176 characters

One liner:

```
 *a="*a=%c%s%c,b[999],c[999];main(){sprintf(b,a,34,a,34);gets(c);putchar(strcmp(b,c)?'0':'1');}",b[999],c[999];main(){sprintf(b,a,34,a,34);gets(c);putchar(strcmp(b,c)?'0':'1');}

```

With whitespace (note that this breaks the program):

```
*a="*a=%c%s%c,b[999],c[999];main(){sprintf(b,a,34,a,34);gets(c);putchar(strcmp(b,c)?'0':'1');}",b[999],c[999];
main() {
  sprintf(b,a,34,a,34);
  gets(c);
  putchar(strcmp(b,c)?'0':'1');
}

```
> 1 votes

# Answer
#PowerShell, 28 bytes

Very similar to this JavaScript answer, uses function provider.

```
filter f{"$Function:f"-eq$_}

```

#Example

```
PS > '"$Function:f"-eq$_' | f
True

PS > 'xxx' | f
False

```
> 1 votes

# Answer
# Stax, 26 bytes

```
"34bLN26)s:f="34bLN26)s:f=

```

Run and debug it
> 1 votes

# Answer
## JavaScript ES6, 14 bytes

Like the other javascript answer but includes it's entire source code and not just the function

```
a=q=>'a='+a==q

```

Example usage:

```
a("q=>'a='+a==q") // returns false
a("a=q=>'a='+a==q") // returns true

```
> 1 votes

# Answer
# 05AB1E, 15 bytes

```
0"D34çýQ"D34çýQ

```

Modifies the default `0"D34çý"D34çý` by adding `Q` (check for equality with the implicit input)

Try it online.

**Explanation:**

```
0                # Push 0 to the stack
                 #  STACK: [0]
 "D34çýQ"        # Push the string 'D34çýQ' to the stack
                 #  STACK: [0, 'D34çýIå']
         D       # Duplicate this string
                 #  STACK: [0, 'D34çýIå', 'D34çýIå']
          34ç    # Push '"' to the stack
                 #  STACK: [0, 'D34çýIå', 'D34çýIå', '"']
             ý   # Join the stack by this '"' delimiter
                 #  STACK: ['0"D34çýIå"D34çýIå']
              Q  # Check if it's equal to the (implicit) input
                 # (and output the top of the stack implicitly as result)

```

---

Cool **15 bytes** alternative provided by *@Grimy*:

```
187745012D27BJQ

```

Try it online.

**Explanation:**

```
187745012        # Push integer 187745012
                 #  STACK: [187745012]
         D       # Duplicate it
                 #  STACK: [187745012, 187745012]
          27     # Push integer 27
                 #  STACK: [187745012, 187745012, 27]
            B    # Convert 187745012 to base-27
                 #  STACK: [187745012, "D27BJQ"]
             J   # Join the values on the stack together
                 #  STACK: ["187745012D27BJQ"]
              Q  # Check if it's equal to the (implicit) input
                 # (and output the top of the stack implicitly as result)

```
> 1 votes

# Answer
# q, 8 bytes

```
{x~.z.s}

```

Return boolean on input matching the self-referential .z.s
> 1 votes

# Answer
# Runic, 11 bytes

```
"3X4+kSqi=@

```

Try it online!

TIO got updated and there's no longer an issue reading input (and no longer requires a trailing whitespace).

### Explanation

```
>                 Implicit entry
 "                Begin reading as string
  3X4+kSqi=@      Pushed to the stack as a string, loop around
 "                End reading as string
  3X4+            Push 3*10 and 4 to the stack, add them together
      k           Convert to character (")
       S          Swap the top two items on the stack
        q         Concatenate. This leaves only "3X4+kSqi=@ on the stack
         i        Read input
          =       Compare using .Equals, push 1 if equal, else 0
           @      Print and terminate

```

## JoKing's solution:

```
"'<~qi=@|

```

### Explanation

```
  <              Entry
 '               Read character (loop around)
"                Push "
         |       Mirror
"                Begin reading string (loop around)
 '<~ri=@|        Push the string '<~qi=@| (loop around)
"                End reading string
 '<~             Push the character < and then discard it
    q            Concatenate, stack contains only "'<~qi=@|
      i          Read input
       =         Compare
        @        Print and terminate

```
> 1 votes

# Answer
# Keg, ~~36~~ ~~28~~ 26 bytes

```
`:&\`ⁿ^\`ⁿ&⅀=`:&\`ⁿ^\`ⁿ&⅀=

```

Try it online!

Same concept as before, but shorter.

## Answer History

```
`:&\`ⁿ⅍^\`ⁿ⅍++&+¿=`:&\`ⁿ⅍^\`ⁿ⅍++&+¿=

```

Try it online!

Who knew generating a program that knows itself would be so unreadable!

## Explained

The very first step here is to generate the string that will be checked against. At this point, we don't particularly know what the checking part will look like, but we do know that there will be a string that looks like so:

```
`\`ⁿ⅍^\`ⁿ⅍++`

```

Which would consequently be followed by:

```
 \`ⁿ⅍^\`ⁿ⅍++

```

This creates a string which contains itself quoted... Something needed for when input is taken, as the quotes are going to be present.

From here, string equality is quite easy, coming in at a trivial 2 bytes:

```
¿=

```

Incorporating this into the string gives:

```
`\`ⁿ⅍^\`ⁿ⅍++¿=`\`ⁿ⅍^\`ⁿ⅍++¿=

```

At this stage, one might think the quine is complete... It has the string part and it has the equality part... What else could be needed? Well. Let me tell you we ain't done yet.

Y'see, we have a quoted string on the stack, but we don't have it's unquoted equivalent present, meaning we need to account for that. The register works well here:

```
`:&\`ⁿ⅍^\`ⁿ⅍++&+¿=`:&\`ⁿ⅍^\`ⁿ⅍++&+¿=

```

And there you have it: a self identifying program written completely on a phone keyboard.
> 1 votes

# Answer
# Perl 6, 33 bytes

```
<dd "<$_>~~.EVAL"eq slurp>~~.EVAL

```

Try it online!

Outputs either `Bool::True` or `Bool::False` to STDERR. This is the basic quine format, with an added check against input (`eq slurp`).
> 1 votes

# Answer
# Japt, <sup>~~22~~ ~~16~~</sup> 14 bytes

```
"iQ ²¶U"iQ ²¶U

```

Try it online!

## Explanation

```
"iQ ²¶U"iQ ²¶U
"iQ ²¶U"        // Take this string.        iQ ²¶U
        iQ      // Insert a quote.          "iQ ²¶U
           ²    // Double.                  "iQ ²¶U"iQ ²¶U
            ¶U  // Check if equal to input.

```
> 1 votes

# Answer
# Ruby `-0n`, <sup>~~32~~</sup> 27 bytes

*Saved 5 bytes thanks to a comment by @Sisyphus on another answer.*

```
eval s="p$_=='eval s=%p'%s"

```

Try it online!

Disclosure: very similar to my answer on a duplicate question.

The `-0` flag sets the null byte as the input record separator. Without `-0`, each line of the input would be read (and tested for equality with the code) separately.
> 1 votes

# Answer
# C (gcc), 132 bytes

```
#define Q(X)main(c,v)int**v;{return!strcmp(#X"\nQ("#X")",v[1]);}
Q(#define Q(X)main(c,v)int**v;{return!strcmp(#X"\nQ("#X")",v[1]);})

```

Try it online!

It turns out using a macro works out better than using `(a)sprintf`, even with `%c%s%1$c`.

I'm not sure if this type of input (a single multiline command-line argument) and output (return value of 1 for true or 0 for false) are allowed.

If they aren't:

---

# C (gcc), 152 bytes

```
x,y[99];main(z){asprintf(&x,z="x,y[99];main(z){asprintf(&x,z=%c%s%1$c,34,z);gets(y);putchar(48+!strcmp(x,y));}",34,z);gets(y);putchar(48+!strcmp(x,y));}

```

Try it online!

Assumes an ASCII environment. Reads from stdin, writes 1 or 0 to stdout. Abuses ints as pointers, leaks memory, and uses the dreaded `gets` :)

---

In case you're curious, here's the opposite combinations of quine and IO methods:

### C (gcc), 136 bytes

```
x;main(y,v)int**v;{asprintf(&x,y="x;main(y,v)int**v;{asprintf(&x,y=%c%s%1$c,34,y);return!strcmp(x,v[1]);}",34,y);return!strcmp(x,v[1]);}

```

Try it online!

### C (gcc), 158 bytes

```
#define Q(X)v[40];main(){read(0,v,159);putchar(48+!strcmp(#X"\nQ("#X")",v));}
Q(#define Q(X)v[40];main(){read(0,v,159);putchar(48+!strcmp(#X"\nQ("#X")",v));})

```

Try it online!
> 1 votes

# Answer
# Julia 1.0, 48 bytes

```
(a=:(show(ARGS[] == "(a=:($(a)))|>eval")))|>eval

```

Try it online!
> 1 votes

# Answer
# Vyxal, 38 bits<sup>v2</sup>, 4.75 bytes

```
`I=`I=

```

Try it Online!

## Explained

```
`I=`I=
     =  # Does the input equal
`I=`    # The string "I="
    I   # With itself wrapped in backticks prepended

```

Created with the help of Luminespire.
> 1 votes

# Answer
# Uiua, 38 bytes

```
≅&sc⊂∶!(⊂⊂↷.+1@!)."≅&sc⊂:!(⊂⊂↷.+1@!)."

```

## Explained

```
≅&sc⊂∶!(⊂⊂↷.+1@!)."≅&sc⊂:!(⊂⊂↷.+1@!)."
                  "≅&sc⊂:!(⊂⊂↷.+1@!)."  # The string "≅&sc⊂:!(⊂⊂↷.+1@!)."
                 .                      # Duplicate it
      !(        )                       # Call the following function on the top copy:
           .+1@!                        #   Push two "
         ⊂↷                             #   Append the first
        ⊂                               #   Prepend the second
# The top of the stack is now a quotified string
    ⊂∶                                  # Prepend the original string without quotes
≅&sc                                    # Does that equal the input?

```

Created with the help of Luminespire.
> 1 votes

# Answer
# , 19 bytes

```
ñOÑ~"qpxØ¥^¨©î±¥$

```

Try it online!

Prints **1** or **0**. Here is a hexdump:

```
00000000: f14f d11b 7e22 7170 78d8 a55e a881 a9ee  .O..~"qpx..^....
00000010: b1a5 24                                  ..$

```
> 0 votes

# Answer
# Java 8, 288 bytes (Full Program with STDIN)

```
interface M{static void main(String[]a){String s="interface M{static void main(String[]a){String s=%c%s%1$c;System.out.print(s.format(s,34,s).equals(new java.util.Scanner(System.in).nextLine()));}}";System.out.print(s.format(s,34,s).equals(new java.util.Scanner(System.in).nextLine()));}}

```

Try it online.

# Java 8, 210 bytes (Full Program with Console Arguments)

```
interface M{static void main(String[]a){String s="interface M{static void main(String[]a){String s=%c%s%1$c;System.out.print(s.format(s,34,s).equals(a[0]));}}";System.out.print(s.format(s,34,s).equals(a[0]));}}

```

Try it online.

# Java 8, 108 bytes (Function)

```
i->{String s="i->{String s=%c%s%1$c;return s.format(s,34,s).equals(i);}";return s.format(s,34,s).equals(i);}

```

Try it online.

**Explanation:**

-part:

* The `String s` contains the unformatted source code.
* `%s` is used to input this String into itself with the `s.format(...)`.
* `%c`, `%1$c` and the `34` are used to format the double-quotes.
* `s.format(s,34,s)` puts it all together

Challenge-part:

* `.equals(...)` checks if this formatted source code equals the input.
    + `java.util.Scanner(System.in).nextLine()` is used as this input for STDIN
    + `a[0]` is used as this input for Console arguments
    + `i` is used as this input for the lambda function
> 0 votes

# Answer
# Pascal (FPC), ~~167~~ 157 bytes

```
const b=#39';var s:string;begin read(s);write(s=a+b+#39#59#97#61#39+a+b)end.';a='const b=#39';var s:string;begin read(s);write(s=a+b+#39#59#97#61#39+a+b)end.

```

Try it online!

While substring can be easily extracted, like in my regular quine, unfortunately, they cannot be concatenated because FPC thinks it is an array in these circumstances. In `a` and `b` are characters before and after constant definitions. `#39#59#97#61#39` is a replacement for `';a='` as this is not represented in the constants. `#39` represents `'` and is at the start of `b`, glued together to the rest of `b`, to shorten the comparison expression as much as possible.
> 0 votes

# Answer
# TeX, 55 bytes

The file has to be saved as `a.tex` and should be run using `pdftex a.tex`. The script doesn't terminate after returning 1 or 0, if that should be necessary append it by `\end` (+4 bytes). If it should work for arbitrary file names replace `\openin0a` with `\openin0\jobname` (+7 bytes).

```
\openin0=a\read0to\0\read1to~\message{\ifx\0~1\else0\fi}

```
> 0 votes

# Answer
# Python 3.8 (pre-release), 42 bytes

```
exec(s:="print('exec(s:=%r)'%s==input())")

```

Try it online!
> 0 votes

# Answer
# Java, 318 bytes

```
interface Q{static void main(String[]a){char q=34;String s="interface Q{static void main(String[]a){char q=34;String s=%c%s%c;System.out.print(new java.util.Scanner(System.in).nextLine().equals(String.format(s,q,s,q)));}}";System.out.print(new java.util.Scanner(System.in).nextLine().equals(String.format(s,q,s,q)));}}

```

Try it online!
> 0 votes

# Answer
# Japt, 11 bytes

```
¶BîQi"¶BîQi

```

Try it

```
¶BîQi"¶BîQi     :Implicit input of string
¶               :Is strictly equal to
 B              :  11
  î             :  Mold to length B
   Q            :    Quotation mark
    i           :    Prepend
     "¶BîQi     :      Literal string

```
> 0 votes

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


title: Print the missing primes

text:
# Question
Title: Print the missing primes
### The Task

Write a program or function that, when passed a numerical input `x`, prints or returns the primes beneath the square root of `x`1 that are not factors of `x`.

### Examples

Let `f(x)` be the function called:

```
>>> f(4)
[]

>>> f(5)
[2]

>>> f(20)
[3]

>>> f(60)
[7]

>>> f(100)
[3, 7]

>>> f(10000)
[3, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

```

### Bonus Rules

* You may use any builtins that your language provides.
* Your program must support an `x` input as high as the upper bound defined by your language.

---

1 Using the square root as only primes below the square root can actually be involved within the factors of `x`. Without making this restriction, larger numbers would have a lot of excess printed numbers.

# Answer
# Jelly, 6 bytes in Jelly's codepage

```
½ÆRḟÆf

```

Try it online!

Explanation:

```
½ÆRḟÆf
 ÆR    All primes less than or equal to
½      the square root of the input
   ḟ   but with the following removed:
    Æf All prime factors of {the input, by default}

```
> 7 votes

# Answer
# MATL, ~~10~~ 9 bytes

```
X^ZqGYfX-

```

Try it online!

### Explanation

```
X^    % Implicit input. Square root
Zq    % Array if primes up to that
G     % Push input again
Yf    % Array of prime factors
X-    % Set difference. Implicit display

```
> 5 votes

# Answer
# **MATLAB, ~~57~~ 54 bytes**

```
function h(p);a=primes(p^.5);a(~ismember(a,factor(p)))

```

Pretty straightforward, gets an array of primes up to sqrt(p) then removes any that are also factors of p. Prints the output of the last line by default because the semicolon is left off.
> 5 votes

# Answer
# Pyth, 10 bytes

```
fP_T-S@Q2P

```

A program that takes input of a number and prints a list.

Test suite

**How it works**

```
fP_T-S@Q2P   Program. Input: Q
fP_T-S@Q2PQ  Implicit input fill
f            Filter
     S@Q2    the 1-indexed range up to floor(sqrt(Q))
    -    PQ  with the prime factors of Q removed
 P_T         by primality
             Implicitly print

```
> 4 votes

# Answer
# Python 3, ~~67~~ 62 bytes

```
f=lambda n,k=1,m=1:k*k<n and(m%k*n%k>0)*[k]+f(n,k+1,m*k*k)or[]

```

Try it online!
> 4 votes

# Answer
# 05AB1E, 8 bytes

```
tLDpÏ¹fK

```

Try it online!

**Explanation**

```
tL        # range [1 ... sqrt(input)]
  DpÏ     # keep only primes
     ¹fK  # remove factors of input

```
> 4 votes

# Answer
# PHP, 76 bytes

```
for($n=1;++$n*$n<$x=$argv[1];){for($i=$n;$n%--$i;);if($i<2&&$x%$n)echo$n,_;}

```

uses my is\_prime solution golfed for $n\>1

takes input from command line argument. Run with `-r`.
> 3 votes

# Answer
# JavaScript (ES6), ~~79~~ 76 bytes

```
f=(q,n=2,x=n)=>n*n<q?[...--x<2&&q%n?[n]:[],...x>1&&n%x?f(q,n,x):f(q,n+1)]:[]

```

Based on my recursive primality test function. I feel like there should be a few ways to simplify this, but I can't figure out how...

### Test snippet

```
f=(q,n=2,x=n)=>n*n<q?[...--x<2&&q%n?[n]:[],...x>1&&n%x?f(q,n,x):f(q,n+1)]:[]
```

```
<input type="number" step=1 min=4 value=4 oninput="O.innerHTML='['+f(this.value)+']'"><br>
<pre id=O>[]</pre>
```
> 2 votes

# Answer
# Mathematica, 46 bytes

```
Select[Prime@Range@PrimePi@Sqrt[a=#],!#∣a&]&

```

Anonymous function. Takes a number as input and returns a list of numbers as output. The Unicode character is U+2223 DIVIDES for `\[Divides]`.
> 2 votes

# Answer
# Ruby, 55 bytes

```
require'prime'
->x{Prime.to_a(x**0.5).select{|n|x%n>0}}

```

A rather lazy answer using the builtin prime enumerator.
> 2 votes

# Answer
# Wonder, 14 bytes

```
@(_> > ^#0.5)P

```

Usage:

```
(@(_> > ^#0.5)P)10

```

Takes items from an infinite list of primes while the item is less than the square root of the argument.
> 2 votes

# Answer
## Pyke, 10 bytes

```
,BS#_P)QP-

```

Try it here!

```
,B         -    int(sqrt(input))
  S        -   range(1, ^+1)
   #_P)    -  filter(^, is_prime)
         - - ^.remove(V)
       QP  -  factors(input)

```
> 2 votes

# Answer
## PowerShell v2+, 71 bytes

```
param($n)1..[math]::Sqrt($n)|?{$n%$_-and'1'*$_-match'^(?!(..+)\1+$)..'}

```

Iterative solution. Takes input `$n` and creates a range from `1` to the `Sqrt($n)` (note that the range operator will implicitly cast the upper end to an `[int]` which will do Banker's Rounding by default). Then uses `|?{...}` (the `Where-Object` operator, which acts like a filter) to pull out those numbers where `$n%$_` is non-zero (i.e., any remainder to the modulo means it's not a factor, and any non-zero is truthy) `-and` the usual regex prime test is `$true`. Those are left on the pipeline, and output is implicit.

### Examples

(with some extra formatting to pretty up the output)

```
PS C:\Tools\Scripts\golfing> 5,20,60,100,10000|%{"f($_)";(.\print-the-missing-primes.ps1 $_)-join', ';""}
f(5)
2

f(20)
3

f(60)
7

f(100)
3, 7

f(10000)
3, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97

```

---

NB - This will fail on earlier versions if the input is bigger than around `2500000000`, because the `..` range operator can only support up to 50,000 items. But, since that is bigger than the default `[int]` datatype's max value, `2147483647`, I'm presuming that to be OK. On my machine, PSv4 Win8.1, however, I can go higher, but I'm not able to find documentation explaining the difference.
> 2 votes

# Answer
# Octave, 44 bytes

This answer is inspired by MattWH's MATLAB answer, but I've golfed it using some Octave-specific features.

```
@(x)(y=primes(x^.5))(~ismember(y,factor(x)))

```

This is an anonymous function that takes the input `x`. Octave has inline variable assignment and indexing allowing `y` to first be created in the function (not possible in MATLAB), then used as part of the logical mask created by `ismember` (again, not possible to do it this way in MATLAB).
> 2 votes

# Answer
# Perl 6, 37 bytes

```
{grep {$^a.is-prime&$_%$a},2.. .sqrt}

```

## Expanded:

```
{   # bare block lambda with implicit parameter ｢$_｣

  grep
  {
    $^a.is-prime  # check if it is prime
    &             # and junction
    $_ % $a       # check if the input is not evenly divisible by it
  },
  2.. .sqrt          # Range of values up-to and including squareroot
}

```
> 1 votes

# Answer
# TSQL, 130 bytes

```
DECLARE @v int=10000

,@ INT=2SELECT 2p INTO #
g:INSERT # SELECT @ FROM # HAVING isnull(min(@%p),1)>0SET @+=1IF @*@<@v GOTO g
SELECT*FROM # WHERE @v%p>0

```

This will only execute once, then you need to drop the temp table to execute again in the same editor

```
DROP TABLE #

```

I made a version to test it, it is a bit longer because the online permissions for creating tables is unavailable. For the same reason it doesn't need the drop table though.

**Try it online**
> 1 votes

# Answer
# R, ~~58~~ 63 bytes

```
for(i in 2:sqrt(x<-scan()))if(x%%i&numbers::isPrime(i))print(i)

```

Loops over all values from 2 to `sqrt(x)` and checks if they are prime with the `numbers` package. `x%%i` calculates `x mod i` which is `0 -> False` if `i` is a divisor of `x` and `>0 -> True` if `i` is not.

+5 bytes because the `numbers::Primes(n)` function doesn't allow decimals, while `2:sqrt(x)` does work, added prime check to `if` statement.
> 1 votes

# Answer
## Haskell, ~~55~~ 54 bytes

```
f x=[y|y<-[2..x],y*y<x,[z|z<-[1..y],gcd(z*x)y>1]==[y]]

```

Mostly straightforward nested list comprehensions. GCD performs two roles, testing whether the numbers below y are factors of y and also testing whether y is a factor of x.

Spaced out a little:

```
f x = [ y|y<-[2..x],     y*y<x,     [z|z<-[1..y], gcd (z*x) y > 1] == [y] ]

```
> 1 votes

# Answer
## Retina, ~~69~~ 66 bytes

```
.+
$*
(11\1|^1)+
$#1$*1:$&
M!&`(?!(11+)\1+:)(1+):(?!\2+$)
M%`1
^0

```

Prints the primes on separate lines, from largest to smallest.

Try it online! (Takes about 10 seconds due to the last two test cases. The header and footer enable a linefeed-separate test suite, and convert the output to comma-separation for readability.)

### Explanation

```
.+
$*

```

Convert the input to unary.

```
(11\1|^1)+
$#1$*1:$&

```

This prepends the square root of the input, separated by `:`. The square root is computed based on the fact that the square of `n` is also the sum of the first `n` odd integers. We can match consecutive odd integers with the forward reference `(11\1|^1)`. In the process the group will be used exactly `n` times, where `n` is the largest number whose square fits into the input.

We insert a unary representation of this number with `$#1$*1`, followed by a colon and the match itself.

```
M!&`(?!(11+)\1+:)(1+):(?!\2+$)

```

This matches all the missing primes that fit into the square root. The prime detection is based on the standard prime checking regex, and then we simply make sure that the prime we've just captured does not divide the input with the second lookahead. By using the `&` option, we get overlapping matches to ensure that we get all primes.

```
M%`1

```

This converts each line (i.e. each missing prime) back to decimal by matching the number of `1`s. The only issue is that this inserts a zero if no missing primes were found at all.

```
^0

```

So this stage removes that zero if it was added.
> 1 votes

# Answer
# Vyxal, 6 bytes

```
√~æ?KF

```

Try it Online!

It's nice to have a massive toolbox again

## Explained

```
√~æ?KF
√~æ     # Keep only primes from the range [1, sqrt(input)]
     F  # With items from
   ?K   # Factors of the input
     F  # Removed

```

Created with the help of Luminespire.
> 1 votes

# Answer
# Uiua, 46 bytes

```
▽∵(=2/+⌕0◿+1⇡.).▽¬≡/+⊞=↷.⊃(+1⇡⌊√)(▽=0◿↷.+1⇡.).

```

Try it Online

## Explained

```
▽∵(=2/+⌕0◿+1⇡.).▽¬≡/+⊞=↷.⊃(+1⇡⌊√)(▽=0◿↷.+1⇡.).
                         ⊃(     )(          ).  # To the input, apply:
                           +1⇡⌊√                #   Range [1, sqrt(input)]
                                  ▽=0◿↷.+1⇡.    #   All factors of the input by:
                                        +1⇡.    #     Creating a range [1, input]
                                      ↷.        #     Rolling a copy to the bottom of the stack
                                   =0◿          #     Pushing whether each number in that range divides the input
                                  ▽             #     And keeping only numbers that do
                ▽¬≡/+⊞=↷.                       #   Filter out divisors from the sqrt range by:
                     ⊞=                         #     Table via equality
                  ≡/+                           #     Sum of row
                 ¬                              #     != 0
# Essentially, keep only numbers where the number of occurrences in the divisor list is 0
 ∵(=2/+⌕0◿+1⇡.).                                # Push a mask of whether each number is prime (using the method in my "is a number prime" Uiua answer)

```

Created with the help of Luminespire.
> 1 votes

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


title: Order by Earliest Lower Digit

text:
# Question
Title: Order by Earliest Lower Digit
Given two strings of digits, determine which string, if any, has the earliest digit which is lower than the other string's digit at the same index.

Do note that this differs from alphabetization, as shown in the following examples:

### Examples

Given inputs `12345000` and `1233999999`, the second string would have the earliest lower digit.

```
12345000
1233999999
^          same value
 ^         same value
  ^        same value
   ^       second is lower
    ^^^^^^ irrelevant

```

Given strings `99` and `998`, neither has the earliest lowest digit, since `99` equals `99`, and the `8` has no digit to compare against.

```
99
998
^   same value
 ^  same value
  ^ irrelevant

```

### Additional specification

* Input/output can be taken/given in any reasonable format.
* You can output any three consistent values to represent choosing the first input, the second input, or neither. (similar to )
* Alternatively, you may use the standard output method of three-way comparison of your language of choice (if one exists)
* You may assume that there will be no leading 0s in input.
* This is , so shortest code in bytes wins.

### Test cases

Output is in the form `<` for first input, `>` for second input, and `=` for equal.

```
 999   999 =
 115   116 <
 116   115 >
 870   789 >
  33  3333 =
3333    33 =
  20  2100 <
  19  1200 >
2100    20 >
1200    19 <
1234  1234 =
4321  5432 <
5678  5432 >
  99   998 =
12345000  1233999999 >

```

# Answer
> 9 votes
# Python 2, 28 bytes

```
lambda*l:cmp(*zip(*zip(*l)))

```

Try it online!

Uses `zip`'s truncating the to the shorter list. Test harness from @SuperStormer. Python 2 is needed for `cmp`.

# Answer
> 9 votes
# Husk, 5 bytes

```
±ḟIz-

```

Try it online!

Input as lists of digits, output as `-1` (first wins), `0` (neither wins) or `1` second wins.
Would be 1-byte shorter to output negative, zero or positive, but Husk doesn't have a 3-way comparison operator so it seems this is ruled-out...

```
   z   # zip digits from each pair of inputs together
    -  # by subtraction,
 ḟ     # get the first element that is
  I    # itself truthy (non-zero),
±      # output the sign of that (-1 or 1) or zero if it's empty

```

# Answer
> 6 votes
# Factor, 17 bytes

```
[ zip unzip <=> ]

```

Try it online!

Outputs `+lt+` for first input, `+gt+` for second input, or `+eq+` for neither.

* `zip unzip` Truncate the longer input to the same length as the shorter one.
* `<=>` Compare.

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

Expects two arrays of characters as `(a)(b)`. Returns `-2`, `-1` or `0` for `<`, `>` or `=` respectively.

```
a=>b=>-a.some((c,i)=>d=c-b[i])^d<0

```

Try it online!

Or **31 bytes** if we output negative / zero / positive:

```
a=>b=>a.some((c,i)=>d=c-b[i])*d

```

Try it online!

# Answer
> 5 votes
# , 44 bytes

```
\(x,n=nchar(x))sign(diff(x%/%10^(n-min(n))))

```

Attempt This Online!

# Answer
> 4 votes
# Python 2, 37 bytes

```
lambda s,t:cmp(s[:len(t)],t[:len(s)])

```

Attempt This Online!

# Answer
> 4 votes
# Nibbles, 4.5 bytes (9 nibbles)

```
`$/|!$_-*

```

Attempt This Online!

Input as lists of digits, output as `1` (first wins), `0` (neither wins) or `-1` second wins. Would be 1-byte (2 nibbles) shorter to output negative, zero or positive.

```
`$/|!$_-*       # full program
`$/|!$_-*$$$    # with implicit args (I think*):
    !           # zip together
     $_         # arg1 & arg2
       -        # by subtraction,
   |            # filter the resulting list
        *$$     # by each element multiplied by itself
                # (zero and negatives are falsy in nibbles),
  /             # now fold over this list
           $    # returning the left-hand element each time
                # (so returning the first element),
`$              # and return the sign of this
                # (or zero if empty)

```

\*I'm not quite sure why `$$$` is chosen for implicit args (here for the documentation), but happily it is and it works here...

# Answer
> 4 votes
# C (clang), ~~64~~ ~~63~~ 62 bytes

```
c;f(*a,*b){for(c=1;(*a&&*b)&c;c+=*a++>*b++)c-=*a<*b;return c;}

```

Try it online!

*Saved a bytes thanks to ceilingcat!!!*

Inputs the digits as two wide-character strings.
Returns \\$0\\$ for `<`, \\$2\\$ for `>`, or \\$1\\$ for `=`.

# Answer
> 4 votes
# Charcoal, 24 bytes

```
≔✂θ⁰Ｌη¹θ≔✂η⁰Ｌθ¹ηＩ⁻›θη›ηθ

```

Try it online! Link is to verbose version of code. Explanation: Charcoal doesn't have any relevant builtins, so it struggles even to port @SuperStormer's Python 2 answer.

```
≔✂θ⁰Ｌη¹θ

```

Truncate the first string to the length of the second.

```
≔✂η⁰Ｌθ¹η

```

Truncate the second string of the length of the first.

```
Ｉ⁻›θη›ηθ

```

Compare the strings.

# Answer
> 4 votes
# Pip, 20 17 12 bytes

*-5 bytes by Dlosc*

Returns -1 for first element, 1 for second and nothing if equal.

```
SG@FI_-BMZab

```

Attempt This Online!

```
SG@FI_-BMZab
        MZab  # For each pair of digits in a, b
     _-B      # Return difference of digits
SG            # Push sign of
  @FI         # First truthy element

```

# Answer
> 3 votes
# `sed -E`, 92 bytes

```
s/^(.*)(.).* \1(.).*/\2\30123456789/;s/^(.)(.).*\1.*\2.*/</;s/^(.)(.).*\2.*\1.*/>/;s/...*/=/

```

Assuming, that both numbers are in one line, space separated. Unfortunately, `sed` doesn't know how compare numbers, so we need to add the digit list and do some regexp backreferencing stuff. Option `-E` used for extended regular expressions to avoid twelve more bytes for escaping:

* `^(.*)(.).* \1(.).*/\2\30123456789/` removes everything but the first differing digit and adds the ordered digits, so `42 43000` would turn into `230123456789`
* `s/^(.)(.).*\1.*\2.*/</` turn the whole line into `<`, if the first digit appears in the digit list before the second one
* `s/^(.)(.).*\2.*\1.*/>/` does the opposite with `>`
* `s/...*/=/` cares for the rest (all legal lines that have not been replaced by `<` or `>` contain at least two characters (`..*` is one byte shorter than `.{2,}`)

# Answer
> 3 votes
# Julia, ~~93~~ ~~77~~ 54 bytes

Port of @Dominic van Essen' R answer in Julia.

Saved 39 bytes thanks to the comment of @MarcMush

---

Golfed version. Try it online!

```
x->(n=ndigits.(x);sign(diff(@.x÷10^(n-min(n...)))[]))

```

Ungolfed version. Try it online!

```
f=function(x)
    n=length.(digits.(x));
    return Int(sign(first(diff(x.÷10 .^(n.-minimum(n))))))
end

```

# Answer
> 3 votes
# Pip, 9 bytes

```
$CM Z:aZb

```

Attempt This Online! Outputs -1 for `<`, 1 for `>`, and 0 for `=`.

### Explanation

```
      aZb  ; Zip the input numbers together, giving a list of pairs of digits
    Z:     ; Transpose into a pair of (equal-length) lists of digits
$CM        ; Fold on numeric comparison

```

The `CM` operator, when given two lists of digits, does almost what we want, but not if the lists are of unequal lengths. (If the shorter list is a prefix of the longer list, the longer list is considered to be greater.) So we zip the numbers together to clip to the length of the shorter one, then zip back again and compare.

# Answer
> 2 votes
# Excel, 70 bytes

```
=@IFERROR(SIGN(TOCOL(1/(MID(A1,ROW(1:99),1)-MID(B1,ROW(1:99),1)),2)),)

```

Inputs in cells `A1` and `B1`.

Outputs `1` for first input, `-1` for second input and `0` for equal.

Assumes maximum string length of `99` characters.

# Answer
> 2 votes
# Retina 0.8.2, 56 bytes

```
^(.+)(.*¶)\1
$2
^(¶.*|.*¶)$

(.).*
$1$*
(1*)¶\1
-
1+-?
1

```

Try it online! Takes input on separate lines but link is to test suite that splits on spaces for convenience. Outputs `-1` for the first input and `1` for the second input having the earliest lower digit. Explanation:

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

```

Remove any matching leading digits.

```
^(¶.*|.*¶)$

```

If at least one string is empty, then the there is no earliest lower digit. The rest of the program has no effect now that the output is empty.

```
(.).*
$1$*

```

Convert the first remaining digit of each number to unary, discarding the rest.

```
(1*)¶\1
-

```

Subtract the two unary numbers.

```
1+-?
1

```

Take the sign.

# Answer
> 2 votes
# JavaScript (Node.js), 21 bytes

```
f=a=>b=>[a>b+f,b>a+f]

```

Try it online!

\


title: Print the N-bonacci sequence

text:
# Question
Title: Print the N-bonacci sequence
This isn't very widely known, but what we call the Fibonacci sequence, AKA

```
1, 1, 2, 3, 5, 8, 13, 21, 34...

```

is actually called the *Duonacci* sequence. This is because to get the next number, you sum the previous 2 numbers. There is also the *Tribonacci* sequence,

```
1, 1, 1, 3, 5, 9, 17, 31, 57, 105, 193, 355, 653, 1201...

```

because the next number is the sum of the previous 3 numbers. And the *Quadronacci* sequence

```
1, 1, 1, 1, 4, 7, 13, 25, 49, 94, 181, 349, 673...

```

And everybody's favorite, the *Pentanacci* sequence:

```
1, 1, 1, 1, 1, 5, 9, 17, 33, 65, 129...

```

And the *Hexanacci* sequence, the *Septanacci* sequence, the *Octonacci* sequence, and so on and so forth up to the N-Bonacci sequence.

The N-bonacci sequence will always start with **N** 1s in a row.

# The Challenge

You must write a function or program that takes two numbers *N* and *X*, and prints out the first *X* N-Bonacci numbers. N will be a whole number larger than 0, and you can safely assume no N-Bonacci numbers will exceed the default number type in your language. The output can be in any human readable format, and you can take input in any reasonable manner. (Command line arguments, function arguments, STDIN, etc.)

As usual, this is Code-golf, so standard loopholes apply and the shortest answer in bytes wins!

# Sample IO

```
#n,  x,     output
 3,  8  --> 1, 1, 1, 3, 5, 9, 17, 31
 7,  13 --> 1, 1, 1, 1, 1, 1, 1, 7, 13, 25, 49, 97, 193
 1,  20 --> 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1
 30, 4  --> 1, 1, 1, 1       //Since the first 30 are all 1's
 5,  11 --> 1, 1, 1, 1, 1, 5, 9, 17, 33, 65, 129

```

# Answer
> 29 votes
## Boolfuck, 6 bytes

```
,,[;+]

```

> You can safely assume no N-Bonacci numbers will exceed the default number type in your language.

The default number type in Boolfuck is a bit. Assuming this also extends to the input numbers N and X, and given that N\>0, there are only two possible inputs - 10 (which outputs nothing) and 11 (which outputs 1).

`,` reads a bit into the current memory location. N is ignored as it must be 1. If X is 0, the loop body (surrounded by `[]`) is skipped. If X is 1, it is output and then flipped to 0 so the loop does not repeat.

# Answer
> 10 votes
## Python 2, 79 bytes

```
n,x=input()
i,f=0,[]
while i<x:v=[sum(f[i-n:]),1][i<n];f.append(v);print v;i+=1

```

Try it online

# Answer
> 7 votes
# Pyth, 13

```
<Qu+Gs>QGEm1Q

```

Test Suite

Takes input newline separated, with `n` first.

### Explanation:

```
<Qu+Gs>QGEm1Q  ##  implicit: Q = eval(input)
  u      Em1Q  ##  read a line of input, and reduce that many times starting with
               ##  Q 1s in a list, with a lambda G,H
               ##  where G is the old value and H is the new one
   +G          ##  append to the old value
     s>QG      ##  the sum of the last Q values of the old value
<Q             ##  discard the last Q values of this list

```

# Answer
> 7 votes
## Haskell, 56 bytes

```
g l=sum l:g(sum l:init l)
n#x|i<-1<$[1..n]=take x$i++g i

```

Usage example: `3 # 8`-\> `[1,1,1,3,5,9,17,31]`.

How it works

```
i<-1<$[1..n]           -- bind i to n copies of 1
take x                 -- take the first x elements of
       i++g i          -- the list starting with i followed by (g i), which is
sum l:                 -- the sum of it's argument followed by
      g(sum l:init l)  -- a recursive call to itself with the the first element
                       -- of the argument list replaced by the sum

```

# Answer
> 6 votes
# Javascript ES6/ES2015, ~~107~~ ~~97~~ ~~85~~ 80 Bytes

Thanks to @user81655, @Neil and @ETHproductions for save some bytes

---

```
(i,n)=>eval("for(l=Array(i).fill(1);n-->i;)l.push(eval(l.slice(-i).join`+`));l")

```

try it online

---

Test cases:

```
console.log(f(3,  8))// 1, 1, 1, 3, 5, 9, 17, 31
console.log(f(7,  13))// 1, 1, 1, 1, 1, 1, 1, 7, 13, 25, 49, 97, 193
console.log(f(5,  11))// 1, 1, 1, 1, 1, 5, 9, 17, 33, 65, 129

```

# Answer
> 5 votes
## ES6, 66 bytes

```
(i,n)=>[...Array(n)].map((_,j,a)=>a[j]=j<i?1:j-i?s+=s-a[j+~i]:s=i)

```

Sadly `map` won't let you access the result array in the callback.

# Answer
> 5 votes
# Jelly, 12 bytes

```
ḣ³S;
b1Ç⁴¡Uḣ

```

Try it online!

### How it works

```
b1Ç⁴¡Uḣ  Main link. Left input: n. Right input: x.

b1       Convert n to base 1.
    ¡    Call...
  Ç        the helper link...
   ⁴       x times.
     U   Reverse the resulting array.
      ḣ  Take its first x elements.

ḣ³S;     Helper link. Argument: A (list)

ḣ³       Take the first n elements of A.
  S      Compute their sum.
   ;     Prepend the sum to A.

```

# Answer
> 5 votes
## Python 2, 55 bytes

```
def f(x,n):l=[1]*n;exec"print l[0];l=l[1:]+[sum(l)];"*x

```

Tracks a length-`n` window of the sequence in the list `l`, updated by appending the sum and removing the first element. Prints the first element each iteration for `x` iterations.

A different approach of storing all the elements and summing the last `n` values gave the same length (55).

```
def f(x,n):l=[1]*n;exec"l+=sum(l[-n:]),;"*x;print l[:x]

```

# Answer
> 5 votes
# Haskell, 47 bytes

```
q(h:t)=h:q(t++[h+sum t])
n?x=take x$q$1<$[1..n]

```

Try it online!

`<$` might have been introduced into Prelude after this challenge was posted.

---

**Haskell, 53 bytes**

```
n%i|i>n=sum$map(n%)[i-n..i-1]|0<1=1
n?x=map(n%)[1..x]

```

Try it online!

Defines the binary function `?`, used like `3?8 == [1,1,1,3,5,9,17,31]`.

The auxiliary function `%` recursively finds the `i`th element of the `n`-bonacci sequence by summing the previous `n` values. Then, the function `?` tabulates the first `x` values of `%`.

# Answer
> 4 votes
# Husk, 9 bytes

```
↑§¡ȯΣ↑_B1

```

Try it online!

Starts from the `B`ase-`1` representation of *N* (simply a list of *N* ones) and `¡`teratively sums (`Σ`) the last (`↑_`) *N* elements and appends the result to the list. Finally, takes () the first *X* numbers in this list and returns them.

# Answer
> 4 votes
# Haskell, 46 bytes

```
g _ 0=[]
g(h:t)n=h:g(t++[sum$h:t])(n-1)

```

```
g.g[1]

```

Attempt This Online!

This is based on xnor's answer but it employs 1 clever trick.

The \\$n\\$-bonacci sequence always start with \\$n\\$ `1`s. A more general version of this might start with just any \\$n\\$ values. And this more general version is what we implement with `g`. `g` takes a list of \\$n\\$ integers and a value \\$m\\$ and gives us a list of the first \\$m\\$ terms of this generalized \\$n\\$-bonacci sequence.

The trick is then that `g[1]` is a cheap way to generate \\$n\\$ `1`s. Since the sequence starting with `[1]` is just an endless stream of `1`s. So we use `g` in two ways, and even though `g` might be slightly longer because it implements something a little more general, it saves bytes because it serves two purposes.

# Answer
> 4 votes
# C#, 109 bytes

```
(n,x)=>{int i,j,k;var y=new int[x];for(i=-1;++i<x;y[i]=i<n?1:k){k=0;for(j=i-n;j>-1&j<i;)k+=y[j++];}return y;}

```

Try it online!

---

```
(n, x) => {
    int i, j, total;
    var result = new int[x];
    for (i = -1; ++i < x; ) { //calculate each term one at a time
        total = 0; //value of the current term
        for (j = i - n; j > -1 & j < i;) //sum the last n terms
        {
            total += result[j++];
        }
        result[i] = i < n ? 1 : total; //first n terms are always 1 so ignore the total if i < n
    }
    return result;
}

```

# Answer
> 3 votes
# C++11, 360 bytes

Hi I just like this question. I know c++ is a very hard language to win this competition. But I'll thrown a dime any way.

```
#include<vector>
#include<numeric>
#include<iostream>
using namespace std;typedef vector<int>v;void p(v& i) {for(auto&v:i)cout<<v<<" ";cout<<endl;}v b(int s,int n){v r(n<s?n:s,1);r.reserve(n);for(auto i=r.begin();r.size()<n;i++){r.push_back(accumulate(i,i+s,0));}return r;}int main(int c, char** a){if(c<3)return 1;v s=b(atoi(a[1]),atoi(a[2]));p(s);return 0;}

```

I'll leave this as the readable explanation of the code above.

```
#include <vector>
#include <numeric>
#include <iostream>

using namespace std;
typedef vector<int> vi;

void p(const vi& in) {
    for (auto& v : in )
        cout << v << " ";
    cout << endl;
}

vi bonacci(int se, int n) {
    vi s(n < se? n : se, 1);
    s.reserve(n);
    for (auto it = s.begin(); s.size() < n; it++){
        s.push_back(accumulate(it, it + se, 0));
    }
    return s;
}

int main (int c, char** v) {
    if (c < 3) return 1;
    vi s = bonacci(atoi(v[1]), atoi(v[2]));
    p(s);
    return 0;
}

```

# Answer
> 3 votes
# Java, 82 + 58 = 140 bytes

Function to find the *ith* **n**-bonacci number (**82 bytes**):

```
int f(int i,int n){if(i<=n)return 1;int s=0,q=0;while(q++<n)s+=f(i-q,n);return s;}

```

Function to print first *k* **n**-bonacci number (**58 bytes**):

```
(k,n)->{for(int i=0;i<k;i++){System.out.println(f(i,n));}}

```

# Answer
> 3 votes
Uiua (version 0.0.7), 34 bytes

```
→(;;)⍥(⊂∶/+↙∶→,⇌.)∶→(-,,)[⍥.-1∶1].

```

# Answer
> 2 votes
# Python 3, 59

Saved 20 bytes thanks to FryAmTheEggman.

Not a great solution, but it'll work for now.

```
def r(n,x):f=[1]*n;exec('f+=[sum(f[-n:])];'*x);return f[:x]

```

Also, here are test cases:

```
assert r(3, 8) == [1, 1, 1, 3, 5, 9, 17, 31]
assert r(7, 13) == [1, 1, 1, 1, 1, 1, 1, 7, 13, 25, 49, 97, 193]
assert r(30, 4) == [1, 1, 1, 1]

```

# Answer
> 2 votes
# APL, 21

```
{⍵↑⍺{⍵,+/⍺↑⌽⍵}⍣⍵+⍺/1}

```

This is a function that takes *n* as its left argument and *x* as its right argument.

Explanation:

```
{⍵↑⍺{⍵,+/⍺↑⌽⍵}⍣⍵+⍺/1}
                   ⍺/1  ⍝ begin state: X ones
                  +     ⍝ identity function (to separate it from the ⍵)
    ⍺{         }⍣⍵     ⍝ apply this function N times to it with X as left argument
      ⍵,               ⍝ result of the previous iteration, followed by...
        +/              ⍝ the sum of
          ⍺↑            ⍝ the first X of
            ⌽          ⍝ the reverse of
             ⍵         ⍝ the previous iteration
 ⍵↑                    ⍝ take the first X numbers of the result

```

Test cases:

```
      ↑⍕¨ {⍵↑⍺{⍵,+/⍺↑⌽⍵}⍣⍵+⍺/1} /¨ (3 8)(7 13)(1 20)(30 4)(5 11)
 1 1 1 3 5 9 17 31
 1 1 1 1 1 1 1 7 13 25 49 97 193
 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
 1 1 1 1
 1 1 1 1 1 5 9 17 33 65 129

```

# Answer
> 2 votes
# C, 132 bytes

The recursive approach is shorter by a couple of bytes.

```
k,n;f(i,s,j){for(j=s=0;j<i&j++<n;)s+=f(i-j);return i<n?1:s;}main(_,v)int**v;{for(n=atoi(v[1]);k++<atoi(v[2]);)printf("%d ",f(k-1));}

```

## Ungolfed

```
k,n; /* loop index, n */

f(i,s,j) /* recursive function */
{
    for(j=s=0;j<i && j++<n;) /* sum previous n n-bonacci values */
        s+=f(i-j);
    return i<n?1:s; /* return either sum or n, depending on what index we're at */
}

main(_,v) int **v;
{
    for(n=atoi(v[1]);k++<atoi(v[2]);) /* print out n-bonacci numbers */
        printf("%d ", f(k-1));
}

```

# Answer
> 2 votes
# Brain-Flak, ~~144~~ ~~124~~ 122 bytes

-20 bytes thanks to Nitroden

This is my first Brain-Flak answer, and I'm sure it can be improved. Any help is appreciated.

```
(([{}]<>)<{({}(()))}{}>)<>{({}[()]<<>({<({}<({}<>)<>>())>[()]}{})({}<><({({}<>)<>}<>)>)<>>)}{}<>{({}<{}>())}{}{({}<>)<>}<>

```

Try it online!

# Answer
> 2 votes
# Pari/GP, 46 bytes

The generating function of the sequence is:

$$\frac{(n-1)x^n}{x^{n+1}-2x+1}-\frac{1}{x-1}$$

```
(n,m)->Vec(n--/(x-(2-1/x)/x^n)-1/(x-1)+O(x^m))

```

Try it online!

# Answer
> 2 votes
# , 60 bytes

```
function(n,m){for(i in 1:m)T[i]=`if`(i>n,sum(T[i-1:n]),1);T}

```

Try it online!

# Answer
> 2 votes
# Vyxal , 8 bytes

```
1ẋ?‡W∑*Ḟ

```

Try it Online!

```
1ẋ       # [1] * input
   ‡W∑   # Function summing its inputs
  ?   *  # Set the arity to the input
       Ḟ # Generate an infinite list from the function and the vector of 1s.

```

# Answer
> 1 votes
# Julia, 78 bytes

```
f(n,x)=(z=ones(Int,n);while endof(z)<x push!(z,sum(z[end-n+1:end]))end;z[1:x])

```

This is a function that accepts two integers and returns an integer array. The approach is simple: Generate an array of ones of length `n`, then grow the array by adding the sum of the previous `n` elements until the array has length `x`.

Ungolfed:

```
function f(n, x)
    z = ones(Int, n)
    while endof(z) < x
        push!(z, sum(z[end-n+1:end]))
    end
    return z[1:x]
end

```

# Answer
> 1 votes
# MATL, 22 ~~26~~ bytes

```
1tiXIX"i:XK"tPI:)sh]K)

```

This uses current release (10.2.1) of the language/compiler.

**Try it online!**

A few extra bytes :-( due to a bug in the `G` function (paste input; now corrected for next release)

### Explanation

```
1tiXIX"      % input N. Copy to clipboard I. Build row array of N ones
i:XK         % input X. Build row array [1,2,...X]. Copy to clipboard I
"            % for loop: repeat X times. Consumes array [1,2,...X]
  t          % duplicate (initially array of N ones)
  PI:)       % flip array and take first N elements
  sh         % compute sum and append to array
]            % end
K)           % take the first X elements of array. Implicitly display

```

# Answer
> 1 votes
## Perl 6, ~~52~72~~ 47~67 bytes

```
sub a($n,$x){EVAL("1,"x$n~"+*"x$n~"...*")[^$x]}

```

Requires the module `MONKEY-SEE-NO-EVAL`, because of the following error:

> ===SORRY!=== Error while compiling -e
> EVAL is a very dangerous function!!! (use MONKEY-SEE-NO-EVAL to override,
> but only if you're VERY sure your data contains no injection attacks)
> at -e:1

```
$ perl6 -MMONKEY-SEE-NO-EVAL -e'a(3,8).say;sub a($n,$x){EVAL("1,"x$n~"+*"x$n~"...*")[^$x]}'
(1 1 1 3 5 9 17 31)

```

# Answer
> 1 votes
# Perl 6, 38 bytes

```
->\N,\X{({@_[*-N..*].sum||1}...*)[^X]} # 38 bytes

```

```
-> \N, \X {
  (

    {

      @_[
        *-N .. * # previous N values
      ].sum      # added together

      ||     # if that produces 0 or an error
      1      # return 1

    } ... *  # produce an infinite list of such values

  )[^X]      # return the first X values produced
}

```

### Usage:

```
# give it a lexical name
my &n-bonacci = >\N,\X{…}

for ( (3,8), (7,13), (1,20), (30,4), (5,11), ) {
  say n-bonacci |@_
}

```

```
(1 1 1 3 5 9 17 31)
(1 1 1 1 1 1 1 7 13 25 49 97 193)
(1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1)
(1 1 1 1)
(1 1 1 1 1 5 9 17 33 65 129)

```

# Answer
> 1 votes
# J, 31 bytes

```
]{.(],[:+/[{.])^:(-@[`]`(1#~[))

```

Ungolfed:

```
] {. (] , [: +/ [ {. ])^:(-@[`]`(1 #~ [))

```

## explanation

Fun times with the power verb in its gerund form:

```
(-@[`]`(1 #~ [)) NB. gerund pre-processing

```

Breakdown in detail:

* `] {. ...` Take the first `<right arg>` elements from all this stuff to the right that does the work...
* `<left> ^: <right>` apply the verb `<left>` repeatedly `<right>` times... where `<right>` is specified by the middle gerund in `(-@[`\]`(1 #~ [)`, ie, `]`, ie, the right arg passed into the function itself. So what is `<left>`? ...
* `(] , [: +/ [ {. ])` The left argument to this entire phrase is first transformed by the first gerund, ie, `-@[`. That means the left argument to this phrase is the *negative* of the left argument to the overall function. This is needed so that the phrase `[ {. ]` takes the *last* elements from the return list we're building up. Those are then summed: `+/`. And finally appended to that same return list: `] ,`.
* So how is the return list initialized? That's what the third pre-processing gerund accomplishes: `(1 #~ [)` -- repeat 1 "left arg" number of times.

Try it online!

# Answer
> 1 votes
# Ruby, 41 bytes

```
->a,b{r=[1]*a;b.times{z,*r=r<<r.sum;p z}}

```

Try it online!

# Answer
> 1 votes
# , 68 bytes

```
function(n,x){a=1+!1:n;for(i in n+1:x){a[i]=sum(a[(i-n:1)])};a[1:x]}

```

Try it online!

# Answer
> 1 votes
# K (ngn/k), ~~26~~ 24 bytes

```
{(y-x){y,+/x#y}[-x]/x#1}

```

Try it online!

# Answer
> 1 votes
# Vyxal, 8 bytes

```
1ẋ{:∑pṫ,

```

Try it Online!

-2 bytes thanks to emanresu A

# Answer
> 1 votes
# JavaScript, 65 bytes

The `eval` & `slice` are annoying me!

```
x=>g=(n,...a)=>n?g(n-1,...a,a[x-1]?eval(a.slice(-x).join`+`):1):a

```

Try it online!

# Answer
> 1 votes
# Thunno 2, 13 bytes

```
{1}¹{K°ɱS}K¹ɱ

```

Attempt This Online!

#### Explanation

```
{1}¹{K°ɱS}K¹ɱ  # Implicit input
{1}            # Push 1 to the stack n times
   ¹{    }     # Repeat x times:
     K°ɱ       #  Take the top n items of the stack
        S      #  And sum this list
          K¹ɱ  # Take the top x items of the stack
               # Implicit output

```

# Answer
> 0 votes
# PHP, 78 bytes

```
for(list(,$n,$x)=$argv;$i<$x;print${$i++}." ")$s+=$$i=$i<$n?1:$$d+$s-=${$d++};

```

Try it online!

-4 Bytes using PHP\>=7.1 `[,$n,$x]` instead of `list(,$n,$x)`

# Answer
> 0 votes
# Jq 1.5, 67 bytes

```
def C:if length>X then.[:X]else.+=[.[-N:]|add]|C end;[range(N)|1]|C

```

Assumes input provided by N and X e.g.

```
def N: 5;
def X: 11;

```

Expanded

```
def C:                        # . is current array
    if length>X               # stop when array is as long as X
    then .[:X]                # return first X elements
    else .+=[.[-N:]|add] | C  # recursively add sum of last N elements to array
    end
;
  [range(N)|1]                # initial state
| C

```

Try it online!

# Answer
> 0 votes
# Mathematica, 59 bytes

```
((f@#=1)&/@Range@#;f@n_:=Tr[f[n-#]&/@Range@#];f/@Range@#2)&

```

You'll probably want to `Clear@f` between function calls. Arguments are `n,x`, just like the test cases.

# Answer
> 0 votes
# Tidy, 36 bytes

```
{x,n:n^recur(*tile(x,c(1)),sum@c,x)}

```

Try it online!

## Explanation

```
{x,n:n^recur(*tile(x,c(1)),sum@c,x)}
{x,n:                              }   lambda taking parameters `x` and `n`
     n^                                take the first `n` terms of...
       recur(                     )        a recursive function
             *tile(x,c(1)),                whose seed is `x` `1`s
                           sum@c,          taking the sum of each window
                                 x         with a window size of `x`

```

# Answer
> 0 votes
# Japt, 18 bytes

```
@ZsVn)x}gK=Vì1;K¯U

```

Try it online!

Explanation:

```
         K=Vì1        :Start with n 1s in an array K
@      }gK            :Extend K to at least x elements by setting each new element to:
      x               : The sum of
 ZsVn                 : The previous n elements
              ;       :Then
               K¯U    :Return the first n elements of K

```

# Answer
> 0 votes
# MathGolf, 10 bytes

```
ª*kÆ_Σ▐├p;

```

Try it online!

## Explanation

```
ª            push [1]
 *           pop a, b : push(a*b)
  k          read integer from input
   Æ         start block of length 5
    _        duplicate TOS
     Σ       sum(list), digit sum(int)
      ▐      append to end of list
       ├     pop from left of string/array
        p    print with newline
         ;   discard TOS

```

# Answer
> 0 votes
# Japt, ~~16~~ 12 bytes

```
@ZÔ¯V x}hVÆ1

```

Try it

```
@ZÔ¯V x}hVÆ1     :Implicit input of integers U=X & V=N
         VÆ1     :Map the range [0,V) returning 1 for each element
        h        :Push the result of the following to the array and repeat until its length equals U
@                :  Pass the array through the following function as Z
 ZÔ              :    Reverse Z
   ¯V            :    Slice to the Vth element
      x          :    Reduce by addition
       }         :  End function

```

# Answer
> 0 votes
# C# (.NET Core), 130 bytes

```
(n,x)=>{int j=0,k=0,l=0;var b=new int[x];for(;j<(x<n?x:n);)b[j++]=1;for(j=n;j<x;l=0){for(k=n;k>0;)l+=b[j-k--];b[j++]=l;}return b;}

```

Try it online!

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

```
a(c,C,i){for(int Q[C+c],*q=Q;C--;printf("%d ",*q++))for(*q=Q-q>(i=-c);Q-q<=i&i<0;)*q+=q[i++];}

```

Try it online!

# Answer
> 0 votes
# krrp, 72 bytes

```
^nx:\L[take]x,^nl:?nL#!fl@-n1#!r[append]lL[sum]lEl.x[map]^_:1.[range]0n.

```

Try it online!

---

# Explanation

```
^nx:              ~ lambda expression in two parameters
 \L               ~  import list module
 [take]x          ~  the first x elements of
  ,^nl:           ~   extend the initial list of n ones
    ?n            ~    if n is non-zero
     L #!fl       ~     keep the first element
      @-n1        ~     recur
       #!r        ~     separate the first element
        [append]l ~      append an additional element,
         L[sum]lE ~      namely the sum of the previous elements
     l            ~    if n is zero, yield l
   . x            ~ extend x elements, yielding in a list of n+x elements
   [map]^_:1.     ~   map a constant function
   [range]0n.     ~   onto a list of n elements

```

Try it online!

# Answer
> 0 votes
# PostScript, 83 bytes

```
/f{/x exch def/n exch def[1 1 x{n le{1}{n copy n 1 sub{add}repeat}ifelse}for]==}def

```

e.g., `5 11 f` prints `[1 1 1 1 1 5 9 17 33 65 129]`.

Try it online!

---
Tags: code-golf, math, fibonacci
---