ejolson
Posts: 3798
Joined: Tue Mar 18, 2014 11:47 am

Re: Tatami Pi Fun.

Tue Dec 03, 2019 8:13 am

jcyr wrote:
Tue Dec 03, 2019 4:33 am
The Tatami problem is not a programming problem. It's more a mathematics or logic problem. The notion that something complicated can be made easily understood with a few comments, or many for that matter, seems a little far fetched and well beyond the scope of what beginners need. A beginner should focus on the syntax and semantics of a language, not the complexities of combinatorial algorithms.

Unless of course the only point is accumulating cabbages.
While cabbage is good, it is also true that a bit of mathematics is needed to determine which rooms are impossible to auspiciously tile. Is that mathematics difficult to work out? I don't really know, because I didn't work it out myself. I drew pictures on paper for about an hour until I found a way to tile 6x10 and 8x10 rooms and thought I understood why the same approach didn't work for a 7x10 room. Then I read Dean Hickerson's note linked to in the post

https://www.raspberrypi.org/forums/view ... 5#p1560632

I don't know if John is still following this thread or not, but if he is, thanks for finding that note. Those pages covered the mathematics so I could proceed directly to the software engineering needed to write an efficient program. It also helped to look at the sample code included in the post

https://www.raspberrypi.org/forums/view ... 5#p1560751

While it sounds good to study syntax and semantics, my personal experience is that I cannot learn any programming language without actually writing a program. Similarly, I find it difficult to compare languages without writing code in both or at least reading code written by others. To keep our discussion of what makes a good first programming language based on fact, we actually write programs. The novelty of writing code to solve problems distinguishes what we do here from educational philosophy and theoretically prevents the eruption of a language war based on emotional attachments. From this point of view it is fortunate that a variety of programming languages and techniques can be used to solve the present challenge.

Although I believe the tatami challenge could be solved by someone who just learned programming, such submissions are notably missing. On the other hand, the entries in Rust were written by someone just learning that language as well as my entry in Visual Basic (for what that's worth). The same is true with Haskell, though the code has yet to be submitted. I've learned surprising things about C--also about profiling, OpenMP, MPI and the characteristics of particular compilers and hardware architectures. I'm a beginner when learning anything new and this forum has encouraged me to learn many new things.

ejolson
Posts: 3798
Joined: Tue Mar 18, 2014 11:47 am

Re: Tatami Pi Fun.

Wed Dec 04, 2019 5:58 am

Heater wrote:
Tue Dec 03, 2019 7:06 am
Unless of course the only point is accumulating cabbages.
That is in fact the entire point of this thread :)
I was looking at the list of suggested programming projects

https://projects.raspberrypi.org/en/projects

created by everyone's favorite computer company to see if there were any ideas that might help in our study of what makes a good first programming language. While Ada's Poetry Generator reminded my of Fido's doggerel project, it also seemed a little misleading about what type of program Ada Countess of Lovelace actually wrote in order that she be considered the first programmer ever.

Rather than random poetry, Ada wrote a program based on logic and mathematics which recursively computed the Bernoulli numbers. In my opinion, the realization that the first computer programmer was not only a woman but a person well versed in mathematical theory and computation acknowledges a role model that could help remove gender biases in science, technology, engineering and mathematics much more effectively than associating the same name with poetry randomly created. The latter association is, in fact, so absurd that if made during the 1800's it might have been considered libel. Indeed, when one studies Ada's poetical science one quickly discovers it was not whimsical or random, but closer to what is today called big-data analytics.

More information about the first non-trivial computer program and how it worked is available at

https://rclab.de/_media/analyticalengin ... k_v1.2.pdf

On another note, it is interesting that the store used in the analytical engine resulted in a variable type which was not easily overwritten. This likely led the Countess of Lovelace to make a particular choice concerning which algorithm to use when generating the Bernoulli numbers. Back on topic, similar considerations might be made by a modern Rust programmer when trying to minimize the number of mut variables in a code that solves tatami challenges.

ejolson
Posts: 3798
Joined: Tue Mar 18, 2014 11:47 am

Re: Tatami Pi Fun.

Wed Dec 04, 2019 7:27 pm

ejolson wrote:
Tue Dec 03, 2019 8:13 am
While cabbage is good, it is also true that a bit of mathematics is needed to determine which rooms are impossible to auspiciously tile.
Fido has been busy trying to get some more cabbages to grow in the snow. This task would appear difficult due to the lack of new tatami-challenge submissions. Fortunately there are no deadlines. In fact, programs which compute really big Fibonacci numbers and programs which find anagrams in the insane British dictionary are also welcome. In all cases, the corresponding charts will be updated, but only in the case of finding rectangles of the same area which do not admit tatami tilings will cabbage be awarded.

While waiting for the cabbage to grow I decided to read issue 88 of the MagPi. What attracted my attention was the feature article about retro computing. In particular, I wanted to know what to do with an emulated pet or even a real one. The article focused on emulating the ZX Spectrum but happily pointed to a complete archive of Ahoy! magazine for Commodore computers. As there was no sign of even a Brussels sprout poking through the snow, I clicked on the link to see what sort of peek and poke madness might lie in the premier issue of Ahoy!

Quite amusingly the Commodore 64 was on the front cover--an inexpensive PET replacement that hopefully doesn't eat as many dog treats. After skimming through a nice story on John von Neuman, I randomly clicked again and downloaded issue 16 which included an article on creating your own games complaining about peek and poke with a description on page 61 of what features the perfect home computer should have:
  • Operating system in ROM.
  • Sufficient RAM.
  • Graphics that look good on a TV.
  • Sound for 5-voice polyphony.
  • Built-in BASIC.
  • Fast reliable disk storage.
  • Cartridge slots.
That just sets the stage, however, as the article finished with
Orson Card wrote:The latest fashion in computer theory says that home computers don't have to be programmable anymore. Computer users just want software they can buy and run--they don't want to develop their own programs.

Well, the people who say that are the same people who sneer at BASIC because it's an "unstructured" language--you can do unpretty things with BASIC. You can get a 0 in neatness. What they don't realize is that the computer is supposed to make us free. Like the VCR, which lets us determine our own viewing schedule and even make our own TV programs, the computer is not in my home so that I can have only the programs that some company thinks at least 100,000 people will buy. There are sometimes things that only one person will buy--me. And I, for one, will own a computer that lets me create that program.
Could it be that this 1985 article is the well-spoken start of the liberation-through-computer-literacy movement? I wonder if today Orson has a Pi.
Last edited by ejolson on Wed Dec 04, 2019 8:14 pm, edited 3 times in total.

Heater
Posts: 13866
Joined: Tue Jul 17, 2012 3:02 pm

Re: Tatami Pi Fun.

Wed Dec 04, 2019 7:52 pm

Orson Card (was he a Hollerith or what?) was not quoting "computer theory" there. He was telling how Bill Gates put it https://commons.wikimedia.org/wiki/File ... byists.jpg

Sadly he was a voice lost in the wind as the Personal Computer Winter closed in with the arrival of Windows.

I wonder if he got into Linux when things started to thaw out again?

While mathematics is good it should be remembered that it is totally founded on cabbage and other nutrient providing food stuffs.
Memory in C++ is a leaky abstraction .

User avatar
davidcoton
Posts: 4243
Joined: Mon Sep 01, 2014 2:37 pm
Location: Cambridge, UK

Re: Tatami Pi Fun.

Wed Dec 04, 2019 8:38 pm

Heater wrote:
Wed Dec 04, 2019 7:52 pm
... the Personal Computer Winter closed in with the arrival of Windows.
Personally I recommend closing Windows with the arrival of winter. :roll:
Signature retired

Heater
Posts: 13866
Joined: Tue Jul 17, 2012 3:02 pm

Re: Tatami Pi Fun.

Wed Dec 04, 2019 9:40 pm

Ha, as they used to say "In a world without Windows, who needs Gates?"
Memory in C++ is a leaky abstraction .

Heater
Posts: 13866
Joined: Tue Jul 17, 2012 3:02 pm

Re: Tatami Pi Fun.

Wed Dec 04, 2019 10:39 pm

Tatami results just in....

Code: Select all

prune (.c vs .rs)

On the x86-64 PC
----------------

gcc         -march=native -mtune=native     4m49s

rustc                                       4m58s

On the Pi 3B (64 bit) 
---------------------

gcc         -march=native -mtune=native     21m55s

rustc                                       26m11s
Once again Rust and C are pretty much neck and neck on the PC with Rust falling a bit behind on ARM.

Turns out I forgot to remove the arithmetic overflow checking in Rust. Sometimes you just have to take the safety wheels off.

At least we are in the same cabbage patch.

Code will be forthcoming...
Last edited by Heater on Wed Dec 04, 2019 11:01 pm, edited 1 time in total.
Memory in C++ is a leaky abstraction .

jahboater
Posts: 4826
Joined: Wed Feb 04, 2015 6:38 pm

Re: Tatami Pi Fun.

Wed Dec 04, 2019 10:46 pm

Heater wrote:
Wed Dec 04, 2019 10:39 pm
Turns out I forgot to remove the array bounds checking in Rust. Sometimes you just have to take the safety wheels off.
I thought that was Rust's raison d'être ?
Seems a shame to make it all unsafe and be as bad as C.

Heater
Posts: 13866
Joined: Tue Jul 17, 2012 3:02 pm

Re: Tatami Pi Fun.

Wed Dec 04, 2019 11:08 pm

jahboater,
I thought that was Rust's raison d'être ?
Sorry, I said the wrong thing above. I meant "arithmetic overflow checking". I fixed it.

Whilst we are here....The safety guarantees in Rust are all about memory safety:

No use of uninitialized data.
No use of allocated data after it is freed.
No NULL pointer problems.
No data races between threads.
Etc, etc.

All done through Rusts model of ownership of data, data life time and immutable or mutable "borrowing of data".

All this happens no matter how you build your code, it's a static analysis done at compile time.

As a bonus there is also arithmetic overflow checking. Most of which is probably done at run time. Always enabled for debug builds. Can be optionally enabled for optimized release builds.

I forgot I had left an "overflow-checks = true" statement in my build file.

Durp, durp...

Even with the safety wheels of Rust can never be as bad as C with regard program correctness.
Memory in C++ is a leaky abstraction .

Heater
Posts: 13866
Joined: Tue Jul 17, 2012 3:02 pm

Re: Tatami Pi Fun.

Thu Dec 05, 2019 9:59 am

Yay!

Code: Select all

$ time ./prune
Pr(40000)=479909
T(63405342000)=1000

real    4m43.437s
user    4m43.203s
sys     0m0.016s
$ time target/release/tatami_rust
T(63405342000)=1000

real    4m43.769s
user    4m43.406s
sys     0m0.000s
Memory in C++ is a leaky abstraction .

ejolson
Posts: 3798
Joined: Tue Mar 18, 2014 11:47 am

Re: Tatami Pi Fun.

Thu Dec 05, 2019 3:16 pm

Heater wrote:
Thu Dec 05, 2019 9:59 am
Yay!

Code: Select all

$ time ./prune
Pr(40000)=479909
T(63405342000)=1000

real    4m43.437s
user    4m43.203s
sys     0m0.016s
$ time target/release/tatami_rust
T(63405342000)=1000

real    4m43.769s
user    4m43.406s
sys     0m0.000s
I've got some good news and some bad news. The good news is that the snow had melted and I'm starting to see what looks like a crop of cabbages outside; the bad news is that code may not earn many cabbages in the runtime category.

Heater
Posts: 13866
Joined: Tue Jul 17, 2012 3:02 pm

Re: Tatami Pi Fun.

Thu Dec 05, 2019 3:43 pm

Also runs on Pi 3B 64

Code: Select all

$ time target/release/tatami_rust
T(63405342000)=1000

real    24m46.845s
user    24m46.676s
sys     0m0.026s

$ time ./prune
Pr(40000)=479909
T(63405342000)=1000

real    21m55.181s
user    21m54.967s
sys     0m0.017s
Nothing much changed except cleaning it up to be presentable in public.

I'll settle for sprouts. I like sprouts.
Memory in C++ is a leaky abstraction .

Return to “General programming discussion”