New problem 241 - Village Ways - is ready
Back to General discussions forum
UPD (from admin) - this problem is live: Village Ways!
The following problem description is an attempt to suggest an easy problem which still requires a little thought in order to solve it.
When a village became too large for its inhabitants, two new villages were created close to the original village. Although the villages had special names it will be convenient to refer to the original village as village 1 and to the two new villages as village 2 and village 3. Roads were made from village 1 to village 2 and from village 1 to village 3. There was no need for a road between villages 2 and 3 because the people could simply travel via village 1.
As the population increased two more villages (4 and 5) were built close to village 2 and joined to it by roads. Later still, villages 6 and 7 were built near to village 3 and joined to it by roads.
By this time the local headman of the original village had become the king of the whole region. He liked the pattern that was emerging with new villages and decided to keep it. Whenever new villages were needed he would take the first village (smallest number) that had not yet been expanded into the neighbouring countryside and would create two new villages joined to it by roads. These villages would be given the next two numbers that had not yet been used. All the villages would have local names but the king insisted that the villages were also known by their numbers. This would be particularly useful for the new postal system that he was hoping to introduce later!
So the next phase of expansion had villages 8 and 9 joined to village 4, villages 10 and 11 joined to village 5 and so on. Although no village had more than 3 roads leading from it, journeys between villages were still reasonably short. For example a journey from village 9 to village 3 would go through villages 4, 2 and 1. A journey from village 11 to village 4 would go through villages 5 and 2.
The problem is to calculate the number of villages that you would need to travel through in order to go between a specified pair of villages by the shortest possible route. The number will include the villages at the start and end of the route. If we use J(v1,v2) to represent the number of villages in the journey between villages v1 and v2 (inclusive), then from the examples above, J(9,3) = 5 and J(11,4) = 4. Similarly J(1,2) = 2 and J(3,3) = 1.
I would anticipate around 10 pairs to be given in a particular run of the problem. The numbers used can be quite large because the number of villages in the shortest chain will be much smaller. Some other examples are: J(26,84) = 11, J(89,85) = 9, J(912,107) = 14, J(102649,493550) = 33.
Clive, Hi!
This looks a bit towards "middle" rather than "easy" :) something one may expect at interview!
As the process of marking tasks for updated way of certification is already under way, we can add this one with no special considerations. Moreover the problem statement is already ready :)
I dare to propose a kind of experiment - perhaps you would like to participate. I just tried to extend the server code so that "generator/checker" could be provided in other language than php (as it was before).
So if you would like, perhaps, you'll go forward and create the "checker" as I call it? It should work pretty easy:
just generate some input data and expected answer - print them both, so that answer is the last line (and input may
consist of multiple lines). As I remember you prefer Python2 still, so for example problem requiring to multiply
two values (similar to problem #1 of adding two values) shall look like this:
#python2
import random
a = random.randint(10000, 99999)
b = random.randint(10000, 99999)
print("%s %s" % (a, b))
print(a * b)
The first line with comment is just technical, so the system knows how to run the code - but this one I can add manually of course.
What do you think? Won't it be too much/nasty to ask of you? Sure if you have no time/mood for this - I'll try myself :)
Rodion, Hi!
I can see why you might want to describe the difficulty level of this problem as “middle” so I clearly need to explain my thoughts. I wanted to design a problem which members would find interesting but also one which would be accessible to anyone who had successfully completed the first 10 problems on the site. The program for this problem is VERY EASY. It requires nothing more sophisticated than an understanding of elementary program structures (loops and branches). Having said that, writing the program is only one part of solving the problem. Working out how to solve it is less easy but not that difficult for anyone prepared to take the time to analyse the structure of the problem.
Some members (I hope only a few) will read the problem description and know immediately how to solve it. There is no interest in it for them and it wasn’t really designed for them. My intention is that members read the problem description and get an initial impression of something fairly complicated. However, a certain amount of thinking, possibly with a diagram or two, should soon begin to reveal that the problem is much simpler than it first appears. This analysis process is the interesting part of solving a problem. The program is the means of checking that the solution works. This brings me back to what I suggested about introductory comments relating to a list of recent problems. Describing this one as “middle difficulty” would immediately deter a large number of members who would regard their programming skills as below this level. I would prefer a description along the lines of: “An easy program to write but some careful thought is needed in analysing the problem”.
I’m intrigued that you think this problem would make a good interview question. Programming interviews must be a lot of fun!
I am very happy to take part in your experiment to have me create the checker in Python. I have already done this to match your requirements and am ready to send it to you. I can either use your gmail address or is there another address that you would prefer me to use via the TinyLetter facility that you have set up?
Gmail would be all right, yes. with tinyletter it is also somehow possible but I'm not sure myself, at least it seems not specially fitted to receive letters, as I understand :)
You can even post it here - I'll catch and we cut it out so no many people shall see, I believe it's ok
As for problem - I believe I understand the easiness of solution, but hopefully I'll be able to try solving it myself with your checker and see if I'm right :)
Clive, thanks, got it and copy-pasted. Looks like working.
Here is the problem - not visible in the list yet, but otherwise functional.
Let's check it (and whoever could participate - feel free to join)!
I shall improve formatting of statement (though for obvious reason I'd prefer not to modify wording itself).
What title would you like (regard current as temporary)?
Should we add some picture - or probably you'd like people to try drawing themselves (as it may give idea of solution, right?)
Also should we add the number of "testcases" in the first line? Or just state it is always 12?
Rodion, Should there be a link in your previous post? I cannot see any way to reach the problem. I shall be happy to check it once I can access it. I am happy to let you choose a title. This is not one of my strong points! The number of test cases is always 12 with the code I placed in the checker. I can change it to be variable but can see no reason why it shouldn't always be 12. I have mixed feelings about a diagram. I certainly would not want a diagram to show anything beyond village 7.
UPD: oh, sure forgotten the link, sorry: Village Ways
Well, seemingly I solved - just made answer bit borken not to spoil statistics :)
Really it takes some looking at the "map" and then some thinking to come up with 10-lines solution.
Slightly formatted problem statement and added description of input/output, with your example.
Please have a look, tell about necessary changes if any - and command when we should let it live!
UPD2: added "number of tests", though - just to make "example" in problem statement short. And then added a line
to the checker so this number is between 12 and 14, though you are right - there is no specific reason in it (except
if probably we shall decide to make larger testset later - for I found most of randomly chosen pairs have 1 as
their "lowest common ancestor").
Rodion,
I have checked the program and it seems to be running perfectly. I take your point about the number of pairs that have 1 as their lowest common ancestor. However, with the number of tests in the range 12 to 14 there is very little chance that this will be the case for all tests. It also means that a person who has made this logical error in their solution will typically get a result where most, but not all, of their answers are correct. They will then have to work out what is going wrong. I can see no reason why the problem should not go live. Thanks for all your help with it.
Hey, sorry to barge in. I had a quick look around after a while and stumbled across this thread. I read the description and used the five minutes between studying and sleeping to type a (very messy, I guess) solution. Just serves as additional verification for you that everything fits ;)
Thanks and hoping to have a bit more time soon :) Simon
Simon, glad to see you - and thanks for check!
We'll see if it pass Quandray's examination also - Grae often is quick to find some annoying flaws! :)
Clive, thanks for confirmation - completely agree, let it live! I posted email notification (still not sure how many people receive it).
there is very little chance that this will be the case for all tests.
I'm curious to check the probability, though probably it will happen bit later :)
Not sure but probably it's I should be more thankful for your help!
Can the start and finish villages be the same?
probably this was in examples... yep, just checked: J(3,3) = 1 ...though it may be a bit counter-intuitive :)
there is very little chance that this will be the case for all tests
Just tested this at last - on average 1 in 5000 runs (for N=12). We are safe as it's not "highly likely" there
will be thousands attempts at this problem soon :) but not exactly something we call "negligible" (to my own surprise).
Think of the villages as the nodes in a binary tree with village 1 being the root. A rough approximation of the likelihood of two villages coming from different ‘halves’ of the tree is 1/2, and in this case the root has to be visited as part of the shortest route. The likelihood for this to be the case for 12 random pairs of villages would be 1/2^12 = 1/4,096, which is close enough to the ‘1 in 5000’ observation.
It tooks 50 lines for me to finish the programme. But one guy, "gardengnome" just wrote the programme with less than 10 codes. Can I paste the code here, I need some explanations. Since I am very new to coding and python (2 months), I can not even understand his codes. :-)
Cheers, Sam.
Cheers. I am happy to explain the main idea, but we probably should do that in a thread that is limited to people who have already solved this problem. Rodion, what do you think?
Btw, if you want to see super-optimised Python code - often the shortest solution - check out the solutions by zelevin. Lots to learn there what is possible with Python ...
Thanks, Mathias. This genuinely means a lot to yours truly.
in a thread that is limited to people who have already solved this problem. Rodion, what do you think?
Oh, Mathias :) Why asking me :) Honestly while I think it is pretty correct way, I feel it is a bit confusing due to poor forum organization here... Let me drop a link:
Here Mathias explains logic behind "Village Ways" problem
(meanwhile I'll try to proceed with the chore of uniting forum branches visibly... not sure it was ever necessary)
And let's put here a link to solution by colleague zelevin for easy access :)
Thanks, Rodion! I do personally consider Mathias' solution for the same problem to be more elegant.
Slightly off topic: I am genuinely curious what people consider their favourite own solution here on CodeAbbey. It could be their solution to a particularly challenging problem, or something where they learnt something new, a clever algorithm, a short solution, and so on. I really like to look at and understand the solutions of others to learn and get inspired.
Obviously don’t post any solutions themselves here.
I make a start: one-line Python code for #33 Parity Control.
I make a start:
perhaps you'd better prefer to start new thread with dedicated title (e.g. like "what's your favorite solution") - if you would like we then can even add a link to that thread to annoying banners popping up in the top-right, so people may add here something by and by :)
As about one-liners - while I feel awe looking at yours or Zelevin's sources - I'd say in general life we prefer to write clear, not clever :)
But you definitely may like to check solutions by One_liner!