Navigate text with arrow keys
code-golf
Most (halfway decent) text editors allow you to navigate text using the arrow keys. Up and down allow you to navigate lines, while left and right moves across a line but also wraps around. Furthermore, if the line is shorter than your curser's X positio...
Background
Most (halfway decent) text editors allow you to navigate text using the arrow keys. Up and down allow you to navigate lines, while left and right move across a line but also wrap around. Furthermore, if the line is shorter than your cursor's X position, the cursor appears at the end...
I guess the worst would be one that didn't compile, and if you made it compile, it would be completely wrong; trying to come up with that kind of code would probably do damage to my brain
well it would backtrack back inside, if the stuff after it fails
but instead of trying the next alternative it would first try adding the first alternative again
take this as an example: (a.|a)*?b matching ababb
zero repetitions doesn't work, so it tries adding a. which does work. but b still fails. so instead of trying the a (which would give a 2-char match), it adds another a., such that the pattern matches all 5 characters
if we did get that to work, I think it means we're limited to DPDAs (I know that normal DPDAs are less powerful than PDAs, but I don't know if a 2-stack DPDA isn't still Turing complete... after all deterministic Turing machines are)
unless...
hm no, never mind.
basically we'd need a way to make the engine search with a BFS instead of a DFS
(plus, we'd need to convince it to perform the backtracking at all with zero-width groups)
it's sort of disappointing if this was the one quirk that prevented it from being Turing complete :D
@kuroineko your comment on the snake shapes question has me thinking now. I thought my method was correct for all cases but I don't have a proof, so I may have to add redundancy until the current version can be proved correct.
Checking the quarter arc of every point after the pivot for intersection with every line segment up to the one before the pivot and also checking the quarter arc of every point before the pivot for intersection with every line segment from the one after the pivot would be sufficient. That would check every convex point against every line segment, which is enough to convince me. I believe that just checking one of these two ways is sufficient, but for that I am not 100% convinced
I'm not considering areas at all. I'm only considering the lines swept out by the points, not the areas swept out by the lines. The moving points are checked against the static lines
Yes I agree surfaces would be watertight, but I believe this much easier approach with no surfaces is also watertight (at least in the double case I mentioned just now)
I can't think of a way that two line segments could intersect during a 90 degree rotation that doesn't involve at least one point passing through at least one line segment
Actually maybe it would still work. I think the key thing is that there are no curves. Since all the lines are straight, there's no way for them to overlap without an end point also overlapping, so we can just check the endpoints against the other lines
If the lines were not all the same length then we'd need to check twice, once for the endpoints of line A against the line of line B, then for the endpoints of line B against the line of line A. The two checks are necessary because either of A or B could be the longer one, allowing the shorter one to miss its endpoints. But when all the lines are the same length I think just checking one way is enough.
Yes - this is important. The quarter arc swept out by a moving point may cross a line in the middle and then cross back again before the end of the line. This is covered by checking for intersection of the arc with the line though, so we're safe
What makes me confident is that if the surface collides with any point on a line, then the boundary of that surface (the arc) must also collide with the line.
I can't picture the snake arrangement. Could you specify it as a list of numbers? Like '1120' is a snake that goes straight, straight, anticlockwise, clockwise
The end points are always on the integer grid, and so is the pivot point. Non-integer points will be passed through during rotation but the start and finish positions will always be integer.
@Sp3000 Okay, so we don't need to model an NPDA... a DPDA is fine, which I think means I only need one valid alternative per iteration - so we don't need any backtracking at all.
Yes, but if I wanted to improve efficiency by considering longer lines, I'd have to think carefully about cases like this where the pivot is between the end points (vertically or horizontally)
Keeping to unit lengths means there are no integers between the ends
I might need to make another diagram to check, but I believe if you divide your line segments into unit lengths and sweep out the arcs of each of the integer points, then between them then they cut every possible unit integer-aligned line segment within the area you have shown
@MartinBüttner Is Regex Storm the only site that lets you see how many empty strings are in the stack? Trying to see if things are any different elsewhere
Actually not necessarily - I'm just thinking of the unit line segment alone. That has no inner integer points and still sweeps out a concave circular area. I still believe it cuts every possible unit integer-aligned line segment though, which is sufficient.
@MartinBüttner The research done at our math department, mostly. We have people working on combinatorics of words, cellular automata, and other fun stuff.
@Sp3000 for your second sentence, I'm pretty sure they all just pass it on to a .NET instance though... I doubt any of these testers reimplement the flavour
Regarding the snake challenge: I don't know how people are currently finding possible positions, but I think it might be easier to generate paths and try to unfold them than start with a line segment and fold it.
@PhiNotPi Starting with a straight line and folding all possibilities means checking each step once and only once and only checking illegal shapes that are one illegal step away from a legal one. Checking all possible shapes would involve much more checks (unless you start with all possible shapes that don't self-intersect, but then you still have to generate that set somehow).
@kuroineko I'm safe if no part of the blue area touches a unit axis-aligned line segment that isn't also cut by one of the two blue arcs
@kuroineko The only way it wouldn't be true is if there could be a line segment with both its end points within the blue area, so both blue arcs miss it
There does appear to be such an arc, so I could be in trouble...
I think I'm still safe overall, because that line segment has to be connected to the pivot
If we were testing for intersection of one snake with a disconnected snake, then my method definitely wouldn't work, and you'd need to consider areas as you suggest
nevertheless, if (for some reason beyond my maths) in the case of unit length axis-aligned segments both arcs are guaranteed to be on the boundary of the swept area, then you can easily check if a point is in the area.
about the segment being connected to the pivot, I don't see how that helps. With a long enough snake and after a few bends, you could end up with a snake segment located as far away from the pivot as you want, oriented in any direction.
@kuroineko Your diagram actually makes me more confident, but confidence is still just a feeling. I'd like to be able to prove it.
The only route back to the pivot without crossing a blue arc is through one of the line segment ends of the blue area, which don't contain any integer points that aren't also on the blue arcs
So this convinces me that the double approach is sufficient (checking all points after the pivot against all segments before the pivot, and vice versa)
But I would still need a proof that the single approach works in order to leave my answer in its current form
well actually I think you could simply check the 4 boundaries of the area, that is the two quarter circles and the two end segments. The quarter circles with a radius comparison, and the segments with the positions relative to the half-plane delimited by the extended lines.
I suspect the areas left out must be within a surface that cannot contain points with integer coordinates.
Area of a Self-Intersecting Polygon
code-golfgeometry
Consider a potentially self-intersecting polygon, defined by a list n ≥ 3 points in 2D space. E.g.
{{-2, 0}, {1, 2}, {-3, 4}, {0.5, -0.5}, {0, 3}, {-0.5, -1}}
There are several ways to define the area of such a polygon, but the most inter...
I'd probably rather go with something like "your algorithm's time complexity must be a polynomial in n", but if that turns out to be a bad idea, I might go with a time limit
I wonder if you could choose cases that can't reach that level of accuracy with Monte Carlo. If you up the accuracy to make floating point struggle, would that rule out Monte Carlo or analytic methods first?
Speaking of regexes I've been thinking of a regex golfer codegolf where you're actually given a regex and the pass/fail sets, and you need to get the shortest regex which matches the sets in the same way via a series of predefined operations (e.g. [x] -> x or abc -> a.c is there is no fail string that matches a.c)
it's not that the backtracking skips empty matches once a quantifier has already found the minimum number of empty repetitions... it's that the quantifier stops altogether as soon as the minimum number of empty repetitions is hit
@MartinBüttner I think you heard about the idea I was discussing with @PhiNotPi and others. Do you think this would be a candidate for the fortnightly challenges?
@flawr sure. but just to be clear, I meant for the fortnightly challenge it might be better to not specify the particular game. maybe others have better ideas for our first asymmetrical koth to test the grounds for how well that works. you can always add the game as an example, but I think it might be more fruitful if you left the decision on the actual game open till when it's picked.
@Sp3000 I wonder if we actually need to able to run for an unspecified amount of steps to claim Turing completeness... I mean Rule 110 doesn't terminate on its own either... you just let it run for long enough until the computation is done, and then you read off the result.
Well the way I see it is if we can get * to work like we want I think we basically have FRACTRAN (I wish I knew more CS so I'd know more about turing-completeness than just esolangs)
@flawr Since the idea is pretty concrete already, post it in the sandbox. Fortnightly challenges ideas are a theme, with the challenge being designed by many people in chat.
@Rainbolt Honestly, regardless of the snippets question, I don't see what's wrong with posting a meta question like "How can I run a KotH without restricting submissions to one language?" (or similar... "while still providing subclass entries in the controller language") with a self-answer along the lines of "if you use Java for the controller, you can just use/adapt this wrapper I wrote:"
Cursor Wars
king-of-the-hill
This question is based off of my previous Navigate Text with Arrow Keys golf. Here, a segment of text is the battle arena, and the opponents move like cursors.
Idea 1: Tron / Light-Bikes
As the cursors move left to right, they paint parts of the text. Neither cu...
hm, PhiNotPi's proposal makes me wonder about a KotH similar to Code Bots, where you can collect characters and add them to code of your bot as the game progresses
the actual submission would probably have to be a real-code bot which assembles the "code bots" from the characters, because I doubt you'd be able to actually improve the logic of a bot if that bot itself is responsible for assembling that logic from individual characters
you'd probably have to keep the game reasonably simple, or the entry barrier will be higher than that of Codemon :P
but I guess a simple entry could just write a strategy for the code bot, and then write an assembler which just adds fixed pieces of code as they become available
Conway's Golf of Life- Brains vs Brawn Edition
2 programs play a competitive version of the game of life, where each program can set as many cells in the initial condidtions as there are characters in the other's source code.
The 2-player game of life is played on an infinite grid of cells. Eac...
I saw one which handled multiple languages in Java or Python i think, if that skeleton is usable it helps a lot that you only need to write in one language
@Peter, say... I've been thinking about Turing completeness of things like cyclic tag systeems, Rule 110 and Game of Life... the thing that's bothering me is that all of these don't have any means inside the system to determine if a computation is complete. if you want to use them to compute something, you sort of just have to run it as long as you care to and then hope that you're stuck in a cycle that represents a halting state, right?
@MartinBüttner Although it may make the infrastructure more complex, specifying a "program has ended" symbol that isn't used for anything else seems to solve that problem.
Navigate text with arrow keys
code-golf
Most (halfway decent) text editors allow you to navigate text using the arrow keys. Up and down allow you to navigate lines, while left and right moves across a line but also wraps around. Furthermore, if the line is shorter than your curser's X positio...
Area of a Self-Intersecting Polygon
code-golfgeometry
Consider a potentially self-intersecting polygon, defined by a list n ≥ 3 points in 2D space. E.g.
{{-2, 0}, {1, 2}, {-3, 4}, {0.5, -0.5}, {0, 3}, {-0.5, -1}}
There are several ways to define the area of such a polygon, but the most inter...
Conway's Golf of Life- Brains vs Brawn Edition
2 programs play a competitive version of the game of life, where each program can set as many cells in the initial condidtions as there are characters in the other's source code.
The 2-player game of life is played on an infinite grid of cells. Eac...
