GC6CQT9 Denken tut nicht weh / myślenie nie boli – 06

[This article was first published on geocacheR, and kindly contributed to R-bloggers]. (You can report issue about the content on this page here)
Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.

This puzzle cache is in Mecklenburg-Vorpommern, Germany. The description is in German and repeated in Polish. Annoyingly, the puzzle instructions are in an image, so you can’t copy and paste the text into translation software. I retyped the German text into Google Translate and got the gist of it.

You have a weighing scales and five different weights. In combination they can be used to measure the weight of any unknown object from 1kg to 121kg. All weights are whole numbers.

To illustrate, imagine you have amongst your five weights, a 12kg weight and a 4kg weight. Clearly, you could successfully weigh another object of 12kg or 4kg. Also, by placing them together you could weigh something 16kg, and by placing the 4kg on one side and the 12kg on the other, you could determine the weight of an 8kg object.

This is probably some old classic, but it looked like an interesting programming puzzle. I didn’t try to google it, but instead thought about how to limit the scope of my search.

Firstly, it’s not obvious that the heaviest weight must be less than 121kg. For example, you can make 115kg using 100+15, but equally 130-15. I decided arbitrarily that I would test combinations up to 150kg.
Secondly, the total weight of the five weights must be at least 121kg. Obviously it’s not possible to measure the weight of any object in excess what you have available to put against it.

The constraints were not yet enough to make this a tractable problem. Even taking into account four of the five weights, the number of combinations for different weights from 1-150kg is 486,246,600. Clearly, I needed a way to narrow the search.

Looking on the cache page, the formula for the location gave me a way in:
N 53 52.(B-A)(E/C)(D/C+B) E 014 08.(C/B+A)({E-D}/C)(E/D)
(assuming AThis is very helpful! The format of the coordinates means you cannot have fractions: we know that E/C is an integer, as is D/C, C/B, (E-D)/C and E/D. By now I was starting to suspect what the solution would be, but I followed it through programmatically.

I set up the 5 objects with the values 1:150 and then made a data frame using the crossing function (from the tidyr package):

a <- b <- c <- d <- e <- 1:150
dafr <- crossing(b, c) 

This contains all 22500 permutations of two of the weights. But we can filter these rows straight away, because C>A, and C/A is an integer:

dafr %<>%
  filter(c > b) %>%

This reduces the combinations down to 630. A good start! Now we can add in another weight:

dafr %<>%
  crossing(e) %>%
  filter(e > c) %>%
  filter((e/c)%%1==0) %>%
  filter(e/c < 10)

Note that I’ve also filtered by E/C being less than ten.

In short, the whole of this step produces 252 combinations of weights

dafr %<>%
  crossing(e) %>%
  filter(e > c) %>%
  filter((e/c)%%1==0) %>%
  filter(e/c < 10) %>%
  filter((c/b)%%1==0) %>%
  crossing(a) %>%
  filter(b > a) %>%
  filter(b-a < 10) %>%
  filter(c/b+a < 10) %>%
  crossing(d) %>%
  filter(d > c) %>%
  filter(e > d) %>%
  filter((d/c)%%1==0) %>%
  filter((d/c)+b < 10) %>%
  filter(((e-d)/c)%%1==0) %>%
  filter(((e-d)/c) < 10) %>%
  filter((e/d)%%1==0) %>%
  filter((e/d) < 10) %>%
  select(a, b, c, d, e) %>%
  mutate(max=a+b+c+d+e) %>%
  filter(max > 120)

They are the weightsets that might work. But only one of those is the answer. So which one?
To answer that, we need to consider some way of finding all of the internal combinations of each of those weightsets. Consider the first line: 1 2 10 40 80. Obviously we can make 1kg, 2kg, 3kg (1+2), 7kg (10-2-1), and so on.
In order to make a combined weight, we can take each weight in turn and weight positively, negatively, or not use it. So the 7kg result above is -1*1 + -1*2 + 1*10 + 0*40 + 0*80.

I created new variables in the data frame, called v, w, x, y, and z. These held every permutation of -1, 0, and 1, using the crossing function:

v <- w <- x <- y <- z <- -1:1
dafr %<>% crossing(v, w, x, y, z)

Then, multiplying the a-e by v-z, I had every possible use-combination of all the valid weightsets:

dafr %<>%
  mutate(av=av, bw=bw, cx=cx, dy=dy, ez=e*z) %>%
  mutate(weigh=av+bw+cx+dy+ez) %>%
  select(a, b, c, d, e, weigh)

Finally, I counted up how many separate weights could be achieved per weightset:

dafr %>%
  filter(weigh > 0) %>%
  filter(weigh < 122) %>%
  unique() %>%
  group_by(a, b, c, d, e) %>%
  summarise(n=n()) %>%

As expected, there was one weightset at the top of that table that covered all 121 possibilities, meaning I just needed to plug the values into the formula by hand and the puzzle cache was solved.

I won’t show the answer here because most cache owners don’t appreciate their mysteries being spoiled by having the solution posted online. But the programmatic approach worked in this case, with a little thought to circumvent the obvious issues of naively working through hundreds of millions of combinations.

That’s not the say the programmatic approach is the best way to approach caches like this. Looking at the answer, an obvious heuristic approach to producing the answer reveals itself to me. And it was the way I “saw” half way through creating the programme. But sometimes the intelligent way is only obvious after the fact, and the programmatic approach can help you learn something about the nature of the problem.

To leave a comment for the author, please follow the link and comment on their blog: geocacheR.

R-bloggers.com offers daily e-mail updates about R news and tutorials about learning R and many other topics. Click here if you're looking to post or find an R/data-science job.
Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.

Never miss an update!
Subscribe to R-bloggers to receive
e-mails with the latest R posts.
(You will not see this message again.)

Click here to close (This popup will not appear again)