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
• Devaka Cooray
• Ron McLeod
• Paul Clapham
• Liutauras Vilda
Sheriffs:
• paul wheaton
• Jeanne Boyarsky
• Tim Cooke
Saloon Keepers:
• Stephan van Hulst
• Tim Holloway
• Tim Moores
• Mikalai Zaikin
• Carey Brown
Bartenders:

Marshal
Posts: 8831
631
• Number of slices to send:
Optional 'thank-you' note:
Hm.. the above idea works on my test data, but get no result on real input, not because it runs forever, but because such coordinate isn't among neighbouring coordinates of rhombus corners.

I might have a bug...

Liutauras Vilda
Marshal
Posts: 8831
631
• Number of slices to send:
Optional 'thank-you' note:

Earlier, I wrote:coordinate must be around, or in different words, within Manhattan distance of 1 of some given sensors covered area's rhombus corner

I did few drawings before attempting, so that looks to me very promising, and in fact, as mentioned - works on test data. Attaching visual representation I draw.

While I was writing this post.. did more drawing.. And here is another scenario - and it is clear why it doesn't work on real input, because it is possibly that point isn't around any of rhombus corner.
sensor_rhombus.jpg

Liutauras Vilda
Marshal
Posts: 8831
631
• Number of slices to send:
Optional 'thank-you' note:
Yeah, so that left drawing led me to another approach. Instead of obtaining rhombus corner coordinates neighbours, to obtain side coordinates outside rhombus and then check like in the previous approach, which coordinate is not covered by any other sensor.

That worked!

But inefficient, because if Manhattan distance between a sensor and beacon is 1_000_000_000, that means in between corner coordinates are also 1M coordinates * 4 sides = 4M. And then multiplied by number of sensors.

On my machine that ran 3.5 minutes. But happy it actually worked, had to massage racket's IDE memory limit though

Bartender
Posts: 5466
212
• 1
• Number of slices to send:
Optional 'thank-you' note:
That is indeed a fine idea. I thought that if you determine the line through two points of a diamond, but then one pixel farther, and you do the same for another diamond, then the crossing point is a point not seen by two diamonds, and can thus be a candidate. Two diamonds have 4 such points in common, so there are n *(n-1) *4 possibilities. These lines have simple equations, of the form x - y = p and x + y = q. But I wasn't sure about why that one point had to be one of those points and did not investigate it.

Edit: your drawing right shows why that method would have worked!

Saloon Keeper
Posts: 15276
350
• 1
• Number of slices to send:
Optional 'thank-you' note:
I wrote the post below before I saw this topic had 4 pages. Ignore.[/edit]

You're on the right track, but I think you've made a mistake in your reasoning.

An unscanned beacon can be enclosed by the edges of 4 overlapping rhombi, similar to a camera shutter, with the corners of the sensor ranges being nowhere near the unscanned beacon.

You should try ALL positions just outside a sensor range, not just the corners.

Sheriff
Posts: 5552
326
• 1
• Number of slices to send:
Optional 'thank-you' note:
True to form I fell off the wagon at day 15. I'll probably pick away at them throughout the year as time and enthusiasm permits. I really enjoy them but they can be a real time sink.

Piet Souris
Bartender
Posts: 5466
212
• 1
• Number of slices to send:
Optional 'thank-you' note:
Hmm, been very busy with day 19 of AoC 2022, and what a nightmare of an exercise this is.

At first reading I thought of applying some linear optimization tricks, but I did not manage to get some working formulas. And besides, I could not find any free software that could solve such a thing.

Then I decided to go for brute force, DFS search, since I was afraid that BFS would tend to very long queues. But with DFS, there are several strategies that you can apply. Whatever strategy I tried, I did get 9 for the example blueprint 1, but I got only 11 for example blueprint 2.

Today I tried the strategy of: given a minute, buy as much geode-robots as possible, and if there is some 'cash' left, buy as much obsidian-robots, et cetera, and enter the next minute with this new situation. I also dfs'ed doing nothing in that same scenario. To my big surprise I got 13 as the optimal result for example blueprint 2! Yes, a bug of course, but here is my version of the scheme that was given in the example.

every line starts with an m, giving the minute at hand. Read for minute the situation at the end of the previous minute, so for minute 1 we see the initial state, with just one ore-robot and nothing else. Then in the next minute (m: 2) we see that we did nothing, just letting that robot collect one ore, and that situation is seen on the line with m: 2, so in fact it is the end-situation for the first minute as given in the example.

Have a look at m: 14. If we compare the 4 numbers on the right (giving the number of robots) and compare that to these numbers in the line above, we see that we built an ore-robot and an obsidian-robot. That costs 2 + 3 ores and 8 clays. If we look at the previous line, we ended with 5 ores and 8 clays, so these become 0 and 0. Then we had 5 ore-robots and 6 clay-robots, so the minute ends with 5 ores and 6 clays, and with 6 ore-robots, 6 clay-robots and 2 obsidian-robots.

I checked the whole list, but I did not find any mistakes. As you see, I ended with 13 geodes, where the example claims that 12 is the optimal number.

And I know it is a monk-labour (monnikenwerk), but can anyone spot whats wrong with my scheme?

**************************************************************************************************

Piets result day 19 AOC 2022 example blueprint 2

Blueprint 2:
Each ore robot costs 2 ore.
Each clay robot costs 3 ore.
Each obsidian robot costs 3 ore and 8 clay.
Each geode robot costs 3 ore and 12 obsidian

**************************************************************************************************

m:  1, c:                 INIT, or:  0, cl:  0, ob:  0, ge:  0, orR:  1, clR:  0, obR:  0, geR:  0
m:  2, c:          DID_NOTHING, or:  1, cl:  0, ob:  0, ge:  0, orR:  1, clR:  0, obR:  0, geR:  0
m:  3, c:          DID_NOTHING, or:  2, cl:  0, ob:  0, ge:  0, orR:  1, clR:  0, obR:  0, geR:  0
m:  4, c:            BUILT_ORE, or:  1, cl:  0, ob:  0, ge:  0, orR:  2, clR:  0, obR:  0, geR:  0
m:  5, c:          DID_NOTHING, or:  3, cl:  0, ob:  0, ge:  0, orR:  2, clR:  0, obR:  0, geR:  0
m:  6, c:           BUILT_CLAY, or:  2, cl:  0, ob:  0, ge:  0, orR:  2, clR:  1, obR:  0, geR:  0
m:  7, c:            BUILT_ORE, or:  2, cl:  1, ob:  0, ge:  0, orR:  3, clR:  1, obR:  0, geR:  0
m:  8, c:            BUILT_ORE, or:  3, cl:  2, ob:  0, ge:  0, orR:  4, clR:  1, obR:  0, geR:  0
m:  9, c:           BUILT_CLAY, or:  4, cl:  3, ob:  0, ge:  0, orR:  4, clR:  2, obR:  0, geR:  0
m: 10, c:           BUILT_CLAY, or:  5, cl:  5, ob:  0, ge:  0, orR:  4, clR:  3, obR:  0, geR:  0
m: 11, c:           BUILT_CLAY, or:  4, cl:  8, ob:  0, ge:  0, orR:  5, clR:  4, obR:  0, geR:  0
m: 12, c:       BUILT_OBSIDIAN, or:  6, cl:  4, ob:  0, ge:  0, orR:  5, clR:  4, obR:  1, geR:  0
m: 13, c:           BUILT_CLAY, or:  5, cl:  8, ob:  1, ge:  0, orR:  5, clR:  6, obR:  1, geR:  0
m: 14, c:       BUILT_OBSIDIAN, or:  5, cl:  6, ob:  2, ge:  0, orR:  6, clR:  6, obR:  2, geR:  0
m: 15, c:           BUILT_CLAY, or:  6, cl: 12, ob:  4, ge:  0, orR:  7, clR:  7, obR:  2, geR:  0
m: 16, c:       BUILT_OBSIDIAN, or:  7, cl: 11, ob:  6, ge:  0, orR:  7, clR:  8, obR:  3, geR:  0
m: 17, c:       BUILT_OBSIDIAN, or:  8, cl: 11, ob:  9, ge:  0, orR:  7, clR:  9, obR:  4, geR:  0
m: 18, c:       BUILT_OBSIDIAN, or:  7, cl: 12, ob: 13, ge:  0, orR:  8, clR: 10, obR:  5, geR:  0
m: 19, c:          BUILT_GEODE, or:  9, cl: 14, ob:  6, ge:  0, orR:  8, clR: 10, obR:  6, geR:  1
m: 20, c:       BUILT_OBSIDIAN, or:  8, cl: 16, ob: 12, ge:  1, orR:  8, clR: 12, obR:  7, geR:  1
m: 21, c:          BUILT_GEODE, or:  8, cl: 20, ob:  7, ge:  2, orR:  9, clR: 12, obR:  8, geR:  2
m: 22, c:       BUILT_OBSIDIAN, or:  9, cl: 16, ob: 15, ge:  4, orR: 10, clR: 12, obR: 10, geR:  2
m: 23, c:          BUILT_GEODE, or: 10, cl: 12, ob: 13, ge:  6, orR: 10, clR: 12, obR: 12, geR:  3
m: 24, c:          BUILT_GEODE, or: 11, cl: 16, ob: 13, ge:  9, orR: 10, clR: 13, obR: 13, geR:  4
m: 25, c:          BUILT_GEODE, or: 10, cl: 13, ob: 14, ge: 13, orR: 11, clR: 13, obR: 15, geR:  5

A: 13

Sheriff
Posts: 17633
300
• 1
• Number of slices to send:
Optional 'thank-you' note:

Piet Souris wrote:if monkey 0 processes value 200, and should send it to monkey 1, that has a dividableBy 13, then you do not need to send that 200, but 200 % 13 = 5

Tim Cooke wrote:...idea does work for the very next monkey but not for other monkeys after that. Might there be something else you can do to the worry level that will work for all monkey tests?

Mike Simmons wrote:Tim C's hints are exactly on target for this one.

Liutauras Vilda wrote:Ok guys, finally, after reading it and re-reading (multiple times) those hints and inspecting input data, eventually got it. Unfortunately, but hints were key. Perhaps I should have just left this one out unresolved.

I know it's waaaay past Advent but I'm still plugging away at these -- they're great exercises.

I could not figure out the better way to manage worry level for Part 2 so I cheated and looked around. I switched from using Int to BigInteger then back to Long in the end for the worry level. There's no discernible difference between BigInteger and Long once you have the right incantation to manage the worry level; calculating 10000 rounds doesn't take more than a second or two with either one.

Here are the key functions in my Kotlin solution:

Piet Souris
Bartender
Posts: 5466
212
• Number of slices to send:
Optional 'thank-you' note:
I'm busy with day 22, second part. It is not difficult, but incredibly tedious. I treated the example as a 3 x 4 array, with cube-sides 2, 4, 5, 6, 10, 11. Then I have a Map with (side, Direction) -> (new side, new Direction) and a method 'Position goingFrom(Direction from, Direction to, Position p)'. As said, very tedious, and for the real thing I had to make a new Map.

Anyone with a much easier way?

Liutauras Vilda
Marshal
Posts: 8831
631
• 1
• Number of slices to send:
Optional 'thank-you' note:
Ok, in which case I need to get back to Day 16, it seems we are not done yet

Piet Souris
Bartender
Posts: 5466
212
• 1
• Number of slices to send:
Optional 'thank-you' note:
No hurry, we have time until dec 1, 2023

Junilu Lacar
Sheriff
Posts: 17633
300
• Number of slices to send:
Optional 'thank-you' note:
Playing around with Kotlin DSLs. Here's what my main() for Day11 looks like now:

I'm always refactoring my solutions and playing around with alternatives and I wanted to have a way to make sure I didn't break the solution as I fiddled around with it. Sure, I could use a testing framework like JUnit or KotlinTest but where's the fun in that?

The whole extension functions with receivers was kind of mind-twisting at first but eventually got it to work after a couple of tries last night.

Junilu Lacar
Sheriff
Posts: 17633
300
• Number of slices to send:
Optional 'thank-you' note:
My next iteration will be to use an infix function to get to something like this:

Junilu Lacar
Sheriff
Posts: 17633
300
• 1
• Number of slices to send:
Optional 'thank-you' note:

Junilu Lacar wrote:My next iteration will be to use an infix function

That was a lot easier to do than I thought it would be. I renamed the functions so it becomes:

 Nothing up my sleeve ... and ... presto! A tiny ad: a bit of art, as a gift, the permaculture playing cards https://gardener-gift.com