The Nineteenth Byte

@overactor each path travels up one side of the map, detouring horizontally across the map wherever there's room. often resulting in a row (pair) of the map being entirely filled by just one of the paths, but sometimes they share and meet mid-row.

Martin Büttner

@Rainbolt sure

Sparr

@overactor the non-dynamic version of his path looks like this:

 _ _ _
|_   _|
 _| |_
|_   _|
 _| |_
|_____|

Rainbolt

oooooo You can get clever and register yourself with the shutdown hook

user2179021

@Sparr ok

overactor

@Sparr Yeah, I got that, the question was more, when does he decide to lengthen one path?

and by how much?

Sparr

7:28 PM

you lengthen a path as soon as the walker reaches the end of it

overactor

yeah, I suspected as much

Sparr

 _ _ _
|  _ _|
| |_ _
|  _ _|
| |_ _
|_____|

overactor

do you double the total path length each time?

Sparr

no

you extend it by one unit

(well, effectively by 2 units)

what I just pasted is what his maze looks like if the walker explores the right side a lot more than the left side

Martin Büttner

@Rainbolt That's limited to Java submissions though, right?

overactor

7:30 PM

that does make more sense

Sparr

?   ?_
|_ _ _|

overactor

for some reason I had myself convinced that doubling the path size was the way to go, since that puts you equally far away from the end of each path.

But obviously making it one longer is the way to go.

Sparr

that's the bottom of the map after the left side has been explored zero steps and the right side 4 steps

if the walker gets to the left ? first, then the left path will go right, towards the middle of the maze

and the right path will later be forced to go up, then back right, when the right ? is later reached

if the walker gets to the right ? first then then the right path will continue to the left, consuming the rest of that first row of detour, and the left ? will turn into a | when it gets visited later.

Rainbolt

@MartinBüttner I just wrote an exit handler in Python and it actually worked better than the java one. All of the output, even from the exit handler, was redirected to the console from Invoker. I'm satisfied that this works.

Martin Büttner

sweet :)

Sparr

7:33 PM

you actually only extend it one step at a time, but you're really committing the maze layout to some larger number of predetermined future steps

here's the balanced(ish) version of my idea for a dynamic two path maze

 _ _ _ _ _ _
|  _ _ _ _ _|
| |_ _ _ _ _
|  _   _ _ _|
| | | |_ _ _
| | |  _   _|
| | | | | |_
|_| |_| |_ _|

I think it might be a tiny bit more efficient than justhalf's version

but I'm too lazy to implement the path extension logic

alternately, that mirrored to swap start and finish

the reasoning being that the existing dynamic two path solutions all have different shapes at the start of the two paths. one starts zig zagging immediately, the other has to cross the whole maze first.

allowing either to zig zag immediately, or neither, should give a small boost

user2179021

@Sparr do you think this logic would be the same for 100 by 100?

Sparr

yes

most of the solutions lately are generalized

debugging logic even at 20x20 is annoying

I did all of my testing at 6x6 or smaller

user2179021

I am not sure I understand what the optimal numbre of paths would be for 100 by 100

what do you think?

Sparr

I still think it's two

I don't think a dynamic four would be better than dynamic two.

static three is worse than static two, at any size maze

user2179021

ah interesting

peter taylor's 4 path is better than his 3 or 2 path right?

It's just not as dynamic as your solution

Sparr

7:45 PM

I'm actually not sure why peter's static 4 is better than his static 2

I'll have to look into that

user2179021

he did something smart :)

Rainbolt

@MartinBüttner I made a README for you. Let me know if it causes you trouble.

Geobits

Peter's 4-path isn't static, that's why it beats his static 2-path.

Rainbolt

If you trust me, download the jar. If you don't, the source code is there too.

Sparr

nope, I can't figure it out

I'm gonna have to run and visualize peter's solution, I think

Rainbolt

7:52 PM

Dang

I was in the middle of Googling that...

Geobits

:D

Rainbolt

Was that a reference to anything?

Sparr

assuming he's done the math right, which his results seem to verify, then an 8 or 16 path solution could be better

user2179021

could anyone take a look at meta.codegolf.stackexchange.com/questions/2140/… please

Rainbolt

All I got was "Jesus shouted to the crowds, “If you trust me, you are trusting not only me, but also God who sent me.""

Sparr

7:53 PM

N goes down a small amount with more paths, because the intersection "rooms" get bigger

Rainbolt

Love how one of those quotation marks is tilted lol

Geobits

@Rainbolt I didn't lift it word for word. An imagining of Jasmine's (from Disney's Aladdin) inner dialog with the "Do you trust me?" bit.

I'm... not quite right today.

New Sandboxed Posts

0

A: Sandbox for Proposed Challenges

Restricted memory optimization The edit distance between two strings is the minimal number of single character insertions, deletions and substitutions needed to transform one string into the other. If the two strings have length n each, it is well known that this can be done in O(n^2) time by dy...

Sparr

@user2179021 I believe a dynamic 4-path would be better than static, but you'd need to track a LOT more info and weight the dynamic-ness against which pass you're on

user2179021

@Sparr I find it fascinating.. I mean what is the optimal strategy? Is it actually something complicated and detailed?

Sparr

7:56 PM

yes, I suspect there are progressively more complex approaches for squeezing fractions of a percent of additional score

for example, right now we are all using zig zags

simple S-shaped switchbacks

something hilbert-curve-y would probably be better, in terms of committing to as little extra extension as possible with each extension

user2179021

I think that's pretty interesting in itself!

the fully static problem just seems to have one boring optimal strategy

make a long path

Martin Büttner

@Rainbolt Thanks a lot, I'll test it in a minute.

Is it too late to post today?

I think I might give it a try.

So far I've posted all my challenges around European lunchtime... let's try something new...

user2179021

if anyone can break my new question I would be very grateful :)

Sparr

I think my stairstep zigzags will be slightly better than justhalf's parallel "combs"

user2179021

I would love it if it weren't broken once it leaves the sandbox.. which would be a first!

Sparr

7:59 PM

and his parallel combs are better than my parallel-the-other-way combs

every step he takes, he's committing to 2-3 steps

user2179021

@Sparr maybe there is a cool optimal shape. Like a hilbert curve as you say

Sparr

my solution commits to ~190 additional steps at a time

user2179021

:)

Sparr

err, ~36

forgot we made the maze smaller :)

I can imagine a solution that commits to 1-2 steps at a time, and that would be better than his, by a small margin

Geobits

-1

Q: Simple string encryption algorithm cracking (\w reward)

I have created a simple encryption algorithm. Your challenge, if you choose to accept it, is to reverse engineer the string, which is a simple English string with punctuation, back to the original then post your results as a response to this post. The prize for the person who manages to crack th...

Martin Büttner

8:04 PM

:/

@Rainbolt downloading your malware now

Rainbolt

rubs hands together maliciously

Martin Büttner

oh

could I request one more change to it? :) make the time limit in seconds the first command line argument? so I can test it on my machine without having to wait 10 minutes?

Geobits

Aww, I haven't gotten to a machine that I can allocate 6GB+ of memory on yet. Now I might not be first to answer :(

Speaking of which, that isn't a problem, is it?

Martin Büttner

@Geobits it kinda is :D

I never have 6GB spare on my machine ^^

I didn't think this problem would be memory intensive. But I think I'll put my usual memory cap on it (1GB)

Geobits

It's very memory intensive if you calculate all perfect squares up to 2^53 up front and save them in a map with their roots :D

Martin Büttner

8:10 PM

oh

user2179021

I added a "help needed" section to meta.codegolf.stackexchange.com/questions/2140/…

how do I add a tag to a sandbox question?

Sparr

I heard someone recently describing some desktop art/music/something software with minimum requirements of 16GB of RAM

Martin Büttner

@user2179021 [tag:tagname]

user2179021

thanks

Martin Büttner

@Sparr ain't nobody got RAM fo' dat

user2179021

8:15 PM

and how do I make the title in the right format in sandbox?

Martin Büttner

@user2179021 prepend # to the line

user2179021

perfect

meta.codegolf.stackexchange.com/questions/2140/… is much improved ;)

Martin Büttner

just hit "edit" on another answer to see their markdown :D

user2179021

all the edit buttons are greyed out

in the sandbox

so my remaining problem is how to verify the answers given

Martin Büttner

then click on history and view the markdown there ^^

user2179021

8:17 PM

ok

I could ask for the list of edits too

but that really might be too hard :)

hmm

Martin Büttner

do it as I'll do with the integer lattice: make them add a switch which will cause the program to print out the edits. in that mode, they may use more memory.

user2179021

ok cool

Peter Taylor

@MartinBüttner Doesn't ring any bells.

@MartinBüttner Still complicates things for GS. Does it count memory on the stack or whatever the interpreter is using internally too? What about integers: how much do they count as, bearing in mind that they can grow arbitrarily?

@user2179021 Not C. Unless you mandate the use of <inttypes.h> and request people to downvote any question using a raw int.

@Geobits 2^52 + 36

@user2179021 No, it's just the number after 3. I wonder whether it's possible to go to higher powers of two, but I'm pretty sure the path complexity increases faster than the score.

@Sparr It turns into static 2.

Martin Büttner

@PeterTaylor Why would you even do this challenge in GolfScript?

Peter Taylor

I might try to add some graphics rather than the ASCII art.

Why not? Nice modern language...

Rainbolt

8:27 PM

And here I thought society was progressing from gibberish to something that resembles natural language...

Sparr

@PeterTaylor I think the operation of your intersections is what was confusing me

@PeterTaylor did you see mine and justhalf's dynamic path lengths? he's really close to optimal.

(I think)

dynamic four paths might be better, but is likely to be more complicated

Peter Taylor

Images coming up

@Sparr, see whether the new images make it clearer what's going on with the second cut.

Sparr

8:49 PM

it does

based on that, I think you could do 8 paths

or arbitrary 2^n paths, for a large enough maze

there's a tiny bit of overhead around the start and finish for more paths

4 might be optimal for 20x20 maze. I suspect 8 or 16 would be for 100x100 maze

Martin Büttner

@Rainbolt need Java support... I just tried compiling your code with javac Invoker.java and then java Invoker ruby test.rb ... I get "Could not find or load main class"

Sparr

and, ignoring that, making your paths dynamic would definitely improve your score. you could almost certainly take the #1 spot

Rainbolt

@MartinBüttner Did you download the jar or are you trying to compile the class?

Martin Büttner

both

the .jar works

Rainbolt

If you are trying to compile the class, you'll have to compile Invoker.class (not Invoker.java)

Martin Büttner

8:51 PM

I just tried compiling it myself, so I could add the command-line argument myself and stop bothering you

Rainbolt

so javac Invoker.class

creates Invoker.java

Martin Büttner

ugh

I always get that the wrong way round

who came up with that, srsly

Rainbolt

I hate it too

You write python code, you get .py files

You write java code, you get .class files

Martin Büttner

well especially since Java is C inspired... there you have .c files which compile to .o(bject) files

Rainbolt

and .cs and .cpp for c# and c++

Martin Büttner

8:53 PM

yup

or any other reasonable language

Rainbolt

This is because in Java, everything exists inside of a class

In other languages, this is not true

Martin Büttner

javac Invoker.class

gives

javac: invalid flag: Invoker.class
Usage: javac <options> <source files>
use -help for a list of possible options

are you sure about this?

Sparr

@Rainbolt no. python:.py::java:.java

Martin Büttner

because I also only get syntax highlighting for .java

Sparr

@Rainbolt .class is more like .pyc

@MartinBüttner you run javac on .java files. class files are ready to be fed to java

Martin Büttner

8:55 PM

okay

that doesn't work then

Rainbolt

Ok i lied

.java produces .class files

Why are you trying to confuse me Martin?!

Sparr

@MartinBüttner what you want will look something like this "java -cp . packagename.classname"

Martin Büttner

ah package name

Sparr

@MartinBüttner possibly one level up from the .class files

Rainbolt

It's javac Invoker.java

to compile

I'll go test while I continue to spew bullshit everywhere

Sparr

8:56 PM

the worst part about java is that so many java developers rely on an IDE that most of them have no idea how to compile or run their code without it

Rainbolt

hey to be fair I just got the extensions backwards!

Martin Büttner

hm java -cp . invoker.Invoker ruby .\test.rb still doesn't work

Sparr

step 1: install Eclipse / IntelliJ / etc

@MartinBüttner go up a level, and make sure the directory containing Invoker.class is named invoker

Rainbolt

Oh dear god. I have to go add java to my path. This is already a headache

Sparr

# find
./invoker
./invoker/Invoker.class
# java -cp . invoker.Invoker

Rainbolt

8:58 PM

rename Invoker.class to Invoker.java

If it's the uncompiled source code

Martin Büttner

@Sparr subfolders...

Rainbolt

Ok mine compiled just fine

Martin Büttner

seems to be working now

thanks

Rainbolt

np

I'm both defensive and embarrassed to not know which one compiled into which lol

If I ever get a job in Java instead of C#, maybe I'll get my stuff down.

Martin Büttner

that's odd

I just tried a simple ruby program, which would trap SIGINT and then output lol

if I try that from the command line, it does output lol, but also:

./test.rb:1:in `write': can't be called from trap context (ThreadError)
     from ./test.rb:1:in `puts'
     from ./test.rb:1:in `puts'
     from ./test.rb:1:in `block in <main>'
     from ./test.rb:2:in `call'
     from ./test.rb:2:in `<main>'

Rainbolt

9:04 PM

interesting

Martin Büttner

if I run it from your invoker, the invoker doesn't get any output

(if I output something outside of the trap that comes through though)

Rainbolt

Oh, that's probably because Trap is actually it's own thread with it's own output

Martin Büttner

oh okay

Rainbolt

2 hours ago, by Rainbolt

@MartinBüttner If I don't capture output from a sub sub process, is that ok?

Interestingly enough, Python doesn't have this problem. You can register a function or even a series of functions to run on exit

And so they do exactly that

Martin Büttner

I'm registering a block... no clue how to tell it not to use that in a separate thread though

Rainbolt

9:07 PM

I think the problem is two sided

1) Java can't put bubbles around things that don't run on the JVM

Martin Büttner

the other oddity is that all examples in the rubydoc use puts inside the trap block

Rainbolt

2) Programs shouldn't really be able to output stuff after being terminated

Martin Büttner

then again their examples don't use SIGINT

Rainbolt

Can you pass your output stream to the trap block?

Martin Büttner

oh they do

Rainbolt

9:09 PM

If so, you could essentially keep the stream alive by passing it to the exit handler

Martin Büttner

doesn't help

this is in the docs

Signal.trap("INT") { |signo| puts Signal.signame(signo) }
Process.kill("INT", 0)

Rainbolt

I don't know Ruby. It looks like your thread gets killed immediately?

Then the thread you registered previously begins to run (I assume)

Martin Büttner

ugh... I'll probably try file-only output tomorrow

Rainbolt

That'll be an interesting problem as well. During our last second rush, if you are trying to dump stuff out at the same time that I am reading, that could get weird.

The goal is 10 minutes of pure uninterrupted processing time where the algorithm is not worried about the time limit, correct?

Then after that, the goal is to stop doing any real work, or at least finish the current iteration of whatever we're doing and output what we have?

What will really be tough is that if I kill you in the middle of file I/O, and then your shutdown thread begins to execute, there may be a split second where the file is locked and the shutdown thread can't access it.

I think you run into the same problem there

It might just be easier to just ask submissions to time themselves than to try and force them to behave

Martin Büttner

10:04 PM

@Rainbolt yes

@Rainbolt don't finish your current iteration, but output what you have (it's just one number)

@Rainbolt but how do I verify that that's fair?

just stuff it in a 10 minute time out an kill it at the end? and if they haven't produce any result in those 10 minutes it's their fault?

@PeterTaylor any idea what the best way would be to turn that into a challenge? there are a lot of ways to do this

Rainbolt

10:24 PM

@MartinBüttner Exactly. Think of it like this: they have ten minutes to produce a result. How is it possible that a computer program can't accurately keep track of time?

Peter Taylor

10:59 PM

Golf "find the chromatic number" looks like the best option to me. Or maybe "find the fractional chromatic number", but that might scare too many people away.

New Sandboxed Posts

11:17 PM

0

A: Sandbox for Proposed Challenges

A Little Cloud code-golf math graphical-output Thomus Chandler is sad. Draw him a cloud to cheer him up. Note: Drawing a cloud won't actually cheer him up. A circle can be defined as a 3-tuple (x,y,r) where x is the x position of the circle on a Cartesian plane, y is the y position of the circ...

Transcript for