# Recognize mod-folds

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)

• Are there any time or memory limits? Jul 17, 2016 at 3:30
• Can I output truthy values and falsey values instead? Jul 17, 2016 at 8:43
• @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.
– Lynn
Jul 17, 2016 at 9:06
• @Lynn is it just me or you still haven't fixed it? Jul 17, 2016 at 9:16
• 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.
– Lynn
Jul 17, 2016 at 9:16

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

# 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

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

# Jelly, 1915 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.

• Can you add an explanation? As someone who hasn't used Jelly (yet), I have no idea how it works. Jul 17, 2016 at 8:12
• I'll add one as soon as I'm done golfing. There still are a few things I want to try first. Jul 17, 2016 at 19:17
• I've (given up and) added an explanation. Jul 18, 2016 at 0:04

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

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