title: Long multiply, 8 bits at a time

text:
# Question
Title: Long multiply, 8 bits at a time
You are given a 16-bit machine and told to implement multiplication of arbitrary-sized integers. Your registers can only hold 16-bit numbers, and the biggest multiply instruction takes two 8-bit inputs and generates a 16-bit result.

Your program must take as input two arbitrary-sized positive numbers and output their product. Each input number is encoded on its own line as a little-endian byte array where each byte is a 2-digit hex number. The output must be similarly formatted. Perhaps best explained with an example:

**input**

```
1f 4a 07
63 a3

```

**output**

```
fd 66 03 a7 04

```

which encodes the multiplication 477727\*41827=19981887229.

You can assume that the last (most significant) byte of each input number is nonzero, and the last chunk of the number you output must be nonzero. Both input numbers will be at most 100 bytes long.

Smallest code wins.

Remember, the biggest multiply you are allowed to use is 1 byte * 1 byte, and no integer types bigger than 2 bytes!

# Answer
> 14 votes
# Perl, 137 characters

```
($x,$y)=<>;while($x=~s/.. *//s){$e=hex$&;$i=0;$s=$r[$i]+=$e*hex,$r[$i]&=255,$r[++$i]+=$s>>8 for$y=~/.. */gs;$y="00$y"}printf'%02x 'x@r,@r

```

## Caveats

* Sometimes prints an extra `00` byte at the end of the result. Of course the result is still correct even with that extra byte.
* Prints an extra space after the last hex byte in the result.

## Explanation

The explanation is going to be a bit long, but I think most people here will find it interesting.

First of all, when I was 10 years old, I was taught the following little trick. You can multiply any two positive numbers with this. I will describe this using the example of 13 × 47. You start by writing the first number, 13, and *dividing* it by 2 (round down each time) until you reach 1:

```
13
 6
 3
 1

```

Now, next to the 13 you write the other number, 47, and keep *multiplying* it by 2 the same number of times:

```
13     47
 6     94
 3    188
 1    376

```

Now you cross out all the lines where the number on the left is *even*. In this case, this is only the 6. (I can’t do strike-through in code, so I’ll just remove it.) Finally, you add all the remaining numbers on the right:

```
13     47
 3    188
 1    376
     ----
      611

```

And this is the right answer. 13 × 47 = 611.

Now, since you are all computer geeks, you will have realised that what we’re actually doing in the left and right columns is `x >> 1` and `y << 1`, respectively. Furthermore, we add the `y` only if `x & 1 == 1`. This translates directly into an algorithm, which I’ll write here in pseudocode:

```
input x, y
result = 0
while x > 0:
    if x & 1 == 1:
        result = result + y
    x = x >> 1
    y = y << 1
print result

```

We can re-write the `if` to use a multiplication, and then we can easily change this so that it works on a byte-by-byte basis instead of bit-by-bit:

```
input x, y
result = 0
while x > 0:
    result = result + (y * (x & 255))
    x = x >> 8
    y = y << 8
print result

```

This still contains a multiplication with `y`, which is arbitrary-size, so we need to change that into a loop too. We’ll do that in Perl.

Now translate everything to Perl:

* `$x` and `$y` are the inputs in hex format, so they have the *least* significant byte *first*.
* Thus, instead of `x >> 8` I do `$x =~ s/.. *//s`. I need the space+star because the last byte might not have a space on it (could use space+`?` too). This automatically puts the removed byte (`x & 255`) into `$&`.
* `y << 8` is simply `$y = "00$y"`.
* The `result` is actually a numerical array, `@r`. At the end, each element of `@r` contains one byte of the answer, but halfway through the calculation it may contain more than one byte. I’ll prove to you below that each value is never more than *two* bytes (16 bits) and that the result is always one byte at the end.

So here is the Perl code unravelled and commented:

```
# Input x and y
($x, $y) = <>;

# Do the equivalent of $& = x & 255, x = x >> 8
while ($x =~ s/.. *//s)
{
    # Let e = x & 255
    $e = hex $&;

    # For every byte in y... (notice this sets $_ to each byte)
    $i = 0;
    for ($y =~ /.. */gs)
    {
        # Do the multiplication of two single-byte values.
        $s = $r[$i] += $e*hex,
        # Truncate the value in $r[$i] to one byte. The rest of it is still in $s
        $r[$i] &= 255,
        # Move to the next array item and add the carry there.
        $r[++$i] += $s >> 8
    }

    # Do the equivalent of y = y << 8
    $y = "00$y"
}

# Output the result in hex format.
printf '%02x ' x @r, @r

```

Now for the proof that this always outputs *bytes*, and that the calculation never generates values greater than *two* bytes. I’ll prove this by induction over the `while` loop:

* The empty `@r` at the beginning clearly has no values greater than 0xFF in it (because it has no values in it at all). This concludes the base case.
* Now, given that `@r` contains only single bytes at the beginning of each `while` iteration:

+ The `for` loop explicitly `&=`s all values in the result array with 255 *except the last one*, so we only need to look at that last one.
    + We know that we always remove only one byte from `$x` and `$y`:

    - Therefore, `$e*hex` is a multiplication of two single-byte values, which means it’s in the range `0 — 0xFE01`.
        - By the inductive hypothesis, `$r[$i]` is one byte; therefore, `$s = $r[$i] += $e*hex` is in the range `0 — 0xFF00`.
        - Therefore, `$s >> 8` is always one byte.
    + `$y` grows an extra `00` in each iteration of the `while` loop:

    - Therefore, in every iteration of the `while` loop, the inner `for` loop runs for one more iteration than it did in the previous `while` iteration.
        - Therefore, the `$r[++$i] += $s >> 8` in the last iteration of the `for` loop always adds `$s >> 8` to `0`, and we already established that `$s >> 8` is always one byte.
    + Therefore, the last value stored in `@r` at the end of the `for` loop is also a single byte.

This concludes a wonderful and exciting challenge. Thanks a lot for posting it!

# Answer
> 4 votes
**C Solution**

This solution does no input validation. It's also only lightly tested. Speed was not really a consideration. Malloc's memory, and isn't particularly clever about how much it grabs. Guaranteed to be enough, and more than necessary.

m() accepts a string, expects two newlines in the string, one after each number. Expects only numbers, lowercase characters, spaces, and newlines. Expects hex digits to always be a pair.

No multiply operation is ever used (knowingly). Shifting is performed on 8-bit variables. One 16-bit addition is performed. No 32-bit data types.

Shrunk by hand, and only mildly. **edit:** more obfuscation, fewer chars :D Compiles with warnings with gcc.

Characters: 675

```
typedef unsigned char u8;
#define x calloc
#define f for
#define l p++
#define E *p>57?*p-87:*p-48
#define g(a) --i;--a;continue
void m(u8*d){short n=0,m=0,a,b,i,k,s;u8*t,*q,*r,*p=d,o;f(;*p!=10;n++,l){}l;f(;*p
!=10;m++,l){}t=x(n,1);q=x(m,1);r=x(n,1);p=d;a=n;i=0;f(;*p!=10;i++,l){if(*p==32){
g(a);}t[i]=E;t[i]<<=4;l;t[i]|=E;}a/=2;b=m;i=0;l;f(;*p!=10;i++,l){if(*p==32){g(b)
;}q[i]=E;q[i]<<=4;l;q[i]|=E;}b/=2;f(k=0;k<8*b;k++){if(q[0]&1){o=0;f(i=0;i<n;i++)
{s=o+t[i]+r[i];o=s>>8;r[i]=s&255;}}f(i=n;i;i--){o=t[i-1]>>7&1;t[i-1]*=2;if(i!=n)
t[i]|=o;}f(i=0;i<m;i++){o=q[i]&1;q[i]/=2;if(i)q[i-1]|=(o<<7);}}k=(r[a+b-1]==0)?a
+b-1:b+a;f(i=0;i<k;i++){printf("%02x ",r[i]);}putchar(10);}

```

You can test with this:

```
int main(void){
  m("1f 4a 07\n63 a3\n");
  m("ff ff ff ff\nff ff ff ff\n");
  m("10 20 30 40\n50 60 70\n");
  m("01 02 03 04 05 06\n01 01 01\n");
  m("00 00 00 00 00 00 00 00 00 00 00 00 01\n00 00 00 00 00 00 00 00 02\n");
  return 0;
}

```

Result:

```
$ ./long
fd 66 03 a7 04
01 00 00 00 fe ff ff ff
00 05 10 22 34 2d 1c
01 03 06 09 0c 0f 0b 06
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 02

```

# Answer
> 4 votes
# OCaml + Batteries, 362 characters

A standard O(n\*m) schoolboy multiplication algorithm. Note that in order to meet the challenge requirements, the operations are done on the bytes of strings, which in OCaml are (conveniently, in this case) mutable. Note also that the accumulator `s` never overflows 16 bits, since 2(2^8 - 1) + (2^8 - 1)^2 = (2^8 - 1)(2^8 + 1) = 2^16 - 1.

```
let(@)=List.map
let m a b=Char.(String.(let e s=of_list(((^)"0x"|-to_int|-chr)@nsplit s" ")in
let a,b=e a,e b in let m,n=length a,length b in let c=make(m+n)'\000'in
iteri(fun i d->let s,x=ref 0,code d in iteri(fun j e->let y=code e in
s:=!s+code c.[i+j]+x*y;c.[i+j]<-chr(!s mod
256);s:=!s/256)b;c.[i+n]<-chr!s)a;join" "((code|-Printf.sprintf"%02x")@to_list c)))

```

For example,

```
# m "1f 4a 07" "63 a3" ;;
- : string = "fd 66 03 a7 04"

# m "ff ff ff ff" "ff ff ff ff" ;;
- : string = "01 00 00 00 fe ff ff ff"

```

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

```
x=>y=>x.map((t,i)=>y.map(u=>(f=i=>(c=s[i]>>8)&&f(i++,s[i]=c+~~s[i],s[i-1]%=256))(i,s[i]=~~s[i++]+`0x${t}`*`0x${u}`)),s=[])&&s.map(t=>(t<16?0:'')+t.toString(16))

```

Try it online!

Lot newer language than that time though

# Answer
> 0 votes
# 8086 DOS .COM file, 134 bytes

It works now!

What better language to do this in than 16-bit assembly?

```
00000000: b9 c8 00 89 cd 31 c0 f3 50 89 e7 e8 5d 00 92 aa  .....1..P...]...
00000010: 74 f9 29 e7 87 fb 89 e6 8d 3a e8 4e 00 9c 56 57  t.)......:.N..VW
00000020: 89 d9 ac f6 e2 03 05 ab 83 15 00 4f e2 f4 5f 5e  ...........O.._^
00000030: 47 9d 74 e6 80 39 00 74 01 4b 01 df 01 e5 29 ef  G.t..9.t.K....).
00000040: 89 ee ac 88 c3 b1 04 d2 e8 e8 10 00 93 24 0f e8  .............$..
00000050: 0a 00 b0 20 e8 0d 00 4f 75 e8 cd 20 3c 09 76 02  ... ...Ou.. <.v.
00000060: 04 27 04 30 b4 02 88 c2 cd 21 c3 b2 00 b4 01 cd  .'.0.....!......
00000070: 21 2c 30 72 0e 3c 0a 72 02 2c 27 b1 04 d2 e2 00  !,0r.<.r.,'.....
00000080: c2 eb ea 3c f0 c3                                ...<..

```

My first, and likely last 16-bit 8086 program.

Assembly (NASM with C comments because of syntax highlighting):

```
        // sed -i -e 's#//#;#g' dosmult.asm
        // nasm -f bin dosmult.asm -o dosmult.com

        // The default, but never harmed anyone.
        [bits 16]
        // 8086 code only! If I use 386 instructions or any of that,
        // I would ruin the challenge.
        [cpu 8086]
        // COM files start at 100h.
        org 100h

        section .text

start:
        // Create a 400 byte buffer on the stack.
        // 200 will be reserved for the input, and 200 for the output.
        mov     cx, 200
        // Save 200 in BP for later, it will be useful.
        mov     bp, cx
        // Push 0 200 times making a 400 byte zeroed buffer on the stack
        xor     ax, ax
        rep     push ax

        mov     di, sp
        // Read the first line of hex digits.
.getline_loop:
        call    gethex
        // Swap DL to AL and store with STOSB
        xchg    dx, ax
        stosb
        // Loop if it was a space
        jz      .getline_loop

        // Get length
        sub     di, sp
        // Store length in BX
        xchg    di, bx
        // Save the pointer to input in SI
        mov     si, sp
        // Load the pointer to output in DI (SI + 200)
        lea     di, [si + bp]

        // Begin multiplication, grade school byte by byte
        // Instead of creating a third buffer, we process the data
        // as the user inputs it.
.loop:
        call    gethex
        // Save flags from gethex so we know when to stop
        pushfw
        // Save SI and DI
        push    si
        push    di
        // Loop counter
        mov     cx, bx
.mult_loop:
        // Load next byte from first input
        lodsb
        // Multiply by the input byte
        mul     dl
        // 16-bit add to [DI]
        // We actually add to AX, then do STOSW.
        add     ax, [di]
        stosw
        // Add the carry bit.
        adc     word [di], 0
        // Decrement DI after STOSW incremented it by 2 to iterate
        // on each byte.
        dec     di
        // while (--cx)
        loop    .mult_loop
.mult_loop_end:
        // Restore DI and SI
        pop     di
        pop     si
        // Increment output pointer
        inc     di
        // Restore flags from gethex
        popfw
        // Jump if we got a space.
        jz      .loop

.loop_end:
        // Was there a trailing zero?
        cmp     byte[di + bx], 0
        jz      .nodec
.dec:
        // If so, decrement the count.
        dec     bx
.nodec:
        // Calculate the length with ugly pointer arithmetic.
        // I feel there is a better way to do this.
        add     di, bx // ptr += len
        add     sp, bp // sp += 200 (sp = output)
        sub     di, sp // ptr -= output
        // Store output array in SI.
        mov     si, sp
        // Print each byte in hex
.print_loop:
        // Load byte
        lodsb
        // puthex(AL >> 4)
        mov     bl, al
        mov     cl, 4
        shr     al, cl
        call    puthex
        // puthex(AL & 0Fh)
        xchg    ax, bx
        and     al, 0Fh
        call    puthex
        // putc(' ')
        mov     al, ' '
        call    putc
        // Loop for every byte from DI.
        dec     di
        jnz     .print_loop
.print_loop_end:
        // exit, not bothering to clean anything up. :P
        int     20h

        // Prints hex digit in AL.
        // Must be <= 0fh
puthex:
        cmp     al, 9
        jbe     .no_hexa
.hexa:
        add     al, 'a' - '9' - 1
.no_hexa:
        add     al, '0'
        // Fallthrough

        // Prints AL to stdout.
putc:
        mov     ah, 2h
        mov     dl, al
        int     21h
        ret

        // Reads a hex byte.
        // Returns in DL.
        // Sets whether it ended in a space in the Z flag.
gethex:
        mov     dl, 0
.start:
        // Read char into AL
        mov     ah, 1h
        int     21h
        // Subtract ASCII '0'
        sub     al, '0'
        // If we hit a space or newline, they will trigger the 'below'
        // condition
        jb      .ret
        // Was AL '0'-'9'? If not, correct it to 'a'-'f'.
        cmp     al, 10
        jb      .no_hexa
.hexa:
        // Correct AL
        sub     al, 'a' - '9' - 1
.no_hexa:
        // DL = (DL << 4) + AL
        // 8086 doesn't have shift by immediate.
        mov     cl, 4
        shl     dl, cl
        // Add to BL
        add     dl, al
        // Loop
        jmp     .start
.ret:
        // Check if AL before the subtraction was a space.
        cmp     al, ' ' - '0'
        ret

```

Naturally, being a 16-bit instruction set, I am only doing 8-bit and 16-bit arithmetic (and I don't use the 16-bit `mul`).

Beats the Perl answer by 3 bytes. Granted, this is binary machine code and that is source code, so I guess this isn't that much to get excited about. However, 8086 lacks a lot of the features Perl has (about 1/3 of it is just I/O and hex conversion ).

I am sure there are multiple optimizations possible here. A lot of my knowledge is from writing 32-bit and 64-bit code, so I am not fully knowledgeable in the 16-bit tricks.

Input is from stdin, in space separated lowercase hex, each ending in a new line. It is not line buffered, so no typos allowed! :P

Output is printed to stdout.

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


title: Interpret Interval Notation

text:
# Question
Title: Interpret Interval Notation
Interval notation is a way to write complicated range bounds more conveniently and concisely than writing an inequality. The challenge, should you choose to accept it, is to write a program or function that interprets a subset of interval notation. In this subset, intervals are a comma-separated pair of integers delimited by either brackets, parentheses, or both.

The range starts from the first integer ends at the second integer, inclusive if delimited by a bracket or exclusive if by parentheses. Multiple ranges, delimited by `U`, may be chained together, in which case duplicate elements are removed.

Input is a string in interval notation and output is a list of numbers contained in the specified interval. Only meaningful intervals are valid, so ranges may overlap, but the start will always be less than the end. Zero sized intervals should have an empty output. All integers in the interval must be displayed once and only once, but may be outputted in any particular order.

This is so the lowest byte count wins.

## Other Details

* Invalid inputs are undefined behavior
* a  or  symbol may be used instead of `U`
* The `U` will always be between ranges, never in front or behind
* If your language uses a character other than `-` to represent negative numbers that may be used instead

## Test Cases

```
[0,5] -> [0,1,2,3,4,5]
(0,5] -> [1,2,3,4,5]
[0,5) -> [0,1,2,3,4]
(0,5) -> [1,2,3,4]
[9,13] -> [9,10,11,12,13]
[-5,-1] -> [-5,-4,-3,-2,-1]
[-5,-1) -> [-5,-4,-3,-2]
(-5,-1] -> [-4,-3,-2,-1]
(-5,-1) -> [-4,-3,-2]
[-3,2] -> [-3,-2,-1,0,1,2]
[-3,2) -> [-3,-2,-1,0,1]
(-3,2] -> [-2,-1,0,1,2]
(-3,2) -> [-2,-1,0,1]
[0,0] -> [0]
(0,0] -> []
[0,0) -> []
(0,0) -> []
[1,2) -> [1]
(1,2) -> []
[-3,0)U(0,3] -> [-3,-2,-1,1,2,3]
[-3,0)U[0,3] -> [-3,-2,-1,0,1,2,3]
[-3,0]U[0,3] -> [-3,-2,-1,0,1,2,3]
[-3,0]U[2,5] -> [-3,-2,-1,0,2,3,4,5]
[1,5]U[2,4] -> [1,2,3,4,5]
[-5,-1]U[-6,-2] -> [-5,-4,-3,-2,-1,-6]
[-5,-1]U[-6,0] -> [-6,-5,-4,-3,-2,-1,0]
[-5,-1]U[-6,-2]U[-7,0] -> [-7,-6,-5,-4,-3,-2,-1,0]
[1,2)U[2,3)U[3,4)U[4,5) -> [1,2,3,4]
[2,1) -> Undefined
U(5,10) -> Undefined
[13,18)U -> Undefined

```

# Answer
> 8 votes
# Python 3, 79 bytes

```
lambda s:eval('{*range%s}'%s.translate({91:40,40:'(1+',93:'+1)',85:',*range'}))

```

Try it online!

-6 bytes thanks to ovs
-3 bytes thanks to dingledooper

# Answer
> 7 votes
# C++ (gcc), ~~139~~ ~~138~~ ~~134~~ ~~104~~ ~~101~~ 100 bytes

Uses C++20 features which aren't enabled by default in GCC, but are standard.

```
int f(auto&s,auto&o){int x,y;for(char c,d;s>>c>>x>>d>>y>>d;s>>d)for(y-=d<42;y>x-c%2;o.insert(y--));}

```

Try it online!

Uses streams because I wanted to simulate`>>`a`>>`merge`>>`conflict instead of writing top `%p`ercentage `printf`/`scanf` calls.

The input is an EOF terminated stream (I could adapt this to accept `'\n'` termination, though). It doesn't actually check the separator.

The output is stored into a `std::set<int>` reference. It must be empty when called.

Usage:

```
std::istringstream input{str};
std::set<int> output;
f(input, output);
// Output now contains the result

```

Ungolfed:

```
#include <set> // std::set
#include <iostream> // streams (abstracted with abbreviated templates)

// input: An EOF terminated std::basic_istream (e.g. std::istringstream)
// output: stored into a reference to a std::set<int>. Must be empty.
// Golfed code returns int, but doesn't actually return anything
void interpret_interval(std::basic_istream &input, std::set<int> &output)
{
    // Holders for our range
    int start, end;
    // read input
    for (char left, right, tmp /* overwrites left/right in golfed code */;
         // this will return false on EOF (or EOS)
         //       [       -1       ,      4      )
         input >> left >> start >> tmp >> end >> right;
         // discard U, sets EOF bit on end
         input >> tmp)
    {
         // done indirectly in the golfed code
         if (left == '[') // golf check: '(' == 40, '[' == 91, do a modulo 2
             start--; // one extra iteration
         if (right == ')') // golf check: ')' == 41, ']' == 93, less than 42
             end--; // one less iteration

         // Loop from end to start, inserting all the numbers in the
         // range to output.
         // XXX: std::iota? Doubt it would be smaller due to the include.
         for (; end > start; end--) {
             output.insert(end);
         }
    }
    // output now contains the set of values. Due to it being a std::set, all values
    // are unique. :)
}

```

# Answer
> 5 votes
# Jelly, ~~23~~ 22 bytes

```
ṣ”Uµṙ1“(Ḋ)Ṗ,r”yḟØ[V)FQ

```

Try it online!

-1 byte thanks to ovs

## How it works

```
ṣ”Uµṙ1“(Ḋ)Ṗ,r”yḟØ[V)FQ - Main link. Takes a string S on the left
ṣ”U                    - Split S on "U"
   µ               )   - Over each section R in the split S:
    ṙ1                 -   Rotate by once, shifting the first character to the end
      “(Ḋ)Ṗ,r”         -   Yield "(Ḋ)Ṗ,r"
              y        -   Transliterate; Replace "(" by "Ḋ", ")" by "Ṗ" and "," by "r"
                Ø[     -   Yield "[]"
               ḟ       -   Remove "[]"
                  V    -   Eval as Jelly code
                    F  - Flatten
                     Q - Deduplicate

```

### Why `r`,  and ?

As we only consider each individual range in the transliterate-then-eval stage, we'll just take a look at the four possible examples:

```
[0,5] -> 0r5
[0,5) -> 0r5Ṗ
(0,5] -> 0r5Ḋ
(0,5) -> 0r5ṖḊ

```

In Jelly, `r` in the infix inclusive range command, so `0r5 ⁼ [0,1,2,3,4,5]`.  is dequeue (i.e. remove first element) and  is pop (remove last element). So `r` generates the range, then we remove the first and/or last elements if necessary, creating exclusive ranges.

# Answer
> 2 votes
# Perl 5 `-MList::Util=uniq -FU`, 53 bytes

```
say for uniq map{($a,$b)=/-?\d+/g;$a+/\(/..$b-/\)/}@F

```

Try it online!

# Answer
> 2 votes
# Wolfram Language (Mathematica), 66 bytes

```
ToExpression[(#/.{"["->"Range[","("->"Range[1+",")"->"-1]"})<>""]&

```

Try it online!

Input a list of characters.

# Answer
> 2 votes
# Ruby `-nl`, 69 bytes

```
p eval"[*#{gsub /[(),U-\]]/,?(=>'1+',?)=>'-1',?,=>'..',?U=>',*'}]|[]"

```

Try it online!

# Answer
> 2 votes
# , 60 bytes

```
[:~.@;'U'<@([:({:+[:i.0>.-/)(']('={:,{.)+3 1".@;@{;:);._1@,]

```

Try it online!

* `'U' ...;._1@, ]` \- Prepend `'U',` to the input `]` and cut it using the first character `;._1`, ie `U`, as a delimiter, applying the verb defined by `...` to each piece. Now we'll breakdown what's in `...`:
* First we turn it into boxed words `;:`, so for example `'(_5,2]'` becomes:

```
┌─┬──┬─┬─┬─┐
│(│_5│,│2│]│
└─┴──┴─┴─┴─┘

```

and we take elements from indexes 3 and 1 `3 1 ... {` (the numbers) and unbox and convert then to ints `".@;@`. We take them in reverse order, right endpoint first, because it ends up saving bytes in a later step.
* `('](' = {: , {.) +` This adds an adjustment to each of the numbers, based on endpoint type. `{:,{.` returns the last and first character, and `](=` does an element-wise comparison, which will return 1 when equal, 0 otherwise. Thus the original input's right endpoint is incremented when it is `]`, and its left endpoint is incremented when it's `)`.
* `({: + [: i. 0 >. -/)` The adjusted, reversed endpoints are now passed to this phrase, which sticks a minus sign between them `-/`, and takes the maximum of that result and 0 `0 >.` (this is to account for the `(0,0)` case, which would otherwise return `_1`). We then generate the integers up to, but not including, that result `i.` and add the original input's adjusted left endpoint `{:` to all of them. We now have the correct range of numbers for a single range.
* `<@` And we box that up, to avoid fill when pieces of unioned input of different lengths are combined.
* `[: ~.@;` Finally we unbox the combined result to get a single list `;` and dedup it `~.@`.

# Answer
> 2 votes
# Jelly, 22 bytes

```
ṣ”UµØ(fOị⁾ṖḊvṖḊVr/Ʋ)ẎQ

```

A monadic Link accepting a list of characters which yields a list of integers.

**Try it online!** (Footer formats the resulting Jelly list as a Python list.)
Or see the test-suite.

### How?

```
ṣ”UµØ(fOị⁾ṖḊvṖḊVr/Ʋ)ẎQ - Link: list of characters, S
 ”U                    - literal character = 'U'
ṣ                      - split (S) at ('U's)
   µ               )   - for each part, P:
    Ø(                 -   literal list of characters = "()"
      f                -   filter keep (characters of P which are one of "()")
       O               -   to ordinals - i.e. '(' -> 40  and  ')' -> 41
         ⁾ṖḊ           -   literal list of characters "ṖḊ"
        ị              -   index into    ...      -> 'Ḋ'          -> 'Ṗ'
                  Ʋ    -   last four links as a monad, f(P):
             Ṗ         -     pop - i.e. remove ']' or ')' from the right of P)
              Ḋ        -     dequeue - i.e. remove '[' or '(' from the left of P)
               V       -     evaluate as Jelly code - e.g. "-4,2" becomes the list [-4,2]
                 /     -     reduce with:
                r      -       inclusive range            ...and then [-4,-3,-2,-1,0,1,2]
            v          -   evaluate (the string of "ṖḊ" characters)
                           as Jelly code with input (the inclusive range)
                    Ẏ  - tighten (to a single list)
                     Q - de-duplicate

```

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

Returns a set.

```
s=>s.replace(/(\[?)(-?\d+),(-?\d+)(]?)/g,(_,a,b,c,d)=>(g=_=>b>c-!d||g(S.add(b++)))(b-=-!a),S=new Set)&&S

```

Try it online!

### Commented

```
s =>                           // s = input sequence
s.replace(                     // match in s all occurrences of:
  /(\[?)(-?\d+),(-?\d+)(]?)/g, //   (\[?)   an optional opening bracket (a)
                               //   (-?\d+) a number preceded by an optional '-' (b)
                               //   ,       a comma
                               //   (-?\d+) another number in the same format (c)
                               //   (]?)    an optional closing bracket (d)
  (_, a, b, c, d) => (         //
    g = _ =>                   //   g is a recursive function ignoring its input
      b > c - !d ||            //     abort if b is greater than c, or greater than
                               //     c - 1 if d is not defined
        g(S.add(b++))          //     otherwise: add b to S, increment b and do a
                               //     recursive call
  )(b -= -!a),                 //   initial call to g; increment b if a is not defined
  S = new Set                  //   initialize S to a set
) && S                         // end of replace(); return S

```

# Answer
> 1 votes
# Charcoal, 46 bytes

```
ＦＥ⪪ＳU⪪ι,Ｆ…⁺ＩΦ§ι⁰λ№§ι⁰(⁺Ｉ⮌Φ⮌§ι¹λ№§ι¹]Ｆ¬№υκ⊞υκＩυ

```

Try it online! Link is to verbose version of code. Uses `U` as the union operator. Explanation:

```
ＦＥ⪪ＳU⪪ι,

```

Split the input on `U` and then split each part on `,` and loop over each pair of parts.

```
Ｆ…⁺ＩΦ§ι⁰λ№§ι⁰(⁺Ｉ⮌Φ⮌§ι¹λ№§ι¹]

```

Form a range from the integer in the first part (excluding the first character) and the integer in the second part (excluding the last character), except increment the first integer if the first part contains a `(` and increment the second integer if the second part contains a `]`, and loop over the range.

```
Ｆ¬№υκ⊞υκ

```

Push any new integers to the predefined empty list.

```
Ｉυ

```

Print all of the collected integers.

# Answer
> 1 votes
# Zsh, ~~89~~ 84 bytes

```
for i (${(s"U")1}){seq $[${${i%,*}#?}+1-#i&1] $[${${i#*,}%?}-!(##$i[-1]&4)]}|sort -u

```

Try it online!

# Answer
> 1 votes
# , 148 bytes

```
function(s)unique(unlist(lapply(parse(t=chartr("[],","():",gsub(",(-?\\d))",",(\\1-1))",gsub("\\((-?\\d)","((1+\\1)",el(strsplit(s,"U")))))),eval)))

```

Try it online!

If there's a shorter way, I can't seem to think of it.

# Answer
> 1 votes
# PowerShell, 137 133 bytes

-4 bytes thanks to Mazzy, who has an even cooler PS solution to this challenge!

```
$r="'|% rep* '"
"'('+('$args$r(','[1+$r)','-1]$r]','))$r[','(($r,' '),($r`U' ',')+',0)'"|iex|iex|%{$l,$n=$_;$l..$n*($n-ge$l)}|sort -u

```

Try it online!

# Answer
> 1 votes
# PowerShell for Windows, ~~133~~ 114 bytes

```
$(switch -r($args){'\('{$l++}','{$l+=+$n}'\)'{$n-=1}'\)|]'{$l..$n*($l-le$n)
$l=0}\D{$n=''}'\d|-'{$n+=$_}})|sort -u

```

Try it online!

Less golfed:

```
$numbers = switch -Regex ($args){
    '\('    {$left++}
    ','     {$left+=+$num}
    '\)'    {$num-=1}
    '\)|]'  {$left..$num*($left -le $num);$left=0}
    '\D'    {$num=''}
    '\d|-'  {$num+=$_}
}
$numbers|sort -u

```

# Answer
> 1 votes
# QuadR, 40 bytes

Uses  and `¯` instead of `U` and `-`

```
⍎⍵
\[
\(
,
\)
]
(
(1↓
{⍺+0,⍳0⌈⍵-⍺}
-1)
)

```

Try it online or try them all!

Execute () it () after simple transliteration to APL:

| In | Out | Explanation |
| --- | --- | --- |
| `[` | `(` | Open group |
| `(` | `(1↓` | Open group but with first element (the start) removed |
| `,` | `{⍺+0,⍳0⌈⍵-⍺}` | Anonymous infix lambda to compute range (see below) |
| `)` | `-1)` | Close group but subtract one from the end |
| `]` | `)` | Close group |

The "try them all" link also replaces `\n` with APL's statement separator , and runs in **D**ocument mode.

### The infix range lambda `{⍺+0,⍳0⌈⍵-⍺}`

`{``}` "dfn"; left and right arguments are  and :

`⍵-⍺` difference

`0⌈` maximum of zero and that; nulls negative differences like `[3,3)``(3``3-1)`

**ɩ**ndices one through that

`0,` prepend zero

`⍺+` add start point to all of those

# Answer
> 0 votes
# Haskell, 194 180 bytes

```
import Data.List
a=init
l=drop 1
t""=[]
t c=nub$i v++t(l n)where(v,n)=span(/='U')c
i('(':c)=l$i('[':c)
i c|last c==')'=a$i$a c++"]"|1<2=f$span(/=',')c
f(_:o,_:w)=[read$o..read$a w]

```

Try it online!

# Answer
> 0 votes
# APL (Dyalog Unicode), ~~107~~ 62 bytes

```
⍎'\]' '\[' ',' '\(' '\)'⎕R')' '(' '{⍺+⍳0⌈1+⍵-⍺}' '(1↓' '-1)'⊢⎕

```

Try it online!

Does a huge regex replacement and then executes the string.

uses  and `¯` for input.

Uses `⎕IO←0` (0-indexing)

-45 bytes by stealing a ton from Adám's QuadR answer(It has a well-written explanation, go upvote it!).

# Answer
> 0 votes
# 05AB1E, 28 bytes

```
'U¡ε¦¨',¡ŸÙy„()©Ã®"¦¨"‡.V}˜ê

```

Try it online or verify all test cases.

**Explanation:**

```
'U¡              '# Split the (implicit) input-string on "U"
   ε              # Map over each interval:
    ¦¨            #  Remove the first and last characters (the "[]()")
      ',¡        '#  Split on ","
         Ÿ        #  Transform that pair of integers into a ranged list
          Ù       #  And uniquify it
                  #  (if a==b in [a,b], it will result in pair [a,a] instead of [a])
    y             #  Push the interval-string we're mapping over again
     „()          #  Push string "()"
        ©         #  Store it in variable `®` (without popping)
         Ã        #  Keep only the "()" in the interval-string (if any)
     ®            #  Push "()" from variable `®` again
      "¦¨"        #  Push "¦¨"
          ‡       #  Transliterate "(" to "¦" and ")" to "¨"
           .V     #  Evaluate and execute it as 05AB1E code:
                  #   `¦`: Remove the first value from the list
                  #   `¨`: Remove the last value from the list
   }˜             # After the map: flatten the list of lists
     ê            # And sort and uniquify the values
                  # (after which the result is output implicitly)

```

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


title: Fill in the grid randomly

text:
# Question
Title: Fill in the grid randomly
Given positive integer `n < 10`, create a 2 dimensional matrix where each location is filled with its `x` and `y` index (starting from the top left).

For example:

Input: 2

```
00 10
10 11

```

Input: 3

```
00 10 20
01 11 21
02 12 22

```

Once the grid is created, randomly fill each index. This can be with an 'x' or any other way to denote a spot has been filled.

You determine which location to fill by randomly generating indices to fill the matrix. You can only fill n^2 times so you cannot fill as many times as you want until the matrix is completely filled. At the end the matrix must be filled so you must do some work to make sure that you check the random numbers that you use to fill to make sure that spot is not already filled.

Refresh or print after each fill in order to show the progression of the filling iterations.

Example for filling:

Input: 2

```
00 10
01 11

```

`00` is randomly chosen:

```
XX 10
01 11

```

`01` is randomly chosen:

```
XX 10
XX 11

```

`00` is randomly chosen, but since it's already been chosen a re-roll chooses `10`:

```
XX XX
XX 11

```

`11` is randomly chosen:

```
XX XX
XX XX

```

Do not print out the random numbers as visually I should be able to see which index was selected. By this I mean do not print "`11` is randomly chosen:". It is here for exploratory sake.

Since this is code-golf The shortest code wins.

Have fun and happy golfing!

# Answer
# 05AB1E, 29 bytes

```
<ÝDâJU[X¹ä»,XÐÙg#Jþ2ô.R„  :)U

```

Try it online!

Space chosen as the char for the removed numbers (as it looks nice), but it could be replaced with any char without affecting byte-count.

**Explanation**

```
                                # implicit input n
<ÝDâ                            # cartesian product of [0..n-1] and [0..n-1]
    JU                          # join pairs and store in X
      [     XÐÙg#               # loop until there's only spaces left in X
       X¹ä                      # split X into n pieces
          »,                    # join rows by space and columns by newlines and print
                 Jþ             # join X to string and remove all non-digits
                   2ô.R         # split in pieces of 2 and pick a pair at random
                       „  :)    # replace this pair with 2 spaces
                            U   # and store in X

```
> 5 votes

# Answer
## Pip, ~~41~~ ~~40~~ ~~38~~ 36 bytes

35 bytes of code, +1 for the `-S` flag.

```
Pm:J_MM ZCGa{ST:mmR:asX2}M$ALmSK{r}

```

Takes input from cmdline argument. Replaces with space (any other character is possible for +1 byte). Outputs successive iterations separated by a single newline (which is legal but can make it a bit hard to read). Try it online!

~~All kinds of dirty tricks in this one.~~ Shorter version has fewer dirty tricks. :^( Explanation:

```
Pm:J_MM ZCGa{ST:mmR:asX2}M$ALmSK{r}
                                     -S flag means nested lists are delimited first
                                       by newlines then by spaces when stringified/printed
           a                         1st cmdline arg
         CG                          Coordinate Grid, a list of lists of coord pairs
        Z                            Zip (transposes so it's x,y instead of row,col)
   J_                                Function that takes a list and joins all items
     MM                              MapMap: map this function to each sublist
                                       This joins a coord pair [1;0] into a string "10"
 Pm:                                 Assign the result to m and print it

                          $ALm       Fold m on Append List: appends all sublists of m
                                       together, making a single list of coord pairs
                              SK     Sort with the following function as key:
                                {r}  Return a random number
                                     We now have a randomly-ordered list of all the
                                       coord pairs from m

            {           }M           Map this function to that list:
             ST:m                    Convert m to string in-place
                 mR:                 Replace (in-place)...
                    a                  the argument (a coord pair)...
                     sX2               ... with two spaces
                                     The map operation returns a list of strings, one for
                                       each step of the process, which are autoprinted
                                       (separated by newlines)

```
> 3 votes

# Answer
# Groovy (202 Bytes)

```
{a->b=new String[a][a];while(b.flatten().flatten().contains(null)){b[(int)(Math.random()*a)][(int)(Math.random()*a)]="XX";b.eachWithIndex{e,i->e.eachWithIndex{f,j->print f?"XX ":"${i}${j} "}println()}}}

```

That specific output format really messed up my byte count, but meh.
Try it out: https://groovyconsole.appspot.com/edit/5171951567896576 (+9 bytes for a prettier print)

## Ungolfed:

```
y={a->
    b=new String[a][a];
    while(b.flatten().flatten().contains(null)) {
        b[(int)(Math.random()*a)][(int)(Math.random()*a)]="XX";
        b.eachWithIndex{
            e,i->
            e.eachWithIndex{
                f,j->
                print f ? "XX ": "${i}${j} "
            }
            println()
        }
    }
}
y(4)

```

## Output Example:

```
00 01 02 XX
10 11 12 13
20 21 22 23
30 31 32 33
00 01 02 XX
XX 11 12 13
20 21 22 23
30 31 32 33
XX 01 02 XX
XX 11 12 13
20 21 22 23
30 31 32 33
XX 01 XX XX
XX 11 12 13
20 21 22 23
30 31 32 33
XX 01 XX XX
XX 11 12 XX
20 21 22 23
30 31 32 33
XX 01 XX XX
XX 11 12 XX
XX 21 22 23
30 31 32 33
XX 01 XX XX
XX 11 XX XX
XX 21 22 23
30 31 32 33
XX 01 XX XX
XX XX XX XX
XX 21 22 23
30 31 32 33
XX XX XX XX
XX XX XX XX
XX 21 22 23
30 31 32 33
XX XX XX XX
XX XX XX XX
XX 21 22 23
30 31 32 33
XX XX XX XX
XX XX XX XX
XX 21 22 23
XX 31 32 33
XX XX XX XX
XX XX XX XX
XX 21 22 23
XX 31 32 33
XX XX XX XX
XX XX XX XX
XX 21 22 23
XX 31 32 33
XX XX XX XX
XX XX XX XX
XX 21 22 23
XX 31 32 33
XX XX XX XX
XX XX XX XX
XX 21 22 23
XX 31 32 33
XX XX XX XX
XX XX XX XX
XX 21 22 23
XX 31 32 33
XX XX XX XX
XX XX XX XX
XX 21 22 23
XX 31 32 33
XX XX XX XX
XX XX XX XX
XX 21 22 23
XX 31 32 33
XX XX XX XX
XX XX XX XX
XX 21 22 XX
XX 31 32 33
XX XX XX XX
XX XX XX XX
XX 21 22 XX
XX 31 32 33
XX XX XX XX
XX XX XX XX
XX 21 22 XX
XX 31 32 33
XX XX XX XX
XX XX XX XX
XX 21 22 XX
XX 31 32 XX
XX XX XX XX
XX XX XX XX
XX XX 22 XX
XX 31 32 XX
XX XX XX XX
XX XX XX XX
XX XX 22 XX
XX 31 32 XX
XX XX XX XX
XX XX XX XX
XX XX 22 XX
XX 31 32 XX
XX XX XX XX
XX XX XX XX
XX XX 22 XX
XX 31 32 XX
XX XX XX XX
XX XX XX XX
XX XX 22 XX
XX 31 32 XX
XX XX XX XX
XX XX XX XX
XX XX 22 XX
XX 31 32 XX
XX XX XX XX
XX XX XX XX
XX XX 22 XX
XX 31 32 XX
XX XX XX XX
XX XX XX XX
XX XX 22 XX
XX 31 32 XX
XX XX XX XX
XX XX XX XX
XX XX 22 XX
XX 31 32 XX
XX XX XX XX
XX XX XX XX
XX XX 22 XX
XX 31 32 XX
XX XX XX XX
XX XX XX XX
XX XX 22 XX
XX 31 32 XX
XX XX XX XX
XX XX XX XX
XX XX 22 XX
XX XX 32 XX
XX XX XX XX
XX XX XX XX
XX XX 22 XX
XX XX 32 XX
XX XX XX XX
XX XX XX XX
XX XX 22 XX
XX XX 32 XX
XX XX XX XX
XX XX XX XX
XX XX 22 XX
XX XX 32 XX
XX XX XX XX
XX XX XX XX
XX XX 22 XX
XX XX 32 XX
XX XX XX XX
XX XX XX XX
XX XX 22 XX
XX XX 32 XX
XX XX XX XX
XX XX XX XX
XX XX 22 XX
XX XX 32 XX
XX XX XX XX
XX XX XX XX
XX XX 22 XX
XX XX 32 XX
XX XX XX XX
XX XX XX XX
XX XX 22 XX
XX XX 32 XX
XX XX XX XX
XX XX XX XX
XX XX 22 XX
XX XX 32 XX
XX XX XX XX
XX XX XX XX
XX XX 22 XX
XX XX 32 XX
XX XX XX XX
XX XX XX XX
XX XX 22 XX
XX XX 32 XX
XX XX XX XX
XX XX XX XX
XX XX 22 XX
XX XX 32 XX
XX XX XX XX
XX XX XX XX
XX XX 22 XX
XX XX 32 XX
XX XX XX XX
XX XX XX XX
XX XX 22 XX
XX XX XX XX
XX XX XX XX
XX XX XX XX
XX XX 22 XX
XX XX XX XX
XX XX XX XX
XX XX XX XX
XX XX 22 XX
XX XX XX XX
XX XX XX XX
XX XX XX XX
XX XX 22 XX
XX XX XX XX
XX XX XX XX
XX XX XX XX
XX XX 22 XX
XX XX XX XX
XX XX XX XX
XX XX XX XX
XX XX 22 XX
XX XX XX XX
XX XX XX XX
XX XX XX XX
XX XX 22 XX
XX XX XX XX
XX XX XX XX
XX XX XX XX
XX XX 22 XX
XX XX XX XX
XX XX XX XX
XX XX XX XX
XX XX XX XX
XX XX XX XX

```
> 2 votes

# Answer
# R, ~~84~~ ~~81~~ 74 bytes

Now uses one-indexing rather than zero-indexing. Got rid of 7 bytes thanks to @Billywob.

```
N=scan()
m=outer(1:N,1:N,paste0)
for(i in sample(N^2)){m[i]="XX";print(m)}

```

Example output for N=3

```
     [,1] [,2] [,3]
[1,] "11" "12" "XX"
[2,] "21" "22" "23"
[3,] "31" "32" "33"
     [,1] [,2] [,3]
[1,] "11" "12" "XX"
[2,] "21" "22" "23"
[3,] "31" "XX" "33"
     [,1] [,2] [,3]
[1,] "11" "12" "XX"
[2,] "XX" "22" "23"
[3,] "31" "XX" "33"
     [,1] [,2] [,3]
[1,] "11" "XX" "XX"
[2,] "XX" "22" "23"
[3,] "31" "XX" "33"
     [,1] [,2] [,3]
[1,] "XX" "XX" "XX"
[2,] "XX" "22" "23"
[3,] "31" "XX" "33"
     [,1] [,2] [,3]
[1,] "XX" "XX" "XX"
[2,] "XX" "22" "23"
[3,] "XX" "XX" "33"
     [,1] [,2] [,3]
[1,] "XX" "XX" "XX"
[2,] "XX" "XX" "23"
[3,] "XX" "XX" "33"
     [,1] [,2] [,3]
[1,] "XX" "XX" "XX"
[2,] "XX" "XX" "XX"
[3,] "XX" "XX" "33"
     [,1] [,2] [,3]
[1,] "XX" "XX" "XX"
[2,] "XX" "XX" "XX"
[3,] "XX" "XX" "XX"

```
> 1 votes

# Answer
## AWK, 229 bytes

```
func p(a){for(k=1;k<=m;k++){if(k==a)gsub("[0-9]","X",M[k])
printf"%s",M[k]}}{n=$1;m=n*n
k=1
for(i=0;i<n;i++)for(j=0;j<n;j++){s=k%n==0?k==m?"\n\n":"\n":" "
M[k++]=i j s}p()
for(;z<m;z++){do{y=int(rand()*m+1)}while(M[y]~"X")p(y)}}

```

I added a few bytes to give the output a space between each matrix.

Note: to make it more 'random' between runs, a call to `srand()` could be added for 7 additional bytes.

Usage and output after storing above code in `FILE`:

```
    awk -f FILE <<< 2

00 01
10 11

XX 01
10 11

XX XX
10 11

XX XX
10 XX

XX XX
XX XX

```
> 0 votes

# Answer
# PHP, 172 Bytes

```
for(;$x<$s=($a=$argv[1])*$a;)$r[]=$x%$a.($x++/$a^0);echo($c=chunk_split)(join(" ",$r),$a*3);for(;$q<$s;){if($r[$z=rand(0,$s-1)]<X)++$q&$r[$z]=XX;echo$c(join(" ",$r),$a*3);}

```

Breakdown

```
for(;$x<$s=($a=$argv[1])*$a;)$r[]=$x%$a.($x++/$a^0); #make the array
echo($c=chunk_split)(join(" ",$r),$a*3); # Output array
for(;$q<$s;)
{
  if($r[$z=rand(0,$s-1)]<X)++$q&$r[$z]=XX; #fill position if it is not XX and raise increment
  echo$c(join(" ",$r),$a*3); #Output array
}

```
> 0 votes

# Answer
# Python 2, 190 bytes

```
from random import *
R=range(input())
G=[(x,y)for x in R for y in R]
def f():print"\n".join(" ".join(["XX","%d%d"%(x,y)][(x,y) in G]for x in R)for y in R)
f()
while G:G.remove(choice(G));f()

```
> 0 votes

# Answer
# APL (Dyalog Unicode), 30 bytes

```
↑{'×'@⍵⊢x}¨,\⊂¨y[?⍨≢y←,x←⍳2/⎕]

```

Try it online!

Uses `⎕IO←0` (0-indexing)

Uses the `×` symbol for replacement, in a grid of co-ordinate pairs.

## Explanation

```
↑{'×'@⍵⊢x}¨,\⊂¨y[?⍨≢y←,x←⍳2/⎕]
                            ⎕  get the input n
                         ⍳2/   create an n×n coordinate grid
                       x←      store in x
                    y←,        convert to a list, and store in y
                 ?⍨≢           get indexes for shuffling the list
               y[            ] and get a random permutation of y
             ⊂¨                wrap each list
           ,\                  and get it's array prefixes
 {       }¨                    for each prefix:
  '×'@⍵⊢x                      place an '×' at those coordinates in the grid x
↑                              align all the grids into a matrix

```
> 0 votes

# Answer
# 05AB1E, 18 (or 17 or 19?) bytes

```
L<ãíJD.rĆvDIô,yðº:

```

Try it online.

The program above outputs each matrix on a separated line. If these matrices have to be pretty-printed, a `»` can be added before the `,`: try it online. (Using the exact output format as the challenge description is 22 bytes: try it online.)

If we're allowed to output with 1-based indexing instead of 0-based, the `<` can be dropped for -1 byte: try it online.

**Explanation:**

```
L                   # Push a list in the range [1, (implicit) input]
 <                  # Optional: decrease each by 1 to change the range to [0, input)
  ã                 # Create all possible pairs of this list
   í                # Reverse each pair
    J               # Join each pair together to a single 2-digit string
     D              # Duplicate this list
      .r            # Pop and shuffle this copy
        Ć           # Enclose, appending it's own head
                    # (this is so the final iteration will print the empty matrix)
         v          # Loop `y` over each index in the shuffled list:
          D         #  Triplicate the unshuffled matrix
           Iô       #  Pop one copy, and split it into parts equal to the input
             »      #  Optional: join each inner list by spaces, and then each string by newlines
              ,     #  Pop and print this matrix with trailing newline
               y    #  Push the current random index
                ðº  #  Push a space, and mirror it to two spaces: "  "
                  : #  Replace the index in the list with these double spaces

```
> 0 votes

---
Tags: code-golf, ascii-art, random, matrix
---


title: Tic-Tac-Toe - X or O?

text:
# Question
Title: Tic-Tac-Toe - X or O?
# Background

Skip to "Task" if you are familiar with Tic-Tac-Toe (I think most are!)

Tic-Tac-Toe is a famous two-player game. It consists of a **3x3** board that is filled gradually by two players (clarifications below); The first player uses the character `X` and the other one uses `O`. The winner is the first to get 3 consecutive and identical characters (`X` or `O`), either horizontally, vertically or diagonally. In case the board is filled and none of the players managed to get three consecutive characters as decribed above, the game ends in a tie. Note that there might be empty spots at the end of the game, in case either of the players wins in less than 9 moves in total (this cannot happen in case of a tie).

# Task

Given a Tic-Tac-Toe board at the end of a game (in the form of a string, a matrix, a flat list of 9 ordered values, any other decent format), determine who wins the game.

* The input will consist of distinct and *consistent* values, one for `X`, one for `O` and another one that represents an empty spot.
* Your program should be able to output 3 distinct, consistent and non-empty values: one in case `X` wins, another one in case `O` wins or another if the players are tied.

Please specify these values in your answer. You can assume that the input will be a valid Tic-Tac-Toe board.

# Test Cases

`X`, `O`, `_` are the input values here; `X wins`, `O wins` and `Tie` are for the output.

```
X O X
O X _
O _ X

```

Output: `X wins`.

```
X _ O
X O _
X O X

```

Output: `X wins`.

```
X O X
_ O X
_ O _

```

Output: `O wins`.

```
X O X
O O X
X X O

```

Output: `Tie`.

---

As usual, all our standard rules apply. This is , the shortest code in bytes in every language wins!

# Answer
> 8 votes
# Jelly,  ~~16 15~~  14 bytes

```
U,Z;ŒD$€ẎḄỊÐḟḢ

```

A monadic link accepting a list of lists (the rows - or columns) with the values:

```
X = 0.155; O = -0.155; _ = 0

```

Returning results:

```
X wins = 1.085; O wins = -1.085; Tie = 0

```

Note: using a value of zero for `_`, and equal but opposite values for `X` and `O`, this value (here `0.155`) may be in the range `(1/6, 1/7)` (exclusive at both ends) - I only chose a value in that range that gave a precisely representable floating point result for the win cases.

**Try it online!**

### How?

```
U,Z;ŒD$€ẎḄỊÐḟḢ - Link: list of lists (as described above)
U              - upend (reverse each row)
  Z            - transpose (get the columns)
 ,             - pair the two
      $€       - last two links as a monad for each of them:
    ŒD         -   diagonals (leading diagonals - notes: 1. only one is of length 3;
               -              2. the upend means we get the anti-diagonals too)
   ;           -   concatenate (with the rows/columns)
        Ẏ      - tighten (make a single list of all the rows, columns and diagonals)
         Ḅ     - from binary (vectorises) (note that [0.155, 0.155, 0.155]
               -                           converts to 4*0.155+2*0.155+1*0.155 = 1.085
               -                           and [-0.155, -0.155, -0.155]
               -                           converts to 4*-0.155+2*-0.155+1*-0.155 = -1.085
               -                           while shorter lists or those of length three
               -                           with any other mixtures of 0.155, -0.155 and 0
               -                           yield results between -1 and 1
               -                           e.g. [.155,.155,0] -> 0.93)
           Ðḟ  - filter discard if:
          Ị    -   insignificant (if abs(z) <= 1) (discards all non-winning results)
             Ḣ - head (yields the first value from the list or zero if it's empty)

```

# Answer
> 6 votes
# Javascript (ES6), ~~103~~ 87 bytes

```
a=>"012+345+678+036+147+258+048+246T".replace(/\d/g,n=>a[n]||!1).match(/(\d)\1\1|T/)[0]

```

## Input

* X is represented as `1`
* O is represented as `2`
* _ is represented as `0`

## Output

* X wins is represented as `"111"`
* O wins is represented as `"000"`
* Tie is represented as `"T"`

## Explanation

```
a=>
    "012+345+678+036+147+258+048+246" // List of indexes for each row
    .replace(/\d/g,n=>a[n]||!1)       // Replace all digits with the value of the cell
    .match(/(\d)\1\1|$/)[0]           // Find the first row filled with the same value

```

## Test cases

```
f=
a=>"012+345+678+036+147+258+048+246T".replace(/\d/g,n=>a[n]||!1).match(/(\d)\1\1|T/)[0]
console.log(f([1,2,1,2,1,0,2,0,1]))
console.log(f([1,0,2,1,2,0,1,2,1]))
console.log(f([1,2,1,0,2,1,0,2,0]))
console.log(f([1,2,1,2,2,1,1,1,2]))
```

# Answer
> 4 votes
# Jelly, 18 bytes

```
UŒD;;Z;ŒDµSA⁼3µÐfḢ

```

Try it online!

`X` = `1`, `O` = `-1`, `_` = `0`
X wins = `[1, 1, 1]`, O wins = `[-1, -1, -1]`, Tie = `0`
Input as list of 3 lists of 3 elements in `(1, -1, 0)` each.

# Answer
> 4 votes
# PHP, 70 bytes

```
for($c=95024101938;${${$i++&7}.=$argn[$c%9]}=1<$c/=3;);echo$XXX-$OOO;

```

Assumes `-n` (interpreter defaults). Additionally requires `-R` (execute `<code>` for every line of input), counted as one.

Input is taken on a single line (exactly as in the problem description, except with all whitespace removed).

Output is the following: `1` → X Wins, `-1` → O Wins, `0` → Tie .

Try it online!

# Answer
> 4 votes
## Perl 5, 58 bytes

**56 bytes code + 2 fpr `-p0`.**

```
$_=eval sprintf'/(.)(.{%s}\1){2}/s||'x4 .'0?$1:T',0,2..4

```

Try it online!

Outputs `X` and `O` for wins, or `T` for a tie. Includes a bunch of header/footer code to test all at once.

---

## Alternative, 58 bytes

```
$}.="/(.)(.{$_}\\1){2}/s||"for 0,2..4;$_=eval$}.'0?$1:T'

```

Try it online!

# Answer
> 3 votes
# Python 3, 73 bytes

```
lambda b:{'XXX','OOO'}&{*b.split(),b[::4],b[1::4],b[2::4],b[::5],b[2::3]}

```

Try it online!

---

# Python 2, ~~100~~ ~~95~~ ~~92~~ ~~87~~ ~~82~~ 77 bytes

```
lambda b:{'XXX','OOO'}&set(b.split()+[b[::4],b[1::4],b[2::4],b[::5],b[2::3]])

```

Try it online!

---

Takes input as a newline separated string of `XO_`

Outputs:

* `{'XXX'}` for `X`,
* `{'OOO'}` for `O`
* `{}` for a tie

Works by slicing the string into rows columns and diagonals:

```
The board:
    1 2 3
    4 5 6
    7 8 9
which is '123\n456\n789' is sliced into:

['123', '456', '789', '147', '258', '369', '159', '357']
rows: b.split() -> ['123', '456', '789']
cols: [b[::4],b[1::4],b[2::4]] -> ['147', '258', '369']
diag: [b[::5],b[2::3]] -> ['159', '357']

```

then `'XXX'` and `'OOO'` are checked against the slices.

Takes input as a newline separated string of `XO_`

Outputs:

* `{'XXX'}` for `X`,
* `{'OOO'}` for `O`
* `{}` for a tie

Works by slicing the string into rows columns and diagonals:

```
The board:
    1 2 3
    4 5 6
    7 8 9
which is '123\n456\n789' is sliced into:

['123', '456', '789', '147', '258', '369', '159', '357']
rows: b.split() -> ['123', '456', '789']
cols: [b[::4],b[1::4],b[2::4]] -> ['147', '258', '369']
diag: [b[::5],b[2::3]] -> ['159', '357']

```

then `'XXX'` and `'OOO'` are checked against the slices.

# Answer
> 3 votes
# R, ~~118~~ ~~116~~ 115 bytes

Thanks to @user2390246 for two extra bytes.

```
function(M,b=table,u=unlist(c(apply(M,1,b),apply(M,2,b),b(diag(M)),b(M[2*1:3+1]))))`if`(any(u>2),names(u[u>2]),"T")

```

Slightly ungolfed:

```
function(M){
    u=unlist(c(apply(M,1,table), #Contingency table of the rows
             apply(M,2,table), #of the columns
             table(diag(M)), #of the diagonal
             table(M[2*1:3+1]))) #of the opposite diagonal
    `if`(any(u>2),names(u[u>2]),"T") #Give name of element that occurs more than twice in any setting
 }

```

Returns `X` if X wins, `O` if O wins and `T` in case of a tie.

Try it online!

# Answer
> 3 votes
# APL (Dyalog Extended), ~~26~~ 21 bytes

```
⌈/1 1(∨⌿⍉∘⌽,⍉,⍉⍤⊢,⊢)⊢

```

Try it online!

Algorithm taken from the J answer, and verify a magic square.

-5 bytes from Adám.

Takes input as a 3x3 integer matrix where:

1 → blank, 2 → X, 3 → O.

returns the appropriate integer for X and O, 1 if it's a tie.

## Explanation

```
{⌈/∨⌿(1 1∘⍉∘⌽,1 1∘⍉,⍉,⊢)⍵} ⍵ → input
     (                 )⍵  pass ⍵ to inner fn:
                      ⊢    return matrix containing argument,
                    ⍉,     argument transposed,
              1 1∘⍉,       it's main diagonal,
      1 1∘⍉∘⌽,             and the main diagonal of it's reverse.
   ∨⌿(                 )   take GCD of each column of the resultant matrix
 ⌈/                        take the maximum of that

```

# Answer
> 2 votes
# Python 3, 173 bytes

```
lambda x:h(x,1)*2or+h(x,0)
h=lambda x,y:g(x,y)or g(zip(*x),y)or x[0][0]==x[1][1]==x[2][2]==y or x[0][2]==x[1][1]==x[2][0]==y
g=lambda x,y:any(all(e==y for e in r)for r in x)

```

Try it online!

* Input as a matrix of `1 == X, 0 == O, -1 == _`
* Output as a single value: `2 == X, 1 == O, 0 == TIE`

-8 bytes thanks to Erik the Outgolfer

# Answer
> 2 votes
# Python 2, ~~124~~ ~~118~~ ~~117~~ 115 bytes

* Saved six bytes thanks to Erik the Outgolfer; using a string to avoid commata.
* Saved one byte thanks to Mr. Xcoder; golfing `[j*3:j*3+3]` to `[j*3:][:3]`.
* Saved two bytes by using a magic number to compress the string.

```
def T(B):
 for j in range(8):
	a,b,c=map(int,`0x197bf3c88b2586f4bef6`[j*3:][:3])
	if B[a]==B[b]==B[c]>0:return B[a]

```

Try it online!

### Input / Output values

* `X` is represented as `1`
* `O` is represented as `2`
* `_` is represented as `None`

# Answer
> 2 votes
# Java 8, ~~112~~ ~~108~~ ~~106~~ ~~104~~ ~~90~~ ~~102~~ 93 bytes

```
b->b.replaceAll(".*(X|O)(\\1|...\\1...|.{4}\\1.{4}|..\\1..)\\1.*","$1").replaceAll("..+","T")

```

+12 bytes (90 → 102) due to bug-fix of only checking one diagonal instead of both..
-9 bytes (102 → 93) by using `replaceAll` instead of `matches`.

Input in the format `XOX OX_ O_X`, output `X`, `O` or `T`.

**Explanation:**

Try it here.

```
b->{                   // Method with String as both parameter and return-type
  b.replaceAll(".*(X|O)(\\1|...\\1...|.{4}\\1.{4}|..\\1..)\\1.*",
                       //  If we found a line of X or O:
     "$1")             //   Replace it with either X or O
   .replaceAll("..+",  //  If there are now more than 2 characters left:
     "T")              //   Replace it with T
                       // End of method (implicit / single-line return-statement)

```

Explanation regex:

```
.*(X|O)(\1|...\1...|.{4}\1.{4}|..\1..)\1.*
.*                                      .*# 0 or more trailing & leading chars
  (X|O)                               \1  # X or O next to those leading/trailing chars
       (\1                                # A single X or O in between (row found)
          |...\1...                       # 3 chars, X or O, 3 chars (column found)
                   |.{4}\1.{4}            # 4 chars, X or O, 4 chars (diagonal TL→BR found)
                              |..\1..)    # 2 chars, X or O, 2 chars (diagonal TR→BL found)

```

# Answer
> 2 votes
# Retina, 51 bytes

```
.*(X|O)(\1|...\1...|.{4}\1.{4}|..\1..)\1.*
$1
..+
T

```

Port of my Java 8 answer. Input in the format `XOX OX_ O_X`, output `X`, `O` or `T`.

**Explanation:**

Try it here.

```
.*(X|O)(\1|...\1...|.{4}\1.{4}|..\1..)\1.*
.*                                      .*# 0 or more trailing & leading chars
  (X|O)                               \1  # X or O next to those leading/trailing chars
       (\1                                # A single X or O in between (row found)
          |...\1...                       # 3 chars, X or O, 3 chars (column found)
                   |.{4}\1.{4}            # 4 chars, X or O, 4 chars (diagonal TL→BR found)
                              |..\1..)    # 2 chars, X or O, 2 chars (diagonal TR→BL found)

$1                                        #  Replace match of above with either X or O

..+                                       # If there are now 2 or more characters left:
T                                         #  Replace everything with T

```

# Answer
> 1 votes
# Retina, 49 bytes

```
;
;;
.*(\w)(.)*\1(?<-2>.)*(?(2)(?!))\1.*
$1
..+
T

```

Try it online! Takes input as an 11-character string of 9 `X`s, `O`s or `-`s in three groups of three separated by `;`s, although the link includes a header which translates the given test cases to this format. Works by matching a winning line directly using a balancing group to ensure that the three matching characters are equidistant. (Suitable distances are 0 (horizontal line), 4 (reverse diagonal), 5 (vertical line), or 6 (diagonal); other distances would hit a `;` or extend outside the string.)

# Answer
> 1 votes
# Retina, 127 bytes

```
.*(X|O)\1\1.*
$1
(X|O).. \1.. \1..
$1
.(X|O). .\1. .\1.
$1
..(X|O) ..\1 ..\1
$1
(X|O).. .\1. ..\1
$1
..(X|O) .\1. \1..
$1
..+
_

```

Try it online!

...I guess you could call this brute force... Thought there might be some merit to it...

# Answer
> 1 votes
# J, 34 bytes

```
[:>./[:+./"1(2 1 0},:0 1 2}),(,|:)

```

Ungolfed:

```
[: >./ [: +./"1 (2 1 0} ,: 0 1 2}) , (, |:)

```

## Explanation

Encoding:

```
X = 2
O = 3
_ = 1

```

Our high-level strategy is first to create a matrix each of whose rows is a possible win. Row one is diagonal /, row 2 is diagonal \\, the next three rows are the rows, and the final three rows are the columns. This part is accomplished by the phrase (using Item Amend `}`):

```
(2 1 0},:0 1 2}),(,|:)

```

Finally we take the GCD of each row:

```
+./"1

```

Thanks to our encoding, any row with a blank will have a GCD of 1, as will any row that contains any mix of Xs and Os, because 2 and 3 are coprime. So all we need to do next is find the maximum element: `>./`

If the game is a tie, it will be 1. If a player wins, it will be that player's number.

Try it online!

# Answer
> 0 votes
# JavaScript, 66 bytes

```
([a,b,c,d,e,f,g,h,i])=>e&(a&i|c&g|b&h|d&f)|a&(b&c|d&g)|i&(c&f|g&h)

```

Keeping it simple.

* Input: A string, or array of numbers or strings, with `0` corresponding to a blank space, `1` an X, and `2` an O.
* Output: `0` for a tie, `1` for X victory, `2` for O victory.

Expanded, lightly commented:

```
( [a,b,c,d,e,f,g,h,i] ) => // Break apart the input into nine variables w/ destructuring
  // Run through all possible win conditions. 1&1&1 -> 1, 2&2&2 -> 2
  e & (             // All victories involving the middle square
    a & i | c & g | // Diagonal lines
    b & h | d & f   // Vertical/horizontal through the middle
  ) |
  a & ( b & c | d & g ) | // Victories with the top-left square
  i & ( c & f | g & h )   // Victories with the bottom-right square

```

# Answer
> 0 votes
# 05AB1E, 14 bytes

```
ø«IÅ\ªIÅ/ª€êéн

```

Input as a 3x3 matrix of integers: `X=1`, `O=-1`, `empty=0`.
Output as: X wins: `[1]`; O wins: `[-1]`; tie: `[-1,1]`.

Try it online or verify all test cases.

**Explanation:**

```
ø           # Zip/transpose the (implicit) input-matrix, swapping rows/columns
 «          # Merge the list to the (implicit) input-matrix, so the list of rows in the
            # input now also contains the columns
  I         # Push the input-matrix again
   Å\       # Pop and push its main diagonal
     ª      # And append this triplet to the list as well
      IÅ/ª  # Do the same for the main anti-diagonal
€           # Now map over each triplet in the list:
 ê          #  Sort and uniquify this triplet
  é         # After the map, sort all inner lists by length
   н        # And pop and push the first (thus shortest) one
            # (after which it is output implicitly as result)

```

Try it online with a step-by-step output.

---
Tags: code-golf, board-game, classification, tic-tac-toe
---


title: Penney-Conway odds

text:
# Question
Title: Penney-Conway odds
## Background

**Penney's game** is a two-player game about coin tossing. Player A announces a sequence of heads and tails of length \\$n\\$, then player B selects a different sequence of same length. The winner is the one whose sequence appears first as a substring (consecutive subsequence) in repeated coin toss.

**Conway's algorithm** describes how to calculate the odds of a single sequence of length \\$n\\$ in Penney's game:

> For every integer \\$1\le i \le n\\$, add \\$2^i\\$ if its first \\$i\\$ items match the last \\$i\\$ items. The sum is the expected amount of tosses before you will see the exact pattern. For example (all examples being \\$n=6\\$),
>
> * `HHHHTT`: Only matches at \\$i=6\\$, so the expected number of tosses is \\$64\\$.
> * `TTHHTT`: Matches at \\$i=1,2,6\\$, so the expected number of tosses is \\$2+4+64=70\\$.
> * `HHHHHH`: Matches everywhere, so \\$2+4+8+16+32+64=126\\$.
>
> This generalizes easily to \\$p\\$-sided dice: for each match, add \\$p^i\\$ instead.

## Task

Suppose we play Penney's game with \\$p\\$-sided dice, where \\$p\ge 2\\$. Given the value of \\$p\\$ and a sequence of outcomes \\$S\\$ as input, calculate the expected tosses before you get the exact pattern \\$S\\$.

The elements of \\$S\\$ can be \\$1 \dots p\\$ or \\$0 \dots p-1\\$.

Standard rules apply. The shortest code in bytes wins.

## Test cases

```
p  S                            ans
------------------------------------------
2  [0, 0, 0, 0, 1, 1]           64
2  [1, 1, 0, 0, 1, 1]           70
3  [1, 1, 1, 1, 1]              363
9  [0, 1, 2, 3, 4, 5, 6, 7, 8]  387420489

```

# Answer
> 8 votes
# 05AB1E, ~~16~~ 9 bytes

Port of @*Dingus*'s Ruby answer, so make sure to upvote him!

-7 bytes thanks to Grimmy.

```
η¹.sÃ€gmO

```

Try it online!

## Explanation

```
η          Find all prefixes of the input
 ¹         Re-take the first input
  .s       Find all suffixes of the input
    Ã      Find the two lists' intersection
     €g    Find the length of each
       m   Exponentiation by the second input
        O  Sum the output list

```

# Answer
> 6 votes
# Python 3.8 (pre-release), 57 bytes

Modification of @math junkie's code making use of the walrus operator.

```
lambda p,S,i=0:sum(p**(i:=i+1)*(S[:i]==S[-i:])for _ in S)

```

Try it online!

---

An alternative 51-byte solution assuming that we may take an extra argument \\$ l \\$ denoting the length of the list.

# Python 2, 51 bytes

```
f=lambda p,S,l:l and(S[:l]==S[-l:])*p**l+f(p,S,l-1)

```

Try it online!

# Answer
> 6 votes
# , 18 15 bytes

```
#.0,~<\.=[:|.<\

```

Try it online!

* Create the boxed suffixes `<\.` and reversed prefixes `[:|.<\`...
* and check where they match elementwise `=`...
* This will be a boolean mask representing the number we seek in base `p`, but shifted right one.
* `0,~` shifts it back how we want...
* `#.` converts it using base `p`

# Answer
> 5 votes
# Python 2, 55 bytes

```
f=lambda p,l,i=0:l==l[:i]or(l[:i]==l[-i:])+p*f(p,l,i+1)

```

Try it online!

# Answer
> 5 votes
# Husk, ~~12~~ ~~10~~ 9 bytes

```
ΣMo^L§nṫḣ

```

Port of *@petStorm*'s 05AB1E answer, so make sure to upvote him!
-2 bytes thanks to *@Zgarb*.
-1 byte thanks to *@Leo*.

Try it online.

**Explanation:**

```
     §     # Using the first argument-list twice:
        ḣ  #  Take its prefixes
       ṫ   #  And its suffices
      n    #  List intersection; keep only the sublists which are present in both
 M         # Map over each remaining sublist as left argument,
  o        # using the following two commands:
    L      #  Take the length of the sublist
   ^       #  take the power of the two: input^length
Σ          # And then sum the integers in the mapped list
           # (after which the result is output implicitly)

```

# Answer
> 3 votes
# Ruby, ~~55~~ ~~53~~ 49 bytes

```
->p,s{(1..s.size).sum{|i|s[0,i]==s[-i,i]?p**i:0}}

```

Try it online!

Similar to the non-recursive Python answer.

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

```
{⍺+.*≢¨(⌽¨,\⌽⍵)∩,\⍵}

```

```
{⍺+.*≢¨(⌽¨,\⌽⍵)∩,\⍵}
,\⍵         prefixes
∩           intersect
(⌽¨,\⌽⍵)   suffixes
≢¨          length of each
⍺+.*        exponentiation and sum

```

Try it online!

# Answer
> 2 votes
# Red, 87 bytes

```
func[p s][o: 0
repeat n d: length? s[if(at s d + 1 - n)=
copy/part s n[o: p ** n + o]]]

```

Try it online!

# Answer
> 2 votes
# K (oK), 31 bytes

```
{x/|0,{(y#x)~|y#|x}/:[y;1+!#y]}

```

Try it online!

# Answer
> 2 votes
# Jelly, 9 bytes

```
eÐƤ¹Ƥ$;0ḅ

```

A dyadic Link accepting a list on the left and an integer on the right which yields an integer.

**Try it online!**

### How?

```
eÐƤ¹Ƥ$;0ḅ - Link: list, S; integer, p           e.g.  [2,3,1,2,3]; 4
     $    - last two links as a monad:
    Ƥ     -   for prefixes (of S):                    [2] [2,3] [2,3,1] [2,3,1,2] [2,3,1,2,3]
   ¹      -     identity                              [2] [2,3] [2,3,1] [2,3,1,2] [2,3,1,2,3]
          -   }                                      =[[2],[2,3],[2,3,1],[2,3,1,2],[2,3,1,2,3]]
 ÐƤ       -   for post-fixes (of S):                  [2,3,1,2,3] [3,1,2,3] [1,2,3] [2,3] [3]
e         -     exists in (the collected prefixes)?   1           0         0       1     0
          -   }                                      =[1,   0,   0,   1,   0]
       0  - literal zero                              0
      ;   - concatenate                               [1,   0,   0,   1,   0,   0]
        ḅ - convert from base (p)                      1×4⁵+0×4⁴+0×4³+1×4²+0×4¹+0×4°
                                                      =1024+16
                                                      =1040

```

# Answer
> 1 votes
# Retina, 55 bytes

```
~[".+¶$.("|'_Lv$`((,\d+)+)$(?<=^(\d+)\1\b.*)
$#2*$($3$*

```

Try it online! Link includes test suite. Takes input as a comma-separated list, but the test suite removes spaces and brackets for ease of use. Explanation:

```
Lv$`((,\d+)+)$(?<=^(\d+)\1\b.*)

```

Match all (necessarily overlapping) suffixes of the input starting with a comma that also match immediately after the base.

```
$#2*$($3$*

```

For each match, output a string of the form `2*2*` where `2` is the input base and the number of `2`s is the number of matched integers. (The trailing `)` is implied.)

```
[".+¶$.("|'_

```

Join the matches with a `_` and prefix the whole output with the following:

```
.+
$.(

```

For the second example, this results in the following:

```
.+
$.(2*2*2*2*2*2*_2*2*_2*

```

Note that the `_)` at the end of the program is implied.

```
~

```

Evaluate the generated Retina program, thus computing the desired result.

# Answer
> 1 votes
# Charcoal, 17 bytes

```
Ｉ×θ↨θＥη⁼…η⁻Ｌηκ✂ηκ

```

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

```
     Ｅη              Map over elements of `S`
              ✂ηκ   `S` sliced starting at that element
       ⁼            Is equal to
        …η⁻Ｌηκ      Prefix of `S` with that length
   ↨θ               Convert from base `p`
 ×θ                 Multiply by `p`
Ｉ                   Cast to string for implicit print

```

# Answer
> 1 votes
# Pure Bash, 70 bytes

```
for((i=$#;--i;)){ [ "${*:2:$i}" = "${*: -$i}" ]&&$[s+=$1**i];};echo $s

```

Try it online!

The input is passed in the arguments: first `p`, then the items (each as a separate argument).

Output is on stdout.

# Answer
> 0 votes
# Pyth, 16 bytes

```
sm*q<Qd>dQ^vzdSl

```

Try it online!

Map (`m`) over the 1-indexed range of the sequence (`Sl(Q)`). If the first `d` elements of the sequence (`<Qd`) equals the last `d` elements (`>dQ`), map to "p to the power of d" (`^vzd`). Sum the result (`s`).

# Answer
> 0 votes
# Brachylog, 16 bytes

```
{{a₀.&a₁}ᵗlᵗ^}ᶠ+

```

Try it online!

```
               +    The output is the sum of
{            }ᶠ     every possible output from:
  a₀.               find a prefix
     &a₁            which is also a suffix
 {      }ᵗ          of the last item of the input,
          lᵗ        take its length,
            ^       and take the first element to the power of that length.

```

---
Tags: code-golf, math, combinatorics, probability-theory
---


title: Remove loops from a walk

text:
# Question
Title: Remove loops from a walk
I've been playing around with a robot on the coordinate plane. This robot is able to tell me if it goes left, right, up, or down by reporting back a string consisting of the letters `L`, `R`, `U`, and `D`, such as `DLURRDLURDLLLRRLRLDURRU`. Each character represents a movement of one unit. However, it seems that the robot is going in loops on the plane, returning to coordinates that it has already visited. I don't want the robot to do that. I'd like the robot to tell me about the path it takes without any loops included - these loops should be removed from left to right in the string. Every step in the string it reports should represent movement to a cell that it has not yet visited before. If the robot ends where it starts, then it should report back an empty string.

```
Test cases

ULRURU -> UURU
URDLDRU -> DRU
LLLLRRRL -> LL
LLLULRRRL -> LLLUR
UURDDRULDL -> {empty string}
DLURRDLURDLLLRRLRLDURRU -> R
URULLLDLUULDDLDRDDLLLLLDLLUUULLURU -> URULLLDLUULDDLDRDDLLLLLDLLUUULLURU

```

This is a standard code golf challenge, where the shortest answer wins. Standard rules apply.

# Answer
> 8 votes
# Jelly, 20 bytes

```
O2ȷ:ı*S
ẆÇÐḟḢ⁸œṣFµÐL

```

**Try it online!** Or see the test-suite.

### How?

```
O2ȷ:ı*S - Link 1, distance travelled: list of UDLR characters
O       - ordinals -> U:85 D:68 L:76 R:82
 2ȷ     - 2000
   :    - integer division -> U:23 D:29 L:26 R:24 (Note mod 4 these are 3 1 2 0)
    ı   - square root of -1  - i.e. (0+1j)
     *  - exponentiate -> U:(0-1j) D:(0+1j) L:(-1+0j) R:(1+0j)
      S - sum - 0 iff the path is a loop

ẆÇÐḟḢ⁸œṣFµÐL - Main Link: list of UDLR characters
         µÐL - loop until no change occurs:
Ẇ            -   all sublists
  Ðḟ         -   filter discard those which are truthy (non-zero) under:
 Ç           -     call last Link (1) as a monad
    Ḣ        -   head - X = first, shortest loop (if none this yields 0)
     ⁸       -   chain's left argument
      œṣ     -   split at sublists equal to X
        F    -   flatten

```

# Answer
> 8 votes
# , 51 39 bytes

```
([,~i.~{.])/@|.&.([:+/\0,0j1^'ULDR'&i.)

```

Try it online!

*-12 bytes thanks to Bubbler! For the idea of combining "Under"s into a single train, and skipping an unnecessary increment of the indexes*

## The idea

1. Convert the letters to their indexes within the `ULDR`
2. Convert those indexes to complex vectors: Think `U = i`, `L = -1`, `D = -i` `R = 1`

In fact, because of rotational symmetry, we don't actually care which direction is "up" as long the relative order of the directions is preserved.
3. Scan sum those vectors to get the path positions (still as complex numbers)
4. Reduce the path into a loop free version: Any time we arrive at a point we've seen, remove all history up to and including that old point.
5. Invert steps 1 to 3, in reverse order.

The fun thing is that step 5 is accomplished with J's Under conjunction, which allows you to perform a transformation, do stuff, and then have the inverse transformation automatically applied. Here, J is smart enough to know how to invert the entire train comprising steps 1 through 3 in reverse order:

```
                             Elementwise
reduce to       Scan sum     index within
remove loops    of...        'ULDR'
     |             |             |
vvvvvvvvvvvvv     vvvvv      vvvvvvvv
([,~i.~{.])/@|.&.([:+/\0,0j1^'ULDR'&i.)
               ^^      ^^^^^^
               |         |
             Under     0 prepended to
                       i raised to...

```

# Answer
> 5 votes
# JavaScript (Node.js),  ~~101 ... 91~~  90 bytes

```
f=s=>s&&[s[Buffer(s).every(c=>p+=[w=s.length,~!++i,1,-w][c%5],i=p=0)-1]]+f(s.slice(p?1:i))

```

Try it online!

## How?

### Method

For each index \\$n\\$ in the input string, we initialize our position to \\$(0,0)\\$ and run a simulation of the walk starting from the \\$n\\$-th character. If there's some move at \\$n+i-1,i\>0\\$ that brings us back to \\$(0,0)\\$, it means that we have identified a loop: we skip the entire segment and restart at \\$n+i\\$.

```
   n  n+i-1
   v    v
...LLURRD...
         ^
        n+i

```

Otherwise, we append the current move to the output (***L*** in the above example) and advance to \\$n+1\\$.

### Implementation

* Instead of relying on an explicit counter \\$n\\$, we use recursive calls to our main function where the leading characters of the input string are gradually removed.
* Instead of using a pair \\$(x,y)\\$ to keep track of our position, we actually use a scalar value \\$p=x+y\cdot w\\$, where \\$w\\$ is the remaining number of characters in the string. This is safe because we can't have more than \\$w\\$ moves in the same direction from this point.
* To convert a character move into a direction, we take its ASCII code modulo \\$5\\$. The ASCII codes of \\$(D,L,R,U)\\$ are \\$(68,76,82,85)\\$, which are conveniently turned into \\$(3,1,2,0)\\$.

## Commented

```
f = s =>                   // f is a recursive function taking a string s
  s &&                     // if s is empty, stop recursion
  [                        // wrapper to turn undefined into an empty string:
    s[                     //   get either s[0] (next char.) or s[-1] (undefined):
      Buffer(s).every(c => //     for each ASCII code c in s:
        p += [             //       add to p:
          w = s.length,    //         +s.length for up ('U' -> 85 -> 85 % 5 = 0)
          ~!++i,           //         -1 for left ('L' -> 76 -> 76 % 5 = 1)
                           //         (increment i)
          1,               //         +1 for right ('R' -> 82 -> 82 % 5 = 2)
          -w               //         -s.length for down ('D' -> 68 -> 68 % 5 = 3)
        ][c % 5],          //       using c modulo 5
                           //       stop if p = 0, meaning that we're back to our
                           //       starting point
        i = p = 0          //       start with i = p = 0
      ) - 1                //     end of every(), subtract 1
    ]                      //   end of s[] lookup
  ] +                      // end of wrapper
  f(                       // recursive call with either:
    s.slice(p ? 1 : i)     //   s.slice(1) (no loop)
  )                        //   or s.slice(i) (skipping the loop)

```

# Answer
> 4 votes
# MATL, 26 bytes

```
t"0J&y15\^hYs&=XR&fq&:[]w(

```

Try it online! Or verify all test cases.

### Explanation

```
t        % Implicit input. Duplicate
"        % For each
  0      %   Push 0
  J      %   Push j (imaginary unit)
  &y     %   Duplicate third-topmost element from the stack: current string
  15\    %   ASCII code of each character, modulo 15. This gives 10, 7, 8, 1
         %   for 'U', 'R', 'L', 'D' respectively
  ^      %   Element-wise power. This gives j^10=-1, j^7=-j, j^8=1, j^1=j for
         %   'U', 'R', 'L', 'D'. These are the steps followed by the robot in
         %   the complex plane (rotated and reflected, but no matter)
  h      %   Concatenate. This prepends the 0, as starting point of the path
  Ys     %   Cumulative sum. This computes the path traced by the robot
  &=     %   Matrix of pair-wise equality comparisons for robot positions
  XR     %   Upper triangular part, without diagonal
  &f     %   Row and column indices of nonzeros. This will be non-empty if
         %   there is a loop in the path
  q      %   Subtract 1
  &:     %   Two-input range. This uses the first element from each input,
         %   that is, the first loop found
  []w(   %   Push [], swap, assignment index: this removes the characters that
         %   caused the loop
         %   string
         % End (implicit). The loop is run as many times as the input length,
         % which is an upper bound to the number of loops
         % Display (implicit)

```

# Answer
> 3 votes
# T-SQL, 236 bytes

First time I ever use `PI()` in sql

I am using table as input

```
WHILE @@rowcount>0WITH C
as(SELECT*,sum(ascii(a)/12-6+3/(ascii(a)-79)*pi())over(order
by b)x FROM @)DELETE C
FROM C,(SELECT top 1max(b)i,min(b)j
FROM C GROUP BY x HAVING SUM(1)>1or x=0ORDER BY 2)z
WHERE(i=j or j<b)and i>=b
SELECT*FROM @

```

**Try it online**

# Answer
> 2 votes
# C (gcc),  ~~119 ... 111~~  110 bytes

Outputs by modifying the input string.

```
p;f(char*s){for(char*r,*q=s;*q;p?*s++=*q++:(q=r))for(r=q,p=0;*r?p+=(*r%17?strlen(q):1)*~-(*r++%5&2):0;);*s=0;}

```

Try it online!

### How?

The algorithm is the same used in my JS answer with a few differences:

* We use a `for` loop instead of a recursive approach.
* We overwrite the input string with the output. This is safe because what is written is at most as long as what is read, and the meaningful information is always ahead of both the read and the write pointers (`q` and `s` respectively).
* Given the ASCII code `c` of the move character, we use `c % 17` to find out if it's a vertical or horizontal move, and `c % 5 & 2` to distinguish between *down* and *up* or between *left* and *right*.

```
         | 'D' (68) | 'L' (76) | 'R' (82) | 'U' (85)
---------+----------+----------+----------+----------
 % 17    |     0    |     8    |    14    |     0
 % 5 & 2 |     2    |     0    |     2    |     0

```

# Answer
> 2 votes
# Java (JDK), 229 bytes

```
s->{var l=new java.util.Stack();int x=0,y=0,i;for(var c:(s+"").getBytes()){l.add(x+","+y);i="DLUR".indexOf(c);x+=~i%2*~-i;y+=i%2*(i-2);i=l.indexOf(x+","+y);if(i>=0){var z=l.subList(i,l.size());s.delete(i,i+z.size());z.clear();}}}

```

Try it online!

## Credits

# Answer
> 2 votes
# perl -nF/(?{s-.\*(??{!($&=~y&R&&c==$&=~y&L&&c&&$&=~y&U&&c==$&=~y&D&&c)})--g;print})(\*COMMIT)/, 62 12 5 0 bytes

Try it online!

Finds substrings with the same amount of Ls and Rs, and the same amount of Us and Ds, and removes them. Prints the result.

# Answer
> 2 votes
# Java (OpenJDK 8), 253 252 243 bytes

```
static String r(String s){String e=s;int l=s.length();for(int i=0;i<l;i++)for(int j=i+1;j<l;j++){int u=0;for(int k=i;k<=j;k++)u+=(9*(e.charAt(k)%6/3)+1)*2*(5.5-(e.charAt(k)-12)/11);if(u==0)return r(e.replace(e.substring(i,j+1),""));}return e;}

```

Try it online!

This uses a recursion method, so I'm not entirely sure if it's being scored correctly. It has a limit of going off 9 tiles in a given loop, but that can be increased to any amount as needed. Ungolfed:

```
public static String remove(String str) {
    String removed = str;
    int l = str.length();
    for (int i = 0; i < l - 1; i++) //-1 optional
        for (int j = i + 1; j < l; j++) {
            int upDownLeftRight = 0;
            for (int k = i; k <= j; k++)
                upDownLeftRight +=(9*(e.charAt(k)%6/3)+1)*2*(5.5-(e.charAt(k)-12)/11);
            if (upDownLeftRight == 0)
                return remove(removed.replace(removed.substring(i, j + 1), ""));
        }
    return removed;
}

```

A few seconds before I was going to submit this the post closed, a few days ago. Just realized it was opened back up.

# Answer
> 2 votes
# Python 2, ~~94~~ 93 bytes

*-1 byte thanks to @dingledooper!*

```
r=""
x,=l=[0]
for c in input():x+=1j**(ord(c)%15);r+=c;l[len(r):]=x,;r=r[:l.index(x)]
print r

```

Try it online!

A minor improvement over @xnor's solution using slice assignment. Be sure to check out and upvote his answer!

The current position `x` is stored as a complex number. For each movement, the program checks the list of visited positions `l`, and truncates the redundant moves appropriately.

# Answer
> 1 votes
# Charcoal, 40 bytes

```
⊞υ⟦ⅈⅉ⟧ＦＳ«Ｍ✳ι⊞υι⊞υ⟦ⅈⅉ⟧≔…υ⊕⌕υ§υ±¹υ»⎚↑Φυ﹪κ²

```

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

```
⊞υ⟦ⅈⅉ⟧

```

Save the current coordinates to the predefined empty list.

```
ＦＳ«

```

Loop through each character of the input string.

```
Ｍ✳ι

```

Move the cursor in that direction.

```
⊞υι⊞υ⟦ⅈⅉ⟧

```

Save the direction and the new position.

```
≔…υ⊕⌕υ§υ±¹υ

```

Truncate the list to the original appearance of the position.

```
»⎚

```

Reset the cursor (possibly due to a bug in Charcoal).

```
↑Φυ﹪κ²

```

Output the directions which didn't get truncated.

# Answer
> 1 votes
# Python 3.8 (pre-release), ~~168~~ ~~164~~ ~~163~~ ~~126~~ 125 bytes

```
l=[p:=0]
n=""
for s in input():
 if(p:=p+1j**(ord(s)%15))in l:x=l.index(p);l=l[:x+1];n=n[:x];p=l[x]
 else:l+=[p];n+=s
exit(n)

```

Try it online!

Assigns a complex number to go up, down, left right on the complex plane. Then iterates over the given path S and either adds the new point to the path in the list of points `l` and the result string `n` or if it detected a loop from a previous index up until the current character, it slices the characters and points that created the loops out of the lists.

-35 thanks to @JonathanAllan!

# Answer
> 1 votes
# Python 3, 178 bytes

```
x=y=0;c=[[0,0]];a='';t='UDLR';u=['y-=1','y+=1','x-=1','x+=1']
for i in input():
 exec(u[t.index(i)])
 if[x,y]in c:f=c.index([x,y]);a=a[:f];c=c[:f]
 else:a+=i
 c+=[[x,y]]
print(a)

```

Try it online!

Keeps track of visited coordinates and removes letters between duplicate coords.

# Answer
> 1 votes
# , ~~208~~ 205 bytes

```
u=function(a){s=function(x)unlist(strsplit(x,''))
m=match
d=s(a)
l=length(d)
for(i in 1:l)for(j in i:l)if(l&!sum(m(d[k<-i:j],s("L R"),2)-2)&!sum(m(d[k],s("D U"),2)-2))return(u(d[-k]))
paste(d,collapse='')}

```

Try it online!

Recursive function: starting at each position in the string, check whether there are equal numbers of L+R and of U+D in the range up to each subsequent position. If so, then this is the first left-to-right loop, so delete this and call the function using the result. Otherwise, there are no loops, so output whatever is left.

Frustratingly, R is not particularly golfy at string-handling (at least with my ability), and one-third of the code is ~~wasted~~ used splitting strings into characters... so:

# +stringr, 155 bytes (or  172 bytes)

```
u=function(d,l=nchar(d),s=substring){
for(i in 1:l)for(j in i:l)if(l&all(!diff(str_count(e<-s(d,i,j),s("UDLR",1:4,1:4)))[-2]))return(u(str_remove(d,e)))
d}

```

Try it online!

Exactly the same approach, but using `stringr` library to work directly on the string instead of splitting into characters.

# Answer
> 1 votes
# Python 2, 98 bytes

```
r=""
x,=l=0,
for c in input():x+=1j**(ord(c)%15);l+=x,;r+=c;n=l.index(x);l=l[:n+1];r=r[:n]
print r

```

Try it online!

Instead of branching on whether the current position `x` has appeared before, we just look for where it first appeared and truncate to right after that. If it never appeared before, we find the current appearance, so nothing gets cut off. The `ord(c)%15` is from a suggestion by Jonathan Allan.

# Answer
> 1 votes
# Wolfram Language, ~~101~~ 100 bytes

```
StringJoin[Characters@#/.(r={"L"->-"R","U"->-"D"})//.{a___,x__,b___}/;Tr@{x}==0->{a,b}/.Reverse/@r]&

```

Try it online!

With some fancier formatting and comments:

```
StringJoin[                                       (*reconvert to input format*)
  Characters@#                                    (*split into characters*)
  /. (r = {"L" -> -"R", "U" -> -"D"})             (*map L to -R and U to -D*)
  //. {a___, x__, b___} /; Tr@{x} == 0 -> {a, b}  (*delete runs that sum to 0*)
  /. Reverse /@ r                                 (*convert -R and -D back to L and U*)
]&

```

This takes a similar method to some of the others, deleting runs that sum to zero, but this one does it by replacing L and U with negative R and negative D respectively.

Another **100 byte** solution that uses a similar but distinct technique, using SequenceReplace:

```
StringJoin@SequenceReplace[Characters@#/.(r={"L"->-"R","U"->-"D"}),{__}?(Tr@#==0&)->{}]/.Reverse/@r&

```

Try it online!

# Answer
> 0 votes
# 05AB1E, 44 bytes

```
gU0ˆÇ5%v1X‚Â(ìyè¯θ+ˆ¯¤kÐV¯gα<‚Xª£ιнJ¯Y>£´vyˆ

```

Ugh.. This can definitely be golfed substantially, but it works..

Inspired by both *@Arnauld*'s JavaScript answer and *@OlivierGrégoire*'s Java answer, so make sure to upvote them!

Try it online or verify all test cases.

**Explanation:**

```
g                # Get the length of the (implicit) input-string
 U               # Pop and store it in variable `X`
0ˆ               # Add 0 to the global array
Ç                # Convert the (implicit) input-string to an integer-list of codepoints
 5%              # Take modulo-5 on each
   v             # Loop over each integer `y`:
    1X‚          #  Pair 1 with the length `X`: [1,length]
       Â         #  Bifurcate it (short for Duplicate & Reverse copy)
        (        #  Negate the values: [-length,-1]
         ì       #  Prepend the lists together: [-length,-1,1,length]
          yè     #  Index `y` into this quadruplet
            ¯θ+  #  Add the last item of the global array to it
               ˆ #  And pop and add it to the global array
    ¯            #  Push the global array
     ¤           #  Push its last item (without popping)
      k          #  Get the first index of this last item in the global array
       Ð         #  Triplicate this index
        V        #  Pop and store one copy in variable `Y`
         ¯g      #  Push the length of the global array
           α     #  Take the absolute difference with the index
            <    #  Decrease it by 1
             ‚   #  Pair it with the index
              Xª #  And append length `X`
    £            #  Split the string into parts of that size
                 #  (which uses the implicit input-string in the very first iteration)
     ι           #  Uninterleave it
      н          #  Only leave the first part of two strings, removing the middle part
       J         #  Join this pair together
    ¯            #  Push the global array again
     Y>          #  Push `Y` + 1
       £         #  Only leave the first `Y`+1 values of the global array
        ´        #  Empty the global array
         v       #  Loop over the `Y`+1 values of the global array:
          yˆ     #   And add each of them back the global array

```

# Answer
> 0 votes
# PowerShell, ~~126~~ 120 bytes

```
$x=$y=0
switch -r(,'-'+$args){U{$y++}D{$y--}R{$x++}L{$x--}.{$g="$g$_$x-$y"-replace"(?<=($x-$y)).*\1$"}}
$g-replace'\d|-'

```

Try it online!

The script:

1. injects `$x-$y` to input string like `-0-0U0-1U0-2R1-2U1-3`
2. removes substrings between same coordinates
3. removes digits and minus chars

Less golfed:

```
$x=$y=0
switch -regex (,'-'+$args){
    U {$y++}
    D {$y--}
    R {$x++}
    L {$x--}
    . {$g="$g$_$x-$y"-replace"(?<=($x-$y)).*\1$"}
}
$g-replace'\d|-'

```

---
Tags: code-golf, path-finding
---