title: Regex golf and ccTLDs, hooray!

text:
# Question
Title: Regex golf and ccTLDs, hooray!
Write a regex that only matches valid country code top level domains (ccTLDs). Your regex must match both the domains with the dot and without the dot (it must match tv and .tv). Any domain that is not a ccTLD or does not exist (e.g. .info or .jobs or .xz) must not be matched.

Use Perl, POSIX, PCRE or Python.

For reference, this is the full list of ccTLDs, as of challenge creation:

.ac .ad .ae .af .ag .ai .al .am .ao .aq .ar .as .at .au .aw .ax .az .ba .bb .bd .be .bf .bg .bh .bi .bj .bm .bn .bo .br .bs .bt .bw .by .bz .ca .cc .cd .cf .cg .ch .ci .ck .cl .cm .cn .co .cr .cu .cv .cw .cx .cy .cz .de .dj .dk .dm .do .dz .ec .ee .eg .er .es .et .eu .fi .fj .fk .fm .fo .fr .ga .gd .ge .gf .gg .gh .gi .gl .gm .gn .gp .gq .gr .gs .gt .gu .gw .gy .hk .hm .hn .hr .ht .hu .id .ie .il .im .in .io .iq .ir .is .it .je .jm .jo .jp .ke .kg .kh .ki .km .kn .kp .kr .kw .ky .kz .la .lb .lc .li .lk .lr .ls .lt .lu .lv .ly .ma .mc .md .me .mg .mh .mk .ml .mm .mn .mo .mp .mq .mr .ms .mt .mu .mv .mw .mx .my .mz .na .nc .ne .nf .ng .ni .nl .no .np .nr .nu .nz .om .pa .pe .pf .pg .ph .pk .pl .pm .pn .pr .ps .pt .pw .py .qa .re .ro .rs .ru .rw .sa .sb .sc .sd .se .sg .sh .si .sk .sl .sm .sn .so .sr .ss .st .sv .sx .sy .sz .tc .td .tf .tg .th .tj .tk .tl .tm .tn .to .tr .tt .tv .tw .tz .ua .ug .uk .us .uy .uz .va .vc .ve .vg .vi .vn .vu .wf .ws .ye .yt .za .zm .zw -- open for registration

.an .bl .bq .bv .eh .gb .mf .sj .su .tp .um -- not open (still must be matched)

^ and $ anchors are not needed.

# Answer
> 4 votes
## 275 bytes

```
\.?([cmst][cdghk-orvz]|[agim][delmq-t]|[dft][jkmo]|[acms]x|[bcgkmp][ghmnrwy]|[psu][agksy]|[aen][cegru]|[abcn][fioz]|l[abcikr-vy]|[bdjkprsvy]e|[bcgmnqvz]a|[behpsty]t|[cghmrv]u|[fgksv]i|[gjkmn]p|b[bdjs]|h[kmnr]|[gptw]f|[artz]w|v[cgn]|[joz]m|[ijr]o|[erw]s|[dku]z|[np]l|fr|in|sb)

```

(277 bytes including `^$`.) A Python program was used to autogenerate part of this regular expression. Here is the first version of the program:

```
def makeregex(list):
  if len(list) == 1:
    return alpha[list[0]]
  regex = "["
  j = list[0]
  while j < 26:
    if j in list:
      if j + 1 in list and j + 2 in list and j + 3 in list:
        regex += alpha[j] + "-"
        while j + 1 in list:
          j += 1
      regex += alpha[j]
    j += 1
  return regex + "]"

def perform(rows, cols):
  replaced = '|'.join([alpha[j] + alpha[k] for j in rows for k in cols if array[j][k] > 0])
  regex = makeregex(rows) + makeregex(cols)
  print regex, 'replaces', replaced, 'saving', len(replaced) - len(regex), 'bytes'
  for j in rows:
    for k in cols:
      if (array[j][k]):
        array[j][k] = -1
      else:
        raise Exception("filling illegal entry")

all = ['ac', 'ad', 'ae', 'af', 'ag', 'ai', 'al', 'am', 'ao', 'aq', 'ar', 'as',
       'at', 'au', 'aw', 'ax', 'az', 'ba', 'bb', 'bd', 'be', 'bf', 'bg', 'bh',
       'bi', 'bj', 'bm', 'bn', 'bo', 'br', 'bs', 'bt', 'bw', 'by', 'bz', 'ca',
       'cc', 'cd', 'cf', 'cg', 'ch', 'ci', 'ck', 'cl', 'cm', 'cn', 'co', 'cr',
       'cu', 'cv', 'cw', 'cx', 'cy', 'cz', 'de', 'dj', 'dk', 'dm', 'do', 'dz',
       'ec', 'ee', 'eg', 'er', 'es', 'et', 'eu', 'fi', 'fj', 'fk', 'fm', 'fo',
       'fr', 'ga', 'gd', 'ge', 'gf', 'gg', 'gh', 'gi', 'gl', 'gm', 'gn', 'gp',
       'gq', 'gr', 'gs', 'gt', 'gu', 'gw', 'gy', 'hk', 'hm', 'hn', 'hr', 'ht',
       'hu', 'id', 'ie', 'il', 'im', 'in', 'io', 'iq', 'ir', 'is', 'it', 'je',
       'jm', 'jo', 'jp', 'ke', 'kg', 'kh', 'ki', 'km', 'kn', 'kp', 'kr', 'kw',
       'ky', 'kz', 'la', 'lb', 'lc', 'li', 'lk', 'lr', 'ls', 'lt', 'lu', 'lv',
       'ly', 'ma', 'mc', 'md', 'me', 'mg', 'mh', 'mk', 'ml', 'mm', 'mn', 'mo',
       'mp', 'mq', 'mr', 'ms', 'mt', 'mu', 'mv', 'mw', 'mx', 'my', 'mz', 'na',
       'nc', 'ne', 'nf', 'ng', 'ni', 'nl', 'no', 'np', 'nr', 'nu', 'nz', 'om',
       'pa', 'pe', 'pf', 'pg', 'ph', 'pk', 'pl', 'pm', 'pn', 'pr', 'ps', 'pt',
       'pw', 'py', 'qa', 're', 'ro', 'rs', 'ru', 'rw', 'sa', 'sb', 'sc', 'sd',
       'se', 'sg', 'sh', 'si', 'sk', 'sl', 'sm', 'sn', 'so', 'sr', 'ss', 'st',
       'sv', 'sx', 'sy', 'sz', 'tc', 'td', 'tf', 'tg', 'th', 'tj', 'tk', 'tl',
       'tm', 'tn', 'to', 'tr', 'tt', 'tv', 'tw', 'tz', 'ua', 'ug', 'uk', 'us',
       'uy', 'uz', 'va', 'vc', 've', 'vg', 'vi', 'vn', 'vu', 'wf', 'ws', 'ye',
       'yt', 'za', 'zm', 'zw']
alpha = 'abcdefghijklmnopqrstuvwxyz'
array = [[alpha[i] + alpha[j] in all for j in range(26)] for i in range(26)]

#perform([2, 12, 18, 19], [2, 3, 6, 7, 10, 11, 12, 13, 14, 17, 21, 25])
#perform([0, 6, 8, 12], [3, 4, 11, 12, 16, 17, 18, 19])
#perform([3, 5, 19], [9, 10, 12, 14])
#perform([0, 2, 12, 18], [23])

while max(max(row) for row in array) > 0:
  best = 0
  i = 1
  while i < 1 << 26:
    row = [-1 for j in range(26)]
    for j in range(26):
      if (i & 1 << j):
        for k in range(26):
          if array[j][k] == 0:
            row[k] = 0
          elif array[j][k] == 1 and row[k]:
            row[k] = max(row[k], 0) + 1
        if max(row) < 1:
          break;
    if max(row) > 0:
      total = 3 * sum(max(j, 0) for j in row)
      if total > best:
        rows = [j for j in range(26) if i & 1 << j]
        cols = [j for j in range(26) if row[j] > 0]
        total -= len(makeregex(rows)) + len(makeregex(cols)) + 1
        if total > best:
          best = total
          bestrows = rows
          bestcols = cols
      i += 1
    else:
      i += i & -i
  if best:
    perform(bestrows, bestcols)
  else:
    print '|'.join([alpha[j] + alpha[k] for j in range(26) for k in range(26) if array[j][k] > 0])
    break

```

This 282-byte regex results from its output:

```
\.?([bgmps][aeghmnrsty]|[cmst][cdghk-orvz]|[acn][cfgiloruz]|[agim][delmq-t]|[bck][ghimnrwyz]|[elm][cr-u]|[dft][jkmo]|[agpt][fltw]|[gnv][aegiu]|[lpu][aksy]|[gjkm][emp]|h[kmnrtu]|b[bdfjo]|r[eosuw]|[ls][biv]|[acms]x|[cmz][amw]|[dey]e|dz|eg|fi|fr|in|io|jo|np|om|qa|ug|uz|vc|vn|wf|ws|yt)

```

The program can also be seeded by adding calls to `perform`, so I tried seeding it with `[cmst][cdghk-orvz]|[agim][delmq-t]|[dft][jkmo]|[acms]x` but that just resulted in a rearranged regex. Obviously this wasn't good enough. The problem seemed to be that I was comparing the performance against a simple alternation. I therefore developed a slower but more accurate scoring function, which works by assuming that all of the remaining matches should be either `x[yz]` or `[xy]z` alternations, generating the largest alternations first, and compares the result with and without the trial regex.

```
def makeregex(list):
  if len(list) == 1:
    return alpha[list[0]]
  regex = "["
  j = list[0]
  while j < 26:
    if j in list:
      if j + 1 in list and j + 2 in list and j + 3 in list:
        regex += alpha[j] + "-"
        while j + 1 in list:
          j += 1
      regex += alpha[j]
    j += 1
  return regex + "]"

def simple(array):
  unused = [[j > 0 for j in row] for row in array]
  regex = ""
  while max(max(row) for row in unused):
    rowcount = [sum(row) for row in unused]
    colcount = [sum(col) for col in zip(*unused)]
    if max(colcount) > max(rowcount):
      colindex = colcount.index(max(colcount))
      col = zip(*unused)[colindex]
      regex += "|" + makeregex([j for j in range(26) if col[j]]) + alpha[colindex]
      for j in range(26):
        unused[j][colindex] = 0
    else:
      rowindex = rowcount.index(max(rowcount))
      row = unused[rowindex]
      regex += "|" + alpha[rowindex] + makeregex([j for j in range(26) if row[j]])
      unused[rowindex] = [0 for j in range(26)]
  return regex

def perform(rows, cols):
  previous = simple(array)[1:].split('|')
  for j in rows:
    for k in cols:
      if (array[j][k]):
        array[j][k] = -1
      else:
        raise Exception("filling illegal entry")
  regex = (makeregex(rows) + makeregex(cols) + simple(array)).split('|')
  replaced = '|'.join(j for j in previous if not j in regex)
  regex = '|'.join(j for j in regex if not j in previous)
  print regex, 'replaces', replaced, 'saving', len(replaced) - len(regex), 'bytes'

all = ['ac', 'ad', 'ae', 'af', 'ag', 'ai', 'al', 'am', 'ao', 'aq', 'ar', 'as',
       'at', 'au', 'aw', 'ax', 'az', 'ba', 'bb', 'bd', 'be', 'bf', 'bg', 'bh',
       'bi', 'bj', 'bm', 'bn', 'bo', 'br', 'bs', 'bt', 'bw', 'by', 'bz', 'ca',
       'cc', 'cd', 'cf', 'cg', 'ch', 'ci', 'ck', 'cl', 'cm', 'cn', 'co', 'cr',
       'cu', 'cv', 'cw', 'cx', 'cy', 'cz', 'de', 'dj', 'dk', 'dm', 'do', 'dz',
       'ec', 'ee', 'eg', 'er', 'es', 'et', 'eu', 'fi', 'fj', 'fk', 'fm', 'fo',
       'fr', 'ga', 'gd', 'ge', 'gf', 'gg', 'gh', 'gi', 'gl', 'gm', 'gn', 'gp',
       'gq', 'gr', 'gs', 'gt', 'gu', 'gw', 'gy', 'hk', 'hm', 'hn', 'hr', 'ht',
       'hu', 'id', 'ie', 'il', 'im', 'in', 'io', 'iq', 'ir', 'is', 'it', 'je',
       'jm', 'jo', 'jp', 'ke', 'kg', 'kh', 'ki', 'km', 'kn', 'kp', 'kr', 'kw',
       'ky', 'kz', 'la', 'lb', 'lc', 'li', 'lk', 'lr', 'ls', 'lt', 'lu', 'lv',
       'ly', 'ma', 'mc', 'md', 'me', 'mg', 'mh', 'mk', 'ml', 'mm', 'mn', 'mo',
       'mp', 'mq', 'mr', 'ms', 'mt', 'mu', 'mv', 'mw', 'mx', 'my', 'mz', 'na',
       'nc', 'ne', 'nf', 'ng', 'ni', 'nl', 'no', 'np', 'nr', 'nu', 'nz', 'om',
       'pa', 'pe', 'pf', 'pg', 'ph', 'pk', 'pl', 'pm', 'pn', 'pr', 'ps', 'pt',
       'pw', 'py', 'qa', 're', 'ro', 'rs', 'ru', 'rw', 'sa', 'sb', 'sc', 'sd',
       'se', 'sg', 'sh', 'si', 'sk', 'sl', 'sm', 'sn', 'so', 'sr', 'ss', 'st',
       'sv', 'sx', 'sy', 'sz', 'tc', 'td', 'tf', 'tg', 'th', 'tj', 'tk', 'tl',
       'tm', 'tn', 'to', 'tr', 'tt', 'tv', 'tw', 'tz', 'ua', 'ug', 'uk', 'us',
       'uy', 'uz', 'va', 'vc', 've', 'vg', 'vi', 'vn', 'vu', 'wf', 'ws', 'ye',
       'yt', 'za', 'zm', 'zw']
alpha = 'abcdefghijklmnopqrstuvwxyz'
array = [[alpha[i] + alpha[j] in all for j in range(26)] for i in range(26)]

#perform([2, 12, 18, 19], [2, 3, 6, 7, 10, 11, 12, 13, 14, 17, 21, 25])
#perform([0, 6, 8, 12], [3, 4, 11, 12, 16, 17, 18, 19])
#perform([3, 5, 19], [9, 10, 12, 14])
#perform([0, 2, 12, 18], [23])

while max(max(row) for row in array) > 0:
  best = simple(array)[1:]
  bestrows = []
  bestcols = []
  i = 1
  while i < 1 << 26:
    row = [-1 for j in range(26)]
    for j in range(26):
      if (i & 1 << j):
        for k in range(26):
          if array[j][k] == 0:
            row[k] = 0
          elif array[j][k] == 1 and row[k]:
            row[k] = max(row[k], 0) + 1
        if max(row) < 1:
          break;
    if max(row) > 0:
      rows = [j for j in range(26) if i & 1 << j]
      cols = [j for j in range(26) if row[j] > 0]
      unused = [row[:] for row in array]
      for j in rows:
        for k in cols:
          unused[j][k] = 0
      total = makeregex(rows) + makeregex(cols) + simple(unused)
      if len(total) < len(best):
        best = total
        bestrows = rows
        bestcols = cols
      i += 1
    else:
      i += i & -i
  if bestrows:
    perform(bestrows, bestcols)
  else:
    print best
    break

```

Now without seeding, this actually produces the worse 286-byte regex:

```
\.?([bgp][ae-hmnrstwy]|[cst][cdghk-orvz]|[nv][acegiu]|m[acdeghk-z]|a[c-gilmoq-uwxz]|k[eghimnprwyz]|l[abcikr-vy]|i[del-oq-t]|s[abeistxy]|c[afiuwxy]|e[cegr-u]|b[bdijoz]|d[ejkmoz]|f[ijkmor]|g[dilpqu]|h[kmnrtu]|n[floprz]|u[agksyz]|r[eosuw]|j[emop]|t[fjtw]|z[amw]|p[kl]|w[fs]|y[et]|om|qa|vn)

```

When seeded with `[cmst][cdghk-orvz]` (which I had independently discovered manually before writing the first program) this improves to this 282-byte regex, thus equalling the first program:

```
\.?([cmst][cdghk-orvz]|[bgmps][aeghmnrsty]|[ag][d-gilmq-uw]|[pt][fkltw]|[acs][cioxz]|[nv][acegiu]|k[eghimnprwyz]|l[abcikr-vy]|i[del-oq-t]|b[bdfijowz]|e[cegr-u]|d[ejkmoz]|f[ijkmor]|h[kmnrtu]|n[floprz]|u[agksyz]|c[afuwy]|m[pquwx]|r[eosuw]|j[emop]|z[amw]|w[fs]|y[et]|gp|om|qa|sb|tj|vn)

```

After some experimentation I discovered that when seeded with `[cmst][cdghk-orvz]|[agim][delmq-t]|[dft][jkmo]|[acms]x` (selected from the output of the first version), it results in the given 275-byte regex.

For completeness, I think the best I achieved manually was the following 282-byte regex:

```
\.?(a[c-gilmoq-uwxz]|b[abd-jostz]|c[afiuwxy]|d[ejkmoz]|e[cegr-u]|f[ijkmor]|g[ad-ilp-u]|h[kmnrtu]|i[del-oq-t]|j[emop]|k[ipz]|l[abcikr-vy]|m[aep-y]|n[acefgilopruz]|om|p[aflst]|qa|r[eosuw]|s[abeistxy]|t[fjtw]|u[agksyz]|v[aceginu]|w[fs]|y[et]|z[amw]|[cmst][cdghk-orvz]|[bgkp][eghmnrwy])

```

# Answer
> 3 votes
# 282 bytes

```
\.?([abcmpt][fglmnrw]|[abgim][delmnq-t]|[acms]x|[adkn][ez]|[aemsv][cegu]|[afn][ior]|[bcmst][dghl-orvz]|[bgls][abirsty]|[clmpu][aky]|[clnv][aciu]|[dfst][jkmo]|[egp][eghrst]|[gmnt][fglpr]|[gr][esuw]|[ir]o|[ty]t|bj|h[kmnrtu]|j[emop]|k[ghimnprwy]|lv|om|qa|tc|u[gmsz]|vn|w[fs]|ye|z[amw])

```

Try it online!

### ~~276 bytes~~—old list

```
\.?([abt][dfgmortwz]|[aclnv][ciu]|[acms]x|[agim][delmq-t]|[bcgkmp][ghmnrwy]|[bdijnr][eo]|[cgnp][afglr]|[cmst][cdghk-orvz]|[dft][jkmo]|[dknu]z|[epsy][et]|[fgks]i|[gjkmn][ep]|[gmv][aegnu]|[jo]m|[psu][agksy]|b[abijs]|e[cgrsu]|fr|h[kmnrtu]|in|l[abkr-vy]|qa|r[suw]|sb|w[fs]|z[amw])

```

Try it online!

---
Tags: code-golf, regular-expression
---


title: Inscriptio Labyrinthica

text:
# Question
Title: Inscriptio Labyrinthica
In the burial place of King Silo of Asturias there is an inscription that reads **SILO PRINCEPS FECIT** (*King Silo made this*).

The first letter is found in the very middle, and from there one reads by going in any non-diagonal direction radiating outward. The final letter is found on all four corners. In this challenge, you'll generalize the process to make them.

## Input

A string (or equivalent), and an integer. You may make the following assumptions about the input:

* The string will have an odd length.
* The integer will be an odd number between 1 and one less than twice the length of the string.

## Output

An *inscriptio labyrinthica* for the string, using the integer for the height *or* width (see models for height examples). Output should be each letter with no spaces, line break as default to your system/language.

## Test cases

Note that an input of 1 or (length * 2 - 1) will result in a horizontal or vertical palindrome.

```
 Input: FOO, 3    Input: BAR, 1    Input: BAR, 3    Input: BAR, 5

Output: OOO      Output: RABAR    Output: RAR       Output: R
        OFO                               ABA               A
        OOO                               RAR               B
                                                            A
                                                            R

 Input: ABCDE, 5   Input: ABCDE, 3   Input: *<>v^, 5

Output: EDCDE     Output: EDCBCDE           ^v>v^
        DCBCD             DCBABCD           v><>v
        CBABC             EDCBCDE           ><*<>
        DCBCD                               v><>v
        EDCDE                               ^v>v^

```

## Scoring

This is so shortest answer in bytes wins. Standard loopholes forbidden.

# Answer
# , 27 bytes

```
([{~]+/&(|@i:)#@[-1+])-:@<:

```

Try it online!

An example will clarify the high-level approach.

Consider `'ABCDE' f 3`

We notice that what we seek is simply the "cross addition" table of `1 0 1` and `3 2 1 0 1 2 3`, which looks like this:

```
4 3 2 1 2 3 4
3 2 1 0 1 2 3
4 3 2 1 2 3 4

```

We then pull those indexes from the original string: `[{~`.

All the rest of the code is just boring arithmetic and the use of `i:` to construct the arguments `1 0 1` and `3 2 1 0 1 2 3`.
> 7 votes

# Answer
# Jelly, 12 bytes

```
Uṡṛ‘HɗŒBŒḄZY

```

Try it online!

A dyadic link taking the string as its left and height as its right argument. Returns a string with line breaks. If a list of strings were acceptable for output, I can remove the final `Y` saving a byte. Interestingly the original “SILO PRINCEPS FECIT” looks to me like ASCII art of a 3D diamond when I look at it on TIO.

## Explanation

```
U            | Reverse input
 ṡ   ɗ       | All overlapping substrings of the length given by:
  ṛ          | - The right argument
   ‘         | - Incremented by 1
    H        | - Halved
      ŒB     | Concatenate to the reverse, keeping a single copy of the last character (so creating a palindrome)
        ŒḄ   | Do the same, but this time using the lists of characters generated by the last atom
          Z  | Transpose
           Y | Join with newlines

```
> 6 votes

# Answer
# , ~~93~~ ~~91~~ 87 bytes

-2 bytes thanks to Giuseppe. -4 bytes by inputting the width rather than the height, as allowed by OP.

```
function(s,W,w=W%/%2,h=length(s)-w-1)write(s[1+outer(abs(-w:w),abs(-h:h),`+`)],1,W,,"")

```

Try it online!

Takes input as a vector of characters. The key part is `s[1+outer(abs(-w:w),abs(-h:h),'+')]`.

First compute \\$w\\$ and \\$h\\$ such that the output is of size \\$(2w+1)\times(2h+1)\\$.

In the output, we want the character in position \\$(i,j)\\$ to be the character at index \\$1+|i-h|+|j-w|\\$ in the input. This corresponds to the outer sum of `abs(-w:w)` and `abs(-h:h)` (`abs(-h:h)` is a short way of writing the vector \\$\[h, h-1, h-2, \ldots, 2, 1, 0, 1, 2, \ldots, h-1, h\]\\$). For instance, `outer(abs(-2:2), abs(-1:1), '+')` gives

```
32123
21012
32123

```

(we then need to add 1 because R is 1-indexed.) The 0 in the centre is where the first letter of the input should go.

The rest is formatting.
> 6 votes

# Answer
# Charcoal, ~~25~~ 19 bytes

```
Ｅ⊘⊕η✂θι⁺ι⁻Ｌθ⊘⊖η‖Ｏ←↑

```

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

```
Ｅ⊘⊕η✂θι⁺ι⁻Ｌθ⊘⊖η

```

Draw a quarter of the inscription.

```
‖Ｏ←↑

```

Reflect to complete the inscription.
> 5 votes

# Answer
# Japt `-R`, ~~19~~ 16 bytes

```
z
ò@VÔtXUaVÊ)êÃê

```

Try it

```
z\nò@VÔtXUaVÊ)êÃê     :Implicit input of integer U & string V
z                     :Floor divide U by 2
 \n                   :Reassign result to U
   ò                  :Range [0,U]
    @                 :Map each X
     VÔ               :  Reverse V
       tX             :  Substring from index X to index ...
         Ua           :    Absolute difference between U and ...
           VÊ         :    Length of V
             )        :  End substring
              ê       :  Palindromise
               Ã      :End map
                ê     :Palindromise
                      :Implicit output, joined by newlines

```
> 3 votes

# Answer
# Wolfram Language (Mathematica), ~~57~~ 54 bytes

```
(g=Reverse@Rest@#~Join~#&)@BlockMap[g,#,⌈#2/2⌉,1]&

```

Try it online!

Takes the width as input.
> 2 votes

# Answer
# Japt `-R`, 10 bytes

```
Ôã°Vz)mê ê

```

Takes width instead of height.

Try it

Pseudocode (U is string, V is integer):

```
U.Reverse().AllSubstringsOfLength(++V / 2).Map(Palindromize).Palindromize

```
> 2 votes

# Answer
# Perl 6, ~~68~~ 67 bytes

```
{say |$^a.comb[{$_...0...$_}($a.comb-$^b+>1-1)X+.abs]for ^$b-$b+>1}

```

Try it online!
> 2 votes

# Answer
# Python 3, 104 bytes

I haven't golfed in so long... I'm sure this could be shorter.

## Details

This code defines a function that takes two arguments (the string and the height) and gives the result on standard output.

The index into the string is the Manhattan distance from the centre of the grid. For a grid of width `w` and height `h`, the distance for the cell at `(x, y)` is `abs(x - (w - 1) / 2) + abs(v - (h - 1) / 2)`.

The width of the grid must be such that the Manhattan distance of the corners (say, `(0, 0)`) is one less than the length of the string. Substituting `(0, 0)` into the above and simplifying, we find that the width is simply `2 * len(s) - h`.

## Code

```
def b(s,h):
 w=2*len(s)-h
 for y in range(h):print(''.join(s[abs(x-w//2)+abs(y-h//2)]for x in range(w)))

```

Try it online!
> 2 votes

# Answer
# 05AB1E, 10 bytes

```
RŒI>;ù€ûû»

```

Try it online!
> 2 votes

# Answer
# Pyth, 19 bytes

```
L+_btbjyyM.:Q-lQ/E2

```

Try it online!

```
L+_btbjyyM.:Q-lQ/E2   Implicit: Q=string, E=height
L                     Define a function, y(b):
  _b                    Reverse b
 +  tb                  Append all be first element of b
                      y is now a palindromisation function
              lQ      Length of Q
             -  /E2   Subtract floored division of E by 2
          .:Q         All substrings of Q with the above length
        yM            Palindromise each substring
       y              Palindromise the set
      j               Join on newlines, implicit print

```
> 1 votes

# Answer
# Stax, ~~11~~ 9 bytes

```
é─C[┬«#t▒

```

Run and debug it

It takes the width, and the original string, in that order.
> 1 votes

# Answer
# Python 2, 95 bytes

```
def f(s,n):
 y=len(s);n//=2
 for i in range(n+1)+range(n)[::-1]:print s[y+~i:n-i:-1]+s[n-i:y-i]

```

Try it online!
> 1 votes

# Answer
# C# (.NET Core), 146 bytes

```
s=>n=>{int w=s.Length*2-n,i=0,j;var r=new char[n,w];for(;i<n;i++)for(j=0;j<w;)r[i,j]=s[System.Math.Abs(n/2-i)+System.Math.Abs(w/2-j++)];return r;}

```

Try it online!

Longest answer so long. :-) It uses the Manhattan distance to the center of the square. There must be a shorter way, though.
> 1 votes

# Answer
# Tcl, ~~188~~ ~~170~~ 162 bytes

```
{{w s} {join [lmap C [lrepeat $w string] {join [$C reverse [set y [$C range $s [set x [expr abs($w/2+1-[incr i])]] end-[expr $w/2-$x]]]][$C range $y 1 end]}] \n}} bytes

```

Try it online!

There seem to be a million bad ways to golf this problem in TCL. This is not the worst of them.

Saved 18 bytes minimum by converting to lambda (can save up to 13 more if return value of a list of lines is acceptable)

Saved an additional 8 since lmap iterator served as an extra constant
> 1 votes

# Answer
~~Canvas, 18 bytes
```
±Ｘ↕┌Ｌ╵┌－Ｙ｛ｘ；１ｙ１＠］┼

```
Try it here!
~~

~~Canvas doesn't do substrings, so I need to treat it like an art object and get a subsection that way. I feel like this costs me 2 bytes, but hey, what can you do.~~

Looks like this actually doesn't work like I thought: Canvas's palindromize functions mirror certain characters (e.g. V mirrored vertically becomes ^), and I can't exactly disable that... oh well, i guess
> 1 votes

# Answer
# Ruby, 65 bytes

```
->s,h{(-(h/=2)..h).map{|y|(z=s[(w=y.abs)..w+~h]).reverse.chop+z}}

```

Try it online!
> 1 votes

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


title: Pythagoras' Other Leg

text:
# Question
Title: Pythagoras' Other Leg
Pythagoras had his leg blown up in the war. It had to be amputated, and though he nearly died, he pulled through and made a full recovery. Now, after a year of walking with crutches, he gets the privilege of getting a prosthetic leg! Thing is, though, there are several that fit, but which ones?

## The Task

Given a positive integer as input that is the length of one leg of a Pythagorean triple, output all possibilities for the other leg. For example, the smallest Pythagorean triple is (3,4,5), which forms a triangle with two legs of length 3 and 4, and a hypotenuse of length 5.

## Examples

```
Leg:5
12

Leg:28
21
45
96
195

Leg:101
5100

Leg:1001
168
468
660
2880
3432
4080
5460
6468
10200
38532
45540
71568
501000

```

## The Rules

* Input will be a single positive integer `n`.
* Output may be in any order, with any delimiter, in any base (though this base must be consistent), and with optional opening and closing braces, and optional trailing whitespace. That is, `1 2 3`, `[1,2,3]`, and `1,11,111` all fit this output specification.
* You may assume that `n` will never be larger than one fourth of the fourth root of your language's limit (without using libraries). In practice, you may assume the input will be less than either this or 10,000, whichever is less.

Pythagoras is waiting on you, so better write your code quick and short!

# Answer
> 4 votes
# Pyth - 13 bytes

Brute forces all possible ones up till `n^2+1`.

```
f!%.a,TQ1S*QQ

```

Test Suite.

# Answer
> 11 votes
# Jelly, 8 bytes

```
²R²+²Æ²O

```

*This answer is non-competing, since it uses features that have been implemented after the challenge was posted.* Try it online!

This approach does not use floating point math, so it will give the correct answer as long as the intervening lists can fit into memory.

### Idea

If **(a, b, c)** is a Pythagorean triple, there are strictly positive integers **k, m, n** such that the set equality **{a, b} = {km2 \- kn2, 2kmn}** holds.

In particular, this means that **a \< b2** and **b \< a2**, so for input **a** we can simply check if **a2 \+ b2** is a perfect square for each **b** in **{1, … a2}**.

### Code

```
            Input: x

²           Compute x².
 R          Get get range 1 ... x².
  ²         Square each integer in that range.
   +²       Add x² to each resulting square.
     Æ²     Check if the resulting sums are perfect squares.
       O    Get all indices of ones.

```

# Answer
> 10 votes
# Julia, 35 bytes

```
n->filter(i->hypot(i,n)%1==0,1:n^2)

```

This is an anonymous function that accepts an integer and returns an array.

For each `i` from 1 to the input squared, we compute the hypotenuse using Julia's built-in `hypot` function, and determine whether the fractional portion is 0. If so, we keep it, otherwise it's excluded.

# Answer
> 5 votes
# CJam, 17 bytes

```
{:A2#{Amh1%!},1>}

```

This is an anonymous function that pops an integer from the stack and leaves an array in return.

Try it online!

### Idea

If **(a, b, c)** is a Pythagorean triple, there are strictly positive integers **k, m, n** such that the set equality **{a, b} = {km2 \- kn2, 2kmn}** holds.

In particular, this means that **a \< b2** and **b \< a2**, so for input **a** we can simply check if **a2 \+ b2** is a perfect square for each **b** in **{1, … a2}**.

### Code

```
:A               Save the input in A.
  2#             Square it.
    {      },    Filter; for each B in {0, ..., A**2}:
     Amh           Calculate the hypotenuse of (A, B).
        1%!        Apply logical NOT to its fractional part.
                 Keep B if ! pushed 1.
             1>  Discard the first kept B (0).

```

# Answer
> 4 votes
# JavaScript ES6, 60 ~~62~~

Same as the other answers, checking from 1 to a\*a-1

```
a=>[...Array(a*a).keys()].filter(b=>b&&!(Math.hypot(a,b)%1))

```

Thx to @Mwr247 the shortest way to build a range in ES6

2 bytes saved thx @ETHproductions

# Answer
> 3 votes
## C, 96 bytes

Alternately increment `y` (the other leg) and `z` (the hypotenuse) until their difference drops to 1. Output every exact match (`c==0`) you encounter on the way.

```
int x,y,z;main(int c,char**a){for(x=z=atoi(a[1]);++y<z;c=x*x+y*y-z*z,c?z+=c>0:printf("%d ",y));}

```

Call the compiled program with *n* as parameter; it will output a space-separated list of decimal numbers.

Obviously not the shortest; I may find comfort in having the fastest.

```
$ time ./pyth 9999
200 2020 13332 13668 16968 44440 45360 54540 55660 137532 164832 168168 413080 494900 504900 617120 1514832 1851468 4544540 5554440 16663332 49990000
real    0m0.846s
user    0m0.800s
sys     0m0.000s

```

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

```
b/.Solve[#^2+b^2==c^2,PositiveIntegers]&

```

I'm using an undocumented form of `Solve`: when the list of variables is omitted, then `Solve` defaults to solving for all symbols in the expression. We thus save 6 bytes over the more regular `Solve[#^2+b^2==c^2,{b,c},PositiveIntegers]`.

`PositiveIntegers` is new in version 12 of Mathematica and thus not available in TIO. In desktop Mathematica, we get

```
F = b/.Solve[#^2+b^2==c^2,PositiveIntegers]& ;

F[5]
(*    {12}    *)

F[28]
(*    {21, 45, 96, 195}    *)

F[101]
(*    {5100}    *)

F[1001]
(*    {168, 468, 660, 2880, 3432, 4080, 5460, 6468, 10200, 38532, 45540, 71568, 501000}    *)

```

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

```
lambda n:[i for i in range(1,n*n)if abs(i+n*1j)%1==0]

```

A straightforward solution using complex `abs` to compute the length of the hypotenuse. It's safe to use `n*n` as an upper bound for the other leg because `(n*n)^2 + n^2 < (n*n+1)^2`. I tried using recursion instead but didn't get anything shorter.

# Answer
> 2 votes
## Seriously, 20 bytes

```
,;╗ªDR;`╜@ÇA1@%Y`M@░

```

Same strategy as xnor's Python answer: check `i in range(1,n*n)` for values where `abs(i+nj) % 1 == 0`, and output the list. Try it online

Explanation:

```
,;╗    get input and save a copy in register 0
ªDR;   push two copies of range(1,n*n)
`╜@ÇA1@%Y`M    map the function across one of the ranges:
    ╜@ÇA         compute abs(i+nj)
    1@%Y         push 1 if result % 1 is 0, else 0
M@░    swap the two lists, take values in the original range where the corresponding values in the second range are truthy

```

# Answer
> 2 votes
# PARI/GP, 36 bytes

```
x->[y|y<-[1..x^2],issquare(x^2+y^2)]

```

# Answer
> 2 votes
# APL(NARS), 373 chars, 746 bytes

```
C←{h←{0=k←⍺-1:,¨⍵⋄(k<0)∨k≥i←≢w←⍵:⍬⋄↑,/{w[⍵],¨k h w[(⍳i)∼⍳⍵]}¨⍳i-k}⋄1≥≡⍵:⍺h⍵⋄⍺h⊂¨⍵}⋄P←{1≥k←≢w←,⍵:⊂w⋄↑,/{w[⍵],¨P w[a∼⍵]}¨a←⍳k}⋄d←{∪×/¨{k←≢b←1,π⍵⋄∪{b[⍵]}¨↑∪/101 1‼k k}⍵}⋄t←{(-/k),(×/2,⍵),+/k←⍵*2}⋄b←{⍬≡a←3 C d w←⍵:(⊂1,⍵,1)⋄(⊂1,⍵,1),a/⍨{⍵[2]>⍵[3]}¨a←↑∪/P¨,a/⍨{w=×/⍵}¨a}⋄u←{(↑⍵),2÷⍨(+/a),-/a←1↓⍵}⋄t1←{(↑¨⍵)×t¨1↓¨⍵}⋄f1←{0=2∣⍵:↑¨t1 b⍵÷2⋄{2⊃⍵}¨t1 u¨b⍵}⋄f←{m←⎕ct⋄⎕ct←0⋄r←f1⍵⋄⎕ct←m⋄r}

```

comment:

```
C: ⍺ combination in ⍵ list
P: permutations  in ⍵ list
d: divisors of ⍵ unsigned
t: Pythagorian triple from ⍵ list 2 unsigned
b: if argument ⍵ is one unsigned it would return the list of (k,i,j) where
   k,i,j are all divisors of ⍵, and ⍵=k×i×j and i>j
u: from one triple (k,i,j) return (k,(i+j)/2,(i-j)/2)
t1: apply (k,i,j) to t in the way  k×t i,j
f: the function of this exercise

```

The idea would be factor the input for to know the possible m,n that generate using t all Pythagorian triple that has the input as leg. Test:

```
  f 18298292829831839x
167413760243137645229428509060960 15219432749376149566311682641900 99808869980900940
  1383584795397831778755607512840
  f 5
12
  f 28
195 96 21 45
  f 101
5100
  f 1001
501000 6468 38532 2880 468 660 168 5460 45540 4080 71568 3432 10200
  ≢f 1001
13
  f 1663481166348349x
1383584795397831778755607512900
  f 198820182831x
19764732550476133587280 346749693868002343608 5664631173992 6083327962596530720 613900915408 115583231289334114460
  18249983887789596492 1883559626820 1040249081604007030900 54749951663368790920 6588244183492044529092
  265093577108 2196081394497348176360

```

# Answer
> 2 votes
# APL (Dyalog Extended), ~~15~~ 14 bytesSBCS

Anonymous tacit prefix function.

```
(⍸⊢(+∊⊢)⍳×⍳)×⍨

```

Try it online!

`×⍨` square (lit. multiplication selfie of) the argument

`(``)` apply the following anonymous tacit function:

**ɩ**ntegers 1 through the argument

multiply by **ɩ**ntegers 1 through the argument (i.e. square)

`⊢(``)` apply the following anonymous tacit function with the argument as left argument:

`+` is the sum

a member of

it?

**ɩ**ndices of truths

# Answer
> 1 votes
# Perl 5, 43 bytes

```
$i=<>;{sqrt(++$_**2+$i**2)!~/\./&&say;redo}

```

If you want the script to terminate, we can inspect other legs up to n² only, as explained by xnor, so we have 48 bytes:

```
map{sqrt(++$_**2+$i**2)!~/\./&&say}1..($i=<>)**2

```

# Answer
> 1 votes
# Japt, 16 bytes

```
1oU² f@!(MhXU %1

```

Try it online!

### How it works

```
        // Implicit: U = input integer
1oU²    // Generate a range of integers from 1 to U squared.
f@!(    // Keep only items X that return falsily to:
MhXU %1 //  Math.hypot(X,U) % 1.
        // This keeps only the items where sqrt(X*X+U*U) = 0.
        // Implicit: output last expression

```

# Answer
> 1 votes
# Stax, 8 bytes

```
î←■↑»⌐╚â

```

Run and debug it

In pseudo-code:

```
(1..n²).filter(d -> is-square(n² + d²))

```

# Answer
> 1 votes
# 05AB1E, 10 bytes

```
nDLn+Å²ƶ0K

```

Try it online or verify all test cases.

```
nDLʒnIn+Å²

```

Try it online or verify all test cases.

**Explanation:**

```
n           # Take the square of the (implicit) input-integer
 D          # Duplicate it
  L         # Create a list in the range [1, input^2]
   n        # Square each value in this list
    +       # Add the input^2 we duplicated to each
     Å²     # Check for each of these if it's a square (1 if truthy; 0 if falsey)
       ƶ    # Multiply each value by its 1-based index
        0K  # Remove all 0s from the list
            # (after which the result is output implicitly)

nDL         # Same as above
   ʒ        # Filter this list by:
    n       #  Get the square of the current number
     In+    #  Add the squared input to it
        Å²  #  And check if it's a square
            # (after the filter, implicitly output the result)

```

# Answer
> 1 votes
# Java 8, 72 bytes

```
n->{for(int i=0;++i<n*n;)if(Math.hypot(i,n)%1==0)System.out.println(i);}

```

Try it online.

**Explanation:**

```
n->{                           // Method with integer as parameter and no return-type
  for(int i=0;++i<n*n;)        //  Loop `i` in the range (0, n²)):
    if(Math.hypot(i,n)         //   If sqrt(i² + n²)
       %1==0)                  //   has no decimal digits after the comma (so is an integer)
      System.out.println(i);}  //    Output `i` with trailing newline

```

# Answer
> 1 votes
# MathGolf, 9 bytes

```
²╒gÆ²k²+°

```

Try it online!

Couldn't find a nice way to remove any of the `²`s, which take up 3/9 bytes. Otherwise it is quite straight-forward

## Explanation

```
²           square input
 ╒          range(1,n+1)
  gÆ        filter list using next 5 operators
    ²       square list element
     k²     push input squared
       +    pop a, b : push(a+b)
        °   is perfect square

```

---
Tags: code-golf
---


title: Invert Some Switches on a Switchboard

text:
# Question
Title: Invert Some Switches on a Switchboard
Inspired by this challenge.

## Goal:

Given a pre-configured switchboard and a list of indexes, invert the switches at the given indexes.

A switchboard is made up of some number of switches (`v` or `^`) wrapped in `-`'s and arranged into rows of varying length. Here is an example switchboard:

```
-v-^-v-
-^-v-
-v-^-v-

```

To invert/flip a switch means changing it from `v` to `^`, or from `^` to `v`.

The switches are indexed left-to-right, top-to-bottom. E.g., in the example above, the last `v` in the first row would be in position 3 and the `^` in the middle row would be at 4 (using 1-indexing).

## Input:

* A string (or list of strings) representing the switchboard. It is guaranteed to match the regex `((-[v^])+-)(\n(-[v^])+-)*`.
* A possibly empty list of numbers representing indexes, may be 0 or 1 (or some arbitrary number if you want) indexed. These are the switches that need to be flipped.

## Output:

* A switchboard in the same shape as the input with the specified switches inverted. Any unspecified switches should retain their initial state.

## Rules:

* Input will always be correctly formatted and no given indexes will be out of bounds.
* The list of indexes will be sorted and will have no duplicates.
* State in your answer what indexing you use, be it 0, 1, or some arbitrary one.
* Trailing whitespace is fine as long as the output looks like the input.
* This is so shortest code wins.

## Examples:

```
#Using 1-indexing
input: #Empty Case
[],
-v-^-v-

output:
-v-^-v-

input: #Single switch
[1],
-v-

output:
-^-

input: #Skip a line
[3,5],
-^-v-v-
-v-
-^-^-

output:
-^-v-^-
-v-
-v-^-

input: #Flip one in each line + number wrap
[3,4,6],
-^-v-v-
-v-
-^-^-

output:
-^-v-^-
-^-
-^-v-

input: #Flip 'em all
[1,2,3,4,5,6],
-^-v-v-
-v-
-^-^-

output:
-v-^-^-
-^-
-v-v-

```

# Answer
# Vim, ~~60, 46, 38~~, 37 bytes/keystrokes

```
qq/\d
ggDJ@"/[v^]
sv^<esc>l?\V<C-r>"
x@qq4u@q

```

`<esc>` and `<C-r>` are both 1 byte/keystroke. Byte Counter

Test Case 1 (Verbose mode)

Test Case 2 (Verbose mode)

Thanks to Grimy for the ideas that led to a reduction of 22 bytes :)
> 11 votes

# Answer
# JavaScript, ~~63~~ 59 bytes

```
a=>s=>s.replace(/v|\^/g,x=>"^v"[a.includes(n++)^x>"^"],n=0)

```

Try it online!

Saved 4 bytes thanks to Arnauld.
> 6 votes

# Answer
# K (oK), ~~31~~ 27 bytes

**Solution:**

```
`0:{@[x;(&x>93)y;"^v"94=]};

```

Try it online!

**Explanation:**

Quick answer, will try to golf it. 0-indexed.

```
`0:{@[x;(&x>93)y;"^v"94=]}; / the solution
`0:                       ; / print to stdout
   {                     }  / lambda taking 2 implicit args x & y
    @[ ;        ;       ]   / apply @[var;index;function]
                     94=    / 94 (ASCII "v") equal to? returns 0 or 1
                 "v^"       / index into "v^" (ie flip switch)
               y            / index into
        (     )             / do this together
          x>93              / x greater than 93 (ASCII "]")
         &                  / indices where true
      x                     / apply to x

```

**Notes:**

* -4 bytes thanks to `>93` trick
> 4 votes

# Answer
# Python 3, ~~140~~ ~~134~~ 103 bytes

**(-30 thanks to DJMcMayhem♦, -1 more thanks to Black Owl Kai)**

```
def f(i,y,x=1):
 for c in y:q=c>'-';p=len(i)and x==i[0]*q;print([c,"v^"[c>'^']][p],end='');x+=q;i=i[p:]

```

Try it online!

---

Oof, second try at golfing anything at all. This just uses a rather unsophisticated loop over the string, using `x` to keep track of the current switch index. Uses 1-indexing.

Ungolfed:

```
def f(i,y):
     x = 1
     for c in y:
         nextchar = c # nextchar gets golfed out completely within the print
         if c in 'v^': # golfed as c>'-'
             if len(i) and x==i[0]:
                nextchar = 'v' if c=='^' else '^'
                i = i[1:]
             x += 1
         print(nextchar, end='')

```
> 3 votes

# Answer
# Perl 6, 31 bytes

```
->$_,\s{S:nth(s){\^|v}=$/~^'('}

```

Try it online!

(-2 bytes thanks to Jo King)

Perl 6's substitution operator `S` conveniently takes an `nth` adverb that accepts not only a single index at which to make the replacement, but a list of them, exactly as needed here.

The replacement is `$/ ~^ '('`, where `$/` is the matched text (either `v` or `^`), `~^` is the stringwise exclusive-or operator, and `(` is the character whose bits turn `v` into `^` and vice versa.
> 3 votes

# Answer
# Jelly, 12 bytes

```
O^%5T⁴ịƲ¦40Ọ

```

A full program accepting a string and a list of integers which prints the result.

**Try it online!**

### How?

```
O^%5T⁴ịƲ¦40Ọ - Main Link: list of characters, S; inversion indices, I
O            - to ordinals   ('\n':10, '-':45, '^':94, 'v':118)
        ¦    - sparse application...
       Ʋ     - ...to indices: last four links as a monad: f(O(S))
  %5         -   modulo 5   (10:0, 45:0, 94:4, 118:3)
    T        -   truthy indices (giving, X, indices of '^' and 'v' in S)
     ⁴       -   4th command line argument = I
      ị      -   index into X   (giving indices of '^' and 'v' to invert in S)
 ^       40  - ...action: XOR with 40   (94:118, 118:94)
           Ọ - from ordinals
             - implicit print

```
> 3 votes

# Answer
# Python 3.8 (pre-release), ~~80~~, ~~78~~, ~~77~~, ~~71~~, 70 bytes

```
lambda x,s,i=0:''.join([c,'^v'[c<'v']][c>s and(i:=i+1)in x]for c in s)

```

*-1 byte, thanks to @Shaggy*

Try it online!
> 3 votes

# Answer
# MATL, 29 bytes

```
c!tt45>o2yfi)(2=XK)t106-E-K(!

```

Try it online! Or verify all text cases.

Input is a cell array of strings and a row vector of numbers, with 1-based indexing. Output is right-padded with spaces.
> 2 votes

# Answer
# Python 2, ~~105~~ ~~97~~ 91 bytes

```
lambda a,s:reduce(lambda(t,i),c:(t+[c,'^v'[c<'v']][c>'-'and i in a],i+(c>'-')),s,('',0))[0]

```

Try it online!

6 bytes saved by ~~stealing~~ using Rin's Fourier transform's `c>'-'` instead of `c in'^v'`.

`0`-indexed.
> 2 votes

# Answer
# JavaScript (Node.js), ~~101~~ ~~98~~ ~~93~~ ~~91~~ ~~77~~ 67 bytes

```
a=>s=>[...s].map(c=>t+=c>s?"^v"[a.includes(i++)^c>"^"]:c,t=i=``)&&t

```

Try it online!

10 bytes, thx to suggestions by Shaggy.

Port of my Python answer. Not used to golfing javascript!
> 2 votes

# Answer
# Jelly, 14 bytes

```
⁾^vḟ$€>”-T⁹ịƲ¦

```

Try it online!

Full program.

This feels *too overlong*...
> 2 votes

# Answer
# Stax, 13 bytes

```
¿╫╦ÜΦ1▌X○!ΩTæ

```

Run and debug it

This uses 0-based indices.

1. Find all indices of the regex `[v^]`.
2. Index into the *index* array using the input.
3. At each result, xor the input's ascii code with `40`. This is `xor('v', '^')`.
> 2 votes

# Answer
# Clean, 93 bytes

```
import StdEnv
$i=foldl(\s c=s++[if(any((==)(sum[1\\k<-s|k>'-']))i&&c>'-')if(c>'^')'^''v'c])[]

```

Try it online!

Defines the function `$ :: [Int] -> [Char] -> [Char]` taking a zero-indexed list of indices and returning a function that takes the string and returns the altered string.
> 2 votes

# Answer
# , 20 bytes

```
ÑñÀ/vüÞ
sv^l?Ö"
xH

```

Try it online!

Uses some new features, such as `Ñ` which is **incredibly** useful.
> 2 votes

# Answer
# JavaScript, 111 bytes

### Code

```
x=>y=>{x.map(i=>eval(`y=y.replace(/(((v|\\^)[^^v]*){${i}})(v|\\^)/,(a,b,c,d,e)=>b+(e<"v"?"v":"^"))`));return y}

```

Takes input in format f(x)(y) where x is the indices and y is the switchboard. Indices are 0 indexed

Try it online!

### Explanation

For each index

```
x.map(i=>...

```

construct the regex that finds the index+1 th "^" or "v"

```
`.../(((v|\\^)[^^v]*){${i}})(v|\\^)/...`

```

insert it into a string to replace it with the opposite symbol "v"\<-\>"^"

```
y=y.replace(...,(a,b,c,d,e)=>b+(e<"v"?"v":"^"))

```

then evaluate the string as a function

```
eval(...)

```

After iterating through the indices to switch, return the switchboard

```
return y

```
> 1 votes

# Answer
# Retina 0.8.2, ~~66~~ 62 bytes

```
\d+
$*
T`v^`^v`.(?<=\b(?(3)$)(?<-3>1)+(,1+)*(-|¶|(v|\^))+)
1A`

```

Try it online! Link includes test case. 1-indexed. Explanation:

```
\d+
$*

```

Convert the input numbers to unary.

```
T`v^`^v`.(?<=\b(?(3)$)(?<-3>1)+(,1+)*(-|¶|(v|\^))+)

```

Transliterate between `v` and `^` all characters with the property that the number of `v`s and `^`s so far (inclusive) equals one of the input numbers.

```
1A`

```

Delete the input numbers.
> 1 votes

# Answer
# Jelly, 17 bytes

```
⁾^vK;`©⁹e€ky@€⁸¦®

```

Try it online!

A full program taking the indices as first and string as second argument. Prints the output with the indicated switches flipped.
> 1 votes

# Answer
# Charcoal, 23 bytes

```
⭆η⎇№θ⌕ΦＬη№v^§ηλκ§v^⁼vιι

```

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

```
 η                      Input string
⭆                       Map over characters and join
  ⎇                     If
   №                    Count of (i.e. exists)
     ⌕                  Index of
               κ        Current index in
       Ｌ                Length of
        η               Input string
      Φ                 Implicit range filtered by
         №              Count of (i.e. exists)
             η          Input string
            §           Indexed by
              λ         Current value
          v^            In literal string `v^`
    θ                   In input list
                 v^     Then literal `v^`
                §       Indexed by
                     ι  Current character
                   ⁼    Equal to
                    v   Literal `v`
                      ι Else current character

```
> 1 votes

# Answer
# Japt, ~~16~~ 14 bytes

```
Ëc^#(*(D>V©øT°

```

Try it

```
Ë>V©øT° ?Dc^#(:D     :Implicit input of multi-line string U & integer array V
Ë                    :Map each D in U
 >V                  :  Greater than V? (Coerces V to a string and, conveniently, all digits are > "\n" & "-" and < "^" & "v")
   ©                 :  Logical AND with
    ø                :  Does V contain
     T°              :    T (initially 0) postfix incremented
        ?            :  If true
         Dc          :  Charcode of D
           ^#(       :  XOR with 40
              :D     :  Else D

```
> 1 votes

# Answer
# Ruby, 56 bytes

1-indexed.

```
->s,i{j=0;s.gsub(/[v^]/){i==i-[j+=1]?$&:"v^".tr($&,'')}}

```

Try it online!
> 1 votes

# Answer
# Japt, 15 bytes

```
®c^(Z>V©øT° *#(

```

Try it

```
®c^(Z>V©ø°T *#(    U = Input String, V = Array of Indices
®                  Map each Z in U
 c^                   XOR Z's charcode by
   (Z>V                 Z is 'v' or '^'
      ©                 Short-circuiting Logical and
       øT°              The current Z's index is in V
             *#(        Multiply the boolean with 40 (false = 0, true = 1)

```
> 1 votes

# Answer
# C# (Visual C# Interactive Compiler), 73 bytes

```
a=>b=>{int i=0;return a.Select(x=>x>45&&b.Contains(++i)?(char)(x^40):x);}

```

Try it online!
> 1 votes

---
Tags: code-golf, string, ascii-art
---


title: Golf range minimum queries of a list

text:
# Question
Title: Golf range minimum queries of a list
*(Inspired by the first problem solved in Stanford’s advanced data structures course.)*

Despite the academicese-heavy name, the problem we're going to solve is almost unbearably simple.

We have a list of numbers.

```
[31, 41, 59, 26, 53, 58, 97]

```

We're going to cut some contiguous snippet out of that list of numbers.

```
[31, 41, 59, 26, 53, 58, 97]
    |41, 59, 26, 53|

```

And then we're going to find the minimum of that snippet. In this case, that's quite obviously 26. That's all.

And the obvious solution is pretty fast, too, with \\$O(n)\\$ time and \\$O(1)\\$ space in the size of the list:

```
minval = arbitrarily large value
for (i=first snippet index, i<last snippet index, i++)
  if (list[i]<minval) minval = list[i]

```

### So what's with the ?

Where it gets interesting is when you try to see how efficient you can make it when you have a fixed list but a large number of range minimum queries -- snippets to find the minimum of. This version of the problem is useful, for example, if you have a huge time series you want to load only once, but you want to find the minimum of many different subintervals of that time series.

In such a scenario, it would actually be faster in practice to literally precompute all \\$n^2/2\\$ queries, store it in a table, and then just retrieve data from that table for an \\$O(1)\\$ time and \\$O(n^2)\\$ space solution.  *^dynamic programming solution taken from the Stanford slides*

And then if you're clever enough, you realize that you only have to store each query with size that's a power of two -- you can just combine those power-of-two minima to sum to an arbitrarily sized query, and achieve the same results with constant time and linearithmic rather than quadratic space.

Interestingly, if you keep optimizing, you can get to an \\$O(1)\\$ time and \\$O(n)\\$ space solution using a sort of augmented list known as a Fischer-Heun structure. I'd love to go into the details of the structure here, but explaining how it weaves into Cartesian tree building on fixed-size snippets would make this question about 50 pages long. It's explained in the Wikipedia page, however, along with several faster-than-linear intermediate structures.

(If you can get past a research paywall, here's the original Fischer & Heun 2011 paper. And if you’d prefer the much more verbose but much more hand-holdy Stanford lecture style, here are the follow-up slides that goes into this solution, including lots of intermediates.)

---

## The challenge

You can either write a full program or a function that calculates the result of a series of range minimum queries given a fixed list. Scoring is set up such that in general, the shortest and most-efficient-over-lots-of-queries code wins.

**Input:**

A list of integers `xs`, followed by a series of `i, j` pairs denoting the start and end of the snippet, inclusive (so the 26 example above uses indices i=1 and j=4). The list of integers is guaranteed to have at least one integer, and `0 <= i <= j < len(xs)`. This can be taken in any format that works best for your language — for example, one list for `xs` and one list of tuples for the `i, j` pairs; or maybe all the different pairs as a variable number of arguments. For a full program that takes in input from stdin, I’ll fix a format for the input:

```
xs[0] xs[1] xs[2] xs[3] ...
i1 j1
i2 j2
i3 j3
...

```

**Output:**

An ordered collection of the range minima for each `i, j` query, in the same order that they were given. In case an unordered map (such as a Python dictionary) from each `i, j` query to its range minimum works better for your language, that will also be allowed as an output; as long as it's obvious which minimum is related to which query.

Once again, for a full program that prints to stdout or a file, I’ll fix the format to have each range minimum on each newline (trailing newlines permitted).

## Scoring:

Lower score is better; score is determined by

```
at(b)^2+as(b)

```

Where `b` is the byte count of your code, `at` is the asymptotic runtime `Ө(n)` of the algorithm in the size of `xs` interpreted as a function of `n`, and `as` is the asymptotic space usage \\$\Theta(n)\\$ in the size of `xs` interpreted as a function of \\$n\\$. (All constant coefficients in such \\$\Theta(n)\\$ expressions must be 1, and only the fastest growing term may be kept in expressions, as is standard.)

Therefore, the above pseudocode solution, which uses \\$\Theta(n)\\$ time and \\$\Theta(1)\\$ space, and is 126 characters, would have a score of `(b => b**2 + 1)(126)=15876+1=15877`. (Of course, the pseudocode isn't really valid since it's missing a construct to deal with multiple queries, and also because it's uncompilable pseudocode...)

## Test cases:

**Input:**

```
31 41 59 26 53 58 97
1 4
0 2
5 6

```

**Output:**

```
26
31
58

```

**Input:**

```
1
0 0
0 0

```

**Output:**

```
1
1

```

**Input:**

```
-4 28 31 -54
0 0
0 1
0 2
0 3
1 1
1 2
1 3
2 2
2 3
3 3

```

**Output:**

```
-4
-4
-4
-4
28
28
-54
31
-54
-54

```

# Answer
> 0 votes
# Jelly, 6 bytes, \\$O(n)\\$ runtime, \\$O(1)\\$ space, score 37

```
r/ịṂɗ€

```

Try it online!

I hope I’ve understood the scoring correctly. Naive implementation that simply indexes into the list and finds the minimum. Requires no lookup table, but limited by needing to check each input value (so \\$O(n)\\$ in efficiency.

# Answer
> 0 votes
# Python 2, 42 bytes, \\$O(n)\\$ runtime, \\$O(1)\\$ space, score 1765

```
lambda x,L:[min(x[l[0]:l[1]+1])for l in L]

```

# Answer
> 0 votes
# T-SQL 2008, 55 bytes

I apologize for being unable to figure out the scoring system.

Input is 2 tables

```
SELECT min(x)FROM a,b
WHERE i>f and i<t+2GROUP BY z,f,t

```

**Try it online**

---
Tags: code-challenge, array
---


title: An OEIS polyglot

text:
# Question
Title: An OEIS polyglot
This is an answer-chaining challenge relating to the OEIS.

Oh, the justification for this is because a company needs one program to print out their OEIS sequences real bad and they have every language.

The answer-chaining format works in the following way:

Someone posts the first answer, from which all further solutions stem. This answer is a program that, given a number N, inputs the Nth number in OEIS sequence of whatever index they choose (we'll call it sequence 1), in whatever language they choose (language 1)

Someone else comes along and chooses their own sequence (that has to be different from the previous, and from all previous sequences). They make a program, in another language (which has to be different from all previous languages), that given a number N in the language 1 outputs the Nth number of sequence 1 and, given a number in language 2 outputs the Nth number of sequence 2.

This process continues ad infinitum.

The nth term of a sequence is the term that comes n times after the first, working from the first item. Here we use 0 and 1-indexing, to be easy on the coders!

No language or sequence reusing.

Input must be an integer or a string representation of an integer and output must be the correct value of the sequence. Error handling (non-int input) is not needed.

You must not post twice in a row.

You must wait an hour or more before posting again.

Whoever is the SECOND-to-last to post after a week of no answers (the person who didn't break the chain) wins, though the contest can continue indefinitely. If you're last and can show that you can add one more language to it, you continue the challenge until the next winner.

You can assume that the input or the output won't be outside the numerical range of your language (for example, assuming that IEEE's limit won't be surpassed by any sequence) but don't be a trickster and abuse this by using a language that only has 1.

Any sequence can be chosen, as long as it hasn't been used before.

The input cannot be out-of-bounds for the sequence you are using.

Two different language versions are different languages (Python 2 and Python 3 are considered different langs of their own). This isn't rigid, but as a rule of thumb, if it's separated from another version of the same language on TIO, it's different.

This isn't banned, but try once not to use the formula the OEIS gives.

If your resulting code is over 65536 characters long, provide a link to access it (e. g. Pastebin).

That's it and that's all. Ready? Set? FUN!

Yes, this IS "One OEIS after another" but put on multiplayer. I thought it'd be cool.

# Answer
# 15. Commentator, A020739

```
//0q   GxxJiiiiihhZUUUUUUUNYAxcccccbCLDLxyzUUUUUTxyzJCLOzUUUUUURzyzxyzxyzcccccbbCLGC//*/0#
/*
박망희		   		0#
;*/

n=>5/2>2?1:40-n//AcaAcAAI(((1)(1)(1)1)((1)(((1)1)1)1)(((1)(1)1)(((1)((1)1)(1)1)1)(((1)(1)(1)(1)1)(((1)(1)((1))(1)1)((1)((1)1)(1)1)(((1)1)(1)(1)1)1)(((1)1)(1)1)(((1)1)1)1)1)1)
//[>[-]<[>+<-],]>>+<[->[>>+<<-]>[<+>-]>[<+>-]<<<]>>>>++++++[<++++++++>-]<<[>+<-]>+.wvWwwWWwwwwwwWwWWWw
               //ip@
               //
;/**/
//I01-* h
//
 ;/*'""""""'""" '""""""""""'"""""'""'"""""""'"""'""""'"'"""""""'"""'""""""'"""'""""""""""*/

```

Try it online!

C#
Brainfuck
Runic Enchantments
Jelly
Gol\>\<\>
Javascript (Node.js) (All 1s)
Parenthetic
Whitespace (All 3s)
05AB12 (All 0s)
Unreadable
Grass
Width
AlphaBeta
Aheui (All 2s)

I had a few plans with Commentator, but only one survived contact with all the other languages. One caused errors in the Jelly (iirc) and I wasn't able to resolve it because I don't know why Jelly interpreted the bytes the way it did.
> 2 votes

# Answer
# 4. Jelly, A000312

```
n=>40-n//
//[>[-]<[>+<-],]>>+<[->[>>+<<-]>[<+>-]>[<+>-]<<<]>>>>++++++[<++++++++>-]<<[>+<-]>+.
       //ip@
       //
;/**/

```

C# (Visual C# Interactive Compiler)
brainfuck
Runic Enchantments
Jelly

Explanation:

We only account for the last line, all of the other lines are ignored.

```
;/**/ Argument: z
;/    Reduce z by ; (concatenation) [1]
      z is an integer, so this just returns z itself.
   */ Reduce z by * (exponentiation) [2]
      Again, this returns z itself.
  *   Exponentiation: return [1] ** [2]
      This resolves to (z ** z).

```

To make C# ignore the code, we're trying to put it in a comment. However, a line starting with `/` isn't valid in Jelly, because `/` needs an operand. The operand we're using here is `;`, since that also fits perfectly as a semicolon in C#. In fact, the semicolon and empty multi-line comment together make a link that calculates \\$^2z=z^z\\$. Note that the function submission in C# is still valid, as there's no general consensus disallowing multiple statements in an anonymous function submission (e.g. imports).
> 4 votes

# Answer
# 16. Java 8, A000290

```
//0q   GxxJiiiiihhZUUUUUUUNYAxcccccbCLDLxyzUUUUUTxyzJCLOzUUUUUURzyzxyzxyzcccccbbCLGC//*/0e#'
/*
박망희             0#
;*/
    //\u000A\u002F\u002A
n=>//\u002A\u002Fn->
/**/""+n==""+n?5/2>2?1:40-/**/n:n*n//AcaAcAAI(((1)(1)(1)1)((1)(((1)1)1)1)(((1)(1)1)(((1)((1)1)(1)1)1)(((1)(1)(1)(1)1)(((1)(1)((1))(1)1)((1)((1)1)(1)1)(((1)1)(1)(1)1)1)(((1)1)(1)1)(((1)1)1)1)1)1)
//[>[-]<[>+<-],]>>+<[->[>>+<<-]>[<+>-]>[<+>-]<<<]>>>>++++++[<++++++++>-]<<[>+<-]>+.wvWwwWWwwwwwwWwWWWw
                          //ip@
                          //
;/**/
//I01-* h
//
 ;/*""'"""'""""""""""'"""" "'""'"""""""'"""'""""'"'"""""""'"""'""""""'"""'""""""""""*/

```

***Never thought I'd see the day where I would be able to add a Java answer as 16th answer in a polyglot-chain! :D***

1. Try it in C#: \\$a(n)=40-n\\$
2. Try it in brainfuck: \\$a(n)=1+n\text{ mod }2\\$
3. Try it in Runic Enchantments: \\$a(n)=4^n\\$
4. Try it in Jelly: \\$a(n)=n^n\\$
5. Try it in Gol\>\<\>: \\$a(n)=-n\\$
6. Try it in JavaScript: \\$a(n)=1\\$
7. Try it in Parenthetic: \\$a(n)=1\text{ if }x^n+y^n=z^n\text{ has a nontrivial solution in integers, otherwise }a(n)=0\\$
8. Try it in Whitespace: \\$a(n)=3\\$
9. Try it in 05AB1E: \\$a(n)=0\\$
10. Try it in Unreadable: \\$a(n)=n\\$
11. Try it in Grass: \\$a(n) = \lfloor n/10^\left(\lfloor log\_{10}(n)\rfloor\right)\rfloor\\$
12. Try it in Width: \\$a(n)=n+1\text{ with }n\geq2\\$
13. Try it in AlphaBeta: \\$a(n)=1\Vert n\\$
14. Try it in Aheui: \\$a(n)=2\\$
15. Try it in Commentator. \\$a(n)=2n+6\\$
16. Try it in Java 8: \\$a(n)=n^2\\$

**Explanation:**

Let me start by saying that although I've heard from each of these languages before here on CGCC, I'm only skilled with Java, C#, 05AB1E, and Whitespace, and apart from that can read the JavaScript part of the code. The other languages are mostly unfamiliar for me, so I hoped after the changes I had in mind to make the Java interact with C#/JavaScript, most other languages would still work.

The first main thing to tackle was Java's `n->` vs C#/JavaScript's `n=>`. Java support unicode values as part of the code, so using the following:

```
//\u000A\u002F\u002A
n=>//\u002A\u002Fn->

```

Will be interpret as this in C#/JavaScript:

```
//\u000A\u002F\u002A
n=>//\u002A\u002Fn->

```

But as this in Java:

```
//
/*
n=>//*/n->

```

This is because `\u000A` is a line-break, `\u002F` is `/` and `\u002A` is `*` in Java.

Then to differentiate the sequence between Java vs C#/JavaScript I added the following:

```
""+n==""+n?...:n*n

```

where `...` is the existing `5/2>2?1:40-n`, and `n*n` is the Java part of the code for oeis sequence A000290 (squares a.k.a. \\$a(n)=n^2\\$).

Why does this work? In Java Strings are Objects, where `==` is used to check if references of objects are pointing to the same place (or to check if primitives are equal), and the actual `Object.equals(Object)` has to be used to check if the values of these Objects are the same. So `""+n==""+n` will be falsey in Java, but truthy in C#/JavaScript.

---

After that was tackled (by re-using the existing newlines to not break the Whitespace program), some things had to be fixed. Four of the existing programs were failing now: Runic Enchantments, Jelly, Unreadable, and Commentator.

The fix for Unreadable was easy. We added four `""""` before the first `'`, so we simply put the `'` somewhere earlier (I placed it at the end of the first line), and remove the leading `'""""` from the Unreadable part of the code at the bottom.

After that came Jelly, which was giving an `IndexError: pop from empty list`. I'm not too skilled in Jelly, so I don't exactly know why it gave this error. If I remember correctly the last line will be the main-link of a Jelly program, and because the code in that last line doesn't use any of the other links, everything else should be ignored. But somehow the part `""+n==""+n` still gave some issues. I was able to fix this by adding `/**/` in front of that line.

As for Runic Enchantments, it didn't output anything anymore. *@Draco18s* pointed out to me that Runic Enchantments starts at all `>` simultaneously, but only the `>2?1:40-n/` and `/ip@` were relevant. This was a huge help to understand the flow of the Runic Enchantments program, and I was able to fix the path by adding a `/**/` at `>2?1:40-/**/n:n*n`, and changing the positions of the `//ip@`, `//`, and space on the last line.

All that's left was Commentator. At that point I realized that my previous fixes of adding `/**/` weren't such a good idea after all, since it would output a bunch of additional rubbish due to the builtins `/*` (convert active to unicode character and output) and `*/` (output active as number).. \>.\> After a bit of fiddling around and trying some things, the fix turned out to be very easy: I've added an `e` before the `#` on the first line. `e#` is the builtin to negate an active, fixing the issues caused by the code I added (apparently).
> 4 votes

# Answer
# 6. JavaScript (Node.js), A000012

```
//
n=>5/2>2?1:40-n//
//[>[-]<[>+<-],]>>+<[->[>>+<<-]>[<+>-]>[<+>-]<<<]>>>>++++++[<++++++++>-]<<[>+<-]>+.
               //ip@
               //
;/**/
//I01-* h
//
 ;/**/

```

C# (A022996): Since `5/2==2` the function returns `40-n` (Line 2)

BF (A000034): The added part only pushes the whole tape one cell to the right, others unchanged (Line 2-3)

Runic (A000302): The `?` after `2` skips the `1:`, and other operations follows from `4` (Line 2)

Jelly (A000312): Unchanged last line

Gol\>\<\> (A001489): Unchanged first column

JS(ES6) (A000012): Since `5/2>2` the function returns `1` (Line 2)

Sneaked the ternary `5/2>2?1:40-n` into the C# part. In C# since `5/2==2` the function returns `40-n`, while in JS `5/2>2` the functions returns 1. The C-style comments made it nearly impossible to add more practical languages (specifically C and Python). More spaces are added on lines 4-5 to ensure that the Runic part works.
> 2 votes

# Answer
# 8. Whitespace, A010701

```
//

n=>5/2>2?1:40-n//(((1)(1)(1)1)((1)(((1)1)1)1)(((1)(1)1)(((1)((1)1)(1)1)1)(((1)(1)(1)(1)1)(((1)(1)((1))(1)1)((1)((1)1)(1)1)(((1)1)(1)(1)1)1)(((1)1)(1)1)(((1)1)1)1)1)1)
//[>[-]<[>+<-],]>>+<[->[>>+<<-]>[<+>-]>[<+>-]<<<]>>>>++++++[<++++++++>-]<<[>+<-]>+.
               //ip@
               //
;/**/
//I01-* h
//
 ;/**/

```

Try it online!

C#
Brainfuck
Runic
Jelly
Gol\>\<\>
Javascript
Paranthetic

I have no idea how Whitespace works. I tried super hard to multiply the input with another value, but it kept complaining about infix arithmetic, so as I had input working, output working, and push-value-to-stack working, so I just went with that.

The input value appears to get lost when pushing `3` to the stack, but oh well. Enjoy a sequence of 3s. The program *does technically take input* it just ends up discarding it.

I also don't know how Paranthetic works, so I can't actually verify that submission as valid, but as far as I can tell the Whitespace code doesn't interfere.

Future answers: be aware that tabs in Runic are a single instruction wide and play havoc with code layout.
> 2 votes

# Answer
# 11. Grass, A000030

```
//0q

n=>5/2>2?1:40-n//(((1)(1)(1)1)((1)(((1)1)1)1)(((1)(1)1)(((1)((1)1)(1)1)1)(((1)(1)(1)(1)1)(((1)(1)((1))(1)1)((1)((1)1)(1)1)(((1)1)(1)(1)1)1)(((1)1)(1)1)(((1)1)1)1)1)1)
//[>[-]<[>+<-],]>>+<[->[>>+<<-]>[<+>-]>[<+>-]<<<]>>>>++++++[<++++++++>-]<<[>+<-]>+.wvWwwWWwwwwwwWwWWWw
               //ip@
               //
;/**/
//I01-* h
//
 ;/*'""""""'""" '""""""""""'"""""'""'"""""""'"""'""""'"'"""""""'"""'""""""'"""'""""""""""*/

```

Try it online!

Grass ignores all characters except `w`, `v` and `W`; conveniently, these three characters are ignored by several of the previously used languages. Luckily, sequence A000030 (return the initial digit in base 10) was still available, as coding even slightly complicated functions in Grass is beyond my ability.

C#
brainfuck
Runic
Jelly
Gol\>\<\>
JavaScript
Parenthetic
Whitespace
05AB1E
Unreadable

The relevant part for Grass is `wvWwwWWwwwwwwWwWWWw`. Here is my (probably flawed) understanding of how it works: the stack is initialized as `OUT::SUCC::w::IN::ε` (that `w` is just the character `w`). Each instruction adds an element to the stack (they are never popped); the number of `w`s or `W`s indicates how deep to go in the stack; `v` separates instructions.

```
wv        # identity
Www       # identity OUT
WWwwwwww  # identity IN (read in 1 character)
Ww        # apply the function identity IN
WWWw      # apply the function identity OUT to the value at the top of the stack

```

If the input is `1234`, at the end, the stack probably looks like this: `1::1::id IN::id OUT::id::OUT::SUCC::w::IN::ε`.

It could be made shorter (don't need to define `id OUT` for example), but I stopped as soon as I found a version which worked.

If someone who knows Grass wants to correct/improve the explanation, please edit my answer!
> 2 votes

# Answer
# 17. Pepe, A000578

```
//0q   GxxJiiiiihhZUUUUUUUNYAxcccccbCLDLxyzUUUUUTxyzJCLOzUUUUUURzyzxyzxyzcccccbbCLGC//*/0e#'
/*
박망희		   		0#
;*/
 	//\u000A\u002F\u002A
n=>//\u002A\u002Fn->
/**/""+n==""+n?5/2>2?1:40-/**/n:n*n//AcaAcAAI(((1)(1)(1)1)((1)(((1)1)1)1)(((1)(1)1)(((1)((1)1)(1)1)1)(((1)(1)(1)(1)1)(((1)(1)((1))(1)1)((1)((1)1)(1)1)(((1)1)(1)(1)1)1)(((1)1)(1)1)(((1)1)1)1)1)1)
//[>[-]<[>+<-],]>>+<[->[>>+<<-]>[<+>-]>[<+>-]<<<]>>>>++++++[<++++++++>-]<<[>+<-]>+.wvWwwWWwwwwwwWwWWWw
                          //ip@
                          //rEeE rEeeEe reEE
;/**/
//I01-* h
//
 ;/*""'"""'""""""""""'"""" "'""'"""""""'"""'""""'"'"""""""'"""'""""""'"""'""""""""""*/

```

Online Interpreter

C#
Brainfuck
Runic Enchantments
Jelly
Gol\>\<\>
Javascript (Node.js) (All 1s)
Parenthetic
Whitespace (All 3s)
05AB12 (All 0s)
Unreadable
Grass
Width
AlphaBeta
Aheui (All 2s)
Commentator
Java

You'll have to excuse the Pepe link for not containing the full source: The interpreter disregards any code that is not Pepe (lit. any character not in the set `RE re`) and so its short link doesn't bother encoding it. Ditto input values.

Computes \\$a(n) = n^3\\$

The AlphaBeta has started throwing errors after writing output, but as a prior answer injected that issue I left it alone. I had planned on fixing it for this answer, but I need to spend some time digging into the jump offsets to resolve the issue. The error with inputs `>0` are easy to fix, but giving it `0` will produce the same error and it will take time to relearn the code in order to fix the offset for it. I wish I could use `W` instead of `UUUUUUUUUU`, but it plays havoc with the Grass code.
> 2 votes

# Answer
# 1. C# (Visual C# Interactive Compiler) A022996

```
n=>40-n

```

Also works in C# (.NET Core), C# (Mono C# compiler), C# (Mono C# Shell), and C# (Visual C# Compiler)

Try it online!
> 1 votes

# Answer
# 7. Parenthetic, A019590

```
//
n=>5/2>2?1:40-n//(((1)(1)(1)1)((1)(((1)1)1)1)(((1)(1)1)(((1)((1)1)(1)1)1)(((1)(1)(1)(1)1)(((1)(1)((1))(1)1)((1)((1)1)(1)1)(((1)1)(1)(1)1)1)(((1)1)(1)1)(((1)1)1)1)1)1)
//[>[-]<[>+<-],]>>+<[->[>>+<<-]>[<+>-]>[<+>-]<<<]>>>>++++++[<++++++++>-]<<[>+<-]>+.
               //ip@
               //
;/**/
//I01-* h
//
 ;/**/

```

C# (A022996)

BF (A000034)

Runic (A000302)

Jelly (A000312)

Gol\>\<\> (A001489)

JS(ES6) (A000012)

Parenthetic (A019590)

Parenthetic ignores everything but the `(` and `)` characters. I've had to insert `1`s before every closing parenthesis to stop Jelly from freaking out though (EDIT: I left one `)` unpreceded by a 1, so apparently not all of them need one, but it's too late to golf it down now). The actual code defines a lambda called `((()))`, that can be called on a number to yield the result (1-indexed).
> 1 votes

# Answer
# 9. 05AB1E, A000004

```
//0q

n=>5/2>2?1:40-n//(((1)(1)(1)1)((1)(((1)1)1)1)(((1)(1)1)(((1)((1)1)(1)1)1)(((1)(1)(1)(1)1)(((1)(1)((1))(1)1)((1)((1)1)(1)1)(((1)1)(1)(1)1)1)(((1)1)(1)1)(((1)1)1)1)1)1)
//[>[-]<[>+<-],]>>+<[->[>>+<<-]>[<+>-]>[<+>-]<<<]>>>>++++++[<++++++++>-]<<[>+<-]>+.
               //ip@
               //
;/**/
//I01-* h
//
 ;/**/

```

C# (Visual C# Interactive Compiler)
brainfuck
Runic Enchantments
Jelly
Gol\>\<\>
JavaScript (Node.js)
Parenthetic
Whitespace
05AB1E
> 1 votes

# Answer
# 10. Unreadable, A001477

```
//0q

n=>5/2>2?1:40-n//(((1)(1)(1)1)((1)(((1)1)1)1)(((1)(1)1)(((1)((1)1)(1)1)1)(((1)(1)(1)(1)1)(((1)(1)((1))(1)1)((1)((1)1)(1)1)(((1)1)(1)(1)1)1)(((1)1)(1)1)(((1)1)1)1)1)1)
//[>[-]<[>+<-],]>>+<[->[>>+<<-]>[<+>-]>[<+>-]<<<]>>>>++++++[<++++++++>-]<<[>+<-]>+.
               //ip@
               //
;/**/
//I01-* h
//
 ;/*'""""""'""" '""""""""""'"""""'""'"""""""'"""'""""'"'"""""""'"""'""""""'"""'""""""""""*/

```

Try it online!

C#
Brainfuck
Runic
Jelly
Gol\>\<\>
Javascript
Paranthetic
Whitespace
05AB1E

Unreadable, as its name suggests, is unreadable. In order to program it I had to use a template and then convert from readable text to Unreadable code.

```
[A=READ()];DO{(A+1)?:BOTH(PRINT(A),[A=READ()])}
[A=READ()]: '""""""'"""'""""""""""
PRINT(A): '"'"""""""'"""
A?: '""'"""
Functioning:
['""""""'"""'""""""""""];'"""""{('""'"""""""'""")?:'""""('"('"""""""'"""),['""""""'"""'""""""""""])}

```

All it does is read each character in the input and output it. One of the more boring sequences, but good for a language that's difficult to work with. I also toyed with using the sequence A000030 before getting the loop to work.

Working via remote desktop is a pain, you think things work, do all the links, then realize that one of them broke and didn't notice.
> 1 votes

# Answer
# 14. Aheui, A007395

Slightly changed to make AlphaBeta works.

```
//0q   GxxJiiiiihhZUUUUUUUNYAxcccccbCLDLxyzUUUUUTxyzJCLOzUUUUUURzyzxyzxyzcccccbbCLGC
/*
박망희*/

n=>5/2>2?1:40-n//AcaAcAAI(((1)(1)(1)1)((1)(((1)1)1)1)(((1)(1)1)(((1)((1)1)(1)1)1)(((1)(1)(1)(1)1)(((1)(1)((1))(1)1)((1)((1)1)(1)1)(((1)1)(1)(1)1)1)(((1)1)(1)1)(((1)1)1)1)1)1)
//[>[-]<[>+<-],]>>+<[->[>>+<<-]>[<+>-]>[<+>-]<<<]>>>>++++++[<++++++++>-]<<[>+<-]>+.wvWwwWWwwwwwwWwWWWw
               //ip@
               //
;/**/
//I01-* h
//
 ;/*'""""""'""" '""""""""""'"""""'""'"""""""'"""'""""'"'"""""""'"""'""""""'"""'""""""""""*/

```

Try it online!

Aheui dismiss any non-Korean character, so `박망희` excuted, which prints `2` and terminates.

C#
Brainfuck
Runic Enchantments
Jelly
Gol\>\<\>
Javascript (Node.js)
Parenthetic
Whitespace
05AB12
Unreadable
Grass
Width
AlphaBeta
Aheui
> 1 votes

# Answer
# 2. brainfuck, A000034

```
n=>40-n
//[>[-]<[>+<-],]>>+<[->[>>+<<-]>[<+>-]>[<+>-]<<<]>>>>++++++[<++++++++>-]<<[>+<-]>+.

```

Try it online!

C#
> 0 votes

# Answer
# 3. Runic Enchantments, A000302

```
n=>40-n//
//[>[-]<[>+<-],]>>+<[->[>>+<<-]>[<+>-]>[<+>-]<<<]>>>>++++++[<++++++++>-]<<[>+<-]>+.
       //ip@
       //

```

Try it online!

C#

BF

If you need help keeping the Runic functional, there is the Esoteric IDE as well as my own IDE (built in Unity3D) in the master branch of Runic's git repo. Esoteric IDE doesn't handle displaying the IP directionality very well (primarily my own inability to add such to the existing framework).

All the BF creates a bunch of IPs that self terminate due to performing invalid actions (mainly due to stack underflow) while the `>` in the C# populates the stack with a `4`, bounces of the comment makers (mirrors in Runic), reaching `ip@` to execute `x^4` on an input x and print the result.
> 0 votes

# Answer
# 5. Gol\>\<\>, A001489

```
//
n=>40-n//
//[>[-]<[>+<-],]>>+<[->[>>+<<-]>[<+>-]>[<+>-]<<<]>>>>++++++[<++++++++>-]<<[>+<-]>+.
       //ip@
       //
;/**/
//I01-* h
//
 ;/**/

```

Try it online!

C#
Brainfuck
Runic
Jelly

Use single-line comment markers in C# to redirect the Fish IP to the operative code, `I01-*h`, reading input, multiplying by -1, and outputting the result. Gol\>\<\> made reading input and dumping the stack as a number easy compared to raw \>\<\>.

Spaces inserted to insure the proper flow of the Fish and Runic IPs, where both C# and Jelly ignore the leading whitespace on the last line (and is a NOP cell in both fungoids).
> 0 votes

# Answer
# 12. Width, A020725

```
//0q

n=>5/2>2?1:40-n//AcaAcAAI(((1)(1)(1)1)((1)(((1)1)1)1)(((1)(1)1)(((1)((1)1)(1)1)1)(((1)(1)(1)(1)1)(((1)(1)((1))(1)1)((1)((1)1)(1)1)(((1)1)(1)(1)1)1)(((1)1)(1)1)(((1)1)1)1)1)1)
//[>[-]<[>+<-],]>>+<[->[>>+<<-]>[<+>-]>[<+>-]<<<]>>>>++++++[<++++++++>-]<<[>+<-]>+.wvWwwWWwwwwwwWwWWWw
               //ip@
               //
;/**/
//I01-* h
//
 ;/*'""""""'""" '""""""""""'"""""'""'"""""""'"""'""""'"'"""""""'"""'""""""'"""'""""""""""*/

```

1-indexed. Outputs by exit code.

Try it online!

The only relevant characters to Width are `a-zA-Z`. The code Width runs is the following:

```
qnnAcaAcAAI

```

The first three characters, `qnn`, are no-ops. `Ac` reads an integer from input, `a` is a no-op, and then `AcAA` increments the integer by one. `I` ends the program, and the top of the stack is becomes the exit code. All other letters in the program are ignored since the program terminated.

C#
brainfuck
Runic Enchantments
Jelly
Gol\>\<\>
JavaScript
Parenthetic
Whitespace
05AB1E
Unreadable
Grass
> 0 votes

# Answer
# 13. AlphaBeta, A162672

```
//0q   GxxJiiiiihhZUUUUUUUNYAxcccccbCLDLxyzUUUUUTxyzJCLOzUUUUUURzyzxyzxyzcccccbbCLGC

n=>5/2>2?1:40-n//AcaAcAAI(((1)(1)(1)1)((1)(((1)1)1)1)(((1)(1)1)(((1)((1)1)(1)1)1)(((1)(1)(1)(1)1)(((1)(1)((1))(1)1)((1)((1)1)(1)1)(((1)1)(1)(1)1)1)(((1)1)(1)1)(((1)1)1)1)1)1)
//[>[-]<[>+<-],]>>+<[->[>>+<<-]>[<+>-]>[<+>-]<<<]>>>>++++++[<++++++++>-]<<[>+<-]>+.wvWwwWWwwwwwwWwWWWw
               //ip@
               //
;/**/
//I01-* h
//
 ;/*'""""""'""" '""""""""""'"""""'""'"""""""'"""'""""'"'"""""""'"""'""""""'"""'""""""""""*/

```

Try it online!

I had originally planned to use sequence A000030 and the code `JCL`, but that got yoinked (I don't blame them, its a good sequence for languages that take input as single bytes). The original code for this entry after having to pick a new sequence was:

```
JiiiiihhZUUUUUNYAxcccccbCLDLxyzUUUUTTxxyzJCLOzWRxyxyzcccccbbCL
^                                                                 Read input (single byte)
                 ^          ^^^      ^^^^    ^  ^^^^^             Clear regisers
        ^                                            ^^^^^^^^^    Input = 0: print 0
 ^^^^^^^ ^^^^^                 ^^^^^^         ^                   Set jump locations
                  ^^^^^^^^                                        Print `1`
                          ^^                                      Print initial byte
                                         ^^^                      Read and print input
                                            ^                     (and loop)

```

Sequences of `xxx` or `xyzxyz` are useful spacers to make the jump-to targets easy values (46 is easier as "5\*10-4"--9 instructions--than "4\*10+6--ten instructions--but 50 is even simpler: only five). You'll see a fair few of those.

But as there are other bytes on the first line, the jump-to codels needed some new values and that turned into:

```
//0q   xxxJiiiiihhZUUUUUUNYAxcccccbCLDLxyzUUUUUTxxyzJCLOzWRxyxyzcccccbbCL

```

Avoiding executing this code as Width code just involved wrapping it in `G` to make it a string literal (which does nothing important in AlphaBeta), a command to pop the top of the stack, and then some extra `W` to make alpha beta not crash when exiting:

```
//0q   GxxJiiiiihhZUUUUUUNYAxcccccbCLDLxyzUUUUUTxxyzJCLOzWWWWWWRxyxyzcccccbbCLGw

```

To avoid conflicts with Grass, though, instead of popping the command with `w` `C` is used instead. Then the "exit program" jump is replaced with `UUUUUU` instead of `WWWWWW` This does leave the IP somewhere in the middle of the rest of the junk code, but far enough out that it doesn't print any errors. Any number of additional `U`s can be added in pairs if this becomes a problem.

```
//0q   GxxJiiiiihhZUUUUUUNYAxcccccbCLDLxyzUUUUUTxxyzJCLOzUUUUUURxyxyzcccccbbCLGC

```

The additional `i` that Runic ends up executing is a NOP on valid inputs as no-input-left-to-read pushes nothing to the stack ("reading all input" is a pain in Runic).

C#
brainfuck
Runic Enchantments
Jelly
Gol\>\<\>
JavaScript
Parenthetic
Whitespace
05AB1E
Unreadable
Grass
Width
> 0 votes

# Answer
# 18. \]=\[, A010716, the all 5's sequence

```
//0q   GxxJiiiiihhZUUUUUUUNYAxcccccbCLDLxyzUUUUUTxyzJCLOzUUUUUURzyzxyzxyzcccccbbCLGC//*/0e#'[=====[===]]=[[==========]]=[
/*]
박망희             0#
;*/
    //\u000A\u002F\u002A
n=>//\u002A\u002Fn->
/**/""+n==""+n?5/2>2?1:40-/**/n:n*n//AcaAcAAI(((1)(1)(1)1)((1)(((1)1)1)1)(((1)(1)1)(((1)((1)1)(1)1)1)(((1)(1)(1)(1)1)(((1)(1)((1))(1)1)((1)((1)1)(1)1)(((1)1)(1)(1)1)1)(((1)1)(1)1)(((1)1)1)1)1)1)
//[>[-]<[>+<-],]>>+<[->[>>+<<-]>[<+>-]>[<+>-]<<<]>>>>++++++[<++++++++>-]<<[>+<-]>+.wvWwwWWwwwwwwWwWWWw
                          //ip@
                          //rEeE rEeeEe reEE
;/**/
//I01-* h
//
 ;/*""'"""'""""""""""'"""" "'""'"""""""'"""'""""'"'"""""""'"""'""""""'"""'""""""""""*/

```

This language isn't on TIO and its only interpreter is written itself in another interpreted language, which is *also* not on TIO. And the one that didn't play nice with Brainfuck last week at the last minute, but I figured out what was wrong a few hours after posting the Pepe answer, so I saved it for this week. Being a language not on TIO I was considering this one an ace-in-the-hole that could easily be tacked onto just about ANY entry and continue the chain.

Put the interpretter code into the "code" box at the top, code from the answer in the input, and click run and get an output (plus some extra junk that is always printed).

The operational portion of the \]=\[ is this at the end of the first line:

```
[=====[===]]=[[==========]]=[

```

Its that trailing `[` that played havoc with the Brainfuck (the rest being ignored, due to how `[` and `]` are handled by Brainfuck) and once I looked at the Brainfuck spec again I realized the problem and that all I had to do was insert a `]` somewhere after the first line (as the \]=\[ interpreter does not read newlines) and before the Brainfuck. I chose the 2nd line.

C#
Brainfuck
Runic
Jelly
Gol\>\<\>
JavaScript (Node.js)
Paranthetic
Whitespace
05AB1E
Unreadable
Grass
Width
AlphaBeta
Aheui (esotope)
Commentator
Java (OpenJDK 8)
Pepe
> 0 votes

# Answer
# 19. Actually, A005843 (2\*n)

```
//0q   GxxJiiiiihhZUUUUUUUNYAxcccccbCLDLxyzUUUUUTxyzJCLOzUUUUUURzyzxyzxyzcccccbbCLGC//*/0e#,2*1z⌂'[=====[===]]=[[==========]]=[
/*]
박망희		   		0#
;*/
 	//\u000A\u002F\u002A
n=>//\u002A\u002Fn->
/**/""+n==""+n?5/2>2?1:40-/**/n:n*n//AcaAcAAI(((1)(1)(1)1)((1)(((1)1)1)1)(((1)(1)1)(((1)((1)1)(1)1)1)(((1)(1)(1)(1)1)(((1)(1)((1))(1)1)((1)((1)1)(1)1)(((1)1)(1)(1)1)1)(((1)1)(1)1)(((1)1)1)1)1)1)
//[>[-]<[>+<-],]>>+<[->[>>+<<-]>[<+>-]>[<+>-]<<<]>>>>++++++[<++++++++>-]<<[>+<-]>+.wvWwwWWwwwwwwWwWWWw
                          //ip@
                          //rEeE rEeeEe reEE
;/**/
//I01-* h
//
 ;/*""'"""'""""""""""'"""" "'""'"""""""'"""'""""'"'"""""""'"""'""""""'"""'""""""""""*/

```

Try it online!

Operational part: `,2*1z⌂` (first line)

As  terminates the program, none of the code after it has any effect, and none of the symbols before it result in any output or pollute operational memory adversely. Section exists within a comment (C#, JS, Java), only contains ignored characters (Commentator, \]=\[, Pepe, Aheui...), is not on the last line (Jelly), or otherwise in un-executed parts of the code (Gol\>\<\>, Runic, AlphaBeta).

C#
Brainfuck
Runic
Jelly
Gol\>\<\>
JavaScript (Node.js)
Paranthetic
Whitespace
05AB1E
Unreadable
Grass
Width
AlphaBeta
Aheui (esotope)
Commentator
Java (OpenJDK 8)
Pepe
\]=\[ (link not possible, see #18 for instructions)
> 0 votes

# Answer
# 20. Neim, A008592 (10\*n)

```
//0q   ÷GxJiiiiihhZUUUUUUUNYAxcccccbCLDLxyzUUUUUTxyzJCLOzUUUUUURzyzxyzxyzcccccbbCLxGC//*/0e#§≈2*1z⌂'>[=====[===]]=[[==========]]=[
/*]
박망희		   		0#
;*/
 	//\u000A\u002F\u002A
n=>//\u002A\u002Fn->
/**/""+n==""+n?5/2>2?1:40-/**/n:n*n//AcaAcAAI(((1)(1)(1)1)((1)(((1)1)1)1)(((1)(1)1)(((1)((1)1)(1)1)1)(((1)(1)(1)(1)1)(((1)(1)((1))(1)1)((1)((1)1)(1)1)(((1)1)(1)(1)1)1)(((1)1)(1)1)(((1)1)1)1)1)1)
//[>[-]<[>+<-],]>>+<[->[>>+<<-]>[<+>-]>[<+>-]<<<]>>>>++++++[<++++++++>-]<<[>+<-]>+.wvWwwWWwwwwwwWwWWWw
                          //ip@
                          //rEeE rEeeEe reEE
;/**/
//I01-* h
//
 ;/*""'"""'""""""""""'"""" "'""'"""""""'"""'""""'"'"""""""'"""'""""""'"""'""""""""""*/

```

Try it online!

I have no idea how the heck Neim works. I know what the code here ends up doing, but I have no idea how the language itself works.

Also turns out I messed up the Brainfuck with #19. Due to command conflicts between multiple languages, changing Actually's input to `§` and then coercing it to an int with  was the optimal solution.

C#
Brainfuck
Runic
Jelly
Gol\>\<\>
JavaScript (Node.js)
Paranthetic
Whitespace
05AB1E
Unreadable
Grass
Width
AlphaBeta
Aheui (esotope)
Commentator
Java (OpenJDK 8)
Pepe
\]=\[ (link not possible, see #18)
Actually
> 0 votes

# Answer
# 21. Flobnar, A010709 (All 4s)

```
//0q   ÷GxJiiiiihhZUUUUUUUNYAxcccccbCLDLxyzUUUUUTxyzJCLOzUUUUUURzyzxyzxyzcccccbbCLxGC//*/0e#§≈2*1z⌂'>[=====[===]]=[[==========]]=[
/*]
박망희		   		0#
;*/
 	//\u000A\u002F\u002A
n=>//\u002A\u002Fn->
/**/""+n==""+n?5/2>2?1:40-/**/n:n*n//AcaAcAAI(((1)(1)(1)1)((1)(((1)1)1)1)(((1)(1)1)(((1)((1)1)(1)1)1)(((1)(1)(1)(1)1)(((1)(1)((1))(1)1)((1)((1)1)(1)1)(((1)1)(1)(1)1)1)(((1)1)(1)1)(((1)1)1)1)1)1)
//[>[-]<[>+<-],]>>+<[->[>>+<<-]>[<+>-]>[<+>-]<<<]>>>>++++++[<++++++++>-]<<[>+<-]>+.wvWwwWWwwwwwwWwWWWw
                          //ip!4@
                          //rEeE rEeeEe reEE
;/**/
//I01-* h
//
 ;/*""'"""'""""""""""'"""" "'""'"""""""'"""'""""'"'"""""""'"""'""""""'"""'""""""""""*/

```

Try it online!

Flobnar starts at `@` and expands outwards evaluating items as the rules dictate (`@` evaluates to whatever's on its left, `4` evaluates to `4`, `+` evaluates to whatever's on the left summed with whatever's on the right, etc). As the placement of the `@` only comes into contact with Runic, a simple `!` prevents alteration of Runic's stack.

Given that Flobnar's input metric is "one byte" and goes into an infinite loop if there are no bytes to read, I decided not to bother with anything more complex.

### Previous languages

C#
Brainfuck
Runic
Jelly
Gol\>\<\>
JavaScript (Node.js)
Paranthetic
Whitespace
05AB1E
Unreadable
Grass
Width
AlphaBeta
Aheui (esotope)
Commentator
Java (OpenJDK 8)
Pepe \]=\[ (link not possible, see #18)
Actually
Neim
> 0 votes

---
Tags: math, code-challenge, sequence, polyglot, answer-chaining
---


# Question
Title: Write The Shortest Program To Check If A Binary Tree Is Balanced
For each node in a balanced binary tree, the maximum difference in the heights of the left child subtree and the right child subtree are at most 1.

The height of a binary tree is the distance from the root node to the node child that is farthest from the root.

Below is an example:

```
           2 <-- root: Height 1
          / \
         7   5 <-- Height 2
        / \   \
       2   6   9 <-- Height 3
          / \  /
         5  11 4 <-- Height 4

```

Height of binary tree: 4

The following are binary trees and a report on whether or not they are balanced:

The tree above is **unbalanced**.

The above tree is **balanced**.

Write the shortest program possible that accepts as input the root of a binary tree and returns a falsey value if the tree is unbalanced and a truthy value if the tree is balanced.

**Input**

The root of a binary tree. This may be in the form of a reference to the root object or even a list that is a valid representation of a binary tree.

**Output**

**Returns truthy value:** If the tree is balanced

**Returns falsey value:** If the tree is **un**balanced.

**Definition of a Binary Tree**

A tree is an object that contains a value and either two other trees or pointers to them.

The structure of the binary tree looks something like the following:

```
typedef struct T
{
   struct T *l;
   struct T *r;
   int v;
}T;

```

If using a list representation for a binary tree, it may look something like the following:

```
[root_value, left_node, right_node]

```

# Answer
> 8 votes
# Jelly, 11 bytes

```
ḊµŒḊ€IỊ;ß€Ạ

```

Try it online!

The empty tree is represented by `[]`.

# Answer
> 3 votes
# Prolog (SWI), 49 bytes

```
N+_/B/C:-X+B,Y+C,abs(X-Y)<2,N is max(X,Y)+1.
0+e.

```

Try it online!

Represents trees as `Value/Left_Child/Right_Child`, with the empty tree being the atom `e`. Defines `+/2`, which outputs through success or failure, with an unbound variable (or one already equal to the tree's height) on the left and the tree on the right--if the height argument is unacceptable, add 9 bytes to define `-T:-_+T.`.

```
N + _/B/C :-            % If the second argument is a tree of the form _Value/B/C,
    X+B,                % X is the height of its left child which is balanced,
    Y+C,                % Y is the height of its right child which is balanced,
    abs(X-Y) < 2,       % the absolute difference between X and Y is strictly less than 2,
    N is max(X,Y)+1.    % and N is the height of the full tree.
0 + e.                  % If, on the other hand, the second argument is e, the first is 0.

```

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

```
h=([l,r])=>l?(d=h(l)-h(r))*d<2?1+h(d>0?l:r):NaN:1

```

Try it online!

-9 bytes by Arnauld.

---

# JavaScript, 58 bytes

```
h=([l,r])=>l?(l=h(l),r=h(r),m=l>r?l:r,m+m-l-r<2?m+1:NaN):1

```

Try it online!

Use `[]` for null, and `[left, right, value]` for nodes.

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

```
f@_[x_,y_]:=f@x&&f@y&&-2<Depth@x-Depth@y<2;f@_=1>0

```

Use `Null` for null, `value[left, right]` for nodes. For example, the following tree is written as `2[7[2[Null, Null], 6[5[Null, Null], 11[Null, Null]]], 5[Null, 9[4[Null, Null], Null]]]`.

```
    2
   / \
  7   5
 / \   \
2   6   9
   / \  /
  5  11 4

```

Try it online!

# Answer
> 3 votes
# Python 3.8 (pre-release), ~~133~~ 125 bytes

```
b=lambda t:((max(l[0],r[0])+1,abs(l[0]-r[0])<2)if(l:=b(t[1]))[1]and(r:=b(t[2]))[1]else(0,0))if t else(0,1)
h=lambda t:b(t)[1]

```

Try it online!

Takes a tree in the "list" format: A node is `[value, left, right]` with `left` and `right` being nodes.

Invoke the function `h`.

Returns `0` or `False` for an unbalanced tree. Returns `1` or `True` for a balanced tree.

## Ungolfed:

```
# Returns tuple (current height, subtrees are balanced (or not))
def balanced(tree):
  if tree: # [] evaluates to False
    left = balanced(tree[1])
    right = balanced(tree[2])
    # If  the subtrees are not both balanced, nothing to do, just pass it up
    if left[1] and right[1]:
      height = max(left[0], right[0]) + 1
      subtrees_balanced = abs(left[0] - right[0]) < 2
    else:
      height = 0 # Value doesn't matter, will be ignored
      subtrees_balanced = False
  else:
    height = 0
    subtrees_balanced = True
  return (height, subtrees_balanced)

def h(tree):
  return balanced(tree)[1]

```

-10: Reversed logic to get rid of `not`s

If taking arguments in the middle of a call is allowed, this could be shortened to (115 bytes)

```
(b:=lambda t:((max(l[0],r[0])+1,abs(l[0]-r[0])<2)if(l:=b(t[1]))[1]and(r:=b(t[2]))[1]else(0,0))if t else(0,1))(_)[1]

```

with `_` being the tree to check.

# Answer
> 2 votes
# JavaScript, 162 bytes

```
f=x=>{for(f=0,s=[[x,1]];s[0];){if(!((d=(t=s.pop())[0]).a&&d.b||f))f=t[1];if(f&&t[1]-f>1)return 0;if(d.a)s.push([d.a,t[1]+1]);if(d.b)s.push([d.b,t[1]+1])}return 1}

```

Try it online!

The format of the input is an object

```
root={a:{node},b:{node},c:value}

```

## Explanation

```
for(f=0,s=[[x,1]];s[0];){if(!((d=(t=s.pop())[0]).a&&d.b||f))f=t[1]

```

Performing breadth first search find the depth of the first node which is missing one or more branches.

```
if(f&&t[1]-f>1)return 0;if(d.a)s.push([d.a,t[1]+1]);if(d.b)s.push([d.b,t[1]+1])}

```

Continuing the breadth first search, return zero if any element is two deeper than the depth of the first node missing branches.

```
return 1}

```

If no such node is found, return 1

# Answer
> 1 votes
# Julia, 56 bytes

```
f(t)=t!=()&&(-(f.(t.c)...)^2<2 ? maximum(f,t.c)+1 : NaN)

```

With the following struct representing the binary tree:

```
struct Tree
    c::NTuple{2,Union{Tree,Tuple{}}}
    v::Int
end

```

`c` is a tuple representing the left and right nodes and the empty tuple `()` is used to signal the absence of a node.

Falsey value is `NaN`, any integer is truthy.

# Answer
> 0 votes
# Kotlin, 67 bytes

```
fun N.c():Int=maxOf(l?.c()?:0,r?.c()?:0)+1
fun N.b()=l?.c()==r?.c()

```

Where

```
data class N(val l: N? = null, val r: N? = null, val v: Int = 0)

```

Try it online!

# Answer
> 0 votes
# Python 2, ~~99~~ ~~96~~ 94 bytes

```
lambda A:A==[]or(abs(D(A[1])-D(A[2]))<2)*f(A[1])*f(A[2])
D=lambda A:A>[]and-~max(map(D,A[1:]))

```

Try it online!

3 bytes from Jo King.

Takes input as: empty node is `[]`, and other nodes are `[<value>, <leftNode>, <rightNode>]`. Outputs `0/1` for False/True.

# Answer
> 0 votes
# C, 117 bytes

```
h(T*r){r=r?1+h(h(r->l)>h(r->r)?r->l:r->r):0;}b(T*r){return r->l&&!b(r->l)||r->r&&!b(r->r)?0:abs(h(r->l)-h(r->r))<=1;}

```

Struct implementation is the following:

```
 typedef struct T
    {
        struct T * l;

        struct T * r;

        int v;

    } T;

```

Try This on JDoodle

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


title: Last k digits of Powers of 2

text:
# Question
Title: Last k digits of Powers of 2
> For any integer \\$r\\$, there exists a power of 2 each of whose last \\$r\\$ digits are either 1 or 2.

Given \\$r\\$, find the smallest \\$x\\$ such that \\$2^x\bmod{10^r}\\$ consists of only 1 or 2.

For \\$r=2\\$, \\$x=9\\$, since \\$2^9=5\color{blue}{\textrm{12}}\\$
For \\$r=3\\$, \\$x=89\\$, since \\$2^{89}=618970019642690137449562\color{blue}{\textrm{112}}\\$
Note: for \\$r=4\\$, \\$x\\$ is \\$=89\\$ (again)

Input : \\$r \leq 100\\$

Output : \\$x\\$

Eg.

> Input : 2
> Ouput : 9
>
> Input : 3
> Ouput : 89

The program should run in a reasonable amount of time.

EDIT: The oeis sequence for this challenge is A147884.

# Answer
## Python, 166 chars

```
k,f,g=1,4,16
i=j=2
n=input()
m=10**n
a=lambda c:c('')-1-i or c('1')+c('2')-c('')+1
while i<=n:
 while a(str(j)[-i:].count):j,k=j*g%m,k+f
 i,g,f=i+1,g**5%m,f*5
print k

```
> 4 votes

# Answer
# Wolfram Language (Mathematica), ~~78~~ ~~76~~ ~~57~~ 55 bytes

```
(x=0;While[Max@Abs[2IntegerDigits[2^++x,10,#]-3]>1];x)&

```

Try it online!

`IntegerDigits[a,10,r]` generates a list of the `r` last decimal digits of `a`. Subtract 3/2 and check that they are all either -1/2 or +1/2.

Timing check: 20 seconds on TIO for `r = 1 .. 10`.

# Wolfram Language (Mathematica), ~~102~~ ~~95~~ ~~91~~ 89 bytes

```
k/.FindInstance[Mod[n=0;Nest[#+10^n(2-Mod[#/2^n++,2])&,0,#]-2^k,5^#]==0,k,Integers][[1]]&

```

Try it online!

This solution is much longer but much faster. By taking the path suggested in OEIS A147884 to go via OEIS A053312, as well as using `FindInstance` magic, TIO manages to compute `r = 1 .. 12` in less than a minute.
> 2 votes

# Answer
# Ruby - 118 chars

```
k,f,g,m=1,4,16
i=j=2
m=10**(n=gets.to_i)
((k+=f;j=j*g%m)until j.to_s=~%r{[12]{#{i}}$};i+=1;f*=5;g=g**5%m)until n<i
p k

```
> 1 votes

# Answer
## Haskell, 115 characters

```
import List
main=readLn>>=print. \r->head$findIndices(all(`elem`"12").take r.(++cycle"0").reverse.show)$iterate(*2)1

```
> 1 votes

# Answer
# Python 3, 63 bytes

```
f=lambda i,c=2:f(i,c+1)if{*str(2**c)[-i:]}-{*'12'}else c**(i>1)

```

Try it online!
> 1 votes

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

```
∞.Δo©‹®I.£2X:`P

```

Try it online or verify the first 8 test cases (any more times out).

**Explanation:**

Uses the fact that \\$2^x \> r\\$ for all possible results, to ensure we have enough digits to get the last \\$r\\$ digits of \\$2^x\\$.

```
∞.Δ            # Find the first positive integer x which is truthy (==1) for:
   o           #  Take 2 to the power the integer: 2^x
    ©          #  Store it in variable `®` (without popping)
     ‹         #  Check that it's larger than the (implicit) input: r < 2^x
               #  (1 if truhy; 0 if falsey)
    ®          #  Push variable `®` again: 2^x
     I.£       #  Only leave the last input amount of digits
        2X:    #  Replace all 2s with 1s
           `   #  Push all digits separated to the stack
    P          #  Take the product of all digits on the stack (including the earlier check)
               #  (NOTE: Only 1 is truthy in 05AB1E)

```
> 1 votes

# Answer
### CSharp - 111 chars

```
int a(int r){int x=1;a:x++;foreach(var c in Math.Pow(2,x)%Math.Pow(10,r)+"")if(c!='1'&&c!='2')goto a;return x;}

```
> 0 votes

# Answer
# Perl 5 `-Mbigint -p`, 33 bytes

```
1while($a=2**++$\)!~/[12]{$_}$/}{

```

Try it online!
> 0 votes

# Answer
# Julia ~~133~~ 122 (51) bytes

Inspired by YOU's answer:

```
n->(k=1;f=4;g=big(16);i=j=2;m=10^n;while i<=n;while digits!(fill(0,i),j)⊈1:2;j,k=j*g%m,k+f;end;i,g,f=i+1,g^5%m,f*5end;k)

```

Try it online!

The following is much shorter, but it crashes for r \> 8, like some of the other answers:

```
f(r,x=big(1))=digits!(fill(0,r),x)⊈1:2&&f(r,2x)+1

```

Try it online!
> 0 votes

---
Tags: code-golf, number, number-theory
---