title: Find the Best Set of Adapters

text:
# Question
Title: Find the Best Set of Adapters
I'm trying to plug this really old phone into my computer but the phone seems to use a very obscure plug. Luckily I have some adapters. Unfortunately, I can't figure out which of them to use to connect my phone to my computer. Can you find the smallest number of adapters that can link my phone and computer?

## Input

A pair of strings representing the phone and the computer's port type and a list of pairs of strings where the pair `A, B` transforms an input of type `A` to type `B`. Example:

```
("A", "D")
[
  ("A", "B"),
  ("C", "D"),
  ("B", "C"),
]

```

The first pair `("A", "D")` is the desired connection. The rest are adapters.

## Challenge

Output the number of adapters required to connect the phone to the computer. In the above example, the answer would be 3 as all 3 adapters would be required.

## Test Cases

```
Phone, Computer
TypeA -> TypeB
TypeC -> TypeD
Output

```

```
A, D
A -> B
B -> C
C -> D
3

```

```
A, Z
A -> B
B -> C
C -> D
D -> Z
X -> Y
Y -> Z
4

```

```
A, B
A -> B
X -> Y
Y -> Z
1

```

```
A, C
A -> B
B -> C
C -> A
2

```

```
A, C
A -> A
B -> B
C -> C
A -> B
B -> C
2

```

## Rules

* Standard loopholes disallowed
* This is , shortest code wins
* You can assume it is possible to make the connection
* The port on the phone and computer will not be of the same type
* There may be adapters of type `A -> A`
* It is not guaranteed that all of the adapters will be possible to use
* You may take input in any form that is convenient

# Answer
# Jelly, 13 bytes

```
ṗJ$Ẏy@ƒ⁼⁵ɗƇẈṂ

```

Try it online!

Full program taking a list of pairs `L` (e.g. `['AB', 'BC', 'CD', 'DZ', 'XY', 'YZ']`) as the first argument, the source as the second and the target as the third.

## How it works

Brute-force approach.

```
ṗJ$Ẏy@ƒ⁼⁵ɗƇẈṂ - Main link. Takes L on the left and S on the right
  $           - Group the previous 2 links into a monad f(L):
 J            -   Yield the indices of L; [1, 2, 3, ..., len(L)]
ṗ             -   Get the n'th Cartesian power of L for each n in this range
   Ẏ          - Flatten into a list of lists
         ɗƇ   - Keep those for which the following is true:
      ƒ       -   Reduce the list by the following, starting with S:
    y@        -     Translate, according to the pair mapping
       ⁼⁵     - Does the final result equal T?
           ẈṂ - Get the length of the shortest element

```
> 5 votes

# Answer
# , 28 bytes

```
1 :'[:#+./ .*^:(1-u{])^:a:~'

```

Try it online!

Perhaps stretching the definition of convenient input, I take the adapter list as an adjacency matrix, and the target connection as a boxed pair of indexes (the noun being modified).

The test cases include an (ungolfed) conversion step, so if this is not allowed it can be easily corrected, though the byte count will about double.

## main idea

Simply multiply the adjacency matrix by itself until the cell representing the target adapter becomes 1, keeping track of the intermediate matrices.

The length of that list is the minimal number of adapters.

## , 30 byte using a verb rather than adverb

```
[:#(,{.+/ .*{:)@]^:(-.@{{:)^:_

```

Try it online!
> 2 votes

# Answer
# Wolfram Language (Mathematica), 13 bytes

```
GraphDistance

```

Try it online!

...and here's the built-in.
> 2 votes

# Answer
# JavaScript (ES6), 78 bytes

Expects `(target, list)(source)`, where `list` is an array of string pairs.

```
(b,c,m)=>g=(a,n)=>a==b?m<n?m:m=n:c.map(p=>p[0]==a?p[g(p[1],p[0]=-~n),0]=a:0)|m

```

Try it online!

### Commented

```
(                      // outer function:
  b,                   //   b   = target plug
  c,                   //   c[] = list of connectors
  m                    //   m   = minimum number of connections
) =>                   //
g = (                  // inner recursive function:
  a,                   //   a = current plug
  n                    //   n = number of connections
) =>                   //
  a == b ?             // if a = b:
    m < n ? m          //   update m to min(m, n)
          : m = n      //   (the update is forced if m is still undefined)
  :                    // else:
    c.map(p =>         //   for each pair p[] in c[]:
      p[0] == a ?      //     if the input plug of p is a:
        p[             //
          g(           //       recursive call:
            p[1],      //         set a to the output plug p[1]
            p[0] = -~n //         increment the number of connections and
                       //         invalidate p[0] so that it's not used again
          ),           //       end of recursive call
          0            //
        ] = a          //       restore p[0] to a afterwards
      :                //     else:
        0              //       do nothing
    ) | m              //   end of map(); yield m

```
> 1 votes

# Answer
# Charcoal, 40 bytes

```
⊞υθＦυＦζＦ›⁼§ι±¹§κ⁰№ι§κ¹⊞υ⁺ι§κ¹Ｉ⊖⌊ＥΦυ№ιηＬι

```

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

```
⊞υθ

```

Start a breadth-first search using the computer's port.

```
Ｆυ

```

Loop over all chains of adapters tried so far.

```
Ｆζ

```

Loop over all of the adapters.

```
Ｆ›⁼§ι±¹§κ⁰№ι§κ¹

```

Can this adapter be plugged in to provide a port not yet seen in this chain?

```
⊞υ⁺ι§κ¹

```

If so then save this new chain to the search list.

```
Ｉ⊖⌊ＥΦυ№ιηＬι

```

Print the shortest number of adapters that result in the desired output port.
> 1 votes

# Answer
# Java, 474 bytes

```
(s,e,a)->{java.util.Map<String,java.util.List<String>>m=new java.util.HashMap();java.util.Map<String,Integer>d=new java.util.HashMap();for(String[]c:a)m.computeIfAbsent(c[0],k->new java.util.ArrayList()).add(c[1]);java.util.List<String>l=new java.util.LinkedList();l.add(s);d.put(s,0);while(l.size()!=0){String c=l.remove(0);for(String n:m.getOrDefault(c,new java.util.ArrayList<>()))if(d.get(c)+1<d.getOrDefault(n,(int)1e9)){d.put(n,d.get(c)+1);l.add(n);}}return d.get(e);}

```

This runs a single breadth-first search (BFS) while keeping track of the distances to each node.

Try it online!
> 1 votes

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

```
(b,c,m)=>g=(a,n=0)=>a==b?m<n?m:m=n:c[n]&&c.map(p=>p[0]==a&&g(p[1],n+1))|m

```

Try it online!

Mainly based on Arnauld's answer.

`c[n]` means `n < c.length`. Since the question claim that "You can assume it is possible to make the connection", it is safe to give up search if we already used `c.length` adapters but not reach destination yet.
> 0 votes

---
Tags: code-golf, string, graph-theory
---


title: Reverse and error!

text:
# Question
Title: Reverse and error!
You have to write a program, if its source code is reversed, then it will error.

For example, if your source is `ABC`, then reversing it and writing `CBA` should crash/throw an error. And `ABC` itself should be a vaild program (I mean your primary source should be a valid program). Output of the main source code can be empty, but your `ABC` code I mean primary source should not output anything to standard error.

Also the minimum length of a solution is 2 bytes.

Standard loopholes apply, shortest code wins.

# Answer
# Malbolge, 2 bytes

Errors via raising a SIGILL (illegal instruction).

```
DP

```

Try it online!

Try it reversed!

## Explanation

Forward:

| C | \[C\] | (C+\[C\])%94 | Action |
| --- | --- | --- | --- |
| 0 | `D` (ord 68) | 68 | No operation. |
| 1 | `P` (ord 80) | 81 | Stop execution of current program. |

Reversed:

| C | \[C\] | (C+\[C\])%94 | Action |
| --- | --- | --- | --- |
| 0 | `P` (ord 80) | 80 | Illegal instruction (stops program) |
| 1 | `D` (ord 68) | 69 | Illegal instruction (not executed) |
> 5 votes

# Answer
# Python 2, 2 bytes

And probably 1 million different languages too

```
+1

```

Try it online!
> 4 votes

# Answer
# , 2 bytes

```
NA

```

Try it online!

Outputs `NA`, which corresponds to "Not Available", to represent missing values.

On the other hand, `AN` errors, as it is literally not available.

A bunch of other examples:

```
1i
1L
ar
as
by
de
df
dt
gc
gl
Im
is
lh
lm
ls
pf
pi
pt
qf
qr
qt
Re
rf
rt
sd
ts
vi
{}
.C

```
> 4 votes

# Answer
# Jelly, 2 bytes

```
D€

```

Try it online! or !enilno ti yrT

## How it works

```
D€ - Main link. Takes no arguments
   - Implicitly set the argument to 0 as the chain doesn't begin with a nilad
 € - Generate the range from 1 to 0 ([]) and over each element:
D  -   Get its digits
     Output the empty list, which outputs nothing due to Jelly's output rules

```

## skrow ti woH

```
€D - Main link. Takes no arguments
€  - € is a quick, which needs a preceding atom upon which to act
     Without a preceding atom, parsing fails and the program errors
 D - D is ignored as the program has errored

```

---

### Alternative programs

There are far too many 2-byte programs that also work to fully list them. Instead, here's how to make your own:

1. Open Jelly on Try it online!
2. Open the Quicks page
3. Open the Atoms page
4. Choose any single character atom. Enter it into the TIO Code field (Copy-Paste works best)
5. Choose any single character quick. Enter it after the atom
6. Press Run.
7. If this errors, clear the characters and go to step 4
8. Voila, you have your answer
> 4 votes

# Answer
# Python 2 or 3, 3 bytes

```
0/1

```

Try it online!

Try it online (Reversed)!

`0/1` is a valid mathematical expression and will result 0 (will show nothing on TIO interpreter) `1/0` (reversed) causes a divide by zero error.

Polygots in a "loooottttttttttt" of languages
> 3 votes

# Answer
# Python 3, 2 bytes

G B already posted one of those, but I wanted to show some more 2-byters:

```
+0
0,
~0
#\
id
0j
0;
{}
0

```

Try it all online!

Here is a more complete list.
> 3 votes

# Answer
# JavaScript, 2 bytes

```
[]

```

Errors with `][`
> 2 votes

# Answer
# Bash, 2 bytes

```
wc

```

Try it online!

Try it online (Reversed)!

Don't think this one has a lot of "polygot"s

other 2-byters `sh`,`ps`,`du`,`ls` (if `sl` is not installed)
> 1 votes

# Answer
# Windows Batch, 2 bytes

```
:a

```

This program is an empty label, if reversed then it would search for a drive named `a:`, but floppy drives are no longer available!!!
> 1 votes

# Answer
# Vyxal, 2 bytes

```
i1

```

Try it Online! or Try it Reversed!

## Explained

Before we begin, `i` takes two arguments (we'll call them `a` and `b`) and returns `a[b]` (indexing). `1` simply pushes `1` to the stack.

The program `i1` is:

```
rhs, lhs = pop(stack, 2)
stack.append(lhs[rhs])
stack.append(1)

```

Because the stack is empty, implicit input is taken for `lhs` and `rhs`. And because there is no input, `0` is returned each time input is needed. Thus, `i` gives `"0"[0]` and then pushes `1`.

The program `1i` is:

```
stack.append(1)
rhs, lhs = pop(stack, 2)
stack.append(lhs[rhs])

```

Which attempts to push `"0"[1]`, which is obviously out of the list. Vyxal doesn't have modular indexing (yet), so this errors.
> 1 votes

# Answer
# naz, 2 bytes

```
1o

```

Any valid 2-byter will throw the error `missing number literal` if reversed; I just picked this one because it actually outputs something (`0`).

Try it online! / Try it reversed!
> 1 votes

# Answer
# MATLAB/Octave, 2 bytes

```
pi

```

When run forward, this yields an approximation of `pi` represented as a floating point number. When reversed, it tries to execute the function named `ip` which is not defined:

```
octave:1> ip
error: 'ip' undefined near line 1, column 1

```
> 1 votes

# Answer
# Java, 42 bytes

```
interface M{static void main(String[]a){}}

```

This is the shortest valid full Java program. It does not output anything. Since all methods in an interface are implicitly public, we can save bytes by putting the main method inside an interface instead of a class.

Try it online!

The reversed code is clearly invalid syntax:

```
}}{)a][gnirtS(niam diov citats{M ecafretni

```

Try it online!
> 1 votes

# Answer
# Lua (2 bytes)

Write the following in the command line

```
=1

```

Although the `=<something>` is supported for backward compatibility, is a deprecated feature in Lua. `1=` triggers the following error:

```
stdin:1: unexpected symbol near '1'

```

in Lua 5.4.2.
> 0 votes

# Answer
## x86-16 machine code, 2 bytes

Full program. Error type is an unhandled SIGSEGV.

Hexdump:

```
00000000: 63c3                                     c.

```

Listing:

```
63         DB 63      ; Raises an unhandled SIGSEGV
C3         RET        ; Not executed

```

Listing (reversed):

```
C3         RET        ; Return to caller
63         DB 63      ; Not executed

```
> 0 votes

# Answer
# \[BASIC\], 2 bytes

```
?a

```

Try it online!

```
a?

```

The reverse will just generate a Syntax Error

Basically (pun totally intended) if you can't make a 2-3 byte program in almost any language that'll crash if reversed, something is wrong!
> 0 votes

# Answer
# MATL, 2 bytes

```
lt

```

Try it at MATL Online

**Explanation**

This program pushes the literal `1` to the stack and duplicates it using `t`. When reversed, `t` tries to grab it's input argument implicitly and since no inputs are provided it errors out

```
MATL run-time error: The following Octave error refers to statement number 1: t
---
Unable to fetch user input

```
> 0 votes

# Answer
# Brain-flak, 2

`()`

Errors on `)(`

#

# PHP, 2

`$=?>` does nothing

`<?=$` errors.
> 0 votes

---
Tags: code-golf, source-layout, error-message
---


title: Triangle Area Side Side Side

text:
# Question
Title: Triangle Area Side Side Side
Given three sides of a triangle, print area of this triangle.

Test cases:

**In:** `2,3,4`

**Out:** `2.90473750965556`

**In:** `3,4,5`

**Out:** `6`

Given the sides \\$a\\$, \\$b\\$, and \\$c\\$, you can assume that \\$a\>0\\$, \\$b\>0\\$, \\$c\>0\\$, \\$a+b\>c\\$, \\$b+c\>a\\$, and \\$c+a\>b\\$.

This is , shortest answer per language in bytes wins.

# Answer
## J, ~~23~~ 19 chars

```
   (4%~2%:[:*/+/-0,+:)

   (4%~2%:[:*/+/-0,+:) 2 3 4
2.90474

   (4%~2%:[:*/+/-0,+:) 3,4,5
6

```

17-char version if input is in `i`: `4%~%:*/(+/,+/-+:)i`

original 23-char version: `(%:@(+/**/@(+/-+:))%4:)`
> 8 votes

# Answer
## APL ~~21~~ 20

Takes screen input via ←⎕

```
(×/(+/t÷2)-0,t←⎕)*.5

```
> 7 votes

# Answer
**Mathematica 23**

```
√Times@@(+##/2-{0,##})&

```
> 7 votes

# Answer
# Python 2, 53

```
t=input()
s=a=sum(t)/2.
for x in t:a*=s-x
print a**.5

```

Input: `2,3,4`

Output: `2.90473750966`
> 6 votes

# Answer
## Python 57 bytes

```
a,b,c=input()
s=(a+b+c)*.5
print(s*(s-a)*(s-b)*(s-c))**.5

```

Using Heron's Formula.

Sample usage:

```
$ echo 2,3,4 | python triangle-area.py
2.90473750966

$ echo 3,4,5 | python triangle-area.py
6.0

```

---

**A 58 byte variant:**

```
a,b,c=input()
print((a+b+c)*(b+c-a)*(a+c-b)*(a+b-c))**.5/4

```
> 5 votes

# Answer
## R : ~~48~~ 43 characters

```
f=function(...)prod(sum(...)/2-c(0,...))^.5

```

Using Heron's formula as well but taking advantage of R's vectorization.
Thanks to @flodel for the idea of the ellipsis.

Usage:

```
f(2,3,4)
[1] 2.904738
f(3,4,5)
[1] 6

```
> 4 votes

# Answer
### GolfScript, 38 characters

```
~].~++:d\{2*d\-*}/'"#{'\+'**0.5/4}"'+~

```

Since the question didn't specify otherwise I chose to work only on integer lengths. Sides must be given on STDIN separated by spaces.

Example:

```
> 2 3 4
2.9047375096555625

```
> 4 votes

# Answer
# Mathematica ~~20~~ 16 or ~~22~~ 18 bytes

With 4 bytes saved by @swish.

This returns an exact answer:

```
Area@SSSTriangle@

```

**Example**

```
Area@SSSTriangle[2,3,4]

```

---

To return the answer in decimal form, two additional bytes are required.

```
N@Area@SSSTriangle[2,3,4]

```

2.90474
> 4 votes

# Answer
### APL, 23 20 characters

```
{(×/(+/⍵÷2)-0,⍵)*÷2} 2 3 4

```

Example:

```
> {(×/(+/⍵÷2)-0,⍵)*÷2} 2 3 4
2.90474

```
> 3 votes

# Answer
# K, 23

```
{sqrt s**/(s:.5*+/x)-x}

```

Example

```
k){sqrt s**/(s:.5*+/x)-x} 2 3 4
2.904738

```
> 3 votes

# Answer
## Javascript, ~~88~~ 85

```
v=prompt().split(/,/g);s=v[0]/2+v[1]/2+v[2]/2;Math.sqrt(s*(s-v[0])*(s-v[1])*(s-v[2]))

```

Not good but fun :) Also Heron... Demonstrates the ungolfability of simple problems in JS lol

**Note**: run from console to see result.

88-\>85: Removed `a`, `b` and `c`.
> 2 votes

# Answer
# C (gcc), 55 bytes

```
#define f(a,b,c)sqrt((a+b+c)*(a+b-c)*(a-b+c)*(b+c-a))/4

```

Try it online!

Yet another implementation of Hero's formula.
> 2 votes

# Answer
# Jelly, 7 bytes

```
SH;_P½ʋ

```

Try it online!
> 2 votes

# Answer
# PHP, ~~78~~ 77

```
<?=sqrt(($s=array_sum($c=fgetcsv(STDIN))/2)*($s-$c[0])*($s-$c[1])*$s-=$c[2]);

```

Useage:

```
php triangle.php
2,3,4

```

Output: `2.9047375096556`

I don't think I can make it shorter? I'm still new to golfing. Anyone let me know if I overlooked something.

Thanks Primo for saving me 1 byte, lol.
> 1 votes

# Answer
# Haskell: 51 (27) characters

```
readLn>>=(\l->print$sqrt$product$map(sum l/2-)$0:l)

```

A very straight-forward implementation of Heron's formula. Example run:

```
Prelude> readLn>>=(\l->print$sqrt$product$map(sum l/2-)$0:l)
[2,3,4]
2.9047375096555625
Prelude>

```

Note that it accepts any numeric input, not only integers. And if the input already is in l the solution only needs to be 36 characters long, and if we are not interested in printing the answer the solution only needs to be 30 characters long. What more is that if we can allow ourself to change the input format we can remove 3 more characters. So if our input looks like \[2,3,4,0.0\] and is already in l we can get our answer with only:

```
sqrt$product$map(sum l/2-)l

```

Example run:

```
Prelude> let l = [2,3,4,0.0]
Prelude> sqrt$product$map(sum l/2-)l
2.9047375096555625
Prelude>

```
> 1 votes

# Answer
## JavaScript (84 86)

```
s=(eval('abc '.split('').join('=prompt()|0;'))+a+b)/2;Math.sqrt(s*(s-a)*(s-b)*(s-c))

```

Another JavaScript solution based on Heron's formula, but trying a different approach for loading variables. Needs to be run from the console. Each side is entered in a separate prompt.

**EDIT**: Make use of return value of `eval` to save 2 characters. Beats @tomsmeding, wahoo! :)
> 1 votes

# Answer
# Tcl, 74 chars.

```
proc R {a b c} {set s ($a+$b+$c)/2.
expr sqrt($s*($s-$a)*($s-$b)*($s-$c))}

```

Pass the sides as argument.

For the input `2 3 4` the value of `s` is `(2+3+4)/2.` as string. Double evaluation FTW.
> 1 votes

# Answer
# TI-BASIC, ~~14~~ 12 bytes

```
4⁻¹√(sum(Ansprod(sum(Ans)-2Ans

```

Starting from a Heron's Formula routine written by Kenneth Hammond (Weregoose), I golfed off two bytes. Note that TI-BASIC is tokenized, and each token, like `Ans` and `prod(`, is one or two bytes in the calculator's memory.

Input through `Ans` i.e. in the form `{a,b,c}:[program name]`.

Explained:

```
                   sum(Ans)-2*Ans   (a+b+c)-2{a,b,c}={b+c-a,c+a-b,a+b-c}
          Ans*prod(                 {a,b,c}*(b+c-a)(c+a-b)(a+b-c)
      sum(                          (a+b+c)(b+c-a)(c+a-b)(a+b-c)
4⁻¹*√(                              √((a+b+c)(b+c-a)(c+a-b)(a+b-c)/16)
                                    =√(s(s-a)(s-b)(s-c))

```
> 1 votes

# Answer
# Japt, ~~17~~ ~~16~~ 15 bytes

```
½*Nx
NmnU ×*U q

```

Test it

Saved 2 bytes thanks to ETH pointing out a redundant newline and some alternative ways to reduce the array.
> 1 votes

# Answer
# Excel, 42 bytes

Based on Heron's formula, high school algebra to golf.

```
=SQRT(((A1+B1)^2-C1^2)*(C1^2-(A1-B1)^2))/4

```

Ungolfed / Unalgebra'ed

```
=SQRT((A1+B1+C1)/2*(((A1+B1+C1)/2)-A1)*(((A1+B1+C1)/2)-B1)*(((A1+B1+C1)/2)-C1))

```
> 1 votes

# Answer
## Julia 0.6.0, 48 bytes

Basically heron's formula:

```
f(a,b,c)=(p=(a+b+c)/2;sqrt(p*(p-a)*(p-b)*(p-c)))

```
> 1 votes

# Answer
# dc, 34 bytes

```
9ksssddlsld++2/d3R-rdls-rdld-***vp

```

Try it online!
> 1 votes

# Answer
# ARBLE, 36 bytes

```
sqrt(a*(a-b)*(a-c)*(a-d))((b+c+d)/2)

```

Heron's formula.

Try it online!
> 0 votes

# Answer
# Perl 5 `-MList::Util=sum -ap`, 40 bytes

```
$r=$t=.5*sum@F;map$r*=$t-$_,@F;$_=sqrt$r

```

Try it online!
> 0 votes

# Answer
# Stax, 10 bytes

```
╝0∞♀»♦▓y╩╪

```

Run and debug it

Operates triples of floating point numbers. Uses Heron's Formula
> 0 votes

# Answer
# APL(NARS), 16 chars, 32 bytes

```
{√×/(+/⍵÷2)-0,⍵}

```

One has to cenvert the Erone formula if a, b, c are sides of triangle

```
p   =(a+b+c)/2
Area=√p*(p-a)(p-b)(p-c)

```

to APL language... test

```
  f←{√×/(+/⍵÷2)-0,⍵}
  f 2 3 4
2.90473751
  f 3 4 5
6

```
> 0 votes

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


title: Parse a list of signed unary numbers

text:
# Question
Title: Parse a list of signed unary numbers
Unary numbers typically only represent nonnegative integers, but we can extend them to represent all integers as follows:

* A positive integer N is represented as N `1`'s: `5 -> 11111`
* A negative integer -N is represented as a `0` followed by N `1`'s: `-5 -> 011111`
* Zero is represented as `0`

We can then represent a list of these numbers unambiguously if we use `0` as the separator:

```
3,-2,0,1
111,011,0,1
111 0 011 0 0 0 1
11100110001

```

Your task: take a string representing such a list of signed unary numbers, and translate it into a list of decimal numbers.

## Details

You may assume that the input is a complete list of signed unary numbers. In particular, your program will not have to handle 1) empty input or 2) input that ends with a separator.

You may assume that the magnitude of each number will not exceed 127. For languages with maximum sizes of strings or lists, you may assume that the input and output will fit in your language's data structures, but your algorithm should theoretically work for a list of any size.

Your program or function may perform I/O in any of the standard ways. Input may be a string or a list of characters, single-character strings, integers, or booleans. You may use any two characters to represent `1` and `0`; if you don't use `1` and `0`, please specify which characters you're using.

Output must be decimal numbers in any reasonable list format (in particular, there must be some kind of a separator between numbers). Negative numbers should be indicated with a minus sign, although if your language has a different format for negative integers I will also accept that. Zero may be represented in the output as `0` or `-0`.

## Test cases

```
1 -> 1
0 -> 0 (or -0, and similarly for the other test cases)
011 -> -2
1101 -> 2,1
1100 -> 2,0
11001 -> 2,-1
110001 -> 2,0,1
11100110001 -> 3,-2,0,1
00000001 -> 0,0,0,-1
01111011111111001111111111111110111111111111111100111111111111111111111110111111111111111111111111111111111111111111 -> -4,8,-15,16,-23,42
01111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111 -> -127

```

# Answer
> 10 votes
# Python 2, ~~73~~ 70 bytes

A function that takes a string as input and returns a string representation of a Python list. Zero can be represented both by `0` and `-0` (when it comes last):

```
lambda s:`map(len,s.split('0'))`.replace('0, ','-').replace('--','0,')

```

### Explanation

1. `split` the input string `s` on zeroes.
2. Take the length of each string in the resulting list (using `map`).

That takes us a long way. Zeroes were separators after all. And the numbers were unary, so `len` conveniently converts those to decimal. But now we've messed up all the non-separator uses of `0`. Luckily, all non-separator uses were leading zeroes so they came after a separator-zero and gave us zero-length strings (`'00'.split('0') == ['', '', '']`). Those zero-length strings then also became `0` because of the `len`.

3. Turn the list into a string (using "reverse quotes"), so we can fix up the mess more easily.
4. `replace` each zero that precedes another number by a negative sign on that number instead. That fixes the use of `0` as a sign but it breaks the literal zeroes. Literal zeroes were also preceded by a separator, so they've now become pairs of extra dashes on the next number.
5. `replace` each `--` back into a `0` element in the "list".

# Answer
> 9 votes
# Retina, ~~23~~ 21 bytes

```
(.)0
$1
01
-1
1+
$.&

```

Try it online!

The first stage `(.)0<newline>$1<space>` matches any character followed by a `0`. The match is replaced by the first character followed by a space. This splits the string in the individual numbers.

The second stage `01<newline>-1` replaces `0`'s before a block of `1`'s to to the `-` sign.

The last stage `1+<newline>$.&` matches all blocks of `1`'s and replaces them with the length of the group.

Here is an example with the output of the individual stages.

# Answer
> 7 votes
# Vim, 56 bytes

```
:s/\v(0?1*)0?/\1\r/g|%s/0/-/|%s/1*$/\=len(submatch(0))
D

```

Try it online!

I haven't posted in vim in a while. I'm mostly using vim because V is a pain sometimes. Because the `count` command, which is perfect for getting the number of '1's on the line will overwrite any '0's on the line, so we can't negate it afterwards.

Explanation:

This is one byte shorter then the straightforward way:

```
:s/\v(0?1*)0?/\1\r/g
:%s/0/-
:%s/1*$/\=len(submatch(0))
D

```

due to command chaining. Since that one separates the commands, I'll use it for the explanation.

```
:s/                     " Substitute
                        " Search for...
   \v                   "   Enable 'magic'. This determines whether certain atoms require a backslash or not.
                        "   Without it we would have: '\(0\?1*\)0\?', which is 2 bytes longer
      0?                "   An optional 0
        1*              "   Followed by any number of '1's
     (    )             "   (call that group 1)
           0?           "   Followed by another optional 0
             /          " Replace it with...
              \1        "   Subgroup 1
                \r      "   A newline
                  /g    " Do this for every match on the current line.

```

Now, each signed unary number is on an individual line. Using '11100110001' as an example, at this point we'll have:

```
111
011
0
1

:%s/0   " Replace every 0
     /- " With a dash

:%s/1*$/                    " Replace every run of 1's at the end of a line
        \=len(submatch(0))  " With the length of said run

```

Since we added newlines at the end of each match, we had an empty line before running that. After running that, we'll have a '0' (because it matched a run of 0 '1's). So we just call `D` to delete this line, leaving it blank

# Answer
> 7 votes
# Haskell, ~~68~~ 66 bytes

```
f(x:r)|(a,b)<-span(>0)r=([(0-),(1+)]!!x$sum a):[z|_:t<-[b],z<-f t]

```

Try it online! Takes input as a list of zeros and ones. Example usage: `f [0,0,0,1,1]` yields `[0,-2]`.

**Explanation:**

The pattern matching in `f(x:r)|(a,b)<-span(>0)r` binds `x` to the first element of the input, `a` to a (potentially empty) list of following `1`s, and `b` to the rest of the input. Given an input `[0,1,1,1,0,0,1]`, we get `x=0`, `a=[1,1,1]` and `b=[0,0,1]`.

The current number is then either the sum of `a` negated if `x=0`, or the sum of `a` plus one if `x=1`. This is achieved by indexing with `x` into a list containing a negation and increment function, and applying the resulting function to the sum of `a`: `[(0-),(1+)]!!x$sum a`.

The rest list `b` is either empty or contains a separating zero and the next number. The list comprehension `[z|_:t<-[b],z<-f t]` tries to match `b` on the pattern `_:t`, that is forget the head element and bind the rest of the list to `t`. If `b` is empty this match fails and the list comprehension evaluates to `[]`, which is the base case for the recursion. Otherwise the function `f` is recursively applied to `t` and the list comprehension evaluates to all elements `z` from the result of `f t`.

# Answer
> 4 votes
# Perl 5, 40 + 1 (`-n`) = 41 bytes

```
print'-'x/00/.y/1//.$"for"0$_"=~/00?1*/g

```

Try it online!

# Answer
> 4 votes
# Husk, ~~20 18 17 15~~ 14 bytes

```
Γ~:?Σṁ_Πȯ₀tΣġ/

```

Try it online!

## Explanation

```
Γ~:?Σṁ_Πȯ₀tΣġ/  Input is a list, say x = [0,1,1,0,0,0,1,1]
            ġ   Group by
             /  division.
                This splits x right before each 0: [[0,1,1],[0],[0],[0,1,1]]
Γ               Deconstruct into head y = [0,1,1] and tail z = [[0],[0],[0,1,1]]
   ?Σṁ_Π        Apply to y:
       Π         Product: 0
   ?Σ            If that is nonzero, take sum of y,
     ṁ_          else take sum of negated elements of y: u = -2
        ȯ₀tΣ    Apply to z:
           Σ     Concatenate: [0,0,0,1,1]
          t      Drop first element: [0,0,1,1]
         ₀       Recurse: [0,2]
 ~:             Tack u to the front: [-2,0,2]

```

The splitting works like this. `ġ/` splits its argument between each pair of elements `a,b` for which `/a b` is falsy. `/a b` is division with flipped arguments, so `b` divided by `a`. The relevant values in this program are these:

* `/1 1` gives `1` (truthy).
* `/1 0` gives `0` (falsy).
* `/0 1` gives `Inf` (positive infinity, truthy).
* `/0 0` gives `Any` (a special NaN-like value, falsy).

# Answer
> 3 votes
# Wolfram Language (Mathematica), 80 bytes

```
StringCases[#<>"0",x_~~Shortest@y___~~"0":>(If[x=="0",-#,#+1]&)@StringLength@y]&

```

Try it online!

Abuses the mechanic of `StringCases`, since it does not check overlapping patterns. Since we search from left to right, without overlaps, we always get only the integers we need.

## Explanation

```
#<>"0"

```

Append a zero at the end

```
StringCases

```

Find all of the following pattern...

```
x_~~Shortest@y___~~"0"

```

A single character (call it `x`), followed by the shortest possible zero-length or longer string (call it `y`), followed by a zero.

```
(If[x=="0",-#,#+1]&)@StringLength@y

```

Apply to matching pattern: take the length of `y`. If `x` is zero, then negate the value. Else, increment one.

This covers `00` as well, since `y` would be an empty string, and we would compute `-0` ( `== 0`).

# Answer
> 3 votes
# Brain-Flak, 94 (70?) bytes

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

```

Try it online!

This is actually surprisingly terse for brain-flak.

Here is a commented/readable version:

```
([])

{

    #Pop the Stack height
    {}

    (
        #If there isn't a leading 0, evaluate to 1...
        {
            (<()>)

            ()
        }

        #Pop the 0
        {}

        #Push a 0 onto the alternate stack
        (<>)
        <>

        #Run of '1's
        {
            #Decrement the alternate stack
            <([{}]<>{})>
            <>
        }

        #And push it here
    )

    #Was there a not leading 0?

    {
        {}

        #Invert the value on the alternate stack
        <>([{}])(<>)
    }

    #Pop 2 zeros
    {}{}

    ([])

}{}<>

#Push stack height
([])

#Reverse the stack
{

    {}

    ({}<>)

    <>([])

}<>

```

If the output can be in reverse, we can do this for 70 instead:

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

```

This tip of mine is *almost* perfect for this situation. But it doesn't quite work since we have to push a 0 before doing the operation (counting the '1's), and the operation happens in a loop. The shortest I could come up with utilizing this tip is:

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

```

which is also 94 bytes.

# Answer
> 3 votes
# *Acc!!*, ~~252~~ 237 bytes

```
N
Count i while _/48 {
Count n while 48/_ {
Write 45
50+N
}
_+49/_*50
Count u while _%50/49 {
_+100-_%50+N
}
_/50-1
Count h while _/200 {
Write _/200+48
_%200+1
}
Count t while _/20+_%2 {
Write _/20+48
_%20-_%2
}
Write _/2+48
Write 9
N
}

```

Uses `-0`. Outputs numbers separated by tab characters, with a trailing tab. Try it online!

Amount of time writing the actual algorithm: 20 minutes. Amount of time debugging my decimal output code: 45 minutes. :^P

### With comments

I don't know if these comments explain the code very well--they're based on my notes to myself while I was writing it, so they assume some understanding of how *Acc!!* works. If anything needs more explanation, let me know and I'll try to make it clearer.

```
# We partition the accumulator _ as [number][flag][nextchar]
# [flag] is a 2-value slot and [nextchar] a 50-value slot
# So [nextchar] is _%50, [flag] is _/50%2, [number] is _/100
# [flag] is 1 if we're in the middle of reading a number, 0 if we're between numbers
# It is also used for outputting as decimal (see below)
# Possible input characters are 0, 1, and newline, so [nextchar] is 48, 49, or 10

# Read the first character
N
# Loop while the character we just read is 0 or 1 and not newline
Count i while _/48 {
  # What we do in the loop depends on the combination of [flag] and [nextchar]:
  # 0,48 (start of number, read 0) => write minus sign, [flag] = 1, read another char
  # _,49 (read 1) => increment [number], [flag] = 1, read another char
  # 1,48 (middle of number, read 0) => write/clear [number], status = 0, read another
  #      char
  # 1,10 (middle of number, read <cr>) => ditto; the next read will be 0 for eof, which
  #      means the acc will be less than 48 and exit the loop

  # Process leading 0, if any
  Count n while 48/_ {
    # acc is 48: i.e. [number] is 0, [flag] is 0, [nextchar] is 48 (representing a 0)
    # Output minus sign
    Write 45
    # Set [flag] to 1 (thereby exiting loop) and read [nextchar]
    50+N
  }
  # If number starts with 1, then we didn't do the previous loop and [flag] is not set
  # In this case, acc is 49, so we add (50 if acc <= 49) to set [flag]
  _+49/_*50

  # Process a run of 1's
  Count u while _%50/49 {
    # [nextchar] is 49 (representing a 1)
    # Increment [number] and read another
    _+100-_%50+N
  }

  # At this stage, we know that we're at the end of a number, so write it as decimal
  # This is "easier" (ha) because the number has at most three digits
  # We shift our partitioning to [number][flag] and set [flag] to 0
  _/50-1

  # Output hundreds digit if nonzero
  # Since [number] is _/2, the hundreds digit is _/200
  Count h while _/200 {
    Write _/200+48
    # Mod 200 leaves only tens and units; also, set [flag] to 1
    _%200+1
  }
  # Output tens digit (_/20) if nonzero OR if there was a hundreds digit
  # In the latter case, [flag] is 1
  Count t while _/20+_%2 {
    Write _/20+48
    # Mod 20 leaves only units; clear [flag] if it was set
    _%20-_%2
  }
  # Write units unconditionally
  Write _/2+48

  # Write a tab for the separator
  Write 9
  # Read another character
  N
}

```

# Answer
> 3 votes
# Jelly,  ~~19~~  18 bytes

There must be a better way...

```
®ḢN$Ḣ©?ṄEȧ
ṣ0L€ÇL¿

```

A full program printing each number followed by a linefeed.

**Try it online!**

### How?

```
®ḢN$Ḣ©?ṄEȧ - Link 1, print first number and yield next input: list of numbers, X
           -                              e.g. [8,0,15,16,...] or [0,4,8,0,15,16,...]
      ?    - if...
    Ḣ      - condition: yield head and modify  8([0,15,16,...])   0([4,8,0,15,16,...])
     ©     -            (copy to register)     8                  0
®          - then: recall from the register    8
   $       - else: last two links as a monad:
 Ḣ         -         yield head and modify                        4([8,0,15,16,...])
  N                  negate                                      -4
       Ṅ   - print that and yield it           8                 -4
        E  - all equal (to get 0 to be truthy) 1                  1
         ȧ - AND the (modified) input          [0,15,16,...]      [8,0,15,16,...]
           -   (ready to be the input for the next call to this link)

ṣ0L€ÇL¿ - Main link: list e.g. [0,1,0,0,0,0,1,1]
ṣ0      - split at zeros       [[],[1],[],[],[],[1,1]
  L€    - length of €ach       [0,1,0,0,0,2]
      ¿ - while...
     L  - condition: length                           1  1  1  0  ([0,1,0,0,0,2], [0,0,0,2], [0,2], [])
    Ç   - action: call the last link (1) as a monad  -1  0 -2     ( - 1            - 0        - 2)

```

# Answer
> 2 votes
# Python 2, ~~96~~ 92 bytes

```
lambda s:[[len(t),-len(t)+1]['1'>t]for t in s.replace('10','1 ').replace('00','0 ').split()]

```

Try it online!

Thx to ovs and DLosc for 2 bytes each.

# Answer
> 2 votes
# , 119 bytes

```
function(x){n=nchar
y=regmatches(x,regexec("(0?)(1*)0?([01]*)",x))[[1]]
cat((-1)^n(y[2])*n(y[3]),"")
if(y[4]>0)f(y[4])}

```

Try it online!

The code uses this solution from stackoverflow for a related problem (Thanks to jeales for the idea). The output is a space-separated string printed to stdout.

# Answer
> 2 votes
# sed, 227 bytes

```
s/^.o*/<&>/
:a
s/>z\(.o*\)/><\1>/
ta
:b
s/z>/0>/g
y/z/-/
s/oooooooooo/x/g
s/ooooooooo/m9/g
s/oooooooo/m8/g
s/ooooooo/m7/g
s/oooooo/m6/g
s/ooooo/m5/g
s/oooo/m4/g
s/ooo/m3/g
s/oo/m2/g
s/o/m1/g
s/x\([^xm]\)/x0\1/g
s/m//g
y/x/o/
tb

```

Try it online!

## Usage

0 and 1 for input are replaced with z and o respectively. Input is given from stdin, on every line.

## With comments

```
# first integer
s/^.o*/<&>/
# find each item
:a
s/>z\(.o*\)/><\1>/
ta
# below: to decimal
:b
# to zero
s/z>/0>/g
# minus sign
y/z/-/
# to decimal others
# m letter indicates that converting a digit is done
s/oooooooooo/x/g
s/ooooooooo/m9/g
s/oooooooo/m8/g
s/ooooooo/m7/g
s/oooooo/m6/g
s/ooooo/m5/g
s/oooo/m4/g
s/ooo/m3/g
s/oo/m2/g
s/o/m1/g
# not converted yet? then to 0
s/x\([^xm]\)/x0\1/g
s/m//g
y/x/o/
# repeat until every unary is converted
tb

```

# Answer
> 1 votes
# QBasic, ~~88~~ 86 bytes

```
1u$=INPUT$(1)
z=u$<"1
IF n*z THEN?(1-2*s)*(n-s):s=0:n=0ELSE s=s-z:n=n+1
IF"!"<u$GOTO 1

```

This was fun. Multiple revisions starting from a 107-byte version resulted in one of the most obfuscated bits of QBasic I think I've ever written. *(Edit: Oddly enough, I was able to golf 2 bytes by making the code clearer.)*

Note: this program reads user input one character at a time without echoing it to the screen (a result of using `INPUT$(1)` instead of the usual `INPUT` statement). So as you're typing, you won't see the 1's and 0's, but the decimal numbers will appear as they are calculated. Make sure to hit `Enter` at the end of the input to see the last number and end the program.

### Ungolfed version

```
sign = 0
num = 0
DO
  digit$ = INPUT$(1)
  isZero = (digit$ < "1")
  IF num > 0 AND isZero THEN
    PRINT (1 - 2 * sign) * (num - sign)
    sign = 0
    num = 0
  ELSE
    IF isZero THEN sign = 1
    num = num + 1
  END IF
LOOP WHILE "!" < digit$

```

### Explanation

(AKA "What?? That still makes no sense!")

The base strategy is to run a loop that grabs one character from `INPUT$(1)` each time through, does stuff with it, and keeps looping as long as the character has an ASCII value greater than that of `!` (i.e., wasn't a newline).

We keep track of numbers-in-progress using two variables. `num` is the number of characters in the current signed unary number (including any leading zero). `sign` is `1` if the number had a leading zero, `0` if not. Both of these need to be initialized to `0`, which is great for the golfed version because numeric variables in QBasic are automatically initialized to `0`.

Whenever we read a character, the first thing is to determine whether it's `1` or `0`. We'll use this result twice, so we store it in `isZero`. Technically, that name is misleading, since the value will also be truthy if the character is a newline. Note that truthy in QBasic is `-1` and falsey is `0`.

Now, if we're in the middle of reading a number (`num > 0`) and we hit a zero or end of input (`isZero`), we need to calculate which number we've finished reading.

* `sign` stores `0` for positive, `1` for negative. To get `1` for positive and `-1` for negative, we need `1-2*sign`.
* `num` stores the correct magnitude for positives but one more than the magnitude for negatives (since it includes the sign marker). So we can use `num-sign` for the magnitude.

Multiply these together and print; then reset `sign` and `num` to `0` in preparation for reading the next number.

Otherwise (if we haven't hit a zero, or if we've hit a zero at the beginning of a number), we update `sign` and `num` as follows:

* `sign` becomes `1` if we're looking at a leading zero; otherwise, if we're looking at a one, it stays at whatever it already was. The golfed code is `s=s-z`, which amounts to the same thing:
    + If this is a leading zero, `z` is `-1`. Since `s` is guaranteed to be `0` (because this is the start of a new number), `s-z` will be `1`.
    + If this is a one, `z` is `0`. Then `s-z` stays at whatever value `s` had previously.
* `num` is incremented.

That's it!

# Answer
> 1 votes
# Jelly, 15 bytes

```
Ż¬<\œp$ḊLCṛ¡ḢƊ€

```

Try it online!

Although it's something of an improvement over the previous solution, this feels clumsy. (Though not as clumsy now that it doesn't use `k`.)

Input as a list of zeroes and ones.

```
Ż                  Prepend a leading zero to the input.
 ¬                 Flip 0 <-> 1.
    œp$            Split that around the corresponding locations of truthy elements of
  <\               it cumulatively reduced by greater than.
       Ḋ           Remove the leading empty slice,
             Ɗ€    then for each remaining slice:
        L          take the length,
         C         and subtract it from 1
           ¡       a number of times equal to
          ṛ Ḣ      the first element.

```

# Answer
> 0 votes
# JavaScript (ES6), 60 bytes

Returns a space-separated list of integers.

```
s=>(0+s).replace(/00?1*/g,s=>(l=s.length,+s[1]?l-1:2-l)+' ')

```

### Test cases

```
let f =

s=>(0+s).replace(/00?1*/g,s=>(l=s.length,+s[1]?l-1:2-l)+' ')

console.log(f("1")) // 1
console.log(f("0")) // 0
console.log(f("011")) // -2
console.log(f("1101")) // 2,1
console.log(f("1100")) // 2,0
console.log(f("11001")) // 2,-1
console.log(f("110001")) // 2,0,1
console.log(f("11100110001")) // 3,-2,0,1
console.log(f("00000001")) // 0,0,0,-1
console.log(f("01111011111111001111111111111110111111111111111100111111111111111111111110111111111111111111111111111111111111111111")) // -4,8,-15,16,-23,42
console.log(f("01111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111")) // -127
```

# Answer
> 0 votes
# Lua, 58 bytes

```
(...):gsub("(0?)(1*)0?",function(s,n)print(#n-2*#s*#n)end)

```

Try it online!

Full program, takes input from the command line and prints the numbers to stdout separated by newlines.

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


title: "Factorise" a quadratic

text:
# Question
Title: "Factorise" a quadratic
When learning to factorise quadratics in the form \\$x^2 + ax + b\\$, a common technique is to find two numbers, \\$p, q\\$ such that

$$pq = b \\ p + q = a$$

as, for such numbers, \\$x^2 + ax + b = (x + p)(x + q)\\$

You are to take two integers \\$a, b \in (-\infty, +\infty)\\$ and output the two integers \\$p, q\\$ such that

$$pq = b \\ p + q = a$$

You may take input in any convenient method and you may assume that a solution always exists.

This is so the shortest code in bytes wins

## Test cases

```
2, -15 -> 5, -3
-22, 85 -> -5, -17
6, -16 -> -2, 8
-8, -240 -> -20, 12
-1, -272 -> 16, -17
17, 16 -> 1, 16
-4, 0 -> 0, -4
3, -54 -> 9, -6
13, 40 -> 8, 5
-29, 198 -> -11, -18
11, -12 -> -1, 12
4, -320 -> 20, -16
4, 4 -> 2, 2

```

# Answer
> 10 votes
# Scala 3, ~~49~~ 44 bytes

```
a=>b=>(-b*b to b*b)map(p=>a-p->p)find(_*_==b)

```

Try it onlne!

Takes `(a)(b)` and returns an `Option[(Int, Int)]`. It's now a little more inefficient since it goes from \\$-b^2\\$ to \\$b^2\\$ instead of \\$-|b|\\$ to \\$|b|\\$, including values that \\$p\\$ and \\$q\\$ could never be, but it saves 4 bytes.

```
a => b =>
  (-b*b to b*b)              //Make a range of all possible q's and then some
    map(q => (a - q, q))     //Make a tuple of (p, q)
    find(_ * _ == b)         //Find a pair such that p * q = b

```

# Answer
> 9 votes
# JavaScript (ES7),  ~~37 36 34~~  31 bytes

*Saved 3 bytes thanks to @tsh*

Expects `(a)(b)`.

```
a=>b=>[b=a/2+(a*a/4-b)**.5,a-b]

```

Try it online!

# Answer
> 9 votes
# Wolfram Language (Mathematica), ~~23~~ ~~21~~ 18 bytes

```
Solve[x x+#2==x#]&

```

Try it online!

# Answer
> 7 votes
# Jelly, 5 bytes

```
1ṭÆrN

```

Try it online!

Input as a list `[b, a]`.

```
1ṭ       Append 1 to the input, (resulting in [b, a, 1])
  Ær     find roots of polynomial from little-endian coefficient list,
    N    negate each root.

```

# Answer
> 6 votes
# Python 3.8, <sup>~~42~~ ~~39~~</sup> 37 bytes

Saved 2 bytes thanks to Danis!!!

```
lambda a,b:[c:=a/2+(a*a/4-b)**.5,a-c]

```

Try it online!

Port of Arnauld's JavaScript answer.

# Answer
> 6 votes
# Retina 0.8.2, 94 bytes

```
\d+
$*
^(-?)(1*)(,(-)(?<2>\2(1(1)*))|(?<5>(?<6>1)*),)(?<-6>\2)*$(?(6)1)
$1$.2,$4$1$.5
--

-0
0

```

Try it online! Link includes test cases. Explanation: \\$|p|\\$ is captured in `$2` and \\$|q|\\$ is captured in `$5`, with `$6` being a helper balancing group used to verify the multiplication.

```
\d+
$*

```

Convert to unary.

```
^(-?)(1*)

```

Start by matching the sign of \\$a\\$, then initially assume \\$|p|\\$ is no greater than \\$|a|\\$.

```
(,(-)(?<2>\2(1(1)*))

```

If \\$b\\$ is negative, then we actually end up matching \\$|a|\\$, and choose \\$|q|\\$ and overwrite `$2` with \\$|p|=|a|+|q|\\$, so \\$|a|=|p|+|q|\operatorname{sgn}(b)\\$.

```
|(?<5>(?<6>1)*),)

```

Otherwise \\$b\\$ is positive, so overwrite `$5` with \\$|q|\\$ such that \\$|a|=|p|+|q|\operatorname{sgn}(b)\\$.

```
(?<-6>\2)*$(?(6)1)

```

Ensure \\$|b|=|pq|\\$.

```
$1$.2,$4$1$.5

```

Output \\$p = |p|\operatorname{sgn}(a)\\$ and \\$q = |q|\operatorname{sgn}(ab)\\$. We then have \\$p+q=|p|\operatorname{sgn}(a)+|q|\operatorname{sgn}(ab)=(|p|+|q|\operatorname{sgn}(b))\operatorname{sgn}(a)=|a|\operatorname{sgn}(a)=a\\$ while \\$pq=|p|\operatorname{sgn}(a)|q|\operatorname{sgn}(ab)=|pq|\operatorname{sgn}(b)=|b|\operatorname{sgn}(b)=b\\$ as desired (where \\$\operatorname{sgn}(0)=1\\$).

```
--

-0
0

```

Fix up extraneous `-`s.

# Answer
> 6 votes
# Charcoal, 25 bytes

```
ＮθＮηＩ⊟ΦＥ…·±↔η↔η⟦ι⁻θι⟧⁼ηΠι

```

Try it online! Link is to verbose version of code. Same idea as @user's Scala solution. Explanation:

```
ＮθＮη

```

Input \\$a\\$ and \\$b\\$.

```
Ｅ…·±↔η↔η

```

Loop \\$p\\$ over \\$\[-|b|,|b|\]\\$.

```
⟦ι⁻θι⟧

```

For each \\$p\\$ create a list \\$(p,q)\\$ where \\$q=a-p\\$.

```
Ｉ⊟Φ...⁼ηΠι

```

Output the one with the highest \\$p\\$ where \\$pq=b\\$.

# Answer
> 6 votes
# Octave, 17 bytes

```
@(x)-roots([1 x])

```

Try it online!

You simply need to solve \\$x^2 + ax + b = (x + p)(x + q) = 0\\$, and \\$x\_1=-p\\$, \\$x\_2=-q\\$.

# Answer
> 5 votes
# 05AB1E, ~~17~~ 16 bytes

```
(Dn4I*-t‚DOsÆ);(

```

Try it online!

Why oh why aren't there any built-ins for this? This solves the quadratic equation to get the two roots. *-1 thanks to @ovs*

# Answer
> 4 votes
# Wolfram Language (Mathematica), ~~28 bytes~~ 24 bytes

thanks to att

```
#&@@Solve[#-b==a==#2/b]&

```

Try it online!

# Answer
> 4 votes
# Brachylog, 8 bytes

```
~+ʰ⟨≜×⟩Ċ

```

Try it online!

Takes input as a list `[a,b]`.

```
  ʰ         For the first element of the input,
~+          get a list of integers which sum to it
    ≜       (in order of least absolute value of the first element).
   ⟨ ×⟩     Its product is the second element,
       Ċ    its length is 2,
            and it's the output.

```

I'm not entirely sure why this needs , but it comes at no cost because the "sandwich" construct `⟨~+×⟩` won't parse without braces around `~+` anyhow (and both `⟨{~+}×⟩Ċ` and `~+ʰ⟨≡×⟩Ċ` would still come out to 8).

# Answer
> 4 votes
# APL (Dyalog Unicode), ~~28~~ 26 bytes

-2 thanks to Razetime.

```
{⍺-⎕←(⍺÷2)+.5*⍨⍵-⍨⍺×⍺÷4}

```

Try it online!

# Answer
> 4 votes
# dc, 24 bytes

Input is a line of two numbers from STDIN. Output is to STDOUT.

```
?rdsad*r4*-vla+2/dlar-rf

```

Try it online!

## Explanation

```
?                        # Read a line of input
 r                       # Swap the two numbers
  dsa                    # Store to `a` w/o popping
     d*                  # Square the 1st input
       r                 # Swap up the second input
        4*               # Multiply by four
          -              # Second-to-top - TOS
           v             # Square root
            la+          # Add by `a`
               2/        # Halve
                 d       # Duplicate
                  lar-   # Push `a` - TOS
                      r  # Swap the top 2 items
                       f # Print entire stack

```

# Answer
> 4 votes
# Python 3.8 (pre-release), 37 bytes

```
lambda a,b:[p:=a/2+(a*a/4-b)**.5,a-p]

```

Try it online!

**Python 2, 42 bytes**

```
def f(a,b):p=a/2+(a*a/4-b)**.5;print p,a-p

```

Try it online!

Takes input as float, and prints the output.

# Answer
> 4 votes
# , ~~36~~ 35 bytes

```
function(b,c)b/2+-.5:1*(b^2-4*c)^.5

```

Try it online!

Uses the Quadratic formula with `a=1`.

# Answer
> 4 votes
# Husk, 12 bytes

```
ḟo=¹ΠmSe`-²ṡ

```

Try it online!

Port of user's Scala answer.

```
           ṡ    # range of integers from -arg1 to +arg1
     m          # map over each of them
      S         # combining itself
       e        # into a 2-element list with
        `-²     # arg2 minus this;
ḟ               # now find the first element that satisfies
 o              # combine 2 functions:
    Π           # product
  =¹            # equals arg1

```

# Answer
> 4 votes
# C (gcc) `-lm`, 45 bytes

```
f(int*a){*a-=a[1]=(*a+sqrt(*a**a-4*a[1]))/2;}

```

Try it online!

Modifies an input array of 2 `int`s.

---

### C (gcc), 53 bytes

```
i;f(int*a){for(i=*a/2;(*a-i)*i-a[1];i--);*a-=a[1]=i;}

```

Try it online!

Doesn't use `sqrt`.

# Answer
> 3 votes
# APL (Dyalog Extended), 19 bytes

-2 thanks to @Bubbler

```
÷∘2⍛{⍺(+,-)√⍵-⍨⍺*2}

```

Try it online!

# Answer
> 3 votes
# Haskell, ~~46~~ 39 bytes

```
a!b=[(k,b-k)|k<-[-a*a..],k*b-k*k==a]!!0

```

Try it online!

Kind of boring, but short.

# Answer
> 3 votes
# convey, 113 bytes

```
v<1
>>>v 0
{?>*"-"v
4*  "vvv
 v  >*vv
v#<<<<vv
-<    vv
*%2   v>v
.1    v}>v
v     v%2v}%2
">>>>>-^>+>^
>>>>>>>>^

```

Try it online!

Ungolfed, mostly. Uses quadratic formula.

# Answer
> 2 votes
# Ruby, ~~41~~ ~~37~~ 35 bytes

*A port of Arnauld's answer in Ruby!*

```
->a,b{[b=a/2r+(a*a/4r-b)**0.5,a-b]}

```

Try it online!

# Answer
> 2 votes
# Julia 1.0, 34 bytes

```
(a,b)->(d=(a*a-4b)^.5;[a+d,a-d]/2)

```

Try it online!

# Answer
> 2 votes
# MathGolf, 13 bytes

```
_½\²¼k-√+`-αÞ

```

I/O as floats.

Port of *@Arnauld*'s JavaScript answer.

Try it online.

I have the feeling this can be a byte shorter with some smart stack manipulations, but I've been unable to find anything yet. An equal-bytes alternative could be `²¼k-√`;½+`-αÞ`.

**Explanation:**

```
_             # Duplicate the first (implicit) input-float
 ½            # Halve it
  \           # Swap so the first input is at the top of the stack again
   ²          # Square it
    ¼         # Divide it by 4
     k-       # Subtract the second input-float
       √      # Take the square-root of that
        +     # Add it to the halved first input that's still on the stack
         `    # Duplicate the top two values (since the stack only contains a single
              # item, this will first add the first input-float implicitly as leading
              # item, and then duplicate both items)
          -   # Subtract the top two items from one another
           α  # Pair the top two items
            Þ # Only leave the top item of the stack, and discard everything else
              # (after which the entire stack is output implicitly as result)

```

# Answer
> 2 votes
# Vyxal, 3 bytes

```
∆QN

```

Try it Online!

Solve for the roots and then negate

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

```
D(Ÿʒ-y*¹Q

```

Try it online!

Takes input as

```
b
a

```

In case \\$p=q\\$ it returns only a single value. In case that's not allowed, it's +5 bytes for appending `}Ðgi«`

Explanation:

```
D              duplicate
)              negate
Ÿ              range, so [-b,.. , b]
ʒ              filter
 -             minus the implicit a
  y            the current number
   *           multiply
    ¹          the first item from the input history - b
     Q         is equals

```

# Answer
> 2 votes
# Whispers v2, ~~110~~ 92 bytes

*Edit: -18 bytes (within less than 2 minutes of submission!) thanks to caird coinheringaahing and the `±` operator*

```
> Input
> Input
> 2
> 4
>> 1*3
>> 2⋅4
>> 5-6
>> √7
>> 8÷3
>> 1÷3
>> 10±9
>> Output 11

```

Try it online!

My first **Whispers** program.
Uses the Quadratic formula with `a=1`.

# Answer
> 1 votes
# Pari/GP, 33 bytes

```
f(a,b)=round(polroots(x^2+a*x+b))

```

Try it online!

# Answer
> 1 votes
# Haskell, 39 bytes

```
f a b=let c=a/2+(a*a/4-b)**0.5in[c,a-c]

```

Try it online!

---
Tags: code-golf, math, number-theory, polynomials, factoring
---


title: Finding Distant Primes

text:
# Question
Title: Finding Distant Primes
Let us call a prime \\$p\\$ an \\$(m,k)\\$-distant prime \\$(m \ge 0, k \ge 1, m,k \in\mathbb{Z})\\$ if there exists a power of \\$k\\$, say \\$k^x (x \ge 0, x \in\mathbb{Z})\\$, such that \\$|k^x-p| = m. \\$ For example, \\$23\\$ is a \\$(9,2)\\$-distant prime as \\$|2^5 - 23| = 9\\$. In other words, any prime which is at a distance of \\$m\\$ from some non-negative power of \\$k\\$ is an \\$(m,k)\\$-distant prime.

For this challenge, you can either:

* Take input three integers \\$n, m, k\\; (n,k \ge1, m \ge0)\\$ and print the \\$n^{th}\\$ \\$(m,k)\\$-distant prime. You do not need to handle inputs where answer does not exist. You can take \\$n\\$ as zero-indexed if you want.
* Take \\$n, m, k\\$ as input and print the first \\$n\\$ \\$(m,k)\\$-distant primes.
* Or, take only \\$m\\$ and \\$k\\$ as input and print all \\$(m,k)\\$-distant primes. It is fine if your program runs infinitely and does not terminate if there aren't any \\$(m,k)\\$-distant primes, or all such primes have already been printed.

# Examples

```
m,k    -> (m,k)-distant primes
1,1    -> 2
0,2    -> 2
1,2    -> 2, 3, 5, 7, 17, 31, 127, 257, 8191, 65537, 131071, 524287, ...
2,2    -> 2, 3
2,3    -> 3, 5, 7, 11, 29, 79, 83, 241, 727, 6563, 19681, 59051
3,2    -> 5, 7, 11, 13, 19, 29, 61, 67, 131, 509, 1021, 4093, 4099, 16381, 32771, 65539, 262147, ...
20,2   -> None
33,6   -> 3
37,2   -> 41, 53, 101, 293, 1061, 2011, 4133, 16421, ...
20,3   -> 7, 23, 29, 47, 61, 101, 223, 263, 709, 2207, 6581, 59029, 59069, 177127, 177167
20,7   -> 29, 2381, 16787
110,89 -> 199, 705079

```

# Rules

* Standard loopholes are forbidden.
* You may choose to write functions instead of programs.
* This is , so the shortest code (in bytes) wins.

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

Expects `(m)(k)(n)` and returns the \\$n\\$-th \\$(m,k)\\$-distant prime (1-indexed).

```
m=>k=>F=(n,p)=>(g=d=>p%--d?g(d):d^1)(p)|(g=(n,K=1)=>K>n||K<n&k>1&&g(n,K*k))(p+m)*g(p-m)||--n?F(n,-~p):p

```

Try it online!

### Commented

```
m => k =>            // outer functions taking m and k
F = (n, p) =>        // inner recursive function taking n
(                    // and using p = current prime candidate
  g = d =>           // g is a recursive function taking a divisor d
    p % --d ? g(d)   //   decrement d until it divides p
            : d ^ 1  //   return a truthy value if p is composite
)(p) |               // initial call to g with d = p
(                    //
  g = (n,            // g is a recursive function taking n = p + m or p - m
          K = 1) =>  // and K = k ** x
    K > n ||         //   if K is greater than n
    K < n & k > 1 && //   or K is less than n and k is greater than 1:
      g(n, K * k)    //     do a recursive call with k raised to the next exponent
)(p + m) *           // unless the above function is truthy for p + m ...
g(p - m)             // ... and for p - m (meaning that we don't have |k**x-p|=m)
                     // or p was composite:
|| --n               //   decrement n
?                    // if all of the above is truthy:
  F(n, -~p)          //   try again with p + 1
:                    // else:
  p                  //   success: return p

```

# Answer
> 4 votes
# Brachylog, 13 bytes

```
^ᵗ↙X≜ℕ₁ᵗ~ȧʰ+ṗ

```

Try it online!

```
^ᵗ↙X≜ℕ₁ᵗ~ȧʰ+ṗ  Given input [A,B]
^ᵗ↙X≜          Try every X: [A, B^X]
     ℕ₁ᵗ       B^X ≥ 1
        ~ȧʰ    Try [A, B^X] and [-A, B^X]
           +   Sum of A + B^X or -A + B^X
            ṗ  is a prime.

```

# Answer
> 4 votes
# Haskell, ~~96~~ ~~88~~ 70 bytes

* Saved 8 bytes thanks to @ovs!
* Saved 18 bytes thanks to @Delfad0r!

```
m!k=[p|p<-[2..],all((>0).mod p)[2..p-1],elem m[abs$k^i-p|i<-[0..m+p]]]

```

Try it online!

```
m!k=                       -- The function's called with m!k
  [p|                      -- Yield every p when
   p <- [2..],           -- p is an integer >= 2
   all((>0).mod p)[2..p-1], -- p is prime
   all                      -- For all
                  [2..p-1]  -- possible divisors of p,
            mod p               -- p mod that number
        >0                      -- is greater than 0
   elem m[abs$k^i-p|i<-[0..m+p]] -- Make sure it's (m, k)-distant

```

# Answer
> 3 votes
# Jelly, ~~16~~ 15 bytes

```
2Ẓȧ+,_ɗ⁴æḟƑƇɗɗ#

```

Try it online!

Takes three command line arguments \\$k\\$, \\$m\\$, \\$n\\$. Produces the first \\$n\\$ \\$(m, k)\\$-distant primes.

## Explanation

```
2Ẓȧ+,_ɗ⁴æḟƑƇɗɗ#   Main dyadic link
2                 Starting with 2
              #   Find the first n numbers p such that
             ɗ    (
 Ẓ                  p is prime
  ȧ                 and
            ɗ       (
   +,_ɗ⁴              p ± m
           Ƈ          Filter items that
          Ƒ             don't change when
        æḟ                rounded down to the nearest power of k
            ɗ       )
             ɗ    )

```

# Answer
> 2 votes
# , 79 bytes

```
function(m,k)repeat{while(sum(!(T=T+1)%%2:T)>1|all(abs(k^(0:T)-T)-m))1;show(T)}

```

Try it online!

Prints all (m,k)-distant primes.

# Answer
> 0 votes
# JavaScript (V8), 91 bytes

```
m=>k=>{for(i=1;;(g=v=>!v+!~-k+v%k?~-v:g(v/k))(i-m)*g(i+m)+~-j||print(i))for(j=++i;i%--j;);}

```

Try it online! (`i<1000` is added so you can test it with multiple testcases.)

This function takes only \\$m\\$ and \\$k\\$ as input, and prints all \\$\left(m,k\right)\\$-distant primes (in language supported integer range).

---
Tags: code-golf, math, primes
---


title: Counting polydominoes

text:
# Question
Title: Counting polydominoes
## Background

A polyomino of size \\$n\\$ is a contiguous shape made from joining \\$n\\$ unit squares side by side. A domino is a size-2 polyomino.

A **polydomino** of size \\$2n\\$ is defined as a polyomino of size \\$2n\\$ which can be tiled with \\$n\\$ dominoes.

The following are some examples of polydominoes for \\$n=3\\$ (hexominoes).

```
. O O  |  . O . .  |  O O O .  |  O O O O O O
O O .  |  O O O O  |  O . O O  |
O O .  |  O . . .  |           |

```

The following are some hexominoes that are *not* polydominoes.

```
. O .  |  O . . .  |  O . O .
O O O  |  O O O O  |  O O O O
O O .  |  O . . .  |

```

## Challenge

Given a positive integer \\$n\\$, count the number of distinct polydominoes of size \\$2n\\$. Rotations and reflections are considered as the same shape. Different tilings of the same shape does not count either. You may take the value of \\$2n\\$ as input instead (you may assume the input is always even in this case).

The following shape has two ways to tile with dominoes, but it is counted only once just like other hexominoes.

```
. O O
O O .
O O .

```

The sequence is OEIS 056786.

## Test cases

The following are the expected results for \\$n=1 \cdots 9\\$.

```
1, 4, 23, 211, 2227, 25824, 310242, 3818983, 47752136

```

# Answer
# Ruby, ~~266 250~~ 242 bytes

```
->n,*z{j=(h=1,m=1i,-1,*r=[-m,0]).product h;(r.map{|c|j.map{|v,w|k=r+[v+=c,v+w];k|k==k&&(w=j.map{|y,q|(x=k.map{|v|y*[v,v.conj][q*q]}).map{|g|g-x.map(&:real).min-m*x.map(&:imag).min}.sort_by &:rect})-z==w&&z<<w[0]}};r,*z=z)until r[-n];z.size+1}

```

Try it online!

Not particularly original, I just recycled my solution to a similar problem, and changed some small details:

* start with the basic domino (instead of single tile)
* add 2 tiles on each step (instead of one)
* check for reflection by using the complex conjugate (instead of only rotation using powers of i)
* ~~stop when reaching size 2n (instead of n)~~ -\> Accept 2n as input

## How it works:

See the linked post for the full explanation. Basically, use complex numbers to make it easier.

## Performance:

43 seconds for n=5 (size 10) on TIO

Thanks Dingus for saving some bytes, the function is a mess and could probably be much shorter anyway if implemented properly.
> 5 votes

# Answer
# JavaScript (ES10), 343 bytes

Expects \\$2n\\$ as input.

```
n=>(c=0,g=(m,k)=>k<n?m.map((r,y)=>m.map((Y,x,[...m])=>(h=(p,R=m[Y=y+!p],P=p-~p<<x)=>(p?x:y)>n-2|(q=r|R)&P|k*!(q&P/2+P*2|(m[y-1]|m[Y+1])&P)?0:m[g(m,k+2,m[y]|=P,m[Y]|=P),m[y]=r,Y]=R)(0)|h(1))):(F=i=>i&&g[M=(m=m.map((r,y)=>m.map((v,x)=>a|=b|=(i&1?r>>n+~x:v>>y)%2<<x,b=0)|b,a=0)).flatMap(v=>v/(a&-a)||[])]|F(i-1))(8)?0:g[M]=++c)([...Array(n)],0)|c

```

Try it online!
> 3 votes

---
Tags: code-golf, combinatorics, tiling, polyomino, dominoes
---


title: Count the number of possible squares

text:
# Question
Title: Count the number of possible squares
In a 9 by 9 grid some points have been marked. The task is it to make a program that counts all distinct squares that can be made using four marked points. Note that squares can also be placed diagonally (any angle).

**Input** can be one of the following:

* A character string of length 81 containing two distinct characters for marked and unmarked points.
* A one dimensional array (length 81) containing two distinct values.
* A two dimensional array (9 by 9) with containing distinct values.

**Output**: The number of possible squares

You can write a full program or a function. This is code-golf. I am interested in the shortest code in every language. Standard loopholes are forbidden.

Examples:

```
Input:  ooo......oooooo...oooooo....oo.oo....oooooo...oooooo......ooo....................
Output: 62

Looks like:

o o o
o o o o o o
o o o o o o
  o o   o o
  o o o o o o
  o o o o o o
        o o o

Input:  ...ooo......ooo......ooo...ooo...oooooo.o.oooooo...ooo...ooo......ooo......ooo...
Output: 65

Input:  ...........o..o..o....................o..o..o....................o..o..o.........
Output: 6

Input:  ooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo
Output: 540

Input:  ...........o..o.......................o.....o....................o...o...........
Output: 0

```

# Answer
# Jelly, 18 bytes

```
ŒṪÆịœc4ṗ2ạ/€QLƲ€ċ3

```

Try it online!

Input is a two-dimensional list of `0` and `1` (or any other falsy and truthy value).

## Explanation

The idea is that for every four distinct points, we calculate the distance between each pair and if there are exactly three distinct distances (including 0), it's a square. (There are other shapes with this property, but they don't fit on a square grid; see @aPaulT's comment.)

```
ŒṪÆịœc4ṗ2ạ/€QLƲ€ċ3   Main monadic link
ŒṪ                   Get the coordinates of truthy points
  Æị                 Convert to complex numbers
    œc4              Get all combinations of size 4
               €     For each
              Ʋ      (
       ṗ2              Cartesian square
         ạ/            Absolute difference
           €             of each pair
            Q          Find unique items
             L         Length
              Ʋ      )
                ċ3   Count the occurences of 3

```
> 6 votes

# Answer
# JavaScript (ES6),  ~~122~~  109 bytes

*Saved 13 bytes thanks to @tsh!*

Expects a binary matrix.

```
f=(m,X,Y,t=0)=>m.map((r,y)=>r.map((v,x)=>t+=v*=1/Y?(m[X-x+Y]||0)[y-Y+X]&(m[y+X-x]||0)[x+y-Y]:~-f(m,x,y)/4))|t

```

Try it online!

---

# JavaScript (ES11), 103 bytes

*Also suggested by @tsh*

We can save 6 more bytes by using optional chaining.

```
f=(m,X,Y,t=0)=>m.map((r,y)=>r.map((v,x)=>t+=v*=1/Y?m[X-x+Y]?.[y-Y+X]&m[y+X-x]?.[x+y-Y]:~-f(m,x,y)/4))|t

```

Optional chaining is not supported on TIO.
> 6 votes

# Answer
# Charcoal, 72 bytes

```
Ｆ⁹⊞υＳυ≔±№ＫＡ1θＦ⁹Ｆ⌕Ａ§υι1Ｆ⁹Ｆ⌕Ａ§υλ1«Ｊ⁺κ⁻λι⁺ι⁻κμ¿ΣＫＫ«Ｊ⁺μ⁻λι⁺λ⁻κμ≧⁺ΣＫＫθ»»⎚Ｉ÷θ⁴

```

Try it online! Link is to verbose version of code. Takes input as an array of 9 strings of `1`s and neutral characaters. Explanation:

```
Ｆ⁹⊞υＳυ

```

Input the array and print it to the canvas.

```
≔±№ＫＡ1θ

```

Initialise the count to the negation of the number of `1`s on the canvas. This is because the algorithm below counts each `1` as a single `0×0` square, which we don't want.

```
Ｆ⁹Ｆ⌕Ａ§υι1

```

Loop over all of the `1`s in the array.

```
Ｆ⁹Ｆ⌕Ａ§υλ1«

```

Loop over all of the `1`s in the array again.

```
Ｊ⁺κ⁻λι⁺ι⁻κμ

```

Treat the two pairs of coordinates as two adjacent corners on a square, and jump to where the third corner would be.

```
¿ΣＫＫ«

```

If there is a `1` here, then...

```
Ｊ⁺μ⁻λι⁺λ⁻κμ

```

... jump to where the fourth corner would be, and...

```
≧⁺ΣＫＫθ

```

... if that's also a `1` then increment the count of squares found.

```
»»⎚Ｉ÷θ⁴

```

Since squares have four pairs of adjacent corners, divide the count by 4.
> 3 votes

# Answer
# Jelly (cairdcoinheringaahing's fork), 17 bytes

```
ŒṪœc4ṗ2ạ/ṢɱQLƲ€ċ3

```

A modification of my Jelly answer. Instead of calculating the Euclidean distances, it simply calculates the two differences of coordinates and then sorts them to make the uniquification order-insensitive.
> 2 votes

# Answer
# Python 3, 133 bytes

```
lambda g,r=range:sum(g[x][y]*g[x+a][y+b]*g[x+b][y-a]*g[x+a+b][y-a+b]for a in r(1,9)for b in r(9-a)for x in r(9-a-b)for y in r(a,9-b))

```

Try it online!

Expects a two dimensional array of booleans.

Shortend by 3 bytes thanks to xigoi.
> 2 votes

# Answer
# Ruby, ~~121 110~~ 99 bytes

```
->m{(0..80).sum{|x|(1..8-k=x%9).sum{|w|(0..k).count{|t|[0,w+9*t,9*w-t,t*8+w*10].all?{|z|m[x+z]}}}}}

```

Try it online!

Accepts a boolean array in input.
> 2 votes

# Answer
# Perl 5, 127 bytes

```
sub{0+map{$a=$_;map{$b=$_;map{//;grep{$_[$'][$_]&$_[$'+$a][$_+$b]&$_[$'+$b][$_-$a]&$_[$'+$a+$b][$_-$a+$b]}$a..8}0..8}0..8}1..8}

```

Try it online!

Expects a two dimensional array containing values 0 or 1.
> 0 votes

# Answer
# MATLAB, 168 Bytes

```
function o=q(I)
o=0;for i=2:9
for j=0:9-i
for k=0:9-i
a=I((1:i)+j,(1:i)+k);a(2:i-1,2:i-1)=0;o=o+floor(sum(a&rot90(a,2)&rot90(a,1)&rot90(a,3),'all')/4);end
end
end

```

A different approach. Takes a 9x9 array of 1s and 0s. Loop through every square submatrix from size 2 to 9, and rotate that submatrix three times and take the boolean combination of all 4 (original + 3 rotations). The sum of all truthy values on the edges divided by 4 rounded down is the number of squares that are in that submatrix. By looking only at the edges, you avoid capturing smaller submatrices in the middle (e.g. 2x2 in the middle of a 4x4). This method captures all squares by using the rotational symmetry of a square. It may not be the golfiest, but it was fun
> 0 votes

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


title: Liars and Guessers

text:
# Question
Title: Liars and Guessers
Github

You have probably played, and may even have written a program to play, a simple number guessing game. If so, this probably looks familiar:

```
Try to guess my number (1 to 100)!
Please enter a guess: 50
Too small, guess again!
Please enter a guess: 75
Too big, guess again!
Please enter a guess: 63
Correct!

```

(Obviously, it usually takes a little longer.)

But what if your opponent *lied*? Or, to be more generous, isn't very good at comparing numbers.

There are two parts to this challenge.

## 1: The liar

* Your program will be passed a number between 0 and 255 inclusive.
* Your program will be passed a guess, within the same bounds.
* Your program should return one of -1 (the guess is smaller than your number), 0 (the guess *is* your number) or 1 (the guess is greater than your number).
* You may store state for the duration of a single game.
* You may return an inaccurate result (lie!) up to 8 times in a game.
* If you return 0 when the guess is not equal to your number, your opponent will win anyway. However, you may chose not to return 0 even when the guess *is* equal to your number (this counts as one of your allotted lies).
* Your aim is to delay returning 0 for as long as possible ("long" as in most calls to the program, not length of time, obviously).

## 2: The guesser

* Your program will be passed a function to call. You should pass this function a guess, between 0 and 255. It will return -1 (indicating that you should guess lower), 0 (indicating that your guess was correct) or 1 (indicating that you should guess higher).
* The function may return an inaccurate result up to 8 times in a single invocation of your program.
* Your aim is to receive output of 0 from the function after calling it the fewest possible times.

## General notes

* Once the liar has used up their allotted lies, the function passed to the guesser (henceforth "guess function") will simply begin returning the correct answer without invoking the liar.
* The maximum number of guesses is 2304 (equivalent to trying every possible number 9 times). After this, the guess function will return 0 and end the game.
* Practically, the guess function will never return 0, it will just end the game. So the guesser only needs to handle a return of -1 or 1.
* The best guesser is the one that takes the fewest guesses to end the game. The best liar is the one that delays the end of the game for the greatest number of guesses.

## Submissions

All submissions must be written in Python 3. Answers should use the following template:

```
# <type>: <name>

<code>

<description>

```

Where `<type>` is either `Liar` or `Guesser`. Every submission should define a callable called `Main` (this may be a class or function).

For the liar, it should accept two parameters: an instance of `random.Random`, to generate any non-determinism needed, and an `int`, which is the secret to protect. It should return another callable, which accepts a guess (as an `int`) and returns `-1`, `0` or `1` (it is never advantageous to return `0`). The recommended way of implementing this is as a class, for example:

```
class Main:
    """Liar that always returns one."""

    def __init__(self, rng: random.Random, secret: int):
        """Store the rng and secret even though we do nothing with them."""
        self.rng = rng
        self.secret = secret

    def __call__(self, guess: int) -> int:
        """Return 1."""
        return 1

```

For the guesser, `Main` should also accept to arguments: an instance of `random.Random`, as above, and a callable (the guess function). For example:

```
def Main(rng: random.Random, liar: Callable[[int], int]):
    """Guess randomly."""
    while True:
        liar(rng.randrange(256))

```

Note that the function never needs to exit, this will be handled by the game runner.

## Latest Results

```
10 repetitions with seed XHMS2Z:

Top liars:
-------------------------------------
tsh_equal_lie                     499
mojo_black_one_big_lie            497
mojo_black_keep_away              486
qwatry_illusionist                485
sheik_yerbouti_the_liar_king      353
citty_mislead                     346
spitemaster_look_over_there       341
leo_knave                          99

Top guessers:
-------------------------------------
user1502040_bayes_bot              26
mojo_black_phoenoix_wright         29
l4m2_fib_trust                     30
tsh_most_correct_guess             30
att_top_median                     32
sheik_yerbouti_no_matter_what      61
tsh_most_recent_guess              65
citty_pester                       67
m_virts_binary_reset_gaussian    1528
m_virts_binary_reset             2015

Slowest submissions:
-------------------------------------
m_virts_binary_reset_gaussian    0.0063s
m_virts_binary_reset             0.0049s
user1502040_bayes_bot            0.0028s
l4m2_fib_trust                   0.0021s
tsh_most_recent_guess            0.0013s
att_top_median                   0.00089s
tsh_most_correct_guess           0.00073s
mojo_black_keep_away             0.00052s
qwatry_illusionist               0.00042s
mojo_black_one_big_lie           0.00042s
tsh_equal_lie                    0.00037s
citty_pester                     0.00018s
citty_mislead                    0.00016s
sheik_yerbouti_no_matter_what    0.00016s
spitemaster_look_over_there      0.00015s
sheik_yerbouti_the_liar_king     0.00013s
mojo_black_phoenoix_wright       0.0001s
leo_knave                        7.5e-06s

0 submissions were disqualified.

```

Congrats to tsh and user1502040 for topping the leaderboards!

# Answer
# Guesser: phoenix\_wright

```
import random
from typing import Callable

def Main(rng: random.Random, liar: Callable[[int], int]):
    while liar(0) == -1: pass
    previous = {0:1}
    lb = 0
    ub = 255
    while True:
        while lb <= ub:
            g = (lb+ub)//2
            if g in previous:
                r = previous[g]
            else:
                r = liar(g)
            if r == 1:
                lb = g+1
            elif r == -1:
                ub = g-1
            previous[g] = r
        k = g == ub
        n = 0
        while True:
            n += 1
            g = min(max(ub+k,0),255)
            k = 1-k
            r = liar(g)
            if previous[g] != r:
                previous[g] = r
                break
        lb = 0
        ub = 255

```

My idea was to cross-examine the liar witness (do a binary search), and when it finds a contradiction, press it (specifically, if it finds a -1 right next to a 1, it repeatedly guesses between the two). If that didn't solve the case, then we get a new testimony (reset the binary search bounds). The idea is to quickly cause the liar to run out of lies. It also has other optimizations. It keeps track of previous responses, so when it resets after the contradiction goes away, it doesn't actually have to use guesses to get back to where it was before. It also begins by checking that the liar isn't lying at the very beginning.
> 7 votes

# Answer
# Liar, equal\_lie

```
"""A liar that only lies when equal."""
import random

class Main:

    def __init__(self, rng: random.Random, secret: int):
        """Store the rng and secret."""
        self.rng = rng
        self.secret = secret

    def __call__(self, guess: int) -> int:
        """Work out the correct response. mostly."""
        if guess == self.secret:
            if guess % 2:
                return -1
            return 1
        if guess < self.secret:
            return 1
        return -1

```

I have no idea why this works.
> 6 votes

# Answer
# Guesser: top\_median

```
import random
from typing import Callable

def Main(rng: random.Random, liar: Callable[[int], int]):
    poss=[0]*256
    while True:
        height = max(poss)
        top = [i for i in range(256) if poss[i]==height]
        guess = top[len(top)//2]

        i = liar(guess)
        for j in [range(guess+1), range(guess,256)][i<0]:
            poss[j] -= 1

```
> 4 votes

# Answer
# Guesser, most\_recent\_guess

```
"""A guesser that based on recent guesses."""
import random
from typing import Callable

def Main(rng: random.Random, liar: Callable[[int], int]):
    scores, current = [0] * 256, 0
    while True:
        max_score = max(scores)
        values = [val for val, score in enumerate(scores) if score == max_score]
        guess = values[len(values) // 2]
        result = liar(guess)
        current -= 1
        if result > 0:
            scores[:guess + 1] = [current] * (guess + 1)
        else:
            scores[guess:] = [current] * (256 - guess)

```

Basic idea: The more recent response would be more trustable.
> 3 votes

# Answer
# Liar: theLiarKing

```
import random, math

class Main:

    def __init__(self, rng: random.Random, secret: int):
        self.rng = rng
        self.secret = secret

    def __call__(self, guess: int) -> int:
        timeToLie = self.rng.randint(1,16)
        if guess == self.secret:
            res = self.rng.choice([-1,1])
        elif timeToLie == 1:
            if self.secret > guess:
                res = -1
            else:
                res = 1
        elif self.secret > guess:
            res = 1
        else:
            res = -1
        return res

```

This liar has a 6.25% chance to lie in each turn, and also lies every time the guesser guesses the right number.

I chose 6.25% (1/16) because in this way, on average, it lies againist my guesser one time because the guess was right and one time just because it wanted to lie.

Check my guesser answer
> 2 votes

# Answer
# Guesser, most\_correct\_guess

```
"""A guesser that based number of correct times."""
import random
from typing import Callable

def Main(rng: random.Random, liar: Callable[[int], int]):
    scores = [1] * 256
    while True:
        index, mid_score = 0, sum(scores) >> 1
        while mid_score > 0:
            mid_score, index = mid_score - scores[index], index + 1
        guess = max(0, index - 1)
        result = liar(guess)
        for index in (range(guess + 1, 256) if result > 0 else range(guess)):
            scores[index] <<= 1

```

Basic idea: We just consider all response from liar with same possibility of lying. There for, an answer may be correct if more responses support it. I still have no idea why `1 <<`  is added there. It just works better than infinity weight (use max instead) and 0 weight (only use sum).
> 2 votes

# Answer
# Guesser, BinaryReset

```

import random
from typing import Callable

def Main(rng: random.Random, liar: Callable[[int], int]):
    """Guess deterministically."""
    ub=255
    lb=0
    while True:
        g=(ub-lb)//2+lb
        r=liar(g)
        if r==-1:
            lb=g
        elif r==1:
            ub=g
        if lb>=ub:
            ub=255
            lb=0

```

Untested, for now ill just hope it works.

# Guesser, BinaryResetGaussian

```

import random
from typing import Callable

def Main(rng: random.Random, liar: Callable[[int], int]):
    """Guess less deterministically."""
    ub=255
    lb=0
    while True:
        g=max(0,min(255,int(rng.gauss((ub+lb)//2,(ub-lb)/6))))
        r=liar(g)
        if r==-1:
            lb=g+1
        elif r==1:
            ub=g-1
        if lb>=ub:
            ub=255
            lb=0

```

Instead of fixing my binary search, why not just add randomness?
> 2 votes

# Answer
# Guesser: FibTrust

```
#def Main(rng: random.Random, liar: Callable[[int], int]):
def Main(rng, liar):
    times=[8]*256
    weight=[1,2,3,5,8,13,21,34,55]
    while 1:
        a=[i>=0 and weight[i] for i in times]
        b=(sum(a)+1)/2
        guess=-1
        #print(times)
        while b>0:
            guess=guess+1
            b=b-a[guess]
        cmp=liar(guess)
        times=[times[i]-(i==guess or (cmp<0)^(i<guess)) for i in range(256)]

```

Try it online!
> 2 votes

# Answer
# Liar: Knave

```
import random

class Main:
    """A **real** liar"""

    def __init__(self, rng: random.Random, secret: int):
        """Store the rng and secret."""
        self.rng = rng
        self.secret = secret

    def __call__(self, guess: int) -> int:
        """You can trust me, really"""
        if guess > self.secret:
            return 1
        return -1

```

I think this challenge needs more Liar submissions. Here's a very straightforward one, lying as much as it can. As simple as it is, it can really throw off some guessers.

---

Extra: here's a TIO link to test submissions online that I put together by ~~vandalizing~~ modifying Artemis' code from Github. Feel free to use it to test your future submissions (add your submission to the header, with a unique name instead of "main", and remember to append it to either the `guessers` or `liars` list).

This liar turned out to be not exactly great, my consolation is that at least it managed to mess with the top positions of the guessers board ^^"
> 2 votes

# Answer
# Liar: keep\_away

```
"""A liar that tries to keep the guesser away from the secret"""
import random

class Main:
    def __init__(self, rng: random.Random, secret: int):
        """Store the rng and secret."""
        self.rng = rng
        self.secret = secret
        self.lb = 0
        self.ub = 255
        self.lies = 4
    def __call__(self,guess):
        r = (guess <= self.secret) - (guess > self.secret)
        a = (self.lb+self.secret)//2
        b = (self.ub+self.secret)//2
        if self.lies:
            if a <= guess < self.secret:
                self.lies -= 1
                self.lb = guess
                r = -r
            elif self.secret < guess <= b:
                self.lies -= 1
                self.ub = guess
                r = -r
        return r

```

Similar to my other liar, this tries to waste time, but instead it keeps track of how close the guesser has gotten, and lies when it gets too close (the threshold for too close gets smaller each time).
> 2 votes

# Answer
# Guesser: BayesBot

```
import random
from typing import Callable

def Main(rng: random.Random, liar: Callable[[int], int]):
    num_possibilities = 256
    max_lies = 8

    distribution = {(secret, max_lies) : 1. / num_possibilities for secret in range(num_possibilities)}

    lie_rates = [
        0, 0.211, 0.195,
        0.188, 0.138, 0.207,
        0.202, 0.140, 0.228,
    ]

    while True:
        secret_distribution = [0] * num_possibilities
        for (secrets, _), p in distribution.items():
            secret_distribution[secrets] += p
        q = 0.5
        for guess, p in enumerate(secret_distribution):
            q -= p
            if q < 0:
                break

        result = liar(guess)

        next_distribution = {}
        for (secret, lies), p in distribution.items():
            if secret == guess:
                lie = True
                cond_p_result = 0.55 if secret % 2 else 0.83
                if result == -1:
                    cond_p_result = 1 - cond_p_result
            else:
                lie = (result == 1) != (guess < secret)
                cond_p_result = lie_rates[lies] if lie else 1 - lie_rates[lies]
            if lies == 0 and lie:
                continue
            next_p = p * cond_p_result
            if lie:
                next_distribution[(secret, lies - 1)] = next_p
            else:
                next_distribution[(secret, lies)] = next_p

        c = 1. / sum(next_distribution.values())
        distribution = {k : c * p for k, p in next_distribution.items()}

```

Uses a statistical model to estimate the probability that each number is the secret, then always guesses the median of this distribution. Sort of like a fuzzy binary search.
> 2 votes

# Answer
# Guesser: noMatterWhat

```
import random
from typing import Callable

def Main(rng: random.Random, liar: Callable[[int], int]):
    i = 0

    while i < 9:
        low = j = 0
        high = 255

        while j < 8:
            guess = (low + high) // 2
            res = liar( guess )
            if res > 0:
                low = guess + 1
            else:
                high = guess - 1
            j += 1

        i += 1

```

The code implements a binary search to look for the secret value.
A binary search over 256 values is granted to find the key in 8 steps.
But since the liar can lie 8 times, a single binary search is not enough, we need at most 9 of them.

So this guesser is granted to end the game in at most 8 * 9 = 72 turns, no matter what's the strategy implemented by the liar.

Special thanks go to Artemis, who had the patience to explain me how to run the game, so that I could debug my answers.

Check my liar answer
> 1 votes

# Answer
# Liar: LookOverThere

```
class Main:
    """Liar that picks a number 64 off from the actual target and pretends that's the correct answer."""

    def __init__(self, rng, secret: int):
        """Pick a new secret."""
        self.secret = secret + 63.5 if secret < 128 else secret - 63.5

    def __call__(self, guess: int) -> int:
        """Return the 'correct' answer."""
        if guess < self.secret:
            return 1
        elif guess > self.secret:
            return -1
        # Should never happen
        return 0

```

Maximizing time spent lying is probably the way to go. So we want to give the correct answer most of the time, lying only when necessary. I may adjust the difference after testing (down to 32 off or 16 off the correct answer).
> 1 votes

# Answer
# Guesser: Pester

```
import random
from typing import Callable

def guess_lies(liar, guess, lies):
    tries = [liar(guess) for _ in range(9-lies)]
    return tries[-1], lies + min((tries.count(-1),tries.count(1)))

def Main(rng: random.Random, liar: Callable[[int], int]):
    while True:
        low = 0
        high = 255
        lies = 0
        for j in range(8):
            guess = (low + high) // 2
            res,lies = guess_lies(liar, guess, lies)
            if res > 0:
                low = guess + 1
            else:
                high = guess - 1

```

Repeatedly guesses the possible amount of times that the liar could lie at any instance + 1, and assumes the last answer is correct. This is only slightly worse than just doing 9 binary searches.
> 1 votes

# Answer
## Liar: Mislead

```
from collections import defaultdict
import random

class Main:
    """Liar that tries to foil binary searchers and repeat guesses"""

    def __init__(self, rng: random.Random, secret: int):
        self.rng = rng
        self.secret = secret
        self.lies = 0
        self.low = 0
        self.high = 255
        self.prev_guess = defaultdict(int)

    def __call__(self, guess: int) -> int:
        """Return 1"""
        if self.prev_guess[guess] > 0:
            if guess != self.secret:
                if self.rng.randint(0,self.prev_guess[guess]-1) == 0:
                    self.lies += 1
                    answer = -1 if guess > self.secret else 1
                else:
                    answer = 1 if guess > self.secret else -1

        if guess == self.secret:
            self.lies += 1
            return self.rng.choice((-1, 1))

        self.prev_guess[guess] += 1

        if not (self.low <= guess <= self.high):
            self.low = 0
            self.high = 255
            self.prev_guess = defaultdict(int)

        if self.low <= self.secret <= self.high:
            if self.rng.randint(1,self.lies+1) == 1:
                self.lies += 1
                if not (guess <= self.secret <= self.high):
                    self.low = guess + 1
                    return 1
                else:
                    self.high = guess - 1
                    return -1

        answer = -1 if self.secret < guess else 1
        if answer < 0:
            self.low = guess + 1
        else:
            self.high = guess - 1
        return answer

```

Tries to break binary searchers and doesn't seem to do a great job at it, also lies to people who ask the same guess multiple times. Isn't great but at least it beats LookOverThere?
> 1 votes

# Answer
# Liar: one\_big\_lie

```
"""A liar that lies once at the very beginning"""
import random

class Main:
    def __init__(self, rng: random.Random, secret: int):
        """Store the rng and secret."""
        self.rng = rng
        self.secret = secret
        self.lied = False
    def __call__(self,guess):
        r = (guess <= self.secret) - (guess > self.secret)
        if not self.lied:
            self.lied = True
            r = -r
        return r

```

The idea is that lying on the very first turn would waste a lot of time for the guesser while using a minimal number of lies.
> 1 votes

# Answer
# Liar: Illusionist

```
import random
class Main:
    def __init__(self, rng: random.Random, secret: int):
        self.rng = rng
        self.secret = secret
        self.fake_secret = (127-secret)%256
        self.unreserved_lies = 4
        self.prev_lies = []
    def __call__(self, guess: int) -> int:
        if guess < self.secret:
            secret_direction = 1
        elif guess > self.secret:
            secret_direction = -1
        else:
            secret_direction = 0
        if self.unreserved_lies and guess not in self.prev_lies:
            if guess < self.fake_secret:
                if secret_direction != 1:
                    self.prev_lies.append(guess)
                    self.unreserved_lies -= 1
                return 1
            if secret_direction != -1:
                self.prev_lies.append(guess)
                self.unreserved_lies -= 1
            return -1
        elif secret_direction != 0:
            return secret_direction
        return -1

```

The liar picks an illusory number to lead the guesser towards. However, if the guesser double checks the liar's answer, it will tell the truth in order to avoid wasting lies. The liar reserves 4 lies for when the guesser chooses a number equal to the real `secret`.
> 1 votes

---
Tags: number, game, king-of-the-hill, python, asymmetric
---


title: Tips for golfing in Befunge

text:
# Question
Title: Tips for golfing in Befunge
What general tips do you have for golfing in Befunge? I'm looking for ideas that can be applied to code golf problems in general that are at least somewhat specific to Befunge (e.g. "remove comments" is not an answer). Please post one tip per answer.

# Answer
When using a multi-line loop, try to use as much of it as possible:

```
>1234....v
^        <

```

vs

```
>1234v
^....<

```
> 9 votes

# Answer
Need to drop a value after a conditional (e.g. because the other path depends on the value, but this one doesn't)? Instead of using `>$` or `$<`, take advatage of the fact that you know the truth value of the variable and use `_` instead to both change direction and pop stack.

### Example

```
'* : v           >$ .. @          Prints number in binary followed by the original
                                  decimal number.
     > :2%\2/ :!#^_ \.

```

gets turned into

```
'* : v           _  .. @          Since we know that the topmost value on the stack
                                  will be 0, we combine `>$` into `_`.
     > :2%\2/ :!#^_ \.

```
> 9 votes

# Answer
Don't forget that `0` is always on the stack. For example, this means that, with an empty stack, `g` is equivalent to `00g` and `p` is equivalent to `000p`.
> 8 votes

# Answer
If you need to push a number larger than 15, use `'` to fetch the ASCII value of the next character:

```
'*

```

to push 42 rather than:

```
4a*2+

```
> 7 votes

# Answer
Instead of using `|`, requiring another line (often with many extra spaces), try using `j`. For example:

```
01-`j@more code here

```

would stop if the number on top of the stack was negative and continue onward otherwise. If you need multiple characters, use `n*j` where `n` is the number of characters you need when the value passed to `j` is `0`. Example:

```
01-`4*j01-*more code

```

which would negate a negative number.
> 5 votes

# Answer
In Befunge-93, if the first thing you're pushing onto the stack is a string, you can often get away with dropping the opening quote. For example this:

```
"!iH",,,@

```

could be simplified to this:

```
!iH",,,@

```

Try it online!

What's happening is the interpreter first tries to execute the characters in the unquoted string. The `!` performs a harmless *not*, and the `i` and `H` are not valid instructions, so they're ignored (although on some implementations you may get a warning).

When the `"` is encountered, that is considered the start of the string, but because there is no closing quote, it wraps all the way around the playfield until the `"` is encountered a second time. What ends up pushed onto the stack is then this:

```
,,,@  ···72 spaces···  !iH

```

Since we only care about the last few characters, though, none of that other stuff matters. So after the quote, we then finally get to execute the three `,` commands, writing out the message, and the `@` command, which exits.

Note that this won't typically work in Befunge-98, since an unrecognised instruction will cause the interpreter to reflect instead of ignoring it.
> 5 votes

# Answer
In Befunge-93, the character input command (`~`) can often be used as a shortcut for -1, since that is the value it returns on EOF.

As an example, the code below will output -1:

```
~.@

```

Try it online!

This is not recommended in production code, since when run in an interactive environment, the program would pause and wait for user input. And obviously if the user were to input something, the result would no longer be -1.

That said, the rule on PPCG is that a program may assume an empty input stream, and that's how it would typically be run on TIO.

Also note that you aren't necessarily precluded from using this trick just because your program needs to read something from the input stream. You just have to make sure you process your inputs up front, after which all future uses of `~` should return -1.
> 5 votes

# Answer
In Befunge-93, it can often be advantageous to flatten a loop into a single line, with the loop section of code being executed in both directions.

For example, consider the code below, which outputs the letter `a` eight times:

```
"a"9>1-:#v_@
    ^\,:\<

```

This can flatten be flattened into a single line by interspersing the loop sequence with bridge instructions (`#`):

```
"a"9>1#\-#,:#:>#\_@

```

Try it online!

If you're just looking at the non-whitespace characters, you may get the impression that this is longer than the the original. But once you take into account the linefeed and the additional padding required in the two line version, you actually end up saving four bytes.

In this particular case, the code be compressed even further by noting that that sequence `:#:` can simply be replaced with `:`.

```
"a"9>1#\-#,:>#\_@

```

Try it online!

In fact, any time you have the same instruction repeated on either side of a `#` command, you can simplify that to just the one instruction, so this is something you should always be looking out for when flattening a loop.

To understand how this works, it can help to write out the loop sequence twice, once with all the characters following the `#` removed (i.e. what happens when executing left to right), and once with the characters preceding the `#` removed (i.e. executing right to left).

```
"a"9>1#\-#,:>#\_@
    >1  -  :>  _      ; executing left to right
    >  \  ,:  \_      ; executing right to left

```

You can clearly see now how this matches the original two line version of the code.
> 4 votes

# Answer
Use the direction of the IP when dealing with `_` or `|`, rather than using an extra character for `!`.

Real example (from this post):

```
#v~
,>:!#@_

```

Can be changed to

```
#v~
:<,_@#

```
> 3 votes

# Answer
Don't forget that `0k` does not execute the next instruction. This means that instead of doing:

```
;some boolean test;!jv;code if false;
       ;code if true;<

```

You can save a character by doing

```
;some boolean test;kv;code if false;
      ;code if true;<

```
> 3 votes

# Answer
Output by exit code, where this is an allowed output form. If the challenge asks you to print one number, you can save a byte by ending the program with `q` instead of `.@`
> 3 votes

# Answer
Don't forget about the `k` operator. Instead of `"!dlroW olleH",,,,,,,,,,,,@`, do `"!dlroW olleH"bk,@`. Note that `k` does the operation *on the cell that it is at* so `9k,` would print not 9 times but 10; 9 times with the `k`, and once with `,`.
> 2 votes

# Answer
When pushing small numbers onto the stack, you can probably figure out easily enough that `45*` will get you `20`, and `67*` will get you `42`. When it comes to larger numbers, though, you really need a program that can calculate the most efficient representation for you.

The easiest option for this is Mike Schwörer's online interface for BefunRep. You simply type in a number and it'll spit out an equivalent Befunge representation. It's not always the most optimal, but it's close enough, and it's almost certain to be better than anything you could come up with by hand.

The online system is limited to numbers in the range 0 to 16777215, so if you need anything larger than that, you'll want to download the standalone BefunRep utility and run the calculations yourself.

If you're programming in Befunge-98, another option to consider is Fungify. In general it isn't nearly as optimal as BefunRep, but for some of the lower numbers, where hex digits and single quote characters are most effective, it can sometimes produce better results.
> 1 votes

# Answer
## Merge branches as soon as possible

If two or more code branches are merging together and they all end with the same sequence of instructions, you can merge them immediately before the instructions they have in common. This is a fairly common circumstance to be on the lookout for.

As an example, I have this subprogram for reading input onto the playing field from my self-interpreter:

Notice that three different branches are coming together at the marked cell, each of which wants to write to the playing field. The one on the top right is `520p` to put 5 at (2,0). The top left is `00p` to put the computed value at (0,0). And on the right (and below) is `20p` to put the computed value at (2,0). Since all of these instructions end with `0p`, I save at least 4 bytes by merging the branches first and then doing `0p` afterwards.
> 1 votes

# Answer
# Use String Mode to Allow the IP to Pass Through Other Code

If you need the IP to get from here to there and there's a bunch of existing and unmovable code in the way in every direction, just push a 0, go into string mode, pass through the code, come out of string mode, and pop all the garbage before continuing. This trick employed in Wim Rijnder's Wumpus here:

(Yes, it would have been more efficient to put the quotes closer to the actual code there, but this is golf--we don't care about speed!)

This trick requires you to be able to spare at most 2 cells on this side and at least 3 on the other side, but it might end up saving space in the long run if writing yourself into a corner that requires this trick ends up greatly compressing the rest of the program. (In particular it could save you from having to write in a low-code-density "lane" for the IP to travel down.)
> 1 votes

---
Tags: code-golf, tips, befunge
---