The Nineteenth Byte - 2014-08-28 (page 1 of 3)

« first day (1307 days earlier) ← previous day next day → last day (3552 days later) »

Martin Büttner

12:05 AM

wth

4 solutions in an hour

There hasn't been a challenge about Golomb rulers yet.

I think I could create one in like 5 seconds.

Martin Büttner

what's that?

In mathematics, a Golomb ruler is a set of marks at integer positions along an imaginary ruler such that no two pairs of marks are the same distance apart. The number of marks on the ruler is its order, and the largest distance between two of its marks is its length. Translation and reflection of a Golomb ruler are considered trivial, so the smallest mark is customarily put at 0 and the next mark at the smaller of its two possible values. The Golomb ruler was named for Solomon W. Golomb and discovered independently by Sidon and Babcock. There is no requirement that a Golomb ruler be able to measure...

Martin Büttner

ah interesting

The challenge could be [code-golf] with the goal being to find optimal Golomb rulers.

12:50 AM

I wonder if an "emulate a quantum computer" challenge would be too complex.

githubphagocyte

@PhiNotPi would that be in the sense of summing over all possibilities? Possible for problems with a reasonably small space of possibilities. Not possible for the kind of large problems you'd use a real quantum computer for, but that doesn't stop you making a toy one for small versions of the problem

IIRC, the internal state of an N-qubit quantum computer can be described with 2^N imaginary numbers.

githubphagocyte

Why do they need to be imaginary? That sounds interesting...

It has 3^N possible ternary states, right? Each qubit can be 0, 1, or in superposition? I have no idea how they work.

Or is it more complicated than just one of those 3 states? Is that why you need imaginary numbers?

Lone imaginary numbers or complex numbers?

I actually meant complex numbers.

githubphagocyte

Ah OK. I still don't know how any of it works...

:)

1:01 AM

A superposition does not have to be a 50-50 chance. It can be any probability between 0 and 1.

Not just that, but they contain additional information which isn't reflected in the probabilities.

Each quantum bit is represented by two complex numbers, A and B (I can't type alpha and beta).

githubphagocyte

wow

So alpha and beta are real-valued complex numbers (I mean the real part and the imaginary part can both take any real value not just 0 or 1)?

Yes.

And |A|^2 + |B|^2 = 1

Not just that, they can be entangled with each other as well.

githubphagocyte

This would need a very clear explanation to attract answers from people like me who don't have any background... I'd like to see it done though.

Meaning that there is a correlation between the value of one bit and other.

githubphagocyte

Entanglement is binary, right? I mean for any given two qubits either they are entangled or they are not?

1:05 AM

No.

githubphagocyte

So they can have a probability of being entangled too?

Once again, entanglement is described by complex numbers.

githubphagocyte

This is fantastic. I think a golf question would have to model quite a small quantum computer though...

Entanglement is weird.

Let's say that two qubits (X and Y) are completely entangled, such that when X is measured to be either 0 or 1, Y is always the opposite.

githubphagocyte

OK

1:09 AM

So, you take the two qubits and move them to opposite sides of the universe (or some very long distance).

githubphagocyte

Then they're still entangled, right?

The first qubit is measured to be a 1. Then, one millisecond later (faster than the speed of light would convey information across the distance), the second qubit is measured.

Yes, they are entangled.

githubphagocyte

So is the complication that there is a probability that you measure one of them, which affects whether they are still entangled?

Then, the second qubit has a 100% chance of being a 0 when measured.

As soon as you measure one of them, the entanglement collapses, and the value of the other qubit is determined as well.

githubphagocyte

I'm still not sure where the fractional entanglement comes in.

Is it due to there being a probability that they got entangled in the first place?

1:15 AM

It is because the state of one of them need not be completely determined by the other.

githubphagocyte

I might need to read up on this...

Instead of this
0% 00
50% 01
50% 10
0% 11

It could be this:

30% 00
42% 01
20% 10
8% 11

githubphagocyte

It doesn't even need to be balanced between 00 and 11 for symmetry?

no

githubphagocyte

That's a whole lot of possibilities.

Once our species gets the hang of using this possibility space there is going to be a whole lot of trouble. Fascinating, terrifying trouble.

1:20 AM

Imagine what would happen in an Intro to Programming class...

(By the way, entanglement isn't limited to 2 qubits)

githubphagocyte

Powers of 2? Or arbitrary numbers entangled?

any number

githubphagocyte

I can imagine a future where such technology allows us to extend our lives to hundreds of years, but it will take until we're in our 80s before we are ready for that Intro to Programming class...

Apparently, the most complicated thing a quantum computer has done so far is to factor 21 = 3 * 7.

githubphagocyte

Do you count the D-Wave computers as quantum?

1:31 AM

Not really.

They are pretty fast and all, but they don't actually lower the time complexity of the computation.

githubphagocyte

They claim to use qubits, but there seems to be a lot of disagreement on that.

They might be. but it's how they use the qubits that counts.

githubphagocyte

Do you think their work is heading in the right direction to get full quantum computers? Or is it just a side track?

Seems to be a side track so far. I don't think they are aiming for the same type of quantum computer.

A quantum computer could be an interesting challenge. I would have to read up on a lot more specifics before I could create a challenge.

githubphagocyte

In theory, if you had a working quantum computer, could you use it to find solutions from a huge space very quickly, including finding a classical computer program rather than writing it?

1:41 AM

Yes, I think it could be used for that.

githubphagocyte

The universe keeps on getting bigger, the more I hear...

Quantum computers, IIRC, offer at least a quadratic speedup on most everything.

I can break a 2048-bit hash in the time that it takes a classical computer to break a 1024-bit hash.

githubphagocyte

A classical computer would take 2^1024 times as long, right?

I think so.

githubphagocyte

That's a speed up worth shouting about

Still not quite enough of a speed up to consider treating programming itself as a hash breaking exercise. Sounds like it would take something more to put programmers out of a job

1:45 AM

Perhaps there could be a hash function (program source) -> (output)

githubphagocyte

Exactly - brute forcing the programming problem by trying out every possible program and testing all possible inputs

Even for fairly small programs that would need much more than a quadratic speed up to be practical though

If you combined a quantum computer with an evolutionary algorithm though...

Quantum computers don't brute force things by doing one possibility after another, they perform ever possibility at once.

^ Or, at least that's true in many cases.

But, you are right that a quadratic speedup may not be enough,

Hash-based cryptography can be secured by making bigger numbers.

githubphagocyte

Yes that's my thinking - things which would normally be impractical to brute force (take forever) might be worth brute forcing on a quantum computer that doesn't have to do it all one at a time

If the numbers only need to be twice as long then we shouldn't even notice much difference.

Factoring numbers is in BQP (quantum polynomial time), which means that all RSA-like cryptography is completely broken.

githubphagocyte

2:01 AM

Public key encryption might have to be completely rethought, but a one time pad is still quantum proof, right?

All you can get is a complete list of all possible texts of that length

I want a quantum computer

Yes, a one-time pad is completely unbreakable, since you would end up with every possible message.

githubphagocyte

I wonder if you could get quantum calculation effects from a series of pieces of paper with slits in, like an extended version of Young's Double Slit experiment, with the distances tailored to do some useful calculation.

@NathanMerrill pong

githubphagocyte

It would speed up my traveling salesman attempt. It's a long time since the single line closed curve drawing question was posted...

2:09 AM

It would certainly make attack on private key encryption easy... you could own all the Bitcoins in the world................

/me thinks

githubphagocyte

@TheDoctor not just bitcoin - most of the cryptocurrencies currently out there. If you have to wait until technology arrives that breaks them all, it won't make you much money though...

I wonder if anyone's working on a quantum-proof cryptocurrency?

Bitcoin is pretty much already quantum proof since it relies on hash functions.

githubphagocyte

@PhiNotPi the blockchain is based on hash functions but what about the private keys? I think they're elliptic curve key pairs. The addresses are put through an extra few hashes but once you've used an address once the public key is visible. Is an elliptic curve based public key susceptible to a quantum computer?

I don't know the answer to that.

0

Q: Is adding a test suite to a question as a community wiki answer helpful?

The specific question I recently posted my test suite as a community wiki answer to a couple of questions that I worked on. Two contributions so far are: Family Tree Solver Put a list in order (Amusingly, it has more upvotes than the answers.) The test suites use perl TAP, which is as clos...

2:20 AM

A google search says that yes, quantum computers can break elliptic curve cryptography.

@Sparr I'm not going to be able to rotate the lines

Consider the following:

D = 3

How would that get shifted?

Or, to further make my point:

Bye!

Copy 3 D
Copy D C
Copy #C *#C+1
Move

bye @PhiNotPi

@NathanMerrill if you're rotating code forward N lines, then any copy into C is incremented by N

so that code rotated forward five lines would be...

githubphagocyte

@PhiNotPi bye :)

2:24 AM

Copy 3 D
Copy D+5 C
Copy #C *#C+1
Move

I think?

remind me what Copy #C *#C+1 does?

why into C?

because a copy into C is an absolute jump. if all my code is moved forward 5 lines, I want all my absolute jumps to be +5

It'll take your Cth line and copy it to the Cth+1 line of your opponent

Ok, another case:

is this ASM?

Copy #C ... doesn't need to be rotated, because that is always pointing at the Copy line itself

2:26 AM

Copy 3 D
Copy #D *#D
Move D

@TheDoctor meta.codegolf.stackexchange.com/questions/1847/…

@TheDoctor no, its my upcoming KoTH

@NathanMerrill nothing changes there, for code rotation

lets say that my code is shifted 5 down, and his code is shifted 3 down

really?

hm

2:27 AM

what if I do a

Copy #3 #5

remembers why i left in the first place

if your code is shifted down 5 and his is shifted down 3 then you're going to be targeting a different line of his code than otherwise. that's the whole point of rotation. he COULD submit a new version of his bot that's rotated down. if your code relies on whether I put FLAG at the top or bottom of my code, I think that's not cool.

but here's the thing

it changes my own code

If I reference line 3, then it no longer references line 3

nucular.github.io/stuff/svgtest

oh, hmm. Copy #X ... should be Copy #X+N ...

that would apply to the Copy #D, too, so I was wrong above

2:29 AM

Ok, then let's talk accessing a line

if my code is shifted 5 lines down

githubphagocyte

@TheDoctor um thanks...

does C start at 5?

the absolute line number of a copy to your opponent won't matter, and shouldn't. that's the whole point of my suggestion. if you use some logic to read their code, then base a copy on that, awesome, but that's relative, and that's going to work regardless of rotation

yes, start C at 5

ok, then Copy 0 A

that puts 0 in A, of course

2:31 AM

what does If A == C return

githubphagocyte

@NathanMerrill are there just going to be the same number of sitting duck bots lying around as any other bot (so a small minority) or will there be a large enough number of sitting ducks to allow building up a clone army?

you would want to +N for comparisons to C

considers previous judgement

@githubphagocyte there probably will be very few, if any duck bots

@NathanMerrill here's an alternative to the code rotation suggestion: instead of rotating every bot's code, only rotate references to enemy code. That would eliminate all of the concerns you're having now, and still accomplish the goal of my original suggestion

2:33 AM

agrees with previous judgment

ok, then next question

I've considered that

leaves

githubphagocyte

@NathanMerrill OK. I was just imagining a huge arena filled mostly with sitting ducks, with one of each contestant bot somewhere on the arena, spreading out into the sitting ducks making clones until they finally meet and battle

assume that my opponent is facing me

If **#C == #C

and you are, by definition of opponent, facing them

2:35 AM

does that return true?

let's say yes, although I'd need to think about how :)

It's really, really tough to get it right

are you asking in the context of self code rotation, or my alternative enemy code rotation?

either

ok, I'm gonna shift gears to the alternative

since I think it will be much simpler

any time my bot tries to read another bot's lines, the read gets rotated. ditto trying to read their C. that's it, I think. it wouldn't require anything else.

reading my own lines or C doesn't get rotated

2:37 AM

also, why is it a problem if they overwrite my last line of code?

or is it about the first line?

is completely ignored

well, if I read my opponent's opponent's code, do I get the same line back if it is both me?

@githubphagocyte one bot per entry and a lot of sitting ducks would shift the game even further in favor of fast offense, and it's already really really slanted that way, I think.

@NathanMerrill when you read any bot's code, you get it rotated by their N, except your own code isn't rotated.

githubphagocyte

@Sparr good point. Balance is more interesting.

whether you're reading your own line with #A or **#A or even ********#A, it's the target of the read that would determine the rotation

2:41 AM

so, yes?

If my code is rotated +5, and his code is +3, then **#A would be rotated +8?

no

reading your own code will never be rotated

no

...from a code standpoint, I don't know whether it is my own code

you don't, but the interpreter does

I mean, the interpreter doesn't

I haven't seen your interpreter, but that sounds weird :/

2:44 AM

I don't parse the string on runtime

I parse the string only initially

githubphagocyte

As long as the interpreter knows the rotation offset of the first and last bots in the chain (you and the other end of the ******), it can work out the difference, right?

Ok...this may actually be possible

I know how to do it, I think

Oh, some more problems

what would *C+C return?

assuming a rotation of 5?

*C+C+5?

when you read your opponent's C, it gets shifted by his code rotation

so *C+C becomes *C+C+5

(*C+5)+C, to be precise

that is absolutely not possible with the way I have the code constructed

oh, sorry

:(

2:50 AM

*C + *C

would that be +10?

*C + *C would be *C + 5 + *C + 5

ok, that is more feasible

the +5 should not happen in the same way as addition in the bot code happens

the +5 should happen during the resolution of *C

I know

bah, it makes things more tough though

in the get_my_c() function of the other_bot object, you should return my_c+my_code_rotation instead of my_c

totally made up framework there

2:51 AM

My code, with a few exceptions, doesn't really care about the variable type

that's wonky, since you've very strongly differentiated between how the variable types work :p

my argument parser now will have to know what kind of variable and whether or not the current bot it's referencing is its self

yeah

might be easier to go back to the original idea

they are actually really similar

githubphagocyte

Can't you treat yourself the same?

2:52 AM

more work to identify all the cases that need adjusting, but your parser doesn't need to change then

the only difference between the variables right now is their initial set value, and some of them are accessed differently

@githubphagocyte if you get rotated code and C when you read your own code/C then you also have to deal with things like Copy C C which would not work correctly

but none of them act differently

githubphagocyte

I mean wouldn't a bot with the same offset as you appear to have no offset (to you) so wouldn't you appear to have no offset to yourself too?

and by accessed, I mean that a certain piece of code accesses a certain variable

2:54 AM

@githubphagocyte not in any of the schemes we've discussed so far

githubphagocyte

Would doing it that way lose the advantages of the schemes you have been considering?

not really, but that still has the problem of requiring modification of your own code

@githubphagocyte how would the following work:

Copy 4 C
Copy #C *#C
Copy *#C #D

if reading your own lines/C gets rotated, then you also have to do rotation on assignment, and modify jumps, etc

@NathanMerrill Copy

:(

2:57 AM

what variables are shifted?

githubphagocyte

I don't yet see where the problem is

Is the rotation a fixed property of a given bot, or does it change during play?

Ok. I have a solution

You cannot submit solutions shorter than 16 lines

githubphagocyte

You mean no more than 8 flags?

er, you cannot submit solutions shorter than 24 lines

no, you can have 24 flags if you'd like

but, now, because I don't auto-fill the rest of the lines, shifting it is no longer a problem

githubphagocyte

I didn't see the bit where shifting was a problem

I might be a bit too far behind to ask useful questions

3:03 AM

because Flags would automatically get set on remaining lines, and code would automatically start at the top

therefore, to modify somebody's code you would point at either of those locations

shifting the code would make it so you can depend on such things

githubphagocyte

But anyone can write flags before their code right? Are you saying you would apply a random offset to each contestant's code, or apply a different offset to each of their 50 bots?

each of the bots would get a different offset, but that isn't the issue

githubphagocyte

Would that work with an extra variable per bot, that isn't readable by any bot but simply defines which one of their lines is zero?

its trying to make it work

yes, that might worok

githubphagocyte

Then absolute references within its own code would be corrected with its own offset, and any references to other bots would be unable to tell what their offset is, making them appear to simply be rotated versions of the code pasted in the question

It might be easier to accept that you might need to rewrite the controller from scratch and just ask questions in terms of what the contestants will see. Otherwise all your decisions will be biased by the pain of having to discard code that's already written...

3:13 AM

@NathanMerrill how does disallowing short entries matter?

Ok...I think setting the offset will work and be painless

githubphagocyte

Is there any type of contestant code that would be prevented by this approach?

trying to identify friendly bots

unless...

I make it hash based on the name

githubphagocyte

So all 50 of your bots will have the same offset?

yes

githubphagocyte

3:30 AM

That would prevent someone from tailoring their bot to defeat yours, so seems enough.

aye

or hash the code, or even just the entrant number modulo 24

githubphagocyte

Are you doing more than one run to give an average score? Could you just randomly assign an offset for each run, but apply it to all 50 of each contestants bots?

Hashing doesn't seem to add much benefit unless you are salting too, since the controller code will presumably be public

@githubphagocyte that doesn't make the problem any simpler

githubphagocyte

@Sparr what breaks if you have a variable per bot that specifies its offset but is not readable by any bot (including itself)?

nothing, but again that doesn't make the problem any simpler

githubphagocyte

3:34 AM

Is the problem people using the knowledge of other contestants' code?

that's the problem that I want to solve

the problem at hand is how to implement a code-rotation solution

option one is basically to actually rotate the code, which requires a lot of transformation of specific types of instructions, particularly manipulating C

option two is to alter the results of reading other bots' code

githubphagocyte

I think my suggestion is equivalent to your option two

Each bot has a hidden variable that indicates which position in its code is zero. That is used to label its own code lines so that all of its functionality works identically to the original unshifted code.

Other bots see the shifted code.

Well, I suppose this is option 1 and 2.

Ok. I think I have implemented the shifting

githubphagocyte

Rotate the code lines without actually adjusting any of the logic, and just offset before calculation

every bot has a shift variable, which is set to the hash of their name

I already had a common accessor function function

that was used only in bot's commands

githubphagocyte

3:42 AM

If the hash is clear from the controller code, will the controller code be public?

after following the person chain

yes

githubphagocyte

Will the hash function be salted?

you technically could code according to the hash of the controller's name

no

githubphagocyte

So the offset for each bot will be public?

yes

githubphagocyte

3:43 AM

That seems equivalent to not having an offset

@githubphagocyte but you don't know what name Nathan will give to the contestants. a lot of KOTH runners remove spaces, or replace with underscores, etc

I could do that

also, I'm going to have an implementation for bot Java and Python

I'm currently working on the Java one

githubphagocyte

If the offset was different each run then all entries would have an unknowable offset, rather than just those that are affected by any text alteration in their name. That seems simpler.

Python one is finished

but, to sate your worries, I now have a global variable

it is randomized at the beginning of each game

it is added to every hash

githubphagocyte

Sounds good.

If you really want to be paranoid you could specify that the random seed will be something that no one including yourself could know or control - say the lottery numbers on the night you run the contest...

3:48 AM

:p

might as well go geohashing

I try to tell people what geohashing all the time

but they always think I'm talking about geocaching and tune me out

githubphagocyte

geohashing is knowable in advance though, right? It's predictable?

no

its based off of the starting bid on the stock market that day

githubphagocyte

I thought it was just based on date - I'll have to refresh my memory..

Ah I see

@NathanMerrill I'm looking forward to entering this challenge, even if I won't come close to winning.

I think inline addition really added a lot to the potential strategies

as much so as going from 16 to 24 lines

githubphagocyte

4:02 AM

It does seem much more powerful now

I'm trying to imagine how to visualise battle

Colour coding based on the majority flag of each bot?

Not sure

I don't have any kind of graphical output

color by flag is definitely an option, although that doesn't tell you anything about original owner or behavior

but I've stepped through the code many times, and I'm quite confident there are none, if any bugs

but it's tough to know that without watching the bots run

I'm thinking a bot might be represented by four colors, in quadrants. one is the flag majority. one is weighted by all flags in the bot. one is weighted by lines of code that match other bots.

one is ???

maybe just two colors, top half is flag, bottom half is lines of code?

lines of code?

so its a gradient?

actually, that's not even possible...I could make it darker if the line isn't original

4:07 AM

if line 0 in a bot matches line 0 in my entry, that's 1/24 "vote" for my color for that bot's code

but I don't track the original owner in the code

What about Move

Move is identical across all bots

if nine bots have Move as line 7, then a bot with Move at line 7 gets a color that's a mix of all of those

it's not a GOOD idea, just an idea :)

just coloring by flag majority is probably the most straightforward option

@NathanMerrill when you're ready to publish your controller, let @PhiNotPi know, I bet he'd be happy to produce bots that break it :p

githubphagocyte

I like the multiple colours idea though

I actually want the single color

githubphagocyte

Fair enough

4:10 AM

it will make it easy to see which bots are taking over

anyways, I don't want to do a graphical display right now

easy enough for someone to graft that onto the controller later

githubphagocyte

That can be done by someone else - it doesn't affect the function of the controller and doesn't need to be in place before you run the first contest

There might even be more than one graphical display if several people have their own idea of what aspect they would like to be visualised

also, running 3 bots (50 copies each) for 50,000 turns takes just over 2 minutes

4:49 AM

does one of them come out a clear winner?

er, I was running it on terribly made bots

I just finished up writing some good bots

4 of them

one of them is a blocker

another always attacks

another copies his opponent

and the last one copies random parts of his code

sounds like a reasonable set of basic bots

I hate KOTHs that don't come with enough bots to run the controller :)

yeah :P

that's why I wrote a bunch of simple bots for pacman at the beginning

which I'm grateful for...and I've learned my lesson

also, putting my own bots has given me more rep than the question itself

I think so, at least

I'll occasionally randomly see +80

to find that people have upvoted all of my bots

oooh, there is a winner

RandomCopier had 91 points
Blocker had 46 points
Attacker had 36 points
Copycat had 26 points
There were 1 bots with equal flags
Execution took 174.868999958 seconds

fascinating

I guess that makes sense

neither the blocker nor the attacker move at all

Copycat has a move as his default action until he finds somebody to copy

also, I'm really happy that Blocker did significantly better than Attacker

4:58 AM

attacking without moving isn't really a viable strategy, I think

does copycat avoid copying flags? I don't know why copying an enemy would be helpful if you also get their flags

1 hour later…

6:05 AM

@NathanMerrill keep me in the loop if you're looking for testers for your controller. Or just let me know when the challenge goes live.

how many line in a row does a bot get to execute before the next bot is up?

1?

6:42 AM

I'm thinking they all execute at once

I guess there are minor differences between that model and the one-line-per-bot model, such as move and attack conflicts

I thought they executed sequentially

anyway, would it possibly be interesting to get to execute more than one line of code without being interrupted?

6:57 AM

would really change the dynamics of the competition

@MartinBüttner Apparently we could have done the first one in 72 hours with about $75 of Amazon EC2 fees...

Martin Büttner

@PeterTaylor well, it doesn't mean that much to me :D

7:15 AM

@PhiNotPi No, they rely quite heavily on underlying structure. A lot of the famous quantum algorithms rely on periodicity and do Fourier transforms.

@Sparr In a bad way?

5 hours later…

12:28 PM

@Sparr I think they execute sequentially.

12:39 PM

The definitely execute sequentially

what's a word for a number that you will add?

I have, say 5 numbers I'm going to add together

...what would I call them?

addendum is all I can think of

ah. addend.

1 hour later…

1:55 PM

I'm pretty sure that this guy can read people's minds. When I think, "Wow, he really hurried through that." and I am just about to hit the rewind button, he goes back over it.

I wish he taught everything, because then I would learn everything

githubphagocyte

@Rainbolt I have those open in another window from when you mentioned them the other day (yesterday? I don't have good time sense). I think I might watch them.

« first day (1307 days earlier) ← previous day next day → last day (3552 days later) »

Transcript for

Aug '1428

The Nineteenth Byte

The Nineteenth Byte: General discussion for codegolf.stackexc...

join this room
about this room

00:00

06:00

12:00

18:00

all times are UTC

site design / logo © 2024 Stack Exchange Inc; legal

mobile