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\$
  • 1
    \$\begingroup\$ (should "add or subtract 1" performed modulo I_i+1? Can you reach 0 from I_i?) \$\endgroup\$ – user202729 May 10 '18 at 17:01
  • \$\begingroup\$ @user202720 No I didn't intend that. \$\endgroup\$ – Anush May 10 '18 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 '18 at 18:15
  • \$\begingroup\$ @l4m2 For the purposes of the complexity analysis assume k goes to infinity. \$\endgroup\$ – Anush May 11 '18 at 18:17
  • \$\begingroup\$ @Anush so how do bit width go? \$\endgroup\$ – l4m2 May 11 '18 at 18:43
5
\$\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\$
  • \$\begingroup\$ How long does the inner while loop run for? \$\endgroup\$ – Anush May 10 '18 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\$ – user202729 May 10 '18 at 16:46
  • \$\begingroup\$ This is a very nice solution. \$\endgroup\$ – Anush May 10 '18 at 16:51
  • \$\begingroup\$ You can save a byte by replacing not 0<= with not-1<. \$\endgroup\$ – Mnemonic May 10 '18 at 16:58
  • 1
    \$\begingroup\$ Could you use yield t instead of print(t,flush=1)? \$\endgroup\$ – Dennis May 10 '18 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
    \$\begingroup\$ Measuring in bit complexity, iteration index is O(k) bits, so division k times may take O(k²) time... \$\endgroup\$ – user202729 May 11 '18 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\$
  • 1
    \$\begingroup\$ For the example in the question with 2 1 3 your code needs 3 2 4 as input it seems. \$\endgroup\$ – Anush May 11 '18 at 9:15
  • 1
    \$\begingroup\$ while(true) can be while(1<2) \$\endgroup\$ – ovs May 11 '18 at 13:27

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.