General discussions: P278 Polyominoes

gardengnome 2022-05-04 21:05:36

P.S. if your solution includes generation of all possible shapes, feel free to boast at forum up to which degree you were able to calculate - and how many memory / time is spent.

Okay, as a starter for n=16: Python 3.10, single-threaded, basic algorithm:

n=1  n_polyominoes=1   time=0.0s
n=2  n_polyominoes=1   time=0.0s
n=3  n_polyominoes=2   time=0.0s
n=4  n_polyominoes=5   time=0.0s
n=5  n_polyominoes=12   time=0.0s
n=6  n_polyominoes=35   time=0.0s
n=7  n_polyominoes=108   time=0.0s
n=8  n_polyominoes=369   time=0.0s
n=9  n_polyominoes=1,285   time=0.1s
n=10  n_polyominoes=4,655   time=0.3s
n=11  n_polyominoes=17,073   time=1.3s
n=12  n_polyominoes=63,600   time=5.5s
n=13  n_polyominoes=238,591   time=23.1s
n=14  n_polyominoes=901,971   time=100.4s
n=15  n_polyominoes=3,426,576   time=454.7s
n=16  n_polyominoes=13,079,255   time=4967.7s

This matches A000105 Number of free polyominoes. Lots of room for improvement.

Rodion (admin) 2022-05-05 15:07:15

Ohm. I just noticed in your message "polymino" has 3 "o"... Perhaps I should update the text...

Thanks for sharing!

My implementation is in Go - i.e. compiled language - so it is predictably somewhat faster:

3 min for n=16
12 min for n=17

However it is quite greedy on memory. Initially I stored all generated "fixed" versions of pieces - but it lead to OOM even on attempt to generate for n=16 (on my laptop with 12Gb). I first tried to make smaller representation of the piece, simply compressing repeating characters, but it was not complete success. Then I modified the code to store only "free" versions of pieces - I thought it will make it run say 4 times slower - but surprisingly the running time just marginally changed. Still it takes 8Gb for n=17 so I can't experiment further without significant reworking of internal representation.

Lots of room for improvement.

When I looked at your code, I was much impressed by it being very short. Hope to investigate and understand the approach bit later, when get rid of my day work. Mine is over 200 lines long.

time=4967.7s

It is not PyPy, right? I usually expect "standard python" to be about 20 times slower than compiled languages so the value seems to be consistent with this expectation.

P.S. I feel very sorry - just noticed today letters from you and Clive in my mailbox. Seemingly I wasn't carefully looking into it for the last week or more. Thanks a lot, shall answer shortly!

gardengnome 2022-05-05 19:26:28

Hi, the results were for "standard python" 3.10. I had tried PyPy 3.11 expecting a boost, but surprisingly that actually slowed it down!? Also, using 8GB instead of 1GB improves performance for n=16 somewhat to about 3,600 seconds = 1 hour, still rather slow. I might have a go at a java version.

With regard to the code, the heavy lifting is done by the default_variant(poly) function (that doesn't give anything away in this open thread).

gardengnome 2022-05-10 18:02:24

Hi Rodion, I think I somehow broke the system. :)

Problem 278 shows as unsolved for me under "Problems" even so I definitely solved it; and resubmitting a solution does not correct that. Interestingly, the count of solved problems under "Ranking" is correct (but not the enlightenment).

Rodion (admin) 2022-05-11 05:50:53

Hello Mathias, thanks for detailed description! Sounds scary!

Please re-check now - perhaps, hopefully, it's better.

Initially thought it is db failure (we had it once only) - but, no, seemingly some flaw in logic / implementation of work with db. There is a table for keeping track who solved what (e.g. user-task relation) and it has field for marking solution as "secondary" (introduced long ago when asked to allow storing more than one solution per task)... Surprisingly your only solution was marked as secondary (I modified it to primary manually). Not sure how that happened - shall try to review the flow of saving / updating solutions. The count of solved problems, however, is stored along with userdata. Enlightment too, but it is recalculated on cron, while counter never decreases after being increased once on solving some new task.

gardengnome 2022-05-11 06:57:44

Many thanks Rodion,

I think I have a good idea what happened.

I submitted an updated solution to this problem. The auto-checker recognised it as C# or something, and I forgot to manually change the language to python. I then saw that you can change the language retrospectively when you look at your solution (there is a drop down). Great, that's what I did. And I assume that when you change the language to something for which already a primary solution exists, it doesn't change the flag to primary. In other words, you overwrite the primary solution with the secondary solution, and then only the secondary solution remains.