The Nineteenth Byte

trichoplax

18:01

Game of Life computers can process binary strings of glider/no glider, which means when it terminates you can't tell whether it's just emitting a very long string of 0s (no glider). But if you made a more complex computer it could represent 0 as two closely spaced gliders, 1 as two widely spaced gliders, and then no gliders would indicate termination. Alternatively it's output could be binary representing a higher language (maybe ASCII) with one of the symbols never used, reserved for halting

Martin Büttner

oh yeah sure

of course you can tell if it's "terminated" from inspection

trichoplax

Real computers do something similar I guess (although you'd know more than me about that...)

Martin Büttner

but it's not like a Turing machine or a PDA or a (normal) tag system which actually includes halting in the model

trichoplax

Do you mean like a Game of Life computer that processes all the input, giving a stream of output, and then disassembles the computer itself when it's finished?

Martin Büttner

ummm... I don't think so :D

trichoplax

18:04

I think I'm answering the wrong question... Oops :)

Martin Büttner

but I guess terminating isn't really a useful property for Turing-complete systems, because of the halting problem... ultimately you can't do anything but cut off the computation to say "it probably doesn't halt any more" anyway

trichoplax

Would a stream of gliders where only every other glider represents output work? The ones in between mean "program is still running", and when it halts they cease

Martin Büttner

@trichoplax I think we're still not talking about the same thing

trichoplax

:)

Peter Taylor

@MartinBüttner Pretty much.

Martin Büttner

18:07

hm, that's sort of unsatisfying :D

kuroi neko

@trichoplax I think I got the bloody twisting snakes under control :) If I'm not mistaken, you can test the swept area of a segment of any lenght with at most 8 half planes and 4 radii.

Martin Büttner

you wanted to say "monkey-fighting snakes"

trichoplax

Great. Does that take longer than the arcs and segments approach?

@MartinBüttner I now have the full quote in my head

Martin Büttner

@PeterTaylor I'm not sure if that means that my beloved .NET regex is or isn't Turing complete. I guess for all practical purposes it is. the thing is it can't not halt - you have to manually specify the maximum number of steps to take. but you could represent not halting as not matching. so basically if you say "run this TM for 10k steps" and you don't get a match it just means "it didn't halt within 10k steps".

but... having an arbitrary but finite number of steps just doesn't sound Turing complete to me :D

trichoplax

Can your .NET regex simulate the Game of Life? Or rule 110?

It sounds like it could only simulate a fixed number of steps

Martin Büttner

18:14

I think I can encode a 2-stack DPDA in it

but I can only make it take an arbitrary finite number of steps (as far as I know)

trichoplax

Do you have access to the step limit while running?

Martin Büttner

no, only before I set it off

trichoplax

Then I guess you'd call it not Turing Complete

Martin Büttner

right... that's what I was thinking

but I don't see how it's practically any different

trichoplax

Hardware limits aside, you could still run any halting program for which the halting time is known in advance.

You just couldn't run any program that is known to not halt

Martin Büttner

18:20

in reality, I can only let a rule 110 or game of life (or even a Turing machine) only run for an arbitrary finite amount of steps before I have to decide "okay it's halted, I have a result" or I say "damn, it still didn't halt, I guess it won't any more"

@trichoplax oh I could also run those reliably (because if I run out of steps without halting I can claim "doesn't halt")... what I can't run is programs where I can't put a finite limit on the runtime.

trichoplax

Anything which people describe as Turing Complete only applies if it has unlimited resources of time and tape, so the limitation you describe effectively applies to anything. I guess the difference is that some things can be adjusted while running (hot swapping more RAM/replacing broken parts)

kuroi neko

@trichoplax I even did a bit of javascript to play with snake bits: petiteleve.free.fr/SO/sweep.html

Peter Taylor

@MartinBüttner That's true for any sufficiently powerful computational system.

trichoplax

@kuroineko Looks a lot sparser than your PHP images. I'm not sure what I'm looking at

kuroi neko

you can drag points around, except the center of rotation.

Martin Büttner

18:24

@PeterTaylor yeah, my point. ^^ I guess at this point, being Turing complete really doesn't make any practical difference

trichoplax

@kuroineko Oh! I thought I was looking at a still image :)

kuroi neko

here is a picture : petiteleve.free.fr/SO/_sweep2.png

I'm not used to talk in English maths, but I'll try a simple explanation

Martin Büttner

@trichoplax I mean it's also just a technical limit of the implementation for regex. there's nothing conceptual stopping it from being Turing complete. it's just that they added an "optimisation" which makes quantifiers skip empty matches if they have already matched the minimum amount.

trichoplax

@MartinBüttner So you could reimplement with the same rules but no limit?

Martin Büttner

yeah. I think if I only removed the restriction for ungreedy quantifiers it wouldn't even make any difference for "normal" regex application

kuroi neko

18:28

if we call M the point of the line supporting the segment that is closest to the center of rotation and M falls within the segment, then you have to split the segment at M.

Martin Büttner

@trichoplax arguably, going by the semantics of regex, it is Turing complete

kuroi neko

If M is not within the segment, then you can test whether a point is inside the swept area with 4 half planes and 2 radius tests.

Martin Büttner

(if I don't have any other mistake in my reasoning)

trichoplax

"the segment that is closest to the center of rotation". Does this segment have the centre of rotation as one of its endpoints? Or is it just closer to the centre than the other segments being considered?

Martin Büttner

but because the implementation doesn't try hard enough when backtracking, it's not possible with the official implementation

trichoplax

18:31

@MartinBüttner Yes that sounds reasonable. It is a failure of the implementation that it terminates before the instruction has been completed

Martin Büttner

I should send a bug report :P

trichoplax

lol

kuroi neko

Imagine the line that prolongates the segment. On this line there is exactly one point that is closest from the center of rotation. It is the point you obtain by drawing a line orthogonal to the segment that goes through the center.

trichoplax

@kuroineko That makes perfect sense now. Now reading your original statement is perfectly clear

So even when M is within the segment it isn't a problem, you just have to consider the two parts of the segment as separate segments?

kuroi neko

Good :) Talking in maths usually makes me buzz like a fridge. Yes, exactly. You split the segment and perform separate checks on both halves (for twice the usual computation cost, of course)

trichoplax

18:36

But even for a length 2 segment, you're halving the comparisons needed so double the work is no worse. For anything longer than 2, even double the work is better than my approach of only looking at length 1 segments

kuroi neko

indeed

Martin Büttner

@Sp3000 Found another interesting quirk. Remember how * and + both include one zero-width pattern? *? doesn't, unless it has to... so *? actually backtracks inside, and tries once before giving up. (+? tries once right away, but won't go back for another attempt)

kuroi neko

and you can precompute all the half planes and radii, so checking unmoved points is fast

trichoplax

Very roughly, a third of all unit segments will be part of a longer segment, so there should be a significant reduction in number of checks.

kuroi neko

You can probably optimize the order of the checks between radii and half planes. And besides everything can be done with integers.

trichoplax

18:40

I should have thought of precomputing. My comparisons are based on translating the pivot point to the origin, so there will be a lot of duplication of calculation

kuroi neko

you still have to translate the checked points to the rotation center, though

trichoplax

yes

kuroi neko

but that's not very time consuming anyway.

trichoplax

No - still definitely worth precomputing. At least for speed. At present I'm also limited by memory

kuroi neko

actually I'm working on a C++ solver. I reckoned memory would be a problem with higher level languages, so I decided to go the hard way :)

I think I found a trick to eliminate symetric figures a bit quicker, but I will not be able to validate that before the bloody thing starts working.

trichoplax

18:45

Yes I was thinking if I got round to making a serious answer it would need to be something like C++.

kuroi neko

well nothing beats C++ as far as speed is concerned.

trichoplax

I was also thinking it would be helpful to have full control over the size of variables

kuroi neko

yes, especially to encode rotations and joints

I'm using bitfields. One to store the partitioning into straight segments, and another to encode left/right rotations

trichoplax

I was thinking of using 2 bits per joint, to indicate 0, 1 or 2. So instead you're just recording the joints that aren't straight?

kuroi neko

yep. And I take only a right turn for the 1st joint, to eliminate half of the symetrical figures.

trichoplax

18:51

When you say "the first joint" do you mean length 1 from the start, or the first point at which there is a turn?

kuroi neko

That takes care of all horizontal symetries. Plus another trick to eliminate vertical symetries just by looking at the partitions (before starting to bend the snakes)

the 1st point at which there is a turn

trichoplax

Nice

kuroi neko

The idea is that starting from the tail up will produce the same results as starting from the head if the partitions mirror each other

for instance a (2,1,3) partition will produce symetrical results of a (3,1,2)

so I gather pairs of symetrical partitions and eliminate one out of two.

trichoplax

Is the last digit the length to the last turn, or the length to the end of the snake?

kuroi neko

length of the rest of the snake

trichoplax

18:54

Cool. So there is no ambiguity

kuroi neko

so basically that cuts the search space nearly in half. Only "palindromic" partitions have no distinct symetric configuration.

for instance (2,1,2), or the basic flat snake (n)

trichoplax

This sounds like it will take considerably less memory - that should allow at least one or two more values to be calculated. My machine can only handle up to 16 with my code

kuroi neko

That does not change the NP completeness, but that might gain a 4x speed factor compared with a brute force folding approach. And if the swept area detection works as planned, that should also boost computation quite a bit.

trichoplax

A 3x speed increase would be enough to increase the score by 1

kuroi neko

due to the 3<sup>N-1</sup> number of configurations?

erf... <sup> does not work here it seems

trichoplax

19:00

If you're near the limit with your score (taking just over a minute) then 4x might be enough to increase the score by 2

:)

kuroi neko

If this tie breaker idea is implemented, that will not matter that much

trichoplax

It seems there are roughly 2.6 times as many combinations with each increase in length. So very roughly 3x time requirement

Rainbolt

FML. My insurance company just reported that my social security number was breached.

kuroi neko

Makes sense. Each new joint multiplies configurations by 3, and some small percentage gets trashed by illegal folding

New Sandboxed Posts

0

A: Sandbox for Proposed Challenges

This is only a first draft so far. I am happy to hear from your suggestiosn Assymetrical KOTH: Catch the Cat This is an assymetrical KOTH, you can submit programs as in the thread of the CATs or in the thred of CATCHERs. (The cat catcher is in fact that fat catcher with the rat and the bat at t...

trichoplax

19:03

I'm expecting that the 2.6 figure will stay fairly constant until the sequence diverges from the sequence of non-intersecting paths. At some point at or below length 31, the number of reachable shapes will suddenly be more restricted than simply the number of non-intersecting paths, then that figure of 2.6 should drop a little

kuroi neko

I suspect memory and cache issues will also influence computation time. It should get slower when memory consumption increases

Right, I'm off to bend some snakes :)

Rainbolt

@kuroineko Lol bentsnake.com

trichoplax

@kuroineko Have fun!

kuroi neko

You too!

Martin Büttner

yay, shaved another byte off the nether regex (and finally updated the explanation, which was still for the 126-byte version)

Optimizer

19:16

yay for 96 bytes

Rainbolt

@PhiNotPi Are you around?

PhiNotPi

Do you want me to be?

flawr

so here it is: meta.codegolf.stackexchange.com/a/4774/24877

Rainbolt

@PhiNotPi How do you want to interface with the wrapper? My proposal: Construct an instance of Wrapper, pass it the command arguments, and then call "prompt()" which returns an int?

PhiNotPi

@Rainbolt I guess that can work. I wouldn't have developed any kind of preference yet.

Rainbolt

19:23

So, using the example given in your question, you would say
Wrapper submissionOne = new Wrapper("perl awesomebot.plx 042 045 0 324 432 6");
int guessTwo = submissionOne.prompt();
Wrapper submissionTwo = new Wrapper("python wonderbot.py 042 045 0 324 432 6");
int guessTwo = submissionTwo.prompt();
// Do whatever you want with the guesses

If that looks alright then I'll go that direction

PhiNotPi

The output of the contestant will be two numbers, if that makes any difference.

It looks fine. I don't know any other way to do it.

A possibly snake-related paper: arxiv.org/pdf/hep-lat/9211062v1.pdf

Martin Büttner

@PhiNotPi I think the restrictions on self-avoiding walks are much less ... strict... than what Lembik asked for

PhiNotPi

I was hoping that some part of it would still apply, since I think people were talking about ways to number the snakes.

Unrelated: did you see my sandbox comment about the shoelace algorithm to find the area of a simple polygon?

Martin Büttner

oh, yeah, it might help to enumerate them and then just filter

@PhiNotPi yes I did, thank you

although I thought if it was trivial to adapt to self-intersecting polygons it wouldn't be specifically called an algorithm for determining the area of simple polygons ^^ ... but maybe you could somehow partition a self-intersecting polygon into simple polygons and then use this to determine each sub-area

PhiNotPi

The problems arise when the "winding" of the polygon changes direction.

If you have a line segment, you have to keep track of which side of the segment is "inside" and that can change when there are intersections.

You would have to take the polygon, divide it in to non-intersection regions, and then do the addition and subtraction.

I have to leave abruptly. Bye!

Zgarb

20:08

I just had an idea for a semi-cooperative KOTH. Posting to sandbox now.

New Sandboxed Posts

0

A: Sandbox for Proposed Challenges

Semi-Cooperative KOTH: Grid-Routing Battle (TODO: Work in progress. For starters, a better name would be nice.) king-of-the-hill grid path-finding This is a semi-cooperative king-of-the-hill challenge, where the bots construct paths through a two-dimensional grid graph. The bot who controls th...

randomra

were there any cooperative KOTH before?

Martin Büttner

I don't think so

Zgarb

I remember it being discussed at some point, when I was lurking here. :P

Martin Büttner

@Zgarb did you mean "0 < y < 2N^2-1"?

yes, it has been discussed before but I am not aware of an actual challenge yet

Zgarb

20:13

@MartinBüttner Nope, I mean "0 <= y < 2N^2-1". The sources have outgoing edges too.

Martin Büttner

oh sorry... they are all to y+1... I saw one of them as y-1

Geobits

Can source/sink vertices be claimed/owned/broken?

Zgarb

@Geobits At this point, I'm thinking they can be.

Martin Büttner

sounds interesting!

Geobits

I think a horizontal dotted line might be interesting. You won't get as many points on each path, but every path will have at least one of your vertices on it.

Zgarb

20:21

I have to go now, but this is something I'll be (slowly) working on.

Please leave comments at the sandbox. ;)

Martin Büttner

does anyone know how we count the bytes of additional interpreter/compiler arguments? do we count the -/-- ... do we count the spaces if we need multiple arguments? if not, do we count the = in something like -option=10 (where I can usually replace the = with a space)?

Martin Büttner

21:07

apparently not

posted on meta

New Meta Posts

0

Q: How do we count compiler/interpreter flags?

It's accepted practice to include non-standard compiler or interpreter flags in a program's byte count (most often used with Perl and Ruby, to run the program in an implicit I/O loop - but there are other use cases). However, I can't find any information about how exactly why count these, and if...

Rainbolt

21:49

@PhiNotPi Here is the wrapper (meta bot post incoming).

I tested it with Python and Java programs.

FUZxxl

Hey ho

Can someone upvote me so I can post a snippet?

0

A: Showcase your language one vote at a time [experimental challenge]

APL Factoid APL (A Programming Language) started out as an interpreter for a formula notation devised by Ken Iverson. When the language was designed, people used teletypwriters to communicate with computers. The character set of these was limited, but due to their construction, one could put mu...

Martin Büttner

whoa, no APL post yet, I'm surprised

Rainbolt

Hmmm... 10 rep for a history lesson

FUZxxl

give me a second

New Meta Posts

0

Q: Java Wrapper for KotH

Description This is a Java wrapper class for communicating with submissions written in other languages. If you decide to use this for a challenge, make your life easier and require submissions to post the command that runs it. If they can't run it from the command prompt, then you probably can't...

discussion

FUZxxl

21:58

here you are.

Martin Büttner

22:16

@feersum just saw your comment, interesting idea

FUZxxl

@MartinBüttner There was an APL submission but it was deleted because said user already submitted a J solution.

Martin Büttner

oh, right

FUZxxl

Let's hope I get another upvote soon so I can post another example.

Peter Taylor

22:36

13

A: On "interactive" answers and other special conditions

My basic guideline would be "as the problem statement says". Which is mostly to mean it's allowed to explicitly override anything it wants from what I'm about to say next. Actions to invoke For test-case/IO programs, I like it better when the whole invocation is possible as a single line, thro...

captncraig

There you go @FU

@FUZxxl

Is there a keystroke to accept user name autocomplete in chat, or do I need to click it?

Doorknob

Tab

captncraig

lol

FUZxxl

@captncraig I'm not sure…

Doorknob

(Although preferably, use the reply arrow that appears when you hover over a message. That way, it's clear which message you're replying to, and things onebox correctly.)

FUZxxl

22:43

Hm… the 3-character snippet is a bit anticlimatic. I have a cool four-character snippet though.

Rainbolt

@MartinBüttner In theory, could someone invent a compiler whose flags were Turing complete?

Martin Büttner

@Rainbolt do you mean gcc? :P

FUZxxl

Or generally any Unix-like C compiler. They support setting arbitrary defines on the command line.

Just do

Doorknob

@Rainbolt ./compile -bfCodeToExecute="++--><..." emptyfile.txt

FUZxxl

cc -DFOO=some_code file.c

Rainbolt

22:52

Just wanted to establish that there was some potential for flag abuse

Otherwise I would downvote my own meta answer

FUZxxl

4 character example incoming!

Martin Büttner

@Peter thanks, I didn't find that one. the "characters beyond equivalent standard invocation" rule seems to make sense, too, although I'm not sure it's always possible to determine that objectively

Rainbolt

I think that the standard vs non standard should remain somewhat subjective

It's one of those "I know abuse when I see it" kinds of things

Martin Büttner

oh yeah, I don't mean deciding what standard flags are. but deciding what the "shortest equivalent invocation" is, could be a bit too dodgy

which is why I prefer your proposal

@Peter I think you said something like the even-odd area of a self-intersecting polygon just being "a simple fold" or something. can you find any links to standard algorithms? I'm having a surprisingly hard time googling this.

Peter Taylor

23:12

@MartinBüttner I was mistaken: I thought the shoelace algorithm worked on self-intersecting polygons.

Martin Büttner

oh right. I guess that means at least it's an interesting challenge :D

FUZxxl

I wonder why people have such a hate for solutions in J. I can understand that for CJam and Pyth, languages constructed specifically for golfing, but J is a serious programming language with a long history and a well-thought design.

Martin Büttner

the little I found so far suggests that you can find all the intersections with Bentley-Ottman

I'm sure you can work from there, but I wonder what the best approach

Peter Taylor

Right now I'm mainly thinking about Morra.

Martin Büttner

fair enough ;)

FUZxxl

23:22

@PeterTaylor Wow. You still have the avatar from that challenge.

Peter Taylor

@FUZxxl I'm more privacy-conscious than these people who post real pictures of themselves (Martin, grc, Doorknob, ...)

FUZxxl

I can't say that; it's too easy to figure out who I am.

Literally ten seconds of clicking links leads to a picture of me.

Peter Taylor

@Rainbolt, I've deleted my comments on your meta post because they're now obsolete.

FUZxxl

This username is now tainted with my real name; I'm too lazy to make a new one.

Doorknob

Not many people can tell, but my profile picture is actually slightly altered by an image editor. (I'm really good at image editing, so most people think it's the real me.)

Martin Büttner

23:27

@Doorknob it's the blur on the edges right?

Doorknob

@MartinBüttner I also cropped out the doorknob and added a blue background.

(I like how you just went right along with the joke :P)

Martin Büttner

@Doorknob oh right, I thought you might have been mounted on a smooth blue door ... that's how good your image editing skills are.

anyway, I'm off for tonight...

Doorknob

Yep. I'm personally very proud of how skilled I am with the paint bucket tool.

FUZxxl

23:43

hm… still waiting for another upvote so I can show off an example with five character.

Transcript for