[Community Puzzle] Heart of the City

Puzzles
#1

https://www.codingame.com/training/expert/heart-of-the-city

Send your feedback or ask for help here!

Created by @SamSi,validated by @MadKnight,@anst and @SatineChatounette.
If you have any issues, feel free to ping them.

#2

A post was merged into an existing topic: Community Puzzle : Heart of the City

#3

Hi everybody,

I am trying to code a solution for Heart of the City, but it seems I am wrong with test case 3:
I count 88 and the answer is 80

Can you help me to see my fault ?
… 1…2…3…4…5… 6…7…8…9…10.11
1 …:negative_squared_cross_mark::white_check_mark::white_check_mark::white_check_mark::white_check_mark::negative_squared_cross_mark::white_check_mark::white_check_mark::white_check_mark::white_check_mark::negative_squared_cross_mark:
2 …:white_check_mark::negative_squared_cross_mark::white_check_mark::white_check_mark::white_check_mark::negative_squared_cross_mark::white_check_mark::white_check_mark::white_check_mark::negative_squared_cross_mark::white_check_mark:
3 …:white_check_mark::white_check_mark::negative_squared_cross_mark::white_check_mark::white_check_mark::negative_squared_cross_mark::white_check_mark::white_check_mark::negative_squared_cross_mark::white_check_mark::white_check_mark:
4 …:white_check_mark::white_check_mark::white_check_mark::negative_squared_cross_mark::white_check_mark::negative_squared_cross_mark::white_check_mark::negative_squared_cross_mark::white_check_mark::white_check_mark::white_check_mark:
5 …:white_check_mark::white_check_mark::white_check_mark::white_check_mark::white_check_mark::white_check_mark::white_check_mark::white_check_mark::white_check_mark::white_check_mark::white_check_mark:
6… :negative_squared_cross_mark::negative_squared_cross_mark::negative_squared_cross_mark::negative_squared_cross_mark::white_check_mark:.C.:white_check_mark::negative_squared_cross_mark::negative_squared_cross_mark::negative_squared_cross_mark::negative_squared_cross_mark:
7 …:white_check_mark::white_check_mark::white_check_mark::white_check_mark::white_check_mark::white_check_mark::white_check_mark::white_check_mark::white_check_mark::white_check_mark::white_check_mark:
8 …:white_check_mark::white_check_mark::white_check_mark::negative_squared_cross_mark::white_check_mark::negative_squared_cross_mark::white_check_mark::negative_squared_cross_mark::white_check_mark::white_check_mark::white_check_mark:
9… :white_check_mark::white_check_mark::negative_squared_cross_mark::white_check_mark::white_check_mark::negative_squared_cross_mark::white_check_mark::white_check_mark::negative_squared_cross_mark::white_check_mark::white_check_mark:
10 :white_check_mark::negative_squared_cross_mark::white_check_mark::white_check_mark::white_check_mark::negative_squared_cross_mark::white_check_mark::white_check_mark::white_check_mark::negative_squared_cross_mark::white_check_mark:
11 :negative_squared_cross_mark::white_check_mark::white_check_mark::white_check_mark::white_check_mark::negative_squared_cross_mark::white_check_mark::white_check_mark::white_check_mark::white_check_mark::negative_squared_cross_mark:

I count 11x11 - 1 - 8x4 = 88

#4

Here are the hidden buildings that are missing (:x:), with the buildings hiding them (:heavy_check_mark:):

… 1…2…3…4…5… 6…7…8…9…10.11
1… :negative_squared_cross_mark::white_check_mark::white_check_mark::white_check_mark::white_check_mark::negative_squared_cross_mark::white_check_mark::white_check_mark::white_check_mark::white_check_mark::negative_squared_cross_mark:
2… :white_check_mark::negative_squared_cross_mark::white_check_mark::x::white_check_mark::negative_squared_cross_mark::white_check_mark::x::white_check_mark::negative_squared_cross_mark::white_check_mark:
3… :white_check_mark::white_check_mark::negative_squared_cross_mark::white_check_mark::white_check_mark::negative_squared_cross_mark::white_check_mark::white_check_mark::negative_squared_cross_mark::white_check_mark::white_check_mark:
4… :white_check_mark::x::white_check_mark::negative_squared_cross_mark::heavy_check_mark::negative_squared_cross_mark::heavy_check_mark::negative_squared_cross_mark::white_check_mark::x::white_check_mark:
5… :white_check_mark::white_check_mark::white_check_mark::heavy_check_mark::white_check_mark::white_check_mark::white_check_mark::heavy_check_mark::white_check_mark::white_check_mark::white_check_mark:
6… :negative_squared_cross_mark::negative_squared_cross_mark::negative_squared_cross_mark::negative_squared_cross_mark::white_check_mark:.C.:white_check_mark::negative_squared_cross_mark::negative_squared_cross_mark::negative_squared_cross_mark::negative_squared_cross_mark:
7… :white_check_mark::white_check_mark::white_check_mark::heavy_check_mark::white_check_mark::white_check_mark::white_check_mark::heavy_check_mark::white_check_mark::white_check_mark::white_check_mark:
8… :white_check_mark::x::white_check_mark::negative_squared_cross_mark::heavy_check_mark::negative_squared_cross_mark::heavy_check_mark::negative_squared_cross_mark::white_check_mark::x::white_check_mark:
9… :white_check_mark::white_check_mark::negative_squared_cross_mark::white_check_mark::white_check_mark::negative_squared_cross_mark::white_check_mark::white_check_mark::negative_squared_cross_mark::white_check_mark::white_check_mark:
10 :white_check_mark::negative_squared_cross_mark::white_check_mark::x::white_check_mark::negative_squared_cross_mark::white_check_mark::x::white_check_mark::negative_squared_cross_mark::white_check_mark:
11 :negative_squared_cross_mark::white_check_mark::white_check_mark::white_check_mark::white_check_mark::negative_squared_cross_mark::white_check_mark::white_check_mark::white_check_mark::white_check_mark::negative_squared_cross_mark:

6 Likes
#5

And that’s when you realize the problem is a little bit harder that what you first imagined :slight_smile:

1 Like
#6

I found it was a very good challenge but if you do not like mathematics, it is a bit hard to solve (especially for the last case).

#7

I’m stuck on this one. :frowning:
I can’t find a simple formula and my python attempt with loops and common divisors is not efficient enough for testcases 5-7.
I’m also thinking about integer factorization and primes.
Can somebody give my a hint?

1 Like
#8

You are in the good way if you think about arithmetic. Try to have a look at the dividers of a number…

1 Like
#9

I had an interesting journey with this puzzle.

First it was “piece of cake”, and then shortly after the “aha, not as easy as it seems …”

Then some thinking which I liked a lot, and the hidden structure was revealed. This allowed me to write a naive solution (I guess similar to @RoDr1g0 ) which solved nicely cases 1…4.

Then started the deep dive, and in this particular puzzle, the deep dive involves college-level arithmetic (as hinted above), number theory, some code optimizations etc.

I found it somewhat interesting to go to this level of in-depth math, and did some google searches, which allowed me to find an optimized solution for cases 5,6.

Mind you, this requires very good understanding of math. Not sure I saw such things in my BA (and I did learn math etc…)

The “ultimate” required too much deep-dive, so I left it alone.

I’m new to this site, and I like it much.
I would prefer in such challenges that the “required knowledge” is listed up-front. Had I known that this requires such a level of math I may have chosen to steer elsewhere (“coders strike back”, gold league right now. Yami … :slight_smile: )

Edit - I jumped the gun too soon. Check @irmo322 comment below. Indeed there is a (very) elegant solution to this puzzle.

2 Likes
#10

I managed to work out the mathematics behind the problem description all by myself. Now, so I thought, I just need to implement the mathematics in code.

My naive implementation was not fast enough for the bigger numbers. That was expected. But my code optimizations were still not fast enough.

I searched around and found some stackexchange codegolf challenge which described this exact problem. Sadly even the presumably highly optimized code from the stackexchange codegolf was not fast enough for the bigger numbers. So I gave up on this puzzle.

I had fun working out the mathematics. I had fun implementing the mathematics. I had fun trying to optimize my naive implementations. I gave up after realizing that I probably need advanced mathematics to solve the big numbers.

In other words: the big numbers are a tad too big. Make them big enough that naive implementations fail. But not so big that it requires advanced mathematics. Or mark the puzzles as requiring advanced mathematics.

[yep, a moderator removed the link]

It probably spoils too much of the puzzle so mods will probably remove the link.

I tried the python version.

1 Like
#11

Hi there!

Indeed it’s a pretty interesting puzzle.

For the last test, I have two hints for you:
1- You don’t necessary need to dive into hard mathematics. There is a solution which can be explained to a (smart) 12 years old teenager.
1 - Use a fast language as C. For example, my solution wasn’t fast enough if written in lua (a script langage) but passes the last test when written in C.

Have fun :slight_smile:

1 Like
#12

My hat’s off to you , @irmo322. Beautiful solution.

Not sure about the 12 years old, but indeed a simple and elegant approach.
Thank you for providing the inspiration.

Your point about the difference between scripting and C is something I’ve also thought about. I wasn’t sure that the site can factor the difference between the execution speed of different languages… Following your experience it seems that there are indeed gaps, and compiled languages are probably faster. Interesting.

#13

Thank you for the nice comment!

#14

n=41
I don’t think that it helps, when i do this.

1 Like
#15

Oh my god, this image is so helpful! I tried creating this in ASCII, but it gave me a headache to try to read it. You can actually analyze the factors in this! Notice how in row 6, each square is red if the corresponding square in row 3 or in row 2 is red? And it just continues! Thank you!

#16

I have it solved in native Python, all testcases.
With some head scratching, google skills and Wikipedia-grade math.
So, doable in scripting languages, just have to use more elegant approach than bit-bashing.

Then again, there are other, very concise solutions in Python, that don’t involve hard math whatsoever. or so it seems. maybe it’s hidden behind the lines.

#17

an update to my wailing from years ago. i kept returning to this puzzle once or twice a year and tried a bit of this and that. i found some mathematical shortcuts. which might seem “simple” once understood. but some of it really is not easy to understand. at least for me. i tried some programmatic optimization. some worked some not. most just marginal.

eventually i got a python solution which was able to pass the last test some of the time. i could have tried submitting that a couple of times until it passed but i did not want to do that. so i coded the same algorithm in c and it passed consistently.

this was some years ago. i forgot whether i still needed to optimize some on the c code. perhaps yes.

well. just wanted to share. maybe encourage some frustrated codingamer trying this puzzle.

#19

I tried calculating slopes, and whenever we find a slope that is already visited: don’t increase the count, else: increase the count by one.

I tried splitting the map to eighths, solving only one eighth, and outputting count*8+8, however, in both javascript and python I get only 57%, my results are corrects, but I’m a little slow and memory consuming I think? Any ideas?

#20

Does your code do any memoisation?

#21

Only the visitedSlopes variable, other than that, IDK if it is even possible to memoize anything else