Download Folders from a GitHub Repo using Python (… files, too)

At some point during your life as a programmer, you will end up with the problem of downloading a single folder from a GitHub repository. For me, it was because I had an auxiliary repo containing files relevant to some unit tests. To solve this problem, I found a very elegant (and super easy) solution, which I want to share here today. In other words, this is a short how-to on how to download/copy files and folders from GitHub using python.

The solution uses the awesome fsspec library. fsspec is a pythonic approach to filesystem management, and allows you to use python to access data in various kinds of locations: on your local machine, on all major cloud providers, and – most importantly – on GitHub. There are many more locations, so the library is worth checking out if you have the time.

Installation

To get started, install fsspec. (Chances are you already have it, because increasing parts of the pydata ecosystem use it internally.)

pip install fsspec

Copy a Folders

import fsspec
from pathlib import Path
# flat copy
destination = Path.home() / "test_folder_copy"
destination.mkdir(exist_ok=True, parents=True)
fs = fsspec.filesystem("github", org="githubtraining", repo="hellogitworld")
fs.get(fs.ls("src/"), destination.as_posix())
# recursive copy
destination = Path.home() / "test_recursive_folder_copy"
destination.mkdir(exist_ok=True, parents=True)
fs = fsspec.filesystem("github", org="githubtraining", repo="hellogitworld")
fs.get(fs.ls("src/"), destination.as_posix(), recursive=True)
view raw folder.py hosted with ❤ by GitHub
Example of how to download a folder from GitHub (shallow or recursive).

The above snippet does the following: We first declare a destination (where to store the folder’s content). Then we use fsspec to turn the repo into a pythonic filesystem. Finally, we list all the files in the target folder of the repo (fs.ls(…)) and download them all using fs.get. Simple, elegant, and convenient. I love it!

Copy Files

Copying/Downloading individual files works the same way; however, this time the destination has to be a file.

import fsspec
from pathlib import Path
# download a single file
destination = Path.home() / "downloaded_readme.txt"
fs = fsspec.filesystem("github", org="githubtraining", repo="hellogitworld")
fs.get("README.txt", destination.as_posix())
view raw copy_file.py hosted with ❤ by GitHub
Example of how to download a single file from GitHub.

And that is all there is to it. Happy coding!

Webcam Capture in Python (without OpenCV)

Did you know that there is a python library that allows you to to capture both a webcam stream or a single webcam image? Did you know that this works on every OS? This is what I want to share in this post: A tutorial on how to use imageio to access your webcam on Linux, Windows, or MacOS that works in either a Python script or a Jupyter Notebook. No OpenCV needed 🙂

Before we begin, a caveat for Jupyter: While the notebook is displayed on your current machine, and widgets run locally, your kernel (that runs the python code) may be hosted on a remote server, docker container, virtual machine, … depending on your setup. If this is the case for you, please note that IPython can only access the remote server’s webcam, not your local one.

Installation

pip install imageio[ffmpeg]

Get a single Image/Screenshot

import imageio as iio
import matplotlib.pyplot as plt
camera = iio.get_reader("<video0>")
screenshot = camera.get_data(0)
camera.close()
plt.imshow(screenshot)

Get a Video as a Sequence of Frames

import imageio as iio
import matplotlib.pyplot as plt
import time
camera = iio.get_reader("<video0>")
meta = camera.get_meta_data()
delay = 1/meta["fps"]
for frame_counter in range(15):
frame = camera.get_next_data()
time.sleep(delay)
camera.close()
plt.imshow(frame)

Full example (record a short MP4)

import imageio as iio
import matplotlib.pyplot as plt
import time
camera = iio.get_reader("<video0>")
meta = camera.get_meta_data()
num_frames = 5 * int(meta["fps"])
delay = 1/meta["fps"]
buffer = list()
for frame_counter in range(num_frames):
frame = camera.get_next_data()
buffer.append(frame)
time.sleep(delay)
camera.close()
iio.mimwrite("frames.mp4", buffer, macro_block_size=8, fps=meta["fps"])

That’s it.

If you happen to run into problems, you have three options to ask for help:

  1. Ask a question on StackOverflow and tag it with imageio (I monitor the tag)
  2. Comment on this post
  3. Create a New Issue / Bug Report on GitHub.

Thanks for reading and Happy Coding!

Faster RNG for Reinforcement Learning in Python

When you start doing reinforcement learning you will sooner or later come to the point where you will generate random numbers. Initializing policy networks or Q-tables, choosing between exploration or exploitation, or selecting among equally good actions are a few examples. Numpy is very efficient at generating those random numbers, and most of the time (like 95%) this is all you need. However, there is one particular edge case were numpy is not the best solution, and that is exactly the case we encounter in RL a lot: generating single random numbers (i.e., to select an action epsilon-greedy).

Generating single random numbers in numpy is a bad idea, because every numpy call gets sent to the numpy engine and then back to python, which creates overhead that dominates runtime for single random numbers. In this case it is (much) more efficient to use the python standard library instead. However, if you can generate the random numbers in batches, numpy is significantly faster than the standard library again. Take a look at this simple profile:

import timeit
number = 10000
numpy_time = timeit.timeit("[np.random.rand() for _ in range(int(1e3))]", "import numpy as np", number=number)
random_time = timeit.timeit("[random.random() for _ in range(int(1e3))]", "import random", number=number)
numpy_batch_time = timeit.timeit("np.random.rand(int(1e3))", "import numpy as np", number=number)
print("Timings")
print("=======")
print(f"Numpy Single: {numpy_time:.3f}")
print(f"Random: {random_time:.3f}")
print(f"Numpy Batch: {numpy_batch_time:.3f}")
print("=======")
# =======
# Numpy Single: 3.245
# Random: 1.003
# Numpy Batch: 0.085
# =======
Comparison between ways to generate random numbers

So if you do your profiling your code and notice that RNG adds up to a significant portion of your runtime, consider pre-generating the random numbers in numpy and then save them to a list. This solution sacrifices a bit of readability, but allows for much faster code. Here is an example that mimics the syntax of the python standard library:

import numpy as np
random_numbers = np.random.rand(int(2e8)).tolist()
def random():
try:
return random_numbers.pop()
except IndexError:
raise IndexError("Out of random numbers; generate more next time.")
def randint(a, b):
return int(round((ba) * random())) + a
view raw RandomDropin.py hosted with ❤ by GitHub
Source Code for Random replacement.

That’s it. Thanks for reading and Happy Coding!

Parallelism in Python Generators

Yesterday I stumbled upon a StackOverflow question that asked about implementing a Rosetta Code problem in parallel to speed it up. One easy way to do it is one, which is a modification of the python example on rosettacode.org.

from multiprocessing import Pool, cpu_count
from itertools import islice, count
def is_special(n, d):
tofind = str(d) * d
return tofind in str(d * n ** d)
def superd(d, N=10000):
if d != int(d) or not 2 <= d <= 9:
raise ValueError("argument must be integer from 2 to 9 inclusive")
with Pool(cpu_count() 2) as workers:
for offset in count(0, N):
worker_fn_args = zip(range(offset, offset + N), [d] * N)
is_superd_batch = workers.starmap(is_special, worker_fn_args)
yield from [n+offset for n in range(N) if is_superd_batch[n]]
if __name__ == '__main__':
for d in range(2, 10):
print(f"{d}:", ', '.join(str(n) for n in islice(superd(d), 10)))
view raw superd.py hosted with ❤ by GitHub
Source code for parallelism in generators

When I posted the question the OP commented that he/she was looking for using non-terminal sub-processes that yield these super-d values. I thought about it, but that version does not seem very practical. If the main process is interested in the results of the computation, then temporary concurrency will be the cleaner solution (like in this example). If the main thread isn’t, e.g., if you are running an old-school threaded web-server, that hands off incoming connections to a worker thread, then solutions with non-terminal sub-processes can make sense. In the latter case you are essentially “starting a program N times in parallel and shutting them down together”. This certainly makes sense, but only if those programs don’t need to communicate. Remember to KISS.

Thank you for reading and Happy Coding!

How to play custom animations during speech on a NAO (or Pepper)

I’ve been asked multiple times now how to sync animations and speech on a NAO – or Pepper for that matter; especially from Python.

The answer to that is, there are two options:

  1. The first one is to create the animation in Choreograph and then export it to a python script. You then create your usual handle to the text-to-speech module, but instead of calling the say method directly, e.g., `tts.say(“Hello”)`, you call it through the module’s `post` method, e.g., tts.post.say(“Hello”). This method exists for every function in the API and essentially just makes a non-blocking call. You can then call your animation.
  2. You create a custom animation in Choreograph, upload it to the robot, and call it through AnimatedSay or QiChat. Other than being the, I think, cleaner solution, it allows you more fine grained control over when in the sentence the animation starts and when it should stop. This is what I will describe in more detail below.

Step 1: Create the Animation

timeline

Fairly straight forward, and the same for both solutions. You use Choreograph to create a new Timeline box in which you create the animation that you would like. You then connect the timeline box to the input and output of the behavior and make sure it works as you’d expect when you press the green play button.

Step 2: Configure the Project and Upload it to the Robot

In this step, you configure the new animation to be deployed as an app on the robot.

properties-choreography

Go to the properties of the project.

properties-configured

Then make sure to select a minimum naoqi version (for NAO 2.1, for Pepper 2.5), the supported models (usually any model of either NAO or Pepper respectively) and set the ID of the Application. We will use this when calling the animations, so choose something snappy, yet memorable. Finally, it is always nice to add a small Description.

project_structure

Next, we need to reorganize the app a bit. Create a new folder and name it after your animation; again, we will use this name to call our behavior, so make sure it’s descriptive. Then move the behavior that contains your animation – by default called behavior1.xar – into the folder you just created, and rename it to behavior.xar .

buttons_upload

Finally, connect to your robot and use the first button in the bottom right corner to upload the app you just created to your robot.

Step 3: Use ALAnimatedSpeech from Python

Note: If you don’t want NAO to use the random gestures it typically uses when speaking in animated speech, consider setting the BodyLanguageMode to disabled. You can still play animations, but it won’t automatically start any.

For existing animations – that come with the robot by default – you call the animation like this

"Hello! ^start(animations/Stand/Gestures/Hey_1) Nice to meet you!"

Now, animations is nothing but an app that is installed on the robot. You can even see listed it in the bottom right corner of Choreograph. Inside the app, there are folders for the different stable poses of NAO like Stand, or Sit, which are again divided into types of animations, e.g., Gestures which you can see above. Inside these folders there is, yet another, folder named after the animation (Hey_1), inside of which is a behavior file called behavior.xar.

We have essentially recreated this structure in our own app and installed it right next to the animations app. So, we can call our own animations using the exact same logic:

"Hello! ^start(pacakge_name/animation_name) Nice to meet you!"

It also works with all the other aspects of the ALAnimatedSpeech module, so ^stop, ^wait, ^run, will work just as fine. You can also assign tags to your animations and then make it choose random animations for that tag group.

Finally, please be aware that the robot will return to it’s last specified pose after finishing an animation. Hence, if you want the robot to wait in a different position after the animation finished, you will have to do that by creating a custom posture. I have some comments on that here: The hidden potential of NAO and Pepper – Custom Robot Postures in naoqi v2.4

I hope this will be useful to some of you. Please feel free to like, share, or leave a comment below.

Happy coding!

The hidden potential of NAO and Pepper – Custom Robot Postures in naoqi v2.4

Introduction

Our lab owns robots build by SoftBank that we use for experiments; we have a Pepper and some NAOs. At the moment, I’m working on a NAO.

naw_low_quality
NAO looking at a Tower of Hanoi

They are quite pretty robots. I mean, they can barely walk around, let alone navigate the environment, they can’t do proper grasping, the build-in CPU is so slow and hogged by the default modules, and streaming video from the robot for remote processing happens at about 5 FPS. So you can’t really do any of the things you would expect you can do, but hey, they look really cool 😀

Okay, jokes aside, the manufacturing of the robots is actually pretty solid. Being able to get your hands on a biped for about 6000€ is solid, and, despite some stability issues, it can walk – however, nobody really uses that feature in social robotics research. They also come with a huge sensor array, that makes every smartphone jealous. Hardware wise both, NAO and Pepper, are good robots.

The thing that is lacking – by a landslide – is the software. The robots come with an API, but that API is proprietary – in itself, not a problem. The problem starts where the documentation ends. Documentation is shaky, disorganized, not very clear, and – for all the cool parts – nonexistent. In short, you don’t get to read the code and you don’t get good documentation to help you either; hence, if something breaks, you are blind and deaf somewhere in the forest of code and have to find the way out yourself.

Pepper can grasp, it can do navigation, and you can stream video data at a decent FPS – the same is true for NAO; it can do all the things I just complained about. You just have to write the code yourself.

This is what I will talk about in this post. I will not go into grasping or walking, but we will look into navigating the joint space more efficiently. That is, we will have a more in-depth look at ALRobotPosture, some of the hidden / undocumented functions, and how we can use this module for some pretty sick motion planning.

Note: Everything in this post works for both NAO and Pepper. For ease of reading, I will only reference the NAO, because – I think – that is the robot most people reading this will own.

ALRobotPosture, an Overview

If you own either a NAO or a Pepper, you have probably noticed that, when you turn (and autonomous life activates) it on, it moves into a certain pose. For Pepper, it is always the same, for the NAO, it depends if it was turned on sitting or standing. This is RobotPosture in action. The same is true after we play an animation. Once it finishes, NAO moves back into a specific pose, waiting for the next command.

This is the most visible action of the module. When no other movement task is running, it will move the NAO into a stable position. The other thing it does, is it transitions between these stable poses. For example, when you want NAO to either sit down or stand up, then it doesn’t play an animation. It actually uses RobotPosture to navigate the joint space from one stable posture to another until it reaches the Sit or Stand posture respectively.

In essence, RobotPosture is a list of configurations – points in joint space – that serve as stable positions the robot can move into. These points are connected; there is a neighbor relationship between them. They are also attractive; hence, when no other motion is running, NAO will move into the closest posture (closeness being defined as closeness in joint space).

The interesting part is that movement between poses is not done as a direct line in joint space. This could be rather dangerous, since the robot would just fall, if it would move in a straight line from the Stand to Sit. Instead, planning is done in the topological map – a directed graph -, that is defined by the poses and their neighbors. NAO then moves in a (joint space) direct line from the current pose to a neighboring pose and goes through different poses until it reaches the final, desired pose.

I visualized the standard poses in Figure 1. Additionally, there is the USRLookAtTower pose, which is a custom posture I’ve added for a project I’m working on. You can also see it in the picture I chose for the beginning of the post. It looks a lot like normal sitting, but the head is tilted downwards. I will walk you through how I did that in the next section. I also color coded the sitting and standing postures, because they are the most used – but mainly because it looks nice 🙂 .

PostureVisualization.png
Figure 1: Visualization of the available postures on a NAO v4. The distances between nodes roughly correspond to the euclidean distance in joint space. Big nodes are targets for ALRobotPosture.goToPosture(), small nodes are used for the transition. Blue nodes belong to the family Sitting and red nodes belong to the family Standing.

The graph is laid out using force-directed graph drawing, where the force corresponds to the euclidean distance between nodes in joint space. However, I took a bit of liberty to prevent label overlap. As you can see, there is no direct connection between Sit and Stand; the robot would move through unstable territory. (We could, however, add such trajectories ourselves, creating a fast, dynamic stand up motion – e.g., for robot football.)

Another advantage of this approach is that it is very computationally efficient. Since we have an abstract map of how poses are connected, we can quickly figure out if a pose is reachable, and compute a path to that given pose.

Enough theory, show some code already! Okay … okay. Here is how to use the basics of the module:


from naoqi import ALBroker
from naoqi import ALProxy
# start a local broker that connects to the NAO
robot_ip = "your-ip-here"
myBroker = ALBroker("myBroker", "0.0.0.0", 0, robot_ip, 9559)
# get a handle to the module
posture_proxy = ALProxy("ALRobotPosture")
tts_proxy = ALProxy("ALTextToSpeech")
announcement = "I am in posture {posture}. It is part of {posture_family}."
# list current postures
postures = posture_proxy.getPostureList()
print(postures)
# round-trip through all available postures
for posture in postures:
posture_proxy.goToPosture(posture, 1.0)
posture_family = posture_proxy.getPostureFamily()
# not needed, just for demonstration
posture_name = posture_proxy.getPosture()
tts_proxy.say(announcement.format(posture=posture_name,
posture_family=posture_family))

view raw

basics.py

hosted with ❤ by GitHub

The snippet will make the robot run through all the available poses and announce the pose’s name once there. This is about the best you can do with the official part of ALRobotPosture; not that much.

Hidden Features

There is a lot more functionality in the module. There just isn’t any documentation of it on the web. We can look at all the methods in a module via:


from naoqi import ALBroker
from naoqi import ALProxy
from pprint import pprint
# start a local broker that connects to the NAO
robot_ip = "your-ip-here"
myBroker = ALBroker("myBroker", "0.0.0.0", 0, robot_ip, 9559)
# get a handle to the module
posture_proxy = ALProxy("ALRobotPosture")
pprint(posture_proxy.getMethodList())

Alternatively we can use qicli (with the parameter –hidden) to list all the functions in a similar fashion. Qicli is documented here.

Here we can find a few very promising functions:

_isRobotInPosture(string, float, float)

This function is similar to getRobotPosture(). However, instead of giving the current posture, it gives a boolean that is true if the robot is in the given posture. The two floats are threshold values for the joint angles and stiffness. That is, by how much is the current pose allowed to deviate from the defined pose for us to consider them the same.

It returns a triple of (bool, [bool] * 26, [bool] * 2) on a NAO robot. The first boolean tells us if the pose has been reached overall, the second is a breakdown if the pose has been reached for each joint. Finally, the last array is the same for stiffness.

This function is useful if two poses are close together. In this case getRobotPosture() may not show the correct pose; however, we can still differentiate with _isRobotInPosture().

_loadPostureLibraryFromName(string)

Make your own network of postures, export it, use this to upload it to an army of NAOs, and dominate the world.

Given a serialized graph of poses, it will load it and replace the current posture graph. The string is the (relative) path to the file. It returns a boolean indicating if the loading has succeeded.

Important: The file path is relative to ~/.local/share/naoqi/robot_posture on the robot, so the posture file has to be stored in that directory on the robot.

_generateCartesianMap()

This is a strange one. While not immediately useful to us, it will re-generate a Cartesian map that the module uses internally to navigate between poses. You have to call this after loading a new posture library or adding individual postures. Otherwise the new postures won’t work!

_getIdFromName(string)

Pretty self explanatory. Look up the id of the posture using it’s name. Takes the name of the posture and returns an integer that is the id.

_isReachable(int)

Takes a posture id and returns a boolean. True if the posture is reachable from the current robot pose.

__savePostureLibrary(string)

The string is the name that we want to save the file as and it will be saved under ~/.local/share/naoqi/robot_posture on the robot.

_addNeighbourToPosture(int, int, float)

Adds a vertex to the graph pointing from the first posture (indexed by the first int) to the second posture. The third value is the cost of traversing along this edge, which can be used for more sophisticated path planning.

_saveCurrentPostureWithName(int, string)

Saves the current pose as an edge with ID int and name string.

 

Custom Poses

Putting all these together, we can create custom poses as follows:

  1. Use the Animation Mode (or any other method) to move NAO into the desired pose
  2. _saveCurrentPostureWithName() to add the node to the graph
  3. _addNeighbourToPosture() to connect it to the graph (edges are directed! we have to add both ways)
  4. export the postures via _savePostureLibrary() (this will save the file in the correct place)
  5. In our code: import our custom poses using _loadPostureLibraryFromName()
  6. re-generate the cartesian map _generateCartesianMap()
  7. goToPosture()

Here is a code snippet that adds a custom posture called “myPosture”, exports the library, imports it, makes the robot sit down, and then go into “myPosture”.


from naoqi import ALBroker
from naoqi import ALProxy
from pprint import pprint
# start a local broker that connects to the NAO
robot_ip = "love"
myBroker = ALBroker("myBroker", "0.0.0.0", 0, robot_ip, 9559)
# get a handle to the module
posture_proxy = ALProxy("ALRobotPosture")
file_name = "firefoxmetzger-awesome-pose.pose"
posture_proxy._saveCurrentPostureWithName(9942, "myPosture")
custom_posture_id = 9942
stand_posture_id = posture_proxy._getIdFromName("Stand")
posture_proxy._addNeighbourToPosture(stand_posture_id, custom_posture_id, 1)
posture_proxy._addNeighbourToPosture(custom_posture_id, stand_posture_id, 1)
posture_proxy._savePostureLibrary(file_name)
posture_proxy._loadPostureLibraryFromName(file_name)
posture_proxy._generateCartesianMap()
posture_proxy.goToPosture("Sit", 0.5)
posture_proxy.goToPosture("myPosture", 0.5)

And just for good measure, a video showing what the robot does when running the snippet:

Naturally, you can be more fancy with this. I am particularly excited about the possibility to do dynamic movements, i.e., one-way trajectories. However, my supervisor will probably kill me if I actually dabble in this area, because the chances of breaking a NAO like this are … elevated.

I hope this article is useful. If you liked it, feel free to leave a like, comment, or follow this blog! I will keep posting tutorials in the area of robotics, AI, and social robotics research.

Happy coding!

Google Code Jam 2018: Trouble Sort

Link to the exercise.

The second problem in this years Code Jam was Trouble Sort. This problem was substantially easier then the first one. At least for the small test.

The idea is that one performs bubble sort with three elements at a time and, if the last element in the triplet bigger then the first, one reverses the entire 3-element sub-list. Pseudo-code for this algorithm was given. The goal of the exercise was to, given a list, sort that list using above strategy and then asserting that it was ordered. If it was one should print “OK” otherwise one should print the index of the (0-indexed) first element of non-increasing order (e.g. [3,9,7] should return 1).


import sys
def trouble_sort(L):
# in place sorting
done = False
while not done:
done = True
for idx in range(len(L) 2):
if L[idx] > L[idx + 2]:
done = False
L[idx],L[idx+1], L[idx + 2] = L[idx + 2], L[idx+1], L[idx]
def assert_list(sorted):
# there is a bug, but I don't see it
idx = 0
while idx < len(sorted) 1:
if sorted[idx] <= sorted[idx+1]:
idx += 1
else:
return str(idx)
return "OK"
def fast_sort(unsorted):
list1 = unsorted[0::2]
list2 = unsorted[1::2]
list1.sort()
list2.sort()
# concatenate the list
unsorted[0::2] = list1
unsorted[1::2] = list2
def next_case(file):
test_cases = list()
num_cases = int(file.readline())
for case_idx in range(num_cases):
N = int(file.readline())
read_list = [int(elem) for elem in file.readline().split(" ")]
assert len(read_list) == N
test_cases.append((N,read_list))
return test_cases
if __name__ == "__main__":
test_cases = next_case(sys.stdin)
for idx, case in enumerate(test_cases):
N, test_list = case
fast_sort(test_list)
result = assert_list(test_list)
print("Case %d: %s" % (idx+1,result))

view raw

trouble_sort.py

hosted with ❤ by GitHub

The problem with passing the big test was that lists could have up to `10^8` many elements and above trouble sort implementation has `O(n^2)`. This means using the naive implementation will quickly run into the timeout.

The “trick” is to see that trouble sort is equivalent to splitting the unsorted list into elements with even and odd index, sorting them and then concatenating those sorted lists. Since this sort can use a reasonably fast algorithm (e.g. pythons native one) it can happen in O(n*log(n)) which will be significantly faster and work on the second, big set of tests. (I know this because I read it in the analysis).

The way I got that intuition was thinking about the fact that reversing a three element list is the same as swapping elements i-1 and i+1 . So we swap with a “distance” of two which made me wonder if it would be possible to swap the second and third element in the list in some way. The only swaps that involve the third element are when the “cursor” is at position two and four and that would swap with the first or fifth element respectively which are both uneven numbers. This trend continues for all numbers (even swap with even, odd with odd) and suddenly you begin to see a pattern.

Unfortunately I failed this challenge completely. My logic is correct, however if you look carefully at the last line, you will see that it outputs something like “Case 1:” however it should output “Case #1:”. I spent over 2 hours trying to find the mistake…

Sometimes it’s the small things that catch you. This probably won’t happen to me again … ever.

Google Code Jam 2018: Saving The Universe Again

During last week I’ve learned about a Code Jam hub in our University. The idea is to meet up and participate in the Google Code Jam 2018 . I ended up participating and advancing into the first round, so I thought I’d share my solutions here for anybody interested. (And for me for further reference)

Task 1: Saving The Universe Again (Link)

An alien robot is shooting a beam that will destroy all algorithms knowledge (not sure how an algorithm can have knowledge, but lets not get philosophical).

The beam starts with strength of 1 and follows a given sequence of actions (string with two literals “S” and “C”). Whenever it shoots “S” it deals damage equal to it’s current strength and whenever it charges “C” the strength is doubled. The sequence “SCSS” would thus deal 5 damage.

You have a shield that can absorb D damage (humanity needs the D!) and can swap any two adjacent literals in the string. What is the minimal number of swaps to reduce the damage dealt to a number <= D? (If impossible return “IMPOSSIBLE”)

You can understand this problem as a tree search (again! gives you a competitive advantage to know these things). The state is the current string and it’s children are all the new states that result from swapping in different places. For each such state you can calculate the damage. To find the closest node to the root node that has damage <= D a possibility is to use simple breadth first search.

Breaching from my usual style I will post the code first and then talk about it below. This is the pure, unmodified code I submitted during the hub, so it is intentionally left a bit messy. It’s still fairly readable though … It’s python and it’s short.


from collections import deque
import sys
def get_damage(sequence):
current_strength = 1
damage = 0
for char in sequence:
if char == "C":
current_strength *= 2
if char == "S":
damage += current_strength
return damage
def get_nodes(sequence):
list_sequence = list(sequence)
children = list()
for idx in range(len(list_sequence) 1):
new_node = list_sequence.copy()
new_node[idx], new_node[idx + 1] = new_node[idx + 1], new_node[idx]
children.append("".join(new_node))
return children
def get_moves(initial_sequence, shield):
q = deque()
# tupel in queue:
# (damage, node, num_swaps)
visited = dict()
current_best = (get_damage(initial_sequence),initial_sequence, 0)
q.appendleft(current_best)
while q:
damage, node, num_swaps = q.pop()
if damage <= shield:
return (damage, node, num_swaps)
if damage < current_best[0]:
current_best = (damage, node, num_swaps)
if node in visited:
continue
visited[node] = (damage, num_swaps)
for child in get_nodes(node):
dmg = get_damage(child)
q.appendleft((dmg, child, num_swaps + 1))
return (current_best[0],current_best[1],"IMPOSSIBLE")
# do pruning on minimum damage and max
def read_file(location):
with open(location, "r") as f:
return next_case(f)
def next_case(file):
test_cases = list()
num_cases = file.readline()
for line in file:
line = line[:1]
shield, sequence = line.split(" ")
test_cases.append((int(shield), sequence))
return test_cases
if __name__ == "__main__":
#test_cases = read_file("foo.txt")
test_cases = next_case(sys.stdin)
for idx, case in enumerate(test_cases):
shield, sequence = case
num_moves = get_moves(sequence, shield)
print("Case #%d: %s" % (idx+1, str(num_moves[2])))

view raw

shield.py

hosted with ❤ by GitHub

Note: This will work for “small” sequences and is too inefficient for large ones. The branching factor of the tree is len(sequence)-1 which can be up to 30. I timed out on the second (big) test, because I didn’t optimize this part.

Pure breadth first search on a tree with branching factor >10 is generally not a good idea. As such I’ve implemented the search using a queue rather then choosing a recursive approach. This allows to better scale the code as ideas for run time optimization come in.

By optimization I mean pruning of nodes that are clearly disadvantageous. One example is in line 32 where I keep a dictionary of nodes that have been visited. If I encounter the same state again, I already know a shorter path to it; thus I can safely ignore it. To be honest, I should have done the weeding out directly in get_nodes to reduce constant overhead.

Another optimization, which I didn’t implement, would be to see that this is a convex problem. There is exactly one clear minimum (S[…]SC[…]C) and one clear maximum (C[…]CS[…]S) along the border of the problem and there are no local optima in between. Thus, we can ignore all swaps that increase the damage or keep it constant, i.e. “SS”, “SC”, “CC”, and focus on those that swap “CS” into “SC”. This will severely decrease the branching factor. (Note: We already ignore “SS” and “CC” as part of above optimization)

Another consequence of this is that we can swap the queue type from a FIFO (i.e. breadth first) into a priority queue, sorting by current damage dealt choosing the node with lowest damage as the next node. This is essentially Dijkstra’s algorithm (as we don’t use a heuristic, otherwise it would be A*). It keeps amazing me again and again how easily you can swap between different tree searches by simply changing the queue type.

Applying those three optimizations should cut down search time by enough to cope with the big test. It also gets very close to the other solutions I’ve seen; that is “pass over the string back to front and switch all “CS” into “SC”. Repeat until no change was made for an entire sweep of the string and then output the total number of swaps. My approach is simply more formal and can be applied to other problems more easily.