// Input expected is 1 to 100 integers that have a // valid range of 1 to 100. /* Created for this code golf challenge: https://codegolf.stackexchange.com/questions/164558 Generalized Gray codes 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 <= O_i <= I_i. 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 k^2 or 2^k. 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. */ // Overload println to display the contents of the // array. // Force println to output the array contents. fun println(array: Array) = print("(${array.contentToString()})\n") // Expanded version of the code. fun process(array: List) { // Get the number of nested arrays. Allocate the // values as zeroes and the increments as one. // Decrement the length. While there is a // combination to print, display it and figure // out the next one. var length = array.size val value = Array(length, {0}) val increment = Array(length, {1}) length -= 1 outer@ while (0<1) { // Display the current values, default to the // last nested array, and loop until we figure // out what array value needs to be modified. // We are testing the current value in the // position plus the increment for that // position is within the range for that // position. If not, we need to change the // position. println(value) var position = length while (value[position]+increment[position] !in 0..array[position]) { // Switch direction for this position, // decrement to the next position, and exit // if beyond the first array. increment[position] *= -1 position -= 1 if (position < 0) break@outer } // while // Update the current value by it's current // increment. value[position] += increment[position] } // while } // process // Test driver fun main(args: Array) { // 178 bytes val p={a:List->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 reading the array values in, split into a // list, map the strings into integers, verify // their range, and store them. On out of // range, cause an exception. try { val data = readLine()!!.split(" ").map{string -> val value = string.toInt() if (value in 0..100) value else throw IllegalArgumentException( "Value out of range!")} // Verify that we got a valid number of elements. // If so, process the data. Otherwise, cause an // exception. if (data.size < 1 || data.size > 100) throw IllegalArgumentException( "Too many arguments!") p(data) // Otherwise, an exception occurred so complain // and process the default. } catch (error: Throwable) { print("Bad input!\n") p(listOf(3, 2, 2)) } // try } // main

array cg