• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Tim Cooke
  • paul wheaton
  • Jeanne Boyarsky
  • Ron McLeod
Sheriffs:
  • Paul Clapham
  • Liutauras Vilda
  • Devaka Cooray
Saloon Keepers:
  • Tim Holloway
  • Roland Mueller
Bartenders:

Dynamic programming (tiling dominoes problem)

 
Rancher
Posts: 317
16
IntelliJ IDE Firefox Browser Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Hello again! Here comes a brief edit because the original message is very unclear:

The problem we are trying to solve is
https://open.kattis.com/problems/tray. The other problem I am discussing, the python code and the video are only to give some background about a similar problem. You can just ignore my blabla, and jump to the problem

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Hello!

It's probably very bad and shameful style from me to ask for help for another problem while the last one (Eulerian path in engineering forum) is not yet solved, but I feel stuck. And you already helped me out so much dynamic programming that I feel confident we will solve it      

Here is the problem description. You are supposed to fill a grid 3 by n, with dominos that are 1 by 1, or 2 by one, placed horizontally or vertically. Some places are forbidden.

It is very similar to this other problem, where you have only 2 by one dominos. You can generate all solutions column by column, where every solution depends on the previous column. If we represent each column as a binary 2^3, then to have a 1 in column [i+1], the previous column is either completely occupied ([i][7]) or we can place a domino horizontally at the bottom of [i], that will trespass to [i+1], means that we have [i][6] in the previous column. There is a video about it from William Fiset.



While it is apparently possible to do a similar solution for the new problem, there is an alternative more elegant solution with 2^6 matrix, and recursive calls. I cannot come up with it and don't know how to start experimenting. Will you help me find the way, like we crossed the Hydra?

 
Marshal
Posts: 80295
434
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
That doesn't look like conventional Java®. It looks more like Python.
Have you found out what the algorithm is for your 2⁶ matrix? Or is that 2×6? Don't use caret ^; use ¹, ², ³, &#x2074...2079; and ⁰. That gives you ¹, ², ³, ⁴... ⁹ and ⁰. There are probably other versions of those HTML tags. Notice that the different exponents are different sizes in my current font.
 
Campbell Ritchie
Marshal
Posts: 80295
434
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I only watched a small part of that video, but it shows that it is impossible to tile a board with an odd number of squares with 2×1 tiles/dominos. One way to start is to tile a 2×3 board and then add another board and see how many combinations you get. If there are 11, then there are two where tiles cross its midline.
 
D.J. Quavern
Rancher
Posts: 317
16
IntelliJ IDE Firefox Browser Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Yes sorry, that's python, but python is just pseudocode sometimes so I used it for illustrative purposes.

We will use Java together of course   .

I just don't know how to begin to solve the Tray problem (https://open.kattis.com/problems/tray) recursively. If we just ignore the "bad tiles" for now, I don't know how to come up with a better solution than the one in the video.

Maybe I should edit my post, this video and posting about another problem just made it confusing for everyone. What do you think Campbell?
 
Campbell Ritchie
Marshal
Posts: 80295
434
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

D.J. Quavern wrote:. . . python is just pseudocode . . .

Hahahahahahahahahahaha!

Maybe I should edit my post . . .

Pleae don't edit it.

But if you ask the other mods, they will tell you my opinions are at the unprintable un‑editing end of the spectrum.
 
D.J. Quavern
Rancher
Posts: 317
16
IntelliJ IDE Firefox Browser Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Ok, I can post a brief edit to clarify my post, without deleting the original content.
 
Space pants. Tiny ad:
Smokeless wood heat with a rocket mass heater
https://woodheat.net
reply
    Bookmark Topic Watch Topic
  • New Topic