Polyominoes

Rate this contribution

Make the contribution public (lvl 20+)

Comments

38 Comments

about 12 months ago

Working on this in PHP. Can't get more than 6 out of 9 cases nor validators online. The most expensive part of my code is copying the board $tb=unserialize(serialize($b)); (a full 2 dim board) which is done for example 154,265 times on case 6 - Glass. If i could fit the biggest board in 63 bits I'm sure i could do it. Traditionally my depth searches can't go past depth 9, especially with this width - so that tracks with expectations. I think I can make it better, but for the time expenditure to do so ... it should be hard and worth more xp imo. there are some tricks to pull off DFS, the overhead of any other alg is too much imo that add undue complexity. if you scan the board in a diagonal fashion you can pre-setup "fit" placement. For example, Glass has 715 such total placements over the 9 pieces. if you have x,y you can clearly see how any cell x+a,y+b is dependent on x,y, so pre-tabling by x,y on diagonals should be efficient. And if letters are reassigned from largest to smallest pieces IFCEGJLBNDMAKH , the distribution of those letters over all 715 is 88,37,0,58,56,60,56,0,142,0,68,150,0,0 with the first trial as I @ 0,0. Considering there are multiple possible solutions, reducing the open board space first makes sense. Bad future moves are easily skipped if a condition like if (($bv|$cv)==$bv) { } isn't satisfied. However that brings up the second most expensive function, grabbing the mask value from the board... which is called 786,681 times ... again just grabbing 16 bits from a 2d board and comparing to the piece orientation bitset. Since order of placement doesn't matter, i can see dancing around and hashing compatible and incompatible moves ... but I can't visualize the expense v. savings since moves can be skipped so easily. I'll try to more linearize the board and adjust the foundational bit twiddling, but I doubt I can solve all 9 online in php. Since php stores strings more efficiently than arrays i tried changing the mb_internal_encoding, but still requires a conversion step before any comparisons are made. So while copying less memory each time is more efficient the coding and decoding seems to be still be done at a 7-bit level internally and you lose any speed gains. A 1dim array of height+4 would be required to streamline the board to its best available format, which i'll try next. I type too much, but i think limiting the pieces to a total of 9 per case would solve the issue of slow langs. And thanks for not making it more than 1 piece being possible per case. yes, coding is fun. overthinking, not so much.

VizGhar Unnamed CodinGamer

about 12 months ago

Hmm not sure if its best idea to change testcases now. But I can move it to HARD category tho... This one was approved in a few days so I was lacking insights like yours. However @Rafarafa solved it without DLX in Ruby

NicknamedTwice Unnamed CodinGamer

1 year ago

cool puzzle but my solution passes all tests in ide but fails validator for test 9 (full brick) :(

VizGhar Unnamed CodinGamer

1 year ago

@Rafarafa came with non-DLX solution in Ruby, so it is solvable. But there are multiple optimization steps required. Heuristics, handling symmetry, bitboarding etc. Not sure whether MEDIUM difficulty is correct bucket for this puzzle in this case.

Timinator Unnamed CodinGamer

1 year ago

✅ Approved the contribution. Comment: Plenty of comments below. I love this contribution! Sure, it's a classic Exact Cover, so maybe I'm biased. Still, @VizGhar has done an absolutely outstanding job putting it together!

cedricdd Unnamed CodinGamer

1 year ago

✅ Approved the contribution. Comment: Cool puzzle, the description is clear & you have a nice progression with the tests/validators. The referee seems to be working properly.

VizGhar Unnamed CodinGamer

1 year ago

Increased time limit to 5s Added more easy tests to try basics Tests - Validators now more similar Removed DFS tag since clear DFS is too hard to pull of Added Algorithm X tag

Rafarafa Unnamed CodinGamer

1 year ago

Some feedback while I still have not entirely solved it. I went and frankesteined my ruby solution (~DFS like) to https://www.codingame.com/..., and: - I could have used some smaller testcases at the beginning, preferably with starting letters (that is: A, B instead of let's say E, N), to debug the core logic. - I'm timeoutting on Butterfly and Owl Mask - I don't find any solutions to Llama (validator) and Dino (validator) - I pass the rest From my understanding, the timeout limit is 2 seconds for everyone (as opposed to language dependent limits in I/O puzzles), so I would be very interested to know if someone managed to solve it in python / ruby within that limit (using a DFS-like approach). Also, the two hardest public tests: Butterfly and Owl Mask, seem to hint at symmetry optimizations that are not relevant for the validators. Maybe there should be more similarity?

Rafarafa Unnamed CodinGamer

1 year ago

I figured out why I was not finding solutions to the validators, I was caching state with: key = floor.gsub(/[^.O]/, ".").hash but I should have had cached also the pieces used: key = [floor.gsub(/[^.O]/, "."), hash_usage].hash It is still remarkable that this only (in my case at least, since it is dependent on the DFS exploration order) appears to be an issue in the validators. ------ I still timeout on Butterfly and Owl Mask :/, but now I pass everything else (including ofc every validator). That is a problem. And the code (expires in one week), in case you want to test the timings of a possible solution: https://bpa.st/...

Timinator Unnamed CodinGamer

1 year ago

print('OOD') print('AAD') print('O.O') I can pass test case #1 with this output. I get a "congratulations" message even though the pieces are not where they belong in the picture.

Timinator Unnamed CodinGamer

1 year ago

I also get congratulations for this on test case 2 even though one piece is well off the board and letters are messed up: print('..L..') print('AABBB') print('A.C.L') print('ACCCJ') print('H.C.J') print('HHJJJ')

darkhorse64 Unnamed CodinGamer

1 year ago

✅ Approved the contribution. Comment: An interesting problem with nice graphics. This sets a new standard for exact cover puzzles.

darkhorse64 Unnamed CodinGamer

1 year ago

I have mixed feelings about your puzzle: you could have made your life easier (and mine) if you only asked for a grid filled with symbols. It feels a bit over engineered. On the other end, it's very nice to have an animated puzzle.

VizGhar Unnamed CodinGamer

1 year ago

5DN1L also wanted to fill board in single turn. I'll pull the puzzle to WIP until resolved. Thank for input

Timinator Unnamed CodinGamer

1 year ago

Outstanding job! Fun to solve and especially fun to watch the tiles fly across and go into position. Being able to visualize the exact cover is super cool!

Timinator Unnamed CodinGamer

1 year ago

print("OO;.O;.O") print("0 1") Do you need to update your stub output? Have you considered including multiples? For instance: ABBBBEFN Adding multiplicity would make the puzzle more difficult for the exact cover solution. You don't even necessarily need more pictures. Could a single shape be solved multiple times (multiple test cases), each time with a different group of polyominoes?

VizGhar Unnamed CodinGamer

1 year ago

Yeah forgot update stub. Not sure if multiplicity will be more difficult. I could just set the polyomino ID to B0, B1... internally

5DN1L Unnamed CodinGamer

1 year ago

Title * Please change "Polyominos" to "Polyominoes". Default code * Please change "polyominos" to "polyominoes". * Please change "tiles" to "polyominoes" (twice). * Please change "tile" to "polyomino". Example * Please change ". Or" to ",". While I know it's acceptable to output the placement of more than 1 piece per turn, • Doing so actually triggers the "your code did not read all available input" warning. • Doing so is inconsistent with Output section, which specifies that only one line should be output per turn. So, let's do it the same way as Power of Thor: if the player knows the trick and wants to output everything in the first turn, let them do so, but we won't mention the trick in the statement 😉 Input * Line 1: Please change "polyominos" to "polyominoes". Output * Please change "Line" to "1 Line". * Please format "n", "row" and "column" with the <var> tag. The comma and the brackets will still be formatted with the <const> tag. * Any reason for having to place the pieces in a specific order? Would it be possible to let the player place the pieces in any order they want (e.g. the output will first specific the id of the piece to place, followed by where to put the piece)? Tags * I'm not sure how the tag "Flood fill" is relevant…? Thanks.

VizGhar Unnamed CodinGamer

1 year ago

Your notes are resolved now. Placing pieces in specific order is meant to force player to output just single line per turn and it's a little bit easier to handle on referee side. I've added paragraph in "The Goal" section to add a little bit to story = dont make your little brother angry. Edit: small changes in wording + added link to github repo. Nothing crucial

VizGhar Unnamed CodinGamer

1 year ago

Game is ready

ABOUT US CAREERS PRIVACY FAQ BLOG

The #1 tech hiring platform

SCREENING INTERVIEWING