# Alice's Tea Party

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]]

• Feb 4, 2018 at 14:13
• Can we return [] instead of [[]] for n = 1? Feb 5, 2018 at 5:57
• Can we do this in c#?If yes,can someone explain Feb 5, 2018 at 11:45
• @Ourous No. The answer should be [[]] because the Mad Hatter's list has length 0. This means that [] is the only possible list (which works since Alice eats the only cake she has before the Mad Hatter comes in), so [[]] is the list of all lists that work. Feb 5, 2018 at 18:38

# Perl, 7875 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. # Python 3, 235191177136134122 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. • 239 bytes (switches to Python 2) Feb 4, 2018 at 19:30 • @cairdcoinheringaahing ty. Added that. Feb 4, 2018 at 19:43 • Edited and fixed some error Feb 4, 2018 at 20:23 • This (133 bytes) should be equivalent. Feb 4, 2018 at 20:36 • Using your same logic, but with a lambda, 120 bytes. Feb 5, 2018 at 6:48 # 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.


# Python 2,130129127123 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.

• Here the input 'n' refers to 2^n ? Please mention that. Feb 5, 2018 at 5:17
• @Manish Kundu: quite right. Feb 5, 2018 at 5:24

# 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!

# 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.