title: Shortest Pangrammatic Window

text:
# Question
Title: Shortest Pangrammatic Window
A pangram is a sentence or excerpt which contains all twenty-six letters of the alphabet, as is demonstrated in this code golf challenge. However, a pangrammatic *window* is a pangram in the form of some segment of text, which may end or begin halfway through a word, found somewhere within a larger work. These naturally occur everywhere, being proper subsets of true pangrams, so just verifying if something contains a pangrammatic window would be boring and also it was previously done.

So, we're interested in finding the smallest one there is in a given piece of text based on its letter length! In the shortest possible code in bytes, of course, to fit the theme.

## Rules and Guidelines

* Receive a string as the input and return the string of the smallest pangrammatic window in the input if there is one. If there is not, return either a Boolean False or an empty string.
* Whether a string is a pangrammatic window or not is case-insensitive and only depends on the 26 letters, not any punctuation or numbers or other odd symbols.
* Similarly, a pangrammatic window's **letter length** is the total number of how many appearances of *letters* occur in it alone, and not simply the number of every character. The returned value must be smallest based on this count. We're linguists, after all, not programmers.
* An output of a pangrammatic window must, however, must be an exact substring of the input, containing the same capitalization and punctuation, etc.
* If there are multiple shortest pangrammatic windows of the same letter length, return any one of them.

## Test Cases

```
'This isn't a pangram.'
==> False

'Everyone knows about that infamous Quick-Brown-Fox (the one who jumped over some lazy ignoramus of a dog so many years ago).'
==> 'Quick-Brown-Fox (the one who jumped over some lazy ig'

'"The five boxing wizards jump quickly." stated Johnny, before beginning to recite the alphabet with a bunch of semicolons in the middle. "ABCDEFGHI;;;;;;;;;;;;;;;JKLMNOPQRSTUVWXYZ!" he shouted to the heavens.'
==> 'ABCDEFGHI;;;;;;;;;;;;;;;JKLMNOPQRSTUVWXYZ'

```

# Answer
> 6 votes
## Pyth, ~~20~~ ~~16~~ 14 bytes

```
hol@GNf!-GrT0.:

```

Explanation:

```
             .: - substrings of input()
      f!-GrT0   - filter to ones which contain the alphabet
 ol@GN          - sort by number of alphabetical chars
h               - ^[0]

      f!-GrT0   - filter(lambda T:V, substrings)
          rT0   -    T.lower()
        -G      -   alphabet-^
       !        -  not ^

 o              - sort(^, lambda N:V)
   @GN          -   filter_presence(alphabet, N)
  l             -  len(^)

```

Try it here!

When there isn't a correct solution, the program exits with an error with no output to stdout.

# Answer
> 3 votes
# Pyth - 22 bytes

\o/ FGITW!

```
h+ol@GrNZf}GS{rTZ.:z)k

```

Test Suite.

# Answer
> 2 votes
# JavaScript (ES6), ~~139~~ ~~138~~ 136 bytes

```
s=>[r=l="",...s].map((_,b,a)=>a.map((c,i)=>i>b&&(t+=c,z=parseInt(c,36))>9&&(v++,n+=!m[z],m[z]=n<26||l&&v>l||(r=t,l=v)),t=m=[],v=n=0))&&r

```

*Saved 2 bytes thanks to @Neil!*

## Indented

```
var solution =

s=>
  [r=l="",...s].map((_,b,a)=> // b = index of start of window to check
    a.map((c,i)=>
      i>b&&(
        t+=c,
        z=parseInt(c,36)
      )>9&&(
        v++,
        n+=!m[z],
        m[z]=
          n<26||
          v>l&&l||(
            r=t,
            l=v
          )
      ),
      t=m=[],
      v=n=0
    )
  )
  &&r
```

```
<textarea cols="70" rows="6" id="input">Everyone knows about that infamous Quick-Brown-Fox (the one who jumped over some lazy ignoramus of a dog so many years ago).</textarea><br /><button onclick="result.textContent=solution(input.value)">Go</button><pre id="result"></pre>
```

# Answer
> 2 votes
# Ruby, 100 bytes

Returns nil if no window is found.

```
->s{r=0..s.size
(r.map{|i|s[i,r.find{|j|(?a..?z).all?{|c|s[i,j]=~/#{c}/i}}||0]}-['']).min_by &:size}

```

# Answer
> 2 votes
## PowerShell v2+, 218 bytes

```
param($a)$z=@{};(0..($b=$a.length-1)|%{($i=$_)..$b|%{-join$a[$i..$_]}})|%{$y=$_;$j=1;65..90|%{$j*=$y.ToUpper().IndexOf([char]$_)+1};if($j){$z[($y-replace'[^A-Za-z]').Length]=$y}}
($z.GetEnumerator()|sort Name)[0].Value

```

Yeah, so substring manipulation (there aren't any built-ins) isn't really PowerShell's strong suit...

We take input `param($a)` and set a new empty hashtable `$z`. This will be our storage of candidate pangrammatic substrings.

Using a slight modification of my code from Exploded Substrings, we construct *all* substrings of the input. Yep, even one-character punctuation-only substrings. This is , not . ;-)

All of those substrings are encapsulated in parens and piped into another loop with `|%{...}`. We temporarily set `$y` to our current substring, set a helper counter `$j`, and start another loop `65..90|%{...}`, conveniently over the ASCII char codes for capital letters. Each inner loop, we take `$y`, make it all uppercase, and pull out the `.IndexOf` that particular char. Since this will return `-1` if not found, we `+1` the result before multiplying it into `$j`. This ensures that if any one character isn't found, `$j` will equal zero.

Which is exactly what the `if` is all about. If `$j` is non-zero, that means that every letter was found at least once in the substring `$y`, so we need to add that to our candidate pool. We do so by taking `$y` and `-replace`ing every non-letter with nothing, which gets us the letter-length of that substring. We use that as the index into hashtable `$z` and store `$y` at that index. This has the quirk of overwriting substrings of the same letter-length with the one that occurs "furthest" in the original string, but that's allowed by the rules, since we're only concerned about letter-length.

Finally, we need to sort through `$z` and pull out the smallest. We have to use the `.GetEnumerator` call in order to sort on the *objects inside* `$z`, then `sort` those on `Name` (i.e., the length index from above), selecting the `[0]`th one (i.e., the shortest), and outputting its `.Value` (i.e., the substring). If no such substring fits, this will toss an error (`Cannot index into a null array`) when it tries to index into `$z`, and output nothing, which is falsey in PowerShell. (the third test case below has an explicit cast as `[bool]` to show this)

### Test Cases

```
PS C:\Tools\Scripts> .\golfing\shortest-pangrammatic-window.ps1 '"The five boxing wizards jump quickly." stated Johnny, before beginning to recite the alphabet with a bunch of semicolons in the middle. "ABCDEFGHI;;;;;;;;;;;;;;;JKLMNOPQRSTUVWXYZ!" he shouted to the heavens.'
ABCDEFGHI;;;;;;;;;;;;;;;JKLMNOPQRSTUVWXYZ!"

PS C:\Tools\Scripts> .\golfing\shortest-pangrammatic-window.ps1 'Everyone knows about that infamous Quick-Brown-Fox (the one who jumped over some lazy ignoramus of a dog so many years ago).'
Quick-Brown-Fox (the one who jumped over some lazy ig

PS C:\Tools\Scripts> [bool](.\golfing\shortest-pangrammatic-window.ps1 "This isn't a pangram.")
Cannot index into a null array.
At C:\Tools\Scripts\golfing\shortest-pangrammatic-window.ps1:2 char:1
+ ($z.GetEnumerator()|sort Name)[0].Value
+ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    + CategoryInfo          : InvalidOperation: (:) [], RuntimeException
    + FullyQualifiedErrorId : NullArray

False

```

# Answer
> 2 votes
# Python 3, ~~171, 167, 163, 157~~, 149 bytes.

Saved 4 bytes thanks to DSM.
Saved 8 bytes thanks to RootTwo.

```
lambda x,r=range:min([x[i:j]for i in r(len(x))for j in r(len(x))if{*map(chr,r(65,91))}<={*x[i:j].upper()}]or' ',key=lambda y:sum(map(str.isalpha,y)))

```

Having to sort based on the number of letters is killing me.

Test cases:

```
assert f("This isn't a pangram.") == ' '
assert f("Everyone knows about that infamous Quick-Brown-Fox (the one who jumped over some lazy ignoramus of a dog so many years ago).") == ' Quick-Brown-Fox (the one who jumped over some lazy ig', f("Everyone knows about that infamous Quick-Brown-Fox (the one who jumped over some lazy ignoramus of a dog so many years ago).")
assert f('"The five boxing wizards jump quickly." stated Johnny, before beginning to recite the alphabet with a bunch of semicolons in the middle. "ABCDEFGHI;;;;;;;;;;;;;;;JKLMNOPQRSTUVWXYZ!" he shouted to the heavens.') == '. "ABCDEFGHI;;;;;;;;;;;;;;;JKLMNOPQRSTUVWXYZ', f('"The five boxing wizards jump quickly." stated Johnny, before beginning to recite the alphabet with a bunch of semicolons in the middle. "ABCDEFGHI;;;;;;;;;;;;;;;JKLMNOPQRSTUVWXYZ!" he shouted to the heavens.')

```

# Answer
> 2 votes
# Haskell, 180 bytes

This was hard, but really fun without imports.

```
l=['a'..'z']
u=['A'..'Z']
f&[]=[];f&x=x:f&f x
g#h=(.g).h.g
f x|v<-[y|y<-(tail&)=<<(init&x),and$zipWith((`elem`y)#(||))l u]=last$[]:[z|z<-v,all((length.filter(`elem`l++u))#(<=)$z)v]

```

Much less golfed:

```
lowerCase = ['a'..'z']
upperCase = ['A'..'Z']

f & x = takeWhile (not . null) $ iterate f x

(#) = flip on

subStrings x = (tail &) =<< (init & x)

pangram p = and $ zipWith ((`elem` p) # (||)) lowerCase upperCase

leqLetters x y = (length . filter (`elem` lowerCase ++ upperCase)) # (<=)

fewestLetters xs = [ x | x <- xs, all (leqLetters x) xs]

safeHead [] = ""
safeHead xs = head xs

f x = safeHead . fewestLetters . filter pangram . subStrings

```

Surprise, surprise: it's really slow.

# Answer
> 2 votes
## Oracle SQL 11.2, 461 bytes

```
WITH s AS (SELECT SUBSTR(:1,LEVEL,1)c,LEVEL p FROM DUAL CONNECT BY LEVEL<=LENGTH(:1)),v(s,f,l)AS(SELECT c,p,p FROM s UNION ALL SELECT s||c,f,p FROM v,s WHERE p=l+1),c AS(SELECT CHR(96+LEVEL)c FROM DUAL CONNECT BY LEVEL<27),a AS(SELECT LISTAGG(c)WITHIN GROUP(ORDER BY 1) a FROM c)SELECT MIN(s)KEEP(DENSE_RANK FIRST ORDER BY LENGTH(s)-NVL(LENGTH(TRANSLATE(LOWER(s),' '||a,' ')),0))FROM(SELECT s,f,SUM(SIGN(INSTR(LOWER(s),c)))x FROM v,c GROUP BY s,f),a WHERE x=26;

```

Un-golfed

```
WITH s AS (SELECT SUBSTR(:1,LEVEL,1)c,LEVEL p FROM DUAL CONNECT BY LEVEL<=LENGTH(:1))
,v(s,f,l) AS
(
  SELECT c,p,p FROM s
  UNION ALL
  SELECT s||c,f,p FROM v,s WHERE p=l+1
)
,c AS(SELECT CHR(96+LEVEL)c FROM DUAL CONNECT BY LEVEL<27)
,a AS(SELECT LISTAGG(c)WITHIN GROUP(ORDER BY 1) a FROM c)
SELECT MIN(s)KEEP(DENSE_RANK FIRST ORDER BY LENGTH(s)-NVL(LENGTH(TRANSLATE(LOWER(s),' '||a,' ')),0))
FROM(SELECT s,f,SUM(SIGN(INSTR(LOWER(s),c)))x FROM v,c GROUP BY s,f),a
WHERE x=26

```

The `s` view splits the input in characters and also returns the position of each character.

The recursive view `v` returns every substring of the input
s is the substring
f the position of the first character of the substring
l the position of the last character added to the current substring

The `c` view returns the alphabet, one letter at a time

The `a` view returns the alphabet concatenated as a single string

`SELECT s,f,SUM(SIGN(INSTR(LOWER(s),c))`
Returns for each substring the number of distinct letters present in it
`INSTR` returns the pos of a letter in the substring, 0 if not present
`SIGN` returns 1 if pos \> 0, 0 if pos = 0

`WHERE x=26`
Filters the substring containing the whole alphabet

`TRANSLATE(LOWER(s),' '||a,' ')`
Deletes every letter from the substring

`LENGTH(s)-NVL(LENGTH(TRANSLATE(LOWER(s),' '||a,' ')`
Length in letters is the length of the substring minus the length of the subtring without letters

`SELECT MIN(s)KEEP(DENSE_RANK FIRST ORDER BY LENGTH(s)-NVL(LENGTH(TRANSLATE(LOWER(s),' '||a,' ')),0))`
Keeps only the substring with the smaller letter count.
If there is more than one, the first one, sorted as strings ascending, is kept

# Answer
> 1 votes
## PowerShell (v4), ~~198~~ 156 bytes

```
param($s)
-join(@(1..($y=$s.Length)|%{$w=$_
0..$y|%{(,@($s[$_..($_+$w)]))}}|?{($_-match'[a-z]'|sort -U).Count-eq26}|sort -Pr {($_-match'[a-z]').count})[0])

# Previous 198 byte golf
$a,$b,$c=@(1..($s="$args").Length|%{$w=$_
0..($s.Length-$w)|%{if((($t=$s[$_..($_+$w)]-match'[a-z]')|sort -u).Count-eq26){(,@($t.Length,$_,$w))}}}|sort -pr{$_[0]})[0]
(-join($s[$b..($b+$c)]),'')[!$a]

```

### Test Cases

```
PS C:\> .\PangramWindow.ps1 "This isn't a pangram."

PS C:\> .\PangramWindow.ps1 'Everyone knows about that infamous Quick-Brown-Fox (the one who jumped over some lazy ignoramus of a dog so many years ago).'
Quick-Brown-Fox (the one who jumped over some lazy ig

PS C:\> .\PangramWindow.ps1 '"The five boxing wizards jump quickly." stated Johnny, before beginning to recite the alphabet with a bunch of semicolons in the middle. "ABCDEFGHI;;;;;;;;;;;;;;;JKLMNOPQRSTUVWXYZ!" he shouted to the heavens.'
ABCDEFGHI;;;;;;;;;;;;;;;JKLMNOPQRSTUVWXYZ!

```

---

### Ungolfed explanation of the original

It's a brute-force nested loop which makes sliding windows of all sizes:

```
.SubString(0, 1) -> slide window over the string
.SubString(0, 2) -> slide window over the string
..
.SubString(0, string.Length) -> slide window over the string

```

For each window, it filters for only letters (case insensitive regex matching by default), runs the remaining characters through a unique filter, checks if there are 26 unique characters as the pangram test.

All windows with pangrams are turned into triplets of *(number of letters including dupes, start index, window length including punctuation)*, which get sorted to find the shortest by overall character count, the first one is picked, and the output string built from that.

There's a lot of indexing outside the bounds of the string, which PowerShell usefully returns $null for, instead of throwing exceptions.

NB. the new 156 byte one is the same approach, but rewritten to use the pipeline a lot more.

```
$string = "$args"

# increasing window widths, outer loop
$allPangramWindows =  foreach ($windowWidth in 1..$string.Length) {

    # sliding windows over string, inner loop
    0..($string.Length - $windowWidth) | ForEach {

        # slice window out of string, returns a char array
        $tmp = $string[$_..($_+$windowWidth)]

        # filter the char array to drop not-letters
        $tmp = $tmp -match '[a-z]'

        # Drop duplicate letters
        $tmpNoDupes = $tmp | sort -Unique

        # If we're left with a 26 character array, this is a pangrammatic window. Output
        # a PowerShell-style tuple of count of letters, start index, width.
        if($tmpNoDupes.Count -eq 26){
            (,@($tmp.Length,$_,$windowWidth))
        }
    }
}

# Force the result into an array (to handle no-results), sort it
# by the first element (num of letters in the window, total)
$allPangramWindows = @( $allPangramWindows | sort -Property {$_[0]} )

# take element 0, a window with the fewest letters
$windowCharCount, $windowStart, $WindowEnd = $allPangramWindows[0]

# uses the results to find the original string with punctuation and whitespace
if ($windowLen) {
    $string[$windowStart..($windowStart + $windowLen)] -join ''
}

```

NB. not sure the ungolfed version works, because I didn't write that then golf it, it's just for exposition.

# Answer
> 1 votes
# Julia, ~~111,110,108~~ 96 bytes

```
!S=minimum(['A':'Z'⊆(r=S[i:j])|>uppercase ? sum(isletter,r) : Inf,r]
for i=(k=keys(S)),j=k)[2]

```

## Attempt This Online!

##

It returns `""` for falsy cases; very ineffective (both for time and for memory); it does not optimize for window size/length - only the letter length is considered

# Answer
> 0 votes
## Haskell, 123 bytes

```
import Data.Lists
import Data.Char
h x=take 1$sortOn((1<$).filter isAlpha)[e|e<-powerslice x,['a'..'z']\\map toLower e==""]

```

Defines a function `h`, which returns the empty list if there's no pangrammatic window or a one element list with the minimum window. Usage example:

```
*Main>  h "'The five boxing wizards jump quickly.' stated Johnny, before beginning to recite the alphabet with a bunch of semicolons in the middle. 'ABCDEFGHI;;;;;;;;;;;;;;;JKLMNOPQRSTUVWXYZ!' he shouted to the heavens."
[". 'ABCDEFGHI;;;;;;;;;;;;;;;JKLMNOPQRSTUVWXYZ"]

```

How it works:

```
          [e|e<-powerslice x                  ]  -- for all continuous subsequences
                                                 -- e of the input
                ,['a'..'z']\\map toLower e==""   -- keep those where the list
                                                 -- difference with all letters is
                                                 -- empty, i.e. every letter appears
                                                 -- at least once
    sortOn((1<$).filter isAlpha)                 -- sort all remaining lists on
                                                 -- their length after removing all
                                                 -- non-letters -> (1<$) see below
take 1                                           -- take the first, i.e. the minimum

calculating the length of a list: we're not interested in the length itself, but
in the relative order of the length. (1<$) replaces each element in a list with
the number 1, e.g. "abc" -> "111", "abcd" -> "1111", etc. Such '1'-strings have
the same order as the length of the original list. One byte saved!

```

# Answer
> 0 votes
# 05AB1E, 13 bytes

```
ŒʒlêAå}éΣág}н

```

Try it online or verify all test cases.

Or alternatively with just a sort-by without filter:

```
ŒéΣláDêAQig]н

```

Try it online or verify all test cases.

Both output an empty string as falsey. (Could have been 12 bytes if we would be allowed to output `-1` as falsey with `ŒéΣág}.ΔlêAå`.)

**Explanation:**

```
Œ       # Get all substrings of the (implicit) input-string
 ʒ      # Filter this list by:
  l     #  Convert the current substring to lowercase
   ê    #  Uniquify and sort all characters in the string
    A   #  Push "abcdefghijklmnopqrstuvwxyz"
     å  #  Check if the lowercase alphabet is in the uniquify-sorted substring
 }é     # After the filter: sort any remaining substrings from shortest to longest
   Σ    # Then sort it again by:
    á   #  Leave just all the letters of the substring
     g  #  Pop and push the length for the amount of letters
   }н   # After the sort-by: pop and leave just the first
        # (or an empty string if the list is empty)
        # (which is output implicitly as result)

```

```
Œ           # Get all substrings of the (implicit) input-string
 é          # Sort them by length (shortest to longest)
  Σ         # Then sort it again by:
   l        #  Convert the current substring to lowercase
    á       #  Leave just all the letters of the substring
     D      #  Duplicate it
      ê     #  Uniquify and sort all characters in the letters in the string
       AQi  #  Pop, and if it's equal to the lowercase alphabet:
          g #   Pop and push the length for the amount of letters
  ]         # Close both the if-statement and sort-by
            # (note, integers are always sorted before strings, even if there are
            # digits in the input-string)
   н        # Pop and leave just the first result
            # (or an empty string if the list is empty)
            # (which is output implicitly as result)

```

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


title: Solve a Card Suit Puzzle

text:
# Question
Title: Solve a Card Suit Puzzle
# Warning: Contains minor Deltarune Chapter 1 Spoilers

Within the Forest section of the first chapter of Deltarune, there are a few puzzles that consist of entering playing-card suits in a certain order to move to the next section. Below is an example of such a puzzle:

>

The way to solve the puzzle is to do any of the following until the input pattern matches the required pattern: a) add a spade, b) add a diamond, c) toggle the suits of the already inputted pattern (spades goes to clubs and vice versa, hearts goes to diamonds and vice versa).

The solution to the puzzle in the picture is:

a) Add a spade

b) Add a diamond

c) Add a spade

d) Toggle suits

>

Here's a video version of the solving of the puzzle

## A Worked Example

Say the required pattern was `diamond, heart, club, spade` (`DHCS`). We first add a heart to the input, as the first item will have to be red in some way:

```
D . . .

```

We then toggle the suits so that we have heart as the first suit.

```
H . . .

```

We then add a diamond to complete the first two suits.

```
H D . .

```

We add then add a spade.

```
H D S .

```

And invert the suits one last time.

```
D H C .

```

Finally, we add the spade and the puzzle is complete.

```
D H C S

```

## Rules

* Input can be taken as a collection (e.g list, string) of any 4 distinct values that represent the 4 suits. E.g. `[4, 3, 2, 1]` where `1 = spades, 2 = clubs, 3 = hearts, 4 = diamonds`.
* It is guaranteed that the input is solvable. You won't need to handle any unsolvable cases.
* There will always be at least one item in the required pattern.
* Output can be given as a collection (e.g list, string) of any 3 distinct values that represent the 3 possible move types. E.g `[2, 3, 2, 1, 3, 1]` where `1 = add spade, 2 = add diamond, 3 = toggle suits`
* There may be multiple solutions of differing length. You can output either one solution or all solutions.
* Toggling twice in a row won't be part of any valid solution.
* Steps in the solution(s) need to be in the right order.

## Test Cases

Assuming `SCHD` for `S`pades, `C`lubs, `H`earts and `D`iamonds for input. Assuming `SDT` for `S`pade, `D`iamond, `T`oggle. Assuming only one solution returned.

```
"CHC" => ["S", "D", "S", "T"]
"DHCS" => ["D", "T", "D", "S", "T", "S"]
"SDC" => ["S", "D", "T", "S", "T"]
"HSD" => ["D", "T", "S", "D"]
"CHS" => ["S", "D", "T", "S"]

```

As this is , the aim of the game is to use as few bytes as possible, as you never know what Lancer and Susie will do next.

# Answer
# Retina 0.8.2, 15 bytes

```
H
TDT
C
TST
TT

```

Try it online! Doesn't output minimal solutions but link is to test suite that removes redundant leading toggles for convenience. Explanation:

```
H
TDT

```

`TDT` inserts an `H` without changing the overall toggle state.

```
C
TST

```

`TST` inserts a `C` without changing the overall toggle state.

```
TT

```

Remove consecutive toggles, as they're not allowed. (Would have saved 4 bytes if they were allowed.)
> 8 votes

# Answer
# Jelly, 11 bytes

```
ṁỊ;1ŒgƊḂKḣ-

```

Try it online!

Works as either a function or a full program. Input format is a list of numbers, 0, 1, 2, 3 for diamonds, spades, hearts, clubs respectively. Output format is a string of `'0'` for diamonds, `'1'` for spades, and a space character `' '` for a toggle. (The TIO link contains a footer which wraps the output in double quotes, so that trailing spaces are visible.)

## Algorithm

### Mathematical algorithm for solving this puzzle

*(i.e. "ais523 has mistaken PPCG for Puzzling")*

This is a closed-form algorithm that produces an optimal solution directly in linear time, using mathematical properties of the puzzle rather than any sort of brute force. The basic observation is that we can split the suits into two groups, the "writable" suits diamonds and spades (which have numbers 0 or 1, i.e. return true from Jelly's  builtin), and the "unwritable" suits clubs and hearts (which have numbers 2 and 3, i.e. return false from Jelly's  builtin). For any two positions in the string (either the string we're trying to create or the string we're working on), it's possible to define a "writability difference" – 'same' if the two positions contain suits with the same writability, or 'different' if the two positions contain suits with different writabilities.

None of our three basic operaions change the writability difference between any two positions that already contain a card: a toggle will affect all writabilities equally and thus will not cause them to become different or cease to be different, and addition of a card won't change positions where we've already added a card. This means that whenever a card is added, it must be added in such a way that the position we're adding it to already has the correct writability difference with the other existing positions (i.e. the same writability difference as it does in the string we're aiming for), and that status will not subsequently change during the solution.

This leads to a really simple rule for determining where to put the toggle actions: performing two addition actions in a row will add two writable suits, thus the writability difference between the added suits' positions will be 'same', and placing a toggle between two addition actions will add a writable suit after an unwritable suit and thus create a writability difference of 'different'. Therefore, in any valid solution that does not contain double-toggles, toggles prior to the final card being added must appear in those, and only those, positions where the two immediately adjacent suits have a writability difference of 'different'. (After the final card, clearly a toggle is required if the final card is unwritable, but not if the final card is writable as the string will already be correct in that case.)

That immediately forces the position of every toggle action. The add-card actions are also obviously forced: a toggle action can't change a card between red and black, so to add a red card (represented with an even number), it's required to add a diamond, and to add a black card (represented with an odd number), it's required to add a spade.

Assuming that there's at least one solution, this gives a description of how to find it (and incidentally also proves that there's at most one solution that doesn't involve a double-toggle or a useless toggle at the start). In fact, there is always exactly one solution that doesn't involve a double-toggle or useless leading toggle; the above argument doesn't prove this directly but can be extended to do so.

### Expressing this algorithm in Jelly

The core of the algorithm can be expressed in Jelly by looking at the list of writabilities (), and grouping it into blocks of consecutive equal writabilities (`Œg`).  is then used to copy the shapes of the blocks onto the original list, which is reduced to a list of red (0) / black (1) using . The resulting list can then be joined on anything other than 0 or 1 in order to add the toggles (as a toggle needs to be put anywhere there's a writability difference of 'different', i.e. the writability changes, and that happens at the gaps between the blocks); joining on spaces (`K`) is tersest as that has a single-character builtin (even though it makes the output a little hard to read, that isn't a requirement of the question).

This doesn't, however, handle the requirement to add an extra "toggle" at the end if the last suit is unwritable. The tersest way I've found to implement this requirement is to append a 1 to the list of writabilities (`;1`), which (due to how  works) effectively adds "a copy of the first suit but writable" to the end of the list of suits we're creating, and then remove it the added suit again at the end of the program (`h-`). This is a no-op if the last suit in the desired output is writable. If, however, the last suit in the desired output is unwritable, this creates a writability difference of 'different' which will lead to an extra toggle instruction being added between the last requested suit and the added suit; and when the added suit is deleted, the toggle instruction won't be. Both cases therefore end up with the desired result, with no explicit `if` statement needed.

## Explanation

```
ṁỊ;1ŒgƊḂKḣ-
      Ɗ      like parentheses, surrounding the previous three builtins
 Ị           {for each suit}, 1 if the suit is 0 or 1, 0 if it's larger
  ;1         append 1
    Œg       group consecutive equal elements into sublists
ṁ            unflatten {the input}, using the same sublists in the same places
       Ḃ     {for each suit}, 1 if the suit is odd, 0 if it's even
        K    join on spaces
         ḣ-  delete the last element

```
> 5 votes

# Answer
# Python, 75 bytes

```
f=lambda p,t=0:p and((v:=p[-1]-t)%2and v+10*f(p[:-1],t)or 5+10*f(p,~t))or 0

```

Attempt This Online!

The input is a list of integers, and the output is an integer where each digit read left to right represents a possible move.
For input: clubs, spades, hearts, and diamonds are 0, 1, 2 and 3 respectively.
For output moves: spades, diamonds, and toggle are 1, 3 and 5 respectively.

---

If a number is not a valid output format, then the answer is 76 bytes:

```
f=lambda p,t=0:p and((v:=p[-1]-t)%2and f(p[:-1],t)+str(v)or f(p,~t)+"5")or""

```

Attempt This Online!

---

## How it works

Here's the unminimized code:
```
def f(p,t=0):
  if p:
    if (v:=p[-1]-t)%2:# true if (t=0 & p=1,3) or (t=-1 & p=0,2)
      return f(p[:-1],t)*10+v
    else:
      return f(p,~t)*10+5 # 5 is arbitrarily chosen
  else:
    return 0

```

It's a recursive function that works from the end of the list to the beginning. `t` is a toggle flag -- it's `-1` when the output will become either a heart or a club, and `0` when the output will be either a spade or a diamond. We append toggles until the end value and toggle bit have *different* odd-ness/even-ness, then append the associated move (spade if end value is spade/club, diamond if it's diamond/heart).

---

-1 byte from @math junkie
> 4 votes

# Answer
# Charcoal, 20 bytes

```
⁻⪫⪪⪫⪪ＳH¦TDT¦C¦TST¦TT

```

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

```
     Ｓ                  Input string
    ⪪ H                 Split on `H`
   ⪫    TDT             Join with `TDT`
  ⪪         C           Split on `C`
 ⪫            TST       Join with `TST`
⁻                 TT    Remove all `TT` substrings
                        Implicitly print

```
> 4 votes

# Answer
# Rust, ~~149~~ 126 bytes

```
|t:&[u8]|t.iter().rev().scan(false,|b,&k|Some(if(k<2)^*b{vec![k&5]}else{*b=!*b;vec![k&5,2]})).fold(vec![],|a,b|[b,a].concat())

```

Verify All Test Cases
> 3 votes

# Answer
# JavaScript (Node.js), ~~70~~ 64 bytes

*-6 thanks to Arnauld*

```
f=(x,y=x.pop())=>y%2?[...f(x),y]:++y?[...f(x.map(z=>z^1)),y,4]:x

```

---

A recursive solution, which I believe also finds the optimal solution. Uses `0` through `3` for clubs, spades, hearts, and diamonds, and uses `4` for toggle, and `1` and `3` to add the respective cards.

Try it online!
> 2 votes

# Answer
# 05AB1E, ~~18~~ ~~16~~ 11 (or 4) bytes

```
4ƵK:5ƵU:11K

```

-5 bytes porting *@Neil*'s Retina answer, with integers as I/O

Inputs `2345` for `DSHC` respectively; outputs `123` for `TDS` respectively.

Try it online or verify all test cases.

**Or 4 bytes with *@Neil*'s convenient input-format**: inputs as a list with `0 1 202 212` for `S D C H` respectively; outputs a string with `0 1 2` for `DST` respectively.

```
J22K

```

Try it online or verify all test cases.

**Original ~~18~~ 16 bytes approach:**

```
₂…)˜(ªÞæ.Δ».V)˜Q

```

Inputs `-6 -2 2 6` for `C H D S` respectively; outputs `2 6 )˜(` for `D S T` respectively.

Try it online or verify all test cases.

**Explanation:**

```
   :              # Replace
4                 # all 4
 ƵK               # with 121
       :          # Then replace
    5             # all 5
     ƵU           # with 131
          K       # Then remove
        11        # all 11
                  # (after which the result is output implicitly)

```

See this 05AB1E tip of mine (section *How to compress large integers?*) to understand why `ƵK` is `121` and `ƵU` is `131`.

```
₂                 # Push 26
 …)˜(             # Push string ")˜("
     ª            # Convert the 26 to [2,6], and append the string: ["2","6",")˜("]
      Þ           # Cycle it indefinitely: ["2","6",")˜(","2","6",")˜(","2",...]
       æ          # Get the powerset of this infinite list
        .Δ        # Find the first result which is truthy for:
          »       #  Join the list with newline delimiter to a single string
           .V     #  Evaluate and execute it as 05AB1E code:
                  #   `2`: Push a 2
                  #   `6`: Push a 6
                  #   `)˜(`: Wrap stack into a list; flatten; negate each
             )˜   #  Wrap the stack into a list and flatten
               Q  #  Check if it's equal to the (implicit) input-list
                  # (after which the found result is output implicitly)

```
> 2 votes

# Answer
# Vyxal, 10 bytes

```
vṅ1JĠ•∷ṅṄṪ

```

Try it Online!

Port of Jelly, so go upvote that.
> 2 votes

---
Tags: code-golf
---


title: Implement Binary Exponentiation

text:
# Question
Title: Implement Binary Exponentiation
# Background

In programming, there is a recursive algorithm called binary exponentiation, which allows for large integer powers to be calculated in a faster way. Given a non-zero base \\$x\\$ and a non-negative exponent \\$n\\$, the algorithm goes something like this (based on the example code from Wikipedia):

```
Function exp_by_squaring(x, n)
    if n = 0  then return  1;
    else if n is even  then return exp_by_squaring(x * x,  n / 2);
    else if n is odd  then return x * exp_by_squaring(x * x, (n - 1) / 2);

```

Basically, the code "reduces" the exponent term by first checking whether the current exponent is odd or even, then if it is even, just square root it; otherwise, divide by the base then square root it. Then repeat until the exponent reaches \\$0\\$. If the exponent is initially \\$0\\$, then just return \\$1\\$ directly.

This allows for an exponent term to be calculated faster than just multiplying the base by itself one at a time.

# Example

Here is an example of the algorithm being applied on \\$x=3,n=21\\$.

1. \\$n=21\\$ is odd and non-zero, so we divide by the base, then square root. In this case, the number reduces to \\$\sqrt{\frac{3^{21}}3}=3^{10}\\$.
2. \\$n=10\\$ is even and non-zero, so we simply take the square root. \\$\sqrt{3^{10}}=3^5\\$.
3. \\$n=5\\$ is odd and non-zero, so we divide by the base, then square root. \\$\sqrt{\frac{3^5}3}=3^2\\$.
4. Continuing the process, we get \\$3^1\\$ then \\$3^0\\$, after which the recursion stops.

# Task

Notice how at each step in the example above, we have a value which resulted from reducing the original number. Your task is to return a list of these numbers, given a non-zero integer base \\$x\ne-1\\$ and a non-negative integer exponent \\$n\\$. The list should always contain the initial value as the first element. The list can be returned in reverse order if you want to.

# Test Cases

```
   x, n     -> Output
   3, 21    -> [10460353203, 59049, 243, 9, 3, 1]
1000, 0     -> [1]
   2, 15    -> [32768, 128, 8, 2, 1]
   1, 40000 -> [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
  21, 3     -> [9261, 21, 1]
   2, 30    -> [1073741824, 32768, 128, 8, 2, 1]

```

---

This is , so shortest code in bytes wins!

# Answer
> 9 votes
# Vyxal, 5 bytes

```
‡½⌊↔e

```

Try it Online!

Takes inputs in reverse order.

# Jelly, 6 bytes

```
HḞ$Ƭ*@

```

Try it online!

Takes inputs in reverse order.

## Explanation

```
HḞ$Ƭ*@  Dyadic link f(n, x)
   Ƭ    Repeatedly apply on n until the results are no longer unique
  $     Last two links as a monad:
H        Halve
 Ḟ       Floor
    *@  x to the power of each

```

# Answer
> 4 votes
# Jelly, 5 bytes

```
:Ƭ2*@

```

Try it online!

Takes `n` on the left, and `x` on the right. Based on Steffan's answer, so be sure to give them an upvote as well.

## How it works

```
:Ƭ2*@ - Main link. Takes n on the left and x on the right
 Ƭ    - Repeatedly apply until a duplicate value is found:
: 2   -   Floor divide n by 2
   *@ - Raise x to each power

```

# Answer
> 3 votes
# PARI/GP, 34 bytes

```
f(x,n)=[x^m\=2|i<-binary(m=2*n+1)]
```

Attempt This Online!

---

# PARI/GP, 29 bytes

```
f(a,n)=if(n,f(a,n\2)*x+a^n,1)
```

Attempt This Online!

This returns a polynomial whose coefficients are the results.

# Answer
> 3 votes
# 05AB1E, 7 bytes

```
bη0šÙCm

```

Try it online!

```
b    convert the exponent to binary
η    takes all prefixes
0š   append the prefix "0", to include 1 in the list
Ù    uniquify, since if the exponent was 0 then "0" was already a prefix
C    convert each prefix from binary to a number
m    exponentiation

```

# 05AB1E, 7 bytes

```
·.Γ;ï}m

```

Try it online!

A port of the Vyxal and Jelly answer

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

```
x=>g=n=>[x**n,...n?g(n>>1):[]]

```

Try it online!

# Answer
> 3 votes
# C (GCC), ~~66~~ 53 bytes

*-13 bytes thanks to @att*

```
r;f(x,n){printf("%d ",r=n?f(x,n/2),(n%2?x:1)*r*r:1);}
```

Attempt This Online!

# Answer
> 2 votes
# Desmos, 42 bytes

```
f(x,n)=x^{floor(n/2^{[0...ceil(log_2n)]})}

```

Try it on Desmos!

# Answer
> 2 votes
# Python 2, 37 bytes (-1 @Steffan, -2 @dingledooper)

```
f=lambda x,n:[1][n:]or[x**n]+f(x,n/2)
```

Attempt This Online!

### Old Python, 40 bytes

```
f=lambda x,n:[x**n]+(n*[n]and f(x,n//2))
```

Attempt This Online!

Doesn't actually implement the algorithm. But produces correct output.

# Answer
> 2 votes
# Java, 59 bytes

```
x->n->{for(n*=2;n>0;)System.out.println(Math.pow(x,n/=2));}

```

Try it online!

# Answer
> 2 votes
# BQN, 16 bytes

```
⊣⋆{×?∾⌊÷2;0}

```

Try it at BQN REPL

```
  {          }    # Recursive function acting on right argument  :
     ?            # if
   ×             # sign of  is non-zero
      ∾          # join  to
                 # the result(s) of a recursive call to this function
                  # with argument:
         ⌊        # floor of
          ÷2     #  divided by 2.
                  # Now, get
⊣                 # the left argument
 ⋆                # raised to these powers

```

# Answer
> 2 votes
# Prolog (SWI), 45 bytes

```
_*0*[1].
X*N*[P|R]:-P is X^N,T is N//2,X*T*R.

```

Try it online!

# Answer
> 2 votes
# x86-64 machine code, 24 bytes

Or 1 less for 32-bit mode, with 1-byte `dec ecx`. If anyone has any other ideas for golfing further, please comment; I expect there's room for improvement. A straightforward binary exponentiation that doesn't have to produce the exact same proof-of-"work" array output is only 19 bytes.

### Actually implements a binary-exponentiation algorithm, not doing a separate `pow` for every output element. Only one or two other answers do this, and I think this is the only iterative (non-recursive) one of those.

This is a function that takes an output pointer in RDI, to an array of DWORDs. `x` in ESI, `n` in EBX. (EDX is clobbered by `mul`. This can be signed if you want; `mul` and `imul` are the same binary operation *on EAX*, differing only in the EDX high half. They're the same size.)

Outputs: Array of steps in the memory the caller passed, RDI points to one-past-end. EAX = `x**n`.

trimmed NASM listing: address, machine-code (the answer), source

```
                   expint: ; uint32_t *out (rdi),  x = esi   n = ebx
 00 6A01               push 1
 02 58                 pop  rax        ;    mov eax,1
 03 AB                 stosd           ;  *rdi++ = eax
 04 0FBDCB             bsr  ecx, ebx   ; bit-scan-reverse.  we need to loop bits high to low; a set bit cares about (gets squared by) how many bits are *below* it, not above.
                                ; ECX = bit-index of highest set bit
 07 740E               jz   .n0        ; exponent=0 is a special case
                   .loop:
 09 F7E0               mul  eax     ; square total
 0B 0FB3CB             btr  ebx, ecx          ; bit-test-reset.  Or just BT, clearing n as we go wasn't helpful.
 0E 7302               jnc .was_even
 10 F7E6                mul  esi     ; total *= x;   (destroys EDX with the high-half result, but this saves a byte vs. imul eax, esi)
                   .was_even:
 12 AB                 stosd
 13 FFC9               dec  ecx
 15 7DF2               jge .loop     ; }while(--bitpos >= 0);  // loop runs for ECX=0, can't use LOOP unless we left-shifted EBX or something
                   .n0:
 17 C3                 ret

size: 0x18 = 24 bytes

```

It feels like there should be room to golf more, but it's tricky to cover the corner cases (like `n==0` is costing 2 bytes) and the off-by-ones (e.g. having to run the loop body for ECX=0 means I can't use `loop`).

Starting with `1` isn't as much of a burden as I'd thought it might be, mostly just requiring an extra `stosd` to output before the first multiply and after the last. We need to start with the MSB, not LSB, so we always have a `1` bit so the first iteration can do `1*1 * x` to get us started with total=x. That does let us fall into the loop with `total=1` after all. If not for having to store the `n`, though, I'd likely start with EAX=`x` and adjust the loop somehow.

(The test-case I asked for with a non-trivial even power turned out not to be relevant for this; I hadn't realized you needed to start from the high end for an iterative version. But it makes sense if you think about it: a `1` in the lowest bit of `n` results in a `*x` at the end. But if you do that at the *start*, a bunch of squaring happens so that odd power becomes an even power. If you just `shr ebx, 1` / `jnc` to divide by 2 and check for odd/even, you'd effectively be bit-reversing the exponent, or something like that. Which works for exponents like `15` that have no significant zeros, but not others.)

**Update: you don't have to start from the MSB, I just had a brain fart**: the normal algorithm would do `x *= x;` every iteration, only multiplying it into the total for set bits in `n`. The algorithm is identical to multiplication by shifting-and-adding, in case it helps to think about how adding partial products works. (Stepanov's lectures on algorithms uses binary exponentiation as one of the main examples, pointing out that replacing `+` with `*` makes exponentiation instead of multiplication.) This question's presentation in terms of square-rooting the total in reverse got me stuck on squaring the total instead of x, and if you do that then you have to go from MSB downward.

No CPU I'm aware of has an integer sqrt instruction, or a single-instruction `pow` to give a starting point. (x87 has some exponential stuff, but takes multiple instructions to do pow. Still maybe worth considering.

Hopefully we can still recover all the same intermediate values this question wants, while doing `shr ecx,1` / `jnc`. But that would make starting with `1` inconvenient.

---

BMI2 `mulx` is a 5-byte instruction, so even if we could reuse FLAGS to save a dec or test, it wouldn't pay for itself.

Try it online! with `_start` test caller (doesn't print: use GDB `display *(int[8]*)($rsp+8)` to display the output array state as you single-step, given that the caller passes RDI=RSP as the output.)

### 19 bytes, different array from a more normal algorithm:

```
expint_v2: ; uint32_t *out (rdi),  x = esi   n = ebx
    push 1
    pop  rax      ; mov eax,1
    stosd
.loop:              ;do{
    shr  ebx, 1  ; n /= 2,  CF = old low bit
    jnc .was_even
    mul  esi          ; total *= x;   (destroys EDX with the high-half result, but this saves a byte vs. imul eax, esi)
.was_even:
    stosd             ; *out++ = eax
    imul esi, esi     ; square x
    test ebx, ebx
    jnz  .loop      ;}while(n!=0);
    ret

```

Same inputs as before, same result in EAX and the highest array element (since the last bit shifted out before it becomes zero is a `1`, unless `n=0` in which case we leave the loop without having done `mul esi`.)

e.g. for 3^21 it produces these steps, where `1870418611` is 3^21 mod 2^32.

```
{1, 3, 3, 243, 243, 1870418611}

```

The `x*=x` steps where `n` doesn't have a set bit don't change the running product. (Like for multiply by addition, where you're not adding a partial product at that shift.)

I don't think it's possible to recover the same proof-of-work temporaries from this (even with a `mov`/`imul` into another temp), because we're working from the low bit up, not from the high bit down.

Starting with `1` is actually helpful, since we actually need to *not* start with `total = x` if `n` is even, but after we square x this iteration we no longer have any odd power of the original `x` left to multiply by, so the total would remain an odd power.

Starting with `total=1` also makes the n=0 case Just Work for free.

Anyway, this order of temporaries is perhaps less interesting, but could probably also be recovered from a recursive implementation. I'm curious whether another challenge, perhaps titled iterative binary exponentiation, would get different answers in other languages. Probably still easier to use `**` or `^` built-ins in languages that have them, after generating the right array of what, prefix-sum of bit-indices of non-zero bits or something?

# Answer
> 1 votes
# Charcoal, 18 bytes

```
ＩＸθＥ⊕Ｌ↨η²↨²✂↨η²¦⁰ι

```

Try it online! Link is to verbose version of code. Outputs the list in ascending order (+1 byte to output in the order given in the question). Explanation:

```
  θ                 First input `x`
 Ｘ                  Vectorised raised to power
       η            Second input `n`
      ↨ ²           Converted to base 2
     Ｌ              Take the length
    ⊕               Incremented
   Ｅ                Map over implicit range
             η      Second input `n`
            ↨ ²     Converted to base 2
           ✂    ⁰   Sliced to length
                 ι  Current value
         ↨²         Converted from base 2
Ｉ                   Cast to string
                    Implicitly print

```

Although Charcoal's `BaseString()` function would convert `0` to `"0"`, its `Base()` function returns an array rather than a string, and this array is empty when `n=0`, so it doesn't have the problem that, say, the 05AB1E answer has. Instead, it has the problem that `CycleChop([], 0)` throws a `ZeroDivisionError`, so I have to use `Slice()` instead.

# Answer
> 1 votes
# Retina, 69 bytes

```
^
1,
\d+$
*
+`(.+),(.+),\b(_*)\3(_?)
$1¶$.($($.4*$2,1)***),$2,$3
,.+

```

Try it online! Link includes test cases. Outputs the list in ascending order. Explanation:

```
^
1,

```

Prefix a `1` which is the working value for the result.

```
\d+$
*

```

Convert `n` to unary.

```
(.+),(.+),\b(_*)\3(_?)

```

Match the previous result, `x`, `n/2` and `n%2`.

```
$1¶$.($($.4*$2,1)***),$2,$3

```

Keep a copy of the previous result, then square it and multiply it by `x` or `1` depending on whether `n` was odd. (Retina only uses the first integer it finds in a string, so multiplying `3,1`, `59049,3,_` and `59049,3,_` is equivalent to multiplying `3`, `59049` and `59049`.) Append `x` and `n/2` for the next pass through the loop.

```
+`

```

Repeat the above until `n=0`.

```
,.+

```

Delete `x`.

Retina doesn't have exponentiation. Retina 1 does however have both eval and multiplication, so exponentiation can be (slowly) performed in 30 bytes:

```
~`(.+),(.+)
.+¶$$.($2*$($1$*)_

```

Try it online! Link includes examples.

# Answer
> 1 votes
# Husk, 6 bytes

```
M^U¡÷2

```

Try it online!

Another port of Steffan's answers: upvote those.

```
   ¡      # Apply function repeatedly, collect values in infinite list:
          #  (using arg1 as starting value)
    ÷2    #  Integer-divide by 2
  U       # Longest prefix with all unique elements
M         # Map over this:
 ^        #  arg2 to the power of this

```

# Answer
> 1 votes
# APL (Dyalog Unicode), 20 bytes SBCS

```
{⍵=0:1⋄(⍺*⍵),⍺∇⌊⍵÷2}

```

Try it on APLgolf!

-2 bytes thanks to Vadim Tukaev

---
Tags: code-golf, math, number, arithmetic, binary
---


# Question
Title: Write a program with infinite expected output
Write a program that halts producing a random finite numerical output with probability 1. The expected value of the outputs of the program must be infinite.

For physical limits, you can assume your language and related functions use infinite precision numbers. E.g. for languages with random function providing range \\$\[0,1)\\$, it returns a real in \\$\[0,1)\\$. (Anyway I need to choose from `1/rnd` and `while(rnd)print(1)`)

Inspired by St. Petersburg paradox.

Shortest code wins. Would be quite small for lots of language though.

---

There are two easy-seen ways to do this, both are accepted given the question: (in Javascript)

```
_=>1/Math.random() // ∫₀¹1/xdx=∞
_=>{c='1';while(Math.random()<.5)c+='1';return c} // Not golfed to easier get understood for other language user, at least I try to
    // 1/2+11/4+111/8+1111/16+...=∞

```

# Answer
# , 9 bytes

```
rf(1,1,1)

```

Try it online!

Outputs a realization of the \\$F(1,1)\\$ distribution. The \\$F(d\_1,d\_2)\\$-distribution has infinite mean for \\$d\_2 \leq 2\\$.

One way of defining the \\$F(1,1)\\$ distribution is as follows: let \\$X\_1,X\_2\\$ be independent \\$\mathcal N(0,1)\\$ random variables. Then \\$\frac{X\_1^2}{X\_2^2}\sim F(1,1)\\$.

Using the \\$F\\$ distribution comes out 1 byte shorter than the 2 more obvious solutions `1/runif(1)` and `rcauchy(1)`.

The plot below shows the evolution of the sample mean, for sample size ranging from 1 to 1e6; you can see that it diverges.

---

Alternate solution for the same byte count:

```
rt(1,1)^2

```

which outputs the square of a realization of Student's distribution \\$t(1)\\$. It has infinite expected value, since the \\$t(1)\\$ distribution has infinite variance. The square is needed to guarantee that the output is positive; without it, the expected value is undefined, since the realizations are often enough arbitrarily large positive or negative numbers.
> 8 votes

# Answer
# Jelly, 6 bytes

```
1ḤXḂ$¿

```

Try it online!

-1 byte thanks to Jonathan Allan

50% chance to output 1, 50% chance to output double this value. -2 bytes using a while loop inspired by Aaron Miller's answer.

## Explanation

```
1
     ¿  While
  ..$
  X     Random integer from 1 to (current value)
   Ḃ    % 2 (this ensures 50% chance no matter how large the current value is - except if it's 1)
 Ḥ      Double the current value

```

Unfortunately, Jelly doesn't have a "random decimal from 0 to 1" built-in, otherwise this could be `<random><reciprocal>`.

## Proof of validity

The probability to output \\$2^x\\$ is \\$2^{-x-1}\\$ for all \\$x\in\mathbb{Z}^+\\$. Therefore, the expected output is \\$\sum\limits\_{n=0}^\infty 2^n\cdot 2^{-n-1}=\sum\limits\_{n=0}^\infty\frac12\rightarrow\infty\\$
> 7 votes

# Answer
# Retina, 5 bytes

```
?+`
1

```

Try it online! Explanation:

```
?+`

```

Loop a random number of times with an exponential distribution...

```

1

```

Double the length. (Actually you get `2ⁿ-1`, but that's still enough to diverge to infinity.)
> 6 votes

# Answer
# Python 3, 37 bytes

```
from random import*
print(1/random())

```

Try it online!

I had a slightly cool solution but now this is just the trivial solution.
> 4 votes

# Answer
# Vyxal, ~~6~~ ~~7~~ 3 bytes

*Thanks to @hyper-neutrino for helping me to understand what expected output is.*

*Thanks to @Lyxal for porting a different answer than I did for -4 bytes.*

```
∆ṘĖ

```

Try it Online!

Explanation:

```
∆Ṙ   # Random float in range [0.0, 1.0)
  Ė  # Reciprocal
     # Implicit output

```
> 4 votes

# Answer
# Thue, 29 bytes

*Edit: +9 bytes to fix issue spotted by @RossMillikan.*

```
1::=.10
10::=~1
.0::=~0
::=
1

```

Try it online! *The TIO interpreter requires a trailing newline, and outputs each digit on a different line, which is not required. Here is an interpreter without these restrictions.*

Outputs in binary (meta link). Each step has a 50% chance to double the binary integer, or to start outputting it. The proven formula from other answers.
> 4 votes

# Answer
# C++ (gcc), ~~169~~ ~~119~~ 118 bytes

```
#include<bits/stdc++.h>
int main(){std::mt19937 p((uint64_t)new int);std::string s="1";while(p()%2)s+=s;std::cout<<s;}

```

Try it online!

This solution is directly derived from the linked paradox in the question. The output string is composed of `1` digits so technically it can be interpreted as a number.

The random number generator is seeded with the address of a heap variable. The address changes each time the program is run.

> Another option is to use the address of a newly allocated heap variable: `mt19937 rng((uint64_t) new char);` (source)
> 1 votes

# Answer
# Pyth, 4 bytes

```
/1OZ

```

Try it online!

```
/1   # 1 divided by
OZ   # Random float between 0 and 1

```
> 1 votes

# Answer
# Bash, 24 bytes

```
echo 32767/$RANDOM|bc -l

```

Try it online!

Prints a random number between \\$1\\$ and \\$\infty\\$.
> 1 votes

# Answer
# Charcoal, 7 bytes

```
1Ｗ‽²↑ＫＡ

```

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

```
1

```

Print `1`.

```
Ｗ‽²

```

Repeat a random number of times with an exponential distribution...

```
↑ＫＡ

```

... duplicate the output.
> 1 votes

# Answer
# , 9 bytes

```
1/rexp(1)

```

Try it online!

`rexp(1)` \- a single random sample from an exponential distribution with a (default) rate parameter of 1 - is the shortest  random function call with a nonzero probability density at zero (there are other shorter random functions \[`rt` and `rf`\], but unfortunately they each lack default values for required parameters, so the function calls are no shorter\*).

\*Edit: no shorter, but both can be made just-as-short: see Robin Ryder's answer
> 1 votes

# Answer
# MATL, 3 bytes

```
1r/

```

Try it online!

This produces the output 1/*x*, where *x* is uniformly distributed on the interval (0,1). This has infinite mean.
> 1 votes

# Answer
# Python 3, 31 bytes

```
from time import*
print(time())

```

Try it online!

The Python 3 `random` library uses the current time for a seed. Therefore, it is necessary to specify the random distribution of time that the program is run, to ensure that the simple `1/random()` is valid. Depending on the yet-to-come specification, my answer may or may not be valid.
> 1 votes

# Answer
# Befunge-93, ~~8~~ 7 bytes

```
2?.#*@#

```

Try it online!

This is basically just the St. Petersburg paradox. Every time the pointer reaches the `?` and goes either left or right, it has a 1/2 chance of doubling the top of the stack and a 1/2 chance of just outputting the top of the stack and halting.

Explanation of the code:

```
2?.#*@#

2        Push 2 onto the stack.
 ?       Change the direction of the pointer to a random direction:
2   *      If left, double the top of the stack.
  .  @     If right, output the top of the stack and halt.
 ?         If up/down, the pointer returns to the ?.

```
> 1 votes

# Answer
# APL, 5 bytes

```
÷1-?0

```

The program generates a random number from the range \[0; 1), then substracts it from 1 to get the range (0; 1\], and takes the reciprocal, so we get a number from the range \[1; +∞).
> 1 votes

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

```
1nx

```

Try it online!

Has an infinite expected value, due to diverging more quickly than exponentially more unlikely repunits. Will nevertheless always terminate when it empties its own stack, when the random trampoline takes more left turns than right turns.
> 0 votes

# Answer
# Random Brainfuck, 5 bytes

```
+[?.]

```

Throw a D256 until you throw a 0

Try it online!
> 0 votes

---
Tags: code-golf, random
---


title: Fibonacci polynomials

text:
# Question
Title: Fibonacci polynomials
The **Fibonacci polynomials** are a polynomial sequence defined as:

* \\$F\_0(x) = 0\\$
* \\$F\_1(x) = 1\\$
* \\$F\_n(x) = x F\_{n-1}(x) + F\_{n-2}(x)\\$

The first few Fibonacci polynomials are:

* \\$F\_0(x) = 0\\$
* \\$F\_1(x) = 1\\$
* \\$F\_2(x) = x\\$
* \\$F\_3(x) = x^2 + 1\\$
* \\$F\_4(x) = x^3 + 2x\\$
* \\$F\_5(x) = x^4 + 3x^2 + 1\\$

When you evaluate the Fibonacci polynomials for \\$x=1\\$, you get the Fibonacci numbers.

## Task

Your task is to calculate the Fibonacci polynomial \\$F\_n(x)\\$.

The usual rules apply. So you may:

* Output all the Fibonacci polynomials.
* Take an input \\$n\\$ and output the \\$n\\$-th Fibonacci polynomial.
* Take an input \\$n\\$ and output the first \\$n\\$ Fibonacci polynomial.

You may use \\$0\\$-indexing or \\$1\\$-indexing.

You may output the polynomials in any reasonable format. Here are some example formats:

* a list of coefficients, in descending order, e.g. \\$x^9+8x^7+21x^5+20x^3+5x\\$ is represented as `[1,0,8,0,21,0,20,0,5,0]`;
* a list of coefficients, in ascending order, e.g. \\$x^9+8x^7+21x^5+20x^3+5x\\$ is represented as `[0,5,0,20,0,21,0,8,0,1]`;
* a function that takes an input \\$n\\$ and gives the coefficient of \\$x^n\\$;
* a built-in polynomial object.

You may pad the coefficient lists with \\$0\\$s. For example, the polynomial \\$0\\$ can represented as `[]`, `[0]` or even `[0,0]`.

You may also take two integers \\$n, k\\$, and output the coefficient of \\$x^k\\$ in \\$n\\$-th Fibonacci polynomial. You may assume that \\$k\<n\\$.

This is , so the shortest code in bytes wins.

## Testcases

Here I output lists of coefficients in descending order.

```
0 -> []
1 -> [1]
2 -> [1, 0]
3 -> [1, 0, 1]
4 -> [1, 0, 2, 0]
5 -> [1, 0, 3, 0, 1]
6 -> [1, 0, 4, 0, 3, 0]
7 -> [1, 0, 5, 0, 6, 0, 1]
8 -> [1, 0, 6, 0, 10, 0, 4, 0]
9 -> [1, 0, 7, 0, 15, 0, 10, 0, 1]
10 -> [1, 0, 8, 0, 21, 0, 20, 0, 5, 0]
11 -> [1, 0, 9, 0, 28, 0, 35, 0, 15, 0, 1]
12 -> [1, 0, 10, 0, 36, 0, 56, 0, 35, 0, 6, 0]
13 -> [1, 0, 11, 0, 45, 0, 84, 0, 70, 0, 21, 0, 1]
14 -> [1, 0, 12, 0, 55, 0, 120, 0, 126, 0, 56, 0, 7, 0]
15 -> [1, 0, 13, 0, 66, 0, 165, 0, 210, 0, 126, 0, 28, 0, 1]

```

# Answer
> 10 votes
# , ~~13~~ 11 bytes

```
$1j1#]!&i.-
```

Attempt This Online!

-2 bytes thanks to @ovs

Looking at the nonzero columns, some keen eyes may have noticed that the columns look like binomial coefficients. And it actually is. (A related fact: summing the coefficients of nth polynomial gives nth Fibonacci number, which you can prove nicely in Lean)

...though we also need to handle the zero columns.

```
$1j1#]!&i.-    A train that takes n, and gives a vector of descending coeffs
     ]    -    n and -n respectively
       &i.     Apply range to both sides; 0..n-1 and n-1..0
      !        (right)C(left)
$1j1#          Insert a zero after each number and take first n numbers

```

# Answer
> 7 votes
# Jelly, 5 bytes

```
Ż+¥¡1

```

Try it online!

Full program taking \\$n\\$ from STDIN and outputting coefficients ascending.

It's always felt a bit silly that the only "repeat" quick is designed for Fibonacci-like recurrences, but when it comes up I can't say it isn't useful.

```
         Since this is invoked as niladic, the initial left argument is 0.
    1    Starting with 1 on the right,
   ¡     repeat n times
  ¥      with the previous left argument replacing the right argument:
 +       vectorized add the right argument to
Ż        the left argument with a prepended 0.

```

# Answer
> 6 votes
# , 33 bytes

```
\(n,k,s=n+k)choose(s/2-.5,k)*s%%2
```

Attempt This Online!

Takes input as \\$n,k\\$ and outputs the coefficient of \\$x^k\\$ in \\$n\\$-th Fibonacci polynomial. Uses the formula from Wikipedia:

\\$F(n,k) = {\frac{n+k-1}{2}\choose k}\\$ if \\$n\\$ and \\$k\\$ have opposite parity.

# Answer
> 4 votes
# Factor \+ `math.polynomials`, 45 bytes

```
{ } .s { 1 } [ dup . tuck "\0"p* p+ t ] loop

```

Try it online!

Prints the sequence forever as ascending coefficients.

# Answer
> 4 votes
# Wolfram Language (Mathematica), 14 bytes

```
#~Fibonacci~x&

```

Try it online!

Returns a polynomial in \\$x\\$.

If \\$n,x\\$ were valid input, `Fibonacci` alone would do.

# Answer
> 3 votes
# Python, 62 bytes (@AnttiP)

```
f=lambda n:n>1and[*map(sum,zip(f(n-1)+[0]),[0,0]+f(n-2))]or[n]
```

Attempt This Online!

### Old Python, 64 bytes

```
f=lambda n:n>1and[*map(sum,zip(f(n-1)+[0]),[0,0]+f(n-2))]or[1]*n
```

Attempt This Online!

Naive implementation of the defining recurrence.

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

```
f=(n,k)=>n>1?f(n-1,k-1)+f(n-2,k):!k*n

```

Try it online!

# Answer
> 3 votes
# Vyxal, 8 bytes

```
ʁḂ$ƈ0ZfẎ

```

Try it Online!

Same idea as Bubbler's J answer.

```
ʁḂ$ƈ0ZfẎ
ʁ        # Exclusive zero range, 0..n-1
 Ḃ       # Bifurcate, push reverse without popping
  $      # Swap
   ƈ     # Binomial coefficients
    0Zf  # Append zero after each
       Ẏ # Only keep the first input items

```

Porting pajonk's Python answer is 8 bytes as well:

# Vyxal, 8 bytes

```
+₌∷½⌊⁰ƈ*

```

Try it Online!

# Answer
> 3 votes
# Python 2, 43 bytes

```
lambda n,k:2**(n*(n-~k))/(4**n-1)**-~k%2**n

```

Try it online!

Uses an arithmetic expression for the binomial adapted to \\$ \binom{\frac{n+k-1}2}{k}\\$ in a way that gives 0 if the top isn't a whole number.

## Python 2, 48 bytes

```
f=lambda n,k:n>0and(k*k+n<2)+f(n-1,k-1)+f(n-2,k)

```

Try it online!

A recursive expression taken from tsh for Pascal's triangle but tilted.

# Answer
> 2 votes
# Python3, 139 bytes:

```
def f(n):d={};F(n,d);return[d.get(i,0)for i in range(n-1,-1,-1)]
def F(n,d,c=0):
 if n==1:d[c]=d.get(c,0)+1
 if n>1:F(n-1,d,c+1);F(n-2,d,c)

```

Try it online!

# Answer
> 2 votes
# Charcoal, 32 bytes

```
ＮθＦ⊕θ⊞υ⎇‹ι²ιΣＥ…⮌υ²×κ∨λＸχθＩ↨⊟υＸχθ

```

Try it online! Link is to verbose version of code. Takes `n` as input and outputs the list of coefficients in descending order. Explanation:

```
Ｎθ

```

Input `n`.

```
Ｆ⊕θ

```

Repeat `n+1` times.

```
⊞υ⎇‹ι²ιΣＥ…⮌υ²×κ∨λＸχθ

```

Except for the first two numbers (which are just `0` and `1`) multiply the last number by a very large base (`10ⁿ`) and add on the penultimate number.

```
Ｉ↨⊟υＸχθ

```

Interpret the last value as a number in that very large base and output the "digits".

# Answer
> 2 votes
# Python, ~~58~~ ~~52~~ 50 bytes

*Edit: -8 bytes thanks to 301\_Moved\_Permanently.*

```
lambda n,k:(n+k)%2*math.comb(n+k>>1,k)
import math
```

Attempt This Online!

Port of my R answer.

# Answer
> 2 votes
# 05AB1E, ~~8~~ 6 bytes

```
λ0š0ζO

```

Outputs the infinite 1-based sequence. The inner coefficient-lists are output in ascending order for -2 bytes.

Try it online.

Since I was curious, a port of *@Bubbler*'s J answer would be **9 bytes**:

```
Ý¨Âc€¾RI£

```

Outputs the 0-based \\$n^{th}\\$ list, in descending order.

Try it online or verify all test cases.

**Explanation:**

```
λ         # Create a recursive environment,
          # to result in the infinite sequence
          # Implicitly starting at a(0)=1
          # Where every following a(n) is calculated as:
          #  (implicitly push the a(n-2)'th and a(n-1)'th terms
          #  (where a(-1)=0 in the first iteration)
 0š       #  Prepend a 0 in front of the top a(n-1)'th term
          #  (which implicitly converts integers to digit-lists first)
    ζ     #  Pair and zip/transpose the two lists,
   0      #  with 0 as filler since the lists are of unequal lengths
     O    #  Sum each inner pair
          # (after which the infinite sequence is output implicitly)

Ý         # Push a list in the range [0, (implicit) input]
 ¨        # Remove the last item to make the range [0,input)
  Â       # Bifurcate; short for Duplicate & Reverse copy
   c      # Calculate the binomial coefficient of the values in the two lists at
          # the same positions
    €¾    # Prepend a 0 in front of each item
      R   # Reverse this list
       I£ # Keep just the first input amount of items
          # (after which this list is output implicitly as result)

```

# Answer
> 2 votes
# K (ngn/k), 22 bytes

```
{(0 0,x)+y,0}\[;!0;,1]

```

Try it online!

# Answer
> 1 votes
# Desmos, ~~62~~ 41 bytes

```
L=[n...0]
f(n)=mod(L+n,2)nCr((n+L-1)/2,L)

```

Function `f` outputs a list of coefficients in descending order, with a leading zero.

Try It On Desmos!

Try It On Desmos! - Prettified

# Answer
> 1 votes
# APL (Dyalog Unicode), 22 bytes SBCS

```
{a←¯1+⍳⍵⋄⍵↑,⍉↑(a!⌽a)0}

```

Try it on APLgolf!

---
Tags: code-golf, sequence, fibonacci, polynomials
---


# Question
Title: Convert Descriptive Notation to Algebraic Notation
# Introduction

Many old chess books use descriptive notation to notate squares on a chessboard, naming the file (column) of the square based on the starting piece positions of White or Black, depending on whose move it is. The ranks (rows) are numbered 1 through 8, with 1 being closest to the player. For example, from White's perspective, QR2 represents the file where the queenside rook started, on the 2nd rank from the bottom.

However, this system has been entirely replaced by algebraic notation in the past few decades, which simply notates files with letters a-h and rows with numbers 1-8, always "from White's point of view". Therefore it would be convenient to have a program that can translate squares from old books.

Note: This problem is the simplified inverse of Convert Algebraic notation to Descriptive notation

# Diagrams

### Descriptive notation

Credit: David Eppstein

### Algebraic notation

Credit: ILA-boy, Klin, Beao

# Task

Given a chess square as a string and either white or black's perspective in descriptive notation, output the chess square in algebraic notation. Reasonable inputs may be used, such as a boolean for white/black perspective. For simplicity, we do not handle moves (including captures) or special symbols (promotion, castling, blunders, end of game, etc.)

The inputs and outputs are case sensitive and follow the above diagrams, with descriptive notation always using capital letters and algebraic notation always using lowercase letters. You must take the input square as one string like "QR1", not two like "QR" and "1".

# Test cases

```
white,QR1 => a1
white,KR8 => h8
white,Q4  => d4
white,KN7 => g7
black,QR1 => a8
black,KR8 => h1
black,Q4  => d5
black,KN7 => g2

```

# Answer
# JavaScript (ES6), 62 bytes

Expects `(white)(string)`, where *white* is a Boolean flag.

```
w=>s=>"egfbchda"[(q=parseInt(s,b=29))/b%43%10|0]+(w?q%b:9-q%b)

```

Try it online!

### How?

We parse the descriptive notation as a base-29 string and save the result in \\$q\\$.

The row number is \\$q\bmod29\\$ for White and \\$9-(q\bmod29)\\$ for Black.

For the column, we apply this minimal perfect hash function:

$$\big(\lfloor q/29\rfloor\bmod43\big)\bmod10$$

| Column | String | \\$\lfloor q/29 \rfloor\\$ | \\$\bmod 43\\$ | \\$\bmod 10\\$ |
| --- | --- | --- | --- | --- |
| a | "QRx" | 781 | 7 | 7 |
| b | "QNx" | 777 | 3 | 3 |
| c | "QBx" | 765 | 34 | 4 |
| d | "Qx" | 26 | 26 | 6 |
| e | "Kx" | 20 | 20 | 0 |
| f | "KBx" | 591 | 32 | 2 |
| g | "KNx" | 603 | 1 | 1 |
| h | "KRx" | 607 | 5 | 5 |

### Example search code

This simple piece of code looks for the shortest valid hash functions of the form `parseInt(s, b) % m0 % m1` with \\$28\le b\le 36\\$ and \\$2\le m\_1\<m\_0\<100\\$.

It is quite inefficient because it tries all tuples \\$(b,m\_0,m\_1)\\$ even if \\$(b,m\_0)\\$ alone leads to an unrecoverable lookup collision. But this works fine for a such a limited search space.

```
const O = {
  "QR" : "a",
  "QN" : "b",
  "QB" : "c",
  "Q"  : "d",
  "K"  : "e",
  "KB" : "f",
  "KN" : "g",
  "KR" : "h"
};

let best = 1 / 0;

for(let b = 28; b <= 36; b++) {
  for(let m0 = 2; m0 <= 100; m0++) {
    for(let m1 = 2; m1 < m0; m1++) {
      let lookup = Array(m1).fill('?');

      if(Object.keys(O).every(key => {
        let i = parseInt(key, b) % m0 % m1;
        if(lookup[i] == '?') {
          lookup[i] = O[key];
        }
        return lookup[i] == O[key];
      })) {
        let str = lookup.join('').replace(/\?*$/, ''),
            code = `"${str}"[parseInt(s,${b})%${m0}%${m1}]`,
            score = code.length;
        if(score <= best) {
          best = score;
          console.log(`Score: ${score} : ${code}`);
        }
      }
    }
  }
}

```

Try it online!
> 10 votes

# Answer
# JavaScript, 68 bytes

```
s=>w=>'dcbaefgh'[x=s.at(-1),('P'>s)*4-~'BNR'.search(s[1])]+(w?x:9-x)

```

```
f=

s=>w=>'dcbaefgh'[x=s.at(-1),('P'>s)*4-~'BNR'.search(s[1])]+(w?x:9-x)

function test(white) {
  const table = document.createElement('table');
  for (const i of (white ? '12345678' : '87654321')) {
    const row = table.appendChild(document.createElement('tr'));
    for (const j of 'QR,QN,QB,Q,K,KB,KN,KR'.split(',')) {
      row.appendChild(document.createElement('td')).textContent = f(j + i)(white);
    }
  }
  document.body.appendChild(table);
}

test(true);
test(false);
```

```
table { display: inline-table; margin-right: 30px; border-collapse: collapse; border: 1px solid black; }
td { width: 25px; height: 25px; line-height: 25px; text-align: center; background: white; color: black; }
tr:nth-child(odd) td:nth-child(even), tr:nth-child(even) td:nth-child(odd) { filter: invert(); }
```
> 5 votes

# Answer
# Python, 65 bytes

```
lambda t,s:f'{97+((x:=int(s[1:],30))>>8^3+(s<"Q")):c}{(-t^x)%10}'
```

Attempt This Online!

### Old Python, 67 bytes (@xnor)

```
lambda t,s:f'{97+(11*ord(s[1])>>7^7*(s>"L")):c}{8**t*int(s[-1])%9}'
```

Attempt This Online!

### Old Python, 68 bytes (@ovs)

```
lambda t,s:f'{97+(11*ord(s[1])>>7^7*(s>"L")):c}{int(t*"-"+s[-1])%9}'
```

Attempt This Online!

### Old Python, 72 bytes

```
lambda t,s:"%c%i"%(97+("RNB".find(s[1])%4^7*(s<"Q")),int(t*"-"+s[-1])%9)
```

Attempt This Online!

A golfed version of @Adam's answer which I was advised is different enough to warrant a separate post.
> 5 votes

# Answer
# Jelly, ~~24~~ 22 bytes

```
ṪVN³¡%9Ṿṭ“¡ṭ."“¬’ḥịØaƲ

```

Try it online! (the footer is a test suite that tests all 64 possibilities from a given player's point of view)

Function submission. Takes the coordinates in descriptive notation as a function argument, and the viewpoint (white=0, black=1) as a command-line argument.

## Explanation

```
ṪVN³¡%9Ṿṭ“¡ṭ."“¬’ḥịØaƲ
Ṫ                       On the last character of the input,
 V                      convert it to a number,
  N                     negate
    ¡                   a number of times
   ³                    equal to the command-line argument,
     %9                 wrapping-modulo by 9,
       Ṿ                convert back to a string,
        ṭ               and prepend
                 ḥ      {the result of} the randomly generated function
         “¡ṭ."“           #29699285
              “¬’         with codomain [1..8]
Ṫ                    Ʋ    applied to the input minus its last character, after
                  ịØa     indexing into the lowercase alphabet

```

The probability that a randomly generated function with an 8-element codomain will map the eight column names onto eight different outputs is approximately 1 in 416. As such, it's possible to convert the column names from descriptive to algebraic notation simply by searching through Jelly's catalogue of random functions to find one that's a perfect hash function for the given inputs (i.e. it maps each of them to a different number from 1 to 8), and specify the codomain using an 8-character string that contains the desired output column names in the order with which the function generates them. Function #2423 happens to have the desired behaviour (I simply checked random functions until I found one that worked).

However, doing this requires the column names to be given explicitly. It's golfier to express them by indexing into the alphabet, but this requires finding a function that maps each of the eight column names onto a different number from 1 to 8 *in the correct order*. The odds of any given randomly generated function happening to do this are 1 in 16777216. After searching through tens of millions of randomly generated functions, I discovered that function #29699285 happens to have the desired behaviour.

When an appropriate function for converting column names is available, the only remaining requirement is to remove the row number before running the function, subtract from 9 if necessary, and add it back at the end. (The conditional subtraction from 9 is done by conditionally negating it, and then taking its value modulo 9.)
> 4 votes

# Answer
# Python, 85 bytes

```
lambda t,s:"%c%i"%(101-(q:="Q"in s)+(2*q-1)*~"BNR".find(s[1]),9*t-(2*t-1)*int(s[-1]))

```

Attempt This Online!

Takes in the integer 0 if it's white's move, 1 if it's black's move, along with the notation string. Returns a string.

## Explanation

Not much of an explanation, but here's the code separated into a series of steps:
```
def f(t,s):
  q=0+("Q"in s)
  r="BNR".find(s[1])
  u=(2*q-1)*~r
  col=100-(q-u)
  x=(2*t-1)
  row=9*t-x*int(s[-1])
  return "%c%i"%(col,row)

```
> 3 votes

# Answer
# Batch Script, 179 Bytes

```
SET t=%2
SET /A a=96,p=%t:~-1%
FOR %%? in (QR QN QB Q K KB KN KR)DO SET /A a+=1,n=9-(((9-p)*(1-%1))+p*%1)&IF %%? == %t:~0,-1% CMD /C EXIT %%a%%&CALL ECHO %%=exitcodeAscii%%%%n%%

```

This is assuming `@ECHO OFF` is enabled. The second arg is the string (ie QR1), and 1st is the side. 0 for white, 1 for black. For example on CMD, if file is named chess.bat

```
CALL chess.bat 0 QR1

```

returns `a1`. I use the built-in variable `=exitcodeAscii` to get the letters from a-h, the rest is just a simple FOR loop.
> 3 votes

# Answer
# Retina 0.8.2, 49 bytes

```
T`d`Rd`b.+
T`QKl,`d-e_
+T`b-gBNR`a-cf-h_BN`.[A-Z]

```

Try it online! Link includes test cases. Explanation:

```
T`d`Rd`b.+

```

For black, subtract the digit from `9`, i.e. transliterate `0-9` to `9-0`.

```
T`QKl,`d-e_

```

`Q` becomes `d`, `K` becomes `e`, and delete the `white,`/`black,` indicator.

```
+T`b-gBNR`a-cf-h_BN`.[A-Z]

```

For each column away from the centre, update the letter, e.g. `QR``dR``cN``bB``a`.
> 2 votes

# Answer
# Python 3.10, 82 bytes

```
lambda b,s:C[C.find(s[:-1])-1]+str(abs(9*b-int(s[-1])))
C="dQeKaQRbQNcQBfKBgKNhKR"
```

Attempt This Online!

Testing out dictionary interleaving idea which is a little shorter than converting to ascii codes with `chr`. "Q" and "K" have to come first, otherwise they will match for at "QR".

-4 bytes using `find` instead of `index` and a better rank calculation for white/black.
> 1 votes

# Answer
## Batch, 126 bytes

```
@set s=%2
@set/ar=(%1*7^^%s:~-1%-1)+1
@for %%i in (QR.a QN.b QB.c Q.d K.e KB.f KN.g KR.h)do @if %%~ni==%s:~,-1% echo%%~xi%r%

```

Takes a boolean (0/1) and a string as command-line parameters (-2 bytes by abusing the input format to take 0 or 7 as the first parameter). Explanation:

```
@set s=%2

```

Get the second parameter into a variable so that we can slice it.

```
@set/ar=(%1*7^^%s:~-1%-1)+1

```

Calculate the descriptive row from the algebraic row by XORing the 0-indexed row with 0 or 7 as appropriate.

```
@for %%i in (QR.a QN.b QB.c Q.d K.e KB.f KN.g KR.h)do @if %%~ni==%s:~,-1% echo%%~xi%r%

```

Based on my answer to the linked challenge, loop over the pairs of descriptive and algebraic columns and output the algebraic column corresponding to the descriptive column. Note that `echo` ignores most punctuation immediately after the `o` which I use to consume the `.` that's part of the `~x` extension, saving 2 bytes.
> 1 votes

# Answer
# 05AB1E, 29 bytes

```
Çнθ<…BNR¹Åsk+.•7œΔ&‘•èI9*¹θα«

```

Port of *@tsh*' JavaScript answer

Inputs in the order `notation,perspective`, where the perspective is `1`/`0` for black/white respectively.

Try it online or verify all test cases.

**Explanation:**

```
Ç           # Convert the (implicit) first input-string to a list of codepoint-integers
 н          # Leave just the first codepoint-integer
  θ         # Leave just its last digit
   <        # Decrease it by 1:
            #  0 if 'Q' and 4 if 'K'
…BNR        # Push string "BNR"
    ¹       # Push the first input-string again
     Ås     # Pop and leave just its middle character
            # (if the input contains just two characters, those will be the 'middle')
       k    # Get the index of this middle in the string (or -1 if not found):
            #  0 if 'B'; 1 if 'N'; 2 if 'R'; -1 if 'Q#'/'K#'
+           # Add the two integers together
 .•7œΔ&‘•   # Push compressed string "cbaefghd"
         è  # Index the earlier integer into this string
            # (0-based modular, so the -1 indexes into the trailing "d")
I           # Push the second input-digit
 9*         # Multiply it by 9
   ¹        # Push the first input-string yet again
    θ       # Pop and leave its last character (the digit)
     α      # Get the absolute difference of it with the (9*perspective)
      «     # Append this digit to the earlier character
            # (after which the result is output implicitly)

```

See this 05AB1E tip of mine (section *How to compress strings not part of the dictionary?*) to understand why `.•7œΔ&‘•` is `"cbaefghd"`.
> 1 votes

# Answer
# Charcoal, 35 bytes

```
§β⌕⪪”＆↓↶Ｇ«ü\`~6ε⪪θ⊞↷” …η⊖ＬηＩ⎇Ｎ⁻⁹ΣηΣη

```

Try it online! Link is to verbose version of code. Takes the White/Black flag as a boolean. Explanation:

```
§β⌕⪪”＆↓↶Ｇ«ü\`~6ε⪪θ⊞↷” …η⊖Ｌη

```

Look up the column in a compressed table and output the lowercase letter with that index.

```
Ｉ⎇Ｎ⁻⁹ΣηΣη

```

Subtract the row from `9` if the player is Black.
> 0 votes

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


title: Print the numbers -1, 0, 1

text:
# Question
Title: Print the numbers -1, 0, 1
This is a very simple challenge, and it is to print the numbers `-1`, `0`, and `1`.

*The following paragraph is credited to Print numbers from 1 to 10*
Your output format can be whatever your language supports. This includes arbitrary separators (commas, semicolons, newlines, combinations of those, etc., but no digits), and prefixes and postfixes (like `[...]`). However, you may not output any other numbers than -1 through 1. Your program may not take any input. Standard loopholes are disallowed.

This is , so the shortest answer in bytes wins. Happy golfing!

# Answer
# Jelly, 3 bytes

```
-r1

```

Try it online!

```
1r-

```

Try it online!

```
-ŒR

```

Try it online!

```
1ŒR

```

Try it online!

```
Ø-Ż

```

Try it online!

```
Ø+Ż

```

Try it online!

```
-rN

```

Try it online!

```
1rN

```

Try it online!

```
2Ż’

```

Try it online!

```
3Ḷ’

```

Try it online!

and a bonus one:

# , 2 bytes

```
-R

```

Try it online!
> 3 votes

# Answer
# Pyt, 4 bytes

```
3ř⁻⁻

```

Try it online!

Explanation:

```
3      Push 3
ř      Push [1,2,3]
⁻⁻     Decrement twice
       Implicit print

```
> 2 votes

# Answer
# , 9 bytes

```
cat(-1:1)

```

Try it online!
> 2 votes

# Answer
# , 11 characters, 4 bytes

```
1**7**3**7**00**7**4023
```

Try it online!

Hexdump to prove byte count:

```
00000000: 3df0 3c09                                =.<.

```

This challenge is very easy in most languages, so I decided to solve it in a language where it's actually an interesting problem.

## Explanation

It took me ages to golf this down to 4 bytes – there are a really huge number of ways to do this with 12 characters, but reaching 11 is very difficult.

The only part of the code here that actually runs (after the first cycle, which just sets up the stack to mirror the structure of the program) is **`4623`** (which is the code generated by the code `4023` in the original program; the `4023` is a literal which pushes **`4623`** to the stack; as usual, I'm using non-bold for commands that just push code to the stack and bold for the commands they push). After the first cycle, each new cycle runs the top stack element, without actually popping it from the stack.

The **`4`** swaps the top two stack elements, and inserts a blank element between them (thus, *a* *b* goes to *b* *blank* *a*). Then the **`6`** analyzes the top element to determine what source code is most likely to have produced it, and appends the resulting source code to the element below it (which will be blank at this point because we just ran a **`4`**). Thus, the net effect of **`46`** is to swap the top two stack elements, and replace the top stack element with (a guess at, but the guesses are always correct for this program) the source code that produced it.

**`2`** duplicates the top stack element, and **`3`** outputs the top stack element, popping both it and the element below. Thus, the net effect of **`23`** is to output and pop the top stack element, without disturbing elements below it.

As such, the effect of our program **`4623`** is to pop and output the source code that produced the second stack element, whilst leaving the top stack element unchanged. The top stack element in question is the actively running program (which doesn't get popped when we start to run it), so once the program finishes running, it'll just run again, etc. – this is in effect an infinite loop which, for each element on the stack, outputs the source code that produced it (and eventually the program crashes due to stack exhaustion). As such, the data being given to the output routines is `00`, `3`, `1` (i.e. the sections of the *source code* in between **`7`**s – the source code has already run to produce runnable code by this point, but the source is reconstructed from the runnable code rather than the runnable code actually being run).

The first `0` sent to the output routine selects numerical output mode. Then, `0`, `3`, `1` get output. The numerical value of a string in 7 is the total number of `1` and **`7`** characters it contains, minus the total number of `0` and **`6`** characters it contains. Thus, the values of these strings are -1, 0, and 1, as required by the question.

One complication is that if we try to output an empty string, we just get no output, rather than its numerical value of 0 being output: this is a special case needed because the output command **`3`** is the primary way to pop and discard stack elements (basically, you push an empty element above the one you want to pop, output that empty element and pop the element below as a side effect). A "clean" way to output 0 thus requires outputting a string like `01` which is nonempty and has a numerical value of zero. This program uses `3`, which is shorter, but the numerical output formatter will append a comma when outputting strings ending `3` (in addition to outputting their numerical value). As a consequence, the output of the program is actually `-1 0, 1`, but this is permitted by the question. (All eight of the one-character strings either have a side effect when output via the numerical formatter, or else have a value different from zero, so outputting `-1 0 1` exactly would make the program longer.)
> 1 votes

# Answer
# JavaScript, ~~19~~ 15 bytes

~~`[-1,0,1].map(alert)`~~

`alert([-1,0,1])`
> 0 votes

# Answer
# Python - 15 bytes

```
print("-1 0 1")

```

I would say "Good luck improving this.", but past experience has taught me never to assume: though, this won't be easily beat (for i in range(3), %ding the spaces and %sing the 1s are all overweight, so you can eliminate those.)
> 0 votes

---
Tags: code-golf, number, sequence, kolmogorov-complexity
---


title: A047841: Autobiographical numbers

text:
# Question
Title: A047841: Autobiographical numbers
# Definition

Here is the process to describe a number:

* For each number from `0` to `9` that is present in the number:
* Write down the frequency of that digit and then the digit.

For example, for the number `10213223`:

* There is `1` occurrence of `0`,
* `2` occurrences of `1`,
* `3` occurrences of `2`,
* `2` occurrences of `3`.

Therefore, the number that describes `10213223` is `10213223` (`10` from the first property, `21` from the second, etc.).

Note that the number of occurrences of a digit **may be greater than 9**.

# Task

You are to print/output all numbers that describe themselves.

# Specs

* Standard loopholes apply, except that you are **allowed** to hardcode the output or store information related to the output in your program.
* The numbers in the output can be in **any order**.
* The numbers in the output are **allowed** to have duplicates.
* You may use **any separator**, if you choose to print instead of output.
* You are **allowed** to prefix and/or postfix output if you choose to print instead of output.
* The separator and the prefix and the postfix may **not** contain any digits (U+0030 to U+0039).
* The solution must compute in **one day**.

# Full list (109 items)

```
22
10213223
10311233
10313314
10313315
10313316
10313317
10313318
10313319
21322314
21322315
21322316
21322317
21322318
21322319
31123314
31123315
31123316
31123317
31123318
31123319
31331415
31331416
31331417
31331418
31331419
31331516
31331517
31331518
31331519
31331617
31331618
31331619
31331718
31331719
31331819
1031223314
1031223315
1031223316
1031223317
1031223318
1031223319
3122331415
3122331416
3122331417
3122331418
3122331419
3122331516
3122331517
3122331518
3122331519
3122331617
3122331618
3122331619
3122331718
3122331719
3122331819
10413223241516
10413223241517
10413223241518
10413223241519
10413223241617
10413223241618
10413223241619
10413223241718
10413223241719
10413223241819
41322324151617
41322324151618
41322324151619
41322324151718
41322324151719
41322324151819
41322324161718
41322324161719
41322324161819
41322324171819
1051322314251617
1051322314251618
1051322314251619
1051322314251718
1051322314251719
1051322314251819
1051322325161718
1051322325161719
1051322325161819
1051322325171819
5132231425161718
5132231425161719
5132231425161819
5132231425171819
5132232516171819
106132231415261718
106132231415261719
106132231415261819
106132231426171819
106132231526171819
613223141526171819
1011112131415161718
1011112131415161719
1011112131415161819
1011112131415171819
1011112131416171819
1011112131516171819
1011112141516171819
1011113141516171819
1111213141516171819
10713223141516271819
101112213141516171819

```

# References

# Answer
> 8 votes
# gawk, 161 bytes

```
BEGIN{
    for(split("0 10 2 2 1 1 1 1",a);c=c<11;n=o=_){
        while(++$c>a[c]+1)$(c++)=0;
        for(i in a)n=$i?n$i i-1:n;
        for(i=10;i--;)if(d=gsub(i,i,n))o=d i o;
        if(n==o)print n
    }
}

```

(line breaks and tabs for clarity)

It's a simple counter which uses the fact that each number has a limited occurrence. For instance is 0 no more than one time in any number, 1 no more than 11 times, 2 no more than 3 times ... and so on.

This way there are only 124415 numbers to check.

It then creates all numbers and checks their validity.

Completes in a few seconds.

# Answer
> 2 votes
# dc, 487 bytes

Hardcoded the solution. I start with 22 and add the differences to get the the next numbers. Some returning operations like adding 1 five times in a row are stored in registers.

This is my first program ever written in dc so it can probably golfed a lot more.

`[1+d1+d1+d1+d1+d]sa[1+d1+d1+d1+d97+d]sb[1+d1+d99+d1+d100+d]sc[1+d1+d1+d98+dlcx]sd[1+d100+d10000+d]se22d10213201+d98010+d2081+dlax11008995+dlax9800995+dlax208096+dlbxldx999891495+dlax2091108096+dlbxldx10410100909697+dldx30909100909798+dlcx9899+dlex1009999990079798+dlcx10909899+dlex4080909099989899+dlex1091000000+d100999998899089899+d1+d100+d10910000+d10 8^+d50709091 10 10^*+d397888989888989899+dlex10 6^+d10 8^+d10 10^+d10 12^+d1001 10 14^*+d9602010000000100000+d90398989999999900000+f`

You can execute the program using `dc -e "[solution]"`, where \[solution\] is the string above. It outputs the numbers in reverse order. `dc -e "[solution]" | sort -n` for output in the same order as the list.

# Answer
> 2 votes
# Haskell, 157 bytes

```
c=concat
d!n=['1'..n]>>[d]
r n=['0'..n]
a=r '9'
b s=c[shows n[d]|d<-a,n<-[sum[1|x<-s,x==d]],n>0]
main=print[x|x<-b.c.zipWith(!)a<$>mapM r"1;33222211",x==b x]

```

Try it online!

Inspired by the gawk answer, this loops over all strings of 0–1 zeros, then 0–11 ones, then 0–3 twos, .... It "biographs" the string (`b "01111122" == "105122"`) and prints that result if is, itself, autobiographical (`b x == x`).

# Answer
> 1 votes
# Ruby, 776 bytes

The rules say that "you are allowed to hardcode the output", so this solution does just that.

```
x="m|62wkn|65075|651sy|651sz|651t0|651t1|651t2|651t3|cp0ei|cp0ej|cp0ek|cp0el|cp0em|cp0en|ij2wi|ij2wj|ij2wk|ij2wl|ij2wm|ij2wnAh3Ah4Ah5Ah6Ah7AjwAjxAjyAjzAmpAmqAmrApiApjAsb|h1yp02|h1yp03|h1yp04|h1yp05|h1yp06|h1yp07Bc7Bc8Bc9BcaBcbBf0Bf1Bf2Bf3BhtBhuBhvBkmBknBnfFh8Fh9FhaFhbFk1Fk2Fk3FmuFmvFpnC08xC08yC08zC0bqC0brC0ejC81iC81jC84bCfu3EsxkfohEsxkfoiEsxkfojEsxkfraEsxkfrbEsxkfu3Et429yuEt429yvEt42a1nEt42hrf|1ej82kg93hy|1ej82kg93hz|1ej82kg93kr|1ej82kg9baj|1ej832ht8a3|t10qi0rmwpi|t10qi0rmwpj|t10qi0rmwsb|t10qi0y4qzv|t10qi2lo3hn|4nq1gm5kd1grG4p2zeraG4p2zerbG4p2zeu3G4p2zmjvG4p3l25nG4qr4enfG9c4v417|7ojtp0qb1maz|8fxg6lw9mtyj|29e6onjxe94gb|lc7bc5zbz4je3";a="|inj,|1fmye,|enb7ow,|enb7,|acnu,|3ovro98,|7ojtc".split',';b="ABCDEFG";7.times{|i|x.gsub! b[i],a[i]};x.split('|').map{|x|p x.to_i 36}

```

---

# Ruby, 116 bytes

A much shorter program that takes way too long to run, but given long enough should be able to do it. I do not know if it fits the time constraint.

```
f=->n{(?0..?9).map{|x|[n.to_s.chars.count{|c|c==x},x]}.select{|a|a[0]>0}.join.to_i}
(10**9).times{|i|p i if i==f[i]}

```

# Answer
> 1 votes
# ///, 542 bytes

```
/:/\/\///^/13223:!/31:*/
10:#/!223!:&/4^241:$/1819:(/51617:)/
!3!:%/5^142:@/111:-/*@121!:_/51:+/
!123!:=/41:A/617:B/19:C/*!3!:D/18:E/6^1=52:F/
#:G/
2^:H/*5^2:I/1!=($:J/_6:K/
&:L/*&:M/_7/22*2^*!1233C4C5C6C7C8C9G14G15G16G17GDGB+4+5+6+7+8+9)=5)=6)=7)=8)=9)J)M)_8)_9)A)6D)6B)7D)7B)8B*#4*#5*#6*#7*#8*#9F=5F=6F=7F=8F=9FJF_7F_8F_9FAF6DF6BF7DF7BF8BLJLML_8L_9LAL6DL6BL7DL7BL8BK(KJDKJBKMDKMBK5$KADKABK6$K7$*%(*%JD*%JB*%MD*%MB*%5$H(DH(BHJ$HM$
%(D
%(B
%J$
%M$
5^2($*EAD*EAB*E6$*6^142A$*6^152A$
EA$-=(D-=(B-=J$-=_7$-=617$-($*@121=($*@I
@12I*7^1=_627$*@22I

```

Try it online!

**Definitely** less than 1440 bytes for sure!!! Uses 28 constants along with the literal, an unusually high amount for ///.

# Answer
> 1 votes
# Husk, ~~21~~ 20 bytes

```
f₁N
=⁰dΣf←Ṡzem#d⁰ŀ10

```

Try it online!

Not sure if it will complete in one day, but it does a straightforward test and filters the infinite list of natural numbers by it. No hardcoding.

Theoretically, it will definitely print all autobiographical numbers, and proceed to check till the heat death of the universe.

-1 byte after correcting the algorithm.

# Answer
> 1 votes
# Jelly, 34 bytes

```
DFṢŒrU
3x8“¢¿‘;µ,€"J’$ŒPŒp€ẎḊÇƑƇVV

```

This program is too slow for TIO, but finished in 2 minutes 8.375 seconds on my computer (thus, less than one day, as required by the question). It can easily be optimized to work on TIO too:

## Jelly (Try It Online!), 36 bytes

```
DFṢŒrU
2x6“¢¿¤¤‘;µ,€"J’$ŒPŒp€ẎḊÇƑƇVV

```

Try it online! (The footer prints the list of results, plus a count of how many results there are.)

## Algorithm

The basic idea is to generate lists of (frequency, number) pairs and then check to see if they correspond to an autobiographical number (by collapsing them into a list of digits, then calculating how many times each digit appears and seeing if it matched the original list of (frequency, number) pairs). We have to generate every list that corresponds to an autobiographical number, but are allowed to also generate extras, as long as we can check and reject them within the time limit.

Any answer has at most one 0, eleven 1s, three 2s, three 3s, and two of any other digit. \\$2×12×4×4×3^6=279936\\$, a small enough list to check in a minute, so we can just generate all (frequency, number) lists with less than these frequencies to get the TIO version of the program. For the "main" submission, we also generate (useless) lists which can have up to four copies of digits in the 4…9 range, because doing so is slightly shorter to express in Jelly; that's \\$2×12×4^8=1572864\\$ lists which is still a small enough number to check within a day.

## Explanation

### Helper function `1Ŀ`

The helper function takes an arbitrary list of (frequency, digit) pairs, counts how many times each digit appears within the frequencies and digits, and returns the appropriate list of (frequency, digit) pairs, sorted by the digit.

If this function is run on a list of (frequency, digit) pairs that represent those of an autobiographical number and are sorted by the digit, the output will be the same as the input. Otherwise, the output will differ from the input.

```
DFṢŒrU
D        Split each number within the frequencies and digits into digits
 F       Recursive flatten, into a flat list of digits
  Ṣ      Sort the list of digits
   Œr    Run-length-encode, into (element, frequency) format
     U   Reverse each interior list, producing (frequency, digit) format

```

### Main program

```
3x8“¢¿‘;µ,€"J’$ŒPŒp€ẎḊÇƑƇVV
3x8                           [3,3,3,3,3,3,3,3]
       ;                      prepend
   “¢¿‘                       [1,11]
           "                  to each element
          €                     for all numbers from 1 to that element
         ,                      pair that number with
        µ                       the element's
            J’$                 0-based index
               ŒP  €Ỷ         for each subsequence of the resulting list
                 Œp             take its Cartesian product
                     Ḋ        discard the first result (the empty list [])
                        Ƈ     filter the lists, keeping those that
                       Ƒ        are unchanged upon
                      Ç         running the helper function 1Ŀ
                         V    numerical concatenation of frequency with digit
                          V   numerical concatenation of those concatenations

```

This is mostly very straightforward, with the only confusing part being the various amounts of flattening and unflattening that go on. In particular, the `ŒPŒp€Ẏ` portion is the best way I found to write "from these sublists, select one or possibly no elements from each, and concatenate them"; the `ŒP` chooses which sublists will have no elements selected, the `Œp€` selects one element from each of the rest, and the  collapses the structure which the `ŒP` introduced.

## If there were no time limit…

you could do the task in 13 bytes:

```
ṢŒrUFV
2*JÇƑƇ

```

Try it online! (starts the search from just before a valid answer, and returns only 7 answers, so that you can see the program working)

The idea here is to search every possible number from 1 to 21000, returning only those which are autobiographical. Obviously, this won't finish in a reasonable length of time. (The choice of 21000 is mostly arbitrary – it's a number that can be calculated in Jelly using only three bytes. I couldn't find a way to calculate a number large enough using only two.)

I have a suspicion that there are a range of possible answers to this question which make different speed/brevity tradeoffs, so it's probably going to be possible to beat 34 bytes by making a program that takes longer to run but still fits within a single day. It's hard to know exactly where the byte savings should go, though.

# Answer
> 0 votes
# Python 2.7 - 684 bytes

```
o=[22]
i=[[10213223,100096],[21322314,5],[31123314,5],[31331415,404],[1031223314,5],[3122331415,404],[10413223241516,303],[41322324151617,20202],[1051322314251617,202],[1051322325161718,10101],[5132231425161718,10101],[5132232516171819,0],[106132231415261718,101],[106132231426171819,0],[106132231526171819,0],[613223141526171819,0],[1011112131415161718,10101]]
l=[1011112131416171819,1011112131516171819,1011112141516171819,1011113141516171819,1111213141516171819,10713223141516271819,101112213141516171819]
for n in i:
 for x in range(n[0],n[0]+n[1]):
  m="";x=str(x)
  for v in range(10):
   v=str(v);c=x.count(v)
   if c!=0:
    m=m+str(c)+v
    if m==x:o.append(m)
o+=l
print o

```

Kind of half hard coded and half computed. It takes the approach of splitting the numbers into groups of a manageable size with an upper and lower limit. The list i stores the lower limit and the difference between it and the upper limit as a nested list, All potential candidates are then checked within the range added to the output list o. The last 7 numbers are so far apart that it is cheaper to store them in their own list and add it at the end.

It currently runs in a couple of seconds and obviously increasing the group size would reduce the byte count but increase the run time. Not sure what it would come down to and still be within the one day limit.

---
Tags: code-golf, string, kolmogorov-complexity, sequence, integer
---