11
\$\begingroup\$

A magic sequence is a sequence of non-negative integers x[0..n-1] such that there are exactly x[i] instances of i

For instance, 6,2,1,0,0,0,1,0,0,0 is a magic sequence since there are 6 0's, 2 1’s, and so on.

Write a function which when given n, outputs all magic sequences of length n


The program that can produce the correct output for the highest value of n within 10 seconds win. (All programs are welcome, though)

For example, Alice's program can deal with upto n=15 within 10 seconds while Bob's can deal with upto n=20 within the same time. Bob wins.

Platform: Linux 2.7GHz @ 4 CPUs

\$\endgroup\$
  • 5
    \$\begingroup\$ Welcome to PPCG! This is a great challenge, but you need a winning criterion. For example, you could say that the winner is the shortest program. \$\endgroup\$ – Ypnypn May 14 '15 at 0:12
  • 1
    \$\begingroup\$ Relevant: Self-descriptive number \$\endgroup\$ – Sp3000 May 14 '15 at 0:23
  • 2
    \$\begingroup\$ Please don't change the winning criterion after answers have been posted. Also, this was much better as a code golf than as fastest code, at least in my opinion. \$\endgroup\$ – Alex A. May 14 '15 at 0:55
  • 2
    \$\begingroup\$ @xnor you can start by generating the integer partitions of n and checking if they can be self-descriptive. \$\endgroup\$ – Martin Ender May 14 '15 at 1:36
  • 2
    \$\begingroup\$ What's the smallest n>5 with a solution not of the form [n-4, 2, 1, ..., 0, 0, 1, 0, 0, 0]? I've looked up to n=20 and not found one, and wondering if I'm making an error. \$\endgroup\$ – xnor May 14 '15 at 2:43
19
\$\begingroup\$

Python, n≈108

def magic_sequences(n):
    if n==4:
        return (1, 2, 1, 0),(2, 0, 2, 0) 
    elif n==5:
        return (2, 1, 2, 0, 0),
    elif n>=7:
        return (n-4,2,1)+(0,)*(n-7)+(1,0,0,0),
    else:
        return ()

This uses the fact, which I'll prove, that the only Magic sequences of length n are:

  • [1, 2, 1, 0] and [2, 0, 2, 0] for n=4
  • [2, 1, 2, 0, 0] for n=5
  • [n-4, 2, 1, 0, 0, ..., 0, 0, 1, 0, 0, 0] for n>=7

So, for n>=7, one only needs to return a huge tuple. I can do this for up to roughly n=10^8 on my laptop, which is likely limited by memory; any more and it freezes up. (Thanks to trichoplax for the idea of using tuples rather than lists.) Or, if one can instead print a dictionary of nonzero entries, {0:n-4, 1:2, 2:1, (n-4):1}, one can do this for ginormous n.

I prove the uniqueness for n>=7; the other ones can be checked by brute force or casework.

The sum of the entries of l is the total count of all numbers of the list, which is its length n. The list has l[0] zeroes, and so n-l[0] nonzero entries. But by definition l[0] must be nonzero or we get a contradiction, and each of the other nonzero entries is at least 1. This already accounts for a sum of l[0] + (n-l[0]-1)*1 = n-1 out of the overall sum of n. So not counting l[0], there can be at most one 2 and no entry bigger than 2.

But that means the only nonzero entries are l[0], l[1], l[2], and l[l[0]], whose values are at most l[0] and a permutation of 1,1,2, which gives a maximum sum of l[0]+4. Since this sum is n, which is at least 7, we have l[0]>=3, and so l[l[0]]=1. Now, there's at least one 1, which means l[1]>=1, but if l[1]==1 that's another 1, so l[1]>=2, which implies l[1] is the lone 2. This gives l[2]=1, and all the remaining entries are 0, so l[0]=n-4, which completes the solution.

\$\endgroup\$
  • \$\begingroup\$ And the language is ...? \$\endgroup\$ – edc65 May 14 '15 at 7:55
  • \$\begingroup\$ @edc65 It looks like python. But I'm not sure. \$\endgroup\$ – Ismael Miguel May 14 '15 at 8:10
4
\$\begingroup\$

Python 3, n≈40

def plausible_suffix(l,N):
    if sum(l)>N:
        return False

    pairs = [(N-1-i,l[i]) for i in range(len(l))]

    if sum(i*x for i,x in pairs)>N:
        return False

    num_remaining = N - len(l)

    for index, desired_count in pairs:
        count = l.count(index)
        more_needed = desired_count - count
        if more_needed<0: 
            return False
        num_remaining -= more_needed
        if num_remaining<0:
            return False
    return True

plausible_func = plausible_suffix

def generate_magic(N):
    l=[0]
    while l:
        extend = False
        if plausible_func(l,N):
            if len(l)==N:
                yield l[::-1]
            else:
                extend = True
        if extend:
            l.append(0)
        else:
            while l[-1]>=N-2:
                l.pop(-1)
                if not l:raise StopIteration
            l[-1]+=1

n=40 #test parameter

if n>0:
    for x in generate_magic(n):
        print(n,x)

Does a breadth-first search of possible lists, filling in entries from right to left, stopping the search at a suffix if it isn't plausible, which can happen if:

  • The sum of the entries in the suffix exceeds n (the sum for the whole list must be n)
  • The weighted sum of i*l[i] in the suffix exceeds n (the sum for the whole list must be n)
  • Any number appears in the suffix more times that the suffix says it should
  • The number of remaining unfilled spots is too small to account for all numbers that need to appear more times.

I had original tested prefixes left to right, but that went more slowly.

The outputs up to n=30 are:

4 [1, 2, 1, 0]
4 [2, 0, 2, 0]
5 [2, 1, 2, 0, 0]
7 [3, 2, 1, 1, 0, 0, 0]
8 [4, 2, 1, 0, 1, 0, 0, 0]
9 [5, 2, 1, 0, 0, 1, 0, 0, 0]
10 [6, 2, 1, 0, 0, 0, 1, 0, 0, 0]
11 [7, 2, 1, 0, 0, 0, 0, 1, 0, 0, 0]
12 [8, 2, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0]
13 [9, 2, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0]
14 [10, 2, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0]
15 [11, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0]
16 [12, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0]
17 [13, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0]
18 [14, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0]
19 [15, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0]
20 [16, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0]
21 [17, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0]
22 [18, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0]
23 [19, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0]
24 [20, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0]
25 [21, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0]
26 [22, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0]
27 [23, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0]
28 [24, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0]
29 [25, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0]
30 [26, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0]

Except for the first three lists [1, 2, 1, 0], [2, 0, 2, 0], [2, 1, 2, 0, 0], there is exactly one list of each length n>6, and it has the form [n-4, 2, 1, ..., 0, 0, 1, 0, 0, 0]. This pattern persists up to at least n=50. I suspect it holds forever, in which case it's trivial to output a huge number of these. Even if not, a mathematical understanding on the possible solutions would greatly speed up a search.

\$\endgroup\$
  • \$\begingroup\$ @Ypnypn I've special-cased n=0. I'd missed that we're returning the result for a single n, not counting up n's. This gets me up to n=40. \$\endgroup\$ – xnor May 14 '15 at 4:17
0
\$\begingroup\$

Pyth - 15 bytes

Uses brute force by all possible sequences of len n and then filters.

f.A.eq/TkYT^UQQ

Full explanation coming soon.

Try it here online.

\$\endgroup\$
  • 2
    \$\begingroup\$ FYI, the OP changed the winning criterion to fastest code. \$\endgroup\$ – Alex A. May 14 '15 at 0:55
  • 2
    \$\begingroup\$ Regardless of the winning criterion, here's a 3 byte golf: ` fqm/TdQT^UQQ` \$\endgroup\$ – Jakube May 14 '15 at 7:11
0
\$\begingroup\$

K, 26 bytes

{f@&{x~(+/x=)'!#x}'f:!x#x}

Like Maltysen's approach, brute force. The heart of the program is a predicate which tests whether a given vector is "magic":

{x~(+/x=)'!#x}

Build an iota vector as long as the input vector (!#x), count the occurrences of each digit ((+/x=)') and compare the result with the input vector (x~). If there's a match, you have a magic sequence.

Unfortunately, this first stab seems to be pretty slow. Testing using Kona on my laptop it takes about 12 seconds to handle n=7. I need to give this a bit more thought.

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