title: Pretty print a grid of polyominoes

text:
# Question
Title: Pretty print a grid of polyominoes
Write a function that accepts a rectangular grid of ids in any reasonable format, for example a multi-line string:

```
IIILOO
ILLLOO

```

and a string or list of box drawing charcters such as:

```
' ═║╔╗╚╝╠╣╦╩╬'

```

or

```
[0x20, 0x2550, 0x2551, 0x2554, 0x2557, 0x255a, 0x255d, 0x2560, 0x2563, 0x2566, 0x2569, 0x256c']

```

(see below for more details) and returns a pretty printed version, as such:

```
╔═══════════╦═══╦═══════╗
║           ║   ║       ║
║   ╔═══════╝   ║       ║
║   ║           ║       ║
╚═══╩═══════════╩═══════╝

```

i.e. a rectangle made out of the box drawing characters, where each border indicates the border of each polyomino.

```
╔═══════════╦═══╦═══════╗
║ I   I   I ║ L ║ O   O ║
║   ╔═══════╝   ║       ║
║ I ║ L   L   L ║ O   O ║
╚═══╩═══════════╩═══════╝

```

# Rules

Shortest submission in bytes per language wins. Standard rules apply.

Note that to leave room for annotations and as the characters used are half width each unit square is 2x4 (3x5 but boundary fields are shared with neighbouring squares) characters in the output.

You may assume that input is clean rectangular and ids are unique to orthogonally connected regions.

To avoid any unicode related issues I have decided to provide the box drawing characters as an input. This may be any flat container holding the characters in any order as long as it contains

1. each character exactly once and
2. only these characters (no fillers)
3. access is sequential or per index only (no sophisticated lookup tables)

# More examples:

In:

```
XXXSS
RXSSL
ROOOL
RROLL

' ═║╔╗╚╝╠╣╦╩╬'

```

Out:

```
╔═══════════╦═══════╗
║           ║       ║
╠═══╗   ╔═══╝   ╔═══╣
║   ║   ║       ║   ║
║   ╠═══╩═══════╣   ║
║   ║           ║   ║
║   ╚═══╗   ╔═══╝   ║
║       ║   ║       ║
╚═══════╩═══╩═══════╝

```

In:

```
1220003
2240503
2444666

' ═║╔╗╚╝╠╣╦╩╬'

```

Out:

```
╔═══╦═══════╦═══════════╦═══╗
║   ║       ║           ║   ║
╠═══╝   ╔═══╣   ╔═══╗   ║   ║
║       ║   ║   ║   ║   ║   ║
║   ╔═══╝   ╚═══╬═══╩═══╩═══╣
║   ║           ║           ║
╚═══╩═══════════╩═══════════╝

```

# Answer
> 9 votes
# Charcoal, ~~147~~ ~~129~~ ~~80~~ ~~78~~ ~~76~~ ~~75~~ ~~71~~ 65 bytes

```
≔⁺ＳψθＷＳＦ²⊞υ⁺⭆ι×⁴λψ⊞υ⭆⌊υψＥυ⭆ＥιＥ⁴§§υ⁻κ÷ν²⁻μ∨⁼ν¹⁼ν²§θ﹪×⁷↨²Ｅλ⁼ν§λ⊕ξ⁹⁵

```

Try it online! Link is to verbose version of code. Expects the box-drawing characters first in the order `╬╦╠╔╩═╚╣╗║ ╝` followed by the newline-terminated grid of strings. Edit: Saved 6 bytes by stealing @Arnauld's cool mapping. Explanation:

```
≔⁺Ｓψθ

```

Append a null byte to the box drawing character string as this gives us a free modulo 13 due to Charcoal's cyclic indexing.

```
ＷＳＦ²⊞υ⁺⭆ι×⁴λψ⊞υ⭆⌊υψ

```

Read in the grid, duplicating it vertically and quadruplicating it horizontally, plus suffix a row and column of null bytes of padding.

```
Ｅυ⭆ＥιＥ⁴§§υ⁻κ÷ν²⁻μ∨⁼ν¹⁼ν²§θ﹪×⁷↨²Ｅλ⁼ν§λ⊕ξ⁹⁵

```

Map over the expanded grid, collecting a `2×2` square for each character, then comparing the characters in that square pairwise, treating the comparison results as base 2, and hashing into the box-drawing characters.

Previous 129 byte canvas-based version:

```
≔⁺ＳψθＷＳ⊞υιυＵＥ¹¦¹Ｆ⊕⊗ＬυＦ⊕⊗Ｌη«Ｊ⊖κ⊖ι≔ＫＭζ¿﹪ⅉ²¿﹪ⅈ²§θ﹪×⁷↨²Ｅ⁴⁼§ζ⊗λ§ζ⊗⊕λ⁹⁵Ｆ¬⁼§ζ¹§ζ⁵§θ⁵¿﹪ⅈ²Ｆ¬⁼§ζ³§ζ⁷§θ⁹»ＵＭＫＡ⎇№θιιψＵＥ¹Ｆ⊕ＬυＦ⊗Ｌη«Ｊ⊖⊗κ⊖⊗ι§ＫＶ⊕⊗κ

```

Try it online! Link is to verbose version of code. Expects the box-drawing characters first in the order `╬╩╣╝╦═╗╠╚║ ╔` followed by the newline-terminated grid of strings. Explanation:

```
≔⁺Ｓψθ

```

Append a null byte to the box drawing character string as this gives us a free modulo 13 due to Charcoal's cyclic indexing.

```
ＷＳ⊞υιυ

```

Read and print the grid.

```
ＵＥ¹¦¹

```

Double-space the grid horizontally and vertically.

```
Ｆ⊕⊗ＬυＦ⊕⊗Ｌη«Ｊ⊖κ⊖ι

```

Loop through each cell of the extended grid, including the border.

```
≔ＫＭζ

```

Get the contents of the adjacent cells.

```
¿﹪ⅉ²¿﹪ⅈ²§θ﹪×⁷↨²Ｅ⁴⁼§ζ⊗λ§ζ⊗⊕λ⁹⁵

```

If this is a cell e.g. between 4 ids then calculate which box-drawing character to draw.

```
Ｆ¬⁼§ζ¹§ζ⁵§θ⁵

```

If this is a row divider and the two ids differ then print a .

```
¿﹪ⅈ²Ｆ¬⁼§ζ³§ζ⁷§θ⁹

```

If this is a column divider and the ids differ then print a .

```
»ＵＭＫＡ⎇№θιιψ

```

Delete all non-box-drawing characters.

```
ＵＥ¹

```

Double-space the grid horizontally.

```
Ｆ⊕ＬυＦ⊗Ｌη«Ｊ⊖⊗κ⊖⊗ι§ＫＶ⊕⊗κ

```

Duplicate the row dividers.

# Answer
> 7 votes
# JavaScript (ES6),  ~~164 154~~  143 bytes

Expects `(a)('╬╩╠╚╣╝║╦═╔ ╗')`, where `a` is a list of strings.

```
a=>c=>[...a,...a,a[0]].map((r,y)=>[...r+r+r+r+0].map((v,x)=>c[g=d=>v==(v=(a[y-d%2>>1]||0)[x-~x-d>>3]),(g``,8*g(1)|g(3)|4*g(2)|2*g``)*7%95%13]))

```

Try it online!

### How?

Given a matrix \\$M\\$ of size \\$w\times h\\$, we build an expanded matrix \\$M'\\$ of width \\$4w+1\\$ and height \\$2h+1\\$ filled with the original values of \\$M\\$ magnified 4 times in width and twice in height. The extra column and extra row are filled with undefined values.

For instance:

```
AB  ==> AAAABBBB?
CD      AAAABBBB?
        CCCCDDDD?
        CCCCDDDD?
        ?????????

```

For each cell \\$(x,y)\\$ in \\$M'\\$, we extract \\${M'}\_{x,y}\\$ and 3 adjacent cells:

$$\begin{pmatrix}v\_3={M'}\_{x-1,y-1}&v\_1={M'}\_{x,y-1}\\ v\_2={M'}\_{x-1,y}&v\_0={M'}\_{x,y}\end{pmatrix}$$

Using these results, we build a 4-bit value as follows:

```
8 4 2 1
| | | |
| | | +--> set if v3 = v1
| | +----> set if v2 = v0
| +------> set if v3 = v2
+--------> set if v1 = v0

```

We may get all values from \\$0\\$ to \\$15\\$ except the ones with exactly 3 bits set: \\$7\\$, \\$11\\$, \\$13\\$ and \\$14\\$ (because if 3 equalities are satisfied, the 4th one must be satisfied as well).

The 12 remaining values can be directly mapped to the output characters. We use the expression \\$((n\times7)\bmod 95)\bmod 13\\$ to force all them into \\$\[0\dots 11\]\\$ (Try it online!).

# Answer
> 7 votes
# PowerShell, ~~282~~ ~~243~~ 219 bytes

Thanks @Arnauld for the idea that the values can be directly mapped to the output characters! I've made a code that finds such an expression by brute force. The `*7%95%13` is single shortest expression.

-24 bytes thanks @Arnauld for "width 4w+1 and height 2h+1" before sliding over the input string.

```
param($t,$s)$n=($s=$s-replace'.',('$0'*4)|%{$_;$_})|% Le*|Sort -b 1
$s=$s+,''|% *ht($n+1)
$s|%{-join(0..$n|%{$x=$_,--$_
$b,$a,$d,$c=$s[--$y,++$y]|%{$_[$x]}
$t[(!($a-$b)+2*!($a-$c)+4*!($b-$d)+8*!($c-$d))*7%95%13]});$y++}

```

Try it online!

Less golfed:

```
param($t,$s)
$s=$s-replace'.',('$0'*4)|%{$_;$_}  # magnify to 4*width and 2*heght
$n=$s|% Length|sort -b 1            # find max length
$s=$s+,''|% PadRight($n+1)          # add +1 to width and height
$s|%{                               # (in addition, we got a rectangle)
    -join(0..$n|%{
        $x=$_,--$_
        $b,$a,$d,$c=$s[--$y,++$y]|%{$_[$x]}           # I need to golf
        $i=!($a-$b)+2*!($a-$c)+4*!($b-$d)+8*!($c-$d)  # this 2 lines  cxxx|;:;:;:;:;:;:>

        $t[7*$i%95%13]
    })
    $y++
}

```

## Main idea

Let a square of 4 characters slide over the input string "magnified 4 times in width and twice in height".

```
..
..IILOO
 ILLLOO

 ..
 ..ILOO
 ILLLOO

  ..
 I..LOO
 ILLLOO

.~.~.~.~.~.

..IILOO
..LLLOO

 ..IILOO
 ..LLLOO

 I..ILOO
 I..LLOO

 II..LOO
 IL..LOO

.~.~.~.~.~.

 IIILOO
..LLLOO
..

.~.~.~.~.~.

 IIILOO
 ILLLO..
      ..

```

Let's name the points in the square as a,b,c,d.

The expression `(a=b)+2*(a=c)+4*(b=d)+8*(c=d)` returns numbers in range 0..15, which correspond to the border chars:

```
 0   1   2   3   4   5   6   7   8   9   10  11  12  13  14  15
----------------------------------------------------------------
 ab  aa  ab  aa  ab  aa  ab  aa  ab  aa  ab  aa  ab  aa  aa  aa
 cd  cd  ad  ad  cb  ca  ab  aa  cc  cc  aa  aa  bb  aa  aa  aa

 0   1   2   3   4   5   6   15  8   9   10  15  12  15  15  15  - the expression results

 ╬   ╦   ╠   ╔   ╣   ╗   ║       ╩   ═   ╚       ╝               - related border chars. the space char for 15
 0   7   1   8   2   9   3       4   11  5       6           10  - *7%95%13 - index in the "flat container"

 012345678901
 ╬╠╣║╩╚╝╦╔╗ ═    - the flat container

```

The script draws the border char for each position of the sliding square. Plus draws middle row between input lines.

The script expectes the flat container with border chars in order `╬╠╣║╩╚╝╦╔╗ ═`.

---
Tags: code-golf, ascii-art, unicode, polyomino
---


# Question
Title: Write an infinitely nested generator comprehension
The goal is to create a generator generator \[...\] generator generator comprehension.

1. The generator must be created via generator comprehension.
2. The following expression must be valid for any number of nestings: `next(next(next(next(next(generator)))))`.

The winner is whoever achieves this with the fewest number of bytes.

# Answer
# Python, ~~31~~ ~~26~~ 25 bytes

```
x=(x for()in iter(set,1))
```

Attempt This Online!

If assignment is not allowed:

# Python, ~~77~~ ~~72~~ 71 bytes

```
(gc.get_referrers(sys._getframe())[0]for()in iter(set,1))
import gc,sys
```

Attempt This Online!

(this is bad code)

-5 bytes on both solutions thanks to @ovs
> 11 votes

# Answer
@pxeger's solution is pretty much the end of this challenge. A generator expression *must* include code like `(a for b in c)`, where `a` must be a generator which behaves like the outer generator expression behaves. Either `a` refers to the outer generator itself, or `a` is a shorter solution to this problem; so a shortest solution must look like `x=(x for b in c)`. For this to *be* a solution, then `c` must be an infinite iterator.

I don't have a proof that `iter(int,1)` is the shortest possible way to make an infinite iterator, but it seems unbeatable. Otherwise, the only way to improve on @pxeger's solution is if you can write an infinite iterator in fewer than 11 bytes.

---

If we relax the rule requiring the result to be created using a generator expression, then here's a few other ideas:

Using `iter`: (18 bytes)

```
x=iter(lambda:x,1)

```

Using `yield`: (23 bytes)

```
def f():yield f()
x=f()

```

Using `itertools.cycle`: (44 bytes)

```
import itertools as i
x=i.cycle(l:=[])
l+=x,

```

---

That said, if the rule is only that the *outer-most* generator be created using a generator expression, and the results after that need not be generators (just things that `next` works on, i.e. any iterators), then `a` in the code above can be some solution to the relaxed challenge, instead of a self-reference: (32 bytes)

```
(z:=iter(lambda:z,1)for _ in[1])

```

This method still can't beat @pxeger's solution, unless there is a solution to the relaxed version of the challenge more than 6 bytes shorter than `z:=iter(lambda:z,1)`. This seems pretty unlikely, and even if it is possible, it would presumably be an infinite iterator; so it would still be shorter if you plugged it into @pxeger's solution instead of this one.
> 7 votes

---
Tags: code-golf, python
---


title: How many values of this type?

text:
# Question
Title: How many values of this type?
## Background

The number of values for a given type is called the *cardinality* of that type, and that of type T is written as `|T|`.

Haskell and a few other languages have a certain set of enum types, each of which has a small finite number of values (the exact names vary, so this challenge uses some arbitrarily chosen names).

```
Name  | Cardinality
------+-------------
Never | 0
Unit  | 1
Bool  | 2 (true or false)
Order | 3 (LT, EQ, or GT)

```

And they also have some derived types which have one or more *type parameters*. Their cardinality depends on which types they get as parameters (written as `T` and `U` in the table below). `Func(T,U)` represents the function commonly written as `T -> U`, i.e. a function that takes a parameter of type T and returns a value of type U.

```
Name(Params) | Cardinality
-------------+-------------
Option(T)    | |T| + 1     (some value from T, or absence)
Either(T,U)  | |T| + |U|   (some value from T or some value from U)
Pair(T,U)    | |T| * |U|   (any combination of values from T and U)
Func(T,U)    | |U| ** |T|  (any combination of U for every value of T)

```

Note: A "function" here is to be understood as a mathematical concept rather than a programming one. A mathematical function `Func(T,U)` maps every possible value of T to some value of U, disregarding the "how". For programmers, it is OK to think of it as functions of the form of (in Haskell-like pseudocode):

```
\(x :: T) -> case x of
  value1OfT -> someValue1OfU
  value2OfT -> someValue2OfU
  ...
  valueXOfT -> someValueXOfU

```

with all cases provided.

For example, `Option(Never)` has cardinality 1, and `Func(Bool,Order)` has cardinality `3**2 = 9`. `Func(Never,Never)` has cardinality 1; `0**0` is defined to be 1 in this system.

A type parameter can itself be a derived type, so `Pair(Func(Never,Never),Pair(Either(Bool,Bool),Option(Order)))` is also a valid type, which has cardinality of `(0**0) * ((2+2) * (3+1)) = 16`.

For this challenge, assume that no types other than the 8 presented above are available.

## Challenge

Given a string that represents a valid type in this system, output its cardinality. You can assume the input does not contain spaces.

Standard rules apply. The shortest code in bytes wins.

## Test cases

```
Never -> 0
Unit -> 1
Bool -> 2
Order -> 3
Func(Never,Never) -> 1
Func(Unit,Never) -> 0
Option(Unit) -> 2
Option(Order) -> 4
Either(Bool,Bool) -> 4
Either(Bool,Order) -> 5
Pair(Bool,Order) -> 6
Pair(Func(Never,Never),Pair(Either(Bool,Bool),Option(Order))) -> 16
Func(Func(Order,Order),Order) -> 7625597484987

```

# Answer
> 17 votes
# Proton, 80 bytes

```
Never,Unit,Bool,Order=0..4
Option=(1+)
Either=(+)
Pair=(*)
Func=(x,y)=>y**x
eval

```

Try it online!

This solution is a whole lot shorter in Proton. Original Python solution included below.

# Python 3, 106 bytes

```
Never=0
Unit=1
Bool=2
Order=3
Option=1 .__add__
Either=int.__add__
Pair=int.__mul__
Func=int.__rpow__
eval

```

Try it online!

-3 bytes thanks to dingledooper

`__rpow__` exists so I don't even have to do `lambda x,y:y**x` so this is even more boring :D

trivial solution and I'm sure there's something both better and smarter

# Answer
> 6 votes
# JavaScript (V8), 98 bytes

```
Never=0
Unit=1
Bool=2
Order=3
Option=x=>1+x
Either=(x,y)=>x+y
Pair=Math.imul
Func=(x,y)=>y**x
eval

```

Try it online!

Same idea as @hyper-neutrino, though its shorter in js

-1 byte thanks to @Arnauld

# Answer
> 6 votes
# 05AB1E, ~~77~~ ~~31~~ 28 bytes

```
Rv"0123>+*m ""NUBdpEPF"ykè.V

```

Byte-count more than halved and sped up a lot by porting *@Neil*'s Charcoal answer, so make sure to upvote him as well!

Try it online or verify all test cases.

**Explanation:**

```
R                            # Reverse the (implicit) input-string
 v                           # Loop over each of its characters `y`:
             "NUBdpEPF"yk    #  Get the index of `y` in "NUBdpEPF"
                             #  (which will result in -1 if it isn't present)
  "0123>+*m "            è   #  Use it to (0-base modulair) index into "0123>+*m "
                          .V #  Execute it as 05AB1E code:
                             #   `>`: Increment the top value by 1
                             #   `+`: Add the top two values together
                             #   `*`: Multiply the top two values
                             #   `m`: Take the exponent of the top two values
                             #   The digits 0-3 remain the same
                             #   ` `: No-op for not found characters / index -1
                             # (after which the result is output implicitly)

```

### Original (77 bytes) answer:

```
”†™‰¿ëÄ‚Ñ”#ā<:Δ”íŽ‰‡¥Öˆ¦c”#vD.γd}þàÝ©NĀiã©',ý}€…(ÿ)yì®N_i>ëíðý…m+*Nè«}øvy`.V:

```

Because 05AB1E lacks both regexes and functions, this uses a brute-force replacement method wrapped in a loop. It's therefore also extremely slow the larger the integer becomes, and will fail to complete the final test cases as is.

Try it online or verify all test cases (the `Δ` is replaced with `[Dd#` in the test suite to speed it up slightly, so we can also verify the last test case).

**Explanation:**

```
”†™‰¿ëÄ‚Ñ”       # Push dictionary string "Never Unit Bool Order"
          #      # Split it on spaces: ["Never","Unit","Bool","Order"]
           ā     # Push a list in the range [1,length] (without popping): [1,2,3,4]
            <    # Decrease each to the range [0,length): [0,1,2,3]
             :   # Replace all "Never" with 0; "Unit" with 1; etc. in the (implicit)
                 # input-string
Δ                # Loop until the result no longer changes:
[Dd#             # (slightly faster alternative, so we'll have one iteration less:)
[                #  Start an infinite loop
 D               #   Duplicate the current string
  d              #   If it's a non-negative (>=0) integer:
   #             #    Stop the infinite loop
 ”íŽ‰‡¥Öˆ¦c”     #  Push dictionary string "Option Either Pair Func"
            #    #  Split it on spaces: ["Option","Either","Pair","Func"]
 v               #  Loop over each string `y` in this list:
  D.γd}þà        #   Get the current maximum integer in the string:
  D              #    Duplicate the string
   .γ            #    Group this string into substrings by:
     d           #     If it's a non-negative (>=0) integer
      }þ         #    After the group-by, only leave these integers
        à        #    And pop and push the maximum
         Ý       #   Pop and push a list in the range [0,max]
          ©      #   Store it in variable `®`
  NĀi            #   If the index is NOT 0 (thus not "Option"):
     ã           #    Take the cartesian product of this list
      ©          #    Store that in variable `®` instead
       ',ý      '#    And join each inner pair with "," delimiter
    }€…(ÿ)       #   After the if-statement: wrap each integer/string into parenthesis
          yì     #   And prepend the current string `y`
  ®              #   Push list `®` again
   N_i           #   If the index is 0 (thus "Option"):
      >          #    Simply increase the value by 1
     ë           #   Else:
      í          #    Reverse each pair in the list
       ðý        #    Join each pair with space delimiter
         …m+*    #    Push string "m+*"
             Nè  #    Index the loop-index into it (0-based modulair)
               « #    Append it to each string
     }ø          #   After the if-else statement: zip to create pairs of the two lists
       v         #   Loop over each pair `y` in this list:
        y        #    Push the pair `y`
         `       #    Pop and push both values separated to the stack
          .V     #    Execute the second string as 05AB1E code, resulting in an integer
            :    #    Replace the first string to this integer
                 # (after which the result is output implicitly)

```

See this 05AB1E tip of mine (section *How to use the dictionary?*) to understand why `”†™‰¿ëÄ‚Ñ”` is `"Never Unit Bool Order"` and `”íŽ‰‡¥Öˆ¦c”` is `"Option Either Pair Func"`.

# Answer
> 4 votes
# Retina, 129 bytes

```
Or
Q
{T`NUBQ)(l`0-3;_
O(\d+);
$.(_$1*
E(\d+),(\d+);
$.($1*_$2*
P(\d+),(\d+);
$.($1*$2*
F(\d+)
F$1*
(F_*)_(,\d+;)
P$1$2$2
F,\d+;
1

```

Try it online! Link includes test cases. Explanation:

```
Or
Q

```

Change `Order` to `Qder` to avoid confusion with `Option`, and also because `O` has special meaning for Transliterate.

```
{

```

Repeat the remaining transformations until the desired result is obtained. (The transliteration does not need to be repeated but it's golfer to share the ```.)

```
T`NUBQ)(l`0-3;_

```

Transliterate the `Never`, `Unit`, `Bool` and `Qder` to `0` to `3` respectively, transliterate the `)` to `;` for ease of matching, and delete the lower case letters and `(`.

```
O(\d+);
$.(_$1*

```

Handle `Option` by incrementing the value.

```
E(\d+),(\d+);
$.($1*_$2*

```

Handle `Either` by taking the sum of the values.

```
P(\d+),(\d+);
$.($1*$2*

```

Handle `Pair` by taking the product of the values.

```
F(\d+)
F$1*

```

Convert the first parameter of `Func` to unary.

```
(F_*)_(,\d+;)
P$1$2$2

```

Compute `Func(n+1,m)` as `Func(n,m)*m` using `P` to do the multiplication.

```
F,\d+;
1

```

`Func(0,m)` is just `1`.

# Retina 0.8.2, 111 bytes

```
Op.{5}
EU,
T`NUB\O)(l`0-3;_
\d
$*
E(1*),(1*);
$1$2
(P1*)1(,1*;)
E$1$2$2
P,1*;

(F1*)1(,1*;)
P$1$2$2
}`F,1*;
1
1

```

Try it online! Link includes reduced test cases, as Retina 0.8.2 has to calculate in unary, which limits the magnitude of the result. Explanation:

```
Op.{5}
EU,

```

Change `Option(` to `Either(Unit,` (except preabbreviated).

```
T`NUB\O)(l`0-3;_

```

Transliterate the `Never`, `Unit`, `Bool` and `Order` to `0` to `3` respectively, transliterate the `)` to `;` for ease of matching, and delete the lower case letters and `(`.

```
\d
$*

```

Convert to unary.

```
E(1*),(1*);
$1$2

```

Handle `Either` by taking the sum of the values.

```
(P1*)1(,1*;)
E$1$2$2

```

Compute `Pair(n+1,m)` as `Pair(n,m)+m` using `E` to do the addition.

```
P,1*;

```

`Pair(0,m)` is just `0`.

```
(F1*)1(,1*;)
P$1$2$2

```

Compute `Func(n+1,m)` as `Func(n,m)*m` using `P` to do the multiplication.

```
F,1*;
1

```

`Func(0,m)` is just `1`.

```
}`

```

Repeat the above transformations until the desired result is obtained.

```
1

```

Convert to decimal.

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

A regex-based solution. This is longer than using @hyper-neutrino's method, but not as much longer as I was expecting.

```
s=>eval(s.replace(/\w+/g,s=>(i="enorpiau".search(s[1]))<4?i:`((x,y)=>y${['|1+','+','*','**'][i&3]}x)`))

```

Try it online!

### How?

All keywords can be unambiguously identified by looking at the second character. Hence the lookup string `"enorpiau"` and an index `i` into this string. We use the pattern `((x,y)=>y…x)` for all operations.

```
 i | keyword  | translation
---+----------+----------------
 0 | N[**e**]ver  | 0
 1 | U[**n**]it   | 1
 2 | B[**o**]ol   | 2
 3 | O[**r**]der  | 3
 4 | O[**p**]tion | ((x,y)=>y|1+x)
 5 | E[**i**]ther | ((x,y)=>y+x)
 6 | P[**a**]ir   | ((x,y)=>y*x)
 7 | F[**u**]nc   | ((x,y)=>y**x)
```

# Answer
> 3 votes
# Julia 1.0, 87 bytes

```
eval∘Meta.parse
Never,Unit,Bool,Order=0:3
Option,Pair,Either=x->x+1,*,+
Func(x,y)=y^x

```

Try it online!

Same idea as the other answers

# Answer
> 2 votes
# Charcoal, ~~66~~ ~~61~~ 60 bytes

```
Ｆ⮌Ｓ«≡ιd⊞υ³B⊞υ²U⊞υ¹N⊞υ⁰p⊞υ⊕⊟υE⊞υ⁺⊟υ⊟υP⊞υ×⊟υ⊟υF«≔⊟υθ⊞υＸ⊟υθ»»Ｉυ

```

Try it online! Link is to verbose version of code. Edit: Saved 5 bytes thanks to @KevinCruijssen pointing out that `d` and `p` uniquely identify `Order` and `Option`. Saved 1 byte by finding a slightly shorter way to exponentiate. Explanation:

```
Ｆ⮌Ｓ«

```

Loop over the characters of the input string in reverse order.

```
≡ι

```

Switch on the current character.

```
d⊞υ³

```

For `(Or)d(er)` push `3` to the predefined empty list.

```
B⊞υ²

```

For `B(ool)` push `2` to the predefined empty list.

```
U⊞υ¹

```

For `U(nit)` push `1` to the predefined empty list.

```
N⊞υ⁰

```

For `N(ull)` push `0` to the predefined empty list.

```
O⊞υ⊕⊟υ

```

For `(O)p(tion)` increment the top of the list.

```
E⊞υ⁺⊟υ⊟υ

```

For `E(ither)` sum the top two elements of the list.

```
P⊞υ×⊟υ⊟υ

```

For `P(air)` multiply the top two elements of the list.

```
F«≔⊟υθ⊞υＸ⊟υθ»

```

For `F(unc)` exponentiate the top two elements of the list. (Unfortunately the elements are in the wrong order, complicating the code. I tried processing the string from left to right which avoids that issue but that then requires an operator stack which ends up making the code much longer.)

```
»

```

Ignore any other characters.

```
Ｉυ

```

Output the final result.

# Answer
> 1 votes
# Ruby, ~~120~~ 95 bytes

```
p=i=->x,y=1{x+y}
a=->x,y{x*y}
u=->x,y{y**x}
f=->s{eval s.gsub(/\w+/){$&[1]}.tr'enor()','0-3[]'}

```

Try it online!

* Thanks to @Dingus for the 25 Bytes saved!

# Answer
> 1 votes
# , 121 bytes

Or **\>=4.1, 100 bytes** by replacing the three `function` appearances with `\`s.

```
function(s,Never=0,Unit=1,Bool=2,Order=3,Option=function(x)x+1,Either=`+`,Pair=`*`,Func=function(a,b)b^a)eval(parse(t=s))

```

Try it online!

doesn't have a simple `eval`, you need to `parse` the string first.

# Answer
> 1 votes
# Haskell, 206 bytes

```
f.read
data T=Never|Unit|Bool|Order|Option T|Either(T,T)|Pair(T,T)|Func(T,T)deriving Read
f(Option a)=f a+1
f(Either(a,b))=f a+f b
f(Pair(a,b))=f a*f b
f(Func(a,b))=f b^f a
f Never=0
f Unit=1
f Bool=2
f _=3

```

Try it online!

# Answer
> 0 votes
# Pari/GP, 92 bytes

```
Never=0
Unit=1
Bool=2
Order=3
Option(x)=1+x
Either(x,y)=x+y
Pair(x,y)=x*y
Func(x,y)=y^x
eval

```

Try it online!

The same as @hyper-neutrino's and @wasif's answers.

# Answer
> 0 votes
# Perl 5, 105 bytes

```
s/\w(.)\w+/$1/g;y/enor/0123/;1while s|([piau]).(\d+)(,(\d+))?\)|($4//1).({a,'*',u,'**'}->{$1}//'+').$2|ee

```

Try it online!

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


# Question
Title: Solve linear equations over the integers
All variables in this question are integer valued.

# Input

4 integers w, x, y, z. They can be positive or negative and will be less than 1048576 in absolute value.

# Output

The general solution to the equation.

\\$ aw+bx+cy+dz = 0 \\$.

The variables \\$a, b, c, d\\$ must all be integer values.

# Output format

Your output should consist of three tuples each with four parts, one for each of the values a, b, c, d. Let me explain by example:

```
Input: -118, 989, 918, -512

Mathematical answer:
        b = 2 n_0
        c = 9 n_0 + 256 n_1 + 81 a
        d = 20 n_0 + 459 n_1 + 145 a

```

Explanation: `n_0` and `n_1` are integers that you can set to anything you like. The solution says: `a` can also be set to any integer value, `b` must be twice whatever you set `n_0` to. This means that `a` can be set to any integer, `c` can now be calculated in terms of three variables we have already set and so can `d`.

The format of your output should be 3 tuples (#,#,#,#), (#,#,#,#), (#,#,#,#). We can assume three free integer variables n0, n1 and n2 and so (a,b,c,d) = (#,#,#,#)n0 + (#,#,#,#)n1 + (#,#,#,#)n2. In the example above the output would therefore be:

```
Output: (0, 2, 9, 20), (0, 0, 256, 459), (1, 0, 81, 145)

```

# Examples

Example one:

```
 Input: -6, 3, 7, 8

 Mathematical answer:
          c = 2a + 3b + 8n
          d = -a - 3b - 7n
          n is any integer

 Output: (1, 0, 2, -1), (0, 1, 3, -3), (0, 0, 8, -7)

```

Example two:

```
Input: -116, 60, 897, 578

Mathematical answer:
        c = 578 n + 158 a + 576 b
        d = -897 n - 245 a - 894 b
        n is any integer

Output: (1, 0, 158, -245), (0, 1, 576, -894), (0, 0, 578, -897)

```

Example three:

```
Input: 159, -736, -845, -96

Output: (1, 0, 27, -236), (0, 1, 64, -571), (0, 0, 96, -845)

```

# Discussion

To understand this challenge further it is worth looking at this possible general solution which does **not** work `[(z, 0, 0, -w), (0, z, 0, -x), (0, 0, z, -y)]`. The problem with this is that there are solutions to the problem instances above which are not the sum of any integer multiples of those tuples. For example: take input -6, 3, 7, 8 from Example 1. The proposed solution would give the tuples:

```
(8, 0, 0, 6), (0, 8, 0, -3), (0, 0, 8, -7)

```

Why doesn't this work?

There is a solution for this instance with a = 1, b = 1, c = 13, d = -11 because `-6+3+7*13-11*8 = 0`. However there are no integers n\_0, n\_1, n\_2 to make `n_0 * (8, 0, 0, 6) + n_1 * (0, 8, 0, -3) + n_2 * (0, 0, 8, -7) = (1, 1, 13, -11)` .

# Answer
# Python 2, 182 bytes

```
def E(a,b):
 if b:x,y,d=E(b,a%b);return y,x-a/b*y,d
 return 1,0,a
def f(a,b,c,d):x,y,g=E(a,b);z,w,h=E(c,d);j=E(g,h)[2];return(b/g,-a/g,0,0),(0,0,d/h,-c/h),(-x*h/j,-y*h/j,z*g/j,w*g/j)

```

Try it online!

Yes, it is possible to solve it without fancy built-ins. And this gives relatively good results for a non-LLL one.

### How it works

I derived a closed-form solution in the following steps: (I flipped the roles of \\$a,b,c,d\\$ and \\$w,x,y,z\\$ because it looked much more natural to me. So \\$a,b,c,d\\$ are coefficients and \\$w,x,y,z\\$ are unknowns here.)

$$ ax+by+cz+dw = 0 $$

If we define \\$g=\gcd(a,b)\\$ and \\$h=\gcd(c,d)\\$, the following substitutions can be done without loss of generality: (\\$u,v\\$ are temporary integer variables)

$$ ax+by = gu\\ cz+dw = hv $$

which results in a system of two heterogeneous and one homogeneous 2-variable linear Diophantine equations:

$$ ax+by = gu \\ cz+dw = hv \\ gu + hv = 0 $$

Then we can apply the textbook procedure:

$$ u = \frac{h}{j}n\_3, \\; v = \frac{-g}{j}n\_3 \quad \text{where} \\; j = \gcd(g,h) $$

If we let \\$(x\_0,y\_0)\\$ be a "special" solution to \\$ax+by=g\\$ and similarly \\$(z\_0,w\_0)\\$, then the solutions are

$$ \begin{align} x &= \frac{b}{g}n\_1 + \frac{-x\_0h}{j}n\_3 \\ y &= \frac{-a}{g}n\_1 + \frac{-y\_0h}{j}n\_3 \\ z &= \frac{d}{h}n\_2 + \frac{z\_0g}{j}n\_3 \\ w &= \frac{-c}{h}n\_2 + \frac{w\_0g}{j}n\_3 \end{align} $$

The special solutions can be found via Extended Euclidean algorithm. Special mention goes to this deceptively short and yet correct implementation of EGCD, once added to sympy but removed later:

```
def extended_euclid(a, b):
    if b == 0:
        return (1, 0, a)

    x0, y0, d = extended_euclid(b, a%b)
    x, y = y0, x0 - (a//b) * y0

    return x, y, d

```
> 5 votes

# Answer
# Wolfram Language (Mathematica), 39 bytes

Still a built-in.

`HermiteDecomposition` gives the Hermite normal form decomposition of an integer matrix.

```
HermiteDecomposition[List/@#][[1,2;;]]&

```

Try it online!

---

# Wolfram Language (Mathematica), without build-in, 118 bytes

Based on Algorithm 2.4.10 in *A Course in Computational Algebraic Number Theory* by Henri Cohen.

The output is sometimes extremely large. You can reduce them with the build-in `LatticeReduce`.

```
(a=#[[1]];U=IdentityMatrix@4;Do[{d,u}=ExtendedGCD[a,b=#[[j]]];U[[{1,j}]]={u,{-b,a}/d}.U[[{1,j}]];a=d,{j,2,4}];Rest@U)&

```

Try it online!
> 3 votes

# Answer
# SageMath, 92 bytes

```
def f(x,y,z,w):
 for v in'abcd':var(v,domain=ZZ)
 return solve([a*x+b*y+c*z+d*w==0],a,b,c,d)

```

Try it online!
> 2 votes

# Answer
# Pari/GP, 21 bytes

Another boring built-in answer.

> matkerint(x,{flag=0}): LLL-reduced Z-basis of the kernel of the matrix x with integral entries. flag is deprecated, and may be set to 0 or 1 for backward compatibility.

```
a->matkerint(Mat(a))~

```

Try it online!
> 1 votes

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


# Question
Title: Two roads diverged in a yellow wood (part 1)
This is the first in a series, the second is Two roads diverged in a yellow wood (part 2)

This challenge is inspired by Robert Frost's famous poem, "The Road Not Taken":

> Two roads diverged in a yellow wood,
> And sorry I could not travel both
> And be one traveler, long I stood
> And looked down one as far as I could
> To where it bent in the undergrowth;
>
> Then took the other, as just as fair,
> And having perhaps the better claim,
> Because it was grassy and wanted wear;
> Though as for that the passing there
> Had worn them really about the same,
>
> And both that morning equally lay
> In leaves no step had trodden black.
> Oh, I kept the first for another day!
> Yet knowing how way leads on to way,
> I doubted if I should ever come back.
>
> I shall be telling this with a sigh
> Somewhere ages and ages hence:
> Two roads diverged in a wood, and I —
> I took the one less traveled by,
> And that has made all the difference.

Notice the second to last line, `I took the one less traveled by,`.

## Your actual challenge

You will take input in the form like:

```
#     ##
 #   ##
  # ##
   #
   #
   #

```

and you have to find the thinner road.

The road starts at the bottom with a `#`. The other 2 roads, which always terminate on the top row, are the roads you have to examine. The road that is the thickest is most traveled by, and therefore it is not what you want. The other one is the least traveled by, and it is the one you want.

## Output

Your program/function must output one of 2 distinct values (eg. 0 or 1, true or false), one for each possible position of the road not taken. For example, you could output 0 if the road not taken is on the left of the road taken, and 1 otherwise, or you could output the string "left" or "right", true, false, etc.

## Test cases:

```
 ##    #
  ##  #
   ###
    #
    #
    #

```

Might output "right".

```
 ##  #
  ## #
   ###
    ##
     #
     #
     #

```

Might output "right".

```
 ##  #
  ## #
   ###
    ##
   #
  #
 #

```

Might output "right".

```
 ##   #
  ## #
   ###
    #
   #
  #
  #

```

Might output "right".

```
 #    ##
  #  ##
   ###
    #
   #
  #
  #

```

Might output "left"

```
 #    ##
  #  ##
   ###
    #
     #
     #
     #

```

Might output "left"

## Notes

* This is , so the shortest answer in bytes wins
* Standard loopholes forbidden
* You must specify your outputs for "left" and "right" and they must be distinct
* Input will be one big string, and may have any amount of lines
* You don't need to worry about valid input.
* The road is always a Y shape, so you only have to look at the top.
* Have any questions? Comment below:

### Lowest byte count wins!

# Answer
> 15 votes
# CJam, 1 byte

```
r

```

`r` puts the first string of adjacent non-whitespace characters from STDIN on the stack, so this prints `##` for *left* and `#` for *right*.

Try it online!

# Answer
> 18 votes
# JavaScript(ES6), ~~19~~ 14 bytes

```
a=>a.trim()[1]

```

Returns `#` for right and a space for left.

## **Original:**

```
a=>a.trim()[1]=='#'

```

### Explanation

**Ungolfed**:

```
function(input) {
  return input.trim().charAt(1) === '#';
};

```

The first thing this function does is remove white space the beginning and end of the input. This means that the first character is always `#`. Then from there I check the second character(JavaScript starts at 0) and see if it is a `#` character. This returns a boolean. If the path is `right` it will be `true`, if it is left it will return `false`.

### How I golfed it

In ES6 there is an anonymous function shorthand called an arrow function. This means that I can take my wrapper function and turn it into:

```
input => ...;

```

Due to the rules of arrow functions it will return the rest of the code. From there I converted `charAt(1)` to `[1]` as it is a shorter way, though not recommended. Then I took `===` and turned it into `==`. While they are different in this case it doesn't matter. Finally, I renamed `input` to `a` and removed all whitespace.

### Output right and left

While the puzzle doesn't actually need the program to output right and left, here's an example of other outputs:

```
a=>a.trim()[1]=='#'?'right':'left'

```

The only added part is `?'right':'left'`. This creates a ternary operator, a condensed if statement, this means that the(ungolfed) code is equal to\*:

```
function(input) {
  let output = input.trim().charAt(1) === '#';
  if(output) {
    return 'right';
  } else {
    return 'left'
  }
};

```

# Example

```
// Function assignment not counted in byte count
let f =
a=>a.trim()[1]=='#'
```

```
<textarea placeholder="Put path in here" id="path" rows="10" style="width:100%"></textarea>
<button onclick="document.getElementById('result').textContent = f(document.getElementById('path').value)">Submit</button>
<p id="result"></p>
```

# Answer
> 10 votes
# *Acc!!*, 30 bytes

Because of the way *Acc!!* takes input, it will give the output after just one line of input is entered. But if you pipe the input in or redirect it from a file, you shouldn't notice the difference.

```
Count i while 35-N {
}
Write N

```

Takes input from stdin. Outputs  if the left-hand road is less traveled, or `#` if the right-hand road is less traveled. Try it online!

### Explanation

`N` reads the ASCII value of a character from stdin every time it is referenced. We loop while `35-N` is truthy; that is, while `35-N != 0` or `N != 35`. Therefore, when the loop exits, we have just read the first `#` character on the line. The next character is then read with `N` and written back to stdout with `Write`.

# Answer
> 9 votes
# Pyth, 2 bytes

```
hc

```

Outputs `#` for left and `##` for right.

**Try it online**

# Explanation

```
hc
 cQ     Split the (implicit) input on whitespace.
h       Get the first part.

```

# Answer
> 7 votes
# Retina, 5 bytes

Outputs `1` if right, `0` if left.

```
^ *##

```

**Try it online**

---

If the values for a positive result didn't have to be distinct (5 bytes):

Outputs a positive integer if right, zero if left.

```
## +#

```

**Try it online**

# Answer
> 5 votes
# IBM/Lotus Notes Formula Language, ~~37~~ ~~35~~ 26 bytes

**Edit** I always forget that `@Like` with wildcards is 2 bytes cheaper than `@Contains`.

**Edit 2** Actually doesn't need the `@if` as it just prints `1` or `0` depending on whether the formula results to `@True` or `@False`.

```
@Like(@Left(a;"##");"%#%")

```

Computed field formula. Simply take everything to the left of the first `##` it finds in field `a` and if there is a `#` in it outputs `1` for left otherwise outputs `0` for right.

With thanks to @DavidArchibald, here is a solution for 22 bytes. Out of respect for Davids solution I won't post it as my main answer.

```
@Left(@Trim(a);2)="##"

```

This one outputs `1` for right and `0` for left.

# Answer
> 4 votes
# C, 35 bytes

```
f(char*s){while(35^*s++);return*s;}

```

Same idea as PragmaticProgrammer's answer: find the first `#`, and output what comes after it -- `#` for "right", and `<space>` for "left".

# C (loophole), 16 bytes

According to the test cases, it looks like the left road is always exactly one space from the left margin. So...

```
#define f(s)2[s]

```

# Answer
> 3 votes
# Pip, ~~8~~ 6 bytes

```
a~`#+`

```

Takes input as a command-line argument (which will need quoting and escaping of newlines when run from an actual command line). Outputs `#` if the left-hand road is less traveled, and `##` if the right-hand road is less traveled. Try it online!

### Explanation

This uses Pip's recently added regex first-match operator.

```
a         First cmdline arg
 ~        Regex match the first instance of...
  `#+`    ...one or more #s (i.e. a cross-section of the left-hand road)
          Print (implicit)

```

The straightforward regex solution (a port of mbomb007's Retina answer) is 9 bytes:

```
`^ +##`Na

```

# Answer
> 3 votes
# Chip, 7 bytes

```
AZ~S
at

```

Try it online!

Outputs `0x0` for left, and `0x1` for right. (The TIO includes flag `-v` so you can see the binary values in stderr. To see the output in ASCII, `e*f` can be appended to the end of the first line.)

Chip operates on individual bits within a byte stream, which actually makes it quite good at this specific problem.

`A` is the least significant bit of the input byte, and '#' is the only character of input for which this bit is set. When this bit is first encountered, we have reached the first '#' of the first line.

`Z` delays that signal for one cycle, so that we are now looking at the next character.

`t` is now activated, which means to terminate execution after this cycle is completed. We don't need to look further than the width of the first road.

`~S` suppresses output for all cycles except the final one. If this wasn't here, we'd get an output on every cycle.

`a` puts the current value of its neighbors (only `A` in this case) to the least significant bit of the output byte.

All of this means that we get a `0x1` if the first '#' is immediately followed by another '#', and `0x0` otherwise.

# Answer
> 2 votes
## Batch, 46 bytes

```
@set/ps=
@for %%a in (%s%)do @echo %%a&exit/b

```

Reads one line from STDIN, splits it on spaces, and prints out the first word, so outputs `#` for left and `##` for right. If an array of quoted command-line parameters is acceptable, then for 36 bytes:

```
@for %%a in (%~1)do @echo %%a&exit/b

```

Unquotes the first argument so that it will be split on spaces and print its first word.

# Answer
> 2 votes
## Python 2, 21 bytes

Try it online

```
lambda S:S.split()[0]

```

Output `#` for left and `##` for right

# Answer
> 2 votes
# Brainfuck, 32 bytes

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

```

### Ungolfed:

```
+[                       while 1
>,>+++++[<------>-]<--     3 if hash; 0 if space
[,.>>]                     print next char and break iff current char is hash
<]

```

Prints `#` for right and  for left.

Try it online!

# Answer
> 2 votes
# Haskell, 21 bytes

```
f n=snd$span(==' ')n!!1

```

or in point-free style:

```
(!!1).snd.span(' '==)

```

"#" means right, and " " means left

The function just takes a string, drops the beginning spaces, and then, it takes the second character (space if the left is skinny and # if the left is thick)

EDIT: Saved three bytes thanks to Laikoni and nimi!

# Answer
> 2 votes
## C 54 bytes

```
char*strchr();char c(char*s){return*(strchr(s,35)+1);}

```

## C++ 58 bytes

```
#include<cstring>
char c(char*s){return*(strchr(s,35)+1);}

```

Since OP specified it can be a "program/function" I elected to write a function to save characters. However, I still included the "#include" statement and accompanying line break in the character count as they are required to compile the function.

**Output**

Returns a space `" "` character to indicate left, or a hash `"#"` character to indicate right.

**Explanation**

The strchr() function walks a given string and returns a pointer to the first occurrence of a specified character. It has an overload which accepts an integer as the second argument as opposed to a char which saves me 1 character. E.g. '#' can be replaced with 35. I then add one to the pointer returned from the function to get the character immediately following, and dereference it, then return the resulting char.

**Note**

I would also like to take this opportunity to formally express my annoyance at Visual Studio auto-formatting my code when I'm trying to golf (╯°□°）╯︵ ┻━┻.

**Edit:** Thanks to Ray for pointing out some differences in C and C++ and where I could save characters \<3.

# Answer
> 2 votes
## Retina, 5 bytes

```
!1`#+

```

Try it online!

An alternative 5-byte solution. Prints `#` for left and `##` for right. The idea is to match all the runs of `#`s (`#+`) and print (`!`) only the first one of them (`1`).

# Answer
> 1 votes
# JavaScript (ES6), 37 bytes

```
p=s=>/^ *#( |$)/.test(s.split("\n")[0])

```

## Explanation:

`p` is a function that returns `true` if the road less traveled by is on the left and false otherwise. This is my first answer on this site, so it probably could be golfed more (maybe the regex.)

It works by taking the top line of the input and seeing if it matches the regex `/^ *#( |$)/` (start of string, any amount of spaces, a #, and a space or end of string.)

This is just to give people clarification about the format and generate ideas. I am sure it can be beat and golfed further. Happy golfing!

```
p=s=>/^ *#[^#]/.test(s.split("\n")[0])
```

```
<textarea rows = "8" cols = "8" oninput = "console.log(p(this.value))"></textarea>
```

# Answer
> 1 votes
## Excel, 17 bytes

```
=left(trim(A1),2)

```

Assumes input in cell `A1`.

Returns `##` for right and `#` (`#` and space) for left.

# Answer
> 1 votes
# Java 8, ~~166~~ ~~66~~ ~~63~~ ~~52~~ ~~43~~ 21 bytes

```
s->s.trim().charAt(1)

```

Outputs `35` for right and `32` for left.
Based on *@Clashsoft*'s Dyvil answer.

Try it online.

**Explanation:**

```
s->           // Method with String parameter and integer return-type
  s.trim()    //  Remove leading and trailing whitespaces
   .charAt(1) //  and return the second character (as int value)

```

# Answer
> 1 votes
# Perl 5, 8 + 1 = 9 bytes

```
die$F[0]

```

Try it online!

Run with `-a` (1 byte penalty).

Output is `# at *filename* line 1, <> line 1` (where *filename* is the filename of the script) if the left road is less travelled, or `## at *filename* line 1, <> line 1` if the right road is less travelled.

## Explanation

The `-a` option automatically reads input and splits it into columns around whitespace, ignoring leading whitespace. As such, the first datum of input is what we need; that's `$F[0]`. It also puts the program in an implicit loop, which we don't want. However, the use of `die` allows us to output a string, and exit the implicit loop, at the same time (and with no more characters than `say`, the more usual way to print a string).

# Answer
> 1 votes
# Dyvil, 12 bytes

```
s=>s.trim[1]

```

Explanation:

```
s=>          // lambda expression
   s.trim    // removes leading (and trailing) whitespace
         [1] // gets the second character

```

Usage:

```
let f: String -> char = s=>s.trim[1]
print f('...')

```

Returns  (whitespace) for left and `#` for right.

# Answer
> 0 votes
# Japt, 3 bytes

```
x

```

(2 bytes for `-g1` flag) Outputs `#` for right and a space for left. Based on the JavaScript answer by David Archibald.

Try it online!

# Answer
> 0 votes
# Befunge 98, 11 bytes

```
-!jv~'
@.~<

```

Try it Online!

Prints `32`  for left, and `35`  for right, both with a single trailing space.

### Explanation

```
-!jv      This is a no-op the first time through, but used later

    ~'    Pushes the ASCII value of the next character, and pushes 32
-!        Subtracts the 2, and nots. If the character was a space, the top will be 1
  jv      Goes to the second line if the character was not a space

  ~<      Pushes the next characer's ASCII value
 .        Prints it (32 for " " and 35 for "#")
@         Ends the program

```

One trick I used was putting the `-!jv` first, even though it didn't do anything. This let me both get rid of the space after the `'` and saved some padding. With this last, the code would be

```
~' -!jv
   @.~<

```

for 15 bytes.

# Answer
> 0 votes
## Ruby, 20 bytes

```
->r{r.strip[1]==' '}

```

Returns true for left, false for right.

# Answer
> 0 votes
# Batch 34 bytes

Checks input file `%1` using `Find` with conditional execution (`&&`=Success `||`=Fail) and returns L or R depending on the presence of `##` , which is only present when the road most travelled by is to the left.

```
@Find "## " %1>nul&&echo(R||echo(L

```

---
Tags: code-golf, ascii-art, decision-problem
---


# Question
Title: Two roads diverged in a yellow wood (part 2)
This is the second in a series, the third is Two roads diverged in a yellow wood (part 3)

This is based on Two roads diverged in a yellow wood (part 1), a previous challenge of mine. It was fairly well received, but it was also fairly trivial (a Java answer in 52 bytes!) So I made something more complex...

## The inspiration

This challenge is inspired by Robert Frost's famous poem, "The Road Not Taken":

> Two roads diverged in a yellow wood,
> And sorry I could not travel both
> And be one traveler, long I stood
> And looked down one as far as I could
> To where it bent in the undergrowth;
>
> ...2 paragraphs trimmed...
>
> I shall be telling this with a sigh
> Somewhere ages and ages hence:
> Two roads diverged in a wood, and I —
> I took the one less traveled by,
> And that has made all the difference.

Notice the second to last line, `I took the one less traveled by,`. Your goal is to find the road least travelled by in your string input. You must output one of 2 values that are distinct from each other that signal which way you should turn to take the road less traveled by. Once the road forks (the trail of hexagons changes to numbers) you are at the intersection. From there, there will be 2 paths made up of digits. The path whose digits has the lowest sum will be the road not taken. Note that the road not taken may have a larger path but a lower path sum. Here are some examples / test cases from a program that prints "left" or "right" for the path not taken:

```
 1     2
  1   2
   1 2
    #
    #
    #
left (3 < 6)

 1     2
  2   2
   1 1
    #
    #
    #
left (4 < 5)

 12    2
  11  2
   1 1
    #
    #
    #
right (6 > 5)

 99   989
  99  89
  99 99
  99 99
    #
    #
    #
   #
left (72 < 79)

1111 1110
 001 111
  11 11
  11 11
    #
   ##
  ##
 ##
left (9 < 10) (Note: 1111 is interpreted as 1+1+1+1=4, not 1111=1111)

1       1
 0     1
  1   1
  1   1
  1   1
  1   1
   1 1
    #
    #
    #
     #
      #
left (6 < 7)

1   1
 0   1
  1   1
  1   1
  1   1
  1   1
   1 1
    #
    #
    #
     #
      #
left (6 < 7)

```

## Things to assume & remember

* There will always be 2 paths. No more, no less.
* You can take input from STDIN one line at a time, a string containing LF characters, or a string containing a literal backslash and a n. If you need input in any other way, ask for approval in the comments.
* You don't have to worry about invalid input or tied paths. Those will never be inputted to your program / function.
* The input can be of any length in width or height, less than the string limit of your language.
* There will never be a `#` and a number in the same line.
* All digits in the path are positive integers 0 to 9.
* Input or output with a trailing newline is allowed.
* See my JS ES6 answer below for an example.
* There will always be at least 1 space between the 2 paths.
* The 2 paths will always have the same height for each map, but may be different on other maps.
* If you are confused about a specific test case, please tell me.
* **1111 is interpreted as 1+1+1+1=4, not 1111=1111. The map is a series of one-digit numbers, not numbers of arbitrary length.**
* This is , so the shortest answer in bytes wins!
* Standard loopholes forbidden

**If you have any questions about this challenge, ask me in the comments, and good luck!**

# Answer
> 2 votes
# 05AB1E, ~~21~~ 15 bytes

Outputs **0** for left and **1** for right.

```
|vy#õK€SO})øO`›

```

Try it online!

**Explanation**

```
|v                # for each line in input
  y#              # split on spaces
    õK            # remove empty strings
      €S          # split each string into a list of chars
        O         # sum each sublist
         }        # end loop
          )ø      # wrap stack in a list and zip
            O     # sum each sublist (side of the tree)
             `›   # compare left to right

```

# Answer
> 10 votes
## Retina, 28 bytes

```
\d
$*
%r`1\G
-
Os`.
+`-1

1+

```

Try it online!

Prints `0` for left and `1` for right. Assumes that there are not trailing spaces on any lines.

### Explanation

```
\d
$*

```

Convert each digit `N` to a run of `N` ones.

```
%r`1\G
-

```

One each line (`%`), match consecutive (`\G`) ones from the end (`r`) and replace each of them with `-` (i.e. turn the right branch into `-`s).

```
Os`.

```

Sort all characters, so that all `-`s are directly in front of all `1`s.

```
+`-1

```

Repeatedly cancel a pair of `-` and `1`.

```
1+

```

Try to match at least one `1` (if so, there were more weights in the left path).

# Answer
> 8 votes
# Chip, 216 bytes

```
 EZ,Z~.
E~]x-.|
F].>vm'
Ax]}#----------------.
Bx]}#---------------.|z.
Cx]}#------------.,Z|##' E
Dx]}#---------.,Z|`@@('A~^~t
 E.>#------.,Z|`@@-('
A~S`#v--.,Z|`@@-('
*f,--<,Z|`@@-('
e |,Z|`@@-('
,Z|`@@-('
>@@-('
a

```

Try it online!

A little bigger than the answer for part 1...

### Overview

Chip is a 2D language inspired by actual circuitry, and it deals with the component bits of each byte in a byte stream.

This solution keeps a running sum of the digits it sees, flipping the sign of the input each time it encounters a stretch of whitespace, then terminating upon the first `#`. So, for input

```
 11   12
  2   2
   1 1
    #
    #
    #

```

We get `1 + 1 - 1 - 2 + 2 - 2 + 1 - 1 = -1`. The sign of the result is given as the output, a negative number produces the result `1`, and positive is `0`.

Therefore, output of `1` means that the left path is less taken, and `0` means right.

### Explanation

At a high level, this is how it works:

The main diagonal with the `@` elements is the accumulator, output is decided by the `a` at the bottom. (Eight pairs of `@` means eight bits, but the highest bit is the sign, so this solution can handle a maximum difference of +127 or -128. Overflowing partway through is okay, as long as we come back before terminating.)

The four lines that start like `Ax]}#--`... are reading the input, and in the case of a digit, negating it (if necessary) and passing the value into the adders.

The first three lines decide if we are looking at a digit, or a sequence of whitespace, and keep track of whether the digits need to be negated.

The remaining elements wedged in under the inputs and the elements at far right handle the termination condition, and map the output to ASCII (so that we get characters `'0'` or `'1'` instead of values `0x0` or `0x1`. This ASCII mapping required no extra bytes, otherwise I wouldn't have included it.)

# Answer
> 7 votes
# Python 2, ~~95~~ ~~89~~ ~~88~~ 87 bytes

Here is my first go at this in python. Definitely not optimal but a decent start.

```
f=lambda x,i:sum(sum(map(int,y))for y in x.split()[i::2]if"#"<y)
lambda x:f(x,1)>f(x,0)

```

Try it online!

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

```
x=>x.replace(/\d(?=.*( )|)/g,(d,s)=>t-=s?d:-d,t=0)&&t<0

```

Assumes there are no trailing spaces on each line, and outputs `true` for `right`, `false` for `left`. The trick is to match each digit in the input, and if there is a space after it on the same line, subtract it from the total; otherwise, add it to the total. If the final total is less than 0, the right road is the one less traveled by, and vice versa.

Try it out:

```
f=x=>x.replace(/\d(?=.*( )|)/g,(d,s)=>t-=s?d:-d,t=0)&&t<0
```

```
<textarea placeholder = "paste in a map here..." oninput = "document.querySelector('div').innerText = f(this.value)"></textarea>
<div></div>
```

# Answer
> 4 votes
# Python 3, 85 94 bytes

```
import re
g=lambda s,i:sum(map(int,''.join(re.findall('\d+',s)[i::2])))
lambda s:g(s,0)>g(s,1)

```

Try it online!

Curses! Didn't read the problem close enough. Added a the fix (`''.join()`), but at the cost of 9 bytes.

# Answer
> 3 votes
## Python 2, 78 bytes

-1 byte thanks to @math\_junkie

Try it online

```
def F(S,r=0):
 for c in S.split():
    if'#'<c:r+=sum(map(int,c));r=-r
 print r>0

```

Prints `False` for left path and `True` for right

# Answer
> 2 votes
## JavaScript (ES6), 106 104 bytes

```
s=b=>(b=b.split`\n`,c=0,d=0,b.forEach(a=>{a=a.match(/\d+/g)||[],c+=+(a[0]?a[0]:0),d+=+(a[1]?a[1]:0)}),c<d)

```

```
s=b=>(b=b.split("\n"),c=0,d=0,b.forEach(a=>{a=a.match(/\d+/g)||[],c+=+(a[0]?a[0]:0),d+=+(a[1]?a[1]:0)}),c<d)

```

`s` is a function that returns `true` if the road not taken is on the left. Ungolfed:

```
var proc = function(str){
    str = str.split("\n");
    var left = 0;
    var right = 0;
    str.forEach(item=>{
        var match = item.match(/\d+/g) || [];
        console.log(match);
        left += +(match[0] ? match[0] : 0);
        right += +(match[1] ? match[1] : 0);
    });
    return left < right;
};

```

```
s=b=>(b=b.split`\n`,c=0,d=0,b.forEach(a=>{a=a.match(/\d+/g)||[],c+=+(a[0]?a[0]:0),d+=+(a[1]?a[1]:0)}),c<d)
```

```
<textarea placeholder = "paste in a map here..." oninput = "document.querySelector('div').innerText = s(this.value)"></textarea>
<div></div>
```

# Answer
> 2 votes
## Retina, 180 bytes

Byte count assumes ISO 8859-1 encoding.

```
^(?=( *(0|(1|(?<3>2|(?<3>3|(?<3>4|(?<3>5|(?<3>6|(?<3>7|(?<3>8|(?<3>9))))))))))+.+¶)+)(.+ (0|(?<-3>1|(?<-3>2|(?<-3>3|(?<-3>4|(?<-3>5|(?<-3>6|(?<-3>7|(?<-3>8|(?<-3>9))))))))))+¶)+ *#

```

Try it online!

I thought I'd also try a regex-only solution (the above is a plain .NET regex which matches only inputs where the right path should be taken, except for using  as a shorthand for `\n`).

It's annoyingly repetitive, but that's what happens when you have to treat each possible digit individually.

The solution is a fairly straight-forward application of balancing groups: first we sum the digits in the left branch by pushing `N` captures onto stack `3` for each digit `N`. Then we try to reach the `#`, while popping from stack `3` `N` times for each digit `N` in the right branch. This is only possible if the sum of digits in the left branch is greater than that in the right branch (since you can't pop from an empty stack).

# Answer
> 2 votes
## CJam, ~~19~~ 18 bytes

```
qN/Sf%z{'1*:~:+}/>

```

Try it online!

Prints `0` for left and `1` for right.

### Explanation

```
q      e# Read all input.
N/     e# Split into lines.
Sf%    e# Split each line around runs of spaces.
z      e# Transpose to group each branch.
       e# Note that each branch will have the same number of digit segments
       e# now but the first branch will also have all the #s at the end in
       e# separate segments.
{      e# For each branch...
  '1*  e#   Join the segments into a single string with 1s as separators.
       e#   This will add the same number of 1s between digit segments in
       e#   both branches (which won't affect their relative sum) and it
       e#   will also insert a 1 before each # in the first branch.
  :~   e#   Evaluate each character. The digit characters are simply turned
       e#   into their values, but # is the exponentiation operator in CJam.
       e#   This is why we inserted those additional 1s, because 1# is a no-op.
  :+   e#   Sum the digits in the branch.
}/
>      e# Check whether the left branch's sum is greater than the right one's.

```

# Answer
> 1 votes
# PowerShell, 80 bytes

```
$args-split'\s|#'-ne''|%{$a+=(($i=[char[]]$_-join'+'|iex),-$i)[($x=!$x)]};$a-gt0

```

Try it online!

*(Just squeaking under the Python answers. :D)*

Outputs `True` for the left path and `False` for the right path.

Takes input as a string delineated with ``n`, which is the PowerShell equivalent of *"a string containing a literal backslash and a n"*, or as a literal multiline string. We then `-split` that input on `\s` (whitespace including newlines) or `#` and filter out all the empty results `-ne''`, so we're left with just an array of the digits. Those are fed into a loop `|%{...}`.

Each iteration, we first take the current element `$_`, cast it as a `char` array, `-join` it together with a plus sign `+`, and pipe it to `iex` (short for `Invoke-Expression` and similar to `eval`). That's stored into `$i` so we properly sum up the digits on this particular chunk of the path. We then use that and its negative as the two elements of an array `($i, -$i)`, indexed into by flipping a Boolean value back and forth. Meaning, the first iteration through this loop, the first left path chunk, we'll index into `-$i`; the next time, we'll take `$i`; and so on. Those are accumulated into `$a` with `+=`.

Finally, we evaluate whether `$a` is `-g`reater`t`han `0`. If it is, then the right path had a larger sum, otherwise the left path had a larger sum. That Boolean result is left on the pipeline, and output is implicit.

# Answer
> 1 votes
# Mathematica, ~~80~~ 77 bytes

*Thanks to Martin Ender for saving 3 bytes!*

```
#<#2&@@Total@Partition[Tr/@ToExpression[Characters@StringSplit@#/."#"->0],2]&

```

Pure function taking a newline-delimited string as input, and returning `True` to take the left path, `False` to take the right path. Damn those long Mathematica command names; this is like 10 tokens.

# Answer
> 1 votes
# Python 3, 84 bytes

Since all the current Python submissions are functions, I thought I'd contribute a full program.

```
x=0
try:
 while 1:
  for n in input().split():x=-x+sum(map(int,n))
except:print(x>0)

```

Prints `True` if the left path is less traveled, `False` otherwise. Try it online!

For each line of input, this splits on whitespace, sums the digits of each resulting element, and adds it to a tally while flipping the sign of the tally at each step. It continues reading lines of input until it hits one with a `#`, at which point `map(int,n)` raises an exception and we exit the loop, printing `True` if the tally is positive and `False` otherwise.

# Answer
> 1 votes
# Java 10, ~~219~~ ~~216~~ ~~208~~ ~~162~~ 146 bytes

```
s->{int l=0,i;for(var x:s.split("\n"))for(i=2;!x.contains("#")&i-->0;)for(int c:x.trim().split("\\s+")[i].getBytes())l+=i>0?48-c:c-48;return l>0;}

```

Bit longer than ~~52~~ 21 bytes this time. ;)
Returns `false` for right and `true` for left.

-24 bytes thanks to *@ceilingcat*.

Try it online.

**Explanation:**

```
s->{                              // Method with String parameter & boolean return-type
  int l=0,                        //  Counter, starting at 0
      i;                          //  Temp integer `i`
  for(var x:s.split("\n"))        //  Loop over the lines:
      for(i=2;!x.contains("#")&   //   Skip lines that doesn't contain "#":
              i-->0;)             //    Inner loop `i` in the range (2,0]:
        for(int c:x.trim()        //     Remove the leading/trailing whitespaces from
                                  //     the current line
                   .split("\\s+") //     Then split it on whitespaces
                     [i]          //     Get the `i`'th part
                   .getBytes())   //     And inner loop over the bytes of this part:
          l+=i>0?                 //      If `i` is 1:
              48-c                //       Decrease the counter by this digit
             :                    //      Else (`i` is 0):
              c-48;               //       Increase the counter by this digit
  return l>0;}                    //  Return whether the counter is positive

```

# Answer
> 0 votes
# Pip, ~~19~~ 18 bytes

```
LR+XDax:-x+$+$0SGx

```

Takes input as a single string on the command line (which will need quoting and escaping of newlines if run on an actual command line). Outputs `-1` for left, `1` for right. Try it online!

### Explanation

Loops over runs of digits, adding the digit sums to a tally. The sign of the tally is swapped each time, with the end result that the left-hand values are negative and the right-hand values are positive. Then we print the sign of the final tally (`-1` or `1`).

```
                    a is 1st cmdline arg; XD is regex `\d`; x is "" (implicit)
                    Note that "" in a math context is treated as 0
  +XD               Apply regex + to XD (resulting in `\d+`)
LR   a              Loop over matches of that regex in a:
             $0      Regex match variable containing the full match
           $+        Sum digits by folding on +
      x:-x+          Swap the sign of the tally and add this sum
               SGx  After the loop, print the sign of the tally

```

# Answer
> 0 votes
# Haskell, 64 bytes

```
g=sum.map fromEnum
f(a:b:r)|a>"#"=g a-g b+f r|1<3=0
(>0).f.words

```

Try it online! Usage: The anonymous function `(>0).f.words` takes a newline separated string as argument and returns `False` for left and `True` for right.

**Explanation:**

Given an input

```
 99   989
  99  89
  99 99
    #
    #
   #

```

that is the string `" 99 989\n 99 89\n 99 99\n #\n #\n #"`, then `words` strips all newlines and spaces and returns a list of the remaining strings: `["99","989","99","89","99","99","#","#","#"]`. The function `f` takes the first two elements `a` and `b` from this list and checks whether `a` is a string of digits by comparing it to the string "#". (Because the char `'#'` is smaller than all the digit chars `'0'`, `'1'`, ... every string starting with a digit will be lexicographically larger than `"#"`.) The function `g` maps each char in a string to its ascii character code and returns their sum. In `f` we apply `g` to `a` and `b` and compute `g a - g b`, that is the value of the left path minus the value of the right one, and add it to a recursive call to `f` to handle the following lines. If the left path is more travelled the result from `f` will be negative and otherwise positive for the right path, so `(>0)` checks if the result is larger than zero.

# Answer
> 0 votes
## Batch, 169 bytes

```
@echo off
set/as=0
:l
set/pr=
if not %r: =%==# call:c - %r%&goto l
cmd/cset/a"s>>9
exit/b
:c
call:r + %3
:r
set/as%1=%2%%10,d=%2/10
if %d% gtr 0 call:r %1 %d%

```

Prints `0` for left, `-1` for right. Note: Reads lines until it finds one with a `#`, then stops reading. The difference in path sums is limited to 511 (add 1 byte to support larger differences). No more than 9 digits in each row of each path (supports any number of rows). Explanation: The `d` subroutine takes two parameters: whether to add or subtract and the digit(s). It extracts the last digit by modulo by 10 and the remaining digits by dividing by 10 and calls itself recursively while there are still digits remaining. The `c` subroutine takes three parameters: whether to add or subtract, the digits to add or subtract, and further digits to add. It calls the `d` subroutine to handle the digits to add and then falls through to handle the first two parameters. This means that calling the `c` subroutine with the parameters of `-` and the left and right digits will add the right digits and subtract the left digits. Finally the result is shifted to extract the sign.

# Answer
> 0 votes
# Octave, 46 bytes

```
@(a)diff((a(:)-48)'*(bwlabel(a>35)(:)==1:2))<0

```

Try it online! A function that takes a 2D character array `a` as input.

Explanation:

```
a=

    1   1
     0   1
      1   1
      1   1
      1   1
      1   1
       1 1
        #
        #
        #
         #
          #

a > 35                   %convert the matrix to a binary matrix
                         %where there is a number corresponing
                         %element of the binary matrix is 1.

*   *
 *   *
  *   *
  *   *
  *   *
  *   *
   * *

bwlabel(a>35)            %label each connected component.

1   2
 1   2
  1   2
  1   2
  1   2
  1   2
   1 2

B=bwlabel(a>35)(:)==1:2  % a binary `[n ,2]` matrix created
                         % each column related to one of labels

A=(a(:)-48)'             % convert array of characters to array of numbers

A * B                    % matrix multiplication that computes
                         % the sum of numbers under each label

diff(A*B)<0              % check if the left is grater than the right

```

# Answer
> 0 votes
# Batch ~~104~~ 223 bytes

* missed the fact that numbers must be counted on a per charcater basis. Answer updated

```
@Echo off&Set/aa=0&For /f "tokens=1,2" %%1 in (%1)Do (Set c=%%1&Set d=%%2
For %%n in (c d)Do For /l %%i in (0 1 9)Do Call Set %%n=%%%%n:%%i=%%i+%%%%
2>nul Call Set/Aa+=%%c%%0,a-=%%d%%0)
IF %A% GTR 0 (Echo(R)Else echo(L

```
* Input is from file passed as argument - `%1`
* splits each line into two tokens
* inserts a + character between each number \[building a sum\]
* Increments `a` with sum of left token, decrements with sum of right token
* Outputs L or R

---

Sidenote: the test cases in this question dont fail if taking the path of just summing the 1st and 2nd column of each line.

I made use of the follwing test case:

```
 034  060
  1  1
  2 0
   0 2
    #
    #
    #
   #

```

---
Tags: code-golf, ascii-art, decision-problem
---


title: Binary triangle A141727

text:
# Question
Title: Binary triangle A141727
## Challenge

Generate the 2D sequence of bits of A141727. (Allowed I/O methods explained at the bottom.)

```
                  1
                1 0 1
              1 0 0 1 0
            1 0 1 0 1 0 0
          1 0 0 1 1 0 1 1 1
        1 0 1 0 0 0 0 0 1 1 0
      1 0 0 1 0 0 0 0 1 1 1 0 0
    1 0 1 0 1 0 0 0 1 1 0 0 1 1 1
  1 0 0 1 1 0 1 1 0 0 0 1 0 0 1 1 0
1 0 1 0 0 0 0 0 0 1 1 0 1 0 1 1 1 0 0

```

This triangle is generated as follows: starting with a row of single 1, generate the bits row-by-row, from left to right. Each bit is the parity of the sum (in other words, XOR-sum) of the neighboring bits already placed (8-way neighborhood).

```
[1]  initial condition

   1
[1]? ?   only one neighbor being 1, sum is 1

   1
 1[0]?   two 1-neighbors, sum is 0

   1
 1 0[1]  two neighbors (0 and 1), sum is 1

     1
   1 0 1
[1]? ? ? ?  one neighbor, sum 1

     1
   1 0 1
 1[0]? ? ?  three neighbors, sum 0

     1
   1 0 1
 1 0[0]? ?  four neighbors, sum 0

     1
   1 0 1
 1 0 0[1]?  three neighbors, sum 1

     1
   1 0 1
 1 0 0 1[0] two neighbors, sum 0

...

```

default I/O methods apply. In this challenge, you can interpret the sequence as a sequence of individual bits or a sequence of rows of bits, so the following are accepted:

* Given `n` (0- or 1-indexed), output `n`-th bit or `n`-th row
* Given `n` (positive), output first `n` bits or first `n` rows
* Given no input, output the infinite sequence of bits or the sequence of rows (refer to sequence rules for exactly which methods count as infinite output)

Standard rules apply. The shortest code in bytes wins.

# Answer
# Python 2, 52 bytes

Outputs an infinite sequence of rows. As a bonus, it runs extremely slowly.

```
n=1
while 1:print'%o'%n;x=n;n*=64;exec'n^=x;x/=8;'*x

```

Try it online!

If the current row expressed in binary is `n`, the next row will be `a(n) ^ n*4`, where `a(n)` is the prefix xor sum of the bits. `a(n)` is also associated with OEIS A006068.

One annoying little thing about Python is that there is no format string to convert an integer to binary. The next best alternative is octal, which is what the code uses instead.

### Python 2, 54 bytes

Adding 2 more bytes gets the program to a reasonable speed.

```
n=1
while 1:
 print'%o'%n;x=n;n*=64
 while x:n^=x;x/=8

```

Try it online!
> 12 votes

# Answer
# Python 3, 110 bytes

```
def f(n):
	if n<1:return[1]
	k=[1];p=f(n-1)+[0,0]
	for i in range(n*2):k+=[p[i-1]^p[i]^p[i+1]^k[-1]]
	return k

```

Try it online!

A pretty basic and *very* sub-par solution to get things started.
> 3 votes

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

```
f=r=>b=r?f(r-1).map(_=>a[++i]=a[i-2]^b[i-3]^b[i],a=[i=1,0])&&a:[1]

```

Try it online!

Input `r`, output an array for `r`-th row.

---

# JavaScript (Node.js), 48 bytes

```
f=r=>r?(g=a=>a^a/4^b/2^b*4?g(a+1):a)(b=f(r-1)):1

```

Try it online!

Or output `r`-th row as an integer if it is allowed.

---

```
      a
    b c d
  e f g h i
j k l m n o p

n = m xor g xor h xor i
  = (l xor f xor g xor h) xor g xor h xor i
  = l xor f xor i

```
> 3 votes

# Answer
# Wolfram Language (Mathematica), ~~52~~ ~~51~~ 50 bytes

```
Nest[i+=#&/@{##,i=0,0}-{0,##,0}&@@#&,{1},#]~Mod~2&

```

Try it online!

Returns the (0-indexed) \\$n\\$th row.

Uses
\\$\displaystyle A\_{n+1}(m)=A\_n(m-1)\oplus\bigoplus\_{i\le m}A\_n(i)\\$,
where \\$A\_n(m)\\$ is the \\$m\\$th element of row \\$n\\$.

This can be rewritten \\$\displaystyle A\_{n+1}(m)=A\_n(m)\oplus\bigoplus\_{i\le m-2}^{}A\_n(i)\\$.
> 2 votes

# Answer
# Pari/GP, 51 bytes

```
n->for(i=a=1,n,a=a*x+a/(1-x)%x^(2*i+1));Vecrev(a)%2

```

Try it online!

0-indexed.

### Explanation

See each row as a polynomial, starting with the constant term. `a*x` prepends a 0 to the list. `a/(1-x)` takes the cumulative sum of the list. `%x^(2*i+1)` truncates the list to the first `2*i+1` elements.
> 2 votes

# Answer
# Python 3, 98, 92, 88, 77, 76 bytes

```
v=-4**64;W=w=v*v;v+=w;O=1
while[print(hex(O)[2::32])]:O*=w;O^=O//v&W//v;W*=w

```

Try it online!

Old version

Old version

Old version

Old version

Probably not competitive but I think mildly amusing. Takes advantage of Python arbitary size integers to perform cumulative xor. In fact we simply do a cumulative sum over digits using the divide by 9 (or rather base-1) trick and take the base large enough that carry never becomes an issue.

Runs "forever", only it maxes out at around m=2^23. That's not a principal limitation, just me being cheap on integer constants. n=2^127 (rowindex) which I hope is close enough to eternity. **UPDATE** simplified the maths using @dingledooper's formula.
> 2 votes

# Answer
# Charcoal, ~~23~~ 22 bytes

```
ＦＮ«Ｆ⊕⊗ιＩ∨¬ι﹪№ＫＭ1²Ｊ±ⅈ⊕ⅉ

```

Try it online! Link is to verbose version of code. Outputs the first `n` rows as a triangle. Explanation:

```
ＦＮ«

```

For each row:

```
Ｆ⊕⊗ι

```

For each bit in the row...

```
Ｉ∨¬ι﹪№ＫＭ1²

```

... output the parity of the number of adjacent `1`s, except for the very first bit, which is always a `1`.

```
Ｊ±ⅈ⊕ⅉ

```

Jump to the start of the next row of bits.
> 2 votes

# Answer
# Ruby, 67 bytes

```
f=->r,c{c<0||c>r*2?0:r<1?1:([*c-2..c].sum{|x|f[r-1,x]}+f[r,c-1])%2}

```

Try it online!

* computes value at `r` row , `c` column
* Values outside the triangle give 0
> 1 votes

# Answer
# 05AB1E, ~~16~~ ~~14~~ 13 bytes

```
λb=Å»^}2β₁4*^

```

Try it online.

Port of *@dingledooper*'s Python 2 answer, but using binary instead of octal integers, so make sure to upvote him/her as well!
-1 byte thanks to *@CommandMaster*.

**Explanation:**

```
λ           # Start a recursive method,
            # to generate an infinite sequence,
            # starting at a(0)=1 by default
            # Where every next a(n) is calculated as follows:
 b          #  Convert the current implicit a(n-1) to a binary string
  =         #  Output it with trailing newline (without popping)
   Å»       #  Cumulative left-reduce its bits by:
     ^      #   Bitwise-XORing
   }        #  After the cumulative left-reduce,
    2β      #  Convert it from a binary-list to an integer
      ₁     #  Push a(n-1) again
       4*   #  Multiply it by 4
         ^  #  And Bitwise-XOR it to the integer

```
> 1 votes

# Answer
# Raku, 52 bytes

```
1,{(1,{[+^] $^x,|(.[^3-1+$++]:v)}...*)[^(2+$_)]}...*

```

Try it online!

This is an expression for a lazy, infinite sequence of rows.

* `1, { ... } ... *` is the main sequence expression. `1` is the first row, and the bracketed anonymous function generates the next row from the previous row, passed in `$_`.
* `(1, { ... } ... *)[^(2 + $_)]` likewise generates the elements of each row, starting with 1, from the previous element `$^x` and the previous row `$_`. The number of elements in each row is two greater than the size of the previous row: `2 + $_`.
* The numbers to be xor-ed together are `$^x`, the previous element of the current row, and `.[^3 - 1 + $++]:v`, a sliding three-index window across the previous row. The `:v` adverb causes indexes out of the array's range, both positive and negative, to be skipped.
* `+^` is the integer xor operator, and `[+^]` reduces the list of integers that contribute to the current element using that operator.
> 1 votes

# Answer
# Ruby, 47 bytes

```
a=1;loop{puts"%b"%a;(a=2*z=2*a).times{a^=z/=2}}

```

Try it online!
> 1 votes

---
Tags: code-golf, sequence, binary, cellular-automata
---


title: Nega-Zeckendorf representation

text:
# Question
Title: Nega-Zeckendorf representation
## Background

Zeckendorf representation is a numeral system where each digit has the value of Fibonacci numbers (1, 2, 3, 5, 8, 13, ...) and no two consecutive digits can be 1.

Nega-Zeckendorf representation is an extension to this system that allows encoding of all integers, not just positive ones. Its base values are nega-Fibonacci numbers (regular Fibonacci numbers with alternating sign; 1, -1, 2, -3, 5, -8, 13, -21, ..., also derived by extending regular Fibonacci sequence to negative indices).

Donald Knuth proved that every integer has a unique representation as a sum of non-consecutive nega-Fibonacci numbers (0 is an empty sum). Therefore, the corresponding nega-Zeckendorf representation is unique for every integer. 0 is represented as an empty list of digits.

## Challenge

Given an integer (which can be positive, zero, or negative), compute its nega-Zeckendorf representation.

The output must consist of zeros and ones, either as numbers or characters. Output in either least-significant first or most-significant first order is acceptable (the latter is used in the test cases).

Standard rules apply. The shortest code in bytes wins.

## Test cases

```
-10 = 101001
-9 = 100010
-8 = 100000
-7 = 100001
-6 = 100100
-5 = 100101
-4 = 1010
-3 = 1000
-2 = 1001
-1 = 10
0 = (empty)
1 = 1
2 = 100
3 = 101
4 = 10010
5 = 10000
6 = 10001
7 = 10100
8 = 10101
9 = 1001010
10 = 1001000

-11 = (-8) + (-3) = 101000
12 = 13 + (-1) = 1000010
24 = 34 + (-8) + (-3) + 1 = 100101001
-43 = (-55) + 13 + (-1) = 1001000010
(c.f. negafibonacci: 1, -1, 2, -3, 5, -8, 13, -21, 34, -55, ...)

```

# Answer
> 4 votes
# Jelly, 17 bytes

```
0BUJNÆḞḋƲ=ʋ1#ḢȯRB

```

Try it online!

+3 bytes (`ḢȯR`) to output `[]` instead of `0`

I'm sure this can be beaten by some clever mathematical trick; this just counts up in binary, converts from nega-Zeckendorf and stops when it equals the input

## How it works

```
0BUJNÆḞḋƲ=ʋ1#ḢȯRB - Main link. Takes n on the left
          ʋ       - Group the previous 4 links into a dyad f(k, n):
 B                -   Convert k to binary
  U               -   Reverse the bits
        Ʋ         -   Group the previous 4 links into a monad g(bin(k)):
   J              -     Indices
    N             -     Negate
     ÆḞ           -     nth Fibonacci number
       ḋ          -     Dot product with bin(k)
         =        -   Does g(bin(k)) equal n?
0          1#     - Find the first integer k such that f(k, n) is true
             Ḣ    - Extract k
              ȯR  - If k = 0, replace with []
                B - Convert to binary

```

# Answer
> 3 votes
# Python 3, 89, 87 bytes

```
f=lambda n,a=-1,b=1,i=0:0<b*n<=b*b-i%2and f"1{f(n+a):0>{i}}"or n and f(n,b,a-b,i+1)or""

```

Try it online!

Old version

Uses the fact that each negative term in the negbonacci equals minus the sum of all preceding positive terms and, similarly, each positive term is 1 minus the sum of all preceding negative terms. This is used to set up a direct recursion.

Test bed "borrowed" from @Noodle9.

# Answer
> 2 votes
# 05AB1E, ~~19~~ 18 bytes

```
∞bõš.ΔRSƶÅfāÉ·<*OQ

```

Try it online or verify all test cases.

**Explanation:**

```
∞                  # Push an infinite positive list: [1,2,3,4,5,...]
 b                 # Convert each to a binary string
  õš               # Prepend an empty string (for edge case 0)
    .Δ             # Find the first value which is truthy for:
      R            #  Reverse the binary string
       S           #  Convert it to a list of bits
        ƶ          #  Multiply each by its 1-based index
         Åf        #  Get the n'th Fibonacci number for each
           ā       #  Push a list in the range [1,length] (without popping)
            É      #  Check for each whether it's odd: [1,0,1,0,1,...]
             ·     #  Double each: [2,0,2,0,2,...]
              <    #  Subtract each by 1: [1,-1,1,-1,1,...]
               *   #  Multiply it to the Fibonacci numbers at the same positions
                O  #  Sum them together
                 Q #  And check if it's equal to the (implicit) input-integer
                   # (after which the found result is output implicitly)

```

# Answer
> 2 votes
# JavaScript (ES6), 74 bytes

Output format: least-significant first.

```
f=(n,k)=>(g=(k,a,b)=>k&&k%2*a+g(k>>1,b-a,a,s+=k%2))(k,1,s='')^n?f(n,-~k):s

```

Try it online!

# Answer
> 2 votes
# Ruby, ~~137 129~~ 119 bytes

```
n=->x{x<2?x:n[x-2]-n[x-1]}
z=->x,u=0{i,y=0,u.to_s(2)
y.bytes.sum{|b|b%2*n[y.size+i-=1]}!=x||y=~/11+/?z[x,u+1]:y[0..-2]}

```

Try it online!

* Saved 8 Bytes thanks to @ovs suggestion to use =~(find) instead of match
* probably not the golfiest but at least I solved this complicated task.

n=-\>x{..} # nega-fib(x)
z=-\>x,u=0{ # starts from 0
y=u.to\_s 2 # binary representation

we convert y to an array of nega+fibs or 0. If that sum is ==x and if no 1's are next to each other we return y with last bit removed, else we try next u

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

```
t=>(h=i=>i&i/2|t-(g=(i,p=0,q=1)=>i&&g(i>>1,q,p-q)+i%2*q)(i)?h(++i):i)``.toString(2)

```

Try it online!

# Answer
> 1 votes
# MathGolf, 20 bytes

```
╘ïâ_h╒m*fh╒¥∞(m*Σk=▼

```

Outputs in least-significant first order (so the test cases in reversed).

Try it online.

**Explanation:**

```
                   ▼ # Do-while false with pop:
╘                    #  Discard everything from the stack
 ï                   #  Push the 0-based loop-index
  â                  #  Convert it to a binary-list
   _                 #  Duplicate it
    h                #  Push the length of this list (without popping)
     ╒               #  Pop and push a list in the range [1,length]
      m*             #  Multiply the integers at the same positions together
        f            #  Get the n'th Fibonacci number for each
         h╒          #  Push a [1,length] ranged list again (without popping)
           ¥         #  Modulo-2 on each
            ∞        #  Double each
             (       #  Subtract each by 1
              m*     #  Multiply the integers at the same positions again
                Σ    #  Sum this list together
                 k=  #  Check whether it's equal to the input-integer
                     # (after which the entire stack is output implicitly as result,
                     # which is the binary-list we've duplicated)

```

# Answer
> 1 votes
# Charcoal, 60 bytes

```
ＮθＦ²⊞υ±ιＷ∧θ⁼›θ§υ±³›θ§υ±¹⊞υ↨…⮌υ²±¹Ｗ›Ｌυ²¿⁼›θ§υ±³›θ⊟υ0«1≧⁺§υ±¹θ

```

Try it online! Link is to verbose version of code. Based on the algorithm in the linked Stack Overflow question. Explanation:

```
Ｎθ

```

Input the integer.

```
Ｆ²⊞υ±ι

```

Start building up the negated nega-Fibonacci sequence with `0, -1`.

```
Ｗ∧θ⁼›θ§υ±³›θ§υ±¹

```

Until enough terms have been generated to calculate the nega-Zeckendorf representation...

```
⊞υ↨…⮌υ²±¹

```

Push the difference between the last two terms to the sequence.

```
Ｗ›Ｌυ²

```

While sufficient terms of the sequence remain:

```
¿⁼›θ§υ±³›θ⊟υ0

```

If the integer does not fall between the third last and the last term (removing the last term as we go), then output a `0`.

```
«1≧⁺§υ±¹θ

```

Otherwise output a `1` and add the (originally second) last term to the integer, which brings it closer to zero (since it has the opposite sign; see the linked question to explain why this works).

# Answer
> 1 votes
# Python 3, <sup>~~125~~ ~~97~~</sup> 93 bytes

```
f=lambda n,k=0:n-g(k)and f(n,k+1)or bin(k)[2:-1]
g=lambda k,a=0,b=1:k and k%2*a+g(k>>1,b-a,a)

```

Try it online!

*Port of Arnauld's JavaScript answer.*

Outputs most-significant first.

# Answer
> 1 votes
# Husk, 19 bytes

```
ḟö=⁰ṁ_z*z*İ_İf↔ΘmḋN

```

Try it online!

```
                mḋ  # get the binary digits of each number in
                  N # the infinite list of integers
               Θ    # and prepend an empty list of no digits;
ḟö                  # now, return the first set that satisfies:
              ↔     # the digits reversed
      z*            # zipped by multiplication with
        z*İ_İf      # the negative negafibonacci sequence
                    # (=fibonacci sequence zipped by multiplication
                    # with powers of -1)
    ṁ_              # all negated and summed
  =⁰                # is equal to the input

```

# Answer
> 1 votes
# Excel, 240 bytes

```
=LET(q,SEQUENCE(1,18),d,SEQUENCE(2^18-1),x,DEC2BIN(INT(d/2^9),9)&DEC2BIN(MOD(d,2^9),9),y,FILTER(x,ISERROR(FIND(11,x))),IF(A1,XLOOKUP(A1,MMULT(MID(y,q,1)*1,TRANSPOSE(-1*ROUND((-((1+5^0.5)/2)^(19-q))/5^0.5,0))),REPLACE(y,1,FIND(1,y)-1,)),""))

```

## Explanation

```
=LET(q,SEQUENCE(1,18),                              # q = [1..18] horizontal
     d,SEQUENCE(2^18-1),                            # d = [1..2^18-1] vertical
     x,DEC2BIN(INT(d/2^9),9)&DEC2BIN(MOD(d,2^9),9), # x = 18 digit binary representations of d
     y,FILTER(x,ISERROR(FIND(11,x))),               # y = x with all items containing "11" removed
IF(A1,                                    # if A1 <> 0 then
      XLOOKUP(A1,                         #   match A1 to
              MMULT(                      #   the matrix multiplication of
                MID(y,q,1)*1,             #   the digits of y times
                TRANSPOSE(-1*ROUND((-((1+5^0.5)/2)^(19-q))/5^0.5,0))),
                                          #   the first 18 digits if the nega-Fibonacci series
              REPLACE(y,1,FIND(1,y)-1,)), #   return the corresponding y with leading zeros removed
      ""))                                # else ""

```

Lists all valid binary representations upto 18 digits and finds the match to the number in A1. Works for \[-4180 .. 2584\].

# Answer
> 0 votes
# Python 3, 111 bytes

```
f=lambda x:x<0 or f(x-2)-f(x-1)
g=lambda a,n=0:a-sum(f(i)for i in range(n)if n>>i&1)and g(a,n+1)or bin(n)[2:-1]

```

Try it online!

---
Tags: code-golf, integer, binary, fibonacci, encoding
---


title: Tips for restricted source in Python

text:
# Question
Title: Tips for restricted source in Python
Just like , pushes one to exploit quirks and hidden features of the Python language. We already have a place to collect all these for , those for remain transmitted by word of mouth or hidden deep within the python documentation.

So today I would like to ask you what are some for solving challenges in Python?

Please only include 1 tip per answer.

---

## What makes a good tip here?

There are a couple of criteria I think a good tip should have:

1. It should be (somewhat) non obvious.

Similar to the tips it should be something that someone who has golfed in python a bit and read the tips page would not immediately think of. For example "Replace `a + b` with `a+b` to avoid using spaces", is obvious to any golfer, since it is already a way to make your code shorter. Thus it is not a good tip here.
2. It should not be too specific.

Since there are many different types of source restrictions, answers here should be at least somewhat applicable to multiple source restrictions, or one common source restriction. For example tips of the form **How to X without using character(s) Y** are generally useful since banned characters is a common source restriction. The thing your tip helps to do should also be somewhat general. For example tips of the form **How to create numbers with X restriction** are useful since many programs utilize numbers regardless of the challenge. Tips of the form **How to implement Shor's algorithm with X restriction** are basically just answers to a challenge you just invented and not very helpful to people solving other challenges.

# Answer
# Avoid "normal" letters

Identifiers are normalized by the Python 3 parser. This implies that cursive (Unicode) letters such as  are interpreted as their ASCII-compliant equivalents `abcDEF`. So the following code works (as was exploited here):

```
=123
()

```

Python versions in which this behaviour is confirmed:

* Works: 3.4, 3.5, 3.6, 3.7, 3.8
* Doesn't work: 2.7

### Example source restriction:

* *Use no characters `abc···xyz`, `ABC···XYZ`.*
> 32 votes

# Answer
# Avoid Numbers with Booleans

When performing arithmetic operations on Booleans, Python treats them as if they are the numbers 1 and 0. So for example

```
>>> True+False
1

```

You can make all positive numbers by just adding booleans to each other.

You can also substitute the booleans for boolean values, for example `[]>[]` is `False` and `[[]]>[]` is `True` so

```
>>> ([]>[])+([[]]>[])
1

```

In some cases, Booleans can even be used in place of a number without having to using arithmetic to cast it. For example, you can index into lists/tuples/strings with Booleans, so:

```
>>> ['a','b'][True]
'b'

```

---

### Example source restrictions:

* *Use no digits (`0123456789`)*
* *Use no alphanumeric characters*
* *Use no `if` conditions*
> 25 votes

# Answer
## Avoid Parens with List indexing

Parentheses are super useful for creating the correct operator precedence so it is a bummer when they are banned. However if `[]` are still available we can use them instead. Simply replace

```
(...)

```

with

```
[...][0]

```

This creates a list and indexes it to get its only element. The list causes the inside to be evaluated first solving your precedence issue.

The example above uses the characters `[]0` to do this however there are other third characters that can be used in this case if need be.

* Using characters `[]>` write `[...][[]>[]]`
* Using characters `[]<` write `[...][[]<[]]`
* Using characters `[]=` write `[...][[[]]==[]]`

---

### Example source restriction:

* *Use no parentheses*
> 22 votes

# Answer
## Function calls without parentheses

We can avoid using parentheses for operator precedence using list indexing, but parentheses are still very useful for calling functions.

List indexing can be used here as well to solve the issue, however it is a lot more complex so I've made it its own answer.

In order to call a function we start by making a new class which has it's indexing defined to be the function. So if we want to call `print` this might look like

```
class c:__class_getitem__=print

```

Then to call the function we simply index it with the argument we want. For example to print `"Hello World"` we do

```
c["Hello World"]

```

This has a few unfortunate short comings:

* It can only be used to call functions with one parameter.
* There are quite a few characters that are required to pull this trick off. ( `:=[]_acegilmst`)
* It uses up a lot of characters if you are doing

But sometimes it might be your only option.

---

## Example source restriction:

* Use no parentheses

Here's an example of it being used.
> 20 votes

# Answer
# Use `<<` and `|` to generate constant without `+`

Fun fact: You can get any positive constant only using `[]<|`. The way to go is left-shifting a boolean. `[]<[[]]` is 1, so `[]<[[]]<<[]<[[]]` should left-shift 1 with 1, which is 2.

Does it work?

```
>>> []<[[]]<<[]<[[]]

Traceback (most recent call last):
  File "<pyshell#29>", line 1, in <module>
    []<[[]]<<[]<[[]]
TypeError: unsupported operand type(s) for <<: 'list' and 'list'

```

...No.

The precedence is wrong. Luckily, we can resolve this with "Ad Hoc Garf Hunter Parenthesis(TM)":

```
>>> [[]<[[]]][[]<[]]<<[[]<[[]]][[]<[]]
2

```

Aha!

To get numbers other than power of two, you still need `+`... or not. `|` or `[bitwise or][[]<[]]`* will do that for you.

```
>>> [[]<[[]]][[]<[]]<<[[]<[[]]][[]<[]]<<[[]<[[]]][[]<[]]<<[[]<[[]]][[]<[]]|[[]<[[]]][[]<[]]<<[[]<[[]]][[]<[]]
10

```

To get negative numbers without `-`, you may want to use `~`.

* That part was enclosed in an "Ad Hoc Garf Hunter Parenthesis(TM)" to indicate precedence.
> 18 votes

# Answer
## Access methods and built-in functions through `__dict__`

Classes contain a `__dict__` attribute, which maps their method names to the methods themselves. If you can't type a method name directly, you can get them from this `__dict__`.

For example, let's say you need to append something to a list, but you can't use the characters `p,n,+`, etc. Since `append()` is the 26th method in a list's `__dict__`, you can call the method like this:

```
a = [1,2,3]
list(a.__class__.__dict__.values())[26](a, 4)
print(a)  # prints [1,2,3,4]

```

Try it online!

This can also be used with `__builtins__` to access built-in functions. Even if someone bans the character `x` to block the `exec` function, you can still call `exec` like this:

```
list(__builtins__.__dict__.values())[20]("print('Hello, World!')")

```

Try it online!

This works best in more recent versions of Python that guarantee dictionary order, but there are probably other ways to use this in older versions, like iterating through the `__dict__` with a regex or substring match.
> 16 votes

# Answer
## Use `ord()` or binary strings to avoid digits

Most integers in the ranges `[32..47]` and `[58..126]` can easily be obtained from the ASCII code of a single character with:

```
x=ord('A')

# or, if parentheses are not allowed:

y=b'A'[False]

```

Try it online!

Larger integers can also be produced using from their unicode points:

```
>>>print (ord("±"))
177
>>> print (ord("π"))
960

```

If you can use an assignment, or you need to avoid brackets you can unpack the values, instead. Note that this will not work inline, even with the walrus operator.

```
x,*_=b'A'
y,_=b'A_'

```

Try it online!

### Example source restrictions:

* *Use no digits*
* *Use no digits / no parentheses / no brackets*
> 14 votes

# Answer
## Alternatives to `eval` and `exec`

Do you need to treat a string as code, but you can't use `eval` or `exec`? There are at least three other ways to execute a string:

### 1) timeit.timeit

```
import timeit
_=timeit.timeit("print('Hello!')", number=1)

```

Try it online!

`timeit` runs `number` times and returns an average of how long it took. By default it runs 1 million times, so you'll almost certainly want to set `number=1` or raise an exception to break out (e.g. `"print('hello'); 0/0"`).

Thanks to Ethan White for showing me this approach.

### 2) os.system

```
import os
c='echo "import math;print(math.pi)" | python3'
_=os.system(c)  # Prints 3.141592653589793

```

Try it online!

`os.system` runs an arbitrary shell command and returns its exit code. If you just need to print something, you can stick to `echo`, but you can also execute arbitrary code by calling `python3` itself.

### 3) code.InteractiveInterpreter().runcode

```
from code import InteractiveInterpreter as I
i = I()
i.runcode("print('Hello!')")

```

Try it online!

`code` is specifically designed for read-eval-print loops, and even though it's a bit clunky, this is the most powerful of the three. `timeit` and `os.system` isolate their processes, but an `InteractiveInterpreter` can use global state instead of its own:

```
from code import InteractiveInterpreter as I
a = 64
i = I(globals())
i.runcode("import math; a=math.log2(a)")
print(a)        # a = 6.0
print(math.pi)  # math is imported globally

```

Try it online!
> 12 votes

# Answer
## Use `--` to avoid +

E.g to do `a+b`:

```
a--b

```

**Example source restriction:**

* Avoid the `+` operator
> 11 votes

# Answer
## Encode restricted characters and use `exec()`

Like most interpreted languages, Python can run a string as code with `eval` and `exec`. `eval` is more limited, but `exec` can handle imports, function definitions, loops, exceptions, etc.

When combined with some of the other tips about encoding characters, this allows you to write your code normally:

```
import sys

def f(i):
 return 1 if i==1 else i*f(i-1)

i=int(sys.argv[1])
print(f(i))

```

Then pick an encoding and pass the encoded version to `exec`:

```
exec('\x69\x6d\x70\x6f\x72\x74\x20\x73\x79\x73\x0a\x0a\x64\x65\x66\x20\x66\x28\x69\x29\x3a\x0a\x20\x72\x65\x74\x75\x72\x6e\x20\x31\x20\x69\x66\x20\x69\x3d\x3d\x31\x20\x65\x6c\x73\x65\x20\x69\x2a\x66\x28\x69\x2d\x31\x29\x0a\x0a\x69\x3d\x69\x6e\x74\x28\x73\x79\x73\x2e\x61\x72\x67\x76\x5b\x31\x5d\x29\x0a\x70\x72\x69\x6e\x74\x28\x66\x28\x69\x29\x29\x0a')

```

Try it online!
> 5 votes

# Answer
## Replace operators with dunder methods

Most python operators are syntactic sugar for specific method calls (often called "magic methods" or "dunder methods", with "dunder" being short for "double underscore"). For example, `+` calls `__add__()`, `==` calls `__eq__()`, and `<<` calls `__lshift__()`

If operators are restricted, you can call these methods directly:

```
a = 1
print(a.__add__(1).__eq__(2))  # True

```

Try it online!

For assignment, you can use `__setitem__` on the `locals()` or `globals()` dictionaries, whether or not the variable already exists:

```
a = 1
locals().__setitem__('a',2)
locals().__setitem__('b',2)
print(a.__add__(b).__eq__(4))  # True

```

Try it online!

Note that you'll have to add parentheses around numbers to avoid a syntax error. `4.__eq__(4)` won't work, but `(4).__eq__(4)` will.
> 5 votes

# Answer
# Use `__import__("module")` instead of `import module`

To avoid whitespace in the `import statement`, or to dynamically construct the name of the module to import as a string (e.g. `"RANDOM".lower()` if you can't use a lowercase `d`). Not likely that useful because you don't often need the standard library, and you still need to be able to use `_`, `i`, `m`, `p`, `o`, `r`, `t`, `(`, and `)`.

Edit: or as Ad Hoc Garf Hunter suggests, you can use `import<tab>module` (with a literal tab character)!
> 5 votes

# Answer
# File Encodings

You can set a custom encoding for your Python source file in a comment at the start. This includes various Unicode things, but also text transforms such as `unicode_escape` and `punycode`, which can be used for restricted source!

Here's an example:

```
# encoding: unicode_escape
print(\x22Hello, World!\x22)
```

Attempt This Online!

Here's the exact specification of an encoding line, from the Python documentation:

> If a comment in the first or second line of the Python script matches the regular expression `coding[=:]\s*([-\w.]+)`, this comment is processed as an encoding declaration; the first group of this expression names the encoding of the source code file

So, for , the best definition is therefore `#coding:unicode_escape`.

This works not only at the file level, but also with `exec` and `eval` *if you pass them a byte string*:

```
print(eval(rb'''# encoding: unicode_escape
\x22Hello, World!\x22'''))
```

Attempt This Online!

Not as useful there though because you can generally just pass a constructed string.
> 5 votes

# Answer
## Use `*` to avoid `/`

`x**-1` is equivalent to `1/x`. So to do `y/x` you can do `x**-1*y`.

If you desperately want to get rid of the `-1`, you can check out Ad Hoc Garf Hunter's other tip.

## Example source restriction:

* Avoid using the `/` character
> 4 votes

# Answer
This is likely not relevant to the question but it's very silly.

This is (maybe) a more portable way of water\_ghost's convoluted method of accessing builtin methods.
The index is 26 only on CPython 3. This very small and extremely easy to understand modification allows it to run on CPython 2.7, CPython 3, PyPy 2.7 and PyPy 3 (tested on Debian 10 amd64)

```
a = [1, 2, 3]
list(a.__class__.__dict__.values())[[14,13,26,25][sum(map(ord,{__import__("sys").version[0],__import__("platform").python_implementation()[0]}))&3]](a, 4)
print(a)

```

---

The correct indices (on my system) are

```
CPython 2.7    13
CPython 3      26
PyPy 2.7       26
PyPy 3         25

```

And by a lucky coincidence `('C'+'2')%4 == 1`, `('C'+'3')%4 == 2`, `('P'+'2') == 2` and `('P'+'3') == 3`. The value 14 is there to trick you into thinking there is a pattern.
> 4 votes

# Answer
## How to create characters just with numbers, quotes and backslashes

Strings can be composed with `\ooo` where `ooo` is the octal value of the character.

Eg:

```
'\141'=='a'

```

You can also use hex, at the expense of an `x` (and `a`,`b`,`c`,`d`,`e` and/or `f` if they're used):

```
'\x61'=='a'

```

And unicode at the expense of a `u` (two pre-Python 3) and hex characters if they're used:

```
'\u2713'=='✓'

```
> 3 votes

# Answer
# `__debug__` is True

Pretty self-expl... expl...

```
>>> __debug__
True

```
> 3 votes

---
Tags: restricted-source, tips, python
---