The Nineteenth Byte

12:28 AM

0

Introduction What you have to do is, given an an ASCII diagram of a chemical, output the chemical formula. Rules Your code must not access the internet and may not use a stored library of molecules. You may have a library of elements. You must verify all of the elements included in the formul...

Sp3000

7:20 AM

Man, I can't view the CJam cheat sheet :( Damnit Great Firewall of China.

Phase

9:18 AM

Any ideas for æ?

Sp3000

What's this for? Something for the command to do in your language, or...?

Phase

@Sp3000 New command

going to use √ to sqrt the top of the stack

I wonder why people don't use languages like ><> and BF more.

Sp3000

I use ><> ... D:

Phase

:D

Sp3000

BF's been used recently too

Phase

9:25 AM

but it's mostly CJam & GolfScript

Sp3000

It depends on the question - some questions really aren't suited for ><>/BF, that's why

Also more Pyth than Golfscript, surely :P

Phase

but what do those languages have that ><> doesn't?

Sp3000

For starters, a concept of strings

Phase

strings in ><> are awesome! "hello world" that's it! :D

Sp3000

Try pushing "hello", then "world", then swapping the two in the stack so that you get [w o r l d h e l l o]

Now replace those two strings by any arbitrary two

Phase

9:29 AM

ah

Sp3000

Should have probably said string manipulation, specifically

Phase

I don't know how I could fix that...

Sp3000

Hm... I guess it might be easier if you used p and g and wrote into the codebox... but nowhere near as simple as \ in CJam, say

Phase

Σ pushes the sum of everything on the stack, should it remove everything and then push the sum, or just push the sum?

Sp3000

Usually replace the elements with the sum

If you need to keep the elements, you can just duplicate

Phase

9:36 AM

but then if I duplicate it and add them all, it'll just be put in the sum

Sp3000

Oh... right. ><> ...

Have you considered whether or not you want arrays?

Phase

I've got multiple stacks, which can kind of be arrays

12345 3[r 2[r] ]rnnnnn;
prints 12534

aditsu

@Sp3000 oh, are you in China? your profile says Australia

Sp3000

Er... if you mean multiple stacks like ><> multiple stacks... that's not quite what I mean because you can only access the top stack in ><>

Currently in China visiting people, but yes I normally live in Australia

Basically I just went from freezing cold to boiling hot over a plane trip

aditsu

oh, haha, anyway, use a vpn, or let me know if you'd like me to email it to you

and if you pass through HK, we should meet :)

Sp3000

9:43 AM

I sure wish I could - it's usually my arcade gaming stop. Not this year though :( (also Namco Wonderland got moved from Causeway bay :( )

aditsu

arcade gaming? o_O never heard of this reason for visiting HK

Sp3000

Well I'd like to arcade in Japan, but I usually don't have a good excuse to go there. HK's got Japanese rhythm arcade machines though (China has some, but they're the Asia versions, i.e. outdated and not as awesome)

(also will try VPN, thanks)

Phase

@aditsu what are Op1, Op2, and Op3?

aditsu

I guess I don't know anything about arcade gaming :p

@Phase in the source code? base classes for operators with arity 1, 2, 3

Phase

@aditsu but why have 3 classes for them? you could have one class and have them pop the needed values in the calc function

aditsu

9:51 AM

that's what I had initially, but then I had this popping code duplicated everywhere

also, I want to know the arity of each operator, for f and : and .

Sp3000

(this is one nice cheat sheet)

Phase

what trigonometry is in cjam?

Sp3000

sin/cos/tan/arcsin/arccos/arctan/hypot

aditsu

look at math in sourceforge.net/p/cjam/wiki/Operators

Phase

now I know what to use for homework ;)

aditsu

9:54 AM

there's also atan2

Sp3000

Are there any planned features which can't actually be done by CJam at all currently? e.g. time.sleep()

aditsu

you can actually do sleep in cjam, but not efficiently :p

Sp3000

Oh right, you've got timestamp. But that's in seconds, right?

aditsu

milliseconds

this sleeps for 5 seconds: 5e3es+{_es>}g;

Sp3000

Ah, then I guess you can :P

Phase

10:01 AM

@aditsu have you used Heroku with Java?

aditsu

anyway, I listed a few planned features at sourceforge.net/p/cjam/wiki/Planned%20features

@Phase never used heroku

Sp3000

Hmm interesting list of features there :)

aditsu

I have a lot more in a file

and I will implement some of the things from tickets

(sourceforge's name for issues)

Phase

(#GitHubIssues)

Sp3000

11:21 AM

@aditsu d[32:32]=d.pop(y),

It's kinda depressing that insert is so long that d[32:32]= is shorter

Actually... d[:32]+=d.pop(y), is even better. I didn't know that even worked D:

aditsu

hmm?

Sp3000

For your ASCII front answer

aditsu

I know, but I'm confused by the d[:32] thing

I get TypeError: 'int' object is not iterable

ah, I need [d.pop(y)]

Sp3000

You need the comma at the end

aditsu

oooh!

Sp3000

11:35 AM

(tuple is one byte shorter than list)

aditsu

thanks :)

we should probably add that insert tip to codegolf.stackexchange.com/q/54/7416

Sp3000

Doing :) I'm trying to compile a list of functions which are rarely needed

aditsu

12:12 PM

you added so many, does it still count as "one tip per answer"? :p

Sp3000

... what's a tip? :D

aditsu

a piece of advice or expert or authoritative information :D

Sp3000

Well that's my piece of advice - with subheadings :P

(it's a list I've been meaning to make, actually - a lot of it's pretty trivial it wouldn't be right putting them in separate tips I don't think...)

Hm... actually...

Yeah, I think I'll split it up

@aditsu Done. Better? :P

aditsu

12:33 PM

I guess so :) it seems that you removed some

Sp3000

The not-as-important ones, yeah

I don't think I've ever seen anyone accidentally use divmod or int.bit_length accidentally in a golf, unlike the rest

aditsu

right

Sp3000

Pretty impressed by your algorithm though, just saying :)

aditsu

thanks :)

Sp3000

1:24 PM

@trichoplax "no one is anywhere near an optimal solution" - what's the optimal? :D

trichoplax

Who knows - but I'm confident it's higher than 137 ;)

I didn't make the mistake of posting a question I know the optimal solution to this time, so I'm expecting it to stay open ended indefinitely

Sp3000

I've been trying a bunch of things, and from what I've seen so far around 140 seems about as good as I can go

Either that or I'm doing things very wrong :P

trichoplax

I doubt the optimal solution is near the upper limit of 487, but I'm confident that an optimal solution would take a long time to find with any algorithm, hence my guess that no optimal solution is near this early in the competition

@Sp3000 You've beaten 137 and not posted...?

Are you saving up higher solutions to use against any new answers...? :P

Sp3000

Nope not yet, but I've squeezed 141 in with only (!) 266 conflicts

(compared to ~1.4k which results from random)

trichoplax

Ah, only 266 conflicts too many...

Sp3000

1:28 PM

Yeah - this algorithm looks promising, but it needs optimisations so that I can run more tests

trichoplax

Looking at your algorithm in the answer, I was wondering how many tied first places you get when choosing the next pixel. If there are only a small number, could you branch and try all of them?

Sp3000

I tried branching but the algorithm's pretty memory intensive, so I never managed to get the branching version running for more than 10 minutes or so

trichoplax

Ah OK. I guess you'd have to save branches not taken to disk and retry them at the end. Not a fast approach...

I don't require deterministic algorithms, so you could choose randomly and see how that goes

Sp3000

The determinism's more for my sake so that I know that my changes don't break things

But trying a bunch of runs gives a lot of 133-135, and the occasional 136. I guess I got lucky with the 137

trichoplax

How do you get different results if it's deterministic? Are those for different starting pixels?

Sp3000

1:33 PM

Yeah, starting pixels

trichoplax

Do you use just one starting pixel each time?

Sp3000

I've also tried alternating the sorting so it reverses direction after each pixel is placed (like the Prolog answer) but that didn't do much

trichoplax

Could you take that pixel as an input and then cycle through them?

Sp3000

I used a few - the 137 was found by me trying to iterate through all possible single starting pixels (which is why I found it at 10)

I think I'm leaking memory though, because it died after 12

trichoplax

You'd have to cover a whole octant to be sure, but if you guess you might still see an improvement

Sp3000

1:35 PM

I thought I'd try other approaches instead though :P

trichoplax

Maybe you could just iterate over starting pixels that haven't shown up in any of the finished results

I'm keen to hear about other approaches - even if they aren't the best results it's interesting to see - and one of them might inspire a good approach later

Sp3000

Hm... it doesn't quite work like that though. e.g. if you take a bunch of pixels in one result, and use that as the start ... you won't necessarily get the same result back

My current one is genetic algorithms with mutation replaced by a local search - still fine tuning it though

trichoplax

Local search being moving an existing pixel a bit?

Sp3000

Replacing an existing pixel with the pixel from a random set which gives the best result

trichoplax

Ah - local in the search space but not necessarily local in the image

Interesting

Sp3000

1:38 PM

Yeah - local in the image might not work too well I thought

Scoring is number of conflicts, and 0 conflicts is hard so I need to get rid of those... which is a vertex cover problem (fun!)

trichoplax

At least my fear of an instant optimal solution didn't materialise. Even if an optimal solution arrives now I'll feel that the difficulty was sufficient

Sp3000

I'd like to see that proof of optimality :P

trichoplax

For the first couple of days I was dreading someone turning up with a one line answer that's provably optimal. "All you need to do is project the image into 17 dimensions and the optimal solution is then a straight line - see my 12 byte program"

Sp3000

:P

trichoplax

It's surprisingly easy to think up problems which are difficult for myself. It's surprisingly difficult to think up problems which are not easy for others.

Sp3000

1:44 PM

Well... there's a lot more "others" than there are "you" :)

trichoplax

Hopefully I've stumbled on one here...

@Sp3000 Indeed. It's a nice way for the world to be :)

Sp3000

Hmm I think I need more optimal answers for small cases to compare to :/ I don't even know what's the best for N = 31

trichoplax

I think the very early optimal answers might be misleading. There's a pattern in the growth of possibilities that breaks around N=10

Sp3000

I sure hope it is - 30 seems outright impossible to me currently :P

trichoplax

The growth of the number of possible lengths seems to grow according to the same pattern as the number of required lengths, just one step behind, but then they diverge around 10 or 11

They stay close for a while so it might look like the pattern is still similar but they are no longer in step

I don't know what effect this has on the optimal solution sizes though

My vague guess is that for higher N, the optimal solution becomes further from the upper limit Dennis provided

Sp3000

1:51 PM

That's what I'd expect... also I'm having trouble getting 10 for 11

trichoplax

I considered offering a bounty to the first answer to also include a proof of a lower upper limit than Dennis's

Even if it's just an upper limit for N=619 rather than a general upper limit

Sp3000

You'd have to make sure it's not (Dennis's - 1) though :P

trichoplax

@Sp3000 I don't know - is that easily provable? I'm convinced it's true but I can't think of a proof...

Sp3000

Well, you'd need to assume N > 5 or something, so it might be a little more complex than I'm making it out to be

trichoplax

I wouldn't be surprised by the result, but I'd be happy to pay a bounty for the proof

Sp3000

1:57 PM

:P k - are non-code answers okay though?

(I'd be interested in the bound, but just wondering)

trichoplax

I'd only offer the bounty to a valid answer that happens to include a proof of an upper limit - it would still need to be competing in the competition and provide a concrete set of points (far below the limit)

Sp3000

Ahaha right

trichoplax

I've learned from experience to word bounties very carefully...

I'd probably run the final wording past chat before committing to it

If I'm going to advertise such a potential future bounty I suppose it makes most sense to edit it into the question now, while there's an existing bounty to draw attention to it

Sp3000

Yeah, that'll be good

trichoplax

Something like "I will award a bounty of 300 to the first valid answer that includes a proof of an upper limit for N=619 lower than Dennis's upper limit of 487"

But I'll want it watertight before I edit it in

Sp3000

2:03 PM

Maybe "lowest bound after some period of time" is better than first?

trichoplax

That would be less annoying for someone who finds a better limit shortly after

Sp3000

Less of a race, yeah

trichoplax

"A valid answer that also happens to include a proof of an upper limit for the specific case of N=619 will be eligible for a side-competition. At the end of October I will award a bounty of 300 to the valid answer that includes the lowest proven upper limit less than 487 (provided that answer also includes a valid solution that need not be equal to the upper limit)."

I think I need to golf that down

Sp3000

You can skip the first sentence I think

trichoplax

"Any bounties that happen to be awarded by others to my example solution will increase the bounty on offer accordingly."

"At the end of October I will award a bounty of 300 to the valid answer that includes the lowest proven upper limit less than 487 for N=619 (provided that answer also includes a valid solution that need not be equal to the upper limit)."

"I will match any bounties that happen to be awarded by others to my example solution, and increase the bounty on offer by double these amounts"

Sp3000

2:11 PM

(up to a limit of 500)

trichoplax

Hmm, allowing people to increase the bounty will be a problem if there turns out to be no lower upper limit. Maybe not a good idea

I'd be stuck with excess rep and trying to reassign it to the senders

PhiNotPi

2:26 PM

It would be hilarious if the whole page got filled with bounties by people shuffling rep back and forth.

trichoplax

Hmmm. I'm still considering it though... :)

Sp3000

4:05 PM

@trichoplax Confirmed optimal 1,2,3,4,5,6,7 for N = 1 ... 7. That was exciting.

trichoplax

So the optimal solution is N pixels for an NxN image up to N=7?

Sp3000

I take back the N > 5 thing

Yeah

1: 1 (0)
2: 2 (0 1)
3: 3 (0 1 5)
4: 4 (0 1 6 12)
5: 5 (0 1 4 11 23)
6: 6 (0 1 9 23 32 35)
7: 7 (0 2 9 20 21 40 48)

8 just terminated - it's 7

trichoplax

4:20 PM

I wonder if it's possible to see an intuitive reason for the pattern breaking after 7

Sp3000

Somehow I doubt it

trichoplax

Every solution has a pair of adjacent solutions but for N=7 they are not in a corner

Sp3000

Those are the first lexicographical solutions - there might be one where it's in the corner for all we know

trichoplax

I suppose I shouldn't try to generalise from examples - yes that's a good point

Sp3000

... oh actually no there wouldn't be cos I checked them

nvm

randomra

4:24 PM

I'm thinking about this problem too, but have no reasonable useful comment yet.

trichoplax

I guess that's relevant since a lot of solutions for N=619 start with adjacent pixels in the corner - maybe that's never optimal above N=6

@randomra I have all questions and no answers myself :)

Sp3000

Recursive backtracker managed up to 130 before it chokes :(

randomra

what might be feasible is to show that finding the optimal solution for a given N is NP-hard (or whatever the correct term is)

what is the non-decision problem equivalent of NP-hard?

PhiNotPi

I think this may be related to the graph coloring problem.

(This is still the unique distance pixels problem, right?)

randomra

yep

trichoplax

4:31 PM

@randomra I suspect it is but I have no clue towards a proof. It is undecided for the 1d case (Golomb ruler)

PhiNotPi

My line of thinking is that "coloring" a pair of points excludes all other pairs of points the same length, similar to how coloring one node of a graph excludes all adjacent nodes from being the same color.

It might be better to relate it to the graph matching problem: en.wikipedia.org/wiki/Matching_(graph_theory)

There's probably some way to convert this problem into a graph problem, but unfortunately the size of the graph will be quite large.

Sp3000

Just to double check: Does it make sense that, if a solution exists, a solution exists where the first lexicographical pixel is in the first half the top row?

trichoplax

Quite large is a very understated way of putting it :)

Sp3000

Because you can translate/reflect/rotate and all

trichoplax

@Sp3000 The only way it wouldn't is if the solution had no border pixels at all

Actually in that case you could translate it to the edge

So yes, you are right

Assuming you include the central pixel in the first half for odd N

Sp3000

4:41 PM

Awesome, posting the backtracker then for reference

trichoplax

Great :)

Sp3000

(it's still on 130 :( )

PhiNotPi

I think there's definitely a pixel in the first half of the top row, and always one in the first column (because translations).

trichoplax

Yes that sounds right

@Sp3000 Interesting - for N=8 there exists a solution with adjacent pixels in the corner again

Sp3000

I don't get the first column part - why can't the top left pixels be (0, 0) and (1, 1)?

trichoplax

4:45 PM

(0, 0) is in the first column :)

Sp3000

... shhhh

trichoplax

lol

As long as those two things can apply to the same pixel it's true - problems otherwise, yes

Sp3000

If there's one thing I've learnt from this challenge, it's that switching from tuples to ints made my first code run 40% faster D:

I didn't expect such a large difference from changing how I represented the coords

trichoplax

Wow

Sp3000

Must be all the set comparisons

trichoplax

4:51 PM

I wonder if that is a PyPy difference or if cpython also has a 40% difference between the two

Sp3000

Hmm not sure

Also, you're putting my name up for every answer I post? :P

trichoplax

Would you just list the highest answer by each person?

Sp3000

If you're using it solely as a leaderboard, then probably. Otherwise, it might be good to add a note summarising the different strategies

(so people don't get confused why there's more than one of a person)

trichoplax

I did wonder about naming them, but I hadn't thought of just including the highest - that sounds easier

I like the idea of describing them if I can think of meaningful labels - I like the fact that answers have taken varied approaches

I'll see if I can summarise them in a couple of words each

Sp3000

btw also attempted: Filling from centre out and filling from border in (another variation of your algorithm). Both terrible - I was hoping having more pixels at the edges would do something but nope.

trichoplax

4:59 PM

It's interesting that good solutions have more pixels near the border, but choosing near the border doesn't necessarily help

How do these descriptions sound? Are they meaningful/accurate enough to include in the question?

Sp3000

Hmm probably not

2/3 words probably too little now that I think a bit

trichoplax

5:16 PM

I could drop the font size for the top one and give them all more words, but I think it still might be unrealistic

And combined approaches in future will break it again, so I'll just list the top answer by each user with no description

New Main Posts

1

Q: Print the British Flag!

Inspired by Print the American Flag! this is a direct copy but with the British flag as it has some symmetries but is still quite complex! Your challenge is to produce the following ASCII-Art in as few bytes as possible! Turn your head/screen (not both!) by 90 degrees to view it properly. ____...

code-golf ascii-art kolmogorov-complexity

aditsu

6:07 PM

Sp3000 will fatalize trichoplax!

PhiNotPi

6:19 PM

trichoplax is kill

trichoplax

lol

New Main Posts

6:43 PM

0

Q: Print out the Smallest Perfect Squared Squares

Squaring the Square is a process of tiling a square using only other squares. If this tiling only uses squares of different sizes, then it is considered to be perfect. The smallest possible perfect squared squares is a 112x112 square tiled using 21 different squares. I have created the ascii a...

code-golf kolmogorov-complexity

aditsu

hmm, I can get 132 easily, but then it gets stuck

what! 133, after a long time

trichoplax

@aditsu For uniquely separated pixels?

aditsu

yeah

@trichoplax btw, why 619?

trichoplax

Do you have a new approach? I'm interested to see new approaches even if they haven't found a winning solution yet

@aditsu lol everyone keeps asking that - maybe I should edit the answer into the question...

aditsu

no idea if it's new, I don't know what others did :p

trichoplax

6:59 PM

I decided (arbitrarily) to go with a prime, and that's the largest prime that can be displayed as a p by p image without SE shrinking it

aditsu

ah, cool

trichoplax

I went with the largest to give slim chance of an optimal solution ever being found, so the question will remain open to new contenders

I've edited the explanation in - although this way I won't get to hear people's theories on why it was 619...

@Sp3000 That hints that primes greater than 6 have no optimal solution with adjacent pixels in the corner. 619 is a prime greater than 6...

aditsu

7:31 PM

I was trying to profile my code, but it says that one whole method is taking the most time, "self time", no other details ><

trichoplax

Weird

Is that the name of a method you have?

Or is it a method of the profiler?

aditsu

it's a description given by the profiler of what's taking the most time - the self time of the method, i.e. code inside the method

maybe I just need a different approach

trichoplax

Is your approach in a single method? Does it just need to be split into separate methods to allow the profiler to distinguish between them? Or does the profiler have a setting to time individual operations/lines/statements?

aditsu

7:46 PM

no, maybe, no

trichoplax

There's an interesting array of approaches in the existing answers, if that helps

aditsu

another option is to translate the thing to C++ :p

trichoplax

Are you currently working in CJam...?

aditsu

haha, no, java

trichoplax

I had to ask - last question I posted the optimal answer was a one liner in CJam...

It's interesting to see a question where the answers are various degrees of brute force but python is winning

aditsu

8:20 PM

yay, segfault with no stack trace... the joys of C++ :)

uh, it crashes before the first line in main, must be a new record

trichoplax

lol

Good luck with that...

At least when you find out what was wrong you'll be able to profile it properly

aditsu

I'm not hoping to profile it, just to make it run faster :p

first I need to make it run

I think it was trying to allocate too much stuff on the stack

let's switch to pointers...

ok, it's working now :)

but doesn't seem faster than java

oh, 134!

aditsu

9:02 PM

I'll let it run overnight :p

trichoplax

9:38 PM

Nice

I think most approaches will see the numbers slow down as they increase so don't get your hopes up too much...

New Main Posts

9:51 PM

0

Q: Algorithm to find the cordinates of nodes of a family tree

I'm looking for an algorithm to draw a family tree from JSON data like below. The tree should look like as I have given below with nodes arranged nicely. To generate the nodes, I need a computer algorithm that generate the coordinates. Please note that I'm not looking for the HTML or JavaScript...

algorithm-advice

Transcript for