20
\$\begingroup\$

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

\$\endgroup\$
4
  • \$\begingroup\$ Can you output a cyclic permutation of the pattern, or does it have to start from the first room? \$\endgroup\$ Aug 3, 2023 at 4:24
  • \$\begingroup\$ @CommandMaster Start from first. 10 and 01 are different(01 should be impossible) \$\endgroup\$
    – l4m2
    Aug 3, 2023 at 4:25
  • \$\begingroup\$ I guess we cannot output occupied rooms with their group number? (e.g. [+1,+2,-1,+3] -> [3,2,0,3,0,2,3,0]) \$\endgroup\$
    – Arnauld
    Aug 3, 2023 at 11:32
  • \$\begingroup\$ The correct output will always have length a power of 2, end in a 0, and contain an odd number of 0s. \$\endgroup\$
    – Nitrodon
    Aug 3, 2023 at 20:51

5 Answers 5

5
\$\begingroup\$

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
\$\endgroup\$
5
\$\begingroup\$

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
\$\endgroup\$
5
  • \$\begingroup\$ Upvote for NaN'ish \$\endgroup\$
    – corvus_192
    Aug 3, 2023 at 8:46
  • \$\begingroup\$ @corvus_192 T/F(.map(x=>x>0)) feels better to me \$\endgroup\$
    – l4m2
    Aug 3, 2023 at 10:57
  • \$\begingroup\$ @l4m2 corvus_192 was referring to the comment initialize q to a NaN'ish value. (I added the 99-byte version later.) \$\endgroup\$
    – Arnauld
    Aug 3, 2023 at 11:29
  • \$\begingroup\$ @Arnauld T/F is also 99 bytes \$\endgroup\$
    – l4m2
    Aug 3, 2023 at 14:14
  • 1
    \$\begingroup\$ @l4m2 I find it less readable. We could also do inverted T/F for 98 bytes. \$\endgroup\$
    – Arnauld
    Aug 3, 2023 at 14:28
2
\$\begingroup\$

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!

\$\endgroup\$
1
\$\begingroup\$

Charcoal, 59 bytes

⊞υ⁰Fθ¿‹ι⁰UMυ∧⁺ικκ«≔⁺υυυFΦ⌕Aυ⁰﹪벧≔υκι»≔⭆υ¬¬ιηW⁼ηײ÷η²≔÷η²ηη

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

⊞υ⁰

Start with one empty room.

Fθ

Loop over the input values.

¿‹ι⁰

If it is negative, then...

UMυ∧⁺ικκ«

Discard those values whose sum is zero, otherwise:

≔⁺υυυ

Duplicate the list.

FΦ⌕Aυ⁰﹪λ²

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.

W⁼ηײ÷η²

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

≔÷η²η

... halve the length of the string.

η

Output the final string.

\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.