Simon blogs

[Simon]

Christmas tree problem

You have a fir tree and want to decorate it with christmas lights.



The fir tree's green bushy "surface" is cone-shaped, with a circular boundary at the bottom.



You also have n candles. These are about to be placed on the fir tree.

In reality, the candles would be connected by electrical cable, which would restrict the candles' distribution on the tree. Assume that the candles need no electricity, or that the cable between any two candles is arbitrarily long.



Task. Distribute the n candles on the fir tree such that the candles are nicely spaced apart from all other candles. You may place candles on the boundary.

Precisely: Given a distribution D of the candles, compute the minimum of all distances d(k, k') between all candles k ≠ k' of D. We call this minimum f(D). We want to maximize f. Thus, denote by M the supremum of the minimum distances of all distributions, M = sup { f(D) : D is a distribution }. Finally, find an arrangement of the candles D that attains f(D) = M. If no such arrangement exist, instead find a sequence (D_i) of arrangements such that the sequence of minimums f(D_i) converges to M.

In a variations of the christmas tree problem, you're encouraged to avoid the boundary, too. Then, for each distribution, don't merely compute the minimum of all candle-to-candle distances, but also the minimum of all candle-to-boundary distances, and use the minimum of these two minimums. Across all distributions, maximize this value.

Example. Given only one candle, put it anywhere you like. If you'd like to avoid the boundary, too, then put the lone candle at the top of the tree.

Example. Given two candles, even if distance to the boundary doesn't matter, the best distribution depends on the shape of the cone. If the cone is very tall and thin, put one candle at the top and one on the circular boundary at the bottom. Otherwise, if the cone is squat and low-risen, put both candles on opposite points of the boundary.

Example. If your christmas tree is not a tree at all, but rather the unbounded real line, you can space the candles arbitrarily far from each other. This is very nice.



Application. If your christmas tree is instead the space of all colors, and you have 8 Lix player colors, find a distribution of 8 colors such that no two colors look more similar than necessary. This is hard, especially if you, in addition, want to avoid black because black lixes looks too much like the boundary level background.

End. The christmas tree problem is really about abstract metric spaces, not christmas trees, but christmas trees inspired me to first think about this problem in detail. I don't know whether this problem is known by other names in mathematics. I don't know whether it's more common to avoid the boundary or not.

-- Simon

[namida]

With regard to Lix specifically, which color tends to be the most visible? Perhaps every player should see their own lixes in that color?

[Proxima]

I really don't think that's a good idea. Players tend to get attached to their favourite colours and want to keep playing as them

[ccexplore]

To be clear, this is mostly a solved problem for Lix, correct?  Hard to imagine how you'd do better for 8 with rainbow + black & white.  Basically the 8 corners of the RGB-space cube.  Though I suppose it is interesting to wonder for the case where black is also treated as boundary to avoid, whether there may be other winning configurations not using the remaining corners of the cube.

Obviously, you can also consider making lixes look different by other attributes besides color, but given how small the sprites are, I suspect it'd be tricky to create other visual differentiators as clear as color would be.

[Simon]

With regard to Lix specifically, which color tends to be the most visible? Perhaps every player should see their own lixes in that color?

Lovely idea for future projects. It would also obviate GUI to pick color. Fewer choices. I took (Player A's color on A's machine is same as player A's color on B's machine) unquestioned from physical board games.

I draw local player's lixes on top of everybody else's. Often, that's exactly want we want. Downside: Lone enemy attackers are invisible in an own dense crowd. Although (automatic color choices, local player gets best color) would have same problem.

I really don't think that's a good idea. Players tend to get attached to their favourite colours and want to keep playing as them

Yeah, I believe I don't want (fixed color that each local player uses for themself) in Lix.

#1 reason: people really care about the color. Raymanni even wants extra colors (8 -> 12) and would be happy to keep the player limit at 8; then, extra colors would be completely irrelevant to physics.

#2 reason: People in voicechat refer to other players by color. Opponents' colors must be clearly visible.

#3 reason: The replay format identifies teams by color.

#2 and #3 would work with server-side (for each team, fix a color across all machines). But since some color has to be picked and transmitted anyway, we can let the people pick it, they love it.

To be clear, this is mostly a solved problem for Lix, correct?

Right, unless Raymanni wants extra colors. Mainly, I wanted to write about the abstract problem, less about Lix.

Hard to imagine how you'd do better for 8 with rainbow + black & white. Basically the 8 corners of the RGB-space cube.

Neither the 1-metric nor the 2-metric in the RGB cube agree with the human visibility metric. Red (255, 0, 0) and black (0, 0, 0) are 255 apart and are clearly distinguishable. Bright green (0, 255, 0) and bright cyan (0, 255, 255) are also 255 apart, but far less disginguishable than red and black.

Sorry for late answers! More on ccx's ideas later.

-- Simon

[Simon]

given how small the sprites are, I suspect it'd be tricky to create other visual differentiators as clear as color would be.

Right. Glaring colors with different lightness are good and easy to implement. The main point of the post was to explain my reluctance to implement Raymanni's desire for more than 8 colors, because 12 colors are harder to christmas-tree-distribute than 8 colors are.



Many news

I'm a software engineer by profession now.

The project is firmware maintenance and development in C++ on Linux. The firmware runs on electrical rectifiers attached to solar panels. My team is 7 people, I get along really well, and occasionally troubleshoot their problems with git.

The job interview was more about Lix than about my formal studies.

After I defended the PhD thesis in September 2018, I spent until April 2019 bugfixing the thesis based on both professor's thorough findings. This was a tricky decision, I could have published immediately without penalty, but I wanted the thesis to be solid. I didn't look for a job much while debugging the thesis. That's why it took 10 months from defense to job. But it's all good now.

Akseli: I solved the Lasertank level 40, Down the Drain. It's really a Sokoban level. Years ago, I solved levels 1-39 and many past 40, but always got stuck on level Down the Drain.

-- Simon

[grams88]

Lix has opened many avenues for you, welldone on getting the job Simon. I'm glad you are settling into the job well.

I remember in my younger days those (Lasertank) levels were quite difficult and I don't think I got too far but I must give it a try in the future as I'm getting quite good at those Sokoban games in my present days. I enjoyed making my own levels and having my brother try to complete them, it's a good little game which I recommend to any sokoban fans.

There was game I completed recently which was the (Lmarbles) game which is based on a game made a long time ago where you had to copy the order of the molecules to complete the level. In Lmarbles you just have to get the order of the colors by moving them around until you get the right design or order so to say.

(Chuck's challenge) was a really good game I thought and there was a lot of levels where you had to move boxes around like the Sokoban type levels and some of them would drive you crazy.

In regards to the color's in Lix, I would try to avoid any color that looks similar to any of the other colors that have been implemented. Maybe this could be an issue if you were to implement more colors. I remember in worms Armageddon the colors Cyan and green felt as if they were too similar but I wonder if that is more a isolated problem with myself rather than with others. Anyway your lix color looks more like blue so no worries in that regard.

[ccexplore]

Right. Glaring colors with different lightness are good and easy to implement. The main point of the post was to explain my reluctance to implement Raymanni's desire for more than 8 colors, because 12 colors are harder to christmas-tree-distribute than 8 colors are.

This is a stab at what one might do for 12 colors, excluding black as a color:
█████████████████████████

Some colors are not quite so distinct compared to the current 8, but I think above might still be manageable for most people?

That being said, how likely anyway are we to ever get a game using all 12 at once?

[namida]

My concerns there would be brown vs orange, purple vs pink, and white vs grey. Those easily could look like different shades of each other, especially in a situation where there aren't lixes of both colors near each other. I think the rest are distinct enough that they'd be recognizable as outright different colors even when not right next to each other. A darker shade of grey would probably resolve the issue in that case, though I think the other two pairs would likely be hard to redeem without instead making them too close to a different color. This still adds two more colors, though.

[grams88]

Would 12 players not make the game a bit crazy and very hard to organise but if it is something you want to do go for gold.

[Simon]

Thanks for the replies! Yes, Lix has brought me far. Still, there won't be 12 colors in Lix.



Magic Cave
(hobbies, time management)

I miss the magic cave from doctoral studies where you would work on a creative project for days, then on the thesis for days, then again on hobbies. Lots of Lix bugs got fixed in the magic cave, many posts were written here on the forums.

The downside of that magic cave is that you naturally let the thesis slip. Any time spent on hobbies could be spent on thesis, thus, even in the magic cave, one will never feel truly free. Likely, that feeling is impossible to re-attain after the age of 5. Still, it's the guiding light to what you should do with your time.

I still want to write a paper with my professor, now that math feels much more like a neglected hobby. Already behind schedule, but it's fine since prof isn't rushing either. It's a side project for both of us.

I have spent time on other hobbies, thus I shouldn't feel like having wasted all too much time.

I have loose ideas for a tile-grid-based Lemmings-inspired puzzle game with many different gadgets, to let my inner five-year-old bloat features. Rules must be really sharply defined, turn order and tile-based movement must be clearly specified. Proxima would be delighted. No time these days, though.

When you don't create things, you become defined by your tastes rather than ability. Your tastes only narrow and exclude people. So create. -- Jonathan Gillette



OO
(software engineering)

We had a three-day seminar on Clean Code, the classic object-oriented guidelines à la Uncle Bob. I've always enjoyed OO and soaked much of this wisdom already in the years past, during magic cave. Thus, the co-workers might have gotten more out of it than I did. Nonetheless, good rehearsal.

According to the seminar, I should make more interfaces and fewer abstract base classes. This seems hard to follow when you roll your own GUI as in Lix: We have GUI Element, an abstract base class that already has important behavior, e.g., decision whether the Element should be redrawn. Then class Button inherits from Element, then TextButton and BitmapButton inherit from Button. How to avoid inheriting from classes here, and instead only inherit from interfaces? Even if TextButton and BitmapButton became decorators, Button would still inherit from Element. Anybody want to give it a shot?

I've ordered a book on UML, Kecher's UML 2.5, a German classic. Allegedly, UML is the driest thing in the software engineering universe. Doesn't matter, it's handy in real life and will fix a sizable knowledge gap.



Error Handling
(software engineering)

I'm interested in error handling strategies. Reason: In C++, everything sucks or is nonstandard.

Ye olde C errore propagation is by return values: Everything returns int, negative values mean errors, zero or positive are good results. Functions return the error code and write other useful output into a buffer that you pass to the function by reference.

int foo(int x, int y, unsigned char* outBuf, size_t outBufLen)

This permeates the codebase at work. Call sites then look like: Make buffer, call the function, if the function returns an error, print something to the global log stream, and abort, or maybe continue if you don't deem the error that bad. The downside is the ton of checking boilerplate around every call. And you can't declare the output const because you have to declare its variable first, then fill it in the call. (Also some people don't like to return early and write 10 nested ifs, but that wouldn't be contemporary C anyway.)

Well, we have C++ exceptions, but they aren't part of the type system. noexcept is a feeble attempt to fix that, it's nowhere used in legacy code. For every method, you must remember whether it throws, and what it throws, to decide whether you want to handle the error. You must read the API docs or hope that it doesn't throw.

As long as you call even one maybe-throwing method, the compiler must generate exception handling around your call. I haven't studied compiled binaries to how fast or slow it is. Even if this were no speed problem -- I don't like exceptions, they feel wrong, it can't be good design that the easiest thing to write is to let the program crash by unhandled exception.

Really the most fitting for the work codebase would be Zig-style error handling: Your functions return either an error code or a useful value, and there are special language features to abort execution and propagate the error. With such features, you may write the call site as if the callee returned no error; on error, it behaves like an exception that is baked into the return type. Or you can explicitly handle the error, again with syntactic sugar because handling is common.

Now, Java had checked exceptions that sound like much the same, baking the possible error into the method signature. But modern Java is moving away from them. Shall we heed this as a warning? Hmm, Zig has no virtual dispatch, not even type inheritance. And Java had some unchecked exceptions from the beginning by design: Nullpointer dereference, or out of memory. While I still firmly believe that nullpointer exception is a glaring misdesign -- the type system should handle whether your pointer may be null or not, and force you to check if applicable -- I have no strong opinion against the out-of-memory Java exception.

In C++, you can define your own error-handling type: A tagged union of error code and useful result. Then all your functions return this tagged union. You can call methods on the tagged union and the call only goes to the useful value if there hasn't been an error yet.

template <typename T>
struct OrError {
    int error;
    T value; // use only if no error
    /* ... maybe methods to chain calls on these as long as no error ... */
};

The downside of the tagged union is that this is impossible to retrofit over the C-style error handling: You'd have to write a wrapper for every int-returning buffer-filling method -- there is no way to generate all the wrappers with a template because the out-buffer parameter is in a different location for each C function. Also, the entire codebase would have to agree on one such error union type, otherwise it would split into worlds that can't call each other's functions without wrapping.

If the wrappers could be autogenerated by the language, we would have a full-fledged error monad.

You could write code in the reactive paradigm where your method call gets you a value stream and a separate error stream. Again, massive boilerplate in languages that don't support it easily.

Thus, there is no clear winner. Every time, it itches enough to find a good solution, but in the end, it's least painful to stick to the convention.

The easiest code to call is still code that cannot fail.

-- Simon

[Simon]

Commercial software

I updated my router's (Fritz Box 7490) firmware from its 2017 version to 2020.

Now the router's webpage config menu takes 4 seconds to load every page. The old version took maybe 0.5 seconds. Eight times the overhead! In commercial software that I pay good money for by buying the router in the first place.

In 4 seconds, there is a serious chance that I'll already have forgotten what I wanted to do once the menu finally opens. Usability 101, don't take 1 second or the user will lose mental focus.

How can one screw up this badly?

Reason 1. The software is way past its heyday, and they've assigned cheap maintenance programmers to that project while the gurus work elsewhere on more fun projects. Surely it must be fine, the customer had already paid.

Reason 2. Some awkward security bug was found and they had to hoist the crufty app onto some new low-level infrastructure. The overhead thus comes from the many adapter layers. With age come all these barnacles that hang off the ship.

Reason 3. It's a boiling frog: The page loads got slower by a tad in every version, and thus it slipped past the testers for 3 years with each of the many updates.

Reason 4. Users should be glad that stuff is working at all despite a firmware update, and it even loaded the old configuration. Maybe the loads come from persistent rubbish from the ancient version, which was either never found in testing, was deemed acceptable after they got the firmware to finally update seamlessly. This kind of updating an entire device is really, really hard after all, especially since they allow me to update after 3 years, likely skipping many intermediate versions.

This mess is one of the reasons why I still have no smartphone. It's way too easy for commercial projects to go down the drain within years.

-- Simon

[Simon]

is something that

If you're a person who doesn't like X, try Y.
If you don't like X, try Y.

This is something that I like.
I like this.
This, I like.

Try and see if you can jump over the gap.
Try to jump over the gap.
Jump over the gap.
Jump the gap.

Remember to go to bed by midnight.
I want to add that
It should be noted that

If it is isomething that can be cut, then cut, cut, cut.



Forewarning

If you don't know what X is, X is a platforming game.
X is a platforming game.

If you don't know X and X is a platforming game, then, very likely, X is also a platforming game when you already know X. The reader is smart enough to understand sentences that he already considers true.

You might believe that you're helpful with such forewarning ("If you don't know X") about introductions ("X is a platforming game") that a knowlegdeable reader may skip. But you don't achieve that unless you clearly mark where the introduction starts and stops. Few do that in English, sadly. Because so few writers do, the reader must still read everything, lest he skip important non-introduction.

For programmers:

• 
  Write for humans exactly like you're supposed to write high-level computer programs. There, we shall hide the repetitive bookkeeping, not bloat the call site. E.g., we prefer
      Optional<X> x = ...
      x.foo()
  to
      X* x = ...
      if x:
          x->foo()
  

And then here continue the essay with whatever remainder written for both for programmer and non-programmer.

-- Simon

[ccexplore]

In some of the examples, the "extraneous" expressions are there either for politeness purposes, or sometimes for flow/emphasis purposes.  For example, "remember to X" reads more like a gentle reminder vs just saying "X" directly, which may sound a little rude to some due to sounding much like a direct command or demand.  Context matters of course.  For example, given that telling people to go to bed is typically something a parent say to a child, it doesn't seem rude for a parent to say it to a child in direct imperative form.  For a different task and different social roles (for example, one coworker to another, speaking of some work-related task), it may be more proper to be less direct.

I agree that the other examples that Simon specifically struck out (ie. "like this") are far more likely to be extraneous.  But without seeing the preceding sentences, I can't rule out some occasional cases where being a little indirect and verbose may be (somewhat) justified.

I'm well aware that I can be a bit wordy in my own writing. Feel free to apply the Simon culls below to some example writings of mine in this forum, I welcome the closer look and debate.

Computer programming is quite different of course compared to spoken or written language.  The programming example you gave doesn't feel to me like much of an analogy to the "is something that" in English.  A programming language may offer multiple ways to do the same thing, but rarely would you have constructs that have completely no effect (besides comments, but they are there to help the human understand why the code is doing certain things certain ways, as opposed to telling the computer to do something).

[Simon]

Thanks for the reply! Sorry for my belated reply.

The programming example you gave doesn't feel to me like much of an analogy to the "is something that" in English.

Here, my desired nuance wasn't filler phrases: Certainly, programming languages have few constructs that could be outright omitted with the same meaning. Thus, "is something that" isn't a suitable example here.

I wanted to draw attention to how the payload -- the businees logic in programming, the big ideas in writing -- should not be bloated by bookkeeping. The reader can often figure out the bookkeeping themselves, or the bookkeeping can be written somewhere else.

For such avoidance of bookkeeping, "if you don't know what X is" is a better example than "is something that". The meaning will change when we leave out "if you don't know what X is", but it really doesn't matter; we want to cut to the point immediately. The change in meaning happens to be irrelevant here, even better.

Feel free to apply the Simon culls below to some example writings of mine in this forum, I welcome the closer look and debate.

All right, I'll try once I see a particularly tasty target. I read practically everything by you, doesn't matter which topic on the forums.

Courtesy is interesting. People interpret bloated, deliberately weakened statements as courteous. When an author prunes the writing, people should be happy that the author doesn't waste their time, they shouldn't feel uncomfortable. <_<;;



Sorry for any of my slowness on the forums these days. I'm still stuck in the editor's undo feature for editor tile insertions/removals.



My current design problem appears to require triple dispatch. (If three objects are of specific subclasses each, call a certain method.) This is likely a misdesign in the classes, I merely don't see how. I expected double dispatch to appear, I have parallel class hierarchies that seem like the least-worst solution.

Maybe I'll have to lie on the psychiatric bench that is the Lemmings Forums, and make a detailed topic about this.

I hesitate making intricate programming design topics here though: It's really software development at heart, not of general Lemmings interest, and probably more sensible on Software Engineering stack overflow. It would be a genuine call for help, on a nontrivial and highly specific problem in my personal areas of expertise and interest (Lemmings, OOP) -- thus obvious solutions won't fit.

On the other hand, it's easier to explain the problem on Lemmings Forums, because we have a bunch of developers here that will readily understand the problem. And if we find the least-worst solution, maybe it'll be helpful too for somebody in the future.

Hmm. After this rambling, I should really make this topic.



Edit: Adding/removing tiles is functional, using the visitor pattern for the common double dispatch and dynamic casting to avoid introducing a second visitor on the parallel hierarchy. Topic here will still be reasonable, it still feels awkward.

-- Simon