159 Hard Life problems

Hi Folks,

Finished most of the tasks, but Hard Life has me at my wits end for the last 6 months at least. I get a solution in about half a second and my program agrees with the example and with the other single patterns supplied. I have even hand traced the code for hours and hours with pencil and paper. But every time I try to submit a solution I get Number of generations is incorrect.

I have reversed the values, left spaces at the start at the end, written it in hex and octal, tried all values +- 5 all to no avail.

Either I am missing something really obvious or I should go back to playing with toy bricks.

A mere crumb of a suggestion would be most greatfully taken as help.

Many thanks in anticipation

Hi Phil, I'll have a look at your code. First thought, wow 357 lines of C! Mine is 67 lines of C++.

To Grae: good point! seemingly in C it requires writing from scratch any data management (I believe hashes in this case). When I tried to implement this about 20 years ago, also in C, I remember writing lists and qsort from scratch and debugging all this for two nights. Somehow I feel nostalgic for those days :)

To Phil: it's really curious as the problem, I believe, is not the hardest! I'll try running your code on my machine and share results if any. Just give me some time please! :)

I used -13 40 to run my code. It took about 15 seconds.
I then tried your code, which finished instantly and gave the answer 251 33.
My answer is more than an order of magnitude higher for both numbers.
In your output you have 71 105 followed by 72 106. My code gives 72 104, so that's where it starts to diverge.
I've seen Rodion's comment. My output starts with 0 13, 1 15, 2 16, the same as yours.

Well, I'm sorry but it seems there is some mistakes in rules implementation.

It's great you made dump of population size at every step. I see that on the first step you count 15 (not depending on input as glider is yet too far).

But it seems not correct. Glider on the 1st step is 5 cells anyway while acorn converts like this:

- X - - - - -
* * * X * * -
X X - - X X X
- - - - - * -

stars denote new organisms. Now hashes denote dying ones:

- # - - - - -
* * - # * * -
# # - - X X #
- - - - - * -

let's remove hashes and replace stars:

- - - - - - -
X X X - X X -
- - - - X X -
- - - - - X -

You see, just 8 cells. So total after 1st generation is 13 for almost every input, not 15. Probably you can check the cause faster than I :)

P.S. besides pencil and paper we can use some ready implementations found by google, i.e. this one.

Thank you all. Much more than a crumb I've got the whole loaf :-)

Many thanks

stranger and stranger.... rewrote the program in python and got the same answers, exactly, iteration by iteration so nothing to do with the data structures.

I checked the patterns - seem ok ( the 15 mentioned above was the second generation not the first).

checked with acorn alone and then r-pentamino. Both give the correct values. -- I have uploaded the python version I wrote this morning.

Just wondering what language to write it in next. (no, I do know that if I repeat the algorithm I will just get the same result) ... perhaps assembler. :-)

I could have used the STL with C++, but I do enjoy creating novel data structures. This one had hashed cells held on separate linked lists, with linked lists threaded through so I could throw complete chains about and double buffer.

This has become a very interesting puzzle to solve; even more interesting than the original.

I picked up this site when my wife was doing chemo (better now!) and it has sustained me, keeping me busy through some difficult times... this and some time spent on project Euler and learning some preludes and some inventions on the keyboard really have enriched the last couple of years.... so thank you

Anyway, I will keep you posted. And while I'm here... 191 cycles to solve micro-life(213) I think not :-)

Ah, sorry for confusion about 13 / 15 then. But I see Quandray offers exact place to look into:

In your output you have 71 105 followed by 72 106. My code gives 72 104, so that's where it starts to diverge.

I set this configuration in the online app mentioned above and here is the 72-nd position:

You can print out the position from your code and compare, I believe. This app shows coordinates of cells, size of population and generation counter so you'll easily find where and how situation diverges...

I picked up this site when my wife was doing chemo (better now!)

Oh, this sounds, well, alarming :( I really wish things will improve!

By coincidence - though it's not comparable, of course - I made first version of this web-site in September of 2013 during somewhat complicated time for my family - my mother-in-law got her knee broken (which would be easier for person younger than 70) and we were travelling everyday between jobs, our and her appartments and various hospitals to take care of dog, cats and herself, so for some weeks I've seen my wife just when we met in subway, rushing in opposite directions. When she had it broken again just few days after leaving hospital we felt a kind of despair (though things improved towards January).

My two penneth; check that your position 71 is right, before you look at position 72.
I changed my code from using set to unordered_set and the time dropped from 15 to 5 seconds.
You may like to try Advent of Code

A bit late to the party, but I recently solved this one and initially fell into the same trap that gives the "Number of generations is incorrect" error.
It was a stupid mistake of reversing my X and Y coordinates, and Golly helped me realise that even from step 0, when I initialized living cell coordinates.
In essence I was drawing the acorn vertically and inverted, the glider also, but in a way that it still glides southeast. So, actually generation 73 is the point where the glider collides with that vertically inverted acorn spawn and things start to diverge, but again you do not need to get to that step to find out.
To demonstrate, I was actually starting with this
--X
X-X
---
-X-
--X
--X
--X

and this
--X
X-X
-XX
Oh well...

Btw, in Markdown instructions page, the markable.in/editor link seems dead. We should perhaps point somewhere else these days

Kostis, Hi!

Glad to see you - and initially thought you solved it in Mathematica - but then found you have switched to Haskell (which is equally astonishing for me - though I once wrote test project in it, trying for position in BioCad).

As about the problem - perhaps checker messages could be improved somehow to hint about such situation, but I can't immediately see how...

markable.in/editor link seems dead. We should perhaps point somewhere else these days

Oh... I even can't remember it and seemingly people haven't used it anyway... Probably we'd better try to add some formatting helper buttons around the text input area...

Probably we'd better try to add some formatting helper buttons around the text input area

Probably the best approach, even if only for the most basic functionality, like code blocks.

but then found you have switched to Haskell

It's not like I've switched to Haskell exclusively, but I am learning the language and I did need the exercise. Besides, you didn't exactly made it easy for me, given the 1 minute time restriction of this particular problem, and it's not like I intend to buy an x86 Mathematica license for hobbyist use. I am masochistic enough however to give it a try on Mathematica on the Raspberry Pi, hopefully soon.

which is equally astonishing for me

Why though? As you pointed out, people use it professionally these days, if a lot less than others. I gather you 're not very fond of it, but as I get to know more it makes sense.

It's an interesting question - what's wrong with Haskell :)

The said BioCad is doing good things (which is comparatively rare among Russian companies). However they decided to use Haskell for various backend services. As the language is not quite popular, there are two immediate consequences:

• great trouble in finding developers who knows Haskell or even wills to use it :)
• there is not sufficient tools and libraries for Haskell, as the community is small

E.g. when I applied to their position and got test-project - I found, for example, that the driver to database they use has been written by their lead developer. Nothing bad except that biotech company probably shouldn't spent time (especially of Tech-Lead) on writing database drivers.

Additionally as I struggled through the project I become gradually angry with language. It's type strictness is absolute, you know - so sometimes you feel you are not really writing implementation but just kicking around to overcome restrictions. At the same time it is wonderful to see how haskell designers hit their restrictions themselves and produced queer features (look at inter-handling strings of different types).

Of course any proponent of Haskell would say I'm all around wrong :) but as Jesus said "judge by their deeds": I first heard of the language probably 20 years ago - it was expected affectionately to superceed all other languages very soon. However, years passed - and as it is said sarcastically "Haskell is not dead - it just never was quite alive". Look at the long expected 2020 standard - it is yet expected :)

Additional trouble is that Haskell has rather steep learning curve. E.g. I once worked in the Erlang project - being hired here with zero knowledge (except test-project also) - and felt myself pretty comfortable in a few weeks. Note, it is also functional language - no varibales, no any kind of loops (but with messages which Haskell lacks). With Haskell, on contrary, spending a week on a test project I didn't feel much comfort (despite I wrote the requested service and it worked well).

All valid points I guess. It's always interesting to see things from a professional's perspective, and the way you describe it is like a chicken-and-egg problem, in that the language doesn't have much support because not many people use it, and people don't much use it because it doesn't have much support.

The way I see it (and even its creators describe it, see https://www.youtube.com/watch?v=iSmkqocn0oQ) is that Haskell, being a committee designed language, and not a company created and supported language for industrial use, like Go, or Rust, is more of a principles-first theoretical playground for (functional) language development, with the occasional professional use, a testbed for ideas that other languages (less strict or pure on the functional front) can benefit from (heck, even Java poses as a functional language these days). Hardly anyone could think that such a language could take over the world, except, yes, if you are a fanboy.

You can of course imagine that I came to Haskell from a completely different route. Mathematica is multi-paradigm (or so the manual says...) but I found I quite liked the functional way. So I thought, given that I wanted to learn another, more versatile language, why not explore the far end of that spectrum so that I can later appreciate whatever middle ground there is. Haskell seemed like the reasonable choice and so far I quite like it. Yes, it has a steep learning curve (that's fine by me), and yes I have stumbled upon some of the self-imposed restrictions you describe, though I have mostly attributed whatever shortcomings to my own inexperience. That said, though difficult around certain concepts that you need to grasp, Haskell has made sense all the way so far -admittedly not very far yet- and it has given me the ability to make command line programs for the occasional weekend project (mostly Numberphile isnpired), besides Codeabbey. Like I've said, it's hobbyist use all the way for me, so I'll probably never stumble upon the frustrating problems that you faced. It's also very likely I won't help the language progress either. But if I can express myself through it and program my computer, I'm happy.

It makes me wonder though, why BioCad chose Haskell. Was it just out of familiarity from their lead developer?

And just because I think I've dragged this way off topic, Hard life was a very nice problem indeed :)