13
\$\begingroup\$

Input: An array I of k positive integers. The integers will be no larger than 100 and k ≤ 100.

Output: Your code must output all possible arrays O of non-negative integers of length k with the restriction that 0 ≤ Oi ≤ Ii. To get from one array to the next you may add or subtract 1 to one value in the array. Your code must not output the same array twice. If the number of different arrays to be output is very large, your code should just carry on outputting forever until it is killed.

Examples

  • If I is an array of k ones then this is exactly the problem of iterating over all Gray codes of bit width k, except that the first and the last element do not need to be reachable in one step.

  • If I = [2,1] then one possible ordering of the output arrays is (0,0),(0,1),(1,1),(1,0),(2,0),(2,1)

  • If I = [2,1,3] then one possible ordering of the output arrays is (0,0,0),(0,0,1),(0,0,2),(0,0,3),(0,1,3),(0,1,2),(0,1,1),(0,1,0),(1,1,0),(1,1,1),(1,1,2),(1,1,3),(2,1,3),(2,1,2),(2,1,1),(2,1,0),....

This is a code-golf challenge, the submission with the source code with the shortest length wins. Don't let the short answers in golfing languages discourage you from posting an answer in other languages. Try to come up with the shortest answer in any language.

This is also a restricted-complexity challenge. Every new array should be output with O(k) time elapsing since the previous outputted array (or the start of the program for the first array outputted). This means that the running time per new output array (they are each of length k) should be no greater than O(k). That is it should take time proportion to k and not, for example k2 or 2k. Note this is not the average time per output but the worst case time for each and every array outputted.

You can assume that all arithmetic on 64 bit integers can be performed in constant time as can reading and outputting them as well as assignment and looking up and changing values in arrays.

One consequence of the restricted-complexity is that solutions that only output at program exit are not acceptable.

\$\endgroup\$
5
  • 1
    \$\begingroup\$ (should "add or subtract 1" performed modulo I_i+1? Can you reach 0 from I_i?) \$\endgroup\$
    – DELETE_ME
    May 10, 2018 at 17:01
  • \$\begingroup\$ @user202720 No I didn't intend that. \$\endgroup\$
    – user9207
    May 10, 2018 at 19:19
  • \$\begingroup\$ How do the complexity work when n and k are limited? assuming they go to infinity with bit width how to go \$\endgroup\$
    – l4m2
    May 11, 2018 at 18:15
  • \$\begingroup\$ @l4m2 For the purposes of the complexity analysis assume k goes to infinity. \$\endgroup\$
    – user9207
    May 11, 2018 at 18:17
  • \$\begingroup\$ @Anush so how do bit width go? \$\endgroup\$
    – l4m2
    May 11, 2018 at 18:43

4 Answers 4

4
\$\begingroup\$

Python 3, 116 bytes

def f(a):
 l=len(a);t=[0]*l;d=[1]*l
 while 1:
  i=0;yield t
  while not-1<t[i]+d[i]<=a[i]:d[i]*=-1;i+=1
  t[i]+=d[i]

Try it online!

Thanks Mnemonic for -1 byte.

Generator function. (thanks Dennis for reminding me, I forgot the feature exists) If the output should be printed to stdout then use print(t,flush=1) for 9 additional bytes, or if Python is called with -u, print(t) suffices for +1 bytes.

Stops with an error (IndexError). If you want to call this function and then continue the program, you have to catch it.

\$\endgroup\$
7
  • \$\begingroup\$ How long does the inner while loop run for? \$\endgroup\$
    – user9207
    May 10, 2018 at 16:45
  • \$\begingroup\$ @Anush At most k steps, because at each step i increases by 1 and after k steps i==k and d[i] causes an error. \$\endgroup\$
    – DELETE_ME
    May 10, 2018 at 16:46
  • \$\begingroup\$ This is a very nice solution. \$\endgroup\$
    – user9207
    May 10, 2018 at 16:51
  • \$\begingroup\$ You can save a byte by replacing not 0<= with not-1<. \$\endgroup\$
    – user48543
    May 10, 2018 at 16:58
  • 1
    \$\begingroup\$ Could you use yield t instead of print(t,flush=1)? \$\endgroup\$
    – Dennis
    May 10, 2018 at 17:11
2
\$\begingroup\$

Stax, 22 bytes

▒)∙ñ╚▀NK♀F☺S(A#P`░]╪Db

Run and debug it

Here's a big one to show the asymptotic behavior Press run.

Unpacked, ungolfed, and commented, it looks like this.

,           pop from input to main stack
W           run the rest of the program repeatedly until explicitly cancelled
  cJP       copy top of stack and print, delimited by spaces
            get the index to mutate
  i^            iteration index + 1
  x{^|%}I       repeatedly apply divmod using l[k]+1 from input
                get the index of the first value that returns modulus >0
  cU=C      if the result is -1 (no match), then terminate the program
            get the direction to mutate
  s             get the "div" part of the last div operation called "d"
  ^|1           -1 ^ (d+1)
  ~{+}&     increment element in array at the index by the calculated amount

Run this one

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Measuring in bit complexity, iteration index is O(k) bits, so division k times may take O(k²) time... \$\endgroup\$
    – DELETE_ME
    May 11, 2018 at 6:44
1
\$\begingroup\$

JavaScript (Node.js), 114 bytes

a=>{b=a.map(_=>0);c=a.map(_=>1);for(i=0;a[i];b[i]+=c[i]||-1){console.log(b);for(i=0;b[i]==a[i]*c[i];i++)c[i]^=1;}}

Try it online! Ungolfed:

function ggray(maxima) {
    var current = Array(maxima.length).fill(0);
    var flag = Array(maxima.length).fill(1);
    for (;;) {
        console.log(current);
        for (var i = 0; ; i++) {
            if (i == maxima.length) return;
            if (current[i] != maxima[i] * flag[i]) break;
            flag[i] = 1 - flag[i];
        }
        if (flag[i]) current[i]++;
        else current[i]--;
    }
}
\$\endgroup\$
1
\$\begingroup\$

Kotlin, 181 178 bytes

Thanks to: Anush pointed out I misunderstood the challenge saving 2 bytes. ovs pointed out a 1 byte savings.

val p={a:List<Int>->var l=a.size
val v=Array(l,{0})
val i=Array(l,{1})
l-=1
o@while(0<1){println(v)
var p=l
while(v[p]+i[p]!in 0..a[p]){i[p]*=-1
p-=1
if(p<0)break@o}
v[p]+=i[p]}}

Try it online!

\$\endgroup\$
2
  • 1
    \$\begingroup\$ For the example in the question with 2 1 3 your code needs 3 2 4 as input it seems. \$\endgroup\$
    – user9207
    May 11, 2018 at 9:15
  • 1
    \$\begingroup\$ while(true) can be while(1<2) \$\endgroup\$
    – ovs
    May 11, 2018 at 13:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy