The Nineteenth Byte

Depends on how simple the challenge is I suppose.

even with more complicated, I think I'd have less motivation to pour time and effort into a decent strategy if there are no bots to beat with it

Good point

in any case, KOTH's are still running okay

that's just something that doesn't translate to other challenge types, because on all others the measure of how good my answer is, is independent of all the other submissions... so even if no one else answers it I can see my result and think "dude, you did really well on this".

@overactor yes, let's hope it remains like that

I normally use more of a measure of "Does this sound like a good/creative/thoughtful strategy?" Even if it doesn't win, I like answers that show the user gave it more than a couple minutes of thought.

1:09 PM

Ok...so, I've been trying out my pacman king of the hill...and there isn't much interaction

@Geobits yes but it's a lot harder to tell in KotHs without opponents whether your creative strategy is actually any good

...hence I'm proposing that after pacman dies, he becomes a ghost

does that sound like a good idea?

@NathanMerrill the only possible interaction is denying someone else to pick things up, right? (while being unable to pick things up yourself)

I know, that's why I said looks good. Even without looking at the leaderboard, you can usually tell if a submission is going to be in the top or bottom half.

There are exceptions, of course.

well, if you pick up pellets where they wanted to go

then you get pellets, and they don't

1:11 PM

@NathanMerrill yeah true... the idea with the ghosts is pretty decent actually

then you could still do well if you die early, if you manage to kill the leading pacman quickly enough

Ok. I just need to provide an incentive that doesn't make everybody want to die as soon as possible

ghosts can't collect pellets

well, of course

I'm just debating between a fixed point amount

isn't that incentive enough? you can't even get any points once you're dead

no, you will

for getting other pacmans

I will give out points for getting other pacmans

1:17 PM

I'm so confused. I'm reading the spec, and it turns out I have no idea what happens when a pacman "dies".

just not sure how much

Geobits

Is it out now? A ghost?

I just planned on removing them

But yeah, I'm thinking to make them a ghost

Ok, so if a pac-ghost kills a pacman, give the ghost half his pellets.

@NathanMerrill I don't think that's even necessary.

1:18 PM

That would absolutely encourage a swift death, though.

I don't like that Geobits

stopping other players from getting more points is a sufficient incentive for a good strategy to hunt down pacmans once you're dead

Either that or make it an automated ghost.

initial ghosts are automated

By the end, the last few alive will have a ton of ghosts to deal with.

1:20 PM

@Geobits the idea was to increase interaction between bots

because there's little to no interaction between pacmans

Isn't competition for resources enough interaction?

@MartinBüttner True, but then it is no longer potentially a good strategy to die early

and try to kill pacmen

@Geobits maybe... but that just boils down to who is quicker

Otherwise, Hungry Hungry Hippos wouldn't even exist.

@NathanMerrill I thought that's not supposed to be a good strategy?

1:21 PM

It's supposed to not be overpowered

so not everybody tries it

for example, if I gave half the points

and stole half from the dying pacman

nearly everybody would try to die first

everyone dies eventually, so there's no need to incentivise an early death to make people explore that part of the game

@EoinCampbell I tried to make read and write as atomic as possible for my caveman submission, to avoid concurrency issues. It's mostly working, although my bot is a lot dumber now for other reasons related to new strategies.

@Sparr Thanks for pointing out the fault in my sandboxed post. That could have been embarrassing if it went live :)

@NathanMerrill in pacman the ghosts' strategies are known and fixed. You can interact with the ghosts to make them attack someone else, if you can track things well enough.

@Geobits np

That's tough though

because each of them have a random, but fixed number of turns between scatter and chase

and when they chase somebody, they find a target, and chase them for the entire duration of the chase

1:26 PM

Is there a reason we actually need more interaction? To me, it's interaction if my score will change by a significant factor with more/different entries. That seems applicable here.

Are you even told the personality of each ghost?

no Martin

@NathanMerrill ahh, yes, it will be hard to tell the difference in scatter and chase when you aren't their only chase target...

Geobits, right now, its simply a "how well can you avoid the ghosts

@Geobits the concern is that two reasonably good entries will score about the same, fluctuating only based on their random placement within the maze. The random factor will be bigger than the strategy factor.

1:27 PM

rather than a KoTH

there's interaction with ghosts, not with other players

also, this is my daily time to poke all of you into submitting for Dogfight. I need some competition over there.

I'm deferring that to weekend I think

@NathanMerrill I just like the idea of turning into a ghost when dying without being able to score points later on. It's simple, it adds interaction, and it can't be abused.

my new method for building circuits which I hate still doesn't work for 6 inputs

@VisualMelon are the others faster at least?

you'll hopefully get a controller by monday

the new method is faster for the problems that take a long time, and slower for the easy problems (but we are talking seconds not minutes), but the result isn't the most compact expression of the form I'm using

but it still runs out of memory after 10minutes for 6 inputs

1:31 PM

@VisualMelon I've loved seeing you fret over increasingly many inputs over the last few days

2

I remember when you were running out of memory (or time?) on 3 inputs

@Sparr I'm glad I'm amking someone ahppy ;P

@Sparr Isn't that just a perfect argument for multiple runs? If two entries are around the same quality level, I would expect them to score closely. Otherwise it's not a very good scoring method.

Originally it ran out of memory building the 2input XNOR xD

@Geobits a lot of runs. not just the 3-5 of some recent 1on1 KOTHs

then I reduced the memory consumption, and it took 4hours to build the 4-bit parity checker, the new method does it in about 5seconds, the old method now in about 14minutes

1:33 PM

officially, Dogfight runs 100 matches between each two planes. I'm running 10000 and still unhappy with the variance.

Right but this isn't 1v1 where you'd have to do n^2 to get all unique pairs. It's a single run for the whole group that you can run multiple times.

(the new method is really boring and I'll probably abandon it thusly, it just finds solutions for all 1-bit outputs, then ORs them to get the desired result - I could make it choose between the methods, thinking about it, that wouldn't be hard, and it would be done in such a way that it's just as fast for small inputs)

I'm going to go and exist in the real world for a bit, please don't create any 8-input tasks while I'm not here

I'll do that when you sort out the 6 bits ;)

1:49 PM

@Sparr yeah I'd rather come up with a graceful control program solution rather than mandating that players have to start worrying about file write & lock concurrency in their bots. they should just have to worry about the problem at hand

the idea of keeping a bot instance alive for the whole contest appeals to me, so we can just keep everything in memory

that precludes storing info between contests, but that's probably a good thing

@MartinBüttner in bracket numbers, does your solution consider the possibility of using a +1 bracket to accomplish parenthetical handling of operator precedence problems?

I think that would probably only be useful very very rarely, but it's a strategy that occurred to me.

@Sparr no it doesn't... that's what I meant by "probably not optimal any more"

I was considering to simply ditch addition altogether because it accounts by far for the largest part of the runtime... but even then I wouldn't get beyond the 5e5 example

I decided to go with low runtime for the big examples rather than optimalness

my solution runs in a few seconds if you accept a size about 10% bigger than what I submitted

I'm still contemplating how to build up the necessary data for breaking down the huge examples

I think I'll just accept that my solution won't be valid because it can't deal with really large numbers. I'd have to write a completely new algorithm for it anyway, so I'll just leave me answer as an optimality checker for the small numbers ^^

does your solution know about [xy] as x+y+1 instead of just xy for x+y?

I'd love to see a number breakdown challenge without the bracketing part. Just come up with the shortest algebraic representation of a given number, using parentheses and single-character operators.

possibly even RPN to avoid parentheses

1:57 PM

@Sparr I thought I'd seen something like that. Can't remember what the name was, let me try a search...

maybe with integers costing their number of digits, maybe costing their value

the bracket notation adds so many tricky little nuances to the problem

can't parenthesize an operation unless it ends with +n, and it costs you 2n characters to do so

I have an idea to modify my algorithm to be optimal under 65536 and still run in reasonable time for huge numbers

I need to change up my representation of already-calculated representations, though

@Sparr yes it does. but it won't remember it if it finds a shorter version for x+y+1

if it wasn't for the precedence problem it would be easy to just store the shortest representation of a given number

but I have to store multiple representations to account for limited operator choice when I have precedence concerns

@Sparr yes exactly, same here

and there's still the concern that in a few cases, breaking a number down would be better

2:08 PM

instead of?

26 as 2*13 is easy to find. 26 as 5^2+1 is much more complicated

3^^2+5^2+7 <-- there is a number for which this form is the ideal representation, and finding it will be non-trivial.

ah yeah. my solution does pick up on that, because I search bottom-up

my 26 is (6*2+1)*2

I need to extend my table of representations up to higher numbers, for values I have components for. I'll also add addition back into it.

I removed addition from my process entirely to speed it up, but that breaks some searches like 26

do you mean just increments or proper addition?

because proper addition is the absolute worst in this challenge :D

right now I'm not storing either. I just start stepping downwards by increments when I don't have a representation for a given number

storing proper addition is on my to-do list

2:36 PM

@Sparr jinx ;)

yeah

ninja'd you

five seconds? nice :p

:O what's a Unihedron?

is it like a Hondekahedron?

Eh, I mixed Greek and Latin roots. :)

2:38 PM

I see ^^

it's basically the unicorn of polyhedra

._. k

unihedron is a sphere? :)

@Sparr isn't that rather a polyhedron with an infinite number of sides?

I don't know, that sounds like an omnihedron.

2

But you wouldn't call a circle as unigon, ay :)

2:41 PM

on a related note, welcome to the nineteenth byte @Unihedron

we love having impossible geometry around in here

Thank you @MartinBüttner

3:08 PM

@MartinBüttner I'm still in debate about giving no points to ghosts, as your position (and the relative position of the ghosts) can make a big difference in how long you last

@NathanMerrill that's why you do multiple runs

I will be running the tests multiple times (10)

and that's why it's good to write a strategy that performs well in both situations

Why not make it not as random, then? Add pacmans around the perimeter (roughly evenly spaced), and ghosts toward the middle. There will still be some variation, but not quite as much.

That's not a bad idea

I actually like that alot

3:12 PM

Just make sure you mix up the order of placement for entries. You don't want the same pacman getting the same corner every time, etc.

Ok...another question...

When giving the wall configuration, would it be easier to have a single hex to convert, or 2 letters (NE) or (NX) or (XX) where X represents no wall

the max number of walls is 2

Personally, I'd either go with single hex as you are now, or variable strings: "" for no walls, "N" for north, "NE" for northeast. I don't see a reason to fix it to two characters. That's just me, though. Others may feel differently.

All in all, it's not hard to parse the hex :)

Also possible is a binary string "0100" assuming the directions are in a fixed order. For NESW, that would be an east wall only.

3:28 PM

@ProgramFOX thanks for the hint

ProgramFOX

@MartinBüttner You're welcome!

I can't do variable length

unless I want to do a separater

separator

Oh, right, it's for a laid out map. In that case, just do single character for sure.

@ProgramFOX I can't read GolfScript but our solutions are pretty much identical aren't they? ^^

ProgramFOX

Yes, indeed :)

This is the first time that I actually find it useful that data you stored in a variable is still on the stack (unless you pop it).

3:36 PM

are you guys discussing a pacman variation where players program the ghosts?

@Sparr last time I checked the idea was to become a ghost when you die

to introduce more interaction between bots

oh. that sounds cool. also very zombie-like

the idea is that you can't score any more but you can improve your position in the leaderboard by hunting down whoever has most pellets

@NathanMerrill requiring bit manipulation will exclude a small number of potential contestants, at the benefit of making most entries run a little faster

do ghosts know who has the most pellets?

@Sparr that is a very good question

3:39 PM

do they get any more info at all than a pacman gets? I think they should be able to see backwards, as a minimal advantage

the default ghost algorithms get a lot more info than that

but in any case you could just aid the auto-ghosts in killing all opponents as fast as possible, hence reducing their average score

back

I like the idea of seeing all directions

the actual ghost algorithms can see the whole maze, right?

their strategies sort of require it

@NathanMerrill I think it would be even better if bot ghosts got the same information as the default ghosts

maybe ghosts can see a 3x3 or 5x5 square around themselves, regardless of walls?

3:44 PM

Every ghost gets all contents from -5 (relative) to +5

something like that would be enough for the default ghosts to not cheat

@NathanMerrill so 11x11?

yep

is that enough for the default ghosts' algorithms?

yes

that is, could the default ghosts simply be entrants who start out dead?

3:45 PM

no, I've already programmed the default ghosts to match the original algorithms

but, except for Clyde, they all get a 11 by 11 square

Clyde gets a 17 by 17 square, and follows the furthest player

4:08 PM

@ProgramFOX did someone really just downvote your answer for being in golfscript?

ProgramFOX

@MartinBüttner Might be. I don't really care, if they really want to lose one rep for downvoting GolfScript answers, it's their choice.

...some people...

the triangles one?

that's an amazingly elegant golfscript solution

No, Slim Shady

I like the way this pacman challenge is shaping up

I could throw in a wild suggestion

make two koth challenges

one where you write a pacman

one where you write a ghost

if your ghost kills a pacman, it turns into one of your ghosts

4:20 PM

See now that would be an idea for a good team-challenge, assuming you could balance it right. Pacmen vs Ghosts.

Right up your sleeve @Geobits

@Geobits the asymmetry would make it even harder, I think

I'm starting over on Bracket Numbers

good luck :)

It would definitely be a challenge to balance it. You'd need some decidedly non-standard pacman rules, I think.

But in general, it would end up being a predator/prey challenge, and those balance fairly well in nature after a while..

4:27 PM

@Geobits it's fairly easy to come up with unstable models for predator-prey systems ;)

I'm going to keep my minimal representations in a heap, so that I can walk forwards through it while adding new representations for bigger numbers

of course you could just take that as a hint and design your challenge around a stable such model

@Sparr have you done the maths on this? I don't think you'll have enough memory to go to 2^31

that's why I basically gave up on my approach

I don't expect to

my previous entry builds its tables up to a defined limit

ah okay

operands up to 2^8 or 2^10 or even 2^12

my new plan is to build a small table, then use the results of that table to sparsely populate higher numbers

the order of building the table matters, too

I was previously building a 256x256 table, one row at a time

now I want to start in a corner and build outwards from there

1x1, 1x2, 2x1, 2x2, 1x3, 3x1, 2x3, 3x2, 3x3, etc

(won't actually to 1x, of course)

4:34 PM

@Geobits instead of [team-challenge], something like [co-op] (or similar) might work, too.

still pretty boring

I think before we graduate this site's name needs to change to PCCG (Programming Challenges & Code Golf) ... there are definitely more "challenges" than "puzzles" on here.

( @Doorknob, where do I take this proposal? ^ :D )

I'm still of the mind that code golf is a type of challenge, but I believe I've been outvoted on dropping it.

There's something on meta about changing the name, I think it's a bit old.

@Geobits Sure, but... what would that change? Are you suggesting to drop CG from the name altogether?

found it meta.codegolf.stackexchange.com/q/1147/8478

That was the basic premise. It's like saying "Sports and Football" IMO.

it's not that old

Or Board and Card Games And Magic: The Gathering.

Since they have a lot of M:TG questions, similar to how we have a lot of code golfs.

4:39 PM

hm yeah, fair enough

Code golf sort of is the hook though.

It wasn't for me. None of my first few answers were for golfs, and I still don't participate as often in them.

I think the killer argument for keeping it is that it's in the domain name

Yet that creates situations like this comment thread: codegolf.stackexchange.com/questions/22720/…

It isn't for me either to be perfectly honest

4:43 PM

@Geobits I just saw that. hilarious :D

Hah

I wonder if he realized

I got hooked because I was locked in a battle with Java over the ASCII Train ;)

and I've just spent the last 4 days looking at Dominoes, thanks Martin

@VisualMelon you're very welcome! :D

5:15 PM

I think I need to keep track of the minimum and maximum operation in each representation

for bracket numbers

unless the operation is, itself, bracketed

I think you only need to keep track of the outermost operation

and for ^ you can only further append ^ to the left not to the right

I think I'm thinking about tetration too much

your solution, hard coding the very very few useful instances of tetration or higher, might be better

yeah feel free to copy those

I am embarrassed at my supreme primes entry. I think I'm the only one not using a probabilistic is_prime()

actually, in my implementation, I can append ^ to the right, not the left

if I have a^b and b=c^d then a^c^d is valid, but if a=e^f then e^f^b is not

well okay, to me the first case is appending to the left because I slap an a^ onto c^d ;)

5:58 PM

What challenge are you guys on about btw?

Maybe someone better with game theory can help me: n players choose an integer between 0 and 1000000, inclusive. All players that do not have unique guesses are eliminated. The person with the median guess from those that remain wins that many points (if the median was 254758, you get 254758 points). Is there an optimal strategy that would spoil the game?

The game continues for x rounds, most points wins. Players receive a history of past medians.

I can't think of any Geobits

If two people employ the same optimal stategy, they both get eliminated

I was just gonna say that :D

Is that an indication there is no optimal strategy?

6:11 PM

Well there might be a strategy that's optimal on average

overactor, that's not necessarily true

Yea, that's the reason for that restriction/rule. I'm just trying to see if I'm missing something.

Q: Find the shortest bracket numbers

but there is one in RPS, too

10

Bracket numbers provide a simple way to express large integers using only left bracket, space, and right bracket ([ ]). A bracket number is defined as a string of one or more pairs of matching brackets [...] called chunks, each separated from its neighbors by zero or more spaces. The number of ...

I totally know what my submission will be

Geobits, post it, I have a great solution

that sounds like you're going to spoil it :P

6:12 PM

If I can be sure it's actually interesting, I will ^^

Yes. Yes it does.

@Geobits for a PPCG KotH you might want to reduce the range of numbers a bit though

The range was just an example, but I do want it to be large enough so that there aren't that many collisions.

Birthday paradox and all, even if uniformly distributed.

2

Birthday paradox +1

@Geobits what if an even number of unique numbers are left?

because its so true

6:15 PM

@overactor randomness?

I was trying to figure that part out.

or divide the points?

I was thinking divide the points, but I'm not sure how that would affect it.

or highest one wins?

out of the two middle ones

more consistent I think

Lowest would be better, since the payoff already drives the median up.

6:17 PM

agreed

how many times will you run it?

A bunch, don't have a specific number chosen. At least 1000 times, I imagine.

@Geobits wait, do duplicates eliminate you for the current round or the rest of the game?

Just that round

The rest of the game would be plain evil.

well unless you run multiple 1000-round trials like Rainbolt does for GvE

6:22 PM

That.... looked like a headache. I'll stick to a massive single run ^^

makes sense

Plus, you could collide by pure chance on the first round and get 0 points for the whole, which would really suck.

yeah it would

will people be provided with the entire history though?

bah, just post it, I've almost got my answer written up

FWIW if anyone wants to stick their oar in on this one. stackoverflow.com/questions/25086373/…

6:24 PM

@MartinBüttner That was the plan, but if you have a better idea?

@EoinCampbell Sorry, I'm not quite rabidly anti-.Net, but it's close.

:)

@Geobits no that's how I would do it I think. but I'd say wait a bit with posting that. I really like the idea, but at the moment it is "yet another pattern-matching KotH"

bill gates ftw!

@MartinBüttner Probably a good idea. Once it drops off a bit, maybe.

-.-

I totally have a fantastic idea for it though :P

6:27 PM

I like Bill Gates, or at least I don't dislike him. I just don't like .Net.

6:38 PM

but but but

.NET is fabulous

:(

@Geobits drugs and alcohol <-- not all redundant classifications are meaningless in context

@Geobits more collisions in your guessing game isn't necessarily a bad thing. It's a probabilistic game, either way.

Geobits...on your previous problem...are you going to allow me to submit a program that takes the last mean and adds 1?

and then allow another to take the last mean and add 2?

@NathanMerrill sounds like a good way to get eliminated :p

@Sparr Agreed, but I don't think it adds anything in this case.

@NathanMerrill Sure, just hope nobody else does.

well, they can't

6:43 PM

Call it The Price Is Right.

because they have to be unique

so, either they randomly land on +2

or mine is the only program doing +2

or their strategy is +2

guesses near the previous round's median might be popular

guesses near the previous round's median if you ignore bots eliminated after the previous round might also be popular

basically, if people are doing calculations without randomness the same person will win each round

no

...why not?

6:44 PM

err, define "round"?

everybody submitting a number

not a game, a round

Only if nobody takes history into account.

If there was no history you might as well just do one round and ban random.

hmmm

I was thinking about only taking the last round into account

oh, no, you'd definitely learn from history

try to find patterns in the enemy moves

...geobits, do the entries maintain their order?

6:47 PM

Note that the only history you get is all past medians (in order). You don't see what each bot entered.

I think the problem is that one entry's score will be heavily dependent on the environment (other entries)

At least that's my idea at this point.

the first place entry could become the last place entry when one new bot is added

that's not a good thing, in terms of contest design

Ok...then my previous statement is still quite true...

if everybody simply does calculations then a small set of people will get all the points

if I enter a copy of your bot, you lose a LOT of standing

6:49 PM

I imagine copies aren't allowed :P

sure, but vaguely close strategies will emerge

Your goal is to try and find a median that won't be picked by others. So actually entering a copy would be dumb anyway.

we have the linear progression bot, the quadratic progression bot, the exponential bot...which will all produce similarly ordered results

even if you start including the MeanMean bot

@EoinCampbell could it be that CompleteMatch() isn't being called?

I assume it's done in Play Match, but the try would quite any exception and not call it

leaving the players in the active dictionary

in most contests, if you have a strategy very similar to the first place bot, you'll get second place, and the first place bot won't drop much if at all

in this contest, as strategies converge, both entries suffer

6:52 PM

I expect the median to slowly converge. And when it does, many could be eliminated because they're looking for something close to the median.

Right. The point is to try to converge to get it right, yet not converge to get points.

sure, but the convergence is one-way

the earlier submission isn't part of the convergence

Are you going to allow multiple entries per player?

it's being converged TO

@NathanMerrill I doubt it.

if so, I'm submitting 100K bots

one for each number

6:56 PM

@Geobits what happens if the closest to the mean is not unique?

err, median

the median is calculated after duplicates are removed, right?

I'm not sure what you mean. All non-unique entries are removed. After that it's not closest to the median, it's the median, or the lower of the two if an even number remain.