# Question
Title: Concatenated halting problem: no + no + ... = yes
## Challenge

Write \\$2 \le n \le 10\\$ distinct, valid non-halting full programs in your language of choice. If all of them are concatenated in order, the resulting full program should be a valid halting program, but if any of them are left out, the result should still be a valid non-halting program.

More formally, write \\$2 \le n \le 10\\$ distinct programs \\$P\_1, P\_2, \cdots, P\_n\\$ in a language \\$L\\$ of your choice, which satisfy the following property:

* \\$P\_1 P\_2 \cdots P\_n\\$ (where \\$XY\\$ means string concatenation of two programs \\$X\\$ and \\$Y\\$) is valid full program in \\$L\\$ and, given no input, halts in finite time.
* If you delete any of \\$1 \le x \le n-1 \\$ program segments (\\$P\_i\\$'s where \\$1 \le i \le n\\$) from the above, the result is still a valid full program in \\$L\\$, but does not halt in finite time.
    + In other words, any nonempty proper subsequence of \\$P\_1 P\_2 \cdots P\_n\\$ should be a valid non-terminating program in \\$L\\$.

A program is *valid* if a compiler can successfully produce an executable or an interpreter finishes any pre-execution check (syntax parser, type checker, and any others if present) without error. A valid program is *halting* if the execution finishes for any reason, including normally (end of program, halt command) or abnormally (any kind of runtime error, including out-of-memory and stack overflow). The output produced by any of the programs does not matter in this challenge.

For example, a three-segment submission `foo`, `bar`, and `baz` is valid if

* `foobarbaz` halts in finite time, and
* each of `foo`, `bar`, `baz`, `foobar`, `foobaz`, and `barbaz` does not halt in finite time in the same language. (The behavior of `barfoo` or `bazbar` does not matter, since the segments are not in order.)

The score of your submission is the number \\$n\\$ (the number of program segments). The higher score wins, tiebreaker being code golf (lower number of bytes wins for the same score). It is encouraged to find a general solution that works beyond \\$n = 10\\$, and to find a solution that does not read its own source code (though it is allowed).

# Answer
# JavaScript (Node.js), 10 programs, 299 bytes

```
(A=_=>setTimeout(A,B=_=>0))();
(B=_=>setTimeout(B,C=_=>0))();
(C=_=>setTimeout(C,D=_=>0))();
(D=_=>setTimeout(D,E=_=>0))();
(E=_=>setTimeout(E,F=_=>0))();
(F=_=>setTimeout(F,G=_=>0))();
(G=_=>setTimeout(G,H=_=>0))();
(H=_=>setTimeout(H,I=_=>0))();
(I=_=>setTimeout(I,J=_=>0))();
(J=_=>setTimeout(J,A=_=>0))()

```

Line breaks are added for readability. They are not a part of any programs.

Node.js will keep running if there is any timers been scheduled, and halt as soon as timer callback queue is cleared.

The order of these programs does not matter. After append an extra `;` to the last one, you may shuffle them and it still meets the requirement of this challenge. It halts as long as you collected all 10 programs, and never halts if anyone is missing. You may also duplicate some programs here, and it works same as the program appears only once. :)
> 29 votes

# Answer
# Zsh, 56 bytes, 10 programs

```
until wc<<Q|grep 36
yes
yes;yes yes	yes yes ;yes
yes	yes

```

Try it online!

The first and most important program is:

```
until wc<<Q|grep 36

```

Each `yes` is part of one of the other programs.

y it online! (note: TIO kills the program very quickly because `yes` produces over 128 KB of output, but if you ran it elsewhere it would never halt)

Tre!

## Explanation

* `<<Q`: heredoc; takes the rest of the script starting from the next line, as a string
* `wc`: output line, word, and character numbers
* `|grep 36`: and search for the string `36` in that output
* `until` : repeat this command until it succeeds

If all 10 programs are present, then there will be exactly 36 characters in the output of `wc` and the `grep` will succeed, so the loop will halt.

If the first program is removed, the remainder of the script will be interpreted as code instead of as a string in the heredoc, and `yes` will never halt.

All the weird whitespace around each `yes` is to make them all distinct and remain as short as possible (mostly 4 bytes).

If any of the `yes` programs is removed, there won't be a `36` in the output so the `until` will loop forever.

## Notes

* `yes` is intended to output `y` indefinitely so it can be piped into an interactive program that asks yes-or-no questions, but in this case it doesn't matter what it outputs
* `<<Q` actually only outputs the contents until the first line containing only `Q`, but there is no such line, so it just goes until the end of the file
* The exact splitting of the program is as follows; a `#` is used to separate each one here

```
until wc<<Q|grep 36
#yes

#yes;#yes #yes  #yes# yes# ;yes#
yes#    yes

```

Notice all the quirky whitespace, and there's a tab in there somewhere.

One of the programs is  `;yes`; it could just be `;yes` with no space, except in the case the only remaining programs are `yes;;yes`: zsh would throw a syntax error because `;;` is treated as one token instead of two semicolon command separators.

---

# Zsh, 107 bytes, 10 programs

```
while 1=u
while 1+=i
while 1+=l
while 1+=t
while 1+=in
while 2=e
while 2+=x
while 2+=i
while 2+=t
until b$@

```

Try it online!

Try it onlin

Tryine!

nline!

Each line is a program.

## Explanation

The idea is to use an infinite loop (well, 10 nested infinite loops), but, over the course of the 10 programs, construct and execute a string that will exit the loops.

If any program is removed, the string will no longer be a snippet that correctly exits, and the program will continue to loop.

The code to halt is built up by `1=u` `1+=i` etc. The string `uiltin` is stored in `$1`, and `exit` is stored in `$2`. Then, `$@` represents all the assigned numeric variables; a `b` is prepended to those to make `builtin exit`, which is executed and halts the program.

## Notes

* All the loops have no body - the code is entirely in the condition. Zsh seems not to care, though.
* The challenge states:

> A program is *valid* if \[...\] an interpreter finishes any pre-execution check (syntax parser, type checker, and any others if present) without error.

Despite producing lots of errors, the program(s) meet these criteria because they only occur at *runtime*. (that kind of comes with the territory when golfing in zsh)

* The `b` is prepended at execution instead of being made part of the string build-up, because it prevents the program where only `2` gets assigned to from halting - it will always result in `bexit` instead of `exit` (this is essentially a problem of irreducibility). There are also some substrings of `uiltin exit` that might be valid commands, which could end the `until` loop, but none exist once a `b` is prepended.
* `builtin` is a pre-command modifier that disambiguates in case `exit` is a user-defined function, but in this case it serves only to get us to 10 programs of which none can be removed.
* `in` is appended in one go instead of `i` and `n` separately because the 10 programs must be distinct, and `1+=i` is already used.
* For the first assignments to `1` and `2`, we can use `=` instead of `+=` to save a byte.
> 20 votes

# Answer
# Befunge-93, ~~25~~ 22 bytes (10 programs)

```
12+3+4+5+6+7+8+"#"`#@_

```

Try it online!

Thanks JoKing for the suggestion (-3 bytes).

**Exaplanation**

The programs are:

```
1     Push 1
2     Push 2, pop two value and push the sum
+     Pop two value and push the sum
3+    Push 3, pop two value and push the sum
4+    Same with 4
5+    ...
6+
7+
8+
"#"`#@_    Last program, it will halt if the stack has a number >35 in it:
           "-"        Push 35
           `          Pop two value, compare, push 1 if greater than 35
           #          Skip the next char (v)
           @          End program
           _          Pop one value, go left if 1, right otherwise

```

The first 9 programs cannot halt, because there is no halt instruction.
The last program takes a number from the stack, and compares it to 35: if it is greater than 35 (the sum is 36), then will halt the program; otherwise, it will let the PC run right, which will repeat the program and loop forever.

Removing any combination of program 1 to 9 will make the sum to be less than 36, so the program will never halt (comparison will always fail).

In theory, it can be extended by adding more number, and changing the value of the comparison in the last program (depending on the size available in your Befunge implementation).

---

# Befunge-93, ~~63~~ 73 bytes (10 programs)

```
 v
v>v
v >v
v  >v
v   >v
v    >v
v     >v
v      >v
v       >v
v       v@

```

Try it online!

Thanks NickKennedy for the fix.

**Explanation**

Each line is a program.

The first 9 lines (i.e. programs) are redirecting the PC down. Since there is no end of program instruction, they will loop forever.

The 10th line is redirecting the PC down, followed by an halt program (@) instruction. If this is executed alone, the PC will loop in the vertical direction forever.

When all together, the PC will be able to get to the @ and halt the program.

Removing any one line will break the flow and will leave the PC loop forever vertically.

It can actually be expanded to 25 programs (which is the limit of the 80x25 code size of the befunge) by just adding more `v >v` lines with the appropriate indentation.

If you use an implementation of befunge without the 80x25 limit, then it can be exdended indefinitely.
> 14 votes

# Answer
# JavaScript, 10 programs / 271 bytes

*Saved 12+ bytes per program thanks to @tsh*

This is similar to the method used by @darrylyeo in this answer.

```
o={get g(){while(k);},set go(_){k--;}};k=9;o.g
o={get g(){for(;;)0}};o.g
o={get g(){for(;;)1}};o.g
o={get g(){for(;;)2}};o.g
o={get g(){for(;;)3}};o.g
o={get g(){for(;;)4}};o.g
o={get g(){for(;;)5}};o.g
o={get g(){for(;;)6}};o.g
o={get g(){for(;;)7}};o.g
o={get g(){for(;;)8}};o.g

```

Try it online! (non-halting)

Try it online! (halting)
> 12 votes

# Answer
# JavaScript (V8), 10 programs, 188 bytes

```
for(b=('a'in this);!b;);
for(c=this.b;!c;);
for(d=this.c;!d;);
for(e=this.d;!e;);
for(f=this.e;!f;);
for(g=this.f;!g;);
for(h=this.g;!h;);
for(i=this.h;!i;);
for(j=this.i;!j;);
for(var a;!this.j;);

```

Try it online! (all, halts)

Try it online! (not all, does not halt)

Javascript hoists the definition of `a` to the top of the scope, so even though it is defined later `'a' in this` returns `true`.
> 12 votes

# Answer
# Pyth, 10 programs, 23 bytes

* `Wn17l"`
* `#`
* `#1`
* `#2`
* `#3`
* `#4`
* `#5`
* `#6`
* `#7`
* `#8`

Try it online!

### How it works

With all programs present, the concatenation is equivalent to this halting Python loop:

```
while 17 != len("##1#2#3#4#5#6#7#8"):
    pass

```

If the first program is present but another is missing, the string will no longer have length 17 and the loop will run forever.

If the first program is missing but another present, the concatenation begins with `#`, which loops a block until an error is raised (which will never happen):

```
while True:
    try:
        while True:
            try:
                print(1)
                while True:
                    try:
                        print(2)
                        while True:
                            try:
                                print(3)
                                while True:
                                    try:
                                        print(4)
                                        while True:
                                            try:
                                                print(5)
                                                while True:
                                                    try:
                                                        print(6)
                                                        while True:
                                                            try:
                                                                print(7)
                                                                while True:
                                                                    try:
                                                                        print(8)
                                                                    except Exception:
                                                                        break
                                                            except Exception:
                                                                break
                                                    except Exception:
                                                        break
                                            except Exception:
                                                break
                                    except Exception:
                                        break
                            except Exception:
                                break
                    except Exception:
                        break
            except Exception:
                break
    except Exception:
        break

```
> 10 votes

# Answer
# GNU sed, 10 programs, 99 bytes

```
:a s/^/A/
ba

```

```
:a :b bb

```

```
:b :c bc

```

```
:c :d bd

```

```
:d :e be

```

```
:e :f bf

```

```
:f :g bg

```

```
:g :h bh

```

```
:h :i bi

```

```
:i :j s/A//
Tj

```

## Explanation

Meta consensus lets sed programs take a single empty line as input (for, without that, sed simply won't do anything at all)

So, evidently, GNU sed will just let you define the same label multiple times, and all except the last one are ignored for execution purposes, which is nice for this challenge. Programs 1 through 9 each define a simple infinite loop (Program 1 does a bit more, which we'll get to in a minute)

```
:a ba

```

This defines a label `:a` and `ba` is effectively a `goto :a`. This program does nothing but loop forever. Then if we concatenate the second

```
:a ba :a :b bb

```

Now the `ba` goes to the *second* `:a` label, which effectively does nothing, and then we loop on `:b` forever. Each program "disarms" the prior one and them introduces its own loop.

Now, the final program

```
:i :j s/A//
Tj

```

First, we disarm the `:i` loop from the ninth program. Then we try to remove an `A` from the pattern space. The pattern space started out containing an empty string (remember, our input is a single empty line), so if we run Program 10 on its own, this substitute will *fail*. `Tj` is a conditional jump. It's a `goto :j` that only executes if the previous substitution *failed*. This is an infinite loop.

However, if Program 1 is in play, then the first thing we did was introduce an `A` at the beginning of the pattern space, which Program 10 happily removes and then the `Tj` doesn't execute since the substitution was successful.

The only way a concatenation of these programs can terminate is if the following conditions are met.

1. For N from 1 to 9, Program N contains an infinite loop trap that we can only escape if Program (N+1) is present.
2. Program 10 contains an infinite loop trap that we can only escape if Program 1 is present.

Hence, a nonempty concatenation terminates if and only if all ten programs are present.
> 8 votes

# Answer
# Bash, 10 programs, 390 bytes

```
trap "while(($[a+=1]<55));do :;done" 0
trap "while(($[a+=2]<55));do :;done" 0
trap "while(($[a+=3]<55));do :;done" 0
trap "while(($[a+=4]<55));do :;done" 0
trap "while(($[a+=5]<55));do :;done" 0
trap "while(($[a+=6]<55));do :;done" 0
trap "while(($[a+=7]<55));do :;done" 0
trap "while(($[a+=8]<55));do :;done" 0
trap "while(($[a+=9]<55));do :;done" 0
trap "while(($[a+=10]<55));do :;done" 0

```

Try it online!

## How?

Each line contains an exit handler that contains a while loop. The while loop will only halt if all the numbers 1..10 have been added to the variable $a. If any lines are missing, then the while condition will be true and will not halt.
> 7 votes

# Answer
# Jelly, 10 programs, ~~37~~ 35 bytes

```
L}n27$¿“¹1¿¹2¿¹3¿¹4¿¹5¿¹6¿¹7¿¹8¿¹9¿

```

Try it online!

## Individual programs with explanation

```
L}n27$¿“ | While not 27, take the length of the right argument
¹1¿ | While 1 do the identity function
¹2¿ | While 2 do the identity function
¹3¿ | While 3 do the identity function
¹4¿ | While 4 do the identity function
¹5¿ | While 5 do the identity function
¹6¿ | While 6 do the identity function
¹7¿ | While 7 do the identity function
¹8¿ | While 8 do the identity function
¹9¿ | While 9 do the identity function

```

When the whole lot is concatenated together, this checks the length of the string between  and the end of the program is 27.

Any subsequence of these programs that does not include the first has an infinite while loop, while programs including the first one will only halt if all of the others are present so that the length is correct.
> 7 votes

# Answer
# Gol\>\<\>, score 10, 11 bytes

```
90.123456!;

```

Try it online!

At 1 point short of perfect this is as close as I can come in Gol\>\<\>.

The first 9 characters `90.123456` are all their own programs with `!;` being the only two byte program.

Since it contains the only halt instruction `!;` must be included to halt. And since it has a `!` we can't simply get to `;` from the right. The only other way to get to `;` is with the teleport `.`. So `.` must be included as well. If `.` is first it will pop two zeros and teleport to itself creating an infinite loop, so something must be present before it. `0` causes the same type of infinite loop as before so `9` must be present as well. Now `0,9` is a location that can never be filled since we have no newlines. Thus any jump there creates an irretrievable infinite loop, we must have the `0` program as well. Now we know the `.` must take us to `9,0`, and of course `;` must be the character there. In order for this to happen we must have all the characters present.

This is the perfect score for Gol\>\<\> because if it were 10, 1 byte programs there would have to be a 1 byte program which halts on it's own. As suggested by @Bubbler it might be possible to use source modification to insert a halt command, however since unknown commands crash Gol\>\<\> a `p` on it's own will override itself with a zero byte and halt with a crash.
> 7 votes

# Answer
# Python 3.8 (pre-release), 10 programs, ~~206 196~~ 174 bytes

## Whole program: (174 bytes)

```
i=1
while i:
 0#while 1:
 i=-8#while i:=2:
 i+=1#while i:=3:
 i+=1#while i:=4:
 i+=1#while i:=5:
 i+=1#while i:=6:
 i+=1#while i:=7:
 i+=1#while i:=8:
 i+=1#while i:=9:
 i+=1

```

Try it online!

## Program 1: (16 bytes)

```
i=1
while i:
 0#

```

## Program 2: (14 bytes)

```
while 1:
 i=-8#

```

## Program 3 to 9: (18 char each)

```
while i:=2:
 i+=1#

```

...

```
while i:=8:
 i+=1#

```

## Program 10: (17 char)

```
while i:=9:
 i+=1

```

## How it works:

* we set i to 1
* In the first program: `while i: 0` if `i` is not equal to `0` (wich is True at the start) we loop into the program. Otherwise the program finish.
* In the second program, if the first program is missing, `while 1` will loop indefinitely. We assign `i` to -8. If the second program is missing, `i` will always be strictly positive and the program will loop indefinitely
* Then we increment `i` by `1` inside the first while loop and comment to neutralize the next `while` statement
* If all 10 programs have been executed, `i` is now equal to `0` and the program stop. Otherwise, the program loops and `i` is set back to `-8` in the seacond loop or will continue to be incremented.

thanks to Bubbler, who pointed me that programs should all be differents, which ended saving me many bytes :p

Thanks to Wheat Wizard♦ which inspired me to improve my solution

# Python 3.8 (pre-release), 10 programs, 127 bytes

The solution where the program reads its own source code I found is:

```
while len(next(open(__file__)))<127:0#while 1:0#while 2:0#while 3:0#while 4:0#while 5:0#while 6:0#while 7:0#while 8:0#while 9:0

```

Try it online!

It is ... well ... a solution. Not clever, not even beautiful, but it is accepted so ...

### First program :

```
while len(open(__file__).read())<127:0#

```

exit if the program is at least 127 char long. Else loop

### Program 2 to 9:

```
while 1:0#

```

...

```
while 8:0#

```

Just infinite loop

### Program 10:

```
while 9:0

```

Same but without comment
> 6 votes

# Answer
# Labyrinth, score 10, 19 bytes

```
0       @
+-*&|$`"'

```

Try it online!

Since Labyrinth programs operate by following the path formed by valid commands, solving this challenge in Labyrinth in its simplest form is about making sure the starting cell (the leftmost cell of the topmost row) is disconnected from the halt command `@` unless every piece appears in the program.

Whenever I thought I found something clever (which had 16 or 17 bytes), I was hit with a weird shortcut path. Also it doesn't help that a comment-only program isn't an infinite loop (the interpreter simply refuses to run it). So I decided to settle with this one, at least for now. (At least it's an improvement over the initial idea of 21 bytes)

```
0+-*&|$`"'
         @

```

---

The fragments are:

```
0       @\n
+
-
*
&
|
$
`
"
'

```

Since every comment-only program halts, every fragment must contain at least one valid command. To avoid memory issues, the commands to form the no-op path were chosen so that the stack size or the number size doesn't grow infinitely when repeated.

```
     All commands that pop and push something on the stack push a single 0
     when run as the first command, and effectively do nothing otherwise
0    Multiply the top by 10 and add 0 (0 * 10 + 0 = 0)
+    Add two numbers (0 + 0 = 0)
-    Subtract two numbers (0 - 0 = 0)
*    Multiply two numbers (0 * 0 = 0)
&    Bitwise & two numbers (0 & 0 = 0)
|    Bitwise | two numbers (0 | 0 = 0)
$    Bitwise ^ two numbers (0 ^ 0 = 0)
`    Negate top (-0 = 0)
"    No-op
'    Debugging no-op

```

It is obvious that we need the first program fragment (the only one containing `@`) to possibly halt. Then, since the `0` is the starting location, we need all the other 9 fragments to connect `0` to `@`.
> 6 votes

# Answer
# Haskell, score 10, 227 bytes

```
main=a;a=a where a=b;main=main;b=b where b=c;main=main;c=c where c=d;main=main;d=d where d=e;main=main;e=e where e=f;main=main;f=f where f=g;main=main;g=g where g=h;main=main;h=h where h=i;main=main;i=i where i=pure();main=main

```

Try it online!

Each program ends after the `where`  except the last which just ends.

Here it is in a more readable manner.

```
main=a
a=a where
  a=b
  main=main
  b=b where
    b=c
    main=main
    c=c where
      c=d
      main=main
      d=d where
        d=e
        main=main
        e=e where
          e=f
          main=main
          f=f where
            f=g
            main=main
            g=g where
              g=h
              main=main
              h=h where
                h=i
                main=main
                i=i where
                  i=pure()
                  main=main

```

Try it online!

# Explanation

The idea here is to use variable shadowing to create a chain of assignments. If the chain is broken the shadow means that we switch and define the variable in terms of itself an form a loop.

This is easier to see for just two programs.

```
main=a;a=a where a=pure();main=main

```

With just the first program

```
main=a;a=a where

```

`a` is a loop so `main` is a loop. But when we add the second `a` gets shadowed and now `a` is a halting program. We do this several times each time changing the variable names so that the nothing can shadow something it is not supposed to.
> 5 votes

# Answer
# Lost, Score 2, 5 bytes

```
/%
@/

```

Try it online!

The programs are

```
/%

```

and

```
@/

```

This works because any lost program that halts must have both `%` and `@`. Since `%` turns off the safety to allow halting and `@` actually does it. The simpler `%@` doesn't work because half the time the pointer is moving vertically and can only hit one of the two. In fact in order to *always* halt a lost program needs some kind of redirect in every column and row (technically there are some specific exceptions to this but lets not get into them), meaning that this is certainly the smallest program that always halts.

So we can't go shorter for score 2. But ...

# Lost, Score 3, 5 bytes

```
%^
@>

```

Try it online!

... we can increase the score at no cost to bytes!

The programs here are:

```
%^

```

```

```

```
@>

```

The second one being a single newline.

This is one of the specific exceptions to the one redirect in every row and column rule. It's the same length, but both of our redirects are in the same column since the other column automatically terminates by itself.

A program needs both `%` and `@` to halt at all so any program missing one of the first two mustn't halt. So we only need to check the case where program 2 is missing.

```
%^@>

```

Here there is no possible path from the `%` to the `@`. The redirects ensure it. So there is no way for this program to halt.

And of course this can't be beat since you can't make a shorter halting program.

# Lost, Score 4, 7 bytes

```
%\<
<@^

```

Try it online!

Nothing much special here it's a modified version of the above. There might be a smaller program that scores 4. I'm not sure.

The programs here are

```
%

```

```
\

```

```
<

```

```
<@^

```

Once again since a program *needs* `%` and `@` to work so we have only to check

```
%<@^

```

```
%/<@^

```

```
%<
<@^

```

None of which halt.

# Lost, Score 10, 19 bytes

```
%<ABCDE\<
<<<<<<<@^

```

Try it online!

And here we have an extensible solution, adding 2 bytes for every 1 score (until we run out of noop bytes). It is modified from the score 4 solution. The programs are

```
%<

```

*Each letter is 1 program for 5 total*

```
\

```

```
<

```

```
<<<<<<

```

```
<@^

```

The first and last program are necessary because they have the `%` and `%`. Without the newline we will have something like

```
%<...<@^

```

Which can never have a path from `%` to `@`, so the newline is needed too. We can also treat the letters as interchangeable since they are all noops, so we are only concerned with *how many* letters are present. At this point we can say that the only way for a program made from these to halt is if `/` is exactly above the `@`. Since it can't approach from the left or the right due to `<` and `^`, and there is no other way to get a vertical direction on the first row. This tells us that `/` must be present, but also gives us a quick way of checking the programs.

Unfortunately there are still quite a few programs to check. In fact more than I think I want to list in this post. The checks are easy given what I've already shown so please have a go yourself if you doubt my work.
> 4 votes

# Answer
# Lenguage, 10 programs, 2324143350556659959 bytes

```
     -[]++++++++++++++++++
      --[]++++++++++++++++
        --[]++++++++++++++
          --[]++++++++++++
            --[]++++++++++
              --[]++++++++
                --[]++++++
                  --[]++++
                    --[]++
+)                    -.[]
---------------------------
     >+-+-+-+-+-+-+-+-+<[]
     201010101010101010367

```

Lacking the i-th program (\\$i \in \[2,10\]\\$), `>+-+-+-++[]` pattern appears (`-[]` when i=2).

Lacking the first several programs, `->+-+-+-+<[]` pattern is still an infinite loop, or `-.[]` if only the 10th one left, still infloop
> 4 votes

# Answer
# Vyxal, 4 bytes, 2 programs.

## #1

```
{

```

Try it Online! Simple forever loop. The `5` flag makes it terminate after 5 seconds so it doesn't jam up the interpreter.

## #2

```
0|{

```

Try it Online! Another simple loop.

## Halting program

```
{0|{

```

Try it Online!

This works because `|` is a branch in structure when in a structure, but does nothing when in the main scope. So in the second one, it pushes 0 then executes a forever loop, but in here, it executes a loop containing a forever loop with 0 as the condition, so the inside loop is never run and the program halts.

Note that like TIO, the Vyxal interpreter times out after 60 seconds to avoid breaking, but if that was removed these two would run forever.
> 3 votes

# Answer
# Vyxal, 19 bytes / 3 programs

## #1

```
`{`{`

```

Try it Online!

## #2

```
{`{`

```

Try it Online!

## #3

```
`0|}0|{`{`

```

Try it Online!

## Concatenated

```
`{`{`{`{``0|}0|{`{`

```

Try it Online!

A quite different approach to what I had before.

With NOPS removed, it becomes:

```
{        # While...
 {  }    # While
  0      # 0
   |     # Do nothing
     0   # 0
      |  # Do..
       { # Forever loop, never executed

```
> 3 votes

# Answer
# \[Scala Interpreter\], 10+ programs, 265 bytes

This challenge is impossible to solve in languages that require a global program body around their code.

Luckily, Scala *Interpreter* is a way to bypass this issue :)

However, the challenge is still hard to solve in a language that requires to declare variables before using them and that does not provide a simple global mutable context to share information between the subprograms. However, the necessary information sharing can be achieved indirectly by affecting the global state of the JVM.

So, here are the 10 programs (one per line). Of course, it can be extended to any number of programs:

```
new java.util.Timer("1");
new java.util.Timer("2");
new java.util.Timer("3");
new java.util.Timer("4");
new java.util.Timer("5");
new java.util.Timer("6");
new java.util.Timer("7");
new java.util.Timer("8");
new java.util.Timer("9");
while(Thread.activeCount!=10){};sys.exit

```

**Explanation**: Every instantiation of a new Timer creates a new background thread that prevents the program from stopping. Further, the 10th program runs forever if the number of threads (incl. main thread) is not 10. Thus, the total number of threads is the indirectly affected "global variable" here.

No concatenation of 1..9 programs halts, for example:

* `scala -e 'new java.util.Timer("2");'`
* `scala -e 'new java.util.Timer("1");new java.util.Timer("5");'`
* `scala -e 'while(Thread.activeCount!=10){};sys.exit'`
* `scala -e 'new java.util.Timer("4");while(Thread.activeCount!=10){};sys.exit'`

Only when concatenating all 10 sub-programs, the resulting program will halt.

You can try out this behavior in TIO:

Try it online!

This approach does also work via Copy&Paste into the Scala REPL or to some Scala IDE, but then you need to replace the literal `10` by `11`, since in this case another JVM thread is running in the background :)
> 3 votes

# Answer
# TypeScript Types, 10 programs, 630 bytes

```
interface X{a:keyof{b,c,d,e,f,g,h,i,j}extends keyof X?0:X["a"]}
interface X{b:keyof{a,c,d,e,f,g,h,i,j}extends keyof X?0:X["b"]}
interface X{c:keyof{a,b,d,e,f,g,h,i,j}extends keyof X?0:X["c"]}
interface X{d:keyof{a,b,c,e,f,g,h,i,j}extends keyof X?0:X["d"]}
interface X{e:keyof{a,b,c,d,f,g,h,i,j}extends keyof X?0:X["e"]}
interface X{f:keyof{a,b,c,d,e,g,h,i,j}extends keyof X?0:X["f"]}
interface X{g:keyof{a,b,c,d,e,f,h,i,j}extends keyof X?0:X["g"]}
interface X{h:keyof{a,b,c,d,e,f,g,i,j}extends keyof X?0:X["h"]}
interface X{i:keyof{a,b,c,d,e,f,g,h,j}extends keyof X?0:X["i"]}
interface X{j:keyof{a,b,c,d,e,f,g,h,i}extends keyof X?0:X["j"]}

```

Try It Online! (with one program removed)

Each line is its own program, and newlines between the programs are optional.

"Does not halt" is hard to define in TypeScript Types, so this uses the closest analog: a type that resolves to itself, resulting in an infinite loop.

Technically, the 'interpreter' still halts, but with an error; if this is problematic, than this program can be considered to be written in TypeScript Types\*, which is like TypeScript Types except any errors cause the 'interpreter' to never halt.

Note that this requires the flag `noImplicitAny: false`; this is the default in `tsc` itself, but not in the playground.
> 3 votes

# Answer
# Charcoal, 96 bytes, score 10

```
Ｗα«≔⁻αAαＷα«≔⁻αBαＷα«≔⁻αCαＷα«≔⁻αDαＷα«≔⁻αEαＷα«≔⁻αFαＷα«≔⁻αGαＷα«≔⁻αHαＷα«≔⁻αIαＷα«≔⁻αJKLMNOPQRSTUVWXYZα

```

Try it online! Explanation: Each loop subtracts a different substring of the predefined uppercase alphabet, so the program will only finish if all of the letters get subtracted. The programs can of course be concatenated in any order. As ten separate programs:

```
Ｗα«≔⁻αAα
Ｗα«≔⁻αBα
Ｗα«≔⁻αCα
Ｗα«≔⁻αDα
Ｗα«≔⁻αEα
Ｗα«≔⁻αFα
Ｗα«≔⁻αGα
Ｗα«≔⁻αHα
Ｗα«≔⁻αIα
Ｗα«≔⁻αJKLMNOPQRSTUVWXYZα

```

This can be trivially extended to 26 programs by subtracting each letter separately. Furthermore, this can be trivially extended to 95 programs by subtracting from the whole printable ASCII character set instead of just the uppercase alphabet. (It might even be possible to extend this up to 150 programs by mixing the approaches.)
> 2 votes

# Answer
# Julia 0.6, 10 programs, ~~275~~ 256 bytes

```
!x=while x<1end
e+=1
!01
!x=while x*e<4end
e+=1
!01
!x=while x*e<5end
e+=1
!01
!x=while x*e<6end
e+=1
!01
!x=while x*e<7end
e+=1
!01
!x=while x*e<8end
e+=1
!01
!x=while x*e<9end
e+=1
!01
!x=while x*e<10end
e+=1
!01
!x=while x*e<11end
e+=1
!01
while e<11end

```

Try it online!

ry it online!

Try it line!

Try it onlin!

the separation between the programs is between each `!0` and `1`

uses Julia 0.6 to be able to redefine `e` (the euler constant)
> 2 votes

# Answer
# , 10 programs, ~~156~~ 151 bytes

```
while(T<-T*2)1-while(T<-T^2)1-while(T<-T*3)1-while(T<-T*4)1-while(T<-T*5)1-while(T<-T*6)1-while(T<-T*7)1-while(T<-T*8)1-while(T<-T*9)1-while(T<-T<6e5)1

```

Try it online!

## Separate programs:

```
while(T<-T*2)1
while(T<-T^2)1
-while(T<-T*3)1
-while(T<-T*4)1
-while(T<-T*5)1
-while(T<-T*6)1
-while(T<-T*7)1
-while(T<-T*8)1
-while(T<-T*9)1
-while(T<-T<6e5)1

```

The full program works by starting with T (which starts at `TRUE` and becomes 1 when used arithmetically) and then multiplied by each number from 2 to 9 as well as squaring it (after `T<-T*2`). The last program compares T to 6e5, at which point all of the comparisons will equal 0.

Separately, no combination of programs will ever reach 0 since anything excluding the last program will just head for +infinity, while any combination including the last program will evaluate to `TRUE` unless all of the prior programs were present.

If any subsequence without the first program did complete its `while` loop, the unary minus would throw an error, but since they never do, no error is generated.

Thanks to @RobinRyder for saving a byte!
> 2 votes

# Answer
# Forte, 10 programs, 96 bytes

```
9LET0=1
10LET1=2
11LET2=3
12LET3=4
13LET4=5
14LET5=6
15LET6=7
16LET7=8
17LET8=21
20LET21=0
21END

```

Each line is a program, except that the last two lines together constitute the tenth program.

### Explanation

Forte is a language built around redefining numbers. Execution control is achieved by redefining line numbers, thereby shuffling statements around.

The only way to exit is via the `END` statement. So right off the bat, if the tenth program is missing, there is no way to exit and the program loops forever.

If the tenth program is present but one of the earlier programs is missing, the `LET` statement on line 20 redefines the number 21 to be some value between 0 and 8 (depending on which of lines 9 through 16 were able to run). Since this number is less than the current line number of 20, the `END` statement moves to before the instruction pointer and is never executed. The program proceeds to loop infinitely.

If all ten programs are present, lines 9 through 17 redefine 0 (through a series of steps) to equal 21. Then line 20 redefines 21 to equal 21 (no change). Execution proceeds to line 21, which ends the program.

<sup>(I'm not sure whether all implementations of Forte will behave this way, but Forter, the version on TIO, does. This behavior seems to be in line with the description in the Esolangs article, too.)</sup>
> 2 votes

# Answer
# Perl 5, 10+ programs, 184 bytes

```
BEGIN{s//t/}{redo}BEGIN{s//i/}{redo}BEGIN{s//x/}{redo}BEGIN{s//4/}{redo}BEGIN{y/4/5/}{redo}BEGIN{y/5/6/}{redo}BEGIN{y/6/7/}{redo}BEGIN{y/7/8/}{redo}BEGIN{y/8/e/}{redo}BEGIN{eval}{redo}

```

Try it online!

With newlines added for readability:

```
BEGIN{s//t/}{redo}
BEGIN{s//i/}{redo}
BEGIN{s//x/}{redo}
BEGIN{s//4/}{redo}
BEGIN{y/4/5/}{redo}
BEGIN{y/5/6/}{redo}
BEGIN{y/6/7/}{redo}
BEGIN{y/7/8/}{redo}
BEGIN{y/8/e/}{redo}
BEGIN{eval}{redo}

```

`{redo}` is a short infinite loop in perl. `BEGIN` blocks run before everything else, so all we need to do is exit from a `BEGIN` block.

To do this, we build the string `exit` and then `eval` it in a `BEGIN` block. `s//whatever/` is a concise way to prepend `whatever` to the global variable `$_`, and then `eval` evaluates that string. The first four programs set `$_` to `4xit` and then the next programs use the transliteration operator `y///` to successively change the `4` to various other numbers and finally to `e`.

Anything besides `exit` will do nothing when `eval` is run, and of course removing `eval` will keep the program from exiting, so the program will run forever.

This method can be extended to an arbitrary number of programs with additional uses of `y///` and `s///`.
> 2 votes

# Answer
# Vyxal, 10 progs, 27 bytes, take 3.

```
{`{
{1
{2
{3
{4
{5
{6
{7
{8
`L17<|`{

```

Try it Online!

I finally figured out what the others are doing. This basically checks if the string between the backticks' length is 17, and if not loops forever.

No trailing newlines, they're just formatted like this for readability.

Any character except `X` and `|` can be used instead of the digits.
> 1 votes

# Answer
# Charcoal, 36 bytes, score 6

```
≔⁰ψＷα«≔⁰αＷβ«≔⁰βＷγ«≔⁰γＷφ«≔⁰φＷχ«≔⁰χＷψ«

```

Try it online! Explanation: This is the concatenation of six six-byte programs. Each program sets a predefined variable to zero and then loops over another predefined variable. This means that no program will finish except for the concatenation of all six, which will ensure that all of the predefined variables are set to zero, causing all of the loops to terminate. (Concatenating the programs in a different order won't work because the first program will prevent the final program's loop from executing, preventing further programs from clearing the first program's loop variable.) As six separate programs:

```
≔⁰ψＷα«
≔⁰αＷβ«
≔⁰βＷγ«
≔⁰γＷφ«
≔⁰φＷχ«
≔⁰χＷψ«

```
> 1 votes

# Answer
# PHP, 10+ programs; ~~342~~ ~~134~~ ~~127~~ ~~124~~ ~~123~~ 116 bytes.

Byte count for PHP assumes you don't require and count the 8 characters of the surrounding `<?php ?>` tags for each program; if so, add 80 bytes.

```
while(!file(__FILE__)[9]);die();
for(;;);
foR(;;);
fOr(;;);
fOR(;;);
For(;;);
FoR(;;);
FOr(;;);
FOR(;;);
while(1);

```

I realized that `FOR` is case-insensitive, so I could use seven more unique `for`s, saving 7 bytes.
> 1 votes

# Answer
# Ruby, 114 bytes, 10 programs

```
1/($.-40)while 99while$.+=11while$.+=07while$.+=06while$.+=05while$.+=04while$.+=03while$.+=02while$.+=01while$.=1

```

Try it online!

The programs break down like this:

```
1/($.-40)while 9

```

```
9while$.+=1

```

```
1while$.+=0

```

```
7while$.+=0

```

...

```
1while$.=1

```

The `1/($.-40)` causes a `ZeroDivisionError` if all the other snippets successfully incremented the counter `$.` to `40`, breaking out of all of the loops. If any parts are missing, `$.` will be less than `40` and the division will work, so the program will continue to loop.

Because the inner loop never terminates, the outer loops can never increment `$.` more than once, so there's no opportunity for `$.` to reach 40 except if all the programs are there.

Try nline!

y it online!

Tre!
> 1 votes

# Answer
# Klein 000, Score 10, 17 bytes

```
ABCDEFG\
....!><@

```

Try it online!

This is a modification of my lost answer so to get a good idea of how this works I recommend reading that explanation. Since Klein is not a language designed to torture the programmer, this ends up being 2 bytes shorter.

The programs are:

*The 7 letters*

```
\

```

```

```

*(Just a newline)*

```
....!><@

```

This works of an alignment principle. The `/` has to be above the `@` or you are not going to reach it. There are some special bits `!><` for example is a trap that catches anything going rightwards, which is there for when the newline is removed.
> 1 votes

# Answer
# Befunge-93, 10 programs, 13 bytes

```
~1\-2*4+7`#@_

```

Try it online!

I think there's at least one more byte that can golfed off this. 9 of the programs are one byte apiece, with the last being `7`#@`. The initial `~1\-2*4+` generates the number `8`, with any lesser combination generating a smaller number. This then uses the `7`#@_` to only terminate if the number is bigger than 7. Note that if the `7`#@` section is removed, the program has no way to terminate, and if the `_` is removed, there is no way for the pointer to travel left, and therefore no way to execute the `@`.
> 1 votes

# Answer
# Perl 5, 10 programs, ~~179~~ 175 bytes

```
END{{redo}}use POSIX;END{{redo}}s//)/;END{{redo}}s//0/;END{{redo}}s//(/;END{{redo}}s//_exit/;END{{redo}}s//::/;END{{redo}}s//SIX/;END{{redo}}s//O/;END{{redo}}s//P/;eval;{redo}

```

Try it online!

For readability, here's the same program with newlines:

```
END{{redo}}use POSIX;
END{{redo}}s//)/;
END{{redo}}s//0/;
END{{redo}}s//(/;
END{{redo}}s//_exit/;
END{{redo}}s//::/;
END{{redo}}s//SIX/;
END{{redo}}s//O/;
END{{redo}}s//P/;
eval;{redo}

```

Builds the string `POSIX::_exit(0)` and evals it. `END` blocks always run at the end of a program even if there was an error, but `POSIX::_exit` skips this.
> 0 votes

---
Tags: code-challenge, source-layout, halting-problem
---


title: Ethiopian Multiplication

text:
# Question
Title: Ethiopian Multiplication
This question is inspired by this answer. Coincidentally, I used to use Ethiopian Multiplication when I was a kid, but had never known the name of the method until recently.

Ethiopian multiplication is a method of multiplying integers using only addition, doubling, and halving.

**Method:**

1. Take two numbers to be multiplied and write them down at the top of two columns.
2. In the left-hand column repeatedly halve the last number, discarding any remainders, and write the result below the last in the same column, until you write a value of 1.
3. In the right-hand column repeatedly double the last number and write the result below. stop when you add a result in the same row as where the left hand column shows 1.
4. Examine the table produced and discard any row where the value in the left column is even. Sum the values in the right-hand column that remain to produce the result of multiplying the original two numbers together.

For example: 17 x 34

```
17    34

```

Halving the first column:

```
17    34
 8
 4
 2
 1

```

Doubling the second column:

```
17    34
 8    68
 4   136
 2   272
 1   544

```

Strike-out rows whose first cell is even, we'll do this by encasing those numbers on the right in square brackets:

```
17    34
 8   [68]
 4  [136]
 2  [272]
 1   544

```

Sum the remaining numbers in the right-hand column:

```
17    34
 8   [68]
 4  [136]
 2  [272]
 1   544
    =====
     578

```

So 17 multiplied by 34, by the Ethiopian method is 578.

**The Task:**

Golf code that takes two numbers between 1 and 1000 and perform the same layout and algorithm, displaying the product below.

Input Method: However you choose...

Example Input:

```
19 427

```

Resulting Output:

```
19   427
 9   854
 4 [1708]
 2 [3416]
 1  6832
   ======
    8113

```

Please note the alignment of the digits. This is most important in the layout. Also note that the double line laid out by equal signs must be two characters longer than the overall answer and must be centre justified.

**Testing**

How will you be testing this? By providing a run of your program using two numbers. These numbers can be extracted from your user ID number (this can be obtained by hovering your cursor over your avatar on the top window). Take your number and take the last three digits, this will be number B, take whatever else remains at the front, that will be number A. Then test for A times B.

Testing example:

My user ID number is 8555, so my numbers are 8 and 555. So my output should look like this:

```
8  [555]
4 [1110]
2 [2220]
1  4440
  ======
   4440

```

**Restrictions:**

No native multiplication operators permitted save for in the use of "doubling", as per mentioned in the algorithm. In other words, if you're using an operator like \*, it can only be used for multiplying by 2 only.

Entries that do not adhere to this will not be considered and the user will be escorted off the premises with a cardboard box full of their belongings. Each entry will have code, plus the test based on your user ID number.

This is code golf. Shortest number of bytes will receive the prize, glory and admiration of their peers... (And maybe a Lamborghini... I said "maybe"!)

# Answer
# Charcoal, 91 bytes

```
≔⟦⟧τ≔⁰σＮθＮηＷθ«⊞τ⪫  Ｉθ⊞υ⪫⎇﹪θ²  ¦[]Ｉη≔⁺σ∧﹪θ²ησ≔÷θ²θ≔⁺ηηη»⊞υ…=⁺²ＬＩσ⊞υ⪫  Ｉσ←Ｅ⮌τ⮌ιＭ⌈ＥυＬιＬυ←Ｅ⮌υ⮌ι

```

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

```
≔⟦⟧τ≔⁰σ

```

Sets `t` to the empty list and `s` to `0`. (`u` already defaults to the empty list.)

```
ＮθＮη

```

Inputs the two numbers.

```
Ｗθ«

```

Repeats while `q` is nonzero.

```
   ⊞τ⪫  Ｉθ

```

Wrap `q` in padding and append it to the list `t`.

```
   ⊞υ⪫⎇﹪θ²  ¦[]Ｉη

```

Wrap `h` either in padding or `[]` depending on whether `q` is odd, and append it to the list `u`.

```
   ≔⁺σ∧﹪θ²ησ

```

Add `h` to `s` if `q` is odd.

```
   ≔÷θ²θ

```

Integer divide `q` by 2.

```
   ≔⁺ηηη»

```

Add `h` to itself.

```
⊞υ…=⁺²ＬＩσ

```

Append a suitable string of `=` signs to the list `u`.

```
⊞υ⪫  Ｉσ

```

Append the padded sum `s` to the list `u`.

```
←Ｅ⮌τ⮌ι

```

Rotate the list `t` by 180° and print it up-side down, thus right-justifying it.

```
Ｍ⌈ＥυＬιＬυ←Ｅ⮌υ⮌ι

```

Move the cursor so that when `u` is right-justified its top left corner lines up with the top-right corner we just reached, and print `u` right-justified.
> 8 votes

# Answer
# Python 2, ~~203~~ ~~202~~ ~~187~~ 133 bytes

```
a,b=input()
s=0
while a:print'%3s%9s'%(a,'[ %%dd] '[a%2::2]%b);s+=[0,b][a%2];a/=2;b*=2
print'%10s==\n%11s'%(''.rjust(len(`s`),'='),s)

```

Try it online!

If I can use `*` for string multiplication (`'='*R`) and as a 'selector' (`b*(a%2)` instead of `[0,b][a%2]`), I get:

## 118 bytes

```
a,b=input()
s=0
while a:print'%3s%9s'%(a,'[ %%dd] '[a%2::2]%b);s+=a%2*b;a/=2;b*=2
print'%10s==\n%11s'%('='*len(`s`),s)

```

Try it online!

---

## Explanation:

```
a,b=input()                   #Get input
L=len(`a`)                    #Get length of first number for adjusting text
l=[]                          #Output list
s=0                           #Sum
while a:
 B=['[%d]',' %d '][a%2]%b     #B is either '[b]' or ' b ' depending on if a is odd/even
 l+=[(`a`,B)]                 #Add a,B to output list
 s+=[0,b][a%2]                #Add b to sum if a is odd
 a/=2;                        #Halve a
 b*=2;                        #Double b
R=len(B)                      #Length of last B for adjusting output
l+=[('',''.rjust(R,'='))]     #Add double line ==== to output list
l+=[('','%d '%s)]             #Add sum to output list
for x,y in l:
 print x.rjust(L),y.rjust(R)  #Print adjusted numbers

```
> 8 votes

# Answer
# Java (OpenJDK 8), ~~353~~ ~~316~~ ~~267~~ ~~214~~ 210 bytes

```
(a,b)->{int g=0;for(;a>0;g+=a%2*b,a/=2,b*=2)System.out.printf("%1$8d%2$10s\n",a,a%2<1?"["+b+"]":b+" ");System.out.printf("%1$19s%2$18s","".valueOf(new char[(int)Math.log10(g)+3]).replace("\0","=")+"\n",g+" ");}

```

Try it online!
> 4 votes

# Answer
# Mathematica, 264 bytes

```
(s=#;k=(i=IntegerLength)@s;t=#2;w=0;P=Print;T=Table;While[s>0,If[OddQ@s,P[""<>T[" ",k-i@s],s,"  ",""<>T[" ",i[s(t)]-i@t],t];w=w+t,P[""<>T[" ",k-i@s],s,""<>T[" ",i[s(t)]-i@t]," [",t,"]"]];s=Quotient[s,2];t=2t];P[" "<>T[" ",k],""<>T["=",i@w+2]];P["  "<>T[" ",k],w])&

```

**input**

> \[19,427\]

**output**

```
19   427
 9   854
 4 [1708]
 2 [3416]
 1  6832
   ======
    8113

```
> 4 votes

# Answer
# \[Bash\], ~~144~~ ~~142~~ ~~140~~ ~~131~~ 128 bytes

Better respect of display, note there is a trailing space character

```
read a b;for((;a;));{ ((a%2))&&((r+=b))&&x=$b\ ||x=[$b];printf %3s%9s\\n $a "$x"
((a/=2,b+=b));};printf %12s\\n =${r//?/=}= $r\

```

First answer

```
read a b;while((a));do ((a%2))&&((r+=b))&&printf "%6s  %6s
" $a $b||printf "%6s [%6s]
" $a $b;((a/=2,b+=b));done;printf "%6s %7s
" \  ==== \  $r

```
> 3 votes

# Answer
# Perl 5, 157 bytes

155 bytes of code + 2 command line flags (`-nl`)

```
$\=<>;$w=y///c;$y=2+length$\<<((log)/log 2);while($_){$s+=$\if$_%2;printf"%${w}s %${y}s\n",$_,$_%2?$\.$":"[$\]";$_>>=1;$\<<=1}say$"x++$w,'='x$y;say$"x++$w,$s

```

Try it online!
> 3 votes

# Answer
## C, C++, ~~319~~ ~~313~~ ~~301~~ 299 bytes

-8 bytes thanks to Zacharý

Great thanks to `printf` magic i just learnt in 60 minutes between the edits

```
#include<string.h>
#include<stdio.h>
#define O printf("%*d %c%*d%c\n",5,a,a%2?32:91,9,b,a%2?32:93);
void m(int a,int b){int r=0,i=0;O while(a>1){r+=a%2*b;a/=2;b*=2;O}r+=b;char t[20],p[20];memset(t,0,20);memset(p,0,20);sprintf(t,"%d",r);memset(p,61,strlen(t)+2);printf("%*c%*s\n%*d",5,32,12,p,16,r);}

```

### C++ optimization, replace header `stdio.h` by `cstdio` and `string.h` by `cstring`, saves 2 byte

Compilation with MSVC requires to add `#pragma warning(disable:4996)` in order to use `sprintf`

Testing with my PPCG ID :

72 x 535 =\>

```
   72 [      535]
   36 [     1070]
   18 [     2140]
    9       4280
    4 [     8560]
    2 [    17120]
    1      34240
          =======
           38520

```

It respects the rules, digit are aligned, and the equal signs will always be 2 char larger than the final number. Example with 17 x 34 =\>

```
   17         34
    8 [       68]
    4 [      136]
    2 [      272]
    1        544
            =====
             578

```
> 3 votes

# Answer
# JavaScript 2017, 221 bytes

Mostly a problem of output formatting

```
(a,b)=>{for(t=b,r=0,l=[],w=`${a}`.length;a;l.push([a,t]),a>>=1,t+=t)z=`${r+=a&1&&t}`.length+2;P=(s,w)=>`${s}`.padStart(w);return[...l.map(([a,b])=>P(a,w)+P(a&1?b+' ':`[${b}]`,z+1)),P('='.repeat(z),z-~w),P(r,z+w)].join`
`}

```

*Less golfed*

```
(a, b) => {
  var w=`${a}`.length, r=0, l=[]
  while(a) {
    r += a&1 && b
    l.push([a,b])
    a >>= 1
    b += b
  }
  // algo complete, result in r, now display it and the steps in l[]
  var z=`${r}`.length+2
  var P= (s,w) => `${s}`.padStart(w)
  return [... l.map( ([a,b]) => P(a,w) + P(a&1?b+' ' : `[${b}]`, z+1) )
    , P('='.repeat(z), z+w+1)
    , P(r, z+w)
  ].join`\n`
}

```

**Test**

```
var F=
(a,b)=>{for(t=b,r=0,l=[],w=`${a}`.length;a;l.push([a,t]),a>>=1,t+=t)z=`${r+=a&1&&t}`.length+2;P=(s,w)=>`${s}`.padStart(w);return[...l.map(([a,b])=>P(a,w)+P(a&1?b+' ':`[${b}]`,z+1)),P('='.repeat(z),z-~w),P(r,z+w)].join`
`}

function update(){
  var i=I.value, [a,b]=i.match(/\d+/g)
  O.textContent=F(+a,+b)
}

update()
```

```
<input id=I value='21x348' oninput='update()'><pre id=O></pre>
```
> 3 votes

# Answer
# Haskell, 305 bytes

```
i=iterate
s=show
l=length.s
a!b=zip((takeWhile(>0).i(`div`2))a)(i(*2)b)
a?b=sum[y|(x,y)<-a!b,rem x 2>0]
a%b=l(snd.last$a!b)
a#b=unlines$[(' '<$[1..l a-l x])++s x++(' '<$[-1..a%b-l y])++if mod x 2<1then show[y]else(' ':s y)|(x,y)<-a!b]++map((++)(' '<$[-1..l a+a%b-l(a?b)]))['='<$[1..l a+1+a%b],' ':(s$a?b)]

```

Try it online!

The `!` operator creates the two lists, `?` computes the product. `%` and `#` are used for the ascii layout.
> 2 votes

# Answer
# C, ~~205~~ ~~201~~ ~~190~~ ~~183~~ ~~156~~ ~~150~~ 143 bytes

This will compile with warnings as C89, & I don't believe it's valid C99, but it ends up being smaller than HatsuPointerKun's version, as it saves bytes by ommitting `#include`'s, not using dynamic lengths to printf as they're unneeded, & using `log10()` to calculate the number of `=`'s needed:

```
r;m(a,b){r=0;while(a){printf(a%2?"%4d%10d\n":"%4d [%8d]\n",a,b);r+=a%2?b:0;a/=2;b<<=1;}printf("%15.*s\n%14d",(int)log10(r)+3,"==========",r);}

```

As my number is `64586`, I used this test program to calculate `64 * 586`:

```
#include <stdio.h>
int m(int a, int b);
int main(void)
{
    m(64, 586);
    putchar('\n');
}

```

& it outputs:

```
  64 [     586]
  32 [    1172]
  16 [    2344]
   8 [    4688]
   4 [    9376]
   2 [   18752]
   1     37504
        =======
         37504

```

### edit

saved 4 bytes by the "implicit int" rule

### edit 2

saved 11 bytes by changing to a `do...while()` loop & moving the printf into the loop from a macro. Also should work correctly if `a=1`.

### edit 3

saved 7 bytes & made the code work right.

### edit 4

Saved 26 bytes with some printf trickery.

### edit 5

saved 6 bytes by collapsing extra padding into 1 number.

### edit 6

saved 7 bytes by printf trickery with the ternary operator & not declaring an unused variable
> 1 votes

# Answer
# Excel VBA, <sub>~~183~~</sub> 172 bytes

An anonymous VBE immediate window function that takes input from range `[A1:B1]` and outputs to the console.

```
a=[A1]:b=[B1]:k="     ":While a:c=a Mod 2:?Right(k &a,2)Right(k &IIf(c,b &" ","["&b &"]"),7):s=s+IIf(c,b,0):a=a\2:b=b*2:Wend:?Right(k &String(Len(s)+2,61),9):?Right(k &s,9)

```

## Ungolfed

```
Sub EthiopianMultiply(ByVal a As Integer, b As Integer)
    Const k As String = "     "
    While a
        Let c = a Mod 2
        Debug.Print Right(k & a, 2);
        Debug.Print Right(k & IIf(c, b & " ", "[" & b & "]"), 7)
        Let s = s + IIf(c, b, 0)
        Let a = a \ 2
        Let b = Int(b * 2)
    Wend
    Debug.Print Right(k & String(Len(s) + 2, 61), 9)
    Debug.Print Right(k & s, 9)
End Sub

```

## Output

```
61   486
30  [972]
15  1944
 7  3888
 3  7776
 1 15552
  =======
   29646

```
> 1 votes

# Answer
# Excel, 201 Bytes

An anonymous worksheet function that takes no input and outputs as plain text to the calling cell. Output is best viewed with word wrapping, a wide column width, and a monospace font on the calling cell.

Functions for all inputs such that \\$(A\<10^5)\land(B\*2^{\lceil Log\_2 A\rceil}\<10^7)\\$.

### Golfed

```
=Let(s,"            ",z,2^Sequence(Log(A1,2)+1,,0),a,Int(A1/z),b,B1*z,c,Sum(IsOdd(a)*b),TextJoin("
",,Right(s&a,4)&Right(s&If(IsOdd(a),b&" ","["&b&"]"),8),Right(s&Rept("=",Len(c)+2),12),Right(s&c,11)))

```

### Commented

```
=Let(s,"          ",                   ' Define var block, hold 10 spaces in s
    z,2^Sequence(Log(A1,2)+1,,0),      ' z=array of powers of 2
    a,Int(A1/z),                       ' a=⌊Input 1/z⌋            - left array
    b,B1*z,                            ' b=B1*2^{0...⌈log2(A1)⌉}  - ~right array
    c,Sum(IsOdd(A)*B),                 ' c=∑(If a(i)Is Odd b(i)) - Sum
    TextJoin("\n",,                    ' concat w. `\n` delimiter from below:
      Right(s&a,4)&	               ' `a` value, padded to 4 chars concat with
          If(IsOdd(a),b&" "," ["&b&"]")'     `b` value, wrapped in `[]` if `a` val is even
	Right(s&   ...,8),             '   padded to 8 chars
      Right(s&Rept("=",Len(c)+2),12),  ' the `=` line
      Right(s&c,11)))		       ' the sum

```

# Output
> 0 votes

---
Tags: code-golf, math, ascii-art, algorithm
---


title: Fastest yes in the west

text:
# Question
Title: Fastest yes in the west
There has been a question about yes in the past, but this one is slightly different. You see, despite `yes` having a rather long size, it is incredibly fast. Running the following command:

```
timeout 1s yes > out

```

yields a file that is **1.9 GB**. Compared to this program:

```
int puts();main(){while(1){puts("y");}}

```

which yields a measly 150 Mb.

The goal is to write a program that outputs `y\n` (that's `y` with a newline) repeatedly forever, in as few lines as possible, outputting the biggest size file in as short time as possible.

The scoring works with the equation: `b * y/y'`. The value `b` is the size of your program in bytes. The value of `y` is the size in bytes of the `out` file after running the following command: `timeout 1s yes > out`. The value of `y'` is the size in bytes of the `out` file after running the following command: `timeout 1s PROG > out` where `PROG` is your program, eg. `./a.out`. Your program should match the output of the gnu coreutils program `yes` ran with no arguments exactly, albeit outputting `y` at any speed you like. Outputting zero bytes would be a divide by zero in the original equation, resulting in a score of inf for these purposes.

Lowest score wins.

Edit:

I will run all code on my computer, please show compilation commands and any setup required.

Specs (in case you want to optimize or something):

* OS: Arch Linux 5.5.2-arch1-1
* CPU: AMD Ryzen 2600X
* SSD: Samsung 970 EVO NVMe
* RAM: 16GB 3200MHz

Here is a script to calculate the score, since it seems people are having trouble:

```
b=$(wc -c < $1)
timeout 1s yes > out
y=$(wc -c < out)
timeout 1s $2 > out
y2=$(wc -c < out)
rm out
echo "scale=3;$b*$y/$y2" | bc

```

Example, given that the script is called `score.sh` and your program is `yes.py`:

```
./score.sh yes.py "python yes.py"

```

# Answer
> 46 votes
# C, 112 bytes, 28 TB/s, score ≈ 0.008

```
long b[9<<21];main(){for(b[2]=write(*b=1,wmemset(b+8,'\ny\ny',1<<25),1<<27)/2;b[3]=b[2]*=2;ioctl(1,'@ ”\r',b));}

```

(If you’re having trouble copying and pasting this, replace the multicharacter constant `'@ ”\r'` with `'@ \x94\r'` or `1075876877`.)

This writes 128 MiB of `y\n`s to stdout, and then repeatedly invokes the `FICLONERANGE` `ioctl` to double the file’s length by adding new references to the same disk blocks. Requires Linux x86-64 and a filesystem supporting `FICLONERANGE`, such as Btrfs or XFS; stdout must be opened in read-write mode (e.g. `./prog 1<> out` in bash).

### Self-contained testing script

This script loop-mounts a freshly created filesystem from a memory-backed image file and runs the program there. (I get about 43 TB/s in-memory, but the ratio with `yes(1)` is similar.) It works with either Btrfs or XFS, but Btrfs seems to give better scores.

```
#!/usr/bin/env bash
set -eux
dir="$(mktemp -dp /dev/shm)"
cd "$dir"
trap 'umount fs || true; rm -r "$dir"' EXIT
printf "long b[9<<21];main(){for(b[2]=write(*b=1,wmemset(b+8,'\\\\ny\\\\ny',1<<25),1<<27)/2;b[3]=b[2]*=2;ioctl(1,'@ \\x94\\\\r',b));}" > prog.c
b="$(stat -c %s prog.c)"
gcc -O3 prog.c -o prog
dd of=fs.img bs=1 count=0 seek=8G

# Pick one:
mkfs.btrfs fs.img
#mkfs.xfs -m reflink=1 fs.img

mkdir fs
mount fs.img fs
sync
timeout 1 yes 1<> fs/out || true
y="$(stat -c %s fs/out)"
rm fs/out
sync
timeout 1 ./prog 1<> fs/out || true
y1="$(stat -c %s fs/out)"
echo "score = $b * $y / $y1 = $(bc -l <<< "$b * $y / $y1")"

```

# Answer
> 34 votes
# Bash, 3 bytes, 1.9 GB/s

```
yes

```

Try it online!

Admittedly this is a troll solution, but the rules do not explicitly forbid it, and it should get you a value close to 3, which is not bad.

# Answer
> 13 votes
# x86-64 machine code (Linux system calls), 29B * 4.7GB/6.6GB = ~20.6 on tmpfs on Skylake

(Or even 28 bytes, but I haven't benchmarked Noah's suggestion of using the low 16 bits of the address as the count for `rep stosd`. Asm source for it on Godbolt.)

At about 6.6 GiB/s, this runs faster than GNU `yes` on tmpfs, the widely-used Linux ramdisk-like filesystem backed by the pagecache. I made sure to align my buffer to at least a cache-line boundary (and in fact a 4k page boundary) so the kernel's `copy_from_user` memcpy-like function using `rep movsb` would be most efficient.

**I don't expect this will outperform `yes` writing to an SSD on a fast Ryzen CPU which isn't the bottleneck; posted score is tentative.** However, writing 2 or 4 bytes at a time is unusably slow so we need a buffer to avoid a huge score penalty (like a factor of 2000 on tmpfs!). But probably this will score about 29 running at the same speed as GNU `yes` if they both fill the page-cache to max capacity with dirty pages and max out I/O bandwidth during the 1s window.

It's break-even for code size to use a buffer in the BSS instead of reserving stack space, in a Linux position-dependent executable where a static address can be put in a register with 5-byte `mov r32, imm32`. Using more space in the BSS doesn't increase the size of an executable that already has a BSS section/segment. But in this case it does make the executable larger so I'm not totally sure it's justified to not count anything for executable metadata for the BSS. **But as usual, I'm counting only the size of the `.text` section.** (And there's no initialized static data; all the constants are immediate.)

Without aligning the stack by 64 or 4k, `sub esp, edx`; `mov edi, esp` would be only 4 bytes, and safe in a Linux x32 executable: 32-bit pointers in 64-bit mode. (For efficient `syscall` instead of slow `int 0x80` or cumbersome `sysenter` in 32-bit mode). Otherwise break-even for `sub rsp, rdx`. So if not counting the BSS bothers you, save a byte and use the stack for buffers up to almost 8MiB (with default `ulimit -s`).

We fill a buffer that's 4x larger than we actually pass to write; `rep stosd` needs a repeat count of dword chunks and it's convenient to use the same number as a byte count for the system call.

Try it online! (NASM source which assembles to this answer's machine code.) It works on TIO; it doesn't depend on the output being a regular file or anything. Below is a NASM listing of machine code hexdump & source.

```
 6                                  global _start
 7                                  _start:
 8                                  ;; All regs zeroed at the top of a Linux static executable (except RSP)
 9
10                                  SIZEPOW equ 17
13 00000000 0FBAE911                   bts  ecx, SIZEPOW  ; 1<<SIZEPOW x 4 bytes to fill.
14 00000004 89CA                       mov  edx, ecx      ; size arg for sys_write in bytes; 1/4 of the actual buffer size
15
16 00000006 B8790A790A                 mov  eax, `y\ny\n`
25 0000000B BF[00000000]               mov  edi, buf        ; mov r32, imm32 static address; 00... is before linking
26 00000010 89FE                       mov  esi, edi        ; syscall arg
27
28                                     ;shr  ecx, 2         ; just fill 4x as much memory as needed
29 00000012 F3AB                       rep  stosd           ; wmemset(rdi, eax, rcx)  4*rcx bytes
30
31 00000014 8D7901                     lea   edi, [rcx + 1]  ;   mov  edi, 1
32                                  .loop:
33 00000017 89F8                       mov  eax, edi         ; __NR_write = stdout fileno
34 00000019 0F05                       syscall
36 0000001B EBFA                       jmp  .loop

47                                  section .bss
48                                   align 4096
49 00000000 <res 00080000>           buf: resd 1<<SIZEPOW

```

0x1b + 2 bytes for last instruction is 29 bytes total.

`mov cx, imm16` would also be 4 bytes, same as BTS, but is limited to 0..65535. vs. BTS r32, imm8 creating any power of 2. (Both depend on a zeroed RCX to start with, to produce a result zero-extended into RCX for `rep stos`)

`mov ax, `y\n``  would be 4 bytes, 1 fewer than `mov eax, imm32`, but then we'd need `rep stosw` which costs an extra operand-size prefix. This would have kept the ratio of filled buffer to used buffer at 2:1 instead of 4:1, so I should have done that to save a few pagefaults at startup, but not redoing the benchmarking now. (`rep stosw` is still fast on Skylake I think; not sure if Zen+ might suffer; but more than a factor of 2 in fill bandwidth + page fault cost is unlikely.)

A static buffer makes alignment to a cache line (or even the page size) not cost instructions; having the stack only 16-byte aligned was a slowdown. I recorded times in comments on my original code that aligned the stack pointer by 64kiB or not after reserving space for a buffer. Alignment to 64k instead of 16B made a ~3% difference in overall speed for writing a 1GiB file (to tmpfs, exiting on ENOSPC) with SIZEPOW=16, and led to a reduction in instructions retired as well. (Measured with `perf stat ./yes > testd/yesout`)

```
     ;;;; instead of  mov  edi, buf
    sub  rsp, rdx
    ;   and  rsp, -65536   ; With: 631.4M cycles 357.6M insns.   Without:  651.3M cycles 359.4M instructions.  (times are somewhat noisy but there's a real difference)
 ;;  mov  rdi, rsp   ; 3 bytes
    push  rsp
    pop   rdi        ; copy a 64-bit reg in 2 bytes
    push  rsp
    pop   rsi

```

For other benchmarking purposes (with a smaller 1GiB tmpfs), it was convenient to use **a loop that exited when `write()` failed** (with `-ENOSPC`) instead of looping until killed. I used this as the bottom of the loop

```
35                                  %if 0
36 0000001B EBFA                       jmp  .loop
37                                  %else
38                                     test eax,eax      ;;;;;;;;;;; For benchmarking purposes: abort on write fail
39                                     jge  .loop
40
41                                     mov eax, 231    ; not golfed
42                                     xor edi, edi
43                                     syscall         ; sys_exit_group(0)
44                                  %endif
45

```

---

# Testing

**I tested using tmpfs** because I don't want to wear out my SSD repeatedly testing this. And because keeping up with a consumer-grade SSD is trivial with any reasonable buffer size. **More interesting (to me) is to find the CPU/memory-bound sweet spot between system call overhead from making too many small `write` system calls vs. L2 cache misses** from re-reading too large a buffer every time. And also minimize time spent on filling a buffer before even starting to make system calls. (Although note that with write-behind I/O buffering for filesystems backed by real disk, there's no advantage to using a smaller buffer to get disk-write started sooner. I/O write-back to actual physical media wouldn't start until dirty pages hit the Linux kernel's high water mark. The default dirty *timeout* is 500 centisecs, and powertop suggests raising that to 1500 (15 seconds), so that's not going to come into play, just the high water mark. So what really matters is getting to the high water mark ASAP for a physical disk, and potentially pushing as many dirty pages into the pagecache as possible within the 1 second window, to finish writeback after `yes` dies. So this 1-second test probably depends on how much RAM your machine has (and even how much *free* RAM), if you're using a physical disk instead of tmpfs.)

`write` inside the kernel is basically a `memcpy` from the provided buffer into the pagecache; specifically Linux's `copy_from_user` function which uses `rep movsb` on systems with ERMSB (Intel since IvB) or `rep movsq` when it's fast (PPro and later, including non-Intel vendors.)

**According to `perf record` / `perf report`** output, with a 128k buffer size, **45% of the counts for hardware "cycles" were in `clear_page_erms`** (on `rep stosb`) and then **18.4% in `copy_user_enhanced_fast_string`** on `rep movsb`. (Makes some sense: clearing is touching a cold page, copy is copying over a just-cleared buffer, presumably hitting in L2 cache for src and destination. Or L1d for dst if it clears 4k at a time. Or only L3 cache if it's clearing whole hugepages :/) Next highest was `iov_iter_fault_in_readable` at 3.8%. **But anyway, only ~63% of total CPU time was spent on the "real work" of actually copying into the pagecache.** And that happens inefficiently, zeroing before copying.

I tried with **`tmpfs` with `huge=never`** (which is the default) and **only got 4.8GiB** for 1s with the 128kiB buffer version that gets 6.6GiB on hugepages. So clearly hugepages are worth it overall. perf record counts for `cycles` were: 14%: `clear_page_erms` and 10% `copy_user_enhanced_fast_string`, with many other kernel functions taking low single digits percentages, like `try_charge` at 4%, `__pagevec_lru_add_fn`, `get_mem_cgroup_from_mm`, `__this_cpu_preempt_check`, and `_raw_spin_lock_irq` at 3 to 2%. Managing memory in 4kiB chunks obviously costs a lot more than in 2MiB chunks.

### Test setup

* **i7-6700k @ 3.9GHz** with 0xd6 microcode update (Nov 2019). (quad core Skylake-client microarchitecture, per-core caches: L1d 32k, L2 256k. Shared L3 = 8MiB) vs. Ryzen having 512kiB L2 caches.
During this test: `/sys/devices/system/cpu/cpufreq/policy0/energy_performance_preference` = balance\_performance, not full `performance` EPP setting. So this is closer to the normal bootup machine state of balance\_power). I ran a warm-up run right before the main test to make sure the CPU speed was at full before the timed 1-second started: `timeout 1s ./yes > testd/yesout; perf stat -d timeout 1s yes > testd/yesout`.

With EPP at `performance` (max turbo = 4.2GHz, near-instant ramp-up), in practice it runs at 4.1GHz average for the test. I get up to 6.9GiB written instead of 6.6, for the 128k buffer version. (And up to 7.3GiB with the `writev` version.)
* **16 GiB of DDR4-2666** (2x8GB DIMMs, dual channel)
* OS = Arch GNU/Linux, kernel = Linux 5.4.13-arch1-1
* **Filesystem = tmpfs** using transparent hugepages:
`sudo mount -t tmpfs -o size=10G,huge=always tmpfs /tmp/test`. Much of the file is using transparent hugepages: from /proc/meminfo after writing a 6.4G file: `ShmemHugePages: 6723584 kB` (6566MB), and goes down to `83968 kB` (82MB) after deleting it. **It's using x86-64 2MiB hugepages instead of 4k normal pages to reduce TLB misses.**
* System idle except for Chromium using about 3% of one core at idle clock speed.
* free memory was sufficient for tmpfs not to actually page anything out to swapspace during the test:

```
$ free -m   # show numbers in megabytes.  Test output deleted; tmpfs nearly empty
              total        used        free      shared  buff/cache   available
Mem:    15820        2790       12164         236         864       12497
Swap:    2047         930        1117

$ cat /proc/sys/vm/swappiness
6

```
* Spectre / Meltdown mitigations (big overhead per system call, above the ~100 cycles each for `syscall` / `sysret` to get in/out of the kernel):

```
$ grep . /sys/devices/system/cpu/vulnerabilities/*
/sys/devices/system/cpu/vulnerabilities/itlb_multihit:KVM: Vulnerable
/sys/devices/system/cpu/vulnerabilities/l1tf:Mitigation: PTE Inversion
/sys/devices/system/cpu/vulnerabilities/mds:Mitigation: Clear CPU buffers; SMT vulnerable
/sys/devices/system/cpu/vulnerabilities/meltdown:Mitigation: PTI
/sys/devices/system/cpu/vulnerabilities/spec_store_bypass:Mitigation: Speculative Store Bypass disabled via prctl and seccomp
/sys/devices/system/cpu/vulnerabilities/spectre_v1:Mitigation: usercopy/swapgs barriers and __user pointer sanitization
/sys/devices/system/cpu/vulnerabilities/spectre_v2:Mitigation: Full generic retpoline, IBPB: conditional, IBRS_FW, STIBP: conditional, RSB filling
/sys/devices/system/cpu/vulnerabilities/tsx_async_abort:Mitigation: Clear CPU buffers; SMT vulnerable

```

### Results writing to tmpfs for 1 second: best case 6.6GiB

Timed with this as a shell one-liner

```
 asm-link -nd yes.asm &&    # assemble with NASM + link
 taskset -c 3 timeout 1s ./yes > testd/yesout;     # warm-up run
 time taskset -c 3  timeout 1s ./yes > testd/yesout;
 ls -lh testd/yesout && rm testd/yesout

```

Up-arrow recall that string of commands a few times, take the best case. (Assume that lower values didn't ramp up the CPU speed right away; spent some time allocating hugepages, or had other spurious interference.)

I intentionally limited myself to only looking at 2 significant figures of file size (letting ls round to `x.y GiB`) because I know there's going to be noise, so perhaps keeping the data simpler might be good.

### Results for various buffer sizes writing to tmpfs: 6.6GiB

(I did see 6.7G in some early testing with SIZEPOW=16 or 17, and I think even 6.8 or 9, but couldn't reproduce it once things settled down. Maybe some lucky early arrangement of hugepages that didn't last into a stable state?)

* SIZEPOW=1, buffer size: 2 (just `'y\n'`), best-case size: 2.9*MiB*
real 0m1.002s, user 0m0.431s, sys 0m0.570s
* SIZEPOW=2, buffer size: 4, best-case size: 5.8MiB
real 0m1.002s, user 0m0.381s, sys 0m0.620s
* ...
* SIZEPOW=11, buffer size: 1024, best-case size: 1.3GiB
real 0m1.005s, user 0m0.343s, sys 0m0.661s
* SIZEPOW=11, buffer size: 2048, best-case size: 2.3GiB
real 0m1.008s, user 0m0.270s, sys 0m0.737s. (Smaller than 1x 4k page = bad)
* SIZEPOW=12, buffer size: 4096, best-case size: 3.6GiB
real 0m1.012s, user 0m0.237s, sys 0m0.772s
* SIZEPOW=13, buffer size: 8192 (same as GNU `yes`), best-case size: 4.8GiB
real 0m1.016s, user 0m0.180s, sys 0m0.834s
* SIZEPOW=14, buffer size: 16384, best-case size: 5.6GiB
real 0m1.018s, user 0m0.090s, sys 0m0.926s
* SIZEPOW=15, buffer size: 32768, best-case size: 6.2GiB
real 0m1.019s, user 0m0.057s, sys 0m0.959s
* SIZEPOW=16, buffer size: 64kiB, best-case size: 6.5GiB
real 0m1.021s, user 0m0.023s, sys 0m0.993s
* SIZEPOW=17, buffer size: 128kiB (1/2 L2 cache size), best-case size: **6.6GiB**
real 0m1.021s, user 0m0.017s, sys 0m1.002s
* SIZEPOW=18, buffer size: 256kiB (= L2 cache size), best-case size: **6.6GiB**
real 0m1.020s, user 0m0.013s, sys 0m1.005s
* SIZEPOW=19, buffer size: 512kiB (2x L2 cache size), best-case size: 6.4GiB
real 0m1.021s, user 0m0.000s, sys 0m1.019s (User time getting meaningless / too small for Linux to measure accurately.)
* SIZEPOW=20, buffer size: 1024kiB, best-case size: 6.2GiB
* SIZEPOW=21, buffer size: 2MiB, best-case size: 5.7GiB
* SIZEPOW=22, buffer size: 4MiB (1/2 L3 size), best-case size: 5.0GiB
* SIZEPOW=23, buffer size: 8MiB (L3 cache size), best-case size: 4.9GiB
* SIZEPOW=24, buffer size: 16MiB (2x L3 cache size), best-case size: 4.9GiB
* SIZEPOW=25, buffer size: 32MiB, best-case size: 4.8GiB
* ...
* SIZEPOW=28, buffer size: 256MiB, best-case size: 4.4GiB

**GNU coreutils 8.31 `yes`**: buffer size 8192, best case size: 4.7GiB

(vs. 4.8GiB for my 8k buffer version. Perhaps because of lower startup overhead. My statically linked executable makes literally no system calls before `write`, just a BSS pagefault or two, vs. GNU `yes` being dynamically has more overhead before it gets going. And not quite as tight a loop around `syscall`, probably involving indirect-call/ret into libc's write wrapper, so at least two different pages of code in user-space are touched between system calls. Two chances for iTLB or i-cache misses. (Making a system call tends to invalidate a lot, especially with Spectre / Meltdown / MDS mitigations enabled, but even without that if a lot of kernel code runs)

GNU `yes`'s buffer is 64-byte aligned (cache line) but not 4k-page aligned. IDK if that makes any difference or leads to more dTLB misses (from spanning 3 pages instead of 2). Being an odd multiple of 64 bytes (address ending in `0x440`) is not ideal for the L2 spatial prefetcher (which tries to complete 128B-aligned pairs of lines) but that's probably insignificant; 8kiB is small enough that we get lots of L1d hits and very few L2 misses overall, including both user and kernel space. (`perf stat -d`)

The fall-off at the high end of size is I think due to cache and TLB misses. You can run `perf stat -d` instead of `time` to see LLC-misses. (And LLC-loads is an indication of L2 load misses. Indeed, small buffers get mostly L2 hits, larger buffers get some misses.)

Note that the `time` real/user/system times are for the `timeout` process itself, not for just the `yes` workload. And that Linux's time accounting is somewhat granular, I think. `perf stat` gives more details, but I didn't want even the tiny overhead of the occasional HW performance-counter event interrupt.

---

## Further speedup ideas:

Spawning **multiple threads** (all writing with `O_APPEND`) might be a minor win, depending on how much they serialize each other when appending. (I'm hoping they just reserve space and then copy, so a 2nd call can reserve more space while an earlier one is still copying. Otherwise we might need **`vmsplice` \+ `splice(2)` or something** to do the page-dirtying in user-space and **give pages to the kernel without further copying** (`SPLICE_F_GIFT` \+ `SPLICE_F_MOVE`)). But making a `clone` system call would probably take significantly more code.

Intel desktop CPUs can nearly saturate their memory bandwidth with a single core, unlike many-core Xeons with higher memory / uncore latency; ironically/paradoxically worse *single-core* memory bandwidth despite more memory controller channels for higher aggregate bandwidth than dual/quad-core client chips. With significant time spent in the kernel not bottlenecked on DRAM bandwidth, multiple threads could still help.

**Using `writev(2)` to pass the same buffer multiple times with one system call** could give the best of both worlds: small buffer for L1 / L2 hits while copying to the pagecache, but lots of work done per syscall. Maybe a few % speedup; (**Tried it; got a 7.0G output with 20 io vecs for an 8kiB buffer**, up from 6.6G. Kernel CPU time is now 49.5% `clear_page_erms`, 13.2% `copy_user_enhanced_fast_string`. So yes, less time spent *copying*, more time spent just clearing. 37 bytes, up from 29, score 26.3. Source on Try it online!).

As expected it doesn't come close to paying for itself in user-space code size to create the array of ptr,length pairs, although it was possible with a `loop` around 2 `push` instructions (4 bytes), but extra instructions outside the loop to get the args into place were necessary. Also, the call number `__NR_writev` is 20 so I used an array of 20 iovs, allowing the same trick as with `fd` = `__NR_write` to save a byte vs. `lea`.

There's still overhead per iovec (200x 2k buffer is slower than 20x 8k buffer). The sweet spot is around 4k or 8k buffers, with very minor gains for using a big vector (20x 8k seems enough). IOV\_MAX is "only" 1024, and isn't slower but is barely faster. (Try it online! - flexible iov size version for perf experiments also needs only a couple changes to flip back to plain write instead of writev.

# Answer
> 11 votes
# C (clang), ~~88~~ 63 bytes, 2.5GB/s

```
b[2048];main(){for(wmemset(b,'\ny\ny',2048);write(1,b,8192););}

```

Try it online! Edit: Saved 25 bytes thanks to @ceilingcat by assuming 4-byte wide characters.

# Answer
> 8 votes
## Bash, 16 bytes, 16TB output, score ~0 .0018554687

Thoroughly abuses the rules

```
trap '' TERM
yes

```

It ignores `timeout`'s SIGTERM (running an empty command) and so continues beyond the 1 second that the benchmark script intended to set. **This will fill your disk unless you kill it with a different signal or set a quota or other size limit.**

# Answer
> 3 votes
# Perl 5 (cperl), 26 bytes

```
while(1){print"y\n"x 9**4}

```

Try it online!

# , 18 bytes

```
repeat{cat('y\n')}

```

Try it online!

Improved thanks to @JDL

# Squirrel, 24 bytes

```
while(1){::print("y\n")}

```

Try it online!

# JavaScript (Node.js), 26 bytes

```
while(1){console.log('y')}

```

Try it online!

# Python 3, 28 bytes

```
while1:print(end='y\n'*9**4)

```

Try it online!

# Julia 1.0, 27 bytes

```
while(1==1) println('y')end

```

Try it online!

## WHILE Programming Language

Performant but not participating because of many bytes...

You can't try it online! Sorry:) But here are Docs,doc and a java-based IDE

# Answer
> 3 votes
# C (gcc), 67 bytes

```
b[1<<16];main(){for(wmemset(b,'\ny\ny',1<<16);~write(1,b,1<<18););}

```

Your times may vary. I'm running this inside a VM on a weak computer.

* `b[1<<16];` is an integer array of \\$2^{18}\\$ bytes.
* `wmemset(b,'\ny\ny',1<<16);` sets that array to a pattern of `y\ny\n`. The characters are reversed due to the endianness of the x86 platform.
* `~write(1,b,1<<18)` writes that array over and over until the write fails. (The `~` makes a `-1` error return -\> false; without it we iterate until the process is killed, saving 1 byte.)

May be faster on other systems if I increase the buffer size to 1 megabyte but there's no noticeable difference on mine. This really should be an average.

Try it online!

# Answer
> 3 votes
### x86 machine code - 21 15 bytes, score : 175119.036

Using write() syscall to print `y\n`

This is a NASM listing (`y.asm`) :

```
6  00000000 6668790A                    push word 0x0a79
7  00000004 43                          inc ebx
8  00000005 89E1                        mov ecx, esp
9  00000007 B202                        mov dl, 2
10                                  .loop:
11 00000009 B004                        mov al, 4
12 0000000B CD80                        int 0x80
13 0000000D EBFA                        jmp .loop

```

Using `score.sh` to get a score (`./score.sh y "./y"`), score are : 175119.036

# Answer
> 2 votes
# Python 3, 34 bytes, 1.9GB/s, score \\$\le\\$ 31.507

```
a='y\n'*2**17
while 1:print(end=a)

```

Try it online!

# Answer
> 2 votes
# Rust, ~~49~~ 48 bytes \\$\times\\,\frac{32186368}{744521728}\approx2.075\\$

Plain Rust, compiled with `-C target-cpu=native -C opt-level=3`. Clearly not the winner, only for reference; not bad, btw :)

```
fn main(){loop{print!("{}","y\n".repeat(8192))}}

```

-1 byte thanks to Anders Kaseorg

Try it online!

# Answer
> 2 votes
# brainfuck, 30\*971956224/621731~46899.2

```
>+[>+[<]>->+]++++++++++<[.>.<]

```

Try it online!

The BF JIT that I'm using prints each character in a separate syscall. An implementation that coalesces multiple `.` commands into one syscall would likely perform better.

Thanks to the list of BF constants.

# Answer
> 2 votes
# Jyxal `0ea7043bf37cd78106cde8f664e452f87286673b`, ~31.551 on my machine

```
{9999`y\n`*₴}

```

Timed using an aging laptop with an Intel Core i5 4th gen, 8 GB ram, using WSL. It uses Vyxal's codepage, so I modified `score.sh` to use the `-m` flag instead of `-c`. Jyxal is a flavor of Vyxal designed for maximum speed. Unfortunately, I could not apply my push-pop optimizations in this case that *really* make Jyxal fast. Also for some weird reason multiplying the string inside the loop seems to be faster than outside...

```
{9999`y\n`*₴} # Ze program
{           } # An infinite loop
     `y\n`    # The string "y\n"
 9999     *   # Repeated 9999 times...
           ₴  # Printed without a newline

```

## How to run

Jyxal isn't exactly released yet, you'd have to built it yourself. Clone the repo at commit `0ea7043bf37cd78106cde8f664e452f87286673b` and then run `./gradlew shadowJar`. You will find the compiled compiler in `/build/libs/`. Then create a file with the Jyxal program, and compile it with `java -jar Jyxal-1.0-SNAPSHOT-all.jar yourProgram.txt`. The run the compiled program using `java -jar yourProgram.jar`. All Java-related steps require Java 17 or higher.

# Answer
> 1 votes
# Python 3, 18 bytes \\$\times\frac{16834568}{622668}\approx486.65\\$

```
while 1:print('y')

```

Try it online!

# Answer
> 1 votes
# Japt, 6 bytes

No clue how the scoring in this challenge works.

```
@Opy}a

```

Try it online!

```
@          :Function
 Opy       :  Print "y"
    }      :End function
     a     :Call repeatedly until it returns a truthy value
           :(Japt's O.p() method returns undefined)

```

# Answer
> 1 votes
# x86-32 Linux, 26 bytes (ungolfed), 1.5M

`write` syscall test. Produces a very underwhelming result.

```
main:
    push    $0x0A79     # "y\n"
    mov     $1, %ebx    # write to stdout (fd=1)
    mov     %esp, %ecx  # use chars on stack
    mov     $2, %edx    # write 2 chars

loop:
    mov     $4, %eax    # sys_write call number
    int     $0x80
    jmp     loop

```

# Answer
> 1 votes
# 05AB1E (legacy) / 05AB1E, 4 bytes, score: *waiting for OP*

```
['y,

```

Or alternatively:

```
'y[=

```

Try it online.

Not sure which combination is the shortest, so for now this answer has four possible variations:

The 05AB1E (legacy) version is compiled and run in Python 3, and the 05AB1E version is compiled and run in Elixir. Based on performance on TIO for most challenges I did, I assume the legacy version will score much better.

I will leave just one of these four combinations with the largest output after OP's local test. The links provided contain instructions on how to install and run both 05AB1E and 05AB1E (legacy) locally.

**Explanation:**

```
[     # Loop indefinitely:
 'y  '#  Push string "y"
   ,  #  Pop and output it with trailing newline

'y   '# Push string "y"
  [   # Loop indefinitely:
   =  #  Output with trailing newline (without popping)

```

# Answer
> 1 votes
# Pyth, 10 bytes \\$\times\frac{1894125568}{1599025152}\approx11.846\\$

```
#p*^9 5"y

```

**Explanation:**

```
#           :  Loop till error
   ^9 5     :  Evaluates to 9 ^ 5 (59049)
  *    "y\n :  Concatenates "y\n" to itself 59049 times
 p          :  Print without trailing newline

```

Try it online!

# Answer
> 1 votes
# GFortran, 24 bytes, score: 49.179

`yes1.f90` Try it online

```
do;print*,'y';enddo
end

```

Might be faster to use `FPUT`??, for **52 bytes**:
`yes2.f90` Try it online

```
do;call fput('y');call fput(new_line(''));enddo
end

```

Run the code

```
//Compile
$ gfortran -std=gnu -Wextra -Wall -pedantic -ffree-form -fcheck=all -fbacktrace yes1.f90 -o yes1.a
$ gfortran -std=gnu -Wextra -Wall -pedantic -ffree-form -fcheck=all -fbacktrace yes2.f90 -o yes2.a

//Run the test
$ timeout 1s yes > out0
$ timeout 1s yes1.a > out1
$ timeout 1s yes2.a > out2

//File sizes
-rw-r--r--  1  staff  29306880  6 Mar 18:43 yes.out
-rw-r--r--  1  staff        24  6 Mar 18:57 yes1.f90
-rw-r--r--  1  staff  14302020  6 Mar 18:51 yes1.out
-rw-r--r--  1  staff        52  6 Mar 18:57 yes2.f90
-rw-r--r--  1  staff  18071552  6 Mar 18:39 yes2.out

//Scores
$ bc<<<"scale=3;24*29306880/14302020"
49.179
$ bc<<<"scale=3;52*29306880/18071552"
84.329

```

My system (inferior to the OP):

```
$ neofetch --off
OS: macOS 11.2 20D64 x86_64
Host: MacBookPro13,2
Kernel: 20.3.0
CPU: Intel i5-6267U (4) @ 2.90GHz
GPU: Intel Iris Graphics 550
Memory: 5500MiB / 8192MiB

```

# Answer
> 0 votes
# C (clang), <sup>~~57~~</sup> 54 bytes \\$\times\frac{44152832}{45940736}\approx51.8984\\$

Saved 3 bytes thanks to @S.S.Anne!!!

```
#define p putchar_unlocked
main(){for(;;p(10))p('y');}

```

Try it online!

This is on my ancient tablet, probability better on my laptop that's far away right now - on holiday! :))))

---
Tags: code-challenge, fastest-code
---


# Question
Title: Minimum difference between cartesian product of 3 elements that add up to a certain number
Let's say I've got a list (or array) of:

```
l = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

```

I want to get the third Cartesian power of the above list, where we take every possible triple of elements from `l`.

Then I want to filter and only keep the sublists where the sum of that sublist equal to the maximum value of the list.

Then I only want one sublist, which is the sublist where the difference of the three numbers that add up to the maximum value is the smallest.

The algorithm to see the smallest difference could be something like (in Python):

```
max(v1,v2,v3) - min(v1,v2,v3)

```

So the expected output for this case would be:

```
(3, 3, 4)

```

The order of the elements within the output could be in any order.

## Test cases:

```
l = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
-> (3, 3, 4)

l = [1, 2, 3, 4, 5]
-> (1, 2, 2)

l = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100]
-> (33, 33, 34)

l = [1, 4, 5, 2, 3, 9, 8, 7, 10, 6]
-> (3, 3, 4)

l = [1, 4, 8, 12, 13, 16, 20, 24, 27]
-> (1, 13, 13)

```

This is tagged with , so the shortest code in bytes wins!

There will always be an output, never would be a case where no 3 elements would add up to the maximum value.

# Answer
> 4 votes
# Factor \+ `math.combinatorics math.unicode`, 83 bytes

```
[ dup supremum swap 3 selections [ Σ = ] with filter [ minmax - abs ] infimum-by ]

```

Try it online!

## Explanation

```
                            ! { 1 2 3 4 5 }
dup                         ! { 1 2 3 4 5 } { 1 2 3 4 5 }
supremum                    ! { 1 2 3 4 5 } 5
swap                        ! 5 { 1 2 3 4 5 }
3 selections                ! 5 { { 1 1 1 } { 1 1 2 } ... }
[ Σ = ] with filter         ! { { 1 1 3 } { 1 2 2 } ... }
[ minmax - abs ] infimum-by ! { 1 2 2 }

```

# Answer
> 4 votes
# Wolfram Language (Mathematica), ~~39~~ 55 bytes

```
l#&@@SortBy[l~Tuples~3,Abs[Max@l-Tr@#]|Max@#-Min@#&]

```

Try it online!

Slow for larger input lists.

# Answer
> 4 votes
# , ~~105~~ 96 bytes

(or 89 bytes in ≥4.1 by using `\` for `function`)

*Edit: -9 bytes thanks to pajonk*

```
function(l,a=expand.grid(l,l,l),b=apply(a[rowSums(a)==max(l),],1,sort))b[,order(b[3,]-b[1,])[1]]

```

Try it online!

# Answer
> 3 votes
# Python 3.8, ~~130~~ ~~115~~ ~~99~~ ~~85~~ 80 bytes:

-14 Thanks to @tsh
-5 Thanks again to @tsh

```
lambda l:max([((z:=max(l)-x-y)in l,x<=y<=z,x-z,x,y,z)for x in l for y in l])[3:]

```

Try it Online!

Get's the Cartesian Product by looping the list 3 times, and summing it up.

# Answer
> 3 votes
# Vyxal, 18 bytes

```
3ÞẊ'∑?G=;µ÷Ȯε^ε+;h

```

Try it Online!

# Answer
> 3 votes
# Vyxal, 16 bytes

```
3ÞẊ'∑?G=;µ₌Gg-;h

```

Try it Online!

-2 thanks to Bubbler's insight.

```
3ÞẊ              # Combinations of input of length 3
   '    ;        # Filter by...
    ∑  =         # Sum equals
     ?G          # Maximum of input
         µ    ;h # Minimum by...
          ₌Gg-   # Difference of min + max

```

# Answer
> 3 votes
# Husk, ~~14~~ 13 bytes

-1 byte thanks to Dominic van Essen

```
◄§-▼▲fo=▲¹Σπ3

```

Try it online!

### Explanation

```
◄§-▼▲fo=▲¹Σπ3
           π3     cartesian product of 3 * input
     fo          filter by composed function
       =▲¹Σ      max of input equals sum
◄§               min by composed binary function
  -▼▲            max - min

```

# Answer
> 3 votes
# Jelly (fork), 11 bytes

```
ṗ3SƘṀṀ_ṂƊÞḢ

```

Try it online! (this is the equivalent in normal Jelly)

This uses my fork of Jelly which includes the `Ƙ` (keep-like) quick to replace the commonly used `<link>⁼¥Ƈ` pattern. You can see this in the TIO link.

## How it works

```
ṗ3SƘṀṀ_ṂƊÞḢ - Main link. Takes a list L on the left
ṗ3          - Cartesian Cube
    Ṁ       - Maximum of L
   Ƙ        - Keep triples whose     is like the maximum
  S         -                    sum
        ƊÞ  - Sort the remaining triples by:
     Ṁ      -   maximum
      _     -   minus
       Ṃ    -   minimum
          Ḣ - Take the first

```

# Answer
> 2 votes
# APL+WIN, 53 bytes

Prompts for list

```
↑((⌊/m)=m←(⌈/¨l)-⌊/¨l)/l←((⌈/i)=+/¨l)/l←,i∘.,,i∘.,i←⎕

```

Try it online! Thanks to Dyalog Classic

# Answer
> 2 votes
# Python/NumPy, 77 bytes

```
lambda l:min(l[argwhere(sum(ix_(l,l,l))==max(l))],key=ptp)
from numpy import*
```

Attempt This Online!

Takes and returns numpy arrays. Approach is straightforward. `ix_(l,l,l)` is essentially the cartesian product. This is then summed over coordinates and compared to the maximum. `argwhere` extracts the coordinates where the comparison succeeds and these are used to index back into `l`. It remains to select a triplet that minimises the spread (difference between `min` and `max`). Rather conveniently, numpy has a function for the spread: `ptp`

# Answer
> 2 votes
# Ruby, ~~73 72 68~~ 61 bytes

```
->l{l.product(l,l).min_by{|x|[(l.max-x.sum)**2,x.max-x.min]}}

```

Try it online!

# Answer
> 2 votes
# MATL, ~~28~~ 25 bytes

```
3Z^!tsGX>=Z)ttX<-X>&S1)Z)

```

Try it online!

```
3Z^     % Third Cartesian power

!ts     % Sum of each sublist

GX> =   % See which ones' sums equal input's maximum

Z)      % Filter to keep only those

ttX<-   % Subtract from each sublist its Minimum

X>      % Maximum of each. Effectively this is (Max - Min)

&S      % Get the indices that would sort this result

1)      % Get the first index of those i.e. the argmin

Z)      % Extract the sublist at that index

```

(Equivalently, perhaps slightly more clearly, `3Z^!tsGX>=Z)tX>yX<-&S1)Z)` \- instead of "effectively" doing `max - min`, just explicitly does `max - min`.)

# Answer
> 1 votes
# Charcoal, 38 bytes

```
ＦθＦθＦθ⊞υ⟦ικλ⟧≔Φυ⁼Σι⌈θυ≔Ｅυ⁻⌈ι⌊ιθＩ§υ⌕θ⌊θ

```

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

```
ＦθＦθＦθ⊞υ⟦ικλ⟧

```

Create the Cartesian product of three copies of the list.

```
≔Φυ⁼Σι⌈θυ

```

Extract those triples that sum to the maximum of the original list.

```
≔Ｅυ⁻⌈ι⌊ιθ

```

For each triple, find the difference between its largest and smallest entries.

```
Ｉ§υ⌕θ⌊θ

```

Output the first triple with the smallest difference.

# Answer
> 1 votes
# C++ (gcc), ~~280~~ \\$\cdots\\$ ~~211~~ 210 bytes

```
#import<regex>
#define S(v)std::sort(&v[0],&*end(v))
using V=std::vector<int>;int f(V&v){V r=v,x;S(v);int m=v.back(),n=m,t;for(int a:r)for(int b:r)for(int c:r)x={a,b,c},S(x),t=x[2]-x[0],v=t<m&a+b+c==n?m=t,x:v;}

```

Try it online!

*Saved ~~3~~ 4 bytes thanks to ceilingcat!!!*

Inputs a vector of integers.
Replaces the input vector with the cartesian product of 3 elements of the input vector that add up to the maximum of the input vector and that have the minimum difference between the smallest and the largest element from all of the cartesian products.

# Answer
> 1 votes
# Scala, 85 bytes

```
a=>(for{x<-a;y<-a;z<-a if x+y+z==a.max}yield Seq(x,y,z)).minBy(l=>l.max-l.min).sorted

```

Try it online!

# Answer
> 1 votes
# Perl 5 List::Util, 140 bytes

```
sub{$"=',';my$m;($d=max(@$_)-min@$_)<($m//9e9)and($m,@r)=($d,@$_)for grep max(@_)==sum(@$_),map[split$"],glob"{@_},{@_},{@_}";sort{$a-$b}@r}

```

Try it online!

# Answer
> 1 votes
# Haskell, 97 bytes

```
import Data.List
f x=head$sortOn(\t->m t-minimum t)$filter((==m x).sum)$sequence[x,x,x]
m=maximum

```

Try it online!

---
Tags: code-golf, number, array, permutations
---


title: Which Western Zodiac sign is today?

text:
# Question
Title: Which Western Zodiac sign is today?
* Task:
With the minimum amount of bytes, determine today's Zodiac sign using the programming language of your choice.
* Rules:
This is code golf, the answer with the fewest characters wins. The initialization of getting the current date into a variable (e.g. `var now = new Date();`) does not add to the count. Leap years must be handled correctly.
* Limitations:
You cannot use any other library functions for handling dates, nor predefined lists. In particular, participants would have to calculate the ordinal day of the year themselves if needed.
* Input:
The current date in the proleptic Gregorian calendar with numeric year, month (1–12) and day of the month (1–28…31).
* Output:
A single Unicode symbol indicating the current one of the twelve Zodiac signs from Western astrology, as used in horoscopes and listed below:

1. ♈ Aries: March 21 – April 19
2. ♉ Taurus: April 20 – May 20
3. ♊ Gemini: May 21 – June 21
4. ♋ Cancer: June 22 – July 22
5. ♌ Leo: July 23 – August 22
6. ♍ Virgo: August 23 – September 22
7. ♎ Libra: September 23 – October 22
8. ♏ Scorpio: October 23 – November 22
9. ♐ Sagittarius: November 23 – December 21
10. ♑ Capricorn: December 22 – January 19
11. ♒ Aquarius: January 20 – February 18
12. ♓ Pisces: February 19 – March 20

The actual dates might differ by one day depending on the year, but for this task the above date ranges are considered accurate for every year.

## Example

The sign for today, 28 February 2022, is Pisces, so the correct output would be `♓`.

## Related challenges

# Answer
> 2 votes
# Jelly, 27 bytes

```
“£f{ẋ’b5⁸ị+19>_@⁸_3%12+⁽#1Ọ

```

A dyadic Link accepting an integer, `month`, on the left and an integer, `day`, on the right that yields a character.

**Try it online!** Or see a whole year.

### How?

```
“£f{ẋ’b5⁸ị+19>_@⁸_3%12+⁽#1Ọ - Link: M; D
“£f{ẋ’                      - 53343748
      b5                    - to base five -> [1, 0, 2, 1, 2, 3, 4, 4, 4, 4, 4, 3]
        ⁸ị                  - get the item at 1-indexed index M
          +19               - add nineteen to it
             >              - is that greater than D? -> 1 or 0
              _@⁸           - subtract from M -> M-1 or M
                 _3         - subtract three (offset since characters start at March)
                   %12      - modulo twelve
                       ⁽#1  - 9800
                      +     - add
                          Ọ - cast to character

```

# Answer
> 5 votes
# JavaScript (Node.js),  ~~64~~  62 bytes

Expects `(month)(day)`.

This version builds the UTF-8 encoding of the code point (from `0xE2 0x99 0x88` for Aries to `0xE2 0x99 0x93` for Pisces).

```
m=>d=>Buffer([226,153,136+(m+=9^d<24+~"1342321"[m%12])%12])+''

```

Try it online!

### ES6, 63 bytes

Using the more straightforward `String.fromCharCode()` with a direct code point is one byte longer.

```
m=>d=>String.fromCharCode(9800+(m+=9^d<24+~"1342321"[m%12])%12)

```

Try it online!

# Answer
> 2 votes
# Retina 0.8.2, 112 bytes

```
T`d`k-m`1.-
T`d`l`.-
T`b-m`c-mb`.-3|[bce]-2|[df]-2[1-9]|[gm]-2[2-9]|[h-l]-2[3-9]|c-19
.(.).+
$1
T`e-mb-d`♈-♓

```

Try it online! Link includes test cases. Takes input in the format `mm-dd`. Does not output a Unicode variation selector, but the output looks fine in TIO to me. Explanation:

```
T`d`k-m`1.-

```

Change October to December to `k` to `m`, which will become Scorpio to Capricorn.

```
T`d`l`.-

```

Change January to September to `b` to `j`, which will become Aquarius to Libra.

```
T`b-m`c-mb`.-3|[bce]-2|[df]-2[1-9]|[gm]-2[2-9]|[h-l]-2[3-9]|c-19

```

Increment the encoded sign if the day is past the cutoff date for the next sign.

```
.(.).+
$1

```

Delete everything except the encoded sign.

```
T`e-mb-d`♈-♓

```

Decode to a Unicode Zodiac sign.

# Answer
> 1 votes
# Charcoal, 31 bytes

```
Ｎθ℅⁺⁹⁸⁰⁰﹪⁺⁸⁺θ›Ｎ⁺¹⁸Ｉ§”)⊞⌊4\`ζ”θ¹²

```

Try it online! Link is to verbose version of code. Takes separate month and day as inputs. Explanation:

```
Ｎθ                           First input as a number
              Ｎ              Second input as a number
             ›               Is greater than
                    ”...”    Compressed string `310212344444`
                   §         Cyclically indexed by
                         θ   Input month
                  Ｉ          Cast to integer
               ⁺             Plus
                ¹⁸           Literal integer `18`
           ⁺                 Plus
            θ                Input month
         ⁺                   Plus
          ⁸                  Literal integer `8`
        ﹪                    Modulo
                          ¹² Literal integer `12`
   ⁺                         Plus
    ⁹⁸⁰⁰                     Literal integer `9800`
  ℅                          Convert to Unicode
                             Implicitly print

```

---
Tags: code-golf, date
---