7
\$\begingroup\$

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]]
\$\endgroup\$
  • \$\begingroup\$ Related. \$\endgroup\$ – user202729 Feb 4 '18 at 14:13
  • \$\begingroup\$ Can we return [] instead of [[]] for n = 1? \$\endgroup\$ – Οurous Feb 5 '18 at 5:57
  • \$\begingroup\$ Can we do this in c#?If yes,can someone explain \$\endgroup\$ – pradeep reddy Feb 5 '18 at 11:45
  • \$\begingroup\$ @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. \$\endgroup\$ – 0WJYxW9FMN Feb 5 '18 at 18:38
2
\$\begingroup\$

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.

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

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.

\$\endgroup\$
  • \$\begingroup\$ 239 bytes (switches to Python 2) \$\endgroup\$ – caird coinheringaahing Feb 4 '18 at 19:30
  • \$\begingroup\$ @cairdcoinheringaahing ty. Added that. \$\endgroup\$ – Manish Kundu Feb 4 '18 at 19:43
  • \$\begingroup\$ Edited and fixed some error \$\endgroup\$ – Manish Kundu Feb 4 '18 at 20:23
  • 1
    \$\begingroup\$ This (133 bytes) should be equivalent. \$\endgroup\$ – Dennis Feb 4 '18 at 20:36
  • 1
    \$\begingroup\$ Using your same logic, but with a lambda, 120 bytes. \$\endgroup\$ – Chas Brown Feb 5 '18 at 6:48
1
\$\begingroup\$

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

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.

\$\endgroup\$
  • \$\begingroup\$ Here the input 'n' refers to 2^n ? Please mention that. \$\endgroup\$ – Manish Kundu Feb 5 '18 at 5:17
  • \$\begingroup\$ @Manish Kundu: quite right. \$\endgroup\$ – Chas Brown Feb 5 '18 at 5:24
1
\$\begingroup\$

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!

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

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.

\$\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.