# Question
Title: CGAC2022 Day 16: Playing with bits, Part 2
Part of **Code Golf Advent Calendar 2022** event. See the linked meta post for details.

---

As soon as the Elves get bored with the last week's game, Bin comes up with a new game. The rules are similar, except the Elves are supposed to say the numbers that have its "left side" equal to its "right side" when written in binary. The "left" and "right" sides are defined as the first and last `floor(k/2)` bits, where `k` is the total number of bits.

Some examples:

* The numbers that are just two copies joined together, such as 3 (`11`), 10 (`1010`), 15 (`1111`), ... are valid. This sequence is A020330.
* 1 (`1`) is valid because its left and right parts are both empty, and as are 18 (`10010`) and 22 (`10110`) because their left and right are both `10`.
* 17 (`10001`) is not valid because `10` != `01`.

You can use any of I/O methods:

* Output the corresponding sequence infinitely
* Given the index `k` (may be 1- or 0-indexed), output the `k`th number in the sequence
* Given `k`, output the first `k` numbers of the sequence

Standard rules apply. The shortest code in bytes wins.

## Test cases

```
1, 3, 5, 7, 10, 15, 18, 22, 27, 31, 36, 45, 54, 63, 68, 76, 85, 93, 102, 110,
119, 127, 136, 153, 170, 187, 204, 221, 238, 255, 264, 280, 297, 313, 330, 346,
363, 379, 396, 412, 429, 445, 462, 478, 495, 511, 528, 561, 594, 627, 660, 693,
726, 759, 792, 825, 858, 891, 924, 957, 990, 1023, 1040, 1072, 1105, 1137, 1170,
1202, 1235, 1267, 1300, 1332, 1365, 1397, 1430, 1462, 1495, 1527, 1560, 1592,
1625, 1657, 1690, 1722, 1755, 1787, 1820, 1852, 1885, 1917, 1950, 1982, 2015,
2047, ...

```

This sequence is not yet on OEIS.

# Answer
> 5 votes
# Vyxal, 8 bytes

```
bI∩v≈A)ȯ

```

Try it Online!

```
       ȯ # First N integers
------)  # Where...
b        # Binary
 I       # Split into two halves
  ∩      # Transposed
     A   # Are all...
   v     # Pairs...
    ≈    # Each all the same element?

```

# Answer
> 5 votes
# Jelly, 10 bytes

```
1BŒHṛ"Ƒ/Ɗ#

```

Try it online!

Full program outputting the first `k` numbers in the sequence given `k` as a command-line argument. (It's worth noting that the less-fun `1BŒHZE€P$Ʋ#` is shorter if 0 is included in the sequence.)

```
1       Ɗ#    Take the first k integers counting up from 1 which satisfy:
 B            Get the binary digits of the candidate
  ŒH          and split them in half, with the middle going to the left.
      Ƒ/      Is the left half unchanged by
    ṛ"        replacing its elements with corresponding elements of the right?

```

# Answer
> 4 votes
# Charcoal, 22 bytes

```
≔⍘⊕Ｎ²θＩ÷⍘×²Φθ⊖κ²⊕⁼§θ¹0

```

Try it online! Link is to verbose version of code. Outputs the `n`th value. Explanation:

```
≔⍘⊕Ｎ²θ

```

Convert `n+1` to base 2 as a string.

```
Ｉ÷⍘×²Φθ⊖κ²⊕⁼§θ¹0

```

Delete the second character, duplicate the result, convert back from base 2, and halve the result if the second character was a `0`.

# Answer
> 4 votes
# Python, 68 bytes

```
i=1
while[(k:=bin(i)[2:])[:(j:=len(k)//2)]==k[-j:]and print(i)]:i+=1

```

Attempt This Online!

Outputs the sequence indefinitely

# Answer
> 4 votes
# Retina 0.8.2, 67 bytes

```
.+
$*11
+`(1+)\1
$+0
01
1
1(.)(.*)
1$+1$+$1
.0$|1$

1
01
+`10
011
1

```

Try it online! Link includes test cases. Explanation: Port of my Charcoal answer.

```
.+
$*11

```

Convert `n` to unary and add `1`.

```
+`(1+)\1
$+0
01
1

```

Convert `n+1` to binary.

```
1(.)(.*)
1$+1$+$1

```

Delete the second character of the binary string and duplicate the rest, then append the second character.

```
.0$|1$

```

If the original second character was a `0` then integer divide the binary number by `2`. (Delete the original second character in any case.)

```
1
01
+`10
011
1

```

Convert from binary to decimal.

# Answer
> 3 votes
# JavaScript (V8), ~~54~~ ~~51~~ 48 bytes

```
for(i=j=n=2;;i=i%~-n?i+2:n*=j^=3)print(i*n+i>>j)

```

Try it online!

Fast and shorter than RegEx solution and scan all

# Answer
> 3 votes
# Jelly, 9 bytes

```
1BŒHw/ḂƲ#

```

A full program that accepts an integer, \\$k\\$, and prints a Jelly representation of the list of the first \\$k\\$ entries.

**Try it online!**

### How?

```
1BŒHw/ḂƲ# - Main Link: integer, k
1       # - starting with j=1, count up and yield the first k integers for which:
       Ʋ  -   last four links as a monad - f(j):
 B        -     binary digits (j)
  ŒH      -     split into halves - e.g. [1,0,0,1,1] -> [[1,0,0],[1,1]]
     /    -     reduce by:
    w     -       first index of sublist (right) in (left)
                       0 : does not exist
                       1 : at the start -> a "left equals right" number
                       2 : exists but is the second sublist of that length
                       (other outputs not possible as only two sublists of that length exist)
      Ḃ   -     modulo two -> 1 if j is a "left equals right" number else 0

```

# Answer
> 2 votes
# JavaScript (V8), 63 bytes (fast)

Prints the sequence infinitely.

```
for(i=k=n=1;k+=q=!(n&n+1);n+=2**(k-2*q>>1)+!(k*i++&!q))print(n)

```

Try it online!

---

# JavaScript (V8), 56 bytes (slow)

Prints the sequence infinitely.

```
for(n=0;;)/^(.*).?\1$/.test((++n).toString(2))&&print(n)

```

Try it online!

# Answer
> 2 votes
# Pyth, 22 bytes

```
.V1K.BbJ.:K/lK2IqhJeJb

```

Try it online!

Prints the sequence infinitely.

```
.V1                     # Run an infinite loop from 1 with b
   K.Bb                 # Initialize K as binary representation of b
       J.:K/lK2         # Get all substrings of len(K)/2 and set as J
                 hJ     # First value of J
                   eJ   # Last value of J
               Iq       # If equal
                     b  # Print b

```

# Answer
> 2 votes
# \>\<\>, 72 bytes

```
1:&:1(?v:2%$2,:1%-20.
]l2%?~1\~l:2%+2,[r
=?v${=*>l1
?v\
&/v&oan:
0.>&1+0

```

Try it online!

# Answer
> 2 votes
# JavaScript (V8), 50 bytes

```
for(n=p=0;;n%(1<<p/2)^n>>-~p/2||print(n))p+=++n>>p

```

Try it online!

And this is 64 bytes in C.

Thanks jdt for -2 bytes on JS. Thanks l4m2, jdt for -3 bytes on C.

# Answer
> 2 votes
# Pip, 20 bytes

```
W UiI0=$@?R*RCHTBiPi

```

Try It Online! (Since DSO doesn't handle infinite loops well, this link outputs elements of the sequence less than 1000.)

### Explanation

The fact that the `CH` builtin makes the first half shorter than the second half when chopping odd-length strings is a bit of a problem here.

```
W UiI0=$@?R*RCHTBiPi
                      i is 0 (implicit)
W                     Loop while
  Ui                  i incremented is truthy:
               TBi      Convert i to binary
             CH         Chop into two halves (if uneven, the second half is longer)
            R           Reverse (the potentially longer second element is now first)
          R*            Reverse each element
       $@?              Find index of first element in second element
    I0=                 If that index is zero:
                  Pi      Print i

```

Here are some worked examples to showcase the core logic. The `@?` operator gets the index of the first occurrence of its right argument as a substring of its left argument; if it is not a substring, the operator returns nil, here represented as `()`.

```
            i  10      13      18       21
          TB   1010    1101    10010    10101
        CH     [10;10] [11;01] [10;010] [10;101]
       R       [10;10] [01;11] [010;10] [101;10]
     R*        [01;01] [10;11] [010;01] [101;01]
  $@?          0       ()      0        1
0=             1       0       1        0

```

# Answer
> 1 votes
# Pip, 43 bytes

```
W1{k:(l:TBo)^@#l//2I#l%2k@1PK0Ik@0=k@1PoUo}

```

Try It Online!

Outputs the sequence indefinitely. Won't run on the above link very well as DSO doesn't handle infinite loops well, use this to verify. Explanation:

```
k:(l:TBo)^@#l//2

```

Converts `o` to binary, splits into two.

```
I#l%2k@1PK0

```

If the length of the binary string is odd, remove the first element from the second half.

```
Ik@0=k@1PoUo

```

If both halves are the same, print `o`, then increment `o`

# Answer
> 1 votes
# Nibbles, 9.5 bytes (19 nibbles)

```
|,~~++!;``@$>>`\~@!

```

```
|                    # filter
 ,~                  # 1..infinity
   ~                 # for falsy results of:
    ++               #   sum of flattened list of
      !              #   zip together
                  !  #   getting abs differences
        ``@$         #     bits of input
       ;             #     (and save this)
                     #     with
                 @   #     saved bits of input
              `\~    #     split into 2 chunks
            >>       #     discarding the first chunk

```

# Answer
> 1 votes
# Husk, 9 bytes

```
föΠFz=½ḋN

```

Try it online!

```
f           # filter
        N   # 1..infinity
 ö          # with composition of 4 functions:
       ḋ    #   get list of binary digits
      ½     #   split into list of two halves
   F        #   fold across this list
    z       #     zip the two halves together
     =      #       by equality
  Π         #   and get the product

```

# Answer
> 1 votes
# 05AB1E, 9 bytes

```
∞ʒ2в2äøøË

```

Try it online!

Outputs the infinite sequence.

* -6, -9 thanks to Steffan
* -1 thanks to Kevin Cruijssen

**Explanation:**

```
∞ʒ2в2äøøË
∞            # Get all integers (>= 1)                    Example for n=19
 ʒ           # where the following evaluates to True:
  2в         # The binary representation of the number    10011
    2ä       # Sliced into two pieces                     [[1, 0, 0], [1, 1]]
      øø     # Zipped together twice                      [[1, 0], [1, 1]]
        Ë    # Are they equal?                            0

```

Previous 19-byte answer:

```
∞ʒbVYg2÷UXYs£XYs.£Q
∞ʒ                          # Get all integers (>= 1) where the following evaluates to True:
  bV                        # Convert to binary and save in Y
    Yg                      # Get the length of Y
      2÷                    # Integer-divide by 2
        UX                  # Save this in X for later
          Ys£               # And get that many elements from the front of Y
             XYs.£          # Do the same but from the back of Y
                  Q         # Check if they are equal
                            # (Implicit output)

```

# Answer
> 1 votes
# Excel, 75 bytes

```
=LET(x,ROW(A:A),FILTER(x,LET(b,BASE(x,2),s,LEN(b)/2,LEFT(b,s)=RIGHT(b,s))))

```

# Answer
> 1 votes
# Factor \+ `lists.lazy`, 46 bytes

```
[ 1 lfrom [ >bin halves swap tail? ] lfilter ]

```

Attempt This Online!

Returns an infinite lazy list of the sequence.

* `1 lfrom` the natural numbers
* `[ ... ] lfilter` take the ones that...
* `>bin` convert integer to binary string
* `halves` split in half with the second half larger, e.g. `"101"` -\> `"1" "01"`
* `swap tail?` does the second half end with the first half?

# Answer
> 1 votes
# PARI/GP, 59 bytes

The basic idea is `is(n)=my(v=binary(n)); v[1..#v\2]==v[(#v+3)\2..#v]`.

```
for(n=1,oo,v=binary(n);v[1..#v\2]==v[(#v+3)\2..#v]&&print(n))

```

# Answer
> 1 votes
# x86 32-bit machine code, 21 bytes

```
40 0F BD C8 D3 D8 72 02 D1 C8 D3 C0 89 C2 D3 E0 09 D0 D1 E8 C3

```

Try it online!

Following the `regparm(1)` calling convention, this takes the 1-indexed `k` in EAX and returns the `k`th number in EAX.

---

If we look at the left halves *inclusive* of the middle bit (if it exists), they form a useful pattern: **1**, **1**1, **10**1, **11**1, **10**10, **11**11, **100**10, **101**10, **110**11, **111**11, **100**100, **101**101, **110**110, **111**111, ...
They are the binary representations of the positive integers, grouped by length and then with each group repeated twice, first with the last bit omitted from the remainder of the number, then with the last bit kept.

Add 1 to the 1-indexed `k`, to get numbers starting with 2=102, then take out the second bit of each number and use it to determine whether it goes in the first or second repetition of its group:

```
n       k   k+1
**1**₂      1   **1**0₂
**1**1₂     2   **1**1₂
**10**1₂    3   **1**0**0****11**1₂    4   **1**0**1****10**10₂   5   **1**1**0****11**11₂   6   **1**1**1****100**10₂  7   **1**0**00****101**10₂  8   **1**0**01****110**11₂  9   **1**0**10****111**11₂  10  **1**0**11****100**100₂ 11  **1**1**00****101**101₂ 12  **1**1**01****110**110₂ 13  **1**1**10****111**111₂ 14  **1**1**11**
```

---

In assembly:

```
f:  inc eax       # Add 1 to EAX.
    bsr ecx, eax  # Set ECX to the position of the first 1 bit in EAX.
    rcr eax, cl   # Rotate EAX and the carry flag (CF) together right by that many bits.
                  #  (CL is the low byte of ECX; here it always equals the full value.)
                  #  The value of CF after BSR is officially undefined, but it is
                  #  consistently 0 (what this program needs) on at least some CPUs.
                  #  (To not rely on this, add CLC before this for +1 byte.)
                  #  The top 1 bit goes to the bottom, the second bit goes into CF,
                  #  and the rest of the bits go to the top of the value;
                  #  the bits we want to keep are now contiguous for plain rotates.
    jc s          # Jump if CF=1, skipping an instruction. (It is shortest
                  #  to use CF immediately, before another instruction overwrites it.)
    ror eax, 1    # (If CF=0) Rotate EAX right by 1 bit.
s:  rol eax, cl   # Rotate EAX left by CL, moving the value of the inclusive left half
                  #  to the bottom (0 removed) or one bit above the bottom (1 removed).
    mov edx, eax  # Copy the value of EAX into EDX.
    shl eax, cl   # Shift EAX left by CL, moving it to just above the copy in EDX.
    or eax, edx   # Combine EAX and EDX by bitwise OR into EAX.
    shr eax, 1    # Shift EAX right by 1 bit.
    ret           # Return. (EAX is the return value.)

```

# Answer
> 0 votes
# C (gcc), ~~99~~ 79 bytes

```
b[11];n;main(l){for(;++n;)l=sprintf(b,"%b",n)/2,bcmp(b,b+l,l)||printf("%d",n);}

```

Try it online!

---
Tags: code-golf, sequence, binary, base-conversion
---


title: Convert To Shorthand Part 1

text:
# Question
Title: Convert To Shorthand Part 1
This challenge has been divided into parts.
Your goal is to convert a sentence into a form of 'short-hand'

## For Part 1 these are the rules

1. Take in 1 word
2. Remove all vowels(a,e,i,o,u), except the ones at the beginning and the end
3. If a letter is repeated more than once consecutively, reduce it to only one (e.g. `Hello` -\> `Hlo`)
4. Create a function which converts the word into it's corresponding unicode characters based on above given rules, as given in the table

| Letter | Corresponding Unicode Character |
| --- | --- |
| A | Λ |
| B | L |
| C |  |
| D |  |
| E |  |
| F |  |
| G | T |
| H | | |
| I |  |
| J | ) |
| K | \< |
| L | ( |
| M |  |
| N |  |
| O |  |
| P |  |
| Q |  |
| R | \ |
| S |  |
| T | _ |
| U |  |
| V |  |
| W | ⌵ (same as V) |
| X | X |
| Y | ɥ |
| Z |  |

## Test Cases

| English Word | Substituted Word |
| --- | --- |
| A | Λ |
| Quick | ⩁\< |
| Brown | L\⌵ᑎ |
| Fox | ⌽X |
| Jumps | )ᨈ⊥⦵ |
| Over | ┼⌵\ |
| The | \_|∟ |
| Lazy | (ᒣɥ |
| Dog | ꙄT |
| Turtle | \_\\\_(∟ |
| Of | ┼⌽ |
| Terror | \_\ |

As this is code-golf, shortest answer wins!

Part 2 has been posted here

# Answer
> 2 votes
# Burlesque, 86 bytes

```
zzgn"aeiou"XX\\)**97?-"ΛLꙄ∟⌽T|⩗)<(ᨈᑎ┼⊥⩁\⦵_⋃⌵⌵Xɥᒣ"jsi

```

Try it online!

```
zz          # To lower case
gn          # Unique consecutives
"aeiou"XX   # Vowels as list
\\          # List diff
)**         # Map ord
97?-        # Conert to index into alphabet
"ΛLꙄ∟⌽T|⩗)<(ᨈᑎ┼⊥⩁\⦵_⋃⌵⌵Xɥᒣ" # SH as string
jsi         # Select indices from SH string

```

# Answer
> 2 votes
# Python 3.8 (pre-release), 151 bytes

```
lambda s:R(r"(.)\1+",r"\1",R("\B[AEIUO]\B","",s.upper())).translate(4*'ᑎ┼⊥⩁\⦵_⋃⌵⌵XɥᒣΛLꙄ∟⌽T|⩗)<(ᨈ')
import re
R=re.sub

```

Try it online!

-2 thanks to @MarcMush. -1 thanks to @Steffan Test harness borrowed from @solid.py

# Answer
> 2 votes
# Retina 0.8.2, 99 bytes

```
T`L`l
\B[aeiou]\B

(.)\1+
$1
c

T`l`Λ\L_Ꙅ∟⌽T|⩗)<(ᨈᑎ┼⊥⩁\\⦵\_⋃⌵⌵Xɥᒣ

```

Try it online! Link includes test cases. Explanation:

```
T`L`l

```

Change everything to lower case.

```
\B[aeiou]\B

```

Remove all interior vowels.

```
(.)\1+
$1

```

Deduplicate consecutive letters.

```
c

```

Convert `c` separately because `T` can only transliterate characters in the BMP.

```
T`l`Λ\L_Ꙅ∟⌽T|⩗)<(ᨈᑎ┼⊥⩁\\⦵\_⋃⌵⌵Xɥᒣ

```

Transliterate the remaining letters.

# Answer
> 2 votes
# Factor \+ `grouping.extras`, 178 bytes

```
[ >lower 1 cut 1 short cut* swap "aeiou"without glue [ ] group-by values [ members ] map-concat [ 97 mod "ΛLꙄ∟⌽T|⩗)<(ᨈᑎ┼⊥⩁\\⦵_⋃⌵⌵Xɥᒣ"nth ] map ]

```

Try it online!

* `>lower` Convert to lowercase
* `1 cut 1 short cut* swap` Slice the ends off the input (if possible -- that's what `short` is for) and bring the middle to the top of the stack.
* `"aeiou"without glue` Remove vowels and put the ends back on.
* `[ ] group-by values [ members ] map-concat` Consolidate consecutive letters.
* `[ 97 mod "ΛLꙄ∟⌽T|⩗)<(ᨈᑎ┼⊥⩁\\⦵_⋃⌵⌵Xɥᒣ"nth ] map` Map letters to shorthand characters.

# Answer
> 2 votes
# 05AB1E, 76 bytes

```
lā¨Ć≠ÅÏžMм}ÔA•6Eˆ2O:¹VÑX©₃Œl±È“v¬BŒŠ>'µ‰‡S“úÁò›ØIÝZÚþв¬èôÏ&Áθ#›¤mн•Ž‚d·вç‡

```

Should have been 74 bytes without the , but apparently there's a bug in `ÅÏ`.. :/

Try it online or verify all test cases.

**Explanation:**

```
l          # Convert the (implicit) input-string to lowercase
 ā         # Push a list in the range [1,length] (without popping)
  ¨        # Remove the last item to make the range [1,length)
   Ć       # Enclose; append its own head, to have a trailing 1
    ≠      # Check which values are NOT 1
           # (we now have a list of 1s with leading/trailing 0 - e.g. [0,1,1,1,0])
     {À    # No-op bug-fix: sort the list, and rotate it once towards the left
     ÅÏ    # Apply to every truthy (==1) character in the string:
       žM  #  Push vowels-constant "aeoiu"
         м #  Remove those from the current character
      }Ô   # After the apply_on_truthy, connected uniquify the resulting string
A # Push the lowecase alphabet
 •6Eˆ2O:¹VÑX©₃Œl±È“v¬BŒŠ>'µ‰‡S“úÁò›ØIÝZÚþв¬èôÏ&Áθ#›¤mн•
          '# Push compressed integer 3279490039691721988310819230336479163628492048784374634744299180010706872685131111164709021133012715753321092552746940878765
   Ž‚d     # Push compressed integer 33189
      ·    # Double it to 66378
           # (compressing 66378 directly is a byte longer: •15Γ•)
       в   # Convert the large integer to base-66378 as list:
           #  [923,76,66377,42564,8735,9021,84,124,10839,41,60,40,6664,5198,9532,8869,10817,92,10677,95,8899,9013,9013,88,613,5283]
        ç  # Convert each integer to a character with that codepoint
         ‡ # Transliterate the lowercase alphabet to these characters
           # (after which the result is output implicitly)

```

See this 05AB1E tip of mine (sections *How to compress large integers?* and *How to compress integer lists?*) to understand why `•6Eˆ2O:¹VÑX©₃Œl±È“v¬BŒŠ>'µ‰‡S“úÁò›ØIÝZÚþв¬èôÏ&Áθ#›¤mн•` is `3279490039691721988310819230336479163628492048784374634744299180010706872685131111164709021133012715753321092552746940878765`; `Ž‚d` is `33189`; `•15Γ•` is `66378` ; and `•6Eˆ2O:¹VÑX©₃Œl±È“v¬BŒŠ>'µ‰‡S“úÁò›ØIÝZÚþв¬èôÏ&Áθ#›¤mн•Ž‚d·в` is `[923,76,66377,42564,8735,9021,84,124,10839,41,60,40,6664,5198,9532,8869,10817,92,10677,95,8899,9013,9013,88,613,5283]`.

# Answer
> 1 votes
# Python 3, 180 bytes

```
lambda w:''.join('ΛLꙄ∟⌽T|⩗)<(ᨈᑎ┼⊥⩁\⦵_⋃⌵⌵Xɥᒣ'[ord(c)%97]for c in(w[0]+re.sub(r'(.)\1+|[aeiou]','',w[1:-1])+(w[-1],'')[len(w)<2]).lower())
import re

```

Try it online!

# Answer
> 1 votes
# Perl 5, 103 bytes

Pretty standard approach: lowercase the input, remove the inner vowels, remove duplicated chars and transliterate `a-z` to the required chars.

```
$_=lc;s/\B[aeiou]\B//g;s/(.)\1+/$1/g;y;a-z;ΛLꙄ∟⌽T|⩗)<(ᨈᑎ┼⊥⩁\\⦵_⋃⌵⌵Xɥᒣ

```

Try it online!

# Answer
> 1 votes
# Julia 1.0, 138 bytes

```
~=replace
!s=(lowercase(s)~r"\B[aeiou]\B"=>"")~r"(.)\1*"=>x->["ΛLꙄ∟⌽T|⩗)<(ᨈᑎ┼⊥⩁\\⦵_⋃⌵⌵Xɥᒣ"...][x[1]-'`']

```

Try it online!

Just found out that `~` has the same precedence than assignement (with right associativity so the parenthesis are needed), making it the only operator with lower precendence than `=>`

# Answer
> 1 votes
# Vyxal, 80 bytes

```
ɽ:ẏḢṪṪ‡kvF¨MĠvhṅka»⟇†←¬ʁoĊ ∇"₄[ḃ0εẆḭ:₇°ḃτsf≈β→ƈḭ⅛Ṁǒṡ□ø꘍$↲„I₇⊍ǔ¹eṀHbṡ‛1L»»ƛ∨O»τCĿ

```

Try it Online!

Port of 05AB1E answer.

## How?

```
ɽ:ẏḢṪṪ‡kvF¨MĠvhṅka»⟇†←¬ʁoĊ ∇"₄[ḃ0εẆḭ:₇°ḃτsf≈β→ƈḭ⅛Ṁǒṡ□ø꘍$↲„I₇⊍ǔ¹eṀHbṡ‛1L»»ƛ∨O»τCĿ
ɽ                                                                                # Lowercase the (implicit) input
 :                                                                                # Duplicate
  ẏ                                                                               # Get length range [0, length)
   ḢṪṪ                                                                            # Remove the first item and the last two items
      ‡kvF                                                                        # Two element lambda: Remove all vowels from input to lambda
          ¨M                                                                      # Apply z (the lambda) for each element of x (the lowercased input)
                                                                                #   only at the indices in y (the length range without the first and last two items)
            Ġ                                                                     # Group consecutive identical items
             vh                                                                   # Get the first item of each (this is removing consecutive duplicates)
               ṅ                                                                  # Join by nothing
                ka                                                                # Push the lowercase alphabet
                  »⟇†←¬ʁoĊ ∇"₄[ḃ0εẆḭ:₇°ḃτsf≈β→ƈḭ⅛Ṁǒṡ□ø꘍$↲„I₇⊍ǔ¹eṀHbṡ‛1L»          # Push huge compressed integer 3279490039691721988310819230336479163628492048784374634744299180010706872685131111164709021133012715753321092552746940878765
                                                                        »ƛ∨O»     # Push compressed integer 66378
                                                                             τ    # Convert the huge compressed integer to base-66378:
                                                                                #  [923,76,66377,42564,8735,9021,84,124,10839,41,60,40,6664,5198,9532,8869,10817,92,10677,95,8899,9013,9013,88,613,5283]
                                                                              C   # Convert that list of codepoints to their corresponding characters
                                                                               ‡  # Transliterate the string made earlier from the lowercase alphabet to these characters

```

# Answer
> 0 votes
# JavaScript (Node.js), 143 bytes

```
s=>s.replace(/\B[aeiou]\B|(.)(?=\1)|(.)/gi,(a,b,c)=>c?[..."_ΛLꙄ∟⌽T|⩗)<(ᨈᑎ┼⊥⩁\\⦵_⋃⌵⌵Xɥᒣ"][Buffer(c)[0]%32]:'')

```

Try it online!

# Answer
> 0 votes
# Ruby `-pl`, 103 bytes

```
gsub(/\B[aeiou]\B/,"").tr_s!"A-Za-z","ΛLꙄ∟⌽T|⩗)<(ᨈᑎ┼⊥⩁\\\\⦵_⋃⌵⌵Xɥᒣ"*2

```

Try it online!

# Answer
> 0 votes
# Charcoal, 99 bytes

```
≔Φ↧θ¬∧∧κ⁻⊕κＬθ№aeiouιθ⭆Φθ¬∧κ⁼ι§θ⊖κyΛLꙄ∟⌽T|⩗)<(ᨈᑎ┼⊥⩁\⦵_⋃⌵⌵Xɥᒣ⌕βι

```

Try it online! Link is to verbose version of code. Note that the deverbosifier thinks that the embedded string needs to be quoted (at a cost of three bytes) but I disagree. Explanation:

```
≔Φ↧θ¬∧∧κ⁻⊕κＬθ№aeiouιθ⭆Φθ

```

Lowercase the string and remove interior vowels.

```
¬∧κ⁼ι§θ⊖κyΛLꙄ∟⌽T|⩗)<(ᨈᑎ┼⊥⩁\⦵_⋃⌵⌵Xɥᒣ⌕βι

```

Deduplicate consecutive letters and translate from lowercase letters to the desired symbols. Note that the symbols take up 3 or 4 bytes each (I'm relying on the deverbosifier calculation here, as it doesn't actually bother generating the appropriate byte sequences).

# Answer
> 0 votes
# Haskell, 200 bytes

```
import Data.Char
import Data.List
c[h]=[h]
c(h:t)=h:[c|c<-init t,notElem c"AEIOU"]++[last t]
f=map((cycle"ᑎ┼⊥⩁\\⦵_⋃⌵⌵XɥᒣΛLꙄ∟⌽T|⩗)<(ᨈ"!!).ord.head).group.c.map toUpper

```

Attempt This Online!

# Answer
> 0 votes
# Go, 289 bytes

```
import."strings"
func f(s string)(O string){o,S:="",ToUpper(s)
for i:=range S{r,L:=S[i:i+1],len(o)
if L>0&&o[L-1:L]==r{continue}
if!Contains("AEIOU",r)||i<1||i>len(s)-2{o+=r}}
for _,r:=range o{O+=string([]rune(`ΛLꙄ∟⌽T|⩗)<(ᨈᑎ┼⊥⩁\⦵_⋃⌵⌵Xɥᒣ`)[r-'A'])}
return}

```

Attempt This Online!

Golang, once again, doesn't have the luxury of regexp lookaheads, lookbehinds, and backreferences, forcing a "manual" implementation. If you can find a Golang-compatible regexp that solved this challenge, leave a comment.

A regexp-using solution using `\B[AEIOU]\B` is 10 bytes *longer* than this solution.

## Explanation

```
// required import
import."strings"
func f(s string)(O string){
// setup
o,S:="",ToUpper(s)
// for each char...
for i:=range S{
// get the current char
r:=S[i:i+1]
// if it's a duplicate char, ignore
if len(o)>0&&o[len(o)-1:len(o)]==r{continue}
// if it's not a vowel, or it's a vowel not at the start/end of the string, add it in
if !Contains("AEIOU",r)||i<1||i>len(s)-2{o+=r}}
// translate to the unicode chars
for _,r:=range o{O+=string([]rune(`ΛLꙄ∟⌽T|⩗)<(ᨈᑎ┼⊥⩁\⦵_⋃⌵⌵Xɥᒣ`)[r-'A'])}
return}

```

# Answer
> 0 votes
# POSIX Issue ≤7 Shell + Utilities, 111 characters

```
tr a-z A-Z|sed 's/./&\
/;s/.$/\
&/'|tr A-Z 'ΛLꙄ∟⌽T|⩗)<(ᨈᑎ┼⊥⩁\\⦵_⋃⌵⌵Xɥᒣ/'|sed 2s/[Λ∟⩗┼⋃ɥ]//g|tr -d \\n|tr -cs 0

```

Fun fact: since XPG3, tr is defined in terms of *characters*, and is defined *exclusively* for characters all the way until SUSv3, which renames -c to -C and adds byte-wise -c.
This is why in present-day POSIX we observe -c which renders the first set the complement of specified values and -C — characters, as well as stuff like `[=equivalence classes=]` which IIRC is only vaguely supported by the illumos gate? This is a wide-reaching standards blunder. The status of this in Issue 8 and later is unclear.

Not surprisingly, *nothing* supports this. All implementations behave as-if the data were in the POSIX (C) locale, i.e. they operate on bytes.

For something *actual implementations* accept, substitute the third line for

```
&/;y/ABCDEFGHIJKLMNOPQRSTUVWXYZ/ΛLꙄ∟⌽T|⩗)<(ᨈᑎ┼⊥⩁\\⦵_⋃⌵⌵Xɥᒣ/'|sed 2s/[Λ∟⩗┼⋃ɥ]//g|tr -d \\n|tr -cs 0

```

this is what the transcript below uses to emulate the answer, but it's also obviously much longer.

```
$ for w in A Quick Brown Fox Jumps Over The Lazy Dog Turtle Of Terror; do echo $w | ./cg; echo; done
Λ
⩁<
L\⌵ᑎ
⌽X
)ᨈ⊥⦵
┼⌵\
_|∟
(ᒣɥ
ꙄT
_\_(∟
┼⌽
_\

```

---
Tags: code-golf, unicode, substitution
---


# Question
Title: CGAC2022 Day 13: Santa's gift and the laser lock, Part 2
Part of **Code Golf Advent Calendar 2022** event. See the linked meta post for details.

---

You successfully route the laser into the sensor, but nothing happens.

"What?" Frustrated, you flip the note from Santa. There's some more text:

> Calculate the number of ways to complete the laser puzzle, and enter it into the number pad on the back side of the package.

Wow, now it's a hard problem. The time is ticking and it's got so many G's, so a simple brute force (`O(3^G)`) won't cut it.

For the example problem below,

```
          +-+-+-+-+-+-+-+
laser --> |G|G|R|\|G|G|G|
          +-+-+-+-+-+-+-+
          |\|R|/|G|R|G|\| --> sensor
          +-+-+-+-+-+-+-+

```

the answer is 3. The G at the 5th cell on the top row can be anything (`./\`); the others are fixed.

## Task

In this task, the positions of the laser and the sensor are fixed, and the height of the grid is always 2. Given the state of the lock as a 2-by-N grid, output the number of its solutions.

The input grid is given as a 2D string like

```
GGR\GGG
\R/GRG\

```

but the following variations (and combinations thereof) are allowed:

* an array of rows / a matrix / a flattened string or array
* charcodes instead of characters
* transposed grid (in other words, columns instead of rows)
* lowercase instead of uppercase

No other alternative I/O formats are allowed.

**This is a challenge.** The time complexity must be at most polynomial in the length of the grid N.

Standard rules apply. The shortest code in bytes wins.

## Test cases

```
G
G
-> 1

GG
GG
-> 6

G\GGGGGRGGGGG
GGG/G\GG/GGGR
-> 64512

RR
RR
-> 0

R\
\R
-> 0

/GGG
GGGG
-> 0

```

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

```
f=(a,p=1,q=0,h=r=>!!a.match('^'+r))=>a?f(a.slice(2),h`\\w`*3**h`.g`*p+h`[g/]{2}`*q,h`.\\w`*3**h`g`*q+h`[S-g]{2}`*p):q

```

Try it online!

Input transposed, flatten, lowercase grid.

```
f=(
  a,  // the input grid, transposed flatten lowercase
  p=1,q=0, // number of solutions where laser reach the first / second row
  h=r=>!!a.match('^'+r) // test if input "a" matches given regex
                        // or in the other word, test if the first column match given pattern
)=>a? // whenever there are remaining columns
  f(a.slice(2), // recursively call function with first column removed
    h`\\w`*3**h`.g`*p+ // pattern "g?", "r?" (where "?" is whatever) allow laser from row 1 to row 1
    h`[g/]{2}`*q, // pattern "//" allow laser from row 2 to row 1
    h`.\\w`*3**h`g`*q+ // pattern "?g", "?r" allow laser from row 2 to row 2
    h`[S-g]{2}`*p // pattern "\\" allow laser from row 1 to row 2
                  // as /[g\\]/ need to be written as "[g\\\\\\\\]"
                  // we use "[S-g]" to avoid leaning toothpick syndrome
):q

```

For any grid with \\$2\times N\\$ cells, the algorithm took \\$O(N^2)\\$ time to compute the result.
> 7 votes

# Answer
# Python, 97 bytes (@Arnauld)

```
def f(a,t=1,b=0):
 for T,B in a:t,b=B*3%5*t*(T&8<1)+T*B%2*b,T*3%5*b*(B&8<1)+t*(T*B%7<2)
 return b

```

Attempt This Online!

### Python, 127 bytes

```
def f(a,t=1,b=0):
 for T,B in a:t,b=t*(T>"a")*3**(B=='g')+b*({T,B}<={*"/g"}),b*(B>"a")*3**(T=="g")+t*({T,B}<={*"\g"})
 return b

```

Attempt This Online!

Using small letters saves a few bytes.

### Python, 134 bytes

```
def f(a,t=1,b=0):
 for T,B in a:t,b=t*(T in"RG")*3**(B=='G')+b*({T,B}<={*"/G"}),b*(B in"RG")*3**(T=="G")+t*({T,B}<={*"\\G"})
 return b

```

Attempt This Online!

Takes the transpose, i.e. a list of 2-strings.

Note: this is linear in the grid length.

### How?

The key insight here would be that there are no nasty interdependencies. Any partial path that leaves column n in the top row, say, can be combined with any partial path that enters column n+1 in the top row. This allows for many counting methods.

A particularly simple one - used here - is to advance column by column keeping track of the numbers of paths that leave the current column at the top or the bottom.
> 5 votes

# Answer
# JavaScript (ES6), 86 bytes

This is a port of loopy walt's answer with an extra layer of ASCII code trickery.

Expects a transposed matrix of ASCII codes, using upper case.

```
m=>m.map(([T,B])=>[t,b]=[B*3%5*t*!(T&8)+T*B%2*b,T*3%5*b*!(B&8)+t*(T*B%7<2)],t=1,b=0)|b

```

Try it online!

### Expressions

* `X * 3 % 5` evaluates to \\$3\\$ if \\$X=71\\$ (`G`) or \\$1\\$ otherwise
* `!(X & 8)` evaluates to \\$1\\$ (true) if \\$X\in\\{71,82\\}\\$ (`G` or `R`) or \\$0\\$ (false) otherwise
* `T * B % 2` evaluates to \\$1\\$ if \\$T,B\in\\{47,71\\}\\$ (`/` or `G`) or \\$0\\$ otherwise
* `T * B % 7 < 2` evaluates to \\$1\\$ (true) if \\$T,B\in\\{71,92\\}\\$ (`G` or `\`) or \\$0\\$ (false) otherwise
> 4 votes

# Answer
# Charcoal, 52 bytes

```
Ｆ²⊞υ¬ιＦＥθ⁺ι§ηκＵＭυ⁺××κ№α§ιλＸ³⁼§ι¬λG×§υ¬λ⬤ι№⁺§/\λGμＩ⊟υ

```

Try it online! Link is to verbose version of code. Explanation: Port of @loopywalt's Python answer.

```
Ｆ²⊞υ¬ι

```

Start with one possible beam on the top row and none on the bottom row.

```
ＦＥθ⁺ι§ηκ

```

Loop through the columns.

```
ＵＭυ⁺××κ№α§ιλＸ³⁼§ι¬λG×§υ¬λ⬤ι№⁺§/\λGμ

```

Update each row, keeping the count for `R` and `G` with no `G` in the other row or trebling it with `G` in the other row, plus the count of the other row if the column is or can be changed to `//` or `\\` as appropriate.

```
Ｉ⊟υ

```

Output the final count for the bottom row.

(As with my answer to the linked question, six bytes could be saved by taking the input in transposed format.)
> 2 votes

# Answer
# 05AB1E, 54 bytes

```
1¾‚Iv©y`'GQ3smsa*y„/G2ãQà‚*y„\G2ãQày`as'GQ3sm*‚®*R‚O}θ

```

Port of *@tsh*'s JavaScript answer, so make sure to upvote him/her as well!
Unlike his/her answer, *I think* my answer is \\$O(38N)\\$ for a grid of dimensions \\$2\times N\\$.

Input is transposed and as a list of 2-char strings.

Try it online or verify all test cases.

**Explanation:**

```
1¾‚                   # † Push 1 and 0, and pair them together
   Iv                 # Loop `y` over the input-list:
     ©                #  Store the current pair in variable `®` (without popping)
     y                #  Push the current string-pair `y`
      `               #  Pop and push them separated to the stack
       'GQ           '#  Check if the second/top is equal to "G"
          3sm         #  Take 3 to the power this y[1]=="G" check
       s              #  Swap so the first character is at the top
        a             #  Check whether it's a letter ("R" or "G"): isLetter(y[0])
             *        #  Multiply the checks together: (3**(y[1]=="G"))*isLetter(y[0])
     y                #  Push the current pair `y` again
      „/G             #  Push string "/G"
         2ã           #  Cartesian power of 2: ["//","/G","G/","GG"]
           Q          #  Check for each whether it's equal to `y`
            à         #  Check if any is truthy by taking the maximum
              ‚       #  Pair the two together
               *      #  Multiply the values in the two pairs together
     y„\G2ãQà         #  Same as above for ["\\","\G","G\","GG"]
     y`as'GQ3sm*     '#  Same as above for isLetter(y[1])*(3**(y[0]=="G"))
                ‚     #  Pair the two together
                 ®*   #  Multiply the values with pair `®` as well
                   R  #  Then revert it
     ‚                #  Pair these two pairs together
      O               #  Sum each inner pair
    }θ                # After the loop: leave last element of the resulting pair
                      # (which is output implicitly as result)

```

† This could have been `0L` instead for -1 byte, but it would change the complexity to \\$O(38N+2)\\$.

***Why I think it's \\$O(38N)\\$:***

Looping with `Iv` is the \\$N\\$ complexity.

Within its body, the following add to the complexity:

* ``` (2x): pop and dumping both characters to the stack: \\$2\times2=4\\$
* `„/G2ã` and `„\G2ã`: cartesian power of 2 on a 2-char string: \\$2\times2^2=8\\$
* `Q` (2x): equals check on all four values in a quadruplet list: \\$2\times4=8\\$
* `à` (2x): maximum on a quadruplet list: \\$2\times4=8\\$
* `‚*` and `‚®*`: multiply the values in two pairs together: \\$2\times2=4\\$
* `R`: reversing a pair: \\$2\\$
* `‚O`: summing the inner pairs of a pair of pairs: \\$2^2=4\\$

All summed together: \\$4+8+8+8+4+2+4=38\\$
> 1 votes

# Answer
# PARI/GP, 84 bytes

```
a->l=[1,0];[l*=[if(u%15%2,v*3%5),u*v%7<2;u*v%2,if(v%15%2,u*3%5)]|t<-a,[u,v]=t~];l[2]

```

Attempt This Online!

Takes a matrix of ASCII codes.

A port of @Arnauld's JavaScript answer. Uses `X % 15 % 2` instead of `!(X & 8)` because PARI/GP doesn't have a bitand operator.
> 0 votes

---
Tags: code-golf, grid, combinatorics, path-finding, restricted-complexity
---


title: CGAC2022 Day 23: North Pole Railroads

text:
# Question
Title: CGAC2022 Day 23: North Pole Railroads
Part of **Code Golf Advent Calendar 2022** event. See the linked meta post for details.

---

Santa and the Elves are secretly preparing for a new tourist train service, called "North Pole Railroads". The train will travel through various sightseeing spots near the North Pole.

As a part of this project, they want to know how many seats they will need. They already have the list of travels for each passenger (given as "from station X to station Y"), which is thanks to the same magic that lets Santa know which children are nice. Each station is numbered from 1, starting from the North Pole.

The Elves are arguing over how to determine the number of seats. One option is to absolutely minimize the number of seats needed. Elves will decide which passenger will take which seat. Two passengers with strictly overlapping travel cannot share a seat (e.g. one is `(1, 3)` and the other is `(2, 4)`), but a travel that ends at X is not overlapping with another that starts at X.

## Task

Given the list of `X, Y` pairs that represent the travel of each passenger, output how many seats will be needed for North Pole Railroads.

Standard rules apply. The shortest code in bytes wins.

## Test cases

```
(1, 2), (2, 3), (1, 3), (3, 4) -> 2
1---2---3---4
 AAA BBB DDD
 CCCCCCC

(1, 3), (1, 3), (3, 6), (3, 6) -> 2
1...3...6
 AAA CCC
 BBB DDD

(1, 5), (2, 8), (6, 9), (5, 7), (4, 6) -> 3
1...2...3...4...5...6...7...8...9
 AAAAAAAAAAAAAAA DDDDDDD
     BBBBBBBBBBBBBBBBBBBBBBB
             EEEEEEE CCCCCCCCCCC

```

# Answer
# Python 3, 48 bytes

```
lambda a:max(sum(p<x<[q]for*p,q in a)for x in a)

```

Try it online!

---

# Python 3, 50 bytes

```
lambda a:max(sum(p<=x<q for p,q in a)for x,y in a)

```

Try it online!
> 7 votes

# Answer
# , 24 20 bytes

```
[:>./[:+/1=,.I."#./]

```

Attempt This Online!

Found independently, but conceptually very similar to tsh's python approach.

* We find the "insert before" index of every left endpoint within every reversed range
* This will be 1 iff the left endpoint is contained within the range
* We sum all the ones for each left endpoint, giving us a count of how many ranges that endpoint is contained in
* Take the max of all the counts

## , 24 bytes

```
[:>./[:#/.~@;<@i.@-+&.>]

```

Try it online!

* Generates all stops for each person (not including the endpoint), so eg `1 4` becomes `1 2 3`.
* Groups the combined list of all stops by stop, and get a count.
* Returns the max count.
> 5 votes

# Answer
# , 40 bytes

```
\(x,y)max(table(unlist(Map(seq,x,y-1))))

```

Attempt This Online!

Takes input as two vectors - of starts and ends of the travels.
> 5 votes

# Answer
# Vyxal, 5 bytes

```
rfĊ↑t

```

Try it online! Takes a list of start stations and a list of end stations.

```
r     # range (vectorises)
 f    # flatten
  Ċ   # counts of every element
   ↑  # get the maximum element by its tail
    t # tail

```

---

## Vyxal, 7 bytes

```
∩÷rfĊ↑t

```

Try it online! The original solution, taking a list of pairs. This transposes  then item splits `÷` first, before continuing with the solution above.
> 5 votes

# Answer
# Charcoal, ~~19~~ ~~17~~ 15 bytes

```
Ｉ⌈ＥθΣＥθ№…⌊λ⌈λ⌊ι

```

Try it online! Link is to verbose version of code. Edit: Saved 2 bytes by using `Minimum` and `Maximum` to obtain the starting and ending stations for each passenger. Saved a further 2 bytes by only checking the starting stations instead of all stations, which allowed me to rewrite the expression to make it work on TIO as well as ATO. Explanation:

```
   θ            Input journeys
  Ｅ             Map over passengers
      θ         Input journeys
     Ｅ          Map over passengers
       №        Count of
             ⌊  Starting station of
              ι Outer passenger in
        …       Range from
         ⌊      Starting station of
          λ     Inner passenger to
           ⌈    Ending station of
            λ   Inner passenger
    Σ           Take the sum
 ⌈              Take the maximum
Ｉ               Cast to string
                Implicitly print

```
> 4 votes

# Answer
# Factor, 56 bytes

```
[ [ last2 [a,b) ] map concat histogram values supremum ]

```

Try it online!

```
                    ! { { 1 5 } { 2 8 } { 6 9 } { 5 7 } { 4 6 } }
[ last2 [a,b) ] map ! { { 1 2 3 4 } { 2 3 4 5 6 7 } { 6 7 8 } { 5 6 } { 4 5 } }
concat              ! { 1 2 3 4 2 3 4 5 6 7 6 7 8 5 6 4 5 }
histogram           ! H{ { 1 1 } { 2 2 } { 3 2 } { 4 3 } { 5 3 } { 6 3 } { 7 2 } { 8 1 } }
values              ! { 1 2 2 3 3 3 2 1 }
supremum            ! 3

```
> 4 votes

# Answer
# Pip, 20 bytes

```
M:($+:{@_Na,b}MUa)Ma

```

Try It Online!
> 4 votes

# Answer
# Jelly, 7 bytes

```
‘r"FĠẈṀ

```

Try it online!

*-2 bytes: Takes start stations and end stations as separate lists.*

```
‘r"FĠẈṀ
‘        - increment
 r"      - vectorized range
   F     - flatten
    Ġ    - group indices by value
     Ẉ   - lengths
      Ṁ  - maximum

```
> 4 votes

# Answer
# JavaScript (ES6), 61 bytes

*-3 thanks to @l4m2*

```
a=>a.map(g=([p,q])=>p<q&&g([p+1,q],m+=m<(g[p]=-~g[p])),m=0)|m

```

Try it online!
> 3 votes

# Answer
# Python3, 237 bytes:

```
lambda x:min(f(x))
def f(x):
 q=[(x,[])]
 while q:
  a,b=q.pop(0)
  if[]==a:yield len(b);continue
  for I,i in enumerate(b):
   if all(y<=a[0][0]or a[0][1]<=x for x,y in i):q+=[(a[1:],b[:I]+[[*i,a[0]]]+b[I+1:])]
  q+=[(a[1:],b+[[a[0]]])]

```

Try it online!
> 2 votes

# Answer
# Nibbles, 9 bytes (18 nibbles)

```
`/.=~+!$_~>$,@$,$]

```

Takes input as lists of start stations and end stations.

```
`/.=~+!$_~>$,@$,$]
      !$_           # zip input lists together
         ~          # using function:
          >$        #   drop inp1 elements
            ,@      #   from range 1..inp2
     +              # now flatten the list of lists
   =~               # and group elements
              $     # by their own values;
  .            ,$   # get the length of each group
`/                  # and fold over this list
                 ]  #   returning the maximum

```
> 2 votes

# Answer
# Jelly, 7 bytes

```
r/ṖṬ)SṀ

```

A monadic Link that accepts a list of pairs of station numbers for the passengers and yields the minimum seat count.

**Try it online!**

### How?

```
r/ṖṬ)SṀ - Link: list of pairs of positive integers, P
    )   - for each (board, alight) in P:
 /      -   reduce by:
r       -     inclusive range -> [board, board+1, ..., alight]
  Ṗ     -   pop (the passenger does not need their seat at their destination)
   Ṭ    -   untruth - e.g. [3,4,5] -> [0,0,1,1,1]
     S  - sum (the columns of that)
      Ṁ - maximum

```
> 2 votes

# Answer
# Excel (ms365), 111 bytes

Formula in `D1`:

```
=MAX(BYROW(A1:B5,LAMBDA(a,LET(x,SEQUENCE(MAX(a)-MIN(a),,MIN(a)+1),MAX(COUNTIFS(A1:A5,"<="&x,B1:B5,">"&x),1)))))

```
> 1 votes

# Answer
# C (gcc), ~~137~~ ~~134~~ ~~133~~ 132 bytes

*-2 byte thanks to @ceilingcat*

```
m;n;k;i;q;l;main(c,v)int**v;{for(;++n-l;k=0)for(i=1;i++<c;m=fmax(k+=atoi(v[i++-1])<=n&n<q,m))l=fmax(q=atoi(v[i]),l);printf("%d",m);}

```

Try it online!
> 1 votes

# Answer
# Haskell, 86 bytes

```
import Data.Ix
import Data.List
s=maximum.map length.group.sort.concat.map(init.range)

```

Try it online!
> 1 votes

# Answer
# x86-64 machine code, 33 bytes

```
92 99 31 C9 57 56 AF 75 02 FF C9 AF 75 02 FF C1 FF CE 75 F2 5E 5F 39 D1 0F 47 D1 FF C8 75 E5 92 C3

```

Try it online!

Following the standard calling convention for Unix-like systems (from the System V AMD64 ABI), this takes an array of pairs of 32-bit integers with the address in RDI and the length in ESI, and takes the number of stations in EDI.

This program runs backwards through the stations, keeping track of the number of passengers on the train, and the answer is the highest that number has been.

In assembly:

```
f:
    xchg edx, eax   # Switch the number of stations into EAX.
    cdq             # Set EDX to 0 by sign-extending EAX.
    xor ecx, ecx    # Set ECX to 0.
            # EAX will hold the current station, ECX the current number of passengers,
            #  and EDX the highest number of passengers so far.
next_station:
    push rdi        # Save the value of RDI onto the stack.
    push rsi        # Save the value of RSI onto the stack.
next_passenger:
    scasd           # Compare EAX and the value at address RDI, advancing the pointer.
    jne s0          # (That value is the starting station.) Jump if they are unequal.
    dec ecx         # (If they are equal) Subtract 1 from the current passenger count.
s0:
    scasd           # Compare EAX and the value at address RDI, advancing the pointer.
    jne s1          # (That value is the ending station.) Jump if they are unequal.
    inc ecx         # (If they are equal) Add 1 to the current passenger count.
s1:
    dec esi         # Subtract 1 from ESI, counting down from the number of passengers.
    jnz next_passenger  # Jump back, to repeat, if it's not zero.
    pop rsi         # Restore the value of RSI from the stack.
    pop rdi         # Restore the value of RDI from the stack.
    cmp ecx, edx    # Compare the current passenger count and EDX.
    cmova edx, ecx  # If the current passenger count is higher, set EDX to that.
    dec eax         # Subtract 1 from EAX, progressing backwards through the stations.
    jnz next_station# Jump back, to repeat, if it's not zero.
    xchg edx, eax   # Switch the highest passenger count into EAX (to be returned).
    ret             # Return.

```
> 1 votes

# Answer
# 05AB1E, 8 bytes

```
εŸ¨}˜D¢à

```

Try it online or verify all test cases.

**Explanation:**

```
ε      # Map over each pair of the (implicit) input-list:
 Ÿ     #  Pop the pair, and push a list in the inclusive range of it
  ¨    #  Remove the last item (the destination-seat)
}˜     # After the map: flatten the list of lists
  D    # Duplicate it
   ¢   # Pop both, and count how many times each occurs
    à  # Pop and leave the maximum count
       # (which is output implicitly as result)

```
> 0 votes

---
Tags: code-golf
---


title: Compute the Mertens function

text:
# Question
Title: Compute the Mertens function
Given a positive integer *n*, compute the value of the Mertens function \\$M(n)\\$ where:

$$M(n) = \Sigma\_{k=1}^{n}\mu(k)$$

and \\$\mu(k)\\$ is the Möbius function where \\$μ(k) = 1\\$ if \\$k\\$ has an even number of distinct prime factors, \\$-1\\$ if \\$k\\$ has an odd number of distinct prime factors, and \\$0\\$ if the prime factors are not distinct.

* This is so create the shortest code for a function or program that computes the Mertens function for an input integer *n* \> 0.
* This is the OEIS sequence A002321.

## Test Cases

```
n M(n)
1 1
2 0
3 -1
4 -1
5 -2
6 -1
7 -2
8 -2
9 -2
10 -1
117 -5
5525 5
7044 -25
8888 4
10000 -23

```

# Answer
> 6 votes
# Jelly, 6 bytes

```
:Ḋß€SC

```

Try it online! or verify the smaller test cases. (takes a while)

### Background

This uses the property

from A002321, which leads to the following recursive formula.

### How it works

```
:Ḋß€SC  Main link. Argument: n

 Ḋ      Dequeue; yield [2, ..., n].
:       Perform the integer division of n by each k in [2, ..., n].
  ß€    Recursively call the main link on each result.
    S   Sum; add the results from the recursive calls.
     C  Complement; map the sum r to 1 - r.

```

# Answer
> 11 votes
# Mathematica, ~~22~~ 20 bytes

Thanks to @miles for saving 2 bytes.

```
Tr@*MoebiusMu@*Range

```

# Explanation

```
Range

```

Generate a list from 1 to input.

```
MoebiusMu

```

Find `MoebiusMu` of each number

```
Tr

```

Sum the result.

# Answer
> 11 votes
# Python 2, ~~45~~ 37 bytes

```
f=lambda n,k=2:n<k or f(n,k+1)-f(n/k)

```

Test it on Ideone.

### Background

This uses the property

from A002321, which leads to the following recursive formula.

### How it works

We use recursion not only to compute **M** for the quotients, but to compute the sum of those images as well. This saves 8 bytes over the following, straightforward implementation.

```
M=lambda n:1-sum(M(n/k)for k in range(2,n+1))

```

When **f** is called with a single argument **n**, the optional argument **k** defaults to **2**.

If **n = 1**, `n<k` yields *True* and **f** returns this value. This is our base case.

If **n \> 1**, `n<k` initially returns *False* and the code following `or` is executed. `f(n/k)` recursively computes one term of the sum, which is subtracted from the return value of `f(n,k+1)`. The latter increments **k** and recursively calls **f**, thus iterating over the possible values of **k**. Once **n \< k + 1** or **n = 1**, `f(n,k+1)` will return **1**, ending the recursion.

# Answer
> 7 votes
# 05AB1E, ~~16~~ 15 bytes

```
LÒvX(ygmyyÙïQ*O

```

**Explanation**

```
L        # range [1 .. n]
Ò        # list of prime factors for each in list
v        # for each prime factor list
 X(ygm   # (-1)^len(factors)
 yyÙïQ*  # multiplied by factors == (unique factors)
 O       # sum

```

Try it online!

# Answer
> 7 votes
# Brachylog, ~~22~~ 20 bytes

```
yb:1a+
$p#dl:_1r^|,0

```

Try it online!

### Explanation

```
yb                 The list [1, 2, …, Input]
  :1a              Apply predicate 1 (second line) to each element
     +             Sum the resulting list

    $p#d               All elements of the list of prime factors of the Input are distinct
        l:_1r^         Output = (-1)^(<length of the list of prime factors>)
|                  Or
    ,0                 Output = 0

```

# Answer
> 5 votes
# Jelly, 9 bytes

```
RÆFỊNP€FS

```

Try it online! or verify all test cases.

### How it works

```
RÆFỊNP€FS  Main link. Argument: n

R          Range; yield [1, ..., n].
 ÆF        Factor; decompose each integer in that range into prime-exponent pairs.
   Ị       Insignificant; yield 1 for argument 1, 0 for all others.
    N      Negative; map n to -n.
           This maps primes to 0, exponent 1 to -1, and all other exponents to 0.
     P€    Reduce the columns of the resulting 2D arrays by multiplication.
           The product of the prime values will always be 0; the product of the
           exponent values is 0 if any exponent is greater than, 1 if there is an
           even number of them, -1 is there is an odd number of them.
       FS  Flatten and sum, computing the sum of µ(k) for k in [1, ..., n].

```

# Answer
> 5 votes
# Haskell, ~~29~~ 27 bytes

```
f n=1-sum(f.div n<$>[2..n])

```

# Answer
> 3 votes
# Jelly, 7 bytes

```
Ị*%ðþÆḊ

```

Not very efficient; determinants are hard.

Try it online! or verify the smaller test cases. (takes a while)

### Background

This uses a formula from A002321:

**M(n)** is the determinant of the Boolean matrix **An×n**, where **ai,j** is **1** if **j = 1** or **i | j**, and **0** otherwise.

### How it works

```
Ị*%ðþÆḊ  Main link. Argument: n

   ð     Combine the preceding atoms into a chain (unknown arity).
         Begin a new, dyadic chain with arguments a and b.
Ị        Insignificant; return 1 iff a = 1.
  %      Compute a % b.
 *       Compute (a == 1) ** (a % b).
         This yields 1 if a = 1, or if a ≠ 1 and a % b = 0; otherwise, it yields 0.
    þ    Table; construct the matrix A by calling the defined chain for every pair
         of integers in [1, ..., n].
     ÆḊ  Compute the determinant of the resulting matrix.

```

# Answer
> 3 votes
# PHP, 113 bytes

```
for(;$i=$argv[1]--;){for($n=$j=1;$j++<$i;)if(!($i%$j)){$i/=$j;$n++;if(!($i%$j))continue 2;}$a+=$n%2?1:-1;}echo$a;

```

As far as I know php lacks anything like prime number functionality so this is kind of a pain. It's probably possible to do better.

use like:

```
 php -r "for(;$i=$argv[1]--;){for($n=$j=1;$j++<$i;)if(!($i%$j)){$i/=$j;$n++;if(!($i%$j))continue 2;}$a+=$n%2?1:-1;}echo$a;" 10000

```

# Answer
> 2 votes
## Racket 103 bytes

```
(λ(N)(for/sum((n(range 1 N)))(define c(length(factorize n)))(cond[(= 0 c)0][(even? c)1][(odd? c)-1])))

```

Ungolfed:

```
(define f
  (λ(N)
    (for/sum ((n (range 1 N)))
      (define c (length (factorize n)))
      (cond
        [(= 0 c) 0]
        [(even? c) 1]
        [(odd? c) -1]))))

```

# Answer
> 2 votes
## CJam (20 bytes)

```
qiM{_,:)(@@f/{j-}/}j

```

Online demo

Uses the formula from OEIS

> `sum(k = 1..n, a([n/k])) = 1`. - David W. Wilson, Feb 27 2012

and CJam's memoising operator `j`.

### Dissection

```
qi       e# Read stdin as an integer
M{       e# Memoise with no base cases
         e#   Memoised function: stack contains n
  _,:)(  e#   Basic manipulations to give n [2 .. n] 1
  @@f/   e#   More basic manipulations to give 1 [n/2 ... n/n]
  {j-}/  e#   For each element of the array, make a memoised recursive call and subtract
}j

```

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

```
n=>[1,...Array(n-1)].reduce((r,_,i)=>r-f(n/++i|0))

```

Port of @Dennis's Python answer.

# Answer
> 2 votes
# Julia, ~~26~~ 25 bytes

```
!n=1-sum(map(!,n÷(2:n)))

```

Try it online!

### Background

This uses the property

from A002321, which leads to the following recursive formula.

### How it works

We redefine the unary operator **!** for our purposes.

`n÷(2:n)` computes all required quotients, our redefined **!** is mapped over them, and finally the sum of all recursive calls is subtracted from **1**.

Unfortunately,

```
!n=1-sum(!,n÷(2:n))

```

does not work since dyadic *sum* will choke on an empty collection.

```
!n=n<2||1-sum(!,n÷(2:n))

```

fixes this, but it doesn't save any bytes and returns *True* for input **1**.

# Answer
> 2 votes
# C, ~~51 50~~ 47 bytes

```
f(n,t,u){for(t=u=1;n/++u;t-=f(n/u));return t;}

```

Edit: Thanks to @Dennis for -3 bytes!

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

```
n->sum(x=1,n,moebius(x))

```

# Answer
> 1 votes
# Scala, 53 bytes

```
def?(n:Int,k:Int=2):Int=if(n<k)1 else?(n,k+1)- ?(n/k)

```

A port of Dennis's pythin answer.

I've called the method `?`, which is a token that doesn't stick to letters.

# Answer
> 1 votes
# Pyth, 12 bytes

Defines a function `y` that takes in the `n`.

```
L-1syM/LbtSb

```

Test suite here. (Note that the trailing `y` here is to actually call the declared function.)

# Answer
> 1 votes
# Actually, ~~18~~ ~~17~~ 16 bytes

Golfing suggestions welcome. Try it online!

```
R`;y;l0~ⁿ)π=*`MΣ

```

**Ungolfing**

```
         Implicit input n.
R        Push the range [1..n].
`...`M   Map the following function over the range. Variable k.
  ;        Duplicate k.
  y        Push the distinct prime factors of k. Call it dpf.
  ;        Duplicate dpf.
  l        Push len(dpf).
  0~       Push -1.
  ⁿ        Push (-1)**len(dpf).
  )        Move (-1)**len(dpf) to BOS. Stack: dpf, k, (-1)**len(dpf)
  π        Push product(dpf).
  =        Check if this product is equal to k.
            If so, then k is squarefree.
  *        Multiply (k is squarefree) * (-1)**(length).
            If k is NOT squarefree, then 0.
            Else if length is odd, then -1.
            Else if length is even, then 1.
           This function is equivalent to the Möbius function.
Σ        Sum the results of the map.
         Implicit return.

```

# Answer
> 1 votes
# J, 19 bytes

```
1#.1*/@:-@~:@q:@+i.

```

Computes the Mertens function on `n` using the sum of the Möbius function over the range `[1, n]`.

## Usage

```
   f =: 1#.1*/@:-@~:@q:@+i.
   (,.f"0) 1 2 3 4 5 6 7 8 9 10 117 5525 7044 8888 10000
    1   1
    2   0
    3  _1
    4  _1
    5  _2
    6  _1
    7  _2
    8  _2
    9  _2
   10  _1
  117  _5
 5525   5
 7044 _25
 8888   4
10000 _23

```

## Explanation

```
1#.1*/@:-@~:@q:@+i.  Input: integer n
                 i.  Range [0, 1, ..., n-1]
   1            +    Add 1 to each
             q:@     Get the prime factors of each
          ~:@        Sieve mask of each, 1s at the first occurrence
                     of a value and 0 elsewhere
        -@           Negate
    */@:             Reduce each using multiplication to get the product
1#.                  Convert that to decimal from a list of base-1 digits
                     Equivalent to getting the sum

```

# Answer
> 0 votes
# Factor \+ `math.extras math.unicode`, 27 bytes

```
[ [1,b] [ mobius ] map Σ ]

```

Attempt This Online!

---
Tags: code-golf, math, sequence, number-theory, primes
---


title: 8086 Segment Address to Linear

text:
# Question
Title: 8086 Segment Address to Linear
Given an 8086 segmented ("*logical*") memory address, output its actual linear physical address.

A segmented memory address has format `xxxx:xxxx`, where each of `x` is one of `0-9A-F`, and the two parts are parsed as hexadecimal integers. Both parts are exactly 4 digits.

To get its actual linear address, multiply the first part by sixteen and add the second part. You can return it in a reasonable format, e.g. integer or a length=5 string. You can choose whether to modulo the result by \\$2^{20}\\$ (like 8086, or 286+ with the A20 gate closed). Yet input format is fixed.

This is , shortest code in each language wins.

Test cases

```
0000:0000 -> 0x00000
1111:1111 -> 0x12221
FFFF:0000 -> 0xFFFF0
FFFF:0010 -> 0x00000 or 0x100000

```

# Answer
# JavaScript (ES6), 33 bytes

*-2 thanks to @l4m2*

Returns an integer.

```
s=>eval(s.replace(/:|^/g,'0+0x'))

```

Try it online!

Turns an input such as `"ABCD:1234"` into `"0+0xABCD0+0x1234"` and evaluates it as JS code.
> 7 votes

# Answer
# Bash, 35 bytes

```
IFS=:;read a b;echo $[16*0x$a+0x$b]

```

Takes input from stdin and outputs to stdout

Attempt This Online!
> 5 votes

# Answer
# C (GCC), 52 bytes

```
main(a,b){scanf("%X:%X",&a,&b);printf("%X",16*a+b);}

```

Attempt This Online!
> 4 votes

# Answer
# MS-DOS .COM (386 instructions), 71 bytes

Takes input from the command line and prints the result. To convert each output character, I use a variant of `AAM` that operates in base 16.

```
BE 82 00 E8 2A 00 8B DF 66 C1 E3 04 46 E8 20 00
66 03 DF 66 C1 CB 10 B9 05 00 8A C3 D4 10 3C 0A
7C 02 04 07 04 30 CD 29 66 C1 C3 04 E2 EC CD 20
66 33 FF B9 04 00 C1 E7 04 AC A8 40 74 02 2C 07
2C 30 03 F8 E2 F0 C3

```

TASM source:

```
IDEAL
P386

MODEL   TINY
CODESEG
ORG 100H

MAIN:
    MOV     SI,82H ; Start of command line
    CALL    DECODE
    MOV     BX,DI
    SHL     EBX,4 ; Adjust segment portion
    INC     SI
    CALL    DECODE
    ADD     EBX,EDI ; Add offset
    ROR     EBX,16 ; Rotate address to point to first digit
    MOV     CX,5
LOOPM:
    MOV     AL,BL
    DB      0D4H, 10H ; AAM 10H (base 16: AH=AL/16, AL=AL mod 16)
    CMP     AL,0AH
    JL      ASCADJ
    ADD     AL,7 ; Convert digits > 9 into A-F
ASCADJ:
    ADD     AL,48
    INT     29H
    ROL     EBX,4 ; Next digit
    LOOP    LOOPM
    INT     20H

DECODE:
    XOR     EDI,EDI ; Return register
    MOV     CX,4
LOOP1:
    SHL     DI,4
    LODSB
    TEST    AL,40H
    JZ      DECADJ
    SUB     AL,7 ; Convert digits A-F to 10-16
DECADJ:
    SUB     AL,48
    ADD     DI,AX
    LOOP    LOOP1
    RET

END MAIN
ENDS

```

Example results:

```
C:\WORK>segment FFFF:0000
FFFF0

```
> 4 votes

# Answer
# x86 .COM, ~~64~~ 59 bytes

```
0100  BE 82 00 66 31 C9 66 F7-E1 B1 08 66 C1 CA 10 66   ...f1.f....f...f
0110  C1 C2 04 AC 3C 3A 74 F3-2C 30 D4 10 D5 09 66 01   ....<:t.,0....f.
0120  C2 E2 EC 66 92 66 99 B1-0A 66 F7 F1 66 85 C0 52   ...f.f...f..f..R
0130  74 03 E8 F0 FF 58 04 30-CD 29 C3                  t....X.0.).

```

Thank Peter Cordes for -5 bytes

```
    org $100
    mov si, $82
    xor ecx, ecx
    mul ecx
    mov cl, 8
b:  ror edx, 16
a:  rol edx, 4
    lodsb
    cmp al, ':'
    je b
    sub al, '0'
    aam $10
    aad 9
    add edx, eax
    loop a
    xchg eax, edx
p:  cdq
    mov cl, 10
    div ecx
    test eax, eax
    push dx
    jz q
    call p
q:  pop ax
    add al, '0'
    int $29
    ret

```

Output decimal
> 4 votes

# Answer
# Excel (ms365), 37 bytes

Formula in `B1`:

```
=SUM(HEX2DEC(MID(A1,{1,6},4))*{16,1})

```
> 4 votes

# Answer
# Vyxal, 7 bytes

```
\:/H16β

```

Try it Online!

```
\:/H16β
\:/     # Split on colon
   H    # Convert each from hex string to int
    16β # Convert list from base 16 to decimal

```
> 3 votes

# Answer
# Python, 39 bytes

```
lambda x:int(x[:4],16)*16+int(x[5:],16)

```

Attempt This Online!
> 2 votes

# Answer
# Raku, 31 bytes

```
*+<4+*o{m:g/\w+/».&{:16(~$_)}}

```

Try it online!

This is two anonymous functions composed together with the `o` operator. The first, `* +< 4 + *` returns its first argument shifted left four bits (ie, multiplied by 16) plus its second argument. The second, enclosed by braces, extracts the two hexadecimal substrings (`m:g/\w+/`) and parses them into integers (`:16(~$_)`).
> 2 votes

# Answer
# Japt `-x`, 13 bytes

```
q': ÔËnG *GpE

```

Try it

Output is an integer. This version includes a footer which translates to the format in the test cases (No modulus, so it outputs `0x100000` for the last test case).

Explanation:

```
q': ÔËnG *GpE
q':           # Split input where the character ':' appears
    Ô         # Reverse the array
     Ë        # Map:
      nG      #  Treat the string as a base-16 number
         *    #  Multiply with
          GpE #  16 to the power of the current index

-x            # Output the sum of the resulting array

```
> 2 votes

# Answer
# Factor, 35 bytes

```
[ ":"split1 hex> swap hex> 16 * + ]

```

Try it online!

```
       ! "1111:1111"
":"    ! "1111:1111" ":"
split1 ! "1111" "1111"
hex>   ! "1111" 4369
swap   ! 4369 "1111"
hex>   ! 4369 4369
16     ! 4369 4369 16
*      ! 4369 69904
+      ! 74273

```
> 2 votes

# Answer
# Python, 53 bytes

```
lambda x:int((s:=x.split(':'))[0],16)*16+int(s[1],16)

```

Attempt This Online!

Returns an integer (ok as per OP). Footer on ATO converts to hexadecimal.
> 1 votes

# Answer
# Jelly,  ~~13~~  11 bytes

Jelly has no built-in standard hex string conversion functions :/

```
ØHiⱮ’ṣ-ḅ⁴ḅ⁴

```

A monadic Link that accepts a list of characters (as defined) and yields an integer.

**Try it online!**

### How?

```
ØHiⱮ’ṣ-ḅ⁴ḅ⁴ - Link: list of characters, S
ØH         - hex-characters -> "0123456789ABCDEF"
   Ɱ       - map across c in S with:
  i        -   first 1-indexed index of c in the hex-characters or 0
    ’      - decrement (vectorises)
      -    - literal -1
     ṣ     - split the ØHiⱮ’ result at -1's (this is what ':' will have mapped to)
       ḅ⁴   - convert from base sixteen (vectorises)
         ḅ⁴ - convert from base sixteen

```
> 1 votes

# Answer
# Perl `-aF:`, 29 + 4 = 33 bytes

```
print 16*hex($F[0])+hex $F[1]

```

Attempt This Online!
> 1 votes

# Answer
# Charcoal, 14 bytes

```
⍘↨Ｅ⪪Ｓ:⍘ι⊗⁸⊗⁸⊗⁸

```

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

```
    Ｓ           Input string
   ⪪            Split on
     :          Literal string `:`
  Ｅ             Map over parts
       ι        Current part
      ⍘         Convert from base
         ⁸      Literal integer `8`
        ⊗       Doubled
 ↨              Convert from base
           ⁸    Literal integer `8`
          ⊗     Doubled
⍘               Convert to base
             ⁸  Literal integer `8`
            ⊗   Doubled
                Implicitly print

```

Consecutive integers would require a separator so I double `8` instead of using a literal `16`. (The first one doesn't need to be double `8` but I wanted to be consistent.)
> 1 votes

# Answer
# Retina 0.8.2, 87 bytes

```
:
0¶0
O#$`.
$.%`
¶

M!`..
[a-f]
55$&
T`l`d
.
$*
+`¶1{16}
1¶
1{16}

%M`1
T`d`l`..
b\B|¶

```

Try it online! Link includes test cases. Explanation:

```
:
0¶0

```

Replace the separator with a newline, but also suffixing a `0` to the first number and prefixing a `0` to the second number, reducing the problem to hexadecimal addition.

```
O#$`.
$.%`
¶

M!`..

```

Transpose the digits.

```
[a-f]
55$&
T`l`d
.
$*

```

Convert each digit to unary. As they are now transposed, each line now corresponds to the sum of the two digits in unary.

```
+`¶1{16}
1¶
1{16}

```

Propagate carries, but drop the 20th carry (allowed per spec).

```
%M`1

```

Convert each resulting "digit" to decimal.

```
T`d`l`..
b\B|¶

```

Convert each decimal number to a hexadecimal digit and join everything together.
> 1 votes

# Answer
# Pip, 23 bytes

```
Uo{aFB16*16E Do}MSa^":"

```

Try It Online!

I couldn't quite figure out a nice way to multiply the first part by 16, I'm sure @DLosc will be able to save the day
> 1 votes

# Answer
# C (gcc), 40 bytes

```
i;f(s){sscanf(s,"%x:%x",&i,&s);s+=i<<4;}

```

Try it online!
> 1 votes

# Answer
# , ~~44~~ 36 bytes

```
strtoi(scan(,"",,,":"),16)%*%c(16,1)

```

Attempt This Online!
> 1 votes

# Answer
# Nibbles, 7 bytes (14 nibbles)

```
`@4.`=$\$Nhex

```

Outputs decimal address value.

```
`@4.`=$\$Nhex
    `=$         # chunk the input by
       \$       # its character class:
         N      #   is it alphanumeric?
   .            # now map over the 3 chunks
                # (the middle one is ":")
          hex   #   get hex value
                #   (value of ":" is zero)
`@4             # and convert the 3-element list
                # to base-4

```

---

For the same bytes, we could also explicitly split `%` the input on the string `":"`, and convert from base-16, similarly to some other answers:
``@16.%$":"hex`
> 1 votes

# Answer
# Go, ~~83~~ 80 bytes

```
import."fmt"
func f(s string)int{l,r:=0,0
Sscanf(s,"%x:%x",&l,&r)
return l*16+r}

```

Attempt This Online!

Very similar to the other answers with some sort of `Scanf`: Look for 2 hex numbers, put them into variables, and return the result.

* -3 bytes from @Steffan: `var l,r int => l,r:=0,0`
> 1 votes

# Answer
# 05AB1E, 7 bytes

```
':¡H16β

```

Outputs as an integer.

Try it online or verify all test cases.

**Explanation:**

```
':¡     '# Split the (implicit) input-string on ":"
   H     # Convert both strings in the pair from hexadecimal to base-10 integers
    16β  # Convert this list to a base-16 integer
         # (which is output implicitly as result)

```
> 1 votes

# Answer
# Arturo, 44 bytes

```
$[s][+*16from.hex take s 4from.hex drop s 5]

```

Try it
> 0 votes

# Answer
# Python 3, 42 bytes

Python translation of @Arnauld's JavaScript solution

```
lambda a:eval('0x'+a.replace(':','0+0x'))

```

Try it online!
> 0 votes

---
Tags: code-golf, x86-family
---


title: Shortest disk image that boots UEFI

text:
# Question
Title: Shortest disk image that boots UEFI
Presumably everybody here knows that for the legacy BIOS, the tiniest bootable disk image is 512 bytes (the lower bound is due to the 2-byte magic at offset 510), and there is a bootsector demoscene where people try to fit the entire demo into the 510 bytes of usable space.

Now that the BIOS is being superseded by UEFI, there is a question: what will be the equivalent of a "bootsector demo" in the UEFI world?

More formally, here is what I'm curious about: what's the minimum size of a whole-drive image that boots on at least one UEFI?

Rules:

1. The answer must be a disk image, or must compile to a disk image.
2. The disk image should boot on at least one UEFI with CSM/Legacy boot **disabled**.
3. By "booting" I consider that the CPU starts executing instructions that have been loaded from the disk image. It does not matter what the image actually does.
4. Exploiting bugs in specific UEFI implementations is OK, unless the bug causes the firmware to attempt a legacy boot.
5. The winner is the image that is the smallest when encoded in the raw format. If there are multiple answers with the same image size, the one where the most space can be used for x86 code wins.

# Answer
> 11 votes
# <sup>~~1886~~</sup> 1799 bytes (~3.51 sectors), OVMF

*-87 bytes by removing . and .. from cluster 2 and reorganizing the sector.*

Started off with @набиячлэвэлиь's answer and golfed it down to the point where it's now a single NASM file building the image from scratch. Outputs "Done" and enters an infinite loop.

Hexdump:

```
00000000: 0000 0000 0000 0000 0000 0000 0201 0100  ................
00000010: 0110 0004 0000 0100 0000 0000 0000 0000  ................
00000020: 0000 0000 0000 0000 0000 0000 0000 0000  ................
00000030: 0000 0000 0000 0000 0000 0000 0000 0000  ................
00000040: 0000 0000 0000 0000 0000 0000 0000 0000  ................
00000050: 0000 0000 0000 0000 0000 0000 0000 0000  ................
00000060: 0000 0000 0000 0000 0000 0000 0000 0000  ................
00000070: 0000 0000 0000 0000 0000 0000 0000 0000  ................
00000080: 0000 0000 0000 0000 0000 0000 0000 0000  ................
00000090: 0000 0000 0000 0000 0000 0000 0000 0000  ................
000000a0: 0000 0000 0000 0000 0000 0000 0000 0000  ................
000000b0: 0000 0000 0000 0000 0000 0000 0000 0000  ................
000000c0: 0000 0000 0000 0000 0000 0000 0000 0000  ................
000000d0: 0000 0000 0000 0000 0000 0000 0000 0000  ................
000000e0: 0000 0000 0000 0000 0000 0000 0000 0000  ................
000000f0: 0000 0000 0000 0000 0000 0000 0000 0000  ................
00000100: 0000 0000 0000 0000 0000 0000 0000 0000  ................
00000110: 0000 0000 0000 0000 0000 0000 0000 0000  ................
00000120: 0000 0000 0000 0000 0000 0000 0000 0000  ................
00000130: 0000 0000 0000 0000 0000 0000 0000 0000  ................
00000140: 0000 0000 0000 0000 0000 0000 0000 0000  ................
00000150: 0000 0000 0000 0000 0000 0000 0000 0000  ................
00000160: 0000 0000 0000 0000 0000 0000 0000 0000  ................
00000170: 0000 0000 0000 0000 0000 0000 0000 0000  ................
00000180: 0000 0000 0000 0000 0000 0000 0000 0000  ................
00000190: 0000 0000 0000 0000 0000 0000 0000 0000  ................
000001a0: 0000 0000 0000 0000 0000 0000 0000 0000  ................
000001b0: 0000 0000 0000 0000 0000 0000 0000 0000  ................
000001c0: 0000 0000 0000 0000 0000 0000 0000 0000  ................
000001d0: 0000 0000 0000 0000 0000 0000 0000 0000  ................
000001e0: 0000 0000 0000 0000 0000 0000 0000 0000  ................
000001f0: 0000 0000 0000 0000 0000 0000 0000 0000  ................
00000200: 0000 00ff 0f00 0000 0000 0000 0000 0000  ................
00000210: 0000 0000 0000 0000 0000 0000 0000 0000  ................
00000220: 0000 0000 0000 0000 0000 0000 0000 0000  ................
00000230: 0000 0000 0000 0000 0000 0000 0000 0000  ................
00000240: 0000 0000 0000 0000 0000 0000 0000 0000  ................
00000250: 0000 0000 0000 0000 0000 0000 0000 0000  ................
00000260: 0000 0000 0000 0000 0000 0000 0000 0000  ................
00000270: 0000 0000 0000 0000 0000 0000 0000 0000  ................
00000280: 0000 0000 0000 0000 0000 0000 0000 0000  ................
00000290: 0000 0000 0000 0000 0000 0000 0000 0000  ................
000002a0: 0000 0000 0000 0000 0000 0000 0000 0000  ................
000002b0: 0000 0000 0000 0000 0000 0000 0000 0000  ................
000002c0: 0000 0000 0000 0000 0000 0000 0000 0000  ................
000002d0: 0000 0000 0000 0000 0000 0000 0000 0000  ................
000002e0: 0000 0000 0000 0000 0000 0000 0000 0000  ................
000002f0: 0000 0000 0000 0000 0000 0000 0000 0000  ................
00000300: 0000 0000 0000 0000 0000 0000 0000 0000  ................
00000310: 0000 0000 0000 0000 0000 0000 0000 0000  ................
00000320: 0000 0000 0000 0000 0000 0000 0000 0000  ................
00000330: 0000 0000 0000 0000 0000 0000 0000 0000  ................
00000340: 0000 0000 0000 0000 0000 0000 0000 0000  ................
00000350: 0000 0000 0000 0000 0000 0000 0000 0000  ................
00000360: 0000 0000 0000 0000 0000 0000 0000 0000  ................
00000370: 0000 0000 0000 0000 0000 0000 0000 0000  ................
00000380: 0000 0000 0000 0000 0000 0000 0000 0000  ................
00000390: 0000 0000 0000 0000 0000 0000 0000 0000  ................
000003a0: 0000 0000 0000 0000 0000 0000 0000 0000  ................
000003b0: 0000 0000 0000 0000 0000 0000 0000 0000  ................
000003c0: 0000 0000 0000 0000 0000 0000 0000 0000  ................
000003d0: 0000 0000 0000 0000 0000 0000 0000 0000  ................
000003e0: 0000 0000 0000 0000 0000 0000 0000 0000  ................
000003f0: 0000 0000 0000 0000 0000 0000 0000 0000  ................
00000400: 4546 4920 2020 2020 2020 2010 0000 0000  EFI        .....
00000410: 0000 0000 0000 0000 0000 0200 0000 0000  ................
00000420: 0000 0000 0000 0000 0000 0000 0000 0000  ................
00000430: 0000 0000 0000 0000 0000 0000 0000 0000  ................
00000440: 0000 0000 0000 0000 0000 0000 0000 0000  ................
00000450: 0000 0000 0000 0000 0000 0000 0000 0000  ................
00000460: 0000 0000 0000 0000 0000 0000 0000 0000  ................
00000470: 0000 0000 0000 0000 0000 0000 0000 0000  ................
00000480: 0000 0000 0000 0000 0000 0000 0000 0000  ................
00000490: 0000 0000 0000 0000 0000 0000 0000 0000  ................
000004a0: 0000 0000 0000 0000 0000 0000 0000 0000  ................
000004b0: 0000 0000 0000 0000 0000 0000 0000 0000  ................
000004c0: 0000 0000 0000 0000 0000 0000 0000 0000  ................
000004d0: 0000 0000 0000 0000 0000 0000 0000 0000  ................
000004e0: 0000 0000 0000 0000 0000 0000 0000 0000  ................
000004f0: 0000 0000 0000 0000 0000 0000 0000 0000  ................
00000500: 0000 0000 0000 0000 0000 0000 0000 0000  ................
00000510: 0000 0000 0000 0000 0000 0000 0000 0000  ................
00000520: 0000 0000 0000 0000 0000 0000 0000 0000  ................
00000530: 0000 0000 0000 0000 0000 0000 0000 0000  ................
00000540: 0000 0000 0000 0000 0000 0000 0000 0000  ................
00000550: 0000 0000 0000 0000 0000 0000 0000 0000  ................
00000560: 0000 0000 0000 0000 0000 0000 0000 0000  ................
00000570: 0000 0000 0000 0000 0000 0000 0000 0000  ................
00000580: 0000 0000 0000 0000 0000 0000 0000 0000  ................
00000590: 0000 0000 0000 0000 0000 0000 0000 0000  ................
000005a0: 0000 0000 0000 0000 0000 0000 0000 0000  ................
000005b0: 0000 0000 0000 0000 0000 0000 0000 0000  ................
000005c0: 0000 0000 0000 0000 0000 0000 0000 0000  ................
000005d0: 0000 0000 0000 0000 0000 0000 0000 0000  ................
000005e0: 0000 0000 0000 0000 0000 0000 0000 0000  ................
000005f0: 0000 0000 0000 0000 0000 0000 0000 0000  ................
00000600: 4d5a 0000 0000 0000 0000 0000 0000 0000  MZ..............
00000610: 0000 0000 0000 0000 0000 0000 0000 0000  ................
00000620: 424f 4f54 2020 2020 2020 2010 0000 0000  BOOT       .....
00000630: 0000 0000 0000 0000 0000 0200 4000 0000  ............@...
00000640: 5045 0000 6486 0100 0000 0000 0000 0000  PE..d...........
00000650: 0000 0000 7000 2e22 0b02 0000 0000 0000  ....p.."........
00000660: 4100 0000 0000 0000 0010 0000 0010 0000  A...............
00000670: 0000 0040 0100 0000 0100 0000 0100 0000  ...@............
00000680: 4200 0000 0000 0000 0000 0000 0000 0000  B...............
00000690: 0040 0000 f000 0000 0000 0000 0a00 0000  .@..............
000006a0: 424f 4f54 5836 3420 4546 4920 0000 0000  BOOTX64 EFI ....
000006b0: 0000 0000 0000 0000 0000 0200 0002 0000  ................
000006c0: 0000 0000 0000 0000 0000 0000 0000 0000  ................
000006d0: 1a00 0000 0010 0000 1a00 0000 f000 0000  ................
000006e0: 0000 0000 0000 0000 0000 0000 2000 0000  ............ ...
000006f0: 488b 4a40 488d 1505 0000 00ff 5108 ebfe  H.J@H.......Q...
00000700: 4400 6f00 6e00 65                        D.o.n.e

```

Boot:

```
$ qemu-system-x86_64 -bios OVMF.fd -nographic -drive file=disk.bin,format=raw
BdsDxe: failed to load Boot0001 "UEFI QEMU DVD-ROM QM00003 " from    PciRoot(0x0)/Pci(0x1,0x1)/Ata(Secondary,Master,0x0): Not Found
BdsDxe: loading Boot0002 "UEFI QEMU HARDDISK QM00001 " from PciRoot(0x0)/Pci(0x1,0x1)/Ata(Primary,Master,0x0)
BdsDxe: starting Boot0002 "UEFI QEMU HARDDISK QM00001 " from PciRoot(0x0)/Pci(0x1,0x1)/Ata(Primary,Master,0x0)
Done

```

There's way too much to explain in a single answer, so here's a .zip of everything in my working directory, and here's the final .asm:

```
[bits 64]

; Creates a non-partitioned disk image with no MBR/GPT, just FAT12.
; (UEFI specs req. implementations to support FAT12, FAT16, and FAT32 ESP's,
; although there might be smaller partition formats for certain
; implementations).
; FAT12 appears to be optimal.

; Resources:
; https://wiki.osdev.org/FAT
; https://wiki.osdev.org/UEFI
; https://wiki.archlinux.org/title/EFI_system_partition
; https://en.wikipedia.org/wiki/Design_of_the_FAT_file_system
; https://uefi.org/sites/default/files/resources/UEFI_Spec_2_10_Aug29.pdf
; https://archive.vn/w01DO#selection-265.0-265.44
; https://wiki.osdev.org/PE
; https://learn.microsoft.com/en-us/windows/win32/debug/pe-format
; https://johv.dk/blog/bare-metal-assembly-tutorial
; https://github.com/tianocore/edk2
; https://retrage.github.io/2019/12/05/debugging-ovmf-en.html
; https://edk2-docs.gitbook.io/edk-ii-build-specification/
; https://uefi.org/sites/default/files/resources/PI_Spec_1_6.pdf

; As long as OVMF boots this, we're good.

; Layout:
;   - Reserved sectors (1 boot sector, everything else opt.)
;   - FAT region (1 FAT * 1 sector per fat = 1 sector)
;   - Root directory region (1 sector)
;   - Data region (1 sector)

; Now, in a golfing view: whats the absolute smallest this image can be?
; - The minimum SectorSize recognized by OVMF is 512 bytes.
; - I have tried merging the FAT into the boot sector, and certain forensics
; tools can read the image just fine, but OVMF can't as it requires that
; ReservedSectors != 0.
; - OVMF requires a full, dedicated directory for the root directory, and will
; only read it right where it should be, after the FAT. This puts the total to
; 3 sectors so far.
; - It does not look like directories can point to cluster 0, meaning we need
; at least 1 sector for data-- now 4 sectors.

; A lot of the boot sector is intended for old BIOS bootloader code, but
; because we're using UEFI, we can fill most of it with zeros.
boot_sector:
    times 11 db 0x00 ; Ignored by OVMF

    ; DOS 2.0 BPB
    ; OVMF requires a sector size within the range [512, 4096].
    ; See edk2/FatPkg/EnhancedFatDxe/Fat.h:63 for more info.
    dw 512          ; Bytes per sector (512, optimal value)

    ; Need at least one sector per cluster (duh)
    ; Volume->FirstClusterLba is fixed to be directly after the root directory
    ; sector(s), so there's no weird bug that you could get by setting this to
    ; zero or -1. See edk2/FatPkg/EnhancedFatDxe/Init.c:316 for more info.
    db 1            ; Sectors per cluster (1, optimal value)

    ; Can't merge sectors as if ReservedSectors == 0, OVMF returns
    ; EFI_UNSUPPORTED. This is due to a check in the code that assumes this is
    ; not a FAT volume if ReservedSectors is 0.
    ; See edk2/FatPkg/EnhancedFatDxe/Init.c:250 for more info.
    dw 1            ; Reserved sectors (1, optimal value)

    ; Just like ReservedSectors, OVMF returns EFI_UNSUPPORTED if NumFats is
    ; zero. See edk2/FatPkg/EnhancedFatDxe/Init.c:250 for more info.
    db 1            ; # of FATs (1, optimal value)

    ; OVMF returns EFI_UNSUPPORTED if RootEntries is zero and the volume is
    ; not FAT32. See edk2/FatPkg/EnhancedFatDxe/Init.c:285 for more info.
    ; Furthermore, OVMF assumes that the root directory entries will take up a
    ; fixed number of sectors, so any value from 1 to 16 inclusive will equal
    ; a single full sector. See edk2/FatPkg/EnhancedFatDxe/Init.c:312 for more
    ; info.
    ; 16 entries * 32 bytes per entry = 512 bytes, 1 sector.
    dw 16           ; # of root directory entries (16, optimal value)

    ; If Sectors and LargeSectors (which we are not using) are both zero, OVMF
    ; returns EFI_UNSUPPORTED. See edk2/FatPkg/EnhancedFatDxe/Init.c:250 for
    ; more info.
    ; OVMF will, understandably, fail to properly read the volume if this is
    ; not just the actual value that it should be.
    dw 4            ; Total logical sectors (4)

    db 0            ; Ignored by OVMF

    ; If SectorsPerFat is zero, OVMF assumes that this volume is FAT32. FAT32
    ; requires a whole lot more sectors of random information, so we can't use
    ; it here.
    ; See edk2/FatPkg/EnhancedFatDxe/Init.c:239 for more info.
    dw 1            ; Sectors per FAT (1, optimal value)

    times 512 - ($ - boot_sector) db 0 ; Boot code + BIOS signature

; Sector 2: The File Allocation Table
; Since we're using FAT12, things get a little difficult in NASM.
; Two entries are 24 bits = 3 bytes, but each entry is stored a little
; awkwardly. See Wikipedia for more info.
; 0b111111111111000000000000
; Split
; 0b11111111 0b11110000 0b00000000
; Reverse byte order (little endian)
; 0b00000000 0b11110000 0b11111111

; Table index 0 is the FAT ID (equal to BPB_Media with high bits 1), and index
; 1 is the end-of-chain indicator (0xFFF)
; However, setting them both to zero results in no difference to OVMF.
file_allocation_table:
    ; FAT ID (0), EOC (0), Cluster 2 (EOC)
    db 0x00, 0x00, 0x00, 0xff, 0x0f, 0x00

    ; Fill rest of table with zero bytes
    times 512 - ($ - file_allocation_table) db 0

; Sector 3: Root directory region
; Each entry is 32 or 64 bytes, an 8.3 format chunk followed by an optional
; long file name chunk. Here we will just use 8.3.
; There is only one file in the root directory-- EFI.
; (/EFI/BOOT/BOOTX64.EFI)
root_dir_region:
    db "EFI        "    ; 8.3 file name (11 chars, space padded)
    db 0x10             ; Attributes (DIRECTORY)
    times 14 db 0       ; Ignored to boot by OVMF
    dw 2                ; Low 16 bits first cluster number (cluster 2)
    times 4 db 0        ; Ignored to boot by OVMF

    ; Fill rest of region with zero bytes
    times 512 - ($ - root_dir_region) db 0

; Since indices 0 and 1 of the FAT are reserved, the first cluster is really
; cluster 2. Using some tricks, we can store all of the data we need in this
; single cluster.
; This cluster is:
;   - The contents of /EFI/ (a listing of directories and files,
;       including BOOT)
;   - The contents of /EFI/BOOT/ (a listing of directories and files,
;       including BOOTX64.EFI)
;   - The contents of BOOTX64.EFI (the file to be booted)
cluster_2:
    ; Once OVMF reads an entry with a zeroed first byte, it stops reading.
    ; Due to how much of a pain OVMF is, the best way to golf this is to
    ; squeeze in the entries where they fit in the EFI and hope for the best.

    ; MZ header
    ; Looks like it's required, even though parts of edk2 are able to handle PE
    ; executables that don't have an MZ header.
    ; EDK II Build Spec. doesn't say much other than "All EFI images must be
    ; formatted PE32/PE32+/COFF." The UEFI specs seem to require the MS-DOS
    ; stub.
    ; There's also extensive support for Terse Executable images (see UEFI
    ; PI specs section 15), but it appears that won't work here either.
mz_hdr:
    db "MZ"
    times 30 db 0

    ; ./BOOT/, but also MZ header part 2.
    ; Here a bit of a hack is employed to save a sector:
    ; If we say that BOOT occupies cluster 2, we can put BOOTX64.EFI right
    ; in this same sector as it refers back to this.
    db "BOOT       "    ; 8.3 file name (11 chars, space padded)
    db 0x10             ; Attributes (DIRECTORY)
    times 14 db 0       ; Ignored to boot by OVMF
    dw 2                ; Low 16 bits of first cluster number (cluster 2)

    ; edk2/BaseTools/Source/C/Common/BasePeCoff.c for some details on how
    ; e_lfanew is read
    dd pe_hdr - cluster_2   ; e_lfanew

    ; PE header
pe_hdr:
    dd "PE"         ; mMagic (0x00004550)
    dw 0x8664       ; mMachine (IMAGE_FILE_MACHINE_AMD64)
    dw 1            ; mNumberOfSections (1)
    dd 0            ; mTimeDateStamp (unused)
    dd 0            ; mPointerToSymbolTable (unused)
    dd 0            ; mNumberOfSymbols (unused)
    dw popt_hdr_len ; mSizeOfOptionalHeader (required to be correct value)
    dw 0x222e       ; mCharacteristics (IMAGE_...)

    ; PE optional (required by OVMF) header
    ; Setting popt_hdr_len to zero results in RETURN_UNSUPPORTED, so there
    ; doesn't seem to be any way that the code section header can be merged
    ; with the optional header.
pe_opt_hdr:
    dw 0x20B        ; mMagic (PE32+ 64 bit)
    db 0            ; mMajorLinkerVersion (unused)
    db 0            ; mMinorLinkerVersion (unused)
    dd 0            ; mSizeOfCode (unused)
    db "A", 0, 0, 0 ; mSizeOfInitializedData (used to keep FAT entries going)
    dd 0            ; mSizeOfUninitializedData (unused)
    dd 0x1000       ; mAddressOfEntryPoint (0x1000)
    dd 0x1000       ; mBaseOfCode (0x1000)
    dq 0x140000000  ; mImageBase (OVMF ignores this, but with PIC who cares)
    dd 0x1          ; mSectionAlignment (1 byte)
    dd 0x1          ; mFileAlignment (1 byte)
    db "B", 0       ; mMajorOperatingSystemVersion (used to keep FAT going)
    dw 0            ; mMinorOperatingSystemVersion (unused)
    dw 0            ; mMajorImageVersion (unused)
    dw 0            ; mMinorImageVersion (unused)
    dw 0            ; mMajorSubsystemVersion (unused)
    dw 0            ; mMinorSubsystemVersion (unused)
    dd 0            ; mWin32VersionValue (unused)
    dd 0x4000       ; mSizeOfImage (must be weirdly large)
    dd all_hdrs_len ; mSizeOfHeaders
    dd 0            ; mCheckSum (unused)
    dw 0xa          ; mSubsystem (EFI)
    dw 0            ; mDllCharacteristics (unused)
    db "BOOTX64 "               ; mSizeOfStackReserve (entry BOOTX64.EFI)
    db "EFI", 0x20, 0, 0, 0, 0  ; mSizeOfStackCommit (BOOTX64 name + attr)
    db 0, 0, 0, 0, 0, 0, 0, 0   ; mSizeOfHeapReserve (BOOTX64 unused)
    db 0, 0, 2, 0, 0, 2, 0, 0   ; mSizeOfHeapCommit (BOOTX64 unused, clst, sze)
    dd 0            ; mLoaderFlags (unused)
    dd 0            ; mNumberOfRvaAndSizes (unused)

popt_hdr_len: equ $ - pe_opt_hdr

; Code section (only section)
code_sec_hdr:
    times 8 db 0    ; mName (unused)
    dd code_sec_len ; mVirtualSize (small as possible)
    dd 0x1000       ; mVirtualAddress (0x1000)
    dd code_sec_len ; mSizeOfRawData (small as possible)
    dd code_sec-cluster_2   ; mPointerToRawData
    dd 0            ; mPointerToRelocations (unused)
    dd 0            ; mPointerToLinenumbers (unused)
    dw 0            ; mNumberOfRelocations (unused)
    dw 0            ; mNumberOfLinenumbers (unused)
    dd 0x20         ; mCharacteristics (rx)

all_hdrs_len: equ $ - mz_hdr

; OVMF REFUSES to load sections with mPointerToRawData before mSizeOfHeaders,
; and falsifying mSizeOfHeaders results in the EFI file just not loading.
; Overall the PE loader seems pretty robust; see
; edk2/MdePkg/Library/BasePeCoff.c for more info.

code_sec:
    ; Output "Done" and loop forever.
    ; In RDX: EFI_SYSTEM_TABLE*

    ; Get EFI_SYSTEM_TABLE->ConOut (EFI_SIMPLE_TEXT_OUTPUT_PROTOCOL*)
    mov rcx, [rdx+64]

    ; Get EFI_SIMPLE_TEXT_OUTPUT_PROTOCOL->OutputString()
    ; <inlined into call directive>

    ; OutputString(rcx this, rdx string)
    ; `this` is already in RCX
    lea rdx, [rel str]

    ; 32 bytes of shadow space is supposed to be allocated, but OVMF runs
    ; without it.
    call [rcx+8] ; Call print

    ; jmp $
    db 0xeb, 0xfe

    ; "Done" + NUL in UTF-16LE
    ; echo -ne "Done\0" | iconv -f UTF-8 -t UTF-16LE |
    ;   hexdump -e ' 1/1 "0x%02x, " ' -v
    ; The last three bytes are 0x00, and since we are at the end of file we can
    ; let OVMF fill in the rest.
    str: db 0x44, 0x00, 0x6f, 0x00, 0x6e, 0x00, 0x65

code_sec_len: equ ($ - code_sec) + 3

    ; OVMF fills the rest of the sector with zero bytes, meaning the smaller
    ; the .efi file is, the smaller the image is.

```

At this point, I think this is pretty close to the lower bound for OVMF without using any major bugs or exploits.

# Answer
> 8 votes
# 16897 bytes (33+1 512-byte blocks), OVMF

Reproduce with

```
base64 -d <<\EOF | lz4 -d > a
BCJNGGRApyIJAAD0Des8kG1rZnMuZmF0AAIEAQABEABEAPgBABAAAgABAPlSgAApzas0Ek5PIE5BTUUgICAgRkFUMTIgICAOH75bfKwiwHQLVrQOuwcAzRBe6/Ay5M0WzRnr/lRoaXMgaXMgbm90IGEgYm9vdGFibGUgZGlzay4gIFBsZWFzZSBpbnNlciAA9B5mbG9wcHkgYW5kDQpwcmVzcyBhbnkga2V5IHRvIHRyeSBhZ2FpbiAuLi4gDQqjAA8CAP8l/w1Vqvj//wjw//9vAAfw/wmgAAvw/w3gAA8AAf8PUwH/JQ8CAJwwRUZJ0QMAAgCwEAAfiw2eVZ5VAAAIABEDygDzBEFOAHYAVgBhAHIADwBwcwAAAP8BAAIKAGBOVlZBUlM/AFMgAAAAkkAAAAgAAT8ADwIA/4/wGxYAAABDAHUAcwB0AG8AbQBNAG8AZABlAAAADOx2wChwmUOgcnHuXESLnxACEAHQAfMYDgAAAGMAZQByAHQAZABiAAAAbuW+2dx12Um017U0IQ9jeicAAAAEBADwCRoAAABWAGUAbgBkAG8AcgBLAGUAeQBzAFgC8wQAAODkc5DsYG5LmQNMIjwmDzwjZQDzDwEIAAAATQBUAEMAAAARQHDrAhTTEY53AKDJaXI7B1sAAI4A8BkUAAAAQQB0AHQAZQBtAHAAdAAgADEAAABFSTJZROwNTLHNnbE53wcMvgAQGZQADAIAAEUAAQIAgEF0dGVtcHQgPgAPAgB9L7wMkgB9DwIAfhDo4gEPAgD/BQXkAg8CAP8JD0kEAR8ySQQZBTALBEkEAD4ADwIAfQ9JBP//ABEuuwkBAgAPAAoCFi4hAAsgAALbAkFCT09UPgAAIAAjkIwACgAIAA9tBwEPAgD/////////hgbfBwzgBwLABw8ACAcCcA0AAAhAWDY0IEgSCgAITwUAlhfwB/////////+GDAIAQE1akADKBwDuBwDUGRO4IQATQAgADwIACfEDgAAAAA4fug4AtAnNIbgBTM0h8x2wcHJvZ3JhbSBjYW77HfMIYmUgcnVuIGluIERPUyBtb2RlLg0NCiRZAHJQRQAAZIYGDgDxABAAADsAAADwACYiCwICI4MeBOMdExAEADEAlGotAAAQABICuAAAAgARBS0AQgAAAHAdGDOPBQE7AACYGgQ8AAACAAA5AAgQAAMSACFQAGwYIgBgCxQFAgA/MAAAfRdRkC50ZXh0AAAAWHkAAKMAAE8UAJUBBwIAwSAAUGAucmRhdGEAAEABANsAACgAAz8BBAIAYkAAUEAucCgAAbwAEzAoAABVGQcCAGJAADBALngoAAEbAAD1AQBQAAI5AQUCAAEoABJlKAAAkBkjAFBQAAFdAAYCAAEoABJpKAAATxUATAEBlwEAMhoHAgBHQAAwwA8ADwIA/2vwAkiD7DhIiUwkMEiJVCQoSItEBQCQQEBIi0AISItMDQDwBUlASI0V1Q8AAP/Q6fv///9mDx9ELAQCAgAEvQECDgAGEAAPAgD/lvEGSABlAGwAbABvACwAIAB0AHIAYQBjDB4zcgAuQgUPAgD/y0AQAAAycAYA/AUPAgD/4W8BBAEABGL5Af/hBwIAQGc9rmMPACIyUCsgAC8gAAQAkChQAAAsUAAAMPAJAJwLAAgA8AIAbWFpbi5kbGwARWZpTWFpbjoADwIA////qgR4DgACAAD0AyADAbciAAoAQBh/uOQIACQAACQOAAIAAJMOEQOeJwACAEAxf4g3EgAkAACYDgACAABDDjADASILAIEAAAA8NQdcBQoABJQOAAIAAHQQIAMBQQ4ACgBCAFTox8UOcEBmZWF0LjCyDhAATgwZA2cEoQEAIAACAC5maWyiKJEAAAD+/wAAZwGUBAHEBAgCAACaAAAoDwCQAAAEACAAAF8oAAIAAA4AAAQAIAAA7gATSHUoAhIAEEEXAAkSAAH3BDAAlGqQAAIkAB1cWgAAdxAAAgAGJAAQiA8AGBASABChEgAhACDYAAJIABG7uhAIJAAR1yQAAOoABCQAEOkPAAmQABH7EAAIJAAQCy8AA0wAAloALBkBogAQPCQACZAAEFQSAAlaABlmEgBxX19kbGxfXyQABtgAE3YkAAYSABGLEgAIIAEQmhIACWwAIrABFBAA5gECogAdvKIAENo2AAMzEAIkAFnnAQAAOKIAE/UkAAA2AQIkABIBBwAQABkAAgsAEhEHAAcSACwjAkgAEzIkAAbGABBFEgAYAhIAIlgCRAIGJAAobQLGAFNfX2VuZCABBn4ALHsCUgIQiVoAJwAQ+AERohIACDYAILQC7AIIbAAdwiQAE88SAAaQAB3nEgAs+AL4ASEKA9cAB34AECZpAAkSACw+AzYAE2AkAALYAPAWcAMAAF9fX1JVTlRJTUVfUFNFVURPX1JFTE9DX0xJU1RfXwBfX/kRYV9zdGFydA8AVl9EVE9SHgBHX3Rscx4A8wdJbWFnZUJhc2UAX19ydF9wc3JlbG9jIgAATQDxA2xsX2NoYXJhY3RlcmlzdGljc1YAcHNpemVfb2ZKAIJja19jb21taW8AChkAcXJlc2VydmUzAPEIbWFqb3Jfc3Vic3lzdGVtX3ZlcnNpb24cAHBfY3J0X3hsTwAEtwABEgAfaRIAAALtAUNfX2JzpwACQgAPFQEHMUVORCMABJsASGhlYXCzAAJ9AB1wawATcFgCqV9fbWlub3Jfb3O0ABBpOwFCX2Jhc98AQHNlY3TPAIJhbGlnbm1lbg8BNUlBVEYAD6IABwBkAAG3AQTcABlDtAEA6gAEGgACrQAVY1UABBAAB/EBCj0ACdYBIGl66QEAuAULqAACnQEL4gAAvQAGWAAKSAIJTQEI5wECkQAXdE4BBvMBAOgAAYECBM4AAncAAkoBCBACsmxvYWRlcl9mbGFncAIIxgA1ZW5klAEGXAAIPwACsAEOVwAPggEHBCQCBL4AAqEAAZ8DDwIAgAAOBA8CAP8OAPoWDJIwHzNJLBkDegUGSSwAPgAPAgB9D0ks//8ADwIAGw9JBP8mHzRJBBkAAA0BAgAEkjAAPgAPAgB9D0kE////Zx81SQQZAG0PAQIABEkEAD4ADwIAfQ9JBP8gUAAAAAAAAAAAAHtyWAQ=
EOF

```

Boots as expected:

```
$ qemu-system-x86_64 -enable-kvm -bios /usr/share/ovmf/OVMF.fd -nographic -drive file=a,format=raw
BdsDxe: failed to load Boot0001 "UEFI QEMU DVD-ROM QM00003 " from PciRoot(0x0)/Pci(0x1,0x1)/Ata(Secondary,Master,0x0): Not Found
BdsDxe: loading Boot0002 "UEFI QEMU HARDDISK QM00001 " from PciRoot(0x0)/Pci(0x1,0x1)/Ata(Primary,Master,0x0)
BdsDxe: starting Boot0002 "UEFI QEMU HARDDISK QM00001 " from PciRoot(0x0)/Pci(0x1,0x1)/Ata(Primary,Master,0x0)
Hello, tractor.
^AxQEMU: Terminated

```

Obtained with

```
$ for i in $(seq 100); do truncate -s $((512 * i)) a && mkfs.fat -af1 -F12 -h0 --mbr=no -r16 -S 512 -R 1 -b 0 --invariant a && break; done 2>&1 | sed 'N;s/\n/\t/' | uniq -c
      6 mkfs.fat: Attempting to create a too small or a too large filesystem    mkfs.fat 4.2 (2021-01-31)
     61 mkfs.fat: Too few blocks for viable filesystem  mkfs.fat 4.2 (2021-01-31)
      1 mkfs.fat 4.2 (2021-01-31)
$ ls -l a
-rw-r--r-- 1 nabijaczleweli users 34816 Dec 30 02:35 a
# mount -o noatime a a.d
# mkdir -p a.d/EFI/BOOT/
# cp uefi-simple/main.efi a.d/EFI/BOOT/BOOTX64.EFI
# umount a.d
$ truncate -s 16897 a

```

Why 16897? The first all-zero block is 31, so I iterated on `for f in $(seq 31 68); do dd count=$f <a.bkp >b; st -e qemu-system-x86_64 -enable-kvm -bios /usr/share/ovmf/OVMF.fd b -nographic; done`, and the first one that booted to the image was 34(\*512=17408). Then I tried to trim it back even more, and having just the first byte of block 34 is sufficient, so 17408-511=16897.
I'm assuming this is due to QEMU rounding the block count up with standard semantics, and OVMF needing to "see" the entire `\EFI\BOOT\BOOTX64.EFI`.

Seeing as these are disk images, byte counts make little sense. Judge this as you wish.

The only limiting condition here is the bootable file which has huge swaths of empty space:

```
$ wc -c main.efi
6038 main.efi
$ size main.efi
   text    data     bss     dec     hex filename
    211      20       0     231      e7 main.efi

```

.text EfiMain is a whole of 56 bytes. (Yes, it's possible to produce a 5490-byte executable by getting rid of the print, as well as 4096/3584-byte executables by `strip --strip-all` resp., the minimum size is the same. I maintain that making a pathologically smaller PE would probably work to shrink this method, but this is not my area of expertise, so who knows.)

main.efi was obtained by building https://github.com/utshina/uefi-simple/blob/e02a105b2d63cf8a116fa64600b6755d625ced28/main.c:

```
#define IN
#define EFIAPI
#define EFI_SUCCESS 0

typedef unsigned short CHAR16;
typedef unsigned long long EFI_STATUS;
typedef void *EFI_HANDLE;

struct _EFI_SIMPLE_TEXT_OUTPUT_PROTOCOL;
typedef
EFI_STATUS
(EFIAPI *EFI_TEXT_STRING) (
    IN struct _EFI_SIMPLE_TEXT_OUTPUT_PROTOCOL  *This,
    IN CHAR16                                   *String
    );

typedef struct _EFI_SIMPLE_TEXT_OUTPUT_PROTOCOL {
    void             *a;
    EFI_TEXT_STRING  OutputString;
} EFI_SIMPLE_TEXT_OUTPUT_PROTOCOL;

typedef struct {
    char                             a[52];
    EFI_HANDLE                       ConsoleOutHandle;
    EFI_SIMPLE_TEXT_OUTPUT_PROTOCOL  *ConOut;
} EFI_SYSTEM_TABLE;

EFI_STATUS
EFIAPI
EfiMain (
    IN EFI_HANDLE        ImageHandle,
    IN EFI_SYSTEM_TABLE  *SystemTable
    )
{
    SystemTable->ConOut->OutputString(SystemTable->ConOut, L"Hello, tractor.\n");
    while(1);
    return EFI_SUCCESS;
}

```

with clang trunk as `cc --target=x86_64-w64-mingw32 -shared -nostdlib -mno-red-zone -fno-stack-protector -Wall -e EfiMain main.c -o main.dll; objcopy --target=efi-app-x86_64 main.dll main.efi`, likewise adapted from instructions in the linked.

---
Tags: code-golf
---