5
$\begingroup$

I want to simulate an operation on a disk, originally specified in project-euler problem #566. Here is a description of the problem.

I want to simulate a disk with arbitrary partitions, but only two coloring. For example, like this:

enter image description here

And I need only one operation: given a specific sector of the disk, e.g. from $0$ to $\frac{\pi}{2}$, flip the sector and flip the coloring. Take the disk above as example, the sector would be:

enter image description here

Flip the sector upside down, and flip the coloring, we get:

enter image description here

Finally, inserting back:

enter image description here

However this took me hours to write and with a lot of condition checking and bugs. I started with a list with all angles that changed colorings, and the initial coloring, like {"black", {0, 1/4 Pi, 3/2 Pi}},and the following functions suffered a lot from the cases which the sector crosses the starting point, although I used mod a lot. Is there any easy and elegant way to deal with such circular structure?

Some of my current code

(*first 0: color counterclockwise on starting point; {0}: partition points; 360: total angle*)
diskStat = {0, {0}, 360};
getLastLEQPos[list_, elem_] := 
  Length[list] + 1 - FirstPosition[Reverse@list, _?(# <= elem &)][[1]];
(*get the color on angle pos*)
getStat[pos_, diskStat_] := 
  Mod[diskStat[[1]] + Mod[getLastLEQPos[diskStat[[2]], pos] + 1, 2], 
   2];
(*get selected interval*)
getInterval[diskStat_, currentPosition_, angle_] := 
  Module[{split, stat}, 
   split = Mod[
       RotateLeft[diskStat[[2]], 
        getLastLEQPos[diskStat[[2]], currentPosition]], 
       360] // (If[
         getStat[360, diskStat] == diskStat[[1]], # /. 
          0 -> Nothing, #]) & // Prepend[currentPosition]; 
   stat = getStat[currentPosition, diskStat]; {stat, 
    Mod[TakeWhile[Mod[split - currentPosition, 360], # <= angle &] + 
      currentPosition, 360], angle}];
(*flip the selected interval*)
reverseInterval[intv_] := 
  With[{end = Mod[intv[[2, 1]] + intv[[3]], 360]}, {If[
     end != intv[[2, -1]], getStat[end, intv], 
     Mod[getStat[end, intv] + 1, 2]], 
    With[{li = 
        If[end != intv[[2, -1]], Append[end][intv[[2]]], intv[[2]]]}, 
      Total@li[[{1, -1}]] - Reverse@li] // Drop[#, -1] &, intv[[3]]}];
$\endgroup$
8
  • $\begingroup$ Are you already using PieChart or SectorChart? Those might reduce the burden of creating the graphics. Also, I'm not sure I understand the conditions of the problem, I.e. when do you need a switch etc. Can you share your code attempts? $\endgroup$ – MarcoB Nov 24 '16 at 15:33
  • $\begingroup$ @MarcoB Actually the visualization part is not very important. The trouble happens when I try to process the list representing the disk. I will post some code later when I have access to computer. $\endgroup$ – vapor Nov 24 '16 at 15:40
  • $\begingroup$ @MarcoB You only need a switch when you specify a sector to switch, i.e. manually. But I need to preform lots of switches, that's why I am seeking a better approach. $\endgroup$ – vapor Nov 25 '16 at 5:59
  • $\begingroup$ Let's say you have borders on 0, Pi/2, Pi, 3Pi/2. Now, what happens when I take 0-Pi/4 for that operation? Should same color sectors merge on 0? $\endgroup$ – Kuba Nov 30 '16 at 8:33
  • $\begingroup$ @Kuba Thanks a lot for looking at my problem! In that case, if the disk starts with white, then you will have 0-Pi/2 to be white. Now we perform "flip and invert", flip: nothing happens; invert: 0-Pi/4 becomes black. $\endgroup$ – vapor Nov 30 '16 at 9:34
1
$\begingroup$

Here are a few ideas that might lead to something.

  1. Is the idea to solve the Project Euler problem easily/elegantly, or to manipulate graphics? This is relevant, because the Euler-project problem asks for a number, not a series of pictures.

  2. Instead of manipulating the graphics, just keep a list of the angles. For example, {{0,45},{60,360}} is the whole disk, except the wedge from 45 degrees to 60 degrees is missing.

  3. Keep just one list of wedges, the black ones, say. Everything else must be white, which could be generated from knowing the black ones.

  4. Suppose we want to take a slice from -45 deg to 45 deg, and flip it over. Suppose the only wedge in our list is from 10 deg to 25 deg. This wedge will get flipped to -25 deg to -10 deg. That is a big clue to how to easily flip any wedge.

  5. If our slice is from 100 deg to 150 deg, the we rotate our wedge(s) counterclockwise by 125 deg, do the flip around zero deg direction and rotate them clockwise by 125 deg.

We will want to define a few operation on the wedges. Here are some ideas for functions that would be nice to have:

  1. slicer is a function that makes a slice at a given angle. For instance, if we want to make a slice at 130 deg, this function looks for any wedge (there should only be one) that spans 130 deg, and divides that wedge into two wedges. We would apply it twice before we flip the wedges.

  2. chooser is a function that takes our list of black wedges and selects the ones that are within two slices. The selected wedges will be flipped over later.

  3. rotate takes a list of wedges and rotates by a given angle

  4. flip takes a list of wedges and flips the about the 0 deg direction.

  5. complement is a function that takes a list of wedges within a slice throws them away, but keeps the blank space between them. In effect, it takes a list black wedges and returns a list of the white wedges within a slice. It should be easier to code this function than to maintain two lists of wedges -- one black and one white.

  6. merge is a function that would merge adjacent wedges. For instance, if we had the list of wedges {{30,60},{60,75}}, that is really just one wedge, {30,75}. We can use MMA's Interval function here.

  7. step is a (poorly named) function that determines the two angles of the next slice. It then applies the slice function at each angle. Next, it picks out the wedges within the slice angles. Then it applies rotate to selected wedges, applies flip to the rotated wedges and applies complement to the flipped wedges. Then it rotates the new wedges back and, finally, adds the new wedges to the list of black wedges and does a merge on the list.

  8. display is a function that takes any list of wedges and displays them in the given color.

  9. solver is a function that counts how many times step had been evaluated and watches for a solution. If the list of black wedges has been returned to {{0,360}}, we're through. The number of times step is evaluated is the function $F(a,b,c)$ referred to in the Project Euler problem. solver can also apply display after each step.

  10. euler566 is a function that evaluates the solver for a series of integers $n$, adds up all the results and returns the sum. This function is the $G(n)$ referred to the in the Project Euler problem.

$\endgroup$

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.