15
\$\begingroup\$

Your task is to create a plain hunt (a bell ringing pattern) with n bells. An example with 6 bells:

123456
214365
241635
426153
462513
645231
654321
563412
536142
351624
315264
132546
123456

Each number "bounces" off the side of the grid. From Wikipedia:

Each bell moves one position at each succeeding change, unless they reach the first or last position, when they remain there for two changes then proceed to the other end of the sequence.

In other words, you swap the bells in adjacent pairs, alternating between taking pairs starting from the the first bell and from the second bell. (Thanks to @xnor for this explanation.) You finish in the same order as the start.

This rule be applied to any number of bells, taken as input. Standard loopholes are forbidden.

Test Cases

6

123456
214365
241635
426153
462513
645231
654321
563412
536142
351624
315264
132546
123456

3

123
213
231
321
312
132
123

2

12
21
21
12

1

1

0: Falls in to "I don't care" situation.

\$\endgroup\$
  • 2
    \$\begingroup\$ Is the starting row always 1 ... n or can it be in any order (e.g. 2314 for n=4)? \$\endgroup\$ – nimi Oct 16 at 19:09
  • 7
    \$\begingroup\$ 1 is a special case since it doesn’t have separate start and end rows both equal to 1. Would it be permissible to return 1, 1 for the input of 1? \$\endgroup\$ – Nick Kennedy Oct 16 at 19:54
  • 2
    \$\begingroup\$ Can I print in list form, like [1,2,3,4] or something similar? \$\endgroup\$ – Embodiment of Ignorance Oct 16 at 20:12
  • 4
    \$\begingroup\$ As a bell-ringer, having anything other than 2n changes for plain hunt on n triggers me... \$\endgroup\$ – Neil Oct 16 at 23:12
  • 8
    \$\begingroup\$ I agree that the n=1 test case having one entry seems out of place. For all the rest, we only checking if we've returned to the start after the first change, since otherwise the first line of course equals itself and we'd stop immediately. So, that would gives [[1], [1]] You could also consider putting n=1 under "don't care" to avoid a potential edge case. \$\endgroup\$ – xnor Oct 17 at 2:13

17 Answers 17

5
\$\begingroup\$

Python 2, 93 bytes

lambda n:[[.5+abs((n+j-i*(-1)**(i+j))%(2*n)-n+.5)for j in range(n)]for i in range(2*n+(n>2))]

Try it online!

Outputs a list of lists of integer-valued floats.

The map (i,j) -> j-i*(-1)**(i+j) is very similar to multiplication in the dihedral group. This isn't a coincidence. If we let \$a\$ represent swapping every other element starting from the first, and \$b\$ doing so starting from the second, then these generate the dihedral group \$D_{2n}\$ gives by relations \$a^2 = b^2 =(ab)^n =1 \$. Note that the sequence we're asked to output has us alternate applying \$a\$ and \$b\$, and the fact that \$ (ab)^n =1 \$ confirms that we return to where we started after \$2n\$ total steps.

We can see the dihedral connection more clearly if we extend the top row to \$2n\$ elements rather than \$n\$, and write it zero-indexed. Doing the alternating swaps as usual gives a pattern like below for \$n=3\$. This is almost a multiplication table for the dihedral group \$D_{2n}\$, except that we invert the first group element before multiplying \$g,h \to g^{-1} h \$, giving zeroes (identity) on the diagonal \$g=h\$.

  012345
 +------
0|012345
1|103254
2|430521
3|345012
4|254103
5|521430

To return the values back into the range [0,1,2], we need to map back 3->2, 4->1, 5->0. In the code, surprisingly many characters as spent on the simple-looking mapping doing modular indexing into the palindromic "bouncing" list [1,2,...,n-1,n,n,n-1,...,2,1], We implement this as .5+abs((n+k)%(2*n)-n+.5). The Python 3.8 walrus can save at least 2 bytes, though I haven't optimized it.

\$\endgroup\$
4
\$\begingroup\$

Haskell, 83 bytes

f(a:b:c)=b:a:f c 
f c=c
q l|a:b<-f l=l:f l:q(a:f b)
g n=take(2*n+sum[1|n>2])$q[1..n]

Try it online!

\$\endgroup\$
3
\$\begingroup\$

PHP, 120 bytes

for($b=$a=range(1,$argn);print join($b)."
",$a[1]&&!$i||$a!=$b;)for($j=$i++%2;$n=$b[++$j];$b[$j-2]=$n)$b[$j++]=$b[$j-2];

Try it online!

for(
  $b=$a=range(1,$argn); // set $a and $b to an array of [1...n]
  print join($b)."\n",  // on start of each iteration print $b
  $a[1]&&               // stop when input is 1 (we only print a single 1 for input of 1)
  !$i||                 // allows first iteration to happen since $a==$b on first iteration 
  $a!=$b;               // stop when $a and $b are equal again
)
  for(
    $j=$i++%2;          // set $j to 0 or 1 (alternates each time)
    $n=$b[++$j];        // increment $j by one and set $n to
                        //   last number of next pair in $b, stop if it doesn't exist
    $b[$j-2]=$n         // swap one of bells in $b
  )
    $b[$j++]=$b[$j-2];  // increment $j by one and swap one of bells in $b
\$\endgroup\$
3
\$\begingroup\$

Zsh, 75 95 bytes

s(){echo $a;a=;for x y;a+=($y $x)}
a=({1..$1})
(($1-1))&&repeat $1 s $a&&s '' $a
(($1-2))&&s $a

Try it online! Try it online!

Defines a function s which swaps each pair of arguments and assigns them to a. s is called once normally ABCD -> BADC and then once with an empty element prepended: ABCD -> ACBD; repeated n times. s is called once more at the end, just to print out the array once more.

echo $a is used instead of <<<$a to suppress the empty element causing extra space.

\$\endgroup\$
  • \$\begingroup\$ Gives triple 1 for 1; the result for 2 is also longer than it should be \$\endgroup\$ – Galen Ivanov Oct 17 at 11:24
  • 1
    \$\begingroup\$ Thanks, fixed. Not pretty, but it works. \$\endgroup\$ – GammaFunction Oct 17 at 11:33
3
\$\begingroup\$

Jelly, 25 bytes

s2UF
RÇŻÇfƊƭƬmn2$Ṃṭ$⁸>2¤¡

A monadic Link accepting a non-negative integer which yields a list of lists of non-negative integers.

Try it online! (The footer calls the Link and formats the result as a grid)

How?

s2UF - helper Link: list                e.g. [4, 2, 5, 1, 3]
s2   - split into chunks of length two       [[4, 2], [5, 1], [3]]
  U  - reverse each                          [[2, 4], [1, 5], [3]]
   F - flatten                               [2, 4, 1, 5, 3]

RÇŻÇfƊƭƬmn2$Ṃṭ$⁸>2¤¡ - Main Link: non-negative integer, N
R                    - range = [1,2,...,N]
       Ƭ             - collect up while unique, applying (starting with X = range result):
      ƭ              -   apply previous (default 2) links in turn each time called:
 Ç                   -     1) call helper link as a monad
     Ɗ               -     2) last three links as a monad - i.e. g(X):
  Ż                  -          prefix a zero
   Ç                 -          call helper link as a monad
    f                -          filter keep only those values in X (i.e. remove the zero)
           $         - last two links as a monad:
          2          -   literal two
         n           -   not equal (N)?
        m            - modulo slice (m1 gives every element back,
                                     m0 performs reflection, which is required when N = 2)
                       [m0 reflecting is a very nice behaviour decision by Dennis IMO]
                   ¡ - repeat...
                  ¤  -   ...number of times: nilad followed by link(s) as a nilad:
               ⁸     -                         chain's left argument, N
                >2   -                         greater than 2?
              $      -   ...action: last two links as a monad:
            Ṃ        -                minimum (always [1,2,...,N])
             ṭ       -                tack (appending the final peel for N>2)
\$\endgroup\$
3
\$\begingroup\$

J, 68 62 59 bytes

[:>[:(]C.~_2<\(}.i.@#))&.>/@:|.\<@:>:@i.,(0;1)$~+:-1#.<&2 3

Try it online!

51 bytes if 1 case is allowed to return 2 lines: Try it online!


Could likely be golfed more but I was happy with the idea.

Essentially, everything flows from noting that to get from one element to the next, you apply 1 of two cyclic permutations:

For example, in this case of n=6, to get from a row with an even index to the next row you apply:

┌───┬───┬───┐
│1 2│3 4│5 6│
└───┴───┴───┘

To get from an odd row to an even you apply:

┌─┬───┬───┬─┐
│1│2 3│4 5│6│
└─┴───┴───┴─┘

Once you set that up, the result is just a right to left scan over those alternating permutations. Everything else is the boring details of constructing the permutations and the list to apply them to.

\$\endgroup\$
2
\$\begingroup\$

Charcoal, 54 bytes

NθFθ«Jι⁰≔⁻⁶∧‹⁺ι¬﹪ι²θ∨﹪ι²±¹ηF⎇‹θ³×θθ⊕⊗θ«✳ηI⊕ι≧⁺⁻¬ⅈ⁼⊕ⅈθη

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

Nθ

Input n.

Fθ«

Loop over each bell.

Jι⁰

Jump to its starting position.

≔⁻⁶∧‹⁺ι¬﹪ι²θ∨﹪ι²±¹η

Calculate its starting direction. For odd bells this is normally 7 (south east) and for even bells this is normally 5 (south west) but if the last bell its odd then its staring direction is 6 (south).

F⎇‹θ³×θθ⊕⊗θ«

Loop over each row, either for n<3 or 2n+1 for n>3.

✳ηI⊕ι

Print the current bell and move in the current direction.

≧⁺⁻¬ⅈ⁼⊕ⅈθη

Adjust the direction if the bell has reached the side so that it bounces.

\$\endgroup\$
2
\$\begingroup\$

Perl 6, 52 bytes

{$_,|({S:g:p($++%2)/(.)(.)/$1$0/}...$_)}o{[~] 1..$_}

Try it online!

Explanation

                                         {[~] 1..$_}  # Concat numbers 1..n
{                                      }o  # Feed into block
 $_,  # Start with first string
                                 ...  # Sequence constructor
      {                         }  # Compute next item by
       S:g         /      /    /   # replacing globally
          :p($++%2)  # starting at alternating positions 0, 1, 0, 1, ...
                    (.)(.)  # any two chars
                           $1$0  # swapped
                                    $_  # Until item equals original string
    |(                                )  # Flatten into result list
\$\endgroup\$
1
\$\begingroup\$

Python 2, 110 104 bytes

n=input()
R=range
s=R(1,n+1)
for k in R(n*2-2/n+1):
 print s
 for i in R(k%2,n-1,2):s[i:i+2]=s[i+1],s[i]

Try it online!

Full program that prints a list of integers for each "change" in the "hunt".

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

C# (Visual C# Interactive Compiler), 128 bytes

x=>{var m=Enumerable.Range(1,x).ToList();for(int i=0,j=0;i<x*2+1-2/x;j=++i%2)for(Print(m);j<x-1;)(m[j],m[++j])=(m[j],m[~-j++]);}

Try it online!

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

Jelly, 28 bytes

¹©Rµ¬ɼks€2UFµ⁺⁻J$п;@WẋL’ẸƊƊ

Try it online!

A monadic link that takes an integer as its input and returns a list of lists of integers. Could be 16 bytes if only needed to handle numbers 3 and above, and 22 if only 2 and above.

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

JavaScript (ES6), 99 bytes

n=>(z=0,g=a=>[a=a.map((v,i)=>v?a[i+=i+z&1||-1]||v:i+1),...z++^2*n^'027'[n]?g(a):[]])([...Array(n)])

Try it online!

Commented

n => (                  // n = input
  z = 0,                // z = counter
  g = a => [            // g = recursive function taking the list of bells a[]
    a =                 // update a[] and append it as a new entry
      a.map((v, i) =>   //   for each value v at position i in a[]:
        v ?             //     if v is defined:
          a[            //       take the bell
            i +=        //         at position:
              i + z & 1 //           i + 1 if i + z is odd
              || -1     //           i - 1 if i + z is even
          ]             //
          || v          //       or leave it unchanged if the above value is undefined
        :               //     else:
          i + 1         //       the array is not yet initialized: set the bell to i + 1
      ),                //   end of map()
    ...z++ ^ 2 * n      // we stop when z = 2n, except for
           ^ '027'[n]   // n = 1 (2n xor 2 -> z = 0) and n = 2 (2n xor 7 -> z = 3)
    ?                   // if the above result is not equal to 0:
      g(a)              //   do a recursive call
    :                   // else:
      []                //   stop
  ]                     //
)([...Array(n)])        // initial call to g with a[] = array of n entries
\$\endgroup\$
1
\$\begingroup\$

C (gcc), 270 224 206 190 bytes

Not a "winning" answer but a fun challenge.

Thanks @ceilingcat for some good cleanup. Learned something new.

Update: further golfed based on how I now know the game to be played.

Further golfed by @ceilingcat

#define w(x)for(i=x;i<n;i++)
#define pb w(0)printf(b+i);puts("");
i,x,n;z(int*b){n=*b;w(0)b[i+n*4]=b[i]=i+49;do{if(n-1)pb;w(x++%2+1)b[i++-1]^=b[i]^=b[i-1]^=b[i];}while(bcmp(b,b+n*4,n*4));pb}

Try it online!

\$\endgroup\$
  • \$\begingroup\$ Great edit. Forgot some of those tricks. \$\endgroup\$ – foreverska Oct 18 at 3:30
0
\$\begingroup\$

Red, 159 bytes

func[n][r: collect[repeat i n[keep i]]repeat i either n < 3[n * n][2 * n + 1][print r:
head r r: skip r i + 1 % 2 until[move r next r(index? r: skip r 2)> n]]]

Try it online!

If two 1s are allowed as a solution for 1:

Red, 155 bytes

func[n][r: collect[repeat i n[keep i]]b: copy r t: on until[print b if t:
not t[b: next b]until[move b next b(index? b: skip b 2)> n]r = b: head b]print b]

Try it online!

\$\endgroup\$
0
\$\begingroup\$

Icon, 119 bytes

procedure f(n)
a:="";a||:=1to n&\z;b:=a
n>1&o:=|(0|1)&write(b)&b[o+(k:=seq(1,2)\n)]:=:b[o+k+1]&b==a
write(b);return
end

Try it online!

\$\endgroup\$
0
\$\begingroup\$

05AB1E, 35 bytes

≠iL[ˆ¯DÁ2£ËNĀ*#θNÈi2ôëćs2ôsš}ε¸˜}í˜

Try it online or verify all test cases.

Not too happy with it.. I have the feeling the duplicated could be golfed somehow, and some of the workarounds could be more elegant (/shorter). Could be 33 bytes if [1,1] instead of 1 is allowed as output; and could be 28 bytes if we'd only had to handle \$\geq3\$.

Explanation (of the 35 bytes version):

≠i              # If the (implicit) input is NOT 1:
  L             #  Create a list in the range [1, (implicit) input]
   [            #  Start an infinite loop:
    ˆ           #   Add the top list to the global array
    ¯D          #   Push the entire global array twice
      Á         #   Rotate the copy once towards the right
       2£       #   Then only leave the first two items
         Ë      #   Check whether those two items are NOT the same
     N          #   Push the current loop-index
      Ā         #   Check whether it is NOT 0 (so not the first iteration)
          *     #   If both checks are truthy:
           #    #    Stop the infinite loop
                #    (after which the TOS global array is output implicitly as result)
     θ          #   Only leave the last list of the global array
      NÈi       #   If the loop-index is even:
         2ô     #    Split the list into parts of size 2
        ë       #   Else (the loop-index is odd):
         ć      #    Extract head; pop and push the remainder-list and first item separated
          s     #    Swap so the remainder-list is at the top of the stack
           2ô   #    Split it into parts of size 2
             s  #    Swap to get the extracted first item again
              š #    And prepend it back in front of the list
        }ε      #   After the if-else: map over the pairs (and potentially loose items):
          ¸     #    Wrap them into a list
           ˜    #    And flatten them
                #   (this is a workaround to wrap multi-digit integers into an inner list,
                #    otherwise an integer like 10 would be reversed to "01"..)
         }í     #   After this map: reverse each inner pair
           ˜    #   And flatten it to a single list again for the next iteration
\$\endgroup\$
0
\$\begingroup\$

Ruby -p, 72 bytes

puts$_=s=[*?1..$_]*''
puts$_ until s[gsub /\B{#{1&$.+=1}}(.)(.)/,'\2\1']

Try it online!

Alternately replaces using the regexps /\B{0}(.)(.)/ and /\B{1}(.)(.)/. The latter matches any two characters other than at the beginning of the string, while the former just matches any two characters--{0} means "repeated zero times" turning the \B into a no-op.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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