#!/usr/bin/env python3 from itertools import combinations import sys lines = set() vertex = set() if len(sys.argv) != 2: sys.exit('Usage: %s INPUT_FILE' % (sys.argv, )) try: with open(sys.argv, 'r') as stream: for input_line in stream: if not input_line.startswith('#'): drawing_line = tuple(input_line.split()) if len(drawing_line) > 0: lines.add(drawing_line) except (IOError, OSError): sys.exit('ERROR: unable to read input file') for l in lines: vertex.update(set(l)) def tuple_in_line(t, lines): return any(all(e in l for e in t) for l in lines) def valid_triangle(trio, lines): return (all(tuple_in_line(pair, lines) for pair in combinations(trio, 2)) and (not tuple_in_line(trio, lines))) triangles =  for trio in combinations(vertex, 3): trio = sorted(trio) if valid_triangle(trio, lines): triangles.append(trio) for t in sorted(triangles): print(' '.join(t)) print('Total: %s' % (len(triangles), ))
It’s been a while since my previous long post. Apart from “routine” tasks like watching my son grow, taking pictures of him and working in my day job, the lack of content is simply explained because, apart from keeping my Fedora installation up-to-date and making sure my personal data is properly backed up, almost all the time I’ve spent at the desk of my home computer during the last two months has been playing The Witcher 1, 2 and 3 in succession, in what has been an incredible gaming journey. It’s hard to sum it up but I’ll try.
The Witcher game series revolves around the adventures of Geralt of Rivia, a so-called witcher in a medieval fantasy world. I’ll tell you soon what a witcher is. The lore and universe background is revealed step by step as you advance in the games and I don’t find it easy to explain in a few words to anyone asking me what the games are about.
The games take place in a fictional world that had been inhabited by elves, dwarfs and gnomes until a phenomenon called “The Conjunction of the Spheres” took place several centuries in the fictional past. When that happened, beings from other “worlds” (universes or planets, it’s not clear nor important) were magically and accidentally transported between these worlds and mixed up. Humans and other beings ended up in the game world when this happened. These other beings are mainly “monsters”. Think of them like animals and creatures from different worlds, with some of them being rational and very powerful, like higher-order vampires.
At some point in time, monsters had become so problematic and threatening that some humans decided to use alchemy, magic and training to create witcher schools. Places were, without spoiling the plot too much, humans are trained and mutated to gain superhuman abilities (far from superhero abilities) allowing them to fight monsters effectively. When they complete training, they travel the world accepting contracts on killing monsters, becoming professional monster-slayers. For that, they can count on their superhuman abilities and senses, a vast knowledge on many types of monsters, a set of armor, a steel sword, a silver sword and basic notions on magic and alchemy. And that’s what a witcher is and what Geralt of Rivia is: a professional monster slayer from the school of the wolf.
With that starting point, the trilogy follows chronologically and the game plots usually touch on politics, war, romance and, of course, killing monsters. Gameplay-wise they are real-time RPGs played in third-person view.
The first game was released in 2007 and it’s a bit different from the other two. It’s probably the worst game in the trilogy but it’s still, in my opinion, a nice game. It serves as a good introduction to several characters in the game world, including Geralt and Triss Merigold, but it does have some rough edges and aspects that were improved or completely changed in later games.
Combat, for example, is radically different in this first installment. Geralt cannot jump or dodge attacks explicitly, and combat revolves around choosing a combat style (fast, strong or group depending on the type of enemy and situation) and clicking on an enemy so that Geralt gets close to it and starts attacking. Attacks are not based on button mashing, but on resisting that urge and waiting for Geralt to complete an attack movement. At that moment, the on-screen cursor will change shape for a second or two indicating you can click once again to chain a second attack creating a combo. As you progress through the game and level up, you acquire talent points that can be spent in a talent tree to learn new abilities. Some of those abilities add a third, fourth or fifth attack that can be chained to form longer combos with increasing damage output. Others improve your chances of dodging and parrying enemy attacks, which happens automatically as I said before, or improve your chances of causing special effects on the enemy like stunning them, making them bleed or knocking them back.
With that in mind, combat in The Witcher quickly becomes a real-time game of numbers: choosing the proper enemy to attack, choosing the right style, drinking the right potion or coating your blade with the right oil to maximize damage, while spending points on useful abilities. Sure, positioning yourself properly in the battlefield is important, as is fleeing away to recover health when you’re hit hard, but those are secondary aspects.
As I mentioned previously, the game has some rough edges. For example, the talent-acquiring system divides talents in three categories: bronze, silver and gold. Normally, acquiring a silver-talented ability requires having developed a previous bronze-talented ability, and the same goes for silver and gold. When you first level up, you are only given bronze talent points to spend. As you progress and keep leveling up, the mix of talent points varies. It’s a way a bit too complicated of forcing you to decide where to spend points, knowing you’ll eventually run out of bronze talent points to spend and get yourself locked out of certain parts of the ability tree.
Another rough edge is the unclear way some game mechanisms work. For example, the way silver swords are crafted. To craft a silver sword, 3 runes of the same or different types must be combined, resulting in swords with different stats depending on the rune combination. After you craft it, the crafted sword will be placed in the silver sword slot in your inventory, replacing whichever sword you had there. The original sword is lost, giving you the impression your sword is modified with the runes instead of the new sword being created from scratch. As a player, you may also wonder if the base sword you’re using (none in reality) plays a part in the stats of the new sword that has been created. The mechanism for steel swords is different, which only adds to the confusion.
But, perhaps, the roughest edge is the way quests and chapters work. The game is divided into chapters, with each chapter taking place in a different “map”. If you progress too much in the main quests, the chapter will end and action will move to the next chapter with no possibility of going back to the previous area. There’s no warning to the player this is about to happen, and it happened to me in the first chapter making me leave many side quests unfinished. Also related, your inventory space is limited but extra items can be stored in an unlimited storage area that’s normally accessible at taverns and inns, teleporting with you between chapters. In the final and decisive chapter, with no previous warning and only small dialogue hints, you’re only given access to the storage space right before the main action starts, leaving possibly valuable potions, oils and other items unused. You may have been accumulating them for the duration of the game with the goal of using them in a possibly harder final chapter or battle.
Despite those rough points and other minor ones like some boss fights being noticeably more difficult than others, or the lack of some proper transitions between game action and cutscenes that sometimes make them surprising and disconcerting, playing The Witcher is quite fun. In technical aspects the game is not remarkable but the gameplay is solid. If you press me to give it a score, I’d say it’s about an 8 and, if you plan on playing any The Witcher games, you won’t waste your time trying this first one.
The Witcher 2
The second game is a direct sequel taking place mere weeks or months after the ending of the first one. It was first published in 2011 and it’s a very different game, which can be appreciated in both the gameplay and graphics. Visually, The Witcher 2 is a huge improvement over its predecessor and thanks to its high-quality textures, geometry and effects it has aged very well, in my opinion. The game has a nice plot with well-developed characters and a much more intense focus on the game world politics and fights for power, but without abandoning romance and monster-slaying elements at all.
Every rough point in the first game has been fixed and polished. The game is still divided in chapters, with each chapter taking place in a different area. But, this time, you get a proper warning when each chapter is about to finish or an important event is about to happen that may affect your ability to complete secondary quests. The are less chapters and areas but they’re more varied and beautiful. The crafting mechanism is improved and every gameplay aspect related to it is now perfectly clear to the player.
Each time you level up you’re given a point you can spend in the abilities tree, to improve an ability you already have or to gain a new one. This is a much simpler mechanism compared to the first game and more in-line with what other games do. A level cap forces you to choose only part of the tree instead of being able to develop every ability.
Talking about level caps and sidetracking for a moment, many games have them but they’re not written explicitly and I don’t really know why. For example, The Witcher 2 has a level cap of 35. I don’t think it’s a bad idea to give this information to the player in advance. When your current level is reported in a screen somewhere, the game could report it as level X/35, for example.
Combat mechanics change completely compared to the first game, and The Witcher 2 is a proper action game in that aspect now. Geralt still can’t jump, nor fall from edges, but he can dodge by performing a roll, perform fast or strong attacks with different buttons and a single button press roughly corresponds to a slash, so you know have almost complete control over the physical behavior of Geralt. The combat mechanics are more similar to other games like the Batman Arkham series or Dark Souls. If I had to choose the best controls of the trilogy, I’d choose this game. They’re responsive, action based, the movement set is varied enough and Geralt’s behavior is almost always what I expect. I only miss being able to jump, but it doesn’t bother me much.
Compared to the first game, inventory space is now replaced by a weight limit and, just like in its predecessor, managing this restriction is a frequent task, but not too burdensome. The teleporting storage mechanism makes a comeback and allows you to save interesting items for later use if you don’t want to sell them.
Another similarity to the first game is the way equipment improves. It’s not directly related to your level but to the area you’re currently at. New areas introduce more powerful items and equipment, inside treasure chests or as recipes that can be found or bought. Some of those recipes are expensive or require crafting elements that can only be obtained after completing a given secondary or main quest. It’s nice and balanced. Your improved equipment, and abilities as you level up, are matched, to maintain some balance, with new types of powerful monsters or larger groups of them. Monsters don’t have a visible level and equipment doesn’t have level requirements either. I think it’s a mechanism that works quite well in practice.
If the first game was an 8, The Witcher 2 is a nice improvement and I’d easily give it a score of 8.5 or 9. Totally recommended as it also introduces more characters and events that will play a major part in The Witcher 3.
The Witcher 3
The Witcher 3 is, again, a sequel to The Witcher 2 taking place a few months after the end of the second game. What can I say about The Witcher 3 that hasn’t been said before? Not much. The Witcher 3 is a superb game and, while not perfect, to me it’s easily a 9.5. Huge, long, detailed, it feels as if The Witcher 1 and 2 were mere steps in raising up enough money to be able to put it to work in such a magnificent title. The Witcher 3 is, no doubt, the witcher game CD Projekt RED wanted to create since the beginning, the best goodbye you could imagine for Geralt, and everything you could hope for in a witcher game.
Visually it’s simply impressive. You only have to find any videos online to see how it looks, with the grass and trees moving in the wind. I sometimes found myself stopping for a moment at the top of a hill and taking a few seconds to observe the view. I distinctly remember the first time I had to go to Oxenfurt, the second biggest city in the game, and emerging from behind a small hill to a view of the city from above, that only got better as I crossed an elevated bridge to cross the city walls while I observed its port below. Many screenshots have been taken from the incredibly beautiful region of Toussaint in its Blood and Wine expansion, but my favorite location are actually the Skellige isles with its coastal villages, its mountains and cliffs, clear water and snow. You can almost feel the cold when it snows and smell the salt when you’re on a beach. And, when I enter a big city or watch NPCs living in a small town somewhere, all following their routines, technology limits non withstanding, I feel it’s the most “alive” universe I’ve experienced in a video game.
So enough daydreaming. Gameplay is amazing. The story is long and good, and most major characters, both old and new, are very well developed. The biggest change from previous installments resides in what leveling up implies. You, again, gain points that you can invest in a “tree” of abilities but now enemies also have a level, and equipment has a level requirement with a direct influence in its stats, such as protection or damage dealt. Equipment does not level up with you and has to be switched for better gear as you advance in the game if you want to survive without problems. This is similar to Borderlands, to name the first title that comes to my mind with similar mechanics. I must recognize I don’t particularly like them but I concede it’s fair and it works perfectly.
Sidetracking again, I like the Dark Souls way better. In it, your character has points in different abilities and weapons scale with some of those abilities. So as you level up, the weapon levels up with you. In addition, you can upgrade your weapon by modifying it and that improves both its base damage as well as its damage scaling. However, I understand such a mechanism is more important in that game because each weapon has a different move set and mastering a weapon takes some effort, while in The Witcher 3, all swords are handled the same and your move set and timings don’t change.
The weight limit carries over from The Witcher 2 but it’s been relaxed a bit and not every item has weight. The storage area is also back and works the same.
The second major change is that, despite the game story progressing in chapters or acts like its predecessors, with some of them taking place mostly in a specific area, you can always go back to previous areas and travel between zones. Maps can be so large that a fast-travel mechanism has been implemented allowing you to travel between designed locations. You can also travel on horseback and sail on a boat.
The crafting mechanism has been improved, augmented and expanded, with the possibility of dismantling items to obtain lesser ingredients or removing upgrades from weapons. Finally, the mini-game changes from dice poker to Gwent, a not-so-simple but incredibly fun card game with collectible cards.
Geralt can now also swim, jump and dodge hits in addition to rolling away, or even shoot a crossbow. For the first time I felt my 3-button wheeled mouse and keyboard were lacking keys to bind to the vast array of possible actions. That’s why I said I actually prefer the controls from The Witcher 2, even with the restricted action set. Geralt’s response to input was altered again in this sequel and, after a few user complaints, an “alternative” movement mode was added to the options menu, making the feel closer to the second game. If you play The Witcher 3 right after The Witcher 2, you’ll probably like the alternative movement mode, so don’t forget to try it out. Just to nitpick, sometimes the way Geralt moves feels a bit robotic and unnatural, specially when jumping.
But those are, like I said, minor faults that barely diminish the quality of a superb game. I’m a completionist and a slow player, and I spent around 200 hours playing The Witcher 3 and its expansions, “Hearts of Stone” and “Blood and Wine”. It does feel like a journey, specially after playing its two previous installments, and I felt sad it was over but too exhausted, in a good way, to tackle “new game plus”. I highly recommend playing the trilogy and savoring it like a fine bottle of Sangreal from Toussaint.
Time to close the review. Wind’s howling.
How many triangles can you see in this image? It is said that only those with IQ 120 or above can find 18 triangles pic.twitter.com/dDPpzk0L3B— People's Daily,China (@PDChina) December 7, 2016
Apart from the bogus IQ statement, it offered me the chance to revisit my old piece of code that brute-forced the problem easily with a few lines of code thanks to the amazing speed of computers today.
I reworked the code by using
itertools.combinations instead of custom code,
removing a lot of boilerplate and improving the code in general and using Python
3 instead of Python 2. The result, in the public domain as the previous ones:
If problems were larger, we could generate graphs with all existing 2-vertex and 3-vertex connections beforehand and enumerate triangles using that knowledge instead of just brute-forcing the problem by generating all possible triangles and checking if they’re valid for the given drawing.
Reminder: to input data to the program you need to enumerate every vertex in the image by hand (a vertex is any point where two or more lines meet) and finally list the lines in the drawing, one per input line as a list of vertex separated by spaces. If in doubt, read my two previous posts on the problem.
In the Twitter image, like other replies said, there are actually 24 triangles.
Just a quick post to say I upgraded to Fedora 25 a couple of weeks ago. The process was painless and nothing major broke for me. When booting, I get the following error on the console and, I suppose due to it, the bootsplash screen is not used.
ERROR: Unable to locate IOAPIC for GSI 37
If you get a similar error, many web searches return outdated information for messages like that one happening several years ago. The only relevant result I found was a thread in the Arch Linux forums. The error seems completely harmless otherwise and a fix has been committed for Linux 4.9. Kernel 4.9 hasn’t been officially released yet as of the time I’m writing this, and Fedora will typically take some weeks to ship it after it’s released, so in the mean time I’ll have to live with the error message.
A few days ago we had a perplexing bug in my day job that turned out to be related to a classic C++ problem with #include directives. Hopefully, C++ modules will solve part of the mess that are #include directives, but no official specification exists yet and they didn’t make it into C++17.
One of the classic questions of #include directives is: what is the difference between an #include directive using double quotes and one using angles? The C standard mentions headers using angles may not be implemented as actual files. For example, there’s no need for a cstdio file to exist when someone uses #include <cstdio>. Double quotes, OTOH, refer to files, and in both cases the implementation is free to choose how to do a lot of things. In practice, different compilers do things differently. From now on, I’ll be talking about Unix systems and GCC/Clang.
GCC and Clang both do a very simple thing. Most standard headers (every single one?) are actual files that exist on disk. The difference between double quotes and angles is that double quotes make the preprocessor look for the file first in the same directory the source file including it is located. If not found, with both angles and double quotes, the compiler proceeds to search for those headers in the list of directories passed using the -I flag. If it’s still not found, a list of standard system directories is used.
Combining the theory and practice above, some people use angles for every standard or system header, and quotes for every “user header” that belongs to the project they’re building, even if the included header is not in the same directory as the source file. Other people like myself prefer to use double quotes when the file is actually in the same directory as the source file including it, probably meaning the header belongs to the same module. Headers belonging to other modules, even if local to the project, are included using angles and passing the corresponding -I option to the compiler that would be needed in any case. Of course, there’s people that don’t fall inside of either camp.
A second typical questions would be: is there any difference between using angles and passing the current directory (dot) using -I., and using quotes without passing the -I option? Yes there is, when the file you’re compiling is not in the directory you’re calling the compiler from. In that case, angles combined with -I. will search for the header in the directory you’re calling the compiler from (the current working directory), while double quotes will make the preprocessor search for the header in the source file directory. For example, imagine the following hierarchy:
header.h subdir/main.c subdir/header.h
When compiling subdir/main.c from the base directory, if subdir/main.c uses #include <header.h> and you pass the -I. option, header.h, in the base directory, will be included. If subdir/main.c uses #include "header.h", subdir/header.h will be included instead.
Subtle but important. A small part of our build system used an auxiliary tool that generated a temporary file in /tmp, and ran the preprocessor on it. When that temporary file used #include directives with double quotes, the included file was searched for in /tmp first. Normally, it didn’t exist there. But one day it did because someone had put a temporary copy in /tmp to do some tests. The included file had outdated contents in /tmp and, furthermore, everything happened to compile and build just fine. Problems only appeared in runtime and it was very hard to find out what was happening because the original source code didn’t match what was being compiled into the binary. It took us a whole day and the solution, in our case, involved using a temporary directory inside /tmp instead of creating the temporary files directly there.
It’s been a long time since my last post, so here’s a new one to tell you I switched graphics cards from a GTX 760 to a GTX 1070.
All started when NVIDIA launched their first Pascal cards back at the start of this past summer. I was pretty serious about getting the amazing GTX 1070 (as powerful as the previous GTX 980ti, nonetheless!) once aftermarket cards became available and AMD had released their Polaris cards too, which I hoped would bring NVIDIA prices down a bit. Taking into account VAT, import taxes and everything, I was hoping GTX 1070 cards would be available for 400-ish euros. Around 410 or 420 was what I expected and the lower the better, of course.
I had never owned a card that expensive, but I thought the improvements this generation brought were worth it. I also planned to sell my old card on eBay to cover some costs (which I did, for around 75 euros). When the time came, the cards were much more expensive (they still are) and it seemed everybody was short on stock permanently. Prices were actually closer to 500 euros in many cases, at least in Spain, with some specific cards going over that figure.
Time passed and AMD released their RX480 cards, while NVIDIA released the GTX 1060 model to compete with them. Both were much more affordable while being incredibly powerful too. A GTX 1060 has similar performance to a GTX 980. RX480 cards had mixed performance. In many interesting old DX11 games performance was below a GTX 1060 and closer to a GTX 970 (which is still not bad at all). In some DX11 titles performance was more or less the same. In a few selected DX11 and most DX12 and Vulkan games performance was clearly superior to a GTX 1060 and closer to the GTX 1070.
So at the end of the summer I had the same doubt many other gamers were having, from what I’ve been reading: pondering if I should go for the RX480 (8GB version) or the GTX 1060 (6GB version). In Spain both cards were priced similarly with some stores having cheaper 1060 cards and others having cheaper RX480 cards, with both being no more than 20 euros apart. I read a lot about async compute, the state of Linux drivers, DX12, Vulkan, DX11 drivers, etc. My take from everything I read? NVIDIA, for all practical purposes, supports async compute even if their solution relies a bit more on software than hardware at this point. We still need more samples from games and comparisons are not totally fair at the time I’m writing this.
For example, Vulkan is noticeably faster in Doom using a GTX 1070, but only when the frame rate is incredibly high and you start to be constrained by CPU performance. Back to the RX480 and GTX 1060, OpenGL performance with NVIDIA drivers was already stellar, so it’s harder to notice the difference. Vulkan performance also improved when NVIDIA released new drivers with support for a newer version of the Vulkan API. And Doom still does not support NVIDIA intrinsic shaders while it supports AMD ones, so it’s hard to tell which card is better. Games implementing DX12 so far have been problematic too, with many of them being traditionally AMD-centric or having inferior performance when compared to DX11. Again, hard to compare. Also, NVIDIA cards in general have less compute performance when compared to AMD cards, but more texel performance. In other words, NVIDIA cards should be slower at shaders but noticeably faster at geometry and texturing. It’s hard to find the sweet spot and performance varies from game to game.
I finally reverted back to my initial plan and got a GTX 1070 for several reasons. First off, a decent aftermarket GTX 1070 was temporarily available in Spain for 420 euros for several days, so I took that chance to grab one. I’m going to use it to play a lot of already-released OpenGL or DX11 games, like The Witcher 3, Arkham Knight, Far Cry 4 and Primal, Fallout 4, etc. Support for the card was already available in NVIDIA drivers for Linux, while AMD support has been introduced more slowly, albeit in a better way (kernel version 4.8 was the best choice but was only released for Fedora 24 last week). 3D performance with open source drivers will be much better with Mesa 12.1, but that’s yet to be released officially and pushed to Fedora. Also, a GTX 1070 uses about the same amount of power as an RX480. In that aspect, NVIDIA cards are more efficient.
That’s more or less why I stayed on “Team Green” like I’ve done since the days of Voodoo cards, but I’m not an NVIDIA fan by any means. In general, I’m not a fan of any brand at all, in any market. I don’t look at the brand stickers on the things I buy, but I do mind their performance, features and price. In fact, being a FOSS enthusiast, I can only congratulate AMD for releasing a phenomenal card like the RX480, improving Mesa and getting support for their cards integrated in the Linux kernel as fast as they did. It’s really amazing. I’m crossing my fingers for them and I sincerely hope Zen ends up being a very nice CPU line that brings some needed competition to Intel. And the same goes for Vega cards and NVIDIA. I’ve owned several AMD Athlon processors in the past, and I look forward to building an all-AMD computer in the future with nice FOSS drivers for Linux and very decent drivers for Windows. They’re definitely on the right path as of now and it’s better for everybody if they stay on it.