### "You can see a lot by just looking" --Yogi Berra

There's a reason Code Jam urges one to look at examples--in this problem, it points you towards the constraint on the Ys that I didn't see because I only considered the most/least significant digit. And now, we'll see whether it can point us at how we might generate

for some values of n. Hey, wait; these are palindromes, so let's just look at the top half. After all, the rest is redundant, and it's the top half that determines the ordering.

Oops. 10 breaks the pattern, because you can't have five ones. 12 shows a skip in the middle where there would otherwise be five ones, and as n increases, we'll presumably see more of those.

So there

UPDATE: I'm not sure there is a way; it's tempting to take the interval including all the numbers and then

**noTwos**in ascending numerical order.**noTwos**, like**oneTwos**, is based on the result of**justOnes**. For now, at least, let's ignore the case of an odd number of digits; for them,**justOnes**simply returns the same values as for the next lower number of digits with a zero in the middle. Now, to take a look at**putStr $ unlines $ map show (sort (justOnes (2 * n) (min (n - 1) 3))**for some values of n. Hey, wait; these are palindromes, so let's just look at the top half. After all, the rest is redundant, and it's the top half that determines the ordering.

**4:**

**10**

1111

**6:**

**100**

101

110

111101

110

111

**8:****1000**

1001

1010

1011

1100

1101

1110

11111001

1010

1011

1100

1101

1110

1111

**10:**

**10000****10001****10010****10011****10100****10101****10110****10111****11000****11001****11010****11011****11100****11101****11110**Oops. 10 breaks the pattern, because you can't have five ones. 12 shows a skip in the middle where there would otherwise be five ones, and as n increases, we'll presumably see more of those.

**12:**

**100000****100001****100010****100011****100100****100101****100110****100111****101000****101001****101010****101011****101100****101101****101110****110000 <-****110001****110010****110011****110100****110101****110110****111000****111001****111010****111100****So, if we pretend these are binary numbers, up to eight digits (total), they go from 10...0 to 11..1. Past eight digits, they go from 10...0 to 11110..0, skipping any value that has more than four ones.**

So there

*is*a pattern. How to generate it efficiently?UPDATE: I'm not sure there is a way; it's tempting to take the interval including all the numbers and then

**filter (\x -> popCount x <= o + 1)**but that's a lot of numbers to generate and then mostly throw away; up at the high end for numbers up to a googol, that'd be around 28 million values that you'd grind out and then throw away all but a few thousand... and then you get to create the palindrome from the top half and switch back to base 10 on top of that. I don't think that's going to cut it... so, back to getting the list of lists of ones to come out in what corresponds to ascending order for the values**justOnes**generates.
## Comments