Monthly Archives: October 2009

A solution to Einav’s programming puzzle

Here’s a solution to the array problem my friend Einav posed. If you haven’t looked at the puzzle, check it out first. A summary: you have a 9×27 array of positive and negative numbers. You can flip the sign of an entire row or column (as many of them as you like). The goal is to make all the rows and columns sum to positive numbers (or zero), and then to find the solution (there are more than one) that has the lowest overall sum.

Here’s the code that finds the solution, in the J programming language:

list=:_9]\33 30 10 _6 18 _7 _11 23 _6 16 _19 9 _26 _8 _19 _8 _21 _14 17 12 _14 31 _30 13 _13 19 16 _6 _11 1 17 _12 _4 _7 14 _21 18 _31 34 _22 17 _19 20 24 6 33 _18 17 _15 31 _5 3 27 _3 _18 _20 _18 31 6 4 _2 _12 24 27 14 4 _29 _3 5 _29 8 _12 _15 _7 _23 23 _9 _8 6 8 _12 33 _23 _19 _4 _8 _7 11 _12 31 _20 19 _15 _30 11 32 7 14 _5 _23 18 _32 _2 _31 _7 8 24 16 32 _4 _10 _14 _6 _1 0 23 23 25 0 _23 22 12 28 _27 15 4 _30 _13 _16 _3 _3 _32 _3 27 _31 22 1 26 4 _2 _13 26 17 14 _9 _18 3 _20 _27 _32 _11 27 13 _17 33 _7 19 _32 13 _31 _2 _24 _31 27 _31 _29 15 2 29 _15 33 _18 _23 15 28 0 30 _4 12 _32 _3 34 27 _25 _18 26 1 34 26 _21 _31 _10 _13 _30 _17 _12 _26 31 23 _31 _19 21 _17 _10 2 _23 23 _3 6 0 _3 _32 0 _10 _25 14 _19 9 14 _27 20 15 _5 _27 18 11 _6 24 7 _17 26 20 _31 _25 _25 4 _16 30 33 23 _4 _4 23
sumOfRows =: ([: +/"1 [: |: ] * [: |: _1 + 2 * [: #: [: i. 2 ^ #)"1 list
rowSigns =: (;/@:,/@:>)"2 {|:(_1;_1 1;1) {~ (_1&<+0&<) sumOfRows
candidates =:,/((_4]\4#"3 (_1 + 2 * #:i.2^9) (* &. |:)" 1 _ list)  * (>rowSigns))
theAnswers =: (] #~ [: (0&<@:+/@:(0&<) * */@:(_1&<)) [: |: +/"2) candidates
theSums =: +/"1 +/"1 theAnswers
theBestAnswer =: ~. ((theSums = ] theBestSum =: <./ theSums) # theAnswers)

 

The basic method is:

1. sumOfRows: Find the sums of all the rows for each permutation of flipping the columns (9 columns = 512 flipping permutations.

2. rowSigns: Find how the rows will have to be flipped in order to make them all positive for each of the column permutations. Note that if any of the rows sum to zero, then they have to be accounted for both ways. The most number of zeroes in any row is two, so that means that some of the column permutations have four possible row solutions.

3. candidates: Find the actual resulting arrays for each column permutation/row solutions. There are 624.

4. theAnswers: Find all the candidates where all the columns are positive after the row solution has been applied. There are 368.

5. theSums: Find the sums of all the answers.

6. theBestAnswer/theBestSum: Find the smallest sum and the corresponding answer. This is kind of cheating on the line count since I did a double assignment, but that’s perfectly acceptable in J. I just don’t particularly like the way I did it. The double reference to theSums is annoying. Line 5 is annoying in general. If I figured out how to do just a single reference to theSums in this line, I would sub in line 5 and get rid of it.

Interesting to note: I had originally thought to look for the solution by first manipulating the signs of the numbers individually to find the smallest possible positive sums, and then work up through them to see which were possible. I didn’t figure out a way to do that, so I fell back on this (relatively) brute force method. Obviously, my first plan would have worked best if the correct answer was fairly low in the sequence; if I ended up trying many potential solutions that didn’t work, it could take as long as the brute force method I ended up with. The interesting thing is that for this particular array, the smallest possible result was in fact possible. I tried another random array to see if (for some unforeseen reason) that is always the case, and it isn’t.

A programming puzzle from Einav

Updated: Never post late at night. The below array is the correct source.

My friend Einav gave me this programming puzzle to work on. Given this array of positive and negative numbers:

33 30 10 -6 18 -7 -11 23 -6 16 -19 9 -26 -8 -19 -8 -21 -14 17 12 -14 31 -30 13 -13 19 16 -6 -11 1 17 -12 -4 -7 14 -21 18 -31 34 -22 17 -19 20 24 6 33 -18 17 -15 31 -5 3 27 -3 -18 -20 -18 31 6 4 -2 -12 24 27 14 4 -29 -3 5 -29 8 -12 -15 -7 -23 23 -9 -8 6 8 -12 33 -23 -19 -4 -8 -7 11 -12 31 -20 19 -15 -30 11 32 7 14 -5 -23 18 -32 -2 -31 -7 8 24 16 32 -4 -10 -14 -6 -1 0 23 23 25 0 -23 22 12 28 -27 15 4 -30 -13 -16 -3 -3 -32 -3 27 -31 22 1 26 4 -2 -13 26 17 14 -9 -18 3 -20 -27 -32 -11 27 13 -17 33 -7 19 -32 13 -31 -2 -24 -31 27 -31 -29 15 2 29 -15 33 -18 -23 15 28 0 30 -4 12 -32 -3 34 27 -25 -18 26 1 34 26 -21 -31 -10 -13 -30 -17 -12 -26 31 23 -31 -19 21 -17 -10 2 -23 23 -3 6 0 -3 -32 0 -10 -25 14 -19 9 14 -27 20 15 -5 -27 18 11 -6 24 7 -17 26 20 -31 -25 -25 4 -16 30 33 23 -4 -4 23
You can flip the sign of entire rows and columns, as many of them
as you like. The goal is to make all the rows and columns sum to positive
numbers (or zero), and then to find the solution (there are more than one)
that has the smallest overall sum. So for example, for this array:
33  30 -10
-16  19   9
-17 -12 -14
You could flip the sign for the bottom row to get this array:
33  30 -10
-16  19   9
17  12  14
Now all the rows and columns have positive sums, and the overall total is 108.
But you could instead flip the second and third columns, and the second row, to get this array:
33  -30  10
16   19    9
-17   12   14
All the rows and columns still total positive, and the overall sum is just 66. So this solution is better (I don’t know if it’s the best)
A pure brute force solution would have to try over 30 billion solutions. I wrote code to solve this in J. I’ll post that separately.

Updated Slitherlink — and an explanation about inside vs. outside for toroidal slitherlinks

First, here’s an updated version of my previous toroidal slitherlink:

Screen shot 2009-10-17 at 1.46.02 PM

That should now be unique for inside/outside solutions. See below for a description of what inside/outside means.

As I mentioned before, Thomas Snyder pointed out that there are two different types of solutions to a toroidal slitherlink: either there is an “inside” and an “outside,” or there is only one “side.”

Continue reading

An even more difficult slitherlink (I think)

Credit: Thomas Snyder (crazy good puzzler) was the one who discovered the two types of toroidal slitherlinks. I’ll post his solutions and mine tonight, along with an explanation of the two types of solution.

Update: it turns out this puzzle does not have a unique solution. Further, it apparently has two different kinds of solution.

I designed the solution to this puzzle to have has two distinct sides — an inside and an outside. The “outside” connects to itself around the “inside,” albeit by going out one side of the puzzle and in the other. This reminds me of an old riddle/joke: “Is a zebra black with white stripes or white with black stripes?” The answer is that the zebra is white with black stripes; notice that the belly of a zebra is solid white(more or less visible depending on the species of zebra and the picture).

Even given that, it turns out my solution isn’t unique. There is a 2 where the loop can go on either side of it. It was right there and I missed it.

But there is another way to solve the puzzle, one that has no “inside” or “outside,” or even sides at all. Imagine if the solution were a single vertical line going from the bottom of the puzzle to the top (and thereby connecting to itself). That’s a loop, but it would be possible to connect any square to any other square without crossing the loop. Hence, no sides at all. There is apparently a solution like that as well, although I haven’t seen it yet.

So I think next time I’ll have to try harder for uniqueness.

Update: I got a Google Wave invite! I have several invites to pass out, so I’ll give one to the first person to post a solution (or pm me on Reddit: gcanyon).

This is a different variation on slitherlinks than the last one I came up with. This is like a regular slitherlink, in that the numbers can be either inside or outside the loop. The trick here is that the puzzle wraps around: the top is connected to the bottom, and the left to the right. So while there is just one loop that doesn’t cross itself, the loop can go off one side and in the other. So this would be a valid solution:

You call that a loop!?

You call that a loop!?

This is a 4×4 grid. The path goes off the lower right side/in the lower left side, and then off the bottom/in the top. Note that the right and left edges are actually the same set of dots, and the top and the bottom are also just one set of dots. Hence the line at the upper right that looks stranded is actually the same line as the one to the left of the 3 in the upper left corner. Once you understand that, you can see that this puzzle has two sets of adjacent 3s: the ones side by side on the lower right, and the ones on top of each other at the lower left and upper left.

So here’s my first puzzle of this type. As usual, it has a single loop that doesn’t cross itself. Unless I’ve made a mistake there is a unique solution. Good luck!

I think this one is hard...

I think this one is hard...

A more difficult slitherlink

This one is the same variant as I described previously: all the numbers are outside the loop. This one is larger at least. I don’t know whether it’s actually more difficult other than that.

One aspect I particularly appreciate of well-designed slitherlink puzzles (and this type of puzzle in general: masyu, nurkabe, fillomino and others) is that there is only one solution. This leads to the interesting solving technique that if a proposed addition to the work-in-progress leads to a situation where there are two ways to fill in a section and both are equivalent, then the proposed addition must be wrong, because there cannot be two solutions. This technique is particularly hard to apply, but I’d be very interested in a puzzle that required extensive application of it to find the solution.

In any case, here’s the puzzle. Check the previous post if you don’t know the general rules for a slitherlink.

Harder?

Harder?