# Question
Title: Repeat your program to print Fibonacci numbers
Write a program fragment so that, when repeated N times it prints the Nth Fibonacci number. For example, if your program is `print(x)` then:

* `print(x)` should print `1`
* `print(x)print(x)` should print `1`
* `print(x)print(x)print(x)` should print `2`
* `print(x)print(x)print(x)print(x)` should print `3`
* `print(x)print(x)print(x)print(x)print(x)` should print `5`
* etc.

First 2 items are 1 then each consecutive item in the sequence is the sum of the previous two.

You may include a non-repeated header and footer, but a smaller header and footer will always beat an answer with a larger sum of header+footer. For example, a 1000 byte answer with no header wins from a 20 byte answer with a 1 byte footer. However, a 0 byte header 20 byte body will win from both.

With header length being equal, smallest number of bytes, in each language, wins.

### Tips

Output in unary
Use shell escape codes like `\r` to erase the previous print.
Use your languages implicit output feature

### Example Submission

> # Python, 0 header/footer, 97 body
>
> ```
> if"k"not in globals():k=["","x"];print("x",end="")
> else:k.append(k[-1]+k[-2]);print(k[-3],end="")
>
> ```
>
> Output in unary
>
> Attempt This Online!

Comments are entirely valid, but solutions that don't use comments are extra impressive.

# Answer
> 15 votes
# , 12 bytes, no header/footer

```
+(F=+T)->T;F

```

Try it once online!

Try it twice

Try it three times

Try it five times

Try it \\$n\\$ times

Right-hand assignment `->` is useful for suppressing output. Paging Robin Ryder and his various solutions involving `->`.

## Why this works

`F` and `T` are automatically assigned as variables for the constants `FALSE` and `TRUE`, and happily are coerced to `0` and `1` in arithmetic expressions.

The shortest R answer to the canonical Fibonacci challenge uses `F<-T+(T=F)` as the body of a loop, using the fact that assignment returns the assigned value (right-hand side for `<-` and `=`) **invisibly**, so the updates to the values happen in the right order (and are made visible by `show`). In that challenge, `F` holds the leading value \\$F\_n\\$ and `T` holds \\$F\_{n-1}\\$.

A few adjustments are required here:

1. `F` now holds the *trailing* value \\$F\_{n}\\$, and `T` is updated on each loop as `F+(F=T)->T` to be \\$F\_{n+1}\\$, on every iteration.
2. We use `F=+T` so that the first copy prints out `1` instead of `TRUE`.
3. Leading `+` and the infrequently-used right-hand assignment `->` operator to satisfy the concatenation requirement.
4. Trailing `;F` to use implicit output to print out the required value.

# Answer
> 14 votes
# Piet \+ ascii-piet, 19 bytes (12×4=48 codels)

```
_TLDJdAaAQIbcr_cc _

```

Try Piet online!

Try Piet online! (x6)

```
A1      nop
B1-F1   1 1 ! roll       `1 0 roll`; an overall no-op if there were some values
                         on the stack, but leaves 1 0 if empty
                         (therefore pushes 1 0 on the first iteration only)
F1-K1   dup 3 1 roll +   apply Fibonacci to the top two values
                         [a b] -> [b a+b]

```

When the program is repeated, the grid is concatenated vertically, putting A1's white cell on L1 and so on. At K1, two things can happen:

* If there are more repetitions below, the IP keeps going down, running more iterations of Fibonacci.
* Otherwise, it heads east, prints the top value as integer (J2-J3) and halts (J4-K4).

# Answer
> 11 votes
# Thunno 2, 4 bytes (no header/footer)

```
Ɓ+1|

```

Try it online!
2x
3x
Nx

#### Explanation

```
Ɓ+    # Without popping, add top two values
  1|  # Replace a 0 with a 1
      # Implicit output

```

# Answer
> 11 votes
# Python, 34 bytes

```
a='x';b=''
print(end=a);a,b=b,a+b#

```

Attempt This Online!

Outputs in unary.

### How?

Streamlined version of OP's example code

# Answer
> 10 votes
# Itr, ~~5~~ 4 bytes (no header or footer)

`â+1w`

online interpreter

2x

3x

Nx (uses `F` operator to repeat sequence input number of times)

## Explanation

```
â+1w ; implicitly start with 0,0 on stack
â    ; push top value below second value a,b -> b,a,b
 +   ; add top two values -> b,a+b
  1w ; maximum of 1 and top stack value
     ; implicit output

```

# Answer
> 10 votes
# T-SQL ~~171~~ ~~160~~ 159 bytes (no header or footer)

*-1 byte thanks to @MickyT*

```
/*
WHERE 1=0--*//*
--*/Select 0 x,1 y into T;EXEC('create trigger X on T for delete as if @@rowcount>0select x from DELETED')
UPDATE T SET x=y,y=x+y;DELETE T--

```

Try it online (use MS SQL)

The trick is using comments to have the initial select and trigger creation on only the first repeat, and the `WHERE` clause preventing the deletion of the fibbonacci record on all except the final repeat. Selecting from `DELETED` then outputs it.

# Answer
> 8 votes
# Cascade, 6 bytes

```
#|
\?

```

Try it online! (prints `0`)

Try it online!Try it online!Try it online! (prints `00`)

Try it online!Try it online!Try it online!Try it online!Try it online!Try it online! (prints `00000000`)

Outputs in unary with zeros. Uses the fact that \\$f\_n = 1 + \sum\_{i=0}^{n-2} f\_{i}\\$.

```
#|   Start evaluating at the first `#`; prints 0 once (acting as 1+)
\?   `\` Move to the second column; skip evaluating f(n-1)
#|   `|` Pass through
\?   `?` Evaluate both columns; the left column evaluates f(n-2) (by induction)
#|   and the right passes through, eventually evaluating all branches
...  down to f(1)

```

---

# Cascade, 10 bytes

```
#1
\+/
\||

```

Try it online! (outputs 1)

Try it online!Try it online!Try it online! (outputs f3 = 2)

Try it online!Try it online!Try it online!Try it online!Try it online!Try it online! (outputs f6 = 8)

After repeating, the code looks like this:

```
#1
\+/
\||#1
\+/
\||#1
\+/
\||#1
\+/
\||

```

The 3 columns on the left are relevant. Read the explanation from bottom to top:

```
#      Print the value as number

\
 |     Ignore one iteration and fetch fn

 +/    Iterate n-1 times (when n is the number of repetition):
\||      (a, b) = (a+b, a)

 10    Initialize to a = 1 (column 2) and b = 0 (column 3)

```

# Cascade, 3 bytes footer, 3 bytes body

body:

```
\?

```

footer:

```
 #

```

Try it online! (outputs `0`)

Try it oTry it oTry it online! (outputs f3 = 2 = `00`)

Try it oTry it oTry it oTry it oTry it oTry it online! (outputs f6 = 8 = `00000000`)

Outputs in unary with zeros. `?` evaluates the center (of the next row), and then evaluates the left (of the next row) because the center always evaluates to 0. This certainly achieves better encoding of fibonacci loop, ~~but I couldn't figure out how to include "print 0" in the loop~~.

# Answer
> 8 votes
# Piet \+ ascii-piet, 53 bytes (15×7=105 codels), no header/footer

```
ttlddtN ub?fnNssSkKCVrTtTLcfkdtlElt?l??T   lL sdD S??

```

Program as picture:

Output in unary.

Try Piet online!

Try Piet online! x2

Try Piet online! x3

Try Piet online! x5

Try Piet online! x10

This is so bad but my brain is completely fried rn, this will do for now. Definitely can be golfed though ~~(watch @Bubbler get some insane 30 byte answer lmao).~~ Bruh ain't no way, Bubbler just post some insane 19 bytes answer. Just move on and go upvote Bubbler's answer lmao.

# Answer
> 8 votes
# C (gcc), 84 bytes (no header/footer)

```
t
#ifndef A
,b;main(a){
#define At
#define A printf("%d",a);}
#endif
t=a;a=a+b;b=t;A

```

Try it online!

This really shows the power of the preprocessor

# Answer
> 7 votes
# 05AB1E, 4 bytes (no header/footer)

```
¼¾Åf

```

Try it online or verify the first ten iterations.

**Explanation:**

```
¼     # Increase counter variable `¾` by 1 (which is 0 by default)
 ¾    # Push counter variable `¾`
  Åf  # Pop and push the 0-based ¾'th Fibonacci value
      # (after which the top of the stack is output implicitly as result)

```

# Answer
> 6 votes
# Ruby, ~~26~~ 21 bytes

```
[a=$.+$.=a||1];p *[a]

```

Try it online!

Thanks Value Ink, Jo King and Sisyphus for the improvements.

### In short

When it's repeated, it will just increase the number and print nothing:

```
[a=$.+$.=a||1] # -> initializes a with 1

#N times:
p *[a][a=$.+$.=a||1] # -> update a then print the non-existing a-th element of [a]

p *[a] # -> print all elements of [a]

```

I didn't know that the splat operator could be used like this.

# Answer
> 6 votes
# Brain-Flak, 16 bytes

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

```

Try it online!

```
(                       # Push...
 ()                     #   One
   [[]]                 #   Minus the current stack height
       ({})             #   Plus peek the value on top of the stack
           <>           #   Move to the other stack
             {}         #   Plus pop the value on top of the stack
               )        #

```

The `(()[[]]({})` trick is a convenient way to initialize the first stack to a '1' if it's empty, and leave it unmodified if it's non-empty. Also it's not everyday that a brain-flak solution has an odd number of `<>`s!

# Answer
> 6 votes
# Uiua, ~~89~~ ~~36~~ ~~25~~ 19 bytes, no header/footer/`tag`

```
:try(+,e)(1 0;)
e=

```

Try it online!

Try it online!Try it online!

Try it online!Try it online!Try it online!

Try it online!Try it online!Try it online!Try it online!Try it online!Try it online!

The programs look a bit different in the links thanks to the auto-formatter; if you paste the program in as given it turns into that then works. Note the trailing newline.

Although `tag` is the only non-random way to make an expression stateful, this exploits the ability to repeatedly shadow built-in constant `e`, as well as to catch empty-stack errors with `⍣ try`.

For the first copy, the stack is empty, so:

```
 try(   )          Try:
       e           Push Euler's constant,
      ,            then push the nonexistent stack element under it.
 try     (    )    That errors, so
             ;     discard the error message
          1 0      and push 0 and 1.
:                  Swap to 1 and 0.
e=                 Pop the 0 to redefine e as 0.
                   The stack now contains only 1

```

which prints `1` as the only value on the stack if no further copies are appended.

For the second copy, the stack is non-empty, so:

```
 try(   )          Try:
       e           Push e (now 0),
      ,            then push the value under it (1),
     +             and add them.
 try     (    )    That doesn't error, so nothing weird happens to it.
:                  Swap, so the old result (1) is on top
                   and the sum (also 1) is on the bottom.
e=                 Pop the old result to re-redefine e as 1.
                   The stack now contains only 1

```

then

```
 try(   )          Try:
       e           Push e (now 1),
      ,            then push the value under it (1),
     +             and add them.
 try     (    )    That doesn't error, so nothing weird happens to it.
:                  Swap, so the old result (2) is on top
                   and the sum (1) is on the bottom.
e=                 Pop the old result to re-redefine e as 1.
                   The stack now contains only 2

```

and so on.

# Answer
> 5 votes
# Ruby, ~~29~~ 23 bytes

Dug around for a bit until I found this magical function called `at_exit`/`END` that could be used to ensure the number is printed once at the end. `$.` is 0 by default, which saves some bytes.

Someone else can port the Unary solution if they want to.

*-6 bytes from dingledooper.*

```
a=1;END{p$.}
$.=a+a=$.#

```

Attempt This Online! x3 x5

# Answer
> 5 votes
# Vyxal, no headers, no footers, just 3 bytes

```
!∆f

```

Try it Online!

or a test suite of the first 1 to 9 repetitions

Hello to everyone who ports this in another stack language or independently discovers it. :p

## Explained

```
!∆f
!   # Push the length of the stack
 ∆f # Push the lengthth fibonacci number, starting from f(0) = 1

```

# Answer
> 5 votes
# Nekomata, 4 bytes (no header/footer)

```
ˣ+1I

```

A port of @The Thonnu's Thunno 2 answer.

```
ˣ+1I
ˣ+      Add without popping; fails if length of stack is less than 2
  1I    Replace failure with 1

```

# Answer
> 5 votes
# JavaScript (Node.js), 38 bytes, 0 Header/Footer

Creates a anonymous function

```
(a=>a?b=>b?f=c=>c?c(f)(a):a()+b():1:1)

```

Attempt This Online!

Lambda Calculus go brr

# Answer
> 5 votes
# Python 3.8 (pre-release), 41 bytes, not unary solution

```
for i in(1,a:=0):
 i,a=i+a,i or+print(a)#

```

Try it online!

# Answer
> 4 votes
# Swift 5.8, no header/footer, 43 bytes

```
var x=0,y=1;defer{print(x)}
(x,y)=(y,x+y)//

```

Port of Value Ink's Ruby answer. Try it on SwiftFiddle!

## Swift 5.6, no header/footer, 106 bytes

This was the original answer. Even though the other one is shorter and also works in 5.6, I'm leaving this one here for the absurdity of it.

```
var x = -1,y=1//"
print(String(repeating:"1",count:y),terminator:"")
(x,y)=(y,x+y)
#if swift(<4)
(#endif
"

```

This abuses a bug (patched in 5.7) where, if an inactive `#if swift` block contains unmatched parentheses, the `#endif` may be followed by an ill-formed string literal, including one with no close quote. I want to elaborate on why this is so strange:

When a `#if` block is inactive due to `os()`, `arch()`, `canImport()`, a `-D` flag, or `#if false`, it's still parsed, but not compiled: example. However, if it's inactive due to `swift()`, it isn't parsed. It's tokenized so that the compiler knows where the correct `#endif` is, but it's not fully parsed: example. So, the fact that mismatched parentheses inside an inactive `#if swift()` do *anything* is bizarre, to say the least.

When this code is appended to itself, the redeclaration of the variables becomes an unused string:

```
var x = -1,y=1//"
print(String(repeating:"1",count:y),terminator:"")
(x,y)=(y,x+y)
#if swift(<4)
(#endif
"var x = -1,y=1//"
print(String(repeating:"1",count:y),terminator:"")
(x,y)=(y,x+y)
#if swift(<4)
(#endif
"

```

The lack of space before the line comment throws off SwiftFiddle's syntax highlighting; SE's highlighting is correct. With that out of the way,

# Answer
> 4 votes
# Node.js, 36 bytes, no header/footer

Returns the result in the exit code.

The highest possible value depends on the operating system. I *think* that's 8-bit/unsigned on Linux and at least 32-bit/signed on (recent versions of) Windows.

```
a=0;b=1
process.exitCode=a=b+(b=a)//

```

See the exit code in the debug section:

Try it online! x1
Try it online! x10

# Answer
> 4 votes
# vim, 10 bytes

```
0py$"_cla

```

Note that the above ends with an ASCII "escape" character which, at least in my browser, is invisible. Basically, this is `0py$"_cla<ESC>`.

This produces the letter "a" once when run once, once when run twice, twice when run 3 times, 3 times when run 4 times, 5 times when run 5 times, 8 times when run 6 times, and so on.

Try it online!

Here is an explanation, along with equivalent Python code, where `L` and `R` denote the text to the left and the right of the cursor, and `Y` denotes the contents of the current register:

* `0`: move the cursor to the beginning of the line (Python: `L, R = '', L + R`)
* `p`: paste the contents of the default register, and put the cursor at the end of it (Python: `L, R = L + R[:1] + Y[:-1], Y[-1:] + R[1:]`)
* `y$`: set the default register to all the text after the cursor (Python: `Y = R`)
* `"_`: when running the following command, do *not* set the default register to the deleted text
* `cla<ESC>`: delete the character after the cursor (if there is one) and insert an "a" (Python: `R = 'a' + R[1:]`)

Near miss: the program `y$0pcla<ESC>` would be an 8-byte solution, except that it generates the sequence at the wrong offset: running it twice produces "aa," running it three times produces "aaa," running it four times produces "aaaaa," and so on. The program `0py$cla<ESC>` doesn't work because the command `cla<ESC>` sets the default register to the deleted text (unless it's preceded with `"_`).

# Answer
> 4 votes
# Headass, 56 bytes

```
U+O[+O[ORO[]]+E.U-):R-OU[UO]OUO[]]+E;U({])UU+O[]]E:?-(}.

```

Prints the word `debug` fib(n) times, where n is the number of copies, separated by newlines. This relies on the fact that DSO doesn't actually provide any debug info when the debug operation is called. it just prints the word 'debug'. Pretty funny stuff!

Linking up to 6 copies because that's how many it took to convince myself:

Try It Online!, Try It Online!x2, Try It Online!x3, Try It Online!x4, Try It Online!x5, Try It Online!x6

## Explanation:

Overall strategy: Each repeat of the code (we will call them "chunks") just aims to print enough 'debug's to reach the next fibonacci number. So the first chunk needs to print 1, since fib(1) = 1, but chunk two doesn't want to print anything, since chunk one already got us to fib(2) = 1, but then chunk three wants to print one more, since fib(3) = 2... etc etc etc. Luckily, there is a sequence which describes exactly this phenomenon:

`1 0 1 1 2 3 5 8 13 21...`

It is the fibonacci sequence.

Each chunk increments a global variable (called `i` in the explanation below) and runs a short loop to get fib(i) but with fib starting with 1, 0. Then, it prints 'debug' that many times before moving on to the next chunk.

```
U+O[+O[ORO[]]+E.   code block 0 (and 2, and 4...)
U+O                if i exists, i++, else let i = 1
   [+O             let a = 1
      [O           let b = 0
        RO         dont worry about it
          []]+E    go to code block 2*(i-1)+1
                   with these values
               .   end code block

U-):R-OU[UO]OUO[]]+E;U({])UU+O[]]E:?-(}.   code block 1 (and 3, and 5...)
U-)                 ;                      if i == 0
                     U({])        :   }      while(a != r0){
                                   ?           print('debug')
                                    -(         a-- (effectively)
                                             }
                          U                  dont worry about it
                           U+O               i++
                              []]E           go to code block 2*i
                                             with the new i value
   :                                       }else{
    R-O                                      i--
       U[                                    r2 = a
         UO                                  a = b
           ]O                                b = b + r2
             UO                              dont worry about it
               []]+E                         go to code block 2*i+1
                                             with these new values
                                       .   end code block

```

all those parts where i say not to worry about it are just things that have to do with the specific ways im shuffling values around on the queue, and it would take up too much space to explain while not adding much clarity. Like and subscribe

## Headass, 27 bytes + 7 byte footer, outputs numerically

```
U+O[]]E.U)UP:R-OU^[U]ODONE.

```

### Footer:

```
UODONOE

```

This one doesn't score as well, but overall it is much shorter and actually outputs numerically rather than with debug messages, so I thought it'd be worth including here.

Try It Online!, Try It Online!x2, Try It Online!x3, Try It Online!x4, Try It Online!x5, Try It Online!x6

### Explanation:

Overall strategy: iterate through all of the even code blocks to count how many copies there are, ending up at the footer, which then uses this count to initialize a loop on code block 1 which just gets fib(n) in a normal way. I want to believe it's possible to have something similar to this with no header/footer, but I don't have any ideas for that yet.

```
U+O[]]E.  code block 0 (and 2, and 4...)
U+O       if i exists, i++, else let i = 1
   []]E   go to code block 2*i
       .  end code block

UODONOE  code block 2*(number of copies + 1)
UO       save i on the queue
  DO     a=0
    NO   b=1
      E  go to code block b (1)

U)UP:R-OU^[U]ODONE.  code block 1
U)  :           NE   while(i){
     R-O               i--
        U^             r1 = a
          [            r2 = a
           U]O          a = b + r2
              DO        b = r1
                NE   } (go to code block 1)
  UP                 print a
                  .  end code block

```

# Answer
> 4 votes
# Backhand, 9 bytes

```
~+~:rO!:@

```

Try it online!

Try it online! (x6)

Backhand's IP jumps by three cells by default, bouncing off at edges. This code makes use of this property to the max. Since the length of the base program is a multiple of 3, any amount of repetition will run as follows:

```
~  :  !  ~  :  !   ...    (forward) set up the initial stack
 +  r  :  +  r  :  ...    (backward) compute Fibonacci
  ~  O  @                 (forward) print the number and halt

set up the initial stack:
~    pop off one element; no op on first iteration
:    dup; pushes two zeros on first iteration
!    not; change the top zero to one
~    pop off one
:    dup 0
!    not to make it 1
...

compute Fibonacci: [a b]
:    dup [a b b]
r    reverse stack [b b a]
+    add [b a+b]

print and halt:
~    pop off b
O    print a as num
@    halt

```

# Answer
> 4 votes
# Haskell, 30 bytes, 0 bytes header, 0 bytes footer

```
q=0:scanl(+)1q;f=(q!!)$0
 +1--

```

Attempt This Online!

# Haskell, 44 bytes, 0 bytes header, 0 bytes footer, no comments

```
f where q=(0,1);qf@(f,g)=(g,f+g)where(f,g)=q

```

Attempt This Online!

# Answer
> 4 votes
# Labyrinth, 14 bytes

```
 #
-(
:
=+{!@

```

Try it online!

Try it online! (6x)

The "repeat the source" requirement is extremely hard in Labyrinth (maybe easier than Hexagony, where it can be rightout impossible, but still), especially to golf it down, mainly due to the IP routing across source boundaries.

I experimented with many layouts for two full days, only to find that the second simplest layout can be golfed by 1 byte (the simplest being the one below).

```
 #        #    push stack height [0 | ]
-(        (-   decrement and subtract from below [1 | ] (implicit zeros are used)
:         :=+  duplicate, swap the tops of two stacks, add [1 | 1]
=+{!@          (one step of fibonacci)
 #        the top is not zero, so turn right at the junction
-(        #(-  push stack height(1), decrement, subtract (becomes noop) [1 | 1]
:         so repeat running fibonacci until it hits the bottom row
=+{!@
 #
-(
:
=+{!@     {!@  print the previous fibonacci and exit

```

# Labyrinth, 15 bytes

```
:1
;
:
=
+
_=!@

```

Try it online!

Try it online! (6x)

The "simplest layout" that uses `_` "push 0" at the junction to skip to the next iteration.

# Answer
> 4 votes
# Jelly, 5 bytes

```
ṛ$‘ÆḞ

```

Try it online!

A niladic link that as shown outputs 1 but when concatenated n times outputs the nth member of the Fibonacci sequence.

## Explanation (example for n = 2)

```
ṛ$‘ÆḞṛ$‘ÆḞ
ṛ$         | Within a monadic chain, right argument (will be zero)
  ‘        | Increment by 1
      $    | Following as a monad:
   ÆḞ      | - Member of the Fibonacci sequence
     ṛ     | - Right argument, restoring the original argument of this monadic chain
       ‘   | Increment by 1
        ÆḞ | Member of the Fibonacci sequence

```

# Answer
> 4 votes
# Fortran (GFortran), ~~77~~ 58 bytes body, ~~42~~ 13 bytes header and footer

```
!mandatory header
program x

!repeatable code
if(j<1)i=1;l=i;if(l>0)write(*,'(A)')('x',k=1,l);i=j;j=j+l

!mandatory footer
end

```

Output is unary and printed vertically. The code depends on the compiler to initialize local variables to zero, e.g. with `-finit-local-zero` for GFortran.

Try it online: 1x, 2x, 4x, 8x

# Answer
> 3 votes
# Pyth, 10 bytes (no header/footer)

```
eaYfgTs>2Y

```

Try it online!

2x 3x 4x 10x

```
              # implicitly assign Y=[]
   f          # find the lowest number starting at 1 for which lambda T is true
       >2Y    # the last two elements of Y
      s       # summed
    gT        # is less than or equal to T
 aY           # append to Y
e             # return the last element of Y

```

# Answer
> 3 votes
# Nim, 60 bytes (no header/footer, outputs in decimal)

```
var a,b=0;b=1;addQuitProc do{.noconv.}:echo a
(a,b)=(b,a+b)#

```

Attempt This Online!

## Without using comments, 82 bytes

Includes a trailing newline.

```
when not declared a:
 var a,b=0;b=1;addQuitProc do{.noconv.}:echo a
(a,b)=(b,a+b)

```

Attempt This Online!

## Unary output, 46 bytes

Port of loopy wait's Python answer.

```
var a,b="x";b=""
stdout.write a
(a,b)=(b,a&b)#

```

Attempt This Online!

# Answer
> 3 votes
# \>\<\>, 13 bytes

```
\\n;
1:
0@
 +

```

Try it online!

When repeated, it looks like this:

```
\\n;
1:
0@
 +\\n;
1:
0@
 +\\n;
1:
0@
 +

```

The first column sets up the stack, the second runs the Fibonacci loop, and the horizontal path prints and exits. Extra copies of `1 0`s are ignored.

# Answer
> 3 votes
# APL (Dyalog), 19 ~~29~~ bytes ~~1 byte~~ No header ~~and~~ or footer

```
⊃{⍬≡⍵:1⋄(+/2↑⍵),⍵}⍬

```

Try it on TryAPL.org!

Thanks to Bubbler for pointing out that the header and footer could be incorporated into the function

With a header/footer, the body could be significantly shorter, but that's counter to the metric of success.

# Answer
> 3 votes
# K (ngn/k), 13 bytes

```
 ://0,1+':*+0

```

Try it online!

There is a leading space. Similar strategy to my APL and J answers, but it was more tricky to find the equivalent for K.

Monadic `+` is "transpose". A scalar changes to a 1x1 matrix, and a list changes to a 1-row matrix. Then monadic `*` unwraps one layer to get a list in both cases.

`://` is "apply `:/` (rightmost element) until it converges". `0 ://` is "apply the same thing zero times", which is essentially a no-op.

# Answer
> 3 votes
# Lambda calculus (Ben Lynn's Nat), 46 bytes

```
(\n.n(\px.Sp(BxSB))K(KI)I)\f.(\l.SB(lf)f)\g.KI

```

Try it online! (Instructions: delete all the code there, copy the body n times and the footer on a single line, choose Nat, click Compile and then Run and see the Output.)

The observation that

> Just realized that codes like `I\f.f` (a trailing lambda abstraction, which puts the next iteration inside its body) are accepted. This may change the conclusion about zero padding.

was correct, and there was indeed a solution without any padding.

The solution above has a structure of

```
x \f. y \g. z

```

and has the following property:

```
(\f. y \g. z) == 1
(\f. y \g. z x \f. y \g. z) == 2
(\f. y \g. z x \f. y \g. z x \f. y \g. z) == 3
...

```

`z` was chosen to be `KI` so that we can ignore `x` and the equation to solve simply becomes

```
(\f. y \g. n) == succ n == SBn

```

which can be solved with `y = \l.SB(lf)f`. Then, `x` should be a function that takes `n` and outputs `n`th fibonacci number. This is solved using 2014MELO03's construction of iterating a pair.

---

# Lambda calculus (Ben Lynn's Nat), 39 bytes, 1 byte footer

```
(\a.a(\zbxf.f(a(SB)b)a)(\f.fI(KI)))(KI)

```

Footer:

```
K

```

Try it online! (Instructions: delete all the code there, copy the body n times and the footer on a single line, choose Nat, click Compile and then Run and see the Output.)

### How I got to this solution

First, ~~there is no solution without any header or footer~~. This is because:

* any lambda term would be in the structure of `x1 x2 .. xn`
* one copy must evaluate to 1 = `I`
* but then 2 copies of the code evaluates to `x1 x2 .. xn x1 x2 .. xn` = `I x1 x2 .. xn` = `x1 x2 .. xn` = `I`, which is true for any number of copies, and 1 is clearly not `fib(i)` for larger `i` (number of copies).

<sub>This logic is false due to the subtlety of the grammar of Nat. See the no-padding solution at the top.</sub>

Given this, I aimed to find a solution with a single combinator as the footer. I chose K because it fits particularly well here; specifically, if repetitions of `x1 x2 .. xn` evaluate to a pair, applying K on it extracts the first element. Then to simplify the problem, I assumed that `n = 2`, i.e. the repeating part is `f x` for some `f` and `x`. It can be an answer if it satisfies the following: (`(x, y)` refers to the Church pair of `x` and `y`.)

* `f x` evaluates to `(1, 0)`.
* `(a, b) f x` = `f a b x` evaluates to `(a+b, a)`.

Given that `a` in the second case is always a Church natural number ≥ 1, I decided to set `x` to zero (= `KI`). Then I can use a simple discriminator that returns `u` for 0 and `v` for 1 or greater:

```
0 (\z. v) u = u
a (\z. v) u = v -- when a >= 1

```

If the first argument is 0, we need to return `(1, 0)`, so `u = \f. f I (KI)`. Otherwise we take two more arguments `b` and `x`, ignore `x`, and construct a new pair `\f. f (a succ b) a`. This completes the construction of the answer above.

About choosing the interpreter and the LC language: I initially wanted to compile this to SKI calculus, but I didn't have a good one, and the three copies of `a` in a single lambda would surely make a mess. So I reached out for a regular LC interpreter instead, and found Nat. After getting some syntax errors (I was trying to use `s` for a function name), I realized that it does support SKIBC combinators out of the box, so I went with it.

# Answer
> 3 votes
# Uiua, 16 bytes, no header/footer

```
&pf;⍥⊃⊂∘tag"""1"

```

Outputs in unary. Try it online! x3 (outputs 11) x6 (outputs 11111111)

Since Uiua prints the entire stack at the end of execution and there is no straightforward way to exit the program in the middle, I decided to print in unary so I can just accumulate all the outputs across iterations. A similar approach was done in my Cascade no-padding answer.

`tag` (a niladic function that initially evaluates to 0 and is incremented each time it is called) acts as the counter in other answers, allowing to generate the n-th term of the delayed Fibonacci sequence `1, 0, 1, 1, 2, 3, ...`, whose cumulative sum is the Fibonacci sequence itself.

```
&pf;⍥⊃⊂∘tag"""1"
    ⍥⊃⊂∘tag"""1"  delayed Fibonacci generator:
              """1"   initial two terms 1 and 0 in unary
    ⍥     tag        repeat n times: (n = 0, 1, ..., repetition - 1)
      ⊃⊂∘           change [b a] with [b+a b] in unary
   ;               discard the next term
&pf                print without newline

```

# Answer
> 2 votes
# Python, ~~44~~ ~~40~~ 35 bytes (no header or footer)

*-5 bytes, thanks to @CursorCoercer*

simplified version of example code

```
a=1;b=0
print(end=a*"x")
a,b=b,a+b#

```

Attempt This Online!

2x, 3x, 4x

first few values

# Python, 11 bytes body, 15 bytes header+footer

the trivial python solution

```
a,b=0,1

a,b=b,a+b

print(a)

```

Attempt This Online!

2x:

```
a,b=0,1
a,b=b,a+b

a,b=b,a+b
print(a)

```

Attempt This Online!

3x:

```
a,b=0,1
a,b=b,a+b

a,b=b,a+b

a,b=b,a+b
print(a)

```

Attempt This Online!

# Answer
> 2 votes
# Charcoal, 14 bytes

```
ＰＩ⌈⊞Ｏυ∨¬υΣ✂υ±²

```

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

```
        υ       Predefined empty list
       ¬        Is empty
      ∨         Logical Or
           υ    Predefined empty list
          ✂     Sliced from
             ²  Literal integer `2`
            ±   Count back from the end
         Σ      Take the sum
   ⊞Ｏ           Push to
     υ          Predefined empty list
  ⌈             Take the maximum (i.e. the entry just added)
 Ｉ              Cast to string
Ｐ               Overwrite without moving the cursor

```

Try it online! Link is to 10 repetitions of the succinct code.

# Answer
> 2 votes
# Go, 55 bytes (2 bytes footer)

```
import."fmt";func f(){a:="x";b:=""
Print(a);a,b=b,a+b//

```

```
}

```

Try it online!
Try it online! x2
Try it online! x3
Try it online! x4

## Go, 30 bytes (8 bytes footer)

```
func()(b int){a:=1
a,b=b,a+b//

```

```
return}

```

Try it online!
Try it online! x2
Try it online! x3
Try it online! x4

*-16 thanks to @JoKing*

# Answer
> 2 votes
# C++ (gcc), 143 125 bytes

-18 bytes thanks to @ceilingcat

Explanation: it uses the constructor of a class to do the Fibonacci increment operation, and then sets up a variable number of global instances of that class to be initialized before `main`. The catch being that all those variables have to be named differently, and there's a bit of preprocessor magic needed to get the `__LINE__` macro combined into the variable names.

```
int m,n=1;struct A{A(){m+=n;n=m-n;}};int main(){__builtin_printf("%d",m);}
#define Y(x)A a##x;
#define X(x)Y(x)
X(__LINE__)//

```

Try it online!

# Answer
> 2 votes
# Befunge-98 (PyFunge), 16 bytes

```
#q_1\\:01p+01g5j

```

Try it online once

Try it online twice

Try it online three times

Try it online five times

Try it online ten times

## Explanation

This outputs the result as an exit code. Most operating systems only show the least significant byte of this number (mod 256 on TIO), but as per the Funge spec, it's returning the full number. It would add a couple of bytes to print to stdout.

Below f1, f2 and f3 are three consecutive Fibonacci numbers.

```
Only run on first and last "loop":

#q_                 Quit with 2nd on stack as exit code if top of stack is non-zero.
   1\               Push 1, swap with 2nd on stack (implicitly 0).

The main "loop", entering with f1 on top and f2 below:

     \              Swap top 2 of stack, f2 now on top.
      :             Duplicate f2.
       01p          Store f2 at (0,1) in funge space.
          +         Add f1 and f2 to get f3.
           01g      Get f2 from (0,1) in funge space.
              5j    Skip the next 5 instructions.

```

`#q_1\` is skipped for all copies of the code except the first. On the first one, the stack is empty (top of stack implicitly 0), so it continues to the right. At the end of the last copy, 5j just skips 5 whitespace and runs the first copy again, this time with the second-highest number generated on top (non-zero).

# Answer
> 2 votes
# Haskell, 27 bytes body, 7 bytes footer

```
g=f!!1;f=[f!!1,sum f]where f=[0,1]

```

The last 7 bytes (`f=[0,1]`) is the footer.

Attempt This Online

# Answer
> 2 votes
# POSIX sh: (Dash, Bash, Zsh), <sup>~~42 36~~</sup> 32 bytes (0 bytes header/footer)

***-6 bytes** by switching to unary, **-4 bytes** by swapping `n` and `n-1` to remove an `${empty-"fallback"}`*

```
set $1$2 ${1-1}
trap echo\ $1 0

```

Try it online! ~~Try it online! Try it online!~~

Zsh can **save 1 byte** by using `trap '<<<$1' 0`.

## Explanation:

`${var-string}` substitutes `"string"` if `$var` is unset. On the first loop, `$1$2` is elided, so the *first* positional argument is set by `${1-1}`, which triggers its the unset-fallback to `1`. On each subsequent loop, the first argument is a concatenation of the two, and the second argument is the first argument from the previous iteration.

We use `trap [snippet] 0` to only output upon EXIT.

# Answer
> 2 votes
# APL(Dyalog Unicode), 11 bytes <sup>SBCS</sup>

```
⊃1,⍨2+/0,⍨⍬

```

Try it on APLgolf!

Inspired by boltcapt's answer. This constructs a list of fibonacci numbers in reverse, starting from empty list , and outputs the first element . When the program is repeated, `⍬⊃` returns the whole array on the right side unchanged.

```
1,⍨2+/0,⍨   when the current list contains f_n, f_{n-1}, ..., f_1
             (e.g. n=5: [5 3 2 1 1])
0,⍨  append 0 [5 3 2 1 1 0]  (f_n, f_{n-1}, ..., f_1, f_0)
2+/  pairwise sum [8 5 3 2 1]  (f_{n+1}, f_n, ..., f_2)
1,⍨  append 1 [8 5 3 2 1 1]  (f_{n+1}, f_n, ..., f_1)

```

# Answer
> 2 votes
# , 11 bytes

```
]/0 1,2+/\0

```

Attempt This Online!

Similar to my APL solution. The fibonacci generator is the same, except that the list is now in increasing order. `]/y` returns the rightmost element of `y`, but `x]/y` returns `y` unmodified.

`x (f"a b)/ y` evaluates the cartesian product of `a`-cells of `x` and `b`-cells of `y`. `]` has default rank of infinity on both sides, so `x (]"_ _)/ y` takes whole `x` on the left and whole `y` on the right, and returns an array containing the single item `x ] y`, which is `y`.

# Answer
> 1 votes
# sclin, 23 bytes

```
0 1.
tuck dup n>o +2@~

```

Try it here! Has a trailing newline.

Example:

```
0 1.
tuck dup n>o +2@~
0 1.
tuck dup n>o +2@~
0 1.
tuck dup n>o +2@~

```

## Explanation

* `0 1` initial conditions
* `tuck dup n>o` store, output term
* `+` add
* `2@~` execute second line down (i.e. skip next line)

Pleasantly surprised that the line-based mechanics of sclin came in handy this time.

---
Tags: code-challenge, source-layout, fibonacci
---


# Question
Title: Find the largest sum such that no two elements are touching
*Inspired by this (off topic) post*

Given an array of numbers, find the largest sum over a subarray not containing two adjacent elements

```
[1,2,3,4]         -> 6   // [_,2,_,4]
[1,2,3,4,5]       -> 9   // [1,_,3,_,5]
[2,2,1,1,2,1,1,2] -> 7   // [2,_,1,_,2,_,_,2]
[3,1,4,1,5,9,2]   -> 16  // [3,_,4,_,_,9,_]
[9,8,7,9,9,8]     -> 26  // [9,_,_,9,_,8]
[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,1,1,1,1,1,1,1,1,1,1,1,1] -> 21

```

## Rules

* You can assume that all number in the array are positive integers
* This is the shortest solution wins

*Optional additional requirement:*

* Your solution has to run in **polynomial time** (\\$O(n^k)\\$ for some integer k)

# Answer
> 24 votes
# Ruby, ~~46~~ 38 bytes

```
->l{a=b=0;l.map{a,b=b,[a+_1,b].max};b}

```

Attempt This Online! Runs in O(n).

### How?

We need 2 accumulators. The first 2 steps will initialize them with the first 2 elements of the list. Then at every step: add the current element to the accumulator that was not increased in the previous step, and discard the smallest.

### Example:

```
[3,1,4,1,5,9,2]
Start -> a=0, b=0
3     -> a=0, b=3
1     -> a=3, b=1
4     -> a=3, b=[3+_+4]
1     -> a=[3+_+4], b=[3+_+_+1]
5     -> a=[3+_+4], b=[3+_+4+_+5]
9     -> a=[3+_+4+_+5], b=[3+_+4+_+_+9]
2     -> a=[3+_+4+_+_+9], b=[3+_+4+_+5+_+2]

```

Thnks @tsh for -6 bytes

# Answer
> 10 votes
# Haskell, ~~38~~ 35 bytes

```
g(x:y:r)=max(g$y:r)$x+g r
g x=sum x

```

Attempt This Online!

`g x=sum x` is a handy way to combine the two base cases `g[x]=x` and `g[]=0`.

---

# Haskell, \\$O(n)\\$, ~~42~~ 38 bytes

```
fst.foldr(\a(b,c)->(max(a+c)b,b))(0,0)

```

Attempt This Online!

Based on G B's Ruby answer. -4 bytes thanks to regr4444!

# Answer
> 8 votes
# , ~~80~~ ~~46~~ 43 bytes

*Edit: hugely golfed with inspiration from G B's answer: upvote that!*

```
\(x)max(Reduce(\(a,i)c(max(a),a[1]+i),x,0))

```

Attempt This Online!

Runs in polynomial time.

# Answer
> 7 votes
# 05AB1E, ~~11~~ 8 bytes

```
ÎĆvMsy+s

```

-3 bytes and \\$O(n)\\$ complexity by porting *@G B*'s Ruby answer, so make sure to upvote that answer as well!

Try it online or verify all test cases.

**Explanation:**

```
Î        # Push 0 and the input-list
 Ć       # Enclose; append the first item at the end of the input-list
         # (this is to have an extra iteration, the value that's appended is irrelevant)
  v      # Pop and loop over each item `y` of this modified input-list:
   M     #  Push a copy of the stack's maximum
    s    #  Swap so the previous value (or 0 in the first iteration) is at the top again
     y+  #  Add the current loop-integer `y` to it
       s #  Swap back to the pushed maximum for the next iteration
         # (after the loop, the maximum of the extra iteration is output implicitly)

```

# Answer
> 5 votes
# Befunge-98 (PyFunge), 35 ~~52~~ ~~60~~ ~~67~~ bytes

```
1pp>1g00g`g3j>;#&00g+01p00p'#j<;.@

```

Try it online!
Takes input as a series of space separated integers. The last integer must have a trailing space.

Uses the dynamic programming approach, and so runs in O(n).

### Alternate version with only printable characters, 36 bytes

```
1pp>1g00g`g3j>;#&00g+01p00p93*#j<;.@

```

Try it online!
Same as above but replaces the unprintable character with 9\*3=27, costing an extra byte (which is why it is not 26)

## Explanation

Here the unprintable character has been replaced by `O`. Note that the unprintable character has ASCII value of 26

```
1pp>1g00g`g3j>;#&00g+01p00p'O#j<;.@  Full program
1p                                   0 is always on the stack, so 1p stores 0
                                     at (0,1)
  p                                  stores 0 at (0,0)
   >         >;#&          'O#j<;.@  Loop until EOF received
    1g00g                            Get (0,1) and put on stack, then get
                                     (0,0) and put on stack
         `                           Pop b, then a, push 1 if a>b, otherwise
                                     push 0
          g                          Stack now either contains 1 or 0, which
                                     corresponds to one of the stored values,
                                     get that value
           3j>;#&               ;.@  Jump to &, which gets one integer input.
                                     If EOF, print top of the stack, then end
                                     Otherwise if continuing loop:
                 00g+                Get (0,0) then add top two values of
                                     the stack
                     01p00p          Pop the top of the stack and store at
                                     (0,1), then get the top of the stack
                                     again and store at (0,0)
                           'O#j<     Jump 26 characters back to the start of
                                     the loop

```

# Answer
> 4 votes
# JavaScript (ES6), 43 bytes

Port of GB's answer, running in \\$O(n)\\$.

```
a=>[...a,b=0].map(v=>[b,a]=[a>b?a:b,b+v])|b

```

Try it online!

---

# JavaScript (ES6), 44 bytes

This one runs in \\$O(2^n)\\$.

```
f=([v,...a],p)=>x=v?p|(v+=f(a,1))<f(a)?x:v:0

```

Try it online!

### Commented

```
f = (        // f is a recursive function taking:
  [v,        //   v = next value from the input array
      ...a], //   a[] = remaining values
  p          //   p = flag set if the previous value was used
) =>         //
x =          // save the result in x
v ?          // if v is defined:
  p | (      //   if p is set
    v +=     //   or the updated value of v obtained by adding
    f(a, 1)  //   the result of a recursive call with p set
  ) < f(a) ? //   is less than f(a):
    x        //     use x (the result of f(a))
  :          //   else:
    v        //     use v
:            // else:
  0          //   stop

```

# Answer
> 4 votes
# Uiua, 8 bytes

```
↥∧⊃⋅+↥.0

```

Try it online!

```
↥∧⊃⋅+↥.0    input: a vector V of numbers
       .0    set up two accumulators:
               maximum containing the last element (Mc),
               maximum not containing the last element (Mn)
 ∧          fold over V: for each item Vi,
   ⊃⋅+↥        replace [Mc Mn Vi] with [Mn+Vi max(Mc,Mn)]:
     ⋅+           discard Mc and add Mn and Vi (arity 3)
       ↥          max of Mc and Mn (arity 2)
   ⊃             fork: take 3 values and pass enough amount of args to each function
↥             max of final Mc and Mn

```

# Answer
> 3 votes
# Vyxal `G`, 59 bitsv2, 7.375 bytes

```
ẏṗ'¯‹g;İṠ

```

Try it Online!

Probably doesn't meet the criteria of running in polynomial time.

## Explained

```
ẏṗ'¯‹g;İṠ
ẏṗ'   ;    # Keep items of the powerser of range(0, len(input)) where:
     g     #  The minimum
   ¯‹      #   Of deltas - 1 isn't 0
# Essentially, this finds all sets without consecutive items, as consecutive items will have a forwards difference of 1, which is 0 when decremented.
# This works regardless of input because it's operating on the list of indices, not actual values
       İ   # Index into the input list
        Ṡ  # And sum each
# The G flag outputs the biggest sum

```

Created with the help of Luminespire.

# Answer
> 3 votes
# Charcoal, 21 bytes

```
Ｆ²⊞υ⁰ＦＡ≔⟦⁺ι§υ¹⌈υ⟧υＩ⌈υ

```

Try it online! Link is to verbose version of code. Explanation: Port of @GB's Ruby answer.

```
Ｆ²⊞υ⁰

```

Start with an accumulator of two zeros.

```
ＦＡ

```

Loop over the input.

```
≔⟦⁺ι§υ¹⌈υ⟧υ

```

Update the accumulators.

```
Ｉ⌈υ

```

Output the best sum.

# Answer
> 3 votes
# Scala 3, 69 bytes

```
l=>{val(a,b)=l.foldLeft((0,0)){case((a,b),c)=>(a max b,a+c)};a max b}

```

Attempt This Online!

# Answer
> 3 votes
# JavaScript (Node.js), 39 bytes

```
a=>a.map(v=>q=(v+=p)>(p=q)?v:p,p=q=0)|q

```

Try it online!

Use two variables `p`, and `q` to track:

* `p`: Largest sum we got for `a[0..i-1]`
* `q`: Largest sum we got for `a[0..i]`

So, for each iteration,

* `i' = i + 1`
* `p' = q`
* `q' = max(q, p + a[i'])`

# Answer
> 3 votes
# Java, ~~64~~ 57 bytes

```
a->{int t=0,r=0;for(int k:a)r=(k+=t)>(t=r)?k:t;return r;}

```

Another port of *@G B*'s Ruby answer.
Also runs in \\$O(n)\\$ complexity.

Try it online.

**Explanation:**

```
a->{                    // Method with integer-array parameter and integer return-type
  int t=0,              //  Temp-integer, starting at 0
      r=0;              //  Result-integer, starting at 0 as well
  for(int k:a)          //  Loop over the integers `k` of the input-array:
    r=(k+=t)>(t=r)?k:t;
  //  (k+=t)            //   First increase the current `k` by value `t`
  //         (t=r)      //   Then replace `t` with value `r`
  //r= k    > t   ?k:t; //   And then set `r` to the maximum of these new `k` and `t` as
                        //   preparation for the next iteration
  return r;}            //  After the loop, return the final 'prepared' maximum `r`

```

# Answer
> 3 votes
# Python, 48 bytes

```
lambda a,b=0,c=0:max(b:=max(d+c,c:=b)for d in a)

```

Attempt This Online!

\\$O(n)\\$ complexity.

Loops over the list. On each prefix, `b` and `c` are the largest such sums of the two previous prefixes.

# Answer
> 2 votes
# Retina 0.8.2, 41 bytes

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

```

Try it online! Takes input on separate lines but link is to test suite that splits on commas for convenience. Explanation: Another port of @GB's Ruby answer.

```
.+
$*

```

Convert to unary.

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

```

Add the first element to the third and keep the larger of the first and second elements.

```
O^`

```

Sort descending.

```
\G1

```

Convert the larger of the remaining two numbers to decimal.

# Answer
> 2 votes
# Nibbles, 9.5 bytes (19 nibbles)

```
`//$`,1:`/@]+/@$$]

```

Attempt This Online!

Runs in polynomial time.
Direct port of my R answer, which is itself inspired by G B's answer.

```
  /                 # fold from right
   $                # over the input,
    `,1             # starting with a list of only [0]:
       :            #   join
        /@]         #     maximum in the result-list-so-far
                    #   to
            /@$     #     first entry of the result-list-so-far
           +   $    #     plus the current element
`/              ]   # and output get the maximum in the final result-list

```

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

```
x=>x.map(e=(t,i)=>e=x[i]=(t+=~~x[i-2])<e?e:t)|e

```

Try it online!

# Answer
> 2 votes
# C (clang), \\$\mathcal{O}(N)\\$, 53 bytes

takes in a zero-terminated array of positive integers and returns via out parameter.

```
n,t;f(*a,*r){for(*r=n=0;*a;(n=*r)<t?*r=t:0)t=n+*a++;}

```

Try it online!

---

# C (gcc), \\$\mathcal{O}(N)\\$, 46 bytes

This one returns the result in the first element of the array, has UB in the form of unsequenced modification and access to `a[2]` and requires the last two elements of the array to be \\$0\\$.

```
f(int*a){*a=*a?f(a+1)<a[2]+*a?a[2]+*a:a[1]:0;}

```

Try it online!

# Answer
> 2 votes
# Python, 55 bytes

```
f=lambda a,b,c,*d:d and f(max(a,b),a+c,*d)or max(a+c,b)

```

Attempt This Online!

Adapted from G B's answer. It only works if the array is at least three elements long.

# Answer
> 1 votes
# Erlang, 77 bytes

```
f(L)->f(L,{0,0}).
f([],{A,B})->max(A,B);
f([H|T],{A,B})->f(T,{max(A,B),A+H}).

```

Attempt This Online!

# Answer
> 1 votes
# Elixir, 80 bytes

```
def f(l)do
{a,b}=Enum.reduce(l,{0,0},fn x,{a,b}->{max(a,b),a+x}end)
max(a,b)
end

```

Attempt This Online!

# Answer
> 1 votes
# Racket, 99 bytes

Golfed version. Try it online!

```
(define (f l)(let loop([l l][a 0][b 0])(if (null? l)(max a b)(loop(cdr l)(max a b)(+ a (car l))))))

```

Ungolfed version. Try it online!

```
#lang racket

(define (max_sum lst)
  (let loop ([lst lst] [a 0] [b 0])
    (if (null? lst)
        (max a b)
        (loop (cdr lst) (max a b) (+ a (car lst))))))

(define (main)
  (displayln (max_sum '(1 2 3 4)))
  (displayln (max_sum '(1 2 3 4 5)))
  (displayln (max_sum '(2 2 1 1 2 1 1 2)))
  (displayln (max_sum '(3 1 4 1 5 9 2)))
  (displayln (max_sum '(9 8 7 9 9 8))))

(main)

```

# Answer
> 1 votes
# Rust, 90 bytes

Golfed version. Try it online!

```
fn s(a:Vec<i32>)->i32{let(x,y)=a.into_iter().fold((0,0),|(x,y),z|(x.max(y),x+z));x.max(y)}

```

Ungolfed version. Try it online!

```
fn main() {
    println!("{}", max_sum(vec![1,2,3,4]));
    println!("{}", max_sum(vec![1,2,3,4,5]));
    println!("{}", max_sum(vec![2,2,1,1,2,1,1,2]));
    println!("{}", max_sum(vec![3,1,4,1,5,9,2]));
    println!("{}", max_sum(vec![9,8,7,9,9,8]));
}

fn max_sum(arr: Vec<i32>) -> i32 {
    let (a, b) = arr.into_iter().fold((0, 0), |(a, b), c| (std::cmp::max(a, b), a + c));
    std::cmp::max(a, b)
}

```

# Answer
> 0 votes
# OCaml, 104 bytes

Golfed version. Try it online!

```
let rec m l=match l with []->0|x::xs->let(a,b)=List.fold_left(fun(a,b)x->(max a b,a+x))(0,0)l in max a b

```

Ungolfed version. Try it online!

```
let rec max_sum lst =
  let rec helper (a, b) = function
    | [] -> max a b
    | h::t -> helper (max a b, a + h) t
  in helper (0, 0) lst

let () =
  print_endline (string_of_int (max_sum [1; 2; 3; 4]));
  print_endline (string_of_int (max_sum [1; 2; 3; 4; 5]));
  print_endline (string_of_int (max_sum [2; 2; 1; 1; 2; 1; 1; 2]));
  print_endline (string_of_int (max_sum [3; 1; 4; 1; 5; 9; 2]));
  print_endline (string_of_int (max_sum [9; 8; 7; 9; 9; 8]));

```

---
Tags: code-golf, array
---


title: Expand Emmet HTML Abbreviations

text:
# Question
Title: Expand Emmet HTML Abbreviations
Emmet is a text-editor and IDE plugin for writing HTML code using much fewer keypresses. You might think of it like a code-golfing HTML preprocessor. Its syntax is based on CSS selectors.

Your challenge is to an implementation of Emmet. Given some Emmet code, output the resulting HTML.

Note that for the purposes of this challenge, you will not have to handle element "shortcuts" like `bq``blockquote` or `a``a[href]`. This version of Emmet does not support item numbering. You also do not need to handle the difference between block and inline elements having different spacing.

All elements should have at least one whitespace character (space, tab, newline, whatever) wherever whitespace is shown here, but you don't need to have the indentation shown in the examples.

# Syntax

<sup>(Paraphrased from Emmet's documentation)</sup>

Emmet basically just describes an HTML document using syntax similar to CSS selectors. It uses symbols to describe where each element should be placed in the document.

### Structure operators

* Child: `>`

```
div>ul>li
<div>
  <ul>
    <li></li>
  </ul>
</div>

```
* Sibling: `+`

```
div+p+blockquote
<div></div>
<p></p>
<blockquote></blockquote>

```
* Put them together:

```
div+div>p>span+em
<div></div>
<div>
  <p>
    <span></span>
    <em></em>
  </p>
</div>

```
* Climb-up: `^`

```
div+div>p>span+em^blockquote
<div></div>
<div>
  <p>
    <span></span>
    <em></em>
  </p>
  <blockquote></blockquote>
</div>

```

```
div+div>p>span+em^^blockquote
<div></div>
<div>
  <p>
    <span></span>
    <em></em>
  </p>
</div>
<blockquote></blockquote>

```
* Multiplication: `*`

```
ul>li*5
<ul>
  <li></li>
  <li></li>
  <li></li>
  <li></li>
  <li></li>
</ul>

```

```
p>span*2+a
<p>
  <span></span>
  <span></span>
  <a></a>
</p>`

```

```
p>span*2^q
<p>
  <span></span>
  <span></span>
</p>
<q></q>

```
* Grouping: `()`

```
div>(header>ul>li*2>a)+footer>p
<div>
  <header>
    <ul>
      <li>
        <a></a>
      </li>
      <li>
        <a></a>
      </li>
    </ul>
  </header>
  <footer>
    <p></p>
  </footer>
</div>

```

### Attribute operators

* ID `#` and class `.`

```
div#header+div.page+div#footer.class1.class2.class3
<div id="header"></div>
<div class="page"></div>
<div id="footer" class="class1 class2 class3"></div>

```
* Custom attributes `[attr]`

```
td[title="Hello world!" colspan=3]
<td title="Hello world!" colspan="3"></td>

```

```
td[title=hello colspan=3]
<td title="hello" colspan="3"></td>

```

```
td[title colspan]
<td title="" colspan=""></td>

```

### Text

Put text in curly braces:

```
p{Hello, World!}
<p>Hello, World!</p>

```

```
a.important[href="https://www.youtube.com/watch?v=dQw4w9WgXcQ"]{click}
<a
  class="important"
  href="https://www.youtube.com/watch?v=dQw4w9WgXcQ"
>
  click
</a>

```

```
a[href]{click}+b{here}
<a href="">click</a>
<b>here</b>

```

```
a[href]>{click}+b{here}
<a href="">
  click
  <b>
    here
  </b>
</a>

```

```
p>{Click}+button{here}+{to continue}
<p>
  Click
  <button>
    here
  </button>
  to continue
</p>

```

```
p{(a+b)*c>a+b*c}
<p>{(a+b)*c>a+b*c}</p>

```

# Additional test cases

```
div>p[block]*2>{abc}+span*2{123}+{def}
<div>
  <p block="">
    abc
    <span>123</span>
    <span>123</span>
    def
  </p>
</div>

```

```
a[href="https://example.com/index.html?a[]={1}&a[]={2}"]{This is an example usage of array parameters "a[]" in url.}
<a href="https://example.com/index.html?a[]={1}&a[]={2}">
  This is an example usage of array parameters "a[]" in url.
</a>

```

---

Your program should give proper output for all of the examples outlined above. This is , so the shortest code per language, measured in bytes, wins!

# Answer
> 4 votes
# Retina, 465 bytes

```
\^+
$&+
+`([^>]+>((\()|(?<-3>\))|(?(3)>)|[^()>])+(?(3)^))\^
($1)
\)|$
/$&
{%`^( *[^()>+]+)\*(\d+)(.*)
$2*$($1$3¶)
G`.
%`^(( *)((\()|(?<-4>\))|(?(4)[>+])|[^()>+])+(?(4)^))\+
$1/¶$2
%`^( *)(((\()|(?<-4>\))|(?(4)[>+])|[^()>+])+(?(4)^))\>(.+)
$1$2¶  $1$5¶$1/$2
)%`^( *)\((.+)\)/$
$1$2
%`^( *)((/|())\w+)(.*?)(/)?$
$1<$2>$#4*$5$#6*$(</$2>
>#(\w+)
 id="$1">
+`>\.(\w+)
 class="$1">
+`(class=".+)" class="
$1
]
 ]
+`>\[(\w+)(="([^"]*)"|=([^ ]*))?
 $1="$3$4">[
[]{[]|}/?

```

Try it online! Link includes test cases. Explanation:

```
\^+
$&+

```

Add a `+` after any `^`s.

```
+`([^>]+>((\()|(?<-3>\))|(?(3)>)|[^()>])+(?(3)^))\^
($1)

```

Convert `^`s into the equivalent brackets.

```
\)|$
/$&

```

Innermost elements should be on a single line.

```
{`
)`

```

Process as much as possible.

```
%`^( *[^()>+]+)\*(\d+)(.*)
$2*$($1$3¶)
G`.

```

Process multiplications.

```
%`^(( *)((\()|(?<-4>\))|(?(4)[>+])|[^()>+])+(?(4)^))\+
$1/¶$2

```

Process siblings.

```
%`^( *)(((\()|(?<-4>\))|(?(4)[>+])|[^()>+])+(?(4)^))\>(.+)
$1$2¶  $1$5¶$1/$2

```

Process children, appending a closing tag after them.

```
%`^( *)\((.+)\)/$
$1$2

```

Unwrap lines starting and ending in brackets.

```
%`^( *)((/|())\w+)(.*?)(/)?$
$1<$2>$#4*$5$#6*$(</$2>

```

Surround tags with `<>`s, removing attributes from closing tags, and add closing tags for single-line tags.

```
>#(\w+)
 id="$1">

```

Process ids.

```
+`>\.(\w+)
 class="$1">
+`(class=".+)" class="
$1

```

Process classes.

```
]
 ]
+`>\[(\w+)(="([^"]*)"|=([^ ]*))?
 $1="$3$4">[

```

Process attributes. I can do this on one line but it turns out to be a byte longer.

```
[]{[]|}/?

```

Remove the remaining syntax.

# Answer
> 3 votes
# Python3, 1152 bytes:

```
import re
R=re.findall
def U(t):
 [N]=R('^\w+',t);n='<'+N
 if(i:=R('(?<=#)\w+',t)):n+=f' id="{i[0]}"'
 if(c:=R('(?<=\.)\w+',t)):n+=' class="'+' '.join(c)+'"'
 if(a:=R('(?<=\[)[^\]]+',t)):n+=' '+' '.join(i+'=""'if'='not in i else re.sub('(?<=\=)[^"]+',lambda x:f'"{x.group()}"',i)for i in R('(?:\w+\="[^"]+")+|(?:\w+\=[^\s\]]+)+|\w+',a[0]))
 e=''
 if(o:=re.findall('(?<=\{)[^\}]+',t)):e=o[0]+' '
 return n+'>'+e,f'</{N}>'
F=lambda t,I:t if type(t)==list else '  '*I+''.join(U(t))
def f(s,I,c,l):
 if'('==s[0]:s.pop(0);t=[];f(s,I+1,t,[]);s.insert(0,t);
 t=s.pop(0)
 if')'!=t:
  if[]!=s:
   S=s.pop(0)
   if')'==S:c.append('  '*I+f'<{t}></{t}>')
   if'>'==S:Q,W=U(t);C=[];c.append(T:=['  '*I+Q,C,'  '*I+W]);l.append(T);f(s,I+1,C,l)
   if'+'==S:C=[];f(s,I,C,l);c.append(F(t,I));c.extend(C)
   if'^'==S[0]:c.append(F(t,I));C=[];f(s,len(l)-len(S),C,l);l[-len(S)].extend(C)
   if'*'==S:x=s.pop(0);s.insert(0,t);C=[];f(s,I,C,l);c.extend(T:=[C for _ in range(int(x))])
  else:Q,W=U(t);c.append('  '*I+Q+W)
P=lambda x:'\n'.join(i if type(i)==str else P(i)for i in x)
def M(s):S=R('\>|\+|\*|\+|\^+|\(|\)|[^(?:\>\+\*\+\^\(\))]+',s);l,c=[],[];f(S,0,c,l);return P(c)

```

Try it online!

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

```
i=>(s=i.match(/\w+|"[^"]*"|\{[^}]*\}|\S/g),S=_=>L=s.shift()||"",U=_=>s.unshift(L)&&"",T=v=>S()==v?' ':U(),D=c=>T`#`?' id='+S()+D(c):T`.`?D(c+(c&&' ')+S()):T`[`?A()+D(c):c&&` class="${c}"`,A=_=>T`]`?'':' '+S()+(T`=`?L+S():'=""')+A(),W=_=>S()[0]=="{"?L.slice(1,-1):U(),P=(r='',l=W()||(T`(`?P()+T`)`:T`^`?U():(r=`</${S()}> `,` <${L}${D('')}>`+W())))=>Array(T`*`?-~S():2).join(l+W()+(T`>`&&P()+(T`^`&&U(L='+')))+r)+(T`+`&&P()))()

```

Try it online!

Following commented code based on a previous version:

```
i=>(
  // tokenize the input
  //   <word>: \w+
  //   <string>: "[^"]*"
  //   <text>: \{[^}]*\}
  //   other operator: \S
  s=i.match(/\w+|"[^"]*"|\{[^}]*\}|\S/g),
  // parse the input
  P())
// Get first token, the token is consumed
S=_=>L=s.shift()||""
// Undo last get, the token is placed back
U=_=>s.unshift(L)&&""
// Test if next token is given value
// Consume the token and return truthy whitespace string if match
// Or return falsy empty string if not match
T=v=>S()==v?' ':U()
// P (whole program) ::= V "+" P | V ">" P (lookahead != "^") | V ">" P "^" P | <empty>
// V (an HTML tag) ::= <text> | "(" P ")" | <word> D | V "*" <word>
P=(
  // right part
  r='',
  // left part
  l=
    W()|| // V -> <text>
    (T`(`?P()+T`)`: // V -> "(" P ")"
     T`^`?U(): // reduce
     (r=`</${S()}> `,` <${L}${D``}>`+W())) // V -> <word> D
)=>
  T`+`?l+r+P(): // P -> V "+" P
  T`>`?l+P()+r+(T`^`&&P()): // P -> V ">" P ["^" P]?
  T`*`?Array(-~S()).join(P(r,l)): // V -> V "*" <word>
  l+r // reduce
// D (all atributes) ::= "#" <word> | "." <word> | "[" A | <empty>
D=c=> // `c` is all class names collected yet
  T`#`?' id='+S()+D(c): // D -> "#" <word> D
  T`.`?D(c+' '+S()): // D -> "." <word> D
  T`[`?A()+D(c): // D -> "[" A D
  c+c&&` class="${c}"` // reduce
// A (`[]` style attributes) ::= <word> A | <word> "=" <word> A | <word> "=" <string> A | "]"
A=_=>
  T`]`?'': // "]"
  ' '+S()+(T`=`?L+S():'=""')+A() // <word> ["=" (<word> | <string>)]? A
// W slice <text> to remove "{}" or return empty string if next token is not <text>
W=_=>S()[0]=="{"?L.slice(1,-1):U()

```

---
Tags: code-golf, parsing, code-generation
---


title: Lookalike shapes

text:
# Question
Title: Lookalike shapes
## Similar figures

Two rectangles are *similar* if the ratios of their sides are the same.

Consider these two rectangles; a rectangle 5 lines tall and 11 chars wide:

```
===========
===========
===========
===========
===========

```

and a rectangle 10 lines tall and 22 chars wide:

```
======================
======================
======================
======================
======================
======================
======================
======================
======================
======================

```

These shapes are similar because the ratios of their sides are the same. To put it formally (with \\$h\\$ being the shortest side and \\$w\\$ being the longest side):

$$ \frac{h\_1}{w\_1} = \frac{h\_2}{w\_2} $$

You can also do:

$$ \frac{h\_1}{h\_2} = \frac{w\_1}{w\_2} $$

## The challenge

Write a program or function that takes a "main" rectangle and some "other" rectangles and prints which of "others" are similar to "main".

## The input

A shape and a list of shapes. Each shape consists of 2 non-zero positive integers, which denote the width and height of the rectangle. For instance, this:

```
(4,2), (3,9)

```

denotes two rectangles, a 4x2 and a 3x9. The exact format of the input may be however you desire.

## The output

The indices of the "other" shapes that are similar to "main". You may choose whether the indices are 0- or 1-based, as well as the exact format and order of the output.

## Sample program

In Python:

```
main = eval(raw_input()) # The main rectangle.
rects = eval(raw_input()) # The list of rectangles.
similar = set()
for i, rect in enumerate(rects):
    if max(main)*min(rect) == min(main)*max(rect): # Cross-multiply
        # They are similar.
        similar.add(i)

print similar

```

## Sample input and output

Input:

```
(1, 2)
[(1, 2), (2, 4)]

```

Output:

```
set([0, 1])

```

Input:

```
(1, 2)
[(1, 9), (2, 5), (16, 8)]

```

Output:

```
set([2])

```

## Winning

This is code-golf, so the shortest submission wins.

## Notes

* This should go without saying, but **standard loopholes are banned**.
* **No builtins for locating similar figures may be used.** (I don't even know if that exists, but I would't be surprised!)

# Answer
# Pyth, 15 bytes

```
fqcFS@QTcFSvzUQ

```
> 5 votes

# Answer
## Python, 61 bytes

```
lambda a,b,l:[i for i,(x,y)in enumerate(l)if x/y in[a/b,b/a]]

```

Yes, I'm using spending 9 chars to write `enumerate`. Takes input like `1, 2, [(1, 9), (3,6), (2, 5), (16, 8)]`. For Python 2, input values need to be written as floats.

One char longer (62) in Python 3:

```
def f(a,b,l,i=0):
 for x,y in l:b/a!=x/y!=a/b or print(i);i+=1

```
> 11 votes

# Answer
# CJam, ~~22~~ ~~20~~ 19 bytes

```
{:$::/_0=f=ee::*0-}

```

The above is an anonymous function that pops a single array of floating point pairs (first pair is needle) from the stack and pushes the array of 1-based indexes in return.

Try it online in the CJam interpreter.

### How it works

```
:$                e# Sort each pair.
  ::/             e# [a b] -> a/b
     _0=          e# Push a copy of the array and extract the first float (needle).
        f=        e# Check which floats are equal to the needle.
          ee      e# Enumerate the resulting Booleans.
            ::*   e# Multiply each Boolean by its index.
                  e# This yields 0 for the needle (index 0) and for non-matching
                  e# haystack pairs (Boolean 0).
               0- e# Remove all zeroes from the array.

```
> 9 votes

# Answer
# Haskell, 48 bytes

```
(a!b)l=[i|(i,(x,y))<-zip[0..]l,x/y+y/x==a/b+b/a]

```

Try it online!

Call this like `(!) 1 2 [(1, 9), (3,6), (2, 5), (16, 8)]`.

A near-port of my Python answer. The expression `zip[0..]l` enumerates the list with its indices.

The expression `x/y+y/x==a/b+b/a` checks that the ratio `x/y` is either `a/b` or `b/a`, since the function `f(z) = z + 1/z` has `f(z) = f(1/z)` and no other collisions.
> 8 votes

# Answer
## Snowman 1.0.2, 61 chars

```
}vgvgaC"[0-9]+"sM:10sB;aM2aG:AsO:nD;aF;aM0AAgaA*|:#eQ;AsItSsP

```

Pure gibberish (unless you happen to know Snowman), a.k.a. exactly in line with the language's design goal of being as confusing as possible.

Input format is same as in the post, output format is also the same minus `set(` and `)`.

Ungolfed (or unminified, really):

```
}vgvgaC     // read two lines of input, concatenate
"[0-9]+"sM  // use a regex to grab all numbers
:10sB;aM    // essentially map(parseInt)
2aG         // take groups of 2 (i.e. all the ordered pairs)

// now map over each ordered pair...
:
  AsO       // sort
  :nD;aF    // fold with division - with 2 array elements, this is just a[0]/a[1]
;aM

// we now have an array of short side to long side ratios
// take out the first one
0AAgaA      // active vars beg, b=array[0], g=the rest
*|          // store first ordered pair in permavar, bring the rest to top

// select indices where...
:
  #         // retrieve first ordered pair
  eQ        // equal?
;AsI

tSsP  // to-string and output

```

I'm pretty proud of some of the tricks I used in this one:

* I used the same input format as in the post. But instead of trying to parse it somehow, which would get really messy, I just concatenated the two lines and then used a regex to extract all the numbers into one big array (with which I then did `2aG`, i.e. get every group of 2).
* `:nD;aF` is pretty fancy. It simply takes an array of two elements and divides the first one by the second one. Which seems pretty simple, but doing it the intuitive way (`a[0]/a[1]`) would be far, far longer in Snowman: `0aa`NiN`aA|,nD` (and that's assuming we don't have to worry about messing with other existing variables). Instead, I used the "fold" method with a predicate of "divide," which, for an array of two elements, achieves the same thing.
* `0AAgaA` looks innocuous enough, but what it actually does is store a `0` to the variables, then takes all variables with an index greater than that (so, all variables except for the first one). But the trick is, instead of `AaG` (which would get rid of the original array and the `0`), I used `AAg`, which keeps both. Now I use `aA`, at-index, using the *very same `0`* to get the first element of the array—furthermore, this is in consume-mode (`aA` instead of `aa`), so it gets rid of the `0` and original array too, which are now garbage for us.

Alas, `0AAgaA*|` does essentially the same thing that GolfScript does in one character: `(`. However, I still think it's pretty nice, by Snowman standards. :)
> 7 votes

# Answer
# Mathematica, 41 bytes

```
Position[a=Sort@#;Sort@#/a&/@#2,{x_,x_}]&

```

Usage:

```
Position[a = Sort@#; Sort@#/a & /@ #2, {x_, x_}] &[{1, 2}, {{1, 2}, {2, 5}, {16, 8}}]
(* {{1}, {3}} *)

```
> 3 votes

# Answer
# Pyth - 14 bytes

Filters by comparing quotients, then maps `indexOf`.

```
xLQfqcFSTcFvzQ

```

Test Suite.
> 3 votes

# Answer
# APL (Dyalog Unicode), ~~16~~ 13 bytesSBCS

```
(=.×∘⌽∨=.×)⍤1

```

Try it online!

-3 thanks to @ngn!

Explanation:

```
(=.×∘⌽∨=.×)⍤1
(     ∨   )   ⍝ "OR" together...
 =.    =.     ⍝ ...fold by equality of:
   ×∘⌽        ⍝ - the arguments multiplied by itself reversed
         x    ⍝ - the argument multiplied by itself
           ⍤1 ⍝ Applied at rank 1 (traverses)

```

Output format is a binary vector like `1 1 0 0 1` of which "other" rectangle is a look-a-like.

# APL (Dyalog Extended), 11 bytesSBCS

```
=/-×⍥(⌈/)¨⌽

```

Try it online!

Explanation:

```
=/-×⍥(⌈/)¨⌽ ⍝ takes only a right argument: ⍵, shape: (main (other...))
          ⌽ ⍝ two transformations:
  -         ⍝ - left (L) vectorized negation: -⍵
          ⌽ ⍝ - right (R): reverse. (main other) => (other main)
     (⌈/)¨  ⍝ transformation: calculate the max (since L is negated, it calculates the min)
            ⍝ (/ reduces over ⌈ max)
            ⍝ this vectorizes, so the "main" side (with only one rect) will get repeated once for each "other" rect on both sides
   ×⍥       ⍝ over multiplication: apply the transformation to both sides. F(L)×F(R)
=/          ⍝ reduce the 2-element matrix (the "main" that's now the side of the "other") to check which are equal

```

Output format is the same as the main Dyalog answer.

Thanks to Adám for the help golfing + Extended.
> 3 votes

# Answer
# Julia, 62 bytes

```
f(m,o)=find([(t=sort(m).*sort(i,rev=true);t[1]==t[2])for i=o])

```

The `find` function locates true elements in a boolean vector. `.*` performs elementwise multiplication of vectors.

Ungolfed:

```
function f(m::Array, o::Array)
    find([(t = sort(m) .* sort(i, rev=true); t[1] == t[2]) for i in o])
end

```

Usage:

```
f([1,2], {[1,9], [2,5], [16,8]})

```
> 2 votes

# Answer
# K5, 19 bytes

I think this will do the trick:

```
&(*t)=1_t:{%/x@>x}'

```

Takes a list of pairs where the first is the "main". Computes the ratio by dividing the sorted dimensions of each pair. Returns a list of the 0-indexed positions of the matching pairs. (arguably the input format I chose makes this -1 indexed- if this is considered invalid tack on a `1+` to the beginning and add two characters to the size of my program.)

Usage example:

```
  &(*t)=1_t:{%/x@>x}'(1 2;1 2;2 4;2 5;16 8)
0 1 3

```

This runs in oK\- note that I implicitly depend on division always producing floating point results. It would work in Kona if you added a decimal point to all the numbers in the input and added a space after the `_`.
> 2 votes

# Answer
# Octave / Matlab, 44 bytes

Using an anonymous function:

```
@(x,y)find((max(x))*min(y')==min(x)*max(y'))

```

The result is in 1-based indexing.

To use it, define the function

```
>> @(x,y)find((max(x))*min(y')==min(x)*max(y'));

```

and call it with the following format

```
>> ans([1 2], [1 9; 2 5; 16 8])
ans =
     3

```

You can try it online.

---

If the result can be in **logical indexing** (`0` indicates not similar, `1` indicates similar): **38 bytes**:

```
@(x,y)(max(x))*min(y')==min(x)*max(y')

```

Same example as above:

```
>> @(x,y)(max(x))*min(y')==min(x)*max(y')
ans =
    @(x,y)(max(x))*min(y')==min(x)*max(y')

>> ans([1 2], [1 9; 2 5; 16 8])
ans =
 0     0     1

```
> 2 votes

# Answer
# Brachylog, 14 bytes

```
z{iXhpᵐ/ᵛ∧Xt}ᵘ

```

Try it online!

Takes input as a list *containing a list containing* the main rectangle and the list of other rectangles (so test case 1 is `[[[1,2]],[[1,2],[2,4]]]`), and outputs a list of 0-based indices through the output variable.

```
z                 Zip the elements of the input, pairing every "other" rectangle with the main rectangle.
 {          }ᵘ    Find (and output) every unique possible output from the following:
  iX              X is an element of the zip paired with its index in the zip.
    h             That element
      ᵐ           with both of its elements
     p            permuted
        ᵛ         produces the same output for both elements
       /          when the first element of each is divided by the second.
         ∧Xt      Output the index.

```

If that sort of odd and specific input formatting is cheating, it's a bit longer...

# Brachylog, 18 bytes

```
{hpX&tiYh;X/ᵛ∧Yt}ᶠ

```

Try it online!

Takes input as a list containing the main rectangle and the list of other rectangles (so test case 1 is the more obvious `[[1,2],[[1,2],[2,4]]]`), and outputs a list of 0-based indices through the output variable.

```
{               }ᵘ    Find (and output) every possible output from the following:
  p                   A permutation of
 h                    the first element of the input
   X                  is X,
    &                 and
      i               a pair [element, index] from
     t                the last element of the input
       Y              is Y,
        h             the first element of which
            ᵛ         produces the same output from
           /          division
         ;            as
          X           X.
             ∧Yt      Output the index.

```

To determine if two width-height pairs represent similar rectangles, it just takes the four bytes `pᵐ/ᵛ` (which outputs the shared ratio or its reciprocal). All the rest is handling the multiple rectangles to compare, and the output being indices.
> 2 votes

# Answer
# dzaima/APL, 7 bytes

```
=/⍤÷⍥>¨

```

Try it online!

8 bytes outputting a list of indices instead of a boolean vector

```
      ¨ for each (pairing the left input with each of the right)
    ⍥>    do the below over sorting the arguments
=/          equals reduce
  ⍤         after
   ÷        vectorized division of the two

```
> 2 votes

# Answer
# Haskell, 75 bytes

```
import Data.List
a(x,y)=max x y/min x y
s r=elemIndices(True).map((==a r).a)

```
> 1 votes

# Answer
# PowerShell, ~~58~~ 56 bytes

-2 bytes thanks to mazzy x2

```
param($x,$y,$b)$b|%{($i++)[$x/$y-($z=$_|sort)[0]/$z[1]]}

```

Try it online!

This slightly abuses the `input may be however you desire` clause by having the first shape's components come separately to save 3 bytes.

# PowerShell, ~~61~~ 59 bytes

```
param($a,$b)$b|%{($i++)[$a[0]/$a[1]-($x=$_|sort)[0]/$x[1]]}

```

Try it online!

Uses conditional indexing to swap between the current zero-based index and null based on whether or not the ratios line up. Luckily in this case, `$i` increments regardless of it being printed or not.
> 1 votes

# Answer
# PowerShell, 57 bytes

```
$args|%{$x,$y=$_|sort
($i++)[$r-$y/$x]
if(!$r){$r=$y/$x}}

```

Try it online!

Indices are 1-based.
> 1 votes

# Answer
# Javascript (ES6), 75

```
(a,b)=>b.filter(e=>e.l*a.h==a.l*e.h||e.l*a.l==a.h*e.h).map(e=>b.indexOf(e))

```

Alternative, also 75

```
(a,b)=>b.map((e,i)=>e.l*a.h==a.l*e.h||e.l*a.l==a.h*e.h?i:-1).filter(e=>e+1)

```

Input is taken as a JSON object, and an array of JSON objects

```
{
    l: length of rectangle,
    h: height of rectangle
}

```
> 0 votes

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

```
ʒ‚ε{ü/}Ë}J¹Jsk

```

Try it online or verify all test cases.

**Explanation:**

```
ʒ               # Filter the (implicit) input-list by:
 ‚              #  Pair the current width/height with the (implicit) input width/height
  ε             #  Map both width/height pairs to:
   {            #   Sort from lowest to highest
    ü/          #   Pair-wise divide them from each other
      }Ë        #  After the map: check if both values in the mapped list are equals
        }J      # After the filter: join all remaining pairs together to a string
          ¹J    # Also join all pairs of the first input together to a string
            s   # Swap to get the filtered result again
             k  # And get it's indices in the complete input-list
                # (which is output implicitly)

```

The `J`oins are there because 05AB1E can't determine the indices on multidimensional lists a.f.a.i.k.

---

If outputting the width/height pairs that are truthy, or outputting a list of truthy/falsey values based on the input-list, it could be **8 bytes** instead:

```
ʒ‚ε{ü/}Ë

```

Try it online or verify all test cases.

```
ε‚ε{ü/}Ë

```

Try it online or verify all test cases.
> 0 votes

# Answer
# Uiua, 10 bytes

```
⊚↥∩/=⊃×÷⊙⍉

```

Try it online!

-2 if I can take the second input transposed.

```
⊚↥∩/=⊃×÷⊙⍉    input: a shape S, a list of shapes M (2d matrix with two columns)
          ⊙⍉    transpose the 2nd input
      ⊃×÷        fork(mul, div): take S and M and give S*M and S/M
                  the operations are done between each item of S and each row of M
   ∩/=            both(reduce by equal): for each of the two matrices,
                  compare the two rows elementwise and give 1 when equal
                  for similar shapes, * gives 1 if in reverse order, / otherwise
  ↥               boolean OR of the two vectors
⊚                vector of indices of ones

```
> 0 votes

---
Tags: code-golf, rational-numbers
---


title: Church Booleans

text:
# Question
Title: Church Booleans
# Church booleans

A Church boolean is a function that returns `x` for true and `y` for false where `x` is the first argument to the function and `y` is the second argument to the function. Further functions can be composed from these functions which represent the `and` `not` `or` `xor` and `implies` logical operations.

# Challenge

Construct the Church booleans and `and` `not` `or` `xor` and `implies` Church gates in a language of your choice. `and` `or` and `xor` should take in two functions (representing Church booleans) and return a function (representing another Church boolean). Likewise, `not` should invert the function it takes and the `implies` gate should perform boolean implies logic where the first argument `implies` the second.

# Scoring

The total length of all of the code required to make Church `true` and `false` in your language and the `and` `not` `or` `xor` and `implies` Church gates excluding the function's name. (for example, `false=lambda x,y:y` in Python would be 13 bytes). You can reuse these names later in your code with them counting 1 byte toward the byte total of that gate.

# Pseudo code Examples:

The functions you create should be able to be called later in your code like so.

```
true(x, y) -> x
false(x, y) -> y
and(true, true)(x, y) -> x
and(true, false)(x, y) -> y
# ... etc

```

# Answer
> 14 votes
# Binary Lambda Calculus, 13.875 12.875 bytes (103 bits)

Binary Lambda Calculus Language (BLC) by John Tromp is basically an efficient serialization format for lambda calculus. It is a great fit for this task, as Church notation is even the "idiomatic" way to work with booleans in BLC.

I used the following lambda functions for the combinators, some of which I copied and golfed from the Haskell answer:, which were found by an exhaustive search with a proof limit of 20 β-reductions for each case. There is a good chance these are shortest possible.

```
True:  (\a \b a)
False: (\a \b b)
Not:   (\a \b \c a c b)
And:   (\a \b b a b)
Or:    (\a a a)
Xor:   (\a \b b (a (\c \d d) b) a)
Impl:  (\a \b a b (\c \d c))

```

These translate to the following (binary) BLC code sequences:

```
 bits |  name | BLC
------+-------+---------
    7 | True  | 0000 110
    6 | False | 0000 10
   19 | Not   | 0000 0001 0111 1010 110
   15 | And   | 0000 0101 1011 010
    8 | Or    | 0001 1010
   28 | Xor   | 0000 0101 1001 0111 0000 0101 0110
   20 | Impl  | 0000 0101 1101 0000 0110

```

Functions above are in total 111 bits long (13.875 bytes) 103 bits long (12.875 bytes). They don't need to be aligned to byte boundaries to be used inside a program, so it makes sense to count fractional bytes.

There is no code re-use between the combinators, because there are no variables/references/names in BLC - everything had to be copied over. Still, the efficiency of the encoding makes for quite a terse representation.

# Answer
> 26 votes
# Haskell, 50 - 6 = 44 bytes

*-1 byte thanks to Khuldraeseth na'Barya, and -1 byte thanks to Christian Sievers.*

```
t=const
f=n t
n=flip
a=n n f
o=($t)
x=(n>>=)
i=o.n

```

Try it online!

# Answer
> 10 votes
# Python 2, (-3?)  ~~101~~  95 bytes

David Beazley eat your heart out!

-6 thanks to Chas Brown (moved the repeated `:` into the join text \>.\<)

```
exec'=lambda x,y=0:'.join('F y;T x;N x(F,T);A x(y,F);O x(T,y);X x(N(y),y);I O(y,N(x))'.split())

```

**Try it online!**

I think it might be `95 - 3` because I don't reuse the functions `A`, `X`, or `I`, but I use a single `=` for assignment (in front of `lambda`). Maybe I cant remove any; maybe I even get to remove 3.5?

# Answer
> 7 votes
# JavaScript (Node.js), ~~92~~ ~~86~~ 83 - 7 = 76 bytes

```
t=p=>q=>p
f=t(q=>q)
n=p=>p(f)(t)
a=p=>n(p)(f)
o=p=>p(t)
x=p=>p(n)(f())
i=p=>n(p)(t)

```

Try it online! Link includes basic test cases. Edit: Saved ~~6~~ 9 bytes thanks to @tsh.

# Answer
> 6 votes
# Python 2, ~~133 - 6 = 127~~ 94 bytes

```
exec"t!u;f!v;n!u(f,t);a!u(v,f);o!u(t,v);x!u(n(v),v);i!o(v,n(u))".replace('!','=lambda u,v=0:')

```

Try it online!

Shamelessly stealing the sneaky idea behind Jonathan Allan's answer; no bytes deducted though.

# Answer
> 5 votes
# Wolfram Language (Mathematica), 61-7=54 bytes

```
t=#&
f=#2&
a=#2~#~f&
o=t~#~#2&
n=f~#~t&
x=n@#~#2~#&
i=#2~#~t&

```

Try it online!

un-golfed: inspired by Wikipedia,

```
t[x_, y_] := x
f[x_, y_] := y
and[x_, y_] := x[y, f]
or[x_, y_] := x[t, y]
not[x_] := x[f, t]
xor[x_, y_] := y[not[x], x]
imply[x_, y_] := x[y, t]

```

# Answer
> 5 votes
# Underload, ~~56~~ 52 bytes

```
(~!)(!)((~)~*):((!)~^)*(:^)(~(!)~^(~)~*)(()~(~)~^~*)

```

Try it online! (includes a testsuite and text identifying parts of the program)

This scores surprisingly well for a very low-level esolang. (Church numerals, Church booleans, etc. are very commonly used in Underload for this reason; the language doesn't have numbers and booleans built in, and this is one of the easier ways to simulate them. That said, it's also common to encode booleans as the Church numerals 0 and 1.)

For anyone who's confused: Underload lets you define reusable functions, but doesn't let you name them in the normal way, they just sort of float around on the argument stack (so if you define five functions and then want to call the first one you defined, you need to write a new function that takes five arguments and calls the fifth of them, then call it with insufficiently many arguments so that it looks for spare arguments to use). Calling them destroys them by default but you can modify the call to make it non-destructive (in simple cases, you just need to add a colon to the call, although the complex cases are more common because you need to make sure that the copies on the stack don't get in your way), so Underload's function support has all the requirements we'd need from the question.

## Explanation

### true

```
(~!)
(  )  Define function:
 ~      Swap arguments
  !     Delete new first argument (original second argument)

```

This one's fairly straightforward; we get rid of the argument we don't want and the argument we do want just stays there, serving as the return value.

### false

```
(!)
( )   Define function:
 !      Delete first argument

```

This one's even more straightforward.

### not

```
((~)~*)
(     )  Define function:
    ~*     Modify first argument by pre-composing it with:
 (~)         Swap arguments

```

This one's fun: `not` doesn't call its argument at all, it just uses a function composition. This is a common trick in Underload, in which you don't inspect your data at all, you just change how it functions by pre- and post-composing things with it. In this case, we modify the function to swap its arguments before running, which clearly negates a Church numeral.

### and

```
:((!)~^)*
 (     )   Define function:
     ~^      Execute its first argument with:
  (!)          false
               {and implicitly, our second argument}
        *  Edit the newly defined function by pre-composing it with:
:            {the most recently defined function}, without destroying it

```

The question permits defining functions in terms of other functions. We define "and" next because the more recently "not" has been defined, the easier it is to use it. (This doesn't subtract from our score, because we aren't naming "not" at all, but it saves bytes over writing the definition out again. This is the only time that one function refers to another, because referring to any function but the most recently defined would cost too many bytes.)

The definition here is `and x y = (not x) false y`. In other words, if `not x`, then we return `false`; otherwise, we return `y`.

### or

```
(:^)
(  )  Define function:
 :      Copy the first argument
  ^     Execute the copy, with arguments
          {implicitly, the original first argument}
          {and implicitly, our second argument}

```

@Nitrodon pointed out in the comments that `or x y = x x y` is normally shorter than `or x y = x true y`, and that turns out to be correct in Underload as well. A naive implementation of that would be `(:~^)`, but we can golf off an additional byte by noting that it doesn't matter whether we run the original first argument or the copy of it, the result is the same either way.

Underload doesn't actually support currying in the usual sense, but definitions like this make it look like it does! (The trick is that non-consumed arguments just stick around, so the function you call will interpret them as its own arguments.)

### implies

```
(~(!)~^(~)~*)
(           )  Define function:
 ~               Swap arguments
     ~^          Execute the new first (original second) argument, with argument:
  (!)              false
                   {and implicitly, our second argument}
       (~)~*     Run "not" on the result

```

The definition used here is `implies x y = not (y false x)`. If y is true, this simplifies to `not false`, i.e. `true`. If y is false, this simplifies to `not x`, thus giving us the truth table we want.

In this case, we're using `not` again, this time by rewriting its code rather than referencing it. It's just written directly as `(~)~*` without parentheses around it, so it gets called rather than defined.

### xor

```
(()~(~)~^~*)
(          )  Define function:
   ~   ~^       Execute the first argument, with arguments:
    (~)           "swap arguments"
 ()               identity function
         ~*     Precompose the second argument with {the result}

```

This time, we're evaluating only one of our two arguments, and using it to determine what to compose onto the second argument. Underload lets you play fast and loose with arity, so we're using the first argument to choose between two two-argument two-return functions; the argument swap that returns them both but in the opposite order, and the identity function that returns them both in the same order.

When the first argument is true, we therefore produce an edited version of the second argument that swaps its arguments before running, i.e. precompose with "swap arguments", i.e. `not`. So a true first argument means we return `not` the second argument. On the other hand, a false first argument means we compose with the identity function, i.e. do nothing. The result is an implementation of `xor`.

# Answer
> 4 votes
# , 67 bytes - 7 = 60

```
t=.[
f=.]
n=.~
a=.2 :'u v]'
o=.2 :'[u v'
x=.2 :'u~v u'
i=.2 :'v u['

```

Try it online!

Worth noting:

Higher order functions work differently in J than in a functional language. To create a new verb from 1 or 2 existing verbs, you need to use either an adverb (in the case of 1) or a conjunction (in the case of 2).

Syntactically, adverbs come after a verb, and conjunctions go between them. Thus to "not" a verb `f` you do `f n`, and to "and" verbs `f` and `g`, you `f a g`.

# Answer
> 4 votes
# Ruby, 82 - 4 = 78 bytes

```
f,t,a,n,i,o,x=%w(y:y x:x f:y t:f t:y y:t y:n[y]).map{|s|eval"->x,y=0{x==f ?#{s}}"}

```

Try it online!

# Answer
> 3 votes
# Java 8, score: ~~360~~ ~~358~~ ~~319~~ ~~271~~ 233 (240-7) bytes

```
interface J<O>{O f(O x,O y,J...j);}J t=(x,y,j)->x;J f=(x,y,j)->y;J n=(x,y,j)->j[0].f(y,x);J a=(x,y,j)->j[0].f(j[1].f(x,y),y);J o=(x,y,j)->j[0].f(x,j[1].f(x,y));J x=(x,y,j)->j[0].f(j[1].f(y,x),j[1].f(x,y));J i=(x,y,j)->j[0].f(j[1].f(x,y),x);

```

~~This was trickier to accomplish than I thought when I started it.. Especially the `implies`. Anyway, it works.. Can probably be golfed a bit here and there.~~ EDIT: Ok, not re-using functions but just duplicating the same approach is a lot cheaper in terms of byte-count for Java.. And I get the full -7 bonus for not using any of the functions as well.

Try it online.

**Explanation:**

```
// Create an interface J to create lambdas with 2 Object and 0 or more amount of optional
// (varargs) J lambda-interfaces, which returns an Object:
interface J<O>{O f(O x,O y,J...j);}

// True: with parameters `x` and `y`, always return `x`
J t=(x,y,j)->x;
// False: with parameters `x` and `y`, always return `y`
J f=(x,y,j)->y;

// Not: with parameters `x`, `y`, and `j` (either `t` or `f`), return: j(y, x)
J n=(x,y,j)->j[0].f(y,x);

// And: with parameters `x`, `y`, and two times `j` (either `t` or `f`), return:
//      j1(j2(x,y), y);
J a=(x,y,j)->j[0].f(j[1].f(x,y),y);

// Or: with parameters `x`, `y`, and two times `j` (either `t` or `f`), return:
//     j1(x, j2(x,y))
J o=(x,y,j)->j[0].f(x,j[1].f(x,y));

// Xor: with parameters `x`, `y`, and two times `j` (either `t` or `f`), return:
//      j1(j2(y,x), j2(x,y))
J x=(x,y,j)->j[0].f(j[1].f(y,x),j[1].f(x,y));

// Implies: with parameters `x`, `y`, and two times `j` (either `t` or `f`), return:
//          j1(j2(x,y), x)
J i=(x,y,j)->j[0].f(j[1].f(x,y),x);

```

# Answer
> 2 votes
# C++17, ~~207−49=158~~ 195 − 58 = 137 bytes

The linebreaks are unnecessary (other than the first two).

```
#define A auto
#define D(v,p)A v=[](A x,A y){return p;};
D(true_,x)
D(false_,y)
A not_=[](A f){return f(false_,true_);};
D(and_,x(y,false_))
D(or_,x(true_,y))
D(xor_,x(not_(y),y))
D(implies,x(y,true_))

```

Try it online!

Unit-tested with assertions such as:

```
static_assert('L' == true_('L', 'R'));
static_assert('R' == not_(true_)('L', 'R'));
static_assert('L' == and_(true_, true_)('L', 'R'));
static_assert('L' == or_(true_, true_)('L', 'R'));
static_assert('R' == xor_(true_, true_)('L', 'R'));
static_assert('L' == implies(true_, true_)('L', 'R'));

```

UPDATED: formerly I'd had

```
A not_=[](A f){return[f](A x,A y){return f(y,x);};};

```

but Roman's answer pointed the way to the shorter version. Notice that now `not_(std::plus<>)` is ill-formed, where formerly it was equivalent to `std::plus<>`; but since `std::plus<>` doesn't "represent a Church boolean," I think either behavior is okay by the rules.

# Answer
> 2 votes
## SKI-calculus + C combinator, ~~36~~ 33 bytes

```
true=K
false=SK
not=C
and=SCI
or=SII
xor=C(CIC)I
implies=CCK

```

I don't actually know of any interpreter that allows you to define additional combinators in terms of previous ones, so I had to test this using http://ski.aditsu.net/ by pasting in the desired combinators e.g. `CCKK(SK)pq` outputs `q`, showing that `K` does not imply `SK`.

Edit: Saved 3 bytes thanks to @Bubbler.

# Answer
> 2 votes
# Forth (gforth), 133  bytes - 7 = 126 122

```
: j execute ;
: t drop ;
: f nip ;
: n ['] f ['] t rot j ;
: a dup j ;
: o over j ;
: x 2dup a n -rot o a ;
: m over n -rot a o ;

```

Try it online!

-4 bytes thanks to Quuxplusone

Initially I significantly overthought this, considering things like macros and literals, but then I realized that if I define things in terms of true and false (like I should have done in the first place), it gets much simpler.

### Code explanation

```
\ Helper function to save some bytes
: j        \ define a new word
  execute  \ execute the word at the provided address
;          \ end word definition

\ True
: t        \ define a new word
  drop     \ drop the second argument
;          \ end the word

\ False
: f        \ define a new word
  nip      \ drop the first argument
;          \ end the word

\ Not - The "hardest" one because we have to reference true and false directly
: n        \ define a new word
  ['] f    \ get address of false
  ['] t    \ get the address of true
  rot      \ stick the input boolean back on the top of the stack
  j        \ call the input boolean, which will select the boolean to return
;          \ end the word

\ And
: a        \ define a new word
  dup      \ duplicate the 2nd input value
  j        \ call the 2nd input on the first and second input
;          \ end the word

\ Or
: o        \ define a new word
  over     \ duplicate the 1st input value
  j        \ call the 1st input on the first and second input
;          \ end the word

\ Xor
: x        \ define a new word
  2dup     \ duplicate both of the inputs
  a n      \ call and, then not the result (nand)
  -rot     \ move the result behind the copied inputs
  o a      \ call or on the original inputs, then call and on the two results
;          \ end the word

\ Implies
: m        \ define a new word
  over     \ duplicate the 1st input value
  n        \ call not on the 1st input value
  -rot     \ move results below inputs
  a o      \ call and on the two inputs, then call or on the two results
;          \ end the word

```

# Answer
> 1 votes
# Perl 6, ~~120~~ ~~106~~ ~~102~~ 101 bytes

*-1 byte thanks to Jo King*

```
my (\t,\f,&n,&a,&o,&i,&x)={@_[0]},{@_[1]},|<f,t &^v,f t,&^v &^v,t n(&^v),&v>>>.&{"&\{\&^u($_)}".EVAL}

```

Try it online!

# Answer
> 1 votes
# C++17, ~~202−49=153~~ 193 − 58 = 135 bytes

Inspired by the comment-discussion of what counts as a 2-ary function anyway, here's a curried version of my previous C++17 solution. It's actually shorter because we can use the same macro to define `not_` as to define all the other functions!

```
#define D(v,p)auto v=[](auto x){return[=](auto y){return p;};};
D(true_,x)
D(false_,y)
D(not_,x(false_)(true_)(y))
D(and_,x(y)(false_))
D(or_,x(true_)(y))
D(xor_,x(not_(y))(y))
D(implies,x(y)(true_))

```

Try it online!

This one is tested with assertions like

```
static_assert('R' == and_(true_)(false_)('L')('R'));
static_assert('L' == or_(true_)(false_)('L')('R'));

```

Notice that `or_` is defined as effectively

```
auto or_=[](auto x){return[=](auto y){return x(true_)(y);};};

```

We could define `or_` more "concisely" as

```
auto or_=[](auto x){return x(true_);};

```

but that would cost us because we wouldn't get to use the `D` macro anymore.

# Answer
> 1 votes
# APL (dzaima/APL), 47 bytesSBCS

Based on Jonah's J solution.

`true` and `false` are infix functions, `not` is a suffix operator, and the rest are infix operators.

```
true←⊣
false←⊢
and←{⍺(⍶⍹false)⍵}
not←⍨
or←{⍺(true⍶⍹)⍵}
xor←{⍺(⍶not⍹⍶)⍵}
implies←{⍺(⍹⍶true)⍵}

```

As per OP, this counts everything from and including  to the end of each line, and counts each call a previous definition as a single byte.

Try it online!

true and false are the left and right identity functions.

`not` simply swaps the arguments of its operand function.

The rest implement the decision tree:

`and` uses the righthand function  to select the result of the lefthand function  if true, else the result of the `false` function.

`or` uses the lefthand function  to select the `true` if true, else the result of the righthand function .

`xor` uses the righthand function  to select the the negated result of the lefthand function `⍶not` if true, else the result of the lefthand function.

`implies` uses the lefthand function  to select the result of the righthand function  if true, else the result of the `true` function.

# Answer
> 1 votes
# Julia 1.0, 36 bytes

```
(b::Bool)(x,y)=b ? x : y;i(x,y)=!x|y

```

I don't know if that counts, I'm actually just overloading the native `Bool` type to be callable, so I get most of the logic gates for free. Unfortunately, Julia doesn't have an `implies` gate, so I had to write my own function.

Try it online!

# Answer
> 1 votes
# Birb, 23 (or 41?) bytes

```
true:
false:
not:
and:
or:
xor:
implies:

```

It works a bit like @Neil's answer, but Birb's alternating associative order changes things a bit. Here are the respective parentheses to indicate the associativity:

```
true: ()
false: ()
not: (())
and: (((())))
or: (())
xor: (((())))
implies: (())

```

You may realize that several programs could be significantly shorter (e.g. `true:` , `not:` , `or:` , or `and:` . However, to have a uniform way of application (due to Birb's alternating associativity), `true` and `false` need to have the same length and all other functions need an odd length \>2. I also tried to use a variety of birbs :)

Example applications:

```
not true
~>
~> [] (false)

xor true false
~>
~>  (true)

```

I'm unsure whether to count the additional .. If not, the sum of the length of all Birb functions is 23 bytes. If yes, `2+l(not) + 4+l(and) + 4+l(or) + 4+l(xor) + 4+l(implies) = 41` bytes.

# Answer
> 0 votes
# Stax, 34 bytes

```
¿S£↓♣└²≡é♫Jíg░EèΩRΦ♂°┤rà╝¶πï╡^O|Θà

```

Run and debug it at staxlang.xyz!

Pushes a bunch of blocks to the stack. Each block expects its last argument atop the stack, followed in reverse order by the rest.

### Unpacked (41 bytes):

```
{sd}Y{d}{y{d}a!}X{ya!}{b!}{cx!sa!}{sx!b!}

```

Each pair of `{ }` is a block. I used the two registers X and Y to hold `true` and `not` so I could access 'em easily later. Unfortunately, `false` couldn't simply be a no-op, as that would leave the stack cluttered and mess up a single XOR case.

Test suite, commented

```
false
{sd}    stack:   x y
 s      swap:    y x
  d     discard: y

true
{d}    stack:   x y
 d     discard: x

not
{y{d}a!}    stack:  p
 y{d}       push:   p f t
     a      rotate: f t p
      !     apply:  p(f,t)

and
{ya!}    stack:  p q
 y       push:   p q f
  a      rotate: q f p
   !     apply:  p(q,f)

or
{b!}    stack:  p q
 b      copies: p q p q
  !     apply:  p q(q,p)

xor
{cx!sa!}    stack:  p q
 c          copy:   p q q
  x!        not:    p q nq
    s       swap:   p nq q
     a      rotate: nq q p
      !     apply:  p(nq,q)

implies
{sx!b!}    stack:  p q
 s         swap:   q p
  x!       not:    q np
    b      copies: q np q np
     !     apply:  q np(np,q)

```

# Answer
> 0 votes
# Befunge-98, ~~105~~ ~~77~~ 65 bytes

Playing further with the notion of "function" in languages without functions... here's a Befunge-98 version of Church booleans!

In this constrained dialect of Befunge-98, a program consists of a series of "lines" or "functions," each of which begins with a `>`(Go Right) instruction in column x=0. Each "function" can be identified with its line number (y-coordinate). Functions can take input via Befunge's *stack*, as usual.

Line 0 is special, because (0,0) is the starting IP. To make a program that executes line L, just place instructions on line 0 that, when executed, fly the instruction pointer to (x=L, y=0).

The magic happens on line 1. Line 1, when executed, pops a number `L` from the stack and jumps to line number `L`. (This line had previously been `> >>0{{2u2}2}$-073*-\x`, which can "absolute jump" to any line; but I just realized that since I know this line is pegged to line 1, we can "relative jump" `L-1` lines in a heck of a lot less code.)

Line 2 represents Church `FALSE`. When executed, it pops two numbers `t` and `f` from the stack and then flies to line number `f`.

Line 3 represents Church `TRUE`. When executed, it pops two numbers `t` and `f` from the stack and then flies to line number `t`.

Line 6, representing Church `XOR`, is innovative. When executed, it pops two numbers `a` and `b` from the stack, and then flies to line `a` with stack input `NOT EXEC b`. So, if `a` represents Church `TRUE`, the result of `a NOT EXEC b` will be `NOT b`; and if `a` represents Church `FALSE`, the result of `a NOT EXEC b` will be `EXEC b`.

---

Here's the ungolfed version with test harness. On line 0, set up the stack with your input. For example, `338` means `IMPLIES TRUE TRUE`. Make sure the closing `x` appears at exactly (x,y)=(0,15) or else nothing will work! Also make sure your stack setup begins with `ba`, so that the program will actually terminate with some output.

Try it online!

```
>  ba 334  0f-1x
> >>1-0a-\x             Line 1: EXEC(x)(...) = goto x
> $^< <            <    Line 2: FALSE(t)(f)(...) = EXEC(f)(...)
> \$^                   Line 3: TRUE(t)(f)(...) = EXEC(t)(...)
> 3\^                   Line 4: OR(x)(y)(...) = EXEC(x)(TRUE)(y)(...)
> 3\2\^                 Line 5: NOT(x)(...) = EXEC(x)(FALSE)(TRUE)(...)
> 1\5\^                 Line 6: XOR(x)(y)(...) = EXEC(x)(NOT)(EXEC)(...)
> 2>24{\1u\1u\03-u}^    Line 7: AND(x)(y)(...) = EXEC(x)(y)(FALSE)(...)
> 3^                    Line 8: IMPLIES(x)(y)(...) = EXEC(x)(y)(TRUE)(...)

> "EURT",,,,@
> "ESLAF",,,,,@

```

---

Here's the version whose bytes I counted.

```
>>>1-0a-\x
>$^<< }u-30\<
>\$^
>3\^\
>3\2^
>1\5^
>2>24{\1u\1u^
>3^

```

Notice that to define a function in this dialect you don't mention its name at all; its "name" is determined by its source location. To call a function, you do mention its "name"; for example, `XOR` (`6`) is defined in terms of `NOT` and `EXEC` (`5` and `1`). But all my "function names" already take only one byte to represent. So this solution gets no scoring adjustments.

---
Tags: code-golf, logic-gates, functional-programming
---