Showing a single Spittle

In our Spring Spitter Web App we want to display any single Spittle, just passing its id. This could be easily done accepting a request in the form of "spittles/show?id=42", following the style we have just used for getting a list of spittles, but we don't like it that much here, since we feel that "spittles/42" will be more expressive of the access to a resource.

Good for us, the Spring Framework has an handy approach to this problem.

Stripping down the view to the limit, what we want to get is something like this:
I have get it through a JSP page with JSTL tags, spittle.jsp, accessing an attribute named spittle that contains a Spittle object. Besides that minimal JSP, I have added a mock test to ensure the new functionality works fine. I have not much to say about them, and anyway you can see them on GitHub.

Let's see instead the new method added to SpittleController.
@RequestMapping(value = "/{spittleId}", method = RequestMethod.GET)
public String spittle(@PathVariable long spittleId, Model model) {
    model.addAttribute(spittleRepository.findOne(spittleId));
    return "spittle";
}
The spittle() method returns a string, the name of the view that should be generated for the caller, and expects two parameters, the spittle id and the model where we are going to push the Spittle object.
Notice that its first parameter is annotated as PathVariable, and notice also as the method is annotated as RequestMapping, with value set to a path. the path is built using curly brackets, signalling to Spring what is a variable that has to be extracted and used as parameter.
Being the class itself annotated as RequestMapping on "/spittles", the Spring framework is smart enough to understand what we want to do here.

Reference: Taking input via path parameters, from Spring in Action, Fourth Edition by Craig Walls. Chapter five, section 3.2.

You can find the code I have written on GitHub.

Go to the full post

Showing a paged list of spittles

As next step in our little Spring Web App, we are going to add in the view a way to display spittles specifying the "end" id, using the standard convention that it is excluded from the interval, and how many of them we want to show.

To do that, I firstly change the SpittleController so that its method mapped to the GET request method would accept the two parameters, giving them default values so that the previous functionality still works.
@RequestMapping(method = RequestMethod.GET)
public List<Spittle> spittles(
        @RequestParam(value = "max", defaultValue = MAX_ID) long max,
        @RequestParam(value = "count", defaultValue = DEFAULT_COUNT) int count) {
    return spittleRepository.findSpittles(max, count);
}
Actually, this version looks quite different from the previous one. The return value here is a List of Spittles, the one that was put in the spittleList model, and so we should wonder how Spring could guess which JSP call to generate a view.

However, internally, they are equivalent - if we don't consider how findSpittles() is called. The job of generating the JSP page and the attribute name is done by the mighty Spring framework, that understands that the first should be extracted from the URI passed as string to the class RequestMapping annotation, "/spittles", stripping the leading slash, and builds the latter from the method return type.

Just a minor nuisance. As the Java compiler states, "The value for annotation attribute RequestParam.defaultValue must be a constant expression". So I can't define MAX_ID converting on the fly the Long.MAX_VALUE to a String:
private static final String MAX_ID = Long.toString(Long.MAX_VALUE); // WON'T WORK!
I have to operate the conversion "by hand", instead.
private static final String MAX_ID = "9223372036854775807"; // Boring!
Besides the already existing shouldShowRecentSpittles() test, that should still work, I added a new shouldShowPagedSpittles() test that is very close to the other one but passes parameters to the (mock) call to the controller. See the tester on GitHub for more details.

Given the fake implementation I gave to the JdbcSpittleRepository, I can also see a result from the browser.
Reference: Accepting request input, from Spring in Action, Fourth Edition by Craig Walls. Chapter five, section three.

Full code for this Spring project is on GitHub.

Go to the full post

From Model to View through a Spring Controller

Another improvement to our little Spittr Spring Web App. We'll fake a JDBC model, create a controller that would get some data from it and pass it to the view, a JSP page that uses EL to access the attribute.

In the end we want to display to the user a very simple web page like this one:
enter in the details of the JSP page, you can find it in my GitHub repository, I just mention the fact that the controller puts a list of Spittles in an attribute named spittleList, and the page reads it by EL looping through a core forEach JSTL tag.

The data is moved around in a POJO, spittr.Spittle, that contains the data identifying a spittle. There is not much to say about it, besides it has its own equals() and hashCode() implementation, that are respectively based on the equals() and hash() methods from the utility class Objects:
// ...

public class Spittle {
    private final Long id;
    private final String message;
    private final LocalDateTime time;
    private Double latitude;
    private Double longitude;

 // ...

    @Override
    final public boolean equals(Object that) {  // 1
        if(this == that) {
            return true;
        }
        if (!(that instanceof Spittle))
            return false;

        Spittle other = (Spittle) that;
        return this.id == other.id && Objects.equals(this.time, other.time);  // 2
    }

    @Override
    public int hashCode() {
        return Objects.hash(id, time);  // 3
    }
}
1. I do not expect the class Spittle to be extended. In case a subclass would be created, it's implementation won't modify the assumption that two spittles are considered equals if they have same id and creation timestamp, as stated in this equals() method. To enforce it, I mark it as final.
2. Using Objects.equals() saves me from the nuisance of checking the time component against null, keeping the code more readable.
3. Since id and time define Spittle equality, it makes sense using them to determine the hash code.

I have written a test case to ensure the Spittle class works as I expected. There is nothing very interesting in it and, as usual, you can look it on GitHub.

The model will be based on the interface spittr.data.SpittleRepository:
public interface SpittleRepository {
    List<Spittle> findRecentSpittles();

    List<Spittle> findSpittles(long max, int count);

    Spittle findOne(long id);

    void save(Spittle spittle);
}
The idea is creating a JDBC repository, for the moment I have faked it. Here is its findSpittles() method:
@Repository
public class JdbcSpittleRepository implements SpittleRepository {
    // ...
    @Override
    public List<Spittle> findSpittles(long max, int count) {
        List<Spittle> result = new ArrayList<>();
        for (long i = 0; i < count; i++) {
            result.add(new Spittle(i, "Message " + i, LocalDateTime.now(), 1.0 * i, 2.0 * i));
        }

        return result;
    }
    // ...
}
The repository interface is used in the SpittleController to find spittles an put them as attribute to be consumed by the view.
@Controller
@RequestMapping("/spittles")
public class SpittleController {
    private SpittleRepository spittleRepository;

    @Autowired
    public SpittleController(SpittleRepository spittleRepository) {
        this.spittleRepository = spittleRepository;
    }

    @RequestMapping(method = RequestMethod.GET)
    public String spittles(Model model) {
        model.addAttribute("spittleList", spittleRepository.findSpittles(Long.MAX_VALUE, 20));
        return "spittles";
    }
}
I use the concrete repository to see what happens when the app actually runs on my tomcat server, however, the real testing is performed on the interface, using the mocking features included in Spring integrated to the mockito framework. For this reason I added this dependence to the application POM.
<dependency>
    <groupId>org.mockito</groupId>
    <artifactId>mockito-core</artifactId>
    <version>${mokito.version}</version>
    <scope>test</scope>
</dependency>
I also have to tell Spring where the repository is. For this reason I created a new configuration class, DataConfig, that simply returns the JdbcSpittleRepository as a bean. This configuration class is called by the already existing RootConfig, by importing it.
@Configuration
@Import(DataConfig.class)
public class RootConfig {
}
The web app works fine both running it "by hand" and through the mock test. So I pushed the code on GitHub.

Reference: Passing model data to the view, from Spring in Action, Fourth Edition by Craig Walls. Chapter five, section 2.3.

Go to the full post

Mock test for a Spring controller

Having built a simple Spring Web App, now I want to test its only controller. In the previous post I have done it "by hand", running a browser on its url and verifying that I actually get the expected page, now I use the mock testing support provided by the Spring framework.

Firstly I add to the pom file the Spring test dependency:
<properties>
 <!-- ... -->
 <spring-test.version>4.3.0.RELEASE</spring-test.version>
 <!-- ... -->
</properties>
<dependencies>
 <!-- ... -->
 <dependency>
  <groupId>org.springframework</groupId>
  <artifactId>spring-test</artifactId>
  <version>${spring-test.version}</version>
  <scope>test</scope>
 </dependency>
 <!-- ... -->
</dependencies>
Then I write a JUnit tester for my HomeController, following a simple pattern:
@Test
public void testHome() {
    HomeController controller = new HomeController();  // 1
    try {
        MockMvc mockMvc = standaloneSetup(controller).build();  // 2
        mockMvc.perform(get("/")).andExpect(view().name("home"));  // 3
    } catch(Throwable t) {  // 4
        // ...
    }
}
1. I create an object from my controller.
2. I build a mock MVC test object from my controller.
3. I perform a mock HTTP GET command for "/" and verify I get back a view named "home".
4. There is not much control on what a MockMvc would throw in case something goes wrong, we have to be ready to catch any possible throwable.

It looks very clean and simple. However I had a problem in the form of this exception:
java.lang.NoClassDefFoundError: javax/servlet/SessionCookieConfig at
 org.springframework.test.web.servlet.setup.StandaloneMockMvcBuilder.
  initWebAppContext(StandaloneMockMvcBuilder.java:329)
...
The fact is that I specified in the POM a dependency for the ancient javax.servlet servlet-api 2.5, while I should use at least a version 3 to get the job done. For my purposes, 3.1.0 is more than enough.
Pay attention to the artifact name change that happened right at the time of moving from 2 to 3. Now the servlet api is identified by the id javax.servlet-api.

Let's slightly improve my web app. We want now that the controller returns the home view while getting both root and "/homepage".

I add another test case, testHomeExtra(), that is just like testHome() but it performs a GET on the other URI.
As expected, it fails, giving as reason, "No ModelAndView found".

I change my controller, specifying at class level which URI's it has to manage:
@Controller
@RequestMapping({"/", "/homepage"})
public class HomeController {
    @RequestMapping(method = GET)
    public String home(Model model) {
        return "home";
    }
}
And now I have green light while testing.
Reference: Building Spring web applications, from Spring in Action, Fourth Edition by Craig Walls. Chapter five, section two, Testing the controller.

I have committed the project changes to GitHub.

Go to the full post

Spittr - a Spring Web Application

I am going to create a Spring Web Application using as IDE the Spring Tool Suite, friendly known as STS, version 3.8.4, without the Spring Boot support. To do that, we can theoretically use the wizard named Spring Legacy Project, but the support from Pivotal is not so strong as I expected and the result needs so many adjustments that in the end I opted to use the basic Maven Project wizard instead.

I selected the archetype with artifact id maven-archetype-webapp from the group id org.apache.maven.archetypes, gave a group and artifact id to my app, and let the wizard go.

Annoyingly, I got an error and a warning:
The superclass "javax.servlet.http.HttpServlet" was not found on the Java Build Path means that the generated POM lacks that dependency. Actually, opening the POM, I see that it lacks almost any dependency, and the only one present, JUnit, refers to the old 3.8.1 version.
The warning points out to the fact that the wizard was designed to support the ancient Java 5, and we'd probably better adjust the project also in this area.

I changed the POM adding these properties and dependencies:
<properties>
 <java.version>1.8</java.version>
 <project.build.sourceEncoding>UTF-8</project.build.sourceEncoding>
 <jsp.version>2.2</jsp.version>
 <jstl.version>1.2</jstl.version>
 <servlet.version>2.5</servlet.version>
 <spring-framework.version>4.3.7.RELEASE</spring-framework.version>
 <junit.version>4.12</junit.version>
</properties>

<dependencies>
 <dependency>
  <groupId>org.springframework</groupId>
  <artifactId>spring-webmvc</artifactId>
  <version>${spring-framework.version}</version>
 </dependency>
 <dependency>
  <groupId>javax.servlet</groupId>
  <artifactId>jstl</artifactId>
  <version>${jstl.version}</version>
 </dependency>
 <dependency>
  <groupId>javax.servlet</groupId>
  <artifactId>servlet-api</artifactId>
  <version>${servlet.version}</version>
  <scope>provided</scope>
 </dependency>
 <dependency>
  <groupId>javax.servlet.jsp</groupId>
  <artifactId>jsp-api</artifactId>
  <version>${jsp.version}</version>
  <scope>provided</scope>
 </dependency>
 <dependency>
  <groupId>junit</groupId>
  <artifactId>junit</artifactId>
  <version>${junit.version}</version>
  <scope>test</scope>
 </dependency>
</dependencies>
To get rid of the warning, I opened the Project Properties and in the page Project Facets I set Java to 1.8.
The wizard created an index.jsp page in the webapp folder. I removed it and I created instead a home.jsp in the WEB-INF views subfolder. This JSP page uses the JSTL core library and a style sheet named style.css from the resources folder. All of these details are not much relevant with the job of creating the web app, so I won't say more on them. For more reference see the full source code on GitHub.

More interestingly, let see the dispatching stream of our application. We are going to use the MVC Spring structure, at the center of it there is the DispatcherServlet that decides how to manage the user requests to generate appropriate responses. From our side, we provide a Java class to configure it. The job is simplified by extending AbstractAnnotationConfigDispatcherServletInitializer and a couple of configuration classes. Our class would be automatically seen by Spring and used to configure the DispatcherServlet.

At the end of all this dispatching and configuring, we'll have a tiny web app that would have just the home.jsp as available view.
Here is the project structure:

Our initializer should override three methods from its super class:
public class SpitterWebInitializer extends AbstractAnnotationConfigDispatcherServletInitializer {
    @Override
    protected String[] getServletMappings() {  // 1
        return new String[] { "/" };
    }

    @Override
    protected Class[] getRootConfigClasses() {  // 2
        return new Class[] { RootConfig.class };
    }

    @Override
    protected Class[] getServletConfigClasses() {  // 3
        return new Class[] { WebConfig.class };
    }
}
1. It returns the paths that the DispatcherServlet will be mapped to. We are mapping to the root directory, handling all the requests to our app.
2. It returns the configuration classes for the application context created by the ContextLoaderListener. You would usually find here middle and data tier components. In this trivial version of our app, there will be nothing in here. I still delegate to RootConfig, even if it won't do anything, to keep the code clean. More brutally, I could have let this method return null.
3. This is about the standard DispatcherServlet configuration. Controllers, view resolvers and handler mappings are returned by this method.

Let's see our WebConfig:
@Configuration  // 1
@EnableWebMvc  // 2
@ComponentScan("spittr.web")  // 3
public class WebConfig extends WebMvcConfigurerAdapter {  // 4
    @Bean
    public ViewResolver viewResolver() {  // 5
        InternalResourceViewResolver resolver = new InternalResourceViewResolver();
        resolver.setPrefix("/WEB-INF/views/");
        resolver.setSuffix(".jsp");
        return resolver;
    }

    @Override
    public void configureDefaultServletHandling(DefaultServletHandlerConfigurer configurer) {
        configurer.enable();  // 6
    }
}
1. It is a Spring configuration class.
2. This is a typical way to say that our app should enable the Spring MVC.
3. Ask Spring to enable component scanning from the passed package.
4. We extends our configuring class from this configurer adapter provided by Spring
5. We create a very simple view resolver that would set a prefix, the /WEB-INF/views/ folder, and a suffix, the jsp extension. In this way, a view named "home" would be resolved to "/WEB-INF/views/home.jsp".
6. We say to the DispatcherServlet that it should delegate to static resources the requests it gets.

Then I created a controller in the spittr.web package, so to actually provide something to do to WebConfig:
@Controller
public class HomeController {
    @RequestMapping(value = "/", method = GET)
    public String home(Model model) {
        return "home";
    }
}
Very simple, it just maps the GET requests to root returning the string "home".

Now we can Run on Server our app for the first time.
Reference: Building Spring web applications, from Spring in Action, Fourth Edition by Craig Walls. Chapter five, section one, Getting started with Spring MVC.
Full code is available on GitHub.

Go to the full post

CodeEval Following Integer

Given a number, we should return its follower, accordingly to a weird rule explained on the CodeEval page of this problem. In a few words, we can only use the digits in the number itself, but we can add a zero if we need to.

The provided samples, that I converted to Python tests, give a better idea of our task:
def test_provided_1(self):
    self.assertEqual(151, solution('115'))

def test_provided_2(self):
    self.assertEqual(2048, solution('842'))

def test_provided_3(self):
    self.assertEqual(80000, solution('8000'))
115 is followed by 151. All the other permutations of the three digits are higher than that.
There is no permutation of 842 that is bigger than it. So we need to add a zero, getting 2048.
Same goes for 8000, we have to add a zero getting 80000.

I felt it was too complicated to check the number and trying to build its follower considering its digits, and I went instead for an almost brute force approach that comes naturally from watching the test case. Check the permutations, and see which one is the next one. If there is no next one, add a zero to the number in second position and return it.

I implemented this algorithm in Python3 adding just a tiny variation. First I generate the number with an added zero and then I check all the permutations. The reason for this inversion should be clear following the code.
digits = []
for c in line:  # 1
    if c != '0':
        insort(digits, c)  # 2
while len(digits) <= len(line):  # 3
    digits.insert(1, '0')
result = int(''.join(digits))
1. Loop on the digits of the passed number, stored in the string named line.
2. I store all the digits but the zeros, sorted in natural order, in the buffer list named digits. The insort function comes from the bisect package.
3. Then I push in the buffer all the required zeros after the first, lowest, significative digit. In this way I get the smaller possible number having one cipher more than the passed one.

Now I am ready to loop on all the permutations for the passed number:
current = int(line)
for item in permutations(line):
    candidate = int(''.join(item))  # 1
    if result > candidate > current:  # 2
        result = candidate
1. I get a permutation, I convert it to an integer. See the itertools library for details.
2. If the current candidate is less than the tentative solution and it is bigger that the number passed in input, I discard the previous calculate result and keep the current one.

At the end of the loop I have in result my solution.

I feared that this intuitive algorithm was too expensive. Fortunately, I was wrong. It has been accepted with good points. Test case and python3 script are on GitHub.

Go to the full post

CodeEval Self Describing Numbers

Tell if the number passed in is self-describing, returning 1 in case of success. That number, also known as self-descriptive number, is such that it has in each digit, starting from the leftmost, the number of that digit in the number itself. If this definition looks confusing to you, you are not alone. Have a look to the CodeEval page for this problem, or to the tests here below.

Based on the provided samples, I wrote these tests:
def test_provided_1(self):
    self.assertEqual(1, solution('2020'))  # 1

def test_provided_2(self):
    self.assertEqual(0, solution('22'))  # 2

def test_provided_3(self):
    self.assertEqual(1, solution('1210'))  # 3
1. '2020' has two 0's, no 1's, two 2's, zero 3's. So it is self describing.
2. '22' has two 2's. To be self-describing it should have two 0's and two 1's. So it is not.
3. One 0's, two 1's, one 2's, zero 3's. Yes, it is.

Got it? we say it is self-describing if all its digits have the value of the respective digits counted in the number.

We could write very compact Python solutions to this problem, almost one-liners, still easy to undestand.

First part, we need to count the digits in the input string. The Counter class in collections is designed right for this task:
from collections import Counter

counter = Counter(map(int, line))
I take the input line (that I name "line"), I map its elements to int, and I use them to initialize an object of the class Counter.

Then I use the built-in all to check all the digit in the range from zero to the string size (right open interval, as python standard). If they are all the same value of the counter for the respective digit, I return 1:
return int(all(counter[i] == int(line[i]) for i in range(len(line))))
Simple and convincing, isn't it?

The complete python3 script and unit test is on GitHub.

Go to the full post

CodeEval Happy Numbers

Check if a number is happy. Meaning that, adding up the squares of its digits we get one, or a number that, following the same recursice procedure, leads to one. A better description is on CodeEval. Now I see that I have already solved this problem a few years ago using C++ as implementation language. This time I used Python, and I have to say that the code looks more readable to me.

The core of the procedure to check if a number is happy requires to add on all its squared up digits. Thinking in a pythonic way, I have seen it as summing all the elements resulting from a custom iteration. I focused on the iterative part of this sub-problem, creating a generator that does the job:
def squared_ciphers(number):
    while number:
        number, cipher = divmod(number, 10)  # 1
        yield cipher ** 2  # 2
1. The handy built-in function divmod() returns the quotient and the remainder of the integer division by its passed parameters. I use it to get the rightmost digit in cipher removing it from number.
2. Each digit is squared and returned.

Now I am ready for the main part of the script. I am about to loop indefinitely until I see the number is happy or sad. Luckly we know that this loop is not infinite. See wikipedia for details.
def solution(line):
    candidate = int(line)
    explored = set()
    while candidate != 1:  # 1
        if candidate in explored:  # 2
            return 0
        explored.add(candidate)
        candidate = sum(squared_ciphers(candidate))  # 3
    return 1
1. If I get a 1, the originating number is happy. I can stop looping.
2. I store all the generate numbers in a set, so that I can easily check if I have already seen the current element. If so, I know I am entering a deadly loop, and so I can safely state the checked number is not happy.
3. I need to generate a new number from the current one. I call the generator to get all its squared ciphers, and I send the results to the sum() built-in function, so to get it.

Happy or not, this script nails it. You can get the full Python3 source from GitHub.

Go to the full post

CodeEval String List

In this CodeEval problem we are given a number n and a string. We have to return, as a comma separated list, the sorted collection of all the possible words sized n from the letters in the string.

I have converted the given samples in python tests:
def test_provided_1(self):
    self.assertEqual('a', solution('1,aa'))

def test_provided_2(self):
    self.assertEqual('aa,ab,ba,bb', solution('2,ab'))

def test_provided_3(self):
    self.assertEqual('ooo,oop,opo,opp,poo,pop,ppo,ppp', solution('3,pop'))
And then I spent some time thinking on them.

The first one remembers us that we need to keep only the unique letters in the string. So I would probably use a set to clean it up from repetitions.
The second one gives away a very important clue. The result is obviously the cartesian product between the first and the second letter. Since I am using Python as implementation language, I thought immediately to itertools product().
The third one tells me not to forget to sort the results. So set is useful as intermediate passage, but then I should put the items in a list, so that I can sort it. Besides, it shows me how I have to proceed, iterating on each partial solution applying each time the cartesian product between the previous result and the initial collection of letters.

Well. It looks quite easy now. It just a matter of writing the code.
def solution(line):
    n, data = line.split(',')
    letters = sorted(list(set(data)))  # 1
    result = letters  # 2
    for i in range(int(n)-1):  # 3
        result = ['{}{}'.format(x[0], x[1]) for x in product(result, letters)]  # 4
    return ','.join(result)
1. I use the set collection to remove duplicates, then I convert it to a list, and I sort it.
2. I need to keep the original letter collection aside, so that I can use it as a factor in the cartesian product, so I copy it in another list.
3. If n is 1, I don't have to do anything more, the plain list of single letters has been already generated. Otherwise have have to apply n-1 times the cartesian product.
4. The itertools product() function returns a tuple, I convert it to a plain string, and I push each result in a new list that overwrite the previous result.

There is not much left out to see, however the full code for the test case and python3 script is on GitHub.

Go to the full post

CodeEval Message Decoding

We are given in input an encoded message, and we have to return it decoded. See the CodeEval page for this problem for more details.

Only one sample is presented, and I didn't bother to convert it to a test case, I just ran my Python script passing the provided input and I had visual check on the result. The point is the problem is not difficult, it just takes some time to get understood properly. At least in my case.

However, if this is the input:
$#**\0100000101101100011100101000
We are expecting this output:
##*\$
Here is the logic behind the transformation.

The first characters represent the dictionary used in this message. We know that they are over when we read a zero or a one. In our case they are five:
$#**\
We convert them in a variable size string of zeros and ones, listing all the numbers from zero on, but skipping the ones represented by 1-only binary numbers:
$ -> 0
# -> 00
* -> 01
* -> 10
\ -> 000
If we had a sixth element, it would have been coded as "001".

Then we have a three-character block, that we have to read as a binary number, and give as the size of the following chunks in the message. Here is "010", meaning 2.
We go on reading elements of this size until when we get a terminator, represented by an all-one sequence:
00 00 10 11
We have three valid elements, and a terminator. We get the first part of our message:
# # *
Back to the size, this time is "011", meaning 3. So we get on reading three by three, until the terminator:
000 111
We already knew the only valid character sized 3 was '\', here we have one on it.

Read again the size, is "001". We read one character at the time.
0 1
There is just a single zero before we get 1, that is the sequence terminator. We add '$' to the decoded message and we read again the size, that is zero:
000
End of transmission. The message was "##*\$". Job done.

Writing a solution in Python, I used a generator to create the keys for the letters in the dictionary:
def key_generator():
    size = 1
    cur = 0
    while True:
        yield format(cur, '0{}b'.format(size))
        if cur == 2 ** size - 2:
            size += 1
            cur = 0
        else:
            cur += 1
I keep the generator status in two variables, size, that knows how long should be the generated key, and cur, that knows the binary value that should be pushed in that space.
The yield statement converts the cur value as expected, using both the built-in format() function and the format() string method. The first gets in the cur value and converts it to a string containing its binary representation. The second provides to the numbers of characters that the binary string should take.
Than we prepare to the next iteration. If increasing the cur we'd get a 1-only binary number, we skip it, resetting cur to zero, and increasing the size. Otherwise it is just a matter of increasing cur.

Now I just have to use the generator to map the provided characters to their coded representation:
mapping = {}
i = 0
for key in key_generator():  # 1
    if line[i] not in ['0', '1']:  # 2
        mapping[key] = line[i]
        i += 1
    else:
        break  # 3
1. I instantiate the generator and loop indefinitely on it.
2. If the current character is valid, I couple the key to it in the dictionary that I named mapping.
3. When I detect a '0' or a '1' I stop filling the dictionary.

I implemented the result generation with a boring double loop:
result = []
while True:
    size = int(line[i:i + 3], 2)  # 1
    if size == 0:
        break
    i += 3
    while True:
        chunk = line[i:i+size]  # 2
        i += size
        if chunk not in mapping:  # 3
            break
        result.append(mapping[chunk])  # 4
1. Convert a three character substring in an integer, considering it as binary. If it is zero, job done. Otherwise move the index in the line and go on reading.
2. Get a chunk of the specified size.
3. There is not such a key in the dictionary, meaning, we got a terminator. Interrupt the inner loop.
4. Otherwise convert the chunk in the actual character and put it in the result list.

We just have to collate the result in a string an return it to the caller.

I pushed the Python3 script to GitHub.

Go to the full post

HackerRank Binary Search: Ice Cream Parlor

Given an integer, the budget for two ice creams, and a list of integer, the price of the available flavors, return the 1-based indeces for the two chosen flavors. As stated in the page problem, we should implement a binary search in our solution.

I converted the provided samples in python tests, and I added to them a couple more when I was thinking on possible algorithms:
def test_provided_1(self):
    self.assertEqual('1 4', solution(4, [1, 4, 5, 3, 2]))

def test_provided_2(self):
    self.assertEqual('1 2', solution(4, [2, 2, 4, 3]))

def test_expensive(self):
    self.assertEqual('3 4', solution(10, [2, 2, 4, 6]))

def test_neighbor(self):
    self.assertEqual('3 4', solution(8, [1, 2, 4, 4, 8]))
Instead of using the suggestion given away in the title, I have been magnetically attracted to use a dictionary. The idea is quite simple, I use as key the flavor price, on which I have to perform the search, and as values a keep a list, so that I can push in it the position of all the flavor having the same price.
def solution(money, prices):
    counter = defaultdict(list)  # 1
    for i in range(len(prices)):  # 2
        counter[prices[i]].append(i+1)

    for price, flavors in counter.items():  # 3
        target = money - price
        if target == price:  # 4
            if len(flavors) > 1:
                return '{0} {1}'.format(flavors[0], flavors[1])
        else:
            others = counter.get(target)  # 5
            if others:
                result = sorted([others[0], flavors[0]])
                return '{} {}'.format(*result)
1. When I try to access a value in this dictionary, if the key was not already in, a new empty list is created. Using defaultdict saves my to call setdefault() on a plain dict.
2. I loop on the input array of prices, appending each flavor position (adjusted to be 1-based) to the associated key reporting its price.
3. Loop on all the price/flavors in the dictionary.
4. If the price I am ready to pay for the second flavor is the same of the amount I would pay for the first, I have only to check if the current bucket is used by more than one flavor. If so, I return the first two of them I found.
5. Otherwise, I check if there is in the dictionary a flavor for the price I am willing to pay. If I see it, I sort the two flavors position (as required by the problem) and return them.

This solution works fine, it is clear and fast, and it is accepted by HackerRank. However it is not what we are expected to produce. So I refactored it to use binary search. The rationale behind it could be thought as if we should run this algorithm in an embedded environment, and we found out that using hash tables eats too much memory, so we need to fall back to a slightly slower algorithm that uses a leaner data structure.

What I do now is putting price/flavors couples in a plain list, sort it and then checking for each element if there is a match to it among the other ones.
def solution(money, prices):
def solution(money, prices):
    counter = sorted([(price, flavor+1) for flavor, price in enumerate(prices)])  # 1
    for i in range(len(counter)):
        other = find_other(counter, i, money - counter[i][0])  # 2
        if other:
            result = sorted([counter[i][1], other])
            return '{} {}'.format(*result)
1. In this list comprehension I enumerate the prices. This generates a number of tuples in the format (index, price), I reverse them, increase the index, since we need it as 1-based, and push them in the list. Then I sort it.
2. For each element in the list, I check if there is a match. I pass to the find_other() function, see it below, the list, the current position, the amount I want spend for the ice cream. I expect it to return the other flavor or nothing, in the sense of python None, if it couldn't find it.

Here I finally perform the binary search:
def find_other(counter, pos, price):
    left = pos+1  # 1
    right = len(counter)-1
    while left <= right:  # 2
        mid = (left + right) // 2
        if counter[mid][0] == price:
            return counter[mid][1]

        if counter[mid][0] > price:
            right = mid-1
        else:
            left = mid+1
    return None
1. I don't care about the left-side elements in the counter list, they have been already checked. This saves some minimal searching time and, more interestingly, avoid the risk of a false positive. Think the case that the total budget is 2x and I am looking for a flavor costing x. I could end up finding the same x I have already found. It won't be difficult to skim this case off, but in this way we have it for free.
2. If there is anything in the current interval, I get its central point, I check it against the expected value, if it is not a match move to the side where I could find it.

Also this solution works fine and it is accepted by HackerRank.

On GitHub: The unit test, the binary search version, and the unofficial hash map version.

Go to the full post

The Spring AOP around advice

I am going to add a plain Spring component to my Spring Boot practice web application. The interesting part of it is that I am developing an AOP aspect that is designed to give a few advices in conjunction with a stated join point.

Here is the component, nothing fancy.
@Component
public class PopConcert implements Performance {
    private static final Log log = LogFactory.getLog(PopConcert.class);

    @Override
    public boolean perform(int level) throws PerformanceException {
        if (level > 8) {
            log.info("A nice gig");
            return true;
        } else if (level > 6) {
            log.info("Not in the mood tonight");
            return false;
        } else {
            throw new PerformanceException("Drunk drummer");
        }
    }
}
Its only method returns a boolean or throws and exception, when something really unusual happens.

I have already talked about Spring AOP with aspects in a previous post, let's see now a sligher more complex aspect, that define more advices:
@Aspect
public class Audience {
    private final static Log log = LogFactory.getLog(Audience.class);

    @Pointcut("execution(boolean Performance.perform(int))")  // 1
    public void performance() {}
    
    @Before("performance()")  // 2
    public void silenceMobile() {
        log.info("Silencing mobile phones");
    }

    @Before("performance()")
    public void takingSeat() {
        log.info("Taking seat");
    }

    @AfterReturning("performance()")  // 3
    public void applaude() {
        log.info("Applauding");
    }

    @AfterThrowing("performance()")  // 4
    public void complain() {
        log.info("Demanding a refund");
    }
}
1. Here I define a pointcut. Not a strict necessity, but it saves some typing, and should improve the code readability. I named it "performance()" and I state it refers to the method perfmorm() defined in the Performance interface. All the advices below refer to it.
2. I have a couple of before advices, as the AspectJ annotation says. Here the point is that I can have more methods associated to the same advice.
3. After the execution of the join point has been completed, Spring should follow this advice.
4. If an exception break the join point run, this advice should be followed by Spring.

As usual I let the magic of putting together everything to be performed by a Spring configuration class:
@Configuration
@EnableAspectJAutoProxy
@ComponentScan(basePackageClasses = Performance.class)  // 1
public class ConcertConfig {
    @Bean
    public Audience audience() {  // 2
        return new Audience();
    }
}
1. In this case the only component in the hierarchy based on Performance is the PopConcert class we have seen above.
2. This method let the aspect spring to life.

I have written a JUnit testcase to see it at work:
@RunWith(SpringJUnit4ClassRunner.class)
@ContextConfiguration(classes = ConcertConfig.class)
public class PopConcertTest {
    @Autowired
    private Performance performance;

    @Test
    public void testPerform() {
        try {
            assertTrue(performance.perform(11));
        } catch (PerformanceException pe) {
            fail("Unexpected PerformanceException: " + pe.getMessage());
        }
    }

    @Test(expected=PerformanceException.class)
    public void testPerformBadly() throws PerformanceException {
        performance.perform(2);
    }
}
Running it I have the greenlight and I can see in the log that the aspect has done its job

When an exception occurs in the join point, the AfterThrowing advice is executed, and when all works fine, the AfterReturning is called:
That's nice. But let's see how put all this stuff in a single advice.

AspectJ Around

The around advice gets its join point as an annotation parameter, as usual, and it gets in input, as a parameter a reference to a ProceedingJoinPoint. What we have to do is just specifying in its body what we want to be executed before, after, and even in case of exception. In a natural way, but with a few caveats.
@Aspect
public class AudienceAround {
    private final static Log log = LogFactory.getLog(AudienceAround.class);

    @Around("execution(boolean Performance.perform(int))")
    public Object watchPerformance(ProceedingJoinPoint pjp) throws PerformanceException {  // 1
        Object result = null;  // 2
        try {
            log.info("Ensure mobile is off");
            log.info("Take place");
            result = pjp.proceed();  // 3
            log.info("Cheer");
        } catch (Throwable t) {  // 4
            log.info("Demand a refund: " + t.getMessage());
            if (t instanceof PerformanceException) {
                throw ((PerformanceException) t);  // 5
            } else {
                throw new PerformanceException("Unexpected:" + t.getMessage());  // 6
            }
        }
        return result;
    }
}
1. Our join point throws an exception, so also its Around advice has to throw it too.
2. When it does not throw an exception, it returns a value, so we have to be prepared to to the same. Notice that it returns a primitive type, but the proceed() method in ProceedingJoinPoint returns an object. Some boxing and unboxing is expected.
3. We are passing the control to Spring, that is going to give it to the specified join point.
4. If the join point throws an exception, we'll get a Throwable. It is more or less the same issue we have in (2). Since Spring doesn't know beforehand what throws it, it falls back to the mother of all exceptions.
5. It won't be a good idea to swallow the exception, the caller wants to get it. So here I rethrow it.
6. If I have done everything right, this should never happen.

I have swapped the beans in ConcertConfig. Now a AudienceAround is seen by Spring as the aspect it should care about. I run again the tester and nothing changes, just the log, and in the right way:
Reference: Aspect-oriented Spring, from Spring in Action, Fourth Edition by Craig Walls. Chapter four.
Repository on GitHub: See the JUnit test case, and browse the concert package.

Go to the full post