Alice's Tea Party

Question

There are n places set around a circular table. Alice is sat on one of them. At each place, there's a cake. Alice eats her cake, but it doesn't taste very nice. Then the Mad Hatter comes in. He gives Alice a list of n-1 numbers, each between 1 and n-1. For each item i in the list, Alice has to move around i places and eat the cake there if there is one. However, Alice will be able to choose whether to move clockwise or anticlockwise for each item in the list. She doesn't like the cakes, so she is trying not to eat them.

Given an integer n, output all the possible lists the Mad Hatter could use to force Alice to eat all the cakes (represented as a tuple/list of tuples/lists of integers or some tuples/lists of integers separated by newlines). Note that it is possible for the Mad Hatter to force Alice to eat all the cakes if and only if n is a power of two, so you may assume that n is a power of two. Make your code as short as possible.

You may also take in x such that 2^x=n if that helps. For example, you may take in 2 instead of 4, 3 instead of 8, etc.

The order in which your program returns the possible lists does not matter.

Test Cases

1 -> [[]]
2 -> [[1]]
4 -> [[2, 1, 2], [2, 3, 2]]
8 -> [[4, 2, 4, 1, 4, 2, 4], [4, 2, 4, 1, 4, 6, 4], [4, 6, 4, 1, 4, 2, 4], [4, 6, 4, 1, 4, 6, 4], [4, 2, 4, 3, 4, 2, 4], [4, 2, 4, 5, 4, 2, 4], [4, 2, 4, 7, 4, 2, 4], [4, 2, 4, 3, 4, 6, 4], [4, 6, 4, 3, 4, 2, 4], [4, 2, 4, 5, 4, 6, 4], [4, 6, 4, 5, 4, 2, 4], [4, 2, 4, 7, 4, 6, 4], [4, 6, 4, 7, 4, 2, 4], [4, 6, 4, 3, 4, 6, 4], [4, 6, 4, 5, 4, 6, 4], [4, 6, 4, 7, 4, 6, 4]]

Answer 1

Python 3, 235 191 177 136 134 122 119 bytes

lambda n:[*product(*[[*(i==n/2and range(1,n,2)or[[n/4,3*n/4],[n/2]][i%2])]for i in range(1,n)])]
from itertools import*

Try It Online

Thanks To Dennis for -31 bytes and ChasBrown for -14 bytes and Mr.XCoder for -1 byte.

Numbers appear in the decimal form, eg:4.0.

Answer 2

Perl, 78 75 72 bytes

Includes +1 for n

perl -nE '$"=",";say<@{[map"{@{[map$`*($_-.5)/@z,@z=1..$_&-$_]}}",/$/..$_-1]}\\ >' <<< 8

Prints a space separated sequence of comma separated numbers (replace the final space by \n for a more readable output)

Uses a string substitution inside a string substitution.

Answer 3

Jelly, 18 bytes

żN$Œp+\€%ṬȦ
’ṗ’çÐf

This is a brute-force solution that tests all (n - 1)^{n - 1} potential solutions one by one.

Try it online!

Verification

$ time jelly eun 'żN$Œp+\€%ṬȦ¶’ṗ’çÐf' 8
[[4, 2, 4, 1, 4, 2, 4], [4, 2, 4, 1, 4, 6, 4], [4, 2, 4, 3, 4, 2, 4], [4, 2, 4, 3, 4, 6, 4], [4, 2, 4, 5, 4, 2, 4], [4, 2, 4, 5, 4, 6, 4], [4, 2, 4, 7, 4, 2, 4], [4, 2, 4, 7, 4, 6, 4], [4, 6, 4, 1, 4, 2, 4], [4, 6, 4, 1, 4, 6, 4], [4, 6, 4, 3, 4, 2, 4], [4, 6, 4, 3, 4, 6, 4], [4, 6, 4, 5, 4, 2, 4], [4, 6, 4, 5, 4, 6, 4], [4, 6, 4, 7, 4, 2, 4], [4, 6, 4, 7, 4, 6, 4]]

real    85m33.780s
user    85m35.903s
sys     0m0.060s

How it works

’ṗ’çÐf       Main link. Argument: n (integer)

’ ’          Yield n-1.
 ṗ           Cartesian power; yield all vector of length n-1 over [1, ..., n-1].
   çÐf       Filter; keep vectors v for which the helper link, called with left
             argument v and right argument n, returns a truthy value.


żN$Œp+\€%ṬȦ  Helper link. Left argument: v (vector). Right argument: n (integer)

żN$          Zip v with -v, mapping [v(1), ... v(n-1)] to
             [[v(1), -v(1)], ..., [v(n-1), -v(n-1)]].
   Œp        Take the Cartesian product of all pairs.
     +\€     Take the cumulative sum of each resulting vector.
        %    Take all cumulative sums modulo n.
             A valid solution results in a permutation of [1, ..., n-1].
         Ṭ   Untruth; map each resulting vector to a Boolean array with 1's at
             the specified indices, 0's elsewhere.
          Ȧ  Test if the resulting array contains only non-zero integers.

Answer 4

Python 2,130 129 127 123 121 bytes

f=lambda n:n>1and(lambda D:[l+[k]+r for l in D for r in D for k in range(1,n,2)])([[i*2for i in a]for a in f(n/2)])or[[]]

Try it online!

Edited: Takes as input n (which must be a power of 2) as the number of seats at the Hatter's table.

Answer 5

Python 2, 81 bytes

f=lambda n,i=1,*l:i/n*[l]or sum([f(n,i+1,x,*l)for x in range(n)if x*i%n==n/2],[])

Try it online!

---

Python 2, 92 bytes

f=lambda n,c=1:[x+[c*y]+z for y in range(1,n,2)for x in f(n/2,c*2)for z in f(n/2,c*2)]or[[]]

Try it online!

Answer 6

Clean, 194 ... 172 bytes

Still in the progress of cutting more off.

import StdEnv

\n=let?_[]_=1>0;?l[i:j]m=all((\e= ?(updateAt e(1<0)l)j e&&l!!e)o\e=e-e/n*n)[m+i,n+m-i]in[k\\k<-iter(n-1)(\e=[[h:t]\\h<-[1..n],t<-e])[[]]| ?[q>1\\q<-[1..n]]k 0]

Try it online!

Lambda function which does a brute-force over every combination of indices up to length n-1.
It still runs in about 5 seconds, because of compiler magic.