Problem 137 Shannon-Fano coding

Ok, this one trips me.

I get the codes alright, however the checker always has the following disagreement, or something similar along these lines, no matter what the input data

Example, with input data

questioning and rather startled gaze. doubt as to my conduct would bring the matter to an end." "'What then?' I asked. well to follow them when up the lane came a neat little landau, London--quite so! Your Majesty, as I understand, became entangled mark of nitrate of silver upon his right forefinger, and a bulge

My answer is

32 OOO 101 OOI 116 OIO 97 OIIO 110 OIII 111 IOOO 114 IOIO 100 IOOIO 108 IOOII 117 IOIIO 105 IOIII 115 IIOOO 104 IIOOI 103 IIOIOO 109 IIOIOI 102 IIOIIO 44 IIOIII 98 IIIOOO 99 IIIOOI 119 IIIOIO 46 IIIOIIO 45 IIIIOOO 73 IIIIOOI 107 IIIIOIO 121 IIIIIOO 34 IIIOIIIO 39 IIIOIIII 112 IIIIOIIO 113 IIIIOIII 33 IIIIIOIO 77 IIIIIIOO 106 IIIIIIIO 63 IIIIIOIIO 76 IIIIIOIII 87 IIIIIIOIO 89 IIIIIIOII 118 IIIIIIIIO 122 IIIIIIIII

And the expected answer is

32 OOO 101 OOI 116 OIO 97 OIIO 110 OIII 111 IOOO 100 IOOIO 108 IOOII 114 IOIO 117 IOIIO 105 IOIII 115 IIOOO 104 IIOOI 103 IIOIOO 109 IIOIOI 102 IIOIIO 44 IIOIII 98 IIIOOO 99 IIIOOI 119 IIIOIO 46 IIIOIIO 34 IIIOIIIO 39 IIIOIIII 45 IIIIOOO 73 IIIIOOI 107 IIIIOIO 112 IIIIOIIO 113 IIIIOIII 121 IIIIIOO 33 IIIIIOIO 63 IIIIIOIIO 76 IIIIIOIII 77 IIIIIIOO 87 IIIIIIOIO 89 IIIIIIOII 106 IIIIIIIO 118 IIIIIIIIO 122 IIIIIIIII

Reading closely you will see that while I get the codes right, there are triplets like "100 IOOIO 108 IOOII 114 IOIO" or longer sequences later on (usually triplets) where the codes match but their sequence is altered.

My code works by working every depth level, so first it will return all -if any- codes with 0 or 1, then all codes with two digits, then all with three, etc etc, until they are depleted.

The checker presents me with a solution where 2 codes of depth 5 (100 and 108) are expected before a code of depth 4 (114). I don't get the logic behind that, in order to replicate it, and besides, it isn't a prerequisite of the problem, as I understand it. I have the codes alright. So, what am I to do here?

output the results in the same order as the letters were sorted during the algorithm.

And that's what I should have paid attention to. Thanks for the clarification, I should have read more carefully. It was an easy fix after that.

As for Mathematica, while indeed proprietary and quite pricey, it comes bundled with the Rasbian OS for free (for personal use, as I recall), since 2013 and it is kept updated by Wolfram Research to this day!
Here is the first announcement, in 2013

Some might complain that it's closed source, a commercial product through and through, and I would agree that the price barrier is what keeps it from the hands of most people, especially since most programmers expect access to all languages to be free. Plus it ties me to a Raspberry Pi. However, it's a fantastic tool, with a great logic behind it, and I enjoy using it.

Perhaps this might help you if you want to, as an experienced programmer, understand what's what regarding the syntax
Fast introduction for programmers

I can't really know what's up with their website. What I have done for a time, while away from home and in my early steps, was to go to Wolfram Programming Lab and type some basic stuff, though that also works in a kind of demo mode, for a limited number of inputs. Then I realised that my always on Pi desktop, where my development enviroment was ready to go, was just an ssh session away. I had Putty an RealVNC viewer all set up, and connecting would take less than a minute. So I may be bound to the Pi for programming but it's not unusual at all that I use it via VNC from my x86 machines, inside or outside of my local network. In fact, RealVNC is another example of a company that has embraced the Raspbbery Pi Foundation's educational purpose by providing proprietary software (the VNC server) for free, and I love it. It works really well.

As for adoption, I think it was a smart move on Wolfram's part to allow Pi users to just have Mathematica available, so that the next generation of developers come to know it and use it. It really shines in labs and research centers the way I hear it, but not many places elsewhere. Not many can afford the 300$ per year just to try out something new. That said, I would see it used from time to time on Project Euler, but I guess that's a different crowd, more math oriented, perhaps from academic background or related vocation, so with access to the tool somehow. Suffice it to say though that since been introduced to your site I have vastly expanded my knowledge of both the language and algorithms in general, thanks to the variety of problems, not just in the narrow spec of math.

You can certainly get my opinion on related topics in the future, though I doubt I would be very helpful in comparison situations. I haven't really used Python for anything. I actually found it quite boring on occasions when I attempted to start learning it. The only language I really know and use is Mathematica. I was drawn to it because of -among other qualities- the functional programming style that made me write meaningful and clean, yet compact code. What I could tell you then, if asked about anything, is how I would implement it in the language I know, which is pretty much what I've been doing these past couple of years. I am presently attempting to learn Haskell since: a) it works everywhere and b) they share quite a few underlying principles, but that's going slow so far.

So yeah, if you have the time and the will to give Mathematica a go, use that dusty Raspberry Pi of yours via VNC (Pi 3 or 4 would be preferable for acceptable Notebook responsiveness). Wolfram's Elementary introduction, which I wholeheartedly recommend, lays down all the basics, though a seasoned programmer will probably find it too elementary. Then there's always the little snippets of gold over at Mathematica Stack Exchange.

for example your "Primes generation" is really not a solution, as it simply uses built-in Prime[...] function.

Busted :D

I agree with all your points, but I believe some background information is important. I am not a professional programmer, and closing to 40 it's unlikely programming will become a profession for me. I've been seeing listings though since the 8-bit days, and I always wondered how it all works. I didn't have access to a computer when it mattered for turning my interest into a job, nor information on languages, books etc. Nowadays, the sky is the limit. This, solving problems in Project Euler, Codeabbey and the likes, is a hobby for me, and a very rewarding one. I love that little rush of dopamine you get when especially after a tricky problem and many days of thinking and trying you get to see the green letters saying you're correct. (I opened a bottle of wine after Necklace Count, honestly!) So, for me the "job" that needs to be done is just that, getting the results right and climbing one more step up the abbey hierarchy :)

I will also admit that I've used the Prime[] function in Project Euler, in one of those early problems. I was even very excited that I had this awesome programming language with all the ready functions that would solve all the problems automatically in a breeze! Those other suckers have no idea! It didn't take too long for that illusion to dissolve, mind you. That said, I don't agree with reinventing the wheel. I think it's just another impractical fantasy. If there is infrastracture in place, you can be certain I'm going to use it, to move forward, if that's appropriate for the given task and serves my purpose. Same way I use the Sort[] function in Mathematica I would use the ready sort() function in Python. Sure, I have access to the source in the latter, and I can see the implementation. Do I need to sort a billion entries for database work? Perhaps I will have to dig deeper. Sorting for a codeabbey problem? Yeah, the built-in function at hand will do the trick, probably. And if not, then we study, watch youtube lectures, and try again, with a new method.

Working through the problems in your site has helped me build confidence in my self, learn the particular tool I use better, but also expand my knowledge into learning algorithms, acquiring language-independent knowledge, which I guess is your ultimately goal through this site. You can be certain it works, definitely if one wants to progress to problems 100 onward, assuming one works through them in numerical order, independent of difficulty based on solvers. I had skipped Paths in the Grid, and Sweet Harvest, because I couldn't work out the dynamic-programming approach, and when I got to Levenshtein Distance, I considered it low hanging fruit having a built-in function. I went for it. Is it cheating? In a way, I guess. There came a time later on, when I read -and watched- more about dynamic programming, came back and solved what held me back. I got a book on algorithms, an introduction by Thomas Cormen, and read all about sorting algorithms, their pros and cons. Fascinating stuff! Also, quite mind-blowing how one could come up with some of those approaches! Does that mean I will stop using the built in sorting function to solve problems? Definitely not, unless, like I said, niche case.

So you may try spending few minutes to implement typical "trial division" algorithm. What I'm curious about is: how elegant or clumsy it will look (there are two nested loops with couple of break conditions in the innner one) how fast it works, say, for 199999 or for million-th number.

Learing algorithms for finding primes is to this day in my to-do list. I'm here because I like knowing things, and because I enjoy a good puzzle as much as anyone, though I'm definitely no genious. So I can definitely try, and be back with my approach and results.

So, in order to satisfy your curiosity, here is a quick and dirty implementation of the trial division algorithm, a primality test for a single integer

primeTest[number_Integer?(# >= 2 &)] := 
 Catch@If[NestWhile[
     Module[{},If[Divisible[number, #] == True, Throw[False]]; # + 1] &, 
     2, # <= Floor[Sqrt[number]] &] > 0, True]

I suppose it doesn't look very readable at first glance, I assure you it is when you get familiar with it, and all it really says is that for given number n cycle through integers 2 to sqrt(n) one by one, and if a divisor is found break out of the loop and return False as output. If not the final output will be sqrt(n), or closest Integer, thus the function will conclude the number is prime.

If I call this function with

primeTest@199999 // RepeatedTiming

I get {0.0193, True}. The first is the average time in seconds over multiple executions of the same function.

For n=1000000 it's {0.0000465, False} and for n=1000001 it's {0.0062, False}. I guess it has to do with the fact that the sqrt of 1000000 is much easier to calculate than with the other two.

But if I get it right, this is different thing - your function just tests if given number is prime - not searches for the N-th prime?

Yeah, I realized what you were asking for after revisiting problem 61. So I gave a go at trial division, like so

knownPrimes = {2, 3, 5};

Clear[trialDivision]
trialDivision[number_Integer] := 
 Which[Divisible[number, 5] == True, Nothing, 1 == 1, 
  Catch@Table[
     If[Divisible[number, i] == True, Throw[Nothing], Nothing], {i, 
      TakeWhile[knownPrimes, # <= Sqrt[number] &]}] // 
   If[# === {}, number, #] &]

Clear[primeNoX]
primeNoX[number_Integer] := 
 Which[number <= Length@knownPrimes, Extract[knownPrimes, {number}], 
  1 == 1, (NestWhile[
    Module[{}, AppendTo[knownPrimes, trialDivision[#]]; # + 2] &, 
    Last[knownPrimes] + 2, Length@knownPrimes < number &]; 
   Last@knownPrimes)]

A quick explanation. The trialDivision function checks the given number for divisibility against already found primes, stored in the knownPrimes list, and returns the number if it's a prime or nothing otherwise. The primeNoX function loops until the nth prime is found, if it's not in the list already. Is this a bad implementation? Probably, because it took ~14 hours to get to the 199999th prime (2750131 - I ran "primeNoX@199999 // AbsoluteTiming"). And there I was thinking that checking only against primes would save time.

By the way, the built-in Prime[199999] took a fraction of a milisecond, which looks suspiciously like pulling the result from a precomputed list. I mean, come on, is there really an algorithm that fast?

So you may try spending few minutes to implement typical "trial division" algorithm

Ha! If only it were a few minutes :) Depending on my spare time I'll try the sieve of Eratosthenes, though that seems more complicated...

Anyway, the code is here to satisfy your curiosity, as requested, not to act as an exemplary piece of algorithm implementation. Thanks for your replies!

Thanks for that enlightening insight into how a real programmer would think. I followed your suggestions and tried a couple of different things. Most notably, I worked with Block[] and a constant array as it really does make a world of difference, but other than that, I ditched calling a separate function, just in case it caused overhead. So, I ended up with just one function, although the result is not as readable for my taste. Also, I gained a slight increase by calculating the root of the number just once for every number. Plus I gained a small but sizeable speed gain from coverting the root to Integer with Floor[], since comparing every time to a Float or worse a symbolic representation is expensive. All in all, calling primeNoX@199999 took "just" 570 seconds, which is loads better than 14 hours, but still a far cry from a second as described in Problem #61. I will paste the code and call it quits. I sincerely can't think of anything at this point that could make my implementation faster.

primeNoX[number_Integer] := 
 Block[{knownPrimes = ConstantArray[10^5, number], arrayPointer = 3, 
   primePointer = 1, currentNumber = 5, isPrime = True}, 
  knownPrimes[[1]] = 2; knownPrimes[[2]] = 3; 
  While[arrayPointer <= number,
   Block[{root = Floor@Sqrt[currentNumber]}, 
    While[knownPrimes[[primePointer]] <= root, 
     Which[Divisible[currentNumber, knownPrimes[[primePointer]]] == 
       True, isPrime = False; Break[],
      1 == 1, primePointer++]]];
   If[isPrime == False, isPrime = True; 
    currentNumber = currentNumber + 2; primePointer = 1,
    knownPrimes[[arrayPointer]] = currentNumber; primePointer = 1; 
    currentNumber = currentNumber + 2; arrayPointer++]]; 
  Last@knownPrimes]

I would be very happy with this final piece of code if I had to use it to solve Problem #61. I would still try to explain how others might need just a second to find the solution, however I would not have called five minutes of execution time unreasonable for solving the problem. The Raspberry Pi 4 is slower than a desktop PC but not 500 times slower. Maybe Mathematica is just more convenient with all it's bells and whistles than it is fast. Plus it's interpreted