18
\$\begingroup\$

Task

Define a mod-fold as a function of the form f(x) = x % a1 % a2 % … % ak, where the ai are positive integers and k ≥ 0. (Here, % is the left-associative modulo operator.)

Given a list of n integers y0, …, yn−1, determine if there exists a mod-fold f so that each yi = f(i).

You may choose and fix any two outputs Y and N for your function/program. If there exists such an f, you must always return/print exactly Y; if not, you must always return/print exactly N. (These could be true/false, or 1/0, or false/true, etc.) Mention these in your answer.

The shortest submission in bytes wins.

Example

Define f(x) = x % 7 % 3. Its values start:

|   x  | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | ...
| f(x) | 0 | 1 | 2 | 0 | 1 | 2 | 0 | 0 | 1 | 2 | ...

Thus, given 0 1 2 0 1 2 0 0 1 2 as input to our solution, we would print Y, as this f generates that sequence. However, given 0 1 0 1 2 as input, we would print N, as no f generates that sequence.

Test cases

The formulas given when the output is Y are just for reference; you must at no point print them.

0 1 2 3 4 5              Y    (x)
1                        N
0 0 0                    Y    (x%1)
0 1 2 0 1 2 0 0 1 2      Y    (x%7%3)
0 0 1                    N
0 1 2 3 4 5 6 0 0 1 2    Y    (x%8%7)
0 1 2 0 1 2 0 1 2 3      N
0 2 1 0 2 1 0 2 1        N
0 1 0 0 0 1 0 0 0 0 1    Y    (x%9%4%3%2)
\$\endgroup\$
  • \$\begingroup\$ Are there any time or memory limits? \$\endgroup\$ – Dennis Jul 17 '16 at 3:30
  • 2
    \$\begingroup\$ Can I output truthy values and falsey values instead? \$\endgroup\$ – Leaky Nun Jul 17 '16 at 8:43
  • 2
    \$\begingroup\$ @Leaky I'd rather you not. I'm not a big fan of truthy-falsey; I'm explicitly trying this as a more objective alternative that still gives you freedom. \$\endgroup\$ – Lynn Jul 17 '16 at 9:06
  • \$\begingroup\$ @Lynn is it just me or you still haven't fixed it? \$\endgroup\$ – Leaky Nun Jul 17 '16 at 9:16
  • \$\begingroup\$ Regarding memory/time constraints: I don't think I'll add any to the challenge itself, but I might run a bounty for the shortest answer in bytes that can answer each one of my test cases in some reasonable time length. \$\endgroup\$ – Lynn Jul 17 '16 at 9:16
7
\$\begingroup\$

Pyth, 14 bytes

}Qm%M+RdUQy_Sl

Returns True/False. Try it online: Demonstration or Test Suite

Explanation:

}Qm%M+RdUQy_SlQ   implicit Q (=input) at the end
             lQ   length of input list
            S     create the list [1, 2, ..., len]
           _      reverse => [len, ..., 2, 1]
          y       generate all subsets (these are all possible mod-folds)
  m               map each subset d to:
        UQ           take the range [0, 1, ..., len-1]
     +Rd             transform each number into a list by prepending it to d
                     e.g. if mod-fold = [7,3], than it creates:
                        [[0,7,3], [1,7,3], [2,7,3], [3,7,3], ...]
   %M                fold each list by the modulo operator
                  this gives all possible truthy sequences of length len
}Q                so checking if Q appears in the list returns True or False

Pyth, 11 bytes

q%M.e+k_tx0

Based on @ferrsum's idea. I actually thought about using the zero-indices for the subset generation, but didn't realize, that all zero-indices has to be the solution already.

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

Python 3, 239 218 bytes

from itertools import*
lambda z:z in[[eval(''.join([str(l)]+['%'+str(i[::-1][k])for k in range(len(i))]))for l in range(len(z))]for i in(i for j in(combinations(range(1,len(z)+1),i+1)for i in range(len(z)))for i in j)]

An anonymous function that takes input of a list z and returns True or False for Y and N.

This uses a method similar to @Jakube 's answer, and although it is essentially a brute force, runs very quickly.

from itertools import*               Import everything from the Python module for
                                     iterable generation
lambda z                             Anonymous function with input list z
combinations(range(1,len(z)+1),i+1)  Yield all sorted i+1 length subsets of the range
                                     [1,len(z)]...
...for i in range(len(z))            ...for all possible subset lengths
(i for j in(...)for i in j)          Flatten, yielding an iterator containing all possible
                                     mod-fold values as separate lists
...for i in...                       For all possible mod-fold values...
...for k in range(len(i))            ...for all mod-fold values indices k...
...for l in range(len(z))            ...for all function domain values in [0,len(z)-1]...
[str(l)]+['%'+str(i[::-1][k])...]    ...create a list containing each character of the
                                     expression representing the function defined by the
                                     mod-fold values (reversed such that the divisors
                                     decrease in magnitude) applied to the domain value...
 eval(''.join(...))                  ...concatenate to string and evaluate...
 [...]                               ...and pack all the values for that particular
                                     function as a list
 [...]                               Pack all lists representing all functions into a list
 ...:z in...                         If z is in this list, it must be a valid mod-fold, so
                                     return True. Else, return False

Try it on Ideone

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

Python 2, 69 bytes

f=lambda a,i=0:i/len(a)or a[i]in[a[i-1]+1,i,0][i<=max(a)::2]*f(a,i+1)

Uses True/False.

The answer to what characterizes a mod-foldable series turns out to be less interesting than it seems at first. It is a series of the form 0, 1, ..., M - 1, 0, 1, ... x1, 0, 1, ..., x2, ... such that for all i, 0 <= xi < M. Such a sequence can be produced by the mod chain of all the (0-based) indices of the zeroes in the array, excluding the first.

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

Jelly, 19 15 14 bytes

LṗLUZ’1¦%/sLe@

Returns 1 for truthy, 0 for falsy. Try it online!

The algorithm is O(nn), where n is the length of the list, making it too slow and memory-intensive for most of the test cases.

A modified version – which replaces the second L with a 5 – can be used to verify all test cases. Note that this modified version won't work for arbitrarily long lists.

How it works

LṗLUZ’1¦%/sLe@  Main link. Argument: A (array of integers)

L L             Yield the length l of A.
 ṗ              Take the l-th Cartesian power of [1, ..., l], i.e., construct
                all arrays of length l that consist of elements of [1, ..., l].
   U            Upend/reverse each array. This way, the first l arrays start
                with [1, ..., l], as do the next l arrays, etc.
    Z           Zip/transpose the array of arrays.
     ’1¦        Decrement the first array to map [1, ..., l] to [0, ..., l - 1].
        %/      Reduce the array's columns by modulus/residue.
          sL    Split the result into chunks of length l.
            e@  Verify if A belongs to the resulting array.
\$\endgroup\$
  • \$\begingroup\$ Can you add an explanation? As someone who hasn't used Jelly (yet), I have no idea how it works. \$\endgroup\$ – Steven H. Jul 17 '16 at 8:12
  • \$\begingroup\$ I'll add one as soon as I'm done golfing. There still are a few things I want to try first. \$\endgroup\$ – Dennis Jul 17 '16 at 19:17
  • \$\begingroup\$ I've (given up and) added an explanation. \$\endgroup\$ – Dennis Jul 18 '16 at 0:04
3
\$\begingroup\$

JavaScript (ES6), 98 bytes

a=>a.every((n,i)=>n?n<(l+=p==i)&&n==p++:p=1,l=p=1)

Saved 48 bytes by switching to @Feersum's discovery. Any given value n in the array is either zero, in which case the next prediction p is 1, or it equals the next prediction, in which case p is incremented. We also measure the length l of the initial sequence by comparing p to i, as n must always be less than l at all times.

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

Python 2, 103 99 bytes

f=lambda l,r:r==x or l and f(l-1,[t%l for t in r])|f(l-1,r)
x=input();l=len(x);print+f(l,range(l))

Prints 1 for truthy and 0 for falsy. Test it on Ideone.

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