Repeating occupied pattern in Hilbert's hotel

Question

Imagine a countable infinite amount of empty rooms. When an infinite amount of guests come, they occupy the 1st, 3rd, 5th...(all odd) empty rooms. Therefore there's always an infinite amount of empty rooms, and occupied guests needn't move when new guests come.

- - - - - - - - - - - - - - - - -
1 - 1 - 1 - 1 - 1 - 1 - 1 - 1 - 1
1 2 1 - 1 2 1 - 1 2 1 - 1 2 1 - 1

Same group of guests would leave together, so if group 1 leave, it results in

- 2 - - - 2 - - - 2 - - - 2 - - -

Notice that some rooms turn empty, so if another group of infinite guests come, it results in

3 2 - 3 - 2 3 - 3 2 - 3 - 2 3 - 3

Now room 1,2,4,6,7,... are occupied while 3,5,8,... are empty.

Input

Given a list of moves(aka. some group join or some group leave). All join requests are labeled 1,2,3,... in order.

You can also choose to not read the joining label or not read join/leave value.

Output

The shortest repeating pattern of occupied/empty.

Test cases

[]            => [0]
[+1]          => [1,0]
[+1,+2]       => [1,1,1,0]
[+1,+2,-1]    => [0,1,0,0]
[+1,+2,-1,+3] => [1,1,0,1,0,1,1,0]
[+1,-1]       => [0]

Shortest code wins

Answer 1

Jelly,  28  24 bytes

N;`⁹¬Tm2Ʋ¦A¬ẹ¦ʋƒ0ṠŒṖEƇḢḢ

A full program* that accepts the register list and prints a Jelly representation of the pattern list.

^{* Only a full program to handle specifically [] => [0] for which the monadic Link would yield the integer 0}

Try it online!

Replacing ŒṖ with sJ$ will be faster if you want to try slightly longer inputs.

How?

The idea is to process the moves in turn maintaining a prefix that starts at [0] and doubles in length at each move either occupying every other empty room with a copy of move or removing all occurrences of the negative of move. Once this is done we can then find the shortest prefix that repeats to give the same.

Actually, the implementation is a little more convoluted - rather than the "either or" above, we process negated values of the moves, always add these to every other unoccupied room, take absolute values and then always remove all occurrences of the negated move from all rooms. This saves some precious bytes.

N;`⁹¬Tm2Ʋ¦A¬ẹ¦ʋƒ0ṠŒṖEƇḢḢ - Main Link: list of moves, Moves
N                        - negate {Moves} (vectorises)
               ƒ0        - start with 0 and reduce {that} by:
              ʋ          -   last four links as a dyad - f(Rooms, -Move)
 ;`                      -     {Rooms} concatenate {Rooms} -> R2
         ¦               -     sparse application...
        Ʋ                -     ...to indices: last four links as a monad - f(R2):
    ¬                    -       logical NOT {R2}
     T                   -       truthy indices of {that} -> I
       2                 -       two
      m                  -       {I} modulo-slice {2
                                   -> indices of every other empty room
   ⁹                     -     ...apply: set to chain's right argument = -Move
          A              -     absolute value {that} (vectorises)
             ¦           -     sparse application...
            ẹ            -     ...to indices: indices of {-Move}
           ¬             -     ...apply: logical NOT
                 Ṡ       - signs {that} -> occupied or not indicators
                  ŒṖ     - partitions of {that}
                     Ƈ   - keep those {patitions} for which:
                    E    -   all equal? -> repetitive partitions
                      Ḣ  - head {that} -> shortest repetitive partition
                       Ḣ - head {that} -> shortest possible prefix

Answer 2

JavaScript (ES6), 100 bytes

Returns a comma-separated binary string.

a=>/(.*?)(,\1)*$/.exec(a.reduce((b,x)=>[...b,...b].map(q=v=>x<0|v?v+x&&v:q^=x),[0]).map(x=>+!!x))[1]

Try it online!

99 bytes if we use NaN for unoccupied

Commented

a =>                 // a[] = input array
/(.*?)(,\1)*$/       // a regular expression that looks for the shortest
                     // prefix which, when repeated a whole number of
                     // times with a leading comma, allows to reach the
                     // end of the string
.exec(               // apply this to:
  a.reduce((b, x) => //   for each element x in a[],
                     //   using the array b[] as the accumulator:
    [...b, ...b]     //     append b[] to itself
    .map(q =         //     initialize q to a NaN'ish value
      v =>           //     for each element v in the resulting array:
      x < 0 | v ?    //       if x is negative or v is not 0:
        v + x && v   //         append 0 if v = -x, or v otherwise
      :              //       else:
        q ^= x       //         toggle q between 0 and x and append that
    ),               //     end of map()
    [0]              //     initialize the accumulator to [0]
  )                  //   end of reduce()
  .map(x => +!!x)    //   update each value to either 0 or 1
                     //   implicit coercion to a string
)[1]                 // end of exec(); return the prefix

Answer 3

Python 3, 223 202 bytes

Oh boy. Cool challenge, cant wait to see what everyone can do!

slowly chipping away I guess...

def f(g,h=[0]):
 for q in g:
  if[q]<h:h=[w*(w-q)for w in h];continue
  h=h+h;p=1
  for i,w in enumerate(h):
   if w<1:h[i]=p*q;p=1-p
 while h==h[:len(h)//2]*2:h=h[:len(h)//2]
 return[1-(i<1)for i in h]

Try it online!

Python 3.8 (pre-release), 215 195 bytes

stealing Ajax1234's walrus operator while loop o7

def f(g,h=[0]):
 for q in g:
  if[q]<h:h=[w*(w-q)for w in h];continue
  h=h+h;p=1
  for i,w in enumerate(h):
   if w<1:h[i]=p*q;p=1-p
 while h==(k:=h[:len(h)//2])*2:h=k
 return[1-(i<1)for i in h]

Try it online!

Answer 4

Charcoal, 59 bytes

⊞υ⁰Ｆθ¿‹ι⁰ＵＭυ∧⁺ικκ«≔⁺υυυＦΦ⌕Ａυ⁰﹪벧≔υκι»≔⭆υ¬¬ιηＷ⁼ηײ÷η²≔÷η²ηη

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

⊞υ⁰

Start with one empty room.

Ｆθ

Loop over the input values.

¿‹ι⁰

If it is negative, then...

ＵＭυ∧⁺ικκ«

Discard those values whose sum is zero, otherwise:

≔⁺υυυ

Duplicate the list.

ＦΦ⌕Ａυ⁰﹪λ²

Loop over alternate indices of the empty rooms. (Filtering is golfier than slicing alternate indices.)

§≔υκι

Fill the room at this index.

»≔⭆υ¬¬ιη

Convert the rooms to a binary string of occupancy.

Ｗ⁼ηײ÷η²

While the string equals half of itself repeated twice, ...

≔÷η²η

... halve the length of the string.

η

Output the final string.

Answer 5

Python3, 227 bytes

def f(m):
 h=[0]*(2**sum(i>0for i in m))
 for i in m:
  if i<0:h=[[0,l][l!=-i]for l in h]
  else:
   k=1
   for j,a in enumerate(h):h[j]=[a,i][k%2 and 0==a];k+=a==0
 while h==(k:=h[:len(h)//2])*2:h=k
 return[int(i>0)for i in h]

Try it online!